#include <PointerAnalysisImpl.h>

Inheritance diagram for SVF::BVDataPTAImpl:

Public Types
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 SVFFunction * >	FunctionSet

typedef OrderedMap< const CallICFGNode *, FunctionSet >	CallEdgeMap

typedef SCCDetection< PTACallGraph * >	CallGraphSCC

typedef Set< const SVFGlobalValue * >	VTableSet

typedef Set< const SVFFunction * >	VFunSet

Public Member Functions
	BVDataPTAImpl (SVFIR *pag, PointerAnalysis::PTATY type, bool alias_check=true)
	Constructor.

	~BVDataPTAImpl () override=default
	Destructor.

PersistentPointsToCache< PointsTo > &	getPtCache ()

Public Member Functions inherited from SVF::PointerAnalysis
ICFG *	getICFG () const
	Get ICFG.

u32_t	getNumOfResolvedIndCallEdge () const
	Return number of resolved indirect call edges.

PTACallGraph *	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 SVFFunction fun1, const SVFFunction 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 SVFFunction *fun) const

bool	isLocalVarInRecursiveFun (NodeID id) const
	Whether a local variable is in function recursions.

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

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.

SVFModule *	getModule () const
	Module.

OrderedNodeSet &	getAllValidPtrs ()
	Get all Valid Pointers for resolution.

virtual void	initialize ()
	Initialization of a pointer analysis, including building symbol table and SVFIR etc.

virtual void	analyze ()=0
	Start Analysis here (main part of pointer analysis). It needs to be implemented in child class.

virtual void	computeDDAPts (NodeID)
	Compute points-to results on-demand, overridden by derived classes.

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

Static Public Member Functions
static bool	classof (const PointerAnalysis *pta)

std::unique_ptr< PTDataTy >	ptD
	Points-to data.

PersistentPointsToCache< PointsTo >	ptCache

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 SVFValue V1, const SVFValue 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

PTDataTy *	getPTDataTy () const
	Get points-to data structure.

void	finalize () override
	Finalization of pointer analysis, and normalize points-to information to Bit Vector representation.

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

Additional Inherited Members
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::PointerAnalysis
const CallSiteToFunPtrMap &	getIndirectCallsites () const
	Return all indirect callsites.

NodeID	getFunPtr (const CallICFGNode *cs) const
	Return function pointer PAGNode at a callsite cs.

virtual void	validateTests ()
	Alias check functions to verify correctness of pointer analysis.

virtual void	validateSuccessTests (std::string fun)

virtual void	validateExpectedFailureTests (std::string fun)

void	resetObjFieldSensitive ()
	Reset all object node as field-sensitive.

Protected Attributes 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.

SVFModule *	svfMod
	Module.

PTATY	ptaTy
	Pointer analysis Type.

PTAImplTy	ptaImplTy
	PTA implementation type.

PTAStat *	stat
	Statistics.

PTACallGraph *	callgraph
	Call graph used for pointer analysis.

CallGraphSCC *	callGraphSCC
	SCC for PTACallGraph.

ICFG *	icfg
	Interprocedural control-flow graph.

CommonCHGraph *	chgraph
	CHGraph.

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

Detailed Description

Pointer analysis implementation which uses bit vector based points-to data structure

Definition at line 42 of file PointerAnalysisImpl.h.

Member Typedef Documentation

◆ DFPTDataTy

typedef DFPTData<NodeID, NodeSet, NodeID, PointsTo> SVF::BVDataPTAImpl::DFPTDataTy

Definition at line 48 of file PointerAnalysisImpl.h.

◆ DiffPTDataTy

typedef DiffPTData<NodeID, NodeSet, NodeID, PointsTo> SVF::BVDataPTAImpl::DiffPTDataTy

Definition at line 47 of file PointerAnalysisImpl.h.

◆ MutDFPTDataTy

typedef MutableDFPTData<NodeID, NodeSet, NodeID, PointsTo> SVF::BVDataPTAImpl::MutDFPTDataTy

Definition at line 53 of file PointerAnalysisImpl.h.

◆ MutDiffPTDataTy

typedef MutableDiffPTData<NodeID, NodeSet, NodeID, PointsTo> SVF::BVDataPTAImpl::MutDiffPTDataTy

Definition at line 52 of file PointerAnalysisImpl.h.

◆ MutIncDFPTDataTy

typedef MutableIncDFPTData<NodeID, NodeSet, NodeID, PointsTo> SVF::BVDataPTAImpl::MutIncDFPTDataTy

Definition at line 54 of file PointerAnalysisImpl.h.

◆ MutPTDataTy

typedef MutablePTData<NodeID, NodeSet, NodeID, PointsTo> SVF::BVDataPTAImpl::MutPTDataTy

Definition at line 51 of file PointerAnalysisImpl.h.

◆ MutVersionedPTDataTy

typedef MutableVersionedPTData<NodeID, NodeSet, NodeID, PointsTo, VersionedVar, Set<VersionedVar> > SVF::BVDataPTAImpl::MutVersionedPTDataTy

Definition at line 55 of file PointerAnalysisImpl.h.

