1//===- xray-stacks.cpp: XRay Function Call Stack Accounting ---------------===//
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 implements stack-based accounting. It takes XRay traces, and
10// collates statistics across these traces to show a breakdown of time spent
11// at various points of the stack to provide insight into which functions
12// spend the most time in terms of a call stack. We provide a few
13// sorting/filtering options for zero'ing in on the useful stacks.
14//
15//===----------------------------------------------------------------------===//
16
17#include <forward_list>
18#include <numeric>
19
20#include "func-id-helper.h"
21#include "trie-node.h"
22#include "xray-registry.h"
23#include "llvm/ADT/StringExtras.h"
24#include "llvm/Support/CommandLine.h"
25#include "llvm/Support/Errc.h"
26#include "llvm/Support/ErrorHandling.h"
27#include "llvm/Support/FormatAdapters.h"
28#include "llvm/Support/FormatVariadic.h"
29#include "llvm/XRay/InstrumentationMap.h"
30#include "llvm/XRay/Trace.h"
31
32using namespace llvm;
33using namespace llvm::xray;
34
35static cl::SubCommand Stack("stack", "Call stack accounting");
36static cl::list<std::string> StackInputs(cl::Positional,
37 cl::desc("<xray trace>"), cl::Required,
38 cl::sub(Stack), cl::OneOrMore);
39
40static cl::opt<bool>
41 StackKeepGoing("keep-going", cl::desc("Keep going on errors encountered"),
42 cl::sub(Stack), cl::init(Val: false));
43static cl::alias StackKeepGoing2("k", cl::aliasopt(StackKeepGoing),
44 cl::desc("Alias for -keep-going"));
45
46// TODO: Does there need to be an option to deduce tail or sibling calls?
47
48static cl::opt<std::string> StacksInstrMap(
49 "instr_map",
50 cl::desc("instrumentation map used to identify function ids. "
51 "Currently supports elf file instrumentation maps."),
52 cl::sub(Stack), cl::init(Val: ""));
53static cl::alias StacksInstrMap2("m", cl::aliasopt(StacksInstrMap),
54 cl::desc("Alias for -instr_map"));
55
56static cl::opt<bool>
57 SeparateThreadStacks("per-thread-stacks",
58 cl::desc("Report top stacks within each thread id"),
59 cl::sub(Stack), cl::init(Val: false));
60
61static cl::opt<bool>
62 AggregateThreads("aggregate-threads",
63 cl::desc("Aggregate stack times across threads"),
64 cl::sub(Stack), cl::init(Val: false));
65
66static cl::opt<bool>
67 DumpAllStacks("all-stacks",
68 cl::desc("Dump sum of timings for all stacks. "
69 "By default separates stacks per-thread."),
70 cl::sub(Stack), cl::init(Val: false));
71static cl::alias DumpAllStacksShort("all", cl::aliasopt(DumpAllStacks),
72 cl::desc("Alias for -all-stacks"));
73
74// TODO(kpw): Add other interesting formats. Perhaps chrome trace viewer format
75// possibly with aggregations or just a linear trace of timings.
76enum StackOutputFormat { HUMAN, FLAMETOOL };
77
78static cl::opt<StackOutputFormat> StacksOutputFormat(
79 "stack-format",
80 cl::desc("The format that output stacks should be "
81 "output in. Only applies with all-stacks."),
82 cl::values(
83 clEnumValN(HUMAN, "human",
84 "Human readable output. Only valid without -all-stacks."),
85 clEnumValN(FLAMETOOL, "flame",
86 "Format consumable by Brendan Gregg's FlameGraph tool. "
87 "Only valid with -all-stacks.")),
88 cl::sub(Stack), cl::init(Val: HUMAN));
89
90// Types of values for each stack in a CallTrie.
91enum class AggregationType {
92 TOTAL_TIME, // The total time spent in a stack and its callees.
93 INVOCATION_COUNT // The number of times the stack was invoked.
94};
95
96static cl::opt<AggregationType> RequestedAggregation(
97 "aggregation-type",
98 cl::desc("The type of aggregation to do on call stacks."),
99 cl::values(
100 clEnumValN(
101 AggregationType::TOTAL_TIME, "time",
102 "Capture the total time spent in an all invocations of a stack."),
103 clEnumValN(AggregationType::INVOCATION_COUNT, "count",
104 "Capture the number of times a stack was invoked. "
105 "In flamegraph mode, this count also includes invocations "
106 "of all callees.")),
107 cl::sub(Stack), cl::init(Val: AggregationType::TOTAL_TIME));
108
109namespace {
110
111/// A helper struct to work with formatv and XRayRecords. Makes it easier to
112/// use instrumentation map names or addresses in formatted output.
113struct format_xray_record : public FormatAdapter<XRayRecord> {
114 explicit format_xray_record(XRayRecord record,
115 const FuncIdConversionHelper &conv)
116 : FormatAdapter<XRayRecord>(std::move(record)), Converter(&conv) {}
117 void format(raw_ostream &Stream, StringRef Style) {
118 Stream << formatv(
119 Fmt: "{FuncId: \"{0}\", ThreadId: \"{1}\", RecordType: \"{2}\"}",
120 Vals: Converter->SymbolOrNumber(FuncId: Item.FuncId), Vals&: Item.TId,
121 Vals: DecodeRecordType(recordType: Item.RecordType));
122 }
123
124private:
125 Twine DecodeRecordType(uint16_t recordType) {
126 switch (recordType) {
127 case 0:
128 return Twine("Fn Entry");
129 case 1:
130 return Twine("Fn Exit");
131 default:
132 // TODO: Add Tail exit when it is added to llvm/XRay/XRayRecord.h
133 return Twine("Unknown");
134 }
135 }
136
137 const FuncIdConversionHelper *Converter;
138};
139
140/// The stack command will take a set of XRay traces as arguments, and collects
141/// information about the stacks of instrumented functions that appear in the
142/// traces. We track the following pieces of information:
143///
144/// - Total time: amount of time/cycles accounted for in the traces.
145/// - Stack count: number of times a specific stack appears in the
146/// traces. Only instrumented functions show up in stacks.
147/// - Cumulative stack time: amount of time spent in a stack accumulated
148/// across the invocations in the traces.
149/// - Cumulative local time: amount of time spent in each instrumented
150/// function showing up in a specific stack, accumulated across the traces.
151///
152/// Example output for the kind of data we'd like to provide looks like the
153/// following:
154///
155/// Total time: 3.33234 s
156/// Stack ID: ...
157/// Stack Count: 2093
158/// # Function Local Time (%) Stack Time (%)
159/// 0 main 2.34 ms 0.07% 3.33234 s 100%
160/// 1 foo() 3.30000 s 99.02% 3.33 s 99.92%
161/// 2 bar() 30 ms 0.90% 30 ms 0.90%
162///
163/// We can also show distributions of the function call durations with
164/// statistics at each level of the stack. This works by doing the following
165/// algorithm:
166///
167/// 1. When unwinding, record the duration of each unwound function associated
168/// with the path up to which the unwinding stops. For example:
169///
170/// Step Duration (? means has start time)
171///
172/// push a <start time> a = ?
173/// push b <start time> a = ?, a->b = ?
174/// push c <start time> a = ?, a->b = ?, a->b->c = ?
175/// pop c <end time> a = ?, a->b = ?, emit duration(a->b->c)
176/// pop b <end time> a = ?, emit duration(a->b)
177/// push c <start time> a = ?, a->c = ?
178/// pop c <end time> a = ?, emit duration(a->c)
179/// pop a <end time> emit duration(a)
180///
181/// 2. We then account for the various stacks we've collected, and for each of
182/// them will have measurements that look like the following (continuing
183/// with the above simple example):
184///
185/// c : [<id("a->b->c"), [durations]>, <id("a->c"), [durations]>]
186/// b : [<id("a->b"), [durations]>]
187/// a : [<id("a"), [durations]>]
188///
189/// This allows us to compute, for each stack id, and each function that
190/// shows up in the stack, some important statistics like:
191///
192/// - median
193/// - 99th percentile
194/// - mean + stddev
195/// - count
196///
197/// 3. For cases where we don't have durations for some of the higher levels
198/// of the stack (perhaps instrumentation wasn't activated when the stack was
199/// entered), we can mark them appropriately.
200///
201/// Computing this data also allows us to implement lookup by call stack nodes,
202/// so that we can find functions that show up in multiple stack traces and
203/// show the statistical properties of that function in various contexts. We
204/// can compute information similar to the following:
205///
206/// Function: 'c'
207/// Stacks: 2 / 2
208/// Stack ID: ...
209/// Stack Count: ...
210/// # Function ...
211/// 0 a ...
212/// 1 b ...
213/// 2 c ...
214///
215/// Stack ID: ...
216/// Stack Count: ...
217/// # Function ...
218/// 0 a ...
219/// 1 c ...
220/// ----------------...
221///
222/// Function: 'b'
223/// Stacks: 1 / 2
224/// Stack ID: ...
225/// Stack Count: ...
226/// # Function ...
227/// 0 a ...
228/// 1 b ...
229/// 2 c ...
230///
231///
232/// To do this we require a Trie data structure that will allow us to represent
233/// all the call stacks of instrumented functions in an easily traversible
234/// manner when we do the aggregations and lookups. For instrumented call
235/// sequences like the following:
236///
237/// a()
238/// b()
239/// c()
240/// d()
241/// c()
242///
243/// We will have a representation like so:
244///
245/// a -> b -> c
246/// | |
247/// | +--> d
248/// |
249/// +--> c
250///
251/// We maintain a sequence of durations on the leaves and in the internal nodes
252/// as we go through and process every record from the XRay trace. We also
253/// maintain an index of unique functions, and provide a means of iterating
254/// through all the instrumented call stacks which we know about.
255
256struct StackDuration {
257 SmallVector<int64_t, 4> TerminalDurations;
258 SmallVector<int64_t, 4> IntermediateDurations;
259};
260} // namespace
261
262static StackDuration mergeStackDuration(const StackDuration &Left,
263 const StackDuration &Right) {
264 StackDuration Data{};
265 Data.TerminalDurations.reserve(N: Left.TerminalDurations.size() +
266 Right.TerminalDurations.size());
267 Data.IntermediateDurations.reserve(N: Left.IntermediateDurations.size() +
268 Right.IntermediateDurations.size());
269 // Aggregate the durations.
270 llvm::append_range(C&: Data.TerminalDurations, R: Left.TerminalDurations);
271 llvm::append_range(C&: Data.TerminalDurations, R: Right.TerminalDurations);
272
273 llvm::append_range(C&: Data.IntermediateDurations, R: Left.IntermediateDurations);
274 llvm::append_range(C&: Data.IntermediateDurations, R: Right.IntermediateDurations);
275 return Data;
276}
277
278using StackTrieNode = TrieNode<StackDuration>;
279
280template <AggregationType AggType>
281static std::size_t GetValueForStack(const StackTrieNode *Node);
282
283// When computing total time spent in a stack, we're adding the timings from
284// its callees and the timings from when it was a leaf.
285template <>
286std::size_t
287GetValueForStack<AggregationType::TOTAL_TIME>(const StackTrieNode *Node) {
288 auto TopSum = std::accumulate(first: Node->ExtraData.TerminalDurations.begin(),
289 last: Node->ExtraData.TerminalDurations.end(), init: 0uLL);
290 return std::accumulate(first: Node->ExtraData.IntermediateDurations.begin(),
291 last: Node->ExtraData.IntermediateDurations.end(), init: TopSum);
292}
293
294// Calculates how many times a function was invoked.
295// TODO: Hook up option to produce stacks
296template <>
297std::size_t
298GetValueForStack<AggregationType::INVOCATION_COUNT>(const StackTrieNode *Node) {
299 return Node->ExtraData.TerminalDurations.size() +
300 Node->ExtraData.IntermediateDurations.size();
301}
302
303// Make sure there are implementations for each enum value.
304template <AggregationType T> struct DependentFalseType : std::false_type {};
305
306template <AggregationType AggType>
307std::size_t GetValueForStack(const StackTrieNode *Node) {
308 static_assert(DependentFalseType<AggType>::value,
309 "No implementation found for aggregation type provided.");
310 return 0;
311}
312
313namespace {
314class StackTrie {
315 // Avoid the magic number of 4 propagated through the code with an alias.
316 // We use this SmallVector to track the root nodes in a call graph.
317 using RootVector = SmallVector<StackTrieNode *, 4>;
318
319 // We maintain pointers to the roots of the tries we see.
320 DenseMap<uint32_t, RootVector> Roots;
321
322 // We make sure all the nodes are accounted for in this list.
323 std::forward_list<StackTrieNode> NodeStore;
324
325 // A map of thread ids to pairs call stack trie nodes and their start times.
326 DenseMap<uint32_t, SmallVector<std::pair<StackTrieNode *, uint64_t>, 8>>
327 ThreadStackMap;
328
329 StackTrieNode *createTrieNode(uint32_t ThreadId, int32_t FuncId,
330 StackTrieNode *Parent) {
331 NodeStore.push_front(val: StackTrieNode{.FuncId: FuncId, .Parent: Parent, .Callees: {}, .ExtraData: {.TerminalDurations: {}, .IntermediateDurations: {}}});
332 auto I = NodeStore.begin();
333 auto *Node = &*I;
334 if (!Parent)
335 Roots[ThreadId].push_back(Elt: Node);
336 return Node;
337 }
338
339 StackTrieNode *findRootNode(uint32_t ThreadId, int32_t FuncId) {
340 const auto &RootsByThread = Roots[ThreadId];
341 auto I = find_if(Range: RootsByThread,
342 P: [&](StackTrieNode *N) { return N->FuncId == FuncId; });
343 return (I == RootsByThread.end()) ? nullptr : *I;
344 }
345
346public:
347 enum class AccountRecordStatus {
348 OK, // Successfully processed
349 ENTRY_NOT_FOUND, // An exit record had no matching call stack entry
350 UNKNOWN_RECORD_TYPE
351 };
352
353 struct AccountRecordState {
354 // We keep track of whether the call stack is currently unwinding.
355 bool wasLastRecordExit;
356
357 static AccountRecordState CreateInitialState() { return {.wasLastRecordExit: false}; }
358 };
359
360 AccountRecordStatus accountRecord(const XRayRecord &R,
361 AccountRecordState *state) {
362 auto &TS = ThreadStackMap[R.TId];
363 switch (R.Type) {
364 case RecordTypes::CUSTOM_EVENT:
365 case RecordTypes::TYPED_EVENT:
366 return AccountRecordStatus::OK;
367 case RecordTypes::ENTER:
368 case RecordTypes::ENTER_ARG: {
369 state->wasLastRecordExit = false;
370 // When we encounter a new function entry, we want to record the TSC for
371 // that entry, and the function id. Before doing so we check the top of
372 // the stack to see if there are callees that already represent this
373 // function.
374 if (TS.empty()) {
375 auto *Root = findRootNode(ThreadId: R.TId, FuncId: R.FuncId);
376 TS.emplace_back(Args: Root ? Root : createTrieNode(ThreadId: R.TId, FuncId: R.FuncId, Parent: nullptr),
377 Args: R.TSC);
378 return AccountRecordStatus::OK;
379 }
380
381 auto &Top = TS.back();
382 auto I = find_if(Range&: Top.first->Callees,
383 P: [&](StackTrieNode *N) { return N->FuncId == R.FuncId; });
384 if (I == Top.first->Callees.end()) {
385 // We didn't find the callee in the stack trie, so we're going to
386 // add to the stack then set up the pointers properly.
387 auto N = createTrieNode(ThreadId: R.TId, FuncId: R.FuncId, Parent: Top.first);
388 Top.first->Callees.emplace_back(Args&: N);
389
390 // Top may be invalidated after this statement.
391 TS.emplace_back(Args&: N, Args: R.TSC);
392 } else {
393 // We found the callee in the stack trie, so we'll use that pointer
394 // instead, add it to the stack associated with the TSC.
395 TS.emplace_back(Args&: *I, Args: R.TSC);
396 }
397 return AccountRecordStatus::OK;
398 }
399 case RecordTypes::EXIT:
400 case RecordTypes::TAIL_EXIT: {
401 bool wasLastRecordExit = state->wasLastRecordExit;
402 state->wasLastRecordExit = true;
403 // The exit case is more interesting, since we want to be able to deduce
404 // missing exit records. To do that properly, we need to look up the stack
405 // and see whether the exit record matches any of the entry records. If it
406 // does match, we attempt to record the durations as we pop the stack to
407 // where we see the parent.
408 if (TS.empty()) {
409 // Short circuit, and say we can't find it.
410
411 return AccountRecordStatus::ENTRY_NOT_FOUND;
412 }
413
414 auto FunctionEntryMatch = find_if(
415 Range: reverse(C&: TS), P: [&](const std::pair<StackTrieNode *, uint64_t> &E) {
416 return E.first->FuncId == R.FuncId;
417 });
418 auto status = AccountRecordStatus::OK;
419 if (FunctionEntryMatch == TS.rend()) {
420 status = AccountRecordStatus::ENTRY_NOT_FOUND;
421 } else {
422 // Account for offset of 1 between reverse and forward iterators. We
423 // want the forward iterator to include the function that is exited.
424 ++FunctionEntryMatch;
425 }
426 auto I = FunctionEntryMatch.base();
427 for (auto &E : make_range(x: I, y: TS.end() - 1))
428 E.first->ExtraData.IntermediateDurations.push_back(
429 Elt: std::max(a: E.second, b: R.TSC) - std::min(a: E.second, b: R.TSC));
430 auto &Deepest = TS.back();
431 if (wasLastRecordExit)
432 Deepest.first->ExtraData.IntermediateDurations.push_back(
433 Elt: std::max(a: Deepest.second, b: R.TSC) - std::min(a: Deepest.second, b: R.TSC));
434 else
435 Deepest.first->ExtraData.TerminalDurations.push_back(
436 Elt: std::max(a: Deepest.second, b: R.TSC) - std::min(a: Deepest.second, b: R.TSC));
437 TS.erase(CS: I, CE: TS.end());
438 return status;
439 }
440 }
441 return AccountRecordStatus::UNKNOWN_RECORD_TYPE;
442 }
443
444 bool isEmpty() const { return Roots.empty(); }
445
446 void printStack(raw_ostream &OS, const StackTrieNode *Top,
447 FuncIdConversionHelper &FN) {
448 // Traverse the pointers up to the parent, noting the sums, then print
449 // in reverse order (callers at top, callees down bottom).
450 SmallVector<const StackTrieNode *, 8> CurrentStack;
451 for (auto *F = Top; F != nullptr; F = F->Parent)
452 CurrentStack.push_back(Elt: F);
453 int Level = 0;
454 OS << formatv(Fmt: "{0,-5} {1,-60} {2,+12} {3,+16}\n", Vals: "lvl", Vals: "function",
455 Vals: "count", Vals: "sum");
456 for (auto *F : reverse(C: drop_begin(RangeOrContainer&: CurrentStack))) {
457 auto Sum = std::accumulate(first: F->ExtraData.IntermediateDurations.begin(),
458 last: F->ExtraData.IntermediateDurations.end(), init: 0LL);
459 auto FuncId = FN.SymbolOrNumber(FuncId: F->FuncId);
460 OS << formatv(Fmt: "#{0,-4} {1,-60} {2,+12} {3,+16}\n", Vals: Level++,
461 Vals: FuncId.size() > 60 ? FuncId.substr(pos: 0, n: 57) + "..." : FuncId,
462 Vals: F->ExtraData.IntermediateDurations.size(), Vals&: Sum);
463 }
464 auto *Leaf = *CurrentStack.begin();
465 auto LeafSum =
466 std::accumulate(first: Leaf->ExtraData.TerminalDurations.begin(),
467 last: Leaf->ExtraData.TerminalDurations.end(), init: 0LL);
468 auto LeafFuncId = FN.SymbolOrNumber(FuncId: Leaf->FuncId);
469 OS << formatv(Fmt: "#{0,-4} {1,-60} {2,+12} {3,+16}\n", Vals: Level++,
470 Vals: LeafFuncId.size() > 60 ? LeafFuncId.substr(pos: 0, n: 57) + "..."
471 : LeafFuncId,
472 Vals: Leaf->ExtraData.TerminalDurations.size(), Vals&: LeafSum);
473 OS << "\n";
474 }
475
476 /// Prints top stacks for each thread.
477 void printPerThread(raw_ostream &OS, FuncIdConversionHelper &FN) {
478 for (const auto &iter : Roots) {
479 OS << "Thread " << iter.first << ":\n";
480 print(OS, FN, RootValues: iter.second);
481 OS << "\n";
482 }
483 }
484
485 /// Prints timing sums for each stack in each threads.
486 template <AggregationType AggType>
487 void printAllPerThread(raw_ostream &OS, FuncIdConversionHelper &FN,
488 StackOutputFormat format) {
489 for (const auto &iter : Roots)
490 printAll<AggType>(OS, FN, iter.second, iter.first, true);
491 }
492
493 /// Prints top stacks from looking at all the leaves and ignoring thread IDs.
494 /// Stacks that consist of the same function IDs but were called in different
495 /// thread IDs are not considered unique in this printout.
496 void printIgnoringThreads(raw_ostream &OS, FuncIdConversionHelper &FN) {
497 RootVector RootValues;
498
499 for (const auto &RootNodeRange : make_second_range(c&: Roots))
500 llvm::append_range(C&: RootValues, R: RootNodeRange);
501
502 print(OS, FN, RootValues);
503 }
504
505 /// Creates a merged list of Tries for unique stacks that disregards their
506 /// thread IDs.
507 RootVector mergeAcrossThreads(std::forward_list<StackTrieNode> &NodeStore) {
508 RootVector MergedByThreadRoots;
509 for (const auto &MapIter : Roots) {
510 const auto &RootNodeVector = MapIter.second;
511 for (auto *Node : RootNodeVector) {
512 auto MaybeFoundIter =
513 find_if(Range&: MergedByThreadRoots, P: [Node](StackTrieNode *elem) {
514 return Node->FuncId == elem->FuncId;
515 });
516 if (MaybeFoundIter == MergedByThreadRoots.end()) {
517 MergedByThreadRoots.push_back(Elt: Node);
518 } else {
519 MergedByThreadRoots.push_back(Elt: mergeTrieNodes(
520 Left: **MaybeFoundIter, Right: *Node, NewParent: nullptr, NodeStore, MergeCallable&: mergeStackDuration));
521 MergedByThreadRoots.erase(CI: MaybeFoundIter);
522 }
523 }
524 }
525 return MergedByThreadRoots;
526 }
527
528 /// Print timing sums for all stacks merged by Thread ID.
529 template <AggregationType AggType>
530 void printAllAggregatingThreads(raw_ostream &OS, FuncIdConversionHelper &FN,
531 StackOutputFormat format) {
532 std::forward_list<StackTrieNode> AggregatedNodeStore;
533 RootVector MergedByThreadRoots = mergeAcrossThreads(NodeStore&: AggregatedNodeStore);
534 bool reportThreadId = false;
535 printAll<AggType>(OS, FN, MergedByThreadRoots,
536 /*threadId*/ 0, reportThreadId);
537 }
538
539 /// Merges the trie by thread id before printing top stacks.
540 void printAggregatingThreads(raw_ostream &OS, FuncIdConversionHelper &FN) {
541 std::forward_list<StackTrieNode> AggregatedNodeStore;
542 RootVector MergedByThreadRoots = mergeAcrossThreads(NodeStore&: AggregatedNodeStore);
543 print(OS, FN, RootValues: MergedByThreadRoots);
544 }
545
546 // TODO: Add a format option when more than one are supported.
547 template <AggregationType AggType>
548 void printAll(raw_ostream &OS, FuncIdConversionHelper &FN,
549 RootVector RootValues, uint32_t ThreadId, bool ReportThread) {
550 SmallVector<const StackTrieNode *, 16> S;
551 for (const auto *N : RootValues) {
552 S.clear();
553 S.push_back(Elt: N);
554 while (!S.empty()) {
555 auto *Top = S.pop_back_val();
556 printSingleStack<AggType>(OS, FN, ReportThread, ThreadId, Top);
557 llvm::append_range(C&: S, R: Top->Callees);
558 }
559 }
560 }
561
562 /// Prints values for stacks in a format consumable for the flamegraph.pl
563 /// tool. This is a line based format that lists each level in the stack
564 /// hierarchy in a semicolon delimited form followed by a space and a numeric
565 /// value. If breaking down by thread, the thread ID will be added as the
566 /// root level of the stack.
567 template <AggregationType AggType>
568 void printSingleStack(raw_ostream &OS, FuncIdConversionHelper &Converter,
569 bool ReportThread, uint32_t ThreadId,
570 const StackTrieNode *Node) {
571 if (ReportThread)
572 OS << "thread_" << ThreadId << ";";
573 SmallVector<const StackTrieNode *, 5> lineage{};
574 lineage.push_back(Elt: Node);
575 while (lineage.back()->Parent != nullptr)
576 lineage.push_back(Elt: lineage.back()->Parent);
577 while (!lineage.empty()) {
578 OS << Converter.SymbolOrNumber(FuncId: lineage.back()->FuncId) << ";";
579 lineage.pop_back();
580 }
581 OS << " " << GetValueForStack<AggType>(Node) << "\n";
582 }
583
584 void print(raw_ostream &OS, FuncIdConversionHelper &FN,
585 RootVector RootValues) {
586 // Go through each of the roots, and traverse the call stack, producing the
587 // aggregates as you go along. Remember these aggregates and stacks, and
588 // show summary statistics about:
589 //
590 // - Total number of unique stacks
591 // - Top 10 stacks by count
592 // - Top 10 stacks by aggregate duration
593 SmallVector<std::pair<const StackTrieNode *, uint64_t>, 11>
594 TopStacksByCount;
595 SmallVector<std::pair<const StackTrieNode *, uint64_t>, 11> TopStacksBySum;
596 auto greater_second =
597 [](const std::pair<const StackTrieNode *, uint64_t> &A,
598 const std::pair<const StackTrieNode *, uint64_t> &B) {
599 return A.second > B.second;
600 };
601 uint64_t UniqueStacks = 0;
602 for (const auto *N : RootValues) {
603 SmallVector<const StackTrieNode *, 16> S;
604 S.emplace_back(Args&: N);
605
606 while (!S.empty()) {
607 auto *Top = S.pop_back_val();
608
609 // We only start printing the stack (by walking up the parent pointers)
610 // when we get to a leaf function.
611 if (!Top->ExtraData.TerminalDurations.empty()) {
612 ++UniqueStacks;
613 auto TopSum =
614 std::accumulate(first: Top->ExtraData.TerminalDurations.begin(),
615 last: Top->ExtraData.TerminalDurations.end(), init: 0uLL);
616 {
617 auto E = std::make_pair(x&: Top, y&: TopSum);
618 TopStacksBySum.insert(
619 I: llvm::lower_bound(Range&: TopStacksBySum, Value&: E, C: greater_second), Elt: E);
620 if (TopStacksBySum.size() == 11)
621 TopStacksBySum.pop_back();
622 }
623 {
624 auto E =
625 std::make_pair(x&: Top, y: Top->ExtraData.TerminalDurations.size());
626 TopStacksByCount.insert(
627 I: llvm::lower_bound(Range&: TopStacksByCount, Value&: E, C: greater_second), Elt: E);
628 if (TopStacksByCount.size() == 11)
629 TopStacksByCount.pop_back();
630 }
631 }
632 llvm::append_range(C&: S, R: Top->Callees);
633 }
634 }
635
636 // Now print the statistics in the end.
637 OS << "\n";
638 OS << "Unique Stacks: " << UniqueStacks << "\n";
639 OS << "Top 10 Stacks by leaf sum:\n\n";
640 for (const auto &P : TopStacksBySum) {
641 OS << "Sum: " << P.second << "\n";
642 printStack(OS, Top: P.first, FN);
643 }
644 OS << "\n";
645 OS << "Top 10 Stacks by leaf count:\n\n";
646 for (const auto &P : TopStacksByCount) {
647 OS << "Count: " << P.second << "\n";
648 printStack(OS, Top: P.first, FN);
649 }
650 OS << "\n";
651 }
652};
653} // namespace
654
655static std::string CreateErrorMessage(StackTrie::AccountRecordStatus Error,
656 const XRayRecord &Record,
657 const FuncIdConversionHelper &Converter) {
658 switch (Error) {
659 case StackTrie::AccountRecordStatus::ENTRY_NOT_FOUND:
660 return std::string(
661 formatv(Fmt: "Found record {0} with no matching function entry\n",
662 Vals: format_xray_record(Record, Converter)));
663 default:
664 return std::string(formatv(Fmt: "Unknown error type for record {0}\n",
665 Vals: format_xray_record(Record, Converter)));
666 }
667}
668
669static CommandRegistration Unused(&Stack, []() -> Error {
670 // Load each file provided as a command-line argument. For each one of them
671 // account to a single StackTrie, and just print the whole trie for now.
672 StackTrie ST;
673 InstrumentationMap Map;
674 if (!StacksInstrMap.empty()) {
675 auto InstrumentationMapOrError = loadInstrumentationMap(Filename: StacksInstrMap);
676 if (!InstrumentationMapOrError)
677 return joinErrors(
678 E1: make_error<StringError>(
679 Args: Twine("Cannot open instrumentation map: ") + StacksInstrMap,
680 Args: std::make_error_code(e: std::errc::invalid_argument)),
681 E2: InstrumentationMapOrError.takeError());
682 Map = std::move(*InstrumentationMapOrError);
683 }
684
685 if (SeparateThreadStacks && AggregateThreads)
686 return make_error<StringError>(
687 Args: Twine("Can't specify options for per thread reporting and reporting "
688 "that aggregates threads."),
689 Args: std::make_error_code(e: std::errc::invalid_argument));
690
691 if (!DumpAllStacks && StacksOutputFormat != HUMAN)
692 return make_error<StringError>(
693 Args: Twine("Can't specify a non-human format without -all-stacks."),
694 Args: std::make_error_code(e: std::errc::invalid_argument));
695
696 if (DumpAllStacks && StacksOutputFormat == HUMAN)
697 return make_error<StringError>(
698 Args: Twine("You must specify a non-human format when reporting with "
699 "-all-stacks."),
700 Args: std::make_error_code(e: std::errc::invalid_argument));
701
702 symbolize::LLVMSymbolizer Symbolizer;
703 FuncIdConversionHelper FuncIdHelper(StacksInstrMap, Symbolizer,
704 Map.getFunctionAddresses());
705 // TODO: Someday, support output to files instead of just directly to
706 // standard output.
707 for (const auto &Filename : StackInputs) {
708 auto TraceOrErr = loadTraceFile(Filename);
709 if (!TraceOrErr) {
710 if (!StackKeepGoing)
711 return joinErrors(
712 E1: make_error<StringError>(
713 Args: Twine("Failed loading input file '") + Filename + "'",
714 Args: std::make_error_code(e: std::errc::invalid_argument)),
715 E2: TraceOrErr.takeError());
716 logAllUnhandledErrors(E: TraceOrErr.takeError(), OS&: errs());
717 continue;
718 }
719 auto &T = *TraceOrErr;
720 StackTrie::AccountRecordState AccountRecordState =
721 StackTrie::AccountRecordState::CreateInitialState();
722 for (const auto &Record : T) {
723 auto error = ST.accountRecord(R: Record, state: &AccountRecordState);
724 if (error != StackTrie::AccountRecordStatus::OK) {
725 if (!StackKeepGoing)
726 return make_error<StringError>(
727 Args: CreateErrorMessage(Error: error, Record, Converter: FuncIdHelper),
728 Args: make_error_code(E: errc::illegal_byte_sequence));
729 errs() << CreateErrorMessage(Error: error, Record, Converter: FuncIdHelper);
730 }
731 }
732 }
733 if (ST.isEmpty()) {
734 return make_error<StringError>(
735 Args: "No instrumented calls were accounted in the input file.",
736 Args: make_error_code(E: errc::result_out_of_range));
737 }
738
739 // Report the stacks in a long form mode for another tool to analyze.
740 if (DumpAllStacks) {
741 if (AggregateThreads) {
742 switch (RequestedAggregation) {
743 case AggregationType::TOTAL_TIME:
744 ST.printAllAggregatingThreads<AggregationType::TOTAL_TIME>(
745 OS&: outs(), FN&: FuncIdHelper, format: StacksOutputFormat);
746 break;
747 case AggregationType::INVOCATION_COUNT:
748 ST.printAllAggregatingThreads<AggregationType::INVOCATION_COUNT>(
749 OS&: outs(), FN&: FuncIdHelper, format: StacksOutputFormat);
750 break;
751 }
752 } else {
753 switch (RequestedAggregation) {
754 case AggregationType::TOTAL_TIME:
755 ST.printAllPerThread<AggregationType::TOTAL_TIME>(OS&: outs(), FN&: FuncIdHelper,
756 format: StacksOutputFormat);
757 break;
758 case AggregationType::INVOCATION_COUNT:
759 ST.printAllPerThread<AggregationType::INVOCATION_COUNT>(
760 OS&: outs(), FN&: FuncIdHelper, format: StacksOutputFormat);
761 break;
762 }
763 }
764 return Error::success();
765 }
766
767 // We're only outputting top stacks.
768 if (AggregateThreads) {
769 ST.printAggregatingThreads(OS&: outs(), FN&: FuncIdHelper);
770 } else if (SeparateThreadStacks) {
771 ST.printPerThread(OS&: outs(), FN&: FuncIdHelper);
772 } else {
773 ST.printIgnoringThreads(OS&: outs(), FN&: FuncIdHelper);
774 }
775 return Error::success();
776});
777