Include GUIDs from the same module when computing GUIDs that needs to be imported.

[danielcdh]

Summary

In the compile phase of SamplePGO+ThinLTO, ICP is not invoked. Instead, indirect call targets will be included as function metadata for ThinIndex to buidl the call graph. This should not only include functions defined in other modules, but also functions defined in the same module, otherwise ThinIndex may find the callee dead and eliminate it, while ICP in backend will revive the symbol, which leads to undefined symbol.

[tejohnson]

Does VP metadata get synthesized from the SamplePGO profile? The original bug report had some of the targets on VP metadata attached to the indirect call, but was missing others. Why not include all the targets on that VP metadata rather than marking them for import which seems more hacky.

[danielcdh]

In D39480#912309, @tejohnson wrote:

Does VP metadata get synthesized from the SamplePGO profile? The original bug report had some of the targets on VP metadata attached to the indirect call, but was missing others. Why not include all the targets on that VP metadata rather than marking them for import which seems more hacky.

Because we need to handle the indirect call chain too. E.g. foo() indirectly calls bar(), which indirectly calls baz(). Assuming these 2 calls are ICPed and inlined in the profiling binary, when processing foo's indirect callsite, marking bar's GUID in the VP is not enough, but adding baz's GUID to foo's callsite does not make sense as baz is not its call target. That's why we need to keep the transitive closure as function level metadata.

[tejohnson]

In D39480#912321, @danielcdh wrote:

In D39480#912309, @tejohnson wrote:

Does VP metadata get synthesized from the SamplePGO profile? The original bug report had some of the targets on VP metadata attached to the indirect call, but was missing others. Why not include all the targets on that VP metadata rather than marking them for import which seems more hacky.

Because we need to handle the indirect call chain too. E.g. foo() indirectly calls bar(), which indirectly calls baz(). Assuming these 2 calls are ICPed and inlined in the profiling binary, when processing foo's indirect callsite, marking bar's GUID in the VP is not enough, but adding baz's GUID to foo's callsite does not make sense as baz is not its call target. That's why we need to keep the transitive closure as function level metadata.

But the case here is when they are in fact in the same module. I'm assuming the situation you describe here already works when bar and baz are in different modules than foo. In this case we have foo and bar in the same module, and were missing the VP metadata showing that foo calls bar indirectly. If baz is also in the same module then the same situation applies to the callsite in bar. If it is in a different module then wouldn't the existing logic handle it? I.e. it would be on bar's function entry metadata?

[danielcdh]

In D39480#912334, @tejohnson wrote:

In D39480#912321, @danielcdh wrote:

In D39480#912309, @tejohnson wrote:

Does VP metadata get synthesized from the SamplePGO profile? The original bug report had some of the targets on VP metadata attached to the indirect call, but was missing others. Why not include all the targets on that VP metadata rather than marking them for import which seems more hacky.

Because we need to handle the indirect call chain too. E.g. foo() indirectly calls bar(), which indirectly calls baz(). Assuming these 2 calls are ICPed and inlined in the profiling binary, when processing foo's indirect callsite, marking bar's GUID in the VP is not enough, but adding baz's GUID to foo's callsite does not make sense as baz is not its call target. That's why we need to keep the transitive closure as function level metadata.

But the case here is when they are in fact in the same module. I'm assuming the situation you describe here already works when bar and baz are in different modules than foo. In this case we have foo and bar in the same module, and were missing the VP metadata showing that foo calls bar indirectly. If baz is also in the same module then the same situation applies to the callsite in bar. If it is in a different module then wouldn't the existing logic handle it? I.e. it would be on bar's function entry metadata?

If baz is in the same module as bar and foo, then we need to have baz in foo's entry metadata. For the callsite in bar (standalone copy), it is possible that bar becomes cold after inlined into foo thus there is no profile to indicate bar has an indirect call to baz.

If baz is in another module, then in the current implementation (without this patch), it will be added in foo's entry metadata.

[tejohnson]

In D39480#912335, @danielcdh wrote:

In D39480#912334, @tejohnson wrote:

In D39480#912321, @danielcdh wrote:

In D39480#912309, @tejohnson wrote:

