LLVM 17.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().
 
bool operator== (const scc_iterator &x) const
 
scc_iteratoroperator++ ()
 
reference operator* () const
 
bool hasCycle () const
 Test if the current SCC has a cycle.
 
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.
 
- Public Member Functions inherited from llvm::iterator_facade_base< DerivedT, IteratorCategoryT, T, DifferenceTypeT, PointerT, ReferenceT >
DerivedT operator+ (DifferenceTypeT n) const
 
DerivedT operator- (DifferenceTypeT n) const
 
DerivedT & operator++ ()
 
DerivedT operator++ (int)
 
DerivedT & operator-- ()
 
DerivedT operator-- (int)
 
bool operator!= (const DerivedT &RHS) const
 
bool operator> (const DerivedT &RHS) const
 
bool operator<= (const DerivedT &RHS) const
 
bool operator>= (const DerivedT &RHS) const
 
PointerProxy operator-> () const
 
ReferenceProxy operator[] (DifferenceTypeT 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< DerivedT, IteratorCategoryT, T, DifferenceTypeT, PointerT, ReferenceT >
using iterator_category = IteratorCategoryT
 
using value_type = T
 
using difference_type = DifferenceTypeT
 
using pointer = PointerT
 
using reference = ReferenceT
 
- Protected Types inherited from llvm::iterator_facade_base< DerivedT, IteratorCategoryT, T, DifferenceTypeT, PointerT, ReferenceT >
enum  { IsRandomAccess , IsBidirectional }
 

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.

◆ 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: