[LVI Printer] Rely on the LVI analysis functions rather than the LVI cache

[anna]

Summary

LVIPrinter pass was previously relying on the LVICache. We now directly call the
the LVI functions which solves the value if the LVI information is not already
available in the cache. This has 2 benefits over the printing of LVI cache:

1. higher coverage (i.e. catches errors) in LVI code paths.
2. relies on the core functions, and not dependent on the LVI cache (which may

be scrapped at some point).
It would still catch any cache invalidation errors, since we first go through
the cache.

*Thanks to Philip for this suggestion, instead of relying on LVI cache for printing*

[anna]

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

59 ↗

(On Diff #95481)

I will add this test in a follow up functional change to LVI code itself: change LVI result and remove an assert that triggers when we call getValueInBlock(%iv2.next, loop). This seems a valid call because %iv2.next is used in the basic block loop, which means it's already defined. When printing LVI for iv2.next at block loop, we currently fail on the assert in:

bool LazyValueInfoImpl::solveBlockValueNonLocal(..){
if (BB == &BB->getParent()->getEntryBlock()) {
    assert(isa<Argument>(Val) && "Unknown live-in to the entry block");
}

The assert makes sense (call solveBlock for values in entry block works only iff it is defined in the entry block OR is a function argument). However, LVI::solve function for (iv2.next, loop) recurses over the predecessors of the loop block, and this includes the entry block.

Note: We don't trigger this solve in the Jumpthreading or CVP usage of LVI. But it seems a perfectly reasonable solve to trigger.

[sanjoy]

lib/Analysis/LazyValueInfo.cpp

1904 ↗

(On Diff #95481)

Is it legal to call getValueInBlock(I, BB) if I does not domiate BB? If it isn't legal, then the code above will not do the right thing in cases like:

  br cond, L, R

L:
  %v = def
  br R

R:

since you'll end up asking getValueInBlock(%v, R) when %v does not dominate R.

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

59 ↗

(On Diff #95481)

I'm not sure if it is correct to say that %iv2.next is used in %loop -- a PHI node's use counts as a use at the end of the incoming block.

[anna]

lib/Analysis/LazyValueInfo.cpp

1904 ↗

(On Diff #95481)

If I does not dominate BB, we fail on an unrelated assert (because we reach the entry basic block, where the only values whose LVI can be calculated are arguments and values defined in the block). It actually boils down to the implicit assumption that we can't calculate getValueInBlock if I does not dominate BB.
I would think that we return undefined for the example you've above, rather than fail on the assert.

This is the same assertion failure for the test2.

I'll make this a stricter requirement, rather than depend on successors.

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

59 ↗

(On Diff #95481)

Agreed. Phi-nodes need to be treated differently.

[anna]

Use dominator information to identify which blocks we can solve for.
Addressed review comments.

[anna]

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

59 ↗

(On Diff #95481)

Added the test back since PhiNode uses are handled separately (only consider phi uses that dominate the def of the value).

[anna]

ping

[anna]

ping2.

[reames]

LGTM w/required changes.

lib/Analysis/LazyValueInfo.cpp

1871 ↗

(On Diff #96399)

The const_casts looks concerning here. We should be able to walk all the function/arg stuff without them; at most we need to cast before invoking the LVI interface.

1901 ↗

(On Diff #96399)

I'd print the unknown values too for ease of testing and consistency.

llvm/trunk/include/llvm/Analysis/LazyValueInfo.h

public:
 
   /// Inform the analysis cache that we have threaded an edge from
   /// PredBB to OldSucc to be from PredBB to NewSucc instead.
   void threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc, BasicBlock *NewSucc);
 
   /// Inform the analysis cache that we have erased a block.
   void eraseBlock(BasicBlock *BB);
 
-  /// Print the \LazyValueInfoCache.
-  void printCache(Function &F, raw_ostream &OS);
+  /// Print the \LazyValueInfo Analysis.
+  /// We pass in the DTree that is required for identifying which basic blocks
+  /// we can solve/print for, in the LVIPrinter. The DT is optional
+  /// in LVI, so we need to pass it here as an argument.
+  void printLVI(Function &F, DominatorTree &DTree, raw_ostream &OS);
 
   // For old PM pass. Delete once LazyValueInfoWrapperPass is gone.
   void releaseMemory();
 
   /// Handle invalidation events in the new pass manager.
   bool invalidate(Function &F, const PreservedAnalyses &PA,
                   FunctionAnalysisManager::Invalidator &Inv);
 };

llvm/trunk/lib/Analysis/LazyValueInfo.cpp

struct LVIValueHandle final : public CallbackVH {
     }
   };
 } // end anonymous namespace
 
 namespace {
   /// This is the cache kept by LazyValueInfo which
   /// maintains information about queries across the clients' queries.
   class LazyValueInfoCache {
-    friend class LazyValueInfoAnnotatedWriter;
     /// This is all of the cached block information for exactly one Value*.
     /// The entries are sorted by the BasicBlock* of the
     /// entries, allowing us to do a lookup with a binary search.
     /// Over-defined lattice values are recorded in OverDefinedCache to reduce
     /// memory overhead.
     struct ValueCacheEntryTy {
       ValueCacheEntryTy(Value *V, LazyValueInfoCache *P) : Handle(V, P) {}
       LVIValueHandle Handle;
       SmallDenseMap<PoisoningVH<BasicBlock>, LVILatticeVal, 4> BlockVals;
     };
 
     /// This tracks, on a per-block basis, the set of values that are
     /// over-defined at the end of that block.
     typedef DenseMap<PoisoningVH<BasicBlock>, SmallPtrSet<Value *, 4>>
         OverDefinedCacheTy;
     /// Keep track of all blocks that we have ever seen, so we
     /// don't spend time removing unused blocks from our caches.
     DenseSet<PoisoningVH<BasicBlock> > SeenBlocks;
 
-  protected:
     /// This is all of the cached information for all values,
     /// mapped from Value* to key information.
     DenseMap<Value *, std::unique_ptr<ValueCacheEntryTy>> ValueCache;
     OverDefinedCacheTy OverDefinedCache;
 
 
   public:
     void insertResult(Value *Val, BasicBlock *BB, const LVILatticeVal &Result) {
LVILatticeVal getCachedValueInfo(Value *V, BasicBlock *BB) const {
       if (I == ValueCache.end())
         return LVILatticeVal();
       auto BBI = I->second->BlockVals.find(BB);
       if (BBI == I->second->BlockVals.end())
         return LVILatticeVal();
       return BBI->second;
     }
 
-    void printCache(Function &F, raw_ostream &OS);
     /// 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;
   };
 }
 
-
-namespace {
-
-  /// An assembly annotator class to print LazyValueCache information in
-  /// comments.
-  class LazyValueInfoAnnotatedWriter : public AssemblyAnnotationWriter {
-    const LazyValueInfoCache* LVICache;
-
-  public:
-    LazyValueInfoAnnotatedWriter(const LazyValueInfoCache *L) : LVICache(L) {}
-
-    virtual void emitBasicBlockStartAnnot(const BasicBlock *BB,
-                                          formatted_raw_ostream &OS) {
-      auto ODI = LVICache->OverDefinedCache.find(const_cast<BasicBlock*>(BB));
-      if (ODI == LVICache->OverDefinedCache.end())
-        return;
-      OS << "; OverDefined values for block are: \n";
-      for (auto *V : ODI->second)
-        OS << ";" << *V << "\n";
-
-      // Find if there are latticevalues defined for arguments of the function.
-      auto *F = const_cast<Function *>(BB->getParent());
-      for (auto &Arg : F->args()) {
-        auto VI = LVICache->ValueCache.find_as(&Arg);
-        if (VI == LVICache->ValueCache.end())
-          continue;
-        auto BBI = VI->second->BlockVals.find(const_cast<BasicBlock *>(BB));
-        if (BBI != VI->second->BlockVals.end())
-          OS << "; CachedLatticeValue for: '" << *VI->first << "' is: '"
-             << BBI->second << "'\n";
-      }
-    }
-
-    virtual void emitInstructionAnnot(const Instruction *I,
-                                      formatted_raw_ostream &OS) {
-
-      auto VI = LVICache->ValueCache.find_as(const_cast<Instruction *>(I));
-      if (VI == LVICache->ValueCache.end())
-        return;
-      OS << "; CachedLatticeValues for: '" << *VI->first << "'\n";
-      for (auto &BV : VI->second->BlockVals) {
-        OS << "; at beginning of BasicBlock: '";
-        BV.first->printAsOperand(OS, false);
-        OS << "' LatticeVal: '" << BV.second << "' \n";
-      }
-    }
-};
-}
-
-void LazyValueInfoCache::printCache(Function &F, raw_ostream &OS) {
-  LazyValueInfoAnnotatedWriter Writer(this);
-  F.print(OS, &Writer);
-
-}
-
 void LazyValueInfoCache::eraseValue(Value *V) {
   for (auto I = OverDefinedCache.begin(), E = OverDefinedCache.end(); I != E;) {
     // Copy and increment the iterator immediately so we can erase behind
     // ourselves.
     auto Iter = I++;
     SmallPtrSetImpl<Value *> &ValueSet = Iter->second;
     ValueSet.erase(V);
     if (ValueSet.empty())
while (!worklist.empty()) {
     }
 
     if (!changed) continue;
 
     worklist.insert(worklist.end(), succ_begin(ToUpdate), succ_end(ToUpdate));
   }
 }
 
+
+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
+  // information. Since this is an optional parameter in LVI, we require this
+  // DomTreeAnalysis pass in the printer pass, and pass the dominator
+  // tree to the LazyValueInfoAnnotatedWriter.
+  DominatorTree &DT;
+
+public:
+  LazyValueInfoAnnotatedWriter(LazyValueInfoImpl *L, DominatorTree &DTree)
+      : LVIImpl(L), DT(DTree) {}
+
+  virtual void emitBasicBlockStartAnnot(const BasicBlock *BB,
+                                        formatted_raw_ostream &OS);
+
+  virtual void emitInstructionAnnot(const Instruction *I,
+                                    formatted_raw_ostream &OS);
+};
+}
 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;
public:
     LVILatticeVal getValueOnEdge(Value *V, BasicBlock *FromBB,BasicBlock *ToBB,
                                  Instruction *CxtI = nullptr);
 
     /// Complete flush all previously computed values
     void clear() {
       TheCache.clear();
     }
 
-    /// Printing the LazyValueInfoCache.
-    void printCache(Function &F, raw_ostream &OS) {
-       TheCache.printCache(F, OS);
+    /// Printing the LazyValueInfo Analysis.
+    void printLVI(Function &F, DominatorTree &DTree, raw_ostream &OS) {
+        LazyValueInfoAnnotatedWriter Writer(this, DTree);
+        F.print(OS, &Writer);
     }
 
     /// This is part of the update interface to inform the cache
     /// that a block has been deleted.
     void eraseBlock(BasicBlock *BB) {
       TheCache.eraseBlock(BB);
     }
 
     /// 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 LazyValueInfoImpl::solve() {
   SmallVector<std::pair<BasicBlock *, Value *>, 8> StartingStack(
       BlockValueStack.begin(), BlockValueStack.end());
 
   unsigned processedCount = 0;
   while (!BlockValueStack.empty()) {
     processedCount++;
     // Abort if we have to process too many values to get a result for this one.

 void LazyValueInfo::eraseBlock(BasicBlock *BB) {
   if (PImpl) {
     const DataLayout &DL = BB->getModule()->getDataLayout();
     getImpl(PImpl, AC, &DL, DT).eraseBlock(BB);
   }
 }
 
 
-void LazyValueInfo::printCache(Function &F, raw_ostream &OS) {
+void LazyValueInfo::printLVI(Function &F, DominatorTree &DTree, raw_ostream &OS) {
   if (PImpl) {
-    getImpl(PImpl, AC, DL, DT).printCache(F, OS);
-  }
+    getImpl(PImpl, AC, DL, DT).printLVI(F, DTree, OS);
+  }
+}
+
+// Print the LVI for the function arguments at the start of each basic block.
+void LazyValueInfoAnnotatedWriter::emitBasicBlockStartAnnot(
+    const BasicBlock *BB, formatted_raw_ostream &OS) {
+  // Find if there are latticevalues defined for arguments of the function.
+  auto *F = BB->getParent();
+  for (auto &Arg : F->args()) {
+    LVILatticeVal Result = LVIImpl->getValueInBlock(
+        const_cast<Argument *>(&Arg), const_cast<BasicBlock *>(BB));
+    if (Result.isUndefined())
+      continue;
+    OS << "; LatticeVal for: '" << Arg << "' is: " << Result << "\n";
+  }
+
+// This function prints the LVI analysis for the instruction I at the beginning
+// of various basic blocks. It relies on calculated values that are stored in
+// the LazyValueInfoCache, and in the absence of cached values, recalculte the
+// LazyValueInfo for `I`, and print that info.
+void LazyValueInfoAnnotatedWriter::emitInstructionAnnot(
+    const Instruction *I, formatted_raw_ostream &OS) {
+
+  auto *ParentBB = I->getParent();
+  SmallPtrSet<const BasicBlock*, 16> BlocksContainingLVI;
+  // We can generate (solve) LVI values only for blocks that are dominated by
+  // the I's parent. However, to avoid generating LVI for all dominating blocks,
+  // that contain redundant/uninteresting information, we print LVI for
+  // blocks that may use this LVI information (such as immediate successor
+  // blocks, and blocks that contain uses of `I`).
+  auto printResult = [&](const BasicBlock *BB) {
+    if (!BlocksContainingLVI.insert(BB).second)
+      return;
+    LVILatticeVal Result = LVIImpl->getValueInBlock(
+        const_cast<Instruction *>(I), const_cast<BasicBlock *>(BB));
+      OS << "; LatticeVal for: '" << *I << "' in BB: '";
+      BB->printAsOperand(OS, false);
+      OS << "' is: " << Result << "\n";
+  };
+
+  printResult(ParentBB);
+  // Print the LVI analysis results for the the immediate successor blocks, that
+  // are dominated by `ParentBB`.
+  for (auto *BBSucc : successors(ParentBB))
+    if (DT.dominates(ParentBB, BBSucc))
+      printResult(BBSucc);
+
+  // Print LVI in blocks where `I` is used.
+  for (auto *U : I->users())
+    if (auto *UseI = dyn_cast<Instruction>(U))
+      if (!isa<PHINode>(UseI) || DT.dominates(ParentBB, UseI->getParent()))
+        printResult(UseI->getParent());
+
 }
 
 namespace {
 // Printer class for LazyValueInfo results.
 class LazyValueInfoPrinter : public FunctionPass {
 public:
   static char ID; // Pass identification, replacement for typeid
   LazyValueInfoPrinter() : FunctionPass(ID) {
     initializeLazyValueInfoPrinterPass(*PassRegistry::getPassRegistry());
   }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.setPreservesAll();
     AU.addRequired<LazyValueInfoWrapperPass>();
+    AU.addRequired<DominatorTreeWrapperPass>();
   }
 
+  // Get the mandatory dominator tree analysis and pass this in to the
+  // LVIPrinter. We cannot rely on the LVI's DT, since it's optional.
   bool runOnFunction(Function &F) override {
     dbgs() << "LVI for function '" << F.getName() << "':\n";
     auto &LVI = getAnalysis<LazyValueInfoWrapperPass>().getLVI();
-    LVI.printCache(F, dbgs());
+    auto &DTree = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
+    LVI.printLVI(F, DTree, dbgs());
     return false;
   }
 };
 }
 
 char LazyValueInfoPrinter::ID = 0;
 INITIALIZE_PASS_BEGIN(LazyValueInfoPrinter, "print-lazy-value-info",
                 "Lazy Value Info Printer Pass", false, false)
 INITIALIZE_PASS_DEPENDENCY(LazyValueInfoWrapperPass)
 INITIALIZE_PASS_END(LazyValueInfoPrinter, "print-lazy-value-info",
                 "Lazy Value Info Printer Pass", false, false)

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

 ; RUN: opt < %s -jump-threading -print-lazy-value-info -disable-output 2>&1 | FileCheck %s
 
 ; Testing LVI cache after jump-threading
 
 ; Jump-threading transforms the IR below to one where
 ; loop and backedge basic blocks are merged into one.
 ; basic block (named backedge) with the branch being:
 ; %cont = icmp slt i32 %iv.next, 400
 ; br i1 %cont, label %backedge, label %exit
 define i8 @test1(i32 %a, i32 %length) {
 ; CHECK-LABEL: LVI for function 'test1':
 entry:
+; CHECK-LABEL: entry:
+; CHECK-NEXT:    ; LatticeVal for: 'i32 %a' is: overdefined
+; CHECK-NEXT:    ; LatticeVal for: 'i32 %length' is: overdefined
   br label %loop
+
 ; CHECK-LABEL: backedge:
-; CHECK-NEXT: ; CachedLatticeValues for: '  %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]'
-; CHECK-DAG: ; at beginning of BasicBlock: '%backedge' LatticeVal: 'constantrange<0, 400>'
-; CHECK-NEXT: %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]
-; CHECK-NEXT: ; CachedLatticeValues for: '  %iv.next = add nsw i32 %iv, 1'
-; CHECK-NEXT: ; at beginning of BasicBlock: '%backedge' LatticeVal: 'constantrange<1, 401>'
-; CHECK-NEXT: %iv.next = add nsw i32 %iv, 1
+; CHECK-NEXT:     ; LatticeVal for: 'i32 %a' is: overdefined
+; CHECK-NEXT:     ; LatticeVal for: 'i32 %length' is: overdefined
+; CHECK-NEXT:     ; LatticeVal for: '  %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]' in BB: '%backedge' is: constantrange<0, 400>
+; CHECK-NEXT:     ; LatticeVal for: '  %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]' in BB: '%exit' is: constantrange<399, 400>
+; CHECK-NEXT:  %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]
+; CHECK-NEXT:     ; LatticeVal for: '  %iv.next = add nsw i32 %iv, 1' in BB: '%backedge' is: constantrange<1, 401>
+; CHECK-NEXT:     ; LatticeVal for: '  %iv.next = add nsw i32 %iv, 1' in BB: '%exit' is: constantrange<400, 401>
+; CHECK-NEXT:  %iv.next = add nsw i32 %iv, 1
+; CHECK-NEXT:     ; LatticeVal for: '  %cont = icmp slt i32 %iv.next, 400' in BB: '%backedge' is: overdefined
+; CHECK-NEXT:     ; LatticeVal for: '  %cont = icmp slt i32 %iv.next, 400' in BB: '%exit' is: constantrange<0, -1>
 ; CHECK-NEXT:  %cont = icmp slt i32 %iv.next, 400
-; CHECK-NEXT: br i1 %cont, label %backedge, label %exit
-
 ; CHECK-NOT: loop
 loop:
   %iv = phi i32 [0, %entry], [%iv.next, %backedge]
   %cnd = icmp sge i32 %iv, 0
   br i1 %cnd, label %backedge, label %exit
 
 backedge:
   %iv.next = add nsw i32 %iv, 1
   %cont = icmp slt i32 %iv.next, 400
   br i1 %cont, label %loop, label %exit
 
 exit:
   ret i8 0
 }
 
-
 ; Here JT does not transform the code, but LVICache is populated during the processing of blocks.
 define i8 @test2(i32 %n) {
 ; CHECK-LABEL: LVI for function 'test2':
 ; CHECK-LABEL: entry:
-; CHECK-LABEL: ; OverDefined values for block are:
-; CHECK-NEXT: ;i32 %n
+; CHECK-NEXT:    ; LatticeVal for: 'i32 %n' is: overdefined
 ; CHECK-NEXT: br label %loop
 entry:
   br label %loop
 
 ; CHECK-LABEL: loop:
-; CHECK-LABEL: ; OverDefined values for block are:
-; CHECK-NEXT: ; %iv2 = phi i32 [ %n, %entry ], [ %iv2.next, %backedge ]
-; CHECK-NEXT: ; CachedLatticeValues for: '  %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]'
-; CHECK-DAG: ; at beginning of BasicBlock: '%loop' LatticeVal: 'constantrange<0, -2147483647>'
-; CHECK-DAG: ; at beginning of BasicBlock: '%backedge' LatticeVal: 'constantrange<0, -2147483648>'
-; CHECK-NEXT: %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]
-; CHECK: %cnd = and i1 %cnd1, %cnd2
-; CHECK: br i1 %cnd, label %backedge, label %exit
+; 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, -2147483647>
+; 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, -2147483647>
+; 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-NEXT:    ; LatticeVal for: '  %cnd1 = icmp sge i32 %iv, 0' in BB: '%loop' is: overdefined
+; CHECK-DAG:     ; LatticeVal for: '  %cnd1 = icmp sge i32 %iv, 0' in BB: '%backedge' is: overdefined
+; CHECK-DAG:     ; LatticeVal for: '  %cnd1 = icmp sge i32 %iv, 0' in BB: '%exit' is: overdefined
+; CHECK-NEXT:  %cnd1 = icmp sge i32 %iv, 0
   %cnd1 = icmp sge i32 %iv, 0
   %cnd2 = icmp sgt i32 %iv2, 0
+; CHECK:       %cnd2 = icmp sgt i32 %iv2, 0
+; CHECK:         ; LatticeVal for: '  %cnd = and i1 %cnd1, %cnd2' in BB: '%loop' is: overdefined
+; 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: ; CachedLatticeValues for: '  %iv.next = add nsw i32 %iv, 1'
-; CHECK-NEXT: ; at beginning of BasicBlock: '%backedge' LatticeVal: 'constantrange<1, -2147483647>'
-; CHECK-NEXT: %iv.next = add nsw i32 %iv, 1
-; CHECK-NEXT: %iv2.next = sub nsw i32 %iv2, 1
-; CHECK: %cont = and i1 %cont1, %cont2
-; CHECK: br i1 %cont, label %loop, label %exit
+; 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, -2147483647>
+; 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
+; CHECK-NEXT:  %cont2 = icmp sgt i32 %iv2.next, 0
   %cont2 = icmp sgt i32 %iv2.next, 0
+; CHECK-NEXT:    ; LatticeVal for: '  %cont = and i1 %cont1, %cont2' in BB: '%backedge' is: overdefined
+; CHECK-NEXT:  %cont = and i1 %cont1, %cont2
   %cont = and i1 %cont1, %cont2
   br i1 %cont, label %loop, label %exit
 
 exit:
   ret i8 0
 }