[AutoFDO] Statistic for context sensitive profile guided inlining

[wenlei]

Summary

AutoFDO compilation has two places that do inlining - the sample profile loader that does inlining with context sensitive profile, and the regular inliner as CGSCC pass. Ideally we want most inlining to come from sample profile loader as that is driven by context sensitive profile and also retains context sensitivity after inlining. However the reality is most of the inlining actually happens during regular inliner. To track the number of inline instances from sample profile loader and help move more inlining to sample profile loader, I'm adding statistics and optimization remarks for sample profile loader's inlining.

[wmi]

However the reality is most of the inlining actually happens during regular inliner.

I would imagine among all the functions with inline instance in profile, only those small and warm/cold functions which are not inlined in early inliner will be inlined in regular inliner. The number of those small/warm and small/cold functions may be large. We found it was helpful to inline warm functions before (but have to pay some cost of code size increase. It is better to only inline small/warm functions). For small and cold functions, I think it doesn't matter whether they are inlined early or late.

It is helpful to collect some optimization remarks here, so thanks for the patch.

llvm/lib/Transforms/IPO/SampleProfile.cpp

906–907

The first parameter in the declaration of OptimizationRemark is "const char *PassName", so why not use DEBUG_TYPE?

I feel "NeverInline" may be more clear than "NotInline" in terms of showing it is illegal to inline.

1010–1021

Not inlined candidate may be reported multiple times here because of the iterative outer loop.

I guess you put the OptimizationRemark here because you want to know the exact reason of why the candidate with inline instance in profile is not inlined (here the reason is not hot enough), then some more information should be emitted to explain it.

If you don't care the exact reason, then it is better to generate the optimization remark in the loop iterating localNotInlinedCallSites. localNotInlinedCallSites contains all the candidates with inline instance in profile but not being inlined for whatever reason including the reason of "not hot enough".

llvm/test/Transforms/SampleProfile/inline-stats.ll

3

Test new pass manager as well.

30

rename the vars with just a number.

[wenlei]

I would imagine among all the functions with inline instance in profile, only those small and warm/cold functions which are not inlined in early inliner will be inlined in regular inliner.

Yes, small functions are the majority. But there're still others.

For small and cold functions, I think it doesn't matter whether they are inlined early or late.

It matters for post-inline profile quality. If it's inlined early by replay inliner of sample loader, the context sensitive profile will be kept. However, if replay inliner rejects them, and later they got inlined by CGSCC inliner, we will have to do count scaling for inlinee so it's not as accurate as if we inline early and preserve context-sensitive profile. This doesn't matter much for the result of inline decision, but it matters for post-inline profile quality which can affect block layout later.

llvm/lib/Transforms/IPO/SampleProfile.cpp

906–907

DEBUG_TYPE is "sample-profile" and I feel it's too broad for practical uses as it covers sample usages, weight propagation, and inlining. I wanted to have something that only gives me inlining remarks, thus using "sample-profile-inline" instead here.

Good point about "NeverInline", will change.

1010–1021

Yes, I care about the reasons. I will change the message to make the reason explicit in the output remarks.

[wenlei]

Restructured remarks sample profile loader inlining:

1. Split into InlineAttempt, InlineSuccess and InlineFail for remark names.
2. Use OptimizationRemark only for InlineSuccess and OptimizationRemarkAnalysis for the rest.

[wenlei]

update test case

[wenlei]

rebase

[wmi]

llvm/lib/Transforms/IPO/SampleProfile.cpp

906–907

Then maybe define a macro for it like #define CSINLINE DEBUG_TYPE "-inline".

[wenlei]

address feedback

[wenlei]

llvm/lib/Transforms/IPO/SampleProfile.cpp

906–907

thanks, macro added.

llvm/lib/Transforms/IPO/SampleProfile.cpp

 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/None.h"
 #include "llvm/ADT/SCCIterator.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/Twine.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/CallGraph.h"
 #include "llvm/Analysis/CallGraphSCCPass.h"
 #include "llvm/Analysis/InlineCost.h"
 #include "llvm/Analysis/LoopInfo.h"

 #include <utility>
 #include <vector>
 
 using namespace llvm;
 using namespace sampleprof;
 using ProfileCount = Function::ProfileCount;
 #define DEBUG_TYPE "sample-profile"
 
