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/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::min(1.0, std::max(-1.0, RelDiff));
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::min(1.0, std::max(-1.0, RelDiff));
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.equals("")) ? 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.equals("")) {
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