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