SVF::FSMPTA< SVFGGraph > Class Template Reference

#include <FSMPTA.h>

Inheritance diagram for SVF::FSMPTA< SVFGGraph >:

Public Member Functions
	FSMPTA (AndersenWaveDiff &preAnalysis, SVFG &backingGraph, SVFGGraph solveGraph)
	~FSMPTA () override=default
void	initialize () override
	Initialize analysis.
void	finalize () override
	Finalize analysis.
Public Member Functions inherited from SVF::FlowSensitive
	FlowSensitive (SVFIR *_pag, PTATY type=PTATY::FSSPARSE_WPA)
	Constructor.
	~FlowSensitive () override=default
	Destructor.
virtual bool	runOnModule ()
	We start from here.
void	analyze () override
	Flow sensitive analysis.
virtual void	solveAndwritePtsToFile (const std::string &filename)
virtual void	readPtsFromFile (const std::string &filename)
virtual void	solveConstraints ()
const std::string	PTAName () const override
	Get PTA name.
SVFG *	getSVFG () const
	Return SVFG.
Public Member Functions inherited from SVF::WPAFSSolver< GraphType >
	WPAFSSolver ()
	Constructor.
virtual	~WPAFSSolver ()
	Destructor.
virtual NodeID	sccRepNode (NodeID id) const
	SCC methods.
Public Member Functions inherited from SVF::BVDataPTAImpl
	BVDataPTAImpl (SVFIR *pag, PTATY type, bool alias_check=true)
	Constructor.
	~BVDataPTAImpl () override=default
	Destructor.
PersistentPointsToCache< PointsTo > &	getPtCache ()
const PointsTo &	getPts (NodeID id) override
const NodeSet &	getRevPts (NodeID nodeId) override
virtual void	clearPts (NodeID id, NodeID element)
	Remove element from the points-to set of id.
virtual void	clearFullPts (NodeID id)
	Clear points-to set of id.
virtual bool	unionPts (NodeID id, const PointsTo &target)
virtual bool	unionPts (NodeID id, NodeID ptd)
virtual bool	addPts (NodeID id, NodeID ptd)
virtual void	clearAllPts ()
	Clear all data.
virtual void	expandFIObjs (const PointsTo &pts, PointsTo &expandedPts)
	Expand FI objects.
virtual void	expandFIObjs (const NodeBS &pts, NodeBS &expandedPts)
	TODO: remove repetition.
void	remapPointsToSets (void)
	Remap all points-to sets to use the current mapping.
virtual void	writeToFile (const std::string &filename)
	Interface for analysis result storage on filesystem.
virtual void	writeObjVarToFile (const std::string &filename)
virtual void	writePtsResultToFile (std::fstream &f)
virtual void	writeGepObjVarMapToFile (std::fstream &f)
virtual bool	readFromFile (const std::string &filename)
virtual void	readPtsResultFromFile (std::ifstream &f)
virtual void	readGepObjVarMapFromFile (std::ifstream &f)
virtual void	readAndSetObjFieldSensitivity (std::ifstream &f, const std::string &delimiterStr)
AliasResult	alias (const SVFVar *V1, const SVFVar *V2) override
	Interface expose to users of our pointer analysis, given Value infos.
AliasResult	alias (NodeID node1, NodeID node2) override
	Interface expose to users of our pointer analysis, given PAGNodeID.
virtual AliasResult	alias (const PointsTo &pts1, const PointsTo &pts2)
	Interface expose to users of our pointer analysis, given two pts.
bool	mayAlias (const PointsTo &pts1, const PointsTo &pts2)
	Convenience bool wrappers: return true if the two operands may/must/partial alias.
void	dumpCPts () override
	dump and debug, print out conditional pts
void	dumpTopLevelPtsTo () override
void	dumpAllPts () override
Public Member Functions inherited from SVF::PointerAnalysis
ICFG *	getICFG () const
	Get ICFG.
u32_t	getNumOfResolvedIndCallEdge () const
	Return number of resolved indirect call edges.
CallGraph *	getCallGraph () const
	Return call graph.
CallGraphSCC *	getCallGraphSCC () const
	Return call graph SCC.
	PointerAnalysis (SVFIR *pag, PTATY ty=PTATY::Default_PTA, bool alias_check=true)
	Constructor.
PTATY	getAnalysisTy () const
	Type of pointer analysis.
PTAImplTy	getImplTy () const
	Return implementation type of the pointer analysis.
bool	printStat ()
	Whether print statistics.
void	disablePrintStat ()
	Whether print statistics.
CallEdgeMap &	getIndCallMap ()
	Get callees from an indirect callsite.
bool	hasIndCSCallees (const CallICFGNode *cs) const
const FunctionSet &	getIndCSCallees (const CallICFGNode *cs) const
virtual void	resolveIndCalls (const CallICFGNode *cs, const PointsTo &target, CallEdgeMap &newEdges)
	Resolve indirect call edges.
void	callGraphSCCDetection ()
	PTACallGraph SCC related methods.
NodeID	getCallGraphSCCRepNode (NodeID id) const
	Get SCC rep node of a SVFG node.