◆ PersDFPTDataTy

typedef PersistentDFPTData<NodeID, NodeSet, NodeID, PointsTo> SVF::BVDataPTAImpl::PersDFPTDataTy

Definition at line 59 of file PointerAnalysisImpl.h.

◆ PersDiffPTDataTy

typedef PersistentDiffPTData<NodeID, NodeSet, NodeID, PointsTo> SVF::BVDataPTAImpl::PersDiffPTDataTy

Definition at line 58 of file PointerAnalysisImpl.h.

◆ PersIncDFPTDataTy

typedef PersistentIncDFPTData<NodeID, NodeSet, NodeID, PointsTo> SVF::BVDataPTAImpl::PersIncDFPTDataTy

Definition at line 60 of file PointerAnalysisImpl.h.

◆ PersPTDataTy

typedef PersistentPTData<NodeID, NodeSet, NodeID, PointsTo> SVF::BVDataPTAImpl::PersPTDataTy

Definition at line 57 of file PointerAnalysisImpl.h.

◆ PersVersionedPTDataTy

typedef PersistentVersionedPTData<NodeID, NodeSet, NodeID, PointsTo, VersionedVar, Set<VersionedVar> > SVF::BVDataPTAImpl::PersVersionedPTDataTy

Definition at line 61 of file PointerAnalysisImpl.h.

◆ PTDataTy

typedef PTData<NodeID, NodeSet, NodeID, PointsTo> SVF::BVDataPTAImpl::PTDataTy

Definition at line 46 of file PointerAnalysisImpl.h.

◆ VersionedPTDataTy

typedef VersionedPTData<NodeID, NodeSet, NodeID, PointsTo, VersionedVar, Set<VersionedVar> > SVF::BVDataPTAImpl::VersionedPTDataTy

Definition at line 49 of file PointerAnalysisImpl.h.

Member Enumeration Documentation

◆ PTBackingType

enum SVF::BVDataPTAImpl::PTBackingType

How the PTData used is implemented.

Enumerator
Mutable
Persistent

Definition at line 64 of file PointerAnalysisImpl.h.

    {
        Mutable,
        Persistent,
    };

Constructor & Destructor Documentation

◆ BVDataPTAImpl()

BVDataPTAImpl::BVDataPTAImpl	(	SVFIR *	p,
		PointerAnalysis::PTATY	type,
		bool	alias_check = `true`
	)

Constructor.

Constructor

Definition at line 46 of file PointerAnalysisImpl.cpp.

                                                                                  :
    PointerAnalysis(p, type, alias_check), ptCache()
{
    if (type == Andersen_BASE || type == Andersen_WPA || type == AndersenWaveDiff_WPA
            || type == TypeCPP_WPA || type == FlowS_DDA
            || type == AndersenSCD_WPA || type == AndersenSFR_WPA || type == CFLFICI_WPA || type == CFLFSCS_WPA)
    {
        // Only maintain reverse points-to when the analysis is field-sensitive, as objects turning
        // field-insensitive is all it is used for.
        bool maintainRevPts = Options::MaxFieldLimit() != 0;
        if (Options::ptDataBacking() == PTBackingType::Mutable) ptD = std::make_unique<MutDiffPTDataTy>(maintainRevPts);
        else if (Options::ptDataBacking() == PTBackingType::Persistent) ptD = std::make_unique<PersDiffPTDataTy>(getPtCache(), maintainRevPts);
        else assert(false && "BVDataPTAImpl::BVDataPTAImpl: unexpected points-to backing type!");
    }
    else if (type == Steensgaard_WPA)
    {
        // Steensgaard is only field-insensitive (for now?), so no reverse points-to.
        if (Options::ptDataBacking() == PTBackingType::Mutable) ptD = std::make_unique<MutDiffPTDataTy>(false);
        else if (Options::ptDataBacking() == PTBackingType::Persistent) ptD = std::make_unique<PersDiffPTDataTy>(getPtCache(), false);
        else assert(false && "BVDataPTAImpl::BVDataPTAImpl: unexpected points-to backing type!");
    }
    else if (type == FSSPARSE_WPA)
    {
        if (Options::INCDFPTData())
        {
            if (Options::ptDataBacking() == PTBackingType::Mutable) ptD = std::make_unique<MutIncDFPTDataTy>(false);
            else if (Options::ptDataBacking() == PTBackingType::Persistent) ptD = std::make_unique<PersIncDFPTDataTy>(getPtCache(), false);
            else assert(false && "BVDataPTAImpl::BVDataPTAImpl: unexpected points-to backing type!");
        }
        else
        {
            if (Options::ptDataBacking() == PTBackingType::Mutable) ptD = std::make_unique<MutDFPTDataTy>(false);
            else if (Options::ptDataBacking() == PTBackingType::Persistent) ptD = std::make_unique<PersDFPTDataTy>(getPtCache(), false);
            else assert(false && "BVDataPTAImpl::BVDataPTAImpl: unexpected points-to backing type!");
        }
    }
    else if (type == VFS_WPA)
    {
        if (Options::ptDataBacking() == PTBackingType::Mutable) ptD = std::make_unique<MutVersionedPTDataTy>(false);
        else if (Options::ptDataBacking() == PTBackingType::Persistent) ptD = std::make_unique<PersVersionedPTDataTy>(getPtCache(), false);
        else assert(false && "BVDataPTAImpl::BVDataPTAImpl: unexpected points-to backing type!");
    }
    else assert(false && "no points-to data available");
 
    ptaImplTy = BVDataImpl;
}

