Index: include/llvm/ADT/DenseMap.h
===================================================================
--- include/llvm/ADT/DenseMap.h
+++ include/llvm/ADT/DenseMap.h
@@ -107,10 +107,12 @@
     for (BucketT *P = getBuckets(), *E = getBucketsEnd(); P != E; ++P) {
       if (!KeyInfoT::isEqual(P->getFirst(), EmptyKey)) {
         if (!KeyInfoT::isEqual(P->getFirst(), TombstoneKey)) {
-          P->getSecond().~ValueT();
+          P->~BucketT();
+          ::new (&P->getFirst()) KeyT(EmptyKey);
           --NumEntries;
+        } else {
+          P->getFirst() = EmptyKey;
         }
-        P->getFirst() = EmptyKey;
       }
     }
     assert(NumEntries == 0 && "Node count imbalance!");
@@ -245,16 +247,16 @@
     if (!LookupBucketFor(Val, TheBucket))
       return false; // not in map.
 
-    TheBucket->getSecond().~ValueT();
-    TheBucket->getFirst() = getTombstoneKey();
+    TheBucket->~BucketT();
+    ::new (&TheBucket->getFirst()) KeyT(getTombstoneKey());
     decrementNumEntries();
     incrementNumTombstones();
     return true;
   }
   void erase(iterator I) {
     BucketT *TheBucket = &*I;
-    TheBucket->getSecond().~ValueT();
-    TheBucket->getFirst() = getTombstoneKey();
+    TheBucket->~BucketT();
+    ::new (&TheBucket->getFirst()) KeyT(getTombstoneKey());
     decrementNumEntries();
     incrementNumTombstones();
   }
@@ -305,9 +307,11 @@
     const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey();
     for (BucketT *P = getBuckets(), *E = getBucketsEnd(); P != E; ++P) {
       if (!KeyInfoT::isEqual(P->getFirst(), EmptyKey) &&
-          !KeyInfoT::isEqual(P->getFirst(), TombstoneKey))
-        P->getSecond().~ValueT();
-      P->getFirst().~KeyT();
+          !KeyInfoT::isEqual(P->getFirst(), TombstoneKey)){
+        P->~BucketT();
+      } else {
+        P->getFirst().~KeyT();
+      }
     }
   }
 
@@ -347,14 +351,15 @@
         bool FoundVal = LookupBucketFor(B->getFirst(), DestBucket);
         (void)FoundVal; // silence warning.
         assert(!FoundVal && "Key already in new map?");
-        DestBucket->getFirst() = std::move(B->getFirst());
-        ::new (&DestBucket->getSecond()) ValueT(std::move(B->getSecond()));
+        DestBucket->getFirst().~KeyT();
+        ::new (DestBucket) BucketT(std::move(*B));
         incrementNumEntries();
 
         // Free the value.
-        B->getSecond().~ValueT();
+        B->~BucketT();
+      } else {
+        B->getFirst().~KeyT();
       }
-      B->getFirst().~KeyT();
     }
   }
 
@@ -372,12 +377,14 @@
              getNumBuckets() * sizeof(BucketT));
     else
       for (size_t i = 0; i < getNumBuckets(); ++i) {
-        ::new (&getBuckets()[i].getFirst())
-            KeyT(other.getBuckets()[i].getFirst());
-        if (!KeyInfoT::isEqual(getBuckets()[i].getFirst(), getEmptyKey()) &&
-            !KeyInfoT::isEqual(getBuckets()[i].getFirst(), getTombstoneKey()))
-          ::new (&getBuckets()[i].getSecond())
-              ValueT(other.getBuckets()[i].getSecond());
+        if (!KeyInfoT::isEqual(other.getBuckets()[i].getFirst(), getEmptyKey()) &&
+            !KeyInfoT::isEqual(other.getBuckets()[i].getFirst(), getTombstoneKey())){
+          ::new (&getBuckets()[i])
+              BucketT(other.getBuckets()[i]);
+        } else {
+          ::new (&getBuckets()[i].getFirst())
+              KeyT(other.getBuckets()[i].getFirst());
+        }
       }
   }
 
