[CSSPGO][llvm-profgen] Fix external address issues of perf reader (leading external LBR part)

[wlei]

Summary

We can have the sampling just hit into the external addresses, in that case, both the top stack frame and the latest LBR target are external addresses. For example:

	        ffffffff
 0x4006c8/0xffffffff/P/-/-/0  0x40069b/0x400670/M/-/-/0

 	          ffffffff
	          40067e
0xffffffff/0xffffffff/P/-/-/0  0x4006c8/0xffffffff/P/-/-/0  0x40069b/0x400670/M/-/-/0

Before we will ignore the entire samples. However, we found there exists some internal LBRs in the remaining part of sample, the range between them is still a valid range, we will lose some valid LBRs. Those LBRs will be unwinded based on a empty(context-less) call stack.

This change tries to fix it, instead of ignoring the entire sample, we only ignore the leading external addresses.

Note that the first outgoing LBR is useful since there is a valid range between it's source and next LBR's target.

[wenlei]

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

92

Ok, so this happens with existing test cases too. I didn't realize the entire function profile for small function could be missing due to external addresses even in contrived tests. Did you verify what is the external address (what function from what library) leads to samples involving quick_sort being ignored?

llvm/tools/llvm-profgen/PerfReader.cpp

256–257

A bit confused by the comment on "unwinded using a context-less frame stack" - I thought after we strip out the leading external frame and external LBR, we would still use the remaining stack as context, hence it's not context-less.

259

I think we can do some sanity check here:

1. assert that we have a paired LBR here? ie. LBR target is external.
2. also assert that the next frame on stack aligns with LBR source?

260

Should this be pushFrame/popFrame instead of switchToFrame depending on the instruction at the source of LBR?
Basically we are unwinding through the internal->external LBR here, which should be either a call or return, right?

612

If only leaf frames are external, can we keep the remaining frames for unwinding?

973

nit: move this into parseSample

1157

nit: top->leaf to make it explicit, for message and variable name.

[wlei]

addressing feedbacks.

[wlei]

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

80–85

Here it's indeed fixed by this patch.

92

Sorry for the confusing. This is not related with this patch, I deleted this part by mistake in https://reviews.llvm.org/D115013. When I fixed this test case, I realized it and tried to sneak in this diff :)

llvm/tools/llvm-profgen/PerfReader.cpp

256–257

Good point. Based on this, we don't need the code here. We can have CALL/Return/JMP to external address and current unwinder all covered this, we can just reuse them. One exception is return to external code, that should be handed by the next patch. Removed this code.

259

assert that we have a paired LBR here? ie. LBR target is external.

Sounds good, added assertion in validateInitialState.

also assert that the next frame on stack aligns with LBR source?

If I understand correctly, that assumes the LBR source should be a CALL? The tricky part is we don't only have CALL into external address, we can have RETURN, JMP. One common cases is the PLT, internal call --> PLT--> external address. PLT code is a JMP.

How about to give a warning if the following CALL unwinding hit a mismatched frame.

260

Yeah, same to above comment. the current unwinder should already covered pushFrame/popFrame. One difference is the Return. For returning to external address, we don't have a target callsite, hence we can't push a valid frame. But this case should be handled by https://reviews.llvm.org/D115550 which used an artificial frame to truncate the call stack.

which should be either a call or return.

You see, it appeared that the PLT code is a JMP.

612

Sounds good, tried to keep the remaining internal call stack for unwinding.

973

fixed, thanks!

1157

Fixed

[wenlei]

llvm/tools/llvm-profgen/PerfReader.cpp

62

Actually do we need the check on isLeadingFrameExternal? Should we always expect parent frame address and LBR source to align for any calls?

Additionally, should there a one instruction shift between frame address and source/call address (see getCallAddrFromFrameAddr)?

And when mismatch happens, should we abort unwinding? It seems that at this point it's guaranteed to generate incorrect context?

How you seen such mismatch happening?

240

nit: this is more like total branches. usually LBR record is considered the full 16/32 entires of branch pairs in LBR. same applies to the warning message.

259