bool	inSameCallGraphSCC (const FunObjVar *fun1, const FunObjVar *fun2)
	Return TRUE if this edge is inside a PTACallGraph SCC, i.e., src node and dst node are in the same SCC on the SVFG.
bool	isInRecursion (const FunObjVar *fun) const
bool	isLocalVarInRecursiveFun (NodeID id) const
	Whether a local variable is in function recursions.
CommonCHGraph *	getCHGraph () const
	get CHGraph
void	getVFnsFromCHA (const CallICFGNode *cs, VFunSet &vfns)
void	getVFnsFromPts (const CallICFGNode *cs, const PointsTo &target, VFunSet &vfns)
void	connectVCallToVFns (const CallICFGNode *cs, const VFunSet &vfns, CallEdgeMap &newEdges)
virtual void	resolveCPPIndCalls (const CallICFGNode *cs, const PointsTo &target, CallEdgeMap &newEdges)
	Resolve cpp indirect call edges.
SVFIR *	getPAG () const
PTAStat *	getStat () const
	Get PTA stat.
OrderedNodeSet &	getAllValidPtrs ()
	Get all Valid Pointers for resolution.
virtual void	computeDDAPts (NodeID)
	Compute points-to results on-demand, overridden by derived classes.
bool	mayAlias (const SVFVar *V1, const SVFVar *V2)
	Convenience bool wrappers: return true if the two operands may/must/partial alias.
bool	mayAlias (NodeID node1, NodeID node2)
void	printIndCSTargets (const CallICFGNode *cs, const FunctionSet &targets)
	Print targets of a function pointer.
virtual void	dumpPts (NodeID ptr, const PointsTo &pts)
void	printIndCSTargets ()
void	dumpAllTypes ()
void	dumpStat ()
	Dump the statistics.
bool	containBlackHoleNode (const PointsTo &pts)
	Determine whether a points-to contains a black hole or constant node.
bool	containConstantNode (const PointsTo &pts)
virtual bool	isBlkObjOrConstantObj (NodeID ptd) const
bool	isHeapMemObj (NodeID id) const
	Whether this object is heap or array.
bool	isArrayMemObj (NodeID id) const
bool	isFIObjNode (NodeID id) const
NodeID	getBaseObjVarID (NodeID id)
NodeID	getFIObjVar (NodeID id)
NodeID	getGepObjVar (NodeID id, const APOffset &ap)
virtual const NodeBS &	getAllFieldsObjVars (NodeID id)
void	setObjFieldInsensitive (NodeID id)
bool	isFieldInsensitive (NodeID id) const

Static Public Member Functions
static bool	supportsCurrentConfiguration ()
static NodeBS	buildExecutionDependencyClosure (SVFG *graph, AndersenBase *preAnalysis, NodeBS dependencyNodes)
Static Public Member Functions inherited from SVF::FlowSensitive
static FlowSensitive *	createFSWPA (SVFIR *_pag)
	Create single instance of flow-sensitive pointer analysis.
static void	releaseFSWPA ()
	Release flow-sensitive pointer analysis.
static bool	classof (const FlowSensitive *)
	Methods for support type inquiry through isa, cast, and dyn_cast.
static bool	classof (const PointerAnalysis *pta)
Static Public Member Functions inherited from SVF::BVDataPTAImpl
static bool	classof (const PointerAnalysis *pta)

Protected Member Functions
NodeStack &	SCCDetect () override
	SCC detection.
void	processNode (NodeID nodeId) override
	Handle various constraints.
void	updateConnectedNodes (const SVFGEdgeSetTy &edges) override
	Update nodes connected during updating call graph.
Protected Member Functions inherited from SVF::FlowSensitive
bool	propFromSrcToDst (SVFGEdge *edge) override
	Propagation.
virtual bool	propAlongDirectEdge (const DirectSVFGEdge *edge)
	Propagate points-to information along a DIRECT SVFG edge.
virtual bool	propAlongIndirectEdge (const IndirectSVFGEdge *edge)
	Propagate points-to information along an INDIRECT SVFG edge.
virtual bool	propVarPtsFromSrcToDst (NodeID var, const SVFGNode *src, const SVFGNode *dst)
	Propagate points-to information of a certain variable from src to dst.
virtual bool	propagateFromAPToFP (const ActualParmSVFGNode *ap, const SVFGNode *dst)
virtual bool	propagateFromFRToAR (const FormalRetSVFGNode *fr, const SVFGNode *dst)
virtual bool	weakUpdateOutFromIn (const SVFGNode *node)
	Handle weak updates.
virtual bool	strongUpdateOutFromIn (const SVFGNode *node, NodeID singleton)
	Handle strong updates.
bool	propVarPtsAfterCGUpdated (NodeID var, const SVFGNode *src, const SVFGNode *dst)
virtual bool	propDFOutToIn (const SVFGNode *srcStmt, NodeID srcVar, const SVFGNode *dstStmt, NodeID dstVar)
virtual bool	propDFInToIn (const SVFGNode *srcStmt, NodeID srcVar, const SVFGNode *dstStmt, NodeID dstVar)
bool	updateOutFromIn (const SVFGNode *srcStmt, NodeID srcVar, const SVFGNode *dstStmt, NodeID dstVar)
	Update data-flow points-to data.
