Use the first instruction's count to estimate the funciton's entry frequency.

[danielcdh]

Summary

In the current implementation, we only have accurate profile count for standalone symbols. For inlined functions, we do not have entry count data because it's not available in LBR. In this patch, we use the first instruction's frequency to estimiate the function's entry count, especially for inlined functions. This may be inaccurate due to debug info in optimized code. However, this is a better estimate than the static 80/20 estimation we have in the current implementation.

[tejohnson]

Started looking at, but have a few initial questions.

include/llvm/ProfileData/SampleProf.h

303

s/standalong/standalone/

304

Should this be used somewhere in this change since it is preferred?

311

What is this line checking?

316

What do these samples correspond to?

[danielcdh]

include/llvm/ProfileData/SampleProf.h

304

This was used by standalone symbols before this change. The 2 newly added use of getEntryCount was used in this patch for inlined functions.

311

Added comment to make it clear.

316

Updated comment to make it clear.

[danielcdh]

update comment

[danielcdh]

rebase

[danielcdh]

rebase

[tejohnson]

include/llvm/ProfileData/SampleProf.h

317

"An indirect callsite may be..."?

lib/Transforms/IPO/SampleProfile.cpp

1268

Is this annotated the value profile before or after promotion/inlining of the indirect calls recorded as inlined in the profile? If after, not sure why we want to include the counts of the promoted/inlined targets in Sum (which AFAICT is what will happen by computing Sum via findIndirectCallFunctionSamples).

[danielcdh]

update comment

lib/Transforms/IPO/SampleProfile.cpp

1268

It's after. The reason we need to have all promoted counts included in SUM is because we do not want to promote too many targets. E.g. if an indirect call site has already been promoted to 3 targets that covers 99% of the case. The rest 1%, even if it's 100% to a 4th target. we do not want to promote it.

[tejohnson]

lib/Transforms/IPO/SampleProfile.cpp

1268

The reason I ask is that this is different than what is done by the main ICP pass. E.g. see ICallPromotionFunc::processFunction and ICallPromotionFunc::tryToPromote, which update the total count before re-generating a new VP annotation. It also makes this patch have a larger effect than what is described in the summary. Suggest splitting this change out and evaluating separately.

[danielcdh]

extract the change that update the SUM of VP.

[tejohnson]

LGTM

include/llvm/ProfileData/SampleProf.h

const FunctionSamples *findFunctionSamplesAt(const LineLocation &Loc,
     return R;
   }
 
   bool empty() const { return TotalSamples == 0; }
 
   /// Return the total number of samples collected inside the function.
   uint64_t getTotalSamples() const { return TotalSamples; }
 
-  /// Return the total number of samples collected at the head of the
-  /// function.
+  /// Return the total number of branch samples that have the function as the
+  /// branch target. This should be equivalent to the sample of the first
+  /// instruction of the symbol. But as we directly get this info for raw
+  /// profile without referring to potentially inaccurate debug info, this
+  /// gives more accurate profile data and is preferred for standalone symbols.
   uint64_t getHeadSamples() const { return TotalHeadSamples; }
 
+  /// Return the sample count of the first instruction of the function.
+  /// The function can be either a standalone symbol or an inlined function.
+  uint64_t getEntrySamples() const {
+    // Use either BodySamples or CallsiteSamples which ever has the smaller
+    // lineno.
+    if (!BodySamples.empty() &&
+        (CallsiteSamples.empty() ||
+         BodySamples.begin()->first < CallsiteSamples.begin()->first))
+      return BodySamples.begin()->second.getSamples();
+    if (!CallsiteSamples.empty()) {
+      uint64_t T = 0;
+      // A callsite may be promoted to several inlined direct calls. We need
+      // to get the sum of them.
+      for (const auto &N_FS : CallsiteSamples.begin()->second)
+        T += N_FS.second.getEntrySamples();
+      return T;
+    }
+    return 0;
+  }
+
   /// Return all the samples collected in the body of the function.
   const BodySampleMap &getBodySamples() const { return BodySamples; }
 
   /// Return all the callsite samples collected in the body of the function.
   const CallsiteSampleMap &getCallsiteSamples() const {
     return CallsiteSamples;
   }
 

lib/Transforms/IPO/SampleProfile.cpp

 protected:
   bool runOnFunction(Function &F, ModuleAnalysisManager *AM);
   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;
   std::vector<const FunctionSamples *>
