#include "llvm/IR/Dominators.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
+#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/IR/ValueHandle.h"
#include "llvm/Support/Debug.h"
Res.markConstantRange(CR);
return Res;
}
-
+ static LVILatticeVal getOverdefined() {
+ LVILatticeVal Res;
+ Res.markOverdefined();
+ return Res;
+ }
+
bool isUndefined() const { return Tag == undefined; }
bool isConstant() const { return Tag == constant; }
bool isNotConstant() const { return Tag == notconstant; }
/// This is all of the cached block information for exactly one Value*.
/// The entries are sorted by the BasicBlock* of the
/// entries, allowing us to do a lookup with a binary search.
- typedef std::map<AssertingVH<BasicBlock>, LVILatticeVal> ValueCacheEntryTy;
+ /// Over-defined lattice values are recorded in OverDefinedCache to reduce
+ /// memory overhead.
+ typedef SmallDenseMap<AssertingVH<BasicBlock>, LVILatticeVal, 4>
+ ValueCacheEntryTy;
/// This is all of the cached information for all values,
/// mapped from Value* to key information.
std::map<LVIValueHandle, ValueCacheEntryTy> ValueCache;
/// This tracks, on a per-block basis, the set of values that are
- /// over-defined at the end of that block. This is required
- /// for cache updating.
- typedef std::pair<AssertingVH<BasicBlock>, Value*> OverDefinedPairTy;
- DenseSet<OverDefinedPairTy> OverDefinedCache;
+ /// over-defined at the end of that block.
+ typedef DenseMap<AssertingVH<BasicBlock>, SmallPtrSet<Value *, 4>>
+ OverDefinedCacheTy;
+ OverDefinedCacheTy OverDefinedCache;
/// Keep track of all blocks that we have ever seen, so we
/// don't spend time removing unused blocks from our caches.
void insertResult(Value *Val, BasicBlock *BB, const LVILatticeVal &Result) {
SeenBlocks.insert(BB);
- lookup(Val)[BB] = Result;
+
+ // Insert over-defined values into their own cache to reduce memory
+ // overhead.
if (Result.isOverdefined())
- OverDefinedCache.insert(std::make_pair(BB, Val));
+ OverDefinedCache[BB].insert(Val);
+ else
+ lookup(Val)[BB] = Result;
}
LVILatticeVal getBlockValue(Value *Val, BasicBlock *BB);
return ValueCache[LVIValueHandle(V, this)];
}
+ bool isOverdefined(Value *V, BasicBlock *BB) const {
+ auto ODI = OverDefinedCache.find(BB);
+
+ if (ODI == OverDefinedCache.end())
+ return false;
+
+ return ODI->second.count(V);
+ }
+
+ bool hasCachedValueInfo(Value *V, BasicBlock *BB) {
+ if (isOverdefined(V, BB))
+ return true;
+
+ LVIValueHandle ValHandle(V, this);
+ auto I = ValueCache.find(ValHandle);
+ if (I == ValueCache.end())
+ return false;
+
+ return I->second.count(BB);
+ }
+
+ LVILatticeVal getCachedValueInfo(Value *V, BasicBlock *BB) {
+ if (isOverdefined(V, BB))
+ return LVILatticeVal::getOverdefined();
+
+ return lookup(V)[BB];
+ }
+
public:
/// This is the query interface to determine the lattice
/// value for the specified Value* at the end of the specified block.
} // end anonymous namespace
void LVIValueHandle::deleted() {
- typedef std::pair<AssertingVH<BasicBlock>, Value*> OverDefinedPairTy;
-
- SmallVector<OverDefinedPairTy, 4> ToErase;
- for (const OverDefinedPairTy &P : Parent->OverDefinedCache)
- if (P.second == getValPtr())
- ToErase.push_back(P);
- for (const OverDefinedPairTy &P : ToErase)
- Parent->OverDefinedCache.erase(P);
+ SmallVector<AssertingVH<BasicBlock>, 4> ToErase;
+ for (auto &I : Parent->OverDefinedCache) {
+ SmallPtrSetImpl<Value *> &ValueSet = I.second;
+ if (ValueSet.count(getValPtr()))
+ ValueSet.erase(getValPtr());
+ if (ValueSet.empty())
+ ToErase.push_back(I.first);
+ }
+ for (auto &BB : ToErase)
+ Parent->OverDefinedCache.erase(BB);
// This erasure deallocates *this, so it MUST happen after we're done
// using any and all members of *this.
return;
SeenBlocks.erase(I);
- SmallVector<OverDefinedPairTy, 4> ToErase;
- for (const OverDefinedPairTy& P : OverDefinedCache)
- if (P.first == BB)
- ToErase.push_back(P);
- for (const OverDefinedPairTy &P : ToErase)
- OverDefinedCache.erase(P);
+ auto ODI = OverDefinedCache.find(BB);
+ if (ODI != OverDefinedCache.end())
+ OverDefinedCache.erase(ODI);
- for (std::map<LVIValueHandle, ValueCacheEntryTy>::iterator
- I = ValueCache.begin(), E = ValueCache.end(); I != E; ++I)
+ for (auto I = ValueCache.begin(), E = ValueCache.end(); I != E; ++I)
I->second.erase(BB);
}
if (solveBlockValue(e.second, e.first)) {
// The work item was completely processed.
assert(BlockValueStack.top() == e && "Nothing should have been pushed!");
- assert(lookup(e.second).count(e.first) && "Result should be in cache!");
+ assert(hasCachedValueInfo(e.second, e.first) &&
+ "Result should be in cache!");
BlockValueStack.pop();
BlockValueSet.erase(e);
if (isa<Constant>(Val))
return true;
- LVIValueHandle ValHandle(Val, this);
- std::map<LVIValueHandle, ValueCacheEntryTy>::iterator I =
- ValueCache.find(ValHandle);
- if (I == ValueCache.end()) return false;
- return I->second.count(BB);
+ return hasCachedValueInfo(Val, BB);
}
LVILatticeVal LazyValueInfoCache::getBlockValue(Value *Val, BasicBlock *BB) {
return LVILatticeVal::get(VC);
SeenBlocks.insert(BB);
- return lookup(Val)[BB];
+ return getCachedValueInfo(Val, BB);
+}
+
+static LVILatticeVal 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())) {
+ ConstantRange Result = getConstantRangeFromMetadata(*Ranges);
+ return LVILatticeVal::getRange(Result);
+ }
+ break;
+ };
+ // Nothing known - Note that we do not want overdefined here. We may know
+ // something else about the value and not having range metadata shouldn't
+ // cause us to throw away those facts.
+ return LVILatticeVal();
}
bool LazyValueInfoCache::solveBlockValue(Value *Val, BasicBlock *BB) {
if (isa<Constant>(Val))
return true;
- if (lookup(Val).count(BB)) {
+ if (hasCachedValueInfo(Val, BB)) {
// If we have a cached value, use that.
DEBUG(dbgs() << " reuse BB '" << BB->getName()
- << "' val=" << lookup(Val)[BB] << '\n');
+ << "' val=" << getCachedValueInfo(Val, BB) << '\n');
// Since we're reusing a cached value, we don't need to update the
// OverDefinedCache. The cache will have been properly updated whenever the
return true;
}
- if (AllocaInst *AI = dyn_cast<AllocaInst>(BBI)) {
- Res = LVILatticeVal::getNot(ConstantPointerNull::get(AI->getType()));
+ // If this value is a nonnull pointer, record it's range and bailout.
+ PointerType *PT = dyn_cast<PointerType>(BBI->getType());
+ if (PT && isKnownNonNull(BBI)) {
+ Res = LVILatticeVal::getNot(ConstantPointerNull::get(PT));
insertResult(Val, BB, Res);
return true;
}
+ // If this is an instruction which supports range metadata, return the
+ // implied range. TODO: This should be an intersection, not a union.
+ Res.mergeIn(getFromRangeMetadata(BBI), DL);
+
// We can only analyze the definitions of certain classes of instructions
// (integral binops and casts at the moment), so bail if this isn't one.
LVILatticeVal Result;
<< CxtI->getName() << "'\n");
LVILatticeVal Result;
+ if (auto *I = dyn_cast<Instruction>(V))
+ Result = getFromRangeMetadata(I);
mergeAssumeBlockValueConstantRange(V, Result, CxtI);
DEBUG(dbgs() << " Result = " << Result << "\n");
std::vector<BasicBlock*> worklist;
worklist.push_back(OldSucc);
- DenseSet<Value*> ClearSet;
- for (OverDefinedPairTy &P : OverDefinedCache)
- if (P.first == OldSucc)
- ClearSet.insert(P.second);
+ auto I = OverDefinedCache.find(OldSucc);
+ if (I == OverDefinedCache.end())
+ return; // Nothing to process here.
+ SmallVector<Value *, 4> ValsToClear(I->second.begin(), I->second.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
if (ToUpdate == NewSucc) continue;
bool changed = false;
- for (Value *V : ClearSet) {
+ for (Value *V : ValsToClear) {
// If a value was marked overdefined in OldSucc, and is here too...
- DenseSet<OverDefinedPairTy>::iterator OI =
- OverDefinedCache.find(std::make_pair(ToUpdate, V));
- if (OI == OverDefinedCache.end()) continue;
-
- // Remove it from the caches.
- ValueCacheEntryTy &Entry = ValueCache[LVIValueHandle(V, this)];
- ValueCacheEntryTy::iterator CI = Entry.find(ToUpdate);
+ auto OI = OverDefinedCache.find(ToUpdate);
+ if (OI == OverDefinedCache.end())
+ continue;
+ SmallPtrSetImpl<Value *> &ValueSet = OI->second;
+ if (!ValueSet.count(V))
+ continue;
- assert(CI != Entry.end() && "Couldn't find entry to update?");
- Entry.erase(CI);
- OverDefinedCache.erase(OI);
+ ValueSet.erase(V);
+ if (ValueSet.empty())
+ OverDefinedCache.erase(OI);
// If we removed anything, then we potentially need to update
// blocks successors too.
if (Ret != Unknown)
return Ret;
- // TODO: Move this logic inside getValueAt so that it can be cached rather
- // than re-queried on each call. This would also allow us to merge the
- // underlying lattice values to get more information.
+ // 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.
if (CxtI) {
+ 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.
- BasicBlock *BB = CxtI->getParent();
- pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
- if (PI != PE &&
- (!isa<Instruction>(V) ||
- cast<Instruction>(V)->getParent() != BB)) {
+ 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.
projects / oota-llvm.git / blobdiff