[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

Here and below - /// doxygen documentation comment

102

Here and below - just printCache?

lib/Analysis/LazyValueInfo.cpp

449

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

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

lib/Analysis/LazyValueInfo.cpp

449

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

[apilipenko]

include/llvm/Analysis/LazyValueInfo.h

102

Works for me

[anna]

Added printing for the overdefined cache, updated tests.

[anna]

include/llvm/Analysis/LazyValueInfo.h

102

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

[• dberlin]

include/llvm/Analysis/LazyValueInfo.h

102

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

lib/Analysis/LazyValueInfo.cpp

444

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

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

1858

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

1871

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

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

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

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

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

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.

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(const DataLayout &DL, 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);
 };
 

include/llvm/InitializePasses.h

 void initializeLCSSAWrapperPassPass(PassRegistry&);
 void initializeLCSSAVerificationPassPass(PassRegistry&);
 void initializeLegacyLICMPassPass(PassRegistry&);
 void initializeLegacyLoopSinkPassPass(PassRegistry&);
 void initializeLazyBranchProbabilityInfoPassPass(PassRegistry&);
 void initializeLazyMachineBlockFrequencyInfoPassPass(PassRegistry&);
 void initializeLazyBlockFrequencyInfoPassPass(PassRegistry&);
 void initializeLazyValueInfoWrapperPassPass(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&);

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);

lib/Analysis/LazyValueInfo.cpp

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;
     }
 
+    // Printing the ValueCache.
+    void printCache(raw_ostream &OS) {
+      for (auto &VC : ValueCache)
+        for (auto &BV : VC.second->BlockVals)
+          OS << " For '" << *VC.first << "' the CachedLatticeValue is: '"
+             << BV.second << "' at the beginning of BasicBlock: '"
+             << BV.first->getName() << "'\n";
+      OS << "Overdefined Values per basic block\n";
+      for (auto &OC : OverDefinedCache) {
+        OS << "\nFor '" << OC.first->getName()
+           << "' the overdefined values are: ";
+        for (Value *V : OC.second)
+          OS << " ' " << *V << " '; ";
+      }
+    }
+
     /// clear - Empty the cache.
     void clear() {
       SeenBlocks.clear();
       ValueCache.clear();
       OverDefinedCache.clear();
     }
 
     /// Inform the cache that a given value has been deleted.
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(raw_ostream &OS) {
+       TheCache.printCache(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(const DataLayout &DL, raw_ostream &OS) {
+  if (PImpl) {
+    getImpl(PImpl, AC, &DL, DT).printCache(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 {
+    errs() << "LVI for function '" << F.getName() << "':\n";
+    auto &LVI = getAnalysis<LazyValueInfoWrapperPass>().getLVI();
+    LVI.printCache(F.getParent()->getDataLayout(), errs());
+    return false;
+  }
+};
+}
+
+char LazyValueInfoPrinter::ID = 0;
+INITIALIZE_PASS_BEGIN(LazyValueInfoPrinter, "print-lazy-value-info",
+                "Lazy Value Info Printer Pass", false, true)
+INITIALIZE_PASS_DEPENDENCY(LazyValueInfoWrapperPass)
+INITIALIZE_PASS_END(LazyValueInfoPrinter, "print-lazy-value-info",
+                "Lazy Value Info Printer Pass", false, true)

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':
+; CHECK-DAG: For ' %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]' the CachedLatticeValue is: 'constantrange<0, 400>' at the beginning of BasicBlock: 'backedge'
+; CHECK-DAG: For ' %iv.next = add nsw i32 %iv, 1' the CachedLatticeValue is: 'constantrange<1, 401>' at the beginning of BasicBlock: 'backedge'
+entry:
+  br label %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-DAG: For ' %iv.next = add nsw i32 %iv, 1' the CachedLatticeValue is: 'constantrange<1, -2147483647>' at the beginning of BasicBlock: 'backedge'
+; CHECK-DAG: For ' %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]' the CachedLatticeValue is: 'constantrange<0, -2147483647>' at the beginning of BasicBlock: 'loop'
+; CHECK-DAG: For ' %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]' the CachedLatticeValue is: 'constantrange<0, -2147483648>' at the beginning of BasicBlock: 'backedge'
+; CHECK-LABEL: Overdefined Values per basic block
+; CHECK-DAG: For 'loop' the overdefined values are:  '   %iv2 = phi i32 [ %n, %entry ], [ %iv2.next, %backedge ] ';
+; CHECK-DAG: For 'entry' the overdefined values are:  ' i32 %n ';
+entry:
+  br label %loop
+
+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
+
+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
+}