Index: include/llvm/XRay/Graph.h
===================================================================
--- /dev/null
+++ include/llvm/XRay/Graph.h
@@ -0,0 +1,542 @@
+//===-- Graph.h - XRay Graph Class ------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// A Graph Datatype for the llvm-xray graph sub command
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_XRAY_GRAPH_T_H
+#define LLVM_XRAY_GRAPH_T_H
+
+#include <initializer_list>
+#include <stdint.h>
+#include <type_traits>
+#include <utility>
+
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/DenseSet.h"
+#include "llvm/ADT/iterator.h"
+#include "llvm/Support/Error.h"
+
+namespace llvm {
+namespace xray {
+
+/// A Graph object represents a Directed Graph and is used in XRAY to compute
+/// and store function call graphs and associated statistical information.
+///
+/// The graph takes in four template parameters, these are:
+///  - VertexAttribute, this is a structure which is stored for each variable.
+///    Must be DefaultConstructible, CopyConstructible, CopyAssignable and
+///    Destructible.
+///  - EdgeAttribute, this is a structure which is stored for each variable
+///    Must be DefaultConstructible, CopyConstructible, CopyAssignable and
+///    Destructible.
+///  - EdgeAttribute, this is a structure which is stored for each variable
+///  - VI, this is a type over which DenseMapInfo is defined and is the type
+///    used look up strings, available as VertexIdentifier.
+///  - If the built in DenseMapInfo is not defined, provide a specialization
+///    class type here.
+///
+/// Usage Example Graph with weighted edges and vertices:
+///   auto G = Graph<int, int, int>();
+///
+///   G[1] = 0;
+///   G[2] = 2;
+///   G[{1,2}] = 1;
+///   G[{2,1}] = -1;
+///   for(const auto &v : G.vertices()){
+///     // Do something with the vertices in the graph;
+///   }
+///   for(const auto &e : G.edges()){
+///     // Do something with the edges in the graph;
+///   }
+///   auto G_2(G); //Copy G;
+///
+template <typename VertexAttribute, typename EdgeAttribute,
+          typename VI = int32_t, typename DMI = DenseMapInfo<VI>>
+class Graph {
+public:
+  /// These objects are used to name edges and vertices in the graph.
+  typedef VI VertexIdentifier;
+  typedef std::pair<VI, VI> EdgeIdentifier;
+
+  /// A child type of std::pair<VertexIdentifier, VertexAttribute> and should be
+  /// treated as such. This type is the value_type of all iterators which range
+  /// over sets of vertices.
+  typedef detail::DenseMapPair<VertexIdentifier, VertexAttribute>
+      VertexValueType;
+
+  /// EdgeValueType, a child type of std::pair<EdgeIdentifier, EdgeAttribute>,
+  /// and should be treated as such. This type the value_type of all iterators
+  /// which range over sets of edges.
+  ///
+  /// The functions defined on this type are strictly to enable references given
+  /// by dereferencing an InnerEdgeMapT::iterator to look like a
+  /// std::pair<EdgeIdentifier, EdgeAttribute>, whilst still allowing fast
+  /// lookup of edges by EdgeIdentifier, and fast iteration of the edges coming
+  /// out of a vertex, with asymptotically optimal iteration through the
+  /// neighborhood of a vertex, whilst maintaining a consistent and easy to
+  /// understand API. Please don't use them.
+  /// FIXME: figure out the friend declaration to enable them to be private.
+  struct EdgeValueType : public std::pair<EdgeIdentifier, EdgeAttribute> {
+    VertexIdentifier &getFirst() {
+      return std::pair<EdgeIdentifier, EdgeAttribute>::first.second;
+    };
+    const VertexIdentifier &getFirst() const {
+      return std::pair<EdgeIdentifier, EdgeAttribute>::first.second;
+    };
+    EdgeAttribute &getSecond() {
+      return std::pair<EdgeIdentifier, EdgeAttribute>::second;
+    }
+    const EdgeAttribute &getSecond() const {
+      return std::pair<EdgeIdentifier, EdgeAttribute>::second;
+    }
+  };
+
+private:
+  /// The type storing the set of edges leaving a vertex. Indexed by the
+  /// VertexIdentifier of the end vertex of the edge.
+  typedef class DenseMap<VertexIdentifier, EdgeAttribute, DMI, EdgeValueType>
+      InnerEdgeMapT;
+
+  /// The type storing the InnerEdgeMapT corresponding to each vertex in
+  /// the graph (When a vertex has an outgoing edge incident to it)
+  typedef class DenseMap<VertexIdentifier, InnerEdgeMapT, DMI> EdgeMapT;
+
+  /// The type used for storing the VertexAttribute for each vertex in
+  /// the graph.
+  typedef class DenseMap<VertexIdentifier, VertexAttribute, DMI> VertexMapT;
+
+  /// The type used for storing the edges entering a vertex. Indexed by
+  /// the VertexIdentifier of the start of the edge. Only used to determine
+  /// where the incoming edges are, the EdgeIdentifiers are stored in an
+  /// InnerEdgeMapT.
+  typedef class DenseSet<VertexIdentifier, DMI> InnerInvGraphT;
+
+  /// The type storing the InnerInvGraphT corresponding to each vertex in
+  /// the graph (When a vertex has an incoming edge incident to it)
+  typedef class DenseMap<VertexIdentifier, InnerInvGraphT, DMI> InvGraphT;
+
+public:
+  typedef std::size_t size_type;
+
+private:
+  /// Stores the map from the start and end vertex of an edge to it's
+  /// EdgeAttribute
+  EdgeMapT Edges;
+
+  /// Stores the map from VertexIdentifier to VertexAttribute
+  VertexMapT Vertices;
+
+  /// Allows fast lookup for the incoming edge set of any given vertex.
+  InvGraphT InvGraph;
+
+  /// The total number of edges in the graph.
+  size_type NumEdges;
+
+  /// An Iterator adapter using an InnerInvGraphT::iterator as a base iterator,
+  /// and storing the VertexIdentifier the iterator range comes from. The
+  /// dereference operator is then performed using a pointer to the graph's edge
+  /// set.
+  template <bool IsConst,
+            typename BaseIt = typename InnerInvGraphT::const_iterator,
+            typename T = typename std::conditional<IsConst, const EdgeValueType,
+                                                   EdgeValueType>::type>
+  class InEdgeIteratorInt
+      : public iterator_adaptor_base<
+            InEdgeIteratorInt<IsConst>, BaseIt,
+            typename std::iterator_traits<BaseIt>::iterator_category, T> {
+    typedef typename std::conditional<IsConst, const EdgeMapT, EdgeMapT>::type
+        InternalEdgeMapT;
+
+    friend class InEdgeIteratorInt<false, BaseIt, EdgeValueType>;
+    friend class InEdgeIteratorInt<true, BaseIt, const EdgeValueType>;
+
+    InternalEdgeMapT *MP;
+    VertexIdentifier SI;
+
+  public:
+    template <bool IsConstDest,
+              typename = typename std::enable_if<IsConstDest && !IsConst>::type>
+    operator InEdgeIteratorInt<IsConstDest, BaseIt, const EdgeValueType>()
+        const {
+      return InEdgeIteratorInt<IsConstDest, BaseIt, const EdgeValueType>(
+          this->I, MP, SI);
+    }
+
+    InEdgeIteratorInt() = default;
+    InEdgeIteratorInt(BaseIt _I, InternalEdgeMapT *_MP, VertexIdentifier _SI)
+        : iterator_adaptor_base<
+              InEdgeIteratorInt<IsConst>, BaseIt,
+              typename std::iterator_traits<BaseIt>::iterator_category, T>(_I),
+          MP(_MP), SI(_SI) {}
+    T &operator*() { return *(MP->find(*(this->I))->second.find(SI)); }
+  };
+
+public:
+  /// A const iterator type for iterating through the set of edges entering a
+  /// vertex.
+  ///
+  /// Has a const EdgeValueType as its value_type
+  typedef class InEdgeIteratorInt<true> ConstInEdgeIterator;
+
+  /// An iterator type for iterating through the set of edges leaving a vertex.
+  ///
+  /// Has an EdgeValueType as its value_type
+  typedef class InEdgeIteratorInt<false> InEdgeIterator;
+
+  /// A class for ranging over the incoming edges incident to a vertex.
+  ///
+  /// Like all views in this class it provides methods to get the beginning and
+  /// past the range iterators for the range, as well as methods to determine
+  /// the number of elements in the range and whether the range is empty.
+  template <bool isConst> class InEdgeView {
+  public:
+    typedef InEdgeIteratorInt<isConst> Iterator;
+    typedef typename std::conditional<isConst, const Graph, Graph>::type GraphT;
+    typedef typename std::conditional<isConst, const EdgeMapT, EdgeMapT>::type
+        InternalEdgeMapT;
+
+  private:
+    InternalEdgeMapT &M;
+    const VertexIdentifier A;
+    const InvGraphT &InvG;
+
+  public:
+    Iterator begin() {
+      auto It = InvG.find(A);
+      if (It == InvG.end())
+        return Iterator();
+      return Iterator(It->second.begin(), &M, A);
+    };
+    Iterator end() {
+      auto It = InvG.find(A);
+      if (It == InvG.end())
+        return Iterator();
+      return Iterator(It->second.end(), &M, A);
+    };
+    size_type size() const {
+      return (InvG.count(A) == 1) ? InvG.find(A)->second.size() : 0;
+    };
+    bool empty() const { return InvG.count(A) == 0; };
+
+    InEdgeView(GraphT &_G, VertexIdentifier _A)
+        : M(_G.Edges), A(_A), InvG(_G.InvGraph){};
+  };
+
+  /// A const iterator type for iterating through the whole vertex set of the
+  /// graph.
+  ///
+  /// Has a const VertexValueType as its value_type
+  typedef typename VertexMapT::const_iterator ConstVertexIterator;
+
+  /// An iterator type for iterating through the whole vertex set of the graph.
+  ///
+  /// Has a VertexValueType as its value_type
+  typedef typename VertexMapT::iterator VertexIterator;
+
+  /// A class for ranging over the vertices in the graph.
+  ///
+  /// Like all views in this class it provides methods to get the beginning and
+  /// past the range iterators for the range, as well as methods to determine
+  /// the number of elements in the range and whether the range is empty.
+  template <bool isConst> class VertexView {
+  public:
+    typedef typename std::conditional<isConst, ConstVertexIterator,
+                                      VertexIterator>::type Iterator;
+    typedef typename std::conditional<isConst, const Graph, Graph>::type GraphT;
+
+  private:
+    GraphT &G;
+
+  public:
+    Iterator begin() { return G.Vertices.begin(); }
+    Iterator end() { return G.Vertices.end(); }
+    size_type size() const { return G.Vertices.size(); }
+    bool empty() const { return G.Vertices.empty(); }
+    VertexView(GraphT &_G) : G(_G){};
+  };
+
+private:
+  /// An iterator to enable iteration through all the edges in the graph.
+  ///
+  /// It works by storing the iterators corresponding to both levels of EdgeMapT
+  /// and the past the range iterator, not comparing the bottom iterator if the
+  /// Top iterator is a past the range iterator.
+  template <bool IsConst>
+  class EdgeListIterator
+      : public iterator_facade_base<
+            EdgeListIterator<IsConst>, std::forward_iterator_tag,
+            typename std::conditional<IsConst, const EdgeValueType,
+                                      EdgeValueType>::type> {
+  private:
+    typedef
+        typename std::conditional<IsConst, typename EdgeMapT::const_iterator,
+                                  typename EdgeMapT::iterator>::type TopItT;
+    typedef typename std::conditional<
+        IsConst, typename InnerEdgeMapT::const_iterator,
+        typename InnerEdgeMapT::iterator>::type BotItT;
+
+    typedef EdgeListIterator<true> const_iterator;
+    typedef typename std::iterator_traits<EdgeListIterator<IsConst>>::reference
+        reference;
+
+    friend class EdgeListIterator<false>;
+    friend class EdgeListIterator<true>;
+
+  private:
+    TopItT TopIt;
+    TopItT TopEnd;
+    BotItT BotIt;
+
+  public:
+    EdgeListIterator(TopItT _TopIt, TopItT _TopEnd, BotItT _BotIt)
+        : TopIt(_TopIt), TopEnd(_TopEnd), BotIt(_BotIt){};
+
+    EdgeListIterator(TopItT _TopIt, TopItT _TopEnd)
+        : TopIt(_TopIt), TopEnd(_TopEnd) {
+      BotIt = (TopIt == TopEnd) ? BotItT() : TopIt->second.begin();
+    }
+
+    // Converting ctor from non-const iterators to const iterators. SFINAEd out
+    // for const iterator sources so it doesn't end up as a user defined
+    // copy constructor.
+
+    template <bool IsConstSrc,
+              typename = typename std::enable_if<!IsConstSrc && IsConst>::type>
+    EdgeListIterator(const EdgeListIterator<IsConstSrc> &I)
+        : TopIt(I.TopIt), TopEnd(I.TopEnd), BotIt(I.BotIt){};
+
+    bool operator==(const const_iterator &b) const {
+      return (TopIt == b.TopIt && (TopIt == TopEnd || BotIt == b.BotIt));
+    };
+
+    EdgeListIterator &operator++() { // pre-increment
+      ++BotIt;
+      if (BotIt == TopIt->second.end()) {
+        ++TopIt;
+        if (TopIt != TopEnd)
+          BotIt = TopIt->second.begin();
+      }
+      return *this;
+    };
+
+    reference operator*() { return *BotIt; };
+  };
+
+public:
+  /// A const iterator for iterating through the entire edge set of the graph.
+  ///
+  /// Has a const EdgeValueType as its value_type
+  typedef EdgeListIterator<true> ConstEdgeIterator;
+
+  /// An iterator for iterating through the entire edge set of the graph.
+  ///
+  /// Has an EdgeValueType as its value_type
+  typedef EdgeListIterator<false> EdgeIterator;
+
+  /// A class for ranging over all the edges in the graph.
+  ///
+  /// Like all views in this class it provides methods to get the beginning and
+  /// past the range iterators for the range, as well as methods to determine
+  /// the number of elements in the range and whether the range is empty.
+  template <bool isConst> class EdgeView {
+  public:
+    typedef typename std::conditional<isConst, ConstEdgeIterator,
+                                      EdgeIterator>::type Iterator;
+    typedef typename std::conditional<isConst, const Graph, Graph>::type GraphT;
+
+  private:
+    GraphT &G;
+
+  public:
+    Iterator begin() { return Iterator(G.Edges.begin(), G.Edges.end()); }
+    Iterator end() {
+      auto e = G.Edges.end();
+      return Iterator(e, e);
+    }
+    size_type size() const { return G.NumEdges; }
+    bool empty() const { return G.Edges.empty(); }
+    EdgeView(GraphT &_G) : G(_G){};
+  };
+
+public:
+  void clear() {
+    Edges.clear();
+    Vertices.clear();
+    InvGraph.clear();
+    NumEdges = 0;
+  }
+
+  /// Returns a view object allowing iteration over the vertices of the graph.
+  /// also allows access to the size of the vertex set.
+  VertexView<false> vertices() { return VertexView<false>(*this); };
+
+  VertexView<true> vertices() const { return VertexView<true>(*this); };
+
+  /// Returns a view object allowing iteration over the edges of the graph.
+  /// also allows access to the size of the edge set.
+  EdgeView<false> edges() { return EdgeView<false>(*this); };
+
+  EdgeView<true> edges() const { return EdgeView<true>(*this); };
+
+  /// Returns a view object allowing iteration over the edges which point to
+  /// a vertex I.
+  InEdgeView<false> inEdges(const VertexIdentifier I) {
+    return InEdgeView<false>(*this, I);
+  }
+
+  InEdgeView<true> inEdges(const VertexIdentifier I) const {
+    return InEdgeView<true>(*this, I);
+  }
+
+  /// Looks up the vertex with identifier I, if it does not exist it default
+  /// constructs it.
+  VertexAttribute &operator[](const VertexIdentifier &I) {
+    if (count(I) == 0) {
+      VertexValueType VVT = {};
+      VVT.first = I;
+      insert(VVT);
+    }
+    return Vertices[I];
+  };
+
+  /// Looks up the edge with identifier I, if it does not exist it default
+  /// constructs it, if it's endpoints do not exist it also default constructs
+  /// them.
+  EdgeAttribute &operator[](const EdgeIdentifier &I) {
+    if (count(I) == 0) {
+      EdgeValueType EVT = {};
+      EVT.first = I;
+      insert(EVT);
+    }
+    return Edges[I.first][I.second];
+  };
+
+  /// Looks up a vertex with Identifier I, or an error if it does not exist.
+  Expected<VertexAttribute &> at(const VertexIdentifier &I){
+    auto It = Vertices.find(I);
+    if(It == Vertices.end())
+        return make_error<StringError>(
+            "Vertex Identifier Does Not Exist",
+            std::make_error_code(std::errc::invalid_argument));
+    return It->second;
+  };
+
+  Expected<const VertexAttribute &> at(const VertexIdentifier &I) const{
+    auto It = Vertices.find(I);
+    if(It == Vertices.end())
+        return make_error<StringError>(
+            "Vertex Identifier Does Not Exist",
+            std::make_error_code(std::errc::invalid_argument));
+    return It->second;
+  };
+
+  /// Looks up an edge with Identifier I, or an error if it does not exist.
+  Expected<EdgeAttribute &> at(const EdgeIdentifier &I){
+    auto It = Edges.find(I.first);
+    if(It == Edges.end())
+        return make_error<StringError>(
+            "Edge Identifier Does Not Exist",
+            std::make_error_code(std::errc::invalid_argument));
+    auto It2 = It->second.find(I.second);
+    if(It2 == It->second.end())
+        return make_error<StringError>(
+            "Edge Identifier Does Not Exist",
+            std::make_error_code(std::errc::invalid_argument));
+    return It2->second;
+  };
+
+  Expected<const EdgeAttribute &> at(const EdgeIdentifier &I) const{
+    auto It = Edges.find(I.first);
+    if(It == Edges.end())
+      return make_error<StringError>(
+            "Edge Identifier Does Not Exist",
+            std::make_error_code(std::errc::invalid_argument));
+    auto It2 = It->second.find(I.second);
+    if(It2 == It->second.end())
+        return make_error<StringError>(
+            "Edge Identifier Does Not Exist",
+            std::make_error_code(std::errc::invalid_argument));
+    return It2->second;
+  };
+
+  /// Looks for a vertex with identifier I, returns 1 if one exists, and
+  /// 0 otherwise
+  size_type count(const VertexIdentifier &I) const {
+    return Vertices.count(I);
+  };
+
+  /// Looks for an edge with Identifier I, returns 1 if one exists and 0
+  /// otherwise
+  size_type count(const EdgeIdentifier &I) const {
+    return (Edges.count(I.first) == 1)
+               ? Edges.find(I.first)->second.count(I.second)
+               : 0;
+  };
+
+  Graph() = default;
+
+  Graph(Graph &&b) = default;
+
+  Graph(const Graph &b) {
+    for (auto &V : b.vertices())
+      insert(V);
+    for (auto &E : b.edges())
+      insert(E);
+  }
+  ~Graph() = default;
+
+  Graph &operator=(const Graph &other) {
+    using std::swap;
+    Graph tmp(other);
+    swap(*this, other);
+    return *this;
+  }
+
+  Graph &operator=(Graph &&other) noexcept {
+    Edges = std::move(other.Edges);
+    Vertices = std::move(other.Vertices);
+    InvGraph = std::move(InvGraph);
+    NumEdges = other.numEdges;
+
+    other.Edges.clear();
+    other.Vertices.clear();
+    other.InvGraph.clear();
+    other.NumEdges = 0;
+    return *this;
+  }
+
+  /// Inserts a vertex into the graph with Identifier Val.first, and
+  /// Attribute Val.second.
+  std::pair<VertexIterator, bool> insert(const VertexValueType &Val) {
+    return Vertices.insert(Val);
+  };
+  std::pair<VertexIterator, bool> insert(VertexValueType &&Val) {
+    return Vertices.insert(Val);
+  };
+
+  /// Inserts an edge into the graph with Identifier Val.first, and
+  /// Attribute Val.second.
+  std::pair<EdgeIterator, bool> insert(const EdgeValueType &Val) {
+    operator[](Val.first.first);
+    operator[](Val.first.second);
+    InnerEdgeMapT &TRef = Edges[Val.first.first];
+    typename EdgeMapT::iterator TI = Edges.find(Val.first.first);
+    InnerInvGraphT &ITRef = InvGraph[Val.first.second];
+    ITRef.insert(Val.first.first);
+    auto p = TRef.insert({Val.first.second, Val.second});
+    p.first->first.first = Val.first.first;
+    ++NumEdges;
+    return {EdgeIterator(TI, Edges.end(), p.first), p.second};
+  };
+};
+}
+}
+#endif
Index: tools/llvm-xray/xray-graph.h
===================================================================
--- tools/llvm-xray/xray-graph.h
+++ 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,6 +50,7 @@
     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.
