A Graph object represents a Directed Graph and is used in XRay to compute and store function call graphs and associated statistical information. More...

#include "llvm/XRay/Graph.h"

Classes
class	EdgeView
	A class for ranging over all the edges in the graph. More...

class	InOutEdgeView
	A class for ranging over the incoming edges incident to a vertex. More...

class	VertexView
	A class for ranging over the vertices in the graph. More...

Public Types
typedef VI	VertexIdentifier
	These objects are used to name edges and vertices in the graph. More...

typedef std::pair< VI, VI >	EdgeIdentifier

using	VertexValueType = detail::DenseMapPair< VertexIdentifier, VertexAttribute >
	This type is the value_type of all iterators which range over vertices, Determined by the Vertices DenseMap. More...

using	EdgeValueType = detail::DenseMapPair< EdgeIdentifier, EdgeAttribute >
	This type is the value_type of all iterators which range over edges, Determined by the Edges DenseMap. More...

using	size_type = std::size_t

using	ConstInEdgeIterator = NeighborEdgeIteratorT< true, false >
	A const iterator type for iterating through the set of edges entering a vertex. More...

using	InEdgeIterator = NeighborEdgeIteratorT< false, false >
	An iterator type for iterating through the set of edges leaving a vertex. More...

using	ConstOutEdgeIterator = NeighborEdgeIteratorT< true, true >
	A const iterator type for iterating through the set of edges entering a vertex. More...

using	OutEdgeIterator = NeighborEdgeIteratorT< false, true >
	An iterator type for iterating through the set of edges leaving a vertex. More...

using	ConstVertexIterator = typename VertexMapT::const_iterator
	A const iterator type for iterating through the whole vertex set of the graph. More...

using	VertexIterator = typename VertexMapT::iterator
	An iterator type for iterating through the whole vertex set of the graph. More...

using	ConstEdgeIterator = typename EdgeMapT::const_iterator
	A const iterator for iterating through the entire edge set of the graph. More...

using	EdgeIterator = typename EdgeMapT::iterator
	An iterator for iterating through the entire edge set of the graph. More...

Public Member Functions
void	clear ()
	Empty the Graph. More...

VertexView< false >	vertices ()
	Returns a view object allowing iteration over the vertices of the graph. More...

VertexView< true >	vertices () const

EdgeView< false >	edges ()
	Returns a view object allowing iteration over the edges of the graph. More...

EdgeView< true >	edges () const

InOutEdgeView< false, true >	outEdges (const VertexIdentifier I)
	Returns a view object allowing iteration over the edges which start at a vertex I. More...

InOutEdgeView< true, true >	outEdges (const VertexIdentifier I) const

InOutEdgeView< false, false >	inEdges (const VertexIdentifier I)
	Returns a view object allowing iteration over the edges which point to a vertex I. More...

InOutEdgeView< true, false >	inEdges (const VertexIdentifier I) const

VertexAttribute &	operator[] (const VertexIdentifier &I)
	Looks up the vertex with identifier I, if it does not exist it default constructs it. More...