On 2nd thought, you're right that if the transfer is not a call, there will be mismatch, PLT is one, tail call jump can be another.

Thought for PLT, perhaps we can treat PLT as external too, so anything involved PLT will be stripped too.

I was hoping that we can have a sense of how intrusive this kind of mismatch is. Hopefully it's rare. Warning is good but perhaps PLT case can be handled?

271–272

Update the comment as it's no longer accurate - it could regular intra function branch, or artificial branch cross function boundaries when there're external functions involved (example would be good).

llvm/tools/llvm-profgen/PerfReader.h

302

nit: LeadingFrame -> LeafFrame. LeafLBR -> LastLBR. Leaf or root is used for frame, but there's no leaf or root for LBR, which isn't hierarchical. If there're other inconsistent usage of the terms, we can fix them too.

Additionally, why not check on CurrentLeafFrame instead given the function name says "Frame"?

[hoy]

llvm/tools/llvm-profgen/PerfReader.cpp

524

nit: unwinded -> unwound

532

nit: NumLeadingExternalLBR -> NumLeadingOutgoingLBR?

612

Maybe we can keep the whole call stack by replacing consecutive external frames with an artificial frame introduced in the other patch. This should be synchronized with the LBR parser where we replace consecutive external LBRs with an artificial branch.

llvm/tools/llvm-profgen/PerfReader.h

217

nit: address -> addresses

Also enum class is preferred.

305

nit: use a single return statement return !LBRStack.empty() && LBRStack[0].Target == ExternalAddr .

[wlei]

addressing reviewer's feedback

[wlei]

llvm/tools/llvm-profgen/PerfReader.cpp

62

Should we always expect parent frame address and LBR source to align for any calls?

you see there is a comment to explain "// TODO: Currently we just assume all the addr that can't match the
2nd frame is in prolog/epilog.", so before we saw frame in prolog/epilog mismatch the call stack.

Additionally, should there a one instruction shift between frame address and source/call address (see getCallAddrFromFrameAddr)?

We already fix this mismatch in extractCallstack see

