#include <FlowSensitive.h>

Inheritance diagram for SVF::FlowSensitive:

Public Types
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 Member Functions
	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 ()

void	initialize () override
	Initialize analysis.

void	finalize () override
	Finalize analysis.

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 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 Types
typedef SVFG::SVFGEdgeSetTy	SVFGEdgeSetTy

Protected Member Functions
NodeStack &	SCCDetect () override
	SCC detection.

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)

void	processNode (NodeID nodeId) override
	Handle various constraints.

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.

virtual void	updateConnectedNodes (const SVFGEdgeSetTy &edges)
	Update nodes connected during updating call graph.

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.

Protected Attributes
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
static std::unique_ptr< FlowSensitive >	fspta

Static Protected Attributes inherited from SVF::PointerAnalysis
static SVFIR *	pag = nullptr
	SVFIR.

Friends
class	FlowSensitiveStat

Additional Inherited Members
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_"

Detailed Description

Definition at line 48 of file FlowSensitive.h.

Member Typedef Documentation

◆ DFInOutMap

typedef BVDataPTAImpl::MutDFPTDataTy::DFPtsMap SVF::FlowSensitive::DFInOutMap

Definition at line 56 of file FlowSensitive.h.

◆ MutDFPTDataTy

typedef BVDataPTAImpl::MutDFPTDataTy SVF::FlowSensitive::MutDFPTDataTy

Definition at line 55 of file FlowSensitive.h.

◆ PtsMap

typedef BVDataPTAImpl::MutDFPTDataTy::PtsMap SVF::FlowSensitive::PtsMap

Definition at line 57 of file FlowSensitive.h.

◆ SVFGEdgeSetTy

typedef SVFG::SVFGEdgeSetTy SVF::FlowSensitive::SVFGEdgeSetTy

protected

Definition at line 52 of file FlowSensitive.h.

Constructor & Destructor Documentation

◆ FlowSensitive()

SVF::FlowSensitive::FlowSensitive	(	SVFIR *	_pag,
		PTATY	type = `PTATY::FSSPARSE_WPA`
	)

inlineexplicit

Constructor.

Definition at line 60 of file FlowSensitive.h.

                                                                        : WPASVFGFSSolver(), BVDataPTAImpl(_pag, type)
    {
        svfg = nullptr;
        solveTime = sccTime = processTime = propagationTime = updateTime = 0;
        addrTime = copyTime = gepTime = loadTime = storeTime = phiTime = 0;
        updateCallGraphTime = directPropaTime = indirectPropaTime = 0;
        numOfProcessedAddr = numOfProcessedCopy = numOfProcessedGep = 0;
        numOfProcessedLoad = numOfProcessedStore = 0;
        numOfProcessedPhi = numOfProcessedActualParam = numOfProcessedFormalRet = 0;
        numOfProcessedMSSANode = 0;
        maxSCCSize = numOfSCC = numOfNodesInSCC = 0;
        iterationForPrintStat = OnTheFlyIterBudgetForStat;
    }

◆ ~FlowSensitive()

SVF::FlowSensitive::~FlowSensitive ( )

overridedefault

Destructor.

Member Function Documentation

◆ analyze()

void FlowSensitive::analyze ( )

overridevirtual

Flow sensitive analysis.

Start analysis

Implements SVF::PointerAnalysis.

Definition at line 127 of file FlowSensitive.cpp.

{
    if(!Options::ReadAnder().empty())
    {
        readPtsFromFile(Options::ReadAnder());
    }
    else
    {
        if(Options::WriteAnder().empty())
        {
            initialize();
            solveConstraints();
            finalize();
        }
        else
        {
            solveAndwritePtsToFile(Options::WriteAnder());
        }
    }
}

◆ classof() [1/2]

static bool SVF::FlowSensitive::classof ( const FlowSensitive * )

inlinestatic

Methods for support type inquiry through isa, cast, and dyn_cast.

Definition at line 123 of file FlowSensitive.h.

    {
        return true;
    }

◆ classof() [2/2]

static bool SVF::FlowSensitive::classof ( const PointerAnalysis * pta )

inlinestatic

Definition at line 127 of file FlowSensitive.h.

    {
        return pta->getAnalysisTy() == PTATY::FSSPARSE_WPA;
    }

◆ clearAllDFOutVarFlag()

void SVF::FlowSensitive::clearAllDFOutVarFlag ( const SVFGNode * stmt )

inlineprotected

Definition at line 210 of file FlowSensitive.h.

    {
        getDFPTDataTy()->clearAllDFOutUpdatedVar(stmt->getId());
    }

◆ cluster()

void FlowSensitive::cluster ( void )

protectedvirtual

Performs clustering based on ander, setting the global best mapping accordingly.

Reimplemented in SVF::VersionedFlowSensitive.

Definition at line 822 of file FlowSensitive.cpp.

{
    std::vector<std::pair<unsigned, unsigned>> keys;
    for (const auto& pair : *pag)
        keys.emplace_back(pair.first, 1);
 
    PointsTo::MappingPtr nodeMapping =
        std::make_shared<std::vector<NodeID>>(
            NodeIDAllocator::Clusterer::cluster(ander, keys, candidateMappings, "aux-ander", print_stat)
        );
    PointsTo::MappingPtr reverseNodeMapping =
        std::make_shared<std::vector<NodeID>>(NodeIDAllocator::Clusterer::getReverseNodeMapping(*nodeMapping));
 
    PointsTo::setCurrentBestNodeMapping(nodeMapping, reverseNodeMapping);
}

◆ connectCallerAndCallee()

void FlowSensitive::connectCallerAndCallee	(	const CallEdgeMap &	newEdges,
		SVFGEdgeSetTy &	edges
	)

protected

Connect nodes in SVFG.

Handle parameter passing in SVFG

Definition at line 737 of file FlowSensitive.cpp.

{
    CallEdgeMap::const_iterator iter = newEdges.begin();
    CallEdgeMap::const_iterator eiter = newEdges.end();
    for (; iter != eiter; iter++)
    {
        const CallICFGNode* cs = iter->first;
        const FunctionSet & functions = iter->second;
        for (FunctionSet::const_iterator func_iter = functions.begin(); func_iter != functions.end(); func_iter++)
        {
            const FunObjVar*  func = *func_iter;
            svfg->connectCallerAndCallee(cs, func, edges);
        }
    }
}

