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 <string>
15
16#include "xray-graph-diff.h"
17#include "xray-graph.h"
18#include "xray-registry.h"
19
20#include "xray-color-helper.h"
21#include "llvm/Support/FormatVariadic.h"
22#include "llvm/XRay/Trace.h"
23
24using namespace llvm;
25using namespace xray;
26
27static cl::SubCommand GraphDiff("graph-diff",
28 "Generate diff of function-call graphs");
29static cl::opt<std::string> GraphDiffInput1(cl::Positional,
30 cl::desc("<xray log file 1>"),
31 cl::Required, cl::sub(GraphDiff));
32static cl::opt<std::string> GraphDiffInput2(cl::Positional,
33 cl::desc("<xray log file 2>"),
34 cl::Required, cl::sub(GraphDiff));
35
36static cl::opt<bool>
37 GraphDiffKeepGoing("keep-going",
38 cl::desc("Keep going on errors encountered"),
39 cl::sub(GraphDiff), cl::init(Val: false));
40static cl::alias GraphDiffKeepGoingA("k", cl::aliasopt(GraphDiffKeepGoing),
41 cl::desc("Alias for -keep-going"));
42static cl::opt<bool>
43 GraphDiffKeepGoing1("keep-going-1",
44 cl::desc("Keep going on errors encountered in trace 1"),
45 cl::sub(GraphDiff), cl::init(Val: false));
46static cl::alias GraphDiffKeepGoing1A("k1", cl::aliasopt(GraphDiffKeepGoing1),
47 cl::desc("Alias for -keep-going-1"));
48static cl::opt<bool>
49 GraphDiffKeepGoing2("keep-going-2",
50 cl::desc("Keep going on errors encountered in trace 2"),
51 cl::sub(GraphDiff), cl::init(Val: false));
52static cl::alias GraphDiffKeepGoing2A("k2", cl::aliasopt(GraphDiffKeepGoing2),
53 cl::desc("Alias for -keep-going-2"));
54
55static cl::opt<std::string>
56 GraphDiffInstrMap("instr-map",
57 cl::desc("binary with the instrumentation map, or "
58 "a separate instrumentation map for graph"),
59 cl::value_desc("binary with xray_instr_map or yaml"),
60 cl::sub(GraphDiff), cl::init(Val: ""));
61static cl::alias GraphDiffInstrMapA("m", cl::aliasopt(GraphDiffInstrMap),
62 cl::desc("Alias for -instr-map"));
63static cl::opt<std::string>
64 GraphDiffInstrMap1("instr-map-1",
65 cl::desc("binary with the instrumentation map, or "
66 "a separate instrumentation map for graph 1"),
67 cl::value_desc("binary with xray_instr_map or yaml"),
68 cl::sub(GraphDiff), cl::init(Val: ""));
69static cl::alias GraphDiffInstrMap1A("m1", cl::aliasopt(GraphDiffInstrMap1),
70 cl::desc("Alias for -instr-map-1"));
71static cl::opt<std::string>
72 GraphDiffInstrMap2("instr-map-2",
73 cl::desc("binary with the instrumentation map, or "
74 "a separate instrumentation map for graph 2"),
75 cl::value_desc("binary with xray_instr_map or yaml"),
76 cl::sub(GraphDiff), cl::init(Val: ""));
77static cl::alias GraphDiffInstrMap2A("m2", cl::aliasopt(GraphDiffInstrMap2),
78 cl::desc("Alias for -instr-map-2"));
79
80static cl::opt<bool> GraphDiffDeduceSiblingCalls(
81 "deduce-sibling-calls",
82 cl::desc("Deduce sibling calls when unrolling function call stacks"),
83 cl::sub(GraphDiff), cl::init(Val: false));
84static cl::alias
85 GraphDiffDeduceSiblingCallsA("d", cl::aliasopt(GraphDiffDeduceSiblingCalls),
86 cl::desc("Alias for -deduce-sibling-calls"));
87static cl::opt<bool> GraphDiffDeduceSiblingCalls1(
88 "deduce-sibling-calls-1",
89 cl::desc("Deduce sibling calls when unrolling function call stacks"),
90 cl::sub(GraphDiff), cl::init(Val: false));
91static cl::alias GraphDiffDeduceSiblingCalls1A(
92 "d1", cl::aliasopt(GraphDiffDeduceSiblingCalls1),
93 cl::desc("Alias for -deduce-sibling-calls-1"));
94static cl::opt<bool> GraphDiffDeduceSiblingCalls2(
95 "deduce-sibling-calls-2",
96 cl::desc("Deduce sibling calls when unrolling function call stacks"),
97 cl::sub(GraphDiff), cl::init(Val: false));
98static cl::alias GraphDiffDeduceSiblingCalls2A(
99 "d2", cl::aliasopt(GraphDiffDeduceSiblingCalls2),
100 cl::desc("Alias for -deduce-sibling-calls-2"));
101
102static cl::opt<GraphRenderer::StatType> GraphDiffEdgeLabel(
103 "edge-label", cl::desc("Output graphs with edges labeled with this field"),
104 cl::value_desc("field"), cl::sub(GraphDiff),
105 cl::init(Val: GraphRenderer::StatType::NONE),
106 cl::values(clEnumValN(GraphRenderer::StatType::NONE, "none",
107 "Do not label Edges"),
108 clEnumValN(GraphRenderer::StatType::COUNT, "count",
109 "function call counts"),
110 clEnumValN(GraphRenderer::StatType::MIN, "min",
111 "minimum function durations"),
112 clEnumValN(GraphRenderer::StatType::MED, "med",
113 "median function durations"),
114 clEnumValN(GraphRenderer::StatType::PCT90, "90p",
115 "90th percentile durations"),
116 clEnumValN(GraphRenderer::StatType::PCT99, "99p",
117 "99th percentile durations"),
118 clEnumValN(GraphRenderer::StatType::MAX, "max",
119 "maximum function durations"),
120 clEnumValN(GraphRenderer::StatType::SUM, "sum",
121 "sum of call durations")));
122static cl::alias GraphDiffEdgeLabelA("e", cl::aliasopt(GraphDiffEdgeLabel),
123 cl::desc("Alias for -edge-label"));
124
125static cl::opt<GraphRenderer::StatType> GraphDiffEdgeColor(
126 "edge-color", cl::desc("Output graphs with edges colored by this field"),
127 cl::value_desc("field"), cl::sub(GraphDiff),
128 cl::init(Val: GraphRenderer::StatType::NONE),
129 cl::values(clEnumValN(GraphRenderer::StatType::NONE, "none",
130 "Do not color Edges"),
131 clEnumValN(GraphRenderer::StatType::COUNT, "count",
132 "function call counts"),
133 clEnumValN(GraphRenderer::StatType::MIN, "min",
134 "minimum function durations"),
135 clEnumValN(GraphRenderer::StatType::MED, "med",
136 "median function durations"),
137 clEnumValN(GraphRenderer::StatType::PCT90, "90p",
138 "90th percentile durations"),
139 clEnumValN(GraphRenderer::StatType::PCT99, "99p",
140 "99th percentile durations"),
141 clEnumValN(GraphRenderer::StatType::MAX, "max",
142 "maximum function durations"),
143 clEnumValN(GraphRenderer::StatType::SUM, "sum",
144 "sum of call durations")));
145static cl::alias GraphDiffEdgeColorA("c", cl::aliasopt(GraphDiffEdgeColor),
146 cl::desc("Alias for -edge-color"));
147
148static cl::opt<GraphRenderer::StatType> GraphDiffVertexLabel(
149 "vertex-label",
150 cl::desc("Output graphs with vertices labeled with this field"),
151 cl::value_desc("field"), cl::sub(GraphDiff),
152 cl::init(Val: GraphRenderer::StatType::NONE),
153 cl::values(clEnumValN(GraphRenderer::StatType::NONE, "none",
154 "Do not label Vertices"),
155 clEnumValN(GraphRenderer::StatType::COUNT, "count",
156 "function call counts"),
157 clEnumValN(GraphRenderer::StatType::MIN, "min",
158 "minimum function durations"),
159 clEnumValN(GraphRenderer::StatType::MED, "med",
160 "median function durations"),
161 clEnumValN(GraphRenderer::StatType::PCT90, "90p",
162 "90th percentile durations"),
163 clEnumValN(GraphRenderer::StatType::PCT99, "99p",
164 "99th percentile durations"),
165 clEnumValN(GraphRenderer::StatType::MAX, "max",
166 "maximum function durations"),
167 clEnumValN(GraphRenderer::StatType::SUM, "sum",
168 "sum of call durations")));
169static cl::alias GraphDiffVertexLabelA("v", cl::aliasopt(GraphDiffVertexLabel),
170 cl::desc("Alias for -vertex-label"));
171
172static cl::opt<GraphRenderer::StatType> GraphDiffVertexColor(
173 "vertex-color",
174 cl::desc("Output graphs with vertices colored by this field"),
175 cl::value_desc("field"), cl::sub(GraphDiff),
176 cl::init(Val: GraphRenderer::StatType::NONE),
177 cl::values(clEnumValN(GraphRenderer::StatType::NONE, "none",
178 "Do not color Vertices"),
179 clEnumValN(GraphRenderer::StatType::COUNT, "count",
180 "function call counts"),
181 clEnumValN(GraphRenderer::StatType::MIN, "min",
182 "minimum function durations"),
183 clEnumValN(GraphRenderer::StatType::MED, "med",
184 "median function durations"),
185 clEnumValN(GraphRenderer::StatType::PCT90, "90p",
186 "90th percentile durations"),
187 clEnumValN(GraphRenderer::StatType::PCT99, "99p",
188 "99th percentile durations"),
189 clEnumValN(GraphRenderer::StatType::MAX, "max",
190 "maximum function durations"),
191 clEnumValN(GraphRenderer::StatType::SUM, "sum",
192 "sum of call durations")));
193static cl::alias GraphDiffVertexColorA("b", cl::aliasopt(GraphDiffVertexColor),
194 cl::desc("Alias for -vertex-color"));
195
196static cl::opt<int> GraphDiffVertexLabelTrunc(
197 "vertex-label-trun", cl::desc("What length to truncate vertex labels to "),
198 cl::sub(GraphDiff), cl::init(Val: 40));
199static cl::alias
200 GraphDiffVertexLabelTrunc1("t", cl::aliasopt(GraphDiffVertexLabelTrunc),
201 cl::desc("Alias for -vertex-label-trun"));
202
203static cl::opt<std::string>
204 GraphDiffOutput("output", cl::value_desc("Output file"), cl::init(Val: "-"),
205 cl::desc("output file; use '-' for stdout"),
206 cl::sub(GraphDiff));
207static cl::alias GraphDiffOutputA("o", cl::aliasopt(GraphDiffOutput),
208 cl::desc("Alias for -output"));
209
210Expected<GraphDiffRenderer> GraphDiffRenderer::Factory::getGraphDiffRenderer() {
211 GraphDiffRenderer R;
212
213 for (int i = 0; i < N; ++i) {
214 const auto &G = this->G[i].get();
215 for (const auto &V : G.vertices()) {
216 const auto &VAttr = V.second;
217 R.G[VAttr.SymbolName].CorrVertexPtr[i] = &V;
218 }
219 for (const auto &E : G.edges()) {
220 auto &EdgeTailID = E.first.first;
221 auto &EdgeHeadID = E.first.second;
222 auto EdgeTailAttrOrErr = G.at(I: EdgeTailID);
223 auto EdgeHeadAttrOrErr = G.at(I: EdgeHeadID);
224 if (!EdgeTailAttrOrErr)
225 return EdgeTailAttrOrErr.takeError();
226 if (!EdgeHeadAttrOrErr)
227 return EdgeHeadAttrOrErr.takeError();
228 GraphT::EdgeIdentifier ID{EdgeTailAttrOrErr->SymbolName,
229 EdgeHeadAttrOrErr->SymbolName};
230 R.G[ID].CorrEdgePtr[i] = &E;
231 }
232 }
233
234 return R;
235}
236
237// Returns the Relative change With respect to LeftStat between LeftStat
238// and RightStat.
239static double statRelDiff(const GraphDiffRenderer::TimeStat &LeftStat,
240 const GraphDiffRenderer::TimeStat &RightStat,
241 GraphDiffRenderer::StatType T) {
242 double LeftAttr = LeftStat.getDouble(T);
243 double RightAttr = RightStat.getDouble(T);
244
245 return RightAttr / LeftAttr - 1.0;
246}
247
248static std::string getColor(const GraphDiffRenderer::GraphT::EdgeValueType &E,
249 const GraphDiffRenderer::GraphT &G, ColorHelper H,
250 GraphDiffRenderer::StatType T) {
251 auto &EdgeAttr = E.second;
252 if (EdgeAttr.CorrEdgePtr[0] == nullptr)
253 return H.getColorString(Point: 2.0); // A number greater than 1.0
254 if (EdgeAttr.CorrEdgePtr[1] == nullptr)
255 return H.getColorString(Point: -2.0); // A number less than -1.0
256
257 if (T == GraphDiffRenderer::StatType::NONE)
258 return H.getDefaultColorString();
259
260 const auto &LeftStat = EdgeAttr.CorrEdgePtr[0]->second.S;
261 const auto &RightStat = EdgeAttr.CorrEdgePtr[1]->second.S;
262
263 double RelDiff = statRelDiff(LeftStat, RightStat, T);
264 double CappedRelDiff = std::clamp(val: RelDiff, lo: -1.0, hi: 1.0);
265
266 return H.getColorString(Point: CappedRelDiff);
267}
268
269static std::string getColor(const GraphDiffRenderer::GraphT::VertexValueType &V,
270 const GraphDiffRenderer::GraphT &G, ColorHelper H,
271 GraphDiffRenderer::StatType T) {
272 auto &VertexAttr = V.second;
273 if (VertexAttr.CorrVertexPtr[0] == nullptr)
274 return H.getColorString(Point: 2.0); // A number greater than 1.0
275 if (VertexAttr.CorrVertexPtr[1] == nullptr)
276 return H.getColorString(Point: -2.0); // A number less than -1.0
277
278 if (T == GraphDiffRenderer::StatType::NONE)
279 return H.getDefaultColorString();
280
281 const auto &LeftStat = VertexAttr.CorrVertexPtr[0]->second.S;
282 const auto &RightStat = VertexAttr.CorrVertexPtr[1]->second.S;
283
284 double RelDiff = statRelDiff(LeftStat, RightStat, T);
285 double CappedRelDiff = std::clamp(val: RelDiff, lo: -1.0, hi: 1.0);
286
287 return H.getColorString(Point: CappedRelDiff);
288}
289
290static Twine truncateString(const StringRef &S, size_t n) {
291 return (S.size() > n) ? Twine(S.substr(Start: 0, N: n)) + "..." : Twine(S);
292}
293
294template <typename T> static bool containsNullptr(const T &Collection) {
295 return llvm::is_contained(Collection, nullptr);
296}
297
298static std::string getLabel(const GraphDiffRenderer::GraphT::EdgeValueType &E,
299 GraphDiffRenderer::StatType EL) {
300 auto &EdgeAttr = E.second;
301 switch (EL) {
302 case GraphDiffRenderer::StatType::NONE:
303 return "";
304 default:
305 if (containsNullptr(Collection: EdgeAttr.CorrEdgePtr))
306 return "";
307
308 const auto &LeftStat = EdgeAttr.CorrEdgePtr[0]->second.S;
309 const auto &RightStat = EdgeAttr.CorrEdgePtr[1]->second.S;
310
311 double RelDiff = statRelDiff(LeftStat, RightStat, T: EL);
312 return std::string(formatv(Fmt: R"({0:P})", Vals&: RelDiff));
313 }
314}
315
316static std::string getLabel(const GraphDiffRenderer::GraphT::VertexValueType &V,
317 GraphDiffRenderer::StatType VL, int TrunLen) {
318 const auto &VertexId = V.first;
319 const auto &VertexAttr = V.second;
320 switch (VL) {
321 case GraphDiffRenderer::StatType::NONE:
322 return std::string(
323 formatv(Fmt: R"({0})", Vals: truncateString(S: VertexId, n: TrunLen).str()));
324 default:
325 if (containsNullptr(Collection: VertexAttr.CorrVertexPtr))
326 return std::string(
327 formatv(Fmt: R"({0})", Vals: truncateString(S: VertexId, n: TrunLen).str()));
328
329 const auto &LeftStat = VertexAttr.CorrVertexPtr[0]->second.S;
330 const auto &RightStat = VertexAttr.CorrVertexPtr[1]->second.S;
331
332 double RelDiff = statRelDiff(LeftStat, RightStat, T: VL);
333 return std::string(formatv(
334 Fmt: R"({{{0}|{1:P}})", Vals: truncateString(S: VertexId, n: TrunLen).str(), Vals&: RelDiff));
335 }
336}
337
338static double getLineWidth(const GraphDiffRenderer::GraphT::EdgeValueType &E,
339 GraphDiffRenderer::StatType EL) {
340 auto &EdgeAttr = E.second;
341 switch (EL) {
342 case GraphDiffRenderer::StatType::NONE:
343 return 1.0;
344 default:
345 if (containsNullptr(Collection: EdgeAttr.CorrEdgePtr))
346 return 1.0;
347
348 const auto &LeftStat = EdgeAttr.CorrEdgePtr[0]->second.S;
349 const auto &RightStat = EdgeAttr.CorrEdgePtr[1]->second.S;
350
351 double RelDiff = statRelDiff(LeftStat, RightStat, T: EL);
352 return (RelDiff > 1.0) ? RelDiff : 1.0;
353 }
354}
355
356void GraphDiffRenderer::exportGraphAsDOT(raw_ostream &OS, StatType EdgeLabel,
357 StatType EdgeColor,
358 StatType VertexLabel,
359 StatType VertexColor, int TruncLen) {
360 // Get numbering of vertices for dot output.
361 StringMap<int32_t> VertexNo;
362
363 int i = 0;
364 for (const auto &V : G.vertices())
365 VertexNo[V.first] = i++;
366
367 ColorHelper H(ColorHelper::DivergingScheme::PiYG);
368
369 OS << "digraph xrayDiff {\n";
370
371 if (VertexLabel != StatType::NONE)
372 OS << "node [shape=record]\n";
373
374 for (const auto &E : G.edges()) {
375 const auto &HeadId = E.first.first;
376 const auto &TailId = E.first.second;
377 OS << formatv(Fmt: R"(F{0} -> F{1} [tooltip="{2} -> {3}" label="{4}" )"
378 R"(color="{5}" labelfontcolor="{5}" penwidth={6}])"
379 "\n",
380 Vals&: VertexNo[HeadId], Vals&: VertexNo[TailId],
381 Vals: HeadId.empty() ? static_cast<StringRef>("F0") : HeadId,
382 Vals: TailId, Vals: getLabel(E, EL: EdgeLabel), Vals: getColor(E, G, H, T: EdgeColor),
383 Vals: getLineWidth(E, EL: EdgeColor));
384 }
385
386 for (const auto &V : G.vertices()) {
387 const auto &VertexId = V.first;
388 if (VertexId.empty()) {
389 OS << formatv(Fmt: R"(F{0} [label="F0"])"
390 "\n",
391 Vals&: VertexNo[VertexId]);
392 continue;
393 }
394 OS << formatv(Fmt: R"(F{0} [label="{1}" color="{2}"])"
395 "\n",
396 Vals&: VertexNo[VertexId], Vals: getLabel(V, VL: VertexLabel, TrunLen: TruncLen),
397 Vals: getColor(V, G, H, T: VertexColor));
398 }
399
400 OS << "}\n";
401}
402
403template <typename T> static T &ifSpecified(T &A, cl::alias &AA, T &B) {
404 if (A.getPosition() == 0 && AA.getPosition() == 0)
405 return B;
406
407 return A;
408}
409
410static CommandRegistration Unused(&GraphDiff, []() -> Error {
411 std::array<GraphRenderer::Factory, 2> Factories{
412 ._M_elems: {{.KeepGoing: ifSpecified(A&: GraphDiffKeepGoing1, AA&: GraphDiffKeepGoing1A,
413 B&: GraphDiffKeepGoing),
414 .DeduceSiblingCalls: ifSpecified(A&: GraphDiffDeduceSiblingCalls1, AA&: GraphDiffDeduceSiblingCalls1A,
415 B&: GraphDiffDeduceSiblingCalls),
416 .InstrMap: ifSpecified(A&: GraphDiffInstrMap1, AA&: GraphDiffInstrMap1A, B&: GraphDiffInstrMap),
417 .Trace: Trace()},
418 {.KeepGoing: ifSpecified(A&: GraphDiffKeepGoing2, AA&: GraphDiffKeepGoing2A,
419 B&: GraphDiffKeepGoing),
420 .DeduceSiblingCalls: ifSpecified(A&: GraphDiffDeduceSiblingCalls2, AA&: GraphDiffDeduceSiblingCalls2A,
421 B&: GraphDiffDeduceSiblingCalls),
422 .InstrMap: ifSpecified(A&: GraphDiffInstrMap2, AA&: GraphDiffInstrMap2A, B&: GraphDiffInstrMap),
423 .Trace: Trace()}}};
424
425 std::array<std::string, 2> Inputs{._M_elems: {GraphDiffInput1, GraphDiffInput2}};
426
427 std::array<GraphRenderer::GraphT, 2> Graphs;
428
429 for (int i = 0; i < 2; i++) {
430 auto TraceOrErr = loadTraceFile(Filename: Inputs[i], Sort: true);
431 if (!TraceOrErr)
432 return make_error<StringError>(
433 Args: Twine("Failed Loading Input File '") + Inputs[i] + "'",
434 Args: make_error_code(E: llvm::errc::invalid_argument));
435 Factories[i].Trace = std::move(*TraceOrErr);
436
437 auto GraphRendererOrErr = Factories[i].getGraphRenderer();
438
439 if (!GraphRendererOrErr)
440 return GraphRendererOrErr.takeError();
441
442 auto GraphRenderer = *GraphRendererOrErr;
443
444 Graphs[i] = GraphRenderer.getGraph();
445 }
446
447 GraphDiffRenderer::Factory DGF(Graphs[0], Graphs[1]);
448
449 auto GDROrErr = DGF.getGraphDiffRenderer();
450 if (!GDROrErr)
451 return GDROrErr.takeError();
452
453 auto &GDR = *GDROrErr;
454
455 std::error_code EC;
456 raw_fd_ostream OS(GraphDiffOutput, EC, sys::fs::OpenFlags::OF_TextWithCRLF);
457 if (EC)
458 return make_error<StringError>(
459 Args: Twine("Cannot open file '") + GraphDiffOutput + "' for writing.", Args&: EC);
460
461 GDR.exportGraphAsDOT(OS, EdgeLabel: GraphDiffEdgeLabel, EdgeColor: GraphDiffEdgeColor,
462 VertexLabel: GraphDiffVertexLabel, VertexColor: GraphDiffVertexColor,
463 TruncLen: GraphDiffVertexLabelTrunc);
464
465 return Error::success();
466});
467