#include <SCC.h>

Classes
class	GNodeSCCInfo

Public Types
typedef std::stack< NodeID >	GNodeStack

typedef Map< NodeID, GNodeSCCInfo >	GNODESCCInfoMap

typedef Map< NodeID, NodeID >	NodeToNodeMap

Public Member Functions
	SCCDetection (const GraphType &GT)

GNodeStack &	topoNodeStack ()

const GNodeStack &	topoNodeStack () const

FIFOWorkList< NodeID >	revTopoNodeStack () const

const GNODESCCInfoMap &	GNodeSCCInfo () const

NodeID	repNode (NodeID n) const
	get the rep node if not found return itself

bool	isInCycle (NodeID n) const
	whether the node is in a cycle

const NodeBS &	subNodes (NodeID n) const
	get all subnodes in one scc, if size is empty insert itself into the set

const NodeBS &	getRepNodes () const
	get all repNodeID

const GraphType &	graph ()

void	find (void)

void	find (NodeSet &candidates)

Private Types
typedef SVF::GenericGraphTraits< GraphType >	GTraits
	Define the GTraits and node iterator for printing.

typedef GTraits::NodeRef	GNODE

typedef GTraits::nodes_iterator	node_iterator

typedef GTraits::ChildIteratorType	child_iterator

typedef unsigned	NodeID

Private Member Functions
bool	visited (NodeID n)

bool	inSCC (NodeID n)

void	setVisited (NodeID n, bool v)

void	setInSCC (NodeID n, bool v)

void	rep (NodeID n, NodeID r)

NodeID	rep (NodeID n)

bool	isInSCC (NodeID n)

GNODE	Node (NodeID id) const

NodeID	Node_Index (GNODE node) const

void	visit (NodeID v)

void	clear ()

Private Attributes
GNODESCCInfoMap	_NodeSCCAuxInfo

const GraphType &	_graph

NodeID	_I

NodeToNodeMap	_D

GNodeStack	_SS

GNodeStack	_T

NodeBS	repNodes

Detailed Description

template<class GraphType>
class SVF::SCCDetection< GraphType >

Definition at line 55 of file SCC.h.

Member Typedef Documentation

◆ child_iterator

template<class GraphType >

typedef GTraits::ChildIteratorType SVF::SCCDetection< GraphType >::child_iterator

private

Definition at line 63 of file SCC.h.

◆ GNODE

template<class GraphType >

typedef GTraits::NodeRef SVF::SCCDetection< GraphType >::GNODE

private

Definition at line 61 of file SCC.h.

◆ GNODESCCInfoMap

template<class GraphType >

typedef Map<NodeID,GNodeSCCInfo > SVF::SCCDetection< GraphType >::GNODESCCInfoMap

Definition at line 117 of file SCC.h.

◆ GNodeStack

template<class GraphType >

typedef std::stack<NodeID> SVF::SCCDetection< GraphType >::GNodeStack

Definition at line 67 of file SCC.h.

◆ GTraits

template<class GraphType >

typedef SVF::GenericGraphTraits<GraphType> SVF::SCCDetection< GraphType >::GTraits

private

Define the GTraits and node iterator for printing.

Definition at line 60 of file SCC.h.

◆ node_iterator

template<class GraphType >

typedef GTraits::nodes_iterator SVF::SCCDetection< GraphType >::node_iterator

private

Definition at line 62 of file SCC.h.

◆ NodeID

template<class GraphType >

typedef unsigned SVF::SCCDetection< GraphType >::NodeID

private

Definition at line 64 of file SCC.h.

◆ NodeToNodeMap

template<class GraphType >

typedef Map<NodeID, NodeID> SVF::SCCDetection< GraphType >::NodeToNodeMap

Definition at line 118 of file SCC.h.

Constructor & Destructor Documentation

◆ SCCDetection()

template<class GraphType >

SVF::SCCDetection< GraphType >::SCCDetection ( const GraphType & GT )