◆ ~BVDataPTAImpl()

SVF::BVDataPTAImpl::~BVDataPTAImpl ( )

overridedefault

Destructor.

Member Function Documentation

◆ addPts()

virtual bool SVF::BVDataPTAImpl::addPts	(	NodeID	id,
		NodeID	ptd
	)

inlinevirtual

Definition at line 121 of file PointerAnalysisImpl.h.

    {
        return ptD->addPts(id,ptd);
    }

◆ alias() [1/3]

AliasResult BVDataPTAImpl::alias	(	const PointsTo &	p1,
		const PointsTo &	p2
	)

virtual

Interface expose to users of our pointer analysis, given two pts.

Return alias results based on our points-to/alias analysis

Definition at line 628 of file PointerAnalysisImpl.cpp.

{
 
    PointsTo pts1;
    expandFIObjs(p1,pts1);
    PointsTo pts2;
    expandFIObjs(p2,pts2);
 
    if (containBlackHoleNode(pts1) || containBlackHoleNode(pts2) || pts1.intersects(pts2))
        return AliasResult::MayAlias;
    else
        return AliasResult::NoAlias;
}

◆ alias() [2/3]

AliasResult BVDataPTAImpl::alias	(	const SVFValue *	V1,
		const SVFValue *	V2
	)

overridevirtual

Interface expose to users of our pointer analysis, given Value infos.

Return alias results based on our points-to/alias analysis

Implements SVF::PointerAnalysis.

Reimplemented in SVF::CFLAlias.

Definition at line 611 of file PointerAnalysisImpl.cpp.

{
    return alias(pag->getValueNode(V1),pag->getValueNode(V2));
}

◆ alias() [3/3]

AliasResult BVDataPTAImpl::alias	(	NodeID	node1,
		NodeID	node2
	)

overridevirtual

Interface expose to users of our pointer analysis, given PAGNodeID.

Return alias results based on our points-to/alias analysis

Implements SVF::PointerAnalysis.

Reimplemented in SVF::CFLAlias.

Definition at line 620 of file PointerAnalysisImpl.cpp.

{
    return alias(getPts(node1),getPts(node2));
}

◆ classof()

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

inlinestatic

Definition at line 81 of file PointerAnalysisImpl.h.

    {
        return pta->getImplTy() == BVDataImpl;
    }

◆ clearAllPts()

virtual void SVF::BVDataPTAImpl::clearAllPts ( )

inlinevirtual

Clear all data.

Definition at line 128 of file PointerAnalysisImpl.h.

    {
        ptD->clear();
    }

◆ clearFullPts()

virtual void SVF::BVDataPTAImpl::clearFullPts ( NodeID id )

inlinevirtual

Clear points-to set of id.

Definition at line 105 of file PointerAnalysisImpl.h.

    {
        ptD->clearFullPts(id);
    }

◆ clearPts()

virtual void SVF::BVDataPTAImpl::clearPts	(	NodeID	id,
		NodeID	element
	)

inlinevirtual

Remove element from the points-to set of id.

Definition at line 99 of file PointerAnalysisImpl.h.

    {
        ptD->clearPts(id, element);
    }

◆ dumpAllPts()

void BVDataPTAImpl::dumpAllPts ( )

overridevirtual

Dump all points-to including top-level (ValVar) and address-taken (ObjVar) variables

Reimplemented from SVF::PointerAnalysis.

Definition at line 471 of file PointerAnalysisImpl.cpp.

{
    OrderedNodeSet pagNodes;
    for(SVFIR::iterator it = pag->begin(), eit = pag->end(); it!=eit; it++)
    {
        pagNodes.insert(it->first);
    }
 
    for (NodeID n : pagNodes)
    {
        outs() << "----------------------------------------------\n";
        dumpPts(n, this->getPts(n));
    }
 
    outs() << "----------------------------------------------\n";
}

◆ dumpCPts()

void SVF::BVDataPTAImpl::dumpCPts ( )

inlineoverridevirtual

dump and debug, print out conditional pts

Reimplemented from SVF::PointerAnalysis.

Definition at line 229 of file PointerAnalysisImpl.h.

    {
        ptD->dumpPTData();
    }

◆ dumpTopLevelPtsTo()

void BVDataPTAImpl::dumpTopLevelPtsTo ( )

overridevirtual

Dump points-to of each pag node

Reimplemented from SVF::PointerAnalysis.

Definition at line 438 of file PointerAnalysisImpl.cpp.

