[GVN] Basic optimization remark support

[anemet]

Summary

Follow-on patches will add more interesting cases.

The goal of this patch-set is to get the GVN messages printed in
opt-viewer from Dhrystone as was presented in my Dev Meeting talk. This
is the optimization view for the function (the last remark in the
function has a bug which is fixed in this series):
http://lab.llvm.org:8080/artifacts/opt-view_test-suite/build/SingleSource/Benchmarks/Dhrystone/CMakeFiles/dry.dir/html/_org_test-suite_SingleSource_Benchmarks_Dhrystone_dry.c.html#L430

[davide]

You're mentioning that more interesting cases will be added in later patches, can you please elaborate what else do you have in mind (other than load elim?)

lib/IR/DiagnosticInfo.cpp

183–188

I assume you're using this but it's not strictly tied to the patch, i.e. maybe can be committed separately? (up to you)

lib/Transforms/Scalar/GVN.cpp

1811–1812

I see here you're adding this DEBUG statement before emitting the remark but you don't in the other two cases. Is this intended?

[anemet]

Hi Davide,

In D26488#591495, @davide wrote:

You're mentioning that more interesting cases will be added in later patches, can you please elaborate what else do you have in mind (other than load elim?)

Currently it is load-elim in patch 2 and 3. There are probably other interesting things we can do with load-pre but I don't have those implemented. Also not directly GVN-specific, but it would also be nice to somehow expose the aliasing information via opt-viewer. (Let me know if you're interested working on any of this.)

lib/IR/DiagnosticInfo.cpp

183–188

Yeah the first use is in this patch and this allows writing the test case for the feature.

lib/Transforms/Scalar/GVN.cpp

1811–1812

Thanks for bringing this up, I haven't so far thought about the relationship of debug output and opt remarks. I think that we shouldn't have debug output if we already have opt remarks. It makes the code less readable and with "opt -pass-remarks*=" you can get them printed.

Let me remove this.

Perhaps in the long run we can imply -pass-remarks*=<pass> if "-debug-only=<pass>" is used.

[anemet]

Remove the debug statement per Davide's comment

[hfinkel]

Should we update the message to also provide the location/type of the store? (or the other load for the PRE case).

When we have debug information on the variable, should we print its name/type from the debug info? (This might be useful when we have aggregates, for example, especially after SROA is done with them). I'm happy for this to be done in follow-up if you agree it is useful.

lib/Transforms/Scalar/GVN.cpp

1813

Please make a function to emit this remark; I don't want to repeat literal strings in the code.

[anemet]

In D26488#593529, @hfinkel wrote:

Should we update the message to also provide the location/type of the store? (or the other load for the PRE case).

Which store, the one that we forward from? I did that in D26489.

When we have debug information on the variable, should we print its name/type from the debug info? (This might be useful when we have aggregates, for example, especially after SROA is done with them). I'm happy for this to be done in follow-up if you agree it is useful.

Yes I agree, we should explore this further.

[anemet]

Address Hal's comment

[hfinkel]

LGTM

include/llvm/IR/DiagnosticInfo.h

public:
   struct Argument {
     StringRef Key;
     std::string Val;
     // If set, the debug location corresponding to the value.
     DebugLoc DLoc;
 
     explicit Argument(StringRef Str = "") : Key("String"), Val(Str) {}
     Argument(StringRef Key, Value *V);
+    Argument(StringRef Key, Type *T);
     Argument(StringRef Key, int N);
     Argument(StringRef Key, unsigned N);
     Argument(StringRef Key, bool B) : Key(Key), Val(B ? "true" : "false") {}
   };
 
   /// \p PassName is the name of the pass emitting this diagnostic. \p
   /// RemarkName is a textual identifier for the remark.  \p Fn is the function
   /// where the diagnostic is being emitted. \p DLoc is the location information