-  findIndirectCallFunctionSamples(const Instruction &I) const;
+  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);
   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);
SampleProfileLoader::findCalleeFunctionSamples(const Instruction &Inst) const {
   if (FS == nullptr)
     return nullptr;
 
   return FS->findFunctionSamplesAt(
       LineLocation(getOffset(DIL), DIL->getBaseDiscriminator()), CalleeName);
 }
 
 /// Returns a vector of FunctionSamples that are the indirect call targets
-/// of \p Inst. The vector is sorted by the total number of samples.
+/// of \p Inst. The vector is sorted by the total number of samples. Stores
+/// the total call count of the indirect call in \p Sum.
 std::vector<const FunctionSamples *>
 SampleProfileLoader::findIndirectCallFunctionSamples(
-    const Instruction &Inst) const {
+    const Instruction &Inst, uint64_t &Sum) const {
   const DILocation *DIL = Inst.getDebugLoc();
   std::vector<const FunctionSamples *> R;
 
   if (!DIL) {
     return R;
   }
 
   const FunctionSamples *FS = findFunctionSamples(Inst);
   if (FS == nullptr)
     return R;
 
+  uint32_t LineOffset = getOffset(DIL);
+  uint32_t Discriminator = DIL->getBaseDiscriminator();
+
+  auto T = FS->findCallTargetMapAt(LineOffset, Discriminator);
+  Sum = 0;
+  if (T)
+    for (const auto &T_C : T.get())
+      Sum += T_C.second;
   if (const FunctionSamplesMap *M = FS->findFunctionSamplesMapAt(
           LineLocation(getOffset(DIL), DIL->getBaseDiscriminator()))) {
     if (M->size() == 0)
       return R;
     for (const auto &NameFS : *M) {
+      Sum += NameFS.second.getEntrySamples();
       R.push_back(&NameFS.second);
     }
     std::sort(R.begin(), R.end(),
               [](const FunctionSamples *L, const FunctionSamples *R) {
-                return L->getTotalSamples() > R->getTotalSamples();
+                return L->getEntrySamples() > R->getEntrySamples();
               });
   }
   return R;
 }
 
 /// \brief Get the FunctionSamples for an instruction.
 ///
 /// The FunctionSamples of an instruction \p Inst is the inlined instance
