1 //===-- xray-graph.h - XRay Function Call Graph Renderer --------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // Generate a DOT file to represent the function call graph encountered in
13 //===----------------------------------------------------------------------===//
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"
35 /// A class encapsulating the logic related to analyzing XRay traces, producting
36 /// Graphs from them and then exporting those graphs for review.
39 /// An enum for enumerating the various statistics gathered on latencies
40 enum class StatType { NONE, COUNT, MIN, MED, PCT90, PCT99, MAX, SUM };
42 /// An inner struct for common timing statistics information
52 std::string getString(StatType T) const;
53 double getDouble(StatType T) const;
55 using TimestampT = uint64_t;
57 /// An inner struct for storing edge attributes for our graph. Here the
58 /// attributes are mainly function call statistics.
60 /// FIXME: expand to contain more information eg call latencies.
63 std::vector<TimestampT> Timings;
66 /// An Inner Struct for storing vertex attributes, at the moment just
67 /// SymbolNames, however in future we could store bulk function statistics.
69 /// FIXME: Store more attributes based on instrumentation map.
70 struct FunctionStats {
71 std::string SymbolName;
80 using FunctionStack = SmallVector<FunctionAttr, 4>;
82 using PerThreadFunctionStackMap =
83 DenseMap<llvm::sys::ProcessInfo::ProcessId, FunctionStack>;
85 class GraphT : public Graph<FunctionStats, CallStats, int32_t> {
87 TimeStat GraphEdgeMax = {};
88 TimeStat GraphVertexMax = {};
92 using VertexIdentifier = typename decltype(G)::VertexIdentifier;
93 using EdgeIdentifier = decltype(G)::EdgeIdentifier;
95 /// Use a Map to store the Function stack for each thread whilst building the
98 /// FIXME: Perhaps we can Build this into LatencyAccountant? or vise versa?
99 PerThreadFunctionStackMap PerThreadFunctionStack;
101 /// Usefull object for getting human readable Symbol Names.
102 FuncIdConversionHelper FuncIdHelper;
103 bool DeduceSiblingCalls = false;
104 TimestampT CurrentMaxTSC = 0;
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);
111 /// Calculates latency statistics for each edge and stores the data in the
113 void calculateEdgeStatistics();
115 /// Calculates latency statistics for each vertex and stores the data in the
117 void calculateVertexStatistics();
119 /// Normalises latency statistics for each edge and vertex by CycleFrequency;
120 void normalizeStatistics(double CycleFrequency);
122 /// An object to color gradients
126 /// Takes in a reference to a FuncIdHelper in order to have ready access to
128 explicit GraphRenderer(const FuncIdConversionHelper &FuncIdHelper, bool DSC)
129 : FuncIdHelper(FuncIdHelper), DeduceSiblingCalls(DSC),
130 CHelper(ColorHelper::SequentialScheme::OrRd) {
134 /// Process an Xray record and expand the graph.
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.)
140 /// FIXME: Make this more robust against small irregularities.
141 Error accountRecord(const XRayRecord &Record);
143 const PerThreadFunctionStackMap &getPerThreadFunctionStack() const {
144 return PerThreadFunctionStack;
150 bool DeduceSiblingCalls;
151 std::string InstrMap;
152 ::llvm::xray::Trace Trace;
153 Expected<GraphRenderer> getGraphRenderer();
156 /// Output the Embedded graph in DOT format on \p OS, labeling the edges by
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);
163 /// Get a reference to the internal graph.
164 const GraphT &getGraph() { return G; }
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,
175 /// Vector Difference of Timestats
176 inline GraphRenderer::TimeStat operator-(const GraphRenderer::TimeStat &A,
177 const GraphRenderer::TimeStat &B) {
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,
184 /// Scalar Diference of TimeStat and double
185 inline GraphRenderer::TimeStat operator/(const GraphRenderer::TimeStat &A,
188 return {static_cast<int64_t>(A.Count / B),
197 /// Scalar product of TimeStat and Double
198 inline GraphRenderer::TimeStat operator*(const GraphRenderer::TimeStat &A,
200 return {static_cast<int64_t>(A.Count * B),
209 /// Scalar product of double TimeStat
210 inline GraphRenderer::TimeStat operator*(double A,
211 const GraphRenderer::TimeStat &B) {
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,
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,
233 #endif // XRAY_GRAPH_H