[llvm-profgen] Decouple artificial branch from LBR parser and fix external address related issues

[wlei]

Summary

This patch is fixing two issues for both CS and non-CS.

1. For external-call-internal, the head samples of the the internal function should be recorded.
2. avoid ignoring LBR after meeting the interrupt branch for CS profile

LBR parser is shared between CS and non-CS, we found it's error-prone while dealing with artificial branch inside LBR parser. Since artificial branch is mainly used for CS profile unwinding, this patch tries to simplify LBR parser by decoupling artificial branch code from it, the concept of artificial branch is removed and split into two transitional branches(internal-to-external, external-to-internal). Then we leave all the processing of external branch to unwinder.

Specifically for unwinder, remembering that we introduce external frame in https://reviews.llvm.org/D115550. We can just take external address as a regular address and reuse current unwind function(unwindCall, unwindReturn). For a normal case, the external frame will match an external LBR, and it will be filtered out by unwindLinear without losing any context.

The data also shows that the interrupt or standalone LBR pattern(unpaired case) does exist, we choose to handle it by clearing the call stack and keeping unwinding. Here we leverage checking in unwindLinear, because a standalone LBR, no matter its type, since it doesn’t have other part to pair, it will eventually cause a wrong linear range, like [external, internal], [internal, external]. Then set the state to invalid there.

[hoy]

Thanks for working on this! The refactoring does make the code base a lot cleaner.

llvm/tools/llvm-profgen/PerfReader.cpp

251

This can be an interrupt branch which does not correspond to any external frame on the call stack. Once such a branch is see, should the state have already been reset to dummy? I'm not seeing the resetting code anywhere. Maybe the stack resetting code being removed from `VirtualUnwinder::unwindCall can be reused to handle such case?

288

Would be nice to make the two cases fit into the call and return case below, respectively.

llvm/tools/llvm-profgen/ProfiledBinary.h

82

This could be a potential legal address. Use UINT64_MAX instead?

[wlei]

Updating D118177: [llvm-profgen] Decouple artificial branch from LBR parser and fix external address related issues

[wlei]

llvm/tools/llvm-profgen/PerfReader.cpp

251

Good point. There can be two patterns for the interrupt branch, I fixed them in other parts.

1. LBR target is an external address caused by interrupt. This will be a regular branch, Resetting the call stack there if a regular branch's target is external address. see PerfReader.cpp:293

2. LBR source is an external address caused by interrupt. This will go into unwindCall, we will find a mismatch call source and the call stack leaf. Resetting the call stack there. see PerfReader.cpp:67

288

Sounds good. Merging all the code into isCallState or isReturnState, now the four pattern: external-call-internal/internal-call-external/external-return-internal/internal-return-external are all handled by them.

llvm/tools/llvm-profgen/ProfiledBinary.h

82

Okay, Before I didn't use UINT64_MAX because there can be add operations to address value and adding value to UINT64_MAX caused overflow, we might always keep in mind of this. I changed to UINT64_MAX and fixed one overflow issue, also wondering if we have a better number for this so that overflow can't be issues in the future.

[hoy]

llvm/tools/llvm-profgen/PerfReader.cpp

240

nit: external-to-internal

856–859

Please leave a comment about why such branch is still useful, i.e, when sourceOffset is external.

llvm/tools/llvm-profgen/PerfReader.h

488

Is this detecting a general return or just return from external?

527

Can we have an internal-to-external return here? I'm wondering if it should be filtered out.

llvm/tools/llvm-profgen/ProfileGenerator.cpp

771

Can this be fused into populateBoundarySamplesForFunction?

Looking at how this is handled on the non-CS side, especially in populateBoundarySamplesForAllFunctions, there is a check if (!FrameVec.empty()) , can we do something similar in populateBoundarySamplesForFunction? Of course we need the check here to bypass populateBodySamplesForFunction call, or perhaps we can move the getFunctionProfileForContext call into the populating functions.

[wlei]

Updating D118177: [llvm-profgen] Decouple artificial branch from LBR parser and fix external address related issues

llvm/tools/llvm-profgen/PerfReader.cpp

240

fixed!

856–859

comments added.

llvm/tools/llvm-profgen/PerfReader.h

488

This is a heuristic to only detect returning from external because the source is external(unknown), so we leverage target address checking if it's the next inst of call inst.

For the general return, the source is known, so we use addressIsReturn to determine if it's a return.

527

The internal-to-external return pattern is handled by the right above branch(if (Binary->addressIsReturn(State.getCurrentLBRSource()))) which checking the source if it's a return.

llvm/tools/llvm-profgen/ProfileGenerator.cpp

771

Yes, fused into populateBoundarySamplesForFunction.

A little difference is I didn't move getFunctionProfileForContext into the populating functions because this is an optimization we did before to reuse the FunctionSamples of one context, otherwise we need to fetch the FunctionSamples twice(one in populateBodySamplesForFunction, one in populateBoundarySamplesForFunction).

Here I just directly bypassed the populateBodySamplesForFunction if the context is empty.

[hoy]

llvm/tools/llvm-profgen/PerfReader.h

488

I meant to say the name of this function doesn't exactly match its code. Maybe including the isSourceExternal check in this function?

527

Ok, a return to external is considered as a return. But in unwindReturn, the pushing external frame code is being removed. Should we keep it?

[wlei]

Updating D118177: [llvm-profgen] Decouple artificial branch from LBR parser and fix external address related issues

[wlei]

llvm/tools/llvm-profgen/PerfReader.h

488

Ah, I see, the function name is not clear. Renamed and merged isSourceExternal

527

Before the ArtificialBranch is actually from two branches [internal-to-external, external-to-internal], so at that time, we take two operations in one call to unwindReturn, first push an external frame, then push an internal address. the stack is [external, internal]

Now after decoupling ArtificialBranch into two branches, it calls unwindReturn twice: In the first call to unwindReturn , say the internal-to-external will push the first address which is the external address(the stack is [external]) and for the second call to unwindReturn , the external-to-internal will push the internal address.(the stack is [external, internal]).

The current one and the previous are expected to be equivalent, just right now it's split into two steps.

Same to`unwindCall`, you can also find it removes the code to pop the extra external frame.

[wlei]

Updating D118177: [llvm-profgen] Decouple artificial branch from LBR parser and fix external address related issues

[hoy]

llvm/tools/llvm-profgen/PerfReader.cpp

293

What kind of branch is not a call or return but with an external target address?

llvm/tools/llvm-profgen/PerfReader.h

527

Thanks for the explanation. I was trying to enumerate new cases we may see here. Previously with artificial branches, unpaired internal/external transitions may be thrown away, as well as samples following them. Now with this change, we never throw away any samples except for external/external transitions. This means the unwinder will see new patterns like unpaired I/E or E/I transitions, and I'm trying to make sense of them.

Perhaps we should bring this offline for a complete understanding and verification of the problem (you may already did that).

[wenlei]