◆ countAliases()

void FlowSensitive::countAliases	(	Set< std::pair< NodeID, NodeID > >	cmp,
		unsigned *	mayAliases,
		unsigned *	noAliases
	)

protectedvirtual

Fills may/noAliases for the location/pointer pairs in cmp.

Definition at line 855 of file FlowSensitive.cpp.

{
    for (std::pair<NodeID, NodeID> locPA : cmp)
    {
        // loc doesn't make a difference for FSPTA.
        NodeID p = locPA.second;
        for (std::pair<NodeID, NodeID> locPB : cmp)
        {
            if (locPB == locPA) continue;
 
            NodeID q = locPB.second;
 
            switch (alias(p, q))
            {
            case AliasResult::NoAlias:
                ++(*noAliases);
                break;
            case AliasResult::MayAlias:
                ++(*mayAliases);
                break;
            default:
                assert("Not May/NoAlias?");
            }
        }
    }
 
}

◆ createFSWPA()

static FlowSensitive * SVF::FlowSensitive::createFSWPA ( SVFIR * _pag )

inlinestatic

Create single instance of flow-sensitive pointer analysis.

Definition at line 78 of file FlowSensitive.h.

    {
        if (fspta == nullptr)
        {
            fspta = std::unique_ptr<FlowSensitive>(new FlowSensitive(_pag));
            fspta->analyze();
        }
        return fspta.get();
    }

◆ finalize()

void FlowSensitive::finalize ( )

overridevirtual

Finalize analysis.

Finalize analysis

Reimplemented from SVF::BVDataPTAImpl.

Reimplemented in SVF::VersionedFlowSensitive.

Definition at line 162 of file FlowSensitive.cpp.

{
    if(Options::DumpVFG())
        svfg->dump("fs_solved", true);
 
    NodeStack& nodeStack = WPASolver<SVFG*>::SCCDetect();
    while (nodeStack.empty() == false)
    {
        NodeID rep = nodeStack.top();
        nodeStack.pop();
        const NodeBS& subNodes = getSCCDetector()->subNodes(rep);
        if (subNodes.count() > maxSCCSize)
            maxSCCSize = subNodes.count();
        if (subNodes.count() > 1)
        {
            numOfNodesInSCC += subNodes.count();
            numOfSCC++;
        }
    }
 
    // TODO: check -stat too.
    if (Options::ClusterFs())
    {
        Map<std::string, std::string> stats;
        const PTDataTy *ptd = getPTDataTy();
        // TODO: should we use liveOnly?
        Map<PointsTo, unsigned> allPts = ptd->getAllPts(true);
        // TODO: parameterise final arg.
        NodeIDAllocator::Clusterer::evaluate(*PointsTo::getCurrentBestNodeMapping(), allPts, stats, true);
        if (print_stat)
        {
            NodeIDAllocator::Clusterer::printStats("post-main: best", stats);
        }
    }
 
    BVDataPTAImpl::finalize();
}

◆ getDFInPtsSet()

const PointsTo & SVF::FlowSensitive::getDFInPtsSet	(	const SVFGNode *	stmt,
		const NodeID	node
	)

inlineprotected

Get points-to set for a node from data flow IN/OUT set at a statement.

Definition at line 247 of file FlowSensitive.h.

    {
        return getDFPTDataTy()->getDFInPtsSet(stmt->getId(),node);
    }

◆ getDFInputMap()

const DFInOutMap & SVF::FlowSensitive::getDFInputMap ( ) const

inlineprotected

Get IN/OUT data flow map. May only be called when the backing is MUTABLE.

Definition at line 260 of file FlowSensitive.h.

    {
        return getMutDFPTDataTy()->getDFIn();
    }

◆ getDFOutPtsSet()

const PointsTo & SVF::FlowSensitive::getDFOutPtsSet	(	const SVFGNode *	stmt,
		const NodeID	node
	)

inlineprotected

Definition at line 251 of file FlowSensitive.h.

    {
        return getDFPTDataTy()->getDFOutPtsSet(stmt->getId(),node);
    }

◆ getDFOutputMap()

const DFInOutMap & SVF::FlowSensitive::getDFOutputMap ( ) const

inlineprotected

Definition at line 264 of file FlowSensitive.h.

    {
        return getMutDFPTDataTy()->getDFOut();
    }

◆ getSVFG()

SVFG * SVF::FlowSensitive::getSVFG ( ) const

inline

Return SVFG.

Definition at line 134 of file FlowSensitive.h.

    {
        return svfg;
    }

◆ initialize()

void FlowSensitive::initialize ( )

overridevirtual

Initialize analysis.

Initialize analysis

Reimplemented from SVF::PointerAnalysis.

Reimplemented in SVF::VersionedFlowSensitive.

Definition at line 44 of file FlowSensitive.cpp.

{
    PointerAnalysis::initialize();
 
    stat = new FlowSensitiveStat(this);
 
    // TODO: support clustered aux. Andersen's.
    assert(!Options::ClusterAnder() && "FlowSensitive::initialize: clustering auxiliary Andersen's unsupported.");
    ander = AndersenWaveDiff::createAndersenWaveDiff(getPAG());
 
    // If cluster option is not set, it will give us a no-mapping points-to set.
    assert(!(Options::ClusterFs() && Options::PlainMappingFs())
           && "FS::init: plain-mapping and cluster-fs are mutually exclusive.");
    if (Options::ClusterFs())
    {
        cluster();
        // Reset the points-to cache although empty so the new mapping could
        // be applied to the inserted empty set.
        getPtCache().reset();
    }
    else if (Options::PlainMappingFs())
    {
        plainMap();
        // As above.
        getPtCache().reset();
    }
 
    svfg = memSSA.buildPTROnlySVFG(ander);
 
    setGraph(svfg);
    //AndersenWaveDiff::releaseAndersenWaveDiff();
}

◆ isStrongUpdate()

bool FlowSensitive::isStrongUpdate	(	const SVFGNode *	node,
		NodeID &	singleton
	)

protected

Return TRUE if this is a strong update STORE statement.

Find the unique element in cpts

Definition at line 654 of file FlowSensitive.cpp.

