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