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