Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

//===- 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'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 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>

#include <tuple>

#include <type_traits>

#include <unordered_map>

#include <unordered_set>

#include <vector>

namespace llvm {

class MCSymbol;

class MCObjectStreamer;

class raw_ostream;

enum class MCPseudoProbeFlag {

  // If set, indicates that the probe is encoded as an address delta

  // instead of a real code address.

  AddressDelta = 0x1,

};

// Function descriptor decoded from .pseudo_probe_desc section

struct MCPseudoProbeFuncDesc {

  uint64_t FuncGUID = 0;

  uint64_t FuncHash = 0;

  std::string FuncName;

  MCPseudoProbeFuncDesc(uint64_t GUID, uint64_t Hash, StringRef Name)

      : FuncGUID(GUID), FuncHash(Hash), FuncName(Name){};

  void print(raw_ostream &OS);

};

class MCDecodedPseudoProbe;

// An inline frame has the form <CalleeGuid, ProbeID>

using InlineSite = std::tuple<uint64_t, uint32_t>;

using MCPseudoProbeInlineStack = SmallVector<InlineSite, 8>;

// GUID to PseudoProbeFuncDesc map

using GUIDProbeFunctionMap =

    std::unordered_map<uint64_t, MCPseudoProbeFuncDesc>;

// Address to pseudo probes map.

using AddressProbesMap =

    std::unordered_map<uint64_t, std::list<MCDecodedPseudoProbe>>;

class MCDecodedPseudoProbeInlineTree;

class MCPseudoProbeBase {

protected:

  uint64_t Guid;

  uint64_t Index;

  uint8_t Attributes;

  uint8_t Type;

  // The value should be equal to PseudoProbeReservedId::Last + 1 which is

  // defined in SampleProfileProbe.h. The header file is not included here to

  // reduce the dependency from MC to IPO.

  const static uint32_t PseudoProbeFirstId = 1;

public:

  MCPseudoProbeBase(uint64_t G, uint64_t I, uint64_t At, uint8_t T)

      : Guid(G), Index(I), Attributes(At), Type(T) {}

  bool isEntry() const { return Index == PseudoProbeFirstId; }

  uint64_t getGuid() const { return Guid; }

  uint64_t getIndex() const { return Index; }

  uint8_t getAttributes() const { return Attributes; }

  uint8_t getType() const { return Type; }

  bool isBlock() const {

    return Type == static_cast<uint8_t>(PseudoProbeType::Block);

  }

  bool isIndirectCall() const {

    return Type == static_cast<uint8_t>(PseudoProbeType::IndirectCall);

  }

  bool isDirectCall() const {

    return Type == static_cast<uint8_t>(PseudoProbeType::DirectCall);

  }

  bool isCall() const { return isIndirectCall() || isDirectCall(); }

  void setAttributes(uint8_t Attr) { Attributes = Attr; }

};

/// Instances of this class represent a pseudo probe instance for a pseudo probe

/// table entry, which is created during a machine instruction is assembled and

/// uses an address from a temporary label created at the current address in the

/// current section.

class MCPseudoProbe : public MCPseudoProbeBase {

  MCSymbol *Label;

public:

  MCPseudoProbe(MCSymbol *Label, uint64_t Guid, uint64_t Index, uint64_t Type,

                uint64_t Attributes)

      : MCPseudoProbeBase(Guid, Index, Attributes, Type), Label(Label) {

    assert(Type <= 0xFF && "Probe type too big to encode, exceeding 2^8");

    assert(Attributes <= 0xFF &&

           "Probe attributes too big to encode, exceeding 2^16");

  }

  MCSymbol *getLabel() const { return Label; }

  void emit(MCObjectStreamer *MCOS, const MCPseudoProbe *LastProbe) const;

};

// Represents a callsite with caller function name and probe id

using MCPseduoProbeFrameLocation = std::pair<StringRef, uint32_t>;

class MCDecodedPseudoProbe : public MCPseudoProbeBase {

