tools/llvm-xray/xray-graph.h

   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