[Inliner,OptDiag] Add hotness attribute to opt diagnostics

[anemet]

Summary

The inliner not being a function pass requires the work-around of
generating the OptimizationRemarkEmitter and in turn BFI on demand.
This will go away after the new PM is ready.

BFI is only computed inside ORE if the user has requested hotness information for optimization diagnostitics (-pass-remark-with-hotness at the 'opt' level). Thus there is no additional overhead without the flag.

[anemet]

Rebase on top of r276488.

[eraman]

This computes DominatorTree, LoopInfo, BPI and BFI for *every callsite* that is considered for inlining. Even though this is (I assume) turned off by default, it's still very expensive. Even in the new PM, this can be avoided only by incrementally updating the BFI of the caller after inlining a callee into it.

[anemet]

In D22694#500037, @eraman wrote:

This computes DominatorTree, LoopInfo, BPI and BFI for *every callsite* that is considered for inlining. Even though this is (I assume) turned off by default, it's still very expensive.

Certainly it is off by default and it's meant as a performance analysis tool so the budget is different. That said, we can I guess cache ORE per caller and only invalidate it once we inline. Does that sound reasonable to you?

Even in the new PM, this can be avoided only by incrementally updating the BFI of the caller after inlining a callee into it.

Sure but I thought that was required for PGO-based inlining anyway. I was hoping to piggyback on that.

[eraman]

In D22694#500141, @anemet wrote:

In D22694#500037, @eraman wrote:

This computes DominatorTree, LoopInfo, BPI and BFI for *every callsite* that is considered for inlining. Even though this is (I assume) turned off by default, it's still very expensive.

Certainly it is off by default and it's meant as a performance analysis tool so the budget is different.

Yes, I understand that this is a reporting tool and so the compilation time is not a major constraint. I was wondering if this makes it practical for use in real applications. Perhaps it is. Have you run this on anything large (SPEC, for example) and measured the overhead? I don't have any objections to this patch if you have measured the overhead and found them reasonable.

That said, we can I guess cache ORE per caller and only invalidate it once we inline. Does that sound reasonable to you?

That'll certainly reduce the overhead in the cases where inlining is considered, but does not happen. I am not sure if it is worth the additional complexity though. If you go this route, please isolate the changes to within ORE and invalidate this in emitOptimizationRemark.

Even in the new PM, this can be avoided only by incrementally updating the BFI of the caller after inlining a callee into it.

Sure but I thought that was required for PGO-based inlining anyway. I was hoping to piggyback on that.

Yes, that's true. I didn't mean to say that ORE has to specifically do this.

test/Transforms/Inline/optimization-remarks-with-hotness.ll

1 ↗

