Index: include/llvm/XRay/Graph.h
===================================================================
--- /dev/null
+++ include/llvm/XRay/Graph.h
@@ -0,0 +1,487 @@
+//===-- graphClass.h - XRay Function Call Graph Renderer --------*- 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 subcommand
+//
+//===----------------------------------------------------------------------===/
+
+#ifndef LLVM_XRAY_GRAPH_T_H
+#define LLVM_XRAY_GRAPH_T_H
+
+#include <stdint.h>
+#include <utility>
+#include <initializer_list>
+#include <type_traits>
+
+#include "llvm/Support/Error.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/DenseSet.h"
+
+namespace llvm{
+namespace xray{
+
+namespace internal{
+
+/// An iterator Class which iterates using BaseIt, using a conversion function
+/// to dereference the poiter.
+template <class BaseIt,
+          class LookupCollection,
+          typename T = void,
+          typename ReturnCollection = LookupCollection>
+class ProxiedIterator {
+  typedef ProxiedIterator<BaseIt, const LookupCollection, T, const ReturnCollection> ConstIterator;
+  friend class ProxiedIterator<BaseIt,
+                               const LookupCollection,
+                               T,
+                               const ReturnCollection>;
+  friend class ProxiedIterator<BaseIt,
+                               typename std::remove_const<LookupCollection>::type,
+                               T,
+                               typename std::remove_const<ReturnCollection>::type>;
+ public:
+  typedef typename std::conditional<std::is_const<ReturnCollection>::value,
+                           typename ReturnCollection::const_iterator,
+                           typename ReturnCollection::iterator>::type RetIt;
+  typedef ptrdiff_t difference_type;
+  typedef typename std::iterator_traits<RetIt>::value_type value_type;
+  typedef typename std::iterator_traits<RetIt>::pointer pointer;
+  typedef typename std::iterator_traits<RetIt>::reference reference;
+  typedef typename std::forward_iterator_tag iterator_category;
+
+  typedef std::function<RetIt(BaseIt, LookupCollection &, T)> ConversionHelper;
+
+ private:
+  BaseIt B;
+  LookupCollection *C;
+  T S;
+  ConversionHelper H;
+
+ public:
+
+  template<class Other,
+           typename = typename std::enable_if<!std::is_const<Other>::value &&
+                    std::is_const<LookupCollection>::value &&
+                    std::is_same<const Other, const LookupCollection>::value>::type,
+           class OtherRC,
+           typename = typename std::enable_if<!std::is_const<OtherRC>::value &&
+                    std::is_const<ReturnCollection>::value &&
+                    std::is_same<const OtherRC, const ReturnCollection>::value>::type>
+  ProxiedIterator(const ProxiedIterator<BaseIt, Other, T, OtherRC> &I):
+    B(I.B), C(I.C), S(I.S) {
+     H = [&I](BaseIt It, LookupCollection &C, T Id) -> RetIt{
+       return I.H(It, const_cast<typename std::remove_const<LookupCollection>::type &>(C), Id);
+     };
+    };
+
+  ProxiedIterator(): C(nullptr){H = nullptr;};
+
+  ProxiedIterator(BaseIt _B, LookupCollection &_C,
+                  ConversionHelper _H, T _S): B(_B), C(&_C), S(_S), H(_H){};
+
+  reference operator*(){
+     return *(H(B, *C, S));
+  };
+
+  pointer operator->(){
+     return H(B,*C, S).operator->();
+  };
+
+  bool operator!=(const ConstIterator &b) const{
+    return B != b.B;
+  }
+  bool operator==(const ConstIterator &b) const{
+    return B == b.B;
+  }
+
+  ProxiedIterator &operator++(){
+    ++B;
+    return *this;
+  }
+  ProxiedIterator operator++(int){
+    ProxiedIterator retval(*this);
+    ++(*this);
+    return retval;
+  }
+};
+
+}
+
+template <typename VertexAttribute,
+          typename EdgeAttribute,
+          typename GraphAttribute,
+          typename VI = int32_t,
+          typename EI = std::pair<VI,VI>>
+class Graph : public GraphAttribute{
+ public:
+  /// These objects are used to name edges and vertices in the graph.
+  typedef VI VertexIdentifier;
+  typedef EI EdgeIdentifier;
+
+  typedef detail::DenseMapPair<VertexIdentifier, VertexAttribute> VertexValueType;
+
+  /// A Value Type for edges which also contains the other edge point to enable
+  /// easy iteration and iterators.
+  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;
+    }
+  };
+
+  ///Typedefs of the various structure types in this class.
+  typedef class DenseMap<VertexIdentifier,
+                             EdgeAttribute,
+                             DenseMapInfo<VertexIdentifier>,
+                             EdgeValueType> InnerEdgeMapT;
+  typedef class DenseMap<VertexIdentifier, InnerEdgeMapT> EdgeMapT;
+  typedef class DenseMap<VertexIdentifier, VertexAttribute> VertexMapT;
+  typedef class DenseSet<VertexIdentifier> InnerInvGraphT;
+  typedef class DenseMap<VertexIdentifier, InnerInvGraphT> InvGraphT;
+
+  ///Typedefs of those iterators whose types are already known.
+  typedef typename VertexMapT::const_iterator ConstVertexIterator;
+  typedef typename VertexMapT::iterator VertexIterator;
+
+  typedef typename InnerEdgeMapT::const_iterator ConstOutEdgeIterator;
+  typedef typename InnerEdgeMapT::iterator OutEdgeIterator;
+
+
+  typedef std::size_t size_type;
+
+ private:
+  /// The actual data in the graph.
+  EdgeMapT Edges;
+  VertexMapT Vertices;
+  InvGraphT InvGraph;
+  size_type NumEdges;
+
+ public:
+
+  /// A bunch of typedefs using the ProxiedIterator class implement them
+  typedef class internal::ProxiedIterator<typename InnerInvGraphT::const_iterator,
+                                const EdgeMapT,
+                                VertexIdentifier,
+                                const InnerEdgeMapT> ConstInEdgeIterator;
+  typedef class internal::ProxiedIterator<typename InnerInvGraphT::const_iterator,
+                                EdgeMapT,
+                                VertexIdentifier,
+                                InnerEdgeMapT> InEdgeIterator;
+
+  template <bool isConst>
+  class InEdgeIteratorProxy {
+   public:
+    typedef typename std::conditional<isConst, ConstInEdgeIterator, InEdgeIterator>::type Iterator;
+    typedef typename std::conditional<isConst, const Graph, Graph>::type GraphT;
+    typedef typename InnerInvGraphT::const_iterator BaseIt;
+    typedef typename std::conditional<isConst, const EdgeMapT, EdgeMapT>::type IntEdgeMapT;
+
+    typedef typename Iterator::RetIt RetIt;
+   private:
+    GraphT &G;
+    VertexIdentifier A;
+    RetIt (*convert)(BaseIt, IntEdgeMapT &, VertexIdentifier);
+   public:
+    Iterator begin(){
+      auto It = G.InvGraph.find(A);
+      if (It == G.InvGraph.end())
+        return Iterator();
+      return Iterator(It->second.begin(), G.Edges,convert, A);
+    };
+    Iterator end(){
+      auto It = G.InvGraph.find(A);
+      if (It == G.InvGraph.end())
+        return Iterator();
+      return Iterator(It->second.end(), G.Edges, convert, A);
+    };
+    size_type size() const{
+      return (G.InvGraph.count(A) == 1)? G.InvGraph.find(A)->second.size() : 0;
+    };
+    bool empty() const{
+      return G.InvGraph.count(A) == 0;
+    };
+
+    InEdgeIteratorProxy (GraphT &_G,
+                    const VertexIdentifier _A): G(_G), A(_A){
+      convert = [](BaseIt It, IntEdgeMapT &C, VertexIdentifier I) -> RetIt{
+                       return C.find(*It)->second.find(I);};
+    };
+  };
+
+  template <bool isConst>
+  class VertexProxy {
+   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(){
+      return G.Vertices.empty();
+    }
+    VertexProxy (GraphT &_G): G(_G){};
+  };
+
+  /// An iterator to enable iteration through all the edges in the graph.
+  template <bool IsConst>
+  class EdgeListIterator{
+   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 EdgeListIterator<false> iterator;
+
+    friend class EdgeListIterator<true>;
+    friend class EdgeListIterator<false>;
+
+   public:
+    typedef ptrdiff_t difference_type;
+    typedef typename std::conditional<IsConst,
+                             const EdgeValueType,
+                             EdgeValueType>::type value_type;
+    typedef value_type *pointer;
+    typedef value_type &reference;
+    typedef std::forward_iterator_tag iterator_category;
+
+   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();
+      }
+
+    // Conveting ctor from non-const iterators to const iterators. SFINAE'd out
+    // for const iterator destinations 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 !((*this)==(b));
+    };
+    bool operator==(const const_iterator &b) const{
+      return (TopIt == b.TopIt && (TopIt == TopEnd || BotIt == b.BotIt));
+    };
+
+    bool operator!=(const iterator &b) const{
+      return !((*this)==b);
+    }
+    bool operator==(const iterator &b) const{
+      return (TopIt == b.TopIt && (TopIt == TopEnd || BotIt == b.BotIt));
+    }
+
+    EdgeListIterator& operator ++(){ //preincrement
+      ++BotIt;
+      if(BotIt == TopIt->second.end()){
+        ++TopIt;
+        if(TopIt != TopEnd)
+          BotIt = TopIt->second.begin();
+      }
+      return *this;
+    };
+    EdgeListIterator operator++(int){ //postincrement
+      EdgeListIterator retval(*this);
+      ++(*this);
+      return retval;
+    };
+
+    reference operator*(){return *BotIt;};
+    pointer operator->(){return &(*BotIt);};
+  };
+
+  typedef EdgeListIterator<true> ConstEdgeIterator;
+  typedef EdgeListIterator<false> EdgeIterator;
+
+
+  template <bool isConst>
+  class EdgeProxy {
+   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(){
+      return G.Edges.empty();
+    }
+    EdgeProxy (GraphT &_G): G(_G){};
+  };
+
+ public:
+  void clear(){
+    Edges.clear();
+    Vertices.clear();
+    InvGraph.clear();
+    NumEdges = 0;
+  }
+
+
+  /// Returns a proxy object allowing iteration over the vertices of the graph.
+  /// also allows access to the size of the vertex set.
+  VertexProxy<false> vertices() {return VertexProxy<false>(*this);};
+
+  VertexProxy<true>  vertices() const{ return VertexProxy<true>(*this);};
+
+  /// Returns a proxy object allowing iteration over the efdges of the graph.
+  /// also allows access to the size of the edvge set.
+  EdgeProxy<false> edges() {return EdgeProxy<false>(*this);};
+
+  EdgeProxy<true>  edges() const{return EdgeProxy<true>(*this);};
+
+  /// Returns a proxy object allowing iteration over the edges which point to
+  /// a vertex I.
+  InEdgeIteratorProxy<false> inEdges(const VertexIdentifier I){
+    return InEdgeIteratorProxy<false>(*this, I);
+  }
+
+  InEdgeIteratorProxy<true> inEdges(const VertexIdentifier I) const{
+    return InEdgeIteratorProxy<true>(*this, I);
+  }
+
+  /// Looks up a 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 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
@@ -26,6 +26,7 @@
 #include "llvm/Support/Program.h"
 #include "llvm/XRay/Trace.h"
 #include "llvm/XRay/XRayRecord.h"
