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/Support/MemoryBuffer.h" 26 #include "llvm/XRay/Trace.h" 27 28 using namespace llvm; 29 using namespace xray; 30 31 static cl::SubCommand GraphDiff("graph-diff", 32 "Generate diff of function-call graphs"); 33 static cl::opt<std::string> GraphDiffInput1(cl::Positional, 34 cl::desc("<xray log file 1>"), 35 cl::Required, cl::sub(GraphDiff)); 36 static cl::opt<std::string> GraphDiffInput2(cl::Positional, 37 cl::desc("<xray log file 2>"), 38 cl::Required, cl::sub(GraphDiff)); 39 40 static cl::opt<bool> 41 GraphDiffKeepGoing("keep-going", 42 cl::desc("Keep going on errors encountered"), 43 cl::sub(GraphDiff), cl::init(false)); 44 static cl::alias GraphDiffKeepGoingA("k", cl::aliasopt(GraphDiffKeepGoing), 45 cl::desc("Alias for -keep-going")); 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 static cl::opt<bool> 53 GraphDiffKeepGoing2("keep-going-2", 54 cl::desc("Keep going on errors encountered in trace 2"), 55 cl::sub(GraphDiff), cl::init(false)); 56 static cl::alias GraphDiffKeepGoing2A("k2", cl::aliasopt(GraphDiffKeepGoing2), 57 cl::desc("Alias for -keep-going-2")); 58 59 static cl::opt<std::string> 60 GraphDiffInstrMap("instr-map", 61 cl::desc("binary with the instrumentation map, or " 62 "a separate instrumentation map for graph"), 63 cl::value_desc("binary with xray_instr_map or yaml"), 64 cl::sub(GraphDiff), cl::init("")); 65 static cl::alias GraphDiffInstrMapA("m", cl::aliasopt(GraphDiffInstrMap), 66 cl::desc("Alias for -instr-map")); 67 static cl::opt<std::string> 68 GraphDiffInstrMap1("instr-map-1", 69 cl::desc("binary with the instrumentation map, or " 70 "a separate instrumentation map for graph 1"), 71 cl::value_desc("binary with xray_instr_map or yaml"), 72 cl::sub(GraphDiff), cl::init("")); 73 static cl::alias GraphDiffInstrMap1A("m1", cl::aliasopt(GraphDiffInstrMap1), 74 cl::desc("Alias for -instr-map-1")); 75 static cl::opt<std::string> 76 GraphDiffInstrMap2("instr-map-2", 77 cl::desc("binary with the instrumentation map, or " 78 "a separate instrumentation map for graph 2"), 79 cl::value_desc("binary with xray_instr_map or yaml"), 80 cl::sub(GraphDiff), cl::init("")); 81 static cl::alias GraphDiffInstrMap2A("m2", cl::aliasopt(GraphDiffInstrMap2), 82 cl::desc("Alias for -instr-map-2")); 83 84 static cl::opt<bool> GraphDiffDeduceSiblingCalls( 85 "deduce-sibling-calls", 86 cl::desc("Deduce sibling calls when unrolling function call stacks"), 87 cl::sub(GraphDiff), cl::init(false)); 88 static cl::alias 89 GraphDiffDeduceSiblingCallsA("d", cl::aliasopt(GraphDiffDeduceSiblingCalls), 90 cl::desc("Alias for -deduce-sibling-calls")); 91 static cl::opt<bool> GraphDiffDeduceSiblingCalls1( 92 "deduce-sibling-calls-1", 93 cl::desc("Deduce sibling calls when unrolling function call stacks"), 94 cl::sub(GraphDiff), cl::init(false)); 95 static cl::alias GraphDiffDeduceSiblingCalls1A( 96 "d1", cl::aliasopt(GraphDiffDeduceSiblingCalls1), 97 cl::desc("Alias for -deduce-sibling-calls-1")); 98 static cl::opt<bool> GraphDiffDeduceSiblingCalls2( 99 "deduce-sibling-calls-2", 100 cl::desc("Deduce sibling calls when unrolling function call stacks"), 101 cl::sub(GraphDiff), cl::init(false)); 102 static cl::alias GraphDiffDeduceSiblingCalls2A( 103 "d2", cl::aliasopt(GraphDiffDeduceSiblingCalls2), 104 cl::desc("Alias for -deduce-sibling-calls-2")); 105 106 static cl::opt<GraphRenderer::StatType> GraphDiffEdgeLabel( 107 "edge-label", cl::desc("Output graphs with edges labeled with this field"), 108 cl::value_desc("field"), cl::sub(GraphDiff), 109 cl::init(GraphRenderer::StatType::NONE), 110 cl::values(clEnumValN(GraphRenderer::StatType::NONE, "none", 111 "Do not label Edges"), 112 clEnumValN(GraphRenderer::StatType::COUNT, "count", 113 "function call counts"), 114 clEnumValN(GraphRenderer::StatType::MIN, "min", 115 "minimum function durations"), 116 clEnumValN(GraphRenderer::StatType::MED, "med", 117 "median function durations"), 118 clEnumValN(GraphRenderer::StatType::PCT90, "90p", 119 "90th percentile durations"), 120 clEnumValN(GraphRenderer::StatType::PCT99, "99p", 121 "99th percentile durations"), 122 clEnumValN(GraphRenderer::StatType::MAX, "max", 123 "maximum function durations"), 124 clEnumValN(GraphRenderer::StatType::SUM, "sum", 125 "sum of call durations"))); 126 static cl::alias GraphDiffEdgeLabelA("e", cl::aliasopt(GraphDiffEdgeLabel), 127 cl::desc("Alias for -edge-label")); 128 129 static cl::opt<GraphRenderer::StatType> GraphDiffEdgeColor( 130 "edge-color", cl::desc("Output graphs with edges colored by this field"), 131 cl::value_desc("field"), cl::sub(GraphDiff), 132 cl::init(GraphRenderer::StatType::NONE), 133 cl::values(clEnumValN(GraphRenderer::StatType::NONE, "none", 134 "Do not color Edges"), 135 clEnumValN(GraphRenderer::StatType::COUNT, "count", 136 "function call counts"), 137 clEnumValN(GraphRenderer::StatType::MIN, "min", 138 "minimum function durations"), 139 clEnumValN(GraphRenderer::StatType::MED, "med", 140 "median function durations"), 141 clEnumValN(GraphRenderer::StatType::PCT90, "90p", 142 "90th percentile durations"), 143 clEnumValN(GraphRenderer::StatType::PCT99, "99p", 144 "99th percentile durations"), 145 clEnumValN(GraphRenderer::StatType::MAX, "max", 146 "maximum function durations"), 147 clEnumValN(GraphRenderer::StatType::SUM, "sum", 148 "sum of call durations"))); 149 static cl::alias GraphDiffEdgeColorA("c", cl::aliasopt(GraphDiffEdgeColor), 150 cl::desc("Alias for -edge-color")); 151 152 static cl::opt<GraphRenderer::StatType> GraphDiffVertexLabel( 153 "vertex-label", 154 cl::desc("Output graphs with vertices labeled with this field"), 155 cl::value_desc("field"), cl::sub(GraphDiff), 156 cl::init(GraphRenderer::StatType::NONE), 157 cl::values(clEnumValN(GraphRenderer::StatType::NONE, "none", 158 "Do not label Vertices"), 159 clEnumValN(GraphRenderer::StatType::COUNT, "count", 160 "function call counts"), 161 clEnumValN(GraphRenderer::StatType::MIN, "min", 162 "minimum function durations"), 163 clEnumValN(GraphRenderer::StatType::MED, "med", 164 "median function durations"), 165 clEnumValN(GraphRenderer::StatType::PCT90, "90p", 166 "90th percentile durations"), 167 clEnumValN(GraphRenderer::StatType::PCT99, "99p", 168 "99th percentile durations"), 169 clEnumValN(GraphRenderer::StatType::MAX, "max", 170 "maximum function durations"), 171 clEnumValN(GraphRenderer::StatType::SUM, "sum", 172 "sum of call durations"))); 173 static cl::alias GraphDiffVertexLabelA("v", cl::aliasopt(GraphDiffVertexLabel), 174 cl::desc("Alias for -vertex-label")); 175 176 static cl::opt<GraphRenderer::StatType> GraphDiffVertexColor( 177 "vertex-color", 178 cl::desc("Output graphs with vertices colored by this field"), 179 cl::value_desc("field"), cl::sub(GraphDiff), 180 cl::init(GraphRenderer::StatType::NONE), 181 cl::values(clEnumValN(GraphRenderer::StatType::NONE, "none", 182 "Do not color Vertices"), 183 clEnumValN(GraphRenderer::StatType::COUNT, "count", 184 "function call counts"), 185 clEnumValN(GraphRenderer::StatType::MIN, "min", 186 "minimum function durations"), 187 clEnumValN(GraphRenderer::StatType::MED, "med", 188 "median function durations"), 189 clEnumValN(GraphRenderer::StatType::PCT90, "90p", 190 "90th percentile durations"), 191 clEnumValN(GraphRenderer::StatType::PCT99, "99p", 192 "99th percentile durations"), 193 clEnumValN(GraphRenderer::StatType::MAX, "max", 194 "maximum function durations"), 195 clEnumValN(GraphRenderer::StatType::SUM, "sum", 196 "sum of call durations"))); 197 static cl::alias GraphDiffVertexColorA("b", cl::aliasopt(GraphDiffVertexColor), 198 cl::desc("Alias for -vertex-color")); 199 200 static cl::opt<int> GraphDiffVertexLabelTrunc( 201 "vertex-label-trun", cl::desc("What length to truncate vertex labels to "), 202 cl::sub(GraphDiff), cl::init(40)); 203 static cl::alias 204 GraphDiffVertexLabelTrunc1("t", cl::aliasopt(GraphDiffVertexLabelTrunc), 205 cl::desc("Alias for -vertex-label-trun")); 206 207 static cl::opt<std::string> 208 GraphDiffOutput("output", cl::value_desc("Output file"), cl::init("-"), 209 cl::desc("output file; use '-' for stdout"), 210 cl::sub(GraphDiff)); 211 static cl::alias GraphDiffOutputA("o", cl::aliasopt(GraphDiffOutput), 212 cl::desc("Alias for -output")); 213 214 Expected<GraphDiffRenderer> GraphDiffRenderer::Factory::getGraphDiffRenderer() { 215 GraphDiffRenderer R; 216 217 for (int i = 0; i < N; ++i) { 218 const auto &G = this->G[i].get(); 219 for (const auto &V : G.vertices()) { 220 const auto &VAttr = V.second; 221 R.G[VAttr.SymbolName].CorrVertexPtr[i] = &V; 222 } 223 for (const auto &E : G.edges()) { 224 auto &EdgeTailID = E.first.first; 225 auto &EdgeHeadID = E.first.second; 226 auto EdgeTailAttrOrErr = G.at(EdgeTailID); 227 auto EdgeHeadAttrOrErr = G.at(EdgeHeadID); 228 if (!EdgeTailAttrOrErr) 229 return EdgeTailAttrOrErr.takeError(); 230 if (!EdgeHeadAttrOrErr) 231 return EdgeHeadAttrOrErr.takeError(); 232 GraphT::EdgeIdentifier ID{EdgeTailAttrOrErr->SymbolName, 233 EdgeHeadAttrOrErr->SymbolName}; 234 R.G[ID].CorrEdgePtr[i] = &E; 235 } 236 } 237 238 return R; 239 } 240 // Returns the Relative change With respect to LeftStat between LeftStat 241 // and RightStat. 242 static 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 251 static 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.0 257 if (EdgeAttr.CorrEdgePtr[1] == nullptr) 258 return H.getColorString(-2.0); // A number less than -1.0 259 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 272 static 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.0 278 if (VertexAttr.CorrVertexPtr[1] == nullptr) 279 return H.getColorString(-2.0); // A number less than -1.0 280 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 293 static Twine truncateString(const StringRef &S, size_t n) { 294 return (S.size() > n) ? Twine(S.substr(0, n)) + "..." : Twine(S); 295 } 296 297 template <typename T> static bool containsNullptr(const T &Collection) { 298 return llvm::is_contained(Collection, nullptr); 299 } 300 301 static 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 319 static 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 341 static 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 359 void 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 371 ColorHelper H(ColorHelper::DivergingScheme::PiYG); 372 373 OS << "digraph xrayDiff {\n"; 374 375 if (VertexLabel != StatType::NONE) 376 OS << "node [shape=record]\n"; 377 378 for (const auto &E : G.edges()) { 379 const auto &HeadId = E.first.first; 380 const auto &TailId = E.first.second; 381 OS << formatv(R"(F{0} -> F{1} [tooltip="{2} -> {3}" label="{4}" )" 382 R"(color="{5}" labelfontcolor="{5}" penwidth={6}])" 383 "\n", 384 VertexNo[HeadId], VertexNo[TailId], 385 (HeadId.equals("")) ? static_cast<StringRef>("F0") : HeadId, 386 TailId, getLabel(E, EdgeLabel), getColor(E, G, H, EdgeColor), 387 getLineWidth(E, EdgeColor)); 388 } 389 390 for (const auto &V : G.vertices()) { 391 const auto &VertexId = V.first; 392 if (VertexId.equals("")) { 393 OS << formatv(R"(F{0} [label="F0"])" 394 "\n", 395 VertexNo[VertexId]); 396 continue; 397 } 398 OS << formatv(R"(F{0} [label="{1}" color="{2}"])" 399 "\n", 400 VertexNo[VertexId], getLabel(V, VertexLabel, TruncLen), 401 getColor(V, G, H, VertexColor)); 402 } 403 404 OS << "}\n"; 405 } 406 407 template <typename T> static T &ifSpecified(T &A, cl::alias &AA, T &B) { 408 if (A.getPosition() == 0 && AA.getPosition() == 0) 409 return B; 410 411 return A; 412 } 413 414 static CommandRegistration Unused(&GraphDiff, []() -> Error { 415 std::array<GraphRenderer::Factory, 2> Factories{ 416 {{ifSpecified(GraphDiffKeepGoing1, GraphDiffKeepGoing1A, 417 GraphDiffKeepGoing), 418 ifSpecified(GraphDiffDeduceSiblingCalls1, GraphDiffDeduceSiblingCalls1A, 419 GraphDiffDeduceSiblingCalls), 420 ifSpecified(GraphDiffInstrMap1, GraphDiffInstrMap1A, GraphDiffInstrMap), 421 Trace()}, 422 {ifSpecified(GraphDiffKeepGoing2, GraphDiffKeepGoing2A, 423 GraphDiffKeepGoing), 424 ifSpecified(GraphDiffDeduceSiblingCalls2, GraphDiffDeduceSiblingCalls2A, 425 GraphDiffDeduceSiblingCalls), 426 ifSpecified(GraphDiffInstrMap2, GraphDiffInstrMap2A, GraphDiffInstrMap), 427 Trace()}}}; 428 429 std::array<std::string, 2> Inputs{{GraphDiffInput1, GraphDiffInput2}}; 430 431 std::array<GraphRenderer::GraphT, 2> Graphs; 432 433 for (int i = 0; i < 2; i++) { 434 auto TraceOrErr = loadTraceFile(Inputs[i], true); 435 if (!TraceOrErr) 436 return make_error<StringError>( 437 Twine("Failed Loading Input File '") + Inputs[i] + "'", 438 make_error_code(llvm::errc::invalid_argument)); 439 Factories[i].Trace = std::move(*TraceOrErr); 440 441 auto GraphRendererOrErr = Factories[i].getGraphRenderer(); 442 443 if (!GraphRendererOrErr) 444 return GraphRendererOrErr.takeError(); 445 446 auto GraphRenderer = *GraphRendererOrErr; 447 448 Graphs[i] = GraphRenderer.getGraph(); 449 } 450 451 GraphDiffRenderer::Factory DGF(Graphs[0], Graphs[1]); 452 453 auto GDROrErr = DGF.getGraphDiffRenderer(); 454 if (!GDROrErr) 455 return GDROrErr.takeError(); 456 457 auto &GDR = *GDROrErr; 458 459 std::error_code EC; 460 raw_fd_ostream OS(GraphDiffOutput, EC, sys::fs::OpenFlags::OF_TextWithCRLF); 461 if (EC) 462 return make_error<StringError>( 463 Twine("Cannot open file '") + GraphDiffOutput + "' for writing.", EC); 464 465 GDR.exportGraphAsDOT(OS, GraphDiffEdgeLabel, GraphDiffEdgeColor, 466 GraphDiffVertexLabel, GraphDiffVertexColor, 467 GraphDiffVertexLabelTrunc); 468 469 return Error::success(); 470 }); 471