1 //===--- PseudoProbe.cpp - Pseudo probe decoding utilities ------*- 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 #include "PseudoProbe.h"
10 #include "ErrorHandling.h"
11 #include "llvm/Support/Endian.h"
12 #include "llvm/Support/LEB128.h"
13 #include "llvm/Support/raw_ostream.h"
14 #include <limits>
15 #include <memory>
16
17 using namespace llvm;
18 using namespace sampleprof;
19 using namespace support;
20
21 namespace llvm {
22 namespace sampleprof {
23
getProbeFNameForGUID(const GUIDProbeFunctionMap & GUID2FuncMAP,uint64_t GUID)24 static StringRef getProbeFNameForGUID(const GUIDProbeFunctionMap &GUID2FuncMAP,
25 uint64_t GUID) {
26 auto It = GUID2FuncMAP.find(GUID);
27 assert(It != GUID2FuncMAP.end() &&
28 "Probe function must exist for a valid GUID");
29 return It->second.FuncName;
30 }
31
print(raw_ostream & OS)32 void PseudoProbeFuncDesc::print(raw_ostream &OS) {
33 OS << "GUID: " << FuncGUID << " Name: " << FuncName << "\n";
34 OS << "Hash: " << FuncHash << "\n";
35 }
36
getInlineContext(SmallVectorImpl<std::string> & ContextStack,const GUIDProbeFunctionMap & GUID2FuncMAP,bool ShowName) const37 void PseudoProbe::getInlineContext(SmallVectorImpl<std::string> &ContextStack,
38 const GUIDProbeFunctionMap &GUID2FuncMAP,
39 bool ShowName) const {
40 uint32_t Begin = ContextStack.size();
41 PseudoProbeInlineTree *Cur = InlineTree;
42 // It will add the string of each node's inline site during iteration.
43 // Note that it won't include the probe's belonging function(leaf location)
44 while (Cur->hasInlineSite()) {
45 std::string ContextStr;
46 if (ShowName) {
47 StringRef FuncName =
48 getProbeFNameForGUID(GUID2FuncMAP, std::get<0>(Cur->ISite));
49 ContextStr += FuncName.str();
50 } else {
51 ContextStr += Twine(std::get<0>(Cur->ISite)).str();
52 }
53 ContextStr += ":";
54 ContextStr += Twine(std::get<1>(Cur->ISite)).str();
55 ContextStack.emplace_back(ContextStr);
56 Cur = Cur->Parent;
57 }
58 // Make the ContextStack in caller-callee order
59 std::reverse(ContextStack.begin() + Begin, ContextStack.end());
60 }
61
62 std::string
getInlineContextStr(const GUIDProbeFunctionMap & GUID2FuncMAP,bool ShowName) const63 PseudoProbe::getInlineContextStr(const GUIDProbeFunctionMap &GUID2FuncMAP,
64 bool ShowName) const {
65 std::ostringstream OContextStr;
66 SmallVector<std::string, 16> ContextStack;
67 getInlineContext(ContextStack, GUID2FuncMAP, ShowName);
68 for (auto &CxtStr : ContextStack) {
69 if (OContextStr.str().size())
70 OContextStr << " @ ";
71 OContextStr << CxtStr;
72 }
73 return OContextStr.str();
74 }
75
76 static const char *PseudoProbeTypeStr[3] = {"Block", "IndirectCall",
77 "DirectCall"};
78
print(raw_ostream & OS,const GUIDProbeFunctionMap & GUID2FuncMAP,bool ShowName)79 void PseudoProbe::print(raw_ostream &OS,
80 const GUIDProbeFunctionMap &GUID2FuncMAP,
81 bool ShowName) {
82 OS << "FUNC: ";
83 if (ShowName) {
84 StringRef FuncName = getProbeFNameForGUID(GUID2FuncMAP, GUID);
85 OS << FuncName.str() << " ";
86 } else {
87 OS << GUID << " ";
88 }
89 OS << "Index: " << Index << " ";
90 OS << "Type: " << PseudoProbeTypeStr[static_cast<uint8_t>(Type)] << " ";
91 if (isDangling()) {
92 OS << "Dangling ";
93 }
94 if (isTailCall()) {
95 OS << "TailCall ";
96 }
97 std::string InlineContextStr = getInlineContextStr(GUID2FuncMAP, ShowName);
98 if (InlineContextStr.size()) {
99 OS << "Inlined: @ ";
100 OS << InlineContextStr;
101 }
102 OS << "\n";
103 }
104
readUnencodedNumber()105 template <typename T> T PseudoProbeDecoder::readUnencodedNumber() {
106 if (Data + sizeof(T) > End) {
107 exitWithError("Decode unencoded number error in " + SectionName +
108 " section");
109 }
110 T Val = endian::readNext<T, little, unaligned>(Data);
111 return Val;
112 }
113
readUnsignedNumber()114 template <typename T> T PseudoProbeDecoder::readUnsignedNumber() {
115 unsigned NumBytesRead = 0;
116 uint64_t Val = decodeULEB128(Data, &NumBytesRead);
117 if (Val > std::numeric_limits<T>::max() || (Data + NumBytesRead > End)) {
118 exitWithError("Decode number error in " + SectionName + " section");
119 }
120 Data += NumBytesRead;
121 return static_cast<T>(Val);
122 }
123
readSignedNumber()124 template <typename T> T PseudoProbeDecoder::readSignedNumber() {
125 unsigned NumBytesRead = 0;
126 int64_t Val = decodeSLEB128(Data, &NumBytesRead);
127 if (Val > std::numeric_limits<T>::max() || (Data + NumBytesRead > End)) {
128 exitWithError("Decode number error in " + SectionName + " section");
129 }
130 Data += NumBytesRead;
131 return static_cast<T>(Val);
132 }
133
readString(uint32_t Size)134 StringRef PseudoProbeDecoder::readString(uint32_t Size) {
135 StringRef Str(reinterpret_cast<const char *>(Data), Size);
136 if (Data + Size > End) {
137 exitWithError("Decode string error in " + SectionName + " section");
138 }
139 Data += Size;
140 return Str;
141 }
142
buildGUID2FuncDescMap(const uint8_t * Start,std::size_t Size)143 void PseudoProbeDecoder::buildGUID2FuncDescMap(const uint8_t *Start,
144 std::size_t Size) {
145 // The pseudo_probe_desc section has a format like:
146 // .section .pseudo_probe_desc,"",@progbits
147 // .quad -5182264717993193164 // GUID
148 // .quad 4294967295 // Hash
149 // .uleb 3 // Name size
150 // .ascii "foo" // Name
151 // .quad -2624081020897602054
152 // .quad 174696971957
153 // .uleb 34
154 // .ascii "main"
155 #ifndef NDEBUG
156 SectionName = "pseudo_probe_desc";
157 #endif
158 Data = Start;
159 End = Data + Size;
160
161 while (Data < End) {
162 uint64_t GUID = readUnencodedNumber<uint64_t>();
163 uint64_t Hash = readUnencodedNumber<uint64_t>();
164 uint32_t NameSize = readUnsignedNumber<uint32_t>();
165 StringRef Name = readString(NameSize);
166
167 // Initialize PseudoProbeFuncDesc and populate it into GUID2FuncDescMap
168 GUID2FuncDescMap.emplace(GUID, PseudoProbeFuncDesc(GUID, Hash, Name));
169 }
170 assert(Data == End && "Have unprocessed data in pseudo_probe_desc section");
171 }
172
buildAddress2ProbeMap(const uint8_t * Start,std::size_t Size)173 void PseudoProbeDecoder::buildAddress2ProbeMap(const uint8_t *Start,
174 std::size_t Size) {
175 // The pseudo_probe section encodes an inline forest and each tree has a
176 // format like:
177 // FUNCTION BODY (one for each uninlined function present in the text
178 // section)
179 // GUID (uint64)
180 // GUID of the function
181 // NPROBES (ULEB128)
182 // Number of probes originating from this function.
183 // NUM_INLINED_FUNCTIONS (ULEB128)
184 // Number of callees inlined into this function, aka number of
185 // first-level inlinees
186 // PROBE RECORDS
187 // A list of NPROBES entries. Each entry contains:
188 // INDEX (ULEB128)
189 // TYPE (uint4)
190 // 0 - block probe, 1 - indirect call, 2 - direct call
191 // ATTRIBUTE (uint3)
192 // 1 - tail call, 2 - dangling
193 // ADDRESS_TYPE (uint1)
194 // 0 - code address, 1 - address delta
195 // CODE_ADDRESS (uint64 or ULEB128)
196 // code address or address delta, depending on Flag
197 // INLINED FUNCTION RECORDS
198 // A list of NUM_INLINED_FUNCTIONS entries describing each of the
199 // inlined callees. Each record contains:
200 // INLINE SITE
201 // GUID of the inlinee (uint64)
202 // Index of the callsite probe (ULEB128)
203 // FUNCTION BODY
204 // A FUNCTION BODY entry describing the inlined function.
205 #ifndef NDEBUG
206 SectionName = "pseudo_probe";
207 #endif
208 Data = Start;
209 End = Data + Size;
210
211 PseudoProbeInlineTree *Root = &DummyInlineRoot;
212 PseudoProbeInlineTree *Cur = &DummyInlineRoot;
213 uint64_t LastAddr = 0;
214 uint32_t Index = 0;
215 // A DFS-based decoding
216 while (Data < End) {
217 // Read inline site for inlinees
218 if (Root != Cur) {
219 Index = readUnsignedNumber<uint32_t>();
220 }
221 // Switch/add to a new tree node(inlinee)
222 Cur = Cur->getOrAddNode(std::make_tuple(Cur->GUID, Index));
223 // Read guid
224 Cur->GUID = readUnencodedNumber<uint64_t>();
225 // Read number of probes in the current node.
226 uint32_t NodeCount = readUnsignedNumber<uint32_t>();
227 // Read number of direct inlinees
228 Cur->ChildrenToProcess = readUnsignedNumber<uint32_t>();
229 // Read all probes in this node
230 for (std::size_t I = 0; I < NodeCount; I++) {
231 // Read index
232 uint32_t Index = readUnsignedNumber<uint32_t>();
233 // Read type | flag.
234 uint8_t Value = readUnencodedNumber<uint8_t>();
235 uint8_t Kind = Value & 0xf;
236 uint8_t Attr = (Value & 0x70) >> 4;
237 // Read address
238 uint64_t Addr = 0;
239 if (Value & 0x80) {
240 int64_t Offset = readSignedNumber<int64_t>();
241 Addr = LastAddr + Offset;
242 } else {
243 Addr = readUnencodedNumber<int64_t>();
244 }
245 // Populate Address2ProbesMap
246 std::vector<PseudoProbe> &ProbeVec = Address2ProbesMap[Addr];
247 ProbeVec.emplace_back(Addr, Cur->GUID, Index, PseudoProbeType(Kind), Attr,
248 Cur);
249 Cur->addProbes(&ProbeVec.back());
250 LastAddr = Addr;
251 }
252
253 // Look for the parent for the next node by subtracting the current
254 // node count from tree counts along the parent chain. The first node
255 // in the chain that has a non-zero tree count is the target.
256 while (Cur != Root) {
257 if (Cur->ChildrenToProcess == 0) {
258 Cur = Cur->Parent;
259 if (Cur != Root) {
260 assert(Cur->ChildrenToProcess > 0 &&
261 "Should have some unprocessed nodes");
262 Cur->ChildrenToProcess -= 1;
263 }
264 } else {
265 break;
266 }
267 }
268 }
269
270 assert(Data == End && "Have unprocessed data in pseudo_probe section");
271 assert(Cur == Root &&
272 " Cur should point to root when the forest is fully built up");
273 }
274
printGUID2FuncDescMap(raw_ostream & OS)275 void PseudoProbeDecoder::printGUID2FuncDescMap(raw_ostream &OS) {
276 OS << "Pseudo Probe Desc:\n";
277 // Make the output deterministic
278 std::map<uint64_t, PseudoProbeFuncDesc> OrderedMap(GUID2FuncDescMap.begin(),
279 GUID2FuncDescMap.end());
280 for (auto &I : OrderedMap) {
281 I.second.print(OS);
282 }
283 }
284
printProbeForAddress(raw_ostream & OS,uint64_t Address)285 void PseudoProbeDecoder::printProbeForAddress(raw_ostream &OS,
286 uint64_t Address) {
287 auto It = Address2ProbesMap.find(Address);
288 if (It != Address2ProbesMap.end()) {
289 for (auto &Probe : It->second) {
290 OS << " [Probe]:\t";
291 Probe.print(OS, GUID2FuncDescMap, true);
292 }
293 }
294 }
295
296 const PseudoProbe *
getCallProbeForAddr(uint64_t Address) const297 PseudoProbeDecoder::getCallProbeForAddr(uint64_t Address) const {
298 auto It = Address2ProbesMap.find(Address);
299 if (It == Address2ProbesMap.end())
300 return nullptr;
301 const std::vector<PseudoProbe> &Probes = It->second;
302
303 const PseudoProbe *CallProbe = nullptr;
304 for (const auto &Probe : Probes) {
305 if (Probe.isCall()) {
306 assert(!CallProbe &&
307 "There should be only one call probe corresponding to address "
308 "which is a callsite.");
309 CallProbe = &Probe;
310 }
311 }
312 return CallProbe;
313 }
314
315 const PseudoProbeFuncDesc *
getFuncDescForGUID(uint64_t GUID) const316 PseudoProbeDecoder::getFuncDescForGUID(uint64_t GUID) const {
317 auto It = GUID2FuncDescMap.find(GUID);
318 assert(It != GUID2FuncDescMap.end() && "Function descriptor doesn't exist");
319 return &It->second;
320 }
321
getInlineContextForProbe(const PseudoProbe * Probe,SmallVectorImpl<std::string> & InlineContextStack,bool IncludeLeaf) const322 void PseudoProbeDecoder::getInlineContextForProbe(
323 const PseudoProbe *Probe, SmallVectorImpl<std::string> &InlineContextStack,
324 bool IncludeLeaf) const {
325 Probe->getInlineContext(InlineContextStack, GUID2FuncDescMap, true);
326 if (!IncludeLeaf)
327 return;
328 // Note that the context from probe doesn't include leaf frame,
329 // hence we need to retrieve and prepend leaf if requested.
330 const auto *FuncDesc = getFuncDescForGUID(Probe->GUID);
331 InlineContextStack.emplace_back(FuncDesc->FuncName + ":" +
332 Twine(Probe->Index).str());
333 }
334
335 const PseudoProbeFuncDesc *
getInlinerDescForProbe(const PseudoProbe * Probe) const336 PseudoProbeDecoder::getInlinerDescForProbe(const PseudoProbe *Probe) const {
337 PseudoProbeInlineTree *InlinerNode = Probe->InlineTree;
338 if (!InlinerNode->hasInlineSite())
339 return nullptr;
340 return getFuncDescForGUID(std::get<0>(InlinerNode->ISite));
341 }
342
343 } // end namespace sampleprof
344 } // end namespace llvm
345