#include <DDAVFSolver.h>

Public Types
typedef SCCDetection< SVFG * >	SVFGSCC

typedef SCCDetection< PTACallGraph * >	CallGraphSCC

typedef PTACallGraphEdge::CallInstSet	CallInstSet

typedef SVFIR::CallSiteSet	CallSiteSet

typedef OrderedSet< DPIm >	DPTItemSet

typedef OrderedMap< DPIm, CPtSet >	DPImToCPtSetMap

typedef OrderedMap< DPIm, CVar >	DPMToCVarMap

typedef OrderedMap< DPIm, DPIm >	DPMToDPMMap

typedef OrderedMap< NodeID, DPTItemSet >	LocToDPMVecMap

typedef OrderedSet< const SVFGEdge * >	ConstSVFGEdgeSet

typedef SVFGEdge::SVFGEdgeSetTy	SVFGEdgeSet

typedef OrderedMap< const SVFGNode *, DPTItemSet >	StoreToPMSetMap

Public Member Functions
	DDAVFSolver ()
	Constructor.

virtual	~DDAVFSolver ()
	Destructor.

NodeBS &	getCandidateQueries ()
	Return candidate pointers for DDA.

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

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

virtual bool	unionDDAPts (DPIm dpm, const CPtSet &targetPts)
	Union pts.

virtual void	addDDAPts (CPtSet &pts, const CVar &var)
	Add pts.

SVFG *	getSVFG () const
	Return SVFG.

SVFGSCC *	getSVFGSCC () const
	Return SVFGSCC.

void	dumpCPtSet (const CPtSet &cpts) const

virtual const CPtSet &	findPT (const DPIm &dpm)
	Compute points-to.

Protected Member Functions
virtual void	handleSingleStatement (const DPIm &dpm, CPtSet &pts)
	Handle single statement.

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