  uint64_t Address;

  MCDecodedPseudoProbeInlineTree *InlineTree;

public:

  MCDecodedPseudoProbe(uint64_t Ad, uint64_t G, uint32_t I, PseudoProbeType K,

                       uint8_t At, MCDecodedPseudoProbeInlineTree *Tree)

      : MCPseudoProbeBase(G, I, At, static_cast<uint8_t>(K)), Address(Ad),

        InlineTree(Tree){};

  uint64_t getAddress() const { return Address; }

  void setAddress(uint64_t Addr) { Address = Addr; }

  MCDecodedPseudoProbeInlineTree *getInlineTreeNode() const {

    return InlineTree;

  }

  // Get the inlined context by traversing current inline tree backwards,

  // each tree node has its InlineSite which is taken as the context.

  // \p ContextStack is populated in root to leaf order

  void

  getInlineContext(SmallVectorImpl<MCPseduoProbeFrameLocation> &ContextStack,

                   const GUIDProbeFunctionMap &GUID2FuncMAP) const;

  // Helper function to get the string from context stack

  std::string

  getInlineContextStr(const GUIDProbeFunctionMap &GUID2FuncMAP) const;

  // Print pseudo probe while disassembling

  void print(raw_ostream &OS, const GUIDProbeFunctionMap &GUID2FuncMAP,

             bool ShowName) const;

};

template <typename ProbeType, typename DerivedProbeInlineTreeType>

class MCPseudoProbeInlineTreeBase {

  struct InlineSiteHash {

    uint64_t operator()(const InlineSite &Site) const {

      return std::get<0>(Site) ^ std::get<1>(Site);

    }

  };

protected:

  // Track children (e.g. inlinees) of current context

  using InlinedProbeTreeMap = std::unordered_map<

      InlineSite, std::unique_ptr<DerivedProbeInlineTreeType>, InlineSiteHash>;

  InlinedProbeTreeMap Children;

  // Set of probes that come with the function.

  std::vector<ProbeType> Probes;

  MCPseudoProbeInlineTreeBase() {

    static_assert(std::is_base_of<MCPseudoProbeInlineTreeBase,

                                  DerivedProbeInlineTreeType>::value,

                  "DerivedProbeInlineTreeType must be subclass of "

                  "MCPseudoProbeInlineTreeBase");

  }

public:

  uint64_t Guid = 0;

  // Root node has a GUID 0.

  bool isRoot() const { return Guid == 0; }

  InlinedProbeTreeMap &getChildren() { return Children; }

  const InlinedProbeTreeMap &getChildren() const { return Children; }

  std::vector<ProbeType> &getProbes() { return Probes; }

  void addProbes(ProbeType Probe) { Probes.push_back(Probe); }

  // Caller node of the inline site

  MCPseudoProbeInlineTreeBase<ProbeType, DerivedProbeInlineTreeType> *Parent;

  DerivedProbeInlineTreeType *getOrAddNode(const InlineSite &Site) {

    auto Ret = Children.emplace(

        Site, std::make_unique<DerivedProbeInlineTreeType>(Site));

    Ret.first->second->Parent = this;

    return Ret.first->second.get();

  };

};

// A Tri-tree based data structure to group probes by inline stack.

// A tree is allocated for a standalone .text section. A fake

// instance is created as the root of a tree.

// A real instance of this class is created for each function, either a

// not inlined function that has code in .text section or an inlined function.

class MCPseudoProbeInlineTree

    : public MCPseudoProbeInlineTreeBase<MCPseudoProbe,

                                         MCPseudoProbeInlineTree> {

public:

  MCPseudoProbeInlineTree() = default;

  MCPseudoProbeInlineTree(uint64_t Guid) { this->Guid = Guid; }

  MCPseudoProbeInlineTree(const InlineSite &Site) {

    this->Guid = std::get<0>(Site);

  }

  // MCPseudoProbeInlineTree method based on Inlinees

  void addPseudoProbe(const MCPseudoProbe &Probe,

                      const MCPseudoProbeInlineStack &InlineStack);

  void emit(MCObjectStreamer *MCOS, const MCPseudoProbe *&LastProbe);

};

// inline tree node for the decoded pseudo probe

class MCDecodedPseudoProbeInlineTree

