1 //===-- xray-graph.h - XRay Function Call Graph Renderer --------*- C++ -*-===//
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 
14 #ifndef XRAY_GRAPH_H
15 #define XRAY_GRAPH_H
16 
17 #include <string>
18 #include <vector>
19 
20 #include "func-id-helper.h"
21 #include "xray-color-helper.h"
22 #include "llvm/ADT/DenseMap.h"
23 #include "llvm/ADT/SmallVector.h"
24 #include "llvm/Support/Errc.h"
25 #include "llvm/Support/Program.h"
26 #include "llvm/Support/raw_ostream.h"
27 #include "llvm/XRay/Graph.h"
28 #include "llvm/XRay/Trace.h"
29 #include "llvm/XRay/XRayRecord.h"
30 
31 namespace llvm {
32 namespace xray {
33 
34 /// A class encapsulating the logic related to analyzing XRay traces, producting
35 /// Graphs from them and then exporting those graphs for review.
36 class GraphRenderer {
37 public:
38   /// An enum for enumerating the various statistics gathered on latencies
39   enum class StatType { NONE, COUNT, MIN, MED, PCT90, PCT99, MAX, SUM };
40 
41   /// An inner struct for common timing statistics information
42   struct TimeStat {
43     int64_t Count;
44     double Min;
45     double Median;
46     double Pct90;
47     double Pct99;
48     double Max;
49     double Sum;
50 
51     std::string getString(StatType T) const;
52     double getDouble(StatType T) const;
53   };
54   using TimestampT = uint64_t;
55 
56   /// An inner struct for storing edge attributes for our graph. Here the
57   /// attributes are mainly function call statistics.
58   ///
59   /// FIXME: expand to contain more information eg call latencies.
60   struct CallStats {
61     TimeStat S;
62     std::vector<TimestampT> Timings;
63   };
64 
65   /// An Inner Struct for storing vertex attributes, at the moment just
66   /// SymbolNames, however in future we could store bulk function statistics.
67   ///
68   /// FIXME: Store more attributes based on instrumentation map.
69   struct FunctionStats {
70     std::string SymbolName;
71     TimeStat S = {};
72   };
73 
74   struct FunctionAttr {
75     int32_t FuncId;
76     uint64_t TSC;
77   };
78 
79   using FunctionStack = SmallVector<FunctionAttr, 4>;
80 
81   using PerThreadFunctionStackMap = DenseMap<uint32_t, FunctionStack>;
82 
83   class GraphT : public Graph<FunctionStats, CallStats, int32_t> {
84   public:
85     TimeStat GraphEdgeMax = {};
86     TimeStat GraphVertexMax = {};
87   };
88 
89   GraphT G;
90   using VertexIdentifier = typename decltype(G)::VertexIdentifier;
91   using EdgeIdentifier = decltype(G)::EdgeIdentifier;
92 
93   /// Use a Map to store the Function stack for each thread whilst building the
94   /// graph.
95   ///
96   /// FIXME: Perhaps we can Build this into LatencyAccountant? or vise versa?
97   PerThreadFunctionStackMap PerThreadFunctionStack;
98 
99   /// Usefull object for getting human readable Symbol Names.
100   FuncIdConversionHelper FuncIdHelper;
101   bool DeduceSiblingCalls = false;
102   TimestampT CurrentMaxTSC = 0;
103 
104   /// A private function to help implement the statistic generation functions;
105   template <typename U>
106   void getStats(U begin, U end, GraphRenderer::TimeStat &S);
107   void updateMaxStats(const TimeStat &S, TimeStat &M);
108 
109   /// Calculates latency statistics for each edge and stores the data in the
110   /// Graph
111   void calculateEdgeStatistics();
112 
113   /// Calculates latency statistics for each vertex and stores the data in the
114   /// Graph
115   void calculateVertexStatistics();
116 
117   /// Normalises latency statistics for each edge and vertex by CycleFrequency;
118   void normalizeStatistics(double CycleFrequency);
119 
120   /// An object to color gradients
121   ColorHelper CHelper;
122 
123 public:
124   /// Takes in a reference to a FuncIdHelper in order to have ready access to
125   /// Symbol names.
126   explicit GraphRenderer(const FuncIdConversionHelper &FuncIdHelper, bool DSC)
127       : FuncIdHelper(FuncIdHelper), DeduceSiblingCalls(DSC),
128         CHelper(ColorHelper::SequentialScheme::OrRd) {
129     G[0] = {};
130   }
131 
132   /// Process an Xray record and expand the graph.
133   ///
134   /// This Function will return true on success, or false if records are not
135   /// presented in per-thread call-tree DFS order. (That is for each thread the
136   /// Records should be in order runtime on an ideal system.)
137   ///
138   /// FIXME: Make this more robust against small irregularities.
139   Error accountRecord(const XRayRecord &Record);
140 
141   const PerThreadFunctionStackMap &getPerThreadFunctionStack() const {
142     return PerThreadFunctionStack;
143   }
144 
145   class Factory {
146   public:
147     bool KeepGoing;
148     bool DeduceSiblingCalls;
149     std::string InstrMap;
150     ::llvm::xray::Trace Trace;
151     Expected<GraphRenderer> getGraphRenderer();
152   };
153 
154   /// Output the Embedded graph in DOT format on \p OS, labeling the edges by
155   /// \p T
156   void exportGraphAsDOT(raw_ostream &OS, StatType EdgeLabel = StatType::NONE,
157                         StatType EdgeColor = StatType::NONE,
158                         StatType VertexLabel = StatType::NONE,
159                         StatType VertexColor = StatType::NONE);
160 
161   /// Get a reference to the internal graph.
162   const GraphT &getGraph() { return G; }
163 };
164 
165 /// Vector Sum of TimeStats
166 inline GraphRenderer::TimeStat operator+(const GraphRenderer::TimeStat &A,
167                                          const GraphRenderer::TimeStat &B) {
168   return {A.Count + B.Count, A.Min + B.Min,     A.Median + B.Median,
169           A.Pct90 + B.Pct90, A.Pct99 + B.Pct99, A.Max + B.Max,
170           A.Sum + B.Sum};
171 }
172 
173 /// Vector Difference of Timestats
174 inline GraphRenderer::TimeStat operator-(const GraphRenderer::TimeStat &A,
175                                          const GraphRenderer::TimeStat &B) {
176 
177   return {A.Count - B.Count, A.Min - B.Min,     A.Median - B.Median,
178           A.Pct90 - B.Pct90, A.Pct99 - B.Pct99, A.Max - B.Max,
179           A.Sum - B.Sum};
180 }
181 
182 /// Scalar Diference of TimeStat and double
183 inline GraphRenderer::TimeStat operator/(const GraphRenderer::TimeStat &A,
184                                          double B) {
185 
186   return {static_cast<int64_t>(A.Count / B),
187           A.Min / B,
188           A.Median / B,
189           A.Pct90 / B,
190           A.Pct99 / B,
191           A.Max / B,
192           A.Sum / B};
193 }
194 
195 /// Scalar product of TimeStat and Double
196 inline GraphRenderer::TimeStat operator*(const GraphRenderer::TimeStat &A,
197                                          double B) {
198   return {static_cast<int64_t>(A.Count * B),
199           A.Min * B,
200           A.Median * B,
201           A.Pct90 * B,
202           A.Pct99 * B,
203           A.Max * B,
204           A.Sum * B};
205 }
206 
207 /// Scalar product of double TimeStat
208 inline GraphRenderer::TimeStat operator*(double A,
209                                          const GraphRenderer::TimeStat &B) {
210   return B * A;
211 }
212 
213 /// Hadamard Product of TimeStats
214 inline GraphRenderer::TimeStat operator*(const GraphRenderer::TimeStat &A,
215                                          const GraphRenderer::TimeStat &B) {
216   return {A.Count * B.Count, A.Min * B.Min,     A.Median * B.Median,
217           A.Pct90 * B.Pct90, A.Pct99 * B.Pct99, A.Max * B.Max,
218           A.Sum * B.Sum};
219 }
220 
221 /// Hadamard Division of TimeStats
222 inline GraphRenderer::TimeStat operator/(const GraphRenderer::TimeStat &A,
223                                          const GraphRenderer::TimeStat &B) {
224   return {A.Count / B.Count, A.Min / B.Min,     A.Median / B.Median,
225           A.Pct90 / B.Pct90, A.Pct99 / B.Pct99, A.Max / B.Max,
226           A.Sum / B.Sum};
227 }
228 } // namespace xray
229 } // namespace llvm
230 
231 #endif // XRAY_GRAPH_H
232