{
    bool isSU = false;
    if (const StoreSVFGNode* store = SVFUtil::dyn_cast<StoreSVFGNode>(node))
    {
        const PointsTo& dstCPSet = getPts(store->getDstNodeID());
        if (dstCPSet.count() == 1)
        {
            PointsTo::iterator it = dstCPSet.begin();
            singleton = *it;
 
            // Strong update can be made if this points-to target is not heap, array or field-insensitive.
            if (!isHeapMemObj(singleton) && !isArrayMemObj(singleton))
            {
                assert(pag->getBaseObject(singleton)->isFieldInsensitive() == pag->getBaseObject(singleton)->isFieldInsensitive());
                if (pag->getBaseObject(singleton)->isFieldInsensitive() == false
                        && !isLocalVarInRecursiveFun(singleton))
                {
                    isSU = true;
                }
            }
        }
    }
    return isSU;
}

◆ plainMap()

void FlowSensitive::plainMap ( void ) const

protectedvirtual

Sets the global best mapping as a plain mapping, i.e. n -> n.

Definition at line 838 of file FlowSensitive.cpp.

{
    assert(Options::NodeAllocStrat() == NodeIDAllocator::Strategy::DENSE
           && "FS::cluster: plain mapping requires dense allocation strategy.");
 
    const size_t numObjects = NodeIDAllocator::get()->getNumObjects();
    PointsTo::MappingPtr plainMapping = std::make_shared<std::vector<NodeID>>(numObjects);
    PointsTo::MappingPtr reversePlainMapping = std::make_shared<std::vector<NodeID>>(numObjects);
    for (NodeID i = 0; i < plainMapping->size(); ++i)
    {
        plainMapping->at(i) = i;
        reversePlainMapping->at(i) = i;
    }
 
    PointsTo::setCurrentBestNodeMapping(plainMapping, reversePlainMapping);
}

◆ processAddr()

bool FlowSensitive::processAddr ( const AddrSVFGNode * addr )

protectedvirtual

Process address node

TODO: If this object has been set as field-insensitive, just add the insensitive object node into dst pointer's pts.

Definition at line 444 of file FlowSensitive.cpp.

{
    double start = stat->getClk();
    NodeID srcID = addr->getSrcNodeID();
    if (isFieldInsensitive(srcID))
        srcID = getFIObjVar(srcID);
    bool changed = addPts(addr->getDstNodeID(), srcID);
    double end = stat->getClk();
    addrTime += (end - start) / TIMEINTERVAL;
    return changed;
}

◆ processCopy()

bool FlowSensitive::processCopy ( const CopySVFGNode * copy )

protectedvirtual

Process copy node

Definition at line 461 of file FlowSensitive.cpp.

{
    double start = stat->getClk();
    bool changed = unionPts(copy->getDstNodeID(), copy->getSrcNodeID());
    double end = stat->getClk();
    copyTime += (end - start) / TIMEINTERVAL;
    return changed;
}

◆ processGep()

bool FlowSensitive::processGep ( const GepSVFGNode * edge )

protectedvirtual

Process gep node

Definition at line 494 of file FlowSensitive.cpp.

{
    double start = stat->getClk();
    bool changed = false;
    const PointsTo& srcPts = getPts(edge->getSrcNodeID());
 
    PointsTo tmpDstPts;
    const GepStmt* gepStmt = SVFUtil::cast<GepStmt>(edge->getSVFStmt());
    if (gepStmt->isVariantFieldGep())
    {
        for (NodeID o : srcPts)
        {
            if (isBlkObjOrConstantObj(o))
            {
                tmpDstPts.set(o);
                continue;
            }
 
            setObjFieldInsensitive(o);
            tmpDstPts.set(getFIObjVar(o));
        }
    }
    else
    {
        for (NodeID o : srcPts)
        {
            if (isBlkObjOrConstantObj(o) || isFieldInsensitive(o))
            {
                tmpDstPts.set(o);
                continue;
            }
 
            NodeID fieldSrcPtdNode = getGepObjVar(o, gepStmt->getAccessPath().getConstantStructFldIdx());
            tmpDstPts.set(fieldSrcPtdNode);
        }
    }
 
    if (unionPts(edge->getDstNodeID(), tmpDstPts))
        changed = true;
 
    double end = stat->getClk();
    gepTime += (end - start) / TIMEINTERVAL;
    return changed;
}

◆ processLoad()

bool FlowSensitive::processLoad ( const LoadSVFGNode * load )

protectedvirtual

Process load node

Foreach node \in src pts(dst) = union pts(node)

If the ptd is a field-insensitive node, we should also get all field nodes' points-to sets and pass them to pagDst.

Reimplemented in SVF::VersionedFlowSensitive.

Definition at line 546 of file FlowSensitive.cpp.

{
    double start = stat->getClk();
    bool changed = false;
 
    NodeID dstVar = load->getDstNodeID();
 
    const PointsTo& srcPts = getPts(load->getSrcNodeID());
 
    // p = *q, the type of p must be a pointer
    if(load->getDstNode()->isPointer())
    {
        for (PointsTo::iterator ptdIt = srcPts.begin(); ptdIt != srcPts.end(); ++ptdIt)
        {
            NodeID ptd = *ptdIt;
 
            if (pag->isConstantObj(ptd))
                continue;
 
            if (unionPtsFromIn(load, ptd, dstVar))
                changed = true;
 
            if (isFieldInsensitive(ptd))
            {
                const NodeBS& allFields = getAllFieldsObjVars(ptd);
                for (NodeBS::iterator fieldIt = allFields.begin(), fieldEit = allFields.end();
                        fieldIt != fieldEit; ++fieldIt)
                {
                    if (unionPtsFromIn(load, *fieldIt, dstVar))
                        changed = true;
                }
            }
        }
    }
    double end = stat->getClk();
    loadTime += (end - start) / TIMEINTERVAL;
    return changed;
}

◆ processNode()

void FlowSensitive::processNode ( NodeID nodeId )

overrideprotectedvirtual

Handle various constraints.

Process each SVFG node

Reimplemented from SVF::WPASolver< GraphType >.

Reimplemented in SVF::VersionedFlowSensitive.

Definition at line 215 of file FlowSensitive.cpp.