+#include "llvm/XRay/Graph.h"
 
 namespace llvm {
 namespace xray {
@@ -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
@@ -68,21 +70,21 @@
     TimeStat S;
   };
 
-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;
+  struct GraphAttribute{
+    TimeStat GraphEdgeMax = {};
+    TimeStat GraphVertexMax = {};
+  };
 
-  /// Graph Vertex Attributes. These are presently stored seperate from the
-  /// main graph.
-  DenseMap<int32_t, VertexAttribute> VertexAttrs;
 
-  TimeStat GraphEdgeMax;
-  TimeStat GraphVertexMax;
+  typedef Graph<VertexAttribute, EdgeAttribute, GraphAttribute, int32_t> GraphT;
+  GraphT G;
+  typedef typename decltype(G)::VertexIdentifier VertexIdentifier;
+  typedef typename decltype(G)::EdgeIdentifier EdgeIdentifier;
 
+ private:
   struct FunctionAttr {
-    int32_t FuncId;
-    uint64_t TSC;
+    VertexIdentifier FuncId;
+    TimestampT TSC;
   };
 
   /// Use a Map to store the Function stack for each thread whilst building the
@@ -95,7 +97,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>
@@ -117,7 +119,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.
   ///
@@ -135,6 +139,11 @@
                         StatType EdgeColor = StatType::NONE,
                         StatType VertexLabel = StatType::NONE,
                         StatType VertexColor = StatType::NONE);
+  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,31 +30,31 @@
 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::init(""));
+    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"),
@@ -62,24 +62,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"),
@@ -99,12 +99,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"),
@@ -124,12 +124,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"),
@@ -149,12 +149,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"),
@@ -174,7 +174,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,14 @@
   auto &ThreadStack = PerThreadFunctionStack[Record.TId];
   switch (Record.Type) {
   case RecordTypes::ENTER: {
-    if (VertexAttrs.count(Record.FuncId) == 0)
-      VertexAttrs[Record.FuncId].SymbolName =
+    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)
@@ -241,23 +241,25 @@
         return make_error<StringError>("No matching Entry record in stack",
                                        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;
   }
   }
@@ -291,38 +293,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();
   }
 }
 
@@ -340,19 +336,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) {
+  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
@@ -488,7 +482,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);
@@ -498,18 +495,21 @@
   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 &V : VertexAttrs) {
+  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 : 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);
@@ -518,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";
@@ -532,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)
@@ -584,7 +584,6 @@
         return Err;
     }
   }
-
   GR.exportGraphAsDOT(OS, Header, GraphEdgeLabel, GraphEdgeColorType,
                       GraphVertexLabel, GraphVertexColorType);
   return Err;