Index: llvm/lib/Analysis/LazyValueInfo.cpp =================================================================== --- llvm/lib/Analysis/LazyValueInfo.cpp +++ llvm/lib/Analysis/LazyValueInfo.cpp @@ -16,6 +16,7 @@ #include "llvm/ADT/Optional.h" #include "llvm/ADT/STLExtras.h" #include "llvm/Analysis/AssumptionCache.h" +#include "llvm/Analysis/CFG.h" #include "llvm/Analysis/ConstantFolding.h" #include "llvm/Analysis/InstructionSimplify.h" #include "llvm/Analysis/TargetLibraryInfo.h" @@ -181,6 +182,10 @@ /// dereferenced in the block (and thus non-null at the end of the block). PerBlockValueCacheTy DereferencedPointerCache; + /// Cache of back edges in function, used to break cycles. + SmallDenseSet> + BackEdges; + bool BackEdgesInitialized = false; public: void insertResult(Value *Val, BasicBlock *BB, @@ -240,12 +245,16 @@ return DereferencedPointerCache.try_emplace(BB); } + bool isBackEdge(const BasicBlock *From, const BasicBlock *To); + /// clear - Empty the cache. void clear() { SeenBlocks.clear(); ValueCache.clear(); OverDefinedCache.clear(); DereferencedPointerCache.clear(); + BackEdges.clear(); + BackEdgesInitialized = false; } /// Inform the cache that a given value has been deleted. @@ -294,6 +303,10 @@ // always clear the dereferenced pointer cache. DereferencedPointerCache.erase(BB); + // TODO: Clear BackEdges less aggressively. + BackEdges.clear(); + BackEdgesInitialized = false; + // Shortcut if we have never seen this block. DenseSet >::iterator I = SeenBlocks.find(BB); if (I == SeenBlocks.end()) @@ -362,8 +375,24 @@ worklist.insert(worklist.end(), succ_begin(ToUpdate), succ_end(ToUpdate)); } + + // TODO: Clear BackEdges less aggressively. + BackEdges.clear(); + BackEdgesInitialized = false; } +bool LazyValueInfoCache::isBackEdge(const BasicBlock *From, + const BasicBlock *To) { + if (!BackEdgesInitialized) { + SmallVector, 32> Edges; + FindFunctionBackedges(*To->getParent(), Edges); + for (const auto &Edge : Edges) + BackEdges.insert(Edge); + BackEdgesInitialized = true; + } + + return BackEdges.count(std::make_pair(From, To)); +} namespace { /// An assembly annotator class to print LazyValueCache information in @@ -408,8 +437,13 @@ /// Push BV onto BlockValueStack unless it's already in there. /// Returns true on success. bool pushBlockValue(const std::pair &BV) { - if (!BlockValueSet.insert(BV).second) + if (!BlockValueSet.insert(BV).second) { + // TODO: Can we avoid computing block values for unreachable blocks + // in a more principled manner? + assert((!DT || !DT->isReachableFromEntry(BV.first)) && + "Cycles may only occur in unreachable blocks"); return false; // It's already in the stack. + } LLVM_DEBUG(dbgs() << "PUSH: " << *BV.second << " in " << BV.first->getName() << "\n"); @@ -424,7 +458,8 @@ ValueLatticeElement getBlockValue(Value *Val, BasicBlock *BB); bool getEdgeValue(Value *V, BasicBlock *F, BasicBlock *T, - ValueLatticeElement &Result, Instruction *CxtI = nullptr); + ValueLatticeElement &Result, Instruction *CxtI = nullptr, + bool AllowBackEdges = false); bool hasBlockValue(Value *Val, BasicBlock *BB); // These methods process one work item and may add more. A false value @@ -1511,7 +1546,8 @@ bool LazyValueInfoImpl::getEdgeValue(Value *Val, BasicBlock *BBFrom, BasicBlock *BBTo, ValueLatticeElement &Result, - Instruction *CxtI) { + Instruction *CxtI, + bool AllowBackEdges) { // If already a constant, there is nothing to compute. if (Constant *VC = dyn_cast(Val)) { Result = ValueLatticeElement::get(VC); @@ -1531,10 +1567,17 @@ } if (!hasBlockValue(Val, BBFrom)) { - if (pushBlockValue(std::make_pair(BBFrom, Val))) - return false; + // Don't take block values from back-edges in order to break cyclic + // references. + if (AllowBackEdges || !TheCache.isBackEdge(BBFrom, BBTo)) + if (pushBlockValue(std::make_pair(BBFrom, Val))) + return false; + // No new information. Result = LocalResult; + // TODO: Why are the following intersections not performed if we don't + // have a block value? Wouldn't they also make sense if we only have the + // local edge value? return true; } @@ -1597,9 +1640,10 @@ << "'\n"); ValueLatticeElement Result; - if (!getEdgeValue(V, FromBB, ToBB, Result, CxtI)) { + if (!getEdgeValue(V, FromBB, ToBB, Result, CxtI, /* AllowBackEdges */ true)) { solve(); - bool WasFastQuery = getEdgeValue(V, FromBB, ToBB, Result, CxtI); + bool WasFastQuery = + getEdgeValue(V, FromBB, ToBB, Result, CxtI, /* AllowBackEdges */ true); (void)WasFastQuery; assert(WasFastQuery && "More work to do after problem solved?"); } Index: llvm/test/Analysis/LazyValueAnalysis/lvi-after-jumpthreading.ll =================================================================== --- llvm/test/Analysis/LazyValueAnalysis/lvi-after-jumpthreading.ll +++ llvm/test/Analysis/LazyValueAnalysis/lvi-after-jumpthreading.ll @@ -53,9 +53,9 @@ ; CHECK-LABEL: loop: ; CHECK-NEXT: ; LatticeVal for: 'i32 %n' is: overdefined -; CHECK-NEXT: ; LatticeVal for: ' %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]' in BB: '%loop' is: constantrange<0, 400> -; CHECK-DAG: ; LatticeVal for: ' %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]' in BB: '%backedge' is: constantrange<0, -2147483648> -; CHECK-DAG: ; LatticeVal for: ' %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]' in BB: '%exit' is: constantrange<0, -2147483648> +; CHECK-NEXT: ; LatticeVal for: ' %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]' in BB: '%loop' is: constantrange<-2147483648, 400> +; CHECK-DAG: ; LatticeVal for: ' %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]' in BB: '%backedge' is: constantrange<0, 400> +; CHECK-DAG: ; LatticeVal for: ' %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]' in BB: '%exit' is: constantrange<-2147483648, 400> ; CHECK-NEXT: %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ] loop: %iv = phi i32 [0, %entry], [%iv.next, %backedge] @@ -81,7 +81,7 @@ ; CHECK-LABEL: backedge: ; CHECK-NEXT: ; LatticeVal for: 'i32 %n' is: overdefined -; CHECK-NEXT: ; LatticeVal for: ' %iv.next = add nsw i32 %iv, 1' in BB: '%backedge' is: constantrange<1, -2147483648> +; CHECK-NEXT: ; LatticeVal for: ' %iv.next = add nsw i32 %iv, 1' in BB: '%backedge' is: constantrange<1, 401> ; CHECK-NEXT: %iv.next = add nsw i32 %iv, 1 backedge: %iv.next = add nsw i32 %iv, 1