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/Support/MemoryBuffer.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 static cl::opt<bool>
47 GraphDiffKeepGoing1("keep-going-1",
48 cl::desc("Keep going on errors encountered in trace 1"),
49 cl::sub(GraphDiff), cl::init(false));
50 static cl::alias GraphDiffKeepGoing1A("k1", cl::aliasopt(GraphDiffKeepGoing1),
51 cl::desc("Alias for -keep-going-1"));
52 static cl::opt<bool>
53 GraphDiffKeepGoing2("keep-going-2",
54 cl::desc("Keep going on errors encountered in trace 2"),
55 cl::sub(GraphDiff), cl::init(false));
56 static cl::alias GraphDiffKeepGoing2A("k2", cl::aliasopt(GraphDiffKeepGoing2),
57 cl::desc("Alias for -keep-going-2"));
58
59 static cl::opt<std::string>
60 GraphDiffInstrMap("instr-map",
61 cl::desc("binary with the instrumentation map, or "
62 "a separate instrumentation map for graph"),
63 cl::value_desc("binary with xray_instr_map or yaml"),
64 cl::sub(GraphDiff), cl::init(""));
65 static cl::alias GraphDiffInstrMapA("m", cl::aliasopt(GraphDiffInstrMap),
66 cl::desc("Alias for -instr-map"));
67 static cl::opt<std::string>
68 GraphDiffInstrMap1("instr-map-1",
69 cl::desc("binary with the instrumentation map, or "
70 "a separate instrumentation map for graph 1"),
71 cl::value_desc("binary with xray_instr_map or yaml"),
72 cl::sub(GraphDiff), cl::init(""));
73 static cl::alias GraphDiffInstrMap1A("m1", cl::aliasopt(GraphDiffInstrMap1),
74 cl::desc("Alias for -instr-map-1"));
75 static cl::opt<std::string>
76 GraphDiffInstrMap2("instr-map-2",
77 cl::desc("binary with the instrumentation map, or "
78 "a separate instrumentation map for graph 2"),
79 cl::value_desc("binary with xray_instr_map or yaml"),
80 cl::sub(GraphDiff), cl::init(""));
81 static cl::alias GraphDiffInstrMap2A("m2", cl::aliasopt(GraphDiffInstrMap2),
82 cl::desc("Alias for -instr-map-2"));
83
84 static cl::opt<bool> GraphDiffDeduceSiblingCalls(
85 "deduce-sibling-calls",
86 cl::desc("Deduce sibling calls when unrolling function call stacks"),
87 cl::sub(GraphDiff), cl::init(false));
88 static cl::alias
89 GraphDiffDeduceSiblingCallsA("d", cl::aliasopt(GraphDiffDeduceSiblingCalls),
90 cl::desc("Alias for -deduce-sibling-calls"));
91 static cl::opt<bool> GraphDiffDeduceSiblingCalls1(
92 "deduce-sibling-calls-1",
93 cl::desc("Deduce sibling calls when unrolling function call stacks"),
94 cl::sub(GraphDiff), cl::init(false));
95 static cl::alias GraphDiffDeduceSiblingCalls1A(
96 "d1", cl::aliasopt(GraphDiffDeduceSiblingCalls1),
97 cl::desc("Alias for -deduce-sibling-calls-1"));
98 static cl::opt<bool> GraphDiffDeduceSiblingCalls2(
99 "deduce-sibling-calls-2",
100 cl::desc("Deduce sibling calls when unrolling function call stacks"),
101 cl::sub(GraphDiff), cl::init(false));
102 static cl::alias GraphDiffDeduceSiblingCalls2A(
103 "d2", cl::aliasopt(GraphDiffDeduceSiblingCalls2),
104 cl::desc("Alias for -deduce-sibling-calls-2"));
105
106 static cl::opt<GraphRenderer::StatType> GraphDiffEdgeLabel(
107 "edge-label", cl::desc("Output graphs with edges labeled with this field"),
108 cl::value_desc("field"), cl::sub(GraphDiff),
109 cl::init(GraphRenderer::StatType::NONE),
110 cl::values(clEnumValN(GraphRenderer::StatType::NONE, "none",
111 "Do not label Edges"),
112 clEnumValN(GraphRenderer::StatType::COUNT, "count",
113 "function call counts"),
114 clEnumValN(GraphRenderer::StatType::MIN, "min",
115 "minimum function durations"),
116 clEnumValN(GraphRenderer::StatType::MED, "med",
117 "median function durations"),
118 clEnumValN(GraphRenderer::StatType::PCT90, "90p",
119 "90th percentile durations"),
120 clEnumValN(GraphRenderer::StatType::PCT99, "99p",
121 "99th percentile durations"),
122 clEnumValN(GraphRenderer::StatType::MAX, "max",
123 "maximum function durations"),
124 clEnumValN(GraphRenderer::StatType::SUM, "sum",
125 "sum of call durations")));
126 static cl::alias GraphDiffEdgeLabelA("e", cl::aliasopt(GraphDiffEdgeLabel),
127 cl::desc("Alias for -edge-label"));
128
129 static cl::opt<GraphRenderer::StatType> GraphDiffEdgeColor(
130 "edge-color", cl::desc("Output graphs with edges colored by this field"),
131 cl::value_desc("field"), cl::sub(GraphDiff),
132 cl::init(GraphRenderer::StatType::NONE),
133 cl::values(clEnumValN(GraphRenderer::StatType::NONE, "none",
134 "Do not color Edges"),
135 clEnumValN(GraphRenderer::StatType::COUNT, "count",
136 "function call counts"),
137 clEnumValN(GraphRenderer::StatType::MIN, "min",
138 "minimum function durations"),
139 clEnumValN(GraphRenderer::StatType::MED, "med",
140 "median function durations"),
141 clEnumValN(GraphRenderer::StatType::PCT90, "90p",
142 "90th percentile durations"),
143 clEnumValN(GraphRenderer::StatType::PCT99, "99p",
144 "99th percentile durations"),
145 clEnumValN(GraphRenderer::StatType::MAX, "max",
146 "maximum function durations"),
147 clEnumValN(GraphRenderer::StatType::SUM, "sum",
148 "sum of call durations")));
149 static cl::alias GraphDiffEdgeColorA("c", cl::aliasopt(GraphDiffEdgeColor),
150 cl::desc("Alias for -edge-color"));
151
152 static cl::opt<GraphRenderer::StatType> GraphDiffVertexLabel(
153 "vertex-label",
154 cl::desc("Output graphs with vertices labeled with this field"),
155 cl::value_desc("field"), cl::sub(GraphDiff),
156 cl::init(GraphRenderer::StatType::NONE),
157 cl::values(clEnumValN(GraphRenderer::StatType::NONE, "none",
158 "Do not label Vertices"),
159 clEnumValN(GraphRenderer::StatType::COUNT, "count",
160 "function call counts"),
161 clEnumValN(GraphRenderer::StatType::MIN, "min",
162 "minimum function durations"),
163 clEnumValN(GraphRenderer::StatType::MED, "med",
164 "median function durations"),
165 clEnumValN(GraphRenderer::StatType::PCT90, "90p",
166 "90th percentile durations"),
167 clEnumValN(GraphRenderer::StatType::PCT99, "99p",
168 "99th percentile durations"),
169 clEnumValN(GraphRenderer::StatType::MAX, "max",
170 "maximum function durations"),
171 clEnumValN(GraphRenderer::StatType::SUM, "sum",
172 "sum of call durations")));
173 static cl::alias GraphDiffVertexLabelA("v", cl::aliasopt(GraphDiffVertexLabel),
174 cl::desc("Alias for -vertex-label"));
175
176 static cl::opt<GraphRenderer::StatType> GraphDiffVertexColor(
177 "vertex-color",
178 cl::desc("Output graphs with vertices colored by this field"),
179 cl::value_desc("field"), cl::sub(GraphDiff),
180 cl::init(GraphRenderer::StatType::NONE),
181 cl::values(clEnumValN(GraphRenderer::StatType::NONE, "none",
182 "Do not color Vertices"),
183 clEnumValN(GraphRenderer::StatType::COUNT, "count",
184 "function call counts"),
185 clEnumValN(GraphRenderer::StatType::MIN, "min",
186 "minimum function durations"),
187 clEnumValN(GraphRenderer::StatType::MED, "med",
188 "median function durations"),
189 clEnumValN(GraphRenderer::StatType::PCT90, "90p",
190 "90th percentile durations"),
191 clEnumValN(GraphRenderer::StatType::PCT99, "99p",
192 "99th percentile durations"),
193 clEnumValN(GraphRenderer::StatType::MAX, "max",
194 "maximum function durations"),
195 clEnumValN(GraphRenderer::StatType::SUM, "sum",
196 "sum of call durations")));
197 static cl::alias GraphDiffVertexColorA("b", cl::aliasopt(GraphDiffVertexColor),
198 cl::desc("Alias for -vertex-color"));
199
200 static cl::opt<int> GraphDiffVertexLabelTrunc(
201 "vertex-label-trun", cl::desc("What length to truncate vertex labels to "),
202 cl::sub(GraphDiff), cl::init(40));
203 static cl::alias
204 GraphDiffVertexLabelTrunc1("t", cl::aliasopt(GraphDiffVertexLabelTrunc),
205 cl::desc("Alias for -vertex-label-trun"));
206
207 static cl::opt<std::string>
208 GraphDiffOutput("output", cl::value_desc("Output file"), cl::init("-"),
209 cl::desc("output file; use '-' for stdout"),
210 cl::sub(GraphDiff));
211 static cl::alias GraphDiffOutputA("o", cl::aliasopt(GraphDiffOutput),
212 cl::desc("Alias for -output"));
213
getGraphDiffRenderer()214 Expected<GraphDiffRenderer> GraphDiffRenderer::Factory::getGraphDiffRenderer() {
215 GraphDiffRenderer R;
216
217 for (int i = 0; i < N; ++i) {
218 const auto &G = this->G[i].get();
219 for (const auto &V : G.vertices()) {
220 const auto &VAttr = V.second;
221 R.G[VAttr.SymbolName].CorrVertexPtr[i] = &V;
222 }
223 for (const auto &E : G.edges()) {
224 auto &EdgeTailID = E.first.first;
225 auto &EdgeHeadID = E.first.second;
226 auto EdgeTailAttrOrErr = G.at(EdgeTailID);
227 auto EdgeHeadAttrOrErr = G.at(EdgeHeadID);
228 if (!EdgeTailAttrOrErr)
229 return EdgeTailAttrOrErr.takeError();
230 if (!EdgeHeadAttrOrErr)
231 return EdgeHeadAttrOrErr.takeError();
232 GraphT::EdgeIdentifier ID{EdgeTailAttrOrErr->SymbolName,
233 EdgeHeadAttrOrErr->SymbolName};
234 R.G[ID].CorrEdgePtr[i] = &E;
235 }
236 }
237
238 return R;
239 }
240 // Returns the Relative change With respect to LeftStat between LeftStat
241 // and RightStat.
statRelDiff(const GraphDiffRenderer::TimeStat & LeftStat,const GraphDiffRenderer::TimeStat & RightStat,GraphDiffRenderer::StatType T)242 static double statRelDiff(const GraphDiffRenderer::TimeStat &LeftStat,
243 const GraphDiffRenderer::TimeStat &RightStat,
244 GraphDiffRenderer::StatType T) {
245 double LeftAttr = LeftStat.getDouble(T);
246 double RightAttr = RightStat.getDouble(T);
247
248 return RightAttr / LeftAttr - 1.0;
249 }
250
getColor(const GraphDiffRenderer::GraphT::EdgeValueType & E,const GraphDiffRenderer::GraphT & G,ColorHelper H,GraphDiffRenderer::StatType T)251 static std::string getColor(const GraphDiffRenderer::GraphT::EdgeValueType &E,
252 const GraphDiffRenderer::GraphT &G, ColorHelper H,
253 GraphDiffRenderer::StatType T) {
254 auto &EdgeAttr = E.second;
255 if (EdgeAttr.CorrEdgePtr[0] == nullptr)
256 return H.getColorString(2.0); // A number greater than 1.0
257 if (EdgeAttr.CorrEdgePtr[1] == nullptr)
258 return H.getColorString(-2.0); // A number less than -1.0
259
260 if (T == GraphDiffRenderer::StatType::NONE)
261 return H.getDefaultColorString();
262
263 const auto &LeftStat = EdgeAttr.CorrEdgePtr[0]->second.S;
264 const auto &RightStat = EdgeAttr.CorrEdgePtr[1]->second.S;
265
266 double RelDiff = statRelDiff(LeftStat, RightStat, T);
267 double CappedRelDiff = std::clamp(RelDiff, -1.0, 1.0);
268
269 return H.getColorString(CappedRelDiff);
270 }
271
getColor(const GraphDiffRenderer::GraphT::VertexValueType & V,const GraphDiffRenderer::GraphT & G,ColorHelper H,GraphDiffRenderer::StatType T)272 static std::string getColor(const GraphDiffRenderer::GraphT::VertexValueType &V,
273 const GraphDiffRenderer::GraphT &G, ColorHelper H,
274 GraphDiffRenderer::StatType T) {
275 auto &VertexAttr = V.second;
276 if (VertexAttr.CorrVertexPtr[0] == nullptr)
277 return H.getColorString(2.0); // A number greater than 1.0
278 if (VertexAttr.CorrVertexPtr[1] == nullptr)
279 return H.getColorString(-2.0); // A number less than -1.0
280
281 if (T == GraphDiffRenderer::StatType::NONE)
282 return H.getDefaultColorString();
283
284 const auto &LeftStat = VertexAttr.CorrVertexPtr[0]->second.S;
285 const auto &RightStat = VertexAttr.CorrVertexPtr[1]->second.S;
286
287 double RelDiff = statRelDiff(LeftStat, RightStat, T);
288 double CappedRelDiff = std::clamp(RelDiff, -1.0, 1.0);
289
290 return H.getColorString(CappedRelDiff);
291 }
292
truncateString(const StringRef & S,size_t n)293 static Twine truncateString(const StringRef &S, size_t n) {
294 return (S.size() > n) ? Twine(S.substr(0, n)) + "..." : Twine(S);
295 }
296
containsNullptr(const T & Collection)297 template <typename T> static bool containsNullptr(const T &Collection) {
298 return llvm::is_contained(Collection, nullptr);
299 }
300
getLabel(const GraphDiffRenderer::GraphT::EdgeValueType & E,GraphDiffRenderer::StatType EL)301 static std::string getLabel(const GraphDiffRenderer::GraphT::EdgeValueType &E,
302 GraphDiffRenderer::StatType EL) {
303 auto &EdgeAttr = E.second;
304 switch (EL) {
305 case GraphDiffRenderer::StatType::NONE:
306 return "";
307 default:
308 if (containsNullptr(EdgeAttr.CorrEdgePtr))
309 return "";
310
311 const auto &LeftStat = EdgeAttr.CorrEdgePtr[0]->second.S;
312 const auto &RightStat = EdgeAttr.CorrEdgePtr[1]->second.S;
313
314 double RelDiff = statRelDiff(LeftStat, RightStat, EL);
315 return std::string(formatv(R"({0:P})", RelDiff));
316 }
317 }
318
getLabel(const GraphDiffRenderer::GraphT::VertexValueType & V,GraphDiffRenderer::StatType VL,int TrunLen)319 static std::string getLabel(const GraphDiffRenderer::GraphT::VertexValueType &V,
320 GraphDiffRenderer::StatType VL, int TrunLen) {
321 const auto &VertexId = V.first;
322 const auto &VertexAttr = V.second;
323 switch (VL) {
324 case GraphDiffRenderer::StatType::NONE:
325 return std::string(
326 formatv(R"({0})", truncateString(VertexId, TrunLen).str()));
327 default:
328 if (containsNullptr(VertexAttr.CorrVertexPtr))
329 return std::string(
330 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 std::string(formatv(
337 R"({{{0}|{1:P}})", truncateString(VertexId, TrunLen).str(), RelDiff));
338 }
339 }
340
getLineWidth(const GraphDiffRenderer::GraphT::EdgeValueType & E,GraphDiffRenderer::StatType EL)341 static 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
exportGraphAsDOT(raw_ostream & OS,StatType EdgeLabel,StatType EdgeColor,StatType VertexLabel,StatType VertexColor,int TruncLen)359 void 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
ifSpecified(T & A,cl::alias & AA,T & B)407 template <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
__anona23076250102() 414 static 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_TextWithCRLF);
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