Properly add out-of-module functions to the import list

[lxfind]

Summary

This patch addresses two issues related to adding inline functions to the import list while recursively going through the profiling data.

1. For callsite samples, only add an inlined function to the import list if it's from outside of the module (i.e. only has a declaration inside the module).
2. For body samples, add each target function to the import list if it's from outside of the module (i.e. only has a declaration inside the module). Previously we were using getSubProgram() to check whether it has dbg info, which is inaccurate. This fix properly add imports and could improve the quality of the pass.

Added a few changes to the test to catch these cases.

[lxfind]

rebase

[lxfind]

Keep test for the original purpose by forcing function out of module

[wenlei]

llvm/include/llvm/ProfileData/SampleProf.h

531

I think we need F->isDeclaration() here, getSubprogram() tells us whether debug metadata (!dbg) is available for this function.

[lxfind]

llvm/include/llvm/ProfileData/SampleProf.h

543

@wenlei Do you know why we are checking for getSubprogram() here?

[wenlei]

llvm/include/llvm/ProfileData/SampleProf.h

543

I didn't notice this, but it looks fishy to me. We could have declaration with !dbg (see metadata-function-dbg.ll) which we should still import. We could also have definition without !dbg.. I'm not sure why we check getSubprogram() - I guess we can verify by trying to contrive a case that this logic would miss for importing.. @wmi is this intentional?

[lxfind]

llvm/include/llvm/ProfileData/SampleProf.h

543

@wenlei I was able to reproduce both of the cases you described, that a function isn't added to import list when it doesn't have !dbg annotation, indicating that we shouldn't rely on getSubProgram here. This is probably also intended to mimic the behavior of isDeclaration.
I will fix this part as well, add a test, while waiting for @wmi to confirm.

[lxfind]

Also use isDeclaration for body samples, add test case

[wmi]

llvm/include/llvm/ProfileData/SampleProf.h

531

Indeed when F->isDeclaration() is true, getSubprogram could also be true. That will potentially miss importing.

I am not very sure about the original intention of using getSubprogram. I am thinking about the case when a comdat function doesn't have debug information in current module, is it possible to import another version with debug information from other module? Need Teresa's opinion on it. I will ask her about it.

[wmi]

llvm/include/llvm/ProfileData/SampleProf.h

531

I checked with Teresa. Currently if there has been a function definition in the module, no import of the same function from other module will be done, no matter how the debug information looks like. So using getSubProgram here is not intended to import comdat function with debug information. I agree we should change it to isDeclaration.

542–543

We can create a lambda so the code snippet here and above can share it.

[lxfind]

use lambda to reuse code

[hoyFB]

llvm/include/llvm/ProfileData/SampleProf.h

531

Should isDeclarationForLinker be checked instead? I thought when a function is imported, it has definition in the current module and it's not longer a declaration. An imported function is a definition in the module it's imported into but since it is also a isDeclarationForLinker (or hasAvailableExternallyLinkage) it won't be emitted into the current object file.

llvm/test/Transforms/SampleProfile/function_metadata.ll

56–57

Nit: remove !11 or replace it with !13?

[tejohnson]

llvm/include/llvm/ProfileData/SampleProf.h

531

IIUC this code is deciding what to tell ThinLTO to import. So it makes sense to see if it is an actual declaration at this point. If there is a def in the module (regardless of linkage type), when we get to the thin link we won't bother importing the callee.

[wenlei]

Thanks! LGTM other than the test tweak hoy pointed out. You may also want to update the summary to reflect the additional fix.

Since most of the time we actually have !dbg for declarations, the additional fix would enable proper profile based importing/inlining for cross-module callee's that were not previously inlined. This could have a positive performance impact (especially for multiple iterations of AutoFDO) because we were unintentionally restricted from growing cross-module inlining based on profile beyond what can be replayed by sample loader (which was from first build without profile).

llvm/include/llvm/ProfileData/SampleProf.h

531

I thought when a function is imported, it has definition in the current module and it's not longer a declaration.

This GUID list here is collected only in pre-link to guide importing for ThinLink, so at this point, isDeclaration is accurate.

[hoyFB]

llvm/include/llvm/ProfileData/SampleProf.h

531

Yeah, that's true. The code is only run in ThinLTOPreLink, so checking isDeclaration is fine here.

[lxfind]

Address test feedback

[hoyFB]

LGTM.

llvm/include/llvm/ProfileData/SampleProf.h

public:
   /// 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,
                             uint64_t Threshold) const {
     if (TotalSamples <= Threshold)
       return;
+    auto isDeclaration = [](const Function *F) {
+      return !F || F->isDeclaration();
+    };
+    if (isDeclaration(M->getFunction(getFuncName()))) {
+      // Add to the import list only when it's defined out of module.
       S.insert(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) {
           const Function *Callee = M->getFunction(getFuncName(TS.getKey()));
-          if (!Callee || !Callee->getSubprogram())
+          if (isDeclaration(Callee))
             S.insert(getGUID(TS.getKey()));
         }
     for (const auto &CS : CallsiteSamples)
       for (const auto &NameFS : CS.second)
         NameFS.second.findInlinedFunctions(S, M, Threshold);
   }
 
   /// Set the name of the function.

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

 test:3200:0
  1: 100
  2: 100
  3: foo:1000
   1: 800
   3: bar:200
    2: 190
    4: baz:10
     2: 10
  4: foo1:1000
   1: 1000
  4: foo2:1000
   1: 1000 foo3:1000
 test_liveness:1000:0
  1: foo:1000
-  1: foo_available:1000
+  1: bar:1000
+   1: 2000 bar_dbg:1000 bar_available:1000
    2: 1000

llvm/test/Transforms/SampleProfile/function_metadata.ll

 ; RUN: opt < %s -passes='thinlto-pre-link<O2>' -pgo-kind=pgo-sample-use-pipeline -profile-file=%S/Inputs/function_metadata.prof -S | FileCheck %s
 ; RUN: opt < %s -passes='thinlto-pre-link<O2>' -pgo-kind=pgo-sample-use-pipeline -profile-file=%S/Inputs/function_metadata.compact.afdo -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 {
+declare void @bar()
+
+declare !dbg !13 void @bar_dbg()
+
+define void @bar_available() !dbg !14 {
   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

 }
 
 ; GUIDs of foo, bar, foo1, foo2 and foo3 should be included in the metadata to
 ; make sure hot inline stacks are imported. The total count of baz is lower
 ; than the hot cutoff threshold and its GUID should not be included in the
 ; metadata.
 ; 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
+; Check GUIDs for foo, bar and bar_dbg 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}
+; to bar. bar_available should not be included as it's within the same module.
+; CHECK: ![[ENTRY_TEST_LIVENESS]] = !{!"function_entry_count", i64 1, i64 6699318081062747564, i64 -2012135647395072713, i64 -1522495160813492905}
 
 !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, retainedNodes: !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, retainedNodes: !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, retainedNodes: !2)
+!13 = !DISubprogram(name: "bar_dbg", scope: !1, file: !1, flags: DIFlagPrototyped, spFlags: DISPFlagOptimized)
+!14 = distinct !DISubprogram(name: "bar_available", line: 7, isLocal: false, isDefinition: true, virtualIndex: 6, flags: DIFlagPrototyped, isOptimized: false, unit: !0, scopeLine: 7, file: !1, scope: !1, type: !6, retainedNodes: !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)