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     uint64_t Count = 0;
  45     double Min = 0;
  46     double Median = 0;
  47     double Pct90 = 0;
  48     double Pct99 = 0;
  49     double Max = 0;
  50     double Sum = 0;
  51     std::string getAsString(StatType T) const;
  52     double compare(StatType T, const TimeStat &Other) const;
  53   };
  54   typedef uint64_t TimestampT;
  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   typedef SmallVector<FunctionAttr, 4> FunctionStack;
  80
  81   typedef DenseMap<llvm::sys::ProcessInfo::ProcessId, FunctionStack>
  82       PerThreadFunctionStackMap;
  83
  84   class GraphT : public Graph<FunctionStats, CallStats, int32_t> {
  85   public:
  86     TimeStat GraphEdgeMax = {};
  87     TimeStat GraphVertexMax = {};
  88   };
  89
  90   GraphT G;
  91   typedef typename decltype(G)::VertexIdentifier VertexIdentifier;
  92   typedef typename decltype(G)::EdgeIdentifier 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   const 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   /// Output the Embedded graph in DOT format on \p OS, labeling the edges by
 147   /// \p T
 148   void exportGraphAsDOT(raw_ostream &OS, const XRayFileHeader &H,
 149                         StatType EdgeLabel = StatType::NONE,
 150                         StatType EdgeColor = StatType::NONE,
 151                         StatType VertexLabel = StatType::NONE,
 152                         StatType VertexColor = StatType::NONE);
 153
 154   /// Get a reference to the internal graph.
 155   const GraphT &getGraph() {
 156     calculateEdgeStatistics();
 157     calculateVertexStatistics();
 158     return G;
 159   }
 160 };
 161 }
 162 }
 163
 164 #endif // XRAY_GRAPH_H