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

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.

1837–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/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> EnableInstructionDelta("print-instruction-delta",
+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,

 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 llvm::Instruction *I,
-                                    llvm::formatted_raw_ostream &OS);
+  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() {}
if (SingleBB && TI->getNumSuccessors() > 1) {
       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 (!EnableInstructionDelta)
+    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 (!EnableInstructionDelta)
+    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
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. The deltas are saved for the
-    // CostAnnotationWriter.
+    // 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 (EnableInstructionDelta)
+  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);

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

-; RUN: opt < %s -inline -debug-only=inline-cost -disable-output -print-instruction-delta |& FileCheck %s
+; RUN: opt < %s -inline -debug-only=inline-cost -disable-output -print-instruction-deltas |& FileCheck %s
 
 ; CHECK:       Analyzing call of callee1... (caller:foo)
 ; CHECK: define i32 @callee1(i32 %x) {
 ; CHECK: ; cost before = -35, cost after = -30, threshold before = 674, threshold after = 674, cost delta = 5
 ; CHECK:   %x1 = add i32 %x, 1
 ; CHECK: ; cost before = -30, cost after = -25, threshold before = 674, threshold after = 674, cost delta = 5
 ; CHECK:   %x2 = add i32 %x1, 1
 ; CHECK: ; cost before = -25, cost after = -20, threshold before = 674, threshold after = 674, cost delta = 5
define i32 @foo(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
 }