[BOLT][NFCI] Migrate pseudo probes to MetadataRewriter interface

[maksfb]

Summary

Use new MetdataRewriter interface to update pseudo probes.

Depends on D154021

[maksfb]

Rebase.

[maksfb]

Rebase.

[Amir]

LG. I didn't notice before that pseudo-probe section was added to the list of debug sections to overwrite.

bolt/include/bolt/Core/BinaryFunction.h

private:
   uint32_t Index{-1U};
 
   /// Get basic block index assuming it belongs to this function.
   unsigned getIndex(const BinaryBasicBlock *BB) const {
     assert(BB->getIndex() < BasicBlocks.size());
     return BB->getIndex();
   }
 
-  /// Return basic block that originally contained offset \p Offset
-  /// from the function start.
-  BinaryBasicBlock *getBasicBlockContainingOffset(uint64_t Offset);
-
-  const BinaryBasicBlock *getBasicBlockContainingOffset(uint64_t Offset) const {
-    return const_cast<BinaryFunction *>(this)->getBasicBlockContainingOffset(
-        Offset);
-  }
-
-  /// Return basic block that started at offset \p Offset.
-  BinaryBasicBlock *getBasicBlockAtOffset(uint64_t Offset) {
-    BinaryBasicBlock *BB = getBasicBlockContainingOffset(Offset);
-    return BB && BB->getOffset() == Offset ? BB : nullptr;
-  }
-
   /// Release memory taken by the list.
   template <typename T> BinaryFunction &clearList(T &List) {
     T TempList;
     TempList.swap(List);
     return *this;
   }
 
   /// Update the indices of all the basic blocks starting at StartIndex.
public:
   BinaryBasicBlock *getBasicBlockForLabel(const MCSymbol *Label) {
     return LabelToBB.lookup(Label);
   }
 
   const BinaryBasicBlock *getBasicBlockForLabel(const MCSymbol *Label) const {
     return LabelToBB.lookup(Label);
   }
 
