#include <FlowDDA.h>

Inheritance diagram for SVF::FlowDDA:

Public Types
typedef BVDataPTAImpl::CallSiteSet	CallSiteSet

typedef BVDataPTAImpl::CallEdgeMap	CallEdgeMap

typedef BVDataPTAImpl::FunctionSet	FunctionSet

Public Types inherited from SVF::BVDataPTAImpl
enum	PTBackingType { Mutable , Persistent }
	How the PTData used is implemented. More...

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
enum	PTATY { Andersen_BASE , Andersen_WPA , AndersenSCD_WPA , AndersenSFR_WPA , AndersenWaveDiff_WPA , Steensgaard_WPA , CSCallString_WPA , CSSummary_WPA , FSDATAFLOW_WPA , FSSPARSE_WPA , VFS_WPA , FSCS_WPA , CFLFICI_WPA , CFLFSCI_WPA , CFLFSCS_WPA , TypeCPP_WPA , FieldS_DDA , FlowS_DDA , PathS_DDA , Cxt_DDA , Default_PTA }
	Pointer analysis type list. More...

enum	PTAImplTy { BaseImpl , BVDataImpl , CondImpl }
	Implementation type: BVDataPTAImpl or CondPTAImpl. More...

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 Types inherited from SVF::DDAVFSolver< NodeID, PointsTo, LocDPItem >
typedef SCCDetection< SVFG * >	SVFGSCC

typedef SCCDetection< CallGraph * >	CallGraphSCC

typedef CallGraphEdge::CallInstSet	CallInstSet

typedef SVFIR::CallSiteSet	CallSiteSet

typedef OrderedSet< LocDPItem >	DPTItemSet

typedef OrderedMap< LocDPItem, PointsTo >	DPImToCPtSetMap

typedef OrderedMap< LocDPItem, NodeID >	DPMToCVarMap

typedef OrderedMap< LocDPItem, LocDPItem >	DPMToDPMMap

typedef OrderedMap< NodeID, DPTItemSet >	LocToDPMVecMap

typedef OrderedSet< const SVFGEdge * >	ConstSVFGEdgeSet

typedef SVFGEdge::SVFGEdgeSetTy	SVFGEdgeSet

typedef OrderedMap< const SVFGNode *, DPTItemSet >	StoreToPMSetMap

Public Member Functions
	FlowDDA (SVFIR _pag, DDAClient client)
	Constructor.

virtual	~FlowDDA ()
	Destructor.

virtual void	analyze () override
	dummy analyze method

void	computeDDAPts (NodeID id) override
	Compute points-to set for all top variable.

void	handleOutOfBudgetDpm (const LocDPItem &dpm)
	Handle out-of-budget dpm.

virtual bool	handleBKCondition (LocDPItem &dpm, const SVFGEdge *edge) override
	Handle condition for flow analysis (backward analysis)

bool	testIndCallReachability (LocDPItem &dpm, const FunObjVar *callee, CallSiteID csId)
	refine indirect call edge

virtual void	initialize () override
	Initialization of the analysis.

virtual void	finalize () override
	Finalize analysis.

virtual bool	isHeapCondMemObj (const NodeID &var, const StoreSVFGNode *store) override

virtual PointsTo	getConservativeCPts (const LocDPItem &dpm) override
	Override parent method.

virtual NodeID	getPtrNodeID (const NodeID &var) const override
	Override parent method.

virtual void	handleAddr (PointsTo &pts, const LocDPItem &dpm, const AddrSVFGNode *addr) override
	Handle Address SVFGNode to add proper points-to.

virtual PointsTo	processGepPts (const GepSVFGNode *gep, const PointsTo &srcPts) override
	processGep node

virtual void	updateCallGraphAndSVFG (const LocDPItem &dpm, const CallICFGNode *cs, SVFGEdgeSet &svfgEdges) override
	Update call graph.

virtual const PointsTo &	getCachedTLPointsTo (const LocDPItem &dpm) override
	Override parent class functions to get/add cached points-to directly via PAGNode ID.

bool	unionDDAPts (LocDPItem dpm, const PointsTo &targetPts) override
	Union pts.

virtual const std::string	PTAName () const override
	Return PTA name.

