[PseudoProbe] Replace relocation with offset for entry probe.

[hoy]

Summary

Currently pseudo probe encoding for a function is like:

• For the first probe, a relocation from it to its physical position in the code body
• For subsequent probes, an incremental offset from the current probe to the previous probe

The relocation could potentially cause relocation overflow during link time. I'm now replacing it with an offset from the first probe to the function start address.

A source function could be lowered into multiple split functions due to outlining (e.g, coro-split). Since those split functions have independent link-time layout, to really avoid relocations from .pseudo_probe sections to .text sections, the offset to replace with should really be the offset from the probe's enclosing split function, rather than from the entry of the source function. This requires some changes to previous section-based emission scheme which now switches to be function-based. The assembly form of pseudo probe directive is also changed correspondingly, i.e, reflecting the split function name.

A sentinel probe is emitted for each of the functions with a different name from the source. The sentinel probe indicates the elf symbol name to differentiate subsequent probes from the ones from a different split function. For examples, given source function

Foo() {
  …
  Probe 1
  …
  Probe 2
}

If it is transformed into two split functions:

Foo:
   …

Foo.outlined:
   …

The encoding for the two split functions will be separate:

GUID of Foo
  Probe 1

GUID of Foo 
  Sentinel probe of Foo.outlined 
  Probe 2

Then probe1 will be decoded against binary Foo's address, and Probe 2 will be decoded against Foo.outlined. The sentinel probe of Foo.outlined makes sure there's not accidental relocation from Foo.outlined's probes to Foo's entry address.

Decoding change will be in separate patch.

[hoy]

Updating D135912: [PseudoProbe] Replace relocation with offset for entry probe.

[rafauler]

Not an expert, just some hints in case you like the suggestions.

llvm/include/llvm/MC/MCPseudoProbe.h

299

Is this over 80col?

llvm/lib/MC/MCPseudoProbe.cpp

151

typo Santinel->Sentinel

214–228

std::map is an expensive data structure. For usage patterns that are strictly "insert then query", considering using a vector + std::sort.

Reference https://llvm.org/docs/ProgrammersManual.html#dss-sortedvectormap

[hoy]

llvm/include/llvm/MC/MCPseudoProbe.h

299

Yes, it is. Fixed.

llvm/lib/MC/MCPseudoProbe.cpp

214–228

Good point. Changed to using vector+sort.

[hoy]

Addressing feedbacks.

[wenlei]

llvm/include/llvm/MC/MCPseudoProbe.h

34–36

I thought we now have GUID for symbol name for sentinel, and address offset for non-sentinel. What does regular probe that doesn't use offset refer to?

287

do you want to rename this to MCPseudoProbeFunctions?

llvm/lib/MC/MCPseudoProbe.cpp

52

Did you mean assert((LastProbe || IsSentinel) && "...")?

80–81

To be accurate, this is the GUID of the (split) binary function name / elf symbol name?

140

nit: this message doesn't provide additional info other than the assertion itself. the message could be something more meaningful - why we don't expect root node here

155

Is this checking the top level binary function name is different from the top level source function name? And this is to avoid emitting sentinel for main function body?

215

nit: this is a comparator instead of a sorter. same for the one above.

[wenlei]

llvm/include/llvm/MC/MCPseudoProbe.h

17–20

Have you considered removing this GUID field, but always require a sentinel probe for any (split) binary function including the main body?

[hoy]

llvm/include/llvm/MC/MCPseudoProbe.h

17–20

The GUID field here is the GUID of the source/dwarf name, which may be different from the actually symbol linkage name, even for the main body of the function. The source GUID will be used to decode and generate a profile against the source function name.

34–36

This is mainly for downwards compatibility, i.e, to have the new llvm-profgen handle old binaries. Also Bolt re-encoding uses the old encoding scheme for simplicity.

287

This class kind of tells how probe encoding looks physically. Probes of a function will stay in a standalone section (comdat) and that's why section is used here. I'd like to keep it as is, but don't have a strong preference. WDYT?

llvm/lib/MC/MCPseudoProbe.cpp

52

Good catch. Yeah, that's what I actually want.

80–81

Exactly.

140

Fixed.

155

Exactly. Added a comment about that.

The encoding for a function with outlined code will look like below. Note that the main entry doesn't need a sentinel probe.

GUID of Foo
  Probe 1

GUID of Foo 
  Sentinel probe of Foo.outlined 
  Probe 2

[hoy]

Addressing feedbacks.

[wenlei]

For those don't, a sentinel probe is emitted for each of the binary functions with a different name from the source.

Nit but it indeed caused confusion for me: if the definition of binary function is each MCSymbol, the above isn't accurate because we never add sentinel for the original function.

Also the term binary function is a bit confusing too. Intuitively a binary function has 1:1 mapping to source function, which is how BOLT defines binary function I believe. I also didn't find precedence in LLVM/MC where these funclets are called binary function. Can we make it straightforward and just call it split functions in code and comments?

Otherwise this looks good. Thanks for working on relocation removal.

llvm/include/llvm/MC/MCPseudoProbe.h

17–20

Ok, makes sense. Maybe clarify this in this comment section as well?

34–36

How about adding a TODO comment to remove this later?

[hoy]

In D135912#3883462, @wenlei wrote:

For those don't, a sentinel probe is emitted for each of the binary functions with a different name from the source.

Nit but it indeed caused confusion for me: if the definition of binary function is each MCSymbol, the above isn't accurate because we never add sentinel for the original function.

I see. Will just remove "Most of the source functions end up with only one binary function. For those don't, ".

Also the term binary function is a bit confusing too. Intuitively a binary function has 1:1 mapping to source function, which is how BOLT defines binary function I believe. I also didn't find precedence in LLVM/MC where these funclets are called binary function. Can we make it straightforward and just call it split functions in code and comments?

Otherwise this looks good. Thanks for working on relocation removal.

How about using code ranges instead of binary functions?

llvm/include/llvm/MC/MCPseudoProbe.h

17–20

Done.

34–36

Sounds good.

[hoy]

Updating comments.

[wenlei]

How about using code ranges instead of binary functions?

code range is very general. I'd just use split function to make it straightforward. otoh, if BOLT uses the term binary function to represent those split funclets, it would be ok to do the same here too.

[hoy]

Updating D135912: [PseudoProbe] Replace relocation with offset for entry probe.

[wenlei]

lgtm, thanks.

llvm/include/llvm/IR/PseudoProbe.h

33

nit on comment: split function entry address? main body doesn't have it.

llvm/lib/MC/MCPseudoProbe.cpp

80–81

nit on comment: function -> split function?

[hoy]

llvm/include/llvm/IR/PseudoProbe.h

33

Sounds good. Strictly speaking, main body can also have a sentinel probe if its source name doesn't equal binary name, like with the .llvm. suffix, but split function here would make it more obvious.

llvm/lib/MC/MCPseudoProbe.cpp

80–81

Done.

[hoy]

Renaming

bolt/lib/Rewrite/RewriteInstance.cpp