EdgeAttribute &	operator[] (const EdgeIdentifier &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. More...

Expected< VertexAttribute & >	at (const VertexIdentifier &I)
	Looks up a vertex with Identifier I, or an error if it does not exist. More...

Expected< const VertexAttribute & >	at (const VertexIdentifier &I) const

Expected< EdgeAttribute & >	at (const EdgeIdentifier &I)
	Looks up an edge with Identifier I, or an error if it does not exist. More...

Expected< const EdgeAttribute & >	at (const EdgeIdentifier &I) const

size_type	count (const VertexIdentifier &I) const
	Looks for a vertex with identifier I, returns 1 if one exists, and 0 otherwise. More...

size_type	count (const EdgeIdentifier &I) const
	Looks for an edge with Identifier I, returns 1 if one exists and 0 otherwise. More...

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. More...

std::pair< VertexIterator, bool >	insert (std::pair< VertexIdentifier, VertexAttribute > &&Val)

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. More...

std::pair< EdgeIterator, bool >	insert (std::pair< EdgeIdentifier, EdgeAttribute > &&Val)
	Inserts an edge into the graph with Identifier Val.first, and Attribute Val.second. More...

Detailed Description

template<typename VertexAttribute, typename EdgeAttribute, typename VI = int32_t>
class llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >

A Graph object represents a Directed Graph and is used in XRay to compute and store function call graphs and associated statistical information.

The graph takes in four template parameters, these are:

VertexAttribute, this is a structure which is stored for each vertex. Must be DefaultConstructible, CopyConstructible, CopyAssignable and Destructible.
EdgeAttribute, this is a structure which is stored for each edge Must be DefaultConstructible, CopyConstructible, CopyAssignable and Destructible.
EdgeAttribute, this is a structure which is stored for each variable
VI, this is a type over which DenseMapInfo is defined and is the type used look up strings, available as VertexIdentifier.
If the built in DenseMapInfo is not defined, provide a specialization class type here.

Graph is CopyConstructible, CopyAssignable, MoveConstructible and MoveAssignable but is not EqualityComparible or LessThanComparible.

Usage Example Graph with weighted edges and vertices: Graph<int, int, int> G;

G[1] = 0; G[2] = 2; G[{1,2}] = 1; G[{2,1}] = -1; for(const auto &v : G.vertices()){ // Do something with the vertices in the graph; } for(const auto &e : G.edges()){ // Do something with the edges in the graph; }

Usage Example with StrRef keys. Graph<int, double, StrRef> StrG; char va[] = "Vertex A"; char vaa[] = "Vertex A"; char vb[] = "Vertex B"; // Vertices are referenced by String Refs. G[va] = 0; G[vb] = 1; G[{va, vb}] = 1.0; cout() << G[vaa] << " " << G[{vaa, vb}]; //prints "0 1.0".

Definition at line 75 of file Graph.h.

Member Typedef Documentation

◆ ConstEdgeIterator

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>

using llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::ConstEdgeIterator = typename EdgeMapT::const_iterator

A const iterator for iterating through the entire edge set of the graph.

Has a const EdgeValueType as its value_type

Definition at line 299 of file Graph.h.

◆ ConstInEdgeIterator

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>

using llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::ConstInEdgeIterator = NeighborEdgeIteratorT<true, false>

A const iterator type for iterating through the set of edges entering a vertex.

Has a const EdgeValueType as its value_type

Definition at line 176 of file Graph.h.

◆ ConstOutEdgeIterator

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>

using llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::ConstOutEdgeIterator = NeighborEdgeIteratorT<true, true>

A const iterator type for iterating through the set of edges entering a vertex.

Has a const EdgeValueType as its value_type

Definition at line 187 of file Graph.h.

◆ ConstVertexIterator

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>

using llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::ConstVertexIterator = typename VertexMapT::const_iterator

A const iterator type for iterating through the whole vertex set of the graph.

Has a const VertexValueType as its value_type

Definition at line 262 of file Graph.h.

◆ EdgeIdentifier

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>

typedef std::pair<VI, VI> llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::EdgeIdentifier

Definition at line 79 of file Graph.h.

◆ EdgeIterator

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>

using llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::EdgeIterator = typename EdgeMapT::iterator

An iterator for iterating through the entire edge set of the graph.

Has an EdgeValueType as its value_type

Definition at line 304 of file Graph.h.

◆ EdgeValueType

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>

using llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::EdgeValueType = detail::DenseMapPair<EdgeIdentifier, EdgeAttribute>

This type is the value_type of all iterators which range over edges, Determined by the Edges DenseMap.

Definition at line 88 of file Graph.h.

◆ InEdgeIterator

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>

using llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::InEdgeIterator = NeighborEdgeIteratorT<false, false>

An iterator type for iterating through the set of edges leaving a vertex.

Has an EdgeValueType as its value_type

Definition at line 181 of file Graph.h.

◆ OutEdgeIterator

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>

using llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::OutEdgeIterator = NeighborEdgeIteratorT<false, true>

An iterator type for iterating through the set of edges leaving a vertex.

Has an EdgeValueType as its value_type

Definition at line 192 of file Graph.h.

◆ size_type

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>

using llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::size_type = std::size_t

Definition at line 90 of file Graph.h.

◆ VertexIdentifier

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>

typedef VI llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::VertexIdentifier

These objects are used to name edges and vertices in the graph.

Definition at line 78 of file Graph.h.

◆ VertexIterator

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>

using llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::VertexIterator = typename VertexMapT::iterator

An iterator type for iterating through the whole vertex set of the graph.

Has a VertexValueType as its value_type

Definition at line 267 of file Graph.h.

◆ VertexValueType

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>

using llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::VertexValueType = detail::DenseMapPair<VertexIdentifier, VertexAttribute>

This type is the value_type of all iterators which range over vertices, Determined by the Vertices DenseMap.

Definition at line 84 of file Graph.h.

Member Function Documentation

◆ at() [1/4]

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>

Expected<VertexAttribute &> llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::at ( const VertexIdentifier & I )

inline

Looks up a vertex with Identifier I, or an error if it does not exist.

Definition at line 399 of file Graph.h.

References llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find(), and llvm::make_error_code().

◆ at() [2/4]

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>

Expected<const VertexAttribute &> llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::at ( const VertexIdentifier & I ) const

inline

Definition at line 408 of file Graph.h.

References llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find(), and llvm::make_error_code().

◆ at() [3/4]

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>

Expected<EdgeAttribute &> llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::at ( const EdgeIdentifier & I )

inline

Looks up an edge with Identifier I, or an error if it does not exist.

Definition at line 418 of file Graph.h.

References llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find(), and llvm::make_error_code().

◆ at() [4/4]

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>

Expected<const EdgeAttribute &> llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::at ( const EdgeIdentifier & I ) const

inline

Definition at line 427 of file Graph.h.

References llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find(), and llvm::make_error_code().

◆ clear()

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>

void llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::clear ( )

inline

Empty the Graph.

Definition at line 341 of file Graph.h.

References llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::clear().

◆ count() [1/2]

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>

size_type llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::count ( const VertexIdentifier & I ) const

inline

Looks for a vertex with identifier I, returns 1 if one exists, and 0 otherwise.

Definition at line 438 of file Graph.h.

References llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::count().

◆ count() [2/2]

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>

size_type llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::count ( const EdgeIdentifier & I ) const

inline

Looks for an edge with Identifier I, returns 1 if one exists and 0 otherwise.

Definition at line 444 of file Graph.h.

References llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::count().

◆ edges() [1/2]

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>

EdgeView<false> llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::edges ( )

inline

Returns a view object allowing iteration over the edges of the graph.

also allows access to the size of the edge set.

Definition at line 356 of file Graph.h.

◆ edges() [2/2]

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>

EdgeView<true> llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::edges ( ) const

inline

Definition at line 358 of file Graph.h.

◆ inEdges() [1/2]

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>

InOutEdgeView<false, false> llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::inEdges ( const VertexIdentifier I )

inline

Returns a view object allowing iteration over the edges which point to a vertex I.

Definition at line 372 of file Graph.h.

References I.

◆ inEdges() [2/2]

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>

InOutEdgeView<true, false> llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::inEdges ( const VertexIdentifier I ) const

inline

Definition at line 376 of file Graph.h.

References I.

◆ insert() [1/4]

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>

std::pair<VertexIterator, bool> llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::insert ( const std::pair< VertexIdentifier, VertexAttribute > & Val )

inline

Inserts a vertex into the graph with Identifier Val.first, and Attribute Val.second.

Definition at line 449 of file Graph.h.

References llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::insert().

◆ insert() [2/4]

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>

std::pair<VertexIterator, bool> llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::insert ( std::pair< VertexIdentifier, VertexAttribute > && Val )

inline

Definition at line 454 of file Graph.h.

References llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::insert().

◆ insert() [3/4]

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>

std::pair<EdgeIterator, bool> llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::insert ( const std::pair< EdgeIdentifier, EdgeAttribute > & Val )

inline

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.

Definition at line 462 of file Graph.h.

References llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::FindAndConstruct(), and llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::insert().

◆ insert() [4/4]

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>

std::pair<EdgeIterator, bool> llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::insert ( std::pair< EdgeIdentifier, EdgeAttribute > && Val )

inline

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.

Definition at line 479 of file Graph.h.

References llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::FindAndConstruct(), and llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::insert().

◆ operator[]() [1/2]

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>

VertexAttribute& llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::operator[] ( const VertexIdentifier & I )

inline

Looks up the vertex with identifier I, if it does not exist it default constructs it.

Definition at line 382 of file Graph.h.

References llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::FindAndConstruct().

◆ operator[]() [2/2]

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>

EdgeAttribute& llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::operator[] ( const EdgeIdentifier & I )

inline

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.

Definition at line 389 of file Graph.h.

References llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::FindAndConstruct(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::insert(), and P.

◆ outEdges() [1/2]

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>

InOutEdgeView<false, true> llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::outEdges ( const VertexIdentifier I )

inline

Returns a view object allowing iteration over the edges which start at a vertex I.

Definition at line 362 of file Graph.h.

References I.

◆ outEdges() [2/2]

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>

InOutEdgeView<true, true> llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::outEdges ( const VertexIdentifier I ) const

inline

Definition at line 366 of file Graph.h.

References I.

◆ vertices() [1/2]

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>

VertexView<false> llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::vertices ( )

inline

Returns a view object allowing iteration over the vertices of the graph.

also allows access to the size of the vertex set.

Definition at line 350 of file Graph.h.

◆ vertices() [2/2]

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>

VertexView<true> llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::vertices ( ) const

inline

Definition at line 352 of file Graph.h.

The documentation for this class was generated from the following file:

include/llvm/XRay/Graph.h

Classes

Public Types

Public Member Functions

Detailed Description

template<typename VertexAttribute, typename EdgeAttribute, typename VI = int32_t> class llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >

Member Typedef Documentation

◆ ConstEdgeIterator

◆ ConstInEdgeIterator

◆ ConstOutEdgeIterator

◆ ConstVertexIterator

◆ EdgeIdentifier

◆ EdgeIterator

◆ EdgeValueType

◆ InEdgeIterator

◆ OutEdgeIterator

◆ size_type

◆ VertexIdentifier

◆ VertexIterator

◆ VertexValueType

Member Function Documentation

◆ at() [1/4]

◆ at() [2/4]

◆ at() [3/4]

◆ at() [4/4]

◆ clear()

◆ count() [1/2]

◆ count() [2/2]

◆ edges() [1/2]

◆ edges() [2/2]

◆ inEdges() [1/2]

◆ inEdges() [2/2]

◆ insert() [1/4]

◆ insert() [2/4]

◆ insert() [3/4]

◆ insert() [4/4]

◆ operator[]() [1/2]

◆ operator[]() [2/2]

◆ outEdges() [1/2]

◆ outEdges() [2/2]

◆ vertices() [1/2]

◆ vertices() [2/2]

template<typename VertexAttribute, typename EdgeAttribute, typename VI = int32_t>
class llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >