Index: llvm/trunk/include/llvm/Analysis/LazyValueInfo.h =================================================================== --- llvm/trunk/include/llvm/Analysis/LazyValueInfo.h +++ llvm/trunk/include/llvm/Analysis/LazyValueInfo.h @@ -100,6 +100,9 @@ /// 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(); Index: llvm/trunk/include/llvm/InitializePasses.h =================================================================== --- llvm/trunk/include/llvm/InitializePasses.h +++ llvm/trunk/include/llvm/InitializePasses.h @@ -178,6 +178,7 @@ void initializeLazyValueInfoWrapperPassPass(PassRegistry&); void initializeLegacyLICMPassPass(PassRegistry&); void initializeLegacyLoopSinkPassPass(PassRegistry&); +void initializeLazyValueInfoPrinterPass(PassRegistry&); void initializeLegalizerPass(PassRegistry&); void initializeLibCallsShrinkWrapLegacyPassPass(PassRegistry&); void initializeLintPass(PassRegistry&); Index: llvm/trunk/lib/Analysis/Analysis.cpp =================================================================== --- llvm/trunk/lib/Analysis/Analysis.cpp +++ llvm/trunk/lib/Analysis/Analysis.cpp @@ -57,6 +57,7 @@ initializeLazyBranchProbabilityInfoPassPass(Registry); initializeLazyBlockFrequencyInfoPassPass(Registry); initializeLazyValueInfoWrapperPassPass(Registry); + initializeLazyValueInfoPrinterPass(Registry); initializeLintPass(Registry); initializeLoopInfoWrapperPassPass(Registry); initializeMemDepPrinterPass(Registry); Index: llvm/trunk/lib/Analysis/LazyValueInfo.cpp =================================================================== --- llvm/trunk/lib/Analysis/LazyValueInfo.cpp +++ llvm/trunk/lib/Analysis/LazyValueInfo.cpp @@ -19,6 +19,7 @@ #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" @@ -31,6 +32,7 @@ #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 #include @@ -362,6 +364,7 @@ /// 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. @@ -373,20 +376,21 @@ SmallDenseMap, LVILatticeVal, 4> BlockVals; }; - /// This is all of the cached information for all values, - /// mapped from Value* to key information. - DenseMap> ValueCache; - /// This tracks, on a per-block basis, the set of values that are /// over-defined at the end of that block. typedef DenseMap, SmallPtrSet> 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 > SeenBlocks; + protected: + /// This is all of the cached information for all values, + /// mapped from Value* to key information. + DenseMap> ValueCache; + OverDefinedCacheTy OverDefinedCache; + + public: void insertResult(Value *Val, BasicBlock *BB, const LVILatticeVal &Result) { SeenBlocks.insert(BB); @@ -439,6 +443,7 @@ return BBI->second; } + void printCache(Function &F, raw_ostream &OS); /// clear - Empty the cache. void clear() { SeenBlocks.clear(); @@ -462,6 +467,49 @@ }; } + +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(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(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 @@ -633,6 +681,11 @@ 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) { @@ -1824,3 +1877,40 @@ 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(); + } + + bool runOnFunction(Function &F) override { + dbgs() << "LVI for function '" << F.getName() << "':\n"; + auto &LVI = getAnalysis().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) Index: llvm/trunk/test/Analysis/LazyValueAnalysis/lvi-after-jumpthreading.ll =================================================================== --- llvm/trunk/test/Analysis/LazyValueAnalysis/lvi-after-jumpthreading.ll +++ llvm/trunk/test/Analysis/LazyValueAnalysis/lvi-after-jumpthreading.ll @@ -0,0 +1,84 @@ +; 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 +}