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
27using namespace llvm;
28using namespace xray;
29
30static cl::SubCommand GraphDiff("graph-diff",
31                                "Generate diff of function-call graphs");
32static cl::opt<std::string> GraphDiffInput1(cl::Positional,
33                                            cl::desc("<xray log file 1>"),
34                                            cl::Required, cl::sub(GraphDiff));
35static cl::opt<std::string> GraphDiffInput2(cl::Positional,
36                                            cl::desc("<xray log file 2>"),
37                                            cl::Required, cl::sub(GraphDiff));
38
39static cl::opt<bool>
40    GraphDiffKeepGoing("keep-going",
41                       cl::desc("Keep going on errors encountered"),
42                       cl::sub(GraphDiff), cl::init(false));
43static cl::alias GraphDiffKeepGoingA("k", cl::aliasopt(GraphDiffKeepGoing),
44                                     cl::desc("Alias for -keep-going"));
45static 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));
49static cl::alias GraphDiffKeepGoing1A("k1", cl::aliasopt(GraphDiffKeepGoing1),
50                                      cl::desc("Alias for -keep-going-1"));
51static 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));
55static cl::alias GraphDiffKeepGoing2A("k2", cl::aliasopt(GraphDiffKeepGoing2),
56                                      cl::desc("Alias for -keep-going-2"));
57
58static 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(""));
64static cl::alias GraphDiffInstrMapA("m", cl::aliasopt(GraphDiffInstrMap),
65                                    cl::desc("Alias for -instr-map"));
66static 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(""));
72static cl::alias GraphDiffInstrMap1A("m1", cl::aliasopt(GraphDiffInstrMap1),
73                                     cl::desc("Alias for -instr-map-1"));
74static 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(""));
80static cl::alias GraphDiffInstrMap2A("m2", cl::aliasopt(GraphDiffInstrMap2),
81                                     cl::desc("Alias for -instr-map-2"));
82
83static 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));
87static cl::alias
88    GraphDiffDeduceSiblingCallsA("d", cl::aliasopt(GraphDiffDeduceSiblingCalls),
89                                 cl::desc("Alias for -deduce-sibling-calls"));
90static 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));
94static cl::alias GraphDiffDeduceSiblingCalls1A(
95    "d1", cl::aliasopt(GraphDiffDeduceSiblingCalls1),
96    cl::desc("Alias for -deduce-sibling-calls-1"));
97static 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));
101static cl::alias GraphDiffDeduceSiblingCalls2A(
102    "d2", cl::aliasopt(GraphDiffDeduceSiblingCalls2),
103    cl::desc("Alias for -deduce-sibling-calls-2"));
104
105static 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")));
125static cl::alias GraphDiffEdgeLabelA("e", cl::aliasopt(GraphDiffEdgeLabel),
126                                     cl::desc("Alias for -edge-label"));
127
128static 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")));
148static cl::alias GraphDiffEdgeColorA("c", cl::aliasopt(GraphDiffEdgeColor),
149                                     cl::desc("Alias for -edge-color"));
150
151static 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")));
172static cl::alias GraphDiffVertexLabelA("v", cl::aliasopt(GraphDiffVertexLabel),
173                                       cl::desc("Alias for -vertex-label"));
174
175static 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")));
196static cl::alias GraphDiffVertexColorA("b", cl::aliasopt(GraphDiffVertexColor),
197                                       cl::desc("Alias for -vertex-color"));
198
199static cl::opt<int> GraphDiffVertexLabelTrunc(
200    "vertex-label-trun", cl::desc("What length to truncate vertex labels to "),
201    cl::sub(GraphDiff), cl::init(40));
202static cl::alias
203    GraphDiffVertexLabelTrunc1("t", cl::aliasopt(GraphDiffVertexLabelTrunc),
204                               cl::desc("Alias for -vertex-label-trun"));
205
206static 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));
210static cl::alias GraphDiffOutputA("o", cl::aliasopt(GraphDiffOutput),
211                                  cl::desc("Alias for -output"));
212
213Expected<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.
241static 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
250static 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::min(1.0, std::max(-1.0, RelDiff));
267
268  return H.getColorString(CappedRelDiff);
269}
270
271static 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::min(1.0, std::max(-1.0, RelDiff));
288
289  return H.getColorString(CappedRelDiff);
290}
291
292static Twine truncateString(const StringRef &S, size_t n) {
293  return (S.size() > n) ? Twine(S.substr(0, n)) + "..." : Twine(S);
294}
295
296template <typename T> static bool containsNullptr(const T &Collection) {
297  for (const auto &E : Collection)
298    if (E == nullptr)
299      return true;
300  return false;
301}
302
303static std::string getLabel(const GraphDiffRenderer::GraphT::EdgeValueType &E,
304                            GraphDiffRenderer::StatType EL) {
305  auto &EdgeAttr = E.second;
306  switch (EL) {
307  case GraphDiffRenderer::StatType::NONE:
308    return "";
309  default:
310    if (containsNullptr(EdgeAttr.CorrEdgePtr))
311      return "";
312
313    const auto &LeftStat = EdgeAttr.CorrEdgePtr[0]->second.S;
314    const auto &RightStat = EdgeAttr.CorrEdgePtr[1]->second.S;
315
316    double RelDiff = statRelDiff(LeftStat, RightStat, EL);
317    return formatv(R"({0:P})", RelDiff);
318  }
319}
320
321static std::string getLabel(const GraphDiffRenderer::GraphT::VertexValueType &V,
322                            GraphDiffRenderer::StatType VL, int TrunLen) {
323  const auto &VertexId = V.first;
324  const auto &VertexAttr = V.second;
325  switch (VL) {
326  case GraphDiffRenderer::StatType::NONE:
327    return formatv(R"({0})", truncateString(VertexId, TrunLen).str());
328  default:
329    if (containsNullptr(VertexAttr.CorrVertexPtr))
330      return 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 formatv(R"({{{0}|{1:P}})", truncateString(VertexId, TrunLen).str(),
337                   RelDiff);
338  }
339}
340
341static 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
359void 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
407template <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
414static 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_Text);
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