Explicitly promote indirect calls before sample profile annotation.

[danielcdh]

Summary

In iterative sample pgo where profile is collected from PGOed binary, we may see indirect call targets promoted and inlined in the profile. Before profile annotation, we need to make this happen in order to annotate correctly on IR. This patch explicitly promotes these indirect calls and inlines them before profile annotation.

[davidxl]

can you split the refactoring code into a different patch?

[danielcdh]

rebase

[davidxl]

lib/Transforms/IPO/SampleProfile.cpp

619

should only be --> is limited with a single target.

1289

PromotedInsns is not used outside, is there a reason it can not be put into inlineHotFunctions as a local var?

[danielcdh]

update

[danielcdh]

add comments

[davidxl]

lgtm

[danielcdh]

reverted due to compile time breakage: needs legality check before promotion.

[danielcdh]

add legality check and according tests.

[danielcdh]

David,

I've fixed the bug and added the corresponding unittests. PTAL.

Thanks,
Dehao

[davidxl]

lib/Transforms/IPO/SampleProfile.cpp

656

better to return the failed reason and emit debug output.

[danielcdh]

update

[davidxl]

lib/Transforms/IPO/SampleProfile.cpp

667

reset CalledFunction to null or continue?

[danielcdh]

update

[davidxl]

lgtm

lib/Transforms/IPO/SampleProfile.cpp

 #include "llvm/ProfileData/InstrProf.h"
 #include "llvm/ProfileData/SampleProfReader.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorOr.h"
 #include "llvm/Support/Format.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/IPO.h"
+#include "llvm/Transforms/Instrumentation.h"
 #include "llvm/Transforms/Utils/Cloning.h"
 #include <cctype>
 
 using namespace llvm;
 using namespace sampleprof;
 
 #define DEBUG_TYPE "sample-profile"
 
SampleProfileLoader::findFunctionSamples(const Instruction &Inst) const {
   return FS;
 }
 
 /// \brief 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.
-///
-/// TODO: investigate the possibility of not invoking InlineFunction directly.
+/// 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.
 ///
 /// \returns True if there is any inline happened.
 bool SampleProfileLoader::inlineHotFunctions(Function &F) {
+  DenseSet<Instruction *> PromotedInsns;
   bool Changed = false;
   LLVMContext &Ctx = F.getContext();
   std::function<AssumptionCache &(Function &)> GetAssumptionCache = [&](
       Function &F) -> AssumptionCache & { return ACT->getAssumptionCache(F); };
   while (true) {
     bool LocalChanged = false;
     SmallVector<Instruction *, 10> CIS;
     for (auto &BB : F) {
for (auto &BB : F) {
         }
       }
       if (Hot) {
         CIS.insert(CIS.begin(), Candidates.begin(), Candidates.end());
       }
     }
     for (auto I : CIS) {
       InlineFunctionInfo IFI(nullptr, ACT ? &GetAssumptionCache : nullptr);
-      CallSite CS(I);
-      Function *CalledFunction = CS.getCalledFunction();
+      Function *CalledFunction = CallSite(I).getCalledFunction();
+      Instruction *DI = I;
+      if (!CalledFunction && !PromotedInsns.count(I)) {
+        auto CalleeFunctionName = findCalleeFunctionSamples(*I)->getName();
+        const char *Reason = "Callee function not available";
+        CalledFunction = F.getParent()->getFunction(CalleeFunctionName);
+        if (CalledFunction && isLegalToPromote(I, CalledFunction, &Reason)) {
+          // The indirect target was promoted and inlined in the profile, as a
+          // result, we do not have profile info for the branch probability.
+          // We set the probability to 80% taken to indicate that the static
+          // call is likely taken.
+          DI = promoteIndirectCall(I, CalledFunction, 80, 100);
+          PromotedInsns.insert(I);
+        } else {
+          DEBUG(dbgs() << "\nFailed to promote indirect call to "
+                       << CalleeFunctionName << " because " << Reason << "\n");
+        }
+      }
       if (!CalledFunction || !CalledFunction->getSubprogram())
         continue;
+      CallSite CS(DI);
       DebugLoc DLoc = I->getDebugLoc();
       uint64_t NumSamples = findCalleeFunctionSamples(*I)->getTotalSamples();
       if (InlineFunction(CS, IFI)) {
         LocalChanged = true;
         emitOptimizationRemark(Ctx, DEBUG_TYPE, F, DLoc,
                                Twine("inlined hot callee '") +
                                    CalledFunction->getName() + "' with " +
                                    Twine(NumSamples) + " samples into '" +
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");
 
   Changed |= inlineHotFunctions(F);
 
   // Compute basic block weights.
   Changed |= computeBlockWeights(F);
 
   if (Changed) {
     // Compute dominance and loop info needed for propagation.
     computeDominanceAndLoopInfo(F);
 

test/Transforms/SampleProfile/Inputs/indirect-call.prof

 test:63067:0
  4: 3345 _Z3barv:1398 _Z3foov:2059
+test_inline:3000:0
+ 5: foo_inline:3000
+  1: 3000
+test_noinline:3000:0
+ 5: foo_noinline:3000
+  1: 3000

test/Transforms/SampleProfile/indirect-call.ll

 ; RUN: opt < %s -sample-profile -sample-profile-file=%S/Inputs/indirect-call.prof -S | FileCheck %s
 
+; CHECK-LABEL: @test
 define void @test(void ()*) !dbg !3 {
   %2 = alloca void ()*
   store void ()* %0, void ()** %2
   %3 = load void ()*, void ()** %2
   ; CHECK: call {{.*}}, !prof ![[PROF:[0-9]+]]
   call void %3(), !dbg !4
   ret void
 }
 
+; CHECK-LABEL: @test_inline
+; If the indirect call is promoted and inlined in profile, we should promote and inline it.
+define void @test_inline(void ()*) !dbg !3 {
+  %2 = alloca void ()*
+  store void ()* %0, void ()** %2
+  %3 = load void ()*, void ()** %2
+; CHECK: icmp {{.*}} @foo_inline
+; CHECK: if.true.direct_targ:
+; CHECK-NOT: call
+; CHECK: if.false.orig_indirect:
+; CHECK: call
+  call void %3(), !dbg !5
+  ret void
+}
+
+; CHECK-LABEL: @test_noinline
+; If the indirect call target is not available, we should not promote it.
+define void @test_noinline(void ()*) !dbg !3 {
+  %2 = alloca void ()*
+  store void ()* %0, void ()** %2
+  %3 = load void ()*, void ()** %2
+; CHECK-NOT: icmp
+; CHECK: call
+  call void %3(), !dbg !5
+  ret void
+}
+
+define void @foo_inline() !dbg !3 {
+  ret void
+}
+
+define i32 @foo_noinline(i32 %x) !dbg !3 {
+  ret i32 %x
+}
+
 !llvm.dbg.cu = !{!0}
 !llvm.module.flags = !{!2}
 
 !0 = distinct !DICompileUnit(language: DW_LANG_C_plus_plus, file: !1)
 !1 = !DIFile(filename: "test.cc", directory: "/")
 !2 = !{i32 2, !"Debug Info Version", i32 3}
 !3 = distinct !DISubprogram(name: "test", scope: !1, file: !1, line: 1, unit: !0)
 !4 = !DILocation(line: 5, scope: !3)
+!5 = !DILocation(line: 6, scope: !3)
 ; CHECK: ![[PROF]] = !{!"VP", i32 0, i64 3457, i64 9191153033785521275, i64 2059, i64 -1069303473483922844, i64 1398}