{
    SVFGNode* node = svfg->getSVFGNode(nodeId);
    if (processSVFGNode(node))
        propagate(&node);
 
    clearAllDFOutVarFlag(node);
}

◆ processPhi()

bool FlowSensitive::processPhi ( const PHISVFGNode * phi )

protectedvirtual

Process mssa phi node

Definition at line 473 of file FlowSensitive.cpp.

{
    double start = stat->getClk();
    bool changed = false;
    NodeID pagDst = phi->getRes()->getId();
    for (PHISVFGNode::OPVers::const_iterator it = phi->opVerBegin(), eit = phi->opVerEnd(); it != eit; ++it)
    {
        NodeID src = it->second->getId();
        const PointsTo& srcPts = getPts(src);
        if (unionPts(pagDst, srcPts))
            changed = true;
    }
 
    double end = stat->getClk();
    phiTime += (end - start) / TIMEINTERVAL;
    return changed;
}

◆ processStore()

bool FlowSensitive::processStore ( const StoreSVFGNode * store )

protectedvirtual

Process store node

foreach node \in dst pts(node) = union pts(src)

STORE statement can only be processed if the pointer on the LHS points to something. If we handle STORE with an empty points-to set, the OUT set will be updated from IN set. Then if LHS pointer points-to one target and it has been identified as a strong update, we can't remove those points-to information computed before this strong update from the OUT set.

check if this is a strong updates store

Reimplemented in SVF::VersionedFlowSensitive.

Definition at line 593 of file FlowSensitive.cpp.

{
 
    const PointsTo & dstPts = getPts(store->getDstNodeID());
 
    if (dstPts.empty())
        return false;
 
    double start = stat->getClk();
    bool changed = false;
 
    // *p = q, the type of q must be a pointer
    if(getPts(store->getSrcNodeID()).empty() == false && store->getSrcNode()->isPointer())
    {
        for (PointsTo::iterator it = dstPts.begin(), eit = dstPts.end(); it != eit; ++it)
        {
            NodeID ptd = *it;
 
            if (pag->isConstantObj(ptd))
                continue;
 
            if (unionPtsFromTop(store, store->getSrcNodeID(), ptd))
                changed = true;
        }
    }
 
    double end = stat->getClk();
    storeTime += (end - start) / TIMEINTERVAL;
 
    double updateStart = stat->getClk();
    // also merge the DFInSet to DFOutSet.
    NodeID singleton;
    bool isSU = isStrongUpdate(store, singleton);
    if (isSU)
    {
        svfgHasSU.set(store->getId());
        if (strongUpdateOutFromIn(store, singleton))
            changed = true;
    }
    else
    {
        svfgHasSU.reset(store->getId());
        if (weakUpdateOutFromIn(store))
            changed = true;
    }
    double updateEnd = stat->getClk();
    updateTime += (updateEnd - updateStart) / TIMEINTERVAL;
 
    return changed;
}

◆ processSVFGNode()

bool FlowSensitive::processSVFGNode ( SVFGNode * node )

protected

Process each SVFG node

Definition at line 227 of file FlowSensitive.cpp.

{
    double start = stat->getClk();
    bool changed = false;
    if (AddrSVFGNode* addr = SVFUtil::dyn_cast<AddrSVFGNode>(node))
    {
        numOfProcessedAddr++;
        if (processAddr(addr))
            changed = true;
    }
    else if (CopySVFGNode* copy = SVFUtil::dyn_cast<CopySVFGNode>(node))
    {
        numOfProcessedCopy++;
        if (processCopy(copy))
            changed = true;
    }
    else if (GepSVFGNode* gep = SVFUtil::dyn_cast<GepSVFGNode>(node))
    {
        numOfProcessedGep++;
        if(processGep(gep))
            changed = true;
    }
    else if (LoadSVFGNode* load = SVFUtil::dyn_cast<LoadSVFGNode>(node))
    {
        numOfProcessedLoad++;
        if(processLoad(load))
            changed = true;
    }
    else if (StoreSVFGNode* store = SVFUtil::dyn_cast<StoreSVFGNode>(node))
    {
        numOfProcessedStore++;
        if (processStore(store))
            changed = true;
    }
    else if (PHISVFGNode* phi = SVFUtil::dyn_cast<PHISVFGNode>(node))
    {
        numOfProcessedPhi++;
        if (processPhi(phi))
            changed = true;
    }
    else if (SVFUtil::isa<MSSAPHISVFGNode, FormalINSVFGNode,
             FormalOUTSVFGNode, ActualINSVFGNode,
             ActualOUTSVFGNode>(node))
    {
        numOfProcessedMSSANode++;
        changed = true;
    }
    else if (SVFUtil::isa<ActualParmSVFGNode, FormalParmSVFGNode,
             ActualRetSVFGNode, FormalRetSVFGNode,
             NullPtrSVFGNode>(node))
    {
        changed = true;
    }
    else if (SVFUtil::isa<CmpVFGNode, BinaryOPVFGNode>(node) ||
             SVFUtil::dyn_cast<UnaryOPVFGNode>(node))
    {
    }
    else
    {
        assert(false && "unexpected kind of SVFG nodes");
    }
 
    double end = stat->getClk();
    processTime += (end - start) / TIMEINTERVAL;
 
    return changed;
}

◆ propagateFromAPToFP()

bool FlowSensitive::propagateFromAPToFP	(	const ActualParmSVFGNode *	ap,
		const SVFGNode *	dst
	)

protectedvirtual

Propagate points-to information from an actual-param to a formal-param. Not necessary if SVFGOPT is used instead of original SVFG.

Propagate points-to information from actual-param to formal-param. Not necessary if SVFGOPT is used instead of original SVFG.

Definition at line 354 of file FlowSensitive.cpp.

{
    const FormalParmSVFGNode* fp = SVFUtil::dyn_cast<FormalParmSVFGNode>(dst);
    assert(fp && "expecting a formal param node");
 
    NodeID pagDst = fp->getParam()->getId();
    const PointsTo &srcCPts = getPts(ap->getParam()->getId());
    bool changed = unionPts(pagDst, srcCPts);
 
    return changed;
}

◆ propagateFromFRToAR()

bool FlowSensitive::propagateFromFRToAR	(	const FormalRetSVFGNode *	fr,
		const SVFGNode *	dst
	)

protectedvirtual

