1 files changed, 373 insertions, 19 deletions

diff --git a/contrib/llvm-project/llvm/lib/MC/MCPseudoProbe.cpp b/contrib/llvm-project/llvm/lib/MC/MCPseudoProbe.cpp
index 731831d3bce3..e35bcec8fe75 100644
--- a/contrib/llvm-project/llvm/lib/MC/MCPseudoProbe.cpp
+++ b/contrib/llvm-project/llvm/lib/MC/MCPseudoProbe.cpp
@@ -12,10 +12,17 @@
 #include "llvm/MC/MCObjectFileInfo.h"
 #include "llvm/MC/MCObjectStreamer.h"
 #include "llvm/MC/MCStreamer.h"
+#include "llvm/Support/Endian.h"
+#include "llvm/Support/LEB128.h"
+#include "llvm/Support/raw_ostream.h"
+#include <limits>
+#include <memory>
+#include <sstream>
 
 #define DEBUG_TYPE "mcpseudoprobe"
 
 using namespace llvm;
+using namespace support;
 
 #ifndef NDEBUG
 int MCPseudoProbeTable::DdgPrintIndent = 0;
@@ -69,23 +76,6 @@ void MCPseudoProbe::emit(MCObjectStreamer *MCOS,
   });
 }
 
-MCPseudoProbeInlineTree::~MCPseudoProbeInlineTree() {
-  for (auto &Inlinee : Inlinees)
-    delete Inlinee.second;
-}
-
-MCPseudoProbeInlineTree *
-MCPseudoProbeInlineTree::getOrAddNode(InlineSite Site) {
-  auto Iter = Inlinees.find(Site);
-  if (Iter == Inlinees.end()) {
-    auto *Node = new MCPseudoProbeInlineTree(std::get<0>(Site));
-    Inlinees[Site] = Node;
-    return Node;
-  } else {
-    return Iter->second;
-  }
-}
-
 void MCPseudoProbeInlineTree::addPseudoProbe(
     const MCPseudoProbe &Probe, const MCPseudoProbeInlineStack &InlineStack) {
   // The function should not be called on the root.
@@ -147,7 +137,7 @@ void MCPseudoProbeInlineTree::emit(MCObjectStreamer *MCOS,
     // Emit number of probes in this node
     MCOS->emitULEB128IntValue(Probes.size());
     // Emit number of direct inlinees
-    MCOS->emitULEB128IntValue(Inlinees.size());
+    MCOS->emitULEB128IntValue(Children.size());
     // Emit probes in this group
     for (const auto &Probe : Probes) {
       Probe.emit(MCOS, LastProbe);
@@ -157,7 +147,13 @@ void MCPseudoProbeInlineTree::emit(MCObjectStreamer *MCOS,
     assert(Probes.empty() && "Root should not have probes");
   }
 
-  // Emit descendent
+  // 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.begin(); Child != Children.end(); ++Child)
+    Inlinees[Child->first] = Child->second.get();
+
   for (const auto &Inlinee : Inlinees) {
     if (Guid) {
       // Emit probe index
@@ -211,3 +207,361 @@ void MCPseudoProbeTable::emit(MCObjectStreamer *MCOS) {
   // Put out the probe.
   ProbeSections.emit(MCOS);
 }
+
+static StringRef getProbeFNameForGUID(const GUIDProbeFunctionMap &GUID2FuncMAP,
+                                      uint64_t GUID) {
+  auto It = GUID2FuncMAP.find(GUID);
+  assert(It != GUID2FuncMAP.end() &&
+         "Probe function must exist for a valid GUID");
+  return It->second.FuncName;
+}
+
+void MCPseudoProbeFuncDesc::print(raw_ostream &OS) {
+  OS << "GUID: " << FuncGUID << " Name: " << FuncName << "\n";
+  OS << "Hash: " << FuncHash << "\n";
+}
+
+void MCDecodedPseudoProbe::getInlineContext(
+    SmallVectorImpl<MCPseduoProbeFrameLocation> &ContextStack,
+    const GUIDProbeFunctionMap &GUID2FuncMAP) const {
+  uint32_t Begin = ContextStack.size();
+  MCDecodedPseudoProbeInlineTree *Cur = InlineTree;
+  // It will add the string of each node's inline site during iteration.
+  // Note that it won't include the probe's belonging function(leaf location)
+  while (Cur->hasInlineSite()) {
+    StringRef FuncName =
+        getProbeFNameForGUID(GUID2FuncMAP, std::get<0>(Cur->ISite));
+    ContextStack.emplace_back(
+        MCPseduoProbeFrameLocation(FuncName, std::get<1>(Cur->ISite)));
+    Cur = static_cast<MCDecodedPseudoProbeInlineTree *>(Cur->Parent);
+  }
+  // Make the ContextStack in caller-callee order
+  std::reverse(ContextStack.begin() + Begin, ContextStack.end());
+}
+
+std::string MCDecodedPseudoProbe::getInlineContextStr(
+    const GUIDProbeFunctionMap &GUID2FuncMAP) const {
+  std::ostringstream OContextStr;
+  SmallVector<MCPseduoProbeFrameLocation, 16> ContextStack;
+  getInlineContext(ContextStack, GUID2FuncMAP);
+  for (auto &Cxt : ContextStack) {
+    if (OContextStr.str().size())
+      OContextStr << " @ ";
+    OContextStr << Cxt.first.str() << ":" << Cxt.second;
+  }
+  return OContextStr.str();
+}
+
+static const char *PseudoProbeTypeStr[3] = {"Block", "IndirectCall",
+                                            "DirectCall"};
+
+void MCDecodedPseudoProbe::print(raw_ostream &OS,
+                                 const GUIDProbeFunctionMap &GUID2FuncMAP,
+                                 bool ShowName) const {
+  OS << "FUNC: ";
+  if (ShowName) {
+    StringRef FuncName = getProbeFNameForGUID(GUID2FuncMAP, Guid);
+    OS << FuncName.str() << " ";
+  } else {
+    OS << Guid << " ";
+  }
+  OS << "Index: " << Index << "  ";
+  OS << "Type: " << PseudoProbeTypeStr[static_cast<uint8_t>(Type)] << "  ";
+  std::string InlineContextStr = getInlineContextStr(GUID2FuncMAP);
+  if (InlineContextStr.size()) {
+    OS << "Inlined: @ ";
+    OS << InlineContextStr;
+  }
+  OS << "\n";
+}
+
+template <typename T> ErrorOr<T> MCPseudoProbeDecoder::readUnencodedNumber() {
+  if (Data + sizeof(T) > End) {
+    return std::error_code();
+  }
+  T Val = endian::readNext<T, little, unaligned>(Data);
+  return ErrorOr<T>(Val);
+}
+
+template <typename T> ErrorOr<T> MCPseudoProbeDecoder::readUnsignedNumber() {
+  unsigned NumBytesRead = 0;
+  uint64_t Val = decodeULEB128(Data, &NumBytesRead);
+  if (Val > std::numeric_limits<T>::max() || (Data + NumBytesRead > End)) {
+    return std::error_code();
+  }
+  Data += NumBytesRead;
+  return ErrorOr<T>(static_cast<T>(Val));
+}
+
+template <typename T> ErrorOr<T> MCPseudoProbeDecoder::readSignedNumber() {
+  unsigned NumBytesRead = 0;
+  int64_t Val = decodeSLEB128(Data, &NumBytesRead);
+  if (Val > std::numeric_limits<T>::max() || (Data + NumBytesRead > End)) {
+    return std::error_code();
+  }
+  Data += NumBytesRead;
+  return ErrorOr<T>(static_cast<T>(Val));
+}
+
+ErrorOr<StringRef> MCPseudoProbeDecoder::readString(uint32_t Size) {
+  StringRef Str(reinterpret_cast<const char *>(Data), Size);
+  if (Data + Size > End) {
+    return std::error_code();
+  }
+  Data += Size;
+  return ErrorOr<StringRef>(Str);
+}
+
+bool MCPseudoProbeDecoder::buildGUID2FuncDescMap(const uint8_t *Start,
+                                                 std::size_t Size) {
+  // The pseudo_probe_desc section has a format like:
+  // .section .pseudo_probe_desc,"",@progbits
+  // .quad -5182264717993193164   // GUID
+  // .quad 4294967295             // Hash
+  // .uleb 3                      // Name size
+  // .ascii "foo"                 // Name
+  // .quad -2624081020897602054
+  // .quad 174696971957
+  // .uleb 34
+  // .ascii "main"
+
+  Data = Start;
+  End = Data + Size;
+
+  while (Data < End) {
+    auto ErrorOrGUID = readUnencodedNumber<uint64_t>();
+    if (!ErrorOrGUID)
+      return false;
+
+    auto ErrorOrHash = readUnencodedNumber<uint64_t>();
+    if (!ErrorOrHash)
+      return false;
+
+    auto ErrorOrNameSize = readUnsignedNumber<uint32_t>();
+    if (!ErrorOrNameSize)
+      return false;
+    uint32_t NameSize = std::move(*ErrorOrNameSize);
+
+    auto ErrorOrName = readString(NameSize);
+    if (!ErrorOrName)
+      return false;
+
+    uint64_t GUID = std::move(*ErrorOrGUID);
+    uint64_t Hash = std::move(*ErrorOrHash);
+    StringRef Name = std::move(*ErrorOrName);
+
+    // Initialize PseudoProbeFuncDesc and populate it into GUID2FuncDescMap
+    GUID2FuncDescMap.emplace(GUID, MCPseudoProbeFuncDesc(GUID, Hash, Name));
+  }
+  assert(Data == End && "Have unprocessed data in pseudo_probe_desc section");
+  return true;
+}
+
+bool MCPseudoProbeDecoder::buildAddress2ProbeMap(const uint8_t *Start,
+                                                 std::size_t Size) {
+  // 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.
+
+  Data = Start;
+  End = Data + Size;
+
+  MCDecodedPseudoProbeInlineTree *Root = &DummyInlineRoot;
+  MCDecodedPseudoProbeInlineTree *Cur = &DummyInlineRoot;
+  uint64_t LastAddr = 0;
+  uint32_t Index = 0;
+  // A DFS-based decoding
+  while (Data < End) {
+    if (Root == Cur) {
+      // Use a sequential id for top level inliner.
+      Index = Root->getChildren().size();
+    } else {
+      // Read inline site for inlinees
+      auto ErrorOrIndex = readUnsignedNumber<uint32_t>();
+      if (!ErrorOrIndex)
+        return false;
+      Index = std::move(*ErrorOrIndex);
+    }
+    // Switch/add to a new tree node(inlinee)
+    Cur = Cur->getOrAddNode(std::make_tuple(Cur->Guid, Index));
+    // Read guid
+    auto ErrorOrCurGuid = readUnencodedNumber<uint64_t>();
+    if (!ErrorOrCurGuid)
+      return false;
+    Cur->Guid = std::move(*ErrorOrCurGuid);
+    // 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
+    auto ErrorOrCurChildrenToProcess = readUnsignedNumber<uint32_t>();
+    if (!ErrorOrCurChildrenToProcess)
+      return false;
+    Cur->ChildrenToProcess = std::move(*ErrorOrCurChildrenToProcess);
+    // Read all probes in this node
+    for (std::size_t I = 0; I < NodeCount; I++) {
+      // Read index
+      auto ErrorOrIndex = readUnsignedNumber<uint32_t>();
+      if (!ErrorOrIndex)
+        return false;
+      uint32_t Index = std::move(*ErrorOrIndex);
+      // Read type | flag.
+      auto ErrorOrValue = readUnencodedNumber<uint8_t>();
+      if (!ErrorOrValue)
+        return false;
+      uint8_t Value = std::move(*ErrorOrValue);
+      uint8_t Kind = Value & 0xf;
+      uint8_t Attr = (Value & 0x70) >> 4;
+      // Read address
+      uint64_t Addr = 0;
+      if (Value & 0x80) {
+        auto ErrorOrOffset = readSignedNumber<int64_t>();
+        if (!ErrorOrOffset)
+          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);
+      }
+      // Populate Address2ProbesMap
+      auto &Probes = Address2ProbesMap[Addr];
+      Probes.emplace_back(Addr, Cur->Guid, Index, PseudoProbeType(Kind), Attr,
+                          Cur);
+      Cur->addProbes(&Probes.back());
+      LastAddr = Addr;
+    }
+
+    // Look for the parent for the next node by subtracting the current
+    // node count from tree counts along the parent chain. The first node
+    // in the chain that has a non-zero tree count is the target.
+    while (Cur != Root) {
+      if (Cur->ChildrenToProcess == 0) {
+        Cur = static_cast<MCDecodedPseudoProbeInlineTree *>(Cur->Parent);
+        if (Cur != Root) {
+          assert(Cur->ChildrenToProcess > 0 &&
+                 "Should have some unprocessed nodes");
+          Cur->ChildrenToProcess -= 1;
+        }
+      } else {
+        break;
+      }
+    }
+  }
+
+  assert(Data == End && "Have unprocessed data in pseudo_probe section");
+  assert(Cur == Root &&
+         " Cur should point to root when the forest is fully built up");
+  return true;
+}
+
+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);
+  }
+}
+
+void MCPseudoProbeDecoder::printProbeForAddress(raw_ostream &OS,
+                                                uint64_t Address) {
+  auto It = Address2ProbesMap.find(Address);
+  if (It != Address2ProbesMap.end()) {
+    for (auto &Probe : It->second) {
+      OS << " [Probe]:\t";
+      Probe.print(OS, GUID2FuncDescMap, true);
+    }
+  }
+}
+
+void MCPseudoProbeDecoder::printProbesForAllAddresses(raw_ostream &OS) {
+  std::vector<uint64_t> Addresses;
+  for (auto Entry : Address2ProbesMap)
+    Addresses.push_back(Entry.first);
+  std::sort(Addresses.begin(), Addresses.end());
+  for (auto K : Addresses) {
+    OS << "Address:\t";
+    OS << K;
+    OS << "\n";
+    printProbeForAddress(OS, K);
+  }
+}
+
+const MCDecodedPseudoProbe *
+MCPseudoProbeDecoder::getCallProbeForAddr(uint64_t Address) const {
+  auto It = Address2ProbesMap.find(Address);
+  if (It == Address2ProbesMap.end())
+    return nullptr;
+  const auto &Probes = It->second;
+
+  const MCDecodedPseudoProbe *CallProbe = nullptr;
+  for (const auto &Probe : Probes) {
+    if (Probe.isCall()) {
+      assert(!CallProbe &&
+             "There should be only one call probe corresponding to address "
+             "which is a callsite.");
+      CallProbe = &Probe;
+    }
+  }
+  return CallProbe;
+}
+
+const MCPseudoProbeFuncDesc *
+MCPseudoProbeDecoder::getFuncDescForGUID(uint64_t GUID) const {
+  auto It = GUID2FuncDescMap.find(GUID);
+  assert(It != GUID2FuncDescMap.end() && "Function descriptor doesn't exist");
+  return &It->second;
+}
+
+void MCPseudoProbeDecoder::getInlineContextForProbe(
+    const MCDecodedPseudoProbe *Probe,
+    SmallVectorImpl<MCPseduoProbeFrameLocation> &InlineContextStack,
+    bool IncludeLeaf) const {
+  Probe->getInlineContext(InlineContextStack, GUID2FuncDescMap);
+  if (!IncludeLeaf)
+    return;
+  // Note that the context from probe doesn't include leaf frame,
+  // hence we need to retrieve and prepend leaf if requested.
+  const auto *FuncDesc = getFuncDescForGUID(Probe->getGuid());
+  InlineContextStack.emplace_back(
+      MCPseduoProbeFrameLocation(FuncDesc->FuncName, Probe->getIndex()));
+}
+
+const MCPseudoProbeFuncDesc *MCPseudoProbeDecoder::getInlinerDescForProbe(
+    const MCDecodedPseudoProbe *Probe) const {
+  MCDecodedPseudoProbeInlineTree *InlinerNode = Probe->getInlineTreeNode();
+  if (!InlinerNode->hasInlineSite())
+    return nullptr;
+  return getFuncDescForGUID(std::get<0>(InlinerNode->ISite));
+}