[llvm-profgen] Filter out invalid LBR ranges.

[hoy]

Summary

The profiler can sometimes give us a LBR trace that implicates bogus code ranges. For example,

0xc5acb56/0xc66c6c0 0xc628195/0xf31fbb0 0xc611261/0xc628130 0xc5c1a21/0xc6111c0 0x1f7edfd3/0xc5c3a50 0xc5c154f/0x1f7edec0 0xe8eed07/0xc5c11e0

, note that the first two pairs are supposed to form a linear execution range, in this case, it is [0xf31fbb0, 0xc5acb56] , which doesn't make sense.

Such bogus ranges should be ruled out to avoid generating a bad profile. I'm fixing this for both CS and non-CS cases.

[wenlei]

llvm/tools/llvm-profgen/PerfReader.cpp

288–289

Is it critical to skip unwinding instead of ignore the entire record for invalid range? If not, perhaps it's better to keep it simple and just ignore such record. I imagine such invalid ranges are rare.

298–299

Theoretically any kind of unwind can discover bad state, so this is not unique to unwindLinear. I suggest we have an invalid state flag for UnwindState, which gets checked for all isXXState (may also added isValidState). This way we also keep the API for unwindXX consistent, and also avoid special checking after unwindLinear.

1182

nit: above->after

1197

I think the choice to use unique ranges was intentional. What motivated this change?

1213–1216

Such invalid ranges doesn't seem to be recorded anyways, how do we get those ranges?

1220

It is unclear to user what "bogus" means. And one could argue that ranges crossing function boundaries (one above) is also bogus. Suggest to be specific about what this is so user knows what this means, e.g. ... of profiled ranges have range start after range end.

llvm/tools/llvm-profgen/PerfReader.h

301

What motivated this change? Conceptually parent frame of dummy root should indeed be nullptr.

[hoy]

llvm/tools/llvm-profgen/PerfReader.cpp

288–289

Sort of. With one of internal large services we have about 5% of such invalid ranges. Ignoring the whole trace where such ranges are in may not be trivial.

warning: 5.13%(77654546/1512342539) of profiled ranges is bogus.

298–299

Sounds good.

1197

Can you remind me of why it was intentional?

I think it's useful to give a number of how many samples are invalid, though some of them could be the same. This reflects the portion of samples will be dropped.

1213–1216

Right, they'll be abandoned. The warning here is to tell how many such samples would be dropped so we kinda getting a sense how important the issue is.

1220

Done.

llvm/tools/llvm-profgen/PerfReader.h

301

It is to handle the diversion of probe samples and dwarf samples. With probe, LBR ranges are reported towards its parent frame (calling context), while w/o probe, ranges are reported towards the leaf frame. See VirtualUnwinder::unwindLinear. When unwinding is at a bad state, the call stack is reset to DummyTrieRoot, thus leading to a null parent technically for the probe case which will cause AV here and there.

[hoy]

Addressing comments.

[wenlei]

llvm/tools/llvm-profgen/PerfReader.cpp

288–289

Is this happening for just one workload or more often across different workloads?

304

nit: put this towards the end of the if-else sequence as it's supposed to be a corner case.

} else if (isValidState(State)) {
    // Unwind branches
    ...
   unwindBranch(State);
}
else {
    // Invalid state
}

305–308

all ranges will be counted towards the root context.

When we skip unwinding, we still have the context carried with probe/dwarf, so it's not always going to be base context, right?

1197

How many unique instance of one issue is an indicator of how wide spread such issue is. The way we report these stats are also aligned with how it was implemented - one "profiled range" is one unique range no matter that count it has.

In this case, there's 5% by your counting, what's the % with original counting?

1213–1216

My question was basically this - if such ranges are dropped earlier, how do we even see ranges whose start > end here?

Looked into this, I guess the answer is we warn on those before they are dropped?

llvm/tools/llvm-profgen/PerfReader.h

301

How many call sites need to guard against this? As an API, I think getParentFrame better strictly do what it says if possible. But if that means sprinkling a check in a dozen places, maybe it's ok to leave it in this state.

[hoy]

llvm/tools/llvm-profgen/PerfReader.cpp

288–289

So far I've only worked on a single workload. The other workloads all suffer from the issue, though not clear what's the percentage.

304

That'd require to change isCallState ... to. check for the invalid flag. It only checks if the current ip corresponds to a call inst.

305–308

Yes, ranges themselves carry inline contexts. The wording may be confusing. I'm changing it to "the rest of the trace can still be processed as if they do not have a calling context."

1197

How many unique instance of one issue is an indicator of how wide spread such issue is. The way we report these stats are also aligned with how it was implemented - one "profiled range" is one unique range no matter that count it has.

Not sure but feel like knowing the real number of samples to be dropped is more helpful, at least it tells how many samples we are losing in reality. For example, we aggregate samples by their look and we have ninety nine A and one B. If B is invalid, previous implementation will tell 50% of samples are invalid, while the current one tells 1% is invalid. Feel like knowing 1% is more helpful than 50%. WDYT?

In this case, there's 5% by your counting, what's the % with original counting?

Original counting is about 4%. Not a big difference.

1213–1216

Yes, this code runs before we actually process the ranges.

llvm/tools/llvm-profgen/PerfReader.h

301

On the second thought, here shouldn't be changed. An assumption of the virtual unwinding is that there always be a leaf frame in the stack. checkStateConsistency basically verifies that. With invalid state we can still honor that assumption by pushing the broken range's IP onto the stack so that nothing else will be changed.

[hoy]

Updating D123271: [llvm-profgen] Filter out invalid LBR ranges.

[wenlei]

llvm/tools/llvm-profgen/PerfReader.cpp

304

Yes, I think we should change all isXXState to check validness first anyways. An invalid state isn't any of the valid states.

305–308

they do not have a calling context. -> they do not have stack sample?

1197

Ok, makes sense. Then we need to change the message, something like " .. samples are from ranges ..", instead of " ... profiled ranges.. "

[hoy]

llvm/tools/llvm-profgen/PerfReader.cpp

304

Sounds good.

305–308

done.

[hoy]

Updating D123271: [llvm-profgen] Filter out invalid LBR ranges.

[wenlei]

lgtm, thanks.

llvm/test/tools/llvm-profgen/Inputs/invalid-range.perfscript

+ PERF_RECORD_MMAP2 1243676/1243676: [0x201000(0x1000) @ 0 00:1d 224517108 1044165]: r-xp /home/noinline-cs-pseudoprobe.perfbin
+
+            20179e
+            2017f9
+      7f83e84e7793
+  5541f689495641d7
+ 0x2017cf/0x20179e/P/-/-/0  0x20177f/0x2017c4/P/-/-/0  0x2017bf/0x201760/P/-/-/0  0x2017d8/0x2017e3/P/-/-/0  0x20177f/0x2017c4/P/-/-/0  0x2017bf/0x201760/P/-/-/0  0x2017cf/0x20179e/P/-/-/0
+
+
+// The consecutive pairs 0x2017bf/0x201760 and 0x2017d8/0x2017e3 form an invalid execution range [0x2017e3, 0x2017bf], should be ignored to avoid bogus instruction ranges.

llvm/test/tools/llvm-profgen/invalid-range.test