Propagate points-to information from a formal-ret to an actual-ret. Not necessary if SVFGOPT is used instead of original SVFG.

Propagate points-to information from formal-ret to actual-ret. Not necessary if SVFGOPT is used instead of original SVFG.

Definition at line 370 of file FlowSensitive.cpp.

{
    const ActualRetSVFGNode* ar = SVFUtil::dyn_cast<ActualRetSVFGNode>(dst);
    assert(ar && "expecting an actual return node");
 
    NodeID pagDst = ar->getRev()->getId();
    const PointsTo & srcCPts = getPts(fr->getRet()->getId());
    bool changed = unionPts(pagDst, srcCPts);
 
    return changed;
}

◆ propAlongDirectEdge()

bool FlowSensitive::propAlongDirectEdge ( const DirectSVFGEdge * edge )

protectedvirtual

Propagate points-to information along a DIRECT SVFG edge.

Propagate points-to information along DIRECT SVFG edge.

Definition at line 323 of file FlowSensitive.cpp.

{
    double start = stat->getClk();
    bool changed = false;
 
    SVFGNode* src = edge->getSrcNode();
    SVFGNode* dst = edge->getDstNode();
    // If this is an actual-param or formal-ret, top-level pointer's pts must be
    // propagated from src to dst.
    if (ActualParmSVFGNode* ap = SVFUtil::dyn_cast<ActualParmSVFGNode>(src))
        changed = propagateFromAPToFP(ap, dst);
    else if (FormalRetSVFGNode* fp = SVFUtil::dyn_cast<FormalRetSVFGNode>(src))
        changed = propagateFromFRToAR(fp, dst);
    else
    {
        // Direct SVFG edge links between def and use of a top-level pointer.
        // There's no points-to information propagated along direct edge.
        // Since the top-level pointer's value has been changed at src node,
        // return TRUE to put dst node into the work list.
        changed = true;
    }
 
    double end = stat->getClk();
    directPropaTime += (end - start) / TIMEINTERVAL;
    return changed;
}

◆ propAlongIndirectEdge()

bool FlowSensitive::propAlongIndirectEdge ( const IndirectSVFGEdge * edge )

protectedvirtual

Propagate points-to information along an INDIRECT SVFG edge.

Propagate points-to information along INDIRECT SVFG edge.

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

Reimplemented in SVF::VersionedFlowSensitive.

Definition at line 385 of file FlowSensitive.cpp.

{
    double start = stat->getClk();
 
    SVFGNode* src = edge->getSrcNode();
    SVFGNode* dst = edge->getDstNode();
 
    bool changed = false;
 
    // Get points-to targets may be used by next SVFG node.
    // Propagate points-to set for node used in dst.
    const NodeBS& pts = edge->getPointsTo();
    for (NodeBS::iterator ptdIt = pts.begin(), ptdEit = pts.end(); ptdIt != ptdEit; ++ptdIt)
    {
        NodeID ptd = *ptdIt;
 
        if (propVarPtsFromSrcToDst(ptd, src, dst))
            changed = true;
 
        if (isFieldInsensitive(ptd))
        {
            const NodeBS& allFields = getAllFieldsObjVars(ptd);
            for (NodeBS::iterator fieldIt = allFields.begin(), fieldEit = allFields.end();
                    fieldIt != fieldEit; ++fieldIt)
            {
                if (propVarPtsFromSrcToDst(*fieldIt, src, dst))
                    changed = true;
            }
        }
    }
 
    double end = stat->getClk();
    indirectPropaTime += (end - start) / TIMEINTERVAL;
    return changed;
}

◆ propDFInToIn()

virtual bool SVF::FlowSensitive::propDFInToIn	(	const SVFGNode *	srcStmt,
		NodeID	srcVar,
		const SVFGNode *	dstStmt,
		NodeID	dstVar
	)

inlineprotectedvirtual

Definition at line 180 of file FlowSensitive.h.

    {
        return getDFPTDataTy()->updateAllDFInFromIn(srcStmt->getId(), srcVar, dstStmt->getId(),dstVar);
    }

◆ propDFOutToIn()

virtual bool SVF::FlowSensitive::propDFOutToIn	(	const SVFGNode *	srcStmt,
		NodeID	srcVar,
		const SVFGNode *	dstStmt,
		NodeID	dstVar
	)

inlineprotectedvirtual

Definition at line 176 of file FlowSensitive.h.

    {
        return getDFPTDataTy()->updateAllDFInFromOut(srcStmt->getId(), srcVar, dstStmt->getId(),dstVar);
    }

◆ propFromSrcToDst()

bool FlowSensitive::propFromSrcToDst ( SVFGEdge * edge )

overrideprotected

Propagation.

Propagate points-to information from an edge's src node to its dst node.

Propagate points-to information from source to destination node Union dfOutput of src to dfInput of dst. Only propagate points-to set of node which exists on the SVFG edge.

propagation along direct edge will always return TRUE.
propagation along indirect edge will return TRUE if destination node's IN set has been updated.

Definition at line 303 of file FlowSensitive.cpp.

{
    double start = stat->getClk();
    bool changed = false;
 
    if (DirectSVFGEdge* dirEdge = SVFUtil::dyn_cast<DirectSVFGEdge>(edge))
        changed = propAlongDirectEdge(dirEdge);
    else if (IndirectSVFGEdge* indEdge = SVFUtil::dyn_cast<IndirectSVFGEdge>(edge))
        changed = propAlongIndirectEdge(indEdge);
    else
        assert(false && "new kind of svfg edge?");
 
    double end = stat->getClk();
    propagationTime += (end - start) /TIMEINTERVAL;
    return changed;
}

◆ propVarPtsAfterCGUpdated()

bool FlowSensitive::propVarPtsAfterCGUpdated	(	NodeID	var,
		const SVFGNode *	src,
		const SVFGNode *	dst
	)

protected

Propagation between newly connected SVFG nodes during updateCallGraph. Can only be used during updateCallGraph.

Propagate points-to information of a certain variable from src to dst.

Definition at line 807 of file FlowSensitive.cpp.

{
    if (SVFUtil::isa<StoreSVFGNode>(src))
    {
        if (propDFOutToIn(src, var, dst, var))
            return true;
    }
    else
    {
        if (propDFInToIn(src, var, dst, var))
            return true;
    }
    return false;
}

