Index: include/llvm/Analysis/LazyValueInfo.h =================================================================== --- include/llvm/Analysis/LazyValueInfo.h +++ include/llvm/Analysis/LazyValueInfo.h @@ -100,8 +100,8 @@ /// 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. + void printLVI(Function &F, raw_ostream &OS); // For old PM pass. Delete once LazyValueInfoWrapperPass is gone. void releaseMemory(); Index: lib/Analysis/LazyValueInfo.cpp =================================================================== --- lib/Analysis/LazyValueInfo.cpp +++ lib/Analysis/LazyValueInfo.cpp @@ -364,7 +364,6 @@ /// 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. @@ -384,7 +383,6 @@ /// 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; @@ -443,7 +441,6 @@ return BBI->second; } - void printCache(Function &F, raw_ostream &OS); /// clear - Empty the cache. void clear() { SeenBlocks.clear(); @@ -467,61 +464,6 @@ }; } - -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"; - - // Find if there are latticevalues defined for arguments of the function. - auto *F = const_cast(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(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(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 @@ -615,6 +557,24 @@ } } + +namespace { +/// An assembly annotator class to print LazyValueCache information in +/// comments. +class LazyValueInfoImpl; +class LazyValueInfoAnnotatedWriter : public AssemblyAnnotationWriter { + LazyValueInfoImpl *LVIImpl; + +public: + LazyValueInfoAnnotatedWriter(LazyValueInfoImpl *L) : LVIImpl(L) {} + + 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 @@ -693,9 +653,10 @@ TheCache.clear(); } - /// Printing the LazyValueInfoCache. - void printCache(Function &F, raw_ostream &OS) { - TheCache.printCache(F, OS); + /// Printing the LazyValueInfo Analysis. + void printLVI(Function &F, raw_ostream &OS) { + LazyValueInfoAnnotatedWriter Writer(this); + F.print(OS, &Writer); } /// This is part of the update interface to inform the cache @@ -714,6 +675,7 @@ }; } // end anonymous namespace + void LazyValueInfoImpl::solve() { SmallVector, 8> StartingStack( BlockValueStack.begin(), BlockValueStack.end()); @@ -1891,12 +1853,63 @@ } -void LazyValueInfo::printCache(Function &F, raw_ostream &OS) { +void LazyValueInfo::printLVI(Function &F, raw_ostream &OS) { if (PImpl) { - getImpl(PImpl, AC, DL, DT).printCache(F, OS); + getImpl(PImpl, AC, DL, DT).printLVI(F, 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 = const_cast(BB->getParent()); + for (auto &Arg : F->args()) { + LVILatticeVal Result = LVIImpl->getValueInBlock(&Arg, const_cast(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(); + // Print the LVI analysis for `I` in basic blocks that define/use `I` as well + // as blocks that are immediate successors of ParentBB. We cannot + // unconditionally call getValueInBlock for all blocks in the function, + // because we will fail on solving LVI for entry basic block if it does not + // define `I`. + SmallPtrSet BlocksContainingLVI; + auto printResult = [&](const BasicBlock *BB) { + if (!BlocksContainingLVI.insert(BB).second) + return; + LVILatticeVal Result = LVIImpl->getValueInBlock( + const_cast(I), const_cast(BB)); + if (!Result.isUndefined()) { + 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. + for (auto *BBSucc : successors(ParentBB)) + printResult(BBSucc); + + // Print LVI in blocks where `I` is used. + for (auto *U : I->users()) + if (auto *UseI = dyn_cast(U)) + printResult(UseI->getParent()); + +} + namespace { // Printer class for LazyValueInfo results. class LazyValueInfoPrinter : public FunctionPass { @@ -1914,7 +1927,7 @@ bool runOnFunction(Function &F) override { dbgs() << "LVI for function '" << F.getName() << "':\n"; auto &LVI = getAnalysis().getLVI(); - LVI.printCache(F, dbgs()); + LVI.printLVI(F, dbgs()); return false; } }; Index: test/Analysis/LazyValueAnalysis/lvi-after-jumpthreading.ll =================================================================== --- test/Analysis/LazyValueAnalysis/lvi-after-jumpthreading.ll +++ test/Analysis/LazyValueAnalysis/lvi-after-jumpthreading.ll @@ -10,17 +10,23 @@ 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] @@ -36,49 +42,3 @@ 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 -}