Add indirect call promotion to SamplePGO

[danielcdh]

Summary

This patch adds metadata for indirect call promotion in the sample profile loader.

[davidxl]

include/llvm/ProfileData/SampleProf.h

241

Add a documentation comment.

lib/Transforms/IPO/SampleProfile.cpp

1106

HeaderLineno --> FuncStartLine?

1119

Can the following be a utility function shared with instrumentation based PGO?

[danielcdh]

Address David's comments.

[davidxl]

lgtm

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

3

Swap the targets to test sorting

include/llvm/ProfileData/SampleProf.h

if (ret == BodySamples.end())
       return std::error_code();
     uint64_t T = 0;
     for (const auto &t_c : ret->second.getCallTargets()) {
       T += t_c.second;
     }
     return T;
   }
 
+  ErrorOr<SampleRecord::CallTargetMap>
+  findCallTargetMapAt(uint32_t LineOffset, uint32_t Discriminator) const {
+    const auto &ret = BodySamples.find(LineLocation(LineOffset, Discriminator));
+    if (ret == BodySamples.end())
+      return std::error_code();
+    return ret->second.getCallTargets();
+  }
+
   /// Return the function samples at the given callsite location.
   FunctionSamples &functionSamplesAt(const LineLocation &Loc) {
     return CallsiteSamples[Loc];
   }
 
   /// Return a pointer to function samples at the given callsite location.
   const FunctionSamples *findFunctionSamplesAt(const LineLocation &Loc) const {
     auto iter = CallsiteSamples.find(Loc);

lib/Transforms/IPO/SampleProfile.cpp

 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/PostDominators.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DebugInfo.h"
 #include "llvm/IR/DiagnosticInfo.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
+#include "llvm/IR/GlobalValue.h"
 #include "llvm/IR/InstIterator.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/MDBuilder.h"
 #include "llvm/IR/Metadata.h"
 #include "llvm/IR/Module.h"
 #include "llvm/Pass.h"
+#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/Utils/Cloning.h"
for (auto &BI : F) {
     for (succ_iterator SI = succ_begin(B1), SE = succ_end(B1); SI != SE; ++SI) {
       BasicBlock *B2 = *SI;
       if (Visited.insert(B2).second)
         Successors[B1].push_back(B2);
     }
   }
 }
 
+/// Sorts the CallTargetMap \p M by count in descending order and stores the
+/// sorted result in \p Sorted. Returns the total counts.
+static uint64_t
+SortCallTargets(SmallVector<std::pair<uint64_t, uint64_t>, 2> &Sorted,
+                const SampleRecord::CallTargetMap &M) {
+  Sorted.clear();
+  uint64_t Sum = 0;
+  for (auto I = M.begin(); I != M.end(); ++I) {
+    Sum += I->getValue();
+    Sorted.push_back(
+        std::make_pair(Function::getGUID(I->getKey()), I->getValue()));
+  }
+  std::sort(Sorted.begin(), Sorted.end(),
+            [](const std::pair<uint64_t, uint64_t> &L,
+               const std::pair<uint64_t, uint64_t> &R) {
+              if (L.second == R.second)
+                return L.first > R.first;
+              else
+                return L.second > R.second;
+            });
+  return Sum;
+}
+
 /// \brief Propagate weights into edges
 ///
 /// The following rules are applied to every block BB in the CFG:
 ///
 /// - If BB has a single predecessor/successor, then the weight
 ///   of that edge is the weight of the block.
 ///
 /// - If all incoming or outgoing edges are known except one, and the
void SampleProfileLoader::propagateWeights(Function &F) {
   DEBUG(dbgs() << "\nPropagation complete. Setting branch weights\n");
   LLVMContext &Ctx = F.getContext();
   MDBuilder MDB(Ctx);
   for (auto &BI : F) {
     BasicBlock *BB = &BI;
 
     if (BlockWeights[BB]) {
       for (auto &I : BB->getInstList()) {
-        if (CallInst *CI = dyn_cast<CallInst>(&I)) {
-          if (!dyn_cast<IntrinsicInst>(&I)) {
-            SmallVector<uint32_t, 1> Weights;
-            Weights.push_back(BlockWeights[BB]);
-            CI->setMetadata(LLVMContext::MD_prof,
-                            MDB.createBranchWeights(Weights));
-          }
+        if (!isa<CallInst>(I) && !isa<InvokeInst>(I))
+          continue;
+        CallSite CS(&I);
+        if (!CS.getCalledFunction()) {
+          const DebugLoc &DLoc = I.getDebugLoc();
+          if (!DLoc)
+            continue;
+          const DILocation *DIL = DLoc;
+          unsigned Lineno = DLoc.getLine();
+          unsigned HeaderLineno = DIL->getScope()->getSubprogram()->getLine();
+          uint32_t LineOffset = getOffset(Lineno, HeaderLineno);
+          uint32_t Discriminator = DIL->getDiscriminator();
+
+          const FunctionSamples *FS = findFunctionSamples(I);
+          if (!FS)
+            continue;
+          auto T = FS->findCallTargetMapAt(LineOffset, Discriminator);
+          if (!T || T.get().size() == 0)
+            continue;
+          SmallVector<std::pair<uint64_t, uint64_t>, 2> SortedCallTargets;
+          uint64_t Sum = SortCallTargets(SortedCallTargets, T.get());
+          LLVMContext &Ctx = I.getParent()->getParent()->getContext();
+          MDBuilder MDHelper(Ctx);
+          SmallVector<Metadata *, 3> Vals;
+          // Tag
+          Vals.push_back(MDHelper.createString("VP"));
+          // Value Kind
+          Vals.push_back(MDHelper.createConstant(ConstantInt::get(
+              Type::getInt32Ty(Ctx), IPVK_IndirectCallTarget)));
+          // Total Count
+          Vals.push_back(MDHelper.createConstant(
+              ConstantInt::get(Type::getInt64Ty(Ctx), Sum)));
+          for (const auto &T_C : SortedCallTargets) {
+            Vals.push_back(MDHelper.createConstant(
+                ConstantInt::get(Type::getInt64Ty(Ctx), T_C.first)));
+            Vals.push_back(MDHelper.createConstant(
+                ConstantInt::get(Type::getInt64Ty(Ctx), T_C.second)));
+          }
+          I.setMetadata(LLVMContext::MD_prof, MDNode::get(Ctx, Vals));
+        } else if (!dyn_cast<IntrinsicInst>(&I)) {
+          I.setMetadata(LLVMContext::MD_prof, MDB.createBranchWeights(Weights));
         }
       }
     }
     TerminatorInst *TI = BB->getTerminator();
     if (TI->getNumSuccessors() == 1)
       continue;
     if (!isa<BranchInst>(TI) && !isa<SwitchInst>(TI))
       continue;

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

+test:63067:0
+ 4: 3345 _Z3foov:2059 _Z3barv:1398

test/Transforms/SampleProfile/indirect-call.ll

+; RUN: opt < %s -sample-profile -sample-profile-file=%S/Inputs/indirect-call.prof -S | FileCheck %s
+
+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
+}
+
+!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)
+; CHECK: ![[PROF]] = !{!"VP", i32 0, i64 3457, i64 9191153033785521275, i64 2059, i64 -1069303473483922844, i64 1398}