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 static 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)); 49 static cl::alias GraphDiffKeepGoing1A("k1", cl::aliasopt(GraphDiffKeepGoing1), 50 cl::desc("Alias for -keep-going-1")); 51 static 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)); 55 static cl::alias GraphDiffKeepGoing2A("k2", cl::aliasopt(GraphDiffKeepGoing2), 56 cl::desc("Alias for -keep-going-2")); 57 58 static 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("")); 64 static cl::alias GraphDiffInstrMapA("m", cl::aliasopt(GraphDiffInstrMap), 65 cl::desc("Alias for -instr-map")); 66 static 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("")); 72 static cl::alias GraphDiffInstrMap1A("m1", cl::aliasopt(GraphDiffInstrMap1), 73 cl::desc("Alias for -instr-map-1")); 74 static 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("")); 80 static cl::alias GraphDiffInstrMap2A("m2", cl::aliasopt(GraphDiffInstrMap2), 81 cl::desc("Alias for -instr-map-2")); 82 83 static 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)); 87 static cl::alias 88 GraphDiffDeduceSiblingCallsA("d", cl::aliasopt(GraphDiffDeduceSiblingCalls), 89 cl::desc("Alias for -deduce-sibling-calls")); 90 static 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)); 94 static cl::alias GraphDiffDeduceSiblingCalls1A( 95 "d1", cl::aliasopt(GraphDiffDeduceSiblingCalls1), 96 cl::desc("Alias for -deduce-sibling-calls-1")); 97 static 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)); 101 static cl::alias GraphDiffDeduceSiblingCalls2A( 102 "d2", cl::aliasopt(GraphDiffDeduceSiblingCalls2), 103 cl::desc("Alias for -deduce-sibling-calls-2")); 104 105 static 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"))); 125 static cl::alias GraphDiffEdgeLabelA("e", cl::aliasopt(GraphDiffEdgeLabel), 126 cl::desc("Alias for -edge-label")); 127 128 static 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"))); 148 static cl::alias GraphDiffEdgeColorA("c", cl::aliasopt(GraphDiffEdgeColor), 149 cl::desc("Alias for -edge-color")); 150 151 static 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"))); 172 static cl::alias GraphDiffVertexLabelA("v", cl::aliasopt(GraphDiffVertexLabel), 173 cl::desc("Alias for -vertex-label")); 174 175 static 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"))); 196 static cl::alias GraphDiffVertexColorA("b", cl::aliasopt(GraphDiffVertexColor), 197 cl::desc("Alias for -vertex-color")); 198 199 static cl::opt<int> GraphDiffVertexLabelTrunc( 200 "vertex-label-trun", cl::desc("What length to truncate vertex labels to "), 201 cl::sub(GraphDiff), cl::init(40)); 202 static cl::alias 203 GraphDiffVertexLabelTrunc1("t", cl::aliasopt(GraphDiffVertexLabelTrunc), 204 cl::desc("Alias for -vertex-label-trun")); 205 206 static 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)); 210 static cl::alias GraphDiffOutputA("o", cl::aliasopt(GraphDiffOutput), 211 cl::desc("Alias for -output")); 212 213 Expected<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 // Returns the Relative change With respect to LeftStat between LeftStat 240 // and RightStat. 241 static double statRelDiff(const GraphDiffRenderer::TimeStat &LeftStat, 242 const GraphDiffRenderer::TimeStat &RightStat, 243 GraphDiffRenderer::StatType T) { 244 double LeftAttr = LeftStat.getDouble(T); 245 double RightAttr = RightStat.getDouble(T); 246 247 return RightAttr / LeftAttr - 1.0; 248 } 249 250 static std::string getColor(const GraphDiffRenderer::GraphT::EdgeValueType &E, 251 const GraphDiffRenderer::GraphT &G, ColorHelper H, 252 GraphDiffRenderer::StatType T) { 253 auto &EdgeAttr = E.second; 254 if (EdgeAttr.CorrEdgePtr[0] == nullptr) 255 return H.getColorString(2.0); // A number greater than 1.0 256 if (EdgeAttr.CorrEdgePtr[1] == nullptr) 257 return H.getColorString(-2.0); // A number less than -1.0 258 259 if (T == GraphDiffRenderer::StatType::NONE) 260 return H.getDefaultColorString(); 261 262 const auto &LeftStat = EdgeAttr.CorrEdgePtr[0]->second.S; 263 const auto &RightStat = EdgeAttr.CorrEdgePtr[1]->second.S; 264 265 double RelDiff = statRelDiff(LeftStat, RightStat, T); 266 double CappedRelDiff = std::min(1.0, std::max(-1.0, RelDiff)); 267 268 return H.getColorString(CappedRelDiff); 269 } 270 271 static std::string getColor(const GraphDiffRenderer::GraphT::VertexValueType &V, 272 const GraphDiffRenderer::GraphT &G, ColorHelper H, 273 GraphDiffRenderer::StatType T) { 274 auto &VertexAttr = V.second; 275 if (VertexAttr.CorrVertexPtr[0] == nullptr) 276 return H.getColorString(2.0); // A number greater than 1.0 277 if (VertexAttr.CorrVertexPtr[1] == nullptr) 278 return H.getColorString(-2.0); // A number less than -1.0 279 280 if (T == GraphDiffRenderer::StatType::NONE) 281 return H.getDefaultColorString(); 282 283 const auto &LeftStat = VertexAttr.CorrVertexPtr[0]->second.S; 284 const auto &RightStat = VertexAttr.CorrVertexPtr[1]->second.S; 285 286 double RelDiff = statRelDiff(LeftStat, RightStat, T); 287 double CappedRelDiff = std::min(1.0, std::max(-1.0, RelDiff)); 288 289 return H.getColorString(CappedRelDiff); 290 } 291 292 static Twine truncateString(const StringRef &S, size_t n) { 293 return (S.size() > n) ? Twine(S.substr(0, n)) + "..." : Twine(S); 294 } 295 296 template <typename T> static bool containsNullptr(const T &Collection) { 297 for (const auto &E : Collection) 298 if (E == nullptr) 299 return true; 300 return false; 301 } 302 303 static std::string getLabel(const GraphDiffRenderer::GraphT::EdgeValueType &E, 304 GraphDiffRenderer::StatType EL) { 305 auto &EdgeAttr = E.second; 306 switch (EL) { 307 case GraphDiffRenderer::StatType::NONE: 308 return ""; 309 default: 310 if (containsNullptr(EdgeAttr.CorrEdgePtr)) 311 return ""; 312 313 const auto &LeftStat = EdgeAttr.CorrEdgePtr[0]->second.S; 314 const auto &RightStat = EdgeAttr.CorrEdgePtr[1]->second.S; 315 316 double RelDiff = statRelDiff(LeftStat, RightStat, EL); 317 return std::string(formatv(R"({0:P})", RelDiff)); 318 } 319 } 320 321 static std::string getLabel(const GraphDiffRenderer::GraphT::VertexValueType &V, 322 GraphDiffRenderer::StatType VL, int TrunLen) { 323 const auto &VertexId = V.first; 324 const auto &VertexAttr = V.second; 325 switch (VL) { 326 case GraphDiffRenderer::StatType::NONE: 327 return std::string( 328 formatv(R"({0})", truncateString(VertexId, TrunLen).str())); 329 default: 330 if (containsNullptr(VertexAttr.CorrVertexPtr)) 331 return std::string( 332 formatv(R"({0})", truncateString(VertexId, TrunLen).str())); 333 334 const auto &LeftStat = VertexAttr.CorrVertexPtr[0]->second.S; 335 const auto &RightStat = VertexAttr.CorrVertexPtr[1]->second.S; 336 337 double RelDiff = statRelDiff(LeftStat, RightStat, VL); 338 return std::string(formatv( 339 R"({{{0}|{1:P}})", truncateString(VertexId, TrunLen).str(), RelDiff)); 340 } 341 } 342 343 static double getLineWidth(const GraphDiffRenderer::GraphT::EdgeValueType &E, 344 GraphDiffRenderer::StatType EL) { 345 auto &EdgeAttr = E.second; 346 switch (EL) { 347 case GraphDiffRenderer::StatType::NONE: 348 return 1.0; 349 default: 350 if (containsNullptr(EdgeAttr.CorrEdgePtr)) 351 return 1.0; 352 353 const auto &LeftStat = EdgeAttr.CorrEdgePtr[0]->second.S; 354 const auto &RightStat = EdgeAttr.CorrEdgePtr[1]->second.S; 355 356 double RelDiff = statRelDiff(LeftStat, RightStat, EL); 357 return (RelDiff > 1.0) ? RelDiff : 1.0; 358 } 359 } 360 361 void GraphDiffRenderer::exportGraphAsDOT(raw_ostream &OS, StatType EdgeLabel, 362 StatType EdgeColor, 363 StatType VertexLabel, 364 StatType VertexColor, int TruncLen) { 365 // Get numbering of vertices for dot output. 366 StringMap<int32_t> VertexNo; 367 368 int i = 0; 369 for (const auto &V : G.vertices()) { 370 VertexNo[V.first] = i++; 371 } 372 373 ColorHelper H(ColorHelper::DivergingScheme::PiYG); 374 375 OS << "digraph xrayDiff {\n"; 376 377 if (VertexLabel != StatType::NONE) 378 OS << "node [shape=record]\n"; 379 380 for (const auto &E : G.edges()) { 381 const auto &HeadId = E.first.first; 382 const auto &TailId = E.first.second; 383 OS << formatv(R"(F{0} -> F{1} [tooltip="{2} -> {3}" label="{4}" )" 384 R"(color="{5}" labelfontcolor="{5}" penwidth={6}])" 385 "\n", 386 VertexNo[HeadId], VertexNo[TailId], 387 (HeadId.equals("")) ? static_cast<StringRef>("F0") : HeadId, 388 TailId, getLabel(E, EdgeLabel), getColor(E, G, H, EdgeColor), 389 getLineWidth(E, EdgeColor)); 390 } 391 392 for (const auto &V : G.vertices()) { 393 const auto &VertexId = V.first; 394 if (VertexId.equals("")) { 395 OS << formatv(R"(F{0} [label="F0"])" 396 "\n", 397 VertexNo[VertexId]); 398 continue; 399 } 400 OS << formatv(R"(F{0} [label="{1}" color="{2}"])" 401 "\n", 402 VertexNo[VertexId], getLabel(V, VertexLabel, TruncLen), 403 getColor(V, G, H, VertexColor)); 404 } 405 406 OS << "}\n"; 407 } 408 409 template <typename T> static T &ifSpecified(T &A, cl::alias &AA, T &B) { 410 if (A.getPosition() == 0 && AA.getPosition() == 0) 411 return B; 412 413 return A; 414 } 415 416 static CommandRegistration Unused(&GraphDiff, []() -> Error { 417 std::array<GraphRenderer::Factory, 2> Factories{ 418 {{ifSpecified(GraphDiffKeepGoing1, GraphDiffKeepGoing1A, 419 GraphDiffKeepGoing), 420 ifSpecified(GraphDiffDeduceSiblingCalls1, GraphDiffDeduceSiblingCalls1A, 421 GraphDiffDeduceSiblingCalls), 422 ifSpecified(GraphDiffInstrMap1, GraphDiffInstrMap1A, GraphDiffInstrMap), 423 Trace()}, 424 {ifSpecified(GraphDiffKeepGoing2, GraphDiffKeepGoing2A, 425 GraphDiffKeepGoing), 426 ifSpecified(GraphDiffDeduceSiblingCalls2, GraphDiffDeduceSiblingCalls2A, 427 GraphDiffDeduceSiblingCalls), 428 ifSpecified(GraphDiffInstrMap2, GraphDiffInstrMap2A, GraphDiffInstrMap), 429 Trace()}}}; 430 431 std::array<std::string, 2> Inputs{{GraphDiffInput1, GraphDiffInput2}}; 432 433 std::array<GraphRenderer::GraphT, 2> Graphs; 434 435 for (int i = 0; i < 2; i++) { 436 auto TraceOrErr = loadTraceFile(Inputs[i], true); 437 if (!TraceOrErr) 438 return make_error<StringError>( 439 Twine("Failed Loading Input File '") + Inputs[i] + "'", 440 make_error_code(llvm::errc::invalid_argument)); 441 Factories[i].Trace = std::move(*TraceOrErr); 442 443 auto GraphRendererOrErr = Factories[i].getGraphRenderer(); 444 445 if (!GraphRendererOrErr) 446 return GraphRendererOrErr.takeError(); 447 448 auto GraphRenderer = *GraphRendererOrErr; 449 450 Graphs[i] = GraphRenderer.getGraph(); 451 } 452 453 GraphDiffRenderer::Factory DGF(Graphs[0], Graphs[1]); 454 455 auto GDROrErr = DGF.getGraphDiffRenderer(); 456 if (!GDROrErr) 457 return GDROrErr.takeError(); 458 459 auto &GDR = *GDROrErr; 460 461 std::error_code EC; 462 raw_fd_ostream OS(GraphDiffOutput, EC, sys::fs::OpenFlags::OF_Text); 463 if (EC) 464 return make_error<StringError>( 465 Twine("Cannot open file '") + GraphDiffOutput + "' for writing.", EC); 466 467 GDR.exportGraphAsDOT(OS, GraphDiffEdgeLabel, GraphDiffEdgeColor, 468 GraphDiffVertexLabel, GraphDiffVertexColor, 469 GraphDiffVertexLabelTrunc); 470 471 return Error::success(); 472 }); 473