[GVN, OptDiag] Print the interesting instructions involved in missed load-elimination

[anemet]

Summary

This includes the intervening store and the load that we're trying to
forward from in the optimization remark for the missed load elimination.

This is hooked up under a new mode in ORE that allows for compile-time
budges for a bit more analysis to print more insightful messages. This
mode is currently enabled for -fsave-optimization-record (-Rpass is
trickier since it is controlled in the front-end).

With this we can now print the red remark in 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#L446

[anemet]

Rebase patch-set

[hfinkel]

lib/Transforms/Scalar/GVN.cpp

1217

This iteration order is going to be non-deterministic if there are multiple users; I don't think we can do it this way. Plus, this won't really give the best answer. Unfortunately, actually giving the best answer probably needs to wait for MemorySSA/NewGVN (because looking at other pointer uses won't pick up cases where a smaller load is replaced by part of a larger store, etc.). In the mean time, can we do something deterministic (e.g. sort the other instructions by dominance, pick the last instruction in the last block (perhaps making use of OrderedBasicBlock))?

[anemet]

lib/Transforms/Scalar/GVN.cpp

1217

Thanks, you're right. For now I just bail if there are more than one other users.

I expect this won't be effective so we will soon have to add the analysis you're suggesting.

[anemet]

Only provide the "other" access if there is only one. This makes the result
deterministic.

[hfinkel]

LGTM

include/llvm/Analysis/OptimizationDiagnosticInfo.h

 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_IR_OPTIMIZATIONDIAGNOSTICINFO_H
 #define LLVM_IR_OPTIMIZATIONDIAGNOSTICINFO_H
 
 #include "llvm/ADT/Optional.h"
 #include "llvm/Analysis/BlockFrequencyInfo.h"
 #include "llvm/IR/DiagnosticInfo.h"
+#include "llvm/IR/Function.h"
 #include "llvm/IR/PassManager.h"
 #include "llvm/Pass.h"
 
 namespace llvm {
 class DebugLoc;
-class Function;
 class LLVMContext;
 class Loop;
 class Pass;
 class Twine;
 class Value;
 
 /// The optimization diagnostic interface.
 ///
void emitOptimizationRemarkAnalysisAliasing(const char *PassName,
                                               const DebugLoc &DLoc,
                                               const Value *V, const Twine &Msg);
 
   /// \brief Same as above but derives the IR Value for the code region and the
   /// debug location from the Loop parameter \p L.
   void emitOptimizationRemarkAnalysisAliasing(const char *PassName, Loop *L,
                                               const Twine &Msg);
 
+  /// \brief Whether we allow for extra compile-time budget to perform more
+  /// analysis to produce fewer false positives.
+  ///
+  /// This is useful when reporting missed optimizations.  In this case we can
+  /// use the extra analysis (1) to filter trivial false positives or (2) to
+  /// provide more context so that non-trivial false positives can be quickly
+  /// detected by the user.
+  bool allowExtraAnalysis() const {
+    // For now, only allow this with -fsave-optimization-record since the -Rpass
+    // options are handled in the front-end.
+    return F->getContext().getDiagnosticsOutputFile();
+  }
+
 private:
   Function *F;
 
   BlockFrequencyInfo *BFI;
 
   /// If we generate BFI on demand, we need to free it when ORE is freed.
   std::unique_ptr<BlockFrequencyInfo> OwnedBFI;
 

lib/Transforms/Scalar/GVN.cpp

 }
 
 static bool isLifetimeStart(const Instruction *Inst) {
   if (const IntrinsicInst* II = dyn_cast<IntrinsicInst>(Inst))
     return II->getIntrinsicID() == Intrinsic::lifetime_start;
   return false;
 }
 
+/// \brief Try to locate the three instruction involved in a missed
+/// load-elimination case that is due to an intervening store.
+static void reportMayClobberedLoad(LoadInst *LI, MemDepResult DepInfo,
+                                   DominatorTree *DT,
+                                   OptimizationRemarkEmitter *ORE) {
+  using namespace ore;
+  User *OtherAccess = nullptr;
+
+  OptimizationRemarkMissed R(DEBUG_TYPE, "LoadClobbered", LI);
+  R << "load of type " << NV("Type", LI->getType()) << " not eliminated"
+    << setExtraArgs();
+
+  for (auto *U : LI->getPointerOperand()->users())
+    if (U != LI && (isa<LoadInst>(U) || isa<StoreInst>(U)) &&
+        DT->dominates(cast<Instruction>(U), LI)) {
+      // FIXME: for now give up if there are multiple memory accesses that
+      // dominate the load.  We need further analysis to decide which one is
+      // that we're forwarding from.
+      if (OtherAccess)
+        OtherAccess = nullptr;
+      else
+        OtherAccess = U;
+    }
+
+  if (OtherAccess)
+    R << " in favor of " << NV("OtherAccess", OtherAccess);
+
+  R << " because it is clobbered by " << NV("ClobberedBy", DepInfo.getInst());
+
+  ORE->emit(R);
+}
+
 bool GVN::AnalyzeLoadAvailability(LoadInst *LI, MemDepResult DepInfo,
                                   Value *Address, AvailableValue &Res) {
 
   assert((DepInfo.isDef() || DepInfo.isClobber()) &&
          "expected a local dependence");
   assert(LI->isUnordered() && "rules below are incorrect for ordered access");
 
   const DataLayout &DL = LI->getModule()->getDataLayout();
if (DepInfo.isClobber()) {
     // Nothing known about this clobber, have to be conservative
     DEBUG(
       // fast print dep, using operator<< on instruction is too slow.
       dbgs() << "GVN: load ";
       LI->printAsOperand(dbgs());
       Instruction *I = DepInfo.getInst();
       dbgs() << " is clobbered by " << *I << '\n';
     );
+
+    if (ORE->allowExtraAnalysis())
+      reportMayClobberedLoad(LI, DepInfo, DT, ORE);
+
     return false;
   }
   assert(DepInfo.isDef() && "follows from above");
 
   Instruction *DepInst = DepInfo.getInst();
 
   // Loading the allocation -> undef.
   if (isa<AllocaInst>(DepInst) || isMallocLikeFn(DepInst, TLI) ||

test/Transforms/GVN/opt-remarks.ll

 ; YAML-NEXT: Function:        inst
 ; YAML-NEXT: Args:
 ; YAML-NEXT:   - String:          'load of type '
 ; YAML-NEXT:   - Type:            i32
 ; YAML-NEXT:   - String:          ' eliminated'
 ; YAML-NEXT:   - String:          ' in favor of '
 ; YAML-NEXT:   - InfavorOfValue:  load
 ; YAML-NEXT: ...
-
+; YAML-NEXT: --- !Missed
+; YAML-NEXT: Pass:            gvn
+; YAML-NEXT: Name:            LoadClobbered
+; YAML-NEXT: DebugLoc:        { File: /tmp/s.c, Line: 3, Column: 3 }
+; YAML-NEXT: Function:        may_alias
+; YAML-NEXT: Args:
+; YAML-NEXT:   - String:          'load of type '
+; YAML-NEXT:   - Type:            i32
+; YAML-NEXT:   - String:          ' not eliminated'
+; YAML-NEXT:   - String:          ' in favor of '
+; YAML-NEXT:   - OtherAccess:     load
+; YAML-NEXT:     DebugLoc:        { File: /tmp/s.c, Line: 1, Column: 13 }
+; YAML-NEXT:   - String:          ' because it is clobbered by '
+; YAML-NEXT:   - ClobberedBy:     store
+; YAML-NEXT:     DebugLoc:        { File: /tmp/s.c, Line: 2, Column: 10 }
+; 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
 }
+
+define i32 @may_alias(i32* %p, i32* %r) !dbg !7 {
+entry:
+  %load1 = load i32, i32* %p, !tbaa !13, !dbg !9
+  store i32 4, i32* %r, !tbaa !13, !dbg !10
+  %load = load i32, i32* %p, !tbaa !13, !dbg !11
+  %add = add i32 %load1, %load
+  ret i32 %add
+}
+!llvm.dbg.cu = !{!0}
+!llvm.module.flags = !{!3, !4, !5}
+!llvm.ident = !{!6}
+
+!0 = distinct !DICompileUnit(language: DW_LANG_C99, file: !1, producer: "clang version 4.0.0 (trunk 282540) (llvm/trunk 282542)", isOptimized: true, runtimeVersion: 0, emissionKind: LineTablesOnly, enums: !2)
+!1 = !DIFile(filename: "/tmp/s.c", directory: "/tmp")
+!2 = !{}
+!3 = !{i32 2, !"Dwarf Version", i32 4}
+!4 = !{i32 2, !"Debug Info Version", i32 3}
+!5 = !{i32 1, !"PIC Level", i32 2}
+!6 = !{!"clang version 4.0.0 (trunk 282540) (llvm/trunk 282542)"}
+!7 = distinct !DISubprogram(name: "may_alias", scope: !1, file: !1, line: 1, type: !8, isLocal: false, isDefinition: true, scopeLine: 1, isOptimized: true, unit: !0, variables: !2)
+!8 = !DISubroutineType(types: !2)
+!9 = !DILocation(line: 1, column: 13, scope: !7)
+!10 = !DILocation(line: 2, column: 10, scope: !7)
+!11 = !DILocation(line: 3, column: 3, scope: !7)
+
+!12 = !{ !"tbaa root" }
+!13 = !{ !"int", !12 }