tools/llvm-xray/xray-graph-diff.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-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::OF_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 });