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

[varno]

Summary

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

Depends on D28999, D28225

[varno]

Minimise the lib components, to add remaining changes on an as need
basis.

[varno]

• move inner class to llvm::xray::internal

[varno]

• fix Spelling mistakes

[dberris]

As @dblaikie already mentioned, it's a really good idea to give this a good set of unit tests given the complexity of the implementation of this type.

include/llvm/XRay/Graph.h

27–30

Please put one space between the namespace name and the opening {.

33

s/poiter/pointer/

38

The name seems to be misleading. I think this is a transforming iterator (applies a function on dereference). A lot of the machinery being implemented here seems unnecessary if you define this in terms of the already existing iterator adapter type in llvm/ADT/iterator.h -- have you considered doing that either for this iterator?

67

Unnecessary empty line?

78–80

I don't think you need this defined in the body of the constructor -- you can initialise H directly with this lambda.

81

Spurious semicolon.

83

You can probably just use non-static data member initialisation for these (instead of having a mix of an initialiser list and an in-constructor definition). That way you can =default this constructor instead.

Also you have a spurious semicolon at the end of a function definition.

85–86

Please avoid using names with leading underscores.

86

Spurious semicolon.

98

Empty line after this?

106

Empty line after this?

116–121

For types that are user-facing, it's usually preferred that it's documented to at least contain the following:

• Important semantic concepts. In this domain (of graphs), say what kind of graph this represents (labelled directed graph).
• Usage examples (how to use this, say as how library users might use it).
• Requirements on the parametric types, as this is a template.

121

Space between identifier and {?

131

Why the inheritance? Will this not work with composition instead? Or is this for the empty base optimisation?

132–143

Since you're giving names anyway, consider using more descriptive ones (like getVertexId and getEdgeAttr).

146–164

I may be wrong, but there seems to be a slight preference for using instead of typedef now.

167–171

Probably document these a little better?

185–223

This doesn't seem like an iterator to me, so the name is a little misleading. This seems to be more of a View into the data, or a range.

225–246

I think you want to call this a view as well, instead of a proxy.

242

This function may be always const?

288–290

Typos?

313

Should be no space between operator and ++?

337–358

I think this really ought to be named a View.

433–436

Is this necessary to implement this way? Can we get away with making copies of the underlying data instead?

I mean, wouldn't it be valid if we just kept this = default also?

481

I'm wondering whether you need to keep track of this value yourself (or whether it's something one of the data structures already keeps track of, that you can just return)?

tools/llvm-xray/xray-graph.h

79–82

Consider using better names than generic terms like VertexAttribute -- in the context of XRay this might be FunctionStats, and EdgeAttribute might better be CallStats.

[varno]

• move inner class to llvm::xray::internal
• fix Spelling mistakes
• Make Graph.h cleaner
• fix bugs and respond to comments
• add comments
• fix

[varno]

• clang-format

[varno]

include/llvm/XRay/Graph.h

131

It was not required, fixed.

132–143

Explained in comment

433–436

Sadly no, it does not work. :( (that was the first thing I tried, and it caused failed tests.)

481

This is not tracked in a single place anywhere, It could be recalculated every time you want to query If you think that would be better.

[dberris]

include/llvm/XRay/Graph.h

11

This isn't entirely accurate -- now that this is in include/llvm/XRay/... then it's no longer just for the llvm-xray graph subcommand.

31

s/XRAY/XRay/

35

Each variable? Or each Vertex?

48

Why this, as opposed to:

Graph<int, int, int> G;

60

You don't really need this copy example, just state that Graph is CopyConstructible, CopyAssignable, MoveConstructible, and MoveAssignable (but has no strict weak partial ordering nor equality, which may or may not be something you'd want to implement anyway).

76–87

s/whilst/while/

Break up the run-on sentence into shorter sentences too.

86

s/Please don't use them.//

131

I still see it doing inheritance -- was this an oversight?

146–164

i.e. instead of:

typedef Foo X;

say:

using X = Foo;

279

For classes, it's already implicit that members are private unless otherwise specified. You may omit this, and the one following it in line 293.

301

Space before the {.

305

This initialisation can happen in the initializer list too.

433–436

Please say more -- it's not clear why an explicit copy of the members doesn't just work.

484

Maybe use 'auto' here instead?

auto TI = Edges.find(Val.first.first);

Also, alternatively you can alias the members of the pairs with more descriptive names.

tools/llvm-xray/xray-graph.h

142

Empty line before?

[varno]

• move inner class to llvm::xray::internal
• fix Spelling mistakes
• Make Graph.h cleaner
• fix bugs and respond to comments
• add comments
• fix
• clang-format
• address missed comments to the color commit
• add at method to Graph

[varno]

Rebase to master

[dblaikie]

Some drive by comments - up to you & Dean how you prioritize them, etc.

include/llvm/XRay/Graph.h

80–82

I don't understand this explanation - I'm not sure how these member functions would "enable references to look like std::pair". Could you explain further?

88

This seems like a strange class - it doesn't look like it provides any encapsulation (public inheritance) & the names don't provide any extra documentation. I'd suggest using std::pair directly without this extra type.

106

Drop the 'class' keyword in all these typedefs

166–172

Seems more common, perhaps a bit simpler/more obvious, to implement non-const iterator to const iterator conversion as a converting ctor rather than a conversion operator. Though probably no real concern either way, I guess? Haven't thought about it in great detail before.

180

Should probably be a const member

188

Drop the 'class' keyword here as it's not needed, I think? (& similarly below)

231

Spurious semicolon

(actually every member function in this class has a semicolon at the end - probably need to do a pass to remove those across this change/others)

260–261

const overloads?

264

Spurious semicolon

317–319

where possible, make operator overloads non-members (this ensures equal treatment of the LHS and RHS - as-is, this wouldn't be usable for comparisons with const_iterator on the LHS, for example)

331

this should probably be const?

[dblaikie]

include/llvm/XRay/Graph.h

403–406

Does two lookups (count and insert). Avoid that if you can (usually by using "insert" and checking the bool element of the pair returned)

415–418

Similar double lookup

497–515

Could use the unified assignment operator if you like, maybe (pass by value, then swap)

529–530

calling insert might be more obvious. Explicitly calling operator overloads is generally a bit 'weird'.

[dberris]

Aside from addressing @dblaikie's comments, please also make sure that the documentation questions raised earlier are addressed too.

Marking this with "Requested Changes" to remove from my "needs review" list.

include/llvm/XRay/Graph.h

367

Please do not use names that start with _.

370

This section s already public, why the repetition here?

tools/llvm-xray/xray-graph.cc

481

Why the empty line?

[varno]

• Address Reviewer comments
• reply to comments
• rebase on top of D29610 and simplify implementation.

[varno]

fix up dependancy

[varno]

try again

[varno]

• Address Reviewer comments
• reply to comments

[varno]

include/llvm/XRay/Graph.h

88

Please see the new Comments to explain this class class.

166–172

In this case I cannot define this as a converting ctor, as I need to access a protected member of my parent, which I cannot do in a converting ctor :(=.

317–319

Well actually in this case yes, it is defined symetrically due to the Boolean template behavior of this class. however this does expose a problem in iterator_facade_base which I have to work around.

[varno]

• Address Reviewer comments
• reply to comments
• clang-format

[dberris]

While thinking about this more, it's going to be really hard to start understanding what the semantics we're optimising for are without unit tests. This class is sufficiently complex in implementation that I think we really ought to spend as much time as we can writing up unit tests that will exercise the parts of the code that are really important (in this case that the graph we're building is representing the graph we intend to build) and that we're able to implement the basic graph algorithms like breadth-first-search or depth-first-search on top of the interface of this graph type. The risk right now of not implementing unit tests is that any changes we make to this type's implementation will introduce subtle bugs that will break the basic use-cases while serving only the ones that the llvm-xray graph/graph-diff tools need.

I understand that there's some urgency here, I'd be really happy with covering basic tests covering the most basic of features of this type.

include/llvm/XRay/Graph.h

42–45

This seems like it's leaking implementation details. Why should the user of the type need to know about DenseMapInfo?

50–62

Some well-placed empty lines here would help readability.

/// Usage:
///
///    Graph<int, int, int> G;
///    G[1] = 0;
///    G[2] = 1;
///    G[{1, 2}] = 2;
///
///    for (const auto& V : G.vertices()) {
///       // V will be an int, do something with it here.
///    }
///
///    for (const auto &E : G.edges()) {
///        // E will be a std::pair<int, int>, do something with it here.
///    }
///
///    // show an example on what to do with the third int?

63

While you do provide documentation for the views and for some of the member operations, please provide documentation about things like:

• Space complexity/requirements.
• Complexity of operations like insertion, removal if that's supported, point-wise lookup, etc.
• What the semantics are for certain operations -- how do failures get conveyed, what are the invariants that are preserved that's useful to know from a user's perspective, etc.

72–74

I don't know whether saying that this is derived from std::pair<...> is important to document. This seems like an implementation detail that doesn't help the user of this class at all. Probably say what this type is useful for -- probably important to say that this represents the vertex and the attributes associated with it.

78–80

Likewise here, I don't see why it's important to tell the reader that you should treat this type as a pair.

81–89

Why is this documentation on this internal class, as opposed to documentation on the operations on the graph type? i.e. why is it important to mention that this is a child of std::pair<...> -- as opposed to saying why this is derived from std::pair<...> instead?

91–96

All this documentation seems like implementation detail documentation. This will not be helpful when the doxygen docs are generated and read by users of this type. Remember this is getting into the set of LLVM libraries, and can be used on its own as opposed to just serving the purposes of llvm-xray graph or similar requirements.

99–113

We still don't have documentation as to "why" these member functions exist, and why we're not just using a DenseMap<pair<VertexIdentifier, VertexIdentifier>, EdgeAttribute>. This still isn't clear from the documentation that's been so far mentioned here. Also it's not clear why the adjacency list being stored isn't just an unordered_map<VertexIdentifier, pair<VertexIdentifier, EdgeAttribute>>, and lookup for all the adjacent vertices (or even out-edges) will be given by equal_range(VertexIdentifier).

Since we're already adapting iterators anyway, I'm sure you can turn an iterator that yields a pair<VertexIdentifier, pair<VertexIdentifier, EdgeAddtribute>> into something that yields a tuple<VertexIdentifier&, VertexIdentifier&, EdgeAttribute&> with appropriate const-ness of members.

For in-edge and out-edge and attribute storage, you could have done it this way:

using EdgeAttributeContainer = std::list<EdgeAttribute>;
std::list<EdgeAttribute> EdgeAttributes;
unordered_multimap<VertexIdentifier, pair<VertexIdentifier, EdgeAttributeContainer::iterator>> OutEdges;
unordered_multimap<VertexIdentifier, pair<VertexIdentifier, EdgeAttributeContainer::iterator>> InEdges;
unordered_multimap<pair<VertexIdentifier, VertexIdentifier>, EdgeAttributeContainer::iterator>> EdgeLookup;

Since you're already defining your own iterators, they could have been simpler lookup, and still have the consistent interface.

I'm not saying this is how you should do it, I'm asking why this isn't what's being done, and the documentation (either internal for the implementer/reader or external generated from this type) isn't answering this question.

140–141

Consider moving this and all public declarations together for easier reading.

352–354

Why can't this be defined as a non-member like so:

friend template <bool IsConstL, bool IsConstR>
bool operator==(const EdgeListIterator<IsConstL>&L, const EdgeListIterator<IsConstR>&R) {
  return ...;
}

This way it's defined with the class and it's also accessible only through ADL?

356

If you defined this as a non-member, it would look like:

friend bool operator!=(...) {
  return !(L == R);
}

558

LLVM Style wants local identifiers starting with capital letters.

tools/llvm-xray/xray-graph.cc

303

Pro-tip: when asserting, provide some human-readable explanation for what the expectation is. As in:

assert((/* complicated conditional */) && "We want a pony, but got a unicorn!");

[dblaikie]

Few more drive-by comments.

include/llvm/XRay/Graph.h

88

Sorry, it's still unclear to me what this class provides over using std::pair directly. (but it sounds like Dean's in on the discussion and has some higher-level feedback/ideas/etc that might motivate a different direction or help sure up this one)

539–540

two lookups (count + find) - avoid that by using find and then checking end, etc.

564

Extra semicolon (there are a whole bunch in this class/generally - remove them all)

572

Missing spaces (run this all through clang-format?)

579

Extra semicolon

582

Extra semicolon

tools/llvm-xray/xray-graph.cc

503–505

LLVM code usually skips {} on single line statements.

[varno]

include/llvm/XRay/Graph.h

42–45

DenseSet and other Derived classes seem to do this too.
It does leak some implementation details, but really only that we use DenseMap,
From that you get the ability to implement for more VertexIdentifier types, the limitation
for key would be the same anyway.

99–113

I cannot quite do this, however something simmilar probably could be done. (The problem with unordered_multimap is the cost of edge-deletion :(. The code complexity of this would increase slightly. If we were to go this way I would probably implement it more like:

DenseMap<VertexIdentifier, Set<VertexIdentifier>> OutEdges;
DenseMap<VertexIdentifier, Set<VertexIdentifier>> InEdges;
DenseMap<pair<VertexIdentifier, VertexIdentifier>, EdgeAttribute>> EdgeLookup;

Which would increase the size somewhat, but would probably work fine.

If you want I can go ahead with that?

[varno]

• Address major reviewer comment and initial tests

[dberris]

Please address all comments.

include/llvm/XRay/Graph.h

42–45

I'm a little uneasy with the requirements being imposed on VI here. Let me ask a different question: can we just remove this? Why is this essential if we're not relying on DenseMap requirements anymore in the implementation? And if we are using DenseMap, can we get away with just not even mentioning this type in the interface of Graph?

I'm trying to further simplify this type because it's currently really hard to explain why VI is there just by looking at what this type is supposed to do.

50–62

I don't see it done.

213–214

Empty line in between?

221–222

Empty line in between?

231

You're doing two lookups here. Consider just doing one lookup using iterators.

316

I'd remove this comment.

365

LLVM Style uses capital letters for local variable names.

tools/llvm-xray/xray-graph.h

123

Probably not for now, but it would be great if we can construct a graph with a terse interface. Something like:

Graph<int, int, int> G(
  {1, 2, 3, 4, 5},
  {{1, 2}, {2, 3}, {3, 4}});

Maybe write as a TODO on the Graph type?

unittests/XRay/GraphTest.cpp

1 ↗

(On Diff #87595)

Please have more basic tests (construction, copy-construction, assignment, move construction, etc.), smaller and more focused test cases for more interface and semantics-related tests.

19 ↗

(On Diff #87595)

This comment seems nothing to do with the graph. Sets? Hashing? This seems to be leaking implementation details, so let's avoid that by only keeping this about the graph.

24 ↗

(On Diff #87595)

This comment seems out of place.

46–47 ↗

(On Diff #87595)

Probably needs to be ASSERT_EQ because if this isn't true it doesn't make sense to proceed with the test case.

50–51 ↗

(On Diff #87595)

Spurious whitespace.

52–53 ↗

(On Diff #87595)

Use consumeError(...) instead?

60–83 ↗

(On Diff #87595)

Break out into a different test case, please, give it a name that describes what the case is actually testing.

66 ↗

(On Diff #87595)

Consider EXPECT_TRUE(bool{T}) instead.

[varno]

• more tests and a fix

[varno]

• Address Review Commits

include/llvm/XRay/Graph.h

42–45

We are still using DenseMap, and so the question.

VI needs to be there, because the type is int for Graph and StrRef for Graph Diff.

316

It was not a problem anymore anyway.

433–436

Oh, in the new version it does work. That is why there is no constructors non-default anymore :)

[dberris]

Almost ready to land. One thing that needs to be addressed are the spurious semicolons (will cause the buildbots that build with -pedantic to complain loudly).

The tests could be better, but those could be improved post-commit.

[varno]

• spurious semicolons

include/llvm/XRay/Graph.h

+//===-- 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{
+
+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:
+  /// 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_gategory;
+
+    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, VertexIdentifier 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;
+    }
+  };
+
+  /// A bunch of typedefs using the ProxiedIterator class implement them
+  typedef class ProxiedIterator<typename InnerInvGraphT::const_iterator,
+                                const EdgeMapT,
+                                VertexIdentifier,
+                                const InnerEdgeMapT> ConstInEdgeIterator;
+  typedef class ProxiedIterator<typename InnerInvGraphT::const_iterator,
+                                EdgeMapT,
+                                VertexIdentifier,
+                                InnerEdgeMapT> InEdgeIterator;
+
+  typedef class ProxiedIterator<typename InnerInvGraphT::ConstIterator,
+                          const VertexMapT, int> ConstInNeighborIterator;
+  typedef class ProxiedIterator<typename InnerInvGraphT::ConstIterator,
+                          VertexMapT, int> InNeighborIterator;
+
+  typedef class ProxiedIterator<typename InnerEdgeMapT::const_iterator,
+                          const VertexMapT, int> ConstOutNeighborIterator;
+  typedef class ProxiedIterator<typename InnerEdgeMapT::const_iterator,
+                          VertexMapT, int> OutNeighborIterator;
+
+  /// A bunch of proky objects to instantiate the various iterator types.
+  template <bool isConst>
+  class OutEdgeIteratorProxy {
+   public:
+    typedef typename std::conditional<isConst, ConstOutEdgeIterator, OutEdgeIterator>::type Iterator;
+    typedef typename std::conditional<isConst, const Graph, Graph>::type GraphT;
+   private:
+    GraphT &G;
+    const VertexIdentifier A;
+   public:
+    Iterator begin(){
+      auto It = G.Edges.find(A);
+      if (It == G.Edges.end())
+        return Iterator();
+      return It->second.begin();
+    };
+    Iterator end(){
+      auto It = G.Edges.find(A);
+      if (It == G.Edges.end())
+        return Iterator();
+      return It->second.end();
+    };
+    size_type size() const{
+      return (G.Edges.count(A) == 1)? G.Edges.find(A)->second.size(): 0;
+    };
+    bool empty() const{
+      return G.Edges.count(A) == 0;
+    };
+
+    OutEdgeIteratorProxy (GraphT &_G,
+                    const VertexIdentifier _A): G(_G), A(_A){};
+  };
+
+  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 OutNeighborIteratorProxy {
+   public:
+    typedef typename std::conditional<isConst, ConstOutNeighborIterator, OutNeighborIterator>::type Iterator;
+    typedef typename std::conditional<isConst, const Graph, Graph>::type GraphT;
+    typedef typename std::conditional<isConst, const VertexMapT, VertexMapT>::type IntVertexMapT;
+    typedef ConstOutEdgeIterator BaseIt;
+    typedef typename Iterator::RetIt RetIt;
+   private:
+    GraphT &G;
+    const VertexIdentifier A;
+    RetIt (*convert)(BaseIt, IntVertexMapT &, int);
+   public:
+    Iterator begin(){
+      auto It = G.Edges.find(A);
+      if (It == G.Edges.end())
+        return Iterator();
+      return Iterator(It->second.begin(), G.Vertices, convert, 0);
+    };
+    Iterator end(){
+      auto It = G.Edges.find(A);
+      if (It == G.Edges.end())
+        return Iterator();
+      return Iterator(It->second.end(), G.Vertices, convert, 0);
+    };
+    size_type size() const{
+      return (G.Edges.count(A) == 1)? G.Edges.find(A)->second.size() : 0;
+    };
+    bool empty() const{
+      return G.Edges.count(A) == 0;
+    };
+
+    OutNeighborIteratorProxy (GraphT &_G,
+                    const VertexIdentifier _A): G(_G), A(_A){
+      convert = [](BaseIt It, IntVertexMapT &C, int) -> RetIt{
+          return C.find(It->first.second);
+      };
+    };
+  };
+
+  template <bool isConst>
+  class InNeighborIteratorProxy {
+   public:
+    typedef typename std::conditional<isConst, ConstInNeighborIterator, InNeighborIterator>::type Iterator;
+    typedef typename std::conditional<isConst, const Graph, Graph>::type GraphT;
+    typedef typename std::conditional<isConst, const VertexMapT, VertexMapT>::type IntVertexMapT;
+    typedef typename DenseSet<VertexIdentifier>::ConstIterator BaseIt;
+    typedef typename Iterator::RetIt RetIt;
+
+   private:
+    GraphT &G;
+    const VertexIdentifier A;
+    RetIt (*convert)(BaseIt, IntVertexMapT &, int);
+   public:
+    Iterator begin(){
+      auto It = G.InvGraph.find(A);
+      if (It == G.InvGraph.end())
+        return Iterator();
+      return Iterator(It->second.begin(), G.Vertices, convert, 0);
+    };
+    Iterator end(){
+      auto It = G.InvGraph.find(A);
+      if (It == G.InvGraph.end())
+        return Iterator();
+      return Iterator(It->second.end(), G.Vertices, convert, 0);
+    };
+    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;
+    };
+
+   InNeighborIteratorProxy (GraphT &_G,
+                    const VertexIdentifier _A): G(_G), A(_A){
+      convert = [](BaseIt It, IntVertexMapT &C, int) -> RetIt{
+        return C.find(*It);
+      };
+    };
+  };
+
+  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);
+  }
+
+  /// Returns a proxy object allowing iteration over the edges which start at
+  /// a vertex I.
+  OutEdgeIteratorProxy<false> outEdges(const VertexIdentifier I){
+    return OutEdgeIteratorProxy<false>(*this, I);
+  }
+
+  OutEdgeIteratorProxy<true> outEdges(const VertexIdentifier I) const{
+    return OutEdgeIteratorProxy<true>(*this, I);
+  }
+
+  /// Returns a proxy object allowing iteration over the vertices which are
+  /// in-neighbors of a vertex I.
+  InNeighborIteratorProxy<false> inNeighbors(const VertexIdentifier I){
+    return InNeighborIteratorProxy<false>(*this, I);
+  }
+
+  InNeighborIteratorProxy<true> inNeighbors(const VertexIdentifier I) const{
+    return InNeighborIteratorProxy<true>(*this, I);
+  }
+
+  /// Returns a proxu object allowing iteration over the vertices which are
+  /// out neighbors of a vertex I.
+  OutNeighborIteratorProxy<false> outNeighbors(const VertexIdentifier I){
+    return OutNeighborIteratorProxy<false>(*this, I);
+  }
+
+  OutNeighborIteratorProxy<true> outNeighbors(const VertexIdentifier I) const{
+    return OutNeighborIteratorProxy<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;
+  }
+
+  /// 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;
+  };
+
+  /// 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};
+  };
+
+  /// Inserts all elements between I and V, These pointers
+  /// must dereference into VertexValueType or EdgeValueType
+  template <typename InputIt>
+  void insert(InputIt I, InputIt E){
+    for(const auto &v: llvm::make_range(I, E))
+      insert(v);
+  };
+
+  /// Inserts all the vertices specified in an Initialiser List.
+  void insert(std::initializer_list<VertexValueType> ilist){
+    for(auto&& v: ilist)
+      insert(v);
+  };
+
+  /// Inserts all the edges specified in an Initialiser List.
+  void insert(std::initializer_list<EdgeValueType> ilist){
+    for(auto&& v: ilist)
+      insert(v);
+  };
+
+  /// Erases the vertes/edge pointed to by pos, and
+  /// returns the next element in the sequence.
+  template <typename CIteratorT>
+      CIteratorT erase(CIteratorT pos){
+        auto Id = pos->first;
+        ++pos;
+        erase(Id);
+        return pos;
+      };
+
+  /// Erases the vertices/edges between I and E, and
+  /// returns the following element in the sequence.
+  template <typename CIteratorT>
+  CIteratorT erase(CIteratorT I, CIteratorT &E){
+    for(; I != E; ++I){
+      auto Id = I->first;
+      ++I;
+      erase(Id);
+    }
+    return I;
+  };
+
+  /// Deletes the vertex with Identifier Key;
+  size_type erase(const VertexIdentifier &Key){
+    erase(inEdges(Key).begin(), inEdges(Key).end());
+    erase(outEdges(Key).begin(), outEdges(Key).end());
+    return Vertices.erase(Key)? 1 : 0;
+  };
+
+  /// Deletes the edge with Identifier Key.
+  size_type erase(const EdgeIdentifier &Key){
+    if(Edges.count(Key.first) == 0 || Edges[Key.first].count(Key.second) == 0){
+      return 0;
+    }
+    Edges[Key.first].erase(Key.second);
+    if(Edges[Key.first].size() == 0)
+      Edges.erase(Key.first);
+    InvGraph[Key.second].erase(Key.first);
+    if(InvGraph[Key.second].size() == 0){
+      InvGraph.erase(Key.second);
+    };
+
+    return 1;
+  };
+};
+}
+}
+#endif

tools/llvm-xray/xray-graph.h

 #include "func-id-helper.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/Support/Errc.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Support/Program.h"
 #include "llvm/XRay/Trace.h"
 #include "llvm/XRay/XRayRecord.h"
+#include "llvm/XRay/Graph.h"
 
 namespace llvm {
 namespace xray {
 
 /// A class encapsulating the logic related to analyzing XRay traces, producting
 /// Graphs from them and then exporting those graphs for review.
 class GraphRenderer {
 public:
   /// An enum for enumerating the various statistics gathered on latencies
   enum class StatType { NONE, COUNT, MIN, MED, PCT90, PCT99, MAX, SUM };
 
   /// An inner struct for common timing statistics information
   struct TimeStat {
     uint64_t Count = 0;
     double Min = 0;
     double Median = 0;
     double Pct90 = 0;
     double Pct99 = 0;
     double Max = 0;
     double Sum = 0;
     std::string getAsString(StatType T) const;
     double compare(StatType T, const TimeStat &Other) const;
   };
+  typedef uint64_t TimestampT;
 
   /// An inner struct for storing edge attributes for our graph. Here the
   /// attributes are mainly function call statistics.
   ///
   /// FIXME: expand to contain more information eg call latencies.
   struct EdgeAttribute {
     TimeStat S;
-    std::vector<uint64_t> Timings;
+    std::vector<TimestampT> Timings;
   };
 
   /// An Inner Struct for storing vertex attributes, at the moment just
   /// SymbolNames, however in future we could store bulk function statistics.
   ///
   /// FIXME: Store more attributes based on instrumentation map.
   struct VertexAttribute {
     std::string SymbolName;
     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;
-
-  /// Graph Vertex Attributes. These are presently stored seperate from the
-  /// main graph.
-  DenseMap<int32_t, VertexAttribute> VertexAttrs;
+  struct GraphAttribute{
+    TimeStat GraphEdgeMax = {};
+    TimeStat GraphVertexMax = {};
+  };
+
 
-  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
   /// graph.
   ///
   /// FIXME: Perhaps we can Build this into LatencyAccountant? or vise versa?
   DenseMap<llvm::sys::ProcessInfo::ProcessId, SmallVector<FunctionAttr, 4>>
       PerThreadFunctionStack;
 
   /// 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>
   void getStats(U begin, U end, GraphRenderer::TimeStat &S);
   void updateMaxStats(const TimeStat &S, TimeStat &M);
 
   /// Calculates latency statistics for each edge and stores the data in the
   /// Graph
   void calculateEdgeStatistics();
 
   /// Calculates latency statistics for each vertex and stores the data in the
   /// Graph
   void calculateVertexStatistics();
 
   /// Normalises latency statistics for each edge and vertex by CycleFrequency;
   void normalizeStatistics(double CycleFrequency);
 
 public:
   /// Takes in a reference to a FuncIdHelper in order to have ready access to
   /// Symbol names.
   explicit GraphRenderer(FuncIdConversionHelper &FuncIdHelper, bool DSC)
-      : FuncIdHelper(FuncIdHelper), DeduceSiblingCalls(DSC) {}
+      : FuncIdHelper(FuncIdHelper), DeduceSiblingCalls(DSC) {
+       G[0] = {};
+      }
 
   /// Process an Xray record and expand the graph.
   ///
   /// This Function will return true on success, or false if records are not
   /// presented in per-thread call-tree DFS order. (That is for each thread the
   /// Records should be in order runtime on an ideal system.)
   ///
   /// FIXME: Make this more robust against small irregularities.
   Error accountRecord(const XRayRecord &Record);
 
   /// Output the Embedded graph in DOT format on \p OS, labeling the edges by
   /// \p T
   void exportGraphAsDOT(raw_ostream &OS, const XRayFileHeader &H,
                         StatType EdgeLabel = StatType::NONE,
                         StatType EdgeColor = StatType::NONE,
                         StatType VertexLabel = StatType::NONE,
                         StatType VertexColor = StatType::NONE);
+  GraphT getGraph(){
+    calculateEdgeStatistics();
+    calculateVertexStatistics();
+    return G;
+  }
 };
 }
 }
 
 #endif // XRAY_GRAPH_H

tools/llvm-xray/xray-graph.cc

-//===-- xray-graph.c - XRay Function Call Graph Renderer ------------------===//
+//===-- xray-graph.cc - XRay Function Call Graph Renderer -----------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //

 #include "llvm/Support/FormatVariadic.h"
 #include "llvm/XRay/Trace.h"
 #include "llvm/XRay/YAMLXRayRecord.h"
 
 using namespace llvm;
 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<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"),
     cl::values(clEnumValN(InstrumentationMapExtractor::InputFormats::ELF, "elf",
                           "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"),
                               clEnumValN(GraphRenderer::StatType::COUNT,
                                          "count", "function call counts"),
                               clEnumValN(GraphRenderer::StatType::MIN, "min",
                                          "minimum function durations"),
                               clEnumValN(GraphRenderer::StatType::MED, "med",
                                          "median function durations"),
                               clEnumValN(GraphRenderer::StatType::PCT90, "90p",
                                          "90th percentile durations"),
                               clEnumValN(GraphRenderer::StatType::PCT99, "99p",
                                          "99th percentile durations"),
                               clEnumValN(GraphRenderer::StatType::MAX, "max",
                                          "maximum function durations"),
                               clEnumValN(GraphRenderer::StatType::SUM, "sum",
                                          "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"),
                clEnumValN(GraphRenderer::StatType::COUNT, "count",
                           "function call counts"),
                clEnumValN(GraphRenderer::StatType::MIN, "min",
                           "minimum function durations"),
                clEnumValN(GraphRenderer::StatType::MED, "med",
                           "median function durations"),
                clEnumValN(GraphRenderer::StatType::PCT90, "90p",
                           "90th percentile durations"),
                clEnumValN(GraphRenderer::StatType::PCT99, "99p",
                           "99th percentile durations"),
                clEnumValN(GraphRenderer::StatType::MAX, "max",
                           "maximum function durations"),
                clEnumValN(GraphRenderer::StatType::SUM, "sum",
                           "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"),
                clEnumValN(GraphRenderer::StatType::COUNT, "count",
                           "function call counts"),
                clEnumValN(GraphRenderer::StatType::MIN, "min",
                           "minimum function durations"),
                clEnumValN(GraphRenderer::StatType::MED, "med",
                           "median function durations"),
                clEnumValN(GraphRenderer::StatType::PCT90, "90p",
                           "90th percentile durations"),
                clEnumValN(GraphRenderer::StatType::PCT99, "99p",
                           "99th percentile durations"),
                clEnumValN(GraphRenderer::StatType::MAX, "max",
                           "maximum function durations"),
                clEnumValN(GraphRenderer::StatType::SUM, "sum",
                           "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"),
                clEnumValN(GraphRenderer::StatType::COUNT, "count",
                           "function call counts"),
                clEnumValN(GraphRenderer::StatType::MIN, "min",
                           "minimum function durations"),
                clEnumValN(GraphRenderer::StatType::MED, "med",
                           "median function durations"),
                clEnumValN(GraphRenderer::StatType::PCT90, "90p",
                           "90th percentile durations"),
                clEnumValN(GraphRenderer::StatType::PCT99, "99p",
                           "99th percentile durations"),
                clEnumValN(GraphRenderer::StatType::MAX, "max",
                           "maximum function durations"),
                clEnumValN(GraphRenderer::StatType::SUM, "sum",
                           "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);
 }
 
 // Updates the statistics for a GraphRenderer::TimeStat
 static void updateStat(GraphRenderer::TimeStat &S, int64_t L) {
   S.Count++;
Error GraphRenderer::accountRecord(const XRayRecord &Record) {
 
   if (Record.TSC < CurrentMaxTSC)
     return make_error<StringError>("Records not in order",
                                    make_error_code(errc::invalid_argument));
 
   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)
         return make_error<StringError>("No matching ENTRY record",
                                        make_error_code(errc::invalid_argument));
       auto Parent = std::find_if(
           ThreadStack.rbegin(), ThreadStack.rend(),
           [&](const FunctionAttr &A) { return A.FuncId == Record.FuncId; });
       if (Parent == ThreadStack.rend())
         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;
   }
   }
 
   return Error::success();
 }
 
 template <typename U>
void GraphRenderer::updateMaxStats(const GraphRenderer::TimeStat &S,
   M.Median = std::max(M.Median, S.Median);
   M.Pct90 = std::max(M.Pct90, S.Pct90);
   M.Pct99 = std::max(M.Pct99, S.Pct99);
   M.Max = std::max(M.Max, S.Max);
   M.Sum = std::max(M.Sum, S.Sum);
 }
 
 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()) {
+    assert(!A.Timings.empty());
+    assert((A.Timings[0] > 0));
+    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());
       }
-    getStats(TempTimings.begin(), TempTimings.end(), VertexAttrs[V.first].S);
-    updateMaxStats(VertexAttrs[V.first].S, GraphVertexMax);
+      assert(!TempTimings.empty() && TempTimings[0] > 0);
+      getStats(TempTimings.begin(), TempTimings.end(), G[V.first].S);
+      updateMaxStats(G[V.first].S, G.GraphVertexMax);
       TempTimings.clear();
     }
   }
