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	hasLoop () const
	Test if the current SCC has a loop. 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, GT >, std::forward_iterator_tag, const std::vector< GT::NodeRef >, ptrdiff_t >
scc_iterator< GraphT, GT >	operator+ (ptrdiff_t n) const
scc_iterator< GraphT, GT >	operator- (ptrdiff_t n) const
scc_iterator< GraphT, GT > &	operator++ ()
scc_iterator< GraphT, GT >	operator++ (int)
scc_iterator< GraphT, GT > &	operator-- ()
scc_iterator< GraphT, GT >	operator-- (int)
bool	operator!= (const scc_iterator< GraphT, GT > &RHS) const
bool	operator> (const scc_iterator< GraphT, GT > &RHS) const
bool	operator<= (const scc_iterator< GraphT, GT > &RHS) const
bool	operator>= (const scc_iterator< GraphT, GT > &RHS) const
const std::vector< GT::NodeRef > *	operator-> ()
const std::vector< GT::NodeRef > *	operator-> () const
ReferenceProxy	operator[] (ptrdiff_t n)
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
Protected Types inherited from llvm::iterator_facade_base< scc_iterator< GraphT, GT >, std::forward_iterator_tag, const std::vector< GT::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 43 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 102 of file SCCIterator.h.

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 105 of file SCCIterator.h.

Referenced by llvm::scc_end().

hasLoop()

template<class GraphT , class GT >

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

(

)

const

Test if the current SCC has a loop.

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

Definition at line 213 of file SCCIterator.h.

References assert().

Referenced by llvm::scc_iterator< GraphT, GT >::operator*().

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 109 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 123 of file SCCIterator.h.

References assert(), and llvm::scc_iterator< GraphT, GT >::hasLoop().

operator++()

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

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

inline

Definition at line 118 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 114 of file SCCIterator.h.

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 136 of file SCCIterator.h.

References assert(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::count(), llvm::dbgs(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::erase(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find(), and N.

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

---

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

• include/llvm/ADT/SCCIterator.h