#include <WPASolver.h>

Inheritance diagram for SVF::WPASolver< GraphType >:

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

typedef GTraits::NodeRef	GNODE

typedef GTraits::EdgeType	GEDGE

typedef GTraits::ChildIteratorType	child_iterator

typedef SCCDetection< GraphType >	SCC

typedef FIFOWorkList< NodeID >	WorkList

Public Attributes
u32_t	numOfIteration
	num of iterations during constraint solving

Protected Member Functions
	WPASolver ()
	Constructor.

virtual	~WPASolver ()=default
	Destructor.

SCC *	getSCCDetector () const
	Get SCC detector.

const GraphType	graph ()
	Get/Set graph methods.

void	setGraph (GraphType g)

virtual NodeStack &	SCCDetect ()
	SCC detection.

virtual NodeStack &	SCCDetect (NodeSet &candidates)

virtual void	initWorklist ()

virtual void	solveWorklist ()

virtual void	processNode (NodeID)
	Following methods are to be implemented in child class, in order to achieve a fully worked PTA.

virtual void	collapseFields ()
	collapse positive weight cycles of a graph

virtual void	propagate (GNODE *v)

virtual bool	propFromSrcToDst (GEDGE *)
	Propagate information from source to destination node, to be implemented in the child class.

virtual NodeID	sccRepNode (NodeID id) const

NodeID	popFromWorklist ()
	Worklist operations.

virtual void	pushIntoWorklist (NodeID id)

bool	isWorklistEmpty ()

bool	isInWorklist (NodeID id)

GNODE *	Node (NodeID id)
	Get node on the graph.

NodeID	Node_Index (GNODE node)
	Get node ID.

Protected Attributes
bool	reanalyze
	Reanalyze if any constraint value changed.

u32_t	iterationForPrintStat
	print out statistics for i-th iteration

GraphType	_graph
	Graph.

std::unique_ptr< SCC >	scc
	SCC.

WorkList	worklist
	Worklist for resolution.

Detailed Description

template<class GraphType>
class SVF::WPASolver< GraphType >

Definition at line 44 of file WPASolver.h.

Member Typedef Documentation

◆ child_iterator

template<class GraphType >

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

Definition at line 52 of file WPASolver.h.

◆ GEDGE

template<class GraphType >

typedef GTraits::EdgeType SVF::WPASolver< GraphType >::GEDGE

Definition at line 51 of file WPASolver.h.

◆ GNODE

template<class GraphType >

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

Definition at line 50 of file WPASolver.h.

◆ GTraits

template<class GraphType >

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

Define the GTraits and node iterator for printing.

Definition at line 49 of file WPASolver.h.

◆ SCC

template<class GraphType >

typedef SCCDetection<GraphType> SVF::WPASolver< GraphType >::SCC

Definition at line 54 of file WPASolver.h.

◆ WorkList

template<class GraphType >

typedef FIFOWorkList<NodeID> SVF::WPASolver< GraphType >::WorkList

Definition at line 56 of file WPASolver.h.

Constructor & Destructor Documentation

◆ WPASolver()

template<class GraphType >

SVF::WPASolver< GraphType >::WPASolver ( )

inlineprotected

Constructor.

Definition at line 61 of file WPASolver.h.

               : reanalyze(false), iterationForPrintStat(1000), _graph(nullptr), numOfIteration(0)
    {
    }

◆ ~WPASolver()

template<class GraphType >

virtual SVF::WPASolver< GraphType >::~WPASolver ( )

protectedvirtualdefault

Destructor.

Member Function Documentation

◆ collapseFields()

template<class GraphType >

virtual void SVF::WPASolver< GraphType >::collapseFields ( )

inlineprotectedvirtual

collapse positive weight cycles of a graph

Reimplemented in SVF::Andersen.

Definition at line 125 of file WPASolver.h.

125{}

◆ getSCCDetector()

template<class GraphType >

SCC * SVF::WPASolver< GraphType >::getSCCDetector ( ) const

inlineprotected

Get SCC detector.

Definition at line 68 of file WPASolver.h.

    {
        return scc.get();
    }

◆ graph()

template<class GraphType >

const GraphType SVF::WPASolver< GraphType >::graph ( )

inlineprotected

Get/Set graph methods.

Definition at line 75 of file WPASolver.h.

    {
        return _graph;
    }

◆ initWorklist()

template<class GraphType >

virtual void SVF::WPASolver< GraphType >::initWorklist ( )

inlineprotectedvirtual

Reimplemented in SVF::Andersen.

Definition at line 98 of file WPASolver.h.

    {
        NodeStack& nodeStack = SCCDetect();
        while (!nodeStack.empty())
        {
            NodeID nodeId = nodeStack.top();
            nodeStack.pop();
            pushIntoWorklist(nodeId);
        }
    }

◆ isInWorklist()

template<class GraphType >

bool SVF::WPASolver< GraphType >::isInWorklist ( NodeID id )

inlineprotected

Definition at line 165 of file WPASolver.h.

    {
        return worklist.find(id);
    }

◆ isWorklistEmpty()

template<class GraphType >

bool SVF::WPASolver< GraphType >::isWorklistEmpty ( )

inlineprotected

Definition at line 161 of file WPASolver.h.

    {
        return worklist.empty();
    }

◆ Node()

template<class GraphType >

GNODE * SVF::WPASolver< GraphType >::Node ( NodeID id )

inlineprotected

Get node on the graph.

Definition at line 178 of file WPASolver.h.

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

