1317017Sdim//===-- xray-graph.h - XRay Function Call Graph Renderer --------*- C++ -*-===// 2317017Sdim// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6317017Sdim// 7317017Sdim//===----------------------------------------------------------------------===// 8317017Sdim// 9317017Sdim// Generate a DOT file to represent the function call graph encountered in 10317017Sdim// the trace. 11317017Sdim// 12317017Sdim//===----------------------------------------------------------------------===// 13317017Sdim 14317017Sdim#ifndef XRAY_GRAPH_H 15317017Sdim#define XRAY_GRAPH_H 16317017Sdim 17317017Sdim#include <string> 18317017Sdim#include <vector> 19317017Sdim 20317017Sdim#include "func-id-helper.h" 21317017Sdim#include "xray-color-helper.h" 22317017Sdim#include "llvm/ADT/DenseMap.h" 23317017Sdim#include "llvm/ADT/SmallVector.h" 24317017Sdim#include "llvm/Support/Errc.h" 25317017Sdim#include "llvm/Support/Program.h" 26317017Sdim#include "llvm/Support/raw_ostream.h" 27317017Sdim#include "llvm/XRay/Graph.h" 28317017Sdim#include "llvm/XRay/Trace.h" 29317017Sdim#include "llvm/XRay/XRayRecord.h" 30317017Sdim 31317017Sdimnamespace llvm { 32317017Sdimnamespace xray { 33317017Sdim 34317017Sdim/// A class encapsulating the logic related to analyzing XRay traces, producting 35317017Sdim/// Graphs from them and then exporting those graphs for review. 36317017Sdimclass GraphRenderer { 37317017Sdimpublic: 38317017Sdim /// An enum for enumerating the various statistics gathered on latencies 39317017Sdim enum class StatType { NONE, COUNT, MIN, MED, PCT90, PCT99, MAX, SUM }; 40317017Sdim 41317017Sdim /// An inner struct for common timing statistics information 42317017Sdim struct TimeStat { 43317472Sdim int64_t Count; 44317472Sdim double Min; 45317472Sdim double Median; 46317472Sdim double Pct90; 47317472Sdim double Pct99; 48317472Sdim double Max; 49317472Sdim double Sum; 50317472Sdim 51317472Sdim std::string getString(StatType T) const; 52317472Sdim double getDouble(StatType T) const; 53317017Sdim }; 54317472Sdim using TimestampT = uint64_t; 55317017Sdim 56317017Sdim /// An inner struct for storing edge attributes for our graph. Here the 57317017Sdim /// attributes are mainly function call statistics. 58317017Sdim /// 59317017Sdim /// FIXME: expand to contain more information eg call latencies. 60317017Sdim struct CallStats { 61317017Sdim TimeStat S; 62317017Sdim std::vector<TimestampT> Timings; 63317017Sdim }; 64317017Sdim 65317017Sdim /// An Inner Struct for storing vertex attributes, at the moment just 66317017Sdim /// SymbolNames, however in future we could store bulk function statistics. 67317017Sdim /// 68317017Sdim /// FIXME: Store more attributes based on instrumentation map. 69317017Sdim struct FunctionStats { 70317017Sdim std::string SymbolName; 71317472Sdim TimeStat S = {}; 72317017Sdim }; 73317017Sdim 74317017Sdim struct FunctionAttr { 75317017Sdim int32_t FuncId; 76317017Sdim uint64_t TSC; 77317017Sdim }; 78317017Sdim 79317472Sdim using FunctionStack = SmallVector<FunctionAttr, 4>; 80317017Sdim 81353358Sdim using PerThreadFunctionStackMap = DenseMap<uint32_t, FunctionStack>; 82317017Sdim 83317017Sdim class GraphT : public Graph<FunctionStats, CallStats, int32_t> { 84317017Sdim public: 85317017Sdim TimeStat GraphEdgeMax = {}; 86317017Sdim TimeStat GraphVertexMax = {}; 87317017Sdim }; 88317017Sdim 89317017Sdim GraphT G; 90317472Sdim using VertexIdentifier = typename decltype(G)::VertexIdentifier; 91317472Sdim using EdgeIdentifier = decltype(G)::EdgeIdentifier; 92317017Sdim 93317017Sdim /// Use a Map to store the Function stack for each thread whilst building the 94317017Sdim /// graph. 95317017Sdim /// 96317017Sdim /// FIXME: Perhaps we can Build this into LatencyAccountant? or vise versa? 97317017Sdim PerThreadFunctionStackMap PerThreadFunctionStack; 98317017Sdim 99317017Sdim /// Usefull object for getting human readable Symbol Names. 100317472Sdim FuncIdConversionHelper FuncIdHelper; 101317017Sdim bool DeduceSiblingCalls = false; 102317017Sdim TimestampT CurrentMaxTSC = 0; 103317017Sdim 104317017Sdim /// A private function to help implement the statistic generation functions; 105317017Sdim template <typename U> 106317017Sdim void getStats(U begin, U end, GraphRenderer::TimeStat &S); 107317017Sdim void updateMaxStats(const TimeStat &S, TimeStat &M); 108317017Sdim 109317017Sdim /// Calculates latency statistics for each edge and stores the data in the 110317017Sdim /// Graph 111317017Sdim void calculateEdgeStatistics(); 112317017Sdim 113317017Sdim /// Calculates latency statistics for each vertex and stores the data in the 114317017Sdim /// Graph 115317017Sdim void calculateVertexStatistics(); 116317017Sdim 117317017Sdim /// Normalises latency statistics for each edge and vertex by CycleFrequency; 118317017Sdim void normalizeStatistics(double CycleFrequency); 119317017Sdim 120317017Sdim /// An object to color gradients 121317017Sdim ColorHelper CHelper; 122317017Sdim 123317017Sdimpublic: 124317017Sdim /// Takes in a reference to a FuncIdHelper in order to have ready access to 125317017Sdim /// Symbol names. 126317017Sdim explicit GraphRenderer(const FuncIdConversionHelper &FuncIdHelper, bool DSC) 127317017Sdim : FuncIdHelper(FuncIdHelper), DeduceSiblingCalls(DSC), 128317017Sdim CHelper(ColorHelper::SequentialScheme::OrRd) { 129317017Sdim G[0] = {}; 130317017Sdim } 131317017Sdim 132317017Sdim /// Process an Xray record and expand the graph. 133317017Sdim /// 134317017Sdim /// This Function will return true on success, or false if records are not 135317017Sdim /// presented in per-thread call-tree DFS order. (That is for each thread the 136317017Sdim /// Records should be in order runtime on an ideal system.) 137317017Sdim /// 138317017Sdim /// FIXME: Make this more robust against small irregularities. 139317017Sdim Error accountRecord(const XRayRecord &Record); 140317017Sdim 141317017Sdim const PerThreadFunctionStackMap &getPerThreadFunctionStack() const { 142317017Sdim return PerThreadFunctionStack; 143317017Sdim } 144317017Sdim 145317472Sdim class Factory { 146317472Sdim public: 147317472Sdim bool KeepGoing; 148317472Sdim bool DeduceSiblingCalls; 149317472Sdim std::string InstrMap; 150317472Sdim ::llvm::xray::Trace Trace; 151317472Sdim Expected<GraphRenderer> getGraphRenderer(); 152317472Sdim }; 153317472Sdim 154317017Sdim /// Output the Embedded graph in DOT format on \p OS, labeling the edges by 155317017Sdim /// \p T 156317472Sdim void exportGraphAsDOT(raw_ostream &OS, StatType EdgeLabel = StatType::NONE, 157317017Sdim StatType EdgeColor = StatType::NONE, 158317017Sdim StatType VertexLabel = StatType::NONE, 159317017Sdim StatType VertexColor = StatType::NONE); 160317017Sdim 161317017Sdim /// Get a reference to the internal graph. 162317472Sdim const GraphT &getGraph() { return G; } 163317017Sdim}; 164317472Sdim 165317472Sdim/// Vector Sum of TimeStats 166317472Sdiminline GraphRenderer::TimeStat operator+(const GraphRenderer::TimeStat &A, 167317472Sdim const GraphRenderer::TimeStat &B) { 168317472Sdim return {A.Count + B.Count, A.Min + B.Min, A.Median + B.Median, 169317472Sdim A.Pct90 + B.Pct90, A.Pct99 + B.Pct99, A.Max + B.Max, 170317472Sdim A.Sum + B.Sum}; 171317017Sdim} 172317472Sdim 173317472Sdim/// Vector Difference of Timestats 174317472Sdiminline GraphRenderer::TimeStat operator-(const GraphRenderer::TimeStat &A, 175317472Sdim const GraphRenderer::TimeStat &B) { 176317472Sdim 177317472Sdim return {A.Count - B.Count, A.Min - B.Min, A.Median - B.Median, 178317472Sdim A.Pct90 - B.Pct90, A.Pct99 - B.Pct99, A.Max - B.Max, 179317472Sdim A.Sum - B.Sum}; 180317017Sdim} 181317017Sdim 182317472Sdim/// Scalar Diference of TimeStat and double 183317472Sdiminline GraphRenderer::TimeStat operator/(const GraphRenderer::TimeStat &A, 184317472Sdim double B) { 185317472Sdim 186317472Sdim return {static_cast<int64_t>(A.Count / B), 187317472Sdim A.Min / B, 188317472Sdim A.Median / B, 189317472Sdim A.Pct90 / B, 190317472Sdim A.Pct99 / B, 191317472Sdim A.Max / B, 192317472Sdim A.Sum / B}; 193317472Sdim} 194317472Sdim 195317472Sdim/// Scalar product of TimeStat and Double 196317472Sdiminline GraphRenderer::TimeStat operator*(const GraphRenderer::TimeStat &A, 197317472Sdim double B) { 198317472Sdim return {static_cast<int64_t>(A.Count * B), 199317472Sdim A.Min * B, 200317472Sdim A.Median * B, 201317472Sdim A.Pct90 * B, 202317472Sdim A.Pct99 * B, 203317472Sdim A.Max * B, 204317472Sdim A.Sum * B}; 205317472Sdim} 206317472Sdim 207317472Sdim/// Scalar product of double TimeStat 208317472Sdiminline GraphRenderer::TimeStat operator*(double A, 209317472Sdim const GraphRenderer::TimeStat &B) { 210317472Sdim return B * A; 211317472Sdim} 212317472Sdim 213317472Sdim/// Hadamard Product of TimeStats 214317472Sdiminline GraphRenderer::TimeStat operator*(const GraphRenderer::TimeStat &A, 215317472Sdim const GraphRenderer::TimeStat &B) { 216317472Sdim return {A.Count * B.Count, A.Min * B.Min, A.Median * B.Median, 217317472Sdim A.Pct90 * B.Pct90, A.Pct99 * B.Pct99, A.Max * B.Max, 218317472Sdim A.Sum * B.Sum}; 219317472Sdim} 220317472Sdim 221317472Sdim/// Hadamard Division of TimeStats 222317472Sdiminline GraphRenderer::TimeStat operator/(const GraphRenderer::TimeStat &A, 223317472Sdim const GraphRenderer::TimeStat &B) { 224317472Sdim return {A.Count / B.Count, A.Min / B.Min, A.Median / B.Median, 225317472Sdim A.Pct90 / B.Pct90, A.Pct99 / B.Pct99, A.Max / B.Max, 226317472Sdim A.Sum / B.Sum}; 227317472Sdim} 228317472Sdim} // namespace xray 229317472Sdim} // namespace llvm 230317472Sdim 231317017Sdim#endif // XRAY_GRAPH_H 232