[llvm-profgen] Filter out oversized LBR ranges.

[wlei]

Summary

As a follow up to D123271: [llvm-profgen] Filter out invalid LBR ranges., LBR ranges that are too big should also be considered as invalid.

For example, the last two pairs in the following trace form a range [0x0d7b02b0, 0x368ba706] that covers a ton of functions in the binary. Such oversized range should also be ignored.

0x0c74505f/0x368b99a0 **0x368ba706**/0x0c745040  0x0d7b1c3f/**0x0d7b02b0**

Add a defensive check to filter out those ranges based that the valid range should not cross the unconditional branch(Call, return, unconditional jmp).

[wenlei]

llvm/tools/llvm-profgen/PerfReader.h

213

nit: isValidLBRRange->isValidFallThroughRange.

llvm/tools/llvm-profgen/ProfiledBinary.h

99–105

I think we can skip the max func size check for simplicity. 99%+ ranges will go through uncond branch check still, so this extra complexity doesn't seem worth it.

243

How about keep CodeAddrOffsets and CallOffsets as unordered_set so other queries are still O(1), but have additional UncondBranchOffsets as set that contains all calls and rets. This also avoids querying multiple containers for isValidLBRRange. The size overhead should be small.

[wlei]

addressing Wenlei's feedback

tweak the test case

[wenlei]

lgtm, thanks.

[hoy]

llvm/tools/llvm-profgen/ProfiledBinary.h

404

upper_bound seems to find the first element that is greater than Start. How about element equals to Start?

[wlei]

llvm/tools/llvm-profgen/ProfiledBinary.h

404

So you mean it will immediately jump when ip is on the Start's address, then it should be lower_bound?

[hoy]

llvm/tools/llvm-profgen/ProfiledBinary.h

404

Yeah, lower_bound finds the first element that is not less than Start. It should be fine.

[wlei]

llvm/tools/llvm-profgen/ProfiledBinary.h

404

Yeah, that sounds reasonable. The Start is actually the LBR's Target, IMO, the Target should not be an unconditional jmp. I will run on our service to see if we have this case.

[wlei]

llvm/tools/llvm-profgen/ProfiledBinary.h

404

Okay.. This indeed happened and it's the HW bug. it can be a function the first inst is a JMP or a JMP follow a call

func:
xxxx : JMP
`

Fixed to lower_bound
Thanks!

[wlei]

upper_bound to lower_bound

[hoy]

llvm/tools/llvm-profgen/ProfiledBinary.h

404

Thanks for verifying that. Surprised to see it was really hit. I was thinking it'd mostly happen in theory.

[wenlei]

llvm/tools/llvm-profgen/ProfiledBinary.h

404

Target, IMO, the Target should not be an unconditional jmp.

jmp->jmp should be valid execution sequence..

[wlei]

llvm/tools/llvm-profgen/ProfiledBinary.h

404

Got it, thanks! No big profile changes(profile similarity: 100.000%) comparing to upper_bound, because almost all those large bogus ranges not only cross one unconditional JMP.

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.
+
+
+            20179e
+            2017f9
+      7f83e84e7793
+  5541f689495641d7
+ 0x2017cf/0x20179e/P/-/-/0  0x2017cf/0x20179e/P/-/-/0  0x20177f/0x2017c4/P/-/-/0  0x2017bf/0x201760/P/-/-/0  0x2017cf/0x20179e/P/-/-/0  0x20177f/0x2017c4/P/-/-/0  0x2017bf/0x201760/P/-/-/0  0x2017cf/0x20179e/P/-/-/0  0x20177f/0x2017c4/P/-/-/0  0x2017bf/0x201760/P/-/-/0  0x2017cf/0x20179e/P/-/-/0  0x20177f/0x2017c4/P/-/-/0  0x2017bf/0x201760/P/-/-/0  0x2017cf/0x20179e/P/-/-/0  0x20177f/0x2017c4/P/-/-/0  0x2017bf/0x201760/P/-/-/0
+
+// Duplicated LBR entries "0x2017cf/0x20179e/P/-/-/0  0x2017cf/0x20179e/P/-/-/0", the range [0x20179e, 0x2017cf] is cross unconditional jmp, 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: 4
+; NOCS-NEXT: 201760-20177f:7
+; NOCS-NEXT: 20179e-2017bf:5
+; NOCS-NEXT: 2017c4-2017cf:6
 ; 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: 20177f->2017c4:7
+; NOCS-NEXT: 2017bf->201760:7
+; NOCS-NEXT: 2017cf->20179e:8
 ; 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:   4
+; CS-NEXT:   201760-20177f:6
+; CS-NEXT:   20179e-2017bf:5
+; CS-NEXT:   2017c4-2017cf:5
+; CS-NEXT:   2017c4-2017d8:1
+; CS-NEXT:   4
+; CS-NEXT:   20177f->2017c4:6
+; CS-NEXT:   2017bf->201760:6
+; CS-NEXT:   2017cf->20179e:6
+; 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:   1
+; CS-NEXT:   2017c4-2017cf:1
+; CS-NEXT:   2
+; CS-NEXT:   2017bf->201760:1
+; CS-NEXT:   2017cf->20179e:2
 ; CS-NEXT: [0x7f4 @ 0x7bf]
-; CS-NEXT:  1
-; CS-NEXT:  201760-20177f:1
-; CS-NEXT:  1
-; CS-NEXT:  20177f->2017c4:1
+; CS-NEXT:   1
+; CS-NEXT:   201760-20177f:1
+; CS-NEXT:   1
+; CS-NEXT:   20177f->2017c4:1
 
 ; clang -O3 -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) {

llvm/tools/llvm-profgen/PerfReader.h

 // 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>;
 
+inline bool isValidFallThroughRange(uint64_t Start, uint64_t End,
+                                    ProfiledBinary *Binary) {
+  // Start bigger than End is considered invalid.
+  // LBR ranges cross the unconditional jmp are also assumed invalid.
+  // It's found that perf data may contain duplicate LBR entries that could form
+  // a range that does not reflect real execution flow on some Intel targets,
+  // e.g. Skylake. Such ranges are ususally very long. Exclude them since there
+  // cannot be a linear execution range that spans over unconditional jmp.
+  return Start <= End && !Binary->rangeCrossUncondBranch(Start, End);
+}
+
 // 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 {

llvm/tools/llvm-profgen/PerfReader.cpp

if (End == ExternalAddr || Target == ExternalAddr) {
     // traces contains a standalone external address failing to pair another
     // one, likely due to interrupt jmp or broken perf script. Set the
     // state to invalid.
     NumUnpairedExtAddr++;
     State.setInvalid();
     return;
   }
 
-  if (Target > End) {
+  if (!isValidFallThroughRange(Binary->virtualAddrToOffset(Target),
+                               Binary->virtualAddrToOffset(End), Binary)) {
     // 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.
while (Index < Records.size()) {
     if (!SrcIsInternal)
       Src = ExternalAddr;
     if (!DstIsInternal)
       Dst = ExternalAddr;
     // Filter external-to-external case to reduce LBR trace size.
     if (!SrcIsInternal && !DstIsInternal)
       continue;
 
-    // TODO: filter out buggy duplicate branches on Skylake
     LBRStack.emplace_back(LBREntry(Src, Dst));
   }
   TraceIt.advance();
   return !LBRStack.empty();
 }
 
 bool PerfScriptReader::extractCallstack(TraceStream &TraceIt,
                                         SmallVectorImpl<uint64_t> &CallStack) {
for (const LBREntry &LBR : Sample->LBRStack) {
     if (Binary->offsetIsCode(TargetOffset)) {
       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 (Binary->offsetIsCode(StartOffset) && Binary->offsetIsCode(EndOffeset) &&
-        StartOffset <= EndOffeset)
+        isValidFallThroughRange(StartOffset, EndOffeset, Binary))
       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
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.";
+  const char *BogusRangeMsg = "Range start is after or too far from 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) {
if (!FRange) {
       continue;
     }
 
     if (EndOffset >= FRange->EndOffset) {
       RangeCrossFunc += I.second;
       WarnInvalidRange(StartOffset, EndOffset, RangeCrossFuncMsg);
     }
 
-    if (StartOffset > EndOffset) {
+    if (!isValidFallThroughRange(StartOffset, EndOffset, Binary)) {
       BogusRange += I.second;
       WarnInvalidRange(StartOffset, EndOffset, BogusRangeMsg);
     }
   }
 
   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.");
+      "of samples are from ranges that have range start after or too far from "
+      "range end acrossing the unconditinal jmp.");
 }
 
 void PerfScriptReader::parsePerfTraces() {
   // Parse perf traces and do aggregation.
   parseAndAggregateTrace();
 
   emitWarningSummary(NumLeafExternalFrame, NumTotalSample,
                      "of samples have leaf external frame in call stack.");

llvm/tools/llvm-profgen/ProfiledBinary.h

struct BinaryFunction {
   uint64_t getFuncSize() {
     uint64_t Sum = 0;
     for (auto &R : Ranges) {
       Sum += R.second - R.first;
     }
     return Sum;
   }
 };
 
 // Info about function range. A function can be split into multiple
 // non-continuous ranges, each range corresponds to one FuncRange.
 struct FuncRange {
   uint64_t StartOffset;
   // EndOffset is an exclusive bound.
   uint64_t EndOffset;
   // Function the range belongs to
   BinaryFunction *Func;
   // Whether the start offset is the real entry of the function.
   bool IsFuncEntry = false;
 
   StringRef getFuncName() { return Func->FuncName; }
 };
 
class ProfiledBinary {
 
   // An array of offsets of all instructions sorted in increasing order. The
   // sorting is needed to fast advance to the next forward/backward instruction.
   std::vector<uint64_t> CodeAddrOffsets;
   // A set of call instruction offsets. Used by virtual unwinding.
   std::unordered_set<uint64_t> CallOffsets;
   // A set of return instruction offsets. Used by virtual unwinding.
   std::unordered_set<uint64_t> RetOffsets;
+  // An ordered set of unconditional branch instruction offsets.
+  std::set<uint64_t> UncondBranchOffsets;
   // A set of branch instruction offsets.
   std::unordered_set<uint64_t> BranchOffsets;
 
   // Estimate and track function prolog and epilog ranges.
   PrologEpilogTracker ProEpilogTracker;
 
   // Track function sizes under different context
   BinarySizeContextTracker FuncSizeTracker;
bool addressInPrologEpilog(uint64_t Address) const {
     return ProEpilogTracker.PrologEpilogSet.count(Offset);
   }
 
   bool offsetIsTransfer(uint64_t Offset) {
     return BranchOffsets.count(Offset) || RetOffsets.count(Offset) ||
            CallOffsets.count(Offset);
   }
 
+  bool rangeCrossUncondBranch(uint64_t Start, uint64_t End) {
+    if (Start >= End)
+      return false;
+    auto R = UncondBranchOffsets.lower_bound(Start);
+    return R != UncondBranchOffsets.end() && *R < End;
+  }
+
   uint64_t getAddressforIndex(uint64_t Index) const {
     return offsetToVirtualAddr(CodeAddrOffsets[Index]);
   }
 
   size_t getCodeOffsetsSize() const { return CodeAddrOffsets.size(); }
 
   bool usePseudoProbes() const { return UsePseudoProbes; }
   bool useFSDiscriminator() const { return UseFSDiscriminator; }

llvm/tools/llvm-profgen/ProfiledBinary.cpp

while (Offset < NextStartOffset) {
     if (Disassembled) {
       const MCInstrDesc &MCDesc = MII->get(Inst.getOpcode());
 
       // Record instruction size.
       Offset2InstSizeMap[Offset] = Size;
 
       // Populate address maps.
       CodeAddrOffsets.push_back(Offset);
-      if (MCDesc.isCall())
+      if (MCDesc.isCall()) {
         CallOffsets.insert(Offset);
-      else if (MCDesc.isReturn())
+        UncondBranchOffsets.insert(Offset);
+      } else if (MCDesc.isReturn()) {
         RetOffsets.insert(Offset);
-      else if (MCDesc.isBranch())
+        UncondBranchOffsets.insert(Offset);
+      } else if (MCDesc.isBranch()) {
+        if (MCDesc.isUnconditionalBranch())
+          UncondBranchOffsets.insert(Offset);
         BranchOffsets.insert(Offset);
+      }
 
       if (InvalidInstLength) {
         WarnInvalidInsts(Offset - InvalidInstLength, Offset - 1);
         InvalidInstLength = 0;
       }
     } else {
       InvalidInstLength += Size;
     }