Cost Annotation Writer for InlineCost

[knaumov]

Summary

The patch adds extra diagnostics for the inline cost analysis. The diagnostic is available under the new command line flag ("print-cost-annotation-writer") for the "inline-cost" pass. When enabled along with -debug-only=inline-cost it prints the IR of inline candidate annotated with cost and threshold increase per every instruction.
This should help analyze inliner decisions.

[apilipenko]

llvm/lib/Analysis/InlineCost.cpp

1846–1847

Code style, { should be on the same line. Please clang-format.

[knaumov]

Refactoring

[knaumov]

ping

[davidxl]

This looks useful. Is it possible to add a test case?

[knaumov]

Sorry for the delay due to the changes in structure of InlineCost.cpp in this patch: https://reviews.llvm.org/D71733 .
Structural changes mostly.
Added test to llvm/test/DebugInfo to test the new flag.

[mtrofin]

llvm/lib/Analysis/InlineCost.cpp

113

Nit: consider replacing std::pair<int,int> with a struct, e.g. struct InliningCostDetail {int Cost, int Threshold} - for readability.

587

I initially thought that the map stores a snapshot of Cost & Threshold values. It seems it actually stores cost and threshold variations due to the analysis of a specific instruction - relative cost of that one instruction, and threshold effects.

If that's correct, could you please detail this in the comment describing the map (or struct members, if using a struct instead of std::pair)

[knaumov]

Changed pait<int, int> to struct InlineCostDetails in DenseMap and changed comment defining CostThrehsoldMap.
@mtrofin : Yes, the DenseMap stores the delta of the cost and threshold after inlining the instruction, not just a snapshot.
This is done in order to see the exact cost/change in the threshold it would take to inline the instruction.

[mtrofin]

lgtm

llvm/lib/Analysis/InlineCost.cpp

109

Nit: CostDelta / ThresholdDelta? (I realize I proposed 'Cost/Threshold' initially, but that was before understanding the usage further below)

Also nit: now that we have a struct, if we had CostBefore/CostAfter and ThresholdBefore/ThresholdAfter, the intent would be even more evident, and we could, if we wanted, also output the raw costs (i.e. costs and delta). But this could be done at a later stage, too.

[knaumov]

Answering @mtrofin comments.
Refactoring, little changes:

• Separated the initial flag into two: one prints the whole info on instruction cost and threshold, the other one prints only deltas of cost and threshold
• Changed the InlineCostDetail structure - introduced CostBefore, CostAfter, CostDelta, ThresholdBefore, ThresholdAfter, ThresholdDelta
• Changed the test that I wrote to match the check of new flags
• Little comment changes

[knaumov]

ping

[RKSimon]

llvm/test/DebugInfo/debuginline-cost-delta.ll

117 ↗

(On Diff #239366)

Is all this necessary?

[knaumov]

Changed unnecessarily complicated test

[apilipenko]

llvm/lib/Analysis/InlineCost.cpp

111–116

You don't have to store deltas in the struct. They are easily computable from other fields.

[knaumov]

Resolving @apilipenko suggestions.
Removed deltas from the struct.

[knaumov]

ping

[apilipenko]

llvm/lib/Analysis/InlineCost.cpp

51–57

Suggest to print all the details under one flag.

109

// This struct is used to store information about inline cost of a particular instruction

110

Suggest InstructionCostDetail.

121–124

No need to use llvm:: namespace prefix.

[knaumov]

Addressed @apilipenko 's comments

• Switched to one flag
• Small changes in struct and comments

[apilipenko]

Couple of nit comments inlined, LGTM once addressed.

llvm/lib/Analysis/InlineCost.cpp

56

Suggest to rename the global and the flag to PrintDebugInstructionDeltas("print-instruction-deltas", ...)

124–125

There are still redundant llvm:: prefixes.

1838–1841

This comment is specific to InlineCostCallAnalyzer and doesn't belong here.

[knaumov]

Fixed small inaccuracies
As the patch is done, @apilipenko , can you please push it for me?

[knaumov]

Sorry, wrong diff

llvm/lib/Analysis/InlineCost.cpp

 #include "llvm/Analysis/CodeMetrics.h"
 #include "llvm/Analysis/ConstantFolding.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/ProfileSummaryInfo.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/Config/llvm-config.h"
+#include "llvm/IR/AssemblyAnnotationWriter.h"
 #include "llvm/IR/CallingConv.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/GetElementPtrTypeIterator.h"
 #include "llvm/IR/GlobalAlias.h"
 #include "llvm/IR/InstVisitor.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/Operator.h"
 #include "llvm/IR/PatternMatch.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
+#include "llvm/Support/FormattedStream.h"
 #include "llvm/Support/raw_ostream.h"
 
 using namespace llvm;
 
 #define DEBUG_TYPE "inline-cost"
 
 STATISTIC(NumCallsAnalyzed, "Number of call sites analyzed");
 
 static cl::opt<int>
     DefaultThreshold("inlinedefault-threshold", cl::Hidden, cl::init(225),
                      cl::ZeroOrMore,
                      cl::desc("Default amount of inlining to perform"));
 
+static cl::opt<bool> PrintDebugInstructionDeltas("print-instruction-deltas",
+    cl::Hidden, cl::init(false),
+    cl::desc("Prints deltas of cost and threshold per instruction"));
+
 static cl::opt<int> InlineThreshold(
     "inline-threshold", cl::Hidden, cl::init(225), cl::ZeroOrMore,
     cl::desc("Control the amount of inlining to perform (default = 225)"));
 
 static cl::opt<int> HintThreshold(
     "inlinehint-threshold", cl::Hidden, cl::init(325), cl::ZeroOrMore,
     cl::desc("Threshold for inlining functions with inline hint"));
 

 
 static cl::opt<bool> OptComputeFullInlineCost(
     "inline-cost-full", cl::Hidden, cl::init(false), cl::ZeroOrMore,
     cl::desc("Compute the full inline cost of a call site even when the cost "
              "exceeds the threshold."));
 
 namespace {
 class InlineCostCallAnalyzer;
+
+// This struct is used to store information about inline cost of a
+// particular instruction
+struct InstructionCostDetail {
+  int CostBefore;
+  int CostAfter;
+  int ThresholdBefore;
+  int ThresholdAfter;
+};
+
+class CostAnnotationWriter : public AssemblyAnnotationWriter {
+public:
+  // This DenseMap stores the delta change in cost and threshold after
+  // accounting for the given instruction.
+  DenseMap <const Instruction *, InstructionCostDetail> CostThresholdMap;
+
+  virtual void emitInstructionAnnot(const Instruction *I,
+                                        formatted_raw_ostream &OS);
+};
+
 class CallAnalyzer : public InstVisitor<CallAnalyzer, bool> {
   typedef InstVisitor<CallAnalyzer, bool> Base;
   friend class InstVisitor<CallAnalyzer, bool>;
 
 protected:
   virtual ~CallAnalyzer() {}
   /// The TargetTransformInfo available for this compilation.
   const TargetTransformInfo &TTI;
protected:
   /// analysis in the caller function; we want the inline cost query to be
   /// easily cacheable. Instead, use the cover function paramHasAttr.
   CallBase &CandidateCall;
 
   /// Extension points for handling callsite features.
   /// Called after a basic block was analyzed.
   virtual void onBlockAnalyzed(const BasicBlock *BB) {}
 
+  /// Called before an instruction was analyzed
+  virtual void onInstructionAnalysisStart(const Instruction *I) {}
+
+  /// Called after an instruction was analyzed
+  virtual void onInstructionAnalysisFinish(const Instruction *I) {}
+
   /// Called at the end of the analysis of the callsite. Return the outcome of
   /// the analysis, i.e. 'InlineResult(true)' if the inlining may happen, or
   /// the reason it can't.
   virtual InlineResult finalizeAnalysis() { return InlineResult::success(); }
   /// Called when we're about to start processing a basic block, and every time
   /// we are done processing an instruction. Return true if there is no point in
   /// continuing the analysis (e.g. we've determined already the call site is
   /// too expensive to inline)
void onBlockAnalyzed(const BasicBlock *BB) override {
     // inlining.
     if (SingleBB && TI->getNumSuccessors() > 1) {
       // Take off the bonus we applied to the threshold.
       Threshold -= SingleBBBonus;
       SingleBB = false;
     }
   }
 
+  void onInstructionAnalysisStart(const Instruction *I) override {
+    // This function is called to store the initial cost of inlining before
+    // the given instruction was assessed.
+    if (!PrintDebugInstructionDeltas)
+        return ;
+    Writer.CostThresholdMap[I].CostBefore = Cost;
+    Writer.CostThresholdMap[I].ThresholdBefore = Threshold;
+  }
+
+  void onInstructionAnalysisFinish(const Instruction *I) override {
+    // This function is called to find new values of cost and threshold after
+    // the instruction has been assessed.
+    if (!PrintDebugInstructionDeltas)
+        return ;
+    Writer.CostThresholdMap[I].CostAfter = Cost;
+    Writer.CostThresholdMap[I].ThresholdAfter = Threshold;
+  }
+
   InlineResult finalizeAnalysis() override {
     // Loops generally act a lot like calls in that they act like barriers to
     // movement, require a certain amount of setup, etc. So when optimising for
     // size, we penalise any call sites that perform loops. We do this after all
     // other costs here, so will likely only be dealing with relatively small
     // functions (and hence DT and LI will hopefully be cheap).
     auto *Caller = CandidateCall.getFunction();
     if (Caller->hasMinSize()) {
InlineCostCallAnalyzer(
       Optional<function_ref<BlockFrequencyInfo &(Function &)>> &GetBFI,
       ProfileSummaryInfo *PSI, OptimizationRemarkEmitter *ORE, Function &Callee,
       CallBase &Call, const InlineParams &Params, bool BoostIndirect = true)
       : CallAnalyzer(TTI, GetAssumptionCache, GetBFI, PSI, ORE, Callee, Call),
         ComputeFullInlineCost(OptComputeFullInlineCost ||
                               Params.ComputeFullInlineCost || ORE),
         Params(Params), Threshold(Params.DefaultThreshold),
         BoostIndirectCalls(BoostIndirect) {}
+
+  /// Annotation Writer for cost annotation
+  CostAnnotationWriter Writer;
+
   void dump();
 
   virtual ~InlineCostCallAnalyzer() {}
   int getThreshold() { return Threshold; }
   int getCost() { return Cost; }
 };
 } // namespace
 
 /// Test whether the given value is an Alloca-derived function argument.
 bool CallAnalyzer::isAllocaDerivedArg(Value *V) {
   return SROAArgValues.count(V);
 }
 
 void CallAnalyzer::disableSROAForArg(AllocaInst *SROAArg) {
   onDisableSROA(SROAArg);
   EnabledSROAAllocas.erase(SROAArg);
   disableLoadElimination();
 }
+
+void CostAnnotationWriter::emitInstructionAnnot(
+    const Instruction *I, formatted_raw_ostream &OS) {
+    // The cost of inlining of the given instruction is printed always.
+    // The threshold delta is printed only when it is non-zero. It happens
+    // when we decided to give a bonus at a particular instruction.
+    OS << "; cost before = " << CostThresholdMap[I].CostBefore <<
+              ", cost after = " << CostThresholdMap[I].CostAfter <<
+              ", threshold before = " << CostThresholdMap[I].ThresholdBefore <<
+              ", threshold after = " << CostThresholdMap[I].ThresholdAfter <<
+              ", ";
+    OS << "cost delta = " << CostThresholdMap[I].CostAfter -
+                                CostThresholdMap[I].CostBefore;
+    if (CostThresholdMap[I].ThresholdAfter != CostThresholdMap[I].ThresholdBefore)
+      OS << ", threshold delta = " << CostThresholdMap[I].ThresholdAfter -
+                                CostThresholdMap[I].ThresholdBefore;
+    OS << "\n";
+}
+
 /// If 'V' maps to a SROA candidate, disable SROA for it.
 void CallAnalyzer::disableSROA(Value *V) {
   if (auto *SROAArg = getSROAArgForValueOrNull(V)) {
     disableSROAForArg(SROAArg);
   }
 }
 
 void CallAnalyzer::disableLoadElimination() {
for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) {
     ++NumInstructions;
     if (isa<ExtractElementInst>(I) || I->getType()->isVectorTy())
       ++NumVectorInstructions;
 
     // If the instruction simplified to a constant, there is no cost to this
     // instruction. Visit the instructions using our InstVisitor to account for
     // all of the per-instruction logic. The visit tree returns true if we
     // consumed the instruction in any way, and false if the instruction's base
     // cost should count against inlining.
+    onInstructionAnalysisStart(&*I);
+
     if (Base::visit(&*I))
       ++NumInstructionsSimplified;
     else
       onMissedSimplification();
 
+    onInstructionAnalysisFinish(&*I);
     using namespace ore;
     // If the visit this instruction detected an uninlinable pattern, abort.
     InlineResult IR = InlineResult::success();
     if (IsRecursiveCall)
       IR = InlineResult::failure("recursive");
     else if (ExposesReturnsTwice)
       IR = InlineResult::failure("exposes returns twice");
     else if (HasDynamicAlloca)
       IR = InlineResult::failure("dynamic alloca");
InlineResult CallAnalyzer::analyze() {
 
   return finalizeAnalysis();
 }
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 /// Dump stats about this call's analysis.
 LLVM_DUMP_METHOD void InlineCostCallAnalyzer::dump() {
 #define DEBUG_PRINT_STAT(x) dbgs() << "      " #x ": " << x << "\n"
+  if (PrintDebugInstructionDeltas)
+    F.print(dbgs(), &Writer);
   DEBUG_PRINT_STAT(NumConstantArgs);
   DEBUG_PRINT_STAT(NumConstantOffsetPtrArgs);
   DEBUG_PRINT_STAT(NumAllocaArgs);
   DEBUG_PRINT_STAT(NumConstantPtrCmps);
   DEBUG_PRINT_STAT(NumConstantPtrDiffs);
   DEBUG_PRINT_STAT(NumInstructionsSimplified);
   DEBUG_PRINT_STAT(NumInstructions);
   DEBUG_PRINT_STAT(SROACostSavings);

llvm/test/Transforms/Inline/debuginline-cost-delta.ll

+; RUN: opt < %s -inline -debug-only=inline-cost -disable-output -print-instruction-deltas 2>&1 | FileCheck %s
+
+; CHECK:       Analyzing call of callee1... (caller:foo)
+; CHECK: define i32 @callee1(i32 %x) {
+; CHECK: ; cost before = {{.*}}, cost after = {{.*}}, threshold before = {{.*}}, threshold after = {{.*}}, cost delta = 5
+; CHECK:   %x1 = add i32 %x, 1
+; CHECK: ; cost before = {{.*}}, cost after = {{.*}}, threshold before = {{.*}}, threshold after = {{.*}}, cost delta = 5
+; CHECK:   %x2 = add i32 %x1, 1
+; CHECK: ; cost before = {{.*}}, cost after = {{.*}}, threshold before = {{.*}}, threshold after = {{.*}}, cost delta = 5
+; CHECK:   %x3 = add i32 %x2, 1
+; CHECK: ; cost before = {{.*}}, cost after = {{.*}}, threshold before = {{.*}}, threshold after = {{.*}}, cost delta = 0
+; CHECK:   ret i32 %x3
+; CHECK: }
+; CHECK:      NumConstantArgs: 0
+; CHECK:      NumConstantOffsetPtrArgs: 0
+; CHECK:      NumAllocaArgs: 0
+; CHECK:      NumConstantPtrCmps: 0
+; CHECK:      NumConstantPtrDiffs: 0
+; CHECK:      NumInstructionsSimplified: 1
+; CHECK:      NumInstructions: 4
+; CHECK:      SROACostSavings: 0
+; CHECK:      SROACostSavingsLost: 0
+; CHECK:      LoadEliminationCost: 0
+; CHECK:      ContainsNoDuplicateCall: 0
+; CHECK:      Cost: {{.*}}
+; CHECK:      Threshold: {{.*}}
+
+define i32 @foo(i32 %y) {
+  %x = call i32 @callee1(i32 %y)
+  ret i32 %x
+}
+
+define i32 @callee1(i32 %x) {
+  %x1 = add i32 %x, 1
+  %x2 = add i32 %x1, 1
+  %x3 = add i32 %x2, 1
+  ret i32 %x3
+}