230 lines · c
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-exception6//7//===----------------------------------------------------------------------===//8//9// Generate a DOT file to represent the function call graph encountered in10// the trace.11//12//===----------------------------------------------------------------------===//13 14#ifndef XRAY_GRAPH_H15#define XRAY_GRAPH_H16 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::xray {32 33/// A class encapsulating the logic related to analyzing XRay traces, producting34/// Graphs from them and then exporting those graphs for review.35class GraphRenderer {36public:37 /// An enum for enumerating the various statistics gathered on latencies38 enum class StatType { NONE, COUNT, MIN, MED, PCT90, PCT99, MAX, SUM };39 40 /// An inner struct for common timing statistics information41 struct TimeStat {42 int64_t Count;43 double Min;44 double Median;45 double Pct90;46 double Pct99;47 double Max;48 double Sum;49 50 std::string getString(StatType T) const;51 double getDouble(StatType T) const;52 };53 using TimestampT = uint64_t;54 55 /// An inner struct for storing edge attributes for our graph. Here the56 /// attributes are mainly function call statistics.57 ///58 /// FIXME: expand to contain more information eg call latencies.59 struct CallStats {60 TimeStat S;61 std::vector<TimestampT> Timings;62 };63 64 /// An Inner Struct for storing vertex attributes, at the moment just65 /// SymbolNames, however in future we could store bulk function statistics.66 ///67 /// FIXME: Store more attributes based on instrumentation map.68 struct FunctionStats {69 std::string SymbolName;70 TimeStat S = {};71 };72 73 struct FunctionAttr {74 int32_t FuncId;75 uint64_t TSC;76 };77 78 using FunctionStack = SmallVector<FunctionAttr, 4>;79 80 using PerThreadFunctionStackMap = DenseMap<uint32_t, FunctionStack>;81 82 class GraphT : public Graph<FunctionStats, CallStats, int32_t> {83 public:84 TimeStat GraphEdgeMax = {};85 TimeStat GraphVertexMax = {};86 };87 88 GraphT G;89 using VertexIdentifier = decltype(G)::VertexIdentifier;90 using EdgeIdentifier = decltype(G)::EdgeIdentifier;91 92 /// Use a Map to store the Function stack for each thread whilst building the93 /// graph.94 ///95 /// FIXME: Perhaps we can Build this into LatencyAccountant? or vise versa?96 PerThreadFunctionStackMap PerThreadFunctionStack;97 98 /// Usefull object for getting human readable Symbol Names.99 FuncIdConversionHelper FuncIdHelper;100 bool DeduceSiblingCalls = false;101 TimestampT CurrentMaxTSC = 0;102 103 /// A private function to help implement the statistic generation functions;104 template <typename U>105 void getStats(U begin, U end, GraphRenderer::TimeStat &S);106 void updateMaxStats(const TimeStat &S, TimeStat &M);107 108 /// Calculates latency statistics for each edge and stores the data in the109 /// Graph110 void calculateEdgeStatistics();111 112 /// Calculates latency statistics for each vertex and stores the data in the113 /// Graph114 void calculateVertexStatistics();115 116 /// Normalises latency statistics for each edge and vertex by CycleFrequency;117 void normalizeStatistics(double CycleFrequency);118 119 /// An object to color gradients120 ColorHelper CHelper;121 122public:123 /// Takes in a reference to a FuncIdHelper in order to have ready access to124 /// Symbol names.125 explicit GraphRenderer(const FuncIdConversionHelper &FuncIdHelper, bool DSC)126 : FuncIdHelper(FuncIdHelper), DeduceSiblingCalls(DSC),127 CHelper(ColorHelper::SequentialScheme::OrRd) {128 G[0] = {};129 }130 131 /// Process an Xray record and expand the graph.132 ///133 /// This Function will return true on success, or false if records are not134 /// presented in per-thread call-tree DFS order. (That is for each thread the135 /// Records should be in order runtime on an ideal system.)136 ///137 /// FIXME: Make this more robust against small irregularities.138 Error accountRecord(const XRayRecord &Record);139 140 const PerThreadFunctionStackMap &getPerThreadFunctionStack() const {141 return PerThreadFunctionStack;142 }143 144 class Factory {145 public:146 bool KeepGoing;147 bool DeduceSiblingCalls;148 std::string InstrMap;149 ::llvm::xray::Trace Trace;150 Expected<GraphRenderer> getGraphRenderer();151 };152 153 /// Output the Embedded graph in DOT format on \p OS, labeling the edges by154 /// \p T155 void exportGraphAsDOT(raw_ostream &OS, StatType EdgeLabel = StatType::NONE,156 StatType EdgeColor = StatType::NONE,157 StatType VertexLabel = StatType::NONE,158 StatType VertexColor = StatType::NONE);159 160 /// Get a reference to the internal graph.161 const GraphT &getGraph() { return G; }162};163 164/// Vector Sum of TimeStats165inline GraphRenderer::TimeStat operator+(const GraphRenderer::TimeStat &A,166 const GraphRenderer::TimeStat &B) {167 return {A.Count + B.Count, A.Min + B.Min, A.Median + B.Median,168 A.Pct90 + B.Pct90, A.Pct99 + B.Pct99, A.Max + B.Max,169 A.Sum + B.Sum};170}171 172/// Vector Difference of Timestats173inline GraphRenderer::TimeStat operator-(const GraphRenderer::TimeStat &A,174 const GraphRenderer::TimeStat &B) {175 176 return {A.Count - B.Count, A.Min - B.Min, A.Median - B.Median,177 A.Pct90 - B.Pct90, A.Pct99 - B.Pct99, A.Max - B.Max,178 A.Sum - B.Sum};179}180 181/// Scalar Diference of TimeStat and double182inline GraphRenderer::TimeStat operator/(const GraphRenderer::TimeStat &A,183 double B) {184 185 return {static_cast<int64_t>(A.Count / B),186 A.Min / B,187 A.Median / B,188 A.Pct90 / B,189 A.Pct99 / B,190 A.Max / B,191 A.Sum / B};192}193 194/// Scalar product of TimeStat and Double195inline GraphRenderer::TimeStat operator*(const GraphRenderer::TimeStat &A,196 double B) {197 return {static_cast<int64_t>(A.Count * B),198 A.Min * B,199 A.Median * B,200 A.Pct90 * B,201 A.Pct99 * B,202 A.Max * B,203 A.Sum * B};204}205 206/// Scalar product of double TimeStat207inline GraphRenderer::TimeStat operator*(double A,208 const GraphRenderer::TimeStat &B) {209 return B * A;210}211 212/// Hadamard Product of TimeStats213inline GraphRenderer::TimeStat operator*(const GraphRenderer::TimeStat &A,214 const GraphRenderer::TimeStat &B) {215 return {A.Count * B.Count, A.Min * B.Min, A.Median * B.Median,216 A.Pct90 * B.Pct90, A.Pct99 * B.Pct99, A.Max * B.Max,217 A.Sum * B.Sum};218}219 220/// Hadamard Division of TimeStats221inline GraphRenderer::TimeStat operator/(const GraphRenderer::TimeStat &A,222 const GraphRenderer::TimeStat &B) {223 return {A.Count / B.Count, A.Min / B.Min, A.Median / B.Median,224 A.Pct90 / B.Pct90, A.Pct99 / B.Pct99, A.Max / B.Max,225 A.Sum / B.Sum};226}227} // namespace llvm::xray228 229#endif // XRAY_GRAPH_H230