+; In the perfscript input, the consecutive branch pairs 0x2017bf/0x201760 and 0x2017d8/0x2017e3 form an invalid execution range [0x2017e3, 0x2017bf].
+; We are testing only the invalid range is dropped to avoid bogus instruction ranges. All other ranges and all branch samples should be kept.
+;
+; RUN: llvm-profgen --format=text --perfscript=%S/Inputs/invalid-range.perfscript --binary=%S/Inputs/noinline-cs-pseudoprobe.perfbin --output=%t1 --skip-symbolization --ignore-stack-samples --use-offset=0
+; RUN: FileCheck %s --input-file %t1 --check-prefix=NOCS
+
+; RUN: llvm-profgen --format=text --perfscript=%S/Inputs/invalid-range.perfscript --binary=%S/Inputs/noinline-cs-pseudoprobe.perfbin --output=%t2 --skip-symbolization --use-offset=0
+; RUN: FileCheck %s --input-file %t2 --check-prefix=CS
+
+
+; NOCS:      4
+; NOCS-NEXT: 201760-20177f:2
+; NOCS-NEXT: 20179e-2017bf:1
+; NOCS-NEXT: 2017c4-2017cf:1
+; NOCS-NEXT: 2017c4-2017d8:1
+; NOCS-NEXT: 4
+; NOCS-NEXT: 20177f->2017c4:2
+; NOCS-NEXT: 2017bf->201760:2
+; NOCS-NEXT: 2017cf->20179e:2
+; NOCS-NEXT: 2017d8->2017e3:1
+
+
+; CS:      []
+; CS-NEXT:  3
+; CS-NEXT:  201760-20177f:1
+; CS-NEXT:  20179e-2017bf:1
+; CS-NEXT:  2017c4-2017d8:1
+; CS-NEXT:  4
+; CS-NEXT:  20177f->2017c4:1
+; CS-NEXT:  2017bf->201760:1
+; CS-NEXT:  2017cf->20179e:1
+; CS-NEXT:  2017d8->2017e3:1
+; CS-NEXT: [0x7f4]
+; CS-NEXT:  1
+; CS-NEXT:  2017c4-2017cf:1
+; CS-NEXT:  2
+; CS-NEXT:  2017bf->201760:1
+; CS-NEXT:  2017cf->20179e:1
+; CS-NEXT: [0x7f4 @ 0x7bf]
+; CS-NEXT:  1
+; CS-NEXT:  201760-20177f:1
+; CS-NEXT:  1
+; CS-NEXT:  20177f->2017c4: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 bar(int x, int y) {
+  if (x % 3) {
+    return x - y;
+  }
+  return x + y;
+}
+
+void foo() {
+  int s, i = 0;
+  while (i++ < 4000 * 4000)
+    if (i % 91) s = bar(i, s); else s += 30;
+  printf("sum is %d\n", s);
+}
+
+int main() {
+  foo();
+  return 0;
+}

llvm/tools/llvm-profgen/PerfReader.h

for (size_t I = 0; I < OtherLBRStack.size(); I++) {
       if (LBRStack[I].Source != OtherLBRStack[I].Source ||
           LBRStack[I].Target != OtherLBRStack[I].Target)
         return false;
     }
     return true;
   }
 
 #ifndef NDEBUG
+  uint64_t Linenum = 0;
+
   void print() const {
+    dbgs() << "Line " << Linenum << "\n";
     dbgs() << "LBR stack\n";
     printLBRStack(LBRStack);
     dbgs() << "Call stack\n";
     printCallStack(CallStack);
   }
 #endif
 };
 // After parsing the sample, we record the samples by aggregating them
struct UnwindState {
   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;
+  // Indicate whether unwinding is currently in a bad state which requires to
+  // skip all subsequent unwinding.
+  bool Invalid = false;
   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;
bool validateInitialState() {
     return true;
   }
 
   void checkStateConsistency() {
     assert(InstPtr.Address == CurrentLeafFrame->Address &&
            "IP should align with context leaf");
   }
 
+  void setInvalid() { Invalid = true; }
   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;
public:
   uint64_t NumMissingExternalFrame = 0;
   uint64_t NumMismatchedProEpiBranch = 0;
   uint64_t NumMismatchedExtCallBranch = 0;
 
 private:
   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 Binary->addressIsCall(State.getCurrentLBRSource());
+    return isValidState(State) &&
+           Binary->addressIsCall(State.getCurrentLBRSource());
   }
 
   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;
 
     // 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);
   }
 
+  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);
 
   template <typename T>
   void collectSamplesFromFrame(UnwindState::ProfiledFrame *Cur, T &Stack);
   // Collect each samples on trie node by DFS traversal

llvm/tools/llvm-profgen/PerfReader.cpp

void VirtualUnwinder::unwindCall(UnwindState &State) {
   }
   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;
+  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.
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;
 
   // 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.
       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
+      // Unwind returns - check whether the IP is indeed at a return
+      // instruction
       unwindReturn(State);
-    } else {
+    } else if (isValidState(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.
+      // 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);
+    } else {
+      // Skip unwinding the rest of LBR trace. Reset the stack and update the
+      // state so that the rest of the trace can still be processed as if they
+      // do not have stack samples.
+      State.clearCallStack();
+      State.InstPtr.update(State.getCurrentLBRSource());
+      State.pushFrame(State.InstPtr.Address);
     }
+
     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());
 
   return true;