{
    for (OrderedNodeSet::iterator nIter = this->getAllValidPtrs().begin();
            nIter != this->getAllValidPtrs().end(); ++nIter)
    {
        const PAGNode* node = getPAG()->getGNode(*nIter);
        if (getPAG()->isValidTopLevelPtr(node))
        {
            const PointsTo& pts = this->getPts(node->getId());
            outs() << "\nNodeID " << node->getId() << " ";
 
            if (pts.empty())
            {
                outs() << "\t\tPointsTo: {empty}\n\n";
            }
            else
            {
                outs() << "\t\tPointsTo: { ";
                for (PointsTo::iterator it = pts.begin(), eit = pts.end();
                        it != eit; ++it)
                    outs() << *it << " ";
                outs() << "}\n\n";
            }
        }
    }
 
    outs().flush();
}

◆ expandFIObjs() [1/2]

void BVDataPTAImpl::expandFIObjs	(	const NodeBS &	pts,
		NodeBS &	expandedPts
	)

virtual

TODO: remove repetition.

Definition at line 145 of file PointerAnalysisImpl.cpp.

{
    expandedPts = pts;
    for (const NodeID o : pts)
    {
        if (pag->getBaseObjVar(o) == o || isFieldInsensitive(o))
        {
            expandedPts |= pag->getAllFieldsObjVars(o);
        }
    }
}

◆ expandFIObjs() [2/2]

void BVDataPTAImpl::expandFIObjs	(	const PointsTo &	pts,
		PointsTo &	expandedPts
	)

virtual

Expand FI objects.

Expand all fields of an aggregate in all points-to sets

Definition at line 133 of file PointerAnalysisImpl.cpp.

{
    expandedPts = pts;;
    for(PointsTo::iterator pit = pts.begin(), epit = pts.end(); pit!=epit; ++pit)
    {
        if (pag->getBaseObjVar(*pit) == *pit || isFieldInsensitive(*pit))
        {
            expandedPts |= pag->getAllFieldsObjVars(*pit);
        }
    }
}

◆ finalize()

void BVDataPTAImpl::finalize ( )

overrideprotectedvirtual

Finalization of pointer analysis, and normalize points-to information to Bit Vector representation.

Reimplemented from SVF::PointerAnalysis.

Reimplemented in SVF::CFLAlias, SVF::CFLBase, SVF::CFLVF, SVF::FlowDDA, SVF::FlowSensitive, SVF::TypeAnalysis, and SVF::VersionedFlowSensitive.

Definition at line 93 of file PointerAnalysisImpl.cpp.

{
    normalizePointsTo();
    PointerAnalysis::finalize();
 
    if (Options::ptDataBacking() == PTBackingType::Persistent && print_stat)
    {
        std::string moduleName(pag->getModule()->getModuleIdentifier());
        std::vector<std::string> names = SVFUtil::split(moduleName,'/');
        if (names.size() > 1)
            moduleName = names[names.size() - 1];
 
        std::string subtitle;
 
        if(ptaTy >= Andersen_BASE && ptaTy <= Steensgaard_WPA)
            subtitle = "Andersen's analysis bitvector";
        else if(ptaTy >=FSDATAFLOW_WPA && ptaTy <=FSCS_WPA)
            subtitle = "flow-sensitive analysis bitvector";
        else if(ptaTy >=CFLFICI_WPA && ptaTy <=CFLFSCS_WPA)
            subtitle = "CFL analysis bitvector";
        else if(ptaTy == TypeCPP_WPA)
            subtitle = "Type analysis bitvector";
        else if(ptaTy >=FieldS_DDA && ptaTy <=Cxt_DDA)
            subtitle = "DDA bitvector";
        else
            subtitle = "bitvector";
 
        SVFUtil::outs() << "\n****Persistent Points-To Cache Statistics: " << subtitle << "****\n";
        SVFUtil::outs() << "################ (program : " << moduleName << ")###############\n";
        SVFUtil::outs().flags(std::ios::left);
        ptCache.printStats("bitvector");
        SVFUtil::outs() << "#######################################################" << std::endl;
        SVFUtil::outs().flush();
    }
 
}

◆ getDFPTDataTy()

DFPTDataTy * SVF::BVDataPTAImpl::getDFPTDataTy ( ) const

inlineprotected

Definition at line 178 of file PointerAnalysisImpl.h.

    {
        DFPTDataTy* df = SVFUtil::dyn_cast<DFPTDataTy>(ptD.get());
        assert(df && "BVDataPTAImpl::getDFPTDataTy: not a DFPTDataTy!");
        return df;
    }

◆ getDiffPTDataTy()

DiffPTDataTy * SVF::BVDataPTAImpl::getDiffPTDataTy ( ) const

inlineprotected

Definition at line 171 of file PointerAnalysisImpl.h.

    {
        DiffPTDataTy* diff = SVFUtil::dyn_cast<DiffPTDataTy>(ptD.get());
        assert(diff && "BVDataPTAImpl::getDiffPTDataTy: not a DiffPTDataTy!");
        return diff;
    }

◆ getMutDFPTDataTy()

MutDFPTDataTy * SVF::BVDataPTAImpl::getMutDFPTDataTy ( ) const

inlineprotected

