470 lines · cpp
1//===-- xray-graph-diff.cpp: XRay Function Call Graph Renderer ------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// Generate a DOT file to represent the function call graph encountered in10// the trace.11//12//===----------------------------------------------------------------------===//13#include <cassert>14#include <cmath>15#include <limits>16#include <string>17 18#include "xray-graph-diff.h"19#include "xray-graph.h"20#include "xray-registry.h"21 22#include "xray-color-helper.h"23#include "llvm/Support/FormatVariadic.h"24#include "llvm/Support/MemoryBuffer.h"25#include "llvm/XRay/Trace.h"26 27using namespace llvm;28using namespace xray;29 30static cl::SubCommand GraphDiff("graph-diff",31 "Generate diff of function-call graphs");32static cl::opt<std::string> GraphDiffInput1(cl::Positional,33 cl::desc("<xray log file 1>"),34 cl::Required, cl::sub(GraphDiff));35static cl::opt<std::string> GraphDiffInput2(cl::Positional,36 cl::desc("<xray log file 2>"),37 cl::Required, cl::sub(GraphDiff));38 39static cl::opt<bool>40 GraphDiffKeepGoing("keep-going",41 cl::desc("Keep going on errors encountered"),42 cl::sub(GraphDiff), cl::init(false));43static cl::alias GraphDiffKeepGoingA("k", cl::aliasopt(GraphDiffKeepGoing),44 cl::desc("Alias for -keep-going"));45static cl::opt<bool>46 GraphDiffKeepGoing1("keep-going-1",47 cl::desc("Keep going on errors encountered in trace 1"),48 cl::sub(GraphDiff), cl::init(false));49static cl::alias GraphDiffKeepGoing1A("k1", cl::aliasopt(GraphDiffKeepGoing1),50 cl::desc("Alias for -keep-going-1"));51static cl::opt<bool>52 GraphDiffKeepGoing2("keep-going-2",53 cl::desc("Keep going on errors encountered in trace 2"),54 cl::sub(GraphDiff), cl::init(false));55static cl::alias GraphDiffKeepGoing2A("k2", cl::aliasopt(GraphDiffKeepGoing2),56 cl::desc("Alias for -keep-going-2"));57 58static cl::opt<std::string>59 GraphDiffInstrMap("instr-map",60 cl::desc("binary with the instrumentation map, or "61 "a separate instrumentation map for graph"),62 cl::value_desc("binary with xray_instr_map or yaml"),63 cl::sub(GraphDiff), cl::init(""));64static cl::alias GraphDiffInstrMapA("m", cl::aliasopt(GraphDiffInstrMap),65 cl::desc("Alias for -instr-map"));66static cl::opt<std::string>67 GraphDiffInstrMap1("instr-map-1",68 cl::desc("binary with the instrumentation map, or "69 "a separate instrumentation map for graph 1"),70 cl::value_desc("binary with xray_instr_map or yaml"),71 cl::sub(GraphDiff), cl::init(""));72static cl::alias GraphDiffInstrMap1A("m1", cl::aliasopt(GraphDiffInstrMap1),73 cl::desc("Alias for -instr-map-1"));74static cl::opt<std::string>75 GraphDiffInstrMap2("instr-map-2",76 cl::desc("binary with the instrumentation map, or "77 "a separate instrumentation map for graph 2"),78 cl::value_desc("binary with xray_instr_map or yaml"),79 cl::sub(GraphDiff), cl::init(""));80static cl::alias GraphDiffInstrMap2A("m2", cl::aliasopt(GraphDiffInstrMap2),81 cl::desc("Alias for -instr-map-2"));82 83static cl::opt<bool> GraphDiffDeduceSiblingCalls(84 "deduce-sibling-calls",85 cl::desc("Deduce sibling calls when unrolling function call stacks"),86 cl::sub(GraphDiff), cl::init(false));87static cl::alias88 GraphDiffDeduceSiblingCallsA("d", cl::aliasopt(GraphDiffDeduceSiblingCalls),89 cl::desc("Alias for -deduce-sibling-calls"));90static cl::opt<bool> GraphDiffDeduceSiblingCalls1(91 "deduce-sibling-calls-1",92 cl::desc("Deduce sibling calls when unrolling function call stacks"),93 cl::sub(GraphDiff), cl::init(false));94static cl::alias GraphDiffDeduceSiblingCalls1A(95 "d1", cl::aliasopt(GraphDiffDeduceSiblingCalls1),96 cl::desc("Alias for -deduce-sibling-calls-1"));97static cl::opt<bool> GraphDiffDeduceSiblingCalls2(98 "deduce-sibling-calls-2",99 cl::desc("Deduce sibling calls when unrolling function call stacks"),100 cl::sub(GraphDiff), cl::init(false));101static cl::alias GraphDiffDeduceSiblingCalls2A(102 "d2", cl::aliasopt(GraphDiffDeduceSiblingCalls2),103 cl::desc("Alias for -deduce-sibling-calls-2"));104 105static cl::opt<GraphRenderer::StatType> GraphDiffEdgeLabel(106 "edge-label", cl::desc("Output graphs with edges labeled with this field"),107 cl::value_desc("field"), cl::sub(GraphDiff),108 cl::init(GraphRenderer::StatType::NONE),109 cl::values(clEnumValN(GraphRenderer::StatType::NONE, "none",110 "Do not label Edges"),111 clEnumValN(GraphRenderer::StatType::COUNT, "count",112 "function call counts"),113 clEnumValN(GraphRenderer::StatType::MIN, "min",114 "minimum function durations"),115 clEnumValN(GraphRenderer::StatType::MED, "med",116 "median function durations"),117 clEnumValN(GraphRenderer::StatType::PCT90, "90p",118 "90th percentile durations"),119 clEnumValN(GraphRenderer::StatType::PCT99, "99p",120 "99th percentile durations"),121 clEnumValN(GraphRenderer::StatType::MAX, "max",122 "maximum function durations"),123 clEnumValN(GraphRenderer::StatType::SUM, "sum",124 "sum of call durations")));125static cl::alias GraphDiffEdgeLabelA("e", cl::aliasopt(GraphDiffEdgeLabel),126 cl::desc("Alias for -edge-label"));127 128static cl::opt<GraphRenderer::StatType> GraphDiffEdgeColor(129 "edge-color", cl::desc("Output graphs with edges colored by this field"),130 cl::value_desc("field"), cl::sub(GraphDiff),131 cl::init(GraphRenderer::StatType::NONE),132 cl::values(clEnumValN(GraphRenderer::StatType::NONE, "none",133 "Do not color Edges"),134 clEnumValN(GraphRenderer::StatType::COUNT, "count",135 "function call counts"),136 clEnumValN(GraphRenderer::StatType::MIN, "min",137 "minimum function durations"),138 clEnumValN(GraphRenderer::StatType::MED, "med",139 "median function durations"),140 clEnumValN(GraphRenderer::StatType::PCT90, "90p",141 "90th percentile durations"),142 clEnumValN(GraphRenderer::StatType::PCT99, "99p",143 "99th percentile durations"),144 clEnumValN(GraphRenderer::StatType::MAX, "max",145 "maximum function durations"),146 clEnumValN(GraphRenderer::StatType::SUM, "sum",147 "sum of call durations")));148static cl::alias GraphDiffEdgeColorA("c", cl::aliasopt(GraphDiffEdgeColor),149 cl::desc("Alias for -edge-color"));150 151static cl::opt<GraphRenderer::StatType> GraphDiffVertexLabel(152 "vertex-label",153 cl::desc("Output graphs with vertices labeled with this field"),154 cl::value_desc("field"), cl::sub(GraphDiff),155 cl::init(GraphRenderer::StatType::NONE),156 cl::values(clEnumValN(GraphRenderer::StatType::NONE, "none",157 "Do not label Vertices"),158 clEnumValN(GraphRenderer::StatType::COUNT, "count",159 "function call counts"),160 clEnumValN(GraphRenderer::StatType::MIN, "min",161 "minimum function durations"),162 clEnumValN(GraphRenderer::StatType::MED, "med",163 "median function durations"),164 clEnumValN(GraphRenderer::StatType::PCT90, "90p",165 "90th percentile durations"),166 clEnumValN(GraphRenderer::StatType::PCT99, "99p",167 "99th percentile durations"),168 clEnumValN(GraphRenderer::StatType::MAX, "max",169 "maximum function durations"),170 clEnumValN(GraphRenderer::StatType::SUM, "sum",171 "sum of call durations")));172static cl::alias GraphDiffVertexLabelA("v", cl::aliasopt(GraphDiffVertexLabel),173 cl::desc("Alias for -vertex-label"));174 175static cl::opt<GraphRenderer::StatType> GraphDiffVertexColor(176 "vertex-color",177 cl::desc("Output graphs with vertices colored by this field"),178 cl::value_desc("field"), cl::sub(GraphDiff),179 cl::init(GraphRenderer::StatType::NONE),180 cl::values(clEnumValN(GraphRenderer::StatType::NONE, "none",181 "Do not color Vertices"),182 clEnumValN(GraphRenderer::StatType::COUNT, "count",183 "function call counts"),184 clEnumValN(GraphRenderer::StatType::MIN, "min",185 "minimum function durations"),186 clEnumValN(GraphRenderer::StatType::MED, "med",187 "median function durations"),188 clEnumValN(GraphRenderer::StatType::PCT90, "90p",189 "90th percentile durations"),190 clEnumValN(GraphRenderer::StatType::PCT99, "99p",191 "99th percentile durations"),192 clEnumValN(GraphRenderer::StatType::MAX, "max",193 "maximum function durations"),194 clEnumValN(GraphRenderer::StatType::SUM, "sum",195 "sum of call durations")));196static cl::alias GraphDiffVertexColorA("b", cl::aliasopt(GraphDiffVertexColor),197 cl::desc("Alias for -vertex-color"));198 199static cl::opt<int> GraphDiffVertexLabelTrunc(200 "vertex-label-trun", cl::desc("What length to truncate vertex labels to "),201 cl::sub(GraphDiff), cl::init(40));202static cl::alias203 GraphDiffVertexLabelTrunc1("t", cl::aliasopt(GraphDiffVertexLabelTrunc),204 cl::desc("Alias for -vertex-label-trun"));205 206static cl::opt<std::string>207 GraphDiffOutput("output", cl::value_desc("Output file"), cl::init("-"),208 cl::desc("output file; use '-' for stdout"),209 cl::sub(GraphDiff));210static cl::alias GraphDiffOutputA("o", cl::aliasopt(GraphDiffOutput),211 cl::desc("Alias for -output"));212 213Expected<GraphDiffRenderer> GraphDiffRenderer::Factory::getGraphDiffRenderer() {214 GraphDiffRenderer R;215 216 for (int i = 0; i < N; ++i) {217 const auto &G = this->G[i].get();218 for (const auto &V : G.vertices()) {219 const auto &VAttr = V.second;220 R.G[VAttr.SymbolName].CorrVertexPtr[i] = &V;221 }222 for (const auto &E : G.edges()) {223 auto &EdgeTailID = E.first.first;224 auto &EdgeHeadID = E.first.second;225 auto EdgeTailAttrOrErr = G.at(EdgeTailID);226 auto EdgeHeadAttrOrErr = G.at(EdgeHeadID);227 if (!EdgeTailAttrOrErr)228 return EdgeTailAttrOrErr.takeError();229 if (!EdgeHeadAttrOrErr)230 return EdgeHeadAttrOrErr.takeError();231 GraphT::EdgeIdentifier ID{EdgeTailAttrOrErr->SymbolName,232 EdgeHeadAttrOrErr->SymbolName};233 R.G[ID].CorrEdgePtr[i] = &E;234 }235 }236 237 return R;238}239 240// Returns the Relative change With respect to LeftStat between LeftStat241// and RightStat.242static double statRelDiff(const GraphDiffRenderer::TimeStat &LeftStat,243 const GraphDiffRenderer::TimeStat &RightStat,244 GraphDiffRenderer::StatType T) {245 double LeftAttr = LeftStat.getDouble(T);246 double RightAttr = RightStat.getDouble(T);247 248 return RightAttr / LeftAttr - 1.0;249}250 251static std::string getColor(const GraphDiffRenderer::GraphT::EdgeValueType &E,252 const GraphDiffRenderer::GraphT &G, ColorHelper H,253 GraphDiffRenderer::StatType T) {254 auto &EdgeAttr = E.second;255 if (EdgeAttr.CorrEdgePtr[0] == nullptr)256 return H.getColorString(2.0); // A number greater than 1.0257 if (EdgeAttr.CorrEdgePtr[1] == nullptr)258 return H.getColorString(-2.0); // A number less than -1.0259 260 if (T == GraphDiffRenderer::StatType::NONE)261 return H.getDefaultColorString();262 263 const auto &LeftStat = EdgeAttr.CorrEdgePtr[0]->second.S;264 const auto &RightStat = EdgeAttr.CorrEdgePtr[1]->second.S;265 266 double RelDiff = statRelDiff(LeftStat, RightStat, T);267 double CappedRelDiff = std::clamp(RelDiff, -1.0, 1.0);268 269 return H.getColorString(CappedRelDiff);270}271 272static std::string getColor(const GraphDiffRenderer::GraphT::VertexValueType &V,273 const GraphDiffRenderer::GraphT &G, ColorHelper H,274 GraphDiffRenderer::StatType T) {275 auto &VertexAttr = V.second;276 if (VertexAttr.CorrVertexPtr[0] == nullptr)277 return H.getColorString(2.0); // A number greater than 1.0278 if (VertexAttr.CorrVertexPtr[1] == nullptr)279 return H.getColorString(-2.0); // A number less than -1.0280 281 if (T == GraphDiffRenderer::StatType::NONE)282 return H.getDefaultColorString();283 284 const auto &LeftStat = VertexAttr.CorrVertexPtr[0]->second.S;285 const auto &RightStat = VertexAttr.CorrVertexPtr[1]->second.S;286 287 double RelDiff = statRelDiff(LeftStat, RightStat, T);288 double CappedRelDiff = std::clamp(RelDiff, -1.0, 1.0);289 290 return H.getColorString(CappedRelDiff);291}292 293static Twine truncateString(const StringRef &S, size_t n) {294 return (S.size() > n) ? Twine(S.substr(0, n)) + "..." : Twine(S);295}296 297template <typename T> static bool containsNullptr(const T &Collection) {298 return llvm::is_contained(Collection, nullptr);299}300 301static std::string getLabel(const GraphDiffRenderer::GraphT::EdgeValueType &E,302 GraphDiffRenderer::StatType EL) {303 auto &EdgeAttr = E.second;304 switch (EL) {305 case GraphDiffRenderer::StatType::NONE:306 return "";307 default:308 if (containsNullptr(EdgeAttr.CorrEdgePtr))309 return "";310 311 const auto &LeftStat = EdgeAttr.CorrEdgePtr[0]->second.S;312 const auto &RightStat = EdgeAttr.CorrEdgePtr[1]->second.S;313 314 double RelDiff = statRelDiff(LeftStat, RightStat, EL);315 return std::string(formatv(R"({0:P})", RelDiff));316 }317}318 319static std::string getLabel(const GraphDiffRenderer::GraphT::VertexValueType &V,320 GraphDiffRenderer::StatType VL, int TrunLen) {321 const auto &VertexId = V.first;322 const auto &VertexAttr = V.second;323 switch (VL) {324 case GraphDiffRenderer::StatType::NONE:325 return std::string(326 formatv(R"({0})", truncateString(VertexId, TrunLen).str()));327 default:328 if (containsNullptr(VertexAttr.CorrVertexPtr))329 return std::string(330 formatv(R"({0})", truncateString(VertexId, TrunLen).str()));331 332 const auto &LeftStat = VertexAttr.CorrVertexPtr[0]->second.S;333 const auto &RightStat = VertexAttr.CorrVertexPtr[1]->second.S;334 335 double RelDiff = statRelDiff(LeftStat, RightStat, VL);336 return std::string(formatv(337 R"({{{0}|{1:P}})", truncateString(VertexId, TrunLen).str(), RelDiff));338 }339}340 341static double getLineWidth(const GraphDiffRenderer::GraphT::EdgeValueType &E,342 GraphDiffRenderer::StatType EL) {343 auto &EdgeAttr = E.second;344 switch (EL) {345 case GraphDiffRenderer::StatType::NONE:346 return 1.0;347 default:348 if (containsNullptr(EdgeAttr.CorrEdgePtr))349 return 1.0;350 351 const auto &LeftStat = EdgeAttr.CorrEdgePtr[0]->second.S;352 const auto &RightStat = EdgeAttr.CorrEdgePtr[1]->second.S;353 354 double RelDiff = statRelDiff(LeftStat, RightStat, EL);355 return (RelDiff > 1.0) ? RelDiff : 1.0;356 }357}358 359void GraphDiffRenderer::exportGraphAsDOT(raw_ostream &OS, StatType EdgeLabel,360 StatType EdgeColor,361 StatType VertexLabel,362 StatType VertexColor, int TruncLen) {363 // Get numbering of vertices for dot output.364 StringMap<int32_t> VertexNo;365 366 int i = 0;367 for (const auto &V : G.vertices())368 VertexNo[V.first] = i++;369 370 ColorHelper H(ColorHelper::DivergingScheme::PiYG);371 372 OS << "digraph xrayDiff {\n";373 374 if (VertexLabel != StatType::NONE)375 OS << "node [shape=record]\n";376 377 for (const auto &E : G.edges()) {378 const auto &HeadId = E.first.first;379 const auto &TailId = E.first.second;380 OS << formatv(R"(F{0} -> F{1} [tooltip="{2} -> {3}" label="{4}" )"381 R"(color="{5}" labelfontcolor="{5}" penwidth={6}])"382 "\n",383 VertexNo[HeadId], VertexNo[TailId],384 HeadId.empty() ? static_cast<StringRef>("F0") : HeadId,385 TailId, getLabel(E, EdgeLabel), getColor(E, G, H, EdgeColor),386 getLineWidth(E, EdgeColor));387 }388 389 for (const auto &V : G.vertices()) {390 const auto &VertexId = V.first;391 if (VertexId.empty()) {392 OS << formatv(R"(F{0} [label="F0"])"393 "\n",394 VertexNo[VertexId]);395 continue;396 }397 OS << formatv(R"(F{0} [label="{1}" color="{2}"])"398 "\n",399 VertexNo[VertexId], getLabel(V, VertexLabel, TruncLen),400 getColor(V, G, H, VertexColor));401 }402 403 OS << "}\n";404}405 406template <typename T> static T &ifSpecified(T &A, cl::alias &AA, T &B) {407 if (A.getPosition() == 0 && AA.getPosition() == 0)408 return B;409 410 return A;411}412 413static CommandRegistration Unused(&GraphDiff, []() -> Error {414 std::array<GraphRenderer::Factory, 2> Factories{415 {{ifSpecified(GraphDiffKeepGoing1, GraphDiffKeepGoing1A,416 GraphDiffKeepGoing),417 ifSpecified(GraphDiffDeduceSiblingCalls1, GraphDiffDeduceSiblingCalls1A,418 GraphDiffDeduceSiblingCalls),419 ifSpecified(GraphDiffInstrMap1, GraphDiffInstrMap1A, GraphDiffInstrMap),420 Trace()},421 {ifSpecified(GraphDiffKeepGoing2, GraphDiffKeepGoing2A,422 GraphDiffKeepGoing),423 ifSpecified(GraphDiffDeduceSiblingCalls2, GraphDiffDeduceSiblingCalls2A,424 GraphDiffDeduceSiblingCalls),425 ifSpecified(GraphDiffInstrMap2, GraphDiffInstrMap2A, GraphDiffInstrMap),426 Trace()}}};427 428 std::array<std::string, 2> Inputs{{GraphDiffInput1, GraphDiffInput2}};429 430 std::array<GraphRenderer::GraphT, 2> Graphs;431 432 for (int i = 0; i < 2; i++) {433 auto TraceOrErr = loadTraceFile(Inputs[i], true);434 if (!TraceOrErr)435 return make_error<StringError>(436 Twine("Failed Loading Input File '") + Inputs[i] + "'",437 make_error_code(llvm::errc::invalid_argument));438 Factories[i].Trace = std::move(*TraceOrErr);439 440 auto GraphRendererOrErr = Factories[i].getGraphRenderer();441 442 if (!GraphRendererOrErr)443 return GraphRendererOrErr.takeError();444 445 auto GraphRenderer = *GraphRendererOrErr;446 447 Graphs[i] = GraphRenderer.getGraph();448 }449 450 GraphDiffRenderer::Factory DGF(Graphs[0], Graphs[1]);451 452 auto GDROrErr = DGF.getGraphDiffRenderer();453 if (!GDROrErr)454 return GDROrErr.takeError();455 456 auto &GDR = *GDROrErr;457 458 std::error_code EC;459 raw_fd_ostream OS(GraphDiffOutput, EC, sys::fs::OpenFlags::OF_TextWithCRLF);460 if (EC)461 return make_error<StringError>(462 Twine("Cannot open file '") + GraphDiffOutput + "' for writing.", EC);463 464 GDR.exportGraphAsDOT(OS, GraphDiffEdgeLabel, GraphDiffEdgeColor,465 GraphDiffVertexLabel, GraphDiffVertexColor,466 GraphDiffVertexLabelTrunc);467 468 return Error::success();469});470