+}
 
 // A Helper function for normalizeStatistics which normalises a single
 // TimeStat element.
 static void normalizeTimeStat(GraphRenderer::TimeStat &S,
                               double CycleFrequency) {
   S.Min /= CycleFrequency;
   S.Median /= CycleFrequency;
   S.Max /= CycleFrequency;
   S.Sum /= CycleFrequency;
   S.Pct90 /= CycleFrequency;
   S.Pct99 /= CycleFrequency;
 }
 
 // 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
 std::string
 GraphRenderer::TimeStat::getAsString(GraphRenderer::StatType T) const {
   std::string St;
   raw_string_ostream S{St};
   switch (T) {

 // object on OS. It does this in the expected way by itterating
 // through all edges then vertices and then outputting them and their
 // annotations.
 //
 // FIXME: output more information, better presented.
 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);
 
   OS << "digraph xray {\n";
 
   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()) {
+    OS << "F" << E.first.first  << " -> "
+       << "F" << E.first.second << " [label=\"" << S.getAsString(ET) << "\"";
+      OS << " color=\"" << getColor(S.compare(EC, G.GraphEdgeMax)) << "\"";
 
-  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);
     if (VT != StatType::NONE)
       OS << "|" << VA.S.getAsString(VT) << "}\"";
     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";
 }
 
 // Here we register and implement the llvm-xray graph subcommand.
 // The bulk of this code reads in the options, opens the required files, uses
 // those files to create a context for analysing the xray trace, then there is a
 // short loop which actually analyses the trace, generates the graph and then
 // outputs it as a DOT.
 //
 // 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)
     return make_error<StringError>(
         Twine("Cannot open file '") + GraphInput + "'", EC);
 
   Error Err = Error::success();
   xray::InstrumentationMapExtractor Extractor(GraphInstrMap, InstrMapFormat,
static CommandRegistration Unused(&GraphC, []() -> Error {
   auto &Trace = *TraceOrErr;
   const auto &Header = Trace.getFileHeader();
   for (const auto &Record : Trace) {
     // Generate graph, FIXME: better error recovery.
     auto ER2 = GR.accountRecord(Record);
     if (ER2)
       return joinErrors(std::move(ER2), std::move(Err));
   }
-
+  auto Graph = GR.getGraph();
+  for(auto & V : Graph.vertices()){
+  OS << V.first << " " << Graph[V.first].S.Sum << "\n";
+  }
   GR.exportGraphAsDOT(OS, Header, GraphEdgeLabel, GraphEdgeColorType,
                       GraphVertexLabel, GraphVertexColorType);
   return Error::success();
 });