Definition at line 185 of file PointerAnalysisImpl.h.

    {
        MutDFPTDataTy* mdf = SVFUtil::dyn_cast<MutDFPTDataTy>(ptD.get());
        assert(mdf && "BVDataPTAImpl::getMutDFPTDataTy: not a MutDFPTDataTy!");
        return mdf;
    }

◆ getPtCache()

PersistentPointsToCache< PointsTo > & SVF::BVDataPTAImpl::getPtCache ( )

inline

Definition at line 76 of file PointerAnalysisImpl.h.

    {
        return ptCache;
    }

◆ getPTDataTy()

PTDataTy * SVF::BVDataPTAImpl::getPTDataTy ( ) const

inlineprotected

Get points-to data structure.

Definition at line 155 of file PointerAnalysisImpl.h.

    {
        return ptD.get();
    }

◆ getPts()

const PointsTo & SVF::BVDataPTAImpl::getPts ( NodeID id )

inlineoverridevirtual

Get points-to and reverse points-to

Implements SVF::PointerAnalysis.

Reimplemented in SVF::Steensgaard.

Definition at line 88 of file PointerAnalysisImpl.h.

    {
        return ptD->getPts(id);
    }

◆ getRevPts()

const NodeSet & SVF::BVDataPTAImpl::getRevPts ( NodeID nodeId )

inlineoverridevirtual

Given an object, get all the nodes having whose pointsto contains the object. Similar to getPts, this also needs to be implemented in child classes.

Implements SVF::PointerAnalysis.

Reimplemented in SVF::CFLAlias.

Definition at line 92 of file PointerAnalysisImpl.h.

    {
        return ptD->getRevPts(nodeId);
    }

◆ getVersionedPTDataTy()

VersionedPTDataTy * SVF::BVDataPTAImpl::getVersionedPTDataTy ( ) const

inlineprotected

Definition at line 192 of file PointerAnalysisImpl.h.

    {
        VersionedPTDataTy* v = SVFUtil::dyn_cast<VersionedPTDataTy>(ptD.get());
        assert(v && "BVDataPTAImpl::getVersionedPTDataTy: not a VersionedPTDataTy!");
        return v;
    }

◆ normalizePointsTo()

void BVDataPTAImpl::normalizePointsTo ( )

protectedvirtual

Normalize points-to information for field-sensitive analysis, i.e., replace fieldObj with baseObj if it is field-insensitive

Normalize points-to information for field-sensitive analysis

Reimplemented in SVF::AndersenBase.

Definition at line 552 of file PointerAnalysisImpl.cpp.

{
    SVFIR::MemObjToFieldsMap &memToFieldsMap = pag->getMemToFieldsMap();
    SVFIR::NodeOffsetMap &GepObjVarMap = pag->getGepObjNodeMap();
 
    // collect each gep node whose base node has been set as field-insensitive
    NodeBS dropNodes;
    for (auto t: memToFieldsMap)
    {
        NodeID base = t.first;
        const MemObj* memObj = pag->getObject(base);
        assert(memObj && "Invalid memobj in memToFieldsMap");
        if (memObj->isFieldInsensitive())
        {
            for (NodeID id : t.second)
            {
                if (SVFUtil::isa<GepObjVar>(pag->getGNode(id)))
                {
                    dropNodes.set(id);
                }
                else
                    assert(id == base && "Not a GepObj Node or a baseObj Node?");
            }
        }
    }
 
    // remove the collected redundant gep nodes in each pointers's pts
    for (SVFIR::iterator nIter = pag->begin(); nIter != pag->end(); ++nIter)
    {
        NodeID n = nIter->first;
 
        const PointsTo &tmpPts = getPts(n);
        for (NodeID obj : tmpPts)
        {
            if (!dropNodes.test(obj))
                continue;
            NodeID baseObj = pag->getBaseObjVar(obj);
            clearPts(n, obj);
            addPts(n, baseObj);
        }
    }
 
    // clear GepObjVarMap and memToFieldsMap for redundant gepnodes
    // and remove those nodes from pag
    for (NodeID n: dropNodes)
    {
        NodeID base = pag->getBaseObjVar(n);
        GepObjVar *gepNode = SVFUtil::dyn_cast<GepObjVar>(pag->getGNode(n));
        const APOffset apOffset = gepNode->getConstantFieldIdx();
        GepObjVarMap.erase(std::make_pair(base, apOffset));
        memToFieldsMap[base].reset(n);
 
        pag->removeGNode(gepNode);
    }
}

◆ onTheFlyCallGraphSolve()

void BVDataPTAImpl::onTheFlyCallGraphSolve	(	const CallSiteToFunPtrMap &	callsites,
		CallEdgeMap &	newEdges
	)

protectedvirtual

On the fly call graph construction.

On the fly call graph construction callsites is candidate indirect callsites need to be analyzed based on points-to results newEdges is the new indirect call edges discovered

Reimplemented in SVF::CFLAlias.

Definition at line 494 of file PointerAnalysisImpl.cpp.

