llvm/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/Support/FormatVariadic.h"
  24 #include "llvm/Support/MemoryBuffer.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::clamp(RelDiff, -1.0, 1.0);
 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::clamp(RelDiff, -1.0, 1.0);
 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   return llvm::is_contained(Collection, nullptr);
 298 }
 299
 300 static std::string getLabel(const GraphDiffRenderer::GraphT::EdgeValueType &E,
 301                             GraphDiffRenderer::StatType EL) {
 302   auto &EdgeAttr = E.second;
 303   switch (EL) {
 304   case GraphDiffRenderer::StatType::NONE:
 305     return "";
 306   default:
 307     if (containsNullptr(EdgeAttr.CorrEdgePtr))
 308       return "";
 309
 310     const auto &LeftStat = EdgeAttr.CorrEdgePtr[0]->second.S;
 311     const auto &RightStat = EdgeAttr.CorrEdgePtr[1]->second.S;
 312
 313     double RelDiff = statRelDiff(LeftStat, RightStat, EL);
 314     return std::string(formatv(R"({0:P})", RelDiff));
 315   }
 316 }
 317
 318 static std::string getLabel(const GraphDiffRenderer::GraphT::VertexValueType &V,
 319                             GraphDiffRenderer::StatType VL, int TrunLen) {
 320   const auto &VertexId = V.first;
 321   const auto &VertexAttr = V.second;
 322   switch (VL) {
 323   case GraphDiffRenderer::StatType::NONE:
 324     return std::string(
 325         formatv(R"({0})", truncateString(VertexId, TrunLen).str()));
 326   default:
 327     if (containsNullptr(VertexAttr.CorrVertexPtr))
 328       return std::string(
 329           formatv(R"({0})", truncateString(VertexId, TrunLen).str()));
 330
 331     const auto &LeftStat = VertexAttr.CorrVertexPtr[0]->second.S;
 332     const auto &RightStat = VertexAttr.CorrVertexPtr[1]->second.S;
 333
 334     double RelDiff = statRelDiff(LeftStat, RightStat, VL);
 335     return std::string(formatv(
 336         R"({{{0}|{1:P}})", truncateString(VertexId, TrunLen).str(), RelDiff));
 337   }
 338 }
 339
 340 static double getLineWidth(const GraphDiffRenderer::GraphT::EdgeValueType &E,
 341                            GraphDiffRenderer::StatType EL) {
 342   auto &EdgeAttr = E.second;
 343   switch (EL) {
 344   case GraphDiffRenderer::StatType::NONE:
 345     return 1.0;
 346   default:
 347     if (containsNullptr(EdgeAttr.CorrEdgePtr))
 348       return 1.0;
 349
 350     const auto &LeftStat = EdgeAttr.CorrEdgePtr[0]->second.S;
 351     const auto &RightStat = EdgeAttr.CorrEdgePtr[1]->second.S;
 352
 353     double RelDiff = statRelDiff(LeftStat, RightStat, EL);
 354     return (RelDiff > 1.0) ? RelDiff : 1.0;
 355   }
 356 }
 357
 358 void GraphDiffRenderer::exportGraphAsDOT(raw_ostream &OS, StatType EdgeLabel,
 359                                          StatType EdgeColor,
 360                                          StatType VertexLabel,
 361                                          StatType VertexColor, int TruncLen) {
 362   // Get numbering of vertices for dot output.
 363   StringMap<int32_t> VertexNo;
 364
 365   int i = 0;
 366   for (const auto &V : G.vertices()) {
 367     VertexNo[V.first] = i++;
 368   }
 369
 370   ColorHelper H(ColorHelper::DivergingScheme::PiYG);
 371
 372   OS << "digraph xrayDiff {\n";
 373
 374   if (VertexLabel != StatType::NONE)
 375     OS << "node [shape=record]\n";
 376
 377   for (const auto &E : G.edges()) {
 378     const auto &HeadId = E.first.first;
 379     const auto &TailId = E.first.second;
 380     OS << formatv(R"(F{0} -> F{1} [tooltip="{2} -> {3}" label="{4}" )"
 381                   R"(color="{5}" labelfontcolor="{5}" penwidth={6}])"
 382                   "\n",
 383                   VertexNo[HeadId], VertexNo[TailId],
 384                   (HeadId.equals("")) ? static_cast<StringRef>("F0") : HeadId,
 385                   TailId, getLabel(E, EdgeLabel), getColor(E, G, H, EdgeColor),
 386                   getLineWidth(E, EdgeColor));
 387   }
 388
 389   for (const auto &V : G.vertices()) {
 390     const auto &VertexId = V.first;
 391     if (VertexId.equals("")) {
 392       OS << formatv(R"(F{0} [label="F0"])"
 393                     "\n",
 394                     VertexNo[VertexId]);
 395       continue;
 396     }
 397     OS << formatv(R"(F{0} [label="{1}" color="{2}"])"
 398                   "\n",
 399                   VertexNo[VertexId], getLabel(V, VertexLabel, TruncLen),
 400                   getColor(V, G, H, VertexColor));
 401   }
 402
 403   OS << "}\n";
 404 }
 405
 406 template <typename T> static T &ifSpecified(T &A, cl::alias &AA, T &B) {
 407   if (A.getPosition() == 0 && AA.getPosition() == 0)
 408     return B;
 409
 410   return A;
 411 }
 412
 413 static CommandRegistration Unused(&GraphDiff, []() -> Error {
 414   std::array<GraphRenderer::Factory, 2> Factories{
 415       {{ifSpecified(GraphDiffKeepGoing1, GraphDiffKeepGoing1A,
 416                     GraphDiffKeepGoing),
 417         ifSpecified(GraphDiffDeduceSiblingCalls1, GraphDiffDeduceSiblingCalls1A,
 418                     GraphDiffDeduceSiblingCalls),
 419         ifSpecified(GraphDiffInstrMap1, GraphDiffInstrMap1A, GraphDiffInstrMap),
 420         Trace()},
 421        {ifSpecified(GraphDiffKeepGoing2, GraphDiffKeepGoing2A,
 422                     GraphDiffKeepGoing),
 423         ifSpecified(GraphDiffDeduceSiblingCalls2, GraphDiffDeduceSiblingCalls2A,
 424                     GraphDiffDeduceSiblingCalls),
 425         ifSpecified(GraphDiffInstrMap2, GraphDiffInstrMap2A, GraphDiffInstrMap),
 426         Trace()}}};
 427
 428   std::array<std::string, 2> Inputs{{GraphDiffInput1, GraphDiffInput2}};
 429
 430   std::array<GraphRenderer::GraphT, 2> Graphs;
 431
 432   for (int i = 0; i < 2; i++) {
 433     auto TraceOrErr = loadTraceFile(Inputs[i], true);
 434     if (!TraceOrErr)
 435       return make_error<StringError>(
 436           Twine("Failed Loading Input File '") + Inputs[i] + "'",
 437           make_error_code(llvm::errc::invalid_argument));
 438     Factories[i].Trace = std::move(*TraceOrErr);
 439
 440     auto GraphRendererOrErr = Factories[i].getGraphRenderer();
 441
 442     if (!GraphRendererOrErr)
 443       return GraphRendererOrErr.takeError();
 444
 445     auto GraphRenderer = *GraphRendererOrErr;
 446
 447     Graphs[i] = GraphRenderer.getGraph();
 448   }
 449
 450   GraphDiffRenderer::Factory DGF(Graphs[0], Graphs[1]);
 451
 452   auto GDROrErr = DGF.getGraphDiffRenderer();
 453   if (!GDROrErr)
 454     return GDROrErr.takeError();
 455
 456   auto &GDR = *GDROrErr;
 457
 458   std::error_code EC;
 459   raw_fd_ostream OS(GraphDiffOutput, EC, sys::fs::OpenFlags::OF_TextWithCRLF);
 460   if (EC)
 461     return make_error<StringError>(
 462         Twine("Cannot open file '") + GraphDiffOutput + "' for writing.", EC);
 463
 464   GDR.exportGraphAsDOT(OS, GraphDiffEdgeLabel, GraphDiffEdgeColor,
 465                        GraphDiffVertexLabel, GraphDiffVertexColor,
 466                        GraphDiffVertexLabelTrunc);
 467
 468   return Error::success();
 469 });