[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

60

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

431

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

182

nit: getNumInstructions or getNumCodeAddresses ?

[hoy]

llvm/tools/llvm-profgen/PerfReader.cpp

60

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

60

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

431

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

182

Good catch!

[hoy]

llvm/tools/llvm-profgen/PerfReader.cpp

60

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

60

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

60

Thanks for the refactoring. Looks a lot cleaner now.

95

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

llvm/tools/llvm-profgen/ProfiledBinary.cpp

137

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

[wlei]

llvm/tools/llvm-profgen/PerfReader.cpp

95

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

137

Good catch!

[hoy]

llvm/tools/llvm-profgen/PerfReader.cpp

95

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

139

nit: return std::string()

llvm/tools/llvm-profgen/ProfiledBinary.h

232

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()) {
     // map from a context key to the address range being unwound.
     // This means basically linear unwinding is not needed for pseudo
     // 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) {
+    bool HasNext = true;
+    while (IP.Address >= Target && HasNext) {
       uint64_t PrevIP = IP.Address;
-      IP.backward();
+      HasNext = IP.backward();
       // Break into segments for implicit call/return due to inlining
-      bool SameInlinee = Binary->inlineContextEqual(PrevIP, IP.Address);
+      bool SameInlinee =
+          HasNext && 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);
   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);

llvm/tools/llvm-profgen/ProfileGenerator.cpp

if (IP.Address > RangeEnd)
       continue;
 
     while (IP.Address <= RangeEnd) {
       uint64_t Offset = Binary->virtualAddrToOffset(IP.Address);
       const FrameLocation &LeafLoc = Binary->getInlineLeafFrameLoc(Offset);
       // Recording body sample for this specific context
       updateBodySamplesforFunctionProfile(FunctionProfile, LeafLoc, Count);
       // Move to next IP within the range
-      IP.advance();
+      if (!IP.advance())
+        break;
     }
   }
 }
 
 void CSProfileGenerator::populateFunctionBoundarySamples(
     StringRef ContextId, FunctionSamples &FunctionProfile,
     const BranchSample &BranchCounters, ProfiledBinary *Binary) {
 
while (IP.Address <= RangeEnd) {
       auto It = Address2ProbesMap.find(IP.Address);
       if (It != Address2ProbesMap.end()) {
         for (const auto &Probe : It->second) {
           if (!Probe.isBlock())
             continue;
           ProbeCounter[&Probe] += Count;
         }
       }
-
-      IP.advance();
+      if (!IP.advance())
+        break;
     }
   }
 }
 
 void PseudoProbeCSProfileGenerator::populateBodySamplesWithProbes(
     const RangeSample &RangeCounter,
     SmallVectorImpl<std::string> &ContextStrStack, ProfiledBinary *Binary) {
   ProbeCounterMap ProbeCounter;

llvm/tools/llvm-profgen/ProfiledBinary.h

union {
     uint64_t Offset = 0;
     // Also used as address in unwinder
     uint64_t Address;
   };
   // Index to the sorted code address array of the binary.
   uint64_t Index = 0;
   InstructionPointer(ProfiledBinary *Binary, uint64_t Address,
                      bool RoundToNext = false);
-  void advance();
-  void backward();
+  bool advance();
+  bool backward();
   void update(uint64_t Addr);
 };
 
 // PrologEpilog offset tracker, used to filter out broken stack samples
 // Currently we use a heuristic size (two) to infer prolog and epilog
 // based on the start address and return address. In the future,
 // we will switch to Dwarf CFI based tracker
 struct PrologEpilogTracker {
   // A set of prolog and epilog offsets. Used by virtual unwinding.
   std::unordered_set<uint64_t> PrologEpilogSet;
   ProfiledBinary *Binary;
   PrologEpilogTracker(ProfiledBinary *Bin) : Binary(Bin){};
 
   // Take the two addresses from the start of function as prolog
   void inferPrologOffsets(
       std::unordered_map<uint64_t, std::string> &FuncStartAddrMap) {
     for (auto I : FuncStartAddrMap) {
       PrologEpilogSet.insert(I.first);
       InstructionPointer IP(Binary, I.first);
-      IP.advance();
+      if (IP.advance())
         PrologEpilogSet.insert(IP.Offset);
     }
   }
 
   // Take the last two addresses before the return address as epilog
   void inferEpilogOffsets(std::unordered_set<uint64_t> &RetAddrs) {
     for (auto Addr : RetAddrs) {
       PrologEpilogSet.insert(Addr);
       InstructionPointer IP(Binary, Addr);
-      IP.backward();
+      if (IP.backward())
         PrologEpilogSet.insert(IP.Offset);
     }
   }
 };
 
 class ProfiledBinary {
   // Absolute path of the binary.
   std::string Path;
   // The target triple.
ProfiledBinary(StringRef Path) : Path(Path), ProEpilogTracker(this) {
     load();
   }
   uint64_t virtualAddrToOffset(uint64_t VitualAddress) const {
     return VitualAddress - BaseAddress;
   }
   uint64_t offsetToVirtualAddr(uint64_t Offset) const {
     return Offset + BaseAddress;
   }
+  uint32_t codeAddrsSize() { return CodeAddrs.size(); }
   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);
public:
 
   StringRef getFuncFromStartOffset(uint64_t Offset) {
     return FuncStartAddrMap[Offset];
   }
 
   const FrameLocation &getInlineLeafFrameLoc(uint64_t Offset,
                                              bool NameOnly = false) {
     return getFrameLocationStack(Offset).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
   std::string

llvm/tools/llvm-profgen/ProfiledBinary.cpp

 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);
     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();
   CSProfileGenerator::compressRecursionContext<std::string>(ContextVec);
 
if (ShowDisassembly) {
         outs() << getReversedLocWithContext(symbolize(Inst));
       }
       outs() << "\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
+    FrameLocationStack SymbolizedCallStack;
+    if (!UsePseudoProbes) {
       InstructionPointer IP(this, Offset);
-    Offset2LocStackMap[Offset] = symbolize(IP, true);
-
+      SymbolizedCallStack = symbolize(IP, true);
+    }
+    if (UsePseudoProbes || !SymbolizedCallStack.empty()) {
+      // For probe-based profile, just use an empty stack as an entry to
+      // indicate a valid binary offset
+      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;
   }
 
   if (ShowDisassembly)
     outs() << "\n";
 
   FuncStartAddrMap[StartOffset] = Symbols[SI].Name.str();
   return true;
InstructionPointer::InstructionPointer(ProfiledBinary *Binary, uint64_t Address,
   Index = Binary->getIndexForAddr(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() {
+bool InstructionPointer::advance() {
+  if (Index + 1 >= Binary->codeAddrsSize())
+    return false;
   Index++;
   Address = Binary->getAddressforIndex(Index);
+  return true;
 }
 
-void InstructionPointer::backward() {
+bool InstructionPointer::backward() {
+  if (Index == 0)
+    return false;
   Index--;
   Address = Binary->getAddressforIndex(Index);
+  return true;
 }
 
 void InstructionPointer::update(uint64_t Addr) {
   Address = Addr;
   Index = Binary->getIndexForAddr(Address);
 }
 
 } // end namespace sampleprof
 } // end namespace llvm