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