virtual bool	updateInFromIn (const SVFGNode *srcStmt, NodeID srcVar, const SVFGNode *dstStmt, NodeID dstVar)
virtual bool	updateInFromOut (const SVFGNode *srcStmt, NodeID srcVar, const SVFGNode *dstStmt, NodeID dstVar)
virtual bool	unionPtsFromIn (const SVFGNode *stmt, NodeID srcVar, NodeID dstVar)
virtual bool	unionPtsFromTop (const SVFGNode *stmt, NodeID srcVar, NodeID dstVar)
void	clearAllDFOutVarFlag (const SVFGNode *stmt)
bool	processSVFGNode (SVFGNode *node)
virtual bool	processAddr (const AddrSVFGNode *addr)
virtual bool	processCopy (const CopySVFGNode *copy)
virtual bool	processPhi (const PHISVFGNode *phi)
virtual bool	processGep (const GepSVFGNode *edge)
virtual bool	processLoad (const LoadSVFGNode *load)
virtual bool	processStore (const StoreSVFGNode *store)
bool	updateCallGraph (const CallSiteToFunPtrMap &callsites) override
	Update call graph.
void	connectCallerAndCallee (const CallEdgeMap &newEdges, SVFGEdgeSetTy &edges)
	Connect nodes in SVFG.
bool	isStrongUpdate (const SVFGNode *node, NodeID &singleton)
	Return TRUE if this is a strong update STORE statement.
virtual void	countAliases (Set< std::pair< NodeID, NodeID > > cmp, unsigned *mayAliases, unsigned *noAliases)
	Fills may/noAliases for the location/pointer pairs in cmp.
const PointsTo &	getDFInPtsSet (const SVFGNode *stmt, const NodeID node)
	Get points-to set for a node from data flow IN/OUT set at a statement.
const PointsTo &	getDFOutPtsSet (const SVFGNode *stmt, const NodeID node)
virtual void	cluster (void)
virtual void	plainMap (void) const
	Sets the global best mapping as a plain mapping, i.e. n -> n.
void	svfgStat ()
const DFInOutMap &	getDFInputMap () const
const DFInOutMap &	getDFOutputMap () const
Protected Member Functions inherited from SVF::WPASolver< GraphType >
	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 (NodeSet &candidates)
virtual void	initWorklist ()
virtual void	solveWorklist ()
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.
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 Member Functions inherited from SVF::BVDataPTAImpl
PTDataTy *	getPTDataTy () const
	Get points-to data structure.
DiffPTDataTy *	getDiffPTDataTy () const
DFPTDataTy *	getDFPTDataTy () const
MutDFPTDataTy *	getMutDFPTDataTy () const
VersionedPTDataTy *	getVersionedPTDataTy () const
virtual void	onTheFlyCallGraphSolve (const CallSiteToFunPtrMap &callsites, CallEdgeMap &newEdges)
	On the fly call graph construction.
virtual void	onTheFlyThreadCallGraphSolve (const CallSiteToFunPtrMap &callsites, CallEdgeMap &newForkEdges)
	On the fly thread call graph construction respecting forksite.
virtual void	normalizePointsTo ()
Protected Member Functions inherited from SVF::PointerAnalysis
const CallSiteToFunPtrMap &	getIndirectCallsites () const
	Return all indirect callsites.
NodeID	getFunPtr (const CallICFGNode *cs) const
	Return function pointer PAGNode at a callsite cs.
virtual void	validateTests ()
	Alias check functions to verify correctness of pointer analysis.
virtual void	validateSuccessTests (std::string fun)
virtual void	validateExpectedFailureTests (std::string fun)
void	resetObjFieldSensitive ()
	Reset all object node as field-sensitive.

Private Types
using	SolveGraphTraits = GenericGraphTraits< SVFGGraph >

Private Member Functions
void	buildRetainedAdjacency ()
void	cacheRetainedEdge (SVFGEdge *edge)

Static Private Member Functions
static void	enqueueSVFGNode (const SVFGNode *node, NodeBS &retained, std::deque< NodeID > &worklist)
static void	demandTopLevelPointer (const SVFVar *var, SVFG *graph, NodeBS &demandedVars, NodeBS &retained, std::deque< NodeID > &worklist)
static void	collectNodeInputDependencies (const SVFGNode *node, SVFG *graph, NodeBS &demandedVars, NodeBS &retained, std::deque< NodeID > &worklist)

Private Attributes
AndersenWaveDiff *	preAnalysis
SVFG *	backingGraph
SVFGGraph	solveGraph
std::unique_ptr< SCCDetection< SVFGGraph > >	solveSCC
NodeStack	solveNodeStack
Map< NodeID, std::vector< SVFGEdge * > >	retainedOutEdges
Set< const SVFGEdge * >	retainedEdgeSet

