[XRay] A graph Class for the llvm-xray graph

Summary:
In preparation for graph comparison and filtering, this is a library for
representing graphs in LLVM. This will enable easier encapsulation and reuse
of graphs in llvm-xray.

Depends on D28999, D28225

Reviewers: dblaikie, dberris

Reviewed By: dberris

Subscribers: mgorny, llvm-commits

Differential Revision: https://reviews.llvm.org/D29005

llvm-svn: 294717

2 files changed, 104 insertions, 96 deletions

diff --git a/llvm/tools/llvm-xray/xray-graph.cc b/llvm/tools/llvm-xray/xray-graph.cc
index 3780ce8672e..e2ce9318cd5 100644
--- a/llvm/tools/llvm-xray/xray-graph.cc
+++ b/llvm/tools/llvm-xray/xray-graph.cc
@@ -1,4 +1,4 @@
-//===-- xray-graph.c - XRay Function Call Graph Renderer ------------------===//
+//===-- xray-graph.cc - XRay Function Call Graph Renderer -----------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
@@ -30,45 +30,47 @@ using namespace llvm;
 using namespace llvm::xray;
 
 // Setup llvm-xray graph subcommand and its options.
-static cl::SubCommand Graph("graph", "Generate function-call graph");
+static cl::SubCommand GraphC("graph", "Generate function-call graph");
 static cl::opt<std::string> GraphInput(cl::Positional,
                                        cl::desc("<xray log file>"),
-                                       cl::Required, cl::sub(Graph));
+                                       cl::Required, cl::sub(GraphC));
 
 static cl::opt<bool>
     GraphKeepGoing("keep-going", cl::desc("Keep going on errors encountered"),
-                   cl::sub(Graph), cl::init(false));
+                   cl::sub(GraphC), cl::init(false));
 static cl::alias GraphKeepGoing2("k", cl::aliasopt(GraphKeepGoing),
                                  cl::desc("Alias for -keep-going"),
-                                 cl::sub(Graph));
+                                 cl::sub(GraphC));
 
 static cl::opt<std::string>
     GraphOutput("output", cl::value_desc("Output file"), cl::init("-"),
-                cl::desc("output file; use '-' for stdout"), cl::sub(Graph));
+                cl::desc("output file; use '-' for stdout"), cl::sub(GraphC));
 static cl::alias GraphOutput2("o", cl::aliasopt(GraphOutput),
-                              cl::desc("Alias for -output"), cl::sub(Graph));
+                              cl::desc("Alias for -output"), cl::sub(GraphC));
 
