Google Git
Sign in
llvm / llvm-project / refs/heads/users/avillega/main.clangd-migrate-command-line-option-parsin-to-opttable / . / llvm / lib / Analysis / LazyValueInfo.cpp
blob: 360fc594ef7ca35ff458cb798868cf5c0e1736bc [file] [log] [blame]
//===- LazyValueInfo.cpp - Value constraint analysis ------------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This file defines the interface for lazy computation of value constraint
// information.
//
//===----------------------------------------------------------------------===//
#include "llvm/Analysis/LazyValueInfo.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/ConstantFolding.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/ValueLattice.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/AssemblyAnnotationWriter.h"
#include "llvm/IR/CFG.h"
#include "llvm/IR/ConstantRange.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/Intrinsics.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/IR/ValueHandle.h"
#include "llvm/InitializePasses.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/FormattedStream.h"
#include "llvm/Support/KnownBits.h"
#include "llvm/Support/raw_ostream.h"
#include <optional>
using namespace llvm;
using namespace PatternMatch;
#define DEBUG_TYPE "lazy-value-info"
// This is the number of worklist items we will process to try to discover an
// answer for a given value.
static const unsigned MaxProcessedPerValue = 500;
char LazyValueInfoWrapperPass::ID = 0;
LazyValueInfoWrapperPass::LazyValueInfoWrapperPass() : FunctionPass(ID) {
initializeLazyValueInfoWrapperPassPass(*PassRegistry::getPassRegistry());
}
INITIALIZE_PASS_BEGIN(LazyValueInfoWrapperPass, "lazy-value-info",
"Lazy Value Information Analysis", false, true)
INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
INITIALIZE_PASS_END(LazyValueInfoWrapperPass, "lazy-value-info",
"Lazy Value Information Analysis", false, true)
namespace llvm {
FunctionPass *createLazyValueInfoPass() { return new LazyValueInfoWrapperPass(); }
}
AnalysisKey LazyValueAnalysis::Key;
/// Returns true if this lattice value represents at most one possible value.
/// This is as precise as any lattice value can get while still representing
/// reachable code.
static bool hasSingleValue(const ValueLatticeElement &Val) {
if (Val.isConstantRange() &&
Val.getConstantRange().isSingleElement())
// Integer constants are single element ranges
return true;
if (Val.isConstant())
// Non integer constants
return true;
return false;
}
/// Combine two sets of facts about the same value into a single set of
/// facts. Note that this method is not suitable for merging facts along
/// different paths in a CFG; that's what the mergeIn function is for. This
/// is for merging facts gathered about the same value at the same location
/// through two independent means.
/// Notes:
/// * This method does not promise to return the most precise possible lattice
/// value implied by A and B. It is allowed to return any lattice element
/// which is at least as strong as *either* A or B (unless our facts
/// conflict, see below).
/// * Due to unreachable code, the intersection of two lattice values could be
/// contradictory. If this happens, we return some valid lattice value so as
/// not confuse the rest of LVI. Ideally, we'd always return Undefined, but
/// we do not make this guarantee. TODO: This would be a useful enhancement.
static ValueLatticeElement intersect(const ValueLatticeElement &A,
const ValueLatticeElement &B) {
// Undefined is the strongest state. It means the value is known to be along
// an unreachable path.
if (A.isUnknown())
return A;
if (B.isUnknown())
return B;
// If we gave up for one, but got a useable fact from the other, use it.
if (A.isOverdefined())
return B;
if (B.isOverdefined())
return A;
// Can't get any more precise than constants.
if (hasSingleValue(A))
return A;
if (hasSingleValue(B))
return B;
// Could be either constant range or not constant here.
if (!A.isConstantRange() || !B.isConstantRange()) {
// TODO: Arbitrary choice, could be improved
return A;
}
// Intersect two constant ranges
ConstantRange Range =
A.getConstantRange().intersectWith(B.getConstantRange());
// Note: An empty range is implicitly converted to unknown or undef depending
// on MayIncludeUndef internally.
return ValueLatticeElement::getRange(
std::move(Range), /*MayIncludeUndef=*/A.isConstantRangeIncludingUndef() ||
B.isConstantRangeIncludingUndef());
}
//===----------------------------------------------------------------------===//
// LazyValueInfoCache Decl
//===----------------------------------------------------------------------===//
namespace {
/// A callback value handle updates the cache when values are erased.
class LazyValueInfoCache;
struct LVIValueHandle final : public CallbackVH {
LazyValueInfoCache *Parent;
LVIValueHandle(Value *V, LazyValueInfoCache *P = nullptr)
: CallbackVH(V), Parent(P) { }
void deleted() override;
void allUsesReplacedWith(Value *V) override {
deleted();
}
};
} // end anonymous namespace
namespace {
using NonNullPointerSet = SmallDenseSet<AssertingVH<Value>, 2>;
/// This is the cache kept by LazyValueInfo which
/// maintains information about queries across the clients' queries.
class LazyValueInfoCache {
/// This is all of the cached information for one basic block. It contains
/// the per-value lattice elements, as well as a separate set for
/// overdefined values to reduce memory usage. Additionally pointers
/// dereferenced in the block are cached for nullability queries.
struct BlockCacheEntry {
SmallDenseMap<AssertingVH<Value>, ValueLatticeElement, 4> LatticeElements;
SmallDenseSet<AssertingVH<Value>, 4> OverDefined;
// std::nullopt indicates that the nonnull pointers for this basic block
// block have not been computed yet.
std::optional<NonNullPointerSet> NonNullPointers;
};
/// Cached information per basic block.
DenseMap<PoisoningVH<BasicBlock>, std::unique_ptr<BlockCacheEntry>>
BlockCache;
/// Set of value handles used to erase values from the cache on deletion.
DenseSet<LVIValueHandle, DenseMapInfo<Value *>> ValueHandles;
const BlockCacheEntry *getBlockEntry(BasicBlock *BB) const {
auto It = BlockCache.find_as(BB);
if (It == BlockCache.end())
return nullptr;
return It->second.get();
}
BlockCacheEntry *getOrCreateBlockEntry(BasicBlock *BB) {
auto It = BlockCache.find_as(BB);
if (It == BlockCache.end())
It = BlockCache.insert({ BB, std::make_unique<BlockCacheEntry>() })
.first;
return It->second.get();
}
void addValueHandle(Value *Val) {
auto HandleIt = ValueHandles.find_as(Val);
if (HandleIt == ValueHandles.end())
ValueHandles.insert({ Val, this });
}
public:
void insertResult(Value *Val, BasicBlock *BB,
const ValueLatticeElement &Result) {
BlockCacheEntry *Entry = getOrCreateBlockEntry(BB);
// Insert over-defined values into their own cache to reduce memory
// overhead.
if (Result.isOverdefined())
Entry->OverDefined.insert(Val);
else
Entry->LatticeElements.insert({ Val, Result });
addValueHandle(Val);
}
std::optional<ValueLatticeElement>
getCachedValueInfo(Value *V, BasicBlock *BB) const {
const BlockCacheEntry *Entry = getBlockEntry(BB);
if (!Entry)
return std::nullopt;
if (Entry->OverDefined.count(V))
return ValueLatticeElement::getOverdefined();
auto LatticeIt = Entry->LatticeElements.find_as(V);
if (LatticeIt == Entry->LatticeElements.end())
return std::nullopt;
return LatticeIt->second;
}
bool isNonNullAtEndOfBlock(
Value *V, BasicBlock *BB,
function_ref<NonNullPointerSet(BasicBlock *)> InitFn) {
BlockCacheEntry *Entry = getOrCreateBlockEntry(BB);
if (!Entry->NonNullPointers) {
Entry->NonNullPointers = InitFn(BB);
for (Value *V : *Entry->NonNullPointers)
addValueHandle(V);
}
return Entry->NonNullPointers->count(V);
}
/// clear - Empty the cache.
void clear() {
BlockCache.clear();
ValueHandles.clear();
}
/// Inform the cache that a given value has been deleted.
void eraseValue(Value *V);
/// This is part of the update interface to inform the cache
/// that a block has been deleted.
void eraseBlock(BasicBlock *BB);
/// Updates the cache to remove any influence an overdefined value in
/// OldSucc might have (unless also overdefined in NewSucc). This just
/// flushes elements from the cache and does not add any.
void threadEdgeImpl(BasicBlock *OldSucc,BasicBlock *NewSucc);
};
}
void LazyValueInfoCache::eraseValue(Value *V) {
for (auto &Pair : BlockCache) {
Pair.second->LatticeElements.erase(V);
Pair.second->OverDefined.erase(V);
if (Pair.second->NonNullPointers)
Pair.second->NonNullPointers->erase(V);
}
auto HandleIt = ValueHandles.find_as(V);
if (HandleIt != ValueHandles.end())
ValueHandles.erase(HandleIt);
}
void LVIValueHandle::deleted() {
// This erasure deallocates *this, so it MUST happen after we're done
// using any and all members of *this.
Parent->eraseValue(*this);
}
void LazyValueInfoCache::eraseBlock(BasicBlock *BB) {
BlockCache.erase(BB);
}
void LazyValueInfoCache::threadEdgeImpl(BasicBlock *OldSucc,
BasicBlock *NewSucc) {
// When an edge in the graph has been threaded, values that we could not
// determine a value for before (i.e. were marked overdefined) may be
// possible to solve now. We do NOT try to proactively update these values.
// Instead, we clear their entries from the cache, and allow lazy updating to
// recompute them when needed.
// The updating process is fairly simple: we need to drop cached info
// for all values that were marked overdefined in OldSucc, and for those same
// values in any successor of OldSucc (except NewSucc) in which they were
// also marked overdefined.
std::vector<BasicBlock*> worklist;
worklist.push_back(OldSucc);
const BlockCacheEntry *Entry = getBlockEntry(OldSucc);
if (!Entry || Entry->OverDefined.empty())
return; // Nothing to process here.
SmallVector<Value *, 4> ValsToClear(Entry->OverDefined.begin(),
Entry->OverDefined.end());
// Use a worklist to perform a depth-first search of OldSucc's successors.
// NOTE: We do not need a visited list since any blocks we have already
// visited will have had their overdefined markers cleared already, and we
// thus won't loop to their successors.
while (!worklist.empty()) {
BasicBlock *ToUpdate = worklist.back();
worklist.pop_back();
// Skip blocks only accessible through NewSucc.
if (ToUpdate == NewSucc) continue;
// If a value was marked overdefined in OldSucc, and is here too...
auto OI = BlockCache.find_as(ToUpdate);
if (OI == BlockCache.end() || OI->second->OverDefined.empty())
continue;
auto &ValueSet = OI->second->OverDefined;
bool changed = false;
for (Value *V : ValsToClear) {
if (!ValueSet.erase(V))
continue;
// If we removed anything, then we potentially need to update
// blocks successors too.
changed = true;
}
if (!changed) continue;
llvm::append_range(worklist, successors(ToUpdate));
}
}
namespace llvm {
namespace {
/// An assembly annotator class to print LazyValueCache information in
/// comments.
class LazyValueInfoAnnotatedWriter : public AssemblyAnnotationWriter {
LazyValueInfoImpl *LVIImpl;
// While analyzing which blocks we can solve values for, we need the dominator
// information.
DominatorTree &DT;
public:
LazyValueInfoAnnotatedWriter(LazyValueInfoImpl *L, DominatorTree &DTree)
: LVIImpl(L), DT(DTree) {}
void emitBasicBlockStartAnnot(const BasicBlock *BB,
formatted_raw_ostream &OS) override;
void emitInstructionAnnot(const Instruction *I,
formatted_raw_ostream &OS) override;
};
} // namespace
// The actual implementation of the lazy analysis and update. Note that the
// inheritance from LazyValueInfoCache is intended to be temporary while
// splitting the code and then transitioning to a has-a relationship.
class LazyValueInfoImpl {
/// Cached results from previous queries
LazyValueInfoCache TheCache;
/// This stack holds the state of the value solver during a query.
/// It basically emulates the callstack of the naive
/// recursive value lookup process.
SmallVector<std::pair<BasicBlock*, Value*>, 8> BlockValueStack;
/// Keeps track of which block-value pairs are in BlockValueStack.
DenseSet<std::pair<BasicBlock*, Value*> > BlockValueSet;
/// Push BV onto BlockValueStack unless it's already in there.
/// Returns true on success.
bool pushBlockValue(const std::pair<BasicBlock *, Value *> &BV) {
if (!BlockValueSet.insert(BV).second)
return false; // It's already in the stack.
LLVM_DEBUG(dbgs() << "PUSH: " << *BV.second << " in "
<< BV.first->getName() << "\n");
BlockValueStack.push_back(BV);
return true;
}
AssumptionCache *AC; ///< A pointer to the cache of @llvm.assume calls.
const DataLayout &DL; ///< A mandatory DataLayout
/// Declaration of the llvm.experimental.guard() intrinsic,
/// if it exists in the module.
Function *GuardDecl;
std::optional<ValueLatticeElement> getBlockValue(Value *Val, BasicBlock *BB,
Instruction *CxtI);
std::optional<ValueLatticeElement> getEdgeValue(Value *V, BasicBlock *F,
BasicBlock *T,
Instruction *CxtI = nullptr);
// These methods process one work item and may add more. A false value
// returned means that the work item was not completely processed and must
// be revisited after going through the new items.
bool solveBlockValue(Value *Val, BasicBlock *BB);
std::optional<ValueLatticeElement> solveBlockValueImpl(Value *Val,
BasicBlock *BB);
std::optional<ValueLatticeElement> solveBlockValueNonLocal(Value *Val,
BasicBlock *BB);
std::optional<ValueLatticeElement> solveBlockValuePHINode(PHINode *PN,
BasicBlock *BB);
std::optional<ValueLatticeElement> solveBlockValueSelect(SelectInst *S,
BasicBlock *BB);
std::optional<ConstantRange> getRangeFor(Value *V, Instruction *CxtI,
BasicBlock *BB);
std::optional<ValueLatticeElement> solveBlockValueBinaryOpImpl(
Instruction *I, BasicBlock *BB,
std::function<ConstantRange(const ConstantRange &, const ConstantRange &)>
OpFn);
std::optional<ValueLatticeElement>
solveBlockValueBinaryOp(BinaryOperator *BBI, BasicBlock *BB);
std::optional<ValueLatticeElement> solveBlockValueCast(CastInst *CI,
BasicBlock *BB);
std::optional<ValueLatticeElement>
solveBlockValueOverflowIntrinsic(WithOverflowInst *WO, BasicBlock *BB);
std::optional<ValueLatticeElement> solveBlockValueIntrinsic(IntrinsicInst *II,
BasicBlock *BB);
std::optional<ValueLatticeElement>
solveBlockValueExtractValue(ExtractValueInst *EVI, BasicBlock *BB);
bool isNonNullAtEndOfBlock(Value *Val, BasicBlock *BB);
void intersectAssumeOrGuardBlockValueConstantRange(Value *Val,
ValueLatticeElement &BBLV,
Instruction *BBI);
void solve();
// For the following methods, if UseBlockValue is true, the function may
// push additional values to the worklist and return nullopt. If
// UseBlockValue is false, it will never return nullopt.
std::optional<ValueLatticeElement>
getValueFromSimpleICmpCondition(CmpInst::Predicate Pred, Value *RHS,
const APInt &Offset, Instruction *CxtI,
bool UseBlockValue);
std::optional<ValueLatticeElement>
getValueFromICmpCondition(Value *Val, ICmpInst *ICI, bool isTrueDest,
bool UseBlockValue);
std::optional<ValueLatticeElement>
getValueFromCondition(Value *Val, Value *Cond, bool IsTrueDest,
bool UseBlockValue, unsigned Depth = 0);
std::optional<ValueLatticeElement> getEdgeValueLocal(Value *Val,
BasicBlock *BBFrom,
BasicBlock *BBTo,
bool UseBlockValue);
public:
/// This is the query interface to determine the lattice value for the
/// specified Value* at the context instruction (if specified) or at the
/// start of the block.
ValueLatticeElement getValueInBlock(Value *V, BasicBlock *BB,
Instruction *CxtI = nullptr);
/// This is the query interface to determine the lattice value for the
/// specified Value* at the specified instruction using only information
/// from assumes/guards and range metadata. Unlike getValueInBlock(), no
/// recursive query is performed.
ValueLatticeElement getValueAt(Value *V, Instruction *CxtI);
/// This is the query interface to determine the lattice
/// value for the specified Value* that is true on the specified edge.
ValueLatticeElement getValueOnEdge(Value *V, BasicBlock *FromBB,
BasicBlock *ToBB,
Instruction *CxtI = nullptr);
ValueLatticeElement getValueAtUse(const Use &U);
/// Complete flush all previously computed values
void clear() {
TheCache.clear();
}
/// Printing the LazyValueInfo Analysis.
void printLVI(Function &F, DominatorTree &DTree, raw_ostream &OS) {
LazyValueInfoAnnotatedWriter Writer(this, DTree);
F.print(OS, &Writer);
}
/// This is part of the update interface to remove information related to this
/// value from the cache.
void forgetValue(Value *V) { TheCache.eraseValue(V); }
/// This is part of the update interface to inform the cache
/// that a block has been deleted.
void eraseBlock(BasicBlock *BB) {
TheCache.eraseBlock(BB);
}
/// This is the update interface to inform the cache that an edge from
/// PredBB to OldSucc has been threaded to be from PredBB to NewSucc.
void threadEdge(BasicBlock *PredBB,BasicBlock *OldSucc,BasicBlock *NewSucc);
LazyValueInfoImpl(AssumptionCache *AC, const DataLayout &DL,
Function *GuardDecl)
: AC(AC), DL(DL), GuardDecl(GuardDecl) {}
};
} // namespace llvm
void LazyValueInfoImpl::solve() {
SmallVector<std::pair<BasicBlock *, Value *>, 8> StartingStack(
BlockValueStack.begin(), BlockValueStack.end());
unsigned processedCount = 0;
while (!BlockValueStack.empty()) {
processedCount++;
// Abort if we have to process too many values to get a result for this one.
// Because of the design of the overdefined cache currently being per-block
// to avoid naming-related issues (IE it wants to try to give different
// results for the same name in different blocks), overdefined results don't
// get cached globally, which in turn means we will often try to rediscover
// the same overdefined result again and again. Once something like
// PredicateInfo is used in LVI or CVP, we should be able to make the
// overdefined cache global, and remove this throttle.
if (processedCount > MaxProcessedPerValue) {
LLVM_DEBUG(
dbgs() << "Giving up on stack because we are getting too deep\n");
// Fill in the original values
while (!StartingStack.empty()) {
std::pair<BasicBlock *, Value *> &e = StartingStack.back();
TheCache.insertResult(e.second, e.first,
ValueLatticeElement::getOverdefined());
StartingStack.pop_back();
}
BlockValueSet.clear();
BlockValueStack.clear();
return;
}
std::pair<BasicBlock *, Value *> e = BlockValueStack.back();
assert(BlockValueSet.count(e) && "Stack value should be in BlockValueSet!");
if (solveBlockValue(e.second, e.first)) {
// The work item was completely processed.
assert(BlockValueStack.back() == e && "Nothing should have been pushed!");
#ifndef NDEBUG
std::optional<ValueLatticeElement> BBLV =
TheCache.getCachedValueInfo(e.second, e.first);
assert(BBLV && "Result should be in cache!");
LLVM_DEBUG(
dbgs() << "POP " << *e.second << " in " << e.first->getName() << " = "
<< *BBLV << "\n");
#endif
BlockValueStack.pop_back();
BlockValueSet.erase(e);
} else {
// More work needs to be done before revisiting.
assert(BlockValueStack.back() != e && "Stack should have been pushed!");
}
}
}
std::optional<ValueLatticeElement>
LazyValueInfoImpl::getBlockValue(Value *Val, BasicBlock *BB,
Instruction *CxtI) {
// If already a constant, there is nothing to compute.
if (Constant *VC = dyn_cast<Constant>(Val))
return ValueLatticeElement::get(VC);
if (std::optional<ValueLatticeElement> OptLatticeVal =
TheCache.getCachedValueInfo(Val, BB)) {
intersectAssumeOrGuardBlockValueConstantRange(Val, *OptLatticeVal, CxtI);
return OptLatticeVal;
}
// We have hit a cycle, assume overdefined.
if (!pushBlockValue({ BB, Val }))
return ValueLatticeElement::getOverdefined();
// Yet to be resolved.
return std::nullopt;
}
static ValueLatticeElement getFromRangeMetadata(Instruction *BBI) {
switch (BBI->getOpcode()) {
default: break;
case Instruction::Load:
case Instruction::Call:
case Instruction::Invoke:
if (MDNode *Ranges = BBI->getMetadata(LLVMContext::MD_range))
if (isa<IntegerType>(BBI->getType())) {
return ValueLatticeElement::getRange(
getConstantRangeFromMetadata(*Ranges));
}
break;
};
// Nothing known - will be intersected with other facts
return ValueLatticeElement::getOverdefined();
}
bool LazyValueInfoImpl::solveBlockValue(Value *Val, BasicBlock *BB) {
assert(!isa<Constant>(Val) && "Value should not be constant");
assert(!TheCache.getCachedValueInfo(Val, BB) &&
"Value should not be in cache");
// Hold off inserting this value into the Cache in case we have to return
// false and come back later.
std::optional<ValueLatticeElement> Res = solveBlockValueImpl(Val, BB);
if (!Res)
// Work pushed, will revisit
return false;
TheCache.insertResult(Val, BB, *Res);
return true;
}
std::optional<ValueLatticeElement>
LazyValueInfoImpl::solveBlockValueImpl(Value *Val, BasicBlock *BB) {
Instruction *BBI = dyn_cast<Instruction>(Val);
if (!BBI || BBI->getParent() != BB)
return solveBlockValueNonLocal(Val, BB);
if (PHINode *PN = dyn_cast<PHINode>(BBI))
return solveBlockValuePHINode(PN, BB);
if (auto *SI = dyn_cast<SelectInst>(BBI))
return solveBlockValueSelect(SI, BB);
// If this value is a nonnull pointer, record it's range and bailout. Note
// that for all other pointer typed values, we terminate the search at the
// definition. We could easily extend this to look through geps, bitcasts,
// and the like to prove non-nullness, but it's not clear that's worth it
// compile time wise. The context-insensitive value walk done inside
// isKnownNonZero gets most of the profitable cases at much less expense.
// This does mean that we have a sensitivity to where the defining
// instruction is placed, even if it could legally be hoisted much higher.
// That is unfortunate.
PointerType *PT = dyn_cast<PointerType>(BBI->getType());
if (PT && isKnownNonZero(BBI, DL))
return ValueLatticeElement::getNot(ConstantPointerNull::get(PT));
if (BBI->getType()->isIntegerTy()) {
if (auto *CI = dyn_cast<CastInst>(BBI))
return solveBlockValueCast(CI, BB);
if (BinaryOperator *BO = dyn_cast<BinaryOperator>(BBI))
return solveBlockValueBinaryOp(BO, BB);
if (auto *EVI = dyn_cast<ExtractValueInst>(BBI))
return solveBlockValueExtractValue(EVI, BB);
if (auto *II = dyn_cast<IntrinsicInst>(BBI))
return solveBlockValueIntrinsic(II, BB);
}
LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()
<< "' - unknown inst def found.\n");
return getFromRangeMetadata(BBI);
}
static void AddNonNullPointer(Value *Ptr, NonNullPointerSet &PtrSet) {
// TODO: Use NullPointerIsDefined instead.
if (Ptr->getType()->getPointerAddressSpace() == 0)
PtrSet.insert(getUnderlyingObject(Ptr));
}
static void AddNonNullPointersByInstruction(
Instruction *I, NonNullPointerSet &PtrSet) {
if (LoadInst *L = dyn_cast<LoadInst>(I)) {
AddNonNullPointer(L->getPointerOperand(), PtrSet);
} else if (StoreInst *S = dyn_cast<StoreInst>(I)) {
AddNonNullPointer(S->getPointerOperand(), PtrSet);
} else if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(I)) {
if (MI->isVolatile()) return;
// FIXME: check whether it has a valuerange that excludes zero?
ConstantInt *Len = dyn_cast<ConstantInt>(MI->getLength());
if (!Len || Len->isZero()) return;
AddNonNullPointer(MI->getRawDest(), PtrSet);
if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(MI))
AddNonNullPointer(MTI->getRawSource(), PtrSet);
}
}
bool LazyValueInfoImpl::isNonNullAtEndOfBlock(Value *Val, BasicBlock *BB) {
if (NullPointerIsDefined(BB->getParent(),
Val->getType()->getPointerAddressSpace()))
return false;
Val = Val->stripInBoundsOffsets();
return TheCache.isNonNullAtEndOfBlock(Val, BB, [](BasicBlock *BB) {
NonNullPointerSet NonNullPointers;
for (Instruction &I : *BB)
AddNonNullPointersByInstruction(&I, NonNullPointers);
return NonNullPointers;
});
}
std::optional<ValueLatticeElement>
LazyValueInfoImpl::solveBlockValueNonLocal(Value *Val, BasicBlock *BB) {
ValueLatticeElement Result; // Start Undefined.
// If this is the entry block, we must be asking about an argument. The
// value is overdefined.
if (BB->isEntryBlock()) {
assert(isa<Argument>(Val) && "Unknown live-in to the entry block");
return ValueLatticeElement::getOverdefined();
}
// Loop over all of our predecessors, merging what we know from them into
// result. If we encounter an unexplored predecessor, we eagerly explore it
// in a depth first manner. In practice, this has the effect of discovering
// paths we can't analyze eagerly without spending compile times analyzing
// other paths. This heuristic benefits from the fact that predecessors are
// frequently arranged such that dominating ones come first and we quickly
// find a path to function entry. TODO: We should consider explicitly
// canonicalizing to make this true rather than relying on this happy
// accident.
for (BasicBlock *Pred : predecessors(BB)) {
std::optional<ValueLatticeElement> EdgeResult = getEdgeValue(Val, Pred, BB);
if (!EdgeResult)
// Explore that input, then return here
return std::nullopt;
Result.mergeIn(*EdgeResult);
// If we hit overdefined, exit early. The BlockVals entry is already set
// to overdefined.
if (Result.isOverdefined()) {
LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()
<< "' - overdefined because of pred '"
<< Pred->getName() << "' (non local).\n");
return Result;
}
}
// Return the merged value, which is more precise than 'overdefined'.
assert(!Result.isOverdefined());
return Result;
}
std::optional<ValueLatticeElement>
LazyValueInfoImpl::solveBlockValuePHINode(PHINode *PN, BasicBlock *BB) {
ValueLatticeElement Result; // Start Undefined.
// Loop over all of our predecessors, merging what we know from them into
// result. See the comment about the chosen traversal order in
// solveBlockValueNonLocal; the same reasoning applies here.
for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
BasicBlock *PhiBB = PN->getIncomingBlock(i);
Value *PhiVal = PN->getIncomingValue(i);
// Note that we can provide PN as the context value to getEdgeValue, even
// though the results will be cached, because PN is the value being used as
// the cache key in the caller.
std::optional<ValueLatticeElement> EdgeResult =
getEdgeValue(PhiVal, PhiBB, BB, PN);
if (!EdgeResult)
// Explore that input, then return here
return std::nullopt;
Result.mergeIn(*EdgeResult);
// If we hit overdefined, exit early. The BlockVals entry is already set
// to overdefined.
if (Result.isOverdefined()) {
LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()
<< "' - overdefined because of pred (local).\n");
return Result;
}
}
// Return the merged value, which is more precise than 'overdefined'.
assert(!Result.isOverdefined() && "Possible PHI in entry block?");
return Result;
}
// If we can determine a constraint on the value given conditions assumed by
// the program, intersect those constraints with BBLV
void LazyValueInfoImpl::intersectAssumeOrGuardBlockValueConstantRange(
Value *Val, ValueLatticeElement &BBLV, Instruction *BBI) {
BBI = BBI ? BBI : dyn_cast<Instruction>(Val);
if (!BBI)
return;
BasicBlock *BB = BBI->getParent();
for (auto &AssumeVH : AC->assumptionsFor(Val)) {
if (!AssumeVH)
continue;
// Only check assumes in the block of the context instruction. Other
// assumes will have already been taken into account when the value was
// propagated from predecessor blocks.
auto *I = cast<CallInst>(AssumeVH);
if (I->getParent() != BB || !isValidAssumeForContext(I, BBI))
continue;
BBLV = intersect(BBLV, *getValueFromCondition(Val, I->getArgOperand(0),
/*IsTrueDest*/ true,
/*UseBlockValue*/ false));
}
// If guards are not used in the module, don't spend time looking for them
if (GuardDecl && !GuardDecl->use_empty() &&
BBI->getIterator() != BB->begin()) {
for (Instruction &I :
make_range(std::next(BBI->getIterator().getReverse()), BB->rend())) {
Value *Cond = nullptr;
if (match(&I, m_Intrinsic<Intrinsic::experimental_guard>(m_Value(Cond))))
BBLV = intersect(BBLV,
*getValueFromCondition(Val, Cond, /*IsTrueDest*/ true,
/*UseBlockValue*/ false));
}
}
if (BBLV.isOverdefined()) {
// Check whether we're checking at the terminator, and the pointer has
// been dereferenced in this block.
PointerType *PTy = dyn_cast<PointerType>(Val->getType());
if (PTy && BB->getTerminator() == BBI &&
isNonNullAtEndOfBlock(Val, BB))
BBLV = ValueLatticeElement::getNot(ConstantPointerNull::get(PTy));
}
}
static ConstantRange toConstantRange(const ValueLatticeElement &Val,
Type *Ty, bool UndefAllowed = false) {
assert(Ty->isIntOrIntVectorTy() && "Must be integer type");
if (Val.isConstantRange(UndefAllowed))
return Val.getConstantRange();
unsigned BW = Ty->getScalarSizeInBits();
if (Val.isUnknown())
return ConstantRange::getEmpty(BW);
return ConstantRange::getFull(BW);
}
std::optional<ValueLatticeElement>
LazyValueInfoImpl::solveBlockValueSelect(SelectInst *SI, BasicBlock *BB) {
// Recurse on our inputs if needed
std::optional<ValueLatticeElement> OptTrueVal =
getBlockValue(SI->getTrueValue(), BB, SI);
if (!OptTrueVal)
return std::nullopt;
ValueLatticeElement &TrueVal = *OptTrueVal;
std::optional<ValueLatticeElement> OptFalseVal =
getBlockValue(SI->getFalseValue(), BB, SI);
if (!OptFalseVal)
return std::nullopt;
ValueLatticeElement &FalseVal = *OptFalseVal;
if (TrueVal.isConstantRange() || FalseVal.isConstantRange()) {
const ConstantRange &TrueCR = toConstantRange(TrueVal, SI->getType());
const ConstantRange &FalseCR = toConstantRange(FalseVal, SI->getType());
Value *LHS = nullptr;
Value *RHS = nullptr;
SelectPatternResult SPR = matchSelectPattern(SI, LHS, RHS);
// Is this a min specifically of our two inputs? (Avoid the risk of
// ValueTracking getting smarter looking back past our immediate inputs.)
if (SelectPatternResult::isMinOrMax(SPR.Flavor) &&
((LHS == SI->getTrueValue() && RHS == SI->getFalseValue()) ||
(RHS == SI->getTrueValue() && LHS == SI->getFalseValue()))) {
ConstantRange ResultCR = [&]() {
switch (SPR.Flavor) {
default:
llvm_unreachable("unexpected minmax type!");
case SPF_SMIN: /// Signed minimum
return TrueCR.smin(FalseCR);
case SPF_UMIN: /// Unsigned minimum
return TrueCR.umin(FalseCR);
case SPF_SMAX: /// Signed maximum
return TrueCR.smax(FalseCR);
case SPF_UMAX: /// Unsigned maximum
return TrueCR.umax(FalseCR);
};
}();
return ValueLatticeElement::getRange(
ResultCR, TrueVal.isConstantRangeIncludingUndef() ||
FalseVal.isConstantRangeIncludingUndef());
}
if (SPR.Flavor == SPF_ABS) {
if (LHS == SI->getTrueValue())
return ValueLatticeElement::getRange(
TrueCR.abs(), TrueVal.isConstantRangeIncludingUndef());
if (LHS == SI->getFalseValue())
return ValueLatticeElement::getRange(
FalseCR.abs(), FalseVal.isConstantRangeIncludingUndef());
}
if (SPR.Flavor == SPF_NABS) {
ConstantRange Zero(APInt::getZero(TrueCR.getBitWidth()));
if (LHS == SI->getTrueValue())
return ValueLatticeElement::getRange(
Zero.sub(TrueCR.abs()), FalseVal.isConstantRangeIncludingUndef());
if (LHS == SI->getFalseValue())
return ValueLatticeElement::getRange(
Zero.sub(FalseCR.abs()), FalseVal.isConstantRangeIncludingUndef());
}
}
// Can we constrain the facts about the true and false values by using the
// condition itself? This shows up with idioms like e.g. select(a > 5, a, 5).
// TODO: We could potentially refine an overdefined true value above.
Value *Cond = SI->getCondition();
// If the value is undef, a different value may be chosen in
// the select condition.
if (isGuaranteedNotToBeUndef(Cond, AC)) {
TrueVal =
intersect(TrueVal, *getValueFromCondition(SI->getTrueValue(), Cond,
/*IsTrueDest*/ true,
/*UseBlockValue*/ false));
FalseVal =
intersect(FalseVal, *getValueFromCondition(SI->getFalseValue(), Cond,
/*IsTrueDest*/ false,
/*UseBlockValue*/ false));
}
ValueLatticeElement Result = TrueVal;
Result.mergeIn(FalseVal);
return Result;
}
std::optional<ConstantRange>
LazyValueInfoImpl::getRangeFor(Value *V, Instruction *CxtI, BasicBlock *BB) {
std::optional<ValueLatticeElement> OptVal = getBlockValue(V, BB, CxtI);
if (!OptVal)
return std::nullopt;
return toConstantRange(*OptVal, V->getType());
}
std::optional<ValueLatticeElement>
LazyValueInfoImpl::solveBlockValueCast(CastInst *CI, BasicBlock *BB) {
// Filter out casts we don't know how to reason about before attempting to
// recurse on our operand. This can cut a long search short if we know we're
// not going to be able to get any useful information anways.
switch (CI->getOpcode()) {
case Instruction::Trunc:
case Instruction::SExt:
case Instruction::ZExt:
break;
default:
// Unhandled instructions are overdefined.
LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()
<< "' - overdefined (unknown cast).\n");
return ValueLatticeElement::getOverdefined();
}
// Figure out the range of the LHS. If that fails, we still apply the
// transfer rule on the full set since we may be able to locally infer
// interesting facts.
std::optional<ConstantRange> LHSRes = getRangeFor(CI->getOperand(0), CI, BB);
if (!LHSRes)
// More work to do before applying this transfer rule.
return std::nullopt;
const ConstantRange &LHSRange = *LHSRes;
const unsigned ResultBitWidth = CI->getType()->getIntegerBitWidth();
// NOTE: We're currently limited by the set of operations that ConstantRange
// can evaluate symbolically. Enhancing that set will allows us to analyze
// more definitions.
return ValueLatticeElement::getRange(LHSRange.castOp(CI->getOpcode(),
ResultBitWidth));
}
std::optional<ValueLatticeElement>
LazyValueInfoImpl::solveBlockValueBinaryOpImpl(
Instruction *I, BasicBlock *BB,
std::function<ConstantRange(const ConstantRange &, const ConstantRange &)>
OpFn) {
// Figure out the ranges of the operands. If that fails, use a
// conservative range, but apply the transfer rule anyways. This
// lets us pick up facts from expressions like "and i32 (call i32
// @foo()), 32"
std::optional<ConstantRange> LHSRes = getRangeFor(I->getOperand(0), I, BB);
if (!LHSRes)
return std::nullopt;
std::optional<ConstantRange> RHSRes = getRangeFor(I->getOperand(1), I, BB);
if (!RHSRes)
return std::nullopt;
const ConstantRange &LHSRange = *LHSRes;
const ConstantRange &RHSRange = *RHSRes;
return ValueLatticeElement::getRange(OpFn(LHSRange, RHSRange));
}
std::optional<ValueLatticeElement>
LazyValueInfoImpl::solveBlockValueBinaryOp(BinaryOperator *BO, BasicBlock *BB) {
assert(BO->getOperand(0)->getType()->isSized() &&
"all operands to binary operators are sized");
if (auto *OBO = dyn_cast<OverflowingBinaryOperator>(BO)) {
unsigned NoWrapKind = 0;
if (OBO->hasNoUnsignedWrap())
NoWrapKind |= OverflowingBinaryOperator::NoUnsignedWrap;
if (OBO->hasNoSignedWrap())
NoWrapKind |= OverflowingBinaryOperator::NoSignedWrap;
return solveBlockValueBinaryOpImpl(
BO, BB,
[BO, NoWrapKind](const ConstantRange &CR1, const ConstantRange &CR2) {
return CR1.overflowingBinaryOp(BO->getOpcode(), CR2, NoWrapKind);
});
}
return solveBlockValueBinaryOpImpl(
BO, BB, [BO](const ConstantRange &CR1, const ConstantRange &CR2) {
return CR1.binaryOp(BO->getOpcode(), CR2);
});
}
std::optional<ValueLatticeElement>
LazyValueInfoImpl::solveBlockValueOverflowIntrinsic(WithOverflowInst *WO,
BasicBlock *BB) {
return solveBlockValueBinaryOpImpl(
WO, BB, [WO](const ConstantRange &CR1, const ConstantRange &CR2) {
return CR1.binaryOp(WO->getBinaryOp(), CR2);
});
}
std::optional<ValueLatticeElement>
LazyValueInfoImpl::solveBlockValueIntrinsic(IntrinsicInst *II, BasicBlock *BB) {
ValueLatticeElement MetadataVal = getFromRangeMetadata(II);
if (!ConstantRange::isIntrinsicSupported(II->getIntrinsicID())) {
LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()
<< "' - unknown intrinsic.\n");
return MetadataVal;
}
SmallVector<ConstantRange, 2> OpRanges;
for (Value *Op : II->args()) {
std::optional<ConstantRange> Range = getRangeFor(Op, II, BB);
if (!Range)
return std::nullopt;
OpRanges.push_back(*Range);
}
return intersect(ValueLatticeElement::getRange(ConstantRange::intrinsic(
II->getIntrinsicID(), OpRanges)),
MetadataVal);
}
std::optional<ValueLatticeElement>
LazyValueInfoImpl::solveBlockValueExtractValue(ExtractValueInst *EVI,
BasicBlock *BB) {
if (auto *WO = dyn_cast<WithOverflowInst>(EVI->getAggregateOperand()))
if (EVI->getNumIndices() == 1 && *EVI->idx_begin() == 0)
return solveBlockValueOverflowIntrinsic(WO, BB);
// Handle extractvalue of insertvalue to allow further simplification
// based on replaced with.overflow intrinsics.
if (Value *V = simplifyExtractValueInst(
EVI->getAggregateOperand(), EVI->getIndices(),
EVI->getModule()->getDataLayout()))
return getBlockValue(V, BB, EVI);
LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()
<< "' - overdefined (unknown extractvalue).\n");
return ValueLatticeElement::getOverdefined();
}
static bool matchICmpOperand(APInt &Offset, Value *LHS, Value *Val,
ICmpInst::Predicate Pred) {
if (LHS == Val)
return true;
// Handle range checking idiom produced by InstCombine. We will subtract the
// offset from the allowed range for RHS in this case.
const APInt *C;
if (match(LHS, m_Add(m_Specific(Val), m_APInt(C)))) {
Offset = *C;
return true;
}
// Handle the symmetric case. This appears in saturation patterns like
// (x == 16) ? 16 : (x + 1).
if (match(Val, m_Add(m_Specific(LHS), m_APInt(C)))) {
Offset = -*C;
return true;
}
// If (x | y) < C, then (x < C) && (y < C).
if (match(LHS, m_c_Or(m_Specific(Val), m_Value())) &&
(Pred == ICmpInst::ICMP_ULT || Pred == ICmpInst::ICMP_ULE))
return true;
// If (x & y) > C, then (x > C) && (y > C).
if (match(LHS, m_c_And(m_Specific(Val), m_Value())) &&
(Pred == ICmpInst::ICMP_UGT || Pred == ICmpInst::ICMP_UGE))
return true;
return false;
}
/// Get value range for a "(Val + Offset) Pred RHS" condition.
std::optional<ValueLatticeElement>
LazyValueInfoImpl::getValueFromSimpleICmpCondition(CmpInst::Predicate Pred,
Value *RHS,
const APInt &Offset,
Instruction *CxtI,
bool UseBlockValue) {
ConstantRange RHSRange(RHS->getType()->getIntegerBitWidth(),
/*isFullSet=*/true);
if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) {
RHSRange = ConstantRange(CI->getValue());
} else if (UseBlockValue) {
std::optional<ValueLatticeElement> R =
getBlockValue(RHS, CxtI->getParent(), CxtI);
if (!R)
return std::nullopt;
RHSRange = toConstantRange(*R, RHS->getType());
} else if (Instruction *I = dyn_cast<Instruction>(RHS)) {
if (auto *Ranges = I->getMetadata(LLVMContext::MD_range))
RHSRange = getConstantRangeFromMetadata(*Ranges);
}
ConstantRange TrueValues =
ConstantRange::makeAllowedICmpRegion(Pred, RHSRange);
return ValueLatticeElement::getRange(TrueValues.subtract(Offset));
}
static std::optional<ConstantRange>
getRangeViaSLT(CmpInst::Predicate Pred, APInt RHS,
function_ref<std::optional<ConstantRange>(const APInt &)> Fn) {
bool Invert = false;
if (Pred == ICmpInst::ICMP_SGT || Pred == ICmpInst::ICMP_SGE) {
Pred = ICmpInst::getInversePredicate(Pred);
Invert = true;
}
if (Pred == ICmpInst::ICMP_SLE) {
Pred = ICmpInst::ICMP_SLT;
if (RHS.isMaxSignedValue())
return std::nullopt; // Could also return full/empty here, if we wanted.
++RHS;
}
assert(Pred == ICmpInst::ICMP_SLT && "Must be signed predicate");
if (auto CR = Fn(RHS))
return Invert ? CR->inverse() : CR;
return std::nullopt;
}
std::optional<ValueLatticeElement> LazyValueInfoImpl::getValueFromICmpCondition(
Value *Val, ICmpInst *ICI, bool isTrueDest, bool UseBlockValue) {
Value *LHS = ICI->getOperand(0);
Value *RHS = ICI->getOperand(1);
// Get the predicate that must hold along the considered edge.
CmpInst::Predicate EdgePred =
isTrueDest ? ICI->getPredicate() : ICI->getInversePredicate();
if (isa<Constant>(RHS)) {
if (ICI->isEquality() && LHS == Val) {
if (EdgePred == ICmpInst::ICMP_EQ)
return ValueLatticeElement::get(cast<Constant>(RHS));
else if (!isa<UndefValue>(RHS))
return ValueLatticeElement::getNot(cast<Constant>(RHS));
}
}
Type *Ty = Val->getType();
if (!Ty->isIntegerTy())
return ValueLatticeElement::getOverdefined();
unsigned BitWidth = Ty->getScalarSizeInBits();
APInt Offset(BitWidth, 0);
if (matchICmpOperand(Offset, LHS, Val, EdgePred))
return getValueFromSimpleICmpCondition(EdgePred, RHS, Offset, ICI,
UseBlockValue);
CmpInst::Predicate SwappedPred = CmpInst::getSwappedPredicate(EdgePred);
if (matchICmpOperand(Offset, RHS, Val, SwappedPred))
return getValueFromSimpleICmpCondition(SwappedPred, LHS, Offset, ICI,
UseBlockValue);
const APInt *Mask, *C;
if (match(LHS, m_And(m_Specific(Val), m_APInt(Mask))) &&
match(RHS, m_APInt(C))) {
// If (Val & Mask) == C then all the masked bits are known and we can
// compute a value range based on that.
if (EdgePred == ICmpInst::ICMP_EQ) {
KnownBits Known;
Known.Zero = ~*C & *Mask;
Known.One = *C & *Mask;
return ValueLatticeElement::getRange(
ConstantRange::fromKnownBits(Known, /*IsSigned*/ false));
}
// If (Val & Mask) != 0 then the value must be larger than the lowest set
// bit of Mask.
if (EdgePred == ICmpInst::ICMP_NE && !Mask->isZero() && C->isZero()) {
return ValueLatticeElement::getRange(ConstantRange::getNonEmpty(
APInt::getOneBitSet(BitWidth, Mask->countr_zero()),
APInt::getZero(BitWidth)));
}
}
// If (X urem Modulus) >= C, then X >= C.
// If trunc X >= C, then X >= C.
// TODO: An upper bound could be computed as well.
if (match(LHS, m_CombineOr(m_URem(m_Specific(Val), m_Value()),
m_Trunc(m_Specific(Val)))) &&
match(RHS, m_APInt(C))) {
// Use the icmp region so we don't have to deal with different predicates.
ConstantRange CR = ConstantRange::makeExactICmpRegion(EdgePred, *C);
if (!CR.isEmptySet())
return ValueLatticeElement::getRange(ConstantRange::getNonEmpty(
CR.getUnsignedMin().zext(BitWidth), APInt(BitWidth, 0)));
}
// Recognize:
// icmp slt (ashr X, ShAmtC), C --> icmp slt X, C << ShAmtC
// Preconditions: (C << ShAmtC) >> ShAmtC == C
const APInt *ShAmtC;
if (CmpInst::isSigned(EdgePred) &&
match(LHS, m_AShr(m_Specific(Val), m_APInt(ShAmtC))) &&
match(RHS, m_APInt(C))) {
auto CR = getRangeViaSLT(
EdgePred, *C, [&](const APInt &RHS) -> std::optional<ConstantRange> {
APInt New = RHS << *ShAmtC;
if ((New.ashr(*ShAmtC)) != RHS)
return std::nullopt;
return ConstantRange::getNonEmpty(
APInt::getSignedMinValue(New.getBitWidth()), New);
});
if (CR)
return ValueLatticeElement::getRange(*CR);
}
return ValueLatticeElement::getOverdefined();
}
// Handle conditions of the form
// extractvalue(op.with.overflow(%x, C), 1).
static ValueLatticeElement getValueFromOverflowCondition(
Value *Val, WithOverflowInst *WO, bool IsTrueDest) {
// TODO: This only works with a constant RHS for now. We could also compute
// the range of the RHS, but this doesn't fit into the current structure of
// the edge value calculation.
const APInt *C;
if (WO->getLHS() != Val || !match(WO->getRHS(), m_APInt(C)))
return ValueLatticeElement::getOverdefined();
// Calculate the possible values of %x for which no overflow occurs.
ConstantRange NWR = ConstantRange::makeExactNoWrapRegion(
WO->getBinaryOp(), *C, WO->getNoWrapKind());
// If overflow is false, %x is constrained to NWR. If overflow is true, %x is
// constrained to it's inverse (all values that might cause overflow).
if (IsTrueDest)
NWR = NWR.inverse();
return ValueLatticeElement::getRange(NWR);
}
std::optional<ValueLatticeElement>
LazyValueInfoImpl::getValueFromCondition(Value *Val, Value *Cond,
bool IsTrueDest, bool UseBlockValue,
unsigned Depth) {
if (ICmpInst *ICI = dyn_cast<ICmpInst>(Cond))
return getValueFromICmpCondition(Val, ICI, IsTrueDest, UseBlockValue);
if (auto *EVI = dyn_cast<ExtractValueInst>(Cond))
if (auto *WO = dyn_cast<WithOverflowInst>(EVI->getAggregateOperand()))
if (EVI->getNumIndices() == 1 && *EVI->idx_begin() == 1)
return getValueFromOverflowCondition(Val, WO, IsTrueDest);
if (++Depth == MaxAnalysisRecursionDepth)
return ValueLatticeElement::getOverdefined();
Value *N;
if (match(Cond, m_Not(m_Value(N))))
return getValueFromCondition(Val, N, !IsTrueDest, UseBlockValue, Depth);
Value *L, *R;
bool IsAnd;
if (match(Cond, m_LogicalAnd(m_Value(L), m_Value(R))))
IsAnd = true;
else if (match(Cond, m_LogicalOr(m_Value(L), m_Value(R))))
IsAnd = false;
else
return ValueLatticeElement::getOverdefined();
std::optional<ValueLatticeElement> LV =
getValueFromCondition(Val, L, IsTrueDest, UseBlockValue, Depth);
if (!LV)
return std::nullopt;
std::optional<ValueLatticeElement> RV =
getValueFromCondition(Val, R, IsTrueDest, UseBlockValue, Depth);
if (!RV)
return std::nullopt;
// if (L && R) -> intersect L and R
// if (!(L || R)) -> intersect !L and !R
// if (L || R) -> union L and R
// if (!(L && R)) -> union !L and !R
if (IsTrueDest ^ IsAnd) {
LV->mergeIn(*RV);
return *LV;
}
return intersect(*LV, *RV);
}
// Return true if Usr has Op as an operand, otherwise false.
static bool usesOperand(User *Usr, Value *Op) {
return is_contained(Usr->operands(), Op);
}
// Return true if the instruction type of Val is supported by
// constantFoldUser(). Currently CastInst, BinaryOperator and FreezeInst only.
// Call this before calling constantFoldUser() to find out if it's even worth
// attempting to call it.
static bool isOperationFoldable(User *Usr) {
return isa<CastInst>(Usr) || isa<BinaryOperator>(Usr) || isa<FreezeInst>(Usr);
}
// Check if Usr can be simplified to an integer constant when the value of one
// of its operands Op is an integer constant OpConstVal. If so, return it as an
// lattice value range with a single element or otherwise return an overdefined
// lattice value.
static ValueLatticeElement constantFoldUser(User *Usr, Value *Op,
const APInt &OpConstVal,
const DataLayout &DL) {
assert(isOperationFoldable(Usr) && "Precondition");
Constant* OpConst = Constant::getIntegerValue(Op->getType(), OpConstVal);
// Check if Usr can be simplified to a constant.
if (auto *CI = dyn_cast<CastInst>(Usr)) {
assert(CI->getOperand(0) == Op && "Operand 0 isn't Op");
if (auto *C = dyn_cast_or_null<ConstantInt>(
simplifyCastInst(CI->getOpcode(), OpConst,
CI->getDestTy(), DL))) {
return ValueLatticeElement::getRange(ConstantRange(C->getValue()));
}
} else if (auto *BO = dyn_cast<BinaryOperator>(Usr)) {
bool Op0Match = BO->getOperand(0) == Op;
bool Op1Match = BO->getOperand(1) == Op;
assert((Op0Match || Op1Match) &&
"Operand 0 nor Operand 1 isn't a match");
Value *LHS = Op0Match ? OpConst : BO->getOperand(0);
Value *RHS = Op1Match ? OpConst : BO->getOperand(1);
if (auto *C = dyn_cast_or_null<ConstantInt>(
simplifyBinOp(BO->getOpcode(), LHS, RHS, DL))) {
return ValueLatticeElement::getRange(ConstantRange(C->getValue()));
}
} else if (isa<FreezeInst>(Usr)) {
assert(cast<FreezeInst>(Usr)->getOperand(0) == Op && "Operand 0 isn't Op");
return ValueLatticeElement::getRange(ConstantRange(OpConstVal));
}
return ValueLatticeElement::getOverdefined();
}
/// Compute the value of Val on the edge BBFrom -> BBTo.
std::optional<ValueLatticeElement>
LazyValueInfoImpl::getEdgeValueLocal(Value *Val, BasicBlock *BBFrom,
BasicBlock *BBTo, bool UseBlockValue) {
// TODO: Handle more complex conditionals. If (v == 0 || v2 < 1) is false, we
// know that v != 0.
if (BranchInst *BI = dyn_cast<BranchInst>(BBFrom->getTerminator())) {
// If this is a conditional branch and only one successor goes to BBTo, then
// we may be able to infer something from the condition.
if (BI->isConditional() &&
BI->getSuccessor(0) != BI->getSuccessor(1)) {
bool isTrueDest = BI->getSuccessor(0) == BBTo;
assert(BI->getSuccessor(!isTrueDest) == BBTo &&
"BBTo isn't a successor of BBFrom");
Value *Condition = BI->getCondition();
// If V is the condition of the branch itself, then we know exactly what
// it is.
if (Condition == Val)
return ValueLatticeElement::get(ConstantInt::get(
Type::getInt1Ty(Val->getContext()), isTrueDest));
// If the condition of the branch is an equality comparison, we may be
// able to infer the value.
std::optional<ValueLatticeElement> Result =
getValueFromCondition(Val, Condition, isTrueDest, UseBlockValue);
if (!Result)
return std::nullopt;
if (!Result->isOverdefined())
return Result;
if (User *Usr = dyn_cast<User>(Val)) {
assert(Result->isOverdefined() && "Result isn't overdefined");
// Check with isOperationFoldable() first to avoid linearly iterating
// over the operands unnecessarily which can be expensive for
// instructions with many operands.
if (isa<IntegerType>(Usr->getType()) && isOperationFoldable(Usr)) {
const DataLayout &DL = BBTo->getModule()->getDataLayout();
if (usesOperand(Usr, Condition)) {
// If Val has Condition as an operand and Val can be folded into a
// constant with either Condition == true or Condition == false,
// propagate the constant.
// eg.
// ; %Val is true on the edge to %then.
// %Val = and i1 %Condition, true.
// br %Condition, label %then, label %else
APInt ConditionVal(1, isTrueDest ? 1 : 0);
Result = constantFoldUser(Usr, Condition, ConditionVal, DL);
} else {
// If one of Val's operand has an inferred value, we may be able to
// infer the value of Val.
// eg.
// ; %Val is 94 on the edge to %then.
// %Val = add i8 %Op, 1
// %Condition = icmp eq i8 %Op, 93
// br i1 %Condition, label %then, label %else
for (unsigned i = 0; i < Usr->getNumOperands(); ++i) {
Value *Op = Usr->getOperand(i);
ValueLatticeElement OpLatticeVal = *getValueFromCondition(
Op, Condition, isTrueDest, /*UseBlockValue*/ false);
if (std::optional<APInt> OpConst =
OpLatticeVal.asConstantInteger()) {
Result = constantFoldUser(Usr, Op, *OpConst, DL);
break;
}
}
}
}
}
if (!Result->isOverdefined())
return Result;
}
}
// If the edge was formed by a switch on the value, then we may know exactly
// what it is.
if (SwitchInst *SI = dyn_cast<SwitchInst>(BBFrom->getTerminator())) {
Value *Condition = SI->getCondition();
if (!isa<IntegerType>(Val->getType()))
return ValueLatticeElement::getOverdefined();
bool ValUsesConditionAndMayBeFoldable = false;
if (Condition != Val) {
// Check if Val has Condition as an operand.
if (User *Usr = dyn_cast<User>(Val))
ValUsesConditionAndMayBeFoldable = isOperationFoldable(Usr) &&
usesOperand(Usr, Condition);
if (!ValUsesConditionAndMayBeFoldable)
return ValueLatticeElement::getOverdefined();
}
assert((Condition == Val || ValUsesConditionAndMayBeFoldable) &&
"Condition != Val nor Val doesn't use Condition");
bool DefaultCase = SI->getDefaultDest() == BBTo;
unsigned BitWidth = Val->getType()->getIntegerBitWidth();
ConstantRange EdgesVals(BitWidth, DefaultCase/*isFullSet*/);
for (auto Case : SI->cases()) {
APInt CaseValue = Case.getCaseValue()->getValue();
ConstantRange EdgeVal(CaseValue);
if (ValUsesConditionAndMayBeFoldable) {
User *Usr = cast<User>(Val);
const DataLayout &DL = BBTo->getModule()->getDataLayout();
ValueLatticeElement EdgeLatticeVal =
constantFoldUser(Usr, Condition, CaseValue, DL);
if (EdgeLatticeVal.isOverdefined())
return ValueLatticeElement::getOverdefined();
EdgeVal = EdgeLatticeVal.getConstantRange();
}
if (DefaultCase) {
// It is possible that the default destination is the destination of
// some cases. We cannot perform difference for those cases.
// We know Condition != CaseValue in BBTo. In some cases we can use
// this to infer Val == f(Condition) is != f(CaseValue). For now, we
// only do this when f is identity (i.e. Val == Condition), but we
// should be able to do this for any injective f.
if (Case.getCaseSuccessor() != BBTo && Condition == Val)
EdgesVals = EdgesVals.difference(EdgeVal);
} else if (Case.getCaseSuccessor() == BBTo)
EdgesVals = EdgesVals.unionWith(EdgeVal);
}
return ValueLatticeElement::getRange(std::move(EdgesVals));
}
return ValueLatticeElement::getOverdefined();
}
/// Compute the value of Val on the edge BBFrom -> BBTo or the value at
/// the basic block if the edge does not constrain Val.
std::optional<ValueLatticeElement>
LazyValueInfoImpl::getEdgeValue(Value *Val, BasicBlock *BBFrom,
BasicBlock *BBTo, Instruction *CxtI) {
// If already a constant, there is nothing to compute.
if (Constant *VC = dyn_cast<Constant>(Val))
return ValueLatticeElement::get(VC);
std::optional<ValueLatticeElement> LocalResult =
getEdgeValueLocal(Val, BBFrom, BBTo, /*UseBlockValue*/ true);
if (!LocalResult)
return std::nullopt;
if (hasSingleValue(*LocalResult))
// Can't get any more precise here
return LocalResult;
std::optional<ValueLatticeElement> OptInBlock =
getBlockValue(Val, BBFrom, BBFrom->getTerminator());
if (!OptInBlock)
return std::nullopt;
ValueLatticeElement &InBlock = *OptInBlock;
// We can use the context instruction (generically the ultimate instruction
// the calling pass is trying to simplify) here, even though the result of
// this function is generally cached when called from the solve* functions
// (and that cached result might be used with queries using a different
// context instruction), because when this function is called from the solve*
// functions, the context instruction is not provided. When called from
// LazyValueInfoImpl::getValueOnEdge, the context instruction is provided,
// but then the result is not cached.
intersectAssumeOrGuardBlockValueConstantRange(Val, InBlock, CxtI);
return intersect(*LocalResult, InBlock);
}
ValueLatticeElement LazyValueInfoImpl::getValueInBlock(Value *V, BasicBlock *BB,
Instruction *CxtI) {
LLVM_DEBUG(dbgs() << "LVI Getting block end value " << *V << " at '"
<< BB->getName() << "'\n");
assert(BlockValueStack.empty() && BlockValueSet.empty());
std::optional<ValueLatticeElement> OptResult = getBlockValue(V, BB, CxtI);
if (!OptResult) {
solve();
OptResult = getBlockValue(V, BB, CxtI);
assert(OptResult && "Value not available after solving");
}
ValueLatticeElement Result = *OptResult;
LLVM_DEBUG(dbgs() << " Result = " << Result << "\n");
return Result;
}
ValueLatticeElement LazyValueInfoImpl::getValueAt(Value *V, Instruction *CxtI) {
LLVM_DEBUG(dbgs() << "LVI Getting value " << *V << " at '" << CxtI->getName()
<< "'\n");
if (auto *C = dyn_cast<Constant>(V))
return ValueLatticeElement::get(C);
ValueLatticeElement Result = ValueLatticeElement::getOverdefined();
if (auto *I = dyn_cast<Instruction>(V))
Result = getFromRangeMetadata(I);
intersectAssumeOrGuardBlockValueConstantRange(V, Result, CxtI);
LLVM_DEBUG(dbgs() << " Result = " << Result << "\n");
return Result;
}
ValueLatticeElement LazyValueInfoImpl::
getValueOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB,
Instruction *CxtI) {
LLVM_DEBUG(dbgs() << "LVI Getting edge value " << *V << " from '"
<< FromBB->getName() << "' to '" << ToBB->getName()
<< "'\n");
std::optional<ValueLatticeElement> Result =
getEdgeValue(V, FromBB, ToBB, CxtI);
while (!Result) {
// As the worklist only explicitly tracks block values (but not edge values)
// we may have to call solve() multiple times, as the edge value calculation
// may request additional block values.
solve();
Result = getEdgeValue(V, FromBB, ToBB, CxtI);
}
LLVM_DEBUG(dbgs() << " Result = " << *Result << "\n");
return *Result;
}
ValueLatticeElement LazyValueInfoImpl::getValueAtUse(const Use &U) {
Value *V = U.get();
auto *CxtI = cast<Instruction>(U.getUser());
ValueLatticeElement VL = getValueInBlock(V, CxtI->getParent(), CxtI);
// Check whether the only (possibly transitive) use of the value is in a
// position where V can be constrained by a select or branch condition.
const Use *CurrU = &U;
// TODO: Increase limit?
const unsigned MaxUsesToInspect = 3;
for (unsigned I = 0; I < MaxUsesToInspect; ++I) {
std::optional<ValueLatticeElement> CondVal;
auto *CurrI = cast<Instruction>(CurrU->getUser());
if (auto *SI = dyn_cast<SelectInst>(CurrI)) {
// If the value is undef, a different value may be chosen in
// the select condition and at use.
if (!isGuaranteedNotToBeUndef(SI->getCondition(), AC))
break;
if (CurrU->getOperandNo() == 1)
CondVal =
*getValueFromCondition(V, SI->getCondition(), /*IsTrueDest*/ true,
/*UseBlockValue*/ false);
else if (CurrU->getOperandNo() == 2)
CondVal =
*getValueFromCondition(V, SI->getCondition(), /*IsTrueDest*/ false,
/*UseBlockValue*/ false);
} else if (auto *PHI = dyn_cast<PHINode>(CurrI)) {
// TODO: Use non-local query?
CondVal = *getEdgeValueLocal(V, PHI->getIncomingBlock(*CurrU),
PHI->getParent(), /*UseBlockValue*/ false);
}
if (CondVal)
VL = intersect(VL, *CondVal);
// Only follow one-use chain, to allow direct intersection of conditions.
// If there are multiple uses, we would have to intersect with the union of
// all conditions at different uses.
// Stop walking if we hit a non-speculatable instruction. Even if the
// result is only used under a specific condition, executing the
// instruction itself may cause side effects or UB already.
// This also disallows looking through phi nodes: If the phi node is part
// of a cycle, we might end up reasoning about values from different cycle
// iterations (PR60629).
if (!CurrI->hasOneUse() || !isSafeToSpeculativelyExecute(CurrI))
break;
CurrU = &*CurrI->use_begin();
}
return VL;
}
void LazyValueInfoImpl::threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc,
BasicBlock *NewSucc) {
TheCache.threadEdgeImpl(OldSucc, NewSucc);
}
//===----------------------------------------------------------------------===//
// LazyValueInfo Impl
//===----------------------------------------------------------------------===//
bool LazyValueInfoWrapperPass::runOnFunction(Function &F) {
Info.AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
if (auto *Impl = Info.getImpl())
Impl->clear();
// Fully lazy.
return false;
}
void LazyValueInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesAll();
AU.addRequired<AssumptionCacheTracker>();
AU.addRequired<TargetLibraryInfoWrapperPass>();
}
LazyValueInfo &LazyValueInfoWrapperPass::getLVI() { return Info; }
/// This lazily constructs the LazyValueInfoImpl.
LazyValueInfoImpl &LazyValueInfo::getOrCreateImpl(const Module *M) {
if (!PImpl) {
assert(M && "getCache() called with a null Module");
const DataLayout &DL = M->getDataLayout();
Function *GuardDecl =
M->getFunction(Intrinsic::getName(Intrinsic::experimental_guard));
PImpl = new LazyValueInfoImpl(AC, DL, GuardDecl);
}
return *static_cast<LazyValueInfoImpl *>(PImpl);
}
LazyValueInfoImpl *LazyValueInfo::getImpl() {
if (!PImpl)
return nullptr;
return static_cast<LazyValueInfoImpl *>(PImpl);
}
LazyValueInfo::~LazyValueInfo() { releaseMemory(); }
void LazyValueInfo::releaseMemory() {
// If the cache was allocated, free it.
if (auto *Impl = getImpl()) {
delete &*Impl;
PImpl = nullptr;
}
}
bool LazyValueInfo::invalidate(Function &F, const PreservedAnalyses &PA,
FunctionAnalysisManager::Invalidator &Inv) {
// We need to invalidate if we have either failed to preserve this analyses
// result directly or if any of its dependencies have been invalidated.
auto PAC = PA.getChecker<LazyValueAnalysis>();
if (!(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>()))
return true;
return false;
}
void LazyValueInfoWrapperPass::releaseMemory() { Info.releaseMemory(); }
LazyValueInfo LazyValueAnalysis::run(Function &F,
FunctionAnalysisManager &FAM) {
auto &AC = FAM.getResult<AssumptionAnalysis>(F);
return LazyValueInfo(&AC, &F.getParent()->getDataLayout());
}
/// Returns true if we can statically tell that this value will never be a
/// "useful" constant. In practice, this means we've got something like an
/// alloca or a malloc call for which a comparison against a constant can
/// only be guarding dead code. Note that we are potentially giving up some
/// precision in dead code (a constant result) in favour of avoiding a
/// expensive search for a easily answered common query.
static bool isKnownNonConstant(Value *V) {
V = V->stripPointerCasts();
// The return val of alloc cannot be a Constant.
if (isa<AllocaInst>(V))
return true;
return false;
}
Constant *LazyValueInfo::getConstant(Value *V, Instruction *CxtI) {
// Bail out early if V is known not to be a Constant.
if (isKnownNonConstant(V))
return nullptr;
BasicBlock *BB = CxtI->getParent();
ValueLatticeElement Result =
getOrCreateImpl(BB->getModule()).getValueInBlock(V, BB, CxtI);
if (Result.isConstant())
return Result.getConstant();
if (Result.isConstantRange()) {
const ConstantRange &CR = Result.getConstantRange();
if (const APInt *SingleVal = CR.getSingleElement())
return ConstantInt::get(V->getContext(), *SingleVal);
}
return nullptr;
}
ConstantRange LazyValueInfo::getConstantRange(Value *V, Instruction *CxtI,
bool UndefAllowed) {
assert(V->getType()->isIntegerTy());
BasicBlock *BB = CxtI->getParent();
ValueLatticeElement Result =
getOrCreateImpl(BB->getModule()).getValueInBlock(V, BB, CxtI);
return toConstantRange(Result, V->getType(), UndefAllowed);
}
ConstantRange LazyValueInfo::getConstantRangeAtUse(const Use &U,
bool UndefAllowed) {
auto *Inst = cast<Instruction>(U.getUser());
ValueLatticeElement Result =
getOrCreateImpl(Inst->getModule()).getValueAtUse(U);
return toConstantRange(Result, U->getType(), UndefAllowed);
}
/// Determine whether the specified value is known to be a
/// constant on the specified edge. Return null if not.
Constant *LazyValueInfo::getConstantOnEdge(Value *V, BasicBlock *FromBB,
BasicBlock *ToBB,
Instruction *CxtI) {
Module *M = FromBB->getModule();
ValueLatticeElement Result =
getOrCreateImpl(M).getValueOnEdge(V, FromBB, ToBB, CxtI);
if (Result.isConstant())
return Result.getConstant();
if (Result.isConstantRange()) {
const ConstantRange &CR = Result.getConstantRange();
if (const APInt *SingleVal = CR.getSingleElement())
return ConstantInt::get(V->getContext(), *SingleVal);
}
return nullptr;
}
ConstantRange LazyValueInfo::getConstantRangeOnEdge(Value *V,
BasicBlock *FromBB,
BasicBlock *ToBB,
Instruction *CxtI) {
Module *M = FromBB->getModule();
ValueLatticeElement Result =
getOrCreateImpl(M).getValueOnEdge(V, FromBB, ToBB, CxtI);
// TODO: Should undef be allowed here?
return toConstantRange(Result, V->getType(), /*UndefAllowed*/ true);
}
static LazyValueInfo::Tristate
getPredicateResult(unsigned Pred, Constant *C, const ValueLatticeElement &Val,
const DataLayout &DL) {
// If we know the value is a constant, evaluate the conditional.
Constant *Res = nullptr;
if (Val.isConstant()) {
Res = ConstantFoldCompareInstOperands(Pred, Val.getConstant(), C, DL);
if (ConstantInt *ResCI = dyn_cast_or_null<ConstantInt>(Res))
return ResCI->isZero() ? LazyValueInfo::False : LazyValueInfo::True;
return LazyValueInfo::Unknown;
}
if (Val.isConstantRange()) {
ConstantInt *CI = dyn_cast<ConstantInt>(C);
if (!CI) return LazyValueInfo::Unknown;
const ConstantRange &CR = Val.getConstantRange();
if (Pred == ICmpInst::ICMP_EQ) {
if (!CR.contains(CI->getValue()))
return LazyValueInfo::False;
if (CR.isSingleElement())
return LazyValueInfo::True;
} else if (Pred == ICmpInst::ICMP_NE) {
if (!CR.contains(CI->getValue()))
return LazyValueInfo::True;
if (CR.isSingleElement())
return LazyValueInfo::False;
} else {
// Handle more complex predicates.
ConstantRange TrueValues = ConstantRange::makeExactICmpRegion(
(ICmpInst::Predicate)Pred, CI->getValue());
if (TrueValues.contains(CR))
return LazyValueInfo::True;
if (TrueValues.inverse().contains(CR))
return LazyValueInfo::False;
}
return LazyValueInfo::Unknown;
}
if (Val.isNotConstant()) {
// If this is an equality comparison, we can try to fold it knowing that
// "V != C1".
if (Pred == ICmpInst::ICMP_EQ) {
// !C1 == C -> false iff C1 == C.
Res = ConstantFoldCompareInstOperands(ICmpInst::ICMP_NE,
Val.getNotConstant(), C, DL);
if (Res && Res->isNullValue())
return LazyValueInfo::False;
} else if (Pred == ICmpInst::ICMP_NE) {
// !C1 != C -> true iff C1 == C.
Res = ConstantFoldCompareInstOperands(ICmpInst::ICMP_NE,
Val.getNotConstant(), C, DL);
if (Res && Res->isNullValue())
return LazyValueInfo::True;
}
return LazyValueInfo::Unknown;
}
return LazyValueInfo::Unknown;
}
/// Determine whether the specified value comparison with a constant is known to
/// be true or false on the specified CFG edge. Pred is a CmpInst predicate.
LazyValueInfo::Tristate
LazyValueInfo::getPredicateOnEdge(unsigned Pred, Value *V, Constant *C,
BasicBlock *FromBB, BasicBlock *ToBB,
Instruction *CxtI) {
Module *M = FromBB->getModule();
ValueLatticeElement Result =
getOrCreateImpl(M).getValueOnEdge(V, FromBB, ToBB, CxtI);
return getPredicateResult(Pred, C, Result, M->getDataLayout());
}
LazyValueInfo::Tristate
LazyValueInfo::getPredicateAt(unsigned Pred, Value *V, Constant *C,
Instruction *CxtI, bool UseBlockValue) {
// Is or is not NonNull are common predicates being queried. If
// isKnownNonZero can tell us the result of the predicate, we can
// return it quickly. But this is only a fastpath, and falling
// through would still be correct.
Module *M = CxtI->getModule();
const DataLayout &DL = M->getDataLayout();
if (V->getType()->isPointerTy() && C->isNullValue() &&
isKnownNonZero(V->stripPointerCastsSameRepresentation(), DL)) {
if (Pred == ICmpInst::ICMP_EQ)
return LazyValueInfo::False;
else if (Pred == ICmpInst::ICMP_NE)
return LazyValueInfo::True;
}
auto &Impl = getOrCreateImpl(M);
ValueLatticeElement Result =
UseBlockValue ? Impl.getValueInBlock(V, CxtI->getParent(), CxtI)
: Impl.getValueAt(V, CxtI);
Tristate Ret = getPredicateResult(Pred, C, Result, DL);
if (Ret != Unknown)
return Ret;
// Note: The following bit of code is somewhat distinct from the rest of LVI;
// LVI as a whole tries to compute a lattice value which is conservatively
// correct at a given location. In this case, we have a predicate which we
// weren't able to prove about the merged result, and we're pushing that
// predicate back along each incoming edge to see if we can prove it
// separately for each input. As a motivating example, consider:
// bb1:
// %v1 = ... ; constantrange<1, 5>
// br label %merge
// bb2:
// %v2 = ... ; constantrange<10, 20>
// br label %merge
// merge:
// %phi = phi [%v1, %v2] ; constantrange<1,20>
// %pred = icmp eq i32 %phi, 8
// We can't tell from the lattice value for '%phi' that '%pred' is false
// along each path, but by checking the predicate over each input separately,
// we can.
// We limit the search to one step backwards from the current BB and value.
// We could consider extending this to search further backwards through the
// CFG and/or value graph, but there are non-obvious compile time vs quality
// tradeoffs.
BasicBlock *BB = CxtI->getParent();
// Function entry or an unreachable block. Bail to avoid confusing
// analysis below.
pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
if (PI == PE)
return Unknown;
// If V is a PHI node in the same block as the context, we need to ask
// questions about the predicate as applied to the incoming value along
// each edge. This is useful for eliminating cases where the predicate is
// known along all incoming edges.
if (auto *PHI = dyn_cast<PHINode>(V))
if (PHI->getParent() == BB) {
Tristate Baseline = Unknown;
for (unsigned i = 0, e = PHI->getNumIncomingValues(); i < e; i++) {
Value *Incoming = PHI->getIncomingValue(i);
BasicBlock *PredBB = PHI->getIncomingBlock(i);
// Note that PredBB may be BB itself.
Tristate Result =
getPredicateOnEdge(Pred, Incoming, C, PredBB, BB, CxtI);
// Keep going as long as we've seen a consistent known result for
// all inputs.
Baseline = (i == 0) ? Result /* First iteration */
: (Baseline == Result ? Baseline
: Unknown); /* All others */
if (Baseline == Unknown)
break;
}
if (Baseline != Unknown)
return Baseline;
}
// For a comparison where the V is outside this block, it's possible
// that we've branched on it before. Look to see if the value is known
// on all incoming edges.
if (!isa<Instruction>(V) || cast<Instruction>(V)->getParent() != BB) {
// For predecessor edge, determine if the comparison is true or false
// on that edge. If they're all true or all false, we can conclude
// the value of the comparison in this block.
Tristate Baseline = getPredicateOnEdge(Pred, V, C, *PI, BB, CxtI);
if (Baseline != Unknown) {
// Check that all remaining incoming values match the first one.
while (++PI != PE) {
Tristate Ret = getPredicateOnEdge(Pred, V, C, *PI, BB, CxtI);
if (Ret != Baseline)
break;
}
// If we terminated early, then one of the values didn't match.
if (PI == PE) {
return Baseline;
}
}
}
return Unknown;
}
LazyValueInfo::Tristate LazyValueInfo::getPredicateAt(unsigned P, Value *LHS,
Value *RHS,
Instruction *CxtI,
bool UseBlockValue) {
CmpInst::Predicate Pred = (CmpInst::Predicate)P;
if (auto *C = dyn_cast<Constant>(RHS))
return getPredicateAt(P, LHS, C, CxtI, UseBlockValue);
if (auto *C = dyn_cast<Constant>(LHS))
return getPredicateAt(CmpInst::getSwappedPredicate(Pred), RHS, C, CxtI,
UseBlockValue);
// Got two non-Constant values. Try to determine the comparison results based
// on the block values of the two operands, e.g. because they have
// non-overlapping ranges.
if (UseBlockValue) {
Module *M = CxtI->getModule();
ValueLatticeElement L =
getOrCreateImpl(M).getValueInBlock(LHS, CxtI->getParent(), CxtI);
if (L.isOverdefined())
return LazyValueInfo::Unknown;
ValueLatticeElement R =
getOrCreateImpl(M).getValueInBlock(RHS, CxtI->getParent(), CxtI);
Type *Ty = CmpInst::makeCmpResultType(LHS->getType());
if (Constant *Res = L.getCompare((CmpInst::Predicate)P, Ty, R,
M->getDataLayout())) {
if (Res->isNullValue())
return LazyValueInfo::False;
if (Res->isOneValue())
return LazyValueInfo::True;
}
}
return LazyValueInfo::Unknown;
}
void LazyValueInfo::threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc,
BasicBlock *NewSucc) {
if (auto *Impl = getImpl())
Impl->threadEdge(PredBB, OldSucc, NewSucc);
}
void LazyValueInfo::forgetValue(Value *V) {
if (auto *Impl = getImpl())
Impl->forgetValue(V);
}
void LazyValueInfo::eraseBlock(BasicBlock *BB) {
if (auto *Impl = getImpl())
Impl->eraseBlock(BB);
}
void LazyValueInfo::clear() {
if (auto *Impl = getImpl())
Impl->clear();
}
void LazyValueInfo::printLVI(Function &F, DominatorTree &DTree, raw_ostream &OS) {
if (auto *Impl = getImpl())
Impl->printLVI(F, DTree, OS);
}
// Print the LVI for the function arguments at the start of each basic block.
void LazyValueInfoAnnotatedWriter::emitBasicBlockStartAnnot(
const BasicBlock *BB, formatted_raw_ostream &OS) {
// Find if there are latticevalues defined for arguments of the function.
auto *F = BB->getParent();
for (const auto &Arg : F->args()) {
ValueLatticeElement Result = LVIImpl->getValueInBlock(
const_cast<Argument *>(&Arg), const_cast<BasicBlock *>(BB));
if (Result.isUnknown())
continue;
OS << "; LatticeVal for: '" << Arg << "' is: " << Result << "\n";
}
}
// This function prints the LVI analysis for the instruction I at the beginning
// of various basic blocks. It relies on calculated values that are stored in
// the LazyValueInfoCache, and in the absence of cached values, recalculate the
// LazyValueInfo for `I`, and print that info.
void LazyValueInfoAnnotatedWriter::emitInstructionAnnot(
const Instruction *I, formatted_raw_ostream &OS) {
auto *ParentBB = I->getParent();
SmallPtrSet<const BasicBlock*, 16> BlocksContainingLVI;
// We can generate (solve) LVI values only for blocks that are dominated by
// the I's parent. However, to avoid generating LVI for all dominating blocks,
// that contain redundant/uninteresting information, we print LVI for
// blocks that may use this LVI information (such as immediate successor
// blocks, and blocks that contain uses of `I`).
auto printResult = [&](const BasicBlock *BB) {
if (!BlocksContainingLVI.insert(BB).second)
return;
ValueLatticeElement Result = LVIImpl->getValueInBlock(
const_cast<Instruction *>(I), const_cast<BasicBlock *>(BB));
OS << "; LatticeVal for: '" << *I << "' in BB: '";
BB->printAsOperand(OS, false);
OS << "' is: " << Result << "\n";
};
printResult(ParentBB);
// Print the LVI analysis results for the immediate successor blocks, that
// are dominated by `ParentBB`.
for (const auto *BBSucc : successors(ParentBB))
if (DT.dominates(ParentBB, BBSucc))
printResult(BBSucc);
// Print LVI in blocks where `I` is used.
for (const auto *U : I->users())
if (auto *UseI = dyn_cast<Instruction>(U))
if (!isa<PHINode>(UseI) || DT.dominates(ParentBB, UseI->getParent()))
printResult(UseI->getParent());
}
PreservedAnalyses LazyValueInfoPrinterPass::run(Function &F,
FunctionAnalysisManager &AM) {
OS << "LVI for function '" << F.getName() << "':\n";
auto &LVI = AM.getResult<LazyValueAnalysis>(F);
auto &DTree = AM.getResult<DominatorTreeAnalysis>(F);
LVI.printLVI(F, DTree, OS);
return PreservedAnalyses::all();
}