/// recursive value lookup process.
std::stack<std::pair<BasicBlock*, Value*> > BlockValueStack;
+ /// BlockValueSet - Keeps track of which block-value pairs are in
+ /// BlockValueStack.
+ DenseSet<std::pair<BasicBlock*, Value*> > BlockValueSet;
+
+ /// pushBlockValue - Push BV onto BlockValueStack unless it's already in
+ /// there. Returns true on success.
+ bool pushBlockValue(const std::pair<BasicBlock *, Value *> &BV) {
+ if (BlockValueSet.count(BV))
+ return false; // It's already in the stack.
+
+ BlockValueStack.push(BV);
+ BlockValueSet.insert(BV);
+ return true;
+ }
+
/// A pointer to the cache of @llvm.assume calls.
AssumptionTracker *AT;
/// An optional DL pointer.
DominatorTree *DT;
friend struct LVIValueHandle;
-
- /// OverDefinedCacheUpdater - A helper object that ensures that the
- /// OverDefinedCache is updated whenever solveBlockValue returns.
- struct OverDefinedCacheUpdater {
- LazyValueInfoCache *Parent;
- Value *Val;
- BasicBlock *BB;
- LVILatticeVal &BBLV;
-
- OverDefinedCacheUpdater(Value *V, BasicBlock *B, LVILatticeVal &LV,
- LazyValueInfoCache *P)
- : Parent(P), Val(V), BB(B), BBLV(LV) { }
-
- bool markResult(bool changed) {
- if (changed && BBLV.isOverdefined())
- Parent->OverDefinedCache.insert(std::make_pair(BB, Val));
- return changed;
- }
- };
-
+ void insertResult(Value *Val, BasicBlock *BB, const LVILatticeVal &Result) {
+ SeenBlocks.insert(BB);
+ lookup(Val)[BB] = Result;
+ if (Result.isOverdefined())
+ OverDefinedCache.insert(std::make_pair(BB, Val));
+ }
LVILatticeVal getBlockValue(Value *Val, BasicBlock *BB);
bool getEdgeValue(Value *V, BasicBlock *F, BasicBlock *T,
void LazyValueInfoCache::solve() {
while (!BlockValueStack.empty()) {
std::pair<BasicBlock*, Value*> &e = BlockValueStack.top();
+ assert(BlockValueSet.count(e) && "Stack value should be in BlockValueSet!");
+
if (solveBlockValue(e.second, e.first)) {
- assert(BlockValueStack.top() == e);
+ // 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!");
+
BlockValueStack.pop();
+ BlockValueSet.erase(e);
+ } else {
+ // More work needs to be done before revisiting.
+ assert(BlockValueStack.top() != e && "Stack should have been pushed!");
}
}
}
if (isa<Constant>(Val))
return true;
- ValueCacheEntryTy &Cache = lookup(Val);
- SeenBlocks.insert(BB);
- LVILatticeVal &BBLV = Cache[BB];
-
- // OverDefinedCacheUpdater is a helper object that will update
- // the OverDefinedCache for us when this method exits. Make sure to
- // call markResult on it as we exit, passing a bool to indicate if the
- // cache needs updating, i.e. if we have solved a new value or not.
- OverDefinedCacheUpdater ODCacheUpdater(Val, BB, BBLV, this);
-
- if (!BBLV.isUndefined()) {
- DEBUG(dbgs() << " reuse BB '" << BB->getName() << "' val=" << BBLV <<'\n');
-
- // Since we're reusing a cached value here, we don't need to update the
- // OverDefinedCache. The cache will have been properly updated
- // whenever the cached value was inserted.
- ODCacheUpdater.markResult(false);
+ if (lookup(Val).count(BB)) {
+ // If we have a cached value, use that.
+ DEBUG(dbgs() << " reuse BB '" << BB->getName()
+ << "' val=" << lookup(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
+ // cached value was inserted.
return true;
}
- // Otherwise, this is the first time we're seeing this block. Reset the
- // lattice value to overdefined, so that cycles will terminate and be
- // conservatively correct.
- BBLV.markOverdefined();
+ // Hold off inserting this value into the Cache in case we have to return
+ // false and come back later.
+ LVILatticeVal Res;
Instruction *BBI = dyn_cast<Instruction>(Val);
if (!BBI || BBI->getParent() != BB) {
- return ODCacheUpdater.markResult(solveBlockValueNonLocal(BBLV, Val, BB));
+ if (!solveBlockValueNonLocal(Res, Val, BB))
+ return false;
+ insertResult(Val, BB, Res);
+ return true;
}
if (PHINode *PN = dyn_cast<PHINode>(BBI)) {
- return ODCacheUpdater.markResult(solveBlockValuePHINode(BBLV, PN, BB));
+ if (!solveBlockValuePHINode(Res, PN, BB))
+ return false;
+ insertResult(Val, BB, Res);
+ return true;
}
if (AllocaInst *AI = dyn_cast<AllocaInst>(BBI)) {
- BBLV = LVILatticeVal::getNot(ConstantPointerNull::get(AI->getType()));
- return ODCacheUpdater.markResult(true);
+ Res = LVILatticeVal::getNot(ConstantPointerNull::get(AI->getType()));
+ insertResult(Val, BB, Res);
+ return true;
}
// We can only analyze the definitions of certain classes of instructions
!BBI->getType()->isIntegerTy()) {
DEBUG(dbgs() << " compute BB '" << BB->getName()
<< "' - overdefined because inst def found.\n");
- BBLV.markOverdefined();
- return ODCacheUpdater.markResult(true);
+ Res.markOverdefined();
+ insertResult(Val, BB, Res);
+ return true;
}
// FIXME: We're currently limited to binops with a constant RHS. This should
DEBUG(dbgs() << " compute BB '" << BB->getName()
<< "' - overdefined because inst def found.\n");
- BBLV.markOverdefined();
- return ODCacheUpdater.markResult(true);
+ Res.markOverdefined();
+ insertResult(Val, BB, Res);
+ return true;
}
- return ODCacheUpdater.markResult(solveBlockValueConstantRange(BBLV, BBI, BB));
+ if (!solveBlockValueConstantRange(Res, BBI, BB))
+ return false;
+ insertResult(Val, BB, Res);
+ return true;
}
static bool InstructionDereferencesPointer(Instruction *I, Value *Ptr) {
BasicBlock *BB) {
// Figure out the range of the LHS. If that fails, bail.
if (!hasBlockValue(BBI->getOperand(0), BB)) {
- BlockValueStack.push(std::make_pair(BB, BBI->getOperand(0)));
- return false;
+ if (pushBlockValue(std::make_pair(BB, BBI->getOperand(0))))
+ return false;
+ BBLV.markOverdefined();
+ return true;
}
LVILatticeVal LHSVal = getBlockValue(BBI->getOperand(0), BB);
// LVI better supports recursive values. Even for the single value case, we
// can intersect to detect dead code (an empty range).
if (!hasBlockValue(Val, BBFrom)) {
- BlockValueStack.push(std::make_pair(BBFrom, Val));
- return false;
+ if (pushBlockValue(std::make_pair(BBFrom, Val)))
+ return false;
+ Result.markOverdefined();
+ return true;
}
// Try to intersect ranges of the BB and the constraint on the edge.
}
if (!hasBlockValue(Val, BBFrom)) {
- BlockValueStack.push(std::make_pair(BBFrom, Val));
- return false;
+ if (pushBlockValue(std::make_pair(BBFrom, Val)))
+ return false;
+ Result.markOverdefined();
+ return true;
}
// If we couldn't compute the value on the edge, use the value from the BB.
DEBUG(dbgs() << "LVI Getting block end value " << *V << " at '"
<< BB->getName() << "'\n");
- BlockValueStack.push(std::make_pair(BB, V));
+ assert(BlockValueStack.empty() && BlockValueSet.empty());
+ pushBlockValue(std::make_pair(BB, V));
+
solve();
LVILatticeVal Result = getBlockValue(V, BB);
mergeAssumeBlockValueConstantRange(V, Result, CxtI);
projects / oota-llvm.git / blobdiff