llvm/tools/llvm-profgen/PerfReader.h

493

Check isValidState first.

517

Good that we don't need to check for artificial return, but perhaps we could assert that the target is next to a call for internal targets?

llvm/tools/llvm-profgen/ProfiledBinary.h

82

Technically, both and 1 and UINT64_MAX can be legal address, but practically that probably will never happen. While overflow is an issue with UINT64_MAX, I think 1 is fine?

[wlei]

Updating D118177: [llvm-profgen] Decouple artificial branch from LBR parser and fix external address related issues

llvm/tools/llvm-profgen/PerfReader.h

493

It's already checked in the only caller, see isCallState.

517

Not sure I fully get your point, we have the code in unwindReturn which call getCallAddrFromFrameAddr to get the target's next call inst. If the return variable(CallAddr) is not a call inst, it just return 0. Do you mean to assert on this zero value, I guess currently it won't pass for many cases. I think before we intent to silently give a zero, then the call stack is truncated by this wrong match.

void VirtualUnwinder::unwindReturn(UnwindState &State) {
  // Add extra frame as we unwind through the return
  const LBREntry &LBR = State.getCurrentLBR();
  uint64_t CallAddr = Binary->getCallAddrFromFrameAddr(LBR.Target);
  State.switchToFrame(CallAddr);
  ...

llvm/tools/llvm-profgen/ProfiledBinary.h

82

This is the address not offset, it will be minus the base address, this is more common than "add" overflow. Both 1 and UINT64_MAX can overflow, that's why I choose the value in the middle 0x1000000000000000ULL. But I'm fine with either value.

[wlei]

As we discussed offline, noted the summary here:

The data shows we the interrupt or standalone LBR pattern does exist, we should handle it(clear the call stack and keep unwinding).

Now we don’t choose to rely on detecting this LBR based on its type(call, return, jmp), we will leverage checking in linearUnwind, because a standalone LBR, no matter its type, since it doesn’t have other part to pair, it will eventually cause a wrong linear range, like [external, internal], [internal, external]. Then set the state to invalid there, this should make the code cleaner.

[hoy]

The current implementation looks much cleaner now, thanks for working on this!

llvm/tools/llvm-profgen/ProfileGenerator.cpp

852

nit: CalleeCtx.append(ContextId.begin(), ContextId.end());

[wlei]

Updating D118177: [llvm-profgen] Decouple artificial branch from LBR parser and fix external address related issues

llvm/tools/llvm-profgen/ProfileGenerator.cpp

852

Done, thanks!

[hoy]

llvm/tools/llvm-profgen/ProfiledBinary.h

82

How can UINT64_MAX overflow? Do we add anything to it?

I guess with value 1 we would need special handling when converting it to offset right?

Actually IIRC, the upper half of the 64-bit mem space, i.e, FFFF8000'00000000 through FFFFFFFF'FFFFFFFF, is used as kernel space on Linux, so using UINT64_MAX to represent external address should be fine.

[wlei]

llvm/tools/llvm-profgen/ProfiledBinary.h

82

Uh.. when it detect bogus trace LeafAddr >= LBRLeaf + 0x100, I already fixed this.

yeah, UINT64_MAX overflow are very unlikely, it should be fine.

1 is also okay I guess, minus a number, then become a negative value, but still doesn't conflict to binary offset.

[hoy]

LGTM.

llvm/tools/llvm-profgen/ProfiledBinary.h

82

I see. Then either value works.

[wenlei]

llvm/tools/llvm-profgen/PerfReader.cpp

88

This doesn't damage the call stack, so the state should remain valid, just skip recording this range.

There's an implicit assumption that is we also filter out external stack frames which matches external LBRs. Perhaps worth pointing out very briefly.

502–508

I think we need to be a bit more disciplined about adding these warnings now. As you can see, for any llvm-profgen run, we're always printing out a bunch of warnings, which can be over whelming to users (non-compiler devs).

It's ok to add these two in this change, but we probably need a follow up change to restructure those warnings: 1) try to see if we can trim some, 2) perhaps hide some less important ones under something like a verbose mode, or different warning level.

851

The notion of ExternalOffset is a bit weird -- it translates a special constant into something special but not a const... Wondering if it could be avoid, e.g. replace X == ExternalOffset with Binary->offsetIsCode(X)?

llvm/tools/llvm-profgen/ProfiledBinary.h

82

I don't have strong opinion either, but I'd suggest keep 1 if UINT64_MAX isn't better than 1. Make changes only if needed.

[wlei]

Updating D118177: [llvm-profgen] Decouple artificial branch from LBR parser and fix external address related issues

llvm/tools/llvm-profgen/PerfReader.cpp

88

Comments refined.

502–508

Agreed the less important warnings should be trimmed . Will follow up with a patch.

851

Changed to use Binary->offsetIsCode

llvm/tools/llvm-profgen/ProfiledBinary.h

82

Sounds good to use 1

[wenlei]

lgtm, thanks.

llvm/test/tools/llvm-profgen/Inputs/cs-interrupt.perfscript

 PERF_RECORD_MMAP2 2854748/2854748: [0x400000(0x1000) @ 0 00:1d 123291722 526021]: r-xp /home/noinline-cs-noprobe.perfbin
 
             4005dc
             400634
             400684
       7f68c5788793
- 0x4005c8/0x4005dc/P/-/-/0  0x40062f/0x4005b0/P/-/-/0  0x400645/0x4005ff/P/-/-/0  0x400637/0x400645/P/-/-/0  0x4005e9/0x400634/P/-/-/0  0x4005d7/0x4005e5/P/-/-/0  0x40062f/0x4005b0/P/-/-/0  0x400645/0x4005ff/P/-/-/0  0x400637/0x400645/P/-/-/0  0x4005e9/0x400634/P/-/-/0  0x4005d7/0x4005e5/P/-/-/0  0x40062f/0x4005b0/P/-/-/0  0x400645/0x4005ff/P/-/-/0  0x400637/0x400645/P/-/-/0  0xffffffff81c009d0/0x400634/P/-/-/0  0x40048a/0x40048e/P/-/-/0
+ 0x4005c8/0x4005dc/P/-/-/0  0x40062f/0x4005b0/P/-/-/0  0x400645/0x4005ff/P/-/-/0  0x400637/0x400645/P/-/-/0  0x4005e9/0x400634/P/-/-/0  0x4005d7/0x4005e5/P/-/-/0  0x40062f/0x4005b0/P/-/-/0  0x400645/0x4005ff/P/-/-/0  0x400637/0x400645/P/-/-/0  0x4005e9/0x400634/P/-/-/0  0x4005d7/0x4005e5/P/-/-/0  0xffffffff81c009d0/0x4005c3/P/-/-/0 0x40062f/0x4005b0/P/-/-/0  0x400645/0x4005ff/P/-/-/0  0x400637/0x400645/P/-/-/0
 
 
             4005dc
             400634
             400684
       7f68c5788793
- 0x4005c8/0x4005dc/P/-/-/0  0x40062f/0x4005b0/P/-/-/0  0x400645/0x4005ff/P/-/-/0  0x400637/0x400645/P/-/-/0  0x4005e9/0x400634/P/-/-/0  0x4005d7/0x4005e5/P/-/-/0  0x40062f/0x4005b0/P/-/-/0  0x400645/0x4005ff/P/-/-/0  0x400637/0x400645/P/-/-/0  0x4005e9/0x400634/P/-/-/0  0x4005d7/0x4005e5/P/-/-/0  0x400634/0xffffffff81c009d0/P/-/-/0 0x40062f/0x4005b0/P/-/-/0  0x400645/0x4005ff/P/-/-/0  0x400637/0x400645/P/-/-/0  0x40048a/0x40048e/P/-/-/0
+ 0x4005c8/0x4005dc/P/-/-/0  0x40062f/0x4005b0/P/-/-/0  0x400645/0x4005ff/P/-/-/0  0x400637/0x400645/P/-/-/0  0x4005e9/0x400634/P/-/-/0  0x4005d7/0x4005e5/P/-/-/0  0x40062f/0x4005b0/P/-/-/0  0x400645/0x4005ff/P/-/-/0  0x400637/0x400645/P/-/-/0  0x4005e9/0x400634/P/-/-/0  0x4005d7/0x4005e5/P/-/-/0  0x4005c3/0xffffffff81c009d0/P/-/-/0 0x40062f/0x4005b0/P/-/-/0  0x400645/0x4005ff/P/-/-/0  0x400637/0x400645/P/-/-/0
 
 // Transition 0xffffffff81c009d0/0x400634 is due to interrupt. Records after it, i.e, 0x40048a/0x40048e, should be ignored to avoid bogus instruction ranges.

llvm/test/tools/llvm-profgen/callback-external-addr.test

 ; RUN: llvm-profgen --format=text --perfscript=%S/Inputs/callback-external-addr.perfscript --binary=%S/Inputs/callback-external-addr.perfbin --output=%t --skip-symbolization
 ; RUN: FileCheck %s --input-file %t --check-prefix=CHECK-UNWINDER
 
+; RUN: llvm-profgen --format=text --perfscript=%S/Inputs/callback-external-addr.perfscript --binary=%S/Inputs/callback-external-addr.perfbin --output=%t --profile-summary-cold-count=0 --csspgo-preinliner=0 --gen-cs-nested-profile=0
+; RUN: FileCheck %s --input-file %t
+
 ; Test if call stack is correctly truncated.
 ; CHECK-UNWINDER-NOT: main:3 @ bar
 ; CHECK-UNWINDER-NOT: main:3 @ foo
 ; CHECK-UNWINDER-NOT: qux:3 @ baz
 ; CHECK-UNWINDER-NOT: qux:3 @ bar
 
 ; Test if return to wrong internal target
 ; CHECK-UNWINDER-NOT: baz:0 @ bar
 ; CHECK-UNWINDER-NOT: bar:0 @ baz
 ; CHECK-UNWINDER-NOT: baz:0 @ main
 ; CHECK-UNWINDER-NOT: bar:0 @ foo
 ; CHECK-UNWINDER-NOT: baz:0 @ qux
 
 ; Test for callback return from internal address to external address.
 ; [foo:2 @ qux:2 @ callBeforeReturn] and [foo:2 @ qux:4 @ callAfterReturn] should exist
 ; which means the callback return won't interrupt the previous call stack
 
+
+; CHECK-UNWINDER: []
+; CHECK-UNWINDER:   0
+; CHECK-UNWINDER:   5
+; CHECK-UNWINDER:   ffffffffffbfffff->690:13
+; CHECK-UNWINDER:   ffffffffffbfffff->6a0:7
+; CHECK-UNWINDER:   ffffffffffbfffff->715:7
+; CHECK-UNWINDER:   ffffffffffbfffff->730:5
+; CHECK-UNWINDER:   ffffffffffbfffff->7b0:5
 ; CHECK-UNWINDER: [bar]
 ; CHECK-UNWINDER:   1
-; CHECK-UNWINDER:   690-69e:12
+; CHECK-UNWINDER:   690-69e:13
 ; CHECK-UNWINDER:   0
 ; CHECK-UNWINDER: [baz]
 ; CHECK-UNWINDER:   1
 ; CHECK-UNWINDER:   6a0-6ae:7
 ; CHECK-UNWINDER:   0
 ; CHECK-UNWINDER: [foo]
 ; CHECK-UNWINDER:   2
 ; CHECK-UNWINDER:   730-747:5

 ; CHECK-UNWINDER:   6ce->720:7
 ; CHECK-UNWINDER: [main]
 ; CHECK-UNWINDER:   2
 ; CHECK-UNWINDER:   77d-7ab:5
 ; CHECK-UNWINDER:   7b0-7bf:5
 ; CHECK-UNWINDER:   1
 ; CHECK-UNWINDER:   7bf->77d:5
 
+; CHECK: [foo:2 @ qux]:132:5
+; CHECK:  0: 5
+; CHECK:  1: 5
+; CHECK:  2: 6 callBeforeReturn:6
+; CHECK:  3: 7
+; CHECK:  4: 7 callAfterReturn:7
+; CHECK:  5: 6
+; CHECK: [bar]:91:13
+; CHECK:  0: 13
+; CHECK:  1: 13
+; CHECK: [main]:65:0
+; CHECK:  2.1: 5
+; CHECK:  2.2: 5
+; CHECK:  3: 5
+; CHECK: [foo]:60:5
+; CHECK:  0: 5
+; CHECK:  1: 5
+; CHECK:  2: 5 qux:5
+; CHECK: [baz]:49:7
+; CHECK:  0: 7
+; CHECK:  1: 7
+; CHECK: [foo:2 @ qux:4 @ callAfterReturn]:49:7
+; CHECK:  0: 7
+; CHECK:  1: 7
+; CHECK: [foo:2 @ qux:2 @ callBeforeReturn]:42:6
+; CHECK:  0: 6
+; CHECK:  1: 6
+
 ; libcallback.c
 ; clang -shared -fPIC -o libcallback.so libcallback.c
 
 int callback(int *cnt, int (*func1)(int), int (*func2)(int), int p) {
   (*cnt)++;
   return func1(p) + func2(p);
 }
 

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

 ;; The test fails on Windows. Fix it before removing the following requirement.
 ; REQUIRES: x86_64-linux
 ; RUN: llvm-profgen --format=text --perfscript=%S/Inputs/cs-interrupt.perfscript --binary=%S/Inputs/noinline-cs-noprobe.perfbin --output=%t --skip-symbolization --profile-summary-cold-count=0 --csspgo-preinliner=0 --gen-cs-nested-profile=0
 ; RUN: FileCheck %s --input-file %t --check-prefix=CHECK-UNWINDER
 ; RUN: llvm-profgen --format=text --perfscript=%S/Inputs/cs-interrupt.perfscript --binary=%S/Inputs/noinline-cs-noprobe.perfbin --output=%t --profile-summary-cold-count=0 --csspgo-preinliner=0 --gen-cs-nested-profile=0
 ; RUN: FileCheck %s --input-file %t
 
-; CHECK:[main:1 @ foo]:88:0
-; CHECK: 2: 5
-; CHECK: 3: 5 bar:5
-; CHECK:[main:1 @ foo:3 @ bar]:74:5
-; CHECK: 0: 5
-; CHECK: 1: 5
-; CHECK: 2: 3
-; CHECK: 5: 4
-
-; CHECK-UNWINDER:      [main:1 @ foo]
+; CHECK: [main:1 @ foo]:72:0
+; CHECK:  2: 4
+; CHECK:  3: 4 bar:4
+; CHECK: [main:1 @ foo:3 @ bar]:67:4
+; CHECK:  0: 4
+; CHECK:  1: 5
+; CHECK:  2: 3
+; CHECK:  5: 4
+; CHECK: [foo]:32:0
+; CHECK:  2: 2
+; CHECK:  3: 2 bar:2
+; CHECK: [bar]:8:2
+; CHECK:  0: 1
+; CHECK:  1: 1
+
+; CHECK-UNWINDER:      []
+; CHECK-UNWINDER-NEXT:   0
+; CHECK-UNWINDER-NEXT:   1
+; CHECK-UNWINDER-NEXT:   ffffffffffbfffff->5c3:1
+; CHECK-UNWINDER-NEXT: [bar]
+; CHECK-UNWINDER-NEXT:   1
+; CHECK-UNWINDER-NEXT:   5b0-5c3:1
+; CHECK-UNWINDER-NEXT:   0
+; CHECK-UNWINDER-NEXT: [foo]
+; CHECK-UNWINDER-NEXT:   2
+; CHECK-UNWINDER-NEXT:   5ff-62f:2
+; CHECK-UNWINDER-NEXT:   645-645:2
+; CHECK-UNWINDER-NEXT:   3
+; CHECK-UNWINDER-NEXT:   62f->5b0:2
+; CHECK-UNWINDER-NEXT:   637->645:2
+; CHECK-UNWINDER-NEXT:   645->5ff:2
+; CHECK-UNWINDER-NEXT: [main:1 @ foo]
 ; CHECK-UNWINDER-NEXT:   3
-; CHECK-UNWINDER-NEXT:   5ff-62f:5
+; CHECK-UNWINDER-NEXT:   5ff-62f:4
 ; CHECK-UNWINDER-NEXT:   634-637:4
-; CHECK-UNWINDER-NEXT:   645-645:5
+; CHECK-UNWINDER-NEXT:   645-645:4
 ; CHECK-UNWINDER-NEXT:   3
-; CHECK-UNWINDER-NEXT:   62f->5b0:5
-; CHECK-UNWINDER-NEXT:   637->645:5
-; CHECK-UNWINDER-NEXT:   645->5ff:5
+; CHECK-UNWINDER-NEXT:   62f->5b0:4
+; CHECK-UNWINDER-NEXT:   637->645:4
+; CHECK-UNWINDER-NEXT:   645->5ff:4
 ; CHECK-UNWINDER-NEXT: [main:1 @ foo:3 @ bar]
-; CHECK-UNWINDER-NEXT:   3
+; CHECK-UNWINDER-NEXT:   4
 ; CHECK-UNWINDER-NEXT:   5b0-5c8:2
-; CHECK-UNWINDER-NEXT:   5b0-5d7:3
+; CHECK-UNWINDER-NEXT:   5b0-5d7:2
+; CHECK-UNWINDER-NEXT:   5c3-5d7:1
 ; CHECK-UNWINDER-NEXT:   5e5-5e9:4
 ; CHECK-UNWINDER-NEXT:   3
 ; CHECK-UNWINDER-NEXT:   5c8->5dc:2
 ; CHECK-UNWINDER-NEXT:   5d7->5e5:4
 ; CHECK-UNWINDER-NEXT:   5e9->634:4
 
-
 ; original code:
 ; clang -O0 -g test.c -o a.out
 #include <stdio.h>
 
 int bar(int x, int y) {
   if (x % 3) {
     return x - y;
   }

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: FileCheck %s --input-file %t --check-prefix=CHECK-EXT-ADDR
 ; 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=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: 2
-; CHECK-ARTIFICIAL-BRANCH: 400870-400870:2
-; CHECK-ARTIFICIAL-BRANCH: 400875-4008bf:1
-; CHECK-ARTIFICIAL-BRANCH: 1
-; CHECK-ARTIFICIAL-BRANCH: 4008bf->400870:2
+; CHECK-EXT-ADDR:      2
+; CHECK-EXT-ADDR-NEXT: 400870-400870:2
+; CHECK-EXT-ADDR-NEXT: 400875-4008bf:1
+; CHECK-EXT-ADDR-NEXT: 2
+; CHECK-EXT-ADDR-NEXT: 4008bf->400870:2
+; CHECK-EXT-ADDR-NEXT: ffffffffffffffff->400875:1
 
 ; CHECK-SYM-LIST: Dump profile symbol list
 ; CHECK-SYM-LIST: main
 ; CHECK-SYM-LIST: partition_pivot_first
 ; CHECK-SYM-LIST: partition_pivot_last
 ; CHECK-SYM-LIST: quick_sort
 ; CHECK-SYM-LIST: swap
 

 ;CHECK:  4.2: swap:300
 ;CHECK:   1: 25
 ;CHECK:   2: 25
 ;CHECK:   3: 25
 ;CHECK:  5: swap:102
 ;CHECK:   1: 6
 ;CHECK:   2: 6
 ;CHECK:   3: 6
+;CHECK: main:1362:0
+;CHECK:  0: 0
+;CHECK:  3: 0
+;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:  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
 
 ;w/o duplication factor :  3.1: 18
 ;w/o duplication factor :  3.3: 18
 ;w/o duplication factor :  4: 19

 
 ;CHECK:   1: 18
 ;CHECK:   2: 18
 ;CHECK:   3: 18
 ;CHECK:  6: swap:85
 ;CHECK:   1: 5
 ;CHECK:   2: 5
 ;CHECK:   3: 5
-;CHECK: main:906:0
-;CHECK:  0: 0
-;CHECK:  3: 0
-;CHECK:  4.1: 0
-;CHECK:  4.3: 0
-;CHECK:  5.1: 11
-;CHECK:  5.3: 11
-;CHECK:  6: 11
-;CHECK:  6.1: 14
-;CHECK:  6.3: 11
-;CHECK:  7: 0
-;CHECK:  8: 0 quick_sort:1
-;CHECK:  9: 0
-;CHECK:  11: 0
-;CHECK:  14: 0
-;CHECK:  65499: 0
 ;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:  4: 12 quick_sort:12
 ;CHECK:  6: 24
 ;CHECK:  65507: 12
 

llvm/tools/llvm-profgen/PerfReader.h

struct PerfInputFile {
   PerfFormat Format = PerfFormat::UnknownFormat;
   PerfContent Content = PerfContent::UnknownContent;
 };
 
 // The parsed LBR sample entry.
 struct LBREntry {
   uint64_t Source = 0;
   uint64_t Target = 0;
-  // An artificial branch stands for a series of consecutive branches starting
-  // from the current binary with a transition through external code and
-  // eventually landing back in the current binary.
-  bool IsArtificial = false;
-  LBREntry(uint64_t S, uint64_t T, bool I)
-      : Source(S), Target(T), IsArtificial(I) {}
+  LBREntry(uint64_t S, uint64_t T) : Source(S), Target(T) {}
 
 #ifndef NDEBUG
   void print() const {
     dbgs() << "from " << format("%#010x", Source) << " to "
            << format("%#010x", Target);
-    if (IsArtificial)
-      dbgs() << " Artificial";
   }
 #endif
 };
 
 #ifndef NDEBUG
 static inline void printLBRStack(const SmallVectorImpl<LBREntry> &LBRStack) {
   for (size_t I = 0; I < LBRStack.size(); I++) {
     dbgs() << "[" << I << "] ";
bool validateInitialState() {
     uint64_t LBRLeaf = LBRStack[LBRIndex].Target;
     uint64_t LeafAddr = CurrentLeafFrame->Address;
     assert((LBRLeaf != ExternalAddr || LBRLeaf == LeafAddr) &&
            "External leading LBR should match the leaf frame.");
 
     // When we take a stack sample, ideally the sampling distance between the
     // leaf IP of stack and the last LBR target shouldn't be very large.
     // Use a heuristic size (0x100) to filter out broken records.
-    if (LeafAddr < LBRLeaf || LeafAddr >= LBRLeaf + 0x100) {
+    if (LeafAddr < LBRLeaf || LeafAddr - LBRLeaf >= 0x100) {
       WithColor::warning() << "Bogus trace: stack tip = "
                            << format("%#010x", LeafAddr)
                            << ", LBR tip = " << format("%#010x\n", LBRLeaf);
       return false;
     }
     return true;
   }
 
public:
 
   uint64_t NumTotalBranches = 0;
   uint64_t NumExtCallBranch = 0;
   uint64_t NumMissingExternalFrame = 0;
   uint64_t NumMismatchedProEpiBranch = 0;
   uint64_t NumMismatchedExtCallBranch = 0;
 
 private:
+  bool isSourceExternal(UnwindState &State) const {
+    return State.getCurrentLBRSource() == ExternalAddr;
+  }
+
+  bool isTargetExternal(UnwindState &State) const {
+    return State.getCurrentLBRTarget() == ExternalAddr;
+  }
+
+  bool nextInstisCall(UnwindState &State) const {
+
+    uint64_t CallAddr =
+        Binary->getCallAddrFromFrameAddr(State.getCurrentLBRTarget());
+    return (CallAddr != 0);
+  }
+
+  // Determine whether the return source is from external code by checking if
+  // the target's the next inst is a call inst.
+  bool isReturnFromExternal(UnwindState &State) const {
+    return isSourceExternal(State) &&
+           (Binary->getCallAddrFromFrameAddr(State.getCurrentLBRTarget()) != 0);
+  }
+
+  // If the source is external address but it's not the `return` case, treat it
+  // as a call from external.
+  bool isCallFromExternal(UnwindState &State) const {
+    return isSourceExternal(State) &&
+           Binary->getCallAddrFromFrameAddr(State.getCurrentLBRTarget()) == 0;
+  }
+
   bool isCallState(UnwindState &State) const {
     // The tail call frame is always missing here in stack sample, we will
     // use a specific tail call tracker to infer it.
-    return isValidState(State) &&
-           Binary->addressIsCall(State.getCurrentLBRSource());
+    if (!isValidState(State))
+      return false;
+
+    if (Binary->addressIsCall(State.getCurrentLBRSource()))
+      return true;
+
+    return isCallFromExternal(State);
   }
 
   bool isReturnState(UnwindState &State) const {
     if (!isValidState(State))
       return false;
 
     // Simply check addressIsReturn, as ret is always reliable, both for
     // regular call and tail call.
-    if (!Binary->addressIsReturn(State.getCurrentLBRSource()))
-      return false;
+    if (Binary->addressIsReturn(State.getCurrentLBRSource()))
+      return true;
 
-    // In a callback case, a return from internal code, say A, to external
-    // runtime can happen. The external runtime can then call back to
-    // another internal routine, say B. Making an artificial branch that
-    // looks like a return from A to B can confuse the unwinder to treat
-    // the instruction before B as the call instruction. Here we detect this
-    // case if the return target is not the next inst of call inst, then we just
-    // do not treat it as a return.
-    uint64_t CallAddr =
-        Binary->getCallAddrFromFrameAddr(State.getCurrentLBRTarget());
-    return (CallAddr != 0);
+    return isReturnFromExternal(State);
   }
 
   bool isValidState(UnwindState &State) const { return !State.Invalid; }
 
   void unwindCall(UnwindState &State);
   void unwindLinear(UnwindState &State, uint64_t Repeat);
   void unwindReturn(UnwindState &State);
   void unwindBranch(UnwindState &State);
 

llvm/tools/llvm-profgen/PerfReader.cpp

 extern cl::opt<bool> ShowSourceLocations;
 extern cl::opt<std::string> OutputFilename;
 
 namespace llvm {
 namespace sampleprof {
 
 void VirtualUnwinder::unwindCall(UnwindState &State) {
   uint64_t Source = State.getCurrentLBRSource();
-  // An artificial return should push an external frame and an artificial call
-  // will match it and pop the external frame so that the context before and
-  // after the external call will be the same.
-  if (State.getCurrentLBR().IsArtificial) {
-    NumExtCallBranch++;
-    // A return is matched and pop the external frame.
-    if (State.getParentFrame()->isExternalFrame()) {
-      State.popFrame();
-    } else {
-      // An artificial return is missing, it happens that the sample is just hit
-      // in the middle of the external code. In this case, the leading branch is
-      // a call to external, we just keep unwinding use a context-less stack.
-      if (State.getParentFrame() != State.getDummyRootPtr())
-        NumMissingExternalFrame++;
-      State.clearCallStack();
-      State.pushFrame(Source);
-      State.InstPtr.update(Source);
-      return;
-    }
-  }
-
   auto *ParentFrame = State.getParentFrame();
   // The 2nd frame after leaf could be missing if stack sample is
   // taken when IP is within prolog/epilog, as frame chain isn't
   // setup yet. Fill in the missing frame in that case.
   // TODO: Currently we just assume all the addr that can't match the
   // 2nd frame is in prolog/epilog. In the future, we will switch to
   // pro/epi tracker(Dwarf CFI) for the precise check.
   if (ParentFrame == State.getDummyRootPtr() ||
       ParentFrame->Address != Source) {
     State.switchToFrame(Source);
     if (ParentFrame != State.getDummyRootPtr()) {
-      if (State.getCurrentLBR().IsArtificial)
+      if (Source == ExternalAddr) {
         NumMismatchedExtCallBranch++;
-      else
+        State.clearCallStack();
+        State.pushFrame(Source);
+      } else
         NumMismatchedProEpiBranch++;
     }
   } else {
     State.popFrame();
   }
   State.InstPtr.update(Source);
 }
 
 void VirtualUnwinder::unwindLinear(UnwindState &State, uint64_t Repeat) {
   InstructionPointer &IP = State.InstPtr;
   uint64_t Target = State.getCurrentLBRTarget();
   uint64_t End = IP.Address;
+
+  // Skip recording LBR trace with external address.
+  if (End == ExternalAddr || Target == ExternalAddr)
+    return;
+
   if (Target > End) {
     // Skip unwinding the rest of LBR trace when a bogus range is seen.
     State.setInvalid();
     return;
   }
+
   if (Binary->usePseudoProbes()) {
     // We don't need to top frame probe since it should be extracted
     // from the range.
     // The outcome of the virtual unwinding with pseudo probes is a
     // map from a context key to the address range being unwound.
     // This means basically linear unwinding is not needed for pseudo
     // probes. The range will be simply recorded here and will be
     // converted to a list of pseudo probes to report in ProfileGenerator.
void VirtualUnwinder::unwindLinear(UnwindState &State, uint64_t Repeat) {
   }
 }
 
 void VirtualUnwinder::unwindReturn(UnwindState &State) {
   // Add extra frame as we unwind through the return
   const LBREntry &LBR = State.getCurrentLBR();
   uint64_t CallAddr = Binary->getCallAddrFromFrameAddr(LBR.Target);
   State.switchToFrame(CallAddr);
-  // Push an external frame for the case of returning to external
-  // address(callback), later if an aitificial call is matched and it will be
-  // popped up. This is to 1)avoid context being interrupted by callback,
-  // context before or after the callback should be the same. 2) the call stack
-  // of function called by callback should be truncated which is done during
-  // recording the context on trie. For example:
-  //  main (call)--> foo (call)--> callback (call)--> bar (return)--> callback
-  //  (return)--> foo (return)--> main
-  // Context for bar should not include main and foo.
-  // For the code of foo, the context of before and after callback should both
-  // be [foo, main].
-  if (LBR.IsArtificial)
-    State.pushFrame(ExternalAddr);
   State.pushFrame(LBR.Source);
   State.InstPtr.update(LBR.Source);
 }
 
 void VirtualUnwinder::unwindBranch(UnwindState &State) {
   // TODO: Tolerate tail call for now, as we may see tail call from libraries.
   // This is only for intra function branches, excluding tail calls.
   uint64_t Source = State.getCurrentLBRSource();
   State.switchToFrame(Source);
   State.InstPtr.update(Source);
 }
 
 std::shared_ptr<StringBasedCtxKey> FrameStack::getContextKey() {
   std::shared_ptr<StringBasedCtxKey> KeyStr =
       std::make_shared<StringBasedCtxKey>();
   KeyStr->Context = Binary->getExpandedContext(Stack, KeyStr->WasLeafInlined);
-  if (KeyStr->Context.empty())
-    return nullptr;
   return KeyStr;
 }
 
 std::shared_ptr<AddrBasedCtxKey> AddressStack::getContextKey() {
   std::shared_ptr<AddrBasedCtxKey> KeyStr = std::make_shared<AddrBasedCtxKey>();
   KeyStr->Context = Stack;
   CSProfileGenerator::compressRecursionContext<uint64_t>(KeyStr->Context);
   CSProfileGenerator::trimContext<uint64_t>(KeyStr->Context);
void VirtualUnwinder::collectSamplesFromFrameTrie(
   } else {
     FrameStack Stack(Binary);
     collectSamplesFromFrameTrie<FrameStack>(Cur, Stack);
   }
 }
 
 void VirtualUnwinder::recordBranchCount(const LBREntry &Branch,
                                         UnwindState &State, uint64_t Repeat) {
-  if (Branch.IsArtificial || Branch.Target == ExternalAddr)
+  if (Branch.Target == ExternalAddr)
     return;
 
+  // Record external-to-internal pattern on the trie root, it later can be
+  // used for generating head samples.
+  if (Branch.Source == ExternalAddr) {
+    State.getDummyRootPtr()->recordBranchCount(Branch.Source, Branch.Target,
+                                               Repeat);
+    return;
+  }
+
   if (Binary->usePseudoProbes()) {
     // Same as recordRangeCount, We don't need to top frame probe since we will
     // extract it from branch's source address
     State.getParentFrame()->recordBranchCount(Branch.Source, Branch.Target,
                                               Repeat);
   } else {
     State.CurrentLeafFrame->recordBranchCount(Branch.Source, Branch.Target,
                                               Repeat);
   }
 }
 
 bool VirtualUnwinder::unwind(const PerfSample *Sample, uint64_t Repeat) {
while (State.hasNextLBR()) {
     if (!State.IsLastLBR()) {
       // Unwind implicit calls/returns from inlining, along the linear path,
       // break into smaller sub section each with its own calling context.
       unwindLinear(State, Repeat);
     }
 
     // Save the LBR branch before it gets unwound.
     const LBREntry &Branch = State.getCurrentLBR();
-
     if (isCallState(State)) {
       // Unwind calls - we know we encountered call if LBR overlaps with
       // transition between leaf the 2nd frame. Note that for calls that
       // were not in the original stack sample, we should have added the
       // extra frame when processing the return paired with this call.
       unwindCall(State);
     } else if (isReturnState(State)) {
       // Unwind returns - check whether the IP is indeed at a return
       // instruction
       unwindReturn(State);
-    } else if (isValidState(State)) {
+    } else if (isValidState(State) && !isTargetExternal(State)) {
       // Unwind branches
       // For regular intra function branches, we only need to record branch
       // with context. For an artificial branch cross function boundaries, we
       // got an issue with returning to external code. Take the two LBR enties
       // for example: [foo:8(RETURN), ext:1] [ext:3(CALL), bar:1] After perf
       // reader, we only get[foo:8(RETURN), bar:1], unwinder will be confused
       // like foo return to bar. Here we detect and treat this case as BRANCH
       // instead of RETURN which only update the source address.
emitWarningSummary(Unwinder.getUntrackedCallsites().size(),
                      "of profiled contexts are truncated due to missing probe "
                      "for call instruction.");
 
   emitWarningSummary(
       Unwinder.NumMismatchedExtCallBranch, Unwinder.NumTotalBranches,
       "of branches'source is a call instruction but doesn't match call frame "
       "stack, likely due to unwinding error of external frame.");
 
   emitWarningSummary(
       Unwinder.NumMismatchedProEpiBranch, Unwinder.NumTotalBranches,
       "of branches'source is a call instruction but doesn't match call frame "
       "stack, likely due to frame in prolog/epilog.");
 
   emitWarningSummary(Unwinder.NumMissingExternalFrame,
                      Unwinder.NumExtCallBranch,
                      "of artificial call branches but doesn't have an external "
                      "frame to match.");
 }
 
 bool PerfScriptReader::extractLBRStack(TraceStream &TraceIt,
                                        SmallVectorImpl<LBREntry> &LBRStack) {
   // The raw format of LBR stack is like:
   // 0x4005c8/0x4005dc/P/-/-/0 0x40062f/0x4005b0/P/-/-/0 ...
bool PerfScriptReader::extractLBRStack(TraceStream &TraceIt,
   if (!Records.empty() && !Records[0].contains('/')) {
     if (Records[0].getAsInteger(16, LeadingAddr)) {
       WarnInvalidLBR(TraceIt);
       TraceIt.advance();
       return false;
     }
     Index = 1;
   }
+
   // Now extract LBR samples - note that we do not reverse the
   // LBR entry order so we can unwind the sample stack as we walk
   // through LBR entries.
-  uint64_t PrevTrDst = 0;
-
   while (Index < Records.size()) {
     auto &Token = Records[Index++];
     if (Token.size() == 0)
       continue;
 
     SmallVector<StringRef, 8> Addresses;
     Token.split(Addresses, "/");
     uint64_t Src;
     uint64_t Dst;
 
     // Stop at broken LBR records.
     if (Addresses.size() < 2 || Addresses[0].substr(2).getAsInteger(16, Src) ||
         Addresses[1].substr(2).getAsInteger(16, Dst)) {
       WarnInvalidLBR(TraceIt);
       break;
     }
 
     bool SrcIsInternal = Binary->addressIsCode(Src);
     bool DstIsInternal = Binary->addressIsCode(Dst);
-    bool IsExternal = !SrcIsInternal && !DstIsInternal;
-    bool IsIncoming = !SrcIsInternal && DstIsInternal;
-    bool IsOutgoing = SrcIsInternal && !DstIsInternal;
-    bool IsArtificial = false;
-
-    // Ignore branches outside the current binary.
-    if (IsExternal) {
-      if (!PrevTrDst && !LBRStack.empty()) {
-        WithColor::warning()
-            << "Invalid transfer to external code in LBR record at line "
-            << TraceIt.getLineNumber() << ": " << TraceIt.getCurrentLine()
-            << "\n";
-      }
-      // Do not ignore the entire samples, the remaining LBR can still be
-      // unwound using a context-less stack.
+    if (!SrcIsInternal)
+      Src = ExternalAddr;
+    if (!DstIsInternal)
+      Dst = ExternalAddr;
+    // Filter external-to-external case to reduce LBR trace size.
+    if (!SrcIsInternal && !DstIsInternal)
       continue;
-    }
-
-    if (IsOutgoing) {
-      if (!PrevTrDst) {
-        // This is a leading outgoing LBR, we should keep processing the LBRs.
-        if (LBRStack.empty()) {
-          NumLeadingOutgoingLBR++;
-          // Record this LBR since current source and next LBR' target is still
-          // a valid range.
-          LBRStack.emplace_back(LBREntry(Src, ExternalAddr, false));
-          continue;
-        }
-        // This is middle unpaired outgoing jump which is likely due to
-        // interrupt or incomplete LBR trace. Ignore current and subsequent
-        // entries since they are likely in different contexts.
-        break;
-      }
-
-      // For transition to external code, group the Source with the next
-      // availabe transition target.
-      Dst = PrevTrDst;
-      PrevTrDst = 0;
-      IsArtificial = true;
-    } else {
-      if (PrevTrDst) {
-        // If we have seen an incoming transition from external code to internal
-        // code, but not a following outgoing transition, the incoming
-        // transition is likely due to interrupt which is usually unpaired.
-        // Ignore current and subsequent entries since they are likely in
-        // different contexts.
-        break;
-      }
-
-      if (IsIncoming) {
-        // For transition from external code (such as dynamic libraries) to
-        // the current binary, keep track of the branch target which will be
-        // grouped with the Source of the last transition from the current
-        // binary.
-        PrevTrDst = Dst;
-        continue;
-      }
-    }
 
     // TODO: filter out buggy duplicate branches on Skylake
-
-    LBRStack.emplace_back(LBREntry(Src, Dst, IsArtificial));
+    LBRStack.emplace_back(LBREntry(Src, Dst));
   }
   TraceIt.advance();
   return !LBRStack.empty();
 }
 
 bool PerfScriptReader::extractCallstack(TraceStream &TraceIt,
                                         SmallVectorImpl<uint64_t> &CallStack) {
   // The raw format of call stack is like:

 
 void UnsymbolizedProfileReader::parsePerfTraces() {
   readUnsymbolizedProfile(PerfTraceFile);
 }
 
 void PerfScriptReader::computeCounterFromLBR(const PerfSample *Sample,
                                              uint64_t Repeat) {
   SampleCounter &Counter = SampleCounters.begin()->second;
-  uint64_t EndOffeset = 0;
+  uint64_t ExternalOffset = Binary->virtualAddrToOffset(ExternalAddr);
+  uint64_t EndOffeset = ExternalOffset;
   for (const LBREntry &LBR : Sample->LBRStack) {
-    assert(LBR.Source != ExternalAddr &&
-           "Branch' source should not be an external address, it should be "
-           "converted to aritificial branch.");
     uint64_t SourceOffset = Binary->virtualAddrToOffset(LBR.Source);
-    uint64_t TargetOffset = LBR.Target == static_cast<uint64_t>(ExternalAddr)
-                                ? static_cast<uint64_t>(ExternalAddr)
-                                : Binary->virtualAddrToOffset(LBR.Target);
+    uint64_t TargetOffset = Binary->virtualAddrToOffset(LBR.Target);
 
-    if (!LBR.IsArtificial && TargetOffset != ExternalAddr) {
+    // Record the branch if its sourceOffset is external. It can be the case an
+    // external source call an internal function, later this branch will be used
+    // to generate the function's head sample.
+    if (TargetOffset != ExternalOffset) {
       Counter.recordBranchCount(SourceOffset, TargetOffset, Repeat);
     }
 
     // If this not the first LBR, update the range count between TO of current
     // LBR and FROM of next LBR.
     uint64_t StartOffset = TargetOffset;
-    if (EndOffeset != 0) {
-      if (StartOffset <= EndOffeset)
-        Counter.recordRangeCount(StartOffset, EndOffeset, Repeat);
-    }
+    if (EndOffeset != ExternalOffset && StartOffset != ExternalOffset &&
+        StartOffset <= EndOffeset)
     EndOffeset = SourceOffset;
   }
 }
 
 void LBRPerfReader::parseSample(TraceStream &TraceIt, uint64_t Count) {
   std::shared_ptr<PerfSample> Sample = std::make_shared<PerfSample>();
   // Parsing LBR stack and populate into PerfSample.LBRStack
   if (extractLBRStack(TraceIt, Sample->LBRStack)) {

llvm/tools/llvm-profgen/ProfileGenerator.h

private:
   void computeSizeForProfiledFunctions();
   // Post processing for profiles before writing out, such as mermining
   // and trimming cold profiles, running preinliner on profiles.
   void postProcessProfiles();
 
   void populateBodySamplesForFunction(FunctionSamples &FunctionProfile,
                                       const RangeSample &RangeCounters);
   void populateBoundarySamplesForFunction(SampleContextFrames ContextId,
-                                          FunctionSamples &FunctionProfile,
+                                          FunctionSamples *CallerProfile,
                                           const BranchSample &BranchCounters);
   void populateInferredFunctionSamples();
 
   void generateProbeBasedProfile();
 
   // Fill in function body samples from probes
   void populateBodySamplesWithProbes(const RangeSample &RangeCounter,
                                      SampleContextFrames ContextStack);

llvm/tools/llvm-profgen/ProfileGenerator.cpp

void CSProfileGenerator::computeSizeForProfiledFunctions() {
   // Flush the symbolizer to save memory.
   Binary->flushSymbolizer();
 }
 
 void CSProfileGenerator::generateLineNumBasedProfile() {
   for (const auto &CI : *SampleCounters) {
     const auto *CtxKey = cast<StringBasedCtxKey>(CI.first.getPtr());
 
+    FunctionSamples *FunctionProfile = nullptr;
+    // Sample context will be empty if the jump is an external-to-internal call
+    // pattern, the head samples should be added for the internal function.
+    if (!CtxKey->Context.empty()) {
       // Get or create function profile for the range
-    FunctionSamples &FunctionProfile =
-        getFunctionProfileForContext(CtxKey->Context, CtxKey->WasLeafInlined);
-
+      FunctionProfile = &getFunctionProfileForContext(CtxKey->Context,
+                                                      CtxKey->WasLeafInlined);
       // Fill in function body samples
-    populateBodySamplesForFunction(FunctionProfile, CI.second.RangeCounter);
+      populateBodySamplesForFunction(*FunctionProfile, CI.second.RangeCounter);
+    }
     // Fill in boundary sample counts as well as call site samples for calls
     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.
do {
         updateBodySamplesforFunctionProfile(FunctionProfile, *LeafLoc, Count);
         FunctionProfile.addTotalSamples(Count);
       }
     } while (IP.advance() && IP.Address <= RangeEnd);
   }
 }
 
 void CSProfileGenerator::populateBoundarySamplesForFunction(
-    SampleContextFrames ContextId, FunctionSamples &FunctionProfile,
+    SampleContextFrames ContextId, FunctionSamples *CallerProfile,
     const BranchSample &BranchCounters) {
 
   for (const auto &Entry : BranchCounters) {
     uint64_t SourceOffset = Entry.first.first;
     uint64_t TargetOffset = Entry.first.second;
     uint64_t Count = Entry.second;
     assert(Count != 0 && "Unexpected zero weight branch");
 
     StringRef CalleeName = getCalleeNameForOffset(TargetOffset);
     if (CalleeName.size() == 0)
       continue;
 
+    SampleContextFrameVector CalleeCtx;
+    if (CallerProfile) {
+      assert(!ContextId.empty() &&
+             "CallerProfile is null only if ContextId is empty");
       // Record called target sample and its count
       auto LeafLoc = Binary->getInlineLeafFrameLoc(SourceOffset);
-    if (!LeafLoc.hasValue())
-      continue;
-    FunctionProfile.addCalledTargetSamples(
+      if (LeafLoc.hasValue()) {
+        CallerProfile->addCalledTargetSamples(
             LeafLoc->Location.LineOffset,
             getBaseDiscriminator(LeafLoc->Location.Discriminator), CalleeName,
             Count);
 
         // Record head sample for called target(callee)
-    SampleContextFrameVector CalleeCtx(ContextId.begin(), ContextId.end());
+        std::copy(ContextId.begin(), ContextId.end(),
+                  std::back_inserter(CalleeCtx));
         assert(CalleeCtx.back().FuncName == LeafLoc->FuncName &&
                "Leaf function name doesn't match");
         CalleeCtx.back() = *LeafLoc;
+      }
+    }
     CalleeCtx.emplace_back(CalleeName, LineLocation(0, 0));
     FunctionSamples &CalleeProfile = getFunctionProfileForContext(CalleeCtx);
     CalleeProfile.addHeadSamples(Count);
   }
 }
 
 static SampleContextFrame
 getCallerContext(SampleContextFrames CalleeContext,

llvm/tools/llvm-profgen/ProfiledBinary.h

struct InstructionPointer {
   InstructionPointer(const ProfiledBinary *Binary, uint64_t Address,
                      bool RoundToNext = false);
   bool advance();
   bool backward();
   void update(uint64_t Addr);
 };
 
 // The special frame addresses.
-enum SpecialFrameAddr {
+enum SpecialFrameAddr : uint64_t {
   // Dummy root of frame trie.
   DummyRoot = 0,
-  // Represent all the addresses outside of current binary.
+  // Represent all the addresses outside of current binary. Use a large value to
+  // avoid integer overflow.
   // This's also used to indicate the call stack should be truncated since this
   // isn't a real call context the compiler will see.
-  ExternalAddr = 1,
+  ExternalAddr = UINT64_MAX,
 };
 
 using RangesTy = std::vector<std::pair<uint64_t, uint64_t>>;
 
 struct BinaryFunction {
   StringRef FuncName;
   // End of range is an exclusive bound.
   RangesTy Ranges;

llvm/tools/llvm-profgen/ProfiledBinary.cpp

bool ProfiledBinary::inlineContextEqual(uint64_t Address1, uint64_t Address2) {
   return std::equal(Context1.begin(), Context1.begin() + Context1.size() - 1,
                     Context2.begin(), Context2.begin() + Context2.size() - 1);
 }
 
 SampleContextFrameVector
 ProfiledBinary::getExpandedContext(const SmallVectorImpl<uint64_t> &Stack,
                                    bool &WasLeafInlined) {
   SampleContextFrameVector ContextVec;
+  if (Stack.empty())
+    return ContextVec;
   // Process from frame root to leaf
   for (auto Address : Stack) {
     uint64_t Offset = virtualAddrToOffset(Address);
     const SampleContextFrameVector &ExpandedContext =
         getFrameLocationStack(Offset);
     // An instruction without a valid debug line will be ignored by sample
     // processing
     if (ExpandedContext.empty())