{
    for(CallSiteToFunPtrMap::const_iterator iter = callsites.begin(), eiter = callsites.end(); iter!=eiter; ++iter)
    {
        const CallICFGNode* cs = iter->first;
 
        if (cs->isVirtualCall())
        {
            const SVFVar* vtbl = cs->getVtablePtr();
            assert(vtbl != nullptr);
            NodeID vtblId = vtbl->getId();
            resolveCPPIndCalls(cs, getPts(vtblId), newEdges);
        }
        else
            resolveIndCalls(iter->first,getPts(iter->second),newEdges);
    }
}

◆ onTheFlyThreadCallGraphSolve()

void BVDataPTAImpl::onTheFlyThreadCallGraphSolve	(	const CallSiteToFunPtrMap &	callsites,
		CallEdgeMap &	newForkEdges
	)

protectedvirtual

On the fly thread call graph construction respecting forksite.

On the fly call graph construction respecting forksite callsites is candidate indirect callsites need to be analyzed based on points-to results newEdges is the new indirect call edges discovered

Definition at line 517 of file PointerAnalysisImpl.cpp.

{
    // add indirect fork edges
    if(ThreadCallGraph *tdCallGraph = SVFUtil::dyn_cast<ThreadCallGraph>(callgraph))
    {
        for(CallSiteSet::const_iterator it = tdCallGraph->forksitesBegin(),
                eit = tdCallGraph->forksitesEnd(); it != eit; ++it)
        {
            const ValVar* pVar = tdCallGraph->getThreadAPI()->getForkedFun(*it);
            if(SVFUtil::dyn_cast<FunValVar>(pVar) == nullptr)
            {
                SVFIR *pag = this->getPAG();
                const NodeBS targets = this->getPts(pVar->getId()).toNodeBS();
                for(NodeBS::iterator ii = targets.begin(), ie = targets.end(); ii != ie; ++ii)
                {
                    if(ObjVar *objPN = SVFUtil::dyn_cast<ObjVar>(pag->getGNode(*ii)))
                    {
                        const MemObj *obj = pag->getObject(objPN);
                        if(obj->isFunction())
                        {
                            const SVFFunction *svfForkedFun = SVFUtil::cast<CallGraphNode>(obj->getGNode())->getFunction();
                            if(tdCallGraph->addIndirectForkEdge(*it, svfForkedFun))
                                newForkEdges[*it].insert(svfForkedFun);
                        }
                    }
                }
            }
        }
    }
}

◆ readAndSetObjFieldSensitivity()

void BVDataPTAImpl::readAndSetObjFieldSensitivity	(	std::ifstream &	f,
		const std::string &	delimiterStr
	)

virtual

Definition at line 379 of file PointerAnalysisImpl.cpp.

{
    string line;
    // //update ObjVar status
    while (F.good())
    {
        getline(F, line);
        if (line.empty() || line == delimiterStr)
            break;
        // Parse a single line in the form of "baseNodeID insensitive"
        istringstream ss(line);
        NodeID base;
        bool insensitive;
        ss >> base >> insensitive;
 
        if (insensitive)
            setObjFieldInsensitive(base);
    }
 
}

◆ readFromFile()

bool BVDataPTAImpl::readFromFile ( const std::string & filename )

virtual

Load pointer analysis result form a file. It populates BVDataPTAImpl with the points-to data, and updates SVFIR with the SVFIR offset nodes created during Andersen's solving stage.

Definition at line 405 of file PointerAnalysisImpl.cpp.

{
 
    outs() << "Loading pointer analysis results from '" << filename << "'...";
 
    ifstream F(filename.c_str());
    if (!F.is_open())
    {
        outs() << "  error opening file for reading!\n";
        return false;
    }
 
    readAndSetObjFieldSensitivity(F,"------");
 
    readPtsResultFromFile(F);
 
    readGepObjVarMapFromFile(F);
 
    readAndSetObjFieldSensitivity(F,"");
 
    // Update callgraph
    updateCallGraph(pag->getIndirectCallsites());
 
    F.close();
    outs() << "\n";
 
    return true;
}

◆ readGepObjVarMapFromFile()

void BVDataPTAImpl::readGepObjVarMapFromFile ( std::ifstream & f )

virtual

Definition at line 343 of file PointerAnalysisImpl.cpp.

{
    string line;
    //read GepObjVarMap from file
    SVFIR::NodeOffsetMap gepObjVarMap = pag->getGepObjNodeMap();
    while (F.good())
    {
        getline(F, line);
        if (line == "------")     break;
        // Parse a single line in the form of "ID baseNodeID offset"
        istringstream ss(line);
        NodeID base;
        size_t offset;
        NodeID id;
        ss >> base >> offset >>id;
        SVFIR::NodeOffsetMap::const_iterator iter = gepObjVarMap.find(std::make_pair(base, offset));
        if (iter == gepObjVarMap.end())
        {
            SVFVar* node = pag->getGNode(base);
            const MemObj* obj = nullptr;
            if (GepObjVar* gepObjVar = SVFUtil::dyn_cast<GepObjVar>(node))
                obj = gepObjVar->getMemObj();
            else if (BaseObjVar* baseNode = SVFUtil::dyn_cast<BaseObjVar>(node))
                obj = baseNode->getMemObj();
            else if (DummyObjVar* baseNode = SVFUtil::dyn_cast<DummyObjVar>(node))
                obj = baseNode->getMemObj();
            else
                assert(false && "new gep obj node kind?");
            pag->addGepObjNode(obj, offset, id);
            NodeIDAllocator::get()->increaseNumOfObjAndNodes();
        }
 
 
    }
}

