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


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

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


dberrisMay 14 2018, 5:42 PM
Differential Revision
D45757: [XRay][profiler] Part 2: XRay Function Call Trie