[AutoFDO] Properly merge context-sensitive profile of inlinee back to outlined function

[wenlei]

Summary

When sample profile loader decides not to inline a previously inlined call-site, we adjust the profile of outlined function simply by scaling up its profile counts by call-site count. This means the context-sensitive profile of that inlined instance will be thrown away. This commit try to keep context-sensitive profile for such cases:

• Instead of scaling outlined function's profile, we now properly merge the FunctionSamples of inlined instance into outlined function, including all recursively inlined profile.
• Instead of adjusting the profile for negative inline decision at the end of the sample profile loader pass, we do the profile merge right after processing each function. This change paired with top-down ordering of annotation/inline-replay (a separate diff) will make sure we recursively merge profile back before the profile is used for annotation and inline replay.

A new switch -sample-profile-merge-inlinee is added to enable the new profile merge for tuning. It should be the default behavior eventually.

[wmi]

The change makes sense to me. The only concern is for inline instance getEntrySamples is not precise and sometimes can have a large difference with the actual head count. It will be interesting to see the actual effect. I will test it combined with D70655 on my side.

[wenlei]

The only concern is for inline instance getEntrySamples is not precise and sometimes can have a large difference with the actual head count

Agreed. I think this problem can be mitigated if we run profile inference on inlinee as well before using the count to drive inline decision and then also use the post-inference entry count of inlinee as call site count for profile adjustment. But that itself deserves a separate change, and needs to be evaluated.

For the reason you mentioned, total samples had to be used to drive inline replay here instead of relying on inlinee's entry count which would be a better proximation of call site count. Ideally, if we run profile inference before early inlining, inlinee's entry count can be more reliable and we may use that instead of total samples.

[wmi]

I did performance test combing D70653 and D70655, there was ~0.2% latency improvement in a benchmark, so that is good.

llvm/include/llvm/ProfileData/SampleProfReader.h

363

I found a potential problem here. When we create a new profile for a function when merging inline instance profile back, if the function somehow has no debug information, the annotation will fail and a warning will be issued. We may want to skip those functions without debug information (The warning is issued in SampleProfileLoader::getFunctionLoc)

[wenlei]

In D70653#1761978, @wmi wrote:

I did performance test combing D70653 and D70655, there was ~0.2% latency improvement in a benchmark, so that is good.

Thanks for code review and measurement. Glad to know that it helped your workload too.

llvm/include/llvm/ProfileData/SampleProfReader.h

363

For these cases, if the function without debug info wasn't inlined, we would still get the warning, right? I though the warning in this case is no different and as helpful comparing to other cases, or did I miss anything?

[wmi]

llvm/include/llvm/ProfileData/SampleProfReader.h

363

Although without the patch, we may also see the warning because of the source drift or compiler upgrade, in reality we rarely see that happens. I am worried that the patch may increase the chance of such warning and break many builds.

So I will look into it and see what causes the warning and whether it is a rare case or not.

[wmi]

llvm/include/llvm/ProfileData/SampleProfReader.h

363

I looked into it and found the case was not rare.

For the function without debug information, in afdo profile there was no inline instance. The function was added to localNotInlinedCallSites because findFunctionSamplesAt returned a function sample as long as the location matched (the imprecise matching is designed for indirect promotion). In this case, the FunctionSamples returned didn't belong to the function without debug information.

I applied file specific -Wno-error to disable the warning whenever I saw a case like this in a large benchmark build, and I found the same problem in at least three files (If I continue the process, I may find more).

To solve the problem, maybe check debug information in findFunctionSamplesAt before return a FunctionSamples when callee name doesn't match the name in FunctionSamples. If debug information doesn't exists for a function, inlining it won't bring more context sensitive information because no profile annotation is possible.

[wenlei]

llvm/include/llvm/ProfileData/SampleProfReader.h

363

Thanks for looking! We only call getOrCreateSamplesFor when a callee is found from call instruction, i.e., it's a direct call. So in this case, it seems a direct call's callee got samples from a different function (inlinee)? Sounds like it can be caused by source change?

If imprecise matching is only meant for indirect call, I can turn it off for direct call - inside findFunctionSamplesAt, only do the fuzzy matching when CalleeName is empty string.

[wenlei]

address review feedback - only do fuzzy match for call site targets for indirect calls, as a result, I had to fix a few test cases.

[wmi]

I rerun perf test and I don't see any performance change. Last run I saw very small improvement on latency in a benchmark. This is fine since the benchmark has some fluctuation by itself.

llvm/include/llvm/ProfileData/SampleProf.h

394

Nit: have an early return when CalleeName.empty() is true.

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

33–34

run opt -instnamer for the test.

[wenlei]

address feedback

[wenlei]

llvm/include/llvm/ProfileData/SampleProf.h

394

done

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

33–34

done. i need to develop this habit. :)

llvm/include/llvm/ProfileData/SampleProf.h

