llvm::scc_iterator< GraphT, GT > Class Template Reference

Enumerate the SCCs of a directed graph in reverse topological order of the SCC DAG. More...

#include "llvm/ADT/SCCIterator.h"

Inheritance diagram for llvm::scc_iterator< GraphT, GT >:

Collaboration diagram for llvm::scc_iterator< GraphT, GT >:

Public Member Functions
bool	isAtEnd () const
	Direct loop termination test which is more efficient than comparison with end(). More...
bool	operator== (const scc_iterator &x) const
scc_iterator &	operator++ ()
reference	operator* () const
bool	hasCycle () const
	Test if the current SCC has a cycle. More...
void	ReplaceNode (NodeRef Old, NodeRef New)
	This informs the scc_iterator that the specified Old node has been deleted, and New is to be used in its place. More...
Public Member Functions inherited from llvm::iterator_facade_base< scc_iterator< GraphT, GraphTraits< GraphT > >, std::forward_iterator_tag, const std::vector< GraphTraits< GraphT > ::NodeRef >, ptrdiff_t >
scc_iterator< GraphT, GraphTraits< GraphT > >	operator+ (ptrdiff_t n) const
scc_iterator< GraphT, GraphTraits< GraphT > >	operator- (ptrdiff_t n) const
scc_iterator< GraphT, GraphTraits< GraphT > > &	operator++ ()
scc_iterator< GraphT, GraphTraits< GraphT > >	operator++ (int)
scc_iterator< GraphT, GraphTraits< GraphT > > &	operator-- ()
scc_iterator< GraphT, GraphTraits< GraphT > >	operator-- (int)
bool	operator!= (const scc_iterator< GraphT, GraphTraits< GraphT > > &RHS) const
bool	operator> (const scc_iterator< GraphT, GraphTraits< GraphT > > &RHS) const
bool	operator<= (const scc_iterator< GraphT, GraphTraits< GraphT > > &RHS) const
bool	operator>= (const scc_iterator< GraphT, GraphTraits< GraphT > > &RHS) const
PointerProxy	operator-> () const
ReferenceProxy	operator[] (ptrdiff_t n) const

Static Public Member Functions
static scc_iterator	begin (const GraphT &G)
static scc_iterator	end (const GraphT &)

Additional Inherited Members
Public Types inherited from llvm::iterator_facade_base< scc_iterator< GraphT, GraphTraits< GraphT > >, std::forward_iterator_tag, const std::vector< GraphTraits< GraphT > ::NodeRef >, ptrdiff_t >
using	iterator_category = std::forward_iterator_tag
using	value_type = const std::vector< GraphTraits< GraphT > ::NodeRef >
using	difference_type = ptrdiff_t
using	pointer = const std::vector< GraphTraits< GraphT > ::NodeRef > *
using	reference = const std::vector< GraphTraits< GraphT > ::NodeRef > &
Protected Types inherited from llvm::iterator_facade_base< scc_iterator< GraphT, GraphTraits< GraphT > >, std::forward_iterator_tag, const std::vector< GraphTraits< GraphT > ::NodeRef >, ptrdiff_t >
enum

Detailed Description

template<class GraphT, class GT = GraphTraits<GraphT>>
class llvm::scc_iterator< GraphT, GT >

Enumerate the SCCs of a directed graph in reverse topological order of the SCC DAG.

This is implemented using Tarjan's DFS algorithm using an internal stack to build up a vector of nodes in a particular SCC. Note that it is a forward iterator and thus you cannot backtrack or re-visit nodes.

Definition at line 46 of file SCCIterator.h.

Member Function Documentation

begin()

template<class GraphT , class GT = GraphTraits<GraphT>>

static scc_iterator llvm::scc_iterator< GraphT, GT >::begin ( const GraphT &  G )

inlinestatic

Definition at line 105 of file SCCIterator.h.

References G.

Referenced by llvm::scc_begin().

end()

template<class GraphT , class GT = GraphTraits<GraphT>>

static scc_iterator llvm::scc_iterator< GraphT, GT >::end ( const GraphT &  )

inlinestatic

Definition at line 108 of file SCCIterator.h.

Referenced by llvm::scc_end().

hasCycle()

template<class GraphT , class GT >

bool llvm::scc_iterator< GraphT, GT >::hasCycle

Test if the current SCC has a cycle.

If the SCC has more than one node, this is trivially true. If not, it may still contain a cycle if the node has an edge back to itself.

Definition at line 219 of file SCCIterator.h.

References assert(), and N.

isAtEnd()

template<class GraphT , class GT = GraphTraits<GraphT>>

bool llvm::scc_iterator< GraphT, GT >::isAtEnd ( ) const

inline

Direct loop termination test which is more efficient than comparison with end().

Definition at line 112 of file SCCIterator.h.

References assert().

operator*()

template<class GraphT , class GT = GraphTraits<GraphT>>

reference llvm::scc_iterator< GraphT, GT >::operator* ( ) const

inline

Definition at line 126 of file SCCIterator.h.

References assert().

operator++()

template<class GraphT , class GT = GraphTraits<GraphT>>

scc_iterator& llvm::scc_iterator< GraphT, GT >::operator++ ( )

inline

Definition at line 121 of file SCCIterator.h.

operator==()

template<class GraphT , class GT = GraphTraits<GraphT>>

bool llvm::scc_iterator< GraphT, GT >::operator== ( const scc_iterator< GraphT, GT > &  x ) const

inline

Definition at line 117 of file SCCIterator.h.

References x.

ReplaceNode()

template<class GraphT , class GT = GraphTraits<GraphT>>

void llvm::scc_iterator< GraphT, GT >::ReplaceNode ( NodeRef  Old, NodeRef  New  )

inline

This informs the scc_iterator that the specified Old node has been deleted, and New is to be used in its place.

Definition at line 139 of file SCCIterator.h.

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

Referenced by llvm::CallGraphSCC::ReplaceNode().

---

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

• include/llvm/ADT/SCCIterator.h