[llvm-profgen] Trim cold function profiles for non-CS AutoFDO

[wlei]

Summary

This change allows to trim the profile if it's considered to be cold for baseline AutoFDO. We reuse the cold threshold from ProfileSummaryBuilder::getColdCountThreshold(..) which can be set by percent(--profile-summary-cutoff-cold) or by value(--profile-summary-cold-count).

[hoy]

llvm/tools/llvm-profgen/ProfileGenerator.cpp

62–63

How about merge the new switch with this one?

[wenlei]

llvm/tools/llvm-profgen/ProfileGenerator.cpp

62–63

Yeah, let's merge them. And this may also mean we need to put it on afdo-specific path, instead having it in ProfileGenerator::postProcessProfiles.

[wlei]

merge TrimColdProfile and CSProfTrimColdContext

[hoy]

lgtm, thanks.

llvm/test/tools/llvm-profgen/merge-cold-profile.test

9

nit: this should not change?

[wlei]

Updating D113785: [llvm-profgen] Trim cold function profiles for non-CS AutoFDO

[wenlei]

None of the tests cover trim vs no-trim difference, it'd be good to have one, so we check trimming is actually making a difference.

[wenlei]

lgtm with a comment on test.

[wlei]

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

107

None of the tests cover trim vs no-trim difference, it'd be good to have one, so we check trimming is actually making a difference.

@wenlei We do have a test case for the trimming here which checked the function won't appear if its total sample is smaller than --profile-summary-cold-count=100

[wenlei]

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

107

But we don't have a check to make sure main/quick_sort actually appears without trimming, right? If for whatever reason these two never appears even without trimming (--trim-cold-profile=0), this test could be doing nothing.

[wlei]

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

88

Here

107

Oh, I got your meaning. In the test above, there is a CHECK for main/quick_sort, but I realize it's mixed with other test and not visible. I will add a separate test case for cold trimming.Thanks for the clarification.

[wlei]

add a separated test case for trimming, added no trim case

[wenlei]

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

107

Thanks, looks good now.

llvm/test/tools/llvm-profgen/Inputs/cold-profile-trimming.raw.prof

+27
[phone]:10
[phone]d:31
[phone]:3
+40068b-4006a2:30
+4006b0-4006b7:3
+4006b0-4006bf:60
+4006b0-4006c8:6
+4006d0-4006ea:51
+4006d0-400700:4
+4006ec-400700:30
[phone]f:5
[phone]:3
[phone]b:9
[phone]e:14
[phone]:3
[phone]b:43
[phone]e:11
[phone]b:4
[phone]:6
[phone]:12
[phone]a6:12
+4007a8-4007b8:11
+4007bd-4007ca:12
+4007cf-4007d7:12
+4007d7-4007d7:12
[phone]:12
[phone]bf:10
+26
+40066d->400686:3
+400675->400682:1
+400689->4006b9:4
+4006a2->4007a8:6
+4006b7->40068b:3
+4006bf->4006d0:9
+4006c8->4006b0:7
+4006ca->4006ec:3
+4006ea->4006b0:5
+400700->4006b0:7
+40072f->400755:5
+400753->400770:6
+40075b->400743:58
+40075f->400740:2
+40076e->400740:25
+400788->4007a8:6
+400792->4007d7:12
+4007a6->400650:7
+4007a6->400710:5
+4007b8->400790:12
+4007ca->400790:12
+4007d7->4007bd:12
+4007d7->4007cf:13
+40082f->400790:1
+400870->400540:12
+4008bf->400870:15

llvm/test/tools/llvm-profgen/cold-profile-trimming.test

