13#ifndef LLVM_XRAY_GRAPH_H
14#define LLVM_XRAY_GRAPH_H
16#include <initializer_list>
72template <
typename VertexAttribute,
typename EdgeAttribute,
73 typename VI = int32_t>
118 NeighborLookupT InNeighbors;
121 NeighborLookupT OutNeighbors;
127 template <
bool IsConst,
bool IsOut,
130 std::conditional_t<IsConst, const EdgeValueType, EdgeValueType>>
131 class NeighborEdgeIteratorT
133 NeighborEdgeIteratorT<IsConst, IsOut>, BaseIt,
134 typename std::iterator_traits<BaseIt>::iterator_category, T> {
135 using InternalEdgeMapT =
136 std::conditional_t<IsConst, const EdgeMapT, EdgeMapT>;
139 friend class NeighborEdgeIteratorT<
true, IsOut, BaseIt,
142 InternalEdgeMapT *MP;
146 template <
bool IsConstDest,
147 typename = std::enable_if_t<IsConstDest && !IsConst>>
148 operator NeighborEdgeIteratorT<IsConstDest, IsOut, BaseIt,
150 return NeighborEdgeIteratorT<IsConstDest, IsOut, BaseIt,
154 NeighborEdgeIteratorT() =
default;
155 NeighborEdgeIteratorT(BaseIt _I, InternalEdgeMapT *_MP,
158 NeighborEdgeIteratorT<IsConst, IsOut>, BaseIt,
159 typename std::iterator_traits<BaseIt>::iterator_category,
T>(_I),
164 return *(MP->find({*(this->
I),
SI}));
166 return *(MP->find({
SI, *(this->
I)}));
200 using iterator = NeighborEdgeIteratorT<isConst, isOut>;
202 using GraphT = std::conditional_t<isConst, const Graph, Graph>;
204 std::conditional_t<isConst, const EdgeMapT, EdgeMapT>;
209 const NeighborLookupT &NL;
213 auto It = NL.find(A);
216 return iterator(It->second.begin(), &M, A);
220 auto It = NL.find(A);
229 auto It = NL.find(A);
232 return iterator(It->second.end(), &M, A);
235 auto It = NL.find(A);
248 return I->second.size();
251 bool empty()
const {
return NL.count(A) == 0; };
254 : M(
G.Edges), A(A), NL(isOut ?
G.OutNeighbors :
G.InNeighbors) {}
276 std::conditional_t<isConst, ConstVertexIterator, VertexIterator>;
278 using GraphT = std::conditional_t<isConst, const Graph, Graph>;
291 bool empty()
const {
return G.Vertices.empty(); }
313 std::conditional_t<isConst, ConstEdgeIterator, EdgeIterator>;
315 using GraphT = std::conditional_t<isConst, const Graph, Graph>;
328 bool empty()
const {
return G.Edges.empty(); }
344 OutNeighbors.clear();
387 Vertices.try_emplace(
I.first);
388 Vertices.try_emplace(
I.second);
389 InNeighbors[
I.second].insert(
I.first);
390 OutNeighbors[
I.first].insert(
I.second);
396 auto It = Vertices.find(
I);
397 if (It == Vertices.end())
399 "Vertex Identifier Does Not Exist",
400 std::make_error_code(std::errc::invalid_argument));
405 auto It = Vertices.find(
I);
406 if (It == Vertices.end())
408 "Vertex Identifier Does Not Exist",
409 std::make_error_code(std::errc::invalid_argument));
415 auto It = Edges.find(
I);
416 if (It == Edges.end())
418 "Edge Identifier Does Not Exist",
419 std::make_error_code(std::errc::invalid_argument));
424 auto It = Edges.find(
I);
425 if (It == Edges.end())
427 "Edge Identifier Does Not Exist",
428 std::make_error_code(std::errc::invalid_argument));
435 return Vertices.count(
I);
444 std::pair<VertexIterator, bool>
445 insert(
const std::pair<VertexIdentifier, VertexAttribute> &Val) {
446 return Vertices.insert(Val);
449 std::pair<VertexIterator, bool>
450 insert(std::pair<VertexIdentifier, VertexAttribute> &&Val) {
451 return Vertices.insert(std::move(Val));
457 std::pair<EdgeIterator, bool>
458 insert(
const std::pair<EdgeIdentifier, EdgeAttribute> &Val) {
459 const auto &p = Edges.insert(Val);
461 const auto &EI = Val.first;
462 Vertices.FindAndConstruct(EI.first);
463 Vertices.FindAndConstruct(EI.second);
464 InNeighbors[EI.second].insert(EI.first);
465 OutNeighbors[EI.first].insert(EI.second);
474 std::pair<EdgeIterator, bool>
475 insert(std::pair<EdgeIdentifier, EdgeAttribute> &&Val) {
477 const auto &p = Edges.insert(std::move(Val));
479 Vertices.try_emplace(EI.first);
480 Vertices.try_emplace(EI.second);
481 InNeighbors[EI.second].insert(EI.first);
482 OutNeighbors[EI.first].insert(EI.second);
This file defines the DenseMap class.
This file defines the DenseSet and SmallDenseSet classes.
StandardInstrumentations SI(Mod->getContext(), Debug, VerifyEach)
DenseMapIterator< KeyT, ValueT, KeyInfoT, BucketT > iterator
DenseMapIterator< KeyT, ValueT, KeyInfoT, BucketT, true > const_iterator
Implements a dense probed hash-table based set.
Tagged union holding either a T or a Error.
DenseSetIterator< true > const_iterator
CRTP base class for adapting an iterator to a different type.
ReferenceT operator*() const
A class for ranging over all the edges in the graph.
const_iterator cend() const
const_iterator end() const
ConstEdgeIterator const_iterator
std::conditional_t< isConst, const Graph, Graph > GraphT
const_iterator cbegin() const
std::conditional_t< isConst, ConstEdgeIterator, EdgeIterator > iterator
const_iterator begin() const
A class for ranging over the incoming edges incident to a vertex.
NeighborEdgeIteratorT< isConst, isOut > iterator
const_iterator end() const
const_iterator cbegin() const
std::conditional_t< isConst, const EdgeMapT, EdgeMapT > InternalEdgeMapT
std::conditional_t< isConst, const Graph, Graph > GraphT
const_iterator begin() const
NeighborEdgeIteratorT< true, isOut > const_iterator
const_iterator cend() const
InOutEdgeView(GraphT &G, VertexIdentifier A)
A class for ranging over the vertices in the graph.
std::conditional_t< isConst, ConstVertexIterator, VertexIterator > iterator
ConstVertexIterator const_iterator
const_iterator end() const
const_iterator begin() const
const_iterator cend() const
std::conditional_t< isConst, const Graph, Graph > GraphT
const_iterator cbegin() const
A Graph object represents a Directed Graph and is used in XRay to compute and store function call gra...
std::pair< EdgeIterator, bool > insert(std::pair< EdgeIdentifier, EdgeAttribute > &&Val)
Inserts an edge into the graph with Identifier Val.first, and Attribute Val.second.
std::pair< EdgeIterator, bool > insert(const std::pair< EdgeIdentifier, EdgeAttribute > &Val)
Inserts an edge into the graph with Identifier Val.first, and Attribute Val.second.
EdgeAttribute & operator[](const EdgeIdentifier &I)
Looks up the edge with identifier I, if it does not exist it default constructs it,...
std::pair< VertexIterator, bool > insert(std::pair< VertexIdentifier, VertexAttribute > &&Val)
VertexView< false > vertices()
Returns a view object allowing iteration over the vertices of the graph.
NeighborEdgeIteratorT< false, true > OutEdgeIterator
An iterator type for iterating through the set of edges leaving a vertex.
InOutEdgeView< true, true > outEdges(const VertexIdentifier I) const
size_type count(const EdgeIdentifier &I) const
Looks for an edge with Identifier I, returns 1 if one exists and 0 otherwise.
void clear()
Empty the Graph.
EdgeView< true > edges() const
size_type count(const VertexIdentifier &I) const
Looks for a vertex with identifier I, returns 1 if one exists, and 0 otherwise.
NeighborEdgeIteratorT< true, false > ConstInEdgeIterator
A const iterator type for iterating through the set of edges entering a vertex.
EdgeView< false > edges()
Returns a view object allowing iteration over the edges of the graph.
NeighborEdgeIteratorT< true, true > ConstOutEdgeIterator
A const iterator type for iterating through the set of edges entering a vertex.
NeighborEdgeIteratorT< false, false > InEdgeIterator
An iterator type for iterating through the set of edges leaving a vertex.
typename VertexMapT::iterator VertexIterator
An iterator type for iterating through the whole vertex set of the graph.
InOutEdgeView< false, false > inEdges(const VertexIdentifier I)
Returns a view object allowing iteration over the edges which point to a vertex I.
typename EdgeMapT::const_iterator ConstEdgeIterator
A const iterator for iterating through the entire edge set of the graph.
std::pair< VertexIterator, bool > insert(const std::pair< VertexIdentifier, VertexAttribute > &Val)
Inserts a vertex into the graph with Identifier Val.first, and Attribute Val.second.
detail::DenseMapPair< VertexIdentifier, VertexAttribute > VertexValueType
This type is the value_type of all iterators which range over vertices, Determined by the Vertices De...
Expected< const VertexAttribute & > at(const VertexIdentifier &I) const
VI VertexIdentifier
These objects are used to name edges and vertices in the graph.
Expected< VertexAttribute & > at(const VertexIdentifier &I)
Looks up a vertex with Identifier I, or an error if it does not exist.
VertexAttribute & operator[](const VertexIdentifier &I)
Looks up the vertex with identifier I, if it does not exist it default constructs it.
VertexView< true > vertices() const
InOutEdgeView< true, false > inEdges(const VertexIdentifier I) const
typename VertexMapT::const_iterator ConstVertexIterator
A const iterator type for iterating through the whole vertex set of the graph.
typename EdgeMapT::iterator EdgeIterator
An iterator for iterating through the entire edge set of the graph.
std::pair< VI, VI > EdgeIdentifier
detail::DenseMapPair< EdgeIdentifier, EdgeAttribute > EdgeValueType
This type is the value_type of all iterators which range over edges, Determined by the Edges DenseMap...
Expected< const EdgeAttribute & > at(const EdgeIdentifier &I) const
Expected< EdgeAttribute & > at(const EdgeIdentifier &I)
Looks up an edge with Identifier I, or an error if it does not exist.
InOutEdgeView< false, true > outEdges(const VertexIdentifier I)
Returns a view object allowing iteration over the edges which start at a vertex I.
This is an optimization pass for GlobalISel generic memory operations.
Error make_error(ArgTs &&... Args)
Make a Error instance representing failure using the given error info type.