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

1832–1833

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

107

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

578

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

103

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

118

Is all this necessary?

[knaumov]

Changed unnecessarily complicated test

[apilipenko]

llvm/lib/Analysis/InlineCost.cpp

105–110

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.

103

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

104

Suggest InstructionCostDetail.

115–118

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

51

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

118–119

There are still redundant llvm:: prefixes.

1823–1827

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<bool> EnableCostAnnotationWriter("print-cost-annotation-writer",
+                                             cl::Hidden, cl::init(false));
+
 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<int>
     ColdCallSiteThreshold("inline-cold-callsite-threshold", cl::Hidden,
                           cl::init(45), cl::ZeroOrMore,
                           cl::desc("Threshold for inlining cold callsites"));

 
 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;
+
+struct InliningCostDetail {int Cost; int Threshold;};
+
+class CostAnnotationWriter : public AssemblyAnnotationWriter {
+public:
+  // This DenseMap stores the delta change in cost and threshold after
+  // accounting for the given instruction.
+  llvm::DenseMap <const Instruction *, InliningCostDetail> CostThresholdMap;
+
+  virtual void emitInstructionAnnot(const llvm::Instruction *I,
+                                    llvm::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;
 
   /// Getter for the cache of @llvm.assume intrinsics.
   std::function<AssumptionCache &(Function &)> &GetAssumptionCache;
 
   /// Getter for BlockFrequencyInfo
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 (!EnableCostAnnotationWriter)
+        return ;
+    Writer.CostThresholdMap[I].Cost = Cost;
+    Writer.CostThresholdMap[I].Threshold = Threshold;
+  }
+
+  void onInstructionAnalysisFinish(const Instruction *I) override {
+    // This function is called to find the difference between the value before
+    // assessment of the given instruction and after.
+    if (!EnableCostAnnotationWriter)
+        return ;
+    Writer.CostThresholdMap[I].Cost = Cost - Writer.CostThresholdMap[I].Cost;
+    Writer.CostThresholdMap[I].Threshold = Threshold -
+                                        Writer.CostThresholdMap[I].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);
   EnabledSROAArgValues.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 = " << CostThresholdMap[I].Cost;
+    if (CostThresholdMap[I].Threshold)
+        OS << ", threshold delta = " << CostThresholdMap[I].Threshold;
+    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.
+    // cost should count against inlining. The deltas are saved for the
+    // CostAnnotationWriter.
+    onInstructionAnalysisStart(&*I);
+
     if (Base::visit(&*I))
       ++NumInstructionsSimplified;
     else
       onCommonInstructionSimplification();
 
+    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 (EnableCostAnnotationWriter)
+    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/DebugInfo/debuginline-cost-delta.ll

+; RUN: opt < %s -inline -debug-only=inline-cost -disable-output -print-cost-annotation-writer |& FileCheck %s
+
+; CHECK:         Analyzing call of _Z3sumii... (caller:main)
+; CHECK: define i32 @_Z3sumii(i32 %x, i32 %y) !dbg !6 {
+; CHECK: entry:
+; CHECK: ; cost = 5
+; CHECK:   %x.addr = alloca i32, align 4
+; CHECK: ; cost = 5
+; CHECK:   %y.addr = alloca i32, align 4
+; CHECK: ; cost = 5
+; CHECK:   store i32 %x, i32* %x.addr, align 4
+; CHECK: ; cost = 5
+; CHECK:   store i32 %y, i32* %y.addr, align 4
+; CHECK: ; cost = 5
+; CHECK:   %0 = load i32, i32* %x.addr, align 4, !dbg !8
+; CHECK: ; cost = 5
+; CHECK:   %1 = load i32, i32* %y.addr, align 4, !dbg !8
+; CHECK: ; cost = 5
+; CHECK:   %add = add nsw i32 %0, %1, !dbg !8
+; CHECK: ; cost = 0
+; CHECK:   ret i32 %add, !dbg !8
+; CHECK: }
+; CHECK:      NumConstantArgs: 0
+; CHECK:      NumConstantOffsetPtrArgs: 0
+; CHECK:      NumAllocaArgs: 0
+; CHECK:      NumConstantPtrCmps: 0
+; CHECK:      NumConstantPtrDiffs: 0
+; CHECK:      NumInstructionsSimplified: 1
+; CHECK:      NumInstructions: 8
+; CHECK:      SROACostSavings: 0
+; CHECK:      SROACostSavingsLost: 0
+; CHECK:      LoadEliminationCost: 0
+; CHECK:      ContainsNoDuplicateCall: 0
+; CHECK:      Cost: -5
+; CHECK:      Threshold: 337
+
+; Original C++ test case
+;
+; #include <stdio.h>
+;
+; int sum(int x, int y) {
+;   return x + y;
+; }
+;
+; int main() {
+;   int s, i = 0;
+;   while (i++ < 20000 * 20000)
+;     if (i != 100) s = sum(i, s); else s = 30;
+;   printf("sum is %d\n", s);
+;   return 0;
+; }
+;
+@.str = private unnamed_addr constant [11 x i8] c"sum is %d\0A\00", align 1
+
+; Function Attrs: nounwind uwtable
+define i32 @_Z3sumii(i32 %x, i32 %y) !dbg !4 {
+entry:
+  %x.addr = alloca i32, align 4
+  %y.addr = alloca i32, align 4
+  store i32 %x, i32* %x.addr, align 4
+  store i32 %y, i32* %y.addr, align 4
+  %0 = load i32, i32* %x.addr, align 4, !dbg !11
+  %1 = load i32, i32* %y.addr, align 4, !dbg !11
+  %add = add nsw i32 %0, %1, !dbg !11
+  ret i32 %add, !dbg !11
+}
+
+; Function Attrs: uwtable
+define i32 @main() !dbg !7 {
+entry:
+  %retval = alloca i32, align 4
+  %s = alloca i32, align 4
+  %i = alloca i32, align 4
+  store i32 0, i32* %retval
+  store i32 0, i32* %i, align 4, !dbg !12
+  br label %while.cond, !dbg !13
+
+while.cond:                                       ; preds = %if.end, %entry
+  %0 = load i32, i32* %i, align 4, !dbg !14
+  %inc = add nsw i32 %0, 1, !dbg !14
+  store i32 %inc, i32* %i, align 4, !dbg !14
+  %cmp = icmp slt i32 %0, 400000000, !dbg !14
+  br i1 %cmp, label %while.body, label %while.end, !dbg !14
+
+while.body:                                       ; preds = %while.cond
+  %1 = load i32, i32* %i, align 4, !dbg !16
+  %cmp1 = icmp ne i32 %1, 100, !dbg !16
+  br i1 %cmp1, label %if.then, label %if.else, !dbg !16
+
+
+if.then:                                          ; preds = %while.body
+  %2 = load i32, i32* %i, align 4, !dbg !18
+  %3 = load i32, i32* %s, align 4, !dbg !18
+  %call = call i32 @_Z3sumii(i32 %2, i32 %3), !dbg !18
+  store i32 %call, i32* %s, align 4, !dbg !18
+  br label %if.end, !dbg !18
+
+if.else:                                          ; preds = %while.body
+  store i32 30, i32* %s, align 4, !dbg !20
+  br label %if.end
+
+if.end:                                           ; preds = %if.else, %if.then
+  br label %while.cond, !dbg !22
+
+while.end:                                        ; preds = %while.cond
+  %4 = load i32, i32* %s, align 4, !dbg !24
+  %call2 = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([11 x i8], [11 x i8]* @.str, i32 0, i32 0), i32 %4), !dbg !24
+  ret i32 0, !dbg !25
+}
+
+declare i32 @printf(i8*, ...) #2
+
+!llvm.dbg.cu = !{!0}
+!llvm.module.flags = !{!8, !9}
+!llvm.ident = !{!10}
+
+!0 = distinct !DICompileUnit(language: DW_LANG_C_plus_plus, producer: "clang version 3.5 ", isOptimized: false, emissionKind: NoDebug, file: !1, enums: !2, retainedTypes: !2, globals: !2, imports: !2)
+!1 = !DIFile(filename: "calls.cc", directory: ".")
+!2 = !{}
+!4 = distinct !DISubprogram(name: "sum", line: 3, isLocal: false, isDefinition: true, virtualIndex: 6, flags: DIFlagPrototyped, isOptimized: false, unit: !0, scopeLine: 3, file: !1, scope: !5, type: !6, retainedNodes: !2)
+!5 = !DIFile(filename: "calls.cc", directory: ".")
+!6 = !DISubroutineType(types: !2)
+!7 = distinct !DISubprogram(name: "main", line: 7, isLocal: false, isDefinition: true, virtualIndex: 6, flags: DIFlagPrototyped, isOptimized: false, unit: !0, scopeLine: 7, file: !1, scope: !5, type: !6, retainedNodes: !2)
+!8 = !{i32 2, !"Dwarf Version", i32 4}
+!9 = !{i32 1, !"Debug Info Version", i32 3}
+!10 = !{!"clang version 3.5 "}
+!11 = !DILocation(line: 4, scope: !4)
+!12 = !DILocation(line: 8, scope: !7)
+!13 = !DILocation(line: 9, scope: !7)
+!14 = !DILocation(line: 9, scope: !15)
+!15 = !DILexicalBlockFile(discriminator: 2, file: !1, scope: !7)
+!16 = !DILocation(line: 10, scope: !17)
+!17 = distinct !DILexicalBlock(line: 10, column: 0, file: !1, scope: !7)
+!18 = !DILocation(line: 10, scope: !19)
+!19 = !DILexicalBlockFile(discriminator: 2, file: !1, scope: !17)
+!20 = !DILocation(line: 10, scope: !21)
+!21 = !DILexicalBlockFile(discriminator: 4, file: !1, scope: !17)
+!22 = !DILocation(line: 10, scope: !23)
+!23 = !DILexicalBlockFile(discriminator: 6, file: !1, scope: !17)
+!24 = !DILocation(line: 11, scope: !7)
+!25 = !DILocation(line: 12, scope: !7)