-static cl::opt<std::string> GraphInstrMap(
-    "instr_map", cl::desc("binary with the instrumrntation map, or "
-                          "a separate instrumentation map"),
-    cl::value_desc("binary with xray_instr_map"), cl::sub(Graph), cl::init(""));
+static cl::opt<std::string>
+    GraphInstrMap("instr_map",
+                  cl::desc("binary with the instrumrntation map, or "
+                           "a separate instrumentation map"),
+                  cl::value_desc("binary with xray_instr_map"), cl::sub(GraphC),
+                  cl::init(""));
 static cl::alias GraphInstrMap2("m", cl::aliasopt(GraphInstrMap),
                                 cl::desc("alias for -instr_map"),
-                                cl::sub(Graph));
+                                cl::sub(GraphC));
 
 static cl::opt<bool> GraphDeduceSiblingCalls(
     "deduce-sibling-calls",
     cl::desc("Deduce sibling calls when unrolling function call stacks"),
-    cl::sub(Graph), cl::init(false));
+    cl::sub(GraphC), cl::init(false));
 static cl::alias
     GraphDeduceSiblingCalls2("d", cl::aliasopt(GraphDeduceSiblingCalls),
                              cl::desc("Alias for -deduce-sibling-calls"),
-                             cl::sub(Graph));
+                             cl::sub(GraphC));
 
 static cl::opt<GraphRenderer::StatType>
     GraphEdgeLabel("edge-label",
                    cl::desc("Output graphs with edges labeled with this field"),
-                   cl::value_desc("field"), cl::sub(Graph),
+                   cl::value_desc("field"), cl::sub(GraphC),
                    cl::init(GraphRenderer::StatType::NONE),
                    cl::values(clEnumValN(GraphRenderer::StatType::NONE, "none",
                                          "Do not label Edges"),
@@ -88,12 +90,12 @@ static cl::opt<GraphRenderer::StatType>
                                          "sum of call durations")));
 static cl::alias GraphEdgeLabel2("e", cl::aliasopt(GraphEdgeLabel),
                                  cl::desc("Alias for -edge-label"),
-                                 cl::sub(Graph));
+                                 cl::sub(GraphC));
 
 static cl::opt<GraphRenderer::StatType> GraphVertexLabel(
     "vertex-label",
     cl::desc("Output graphs with vertices labeled with this field"),
-    cl::value_desc("field"), cl::sub(Graph),
+    cl::value_desc("field"), cl::sub(GraphC),
     cl::init(GraphRenderer::StatType::NONE),
     cl::values(clEnumValN(GraphRenderer::StatType::NONE, "none",
                           "Do not label Edges"),
@@ -113,12 +115,12 @@ static cl::opt<GraphRenderer::StatType> GraphVertexLabel(
                           "sum of call durations")));
 static cl::alias GraphVertexLabel2("v", cl::aliasopt(GraphVertexLabel),
                                    cl::desc("Alias for -edge-label"),
-                                   cl::sub(Graph));
+                                   cl::sub(GraphC));
 
 static cl::opt<GraphRenderer::StatType> GraphEdgeColorType(
     "color-edges",
     cl::desc("Output graphs with edge colors determined by this field"),
-    cl::value_desc("field"), cl::sub(Graph),
+    cl::value_desc("field"), cl::sub(GraphC),
     cl::init(GraphRenderer::StatType::NONE),
     cl::values(clEnumValN(GraphRenderer::StatType::NONE, "none",
                           "Do not label Edges"),
@@ -138,12 +140,12 @@ static cl::opt<GraphRenderer::StatType> GraphEdgeColorType(
                           "sum of call durations")));
 static cl::alias GraphEdgeColorType2("c", cl::aliasopt(GraphEdgeColorType),
                                      cl::desc("Alias for -color-edges"),
-                                     cl::sub(Graph));
+                                     cl::sub(GraphC));
 
 static cl::opt<GraphRenderer::StatType> GraphVertexColorType(
     "color-vertices",
     cl::desc("Output graphs with vertex colors determined by this field"),
-    cl::value_desc("field"), cl::sub(Graph),
+    cl::value_desc("field"), cl::sub(GraphC),
     cl::init(GraphRenderer::StatType::NONE),
     cl::values(clEnumValN(GraphRenderer::StatType::NONE, "none",
                           "Do not label Edges"),
@@ -163,7 +165,7 @@ static cl::opt<GraphRenderer::StatType> GraphVertexColorType(
                           "sum of call durations")));
 static cl::alias GraphVertexColorType2("b", cl::aliasopt(GraphVertexColorType),
                                        cl::desc("Alias for -edge-label"),
-                                       cl::sub(Graph));
+                                       cl::sub(GraphC));
 
 template <class T> T diff(T L, T R) { return std::max(L, R) - std::min(L, R); }
 