Additional Inherited Members
Public Types inherited from SVF::FlowSensitive
typedef BVDataPTAImpl::MutDFPTDataTy	MutDFPTDataTy
typedef BVDataPTAImpl::MutDFPTDataTy::DFPtsMap	DFInOutMap
typedef BVDataPTAImpl::MutDFPTDataTy::PtsMap	PtsMap
Public Types inherited from SVF::WPASolver< GraphType >
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 Types inherited from SVF::BVDataPTAImpl
typedef PTData< NodeID, NodeSet, NodeID, PointsTo >	PTDataTy
typedef DiffPTData< NodeID, NodeSet, NodeID, PointsTo >	DiffPTDataTy
typedef DFPTData< NodeID, NodeSet, NodeID, PointsTo >	DFPTDataTy
typedef VersionedPTData< NodeID, NodeSet, NodeID, PointsTo, VersionedVar, Set< VersionedVar > >	VersionedPTDataTy
typedef MutablePTData< NodeID, NodeSet, NodeID, PointsTo >	MutPTDataTy
typedef MutableDiffPTData< NodeID, NodeSet, NodeID, PointsTo >	MutDiffPTDataTy
typedef MutableDFPTData< NodeID, NodeSet, NodeID, PointsTo >	MutDFPTDataTy
typedef MutableIncDFPTData< NodeID, NodeSet, NodeID, PointsTo >	MutIncDFPTDataTy
typedef MutableVersionedPTData< NodeID, NodeSet, NodeID, PointsTo, VersionedVar, Set< VersionedVar > >	MutVersionedPTDataTy
typedef PersistentPTData< NodeID, NodeSet, NodeID, PointsTo >	PersPTDataTy
typedef PersistentDiffPTData< NodeID, NodeSet, NodeID, PointsTo >	PersDiffPTDataTy
typedef PersistentDFPTData< NodeID, NodeSet, NodeID, PointsTo >	PersDFPTDataTy
typedef PersistentIncDFPTData< NodeID, NodeSet, NodeID, PointsTo >	PersIncDFPTDataTy
typedef PersistentVersionedPTData< NodeID, NodeSet, NodeID, PointsTo, VersionedVar, Set< VersionedVar > >	PersVersionedPTDataTy
Public Types inherited from SVF::PointerAnalysis
typedef Set< const CallICFGNode * >	CallSiteSet
	Indirect call edges type, map a callsite to a set of callees.
typedef SVFIR::CallSiteToFunPtrMap	CallSiteToFunPtrMap
typedef Set< const FunObjVar * >	FunctionSet
typedef OrderedMap< const CallICFGNode *, FunctionSet >	CallEdgeMap
typedef SCCDetection< CallGraph * >	CallGraphSCC
typedef Set< const GlobalObjVar * >	VTableSet
typedef Set< const FunObjVar * >	VFunSet
Public Attributes inherited from SVF::WPASolver< GraphType >
u32_t	numOfIteration
	num of iterations during constraint solving
Static Public Attributes inherited from SVF::PointerAnalysis
static const std::string	aliasTestMayAlias = "MAYALIAS"
static const std::string	aliasTestMayAliasMangled = "_Z8MAYALIASPvS_"
static const std::string	aliasTestNoAlias = "NOALIAS"
static const std::string	aliasTestNoAliasMangled = "_Z7NOALIASPvS_"
static const std::string	aliasTestPartialAlias = "PARTIALALIAS"
static const std::string	aliasTestPartialAliasMangled = "_Z12PARTIALALIASPvS_"
static const std::string	aliasTestMustAlias = "MUSTALIAS"
static const std::string	aliasTestMustAliasMangled = "_Z9MUSTALIASPvS_"
static const std::string	aliasTestFailMayAlias = "EXPECTEDFAIL_MAYALIAS"
static const std::string	aliasTestFailMayAliasMangled = "_Z21EXPECTEDFAIL_MAYALIASPvS_"
static const std::string	aliasTestFailNoAlias = "EXPECTEDFAIL_NOALIAS"
static const std::string	aliasTestFailNoAliasMangled = "_Z20EXPECTEDFAIL_NOALIASPvS_"
Protected Types inherited from SVF::FlowSensitive
typedef SVFG::SVFGEdgeSetTy	SVFGEdgeSetTy
Protected Attributes inherited from SVF::FlowSensitive
SVFG *	svfg
SVFGBuilder	memSSA
AndersenWaveDiff *	ander
std::vector< std::pair< hclust_fast_methods, std::vector< NodeID > > >	candidateMappings
	Save candidate mappings for evaluation's sake.
u32_t	numOfProcessedAddr
	Statistics.
u32_t	numOfProcessedCopy
	Number of processed Addr node.
u32_t	numOfProcessedGep
	Number of processed Copy node.
u32_t	numOfProcessedPhi
	Number of processed Gep node.
u32_t	numOfProcessedLoad
	Number of processed Phi node.
u32_t	numOfProcessedStore
	Number of processed Load node.
u32_t	numOfProcessedActualParam
	Number of processed Store node.
u32_t	numOfProcessedFormalRet
	Number of processed actual param node.
u32_t	numOfProcessedMSSANode
	Number of processed formal ret node.
