#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
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 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, 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
bool	mayAlias (const SVFVar V1, const SVFVar V2)
bool	mayAlias (NodeID node1, NodeID node2)
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	~PointerAnalysis ()
	Destructor.
virtual NodeBS	getMayAliases (NodeID node)
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
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_"
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 ()
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 ValVar *valVar) 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.
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 54 of file FlowDDA.h.

Member Typedef Documentation

◆ CallEdgeMap

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

Definition at line 59 of file FlowDDA.h.

◆ CallSiteSet

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

Definition at line 58 of file FlowDDA.h.

◆ FunctionSet

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

Definition at line 60 of file FlowDDA.h.

Constructor & Destructor Documentation

◆ FlowDDA()

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

inline

Constructor.

Definition at line 62 of file FlowDDA.h.

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

◆ ~FlowDDA()

virtual SVF::FlowDDA::~FlowDDA ( )

inlinevirtual

Destructor.

Definition at line 68 of file FlowDDA.h.

69 {

70 }

Member Function Documentation

◆ analyze()

virtual void SVF::FlowDDA::analyze ( )

inlineoverridevirtual

dummy analyze method

Implements SVF::PointerAnalysis.

Definition at line 72 of file FlowDDA.h.

72{}

◆ 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());
 
    const ValVar* node = getPAG()->getValVar(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 97 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 155 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 110 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 115 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 120 of file FlowDDA.h.

    {
        NodeID srcID = addr->getSrcNodeID();
        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 87 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->getSVFStmt());
            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 168 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 )

inlineoverride

Union pts.

Definition at line 162 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 136 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 174 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