LLVM  14.0.0git
Classes | Public Member Functions | Static Public Member Functions | List of all members
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 >:
Inheritance graph
[legend]
Collaboration diagram for llvm::scc_iterator< GraphT, GT >:
Collaboration graph
[legend]

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_iteratoroperator++ ()
 
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
 
const std::vector< GraphTraits< GraphT > ::NodeRef > * operator-> ()
 
const std::vector< GraphTraits< GraphT > ::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

- 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 42 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 101 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 104 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 215 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 108 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 122 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 117 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 113 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 135 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: