[llvm-profgen] Update callsite body samples by summing up all call target samples.

[hoy]

Summary

Current profile generation caculcates callsite body samples and call target samples separately. The former is done based on LBR range samples while the latter is done based on branch samples. Note that there's a subtle difference. LBR ranges is formed from two consecutive branch samples. Therefore the last entry in a LBR record will not be counted towards body samples while there's still a chance for it to be counted towards call targets if it is a function call. I'm making sense of the call body samples by updating it to the aggregation of call targets.

[wenlei]

llvm/include/llvm/ProfileData/SampleProf.h

793

LBR ranges is formed from two consecutive branch samples. Therefore the last entry in a LBR record will not be counted towards body samples while there's still a chance for it to be counted towards call targets if it is a function call

Based on this theory, is it actually possible for I.second.getSamples() to be larger than TargetSamples?

llvm/tools/llvm-profgen/ProfileGenerator.cpp

94

I'm not sure if we need a switch here. It feels to me that we should always try to make the counts consistent. But ofc, that means more testing is needed.

llvm/tools/llvm-profgen/ProfileGenerator.h

104

nit: updateFunctionSamples?

[hoy]

llvm/include/llvm/ProfileData/SampleProf.h

793

Actually it is possible. If some call targets are external targets, they won't be counted, but the body sample count which is from the lbr ranges can include them.

llvm/tools/llvm-profgen/ProfileGenerator.cpp

94

Makes sense to make it unconditional.

Regarding testing, it should have minimal impact on CS probe profile. I'll test for regular non-CS profile.

llvm/tools/llvm-profgen/ProfileGenerator.h

104

done.

[hoy]

Updating D122609: [llvm-profgen] An option to update callsite body samples by summing up all call target samples.

[wenlei]

llvm/include/llvm/ProfileData/SampleProf.h

28

what triggered this change?

793

Ok, add a comment?

[hoy]

Updating D122609: [llvm-profgen] Update callsite body samples by summing up all call target samples.

[hoy]

Updating D122609: [llvm-profgen] Update callsite body samples by summing up all call target samples.

llvm/include/llvm/ProfileData/SampleProf.h

793

done.

[wenlei]

lgtm, thanks.

[hoy]

Performance testing came back neutral, with a 99.962% profile similarity.

llvm/include/llvm/ProfileData/SampleProf.h

 #include "llvm/ADT/StringRef.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/GlobalValue.h"
 #include "llvm/Support/Allocator.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorOr.h"
 #include "llvm/Support/MathExtras.h"
 #include <algorithm>
 #include <cstdint>
 #include <list>
 #include <map>
 #include <set>
 #include <sstream>
 #include <string>
 #include <system_error>
 #include <unordered_map>
 #include <utility>
public:
   bool hasCalls() const { return !CallTargets.empty(); }
 
   uint64_t getSamples() const { return NumSamples; }
   const CallTargetMap &getCallTargets() const { return CallTargets; }
   const SortedCallTargetSet getSortedCallTargets() const {
     return SortCallTargets(CallTargets);
   }
 
+  uint64_t getCallTargetSum() const {
+    uint64_t Sum = 0;
+    for (const auto &I : CallTargets)
+      Sum += I.second;
+    return Sum;
+  }
+
   /// Sort call targets in descending order of call frequency.
   static const SortedCallTargetSet SortCallTargets(const CallTargetMap &Targets) {
     SortedCallTargetSet SortedTargets;
     for (const auto &I : Targets) {
       SortedTargets.emplace(I.first(), I.second);
     }
     return SortedTargets;
   }
public:
 
   sampleprof_error addBodySamplesForProbe(uint32_t Index, uint64_t Num,
                                           uint64_t Weight = 1) {
     SampleRecord S;
     S.addSamples(Num, Weight);
     return BodySamples[LineLocation(Index, 0)].merge(S, Weight);
   }
 
