1//===- lib/MC/MCPseudoProbe.cpp - Pseudo probe encoding support ----------===//
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 "llvm/MC/MCPseudoProbe.h"
10#include "llvm/ADT/STLExtras.h"
11#include "llvm/IR/PseudoProbe.h"
12#include "llvm/MC/MCAsmInfo.h"
13#include "llvm/MC/MCAssembler.h"
14#include "llvm/MC/MCContext.h"
15#include "llvm/MC/MCExpr.h"
16#include "llvm/MC/MCObjectFileInfo.h"
17#include "llvm/MC/MCObjectStreamer.h"
18#include "llvm/MC/MCSymbol.h"
19#include "llvm/Support/Endian.h"
20#include "llvm/Support/Error.h"
21#include "llvm/Support/LEB128.h"
22#include "llvm/Support/MD5.h"
23#include "llvm/Support/WithColor.h"
24#include "llvm/Support/raw_ostream.h"
25#include <algorithm>
26#include <cassert>
27#include <limits>
28#include <sstream>
29#include <vector>
30
31#define DEBUG_TYPE "mcpseudoprobe"
32
33using namespace llvm;
34using namespace support;
35
36#ifndef NDEBUG
37int MCPseudoProbeTable::DdgPrintIndent = 0;
38#endif
39
40static const MCExpr *buildSymbolDiff(MCObjectStreamer *MCOS, const MCSymbol *A,
41 const MCSymbol *B) {
42 MCContext &Context = MCOS->getContext();
43 const MCExpr *ARef = MCSymbolRefExpr::create(Symbol: A, Ctx&: Context);
44 const MCExpr *BRef = MCSymbolRefExpr::create(Symbol: B, Ctx&: Context);
45 const MCExpr *AddrDelta =
46 MCBinaryExpr::create(Op: MCBinaryExpr::Sub, LHS: ARef, RHS: BRef, Ctx&: Context);
47 return AddrDelta;
48}
49
50uint64_t MCDecodedPseudoProbe::getGuid() const { return InlineTree->Guid; }
51
52void MCPseudoProbe::emit(MCObjectStreamer *MCOS,
53 const MCPseudoProbe *LastProbe) const {
54 bool IsSentinel = isSentinelProbe(Flags: getAttributes());
55 assert((LastProbe || IsSentinel) &&
56 "Last probe should not be null for non-sentinel probes");
57
58 // Emit Index
59 MCOS->emitULEB128IntValue(Value: Index);
60 // Emit Type and the flag:
61 // Type (bit 0 to 3), with bit 4 to 6 for attributes.
62 // Flag (bit 7, 0 - code address, 1 - address delta). This indicates whether
63 // the following field is a symbolic code address or an address delta.
64 // Emit FS discriminator
65 assert(Type <= 0xF && "Probe type too big to encode, exceeding 15");
66 auto NewAttributes = Attributes;
67 if (Discriminator)
68 NewAttributes |= (uint32_t)PseudoProbeAttributes::HasDiscriminator;
69 assert(NewAttributes <= 0x7 &&
70 "Probe attributes too big to encode, exceeding 7");
71 uint8_t PackedType = Type | (NewAttributes << 4);
72 uint8_t Flag =
73 !IsSentinel ? ((int8_t)MCPseudoProbeFlag::AddressDelta << 7) : 0;
74 MCOS->emitInt8(Value: Flag | PackedType);
75
76 if (!IsSentinel) {
77 // Emit the delta between the address label and LastProbe.
78 const MCExpr *AddrDelta =
79 buildSymbolDiff(MCOS, A: Label, B: LastProbe->getLabel());
80 int64_t Delta;
81 if (AddrDelta->evaluateAsAbsolute(Res&: Delta, Asm: MCOS->getAssemblerPtr())) {
82 MCOS->emitSLEB128IntValue(Value: Delta);
83 } else {
84 auto *F = MCOS->getCurrentFragment();
85 F->makeLEB(IsSigned: true, Value: AddrDelta);
86 MCOS->newFragment();
87 }
88 } else {
89 // Emit the GUID of the split function that the sentinel probe represents.
90 MCOS->emitInt64(Value: Guid);
91 }
92
93 if (Discriminator)
94 MCOS->emitULEB128IntValue(Value: Discriminator);
95
96 LLVM_DEBUG({
97 dbgs().indent(MCPseudoProbeTable::DdgPrintIndent);
98 dbgs() << "Probe: " << Index << "\n";
99 });
100}
101
102void MCPseudoProbeInlineTree::addPseudoProbe(
103 const MCPseudoProbe &Probe, const MCPseudoProbeInlineStack &InlineStack) {
104 // The function should not be called on the root.
105 assert(isRoot() && "Should only be called on root");
106
107 // When it comes here, the input look like:
108 // Probe: GUID of C, ...
109 // InlineStack: [88, A], [66, B]
110 // which means, Function A inlines function B at call site with a probe id of
111 // 88, and B inlines C at probe 66. The tri-tree expects a tree path like {[0,
112 // A], [88, B], [66, C]} to locate the tree node where the probe should be
113 // added. Note that the edge [0, A] means A is the top-level function we are
114 // emitting probes for.
115
116 // Make a [0, A] edge.
117 // An empty inline stack means the function that the probe originates from
118 // is a top-level function.
119 InlineSite Top;
120 if (InlineStack.empty()) {
121 Top = InlineSite(Probe.getGuid(), 0);
122 } else {
123 Top = InlineSite(std::get<0>(t: InlineStack.front()), 0);
124 }
125
126 auto *Cur = getOrAddNode(Site: Top);
127
128 // Make interior edges by walking the inline stack. Once it's done, Cur should
129 // point to the node that the probe originates from.
130 if (!InlineStack.empty()) {
131 auto Iter = InlineStack.begin();
132 auto Index = std::get<1>(t: *Iter);
133 Iter++;
134 for (; Iter != InlineStack.end(); Iter++) {
135 // Make an edge by using the previous probe id and current GUID.
136 Cur = Cur->getOrAddNode(Site: InlineSite(std::get<0>(t: *Iter), Index));
137 Index = std::get<1>(t: *Iter);
138 }
139 Cur = Cur->getOrAddNode(Site: InlineSite(Probe.getGuid(), Index));
140 }
141
142 Cur->Probes.push_back(x: Probe);
143}
144
145void MCPseudoProbeInlineTree::emit(MCObjectStreamer *MCOS,
146 const MCPseudoProbe *&LastProbe) {
147 LLVM_DEBUG({
148 dbgs().indent(MCPseudoProbeTable::DdgPrintIndent);
149 dbgs() << "Group [\n";
150 MCPseudoProbeTable::DdgPrintIndent += 2;
151 });
152 assert(!isRoot() && "Root should be handled separately");
153
154 // Emit probes grouped by GUID.
155 LLVM_DEBUG({
156 dbgs().indent(MCPseudoProbeTable::DdgPrintIndent);
157 dbgs() << "GUID: " << Guid << "\n";
158 });
159 // Emit Guid
160 MCOS->emitInt64(Value: Guid);
161 // Emit number of probes in this node, including a sentinel probe for
162 // top-level functions if needed.
163 bool NeedSentinel = false;
164 if (Parent->isRoot()) {
165 assert(isSentinelProbe(LastProbe->getAttributes()) &&
166 "Starting probe of a top-level function should be a sentinel probe");
167 // The main body of a split function doesn't need a sentinel probe.
168 if (LastProbe->getGuid() != Guid)
169 NeedSentinel = true;
170 }
171
172 MCOS->emitULEB128IntValue(Value: Probes.size() + NeedSentinel);
173 // Emit number of direct inlinees
174 MCOS->emitULEB128IntValue(Value: Children.size());
175 // Emit sentinel probe for top-level functions
176 if (NeedSentinel)
177 LastProbe->emit(MCOS, LastProbe: nullptr);
178
179 // Emit probes in this group
180 for (const auto &Probe : Probes) {
181 Probe.emit(MCOS, LastProbe);
182 LastProbe = &Probe;
183 }
184
185 // Emit sorted descendant. InlineSite is unique for each pair, so there will
186 // be no ordering of Inlinee based on MCPseudoProbeInlineTree*
187 using InlineeType = std::pair<InlineSite, MCPseudoProbeInlineTree *>;
188 std::vector<InlineeType> Inlinees;
189 for (const auto &Child : Children)
190 Inlinees.emplace_back(args: Child.first, args: Child.second.get());
191 llvm::sort(C&: Inlinees, Comp: llvm::less_first());
192
193 for (const auto &Inlinee : Inlinees) {
194 // Emit probe index
195 MCOS->emitULEB128IntValue(Value: std::get<1>(t: Inlinee.first));
196 LLVM_DEBUG({
197 dbgs().indent(MCPseudoProbeTable::DdgPrintIndent);
198 dbgs() << "InlineSite: " << std::get<1>(Inlinee.first) << "\n";
199 });
200 // Emit the group
201 Inlinee.second->emit(MCOS, LastProbe);
202 }
203
204 LLVM_DEBUG({
205 MCPseudoProbeTable::DdgPrintIndent -= 2;
206 dbgs().indent(MCPseudoProbeTable::DdgPrintIndent);
207 dbgs() << "]\n";
208 });
209}
210
211void MCPseudoProbeSections::emit(MCObjectStreamer *MCOS) {
212 MCContext &Ctx = MCOS->getContext();
213 SmallVector<std::pair<MCSymbol *, MCPseudoProbeInlineTree *>> Vec;
214 Vec.reserve(N: MCProbeDivisions.size());
215 for (auto &ProbeSec : MCProbeDivisions)
216 Vec.emplace_back(Args: ProbeSec.first, Args: &ProbeSec.second);
217 for (auto I : llvm::enumerate(First&: MCOS->getAssembler()))
218 I.value().setOrdinal(I.index());
219 llvm::sort(C&: Vec, Comp: [](const auto &A, const auto &B) {
220 return std::make_pair(A.first->getSection().getOrdinal(),
221 A.first->getName()) <
222 std::make_pair(B.first->getSection().getOrdinal(),
223 B.first->getName());
224 });
225 for (auto [FuncSym, RootPtr] : Vec) {
226 const auto &Root = *RootPtr;
227 if (auto *S = Ctx.getObjectFileInfo()->getPseudoProbeSection(
228 TextSec: FuncSym->getSection())) {
229 // Switch to the .pseudoprobe section or a comdat group.
230 MCOS->switchSection(Section: S);
231 // Emit probes grouped by GUID.
232 // Emit sorted descendant. InlineSite is unique for each pair, so there
233 // will be no ordering of Inlinee based on MCPseudoProbeInlineTree*
234 using InlineeType = std::pair<InlineSite, MCPseudoProbeInlineTree *>;
235 std::vector<InlineeType> Inlinees;
236 for (const auto &Child : Root.getChildren())
237 Inlinees.emplace_back(args: Child.first, args: Child.second.get());
238 llvm::sort(C&: Inlinees, Comp: llvm::less_first());
239
240 for (const auto &Inlinee : Inlinees) {
241 // Emit the group guarded by a sentinel probe.
242 MCPseudoProbe SentinelProbe(
243 const_cast<MCSymbol *>(FuncSym), MD5Hash(Str: FuncSym->getName()),
244 (uint32_t)PseudoProbeReservedId::Invalid,
245 (uint32_t)PseudoProbeType::Block,
246 (uint32_t)PseudoProbeAttributes::Sentinel, 0);
247 const MCPseudoProbe *Probe = &SentinelProbe;
248 Inlinee.second->emit(MCOS, LastProbe&: Probe);
249 }
250 }
251 }
252}
253
254//
255// This emits the pseudo probe tables.
256//
257void MCPseudoProbeTable::emit(MCObjectStreamer *MCOS) {
258 MCContext &Ctx = MCOS->getContext();
259 auto &ProbeTable = Ctx.getMCPseudoProbeTable();
260
261 // Bail out early so we don't switch to the pseudo_probe section needlessly
262 // and in doing so create an unnecessary (if empty) section.
263 auto &ProbeSections = ProbeTable.getProbeSections();
264 if (ProbeSections.empty())
265 return;
266
267 LLVM_DEBUG(MCPseudoProbeTable::DdgPrintIndent = 0);
268
269 // Put out the probe.
270 ProbeSections.emit(MCOS);
271}
272
273static StringRef getProbeFNameForGUID(const GUIDProbeFunctionMap &GUID2FuncMAP,
274 uint64_t GUID) {
275 auto It = GUID2FuncMAP.find(GUID);
276 assert(It != GUID2FuncMAP.end() &&
277 "Probe function must exist for a valid GUID");
278 return It->FuncName;
279}
280
281void MCPseudoProbeFuncDesc::print(raw_ostream &OS) {
282 OS << "GUID: " << FuncGUID << " Name: " << FuncName << "\n";
283 OS << "Hash: " << FuncHash << "\n";
284}
285
286void MCDecodedPseudoProbe::getInlineContext(
287 SmallVectorImpl<MCPseudoProbeFrameLocation> &ContextStack,
288 const GUIDProbeFunctionMap &GUID2FuncMAP) const {
289 uint32_t Begin = ContextStack.size();
290 MCDecodedPseudoProbeInlineTree *Cur = InlineTree;
291 // It will add the string of each node's inline site during iteration.
292 // Note that it won't include the probe's belonging function(leaf location)
293 while (Cur->hasInlineSite()) {
294 StringRef FuncName = getProbeFNameForGUID(GUID2FuncMAP, GUID: Cur->Parent->Guid);
295 ContextStack.emplace_back(Args: MCPseudoProbeFrameLocation(
296 FuncName, std::get<1>(t: Cur->getInlineSite())));
297 Cur = static_cast<MCDecodedPseudoProbeInlineTree *>(Cur->Parent);
298 }
299 // Make the ContextStack in caller-callee order
300 std::reverse(first: ContextStack.begin() + Begin, last: ContextStack.end());
301}
302
303std::string MCDecodedPseudoProbe::getInlineContextStr(
304 const GUIDProbeFunctionMap &GUID2FuncMAP) const {
305 std::ostringstream OContextStr;
306 SmallVector<MCPseudoProbeFrameLocation, 16> ContextStack;
307 getInlineContext(ContextStack, GUID2FuncMAP);
308 for (auto &Cxt : ContextStack) {
309 if (OContextStr.str().size())
310 OContextStr << " @ ";
311 OContextStr << Cxt.first.str() << ":" << Cxt.second;
312 }
313 return OContextStr.str();
314}
315
316static const char *PseudoProbeTypeStr[3] = {"Block", "IndirectCall",
317 "DirectCall"};
318
319void MCDecodedPseudoProbe::print(raw_ostream &OS,
320 const GUIDProbeFunctionMap &GUID2FuncMAP,
321 bool ShowName) const {
322 OS << "FUNC: ";
323 if (ShowName) {
324 StringRef FuncName = getProbeFNameForGUID(GUID2FuncMAP, GUID: getGuid());
325 OS << FuncName.str() << " ";
326 } else {
327 OS << getGuid() << " ";
328 }
329 OS << "Index: " << Index << " ";
330 if (Discriminator)
331 OS << "Discriminator: " << Discriminator << " ";
332 OS << "Type: " << PseudoProbeTypeStr[static_cast<uint8_t>(Type)] << " ";
333 std::string InlineContextStr = getInlineContextStr(GUID2FuncMAP);
334 if (InlineContextStr.size()) {
335 OS << "Inlined: @ ";
336 OS << InlineContextStr;
337 }
338 OS << "\n";
339}
340
341template <typename T> ErrorOr<T> MCPseudoProbeDecoder::readUnencodedNumber() {
342 if (Data + sizeof(T) > End) {
343 return std::error_code();
344 }
345 T Val = endian::readNext<T, llvm::endianness::little>(Data);
346 return ErrorOr<T>(Val);
347}
348
349template <typename T> ErrorOr<T> MCPseudoProbeDecoder::readUnsignedNumber() {
350 unsigned NumBytesRead = 0;
351 uint64_t Val = decodeULEB128(p: Data, n: &NumBytesRead);
352 if (Val > std::numeric_limits<T>::max() || (Data + NumBytesRead > End)) {
353 return std::error_code();
354 }
355 Data += NumBytesRead;
356 return ErrorOr<T>(static_cast<T>(Val));
357}
358
359template <typename T> ErrorOr<T> MCPseudoProbeDecoder::readSignedNumber() {
360 unsigned NumBytesRead = 0;
361 int64_t Val = decodeSLEB128(p: Data, n: &NumBytesRead);
362 if (Val > std::numeric_limits<T>::max() || (Data + NumBytesRead > End)) {
363 return std::error_code();
364 }
365 Data += NumBytesRead;
366 return ErrorOr<T>(static_cast<T>(Val));
367}
368
369ErrorOr<StringRef> MCPseudoProbeDecoder::readString(uint32_t Size) {
370 StringRef Str(reinterpret_cast<const char *>(Data), Size);
371 if (Data + Size > End) {
372 return std::error_code();
373 }
374 Data += Size;
375 return ErrorOr<StringRef>(Str);
376}
377
378bool MCPseudoProbeDecoder::buildGUID2FuncDescMap(const uint8_t *Start,
379 std::size_t Size,
380 bool IsMMapped,
381 bool VerboseWarnings) {
382 // The pseudo_probe_desc section has a format like:
383 // .section .pseudo_probe_desc,"",@progbits
384 // .quad -5182264717993193164 // GUID
385 // .quad 4294967295 // Hash
386 // .uleb 3 // Name size
387 // .ascii "foo" // Name
388 // .quad -2624081020897602054
389 // .quad 174696971957
390 // .uleb 34
391 // .ascii "main"
392
393 Data = Start;
394 End = Data + Size;
395
396 uint32_t FuncDescCount = 0;
397 while (Data < End) {
398 // GUID
399 if (!readUnencodedNumber<uint64_t>())
400 return false;
401 // Hash
402 if (!readUnencodedNumber<uint64_t>())
403 return false;
404
405 auto ErrorOrNameSize = readUnsignedNumber<uint32_t>();
406 if (!ErrorOrNameSize)
407 return false;
408 // Function name
409 if (!readString(Size: *ErrorOrNameSize))
410 return false;
411 ++FuncDescCount;
412 }
413 assert(Data == End && "Have unprocessed data in pseudo_probe_desc section");
414 GUID2FuncDescMap.reserve(n: FuncDescCount);
415
416 Data = Start;
417 End = Data + Size;
418 while (Data < End) {
419 uint64_t GUID =
420 cantFail(ValOrErr: errorOrToExpected(EO: readUnencodedNumber<uint64_t>()));
421 uint64_t Hash =
422 cantFail(ValOrErr: errorOrToExpected(EO: readUnencodedNumber<uint64_t>()));
423 uint32_t NameSize =
424 cantFail(ValOrErr: errorOrToExpected(EO: readUnsignedNumber<uint32_t>()));
425 StringRef Name = cantFail(ValOrErr: errorOrToExpected(EO: readString(Size: NameSize)));
426
427 // Initialize PseudoProbeFuncDesc and populate it into GUID2FuncDescMap
428 GUID2FuncDescMap.emplace_back(
429 args&: GUID, args&: Hash, args: IsMMapped ? Name : Name.copy(A&: FuncNameAllocator));
430 }
431 assert(Data == End && "Have unprocessed data in pseudo_probe_desc section");
432 assert(GUID2FuncDescMap.size() == FuncDescCount &&
433 "Mismatching function description count pre- and post-parsing");
434 llvm::stable_sort(Range&: GUID2FuncDescMap, C: [](const auto &LHS, const auto &RHS) {
435 return LHS.FuncGUID < RHS.FuncGUID;
436 });
437
438 // Detect duplicate GUIDs with different hashes across TUs.
439 uint32_t MismatchCount = 0;
440 uint64_t LastMismatchGUID = 0;
441 for (size_t I = 1; I < GUID2FuncDescMap.size(); ++I) {
442 const auto &Prev = GUID2FuncDescMap[I - 1];
443 const auto &Curr = GUID2FuncDescMap[I];
444 if (Prev.FuncGUID == Curr.FuncGUID && Prev.FuncHash != Curr.FuncHash) {
445 if (LastMismatchGUID != Curr.FuncGUID) {
446 ++MismatchCount;
447 LastMismatchGUID = Curr.FuncGUID;
448 }
449 if (VerboseWarnings)
450 WithColor::warning() << "pseudo probe descriptor for " << Prev.FuncName
451 << " has mismatching hash across TUs: "
452 << format_hex(N: Prev.FuncHash, Width: 18) << " vs "
453 << format_hex(N: Curr.FuncHash, Width: 18) << "\n";
454 }
455 }
456 if (MismatchCount > 0)
457 WithColor::warning() << MismatchCount
458 << " functions have mismatching pseudo probe "
459 "descriptors across translation units.\n";
460 return true;
461}
462
463template <bool IsTopLevelFunc>
464bool MCPseudoProbeDecoder::buildAddress2ProbeMap(
465 MCDecodedPseudoProbeInlineTree *Cur, uint64_t &LastAddr,
466 const Uint64Set &GuidFilter, const Uint64Map &FuncStartAddrs,
467 const uint32_t CurChildIndex) {
468 // The pseudo_probe section encodes an inline forest and each tree has a
469 // format defined in MCPseudoProbe.h
470
471 uint32_t Index = 0;
472 if (IsTopLevelFunc) {
473 // Use a sequential id for top level inliner.
474 Index = CurChildIndex;
475 } else {
476 // Read inline site for inlinees
477 Index = cantFail(ValOrErr: errorOrToExpected(EO: readUnsignedNumber<uint32_t>()));
478 }
479
480 // Read guid
481 uint64_t Guid = cantFail(ValOrErr: errorOrToExpected(EO: readUnencodedNumber<uint64_t>()));
482
483 // Decide if top-level node should be disgarded.
484 if (IsTopLevelFunc && !GuidFilter.empty() && !GuidFilter.count(V: Guid))
485 Cur = nullptr;
486
487 // If the incoming node is null, all its children nodes should be disgarded.
488 if (Cur) {
489 // Switch/add to a new tree node(inlinee)
490 Cur->getChildren()[CurChildIndex] =
491 MCDecodedPseudoProbeInlineTree(InlineSite(Guid, Index), Cur);
492 Cur = &Cur->getChildren()[CurChildIndex];
493 if (IsTopLevelFunc && !EncodingIsAddrBased) {
494 if (auto V = FuncStartAddrs.lookup(Val: Guid))
495 LastAddr = V;
496 }
497 }
498
499 // Read number of probes in the current node.
500 uint32_t NodeCount =
501 cantFail(ValOrErr: errorOrToExpected(EO: readUnsignedNumber<uint32_t>()));
502 uint32_t CurrentProbeCount = 0;
503 // Read number of direct inlinees
504 uint32_t ChildrenToProcess =
505 cantFail(ValOrErr: errorOrToExpected(EO: readUnsignedNumber<uint32_t>()));
506 // Read all probes in this node
507 for (std::size_t I = 0; I < NodeCount; I++) {
508 // Read index
509 uint32_t Index =
510 cantFail(ValOrErr: errorOrToExpected(EO: readUnsignedNumber<uint32_t>()));
511 // Read type | flag.
512 uint8_t Value = cantFail(ValOrErr: errorOrToExpected(EO: readUnencodedNumber<uint8_t>()));
513 uint8_t Kind = Value & 0xf;
514 uint8_t Attr = (Value & 0x70) >> 4;
515 // Read address
516 uint64_t Addr = 0;
517 if (Value & 0x80) {
518 int64_t Offset = cantFail(ValOrErr: errorOrToExpected(EO: readSignedNumber<int64_t>()));
519 Addr = LastAddr + Offset;
520 } else {
521 Addr = cantFail(ValOrErr: errorOrToExpected(EO: readUnencodedNumber<int64_t>()));
522 if (isSentinelProbe(Flags: Attr)) {
523 // For sentinel probe, the addr field actually stores the GUID of the
524 // split function. Convert it to the real address.
525 if (auto V = FuncStartAddrs.lookup(Val: Addr))
526 Addr = V;
527 } else {
528 // For now we assume all probe encoding should be either based on
529 // leading probe address or function start address.
530 // The scheme is for downwards compatibility.
531 // TODO: retire this scheme once compatibility is no longer an issue.
532 EncodingIsAddrBased = true;
533 }
534 }
535
536 uint32_t Discriminator = 0;
537 if (hasDiscriminator(Flags: Attr)) {
538 Discriminator =
539 cantFail(ValOrErr: errorOrToExpected(EO: readUnsignedNumber<uint32_t>()));
540 }
541
542 if (Cur && !isSentinelProbe(Flags: Attr)) {
543 PseudoProbeVec.emplace_back(args&: Addr, args&: Index, args: PseudoProbeType(Kind), args&: Attr,
544 args&: Discriminator, args&: Cur);
545 ++CurrentProbeCount;
546 }
547 LastAddr = Addr;
548 }
549
550 if (Cur) {
551 Cur->setProbes(
552 MutableArrayRef(PseudoProbeVec).take_back(N: CurrentProbeCount));
553 InlineTreeVec.resize(new_size: InlineTreeVec.size() + ChildrenToProcess);
554 Cur->getChildren() =
555 MutableArrayRef(InlineTreeVec).take_back(N: ChildrenToProcess);
556 }
557 for (uint32_t I = 0; I < ChildrenToProcess; I++) {
558 buildAddress2ProbeMap<false>(Cur, LastAddr, GuidFilter, FuncStartAddrs, CurChildIndex: I);
559 }
560 return Cur;
561}
562
563template <bool IsTopLevelFunc>
564bool MCPseudoProbeDecoder::countRecords(bool &Discard, uint32_t &ProbeCount,
565 uint32_t &InlinedCount,
566 const Uint64Set &GuidFilter) {
567 if (!IsTopLevelFunc)
568 // Read inline site for inlinees
569 if (!readUnsignedNumber<uint32_t>())
570 return false;
571
572 // Read guid
573 auto ErrorOrCurGuid = readUnencodedNumber<uint64_t>();
574 if (!ErrorOrCurGuid)
575 return false;
576 uint64_t Guid = std::move(*ErrorOrCurGuid);
577
578 // Decide if top-level node should be disgarded.
579 if (IsTopLevelFunc) {
580 Discard = !GuidFilter.empty() && !GuidFilter.count(V: Guid);
581 if (!Discard)
582 // Allocate an entry for top-level function record.
583 ++InlinedCount;
584 }
585
586 // Read number of probes in the current node.
587 auto ErrorOrNodeCount = readUnsignedNumber<uint32_t>();
588 if (!ErrorOrNodeCount)
589 return false;
590 uint32_t NodeCount = std::move(*ErrorOrNodeCount);
591 uint32_t CurrentProbeCount = 0;
592
593 // Read number of direct inlinees
594 auto ErrorOrCurChildrenToProcess = readUnsignedNumber<uint32_t>();
595 if (!ErrorOrCurChildrenToProcess)
596 return false;
597 uint32_t ChildrenToProcess = std::move(*ErrorOrCurChildrenToProcess);
598
599 // Read all probes in this node
600 for (std::size_t I = 0; I < NodeCount; I++) {
601 // Read index
602 if (!readUnsignedNumber<uint32_t>())
603 return false;
604
605 // Read type | flag.
606 auto ErrorOrValue = readUnencodedNumber<uint8_t>();
607 if (!ErrorOrValue)
608 return false;
609 uint8_t Value = std::move(*ErrorOrValue);
610
611 uint8_t Attr = (Value & 0x70) >> 4;
612 if (Value & 0x80) {
613 // Offset
614 if (!readSignedNumber<int64_t>())
615 return false;
616 } else {
617 // Addr
618 if (!readUnencodedNumber<int64_t>())
619 return false;
620 }
621
622 if (hasDiscriminator(Flags: Attr))
623 // Discriminator
624 if (!readUnsignedNumber<uint32_t>())
625 return false;
626
627 if (!Discard && !isSentinelProbe(Flags: Attr))
628 ++CurrentProbeCount;
629 }
630
631 if (!Discard) {
632 ProbeCount += CurrentProbeCount;
633 InlinedCount += ChildrenToProcess;
634 }
635
636 for (uint32_t I = 0; I < ChildrenToProcess; I++)
637 if (!countRecords<false>(Discard, ProbeCount, InlinedCount, GuidFilter))
638 return false;
639 return true;
640}
641
642bool MCPseudoProbeDecoder::buildAddress2ProbeMap(
643 const uint8_t *Start, std::size_t Size, const Uint64Set &GuidFilter,
644 const Uint64Map &FuncStartAddrs) {
645 // For function records in the order of their appearance in the encoded data
646 // (DFS), count the number of contained probes and inlined function records.
647 uint32_t ProbeCount = 0;
648 uint32_t InlinedCount = 0;
649 uint32_t TopLevelFuncs = 0;
650 Data = Start;
651 End = Data + Size;
652 bool Discard = false;
653 while (Data < End) {
654 if (!countRecords<true>(Discard, ProbeCount, InlinedCount, GuidFilter))
655 return false;
656 TopLevelFuncs += !Discard;
657 }
658 assert(Data == End && "Have unprocessed data in pseudo_probe section");
659 PseudoProbeVec.reserve(n: ProbeCount);
660 InlineTreeVec.reserve(n: InlinedCount);
661
662 // Allocate top-level function records as children of DummyInlineRoot.
663 InlineTreeVec.resize(new_size: TopLevelFuncs);
664 DummyInlineRoot.getChildren() = MutableArrayRef(InlineTreeVec);
665
666 Data = Start;
667 End = Data + Size;
668 uint64_t LastAddr = 0;
669 uint32_t CurChildIndex = 0;
670 while (Data < End)
671 CurChildIndex += buildAddress2ProbeMap<true>(
672 Cur: &DummyInlineRoot, LastAddr, GuidFilter, FuncStartAddrs, CurChildIndex);
673 assert(Data == End && "Have unprocessed data in pseudo_probe section");
674 assert(PseudoProbeVec.size() == ProbeCount &&
675 "Mismatching probe count pre- and post-parsing");
676 assert(InlineTreeVec.size() == InlinedCount &&
677 "Mismatching function records count pre- and post-parsing");
678
679 std::vector<std::pair<uint64_t, uint32_t>> SortedA2P(ProbeCount);
680 for (const auto &[I, Probe] : llvm::enumerate(First&: PseudoProbeVec))
681 SortedA2P[I] = {Probe.getAddress(), I};
682 llvm::sort(C&: SortedA2P);
683 Address2ProbesMap.reserve(n: ProbeCount);
684 for (const uint32_t I : llvm::make_second_range(c&: SortedA2P))
685 Address2ProbesMap.emplace_back(args&: PseudoProbeVec[I]);
686 SortedA2P.clear();
687 return true;
688}
689
690void MCPseudoProbeDecoder::printGUID2FuncDescMap(raw_ostream &OS) {
691 OS << "Pseudo Probe Desc:\n";
692 for (auto &I : GUID2FuncDescMap)
693 I.print(OS);
694}
695
696void MCPseudoProbeDecoder::printProbeForAddress(raw_ostream &OS,
697 uint64_t Address) {
698 for (const MCDecodedPseudoProbe &Probe : Address2ProbesMap.find(Address)) {
699 OS << " [Probe]:\t";
700 Probe.print(OS, GUID2FuncMAP: GUID2FuncDescMap, ShowName: true);
701 }
702}
703
704void MCPseudoProbeDecoder::printProbesForAllAddresses(raw_ostream &OS) {
705 uint64_t PrevAddress = INT64_MAX;
706 for (MCDecodedPseudoProbe &Probe : Address2ProbesMap) {
707 uint64_t Address = Probe.getAddress();
708 if (Address != PrevAddress) {
709 PrevAddress = Address;
710 OS << "Address:\t" << Address << '\n';
711 }
712 OS << " [Probe]:\t";
713 Probe.print(OS, GUID2FuncMAP: GUID2FuncDescMap, ShowName: true);
714 }
715}
716
717const MCDecodedPseudoProbe *
718MCPseudoProbeDecoder::getCallProbeForAddr(uint64_t Address) const {
719 const MCDecodedPseudoProbe *CallProbe = nullptr;
720 for (const MCDecodedPseudoProbe &Probe : Address2ProbesMap.find(Address)) {
721 if (Probe.isCall()) {
722 // Disabling the assert and returning first call probe seen so far.
723 // Subsequent call probes, if any, are ignored. Due to the the way
724 // .pseudo_probe section is decoded, probes of the same-named independent
725 // static functions are merged thus multiple call probes may be seen for a
726 // callsite. This should only happen to compiler-generated statics, with
727 // -funique-internal-linkage-names where user statics get unique names.
728 //
729 // TODO: re-enable or narrow down the assert to static functions only.
730 //
731 // assert(!CallProbe &&
732 // "There should be only one call probe corresponding to address "
733 // "which is a callsite.");
734 CallProbe = &Probe;
735 break;
736 }
737 }
738 return CallProbe;
739}
740
741const MCPseudoProbeFuncDesc *
742MCPseudoProbeDecoder::getFuncDescForGUID(uint64_t GUID) const {
743 auto It = GUID2FuncDescMap.find(GUID);
744 assert(It != GUID2FuncDescMap.end() && "Function descriptor doesn't exist");
745 return &*It;
746}
747
748void MCPseudoProbeDecoder::getInlineContextForProbe(
749 const MCDecodedPseudoProbe *Probe,
750 SmallVectorImpl<MCPseudoProbeFrameLocation> &InlineContextStack,
751 bool IncludeLeaf) const {
752 Probe->getInlineContext(ContextStack&: InlineContextStack, GUID2FuncMAP: GUID2FuncDescMap);
753 if (!IncludeLeaf)
754 return;
755 // Note that the context from probe doesn't include leaf frame,
756 // hence we need to retrieve and prepend leaf if requested.
757 const auto *FuncDesc = getFuncDescForGUID(GUID: Probe->getGuid());
758 InlineContextStack.emplace_back(
759 Args: MCPseudoProbeFrameLocation(FuncDesc->FuncName, Probe->getIndex()));
760}
761
762const MCPseudoProbeFuncDesc *MCPseudoProbeDecoder::getInlinerDescForProbe(
763 const MCDecodedPseudoProbe *Probe) const {
764 MCDecodedPseudoProbeInlineTree *InlinerNode = Probe->getInlineTreeNode();
765 if (!InlinerNode->hasInlineSite())
766 return nullptr;
767 return getFuncDescForGUID(GUID: InlinerNode->Parent->Guid);
768}
769