Implemented color coding and Vertex labels in XRay Graph

[varno]

Summary

A patch to enable the llvm-xray graph subcommand to color edges and
vertices based on statistics and to annotate vertices with statistics.

Depends on D27243

[varno]

• Fixing Test with changes added to handle color.

[dblaikie]

Needs test coverage for the color functionality, I think? (I don't see any colors being tested in the tests)

tools/llvm-xray/xray-graph.cc

284–290

Could use a member pointer & a helper function (possibly template) to maybe make these shorter/more reliable (by only having to mention the member name once - less chance of accidentally mismatching them).

346

Typo, 'function'

Also probably s/Normalise Statistics/normaliseStatistics/

Also, normalize rather than normalise (consistency with the rest of the codebase)

439–462

Could use another member pointer helper to handle this table, if you like.

[dberris]

tools/llvm-xray/xray-graph.cc

393–397

Probably missing a few punctuation marks. I think some structured fomulae might help with what exactly it's doing, like:

// Evaluates a polynomial given the provided range of coefficients in order.
//
//    p(x) = a[0]*x^0 + a[1]*x^1 + a[2]*x^2 + ... + a[n]*x^n
//
// We use Horner's Method for numerical stability for mapping to an 8-bit
// fixed point domain.

414–422

You probably want to document how you came up with these polynomials, even potentially citing some sources on how one might possibly start changing these.

425–427

Reading this, I think you're better off making polyEval take an llvm::ArrayRef instead (to make it easier to read).

464

Can you document why compare is returning the square root? You mentioned this offline in our discussion, but it would be good to document the reasons here.

[varno]

• Clang format

[varno]

Fixed and addressed comments.

[varno]

tools/llvm-xray/xray-graph.cc

284–290

Discussion resulted in this comment being seen as not easy to do due to specifics.

[dberris]

In general I think this could do with a bit more documentation, about the semantics of what we're trying to do (as opposed to how we're doing it).

tools/llvm-xray/xray-graph.cc

170

Empty line after this?

171

