[LVI] Make results independent of query order (WIP)

[nikic]

Summary

Related to D69686. Previously LVI broke cycles as they occurred, by assuming an overdefined result if pushBlockValue() failed. This means that the result depends on the query order, as this may start (and correspondingly break) the cycle at different points.

This patch proposes to instead break cycles at back-edges, so that the results computed by LVI are fixed by the control flow structure and do not depend on query order. We assume that the block value coming from the backedge is overdefined and only use any potential edge-local value in that case. This gives LVI a well-defined acyclic dependency graph.

This is a prototype implementation to get some feedback. The main problem is that right now, I'm aggressively clearing the backedge cache if any CFG change occurs. This might be expensive and it would be better to do more fine-grained updates. Not sure how hard that would be.

Another unfortunate bit is that we still need to check for cycles in pushBlockValue(), due to the degenerate case of unreachable basic blocks, which may contain self-referencing instructions.

[nikic]

Any feedback on the general idea here?

[nikic]

Rebase and use Optional.

[lebedev.ri]

No idea who is comfortable/qualified doing LVI reviews, but that isn't me.

[nikic]

This is still a problem, but the solution isn't great and I don't plan to work on this in the near future.

llvm/lib/Analysis/LazyValueInfo.cpp

 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Analysis/LazyValueInfo.h"
 #include "llvm/ADT/DenseSet.h"
 #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"
 #include "llvm/Analysis/ValueLattice.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/AssemblyAnnotationWriter.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/ConstantRange.h"
struct BlockCacheEntryTy {
       // block have not been computed yet.
       Optional<DenseSet<AssertingVH<Value>>> DereferencedPointers;
     };
 
     /// Cached information per basic block.
     DenseMap<PoisoningVH<BasicBlock>, BlockCacheEntryTy> BlockCache;
     /// Set of value handles used to erase values from the cache on deletion.
     DenseSet<LVIValueHandle, DenseMapInfo<Value *>> ValueHandles;
+    /// Cache of back edges in function, used to break cycles.
+    Optional<DenseSet<std::pair<const BasicBlock *, const BasicBlock *>>>
+        BackEdges;
 
   public:
     void insertResult(Value *Val, BasicBlock *BB,
                       const ValueLatticeElement &Result) {
       auto &CacheEntry = BlockCache.try_emplace(BB).first->second;
       // Insert over-defined values into their own cache to reduce memory
       // overhead.
       if (Result.isOverdefined())
bool isPointerDereferencedInBlock(
           if (HandleIt == ValueHandles.end())
             ValueHandles.insert({ V, this });
         }
       }
 
       return CacheEntry.DereferencedPointers->count(V);
     }
 
+    bool isBackEdge(const BasicBlock *From, const BasicBlock *To);
+
     /// clear - Empty the cache.
     void clear() {
       BlockCache.clear();
       ValueHandles.clear();
+      BackEdges.reset();
     }
 
     /// 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);

 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) {
   BlockCache.erase(BB);
+
+  // TODO: Clear BackEdges less aggressively.
+  BackEdges.reset();
 }
 
 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
for (Value *V : ValsToClear) {
       // blocks successors too.
       changed = true;
     }
 
     if (!changed) continue;
 
     worklist.insert(worklist.end(), succ_begin(ToUpdate), succ_end(ToUpdate));
   }
+
+  // TODO: Clear BackEdges less aggressively.
+  BackEdges.reset();
 }
 
+bool LazyValueInfoCache::isBackEdge(const BasicBlock *From,
+                                    const BasicBlock *To) {
+  if (!BackEdges) {
+    SmallVector<std::pair<const BasicBlock *, const BasicBlock *>, 32> Edges;
+    FindFunctionBackedges(*To->getParent(), Edges);
+    BackEdges.emplace();
+    for (const auto &Edge : Edges)
+      BackEdges->insert(Edge);
+  }
+
+  return BackEdges->count(std::make_pair(From, To));
+}
 
 namespace {
 /// An assembly annotator class to print LazyValueCache information in
 /// comments.
 class LazyValueInfoImpl;
 class LazyValueInfoAnnotatedWriter : public AssemblyAnnotationWriter {
   LazyValueInfoImpl *LVIImpl;
   // While analyzing which blocks we can solve values for, we need the dominator
class LazyValueInfoImpl {
     SmallVector<std::pair<BasicBlock*, Value*>, 8> BlockValueStack;
 
     /// Keeps track of which block-value pairs are in BlockValueStack.
     DenseSet<std::pair<BasicBlock*, Value*> > BlockValueSet;
 
     /// Push BV onto BlockValueStack unless it's already in there.
     /// Returns true on success.
     bool pushBlockValue(const std::pair<BasicBlock *, Value *> &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");
       BlockValueStack.push_back(BV);
       return true;
     }
 
     AssumptionCache *AC;  ///< A pointer to the cache of @llvm.assume calls.
     const DataLayout &DL; ///< A mandatory DataLayout
     DominatorTree *DT;    ///< An optional DT pointer.
     DominatorTree *DisabledDT; ///< Stores DT if it's disabled.
 
   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
   // 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(ValueLatticeElement &Res, Value *Val,
                            BasicBlock *BB);
static bool getEdgeValueLocal(Value *Val, BasicBlock *BBFrom,
   return false;
 }
 
 /// 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 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<Constant>(Val)) {
     Result = ValueLatticeElement::get(VC);
     return true;
   }
 
   ValueLatticeElement LocalResult;
   if (!getEdgeValueLocal(Val, BBFrom, BBTo, LocalResult))
     // If we couldn't constrain the value on the edge, LocalResult doesn't
     // provide any information.
     LocalResult = ValueLatticeElement::getOverdefined();
 
   if (hasSingleValue(LocalResult)) {
     // Can't get any more precise here
     Result = LocalResult;
     return true;
   }
 
   if (!hasBlockValue(Val, BBFrom)) {
+    // 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;
   }
 
   // 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

 ValueLatticeElement LazyValueInfoImpl::
 getValueOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB,
                Instruction *CxtI) {
   LLVM_DEBUG(dbgs() << "LVI Getting edge value " << *V << " from '"
                     << FromBB->getName() << "' to '" << ToBB->getName()
                     << "'\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?");
   }
 
   LLVM_DEBUG(dbgs() << "  Result = " << Result << "\n");
   return Result;
 }
 

llvm/test/Analysis/LazyValueAnalysis/lvi-after-jumpthreading.ll

 ; CHECK-LABEL: entry:
 ; CHECK-NEXT:    ; LatticeVal for: 'i32 %n' is: overdefined
 ; CHECK-NEXT: br label %loop
 entry:
   br label %loop
 
 ; 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]
 ; CHECK-NEXT:    ; LatticeVal for: '  %iv2 = phi i32 [ %n, %entry ], [ %iv2.next, %backedge ]' in BB: '%loop' is: overdefined
 ; CHECK-DAG:     ; LatticeVal for: '  %iv2 = phi i32 [ %n, %entry ], [ %iv2.next, %backedge ]' in BB: '%backedge' is: constantrange<1, -2147483648>
 ; CHECK-DAG:     ; LatticeVal for: '  %iv2 = phi i32 [ %n, %entry ], [ %iv2.next, %backedge ]' in BB: '%exit' is: overdefined
 ; CHECK-NEXT:  %iv2 = phi i32 [ %n, %entry ], [ %iv2.next, %backedge ]
   %iv2 = phi i32 [%n, %entry], [%iv2.next, %backedge]

 ; CHECK-DAG:     ; LatticeVal for: '  %cnd = and i1 %cnd1, %cnd2' in BB: '%backedge' is: constantrange<-1, 0>
 ; CHECK-DAG:     ; LatticeVal for: '  %cnd = and i1 %cnd1, %cnd2' in BB: '%exit' is: overdefined
 ; CHECK-NEXT:  %cnd = and i1 %cnd1, %cnd2
   %cnd = and i1 %cnd1, %cnd2
   br i1 %cnd, label %backedge, label %exit
 
 ; 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
   %iv2.next = sub nsw i32 %iv2, 1
 ; CHECK:         ; LatticeVal for: '  %cont1 = icmp slt i32 %iv.next, 400' in BB: '%backedge' is: overdefined
 ; CHECK-NEXT:  %cont1 = icmp slt i32 %iv.next, 400
   %cont1 = icmp slt i32 %iv.next, 400
 ; CHECK-NEXT:    ; LatticeVal for: '  %cont2 = icmp sgt i32 %iv2.next, 0' in BB: '%backedge' is: overdefined