LLVM API Documentation

Classes | Public Member Functions | Static Public Member Functions
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 <SCCIterator.h>

Inheritance diagram for llvm::scc_iterator< GraphT, GT >:
Inheritance graph
[legend]
Collaboration diagram for llvm::scc_iterator< GraphT, GT >:
Collaboration graph
[legend]

List of all members.

Classes

struct  StackElement
 Element of VisitStack during DFS.

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 hasLoop () const
 Test if the current SCC has a loop.
void ReplaceNode (NodeType *Old, NodeType *New)

Static Public Member Functions

static scc_iterator begin (const GraphT &G)
static scc_iterator end (const GraphT &)

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


Member Function Documentation

template<class GraphT, class GT = GraphTraits<GraphT>>
static scc_iterator llvm::scc_iterator< GraphT, GT >::begin ( const GraphT &  G) [inline, static]

Definition at line 100 of file SCCIterator.h.

Referenced by llvm::scc_begin().

template<class GraphT, class GT = GraphTraits<GraphT>>
static scc_iterator llvm::scc_iterator< GraphT, GT >::end ( const GraphT &  ) [inline, static]

Definition at line 103 of file SCCIterator.h.

Referenced by llvm::scc_end().

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

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

template<class GraphT, class GT = GraphTraits<GraphT>>
reference llvm::scc_iterator< GraphT, GT >::operator* ( ) const [inline]

Definition at line 121 of file SCCIterator.h.

template<class GraphT, class GT = GraphTraits<GraphT>>
scc_iterator& llvm::scc_iterator< GraphT, GT >::operator++ ( ) [inline]
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 112 of file SCCIterator.h.

template<class GraphT, class GT = GraphTraits<GraphT>>
void llvm::scc_iterator< GraphT, GT >::ReplaceNode ( NodeType *  Old,
NodeType *  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 134 of file SCCIterator.h.

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

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


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