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.

[dblaikie]

tools/llvm-xray/xray-graph.cc

84–88 ↗

(On Diff #79681)

could potentially use a conditional operator inside the [] since the expression is otherwise identical.

Also, the outer () aren't necessary - but you can keep them if you find they enhance readability.

89–91 ↗

(On Diff #79681)

Consider dropping {} on single line blocks.

116–120 ↗

(On Diff #79681)

Inconsistent bracing (why does the inner loop have braces but the outer loop doesn't? - personally I'd probably drop them from both, but I could see an argument for adding them to both - just doesn't seem right to add them only to one and not the other)

120 ↗

(On Diff #79681)

Extra semicolon

128 ↗

(On Diff #79681)

Extra semi

132–133 ↗

(On Diff #79681)

Drop these (it's just a static variable in this scope anyway)

174–183 ↗

(On Diff #79681)

Should be some common utility for this, so every tool doesn't have to go through the same hoops (probably coalesce all the instrumentation map extractor stuff as well)

tools/llvm-xray/xray-graph.h

30 ↗

(On Diff #79681)

No need for the explicit 'private' as it's implied/the default here.

41 ↗

(On Diff #79681)

(Consider LLVM's data structures - can be more memory efficient than the allocation-per-node of standard containers.

Also a map of maps might be more efficient as a map of pair -> value, if it's equivalent for your use case)

59 ↗

(On Diff #79681)

(similarly, consider other data structures - but also maybe consider multimap rather than map to vector)

68 ↗

(On Diff #79681)

Extra semicolon

[varno]

• Initial work on the XRay Graph tool.
• Responses to Phabricator comments

[varno]

Remove spurious files by basing patch on D24377

[dberris]

tools/llvm-xray/CMakeLists.txt

16 ↗

(On Diff #80007)

nit: we try to somewhat keep this in lexicographical order.

tools/llvm-xray/xray-graph.cc

174–183 ↗

(On Diff #79681)

+1 -- if you rebase again to the latest of D24377 you can use the utility function that determines the supported loader function here.

tools/llvm-xray/xray-graph.h

41 ↗

(On Diff #79681)

http://llvm.org/docs/ProgrammersManual.html is a good resource to look up available data structures -- for instance, for map-like containers:

http://llvm.org/docs/ProgrammersManual.html#map-like-containers-std-map-densemap-etc

You have a few choices you can work with.

[varno]

tools/llvm-xray/xray-graph.cc

174–183 ↗

(On Diff #79681)

Yeah there probably should be. Not yet though AFAIK.

tools/llvm-xray/xray-graph.h

41 ↗

(On Diff #79681)

Thinking more on this before I make changes.

59 ↗

(On Diff #79681)

Thinking on this more before I make changes.

[varno]

I am planning changes

[varno]

• Additional Changes in response to dblaikie's comments
• Rebase to current version of D24377 and use getSupportedLoader

[varno]

I have addressed the last open comments.

[dberris]

Cool -- now let's see some tests for this, to make sure that we don't regress it when it goes in. You can find examples of tests in the test/tools/llvm-xray/ directory.

[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

121 ↗

(On Diff #80535)

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

155–156 ↗

(On Diff #80535)

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

tools/llvm-xray/xray-graph.h

27–28 ↗

(On Diff #80535)

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

75 ↗

(On Diff #80535)

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

115–124 ↗

(On Diff #80535)

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?

126–127 ↗

(On Diff #80535)

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

121 ↗

(On Diff #80535)

No.

tools/llvm-xray/xray-graph.h

115–124 ↗

(On Diff #80535)

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).

126–127 ↗

(On Diff #80535)

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

174–175 ↗

(On Diff #80538)

Empty line between these two lines?

187–196 ↗

(On Diff #80538)

The indentation here is a little weird. Fix?

tools/llvm-xray/xray-graph.h

115–124 ↗

(On Diff #80535)

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

126–127 ↗

(On Diff #80535)

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

115–124 ↗

(On Diff #80535)

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

229–230 ↗

(On Diff #80539)

Missing empty line between these two.

344–347 ↗

(On Diff #80539)

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

115–124 ↗

(On Diff #80535)

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

115–124 ↗

(On Diff #80535)

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

[dberris]

tools/llvm-xray/xray-graph.h

43–44 ↗

(On Diff #80541)

Missing empty line between these two.

74–75 ↗

(On Diff #80541)

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

102 ↗

(On Diff #80541)

Potentially spurious empty line here.

117 ↗

(On Diff #80541)

Also potentially spurious empty line here.

142–148 ↗

(On Diff #80541)

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

150 ↗

(On Diff #80541)

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.

204–205 ↗

(On Diff #80541)

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

214 ↗

(On Diff #80541)

No need for void in the function arguments.

215 ↗

(On Diff #80541)

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

221 ↗

(On Diff #80541)

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

221–228 ↗

(On Diff #80541)

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

88 ↗

(On Diff #80541)

Why are the iterators not the same type?

92 ↗

(On Diff #80541)

No need for void in the function arguments.

[varno]

• Comments

[varno]

tools/llvm-xray/xray-graph.cc

221–228 ↗

(On Diff #80541)

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

221–228 ↗

(On Diff #80541)

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

211–212 ↗

(On Diff #80696)

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

222 ↗

(On Diff #80696)

Remove dead code

287–288 ↗

(On Diff #80696)

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.

340–341 ↗

(On Diff #80696)

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)

358 ↗

(On Diff #80696)

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

211–212 ↗

(On Diff #80696)

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

15 ↗

(On Diff #80696)

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

211–212 ↗

(On Diff #80696)

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.

340–341 ↗

(On Diff #80696)

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.

358 ↗

(On Diff #80696)

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).

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

+#RUN: llvm-xray graph %s -o - -m %S/Inputs/simple-instrmap.yaml -t yaml -d \
+#RUN:    | FileCheck %s -check-prefix=COUNT
+#RUN: llvm-xray graph %s -o - -m %S/Inputs/simple-instrmap.yaml -t yaml -d -e count \
+#RUN:    | FileCheck %s -check-prefix=COUNT
+#
+#RUN: llvm-xray graph %s -o - -m %S/Inputs/simple-instrmap.yaml -t yaml -d -e min \
+#RUN:    | FileCheck %s -check-prefix=TIME
+#RUN: llvm-xray graph %s -o - -m %S/Inputs/simple-instrmap.yaml -t yaml -d -e med \
+#RUN:    | FileCheck %s -check-prefix=TIME
+#RUN: llvm-xray graph %s -o - -m %S/Inputs/simple-instrmap.yaml -t yaml -d -e 90p \
+#RUN:    | FileCheck %s -check-prefix=TIME
+#RUN: llvm-xray graph %s -o - -m %S/Inputs/simple-instrmap.yaml -t yaml -d -e 99p \
+#RUN:    | FileCheck %s -check-prefix=TIME
+#RUN: llvm-xray graph %s -o - -m %S/Inputs/simple-instrmap.yaml -t yaml -d -e max \
+#RUN:    | FileCheck %s -check-prefix=TIME
+#RUN: llvm-xray graph %s -o - -m %S/Inputs/simple-instrmap.yaml -t yaml -d -e sum \
+#RUN:    | FileCheck %s -check-prefix=TIME
+#
+---
+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 }
+...
+
+#EMPTY:       digraph xray {
+#EMPTY-DAG:   F0 -> F1 [label=""];
+#EMPTY-DAG:   F1 -> F2 [label=""];
+#EMPTY-DAG:   F2 -> F3 [label=""];
+#EMPTY-DAG:   F1 [label="@(1)"];
+#EMPTY-DAG:   F2 [label="@(2)"];
+#EMPTY-DAG:   F3 [label="@(3)"];
+#EMPTY-NEXT:       }
+
+#COUNT:       digraph xray {
+#COUNT-DAG:   F0 -> F1 [label="1"];
+#COUNT-DAG:   F1 -> F2 [label="1"];
+#COUNT-DAG:   F2 -> F3 [label="1"];
+#COUNT-DAG:   F1 [label="@(1)"];
+#COUNT-DAG:   F2 [label="@(2)"];
+#COUNT-DAG:   F3 [label="@(3)"];
+#COUNT-NEXT:       }
+
+
+#TIME:       digraph xray {
+#TIME-DAG:   F0 -> F1 [label="4.{{.*}}"];
+#TIME-DAG:   F1 -> F2 [label="3.{{.*}}"];
+#TIME-DAG:   F2 -> F3 [label="1.{{.*}}"];
+#TIME-DAG:   F1 [label="@(1)"];
+#TIME-DAG:   F2 [label="@(2)"];
+#TIME-DAG:   F3 [label="@(3)"];
+#TIME-NEXT:       }

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

+#RUN: llvm-xray graph %s -o - -m %S/Inputs/simple-instrmap.yaml -t yaml \
+#RUN:    | FileCheck %s -check-prefix=COUNT
+#RUN: llvm-xray graph %s -o - -m %S/Inputs/simple-instrmap.yaml -t yaml -e count \
+#RUN:    | FileCheck %s -check-prefix=COUNT
+#
+#RUN: llvm-xray graph %s -o - -m %S/Inputs/simple-instrmap.yaml -t yaml -e min \
+#RUN:    | FileCheck %s -check-prefix=TIME
+#RUN: llvm-xray graph %s -o - -m %S/Inputs/simple-instrmap.yaml -t yaml -e med \
+#RUN:    | FileCheck %s -check-prefix=TIME
+#RUN: llvm-xray graph %s -o - -m %S/Inputs/simple-instrmap.yaml -t yaml -e 90p \
+#RUN:    | FileCheck %s -check-prefix=TIME
+#RUN: llvm-xray graph %s -o - -m %S/Inputs/simple-instrmap.yaml -t yaml -e 99p \
+#RUN:    | FileCheck %s -check-prefix=TIME
+#RUN: llvm-xray graph %s -o - -m %S/Inputs/simple-instrmap.yaml -t yaml -e max \
+#RUN:    | FileCheck %s -check-prefix=TIME
+#RUN: llvm-xray graph %s -o - -m %S/Inputs/simple-instrmap.yaml -t yaml -e sum \
+#RUN:    | FileCheck %s -check-prefix=TIME
+---
+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 }
+...
+
+
+#EMPTY:   digraph xray {
+#EMPTY-NEXT:   F0 -> F1 [label=""];
+#EMPTY-NEXT:   F1 [label="@(1)"];
+#EMPTY-NEXT:   }
+
+#COUNT:   digraph xray {
+#COUNT-NEXT:   F0 -> F1 [label="1"];
+#COUNT-NEXT:   F1 [label="@(1)"];
+#COUNT-NEXT:   }
+
+#TIME:   digraph xray {
+#TIME-NEXT:   F0 -> F1 [label="3.8{{.*}}e-08"];
+#TIME-NEXT:   F1 [label="@(1)"];
+#TIME-NEXT:   }

llvm/trunk/tools/llvm-xray/CMakeLists.txt

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

llvm/trunk/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 <vector>
+
+#include "func-id-helper.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/Support/raw_ostream.h"
+#include "llvm/XRay/Trace.h"
+#include "llvm/XRay/XRayRecord.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 {
+public:
+  /// An inner struct for common timing statistics information
+  struct TimeStat {
+    uint64_t Count;
+    double Min;
+    double Median;
+    double Pct90;
+    double Pct99;
+    double Max;
+    double Sum;
+  };
+
+  /// 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 {
+    TimeStat S;
+    std::vector<uint64_t> Timings;
+  };
+
+  /// 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;
+    TimeStat S;
+  };
+
+private:
+  /// The Graph stored in an edge-list like format, with the edges also having
+  /// An attached set of attributes.
+  DenseMap<int32_t, DenseMap<int32_t, EdgeAttribute>> Graph;
+
+  /// Graph Vertex Attributes. These are presently stored seperate from the
+  /// main graph.
+  DenseMap<int32_t, VertexAttribute> VertexAttrs;
+
+  struct FunctionAttr {
+    int32_t FuncId;
+    uint64_t TSC;
+  };
+
+  /// 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?
+  DenseMap<pid_t, SmallVector<FunctionAttr, 4>> PerThreadFunctionStack;
+
+  /// Usefull object for getting human readable Symbol Names.
+  FuncIdConversionHelper &FuncIdHelper;
+  bool DeduceSiblingCalls = false;
+  uint64_t CurrentMaxTSC = 0;
+
+  /// A private function to help implement the statistic generation functions;
+  template <typename U>
+  void getStats(U begin, U end, GraphRenderer::TimeStat &S);
+
+  /// Calculates latency statistics for each edge and stores the data in the
+  /// Graph
+  void calculateEdgeStatistics();
+
+  /// Calculates latency statistics for each vertex and stores the data in the
+  /// Graph
+  void calculateVertexStatistics();
+
+  /// Normalises latency statistics for each edge and vertex by CycleFrequency;
+  void normaliseStatistics(double CycleFrequency);
+
+public:
+  /// Takes in a reference to a FuncIdHelper in order to have ready access to
+  /// Symbol names.
+  explicit GraphRenderer(FuncIdConversionHelper &FuncIdHelper, bool DSC)
+      : FuncIdHelper(FuncIdHelper), DeduceSiblingCalls(DSC) {}
+
+  /// 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);
+
+  /// An enum for enumerating the various statistics gathered on latencies
+  enum class StatType { COUNT, MIN, MED, PCT90, PCT99, MAX, SUM };
+
+  /// Output the Embedded graph in DOT format on \p OS, labeling the edges by
+  /// \p T
+  void exportGraphAsDOT(raw_ostream &OS, const XRayFileHeader &H,
+                        StatType T = StatType::COUNT);
+};
+}
+}
+
+#endif // XRAY_GRAPH_H

llvm/trunk/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-registry.h"
+#include "llvm/Support/ErrorHandling.h"
+#include "llvm/Support/FormatVariadic.h"
+#include "llvm/XRay/Trace.h"
+#include "llvm/XRay/YAMLXRayRecord.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));
+
+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));
+
+static cl::opt<bool> GraphDeduceSiblingCalls(
+    "deduce-sibling-calls",
+    cl::desc("Deduce sibling calls when unrolling function call stacks"),
+    cl::sub(Graph), cl::init(false));
+static cl::alias
+    GraphDeduceSiblingCalls2("d", cl::aliasopt(GraphDeduceSiblingCalls),
+                             cl::desc("Alias for -deduce-sibling-calls"),
+                             cl::sub(Graph));
+
+static cl::opt<GraphRenderer::StatType>
+    GraphEdgeLabel("edge-label",
+                   cl::desc("Output graphs with edges labeled with this field"),
+                   cl::value_desc("field"), cl::sub(Graph),
+                   cl::init(GraphRenderer::StatType::COUNT),
+                   cl::values(clEnumValN(GraphRenderer::StatType::COUNT,
+                                         "count", "function call counts"),
+                              clEnumValN(GraphRenderer::StatType::MIN, "min",
+                                         "minimum function durations"),
+                              clEnumValN(GraphRenderer::StatType::MED, "med",
+                                         "median function durations"),
+                              clEnumValN(GraphRenderer::StatType::PCT90, "90p",
+                                         "90th percentile durations"),
+                              clEnumValN(GraphRenderer::StatType::PCT99, "99p",
+                                         "99th percentile durations"),
+                              clEnumValN(GraphRenderer::StatType::MAX, "max",
+                                         "maximum function durations"),
+                              clEnumValN(GraphRenderer::StatType::SUM, "sum",
+                                         "sum of call durations")));
+static cl::alias GraphEdgeLabel2("e", cl::aliasopt(GraphEdgeLabel),
+                                 cl::desc("Alias for -edge-label"),
+                                 cl::sub(Graph));
+
+namespace {
+template <class T> T diff(T L, T R) { return std::max(L, R) - std::min(L, R); }
+
+void updateStat(GraphRenderer::TimeStat &S, int64_t lat) {
+  S.Count++;
+  if (S.Min > lat || S.Min == 0)
+    S.Min = lat;
+  if (S.Max < lat)
+    S.Max = lat;
+  S.Sum += lat;
+}
+}
+
+// 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.
+// FIXME: Refactor this and account subcommand to reduce code duplication.
+bool GraphRenderer::accountRecord(const XRayRecord &Record) {
+  if (CurrentMaxTSC == 0)
+    CurrentMaxTSC = Record.TSC;
+
+  if (Record.TSC < CurrentMaxTSC)
+    return false;
+
+  auto &ThreadStack = PerThreadFunctionStack[Record.TId];
+  switch (Record.Type) {
+  case RecordTypes::ENTER: {
+    if (VertexAttrs.count(Record.FuncId) == 0)
+      VertexAttrs[Record.FuncId].SymbolName =
+          FuncIdHelper.SymbolOrNumber(Record.FuncId);
+    ThreadStack.push_back({Record.FuncId, Record.TSC});
+    break;
+  }
+  case RecordTypes::EXIT: {
+    // FIXME: Refactor this and the account subcommand to reducr code
+    // duplication
+    if (ThreadStack.size() == 0 || ThreadStack.back().FuncId != Record.FuncId) {
+      if (!DeduceSiblingCalls)
+        return false;
+      auto Parent = std::find_if(
+          ThreadStack.rbegin(), ThreadStack.rend(),
+          [&](const FunctionAttr &A) { return A.FuncId == Record.FuncId; });
+      if (Parent == ThreadStack.rend())
+        return false; // There is no matching Function for this exit.
+      while (ThreadStack.back().FuncId != Record.FuncId) {
+        uint64_t D = diff(ThreadStack.back().TSC, Record.TSC);
+        int32_t TopFuncId = ThreadStack.back().FuncId;
+        ThreadStack.pop_back();
+        assert(ThreadStack.size() != 0);
+        auto &EA = Graph[ThreadStack.back().FuncId][TopFuncId];
+        EA.Timings.push_back(D);
+        updateStat(EA.S, D);
+        updateStat(VertexAttrs[TopFuncId].S, D);
+      }
+    }
+    uint64_t D = diff(ThreadStack.back().TSC, Record.TSC);
+    ThreadStack.pop_back();
+    auto &V = Graph[ThreadStack.empty() ? 0 : ThreadStack.back().FuncId];
+    auto &EA = V[Record.FuncId];
+    EA.Timings.push_back(D);
+    updateStat(EA.S, D);
+    updateStat(VertexAttrs[Record.FuncId].S, D);
+    break;
+  }
+  }
+
+  return true;
+}
+
+template <typename U>
+void GraphRenderer::getStats(U begin, U end, GraphRenderer::TimeStat &S) {
+  assert(begin != end);
+  std::ptrdiff_t MedianOff = S.Count / 2;
+  std::nth_element(begin, begin + MedianOff, end);
+  S.Median = *(begin + MedianOff);
+  std::ptrdiff_t Pct90Off = (S.Count * 9) / 10;
+  std::nth_element(begin, begin + Pct90Off, end);
+  S.Pct90 = *(begin + Pct90Off);
+  std::ptrdiff_t Pct99Off = (S.Count * 99) / 100;
+  std::nth_element(begin, begin + Pct99Off, end);
+  S.Pct99 = *(begin + Pct99Off);
+}
+
+void GraphRenderer::calculateEdgeStatistics() {
+  for (auto &V : Graph) {
+    for (auto &E : V.second) {
+      auto &A = E.second;
+      getStats(A.Timings.begin(), A.Timings.end(), A.S);
+    }
+  }
+}
+
+void GraphRenderer::calculateVertexStatistics() {
+  DenseMap<int32_t, std::pair<uint64_t, SmallVector<EdgeAttribute *, 4>>>
+      IncommingEdges;
+  uint64_t MaxCount = 0;
+  for (auto &V : Graph) {
+    for (auto &E : V.second) {
+      auto &IEV = IncommingEdges[E.first];
+      IEV.second.push_back(&E.second);
+      IEV.first += E.second.S.Count;
+      if (IEV.first > MaxCount)
+        MaxCount = IEV.first;
+    }
+  }
+  std::vector<uint64_t> TempTimings;
+  TempTimings.reserve(MaxCount);
+  for (auto &V : IncommingEdges) {
+    for (auto &P : V.second.second) {
+      TempTimings.insert(TempTimings.end(), P->Timings.begin(),
+                         P->Timings.end());
+    }
+    getStats(TempTimings.begin(), TempTimings.end(), VertexAttrs[V.first].S);
+    TempTimings.clear();
+  }
+}
+
+void GraphRenderer::normaliseStatistics(double CycleFrequency) {
+  for (auto &V : Graph) {
+    for (auto &E : V.second) {
+      auto &S = E.second.S;
+      S.Min /= CycleFrequency;
+      S.Median /= CycleFrequency;
+      S.Max /= CycleFrequency;
+      S.Sum /= CycleFrequency;
+      S.Pct90 /= CycleFrequency;
+      S.Pct99 /= CycleFrequency;
+    }
+  }
+  for (auto &V : VertexAttrs) {
+    auto &S = V.second.S;
+    S.Min /= CycleFrequency;
+    S.Median /= CycleFrequency;
+    S.Max /= CycleFrequency;
+    S.Sum /= CycleFrequency;
+    S.Pct90 /= CycleFrequency;
+    S.Pct99 /= CycleFrequency;
+  }
+}
+
+namespace {
+void outputEdgeInfo(const GraphRenderer::TimeStat &S, GraphRenderer::StatType T,
+                    raw_ostream &OS) {
+  switch (T) {
+  case GraphRenderer::StatType::COUNT:
+    OS << S.Count;
+    break;
+  case GraphRenderer::StatType::MIN:
+    OS << S.Min;
+    break;
+  case GraphRenderer::StatType::MED:
+    OS << S.Median;
+    break;
+  case GraphRenderer::StatType::PCT90:
+    OS << S.Pct90;
+    break;
+  case GraphRenderer::StatType::PCT99:
+    OS << S.Pct99;
+    break;
+  case GraphRenderer::StatType::MAX:
+    OS << S.Max;
+    break;
+  case GraphRenderer::StatType::SUM:
+    OS << S.Sum;
+    break;
+  }
+}
+}
+
+// Outputs a DOT format version of the Graph embedded in the GraphRenderer
+// object on OS. 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 XRayFileHeader &H,
+                                     StatType T) {
+  calculateEdgeStatistics();
+  calculateVertexStatistics();
+  if (H.CycleFrequency)
+    normaliseStatistics(H.CycleFrequency);
+
+  OS << "digraph xray {\n";
+
+  for (const auto &V : Graph)
+    for (const auto &E : V.second) {
+      OS << "F" << V.first << " -> "
+         << "F" << E.first << " [label=\"";
+      outputEdgeInfo(E.second.S, T, OS);
+      OS << "\"];\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);
+  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(GraphInstrMap, Symbolizer,
+                                                  FunctionAddresses);
+
+  xray::GraphRenderer GR(FuncIdHelper, GraphDeduceSiblingCalls);
+
+  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);
+
+  auto TraceOrErr = loadTraceFile(GraphInput, true);
+
+  if (!TraceOrErr) {
+    return joinErrors(
+        make_error<StringError>(
+            Twine("Failed loading input file '") + GraphInput + "'",
+            std::make_error_code(std::errc::protocol_error)),
+        std::move(Err));
+  }
+
+  auto &Trace = *TraceOrErr;
+  const auto &Header = Trace.getFileHeader();
+  for (const auto &Record : Trace) {
+    // 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, Header, GraphEdgeLabel);
+  return Error::success();
+});