◆ Node_Index()

template<class GraphType >

NodeID SVF::WPASolver< GraphType >::Node_Index ( GNODE node )

inlineprotected

Get node ID.

Definition at line 184 of file WPASolver.h.

    {
        return GTraits::getNodeID(node);
    }

◆ popFromWorklist()

template<class GraphType >

NodeID SVF::WPASolver< GraphType >::popFromWorklist ( )

inlineprotected

Worklist operations.

Definition at line 152 of file WPASolver.h.

    {
        return sccRepNode(worklist.pop());
    }

◆ processNode()

template<class GraphType >

virtual void SVF::WPASolver< GraphType >::processNode ( NodeID )

inlineprotectedvirtual

Following methods are to be implemented in child class, in order to achieve a fully worked PTA.

Process each node on the graph, to be implemented in the child class

Reimplemented in SVF::VersionedFlowSensitive, SVF::Andersen, SVF::AndersenWaveDiff, SVF::FSMPTA< SVFGGraph >, and SVF::FlowSensitive.

Definition at line 123 of file WPASolver.h.

123{}

◆ propagate()

template<class GraphType >

virtual void SVF::WPASolver< GraphType >::propagate ( GNODE * v )

inlineprotectedvirtual

dump statistics Propagation for the solving, to be implemented in the child class

Reimplemented in SVF::WPASCCSolver< GraphType >.

Definition at line 128 of file WPASolver.h.

    {
        child_iterator EI = GTraits::direct_child_begin(*v);
        child_iterator EE = GTraits::direct_child_end(*v);
        for (; EI != EE; ++EI)
        {
            if (propFromSrcToDst(*(EI.getCurrent())))
                pushIntoWorklist(Node_Index(*EI));
        }
    }

◆ propFromSrcToDst()

template<class GraphType >

virtual bool SVF::WPASolver< GraphType >::propFromSrcToDst ( GEDGE * )

inlineprotectedvirtual

Propagate information from source to destination node, to be implemented in the child class.

Definition at line 139 of file WPASolver.h.

    {
        return false;
    }

◆ pushIntoWorklist()

template<class GraphType >

virtual void SVF::WPASolver< GraphType >::pushIntoWorklist ( NodeID id )

inlineprotectedvirtual

Definition at line 157 of file WPASolver.h.

    {
        worklist.push(sccRepNode(id));
    }

◆ SCCDetect() [1/2]

template<class GraphType >

virtual NodeStack & SVF::WPASolver< GraphType >::SCCDetect ( )

inlineprotectedvirtual

SCC detection.

Reimplemented in SVF::Andersen, SVF::AndersenSCD, SVF::WPAFSSolver< GraphType >, and SVF::FlowSensitive.

Definition at line 87 of file WPASolver.h.

    {
        getSCCDetector()->find();
        return getSCCDetector()->topoNodeStack();
    }

◆ SCCDetect() [2/2]

template<class GraphType >

virtual NodeStack & SVF::WPASolver< GraphType >::SCCDetect ( NodeSet & candidates )

inlineprotectedvirtual

Definition at line 92 of file WPASolver.h.

    {
        getSCCDetector()->find(candidates);
        return getSCCDetector()->topoNodeStack();
    }

◆ sccRepNode()

template<class GraphType >

virtual NodeID SVF::WPASolver< GraphType >::sccRepNode ( NodeID id ) const

inlineprotectedvirtual

Reimplemented in SVF::WPAFSSolver< GraphType >, SVF::AndersenBase, and SVF::Steensgaard.

Definition at line 145 of file WPASolver.h.

    {
        return getSCCDetector()->repNode(id);
    }

◆ setGraph()

template<class GraphType >

void SVF::WPASolver< GraphType >::setGraph ( GraphType g )

inlineprotected

Definition at line 79 of file WPASolver.h.

    {
        _graph = g;
        scc = std::make_unique<SCC>(_graph);
    }

◆ solveWorklist()

template<class GraphType >

virtual void SVF::WPASolver< GraphType >::solveWorklist ( )

inlineprotectedvirtual

Reimplemented in SVF::AndersenWaveDiff, SVF::AndersenSCD, and SVF::Steensgaard.

Definition at line 109 of file WPASolver.h.

    {
        while (!isWorklistEmpty())
        {
            NodeID nodeId = popFromWorklist();
            // Keep solving until workList is empty.
            processNode(nodeId);
            collapseFields();
        }
    }

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

/home/runner/work/SVF/SVF/svf/include/WPA/WPASolver.h

Public Types

Public Attributes

Protected Member Functions

Protected Attributes

Detailed Description

Member Typedef Documentation

◆ child_iterator

◆ GEDGE

◆ GNODE

◆ GTraits

◆ SCC

◆ WorkList

Constructor & Destructor Documentation

◆ WPASolver()

◆ ~WPASolver()

Member Function Documentation

◆ collapseFields()

◆ getSCCDetector()

◆ graph()

◆ initWorklist()

◆ isInWorklist()

◆ isWorklistEmpty()

◆ Node()

◆ Node_Index()

◆ popFromWorklist()

◆ processNode()

◆ propagate()

◆ propFromSrcToDst()

◆ pushIntoWorklist()

◆ SCCDetect() [1/2]

◆ SCCDetect() [2/2]

◆ sccRepNode()

◆ setGraph()

◆ solveWorklist()

Member Data Documentation

◆ _graph

◆ iterationForPrintStat

◆ numOfIteration

◆ reanalyze

◆ scc

◆ worklist