[XRay][profiler] Part 2: XRay Function Call Trie

Summary:
This is part of the larger XRay Profiling Mode effort.

This patch implements a central data structure for capturing statistics
about XRay instrumented function call stacks. The `FunctionCallTrie`
type does the following things:

*  It keeps track of a shadow function call stack of XRay instrumented
   functions as they are entered (function enter event) and as they are
   exited (function exit event).

*  When a function is entered, the shadow stack contains information
   about the entry TSC, and updates the trie (or prefix tree)
   representing the current function call stack. If we haven't
   encountered this function call before, this creates a unique node for
   the function in this position on the stack. We update the list of
   callees of the parent function as well to reflect this newly found
   path.

*  When a function is exited, we compute statistics (TSC deltas,
   function call count frequency) for the associated function(s) up the
   stack as we unwind to find the matching entry event.

This builds upon the XRay `Allocator` and `Array` types in Part 1 of
this series of patches.

Depends on D45756.

Reviewers: echristo, pelikan, kpw

Reviewed By: kpw

Subscribers: llvm-commits, mgorny

Differential Revision: https://reviews.llvm.org/D45757

llvm-svn: 332313

0 files changed, 0 insertions, 0 deletions