//===-- xray-graph-diff.cpp: 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 #include #include #include #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 GraphDiffInput1(cl::Positional, cl::desc(""), cl::Required, cl::sub(GraphDiff)); static cl::opt GraphDiffInput2(cl::Positional, cl::desc(""), cl::Required, cl::sub(GraphDiff)); static cl::opt 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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::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 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 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("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 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 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 Inputs{{GraphDiffInput1, GraphDiffInput2}}; std::array Graphs; for (int i = 0; i < 2; i++) { auto TraceOrErr = loadTraceFile(Inputs[i], true); if (!TraceOrErr) return make_error( 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( Twine("Cannot open file '") + GraphDiffOutput + "' for writing.", EC); GDR.exportGraphAsDOT(OS, GraphDiffEdgeLabel, GraphDiffEdgeColor, GraphDiffVertexLabel, GraphDiffVertexColor, GraphDiffVertexLabelTrunc); return Error::success(); });