+; RUN: llvm-profgen --format=text --unsymbolized-profile=%S/Inputs/cold-profile-trimming.raw.prof --binary=%S/Inputs/inline-noprobe2.perfbin --output=%t1 --use-offset=0 --trim-cold-profile=0
+; RUN: FileCheck %s --input-file %t1 --check-prefix=CHECK-NOTRIM
+; RUN: llvm-profgen --format=text --unsymbolized-profile=%S/Inputs/cold-profile-trimming.raw.prof --binary=%S/Inputs/inline-noprobe2.perfbin --output=%t1 --use-offset=0 --trim-cold-profile=1 --profile-summary-cold-count=100
+; RUN: FileCheck %s --input-file %t1 --check-prefix=CHECK-TRIM
+
+;CHECK-NOTRIM: partition_pivot_last:1091:7
+;CHECK-NOTRIM: partition_pivot_first:365:5
+;CHECK-NOTRIM: quick_sort:83:25
+;CHECK-NOTRIM: main:52:0
+
+;CHECK-TRIM: partition_pivot_last:1091:7
+;CHECK-TRIM: partition_pivot_first:365:5
+;CHECK-TRIM-NOT: quick_sort:83:25
+;CHECK-TRIM-NOT: main:52:0
+
+; original code:
+; clang -O3 -g -fno-optimize-sibling-calls -fdebug-info-for-profiling qsort.c -o a.out
+#include <stdio.h>
+#include <stdlib.h>
+
+void swap(int *a, int *b) {
+  int t = *a;
+  *a = *b;
+  *b = t;
+}
+
+int partition_pivot_last(int* array, int low, int high) {
+  int pivot = array[high];
+  int i = low - 1;
+  for (int j = low; j < high; j++)
+    if (array[j] < pivot)
+      swap(&array[++i], &array[j]);
+  swap(&array[i + 1], &array[high]);
+  return (i + 1);
+}
+
+int partition_pivot_first(int* array, int low, int high) {
+  int pivot = array[low];
+  int i = low + 1;
+  for (int j = low + 1; j <= high; j++)
+    if (array[j] < pivot) { if (j != i) swap(&array[i], &array[j]); i++;}
+  swap(&array[i - 1], &array[low]);
+  return i - 1;
+}
+
+void quick_sort(int* array, int low, int high, int (*partition_func)(int *, int, int)) {
+  if (low < high) {
+    int pi = (*partition_func)(array, low, high);
+    quick_sort(array, low, pi - 1, partition_func);
+    quick_sort(array, pi + 1, high, partition_func);
+  }
+}
+
+int main() {
+  const int size = 200;
+  int sum = 0;
+  int *array = malloc(size * sizeof(int));
+  for(int i = 0; i < 100 * 1000; i++) {
+    for(int j = 0; j < size; j++)
+      array[j] = j % 10 ? rand() % size: j;
+    int (*fptr)(int *, int, int) = i % 3 ? partition_pivot_last : partition_pivot_first;
+    quick_sort(array, 0, size - 1, fptr);
+    sum += array[i % size];
+  }
+  printf("sum=%d\n", sum);
+
+  return 0;
+}

llvm/test/tools/llvm-profgen/cs-preinline.test

 ; Test default llvm-profgen with preinline off
 ; RUN: llvm-profgen --format=text --perfscript=%S/Inputs/inline-cs-noprobe.perfscript --binary=%S/Inputs/inline-cs-noprobe.perfbin --output=%t
 ; RUN: FileCheck %s --input-file %t --check-prefix=CHECK-DEFAULT
 
 ; Test llvm-profgen with preinliner on will merge not inlinable profile into base profile.
 ; RUN: llvm-profgen --format=text --perfscript=%S/Inputs/inline-cs-noprobe.perfscript --binary=%S/Inputs/inline-cs-noprobe.perfbin --output=%t --csspgo-preinliner=1
 ; RUN: FileCheck %s --input-file %t --check-prefix=CHECK-PREINL
 
 ; Test preinliner threshold that prevents all possible inlining and merges everything into base profile.
 ; RUN: llvm-profgen --format=text --perfscript=%S/Inputs/inline-cs-noprobe.perfscript --binary=%S/Inputs/inline-cs-noprobe.perfbin --output=%t --csspgo-preinliner=1  -sample-profile-cold-inline-threshold=0
 ; RUN: FileCheck %s --input-file %t --check-prefix=CHECK-NO-PREINL
 
 ; Test cold profile trimming. Only base profiles should be dropped.