u32_t	maxSCCSize
	Number of processed mssa node.
u32_t	numOfSCC
u32_t	numOfNodesInSCC
double	solveTime
	time of solve.
double	sccTime
	time of SCC detection.
double	processTime
	time of processNode.
double	propagationTime
	time of points-to propagation.
double	directPropaTime
	time of points-to propagation of address-taken objects
double	indirectPropaTime
	time of points-to propagation of top-level pointers
double	updateTime
	time of strong/weak updates.
double	addrTime
	time of handling address edges
double	copyTime
	time of handling copy edges
double	gepTime
	time of handling gep edges
double	loadTime
	time of load edges
double	storeTime
	time of store edges
double	phiTime
	time of phi nodes.
double	updateCallGraphTime
	time of updating call graph
NodeBS	svfgHasSU
Protected Attributes inherited from SVF::WPAFSSolver< GraphType >
NodeStack	nodeStack
	stack used for processing nodes.
Protected Attributes inherited from SVF::WPASolver< GraphType >
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.
Protected Attributes inherited from SVF::PointerAnalysis
bool	print_stat
	User input flags.
bool	alias_validation
	Flag for validating points-to/alias results.
u32_t	OnTheFlyIterBudgetForStat
	Flag for iteration budget for on-the-fly statistics.
PTATY	ptaTy
	Pointer analysis Type.
PTAImplTy	ptaImplTy
	PTA implementation type.
PTAStat *	stat
	Statistics.
CallGraph *	callgraph
	Call graph used for pointer analysis.
CallGraphSCC *	callGraphSCC
	SCC for PTACallGraph.
ICFG *	icfg
	Interprocedural control-flow graph.
CommonCHGraph *	chgraph
	CHGraph.
Static Protected Attributes inherited from SVF::FlowSensitive
static std::unique_ptr< FlowSensitive >	fspta
Static Protected Attributes inherited from SVF::PointerAnalysis
static SVFIR *	pag = nullptr
	SVFIR.

Detailed Description

template<class SVFGGraph>
class SVF::FSMPTA< SVFGGraph >

Flow-sensitive solver over an already-built thread-aware SVFG. SVFGGraph is either SVFG* for the whole graph or const SlicedSVFGView* for an exact slice. The backing SVFG is owned by MTASVFGBuilder; this class owns only the analysis state and the SCC detector for its solve graph.

Definition at line 54 of file FSMPTA.h.

Member Typedef Documentation

SolveGraphTraits

template<class SVFGGraph >

using SVF::FSMPTA< SVFGGraph >::SolveGraphTraits = GenericGraphTraits<SVFGGraph>

private

Definition at line 80 of file FSMPTA.h.

Constructor & Destructor Documentation

FSMPTA()

template<class SVFGGraph >

FSMPTA::FSMPTA	(	AndersenWaveDiff &	preAnalysis,
		SVFG &	backingGraph,
		SVFGGraph	solveGraph
	)

Definition at line 42 of file FSMPTA.cpp.

    : FlowSensitive(pre.getPAG()), preAnalysis(&pre), backingGraph(&graph),
      solveGraph(solveGraph)
{
}

~FSMPTA()

template<class SVFGGraph >

SVF::FSMPTA< SVFGGraph >::~FSMPTA ( )

overridedefault

Member Function Documentation

buildExecutionDependencyClosure()

template<class SVFGGraph >

NodeBS FSMPTA::buildExecutionDependencyClosure ( SVFG *  graph, AndersenBase *  preAnalysis, NodeBS  dependencyNodes  )

static

Close a backward value-flow slice over FlowSensitive's execution dependencies. Besides explicit SVFG predecessors, this follows the definition of every top-level pointer read through the solver-global points-to map, closes future indirect-call boundary edges, and retains variant-GEP transfers whose field-sensitivity side effect is global.

Definition at line 121 of file FSMPTA.cpp.