◆ readPtsResultFromFile()

void BVDataPTAImpl::readPtsResultFromFile ( std::ifstream & f )

virtual

Definition at line 289 of file PointerAnalysisImpl.cpp.

{
    string line;
    // Read analysis results from file
    PTDataTy *ptD = getPTDataTy();
 
    // Read points-to sets
    string delimiter1 = " -> { ";
    string delimiter2 = " }";
    map<NodeID, string> nodePtsMap;
    map<string, PointsTo> strPtsMap;
 
    while (F.good())
    {
        // Parse a single line in the form of "var -> { obj1 obj2 obj3 }"
        getline(F, line);
        if (line.at(0) == '[' || line == "---VERSIONED---") continue;
        if (line == "------")     break;
        size_t pos = line.find(delimiter1);
        if (pos == string::npos)    break;
        if (line.back() != '}')     break;
 
        // var
        NodeID var = atoi(line.substr(0, pos).c_str());
 
        // objs
        pos = pos + delimiter1.length();
        size_t len = line.length() - pos - delimiter2.length();
        string objs = line.substr(pos, len);
        PointsTo dstPts;
 
        if (!objs.empty())
        {
            // map the variable ID to its unique string pointer set
            nodePtsMap[var] = objs;
            if (strPtsMap.count(objs)) continue;
 
            istringstream ss(objs);
            NodeID obj;
            while (ss.good())
            {
                ss >> obj;
                dstPts.set(obj);
            }
            // map the string pointer set to the parsed PointsTo set
            strPtsMap[objs] = dstPts;
        }
    }
 
    // map the variable ID to its pointer set
    for (auto t: nodePtsMap)
        ptD->unionPts(t.first, strPtsMap[t.second]);
}

◆ remapPointsToSets()

void BVDataPTAImpl::remapPointsToSets ( void )

Remap all points-to sets to use the current mapping.

Definition at line 157 of file PointerAnalysisImpl.cpp.

{
    getPTDataTy()->remapAllPts();
}

◆ unionPts() [1/2]

virtual bool SVF::BVDataPTAImpl::unionPts	(	NodeID	id,
		const PointsTo &	target
	)

inlinevirtual

Union/add points-to. Add the reverse points-to for node collapse purpose To be noted that adding reverse pts might incur 10% total overhead during solving

Reimplemented in SVF::Andersen, and SVF::Steensgaard.

Definition at line 113 of file PointerAnalysisImpl.h.

    {
        return ptD->unionPts(id, target);
    }

◆ unionPts() [2/2]

virtual bool SVF::BVDataPTAImpl::unionPts	(	NodeID	id,
		NodeID	ptd
	)

inlinevirtual

Reimplemented in SVF::Andersen, and SVF::Steensgaard.

Definition at line 117 of file PointerAnalysisImpl.h.

    {
        return ptD->unionPts(id,ptd);
    }

◆ updateCallGraph()

virtual bool SVF::BVDataPTAImpl::updateCallGraph ( const CallSiteToFunPtrMap & )

inlineprotectedvirtual

Update callgraph. This should be implemented by its subclass.

Reimplemented in SVF::AndersenBase, SVF::CFLAlias, SVF::AndersenSCD, and SVF::FlowSensitive.

Definition at line 165 of file PointerAnalysisImpl.h.

    {
        assert(false && "Virtual function not implemented!");
        return false;
    }

◆ writeGepObjVarMapToFile()

void BVDataPTAImpl::writeGepObjVarMapToFile ( std::fstream & f )

virtual

Definition at line 224 of file PointerAnalysisImpl.cpp.

{
    //write gepObjVarMap to file(in form of: baseID offset gepObjNodeId)
    SVFIR::NodeOffsetMap &gepObjVarMap = pag->getGepObjNodeMap();
    for(SVFIR::NodeOffsetMap::const_iterator it = gepObjVarMap.begin(), eit = gepObjVarMap.end(); it != eit; it++)
    {
        const SVFIR::NodeOffset offsetPair = it -> first;
        //write the base id to file
        f << offsetPair.first << " ";
        //write the offset to file
        f << offsetPair.second << " ";
        //write the gepObjNodeId to file
        f << it->second << "\n";
    }
 
}

◆ writeObjVarToFile()

void BVDataPTAImpl::writeObjVarToFile ( const std::string & filename )

virtual

Definition at line 162 of file PointerAnalysisImpl.cpp.