// We need to translate return address to call address for non-leaf frames.
if (!CallStack.empty()) {
  auto CallAddr = Binary->getCallAddrFromFrameAddr(FrameAddr);
  if (!CallAddr) {
  ....

And when mismatch happens, should we abort unwinding? It seems that at this point it's guaranteed to generate incorrect context?

Yeah, before for the frame in prolog/epilog, we didn't abort. If mismatch happen, we still can process using a context-less stack, but that will make things even complicated.

How you seen such mismatch happening?

I haven't tested it. I will add a warning for both leading frame issue and frame prolog/epilog. Maybe we can see how many cases of them to decide if we need to abort.

240

thanks for the suggestion.

259

PLT case can be handled, we can have a diff to make PLT code as external code. then we can have some statistic base on this. I will have a separated diff for PLT stuffs.

524

fixed, thanks!

532

fixed, thanks!

612

Good point. Changed to both use external branch, update in the next patch.

llvm/tools/llvm-profgen/PerfReader.h

217

Fixed, thanks

Also enum class is preferred.

It appeared that an complication issue to initialize the static const variable in ProfiledFrame

302

Thanks for the suggestion. The warning is moved to the next patch.

305

The warning is moved to the next patch, thanks!

[wenlei]

lgtm, thanks.

llvm/tools/llvm-profgen/PerfReader.cpp

259

Dealing with PLT in separate patch sounds good. And I guess we only need to deal with it if it's important enough.

[hoy]

llvm/tools/llvm-profgen/PerfReader.cpp

612

Thanks. Just to be clear, we will no longer need to break, instead, we'll continue whenever the top of stack is also an ExternalAddr. This way we could handle the following case

Ext
Ext
foo
Ext
Ext
bar
main
Ext/Ext /Ext/Ext foo/Ext foo/foo Ext/foo Ext/Ext bar/Ext bar/bar bar/bar ...

Though this should be rare, for completeness does it sounds reasonable?

[wlei]

llvm/tools/llvm-profgen/PerfReader.cpp

612

That's a good point. Only one thing: we don't know Ext/Ext is a Call or Return or Jmp. So I think we should preprocess to deduplicate the Ext in the call stack. like we also deduplicate the Ext in LBRsample.
in your case, we will get.

Ext
Ext
foo
Ext
Ext
bar
main

to

Ext
foo
Ext
bar
main

[hoy]

llvm/tools/llvm-profgen/PerfReader.cpp

612

Exactly, that is actually what I meant, i.e, to skip the current Ext frame only if the top of stack is already an Ext.

Do you think we need the other change to correctly truncate such as mixed callsite when reporting samples? Sounds good to implement there.

[wlei]

llvm/tools/llvm-profgen/PerfReader.cpp

612

Sounds good, I can move to code of truncating external addr from the 2nd patch to here. but here it's just truncate the context we need next patch to handle Call/Return of artificial branch.

[hoy]

llvm/tools/llvm-profgen/PerfReader.cpp

612

I see. Sounds good to move the truncating code here to make the current patch more complete and self-contained,

[wlei]

addressing Hontao's feedback: Also keep the external address in the middle, deduplicate them. They can still be unwound(in next patch). And truncate the context for them.

[hoy]

lgtm, thanks.

llvm/test/tools/llvm-profgen/Inputs/external-address.perfscript

+PERF_RECORD_MMAP2 2854748/2854748: [0x400000(0x1000) @ 0 00:1d 123291722 526021]: r-xp /home/inline-cs-noprobe.perfbin
+
+; Test for an external top address, should only ignore the call stack and keep unwinding the LBR
+
+; Valid LBR. The first 4006d7 will be kept for unwinding, the second will be truncated.
+
+          ffffffff
+          ffffffff
+            4006d7
+          ffffffff
+            4006d7
+          ffffffff
+ 0x4006c8/0x40067e/P/-/-/0  0x40069b/0x400670/M/-/-/0
+
+ ; Valid LBR
+          ffffffff
+ 0x4006c8/0x40067e/P/-/-/0  0x40069b/0x400670/M/-/-/0
+
+; Valid LBR
+          ffffffff
+ 0x4006c8/0xffffffff/P/-/-/0  0x40069b/0x400670/M/-/-/0
+
+; Valid LBR
+            40067e
+ 0x4006c8/0xffffffff/P/-/-/0  0x40069b/0x400670/M/-/-/0
+
+; Valid LBR
+          ffffffff
+  5541f689495641d7
+ 0xffffffff/0xffffffff/P/-/-/0  0x4006c8/0xffffffff/P/-/-/0  0x40069b/0x400670/M/-/-/0
+
+; Empty sample
+          ffffffff
+  5541f689495641d7
+ 0xffffffff/0xffffffff/P/-/-/0  0xffffffff/0xffffffff/P/-/-/0
+
+; Invalid LBR
+          ffffffff
+ 0xffffffff/0xffffffff/P/-/-/0  0x40069b/0x400670/M/-/-/0

llvm/test/tools/llvm-profgen/Inputs/inline-cs-noprobe.perfscript

 PERF_RECORD_MMAP2 2854748/2854748: [0x400000(0x1000) @ 0 00:1d 123291722 526021]: r-xp /home/inline-cs-noprobe.perfbin
 
-; test for an external or invalid top address, should skip the whole sample
-
-          ffffffff
-            40067e
-  5541f689495641d7
- 0x4006c8/0x40067e/P/-/-/0  0x4006c8/0x40067e/P/-/-/0  0x4006c8/0x40067e/P/-/-/0  0x4006c8/0x40067e/P/-/-/0  0x4006c8/0x40067e/P/-/-/0  0x4006c8/0x40067e/P/-/-/0  0x4006c8/0x40067e/P/-/-/0  0x4006c8/0x40067e/P/-/-/0  0x4006c8/0x40067e/P/-/-/0  0x4006c8/0x40067e/P/-/-/0  0x4006c8/0x40067e/P/-/-/0  0x4006c8/0x40067e/P/-/-/0  0x40069b/0x400670/M/-/-/0  0x4006c8/0x40067e/P/-/-/0  0x4006c8/0x40067e/P/-/-/0  0x4006c8/0x40067e/P/-/-/0
-
             40067e
   5541f689495641d7
  0x4006c8/0x40067e/P/-/-/0  0x4006c8/0x40067e/P/-/-/0  0x4006c8/0x40067e/P/-/-/0  0x4006c8/0x40067e/P/-/-/0  0x4006c8/0x40067e/P/-/-/0  0x4006c8/0x40067e/P/-/-/0  0x4006c8/0x40067e/P/-/-/0  0x4006c8/0x40067e/P/-/-/0  0x4006c8/0x40067e/P/-/-/0  0x4006c8/0x40067e/P/-/-/0  0x4006c8/0x40067e/P/-/-/0  0x4006c8/0x40067e/P/-/-/0  0x40069b/0x400670/M/-/-/0  0x4006c8/0x40067e/P/-/-/0  0x4006c8/0x40067e/P/-/-/0  0x4006c8/0x40067e/P/-/-/0

llvm/test/tools/llvm-profgen/cs-external-address.test

+; RUN: llvm-profgen --format=text --perfscript=%S/Inputs/external-address.perfscript --binary=%S/Inputs/inline-cs-noprobe.perfbin --output=%t --skip-symbolization --profile-summary-hot-count=0 --compress-recursion=0
+; RUN: FileCheck %s --input-file %t --check-prefix=CHECK-UNWINDER
+
+
+; CHECK-UNWINDER: [main:1 @ foo]
+; CHECK-UNWINDER:   2
+; CHECK-UNWINDER:   670-6ad:4
+; CHECK-UNWINDER:   6bd-6c8:4
+; CHECK-UNWINDER:   2
+; CHECK-UNWINDER:   69b->670:5
+; CHECK-UNWINDER:   6c8->67e:1
+; CHECK-UNWINDER: [main:1 @ foo:3.1 @ bar]
+; CHECK-UNWINDER:   1
+; CHECK-UNWINDER:   6af-6bb:4
+; CHECK-UNWINDER:   0
+
+; Manually created to test if remaining call stack can be correctly unwinded.
+; CHECK-UNWINDER: [main:1 @ foo:4 @ main:1 @ foo]
+; CHECK-UNWINDER:   2
+; CHECK-UNWINDER:   670-6ad:1
+; CHECK-UNWINDER:   6bd-6c8:1
+; CHECK-UNWINDER:   2
+; CHECK-UNWINDER:   69b->670:1
+; CHECK-UNWINDER:   6c8->67e:1
+; CHECK-UNWINDER: [main:1 @ foo:4 @ main:1 @ foo:3.1 @ bar]
+; CHECK-UNWINDER:   1
+; CHECK-UNWINDER:   6af-6bb:1
+; CHECK-UNWINDER:   0

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
 ; 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
->>>>>>> 02ea7084c370 ([llvm-profgen] Support LBR only perf script)
 ; 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

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

 
 ;CHECK:   1: 18
 ;CHECK:   2: 18
 ;CHECK:   3: 18
 ;CHECK:  6: swap:85
 ;CHECK:   1: 5
 ;CHECK:   2: 5
 ;CHECK:   3: 5
-;CHECK: main:486:0
+;CHECK: main:906:0
 ;CHECK:  0: 0
 ;CHECK:  3: 0
 ;CHECK:  4.1: 0
 ;CHECK:  4.3: 0
-;CHECK:  5.1: 6
-;CHECK:  5.3: 6
-;CHECK:  6: 6
-;CHECK:  6.1: 6
-;CHECK:  6.3: 6
+;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
+
 
 
 ; original code:
 ; clang -O3 -g -fno-optimize-sibling-calls -fdebug-info-for-profiling qsort.c -o a.out
 #include <stdio.h>
 #include <stdlib.h>
 
 void swap(int *a, int *b) {

llvm/tools/llvm-profgen/PerfReader.h

 // After parsing the sample, we record the samples by aggregating them
 // into this counter. The key stores the sample data and the value is
 // the sample repeat times.
 using AggregatedCounter =
     std::unordered_map<Hashable<PerfSample>, uint64_t,
                        Hashable<PerfSample>::Hash, Hashable<PerfSample>::Equal>;
 
 using SampleVector = SmallVector<std::tuple<uint64_t, uint64_t, uint64_t>, 16>;
+
+// The special frame addresses.
+enum SpecialFrameAddr {
+  // Dummy root of frame trie.
+  DummyRoot = 0,
+  // Represent all the addresses outside of current binary.
+  ExternalAddr = 1,
+};
+
 // The state for the unwinder, it doesn't hold the data but only keep the
 // pointer/index of the data, While unwinding, the CallStack is changed
 // dynamicially and will be recorded as the context of the sample
 struct UnwindState {
   // Profiled binary that current frame address belongs to
   const ProfiledBinary *Binary;
   // Call stack trie node
   struct ProfiledFrame {
-    const uint64_t Address = 0;
+    const uint64_t Address = DummyRoot;
     ProfiledFrame *Parent;
     SampleVector RangeSamples;
     SampleVector BranchSamples;
     std::unordered_map<uint64_t, std::unique_ptr<ProfiledFrame>> Children;
 
     ProfiledFrame(uint64_t Addr = 0, ProfiledFrame *P = nullptr)
         : Address(Addr), Parent(P) {}
     ProfiledFrame *getOrCreateChildFrame(uint64_t Address) {
       assert(Address && "Address can't be zero!");
       auto Ret = Children.emplace(
           Address, std::make_unique<ProfiledFrame>(Address, this));
       return Ret.first->second.get();
     }
     void recordRangeCount(uint64_t Start, uint64_t End, uint64_t Count) {
       RangeSamples.emplace_back(std::make_tuple(Start, End, Count));
     }
     void recordBranchCount(uint64_t Source, uint64_t Target, uint64_t Count) {
       BranchSamples.emplace_back(std::make_tuple(Source, Target, Count));
     }
-    bool isDummyRoot() { return Address == 0; }
+    bool isDummyRoot() { return Address == DummyRoot; }
+    bool isExternalFrame() { return Address == ExternalAddr; }
     bool isLeafFrame() { return Children.empty(); }
   };
 
   ProfiledFrame DummyTrieRoot;
   ProfiledFrame *CurrentLeafFrame;
   // Used to fall through the LBR stack
   uint32_t LBRIndex = 0;
   // Reference to PerfSample.LBRStack
   const SmallVector<LBREntry, 16> &LBRStack;
   // Used to iterate the address range
   InstructionPointer InstPtr;
   UnwindState(const PerfSample *Sample, const ProfiledBinary *Binary)
       : Binary(Binary), LBRStack(Sample->LBRStack),
         InstPtr(Binary, Sample->CallStack.front()) {
     initFrameTrie(Sample->CallStack);
   }
 
   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) {
       WithColor::warning() << "Bogus trace: stack tip = "
                            << format("%#010x", LeafAddr)
                            << ", LBR tip = " << format("%#010x\n", LBRLeaf);
       return false;
     }
     return true;
   }
 
   void checkStateConsistency() {
     assert(InstPtr.Address == CurrentLeafFrame->Address &&
            "IP should align with context leaf");
   }
 
   bool hasNextLBR() const { return LBRIndex < LBRStack.size(); }
   uint64_t getCurrentLBRSource() const { return LBRStack[LBRIndex].Source; }
   uint64_t getCurrentLBRTarget() const { return LBRStack[LBRIndex].Target; }
   const LBREntry &getCurrentLBR() const { return LBRStack[LBRIndex]; }
+  bool IsLastLBR() const { return LBRIndex == 0; }
+  bool getLBRStackSize() const { return LBRStack.size(); }
   void advanceLBR() { LBRIndex++; }
-
   ProfiledFrame *getParentFrame() { return CurrentLeafFrame->Parent; }
 
   void pushFrame(uint64_t Address) {
     CurrentLeafFrame = CurrentLeafFrame->getOrCreateChildFrame(Address);
   }
 
   void switchToFrame(uint64_t Address) {
     if (CurrentLeafFrame->Address == Address)
       return;
     CurrentLeafFrame = CurrentLeafFrame->Parent->getOrCreateChildFrame(Address);
   }
 
using ContextSampleCounterMap =
     std::unordered_map<Hashable<ContextKey>, SampleCounter,
                        Hashable<ContextKey>::Hash, Hashable<ContextKey>::Equal>;
 
 struct FrameStack {
   SmallVector<uint64_t, 16> Stack;
   ProfiledBinary *Binary;
   FrameStack(ProfiledBinary *B) : Binary(B) {}
   bool pushFrame(UnwindState::ProfiledFrame *Cur) {
+    // Truncate the context for external frame since this isn't a real call
+    // context the compiler will see
+    if (Cur->isExternalFrame())
+      return false;
     Stack.push_back(Cur->Address);
     return true;
   }
 
   void popFrame() {
     if (!Stack.empty())
       Stack.pop_back();
   }
   std::shared_ptr<StringBasedCtxKey> getContextKey();
 };
 
 struct ProbeStack {
   SmallVector<const MCDecodedPseudoProbe *, 16> Stack;
   ProfiledBinary *Binary;
   ProbeStack(ProfiledBinary *B) : Binary(B) {}
   bool pushFrame(UnwindState::ProfiledFrame *Cur) {
+    // Truncate the context for external frame since this isn't a real call
+    // context the compiler will see
+    if (Cur->isExternalFrame())
+      return false;
     const MCDecodedPseudoProbe *CallProbe =
         Binary->getCallProbeForAddr(Cur->Address);
     // We may not find a probe for a merged or external callsite.
     // Callsite merging may cause the loss of original probe IDs.
     // Cutting off the context from here since the inliner will
     // not know how to consume a context with unknown callsites.
     if (!CallProbe)
       return false;
bool isReturnState(UnwindState &State) const {
     // Simply check addressIsReturn, as ret is always reliable, both for
     // regular call and tail call.
     return Binary->addressIsReturn(State.getCurrentLBRSource());
   }
 
   void unwindCall(UnwindState &State);
   void unwindLinear(UnwindState &State, uint64_t Repeat);
   void unwindReturn(UnwindState &State);
-  void unwindBranchWithinFrame(UnwindState &State);
+  void unwindBranch(UnwindState &State);
 
   template <typename T>
   void collectSamplesFromFrame(UnwindState::ProfiledFrame *Cur, T &Stack);
   // Collect each samples on trie node by DFS traversal
   template <typename T>
   void collectSamplesFromFrameTrie(UnwindState::ProfiledFrame *Cur, T &Stack);
   void collectSamplesFromFrameTrie(UnwindState::ProfiledFrame *Cur);
 
public:
   bool profileIsCSFlat() { return ProfileIsCSFlat; }
 
 protected:
   ProfiledBinary *Binary = nullptr;
   StringRef PerfTraceFile;
 
   ContextSampleCounterMap SampleCounters;
   bool ProfileIsCSFlat = false;
+
+  uint64_t NumTotalSample = 0;
+  uint64_t NumLeafExternalFrame = 0;
+  uint64_t NumLeadingOutgoingLBR = 0;
 };
 
 // Read perf script to parse the events and samples.
 class PerfScriptReader : public PerfReaderBase {
 public:
   PerfScriptReader(ProfiledBinary *B, StringRef PerfTrace)
       : PerfReaderBase(B, PerfTrace){};
 

llvm/tools/llvm-profgen/PerfReader.cpp

void VirtualUnwinder::unwindCall(UnwindState &State) {
   // 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.
   uint64_t Source = State.getCurrentLBRSource();
   auto *ParentFrame = State.getParentFrame();
+
   if (ParentFrame == State.getDummyRootPtr() ||
       ParentFrame->Address != Source) {
     State.switchToFrame(Source);
   } else {
     State.popFrame();
   }
   State.InstPtr.update(Source);
 }
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);
   State.pushFrame(LBR.Source);
   State.InstPtr.update(LBR.Source);
 }
 
-void VirtualUnwinder::unwindBranchWithinFrame(UnwindState &State) {
+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() {
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)
+  if (Branch.IsArtificial || Branch.Target == ExternalAddr)
     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) {
   // Capture initial state as starting point for unwinding.
   UnwindState State(Sample, Binary);
 
   // Sanity check - making sure leaf of LBR aligns with leaf of stack sample
   // Stack sample sometimes can be unreliable, so filter out bogus ones.
   if (!State.validateInitialState())
     return false;
 
-  // Also do not attempt linear unwind for the leaf range as it's incomplete.
-  bool IsLeaf = true;
-
   // Now process the LBR samples in parrallel with stack sample
   // Note that we do not reverse the LBR entry order so we can
   // unwind the sample stack as we walk through LBR entries.
   while (State.hasNextLBR()) {
     State.checkStateConsistency();
 
+    // Do not attempt linear unwind for the leaf range as it's incomplete.
+    if (!State.IsLastLBR()) {
       // Unwind implicit calls/returns from inlining, along the linear path,
       // break into smaller sub section each with its own calling context.
-    if (!IsLeaf) {
       unwindLinear(State, Repeat);
     }
-    IsLeaf = false;
 
     // 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 {
-      // Unwind branches - for regular intra function branches, we only
-      // need to record branch with context.
-      unwindBranchWithinFrame(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.
+      unwindBranch(State);
     }
     State.advanceLBR();
     // Record `branch` with calling context after unwinding.
     recordBranchCount(Branch, State, Repeat);
   }
   // As samples are aggregated on trie, record them into counter map
   collectSamplesFromFrameTrie(State.getDummyRootPtr());
 
if (const auto *CtxKey = dyn_cast<StringBasedCtxKey>(K)) {
     llvm_unreachable("unexpected key type");
   }
 }
 
 void HybridPerfReader::unwindSamples() {
   if (Binary->useFSDiscriminator())
     exitWithError("FS discriminator is not supported in CS profile.");
   std::set<uint64_t> AllUntrackedCallsites;
+  VirtualUnwinder Unwinder(&SampleCounters, Binary);
   for (const auto &Item : AggregatedSamples) {
     const PerfSample *Sample = Item.first.getPtr();
-    VirtualUnwinder Unwinder(&SampleCounters, Binary);
     Unwinder.unwind(Sample, Item.second);
     auto &CurrUntrackedCallsites = Unwinder.getUntrackedCallsites();
     AllUntrackedCallsites.insert(CurrUntrackedCallsites.begin(),
                                  CurrUntrackedCallsites.end());
   }
 
   // Warn about untracked frames due to missing probes.
   if (ShowDetailedWarning) {
while (Index < Records.size()) {
 
     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. Ignore all remaining branches
-    // if there's no incoming branch before the external branch in reverse
-    // order.
+    // Ignore branches outside the current binary.
     if (IsExternal) {
-      if (PrevTrDst)
-        continue;
-      if (!LBRStack.empty()) {
+      if (!PrevTrDst && !LBRStack.empty()) {
         WithColor::warning()
             << "Invalid transfer to external code in LBR record at line "
             << TraceIt.getLineNumber() << ": " << TraceIt.getCurrentLine()
             << "\n";
       }
-      break;
+      // Do not ignore the entire samples, the remaining LBR can still be
+      // unwound using a context-less stack.
+      continue;
     }
 
     if (IsOutgoing) {
       if (!PrevTrDst) {
-        // This is 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.
+        // 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;
       }
 
       if (Binary->addressIsReturn(Src)) {
         // 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
while (!TraceIt.isAtEoF() && !TraceIt.getCurrentLine().startswith(" 0x")) {
     if (FrameStr.getAsInteger(16, FrameAddr)) {
       // We might parse a non-perf sample line like empty line and comments,
       // skip it
       TraceIt.advance();
       return false;
     }
     TraceIt.advance();
     // Currently intermixed frame from different binaries is not supported.
-    // Ignore caller frames not from binary of interest.
-    if (!Binary->addressIsCode(FrameAddr))
-      break;
+    if (!Binary->addressIsCode(FrameAddr)) {
+      if (CallStack.empty())
+        NumLeafExternalFrame++;
+      // Push a special value(ExternalAddr) for the external frames so that
+      // unwinder can still work on this with artificial Call/Return branch.
+      // After unwinding, the context will be truncated for external frame.
+      // Also deduplicate the consecutive external addresses.
+      if (CallStack.empty() || CallStack.back() != ExternalAddr)
+        CallStack.emplace_back(ExternalAddr);
+      continue;
+    }
 
     // We need to translate return address to call address for non-leaf frames.
     if (!CallStack.empty()) {
       auto CallAddr = Binary->getCallAddrFromFrameAddr(FrameAddr);
       if (!CallAddr) {
         // Stop at an invalid return address caused by bad unwinding. This could
         // happen to frame-pointer-based unwinding and the callee functions that
         // do not have the frame pointer chain set up.
         InvalidReturnAddresses.insert(FrameAddr);
         break;
       }
       FrameAddr = CallAddr;
     }
 
     CallStack.emplace_back(FrameAddr);
   }
 
+  // Strip out the bottom external addr.
+  if (CallStack.size() > 1 && CallStack.back() == ExternalAddr)
+    CallStack.pop_back();
+
   // Skip other unrelated line, find the next valid LBR line
   // Note that even for empty call stack, we should skip the address at the
   // bottom, otherwise the following pass may generate a truncated callstack
   while (!TraceIt.isAtEoF() && !TraceIt.getCurrentLine().startswith(" 0x")) {
     TraceIt.advance();
   }
   // Filter out broken stack sample. We may not have complete frame info
   // if sample end up in prolog/epilog, the result is dangling context not
uint64_t PerfScriptReader::parseAggregatedCount(TraceStream &TraceIt) {
   // it's unmatched
   uint64_t Count = 1;
   if (!TraceIt.getCurrentLine().getAsInteger(10, Count))
     TraceIt.advance();
   return Count;
 }
 
 void PerfScriptReader::parseSample(TraceStream &TraceIt) {
+  NumTotalSample++;
   uint64_t Count = parseAggregatedCount(TraceIt);
   assert(Count >= 1 && "Aggregated count should be >= 1!");
   parseSample(TraceIt, Count);
 }
 
 bool PerfScriptReader::extractMMap2EventForBinary(ProfiledBinary *Binary,
                                                   StringRef Line,
                                                   MMapEvent &MMap) {
if (extractMMap2EventForBinary(Binary, TraceIt.getCurrentLine(), MMap))
     updateBinaryAddress(MMap);
   TraceIt.advance();
 }
 
 void PerfScriptReader::parseEventOrSample(TraceStream &TraceIt) {
   if (isMMap2Event(TraceIt.getCurrentLine()))
     parseMMap2Event(TraceIt);
   else
     parseSample(TraceIt);
 }
 
 void PerfScriptReader::parseAndAggregateTrace() {
   // Trace line iterator
   TraceStream TraceIt(PerfTraceFile);
   while (!TraceIt.isAtEoF())
     parseEventOrSample(TraceIt);
 }
void PerfScriptReader::warnInvalidRange() {
   emitWarningSummary(RangeCrossFunc, TotalRangeNum,
                      "of profiled ranges do cross function boundaries.");
 }
 
 void PerfScriptReader::parsePerfTraces() {
   // Parse perf traces and do aggregation.
   parseAndAggregateTrace();
 
+  emitWarningSummary(NumLeafExternalFrame, NumTotalSample,
+                     "of samples have leaf external frame in call stack.");
+  emitWarningSummary(NumLeadingOutgoingLBR, NumTotalSample,
+                     "of samples have leading external LBR.");
+
   // Generate unsymbolized profile.
   warnTruncatedStack();
   warnInvalidRange();
   generateUnsymbolizedProfile();
 
   if (SkipSymbolization)
     writeUnsymbolizedProfile(OutputFilename);
 }
 
 } // end namespace sampleprof
 } // end namespace llvm