This is a template, no need to be static (it's implicitly inline).

175

Style guide says identifiers ought to have an uppercase start letter.

184–187

Can we describe this in less round-about way?

We can spend a few words in documentation to indicate what the side-effects are and some detail of what the algorithm being implemented is.

192–193

Was the intent to use llvm::Expected<...>? In which case I'd prefer you change this now.

[dberris]

Also, I think you'd want to rebase this given that llvm-xray graph has landed upstream.

[varno]

• Clang format
• Fixed tests after rebase
• Addressed review comments

[varno]

Also has been rebased to master.

[dberris]

tools/llvm-xray/xray-graph.cc

403

Empty line after this?

405

s/propper/proper/

416–417

Leave out the "I" and "Mathematica" parts -- explain the concepts involved, not the mechanics.

423–424

Instead of "subjectively provided a good result", say something like: "we used a 9-degree polynomial arbitrarily based on a fuzzy goodness of fit metric (using human judgment)".

437–438

Unnecessary now?

446–447

s/annother/another/

578–584

Do you need the equivalent of a "keep-going" flag here too (similar to what we have in llvm-xray account)?

[varno]

• Reply to comments

[dberris]

tools/llvm-xray/xray-graph.cc

578–584

Okay, now I think you need to report errors encountered that we're ignoring in case we do want to keep going. Accumulating the individual errors into a long list seems unnecessary to me.

580–586

This looks like it'd be better as:

if (auto E = GR.accountRecord(Record)) {
  ...
}

[varno]

• Respond to comments
• clang-format new

[varno]

• clang-format fix

[varno]

tools/llvm-xray/xray-graph.cc

580–586

This does not quite work here.

[dberris]

LGTM -- we can probably use some more user-facing documentation explaining a bit what this tool actually does (probably time to update docs/XRay.rst) but something to be done for later.

tools/llvm-xray/xray-graph.cc

579–584

In the future, comments like these really ought to expound more on what it's actually doing at a semantic level to help the reader of the code. A more informative comment as to "why" we're doing something might make more sense to the reader as that's not immediately obvious. Something like:

// Populate the graph with function call records that we
// encounter from the XRay trace. Any errors we encounter
// will be printed through standard error.

[dblaikie]

llvm/trunk/tools/llvm-xray/xray-graph.cc

212–213 ↗

(On Diff #85700)

Should probably be using llvm::errc - see the Support/errc.h - it defines portable constants we know work across all the compilers LLVM supports, etc.

401–403 ↗

(On Diff #85700)

Usually don't bother with {} on single line scopes.

586–592 ↗

(On Diff #85700)

Should accountRecord do this work/include this information in its Error (rather than callers doing so)?

llvm/trunk/tools/llvm-xray/xray-graph.h

135 ↗

(On Diff #85700)

Const value return type? I'm assuming this should be a const ref return type? (we should really have a clang-tidy for that if we don't already, maybe even a straight-up compiler warning)

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}
+- { id: 4, address: 0x4, function: 0x4, kind: function-enter, always-instrument: true}
+- { id: 4, address: 0x5, function: 0x4, kind: function-exit, always-instrument: true}
+- { id: 5, address: 0x5, function: 0x5, kind: function-enter, always-instrument: true}
+- { id: 5, address: 0x6, function: 0x5, kind: function-exit, always-instrument: true}
+- { id: 6, address: 0x6, function: 0x6, kind: function-enter, always-instrument: true}
+- { id: 6, address: 0x7, function: 0x6, kind: function-exit, always-instrument: true}
+- { id: 7, address: 0x7, function: 0x7, kind: function-enter, always-instrument: true}
+- { id: 7, address: 0x8, function: 0x7, kind: function-exit, always-instrument: true}
+- { id: 8, address: 0x8, function: 0x8, kind: function-enter, always-instrument: true}
+- { id: 8, address: 0x9, function: 0x8, kind: function-exit, always-instrument: true}
+- { id: 9, address: 0x9, function: 0x9, kind: function-enter, always-instrument: true}
+- { id: 9, address: 0xA, function: 0x9, kind: function-exit, always-instrument: true}
 ...

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

+#RUN: llvm-xray graph %s -o - -m %S/Inputs/simple-instrmap.yaml -t yaml -e sum -c sum \
+#RUN:    | FileCheck %s -check-prefix=EDGE
+#RUN: llvm-xray graph %s -o - -m %S/Inputs/simple-instrmap.yaml -t yaml -v sum -b sum \
+#RUN:    | FileCheck %s -check-prefix=VERTEX
+---
+header:
+  version: 1
+  type: 0
+  constant-tsc: true
+  nonstop-tsc: true
+  cycle-frequency: 1
+records:
+  - { type: 0, func-id: 1, cpu: 1, thread: 111, kind: function-enter, tsc: 10000 }
+  - { type: 0, func-id: 1, cpu: 1, thread: 111, kind: function-exit,  tsc: 10010 }
+  - { type: 0, func-id: 2, cpu: 1, thread: 111, kind: function-enter, tsc: 10100 }
+  - { type: 0, func-id: 2, cpu: 1, thread: 111, kind: function-exit,  tsc: 10120 }
+  - { type: 0, func-id: 3, cpu: 1, thread: 111, kind: function-enter, tsc: 10200 }
+  - { type: 0, func-id: 3, cpu: 1, thread: 111, kind: function-exit,  tsc: 10230 }
+  - { type: 0, func-id: 4, cpu: 1, thread: 111, kind: function-enter, tsc: 10300 }
+  - { type: 0, func-id: 4, cpu: 1, thread: 111, kind: function-exit,  tsc: 10340 }
+  - { type: 0, func-id: 5, cpu: 1, thread: 111, kind: function-enter, tsc: 10400 }
+  - { type: 0, func-id: 5, cpu: 1, thread: 111, kind: function-exit,  tsc: 10450 }
+  - { type: 0, func-id: 6, cpu: 1, thread: 111, kind: function-enter, tsc: 10500 }
+  - { type: 0, func-id: 6, cpu: 1, thread: 111, kind: function-exit,  tsc: 10560 }
+  - { type: 0, func-id: 7, cpu: 1, thread: 111, kind: function-enter, tsc: 10600 }
+  - { type: 0, func-id: 7, cpu: 1, thread: 111, kind: function-exit,  tsc: 10670 }
+  - { type: 0, func-id: 8, cpu: 1, thread: 111, kind: function-enter, tsc: 10700 }
+  - { type: 0, func-id: 8, cpu: 1, thread: 111, kind: function-exit,  tsc: 10780 }
+  - { type: 0, func-id: 9, cpu: 1, thread: 111, kind: function-enter, tsc: 10800 }
+  - { type: 0, func-id: 9, cpu: 1, thread: 111, kind: function-exit,  tsc: 10890 }
+---
+
+
+#EDGE:     digraph xray {
+#EDGE-DAG: F0 -> F7 [label="7.{{[0-9]*}}e+01" color="#B00100"];
+#EDGE-DAG: F0 -> F2 [label="2.{{[0-9]*}}e+01" color="#FD9965"];
+#EDGE-DAG: F0 -> F9 [label="9.{{[0-9]*}}e+01" color="#7F0000"];
+#EDGE-DAG: F0 -> F4 [label="4.{{[0-9]*}}e+01" color="#E8543b"];
+#EDGE-DAG: F0 -> F6 [label="6.{{[0-9]*}}e+01" color="#C5140a"];
+#EDGE-DAG: F0 -> F1 [label="1.{{[0-9]*}}e+01" color="#FDC58c"];
+#EDGE-DAG: F0 -> F8 [label="8.{{[0-9]*}}e+01" color="#990101"];
+#EDGE-DAG: F0 -> F3 [label="3.{{[0-9]*}}e+01" color="#F5744d"];
+#EDGE-DAG: F0 -> F5 [label="5.{{[0-9]*}}e+01" color="#D83323"];
+#EDGE-DAG: F7 [label="@(7)"];
+#EDGE-DAG: F2 [label="@(2)"];
+#EDGE-DAG: F9 [label="@(9)"];
+#EDGE-DAG: F4 [label="@(4)"];
+#EDGE-DAG: F6 [label="@(6)"];
+#EDGE-DAG: F1 [label="@(1)"];
+#EDGE-DAG: F8 [label="@(8)"];
+#EDGE-DAG: F3 [label="@(3)"];
+#EDGE-DAG: F5 [label="@(5)"];
+#EDGE-NEXT:     }
+#
+#VERTEX:     digraph xray {
+#VERTEX-DAG: node [shape=record];
+#VERTEX-DAG: F0 -> F7 [label=""];
+#VERTEX-DAG: F0 -> F2 [label=""];
+#VERTEX-DAG: F0 -> F9 [label=""];
+#VERTEX-DAG: F0 -> F4 [label=""];
+#VERTEX-DAG: F0 -> F6 [label=""];
+#VERTEX-DAG: F0 -> F1 [label=""];
+#VERTEX-DAG: F0 -> F8 [label=""];
+#VERTEX-DAG: F0 -> F3 [label=""];
+#VERTEX-DAG: F0 -> F5 [label=""];
+#VERTEX-DAG: F7 [label="{@(7)|7.{{[0-9]*}}e+01}" color="#B00100"];
+#VERTEX-DAG: F2 [label="{@(2)|2.{{[0-9]*}}e+01}" color="#FD9965"];
+#VERTEX-DAG: F9 [label="{@(9)|9.{{[0-9]*}}e+01}" color="#7F0000"];
+#VERTEX-DAG: F4 [label="{@(4)|4.{{[0-9]*}}e+01}" color="#E8543b"];
+#VERTEX-DAG: F6 [label="{@(6)|6.{{[0-9]*}}e+01}" color="#C5140a"];
+#VERTEX-DAG: F1 [label="{@(1)|1.{{[0-9]*}}e+01}" color="#FDC58c"];
+#VERTEX-DAG: F8 [label="{@(8)|8.{{[0-9]*}}e+01}" color="#990101"];
+#VERTEX-DAG: F3 [label="{@(3)|3.{{[0-9]*}}e+01}" color="#F5744d"];
+#VERTEX-DAG: F5 [label="{@(5)|5.{{[0-9]*}}e+01}" color="#D83323"];
+#VERTEX-NEXT: }

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:    | FileCheck %s -check-prefix=EMPTY
 #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 \

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:    | FileCheck %s -check-prefix=EMPTY
 #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 \

tools/llvm-xray/xray-graph.h

 // Generate a DOT file to represent the function call graph encountered in
 // the trace.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef XRAY_GRAPH_H
 #define XRAY_GRAPH_H
 
+#include <string>
 #include <vector>
 
 #include "func-id-helper.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/SmallVector.h"
+#include "llvm/Support/Errc.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Support/Program.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 enum for enumerating the various statistics gathered on latencies
+  enum class StatType { NONE, COUNT, MIN, MED, PCT90, PCT99, MAX, SUM };
+
   /// 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;
+    uint64_t Count = 0;
+    double Min = 0;
+    double Median = 0;
+    double Pct90 = 0;
+    double Pct99 = 0;
+    double Max = 0;
+    double Sum = 0;
+    std::string getAsString(StatType T) const;
+    double compare(StatType T, const TimeStat &Other) const;
   };
 
   /// 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;
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;
 
+  TimeStat GraphEdgeMax;
+  TimeStat GraphVertexMax;
+
   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<llvm::sys::ProcessInfo::ProcessId, 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);
+  void updateMaxStats(const TimeStat &S, TimeStat &M);
 
   /// 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);
+  void normalizeStatistics(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 };
+  Error accountRecord(const XRayRecord &Record);
 
   /// 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);
+                        StatType EdgeLabel = StatType::NONE,
+                        StatType EdgeColor = StatType::NONE,
+                        StatType VertexLabel = StatType::NONE,
+                        StatType VertexColor = StatType::NONE);
 };
 }
 }
 
 #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 <cmath>
 #include <system_error>
 #include <utility>
 
 #include "xray-extract.h"
 #include "xray-graph.h"
 #include "xray-registry.h"
