1 //===- MCPseudoProbe.h - Pseudo probe encoding support ---------*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file contains the declaration of the MCPseudoProbe to support the pseudo 10 // probe encoding for AutoFDO. Pseudo probes together with their inline context 11 // are encoded in a DFS recursive way in the .pseudoprobe sections. For each 12 // .pseudoprobe section, the encoded binary data consist of a single or mutiple 13 // function records each for one outlined function. A function record has the 14 // following format : 15 // 16 // FUNCTION BODY (one for each outlined function present in the text section) 17 // GUID (uint64) 18 // GUID of the function 19 // NPROBES (ULEB128) 20 // Number of probes originating from this function. 21 // NUM_INLINED_FUNCTIONS (ULEB128) 22 // Number of callees inlined into this function, aka number of 23 // first-level inlinees 24 // PROBE RECORDS 25 // A list of NPROBES entries. Each entry contains: 26 // INDEX (ULEB128) 27 // TYPE (uint4) 28 // 0 - block probe, 1 - indirect call, 2 - direct call 29 // ATTRIBUTE (uint3) 30 // 1 - reserved 31 // ADDRESS_TYPE (uint1) 32 // 0 - code address, 1 - address delta 33 // CODE_ADDRESS (uint64 or ULEB128) 34 // code address or address delta, depending on ADDRESS_TYPE 35 // INLINED FUNCTION RECORDS 36 // A list of NUM_INLINED_FUNCTIONS entries describing each of the inlined 37 // callees. Each record contains: 38 // INLINE SITE 39 // ID of the callsite probe (ULEB128) 40 // FUNCTION BODY 41 // A FUNCTION BODY entry describing the inlined function. 42 //===----------------------------------------------------------------------===// 43 44 #ifndef LLVM_MC_MCPSEUDOPROBE_H 45 #define LLVM_MC_MCPSEUDOPROBE_H 46 47 #include "llvm/ADT/MapVector.h" 48 #include "llvm/MC/MCSection.h" 49 #include <functional> 50 #include <map> 51 #include <vector> 52 53 namespace llvm { 54 55 class MCStreamer; 56 class MCSymbol; 57 class MCObjectStreamer; 58 59 enum class MCPseudoProbeFlag { 60 // If set, indicates that the probe is encoded as an address delta 61 // instead of a real code address. 62 AddressDelta = 0x1, 63 }; 64 65 /// Instances of this class represent a pseudo probe instance for a pseudo probe 66 /// table entry, which is created during a machine instruction is assembled and 67 /// uses an address from a temporary label created at the current address in the 68 /// current section. 69 class MCPseudoProbe { 70 MCSymbol *Label; 71 uint64_t Guid; 72 uint64_t Index; 73 uint8_t Type; 74 uint8_t Attributes; 75 76 public: MCPseudoProbe(MCSymbol * Label,uint64_t Guid,uint64_t Index,uint64_t Type,uint64_t Attributes)77 MCPseudoProbe(MCSymbol *Label, uint64_t Guid, uint64_t Index, uint64_t Type, 78 uint64_t Attributes) 79 : Label(Label), Guid(Guid), Index(Index), Type(Type), 80 Attributes(Attributes) { 81 assert(Type <= 0xFF && "Probe type too big to encode, exceeding 2^8"); 82 assert(Attributes <= 0xFF && 83 "Probe attributes too big to encode, exceeding 2^16"); 84 } 85 getLabel()86 MCSymbol *getLabel() const { return Label; } 87 getGuid()88 uint64_t getGuid() const { return Guid; } 89 getIndex()90 uint64_t getIndex() const { return Index; } 91 getType()92 uint8_t getType() const { return Type; } 93 getAttributes()94 uint8_t getAttributes() const { return Attributes; } 95 96 void emit(MCObjectStreamer *MCOS, const MCPseudoProbe *LastProbe) const; 97 }; 98 99 // An inline frame has the form <Guid, ProbeID> 100 using InlineSite = std::tuple<uint64_t, uint32_t>; 101 using MCPseudoProbeInlineStack = SmallVector<InlineSite, 8>; 102 103 // A Tri-tree based data structure to group probes by inline stack. 104 // A tree is allocated for a standalone .text section. A fake 105 // instance is created as the root of a tree. 106 // A real instance of this class is created for each function, either an 107 // unlined function that has code in .text section or an inlined function. 108 class MCPseudoProbeInlineTree { 109 uint64_t Guid; 110 // Set of probes that come with the function. 111 std::vector<MCPseudoProbe> Probes; 112 // Use std::map for a deterministic output. 113 std::map<InlineSite, MCPseudoProbeInlineTree *> Inlinees; 114 115 // Root node has a GUID 0. isRoot()116 bool isRoot() { return Guid == 0; } 117 MCPseudoProbeInlineTree *getOrAddNode(InlineSite Site); 118 119 public: 120 MCPseudoProbeInlineTree() = default; MCPseudoProbeInlineTree(uint64_t Guid)121 MCPseudoProbeInlineTree(uint64_t Guid) : Guid(Guid) {} 122 ~MCPseudoProbeInlineTree(); 123 void addPseudoProbe(const MCPseudoProbe &Probe, 124 const MCPseudoProbeInlineStack &InlineStack); 125 void emit(MCObjectStreamer *MCOS, const MCPseudoProbe *&LastProbe); 126 }; 127 128 /// Instances of this class represent the pseudo probes inserted into a compile 129 /// unit. 130 class MCPseudoProbeSection { 131 public: addPseudoProbe(MCSection * Sec,const MCPseudoProbe & Probe,const MCPseudoProbeInlineStack & InlineStack)132 void addPseudoProbe(MCSection *Sec, const MCPseudoProbe &Probe, 133 const MCPseudoProbeInlineStack &InlineStack) { 134 MCProbeDivisions[Sec].addPseudoProbe(Probe, InlineStack); 135 } 136 137 // TODO: Sort by getOrdinal to ensure a determinstic section order 138 using MCProbeDivisionMap = std::map<MCSection *, MCPseudoProbeInlineTree>; 139 140 private: 141 // A collection of MCPseudoProbe for each text section. The MCPseudoProbes 142 // are grouped by GUID of the functions where they are from and will be 143 // encoded by groups. In the comdat scenario where a text section really only 144 // contains the code of a function solely, the probes associated with a comdat 145 // function are still grouped by GUIDs due to inlining that can bring probes 146 // from different functions into one function. 147 MCProbeDivisionMap MCProbeDivisions; 148 149 public: getMCProbes()150 const MCProbeDivisionMap &getMCProbes() const { return MCProbeDivisions; } 151 empty()152 bool empty() const { return MCProbeDivisions.empty(); } 153 154 void emit(MCObjectStreamer *MCOS); 155 }; 156 157 class MCPseudoProbeTable { 158 // A collection of MCPseudoProbe in the current module grouped by text 159 // sections. MCPseudoProbes will be encoded into a corresponding 160 // .pseudoprobe section. With functions emitted as separate comdats, 161 // a text section really only contains the code of a function solely, and the 162 // probes associated with the text section will be emitted into a standalone 163 // .pseudoprobe section that shares the same comdat group with the function. 164 MCPseudoProbeSection MCProbeSections; 165 166 public: 167 static void emit(MCObjectStreamer *MCOS); 168 getProbeSections()169 MCPseudoProbeSection &getProbeSections() { return MCProbeSections; } 170 171 #ifndef NDEBUG 172 static int DdgPrintIndent; 173 #endif 174 }; 175 } // end namespace llvm 176 177 #endif // LLVM_MC_MCPSEUDOPROBE_H 178