Initial work on the XRay Graph tool.

[varno]

Summary

[XRay] Implement the llvm-xray graph subcommand

This is an innitial change to implement a new subcommand for the llvm-xray tool.

Here we define the graph subcommand which generates a graph from the function
call information and uses it to present the call information graphically with
additional annotations. This tool was originally proposed by dberris.

Depends on D24377.

[dberris]

Needs tests.

[varno]

• Extra work making the xray-graph tool more powerful.
• Further work on options in llvm-xray graph subcommand
• Created Tests

[dberris]

Some style comments.

As for tests I think this is an OK set for first tests, but it'd be good to look at error conditions and making sure we're handling those appropriately.

tools/llvm-xray/xray-graph.cc

122

Can you use .emplace_back(...) instead here?

156–157

Please add an empty line between the end of function definitions, and the start of the next function.

tools/llvm-xray/xray-graph.h

28–29

Please add an empty line between last non-comment and first comment lines.

76

Can you use a SmallVector<...> instead of a std::vector<...>?

116–125

Can this not happen incrementally, as we're adding the records, or on demand when we export? i.e. why do they need to be public functions?

127–128

Does this need to be part of the class? Could this not be a function in the implementation?

[varno]

tools/llvm-xray/xray-graph.cc

122

No.

tools/llvm-xray/xray-graph.h

116–125

Not really, all the records need to be added before we calculate the statistics. And I was wanting the statistics calculated to do graph transformations later (before output).

127–128

I suppose it could be a friend function, it uses private types (the TimeStat type).

[varno]

• Reply to dberris comments.

[dberris]

The formatting changes I suspect can be automated away by using clang-format, so we don't have to spend too many cycles just getting those things "right". :)

tools/llvm-xray/xray-graph.cc

175–176

Empty line between these two lines?

188–197

The indentation here is a little weird. Fix?

tools/llvm-xray/xray-graph.h

116–125

Sure, but why aren't these just implementation details of the exportGraphAsDOT(...) function?

127–128

It doesn't have to use that type, right? I suspect you could just make this a template in the unnamed namespace in the implementation. Or that type could just be public and you could just use it (i.e for example you might want to be able to provide an iterator to the graph later, so that other commands can leverage the graph too).

[varno]

• Comments by Dberris

[varno]

tools/llvm-xray/xray-graph.h

116–125

I suppose that right now they could be, but I have plans that require them to be run before exportGraphAsDOT

[dberris]

Did you run this through clang-format in LLVM mode?

tools/llvm-xray/xray-graph.cc

230–231

Missing empty line between these two.

345–348

I'm looking at these lines and thinking it seems they're unnecessarily exposing implementation details -- really these things are something the graph renderer can decide itself if it took the file header as an argument to the constructor. And these really ought to just happen when we're exporting the data as DOT and passing arguments to the kind of data we want to see.

tools/llvm-xray/xray-graph.h

116–125

I suspect we can break these out later if we really need to. For now, they're a distraction and from an API design perspective, really brittle -- if someone wants to use this class they have to know to call these functions before exporting. If this doesn't happen while we're accounting the records, then this means the state of the graph is not easily determined.

If for example an external algorithm requires the graph, then we ought to be able to access the graph itself -- and maybe the accounting ought to happen externally instead, as an algorithm that passes through the graph we've built or as an extension to the graph traversal algorithm being employed, exposed as a method to this class.

[varno]

• Replying to comments

[varno]

tools/llvm-xray/xray-graph.h

116–125

Ok, I'll break them out and we can add them in later if needed

[dberris]

tools/llvm-xray/xray-graph.h

44–45

Missing empty line between these two.

75–76

Missing line in between these two.

[varno]

• Patch comment reply

[dberris]

Now had a look closely at the implementation. Please pardon the piecemeal review.

tools/llvm-xray/xray-graph.cc

103

Potentially spurious empty line here.

118

Also potentially spurious empty line here.

143–149

So I think in a future change which we talked about offline, we ought to make this and the account tool work with each other in some form of refactored implementation -- where the account tool can depend on the graph tool instead of duplicating a lot of this logic.

