#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.
+ /// Over-defined lattice values are recorded in OverDefinedCache to reduce
+ /// memory overhead.
typedef SmallDenseMap<AssertingVH<BasicBlock>, LVILatticeVal, 4>
ValueCacheEntryTy;
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.
+ /// over-defined at the end of that block.
typedef DenseMap<AssertingVH<BasicBlock>, SmallPtrSet<Value *, 4>>
OverDefinedCacheTy;
OverDefinedCacheTy OverDefinedCache;
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[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.
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);
- auto 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 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");
if (!ValueSet.count(V))
continue;
- // Remove it from the caches.
- ValueCacheEntryTy &Entry = ValueCache[LVIValueHandle(V, this)];
- ValueCacheEntryTy::iterator CI = Entry.find(ToUpdate);
-
- assert(CI != Entry.end() && "Couldn't find entry to update?");
- Entry.erase(CI);
ValueSet.erase(V);
if (ValueSet.empty())
OverDefinedCache.erase(OI);
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();
projects / oota-llvm.git / blobdiff