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