[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

100–106

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.

252

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

416

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

416

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

416

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

[wlei]

llvm/tools/llvm-profgen/ProfiledBinary.h

416

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

416

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

416

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

416

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

jmp->jmp should be valid execution sequence..

[wlei]

llvm/tools/llvm-profgen/ProfiledBinary.h

416

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  0x20177f/0x2017c4/P/-/-/0  0x20188c/0x201760/P/-/-/0  0x2017d8/0x2017e3/P/-/-/0  0x20177f/0x2017c4/P/-/-/0  0x2017bf/0x201760/P/-/-/0  0x2017cf/0x20179e/P/-/-/0
+
+
+// The consecutive pairs 20188c/0x201760 and 0x2017d8/0x2017e3 form an oversized execution range [0x2017e3, 0x20188c] that is greater than the largest function range, 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
+; NOCS-NEXT: 201760-20177f:4
+; NOCS-NEXT: 20179e-2017bf:2
+; NOCS-NEXT: 2017c4-2017cf:2
+; NOCS-NEXT: 2017c4-2017d8:2
+; NOCS-NEXT: 5
+; NOCS-NEXT: 20177f->2017c4:4
+; NOCS-NEXT: 2017bf->201760:3
+; NOCS-NEXT: 2017cf->20179e:4
+; NOCS-NEXT: 2017d8->2017e3:2
+; NOCS-NEXT: 20188c->201760:1
 
 
 ; CS:      []
 ; CS-NEXT:  3
-; CS-NEXT:  201760-20177f:1
-; CS-NEXT:  20179e-2017bf:1
-; CS-NEXT:  2017c4-2017d8:1
+; CS-NEXT:  201760-20177f:2
+; CS-NEXT:  20179e-2017bf:2
+; CS-NEXT:  2017c4-2017d8:2
 ; 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:  20177f->2017c4:2
+; CS-NEXT:  2017bf->201760:2
+; CS-NEXT:  2017cf->20179e:2
+; CS-NEXT:  2017d8->2017e3:2
 ; CS-NEXT: [0x7f4]
 ; CS-NEXT:  1
-; CS-NEXT:  2017c4-2017cf:1
+; CS-NEXT:  2017c4-2017cf:2
 ; CS-NEXT:  2
 ; CS-NEXT:  2017bf->201760:1
-; CS-NEXT:  2017cf->20179e: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:  201760-20177f:2
+; CS-NEXT:  2
+; CS-NEXT:  20177f->2017c4:2
+; CS-NEXT:  20188c->201760: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 isValidLBRRange(uint64_t Start, uint64_t End,
+                            ProfiledBinary *Binary) {
+  // 1) Start bigger than End is considered invalid.
+  // 2) LBR ranges longer than the largest function range are assumed invalid.
+  // 3) LBR ranges cross the unconditional jmp are 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. Since there
+  // cannot be a linear execution range that spans over multiple funtion ranges
+  // and unconditional jmp. Exclude them when they are larger than the max
+  // function size or cross the unconditional jmp.
+  return Start <= End && End - Start <= Binary->getMaxFuncRangeSize() &&
+         !Binary->rangeCrossCall(Start, End) &&
+         !Binary->rangeCrossReturn(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 (!isValidLBRRange(Target, 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)
+        isValidLBRRange(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 (!isValidLBRRange(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.");
+  emitWarningSummary(BogusRange, TotalRangeNum,
+                     "of samples are from ranges that have range start after "
+                     "or too far from range end.");
 }
 
 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

 #include "llvm/MC/MCRegisterInfo.h"
 #include "llvm/MC/MCSubtargetInfo.h"
 #include "llvm/MC/MCTargetOptions.h"
 #include "llvm/Object/ELFObjectFile.h"
 #include "llvm/ProfileData/SampleProf.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Transforms/IPO/SampleContextTracker.h"
+#include <algorithm>
 #include <list>
 #include <map>
 #include <set>
 #include <sstream>
 #include <string>
 #include <unordered_map>
 #include <unordered_set>
 #include <vector>
struct BinaryFunction {
 
   uint64_t getFuncSize() {
     uint64_t Sum = 0;
     for (auto &R : Ranges) {
       Sum += R.second - R.first;
     }
     return Sum;
   }
+
+  uint64_t getMaxFuncRangeSize() {
+    uint64_t Size = 0;
+    for (auto &R : Ranges) {
+      Size = std::max(Size, R.second - R.first);
+    }
+    return Size;
+  }
 };
 
 // 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;
for (auto I : FuncStartOffsetMap) {
       InstructionPointer IP(Binary, I.first);
       if (!IP.advance())
         break;
       PrologEpilogSet.insert(IP.Offset);
     }
   }
 
   // Take the last two addresses before the return address as epilog
-  void inferEpilogOffsets(std::unordered_set<uint64_t> &RetAddrs) {
+  void inferEpilogOffsets(std::set<uint64_t> &RetAddrs) {
     for (auto Addr : RetAddrs) {
       PrologEpilogSet.insert(Addr);
       InstructionPointer IP(Binary, Addr);
       if (!IP.backward())
         break;
       PrologEpilogSet.insert(IP.Offset);
     }
   }
class ProfiledBinary {
 
   // Offset to instruction size map. Also used for quick offset lookup.
   std::unordered_map<uint64_t, uint64_t> Offset2InstSizeMap;
 
   // 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;
+  std::set<uint64_t> CallOffsets;
   // A set of return instruction offsets. Used by virtual unwinding.
-  std::unordered_set<uint64_t> RetOffsets;
+  std::set<uint64_t> RetOffsets;
+  // A 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;
 
   // The symbolizer used to get inline context for an instruction.
   std::unique_ptr<symbolize::LLVMSymbolizer> Symbolizer;
 
   // String table owning function name strings created from the symbolizer.
   std::unordered_set<std::string> NameStrings;
 
   // A collection of functions to print disassembly for.
   StringSet<> DisassembleFunctionSet;
 
   // Pseudo probe decoder
   MCPseudoProbeDecoder ProbeDecoder;
 
   // Function name to probe frame map for top-level outlined functions.
   StringMap<MCDecodedPseudoProbeInlineTree *> TopLevelProbeFrameMap;
 
+  // The size of largest binary function range.
+  uint64_t MaxFuncRangeSize = 0;
+
   bool UsePseudoProbes = false;
 
   bool UseFSDiscriminator = false;
 
   // Whether we need to symbolize all instructions to get function context size.
   bool TrackFuncContextSize = false;
 
   // Indicate if the base loading address is parsed from the mmap event or uses
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 rangeCrossCall(uint64_t Start, uint64_t End) {
+    if (Start >= End)
+      return false;
+    auto R = CallOffsets.upper_bound(Start);
+    return R != CallOffsets.end() && *R < End;
+  }
+
+  bool rangeCrossReturn(uint64_t Start, uint64_t End) {
+    if (Start >= End)
+      return false;
+    auto R = RetOffsets.upper_bound(Start);
+    return R != RetOffsets.end() && *R < End;
+  }
+
+  bool rangeCrossUncondBranch(uint64_t Start, uint64_t End) {
+    if (Start >= End)
+      return false;
+    auto R = UncondBranchOffsets.upper_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(); }
+  uint64_t getMaxFuncRangeSize() const { return MaxFuncRangeSize; }
 
   bool usePseudoProbes() const { return UsePseudoProbes; }
   bool useFSDiscriminator() const { return UseFSDiscriminator; }
   // Get the index in CodeAddrOffsets for the address
   // As we might get an address which is not the code
   // here it would round to the next valid code address by
   // using lower bound operation
   uint32_t getIndexForOffset(uint64_t Offset) const {

llvm/tools/llvm-profgen/ProfiledBinary.cpp

 #include "llvm/ADT/Triple.h"
 #include "llvm/DebugInfo/Symbolize/SymbolizableModule.h"
 #include "llvm/Demangle/Demangle.h"
 #include "llvm/IR/DebugInfoMetadata.h"
 #include "llvm/MC/TargetRegistry.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Format.h"
 #include "llvm/Support/TargetSelect.h"
+#include <algorithm>
 
 #define DEBUG_TYPE "load-binary"
 
 using namespace llvm;
 using namespace sampleprof;
 
 cl::opt<bool> ShowDisassemblyOnly("show-disassembly-only", cl::init(false),
                                   cl::ZeroOrMore,
void ProfiledBinary::load() {
   if (!DebugBinaryPath.empty()) {
     OwningBinary<Binary> DebugPath =
         unwrapOrError(createBinary(DebugBinaryPath), DebugBinaryPath);
     loadSymbolsFromDWARF(*cast<ObjectFile>(DebugPath.getBinary()));
   } else {
     loadSymbolsFromDWARF(*cast<ObjectFile>(&ExeBinary));
   }
 
+  // Compute the size of largest binary function range, which will be used
+  // to filter out invalid lbr ranges.
+  for (auto &F : BinaryFunctions)
+    MaxFuncRangeSize =
+        std::max(MaxFuncRangeSize, F.second.getMaxFuncRangeSize());
+
   // Disassemble the text sections.
   disassemble(Obj);
 
   // Use function start and return address to infer prolog and epilog
   ProEpilogTracker.inferPrologOffsets(StartOffset2FuncRangeMap);
   ProEpilogTracker.inferEpilogOffsets(RetOffsets);
 
   warnNoFuncEntry();
if (Disassembled) {
       Offset2InstSizeMap[Offset] = Size;
 
       // Populate address maps.
       CodeAddrOffsets.push_back(Offset);
       if (MCDesc.isCall())
         CallOffsets.insert(Offset);
       else if (MCDesc.isReturn())
         RetOffsets.insert(Offset);
-      else if (MCDesc.isBranch())
+      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;
     }