tools/llvm-xray/xray-graph-diff.cpp

   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 });