@@ -208,14 +210,13 @@ Error GraphRenderer::accountRecord(const XRayRecord &Record) {
   auto &ThreadStack = PerThreadFunctionStack[Record.TId];
   switch (Record.Type) {
   case RecordTypes::ENTER: {
-    if (VertexAttrs.count(Record.FuncId) == 0)
-      VertexAttrs[Record.FuncId].SymbolName =
-          FuncIdHelper.SymbolOrNumber(Record.FuncId);
+    if (G.count(Record.FuncId) == 0)
+      G[Record.FuncId].SymbolName = FuncIdHelper.SymbolOrNumber(Record.FuncId);
     ThreadStack.push_back({Record.FuncId, Record.TSC});
     break;
   }
   case RecordTypes::EXIT: {
-    // FIXME: Refactor this and the account subcommand to reducr code
+    // FIXME: Refactor this and the account subcommand to reduce code
     // duplication
     if (ThreadStack.size() == 0 || ThreadStack.back().FuncId != Record.FuncId) {
       if (!DeduceSiblingCalls)
@@ -230,23 +231,25 @@ Error GraphRenderer::accountRecord(const XRayRecord &Record) {
             make_error_code(errc::invalid_argument)); // There is no matching
                                                       // Function for this exit.
       while (ThreadStack.back().FuncId != Record.FuncId) {
-        uint64_t D = diff(ThreadStack.back().TSC, Record.TSC);
-        int32_t TopFuncId = ThreadStack.back().FuncId;
+        TimestampT D = diff(ThreadStack.back().TSC, Record.TSC);
+        VertexIdentifier TopFuncId = ThreadStack.back().FuncId;
         ThreadStack.pop_back();
         assert(ThreadStack.size() != 0);
-        auto &EA = Graph[ThreadStack.back().FuncId][TopFuncId];
+        EdgeIdentifier EI(ThreadStack.back().FuncId, TopFuncId);
+        auto &EA = G[EI];
         EA.Timings.push_back(D);
         updateStat(EA.S, D);
-        updateStat(VertexAttrs[TopFuncId].S, D);
+        updateStat(G[TopFuncId].S, D);
       }
     }
     uint64_t D = diff(ThreadStack.back().TSC, Record.TSC);
     ThreadStack.pop_back();
-    auto &V = Graph[ThreadStack.empty() ? 0 : ThreadStack.back().FuncId];
-    auto &EA = V[Record.FuncId];
+    VertexIdentifier VI = ThreadStack.empty() ? 0 : ThreadStack.back().FuncId;
+    EdgeIdentifier EI(VI, Record.FuncId);
+    auto &EA = G[EI];
     EA.Timings.push_back(D);
     updateStat(EA.S, D);
-    updateStat(VertexAttrs[Record.FuncId].S, D);
+    updateStat(G[Record.FuncId].S, D);
     break;
   }
   }
@@ -280,38 +283,33 @@ void GraphRenderer::updateMaxStats(const GraphRenderer::TimeStat &S,
 }
 
 void GraphRenderer::calculateEdgeStatistics() {
-  for (auto &V : Graph) {
-    for (auto &E : V.second) {
-      auto &A = E.second;
-      getStats(A.Timings.begin(), A.Timings.end(), A.S);
-      updateMaxStats(A.S, GraphEdgeMax);
-    }
+  assert(!G.edges().empty());
+  for (auto &E : G.edges()) {
+    auto &A = E.second;
+    assert(!A.Timings.empty());
+    assert((A.Timings[0] > 0));
+    getStats(A.Timings.begin(), A.Timings.end(), A.S);
+    assert(A.S.Sum > 0);
+    updateMaxStats(A.S, G.GraphEdgeMax);
   }
 }
 
 void GraphRenderer::calculateVertexStatistics() {
-  DenseMap<int32_t, std::pair<uint64_t, SmallVector<EdgeAttribute *, 4>>>
-      IncommingEdges;
-  uint64_t MaxCount = 0;
-  for (auto &V : Graph) {
-    for (auto &E : V.second) {
-      auto &IEV = IncommingEdges[E.first];
-      IEV.second.push_back(&E.second);
-      IEV.first += E.second.S.Count;
-      if (IEV.first > MaxCount)
-        MaxCount = IEV.first;
-    }
-  }
   std::vector<uint64_t> TempTimings;
-  TempTimings.reserve(MaxCount);
-  for (auto &V : IncommingEdges) {
-    for (auto &P : V.second.second) {
-      TempTimings.insert(TempTimings.end(), P->Timings.begin(),
-                         P->Timings.end());
+  for (auto &V : G.vertices()) {
+    assert((V.first == 0 || G[V.first].S.Sum != 0) &&
+           "Every non-root vertex should have at least one call");
+    if (V.first != 0) {
+      for (auto &E : G.inEdges(V.first)) {
+        auto &A = E.second;
+        TempTimings.insert(TempTimings.end(), A.Timings.begin(),
+                           A.Timings.end());
+      }
+      assert(!TempTimings.empty() && TempTimings[0] > 0);
+      getStats(TempTimings.begin(), TempTimings.end(), G[V.first].S);
+      updateMaxStats(G[V.first].S, G.GraphVertexMax);
+      TempTimings.clear();
     }
-    getStats(TempTimings.begin(), TempTimings.end(), VertexAttrs[V.first].S);
-    updateMaxStats(VertexAttrs[V.first].S, GraphVertexMax);
-    TempTimings.clear();
   }
 }
 
@@ -329,19 +327,17 @@ static void normalizeTimeStat(GraphRenderer::TimeStat &S,
 
 // Normalises the statistics in the graph for a given TSC frequency.
 void GraphRenderer::normalizeStatistics(double CycleFrequency) {
-  for (auto &V : Graph) {
-    for (auto &E : V.second) {
-      auto &S = E.second.S;
-      normalizeTimeStat(S, CycleFrequency);
-    }
+  for (auto &E : G.edges()) {
+    auto &S = E.second.S;
+    normalizeTimeStat(S, CycleFrequency);
   }
-  for (auto &V : VertexAttrs) {
+  for (auto &V : G.vertices()) {
     auto &S = V.second.S;
     normalizeTimeStat(S, CycleFrequency);
   }
 
-  normalizeTimeStat(GraphEdgeMax, CycleFrequency);
-  normalizeTimeStat(GraphVertexMax, CycleFrequency);
+  normalizeTimeStat(G.GraphEdgeMax, CycleFrequency);
+  normalizeTimeStat(G.GraphVertexMax, CycleFrequency);
 }
 
 // Returns a string containing the value of statistic field T
@@ -477,8 +473,11 @@ double GraphRenderer::TimeStat::compare(StatType T, const TimeStat &O) const {
 void GraphRenderer::exportGraphAsDOT(raw_ostream &OS, const XRayFileHeader &H,
                                      StatType ET, StatType EC, StatType VT,
                                      StatType VC) {
+  G.GraphEdgeMax = {};
+  G.GraphVertexMax = {};
   calculateEdgeStatistics();
   calculateVertexStatistics();
+
   if (H.CycleFrequency)
     normalizeStatistics(H.CycleFrequency);
 
@@ -487,18 +486,19 @@ void GraphRenderer::exportGraphAsDOT(raw_ostream &OS, const XRayFileHeader &H,
   if (VT != StatType::NONE)
     OS << "node [shape=record];\n";
 
-  for (const auto &V : Graph)
-    for (const auto &E : V.second) {
-      const auto &S = E.second.S;
-      OS << "F" << V.first << " -> "
-         << "F" << E.first << " [label=\"" << S.getAsString(ET) << "\"";
-      if (EC != StatType::NONE)
-        OS << " color=\"" << getColor(S.compare(EC, GraphEdgeMax)) << "\"";
-      OS << "];\n";
-    }
+  for (const auto &E : G.edges()) {
+    const auto &S = E.second.S;
+    OS << "F" << E.first.first << " -> "
+       << "F" << E.first.second << " [label=\"" << S.getAsString(ET) << "\"";
+    if (EC != StatType::NONE)
+      OS << " color=\"" << getColor(S.compare(EC, G.GraphEdgeMax)) << "\"";
+    OS << "];\n";
+  }
 
-  for (const auto &V : VertexAttrs) {
+  for (const auto &V : G.vertices()) {
     const auto &VA = V.second;
+    if (V.first == 0)
+      continue;
     OS << "F" << V.first << " [label=\"" << (VT != StatType::NONE ? "{" : "")
        << (VA.SymbolName.size() > 40 ? VA.SymbolName.substr(0, 40) + "..."
                                      : VA.SymbolName);
@@ -507,7 +507,7 @@ void GraphRenderer::exportGraphAsDOT(raw_ostream &OS, const XRayFileHeader &H,
     else
       OS << "\"";
     if (VC != StatType::NONE)
-      OS << " color=\"" << getColor(VA.S.compare(VC, GraphVertexMax)) << "\"";
+      OS << " color=\"" << getColor(VA.S.compare(VC, G.GraphVertexMax)) << "\"";
     OS << "];\n";
   }
   OS << "}\n";
@@ -521,7 +521,7 @@ void GraphRenderer::exportGraphAsDOT(raw_ostream &OS, const XRayFileHeader &H,
 //
 // FIXME: include additional filtering and annalysis passes to provide more
 // specific useful information.
-static CommandRegistration Unused(&Graph, []() -> Error {
+static CommandRegistration Unused(&GraphC, []() -> Error {
   InstrumentationMap Map;
   if (!GraphInstrMap.empty()) {
     auto InstrumentationMapOrError = loadInstrumentationMap(GraphInstrMap);
@@ -581,7 +581,6 @@ static CommandRegistration Unused(&Graph, []() -> Error {
     handleAllErrors(std::move(E),
                     [&](const ErrorInfoBase &E) { E.log(errs()); });
   }
-
   GR.exportGraphAsDOT(OS, Header, GraphEdgeLabel, GraphEdgeColorType,
                       GraphVertexLabel, GraphVertexColorType);
   return Error::success();
diff --git a/llvm/tools/llvm-xray/xray-graph.h b/llvm/tools/llvm-xray/xray-graph.h
index 8b0e2082520..fd8ac17f902 100644
--- a/llvm/tools/llvm-xray/xray-graph.h
+++ b/llvm/tools/llvm-xray/xray-graph.h
@@ -24,6 +24,7 @@
 #include "llvm/Support/Errc.h"
 #include "llvm/Support/Program.h"
 #include "llvm/Support/raw_ostream.h"
+#include "llvm/XRay/Graph.h"
 #include "llvm/XRay/Trace.h"
 #include "llvm/XRay/XRayRecord.h"
 
@@ -49,21 +50,22 @@ public:
     std::string getAsString(StatType T) const;
     double compare(StatType T, const TimeStat &Other) const;
   };
+  typedef uint64_t TimestampT;
 
   /// An inner struct for storing edge attributes for our graph. Here the
   /// attributes are mainly function call statistics.
   ///
   /// FIXME: expand to contain more information eg call latencies.
-  struct EdgeAttribute {
+  struct CallStats {
     TimeStat S;
-    std::vector<uint64_t> Timings;
+    std::vector<TimestampT> Timings;
   };
 
   /// An Inner Struct for storing vertex attributes, at the moment just
   /// SymbolNames, however in future we could store bulk function statistics.
   ///
   /// FIXME: Store more attributes based on instrumentation map.
-  struct VertexAttribute {
+  struct FunctionStats {
     std::string SymbolName;
     TimeStat S;
   };
@@ -78,17 +80,15 @@ public:
   typedef DenseMap<llvm::sys::ProcessInfo::ProcessId, FunctionStack>
       PerThreadFunctionStackMap;
 
-private:
-  /// The Graph stored in an edge-list like format, with the edges also having
-  /// An attached set of attributes.
-  DenseMap<int32_t, DenseMap<int32_t, EdgeAttribute>> Graph;
-
-  /// Graph Vertex Attributes. These are presently stored seperate from the
-  /// main graph.
-  DenseMap<int32_t, VertexAttribute> VertexAttrs;
+  class GraphT : public Graph<FunctionStats, CallStats, int32_t> {
+  public:
+    TimeStat GraphEdgeMax = {};
+    TimeStat GraphVertexMax = {};
+  };
 
-  TimeStat GraphEdgeMax;
-  TimeStat GraphVertexMax;
+  GraphT G;
+  typedef typename decltype(G)::VertexIdentifier VertexIdentifier;
+  typedef typename decltype(G)::EdgeIdentifier EdgeIdentifier;
 
   /// Use a Map to store the Function stack for each thread whilst building the
   /// graph.
@@ -99,7 +99,7 @@ private:
   /// Usefull object for getting human readable Symbol Names.
   FuncIdConversionHelper &FuncIdHelper;
   bool DeduceSiblingCalls = false;
-  uint64_t CurrentMaxTSC = 0;
+  TimestampT CurrentMaxTSC = 0;
 
   /// A private function to help implement the statistic generation functions;
   template <typename U>
@@ -121,7 +121,9 @@ public:
   /// Takes in a reference to a FuncIdHelper in order to have ready access to
   /// Symbol names.
   explicit GraphRenderer(FuncIdConversionHelper &FuncIdHelper, bool DSC)
-      : FuncIdHelper(FuncIdHelper), DeduceSiblingCalls(DSC) {}
+      : FuncIdHelper(FuncIdHelper), DeduceSiblingCalls(DSC) {
+    G[0] = {};
+  }
 
   /// Process an Xray record and expand the graph.
   ///
@@ -132,7 +134,7 @@ public:
   /// FIXME: Make this more robust against small irregularities.
   Error accountRecord(const XRayRecord &Record);
 
-  const PerThreadFunctionStackMap getPerThreadFunctionStack() const {
+  const PerThreadFunctionStackMap &getPerThreadFunctionStack() const {
     return PerThreadFunctionStack;
   }
 
@@ -143,6 +145,13 @@ public:
                         StatType EdgeColor = StatType::NONE,
                         StatType VertexLabel = StatType::NONE,
                         StatType VertexColor = StatType::NONE);
+
+  /// Get a reference to the internal graph.
+  const GraphT &getGraph() {
+    calculateEdgeStatistics();
+    calculateVertexStatistics();
+    return G;
+  }
 };
 }
 }