void RewriteInstance::parsePseudoProbe() {
 
   StringRef Contents = PseudoProbeDescSection->getContents();
   if (!BC->ProbeDecoder.buildGUID2FuncDescMap(
           reinterpret_cast<const uint8_t *>(Contents.data()),
           Contents.size())) {
     errs() << "BOLT-WARNING: fail in building GUID2FuncDescMap\n";
     return;
   }
+
+  MCPseudoProbeDecoder::Uint64Set GuidFilter;
+  MCPseudoProbeDecoder::Uint64Map FuncStartAddrs;
+  for (const BinaryFunction *F : BC->getAllBinaryFunctions()) {
+    for (const MCSymbol *Sym : F->getSymbols()) {
+      FuncStartAddrs[Function::getGUID(NameResolver::restore(Sym->getName()))] =
+          F->getAddress();
+    }
+  }
   Contents = PseudoProbeSection->getContents();
   if (!BC->ProbeDecoder.buildAddress2ProbeMap(
-          reinterpret_cast<const uint8_t *>(Contents.data()),
-          Contents.size())) {
+          reinterpret_cast<const uint8_t *>(Contents.data()), Contents.size(),
+          GuidFilter, FuncStartAddrs)) {
     BC->ProbeDecoder.getAddress2ProbesMap().clear();
     errs() << "BOLT-WARNING: fail in building Address2ProbeMap\n";
     return;
   }
 
   if (opts::PrintPseudoProbes == opts::PrintPseudoProbesOptions::PPP_All ||
       opts::PrintPseudoProbes ==
           opts::PrintPseudoProbesOptions::PPP_Probes_Section_Decode) {
auto EmitSLEB128IntValue = [&](int64_t Value) {
     Contents.append(OSE.str().begin(), OSE.str().end());
   };
 
   // Emit indiviual pseudo probes in a inline tree node
   // Probe index, type, attribute, address type and address are encoded
   // Address of the first probe is absolute.
   // Other probes' address are represented by delta
   auto EmitDecodedPseudoProbe = [&](MCDecodedPseudoProbe *&CurProbe) {
+    assert(!isSentinelProbe(CurProbe->getAttributes()) &&
+           "Sentinel probes should not be emitted");
     EmitULEB128IntValue(CurProbe->getIndex());
     uint8_t PackedType = CurProbe->getType() | (CurProbe->getAttributes() << 4);
     uint8_t Flag =
         LastProbe ? ((int8_t)MCPseudoProbeFlag::AddressDelta << 7) : 0;
     EmitInt(Flag | PackedType, 1);
     if (LastProbe) {
       // Emit the delta between the address label and LastProbe.
       int64_t Delta = CurProbe->getAddress() - LastProbe->getAddress();
if (opts::PrintPseudoProbes == opts::PrintPseudoProbesOptions::PPP_All ||
           opts::PrintPseudoProbesOptions::PPP_Encoded_Probes) {
     // create a dummy decoder;
     MCPseudoProbeDecoder DummyDecoder;
     StringRef DescContents = PseudoProbeDescSection->getContents();
     DummyDecoder.buildGUID2FuncDescMap(
         reinterpret_cast<const uint8_t *>(DescContents.data()),
         DescContents.size());
     StringRef ProbeContents = PseudoProbeSection->getOutputContents();
+    MCPseudoProbeDecoder::Uint64Set GuidFilter;
+    MCPseudoProbeDecoder::Uint64Map FuncStartAddrs;
+    for (const BinaryFunction *F : BC->getAllBinaryFunctions()) {
+      const uint64_t Addr =
+          F->isEmitted() ? F->getOutputAddress() : F->getAddress();
+      FuncStartAddrs[Function::getGUID(
+          NameResolver::restore(F->getOneName()))] = Addr;
+    }
     DummyDecoder.buildAddress2ProbeMap(
         reinterpret_cast<const uint8_t *>(ProbeContents.data()),
-        ProbeContents.size());
+        ProbeContents.size(), GuidFilter, FuncStartAddrs);
     DummyDecoder.printProbesForAllAddresses(outs());
   }
 }
 
 void RewriteInstance::updateSDTMarkers() {
   NamedRegionTimer T("updateSDTMarkers", "update SDT markers", TimerGroupName,
                      TimerGroupDesc, opts::TimeRewrite);
 

llvm/include/llvm/IR/PseudoProbe.h

 #include <limits>
 
 namespace llvm {
 
 class Instruction;
 
 constexpr const char *PseudoProbeDescMetadataName = "llvm.pseudo_probe_desc";
 
+enum class PseudoProbeReservedId { Invalid = 0, Last = Invalid };
+
 enum class PseudoProbeType { Block = 0, IndirectCall, DirectCall };
 
+enum class PseudoProbeAttributes {
+  Reserved = 0x1,
+  Sentinel = 0x2, // A place holder for split function entry address.
+};
+
 // The saturated distrution factor representing 100% for block probes.
 constexpr static uint64_t PseudoProbeFullDistributionFactor =
     std::numeric_limits<uint64_t>::max();
 
 struct PseudoProbeDwarfDiscriminator {
 public:
   // The following APIs encodes/decodes per-probe information to/from a
   // 32-bit integer which is organized as:
struct PseudoProbe {
   uint32_t Type;
   uint32_t Attr;
   // Distribution factor that estimates the portion of the real execution count.
   // A saturated distribution factor stands for 1.0 or 100%. A pesudo probe has
   // a factor with the value ranged from 0.0 to 1.0.
   float Factor;
 };
 
+static inline bool isSentinelProbe(uint32_t Flags) {
+  return Flags & (uint32_t)PseudoProbeAttributes::Sentinel;
+}
+
 Optional<PseudoProbe> extractProbe(const Instruction &Inst);
 
 void setProbeDistributionFactor(Instruction &Inst, float Factor);
 } // end namespace llvm
 
 #endif // LLVM_IR_PSEUDOPROBE_H

llvm/include/llvm/MC/MCObjectFileInfo.h

public:
   MCSection *getRemarksSection() const { return RemarksSection; }
 
   MCSection *getStackSizesSection(const MCSection &TextSec) const;
 
   MCSection *getBBAddrMapSection(const MCSection &TextSec) const;
 
   MCSection *getKCFITrapSection(const MCSection &TextSec) const;
 
-  MCSection *getPseudoProbeSection(const MCSection *TextSec) const;
+  MCSection *getPseudoProbeSection(const MCSection &TextSec) const;
 
   MCSection *getPseudoProbeDescSection(StringRef FuncName) const;
 
   MCSection *getPCSection(StringRef Name, const MCSection *TextSec) const;
 
   // ELF specific sections.
   MCSection *getDataRelROSection() const { return DataRelROSection; }
   const MCSection *getMergeableConst4Section() const {

llvm/include/llvm/MC/MCPseudoProbe.h

 //===- MCPseudoProbe.h - Pseudo probe encoding support ---------*- 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
 //
 //===----------------------------------------------------------------------===//
 //
 // This file contains the declaration of the MCPseudoProbe to support the pseudo
 // probe encoding for AutoFDO. Pseudo probes together with their inline context
 // are encoded in a DFS recursive way in the .pseudoprobe sections. For each
 // .pseudoprobe section, the encoded binary data consist of a single or mutiple
 // function records each for one outlined function. A function record has the
 // following format :
 //
 // FUNCTION BODY (one for each outlined function present in the text section)
 //    GUID (uint64)
-//        GUID of the function
+//        GUID of the function's source name which may be different from the
+//        actual binary linkage name. This GUID will be used to decode and
+//        generate a profile against the source function name.
 //    NPROBES (ULEB128)
 //        Number of probes originating from this function.
 //    NUM_INLINED_FUNCTIONS (ULEB128)
 //        Number of callees inlined into this function, aka number of
 //        first-level inlinees
 //    PROBE RECORDS
 //        A list of NPROBES entries. Each entry contains:
 //          INDEX (ULEB128)
 //          TYPE (uint4)
 //            0 - block probe, 1 - indirect call, 2 - direct call
 //          ATTRIBUTE (uint3)
 //            1 - reserved
 //          ADDRESS_TYPE (uint1)
-//            0 - code address, 1 - address delta
+//            0 - code address for regular probes (for downwards compatibility)
+//              - GUID of linkage name for sentinel probes
+//            1 - address delta
 //          CODE_ADDRESS (uint64 or ULEB128)
 //            code address or address delta, depending on ADDRESS_TYPE
 //    INLINED FUNCTION RECORDS
 //        A list of NUM_INLINED_FUNCTIONS entries describing each of the inlined
 //        callees.  Each record contains:
 //          INLINE SITE
 //            ID of the callsite probe (ULEB128)
 //          FUNCTION BODY
 //            A FUNCTION BODY entry describing the inlined function.
+//
+// TODO: retire the ADDRESS_TYPE encoding for code addresses once compatibility
+// is no longer an issue.
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_MC_MCPSEUDOPROBE_H
 #define LLVM_MC_MCPSEUDOPROBE_H
 
+#include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/IR/PseudoProbe.h"
 #include "llvm/Support/ErrorOr.h"
 #include <list>
 #include <map>
 #include <memory>
 #include <string>
public:
   MCDecodedPseudoProbeInlineTree(const InlineSite &Site) : ISite(Site){};
 
   // Return false if it's a dummy inline site
   bool hasInlineSite() const { return !isRoot() && !Parent->isRoot(); }
 };
 
 /// Instances of this class represent the pseudo probes inserted into a compile
 /// unit.
-class MCPseudoProbeSection {
+class MCPseudoProbeSections {
 public:
-  void addPseudoProbe(MCSection *Sec, const MCPseudoProbe &Probe,
+  void addPseudoProbe(MCSymbol *FuncSym, const MCPseudoProbe &Probe,
                       const MCPseudoProbeInlineStack &InlineStack) {
-    MCProbeDivisions[Sec].addPseudoProbe(Probe, InlineStack);
+    MCProbeDivisions[FuncSym].addPseudoProbe(Probe, InlineStack);
   }
 
   // TODO: Sort by getOrdinal to ensure a determinstic section order
-  using MCProbeDivisionMap = std::map<MCSection *, MCPseudoProbeInlineTree>;
+  using MCProbeDivisionMap = std::map<MCSymbol *, MCPseudoProbeInlineTree>;
 
 private:
-  // A collection of MCPseudoProbe for each text section. The MCPseudoProbes
-  // are grouped by GUID of the functions where they are from and will be
-  // encoded by groups. In the comdat scenario where a text section really only
-  // contains the code of a function solely, the probes associated with a comdat
-  // function are still grouped by GUIDs due to inlining that can bring probes
-  // from different functions into one function.
+  // A collection of MCPseudoProbe for each function. The MCPseudoProbes are
+  // grouped by GUIDs due to inlining that can bring probes from different
+  // functions into one function.
   MCProbeDivisionMap MCProbeDivisions;
 
 public:
   const MCProbeDivisionMap &getMCProbes() const { return MCProbeDivisions; }
 
   bool empty() const { return MCProbeDivisions.empty(); }
 
   void emit(MCObjectStreamer *MCOS);
 };
 
 class MCPseudoProbeTable {
-  // A collection of MCPseudoProbe in the current module grouped by text
-  // sections. MCPseudoProbes will be encoded into a corresponding
+  // A collection of MCPseudoProbe in the current module grouped by
+  // functions. MCPseudoProbes will be encoded into a corresponding
   // .pseudoprobe section. With functions emitted as separate comdats,
   // a text section really only contains the code of a function solely, and the
   // probes associated with the text section will be emitted into a standalone
   // .pseudoprobe section that shares the same comdat group with the function.
-  MCPseudoProbeSection MCProbeSections;
+  MCPseudoProbeSections MCProbeSections;
 
 public:
   static void emit(MCObjectStreamer *MCOS);
 
-  MCPseudoProbeSection &getProbeSections() { return MCProbeSections; }
+  MCPseudoProbeSections &getProbeSections() { return MCProbeSections; }
 
 #ifndef NDEBUG
   static int DdgPrintIndent;
 #endif
 };
 
 class MCPseudoProbeDecoder {
   // GUID to PseudoProbeFuncDesc map.
class MCPseudoProbeDecoder {
   MCDecodedPseudoProbeInlineTree DummyInlineRoot;
 
   /// Points to the current location in the buffer.
   const uint8_t *Data = nullptr;
 
   /// Points to the end of the buffer.
   const uint8_t *End = nullptr;
 
+  /// Whether encoding is based on a starting probe with absolute code address.
+  bool EncodingIsAddrBased = false;
+
   // Decoding helper function
   template <typename T> ErrorOr<T> readUnencodedNumber();
   template <typename T> ErrorOr<T> readUnsignedNumber();
   template <typename T> ErrorOr<T> readSignedNumber();
   ErrorOr<StringRef> readString(uint32_t Size);
 
 public:
+  using Uint64Set = DenseSet<uint64_t>;
+  using Uint64Map = DenseMap<uint64_t, uint64_t>;
+
   // Decode pseudo_probe_desc section to build GUID to PseudoProbeFuncDesc map.
   bool buildGUID2FuncDescMap(const uint8_t *Start, std::size_t Size);
 
-  // Decode pseudo_probe section to build address to probes map.
-  bool buildAddress2ProbeMap(const uint8_t *Start, std::size_t Size);
-
   // Decode pseudo_probe section to build address to probes map for specifed
   // functions only.
   bool buildAddress2ProbeMap(const uint8_t *Start, std::size_t Size,
-                             std::unordered_set<uint64_t> &GuildFilter);
+                             const Uint64Set &GuildFilter,
+                             const Uint64Map &FuncStartAddrs);
 
   bool buildAddress2ProbeMap(MCDecodedPseudoProbeInlineTree *Cur,
-                             uint64_t &LastAddr,
-                             std::unordered_set<uint64_t> &GuildFilter);
+                             uint64_t &LastAddr, const Uint64Set &GuildFilter,
+                             const Uint64Map &FuncStartAddrs);
 
   // Print pseudo_probe_desc section info
   void printGUID2FuncDescMap(raw_ostream &OS);
 
   // Print pseudo_probe section info, used along with show-disassembly
   void printProbeForAddress(raw_ostream &OS, uint64_t Address);
 
   // do printProbeForAddress for all addresses

llvm/include/llvm/MC/MCStreamer.h

public:
   virtual void emitAddrsigSym(const MCSymbol *Sym) {}
 
   /// Emit the given \p Instruction into the current section.
   virtual void emitInstruction(const MCInst &Inst, const MCSubtargetInfo &STI);
 
   /// Emit the a pseudo probe into the current section.
   virtual void emitPseudoProbe(uint64_t Guid, uint64_t Index, uint64_t Type,
                                uint64_t Attr,
-                               const MCPseudoProbeInlineStack &InlineStack);
+                               const MCPseudoProbeInlineStack &InlineStack,
+                               MCSymbol *FnSym);
 
   /// Set the bundle alignment mode from now on in the section.
   /// The argument is the power of 2 to which the alignment is set. The
   /// value 0 means turn the bundle alignment off.
   virtual void emitBundleAlignMode(unsigned AlignPow2);
 
   /// The following instructions are a bundle-locked group.
   ///

llvm/include/llvm/Transforms/IPO/SampleProfileProbe.h

 using BlockIdMap = std::unordered_map<BasicBlock *, uint32_t>;
 using InstructionIdMap = std::unordered_map<Instruction *, uint32_t>;
 // Map from tuples of Probe id and inline stack hash code to distribution
 // factors.
 using ProbeFactorMap = std::unordered_map<std::pair<uint64_t, uint64_t>, float,
                                           pair_hash<uint64_t, uint64_t>>;
 using FuncProbeFactorMap = StringMap<ProbeFactorMap>;
 
-enum class PseudoProbeReservedId { Invalid = 0, Last = Invalid };
-
 class PseudoProbeDescriptor {
   uint64_t FunctionGUID;
   uint64_t FunctionHash;
 
 public:
   PseudoProbeDescriptor(uint64_t GUID, uint64_t Hash)
       : FunctionGUID(GUID), FunctionHash(Hash) {}
   uint64_t getFunctionGUID() const { return FunctionGUID; }

llvm/lib/CodeGen/AsmPrinter/PseudoProbePrinter.cpp

if (!CallerGuid)
       CallerGuid = Function::getGUID(Name);
     uint64_t CallerProbeId = PseudoProbeDwarfDiscriminator::extractProbeIndex(
         InlinedAt->getDiscriminator());
     ReversedInlineStack.emplace_back(CallerGuid, CallerProbeId);
     InlinedAt = InlinedAt->getInlinedAt();
   }
 
   SmallVector<InlineSite, 8> InlineStack(llvm::reverse(ReversedInlineStack));
-  Asm->OutStreamer->emitPseudoProbe(Guid, Index, Type, Attr, InlineStack);
+  Asm->OutStreamer->emitPseudoProbe(Guid, Index, Type, Attr, InlineStack,
+                                    Asm->CurrentFnSym);
 }

llvm/lib/MC/MCAsmStreamer.cpp

public:
 
   void emitCGProfileEntry(const MCSymbolRefExpr *From,
                           const MCSymbolRefExpr *To, uint64_t Count) override;
 
   void emitInstruction(const MCInst &Inst, const MCSubtargetInfo &STI) override;
 
   void emitPseudoProbe(uint64_t Guid, uint64_t Index, uint64_t Type,
                        uint64_t Attr,
-                       const MCPseudoProbeInlineStack &InlineStack) override;
+                       const MCPseudoProbeInlineStack &InlineStack, MCSymbol *FnSym) override;
 
   void emitBundleAlignMode(unsigned AlignPow2) override;
   void emitBundleLock(bool AlignToEnd) override;
   void emitBundleUnlock() override;
 
   Optional<std::pair<bool, std::string>>
   emitRelocDirective(const MCExpr &Offset, StringRef Name, const MCExpr *Expr,
                      SMLoc Loc, const MCSubtargetInfo &STI) override;
void MCAsmStreamer::emitInstruction(const MCInst &Inst,
   if (Comments.size() && Comments.back() != '\n')
     getCommentOS() << "\n";
 
   EmitEOL();
 }
 
 void MCAsmStreamer::emitPseudoProbe(
     uint64_t Guid, uint64_t Index, uint64_t Type, uint64_t Attr,
-    const MCPseudoProbeInlineStack &InlineStack) {
+    const MCPseudoProbeInlineStack &InlineStack, MCSymbol *FnSym) {
   OS << "\t.pseudoprobe\t" << Guid << " " << Index << " " << Type << " "
      << Attr;
   // Emit inline stack like
   //  @ GUIDmain:3 @ GUIDCaller:1 @ GUIDDirectCaller:11
   for (const auto &Site : InlineStack)
     OS << " @ " << std::get<0>(Site) << ":" << std::get<1>(Site);
+
+  OS << " " << FnSym->getName();
+
   EmitEOL();
 }
 
 void MCAsmStreamer::emitBundleAlignMode(unsigned AlignPow2) {
   OS << "\t.bundle_align_mode " << AlignPow2;
   EmitEOL();
 }
 

llvm/lib/MC/MCObjectFileInfo.cpp

MCObjectFileInfo::getKCFITrapSection(const MCSection &TextSec) const {
 
   return Ctx->getELFSection(".kcfi_traps", ELF::SHT_PROGBITS, Flags, 0,
                             GroupName,
                             /*IsComdat=*/true, ElfSec.getUniqueID(),
                             cast<MCSymbolELF>(TextSec.getBeginSymbol()));
 }
 
 MCSection *
-MCObjectFileInfo::getPseudoProbeSection(const MCSection *TextSec) const {
+MCObjectFileInfo::getPseudoProbeSection(const MCSection &TextSec) const {
   if (Ctx->getObjectFileType() == MCContext::IsELF) {
-    const auto *ElfSec = static_cast<const MCSectionELF *>(TextSec);
+    const auto &ElfSec = static_cast<const MCSectionELF &>(TextSec);
     // Create a separate section for probes that comes with a comdat function.
-    if (const MCSymbol *Group = ElfSec->getGroup()) {
+    if (const MCSymbol *Group = ElfSec.getGroup()) {
       auto *S = static_cast<MCSectionELF *>(PseudoProbeSection);
       auto Flags = S->getFlags() | ELF::SHF_GROUP;
       return Ctx->getELFSection(S->getName(), S->getType(), Flags,
                                 S->getEntrySize(), Group->getName(),
                                 /*IsComdat=*/true);
     }
   }
   return PseudoProbeSection;

llvm/lib/MC/MCParser/AsmParser.cpp

if (getLexer().is(AsmToken::Integer)) {
                         "unexpected token in '.pseudoprobe' directive"))
         return true;
     }
 
     InlineSite Site(CallerGuid, CallerProbeId);
     InlineStack.push_back(Site);
   }
 
+  // Parse function entry name
+  StringRef FnName;
+  if (parseIdentifier(FnName))
+    return Error(getLexer().getLoc(), "unexpected token in '.pseudoprobe' directive");
+  MCSymbol *FnSym = getContext().lookupSymbol(FnName);
+
   if (parseEOL())
     return true;
 
-  getStreamer().emitPseudoProbe(Guid, Index, Type, Attr, InlineStack);
+  getStreamer().emitPseudoProbe(Guid, Index, Type, Attr, InlineStack, FnSym);
   return false;
 }
 
 /// parseDirectiveLTODiscard
 ///  ::= ".lto_discard" [ identifier ( , identifier )* ]
 /// The LTO library emits this directive to discard non-prevailing symbols.
 /// We ignore symbol assignments and attribute changes for the specified
 /// symbols.

llvm/lib/MC/MCPseudoProbe.cpp

 //===- lib/MC/MCPseudoProbe.cpp - Pseudo probe encoding support ----------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/MC/MCPseudoProbe.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/MC/MCAsmInfo.h"
 #include "llvm/MC/MCContext.h"
 #include "llvm/MC/MCExpr.h"
 #include "llvm/MC/MCFragment.h"
 #include "llvm/MC/MCObjectFileInfo.h"
 #include "llvm/MC/MCObjectStreamer.h"
+#include "llvm/MC/MCSymbol.h"
 #include "llvm/Support/Endian.h"
 #include "llvm/Support/LEB128.h"
+#include "llvm/Support/MD5.h"
 #include "llvm/Support/raw_ostream.h"
+#include <algorithm>
+#include <cassert>
 #include <limits>
 #include <memory>
 #include <sstream>
+#include <vector>
 
 #define DEBUG_TYPE "mcpseudoprobe"
 
 using namespace llvm;
 using namespace support;
 
 #ifndef NDEBUG
 int MCPseudoProbeTable::DdgPrintIndent = 0;
 #endif
 
 static const MCExpr *buildSymbolDiff(MCObjectStreamer *MCOS, const MCSymbol *A,
                                      const MCSymbol *B) {
   MCContext &Context = MCOS->getContext();
   MCSymbolRefExpr::VariantKind Variant = MCSymbolRefExpr::VK_None;
   const MCExpr *ARef = MCSymbolRefExpr::create(A, Variant, Context);
   const MCExpr *BRef = MCSymbolRefExpr::create(B, Variant, Context);
   const MCExpr *AddrDelta =
       MCBinaryExpr::create(MCBinaryExpr::Sub, ARef, BRef, Context);
   return AddrDelta;
 }
 
 void MCPseudoProbe::emit(MCObjectStreamer *MCOS,
                          const MCPseudoProbe *LastProbe) const {
+  bool IsSentinel = isSentinelProbe(getAttributes());
+  assert((LastProbe || IsSentinel) &&
+         "Last probe should not be null for non-sentinel probes");
+
   // Emit Index
   MCOS->emitULEB128IntValue(Index);
   // Emit Type and the flag:
   // Type (bit 0 to 3), with bit 4 to 6 for attributes.
   // Flag (bit 7, 0 - code address, 1 - address delta). This indicates whether
   // the following field is a symbolic code address or an address delta.
   assert(Type <= 0xF && "Probe type too big to encode, exceeding 15");
   assert(Attributes <= 0x7 &&
          "Probe attributes too big to encode, exceeding 7");
   uint8_t PackedType = Type | (Attributes << 4);
-  uint8_t Flag = LastProbe ? ((int8_t)MCPseudoProbeFlag::AddressDelta << 7) : 0;
+  uint8_t Flag =
+      !IsSentinel ? ((int8_t)MCPseudoProbeFlag::AddressDelta << 7) : 0;
   MCOS->emitInt8(Flag | PackedType);
 
-  if (LastProbe) {
+  if (!IsSentinel) {
     // Emit the delta between the address label and LastProbe.
     const MCExpr *AddrDelta =
         buildSymbolDiff(MCOS, Label, LastProbe->getLabel());
     int64_t Delta;
     if (AddrDelta->evaluateAsAbsolute(Delta, MCOS->getAssemblerPtr())) {
       MCOS->emitSLEB128IntValue(Delta);
     } else {
       MCOS->insert(new MCPseudoProbeAddrFragment(AddrDelta));
     }
   } else {
-    // Emit label as a symbolic code address.
-    MCOS->emitSymbolValue(
-        Label, MCOS->getContext().getAsmInfo()->getCodePointerSize());
+    // Emit the GUID of the split function that the sentinel probe represents.
+    MCOS->emitInt64(Guid);
   }
 
   LLVM_DEBUG({
     dbgs().indent(MCPseudoProbeTable::DdgPrintIndent);
     dbgs() << "Probe: " << Index << "\n";
   });
 }
 
 void MCPseudoProbeInlineTree::addPseudoProbe(
     const MCPseudoProbe &Probe, const MCPseudoProbeInlineStack &InlineStack) {
   // The function should not be called on the root.
-  assert(isRoot() && "Should not be called on root");
+  assert(isRoot() && "Should only be called on root");
 
   // When it comes here, the input look like:
   //    Probe: GUID of C, ...
   //    InlineStack: [88, A], [66, B]
   // which means, Function A inlines function B at call site with a probe id of
   // 88, and B inlines C at probe 66. The tri-tree expects a tree path like {[0,
   // A], [88, B], [66, C]} to locate the tree node where the probe should be
   // added. Note that the edge [0, A] means A is the top-level function we are

 
 void MCPseudoProbeInlineTree::emit(MCObjectStreamer *MCOS,
                                    const MCPseudoProbe *&LastProbe) {
   LLVM_DEBUG({
     dbgs().indent(MCPseudoProbeTable::DdgPrintIndent);
     dbgs() << "Group [\n";
     MCPseudoProbeTable::DdgPrintIndent += 2;
   });
+  assert(!isRoot() && "Root should be handled seperately");
+
   // Emit probes grouped by GUID.
-  if (Guid != 0) {
-    LLVM_DEBUG({
-      dbgs().indent(MCPseudoProbeTable::DdgPrintIndent);
-      dbgs() << "GUID: " << Guid << "\n";
-    });
-    // Emit Guid
-    MCOS->emitInt64(Guid);
-    // Emit number of probes in this node
-    MCOS->emitULEB128IntValue(Probes.size());
-    // Emit number of direct inlinees
-    MCOS->emitULEB128IntValue(Children.size());
-    // Emit probes in this group
-    for (const auto &Probe : Probes) {
-      Probe.emit(MCOS, LastProbe);
-      LastProbe = &Probe;
-    }
-  } else {
-    assert(Probes.empty() && "Root should not have probes");
-  }
+  // Emit number of probes in this node, including a sentinel probe for
+  // top-level functions if needed.
+  bool NeedSentinel = false;
+  if (Parent->isRoot()) {
+    assert(isSentinelProbe(LastProbe->getAttributes()) &&
+           "Starting probe of a top-level function should be a sentinel probe");
+    // The main body of a split function doesn't need a sentinel probe.
+    if (LastProbe->getGuid() != Guid)
+      NeedSentinel = true;
+  }
+
+  MCOS->emitULEB128IntValue(Probes.size() + NeedSentinel);
+  // Emit sentinel probe for top-level functions
+  if (NeedSentinel)
+    LastProbe->emit(MCOS, nullptr);
+
 
-  // Emit sorted descendant
-  // InlineSite is unique for each pair,
-  // so there will be no ordering of Inlinee based on MCPseudoProbeInlineTree*
-  std::map<InlineSite, MCPseudoProbeInlineTree *> Inlinees;
-  for (auto &Child : Children)
-    Inlinees[Child.first] = Child.second.get();
+  // Emit sorted descendant. InlineSite is unique for each pair, so there will
+  // be no ordering of Inlinee based on MCPseudoProbeInlineTree*
+  using InlineeType = std::pair<InlineSite, MCPseudoProbeInlineTree *>;
+  auto Comparer = [](const InlineeType &A, const InlineeType &B) {
+    return A.first < B.first;
+  };
+  std::vector<InlineeType> Inlinees;
+  for (const auto &Child : Children)
+    Inlinees.emplace_back(Child.first, Child.second.get());
+  std::sort(Inlinees.begin(), Inlinees.end(), Comparer);
 
   for (const auto &Inlinee : Inlinees) {
-    if (Guid) {
-      // Emit probe index
-      MCOS->emitULEB128IntValue(std::get<1>(Inlinee.first));
-      LLVM_DEBUG({
-        dbgs().indent(MCPseudoProbeTable::DdgPrintIndent);
-        dbgs() << "InlineSite: " << std::get<1>(Inlinee.first) << "\n";
-      });
-    }
     // Emit the group
     Inlinee.second->emit(MCOS, LastProbe);
   }
 
   LLVM_DEBUG({
     MCPseudoProbeTable::DdgPrintIndent -= 2;
     dbgs().indent(MCPseudoProbeTable::DdgPrintIndent);
     dbgs() << "]\n";
   });
 }
 
-void MCPseudoProbeSection::emit(MCObjectStreamer *MCOS) {
+void MCPseudoProbeSections::emit(MCObjectStreamer *MCOS) {
   MCContext &Ctx = MCOS->getContext();
-
   for (auto &ProbeSec : MCProbeDivisions) {
-    const MCPseudoProbe *LastProbe = nullptr;
-    if (auto *S =
-            Ctx.getObjectFileInfo()->getPseudoProbeSection(ProbeSec.first)) {
+    const auto *FuncSym = ProbeSec.first;
+    const auto &Root = ProbeSec.second;
+    if (auto *S = Ctx.getObjectFileInfo()->getPseudoProbeSection(
+            FuncSym->getSection())) {
       // Switch to the .pseudoprobe section or a comdat group.
       MCOS->switchSection(S);
       // Emit probes grouped by GUID.
-      ProbeSec.second.emit(MCOS, LastProbe);
+      // Emit sorted descendant. InlineSite is unique for each pair, so there
+      // will be no ordering of Inlinee based on MCPseudoProbeInlineTree*
+      using InlineeType = std::pair<InlineSite, MCPseudoProbeInlineTree *>;
+      auto Comparer = [](const InlineeType &A, const InlineeType &B) {
+        return A.first < B.first;
+      };
+      std::vector<InlineeType> Inlinees;
+      for (const auto &Child : Root.getChildren())
+        Inlinees.emplace_back(Child.first, Child.second.get());
+      std::sort(Inlinees.begin(), Inlinees.end(), Comparer);
+
+      for (const auto &Inlinee : Inlinees) {
+        // Emit the group guarded by a sentinel probe.
+        MCPseudoProbe SentinelProbe(const_cast<MCSymbol *>(FuncSym),
+                                    MD5Hash(FuncSym->getName()),
+                                    (uint32_t)PseudoProbeReservedId::Invalid,
+                                    (uint32_t)PseudoProbeType::Block,
+                                    (uint32_t)PseudoProbeAttributes::Sentinel);
+        const MCPseudoProbe *Probe = &SentinelProbe;
+        Inlinee.second->emit(MCOS, Probe);
+      }
     }
   }
 }
 
 //
 // This emits the pseudo probe tables.
 //
 void MCPseudoProbeTable::emit(MCObjectStreamer *MCOS) {
while (Data < End) {
     GUID2FuncDescMap.emplace(GUID, MCPseudoProbeFuncDesc(GUID, Hash, Name));
   }
   assert(Data == End && "Have unprocessed data in pseudo_probe_desc section");
   return true;
 }
 
 bool MCPseudoProbeDecoder::buildAddress2ProbeMap(
     MCDecodedPseudoProbeInlineTree *Cur, uint64_t &LastAddr,
-    std::unordered_set<uint64_t> &GuildFilter) {
+    const Uint64Set &GuidFilter, const Uint64Map &FuncStartAddrs) {
   // The pseudo_probe section encodes an inline forest and each tree has a
-  // format like:
-  //  FUNCTION BODY (one for each uninlined function present in the text
-  //  section)
-  //     GUID (uint64)
-  //         GUID of the function
-  //     NPROBES (ULEB128)
-  //         Number of probes originating from this function.
-  //     NUM_INLINED_FUNCTIONS (ULEB128)
-  //         Number of callees inlined into this function, aka number of
-  //         first-level inlinees
-  //     PROBE RECORDS
-  //         A list of NPROBES entries. Each entry contains:
-  //           INDEX (ULEB128)
-  //           TYPE (uint4)
-  //             0 - block probe, 1 - indirect call, 2 - direct call
-  //           ATTRIBUTE (uint3)
-  //             1 - tail call, 2 - dangling
-  //           ADDRESS_TYPE (uint1)
-  //             0 - code address, 1 - address delta
-  //           CODE_ADDRESS (uint64 or ULEB128)
-  //             code address or address delta, depending on Flag
-  //     INLINED FUNCTION RECORDS
-  //         A list of NUM_INLINED_FUNCTIONS entries describing each of the
-  //         inlined callees.  Each record contains:
-  //           INLINE SITE
-  //             Index of the callsite probe (ULEB128)
-  //           FUNCTION BODY
-  //             A FUNCTION BODY entry describing the inlined function.
+  // format defined in MCPseudoProbe.h
 
   uint32_t Index = 0;
-  if (Cur == &DummyInlineRoot) {
+  bool IsTopLevelFunc = Cur == &DummyInlineRoot;
+  if (IsTopLevelFunc) {
     // Use a sequential id for top level inliner.
     Index = Cur->getChildren().size();
   } else {
     // Read inline site for inlinees
     auto ErrorOrIndex = readUnsignedNumber<uint32_t>();
     if (!ErrorOrIndex)
       return false;
     Index = std::move(*ErrorOrIndex);
   }
 
   // Read guid
   auto ErrorOrCurGuid = readUnencodedNumber<uint64_t>();
   if (!ErrorOrCurGuid)
     return false;
   uint64_t Guid = std::move(*ErrorOrCurGuid);
 
   // Decide if top-level node should be disgarded.
-  if (Cur == &DummyInlineRoot && !GuildFilter.empty() &&
-      !GuildFilter.count(Guid))
+  if (IsTopLevelFunc && !GuidFilter.empty() && !GuidFilter.count(Guid))
     Cur = nullptr;
 
   // If the incoming node is null, all its children nodes should be disgarded.
   if (Cur) {
     // Switch/add to a new tree node(inlinee)
     Cur = Cur->getOrAddNode(std::make_tuple(Guid, Index));
     Cur->Guid = Guid;
+    if (IsTopLevelFunc && !EncodingIsAddrBased) {
+      if (auto V = FuncStartAddrs.lookup(Guid))
+        LastAddr = V;
+    }
   }
 
   // Read number of probes in the current node.
   auto ErrorOrNodeCount = readUnsignedNumber<uint32_t>();
   if (!ErrorOrNodeCount)
     return false;
   uint32_t NodeCount = std::move(*ErrorOrNodeCount);
   // Read number of direct inlinees
if (Value & 0x80) {
         return false;
       int64_t Offset = std::move(*ErrorOrOffset);
       Addr = LastAddr + Offset;
     } else {
       auto ErrorOrAddr = readUnencodedNumber<int64_t>();
       if (!ErrorOrAddr)
         return false;
       Addr = std::move(*ErrorOrAddr);
+      if (isSentinelProbe(Attr)) {
+        // For sentinel probe, the addr field actually stores the GUID of the
+        // split function. Convert it to the real address.
+        if (auto V = FuncStartAddrs.lookup(Addr))
+          Addr = V;
+      } else {
+        // For now we assume all probe encoding should be either based on
+        // leading probe address or function start address.
+        // The scheme is for downwards compatibility.
+        // TODO: retire this scheme once compatibility is no longer an issue.
+        EncodingIsAddrBased = true;
+      }
     }
 
-    if (Cur) {
+    if (Cur && !isSentinelProbe(Attr)) {
       // Populate Address2ProbesMap
       auto &Probes = Address2ProbesMap[Addr];
       Probes.emplace_back(Addr, Cur->Guid, Index, PseudoProbeType(Kind), Attr,
                           Cur);
       Cur->addProbes(&Probes.back());
     }
     LastAddr = Addr;
   }
 
   uint32_t ChildrenToProcess = std::move(*ErrorOrCurChildrenToProcess);
   for (uint32_t I = 0; I < ChildrenToProcess; I++) {
-    buildAddress2ProbeMap(Cur, LastAddr, GuildFilter);
+    buildAddress2ProbeMap(Cur, LastAddr, GuidFilter, FuncStartAddrs);
   }
 
   return true;
 }
 
 bool MCPseudoProbeDecoder::buildAddress2ProbeMap(
-    const uint8_t *Start, std::size_t Size,
-    std::unordered_set<uint64_t> &GuildFilter) {
+    const uint8_t *Start, std::size_t Size, const Uint64Set &GuidFilter,
+    const Uint64Map &FuncStartAddrs) {
   Data = Start;
   End = Data + Size;
   uint64_t LastAddr = 0;
   while (Data < End)
-    buildAddress2ProbeMap(&DummyInlineRoot, LastAddr, GuildFilter);
+    buildAddress2ProbeMap(&DummyInlineRoot, LastAddr, GuidFilter,
+                          FuncStartAddrs);
   assert(Data == End && "Have unprocessed data in pseudo_probe section");
   return true;
 }
 
-bool MCPseudoProbeDecoder::buildAddress2ProbeMap(const uint8_t *Start,
-                                                 std::size_t Size) {
-  std::unordered_set<uint64_t> GuildFilter;
-  return buildAddress2ProbeMap(Start, Size, GuildFilter);
-}
-
 void MCPseudoProbeDecoder::printGUID2FuncDescMap(raw_ostream &OS) {
   OS << "Pseudo Probe Desc:\n";
   // Make the output deterministic
   std::map<uint64_t, MCPseudoProbeFuncDesc> OrderedMap(GUID2FuncDescMap.begin(),
                                                        GUID2FuncDescMap.end());
   for (auto &I : OrderedMap) {
     I.second.print(OS);
   }

llvm/lib/MC/MCStreamer.cpp

void MCStreamer::emitInstruction(const MCInst &Inst, const MCSubtargetInfo &) {
   // Scan for values.
   for (unsigned i = Inst.getNumOperands(); i--;)
     if (Inst.getOperand(i).isExpr())
       visitUsedExpr(*Inst.getOperand(i).getExpr());
 }
 
 void MCStreamer::emitPseudoProbe(uint64_t Guid, uint64_t Index, uint64_t Type,
                                  uint64_t Attr,
-                                 const MCPseudoProbeInlineStack &InlineStack) {
+                                 const MCPseudoProbeInlineStack &InlineStack,
+                                 MCSymbol *FnSym) {
   auto &Context = getContext();
 
   // Create a symbol at in the current section for use in the probe.
   MCSymbol *ProbeSym = Context.createTempSymbol();
 
   // Set the value of the symbol to use for the MCPseudoProbe.
   emitLabel(ProbeSym);
 
   // Create a (local) probe entry with the symbol.
   MCPseudoProbe Probe(ProbeSym, Guid, Index, Type, Attr);
 
   // Add the probe entry to this section's entries.
   Context.getMCPseudoProbeTable().getProbeSections().addPseudoProbe(
-      getCurrentSectionOnly(), Probe, InlineStack);
+      FnSym, Probe, InlineStack);
 }
 
 void MCStreamer::emitAbsoluteSymbolDiff(const MCSymbol *Hi, const MCSymbol *Lo,
                                         unsigned Size) {
   // Get the Hi-Lo expression.
   const MCExpr *Diff =
       MCBinaryExpr::createSub(MCSymbolRefExpr::create(Hi, Context),
                               MCSymbolRefExpr::create(Lo, Context), Context);

llvm/test/Transforms/SampleProfile/pseudo-probe-emit-inline.ll

 ; REQUIRES: x86_64-linux
 ; RUN: opt < %s -passes='pseudo-probe,cgscc(inline)' -function-sections -mtriple=x86_64-unknown-linux-gnu -S -o %t
 ; RUN: FileCheck %s < %t --check-prefix=CHECK-IL
 ; RUN: llc -function-sections <%t -filetype=asm -o %t1
 ; RUN: FileCheck %s < %t1 --check-prefix=CHECK-ASM
 ; RUN: llc -function-sections <%t -filetype=obj -o %t2
 ; RUN: llvm-objdump --section-headers  %t2 | FileCheck %s --check-prefix=CHECK-OBJ
 ; RUN: llvm-mc -filetype=asm <%t1 -o %t3
 ; RUN: FileCheck %s < %t3 --check-prefix=CHECK-ASM
 ; RUN: llvm-mc -filetype=obj <%t1 -o %t4
 ; RUN: llvm-objdump --section-headers  %t4 | FileCheck %s --check-prefix=CHECK-OBJ
 
+
 define dso_local void @foo2() !dbg !7 {
 ; CHECK-IL:  call void @llvm.pseudoprobe(i64 [[#GUID1:]], i64 1, i32 0, i64 -1), !dbg ![[#]]
-; CHECK-ASM: .pseudoprobe [[#GUID1:]] 1 0 0
+; CHECK-ASM: .pseudoprobe [[#GUID1:]] 1 0 0 foo2
   ret void, !dbg !10
 }
 
 define dso_local void @foo() #0 !dbg !11 {
 ; CHECK-IL:  call void @llvm.pseudoprobe(i64 [[#GUID2:]], i64 1, i32 0, i64 -1), !dbg ![[#]]
 ; CHECK-IL:  call void @llvm.pseudoprobe(i64 [[#GUID1]], i64 1, i32 0, i64 -1), !dbg ![[#DL1:]]
-; CHECK-ASM: .pseudoprobe [[#GUID2:]] 1 0 0
-; CHECK-ASM: .pseudoprobe [[#GUID1]] 1 0 0 @ [[#GUID2]]:2
+; CHECK-ASM: .pseudoprobe [[#GUID2:]] 1 0 0 foo
+; CHECK-ASM: .pseudoprobe [[#GUID1]] 1 0 0 @ [[#GUID2]]:2 foo
   call void @foo2(), !dbg !12
   ret void, !dbg !13
 }
 
 define dso_local i32 @entry() !dbg !14 {
 ; CHECK-IL:  call void @llvm.pseudoprobe(i64 [[#GUID3:]], i64 1, i32 0, i64 -1), !dbg ![[#]]
 ; CHECK-IL:  call void @llvm.pseudoprobe(i64 [[#GUID2]], i64 1, i32 0, i64 -1), !dbg ![[#DL2:]]
 ; CHECK-IL:  call void @llvm.pseudoprobe(i64 [[#GUID1]], i64 1, i32 0, i64 -1), !dbg ![[#DL3:]]
-; CHECK-ASM: .pseudoprobe [[#GUID3:]] 1 0 0
-; CHECK-ASM: .pseudoprobe [[#GUID2]] 1 0 0 @ [[#GUID3]]:2
-; CHECK-ASM: .pseudoprobe [[#GUID1]] 1 0 0 @ [[#GUID3]]:2 @ [[#GUID2]]:2
+; CHECK-ASM: .pseudoprobe [[#GUID3:]] 1 0 0 entry
+; CHECK-ASM: .pseudoprobe [[#GUID2]] 1 0 0 @ [[#GUID3]]:2 entry
+; CHECK-ASM: .pseudoprobe [[#GUID1]] 1 0 0 @ [[#GUID3]]:2 @ [[#GUID2]]:2 entry
   call void @foo(), !dbg !18
   ret i32 0, !dbg !19
 }
 
 
 ; CHECK-IL: ![[#SCOPE1:]] = distinct !DISubprogram(name: "foo2"
 ; CHECK-IL: ![[#SCOPE2:]] = distinct !DISubprogram(name: "foo"
 ; CHECK-IL: ![[#DL1]] = !DILocation(line: 3, column: 1,  scope: ![[#SCOPE1]], inlinedAt: ![[#INL1:]])

 ; CHECK-ASM-NEXT: .section .pseudo_probe_desc,"G",@progbits,.pseudo_probe_desc_entry,comdat
 ; CHECK-ASM-NEXT: .quad [[#GUID3]]
 ; CHECK-ASM-NEXT: .quad [[#HASH3:]]
 ; CHECK-ASM-NEXT: .byte 5
 ; CHECK-ASM-NEXT: .ascii "entry"
 
 ; CHECK-OBJ: .pseudo_probe_desc
 ; CHECK-OBJ: .pseudo_probe
+; CHECK-OBJ-NOT: .rela.pseudo_probe
 
 !llvm.dbg.cu = !{!0}
 !llvm.module.flags = !{!3, !4}
 
 !0 = distinct !DICompileUnit(language: DW_LANG_C99, file: !1, emissionKind: FullDebug)
 !1 = !DIFile(filename: "foo.c", directory: "any")
 !2 = !{}
 !3 = !{i32 2, !"Dwarf Version", i32 4}

llvm/test/Transforms/SampleProfile/pseudo-probe-emit.ll

 
 @a = dso_local global i32 0, align 4
 
 define void @foo(i32 %x) !dbg !3 {
 bb0:
   %cmp = icmp eq i32 %x, 0
 ; CHECK-IL: call void @llvm.pseudoprobe(i64 [[#GUID:]], i64 1, i32 0, i64 -1), !dbg ![[#FAKELINE:]]
 ; CHECK-MIR: PSEUDO_PROBE [[#GUID:]], 1, 0, 0
-; CHECK-ASM: .pseudoprobe [[#GUID:]] 1 0 0
+; CHECK-ASM: .pseudoprobe [[#GUID:]] 1 0 0 foo
   br i1 %cmp, label %bb1, label %bb2
 
 bb1:
 ; CHECK-IL: call void @llvm.pseudoprobe(i64 [[#GUID:]], i64 2, i32 0, i64 -1), !dbg ![[#FAKELINE]]
 ; CHECK-MIR: PSEUDO_PROBE [[#GUID]], 3, 0, 0
 ; CHECK-MIR: PSEUDO_PROBE [[#GUID]], 4, 0, 0
-; CHECK-ASM: .pseudoprobe [[#GUID]] 3 0 0
-; CHECK-ASM: .pseudoprobe [[#GUID]] 4 0 0
+; CHECK-ASM: .pseudoprobe [[#GUID]] 3 0 0 foo
+; CHECK-ASM: .pseudoprobe [[#GUID]] 4 0 0 foo
   store i32 6, ptr @a, align 4
   br label %bb3
 
 bb2:
 ; CHECK-IL: call void @llvm.pseudoprobe(i64 [[#GUID:]], i64 3, i32 0, i64 -1), !dbg ![[#FAKELINE]]
 ; CHECK-MIR: PSEUDO_PROBE [[#GUID]], 2, 0, 0
 ; CHECK-MIR: PSEUDO_PROBE [[#GUID]], 4, 0, 0
-; CHECK-ASM: .pseudoprobe [[#GUID]] 2 0 0
-; CHECK-ASM: .pseudoprobe [[#GUID]] 4 0 0
+; CHECK-ASM: .pseudoprobe [[#GUID]] 2 0 0 foo
+; CHECK-ASM: .pseudoprobe [[#GUID]] 4 0 0 foo
   store i32 8, ptr @a, align 4
   br label %bb3
 
 bb3:
 ; CHECK-IL: call void @llvm.pseudoprobe(i64 [[#GUID]], i64 4, i32 0, i64 -1), !dbg ![[#REALLINE:]]
   ret void, !dbg !12
 }
 
-declare void @bar(i32 %x) 
+declare void @bar(i32 %x)
 
 define internal void @foo2(ptr %f) !dbg !4 {
 entry:
 ; CHECK-IL: call void @llvm.pseudoprobe(i64 [[#GUID2:]], i64 1, i32 0, i64 -1)
 ; CHECK-MIR: PSEUDO_PROBE [[#GUID2:]], 1, 0, 0
-; CHECK-ASM: .pseudoprobe [[#GUID2:]] 1 0 0
+; CHECK-ASM: .pseudoprobe [[#GUID2:]] 1 0 0 foo2
 ; Check pseudo_probe metadata attached to the indirect call instruction.
 ; CHECK-IL: call void %f(i32 1), !dbg ![[#PROBE0:]]
 ; CHECK-MIR: PSEUDO_PROBE [[#GUID2]], 2, 1, 0
-; CHECK-ASM: .pseudoprobe [[#GUID2]] 2 1 0
+; CHECK-ASM: .pseudoprobe [[#GUID2]] 2 1 0 foo2
   call void %f(i32 1), !dbg !13
 ; Check pseudo_probe metadata attached to the direct call instruction.
 ; CHECK-IL: call void @bar(i32 1), !dbg ![[#PROBE1:]]
 ; CHECK-MIR: PSEUDO_PROBE [[#GUID2]], 3, 2, 0
-; CHECK-ASM: .pseudoprobe [[#GUID2]] 3 2 0
+; CHECK-ASM: .pseudoprobe [[#GUID2]] 3 2 0 foo2
   call void @bar(i32 1)
   ret void
 }
 
 ; CHECK-IL: Function Attrs: inaccessiblememonly nocallback nofree nosync nounwind willreturn
 ; CHECK-IL-NEXT: declare void @llvm.pseudoprobe(i64, i64, i32, i64)
 
 ; CHECK-IL: ![[#FOO:]] = distinct !DISubprogram(name: "foo"

 ; CHECK-ASM-NEXT: .ascii  "foo"
 ; CHECK-ASM-NEXT: .section  .pseudo_probe_desc,"G",@progbits,.pseudo_probe_desc_foo2,comdat
 ; CHECK-ASM-NEXT: .quad [[#GUID2]]
 ; CHECK-ASM-NEXT: .quad [[#HASH2:]]
 ; CHECK-ASM-NEXT: .byte 4
 ; CHECK-ASM-NEXT: .ascii  "foo2"
 
 ; CHECK-OBJ-COUNT-2: .pseudo_probe_desc
-; CHECK-OBJ-COUNT-2: .pseudo_probe
+; CHECK-OBJ: .pseudo_probe
+; CHECK-OBJ-NOT: .rela.pseudo_probe
 
 !llvm.dbg.cu = !{!0}
 !llvm.module.flags = !{!9, !10}
 
 !0 = distinct !DICompileUnit(language: DW_LANG_C99, file: !1)
 !1 = !DIFile(filename: "test.c", directory: "")
 !2 = !{}
 !3 = distinct !DISubprogram(name: "foo", scope: !1, file: !1, line: 1, type: !5, unit: !0, retainedNodes: !2)

llvm/test/tools/llvm-profgen/inline-force-dwarf.test

 ; RUN: llvm-profgen --format=text --ignore-stack-samples --use-dwarf-correlation --perfscript=%S/Inputs/inline-cs-pseudoprobe.perfscript --binary=%S/Inputs/inline-cs-pseudoprobe.perfbin --output=%t --profile-summary-cold-count=0
 ; RUN: FileCheck %s --input-file %t
 
 ; CHECK:     main:1109:0
 ; CHECK-NEXT: 0: 0
 ; CHECK-NEXT: 2: 0
 ; CHECK-NEXT: 1: foo:1109
 ; CHECK-NEXT:  2: 14
 ; CHECK-NEXT:  3: 15
 ; CHECK-NEXT:  4: 0
-; CHECK-NEXT:  65526: 14
-; CHECK-NEXT:  3: bar:224
+; CHECK-NEXT:  65525: 14
+; CHECK-NEXT:  3: bar:196
 ; CHECK-NEXT:   1: 14
-; CHECK-NEXT:   65533: 14
 
 
 ; 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>
 

llvm/tools/llvm-profgen/ProfileGenerator.cpp

void CSProfileGenerator::generateProfile() {
 
   if (Binary->getTrackFuncContextSize())
     computeSizeForProfiledFunctions();
 
   postProcessProfiles();
 }
 
 void CSProfileGenerator::computeSizeForProfiledFunctions() {
-  std::unordered_set<const BinaryFunction *> ProfiledFunctions;
   for (auto *Func : Binary->getProfiledFunctions())
     Binary->computeInlinedContextSizeForFunc(Func);
 
   // Flush the symbolizer to save memory.
   Binary->flushSymbolizer();
 }
 
 void CSProfileGenerator::updateFunctionSamples() {

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 "ErrorHandling.h"
+#include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/StringSet.h"
 #include "llvm/DebugInfo/DWARF/DWARFContext.h"
 #include "llvm/DebugInfo/Symbolize/Symbolize.h"
 #include "llvm/MC/MCAsmInfo.h"
 #include "llvm/MC/MCContext.h"
 #include "llvm/MC/MCDisassembler/MCDisassembler.h"
public:
   uint32_t getFuncSizeForContext(const ContextTrieNode *Context);
 
   // For inlinees that are full optimized away, we can establish zero size using
   // their remaining probes.
   void trackInlineesOptimizedAway(MCPseudoProbeDecoder &ProbeDecoder);
 
   using ProbeFrameStack = SmallVector<std::pair<StringRef, uint32_t>>;
   void trackInlineesOptimizedAway(MCPseudoProbeDecoder &ProbeDecoder,
                                   MCDecodedPseudoProbeInlineTree &ProbeNode,
                                   ProbeFrameStack &Context);
 
   void dump() { RootContext.dumpTree(); }
 
 private:
   // Root node for context trie tree, node that this is a reverse context trie
   // with callee as parent and caller as child. This way we can traverse from
   // root to find the best/longest matching context if an exact match does not
   // exist. It gives us the best possible estimate for function's post-inline,
class ProfiledBinary {
   std::set<std::pair<uint64_t, uint64_t>> TextSections;
 
   // A map of mapping function name to BinaryFunction info.
   std::unordered_map<std::string, BinaryFunction> BinaryFunctions;
 
   // A list of binary functions that have samples.
   std::unordered_set<const BinaryFunction *> ProfiledFunctions;
 
+  // GUID to Elf symbol start address map
+  DenseMap<uint64_t, uint64_t> SymbolStartAddrs;
+
+  // Start address to Elf symbol GUID map
+  std::unordered_multimap<uint64_t, uint64_t> StartAddrToSymMap;
+
   // An ordered map of mapping function's start address to function range
-  // relevant info. Currently to determine if the address of ELF is the start of
+  // relevant info. Currently to determine if the offset of ELF is the start of
   // a real function, we leverage the function range info from DWARF.
   std::map<uint64_t, FuncRange> StartAddrToFuncRangeMap;
 
   // Address to context location map. Used to expand the context.
   std::unordered_map<uint64_t, SampleContextFrameVector> AddressToLocStackMap;
 
   // Address to instruction size map. Also used for quick Address lookup.
   std::unordered_map<uint64_t, uint64_t> AddressToInstSizeMap;
class ProfiledBinary {
   // the preferred address
   bool IsLoadedByMMap = false;
   // Use to avoid redundant warning.
   bool MissingMMapWarned = false;
 
   void setPreferredTextSegmentAddresses(const ELFObjectFileBase *O);
 
   template <class ELFT>
-  void setPreferredTextSegmentAddresses(const ELFFile<ELFT> &Obj, StringRef FileName);
+  void setPreferredTextSegmentAddresses(const ELFFile<ELFT> &Obj,
+                                        StringRef FileName);
 
   void checkPseudoProbe(const ELFObjectFileBase *Obj);
 
   void decodePseudoProbe(const ELFObjectFileBase *Obj);
 
   void
   checkUseFSDiscriminator(const ELFObjectFileBase *Obj,
                           std::map<SectionRef, SectionSymbolsTy> &AllSymbols);
 
   // Set up disassembler and related components.
   void setUpDisassembler(const ELFObjectFileBase *Obj);
   void setupSymbolizer();
 
   // Load debug info of subprograms from DWARF section.
   void loadSymbolsFromDWARF(ObjectFile &Obj);
 
   // Load debug info from DWARF unit.
   void loadSymbolsFromDWARFUnit(DWARFUnit &CompilationUnit);
 
+  // Create elf symbol to its start address mapping.
+  void populateElfSymbolAddressList(const ELFObjectFileBase *O);
+
   // A function may be spilt into multiple non-continuous address ranges. We use
   // this to set whether start address of a function is the real entry of the
   // function and also set false to the non-function label.
   void setIsFuncEntry(uint64_t Address, StringRef RangeSymName);
 
   // Warn if no entry range exists in the function.
   void warnNoFuncEntry();
 
public:
   uint64_t getBaseAddress() const { return BaseAddress; }
   void setBaseAddress(uint64_t Address) { BaseAddress = Address; }
 
   // Canonicalize to use preferred load address as base address.
   uint64_t canonicalizeVirtualAddress(uint64_t Address) {
     return Address - BaseAddress + getPreferredBaseAddress();
   }
   // Return the preferred load address for the first executable segment.
-  uint64_t getPreferredBaseAddress() const { return PreferredTextSegmentAddresses[0]; }
+  uint64_t getPreferredBaseAddress() const {
+    return PreferredTextSegmentAddresses[0];
+  }
   // Return the preferred load address for the first loadable segment.
   uint64_t getFirstLoadableAddress() const { return FirstLoadableAddress; }
   // Return the file offset for the first executable segment.
   uint64_t getTextSegmentOffset() const { return TextSegmentOffsets[0]; }
   const std::vector<uint64_t> &getPreferredTextSegmentAddresses() const {
     return PreferredTextSegmentAddresses;
   }
   const std::vector<uint64_t> &getTextSegmentOffsets() const {

llvm/tools/llvm-profgen/ProfiledBinary.cpp

void ProfiledBinary::load() {
   // Current only support X86
   if (!TheTriple.isX86())
     exitWithError("unsupported target", TheTriple.getTriple());
   LLVM_DEBUG(dbgs() << "Loading " << Path << "\n");
 
   // Find the preferred load address for text sections.
   setPreferredTextSegmentAddresses(Obj);
 
-  checkPseudoProbe(Obj);
-
-  if (ShowDisassemblyOnly)
-    decodePseudoProbe(Obj);
-
   // Load debug info of subprograms from DWARF section.
   // If path of debug info binary is specified, use the debug info from it,
   // otherwise use the debug info from the executable binary.
   if (!DebugBinaryPath.empty()) {
     OwningBinary<Binary> DebugPath =
         unwrapOrError(createBinary(DebugBinaryPath), DebugBinaryPath);
     loadSymbolsFromDWARF(*cast<ObjectFile>(DebugPath.getBinary()));
   } else {
     loadSymbolsFromDWARF(*cast<ObjectFile>(&ExeBinary));
   }
 
+  DisassembleFunctionSet.insert(DisassembleFunctions.begin(),
+                                DisassembleFunctions.end());
+
+  checkPseudoProbe(Obj);
+
+  if (UsePseudoProbes)
+    populateElfSymbolAddressList(Obj);
+
+  if (ShowDisassemblyOnly)
+    decodePseudoProbe(Obj);
+
   // Disassemble the text sections.
   disassemble(Obj);
 
   // Use function start and return address to infer prolog and epilog
   ProEpilogTracker.inferPrologAddresses(StartAddrToFuncRangeMap);
   ProEpilogTracker.inferEpilogAddresses(RetAddressSet);
 
   warnNoFuncEntry();
void ProfiledBinary::checkPseudoProbe(const ELFObjectFileBase *Obj) {
   // set UsePseudoProbes flag, used for PerfReader
   UsePseudoProbes = HasProbeDescSection && HasPseudoProbeSection;
 }
 
 void ProfiledBinary::decodePseudoProbe(const ELFObjectFileBase *Obj) {
   if (!UsePseudoProbes)
     return;
 
-  std::unordered_set<uint64_t> ProfiledGuids;
-  if (!ShowDisassemblyOnly)
-    for (auto *F : ProfiledFunctions)
-      ProfiledGuids.insert(Function::getGUID(F->FuncName));
+  MCPseudoProbeDecoder::Uint64Set GuidFilter;
+  MCPseudoProbeDecoder::Uint64Map FuncStartAddresses;
+  if (ShowDisassemblyOnly) {
+    if (DisassembleFunctionSet.empty()) {
+      FuncStartAddresses = SymbolStartAddrs;
+    } else {
+      for (auto &F : DisassembleFunctionSet) {
+        auto GUID = Function::getGUID(F.first());
+        if (auto StartAddr = SymbolStartAddrs.lookup(GUID)) {
+          FuncStartAddresses[GUID] = StartAddr;
+          FuncRange &Range = StartAddrToFuncRangeMap[StartAddr];
+          GuidFilter.insert(Function::getGUID(Range.getFuncName()));
+        }
+      }
+    }
+  } else {
+    for (auto *F : ProfiledFunctions) {
+      GuidFilter.insert(Function::getGUID(F->FuncName));
+      for (auto &Range : F->Ranges) {
+        auto GUIDs = StartAddrToSymMap.equal_range(Range.first);
+        for (auto I = GUIDs.first; I != GUIDs.second; ++I)
+          FuncStartAddresses[I->second] = I->first;
+      }
+    }
+  }
 
   StringRef FileName = Obj->getFileName();
   for (section_iterator SI = Obj->section_begin(), SE = Obj->section_end();
        SI != SE; ++SI) {
     const SectionRef &Section = *SI;
     StringRef SectionName = unwrapOrError(Section.getName(), FileName);
 
     if (SectionName == ".pseudo_probe_desc") {
       StringRef Contents = unwrapOrError(Section.getContents(), FileName);
       if (!ProbeDecoder.buildGUID2FuncDescMap(
               reinterpret_cast<const uint8_t *>(Contents.data()),
               Contents.size()))
         exitWithError(
             "Pseudo Probe decoder fail in .pseudo_probe_desc section");
     } else if (SectionName == ".pseudo_probe") {
       StringRef Contents = unwrapOrError(Section.getContents(), FileName);
       if (!ProbeDecoder.buildAddress2ProbeMap(
               reinterpret_cast<const uint8_t *>(Contents.data()),
-              Contents.size(), ProfiledGuids))
+              Contents.size(), GuidFilter, FuncStartAddresses))
         exitWithError("Pseudo Probe decoder fail in .pseudo_probe section");
     }
   }
 
   // Build TopLevelProbeFrameMap to track size for optimized inlinees when probe
   // is available
   if (TrackFuncContextSize) {
     for (const auto &Child : ProbeDecoder.getDummyInlineRoot().getChildren()) {
for (const SymbolRef &Symbol : Obj->symbols()) {
     if (SecI != Obj->section_end())
       AllSymbols[*SecI].push_back(SymbolInfoTy(Addr, Name, ELF::STT_NOTYPE));
   }
 
   // Sort all the symbols. Use a stable sort to stabilize the output.
   for (std::pair<const SectionRef, SectionSymbolsTy> &SecSyms : AllSymbols)
     stable_sort(SecSyms.second);
 
-  DisassembleFunctionSet.insert(DisassembleFunctions.begin(),
-                                DisassembleFunctions.end());
   assert((DisassembleFunctionSet.empty() || ShowDisassemblyOnly) &&
          "Functions to disassemble should be only specified together with "
          "--show-disassembly-only");
 
   if (ShowDisassemblyOnly)
     outs() << "\nDisassembly of " << FileName << ":\n";
 
   // Dissassemble a text section.
for (std::size_t SI = 0, SE = Symbols.size(); SI != SE; ++SI) {
       if (Symbols[SI].Name == FSDiscriminatorVar) {
         UseFSDiscriminator = true;
         return;
       }
     }
   }
 }
 
+void ProfiledBinary::populateElfSymbolAddressList(
+    const ELFObjectFileBase *Obj) {
+  // Create a mapping from virtual address to symbol GUID and the other way
+  // around.
+  StringRef FileName = Obj->getFileName();
+  for (const SymbolRef &Symbol : Obj->symbols()) {
+    const uint64_t Addr = unwrapOrError(Symbol.getAddress(), FileName);
+    const StringRef Name = unwrapOrError(Symbol.getName(), FileName);
+    uint64_t GUID = Function::getGUID(Name);
+    SymbolStartAddrs[GUID] = Addr;
+    StartAddrToSymMap.emplace(Addr, GUID);
+  }
+}
+
 void ProfiledBinary::loadSymbolsFromDWARFUnit(DWARFUnit &CompilationUnit) {
   for (const auto &DieInfo : CompilationUnit.dies()) {
     llvm::DWARFDie Die(&CompilationUnit, &DieInfo);
 
     if (!Die.isSubprogramDIE())
       continue;
     auto Name = Die.getName(llvm::DINameKind::LinkageName);
     if (!Name)