Index: llvm/trunk/test/tools/llvm-xray/X86/Inputs/simple-instrmap.yaml =================================================================== --- llvm/trunk/test/tools/llvm-xray/X86/Inputs/simple-instrmap.yaml +++ llvm/trunk/test/tools/llvm-xray/X86/Inputs/simple-instrmap.yaml @@ -7,4 +7,16 @@ - { 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} ... Index: llvm/trunk/test/tools/llvm-xray/X86/graph-color-simple-case.yaml =================================================================== --- llvm/trunk/test/tools/llvm-xray/X86/graph-color-simple-case.yaml +++ llvm/trunk/test/tools/llvm-xray/X86/graph-color-simple-case.yaml @@ -0,0 +1,75 @@ +#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: } Index: llvm/trunk/test/tools/llvm-xray/X86/graph-deduce-tail-call.yaml =================================================================== --- llvm/trunk/test/tools/llvm-xray/X86/graph-deduce-tail-call.yaml +++ llvm/trunk/test/tools/llvm-xray/X86/graph-deduce-tail-call.yaml @@ -1,5 +1,5 @@ #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 # Index: llvm/trunk/test/tools/llvm-xray/X86/graph-simple-case.yaml =================================================================== --- llvm/trunk/test/tools/llvm-xray/X86/graph-simple-case.yaml +++ llvm/trunk/test/tools/llvm-xray/X86/graph-simple-case.yaml @@ -1,5 +1,5 @@ #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 # Index: llvm/trunk/tools/llvm-xray/xray-graph.h =================================================================== --- llvm/trunk/tools/llvm-xray/xray-graph.h +++ llvm/trunk/tools/llvm-xray/xray-graph.h @@ -15,13 +15,15 @@ #ifndef XRAY_GRAPH_H #define XRAY_GRAPH_H +#include #include #include "func-id-helper.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/SmallVector.h" -#include "llvm/Support/raw_ostream.h" +#include "llvm/Support/Errc.h" #include "llvm/Support/Program.h" +#include "llvm/Support/raw_ostream.h" #include "llvm/XRay/Trace.h" #include "llvm/XRay/XRayRecord.h" @@ -32,15 +34,20 @@ /// 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 @@ -61,6 +68,16 @@ TimeStat S; }; + struct FunctionAttr { + int32_t FuncId; + uint64_t TSC; + }; + + typedef SmallVector FunctionStack; + + typedef DenseMap + PerThreadFunctionStackMap; + private: /// The Graph stored in an edge-list like format, with the edges also having /// An attached set of attributes. @@ -70,17 +87,14 @@ /// main graph. DenseMap VertexAttrs; - struct FunctionAttr { - int32_t FuncId; - uint64_t TSC; - }; + TimeStat GraphEdgeMax; + TimeStat GraphVertexMax; /// 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> - PerThreadFunctionStack; + PerThreadFunctionStackMap PerThreadFunctionStack; /// Usefull object for getting human readable Symbol Names. FuncIdConversionHelper &FuncIdHelper; @@ -90,6 +104,7 @@ /// A private function to help implement the statistic generation functions; template 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 @@ -100,7 +115,7 @@ 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 @@ -115,15 +130,19 @@ /// Records should be in order runtime on an ideal system.) /// /// FIXME: Make this more robust against small irregularities. - bool accountRecord(const XRayRecord &Record); + Error accountRecord(const XRayRecord &Record); - /// An enum for enumerating the various statistics gathered on latencies - enum class StatType { COUNT, MIN, MED, PCT90, PCT99, MAX, SUM }; + const PerThreadFunctionStackMap getPerThreadFunctionStack() const { + return PerThreadFunctionStack; + } /// 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); }; } } Index: llvm/trunk/tools/llvm-xray/xray-graph.cc =================================================================== --- llvm/trunk/tools/llvm-xray/xray-graph.cc +++ llvm/trunk/tools/llvm-xray/xray-graph.cc @@ -13,13 +13,14 @@ //===----------------------------------------------------------------------===// #include #include +#include #include #include #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" @@ -34,16 +35,25 @@ cl::desc(""), cl::Required, cl::sub(Graph)); +static cl::opt + 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 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 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::opt + 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)); @@ -72,8 +82,10 @@ 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"), @@ -91,36 +103,120 @@ cl::desc("Alias for -edge-label"), cl::sub(Graph)); -namespace { +static cl::opt 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)); + +static cl::opt 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 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 T diff(T L, T R) { return std::max(L, R) - std::min(L, R); } -void updateStat(GraphRenderer::TimeStat &S, int64_t lat) { +// Updates the statistics for a GraphRenderer::TimeStat +static void updateStat(GraphRenderer::TimeStat &S, int64_t L) { S.Count++; - if (S.Min > lat || S.Min == 0) - S.Min = lat; - if (S.Max < lat) - S.Max = lat; - S.Sum += lat; -} + 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. // -// There is an immaginary root for functions at the top of their stack with +// This funciton will also error if the records are out of order, as the trace +// is expected to be sorted. +// +// 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("Records not in order", + make_error_code(errc::invalid_argument)); auto &ThreadStack = PerThreadFunctionStack[Record.TId]; switch (Record.Type) { @@ -136,12 +232,16 @@ // duplication if (ThreadStack.size() == 0 || ThreadStack.back().FuncId != Record.FuncId) { if (!DeduceSiblingCalls) - return false; + return make_error("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( + "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; @@ -164,7 +264,7 @@ } } - return true; + return Error::success(); } template @@ -181,11 +281,23 @@ 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); } } } @@ -211,60 +323,162 @@ 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) { +// A Helper function for normalizeStatistics which normalises a single +// TimeStat element. +static void normalizeTimeStat(GraphRenderer::TimeStat &S, + double CycleFrequency) { + S.Min /= CycleFrequency; + S.Median /= CycleFrequency; + S.Max /= CycleFrequency; + S.Sum /= CycleFrequency; + S.Pct90 /= CycleFrequency; + S.Pct99 /= 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; - S.Min /= CycleFrequency; - S.Median /= CycleFrequency; - S.Max /= CycleFrequency; - S.Sum /= CycleFrequency; - S.Pct90 /= CycleFrequency; - S.Pct99 /= CycleFrequency; + 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 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(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(Count) / static_cast(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 @@ -274,29 +488,41 @@ // // 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"; + << "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) - OS << "F" << V.first << " [label=\"" - << (V.second.SymbolName.size() > 40 - ? V.second.SymbolName.substr(0, 40) + "..." - : V.second.SymbolName) - << "\"];\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"; } @@ -352,15 +578,26 @@ 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( - Twine("Failed accounting function calls in file '") + GraphInput + - "'.", - make_error_code(llvm::errc::invalid_argument)); + // Generate graph. + auto E = GR.accountRecord(Record); + if (!E) + continue; + + for (const auto &ThreadStack : GR.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.FuncId) << '\n'; } + + if (!GraphKeepGoing) + return joinErrors(std::move(E), std::move(Err)); + handleAllErrors(std::move(E), + [&](const ErrorInfoBase &E) { E.log(errs()); }); } - GR.exportGraphAsDOT(OS, Header, GraphEdgeLabel); - return Error::success(); + GR.exportGraphAsDOT(OS, Header, GraphEdgeLabel, GraphEdgeColorType, + GraphVertexLabel, GraphVertexColorType); + return Err; });