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
getGraphDiffRenderer()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.
statRelDiff(const GraphDiffRenderer::TimeStat & LeftStat,const GraphDiffRenderer::TimeStat & RightStat,GraphDiffRenderer::StatType T)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
getColor(const GraphDiffRenderer::GraphT::EdgeValueType & E,const GraphDiffRenderer::GraphT & G,ColorHelper H,GraphDiffRenderer::StatType T)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
getColor(const GraphDiffRenderer::GraphT::VertexValueType & V,const GraphDiffRenderer::GraphT & G,ColorHelper H,GraphDiffRenderer::StatType T)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
truncateString(const StringRef & S,size_t n)292 static Twine truncateString(const StringRef &S, size_t n) {
293 return (S.size() > n) ? Twine(S.substr(0, n)) + "..." : Twine(S);
294 }
295
containsNullptr(const T & Collection)296 template <typename T> static bool containsNullptr(const T &Collection) {
297 return llvm::is_contained(Collection, nullptr);
298 }
299
getLabel(const GraphDiffRenderer::GraphT::EdgeValueType & E,GraphDiffRenderer::StatType EL)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
getLabel(const GraphDiffRenderer::GraphT::VertexValueType & V,GraphDiffRenderer::StatType VL,int TrunLen)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
getLineWidth(const GraphDiffRenderer::GraphT::EdgeValueType & E,GraphDiffRenderer::StatType EL)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
exportGraphAsDOT(raw_ostream & OS,StatType EdgeLabel,StatType EdgeColor,StatType VertexLabel,StatType VertexColor,int TruncLen)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
ifSpecified(T & A,cl::alias & AA,T & B)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
__anon0eabb36e0102() 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