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 {
32namespace 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.
36class GraphRenderer {
37public:
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
123public:
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
166inline GraphRenderer::TimeStat operator+(const GraphRenderer::TimeStat &A,
167 const GraphRenderer::TimeStat &B) {
168 return {.Count: A.Count + B.Count, .Min: A.Min + B.Min, .Median: A.Median + B.Median,
169 .Pct90: A.Pct90 + B.Pct90, .Pct99: A.Pct99 + B.Pct99, .Max: A.Max + B.Max,
170 .Sum: A.Sum + B.Sum};
171}
172
173/// Vector Difference of Timestats
174inline GraphRenderer::TimeStat operator-(const GraphRenderer::TimeStat &A,
175 const GraphRenderer::TimeStat &B) {
176
177 return {.Count: A.Count - B.Count, .Min: A.Min - B.Min, .Median: A.Median - B.Median,
178 .Pct90: A.Pct90 - B.Pct90, .Pct99: A.Pct99 - B.Pct99, .Max: A.Max - B.Max,
179 .Sum: A.Sum - B.Sum};
180}
181
182/// Scalar Diference of TimeStat and double
183inline GraphRenderer::TimeStat operator/(const GraphRenderer::TimeStat &A,
184 double B) {
185
186 return {.Count: static_cast<int64_t>(A.Count / B),
187 .Min: A.Min / B,
188 .Median: A.Median / B,
189 .Pct90: A.Pct90 / B,
190 .Pct99: A.Pct99 / B,
191 .Max: A.Max / B,
192 .Sum: A.Sum / B};
193}
194
195/// Scalar product of TimeStat and Double
196inline GraphRenderer::TimeStat operator*(const GraphRenderer::TimeStat &A,
197 double B) {
198 return {.Count: static_cast<int64_t>(A.Count * B),
199 .Min: A.Min * B,
200 .Median: A.Median * B,
201 .Pct90: A.Pct90 * B,
202 .Pct99: A.Pct99 * B,
203 .Max: A.Max * B,
204 .Sum: A.Sum * B};
205}
206
207/// Scalar product of double TimeStat
208inline GraphRenderer::TimeStat operator*(double A,
209 const GraphRenderer::TimeStat &B) {
210 return B * A;
211}
212
213/// Hadamard Product of TimeStats
214inline GraphRenderer::TimeStat operator*(const GraphRenderer::TimeStat &A,
215 const GraphRenderer::TimeStat &B) {
216 return {.Count: A.Count * B.Count, .Min: A.Min * B.Min, .Median: A.Median * B.Median,
217 .Pct90: A.Pct90 * B.Pct90, .Pct99: A.Pct99 * B.Pct99, .Max: A.Max * B.Max,
218 .Sum: A.Sum * B.Sum};
219}
220
221/// Hadamard Division of TimeStats
222inline GraphRenderer::TimeStat operator/(const GraphRenderer::TimeStat &A,
223 const GraphRenderer::TimeStat &B) {
224 return {.Count: A.Count / B.Count, .Min: A.Min / B.Min, .Median: A.Median / B.Median,
225 .Pct90: A.Pct90 / B.Pct90, .Pct99: A.Pct99 / B.Pct99, .Max: A.Max / B.Max,
226 .Sum: A.Sum / B.Sum};
227}
228} // namespace xray
229} // namespace llvm
230
231#endif // XRAY_GRAPH_H
232