+  /// Return basic block that originally contained offset \p Offset
+  /// from the function start.
+  BinaryBasicBlock *getBasicBlockContainingOffset(uint64_t Offset);
+
+  const BinaryBasicBlock *getBasicBlockContainingOffset(uint64_t Offset) const {
+    return const_cast<BinaryFunction *>(this)->getBasicBlockContainingOffset(
+        Offset);
+  }
+
+  /// Return basic block that started at offset \p Offset.
+  BinaryBasicBlock *getBasicBlockAtOffset(uint64_t Offset) {
+    BinaryBasicBlock *BB = getBasicBlockContainingOffset(Offset);
+    return BB && BB->getOffset() == Offset ? BB : nullptr;
+  }
+
   /// Retrieve the landing pad BB associated with invoke instruction \p Invoke
   /// that is in \p BB. Return nullptr if none exists
   BinaryBasicBlock *getLandingPadBBFor(const BinaryBasicBlock &BB,
                                        const MCInst &InvokeInst) const {
     assert(BC.MIB->isInvoke(InvokeInst) && "must be invoke instruction");
     const std::optional<MCPlus::MCLandingPad> LP =
         BC.MIB->getEHInfo(InvokeInst);
     if (LP && LP->first) {

bolt/include/bolt/Rewrite/MetadataRewriters.h

 namespace llvm {
 namespace bolt {
 
 class MetadataRewriter;
 class BinaryContext;
 
 // The list of rewriter build functions.
 
+std::unique_ptr<MetadataRewriter> createPseudoProbeRewriter(BinaryContext &);
+
 std::unique_ptr<MetadataRewriter> createSDTRewriter(BinaryContext &);
 
 } // namespace bolt
 } // namespace llvm
 
 #endif // BOLT_REWRITE_METADATA_REWRITERS_H

bolt/include/bolt/Rewrite/RewriteInstance.h

private:
   void processMetadataPreCFG();
 
   /// Update debug and other auxiliary information in the file.
   void updateMetadata();
 
   /// Update LKMarkers' locations for the output binary.
   void updateLKMarkers();
 
-  /// Update address of MCDecodedPseudoProbe.
-  void updatePseudoProbes();
-
-  /// Encode MCDecodedPseudoProbe.
-  void encodePseudoProbes();
-
   /// Return the list of code sections in the output order.
   std::vector<BinarySection *> getCodeSections();
 
   /// Map all sections to their final addresses.
   void mapFileSections(BOLTLinker::SectionMapper MapSection);
 
   /// Map code sections generated by BOLT.
   void mapCodeSections(BOLTLinker::SectionMapper MapSection);
#define ELF_FUNCTION(TYPE, FUNC)                                               \
   /// Return 0 if the address has no mapping in the file, including being
   /// part of .bss section.
   uint64_t getFileOffsetForAddress(uint64_t Address) const;
 
   /// Return true if we will overwrite contents of the section instead
   /// of appending contents to it.
   bool willOverwriteSection(StringRef SectionName);
 
-  /// Parse .pseudo_probe_desc section and .pseudo_probe section
-  /// Setup Pseudo probe decoder
-  void parsePseudoProbe();
-
 public:
   /// Standard ELF sections we overwrite.
   static constexpr const char *SectionsToOverwrite[] = {
       ".shstrtab",
       ".symtab",
       ".strtab",
   };
 
private:
 
   /// Exception handling and stack unwinding information in this binary.
   ErrorOr<BinarySection &> LSDASection{std::errc::bad_address};
   ErrorOr<BinarySection &> EHFrameSection{std::errc::bad_address};
 
   /// .note.gnu.build-id section.
   ErrorOr<BinarySection &> BuildIDSection{std::errc::bad_address};
 
-  /// .pseudo_probe_desc section.
-  /// Contains information about pseudo probe description, like its related
-  /// function
-  ErrorOr<BinarySection &> PseudoProbeDescSection{std::errc::bad_address};
-
-  /// .pseudo_probe section.
-  /// Contains information about pseudo probe details, like its address
-  ErrorOr<BinarySection &> PseudoProbeSection{std::errc::bad_address};
-
   /// Helper for accessing sections by name.
   BinarySection *getSection(const Twine &Name) {
     ErrorOr<BinarySection &> ErrOrSection = BC->getUniqueSectionByName(Name);
     return ErrOrSection ? &ErrOrSection.get() : nullptr;
   }
 
   /// A reference to the build-id bytes in the original binary
   StringRef BuildID;

bolt/lib/Rewrite/CMakeLists.txt

 add_llvm_library(LLVMBOLTRewrite
   BinaryPassManager.cpp
   BoltDiff.cpp
   DWARFRewriter.cpp
   ExecutableFileMemoryManager.cpp
   JITLinkLinker.cpp
   MachORewriteInstance.cpp
   MetadataManager.cpp
+  PseudoProbeRewriter.cpp
   RewriteInstance.cpp
   SDTRewriter.cpp
 
   DISABLE_LLVM_LINK_LLVM_DYLIB
 
   LINK_LIBS
   ${LLVM_PTHREAD_LIB}
   )

bolt/lib/Rewrite/PseudoProbeRewriter.cpp

+//===- bolt/Rewrite/PseudoProbeRewriter.cpp -------------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+//
+// Implement support for pseudo probes.
+//
+//===----------------------------------------------------------------------===//
+
+#include "bolt/Core/BinaryFunction.h"
+#include "bolt/Rewrite/MetadataRewriter.h"
+#include "bolt/Rewrite/MetadataRewriters.h"
+#include "bolt/Utils/CommandLineOpts.h"
+#include "llvm/IR/Function.h"
+#include "llvm/MC/MCPseudoProbe.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/LEB128.h"
+
+#undef DEBUG_TYPE
+#define DEBUG_TYPE "pseudo-probe-rewriter"
+
+using namespace llvm;
+using namespace bolt;
+
+namespace opts {
+
+enum PrintPseudoProbesOptions {
+  PPP_None = 0,
+  PPP_Probes_Section_Decode = 0x1,
+  PPP_Probes_Address_Conversion = 0x2,
+  PPP_Encoded_Probes = 0x3,
+  PPP_All = 0xf
+};
+
+static cl::opt<PrintPseudoProbesOptions> PrintPseudoProbes(
+    "print-pseudo-probes", cl::desc("print pseudo probe info"),
+    cl::init(PPP_None),
+    cl::values(clEnumValN(PPP_Probes_Section_Decode, "decode",
+                          "decode probes section from binary"),
+               clEnumValN(PPP_Probes_Address_Conversion, "address_conversion",
+                          "update address2ProbesMap with output block address"),
+               clEnumValN(PPP_Encoded_Probes, "encoded_probes",
+                          "display the encoded probes in binary section"),
+               clEnumValN(PPP_All, "all", "enable all debugging printout")),
+    cl::Hidden, cl::cat(BoltCategory));
+
+} // namespace opts
+
+namespace {
+class PseudoProbeRewriter final : public MetadataRewriter {
+  /// .pseudo_probe_desc section.
+  /// Contains information about pseudo probe description, like its related
+  /// function
+  ErrorOr<BinarySection &> PseudoProbeDescSection{std::errc::bad_address};
+
+  /// .pseudo_probe section.
+  /// Contains information about pseudo probe details, like its address
+  ErrorOr<BinarySection &> PseudoProbeSection{std::errc::bad_address};
+
+  /// Update address of MCDecodedPseudoProbe.
+  void updatePseudoProbes();
+
+  /// Encode MCDecodedPseudoProbe.
+  void encodePseudoProbes();
+
+  /// Parse .pseudo_probe_desc section and .pseudo_probe section
+  /// Setup Pseudo probe decoder
+  void parsePseudoProbe();
+
+  /// PseudoProbe decoder
+  MCPseudoProbeDecoder ProbeDecoder;
+
+public:
+  PseudoProbeRewriter(BinaryContext &BC)
+      : MetadataRewriter("pseudo-probe-rewriter", BC) {}
+
+  Error postEmitFinalizer() override;
+};
+
+Error PseudoProbeRewriter::postEmitFinalizer() {
+  parsePseudoProbe();
+  updatePseudoProbes();
+
+  return Error::success();
+}
+
+void PseudoProbeRewriter::parsePseudoProbe() {
+  PseudoProbeDescSection = BC.getUniqueSectionByName(".pseudo_probe_desc");
+  PseudoProbeSection = BC.getUniqueSectionByName(".pseudo_probe");
+
+  if (!PseudoProbeDescSection && !PseudoProbeSection) {
+    // pesudo probe is not added to binary. It is normal and no warning needed.
+    return;
+  }
+
+  // If only one section is found, it might mean the ELF is corrupted.
+  if (!PseudoProbeDescSection) {
+    errs() << "BOLT-WARNING: fail in reading .pseudo_probe_desc binary\n";
+    return;
+  } else if (!PseudoProbeSection) {
+    errs() << "BOLT-WARNING: fail in reading .pseudo_probe binary\n";
+    return;
+  }
+
+  StringRef Contents = PseudoProbeDescSection->getContents();
+  if (!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 (!ProbeDecoder.buildAddress2ProbeMap(
+          reinterpret_cast<const uint8_t *>(Contents.data()), Contents.size(),
+          GuidFilter, FuncStartAddrs)) {
+    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) {
+    outs() << "Report of decoding input pseudo probe binaries \n";
+    ProbeDecoder.printGUID2FuncDescMap(outs());
+    ProbeDecoder.printProbesForAllAddresses(outs());
+  }
+}
+
+void PseudoProbeRewriter::updatePseudoProbes() {
+  // check if there is pseudo probe section decoded
+  if (ProbeDecoder.getAddress2ProbesMap().empty())
+    return;
+  // input address converted to output
+  AddressProbesMap &Address2ProbesMap = ProbeDecoder.getAddress2ProbesMap();
+  const GUIDProbeFunctionMap &GUID2Func = ProbeDecoder.getGUID2FuncDescMap();
+
+  for (auto &AP : Address2ProbesMap) {
+    BinaryFunction *F = BC.getBinaryFunctionContainingAddress(AP.first);
+    // If F is removed, eliminate all probes inside it from inline tree
+    // Setting probes' addresses as INT64_MAX means elimination
+    if (!F) {
+      for (MCDecodedPseudoProbe &Probe : AP.second)
+        Probe.setAddress(INT64_MAX);
+      continue;
+    }
+    // If F is not emitted, the function will remain in the same address as its
+    // input
+    if (!F->isEmitted())
+      continue;
+
+    uint64_t Offset = AP.first - F->getAddress();
+    const BinaryBasicBlock *BB = F->getBasicBlockContainingOffset(Offset);
+    uint64_t BlkOutputAddress = BB->getOutputAddressRange().first;
+    // Check if block output address is defined.
+    // If not, such block is removed from binary. Then remove the probes from
+    // inline tree
+    if (BlkOutputAddress == 0) {
+      for (MCDecodedPseudoProbe &Probe : AP.second)
+        Probe.setAddress(INT64_MAX);
+      continue;
+    }
+
+    unsigned ProbeTrack = AP.second.size();
+    std::list<MCDecodedPseudoProbe>::iterator Probe = AP.second.begin();
+    while (ProbeTrack != 0) {
+      if (Probe->isBlock()) {
+        Probe->setAddress(BlkOutputAddress);
+      } else if (Probe->isCall()) {
+        // A call probe may be duplicated due to ICP
+        // Go through output of InputOffsetToAddressMap to collect all related
+        // probes
+        const InputOffsetToAddressMapTy &Offset2Addr =
+            F->getInputOffsetToAddressMap();
+        auto CallOutputAddresses = Offset2Addr.equal_range(Offset);
+        auto CallOutputAddress = CallOutputAddresses.first;
+        if (CallOutputAddress == CallOutputAddresses.second) {
+          Probe->setAddress(INT64_MAX);
+        } else {
+          Probe->setAddress(CallOutputAddress->second);
+          CallOutputAddress = std::next(CallOutputAddress);
+        }
+
+        while (CallOutputAddress != CallOutputAddresses.second) {
+          AP.second.push_back(*Probe);
+          AP.second.back().setAddress(CallOutputAddress->second);
+          Probe->getInlineTreeNode()->addProbes(&(AP.second.back()));
+          CallOutputAddress = std::next(CallOutputAddress);
+        }
+      }
+      Probe = std::next(Probe);
+      ProbeTrack--;
+    }
+  }
+
+  if (opts::PrintPseudoProbes == opts::PrintPseudoProbesOptions::PPP_All ||
+      opts::PrintPseudoProbes ==
+          opts::PrintPseudoProbesOptions::PPP_Probes_Address_Conversion) {
+    outs() << "Pseudo Probe Address Conversion results:\n";
+    // table that correlates address to block
+    std::unordered_map<uint64_t, StringRef> Addr2BlockNames;
+    for (auto &F : BC.getBinaryFunctions())
+      for (BinaryBasicBlock &BinaryBlock : F.second)
+        Addr2BlockNames[BinaryBlock.getOutputAddressRange().first] =
+            BinaryBlock.getName();
+
+    // scan all addresses -> correlate probe to block when print out
+    std::vector<uint64_t> Addresses;
+    for (auto &Entry : Address2ProbesMap)
+      Addresses.push_back(Entry.first);
+    llvm::sort(Addresses);
+    for (uint64_t Key : Addresses) {
+      for (MCDecodedPseudoProbe &Probe : Address2ProbesMap[Key]) {
+        if (Probe.getAddress() == INT64_MAX)
+          outs() << "Deleted Probe: ";
+        else
+          outs() << "Address: " << format_hex(Probe.getAddress(), 8) << " ";
+        Probe.print(outs(), GUID2Func, true);
+        // print block name only if the probe is block type and undeleted.
+        if (Probe.isBlock() && Probe.getAddress() != INT64_MAX)
+          outs() << format_hex(Probe.getAddress(), 8) << " Probe is in "
+                 << Addr2BlockNames[Probe.getAddress()] << "\n";
+      }
+    }
+    outs() << "=======================================\n";
+  }
+
+  // encode pseudo probes with updated addresses
+  encodePseudoProbes();
+}
+
+void PseudoProbeRewriter::encodePseudoProbes() {
+  // Buffer for new pseudo probes section
+  SmallString<8> Contents;
+  MCDecodedPseudoProbe *LastProbe = nullptr;
+
+  auto EmitInt = [&](uint64_t Value, uint32_t Size) {
+    const bool IsLittleEndian = BC.AsmInfo->isLittleEndian();
+    uint64_t Swapped = support::endian::byte_swap(
+        Value, IsLittleEndian ? support::little : support::big);
+    unsigned Index = IsLittleEndian ? 0 : 8 - Size;
+    auto Entry = StringRef(reinterpret_cast<char *>(&Swapped) + Index, Size);
+    Contents.append(Entry.begin(), Entry.end());
+  };
+
+  auto EmitULEB128IntValue = [&](uint64_t Value) {
+    SmallString<128> Tmp;
+    raw_svector_ostream OSE(Tmp);
+    encodeULEB128(Value, OSE, 0);
+    Contents.append(OSE.str().begin(), OSE.str().end());
+  };
+
+  auto EmitSLEB128IntValue = [&](int64_t Value) {
+    SmallString<128> Tmp;
+    raw_svector_ostream OSE(Tmp);
+    encodeSLEB128(Value, OSE);
+    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();
+      EmitSLEB128IntValue(Delta);
+    } else {
+      // Emit absolute address for encoding the first pseudo probe.
+      uint32_t AddrSize = BC.AsmInfo->getCodePointerSize();
+      EmitInt(CurProbe->getAddress(), AddrSize);
+    }
+  };
+
+  std::map<InlineSite, MCDecodedPseudoProbeInlineTree *,
+           std::greater<InlineSite>>
+      Inlinees;
+
+  // DFS of inline tree to emit pseudo probes in all tree node
+  // Inline site index of a probe is emitted first.
+  // Then tree node Guid, size of pseudo probes and children nodes, and detail
+  // of contained probes are emitted Deleted probes are skipped Root node is not
+  // encoded to binaries. It's a "wrapper" of inline trees of each function.
+  std::list<std::pair<uint64_t, MCDecodedPseudoProbeInlineTree *>> NextNodes;
+  const MCDecodedPseudoProbeInlineTree &Root =
+      ProbeDecoder.getDummyInlineRoot();
+  for (auto Child = Root.getChildren().begin();
+       Child != Root.getChildren().end(); ++Child)
+    Inlinees[Child->first] = Child->second.get();
+
+  for (auto Inlinee : Inlinees)
+    // INT64_MAX is "placeholder" of unused callsite index field in the pair
+    NextNodes.push_back({INT64_MAX, Inlinee.second});
+
+  Inlinees.clear();
+
+  while (!NextNodes.empty()) {
+    uint64_t ProbeIndex = NextNodes.back().first;
+    MCDecodedPseudoProbeInlineTree *Cur = NextNodes.back().second;
+    NextNodes.pop_back();
+
+    if (Cur->Parent && !Cur->Parent->isRoot())
+      // Emit probe inline site
+      EmitULEB128IntValue(ProbeIndex);
+
+    // Emit probes grouped by GUID.
+    LLVM_DEBUG({
+      dbgs().indent(MCPseudoProbeTable::DdgPrintIndent);
+      dbgs() << "GUID: " << Cur->Guid << "\n";
+    });
+    // Emit Guid
+    EmitInt(Cur->Guid, 8);
+    // Emit number of probes in this node
+    uint64_t Deleted = 0;
+    for (MCDecodedPseudoProbe *&Probe : Cur->getProbes())
+      if (Probe->getAddress() == INT64_MAX)
+        Deleted++;
+    LLVM_DEBUG(dbgs() << "Deleted Probes:" << Deleted << "\n");
+    uint64_t ProbesSize = Cur->getProbes().size() - Deleted;
+    EmitULEB128IntValue(ProbesSize);
+    // Emit number of direct inlinees
+    EmitULEB128IntValue(Cur->getChildren().size());
+    // Emit probes in this group
+    for (MCDecodedPseudoProbe *&Probe : Cur->getProbes()) {
+      if (Probe->getAddress() == INT64_MAX)
+        continue;
+      EmitDecodedPseudoProbe(Probe);
+      LastProbe = Probe;
+    }
+
+    for (auto Child = Cur->getChildren().begin();
+         Child != Cur->getChildren().end(); ++Child)
+      Inlinees[Child->first] = Child->second.get();
+    for (const auto &Inlinee : Inlinees) {
+      assert(Cur->Guid != 0 && "non root tree node must have nonzero Guid");
+      NextNodes.push_back({std::get<1>(Inlinee.first), Inlinee.second});
+      LLVM_DEBUG({
+        dbgs().indent(MCPseudoProbeTable::DdgPrintIndent);
+        dbgs() << "InlineSite: " << std::get<1>(Inlinee.first) << "\n";
+      });
+    }
+    Inlinees.clear();
+  }
+
+  // Create buffer for new contents for the section
+  // Freed when parent section is destroyed
+  uint8_t *Output = new uint8_t[Contents.str().size()];
+  memcpy(Output, Contents.str().data(), Contents.str().size());
+  BC.registerOrUpdateSection(".pseudo_probe", PseudoProbeSection->getELFType(),
+                             PseudoProbeSection->getELFFlags(), Output,
+                             Contents.str().size(), 1);
+  if (opts::PrintPseudoProbes == opts::PrintPseudoProbesOptions::PPP_All ||
+      opts::PrintPseudoProbes ==
+          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(), GuidFilter, FuncStartAddrs);
+    DummyDecoder.printProbesForAllAddresses(outs());
+  }
+}
+} // namespace
+
+std::unique_ptr<MetadataRewriter>
+llvm::bolt::createPseudoProbeRewriter(BinaryContext &BC) {
+  return std::make_unique<PseudoProbeRewriter>(BC);
+}

bolt/lib/Rewrite/RewriteInstance.cpp

 #include "bolt/RuntimeLibs/HugifyRuntimeLibrary.h"
 #include "bolt/RuntimeLibs/InstrumentationRuntimeLibrary.h"
 #include "bolt/Utils/CommandLineOpts.h"
 #include "bolt/Utils/Utils.h"
 #include "llvm/ADT/AddressRanges.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/DebugInfo/DWARF/DWARFContext.h"
 #include "llvm/DebugInfo/DWARF/DWARFDebugFrame.h"
-#include "llvm/IR/Function.h"
 #include "llvm/MC/MCAsmBackend.h"
 #include "llvm/MC/MCAsmInfo.h"
 #include "llvm/MC/MCAsmLayout.h"
 #include "llvm/MC/MCDisassembler/MCDisassembler.h"
 #include "llvm/MC/MCObjectStreamer.h"
 #include "llvm/MC/MCStreamer.h"
 #include "llvm/MC/MCSymbol.h"
 #include "llvm/MC/TargetRegistry.h"
 #include "llvm/Object/ObjectFile.h"
 #include "llvm/Support/Alignment.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/DataExtractor.h"
 #include "llvm/Support/Errc.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/FileSystem.h"
-#include "llvm/Support/LEB128.h"
 #include "llvm/Support/ManagedStatic.h"
 #include "llvm/Support/Regex.h"
 #include "llvm/Support/Timer.h"
 #include "llvm/Support/ToolOutputFile.h"
 #include "llvm/Support/raw_ostream.h"
 #include <algorithm>
 #include <fstream>
 #include <memory>
PrintGlobals("print-globals",
                  cl::cat(BoltCategory));
 
 extern cl::opt<bool> PrintSections;
 
 static cl::opt<bool> PrintLoopInfo("print-loops",
                                    cl::desc("print loop related information"),
                                    cl::Hidden, cl::cat(BoltCategory));
 
-enum PrintPseudoProbesOptions {
-  PPP_None = 0,
-  PPP_Probes_Section_Decode = 0x1,
-  PPP_Probes_Address_Conversion = 0x2,
-  PPP_Encoded_Probes = 0x3,
-  PPP_All = 0xf
-};
-
-cl::opt<PrintPseudoProbesOptions> PrintPseudoProbes(
-    "print-pseudo-probes", cl::desc("print pseudo probe info"),
-    cl::init(PPP_None),
-    cl::values(clEnumValN(PPP_Probes_Section_Decode, "decode",
-                          "decode probes section from binary"),
-               clEnumValN(PPP_Probes_Address_Conversion, "address_conversion",
-                          "update address2ProbesMap with output block address"),
-               clEnumValN(PPP_Encoded_Probes, "encoded_probes",
-                          "display the encoded probes in binary section"),
-               clEnumValN(PPP_All, "all", "enable all debugging printout")),
-    cl::ZeroOrMore, cl::Hidden, cl::cat(BoltCategory));
-
 static cl::opt<cl::boolOrDefault> RelocationMode(
     "relocs", cl::desc("use relocations in the binary (default=autodetect)"),
     cl::cat(BoltCategory));
 
 static cl::opt<std::string>
 SaveProfile("w",
   cl::desc("save recorded profile to a file"),
   cl::cat(BoltOutputCategory));
SequentialDisassembly("sequential-disassembly",
   cl::cat(BoltOptCategory));
 
 static cl::opt<bool> WriteBoltInfoSection(
     "bolt-info", cl::desc("write bolt info section in the output binary"),
     cl::init(true), cl::Hidden, cl::cat(BoltOutputCategory));
 
 } // namespace opts
 