while (true) {
     for (auto I : CIS) {
       Function *CalledFunction = CallSite(I).getCalledFunction();
       // Do not inline recursive calls.
       if (CalledFunction == &F)
         continue;
       if (CallSite(I).isIndirectCall()) {
         if (PromotedInsns.count(I))
           continue;
-        for (const auto *FS : findIndirectCallFunctionSamples(*I)) {
+        uint64_t Sum;
+        for (const auto *FS : findIndirectCallFunctionSamples(*I, Sum)) {
           if (IsThinLTOPreLink) {
             FS->findImportedFunctions(ImportGUIDs, F.getParent(),
                                       Samples->getTotalSamples() *
                                           SampleProfileHotThreshold / 100);
             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.
           if (CalleeFunctionName == F.getName())
             continue;
 
           const char *Reason = "Callee function not available";
           auto R = SymbolMap.find(CalleeFunctionName);
           if (R != SymbolMap.end() && R->getValue() &&
               !R->getValue()->isDeclaration() &&
               R->getValue()->getSubprogram() &&
               isLegalToPromote(I, R->getValue(), &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.
+            uint64_t C = FS->getEntrySamples();
             Instruction *DI = promoteIndirectCall(
-                I, R->getValue(), 80, 100, false, ORE);
+                I, R->getValue(), C, Sum, false, ORE);
+            Sum -= C;
             PromotedInsns.insert(I);
             // If profile mismatches, we should not attempt to inline DI.
             if ((isa<CallInst>(DI) || isa<InvokeInst>(DI)) &&
                 inlineCallInstruction(DI))
               LocalChanged = true;
           } else {
             DEBUG(dbgs()
                   << "\nFailed to promote indirect call to "
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<InstrProfValueData, 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({Function::getGUID(I->getKey()), I->getValue()});
-  }
-  std::sort(Sorted.begin(), Sorted.end(),
+/// Returns the sorted CallTargetMap \p M by count in descending order.
+static SmallVector<InstrProfValueData, 2> SortCallTargets(
+  SmallVector<InstrProfValueData, 2> R;
+  for (auto I = M.begin(); I != M.end(); ++I)
+    R.push_back({Function::getGUID(I->getKey()), I->getValue()});
+  std::sort(R.begin(), R.end(),
             [](const InstrProfValueData &L, const InstrProfValueData &R) {
               if (L.Count == R.Count)
                 return L.Value > R.Value;
               else
                 return L.Count > R.Count;
             });
-  return Sum;
+  return R;
 }
 
 /// \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 (BlockWeights[BB]) {
           uint32_t Discriminator = DIL->getBaseDiscriminator();
 
           const FunctionSamples *FS = findFunctionSamples(I);
           if (!FS)
             continue;
           auto T = FS->findCallTargetMapAt(LineOffset, Discriminator);
           if (!T || T.get().size() == 0)
             continue;
-          SmallVector<InstrProfValueData, 2> SortedCallTargets;
-          uint64_t Sum = SortCallTargets(SortedCallTargets, T.get());
+          SmallVector<InstrProfValueData, 2> SortedCallTargets =
+              SortCallTargets(T.get());
+          uint64_t Sum;
+          findIndirectCallFunctionSamples(I, Sum);
           annotateValueSite(*I.getParent()->getParent()->getParent(), I,
                             SortedCallTargets, Sum, IPVK_IndirectCallTarget,
                             SortedCallTargets.size());
         } else if (!dyn_cast<IntrinsicInst>(&I)) {
           SmallVector<uint32_t, 1> Weights;
           Weights.push_back(BlockWeights[BB]);
           I.setMetadata(LLVMContext::MD_prof, MDB.createBranchWeights(Weights));
         }
       }

test/Transforms/SampleProfile/indirect-call.ll

 
 ; CHECK-LABEL: @test_inline
 ; If the indirect call is promoted and inlined in profile, we should promote and inline it.
 define void @test_inline(i64* (i32*)*, i32* %x) !dbg !6 {
   %2 = alloca i64* (i32*)*
   store i64* (i32*)* %0, i64* (i32*)** %2
   %3 = load i64* (i32*)*, i64* (i32*)** %2
 ; CHECK: icmp {{.*}} @foo_inline2
+; CHECK: br {{.*}} !prof ![[BR1:[0-9]+]]
 ; CHECK: if.true.direct_targ:
 ; CHECK-NOT: call
 ; CHECK: if.false.orig_indirect:
 ; CHECK: icmp {{.*}} @foo_inline1
+; CHECK: br {{.*}} !prof ![[BR2:[0-9]+]]
 ; CHECK: if.true.direct_targ1:
 ; CHECK-NOT: call
 ; CHECK: if.false.orig_indirect2:
 ; CHECK: call {{.*}} !prof ![[VP:[0-9]+]]
   call i64* %3(i32* %x), !dbg !7
   ret void
 }
 

 
 !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: 3, unit: !0)
 !4 = !DILocation(line: 4, scope: !3)
 !5 = !DILocation(line: 6, scope: !3)
 ; CHECK: ![[PROF]] = !{!"VP", i32 0, i64 3457, i64 9191153033785521275, i64 2059, i64 -1069303473483922844, i64 1398}
-; CHECK: ![[VP]] = !{!"VP", i32 0, i64 1000, i64 -6391416044382067764, i64 1000}
+; CHECK: ![[BR1]] = !{!"branch_weights", i32 4000, i32 4000}
+; CHECK: ![[BR2]] = !{!"branch_weights", i32 3000, i32 1000}
+; CHECK: ![[VP]] = !{!"VP", i32 0, i64 8000, i64 -6391416044382067764, i64 1000}
 !6 = distinct !DISubprogram(name: "test_inline", scope: !1, file: !1, line: 6, unit: !0)
 !7 = !DILocation(line: 7, scope: !6)
 !8 = distinct !DISubprogram(name: "test_inline_strip", scope: !1, file: !1, line: 8, unit: !0)
 !9 = !DILocation(line: 9, scope: !8)
 !10 = distinct !DISubprogram(name: "test_inline_strip_conflict", scope: !1, file: !1, line: 10, unit: !0)
 !11 = !DILocation(line: 11, scope: !10)
 !12 = distinct !DISubprogram(name: "test_noinline", scope: !1, file: !1, line: 12, unit: !0)
 !13 = !DILocation(line: 13, scope: !12)