-#include "llvm/Support/Errc.h"
+#include "llvm/ADT/ArrayRef.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<bool> GraphKeepGoing("keep-going",
+                                    cl::desc("Keep going on errors encountered"),
+                                    cl::sub(Graph), cl::init(false));
+static cl::alias GraphKeepGoing2("k", cl::aliasopt(GraphKeepGoing),
+                                 cl::desc("Alias for -keep-going"),
+                                 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 "
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,
+                   cl::init(GraphRenderer::StatType::NONE),
+                   cl::values(clEnumValN(GraphRenderer::StatType::NONE, "none",
+                                         "Do not label Edges"),
+                              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); }
+static cl::opt<GraphRenderer::StatType> GraphVertexLabel(
+    "vertex-label",
+    cl::desc("Output graphs with vertices labeled with this field"),
+    cl::value_desc("field"), cl::sub(Graph),
+    cl::init(GraphRenderer::StatType::NONE),
+    cl::values(clEnumValN(GraphRenderer::StatType::NONE, "none",
+                          "Do not label Edges"),
+               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 GraphVertexLabel2("v", cl::aliasopt(GraphVertexLabel),
+                                   cl::desc("Alias for -edge-label"),
+                                   cl::sub(Graph));
 
-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;
+static cl::opt<GraphRenderer::StatType> GraphEdgeColorType(
+    "color-edges",
+    cl::desc("Output graphs with edge colors determined by this field"),
+    cl::value_desc("field"), cl::sub(Graph),
+    cl::init(GraphRenderer::StatType::NONE),
+    cl::values(clEnumValN(GraphRenderer::StatType::NONE, "none",
+                          "Do not label Edges"),
+               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 GraphEdgeColorType2("c", cl::aliasopt(GraphEdgeColorType),
+                                     cl::desc("Alias for -color-edges"),
+                                     cl::sub(Graph));
+
+static cl::opt<GraphRenderer::StatType> GraphVertexColorType(
+    "color-vertices",
+    cl::desc("Output graphs with vertex colors determined by this field"),
+    cl::value_desc("field"), cl::sub(Graph),
+    cl::init(GraphRenderer::StatType::NONE),
+    cl::values(clEnumValN(GraphRenderer::StatType::NONE, "none",
+                          "Do not label Edges"),
+               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 GraphVertexColorType2("b", cl::aliasopt(GraphVertexColorType),
+                                       cl::desc("Alias for -edge-label"),
+                                       cl::sub(Graph));
+
+template <class T> T diff(T L, T R) {
+  return std::max(L, R) - std::min(L, R);
 }
+
+// Updates the statistics for a GraphRenderer::TimeStat
+static void updateStat(GraphRenderer::TimeStat &S, int64_t L) {
+  S.Count++;
+  if (S.Min > L || S.Min == 0)
+    S.Min = L;
+  if (S.Max < L)
+    S.Max = L;
+  S.Sum += L;
 }
 
-// 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.
+// Evaluates an XRay record and performs accounting on it.
+//
+// If the record is an ENTER record it pushes the FuncID and TSC onto a
+// structure representing the call stack for that function.
+// If the record is an EXIT record it checks computes computes the ammount of
+// time the function took to complete and then stores that information in an
+// edge of the graph. If there is no matching ENTER record the function tries
+// to recover by assuming that there were EXIT records which were missed, for
+// example caused by tail call elimination and if the option is enabled then
+// then tries to recover from this.
+//
+// This funciton will also error if the records are out of order, as the trace
+// is expected to be sorted.
 //
-// There is an immaginary root for functions at the top of their stack with
+// The graph generated has an immaginary root for functions called by no-one at
 // 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) {
+Error GraphRenderer::accountRecord(const XRayRecord &Record) {
+  using std::make_error_code;
+  using std::errc;
   if (CurrentMaxTSC == 0)
     CurrentMaxTSC = Record.TSC;
 
   if (Record.TSC < CurrentMaxTSC)
-    return false;
+    return make_error<StringError>("Records not in order",
+                                   make_error_code(errc::invalid_argument));
 
   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;
+        return make_error<StringError>("No matching ENTRY record",
+                                       make_error_code(errc::invalid_argument));
       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.
+        return make_error<StringError>("No matching Entry record in stack",
+                                       make_error_code(errc::invalid_argument)); // 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;
+  return Error::success();
 }
 
 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::updateMaxStats(const GraphRenderer::TimeStat &S,
+                                   GraphRenderer::TimeStat &M) {
+  M.Count = std::max(M.Count, S.Count);
+  M.Min = std::max(M.Min, S.Min);
+  M.Median = std::max(M.Median, S.Median);
+  M.Pct90 = std::max(M.Pct90, S.Pct90);
+  M.Pct99 = std::max(M.Pct99, S.Pct99);
+  M.Max = std::max(M.Max, S.Max);
+  M.Sum = std::max(M.Sum, S.Sum);
+}
+
 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);
+      updateMaxStats(A.S, GraphEdgeMax);
     }
   }
 }
 
 void GraphRenderer::calculateVertexStatistics() {
   DenseMap<int32_t, std::pair<uint64_t, SmallVector<EdgeAttribute *, 4>>>
       IncommingEdges;
   uint64_t MaxCount = 0;
void GraphRenderer::calculateVertexStatistics() {
   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);
+    updateMaxStats(VertexAttrs[V.first].S, GraphVertexMax);
     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;
-    }
+// A Helper function for normalizeStatistics which normalises a single
+// TimeStat element.
+static void normalizeTimeStat(GraphRenderer::TimeStat &S,
+                              double CycleFrequency) {
+
+// Normalises the statistics in the graph for a given TSC frequency.
+void GraphRenderer::normalizeStatistics(double CycleFrequency) {
+  for (auto &V : Graph) {
+    for (auto &E : V.second) {
+      auto &S = E.second.S;
+      normalizeTimeStat(S, 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;
+    normalizeTimeStat(S, CycleFrequency);
   }
+
+  normalizeTimeStat(GraphEdgeMax, CycleFrequency);
+  normalizeTimeStat(GraphVertexMax, CycleFrequency);
 }
 
-namespace {
-void outputEdgeInfo(const GraphRenderer::TimeStat &S, GraphRenderer::StatType T,
-                    raw_ostream &OS) {
+// Returns a string containing the value of statistic field T
+std::string
+GraphRenderer::TimeStat::getAsString(GraphRenderer::StatType T) const {
+  std::string St;
+  raw_string_ostream S{St};
   switch (T) {
   case GraphRenderer::StatType::COUNT:
-    OS << S.Count;
+    S << Count;
     break;
   case GraphRenderer::StatType::MIN:
-    OS << S.Min;
+    S << Min;
     break;
   case GraphRenderer::StatType::MED:
-    OS << S.Median;
+    S << Median;
     break;
   case GraphRenderer::StatType::PCT90:
-    OS << S.Pct90;
+    S << Pct90;
     break;
   case GraphRenderer::StatType::PCT99:
-    OS << S.Pct99;
+    S << Pct99;
     break;
   case GraphRenderer::StatType::MAX:
-    OS << S.Max;
+    S << Max;
     break;
   case GraphRenderer::StatType::SUM:
-    OS << S.Sum;
+    S << Sum;
+    break;
+  case GraphRenderer::StatType::NONE:
     break;
   }
+  return S.str();
 }
+
+// Evaluates a polynomial given the coefficints provided in an ArrayRef
+// evaluating:
+//
+//    p(x) = a[n-0]*x^0 + a[n-1]*x^1 + ... a[n-n]*x^n
+//
+// at x_0 using Horner's Method for both performance and stability reasons.
+static double polyEval(ArrayRef<double> a, double x_0) {
+  double B = 0;
+  for (const auto &c : a) {
+    B = c + B * x_0;
+  }
+  return B;
+}
+
+// Takes a double precision number, clips it between 0 and 1 and then converts
+// that to an integer between 0x00 and 0xFF with proxpper rounding.
+static uint8_t uintIntervalTo8bitChar(double B) {
+  double n = std::max(std::min(B, 1.0), 0.0);
+  return static_cast<uint8_t>(255 * n + 0.5);
+}
+
+// Gets a color in a gradient given a number in the interval [0,1], it does this
+// by evaluating a polynomial which maps [0, 1] -> [0, 1] for each of the R G
+// and B values in the color. It then converts this [0,1] colors to a 24 bit
+// color.
+//
+// In order to calculate these polynomials,
+// //   1. Convert the OrRed9 color scheme from http://colorbrewer2.org/ from sRGB
+//      to LAB color space.
+//   2. Interpolate between the descrete colors in LAB space using a cubic
+//      spline interpolation.
+//   3. Sample this interpolation at 100 points and convert to sRGB.
+//   4. Calculate a polynomial fit for these 100 points for each of R G and B.
+//      We used a polynomial of degree 9 arbitrarily based on a fuzzy goodness
+//      of fit metric (using human judgement);
+//   5. Extract these polynomial coefficients from matlab as a set of constants.
+static std::string getColor(double point) {
+  assert(point >= 0.0 && point <= 1);
+  const static double RedPoly[] = {-38.4295,  239.239, -600.108, 790.544,
+                                   -591.26,   251.304, -58.0983, 6.62999,
+                                   -0.325899, 1.00173};
+  const static double GreenPoly[] = {-603.634,   2338.15, -3606.74, 2786.16,
+                                     -1085.19,   165.15,  11.2584,  -6.11338,
+                                     -0.0091078, 0.965469};
+  const static double BluePoly[] = {-325.686, 947.415,  -699.079, -513.75,
+                                    1127.78,  -732.617, 228.092,  -33.8202,
+                                    0.732108, 0.913916};
+
+  uint8_t r = uintIntervalTo8bitChar(polyEval(RedPoly, point));
+  uint8_t g = uintIntervalTo8bitChar(polyEval(GreenPoly, point));
+  uint8_t b = uintIntervalTo8bitChar(polyEval(BluePoly, point));
+
+  return llvm::formatv("#{0:X-2}{1:X-2}{2:x-2}", r, g, b);
+}
+
+// Returns the quotient between the property T of this and another TimeStat as
+// a double
+double GraphRenderer::TimeStat::compare(StatType T, const TimeStat &O) const {
+  double retval = 0;
+  switch (T) {
+  case GraphRenderer::StatType::COUNT:
+    retval = static_cast<double>(Count) / static_cast<double>(O.Count);
+    break;
+  case GraphRenderer::StatType::MIN:
+    retval = Min / O.Min;
+    break;
+  case GraphRenderer::StatType::MED:
+    retval = Median / O.Median;
+    break;
+  case GraphRenderer::StatType::PCT90:
+    retval = Pct90 / O.Pct90;
+    break;
+  case GraphRenderer::StatType::PCT99:
+    retval = Pct99 / O.Pct99;
+    break;
+  case GraphRenderer::StatType::MAX:
+    retval = Max / O.Max;
+    break;
+  case GraphRenderer::StatType::SUM:
+    retval = Sum / O.Sum;
+    break;
+  case GraphRenderer::StatType::NONE:
+    retval = 0.0;
+    break;
+  }
+  return std::sqrt(
+      retval); // the square root here provides more dynamic contrast for
+               // low runtime edges, giving better separation and
+               // coloring lower down the call stack.
 }
 
 // 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) {
+                                     StatType ET, StatType EC, StatType VT,
+                                     StatType VC) {
   calculateEdgeStatistics();
   calculateVertexStatistics();
   if (H.CycleFrequency)
-    normaliseStatistics(H.CycleFrequency);
+    normalizeStatistics(H.CycleFrequency);
 
   OS << "digraph xray {\n";
 
+  if (VT != StatType::NONE)
+    OS << "node [shape=record];\n";
+
   for (const auto &V : Graph)
     for (const auto &E : V.second) {
+      const auto &S = E.second.S;
       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";
-
+         << "F" << E.first << " [label=\"" << S.getAsString(ET) << "\"";
+      if (EC != StatType::NONE)
+        OS << " color=\"" << getColor(S.compare(EC, GraphEdgeMax)) << "\"";
+      OS << "];\n";
+    }
+
+  for (const auto &V : VertexAttrs) {
+    const auto &VA = V.second;
+    OS << "F" << V.first << " [label=\"" << (VT != StatType::NONE ? "{" : "")
+       << (VA.SymbolName.size() > 40 ? VA.SymbolName.substr(0, 40) + "..."
+                                     : VA.SymbolName);
+    if (VT != StatType::NONE)
+      OS << "|" << VA.S.getAsString(VT) << "}\"";
+    else
+      OS << "\"";
+    if (VC != StatType::NONE)
+      OS << " color=\"" << getColor(VA.S.compare(VC, GraphVertexMax)) << "\"";
+    OS << "];\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.
return joinErrors(
         make_error<StringError>(Twine("Failed loading input file '") +
                                     GraphInput + "'",
                                 make_error_code(llvm::errc::invalid_argument)),
         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 +
-              "'.",
-          make_error_code(llvm::errc::invalid_argument));
+    // Generate graph.
+    auto ER2 = GR.accountRecord(Record);
+    if (ER2){
+      Err = joinErrors(std::move(ER2), std::move(Err));
+      if(!GraphKeepGoing)
+        return Err;
     }
   }
 
-  GR.exportGraphAsDOT(OS, Header, GraphEdgeLabel);
-  return Error::success();
+  GR.exportGraphAsDOT(OS, Header, GraphEdgeLabel, GraphEdgeColorType,
+                      GraphVertexLabel, GraphVertexColorType);
+  return Err;
 });