{
    if (graph == nullptr || preAnalysis == nullptr)
    {
        SVFUtil::errs() << "[ERROR] FSMPTA execution closure requires a BaseSVFG "
                        << "and Andersen targets\n";
        return NodeBS();
    }
 
    std::deque<NodeID> nodeWorklist;
    for (NodeID id : dependencyNodes)
        nodeWorklist.push_back(id);
 
    NodeBS demandedVars;
    // FlowSensitive::solveConstraints invokes updateCallGraph() for the whole
    // program after every iteration. Its function-pointer reads are therefore
    // execution roots even when the call site is not itself in the target slice.
    SVFIR* pag = graph->getPAG();
    for (const auto& callsiteAndPtr : pag->getIndirectCallsites())
    {
        const SVFVar* funPtr = pag->getGNode(callsiteAndPtr.second);
        demandTopLevelPointer(funPtr, graph, demandedVars,
                              dependencyNodes, nodeWorklist);
    }
 
    Set<const CallICFGNode*> indirectSites;
    Set<const FunObjVar*> indirectTargets;
    for (const auto& callsiteAndPtr : pag->getIndirectCallsites())
        indirectSites.insert(callsiteAndPtr.first);
    for (const auto& callsiteAndTargets : preAnalysis->getIndCallMap())
        for (const FunObjVar* target : callsiteAndTargets.second)
            indirectTargets.insert(target);
 
    // One backing-SVFG pass collects both kinds of solver-global roots:
    // updateCallGraph boundary nodes and variant-GEP side effects.
    for (SVFG::const_iterator it = graph->begin(), eit = graph->end();
            it != eit; ++it)
    {
        const SVFGNode* node = it->second;
        bool boundary = false;
        if (const ActualParmSVFGNode* actual =
                    SVFUtil::dyn_cast<ActualParmSVFGNode>(node))
            boundary = indirectSites.count(actual->getCallSite()) > 0;
        else if (const ActualRetSVFGNode* actual =
                     SVFUtil::dyn_cast<ActualRetSVFGNode>(node))
            boundary = indirectSites.count(actual->getCallSite()) > 0;
        else if (const ActualINSVFGNode* actual =
                     SVFUtil::dyn_cast<ActualINSVFGNode>(node))
            boundary = indirectSites.count(actual->getCallSite()) > 0;
        else if (const ActualOUTSVFGNode* actual =
                     SVFUtil::dyn_cast<ActualOUTSVFGNode>(node))
            boundary = indirectSites.count(actual->getCallSite()) > 0;
        else if (const FormalParmSVFGNode* formal =
                     SVFUtil::dyn_cast<FormalParmSVFGNode>(node))
            boundary = indirectTargets.count(formal->getFun()) > 0;
        else if (const FormalRetSVFGNode* formal =
                     SVFUtil::dyn_cast<FormalRetSVFGNode>(node))
            boundary = indirectTargets.count(formal->getFun()) > 0;
        else if (const FormalINSVFGNode* formal =
                     SVFUtil::dyn_cast<FormalINSVFGNode>(node))
            boundary = indirectTargets.count(
                           formal->getFunEntryNode()->getFun()) > 0;
        else if (const FormalOUTSVFGNode* formal =
                     SVFUtil::dyn_cast<FormalOUTSVFGNode>(node))
            boundary = indirectTargets.count(
                           formal->getFunExitNode()->getFun()) > 0;
        else if (const InterMSSAPHISVFGNode* phi =
                     SVFUtil::dyn_cast<InterMSSAPHISVFGNode>(node))
            boundary = phi->isFormalINPHI()
                       ? indirectTargets.count(phi->getFun()) > 0
                       : indirectSites.count(phi->getCallSite()) > 0;
 
        if (boundary)
            enqueueSVFGNode(node, dependencyNodes, nodeWorklist);
 
        // A variant GEP changes field-sensitivity globally. Later transfers
        // read that state without an explicit SVFG edge.
        if (const GepSVFGNode* gep = SVFUtil::dyn_cast<GepSVFGNode>(node))
        {
            const GepStmt* stmt = SVFUtil::cast<GepStmt>(gep->getSVFStmt());
            if (stmt->isVariantFieldGep())
                enqueueSVFGNode(gep, dependencyNodes, nodeWorklist);
        }
    }
 
    // Joint fixed point: explicit SVFG predecessors carry direct/MemorySSA
    // dependencies; definition roots cover FlowSensitive's implicit reads from
    // the solver-global top-level points-to relation.
    while (!nodeWorklist.empty())
    {
        const NodeID id = nodeWorklist.front();
        nodeWorklist.pop_front();
        const SVFGNode* node = graph->getSVFGNode(id);
 
        for (const SVFGEdge* edge : node->getInEdges())
            enqueueSVFGNode(
                edge->getSrcNode(), dependencyNodes, nodeWorklist);
 
        collectNodeInputDependencies(
            node, graph, demandedVars, dependencyNodes, nodeWorklist);
    }
    return dependencyNodes;
}

buildRetainedAdjacency()

template<class SVFGGraph >

void FSMPTA::buildRetainedAdjacency ( )

private

Definition at line 271 of file FSMPTA.cpp.

{
    for (SVFG::iterator it = svfg->begin(), eit = svfg->end(); it != eit; ++it)
    {
        SVFGNode* node = it->second;
        if (!SolveGraphTraits::containsNode(solveGraph, node))
            continue;
        for (SVFGEdge* edge : node->getOutEdges())
            cacheRetainedEdge(edge);
    }
}

cacheRetainedEdge()

template<class SVFGGraph >

void FSMPTA::cacheRetainedEdge ( SVFGEdge *  edge )

private

Definition at line 263 of file FSMPTA.cpp.

{
    if (SolveGraphTraits::containsEdge(solveGraph, edge) &&
            retainedEdgeSet.insert(edge).second)
        retainedOutEdges[edge->getSrcID()].push_back(edge);
}

collectNodeInputDependencies()

template<class SVFGGraph >

void FSMPTA::collectNodeInputDependencies ( const SVFGNode *  node, SVFG *  graph, NodeBS &  demandedVars, NodeBS &  retained, std::deque< NodeID > &  nodeWorklist  )

staticprivate

Register every solver-global top-level points-to read performed while a node is processed. MemorySSA IN/OUT state is carried by explicit indirect SVFG predecessors and therefore needs no separate variable root here.