@@ -810,13 +817,20 @@
           continue;
         }
         // Swap separately and handle any assymetry.
-        std::swap(LHSB->getFirst(), RHSB->getFirst());
         if (hasLHSValue) {
-          ::new (&RHSB->getSecond()) ValueT(std::move(LHSB->getSecond()));
-          LHSB->getSecond().~ValueT();
+          KeyT Temp = std::move(RHSB->getFirst());
+          RHSB->getFirst().~KeyT();
+          ::new (RHSB) BucketT(std::move(*LHSB));
+          LHSB->~BucketT();
+          ::new (&LHSB->getFirst()) KeyT(std::move(Temp));
         } else if (hasRHSValue) {
-          ::new (&LHSB->getSecond()) ValueT(std::move(RHSB->getSecond()));
-          RHSB->getSecond().~ValueT();
+          KeyT Temp = std::move(LHSB->getFirst());
+          LHSB->getFirst().~KeyT();
+          ::new (LHSB) BucketT(std::move(*RHSB));
+          RHSB->~BucketT();
+          ::new (&RHSB->getFirst()) KeyT(std::move(Temp));
+        } else {
+          std::swap(LHSB->getFirst(), RHSB->getFirst());
         }
       }
       return;
@@ -841,12 +855,13 @@
     for (unsigned i = 0, e = InlineBuckets; i != e; ++i) {
       BucketT *NewB = &LargeSide.getInlineBuckets()[i],
               *OldB = &SmallSide.getInlineBuckets()[i];
-      ::new (&NewB->getFirst()) KeyT(std::move(OldB->getFirst()));
-      OldB->getFirst().~KeyT();
-      if (!KeyInfoT::isEqual(NewB->getFirst(), EmptyKey) &&
-          !KeyInfoT::isEqual(NewB->getFirst(), TombstoneKey)) {
-        ::new (&NewB->getSecond()) ValueT(std::move(OldB->getSecond()));
-        OldB->getSecond().~ValueT();
+      if (!KeyInfoT::isEqual(OldB->getFirst(), EmptyKey) &&
+          !KeyInfoT::isEqual(OldB->getFirst(), TombstoneKey)) {
+        ::new (NewB) BucketT(std::move(*OldB));
+        OldB->~BucketT();
+      } else {
+        ::new (&NewB->getFirst()) KeyT(std::move(OldB->getFirst()));
+          OldB->getFirst().~KeyT();
       }
     }
 
@@ -912,12 +927,12 @@
             !KeyInfoT::isEqual(P->getFirst(), TombstoneKey)) {
           assert(size_t(TmpEnd - TmpBegin) < InlineBuckets &&
                  "Too many inline buckets!");
-          ::new (&TmpEnd->getFirst()) KeyT(std::move(P->getFirst()));
-          ::new (&TmpEnd->getSecond()) ValueT(std::move(P->getSecond()));
+          ::new (TmpEnd) BucketT(std::move(*P));
           ++TmpEnd;
-          P->getSecond().~ValueT();
+          P->~BucketT();
+        } else {
+          P->getFirst().~KeyT();
         }
-        P->getFirst().~KeyT();
       }
 
       // Now make this map use the large rep, and move all the entries back