◆ propVarPtsFromSrcToDst()

bool FlowSensitive::propVarPtsFromSrcToDst	(	NodeID	var,
		const SVFGNode *	src,
		const SVFGNode *	dst
	)

protectedvirtual

Propagate points-to information of a certain variable from src to dst.

Definition at line 425 of file FlowSensitive.cpp.

{
    bool changed = false;
    if (SVFUtil::isa<StoreSVFGNode>(src))
    {
        if (updateInFromOut(src, var, dst, var))
            changed = true;
    }
    else
    {
        if (updateInFromIn(src, var, dst, var))
            changed = true;
    }
    return changed;
}

◆ PTAName()

const std::string SVF::FlowSensitive::PTAName ( ) const

inlineoverridevirtual

Get PTA name.

Reimplemented from SVF::PointerAnalysis.

Reimplemented in SVF::VersionedFlowSensitive.

Definition at line 116 of file FlowSensitive.h.

    {
        return "FlowSensitive";
    }

◆ readPtsFromFile()

void FlowSensitive::readPtsFromFile ( const std::string & filename )

virtual

Initialization for the Solver

Load the pts from file

finalize the analysis

Reimplemented in SVF::VersionedFlowSensitive.

Definition at line 148 of file FlowSensitive.cpp.

{
    initialize();
    if(!filename.empty())
        this->readFromFile(filename);
    finalize();
}

◆ releaseFSWPA()

static void SVF::FlowSensitive::releaseFSWPA ( )

inlinestatic

Release flow-sensitive pointer analysis.

Definition at line 89 of file FlowSensitive.h.

    {
        fspta = nullptr;
    }

◆ runOnModule()

virtual bool SVF::FlowSensitive::runOnModule ( )

inlinevirtual

We start from here.

Definition at line 95 of file FlowSensitive.h.

    {
        return false;
    }

◆ SCCDetect()

NodeStack & FlowSensitive::SCCDetect ( )

overrideprotectedvirtual

SCC detection.

SCC detection

Reimplemented from SVF::WPAFSSolver< GraphType >.

Definition at line 203 of file FlowSensitive.cpp.

{
    double start = stat->getClk();
    NodeStack& nodeStack = WPASVFGFSSolver::SCCDetect();
    double end = stat->getClk();
    sccTime += (end - start) / TIMEINTERVAL;
    return nodeStack;
}

◆ solveAndwritePtsToFile()

void FlowSensitive::solveAndwritePtsToFile ( const std::string & filename )

virtual

Start analysis

Initialization for the Solver

finalize the analysis

Reimplemented in SVF::VersionedFlowSensitive.

Definition at line 111 of file FlowSensitive.cpp.

{
    initialize();
    if(!filename.empty())
        writeObjVarToFile(filename);
    solveConstraints();
    if(!filename.empty())
        writeToFile(filename);
    finalize();
}

◆ solveConstraints()

void FlowSensitive::solveConstraints ( )

virtual

Start solving constraints

Definition at line 76 of file FlowSensitive.cpp.

{
    bool limitTimerSet = SVFUtil::startAnalysisLimitTimer(Options::FsTimeLimit());
 
    double start = stat->getClk(true);
    DBOUT(DGENERAL, outs() << SVFUtil::pasMsg("Start Solving Constraints\n"));
 
    do
    {
        numOfIteration++;
 
        if(0 == numOfIteration % OnTheFlyIterBudgetForStat)
            dumpStat();
 
        callGraphSCC->find();
 
        initWorklist();
        solveWorklist();
    }
    while (updateCallGraph(getIndirectCallsites()));
 
    DBOUT(DGENERAL, outs() << SVFUtil::pasMsg("Finish Solving Constraints\n"));
 
    // Reset the time-up alarm; analysis is done.
    SVFUtil::stopAnalysisLimitTimer(limitTimerSet);
 
    double end = stat->getClk(true);
    solveTime += (end - start) / TIMEINTERVAL;
 
}

◆ strongUpdateOutFromIn()

virtual bool SVF::FlowSensitive::strongUpdateOutFromIn	(	const SVFGNode *	node,
		NodeID	singleton
	)

inlineprotectedvirtual

Handle strong updates.

Definition at line 165 of file FlowSensitive.h.

    {
        return getDFPTDataTy()->updateAllDFOutFromIn(node->getId(),singleton,true);
    }

◆ svfgStat()

void SVF::FlowSensitive::svfgStat ( )

protected

◆ unionPtsFromIn()

virtual bool SVF::FlowSensitive::unionPtsFromIn	(	const SVFGNode *	stmt,
		NodeID	srcVar,
		NodeID	dstVar
	)

inlineprotectedvirtual

Definition at line 201 of file FlowSensitive.h.

    {
        return getDFPTDataTy()->updateTLVPts(stmt->getId(),srcVar,dstVar);
    }

◆ unionPtsFromTop()

virtual bool SVF::FlowSensitive::unionPtsFromTop	(	const SVFGNode *	stmt,
		NodeID	srcVar,
		NodeID	dstVar
	)

inlineprotectedvirtual

Definition at line 205 of file FlowSensitive.h.

    {
        return getDFPTDataTy()->updateATVPts(srcVar,stmt->getId(),dstVar);
    }

◆ updateCallGraph()

bool FlowSensitive::updateCallGraph ( const CallSiteToFunPtrMap & callsites )

overrideprotectedvirtual

Update call graph.

Update call graph

Reimplemented from SVF::BVDataPTAImpl.

Definition at line 684 of file FlowSensitive.cpp.

