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