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

621

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

1282–1283

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

657

better to return the failed reason and emit debug output.

[danielcdh]

update

[davidxl]

lib/Transforms/IPO/SampleProfile.cpp

668

reset CalledFunction to null or continue?

[danielcdh]

update

[davidxl]

lgtm

include/llvm/Transforms/Instrumentation.h

ModulePass *createGCOVProfilerPass(const GCOVOptions &Options =
                                    GCOVOptions::getDefault());
 
 // PGO Instrumention
 ModulePass *createPGOInstrumentationGenLegacyPass();
 ModulePass *
 createPGOInstrumentationUseLegacyPass(StringRef Filename = StringRef(""));
 ModulePass *createPGOIndirectCallPromotionLegacyPass(bool InLTO = false);
 
+// Helper function that transforms Inst (either a indirect-call instruction, or
+// an invoke instruction , to a conditional call to F. This is like:
+//     if (Inst.CalledValue == F)
+//        F(...);
+//     else
+//        Inst(...);
+//     end
+// TotalCount is the profile count value that the instruction executes.
+// Count is the profile count value that F is the target function.
+// These two values are being used to update the branch weight.
+// Returns the promoted direct call instruction.
+Instruction *promoteIndirectCall(Instruction *Inst, Function *F, uint64_t Count,
+                                 uint64_t TotalCount);
+
 /// Options for the frontend instrumentation based profiling pass.
 struct InstrProfOptions {
   // Add the 'noredzone' attribute to added runtime library calls.
   bool NoRedZone = false;
 
   // Name of the profile file to use as output
   std::string InstrProfileOutput;
 

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"
 

 protected:
   bool runOnFunction(Function &F);
   unsigned getFunctionLoc(Function &F);
   bool emitAnnotations(Function &F);
   ErrorOr<uint64_t> getInstWeight(const Instruction &I);
   ErrorOr<uint64_t> getBlockWeight(const BasicBlock *BB);
   const FunctionSamples *findCalleeFunctionSamples(const Instruction &I) const;
   const FunctionSamples *findFunctionSamples(const Instruction &I) const;
-  bool inlineHotFunctions(Function &F);
+  bool inlineHotFunctions(Function &F, DenseSet<Instruction *> PromotedInsns);
   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);
   void findEquivalencesFor(BasicBlock *BB1, ArrayRef<BasicBlock *> Descendants,
                            DominatorTreeBase<BasicBlock> *DomTree);
   void propagateWeights(Function &F);

 /// \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.
 ///
 /// \param F function to perform iterative inlining.
 ///
 /// \returns True if there is any inline happened.
-bool SampleProfileLoader::inlineHotFunctions(Function &F) {
+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)) {
+        CalledFunction = F.getParent()->getFunction(
+            findCalleeFunctionSamples(*I)->getName());
+        if (CalledFunction) {
+          DI = promoteIndirectCall(I, CalledFunction, 80, 100);
+          PromotedInsns.insert(I);
+        }
+      }
       if (!CalledFunction || !CalledFunction->getSubprogram())
         continue;
