Index: lib/Analysis/LazyValueInfo.cpp =================================================================== --- lib/Analysis/LazyValueInfo.cpp +++ lib/Analysis/LazyValueInfo.cpp @@ -209,28 +209,21 @@ return ODI->second.count(V); } - bool hasCachedValueInfo(Value *V, BasicBlock *BB) const { - if (isOverdefined(V, BB)) + bool getCachedValueInfo(ValueLatticeElement &BBLV, Value *V, + BasicBlock *BB) const { + if (isOverdefined(V, BB)) { + BBLV = ValueLatticeElement::getOverdefined(); return true; + } auto I = ValueCache.find_as(V); if (I == ValueCache.end()) return false; - - return I->second->BlockVals.count(BB); - } - - ValueLatticeElement getCachedValueInfo(Value *V, BasicBlock *BB) const { - if (isOverdefined(V, BB)) - return ValueLatticeElement::getOverdefined(); - - auto I = ValueCache.find_as(V); - if (I == ValueCache.end()) - return ValueLatticeElement(); auto BBI = I->second->BlockVals.find(BB); if (BBI == I->second->BlockVals.end()) - return ValueLatticeElement(); - return BBI->second; + return false; + BBLV = BBI->second; + return true; } /// clear - Empty the cache. @@ -407,10 +400,9 @@ DominatorTree *DT; ///< An optional DT pointer. DominatorTree *DisabledDT; ///< Stores DT if it's disabled. - ValueLatticeElement getBlockValue(Value *Val, BasicBlock *BB); + bool getBlockValue(ValueLatticeElement &Result, Value *Val, BasicBlock *BB); bool getEdgeValue(Value *V, BasicBlock *F, BasicBlock *T, ValueLatticeElement &Result, Instruction *CxtI = nullptr); - bool hasBlockValue(Value *Val, BasicBlock *BB); // 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 @@ -545,12 +537,14 @@ if (solveBlockValue(e.second, e.first)) { // The work item was completely processed. assert(BlockValueStack.back() == e && "Nothing should have been pushed!"); - assert(TheCache.hasCachedValueInfo(e.second, e.first) && +#ifndef NDEBUG + ValueLatticeElement BBLV; + assert(TheCache.getCachedValueInfo(BBLV, e.second, e.first) && "Result should be in cache!"); - LLVM_DEBUG( dbgs() << "POP " << *e.second << " in " << e.first->getName() << " = " - << TheCache.getCachedValueInfo(e.second, e.first) << "\n"); + << BBLV << "\n"); +#endif BlockValueStack.pop_back(); BlockValueSet.erase(e); @@ -561,21 +555,25 @@ } } -bool LazyValueInfoImpl::hasBlockValue(Value *Val, BasicBlock *BB) { +bool LazyValueInfoImpl::getBlockValue(ValueLatticeElement &BBLV, + Value *Val, BasicBlock *BB) { // If already a constant, there is nothing to compute. - if (isa(Val)) + if (Constant *VC = dyn_cast(Val)) { + BBLV = ValueLatticeElement::get(VC); return true; + } - return TheCache.hasCachedValueInfo(Val, BB); -} + if (TheCache.getCachedValueInfo(BBLV, Val, BB)) + return true; -ValueLatticeElement LazyValueInfoImpl::getBlockValue(Value *Val, - BasicBlock *BB) { - // If already a constant, there is nothing to compute. - if (Constant *VC = dyn_cast(Val)) - return ValueLatticeElement::get(VC); + // We have hit a cycle, assume overdefined. + if (!pushBlockValue({ BB, Val })) { + BBLV = ValueLatticeElement::getOverdefined(); + return true; + } - return TheCache.getCachedValueInfo(Val, BB); + // Yet to be resolved. + return false; } static ValueLatticeElement getFromRangeMetadata(Instruction *BBI) { @@ -596,9 +594,12 @@ } bool LazyValueInfoImpl::solveBlockValue(Value *Val, BasicBlock *BB) { +#ifndef NDEBUG + ValueLatticeElement BBLV; assert(!isa(Val) && "Value should not be constant"); - assert(!TheCache.hasCachedValueInfo(Val, BB) && + assert(!TheCache.getCachedValueInfo(BBLV, Val, BB) && "Value should not be in cache"); +#endif // Hold off inserting this value into the Cache in case we have to return // false and come back later. @@ -849,13 +850,10 @@ SelectInst *SI, BasicBlock *BB) { // Recurse on our inputs if needed - if (!hasBlockValue(SI->getTrueValue(), BB)) { - if (pushBlockValue(std::make_pair(BB, SI->getTrueValue()))) - return false; - BBLV = ValueLatticeElement::getOverdefined(); - return true; - } - ValueLatticeElement TrueVal = getBlockValue(SI->getTrueValue(), BB); + ValueLatticeElement TrueVal; + if (!getBlockValue(TrueVal, SI->getTrueValue(), BB)) + return false; + // If we hit overdefined, don't ask more queries. We want to avoid poisoning // extra slots in the table if we can. if (TrueVal.isOverdefined()) { @@ -863,13 +861,10 @@ return true; } - if (!hasBlockValue(SI->getFalseValue(), BB)) { - if (pushBlockValue(std::make_pair(BB, SI->getFalseValue()))) - return false; - BBLV = ValueLatticeElement::getOverdefined(); - return true; - } - ValueLatticeElement FalseVal = getBlockValue(SI->getFalseValue(), BB); + ValueLatticeElement FalseVal; + if (!getBlockValue(FalseVal, SI->getFalseValue(), BB)) + return false; + // If we hit overdefined, don't ask more queries. We want to avoid poisoning // extra slots in the table if we can. if (FalseVal.isOverdefined()) { @@ -990,20 +985,17 @@ Optional LazyValueInfoImpl::getRangeForOperand(unsigned Op, Instruction *I, BasicBlock *BB) { - if (!hasBlockValue(I->getOperand(Op), BB)) - if (pushBlockValue(std::make_pair(BB, I->getOperand(Op)))) - return None; + ValueLatticeElement Val; + if (!getBlockValue(Val, I->getOperand(Op), BB)) + return None; + + intersectAssumeOrGuardBlockValueConstantRange(I->getOperand(Op), Val, I); + if (Val.isConstantRange()) + return Val.getConstantRange(); const unsigned OperandBitWidth = DL.getTypeSizeInBits(I->getOperand(Op)->getType()); - ConstantRange Range = ConstantRange::getFull(OperandBitWidth); - if (hasBlockValue(I->getOperand(Op), BB)) { - ValueLatticeElement Val = getBlockValue(I->getOperand(Op), BB); - intersectAssumeOrGuardBlockValueConstantRange(I->getOperand(Op), Val, I); - if (Val.isConstantRange()) - Range = Val.getConstantRange(); - } - return Range; + return ConstantRange::getFull(OperandBitWidth); } bool LazyValueInfoImpl::solveBlockValueCast(ValueLatticeElement &BBLV, @@ -1164,16 +1156,8 @@ // based on replaced with.overflow intrinsics. if (Value *V = SimplifyExtractValueInst( EVI->getAggregateOperand(), EVI->getIndices(), - EVI->getModule()->getDataLayout())) { - if (!hasBlockValue(V, BB)) { - if (pushBlockValue({ BB, V })) - return false; - BBLV = ValueLatticeElement::getOverdefined(); - return true; - } - BBLV = getBlockValue(V, BB); - return true; - } + EVI->getModule()->getDataLayout())) + return getBlockValue(BBLV, V, BB); LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName() << "' - overdefined (unknown extractvalue).\n"); @@ -1516,16 +1500,11 @@ return true; } - if (!hasBlockValue(Val, BBFrom)) { - if (pushBlockValue(std::make_pair(BBFrom, Val))) - return false; - // No new information. - Result = LocalResult; - return true; - } + ValueLatticeElement InBlock; + if (!getBlockValue(InBlock, Val, BBFrom)) + return false; // Try to intersect ranges of the BB and the constraint on the edge. - ValueLatticeElement InBlock = getBlockValue(Val, BBFrom); intersectAssumeOrGuardBlockValueConstantRange(Val, InBlock, BBFrom->getTerminator()); // We can use the context instruction (generically the ultimate instruction @@ -1548,11 +1527,13 @@ << BB->getName() << "'\n"); assert(BlockValueStack.empty() && BlockValueSet.empty()); - if (!hasBlockValue(V, BB)) { - pushBlockValue(std::make_pair(BB, V)); + ValueLatticeElement Result; + if (!getBlockValue(Result, V, BB)) { solve(); + bool ValueAvailable = getBlockValue(Result, V, BB); + (void) ValueAvailable; + assert(ValueAvailable && "Value not available after solving"); } - ValueLatticeElement Result = getBlockValue(V, BB); intersectAssumeOrGuardBlockValueConstantRange(V, Result, CxtI); LLVM_DEBUG(dbgs() << " Result = " << Result << "\n");