CoCalc -- xray-graph-diff.cpp

GitHub Repository: freebsd/freebsd-src
Path: blob/main/contrib/llvm-project/llvm/tools/llvm-xray/xray-graph-diff.cpp
³⁵²³¹ views
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.empty() ? 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.empty()) {
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
});
470

471
Product

Resources

Company