inline

Definition at line 120 of file SCC.h.

        : _graph(GT),
          _I(0)
    {}

Member Function Documentation

◆ clear()

template<class GraphType >

void SVF::SCCDetection< GraphType >::clear ( )

inlineprivate

Definition at line 317 of file SCC.h.

    {
        _NodeSCCAuxInfo.clear();
        _I = 0;
        _D.clear();
        repNodes.clear();
        while(!_SS.empty())
            _SS.pop();
        while(!_T.empty())
            _T.pop();
    }

◆ find() [1/2]

template<class GraphType >

void SVF::SCCDetection< GraphType >::find ( NodeSet & candidates )

inline

Definition at line 356 of file SCC.h.

    {
        // This function is reloaded to only visit candidate NODES
        clear();
        for (NodeID node : candidates)
        {
            if (!this->visited(node))
            {
                if (this->rep(node) == UINT_MAX || this->rep(node) == node)
                    visit(node);
                else
                    this->visited(node);
            }
        }
    }

◆ find() [2/2]

template<class GraphType >

void SVF::SCCDetection< GraphType >::find ( void )

inline

Definition at line 330 of file SCC.h.

    {
        // Visit each unvisited root node.   A root node is defined
        // to be a node that has no incoming copy/skew edges
        clear();
        node_iterator I = GTraits::nodes_begin(_graph);
        node_iterator E = GTraits::nodes_end(_graph);
        for (; I != E; ++I)
        {
            NodeID node = Node_Index(*I);
            if (!this->visited(node))
            {
                // We skip any nodes that have a representative other than
                // themselves.  Such nodes occur as a result of merging
                // nodes either through unifying an ACC or other node
                // merging optimizations.  Any such node should have no
                // outgoing edges and therefore should no longer be a member
                // of an SCC.
                if (this->rep(node) == UINT_MAX || this->rep(node) == node)
                    visit(node);
                else
                    this->visited(node);
            }
        }
    }

◆ getRepNodes()

template<class GraphType >

const NodeBS & SVF::SCCDetection< GraphType >::getRepNodes ( ) const

inline

get all repNodeID

Definition at line 203 of file SCC.h.

    {
        return repNodes;
    }

◆ GNodeSCCInfo()

template<class GraphType >

const GNODESCCInfoMap & SVF::SCCDetection< GraphType >::GNodeSCCInfo ( ) const

inline

Definition at line 155 of file SCC.h.

    {
        return _NodeSCCAuxInfo;
    }

◆ graph()

template<class GraphType >

const GraphType & SVF::SCCDetection< GraphType >::graph ( )

inline

Definition at line 208 of file SCC.h.

    {
        return _graph;
    }

◆ inSCC()

template<class GraphType >

bool SVF::SCCDetection< GraphType >::inSCC ( NodeID n )

inlineprivate

Definition at line 227 of file SCC.h.

    {
        return _NodeSCCAuxInfo[n].inSCC();
    }

◆ isInCycle()

template<class GraphType >

bool SVF::SCCDetection< GraphType >::isInCycle ( NodeID n ) const

inline

whether the node is in a cycle

Definition at line 171 of file SCC.h.

    {
        NodeID rep = repNode(n);
        // multi-node cycle
        if (subNodes(rep).count() > 1)
        {
            return true;
        }
        // self-cycle
        else
        {
            child_iterator EI = GTraits::direct_child_begin(Node(rep));
            child_iterator EE = GTraits::direct_child_end(Node(rep));
            for (; EI != EE; ++EI)
            {
                NodeID w = Node_Index(*EI);
                if(w==rep)
                    return true;
            }
            return false;
        }
    }

◆ isInSCC()

template<class GraphType >

bool SVF::SCCDetection< GraphType >::isInSCC ( NodeID n )

inlineprivate

Definition at line 256 of file SCC.h.

    {
        return _NodeSCCAuxInfo[n].inSCC();
    }

◆ Node()

template<class GraphType >

