[llvm-profgen] Warn on invalid range and show warning summary

[wlei]

Summary

Two things in this diff:

1. Warn on the invalid range, currently three types of checking, see the detailed message in the code.

2. In some situation, llvm-profgen gives lots of warnings on the truncated stacks which is noisy. This change provides a switch to --show-detailed-warning to skip the warnings. Alternatively, we use a summary for those warning and show the percentage of cases with those issues.

Example of warning summary.

warning: 0.05%(1120/2428958) cases with issue: Profile context truncated due to missing probe for call instruction.
warning: 0.00%(2/178637) cases with issue: Range does not belong to any functions, likely from external function.

[hoy]

llvm/tools/llvm-profgen/PerfReader.cpp

37

nit: name it `filter-invalid-lbr-ranges" and flip the default value?

[wenlei]

llvm/tools/llvm-profgen/PerfReader.cpp

37

I'm curious in what scenario do we not want to filter out invalid ranges? I feels to me that we don't need a switch here?

1138

The message is a bit unclear. Does this indicate we have a range for functions outside of the binary? We would have caught diassembling error while diassembling?

perhaps this Range does not belong to any functions?

1143

nit, better message: Fall through range should not cross function boundaries

1145

I think there's another case we could detect and warn - that is range start/end is not on instruction boundary. That could happen when perf and binary mismatches. I ran into that couple times.

We could also check stack sample addresses are on instruction boundary for CS profile, and warn about potential mismatch perf profile.

1146

I think you meant to place this loop outside of the inner most loop?

[wlei]

Updating D111902: [llvm-profgen] Warn and filter out invalid range

[hoy]

llvm/tools/llvm-profgen/PerfReader.cpp

447

How about emit summary before the detailed messages?

1043

Make these static fields of PerfScriptReader? static const char* should be fine.

llvm/tools/llvm-profgen/ProfiledBinary.cpp

406

Is this supposed to identify a branch instruction? BranchAddrs may sound easier to understand?

[wlei]

Updating D111902: [llvm-profgen] Warn on invalid range and show warning summary

llvm/tools/llvm-profgen/PerfReader.cpp

447

It seems we need to align with warnInvalidRange where we need to first get the invalid number then emit summary.

1043

Sounds good, thanks!

llvm/tools/llvm-profgen/ProfiledBinary.cpp

406

isTerminator can be branches and return, refer to the comments from isTerminator

/// Returns true if this instruction part of the terminator for
/// a basic block.  Typically this is things like return and branch
/// instructions.
///

Added comments on it.

[hoy]

llvm/tools/llvm-profgen/PerfReader.cpp

447

I see. Makes sense to leave it as is.

llvm/tools/llvm-profgen/ProfiledBinary.cpp

406

I see. Return instructions can also be considered branch instructions in the profile generator. They are basically jumps. We use TerminatorOffsets to check if the last instruction of a range is a jump, right? Terminator sounds a bit formal. Branches or jumps may be more natural to understand. What do you think?

[wlei]

llvm/tools/llvm-profgen/ProfiledBinary.cpp

406

Yeah, this term is a little bit ambiguous. I have the function to check if this is a jump, see below.

bool offsetIsBoundry(uint64_t Offset) {
   return TerminatorOffsets.count(Offset) || CallAddrs.count(Offset);
 }

So Terminator is branch or return but not call. So we should check both Terminator and call here. jump seems including call.

Maybe rename it to BranchOrReturnOffsets?

[hoy]

llvm/tools/llvm-profgen/ProfiledBinary.cpp

406

I see. We already have CallAddrs and RetAddrs, maybe make a BranchAddrs for isTerminator && !isReturn?

[wlei]

Updating D111902: [llvm-profgen] Warn on invalid range and show warning summary

[wlei]

llvm/tools/llvm-profgen/ProfiledBinary.cpp

406

I see, we have the isBranch in MC, we can just use that!

[hoy]

lgtm, thanks.

llvm/tools/llvm-profgen/PerfReader.cpp

1078

nit: no need to use static. Sorry for previous confusion.

[wlei]

address Hongtao's feedback.

[wenlei]

llvm/tools/llvm-profgen/PerfReader.cpp

1038

Suggest we rephrase the message.

warning: 0.05%(1120/2428958) cases with issue: Profile context truncated due to missing probe for call instruction.

->

warning: 0.05% (1120/2428958) of profiled contexts are truncated due to missing probe for call instruction.

warning: 0.00%(2/178637) cases with issue: Range does not belong to any functions, likely from external function.

->

warning: 0.00% (2/178637) of profiled ranges do not belong to any functions.

And specifically for invalid ranges, I thought we filter out external entries already, no? Did you check that they are actually from external functions?

1081–1082

For EndNotBoundaryMsg and RangeCrossFuncMsg, we can hint profile/ binary mismatch: likely due to profile and binary mismatch.

1097

could also check addressIsCode(StartOffset) to make sure start is also on instruction boundary?

1099

"dangling" can be a confusing term. If this is truly external, we can say ExternalRange, or whatever that's more explicit.

llvm/tools/llvm-profgen/ProfiledBinary.h

330

nit: offsetIsTransfer - this would be consistent with others. flow transfer instructions includes call,ret,branch.

[wlei]

addressing Wenlei's feedbacks

[wlei]

llvm/tools/llvm-profgen/PerfReader.cpp

1038

We filter out the address that's not in the ELF text section(false for addressIsCode), I guess we name that the external entry.

Here the two((2/178637)) "external" functions is still inside ELF text section, like the PLT, .init, .fini section. It's also meaningless I think, you see the num is very small.

1097

Seems we call addressIsCode in early time in parseSample, so if that works well, we don't need to call here. But I guess you mean to detect the bugs here. added addressIsCode .

1099

It means it doesn't find/match the function range in ELF, maybe not external, how about UnmatchedRange?

llvm/tools/llvm-profgen/ProfiledBinary.h

330

Fixed, thanks.

[wlei]

fix typo

[wenlei]

lgtm, thanks.

llvm/test/tools/llvm-profgen/cs-invalid-ret-addr.test

 ; REQUIRES: x86_64-linux
-; RUN: llvm-profgen --format=text  --perfscript=%S/Inputs/cs-invalid-ret-addr.perfscript --binary=%S/Inputs/noinline-cs-noprobe.perfbin --output=%t 2>&1 |  FileCheck %s
+; RUN: llvm-profgen --format=text  --perfscript=%S/Inputs/cs-invalid-ret-addr.perfscript --binary=%S/Inputs/noinline-cs-noprobe.perfbin --output=%t --show-detailed-warning 2>&1 |  FileCheck %s
 
 ; CHECK: warning: Truncated stack sample due to invalid return address at 0x400686, likely caused by frame pointer omission

llvm/tools/llvm-profgen/PerfReader.h

protected:
   // Update base address based on mmap events
   void updateBinaryAddress(const MMapEvent &Event);
   // Parse mmap event and update binary address
   void parseMMap2Event(TraceStream &TraceIt);
   // Parse perf events/samples and do aggregation
   void parseAndAggregateTrace();
   // Parse either an MMAP event or a perf sample
   void parseEventOrSample(TraceStream &TraceIt);
+  void emitWarningSummary(uint64_t Num, uint64_t Total, StringRef Msg);
   // Warn if the relevant mmap event is missing.
   void warnIfMissingMMap();
   // Emit accumulate warnings.
   void warnTruncatedStack();
+  // Warn if range is invalid.
+  void warnInvalidRange();
   // Extract call stack from the perf trace lines
   bool extractCallstack(TraceStream &TraceIt,
                         SmallVectorImpl<uint64_t> &CallStack);
   // Extract LBR stack from one perf trace line
   bool extractLBRStack(TraceStream &TraceIt,
                        SmallVectorImpl<LBREntry> &LBRStack);
   uint64_t parseAggregatedCount(TraceStream &TraceIt);
   // Parse one sample from multiple perf lines, override this for different

llvm/tools/llvm-profgen/PerfReader.cpp

static cl::opt<bool>
     UseOffset("use-offset", cl::init(true), cl::ZeroOrMore,
               cl::desc("Work with `--skip-symbolization` or "
                        "`--unsymbolized-profile` to write/read the "
                        "offset instead of virtual address."));
 static cl::opt<bool>
     IgnoreStackSamples("ignore-stack-samples", cl::init(false), cl::ZeroOrMore,
                        cl::desc("Ignore call stack samples for hybrid samples "
                                 "and produce context-insensitive profile."));
+static cl::opt<bool>
+    ShowDetailedWarning("show-detailed-warning", cl::init(false),
+                        cl::ZeroOrMore,
+                        cl::desc("Show detailed warning message."));
 
 extern cl::opt<std::string> PerfTraceFilename;
 extern cl::opt<bool> ShowDisassemblyOnly;
 extern cl::opt<bool> ShowSourceLocations;
 extern cl::opt<std::string> OutputFilename;
 
 namespace llvm {
 namespace sampleprof {
for (const auto &Item : AggregatedSamples) {
     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) {
     for (auto Address : AllUntrackedCallsites)
       WithColor::warning() << "Profile context truncated due to missing probe "
                            << "for call instruction at "
                            << format("0x%" PRIx64, Address) << "\n";
   }
 
+  emitWarningSummary(AllUntrackedCallsites.size(), SampleCounters.size(),
+                     "of profiled contexts are truncated due to missing probe "
+                     "for call instruction.");
+}
+
 bool PerfScriptReader::extractLBRStack(TraceStream &TraceIt,
                                        SmallVectorImpl<LBREntry> &LBRStack) {
   // The raw format of LBR stack is like:
   // 0x4005c8/0x4005dc/P/-/-/0 0x40062f/0x4005b0/P/-/-/0 ...
   //                           ... 0x4005c8/0x4005dc/P/-/-/0
   // It's in FIFO order and seperated by whitespace.
   SmallVector<StringRef, 32> Records;
   TraceIt.getCurrentLine().split(Records, " ", -1, false);
void HybridPerfReader::generateUnsymbolizedProfile() {
   ProfileIsCS = !IgnoreStackSamples;
   if (ProfileIsCS)
     unwindSamples();
   else
     PerfScriptReader::generateUnsymbolizedProfile();
 }
 
 void PerfScriptReader::warnTruncatedStack() {
+  if (ShowDetailedWarning) {
     for (auto Address : InvalidReturnAddresses) {
       WithColor::warning()
           << "Truncated stack sample due to invalid return address at "
           << format("0x%" PRIx64, Address)
           << ", likely caused by frame pointer omission\n";
     }
   }
+  emitWarningSummary(
+      InvalidReturnAddresses.size(), AggregatedSamples.size(),
+      "of truncated stack samples due to invalid return address, "
+      "likely caused by frame pointer omission.");
+}
+
+void PerfScriptReader::emitWarningSummary(uint64_t Num, uint64_t Total,
+                                          StringRef Msg) {
+  if (!Total || !Num)
+    return;
+  WithColor::warning() << format("%.2f", static_cast<double>(Num) * 100 / Total)
+                       << "%(" << Num << "/" << Total << ") " << Msg << "\n";
+}
+
+void PerfScriptReader::warnInvalidRange() {
+  std::unordered_map<std::pair<uint64_t, uint64_t>, uint64_t,
+                     pair_hash<uint64_t, uint64_t>>
+      Ranges;
+
+  for (const auto &Item : AggregatedSamples) {
+    const PerfSample *Sample = Item.first.getPtr();
+    uint64_t Count = Item.second;
+    uint64_t EndOffeset = 0;
+    for (const LBREntry &LBR : Sample->LBRStack) {
+      uint64_t SourceOffset = Binary->virtualAddrToOffset(LBR.Source);
+      uint64_t StartOffset = Binary->virtualAddrToOffset(LBR.Target);
+      if (EndOffeset != 0)
+        Ranges[{StartOffset, EndOffeset}] += Count;
+      EndOffeset = SourceOffset;
+    }
+  }
+
+  if (Ranges.empty()) {
+    WithColor::warning() << "No samples in perf script!\n";
+    return;
+  }
+
+  auto WarnInvalidRange =
+      [&](uint64_t StartOffset, uint64_t EndOffset, StringRef Msg) {
+        if (!ShowDetailedWarning)
+          return;
+        WithColor::warning()
+            << "["
+            << format("%8" PRIx64, Binary->offsetToVirtualAddr(StartOffset))
+            << ","
+            << format("%8" PRIx64, Binary->offsetToVirtualAddr(EndOffset))
+            << "]: " << Msg << "\n";
+      };
+
+  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.";
+
+  uint64_t InstNotBoundary = 0;
+  uint64_t UnmatchedRange = 0;
+  uint64_t RangeCrossFunc = 0;
+
+  for (auto &I : Ranges) {
+    uint64_t StartOffset = I.first.first;
+    uint64_t EndOffset = I.first.second;
+
+    if (!Binary->offsetIsCode(StartOffset) ||
+        !Binary->offsetIsTransfer(EndOffset)) {
+      InstNotBoundary++;
+      WarnInvalidRange(StartOffset, EndOffset, EndNotBoundaryMsg);
+    }
+
+    auto *FRange = Binary->findFuncRangeForOffset(StartOffset);
+    if (!FRange) {
+      UnmatchedRange++;
+      WarnInvalidRange(StartOffset, EndOffset, DanglingRangeMsg);
+      continue;
+    }
+
+    if (EndOffset >= FRange->EndOffset) {
+      RangeCrossFunc++;
+      WarnInvalidRange(StartOffset, EndOffset, RangeCrossFuncMsg);
+    }
+  }
+
+  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.");
+}
 
 void PerfScriptReader::parsePerfTraces() {
   // Parse perf traces and do aggregation.
   parseAndAggregateTrace();
 
   // Generate unsymbolized profile.
   warnTruncatedStack();
+  warnInvalidRange();
   generateUnsymbolizedProfile();
 
   if (SkipSymbolization)
     writeUnsymbolizedProfile(OutputFilename);
 }
 
 } // end namespace sampleprof
 } // end namespace llvm

llvm/tools/llvm-profgen/ProfiledBinary.h

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> CallAddrs;
+  std::unordered_set<uint64_t> CallOffsets;
   // A set of return instruction offsets. Used by virtual unwinding.
-  std::unordered_set<uint64_t> RetAddrs;
+  std::unordered_set<uint64_t> RetOffsets;
+  // 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.
public:
   uint64_t getTextSegmentOffset() const { return TextSegmentOffsets[0]; }
   const std::vector<uint64_t> &getPreferredTextSegmentAddresses() const {
     return PreferredTextSegmentAddresses;
   }
   const std::vector<uint64_t> &getTextSegmentOffsets() const {
     return TextSegmentOffsets;
   }
 
+  bool offsetIsCode(uint64_t Offset) const {
+    return Offset2InstSizeMap.find(Offset) != Offset2InstSizeMap.end();
+  }
   bool addressIsCode(uint64_t Address) const {
     uint64_t Offset = virtualAddrToOffset(Address);
-    return Offset2InstSizeMap.find(Offset) != Offset2InstSizeMap.end();
+    return offsetIsCode(Offset);
   }
   bool addressIsCall(uint64_t Address) const {
     uint64_t Offset = virtualAddrToOffset(Address);
-    return CallAddrs.count(Offset);
+    return CallOffsets.count(Offset);
   }
   bool addressIsReturn(uint64_t Address) const {
     uint64_t Offset = virtualAddrToOffset(Address);
-    return RetAddrs.count(Offset);
+    return RetOffsets.count(Offset);
   }
   bool addressInPrologEpilog(uint64_t Address) const {
     uint64_t Offset = virtualAddrToOffset(Address);
     return ProEpilogTracker.PrologEpilogSet.count(Offset);
   }
 
+  bool offsetIsTransfer(uint64_t Offset) {
+    return BranchOffsets.count(Offset) || RetOffsets.count(Offset) ||
+           CallOffsets.count(Offset);
+  }
+
   uint64_t getAddressforIndex(uint64_t Index) const {
     return offsetToVirtualAddr(CodeAddrOffsets[Index]);
   }
 
   bool usePseudoProbes() const { return UsePseudoProbes; }
   // 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

llvm/tools/llvm-profgen/ProfiledBinary.cpp

void ProfiledBinary::load() {
   disassemble(Obj);
 
   // Track size for optimized inlinees when probe is available
   if (UsePseudoProbes && TrackFuncContextSize)
     FuncSizeTracker.trackInlineesOptimizedAway(ProbeDecoder);
 
   // Use function start and return address to infer prolog and epilog
   ProEpilogTracker.inferPrologOffsets(StartOffset2FuncRangeMap);
-  ProEpilogTracker.inferEpilogOffsets(RetAddrs);
+  ProEpilogTracker.inferEpilogOffsets(RetOffsets);
 
   // TODO: decode other sections.
 }
 
 bool ProfiledBinary::inlineContextEqual(uint64_t Address1, uint64_t Address2) {
   uint64_t Offset1 = virtualAddrToOffset(Address1);
   uint64_t Offset2 = virtualAddrToOffset(Address2);
   const SampleContextFrameVector &Context1 = getFrameLocationStack(Offset1);
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())
-        CallAddrs.insert(Offset);
+        CallOffsets.insert(Offset);
       else if (MCDesc.isReturn())
-        RetAddrs.insert(Offset);
+        RetOffsets.insert(Offset);
+      else if (MCDesc.isBranch())
+        BranchOffsets.insert(Offset);
 
       if (InvalidInstLength) {
         WarnInvalidInsts(Offset - InvalidInstLength, Offset - 1);
         InvalidInstLength = 0;
       }
     } else {
       InvalidInstLength += Size;
     }
 
     Offset += Size;