void	reComputeForEdges (const DPIm &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 (CPtSet &pts, const DPIm &oldDpm)
	Backward traverse along indirect value flows.

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

Friends
class	DDAStat

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;

PTACallGraph *	_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.

void	startNewPTCompFromLoadSrc (CPtSet &pts, const DPIm &oldDpm)

void	startNewPTCompFromStoreDst (CPtSet &pts, const DPIm &oldDpm)

void	backtraceToStoreSrc (CPtSet &pts, const DPIm &oldDpm)

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

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

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

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

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

void	resolveFunPtr (const DPIm &dpm)
	resolve function pointer

virtual NodeID	getPtrNodeID (const CVar &var) const =0
	Methods to be implemented in child class.

virtual CPtSet	processGepPts (const GepSVFGNode *gep, const CPtSet &srcPts)=0
	ProcessGep node to generate field object nodes of a struct.

virtual void	handleAddr (CPtSet &pts, const DPIm &dpm, const AddrSVFGNode *addr)=0
	Handle AddrSVFGNode to add proper points-to.

virtual CPtSet	getConservativeCPts (const DPIm &dpm)=0
	Get conservative points-to results when the query is out of budget.

virtual bool	handleBKCondition (DPIm &, const SVFGEdge *)
	Handle condition for context or path analysis (backward analysis)

virtual void	updateCallGraphAndSVFG (const DPIm &, const CallICFGNode *, SVFGEdgeSet &)
	Update call graph.

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

bool	isbkVisited (const DPIm &dpm)

void	clearbkVisited (const DPIm &dpm)

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

virtual void	updateCachedPointsTo (const DPIm &dpm, const CPtSet &pts)

virtual const CPtSet &	getCachedTLPointsTo (const DPIm &dpm)

virtual const CPtSet &	getCachedADPointsTo (const DPIm &dpm)

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

virtual DPIm	getDPImWithOldCond (const DPIm &oldDpm, const CVar &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 (PTACallGraph *cg)
	Set callgraph.

void	setCallGraphSCC (CallGraphSCC *scc)
	Set callgraphSCC.

virtual bool	isHeapCondMemObj (const CVar &var, const StoreSVFGNode *)
	Check heap and array object.

bool	isArrayCondMemObj (const CVar &var) const

bool	isFieldInsenCondMemObj (const CVar &var) const

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

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

const DPIm &	getLoadDpm (const DPIm &dpm) const

void	addLoadCVar (const DPIm &dpm, const CVar &loadVar)

const CVar &	getLoadCVar (const DPIm &dpm) const

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

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

bool	testOutOfBudget (const DPIm &dpm)

bool	isOutOfBudgetQuery () const

void	addOutOfBudgetDpm (const DPIm &dpm)

bool	isOutOfBudgetDpm (const DPIm &dpm) const

DDAStat *	setDDAStat (DDAStat *s)
	Set DDAStat.

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

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

const LocToDPMVecMap &	getLocToDPMVecMap () const
	Map a SVFGNode to its dpms for handling value-flow cycles.

const DPTItemSet &	getDpmSetAtLoc (const SVFGNode *loc)

void	addDpmToLoc (const DPIm &dpm)

void	removeDpmFromLoc (const DPIm &dpm)

Detailed Description

template<class CVar, class CPtSet, class DPIm>
class SVF::DDAVFSolver< CVar, CPtSet, DPIm >

Value-Flow Based Demand-Driven Points-to Analysis

Definition at line 47 of file DDAVFSolver.h.

Member Typedef Documentation

◆ CallGraphSCC

template<class CVar , class CPtSet , class DPIm >

typedef SCCDetection<PTACallGraph*> SVF::DDAVFSolver< CVar, CPtSet, DPIm >::CallGraphSCC

Definition at line 52 of file DDAVFSolver.h.

◆ CallInstSet

template<class CVar , class CPtSet , class DPIm >

typedef PTACallGraphEdge::CallInstSet SVF::DDAVFSolver< CVar, CPtSet, DPIm >::CallInstSet

Definition at line 53 of file DDAVFSolver.h.

◆ CallSiteSet

template<class CVar , class CPtSet , class DPIm >

typedef SVFIR::CallSiteSet SVF::DDAVFSolver< CVar, CPtSet, DPIm >::CallSiteSet

Definition at line 54 of file DDAVFSolver.h.

◆ ConstSVFGEdgeSet

template<class CVar , class CPtSet , class DPIm >

typedef OrderedSet<const SVFGEdge* > SVF::DDAVFSolver< CVar, CPtSet, DPIm >::ConstSVFGEdgeSet

Definition at line 60 of file DDAVFSolver.h.

◆ DPImToCPtSetMap

template<class CVar , class CPtSet , class DPIm >

typedef OrderedMap<DPIm, CPtSet> SVF::DDAVFSolver< CVar, CPtSet, DPIm >::DPImToCPtSetMap

Definition at line 56 of file DDAVFSolver.h.

◆ DPMToCVarMap

template<class CVar , class CPtSet , class DPIm >

typedef OrderedMap<DPIm,CVar> SVF::DDAVFSolver< CVar, CPtSet, DPIm >::DPMToCVarMap

Definition at line 57 of file DDAVFSolver.h.

◆ DPMToDPMMap

template<class CVar , class CPtSet , class DPIm >

typedef OrderedMap<DPIm,DPIm> SVF::DDAVFSolver< CVar, CPtSet, DPIm >::DPMToDPMMap

Definition at line 58 of file DDAVFSolver.h.

◆ DPTItemSet

template<class CVar , class CPtSet , class DPIm >

typedef OrderedSet<DPIm> SVF::DDAVFSolver< CVar, CPtSet, DPIm >::DPTItemSet

Definition at line 55 of file DDAVFSolver.h.

◆ LocToDPMVecMap

template<class CVar , class CPtSet , class DPIm >

typedef OrderedMap<NodeID, DPTItemSet> SVF::DDAVFSolver< CVar, CPtSet, DPIm >::LocToDPMVecMap

Definition at line 59 of file DDAVFSolver.h.

◆ StoreToPMSetMap

template<class CVar , class CPtSet , class DPIm >

typedef OrderedMap<const SVFGNode*, DPTItemSet> SVF::DDAVFSolver< CVar, CPtSet, DPIm >::StoreToPMSetMap

Definition at line 62 of file DDAVFSolver.h.

◆ SVFGEdgeSet

template<class CVar , class CPtSet , class DPIm >

typedef SVFGEdge::SVFGEdgeSetTy SVF::DDAVFSolver< CVar, CPtSet, DPIm >::SVFGEdgeSet

Definition at line 61 of file DDAVFSolver.h.

◆ SVFGSCC

template<class CVar , class CPtSet , class DPIm >

typedef SCCDetection<SVFG*> SVF::DDAVFSolver< CVar, CPtSet, DPIm >::SVFGSCC

Definition at line 51 of file DDAVFSolver.h.

Constructor & Destructor Documentation

◆ DDAVFSolver()

template<class CVar , class CPtSet , class DPIm >

SVF::DDAVFSolver< CVar, CPtSet, DPIm >::DDAVFSolver ( )

inline

Constructor.

Definition at line 65 of file DDAVFSolver.h.

                 : outOfBudgetQuery(false),_pag(nullptr),_svfg(nullptr),_ander(nullptr),_callGraph(nullptr), _callGraphSCC(nullptr), _svfgSCC(nullptr), ddaStat(nullptr)
    {
    }

◆ ~DDAVFSolver()

template<class CVar , class CPtSet , class DPIm >

virtual SVF::DDAVFSolver< CVar, CPtSet, DPIm >::~DDAVFSolver ( )

inlinevirtual

Destructor.

Definition at line 69 of file DDAVFSolver.h.

    {
        if(_ander != nullptr)
        {
            // AndersenWaveDiff::releaseAndersenWaveDiff();
            _ander = nullptr;
        }
 
        if (_svfg != nullptr)
        {
            // DDASVFGBuilder::releaseDDASVFG();
            _svfg = nullptr;
        }
 
        if (_svfgSCC != nullptr)
            delete _svfgSCC;
        _svfgSCC = nullptr;
 
        _callGraph = nullptr;
        _callGraphSCC = nullptr;
    }

Member Function Documentation

◆ addDDAPts()

template<class CVar , class CPtSet , class DPIm >

virtual void SVF::DDAVFSolver< CVar, CPtSet, DPIm >::addDDAPts	(	CPtSet &	pts,
		const CVar &	var
	)

inlinevirtual

Add pts.

Definition at line 113 of file DDAVFSolver.h.

    {
        pts.set(var);
    }

◆ addDpmToLoc()

template<class CVar , class CPtSet , class DPIm >

void SVF::DDAVFSolver< CVar, CPtSet, DPIm >::addDpmToLoc ( const DPIm & dpm )

inlineprivate

Definition at line 669 of file DDAVFSolver.h.

    {
        locToDpmSetMap[dpm.getLoc()->getId()].insert(dpm);
    }

◆ addLoadCVar()

template<class CVar , class CPtSet , class DPIm >

void SVF::DDAVFSolver< CVar, CPtSet, DPIm >::addLoadCVar	(	const DPIm &	dpm,
		const CVar &	loadVar
	)

inlineprotected

Definition at line 702 of file DDAVFSolver.h.

    {
        typename DPMToCVarMap::iterator it = loadToPTCVarMap.find(dpm);
        if(it!=loadToPTCVarMap.end())
            it->second = loadVar;
        else
            loadToPTCVarMap.insert(std::make_pair(dpm,loadVar));
    }

◆ addLoadDpm()

template<class CVar , class CPtSet , class DPIm >

void SVF::DDAVFSolver< CVar, CPtSet, DPIm >::addLoadDpm	(	const DPIm &	dpm,
		const DPIm &	loadDpm
	)

inlineprotected

Note that simply use "dpmToloadDpmMap[dpm]=loadDpm", requires DPIm have a default constructor.

Definition at line 688 of file DDAVFSolver.h.

    {
        typename DPMToDPMMap::iterator it = dpmToloadDpmMap.find(dpm);
        if(it!=dpmToloadDpmMap.end())
            it->second = loadDpm;
        else
            dpmToloadDpmMap.insert(std::make_pair(dpm,loadDpm));
    }

◆ addLoadDpmAndCVar()

template<class CVar , class CPtSet , class DPIm >

void SVF::DDAVFSolver< CVar, CPtSet, DPIm >::addLoadDpmAndCVar	(	const DPIm &	dpm,
		const DPIm &	loadDpm,
		const CVar &	loadVar
	)

inlineprotected

LoadDpm for must-alias analysis.

Definition at line 682 of file DDAVFSolver.h.

    {
        addLoadCVar(dpm,loadVar);
        addLoadDpm(dpm,loadDpm);
    }

◆ addOutOfBudgetDpm()

template<class CVar , class CPtSet , class DPIm >

void SVF::DDAVFSolver< CVar, CPtSet, DPIm >::addOutOfBudgetDpm ( const DPIm & dpm )

inlineprotected

Definition at line 737 of file DDAVFSolver.h.

    {
        outOfBudgetDpms.insert(dpm);
    }

◆ addSUStat()

template<class CVar , class CPtSet , class DPIm >

void SVF::DDAVFSolver< CVar, CPtSet, DPIm >::addSUStat	(	const DPIm &	dpm,
		const SVFGNode *	node
	)

inlineprotected

stat strong updates num

Definition at line 754 of file DDAVFSolver.h.

    {
        if (storeToDPMs[node].insert(dpm).second)
        {
            ddaStat->_NumOfStrongUpdates++;
            ddaStat->_StrongUpdateStores.set(node->getId());
        }
    }

◆ backtraceAlongDirectVF()

template<class CVar , class CPtSet , class DPIm >

void SVF::DDAVFSolver< CVar, CPtSet, DPIm >::backtraceAlongDirectVF	(	CPtSet &	pts,
		const DPIm &	oldDpm
	)

inlineprotected

Backward traverse along direct value flows.

Definition at line 374 of file DDAVFSolver.h.

    {
        const SVFGNode* node = oldDpm.getLoc();
        const SVFGEdgeSet edgeSet(node->getInEdges());
        for (SVFGNode::const_iterator it = edgeSet.begin(), eit = edgeSet.end(); it != eit; ++it)
        {
            if(const DirectSVFGEdge* dirEdge = SVFUtil::dyn_cast<DirectSVFGEdge>(*it))
            {
                DBOUT(DDDA, SVFUtil::outs() << "\t\t==backtrace directVF svfgNode " <<
                      dirEdge->getDstID() << " --> " << dirEdge->getSrcID() << "\n");
                const SVFGNode* srcNode = dirEdge->getSrcNode();
                backwardPropDpm(pts,getSVFG()->getLHSTopLevPtr(srcNode)->getId(),oldDpm,dirEdge);
            }
        }
    }

◆ backtraceAlongIndirectVF()

template<class CVar , class CPtSet , class DPIm >

void SVF::DDAVFSolver< CVar, CPtSet, DPIm >::backtraceAlongIndirectVF	(	CPtSet &	pts,
		const DPIm &	oldDpm
	)

inlineprotected

Backward traverse along indirect value flows.

Definition at line 352 of file DDAVFSolver.h.

    {
        const SVFGNode* node = oldDpm.getLoc();
        NodeID obj = oldDpm.getCurNodeID();
        if (_pag->isConstantObj(obj))
            return;
        const SVFGEdgeSet edgeSet(node->getInEdges());
        for (SVFGNode::const_iterator it = edgeSet.begin(), eit = edgeSet.end(); it != eit; ++it)
        {
            if(const IndirectSVFGEdge* indirEdge = SVFUtil::dyn_cast<IndirectSVFGEdge>(*it))
            {
                const NodeBS& guard = indirEdge->getPointsTo();
                if(guard.test(obj))
                {
                    DBOUT(DDDA, SVFUtil::outs() << "\t\t==backtrace indirectVF svfgNode " <<
                          indirEdge->getDstID() << " --> " << indirEdge->getSrcID() << "\n");
                    backwardPropDpm(pts,oldDpm.getCurNodeID(),oldDpm,indirEdge);
                }
            }
        }
    }

◆ backtraceToStoreSrc()

template<class CVar , class CPtSet , class DPIm >

void SVF::DDAVFSolver< CVar, CPtSet, DPIm >::backtraceToStoreSrc	(	CPtSet &	pts,
		const DPIm &	oldDpm
	)

inlineprotected

Definition at line 413 of file DDAVFSolver.h.

    {
        const StoreSVFGNode* store = SVFUtil::cast<StoreSVFGNode>(oldDpm.getLoc());
        const SVFGNode* storeSrc = getDefSVFGNode(store->getPAGSrcNode());
        DBOUT(DDDA, SVFUtil::outs() << "++backtrace to storeSrc from svfgNode " << getLoadDpm(oldDpm).getLoc()->getId() << " to "<<
              store->getId() << " to " << storeSrc->getId() <<"\n");
        const SVFGEdge* edge = getSVFG()->getIntraVFGEdge(storeSrc,store,SVFGEdge::IntraDirectVF);
        assert(edge && "Edge not found!!");
        backwardPropDpm(pts,store->getPAGSrcNodeID(),oldDpm,edge);
    }

◆ backwardPropDpm()

template<class CVar , class CPtSet , class DPIm >

virtual void SVF::DDAVFSolver< CVar, CPtSet, DPIm >::backwardPropDpm	(	CPtSet &	pts,
		NodeID	ptr,
		const DPIm &	oldDpm,
		const SVFGEdge *	edge
	)

inlineprotectedvirtual

dpm transit during backward tracing

handle context-/path- sensitivity

record the source of load dpm

handle out of budget case

Definition at line 426 of file DDAVFSolver.h.

    {
        DPIm dpm(oldDpm);
        dpm.setLocVar(edge->getSrcNode(),ptr);
        DOTIMESTAT(double start = DDAStat::getClk(true));
        if(handleBKCondition(dpm,edge)==false)
        {
            DOTIMESTAT(ddaStat->_TotalTimeOfBKCondition += DDAStat::getClk(true) - start);
            DBOUT(DDDA, SVFUtil::outs() << "\t!!! infeasible path svfgNode: " << edge->getDstID() << " --| " << edge->getSrcID() << "\n");
            DOSTAT(ddaStat->_NumOfInfeasiblePath++);
            return;
        }
 
        if(SVFUtil::isa<IndirectSVFGEdge>(edge))
            addLoadDpmAndCVar(dpm,getLoadDpm(oldDpm),getLoadCVar(oldDpm));
 
        DOSTAT(ddaStat->_NumOfDPM++);
        unionDDAPts(pts,findPT(dpm));
    }

◆ buildSVFG()

template<class CVar , class CPtSet , class DPIm >

virtual void SVF::DDAVFSolver< CVar, CPtSet, DPIm >::buildSVFG ( SVFIR * pag )

inlineprotectedvirtual

Build SVFG.

Definition at line 317 of file DDAVFSolver.h.

    {
        _ander = AndersenWaveDiff::createAndersenWaveDiff(pag);
        _svfg = svfgBuilder.buildPTROnlySVFG(_ander);
        _pag = _svfg->getPAG();
    }

◆ clearbkVisited()

template<class CVar , class CPtSet , class DPIm >

void SVF::DDAVFSolver< CVar, CPtSet, DPIm >::clearbkVisited ( const DPIm & dpm )

inlineprotected

Definition at line 549 of file DDAVFSolver.h.

    {
        assert(backwardVisited.find(dpm)!=backwardVisited.end() && "dpm not found!");
        backwardVisited.erase(dpm);
    }

◆ dumpCPtSet()

template<class CVar , class CPtSet , class DPIm >

void SVF::DDAVFSolver< CVar, CPtSet, DPIm >::dumpCPtSet ( const CPtSet & cpts ) const

inline

Definition at line 128 of file DDAVFSolver.h.

    {
        SVFUtil::outs() << "{";
        for(typename CPtSet::iterator it = cpts.begin(), eit = cpts.end(); it!=eit; ++it)
        {
            SVFUtil::outs() << (*it) << " ";
        }
        SVFUtil::outs() << "}\n";
    }

◆ edgeInSVFGSCC()

template<class CVar , class CPtSet , class DPIm >

bool SVF::DDAVFSolver< CVar, CPtSet, DPIm >::edgeInSVFGSCC ( const SVFGEdge * edge )

inlineprotected

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.

Definition at line 624 of file DDAVFSolver.h.

    {
        return (getSVFGSCCRepNode(edge->getSrcID()) == getSVFGSCCRepNode(edge->getDstID()));
    }

◆ findPT()

template<class CVar , class CPtSet , class DPIm >

virtual const CPtSet & SVF::DDAVFSolver< CVar, CPtSet, DPIm >::findPT ( const DPIm & dpm )

inlinevirtual

Compute points-to.

Add successors of current stmt if its pts has been changed.

Definition at line 138 of file DDAVFSolver.h.

    {
 
        if(isbkVisited(dpm))
        {
            const CPtSet& cpts = getCachedPointsTo(dpm);
            DBOUT(DDDA, SVFUtil::outs() << "\t already backward visited dpm: ");
            DBOUT(DDDA, dpm.dump());
            DBOUT(DDDA, SVFUtil::outs() << "\t return points-to: ");
            DBOUT(DDDA, dumpCPtSet(cpts));
            return cpts;
        }
 
        DBOUT(DDDA, SVFUtil::outs() << "\t backward visit dpm: ");
        DBOUT(DDDA, dpm.dump());
        markbkVisited(dpm);
        addDpmToLoc(dpm);
 
        if(testOutOfBudget(dpm) == false)
        {
 
            CPtSet pts;
            handleSingleStatement(dpm, pts);
 
            updateCachedPointsTo(dpm, pts);
        }
        return getCachedPointsTo(dpm);
    }

◆ getAndersenAnalysis()

template<class CVar , class CPtSet , class DPIm >

AndersenWaveDiff * SVF::DDAVFSolver< CVar, CPtSet, DPIm >::getAndersenAnalysis ( ) const

inlineprotected

Return Andersen's analysis.

Definition at line 718 of file DDAVFSolver.h.

    {
        return _ander;
    }

◆ getCachedADPointsTo()

template<class CVar , class CPtSet , class DPIm >

virtual const CPtSet & SVF::DDAVFSolver< CVar, CPtSet, DPIm >::getCachedADPointsTo ( const DPIm & dpm )

inlineprotectedvirtual

Definition at line 578 of file DDAVFSolver.h.

    {
        return dpmToADCPtSetMap[dpm];
    }

◆ getCachedPointsTo()

template<class CVar , class CPtSet , class DPIm >

virtual const CPtSet & SVF::DDAVFSolver< CVar, CPtSet, DPIm >::getCachedPointsTo ( const DPIm & dpm )

inlineprotectedvirtual

Points-to Caching for top-level pointers and address-taken objects.

Definition at line 558 of file DDAVFSolver.h.

    {
        if (isTopLevelPtrStmt(dpm.getLoc()))
            return getCachedTLPointsTo(dpm);
        else
            return getCachedADPointsTo(dpm);
    }

◆ getCachedTLPointsTo()

template<class CVar , class CPtSet , class DPIm >

virtual const CPtSet & SVF::DDAVFSolver< CVar, CPtSet, DPIm >::getCachedTLPointsTo ( const DPIm & dpm )

inlineprotectedvirtual

Reimplemented in SVF::FlowDDA.

Definition at line 574 of file DDAVFSolver.h.

    {
        return dpmToTLCPtSetMap[dpm];
    }

◆ getCandidateQueries()

template<class CVar , class CPtSet , class DPIm >

NodeBS & SVF::DDAVFSolver< CVar, CPtSet, DPIm >::getCandidateQueries ( )

inline

Return candidate pointers for DDA.

Definition at line 91 of file DDAVFSolver.h.

    {
        return candidateQueries;
    }

◆ getConservativeCPts()

template<class CVar , class CPtSet , class DPIm >

virtual CPtSet SVF::DDAVFSolver< CVar, CPtSet, DPIm >::getConservativeCPts ( const DPIm & dpm )

protectedpure virtual

Get conservative points-to results when the query is out of budget.

Implemented in SVF::ContextDDA, and SVF::FlowDDA.

◆ getDefSVFGNode()

template<class CVar , class CPtSet , class DPIm >

const SVFGNode * SVF::DDAVFSolver< CVar, CPtSet, DPIm >::getDefSVFGNode ( const PAGNode * pagNode ) const

inlineprotected

GetDefinition SVFG.

Definition at line 347 of file DDAVFSolver.h.

    {
        return getSVFG()->getDefSVFGNode(pagNode);
    }

◆ getDPIm()

template<class CVar , class CPtSet , class DPIm >

virtual DPIm SVF::DDAVFSolver< CVar, CPtSet, DPIm >::getDPIm	(	const CVar &	var,
		const SVFGNode *	loc
	)		const

inlinevirtual

Given CVar and location (SVFGNode) return a new DPItem.

Definition at line 96 of file DDAVFSolver.h.

    {
        DPIm dpm(var,loc);
        return dpm;
    }

◆ getDPImWithOldCond()

template<class CVar , class CPtSet , class DPIm >

virtual DPIm SVF::DDAVFSolver< CVar, CPtSet, DPIm >::getDPImWithOldCond	(	const DPIm &	oldDpm,
		const CVar &	var,
		const SVFGNode *	loc
	)

inlineprotectedvirtual

Return dpm with old context and path conditions.

Definition at line 590 of file DDAVFSolver.h.

    {
        DPIm dpm(oldDpm);
        dpm.setLocVar(loc,getPtrNodeID(var));
 
        if(SVFUtil::isa<StoreSVFGNode>(loc))
            addLoadDpmAndCVar(dpm,getLoadDpm(oldDpm),var);
 
        if(SVFUtil::isa<LoadSVFGNode>(loc))
            addLoadDpmAndCVar(dpm,oldDpm,var);
 
        DOSTAT(ddaStat->_NumOfDPM++);
        return dpm;
    }

◆ getDpmSetAtLoc()

template<class CVar , class CPtSet , class DPIm >

const DPTItemSet & SVF::DDAVFSolver< CVar, CPtSet, DPIm >::getDpmSetAtLoc ( const SVFGNode * loc )

inlineprivate

Definition at line 665 of file DDAVFSolver.h.

    {
        return locToDpmSetMap[loc->getId()];
    }

◆ getLoadCVar()

template<class CVar , class CPtSet , class DPIm >

const CVar & SVF::DDAVFSolver< CVar, CPtSet, DPIm >::getLoadCVar ( const DPIm & dpm ) const

inlineprotected

Definition at line 710 of file DDAVFSolver.h.

    {
        typename DPMToCVarMap::const_iterator it = loadToPTCVarMap.find(dpm);
        assert(it!=loadToPTCVarMap.end() && "not found??");
        return it->second;
    }

◆ getLoadDpm()

template<class CVar , class CPtSet , class DPIm >

const DPIm & SVF::DDAVFSolver< CVar, CPtSet, DPIm >::getLoadDpm ( const DPIm & dpm ) const

inlineprotected

Definition at line 696 of file DDAVFSolver.h.

    {
        typename DPMToDPMMap::const_iterator it = dpmToloadDpmMap.find(dpm);
        assert(it!=dpmToloadDpmMap.end() && "not found??");
        return it->second;
    }

◆ getLocToDPMVecMap()

template<class CVar , class CPtSet , class DPIm >

const LocToDPMVecMap & SVF::DDAVFSolver< CVar, CPtSet, DPIm >::getLocToDPMVecMap ( ) const

inlineprivate

Map a SVFGNode to its dpms for handling value-flow cycles.

Definition at line 661 of file DDAVFSolver.h.

    {
        return locToDpmSetMap;
    }

◆ getPtrNodeID()

template<class CVar , class CPtSet , class DPIm >

virtual NodeID SVF::DDAVFSolver< CVar, CPtSet, DPIm >::getPtrNodeID ( const CVar & var ) const

protectedpure virtual

Methods to be implemented in child class.

Get variable ID (PAGNodeID) according to CVar

Implemented in SVF::ContextDDA, and SVF::FlowDDA.

◆ getSVFG()

template<class CVar , class CPtSet , class DPIm >

SVFG * SVF::DDAVFSolver< CVar, CPtSet, DPIm >::getSVFG ( ) const

inline

Return SVFG.

Definition at line 118 of file DDAVFSolver.h.

    {
        return _svfg;
    }

◆ getSVFGSCC()

template<class CVar , class CPtSet , class DPIm >

SVFGSCC * SVF::DDAVFSolver< CVar, CPtSet, DPIm >::getSVFGSCC ( ) const

inline

Return SVFGSCC.

Definition at line 123 of file DDAVFSolver.h.

    {
        return _svfgSCC;
    }

◆ getSVFGSCCRepNode()

template<class CVar , class CPtSet , class DPIm >

NodeID SVF::DDAVFSolver< CVar, CPtSet, DPIm >::getSVFGSCCRepNode ( NodeID id )

inlineprotected

Get SCC rep node of a SVFG node.

Definition at line 614 of file DDAVFSolver.h.

    {
        return _svfgSCC->repNode(id);
    }

◆ handleAddr()

template<class CVar , class CPtSet , class DPIm >

virtual void SVF::DDAVFSolver< CVar, CPtSet, DPIm >::handleAddr	(	CPtSet &	pts,
		const DPIm &	dpm,
		const AddrSVFGNode *	addr
	)

protectedpure virtual

Handle AddrSVFGNode to add proper points-to.

Implemented in SVF::ContextDDA, and SVF::FlowDDA.

◆ handleBKCondition()

template<class CVar , class CPtSet , class DPIm >

virtual bool SVF::DDAVFSolver< CVar, CPtSet, DPIm >::handleBKCondition	(	DPIm &	,
		const SVFGEdge *
	)

inlineprotectedvirtual

Handle condition for context or path analysis (backward analysis)

Reimplemented in SVF::ContextDDA, and SVF::FlowDDA.

Definition at line 531 of file DDAVFSolver.h.

    {
        return true;
    }

◆ handleOutOfBudgetDpm()

template<class CVar , class CPtSet , class DPIm >

void SVF::DDAVFSolver< CVar, CPtSet, DPIm >::handleOutOfBudgetDpm ( const DPIm & dpm )

inlineprotected

handle out-of-budget queries

Handle out-of-budget dpm

Definition at line 725 of file DDAVFSolver.h.

725{}

◆ handleSingleStatement()

template<class CVar , class CPtSet , class DPIm >

virtual void SVF::DDAVFSolver< CVar, CPtSet, DPIm >::handleSingleStatement	(	const DPIm &	dpm,
		CPtSet &	pts
	)

inlineprotectedvirtual

Handle single statement.

resolve function pointer first at indirect callsite

Definition at line 170 of file DDAVFSolver.h.

    {
        resolveFunPtr(dpm);
 
        const SVFGNode* node = dpm.getLoc();
        if(SVFUtil::isa<AddrSVFGNode>(node))
        {
            handleAddr(pts,dpm,SVFUtil::cast<AddrSVFGNode>(node));
        }
        else if (SVFUtil::isa<CopySVFGNode, PHISVFGNode, ActualParmSVFGNode,
                 FormalParmSVFGNode, ActualRetSVFGNode,
                 FormalRetSVFGNode, NullPtrSVFGNode>(node))
        {
            backtraceAlongDirectVF(pts,dpm);
        }
        else if(SVFUtil::isa<GepSVFGNode>(node))
        {
            CPtSet gepPts;
            backtraceAlongDirectVF(gepPts,dpm);
            unionDDAPts(pts, processGepPts(SVFUtil::cast<GepSVFGNode>(node),gepPts));
        }
        else if(const LoadSVFGNode* load = SVFUtil::dyn_cast<LoadSVFGNode>(node))
        {
            if(load->getPAGDstNode()->isPointer() == false)
                return;
 
            CPtSet loadpts;
            startNewPTCompFromLoadSrc(loadpts,dpm);
            for(typename CPtSet::iterator it = loadpts.begin(), eit = loadpts.end(); it!=eit; ++it)
            {
                backtraceAlongIndirectVF(pts,getDPImWithOldCond(dpm,*it,load));
            }
        }
        else if(const StoreSVFGNode* store = SVFUtil::dyn_cast<StoreSVFGNode>(node))
        {
            if(store->getPAGSrcNode()->isPointer() == false)
                return;
 
            if(isMustAlias(getLoadDpm(dpm),dpm))
            {
                DBOUT(DDDA, SVFUtil::outs() << "+++must alias for load and store:");
                DBOUT(DDDA, getLoadDpm(dpm).dump());
                DBOUT(DDDA, dpm.dump());
                DBOUT(DDDA, SVFUtil::outs() << "+++\n");
                DOSTAT(ddaStat->_NumOfMustAliases++);
                backtraceToStoreSrc(pts,dpm);
            }
            else
            {
                CPtSet storepts;
                startNewPTCompFromStoreDst(storepts,dpm);
                for(typename CPtSet::iterator it = storepts.begin(), eit = storepts.end(); it!=eit; ++it)
                {
                    if(propagateViaObj(*it,getLoadCVar(dpm)))
                    {
                        backtraceToStoreSrc(pts,getDPImWithOldCond(dpm,*it,store));
 
                        if(isStrongUpdate(storepts,store))
                        {
                            DBOUT(DDDA, SVFUtil::outs() << "backward strong update for obj " << dpm.getCurNodeID() << "\n");
                            DOSTAT(addSUStat(dpm,store);)
                        }
                        else
                        {
                            DOSTAT(rmSUStat(dpm,store);)
                            backtraceAlongIndirectVF(pts,getDPImWithOldCond(dpm,*it,store));
                        }
                    }
                    else
                    {
                        backtraceAlongIndirectVF(pts,dpm);
                    }
                }
            }
        }
        else if(SVFUtil::isa<MRSVFGNode>(node))
        {
            backtraceAlongIndirectVF(pts,dpm);
        }
        else
            assert(false && "unexpected kind of SVFG nodes");
    }

◆ isArrayCondMemObj()

template<class CVar , class CPtSet , class DPIm >

bool SVF::DDAVFSolver< CVar, CPtSet, DPIm >::isArrayCondMemObj ( const CVar & var ) const

inlineprotected

Definition at line 646 of file DDAVFSolver.h.

    {
        const MemObj* mem = _pag->getObject(getPtrNodeID(var));
        assert(mem && "memory object is null??");
        return mem->isArray();
    }

◆ isbkVisited()

template<class CVar , class CPtSet , class DPIm >

bool SVF::DDAVFSolver< CVar, CPtSet, DPIm >::isbkVisited ( const DPIm & dpm )

inlineprotected

Definition at line 545 of file DDAVFSolver.h.

    {
        return backwardVisited.find(dpm)!=backwardVisited.end();
    }

◆ isFieldInsenCondMemObj()

template<class CVar , class CPtSet , class DPIm >

bool SVF::DDAVFSolver< CVar, CPtSet, DPIm >::isFieldInsenCondMemObj ( const CVar & var ) const

inlineprotected

Definition at line 652 of file DDAVFSolver.h.

    {
        const MemObj* mem =  _pag->getBaseObj(getPtrNodeID(var));
        return mem->isFieldInsensitive();
    }

◆ isHeapCondMemObj()

template<class CVar , class CPtSet , class DPIm >

virtual bool SVF::DDAVFSolver< CVar, CPtSet, DPIm >::isHeapCondMemObj	(	const CVar &	var,
		const StoreSVFGNode *
	)

inlineprotectedvirtual

Check heap and array object.

Reimplemented in SVF::ContextDDA, and SVF::FlowDDA.

Definition at line 640 of file DDAVFSolver.h.

    {
        const BaseObjVar* pVar = _pag->getBaseObject(getPtrNodeID(var));
        return pVar && SVFUtil::isa<HeapObjVar, DummyObjVar>(pVar);
    }

◆ isLocalCVarInRecursion()

template<class CVar , class CPtSet , class DPIm >

virtual bool SVF::DDAVFSolver< CVar, CPtSet, DPIm >::isLocalCVarInRecursion ( const CVar & var ) const

inlineprotectedvirtual

Whether a local variable is in function recursions.

Definition at line 471 of file DDAVFSolver.h.

    {
        NodeID id = getPtrNodeID(var);
        const BaseObjVar* baseObj = _pag->getBaseObject(id);
        assert(baseObj && "base object is null??");
        const MemObj* obj = _pag->getObject(id);
        assert(obj && "object not found!!");
        if(SVFUtil::isa<StackObjVar>(baseObj))
        {
            if(const SVFFunction* svffun = _pag->getGNode(id)->getFunction())
            {
                return _callGraphSCC->isInCycle(_callGraph->getCallGraphNode(svffun)->getId());
            }
        }
        return false;
    }

◆ isMustAlias()

template<class CVar , class CPtSet , class DPIm >

virtual bool SVF::DDAVFSolver< CVar, CPtSet, DPIm >::isMustAlias	(	const DPIm &	,
		const DPIm &
	)

inlineprotectedvirtual

whether load and store are aliased

Definition at line 449 of file DDAVFSolver.h.

    {
        return false;
    }

◆ isOutOfBudgetDpm()

template<class CVar , class CPtSet , class DPIm >

bool SVF::DDAVFSolver< CVar, CPtSet, DPIm >::isOutOfBudgetDpm ( const DPIm & dpm ) const

inlineprotected

Definition at line 741 of file DDAVFSolver.h.

    {
        return outOfBudgetDpms.find(dpm) != outOfBudgetDpms.end();
    }

◆ isOutOfBudgetQuery()

template<class CVar , class CPtSet , class DPIm >

bool SVF::DDAVFSolver< CVar, CPtSet, DPIm >::isOutOfBudgetQuery ( ) const

inlineprotected

Definition at line 733 of file DDAVFSolver.h.

    {
        return outOfBudgetQuery;
    }

◆ isStrongUpdate()

template<class CVar , class CPtSet , class DPIm >

virtual bool SVF::DDAVFSolver< CVar, CPtSet, DPIm >::isStrongUpdate	(	const CPtSet &	dstCPSet,
		const StoreSVFGNode *	store
	)

inlineprotectedvirtual

Return TRUE if this is a strong update STORE statement.

Find the unique element in cpts

Definition at line 454 of file DDAVFSolver.h.

    {
        if (dstCPSet.count() == 1)
        {
            typename CPtSet::iterator it = dstCPSet.begin();
            const CVar& var = *it;
            // Strong update can be made if this points-to target is not heap, array or field-insensitive.
            if (!isHeapCondMemObj(var,store) && !isArrayCondMemObj(var)
                    && !isFieldInsenCondMemObj(var) && !isLocalCVarInRecursion(var))
            {
                return true;
            }
        }
        return false;
    }

◆ isSVFGNodeInCycle()

template<class CVar , class CPtSet , class DPIm >

bool SVF::DDAVFSolver< CVar, CPtSet, DPIm >::isSVFGNodeInCycle ( const SVFGNode * node )

inlineprotected

Return whether this SVFGNode is in cycle.

Definition at line 619 of file DDAVFSolver.h.

    {
        return _svfgSCC->isInCycle(node->getId());
    }

◆ isTopLevelPtrStmt()

template<class CVar , class CPtSet , class DPIm >

bool SVF::DDAVFSolver< CVar, CPtSet, DPIm >::isTopLevelPtrStmt ( const SVFGNode * stmt )

inlineprotected

Whether this is a top-level pointer statement.

Definition at line 585 of file DDAVFSolver.h.

    {
        return !SVFUtil::isa<StoreSVFGNode, MRSVFGNode>(stmt);
    }

◆ markbkVisited()

template<class CVar , class CPtSet , class DPIm >

void SVF::DDAVFSolver< CVar, CPtSet, DPIm >::markbkVisited ( const DPIm & dpm )

inlineprotected

Visited flags to avoid cycles.

Definition at line 541 of file DDAVFSolver.h.

    {
        backwardVisited.insert(dpm);
    }

◆ OOBResetVisited()

template<class CVar , class CPtSet , class DPIm >

void SVF::DDAVFSolver< CVar, CPtSet, DPIm >::OOBResetVisited ( )

inlineprotected

Reset visited map if the current query is out-of-budget.

Definition at line 336 of file DDAVFSolver.h.

    {
        for(typename LocToDPMVecMap::const_iterator it = locToDpmSetMap.begin(),eit = locToDpmSetMap.end(); it!=eit; ++it)
        {
            DPTItemSet dpmSet(it->second.begin(), it->second.end());
            for(typename DPTItemSet::const_iterator dit = dpmSet.begin(),deit=dpmSet.end(); dit!=deit; ++dit)
                if(isOutOfBudgetDpm(*dit)==false)
                    clearbkVisited(*dit);
        }
    }

◆ processGepPts()

template<class CVar , class CPtSet , class DPIm >

virtual CPtSet SVF::DDAVFSolver< CVar, CPtSet, DPIm >::processGepPts	(	const GepSVFGNode *	gep,
		const CPtSet &	srcPts
	)

protectedpure virtual

ProcessGep node to generate field object nodes of a struct.

Implemented in SVF::ContextDDA, and SVF::FlowDDA.

◆ propagateViaObj()

template<class CVar , class CPtSet , class DPIm >

virtual bool SVF::DDAVFSolver< CVar, CPtSet, DPIm >::propagateViaObj	(	const CVar &	storeObj,
		const CVar &	loadObj
	)

inlineprotectedvirtual

If the points-to contain the object obj, we could move forward along indirect value-flow edge.

Reimplemented in SVF::ContextDDA.

Definition at line 489 of file DDAVFSolver.h.

    {
        return getPtrNodeID(storeObj) == getPtrNodeID(loadObj);
    }

◆ reCompute()

template<class CVar , class CPtSet , class DPIm >

void SVF::DDAVFSolver< CVar, CPtSet, DPIm >::reCompute ( const DPIm & dpm )

inlineprotected

recompute points-to for value-flow cycles and indirect calls

re-compute due to indirect calls

callgraph scc detection for local variable in recursion

re-compute for transitive closures

Definition at line 255 of file DDAVFSolver.h.

    {
        SVFGEdgeSet newIndirectEdges;
        if(_pag->isFunPtr(dpm.getCurNodeID()))
        {
            const CallSiteSet& csSet = _pag->getIndCallSites(dpm.getCurNodeID());
            for(CallSiteSet::const_iterator it = csSet.begin(), eit = csSet.end(); it!=eit; ++it)
                updateCallGraphAndSVFG(dpm, (*it),newIndirectEdges);
        }
        if(!newIndirectEdges.empty())
            _callGraphSCC->find();
        reComputeForEdges(dpm,newIndirectEdges,true);
 
        SVFGEdgeSet edgeSet(dpm.getLoc()->getOutEdges());
        reComputeForEdges(dpm,edgeSet,false);
    }

◆ reComputeForEdges()

template<class CVar , class CPtSet , class DPIm >

void SVF::DDAVFSolver< CVar, CPtSet, DPIm >::reComputeForEdges	(	const DPIm &	dpm,
		const SVFGEdgeSet &	edgeSet,
		bool	indirectCall = `false`
	)

inlineprotected

Traverse along out edges to find all nodes which may be affected by locDPM.

Only collect nodes we have traversed

Definition at line 276 of file DDAVFSolver.h.

    {
        for (SVFGNode::const_iterator it = edgeSet.begin(), eit = edgeSet.end(); it != eit; ++it)
        {
            const SVFGEdge* edge = *it;
            const SVFGNode* dst = edge->getDstNode();
            typename LocToDPMVecMap::const_iterator locIt = getLocToDPMVecMap().find(dst->getId());
            if (locIt == getLocToDPMVecMap().end())
                continue;
            DPTItemSet dpmSet(locIt->second.begin(), locIt->second.end());
            for(typename DPTItemSet::const_iterator it = dpmSet.begin(),eit = dpmSet.end(); it!=eit; ++it)
            {
                const DPIm& dstDpm = *it;
                if(!indirectCall && SVFUtil::isa<IndirectSVFGEdge>(edge) && !SVFUtil::isa<LoadSVFGNode>(edge->getDstNode()))
                {
                    if(dstDpm.getCurNodeID() == dpm.getCurNodeID())
                    {
                        DBOUT(DDDA,SVFUtil::outs() << "\t Recompute, forward from :");
                        DBOUT(DDDA, dpm.dump());
                        DOSTAT(ddaStat->_NumOfStepInCycle++);
                        clearbkVisited(dstDpm);
                        findPT(dstDpm);
                    }
                }
                else
                {
                    if(indirectCall)
                        DBOUT(DDDA,SVFUtil::outs() << "\t Recompute for indirect call from :");
                    else
                        DBOUT(DDDA,SVFUtil::outs() << "\t Recompute forward from :");
                    DBOUT(DDDA, dpm.dump());
                    DOSTAT(ddaStat->_NumOfStepInCycle++);
                    clearbkVisited(dstDpm);
                    findPT(dstDpm);
                }
            }
        }
    }

◆ removeDpmFromLoc()

template<class CVar , class CPtSet , class DPIm >

void SVF::DDAVFSolver< CVar, CPtSet, DPIm >::removeDpmFromLoc ( const DPIm & dpm )

inlineprivate

Definition at line 673 of file DDAVFSolver.h.

    {
        assert(dpm == locToDpmSetMap[dpm.getLoc()].back() && "dpm not match with the end of vector");
        locToDpmSetMap[dpm.getLoc()->getId()].erase(dpm);
    }

◆ resetQuery()

template<class CVar , class CPtSet , class DPIm >

virtual void SVF::DDAVFSolver< CVar, CPtSet, DPIm >::resetQuery ( )

inlineprotectedvirtual

Reset visited map for next points-to query.

Definition at line 324 of file DDAVFSolver.h.

    {
        if(outOfBudgetQuery)
            OOBResetVisited();
 
        locToDpmSetMap.clear();
        dpmToloadDpmMap.clear();
        loadToPTCVarMap.clear();
        outOfBudgetQuery = false;
        ddaStat->_NumOfStep = 0;
    }

◆ resolveFunPtr()

template<class CVar , class CPtSet , class DPIm >

void SVF::DDAVFSolver< CVar, CPtSet, DPIm >::resolveFunPtr ( const DPIm & dpm )

inlineprotected

resolve function pointer

use pre-analysis call graph to approximate all potential callsites

Definition at line 494 of file DDAVFSolver.h.

    {
        if(const CallICFGNode* cbn= getSVFG()->isCallSiteRetSVFGNode(dpm.getLoc()))
        {
            if(_pag->isIndirectCallSites(cbn))
            {
                NodeID funPtr = _pag->getFunPtr(cbn);
                DPIm funPtrDpm(dpm);
                funPtrDpm.setLocVar(getSVFG()->getDefSVFGNode(_pag->getGNode(funPtr)),funPtr);
                findPT(funPtrDpm);
            }
        }
        else if(const SVFFunction* fun = getSVFG()->isFunEntrySVFGNode(dpm.getLoc()))
        {
            CallInstSet csSet;
            _ander->getCallGraph()->getIndCallSitesInvokingCallee(fun,csSet);
            for(CallInstSet::const_iterator it = csSet.begin(), eit = csSet.end(); it!=eit; ++it)
            {
                NodeID funPtr = _pag->getFunPtr(*it);
                DPIm funPtrDpm(dpm);
                funPtrDpm.setLocVar(getSVFG()->getDefSVFGNode(_pag->getGNode(funPtr)),funPtr);
                findPT(funPtrDpm);
            }
        }
    }

◆ rmSUStat()

template<class CVar , class CPtSet , class DPIm >

void SVF::DDAVFSolver< CVar, CPtSet, DPIm >::rmSUStat	(	const DPIm &	dpm,
		const SVFGNode *	node
	)

inlineprotected

remove strong updates num if the dpm goes to weak updates branch

Definition at line 763 of file DDAVFSolver.h.

    {
        DPTItemSet& dpmSet = storeToDPMs[node];
        if (dpmSet.erase(dpm))
        {
            ddaStat->_NumOfStrongUpdates--;
            if(dpmSet.empty())
                ddaStat->_StrongUpdateStores.reset(node->getId());
        }
    }

◆ setCallGraph()

template<class CVar , class CPtSet , class DPIm >

void SVF::DDAVFSolver< CVar, CPtSet, DPIm >::setCallGraph ( PTACallGraph * cg )

inlineprotected

Set callgraph.

Definition at line 629 of file DDAVFSolver.h.

    {
        _callGraph = cg;
    }

◆ setCallGraphSCC()

template<class CVar , class CPtSet , class DPIm >

void SVF::DDAVFSolver< CVar, CPtSet, DPIm >::setCallGraphSCC ( CallGraphSCC * scc )

inlineprotected

Set callgraphSCC.

Definition at line 634 of file DDAVFSolver.h.

    {
        _callGraphSCC = scc;
    }

◆ setDDAStat()

template<class CVar , class CPtSet , class DPIm >

DDAStat * SVF::DDAVFSolver< CVar, CPtSet, DPIm >::setDDAStat ( DDAStat * s )

inlineprotected

Set DDAStat.

Definition at line 748 of file DDAVFSolver.h.

    {
        ddaStat = s;
        return ddaStat;
    }

◆ startNewPTCompFromLoadSrc()

template<class CVar , class CPtSet , class DPIm >

void SVF::DDAVFSolver< CVar, CPtSet, DPIm >::startNewPTCompFromLoadSrc	(	CPtSet &	pts,
		const DPIm &	oldDpm
	)

inlineprotected

Backward traverse for top-level pointers of load/store statements

Definition at line 392 of file DDAVFSolver.h.

    {
        const LoadSVFGNode* load = SVFUtil::cast<LoadSVFGNode>(oldDpm.getLoc());
        const SVFGNode* loadSrc = getDefSVFGNode(load->getPAGSrcNode());
        DBOUT(DDDA, SVFUtil::outs() << "!##start new computation from loadSrc svfgNode " <<
              load->getId() << " --> " << loadSrc->getId() << "\n");
        const SVFGEdge* edge = getSVFG()->getIntraVFGEdge(loadSrc,load,SVFGEdge::IntraDirectVF);
        assert(edge && "Edge not found!!");
        backwardPropDpm(pts,load->getPAGSrcNodeID(),oldDpm,edge);
 
    }

◆ startNewPTCompFromStoreDst()

template<class CVar , class CPtSet , class DPIm >

void SVF::DDAVFSolver< CVar, CPtSet, DPIm >::startNewPTCompFromStoreDst	(	CPtSet &	pts,
		const DPIm &	oldDpm
	)

inlineprotected

Definition at line 403 of file DDAVFSolver.h.

    {
        const StoreSVFGNode* store = SVFUtil::cast<StoreSVFGNode>(oldDpm.getLoc());
        const SVFGNode* storeDst = getDefSVFGNode(store->getPAGDstNode());
        DBOUT(DDDA, SVFUtil::outs() << "!##start new computation from storeDst svfgNode " <<
              store->getId() << " --> " << storeDst->getId() << "\n");
        const SVFGEdge* edge = getSVFG()->getIntraVFGEdge(storeDst,store,SVFGEdge::IntraDirectVF);
        assert(edge && "Edge not found!!");
        backwardPropDpm(pts,store->getPAGDstNodeID(),oldDpm,edge);
    }

◆ SVFGSCCDetection()

template<class CVar , class CPtSet , class DPIm >

void SVF::DDAVFSolver< CVar, CPtSet, DPIm >::SVFGSCCDetection ( )

inlineprotected

SVFG SCC detection.

Definition at line 605 of file DDAVFSolver.h.

    {
        if(_svfgSCC==nullptr)
        {
            _svfgSCC = new SVFGSCC(getSVFG());
        }
        _svfgSCC->find();
    }

◆ testOutOfBudget()

template<class CVar , class CPtSet , class DPIm >

bool SVF::DDAVFSolver< CVar, CPtSet, DPIm >::testOutOfBudget ( const DPIm & dpm )

inlineprotected

Definition at line 726 of file DDAVFSolver.h.

    {
        if(outOfBudgetQuery) return true;
        if(++ddaStat->_NumOfStep > DPIm::getMaxBudget())
            outOfBudgetQuery = true;
        return isOutOfBudgetDpm(dpm) || outOfBudgetQuery;
    }

◆ unionDDAPts() [1/2]

template<class CVar , class CPtSet , class DPIm >

virtual bool SVF::DDAVFSolver< CVar, CPtSet, DPIm >::unionDDAPts	(	CPtSet &	pts,
		const CPtSet &	targetPts
	)

inlinevirtual

Union pts.

Definition at line 102 of file DDAVFSolver.h.

    {
        return (pts |= targetPts);
    }

◆ unionDDAPts() [2/2]

template<class CVar , class CPtSet , class DPIm >

virtual bool SVF::DDAVFSolver< CVar, CPtSet, DPIm >::unionDDAPts	(	DPIm	dpm,
		const CPtSet &	targetPts
	)

inlinevirtual

Union pts.

Reimplemented in SVF::FlowDDA.

Definition at line 107 of file DDAVFSolver.h.

    {
        CPtSet& pts = isTopLevelPtrStmt(dpm.getLoc()) ? dpmToTLCPtSetMap[dpm] : dpmToADCPtSetMap[dpm];
        return pts |= targetPts;
    }

◆ updateCachedPointsTo()

template<class CVar , class CPtSet , class DPIm >

virtual void SVF::DDAVFSolver< CVar, CPtSet, DPIm >::updateCachedPointsTo	(	const DPIm &	dpm,
		const CPtSet &	pts
	)

inlineprotectedvirtual

Definition at line 565 of file DDAVFSolver.h.

    {
        if (unionDDAPts(dpm, pts))
        {
            DOSTAT(double start = DDAStat::getClk(true));
            reCompute(dpm);
            DOSTAT(ddaStat->_AnaTimeCyclePerQuery += DDAStat::getClk(true) - start);
        }
    }

◆ updateCallGraphAndSVFG()

template<class CVar , class CPtSet , class DPIm >

virtual void SVF::DDAVFSolver< CVar, CPtSet, DPIm >::updateCallGraphAndSVFG	(	const DPIm &	,
		const CallICFGNode *	,
		SVFGEdgeSet &
	)

inlineprotectedvirtual

Update call graph.

Reimplemented in SVF::ContextDDA, and SVF::FlowDDA.

Definition at line 536 of file DDAVFSolver.h.

536{}

Friends And Related Symbol Documentation

◆ DDAStat

template<class CVar , class CPtSet , class DPIm >

friend class DDAStat

friend

Definition at line 49 of file DDAVFSolver.h.

Member Data Documentation

◆ _ander

template<class CVar , class CPtSet , class DPIm >

AndersenWaveDiff* SVF::DDAVFSolver< CVar, CPtSet, DPIm >::_ander

protected

Andersen's analysis.

Definition at line 777 of file DDAVFSolver.h.

◆ _callGraph

template<class CVar , class CPtSet , class DPIm >

PTACallGraph* SVF::DDAVFSolver< CVar, CPtSet, DPIm >::_callGraph

protected

PTACallGraph.

Definition at line 779 of file DDAVFSolver.h.

◆ _callGraphSCC

template<class CVar , class CPtSet , class DPIm >

CallGraphSCC* SVF::DDAVFSolver< CVar, CPtSet, DPIm >::_callGraphSCC

protected

SCC for PTACallGraph.

Definition at line 780 of file DDAVFSolver.h.

◆ _pag

template<class CVar , class CPtSet , class DPIm >

SVFIR* SVF::DDAVFSolver< CVar, CPtSet, DPIm >::_pag

protected

SVFIR.

Definition at line 775 of file DDAVFSolver.h.

◆ _svfg

template<class CVar , class CPtSet , class DPIm >

SVFG* SVF::DDAVFSolver< CVar, CPtSet, DPIm >::_svfg

protected

SVFG.

Definition at line 776 of file DDAVFSolver.h.

◆ _svfgSCC

template<class CVar , class CPtSet , class DPIm >

SVFGSCC* SVF::DDAVFSolver< CVar, CPtSet, DPIm >::_svfgSCC

protected

SCC for SVFG.

Definition at line 781 of file DDAVFSolver.h.

◆ backwardVisited

template<class CVar , class CPtSet , class DPIm >

DPTItemSet SVF::DDAVFSolver< CVar, CPtSet, DPIm >::backwardVisited

protected

visited map during backward traversing

Definition at line 782 of file DDAVFSolver.h.

◆ candidateQueries

template<class CVar , class CPtSet , class DPIm >

NodeBS SVF::DDAVFSolver< CVar, CPtSet, DPIm >::candidateQueries

protected

candidate pointers;

Definition at line 778 of file DDAVFSolver.h.

◆ ddaStat

template<class CVar , class CPtSet , class DPIm >

DDAStat* SVF::DDAVFSolver< CVar, CPtSet, DPIm >::ddaStat

protected

DDA stat.

Definition at line 790 of file DDAVFSolver.h.

◆ dpmToADCPtSetMap

template<class CVar , class CPtSet , class DPIm >

DPImToCPtSetMap SVF::DDAVFSolver< CVar, CPtSet, DPIm >::dpmToADCPtSetMap

protected

points-to caching map for address-taken vars

Definition at line 784 of file DDAVFSolver.h.

◆ dpmToloadDpmMap

template<class CVar , class CPtSet , class DPIm >

DPMToDPMMap SVF::DDAVFSolver< CVar, CPtSet, DPIm >::dpmToloadDpmMap

protected

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

Definition at line 786 of file DDAVFSolver.h.

◆ dpmToTLCPtSetMap

template<class CVar , class CPtSet , class DPIm >

DPImToCPtSetMap SVF::DDAVFSolver< CVar, CPtSet, DPIm >::dpmToTLCPtSetMap

protected

points-to caching map for top-level vars

Definition at line 783 of file DDAVFSolver.h.

◆ loadToPTCVarMap

template<class CVar , class CPtSet , class DPIm >

DPMToCVarMap SVF::DDAVFSolver< CVar, CPtSet, DPIm >::loadToPTCVarMap

protected

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

Definition at line 787 of file DDAVFSolver.h.

◆ locToDpmSetMap

template<class CVar , class CPtSet , class DPIm >

LocToDPMVecMap SVF::DDAVFSolver< CVar, CPtSet, DPIm >::locToDpmSetMap

protected

map location to its dpms

Definition at line 785 of file DDAVFSolver.h.

◆ outOfBudgetDpms

template<class CVar , class CPtSet , class DPIm >

DPTItemSet SVF::DDAVFSolver< CVar, CPtSet, DPIm >::outOfBudgetDpms

protected

out of budget dpm set

Definition at line 788 of file DDAVFSolver.h.

◆ outOfBudgetQuery

template<class CVar , class CPtSet , class DPIm >

bool SVF::DDAVFSolver< CVar, CPtSet, DPIm >::outOfBudgetQuery

protected

Whether the current query is out of step limits.

Definition at line 774 of file DDAVFSolver.h.

◆ storeToDPMs

template<class CVar , class CPtSet , class DPIm >

StoreToPMSetMap SVF::DDAVFSolver< CVar, CPtSet, DPIm >::storeToDPMs

protected

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

Definition at line 789 of file DDAVFSolver.h.

◆ svfgBuilder

template<class CVar , class CPtSet , class DPIm >

SVFGBuilder SVF::DDAVFSolver< CVar, CPtSet, DPIm >::svfgBuilder

protected

SVFG Builder.

Definition at line 791 of file DDAVFSolver.h.

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

/home/runner/work/SVF/SVF/svf/include/DDA/DDAVFSolver.h

Public Types

Public Member Functions

Protected Member Functions

Friends

Detailed Description

Member Typedef Documentation

◆ CallGraphSCC

◆ CallInstSet

◆ CallSiteSet

◆ ConstSVFGEdgeSet

◆ DPImToCPtSetMap

◆ DPMToCVarMap

◆ DPMToDPMMap

◆ DPTItemSet

◆ LocToDPMVecMap

◆ StoreToPMSetMap

◆ SVFGEdgeSet

◆ SVFGSCC

Constructor & Destructor Documentation

◆ DDAVFSolver()

◆ ~DDAVFSolver()

Member Function Documentation

◆ addDDAPts()

◆ addDpmToLoc()

◆ addLoadCVar()

◆ addLoadDpm()

◆ addLoadDpmAndCVar()

◆ addOutOfBudgetDpm()

◆ addSUStat()

◆ backtraceAlongDirectVF()

◆ backtraceAlongIndirectVF()

◆ backtraceToStoreSrc()

◆ backwardPropDpm()

◆ buildSVFG()

◆ clearbkVisited()

◆ dumpCPtSet()

◆ edgeInSVFGSCC()

◆ findPT()

◆ getAndersenAnalysis()

◆ getCachedADPointsTo()

◆ getCachedPointsTo()

◆ getCachedTLPointsTo()

◆ getCandidateQueries()

◆ getConservativeCPts()

◆ getDefSVFGNode()

◆ getDPIm()

◆ getDPImWithOldCond()

◆ getDpmSetAtLoc()

◆ getLoadCVar()

◆ getLoadDpm()

◆ getLocToDPMVecMap()

◆ getPtrNodeID()

◆ getSVFG()

◆ getSVFGSCC()

◆ getSVFGSCCRepNode()

◆ handleAddr()

◆ handleBKCondition()

◆ handleOutOfBudgetDpm()

◆ handleSingleStatement()

◆ isArrayCondMemObj()

◆ isbkVisited()

◆ isFieldInsenCondMemObj()

◆ isHeapCondMemObj()

◆ isLocalCVarInRecursion()

◆ isMustAlias()

◆ isOutOfBudgetDpm()

◆ isOutOfBudgetQuery()

◆ isStrongUpdate()

◆ isSVFGNodeInCycle()

◆ isTopLevelPtrStmt()

◆ markbkVisited()

◆ OOBResetVisited()

◆ processGepPts()

◆ propagateViaObj()

◆ reCompute()

◆ reComputeForEdges()

◆ removeDpmFromLoc()

◆ resetQuery()

◆ resolveFunPtr()

◆ rmSUStat()