GNODE SVF::SCCDetection< GraphType >::Node ( NodeID id ) const

inlineprivate

Definition at line 261 of file SCC.h.

    {
        return GTraits::getNode(_graph, id);
    }

◆ Node_Index()

template<class GraphType >

NodeID SVF::SCCDetection< GraphType >::Node_Index ( GNODE node ) const

inlineprivate

Definition at line 266 of file SCC.h.

    {
        return GTraits::getNodeID(node);
    }

◆ rep() [1/2]

template<class GraphType >

NodeID SVF::SCCDetection< GraphType >::rep ( NodeID n )

inlineprivate

Definition at line 252 of file SCC.h.

    {
        return _NodeSCCAuxInfo[n].rep();
    }

◆ rep() [2/2]

template<class GraphType >

void SVF::SCCDetection< GraphType >::rep	(	NodeID	n,
		NodeID	r
	)

inlineprivate

Definition at line 240 of file SCC.h.

    {
        _NodeSCCAuxInfo[n].rep(r);
        _NodeSCCAuxInfo[r].addSubNodes(n);
        if (n != r)
        {
            _NodeSCCAuxInfo[n].subNodes().clear();
            repNodes.reset(n);
            repNodes.set(r);
        }
    }

◆ repNode()

template<class GraphType >

NodeID SVF::SCCDetection< GraphType >::repNode ( NodeID n ) const

inline

get the rep node if not found return itself

Definition at line 161 of file SCC.h.

    {
        typename GNODESCCInfoMap::const_iterator it = _NodeSCCAuxInfo.find(n);
        assert(it!=_NodeSCCAuxInfo.end() && "scc rep not found");
        NodeID rep = it->second.rep();
        return rep!= UINT_MAX ? rep : n ;
    }

◆ revTopoNodeStack()

template<class GraphType >

FIFOWorkList< NodeID > SVF::SCCDetection< GraphType >::revTopoNodeStack ( ) const

inline

Return a handle to the stack of nodes in reverse topological order. This will be used to seed the initial solution and improve efficiency.

Definition at line 142 of file SCC.h.

    {
        FIFOWorkList<NodeID> revTopoOrder;
        GNodeStack topoOrder = topoNodeStack();
        while(!topoOrder.empty())
        {
            NodeID nodeID = topoOrder.top();
            topoOrder.pop();
            revTopoOrder.push(nodeID);
        }
        return revTopoOrder;
    }

◆ setInSCC()

template<class GraphType >

void SVF::SCCDetection< GraphType >::setInSCC	(	NodeID	n,
		bool	v
	)

inlineprivate

Definition at line 236 of file SCC.h.

    {
        _NodeSCCAuxInfo[n].inSCC(v);
    }

◆ setVisited()

template<class GraphType >

void SVF::SCCDetection< GraphType >::setVisited	(	NodeID	n,
		bool	v
	)

inlineprivate

Definition at line 232 of file SCC.h.

    {
        _NodeSCCAuxInfo[n].visited(v);
    }

◆ subNodes()

template<class GraphType >

const NodeBS & SVF::SCCDetection< GraphType >::subNodes ( NodeID n ) const

inline

get all subnodes in one scc, if size is empty insert itself into the set

Definition at line 195 of file SCC.h.

    {
        typename GNODESCCInfoMap::const_iterator it = _NodeSCCAuxInfo.find(n);
        assert(it!=_NodeSCCAuxInfo.end() && "scc rep not found");
        return it->second.subNodes();
    }

◆ topoNodeStack() [1/2]

template<class GraphType >

GNodeStack & SVF::SCCDetection< GraphType >::topoNodeStack ( )

inline

Definition at line 129 of file SCC.h.

    {
        return _T;
    }

◆ topoNodeStack() [2/2]

template<class GraphType >

const GNodeStack & SVF::SCCDetection< GraphType >::topoNodeStack ( ) const

inline

Definition at line 134 of file SCC.h.

    {
        return _T;
    }