-; RUN: llvm-profgen --format=text --perfscript=%S/Inputs/inline-cs-noprobe.perfscript --binary=%S/Inputs/inline-cs-noprobe.perfbin --output=%t --csspgo-preinliner=1  --csprof-trim-cold-context=1 --profile-summary-hot-count=250
+; RUN: llvm-profgen --format=text --perfscript=%S/Inputs/inline-cs-noprobe.perfscript --binary=%S/Inputs/inline-cs-noprobe.perfbin --output=%t --csspgo-preinliner=1  --trim-cold-profile=1 --profile-summary-hot-count=250
 
 ; RUN: FileCheck %s --input-file %t --check-prefix=CHECK-TRIM
 
 ; CHECK-DEFAULT:     [main:1 @ foo]:44:0
 ; CHECK-DEFAULT-NEXT: 2.1: 14
 ; CHECK-DEFAULT-NEXT: 3: 15
 ; CHECK-DEFAULT-NEXT: 3.1: 14 bar:14
 ; CHECK-DEFAULT-NEXT: 3.2: 1

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

 ; RUN: llvm-profgen --format=text --perfscript=%S/Inputs/artificial-branch.perfscript --binary=%S/Inputs/inline-noprobe2.perfbin --output=%t  --skip-symbolization --use-offset=0
 ; RUN: FileCheck %s --input-file %t --check-prefix=CHECK-ARTIFICIAL-BRANCH
 ; RUN: llvm-profgen --format=text --perfscript=%S/Inputs/inline-noprobe2.perfscript --binary=%S/Inputs/inline-noprobe2.perfbin --output=%t  --skip-symbolization --use-offset=0
 ; RUN: FileCheck %s --input-file %t --check-prefix=CHECK-RAW-PROFILE
 ; RUN: llvm-profgen --format=text --unsymbolized-profile=%t --binary=%S/Inputs/inline-noprobe2.perfbin --output=%t1 --use-offset=0
 ; RUN: FileCheck %s --input-file %t1 --check-prefix=CHECK
 
+; RUN: llvm-profgen --format=text --unsymbolized-profile=%t --binary=%S/Inputs/inline-noprobe2.perfbin --output=%t1 --use-offset=0 --trim-cold-profile --profile-summary-cold-count=100
+; RUN: FileCheck %s --input-file %t1 --check-prefix=CHECK-TRIM-COLD
+
 ; RUN: llvm-profgen --format=extbinary --perfscript=%S/Inputs/inline-noprobe2.perfscript --binary=%S/Inputs/inline-noprobe2.perfbin --output=%t --populate-profile-symbol-list=1
 ; RUN: llvm-profdata show -show-prof-sym-list -sample %t | FileCheck %s --check-prefix=CHECK-SYM-LIST
 
 ; CHECK-ARTIFICIAL-BRANCH: 3
 ; CHECK-ARTIFICIAL-BRANCH: 400540-400540:1
 ; CHECK-ARTIFICIAL-BRANCH: 400870-400870:2
 ; CHECK-ARTIFICIAL-BRANCH: 400875-4008bf:1
 ; CHECK-ARTIFICIAL-BRANCH: 2

 ;CHECK-NEXT:   2: 5
 ;CHECK-NEXT:   3: 5
 ;CHECK-NEXT: quick_sort:83:25
 ;CHECK-NEXT:  1: 24
 ;CHECK-NEXT:  2: 12 partition_pivot_last:7 partition_pivot_first:5
 ;CHECK-NEXT:  3: 11 quick_sort:12
 ;CHECK-NEXT:  4: 12 quick_sort:12
 ;CHECK-NEXT:  6: 24
 ;CHECK-NEXT: main:52:0
 ;CHECK-NEXT:  0: 0
 ;CHECK-NEXT:  3: 0
 ;CHECK-NEXT:  4.1: 0
 ;CHECK-NEXT:  4.3: 0
 ;CHECK-NEXT:  5.1: 10
 ;CHECK-NEXT:  5.3: 10
 ;CHECK-NEXT:  6: 10
 ;CHECK-NEXT:  6.1: 12
 ;CHECK-NEXT:  6.3: 10
 ;CHECK-NEXT:  7: 0
 ;CHECK-NEXT:  8: 0 quick_sort:1
 ;CHECK-NEXT:  9: 0
 ;CHECK-NEXT:  11: 0
 ;CHECK-NEXT:  14: 0
 