+STATISTIC(NumCSInlined,
+          "Number of functions inlined with context sensitive profile");
+STATISTIC(NumCSNotInlined,
+          "Number of functions not inlined with context sensitive profile");
+
 // Command line option to specify the file to read samples from. This is
 // mainly used for debugging.
 static cl::opt<std::string> SampleProfileFile(
     "sample-profile-file", cl::init(""), cl::value_desc("filename"),
     cl::desc("Profile file loaded by -sample-profile"), cl::Hidden);
 
 // The named file contains a set of transformations that may have been applied
 // to the symbol names between the program from which the sample data was
protected:
   findIndirectCallFunctionSamples(const Instruction &I, uint64_t &Sum) const;
   mutable DenseMap<const DILocation *, const FunctionSamples *> DILocation2SampleMap;
   const FunctionSamples *findFunctionSamples(const Instruction &I) const;
   bool inlineCallInstruction(Instruction *I);
   bool inlineHotFunctions(Function &F,
                           DenseSet<GlobalValue::GUID> &InlinedGUIDs);
   // Inline cold/small functions in addition to hot ones
   bool shouldInlineColdCallee(Instruction &CallInst);
+  void emitOptimizationRemarksForInlineCandidates(
+    const SmallVector<Instruction *, 10> &Candidates, const Function &F, bool Hot);
   void printEdgeWeight(raw_ostream &OS, Edge E);
   void printBlockWeight(raw_ostream &OS, const BasicBlock *BB) const;
   void printBlockEquivalence(raw_ostream &OS, const BasicBlock *BB);
   bool computeBlockWeights(Function &F);
   void findEquivalenceClasses(Function &F);
   template <bool IsPostDom>
   void findEquivalencesFor(BasicBlock *BB1, ArrayRef<BasicBlock *> Descendants,
                            DominatorTreeBase<BasicBlock, IsPostDom> *DomTree);
