diff options
Diffstat (limited to 'contrib/llvm/lib/Analysis/LazyValueInfo.cpp')
| -rw-r--r-- | contrib/llvm/lib/Analysis/LazyValueInfo.cpp | 964 |
1 files changed, 500 insertions, 464 deletions
diff --git a/contrib/llvm/lib/Analysis/LazyValueInfo.cpp b/contrib/llvm/lib/Analysis/LazyValueInfo.cpp index 3ce667f..d442310 100644 --- a/contrib/llvm/lib/Analysis/LazyValueInfo.cpp +++ b/contrib/llvm/lib/Analysis/LazyValueInfo.cpp @@ -26,6 +26,7 @@ #include "llvm/IR/Dominators.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" @@ -50,7 +51,7 @@ namespace llvm { FunctionPass *createLazyValueInfoPass() { return new LazyValueInfoWrapperPass(); } } -char LazyValueAnalysis::PassID; +AnalysisKey LazyValueAnalysis::Key; //===----------------------------------------------------------------------===// // LVILatticeVal @@ -70,12 +71,14 @@ class LVILatticeVal { /// "nothing known yet". undefined, - /// This Value has a specific constant value. (For integers, constantrange - /// is used instead.) + /// This Value has a specific constant value. (For constant integers, + /// constantrange is used instead. Integer typed constantexprs can appear + /// as constant.) constant, - /// This Value is known to not have the specified value. (For integers, - /// constantrange is used instead.) + /// This Value is known to not have the specified value. (For constant + /// integers, constantrange is used instead. As above, integer typed + /// constantexprs can appear here.) notconstant, /// The Value falls within this range. (Used only for integer typed values.) @@ -139,37 +142,37 @@ public: return Range; } - /// Return true if this is a change in status. - bool markOverdefined() { +private: + void markOverdefined() { if (isOverdefined()) - return false; + return; Tag = overdefined; - return true; } - /// Return true if this is a change in status. - bool markConstant(Constant *V) { + void markConstant(Constant *V) { assert(V && "Marking constant with NULL"); - if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) - return markConstantRange(ConstantRange(CI->getValue())); + if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) { + markConstantRange(ConstantRange(CI->getValue())); + return; + } if (isa<UndefValue>(V)) - return false; + return; assert((!isConstant() || getConstant() == V) && "Marking constant with different value"); assert(isUndefined()); Tag = constant; Val = V; - return true; } - /// Return true if this is a change in status. - bool markNotConstant(Constant *V) { + void markNotConstant(Constant *V) { assert(V && "Marking constant with NULL"); - if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) - return markConstantRange(ConstantRange(CI->getValue()+1, CI->getValue())); + if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) { + markConstantRange(ConstantRange(CI->getValue()+1, CI->getValue())); + return; + } if (isa<UndefValue>(V)) - return false; + return; assert((!isConstant() || getConstant() != V) && "Marking constant !constant with same value"); @@ -178,100 +181,70 @@ public: assert(isUndefined() || isConstant()); Tag = notconstant; Val = V; - return true; } - /// Return true if this is a change in status. - bool markConstantRange(ConstantRange NewR) { + void markConstantRange(ConstantRange NewR) { if (isConstantRange()) { if (NewR.isEmptySet()) - return markOverdefined(); - - bool changed = Range != NewR; - Range = std::move(NewR); - return changed; + markOverdefined(); + else { + Range = std::move(NewR); + } + return; } assert(isUndefined()); if (NewR.isEmptySet()) - return markOverdefined(); - - Tag = constantrange; - Range = std::move(NewR); - return true; + markOverdefined(); + else { + Tag = constantrange; + Range = std::move(NewR); + } } +public: + /// Merge the specified lattice value into this one, updating this /// one and returning true if anything changed. - bool mergeIn(const LVILatticeVal &RHS, const DataLayout &DL) { - if (RHS.isUndefined() || isOverdefined()) return false; - if (RHS.isOverdefined()) return markOverdefined(); + void mergeIn(const LVILatticeVal &RHS, const DataLayout &DL) { + if (RHS.isUndefined() || isOverdefined()) + return; + if (RHS.isOverdefined()) { + markOverdefined(); + return; + } if (isUndefined()) { - Tag = RHS.Tag; - Val = RHS.Val; - Range = RHS.Range; - return true; + *this = RHS; + return; } if (isConstant()) { - if (RHS.isConstant()) { - if (Val == RHS.Val) - return false; - return markOverdefined(); - } - - if (RHS.isNotConstant()) { - if (Val == RHS.Val) - return markOverdefined(); - - // Unless we can prove that the two Constants are different, we must - // move to overdefined. - if (ConstantInt *Res = - dyn_cast<ConstantInt>(ConstantFoldCompareInstOperands( - CmpInst::ICMP_NE, getConstant(), RHS.getNotConstant(), DL))) - if (Res->isOne()) - return markNotConstant(RHS.getNotConstant()); - - return markOverdefined(); - } - - return markOverdefined(); + if (RHS.isConstant() && Val == RHS.Val) + return; + markOverdefined(); + return; } if (isNotConstant()) { - if (RHS.isConstant()) { - if (Val == RHS.Val) - return markOverdefined(); - - // Unless we can prove that the two Constants are different, we must - // move to overdefined. - if (ConstantInt *Res = - dyn_cast<ConstantInt>(ConstantFoldCompareInstOperands( - CmpInst::ICMP_NE, getNotConstant(), RHS.getConstant(), DL))) - if (Res->isOne()) - return false; - - return markOverdefined(); - } - - if (RHS.isNotConstant()) { - if (Val == RHS.Val) - return false; - return markOverdefined(); - } - - return markOverdefined(); + if (RHS.isNotConstant() && Val == RHS.Val) + return; + markOverdefined(); + return; } assert(isConstantRange() && "New LVILattice type?"); - if (!RHS.isConstantRange()) - return markOverdefined(); - + if (!RHS.isConstantRange()) { + // We can get here if we've encountered a constantexpr of integer type + // and merge it with a constantrange. + markOverdefined(); + return; + } ConstantRange NewR = Range.unionWith(RHS.getConstantRange()); if (NewR.isFullSet()) - return markOverdefined(); - return markConstantRange(NewR); + markOverdefined(); + else + markConstantRange(NewR); } }; @@ -366,6 +339,9 @@ namespace { /// A callback value handle updates the cache when values are erased. class LazyValueInfoCache; struct LVIValueHandle final : public CallbackVH { + // Needs to access getValPtr(), which is protected. + friend struct DenseMapInfo<LVIValueHandle>; + LazyValueInfoCache *Parent; LVIValueHandle(Value *V, LazyValueInfoCache *P) @@ -376,7 +352,7 @@ namespace { deleted(); } }; -} +} // end anonymous namespace namespace { /// This is the cache kept by LazyValueInfo which @@ -387,12 +363,15 @@ namespace { /// 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; + struct ValueCacheEntryTy { + ValueCacheEntryTy(Value *V, LazyValueInfoCache *P) : Handle(V, P) {} + LVIValueHandle Handle; + SmallDenseMap<AssertingVH<BasicBlock>, LVILatticeVal, 4> BlockVals; + }; /// This is all of the cached information for all values, /// mapped from Value* to key information. - std::map<LVIValueHandle, ValueCacheEntryTy> ValueCache; + DenseMap<Value *, std::unique_ptr<ValueCacheEntryTy>> ValueCache; /// This tracks, on a per-block basis, the set of values that are /// over-defined at the end of that block. @@ -404,6 +383,183 @@ namespace { /// don't spend time removing unused blocks from our caches. DenseSet<AssertingVH<BasicBlock> > SeenBlocks; + public: + void insertResult(Value *Val, BasicBlock *BB, const LVILatticeVal &Result) { + SeenBlocks.insert(BB); + + // Insert over-defined values into their own cache to reduce memory + // overhead. + if (Result.isOverdefined()) + OverDefinedCache[BB].insert(Val); + else { + auto It = ValueCache.find_as(Val); + if (It == ValueCache.end()) { + ValueCache[Val] = make_unique<ValueCacheEntryTy>(Val, this); + It = ValueCache.find_as(Val); + assert(It != ValueCache.end() && "Val was just added to the map!"); + } + It->second->BlockVals[BB] = Result; + } + } + + 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) const { + if (isOverdefined(V, BB)) + return true; + + auto I = ValueCache.find_as(V); + if (I == ValueCache.end()) + return false; + + return I->second->BlockVals.count(BB); + } + + LVILatticeVal getCachedValueInfo(Value *V, BasicBlock *BB) const { + if (isOverdefined(V, BB)) + return LVILatticeVal::getOverdefined(); + + auto I = ValueCache.find_as(V); + if (I == ValueCache.end()) + return LVILatticeVal(); + auto BBI = I->second->BlockVals.find(BB); + if (BBI == I->second->BlockVals.end()) + return LVILatticeVal(); + return BBI->second; + } + + /// clear - Empty the cache. + void clear() { + SeenBlocks.clear(); + ValueCache.clear(); + OverDefinedCache.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); + + friend struct LVIValueHandle; + }; +} + +void LazyValueInfoCache::eraseValue(Value *V) { + SmallVector<AssertingVH<BasicBlock>, 4> ToErase; + for (auto &I : OverDefinedCache) { + SmallPtrSetImpl<Value *> &ValueSet = I.second; + ValueSet.erase(V); + if (ValueSet.empty()) + ToErase.push_back(I.first); + } + for (auto &BB : ToErase) + OverDefinedCache.erase(BB); + + ValueCache.erase(V); +} + +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) { + // Shortcut if we have never seen this block. + DenseSet<AssertingVH<BasicBlock> >::iterator I = SeenBlocks.find(BB); + if (I == SeenBlocks.end()) + return; + SeenBlocks.erase(I); + + auto ODI = OverDefinedCache.find(BB); + if (ODI != OverDefinedCache.end()) + OverDefinedCache.erase(ODI); + + for (auto &I : ValueCache) + I.second->BlockVals.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); + + 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 + // 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 = OverDefinedCache.find(ToUpdate); + if (OI == OverDefinedCache.end()) + continue; + SmallPtrSetImpl<Value *> &ValueSet = OI->second; + + 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 (ValueSet.empty()) { + OverDefinedCache.erase(OI); + break; + } + } + + if (!changed) continue; + + worklist.insert(worklist.end(), succ_begin(ToUpdate), succ_end(ToUpdate)); + } +} + +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. @@ -428,19 +584,6 @@ namespace { const DataLayout &DL; ///< A mandatory DataLayout DominatorTree *DT; ///< An optional DT pointer. - friend struct LVIValueHandle; - - void insertResult(Value *Val, BasicBlock *BB, const LVILatticeVal &Result) { - SeenBlocks.insert(BB); - - // 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); bool getEdgeValue(Value *V, BasicBlock *F, BasicBlock *T, LVILatticeVal &Result, Instruction *CxtI = nullptr); @@ -450,6 +593,7 @@ namespace { // 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); + bool solveBlockValueImpl(LVILatticeVal &Res, Value *Val, BasicBlock *BB); bool solveBlockValueNonLocal(LVILatticeVal &BBLV, Value *Val, BasicBlock *BB); bool solveBlockValuePHINode(LVILatticeVal &BBLV, PHINode *PN, BasicBlock *BB); bool solveBlockValueSelect(LVILatticeVal &BBLV, SelectInst *S, @@ -458,43 +602,12 @@ namespace { BasicBlock *BB); bool solveBlockValueCast(LVILatticeVal &BBLV, Instruction *BBI, BasicBlock *BB); - void intersectAssumeBlockValueConstantRange(Value *Val, LVILatticeVal &BBLV, + void intersectAssumeOrGuardBlockValueConstantRange(Value *Val, + LVILatticeVal &BBLV, Instruction *BBI); void solve(); - ValueCacheEntryTy &lookup(Value *V) { - 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. @@ -511,60 +624,28 @@ namespace { LVILatticeVal getValueOnEdge(Value *V, BasicBlock *FromBB,BasicBlock *ToBB, Instruction *CxtI = nullptr); - /// 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); + /// Complete flush all previously computed values + void clear() { + TheCache.clear(); + } /// This is part of the update interface to inform the cache /// that a block has been deleted. - void eraseBlock(BasicBlock *BB); - - /// clear - Empty the cache. - void clear() { - SeenBlocks.clear(); - ValueCache.clear(); - OverDefinedCache.clear(); + void eraseBlock(BasicBlock *BB) { + TheCache.eraseBlock(BB); } - LazyValueInfoCache(AssumptionCache *AC, const DataLayout &DL, + /// 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, DominatorTree *DT = nullptr) : AC(AC), DL(DL), DT(DT) {} }; } // end anonymous namespace -void LVIValueHandle::deleted() { - 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. - Parent->ValueCache.erase(*this); -} - -void LazyValueInfoCache::eraseBlock(BasicBlock *BB) { - // Shortcut if we have never seen this block. - DenseSet<AssertingVH<BasicBlock> >::iterator I = SeenBlocks.find(BB); - if (I == SeenBlocks.end()) - return; - SeenBlocks.erase(I); - - auto ODI = OverDefinedCache.find(BB); - if (ODI != OverDefinedCache.end()) - OverDefinedCache.erase(ODI); - - for (auto &I : ValueCache) - I.second.erase(BB); -} - -void LazyValueInfoCache::solve() { +void LazyValueInfoImpl::solve() { while (!BlockValueStack.empty()) { std::pair<BasicBlock*, Value*> &e = BlockValueStack.top(); assert(BlockValueSet.count(e) && "Stack value should be in BlockValueSet!"); @@ -572,11 +653,11 @@ void LazyValueInfoCache::solve() { if (solveBlockValue(e.second, e.first)) { // The work item was completely processed. assert(BlockValueStack.top() == e && "Nothing should have been pushed!"); - assert(hasCachedValueInfo(e.second, e.first) && + assert(TheCache.hasCachedValueInfo(e.second, e.first) && "Result should be in cache!"); DEBUG(dbgs() << "POP " << *e.second << " in " << e.first->getName() - << " = " << getCachedValueInfo(e.second, e.first) << "\n"); + << " = " << TheCache.getCachedValueInfo(e.second, e.first) << "\n"); BlockValueStack.pop(); BlockValueSet.erase(e); @@ -587,21 +668,20 @@ void LazyValueInfoCache::solve() { } } -bool LazyValueInfoCache::hasBlockValue(Value *Val, BasicBlock *BB) { +bool LazyValueInfoImpl::hasBlockValue(Value *Val, BasicBlock *BB) { // If already a constant, there is nothing to compute. if (isa<Constant>(Val)) return true; - return hasCachedValueInfo(Val, BB); + return TheCache.hasCachedValueInfo(Val, BB); } -LVILatticeVal LazyValueInfoCache::getBlockValue(Value *Val, BasicBlock *BB) { +LVILatticeVal LazyValueInfoImpl::getBlockValue(Value *Val, BasicBlock *BB) { // If already a constant, there is nothing to compute. if (Constant *VC = dyn_cast<Constant>(Val)) return LVILatticeVal::get(VC); - SeenBlocks.insert(BB); - return getCachedValueInfo(Val, BB); + return TheCache.getCachedValueInfo(Val, BB); } static LVILatticeVal getFromRangeMetadata(Instruction *BBI) { @@ -610,7 +690,7 @@ static LVILatticeVal getFromRangeMetadata(Instruction *BBI) { case Instruction::Load: case Instruction::Call: case Instruction::Invoke: - if (MDNode *Ranges = BBI->getMetadata(LLVMContext::MD_range)) + if (MDNode *Ranges = BBI->getMetadata(LLVMContext::MD_range)) if (isa<IntegerType>(BBI->getType())) { return LVILatticeVal::getRange(getConstantRangeFromMetadata(*Ranges)); } @@ -620,14 +700,14 @@ static LVILatticeVal getFromRangeMetadata(Instruction *BBI) { return LVILatticeVal::getOverdefined(); } -bool LazyValueInfoCache::solveBlockValue(Value *Val, BasicBlock *BB) { +bool LazyValueInfoImpl::solveBlockValue(Value *Val, BasicBlock *BB) { if (isa<Constant>(Val)) return true; - if (hasCachedValueInfo(Val, BB)) { + if (TheCache.hasCachedValueInfo(Val, BB)) { // If we have a cached value, use that. DEBUG(dbgs() << " reuse BB '" << BB->getName() - << "' val=" << getCachedValueInfo(Val, BB) << '\n'); + << "' val=" << TheCache.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 @@ -638,28 +718,26 @@ bool LazyValueInfoCache::solveBlockValue(Value *Val, BasicBlock *BB) { // Hold off inserting this value into the Cache in case we have to return // false and come back later. LVILatticeVal Res; + if (!solveBlockValueImpl(Res, Val, BB)) + // Work pushed, will revisit + return false; + + TheCache.insertResult(Val, BB, Res); + return true; +} + +bool LazyValueInfoImpl::solveBlockValueImpl(LVILatticeVal &Res, + Value *Val, BasicBlock *BB) { Instruction *BBI = dyn_cast<Instruction>(Val); - if (!BBI || BBI->getParent() != BB) { - if (!solveBlockValueNonLocal(Res, Val, BB)) - return false; - insertResult(Val, BB, Res); - return true; - } + if (!BBI || BBI->getParent() != BB) + return solveBlockValueNonLocal(Res, Val, BB); - if (PHINode *PN = dyn_cast<PHINode>(BBI)) { - if (!solveBlockValuePHINode(Res, PN, BB)) - return false; - insertResult(Val, BB, Res); - return true; - } + if (PHINode *PN = dyn_cast<PHINode>(BBI)) + return solveBlockValuePHINode(Res, PN, BB); - if (auto *SI = dyn_cast<SelectInst>(BBI)) { - if (!solveBlockValueSelect(Res, SI, BB)) - return false; - insertResult(Val, BB, Res); - return true; - } + if (auto *SI = dyn_cast<SelectInst>(BBI)) + return solveBlockValueSelect(Res, 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 @@ -673,29 +751,20 @@ bool LazyValueInfoCache::solveBlockValue(Value *Val, BasicBlock *BB) { PointerType *PT = dyn_cast<PointerType>(BBI->getType()); if (PT && isKnownNonNull(BBI)) { Res = LVILatticeVal::getNot(ConstantPointerNull::get(PT)); - insertResult(Val, BB, Res); return true; } if (BBI->getType()->isIntegerTy()) { - if (isa<CastInst>(BBI)) { - if (!solveBlockValueCast(Res, BBI, BB)) - return false; - insertResult(Val, BB, Res); - return true; - } + if (isa<CastInst>(BBI)) + return solveBlockValueCast(Res, BBI, BB); + BinaryOperator *BO = dyn_cast<BinaryOperator>(BBI); - if (BO && isa<ConstantInt>(BO->getOperand(1))) { - if (!solveBlockValueBinaryOp(Res, BBI, BB)) - return false; - insertResult(Val, BB, Res); - return true; - } + if (BO && isa<ConstantInt>(BO->getOperand(1))) + return solveBlockValueBinaryOp(Res, BBI, BB); } DEBUG(dbgs() << " compute BB '" << BB->getName() << "' - unknown inst def found.\n"); Res = getFromRangeMetadata(BBI); - insertResult(Val, BB, Res); return true; } @@ -748,7 +817,7 @@ static bool isObjectDereferencedInBlock(Value *Val, BasicBlock *BB) { return false; } -bool LazyValueInfoCache::solveBlockValueNonLocal(LVILatticeVal &BBLV, +bool LazyValueInfoImpl::solveBlockValueNonLocal(LVILatticeVal &BBLV, Value *Val, BasicBlock *BB) { LVILatticeVal Result; // Start Undefined. @@ -763,7 +832,7 @@ bool LazyValueInfoCache::solveBlockValueNonLocal(LVILatticeVal &BBLV, PointerType *PTy = cast<PointerType>(Val->getType()); Result = LVILatticeVal::getNot(ConstantPointerNull::get(PTy)); } else { - Result.markOverdefined(); + Result = LVILatticeVal::getOverdefined(); } BBLV = Result; return true; @@ -785,7 +854,7 @@ bool LazyValueInfoCache::solveBlockValueNonLocal(LVILatticeVal &BBLV, if (Result.isOverdefined()) { DEBUG(dbgs() << " compute BB '" << BB->getName() << "' - overdefined because of pred (non local).\n"); - // Bofore giving up, see if we can prove the pointer non-null local to + // Before giving up, see if we can prove the pointer non-null local to // this particular block. if (Val->getType()->isPointerTy() && isObjectDereferencedInBlock(Val, BB)) { @@ -806,7 +875,7 @@ bool LazyValueInfoCache::solveBlockValueNonLocal(LVILatticeVal &BBLV, return true; } -bool LazyValueInfoCache::solveBlockValuePHINode(LVILatticeVal &BBLV, +bool LazyValueInfoImpl::solveBlockValuePHINode(LVILatticeVal &BBLV, PHINode *PN, BasicBlock *BB) { LVILatticeVal Result; // Start Undefined. @@ -845,64 +914,70 @@ bool LazyValueInfoCache::solveBlockValuePHINode(LVILatticeVal &BBLV, return true; } -static bool getValueFromFromCondition(Value *Val, ICmpInst *ICI, - LVILatticeVal &Result, - bool isTrueDest = true); +static LVILatticeVal getValueFromCondition(Value *Val, Value *Cond, + bool isTrueDest = true); // If we can determine a constraint on the value given conditions assumed by // the program, intersect those constraints with BBLV -void LazyValueInfoCache::intersectAssumeBlockValueConstantRange(Value *Val, - LVILatticeVal &BBLV, - Instruction *BBI) { +void LazyValueInfoImpl::intersectAssumeOrGuardBlockValueConstantRange( + Value *Val, LVILatticeVal &BBLV, Instruction *BBI) { BBI = BBI ? BBI : dyn_cast<Instruction>(Val); if (!BBI) return; - for (auto &AssumeVH : AC->assumptions()) { + for (auto &AssumeVH : AC->assumptionsFor(Val)) { if (!AssumeVH) continue; auto *I = cast<CallInst>(AssumeVH); if (!isValidAssumeForContext(I, BBI, DT)) continue; - Value *C = I->getArgOperand(0); - if (ICmpInst *ICI = dyn_cast<ICmpInst>(C)) { - LVILatticeVal Result; - if (getValueFromFromCondition(Val, ICI, Result)) - BBLV = intersect(BBLV, Result); - } + BBLV = intersect(BBLV, getValueFromCondition(Val, I->getArgOperand(0))); + } + + // If guards are not used in the module, don't spend time looking for them + auto *GuardDecl = BBI->getModule()->getFunction( + Intrinsic::getName(Intrinsic::experimental_guard)); + if (!GuardDecl || GuardDecl->use_empty()) + return; + + for (Instruction &I : make_range(BBI->getIterator().getReverse(), + BBI->getParent()->rend())) { + Value *Cond = nullptr; + if (match(&I, m_Intrinsic<Intrinsic::experimental_guard>(m_Value(Cond)))) + BBLV = intersect(BBLV, getValueFromCondition(Val, Cond)); } } -bool LazyValueInfoCache::solveBlockValueSelect(LVILatticeVal &BBLV, +bool LazyValueInfoImpl::solveBlockValueSelect(LVILatticeVal &BBLV, 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.markOverdefined(); + BBLV = LVILatticeVal::getOverdefined(); return true; } LVILatticeVal TrueVal = getBlockValue(SI->getTrueValue(), BB); // 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()) { - BBLV.markOverdefined(); + BBLV = LVILatticeVal::getOverdefined(); return true; } if (!hasBlockValue(SI->getFalseValue(), BB)) { if (pushBlockValue(std::make_pair(BB, SI->getFalseValue()))) return false; - BBLV.markOverdefined(); + BBLV = LVILatticeVal::getOverdefined(); return true; } LVILatticeVal FalseVal = getBlockValue(SI->getFalseValue(), BB); // 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()) { - BBLV.markOverdefined(); + BBLV = LVILatticeVal::getOverdefined(); return true; } @@ -916,22 +991,22 @@ bool LazyValueInfoCache::solveBlockValueSelect(LVILatticeVal &BBLV, // ValueTracking getting smarter looking back past our immediate inputs.) if (SelectPatternResult::isMinOrMax(SPR.Flavor) && LHS == SI->getTrueValue() && RHS == SI->getFalseValue()) { - switch (SPR.Flavor) { - default: - llvm_unreachable("unexpected minmax type!"); - case SPF_SMIN: /// Signed minimum - BBLV.markConstantRange(TrueCR.smin(FalseCR)); - return true; - case SPF_UMIN: /// Unsigned minimum - BBLV.markConstantRange(TrueCR.umin(FalseCR)); - return true; - case SPF_SMAX: /// Signed maximum - BBLV.markConstantRange(TrueCR.smax(FalseCR)); - return true; - case SPF_UMAX: /// Unsigned maximum - BBLV.markConstantRange(TrueCR.umax(FalseCR)); - return true; - }; + 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); + }; + }(); + BBLV = LVILatticeVal::getRange(ResultCR); + return true; } // TODO: ABS, NABS from the SelectPatternResult @@ -940,27 +1015,21 @@ bool LazyValueInfoCache::solveBlockValueSelect(LVILatticeVal &BBLV, // 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. - if (auto *ICI = dyn_cast<ICmpInst>(SI->getCondition())) { - LVILatticeVal TrueValTaken, FalseValTaken; - if (!getValueFromFromCondition(SI->getTrueValue(), ICI, - TrueValTaken, true)) - TrueValTaken.markOverdefined(); - if (!getValueFromFromCondition(SI->getFalseValue(), ICI, - FalseValTaken, false)) - FalseValTaken.markOverdefined(); - - TrueVal = intersect(TrueVal, TrueValTaken); - FalseVal = intersect(FalseVal, FalseValTaken); - - - // Handle clamp idioms such as: - // %24 = constantrange<0, 17> - // %39 = icmp eq i32 %24, 0 - // %40 = add i32 %24, -1 - // %siv.next = select i1 %39, i32 16, i32 %40 - // %siv.next = constantrange<0, 17> not <-1, 17> - // In general, this can handle any clamp idiom which tests the edge - // condition via an equality or inequality. + Value *Cond = SI->getCondition(); + TrueVal = intersect(TrueVal, + getValueFromCondition(SI->getTrueValue(), Cond, true)); + FalseVal = intersect(FalseVal, + getValueFromCondition(SI->getFalseValue(), Cond, false)); + + // Handle clamp idioms such as: + // %24 = constantrange<0, 17> + // %39 = icmp eq i32 %24, 0 + // %40 = add i32 %24, -1 + // %siv.next = select i1 %39, i32 16, i32 %40 + // %siv.next = constantrange<0, 17> not <-1, 17> + // In general, this can handle any clamp idiom which tests the edge + // condition via an equality or inequality. + if (auto *ICI = dyn_cast<ICmpInst>(Cond)) { ICmpInst::Predicate Pred = ICI->getPredicate(); Value *A = ICI->getOperand(0); if (ConstantInt *CIBase = dyn_cast<ConstantInt>(ICI->getOperand(1))) { @@ -1001,13 +1070,13 @@ bool LazyValueInfoCache::solveBlockValueSelect(LVILatticeVal &BBLV, return true; } -bool LazyValueInfoCache::solveBlockValueCast(LVILatticeVal &BBLV, +bool LazyValueInfoImpl::solveBlockValueCast(LVILatticeVal &BBLV, Instruction *BBI, BasicBlock *BB) { if (!BBI->getOperand(0)->getType()->isSized()) { // Without knowing how wide the input is, we can't analyze it in any useful // way. - BBLV.markOverdefined(); + BBLV = LVILatticeVal::getOverdefined(); return true; } @@ -1024,7 +1093,7 @@ bool LazyValueInfoCache::solveBlockValueCast(LVILatticeVal &BBLV, // Unhandled instructions are overdefined. DEBUG(dbgs() << " compute BB '" << BB->getName() << "' - overdefined (unknown cast).\n"); - BBLV.markOverdefined(); + BBLV = LVILatticeVal::getOverdefined(); return true; } @@ -1041,7 +1110,8 @@ bool LazyValueInfoCache::solveBlockValueCast(LVILatticeVal &BBLV, ConstantRange LHSRange = ConstantRange(OperandBitWidth); if (hasBlockValue(BBI->getOperand(0), BB)) { LVILatticeVal LHSVal = getBlockValue(BBI->getOperand(0), BB); - intersectAssumeBlockValueConstantRange(BBI->getOperand(0), LHSVal, BBI); + intersectAssumeOrGuardBlockValueConstantRange(BBI->getOperand(0), LHSVal, + BBI); if (LHSVal.isConstantRange()) LHSRange = LHSVal.getConstantRange(); } @@ -1052,31 +1122,12 @@ bool LazyValueInfoCache::solveBlockValueCast(LVILatticeVal &BBLV, // 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. - LVILatticeVal Result; - switch (BBI->getOpcode()) { - case Instruction::Trunc: - Result.markConstantRange(LHSRange.truncate(ResultBitWidth)); - break; - case Instruction::SExt: - Result.markConstantRange(LHSRange.signExtend(ResultBitWidth)); - break; - case Instruction::ZExt: - Result.markConstantRange(LHSRange.zeroExtend(ResultBitWidth)); - break; - case Instruction::BitCast: - Result.markConstantRange(LHSRange); - break; - default: - // Should be dead if the code above is correct - llvm_unreachable("inconsistent with above"); - break; - } - - BBLV = Result; + auto CastOp = (Instruction::CastOps) BBI->getOpcode(); + BBLV = LVILatticeVal::getRange(LHSRange.castOp(CastOp, ResultBitWidth)); return true; } -bool LazyValueInfoCache::solveBlockValueBinaryOp(LVILatticeVal &BBLV, +bool LazyValueInfoImpl::solveBlockValueBinaryOp(LVILatticeVal &BBLV, Instruction *BBI, BasicBlock *BB) { @@ -1101,7 +1152,7 @@ bool LazyValueInfoCache::solveBlockValueBinaryOp(LVILatticeVal &BBLV, // Unhandled instructions are overdefined. DEBUG(dbgs() << " compute BB '" << BB->getName() << "' - overdefined (unknown binary operator).\n"); - BBLV.markOverdefined(); + BBLV = LVILatticeVal::getOverdefined(); return true; }; @@ -1118,7 +1169,8 @@ bool LazyValueInfoCache::solveBlockValueBinaryOp(LVILatticeVal &BBLV, ConstantRange LHSRange = ConstantRange(OperandBitWidth); if (hasBlockValue(BBI->getOperand(0), BB)) { LVILatticeVal LHSVal = getBlockValue(BBI->getOperand(0), BB); - intersectAssumeBlockValueConstantRange(BBI->getOperand(0), LHSVal, BBI); + intersectAssumeOrGuardBlockValueConstantRange(BBI->getOperand(0), LHSVal, + BBI); if (LHSVal.isConstantRange()) LHSRange = LHSVal.getConstantRange(); } @@ -1129,82 +1181,114 @@ bool LazyValueInfoCache::solveBlockValueBinaryOp(LVILatticeVal &BBLV, // 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. - LVILatticeVal Result; - switch (BBI->getOpcode()) { - case Instruction::Add: - Result.markConstantRange(LHSRange.add(RHSRange)); - break; - case Instruction::Sub: - Result.markConstantRange(LHSRange.sub(RHSRange)); - break; - case Instruction::Mul: - Result.markConstantRange(LHSRange.multiply(RHSRange)); - break; - case Instruction::UDiv: - Result.markConstantRange(LHSRange.udiv(RHSRange)); - break; - case Instruction::Shl: - Result.markConstantRange(LHSRange.shl(RHSRange)); - break; - case Instruction::LShr: - Result.markConstantRange(LHSRange.lshr(RHSRange)); - break; - case Instruction::And: - Result.markConstantRange(LHSRange.binaryAnd(RHSRange)); - break; - case Instruction::Or: - Result.markConstantRange(LHSRange.binaryOr(RHSRange)); - break; - default: - // Should be dead if the code above is correct - llvm_unreachable("inconsistent with above"); - break; - } - - BBLV = Result; + auto BinOp = (Instruction::BinaryOps) BBI->getOpcode(); + BBLV = LVILatticeVal::getRange(LHSRange.binaryOp(BinOp, RHSRange)); return true; } -bool getValueFromFromCondition(Value *Val, ICmpInst *ICI, - LVILatticeVal &Result, bool isTrueDest) { - assert(ICI && "precondition"); - if (isa<Constant>(ICI->getOperand(1))) { - if (ICI->isEquality() && ICI->getOperand(0) == Val) { +static LVILatticeVal getValueFromICmpCondition(Value *Val, ICmpInst *ICI, + bool isTrueDest) { + Value *LHS = ICI->getOperand(0); + Value *RHS = ICI->getOperand(1); + CmpInst::Predicate Predicate = ICI->getPredicate(); + + if (isa<Constant>(RHS)) { + if (ICI->isEquality() && LHS == Val) { // We know that V has the RHS constant if this is a true SETEQ or // false SETNE. - if (isTrueDest == (ICI->getPredicate() == ICmpInst::ICMP_EQ)) - Result = LVILatticeVal::get(cast<Constant>(ICI->getOperand(1))); + if (isTrueDest == (Predicate == ICmpInst::ICMP_EQ)) + return LVILatticeVal::get(cast<Constant>(RHS)); else - Result = LVILatticeVal::getNot(cast<Constant>(ICI->getOperand(1))); - return true; + return LVILatticeVal::getNot(cast<Constant>(RHS)); } + } - // Recognize the range checking idiom that InstCombine produces. - // (X-C1) u< C2 --> [C1, C1+C2) - ConstantInt *NegOffset = nullptr; - if (ICI->getPredicate() == ICmpInst::ICMP_ULT) - match(ICI->getOperand(0), m_Add(m_Specific(Val), - m_ConstantInt(NegOffset))); - - ConstantInt *CI = dyn_cast<ConstantInt>(ICI->getOperand(1)); - if (CI && (ICI->getOperand(0) == Val || NegOffset)) { - // Calculate the range of values that are allowed by the comparison - ConstantRange CmpRange(CI->getValue()); - ConstantRange TrueValues = - ConstantRange::makeAllowedICmpRegion(ICI->getPredicate(), CmpRange); + if (!Val->getType()->isIntegerTy()) + return LVILatticeVal::getOverdefined(); + + // Use ConstantRange::makeAllowedICmpRegion in order to determine the possible + // range of Val guaranteed by the condition. Recognize comparisons in the from + // of: + // icmp <pred> Val, ... + // icmp <pred> (add Val, Offset), ... + // The latter is the range checking idiom that InstCombine produces. Subtract + // the offset from the allowed range for RHS in this case. + + // Val or (add Val, Offset) can be on either hand of the comparison + if (LHS != Val && !match(LHS, m_Add(m_Specific(Val), m_ConstantInt()))) { + std::swap(LHS, RHS); + Predicate = CmpInst::getSwappedPredicate(Predicate); + } - if (NegOffset) // Apply the offset from above. - TrueValues = TrueValues.subtract(NegOffset->getValue()); + ConstantInt *Offset = nullptr; + if (LHS != Val) + match(LHS, m_Add(m_Specific(Val), m_ConstantInt(Offset))); + + if (LHS == Val || Offset) { + // Calculate the range of values that are allowed by the comparison + ConstantRange RHSRange(RHS->getType()->getIntegerBitWidth(), + /*isFullSet=*/true); + if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) + RHSRange = ConstantRange(CI->getValue()); + else if (Instruction *I = dyn_cast<Instruction>(RHS)) + if (auto *Ranges = I->getMetadata(LLVMContext::MD_range)) + RHSRange = getConstantRangeFromMetadata(*Ranges); + + // If we're interested in the false dest, invert the condition + CmpInst::Predicate Pred = + isTrueDest ? Predicate : CmpInst::getInversePredicate(Predicate); + ConstantRange TrueValues = + ConstantRange::makeAllowedICmpRegion(Pred, RHSRange); - // If we're interested in the false dest, invert the condition. - if (!isTrueDest) TrueValues = TrueValues.inverse(); + if (Offset) // Apply the offset from above. + TrueValues = TrueValues.subtract(Offset->getValue()); - Result = LVILatticeVal::getRange(std::move(TrueValues)); - return true; - } + return LVILatticeVal::getRange(std::move(TrueValues)); } - return false; + return LVILatticeVal::getOverdefined(); +} + +static LVILatticeVal +getValueFromCondition(Value *Val, Value *Cond, bool isTrueDest, + DenseMap<Value*, LVILatticeVal> &Visited); + +static LVILatticeVal +getValueFromConditionImpl(Value *Val, Value *Cond, bool isTrueDest, + DenseMap<Value*, LVILatticeVal> &Visited) { + if (ICmpInst *ICI = dyn_cast<ICmpInst>(Cond)) + return getValueFromICmpCondition(Val, ICI, isTrueDest); + + // Handle conditions in the form of (cond1 && cond2), we know that on the + // true dest path both of the conditions hold. + if (!isTrueDest) + return LVILatticeVal::getOverdefined(); + + BinaryOperator *BO = dyn_cast<BinaryOperator>(Cond); + if (!BO || BO->getOpcode() != BinaryOperator::And) + return LVILatticeVal::getOverdefined(); + + auto RHS = getValueFromCondition(Val, BO->getOperand(0), isTrueDest, Visited); + auto LHS = getValueFromCondition(Val, BO->getOperand(1), isTrueDest, Visited); + return intersect(RHS, LHS); +} + +static LVILatticeVal +getValueFromCondition(Value *Val, Value *Cond, bool isTrueDest, + DenseMap<Value*, LVILatticeVal> &Visited) { + auto I = Visited.find(Cond); + if (I != Visited.end()) + return I->second; + + auto Result = getValueFromConditionImpl(Val, Cond, isTrueDest, Visited); + Visited[Cond] = Result; + return Result; +} + +LVILatticeVal getValueFromCondition(Value *Val, Value *Cond, bool isTrueDest) { + assert(Cond && "precondition"); + DenseMap<Value*, LVILatticeVal> Visited; + return getValueFromCondition(Val, Cond, isTrueDest, Visited); } /// \brief Compute the value of Val on the edge BBFrom -> BBTo. Returns false if @@ -1233,9 +1317,9 @@ static bool getEdgeValueLocal(Value *Val, BasicBlock *BBFrom, // If the condition of the branch is an equality comparison, we may be // able to infer the value. - if (ICmpInst *ICI = dyn_cast<ICmpInst>(BI->getCondition())) - if (getValueFromFromCondition(Val, ICI, Result, isTrueDest)) - return true; + Result = getValueFromCondition(Val, BI->getCondition(), isTrueDest); + if (!Result.isOverdefined()) + return true; } } @@ -1267,7 +1351,7 @@ static bool getEdgeValueLocal(Value *Val, BasicBlock *BBFrom, /// \brief Compute the value of Val on the edge BBFrom -> BBTo or the value at /// the basic block if the edge does not constrain Val. -bool LazyValueInfoCache::getEdgeValue(Value *Val, BasicBlock *BBFrom, +bool LazyValueInfoImpl::getEdgeValue(Value *Val, BasicBlock *BBFrom, BasicBlock *BBTo, LVILatticeVal &Result, Instruction *CxtI) { // If already a constant, there is nothing to compute. @@ -1280,7 +1364,7 @@ bool LazyValueInfoCache::getEdgeValue(Value *Val, BasicBlock *BBFrom, if (!getEdgeValueLocal(Val, BBFrom, BBTo, LocalResult)) // If we couldn't constrain the value on the edge, LocalResult doesn't // provide any information. - LocalResult.markOverdefined(); + LocalResult = LVILatticeVal::getOverdefined(); if (hasSingleValue(LocalResult)) { // Can't get any more precise here @@ -1298,39 +1382,40 @@ bool LazyValueInfoCache::getEdgeValue(Value *Val, BasicBlock *BBFrom, // Try to intersect ranges of the BB and the constraint on the edge. LVILatticeVal InBlock = getBlockValue(Val, BBFrom); - intersectAssumeBlockValueConstantRange(Val, InBlock, BBFrom->getTerminator()); + intersectAssumeOrGuardBlockValueConstantRange(Val, InBlock, + BBFrom->getTerminator()); // 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 - // LazyValueInfoCache::getValueOnEdge, the context instruction is provided, + // LazyValueInfoImpl::getValueOnEdge, the context instruction is provided, // but then the result is not cached. - intersectAssumeBlockValueConstantRange(Val, InBlock, CxtI); + intersectAssumeOrGuardBlockValueConstantRange(Val, InBlock, CxtI); Result = intersect(LocalResult, InBlock); return true; } -LVILatticeVal LazyValueInfoCache::getValueInBlock(Value *V, BasicBlock *BB, +LVILatticeVal LazyValueInfoImpl::getValueInBlock(Value *V, BasicBlock *BB, Instruction *CxtI) { DEBUG(dbgs() << "LVI Getting block end value " << *V << " at '" << BB->getName() << "'\n"); assert(BlockValueStack.empty() && BlockValueSet.empty()); if (!hasBlockValue(V, BB)) { - pushBlockValue(std::make_pair(BB, V)); + pushBlockValue(std::make_pair(BB, V)); solve(); } LVILatticeVal Result = getBlockValue(V, BB); - intersectAssumeBlockValueConstantRange(V, Result, CxtI); + intersectAssumeOrGuardBlockValueConstantRange(V, Result, CxtI); DEBUG(dbgs() << " Result = " << Result << "\n"); return Result; } -LVILatticeVal LazyValueInfoCache::getValueAt(Value *V, Instruction *CxtI) { +LVILatticeVal LazyValueInfoImpl::getValueAt(Value *V, Instruction *CxtI) { DEBUG(dbgs() << "LVI Getting value " << *V << " at '" << CxtI->getName() << "'\n"); @@ -1340,13 +1425,13 @@ LVILatticeVal LazyValueInfoCache::getValueAt(Value *V, Instruction *CxtI) { LVILatticeVal Result = LVILatticeVal::getOverdefined(); if (auto *I = dyn_cast<Instruction>(V)) Result = getFromRangeMetadata(I); - intersectAssumeBlockValueConstantRange(V, Result, CxtI); + intersectAssumeOrGuardBlockValueConstantRange(V, Result, CxtI); DEBUG(dbgs() << " Result = " << Result << "\n"); return Result; } -LVILatticeVal LazyValueInfoCache:: +LVILatticeVal LazyValueInfoImpl:: getValueOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB, Instruction *CxtI) { DEBUG(dbgs() << "LVI Getting edge value " << *V << " from '" @@ -1364,75 +1449,24 @@ getValueOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB, return Result; } -void LazyValueInfoCache::threadEdge(BasicBlock *PredBB, 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); - - 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 - // 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; - - bool changed = false; - for (Value *V : ValsToClear) { - // If a value was marked overdefined in OldSucc, and is here too... - auto OI = OverDefinedCache.find(ToUpdate); - if (OI == OverDefinedCache.end()) - continue; - SmallPtrSetImpl<Value *> &ValueSet = OI->second; - if (!ValueSet.count(V)) - continue; - - ValueSet.erase(V); - if (ValueSet.empty()) - OverDefinedCache.erase(OI); - - // If we removed anything, then we potentially need to update - // blocks successors too. - changed = true; - } - - if (!changed) continue; - - worklist.insert(worklist.end(), succ_begin(ToUpdate), succ_end(ToUpdate)); - } +void LazyValueInfoImpl::threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc, + BasicBlock *NewSucc) { + TheCache.threadEdgeImpl(OldSucc, NewSucc); } //===----------------------------------------------------------------------===// // LazyValueInfo Impl //===----------------------------------------------------------------------===// -/// This lazily constructs the LazyValueInfoCache. -static LazyValueInfoCache &getCache(void *&PImpl, AssumptionCache *AC, - const DataLayout *DL, - DominatorTree *DT = nullptr) { +/// This lazily constructs the LazyValueInfoImpl. +static LazyValueInfoImpl &getImpl(void *&PImpl, AssumptionCache *AC, + const DataLayout *DL, + DominatorTree *DT = nullptr) { if (!PImpl) { assert(DL && "getCache() called with a null DataLayout"); - PImpl = new LazyValueInfoCache(AC, *DL, DT); + PImpl = new LazyValueInfoImpl(AC, *DL, DT); } - return *static_cast<LazyValueInfoCache*>(PImpl); + return *static_cast<LazyValueInfoImpl*>(PImpl); } bool LazyValueInfoWrapperPass::runOnFunction(Function &F) { @@ -1445,7 +1479,7 @@ bool LazyValueInfoWrapperPass::runOnFunction(Function &F) { Info.TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(); if (Info.PImpl) - getCache(Info.PImpl, Info.AC, &DL, Info.DT).clear(); + getImpl(Info.PImpl, Info.AC, &DL, Info.DT).clear(); // Fully lazy. return false; @@ -1464,7 +1498,7 @@ LazyValueInfo::~LazyValueInfo() { releaseMemory(); } void LazyValueInfo::releaseMemory() { // If the cache was allocated, free it. if (PImpl) { - delete &getCache(PImpl, AC, nullptr); + delete &getImpl(PImpl, AC, nullptr); PImpl = nullptr; } } @@ -1479,7 +1513,6 @@ LazyValueInfo LazyValueAnalysis::run(Function &F, FunctionAnalysisManager &FAM) return LazyValueInfo(&AC, &TLI, DT); } - /// 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 @@ -1502,7 +1535,7 @@ Constant *LazyValueInfo::getConstant(Value *V, BasicBlock *BB, const DataLayout &DL = BB->getModule()->getDataLayout(); LVILatticeVal Result = - getCache(PImpl, AC, &DL, DT).getValueInBlock(V, BB, CxtI); + getImpl(PImpl, AC, &DL, DT).getValueInBlock(V, BB, CxtI); if (Result.isConstant()) return Result.getConstant(); @@ -1520,12 +1553,15 @@ ConstantRange LazyValueInfo::getConstantRange(Value *V, BasicBlock *BB, unsigned Width = V->getType()->getIntegerBitWidth(); const DataLayout &DL = BB->getModule()->getDataLayout(); LVILatticeVal Result = - getCache(PImpl, AC, &DL, DT).getValueInBlock(V, BB, CxtI); - assert(!Result.isConstant()); + getImpl(PImpl, AC, &DL, DT).getValueInBlock(V, BB, CxtI); if (Result.isUndefined()) return ConstantRange(Width, /*isFullSet=*/false); if (Result.isConstantRange()) return Result.getConstantRange(); + // We represent ConstantInt constants as constant ranges but other kinds + // of integer constants, i.e. ConstantExpr will be tagged as constants + assert(!(Result.isConstant() && isa<ConstantInt>(Result.getConstant())) && + "ConstantInt value must be represented as constantrange"); return ConstantRange(Width, /*isFullSet=*/true); } @@ -1536,7 +1572,7 @@ Constant *LazyValueInfo::getConstantOnEdge(Value *V, BasicBlock *FromBB, Instruction *CxtI) { const DataLayout &DL = FromBB->getModule()->getDataLayout(); LVILatticeVal Result = - getCache(PImpl, AC, &DL, DT).getValueOnEdge(V, FromBB, ToBB, CxtI); + getImpl(PImpl, AC, &DL, DT).getValueOnEdge(V, FromBB, ToBB, CxtI); if (Result.isConstant()) return Result.getConstant(); @@ -1583,8 +1619,8 @@ static LazyValueInfo::Tristate getPredicateResult(unsigned Pred, Constant *C, } // Handle more complex predicates. - ConstantRange TrueValues = - ICmpInst::makeConstantRange((ICmpInst::Predicate)Pred, CI->getValue()); + ConstantRange TrueValues = ConstantRange::makeExactICmpRegion( + (ICmpInst::Predicate)Pred, CI->getValue()); if (TrueValues.contains(CR)) return LazyValueInfo::True; if (TrueValues.inverse().contains(CR)) @@ -1624,7 +1660,7 @@ LazyValueInfo::getPredicateOnEdge(unsigned Pred, Value *V, Constant *C, Instruction *CxtI) { const DataLayout &DL = FromBB->getModule()->getDataLayout(); LVILatticeVal Result = - getCache(PImpl, AC, &DL, DT).getValueOnEdge(V, FromBB, ToBB, CxtI); + getImpl(PImpl, AC, &DL, DT).getValueOnEdge(V, FromBB, ToBB, CxtI); return getPredicateResult(Pred, C, Result, DL, TLI); } @@ -1644,7 +1680,7 @@ LazyValueInfo::getPredicateAt(unsigned Pred, Value *V, Constant *C, return LazyValueInfo::True; } const DataLayout &DL = CxtI->getModule()->getDataLayout(); - LVILatticeVal Result = getCache(PImpl, AC, &DL, DT).getValueAt(V, CxtI); + LVILatticeVal Result = getImpl(PImpl, AC, &DL, DT).getValueAt(V, CxtI); Tristate Ret = getPredicateResult(Pred, C, Result, DL, TLI); if (Ret != Unknown) return Ret; @@ -1703,7 +1739,7 @@ LazyValueInfo::getPredicateAt(unsigned Pred, Value *V, Constant *C, } 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 @@ -1734,13 +1770,13 @@ void LazyValueInfo::threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc, BasicBlock *NewSucc) { if (PImpl) { const DataLayout &DL = PredBB->getModule()->getDataLayout(); - getCache(PImpl, AC, &DL, DT).threadEdge(PredBB, OldSucc, NewSucc); + getImpl(PImpl, AC, &DL, DT).threadEdge(PredBB, OldSucc, NewSucc); } } void LazyValueInfo::eraseBlock(BasicBlock *BB) { if (PImpl) { const DataLayout &DL = BB->getModule()->getDataLayout(); - getCache(PImpl, AC, &DL, DT).eraseBlock(BB); + getImpl(PImpl, AC, &DL, DT).eraseBlock(BB); } } |
