LLVM 17.0.0git
MCPseudoProbe.h
Go to the documentation of this file.
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's source name which may be different from the
19// actual binary linkage name. This GUID will be used to decode and
20// generate a profile against the source function name.
21// NPROBES (ULEB128)
22// Number of probes originating from this function.
23// NUM_INLINED_FUNCTIONS (ULEB128)
24// Number of callees inlined into this function, aka number of
25// first-level inlinees
26// PROBE RECORDS
27// A list of NPROBES entries. Each entry contains:
28// INDEX (ULEB128)
29// TYPE (uint4)
30// 0 - block probe, 1 - indirect call, 2 - direct call
31// ATTRIBUTE (uint3)
32// 1 - reserved
33// ADDRESS_TYPE (uint1)
34// 0 - code address for regular probes (for downwards compatibility)
35// - GUID of linkage name for sentinel probes
36// 1 - address delta
37// CODE_ADDRESS (uint64 or ULEB128)
38// code address or address delta, depending on ADDRESS_TYPE
39// INLINED FUNCTION RECORDS
40// A list of NUM_INLINED_FUNCTIONS entries describing each of the inlined
41// callees. Each record contains:
42// INLINE SITE
43// ID of the callsite probe (ULEB128)
44// FUNCTION BODY
45// A FUNCTION BODY entry describing the inlined function.
46//
47// TODO: retire the ADDRESS_TYPE encoding for code addresses once compatibility
48// is no longer an issue.
49//===----------------------------------------------------------------------===//
50
51#ifndef LLVM_MC_MCPSEUDOPROBE_H
52#define LLVM_MC_MCPSEUDOPROBE_H
53
54#include "llvm/ADT/DenseSet.h"
56#include "llvm/ADT/StringRef.h"
57#include "llvm/IR/PseudoProbe.h"
59#include <list>
60#include <map>
61#include <memory>
62#include <string>
63#include <tuple>
64#include <type_traits>
65#include <unordered_map>
66#include <unordered_set>
67#include <vector>
68
69namespace llvm {
70
71class MCSymbol;
72class MCObjectStreamer;
73class raw_ostream;
74
76 // If set, indicates that the probe is encoded as an address delta
77 // instead of a real code address.
78 AddressDelta = 0x1,
79};
80
81// Function descriptor decoded from .pseudo_probe_desc section
85 std::string FuncName;
86
88 : FuncGUID(GUID), FuncHash(Hash), FuncName(Name){};
89
90 void print(raw_ostream &OS);
91};
92
93class MCDecodedPseudoProbe;
94
95// An inline frame has the form <CalleeGuid, ProbeID>
96using InlineSite = std::tuple<uint64_t, uint32_t>;
98// GUID to PseudoProbeFuncDesc map
100 std::unordered_map<uint64_t, MCPseudoProbeFuncDesc>;
101// Address to pseudo probes map.
103 std::unordered_map<uint64_t, std::list<MCDecodedPseudoProbe>>;
104
106
108protected:
111 uint8_t Attributes;
112 uint8_t Type;
113 // The value should be equal to PseudoProbeReservedId::Last + 1 which is
114 // defined in SampleProfileProbe.h. The header file is not included here to
115 // reduce the dependency from MC to IPO.
116 const static uint32_t PseudoProbeFirstId = 1;
117
118public:
120 : Guid(G), Index(I), Attributes(At), Type(T) {}
121
122 bool isEntry() const { return Index == PseudoProbeFirstId; }
123
124 uint64_t getGuid() const { return Guid; }
125
126 uint64_t getIndex() const { return Index; }
127
128 uint8_t getAttributes() const { return Attributes; }
129
130 uint8_t getType() const { return Type; }
131
132 bool isBlock() const {
133 return Type == static_cast<uint8_t>(PseudoProbeType::Block);
134 }
135
136 bool isIndirectCall() const {
137 return Type == static_cast<uint8_t>(PseudoProbeType::IndirectCall);
138 }
139
140 bool isDirectCall() const {
141 return Type == static_cast<uint8_t>(PseudoProbeType::DirectCall);
142 }
143
144 bool isCall() const { return isIndirectCall() || isDirectCall(); }
145
146 void setAttributes(uint8_t Attr) { Attributes = Attr; }
147};
148
149/// Instances of this class represent a pseudo probe instance for a pseudo probe
150/// table entry, which is created during a machine instruction is assembled and
151/// uses an address from a temporary label created at the current address in the
152/// current section.
154 MCSymbol *Label;
155
156public:
159 : MCPseudoProbeBase(Guid, Index, Attributes, Type), Label(Label) {
160 assert(Type <= 0xFF && "Probe type too big to encode, exceeding 2^8");
161 assert(Attributes <= 0xFF &&
162 "Probe attributes too big to encode, exceeding 2^16");
163 }
164
165 MCSymbol *getLabel() const { return Label; }
166 void emit(MCObjectStreamer *MCOS, const MCPseudoProbe *LastProbe) const;
167};
168
169// Represents a callsite with caller function name and probe id
170using MCPseduoProbeFrameLocation = std::pair<StringRef, uint32_t>;
171
173 uint64_t Address;
175
176public:
178 uint8_t At, MCDecodedPseudoProbeInlineTree *Tree)
179 : MCPseudoProbeBase(G, I, At, static_cast<uint8_t>(K)), Address(Ad),
180 InlineTree(Tree){};
181
182 uint64_t getAddress() const { return Address; }
183
184 void setAddress(uint64_t Addr) { Address = Addr; }
185
187 return InlineTree;
188 }
189
190 // Get the inlined context by traversing current inline tree backwards,
191 // each tree node has its InlineSite which is taken as the context.
192 // \p ContextStack is populated in root to leaf order
193 void
195 const GUIDProbeFunctionMap &GUID2FuncMAP) const;
196
197 // Helper function to get the string from context stack
198 std::string
199 getInlineContextStr(const GUIDProbeFunctionMap &GUID2FuncMAP) const;
200
201 // Print pseudo probe while disassembling
202 void print(raw_ostream &OS, const GUIDProbeFunctionMap &GUID2FuncMAP,
203 bool ShowName) const;
204};
205
206template <typename ProbeType, typename DerivedProbeInlineTreeType>
208 struct InlineSiteHash {
209 uint64_t operator()(const InlineSite &Site) const {
210 return std::get<0>(Site) ^ std::get<1>(Site);
211 }
212 };
213
214protected:
215 // Track children (e.g. inlinees) of current context
216 using InlinedProbeTreeMap = std::unordered_map<
217 InlineSite, std::unique_ptr<DerivedProbeInlineTreeType>, InlineSiteHash>;
219 // Set of probes that come with the function.
220 std::vector<ProbeType> Probes;
222 static_assert(std::is_base_of<MCPseudoProbeInlineTreeBase,
223 DerivedProbeInlineTreeType>::value,
224 "DerivedProbeInlineTreeType must be subclass of "
225 "MCPseudoProbeInlineTreeBase");
226 }
227
228public:
230
231 // Root node has a GUID 0.
232 bool isRoot() const { return Guid == 0; }
234 const InlinedProbeTreeMap &getChildren() const { return Children; }
235 std::vector<ProbeType> &getProbes() { return Probes; }
236 void addProbes(ProbeType Probe) { Probes.push_back(Probe); }
237 // Caller node of the inline site
239 DerivedProbeInlineTreeType *getOrAddNode(const InlineSite &Site) {
240 auto Ret = Children.emplace(
241 Site, std::make_unique<DerivedProbeInlineTreeType>(Site));
242 Ret.first->second->Parent = this;
243 return Ret.first->second.get();
244 };
245};
246
247// A Tri-tree based data structure to group probes by inline stack.
248// A tree is allocated for a standalone .text section. A fake
249// instance is created as the root of a tree.
250// A real instance of this class is created for each function, either a
251// not inlined function that has code in .text section or an inlined function.
253 : public MCPseudoProbeInlineTreeBase<MCPseudoProbe,
254 MCPseudoProbeInlineTree> {
255public:
259 this->Guid = std::get<0>(Site);
260 }
261
262 // MCPseudoProbeInlineTree method based on Inlinees
263 void addPseudoProbe(const MCPseudoProbe &Probe,
264 const MCPseudoProbeInlineStack &InlineStack);
265 void emit(MCObjectStreamer *MCOS, const MCPseudoProbe *&LastProbe);
266};
267
268// inline tree node for the decoded pseudo probe
270 : public MCPseudoProbeInlineTreeBase<MCDecodedPseudoProbe *,
271 MCDecodedPseudoProbeInlineTree> {
272public:
274 // Used for decoding
276
279
280 // Return false if it's a dummy inline site
281 bool hasInlineSite() const { return !isRoot() && !Parent->isRoot(); }
282};
283
284/// Instances of this class represent the pseudo probes inserted into a compile
285/// unit.
287public:
288 void addPseudoProbe(MCSymbol *FuncSym, const MCPseudoProbe &Probe,
289 const MCPseudoProbeInlineStack &InlineStack) {
290 MCProbeDivisions[FuncSym].addPseudoProbe(Probe, InlineStack);
291 }
292
293 // TODO: Sort by getOrdinal to ensure a determinstic section order
294 using MCProbeDivisionMap = std::map<MCSymbol *, MCPseudoProbeInlineTree>;
295
296private:
297 // A collection of MCPseudoProbe for each function. The MCPseudoProbes are
298 // grouped by GUIDs due to inlining that can bring probes from different
299 // functions into one function.
300 MCProbeDivisionMap MCProbeDivisions;
301
302public:
303 const MCProbeDivisionMap &getMCProbes() const { return MCProbeDivisions; }
304
305 bool empty() const { return MCProbeDivisions.empty(); }
306
307 void emit(MCObjectStreamer *MCOS);
308};
309
311 // A collection of MCPseudoProbe in the current module grouped by
312 // functions. MCPseudoProbes will be encoded into a corresponding
313 // .pseudoprobe section. With functions emitted as separate comdats,
314 // a text section really only contains the code of a function solely, and the
315 // probes associated with the text section will be emitted into a standalone
316 // .pseudoprobe section that shares the same comdat group with the function.
317 MCPseudoProbeSections MCProbeSections;
318
319public:
320 static void emit(MCObjectStreamer *MCOS);
321
322 MCPseudoProbeSections &getProbeSections() { return MCProbeSections; }
323
324#ifndef NDEBUG
325 static int DdgPrintIndent;
326#endif
327};
328
330 // GUID to PseudoProbeFuncDesc map.
331 GUIDProbeFunctionMap GUID2FuncDescMap;
332
333 // Address to probes map.
334 AddressProbesMap Address2ProbesMap;
335
336 // The dummy root of the inline trie, all the outlined function will directly
337 // be the children of the dummy root, all the inlined function will be the
338 // children of its inlineer. So the relation would be like:
339 // DummyRoot --> OutlinedFunc --> InlinedFunc1 --> InlinedFunc2
340 MCDecodedPseudoProbeInlineTree DummyInlineRoot;
341
342 /// Points to the current location in the buffer.
343 const uint8_t *Data = nullptr;
344
345 /// Points to the end of the buffer.
346 const uint8_t *End = nullptr;
347
348 /// Whether encoding is based on a starting probe with absolute code address.
349 bool EncodingIsAddrBased = false;
350
351 // Decoding helper function
352 template <typename T> ErrorOr<T> readUnencodedNumber();
353 template <typename T> ErrorOr<T> readUnsignedNumber();
354 template <typename T> ErrorOr<T> readSignedNumber();
355 ErrorOr<StringRef> readString(uint32_t Size);
356
357public:
360
361 // Decode pseudo_probe_desc section to build GUID to PseudoProbeFuncDesc map.
362 bool buildGUID2FuncDescMap(const uint8_t *Start, std::size_t Size);
363
364 // Decode pseudo_probe section to build address to probes map for specifed
365 // functions only.
366 bool buildAddress2ProbeMap(const uint8_t *Start, std::size_t Size,
367 const Uint64Set &GuildFilter,
368 const Uint64Map &FuncStartAddrs);
369
371 uint64_t &LastAddr, const Uint64Set &GuildFilter,
372 const Uint64Map &FuncStartAddrs);
373
374 // Print pseudo_probe_desc section info
376
377 // Print pseudo_probe section info, used along with show-disassembly
379
380 // do printProbeForAddress for all addresses
382
383 // Look up the probe of a call for the input address
385
387
388 // Helper function to populate one probe's inline stack into
389 // \p InlineContextStack.
390 // Current leaf location info will be added if IncludeLeaf is true
391 // Example:
392 // Current probe(bar:3) inlined at foo:2 then inlined at main:1
393 // IncludeLeaf = true, Output: [main:1, foo:2, bar:3]
394 // IncludeLeaf = false, Output: [main:1, foo:2]
396 const MCDecodedPseudoProbe *Probe,
398 bool IncludeLeaf) const;
399
401 return Address2ProbesMap;
402 }
403
404 AddressProbesMap &getAddress2ProbesMap() { return Address2ProbesMap; }
405
407 return GUID2FuncDescMap;
408 }
409
412
414 return DummyInlineRoot;
415 }
416};
417
418} // end namespace llvm
419
420#endif // LLVM_MC_MCPSEUDOPROBE_H
dxil metadata emit
Given that RA is a live value
This file defines the DenseSet and SmallDenseSet classes.
uint64_t Addr
std::string Name
uint64_t Size
Provides ErrorOr<T> smart pointer.
#define I(x, y, z)
Definition: MD5.cpp:58
#define G(x, y, z)
Definition: MD5.cpp:56
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
raw_pwrite_stream & OS
This file defines the SmallVector class.
Represents either an error or a value T.
Definition: ErrorOr.h:56
MCDecodedPseudoProbeInlineTree(const InlineSite &Site)
void print(raw_ostream &OS, const GUIDProbeFunctionMap &GUID2FuncMAP, bool ShowName) const
void setAddress(uint64_t Addr)
std::string getInlineContextStr(const GUIDProbeFunctionMap &GUID2FuncMAP) const
void getInlineContext(SmallVectorImpl< MCPseduoProbeFrameLocation > &ContextStack, const GUIDProbeFunctionMap &GUID2FuncMAP) const
MCDecodedPseudoProbe(uint64_t Ad, uint64_t G, uint32_t I, PseudoProbeType K, uint8_t At, MCDecodedPseudoProbeInlineTree *Tree)
MCDecodedPseudoProbeInlineTree * getInlineTreeNode() const
uint64_t getAddress() const
Streaming object file generation interface.
uint8_t getType() const
uint64_t getGuid() const
uint8_t getAttributes() const
bool isIndirectCall() const
uint64_t getIndex() const
MCPseudoProbeBase(uint64_t G, uint64_t I, uint64_t At, uint8_t T)
void setAttributes(uint8_t Attr)
static const uint32_t PseudoProbeFirstId
bool buildAddress2ProbeMap(const uint8_t *Start, std::size_t Size, const Uint64Set &GuildFilter, const Uint64Map &FuncStartAddrs)
void getInlineContextForProbe(const MCDecodedPseudoProbe *Probe, SmallVectorImpl< MCPseduoProbeFrameLocation > &InlineContextStack, bool IncludeLeaf) const
const AddressProbesMap & getAddress2ProbesMap() const
void printProbesForAllAddresses(raw_ostream &OS)
const GUIDProbeFunctionMap & getGUID2FuncDescMap() const
bool buildGUID2FuncDescMap(const uint8_t *Start, std::size_t Size)
const MCDecodedPseudoProbeInlineTree & getDummyInlineRoot() const
void printGUID2FuncDescMap(raw_ostream &OS)
void printProbeForAddress(raw_ostream &OS, uint64_t Address)
AddressProbesMap & getAddress2ProbesMap()
const MCPseudoProbeFuncDesc * getInlinerDescForProbe(const MCDecodedPseudoProbe *Probe) const
const MCDecodedPseudoProbe * getCallProbeForAddr(uint64_t Address) const
const MCPseudoProbeFuncDesc * getFuncDescForGUID(uint64_t GUID) const
InlinedProbeTreeMap & getChildren()
std::unordered_map< InlineSite, std::unique_ptr< DerivedProbeInlineTreeType >, InlineSiteHash > InlinedProbeTreeMap
const InlinedProbeTreeMap & getChildren() const
MCPseudoProbeInlineTreeBase< ProbeType, DerivedProbeInlineTreeType > * Parent
void addProbes(ProbeType Probe)
DerivedProbeInlineTreeType * getOrAddNode(const InlineSite &Site)
std::vector< ProbeType > & getProbes()
std::vector< ProbeType > Probes
MCPseudoProbeInlineTree(uint64_t Guid)
void addPseudoProbe(const MCPseudoProbe &Probe, const MCPseudoProbeInlineStack &InlineStack)
MCPseudoProbeInlineTree(const InlineSite &Site)
Instances of this class represent the pseudo probes inserted into a compile unit.
void addPseudoProbe(MCSymbol *FuncSym, const MCPseudoProbe &Probe, const MCPseudoProbeInlineStack &InlineStack)
const MCProbeDivisionMap & getMCProbes() const
std::map< MCSymbol *, MCPseudoProbeInlineTree > MCProbeDivisionMap
MCPseudoProbeSections & getProbeSections()
Instances of this class represent a pseudo probe instance for a pseudo probe table entry,...
MCSymbol * getLabel() const
MCPseudoProbe(MCSymbol *Label, uint64_t Guid, uint64_t Index, uint64_t Type, uint64_t Attributes)
MCSymbol - Instances of this class represent a symbol name in the MC file, and MCSymbols are created ...
Definition: MCSymbol.h:41
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:577
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
PseudoProbeType
Definition: PseudoProbe.h:29
std::unordered_map< uint64_t, std::list< MCDecodedPseudoProbe > > AddressProbesMap
std::tuple< uint64_t, uint32_t > InlineSite
Definition: MCPseudoProbe.h:96
std::pair< StringRef, uint32_t > MCPseduoProbeFrameLocation
MCPseudoProbeFlag
Definition: MCPseudoProbe.h:75
std::unordered_map< uint64_t, MCPseudoProbeFuncDesc > GUIDProbeFunctionMap
MCPseudoProbeFuncDesc(uint64_t GUID, uint64_t Hash, StringRef Name)
Definition: MCPseudoProbe.h:87
void print(raw_ostream &OS)