contrib/llvm/tools/llvm-xray/trie-node.h

   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