diff options
Diffstat (limited to 'tools/llvm-xray/xray-graph-diff.cc')
| -rw-r--r-- | tools/llvm-xray/xray-graph-diff.cc | 484 |
1 files changed, 484 insertions, 0 deletions
diff --git a/tools/llvm-xray/xray-graph-diff.cc b/tools/llvm-xray/xray-graph-diff.cc new file mode 100644 index 000000000000..3c69b3fb0751 --- /dev/null +++ b/tools/llvm-xray/xray-graph-diff.cc @@ -0,0 +1,484 @@ +//===-- xray-graph-diff.cc - 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 <cassert> +#include <cmath> +#include <limits> +#include <string> + +#include "xray-graph-diff.h" +#include "xray-graph.h" +#include "xray-registry.h" + +#include "xray-color-helper.h" +#include "llvm/ADT/iterator_range.h" +#include "llvm/Support/FormatVariadic.h" +#include "llvm/XRay/Trace.h" + +using namespace llvm; +using namespace xray; + +static cl::SubCommand GraphDiff("graph-diff", + "Generate diff of function-call graphs"); +static cl::opt<std::string> GraphDiffInput1(cl::Positional, + cl::desc("<xray log file 1>"), + cl::Required, cl::sub(GraphDiff)); +static cl::opt<std::string> GraphDiffInput2(cl::Positional, + cl::desc("<xray log file 2>"), + cl::Required, cl::sub(GraphDiff)); + +static cl::opt<bool> + GraphDiffKeepGoing("keep-going", + cl::desc("Keep going on errors encountered"), + cl::sub(GraphDiff), cl::init(false)); +static cl::alias GraphDiffKeepGoingA("k", cl::aliasopt(GraphDiffKeepGoing), + cl::desc("Alias for -keep-going"), + cl::sub(GraphDiff)); +static cl::opt<bool> + GraphDiffKeepGoing1("keep-going-1", + cl::desc("Keep going on errors encountered in trace 1"), + cl::sub(GraphDiff), cl::init(false)); +static cl::alias GraphDiffKeepGoing1A("k1", cl::aliasopt(GraphDiffKeepGoing1), + cl::desc("Alias for -keep-going-1"), + cl::sub(GraphDiff)); +static cl::opt<bool> + GraphDiffKeepGoing2("keep-going-2", + cl::desc("Keep going on errors encountered in trace 2"), + cl::sub(GraphDiff), cl::init(false)); +static cl::alias GraphDiffKeepGoing2A("k2", cl::aliasopt(GraphDiffKeepGoing2), + cl::desc("Alias for -keep-going-2"), + cl::sub(GraphDiff)); + +static cl::opt<std::string> + GraphDiffInstrMap("instr-map", + cl::desc("binary with the instrumentation map, or " + "a separate instrumentation map for graph"), + cl::value_desc("binary with xray_instr_map or yaml"), + cl::sub(GraphDiff), cl::init("")); +static cl::alias GraphDiffInstrMapA("m", cl::aliasopt(GraphDiffInstrMap), + cl::desc("Alias for -instr-map"), + cl::sub(GraphDiff)); +static cl::opt<std::string> + GraphDiffInstrMap1("instr-map-1", + cl::desc("binary with the instrumentation map, or " + "a separate instrumentation map for graph 1"), + cl::value_desc("binary with xray_instr_map or yaml"), + cl::sub(GraphDiff), cl::init("")); +static cl::alias GraphDiffInstrMap1A("m1", cl::aliasopt(GraphDiffInstrMap1), + cl::desc("Alias for -instr-map-1"), + cl::sub(GraphDiff)); +static cl::opt<std::string> + GraphDiffInstrMap2("instr-map-2", + cl::desc("binary with the instrumentation map, or " + "a separate instrumentation map for graph 2"), + cl::value_desc("binary with xray_instr_map or yaml"), + cl::sub(GraphDiff), cl::init("")); +static cl::alias GraphDiffInstrMap2A("m2", cl::aliasopt(GraphDiffInstrMap2), + cl::desc("Alias for -instr-map-2"), + cl::sub(GraphDiff)); + +static cl::opt<bool> GraphDiffDeduceSiblingCalls( + "deduce-sibling-calls", + cl::desc("Deduce sibling calls when unrolling function call stacks"), + cl::sub(GraphDiff), cl::init(false)); +static cl::alias + GraphDiffDeduceSiblingCallsA("d", cl::aliasopt(GraphDiffDeduceSiblingCalls), + cl::desc("Alias for -deduce-sibling-calls"), + cl::sub(GraphDiff)); +static cl::opt<bool> GraphDiffDeduceSiblingCalls1( + "deduce-sibling-calls-1", + cl::desc("Deduce sibling calls when unrolling function call stacks"), + cl::sub(GraphDiff), cl::init(false)); +static cl::alias GraphDiffDeduceSiblingCalls1A( + "d1", cl::aliasopt(GraphDiffDeduceSiblingCalls1), + cl::desc("Alias for -deduce-sibling-calls-1"), cl::sub(GraphDiff)); +static cl::opt<bool> GraphDiffDeduceSiblingCalls2( + "deduce-sibling-calls-2", + cl::desc("Deduce sibling calls when unrolling function call stacks"), + cl::sub(GraphDiff), cl::init(false)); +static cl::alias GraphDiffDeduceSiblingCalls2A( + "d2", cl::aliasopt(GraphDiffDeduceSiblingCalls2), + cl::desc("Alias for -deduce-sibling-calls-2"), cl::sub(GraphDiff)); + +static cl::opt<GraphRenderer::StatType> GraphDiffEdgeLabel( + "edge-label", cl::desc("Output graphs with edges labeled with this field"), + cl::value_desc("field"), cl::sub(GraphDiff), + 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 GraphDiffEdgeLabelA("e", cl::aliasopt(GraphDiffEdgeLabel), + cl::desc("Alias for -edge-label"), + cl::sub(GraphDiff)); + +static cl::opt<GraphRenderer::StatType> GraphDiffEdgeColor( + "edge-color", cl::desc("Output graphs with edges colored by this field"), + cl::value_desc("field"), cl::sub(GraphDiff), + cl::init(GraphRenderer::StatType::NONE), + cl::values(clEnumValN(GraphRenderer::StatType::NONE, "none", + "Do not color 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 GraphDiffEdgeColorA("c", cl::aliasopt(GraphDiffEdgeColor), + cl::desc("Alias for -edge-color"), + cl::sub(GraphDiff)); + +static cl::opt<GraphRenderer::StatType> GraphDiffVertexLabel( + "vertex-label", + cl::desc("Output graphs with vertices labeled with this field"), + cl::value_desc("field"), cl::sub(GraphDiff), + cl::init(GraphRenderer::StatType::NONE), + cl::values(clEnumValN(GraphRenderer::StatType::NONE, "none", + "Do not label Vertices"), + 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 GraphDiffVertexLabelA("v", cl::aliasopt(GraphDiffVertexLabel), + cl::desc("Alias for -vertex-label"), + cl::sub(GraphDiff)); + +static cl::opt<GraphRenderer::StatType> GraphDiffVertexColor( + "vertex-color", + cl::desc("Output graphs with vertices colored by this field"), + cl::value_desc("field"), cl::sub(GraphDiff), + cl::init(GraphRenderer::StatType::NONE), + cl::values(clEnumValN(GraphRenderer::StatType::NONE, "none", + "Do not color Vertices"), + 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 GraphDiffVertexColorA("b", cl::aliasopt(GraphDiffVertexColor), + cl::desc("Alias for -vertex-color"), + cl::sub(GraphDiff)); + +static cl::opt<int> GraphDiffVertexLabelTrunc( + "vertex-label-trun", cl::desc("What length to truncate vertex labels to "), + cl::sub(GraphDiff), cl::init(40)); +static cl::alias + GraphDiffVertexLabelTrunc1("t", cl::aliasopt(GraphDiffVertexLabelTrunc), + cl::desc("Alias for -vertex-label-trun"), + cl::sub(GraphDiff)); + +static cl::opt<std::string> + GraphDiffOutput("output", cl::value_desc("Output file"), cl::init("-"), + cl::desc("output file; use '-' for stdout"), + cl::sub(GraphDiff)); +static cl::alias GraphDiffOutputA("o", cl::aliasopt(GraphDiffOutput), + cl::desc("Alias for -output"), + cl::sub(GraphDiff)); + +Expected<GraphDiffRenderer> GraphDiffRenderer::Factory::getGraphDiffRenderer() { + GraphDiffRenderer R; + + for (int i = 0; i < N; ++i) { + const auto &G = this->G[i].get(); + for (const auto &V : G.vertices()) { + const auto &VAttr = V.second; + R.G[VAttr.SymbolName].CorrVertexPtr[i] = &V; + } + for (const auto &E : G.edges()) { + auto &EdgeTailID = E.first.first; + auto &EdgeHeadID = E.first.second; + auto EdgeTailAttrOrErr = G.at(EdgeTailID); + auto EdgeHeadAttrOrErr = G.at(EdgeHeadID); + if (!EdgeTailAttrOrErr) + return EdgeTailAttrOrErr.takeError(); + if (!EdgeHeadAttrOrErr) + return EdgeHeadAttrOrErr.takeError(); + GraphT::EdgeIdentifier ID{EdgeTailAttrOrErr->SymbolName, + EdgeHeadAttrOrErr->SymbolName}; + R.G[ID].CorrEdgePtr[i] = &E; + } + } + + return R; +} +// Returns the Relative change With respect to LeftStat between LeftStat +// and RightStat. +static double statRelDiff(const GraphDiffRenderer::TimeStat &LeftStat, + const GraphDiffRenderer::TimeStat &RightStat, + GraphDiffRenderer::StatType T) { + double LeftAttr = LeftStat.getDouble(T); + double RightAttr = RightStat.getDouble(T); + + return RightAttr / LeftAttr - 1.0; +} + +static std::string getColor(const GraphDiffRenderer::GraphT::EdgeValueType &E, + const GraphDiffRenderer::GraphT &G, ColorHelper H, + GraphDiffRenderer::StatType T) { + auto &EdgeAttr = E.second; + if (EdgeAttr.CorrEdgePtr[0] == nullptr) + return H.getColorString(2.0); // A number greater than 1.0 + if (EdgeAttr.CorrEdgePtr[1] == nullptr) + return H.getColorString(-2.0); // A number less than -1.0 + + if (T == GraphDiffRenderer::StatType::NONE) + return H.getDefaultColorString(); + + const auto &LeftStat = EdgeAttr.CorrEdgePtr[0]->second.S; + const auto &RightStat = EdgeAttr.CorrEdgePtr[1]->second.S; + + double RelDiff = statRelDiff(LeftStat, RightStat, T); + double CappedRelDiff = std::min(1.0, std::max(-1.0, RelDiff)); + + return H.getColorString(CappedRelDiff); +} + +static std::string getColor(const GraphDiffRenderer::GraphT::VertexValueType &V, + const GraphDiffRenderer::GraphT &G, ColorHelper H, + GraphDiffRenderer::StatType T) { + auto &VertexAttr = V.second; + if (VertexAttr.CorrVertexPtr[0] == nullptr) + return H.getColorString(2.0); // A number greater than 1.0 + if (VertexAttr.CorrVertexPtr[1] == nullptr) + return H.getColorString(-2.0); // A number less than -1.0 + + if (T == GraphDiffRenderer::StatType::NONE) + return H.getDefaultColorString(); + + const auto &LeftStat = VertexAttr.CorrVertexPtr[0]->second.S; + const auto &RightStat = VertexAttr.CorrVertexPtr[1]->second.S; + + double RelDiff = statRelDiff(LeftStat, RightStat, T); + double CappedRelDiff = std::min(1.0, std::max(-1.0, RelDiff)); + + return H.getColorString(CappedRelDiff); +} + +static Twine truncateString(const StringRef &S, size_t n) { + return (S.size() > n) ? Twine(S.substr(0, n)) + "..." : Twine(S); +} + +template <typename T> static bool containsNullptr(const T &Collection) { + for (const auto &E : Collection) + if (E == nullptr) + return true; + return false; +} + +static std::string getLabel(const GraphDiffRenderer::GraphT::EdgeValueType &E, + GraphDiffRenderer::StatType EL) { + auto &EdgeAttr = E.second; + switch (EL) { + case GraphDiffRenderer::StatType::NONE: + return ""; + default: + if (containsNullptr(EdgeAttr.CorrEdgePtr)) + return ""; + + const auto &LeftStat = EdgeAttr.CorrEdgePtr[0]->second.S; + const auto &RightStat = EdgeAttr.CorrEdgePtr[1]->second.S; + + double RelDiff = statRelDiff(LeftStat, RightStat, EL); + return formatv(R"({0:P})", RelDiff); + } +} + +static std::string getLabel(const GraphDiffRenderer::GraphT::VertexValueType &V, + GraphDiffRenderer::StatType VL, int TrunLen) { + const auto &VertexId = V.first; + const auto &VertexAttr = V.second; + switch (VL) { + case GraphDiffRenderer::StatType::NONE: + return formatv(R"({0})", truncateString(VertexId, TrunLen).str()); + default: + if (containsNullptr(VertexAttr.CorrVertexPtr)) + return formatv(R"({0})", truncateString(VertexId, TrunLen).str()); + + const auto &LeftStat = VertexAttr.CorrVertexPtr[0]->second.S; + const auto &RightStat = VertexAttr.CorrVertexPtr[1]->second.S; + + double RelDiff = statRelDiff(LeftStat, RightStat, VL); + return formatv(R"({{{0}|{1:P}})", truncateString(VertexId, TrunLen).str(), + RelDiff); + } +} + +static double getLineWidth(const GraphDiffRenderer::GraphT::EdgeValueType &E, + GraphDiffRenderer::StatType EL) { + auto &EdgeAttr = E.second; + switch (EL) { + case GraphDiffRenderer::StatType::NONE: + return 1.0; + default: + if (containsNullptr(EdgeAttr.CorrEdgePtr)) + return 1.0; + + const auto &LeftStat = EdgeAttr.CorrEdgePtr[0]->second.S; + const auto &RightStat = EdgeAttr.CorrEdgePtr[1]->second.S; + + double RelDiff = statRelDiff(LeftStat, RightStat, EL); + return (RelDiff > 1.0) ? RelDiff : 1.0; + } +} + +void GraphDiffRenderer::exportGraphAsDOT(raw_ostream &OS, StatType EdgeLabel, + StatType EdgeColor, + StatType VertexLabel, + StatType VertexColor, int TruncLen) { + // Get numbering of vertices for dot output. + StringMap<int32_t> VertexNo; + + int i = 0; + for (const auto &V : G.vertices()) { + VertexNo[V.first] = i++; + } + + ColorHelper H(ColorHelper::DivergingScheme::PiYG); + + OS << "digraph xrayDiff {\n"; + + if (VertexLabel != StatType::NONE) + OS << "node [shape=record]\n"; + + for (const auto &E : G.edges()) { + const auto &HeadId = E.first.first; + const auto &TailId = E.first.second; + OS << formatv(R"(F{0} -> F{1} [tooltip="{2} -> {3}" label="{4}" )" + R"(color="{5}" labelfontcolor="{5}" penwidth={6}])" + "\n", + VertexNo[HeadId], VertexNo[TailId], + (HeadId.equals("")) ? static_cast<StringRef>("F0") : HeadId, + TailId, getLabel(E, EdgeLabel), getColor(E, G, H, EdgeColor), + getLineWidth(E, EdgeColor)); + } + + for (const auto &V : G.vertices()) { + const auto &VertexId = V.first; + if (VertexId.equals("")) { + OS << formatv(R"(F{0} [label="F0"])" + "\n", + VertexNo[VertexId]); + continue; + } + OS << formatv(R"(F{0} [label="{1}" color="{2}"])" + "\n", + VertexNo[VertexId], getLabel(V, VertexLabel, TruncLen), + getColor(V, G, H, VertexColor)); + } + + OS << "}\n"; +} + +template <typename T> static T &ifSpecified(T &A, cl::alias &AA, T &B) { + if (A.getPosition() == 0 && AA.getPosition() == 0) + return B; + + return A; +} + +static CommandRegistration Unused(&GraphDiff, []() -> Error { + std::array<GraphRenderer::Factory, 2> Factories{ + {{ifSpecified(GraphDiffKeepGoing1, GraphDiffKeepGoing1A, + GraphDiffKeepGoing), + ifSpecified(GraphDiffDeduceSiblingCalls1, GraphDiffDeduceSiblingCalls1A, + GraphDiffDeduceSiblingCalls), + ifSpecified(GraphDiffInstrMap1, GraphDiffInstrMap1A, GraphDiffInstrMap), + Trace()}, + {ifSpecified(GraphDiffKeepGoing2, GraphDiffKeepGoing2A, + GraphDiffKeepGoing), + ifSpecified(GraphDiffDeduceSiblingCalls2, GraphDiffDeduceSiblingCalls2A, + GraphDiffDeduceSiblingCalls), + ifSpecified(GraphDiffInstrMap2, GraphDiffInstrMap2A, GraphDiffInstrMap), + Trace()}}}; + + std::array<std::string, 2> Inputs{{GraphDiffInput1, GraphDiffInput2}}; + + std::array<GraphRenderer::GraphT, 2> Graphs; + + for (int i = 0; i < 2; i++) { + auto TraceOrErr = loadTraceFile(Inputs[i], true); + if (!TraceOrErr) + return make_error<StringError>( + Twine("Failed Loading Input File '") + Inputs[i] + "'", + make_error_code(llvm::errc::invalid_argument)); + Factories[i].Trace = std::move(*TraceOrErr); + + auto GraphRendererOrErr = Factories[i].getGraphRenderer(); + + if (!GraphRendererOrErr) + return GraphRendererOrErr.takeError(); + + auto GraphRenderer = *GraphRendererOrErr; + + Graphs[i] = GraphRenderer.getGraph(); + } + + GraphDiffRenderer::Factory DGF(Graphs[0], Graphs[1]); + + auto GDROrErr = DGF.getGraphDiffRenderer(); + if (!GDROrErr) + return GDROrErr.takeError(); + + auto &GDR = *GDROrErr; + + std::error_code EC; + raw_fd_ostream OS(GraphDiffOutput, EC, sys::fs::OpenFlags::F_Text); + if (EC) + return make_error<StringError>( + Twine("Cannot open file '") + GraphDiffOutput + "' for writing.", EC); + + GDR.exportGraphAsDOT(OS, GraphDiffEdgeLabel, GraphDiffEdgeColor, + GraphDiffVertexLabel, GraphDiffVertexColor, + GraphDiffVertexLabelTrunc); + + return Error::success(); +}); |