+// FIXME: implement a better way to mark sections for replacement.
 constexpr const char *RewriteInstance::SectionsToOverwrite[];
 std::vector<std::string> RewriteInstance::DebugSectionsToOverwrite = {
     ".debug_abbrev", ".debug_aranges",  ".debug_line",   ".debug_line_str",
     ".debug_loc",    ".debug_loclists", ".debug_ranges", ".debug_rnglists",
-    ".gdb_index",    ".debug_addr"};
+    ".gdb_index",    ".debug_addr",     ".pseudo_probe"};
 
 const char RewriteInstance::TimerGroupName[] = "rewrite";
 const char RewriteInstance::TimerGroupDesc[] = "Rewrite passes";
 
 namespace llvm {
 namespace bolt {
 
 extern const char *BoltRevision;
Error RewriteInstance::discoverStorage() {
   if (!getFileOffsetForAddress(BC->OldTextSectionAddress))
     return createStringError(errc::executable_format_error,
                              "BOLT-ERROR: input binary is not a valid ELF "
                              "executable as its text section is not "
                              "mapped to a valid segment");
   return Error::success();
 }
 
-void RewriteInstance::parsePseudoProbe() {
-  if (!PseudoProbeDescSection && !PseudoProbeSection) {
-    // pesudo probe is not added to binary. It is normal and no warning needed.
-    return;
-  }
-
-  // If only one section is found, it might mean the ELF is corrupted.
-  if (!PseudoProbeDescSection) {
-    errs() << "BOLT-WARNING: fail in reading .pseudo_probe_desc binary\n";
-    return;
-  } else if (!PseudoProbeSection) {
-    errs() << "BOLT-WARNING: fail in reading .pseudo_probe binary\n";
-    return;
-  }
-
-  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(),
-          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) {
-    outs() << "Report of decoding input pseudo probe binaries \n";
-    BC->ProbeDecoder.printGUID2FuncDescMap(outs());
-    BC->ProbeDecoder.printProbesForAllAddresses(outs());
-  }
-}
-
 void RewriteInstance::parseBuildID() {
   if (!BuildIDSection)
     return;
 
   StringRef Buf = BuildIDSection->getContents();
 
   // Reading notes section (see Portable Formats Specification, Version 1.1,
   // pg 2-5, section "Note Section").
errs() << "BOLT-WARNING: debug info will be stripped from the binary. "
               "Use -update-debug-sections to keep it.\n";
   }
 
   HasTextRelocations = (bool)BC->getUniqueSectionByName(".rela.text");
   HasSymbolTable = (bool)BC->getUniqueSectionByName(".symtab");
   LSDASection = BC->getUniqueSectionByName(".gcc_except_table");
   EHFrameSection = BC->getUniqueSectionByName(".eh_frame");
   BuildIDSection = BC->getUniqueSectionByName(".note.gnu.build-id");
-  PseudoProbeDescSection = BC->getUniqueSectionByName(".pseudo_probe_desc");
-  PseudoProbeSection = BC->getUniqueSectionByName(".pseudo_probe");
 
   if (ErrorOr<BinarySection &> BATSec =
           BC->getUniqueSectionByName(BoltAddressTranslation::SECTION_NAME)) {
     // Do not read BAT when plotting a heatmap
     if (!opts::HeatmapMode) {
       if (std::error_code EC = BAT->parse(BATSec->getContents())) {
         errs() << "BOLT-ERROR: failed to parse BOLT address translation "
                   "table.\n";
errs() << "BOLT-ERROR: input binary does not have local file symbols "
               "but profile data includes function names with embedded file "
               "names. It appears that the input binary was stripped while a "
               "profiled binary was not\n";
     exit(1);
   }
 }
 
 void RewriteInstance::initializeMetadataManager() {
+  MetadataManager.registerRewriter(createPseudoProbeRewriter(*BC));
+
   MetadataManager.registerRewriter(createSDTRewriter(*BC));
 }
 
 void RewriteInstance::processMetadataPreCFG() {
   initializeMetadataManager();
 
   MetadataManager.runInitializersPreCFG();
 
void RewriteInstance::emitAndLink() {
   }
 }
 
 void RewriteInstance::updateMetadata() {
   MetadataManager.runFinalizersAfterEmit();
 
   // TODO: use MetadataManager for updates.
   updateLKMarkers();
-  parsePseudoProbe();
-  updatePseudoProbes();
 
   if (opts::UpdateDebugSections) {
     NamedRegionTimer T("updateDebugInfo", "update debug info", TimerGroupName,
                        TimerGroupDesc, opts::TimeRewrite);
     DebugInfoRewriter->updateDebugInfo();
   }
 
   if (opts::WriteBoltInfoSection)
     addBoltInfoSection();
 }
 
-void RewriteInstance::updatePseudoProbes() {
-  // check if there is pseudo probe section decoded
-  if (BC->ProbeDecoder.getAddress2ProbesMap().empty())
-    return;
-  // input address converted to output
-  AddressProbesMap &Address2ProbesMap = BC->ProbeDecoder.getAddress2ProbesMap();
-  const GUIDProbeFunctionMap &GUID2Func =
-      BC->ProbeDecoder.getGUID2FuncDescMap();
-
-  for (auto &AP : Address2ProbesMap) {
-    BinaryFunction *F = BC->getBinaryFunctionContainingAddress(AP.first);
-    // If F is removed, eliminate all probes inside it from inline tree
-    // Setting probes' addresses as INT64_MAX means elimination
-    if (!F) {
-      for (MCDecodedPseudoProbe &Probe : AP.second)
-        Probe.setAddress(INT64_MAX);
-      continue;
-    }
-    // If F is not emitted, the function will remain in the same address as its
-    // input
-    if (!F->isEmitted())
-      continue;
-
-    uint64_t Offset = AP.first - F->getAddress();
-    const BinaryBasicBlock *BB = F->getBasicBlockContainingOffset(Offset);
-    uint64_t BlkOutputAddress = BB->getOutputAddressRange().first;
-    // Check if block output address is defined.
-    // If not, such block is removed from binary. Then remove the probes from
-    // inline tree
-    if (BlkOutputAddress == 0) {
-      for (MCDecodedPseudoProbe &Probe : AP.second)
-        Probe.setAddress(INT64_MAX);
-      continue;
-    }
-
-    unsigned ProbeTrack = AP.second.size();
-    std::list<MCDecodedPseudoProbe>::iterator Probe = AP.second.begin();
-    while (ProbeTrack != 0) {
-      if (Probe->isBlock()) {
-        Probe->setAddress(BlkOutputAddress);
-      } else if (Probe->isCall()) {
-        // A call probe may be duplicated due to ICP
-        // Go through output of InputOffsetToAddressMap to collect all related
-        // probes
-        const InputOffsetToAddressMapTy &Offset2Addr =
-            F->getInputOffsetToAddressMap();
-        auto CallOutputAddresses = Offset2Addr.equal_range(Offset);
-        auto CallOutputAddress = CallOutputAddresses.first;
-        if (CallOutputAddress == CallOutputAddresses.second) {
-          Probe->setAddress(INT64_MAX);
-        } else {
-          Probe->setAddress(CallOutputAddress->second);
-          CallOutputAddress = std::next(CallOutputAddress);
-        }
-
-        while (CallOutputAddress != CallOutputAddresses.second) {
-          AP.second.push_back(*Probe);
-          AP.second.back().setAddress(CallOutputAddress->second);
-          Probe->getInlineTreeNode()->addProbes(&(AP.second.back()));
-          CallOutputAddress = std::next(CallOutputAddress);
-        }
-      }
-      Probe = std::next(Probe);
-      ProbeTrack--;
-    }
-  }
-
-  if (opts::PrintPseudoProbes == opts::PrintPseudoProbesOptions::PPP_All ||
-      opts::PrintPseudoProbes ==
-          opts::PrintPseudoProbesOptions::PPP_Probes_Address_Conversion) {
-    outs() << "Pseudo Probe Address Conversion results:\n";
-    // table that correlates address to block
-    std::unordered_map<uint64_t, StringRef> Addr2BlockNames;
-    for (auto &F : BC->getBinaryFunctions())
-      for (BinaryBasicBlock &BinaryBlock : F.second)
-        Addr2BlockNames[BinaryBlock.getOutputAddressRange().first] =
-            BinaryBlock.getName();
-
-    // scan all addresses -> correlate probe to block when print out
-    std::vector<uint64_t> Addresses;
-    for (auto &Entry : Address2ProbesMap)
-      Addresses.push_back(Entry.first);
-    llvm::sort(Addresses);
-    for (uint64_t Key : Addresses) {
-      for (MCDecodedPseudoProbe &Probe : Address2ProbesMap[Key]) {
-        if (Probe.getAddress() == INT64_MAX)
-          outs() << "Deleted Probe: ";
-        else
-          outs() << "Address: " << format_hex(Probe.getAddress(), 8) << " ";
-        Probe.print(outs(), GUID2Func, true);
-        // print block name only if the probe is block type and undeleted.
-        if (Probe.isBlock() && Probe.getAddress() != INT64_MAX)
-          outs() << format_hex(Probe.getAddress(), 8) << " Probe is in "
-                 << Addr2BlockNames[Probe.getAddress()] << "\n";
-      }
-    }
-    outs() << "=======================================\n";
-  }
-
-  // encode pseudo probes with updated addresses
-  encodePseudoProbes();
-}
-
-template <typename F>
-static void emitLEB128IntValue(F encode, uint64_t Value,
-                               SmallString<8> &Contents) {
-  SmallString<128> Tmp;
-  raw_svector_ostream OSE(Tmp);
-  encode(Value, OSE);
-  Contents.append(OSE.str().begin(), OSE.str().end());
-}
-
-void RewriteInstance::encodePseudoProbes() {
-  // Buffer for new pseudo probes section
-  SmallString<8> Contents;
-  MCDecodedPseudoProbe *LastProbe = nullptr;
-
-  auto EmitInt = [&](uint64_t Value, uint32_t Size) {
-    const bool IsLittleEndian = BC->AsmInfo->isLittleEndian();
-    uint64_t Swapped = support::endian::byte_swap(
-        Value, IsLittleEndian ? support::little : support::big);
-    unsigned Index = IsLittleEndian ? 0 : 8 - Size;
-    auto Entry = StringRef(reinterpret_cast<char *>(&Swapped) + Index, Size);
-    Contents.append(Entry.begin(), Entry.end());
-  };
-
-  auto EmitULEB128IntValue = [&](uint64_t Value) {
-    SmallString<128> Tmp;
-    raw_svector_ostream OSE(Tmp);
-    encodeULEB128(Value, OSE, 0);
-    Contents.append(OSE.str().begin(), OSE.str().end());
-  };
-
-  auto EmitSLEB128IntValue = [&](int64_t Value) {
-    SmallString<128> Tmp;
-    raw_svector_ostream OSE(Tmp);
-    encodeSLEB128(Value, OSE);
-    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();
-      EmitSLEB128IntValue(Delta);
-    } else {
-      // Emit absolute address for encoding the first pseudo probe.
-      uint32_t AddrSize = BC->AsmInfo->getCodePointerSize();
-      EmitInt(CurProbe->getAddress(), AddrSize);
-    }
-  };
-
-  std::map<InlineSite, MCDecodedPseudoProbeInlineTree *,
-           std::greater<InlineSite>>
-      Inlinees;
-
-  // DFS of inline tree to emit pseudo probes in all tree node
-  // Inline site index of a probe is emitted first.
-  // Then tree node Guid, size of pseudo probes and children nodes, and detail
-  // of contained probes are emitted Deleted probes are skipped Root node is not
-  // encoded to binaries. It's a "wrapper" of inline trees of each function.
-  std::list<std::pair<uint64_t, MCDecodedPseudoProbeInlineTree *>> NextNodes;
-  const MCDecodedPseudoProbeInlineTree &Root =
-      BC->ProbeDecoder.getDummyInlineRoot();
-  for (auto Child = Root.getChildren().begin();
-       Child != Root.getChildren().end(); ++Child)
-    Inlinees[Child->first] = Child->second.get();
-
-  for (auto Inlinee : Inlinees)
-    // INT64_MAX is "placeholder" of unused callsite index field in the pair
-    NextNodes.push_back({INT64_MAX, Inlinee.second});
-
-  Inlinees.clear();
-
-  while (!NextNodes.empty()) {
-    uint64_t ProbeIndex = NextNodes.back().first;
-    MCDecodedPseudoProbeInlineTree *Cur = NextNodes.back().second;
-    NextNodes.pop_back();
-
-    if (Cur->Parent && !Cur->Parent->isRoot())
-      // Emit probe inline site
-      EmitULEB128IntValue(ProbeIndex);
-
-    // Emit probes grouped by GUID.
-    LLVM_DEBUG({
-      dbgs().indent(MCPseudoProbeTable::DdgPrintIndent);
-      dbgs() << "GUID: " << Cur->Guid << "\n";
-    });
-    // Emit Guid
-    EmitInt(Cur->Guid, 8);
-    // Emit number of probes in this node
-    uint64_t Deleted = 0;
-    for (MCDecodedPseudoProbe *&Probe : Cur->getProbes())
-      if (Probe->getAddress() == INT64_MAX)
-        Deleted++;
-    LLVM_DEBUG(dbgs() << "Deleted Probes:" << Deleted << "\n");
-    uint64_t ProbesSize = Cur->getProbes().size() - Deleted;
-    EmitULEB128IntValue(ProbesSize);
-    // Emit number of direct inlinees
-    EmitULEB128IntValue(Cur->getChildren().size());
-    // Emit probes in this group
-    for (MCDecodedPseudoProbe *&Probe : Cur->getProbes()) {
-      if (Probe->getAddress() == INT64_MAX)
-        continue;
-      EmitDecodedPseudoProbe(Probe);
-      LastProbe = Probe;
-    }
-
-    for (auto Child = Cur->getChildren().begin();
-         Child != Cur->getChildren().end(); ++Child)
-      Inlinees[Child->first] = Child->second.get();
-    for (const auto &Inlinee : Inlinees) {
-      assert(Cur->Guid != 0 && "non root tree node must have nonzero Guid");
-      NextNodes.push_back({std::get<1>(Inlinee.first), Inlinee.second});
-      LLVM_DEBUG({
-        dbgs().indent(MCPseudoProbeTable::DdgPrintIndent);
-        dbgs() << "InlineSite: " << std::get<1>(Inlinee.first) << "\n";
-      });
-    }
-    Inlinees.clear();
-  }
-
-  // Create buffer for new contents for the section
-  // Freed when parent section is destroyed
-  uint8_t *Output = new uint8_t[Contents.str().size()];
-  memcpy(Output, Contents.str().data(), Contents.str().size());
-  addToDebugSectionsToOverwrite(".pseudo_probe");
-  BC->registerOrUpdateSection(".pseudo_probe", PseudoProbeSection->getELFType(),
-                              PseudoProbeSection->getELFFlags(), Output,
-                              Contents.str().size(), 1);
-  if (opts::PrintPseudoProbes == opts::PrintPseudoProbesOptions::PPP_All ||
-      opts::PrintPseudoProbes ==
-          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(), GuidFilter, FuncStartAddrs);
-    DummyDecoder.printProbesForAllAddresses(outs());
-  }
-}
-
 void RewriteInstance::updateLKMarkers() {
   if (BC->LKMarkers.size() == 0)
     return;
 
   NamedRegionTimer T("updateLKMarkers", "update LK markers", TimerGroupName,
                      TimerGroupDesc, opts::TimeRewrite);
 
   std::unordered_map<std::string, uint64_t> PatchCounts;