Definition at line 86 of file FSMPTA.cpp.

{
    if (const CopySVFGNode* copy = SVFUtil::dyn_cast<CopySVFGNode>(node))
        demandTopLevelPointer(copy->getSrcNode(), graph, demandedVars,
                              retained, nodeWorklist);
    else if (const GepSVFGNode* gep = SVFUtil::dyn_cast<GepSVFGNode>(node))
        demandTopLevelPointer(gep->getSrcNode(), graph, demandedVars,
                              retained, nodeWorklist);
    else if (const PHISVFGNode* phi = SVFUtil::dyn_cast<PHISVFGNode>(node))
        for (auto it = phi->opVerBegin(), eit = phi->opVerEnd(); it != eit; ++it)
            demandTopLevelPointer(it->second, graph, demandedVars,
                                  retained, nodeWorklist);
    else if (const LoadSVFGNode* load = SVFUtil::dyn_cast<LoadSVFGNode>(node))
        demandTopLevelPointer(load->getSrcNode(), graph, demandedVars,
                              retained, nodeWorklist);
    else if (const StoreSVFGNode* store = SVFUtil::dyn_cast<StoreSVFGNode>(node))
    {
        demandTopLevelPointer(store->getDstNode(), graph, demandedVars,
                              retained, nodeWorklist);
        demandTopLevelPointer(store->getSrcNode(), graph, demandedVars,
                              retained, nodeWorklist);
    }
    else if (const ActualParmSVFGNode* actual =
                 SVFUtil::dyn_cast<ActualParmSVFGNode>(node))
        demandTopLevelPointer(actual->getParam(), graph, demandedVars,
                              retained, nodeWorklist);
    else if (const FormalRetSVFGNode* formal =
                 SVFUtil::dyn_cast<FormalRetSVFGNode>(node))
        demandTopLevelPointer(formal->getRet(), graph, demandedVars,
                              retained, nodeWorklist);
}

demandTopLevelPointer()

template<class SVFGGraph >

void FSMPTA::demandTopLevelPointer ( const SVFVar *  var, SVFG *  graph, NodeBS &  demandedVars, NodeBS &  retained, std::deque< NodeID > &  worklist  )

staticprivate

Definition at line 69 of file FSMPTA.cpp.

{
    const ValVar* val = SVFUtil::dyn_cast<ValVar>(var);
    if (val == nullptr || !val->isPointer() || demandedVars.test(val->getId()))
        return;
 
    demandedVars.set(val->getId());
    if (graph->hasDefSVFGNode(val))
        enqueueSVFGNode(graph->getDefSVFGNode(val), retained, nodeWorklist);
}

enqueueSVFGNode()

template<class SVFGGraph >

void FSMPTA::enqueueSVFGNode ( const SVFGNode *  node, NodeBS &  retained, std::deque< NodeID > &  worklist  )

staticprivate

Definition at line 57 of file FSMPTA.cpp.

{
    if (node != nullptr && !retained.test(node->getId()))
    {
        retained.set(node->getId());
        nodeWorklist.push_back(node->getId());
    }
}

finalize()

template<class SVFGGraph >

void FSMPTA::finalize ( )

overridevirtual

Finalize analysis.

Finalize analysis

Reimplemented from SVF::FlowSensitive.

Definition at line 255 of file FSMPTA.cpp.

{
    if (Options::DumpVFG())
        svfg->dump("fs_solved", true);
    BVDataPTAImpl::finalize();
}

initialize()

template<class SVFGGraph >

void FSMPTA::initialize ( )

overridevirtual

Initialize analysis.

Initialize analysis

Reimplemented from SVF::FlowSensitive.

Definition at line 227 of file FSMPTA.cpp.

{
    PointerAnalysis::initialize();
    stat = new FlowSensitiveStat(this);
    // SlicedMTA reports the deployment-facing result summary. Avoid the generic
    // FlowSensitive statistics pass because it recomputes SCCs on the full SVFG.
    disablePrintStat();
 
    if (!supportsCurrentConfiguration())
    {
        SVFUtil::errs() << "[ERROR] FSMPTA does not support clustered Andersen, "
                        << "clustered FS, or plain FS mappings\n";
        std::abort();
    }
 
    // Reuse both the Andersen result and the already-built base SVFG. The main
    // ILA overlay has been attached by SlicedMTA before analysis starts.
    ander = preAnalysis;
    svfg = backingGraph;
    // Retain the stock graph handle for FlowSensitive's dynamic-call support;
    // SCC/worklist topology is supplied exclusively by solveSCC below.
    setGraph(svfg);
    solveSCC = std::make_unique<SCCDetection<SVFGGraph>>(solveGraph);
    if constexpr (SolveGraphTraits::isFilteredGraph)
        buildRetainedAdjacency();
}

processNode()

template<class SVFGGraph >

void FSMPTA::processNode ( NodeID  nodeId )

overrideprotectedvirtual

Handle various constraints.

Process each SVFG node

Reimplemented from SVF::FlowSensitive.

Definition at line 309 of file FSMPTA.cpp.

