LLVM 20.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// 2 - Sentinel
34// 4 - HasDiscriminator
35// ADDRESS_TYPE (uint1)
36// 0 - code address for regular probes (for downwards compatibility)
37// - GUID of linkage name for sentinel probes
38// 1 - address delta
39// CODE_ADDRESS (uint64 or ULEB128)
40// code address or address delta, depending on ADDRESS_TYPE
41// DISCRIMINATOR (ULEB128) if HasDiscriminator
42// INLINED FUNCTION RECORDS
43// A list of NUM_INLINED_FUNCTIONS entries describing each of the inlined
44// callees. Each record contains:
45// INLINE SITE
46// ID of the callsite probe (ULEB128)
47// FUNCTION BODY
48// A FUNCTION BODY entry describing the inlined function.
49//
50// TODO: retire the ADDRESS_TYPE encoding for code addresses once compatibility
51// is no longer an issue.
52//===----------------------------------------------------------------------===//
53
54#ifndef LLVM_MC_MCPSEUDOPROBE_H
55#define LLVM_MC_MCPSEUDOPROBE_H
56
57#include "llvm/ADT/DenseMap.h"
58#include "llvm/ADT/DenseSet.h"
60#include "llvm/ADT/StringRef.h"
61#include "llvm/IR/PseudoProbe.h"
63#include <list>
64#include <map>
65#include <memory>
66#include <string>
67#include <tuple>
68#include <type_traits>
69#include <unordered_map>
70#include <unordered_set>
71#include <vector>
72
73namespace llvm {
74
75class MCSymbol;
76class MCObjectStreamer;
77class raw_ostream;
78
80 // If set, indicates that the probe is encoded as an address delta
81 // instead of a real code address.
82 AddressDelta = 0x1,
83};
84
85// Function descriptor decoded from .pseudo_probe_desc section
89 std::string FuncName;
90
92 : FuncGUID(GUID), FuncHash(Hash), FuncName(Name){};
93
94 void print(raw_ostream &OS);
95};
96
97class MCDecodedPseudoProbe;
98
99// An inline frame has the form <CalleeGuid, ProbeID>
100using InlineSite = std::tuple<uint64_t, uint32_t>;
102// GUID to PseudoProbeFuncDesc map
104 std::unordered_map<uint64_t, MCPseudoProbeFuncDesc>;
105// Address to pseudo probes map.
106using AddressProbesMap = std::map<uint64_t, std::list<MCDecodedPseudoProbe>>;
107
109
111protected:
115 uint8_t Attributes;
116 uint8_t Type;
117 // The value should be equal to PseudoProbeReservedId::Last + 1 which is
118 // defined in SampleProfileProbe.h. The header file is not included here to
119 // reduce the dependency from MC to IPO.
120 const static uint32_t PseudoProbeFirstId = 1;
121
122public:
124 : Guid(G), Index(I), Discriminator(D), Attributes(At), Type(T) {}
125
126 bool isEntry() const { return Index == PseudoProbeFirstId; }
127
128 uint64_t getGuid() const { return Guid; }
129
130 uint64_t getIndex() const { return Index; }
131
133
134 uint8_t getAttributes() const { return Attributes; }
135
136 uint8_t getType() const { return Type; }
137
138 bool isBlock() const {
139 return Type == static_cast<uint8_t>(PseudoProbeType::Block);
140 }
141
142 bool isIndirectCall() const {
143 return Type == static_cast<uint8_t>(PseudoProbeType::IndirectCall);
144 }
145
146 bool isDirectCall() const {
147 return Type == static_cast<uint8_t>(PseudoProbeType::DirectCall);
148 }
149
150 bool isCall() const { return isIndirectCall() || isDirectCall(); }
151
152 void setAttributes(uint8_t Attr) { Attributes = Attr; }
153};
154
155/// Instances of this class represent a pseudo probe instance for a pseudo probe
156/// table entry, which is created during a machine instruction is assembled and
157/// uses an address from a temporary label created at the current address in the
158/// current section.
160 MCSymbol *Label;
161
162public:
166 Label(Label) {
167 assert(Type <= 0xFF && "Probe type too big to encode, exceeding 2^8");
168 assert(Attributes <= 0xFF &&
169 "Probe attributes too big to encode, exceeding 2^16");
170 }
171
172 MCSymbol *getLabel() const { return Label; }
173 void emit(MCObjectStreamer *MCOS, const MCPseudoProbe *LastProbe) const;
174};
175
176// Represents a callsite with caller function name and probe id
177using MCPseudoProbeFrameLocation = std::pair<StringRef, uint32_t>;
178
180 uint64_t Address;
182
183public:
185 uint8_t At, uint32_t D,
187 : MCPseudoProbeBase(G, I, At, static_cast<uint8_t>(K), D), Address(Ad),
188 InlineTree(Tree){};
189
190 uint64_t getAddress() const { return Address; }
191
192 void setAddress(uint64_t Addr) { Address = Addr; }
193
195 return InlineTree;
196 }
197
198 // Get the inlined context by traversing current inline tree backwards,
199 // each tree node has its InlineSite which is taken as the context.
200 // \p ContextStack is populated in root to leaf order
201 void
203 const GUIDProbeFunctionMap &GUID2FuncMAP) const;
204
205 // Helper function to get the string from context stack
206 std::string
207 getInlineContextStr(const GUIDProbeFunctionMap &GUID2FuncMAP) const;
208
209 // Print pseudo probe while disassembling
210 void print(raw_ostream &OS, const GUIDProbeFunctionMap &GUID2FuncMAP,
211 bool ShowName) const;
212};
213
214template <typename ProbeType, typename DerivedProbeInlineTreeType>
216 struct InlineSiteHash {
217 uint64_t operator()(const InlineSite &Site) const {
218 return std::get<0>(Site) ^ std::get<1>(Site);
219 }
220 };
221
222protected:
223 // Track children (e.g. inlinees) of current context
224 using InlinedProbeTreeMap = std::unordered_map<
225 InlineSite, std::unique_ptr<DerivedProbeInlineTreeType>, InlineSiteHash>;
227 // Set of probes that come with the function.
228 std::vector<ProbeType> Probes;
230 static_assert(std::is_base_of<MCPseudoProbeInlineTreeBase,
231 DerivedProbeInlineTreeType>::value,
232 "DerivedProbeInlineTreeType must be subclass of "
233 "MCPseudoProbeInlineTreeBase");
234 }
235
236public:
238
239 // Root node has a GUID 0.
240 bool isRoot() const { return Guid == 0; }
242 const InlinedProbeTreeMap &getChildren() const { return Children; }
243 std::vector<ProbeType> &getProbes() { return Probes; }
244 const std::vector<ProbeType> &getProbes() const { return Probes; }
245 void addProbes(ProbeType Probe) { Probes.push_back(Probe); }
246 // Caller node of the inline site
248 nullptr;
249 DerivedProbeInlineTreeType *getOrAddNode(const InlineSite &Site) {
250 auto Ret = Children.emplace(
251 Site, std::make_unique<DerivedProbeInlineTreeType>(Site));
252 Ret.first->second->Parent = this;
253 return Ret.first->second.get();
254 };
255};
256
257// A Tri-tree based data structure to group probes by inline stack.
258// A tree is allocated for a standalone .text section. A fake
259// instance is created as the root of a tree.
260// A real instance of this class is created for each function, either a
261// not inlined function that has code in .text section or an inlined function.
263 : public MCPseudoProbeInlineTreeBase<MCPseudoProbe,
264 MCPseudoProbeInlineTree> {
265public:
269 this->Guid = std::get<0>(Site);
270 }
271
272 // MCPseudoProbeInlineTree method based on Inlinees
273 void addPseudoProbe(const MCPseudoProbe &Probe,
274 const MCPseudoProbeInlineStack &InlineStack);
275 void emit(MCObjectStreamer *MCOS, const MCPseudoProbe *&LastProbe);
276};
277
278// inline tree node for the decoded pseudo probe
280 : public MCPseudoProbeInlineTreeBase<MCDecodedPseudoProbe *,
281 MCDecodedPseudoProbeInlineTree> {
282public:
284
287
288 // Return false if it's a dummy inline site
289 bool hasInlineSite() const { return !isRoot() && !Parent->isRoot(); }
290};
291
292/// Instances of this class represent the pseudo probes inserted into a compile
293/// unit.
295public:
296 void addPseudoProbe(MCSymbol *FuncSym, const MCPseudoProbe &Probe,
297 const MCPseudoProbeInlineStack &InlineStack) {
298 MCProbeDivisions[FuncSym].addPseudoProbe(Probe, InlineStack);
299 }
300
301 // The addresses of MCPseudoProbeInlineTree are used by the tree structure and
302 // need to be stable.
303 using MCProbeDivisionMap = std::unordered_map<MCSymbol *, MCPseudoProbeInlineTree>;
304
305private:
306 // A collection of MCPseudoProbe for each function. The MCPseudoProbes are
307 // grouped by GUIDs due to inlining that can bring probes from different
308 // functions into one function.
309 MCProbeDivisionMap MCProbeDivisions;
310
311public:
312 const MCProbeDivisionMap &getMCProbes() const { return MCProbeDivisions; }
313
314 bool empty() const { return MCProbeDivisions.empty(); }
315
316 void emit(MCObjectStreamer *MCOS);
317};
318
320 // A collection of MCPseudoProbe in the current module grouped by
321 // functions. MCPseudoProbes will be encoded into a corresponding
322 // .pseudoprobe section. With functions emitted as separate comdats,
323 // a text section really only contains the code of a function solely, and the
324 // probes associated with the text section will be emitted into a standalone
325 // .pseudoprobe section that shares the same comdat group with the function.
326 MCPseudoProbeSections MCProbeSections;
327
328public:
329 static void emit(MCObjectStreamer *MCOS);
330
331 MCPseudoProbeSections &getProbeSections() { return MCProbeSections; }
332
333#ifndef NDEBUG
334 static int DdgPrintIndent;
335#endif
336};
337
339 // GUID to PseudoProbeFuncDesc map.
340 GUIDProbeFunctionMap GUID2FuncDescMap;
341
342 // Address to probes map.
343 AddressProbesMap Address2ProbesMap;
344
345 // The dummy root of the inline trie, all the outlined function will directly
346 // be the children of the dummy root, all the inlined function will be the
347 // children of its inlineer. So the relation would be like:
348 // DummyRoot --> OutlinedFunc --> InlinedFunc1 --> InlinedFunc2
349 MCDecodedPseudoProbeInlineTree DummyInlineRoot;
350
351 /// Points to the current location in the buffer.
352 const uint8_t *Data = nullptr;
353
354 /// Points to the end of the buffer.
355 const uint8_t *End = nullptr;
356
357 /// Whether encoding is based on a starting probe with absolute code address.
358 bool EncodingIsAddrBased = false;
359
360 // Decoding helper function
361 template <typename T> ErrorOr<T> readUnencodedNumber();
362 template <typename T> ErrorOr<T> readUnsignedNumber();
363 template <typename T> ErrorOr<T> readSignedNumber();
364 ErrorOr<StringRef> readString(uint32_t Size);
365
366public:
369
370 // Decode pseudo_probe_desc section to build GUID to PseudoProbeFuncDesc map.
371 bool buildGUID2FuncDescMap(const uint8_t *Start, std::size_t Size);
372
373 // Decode pseudo_probe section to build address to probes map for specifed
374 // functions only.
375 bool buildAddress2ProbeMap(const uint8_t *Start, std::size_t Size,
376 const Uint64Set &GuildFilter,
377 const Uint64Map &FuncStartAddrs);
378
380 uint64_t &LastAddr, const Uint64Set &GuildFilter,
381 const Uint64Map &FuncStartAddrs);
382
383 // Print pseudo_probe_desc section info
385
386 // Print pseudo_probe section info, used along with show-disassembly
388
389 // do printProbeForAddress for all addresses
391
392 // Look up the probe of a call for the input address
394
396
397 // Helper function to populate one probe's inline stack into
398 // \p InlineContextStack.
399 // Current leaf location info will be added if IncludeLeaf is true
400 // Example:
401 // Current probe(bar:3) inlined at foo:2 then inlined at main:1
402 // IncludeLeaf = true, Output: [main:1, foo:2, bar:3]
403 // IncludeLeaf = false, Output: [main:1, foo:2]
405 const MCDecodedPseudoProbe *Probe,
407 bool IncludeLeaf) const;
408
410 return Address2ProbesMap;
411 }
412
413 AddressProbesMap &getAddress2ProbesMap() { return Address2ProbesMap; }
414
416 return GUID2FuncDescMap;
417 }
418
421
423 return DummyInlineRoot;
424 }
425};
426
427} // end namespace llvm
428
429#endif // LLVM_MC_MCPSEUDOPROBE_H
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
Given that RA is a live value
This file defines the DenseMap class.
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)
MCDecodedPseudoProbe(uint64_t Ad, uint64_t G, uint32_t I, PseudoProbeType K, uint8_t At, uint32_t D, MCDecodedPseudoProbeInlineTree *Tree)
std::string getInlineContextStr(const GUIDProbeFunctionMap &GUID2FuncMAP) const
MCDecodedPseudoProbeInlineTree * getInlineTreeNode() const
void getInlineContext(SmallVectorImpl< MCPseudoProbeFrameLocation > &ContextStack, const GUIDProbeFunctionMap &GUID2FuncMAP) const
uint64_t getAddress() const
Streaming object file generation interface.
uint8_t getType() const
uint64_t getGuid() const
uint8_t getAttributes() const
uint32_t getDiscriminator() const
MCPseudoProbeBase(uint64_t G, uint64_t I, uint64_t At, uint8_t T, uint32_t D)
bool isIndirectCall() const
uint64_t getIndex() const
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)
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)
void getInlineContextForProbe(const MCDecodedPseudoProbe *Probe, SmallVectorImpl< MCPseudoProbeFrameLocation > &InlineContextStack, bool IncludeLeaf) const
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()
const std::vector< ProbeType > & getProbes() const
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
void emit(MCObjectStreamer *MCOS, const MCPseudoProbe *&LastProbe)
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)
void emit(MCObjectStreamer *MCOS)
const MCProbeDivisionMap & getMCProbes() const
std::unordered_map< MCSymbol *, MCPseudoProbeInlineTree > MCProbeDivisionMap
MCPseudoProbeSections & getProbeSections()
static void emit(MCObjectStreamer *MCOS)
Instances of this class represent a pseudo probe instance for a pseudo probe table entry,...
MCSymbol * getLabel() const
void emit(MCObjectStreamer *MCOS, const MCPseudoProbe *LastProbe) const
MCPseudoProbe(MCSymbol *Label, uint64_t Guid, uint64_t Index, uint64_t Type, uint64_t Attributes, uint32_t Discriminator)
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:586
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
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::map< uint64_t, std::list< MCDecodedPseudoProbe > > AddressProbesMap
std::tuple< uint64_t, uint32_t > InlineSite
std::pair< StringRef, uint32_t > MCPseudoProbeFrameLocation
MCPseudoProbeFlag
Definition: MCPseudoProbe.h:79
std::unordered_map< uint64_t, MCPseudoProbeFuncDesc > GUIDProbeFunctionMap
MCPseudoProbeFuncDesc(uint64_t GUID, uint64_t Hash, StringRef Name)
Definition: MCPseudoProbe.h:91
void print(raw_ostream &OS)