[llvm-profgen] Filter out oversized LBR ranges.

[hoy]

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**

I'm using the size of the largest binary function range to define an oversized range, since there cannot be a linear execution range that spans over multiple function ranges.

[wenlei]

llvm/tools/llvm-profgen/PerfReader.h

218

While it has value to have such defensive checks in the tool, I'm wondering what has caused such bad input.

The range check seems hacky. If we have to go with it, we at least need some explanation why it's needed, and call out in comment that this is a workaround.

[hoy]

We don't seem to need this change at this point.

[hoy]

Updating D123361: [llvm-profgen] Filter out oversized LBR ranges.

[hoy]

Replaced by D125448: [llvm-profgen] Filter out oversized LBR ranges..

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) {
+  // Start bigger than End is considered invalid.
+  // LBR ranges longer than the largest function range 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. To exclude them, the size
+  // of the largest binary function range is used as the threshold, since there
+  // cannot be a linear execution range that spans over multiple funtion ranges.
+  return Start <= End && End - Start <= Binary->getMaxFuncRangeSize();
+}
+
 // 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;
class ProfiledBinary {
   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
return BranchOffsets.count(Offset) || RetOffsets.count(Offset) ||
            CallOffsets.count(Offset);
   }
 
   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();