If you rebase against the account change (D24377) then the version used there now has less calls to .pop_back() on the vector, and also has a simpler loop as a result (i.e. you don't need the extra spillover logic, and the version there has less nesting and more straight-line code anyway.

The actionable comment right now I think would be a //FIXME: Refactor this and the account subcommand to reduce code duplication

151

Maybe use a name that isn't overloaded in this context -- D is a perfectly fine letter for something that indicates the delta between two numbers.

205–206

Empty line in between, and don't need void in the function arguments.

215

No need for void in the function arguments.

216

Consider also using a SmallVector here, with potentially the same initial size as with the adjacency list we maintain.

222

It's thoroughly confusing too that you're using Timings here, but there's a data member named Timings as well. :)

222–229

Is there no way to do this in a single pass, in the same loop above? I could imagine building a map that contains a vertex as the key, then accumulating statistics as you go traversing the graph (or even just storing the data anyway like you do here for the timings), and another pass to collapse that data.

tools/llvm-xray/xray-graph.h

89

Why are the iterators not the same type?

93

No need for void in the function arguments.

[varno]

• Comments

[varno]

tools/llvm-xray/xray-graph.cc

222–229

Really not, the way here has linear space and uses the required memory for each section. If we did not care about memory I could store the accumulation data for both edges and vertices. but otherwise ???

[varno]

• Reply to dberris comments.
• Comments
• comments

[dberris]

From a style perspective and implementation I think this is mostly OK -- waiting on @dblaikie to have a look.

tools/llvm-xray/xray-graph.cc

222–229

Right, so the alternate body of the function seems to be more straight-forward, and the amount of memory being used isn't that bad. You can even be smart about this and have an upper bound on the elements in the vector, and as you insert you keep a relative order and track median, and other percentiles incrementally. That's not as critical as the functionality though, and we can tune this as we go along late anyway if we encounter really big graphs in practice that would cause this to be a huge problem (either as implemented or even in the alternative version).

I'm happy either way if you choose to stick with the current implementation, but if you do consider just removing the alternate implementation you have here #ifdef 0'd out.

[dblaikie]

test/tools/llvm-xray/X86/graph-deduce-tail-call.yaml

8–17 ↗

(On Diff #80696)

This seems to be passing a variety of values for '-e' but tests that the behavior is the same in all of them. I'm assuming the flag does something - do you have tests that confirm that it does the right thing? (somewhat similar for the top two test cases too)

39–40 ↗

(On Diff #80696)

Is deduce-sibling-calls tested?

tools/llvm-xray/xray-graph.cc

212–213

Is this optimization worthwhile? Or could we put this as a local variable in the outer loop below - no need to clear it, etc.

223

Remove dead code

288–289

Probably skip the extra language like "does what the name suggests" and "does this in the expected way".

If it's pretty obvious/self explanatory, then a brief comment is OK.

341–342

Should this be silently handled? If a user specifies a file, seems like we should error if it's not there

(@dberris - goes for existing tools too, I imagine, guess I didn't notice this in the others)

359

Move this to where it's used (then you could even use 'const auto *' if you like

[varno]

test/tools/llvm-xray/X86/graph-deduce-tail-call.yaml

8–17 ↗

(On Diff #80696)

I need to add additional test cases for these, however the test case size for -e 99p must be quite long in order for it to work. Will add in next revision of patch.

39–40 ↗

(On Diff #80696)

Yes. Otherwise the graph would only have two nodes with timing information

tools/llvm-xray/xray-graph.cc

212–213

I think it is worth while, however I have no testing results. At this time, as I am working on a patch which changes how this code works completely due to a new data structure, I don't know.

[dberris]

test/tools/llvm-xray/X86/graph-simple-case.yaml

34–35 ↗

(On Diff #80696)

Did you need to write "DAG" here somewhere too?

tools/llvm-xray/CMakeLists.txt

12–16

Rebasing this to tip of trunk now that 'llvm-xray account' has landed might mean this dependency goes away now.

tools/llvm-xray/xray-graph.cc

212–213

I'd urge you to not change this patch, but instead stack one on top of it instead for any further changes you'd need to do. I'd much rather do that review of the refactoring separately than doing this review over with new data structures.

341–342

I think we at least should print something to the effect of "well, we can't symbolise properly". I'm happy with making this an explicit error, to not give users potentially misleading results.

359

Given the changes that have landed now, there's a better way of doing this (if we look at what's happening in llvm-xray account at least).

[varno]

Rebase and addess comment.

[varno]

test/tools/llvm-xray/X86/graph-simple-case.yaml

34–35 ↗

(On Diff #80696)

I don't need DAG here as there is only one edge in this graph.

[dberris]

test/tools/llvm-xray/X86/graph-simple-case.yaml

34–35 ↗

(On Diff #80696)

So as written, this will mean that if these lines are not arranged in exactly this order, the test will pass. If you meant to preserve order of the output lines being checked, you pick either -DAG: or -NEXT:.

This means, instead of:

#EMPTY:
#EMPTY:
#EMPTY:

It ought to be:

#EMPTY:
#EMPTY-NEXT:
#EMPTY-NEXT:
#EMPTY-NEXT:

to preserve the order of lines and matching.

[varno]

• Initial work on the XRay Graph tool.
• clang-format

[varno]

• fix tests

[varno]

Hi dblakie, I was wondering if you could land this patch for me?

[labath]

Please try to avoid adding pid_t references. This type is not available on windows. llvm::sys::ProcessInfo::ProcessId is a possible replacement (i've fixed the usage in this commit in r292206).

test/tools/llvm-xray/X86/Inputs/simple-instrmap.yaml

+# This is a simple instrumentation map with bogus addresses and offsets, but
+# follow the recommended format.
+---
+- { id: 1, address: 0x1, function: 0x1, kind: function-enter, always-instrument: true}
+- { id: 1, address: 0x2, function: 0x1, kind: function-exit, always-instrument: true}
+- { id: 2, address: 0x2, function: 0x2, kind: function-enter, always-instrument: true}
+- { id: 2, address: 0x3, function: 0x2, kind: function-exit, always-instrument: true}
+- { id: 3, address: 0x3, function: 0x3, kind: function-enter, always-instrument: true}
+- { id: 3, address: 0x4, function: 0x3, kind: function-exit, always-instrument: true}
+...

test/tools/llvm-xray/X86/Inputs/simple-xray-instrmap.yaml

+---
+- { id: 1, address: 0x000000000041CA40, function: 0x000000000041CA40, kind: function-enter, 
+    always-instrument: true }
+- { id: 1, address: 0x000000000041CA50, function: 0x000000000041CA40, kind: tail-exit, 
+    always-instrument: true }
+- { id: 2, address: 0x000000000041CA70, function: 0x000000000041CA70, kind: function-enter, 
+    always-instrument: true }
+- { id: 2, address: 0x000000000041CA7C, function: 0x000000000041CA70, kind: tail-exit, 
+    always-instrument: true }
+- { id: 3, address: 0x000000000041CAA0, function: 0x000000000041CAA0, kind: function-enter, 
+    always-instrument: true }
+- { id: 3, address: 0x000000000041CAB4, function: 0x000000000041CAA0, kind: function-exit, 
+    always-instrument: true }
+...

test/tools/llvm-xray/X86/account-deduce-tail-call.yaml

+#RUN: llvm-xray account %s -i=yaml -o - -m %S/Inputs/simple-instrmap.yaml -t yaml -d | FileCheck %s
+---
+header:
+  version: 1
+  type: 0
+  constant-tsc: true
+  nonstop-tsc: true
+  cycle-frequency: 0
+records:
+# Here we reconstruct the following call trace:
+#
+#   f1()
+#     f2()
+#       f3()
+#
+# But we find that we're missing an exit record for f2() because it's
+# tail-called f3(). We make sure that if we see a trace like this that we can
+# deduce tail calls, and account the time (potentially wrongly) to f2() when
+# f1() exits. That is because we don't go back to f3()'s entry record to
+# properly do the math on the timing of f2().
+#
+# Note that by default, tail/sibling call deduction is disabled, and is enabled
+# with a flag "-d" or "-deduce-sibling-calls".
+#
+  - { type: 0, func-id: 1, cpu: 1, thread: 111, kind: function-enter, tsc: 10000 }
+  - { type: 0, func-id: 2, cpu: 1, thread: 111, kind: function-enter, tsc: 10001 }
+  - { type: 0, func-id: 3, cpu: 1, thread: 111, kind: function-enter, tsc: 10002 }
+  - { type: 0, func-id: 3, cpu: 1, thread: 111, kind: function-exit,  tsc: 10003 }
+  - { type: 0, func-id: 1, cpu: 1, thread: 111, kind: function-exit,  tsc: 10004 }
+...
+
+#CHECK:       Functions with latencies: 3
+#CHECK-NEXT:  funcid  count  [min, median, 90%ile, 99%ile, max] debug function
+#CHECK-NEXT:  1 1 [4.{{.*}}, 4.{{.*}}, 4.{{.*}}, 4.{{.*}}, 4.{{.*}}] {{.*}} {{.*}}
+#CHECK-NEXT:  2 1 [3.{{.*}}, 3.{{.*}}, 3.{{.*}}, 3.{{.*}}, 3.{{.*}}] {{.*}} {{.*}}
+#CHECK-NEXT:  3 1 [1.{{.*}}, 1.{{.*}}, 1.{{.*}}, 1.{{.*}}, 1.{{.*}}] {{.*}} {{.*}}

test/tools/llvm-xray/X86/account-simple-case.yaml

+#RUN: llvm-xray account %s -i=yaml -o - -m %S/Inputs/simple-instrmap.yaml -t yaml | FileCheck %s
+---
+header:
+  version: 1
+  type: 0
+  constant-tsc: true
+  nonstop-tsc: true
+  cycle-frequency: 2601000000
+records:
+  - { type: 0, func-id: 1, cpu: 1, thread: 111, kind: function-enter,
+    tsc: 10001 }
+  - { type: 0, func-id: 1, cpu: 1, thread: 111, kind: function-exit,
+    tsc: 10100 }
+...
+
+#CHECK:       Functions with latencies: 1
+#CHECK-NEXT:  funcid  count  [min, median, 90%ile, 99%ile, max] debug function
+#CHECK-NEXT:  1 1 [{{.*}}, {{.*}}, {{.*}}, {{.*}}, {{.*}}] {{.*}} {{.*}}

test/tools/llvm-xray/X86/convert-roundtrip.yaml

+#RUN: llvm-xray convert %s -i=yaml -f=raw -o %t && llvm-xray convert %t -f=yaml -o - | FileCheck %s
+---
+header:
+  version: 1
+  type: 0
+  constant-tsc: true
+  nonstop-tsc: true
+  cycle-frequency: 2601000000
+records:
+  - { type: 0, func-id: 1, cpu: 1, thread: 111, kind: function-enter,
+    tsc: 10001 }
+  - { type: 0, func-id: 1, cpu: 1, thread: 111, kind: function-exit,
+    tsc: 10100 }
+...
+
+#CHECK:       ---
+#CHECK-NEXT:  header:
+#CHECK-NEXT:    version: 1
+#CHECK-NEXT:    type: 0
+#CHECK-NEXT:    constant-tsc: true
+#CHECK-NEXT:    nonstop-tsc: true
+#CHECK-NEXT:    cycle-frequency: 2601000000
+#CHECK-NEXT:  records:
+#CHECK-NEXT:    - { type: 0, func-id: 1, function: '1', cpu: 1, thread: 111, kind: function-enter,
+#CHECK-NEXT:      tsc: 10001 }
+#CHECK-NEXT:    - { type: 0, func-id: 1, function: '1', cpu: 1, thread: 111, kind: function-exit,
+#CHECK-NEXT:      tsc: 10100 }
+#CHECK-NEXT:  ...

test/tools/llvm-xray/X86/convert-to-yaml.txt

+; RUN: llvm-xray convert %S/Inputs/naive-log-simple.xray -f=yaml -o - | FileCheck %s
+
+; CHECK:      ---
+; CHECK-NEXT: header:
+; CHECK-NEXT:   version:         1
+; CHECK-NEXT:   type:            0
+; CHECK-NEXT:   constant-tsc:    true
+; CHECK-NEXT:   nonstop-tsc:     true
+; CHECK-NEXT:   cycle-frequency: 2601000000
+; CHECK-NEXT: records:
+; CHECK-NEXT:   - { type: 0, func-id: 3, function: '3', cpu: 37, thread: 84697, kind: function-enter,
+; CHECK-NEXT:       tsc: 3315356841453914 }
+; CHECK-NEXT:   - { type: 0, func-id: 2, function: '2', cpu: 37, thread: 84697, kind: function-enter,
+; CHECK-NEXT:       tsc: 3315356841454542 }
+; CHECK-NEXT:   - { type: 0, func-id: 2, function: '2', cpu: 37, thread: 84697, kind: function-exit,
+; CHECK-NEXT:       tsc: 3315356841454670 }
+; CHECK-NEXT:   - { type: 0, func-id: 1, function: '1', cpu: 37, thread: 84697, kind: function-enter,
+; CHECK-NEXT:       tsc: 3315356841454762 }
+; CHECK-NEXT:   - { type: 0, func-id: 1, function: '1', cpu: 37, thread: 84697, kind: function-exit,
+; CHECK-NEXT:       tsc: 3315356841454802 }
+; CHECK-NEXT:   - { type: 0, func-id: 3, function: '3', cpu: 37, thread: 84697, kind: function-exit,
+; CHECK-NEXT:       tsc: 3315356841494828 }
+; CHECK-NEXT: ...

test/tools/llvm-xray/X86/convert-with-debug-syms.txt

+; RUN: llvm-xray convert -m %S/Inputs/elf64-sample-o2.bin -y %S/Inputs/naive-log-simple.xray -f=yaml -o - 2>&1 | FileCheck %s
+
+; CHECK:      ---
+; CHECK-NEXT: header:
+; CHECK-NEXT:   version:         1
+; CHECK-NEXT:   type:            0
+; CHECK-NEXT:   constant-tsc:    true
+; CHECK-NEXT:   nonstop-tsc:     true
+; CHECK-NEXT:   cycle-frequency: 2601000000
+; CHECK-NEXT: records:
+; CHECK-NEXT:   - { type: 0, func-id: 3, function: main, cpu: 37, thread: 84697, kind: function-enter,
+; CHECK-NEXT:       tsc: 3315356841453914 }
+; CHECK-NEXT:   - { type: 0, func-id: 2, function: 'foo()', cpu: 37, thread: 84697, kind: function-enter,
+; CHECK-NEXT:       tsc: 3315356841454542 }
+; CHECK-NEXT:   - { type: 0, func-id: 2, function: 'foo()', cpu: 37, thread: 84697, kind: function-exit,
+; CHECK-NEXT:       tsc: 3315356841454670 }
+; CHECK-NEXT:   - { type: 0, func-id: 1, function: 'bar()', cpu: 37, thread: 84697, kind: function-enter,
+; CHECK-NEXT:       tsc: 3315356841454762 }
+; CHECK-NEXT:   - { type: 0, func-id: 1, function: 'bar()', cpu: 37, thread: 84697, kind: function-exit,
+; CHECK-NEXT:       tsc: 3315356841454802 }
+; CHECK-NEXT:   - { type: 0, func-id: 3, function: main, cpu: 37, thread: 84697, kind: function-exit,
+; CHECK-NEXT:       tsc: 3315356841494828 }
+; CHECK-NEXT: ...

test/tools/llvm-xray/X86/convert-with-standalone-instrmap.txt

+; RUN: llvm-xray convert -m %S/Inputs/elf64-objcopied-instrmap.bin -y %S/Inputs/naive-log-simple.xray -f=yaml -o - 2>&1 | FileCheck %s
+
+; CHECK:      ---
+; CHECK-NEXT: header:
+; CHECK-NEXT:   version:         1
+; CHECK-NEXT:   type:            0
+; CHECK-NEXT:   constant-tsc:    true
+; CHECK-NEXT:   nonstop-tsc:     true
+; CHECK-NEXT:   cycle-frequency: 2601000000
+; CHECK-NEXT: records:
+; CHECK-NEXT:   - { type: 0, func-id: 3, function: '@(41caa0)', cpu: 37, thread: 84697,
+; CHECK-NEXT:       kind: function-enter, tsc: 3315356841453914 }
+; CHECK-NEXT:   - { type: 0, func-id: 2, function: '@(41ca70)', cpu: 37, thread: 84697,
+; CHECK-NEXT:       kind: function-enter, tsc: 3315356841454542 }
+; CHECK-NEXT:   - { type: 0, func-id: 2, function: '@(41ca70)', cpu: 37, thread: 84697,
+; CHECK-NEXT:       kind: function-exit, tsc: 3315356841454670 }
+; CHECK-NEXT:   - { type: 0, func-id: 1, function: '@(41ca40)', cpu: 37, thread: 84697,
+; CHECK-NEXT:       kind: function-enter, tsc: 3315356841454762 }
+; CHECK-NEXT:   - { type: 0, func-id: 1, function: '@(41ca40)', cpu: 37, thread: 84697,
+; CHECK-NEXT:       kind: function-exit, tsc: 3315356841454802 }
+; CHECK-NEXT:   - { type: 0, func-id: 3, function: '@(41caa0)', cpu: 37, thread: 84697,
+; CHECK-NEXT:       kind: function-exit, tsc: 3315356841494828 }
+; CHECK-NEXT: ...

test/tools/llvm-xray/X86/convert-with-yaml-instrmap.txt

+; RUN: llvm-xray convert -m %S/Inputs/simple-xray-instrmap.yaml -t yaml %S/Inputs/naive-log-simple.xray -f=yaml -o - | FileCheck %s
+
+; CHECK:      ---
+; CHECK-NEXT: header:
+; CHECK-NEXT:   version:         1
+; CHECK-NEXT:   type:            0
+; CHECK-NEXT:   constant-tsc:    true
+; CHECK-NEXT:   nonstop-tsc:     true
+; CHECK-NEXT:   cycle-frequency: 2601000000
+; CHECK-NEXT: records:
+; CHECK-NEXT:   - { type: 0, func-id: 3, function: '3', cpu: 37, thread: 84697, kind: function-enter,
+; CHECK-NEXT:       tsc: 3315356841453914 }
+; CHECK-NEXT:   - { type: 0, func-id: 2, function: '2', cpu: 37, thread: 84697, kind: function-enter,
+; CHECK-NEXT:       tsc: 3315356841454542 }
+; CHECK-NEXT:   - { type: 0, func-id: 2, function: '2', cpu: 37, thread: 84697, kind: function-exit,
+; CHECK-NEXT:       tsc: 3315356841454670 }
+; CHECK-NEXT:   - { type: 0, func-id: 1, function: '1', cpu: 37, thread: 84697, kind: function-enter,
+; CHECK-NEXT:       tsc: 3315356841454762 }
+; CHECK-NEXT:   - { type: 0, func-id: 1, function: '1', cpu: 37, thread: 84697, kind: function-exit,
+; CHECK-NEXT:       tsc: 3315356841454802 }
+; CHECK-NEXT:   - { type: 0, func-id: 3, function: '3', cpu: 37, thread: 84697, kind: function-exit,
+; CHECK-NEXT:       tsc: 3315356841494828 }
+; CHECK-NEXT: ...

tools/llvm-xray/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   ${LLVM_TARGETS_TO_BUILD}
+  DebugInfoDWARF
+  Object
   Support
-  Object)
+  Symbolize)
 
 set(LLVM_XRAY_TOOLS
+  func-id-helper.cc
+  xray-account.cc
+  xray-converter.cc
   xray-extract.cc
-  xray-registry.cc)
+  xray-extract.cc
+  xray-log-reader.cc
+  xray-registry.cc
+  xray-graph.cc)
 
 add_llvm_tool(llvm-xray llvm-xray.cc ${LLVM_XRAY_TOOLS})

tools/llvm-xray/func-id-helper.h

+//===- func-id-helper.h - XRay Function ID Conversion Helpers -------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Defines helper tools dealing with XRay-generated function ids.
+//
+//===----------------------------------------------------------------------===//
+#ifndef LLVM_TOOLS_LLVM_XRAY_FUNC_ID_HELPER_H
+#define LLVM_TOOLS_LLVM_XRAY_FUNC_ID_HELPER_H
+
+#include "llvm/DebugInfo/Symbolize/Symbolize.h"
+#include <unordered_map>
+
+namespace llvm {
+namespace xray {
+
+// This class consolidates common operations related to Function IDs.
+class FuncIdConversionHelper {
+public:
+  using FunctionAddressMap = std::unordered_map<int32_t, uint64_t>;
+
+private:
+  std::string BinaryInstrMap;
+  symbolize::LLVMSymbolizer &Symbolizer;
+  const FunctionAddressMap &FunctionAddresses;
+
+public:
+  FuncIdConversionHelper(std::string BinaryInstrMap,
+                         symbolize::LLVMSymbolizer &Symbolizer,
+                         const FunctionAddressMap &FunctionAddresses)
+      : BinaryInstrMap(std::move(BinaryInstrMap)), Symbolizer(Symbolizer),
+        FunctionAddresses(FunctionAddresses) {}
+
+  // Returns the symbol or a string representation of the function id.
+  std::string SymbolOrNumber(int32_t FuncId) const;
+
+  // Returns the file and column from debug info for the given function id.
+  std::string FileLineAndColumn(int32_t FuncId) const;
+};
+
+} // namespace xray
+} // namespace llvm
+
+#endif // LLVM_TOOLS_LLVM_XRAY_FUNC_ID_HELPER_H

tools/llvm-xray/func-id-helper.cc

+//===- xray-fc-account.cc - XRay Function Call Accounting Tool ------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Implementation of the helper tools dealing with XRay-generated function ids.
+//
+//===----------------------------------------------------------------------===//
+
+#include "func-id-helper.h"
+#include "llvm/Support/Path.h"
+#include <sstream>
+
+using namespace llvm;
+using namespace xray;
+
+std::string FuncIdConversionHelper::SymbolOrNumber(int32_t FuncId) const {
+  std::ostringstream F;
+  auto It = FunctionAddresses.find(FuncId);
+  if (It == FunctionAddresses.end()) {
+    F << "#" << FuncId;
+    return F.str();
+  }
+
+  if (auto ResOrErr = Symbolizer.symbolizeCode(BinaryInstrMap, It->second)) {
+    auto &DI = *ResOrErr;
+    if (DI.FunctionName == "<invalid>")
+      F << "@(" << std::hex << It->second << ")";
+    else
+      F << DI.FunctionName;
+  } else
+    handleAllErrors(ResOrErr.takeError(), [&](const ErrorInfoBase &) {
+      F << "@(" << std::hex << It->second << ")";
+    });
+
+  return F.str();
+}
+
+std::string FuncIdConversionHelper::FileLineAndColumn(int32_t FuncId) const {
+  auto It = FunctionAddresses.find(FuncId);
+  if (It == FunctionAddresses.end())
+    return "(unknown)";
+
+  std::ostringstream F;
+  auto ResOrErr = Symbolizer.symbolizeCode(BinaryInstrMap, It->second);
+  if (!ResOrErr) {
+    consumeError(ResOrErr.takeError());
+    return "(unknown)";
+  }
+
+  auto &DI = *ResOrErr;
+  F << sys::path::filename(DI.FileName).str() << ":" << DI.Line << ":"
+    << DI.Column;
+
+  return F.str();
+}

tools/llvm-xray/xray-account.h

+//===- xray-account.h - XRay Function Call Accounting ---------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines the interface for performing some basic function call
+// accounting from an XRay trace.
+//
+//===----------------------------------------------------------------------===//
+#ifndef LLVM_TOOLS_LLVM_XRAY_XRAY_ACCOUNT_H
+#define LLVM_TOOLS_LLVM_XRAY_XRAY_ACCOUNT_H
+
+#include <map>
+#include <utility>
+#include <vector>
+
+#include "func-id-helper.h"
+#include "xray-record.h"
+#include "llvm/Support/raw_ostream.h"
+
+namespace llvm {
+namespace xray {
+
+class LatencyAccountant {
+public:
+  typedef std::map<int32_t, std::vector<uint64_t>> FunctionLatencyMap;
+  typedef std::map<pid_t, std::pair<uint64_t, uint64_t>> PerThreadMinMaxTSCMap;
+  typedef std::map<uint8_t, std::pair<uint64_t, uint64_t>> PerCPUMinMaxTSCMap;
+  typedef std::vector<std::pair<int32_t, uint64_t>> FunctionStack;
+  typedef std::map<pid_t, FunctionStack> PerThreadFunctionStackMap;
+
+private:
+  PerThreadFunctionStackMap PerThreadFunctionStack;
+  FunctionLatencyMap FunctionLatencies;
+  PerThreadMinMaxTSCMap PerThreadMinMaxTSC;
+  PerCPUMinMaxTSCMap PerCPUMinMaxTSC;
+  FuncIdConversionHelper &FuncIdHelper;
+
+  bool DeduceSiblingCalls = false;
+  uint64_t CurrentMaxTSC = 0;
+
+  void recordLatency(int32_t FuncId, uint64_t Latency) {
+    FunctionLatencies[FuncId].push_back(Latency);
+  }
+
+public:
+  explicit LatencyAccountant(FuncIdConversionHelper &FuncIdHelper,
+                             bool DeduceSiblingCalls)
+      : FuncIdHelper(FuncIdHelper), DeduceSiblingCalls(DeduceSiblingCalls) {}
+
+  const FunctionLatencyMap &getFunctionLatencies() const {
+    return FunctionLatencies;
+  }
+
+  const PerThreadMinMaxTSCMap &getPerThreadMinMaxTSC() const {
+    return PerThreadMinMaxTSC;
+  }
+
+  const PerCPUMinMaxTSCMap &getPerCPUMinMaxTSC() const {
+    return PerCPUMinMaxTSC;
+  }
+
+  /// Returns false in case we fail to account the provided record. This happens
+  /// in the following cases:
+  ///
+  ///   - An exit record does not match any entry records for the same function.
+  ///     If we've been set to deduce sibling calls, we try walking up the stack
+  ///     and recording times for the higher level functions.
+  ///   - A record has a TSC that's before the latest TSC that has been
+  ///     recorded. We still record the TSC for the min-max.
+  ///
+  bool accountRecord(const XRayRecord &Record);
+
+  const FunctionStack *getThreadFunctionStack(pid_t TId) const {
+    auto I = PerThreadFunctionStack.find(TId);
+    if (I == PerThreadFunctionStack.end())
+      return nullptr;
+    return &I->second;
+  }
+
+  const PerThreadFunctionStackMap &getPerThreadFunctionStack() const {
+    return PerThreadFunctionStack;
+  }
+
+  // Output Functions
+  // ================
+
+  void exportStatsAsTEXT(raw_ostream &OS, const XRayFileHeader &Header) const;
+  void exportStatsAsCSV(raw_ostream &OS, const XRayFileHeader &Header) const;
+
+private:
+  // Internal helper to implement common parts of the exportStatsAs...
+  // functions.
+  template <class F> void exportStats(const XRayFileHeader &Header, F fn) const;
+};
+
+} // namespace xray
+} // namespace llvm
+
+#endif // LLVM_TOOLS_LLVM_XRAY_XRAY_ACCOUNT_H

tools/llvm-xray/xray-account.cc

+//===- xray-account.h - XRay Function Call Accounting ---------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements basic function call accounting from an XRay trace.
+//
+//===----------------------------------------------------------------------===//
+
+#include <algorithm>
+#include <cassert>
+#include <system_error>
+#include <utility>
+
+#include "xray-account.h"
+#include "xray-extract.h"
+#include "xray-log-reader.h"
+#include "xray-registry.h"
+#include "llvm/Support/ErrorHandling.h"
+#include "llvm/Support/FormatVariadic.h"
+
+using namespace llvm;
+using namespace llvm::xray;
+
+static cl::SubCommand Account("account", "Function call accounting");
+static cl::opt<std::string> AccountInput(cl::Positional,
+                                         cl::desc("<xray log file>"),
+                                         cl::Required, cl::sub(Account));
+static cl::opt<bool>
+    AccountKeepGoing("keep_going", cl::desc("Keep going on errors encountered"),
+                     cl::sub(Account), cl::init(false));
+static cl::alias AccountKeepGoing2("k", cl::aliasopt(AccountKeepGoing),
+                                   cl::desc("Alias for -keep_going"),
+                                   cl::sub(Account));
+static cl::opt<bool> AccountDeduceSiblingCalls(
+    "deduce-sibling-calls",
+    cl::desc("Deduce sibling calls when unrolling function call stacks"),
+    cl::sub(Account), cl::init(false));
+static cl::alias
+    AccountDeduceSiblingCalls2("d", cl::aliasopt(AccountDeduceSiblingCalls),
+                               cl::desc("Alias for -deduce_sibling_calls"),
+                               cl::sub(Account));
+static cl::opt<std::string>
+    AccountOutput("output", cl::value_desc("output file"), cl::init("-"),
+                  cl::desc("output file; use '-' for stdout"),
+                  cl::sub(Account));
+static cl::alias AccountOutput2("o", cl::aliasopt(AccountOutput),
+                                cl::desc("Alias for -output"),
+                                cl::sub(Account));
+enum class AccountOutputFormats { TEXT, CSV };
+static cl::opt<AccountOutputFormats>
+    AccountOutputFormat("format", cl::desc("output format"),
+                        cl::values(clEnumValN(AccountOutputFormats::TEXT,
+                                              "text", "report stats in text"),
+                                   clEnumValN(AccountOutputFormats::CSV, "csv",
+                                              "report stats in csv")),
+                        cl::sub(Account));
+static cl::alias AccountOutputFormat2("f", cl::desc("Alias of -format"),
+                                      cl::aliasopt(AccountOutputFormat),
+                                      cl::sub(Account));
+enum class AccountInputFormats { RAW, YAML };
+static cl::opt<AccountInputFormats> AccountInputFormat(
+    "input-format", cl::desc("input format"),
+    cl::values(clEnumValN(AccountInputFormats::RAW, "binary",
+                          "input in binary"),
+               clEnumValN(AccountInputFormats::YAML, "yaml", "input in yaml")),
+    cl::sub(Account));
+static cl::alias AccountInputFormat2("i", cl::desc("Alias for -input-format"),
+                                     cl::aliasopt(AccountInputFormat),
+                                     cl::sub(Account));
+
+enum class SortField {
+  FUNCID,
+  COUNT,
+  MIN,
+  MED,
+  PCT90,
+  PCT99,
+  MAX,
+  SUM,
+  FUNC,
+};
+static cl::opt<SortField> AccountSortOutput(
+    "sort", cl::desc("sort output by this field"), cl::value_desc("field"),
+    cl::sub(Account), cl::init(SortField::FUNCID),
+    cl::values(clEnumValN(SortField::FUNCID, "funcid", "function id"),
+               clEnumValN(SortField::COUNT, "count", "funciton call counts"),
+               clEnumValN(SortField::MIN, "min", "minimum function durations"),
+               clEnumValN(SortField::MED, "med", "median function durations"),
+               clEnumValN(SortField::PCT90, "90p", "90th percentile durations"),
+               clEnumValN(SortField::PCT99, "99p", "99th percentile durations"),
+               clEnumValN(SortField::MAX, "max", "maximum function durations"),
+               clEnumValN(SortField::SUM, "sum", "sum of call durations"),
+               clEnumValN(SortField::FUNC, "func", "function names")));
+static cl::alias AccountSortOutput2("s", cl::aliasopt(AccountSortOutput),
+                                    cl::desc("Alias for -sort"),
+                                    cl::sub(Account));
+
+enum class SortDirection {
+  ASCENDING,
+  DESCENDING,
+};
+static cl::opt<SortDirection> AccountSortOrder(
+    "sortorder", cl::desc("sort ordering"), cl::init(SortDirection::ASCENDING),
+    cl::values(clEnumValN(SortDirection::ASCENDING, "asc", "ascending"),
+               clEnumValN(SortDirection::DESCENDING, "dsc", "descending")),
+    cl::sub(Account));
+static cl::alias AccountSortOrder2("r", cl::aliasopt(AccountSortOrder),
+                                   cl::desc("Alias for -sortorder"),
+                                   cl::sub(Account));
+
+static cl::opt<int> AccountTop("top", cl::desc("only show the top N results"),
+                               cl::value_desc("N"), cl::sub(Account),
+                               cl::init(-1));
+static cl::alias AccountTop2("p", cl::desc("Alias for -top"),
+                             cl::aliasopt(AccountTop), cl::sub(Account));
+
+static cl::opt<std::string>
+    AccountInstrMap("instr_map",
+                    cl::desc("binary with the instrumentation map, or "
+                             "a separate instrumentation map"),
+                    cl::value_desc("binary with xray_instr_map"),
+                    cl::sub(Account), cl::init(""));
+static cl::alias AccountInstrMap2("m", cl::aliasopt(AccountInstrMap),
+                                  cl::desc("Alias for -instr_map"),
+                                  cl::sub(Account));
+static cl::opt<InstrumentationMapExtractor::InputFormats> InstrMapFormat(
+    "instr-map-format", cl::desc("format of instrumentation map"),
+    cl::values(clEnumValN(InstrumentationMapExtractor::InputFormats::ELF, "elf",
+                          "instrumentation map in an ELF header"),
+               clEnumValN(InstrumentationMapExtractor::InputFormats::YAML,
+                          "yaml", "instrumentation map in YAML")),
+    cl::sub(Account), cl::init(InstrumentationMapExtractor::InputFormats::ELF));
+static cl::alias InstrMapFormat2("t", cl::aliasopt(InstrMapFormat),
+                                 cl::desc("Alias for -instr-map-format"),
+                                 cl::sub(Account));
+
+namespace {
+
+template <class T, class U> void setMinMax(std::pair<T, T> &MM, U &&V) {
+  if (MM.first == 0 || MM.second == 0)
+    MM = std::make_pair(std::forward<U>(V), std::forward<U>(V));
+  else
+    MM = std::make_pair(std::min(MM.first, V), std::max(MM.second, V));
+}
+
+template <class T> T diff(T L, T R) { return std::max(L, R) - std::min(L, R); }
+
+} // namespace
+
+bool LatencyAccountant::accountRecord(const XRayRecord &Record) {
+  setMinMax(PerThreadMinMaxTSC[Record.TId], Record.TSC);
+  setMinMax(PerCPUMinMaxTSC[Record.CPU], Record.TSC);
+
+  if (CurrentMaxTSC == 0)
+    CurrentMaxTSC = Record.TSC;
+
+  if (Record.TSC < CurrentMaxTSC)
+    return false;
+
+  auto &ThreadStack = PerThreadFunctionStack[Record.TId];
+  switch (Record.Type) {
+  case RecordTypes::ENTER: {
+    // Function Enter
+    ThreadStack.push_back({Record.FuncId, Record.TSC});
+    break;
+  }
+  case RecordTypes::EXIT: {
+    // Function Exit
+    if (ThreadStack.back().first != Record.FuncId) {
+      if (!DeduceSiblingCalls)
+        return false;
+      auto Parent =
+          std::find_if(ThreadStack.rbegin(), ThreadStack.rend(),
+                       [&](const std::pair<const int32_t, uint64_t> &E) {
+                         return E.first == Record.FuncId;
+                       });
+      if (Parent != ThreadStack.rend()) {
+        // We found a matching entry for this function.
+        auto I = ThreadStack.rbegin();
+        while (I <= Parent) {
+          const auto &Top = *I;
+          recordLatency(Top.first, diff(Top.second, Record.TSC));
+          ThreadStack.pop_back();
+          I = ThreadStack.rbegin();
+        }
+        return true;
+      }
+
+      // We didn't find a matching entry for this exit
+      return false;
+    }
+
+    // We did find that the top of the function call stack matches this exit.
+    assert(ThreadStack.back().first == Record.FuncId);
+    const auto &Top = ThreadStack.back();
+    recordLatency(Top.first, diff(Top.second, Record.TSC));
+    ThreadStack.pop_back();
+    break;
+  }
+  }
+
+  return true;
+}
+
+namespace {
+
+// We consolidate the data into a struct which we can output in various forms.
+struct ResultRow {
+  uint64_t Count;
+  double Min;
+  double Median;
+  double Pct90;
+  double Pct99;
+  double Max;
+  double Sum;
+  std::string DebugInfo;
+  std::string Function;
+};
+
+ResultRow getStats(std::vector<uint64_t> &Timings) {
+  assert(!Timings.empty());
+  ResultRow R;
+  R.Sum = std::accumulate(Timings.begin(), Timings.end(), 0.0);
+  auto MinMax = std::minmax_element(Timings.begin(), Timings.end());
+  R.Min = *MinMax.first;
+  R.Max = *MinMax.second;
+  auto MedianOff = Timings.size() / 2;
+  std::nth_element(Timings.begin(), Timings.begin() + MedianOff, Timings.end());
+  R.Median = Timings[MedianOff];
+  auto Pct90Off = std::floor(Timings.size() * 0.9);
+  std::nth_element(Timings.begin(), Timings.begin() + Pct90Off, Timings.end());
+  R.Pct90 = Timings[Pct90Off];
+  auto Pct99Off = std::floor(Timings.size() * 0.99);
+  std::nth_element(Timings.begin(), Timings.begin() + Pct90Off, Timings.end());
+  R.Pct99 = Timings[Pct99Off];
+  R.Count = Timings.size();
+  return R;
+}
+
+} // namespace
+
+template <class F>
+void LatencyAccountant::exportStats(const XRayFileHeader &Header, F Fn) const {
+  using TupleType = std::tuple<int32_t, uint64_t, ResultRow>;
+  std::vector<TupleType> Results;
+  Results.reserve(FunctionLatencies.size());
+  for (auto FT : FunctionLatencies) {
+    const auto &FuncId = FT.first;
+    auto &Timings = FT.second;
+    Results.emplace_back(FuncId, Timings.size(), getStats(Timings));
+    auto &Row = std::get<2>(Results.back());
+    if (Header.CycleFrequency) {
+      double CycleFrequency = Header.CycleFrequency;
+      Row.Min /= CycleFrequency;
+      Row.Median /= CycleFrequency;
+      Row.Pct90 /= CycleFrequency;
+      Row.Pct99 /= CycleFrequency;
+      Row.Max /= CycleFrequency;
+      Row.Sum /= CycleFrequency;
+    }
+
+    Row.Function = FuncIdHelper.SymbolOrNumber(FuncId);
+    Row.DebugInfo = FuncIdHelper.FileLineAndColumn(FuncId);
+  }
+
+  switch (AccountSortOrder) {
+  case SortDirection::ASCENDING:
+    switch (AccountSortOutput) {
+    case SortField::FUNCID:
+      std::sort(Results.begin(), Results.end(),
+                [](const TupleType &L, const TupleType &R) {
+                  return std::get<0>(L) < std::get<0>(R);
+                });
+      break;
+    case SortField::COUNT:
+      std::sort(Results.begin(), Results.end(),
+                [](const TupleType &L, const TupleType &R) {
+                  return std::get<1>(L) < std::get<1>(R);
+                });
+      break;
+    case SortField::SUM:
+      std::sort(Results.begin(), Results.end(),
+                [](const TupleType &L, const TupleType &R) {
+                  return std::get<2>(L).Sum < std::get<2>(R).Sum;
+                });
+      break;
+    default:;
+      // FIXME: Not supported yet.
+    }
+    break;
+  case SortDirection::DESCENDING:
+    switch (AccountSortOutput) {
+    case SortField::FUNCID:
+      std::sort(Results.begin(), Results.end(),
+                [](const TupleType &L, const TupleType &R) {
+                  return std::get<0>(L) > std::get<0>(R);
+                });
+      break;
+    case SortField::COUNT:
+      std::sort(Results.begin(), Results.end(),
+                [](const TupleType &L, const TupleType &R) {
+                  return std::get<1>(L) > std::get<1>(R);
+                });
+      break;
+    case SortField::SUM:
+      std::sort(Results.begin(), Results.end(),
+                [](const TupleType &L, const TupleType &R) {
+                  return std::get<2>(L).Sum > std::get<2>(R).Sum;
+                });
+      break;
+    default:;
+      // FIXME: Not supported yet.
+    }
+    break;
+  }
+
+  if (AccountTop > 0) {
+    auto it = Results.begin();
+    std::advance(it, AccountTop.getValue());
+    Results.erase(it, Results.end());
+  }
+
+  for (const auto &R : Results)
+    Fn(std::get<0>(R), std::get<1>(R), std::get<2>(R));
+}
+
+void LatencyAccountant::exportStatsAsTEXT(raw_ostream &OS,
+                                          const XRayFileHeader &Header) const {
+  OS << "Functions with latencies: " << FunctionLatencies.size() << "\n";
+
+  // We spend some effort to make the text output more readable, so we do the
+  // following formatting decisions for each of the fields:
+  //
+  //   - funcid: 32-bit, but we can determine the largest number and be
+  //   between
+  //     a minimum of 5 characters, up to 9 characters, right aligned.
+  //   - count:  64-bit, but we can determine the largest number and be
+  //   between
+  //     a minimum of 5 characters, up to 9 characters, right aligned.
+  //   - min, median, 90pct, 99pct, max: double precision, but we want to keep
+  //     the values in seconds, with microsecond precision (0.000'001), so we
+  //     have at most 6 significant digits, with the whole number part to be
+  //     at
+  //     least 1 character. For readability we'll right-align, with full 9
+  //     characters each.
+  //   - debug info, function name: we format this as a concatenation of the
+  //     debug info and the function name.
+  //
+  static constexpr char StatsHeaderFormat[] =
+      "{0,+9} {1,+10} [{2,+9}, {3,+9}, {4,+9}, {5,+9}, {6,+9}] {7,+9}";
+  static constexpr char StatsFormat[] =
+      R"({0,+9} {1,+10} [{2,+9:f6}, {3,+9:f6}, {4,+9:f6}, {5,+9:f6}, {6,+9:f6}] {7,+9:f6})";
+  OS << llvm::formatv(StatsHeaderFormat, "funcid", "count", "min", "med", "90p",
+                      "99p", "max", "sum")
+     << llvm::formatv("  {0,-12}\n", "function");
+  exportStats(Header, [&](int32_t FuncId, size_t Count, const ResultRow &Row) {
+    OS << llvm::formatv(StatsFormat, FuncId, Count, Row.Min, Row.Median,
+                        Row.Pct90, Row.Pct99, Row.Max, Row.Sum)
+       << "  " << Row.DebugInfo << ": " << Row.Function << "\n";
+  });
+}
+
+void LatencyAccountant::exportStatsAsCSV(raw_ostream &OS,
+                                         const XRayFileHeader &Header) const {
+  OS << "funcid,count,min,median,90%ile,99%ile,max,sum,debug,function\n";
+  exportStats(Header, [&](int32_t FuncId, size_t Count, const ResultRow &Row) {
+    OS << FuncId << ',' << Count << ',' << Row.Min << ',' << Row.Median << ','
+       << Row.Pct90 << ',' << Row.Pct99 << ',' << Row.Max << "," << Row.Sum
+       << ",\"" << Row.DebugInfo << "\",\"" << Row.Function << "\"\n";
+  });
+}
+
+namespace llvm {
+namespace xray {
+
+static CommandRegistration Unused(&Account, []() -> Error {
+  int Fd;
+  auto EC = sys::fs::openFileForRead(AccountInput, Fd);
+  if (EC)
+    return make_error<StringError>(
+        Twine("Cannot open file '") + AccountInput + "'", EC);
+
+  Error Err = Error::success();
+  xray::InstrumentationMapExtractor Extractor(AccountInstrMap, InstrMapFormat,
+                                              Err);
+  if (auto E = handleErrors(
+          std::move(Err), [&](std::unique_ptr<StringError> E) -> Error {
+            if (E->convertToErrorCode() == std::errc::no_such_file_or_directory)
+              return Error::success();
+            return Error(std::move(E));
+          }))
+    return E;
+
+  raw_fd_ostream OS(AccountOutput, EC, sys::fs::OpenFlags::F_Text);
+  if (EC)
+    return make_error<StringError>(
+        Twine("Cannot open file '") + AccountOutput + "' for writing.", EC);
+
+  const auto &FunctionAddresses = Extractor.getFunctionAddresses();
+  symbolize::LLVMSymbolizer::Options Opts(
+      symbolize::FunctionNameKind::LinkageName, true, true, false, "");
+  symbolize::LLVMSymbolizer Symbolizer(Opts);
+  llvm::xray::FuncIdConversionHelper FuncIdHelper(AccountInstrMap, Symbolizer,
+                                                  FunctionAddresses);
+  xray::LatencyAccountant FCA(FuncIdHelper, AccountDeduceSiblingCalls);
+  const llvm::xray::XRayFileHeader *Header = nullptr;
+
+  LogReader::LoaderFunction Loader;
+  switch (AccountInputFormat) {
+  case AccountInputFormats::RAW:
+    Loader = NaiveLogLoader;
+    break;
+  case AccountInputFormats::YAML:
+    Loader = YAMLLogLoader;
+    break;
+  };
+
+  LogReader Reader(AccountInput, Err, true, Loader);
+  if (Err)
+    return joinErrors(
+        make_error<StringError>(
+            Twine("Failed loading input file '") + AccountInput + "'",
+            std::make_error_code(std::errc::protocol_error)),
+        std::move(Err));
+
+  Header = &Reader.getFileHeader();
+  for (const auto &Record : Reader) {
+    if (!FCA.accountRecord(Record)) {
+      for (const auto &ThreadStack : FCA.getPerThreadFunctionStack()) {
+        errs() << "Thread ID: " << ThreadStack.first << "\n";
+        auto Level = ThreadStack.second.size();
+        for (const auto &Entry : llvm::reverse(ThreadStack.second))
+          errs() << "#" << Level-- << "\t"
+                 << FuncIdHelper.SymbolOrNumber(Entry.first) << '\n';
+      }
+      if (!AccountKeepGoing)
+        return make_error<StringError>(
+            Twine("Failed accounting function calls in file '") + AccountInput +
+                "'.",
+            std::make_error_code(std::errc::bad_message));
+    }
+  }
+  switch (AccountOutputFormat) {
+  case AccountOutputFormats::TEXT:
+    FCA.exportStatsAsTEXT(OS, *Header);
+    break;
+  case AccountOutputFormats::CSV:
+    FCA.exportStatsAsCSV(OS, *Header);
+    break;
+  }
+  return Error::success();
+});
+
+} // namespace xray
+} // namespace llvm

tools/llvm-xray/xray-converter.h

+//===- xray-converter.h - XRay Trace Conversion ---------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Defines the TraceConverter class for turning binary traces into
+// human-readable text and vice versa.
+//
+//===----------------------------------------------------------------------===//
+#ifndef LLVM_TOOLS_LLVM_XRAY_XRAY_CONVERTER_H
+#define LLVM_TOOLS_LLVM_XRAY_XRAY_CONVERTER_H
+
+#include "func-id-helper.h"
+#include "xray-log-reader.h"
+#include "xray-record.h"
+
+namespace llvm {
+namespace xray {
+
+class TraceConverter {
+  FuncIdConversionHelper &FuncIdHelper;
+  bool Symbolize;
+
+public:
+  TraceConverter(FuncIdConversionHelper &FuncIdHelper, bool Symbolize = false)
+      : FuncIdHelper(FuncIdHelper), Symbolize(Symbolize) {}
+
+  void exportAsYAML(const LogReader &Records, raw_ostream &OS);
+  void exportAsRAWv1(const LogReader &Records, raw_ostream &OS);
+};
+
+} // namespace xray
+} // namespace llvm
+
+#endif // LLVM_TOOLS_LLVM_XRAY_XRAY_CONVERTER_H

tools/llvm-xray/xray-converter.cc

+//===- xray-converter.cc - XRay Trace Conversion --------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Implements the trace conversion functions.
+//
+//===----------------------------------------------------------------------===//
+#include "xray-converter.h"
+
+#include "xray-extract.h"
+#include "xray-record-yaml.h"
+#include "xray-registry.h"
+#include "llvm/DebugInfo/Symbolize/Symbolize.h"
+#include "llvm/Support/EndianStream.h"
+#include "llvm/Support/FileSystem.h"
+#include "llvm/Support/YAMLTraits.h"
+#include "llvm/Support/raw_ostream.h"
+#include <unistd.h>
+
+using namespace llvm;
+using namespace xray;
+
+// llvm-xray convert
+// ----------------------------------------------------------------------------
+static cl::SubCommand Convert("convert", "Trace Format Conversion");
+static cl::opt<std::string> ConvertInput(cl::Positional,
+                                         cl::desc("<xray log file>"),
+                                         cl::Required, cl::sub(Convert));
+enum class ConvertFormats { BINARY, YAML };
+static cl::opt<ConvertFormats> ConvertInputFormat(
+    "input-format", cl::desc("input format"),
+    cl::values(clEnumValN(ConvertFormats::BINARY, "raw",
+                          "input is in raw binary"),
+               clEnumValN(ConvertFormats::YAML, "yaml", "input is in yaml")),
+    cl::sub(Convert));
+static cl::alias ConvertInputFormat2("i", cl::aliasopt(ConvertInputFormat),
+                                     cl::desc("Alias for -input-format"),
+                                     cl::sub(Convert));
+static cl::opt<ConvertFormats> ConvertOutputFormat(
+    "output-format", cl::desc("output format"),
+    cl::values(clEnumValN(ConvertFormats::BINARY, "raw", "output in binary"),
+               clEnumValN(ConvertFormats::YAML, "yaml", "output in yaml")),
+    cl::sub(Convert));
+static cl::alias ConvertOutputFormat2("f", cl::aliasopt(ConvertOutputFormat),
+                                      cl::desc("Alias for -output-format"),
+                                      cl::sub(Convert));
+static cl::opt<std::string>
+    ConvertOutput("output", cl::value_desc("output file"), cl::init("-"),
+                  cl::desc("output file; use '-' for stdout"),
+                  cl::sub(Convert));
+static cl::alias ConvertOutput2("o", cl::aliasopt(ConvertOutput),
+                                cl::desc("Alias for -output"),
+                                cl::sub(Convert));
+
+static cl::opt<bool>
+    ConvertSymbolize("symbolize",
+                     cl::desc("symbolize function ids from the input log"),
+                     cl::init(false), cl::sub(Convert));
+static cl::alias ConvertSymbolize2("y", cl::aliasopt(ConvertSymbolize),
+                                   cl::desc("Alias for -symbolize"),
+                                   cl::sub(Convert));
+
+static cl::opt<std::string>
+    ConvertInstrMap("instr_map",
+                    cl::desc("binary with the instrumentation map, or "
+                             "a separate instrumentation map"),
+                    cl::value_desc("binary with xray_instr_map"),
+                    cl::sub(Convert), cl::init(""));
+static cl::alias ConvertInstrMap2("m", cl::aliasopt(ConvertInstrMap),
+                                  cl::desc("Alias for -instr_map"),
+                                  cl::sub(Convert));
+static cl::opt<bool> ConvertSortInput(
+    "sort",
+    cl::desc("determines whether to sort input log records by timestamp"),
+    cl::sub(Convert), cl::init(true));
+static cl::alias ConvertSortInput2("s", cl::aliasopt(ConvertSortInput),
+                                   cl::desc("Alias for -sort"),
+                                   cl::sub(Convert));
+static cl::opt<InstrumentationMapExtractor::InputFormats> InstrMapFormat(
+    "instr-map-format", cl::desc("format of instrumentation map"),
+    cl::values(clEnumValN(InstrumentationMapExtractor::InputFormats::ELF, "elf",
+                          "instrumentation map in an ELF header"),
+               clEnumValN(InstrumentationMapExtractor::InputFormats::YAML,
+                          "yaml", "instrumentation map in YAML")),
+    cl::sub(Convert), cl::init(InstrumentationMapExtractor::InputFormats::ELF));
+static cl::alias InstrMapFormat2("t", cl::aliasopt(InstrMapFormat),
+                                 cl::desc("Alias for -instr-map-format"),
+                                 cl::sub(Convert));
+
+using llvm::yaml::MappingTraits;
+using llvm::yaml::ScalarEnumerationTraits;
+using llvm::yaml::IO;
+using llvm::yaml::Output;
+
+void TraceConverter::exportAsYAML(const LogReader &Records, raw_ostream &OS) {
+  YAMLXRayTrace Trace;
+  const auto &FH = Records.getFileHeader();
+  Trace.Header = {FH.Version, FH.Type, FH.ConstantTSC, FH.NonstopTSC,
+                  FH.CycleFrequency};
+  Trace.Records.reserve(Records.size());
+  for (const auto &R : Records) {
+    Trace.Records.push_back({R.RecordType, R.CPU, R.Type, R.FuncId,
+                             Symbolize ? FuncIdHelper.SymbolOrNumber(R.FuncId)
+                                       : std::to_string(R.FuncId),
+                             R.TSC, R.TId});
+  }
+  Output Out(OS);
+  Out << Trace;
+}
+
+void TraceConverter::exportAsRAWv1(const LogReader &Records, raw_ostream &OS) {
+  // First write out the file header, in the correct endian-appropriate format
+  // (XRay assumes currently little endian).
+  support::endian::Writer<support::endianness::little> Writer(OS);
+  const auto &FH = Records.getFileHeader();
+  Writer.write(FH.Version);
+  Writer.write(FH.Type);
+  uint32_t Bitfield{0};
+  if (FH.ConstantTSC)
+    Bitfield |= 1uL;
+  if (FH.NonstopTSC)
+    Bitfield |= 1uL << 1;
+  Writer.write(Bitfield);
+  Writer.write(FH.CycleFrequency);
+
+  // There's 16 bytes of padding at the end of the file header.
+  static constexpr uint32_t Padding4B = 0;
+  Writer.write(Padding4B);
+  Writer.write(Padding4B);
+  Writer.write(Padding4B);
+  Writer.write(Padding4B);
+
+  // Then write out the rest of the records, still in an endian-appropriate
+  // format.
+  for (const auto &R : Records) {
+    Writer.write(R.RecordType);
+    Writer.write(R.CPU);
+    switch (R.Type) {
+    case RecordTypes::ENTER:
+      Writer.write(uint8_t{0});
+      break;
+    case RecordTypes::EXIT:
+      Writer.write(uint8_t{1});
+      break;
+    }
+    Writer.write(R.FuncId);
+    Writer.write(R.TSC);
+    Writer.write(R.TId);
+    Writer.write(Padding4B);
+    Writer.write(Padding4B);
+    Writer.write(Padding4B);
+  }
+}
+
+namespace llvm {
+namespace xray {
+
+static CommandRegistration Unused(&Convert, []() -> Error {
+  // FIXME: Support conversion to BINARY when upgrading XRay trace versions.
+  int Fd;
+  auto EC = sys::fs::openFileForRead(ConvertInput, Fd);
+  if (EC)
+    return make_error<StringError>(
+        Twine("Cannot open file '") + ConvertInput + "'", EC);
+
+  Error Err = Error::success();
+  xray::InstrumentationMapExtractor Extractor(ConvertInstrMap, InstrMapFormat,
+                                              Err);
+  handleAllErrors(std::move(Err),
+                  [&](const ErrorInfoBase &E) { E.log(errs()); });
+
+  const auto &FunctionAddresses = Extractor.getFunctionAddresses();
+  symbolize::LLVMSymbolizer::Options Opts(
+      symbolize::FunctionNameKind::LinkageName, true, true, false, "");
+  symbolize::LLVMSymbolizer Symbolizer(Opts);
+  llvm::xray::FuncIdConversionHelper FuncIdHelper(ConvertInstrMap, Symbolizer,
+                                                  FunctionAddresses);
+  llvm::xray::TraceConverter TC(FuncIdHelper, ConvertSymbolize);
+  LogReader::LoaderFunction Loader;
+  switch (ConvertInputFormat) {
+  case ConvertFormats::BINARY:
+    Loader = NaiveLogLoader;
+    break;
+  case ConvertFormats::YAML:
+    Loader = YAMLLogLoader;
+    break;
+  }
+
+  LogReader Reader(ConvertInput, Err, ConvertSortInput, Loader);
+  if (Err)
+    return joinErrors(
+        make_error<StringError>(
+            Twine("Failed loading input file '") + ConvertInput + "'.",
+            std::make_error_code(std::errc::protocol_error)),
+        std::move(Err));
+
+  raw_fd_ostream OS(ConvertOutput, EC,
+                    ConvertOutputFormat == ConvertFormats::BINARY
+                        ? sys::fs::OpenFlags::F_None
+                        : sys::fs::OpenFlags::F_Text);
+  if (EC)
+    return make_error<StringError>(
+        Twine("Cannot open file '") + ConvertOutput + "' for writing.", EC);
+
+  switch (ConvertOutputFormat) {
+  case ConvertFormats::YAML:
+    TC.exportAsYAML(Reader, OS);
+    break;
+  case ConvertFormats::BINARY:
+    TC.exportAsRAWv1(Reader, OS);
+    break;
+  }
+  return Error::success();
+});
+
+} // namespace xray
+} // namespace llvm

tools/llvm-xray/xray-extract.cc

if (Entry.Function != CurFn) {
       InstrMap[FuncId] = Entry.Function;
       FunctionIds[Entry.Function] = FuncId;
     }
   }
   OutputSleds = std::move(Sleds);
   return llvm::Error::success();
 }
 
+Error LoadYAMLInstrMap(
+    StringRef Filename, std::deque<SledEntry> &Sleds,
+    InstrumentationMapExtractor::FunctionAddressMap &InstrMap,
+    InstrumentationMapExtractor::FunctionAddressReverseMap &FunctionIds) {
+  int Fd;
+  if (auto EC = sys::fs::openFileForRead(Filename, Fd))
+    return make_error<StringError>(
+        Twine("Failed opening file '") + Filename + "' for reading.", EC);
+
+  uint64_t FileSize;
+  if (auto EC = sys::fs::file_size(Filename, FileSize))
+    return make_error<StringError>(
+        Twine("Failed getting size of file '") + Filename + "'.", EC);
+
+  std::error_code EC;
+  sys::fs::mapped_file_region MappedFile(
+      Fd, sys::fs::mapped_file_region::mapmode::readonly, FileSize, 0, EC);
+  if (EC)
+    return make_error<StringError>(
+        Twine("Failed memory-mapping file '") + Filename + "'.", EC);
+
+  std::vector<YAMLXRaySledEntry> YAMLSleds;
+  Input In(StringRef(MappedFile.data(), MappedFile.size()));
+  In >> YAMLSleds;
+  if (In.error())
+    return make_error<StringError>(
+        Twine("Failed loading YAML document from '") + Filename + "'.",
+        In.error());
+
+  for (const auto &Y : YAMLSleds) {
+    InstrMap[Y.FuncId] = Y.Function;
+    FunctionIds[Y.Function] = Y.FuncId;
+    Sleds.emplace_back(
+        SledEntry{Y.Address, Y.Function, Y.Kind, Y.AlwaysInstrument});
+  }
+  return Error::success();
+}
+
 } // namespace
 
 InstrumentationMapExtractor::InstrumentationMapExtractor(std::string Filename,
                                                          InputFormats Format,
                                                          Error &EC) {
   ErrorAsOutParameter ErrAsOutputParam(&EC);
+  if (Filename.empty()) {
+    EC = Error::success();
+    return;
+  }
   switch (Format) {
   case InputFormats::ELF: {
     EC = handleErrors(
         LoadBinaryInstrELF(Filename, Sleds, FunctionAddresses, FunctionIds),
-        [](std::unique_ptr<ErrorInfoBase> E) {
+        [&](std::unique_ptr<ErrorInfoBase> E) {
           return joinErrors(
               make_error<StringError>(
                   Twine("Cannot extract instrumentation map from '") +
-                      ExtractInput + "'.",
+                      Filename + "'.",
                   std::make_error_code(std::errc::executable_format_error)),
               std::move(E));
         });
     break;
   }
-  default:
-    llvm_unreachable("Input format type not supported yet.");
+  case InputFormats::YAML: {
+    EC = handleErrors(
+        LoadYAMLInstrMap(Filename, Sleds, FunctionAddresses, FunctionIds),
+        [&](std::unique_ptr<ErrorInfoBase> E) {
+          return joinErrors(
+              make_error<StringError>(
+                  Twine("Cannot load YAML instrumentation map from '") +
+                      Filename + "'.",
+                  std::make_error_code(std::errc::wrong_protocol_type)),
+              std::move(E));
+        });
     break;
   }
   }
+}
 
 void InstrumentationMapExtractor::exportAsYAML(raw_ostream &OS) {
   // First we translate the sleds into the YAMLXRaySledEntry objects in a deque.
   std::vector<YAMLXRaySledEntry> YAMLSleds;
   YAMLSleds.reserve(Sleds.size());
   for (const auto &Sled : Sleds) {
     YAMLSleds.push_back({FunctionIds[Sled.Function], Sled.Address,
                          Sled.Function, Sled.Kind, Sled.AlwaysInstrument});

tools/llvm-xray/xray-graph.h

+//===-- xray-graph.h - XRay Function Call Graph Renderer --------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Generate a DOT file to represent the function call graph encountered in
+// the trace.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef XRAY_GRAPH_H
+#define XRAY_GRAPH_H
+
+#include <unordered_map>
+#include <vector>
+
+#include "func-id-helper.h"
+#include "xray-record.h"
+#include "llvm/Support/raw_ostream.h"
+
+namespace llvm {
+namespace xray {
+/// A class encapsulating the logic related to analyzing XRay traces, producting
+/// Graphs from them and then exporting those graphs for review.
+class GraphRenderer {
+  /// An inner struct for storing edge attributes for our graph. Here the
+  /// attributes are mainly function call statistics.
+  ///
+  /// FIXME: expand to contain more information eg call latencies.
+  struct EdgeAttribute {
+    uint64_t CallCount = 0;
+  };
+
+  /// The Graph stored in an edge-list like format, with the edges also having
+  /// An attached set of attributes.
+  std::unordered_map<int32_t, std::unordered_map<int32_t, EdgeAttribute>> Graph;
+
+  /// An Inner Struct for storing vertex attributes, at the moment just
+  /// SymbolNames, however in future we could store bulk function statistics.
+  ///
+  /// FIXME: Store more attributes based on instrumentation map.
+  struct VertexAttribute {
+    std::string SymbolName;
+  };
+
+  /// Graph Vertex Attributes. These are presently stored seperate from the
+  /// main graph.
+  std::unordered_map<int32_t, VertexAttribute> VertexAttrs;
+
+  /// Use a Map to store the Function stack for each thread whilst building the
+  /// graph.
+  ///
+  /// FIXME: Perhaps we can Build this into LatencyAccountant? or vise versa?
+  std::unordered_map<pid_t, std::vector<int32_t>> PerThreadFunctionStack;
+
+  /// Usefull object for getting human readable Symbol Names.
+  FuncIdConversionHelper &FuncIdHelper;
+
+public:
+  /// Takes in a reference to a FuncIdHelper in order to have ready access to
+  /// Symbol names.
+  explicit GraphRenderer(FuncIdConversionHelper &FuncIdHelper)
+      : FuncIdHelper(FuncIdHelper){}
+
+  /// Process an Xray record and expand the graph.
+  ///
+  /// This Function will return true on success, or false if records are not
+  /// presented in per-thread call-tree DFS order. (That is for each thread the
+  /// Records should be in order runtime on an ideal system.)
+  ///
+  /// FIXME: Make this more robust against small irregularities.
+  bool accountRecord(const XRayRecord &Record);
+
+  /// Output the Embedded graph in DOT format on \p OS.
+  void exportGraphAsDOT(raw_ostream &OS) const;
+};
+}
+}
+
+#endif // XRAY_GRAPH_H

tools/llvm-xray/xray-graph.cc

+//===-- xray-graph.c - XRay Function Call Graph Renderer ------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Generate a DOT file to represent the function call graph encountered in
+// the trace.
+//
+//===----------------------------------------------------------------------===//
+#include <algorithm>
+#include <cassert>
+#include <system_error>
+#include <utility>
+
+#include "xray-extract.h"
+#include "xray-graph.h"
+#include "xray-log-reader.h"
+#include "xray-registry.h"
+#include "llvm/Support/ErrorHandling.h"
+#include "llvm/Support/FormatVariadic.h"
+
+using namespace llvm;
+using namespace xray;
+
+// Setup llvm-xray graph subcommand and its options.
+static cl::SubCommand Graph("graph", "Generate function-call graph");
+static cl::opt<std::string> GraphInput(cl::Positional,
+                                       cl::desc("<xray log file>"),
+                                       cl::Required, cl::sub(Graph));
+
+enum class GraphInputFormats { RAW, YAML };
+static cl::opt<GraphInputFormats> GraphInputFormat(
+    "input-format", cl::desc("input format"),
+    cl::values(clEnumValN(GraphInputFormats::RAW, "binary", "input in binary"),
+               clEnumValN(GraphInputFormats::YAML, "yaml", "input in yaml")),
+    cl::sub(Graph));
+static cl::alias GraphInputFormat2("i", cl::desc("Alias for -input-format"),
+                                   cl::aliasopt(GraphInputFormat),
+                                   cl::sub(Graph));
+
+static cl::opt<std::string>
+    GraphOutput("output", cl::value_desc("Output file"), cl::init("-"),
+                cl::desc("output file; use '-' for stdout"), cl::sub(Graph));
+static cl::alias GraphOutput2("o", cl::aliasopt(GraphOutput),
+                              cl::desc("Alias for -output"), cl::sub(Graph));
+
+static cl::opt<std::string> GraphInstrMap(
+    "instr_map", cl::desc("binary with the instrumrntation map, or "
+                          "a separate instrumentation map"),
+    cl::value_desc("binary with xray_instr_map"), cl::sub(Graph), cl::init(""));
+static cl::alias GraphInstrMap2("m", cl::aliasopt(GraphInstrMap),
+                                cl::desc("alias for -instr_map"),
+                                cl::sub(Graph));
+
+static cl::opt<InstrumentationMapExtractor::InputFormats> InstrMapFormat(
+    "instr-map-format", cl::desc("format of instrumentation map"),
+    cl::values(clEnumValN(InstrumentationMapExtractor::InputFormats::ELF, "elf",
+                          "instrumentation map in an ELF header"),
+               clEnumValN(InstrumentationMapExtractor::InputFormats::YAML,
+                          "yaml", "instrumentation map in YAML")),
+    cl::sub(Graph), cl::init(InstrumentationMapExtractor::InputFormats::ELF));
+static cl::alias InstrMapFormat2("t", cl::aliasopt(InstrMapFormat),
+                                 cl::desc("Alias for -instr-map-format"),
+                                 cl::sub(Graph));
+
+// Evaluates an XRay record and performs accounting on it, creating and
+// decorating a function call graph as it does so. It does this by maintaining
+// a call stack on a per-thread basis and adding edges and verticies to the
+// graph as they are seen for the first time.
+//
+// There is an immaginary root for functions at the top of their stack with
+// FuncId 0.
+//
+// FIXME: make more robust to errors and
+// Decorate Graph More Heavily.
+bool GraphRenderer::accountRecord(const XRayRecord &Record) {
+  auto &ThreadStack = PerThreadFunctionStack[Record.TId];
+  switch (Record.Type) {
+  case RecordTypes::ENTER: {
+    ++ Graph[(ThreadStack.empty() ? 0 : ThreadStack.back())]
+               [Record.FuncId].CallCount;
+    if (VertexAttrs.count(Record.FuncId) == 0)
+      VertexAttrs[Record.FuncId] = {FuncIdHelper.SymbolOrNumber(Record.FuncId)};
+
+    ThreadStack.push_back(Record.FuncId);
+    break;
+  }
+  case RecordTypes::EXIT: {
+    if (ThreadStack.size() == 0 || ThreadStack.back() != Record.FuncId)
+      return false;
+
+    ThreadStack.pop_back();
+    break;
+  }
+  }
+
+  return true;
+}
+
+// Does what the name suggests, it creates a DOT file from the Graph embedded in
+// the GraphRenderer object. It does this in the expected way by itterating
+// through all edges then vertices and then outputting them and their
+// annotations.
+//
+// FIXME: output more information, better presented.
+void GraphRenderer::exportGraphAsDOT(raw_ostream &OS) const {
+  OS << "digraph xray {\n";
+
+  for (const auto &V : Graph)
+    for (const auto &E : V.second)
+      OS << "F" << V.first << " -> "
+         << "F" << E.first << " label=\"" << E.second.CallCount << "\"];\n";
+
+  for (const auto &V : VertexAttrs)
+    OS << "F" << V.first << " [label=\""
+       << (V.second.SymbolName.size() > 40
+               ? V.second.SymbolName.substr(0, 40) + "..."
+               : V.second.SymbolName)
+       << "\"];\n";
+
+  OS << "}\n";
+}
+
+// Here we register and implement the llvm-xray graph subcommand.
+// The bulk of this code reads in the options, opens the required files, uses
+// those files to create a context for analysing the xray trace, then there is a
+// short loop which actually analyses the trace, generates the graph and then
+// outputs it as a DOT.
+//
+// FIXME: include additional filtering and annalysis passes to provide more
+// specific useful information.
+static CommandRegistration Unused(&Graph, []() -> Error {
+  int Fd;
+  auto EC = sys::fs::openFileForRead(GraphInput, Fd);
+  if (EC)
+    return make_error<StringError>(
+        Twine("Cannot open file '") + GraphInput + "'", EC);
+
+  Error Err = Error::success();
+  xray::InstrumentationMapExtractor Extractor(GraphInstrMap, InstrMapFormat,
+                                              Err);
+  if (auto E = handleErrors(
+          std::move(Err), [&](std::unique_ptr<StringError> E) -> Error {
+            if (E->convertToErrorCode() == std::errc::no_such_file_or_directory)
+              return Error::success();
+            return Error(std::move(E));
+          }))
+    return E;
+
+  raw_fd_ostream OS(GraphOutput, EC, sys::fs::OpenFlags::F_Text);
+  if (EC)
+    return make_error<StringError>(
+        Twine("Cannot open file '") + GraphOutput + "' for writing.", EC);
+
+  const auto &FunctionAddresses = Extractor.getFunctionAddresses();
+  symbolize::LLVMSymbolizer::Options Opts(
+      symbolize::FunctionNameKind::LinkageName, true, true, false, "");
+  symbolize::LLVMSymbolizer Symbolizer(Opts);
+  llvm::xray::FuncIdConversionHelper FuncIdHelper(GraphInstrMap, Symbolizer,
+                                                  FunctionAddresses);
+  xray::GraphRenderer GR(FuncIdHelper);
+
+  LogReader::LoaderFunction Loader;
+  switch (GraphInputFormat) {
+  case GraphInputFormats::RAW:
+    Loader = NaiveLogLoader;
+    break;
+  case GraphInputFormats::YAML:
+    Loader = YAMLLogLoader;
+    break;
+  };
+
+  LogReader Reader(GraphInput, Err, true, Loader);
+  if (Err)
+    return joinErrors(
+        make_error<StringError>(
+            Twine("Failed loading input file '") + GraphInput + "'",
+            std::make_error_code(std::errc::protocol_error)),
+        std::move(Err));
+
+  for (const auto &Record : Reader) {
+    // Generate graph, FIXME: better error recovery.
+    if (!GR.accountRecord(Record)) {
+      return make_error<StringError>(
+          Twine("Failed accounting function calls in file '") + GraphInput +
+              "'.",
+          std::make_error_code(std::errc::bad_message));
+    }
+  }
+
+  GR.exportGraphAsDOT(OS);
+  return Error::success();
+});

tools/llvm-xray/xray-log-reader.h

+//===- xray-log-reader.h - XRay Log Reader Interface ----------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Define the interface for an XRay log reader. Currently we only support one
+// version of the log (naive log) with fixed-sized records.
+//
+//===----------------------------------------------------------------------===//
+#ifndef LLVM_TOOLS_LLVM_XRAY_XRAY_LOG_READER_H
+#define LLVM_TOOLS_LLVM_XRAY_XRAY_LOG_READER_H
+
+#include <cstdint>
+#include <deque>
+#include <vector>
+
+#include "xray-record-yaml.h"
+#include "xray-record.h"
+#include "llvm/Support/Error.h"
+#include "llvm/Support/FileSystem.h"
+
+namespace llvm {
+namespace xray {
+
+class LogReader {
+  XRayFileHeader FileHeader;
+  std::vector<XRayRecord> Records;
+
+  typedef std::vector<XRayRecord>::const_iterator citerator;
+
+public:
+  typedef std::function<Error(StringRef, XRayFileHeader &,
+                              std::vector<XRayRecord> &)>
+      LoaderFunction;
+
+  LogReader(StringRef Filename, Error &Err, bool Sort, LoaderFunction Loader);
+
+  const XRayFileHeader &getFileHeader() const { return FileHeader; }
+
+  citerator begin() const { return Records.begin(); }
+  citerator end() const { return Records.end(); }
+  size_t size() const { return Records.size(); }
+};
+
+Error NaiveLogLoader(StringRef Data, XRayFileHeader &FileHeader,
+                     std::vector<XRayRecord> &Records);
+Error YAMLLogLoader(StringRef Data, XRayFileHeader &FileHeader,
+                    std::vector<XRayRecord> &Records);
+
+} // namespace xray
+} // namespace llvm
+
+#endif // LLVM_TOOLS_LLVM_XRAY_XRAY_LOG_READER_H

tools/llvm-xray/xray-log-reader.cc

+//===- xray-log-reader.cc - XRay Log Reader Implementation ----------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// XRay log reader implementation.
+//
+//===----------------------------------------------------------------------===//
+#include <sys/types.h>
+
+#include "xray-log-reader.h"
+#include "xray-record-yaml.h"
+#include "llvm/Support/DataExtractor.h"
+#include "llvm/Support/FileSystem.h"
+
+using namespace llvm;
+using namespace llvm::xray;
+using llvm::yaml::Input;
+
+LogReader::LogReader(
+    StringRef Filename, Error &Err, bool Sort,
+    std::function<Error(StringRef, XRayFileHeader &, std::vector<XRayRecord> &)>
+        Loader) {
+  ErrorAsOutParameter Guard(&Err);
+  int Fd;
+  if (auto EC = sys::fs::openFileForRead(Filename, Fd)) {
+    Err = make_error<StringError>(
+        Twine("Cannot read log from '") + Filename + "'", EC);
+    return;
+  }
+  uint64_t FileSize;
+  if (auto EC = sys::fs::file_size(Filename, FileSize)) {
+    Err = make_error<StringError>(
+        Twine("Cannot read log from '") + Filename + "'", EC);
+    return;
+  }
+
+  std::error_code EC;
+  sys::fs::mapped_file_region MappedFile(
+      Fd, sys::fs::mapped_file_region::mapmode::readonly, FileSize, 0, EC);
+  if (EC) {
+    Err = make_error<StringError>(
+        Twine("Cannot read log from '") + Filename + "'", EC);
+    return;
+  }
+
+  if (auto E = Loader(StringRef(MappedFile.data(), MappedFile.size()),
+                      FileHeader, Records)) {
+    Err = std::move(E);
+    return;
+  }
+
+  if (Sort)
+    std::sort(
+        Records.begin(), Records.end(),
+        [](const XRayRecord &L, const XRayRecord &R) { return L.TSC < R.TSC; });
+}
+
+Error llvm::xray::NaiveLogLoader(StringRef Data, XRayFileHeader &FileHeader,
+                                 std::vector<XRayRecord> &Records) {
+  // FIXME: Maybe deduce whether the data is little or big-endian using some
+  // magic bytes in the beginning of the file?
+
+  // First 32 bytes of the file will always be the header. We assume a certain
+  // format here:
+  //
+  //   (2)   uint16 : version
+  //   (2)   uint16 : type
+  //   (4)   uint32 : bitfield
+  //   (8)   uint64 : cycle frequency
+  //   (16)  -      : padding
+  //
+  if (Data.size() < 32)
+    return make_error<StringError>(
+        "Not enough bytes for an XRay log.",
+        std::make_error_code(std::errc::invalid_argument));
+
+  if (Data.size() - 32 == 0 || Data.size() % 32 != 0)
+    return make_error<StringError>(
+        "Invalid-sized XRay data.",
+        std::make_error_code(std::errc::invalid_argument));
+
+  DataExtractor HeaderExtractor(Data, true, 8);
+  uint32_t OffsetPtr = 0;
+  FileHeader.Version = HeaderExtractor.getU16(&OffsetPtr);
+  FileHeader.Type = HeaderExtractor.getU16(&OffsetPtr);
+  uint32_t Bitfield = HeaderExtractor.getU32(&OffsetPtr);
+  FileHeader.ConstantTSC = Bitfield & 1uL;
+  FileHeader.NonstopTSC = Bitfield & 1uL << 1;
+  FileHeader.CycleFrequency = HeaderExtractor.getU64(&OffsetPtr);
+
+  if (FileHeader.Version != 1)
+    return make_error<StringError>(
+        Twine("Unsupported XRay file version: ") + Twine(FileHeader.Version),
+        std::make_error_code(std::errc::invalid_argument));
+
+  // Each record after the header will be 32 bytes, in the following format:
+  //
+  //   (2)   uint16 : record type
+  //   (1)   uint8  : cpu id
+  //   (1)   uint8  : type
+  //   (4)   sint32 : function id
+  //   (8)   uint64 : tsc
+  //   (4)   uint32 : thread id
+  //   (12)  -      : padding
+  for (auto S = Data.drop_front(32); !S.empty(); S = S.drop_front(32)) {
+    DataExtractor RecordExtractor(S, true, 8);
+    uint32_t OffsetPtr = 0;
+    Records.emplace_back();
+    auto &Record = Records.back();
+    Record.RecordType = RecordExtractor.getU16(&OffsetPtr);
+    Record.CPU = RecordExtractor.getU8(&OffsetPtr);
+    auto Type = RecordExtractor.getU8(&OffsetPtr);
+    switch (Type) {
+    case 0:
+      Record.Type = RecordTypes::ENTER;
+      break;
+    case 1:
+      Record.Type = RecordTypes::EXIT;
+      break;
+    default:
+      return make_error<StringError>(
+          Twine("Unknown record type '") + Twine(int{Type}) + "'",
+          std::make_error_code(std::errc::protocol_error));
+    }
+    Record.FuncId = RecordExtractor.getSigned(&OffsetPtr, sizeof(int32_t));
+    Record.TSC = RecordExtractor.getU64(&OffsetPtr);
+    Record.TId = RecordExtractor.getU32(&OffsetPtr);
+  }
+  return Error::success();
+}
+
+Error llvm::xray::YAMLLogLoader(StringRef Data, XRayFileHeader &FileHeader,
+                                std::vector<XRayRecord> &Records) {
+
+  // Load the documents from the MappedFile.
+  YAMLXRayTrace Trace;
+  Input In(Data);
+  In >> Trace;
+  if (In.error())
+    return make_error<StringError>("Failed loading YAML Data.", In.error());
+
+  FileHeader.Version = Trace.Header.Version;
+  FileHeader.Type = Trace.Header.Type;
+  FileHeader.ConstantTSC = Trace.Header.ConstantTSC;
+  FileHeader.NonstopTSC = Trace.Header.NonstopTSC;
+  FileHeader.CycleFrequency = Trace.Header.CycleFrequency;
+
+  if (FileHeader.Version != 1)
+    return make_error<StringError>(
+        Twine("Unsupported XRay file version: ") + Twine(FileHeader.Version),
+        std::make_error_code(std::errc::invalid_argument));
+
+  std::vector<XRayRecord> Tmp;
+  Tmp.reserve(Trace.Records.size());
+  std::transform(Trace.Records.begin(), Trace.Records.end(),
+                 std::back_inserter(Tmp), [&](const YAMLXRayRecord &R) {
+                   return XRayRecord{R.RecordType, R.CPU, R.Type,
+                                     R.FuncId,     R.TSC, R.TId};
+                 });
+  Records = std::move(Tmp);
+  return Error::success();
+}

tools/llvm-xray/xray-record-yaml.h

+//===- xray-record-yaml.h - XRay Record YAML Support Definitions ----------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Types and traits specialisations for YAML I/O of XRay log entries.
+//
+//===----------------------------------------------------------------------===//
+#ifndef LLVM_TOOLS_LLVM_XRAY_XRAY_RECORD_YAML_H
+#define LLVM_TOOLS_LLVM_XRAY_XRAY_RECORD_YAML_H
+
+#include <type_traits>
+
+#include "xray-record.h"
+#include "llvm/Support/YAMLTraits.h"
+
+namespace llvm {
+namespace xray {
+
+struct YAMLXRayFileHeader {
+  uint16_t Version;
+  uint16_t Type;
+  bool ConstantTSC;
+  bool NonstopTSC;
+  uint64_t CycleFrequency;
+};
+
+struct YAMLXRayRecord {
+  uint16_t RecordType;
+  uint8_t CPU;
+  RecordTypes Type;
+  int32_t FuncId;
+  std::string Function;
+  uint64_t TSC;
+  uint32_t TId;
+};
+
+struct YAMLXRayTrace {
+  YAMLXRayFileHeader Header;
+  std::vector<YAMLXRayRecord> Records;
+};
+
+using XRayRecordStorage =
+    std::aligned_storage<sizeof(XRayRecord), alignof(XRayRecord)>::type;
+
+} // namespace xray
+
+namespace yaml {
+
+// YAML Traits
+// -----------
+template <> struct ScalarEnumerationTraits<xray::RecordTypes> {
+  static void enumeration(IO &IO, xray::RecordTypes &Type) {
+    IO.enumCase(Type, "function-enter", xray::RecordTypes::ENTER);
+    IO.enumCase(Type, "function-exit", xray::RecordTypes::EXIT);
+  }
+};
+
+template <> struct MappingTraits<xray::YAMLXRayFileHeader> {
+  static void mapping(IO &IO, xray::YAMLXRayFileHeader &Header) {
+    IO.mapRequired("version", Header.Version);
+    IO.mapRequired("type", Header.Type);
+    IO.mapRequired("constant-tsc", Header.ConstantTSC);
+    IO.mapRequired("nonstop-tsc", Header.NonstopTSC);
+    IO.mapRequired("cycle-frequency", Header.CycleFrequency);
+  }
+};
+
+template <> struct MappingTraits<xray::YAMLXRayRecord> {
+  static void mapping(IO &IO, xray::YAMLXRayRecord &Record) {
+    // FIXME: Make this type actually be descriptive
+    IO.mapRequired("type", Record.RecordType);
+    IO.mapRequired("func-id", Record.FuncId);
+    IO.mapOptional("function", Record.Function);
+    IO.mapRequired("cpu", Record.CPU);
+    IO.mapRequired("thread", Record.TId);
+    IO.mapRequired("kind", Record.Type);
+    IO.mapRequired("tsc", Record.TSC);
+  }
+
+  static constexpr bool flow = true;
+};
+
+template <> struct MappingTraits<xray::YAMLXRayTrace> {
+  static void mapping(IO &IO, xray::YAMLXRayTrace &Trace) {
+    // A trace file contains two parts, the header and the list of all the
+    // trace records.
+    IO.mapRequired("header", Trace.Header);
+    IO.mapRequired("records", Trace.Records);
+  }
+};
+
+} // namespace yaml
+} // namespace llvm
+
+LLVM_YAML_IS_SEQUENCE_VECTOR(xray::YAMLXRayRecord) 
+
+#endif // LLVM_TOOLS_LLVM_XRAY_XRAY_RECORD_YAML_H

tools/llvm-xray/xray-record.h

+//===- xray-record.h - XRay Trace Record ----------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file replicates the record definition for XRay log entries. This should
+// follow the evolution of the log record versions supported in the compiler-rt
+// xray project.
+//
+//===----------------------------------------------------------------------===//
+#ifndef LLVM_TOOLS_LLVM_XRAY_XRAY_RECORD_H
+#define LLVM_TOOLS_LLVM_XRAY_XRAY_RECORD_H
+
+#include <cstdint>
+
+namespace llvm {
+namespace xray {
+
+struct XRayFileHeader {
+  uint16_t Version = 0;
+  uint16_t Type = 0;
+  bool ConstantTSC;
+  bool NonstopTSC;
+  uint64_t CycleFrequency = 0;
+};
+
+enum class RecordTypes { ENTER, EXIT };
+
+struct XRayRecord {
+  uint16_t RecordType;
+
+  // The CPU where the thread is running. We assume number of CPUs <= 256.
+  uint8_t CPU;
+
+  // Identifies the type of record.
+  RecordTypes Type;
+
+  // The function ID for the record.
+  int32_t FuncId;
+
+  // Get the full 8 bytes of the TSC when we get the log record.
+  uint64_t TSC;
+
+  // The thread ID for the currently running thread.
+  uint32_t TId;
+};
+
+} // namespace xray
+} // namespace llvm
+
+#endif // LLVM_TOOLS_LLVM_XRAY_XRAY_RECORD_H