Does VP metadata get synthesized from the SamplePGO profile? The original bug report had some of the targets on VP metadata attached to the indirect call, but was missing others. Why not include all the targets on that VP metadata rather than marking them for import which seems more hacky.

Because we need to handle the indirect call chain too. E.g. foo() indirectly calls bar(), which indirectly calls baz(). Assuming these 2 calls are ICPed and inlined in the profiling binary, when processing foo's indirect callsite, marking bar's GUID in the VP is not enough, but adding baz's GUID to foo's callsite does not make sense as baz is not its call target. That's why we need to keep the transitive closure as function level metadata.

But the case here is when they are in fact in the same module. I'm assuming the situation you describe here already works when bar and baz are in different modules than foo. In this case we have foo and bar in the same module, and were missing the VP metadata showing that foo calls bar indirectly. If baz is also in the same module then the same situation applies to the callsite in bar. If it is in a different module then wouldn't the existing logic handle it? I.e. it would be on bar's function entry metadata?

If baz is in the same module as bar and foo, then we need to have baz in foo's entry metadata. For the callsite in bar (standalone copy), it is possible that bar becomes cold after inlined into foo thus there is no profile to indicate bar has an indirect call to baz.

If baz is in another module, then in the current implementation (without this patch), it will be added in foo's entry metadata.

After discussing offline with Dehao, I understand the issue:

• just an intra-module indirect call could be handled by doing the promotion/inlining during the compile step (or annotating it on the VP metadata attached to the indirect call)
• the issue is when you have a call out of the module, that then does an indirect call back into the module, where the whole call chain was promoted/inlined in the profiled binary: A.c:foo() ->(direct or indirect)-> B.c:bar() ->(indirect)-> A.c:baz()

If the indirect calls along this chain were promoted and then inlined into foo in the profiled binary, we cannot do the promotion/inlining of the call back to A.c:baz() during the compile step since it is intra-module, but we need to be able to annotate the call somewhere. And apparently we can't do this on the VP metadata for the indirect call in B.c:bar() since it was inlined into foo() in the profiled binary (Dehao - is that correct?).

In that case, I have a couple suggestions for the comments and test below.

include/llvm/ProfileData/SampleProf.h

354–355

Function name and comment need updating, since we aren't necessarily importing, but need to register the promoted indirect calls for liveness analysis.

test/Transforms/SampleProfile/function_metadata.ll

8

Suggest making this a different test with a different name since we aren't testing importing, but rather liveness analysis. In that case it would also be good to add a check for the situation described earlier as well.
A.c:foo() ->(direct or indirect)-> B.c:bar() ->(indirect)-> A.c:baz()

[danielcdh]

If the indirect calls along this chain were promoted and then inlined into foo in the profiled binary, we cannot do the promotion/inlining of the call back to A.c:baz() during the compile step since it is intra-module, but we need to be able to annotate the call somewhere. And apparently we can't do this on the VP metadata for the indirect call in B.c:bar() since it was inlined into foo() in the profiled binary (Dehao - is that correct?).

That's correct

[danielcdh]

update

[tejohnson]

include/llvm/ProfileData/SampleProf.h

375

Needs update for name change?

lib/Transforms/IPO/SampleProfile.cpp

1468

I would leave the old reason too - it's both right? Making the IR match before annotation and getting the correct liveness analysis, for anything that couldn't be inlined during the compile step.

test/Transforms/SampleProfile/function_metadata.ll

36

I think you also need to add a second module to test for the A.c:foo() ->(direct or indirect)-> B.c:bar() ->(indirect)-> A.c:baz() case.

[danielcdh]

test/Transforms/SampleProfile/function_metadata.ll

36

foo is not defined in this module, so in this new test it is A.c:test_liveness() ->direct-> B.c:foo() -> (indirect or direct) -> A.c: foo_available().

[danielcdh]

update

[tejohnson]

LGTM

include/llvm/ProfileData/SampleProf.h

sampleprof_error merge(const FunctionSamples &Other, uint64_t Weight = 1) {
     for (const auto &I : Other.getCallsiteSamples()) {
       const LineLocation &Loc = I.first;
       FunctionSamplesMap &FSMap = functionSamplesAt(Loc);
       for (const auto &Rec : I.second)
         MergeResult(Result, FSMap[Rec.first()].merge(Rec.second, Weight));
     }
     return Result;
   }
 
