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 =
  82       DenseMap<llvm::sys::procid_t, FunctionStack>;
  83
  84   class GraphT : public Graph<FunctionStats, CallStats, int32_t> {
  85   public:
  86     TimeStat GraphEdgeMax = {};
  87     TimeStat GraphVertexMax = {};
  88   };
  89
  90   GraphT G;
  91   using VertexIdentifier = typename decltype(G)::VertexIdentifier;
  92   using EdgeIdentifier = decltype(G)::EdgeIdentifier;
  93
  94   /// Use a Map to store the Function stack for each thread whilst building the
  95   /// graph.
  96   ///
  97   /// FIXME: Perhaps we can Build this into LatencyAccountant? or vise versa?
  98   PerThreadFunctionStackMap PerThreadFunctionStack;
  99
 100   /// Usefull object for getting human readable Symbol Names.
 101   FuncIdConversionHelper FuncIdHelper;
 102   bool DeduceSiblingCalls = false;
 103   TimestampT CurrentMaxTSC = 0;
 104
 105   /// A private function to help implement the statistic generation functions;
 106   template <typename U>
 107   void getStats(U begin, U end, GraphRenderer::TimeStat &S);
 108   void updateMaxStats(const TimeStat &S, TimeStat &M);
 109
 110   /// Calculates latency statistics for each edge and stores the data in the
 111   /// Graph
 112   void calculateEdgeStatistics();
 113
 114   /// Calculates latency statistics for each vertex and stores the data in the
 115   /// Graph
 116   void calculateVertexStatistics();
 117
 118   /// Normalises latency statistics for each edge and vertex by CycleFrequency;
 119   void normalizeStatistics(double CycleFrequency);
 120
 121   /// An object to color gradients
 122   ColorHelper CHelper;
 123
 124 public:
 125   /// Takes in a reference to a FuncIdHelper in order to have ready access to
 126   /// Symbol names.
 127   explicit GraphRenderer(const FuncIdConversionHelper &FuncIdHelper, bool DSC)
 128       : FuncIdHelper(FuncIdHelper), DeduceSiblingCalls(DSC),
 129         CHelper(ColorHelper::SequentialScheme::OrRd) {
 130     G[0] = {};
 131   }
 132
 133   /// Process an Xray record and expand the graph.
 134   ///
 135   /// This Function will return true on success, or false if records are not
 136   /// presented in per-thread call-tree DFS order. (That is for each thread the
 137   /// Records should be in order runtime on an ideal system.)
 138   ///
 139   /// FIXME: Make this more robust against small irregularities.
 140   Error accountRecord(const XRayRecord &Record);
 141
 142   const PerThreadFunctionStackMap &getPerThreadFunctionStack() const {
 143     return PerThreadFunctionStack;
 144   }
 145
 146   class Factory {
 147   public:
 148     bool KeepGoing;
 149     bool DeduceSiblingCalls;
 150     std::string InstrMap;
 151     ::llvm::xray::Trace Trace;
 152     Expected<GraphRenderer> getGraphRenderer();
 153   };
 154
 155   /// Output the Embedded graph in DOT format on \p OS, labeling the edges by
 156   /// \p T
 157   void exportGraphAsDOT(raw_ostream &OS, StatType EdgeLabel = StatType::NONE,
 158                         StatType EdgeColor = StatType::NONE,
 159                         StatType VertexLabel = StatType::NONE,
 160                         StatType VertexColor = StatType::NONE);
 161
 162   /// Get a reference to the internal graph.
 163   const GraphT &getGraph() { return G; }
 164 };
 165
 166 /// Vector Sum of TimeStats
 167 inline GraphRenderer::TimeStat operator+(const GraphRenderer::TimeStat &A,
 168                                          const GraphRenderer::TimeStat &B) {
 169   return {A.Count + B.Count, A.Min + B.Min,     A.Median + B.Median,
 170           A.Pct90 + B.Pct90, A.Pct99 + B.Pct99, A.Max + B.Max,
 171           A.Sum + B.Sum};
 172 }
 173
 174 /// Vector Difference of Timestats
 175 inline GraphRenderer::TimeStat operator-(const GraphRenderer::TimeStat &A,
 176                                          const GraphRenderer::TimeStat &B) {
 177
 178   return {A.Count - B.Count, A.Min - B.Min,     A.Median - B.Median,
 179           A.Pct90 - B.Pct90, A.Pct99 - B.Pct99, A.Max - B.Max,
 180           A.Sum - B.Sum};
 181 }
 182
 183 /// Scalar Diference of TimeStat and double
 184 inline GraphRenderer::TimeStat operator/(const GraphRenderer::TimeStat &A,
 185                                          double B) {
 186
 187   return {static_cast<int64_t>(A.Count / B),
 188           A.Min / B,
 189           A.Median / B,
 190           A.Pct90 / B,
 191           A.Pct99 / B,
 192           A.Max / B,
 193           A.Sum / B};
 194 }
 195
 196 /// Scalar product of TimeStat and Double
 197 inline GraphRenderer::TimeStat operator*(const GraphRenderer::TimeStat &A,
 198                                          double B) {
 199   return {static_cast<int64_t>(A.Count * B),
 200           A.Min * B,
 201           A.Median * B,
 202           A.Pct90 * B,
 203           A.Pct99 * B,
 204           A.Max * B,
 205           A.Sum * B};
 206 }
 207
 208 /// Scalar product of double TimeStat
 209 inline GraphRenderer::TimeStat operator*(double A,
 210                                          const GraphRenderer::TimeStat &B) {
 211   return B * A;
 212 }
 213
 214 /// Hadamard Product of TimeStats
 215 inline GraphRenderer::TimeStat operator*(const GraphRenderer::TimeStat &A,
 216                                          const GraphRenderer::TimeStat &B) {
 217   return {A.Count * B.Count, A.Min * B.Min,     A.Median * B.Median,
 218           A.Pct90 * B.Pct90, A.Pct99 * B.Pct99, A.Max * B.Max,
 219           A.Sum * B.Sum};
 220 }
 221
 222 /// Hadamard Division of TimeStats
 223 inline GraphRenderer::TimeStat operator/(const GraphRenderer::TimeStat &A,
 224                                          const GraphRenderer::TimeStat &B) {
 225   return {A.Count / B.Count, A.Min / B.Min,     A.Median / B.Median,
 226           A.Pct90 / B.Pct90, A.Pct99 / B.Pct99, A.Max / B.Max,
 227           A.Sum / B.Sum};
 228 }
 229 } // namespace xray
 230 } // namespace llvm
 231
 232 #endif // XRAY_GRAPH_H