[LVI] Add an LVI printer pass to capture test LVI cache after transformations

[anna]

Summary

Adding a printer pass for printing the LVI cache values after transformations
that use LVI.
This will help us in identifying cases where LVI
invariants are violated, or transforms that leave LVI in an incorrect state.
Right now, I have added two test cases to show that the printer pass is working.
I will be adding more test cases in a later change, once this change is
checked in upstream.

[apilipenko]

It's worth noting for others that the motivation for the change is a bug we found in JumpThreading LVI cache invalidation. The bug is easily triggered with our downstream changes, but is difficult to trigger it upstream. We need the printer pass to write an isolated upstream test case for this problem.

include/llvm/Analysis/LazyValueInfo.h

101 ↗

(On Diff #91214)

Here and below - /// doxygen documentation comment

102 ↗

(On Diff #91214)

Here and below - just printCache?

lib/Analysis/LazyValueInfo.cpp

449 ↗

(On Diff #91214)

For the sake of completeness you might also want to print overdefined cache.

[anna]

In D30790#697519, @apilipenko wrote:

It's worth noting for others that the motivation for the change is a bug we found in JumpThreading LVI cache invalidation. The bug is easily triggered with our downstream changes, but is difficult to trigger it upstream. We need the printer pass to write an isolated upstream test case for this problem.

Yes, the motivation is the bug :)
It is *easier* to trigger the bug upstream with printer pass after jump-threading. This pass will also help in uncovering/testing any other LVI caching issues or LVI broken invariants. Also, we can easily print the LVI cache within any pass (using LVI) as LVI->printLazyValueInfoCache(errs()).

[anna]

include/llvm/Analysis/LazyValueInfo.h

102 ↗

(On Diff #91214)

how about printCaches? Since we'll print both the overdefined and the LVICache.

lib/Analysis/LazyValueInfo.cpp

449 ↗

(On Diff #91214)

agreed. I've added printing of overdefined per basic block.

[apilipenko]

include/llvm/Analysis/LazyValueInfo.h

102 ↗

(On Diff #91214)

Works for me

[anna]

Added printing for the overdefined cache, updated tests.

[anna]

include/llvm/Analysis/LazyValueInfo.h

102 ↗

(On Diff #91214)

Both overdefined and latticevaluecache are defined within the LVICache. So, left as printCache itself.

[• dberlin]

include/llvm/Analysis/LazyValueInfo.h

102 ↗

(On Diff #91364)

What's the reason for datalayout?
It's always gettable from any instruction, etc.

lib/Analysis/LazyValueInfo.cpp

444 ↗

(On Diff #91364)

FWIW: I would generally recommend you do this as an annotation to the basic blocks/values, using the asm printer interface, and adding them as comments.

This would produce output similar to print-predicateinfo, print-memoryssa, etc, where the values are right above the instructions they belong to.

This usually makes it significantly easier to test and understand what is going on, IME.

I have not looked at this specific case, of course.

But, for example, the iteration order here is *completely* undefined, meaning you have to be prepared for the output to appear in any order.

448 ↗

(On Diff #91364)

BB's don't always have names, i would use BV.first->printAsOperand(), which will also handle the nameless ones properly.

1858 ↗

(On Diff #91364)

You should add a new PM version of this as well.

1871 ↗

(On Diff #91364)

I do not believe we normally print to errs for printing passes.
I believe they still print to dbgs()

[anna]

include/llvm/Analysis/LazyValueInfo.h

102 ↗

(On Diff #91364)

We need it here for getting the LazyValueInfoImpl within this function. I don't think we have any other way for getting the datalayout.

see: getImpl(PImpl, AC, &DL, DT).printCache(OS);

lib/Analysis/LazyValueInfo.cpp

444 ↗

(On Diff #91364)

Yes, since the order would be completely undefined, I used the CHECK-DAG part here along with the CHECK-LABEL.
Thanks, I will take a look at the asm printer interface used in the other print functions.

1871 ↗

(On Diff #91364)

So, couple of ones still print to errs, like the AliasSetPrinter (that's the one I followed for this). It looks like most printing passes print to dbgs(), I can change to that.

[• dberlin]

include/llvm/Analysis/LazyValueInfo.h

102 ↗

(On Diff #91364)

Oh, yeah, this is just silly.
It looks like LazyValueInfo doesn't have DL, but all the impl's require it.
This looks like it was just the simplest conversion possible.

I would just add it to the class LazyValueInfo interface, since everything else is there.

[anna]

Hi folks,
Daniel added a suggestion regarding the printing of the LVI:

FWIW: I would generally recommend you do this as an annotation to the basic blocks/values, using the asm printer interface, and adding them as comments.

This would produce output similar to print-predicateinfo, print-memoryssa, etc, where the values are right above the instructions they belong to.

This usually makes it significantly easier to test and understand what is going on, IME.

I had a look at the print-predicateinfo, and agree with Daniel - adding annotations as comments before the instruction makes it easier to see what's the transformation (along with the LVI values). However, in the LVI case, an instruction would have a list of LatticeValues corresponding to different basic blocks. Also, the LatticeValueCache structure enables printing the annotation per instruction (the cache key is ssa value). The overdefined cache structure enables printing per basic block. So, the print would be something like this:

For test2 example (see annotations added as comments):

entry:
; ' i32 %n ' is overdefined
  br label %loop

loop
;  %iv2 = phi i32 [ %n, %entry ], [ %iv2.next, %backedge ] '  is overdefined
; 'constantrange<0, -2147483647>' at the beginning of 'loop'
; 'constantrange<0, -2147483648>' at the beginning of 'backedge'
  %iv = phi i32 [0, %entry], [%iv.next, %backedge] <-- the values corresponding to the `%iv` per basic block, are annotated before the instruction.
  %iv2 = phi i32 [%n, %entry], [%iv2.next, %backedge]
  %cnd1 = icmp sge i32 %iv, 0
  %cnd2 = icmp sgt i32 %iv2, 0
  %cnd = and i1 %cnd1, %cnd2
  br i1 %cnd, label %backedge, label %exit

backedge:
; 'constantrange<1, -2147483647>' at the beginning of  'backedge'
  %iv.next = add nsw i32 %iv, 1
  %iv2.next = sub nsw i32 %iv2, 1
  %cont1 = icmp slt i32 %iv.next, 400
  %cont2 = icmp sgt i32 %iv2.next, 0
  %cont = and i1 %cont1, %cont2
  br i1 %cont, label %loop, label %exit

exit:
  ret i8 0

I think it looks clearer than the CHECK-DAG and CHECK-LABEL combination I have for test2 currently.

Does this look better?

include/llvm/Analysis/LazyValueInfo.h

102 ↗

(On Diff #91364)

Thanks, added as a separate NFC.

[anna]

As per comment above. Changing this to use the AssemblyAnnotationWriter.

[anna]

Updated the pass to use the AseemblyAnnotationWriter.
Addressed other review comments.
Tests updated accordingly.

I have not yet added the new pass manager version, I'll add for review once this is completed.
(The new pass manager version of the LVIPrinter compiles, but it does not use the existing LVI object, I'll debug that on the side.
Don't want to block this review on that issue).

[anna]

Review for the updated version. The previous LGTMed version did not return the annotation as comments.

[anna]

ping

[• dberlin]

I think this looks good to me :)
Thanks for doing this!

[anna]

Thanks Daniel!

I'll submit a follow on patch (directly) for capturing lattice values of the function's arguments. Just realized while adding some test cases that the AssemblyAnnotationWriter only prints info for instructions and basic blocks.

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);
+
   // 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/include/llvm/InitializePasses.h

 void initializeLCSSAVerificationPassPass(PassRegistry&);
 void initializeLCSSAWrapperPassPass(PassRegistry&);
 void initializeLazyBlockFrequencyInfoPassPass(PassRegistry&);
 void initializeLazyBranchProbabilityInfoPassPass(PassRegistry&);
 void initializeLazyMachineBlockFrequencyInfoPassPass(PassRegistry&);
 void initializeLazyValueInfoWrapperPassPass(PassRegistry&);
 void initializeLegacyLICMPassPass(PassRegistry&);
 void initializeLegacyLoopSinkPassPass(PassRegistry&);
+void initializeLazyValueInfoPrinterPass(PassRegistry&);
 void initializeLegalizerPass(PassRegistry&);
 void initializeLibCallsShrinkWrapLegacyPassPass(PassRegistry&);
 void initializeLintPass(PassRegistry&);
 void initializeLiveDebugValuesPass(PassRegistry&);
 void initializeLiveDebugVariablesPass(PassRegistry&);
 void initializeLiveIntervalsPass(PassRegistry&);
 void initializeLiveRegMatrixPass(PassRegistry&);
 void initializeLiveStacksPass(PassRegistry&);

llvm/trunk/lib/Analysis/Analysis.cpp

void llvm::initializeAnalysis(PassRegistry &Registry) {
   initializeAAResultsWrapperPassPass(Registry);
   initializeGlobalsAAWrapperPassPass(Registry);
   initializeIVUsersWrapperPassPass(Registry);
   initializeInstCountPass(Registry);
   initializeIntervalPartitionPass(Registry);
   initializeLazyBranchProbabilityInfoPassPass(Registry);
   initializeLazyBlockFrequencyInfoPassPass(Registry);
   initializeLazyValueInfoWrapperPassPass(Registry);
+  initializeLazyValueInfoPrinterPass(Registry);
   initializeLintPass(Registry);
   initializeLoopInfoWrapperPassPass(Registry);
   initializeMemDepPrinterPass(Registry);
   initializeMemDerefPrinterPass(Registry);
   initializeMemoryDependenceWrapperPassPass(Registry);
   initializeModuleDebugInfoPrinterPass(Registry);
   initializeModuleSummaryIndexWrapperPassPass(Registry);
   initializeObjCARCAAWrapperPassPass(Registry);

llvm/trunk/lib/Analysis/LazyValueInfo.cpp

 
 #include "llvm/Analysis/LazyValueInfo.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/ConstantFolding.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/ValueTracking.h"
+#include "llvm/IR/AssemblyAnnotationWriter.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/ConstantRange.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
 #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"
 #include "llvm/Support/Debug.h"
+#include "llvm/Support/FormattedStream.h"
 #include "llvm/Support/raw_ostream.h"
 #include <map>
 #include <stack>
 using namespace llvm;
 using namespace PatternMatch;
 
 #define DEBUG_TYPE "lazy-value-info"
 
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 is all of the cached information for all values,
-    /// mapped from Value* to key information.
-    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.
     typedef DenseMap<PoisoningVH<BasicBlock>, SmallPtrSet<Value *, 4>>
         OverDefinedCacheTy;
-    OverDefinedCacheTy OverDefinedCache;
-
     /// 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) {
       SeenBlocks.insert(BB);
 
       // Insert over-defined values into their own cache to reduce memory
       // overhead.
       if (Result.isOverdefined())
         OverDefinedCache[BB].insert(Val);
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";
+    }
+
+    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())
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);
+    }
+
     /// 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 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) {
+  if (PImpl) {
+    getImpl(PImpl, AC, DL, DT).printCache(F, OS);
+  }
+}
+
+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>();
+  }
+
+  bool runOnFunction(Function &F) override {
+    dbgs() << "LVI for function '" << F.getName() << "':\n";
+    auto &LVI = getAnalysis<LazyValueInfoWrapperPass>().getLVI();
+    LVI.printCache(F, 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:
+  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:  %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: 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
+loop:
+  %iv = phi i32 [0, %entry], [%iv.next, %backedge]
+  %iv2 = phi i32 [%n, %entry], [%iv2.next, %backedge]
+  %cnd1 = icmp sge i32 %iv, 0
+  %cnd2 = icmp sgt i32 %iv2, 0
+  %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
+backedge:
+  %iv.next = add nsw i32 %iv, 1
+  %iv2.next = sub nsw i32 %iv2, 1
+  %cont1 = icmp slt i32 %iv.next, 400
+  %cont2 = icmp sgt i32 %iv2.next, 0
+  %cont = and i1 %cont1, %cont2
+  br i1 %cont, label %loop, label %exit
+
+exit:
+  ret i8 0
+}