@@ -56,7 +58,7 @@
   /// FIXME: expand to contain more information eg call latencies.
   struct EdgeAttribute {
     TimeStat S;
-    std::vector<uint64_t> Timings;
+    std::vector<TimestampT> Timings;
   };
 
   /// An Inner Struct for storing vertex attributes, at the moment just
@@ -78,17 +80,15 @@
   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<VertexAttribute, EdgeAttribute, 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 @@
   /// 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 @@
   /// 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 @@
   /// 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,12 @@
                         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;
+  }
 };
 }
 }
Index: tools/llvm-xray/xray-graph.cc
===================================================================
--- tools/llvm-xray/xray-graph.cc
+++ 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,33 +30,33 @@
 using namespace 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::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<InstrumentationMapExtractor::InputFormats> InstrMapFormat(
     "instr-map-format", cl::desc("format of instrumentation map"),
@@ -64,24 +64,24 @@
                           "instrumentation map in an ELF header"),
                clEnumValN(InstrumentationMapExtractor::InputFormats::YAML,
                           "yaml", "instrumentation map in YAML")),
-    cl::sub(Graph), cl::init(InstrumentationMapExtractor::InputFormats::ELF));
+    cl::sub(GraphC), cl::init(InstrumentationMapExtractor::InputFormats::ELF));
 static cl::alias InstrMapFormat2("t", cl::aliasopt(InstrMapFormat),
                                  cl::desc("Alias for -instr-map-format"),
-                                 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"),
@@ -101,12 +101,12 @@
                                          "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"),