void HybridPerfReader::parseSample(TraceStream &TraceIt, uint64_t Count) {
   // e.g.
   //            4005dc    # call stack leaf
   //            400634
   //            400684    # call stack root
   // 0x4005c8/0x4005dc/P/-/-/0   0x40062f/0x4005b0/P/-/-/0 ...
   //          ... 0x4005c8/0x4005dc/P/-/-/0    # LBR Entries
   //
   std::shared_ptr<PerfSample> Sample = std::make_shared<PerfSample>();
-
+#ifndef NDEBUG
+  Sample->Linenum = TraceIt.getLineNumber();
+#endif
   // Parsing call stack and populate into PerfSample.CallStack
   if (!extractCallstack(TraceIt, Sample->CallStack)) {
     // Skip the next LBR line matched current call stack
     if (!TraceIt.isAtEoF() && TraceIt.getCurrentLine().startswith(" 0x"))
       TraceIt.advance();
     return;
   }
 
for (const LBREntry &LBR : Sample->LBRStack) {
 
     if (!LBR.IsArtificial && TargetOffset != ExternalAddr) {
       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 (EndOffeset != 0) {
+      if (StartOffset <= EndOffeset)
         Counter.recordRangeCount(StartOffset, EndOffeset, Repeat);
+    }
     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)) {
void PerfScriptReader::warnInvalidRange() {
 
   const char *EndNotBoundaryMsg = "Range is not on instruction boundary, "
                                   "likely due to profile and binary mismatch.";
   const char *DanglingRangeMsg = "Range does not belong to any functions, "
                                  "likely from PLT, .init or .fini section.";
   const char *RangeCrossFuncMsg =
       "Fall through range should not cross function boundaries, likely due to "
       "profile and binary mismatch.";
+  const char *BogusRangeMsg = "Range start is after range end.";
 
+  uint64_t TotalRangeNum = 0;
   uint64_t InstNotBoundary = 0;
   uint64_t UnmatchedRange = 0;
   uint64_t RangeCrossFunc = 0;
+  uint64_t BogusRange = 0;
 
   for (auto &I : Ranges) {
     uint64_t StartOffset = I.first.first;
     uint64_t EndOffset = I.first.second;
+    TotalRangeNum += I.second;
 
     if (!Binary->offsetIsCode(StartOffset) ||
         !Binary->offsetIsTransfer(EndOffset)) {
-      InstNotBoundary++;
+      InstNotBoundary += I.second;
       WarnInvalidRange(StartOffset, EndOffset, EndNotBoundaryMsg);
     }
 
     auto *FRange = Binary->findFuncRangeForOffset(StartOffset);
     if (!FRange) {
-      UnmatchedRange++;
+      UnmatchedRange += I.second;
       WarnInvalidRange(StartOffset, EndOffset, DanglingRangeMsg);
       continue;
     }
 
     if (EndOffset >= FRange->EndOffset) {
-      RangeCrossFunc++;
+      RangeCrossFunc += I.second;
       WarnInvalidRange(StartOffset, EndOffset, RangeCrossFuncMsg);
     }
+
+    if (StartOffset > EndOffset) {
+      BogusRange += I.second;
+      WarnInvalidRange(StartOffset, EndOffset, BogusRangeMsg);
+    }
   }
 
-  uint64_t TotalRangeNum = Ranges.size();
-  emitWarningSummary(InstNotBoundary, TotalRangeNum,
-                     "of profiled ranges are not on instruction boundary.");
-  emitWarningSummary(UnmatchedRange, TotalRangeNum,
-                     "of profiled ranges do not belong to any functions.");
-  emitWarningSummary(RangeCrossFunc, TotalRangeNum,
-                     "of profiled ranges do cross function boundaries.");
+  emitWarningSummary(
+      InstNotBoundary, TotalRangeNum,
+      "of samples are from ranges that are not on instruction boundary.");
+  emitWarningSummary(
+      UnmatchedRange, TotalRangeNum,
+      "of samples are from ranges that do not belong to any functions.");
+  emitWarningSummary(
+      RangeCrossFunc, TotalRangeNum,
+      "of samples are from ranges that do cross function boundaries.");
+  emitWarningSummary(
+      BogusRange, TotalRangeNum,
+      "of samples are from ranges that have range start after range end.");
 }
 
 void PerfScriptReader::parsePerfTraces() {
   // Parse perf traces and do aggregation.
   parseAndAggregateTrace();
 
   emitWarningSummary(NumLeafExternalFrame, NumTotalSample,
                      "of samples have leaf external frame in call stack.");