Index: include/llvm/XRay/Graph.h
===================================================================
--- /dev/null
+++ include/llvm/XRay/Graph.h
@@ -0,0 +1,585 @@
+//===-- 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 XRay.
+//
+//===----------------------------------------------------------------------===//
+
+#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 vertex.
+///    Must be DefaultConstructible, CopyConstructible, CopyAssignable and
+///    Destructible.
+///  - EdgeAttribute, this is a structure which is stored for each edge
+///    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.
+///
+/// Graph is CopyConstructible, CopyAssignable, MoveConstructible and
+/// MoveAssignable but is not EqualityComparible or LessThanComparible.
+///
+/// Usage Example Graph with weighted edges and vertices:
+///   Graph<int, int, int> G;
+///
+///   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;
+///   }
+///
+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 following properties are desireable in the graph class:
+  ///  - EdgeIterators de-reference to a child type of
+  ///    std::pair<EdgeIdentifier, EdgeAttribute> to enable a standard library
+  ///    like metaphore.
+  ///  - Edges can be looked up by their EdgeIdentifier in amortised constant
+  ///    time.
+  ///  - The out-edges of a vertex can be looked up in amortised constant time.
+  ///  The first two of these can be implemented by defining the graph to be a
+  ///  DenseMap<EdgeIdentifier, EdgeAttribute> however the third is not
+  ///  satisfied by this. However DenseMap allows us to define our own BucketT.
+  ///  We can then have a DenseMap of VertexIdentifier to DenseMaps with a
+  ///  custom BucketT. This gives us the third property and allows us to
+  ///  implement the prefered complexity. It also allows our iterators to have
+  ///  a simple implementation. This type implements the BucketT interface while
+  ///  having the inner Dense Map store EdgeValueTypes.
+  ///
+  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.
+  using InnerEdgeMapT =
+      DenseMap<VertexIdentifier, EdgeAttribute, DMI, EdgeValueType>;
+
+  /// The type storing the InnerEdgeMapT corresponding to each vertex in
+  /// the graph (When a vertex has an outgoing edge incident to it)
+  using EdgeMapT = DenseMap<VertexIdentifier, InnerEdgeMapT, DMI>;
+
+  /// The type used for storing the VertexAttribute for each vertex in
+  /// the graph.
+  using VertexMapT = DenseMap<VertexIdentifier, VertexAttribute, DMI>;
+
+  /// 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.
+  using InnerInvGraphT = DenseSet<VertexIdentifier, DMI>;
+
+  /// The type storing the InnerInvGraphT corresponding to each vertex in
+  /// the graph (When a vertex has an incoming edge incident to it)
+  using InvGraphT = DenseMap<VertexIdentifier, InnerInvGraphT, DMI>;
+
+public:
+  using size_type = std::size_t;
+
+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> {
+    using InternalEdgeMapT =
+        typename std::conditional<IsConst, const EdgeMapT, EdgeMapT>::type;
+
+    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*() const{ 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
+  using ConstInEdgeIterator = InEdgeIteratorInt<true>;
+
+  /// An iterator type for iterating through the set of edges leaving a vertex.
+  ///
+  /// Has an EdgeValueType as its value_type
+  using InEdgeIterator = InEdgeIteratorInt<false>;
+
+  /// 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:
+    using iterator = InEdgeIteratorInt<isConst>;
+    using const_iterator = InEdgeIteratorInt<true>;
+    using GraphT = typename std::conditional<isConst, const Graph, Graph>::type;
+    using InternalEdgeMapT =
+       typename std::conditional<isConst, const EdgeMapT, EdgeMapT>::type;
+
+  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);
+    }
+
+    const_iterator cbegin() const {
+      auto It = InvG.find(A);
+      if (It == InvG.end())
+        return const_iterator();
+      return const_iterator(It->second.begin(), &M, A);
+    }
+    const_iterator begin() const {
+      return cbegin();
+    }
+
+    iterator end() {
+      auto It = InvG.find(A);
+      if (It == InvG.end())
+        return iterator();
+      return iterator(It->second.end(), &M, A);
+    }
+    const_iterator cend() const {
+      auto It = InvG.find(A);
+      if (It == InvG.end())
+        return const_iterator();
+      return const_iterator(It->second.end(), &M, A);
+    }
+    const_iterator end() const{
+      return cend();
+    }
+
+    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
+  using ConstVertexIterator = typename VertexMapT::const_iterator;
+
+  /// An iterator type for iterating through the whole vertex set of the graph.
+  ///
+  /// Has a VertexValueType as its value_type
+  using VertexIterator = typename VertexMapT::iterator;
+
+  /// 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:
+    using iterator =
+        typename std::conditional<isConst, ConstVertexIterator,
+                 VertexIterator>::type;
+    using const_iterator = ConstVertexIterator;
+    using GraphT = typename std::conditional<isConst, const Graph, Graph>::type;
+
+  private:
+    GraphT &G;
+
+  public:
+    iterator begin() { return G.Vertices.begin(); }
+    iterator end() { return G.Vertices.end(); }
+    const_iterator cbegin() const {return G.Vertices.cbegin();}
+    const_iterator cend() const {return G.Vertices.cend();}
+    const_iterator begin() const {return G.Vertices.begin();}
+    const_iterator end() const {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> {
+    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));
+    }
+
+    bool operator!=(const const_iterator &b) const {
+      return !((*this) == b);
+    }
+
+    EdgeListIterator &operator++() { // pre-increment
+      ++BotIt;
+      if (BotIt == TopIt->second.end()) {
+        ++TopIt;
+        if (TopIt != TopEnd)
+          BotIt = TopIt->second.begin();
+      }
+      return *this;
+    }
+
+    reference operator*() const { 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:
+    using iterator = typename std::conditional<isConst, ConstEdgeIterator,
+                                      EdgeIterator>::type;
+    using const_iterator = ConstEdgeIterator;
+    using GraphT = typename std::conditional<isConst, const Graph, Graph>::type;
+
+  private:
+    GraphT &G;
+
+  public:
+    iterator begin() { return iterator(G.Edges.begin(), G.Edges.end()); }
+    const_iterator cbegin() const{
+      return const_iterator(G.Edges.cbegin(), G.Edges.cend());
+    }
+    const_iterator begin() const{
+      return cbegin();
+    }
+    iterator end() {
+      auto e = G.Edges.end();
+      return iterator(e, e);
+    }
+    const_iterator cend() const {
+      auto e = G.Edges.cend();
+      return const_iterator(e, e);
+    }
+    const_iterator end() const {
+      return cend();
+    }
+    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) {
+    return Vertices.FindAndConstruct(I).second;
+  };
+
+  /// 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) {
+    auto &p1 = Edges.FindAndConstruct(I.first);
+    if(p1.second.count(I.second) == 1){
+      return p1.second[I.second];
+    }
+    auto &p2 = p1.second.FindAndConstruct(I.second);
+    Vertices.FindAndConstruct(I.first);
+    Vertices.FindAndConstruct(I.second);
+    InnerInvGraphT &ITRef = InvGraph[I.second];
+    ITRef.insert(I.first);
+    p2.first.first = I.first;
+    ++NumEdges;
+    return p2.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) = default;
+
+  ~Graph() = default;
+
+
+  Graph &operator=(const Graph &other) = default;
+
+  Graph &operator=(Graph &&other) noexcept = default;
+
+  /// 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. If the key is already in the map, it returns false
+  /// and doesn't update the value.
+  std::pair<EdgeIterator, bool> insert(const EdgeValueType &Val) {
+    auto p1 = Edges.FindAndConstruct(Val.first.first);
+    auto p2 = p1.second.insert({Val.first.second, Val.second});
+    if(!p2.second){
+      Vertices.insert({Val.first.first, VertexAttribute()});
+      Vertices.insert({Val.first.second, VertexAttribute()});
+      InnerInvGraphT &ITRef = InvGraph[Val.first.second];
+      ITRef.insert(Val.first.first);
+      p2.first->first.first = Val.first.first;
+      ++NumEdges;
+    };
+
+    return {EdgeIterator(p1.first, Edges.end(), p2.first), p2.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,45 +30,45 @@
 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(""));
+    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 +88,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"),
@@ -113,12 +113,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"),
@@ -138,12 +138,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"),
@@ -163,7 +163,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); }
 
@@ -208,14 +208,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)
@@ -230,23 +229,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;
   }
   }
@@ -280,38 +281,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();
   }
 }
 
@@ -329,19 +324,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
@@ -477,7 +470,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);
@@ -487,18 +483,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);
@@ -507,7 +505,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";
@@ -521,7 +519,7 @@
 //
 // 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 +579,6 @@
     handleAllErrors(std::move(E),
                     [&](const ErrorInfoBase &E) { E.log(errs()); });
   }
-
   GR.exportGraphAsDOT(OS, Header, GraphEdgeLabel, GraphEdgeColorType,
                       GraphVertexLabel, GraphVertexColorType);
   return Error::success();