include/llvm/Transforms/Scalar/GVN.h

 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/MemoryDependenceAnalysis.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/PassManager.h"
 
 namespace llvm {
+class OptimizationRemarkEmitter;
 
 /// A private "module" namespace for types and utilities used by GVN. These
 /// are implementation details and should not be used by clients.
 namespace gvn LLVM_LIBRARY_VISIBILITY {
 struct AvailableValue;
 struct AvailableValueInBlock;
 class GVNLegacyPass;
 }
private:
   friend class gvn::GVNLegacyPass;
   friend struct DenseMapInfo<Expression>;
 
   MemoryDependenceResults *MD;
   DominatorTree *DT;
   const TargetLibraryInfo *TLI;
   AssumptionCache *AC;
   SetVector<BasicBlock *> DeadBlocks;
+  OptimizationRemarkEmitter *ORE;
 
   ValueTable VN;
 
   /// A mapping from value numbers to lists of Value*'s that
   /// have that value number.  Use findLeader to query it.
   struct LeaderTableEntry {
     Value *Val;
     const BasicBlock *BB;
private:
   SmallVector<Instruction *, 8> InstrsToErase;
 
   typedef SmallVector<NonLocalDepResult, 64> LoadDepVect;
   typedef SmallVector<gvn::AvailableValueInBlock, 64> AvailValInBlkVect;
   typedef SmallVector<BasicBlock *, 64> UnavailBlkVect;
 
   bool runImpl(Function &F, AssumptionCache &RunAC, DominatorTree &RunDT,
                const TargetLibraryInfo &RunTLI, AAResults &RunAA,
-               MemoryDependenceResults *RunMD);
+               MemoryDependenceResults *RunMD, OptimizationRemarkEmitter *ORE);
 
   /// Push a new Value to the LeaderTable onto the list for its value number.
   void addToLeaderTable(uint32_t N, Value *V, const BasicBlock *BB) {
     LeaderTableEntry &Curr = LeaderTable[N];
     if (!Curr.Val) {
       Curr.Val = V;
       Curr.BB = BB;
       return;

lib/IR/DiagnosticInfo.cpp

DiagnosticInfoOptimizationBase::Argument::Argument(StringRef Key, Value *V)
   if (auto *F = dyn_cast<Function>(V)) {
     if (DISubprogram *SP = F->getSubprogram())
       DLoc = DebugLoc::get(SP->getScopeLine(), 0, SP);
   }
   else if (auto *I = dyn_cast<Instruction>(V))
     DLoc = I->getDebugLoc();
 }
 
+DiagnosticInfoOptimizationBase::Argument::Argument(StringRef Key, Type *T)
+    : Key(Key) {
+  raw_string_ostream OS(Val);
+  OS << *T;
+}
+
 DiagnosticInfoOptimizationBase::Argument::Argument(StringRef Key, int N)
     : Key(Key), Val(itostr(N)) {}
 
 DiagnosticInfoOptimizationBase::Argument::Argument(StringRef Key, unsigned N)
     : Key(Key), Val(utostr(N)) {}
 
 void DiagnosticInfoOptimizationBase::print(DiagnosticPrinter &DP) const {
   DP << getLocationStr() << ": " << getMsg();

lib/Transforms/Scalar/GVN.cpp

 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/CFG.h"
 #include "llvm/Analysis/ConstantFolding.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/Loads.h"
 #include "llvm/Analysis/MemoryBuiltins.h"
 #include "llvm/Analysis/MemoryDependenceAnalysis.h"
+#include "llvm/Analysis/OptimizationDiagnosticInfo.h"
 #include "llvm/Analysis/PHITransAddr.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/GlobalVariable.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/IntrinsicInst.h"
PreservedAnalyses GVN::run(Function &F, FunctionAnalysisManager &AM) {
   // significant! Re-ordering these variables will cause GVN when run alone to
   // be less effective! We should fix memdep and basic-aa to not exhibit this
   // behavior, but until then don't change the order here.
   auto &AC = AM.getResult<AssumptionAnalysis>(F);
   auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
   auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
   auto &AA = AM.getResult<AAManager>(F);
   auto &MemDep = AM.getResult<MemoryDependenceAnalysis>(F);
-  bool Changed = runImpl(F, AC, DT, TLI, AA, &MemDep);
+  auto &ORE = AM.getResult<OptimizationRemarkEmitterAnalysis>(F);
+  bool Changed = runImpl(F, AC, DT, TLI, AA, &MemDep, &ORE);
   if (!Changed)
     return PreservedAnalyses::all();
   PreservedAnalyses PA;
   PA.preserve<DominatorTreeAnalysis>();
   PA.preserve<GlobalsAA>();
   return PA;
 }
 
bool GVN::PerformLoadPRE(LoadInst *LI, AvailValInBlkVect &ValuesPerBlock,
   LI->replaceAllUsesWith(V);
   if (isa<PHINode>(V))
     V->takeName(LI);
   if (Instruction *I = dyn_cast<Instruction>(V))
     I->setDebugLoc(LI->getDebugLoc());
   if (V->getType()->getScalarType()->isPointerTy())
     MD->invalidateCachedPointerInfo(V);
   markInstructionForDeletion(LI);
+  ORE->emit(OptimizationRemark(DEBUG_TYPE, "LoadPRE", LI)
+            << "load eliminated by PRE");
   ++NumPRELoad;
   return true;
 }
 
+static void reportLoadElim(LoadInst *LI, OptimizationRemarkEmitter *ORE) {
+  ORE->emit(OptimizationRemark(DEBUG_TYPE, "LoadElim", LI)
+            << "load of type " << ore::NV("Type", LI->getType())
+            << " eliminated");
+}
+
 /// Attempt to eliminate a load whose dependencies are
 /// non-local by performing PHI construction.
 bool GVN::processNonLocalLoad(LoadInst *LI) {
   // non-local speculations are not allowed under asan.
   if (LI->getParent()->getParent()->hasFnAttribute(Attribute::SanitizeAddress))
     return false;
 
   // Step 1: Find the non-local dependencies of the load.
if (isa<PHINode>(V))
       V->takeName(LI);
     if (Instruction *I = dyn_cast<Instruction>(V))
       if (LI->getDebugLoc())
         I->setDebugLoc(LI->getDebugLoc());
     if (V->getType()->getScalarType()->isPointerTy())
       MD->invalidateCachedPointerInfo(V);
     markInstructionForDeletion(LI);
     ++NumGVNLoad;
+    reportLoadElim(LI, ORE);
     return true;
   }
 
   // Step 4: Eliminate partial redundancy.
   if (!EnablePRE || !EnableLoadPRE)
     return false;
 
   return PerformLoadPRE(LI, ValuesPerBlock, UnavailableBlocks);
bool GVN::processLoad(LoadInst *L) {
   AvailableValue AV;
   if (AnalyzeLoadAvailability(L, Dep, L->getPointerOperand(), AV)) {
     Value *AvailableValue = AV.MaterializeAdjustedValue(L, L, *this);
 
     // Replace the load!
     patchAndReplaceAllUsesWith(L, AvailableValue);
     markInstructionForDeletion(L);
     ++NumGVNLoad;
+    reportLoadElim(L, ORE);
     // Tell MDA to rexamine the reused pointer since we might have more
     // information after forwarding it.
     if (MD && AvailableValue->getType()->getScalarType()->isPointerTy())
       MD->invalidateCachedPointerInfo(AvailableValue);
     return true;
   }
 
   return false;
 }
 
if (MD && Repl->getType()->getScalarType()->isPointerTy())
     MD->invalidateCachedPointerInfo(Repl);
   markInstructionForDeletion(I);
   return true;
 }
 
 /// runOnFunction - This is the main transformation entry point for a function.
 bool GVN::runImpl(Function &F, AssumptionCache &RunAC, DominatorTree &RunDT,
                   const TargetLibraryInfo &RunTLI, AAResults &RunAA,
-                  MemoryDependenceResults *RunMD) {
+                  MemoryDependenceResults *RunMD,
+                  OptimizationRemarkEmitter *RunORE) {
   AC = &RunAC;
   DT = &RunDT;
   VN.setDomTree(DT);
   TLI = &RunTLI;
   VN.setAliasAnalysis(&RunAA);
   MD = RunMD;
   VN.setMemDep(MD);
+  ORE = RunORE;
 
   bool Changed = false;
   bool ShouldContinue = true;
 
   // Merge unconditional branches, allowing PRE to catch more
   // optimization opportunities.
   for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ) {
     BasicBlock *BB = &*FI++;
if (skipFunction(F))
       return false;
 
     return Impl.runImpl(
         F, getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F),
         getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
         getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(),
         getAnalysis<AAResultsWrapperPass>().getAAResults(),
         NoLoads ? nullptr
-                : &getAnalysis<MemoryDependenceWrapperPass>().getMemDep());
+                : &getAnalysis<MemoryDependenceWrapperPass>().getMemDep(),
+        &getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE());
   }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addRequired<AssumptionCacheTracker>();
     AU.addRequired<DominatorTreeWrapperPass>();
     AU.addRequired<TargetLibraryInfoWrapperPass>();
     if (!NoLoads)
       AU.addRequired<MemoryDependenceWrapperPass>();
     AU.addRequired<AAResultsWrapperPass>();
 
     AU.addPreserved<DominatorTreeWrapperPass>();
     AU.addPreserved<GlobalsAAWrapperPass>();
