[CSSPGO][llvm-profgen] Compress recursive cycles in calling context

[wlei]

Summary

This change compresses the context string by removing cycles due to recursive function for CS profile generation. Removing recursion cycles is a way to normalize the calling context which will be better for the sample aggregation and also make the context promoting deterministic.
Specifically for implementation, we recognize adjacent repeated frames as cycles and deduplicated them through multiple round of iteration.
For example:
Considering a input context string stack:
[“a”, “a”, “b”, “c”, “a”, “b”, “c”, “b”, “c”, “d”]
For first iteration,, it removed all adjacent repeated frames of size 1:
[“a”, “b”, “c”, “a”, “b”, “c”, “b”, “c”, “d”]
For second iteration, it removed all adjacent repeated frames of size 2:
[“a”, “b”, “c”, “a”, “b”, “c”, “d”]
So in the end, we get compressed output:
[“a”, “b”, “c”, “d”]

Compression will be called in two place: one for sample's context key right after unwinding, one is for the eventual context string id in the ProfileGenerator.
Added a switch compress-recursion to control the size of duplicated frames, default -1 means no size limit.
Added unit tests and regression test for this.

[wlei]

rebase

[wmi]

llvm/test/tools/llvm-profgen/recursion-compression.test

1 ↗

(On Diff #313134)

Could you show the result of --compress-recursion=0 (I assume no compression will happen) so it is easy to check which part of the output is compressed for --compress-recursion=-1?

llvm/tools/llvm-profgen/ProfileGenerator.cpp

450

Use SmallVectorImpl<std::string>& as a parameter type instead of SmallVector<std::string, 16>&. There are some other places with the same issue.

473

Use SmallVectorImpl<std::string>& as a parameter type instead of SmallVector<std::string, 16>&.

501

Nit: Change it to ContextStrStackCopy to make the vector copy more explicit.

llvm/tools/llvm-profgen/ProfileGenerator.h

94–95

Is p a variable or does it refer to some other variable?

106–108

Could you give an example of what the sequence looks like after the population?

llvm/unittests/tools/llvm-profgen/ContextCompressionTest.cpp

15

How about have a similar test for pseudo probe?

[wlei]

Addressing Wei's feedback

[wlei]

llvm/test/tools/llvm-profgen/recursion-compression.test

1 ↗

(On Diff #313134)

Good idea, added the uncompressed test case

llvm/tools/llvm-profgen/ProfileGenerator.cpp

450

Yeah, thanks for the suggestions, fixed all the issues.

501

Good catch, changed to use a new variable ContextStrStackCopy to make it more explicit.

llvm/tools/llvm-profgen/ProfileGenerator.h

94–95

Sorry, I just miss to update the comments. 'p' is actually the Left. fixed the comments.

106–108

Sure, an example is added in the code comments

llvm/unittests/tools/llvm-profgen/ContextCompressionTest.cpp

15

Do you mean to add compression test for the element whose type is PseudoProbe?
The pseudo probe in the context key is represented as a PseudoProbe pointer, i.e an integer, so it should be same as the string. The only thing for the type T is implementing the == operator.

[wmi]

llvm/tools/llvm-profgen/ProfileGenerator.h

106–108

Thanks for the example. I can understand where are the redundent comparisons but I havn't understood how to skip the windows by doing the population (std::copy). I don't see the std::copy change anything for the example below. Could you clarify?

Similarly I don't see how the duplicated str is removed from Context sequence when Duplication is found above (if (Right - Left == I) is true). Could you also clarify that?

llvm/unittests/tools/llvm-profgen/ContextCompressionTest.cpp

15

Ok, thanks for the clarification.

[wlei]

rewrote the comments, adding more examples

[wlei]

llvm/tools/llvm-profgen/ProfileGenerator.h

106–108

Yeah, our original design is to use a new vector to store the compressed result, then we changed to use in-place algorithm to reduce the memcpy which make readability worse.
rewrote the code comments, added another example, please see this version is clear or not?

[hoy]

llvm/tools/llvm-profgen/ProfileGenerator.h

61

Moving the implementation to ProfileGenerator.cpp so that RecursionCompression can be checked instead of using an extra global?

63

typo: sequence

[wmi]

llvm/tools/llvm-profgen/ProfileGenerator.h

106–108

Thanks, now I understand it better. However, I am surprised seems you doesn't remove the redundent comparison which I thought you tried to remove.

suppose you have the following sequence:
a b c d b c d

Considering I==3.
In the first iteration. abc and dbc are compared, so Left==0 and Right==2, The algorithm find the first non-common place is Left==0. Then it updates Right to be Left + I = 3 at the end of the iteration. Note in this iteration, it have compared the common parts so it already knows the 2th/5th char in the string are the same --> 'b', and 3th/6th chars in the string are the same --> 'd'.

In the next iteration, the algorithm executes the comparison loop again:

uint32_t Left = Right;
while (Right - Left < I && Context[Left] == Context[Left + I]) {
   // Find the longest suffix inside the window. When stops, Left points
   // at the diverging point in the current sequence.
   Left--;
}

With Right==3, it will compare 3 chars before it can confirm there is duplication found, so it will compare 2th char and 5th char, 4th char and 6th char again which it already know they are the same in the first iteration.

Do I understand it correctly?

[wmi]

llvm/tools/llvm-profgen/ProfileGenerator.h

106–108

Sorry: some typos:

2th/5th char in the string are the same --> 'b', and 3th/6th chars in the string are the same --> 'd'.

'd' ==> 'c'

so it will compare 2th char and 5th char, 4th char and 6th char again which it already know they are the same in the first iteration.

4th char and 6th char again ==> 3th char and 6th char again

[wlei]

llvm/tools/llvm-profgen/ProfileGenerator.h

106–108

Yes, your'are right. I think we miss this, your case is another optimizing opportunity.

This code's redundancy removing is like below:

0 1 2 3 4 5 6 7 8
a b c a b d a b d
I = 3

For 1st iteration, abc and abd are compared, we know c and d is different. So Left is 2 and Right is 2. Then Right will be Left + I = 5. It means to avoid comparing [bca, bda] and [cab, dab] since we already know the comparison between c and d is false.

The 2nd iteration will just compare [abd, abd]

So let me implement it based on your idea, thanks for your feedback.

[hoy]

llvm/tools/llvm-profgen/ProfileGenerator.h

106–108

Yes, that's a missing opportunity. Once a common suffix is found, it will become the common prefix for the next compare. Then the next compare will not need to compare the common prefix again. The optimization was not done because it adds complexity and does not change the complexity, still O(n).

Thanks for pointing this out, Wei and thanks for giving it a shot Lei!

[wmi]

llvm/tools/llvm-profgen/ProfileGenerator.h

106–108

The optimization was not done because it adds complexity and does not change the complexity, still O(n).

Agree. I don't know how much cpu and memory overhead are spent on compression for large case. What is your experience on it? That will help to decide the tradeoff between optimization and complexity.

[hoy]

llvm/tools/llvm-profgen/ProfileGenerator.h

106–108

We haven't measured that. But I think this optimization is worse pursuing. We just need a variable to store the length of the last common suffix and stop the comparing when the rest of string to compare is right in that length.

[wlei]

llvm/tools/llvm-profgen/ProfileGenerator.h

106–108

Yeah, I think that shouldn't need too much work. Let me try it.

[wlei]

Remove more redundancy cases during deduplication

[wlei]

llvm/tools/llvm-profgen/ProfileGenerator.h

61

Yes, I tried this but failed because of the unit test which need to link the cpp file and the dependence need to include many other files. Not sure other ways to link the a Tool dir to the unit test, so I chose to put it into header file. what do you think?

63

fixed

106–108

Implemented, added a new variable LeftBoundary for the check and the Left pointer will end at it not the Right - I.

[hoy]

llvm/tools/llvm-profgen/ProfileGenerator.h

61

I see. Can CompressionSize be made a static field of the class and initialized in the cpp file?

Also, it sounds to me compressRecursionContext should be a function of CSProfileGenerator since it is CS-specific. What do you think?

106–108

looks good, thanks!

[wlei]

addressing Hongtao's feedback

[wlei]

llvm/tools/llvm-profgen/ProfileGenerator.h

61

Yes, good suggestions, thanks. made CompressionSize static and moved compressRecursionContext into CSProfileGenerator

[hoy]

llvm/tools/llvm-profgen/ProfileGenerator.h

20

Remove this?

221

Nit: add a comment about the special value -1?

[wlei]

addressing Hongtao's feedback

llvm/tools/llvm-profgen/ProfileGenerator.h

20

Good catch!

221

Good point!

[wenlei]

llvm/test/tools/llvm-profgen/recursion-compression.test

69 ↗

(On Diff #317725)

nit: missed a CHECK?

1 ↗

(On Diff #313134)

Would it be better to place the check for compressed form side by side with uncompressed form for readability?

[wenlei]

llvm/test/tools/llvm-profgen/recursion-compression.test

1 ↗

(On Diff #317725)

A test case to cover line-based profile too? That goes through slightly different path for handling the inline context expansion, so e2e test would be good (doesn't have to be as through as the one for probe though).

llvm/tools/llvm-profgen/ProfileGenerator.h

96

We could remove this redirector, and just use default parameter?

[wlei]

addressing Wenlei's feedback, added line-based test

[wlei]

llvm/test/tools/llvm-profgen/recursion-compression.test

1 ↗

(On Diff #317725)

Good catch, the line-based test added

69 ↗

(On Diff #317725)

Good catch!

1 ↗

(On Diff #313134)

Just tried but the problem here is the result is sorted by the total sample, if the order changed after compressed and merged, it couldn't properly match the line. So how about keep the current one or I can give some comments for readability?

llvm/tools/llvm-profgen/ProfileGenerator.h

96

Yeah, good to know this, we can use uint32_t CompressionSize = MaxCompressionSize as the default parameter.

[wenlei]

llvm/test/tools/llvm-profgen/recursion-compression.test

1 ↗

(On Diff #317725)

Test for --compress-recursion=0 is gone? and I don't see new test case here?

1 ↗

(On Diff #313134)

I see.. then we can leave it. thanks..

[wlei]

llvm/test/tools/llvm-profgen/recursion-compression.test

1 ↗

(On Diff #317725)

Oh, I guess you need to refer the latest commit. I removed this file, so the code here is outdated.

[wenlei]

lgtm, thanks!

llvm/test/tools/llvm-profgen/recursion-compression.test

1 ↗

(On Diff #317725)

Oops.. sorry i was indeed looking at the wrong version. thanks for adding test for line-based profile.

[wmi]

LGTM. Thanks.

llvm/test/tools/llvm-profgen/Inputs/recursion-compression-noprobe.perfscript

+PERF_RECORD_MMAP2 3019402/3019402: [0x400000(0x1000) @ 0 00:1d 265650677 1451231]: r-xp recursion-compression-noprobe.perfbin
+
+            4007e1
+ 0x4007d6/0x4007e1/P/-/-/0  0x4007c7/0x4007c0/P/-/-/0  0x4007c7/0x4007c0/P/-/-/0  0x4007c7/0x4007c0/P/-/-/0  0x4007c7/0x4007c0/P/-/-/0  0x4007c7/0x4007c0/P/-/-/0  0x4007c7/0x4007c0/P/-/-/0  0x4007c7/0x4007c0/P/-/-/0  0x4007c7/0x4007c0/P/-/-/0  0x4007c7/0x4007c0/P/-/-/0  0x4007c7/0x4007c0/P/-/-/0  0x400795/0x4007b0/P/-/-/0  0x40079c/0x400790/P/-/-/0  0x400801/0x400770/P/-/-/0  0x400698/0x400801/P/-/-/0  0x400673/0x400696/P/-/-/0

llvm/test/tools/llvm-profgen/Inputs/recursion-compression-pseudoprobe.perfscript

+PERF_RECORD_MMAP2 3367317/3367317: [0x201000(0x1000) @ 0 00:1d 238458915 1121070]: r-xp recursion-compression-pseudoprobe.perfbin
+
+            2017db
+            2017ba
+            2017e5
+            2017ba
+            2017e5
+            2017d9
+            2017ba
+            2017b0
+            2017b0
+            2017b0
+            2017b0
+            2017b0
+            2017b0
+            2017b0
+            2017b0
+            2017e5
+            2017d9
+            201847
+      7fcb072a67c3
+  5541f689495641d7
+ 0x2017cd/0x2017db/P/-/-/0  0x2017b5/0x2017c0/P/-/-/0  0x2017a7/0x2017b2/P/-/-/0  0x2017e0/0x2017a0/P/-/-/0  0x2017cd/0x2017db/P/-/-/0  0x2017b5/0x2017c0/P/-/-/0  0x2017a7/0x2017b2/P/-/-/0  0x2017e0/0x2017a0/P/-/-/0  0x2017cd/0x2017db/P/-/-/0  0x2017d4/0x2017c0/P/-/-/0  0x2017b5/0x2017c0/P/-/-/0  0x2017a7/0x2017b2/P/-/-/0  0x2017ab/0x2017a0/P/-/-/0  0x2017ab/0x2017a0/P/-/-/0  0x2017ab/0x2017a0/P/-/-/0  0x2017ab/0x2017a0/P/-/-/0

llvm/test/tools/llvm-profgen/recursion-compression-noprobe.test

+; Firstly test uncompression(--compress-recursion=0)
+; RUN: llvm-profgen --perfscript=%S/Inputs/recursion-compression-noprobe.perfscript --binary=%S/Inputs/recursion-compression-noprobe.perfbin --output=%t --compress-recursion=0
+; RUN: FileCheck %s --input-file %t -check-prefix=CHECK-UNCOMPRESS
+; RUN: llvm-profgen --perfscript=%S/Inputs/recursion-compression-noprobe.perfscript --binary=%S/Inputs/recursion-compression-noprobe.perfbin --output=%t
+; RUN: FileCheck %s --input-file %t
+
+; CHECK-UNCOMPRESS:[main:1 @ foo:3 @ fa]:14:0
+; CHECK-UNCOMPRESS: 1: 1
+; CHECK-UNCOMPRESS: 2: 13 fb:11
+; CHECK-UNCOMPRESS:[main:1 @ foo:3 @ fa:2 @ fb]:12:0
+; CHECK-UNCOMPRESS: 1: 11
+; CHECK-UNCOMPRESS: 2: 1 fa:1
+; CHECK-UNCOMPRESS:[main:1 @ foo:3 @ fa:2 @ fb:2 @ fa]:3:0
+; CHECK-UNCOMPRESS: 1: 1
+; CHECK-UNCOMPRESS: 2: 2 fb:1
+; CHECK-UNCOMPRESS:[main:1 @ foo]:3:0
+; CHECK-UNCOMPRESS: 2: 1
+; CHECK-UNCOMPRESS: 3: 2 fa:1
+; CHECK-UNCOMPRESS:[main:1 @ foo:3 @ fa:2 @ fb:2 @ fa:2 @ fb:2 @ fa]:1:0
+; CHECK-UNCOMPRESS: 4: 1
+; CHECK-UNCOMPRESS:[main:1 @ foo:3 @ fa:2 @ fb:2 @ fa:2 @ fb]:1:0
+; CHECK-UNCOMPRESS: 2: 1 fa:1
+
+; CHECK: [main:1 @ foo:3 @ fa]:14:0
+; CHECK:  1: 1
+; CHECK:  2: 13 fb:11
+; CHECK: [main:1 @ foo:3 @ fa:2 @ fb]:12:0
+; CHECK:  1: 11
+; CHECK:  2: 1 fa:1
+; CHECK: [main:1 @ foo:3 @ fa:2 @ fb:2 @ fa]:4:0
+; CHECK:  1: 1
+; CHECK:  2: 2 fb:1
+; CHECK:  4: 1
+; CHECK: [main:1 @ foo]:3:0
+; CHECK:  2: 1
+; CHECK:  3: 2 fa:1
+; CHECK: [main:1 @ foo:3 @ fa:2 @ fb:2 @ fa:2 @ fb]:0:0
+
+
+; original code:
+; clang -O3 -g test.c -o a.out
+#include <stdio.h>
+
+int fb(int n) {
+  if(n > 10) return fb(n / 2);
+  return fa(n - 1);
+}
+
+int fa(int n) {
+  if(n < 2) return n;
+  if(n % 2) return fb(n - 1);
+  return fa(n - 1);
+}
+
+void foo() {
+  int s, i = 0;
+  while (i++ < 10000)
+    s += fa(i);
+  printf("sum is %d\n", s);
+}
+
+int main() {
+  foo();
+  return 0;
+}

llvm/test/tools/llvm-profgen/recursion-compression-pseudoprobe.test

+; Firstly test uncompression(--compress-recursion=0)
+; RUN: llvm-profgen --perfscript=%S/Inputs/recursion-compression-pseudoprobe.perfscript --binary=%S/Inputs/recursion-compression-pseudoprobe.perfbin --output=%t --compress-recursion=0
+; RUN: FileCheck %s --input-file %t -check-prefix=CHECK-UNCOMPRESS
+; RUN: llvm-profgen --perfscript=%S/Inputs/recursion-compression-pseudoprobe.perfscript --binary=%S/Inputs/recursion-compression-pseudoprobe.perfbin --output=%t --show-unwinder-output | FileCheck %s --check-prefix=CHECK-UNWINDER
+; RUN: FileCheck %s --input-file %t
+
+; CHECK-UNCOMPRESS: [main:2 @ foo:5 @ fa:8 @ fa:7 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:6 @ fa:8 @ fa:7 @ fb:6 @ fa]:4:1
+; CHECK-UNCOMPRESS:  1: 1
+; CHECK-UNCOMPRESS:  3: 1
+; CHECK-UNCOMPRESS:  4: 1
+; CHECK-UNCOMPRESS:  7: 1 fb:1
+; CHECK-UNCOMPRESS:  !CFGChecksum: 120515930909
+; CHECK-UNCOMPRESS: [main:2 @ foo:5 @ fa:8 @ fa:7 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:6 @ fa:8 @ fa]:4:1
+; CHECK-UNCOMPRESS:  1: 1
+; CHECK-UNCOMPRESS:  3: 1
+; CHECK-UNCOMPRESS:  4: 1
+; CHECK-UNCOMPRESS:  7: 1 fb:1
+; CHECK-UNCOMPRESS:  !CFGChecksum: 120515930909
+; CHECK-UNCOMPRESS: [main:2 @ foo:5 @ fa:8 @ fa:7 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:6 @ fa]:4:1
+; CHECK-UNCOMPRESS:  1: 1
+; CHECK-UNCOMPRESS:  3: 1
+; CHECK-UNCOMPRESS:  5: 1
+; CHECK-UNCOMPRESS:  8: 1 fa:1
+; CHECK-UNCOMPRESS:  !CFGChecksum: 120515930909
+; CHECK-UNCOMPRESS: [main:2 @ foo:5 @ fa:8 @ fa:7 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:6 @ fa:8 @ fa:7 @ fb:6 @ fa:7 @ fb]:3:1
+; CHECK-UNCOMPRESS:  1: 1
+; CHECK-UNCOMPRESS:  3: 1
+; CHECK-UNCOMPRESS:  6: 1 fa:1
+; CHECK-UNCOMPRESS:  !CFGChecksum: 72617220756
+; CHECK-UNCOMPRESS: [main:2 @ foo:5 @ fa:8 @ fa:7 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:6 @ fa:8 @ fa:7 @ fb]:3:1
+; CHECK-UNCOMPRESS:  1: 1
+; CHECK-UNCOMPRESS:  3: 1
+; CHECK-UNCOMPRESS:  6: 1 fa:1
+; CHECK-UNCOMPRESS:  !CFGChecksum: 72617220756
+; CHECK-UNCOMPRESS: [main:2 @ foo:5 @ fa:8 @ fa:7 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb]:3:1
+; CHECK-UNCOMPRESS:  1: 1
+; CHECK-UNCOMPRESS:  3: 1
+; CHECK-UNCOMPRESS:  6: 1 fa:1
+; CHECK-UNCOMPRESS:  !CFGChecksum: 72617220756
+; CHECK-UNCOMPRESS: [main:2 @ foo:5 @ fa:8 @ fa:7 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb]:3:1
+; CHECK-UNCOMPRESS:  1: 1
+; CHECK-UNCOMPRESS:  2: 1
+; CHECK-UNCOMPRESS:  5: 1 fb:1
+; CHECK-UNCOMPRESS:  !CFGChecksum: 72617220756
+; CHECK-UNCOMPRESS: [main:2 @ foo:5 @ fa:8 @ fa:7 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb]:3:1
+; CHECK-UNCOMPRESS:  1: 1
+; CHECK-UNCOMPRESS:  2: 1
+; CHECK-UNCOMPRESS:  5: 1 fb:1
+; CHECK-UNCOMPRESS:  !CFGChecksum: 72617220756
+; CHECK-UNCOMPRESS: [main:2 @ foo:5 @ fa:8 @ fa:7 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb]:3:1
+; CHECK-UNCOMPRESS:  1: 1
+; CHECK-UNCOMPRESS:  2: 1
+; CHECK-UNCOMPRESS:  5: 1 fb:1
+; CHECK-UNCOMPRESS:  !CFGChecksum: 72617220756
+; CHECK-UNCOMPRESS: [main:2 @ foo:5 @ fa:8 @ fa:7 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb:6 @ fa:8 @ fa:7 @ fb:6 @ fa:7 @ fb:6 @ fa]:2:1
+; CHECK-UNCOMPRESS:  1: 1
+; CHECK-UNCOMPRESS:  3: 1
+; CHECK-UNCOMPRESS:  !CFGChecksum: 120515930909
+; CHECK-UNCOMPRESS: [main:2 @ foo:5 @ fa:8 @ fa:7 @ fb:5 @ fb:5 @ fb:5 @ fb:5 @ fb]:1:0
+; CHECK-UNCOMPRESS:  5: 1 fb:1
+; CHECK-UNCOMPRESS:  !CFGChecksum: 72617220756
+
+
+; CHECK: [main:2 @ foo:5 @ fa:8 @ fa:7 @ fb:5 @ fb]:13:4
+; CHECK:  1: 4
+; CHECK:  2: 3
+; CHECK:  3: 1
+; CEHCK:  5: 4 fb:4
+; CHECK:  6: 1 fa:1
+; CHECK !CFGChecksum: 72617220756
+; CHECK: [main:2 @ foo:5 @ fa:8 @ fa:7 @ fb:5 @ fb:6 @ fa:8 @ fa:7 @ fb:6 @ fa]:6:2
+; CHECK:  1: 2
+; CHECK:  3: 2
+; CHECK:  4: 1
+; CHECK:  7: 1 fb:1
+; CHECK:  !CFGChecksum: 120515930909
+; CHECK: [main:2 @ foo:5 @ fa:8 @ fa:7 @ fb:5 @ fb:6 @ fa:8 @ fa]:4:1
+; CHECK:  1: 1
+; CHECK:  3: 1
+; CHECK:  4: 1
+; CHECK:  7: 1 fb:1
+; CHECK:  !CFGChecksum: 120515930909
+; CHECK: [main:2 @ foo:5 @ fa:8 @ fa:7 @ fb:5 @ fb:6 @ fa]:4:1
+; CHECK:  1: 1
+; CHECK:  3: 1
+; CHECK:  5: 1
+; CHECK:  8: 1 fa:1
+; CHECK:  !CFGChecksum: 120515930909
+; CHECK: [main:2 @ foo:5 @ fa:8 @ fa:7 @ fb:5 @ fb:6 @ fa:8 @ fa:7 @ fb:6 @ fa:7 @ fb]:3:1
+; CHECK:  1: 1
+; CHECK:  3: 1
+; CHECK:  6: 1 fa:1
+; CHECK:  !CFGChecksum: 72617220756
+; CHECK: [main:2 @ foo:5 @ fa:8 @ fa:7 @ fb:5 @ fb:6 @ fa:8 @ fa:7 @ fb]:3:1
+; CHECK:  1: 1
+; CHECK:  3: 1
+; CHECK:  6: 1 fa:1
+; CHECK:  !CFGChecksum: 72617220756
+
+
+; CHECK-UNWINDER: Binary(recursion-compression-pseudoprobe.perfbin)'s Range Counter:
+; CHECK-UNWINDER: main:2 @ foo:5 @ fa:8 @ fa:7 @ fb:5
+; CHECK-UNWINDER:   (7a0, 7a7): 1
+; CHECK-UNWINDER:   (7a0, 7ab): 3
+; CHECK-UNWINDER:   (7b2, 7b5): 1
+; CHECK-UNWINDER: main:2 @ foo:5 @ fa:8 @ fa:7 @ fb:5 @ fb:6
+; CHECK-UNWINDER:   (7c0, 7d4): 1
+; CHECK-UNWINDER: main:2 @ foo:5 @ fa:8 @ fa:7 @ fb:5 @ fb:6 @ fa:8
+; CHECK-UNWINDER:   (7c0, 7cd): 1
+; CHECK-UNWINDER:   (7db, 7e0): 1
+; CHECK-UNWINDER: main:2 @ foo:5 @ fa:8 @ fa:7 @ fb:5 @ fb:6 @ fa:8 @ fa:7
+; CHECK-UNWINDER:   (7a0, 7a7): 1
+; CHECK-UNWINDER:   (7b2, 7b5): 1
+; CHECK-UNWINDER: main:2 @ foo:5 @ fa:8 @ fa:7 @ fb:5 @ fb:6 @ fa:8 @ fa:7 @ fb:6
+; CHECK-UNWINDER:   (7c0, 7cd): 2
+; CHECK-UNWINDER:   (7db, 7e0): 1
+; CHECK-UNWINDER: main:2 @ foo:5 @ fa:8 @ fa:7 @ fb:5 @ fb:6 @ fa:8 @ fa:7 @ fb:6 @ fa:7
+; CHECK-UNWINDER:   (7a0, 7a7): 1
+; CHECK-UNWINDER:   (7b2, 7b5): 1
+
+; CHECK-UNWINDER: Binary(recursion-compression-pseudoprobe.perfbin)'s Branch Counter:
+; CHECK-UNWINDER: main:2 @ foo:5 @ fa:8 @ fa:7 @ fb:5
+; CHECK-UNWINDER:   (7a7, 7b2): 1
+; CHECK-UNWINDER:   (7ab, 7a0): 4
+; CHECK-UNWINDER:   (7b5, 7c0): 1
+; CHECK-UNWINDER: main:2 @ foo:5 @ fa:8 @ fa:7 @ fb:5 @ fb:6
+; CHECK-UNWINDER:   (7d4, 7c0): 1
+; CHECK-UNWINDER: main:2 @ foo:5 @ fa:8 @ fa:7 @ fb:5 @ fb:6 @ fa:8
+; CHECK-UNWINDER:   (7cd, 7db): 1
+; CHECK-UNWINDER:   (7e0, 7a0): 1
+; CHECK-UNWINDER: main:2 @ foo:5 @ fa:8 @ fa:7 @ fb:5 @ fb:6 @ fa:8 @ fa:7
+; CHECK-UNWINDER:   (7a7, 7b2): 1
+; CHECK-UNWINDER:   (7b5, 7c0): 1
+; CHECK-UNWINDER: main:2 @ foo:5 @ fa:8 @ fa:7 @ fb:5 @ fb:6 @ fa:8 @ fa:7 @ fb:6
+; CHECK-UNWINDER:   (7cd, 7db): 2
+; CHECK-UNWINDER:   (7e0, 7a0): 1
+; CHECK-UNWINDER: main:2 @ foo:5 @ fa:8 @ fa:7 @ fb:5 @ fb:6 @ fa:8 @ fa:7 @ fb:6 @ fa:7
+; CHECK-UNWINDER:   (7a7, 7b2): 1
+; CHECK-UNWINDER:   (7b5, 7c0): 1
+
+
+; clang -O3 -fexperimental-new-pass-manager -fuse-ld=lld -fpseudo-probe-for-profiling
+; -fno-omit-frame-pointer -mno-omit-leaf-frame-pointer -Xclang -mdisable-tail-calls
+; -g test.c  -o a.out
+
+#include <stdio.h>
+
+int fb(int n) {
+  if(n > 10) return fb(n / 2);
+  return fa(n - 1);
+}
+
+int fa(int n) {
+  if(n < 2) return n;
+  if(n % 2) return fb(n - 1);
+  return fa(n - 1);
+}
+
+void foo() {
+  int s, i = 0;
+  while (i++ < 10000)
+    s += fa(i);
+  printf("sum is %d\n", s);
+}
+
+int main() {
+  foo();
+  return 0;
+}

llvm/tools/llvm-profgen/PerfReader.cpp

 //===-- PerfReader.cpp - perfscript reader  ---------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 #include "PerfReader.h"
+#include "ProfileGenerator.h"
 
 static cl::opt<bool> ShowMmapEvents("show-mmap-events", cl::ReallyHidden,
                                     cl::init(false), cl::ZeroOrMore,
                                     cl::desc("Print binary load events."));
 
 static cl::opt<bool> ShowUnwinderOutput("show-unwinder-output",
                                         cl::ReallyHidden, cl::init(false),
                                         cl::ZeroOrMore,
for (; Iter != EndT; Iter++) {
       // Callsite merging may cause the loss of original probe IDs.
       // Cutting off the context from here since the inline will
       // not know how to consume a context with unknown callsites.
       if (!CallProbe)
         break;
       ProbeBasedKey->Probes.emplace_back(CallProbe);
     }
   }
+  CSProfileGenerator::compressRecursionContext<const PseudoProbe *>(
+      ProbeBasedKey->Probes);
   ProbeBasedKey->genHashCode();
   Hashable<ContextKey> ContextId(ProbeBasedKey);
   auto Ret = CtxCounterMap->emplace(ContextId, SampleCounter());
   return Ret.first->second;
 }
 
 void VirtualUnwinder::recordRangeCount(uint64_t Start, uint64_t End,
                                        UnwindState &State, uint64_t Repeat) {

llvm/tools/llvm-profgen/ProfileGenerator.h

 #include "PerfReader.h"
 #include "ProfiledBinary.h"
 #include "llvm/ProfileData/SampleProfWriter.h"
 
 using namespace llvm;
 using namespace sampleprof;
 
 namespace llvm {
 namespace sampleprof {
 
 class ProfileGenerator {
 
 public:
   ProfileGenerator(){};
   virtual ~ProfileGenerator() = default;
   static std::unique_ptr<ProfileGenerator>
   create(const BinarySampleCounterMap &BinarySampleCounters,
protected:
   |<--100-->|
   |<------200------>|
   A         B       C
 
   sample count for disjoint region [A,B] would be 300.
   */
   void findDisjointRanges(RangeSample &DisjointRanges,
                           const RangeSample &Ranges);
+
   // Used by SampleProfileWriter
   StringMap<FunctionSamples> ProfileMap;
 };
 
 class CSProfileGenerator : public ProfileGenerator {
 protected:
   const BinarySampleCounterMap &BinarySampleCounters;
 
 public:
   CSProfileGenerator(const BinarySampleCounterMap &Counters)
       : BinarySampleCounters(Counters){};
 
 public:
   void generateProfile() override {
     // Enable context-sensitive functionalities in SampleProf
     FunctionSamples::ProfileIsCS = true;
     for (const auto &BI : BinarySampleCounters) {
       ProfiledBinary *Binary = BI.first;
for (const auto &BI : BinarySampleCounters) {
       }
     }
     // 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();
   }
 
+  // Remove adjacent repeated context sequences up to a given sequence length,
+  // -1 means no size limit. Note that repeated sequences are identified based
+  // on the exact call site, this is finer granularity than function recursion.
+  template <typename T>
+  static void compressRecursionContext(SmallVectorImpl<T> &Context,
+                                       int32_t CSize = MaxCompressionSize) {
+    uint32_t I = 1;
+    uint32_t HS = static_cast<uint32_t>(Context.size() / 2);
+    uint32_t MaxDedupSize =
+        CSize == -1 ? HS : std::min(static_cast<uint32_t>(CSize), HS);
+    auto BeginIter = Context.begin();
+    // Use an in-place algorithm to save memory copy
+    // End indicates the end location of current iteration's data
+    uint32_t End = 0;
+    // Deduplicate from length 1 to the max possible size of a repeated
+    // sequence.
+    while (I <= MaxDedupSize) {
+      // This is a linear algorithm that deduplicates adjacent repeated
+      // sequences of size I. The deduplication detection runs on a sliding
+      // window whose size is 2*I and it keeps sliding the window to deduplicate
+      // the data inside. Once duplication is detected, deduplicate it by
+      // skipping the right half part of the window, otherwise just copy back
+      // the new one by appending them at the back of End pointer(for the next
+      // iteration).
+      //
+      // For example:
+      // Input: [a1, a2, b1, b2]
+      // (Added index to distinguish the same char, the origin is [a, a, b,
+      // b], the size of the dedup window is 2(I = 1) at the beginning)
+      //
+      // 1) The initial status is a dummy window[null, a1], then just copy the
+      // right half of the window(End = 0), then slide the window.
+      // Result: [a1], a2, b1, b2 (End points to the element right before ],
+      // after ] is the data of the previous iteration)
+      //
+      // 2) Next window is [a1, a2]. Since a1 == a2, then skip the right half of
+      // the window i.e the duplication happen. Only slide the window.
+      // Result: [a1], a2, b1, b2
+      //
+      // 3) Next window is [a2, b1], copy the right half of the window(b1 is
+      // new) to the End and slide the window.
+      // Result: [a1, b1], b1, b2
+      //
+      // 4) Next window is [b1, b2], same to 2), skip b2.
+      // Result: [a1, b1], b1, b2
+      // After resize, it will be [a, b]
+
+      // Use pointers like below to do comparison inside the window
+      //    [a         b         c        a       b        c]
+      //     |         |         |                |        |
+      // LeftBoundary Left     Right           Left+I    Right+I
+      // A duplication found if Left < LeftBoundry.
+
+      int32_t Right = I - 1;
+      End = I;
+      int32_t LeftBoundary = 0;
+      while (Right + I < Context.size()) {
+        // To avoids scanning a part of a sequence repeatedly, it finds out
+        // the common suffix of two hald in the window. The common suffix will
+        // serve as the common prefix of next possible pair of duplicate
+        // sequences. The non-common part will be ignored and never scanned
+        // again.
+
+        // For example.
+        // Input: [a, b1], c1, b2, c2
+        // I = 2
+        //
+        // 1) For the window [a, b1, c1, b2], non-common-suffix for the right
+        // part is 'c1', copy it and only slide the window 1 step.
+        // Result: [a, b1, c1], b2, c2
+        //
+        // 2) Next window is [b1, c1, b2, c2], so duplication happen.
+        // Result after resize: [a, b, c]
+
+        int32_t Left = Right;
+        while (Left >= LeftBoundary && Context[Left] == Context[Left + I]) {
+          // Find the longest suffix inside the window. When stops, Left points
+          // at the diverging point in the current sequence.
+          Left--;
+        }
+
+        bool DuplicationFound = (Left < LeftBoundary);
+        // Don't need to recheck the data before Right
+        LeftBoundary = Right + 1;
+        if (DuplicationFound) {
+          // Duplication found, skip right half of the window.
+          Right += I;
+        } else {
+          // Copy the non-common-suffix part of the adjacent sequence.
+          std::copy(BeginIter + Right + 1, BeginIter + Left + I + 1,
+                    BeginIter + End);
+          End += Left + I - Right;
+          // Only slide the window by the size of non-common-suffix
+          Right = Left + I;
+        }
+      }
+      // Don't forget the remaining part that's not scanned.
+      std::copy(BeginIter + Right + 1, Context.end(), BeginIter + End);
+      End += Context.size() - Right - 1;
+      I++;
+      Context.resize(End);
+    }
+  }
+
 protected:
   // Lookup or create FunctionSamples for the context
   FunctionSamples &getFunctionProfileForContext(StringRef ContextId);
 
 private:
   // Helper function for updating body sample for a leaf location in
   // FunctionProfile
   void updateBodySamplesforFunctionProfile(FunctionSamples &FunctionProfile,
                                            const FrameLocation &LeafLoc,
                                            uint64_t Count);
   void populateFunctionBodySamples(FunctionSamples &FunctionProfile,
                                    const RangeSample &RangeCounters,
                                    ProfiledBinary *Binary);
   void populateFunctionBoundarySamples(StringRef ContextId,
                                        FunctionSamples &FunctionProfile,
                                        const BranchSample &BranchCounters,
                                        ProfiledBinary *Binary);
   void populateInferredFunctionSamples();
+
+public:
+  // Deduplicate adjacent repeated context sequences up to a given sequence
+  // length. -1 means no size limit.
+  static int32_t MaxCompressionSize;
 };
 
 using ProbeCounterMap = std::unordered_map<const PseudoProbe *, uint64_t>;
 
 class PseudoProbeCSProfileGenerator : public CSProfileGenerator {
 
 public:
   PseudoProbeCSProfileGenerator(const BinarySampleCounterMap &Counters)
       : CSProfileGenerator(Counters) {}
   void generateProfile() override;
 
 private:
   // Go through each address from range to extract the top frame probe by
   // looking up in the Address2ProbeMap
   void extractProbesFromRange(const RangeSample &RangeCounter,
                               ProbeCounterMap &ProbeCounter,
                               ProfiledBinary *Binary);
   // Fill in function body samples from probes
-  void populateBodySamplesWithProbes(const RangeSample &RangeCounter,
-                                     StringRef PrefixContextId,
-                                     ProfiledBinary *Binary);
+  void
+  populateBodySamplesWithProbes(const RangeSample &RangeCounter,
+                                SmallVectorImpl<std::string> &ContextStrStack,
   // Fill in boundary samples for a call probe
-  void populateBoundarySamplesWithProbes(const BranchSample &BranchCounter,
-                                         StringRef PrefixContextId,
-                                         ProfiledBinary *Binary);
+  void populateBoundarySamplesWithProbes(
+      const BranchSample &BranchCounter,
+      SmallVectorImpl<std::string> &ContextStrStack, ProfiledBinary *Binary);
   // Helper function to get FunctionSamples for the leaf inlined context
-  FunctionSamples &getFunctionProfileForLeafProbe(
-      StringRef PrefixContextId,
-      SmallVector<std::string, 16> &LeafInlinedContext,
+  FunctionSamples &
+  getFunctionProfileForLeafProbe(SmallVectorImpl<std::string> &ContextStrStack,
                                  const PseudoProbeFuncDesc *LeafFuncDesc);
   // Helper function to get FunctionSamples for the leaf probe
-  FunctionSamples &getFunctionProfileForLeafProbe(StringRef PrefixContextId,
-                                                  const PseudoProbe *LeafProbe,
-                                                  ProfiledBinary *Binary);
+  FunctionSamples &
+  getFunctionProfileForLeafProbe(SmallVectorImpl<std::string> &ContextStrStack,
 };
 
 } // end namespace sampleprof
 } // end namespace llvm
 
 #endif

llvm/tools/llvm-profgen/ProfileGenerator.cpp

static cl::opt<SampleProfileFormat> OutputFormat(
     cl::values(
         clEnumValN(SPF_Binary, "binary", "Binary encoding (default)"),
         clEnumValN(SPF_Compact_Binary, "compbinary", "Compact binary encoding"),
         clEnumValN(SPF_Ext_Binary, "extbinary", "Extensible binary encoding"),
         clEnumValN(SPF_Text, "text", "Text encoding"),
         clEnumValN(SPF_GCC, "gcc",
                    "GCC encoding (only meaningful for -sample)")));
 
+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));
+
 using namespace llvm;
 using namespace sampleprof;
 
 namespace llvm {
 namespace sampleprof {
 
+// Initialize the MaxCompressionSize to -1 which means no size limit
+int32_t CSProfileGenerator::MaxCompressionSize = -1;
+
 static bool
 usePseudoProbes(const BinarySampleCounterMap &BinarySampleCounters) {
   return BinarySampleCounters.size() &&
          BinarySampleCounters.begin()->first->usePseudoProbes();
 }
 
 std::unique_ptr<ProfileGenerator>
 ProfileGenerator::create(const BinarySampleCounterMap &BinarySampleCounters,
CallerProfile.addCalledTargetSamples(
         EstimatedCallCount);
     CallerProfile.addBodySamples(CallerLeafFrameLoc.second.LineOffset,
                                  CallerLeafFrameLoc.second.Discriminator,
                                  EstimatedCallCount);
     CallerProfile.addTotalSamples(EstimatedCallCount);
   }
 }
 
-// Helper function to extract context prefix
-// PrefixContextId is the context id string except for the leaf probe's
-// context, the final ContextId will be:
-// ContextId =  PrefixContextId + LeafContextId;
-// Remind that the string in ContextStrStack is in callee-caller order
-// So process the string vector reversely
-static std::string
-extractPrefixContextId(const SmallVector<const PseudoProbe *, 16> &Probes,
+// Helper function to extract context prefix string stack
+// Extract context stack for reusing, leaf context stack will
+// be added compressed while looking up function profile
+static void
+extractPrefixContextStack(SmallVectorImpl<std::string> &ContextStrStack,
+                          const SmallVectorImpl<const PseudoProbe *> &Probes,
                           ProfiledBinary *Binary) {
-  SmallVector<std::string, 16> ContextStrStack;
   for (const auto *P : Probes) {
     Binary->getInlineContextForProbe(P, ContextStrStack, true);
   }
-  std::ostringstream OContextStr;
-  for (auto &CxtStr : ContextStrStack) {
-    if (OContextStr.str().size())
-      OContextStr << " @ ";
-    OContextStr << CxtStr;
-  }
-  return OContextStr.str();
 }
 
 void PseudoProbeCSProfileGenerator::generateProfile() {
   // Enable CS and pseudo probe functionalities in SampleProf
   FunctionSamples::ProfileIsCS = true;
   FunctionSamples::ProfileIsProbeBased = true;
   for (const auto &BI : BinarySampleCounters) {
     ProfiledBinary *Binary = BI.first;
     for (const auto &CI : BI.second) {
       const ProbeBasedCtxKey *CtxKey =
           dyn_cast<ProbeBasedCtxKey>(CI.first.getPtr());
-      std::string PrefixContextId =
-          extractPrefixContextId(CtxKey->Probes, Binary);
+      SmallVector<std::string, 16> ContextStrStack;
+      extractPrefixContextStack(ContextStrStack, CtxKey->Probes, Binary);
       // Fill in function body samples from probes, also infer caller's samples
       // from callee's probe
-      populateBodySamplesWithProbes(CI.second.RangeCounter, PrefixContextId,
+      populateBodySamplesWithProbes(CI.second.RangeCounter, ContextStrStack,
                                     Binary);
       // Fill in boundary samples for a call probe
       populateBoundarySamplesWithProbes(CI.second.BranchCounter,
-                                        PrefixContextId, Binary);
+                                        ContextStrStack, Binary);
     }
   }
 }
 
 void PseudoProbeCSProfileGenerator::extractProbesFromRange(
     const RangeSample &RangeCounter, ProbeCounterMap &ProbeCounter,
     ProfiledBinary *Binary) {
   RangeSample Ranges;
while (IP.Address <= RangeEnd) {
       }
 
       IP.advance();
     }
   }
 }
 
 void PseudoProbeCSProfileGenerator::populateBodySamplesWithProbes(
-    const RangeSample &RangeCounter, StringRef PrefixContextId,
-    ProfiledBinary *Binary) {
+    const RangeSample &RangeCounter,
+    SmallVectorImpl<std::string> &ContextStrStack, ProfiledBinary *Binary) {
   ProbeCounterMap ProbeCounter;
   // Extract the top frame probes by looking up each address among the range in
   // the Address2ProbeMap
   extractProbesFromRange(RangeCounter, ProbeCounter, Binary);
   for (auto PI : ProbeCounter) {
     const PseudoProbe *Probe = PI.first;
     uint64_t Count = PI.second;
     FunctionSamples &FunctionProfile =
-        getFunctionProfileForLeafProbe(PrefixContextId, Probe, Binary);
+        getFunctionProfileForLeafProbe(ContextStrStack, Probe, Binary);
 
     FunctionProfile.addBodySamples(Probe->Index, 0, Count);
     FunctionProfile.addTotalSamples(Count);
     if (Probe->isEntry()) {
       FunctionProfile.addHeadSamples(Count);
       // Look up for the caller's function profile
       const auto *InlinerDesc = Binary->getInlinerDescForProbe(Probe);
       if (InlinerDesc != nullptr) {
if (Probe->isEntry()) {
         CallerProfile.addCalledTargetSamples(CallerIndex, 0,
                                              FunctionProfile.getName(), Count);
       }
     }
   }
 }
 
 void PseudoProbeCSProfileGenerator::populateBoundarySamplesWithProbes(
-    const BranchSample &BranchCounter, StringRef PrefixContextId,
-    ProfiledBinary *Binary) {
+    const BranchSample &BranchCounter,
+    SmallVectorImpl<std::string> &ContextStrStack, ProfiledBinary *Binary) {
   for (auto BI : BranchCounter) {
     uint64_t SourceOffset = BI.first.first;
     uint64_t TargetOffset = BI.first.second;
     uint64_t Count = BI.second;
     uint64_t SourceAddress = Binary->offsetToVirtualAddr(SourceOffset);
     const PseudoProbe *CallProbe = Binary->getCallProbeForAddr(SourceAddress);
     if (CallProbe == nullptr)
       continue;
     FunctionSamples &FunctionProfile =
-        getFunctionProfileForLeafProbe(PrefixContextId, CallProbe, Binary);
+        getFunctionProfileForLeafProbe(ContextStrStack, CallProbe, Binary);
     FunctionProfile.addBodySamples(CallProbe->Index, 0, Count);
     FunctionProfile.addTotalSamples(Count);
     StringRef CalleeName = FunctionSamples::getCanonicalFnName(
         Binary->getFuncFromStartOffset(TargetOffset));
     if (CalleeName.size() == 0)
       continue;
     FunctionProfile.addCalledTargetSamples(CallProbe->Index, 0, CalleeName,
                                            Count);
   }
 }
 
 FunctionSamples &PseudoProbeCSProfileGenerator::getFunctionProfileForLeafProbe(
-    StringRef PrefixContextId, SmallVector<std::string, 16> &LeafInlinedContext,
+    SmallVectorImpl<std::string> &ContextStrStack,
     const PseudoProbeFuncDesc *LeafFuncDesc) {
-  assert(LeafInlinedContext.size() &&
-         "Profile context must have the leaf frame");
-  std::ostringstream OContextStr;
-  OContextStr << PrefixContextId.str();
+  assert(ContextStrStack.size() && "Profile context must have the leaf frame");
+  // Compress the context string except for the leaf frame
+  std::string LeafFrame = ContextStrStack.back();
+  ContextStrStack.pop_back();
+  CSProfileGenerator::compressRecursionContext(ContextStrStack);
 
-  for (uint32_t I = 0; I < LeafInlinedContext.size() - 1; I++) {
+  std::ostringstream OContextStr;
+  for (uint32_t I = 0; I < ContextStrStack.size(); I++) {
     if (OContextStr.str().size())
       OContextStr << " @ ";
-    OContextStr << LeafInlinedContext[I];
+    OContextStr << ContextStrStack[I];
   }
   // For leaf inlined context with the top frame, we should strip off the top
   // frame's probe id, like:
   // Inlined stack: [foo:1, bar:2], the ContextId will be "foo:1 @ bar"
   if (OContextStr.str().size())
     OContextStr << " @ ";
-  StringRef LeafLoc = LeafInlinedContext.back();
-  OContextStr << LeafLoc.split(":").first.str();
+  OContextStr << StringRef(LeafFrame).split(":").first.str();
 
   FunctionSamples &FunctionProile =
       getFunctionProfileForContext(OContextStr.str());
   FunctionProile.setFunctionHash(LeafFuncDesc->FuncHash);
   return FunctionProile;
 }
 
 FunctionSamples &PseudoProbeCSProfileGenerator::getFunctionProfileForLeafProbe(
-    StringRef PrefixContextId, const PseudoProbe *LeafProbe,
+    SmallVectorImpl<std::string> &ContextStrStack, const PseudoProbe *LeafProbe,
     ProfiledBinary *Binary) {
-  SmallVector<std::string, 16> LeafInlinedContext;
-  Binary->getInlineContextForProbe(LeafProbe, LeafInlinedContext);
+  // Explicitly copy the context for appending the leaf context
+  SmallVector<std::string, 16> ContextStrStackCopy(ContextStrStack.begin(),
+                                                   ContextStrStack.end());
+  Binary->getInlineContextForProbe(LeafProbe, ContextStrStackCopy);
   // Note that the context from probe doesn't include leaf frame,
   // hence we need to retrieve and append the leaf frame.
   const auto *FuncDesc = Binary->getFuncDescForGUID(LeafProbe->GUID);
-  LeafInlinedContext.emplace_back(FuncDesc->FuncName + ":" +
+  ContextStrStackCopy.emplace_back(FuncDesc->FuncName + ":" +
                                    Twine(LeafProbe->Index).str());
-  return getFunctionProfileForLeafProbe(PrefixContextId, LeafInlinedContext,
-                                        FuncDesc);
+  return getFunctionProfileForLeafProbe(ContextStrStackCopy, FuncDesc);
 }
 
 } // end namespace sampleprof
 } // end namespace llvm

llvm/tools/llvm-profgen/ProfiledBinary.h

public:
   // used as the key of function sample map
   std::string getExpandedContextStr(const std::list<uint64_t> &stack) const;
 
   const PseudoProbe *getCallProbeForAddr(uint64_t Address) const {
     return ProbeDecoder.getCallProbeForAddr(Address);
   }
   void
   getInlineContextForProbe(const PseudoProbe *Probe,
-                           SmallVector<std::string, 16> &InlineContextStack,
+                           SmallVectorImpl<std::string> &InlineContextStack,
                            bool IncludeLeaf = false) const {
     return ProbeDecoder.getInlineContextForProbe(Probe, InlineContextStack,
                                                  IncludeLeaf);
   }
   const AddressProbesMap &getAddress2ProbesMap() const {
     return ProbeDecoder.getAddress2ProbesMap();
   }
   const PseudoProbeFuncDesc *getFuncDescForGUID(uint64_t GUID) {

llvm/tools/llvm-profgen/ProfiledBinary.cpp

 //===-- ProfiledBinary.cpp - Binary decoder ---------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "ProfiledBinary.h"
 #include "ErrorHandling.h"
+#include "ProfileGenerator.h"
 #include "llvm/ADT/Triple.h"
 #include "llvm/Demangle/Demangle.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Format.h"
 #include "llvm/Support/TargetRegistry.h"
 #include "llvm/Support/TargetSelect.h"
 
 #define DEBUG_TYPE "load-binary"
bool ProfiledBinary::inlineContextEqual(uint64_t Address1,
   // needs to be remove that as it's not part of the calling context
   return std::equal(Context1.begin(), Context1.begin() + Context1.size() - 1,
                     Context2.begin(), Context2.begin() + Context2.size() - 1);
 }
 
 std::string
 ProfiledBinary::getExpandedContextStr(const std::list<uint64_t> &Stack) const {
   std::string ContextStr;
-  SmallVector<std::string, 8> ContextVec;
+  SmallVector<std::string, 16> ContextVec;
   // Process from frame root to leaf
   for (auto Iter = Stack.rbegin(); Iter != Stack.rend(); Iter++) {
     uint64_t Offset = virtualAddrToOffset(*Iter);
     const FrameLocationStack &ExpandedContext = getFrameLocationStack(Offset);
     for (const auto &Loc : ExpandedContext) {
       ContextVec.push_back(getCallSite(Loc));
     }
   }
 
   assert(ContextVec.size() && "Context length should be at least 1");
+  // Compress the context string except for the leaf frame
+  std::string LeafFrame = ContextVec.back();
+  ContextVec.pop_back();
+  CSProfileGenerator::compressRecursionContext<std::string>(ContextVec);
 
   std::ostringstream OContextStr;
   for (uint32_t I = 0; I < (uint32_t)ContextVec.size(); I++) {
     if (OContextStr.str().size()) {
       OContextStr << " @ ";
     }
-
-    if (I == ContextVec.size() - 1) {
-      // Only keep the function name for the leaf frame
-      StringRef Ref(ContextVec[I]);
-      OContextStr << Ref.split(":").first.str();
-    } else {
-      OContextStr << ContextVec[I];
-    }
-  }
+  // Only keep the function name for the leaf frame
+  if (OContextStr.str().size())
+    OContextStr << " @ ";
+  OContextStr << StringRef(LeafFrame).split(":").first.str();
   return OContextStr.str();
 }
 
 void ProfiledBinary::setPreferredBaseAddress(const ELFObjectFileBase *Obj) {
   for (section_iterator SI = Obj->section_begin(), SE = Obj->section_end();
        SI != SE; ++SI) {
     const SectionRef &Section = *SI;
     if (Section.isText()) {

llvm/tools/llvm-profgen/PseudoProbe.h

struct PseudoProbe {
   bool isBlock() const { return Type == PseudoProbeType::Block; }
   bool isIndirectCall() const { return Type == PseudoProbeType::IndirectCall; }
   bool isDirectCall() const { return Type == PseudoProbeType::DirectCall; }
   bool isCall() const { return isIndirectCall() || isDirectCall(); }
 
   // Get the inlined context by traversing current inline tree backwards,
   // each tree node has its InlineSite which is taken as the context.
   // \p ContextStack is populated in root to leaf order
-  void getInlineContext(SmallVector<std::string, 16> &ContextStack,
+  void getInlineContext(SmallVectorImpl<std::string> &ContextStack,
                         const GUIDProbeFunctionMap &GUID2FuncMAP,
                         bool ShowName) const;
   // Helper function to get the string from context stack
   std::string getInlineContextStr(const GUIDProbeFunctionMap &GUID2FuncMAP,
                                   bool ShowName) const;
   // Print pseudo probe while disassembling
   void print(raw_ostream &OS, const GUIDProbeFunctionMap &GUID2FuncMAP,
              bool ShowName);
public:
   // \p InlineContextStack.
   // Current leaf location info will be added if IncludeLeaf is true
   // Example:
   //  Current probe(bar:3) inlined at foo:2 then inlined at main:1
   //  IncludeLeaf = true,  Output: [main:1, foo:2, bar:3]
   //  IncludeLeaf = false, Output: [main:1, foo:2]
   void
   getInlineContextForProbe(const PseudoProbe *Probe,
-                           SmallVector<std::string, 16> &InlineContextStack,
+                           SmallVectorImpl<std::string> &InlineContextStack,
                            bool IncludeLeaf) const;
 
   const AddressProbesMap &getAddress2ProbesMap() const {
     return Address2ProbesMap;
   }
 
   const PseudoProbeFuncDesc *
   getInlinerDescForProbe(const PseudoProbe *Probe) const;
 };
 
 } // end namespace sampleprof
 } // end namespace llvm
 
 #endif

llvm/tools/llvm-profgen/PseudoProbe.cpp

static StringRef getProbeFNameForGUID(const GUIDProbeFunctionMap &GUID2FuncMAP,
   return It->second.FuncName;
 }
 
 void PseudoProbeFuncDesc::print(raw_ostream &OS) {
   OS << "GUID: " << FuncGUID << " Name: " << FuncName << "\n";
   OS << "Hash: " << FuncHash << "\n";
 }
 
-void PseudoProbe::getInlineContext(SmallVector<std::string, 16> &ContextStack,
+void PseudoProbe::getInlineContext(SmallVectorImpl<std::string> &ContextStack,
                                    const GUIDProbeFunctionMap &GUID2FuncMAP,
                                    bool ShowName) const {
   uint32_t Begin = ContextStack.size();
   PseudoProbeInlineTree *Cur = InlineTree;
   // It will add the string of each node's inline site during iteration.
   // Note that it won't include the probe's belonging function(leaf location)
   while (Cur->hasInlineSite()) {
     std::string ContextStr;

 const PseudoProbeFuncDesc *
 PseudoProbeDecoder::getFuncDescForGUID(uint64_t GUID) const {
   auto It = GUID2FuncDescMap.find(GUID);
   assert(It != GUID2FuncDescMap.end() && "Function descriptor doesn't exist");
   return &It->second;
 }
 
 void PseudoProbeDecoder::getInlineContextForProbe(
-    const PseudoProbe *Probe, SmallVector<std::string, 16> &InlineContextStack,
+    const PseudoProbe *Probe, SmallVectorImpl<std::string> &InlineContextStack,
     bool IncludeLeaf) const {
   Probe->getInlineContext(InlineContextStack, GUID2FuncDescMap, true);
   if (!IncludeLeaf)
     return;
   // Note that the context from probe doesn't include leaf frame,
   // hence we need to retrieve and prepend leaf if requested.
   const auto *FuncDesc = getFuncDescForGUID(Probe->GUID);
   InlineContextStack.emplace_back(FuncDesc->FuncName + ":" +

llvm/unittests/tools/CMakeLists.txt

 if(LLVM_TARGETS_TO_BUILD MATCHES "X86")
   add_subdirectory(
     llvm-cfi-verify
   )
 endif()
 
 add_subdirectory(
   llvm-exegesis
 )
-
+add_subdirectory(llvm-profgen)

llvm/unittests/tools/llvm-profgen/CMakeLists.txt

+add_llvm_unittest(LLVMProfgenTests
+    ContextCompressionTest.cpp
+  )
+
+target_link_libraries(LLVMProfgenTests PRIVATE LLVMTestingSupport)

llvm/unittests/tools/llvm-profgen/ContextCompressionTest.cpp

+//===-- ContextCompressionTest.cpp -------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+#include "../tools/llvm-profgen/ProfileGenerator.h"
+#include "gtest/gtest.h"
+
+using namespace llvm;
+using namespace sampleprof;
+
+TEST(TestCompression, TestNoSizeLimit1) {
+  SmallVector<std::string, 16> Context = {"a", "b", "c", "a", "b", "c"};
+  SmallVector<std::string, 16> Expect = {"a", "b", "c"};
+  CSProfileGenerator::compressRecursionContext(Context, -1);
+  EXPECT_TRUE(std::equal(Context.begin(), Context.end(), Expect.begin()));
+}
+
+TEST(TestCompression, TestNoSizeLimit2) {
+  SmallVector<std::string, 16> Context = {"m", "a", "a", "b", "c", "a",
+                                          "b", "c", "b", "c", "d"};
+  SmallVector<std::string, 16> Expect = {"m", "a", "b", "c", "d"};
+  CSProfileGenerator::compressRecursionContext(Context, -1);
+  EXPECT_TRUE(std::equal(Context.begin(), Context.end(), Expect.begin()));
+}
+
+TEST(TestCompression, TestMaxDedupSize) {
+  SmallVector<std::string, 16> Context = {"m", "a", "a", "b", "c", "a",
+                                          "b", "c", "b", "c", "d"};
+  SmallVector<std::string, 16> Expect = {"m", "a", "b", "c",
+                                         "a", "b", "c", "d"};
+  CSProfileGenerator::compressRecursionContext(Context, 2);
+  EXPECT_TRUE(std::equal(Context.begin(), Context.end(), Expect.begin()));
+}