-  /// Recursively traverses all children, if the corresponding function is
-  /// not defined in module \p M, and its total sample is no less than
-  /// \p Threshold, add its corresponding GUID to \p S. Also traverse the
-  /// BodySamples to add hot CallTarget's GUID to \p S.
-  void findImportedFunctions(DenseSet<GlobalValue::GUID> &S, const Module *M,
-                             uint64_t Threshold) const {
+  /// Recursively traverses all children, if the total sample count of the
+  /// corresponding function is no less than \p Threshold, add its corresponding
+  /// GUID to \p S. Also traverse the BodySamples to add hot CallTarget's GUID
+  /// to \p S.
+  void findInlinedFunctions(DenseSet<GlobalValue::GUID> &S, const Module *M,
     if (TotalSamples <= Threshold)
       return;
-    Function *F = M->getFunction(Name);
-    if (!F || !F->getSubprogram())
-      S.insert(Function::getGUID(Name));
     // Import hot CallTargets, which may not be available in IR because full
     // profile annotation cannot be done until backend compilation in ThinLTO.
     for (const auto &BS : BodySamples)
       for (const auto &TS : BS.second.getCallTargets())
         if (TS.getValue() > Threshold) {
           Function *Callee = M->getFunction(TS.getKey());
           if (!Callee || !Callee->getSubprogram())
             S.insert(Function::getGUID(TS.getKey()));
         }
     for (const auto &CS : CallsiteSamples)
       for (const auto &NameFS : CS.second)
-        NameFS.second.findImportedFunctions(S, M, Threshold);
+        NameFS.second.findInlinedFunctions(S, M, Threshold);
   }
 
   /// Set the name of the function.
   void setName(StringRef FunctionName) { Name = FunctionName; }
 
   /// Return the function name.
   const StringRef &getName() const { return Name; }
 

lib/Transforms/IPO/SampleProfile.cpp

protected:
   ErrorOr<uint64_t> getInstWeight(const Instruction &I);
   ErrorOr<uint64_t> getBlockWeight(const BasicBlock *BB);
   const FunctionSamples *findCalleeFunctionSamples(const Instruction &I) const;
   std::vector<const FunctionSamples *>
   findIndirectCallFunctionSamples(const Instruction &I, uint64_t &Sum) const;
   const FunctionSamples *findFunctionSamples(const Instruction &I) const;
   bool inlineCallInstruction(Instruction *I);
   bool inlineHotFunctions(Function &F,
-                          DenseSet<GlobalValue::GUID> &ImportGUIDs);
+                          DenseSet<GlobalValue::GUID> &InlinedGUIDs);
   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);

 ///
 /// 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.
 ///
 /// \param F function to perform iterative inlining.
