-//===- LazyValueInfo.cpp - Value constraint analysis ----------------------===//
+//===- LazyValueInfo.cpp - Value constraint analysis ------------*- C++ -*-===//
//
// The LLVM Compiler Infrastructure
//
typedef std::pair<AssertingVH<BasicBlock>, Value*> OverDefinedPairTy;
SmallVector<OverDefinedPairTy, 4> ToErase;
- for (DenseSet<OverDefinedPairTy>::iterator
- I = Parent->OverDefinedCache.begin(),
- E = Parent->OverDefinedCache.end();
- I != E; ++I) {
- if (I->second == getValPtr())
- ToErase.push_back(*I);
- }
-
- for (SmallVectorImpl<OverDefinedPairTy>::iterator I = ToErase.begin(),
- E = ToErase.end(); I != E; ++I)
- Parent->OverDefinedCache.erase(*I);
+ for (const OverDefinedPairTy &P : Parent->OverDefinedCache)
+ if (P.second == getValPtr())
+ ToErase.push_back(P);
+ for (const OverDefinedPairTy &P : ToErase)
+ Parent->OverDefinedCache.erase(P);
// This erasure deallocates *this, so it MUST happen after we're done
// using any and all members of *this.
SeenBlocks.erase(I);
SmallVector<OverDefinedPairTy, 4> ToErase;
- for (DenseSet<OverDefinedPairTy>::iterator I = OverDefinedCache.begin(),
- E = OverDefinedCache.end(); I != E; ++I) {
- if (I->first == BB)
- ToErase.push_back(*I);
- }
-
- for (SmallVectorImpl<OverDefinedPairTy>::iterator I = ToErase.begin(),
- E = ToErase.end(); I != E; ++I)
- OverDefinedCache.erase(*I);
+ for (const OverDefinedPairTy& P : OverDefinedCache)
+ if (P.first == BB)
+ ToErase.push_back(P);
+ for (const OverDefinedPairTy &P : ToErase)
+ OverDefinedCache.erase(P);
for (std::map<LVIValueHandle, ValueCacheEntryTy>::iterator
I = ValueCache.begin(), E = ValueCache.end(); I != E; ++I)
// 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 exist, passing a bool to indicate if the
- // cache needs updating, i.e. if we have solve a new value or not.
+ // 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);
- // Once this BB is encountered, Val's value for this BB will not be Undefined
- // any longer. When we encounter this BB again, if Val's value is Overdefined,
- // we need to compute its value again.
- //
- // For example, considering this control flow,
- // BB1->BB2, BB1->BB3, BB2->BB3, BB2->BB4
- //
- // Suppose we have "icmp slt %v, 0" in BB1, and "icmp sgt %v, 0" in BB3. At
- // the very beginning, when analyzing edge BB2->BB3, we don't know %v's value
- // in BB2, and the data flow algorithm tries to compute BB2's predecessors, so
- // then we know %v has negative value on edge BB1->BB2. And then we return to
- // check BB2 again, and at this moment BB2 has Overdefined value for %v in
- // BB2. So we should have to follow data flow propagation algorithm to get the
- // value on edge BB1->BB2 propagated to BB2, and finally %v on BB2 has a
- // constant range describing a negative value.
-
- if (!BBLV.isUndefined() && !BBLV.isOverdefined()) {
+ 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
- // OverDefinedCahce. The cache will have been properly updated
+ // OverDefinedCache. The cache will have been properly updated
// whenever the cached value was inserted.
ODCacheUpdater.markResult(false);
return true;
// If 'GetUnderlyingObject' didn't converge, skip it. It won't converge
// inside InstructionDereferencesPointer either.
if (UnderlyingVal == GetUnderlyingObject(UnderlyingVal, nullptr, 1)) {
- for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
- BI != BE; ++BI) {
- if (InstructionDereferencesPointer(BI, UnderlyingVal)) {
+ for (Instruction &I : *BB) {
+ if (InstructionDereferencesPointer(&I, UnderlyingVal)) {
NotNull = true;
break;
}
BasicBlock *PhiBB = PN->getIncomingBlock(i);
Value *PhiVal = PN->getIncomingValue(i);
LVILatticeVal EdgeResult;
+ // Note that we can provide PN as the context value to getEdgeValue, even
+ // though the results will be cached, because PN is the value being used as
+ // the cache key in the caller.
EdgesMissing |= !getEdgeValue(PhiVal, PhiBB, BB, EdgeResult, PN);
if (EdgesMissing)
continue;
LVILatticeVal &Result,
bool isTrueDest = true);
-// If we can determine a constant range for the value Val at the context
+// If we can determine a constant range for the value Val in the context
// provided by the instruction BBI, then merge it into BBLV. If we did find a
// constant range, return true.
-void LazyValueInfoCache::mergeAssumeBlockValueConstantRange(
- Value *Val, LVILatticeVal &BBLV, Instruction *BBI) {
+void LazyValueInfoCache::mergeAssumeBlockValueConstantRange(Value *Val,
+ LVILatticeVal &BBLV,
+ Instruction *BBI) {
BBI = BBI ? BBI : dyn_cast<Instruction>(Val);
if (!BBI)
return;
unsigned BitWidth = Val->getType()->getIntegerBitWidth();
ConstantRange EdgesVals(BitWidth, DefaultCase/*isFullSet*/);
- for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end();
- i != e; ++i) {
+ for (SwitchInst::CaseIt i : SI->cases()) {
ConstantRange EdgeVal(i.getCaseValue()->getValue());
if (DefaultCase) {
// It is possible that the default destination is the destination of
if (getEdgeValueLocal(Val, BBFrom, BBTo, Result)) {
if (!Result.isConstantRange() ||
- Result.getConstantRange().getSingleElement())
+ Result.getConstantRange().getSingleElement())
return true;
// FIXME: this check should be moved to the beginning of the function when
// Try to intersect ranges of the BB and the constraint on the edge.
LVILatticeVal InBlock = getBlockValue(Val, BBFrom);
+ mergeAssumeBlockValueConstantRange(Val, InBlock, BBFrom->getTerminator());
+ // See note on the use of the CxtI with mergeAssumeBlockValueConstantRange,
+ // and caching, below.
mergeAssumeBlockValueConstantRange(Val, InBlock, CxtI);
if (!InBlock.isConstantRange())
return true;
return false;
}
- // if we couldn't compute the value on the edge, use the value from the BB
+ // If we couldn't compute the value on the edge, use the value from the BB.
Result = getBlockValue(Val, BBFrom);
+ mergeAssumeBlockValueConstantRange(Val, Result, 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,
+ // but then the result is not cached.
mergeAssumeBlockValueConstantRange(Val, Result, CxtI);
return true;
}
// 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 dropped cached info
+ // 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.
worklist.push_back(OldSucc);
DenseSet<Value*> ClearSet;
- for (DenseSet<OverDefinedPairTy>::iterator I = OverDefinedCache.begin(),
- E = OverDefinedCache.end(); I != E; ++I) {
- if (I->first == OldSucc)
- ClearSet.insert(I->second);
- }
+ for (OverDefinedPairTy &P : OverDefinedCache)
+ if (P.first == OldSucc)
+ ClearSet.insert(P.second);
// 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 (DenseSet<Value*>::iterator I = ClearSet.begin(), E = ClearSet.end();
- I != E; ++I) {
+ for (Value *V : ClearSet) {
// If a value was marked overdefined in OldSucc, and is here too...
DenseSet<OverDefinedPairTy>::iterator OI =
- OverDefinedCache.find(std::make_pair(ToUpdate, *I));
+ OverDefinedCache.find(std::make_pair(ToUpdate, V));
if (OI == OverDefinedCache.end()) continue;
// Remove it from the caches.
- ValueCacheEntryTy &Entry = ValueCache[LVIValueHandle(*I, this)];
+ ValueCacheEntryTy &Entry = ValueCache[LVIValueHandle(V, this)];
ValueCacheEntryTy::iterator CI = Entry.find(ToUpdate);
assert(CI != Entry.end() && "Couldn't find entry to update?");
DataLayoutPass *DLP = getAnalysisIfAvailable<DataLayoutPass>();
DL = DLP ? &DLP->getDataLayout() : nullptr;
+
TLI = &getAnalysis<TargetLibraryInfo>();
if (PImpl)