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 +#include +#include +#include + +#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 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 > +class Graph { +public: + /// These objects are used to name edges and vertices in the graph. + typedef VI VertexIdentifier; + typedef std::pair EdgeIdentifier; + + /// A child type of std::pair and should be + /// treated as such. This type is the value_type of all iterators which range + /// over sets of vertices. + typedef detail::DenseMapPair + VertexValueType; + + /// EdgeValueType, a child type of std::pair, + /// 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 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 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 { + VertexIdentifier &getFirst() { + return std::pair::first.second; + } + + const VertexIdentifier &getFirst() const { + return std::pair::first.second; + } + + EdgeAttribute &getSecond() { + return std::pair::second; + } + + const EdgeAttribute &getSecond() const { + return std::pair::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; + + /// 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; + + /// The type used for storing the VertexAttribute for each vertex in + /// the graph. + using VertexMapT = DenseMap; + + /// 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; + + /// 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; + +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 ::type> + class InEdgeIteratorInt + : public iterator_adaptor_base< + InEdgeIteratorInt, BaseIt, + typename std::iterator_traits::iterator_category, T> { + using InternalEdgeMapT = + typename std::conditional::type; + + friend class InEdgeIteratorInt; + friend class InEdgeIteratorInt; + + InternalEdgeMapT *MP; + VertexIdentifier SI; + + public: + template ::type> + operator InEdgeIteratorInt() + const { + return InEdgeIteratorInt( + this->I, MP, SI); + } + + InEdgeIteratorInt() = default; + InEdgeIteratorInt(BaseIt _I, InternalEdgeMapT *_MP, VertexIdentifier _SI) + : iterator_adaptor_base< + InEdgeIteratorInt, BaseIt, + typename std::iterator_traits::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; + + /// An iterator type for iterating through the set of edges leaving a vertex. + /// + /// Has an EdgeValueType as its value_type + using InEdgeIterator = InEdgeIteratorInt; + + /// 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 class InEdgeView { + public: + using iterator = InEdgeIteratorInt; + using const_iterator = InEdgeIteratorInt; + using GraphT = typename std::conditional::type; + using InternalEdgeMapT = + typename std::conditional::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 class VertexView { + public: + using iterator = + typename std::conditional::type; + using const_iterator = ConstVertexIterator; + using GraphT = typename std::conditional::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 + class EdgeListIterator + : public iterator_facade_base< + EdgeListIterator, std::forward_iterator_tag, + typename std::conditional::type> { + typedef + typename std::conditional::type TopItT; + typedef typename std::conditional< + IsConst, typename InnerEdgeMapT::const_iterator, + typename InnerEdgeMapT::iterator>::type BotItT; + + typedef EdgeListIterator const_iterator; + typedef typename std::iterator_traits>::reference + reference; + + friend class EdgeListIterator; + friend class EdgeListIterator; + + 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 ::type> + EdgeListIterator(const EdgeListIterator &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 ConstEdgeIterator; + + /// An iterator for iterating through the entire edge set of the graph. + /// + /// Has an EdgeValueType as its value_type + typedef EdgeListIterator 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 class EdgeView { + public: + using iterator = typename std::conditional::type; + using const_iterator = ConstEdgeIterator; + using GraphT = typename std::conditional::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 vertices() { return VertexView(*this); }; + + VertexView vertices() const { return VertexView(*this); }; + + /// Returns a view object allowing iteration over the edges of the graph. + /// also allows access to the size of the edge set. + EdgeView edges() { return EdgeView(*this); }; + + EdgeView edges() const { return EdgeView(*this); }; + + /// Returns a view object allowing iteration over the edges which point to + /// a vertex I. + InEdgeView inEdges(const VertexIdentifier I) { + return InEdgeView(*this, I); + } + + InEdgeView inEdges(const VertexIdentifier I) const { + return InEdgeView(*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 at(const VertexIdentifier &I) { + auto It = Vertices.find(I); + if (It == Vertices.end()) + return make_error( + "Vertex Identifier Does Not Exist", + std::make_error_code(std::errc::invalid_argument)); + return It->second; + }; + + Expected at(const VertexIdentifier &I) const { + auto It = Vertices.find(I); + if (It == Vertices.end()) + return make_error( + "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 at(const EdgeIdentifier &I) { + auto It = Edges.find(I.first); + if (It == Edges.end()) + return make_error( + "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( + "Edge Identifier Does Not Exist", + std::make_error_code(std::errc::invalid_argument)); + return It2->second; + }; + + Expected at(const EdgeIdentifier &I) const { + auto It = Edges.find(I.first); + if (It == Edges.end()) + return make_error( + "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( + "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 insert(const VertexValueType &Val) { + return Vertices.insert(Val); + }; + std::pair 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 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 Timings; + std::vector Timings; }; /// An Inner Struct for storing vertex attributes, at the moment just @@ -78,17 +80,15 @@ typedef DenseMap PerThreadFunctionStackMap; -private: - /// The Graph stored in an edge-list like format, with the edges also having - /// An attached set of attributes. - DenseMap> Graph; - - /// Graph Vertex Attributes. These are presently stored seperate from the - /// main graph. - DenseMap VertexAttrs; + class GraphT : public Graph { + 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 @@ -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 GraphInput(cl::Positional, cl::desc(""), - cl::Required, cl::sub(Graph)); + cl::Required, cl::sub(GraphC)); static cl::opt 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 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 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 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 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 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 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 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 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>> - 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 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();