bool SampleProfileLoader::inlineCallInstruction(Instruction *I) {
   // set ComputeFullInlineCost, otherwise getInlineCost may return early
   // when cost exceeds threshold without checking all IRs in the callee.
   // The acutal cost does not matter because we only checks isNever() to
   // see if it is legal to inline the callsite.
   InlineCost Cost =
       getInlineCost(cast<CallBase>(*I), Params, GetTTI(*CalledFunction), GetAC,
                     None, nullptr, nullptr);
   if (Cost.isNever()) {
-    ORE->emit(OptimizationRemark(DEBUG_TYPE, "Not inline", DLoc, BB)
+    ORE->emit(OptimizationRemarkAnalysis("sample-profile-inline", "InlineFail", 
+                                         DLoc, BB)
               << "incompatible inlining");
     return false;
   }
   InlineFunctionInfo IFI(nullptr, &GetAC);
   if (InlineFunction(CS, IFI)) {
     // The call to InlineFunction erases I, so we can't pass it here.
-    ORE->emit(OptimizationRemark(DEBUG_TYPE, "HotInline", DLoc, BB)
-              << "inlined hot callee '" << ore::NV("Callee", CalledFunction)
+    ORE->emit(OptimizationRemark("sample-profile-inline", "InlineSuccess", 
+                                 DLoc, BB)
+              << "inlined callee '" << ore::NV("Callee", CalledFunction)
               << "' into '" << ore::NV("Caller", BB->getParent()) << "'");
     return true;
   }
   return false;
 }
 
 bool SampleProfileLoader::shouldInlineColdCallee(Instruction &CallInst) {
   if (!ProfileSizeInline)
     return false;
 
   Function *Callee = CallSite(&CallInst).getCalledFunction();
   if (Callee == nullptr)
     return false;
 
   InlineCost Cost =
       getInlineCost(cast<CallBase>(CallInst), getInlineParams(),
                     GetTTI(*Callee), GetAC, None, nullptr, nullptr);
 
   return Cost.getCost() <= SampleColdCallSiteThreshold;
 }
 
+void SampleProfileLoader::emitOptimizationRemarksForInlineCandidates(
+    const SmallVector<Instruction *, 10> &Candidates, const Function &F,
+    bool Hot) {
+  for (auto I : Candidates) {
+    Function *CalledFunction = CallSite(I).getCalledFunction();
+    if (CalledFunction) {
+      ORE->emit(OptimizationRemarkAnalysis("sample-profile-inline",
+                                           "InlineAttempt", I->getDebugLoc(),
+                                           I->getParent())
+                << "previous inlining reattempted for "
+                << (Hot ? "hotness: '" : "size: '")
+                << ore::NV("Callee", CalledFunction) << "' into '"
+                << ore::NV("Caller", &F) << "'");
+    }
+  }
+}
+
 /// Iteratively inline hot callsites of a function.
 ///
 /// Iteratively traverse all callsites of the function \p F, and find if
 /// the corresponding inlined instance exists and is hot in profile. If
 /// it is hot enough, inline the callsites and adds new callsites of the
 /// callee into the caller. If the call is an indirect call, first promote
 /// it to direct call. Each indirect call is limited with a single target.
 ///
for (auto &BB : F) {
           if (callsiteIsHot(FS, PSI))
             Hot = true;
           else if (shouldInlineColdCallee(I))
             ColdCandidates.push_back(&I);
         }
       }
       if (Hot) {
         CIS.insert(CIS.begin(), AllCandidates.begin(), AllCandidates.end());
+        emitOptimizationRemarksForInlineCandidates(AllCandidates, F, true);
       }
       else {
         CIS.insert(CIS.begin(), ColdCandidates.begin(), ColdCandidates.end());
+        emitOptimizationRemarksForInlineCandidates(ColdCandidates, F, false);
       }
     }
     for (auto I : CIS) {
       Function *CalledFunction = CallSite(I).getCalledFunction();
       // Do not inline recursive calls.
       if (CalledFunction == &F)
         continue;
       if (CallSite(I).isIndirectCall()) {
         if (PromotedInsns.count(I))
           continue;
         uint64_t Sum;
         for (const auto *FS : findIndirectCallFunctionSamples(*I, Sum)) {
           if (IsThinLTOPreLink) {
             FS->findInlinedFunctions(InlinedGUIDs, F.getParent(),
                                      PSI->getOrCompHotCountThreshold());
             continue;
           }
           auto CalleeFunctionName = FS->getFuncNameInModule(F.getParent());
           // If it is a recursive call, we do not inline it as it could bloat
           // the code exponentially. There is way to better handle this, e.g.
           // clone the caller first, and inline the cloned caller if it is
for (auto I : CIS) {
                 pgo::promoteIndirectCall(I, R->getValue(), C, Sum, false, ORE);
             Sum -= C;
             PromotedInsns.insert(I);
             // If profile mismatches, we should not attempt to inline DI.
             if ((isa<CallInst>(DI) || isa<InvokeInst>(DI)) &&
                 inlineCallInstruction(DI)) {
               localNotInlinedCallSites.erase(I);
               LocalChanged = true;
+              ++NumCSInlined;
             }
           } else {
             LLVM_DEBUG(dbgs()
                        << "\nFailed to promote indirect call to "
                        << CalleeFunctionName << " because " << Reason << "\n");
           }
         }
       } else if (CalledFunction && CalledFunction->getSubprogram() &&
                  !CalledFunction->isDeclaration()) {
         if (inlineCallInstruction(I)) {
           localNotInlinedCallSites.erase(I);
           LocalChanged = true;
+          ++NumCSInlined;
         }
       } else if (IsThinLTOPreLink) {
         findCalleeFunctionSamples(*I)->findInlinedFunctions(
             InlinedGUIDs, F.getParent(), PSI->getOrCompHotCountThreshold());
       }
     }
     if (LocalChanged) {
       Changed = true;
     } else {
       break;
     }
   }
 
   // Accumulate not inlined callsite information into notInlinedSamples
   for (const auto &Pair : localNotInlinedCallSites) {
     Instruction *I = Pair.getFirst();
     Function *Callee = CallSite(I).getCalledFunction();
     if (!Callee || Callee->isDeclaration())
       continue;
+
+    ORE->emit(OptimizationRemarkAnalysis("sample-profile-inline", "NotInline",
+                                         I->getDebugLoc(), I->getParent())
+              << "previous inlining not repeated: '"
+              << ore::NV("Callee", Callee) << "' into '"
+              << ore::NV("Caller", &F) << "'");
+
+    ++NumCSNotInlined;
     const FunctionSamples *FS = Pair.getSecond();
     if (FS->getTotalSamples() == 0 && FS->getEntrySamples() == 0) {
       continue;
     }
 
     if (ProfileMergeInlinee) {
       // Use entry samples as head samples during the merge, as inlinees
       // don't have head samples.

llvm/test/Transforms/SampleProfile/inline-coverage.ll

 ;     6
 ;     7    int main() {
 ;     8      long long int sum = 0;
 ;     9      for (int i = 0; i < 200000 * 3000; i++)
 ;    10        sum += foo(i);
 ;    11      return sum > 0 ? 0 : 1;
 ;    12    }
 ;
-; CHECK: remark: coverage.cc:10:12: inlined hot callee '_Z3fool' into 'main'
+; CHECK: remark: coverage.cc:10:12: previous inlining reattempted for hotness: '_Z3fool' into 'main'
 ; CHECK: remark: coverage.cc:9:21: Applied 23478 samples from profile (offset: 2.1)
 ; CHECK: remark: coverage.cc:10:16: Applied 23478 samples from profile (offset: 3)
 ; CHECK: remark: coverage.cc:4:10: Applied 31878 samples from profile (offset: 1)
 ; CHECK: remark: coverage.cc:11:10: Applied 0 samples from profile (offset: 4)
 ; CHECK: remark: coverage.cc:10:16: most popular destination for conditional branches at coverage.cc:9:3
 ;
 ; There is one sample record with 0 samples at offset 4 in main() that we never
 ; use:

llvm/test/Transforms/SampleProfile/inline-stats.ll

+; REQUIRES: asserts
+; RUN: opt < %s -sample-profile -sample-profile-file=%S/Inputs/inline.prof -stats -S 2>&1 | FileCheck %s
+
+; 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)
+
+; CHECK: 1 sample-profile - Number of functions inlined with context sensitive profile
 No newline at end of file

llvm/test/Transforms/SampleProfile/remarks.ll

 ;     9          sum += -i * rand();
 ;    10      return sum;
 ;    11    }
 ;    12
 ;    13    int main() { return foo() > 0; }
 
 ; We are expecting foo() to be inlined in main() (almost all the cycles are
 ; spent inside foo).
