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 
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.
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 
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::min(1.0, std::max(-1.0, RelDiff));
268 
269   return H.getColorString(CappedRelDiff);
270 }
271 
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::min(1.0, std::max(-1.0, RelDiff));
289 
290   return H.getColorString(CappedRelDiff);
291 }
292 
293 static Twine truncateString(const StringRef &S, size_t n) {
294   return (S.size() > n) ? Twine(S.substr(0, n)) + "..." : Twine(S);
295 }
296 
297 template <typename T> static bool containsNullptr(const T &Collection) {
298   return llvm::is_contained(Collection, nullptr);
299 }
300 
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 
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 
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 
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 
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 
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