+      CallSite CS(DI);
       if (InlineFunction(CS, IFI)) {
         DebugLoc DLoc = I->getDebugLoc();
         uint64_t NumSamples = findCalleeFunctionSamples(*I)->getTotalSamples();
         LocalChanged = true;
         emitOptimizationRemark(Ctx, DEBUG_TYPE, F, DLoc,
                                Twine("inlined hot callee '") +
                                    CalledFunction->getName() + "' with " +
                                    Twine(NumSamples) + " samples into '" +
                                    F.getName() + "'");
       }
     }
     if (LocalChanged) {
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);
+  DenseSet<Instruction *> PromotedInsns;
+  Changed |= inlineHotFunctions(F, PromotedInsns);
 
   // Compute basic block weights.
   Changed |= computeBlockWeights(F);
 
   if (Changed) {
     // Compute dominance and loop info needed for propagation.
     computeDominanceAndLoopInfo(F);
 

lib/Transforms/Instrumentation/IndirectCallPromotion.cpp

private:
   // of promotions. Inst is the candidate indirect call, ValueDataRef
   // contains the array of value profile data for profiled targets,
   // TotalCount is the total profiled count of call executions, and
   // NumCandidates is the number of candidate entries in ValueDataRef.
   std::vector<PromotionCandidate> getPromotionCandidatesForCallSite(
       Instruction *Inst, const ArrayRef<InstrProfValueData> &ValueDataRef,
       uint64_t TotalCount, uint32_t NumCandidates);
 
-  // Main function that transforms Inst (either a indirect-call instruction, or
-  // an invoke instruction , to a conditional call to F. This is like:
-  //     if (Inst.CalledValue == F)
-  //        F(...);
-  //     else
-  //        Inst(...);
-  //     end
-  // TotalCount is the profile count value that the instruction executes.
-  // Count is the profile count value that F is the target function.
-  // These two values are being used to update the branch weight.
-  void promote(Instruction *Inst, Function *F, uint64_t Count,
-               uint64_t TotalCount);
-
   // Promote a list of targets for one indirect-call callsite. Return
   // the number of promotions.
   uint32_t tryToPromote(Instruction *Inst,
                         const std::vector<PromotionCandidate> &Candidates,
                         uint64_t &TotalCount);
 
   static const char *StatusToString(const TargetStatus S) {
     switch (S) {

 // It transforms to:
 //     if (Foo == DirectCallee)
 //        Ret1 = DirectCallee(Args);
 //     else
 //        Ret2 = (*Foo)(Args);
 //     Ret = phi(Ret1, Ret2);
 // It adds type casts for the args do not match the parameters and the return
 // value. Branch weights metadata also updated.
-void ICallPromotionFunc::promote(Instruction *Inst, Function *DirectCallee,
-                                 uint64_t Count, uint64_t TotalCount) {
+// Returns the promoted direct call instruction.
+Instruction *llvm::promoteIndirectCall(Instruction *Inst,
+                                       Function *DirectCallee, uint64_t Count,
+                                       uint64_t TotalCount) {
   assert(DirectCallee != nullptr);
   BasicBlock *BB = Inst->getParent();
   // Just to suppress the non-debug build warning.
   (void)BB;
   DEBUG(dbgs() << "\n\n== Basic Block Before ==\n");
   DEBUG(dbgs() << *BB << "\n");
 
   BasicBlock *DirectCallBB, *IndirectCallBB, *MergeBB;
Instruction *llvm::promoteIndirectCall(Instruction *Inst,
   }
 
   insertCallRetPHI(Inst, NewInst, DirectCallee);
 
   DEBUG(dbgs() << "\n== Basic Blocks After ==\n");
   DEBUG(dbgs() << *BB << *DirectCallBB << *IndirectCallBB << *MergeBB << "\n");
 
   emitOptimizationRemark(
-      F.getContext(), "pgo-icall-prom", F, Inst->getDebugLoc(),
+      BB->getContext(), "pgo-icall-prom", *BB->getParent(), Inst->getDebugLoc(),
       Twine("Promote indirect call to ") + DirectCallee->getName() +
           " with count " + Twine(Count) + " out of " + Twine(TotalCount));
+  return NewInst;
 }
 
 // Promote indirect-call to conditional direct-call for one callsite.
 uint32_t ICallPromotionFunc::tryToPromote(
     Instruction *Inst, const std::vector<PromotionCandidate> &Candidates,
     uint64_t &TotalCount) {
   uint32_t NumPromoted = 0;
 
   for (auto &C : Candidates) {
     uint64_t Count = C.Count;
-    promote(Inst, C.TargetFunction, Count, TotalCount);
+    promoteIndirectCall(Inst, C.TargetFunction, Count, TotalCount);
     assert(TotalCount >= Count);
     TotalCount -= Count;
     NumOfPGOICallPromotion++;
     NumPromoted++;
   }
   return NumPromoted;
 }
 

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
+}
+
 !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}