-/// \param ImportGUIDs a set to be updated to include all GUIDs that come
-///     from a different module but inlined in the profiled binary.
+/// \param InlinedGUIDs a set to be updated to include all GUIDs that are
+///     inlined in the profiled binary.
 ///
 /// \returns True if there is any inline happened.
 bool SampleProfileLoader::inlineHotFunctions(
-    Function &F, DenseSet<GlobalValue::GUID> &ImportGUIDs) {
+    Function &F, DenseSet<GlobalValue::GUID> &InlinedGUIDs) {
   DenseSet<Instruction *> PromotedInsns;
   bool Changed = false;
   while (true) {
     bool LocalChanged = false;
     SmallVector<Instruction *, 10> CIS;
     for (auto &BB : F) {
       bool Hot = false;
       SmallVector<Instruction *, 10> Candidates;
for (auto I : CIS) {
       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->findImportedFunctions(ImportGUIDs, F.getParent(),
-                                      Samples->getTotalSamples() *
-                                          SampleProfileHotThreshold / 100);
+            FS->findInlinedFunctions(InlinedGUIDs, F.getParent(),
             continue;
           }
           auto CalleeFunctionName = FS->getName();
           // 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
           // recursive. As llvm does not inline recursive calls, we will
           // simply ignore it instead of handling it explicitly.
for (auto I : CIS) {
                   << CalleeFunctionName << " because " << Reason << "\n");
           }
         }
       } else if (CalledFunction && CalledFunction->getSubprogram() &&
                  !CalledFunction->isDeclaration()) {
         if (inlineCallInstruction(I))
           LocalChanged = true;
       } else if (IsThinLTOPreLink) {
-        findCalleeFunctionSamples(*I)->findImportedFunctions(
-            ImportGUIDs, F.getParent(),
+        findCalleeFunctionSamples(*I)->findInlinedFunctions(
+            InlinedGUIDs, F.getParent(),
             Samples->getTotalSamples() * SampleProfileHotThreshold / 100);
       }
     }
     if (LocalChanged) {
       Changed = true;
     } else {
       break;
     }
bool SampleProfileLoader::emitAnnotations(Function &F) {
   bool Changed = false;
 
   if (getFunctionLoc(F) == 0)
     return false;
 
   DEBUG(dbgs() << "Line number for the first instruction in " << F.getName()
                << ": " << getFunctionLoc(F) << "\n");
 
-  DenseSet<GlobalValue::GUID> ImportGUIDs;
-  Changed |= inlineHotFunctions(F, ImportGUIDs);
+  DenseSet<GlobalValue::GUID> InlinedGUIDs;
+  Changed |= inlineHotFunctions(F, InlinedGUIDs);
 
   // Compute basic block weights.
   Changed |= computeBlockWeights(F);
 
   if (Changed) {
     // Add an entry count to the function using the samples gathered at the
-    // function entry. Also sets the GUIDs that comes from a different
-    // module but inlined in the profiled binary. This is aiming at making
-    // the IR match the profiled binary before annotation.
-    F.setEntryCount(Samples->getHeadSamples() + 1, &ImportGUIDs);
+    // function entry.
+    // Sets the GUIDs that are inlined in the profiled binary. This is used
+    // for ThinLink to make correct liveness analysis, and also make the IR
+    // match the profiled binary before annotation.
+    F.setEntryCount(Samples->getHeadSamples() + 1, &InlinedGUIDs);
 
     // Compute dominance and loop info needed for propagation.
     computeDominanceAndLoopInfo(F);
 
     // Find equivalence classes.
     findEquivalenceClasses(F);
 
     // Propagate weights to all edges.

test/Transforms/SampleProfile/Inputs/function_metadata.prof

 test:10000:0
  3: foo:1000
   3: bar:200
    4: baz:10
  4: foo1:1000
   1: 1000
  4: foo2:1000
   1: 1000 foo3:1000
+test_liveness:10000:0
+ 1: foo:1000
+  1: foo_available:1000

test/Transforms/SampleProfile/function_metadata.ll

-; RUN: opt < %s -passes='thinlto-pre-link<O2>' -pgo-kind=new-pm-pgo-sample-use-pipeline -profile-file=%S/Inputs/import.prof -S | FileCheck %s
+; RUN: opt < %s -passes='thinlto-pre-link<O2>' -pgo-kind=new-pm-pgo-sample-use-pipeline -profile-file=%S/Inputs/function_metadata.prof -S | FileCheck %s
 
 ; Tests whether the functions in the inline stack are added to the
 ; function_entry_count metadata.
 
 declare void @foo()
 
+define void @foo_available() !dbg !11 {
+  ret void
+}
+
+; CHECK: define void @test({{.*}} !prof ![[ENTRY_TEST:[0-9]+]]
 define void @test(void ()*) !dbg !7 {
   %2 = alloca void ()*
   store void ()* %0, void ()** %2
   %3 = load void ()*, void ()** %2
   ; CHECK: call {{.*}}, !prof ![[PROF:[0-9]+]]
   call void @foo(), !dbg !18
   call void %3(), !dbg !19
   ret void
 }
 
+; CHECK: define void @test_liveness({{.*}} !prof ![[ENTRY_TEST_LIVENESS:[0-9]+]]
+define void @test_liveness() !dbg !12 {
+  call void @foo(), !dbg !20
+  ret void
+}
+
 ; GUIDs of foo, bar, foo1, foo2 and foo3 should be included in the metadata to
 ; make sure hot inline stacks are imported.
-; CHECK: !{!"function_entry_count", i64 1, i64 2494702099028631698, i64 6699318081062747564, i64 7682762345278052905,  i64 -7908226060800700466, i64 -2012135647395072713}
+; CHECK: ![[ENTRY_TEST]] = !{!"function_entry_count", i64 1, i64 2494702099028631698, i64 6699318081062747564, i64 7682762345278052905,  i64 -7908226060800700466, i64 -2012135647395072713}
+
+; Check GUIDs for both foo and foo_available are included in the metadata to
+; make sure the liveness analysis can capture the dependency from test_liveness
+; to foo_available.
+; CHECK: ![[ENTRY_TEST_LIVENESS]] = !{!"function_entry_count", i64 1, i64 4005816710939881937, i64 6699318081062747564}
 
 !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 = !{}
 !6 = !DISubroutineType(types: !2)
 !7 = distinct !DISubprogram(name: "test", line: 7, isLocal: false, isDefinition: true, virtualIndex: 6, flags: DIFlagPrototyped, isOptimized: false, unit: !0, scopeLine: 7, file: !1, scope: !1, type: !6, variables: !2)
 !8 = !{i32 2, !"Dwarf Version", i32 4}
 !9 = !{i32 1, !"Debug Info Version", i32 3}
 !10 = !{!"clang version 3.5 "}
+!11 = distinct !DISubprogram(name: "foo_available", line: 7, isLocal: false, isDefinition: true, virtualIndex: 6, flags: DIFlagPrototyped, isOptimized: false, unit: !0, scopeLine: 7, file: !1, scope: !1, type: !6, variables: !2)
+!12 = distinct !DISubprogram(name: "test_liveness", line: 7, isLocal: false, isDefinition: true, virtualIndex: 6, flags: DIFlagPrototyped, isOptimized: false, unit: !0, scopeLine: 7, file: !1, scope: !1, type: !6, variables: !2)
 !15 = !DILexicalBlockFile(discriminator: 1, file: !1, scope: !7)
 !17 = distinct !DILexicalBlock(line: 10, column: 0, file: !1, scope: !7)
 !18 = !DILocation(line: 10, scope: !17)
 !19 = !DILocation(line: 11, scope: !17)
+!20 = !DILocation(line: 8, scope: !12)

test/Transforms/SampleProfile/import.ll

-; RUN: opt < %s -passes='thinlto-pre-link<O2>' -pgo-kind=new-pm-pgo-sample-use-pipeline -profile-file=%S/Inputs/import.prof -S | FileCheck %s
-
-; Tests whether the functions in the inline stack are added to the
-; function_entry_count metadata.
-
-declare void @foo()
-
-define void @test(void ()*) !dbg !7 {
-  %2 = alloca void ()*
-  store void ()* %0, void ()** %2
-  %3 = load void ()*, void ()** %2
-  ; CHECK: call {{.*}}, !prof ![[PROF:[0-9]+]]
-  call void @foo(), !dbg !18
-  call void %3(), !dbg !19
-  ret void
-}
-
-; GUIDs of foo, bar, foo1, foo2 and foo3 should be included in the metadata to
-; make sure hot inline stacks are imported.
-; CHECK: !{!"function_entry_count", i64 1, i64 2494702099028631698, i64 6699318081062747564, i64 7682762345278052905,  i64 -7908226060800700466, i64 -2012135647395072713}
-
-!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 = !{}
-!6 = !DISubroutineType(types: !2)
-!7 = distinct !DISubprogram(name: "test", line: 7, isLocal: false, isDefinition: true, virtualIndex: 6, flags: DIFlagPrototyped, isOptimized: false, unit: !0, scopeLine: 7, file: !1, scope: !1, type: !6, variables: !2)
-!8 = !{i32 2, !"Dwarf Version", i32 4}
-!9 = !{i32 1, !"Debug Info Version", i32 3}
-!10 = !{!"clang version 3.5 "}
-!15 = !DILexicalBlockFile(discriminator: 1, file: !1, scope: !7)
-!17 = distinct !DILexicalBlock(line: 10, column: 0, file: !1, scope: !7)
-!18 = !DILocation(line: 10, scope: !17)
-!19 = !DILocation(line: 11, scope: !17)