{
    outs() << "Storing ObjVar to '" << filename << "'...";
    error_code err;
    std::fstream f(filename.c_str(), std::ios_base::out);
    if (!f.good())
    {
        outs() << "  error opening file for writing!\n";
        return;
    }
 
    // Write BaseNodes insensitivity to file
    NodeBS NodeIDs;
    for (auto it = pag->begin(), ie = pag->end(); it != ie; ++it)
    {
        PAGNode* pagNode = it->second;
        if (!isa<ObjVar>(pagNode)) continue;
        NodeID n = pag->getBaseObjVar(it->first);
        if (NodeIDs.test(n)) continue;
        f << n << " ";
        f << isFieldInsensitive(n) << "\n";
        NodeIDs.set(n);
    }
 
    f << "------\n";
 
    f.close();
    if (f.good())
    {
        outs() << "\n";
        return;
    }
 
 
}

◆ writePtsResultToFile()

void BVDataPTAImpl::writePtsResultToFile ( std::fstream & f )

virtual

Definition at line 198 of file PointerAnalysisImpl.cpp.

{
    // Write analysis results to file
    for (auto it = pag->begin(), ie = pag->end(); it != ie; ++it)
    {
        NodeID var = it->first;
        const PointsTo &pts = getPts(var);
 
        stringstream ss;
        f << var << " -> { ";
        if (pts.empty())
        {
            f << " ";
        }
        else
        {
            for (NodeID n: pts)
            {
                f << n << " ";
            }
        }
        f << "}\n";
    }
 
}

◆ writeToFile()

void BVDataPTAImpl::writeToFile ( const std::string & filename )

virtual

Interface for analysis result storage on filesystem.

Store pointer analysis result into a file. It includes the points-to relations, and all SVFIR nodes including those created when solving Andersen's constraints.

Definition at line 246 of file PointerAnalysisImpl.cpp.

{
 
    outs() << "Storing pointer analysis results to '" << filename << "'...";
 
    error_code err;
    std::fstream f(filename.c_str(), std::ios_base::app);
    if (!f.good())
    {
        outs() << "  error opening file for writing!\n";
        return;
    }
 
    writePtsResultToFile(f);
 
    f << "------\n";
 
    writeGepObjVarMapToFile(f);
 
    f << "------\n";
 
    // Write BaseNodes insensitivity to file
    NodeBS NodeIDs;
    for (auto it = pag->begin(), ie = pag->end(); it != ie; ++it)
    {
        PAGNode* pagNode = it->second;
        if (!isa<ObjVar>(pagNode)) continue;
        NodeID n = pag->getBaseObjVar(it->first);
        if (NodeIDs.test(n)) continue;
        f << n << " ";
        f << isFieldInsensitive(n) << "\n";
        NodeIDs.set(n);
    }
 
    // Job finish and close file
    f.close();
    if (f.good())
    {
        outs() << "\n";
        return;
    }
}

Member Data Documentation

◆ ptCache

PersistentPointsToCache<PointsTo> SVF::BVDataPTAImpl::ptCache

private

Definition at line 214 of file PointerAnalysisImpl.h.

◆ ptD

std::unique_ptr<PTDataTy> SVF::BVDataPTAImpl::ptD

private

Points-to data.

Definition at line 212 of file PointerAnalysisImpl.h.

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

/home/runner/work/SVF/SVF/svf/include/MemoryModel/PointerAnalysisImpl.h
/home/runner/work/SVF/SVF/svf/lib/MemoryModel/PointerAnalysisImpl.cpp

Public Types

Public Member Functions

Static Public Member Functions

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ DFPTDataTy

◆ DiffPTDataTy

◆ MutDFPTDataTy

◆ MutDiffPTDataTy

◆ MutIncDFPTDataTy

◆ MutPTDataTy

◆ MutVersionedPTDataTy

◆ PersDFPTDataTy

◆ PersDiffPTDataTy

◆ PersIncDFPTDataTy

◆ PersPTDataTy

◆ PersVersionedPTDataTy

◆ PTDataTy

◆ VersionedPTDataTy

Member Enumeration Documentation

◆ PTBackingType

Constructor & Destructor Documentation

◆ BVDataPTAImpl()

◆ ~BVDataPTAImpl()

Member Function Documentation

◆ addPts()

◆ alias() [1/3]

◆ alias() [2/3]

◆ alias() [3/3]

◆ classof()

◆ clearAllPts()

◆ clearFullPts()

◆ clearPts()

◆ dumpAllPts()

◆ dumpCPts()

◆ dumpTopLevelPtsTo()

◆ expandFIObjs() [1/2]

◆ expandFIObjs() [2/2]

◆ finalize()

◆ getDFPTDataTy()

◆ getDiffPTDataTy()

◆ getMutDFPTDataTy()

◆ getPtCache()

◆ getPTDataTy()

◆ getPts()

◆ getRevPts()

◆ getVersionedPTDataTy()

◆ normalizePointsTo()

◆ onTheFlyCallGraphSolve()

◆ onTheFlyThreadCallGraphSolve()

◆ readAndSetObjFieldSensitivity()

◆ readFromFile()

◆ readGepObjVarMapFromFile()

◆ readPtsResultFromFile()

◆ remapPointsToSets()

◆ unionPts() [1/2]

◆ unionPts() [2/2]

◆ updateCallGraph()

◆ writeGepObjVarMapToFile()

◆ writeObjVarToFile()

◆ writePtsResultToFile()

◆ writeToFile()

Member Data Documentation

◆ ptCache

◆ ptD