[CSSPGO][llvm-profgen] Filter out the instructions without location info for symbolizer

[wlei]

Summary

It appears some instructions doesn't have the debug location info and the symbolizer will return an empty call stack for them which will cause some crash later in profile unwinding. Actually we do not record the sample info for them, so this change just filter out those instruction.

As those instruction would appears at the begin and end of the instruction list, without them we need to add the boundary check for IP advance and backward.

Also for pseudo probe based profile, we actually don't need the symbolized location info, so here just change to use an empty stack for it. This could save half of the binary loading time.

[wenlei]

symbolizer will return an empty call stack for them which will cause some crash later in profile unwinding.

Can you share more details on what which part had trouble dealing with such cases?

llvm/tools/llvm-profgen/PerfReader.cpp

64

Since all code addresses for the entire binary is record in a single vector, this HasNext check is only going to help for the first/last instruction of the entire binary.

Is the problem you're seeing very specific to first/last instruction of the entire binary? I thought instruction without location could happen anywhere..

llvm/tools/llvm-profgen/ProfiledBinary.cpp

458

What about still advancing the index before returning false? I.e. advancing IP past last instruction should leave IP in invalid state - this might help expose issues where return value from advance is not checked, otherwise we might be slightly accessing last instruction repeatedly. We could also set address to UINT_MAX for such case, so extra check may be avoided. Same for backward, but UINT_MIN for address.

llvm/tools/llvm-profgen/ProfiledBinary.h

190

nit: getNumInstructions or getNumCodeAddresses ?

[hoy]

llvm/tools/llvm-profgen/PerfReader.cpp

64

Yeah, empty inline context should not be uncommon. Is the case where IP.backward() resulted in an invalid IP that crashed the inlineContextEqual check?

[wlei]

In D96434#2555468, @wenlei wrote:

symbolizer will return an empty call stack for them which will cause some crash later in profile unwinding.

Can you share more details on what which part had trouble dealing with such cases?

Sure, it's the case with the inlineContextEqual(as we are discussing in the comments below), if the locationStack is empty, the equal function will crash. After I filter out all the instruction without location, then I got the out-of-boundary crash. so that's why I also need to fix advance and backward.

In our internal prototype, it gives all the instruction without location info a fake location, like <function_name, -1>, -1 is the location line number.
here for profgen's symbolizer, it only gives an empty stack.

llvm/tools/llvm-profgen/PerfReader.cpp

64

this HasNext check is only going to help for the first/last instruction of the entire binary.
IP.backward() resulted in an invalid IP that crashed the inlineContextEqual check

Exactly, you both are right.

Is the problem you're seeing very specific to first/last instruction of the entire binary? I thought instruction without location could happen anywhere..

Yes, it could happen anywhere. if the instruction without location is not the first/ last instruction, it will jump to the next valid address which also get false for inlineContextEqual, it's fine for that. Only the first/last one, it will be out of boundary.

For our internal tool, it use a fake location, like <function_name, -1> which can ensure inlineContextEqual always return false. and I also saw the first/last instruction is always a fake location, so there is no out of boundary issue for it.

An alternative to fix this is to do the same as our internal one, for all the empty location stack, we create a fake location, say <invalid, -1>, then I guess we don't need to check the boundary for advance and backward (theoretically we should also check but we didn't see the case first/last insn isn't a fake location for our internal tool). One trade-off is it could sightly increase the memory usage.

Any thoughts on this?

llvm/tools/llvm-profgen/ProfiledBinary.cpp

458

Good suggestion! met the repeating instruction issue..

Will make the out of boundary address to UINT_MIN/UINT_MAX.

llvm/tools/llvm-profgen/ProfiledBinary.h

190

Good catch!

[hoy]

llvm/tools/llvm-profgen/PerfReader.cpp

64

Thanks for the explanation. Can this out-of-range issue be fixed by making inlineContextEqual always return false for empty stacks? Tweaking inlineContextEqual so that no special care to out-of-bound IP sound cleaner to me.

[wlei]

address Hongtao's feedback

[wlei]

llvm/tools/llvm-profgen/PerfReader.cpp

64

Good point! I forgot it also needs to change getInlineLeafFrameLoc and getExpandedContextStr for the empty location stack check.

Submitted the latest diff for the tweaking, ran them on the SPEC, it all passed!

[hoy]

llvm/tools/llvm-profgen/PerfReader.cpp

64

Thanks for the refactoring. Looks a lot cleaner now.

98

Can we not return null here and instead just check if the return value has empty string below?

