contrib/llvm/tools/llvm-xray/xray-graph.h

   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.
 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
 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.
 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