Index: test/tools/llvm-xray/X86/graph-deduce-tail-call.yaml =================================================================== --- test/tools/llvm-xray/X86/graph-deduce-tail-call.yaml +++ test/tools/llvm-xray/X86/graph-deduce-tail-call.yaml @@ -1,7 +1,7 @@ #RUN: llvm-xray graph %s -i=yaml -o - -m %S/Inputs/simple-instrmap.yaml -t yaml -d \ #RUN: | FileCheck %s -check-prefix=EMPTY #RUN: llvm-xray graph %s -i=yaml -o - -m %S/Inputs/simple-instrmap.yaml -t yaml -d -e count \ -#RUN: | FileCheck %s -check-prefix=EMPTY +#RUN: | FileCheck %s -check-prefix=COUNT # #RUN: llvm-xray graph %s -i=yaml -o - -m %S/Inputs/simple-instrmap.yaml -t yaml -d -e min \ #RUN: | FileCheck %s -check-prefix=TIME @@ -47,14 +47,24 @@ ... #EMPTY: digraph xray { -#EMPTY-DAG: F0 -> F1 [label="1"]; -#EMPTY-DAG: F1 -> F2 [label="1"]; -#EMPTY-DAG: F2 -> F3 [label="1"]; +#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: } +#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: } + + #TIME: digraph xray { #TIME-DAG: F0 -> F1 [label="4.{{.*}}"]; #TIME-DAG: F1 -> F2 [label="3.{{.*}}"]; Index: test/tools/llvm-xray/X86/graph-simple-case.yaml =================================================================== --- test/tools/llvm-xray/X86/graph-simple-case.yaml +++ test/tools/llvm-xray/X86/graph-simple-case.yaml @@ -1,7 +1,7 @@ #RUN: llvm-xray graph %s -i=yaml -o - -m %S/Inputs/simple-instrmap.yaml -t yaml \ #RUN: | FileCheck %s -check-prefix=EMPTY #RUN: llvm-xray graph %s -i=yaml -o - -m %S/Inputs/simple-instrmap.yaml -t yaml -e count \ -#RUN: | FileCheck %s -check-prefix=EMPTY +#RUN: | FileCheck %s -check-prefix=COUNT # #RUN: llvm-xray graph %s -i=yaml -o - -m %S/Inputs/simple-instrmap.yaml -t yaml -e min \ #RUN: | FileCheck %s -check-prefix=TIME @@ -31,10 +31,15 @@ #EMPTY: digraph xray { -#EMPTY: F0 -> F1 [label="1"]; +#EMPTY: F0 -> F1 [label=""]; #EMPTY: F1 [label="@(1)"]; #EMPTY: } +#COUNT: digraph xray { +#COUNT: F0 -> F1 [label="1"]; +#COUNT: F1 [label="@(1)"]; +#COUNT: } + #TIME: digraph xray { #TIME: F0 -> F1 [label="3.8{{.*}}e-08"]; #TIME: F1 [label="@(1)"]; Index: tools/llvm-xray/xray-graph.h =================================================================== --- tools/llvm-xray/xray-graph.h +++ tools/llvm-xray/xray-graph.h @@ -17,6 +17,7 @@ #include #include +#include #include "func-id-helper.h" #include "xray-record.h" @@ -31,15 +32,21 @@ /// Graphs from them and then exporting those graphs for review. class GraphRenderer { public: - /// An inner struct for common timing statistics information + + /// 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 @@ -69,6 +76,9 @@ /// main graph. DenseMap VertexAttrs; + TimeStat GraphEdgeMax; + TimeStat GraphVertexMax; + struct FunctionAttr { int32_t FuncId; uint64_t TSC; @@ -88,6 +98,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 @@ -115,13 +126,14 @@ /// 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); + StatType EdgeLabel = StatType::NONE, + StatType EdgeColor = StatType::NONE, + StatType VertexLabel = StatType::NONE, + StatType VertexColor = StatType::NONE); }; } } Index: tools/llvm-xray/xray-graph.cc =================================================================== --- tools/llvm-xray/xray-graph.cc +++ tools/llvm-xray/xray-graph.cc @@ -15,6 +15,7 @@ #include #include #include +#include #include "xray-extract.h" #include "xray-graph.h" @@ -75,29 +76,101 @@ cl::desc("Alias for -deduce-sibling-calls"), cl::sub(Graph)); -static cl::opt - 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::opt GraphEdgeLabel("edge-label", + cl::desc("Output graphs with edges 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 GraphEdgeLabel2("e", cl::aliasopt(GraphEdgeLabel), cl::desc("Alias for -edge-label"), cl::sub(Graph)); +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(GraphEdgeLabel), + 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(GraphEdgeLabel), + cl::desc("Alias for -edge-label"), + cl::sub(Graph)); namespace { template T diff(T L, T R) { return std::max(L, R) - std::min(L, R); } @@ -186,11 +259,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); } } } @@ -216,72 +301,147 @@ P->Timings.end()); } getStats(TempTimings.begin(), TempTimings.end(), VertexAttrs[V.first].S); + updateMaxStats(VertexAttrs[V.first].S, GraphVertexMax); TempTimings.clear(); } -// Here is an alternative body of this function -#if 0 - DenseMap> VertexData; - for (auto &V : Graph) { - for (auto &E : V.second){ - auto &vect = VertexData[E.first]; - vect.insert(vect.end(), E.second.Timings.begin(), E.second.timings.end()); - } - } - for (auto &V: VertexData) - getStats(V.second.begin(), V.second.end(), VertexAttrs[V.first].S); -#endif } -void GraphRenderer::normaliseStatistics(double CycleFrequency) { - for (auto &V : Graph) { - for (auto &E : V.second) { - auto &S = E.second.S; +namespace { +// A Helper functio for Normalise Statistics which normalises a single +// TimeStat element. +void NormaliseTimeStat(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::normaliseStatistics(double CycleFrequency) { + for (auto &V : Graph) { + for (auto &E : V.second) { + auto &S = E.second.S; + NormaliseTimeStat(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; + NormaliseTimeStat(S,CycleFrequency); } + + NormaliseTimeStat(GraphEdgeMax, CycleFrequency); + NormaliseTimeStat(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(); } + +namespace{ + +// Evaluates a polynomial p(x) = a_0 + a_1*x^1 + ... a_n*x^n at x_0 using +// Horner's Method, and then returns the value as an 8-bit fixed point +// representation +// The Polynomial coefficients are parsed in such that begin contains a_n +// and following it are a_(n-1) ... in order. +template +uint8_t polyEval(const U &Begin, const U &End, double x_0){ + double B = 0; + for(U i = Begin; i!= End; ++i){ + B = *i + B*x_0; + } + double n = std::max(std::min(B,1.0),0.0); + return static_cast(255*n + 0.5); +} + +// Given a number between 0.0 and 1.0 returns a color from a gradient +// defined between these two points, the gradient is represented as a +// polynomial which is then evaluated at this point and scaled to an 24-bit +// RGB value which is then returned as a string. +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}; + using std::begin; + using std::end; + uint8_t r = polyEval(begin(RedPoly),end(RedPoly), point); + uint8_t g = polyEval(begin(GreenPoly),end(GreenPoly),point); + uint8_t b = polyEval(begin(BluePoly),end(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 annother 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); } // Does what the name suggests, it creates a DOT file from the Graph embedded in @@ -291,7 +451,7 @@ // // 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) @@ -299,21 +459,35 @@ 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) + for (const auto &V : VertexAttrs){ + const auto &VA = V.second; OS << "F" << V.first << " [label=\"" - << (V.second.SymbolName.size() > 40 - ? V.second.SymbolName.substr(0, 40) + "..." - : V.second.SymbolName) - << "\"];\n"; - + << (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"; } @@ -375,6 +549,8 @@ } } - GR.exportGraphAsDOT(OS, *Header, GraphEdgeLabel); + GR.exportGraphAsDOT(OS, *Header, + GraphEdgeLabel, GraphEdgeColorType, + GraphVertexLabel, GraphVertexColorType); return Error::success(); });