-; CHECK: remark: remarks.cc:13:21: inlined hot callee '_Z3foov' into 'main'
+; CHECK: remark: remarks.cc:13:21: inlined callee '_Z3foov' into 'main'
 
 ; The back edge for the loop is the hottest edge in the loop subgraph.
 ; CHECK: remark: remarks.cc:6:9: most popular destination for conditional branches at remarks.cc:5:3
 
 ; The predicate almost always chooses the 'else' branch.
 ; CHECK: remark: remarks.cc:9:15: most popular destination for conditional branches at remarks.cc:6:9
 
 ; Checking to see if YAML file is generated and contains remarks
 ;YAML:       --- !Passed
-;YAML-NEXT:  Pass:            sample-profile
-;YAML-NEXT:  Name:            HotInline
+;YAML-NEXT:  Pass:            sample-profile-inline
+;YAML-NEXT:  Name:            InlineSuccess
 ;YAML-NEXT:  DebugLoc:        { File: remarks.cc, Line: 13, Column: 21 }
 ;YAML-NEXT:  Function:        main
 ;YAML-NEXT:  Args:
-;YAML-NEXT:    - String:          'inlined hot callee '''
+;YAML-NEXT:    - String:          'inlined callee '''
 ;YAML-NEXT:    - Callee:          _Z3foov
 ;YAML-NEXT:      DebugLoc:        { File: remarks.cc, Line: 3, Column: 0 }
 ;YAML-NEXT:    - String:          ''' into '''
 ;YAML-NEXT:    - Caller:          main
 ;YAML-NEXT:        DebugLoc:        { File: remarks.cc, Line: 13, Column: 0 }
 ;YAML-NEXT:    - String:          ''''
 ;YAML-NEXT:  ...
 ;YAML:  --- !Analysis