    : public MCPseudoProbeInlineTreeBase<MCDecodedPseudoProbe *,

                                         MCDecodedPseudoProbeInlineTree> {

public:

  InlineSite ISite;

  // Used for decoding

  uint32_t ChildrenToProcess = 0;

  MCDecodedPseudoProbeInlineTree() = default;

  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 MCPseudoProbeSections {

public:

  void addPseudoProbe(MCSymbol *FuncSym, const MCPseudoProbe &Probe,

                      const MCPseudoProbeInlineStack &InlineStack) {

    MCProbeDivisions[FuncSym].addPseudoProbe(Probe, InlineStack);

  }

  // TODO: Sort by getOrdinal to ensure a determinstic section order

  using MCProbeDivisionMap = std::map<MCSymbol *, MCPseudoProbeInlineTree>;

private:

  // 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

  // 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.

  MCPseudoProbeSections MCProbeSections;

public:

  static void emit(MCObjectStreamer *MCOS);

  MCPseudoProbeSections &getProbeSections() { return MCProbeSections; }

#ifndef NDEBUG

  static int DdgPrintIndent;

#endif

};

class MCPseudoProbeDecoder {

  // GUID to PseudoProbeFuncDesc map.

  GUIDProbeFunctionMap GUID2FuncDescMap;

  // Address to probes map.

  AddressProbesMap Address2ProbesMap;

  // The dummy root of the inline trie, all the outlined function will directly

  // be the children of the dummy root, all the inlined function will be the

  // children of its inlineer. So the relation would be like:

  // DummyRoot --> OutlinedFunc --> InlinedFunc1 --> InlinedFunc2

  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 for specifed

  // functions only.

  bool buildAddress2ProbeMap(const uint8_t *Start, std::size_t Size,

                             const Uint64Set &GuildFilter,

                             const Uint64Map &FuncStartAddrs);

  bool buildAddress2ProbeMap(MCDecodedPseudoProbeInlineTree *Cur,

                             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

  void printProbesForAllAddresses(raw_ostream &OS);

  // Look up the probe of a call for the input address

  const MCDecodedPseudoProbe *getCallProbeForAddr(uint64_t Address) const;

  const MCPseudoProbeFuncDesc *getFuncDescForGUID(uint64_t GUID) const;

  // Helper function to populate one probe's inline stack into

  // \p InlineContextStack.

  // Current leaf location info will be added if IncludeLeaf is true

  // Example:

  //  Current probe(bar:3) inlined at foo:2 then inlined at main:1

  //  IncludeLeaf = true,  Output: [main:1, foo:2, bar:3]

  //  IncludeLeaf = false, Output: [main:1, foo:2]

  void getInlineContextForProbe(

      const MCDecodedPseudoProbe *Probe,

      SmallVectorImpl<MCPseduoProbeFrameLocation> &InlineContextStack,

      bool IncludeLeaf) const;

  const AddressProbesMap &getAddress2ProbesMap() const {

    return Address2ProbesMap;

  }

  AddressProbesMap &getAddress2ProbesMap() { return Address2ProbesMap; }

  const GUIDProbeFunctionMap &getGUID2FuncDescMap() const {

    return GUID2FuncDescMap;

  }

  const MCPseudoProbeFuncDesc *

  getInlinerDescForProbe(const MCDecodedPseudoProbe *Probe) const;

  const MCDecodedPseudoProbeInlineTree &getDummyInlineRoot() const {

    return DummyInlineRoot;

  }

};

} // end namespace llvm

#endif // LLVM_MC_MCPSEUDOPROBE_H