{
    double start = stat->getClk();
    CallEdgeMap newEdges;
    onTheFlyCallGraphSolve(callsites, newEdges);
 
    // Bound the new edges by the Andersen's call graph.
    // TODO: we want this to be an assertion eventually.
    const CallEdgeMap &andersCallEdgeMap = ander->getIndCallMap();
    for (typename CallEdgeMap::value_type &csfs : newEdges)
    {
        const CallICFGNode *potentialCallSite = csfs.first;
        FunctionSet &potentialFunctionSet = csfs.second;
 
        // Check this callsite even calls anything per Andersen's.
        typename CallEdgeMap::const_iterator andersFunctionSetIt
            = andersCallEdgeMap.find(potentialCallSite);
        if (andersFunctionSetIt == andersCallEdgeMap.end())
        {
            potentialFunctionSet.clear();
        }
 
        const FunctionSet &andersFunctionSet = andersFunctionSetIt->second;
        for (FunctionSet::iterator potentialFunctionIt = potentialFunctionSet.begin();
                potentialFunctionIt != potentialFunctionSet.end(); )
        {
            const FunObjVar *potentialFunction = *potentialFunctionIt;
            if (andersFunctionSet.find(potentialFunction) == andersFunctionSet.end())
            {
                // potentialFunction is not in the Andersen's call graph -- remove it.
                potentialFunctionIt = potentialFunctionSet.erase(potentialFunctionIt);
            }
            else
            {
                // potentialFunction is in the Andersen's call graph -- keep it..
                ++potentialFunctionIt;
            }
        }
    }
 
    SVFGEdgeSetTy svfgEdges;
    connectCallerAndCallee(newEdges, svfgEdges);
 
    updateConnectedNodes(svfgEdges);
 
    double end = stat->getClk();
    updateCallGraphTime += (end - start) / TIMEINTERVAL;
    return (!newEdges.empty());
}

◆ updateConnectedNodes()

void FlowSensitive::updateConnectedNodes ( const SVFGEdgeSetTy & edges )

protectedvirtual

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 in SVF::VersionedFlowSensitive.

Definition at line 757 of file FlowSensitive.cpp.

{
    for (const SVFGEdge* edge : edges)
    {
        SVFGNode* dstNode = edge->getDstNode();
        if (SVFUtil::isa<PHISVFGNode>(dstNode))
        {
            pushIntoWorklist(dstNode->getId());
        }
        else if (SVFUtil::isa<FormalINSVFGNode, ActualOUTSVFGNode>(dstNode))
        {
            bool changed = false;
 
            SVFGNode* srcNode = edge->getSrcNode();
 
            const NodeBS& pts = SVFUtil::cast<IndirectSVFGEdge>(edge)->getPointsTo();
            for (NodeBS::iterator ptdIt = pts.begin(), ptdEit = pts.end(); ptdIt != ptdEit; ++ptdIt)
            {
                NodeID ptd = *ptdIt;
 
                if (propVarPtsAfterCGUpdated(ptd, srcNode, dstNode))
                    changed = true;
 
                if (isFieldInsensitive(ptd))
                {
                    const NodeBS& allFields = getAllFieldsObjVars(ptd);
                    for (NodeBS::iterator fieldIt = allFields.begin(), fieldEit = allFields.end();
                            fieldIt != fieldEit; ++fieldIt)
                    {
                        if (propVarPtsAfterCGUpdated(*fieldIt, srcNode, dstNode))
                            changed = true;
                    }
                }
            }
 
            if (changed)
                pushIntoWorklist(dstNode->getId());
        }
    }
}

◆ updateInFromIn()

virtual bool SVF::FlowSensitive::updateInFromIn	(	const SVFGNode *	srcStmt,
		NodeID	srcVar,
		const SVFGNode *	dstStmt,
		NodeID	dstVar
	)

inlineprotectedvirtual

Definition at line 192 of file FlowSensitive.h.

    {
        return getDFPTDataTy()->updateDFInFromIn(srcStmt->getId(),srcVar, dstStmt->getId(),dstVar);
    }

◆ updateInFromOut()

virtual bool SVF::FlowSensitive::updateInFromOut	(	const SVFGNode *	srcStmt,
		NodeID	srcVar,
		const SVFGNode *	dstStmt,
		NodeID	dstVar
	)

inlineprotectedvirtual

Definition at line 196 of file FlowSensitive.h.

    {
        return getDFPTDataTy()->updateDFInFromOut(srcStmt->getId(),srcVar, dstStmt->getId(),dstVar);
    }

◆ updateOutFromIn()

bool SVF::FlowSensitive::updateOutFromIn	(	const SVFGNode *	srcStmt,
		NodeID	srcVar,
		const SVFGNode *	dstStmt,
		NodeID	dstVar
	)

inlineprotected

Update data-flow points-to data.

Definition at line 188 of file FlowSensitive.h.

    {
        return getDFPTDataTy()->updateDFOutFromIn(srcStmt->getId(),srcVar, dstStmt->getId(),dstVar);
    }

◆ weakUpdateOutFromIn()

virtual bool SVF::FlowSensitive::weakUpdateOutFromIn ( const SVFGNode * node )

inlineprotectedvirtual

Handle weak updates.

Definition at line 160 of file FlowSensitive.h.

    {
        return getDFPTDataTy()->updateAllDFOutFromIn(node->getId(),0,false);
    }

Friends And Related Symbol Documentation

◆ FlowSensitiveStat

friend class FlowSensitiveStat

friend

Definition at line 50 of file FlowSensitive.h.

Member Data Documentation

◆ addrTime

double SVF::FlowSensitive::addrTime

protected

time of handling address edges

Definition at line 306 of file FlowSensitive.h.

◆ ander

AndersenWaveDiff* SVF::FlowSensitive::ander

protected

Definition at line 278 of file FlowSensitive.h.

◆ candidateMappings

std::vector<std::pair<hclust_fast_methods, std::vector<NodeID> > > SVF::FlowSensitive::candidateMappings

protected

Save candidate mappings for evaluation's sake.

Definition at line 281 of file FlowSensitive.h.

◆ copyTime

double SVF::FlowSensitive::copyTime

protected

time of handling copy edges

Definition at line 307 of file FlowSensitive.h.

◆ directPropaTime

double SVF::FlowSensitive::directPropaTime

protected

time of points-to propagation of address-taken objects

Definition at line 303 of file FlowSensitive.h.

◆ fspta

std::unique_ptr< FlowSensitive > FlowSensitive::fspta

staticprotected

Definition at line 276 of file FlowSensitive.h.

◆ gepTime

double SVF::FlowSensitive::gepTime

protected

time of handling gep edges

Definition at line 308 of file FlowSensitive.h.

◆ indirectPropaTime

double SVF::FlowSensitive::indirectPropaTime

protected

time of points-to propagation of top-level pointers

Definition at line 304 of file FlowSensitive.h.

◆ loadTime

double SVF::FlowSensitive::loadTime