@@ -126,12 +126,12 @@
                           "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"),
@@ -151,12 +151,12 @@
                           "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"),
@@ -176,7 +176,7 @@
                           "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); }
 
@@ -221,14 +221,13 @@
   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)
@@ -243,23 +242,25 @@
             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);
+        EdgeAttribute &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;
   }
   }
@@ -293,38 +294,32 @@
 }
 
 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);
+    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();
   }
 }
 
@@ -342,19 +337,17 @@
 
 // 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
@@ -490,7 +483,10 @@
 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);
@@ -500,18 +496,20 @@
   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);
@@ -520,7 +518,7 @@
     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";
@@ -534,7 +532,7 @@
 //
 // FIXME: include additional filtering and annalysis passes to provide more
 // specific useful information.
-static CommandRegistration Unused(&Graph, []() -> Error {
+static CommandRegistration Unused(&GraphC, []() -> Error {
   int Fd;
   auto EC = sys::fs::openFileForRead(GraphInput, Fd);
   if (EC)
@@ -596,7 +594,6 @@
     handleAllErrors(std::move(E),
                     [&](const ErrorInfoBase &E) { E.log(errs()); });
   }
-
   GR.exportGraphAsDOT(OS, Header, GraphEdgeLabel, GraphEdgeColorType,
                       GraphVertexLabel, GraphVertexColorType);
   return Err;