Public Member Functions inherited from SVF::BVDataPTAImpl
	BVDataPTAImpl (SVFIR *pag, PointerAnalysis::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.

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

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	getBaseObjVar (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

Public Member Functions inherited from SVF::DDAVFSolver< NodeID, PointsTo, LocDPItem >
	DDAVFSolver ()
	Constructor.

virtual	~DDAVFSolver ()
	Destructor.

NodeBS &	getCandidateQueries ()
	Return candidate pointers for DDA.

virtual LocDPItem	getDPIm (const NodeID &var, const SVFGNode *loc) const
	Given CVar and location (SVFGNode) return a new DPItem.

virtual bool	unionDDAPts (PointsTo &pts, const PointsTo &targetPts)
	Union pts.

virtual void	addDDAPts (PointsTo &pts, const NodeID &var)
	Add pts.

SVFG *	getSVFG () const
	Return SVFG.

SVFGSCC *	getSVFGSCC () const
	Return SVFGSCC.

void	dumpCPtSet (const PointsTo &cpts) const

virtual const PointsTo &	findPT (const LocDPItem &dpm)
	Compute points-to.

Private Attributes
DDAClient *	_client
	DDA client.

Additional Inherited Members
Static Public Member Functions inherited from SVF::BVDataPTAImpl
static bool	classof (const PointerAnalysis *pta)

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 Member Functions inherited from SVF::BVDataPTAImpl
PTDataTy *	getPTDataTy () const
	Get points-to data structure.

virtual bool	updateCallGraph (const CallSiteToFunPtrMap &)
	Update callgraph. This should be implemented by its subclass.

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 Member Functions inherited from SVF::DDAVFSolver< NodeID, PointsTo, LocDPItem >
virtual void	handleSingleStatement (const LocDPItem &dpm, PointsTo &pts)
	Handle single statement.

void	reCompute (const LocDPItem &dpm)
	recompute points-to for value-flow cycles and indirect calls

void	reComputeForEdges (const LocDPItem &dpm, const SVFGEdgeSet &edgeSet, bool indirectCall=false)
	Traverse along out edges to find all nodes which may be affected by locDPM.

virtual void	buildSVFG (SVFIR *pag)
	Build SVFG.

virtual void	resetQuery ()
	Reset visited map for next points-to query.

void	OOBResetVisited ()
	Reset visited map if the current query is out-of-budget.

const SVFGNode *	getDefSVFGNode (const PAGNode *pagNode) const
	GetDefinition SVFG.

void	backtraceAlongIndirectVF (PointsTo &pts, const LocDPItem &oldDpm)
	Backward traverse along indirect value flows.

void	backtraceAlongDirectVF (PointsTo &pts, const LocDPItem &oldDpm)
	Backward traverse along direct value flows.

void	startNewPTCompFromLoadSrc (PointsTo &pts, const LocDPItem &oldDpm)

void	startNewPTCompFromStoreDst (PointsTo &pts, const LocDPItem &oldDpm)

void	backtraceToStoreSrc (PointsTo &pts, const LocDPItem &oldDpm)

virtual void	backwardPropDpm (PointsTo &pts, NodeID ptr, const LocDPItem &oldDpm, const SVFGEdge *edge)
	dpm transit during backward tracing

virtual bool	isMustAlias (const LocDPItem &, const LocDPItem &)
	whether load and store are aliased

virtual bool	isStrongUpdate (const PointsTo &dstCPSet, const StoreSVFGNode *store)
	Return TRUE if this is a strong update STORE statement.

virtual bool	isLocalCVarInRecursion (const NodeID &var) const
	Whether a local variable is in function recursions.

virtual bool	propagateViaObj (const NodeID &storeObj, const NodeID &loadObj)
	If the points-to contain the object obj, we could move forward along indirect value-flow edge.

void	resolveFunPtr (const LocDPItem &dpm)
	resolve function pointer

void	markbkVisited (const LocDPItem &dpm)
	Visited flags to avoid cycles.

bool	isbkVisited (const LocDPItem &dpm)

void	clearbkVisited (const LocDPItem &dpm)

virtual const PointsTo &	getCachedPointsTo (const LocDPItem &dpm)
	Points-to Caching for top-level pointers and address-taken objects.

virtual void	updateCachedPointsTo (const LocDPItem &dpm, const PointsTo &pts)

virtual const PointsTo &	getCachedADPointsTo (const LocDPItem &dpm)

bool	isTopLevelPtrStmt (const SVFGNode *stmt)
	Whether this is a top-level pointer statement.

virtual LocDPItem	getDPImWithOldCond (const LocDPItem &oldDpm, const NodeID &var, const SVFGNode *loc)
	Return dpm with old context and path conditions.

void	SVFGSCCDetection ()
	SVFG SCC detection.

NodeID	getSVFGSCCRepNode (NodeID id)
	Get SCC rep node of a SVFG node.

bool	isSVFGNodeInCycle (const SVFGNode *node)
	Return whether this SVFGNode is in cycle.

bool	edgeInSVFGSCC (const SVFGEdge *edge)
	Return TRUE if this edge is inside a SVFG SCC, i.e., src node and dst node are in the same SCC on the SVFG.

void	setCallGraph (CallGraph *cg)
	Set callgraph.

void	setCallGraphSCC (CallGraphSCC *scc)
	Set callgraphSCC.

bool	isArrayCondMemObj (const NodeID &var) const

bool	isFieldInsenCondMemObj (const NodeID &var) const

void	addLoadDpmAndCVar (const LocDPItem &dpm, const LocDPItem &loadDpm, const NodeID &loadVar)
	LoadDpm for must-alias analysis.

void	addLoadDpm (const LocDPItem &dpm, const LocDPItem &loadDpm)
	Note that simply use "dpmToloadDpmMap[dpm]=loadDpm", requires DPIm have a default constructor.

const LocDPItem &	getLoadDpm (const LocDPItem &dpm) const

void	addLoadCVar (const LocDPItem &dpm, const NodeID &loadVar)

const NodeID &	getLoadCVar (const LocDPItem &dpm) const

AndersenWaveDiff *	getAndersenAnalysis () const
	Return Andersen's analysis.

void	handleOutOfBudgetDpm (const LocDPItem &dpm)
	handle out-of-budget queries

bool	testOutOfBudget (const LocDPItem &dpm)

bool	isOutOfBudgetQuery () const

void	addOutOfBudgetDpm (const LocDPItem &dpm)

bool	isOutOfBudgetDpm (const LocDPItem &dpm) const

DDAStat *	setDDAStat (DDAStat *s)
	Set DDAStat.

void	addSUStat (const LocDPItem &dpm, const SVFGNode *node)
	stat strong updates num

void	rmSUStat (const LocDPItem &dpm, const SVFGNode *node)
	remove strong updates num if the dpm goes to weak updates branch

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.

Protected Attributes inherited from SVF::DDAVFSolver< NodeID, PointsTo, LocDPItem >
bool	outOfBudgetQuery
	Whether the current query is out of step limits.

SVFIR *	_pag
	SVFIR.

SVFG *	_svfg
	SVFG.

AndersenWaveDiff *	_ander
	Andersen's analysis.

NodeBS	candidateQueries
	candidate pointers;

CallGraph *	_callGraph
	PTACallGraph.

CallGraphSCC *	_callGraphSCC
	SCC for PTACallGraph.

SVFGSCC *	_svfgSCC
	SCC for SVFG.

DPTItemSet	backwardVisited
	visited map during backward traversing

DPImToCPtSetMap	dpmToTLCPtSetMap
	points-to caching map for top-level vars

DPImToCPtSetMap	dpmToADCPtSetMap
	points-to caching map for address-taken vars

LocToDPMVecMap	locToDpmSetMap
	map location to its dpms

DPMToDPMMap	dpmToloadDpmMap
	dpms at loads for may/must-alias analysis with stores

DPMToCVarMap	loadToPTCVarMap
	map a load dpm to its cvar pointed by its pointer operand

DPTItemSet	outOfBudgetDpms
	out of budget dpm set

StoreToPMSetMap	storeToDPMs
	map store to set of DPM which have been stong updated there

DDAStat *	ddaStat
	DDA stat.

SVFGBuilder	svfgBuilder
	SVFG Builder.

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

Detailed Description

Flow sensitive demand-driven analysis on value-flow graph

Definition at line 53 of file FlowDDA.h.

Member Typedef Documentation

◆ CallEdgeMap

typedef BVDataPTAImpl::CallEdgeMap SVF::FlowDDA::CallEdgeMap

Definition at line 58 of file FlowDDA.h.

◆ CallSiteSet

typedef BVDataPTAImpl::CallSiteSet SVF::FlowDDA::CallSiteSet

Definition at line 57 of file FlowDDA.h.

◆ FunctionSet

typedef BVDataPTAImpl::FunctionSet SVF::FlowDDA::FunctionSet

Definition at line 59 of file FlowDDA.h.

Constructor & Destructor Documentation

◆ FlowDDA()

SVF::FlowDDA::FlowDDA	(	SVFIR *	_pag,
		DDAClient *	client
	)

inline

Constructor.

Definition at line 61 of file FlowDDA.h.

                                           : BVDataPTAImpl(_pag, PointerAnalysis::FlowS_DDA),
        DDAVFSolver<NodeID,PointsTo,LocDPItem>(),
        _client(client)
    {
    }

◆ ~FlowDDA()

virtual SVF::FlowDDA::~FlowDDA ( )

inlinevirtual

Destructor.

Definition at line 67 of file FlowDDA.h.

68 {

69 }

Member Function Documentation

◆ analyze()

virtual void SVF::FlowDDA::analyze ( )

inlineoverridevirtual

dummy analyze method

Implements SVF::PointerAnalysis.

Definition at line 71 of file FlowDDA.h.

71{}

◆ computeDDAPts()

void FlowDDA::computeDDAPts ( NodeID id )

overridevirtual

Compute points-to set for all top variable.

Compute points-to set for queries

start DDA analysis

Reimplemented from SVF::PointerAnalysis.

Definition at line 43 of file FlowDDA.cpp.

{
    resetQuery();
    LocDPItem::setMaxBudget(Options::FlowBudget());
 
    PAGNode* node = getPAG()->getGNode(id);
    LocDPItem dpm = getDPIm(node->getId(),getDefSVFGNode(node));
 
    DOTIMESTAT(double start = DDAStat::getClk(true));
    const PointsTo& pts = findPT(dpm);
    DOTIMESTAT(ddaStat->_AnaTimePerQuery = DDAStat::getClk(true) - start);
    DOTIMESTAT(ddaStat->_TotalTimeOfQueries += ddaStat->_AnaTimePerQuery);
 
    if(isOutOfBudgetQuery() == false)
        unionPts(node->getId(),pts);
    else
        handleOutOfBudgetDpm(dpm);
 
    if(this->printStat())
        DOSTAT(stat->performStatPerQuery(node->getId()));
 
    DBOUT(DGENERAL,stat->printStatPerQuery(id,getPts(id)));
}

◆ finalize()

virtual void SVF::FlowDDA::finalize ( )

inlineoverridevirtual

Finalize analysis.

Reimplemented from SVF::BVDataPTAImpl.

Definition at line 96 of file FlowDDA.h.

    {
        BVDataPTAImpl::finalize();
    }

◆ getCachedTLPointsTo()

virtual const PointsTo & SVF::FlowDDA::getCachedTLPointsTo ( const LocDPItem & dpm )

inlineoverridevirtual

Override parent class functions to get/add cached points-to directly via PAGNode ID.

Reimplemented from SVF::DDAVFSolver< NodeID, PointsTo, LocDPItem >.

Definition at line 154 of file FlowDDA.h.

    {
        return getPts(dpm.getCurNodeID());
    }

◆ getConservativeCPts()

virtual PointsTo SVF::FlowDDA::getConservativeCPts ( const LocDPItem & dpm )

inlineoverridevirtual

Override parent method.

Implements SVF::DDAVFSolver< NodeID, PointsTo, LocDPItem >.

Definition at line 109 of file FlowDDA.h.

    {
        return getAndersenAnalysis()->getPts(dpm.getCurNodeID());
    }

◆ getPtrNodeID()

virtual NodeID SVF::FlowDDA::getPtrNodeID ( const NodeID & var ) const

inlineoverridevirtual

Override parent method.

Implements SVF::DDAVFSolver< NodeID, PointsTo, LocDPItem >.

Definition at line 114 of file FlowDDA.h.

    {
        return var;
    }

◆ handleAddr()

virtual void SVF::FlowDDA::handleAddr	(	PointsTo &	pts,
		const LocDPItem &	dpm,
		const AddrSVFGNode *	addr
	)

inlineoverridevirtual

Handle Address SVFGNode to add proper points-to.

whether this object is set field-insensitive during pre-analysis

Implements SVF::DDAVFSolver< NodeID, PointsTo, LocDPItem >.

Definition at line 119 of file FlowDDA.h.

    {
        NodeID srcID = addr->getPAGSrcNodeID();
        if (isFieldInsensitive(srcID))
            srcID = getFIObjVar(srcID);
 
        addDDAPts(pts,srcID);
        DBOUT(DDDA, SVFUtil::outs() << "\t add points-to target " << srcID << " to dpm ");
        DBOUT(DDDA, dpm.dump());
    }

◆ handleBKCondition()

bool FlowDDA::handleBKCondition	(	LocDPItem &	dpm,
		const SVFGEdge *	edge
	)

overridevirtual

Handle condition for flow analysis (backward analysis)

Reimplemented from SVF::DDAVFSolver< NodeID, PointsTo, LocDPItem >.

Definition at line 102 of file FlowDDA.cpp.

{
    _client->handleStatement(edge->getSrcNode(), dpm.getCurNodeID());
//    CallSiteID csId = 0;
//
//    if (edge->isCallVFGEdge()) {
//        /// we don't handle context in recursions, they treated as assignments
//        if (const CallDirSVFGEdge* callEdge = SVFUtil::dyn_cast<CallDirSVFGEdge>(edge))
//            csId = callEdge->getCallSiteId();
//        else
//            csId = SVFUtil::cast<CallIndSVFGEdge>(edge)->getCallSiteId();
//
//        const FunObjVar* callee = edge->getDstNode()->getBB()->getParent();
//        if(testIndCallReachability(dpm,callee,csId)==false){
//            return false;
//        }
//
//    }
//
//    else if (edge->isRetVFGEdge()) {
//        /// we don't handle context in recursions, they treated as assignments
//        if (const RetDirSVFGEdge* retEdge = SVFUtil::dyn_cast<RetDirSVFGEdge>(edge))
//            csId = retEdge->getCallSiteId();
//        else
//            csId = SVFUtil::cast<RetIndSVFGEdge>(edge)->getCallSiteId();
//
//        const FunObjVar* callee = edge->getSrcNode()->getBB()->getParent();
//        if(testIndCallReachability(dpm,callee,csId)==false){
//            return false;
//        }
//
//    }
 
    return true;
}

◆ handleOutOfBudgetDpm()

void FlowDDA::handleOutOfBudgetDpm ( const LocDPItem & dpm )

Handle out-of-budget dpm.

Handle out-of-budget dpm

Definition at line 72 of file FlowDDA.cpp.

{
    DBOUT(DGENERAL,outs() << "~~~Out of budget query, downgrade to andersen analysis \n");
    const PointsTo& anderPts = getAndersenAnalysis()->getPts(dpm.getCurNodeID());
    updateCachedPointsTo(dpm,anderPts);
    unionPts(dpm.getCurNodeID(),anderPts);
    addOutOfBudgetDpm(dpm);
}

◆ initialize()

virtual void SVF::FlowDDA::initialize ( )

inlineoverridevirtual

Initialization of the analysis.

Reimplemented from SVF::PointerAnalysis.

Definition at line 86 of file FlowDDA.h.

    {
        BVDataPTAImpl::initialize();
        buildSVFG(pag);
        setCallGraph(getCallGraph());
        setCallGraphSCC(getCallGraphSCC());
        stat = setDDAStat(new DDAStat(this));
    }

◆ isHeapCondMemObj()

bool FlowDDA::isHeapCondMemObj	(	const NodeID &	var,
		const StoreSVFGNode *	store
	)

overridevirtual

we exclude concrete heap here following the conditions: (1) local allocated heap and (2) not escaped to the scope outside the current function (3) not inside loop (4) not involved in recursion

Reimplemented from SVF::DDAVFSolver< NodeID, PointsTo, LocDPItem >.

Definition at line 177 of file FlowDDA.cpp.

{
    const BaseObjVar* pVar = _pag->getBaseObject(getPtrNodeID(var));
    if(pVar && SVFUtil::isa<HeapObjVar, DummyObjVar>(pVar))
    {
//        if(const Instruction* mallocSite = SVFUtil::dyn_cast<Instruction>(mem->getValue())) {
//            const FunObjVar* fun = mallocSite->getParent()->getParent();
//            const FunObjVar* curFun = store->getBB() ? store->getBB()->getParent() : nullptr;
//            if(fun!=curFun)
//                return true;
//            if(_callGraphSCC->isInCycle(_callGraph->getCallGraphNode(fun)->getId()))
//                return true;
//            if(_pag->getICFG()->isInLoop(mallocSite))
//                return true;
//
//            return false;
//        }
        return true;
    }
    return false;
}

◆ processGepPts()

PointsTo FlowDDA::processGepPts	(	const GepSVFGNode *	gep,
		const PointsTo &	srcPts
	)

overridevirtual

processGep node

Generate field objects for structs

Implements SVF::DDAVFSolver< NodeID, PointsTo, LocDPItem >.

Definition at line 141 of file FlowDDA.cpp.

{
    PointsTo tmpDstPts;
    for (PointsTo::iterator piter = srcPts.begin(); piter != srcPts.end(); ++piter)
    {
        NodeID ptd = *piter;
        if (isBlkObjOrConstantObj(ptd))
            tmpDstPts.set(ptd);
        else
        {
            const GepStmt* gepStmt = SVFUtil::cast<GepStmt>(gep->getPAGEdge());
            if (gepStmt->isVariantFieldGep())
            {
                setObjFieldInsensitive(ptd);
                tmpDstPts.set(getFIObjVar(ptd));
            }
            else
            {
                NodeID fieldSrcPtdNode = getGepObjVar(ptd, gepStmt->getAccessPath().getConstantStructFldIdx());
                tmpDstPts.set(fieldSrcPtdNode);
            }
        }
    }
    DBOUT(DDDA, outs() << "\t return created gep objs {");
    DBOUT(DDDA, SVFUtil::dumpSet(srcPts));
    DBOUT(DDDA, outs() << "} --> {");
    DBOUT(DDDA, SVFUtil::dumpSet(tmpDstPts));
    DBOUT(DDDA, outs() << "}\n");
    return tmpDstPts;
}

◆ PTAName()

virtual const std::string SVF::FlowDDA::PTAName ( ) const

inlineoverridevirtual

Return PTA name.

Reimplemented from SVF::PointerAnalysis.

Definition at line 167 of file FlowDDA.h.

    {
        return "FlowSensitive DDA";
    }

◆ testIndCallReachability()

bool FlowDDA::testIndCallReachability	(	LocDPItem &	dpm,
		const FunObjVar *	callee,
		CallSiteID	csId
	)

refine indirect call edge

Definition at line 81 of file FlowDDA.cpp.

{
 
    const CallICFGNode* cbn = getSVFG()->getCallSite(csId);
 
    if(getPAG()->isIndirectCallSites(cbn))
    {
        if(getCallGraph()->hasIndCSCallees(cbn))
        {
            const FunctionSet& funset = getCallGraph()->getIndCSCallees(cbn);
            if(funset.find(callee)!=funset.end())
                return true;
        }
 
        return false;
    }
    else    // if this is an direct call
        return true;
 
}

◆ unionDDAPts()

bool SVF::FlowDDA::unionDDAPts	(	LocDPItem	dpm,
		const PointsTo &	targetPts
	)

inlineoverridevirtual

Union pts.

Reimplemented from SVF::DDAVFSolver< NodeID, PointsTo, LocDPItem >.

Definition at line 161 of file FlowDDA.h.

    {
        if (isTopLevelPtrStmt(dpm.getLoc())) return unionPts(dpm.getCurNodeID(), targetPts);
        else return dpmToADCPtSetMap[dpm] |= targetPts;
    }

◆ updateCallGraphAndSVFG()

virtual void SVF::FlowDDA::updateCallGraphAndSVFG	(	const LocDPItem &	dpm,
		const CallICFGNode *	cs,
		SVFGEdgeSet &	svfgEdges
	)

inlineoverridevirtual

Update call graph.

Reimplemented from SVF::DDAVFSolver< NodeID, PointsTo, LocDPItem >.

Definition at line 135 of file FlowDDA.h.

    {
        CallEdgeMap newEdges;
        resolveIndCalls(cs, getCachedPointsTo(dpm), newEdges);
        for (CallEdgeMap::const_iterator iter = newEdges.begin(),eiter = newEdges.end(); iter != eiter; iter++)
        {
            const CallICFGNode* newcs = 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;
                getSVFG()->connectCallerAndCallee(newcs, func, svfgEdges);
            }
        }
    }

Member Data Documentation

◆ _client

DDAClient* SVF::FlowDDA::_client

private

DDA client.

Definition at line 173 of file FlowDDA.h.

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

/home/runner/work/SVF/SVF/svf/include/DDA/FlowDDA.h
/home/runner/work/SVF/SVF/svf/lib/DDA/FlowDDA.cpp

Public Types

Public Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ CallEdgeMap

◆ CallSiteSet

◆ FunctionSet

Constructor & Destructor Documentation

◆ FlowDDA()

◆ ~FlowDDA()

Member Function Documentation

◆ analyze()

◆ computeDDAPts()

◆ finalize()

◆ getCachedTLPointsTo()

◆ getConservativeCPts()

◆ getPtrNodeID()

◆ handleAddr()

◆ handleBKCondition()

◆ handleOutOfBudgetDpm()

◆ initialize()

◆ isHeapCondMemObj()

◆ processGepPts()

◆ PTAName()

◆ testIndCallReachability()

◆ unionDDAPts()

◆ updateCallGraphAndSVFG()

Member Data Documentation

◆ _client