+  // Accumulate all call target samples to update the body samples.
+  void updateCallsiteSamples() {
+    for (auto &I : BodySamples) {
+      uint64_t TargetSamples = I.second.getCallTargetSum();
+      // It's possible that the body sample count can be greater than the call
+      // target sum. E.g, if some call targets are external targets, they won't
+      // be considered valid call targets, but the body sample count which is
+      // from lbr ranges can actually include them.
+      if (TargetSamples > I.second.getSamples())
+        I.second.addSamples(TargetSamples - I.second.getSamples());
+    }
+  }
+
   // Accumulate all body samples to set total samples.
   void updateTotalSamples() {
     setTotalSamples(0);
     for (const auto &I : BodySamples)
       addTotalSamples(I.second.getSamples());
 
     for (auto &I : CallsiteSamples) {
       for (auto &CS : I.second) {

llvm/test/tools/llvm-profgen/inline-noprobe2.test

 ;CHECK:  4.1: 0
 ;CHECK:  4.3: 0
 ;CHECK:  5.1: 17
 ;CHECK:  5.3: 17
 ;CHECK:  6: 17
 ;CHECK:  6.1: 17
 ;CHECK:  6.3: 17
 ;CHECK:  7: 0
-;CHECK:  8: 0 quick_sort:1
+;CHECK:  8: 1 quick_sort:1
 ;CHECK:  9: 0
 ;CHECK:  11: 0
 ;CHECK:  14: 0
 ;CHECK:  65499: 0
 ;CHECK: partition_pivot_last:1210:7
 ;CHECK:  1: 6
 ;CHECK:  2: 6
 ;CHECK:  3: 6

 ;CHECK:   3: 18
 ;CHECK:  6: swap:85
 ;CHECK:   1: 5
 ;CHECK:   2: 5
 ;CHECK:   3: 5
 ;CHECK: quick_sort:903:25
 ;CHECK:  1: 24
 ;CHECK:  2: 12 partition_pivot_last:7 partition_pivot_first:5
-;CHECK:  3: 11 quick_sort:12
+;CHECK:  3: 12 quick_sort:12
 ;CHECK:  4: 12 quick_sort:12
 ;CHECK:  6: 24
 ;CHECK:  65507: 12
 
 
 
 ; original code:
 ; clang -O3 -g -fno-optimize-sibling-calls -fdebug-info-for-profiling qsort.c -o a.out

llvm/test/tools/llvm-profgen/noinline-noprobe.test

 ; RUN: llvm-profgen --format=text --perfscript=%S/Inputs/noprobe.perfscript --binary=%S/Inputs/noprobe.perfbin --output=%t --skip-symbolization
 ; RUN: FileCheck %s --input-file %t --check-prefix=CHECK-RAW-PROFILE
 ; RUN: llvm-profgen --format=text --perfscript=%S/Inputs/noprobe.mmap.perfscript --binary=%S/Inputs/noprobe.perfbin --output=%t --skip-symbolization
 ; RUN: FileCheck %s --input-file %t --check-prefix=CHECK-RAW-PROFILE
 ; RUN: llvm-profgen --format=text --perfscript=%S/Inputs/noprobe.aggperfscript --binary=%S/Inputs/noprobe.perfbin --output=%t --skip-symbolization
 ; RUN: FileCheck %s --input-file %t --check-prefix=CHECK-RAW-PROFILE-AGG
 ; RUN: llvm-profgen --format=text --perfscript=%S/Inputs/noprobe.perfscript --binary=%S/Inputs/noprobe.perfbin --output=%t
 ; RUN: FileCheck %s --input-file %t --check-prefix=CHECK
 
 ;CHECK: foo:1241:0
 ;CHECK:  0: 0
 ;CHECK:  1: 0
 ;CHECK:  2: 19
-;CHECK:  3: 19 bar:21
+;CHECK:  3: 21 bar:21
 ;CHECK:  4: 0
 ;CHECK:  5: 0
 ;CHECK: bar:926:21
 ;CHECK:  0: 20
 ;CHECK:  1: 20
 ;CHECK:  2: 13
 ;CHECK:  4: 6
 ;CHECK:  5: 18

llvm/test/tools/llvm-profgen/update-samples.test

+; RUN: llvm-profgen --format=text --perfscript=%S/Inputs/noprobe.perfscript --binary=%S/Inputs/noprobe.perfbin --output=%t1
+; RUN: FileCheck %s --input-file %t1 --check-prefix=CALLSITE
+; RUN: llvm-profgen --format=text --perfscript=%S/Inputs/noprobe.perfscript --binary=%S/Inputs/noprobe.perfbin --output=%t2 --update-total-samples=1
+; RUN: FileCheck %s --input-file %t2 --check-prefix=TOTAL
+
+
+;CALLSITE: foo:1241:0
+;CALLSITE:  0: 0
+;CALLSITE:  1: 0
+;CALLSITE:  2: 19
+;CALLSITE:  3: 21 bar:21
+;CALLSITE:  4: 0
+;CALLSITE:  5: 0
+
+;TOTAL: foo:40:0
+;TOTAL:  0: 0
+;TOTAL:  1: 0
+;TOTAL:  2: 19
+;TOTAL:  3: 21 bar:21
+;TOTAL:  4: 0
+;TOTAL:  5: 0
+
+
+; original code:
+; clang -O3 -g -fdebug-info-for-profiling test.c -fno-inline -o a.out
+#include <stdio.h>
+
+int bar(int x, int y) {
+  if (x % 3) {
+    return x - y;
+  }
+  return x + y;
+}
+
+void foo() {
+  int s, i = 0;
+  while (i++ < 4000 * 4000)
+    if (i % 91) s = bar(i, s); else s += 30;
+  printf("sum is %d\n", s);
+}
+
+int main() {
+  foo();
+  return 0;
+}

llvm/tools/llvm-profgen/ProfileGenerator.h

void extractProbesFromRange(const RangeSample &RangeCounter,
                               ProbeCounterMap &ProbeCounter,
                               bool FindDisjointRanges = true);
 
   // Helper function for updating body sample for a leaf location in
   // FunctionProfile
   void updateBodySamplesforFunctionProfile(FunctionSamples &FunctionProfile,
                                            const SampleContextFrame &LeafLoc,
                                            uint64_t Count);
+
+  void updateFunctionSamples();
+
   void updateTotalSamples();
 
+  void updateCallsiteSamples();
+
   StringRef getCalleeNameForOffset(uint64_t TargetOffset);
 
   void computeSummaryAndThreshold();
 
   void calculateAndShowDensity(const SampleProfileMap &Profiles);
 
   double calculateDensity(const SampleProfileMap &Profiles,
                           uint64_t HotCntThreshold);

llvm/tools/llvm-profgen/ProfileGenerator.cpp

 
 static cl::opt<bool> UpdateTotalSamples(
     "update-total-samples", llvm::cl::init(false),
     llvm::cl::desc(
         "Update total samples by accumulating all its body samples."),
     llvm::cl::Optional);
 
 extern cl::opt<int> ProfileSummaryCutoffHot;
 
 static cl::opt<bool> GenCSNestedProfile(
     "gen-cs-nested-profile", cl::Hidden, cl::init(true),
     cl::desc("Generate nested function profiles for CSSPGO"));
 
 using namespace llvm;
 using namespace sampleprof;
 
 namespace llvm {
void ProfileGeneratorBase::updateBodySamplesforFunctionProfile(
   uint64_t PreviousCount = R ? R.get() : 0;
   if (PreviousCount <= Count) {
     FunctionProfile.addBodySamples(LeafLoc.Location.LineOffset, Discriminator,
                                    Count - PreviousCount);
   }
 }
 
 void ProfileGeneratorBase::updateTotalSamples() {
-  if (!UpdateTotalSamples)
-    return;
-
   for (auto &Item : ProfileMap) {
     FunctionSamples &FunctionProfile = Item.second;
     FunctionProfile.updateTotalSamples();
   }
 }
 
+void ProfileGeneratorBase::updateCallsiteSamples() {
+  for (auto &Item : ProfileMap) {
+    FunctionSamples &FunctionProfile = Item.second;
+    FunctionProfile.updateCallsiteSamples();
+  }
+}
+
+void ProfileGeneratorBase::updateFunctionSamples() {
+  updateCallsiteSamples();
+
+  if (UpdateTotalSamples)
+    updateTotalSamples();
+}
+
 void ProfileGeneratorBase::collectProfiledFunctions() {
   std::unordered_set<const BinaryFunction *> ProfiledFunctions;
   if (SampleCounters) {
     // Go through all the stacks, ranges and branches in sample counters, use
     // the start of the range to look up the function it belongs and record the
     // function.
     for (const auto &CI : *SampleCounters) {
       if (const auto *CtxKey = dyn_cast<AddrBasedCtxKey>(CI.first.getPtr())) {
void ProfileGenerator::generateLineNumBasedProfile() {
   assert(SampleCounters->size() == 1 &&
          "Must have one entry for profile generation.");
   const SampleCounter &SC = SampleCounters->begin()->second;
   // Fill in function body samples
   populateBodySamplesForAllFunctions(SC.RangeCounter);
   // Fill in boundary sample counts as well as call site samples for calls
   populateBoundarySamplesForAllFunctions(SC.BranchCounter);
 
-  updateTotalSamples();
+  updateFunctionSamples();
 }
 
 void ProfileGenerator::generateProbeBasedProfile() {
   assert(SampleCounters->size() == 1 &&
          "Must have one entry for profile generation.");
   // Enable pseudo probe functionalities in SampleProf
   FunctionSamples::ProfileIsProbeBased = true;
   const SampleCounter &SC = SampleCounters->begin()->second;
   // Fill in function body samples
   populateBodySamplesWithProbesForAllFunctions(SC.RangeCounter);
   // Fill in boundary sample counts as well as call site samples for calls
   populateBoundarySamplesWithProbesForAllFunctions(SC.BranchCounter);
 
-  updateTotalSamples();
+  updateFunctionSamples();
 }
 
 void ProfileGenerator::populateBodySamplesWithProbesForAllFunctions(
     const RangeSample &RangeCounter) {
   ProbeCounterMap ProbeCounter;
   // preprocessRangeCounter returns disjoint ranges, so no longer to redo it
   // inside extractProbesFromRange.
   extractProbesFromRange(preprocessRangeCounter(RangeCounter), ProbeCounter,
populateBoundarySamplesForFunction(CtxKey->Context, FunctionProfile,
                                        CI.second.BranchCounter);
   }
   // Fill in call site value sample for inlined calls and also use context to
   // infer missing samples. Since we don't have call count for inlined
   // functions, we estimate it from inlinee's profile using the entry of the
   // body sample.
   populateInferredFunctionSamples();
 
-  updateTotalSamples();
+  updateFunctionSamples();
 }
 
 void CSProfileGenerator::populateBodySamplesForFunction(
     FunctionSamples &FunctionProfile, const RangeSample &RangeCounter) {
   // Compute disjoint ranges first, so we can use MAX
   // for calculating count for each location.
   RangeSample Ranges;
   findDisjointRanges(Ranges, RangeCounter);