{
    SVFGNode* node = svfg->getSVFGNode(nodeId);
    assert(SolveGraphTraits::containsNode(solveGraph, node) &&
           "FSMPTA worklist must never contain a node outside the solve graph");
 
    if (processSVFGNode(node))
    {
        if constexpr (SolveGraphTraits::isFilteredGraph)
        {
            const auto found = retainedOutEdges.find(nodeId);
            if (found != retainedOutEdges.end())
            {
                for (SVFGEdge* edge : found->second)
                {
                    if (propFromSrcToDst(edge))
                    {
                        pushIntoWorklist(edge->getDstID());
                    }
                }
            }
        }
        else
        {
            for (SVFGEdge* edge : node->getOutEdges())
            {
                if (propFromSrcToDst(edge))
                {
                    pushIntoWorklist(edge->getDstID());
                }
            }
        }
    }
    clearAllDFOutVarFlag(node);
}

SCCDetect()

template<class SVFGGraph >

NodeStack & FSMPTA::SCCDetect ( )

overrideprotectedvirtual

SCC detection.

SCC detection

Reimplemented from SVF::FlowSensitive.

Definition at line 284 of file FSMPTA.cpp.

{
    const double start = stat->getClk();
    solveSCC->find();
    assert(solveNodeStack.empty() && "FSMPTA SCC stack was not fully consumed");
 
    FIFOWorkList<NodeID> revTopo = solveSCC->revTopoNodeStack();
    while (!revTopo.empty())
    {
        const NodeID rep = revTopo.front();
        revTopo.pop();
        const NodeBS& subNodes = solveSCC->subNodes(rep);
        for (NodeID id : subNodes)
            solveNodeStack.push(id);
    }
 
    assert(solveNodeStack.size() == SolveGraphTraits::graphSize(solveGraph) &&
           "FSMPTA SCC topology must contain exactly the solve graph");
 
    const double end = stat->getClk();
    sccTime += (end - start) / TIMEINTERVAL;
    return solveNodeStack;
}

supportsCurrentConfiguration()

template<class SVFGGraph >

bool FSMPTA::supportsCurrentConfiguration ( )

static

Definition at line 50 of file FSMPTA.cpp.

{
    return !Options::ClusterAnder() && !Options::ClusterFs() &&
           !Options::PlainMappingFs();
}

updateConnectedNodes()

template<class SVFGGraph >

void FSMPTA::updateConnectedNodes ( const SVFGEdgeSetTy &  edges )

overrideprotectedvirtual

Update nodes connected during updating call graph.

Push nodes connected during update call graph into worklist so they will be solved during next iteration.

If this is a formal-param or actual-ret node, we need to solve this phi node in next iteration

If this is a formal-in or actual-out node, we need to propagate points-to information from its predecessor node.

If this is a field-insensitive obj, propagate all field node's pts

Reimplemented from SVF::FlowSensitive.

Definition at line 346 of file FSMPTA.cpp.

{
    if constexpr (SolveGraphTraits::isFilteredGraph)
    {
        SVFGEdgeSetTy keptEdges;
        for (SVFGEdge* edge : edges)
            if (SolveGraphTraits::containsEdge(solveGraph, edge))
            {
                keptEdges.insert(edge);
                cacheRetainedEdge(edge);
            }
        FlowSensitive::updateConnectedNodes(keptEdges);
    }
    else
    {
        FlowSensitive::updateConnectedNodes(edges);
    }
}

Member Data Documentation

backingGraph

template<class SVFGGraph >

SVFG* SVF::FSMPTA< SVFGGraph >::backingGraph

private

Definition at line 94 of file FSMPTA.h.

preAnalysis

template<class SVFGGraph >

AndersenWaveDiff* SVF::FSMPTA< SVFGGraph >::preAnalysis

private

Definition at line 93 of file FSMPTA.h.

retainedEdgeSet

template<class SVFGGraph >

Set<const SVFGEdge*> SVF::FSMPTA< SVFGGraph >::retainedEdgeSet

private

Definition at line 99 of file FSMPTA.h.

retainedOutEdges

template<class SVFGGraph >

Map<NodeID, std::vector<SVFGEdge*> > SVF::FSMPTA< SVFGGraph >::retainedOutEdges

private

Definition at line 98 of file FSMPTA.h.

solveGraph

template<class SVFGGraph >

SVFGGraph SVF::FSMPTA< SVFGGraph >::solveGraph

private

Definition at line 95 of file FSMPTA.h.

solveNodeStack

template<class SVFGGraph >

NodeStack SVF::FSMPTA< SVFGGraph >::solveNodeStack

private

Definition at line 97 of file FSMPTA.h.

solveSCC

template<class SVFGGraph >

std::unique_ptr<SCCDetection<SVFGGraph> > SVF::FSMPTA< SVFGGraph >::solveSCC

private

Definition at line 96 of file FSMPTA.h.

---

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

• /home/runner/work/SVF/SVF/svf/include/MTA/FSMPTA.h
• /home/runner/work/SVF/SVF/svf/lib/MTA/FSMPTA.cpp