1 //===-- xray-graph.h - XRay Function Call Graph Renderer --------*- C++ -*-===//
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
7 //===----------------------------------------------------------------------===//
9 // Generate a DOT file to represent the function call graph encountered in
12 //===----------------------------------------------------------------------===//
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"
34 /// A class encapsulating the logic related to analyzing XRay traces, producting
35 /// Graphs from them and then exporting those graphs for review.
38 /// An enum for enumerating the various statistics gathered on latencies
39 enum class StatType { NONE, COUNT, MIN, MED, PCT90, PCT99, MAX, SUM };
41 /// An inner struct for common timing statistics information
51 std::string getString(StatType T) const;
52 double getDouble(StatType T) const;
54 using TimestampT = uint64_t;
56 /// An inner struct for storing edge attributes for our graph. Here the
57 /// attributes are mainly function call statistics.
59 /// FIXME: expand to contain more information eg call latencies.
62 std::vector<TimestampT> Timings;
65 /// An Inner Struct for storing vertex attributes, at the moment just
66 /// SymbolNames, however in future we could store bulk function statistics.
68 /// FIXME: Store more attributes based on instrumentation map.
69 struct FunctionStats {
70 std::string SymbolName;
79 using FunctionStack = SmallVector<FunctionAttr, 4>;
81 using PerThreadFunctionStackMap = DenseMap<uint32_t, FunctionStack>;
83 class GraphT : public Graph<FunctionStats, CallStats, int32_t> {
85 TimeStat GraphEdgeMax = {};
86 TimeStat GraphVertexMax = {};
90 using VertexIdentifier = typename decltype(G)::VertexIdentifier;
91 using EdgeIdentifier = decltype(G)::EdgeIdentifier;
93 /// Use a Map to store the Function stack for each thread whilst building the
96 /// FIXME: Perhaps we can Build this into LatencyAccountant? or vise versa?
97 PerThreadFunctionStackMap PerThreadFunctionStack;
99 /// Usefull object for getting human readable Symbol Names.
100 FuncIdConversionHelper FuncIdHelper;
101 bool DeduceSiblingCalls = false;
102 TimestampT CurrentMaxTSC = 0;
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);
109 /// Calculates latency statistics for each edge and stores the data in the
111 void calculateEdgeStatistics();
113 /// Calculates latency statistics for each vertex and stores the data in the
115 void calculateVertexStatistics();
117 /// Normalises latency statistics for each edge and vertex by CycleFrequency;
118 void normalizeStatistics(double CycleFrequency);
120 /// An object to color gradients
124 /// Takes in a reference to a FuncIdHelper in order to have ready access to
126 explicit GraphRenderer(const FuncIdConversionHelper &FuncIdHelper, bool DSC)
127 : FuncIdHelper(FuncIdHelper), DeduceSiblingCalls(DSC),
128 CHelper(ColorHelper::SequentialScheme::OrRd) {
132 /// Process an Xray record and expand the graph.
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.)
138 /// FIXME: Make this more robust against small irregularities.
139 Error accountRecord(const XRayRecord &Record);
141 const PerThreadFunctionStackMap &getPerThreadFunctionStack() const {
142 return PerThreadFunctionStack;
148 bool DeduceSiblingCalls;
149 std::string InstrMap;
150 ::llvm::xray::Trace Trace;
151 Expected<GraphRenderer> getGraphRenderer();
154 /// Output the Embedded graph in DOT format on \p OS, labeling the edges by
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);
161 /// Get a reference to the internal graph.
162 const GraphT &getGraph() { return G; }
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,
173 /// Vector Difference of Timestats
174 inline GraphRenderer::TimeStat operator-(const GraphRenderer::TimeStat &A,
175 const GraphRenderer::TimeStat &B) {
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,
182 /// Scalar Diference of TimeStat and double
183 inline GraphRenderer::TimeStat operator/(const GraphRenderer::TimeStat &A,
186 return {static_cast<int64_t>(A.Count / B),
195 /// Scalar product of TimeStat and Double
196 inline GraphRenderer::TimeStat operator*(const GraphRenderer::TimeStat &A,
198 return {static_cast<int64_t>(A.Count * B),
207 /// Scalar product of double TimeStat
208 inline GraphRenderer::TimeStat operator*(double A,
209 const GraphRenderer::TimeStat &B) {
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,
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,
231 #endif // XRAY_GRAPH_H