#include <WPASolver.h>

Inheritance diagram for SVF::WPASolver< GraphType >:

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

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 More...

Protected Member Functions
	WPASolver ()
	Constructor. More...

virtual	~WPASolver ()=default
	Destructor. More...

SCC *	getSCCDetector () const
	Get SCC detector. More...

const GraphType	graph ()
	Get/Set graph methods. More...

void	setGraph (GraphType g)

virtual NodeStack &	SCCDetect ()
	SCC detection. More...

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. More...

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

virtual void	propagate (GNODE *v)

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

virtual NodeID	sccRepNode (NodeID id) const

NodeID	popFromWorklist ()
	Worklist operations. More...

virtual void	pushIntoWorklist (NodeID id)

bool	isWorklistEmpty ()

bool	isInWorklist (NodeID id)

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

NodeID	Node_Index (GNODE node)
	Get node ID. More...

Protected Attributes
bool	reanalyze
	Reanalyze if any constraint value changed. More...

u32_t	iterationForPrintStat
	print out statistics for i-th iteration More...

GraphType	_graph
	Graph. More...

std::unique_ptr< SCC >	scc
	SCC. More...

WorkList	worklist
	Worklist for resolution. More...

Detailed Description

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

Definition at line 43 of file WPASolver.h.

Member Typedef Documentation

◆ child_iterator

template<class GraphType >

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

Definition at line 51 of file WPASolver.h.

◆ GEDGE

template<class GraphType >

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

Definition at line 50 of file WPASolver.h.

◆ GNODE

template<class GraphType >

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

Definition at line 49 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 48 of file WPASolver.h.

◆ SCC

template<class GraphType >

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

Definition at line 53 of file WPASolver.h.

◆ WorkList

template<class GraphType >

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

Definition at line 55 of file WPASolver.h.

Constructor & Destructor Documentation

◆ WPASolver()

template<class GraphType >

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

inlineprotected

Constructor.

Definition at line 60 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 124 of file WPASolver.h.

124 {}

◆ getSCCDetector()

template<class GraphType >

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

inlineprotected

Get SCC detector.

Definition at line 67 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 74 of file WPASolver.h.

     {
         return _graph;
     }

◆ initWorklist()

template<class GraphType >

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

inlineprotectedvirtual

Reimplemented in SVF::Andersen.

Definition at line 97 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 164 of file WPASolver.h.

     {
         return worklist.find(id);
     }

◆ isWorklistEmpty()

template<class GraphType >

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

inlineprotected

Definition at line 160 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 177 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 183 of file WPASolver.h.

     {
         return GTraits::getNodeID(node);
     }

◆ popFromWorklist()

template<class GraphType >

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

inlineprotected

Worklist operations.

Definition at line 151 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::FlowSensitive, SVF::AndersenWaveDiff, SVF::Andersen, and SVF::VersionedFlowSensitive.

Definition at line 122 of file WPASolver.h.

122 {}

◆ 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 127 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 138 of file WPASolver.h.

     {
         return false;
     }

◆ pushIntoWorklist()

template<class GraphType >

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

inlineprotectedvirtual

Definition at line 156 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::FlowSensitive, SVF::WPAFSSolver< GraphType >, SVF::AndersenSCD, and SVF::Andersen.

Definition at line 86 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 91 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::Steensgaard, SVF::AndersenBase, and SVF::WPAFSSolver< GraphType >.

Definition at line 144 of file WPASolver.h.

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

◆ setGraph()

template<class GraphType >

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

inlineprotected

Definition at line 78 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::Steensgaard, SVF::AndersenSCD, and SVF::AndersenWaveDiff.

Definition at line 108 of file WPASolver.h.

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

Member Data Documentation

◆ _graph

template<class GraphType >

GraphType SVF::WPASolver< GraphType >::_graph

protected

Graph.

Definition at line 190 of file WPASolver.h.

◆ iterationForPrintStat

template<class GraphType >

u32_t SVF::WPASolver< GraphType >::iterationForPrintStat

protected

print out statistics for i-th iteration

Definition at line 173 of file WPASolver.h.

◆ numOfIteration

template<class GraphType >

u32_t SVF::WPASolver< GraphType >::numOfIteration

num of iterations during constraint solving

Definition at line 200 of file WPASolver.h.

◆ reanalyze

template<class GraphType >

bool SVF::WPASolver< GraphType >::reanalyze

protected

Reanalyze if any constraint value changed.

Definition at line 171 of file WPASolver.h.

◆ scc

template<class GraphType >

std::unique_ptr<SCC> SVF::WPASolver< GraphType >::scc

protected

SCC.

Definition at line 193 of file WPASolver.h.

◆ worklist

template<class GraphType >

WorkList SVF::WPASolver< GraphType >::worklist

protected

Worklist for resolution.

Definition at line 196 of file WPASolver.h.

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

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

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

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