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> * 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