protected

time of load edges

Definition at line 309 of file FlowSensitive.h.

◆ maxSCCSize

u32_t SVF::FlowSensitive::maxSCCSize

protected

Number of processed mssa node.

Definition at line 295 of file FlowSensitive.h.

◆ memSSA

SVFGBuilder SVF::FlowSensitive::memSSA

protected

Definition at line 277 of file FlowSensitive.h.

◆ numOfNodesInSCC

u32_t SVF::FlowSensitive::numOfNodesInSCC

protected

Definition at line 297 of file FlowSensitive.h.

◆ numOfProcessedActualParam

u32_t SVF::FlowSensitive::numOfProcessedActualParam

protected

Number of processed Store node.

Definition at line 291 of file FlowSensitive.h.

◆ numOfProcessedAddr

u32_t SVF::FlowSensitive::numOfProcessedAddr

protected

Statistics.

Definition at line 285 of file FlowSensitive.h.

◆ numOfProcessedCopy

u32_t SVF::FlowSensitive::numOfProcessedCopy

protected

Number of processed Addr node.

Definition at line 286 of file FlowSensitive.h.

◆ numOfProcessedFormalRet

u32_t SVF::FlowSensitive::numOfProcessedFormalRet

protected

Number of processed actual param node.

Definition at line 292 of file FlowSensitive.h.

◆ numOfProcessedGep

u32_t SVF::FlowSensitive::numOfProcessedGep

protected

Number of processed Copy node.

Definition at line 287 of file FlowSensitive.h.

◆ numOfProcessedLoad

u32_t SVF::FlowSensitive::numOfProcessedLoad

protected

Number of processed Phi node.

Definition at line 289 of file FlowSensitive.h.

◆ numOfProcessedMSSANode

u32_t SVF::FlowSensitive::numOfProcessedMSSANode

protected

Number of processed formal ret node.

Definition at line 293 of file FlowSensitive.h.

◆ numOfProcessedPhi

u32_t SVF::FlowSensitive::numOfProcessedPhi

protected

Number of processed Gep node.

Definition at line 288 of file FlowSensitive.h.

◆ numOfProcessedStore

u32_t SVF::FlowSensitive::numOfProcessedStore

protected

Number of processed Load node.

Definition at line 290 of file FlowSensitive.h.

◆ numOfSCC

u32_t SVF::FlowSensitive::numOfSCC

protected

Definition at line 296 of file FlowSensitive.h.

◆ phiTime

double SVF::FlowSensitive::phiTime

protected

time of phi nodes.

Definition at line 311 of file FlowSensitive.h.

◆ processTime

double SVF::FlowSensitive::processTime

protected

time of processNode.

Definition at line 301 of file FlowSensitive.h.

◆ propagationTime

double SVF::FlowSensitive::propagationTime

protected

time of points-to propagation.

Definition at line 302 of file FlowSensitive.h.

◆ sccTime

double SVF::FlowSensitive::sccTime

protected

time of SCC detection.

Definition at line 300 of file FlowSensitive.h.

◆ solveTime

double SVF::FlowSensitive::solveTime

protected

time of solve.

Definition at line 299 of file FlowSensitive.h.

◆ storeTime

double SVF::FlowSensitive::storeTime

protected

time of store edges

Definition at line 310 of file FlowSensitive.h.

◆ svfg

SVFG* SVF::FlowSensitive::svfg

protected

Definition at line 244 of file FlowSensitive.h.

◆ svfgHasSU

NodeBS SVF::FlowSensitive::svfgHasSU

protected

Definition at line 314 of file FlowSensitive.h.

◆ updateCallGraphTime

double SVF::FlowSensitive::updateCallGraphTime

protected

time of updating call graph

Definition at line 312 of file FlowSensitive.h.

◆ updateTime

double SVF::FlowSensitive::updateTime

protected

time of strong/weak updates.

Definition at line 305 of file FlowSensitive.h.

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

/home/runner/work/SVF/SVF/svf/include/WPA/FlowSensitive.h
/home/runner/work/SVF/SVF/svf/lib/WPA/FlowSensitive.cpp

Public Types

Public Member Functions

Static Public Member Functions

Protected Types

Protected Member Functions

Protected Attributes

Static Protected Attributes

Friends

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ DFInOutMap

◆ MutDFPTDataTy

◆ PtsMap

◆ SVFGEdgeSetTy

Constructor & Destructor Documentation

◆ FlowSensitive()

◆ ~FlowSensitive()

Member Function Documentation

◆ analyze()

◆ classof() [1/2]

◆ classof() [2/2]

◆ clearAllDFOutVarFlag()

◆ cluster()

◆ connectCallerAndCallee()

◆ countAliases()

◆ createFSWPA()

◆ finalize()

◆ getDFInPtsSet()

◆ getDFInputMap()

◆ getDFOutPtsSet()

◆ getDFOutputMap()

◆ getSVFG()

◆ initialize()

◆ isStrongUpdate()

◆ plainMap()

◆ processAddr()

◆ processCopy()

◆ processGep()

◆ processLoad()

◆ processNode()

◆ processPhi()

◆ processStore()

◆ processSVFGNode()

◆ propagateFromAPToFP()

◆ propagateFromFRToAR()

◆ propAlongDirectEdge()

◆ propAlongIndirectEdge()

◆ propDFInToIn()

◆ propDFOutToIn()

◆ propFromSrcToDst()

◆ propVarPtsAfterCGUpdated()

◆ propVarPtsFromSrcToDst()

◆ PTAName()

◆ readPtsFromFile()

◆ releaseFSWPA()

◆ runOnModule()

◆ SCCDetect()

◆ solveAndwritePtsToFile()

◆ solveConstraints()

◆ strongUpdateOutFromIn()

◆ svfgStat()

◆ unionPtsFromIn()

◆ unionPtsFromTop()

◆ updateCallGraph()

◆ updateConnectedNodes()

◆ updateInFromIn()

◆ updateInFromOut()

◆ updateOutFromIn()

◆ weakUpdateOutFromIn()

Friends And Related Symbol Documentation

◆ FlowSensitiveStat

Member Data Documentation

◆ addrTime

◆ ander

◆ candidateMappings

◆ copyTime

◆ directPropaTime

◆ fspta

◆ gepTime