(On Diff #65185)

The test case could be vastly simplified. The contents of the functions do not affect the test case.

[anemet]

In D22694#500213, @eraman wrote:

In D22694#500141, @anemet wrote:

In D22694#500037, @eraman wrote:

This computes DominatorTree, LoopInfo, BPI and BFI for *every callsite* that is considered for inlining. Even though this is (I assume) turned off by default, it's still very expensive.

Certainly it is off by default and it's meant as a performance analysis tool so the budget is different.

Yes, I understand that this is a reporting tool and so the compilation time is not a major constraint. I was wondering if this makes it practical for use in real applications. Perhaps it is. Have you run this on anything large (SPEC, for example) and measured the overhead? I don't have any objections to this patch if you have measured the overhead and found them reasonable.

No, I haven't run it with anything yet. I can keep this patch local for now and start doing the evaluation and go from there.

That said, we can I guess cache ORE per caller and only invalidate it once we inline. Does that sound reasonable to you?

That'll certainly reduce the overhead in the cases where inlining is considered, but does not happen. I am not sure if it is worth the additional complexity though. If you go this route, please isolate the changes to within ORE and invalidate this in emitOptimizationRemark.

Yes, certainly. It would be good if as little of this as possible would spill over into the inliner.

[anemet]

test/Transforms/Inline/optimization-remarks-with-hotness.ll

1 ↗

(On Diff #65185)

It is just a copy of optimization-remarks.ll further annotated with !prof metadata. Anyhow, I can simplify it.

[anemet]

In D22694#500213, @eraman wrote:

Yes, I understand that this is a reporting tool and so the compilation time is not a major constraint. I was wondering if this makes it practical for use in real applications. Perhaps it is. Have you run this on anything large (SPEC, for example) and measured the overhead? I don't have any objections to this patch if you have measured the overhead and found them reasonable.

I've run this on SPEC2000_int, SPEC2006_int/fp now and the overhead seems reasonable with a release (no-asserts) compiler. The worst ones were perlbmk (both 2000 and 2006) and omnetpp around 30% slower. The differences trail off quickly afterwards. Also this was done without LTO. LTO is probably worse.

Let me know if you have further questions.

Adam

[anemet]

Simplified the test per @eraman's comments.

[chandlerc]

LGTM w.r.t. to the inliner. Please make sure the other heavy users of remarks are happy as well as you are changing the output mechanism here.

I agree with the sentiment in the patch description that this is a bit gross, but at least seems sufficiently isolated.

include/llvm/Analysis/OptimizationDiagnosticInfo.h

37–38 ↗

(On Diff #67187)

This needs a proper doxygen comment, especially regarding the cost of doing this. And doubly especially that it is free unless the context has the hotness emission specifically enabled. I had to read the implementation to understand why this is OK. =[

I'll also note that this applies to this entire file which seems ... remarkably devoid of doxygen API comments. Please document this interface and infrastructure in subsequent commits. =/

156 ↗

(On Diff #67187)

No need for '\brief'.

[davidxl]

lgtm -- the compile time issue is temporary (and not affecting the default path).

[anemet]

include/llvm/Analysis/OptimizationDiagnosticInfo.h

37–38 ↗

(On Diff #67187)

Actually, I think that only the class comment was missing. The member functions were heavily commented.

Fixed in rL278186.

Thanks to all of you for the reviews!

llvm/trunk/include/llvm/Analysis/OptimizationDiagnosticInfo.h

 // that by using this service passes become dependent on BFI as well.  BFI is
 // used to compute the "hotness" of the diagnostic message.
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_IR_OPTIMIZATIONDIAGNOSTICINFO_H
 #define LLVM_IR_OPTIMIZATIONDIAGNOSTICINFO_H
 
 #include "llvm/ADT/Optional.h"
+#include "llvm/Analysis/BlockFrequencyInfo.h"
 #include "llvm/IR/PassManager.h"
 #include "llvm/Pass.h"
 
 namespace llvm {
-class BlockFrequencyInfo;
 class DebugLoc;
 class Function;
 class LLVMContext;
 class Loop;
 class Pass;
 class Twine;
 class Value;
 
 class OptimizationRemarkEmitter {
 public:
   OptimizationRemarkEmitter(Function *F, BlockFrequencyInfo *BFI)
       : F(F), BFI(BFI) {}
 
+  /// \brief This variant can be used to generate ORE on demand (without the
+  /// analysis pass).
+  ///
+  /// Note that this ctor has a very different cost depending on whether
+  /// F->getContext().getDiagnosticHotnessRequested() is on or not.  If it's off
+  /// the operation is free.
+  ///
+  /// Whereas if DiagnosticHotnessRequested is on, it is fairly expensive
+  /// operation since BFI and all its required analyses are computed.  This is
+  /// for example useful for CGSCC passes that can't use function analyses
+  /// passes in the old PM.
+  OptimizationRemarkEmitter(Function *F);
+
   OptimizationRemarkEmitter(OptimizationRemarkEmitter &&Arg)
       : F(Arg.F), BFI(Arg.BFI) {}
 
   OptimizationRemarkEmitter &operator=(OptimizationRemarkEmitter &&RHS) {
     F = RHS.F;
     BFI = RHS.BFI;
     return *this;
   }
public:
   void emitOptimizationRemarkAnalysisAliasing(const char *PassName, Loop *L,
                                               const Twine &Msg);
 
 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;
+
   Optional<uint64_t> computeHotness(const Value *V);
 
   OptimizationRemarkEmitter(const OptimizationRemarkEmitter &) = delete;
   void operator=(const OptimizationRemarkEmitter &) = delete;
 };
 
 class OptimizationRemarkEmitterWrapperPass : public FunctionPass {
   std::unique_ptr<OptimizationRemarkEmitter> ORE;

llvm/trunk/include/llvm/Transforms/IPO/InlinerPass.h

 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/Transforms/Utils/ImportedFunctionsInliningStatistics.h"
 
 namespace llvm {
 class AssumptionCacheTracker;
 class CallSite;
 class DataLayout;
 class InlineCost;
+class OptimizationRemarkEmitter;
 class ProfileSummaryInfo;
 template <class PtrType, unsigned SmallSize> class SmallPtrSet;
 
 /// This class contains all of the helper code which is used to perform the
 /// inlining operations that do not depend on the policy.
 struct Inliner : public CallGraphSCCPass {
   explicit Inliner(char &ID);
   explicit Inliner(char &ID, bool InsertLifetime);

llvm/trunk/lib/Analysis/OptimizationDiagnosticInfo.cpp

 //===- OptimizationDiagnosticInfo.cpp - Optimization Diagnostic -*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // Optimization diagnostic interfaces.  It's packaged as an analysis pass so
 // that by using this service passes become dependent on BFI as well.  BFI is
 // used to compute the "hotness" of the diagnostic message.
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Analysis/OptimizationDiagnosticInfo.h"
+#include "llvm/Analysis/BranchProbabilityInfo.h"
 #include "llvm/Analysis/LazyBlockFrequencyInfo.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/IR/DiagnosticInfo.h"
+#include "llvm/IR/Dominators.h"
 #include "llvm/IR/LLVMContext.h"
 
 using namespace llvm;
 
+OptimizationRemarkEmitter::OptimizationRemarkEmitter(Function *F)
+    : F(F), BFI(nullptr) {
+  if (!F->getContext().getDiagnosticHotnessRequested())
+    return;
+
+  // First create a dominator tree.
+  DominatorTree DT;
+  DT.recalculate(*F);
+
+  // Generate LoopInfo from it.
+  LoopInfo LI;
+  LI.analyze(DT);
+
+  // Then compute BranchProbabilityInfo.
+  BranchProbabilityInfo BPI;
+  BPI.calculate(*F, LI);
+
+  // Finally compute BFI.
+  OwnedBFI = llvm::make_unique<BlockFrequencyInfo>(*F, BPI, LI);
+  BFI = OwnedBFI.get();
+}
+
 Optional<uint64_t> OptimizationRemarkEmitter::computeHotness(const Value *V) {
   if (!BFI)
     return None;
 
   return BFI->getBlockProfileCount(cast<BasicBlock>(V));
 }
 
 void OptimizationRemarkEmitter::emitOptimizationRemark(const char *PassName,

llvm/trunk/lib/Transforms/IPO/Inliner.cpp

 
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/BasicAliasAnalysis.h"
 #include "llvm/Analysis/CallGraph.h"
 #include "llvm/Analysis/InlineCost.h"
+#include "llvm/Analysis/OptimizationDiagnosticInfo.h"
 #include "llvm/Analysis/ProfileSummaryInfo.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/IR/CallSite.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/DiagnosticInfo.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/Module.h"
for (unsigned AllocaNo = 0, e = IFI.StaticAllocas.size(); AllocaNo != e;
     // operation.
     AllocasForType.push_back(AI);
     UsedAllocas.insert(AI);
   }
 
   return true;
 }
 
-static void emitAnalysis(CallSite CS, const Twine &Msg) {
-  Function *Caller = CS.getCaller();
-  LLVMContext &Ctx = Caller->getContext();
-  DebugLoc DLoc = CS.getInstruction()->getDebugLoc();
-  emitOptimizationRemarkAnalysis(Ctx, DEBUG_TYPE, *Caller, DLoc, Msg);
+static void emitAnalysis(CallSite CS, OptimizationRemarkEmitter &ORE,
+                         const Twine &Msg) {
+  ORE.emitOptimizationRemarkAnalysis(DEBUG_TYPE, CS.getInstruction(), Msg);
 }
 
 /// Return true if inlining of CS can block the caller from being
 /// inlined which is proved to be more beneficial. \p IC is the
 /// estimated inline cost associated with callsite \p CS.
 /// \p TotalAltCost will be set to the estimated cost of inlining the caller
 /// if \p CS is suppressed for inlining.
 static bool
shouldBeDeferred(Function *Caller, CallSite CS, InlineCost IC,
   if (inliningPreventsSomeOuterInline && TotalSecondaryCost < IC.getCost())
     return true;
 
   return false;
 }
 
 /// Return true if the inliner should attempt to inline at the given CallSite.
 static bool shouldInline(CallSite CS,
-                         function_ref<InlineCost(CallSite CS)> GetInlineCost) {
+                         function_ref<InlineCost(CallSite CS)> GetInlineCost,
+                         OptimizationRemarkEmitter &ORE) {
   InlineCost IC = GetInlineCost(CS);
 
   if (IC.isAlways()) {
     DEBUG(dbgs() << "    Inlining: cost=always"
                  << ", Call: " << *CS.getInstruction() << "\n");
-    emitAnalysis(CS, Twine(CS.getCalledFunction()->getName()) +
+    emitAnalysis(CS, ORE, Twine(CS.getCalledFunction()->getName()) +
                               " should always be inlined (cost=always)");
     return true;
   }
 
   if (IC.isNever()) {
     DEBUG(dbgs() << "    NOT Inlining: cost=never"
                  << ", Call: " << *CS.getInstruction() << "\n");
-    emitAnalysis(CS, Twine(CS.getCalledFunction()->getName() +
+    emitAnalysis(CS, ORE, Twine(CS.getCalledFunction()->getName() +
                                 " should never be inlined (cost=never)"));
     return false;
   }
 
   Function *Caller = CS.getCaller();
   if (!IC) {
     DEBUG(dbgs() << "    NOT Inlining: cost=" << IC.getCost()
                  << ", thres=" << (IC.getCostDelta() + IC.getCost())
                  << ", Call: " << *CS.getInstruction() << "\n");
-    emitAnalysis(CS, Twine(CS.getCalledFunction()->getName() +
+    emitAnalysis(CS, ORE, Twine(CS.getCalledFunction()->getName() +
                                 " too costly to inline (cost=") +
                               Twine(IC.getCost()) + ", threshold=" +
                               Twine(IC.getCostDelta() + IC.getCost()) + ")");
     return false;
   }
 
   int TotalSecondaryCost = 0;
   if (shouldBeDeferred(Caller, CS, IC, TotalSecondaryCost, GetInlineCost)) {
     DEBUG(dbgs() << "    NOT Inlining: " << *CS.getInstruction()
                  << " Cost = " << IC.getCost()
                  << ", outer Cost = " << TotalSecondaryCost << '\n');
-    emitAnalysis(CS, Twine("Not inlining. Cost of inlining " +
-                           CS.getCalledFunction()->getName() +
-                           " increases the cost of inlining " +
-                           CS.getCaller()->getName() + " in other contexts"));
+    emitAnalysis(CS, ORE,
+                 Twine("Not inlining. Cost of inlining " +
     return false;
   }
 
   DEBUG(dbgs() << "    Inlining: cost=" << IC.getCost()
                << ", thres=" << (IC.getCostDelta() + IC.getCost())
                << ", Call: " << *CS.getInstruction() << '\n');
-  emitAnalysis(
-      CS, CS.getCalledFunction()->getName() + Twine(" can be inlined into ") +
-              CS.getCaller()->getName() + " with cost=" + Twine(IC.getCost()) +
-              " (threshold=" + Twine(IC.getCostDelta() + IC.getCost()) + ")");
+  emitAnalysis(CS, ORE, CS.getCalledFunction()->getName() +
+                            Twine(" can be inlined into ") +
+                            CS.getCaller()->getName() + " with cost=" +
+                            Twine(IC.getCost()) + " (threshold=" +
+                            Twine(IC.getCostDelta() + IC.getCost()) + ")");
   return true;
 }
 
 /// Return true if the specified inline history ID
 /// indicates an inline history that includes the specified function.
 static bool InlineHistoryIncludes(
     Function *F, int InlineHistoryID,
     const SmallVectorImpl<std::pair<Function *, int>> &InlineHistory) {
for (unsigned CSi = 0; CSi != CallSites.size(); ++CSi) {
         // itself.  If so, we'd be recursively inlining the same function,
         // which would provide the same callsites, which would cause us to
         // infinitely inline.
         int InlineHistoryID = CallSites[CSi].second;
         if (InlineHistoryID != -1 &&
             InlineHistoryIncludes(Callee, InlineHistoryID, InlineHistory))
           continue;
 
-        LLVMContext &CallerCtx = Caller->getContext();
-
         // Get DebugLoc to report. CS will be invalid after Inliner.
         DebugLoc DLoc = CS.getInstruction()->getDebugLoc();
+        BasicBlock *Block = CS.getParent();
+        // FIXME for new PM: because of the old PM we currently generate ORE and
+        // in turn BFI on demand.  With the new PM, the ORE dependency should
+        // just become a regular analysis dependency.
+        OptimizationRemarkEmitter ORE(Caller);
 
         // If the policy determines that we should inline this function,
         // try to do so.
-        if (!shouldInline(CS, GetInlineCost)) {
-          emitOptimizationRemarkMissed(CallerCtx, DEBUG_TYPE, *Caller, DLoc,
+        if (!shouldInline(CS, GetInlineCost, ORE)) {
+          ORE.emitOptimizationRemarkMissed(DEBUG_TYPE, DLoc, Block,
                                            Twine(Callee->getName() +
                                                  " will not be inlined into " +
                                                  Caller->getName()));
           continue;
         }
 
         // Attempt to inline the function.
         if (!InlineCallIfPossible(CS, InlineInfo, InlinedArrayAllocas,
                                   InlineHistoryID, InsertLifetime, AARGetter,
                                   ImportedFunctionsStats)) {
-          emitOptimizationRemarkMissed(CallerCtx, DEBUG_TYPE, *Caller, DLoc,
+          ORE.emitOptimizationRemarkMissed(DEBUG_TYPE, DLoc, Block,
                                            Twine(Callee->getName() +
                                                  " will not be inlined into " +
                                                  Caller->getName()));
           continue;
         }
         ++NumInlined;
 
         // Report the inline decision.
-        emitOptimizationRemark(
-            CallerCtx, DEBUG_TYPE, *Caller, DLoc,
+        ORE.emitOptimizationRemark(
+            DEBUG_TYPE, DLoc, Block,
             Twine(Callee->getName() + " inlined into " + Caller->getName()));
 
         // If inlining this function gave us any new call sites, throw them
         // onto our worklist to process.  They are useful inline candidates.
         if (!InlineInfo.InlinedCalls.empty()) {
           // Create a new inline history entry for this, so that we remember
           // that these new callsites came about due to inlining Callee.
           int NewHistoryID = InlineHistory.size();

llvm/trunk/test/Transforms/Inline/optimization-remarks-with-hotness.ll

+; RUN: opt < %s -inline -pass-remarks=inline -pass-remarks-missed=inline \
+; RUN:     -pass-remarks-analysis=inline -pass-remarks-with-hotness -S 2>&1 \
+; RUN:     | FileCheck %s
+
+; CHECK: foo should always be inlined (cost=always) (hotness: 30)
+; CHECK: foo inlined into bar (hotness: 30)
+; CHECK: foz should never be inlined (cost=never) (hotness: 30)
+; CHECK: foz will not be inlined into bar (hotness: 30)
+
+; Function Attrs: alwaysinline nounwind uwtable
+define i32 @foo() #0 !prof !1 {
+entry:
+  ret i32 4
+}
+
+; Function Attrs: noinline nounwind uwtable
+define i32 @foz() #1 !prof !2 {
+entry:
+  ret i32 2
+}
+
+; Function Attrs: nounwind uwtable
+define i32 @bar() !prof !3 {
+entry:
+  %call = call i32 @foo()
+  %call2 = call i32 @foz()
+  %mul = mul i32 %call, %call2
+  ret i32 %mul
+}
+
+attributes #0 = { alwaysinline }
+attributes #1 = { noinline }
+
+!llvm.ident = !{!0}
+
+!0 = !{!"clang version 3.5.0 "}
+!1 = !{!"function_entry_count", i64 10}
+!2 = !{!"function_entry_count", i64 20}
+!3 = !{!"function_entry_count", i64 30}