◆ visit()

template<class GraphType >

void SVF::SCCDetection< GraphType >::visit ( NodeID v )

inlineprivate

Definition at line 271 of file SCC.h.

    {
        // SVFUtil::outs() << "visit GNODE: " << Node_Index(v)<< "\n";
        _I += 1;
        _D[v] = _I;
        this->rep(v,v);
        this->setVisited(v,true);
 
        child_iterator EI = GTraits::direct_child_begin(Node(v));
        child_iterator EE = GTraits::direct_child_end(Node(v));
 
        for (; EI != EE; ++EI)
        {
            NodeID w = Node_Index(*EI);
 
            if (!this->visited(w))
                visit(w);
            if (!this->inSCC(w))
            {
                NodeID rep;
                rep = _D[this->rep(v)] < _D[this->rep(w)] ?
                      this->rep(v) : this->rep(w);
                this->rep(v,rep);
            }
        }
        if (this->rep(v) == v)
        {
            this->setInSCC(v,true);
            while (!_SS.empty())
            {
                NodeID w = _SS.top();
                if (_D[w] <= _D[v])
                    break;
                else
                {
                    _SS.pop();
                    this->setInSCC(w,true);
                    this->rep(w,v);
                }
            }
            _T.push(v);
        }
        else
            _SS.push(v);
    }

◆ visited()

template<class GraphType >

bool SVF::SCCDetection< GraphType >::visited ( NodeID n )

inlineprivate

Definition at line 223 of file SCC.h.

    {
        return _NodeSCCAuxInfo[n].visited();
    }

Member Data Documentation

◆ _D

template<class GraphType >

NodeToNodeMap SVF::SCCDetection< GraphType >::_D

private

Definition at line 218 of file SCC.h.

◆ _graph

template<class GraphType >

const GraphType& SVF::SCCDetection< GraphType >::_graph

private

Definition at line 216 of file SCC.h.

◆ _I

template<class GraphType >

NodeID SVF::SCCDetection< GraphType >::_I

private

Definition at line 217 of file SCC.h.

◆ _NodeSCCAuxInfo

template<class GraphType >

GNODESCCInfoMap SVF::SCCDetection< GraphType >::_NodeSCCAuxInfo

private

Definition at line 214 of file SCC.h.

◆ _SS

template<class GraphType >

GNodeStack SVF::SCCDetection< GraphType >::_SS

private

Definition at line 219 of file SCC.h.

◆ _T

template<class GraphType >

GNodeStack SVF::SCCDetection< GraphType >::_T

private

Definition at line 220 of file SCC.h.

◆ repNodes

template<class GraphType >

NodeBS SVF::SCCDetection< GraphType >::repNodes

private

Definition at line 221 of file SCC.h.

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

/home/runner/work/SVF/SVF/svf/include/Graphs/SCC.h

Classes

Public Types

Public Member Functions

Private Types

Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ child_iterator

◆ GNODE

◆ GNODESCCInfoMap

◆ GNodeStack

◆ GTraits

◆ node_iterator

◆ NodeID

◆ NodeToNodeMap

Constructor & Destructor Documentation

◆ SCCDetection()

Member Function Documentation

◆ clear()

◆ find() [1/2]

◆ find() [2/2]

◆ getRepNodes()

◆ GNodeSCCInfo()

◆ graph()

◆ inSCC()

◆ isInCycle()

◆ isInSCC()

◆ Node()

◆ Node_Index()

◆ rep() [1/2]

◆ rep() [2/2]

◆ repNode()

◆ revTopoNodeStack()

◆ setInSCC()

◆ setVisited()

◆ subNodes()

◆ topoNodeStack() [1/2]

◆ topoNodeStack() [2/2]

◆ visit()

◆ visited()

Member Data Documentation

◆ _D

◆ _graph

◆ _I

◆ _NodeSCCAuxInfo

◆ _SS

◆ _T

◆ repNodes