llvm/tools/llvm-profgen/ProfiledBinary.cpp

158

Add comment for this? An instruction without a valid debug line will be ignored by sample processing.

[wlei]

llvm/tools/llvm-profgen/PerfReader.cpp

98

This is a polymorphism function, for the callee the base class's not straightforward to get the Context string value. Or make a virtual function isEmpty for them?

llvm/tools/llvm-profgen/ProfiledBinary.cpp

158

Good catch!

[hoy]

llvm/tools/llvm-profgen/PerfReader.cpp

98

I see. It's fine to leave it as is. A virtual method adds additional cost. A null key can be used to identify bad line numbers.

[wlei]

address Hongtao's feedback: added comments

Also fix a bug with total value, it should also accumulate the count even for a invalid debug line

[wlei]

llvm/test/tools/llvm-profgen/inline-cs-noprobe.test

4 ↗

(On Diff #323360)

Note for reviewers, this is due to the total value computation change, fix bugs to use SUM of count instead of MAX.

[wenlei]

llvm/tools/llvm-profgen/ProfiledBinary.cpp

160

nit: return std::string()

llvm/tools/llvm-profgen/ProfiledBinary.h

237

do we still need NameOnly parameter?

[wlei]

Address Wenlei's feedback and fix lint

[wenlei]

thanks, lgtm.

llvm/tools/llvm-profgen/PerfReader.cpp

if (Binary->usePseudoProbes()) {
     // probes. The range will be simply recorded here and will be
     // converted to a list of pseudo probes to report in ProfileGenerator.
     State.getParentFrame()->recordRangeCount(Target, End, Repeat);
   } else {
     // Unwind linear execution part
     uint64_t LeafAddr = State.CurrentLeafFrame->Address;
     while (IP.Address >= Target) {
       uint64_t PrevIP = IP.Address;
       IP.backward();
       // Break into segments for implicit call/return due to inlining
       bool SameInlinee = Binary->inlineContextEqual(PrevIP, IP.Address);
       if (!SameInlinee || PrevIP == Target) {
         State.switchToFrame(LeafAddr);
         State.CurrentLeafFrame->recordRangeCount(PrevIP, End, Repeat);
         End = IP.Address;
       }
       LeafAddr = IP.Address;
void VirtualUnwinder::unwindBranchWithinFrame(UnwindState &State) {
   State.switchToFrame(Source);
   State.InstPtr.update(Source);
 }
 
 std::shared_ptr<StringBasedCtxKey> FrameStack::getContextKey() {
   std::shared_ptr<StringBasedCtxKey> KeyStr =
       std::make_shared<StringBasedCtxKey>();
   KeyStr->Context = Binary->getExpandedContextStr(Stack);
+  if (KeyStr->Context.empty())
+    return nullptr;
   KeyStr->genHashCode();
   return KeyStr;
 }
 
 std::shared_ptr<ProbeBasedCtxKey> ProbeStack::getContextKey() {
   std::shared_ptr<ProbeBasedCtxKey> ProbeBasedKey =
       std::make_shared<ProbeBasedCtxKey>();
   for (auto CallProbe : Stack) {
     ProbeBasedKey->Probes.emplace_back(CallProbe);
   }
   CSProfileGenerator::compressRecursionContext<const PseudoProbe *>(
       ProbeBasedKey->Probes);
   ProbeBasedKey->genHashCode();
   return ProbeBasedKey;
 }
 
 template <typename T>
 void VirtualUnwinder::collectSamplesFromFrame(UnwindState::ProfiledFrame *Cur,
                                               T &Stack) {
   if (Cur->RangeSamples.empty() && Cur->BranchSamples.empty())
     return;
 
   std::shared_ptr<ContextKey> Key = Stack.getContextKey();
+  if (Key == nullptr)
+    return;
   auto Ret = CtxCounterMap->emplace(Hashable<ContextKey>(Key), SampleCounter());
   SampleCounter &SCounter = Ret.first->second;
   for (auto &Item : Cur->RangeSamples) {
     uint64_t StartOffset = Binary->virtualAddrToOffset(std::get<0>(Item));
     uint64_t EndOffset = Binary->virtualAddrToOffset(std::get<1>(Item));
     SCounter.recordRangeCount(StartOffset, EndOffset, std::get<2>(Item));
   }
 

llvm/tools/llvm-profgen/ProfileGenerator.cpp

for (auto Range : Ranges) {
     // Disjoint ranges may have range in the middle of two instr,
     // e.g. If Instr1 at Addr1, and Instr2 at Addr2, disjoint range
     // can be Addr1+1 to Addr2-1. We should ignore such range.
     if (IP.Address > RangeEnd)
       continue;
 
     while (IP.Address <= RangeEnd) {
       uint64_t Offset = Binary->virtualAddrToOffset(IP.Address);
-      const FrameLocation &LeafLoc = Binary->getInlineLeafFrameLoc(Offset);
+      auto LeafLoc = Binary->getInlineLeafFrameLoc(Offset);
+      if (LeafLoc.hasValue()) {
         // Recording body sample for this specific context
-      updateBodySamplesforFunctionProfile(FunctionProfile, LeafLoc, Count);
+        updateBodySamplesforFunctionProfile(FunctionProfile, *LeafLoc, Count);
+      }
       // Move to next IP within the range
       IP.advance();
     }
   }
 }
 
 void CSProfileGenerator::populateFunctionBoundarySamples(
     StringRef ContextId, FunctionSamples &FunctionProfile,
     const BranchSample &BranchCounters, ProfiledBinary *Binary) {
 
   for (auto Entry : BranchCounters) {
     uint64_t SourceOffset = Entry.first.first;
     uint64_t TargetOffset = Entry.first.second;
     uint64_t Count = Entry.second;
     // Get the callee name by branch target if it's a call branch
     StringRef CalleeName = FunctionSamples::getCanonicalFnName(
         Binary->getFuncFromStartOffset(TargetOffset));
     if (CalleeName.size() == 0)
       continue;
 
     // Record called target sample and its count
-    const FrameLocation &LeafLoc = Binary->getInlineLeafFrameLoc(SourceOffset);
-    FunctionProfile.addCalledTargetSamples(LeafLoc.second.LineOffset,
-                                           LeafLoc.second.Discriminator,
+    auto LeafLoc = Binary->getInlineLeafFrameLoc(SourceOffset);
+    if (!LeafLoc.hasValue())
+      continue;
+    FunctionProfile.addCalledTargetSamples(LeafLoc->second.LineOffset,
+                                           LeafLoc->second.Discriminator,
                                            CalleeName, Count);
 
     // Record head sample for called target(callee)
     std::ostringstream OCalleeCtxStr;
     if (ContextId.find(" @ ") != StringRef::npos) {
       OCalleeCtxStr << ContextId.rsplit(" @ ").first.str();
       OCalleeCtxStr << " @ ";
     }
-    OCalleeCtxStr << getCallSite(LeafLoc) << " @ " << CalleeName.str();
+    OCalleeCtxStr << getCallSite(*LeafLoc) << " @ " << CalleeName.str();
 
     FunctionSamples &CalleeProfile =
         getFunctionProfileForContext(OCalleeCtxStr.str());
     assert(Count != 0 && "Unexpected zero weight branch");
     CalleeProfile.addHeadSamples(Count);
   }
 }
 

llvm/tools/llvm-profgen/ProfiledBinary.h

 //===-- ProfiledBinary.h - Binary decoder -----------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TOOLS_LLVM_PROFGEN_PROFILEDBINARY_H
 #define LLVM_TOOLS_LLVM_PROFGEN_PROFILEDBINARY_H
 
 #include "CallContext.h"
 #include "PseudoProbe.h"
+#include "llvm/ADT/Optional.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/DebugInfo/Symbolize/Symbolize.h"
 #include "llvm/MC/MCAsmInfo.h"
 #include "llvm/MC/MCContext.h"
 #include "llvm/MC/MCDisassembler/MCDisassembler.h"
 #include "llvm/MC/MCInst.h"
 #include "llvm/MC/MCInstPrinter.h"
 #include "llvm/MC/MCInstrAnalysis.h"
ProfiledBinary(StringRef Path, StringRef FileName)
     load();
   }
   uint64_t virtualAddrToOffset(uint64_t VitualAddress) const {
     return VitualAddress - BaseAddress;
   }
   uint64_t offsetToVirtualAddr(uint64_t Offset) const {
     return Offset + BaseAddress;
   }
   StringRef getPath() const { return Path; }
   StringRef getName() const { return llvm::sys::path::filename(Path); }
   uint64_t getBaseAddress() const { return BaseAddress; }
   void setBaseAddress(uint64_t Address) { BaseAddress = Address; }
   uint64_t getPreferredBaseAddress() const { return PreferredBaseAddress; }
 
   bool addressIsCode(uint64_t Address) const {
     uint64_t Offset = virtualAddrToOffset(Address);
     return Offset2LocStackMap.find(Offset) != Offset2LocStackMap.end();
public:
   uint64_t getCallAddrFromFrameAddr(uint64_t FrameAddr) const {
     return getAddressforIndex(getIndexForAddr(FrameAddr) - 1);
   }
 
   StringRef getFuncFromStartOffset(uint64_t Offset) {
     return FuncStartAddrMap[Offset];
   }
 
-  const FrameLocation &getInlineLeafFrameLoc(uint64_t Offset,
+  Optional<const FrameLocation> getInlineLeafFrameLoc(uint64_t Offset,
                                                       bool NameOnly = false) {
-    return getFrameLocationStack(Offset).back();
+    auto &Stack = getFrameLocationStack(Offset);
+    if (Stack.empty())
+      return {};
+    return Stack.back();
   }
 
   // Compare two addresses' inline context
   bool inlineContextEqual(uint64_t Add1, uint64_t Add2) const;
 
   // Get the context string of the current stack with inline context filled in.
   // It will search the disassembling info stored in Offset2LocStackMap. This is
   // used as the key of function sample map

llvm/tools/llvm-profgen/ProfiledBinary.cpp

 bool ProfiledBinary::inlineContextEqual(uint64_t Address1,
                                         uint64_t Address2) const {
   uint64_t Offset1 = virtualAddrToOffset(Address1);
   uint64_t Offset2 = virtualAddrToOffset(Address2);
   const FrameLocationStack &Context1 = getFrameLocationStack(Offset1);
   const FrameLocationStack &Context2 = getFrameLocationStack(Offset2);
   if (Context1.size() != Context2.size())
     return false;
-
+  if (Context1.empty())
+    return false;
   // The leaf frame contains location within the leaf, and it
   // needs to be remove that as it's not part of the calling context
   return std::equal(Context1.begin(), Context1.begin() + Context1.size() - 1,
                     Context2.begin(), Context2.begin() + Context2.size() - 1);
 }
 
 std::string ProfiledBinary::getExpandedContextStr(
     const SmallVectorImpl<uint64_t> &Stack) const {
   std::string ContextStr;
   SmallVector<std::string, 16> ContextVec;
   // Process from frame root to leaf
   for (auto Address : Stack) {
     uint64_t Offset = virtualAddrToOffset(Address);
     const FrameLocationStack &ExpandedContext = getFrameLocationStack(Offset);
+    if (ExpandedContext.empty())
+      return "";
     for (const auto &Loc : ExpandedContext) {
       ContextVec.push_back(getCallSite(Loc));
     }
   }
 
   assert(ContextVec.size() && "Context length should be at least 1");
   // Compress the context string except for the leaf frame
   std::string LeafFrame = ContextVec.back();
   ContextVec.pop_back();
if (ShowDisassembly()) {
         OS << getReversedLocWithContext(symbolize(Inst));
       }
       OS << "\n";
     }
 
     const MCInstrDesc &MCDesc = MII->get(Inst.getOpcode());
 
     // Populate a vector of the symbolized callsite at this location
+    // We don't need symbolized info for probe-based profile, just use an empty
+    // stack as an entry to indicate a valid binary offset
+    FrameLocationStack SymbolizedCallStack;
+    if (!UsePseudoProbes) {
       InstructionPointer IP(this, Offset);
-    Offset2LocStackMap[Offset] = symbolize(IP, true);
-
+      SymbolizedCallStack = symbolize(IP, true);
+    }
+    Offset2LocStackMap[Offset] = SymbolizedCallStack;
     // Populate address maps.
     CodeAddrs.push_back(Offset);
     if (MCDesc.isCall())
       CallAddrs.insert(Offset);
     else if (MCDesc.isReturn())
       RetAddrs.insert(Offset);
 
     Offset += Size;
InstructionPointer::InstructionPointer(ProfiledBinary *Binary, uint64_t Address,
   if (RoundToNext) {
     // we might get address which is not the code
     // it should round to the next valid address
     this->Address = Binary->getAddressforIndex(Index);
   }
 }
 
 void InstructionPointer::advance() {
   Index++;
   Address = Binary->getAddressforIndex(Index);
 }
 
 void InstructionPointer::backward() {
   Index--;
   Address = Binary->getAddressforIndex(Index);
 }
 
 void InstructionPointer::update(uint64_t Addr) {
   Address = Addr;
   Index = Binary->getIndexForAddr(Address);
 }
 
 } // end namespace sampleprof
 } // end namespace llvm