1 //===- trie-node.h - XRay Call Stack Data Structure -----------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file provides a data structure and routines for working with call stacks
11 // of instrumented functions.
12 //
13 //===----------------------------------------------------------------------===//
14
15 #ifndef LLVM_TOOLS_LLVM_XRAY_STACK_TRIE_H
16 #define LLVM_TOOLS_LLVM_XRAY_STACK_TRIE_H
17
18 #include <forward_list>
19 #include <numeric>
20
21 #include "llvm/ADT/DenseMap.h"
22 #include "llvm/ADT/STLExtras.h"
23 #include "llvm/ADT/SmallVector.h"
24
25 /// A type to represent a trie of invocations. It is useful to construct a
26 /// graph of these nodes from reading an XRay trace, such that each function
27 /// call can be placed in a larger context.
28 ///
29 /// The template parameter allows users of the template to attach their own
30 /// data elements to each node in the invocation graph.
31 template <typename AssociatedData> struct TrieNode {
32 /// The function ID.
33 int32_t FuncId;
34
35 /// The caller of this function.
36 TrieNode<AssociatedData> *Parent;
37
38 /// The callees from this function.
39 llvm::SmallVector<TrieNode<AssociatedData> *, 4> Callees;
40
41 /// Additional parameterized data on each node.
42 AssociatedData ExtraData;
43 };
44
45 /// Merges together two TrieNodes with like function ids, aggregating their
46 /// callee lists and durations. The caller must provide storage where new merged
47 /// nodes can be allocated in the form of a linked list.
48 template <typename T, typename Callable>
49 TrieNode<T> *
mergeTrieNodes(const TrieNode<T> & Left,const TrieNode<T> & Right,typename std::remove_reference<TrieNode<T> * >::type NewParent,std::forward_list<TrieNode<T>> & NodeStore,Callable && MergeCallable)50 mergeTrieNodes(const TrieNode<T> &Left, const TrieNode<T> &Right,
51 /*Non-deduced pointer type for nullptr compatibility*/
52 typename std::remove_reference<TrieNode<T> *>::type NewParent,
53 std::forward_list<TrieNode<T>> &NodeStore,
54 Callable &&MergeCallable) {
55 llvm::function_ref<T(const T &, const T &)> MergeFn(
56 std::forward<Callable>(MergeCallable));
57 assert(Left.FuncId == Right.FuncId);
58 NodeStore.push_front(TrieNode<T>{
59 Left.FuncId, NewParent, {}, MergeFn(Left.ExtraData, Right.ExtraData)});
60 auto I = NodeStore.begin();
61 auto *Node = &*I;
62
63 // Build a map of callees from the left side.
64 llvm::DenseMap<int32_t, TrieNode<T> *> LeftCalleesByFuncId;
65 for (auto *Callee : Left.Callees) {
66 LeftCalleesByFuncId[Callee->FuncId] = Callee;
67 }
68
69 // Iterate through the right side, either merging with the map values or
70 // directly adding to the Callees vector. The iteration also removes any
71 // merged values from the left side map.
72 // TODO: Unroll into iterative and explicit stack for efficiency.
73 for (auto *Callee : Right.Callees) {
74 auto iter = LeftCalleesByFuncId.find(Callee->FuncId);
75 if (iter != LeftCalleesByFuncId.end()) {
76 Node->Callees.push_back(
77 mergeTrieNodes(*(iter->second), *Callee, Node, NodeStore, MergeFn));
78 LeftCalleesByFuncId.erase(iter);
79 } else {
80 Node->Callees.push_back(Callee);
81 }
82 }
83
84 // Add any callees that weren't found in the right side.
85 for (auto MapPairIter : LeftCalleesByFuncId) {
86 Node->Callees.push_back(MapPairIter.second);
87 }
88
89 return Node;
90 }
91
92 #endif // LLVM_TOOLS_LLVM_XRAY_STACK_TRIE_H
93