const FunctionSamples *findFunctionSamplesAt(const LineLocation &Loc,
 
     auto iter = CallsiteSamples.find(Loc);
     if (iter == CallsiteSamples.end())
       return nullptr;
     auto FS = iter->second.find(CalleeName);
     if (FS != iter->second.end())
       return &FS->second;
     // If we cannot find exact match of the callee name, return the FS with
-    // the max total count.
+    // the max total count. Only do this when CalleeName is not provided, 
+    // i.e., only for indirect calls.
     uint64_t MaxTotalSamples = 0;
     const FunctionSamples *R = nullptr;
+    if (CalleeName.empty()) {
       for (const auto &NameFS : iter->second)
         if (NameFS.second.getTotalSamples() >= MaxTotalSamples) {
           MaxTotalSamples = NameFS.second.getTotalSamples();
           R = &NameFS.second;
         }
+    }
     return R;
   }
 
   bool empty() const { return TotalSamples == 0; }
 
   /// Return the total number of samples collected inside the function.
   uint64_t getTotalSamples() const { return TotalSamples; }
 

llvm/include/llvm/ProfileData/SampleProfReader.h

public:
   FunctionSamples *getSamplesFor(const Function &F) {
     // The function name may have been updated by adding suffix. Call
     // a helper to (optionally) strip off suffixes so that we can
     // match against the original function name in the profile.
     StringRef CanonName = FunctionSamples::getCanonicalFnName(F);
     return getSamplesFor(CanonName);
   }
 
+  /// Return the samples collected for function \p F, create empty
+  /// FunctionSamples if it doesn't exist.
+  FunctionSamples *getOrCreateSamplesFor(const Function &F) {
+    std::string FGUID;
+    StringRef CanonName = FunctionSamples::getCanonicalFnName(F);
+    CanonName = getRepInFormat(CanonName, getFormat(), FGUID);
+    return &Profiles[CanonName];
+  }
+
   /// Return the samples collected for function \p F.
   virtual FunctionSamples *getSamplesFor(StringRef Fname) {
     if (Remapper) {
       if (auto FS = Remapper->getSamplesFor(Fname))
         return FS;
     }
     std::string FGUID;
     Fname = getRepInFormat(Fname, getFormat(), FGUID);

llvm/lib/Transforms/IPO/SampleProfile.cpp

cl::desc("If the sample profile is accurate, we will mark all un-sampled "
              "un-sampled callsites and functions conservatively as unknown. "));
 
 static cl::opt<bool> ProfileAccurateForSymsInList(
     "profile-accurate-for-symsinlist", cl::Hidden, cl::ZeroOrMore,
     cl::init(true),
     cl::desc("For symbols in profile symbol list, regard their profiles to "
              "be accurate. It may be overriden by profile-sample-accurate. "));
 
+static cl::opt<bool> ProfileMergeInlinee(
+    "sample-profile-merge-inlinee", cl::Hidden, cl::init(false),
+    cl::desc("Merge past inlinee's profile to outline version if sample "
+             "profile loader decided not to inline a call site."));
+
 namespace {
 
 using BlockWeightMap = DenseMap<const BasicBlock *, uint64_t>;
 using EquivalenceClassMap = DenseMap<const BasicBlock *, const BasicBlock *>;
 using Edge = std::pair<const BasicBlock *, const BasicBlock *>;
 using EdgeWeightMap = DenseMap<Edge, uint64_t>;
 using BlockEdgeMap =
     DenseMap<const BasicBlock *, SmallVector<const BasicBlock *, 8>>;
bool SampleProfileLoader::inlineHotFunctions(
 
   // 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;
     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.
+      assert(FS->getHeadSamples() == 0 && "Expect 0 head sample for inlinee");
+      const_cast<FunctionSamples *>(FS)->addHeadSamples(FS->getEntrySamples());
+
+      // Note that we have to do the merge right after processing function.
+      // This allows OutlineFS's profile to be used for annotation during
+      // top-down processing of functions' annotation.
+      FunctionSamples *OutlineFS = Reader->getOrCreateSamplesFor(*Callee);
+      OutlineFS->merge(*FS);
+    } else {
       auto pair =
           notInlinedCallInfo.try_emplace(Callee, NotInlinedProfileInfo{0});
       pair.first->second.entryCount += FS->getEntrySamples();
     }
+  }
   return Changed;
 }
 
 /// Find equivalence classes for the given block.
 ///
 /// This finds all the blocks that are guaranteed to execute the same
 /// number of times as \p BB1. To do this, it traverses all the
 /// descendants of \p BB1 in the dominator or post-dominator tree.

llvm/test/CodeGen/X86/insert-prefetch-inline.afdo

 caller:0:0
- 2:sum:0
+ 2: sum:0
   3: 0 __prefetch_nta_0:23456
   3.1: 0 __prefetch_nta_0:8764 __prefetch_nta_1:64
 No newline at end of file

llvm/test/Transforms/SampleProfile/Inputs/einline.prof

 _Z3foov:200:100