+    AU.addRequired<OptimizationRemarkEmitterWrapperPass>();
   }
 
 private:
   bool NoLoads;
   GVN Impl;
 };
 
 char GVNLegacyPass::ID = 0;
 
 // The public interface to this file...
 FunctionPass *llvm::createGVNPass(bool NoLoads) {
   return new GVNLegacyPass(NoLoads);
 }
 
 INITIALIZE_PASS_BEGIN(GVNLegacyPass, "gvn", "Global Value Numbering", false, false)
 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
 INITIALIZE_PASS_DEPENDENCY(MemoryDependenceWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(OptimizationRemarkEmitterWrapperPass)
 INITIALIZE_PASS_END(GVNLegacyPass, "gvn", "Global Value Numbering", false, false)

test/Transforms/GVN/opt-remarks.ll

+; RUN: opt < %s -gvn -o /dev/null  -pass-remarks-output=%t -S -pass-remarks=gvn \
+; RUN:     2>&1 | FileCheck %s
+; RUN: cat %t | FileCheck -check-prefix=YAML %s
+
+; CHECK:      remark: <unknown>:0:0: load of type i32 eliminated{{$}}
+; CHECK-NEXT: remark: <unknown>:0:0: load of type i32 eliminated{{$}}
+; CHECK-NEXT: remark: <unknown>:0:0: load of type i32 eliminated{{$}}
+; CHECK-NOT:  remark:
+
+; YAML:      --- !Passed
+; YAML-NEXT: Pass:            gvn
+; YAML-NEXT: Name:            LoadElim
+; YAML-NEXT: Function:        arg
+; YAML-NEXT: Args:
+; YAML-NEXT:   - String:          'load of type '
+; YAML-NEXT:   - Type:            i32
+; YAML-NEXT:   - String:          ' eliminated'
+; YAML-NEXT: ...
+; YAML-NEXT: --- !Passed
+; YAML-NEXT: Pass:            gvn
+; YAML-NEXT: Name:            LoadElim
+; YAML-NEXT: Function:        const
+; YAML-NEXT: Args:
+; YAML-NEXT:   - String:          'load of type '
+; YAML-NEXT:   - Type:            i32
+; YAML-NEXT:   - String:          ' eliminated'
+; YAML-NEXT: ...
+; YAML-NEXT: --- !Passed
+; YAML-NEXT: Pass:            gvn
+; YAML-NEXT: Name:            LoadElim
+; YAML-NEXT: Function:        inst
+; YAML-NEXT: Args:
+; YAML-NEXT:   - String:          'load of type '
+; YAML-NEXT:   - Type:            i32
+; YAML-NEXT:   - String:          ' eliminated'
+; YAML-NEXT: ...
+
+
+define i32 @arg(i32* %p, i32 %i) {
+entry:
+  store i32 %i, i32* %p
+  %load = load i32, i32* %p
+  ret i32 %load
+}
+
+define i32 @const(i32* %p) {
+entry:
+  store i32 4, i32* %p
+  %load = load i32, i32* %p
+  ret i32 %load
+}
+
+define i32 @inst(i32* %p) {
+entry:
+  %load1 = load i32, i32* %p
+  %load = load i32, i32* %p
+  %add = add i32 %load1, %load
+  ret i32 %add
+}