+;CHECK-TRIM-COLD: partition_pivot_first:367:5
+;CHECK-TRIM-COLD: partition_pivot_last:225:7
+;CHECK-TRIM-COLD-NOT: quick_sort:83:25
+;CHECK-TRIM-COLD-NOT: main:52:0
+
 ; original code:
 ; clang -O3 -g -fno-optimize-sibling-calls -fdebug-info-for-profiling qsort.c -o a.out
 #include <stdio.h>
 #include <stdlib.h>
 
 void swap(int *a, int *b) {
   int t = *a;
   *a = *b;

llvm/test/tools/llvm-profgen/merge-cold-profile.test

 ; Used the data from recursion-compression.test, refer it for the unmerged output
 ; RUN: llvm-profgen --format=text --perfscript=%S/Inputs/recursion-compression-pseudoprobe.perfscript --binary=%S/Inputs/recursion-compression-pseudoprobe.perfbin --output=%t1 --compress-recursion=-1 --profile-summary-hot-count=8
 ; RUN: FileCheck %s --input-file %t1
 
-; Test --csprof-trim-cold-context=0
-; RUN: llvm-profgen --format=text --perfscript=%S/Inputs/recursion-compression-pseudoprobe.perfscript --binary=%S/Inputs/recursion-compression-pseudoprobe.perfbin --output=%t2 --compress-recursion=-1 --profile-summary-hot-count=100 --csprof-trim-cold-context=0
+; Test --trim-cold-profile=0
+; RUN: llvm-profgen --format=text --perfscript=%S/Inputs/recursion-compression-pseudoprobe.perfscript --binary=%S/Inputs/recursion-compression-pseudoprobe.perfbin --output=%t2 --compress-recursion=-1 --profile-summary-hot-count=100 --trim-cold-profile=0
 ; RUN: FileCheck %s --input-file %t2 --check-prefix=CHECK-KEEP-COLD
 
 ; Test --csprof-merge-cold-context=0
 ; RUN: llvm-profgen --format=text --perfscript=%S/Inputs/recursion-compression-pseudoprobe.perfscript --binary=%S/Inputs/recursion-compression-pseudoprobe.perfbin --output=%t3 --compress-recursion=-1 --profile-summary-hot-count=10 --csprof-merge-cold-context=0
 ; RUN: FileCheck %s --input-file %t3 --check-prefix=CHECK-UNMERGED
 
 ; Test --csprof-frame-depth-for-cold-context
-; RUN: llvm-profgen --format=text --perfscript=%S/Inputs/recursion-compression-pseudoprobe.perfscript --binary=%S/Inputs/recursion-compression-pseudoprobe.perfbin --output=%t2 --compress-recursion=-1 --profile-summary-hot-count=100 --csprof-trim-cold-context=0 --csprof-max-cold-context-depth=2
+; RUN: llvm-profgen --format=text --perfscript=%S/Inputs/recursion-compression-pseudoprobe.perfscript --binary=%S/Inputs/recursion-compression-pseudoprobe.perfbin --output=%t2 --compress-recursion=-1 --profile-summary-hot-count=100 --trim-cold-profile=0 --csprof-max-cold-context-depth=2
 ; RUN: FileCheck %s --input-file %t2 --check-prefix=CHECK-COLD-CONTEXT-LENGTH
 
 ; CHECK:     [fa]:14:4
 ; CHECK-NEXT: 1: 4
 ; CHECK-NEXT: 3: 4
 ; CHECK-NEXT: 4: 2
 ; CHECK-NEXT: 5: 1
 ; CHECK-NEXT: 6: 0

llvm/tools/llvm-profgen/ProfileGenerator.h

private:
   // inline stack and meanwhile it adds the total samples for each frame's
   // function profile.
   FunctionSamples &
   getLeafFrameProfile(const SampleContextFrameVector &FrameVec);
   void populateBodySamplesForAllFunctions(const RangeSample &RangeCounter);
   void
   populateBoundarySamplesForAllFunctions(const BranchSample &BranchCounters);
   void postProcessProfiles();
+  void trimColdProfiles(const SampleProfileMap &Profiles,
+                        uint64_t ColdCntThreshold);
 };
 
 using ProbeCounterMap =
     std::unordered_map<const MCDecodedPseudoProbe *, uint64_t>;
 
 class CSProfileGenerator : public ProfileGeneratorBase {
 public:
   CSProfileGenerator(ProfiledBinary *Binary,

llvm/tools/llvm-profgen/ProfileGenerator.cpp

 
 static cl::opt<int32_t, true> RecursionCompression(
     "compress-recursion",
     cl::desc("Compressing recursion by deduplicating adjacent frame "
              "sequences up to the specified size. -1 means no size limit."),
     cl::Hidden,
     cl::location(llvm::sampleprof::CSProfileGenerator::MaxCompressionSize));
 
+static cl::opt<bool>
+    TrimColdProfile("trim-cold-profile", cl::init(false), cl::ZeroOrMore,
+                    cl::desc("If the total count of the profile is smaller "
+                             "than threshold, it will be trimmed."));
+
 static cl::opt<bool> CSProfMergeColdContext(
     "csprof-merge-cold-context", cl::init(true), cl::ZeroOrMore,
     cl::desc("If the total count of context profile is smaller than "
              "the threshold, it will be merged into context-less base "
              "profile."));
 
-static cl::opt<bool> CSProfTrimColdContext(
-    "csprof-trim-cold-context", cl::init(false), cl::ZeroOrMore,
-    cl::desc("If the total count of the profile after all merge is done "
-             "is still smaller than threshold, it will be trimmed."));
-
 static cl::opt<uint32_t> CSProfMaxColdContextDepth(
     "csprof-max-cold-context-depth", cl::init(1), cl::ZeroOrMore,
     cl::desc("Keep the last K contexts while merging cold profile. 1 means the "
              "context-less base profile"));
 
 static cl::opt<int, true> CSProfMaxContextDepth(
     "csprof-max-context-depth", cl::ZeroOrMore,
     cl::desc("Keep the last K contexts while merging profile. -1 means no "
              "depth limit."),
void ProfileGenerator::generateProfile() {
   } else {
     generateLineNumBasedProfile();
   }
   postProcessProfiles();
 }
 
 void ProfileGenerator::postProcessProfiles() {
   computeSummaryAndThreshold();
+  trimColdProfiles(ProfileMap, ColdCountThreshold);
   calculateAndShowDensity(ProfileMap);
 }
 
+void ProfileGenerator::trimColdProfiles(const SampleProfileMap &Profiles,
+                                        uint64_t ColdCntThreshold) {
+  if (!TrimColdProfile)
+    return;
+
+  // Move cold profiles into a tmp container.
+  std::vector<SampleContext> ColdProfiles;
+  for (const auto &I : ProfileMap) {
+    if (I.second.getTotalSamples() < ColdCntThreshold)
+      ColdProfiles.emplace_back(I.first);
+  }
+
+  // Remove the cold profile from ProfileMap.
+  for (const auto &I : ColdProfiles)
+    ProfileMap.erase(I);
+}
+
 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);
if (EnableCSPreInliner) {
     CSPreInliner(ProfileMap, *Binary, HotCountThreshold, ColdCountThreshold)
         .run();
     // Turn off the profile merger by default unless it is explicitly enabled.
     if (!CSProfMergeColdContext.getNumOccurrences())
       CSProfMergeColdContext = false;
   }
 
   // Trim and merge cold context profile using cold threshold above.
-  if (CSProfTrimColdContext || CSProfMergeColdContext) {
+  if (TrimColdProfile || CSProfMergeColdContext) {
     SampleContextTrimmer(ProfileMap)
         .trimAndMergeColdContextProfiles(
-            HotCountThreshold, CSProfTrimColdContext, CSProfMergeColdContext,
+            HotCountThreshold, TrimColdProfile, CSProfMergeColdContext,
             CSProfMaxColdContextDepth, EnableCSPreInliner);
   }
 
   // Merge function samples of CS profile to calculate profile density.
   sampleprof::SampleProfileMap ContextLessProfiles;
   for (const auto &I : ProfileMap) {
     ContextLessProfiles[I.second.getName()].merge(I.second);
   }