- 1: _Z3barv:0
+ 1: _ZL3barv:0
  2: no_inline:100
- 3: _Z3barv:100
+ 3: _ZL3barv:100
 recursive:200:100
  1: recursive:100
  2: recursive:100

llvm/test/Transforms/SampleProfile/Inputs/inline-callee-update.prof

 test_sample_loader_inline:63067:0
  1: sample_loader_inlinee:40000
 sample_loader_inlinee:3000:0
  1: direct_leaf_func:35000
   11: 3000
 test_cgscc_inline:63067:0
- 1: sample_loader_inlinee:1
+ 1: cgscc_inlinee:1
 cgscc_inlinee:3000:0
  1: direct_leaf_func:35000
   11: 3000
 No newline at end of file

llvm/test/Transforms/SampleProfile/Inputs/inline-mergeprof.prof

+main:225715:0
+ 2.1: 5553
+ 3: 5391
+ 3.1: _Z3sumii:46
+  1: 23
+  2: _Z3subii:2
+   1: 2
+  3: 21
+
+_Z3sumii:11:22
+ 1: 11
+ 2: 10 _Z3subii:10
+ 3: 1
 No newline at end of file

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

+; Test we lose details of not inlined profile without '-sample-profile-merge-inlinee'
+; RUN: opt < %s -sample-profile -sample-profile-file=%S/Inputs/inline-mergeprof.prof -S | FileCheck -check-prefix=SCALE %s
+; RUN: opt < %s -passes=sample-profile -sample-profile-file=%S/Inputs/inline-mergeprof.prof -S | FileCheck -check-prefix=SCALE %s
+
+; Test we properly merge not inlined profile properly with '-sample-profile-merge-inlinee'
+; RUN: opt < %s -sample-profile -sample-profile-file=%S/Inputs/inline-mergeprof.prof -sample-profile-merge-inlinee -S | FileCheck -check-prefix=MERGE %s
+; RUN: opt < %s -passes=sample-profile -sample-profile-file=%S/Inputs/inline-mergeprof.prof -sample-profile-merge-inlinee -S | FileCheck -check-prefix=MERGE  %s
+
+@.str = private unnamed_addr constant [11 x i8] c"sum is %d\0A\00", align 1
+
+; Function Attrs: uwtable
+define i32 @main() !dbg !7 {
+entry:
+  %retval = alloca i32, align 4
+  %s = alloca i32, align 4
+  %i = alloca i32, align 4
+  %0 = load i32, i32* %i, align 4, !dbg !18
+  %1 = load i32, i32* %s, align 4, !dbg !18
+  %call = call i32 @_Z3sumii(i32 %0, i32 %1), !dbg !18
+; SCALE: call i32 @_Z3sumii
+; MERGE: call i32 @_Z3sumii
+  store i32 %call, i32* %s, align 4, !dbg !18
+  ret i32 0, !dbg !25
+}
+
+; 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
+  %2 = load i32, i32* %x.addr, align 4, !dbg !11
+  %3 = load i32, i32* %y.addr, align 4, !dbg !11
+  %cmp1 = icmp ne i32 %3, 100, !dbg !11
+  br i1 %cmp1, label %if.then, label %if.else, !dbg !11
+if.then:
+  %call = call i32 @_Z3subii(i32 %2, i32 %3), !dbg !29
+  ret i32 %add, !dbg !29
+if.else:
+  ret i32 %add, !dbg !30
+}
+
+; Function Attrs: nounwind uwtable
+define i32 @_Z3subii(i32 %x, i32 %y) !dbg !26 {
+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 !27
+  %1 = load i32, i32* %y.addr, align 4, !dbg !27
+  %add = sub nsw i32 %0, %1, !dbg !27
+  ret i32 %add, !dbg !28
+}
+
+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)
+!26 = distinct !DISubprogram(name: "sub", line: 20, isLocal: false, isDefinition: true, virtualIndex: 6, flags: DIFlagPrototyped, isOptimized: false, unit: !0, scopeLine: 20, file: !1, scope: !5, type: !6, retainedNodes: !2)
+!27 = !DILocation(line: 20, scope: !26)
+!28 = !DILocation(line: 21, scope: !26)
+!29 = !DILocation(line: 5, scope: !4)
+!30 = !DILocation(line: 6, scope: !4)
+
+; SCALE: name: "sum"
+; SCALE-NEXT: {!"function_entry_count", i64 46}
+; SCALE: !{!"branch_weights", i32 11, i32 2}
+; SCALE: !{!"branch_weights", i64 20}
+; SCALE: name: "sub"
+; SCALE-NEXT: {!"function_entry_count", i64 -1}
+
+; MERGE: name: "sum"
+; MERGE-NEXT: {!"function_entry_count", i64 46}
+; MERGE: !{!"branch_weights", i32 11, i32 23}
+; MERGE: !{!"branch_weights", i32 10}
+; MERGE: name: "sub"
+; MERGE-NEXT: {!"function_entry_count", i64 3}
 No newline at end of file