1 //===-- xray-graph.h - XRay Function Call Graph Renderer --------*- C++ -*-===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // Generate a DOT file to represent the function call graph encountered in 11 // the trace. 12 // 13 //===----------------------------------------------------------------------===// 14 15 #ifndef XRAY_GRAPH_H 16 #define XRAY_GRAPH_H 17 18 #include <string> 19 #include <vector> 20 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" 31 32 namespace llvm { 33 namespace xray { 34 35 /// A class encapsulating the logic related to analyzing XRay traces, producting 36 /// Graphs from them and then exporting those graphs for review. 37 class GraphRenderer { 38 public: 39 /// An enum for enumerating the various statistics gathered on latencies 40 enum class StatType { NONE, COUNT, MIN, MED, PCT90, PCT99, MAX, SUM }; 41 42 /// An inner struct for common timing statistics information 43 struct TimeStat { 44 int64_t Count; 45 double Min; 46 double Median; 47 double Pct90; 48 double Pct99; 49 double Max; 50 double Sum; 51 52 std::string getString(StatType T) const; 53 double getDouble(StatType T) const; 54 }; 55 using TimestampT = uint64_t; 56 57 /// An inner struct for storing edge attributes for our graph. Here the 58 /// attributes are mainly function call statistics. 59 /// 60 /// FIXME: expand to contain more information eg call latencies. 61 struct CallStats { 62 TimeStat S; 63 std::vector<TimestampT> Timings; 64 }; 65 66 /// An Inner Struct for storing vertex attributes, at the moment just 67 /// SymbolNames, however in future we could store bulk function statistics. 68 /// 69 /// FIXME: Store more attributes based on instrumentation map. 70 struct FunctionStats { 71 std::string SymbolName; 72 TimeStat S = {}; 73 }; 74 75 struct FunctionAttr { 76 int32_t FuncId; 77 uint64_t TSC; 78 }; 79 80 using FunctionStack = SmallVector<FunctionAttr, 4>; 81 82 using PerThreadFunctionStackMap = 83 DenseMap<llvm::sys::procid_t, FunctionStack>; 84 85 class GraphT : public Graph<FunctionStats, CallStats, int32_t> { 86 public: 87 TimeStat GraphEdgeMax = {}; 88 TimeStat GraphVertexMax = {}; 89 }; 90 91 GraphT G; 92 using VertexIdentifier = typename decltype(G)::VertexIdentifier; 93 using EdgeIdentifier = decltype(G)::EdgeIdentifier; 94 95 /// Use a Map to store the Function stack for each thread whilst building the 96 /// graph. 97 /// 98 /// FIXME: Perhaps we can Build this into LatencyAccountant? or vise versa? 99 PerThreadFunctionStackMap PerThreadFunctionStack; 100 101 /// Usefull object for getting human readable Symbol Names. 102 FuncIdConversionHelper FuncIdHelper; 103 bool DeduceSiblingCalls = false; 104 TimestampT CurrentMaxTSC = 0; 105 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); 110 111 /// Calculates latency statistics for each edge and stores the data in the 112 /// Graph 113 void calculateEdgeStatistics(); 114 115 /// Calculates latency statistics for each vertex and stores the data in the 116 /// Graph 117 void calculateVertexStatistics(); 118 119 /// Normalises latency statistics for each edge and vertex by CycleFrequency; 120 void normalizeStatistics(double CycleFrequency); 121 122 /// An object to color gradients 123 ColorHelper CHelper; 124 125 public: 126 /// Takes in a reference to a FuncIdHelper in order to have ready access to 127 /// Symbol names. GraphRenderer(const FuncIdConversionHelper & FuncIdHelper,bool DSC)128 explicit GraphRenderer(const FuncIdConversionHelper &FuncIdHelper, bool DSC) 129 : FuncIdHelper(FuncIdHelper), DeduceSiblingCalls(DSC), 130 CHelper(ColorHelper::SequentialScheme::OrRd) { 131 G[0] = {}; 132 } 133 134 /// Process an Xray record and expand the graph. 135 /// 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.) 139 /// 140 /// FIXME: Make this more robust against small irregularities. 141 Error accountRecord(const XRayRecord &Record); 142 getPerThreadFunctionStack()143 const PerThreadFunctionStackMap &getPerThreadFunctionStack() const { 144 return PerThreadFunctionStack; 145 } 146 147 class Factory { 148 public: 149 bool KeepGoing; 150 bool DeduceSiblingCalls; 151 std::string InstrMap; 152 ::llvm::xray::Trace Trace; 153 Expected<GraphRenderer> getGraphRenderer(); 154 }; 155 156 /// Output the Embedded graph in DOT format on \p OS, labeling the edges by 157 /// \p T 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); 162 163 /// Get a reference to the internal graph. getGraph()164 const GraphT &getGraph() { return G; } 165 }; 166 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, 172 A.Sum + B.Sum}; 173 } 174 175 /// Vector Difference of Timestats 176 inline GraphRenderer::TimeStat operator-(const GraphRenderer::TimeStat &A, 177 const GraphRenderer::TimeStat &B) { 178 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, 181 A.Sum - B.Sum}; 182 } 183 184 /// Scalar Diference of TimeStat and double 185 inline GraphRenderer::TimeStat operator/(const GraphRenderer::TimeStat &A, 186 double B) { 187 188 return {static_cast<int64_t>(A.Count / B), 189 A.Min / B, 190 A.Median / B, 191 A.Pct90 / B, 192 A.Pct99 / B, 193 A.Max / B, 194 A.Sum / B}; 195 } 196 197 /// Scalar product of TimeStat and Double 198 inline GraphRenderer::TimeStat operator*(const GraphRenderer::TimeStat &A, 199 double B) { 200 return {static_cast<int64_t>(A.Count * B), 201 A.Min * B, 202 A.Median * B, 203 A.Pct90 * B, 204 A.Pct99 * B, 205 A.Max * B, 206 A.Sum * B}; 207 } 208 209 /// Scalar product of double TimeStat 210 inline GraphRenderer::TimeStat operator*(double A, 211 const GraphRenderer::TimeStat &B) { 212 return B * A; 213 } 214 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, 220 A.Sum * B.Sum}; 221 } 222 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, 228 A.Sum / B.Sum}; 229 } 230 } // namespace xray 231 } // namespace llvm 232 233 #endif // XRAY_GRAPH_H 234