#include <AndersenPWC.h>

Inheritance diagram for SVF::AndersenSFR:

Public Types
typedef Map< NodeID, NodeBS >	NodeStrides

typedef Map< NodeID, NodeSet >	FieldReps

typedef Map< NodeID, std::pair< NodeID, NodeSet > >	SFRTrait

Public Types inherited from SVF::AndersenSCD
typedef Map< NodeID, NodeID >	NodeToNodeMap

Public Types inherited from SVF::Andersen
typedef SCCDetection< ConstraintGraph * >	CGSCC

Public Types inherited from SVF::AndersenBase
typedef OrderedMap< const CallICFGNode *, NodeID >	CallSite2DummyValPN

Public Types inherited from SVF::WPASolver< GraphType >
typedef SVF::GenericGraphTraits< GraphType >	GTraits
	Define the GTraits and node iterator for printing.

typedef GTraits::NodeRef	GNODE

typedef GTraits::EdgeType	GEDGE

typedef GTraits::ChildIteratorType	child_iterator

typedef SCCDetection< GraphType >	SCC

typedef FIFOWorkList< NodeID >	WorkList

Public Types inherited from SVF::BVDataPTAImpl
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
	AndersenSFR (SVFIR *_pag, PTATY type=AndersenSFR_WPA)

	~AndersenSFR ()

Public Member Functions inherited from SVF::AndersenSCD
	AndersenSCD (SVFIR *_pag, PTATY type=AndersenSCD_WPA)

Public Member Functions inherited from SVF::Andersen
	Andersen (SVFIR *_pag, PTATY type=Andersen_WPA, bool alias_check=true)
	Constructor.

virtual	~Andersen ()
	Destructor.

virtual void	finalize ()
	Finalize analysis.

void	resetData ()
	Reset data.

virtual const PointsTo &	getPts (NodeID id)
	Operation of points-to set.

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

virtual bool	unionPts (NodeID id, NodeID ptd)

void	dumpTopLevelPtsTo ()

void	setDetectPWC (bool flag)

Public Member Functions inherited from SVF::AndersenBase
	AndersenBase (SVFIR *_pag, PTATY type=Andersen_BASE, bool alias_check=true)
	Constructor.

	~AndersenBase () override
	Destructor.

virtual void	analyze () override
	Andersen analysis.

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

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

virtual void	solveConstraints ()

virtual bool	updateThreadCallGraph (const CallSiteToFunPtrMap &, NodePairSet &)
	Update thread call graph.

virtual void	connectCaller2ForkedFunParams (const CallICFGNode cs, const SVFFunction F, NodePairSet &cpySrcNodes)
	Connect formal and actual parameters for indirect forksites.

virtual void	connectCaller2CalleeParams (const CallICFGNode cs, const SVFFunction F, NodePairSet &cpySrcNodes)
	Connect formal and actual parameters for indirect callsites.

ConstraintGraph *	getConstraintGraph ()
	Get constraint graph.

NodeID	sccRepNode (NodeID id) const override
	SCC methods.

NodeBS &	sccSubNodes (NodeID repId)

void	printStat ()
	dump statistics

virtual void	normalizePointsTo () override

void	cleanConsCG (NodeID id)
	remove redundant gepnodes in constraint graph

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

	~BVDataPTAImpl () override=default
	Destructor.

PersistentPointsToCache< PointsTo > &	getPtCache ()

const PointsTo &	getPts (NodeID id) override

const NodeSet &	getRevPts (NodeID nodeId) override

virtual void	clearPts (NodeID id, NodeID element)
	Remove element from the points-to set of id.

virtual void	clearFullPts (NodeID id)
	Clear points-to set of id.

virtual bool	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

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.

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	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 AndersenSFR *	createAndersenSFR (SVFIR *_pag)
	Create an singleton instance directly instead of invoking llvm pass manager.

static void	releaseAndersenSFR ()

Static Public Member Functions inherited from SVF::AndersenSCD
static AndersenSCD *	createAndersenSCD (SVFIR *_pag)
	Create an singleton instance directly instead of invoking llvm pass manager.

static void	releaseAndersenSCD ()

Static Public Member Functions inherited from SVF::Andersen
static bool	classof (const Andersen *)
	Methods for support type inquiry through isa, cast, and dyn_cast:

static bool	classof (const PointerAnalysis *pta)

Static Public Member Functions inherited from SVF::AndersenBase
static bool	classof (const AndersenBase *)
	Methods for support type inquiry through isa, cast, and dyn_cast:

static bool	classof (const PointerAnalysis *pta)

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

Protected Member Functions
void	initialize ()
	Initialize analysis.

void	PWCDetect ()

void	fieldExpand (NodeSet &initials, APOffset offset, NodeBS &strides, PointsTo &expandPts)

bool	processGepPts (const PointsTo &pts, const GepCGEdge *edge)

bool	mergeSrcToTgt (NodeID nodeId, NodeID newRepId)

Protected Member Functions inherited from SVF::AndersenSCD
void	addSccCandidate (NodeID nodeId)

virtual NodeStack &	SCCDetect ()

virtual void	solveWorklist ()

virtual void	handleLoadStore (ConstraintNode *node)

virtual void	processAddr (const AddrCGEdge *addr)

virtual bool	addCopyEdge (NodeID src, NodeID dst)

virtual bool	updateCallGraph (const CallSiteToFunPtrMap &callsites)

virtual void	processPWC (ConstraintNode *rep)

virtual void	handleCopyGep (ConstraintNode *node)

Protected Member Functions inherited from SVF::Andersen
virtual void	computeDiffPts (NodeID id)
	Handle diff points-to set.

virtual const PointsTo &	getDiffPts (NodeID id)

void	updatePropaPts (NodeID dstId, NodeID srcId)
	Handle propagated points-to set.

void	clearPropaPts (NodeID src)

virtual void	initWorklist ()

virtual void	processNode (NodeID nodeId)
	Override WPASolver function in order to use the default solver.

void	processAllAddr ()
	handling various constraints

virtual bool	processLoad (NodeID node, const ConstraintEdge *load)

virtual bool	processStore (NodeID node, const ConstraintEdge *load)

virtual bool	processCopy (NodeID node, const ConstraintEdge *edge)

virtual bool	processGep (NodeID node, const GepCGEdge *edge)

virtual void	mergeNodeToRep (NodeID nodeId, NodeID newRepId)
	Merge sub node to its rep.

void	mergeSccNodes (NodeID repNodeId, const NodeBS &subNodes)
	Merge sub node in a SCC cycle to their rep node.

void	mergeSccCycle ()

virtual void	collapsePWCNode (NodeID nodeId)
	Collapse a field object into its base for field insensitive analysis.

void	collapseFields ()
	collapse positive weight cycles of a graph

bool	collapseNodePts (NodeID nodeId)

bool	collapseField (NodeID nodeId)

void	updateNodeRepAndSubs (NodeID nodeId, NodeID newRepId)
	Updates subnodes of its rep, and rep node of its subs.

void	sanitizePts ()
	Sanitize pts for field insensitive objects.

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

virtual void	cluster (void) const

Protected Member Functions inherited from SVF::AndersenBase
void	heapAllocatorViaIndCall (const CallICFGNode *cs, NodePairSet &cpySrcNodes)

Protected Member Functions inherited from SVF::WPASolver< GraphType >
	WPASolver ()
	Constructor.

virtual	~WPASolver ()=default
	Destructor.

SCC *	getSCCDetector () const
	Get SCC detector.

const GraphType	graph ()
	Get/Set graph methods.

void	setGraph (GraphType g)

virtual NodeStack &	SCCDetect (NodeSet &candidates)

virtual void	propagate (GNODE *v)

virtual bool	propFromSrcToDst (GEDGE *)
	Propagate information from source to destination node, to be implemented in the child class.

NodeID	popFromWorklist ()
	Worklist operations.

virtual void	pushIntoWorklist (NodeID id)

bool	isWorklistEmpty ()

bool	isInWorklist (NodeID id)

GNODE *	Node (NodeID id)
	Get node on the graph.

NodeID	Node_Index (GNODE node)
	Get node ID.

Protected Member Functions inherited from SVF::BVDataPTAImpl
PTDataTy *	getPTDataTy () const
	Get points-to data structure.

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

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.

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.

Private Attributes
CSC *	csc

NodeSet	sfrObjNodes

FieldReps	fieldReps

Static Private Attributes
static AndersenSFR *	sfrAndersen = nullptr

Additional Inherited Members
Public Attributes inherited from SVF::AndersenBase
NodeBS	redundantGepNodes

Public Attributes inherited from SVF::WPASolver< GraphType >
u32_t	numOfIteration
	num of iterations during constraint solving

Static Public Attributes inherited from SVF::AndersenBase
static u32_t	numOfProcessedAddr = 0
	Statistics.

static u32_t	numOfProcessedCopy = 0
	Number of processed Addr edge.

static u32_t	numOfProcessedGep = 0
	Number of processed Copy edge.

static u32_t	numOfProcessedLoad = 0
	Number of processed Gep edge.

static u32_t	numOfProcessedStore = 0
	Number of processed Load edge.

static u32_t	numOfSfrs = 0
	Number of processed Store edge.

static u32_t	numOfFieldExpand = 0

static u32_t	numOfSCCDetection = 0

static double	timeOfSCCDetection = 0

static double	timeOfSCCMerges = 0

static double	timeOfCollapse = 0

static u32_t	AveragePointsToSetSize = 0

static u32_t	MaxPointsToSetSize = 0

static double	timeOfProcessCopyGep = 0

static double	timeOfProcessLoadStore = 0

static double	timeOfUpdateCallGraph = 0

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 Attributes inherited from SVF::AndersenSCD
NodeSet	sccCandidates

NodeToNodeMap	pwcReps

Protected Attributes inherited from SVF::Andersen
CallSite2DummyValPN	callsite2DummyValPN
	Map an instruction to a dummy obj which created at an indirect callsite, which invokes a heap allocator.

Protected Attributes inherited from SVF::AndersenBase
ConstraintGraph *	consCG
	Constraint Graph.

CallSite2DummyValPN	callsite2DummyValPN

Protected Attributes inherited from SVF::WPASolver< GraphType >
bool	reanalyze
	Reanalyze if any constraint value changed.

u32_t	iterationForPrintStat
	print out statistics for i-th iteration

GraphType	_graph
	Graph.

std::unique_ptr< SCC >	scc
	SCC.

WorkList	worklist
	Worklist for resolution.

Protected Attributes inherited from SVF::PointerAnalysis
bool	print_stat
	User input flags.

bool	alias_validation
	Flag for validating points-to/alias results.

u32_t	OnTheFlyIterBudgetForStat
	Flag for iteration budget for on-the-fly statistics.

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::AndersenSCD
static AndersenSCD *	scdAndersen = nullptr

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

Detailed Description

Selective Cycle Detection with Stride-based Field Representation

Definition at line 102 of file AndersenPWC.h.

Member Typedef Documentation

◆ FieldReps

typedef Map<NodeID, NodeSet> SVF::AndersenSFR::FieldReps

Definition at line 106 of file AndersenPWC.h.

◆ NodeStrides

typedef Map<NodeID, NodeBS> SVF::AndersenSFR::NodeStrides

Definition at line 105 of file AndersenPWC.h.

◆ SFRTrait

typedef Map<NodeID, std::pair<NodeID, NodeSet> > SVF::AndersenSFR::SFRTrait

Definition at line 107 of file AndersenPWC.h.

Constructor & Destructor Documentation

◆ AndersenSFR()

SVF::AndersenSFR::AndersenSFR	(	SVFIR *	_pag,
		PTATY	type = `AndersenSFR_WPA`
	)

inline

Definition at line 117 of file AndersenPWC.h.

                                                           :
        AndersenSCD(_pag, type), csc(nullptr)
    {
    }

◆ ~AndersenSFR()

SVF::AndersenSFR::~AndersenSFR ( )

inline

Definition at line 140 of file AndersenPWC.h.

    {
        if (csc != nullptr)
        {
            delete(csc);
            csc = nullptr;
        }
    }

Member Function Documentation

◆ createAndersenSFR()

static AndersenSFR * SVF::AndersenSFR::createAndersenSFR ( SVFIR * _pag )

inlinestatic

Create an singleton instance directly instead of invoking llvm pass manager.

Definition at line 123 of file AndersenPWC.h.

    {
        if (sfrAndersen == nullptr)
        {
            sfrAndersen = new AndersenSFR(_pag);
            sfrAndersen->analyze();
            return sfrAndersen;
        }
        return sfrAndersen;
    }

◆ fieldExpand()

void AndersenSFR::fieldExpand	(	NodeSet &	initials,
		APOffset	offset,
		NodeBS &	strides,
		PointsTo &	expandPts
	)

protected

Expand field IDs in target pts based on the initials and offsets

Definition at line 120 of file AndersenSFR.cpp.

{
    numOfFieldExpand++;
 
    while (!initials.empty())
    {
        NodeID init = *initials.begin();
        initials.erase(init);
 
        if (consCG->isBlkObjOrConstantObj(init))
            expandPts.set(init);
        else
        {
            PAGNode* initPN = pag->getGNode(init);
            const MemObj* obj = pag->getBaseObj(init);
            const u32_t maxLimit = obj->getMaxFieldOffsetLimit();
            APOffset initOffset;
            if (GepObjVar *gepNode = SVFUtil::dyn_cast<GepObjVar>(initPN))
                initOffset = gepNode->getConstantFieldIdx();
            else if (SVFUtil::isa<BaseObjVar, DummyObjVar>(initPN))
                initOffset = 0;
            else
            {
                assert(false && "Not an object node!!");
                abort();
            }
 
            Set<APOffset> offsets;
            offsets.insert(offset);
 
            // calculate offsets
            bool loopFlag = true;
            while (loopFlag)
            {
                loopFlag = false;
                for (auto _f : offsets)
                    for (auto _s : strides)
                    {
                        APOffset _f1 = _f + _s;
                        loopFlag = (offsets.find(_f1) == offsets.end()) && ( (u32_t)(initOffset + _f1) < maxLimit);
                        if (loopFlag)
                            offsets.insert(_f1);
                    }
            }
 
            // get gep objs
            for (APOffset _f : offsets)
            {
                NodeID gepId = consCG->getGepObjVar(init, _f);
                initials.erase(gepId);  // gep id in initials should be removed to avoid redundant derivation
                expandPts.set(gepId);
            }
        }
    }
}

◆ initialize()

void AndersenSFR::initialize ( )

protectedvirtual

Initialize analysis.

 Connect formal and actual parameters for indirect callsites
&zwj;/

void AndersenBase::connectCaller2CalleeParams(const CallICFGNode* cs, const SVFFunction* F, NodePairSet &cpySrcNodes) { assert(F);

DBOUT(DAndersen, outs() << "connect parameters from indirect callsite " << cs->valueOnlyToString() << " to callee " << *F << "\n");

const CallICFGNode* callBlockNode = cs; const RetICFGNode* retBlockNode = cs->getRetICFGNode();

if(SVFUtil::isHeapAllocExtFunViaRet(F) && pag->callsiteHasRet(retBlockNode)) { heapAllocatorViaIndCall(cs,cpySrcNodes); }

if (pag->funHasRet(F) && pag->callsiteHasRet(retBlockNode)) { const PAGNode* cs_return = pag->getCallSiteRet(retBlockNode); const PAGNode* fun_return = pag->getFunRet(F); if (cs_return->isPointer() && fun_return->isPointer()) { NodeID dstrec = sccRepNode(cs_return->getId()); NodeID srcret = sccRepNode(fun_return->getId()); if(addCopyEdge(srcret, dstrec)) { cpySrcNodes.insert(std::make_pair(srcret,dstrec)); } } else { DBOUT(DAndersen, outs() << "not a pointer ignored\n"); } }

if (pag->hasCallSiteArgsMap(callBlockNode) && pag->hasFunArgsList(F)) {

connect actual and formal param const SVFIR::SVFVarList& csArgList = pag->getCallSiteArgsList(callBlockNode); const SVFIR::SVFVarList& funArgList = pag->getFunArgsList(F); Go through the fixed parameters. DBOUT(DPAGBuild, outs() << " args:"); SVFIR::SVFVarList::const_iterator funArgIt = funArgList.begin(), funArgEit = funArgList.end(); SVFIR::SVFVarList::const_iterator csArgIt = csArgList.begin(), csArgEit = csArgList.end(); for (; funArgIt != funArgEit; ++csArgIt, ++funArgIt) { Some programs (e.g. Linux kernel) leave unneeded parameters empty. if (csArgIt == csArgEit) { DBOUT(DAndersen, outs() << " !! not enough args\n"); break; } const PAGNode *cs_arg = *csArgIt ; const PAGNode *fun_arg = *funArgIt;

if (cs_arg->isPointer() && fun_arg->isPointer()) { DBOUT(DAndersen, outs() << "process actual parm " << cs_arg->toString() << " \n"); NodeID srcAA = sccRepNode(cs_arg->getId()); NodeID dstFA = sccRepNode(fun_arg->getId()); if(addCopyEdge(srcAA, dstFA)) { cpySrcNodes.insert(std::make_pair(srcAA,dstFA)); } } }

Any remaining actual args must be varargs. if (F->isVarArg()) { NodeID vaF = sccRepNode(pag->getVarargNode(F)); DBOUT(DPAGBuild, outs() << "\n varargs:"); for (; csArgIt != csArgEit; ++csArgIt) { const PAGNode *cs_arg = *csArgIt; if (cs_arg->isPointer()) { NodeID vnAA = sccRepNode(cs_arg->getId()); if (addCopyEdge(vnAA,vaF)) { cpySrcNodes.insert(std::make_pair(vnAA,vaF)); } } } } if(csArgIt != csArgEit) { writeWrnMsg("too many args to non-vararg func."); writeWrnMsg("(" + cs->getSourceLoc() + ")"); } } }

void AndersenBase::heapAllocatorViaIndCall(const CallICFGNode* cs, NodePairSet &cpySrcNodes) { assert(cs->getCalledFunction() == nullptr && "not an indirect callsite?"); const RetICFGNode* retBlockNode = cs->getRetICFGNode(); const PAGNode* cs_return = pag->getCallSiteRet(retBlockNode); NodeID srcret; CallSite2DummyValPN::const_iterator it = callsite2DummyValPN.find(cs); if(it != callsite2DummyValPN.end()) { srcret = sccRepNode(it->second); } else { NodeID valNode = pag->addDummyValNode(); NodeID objNode = pag->addDummyObjNode(cs->getType()); addPts(valNode,objNode); callsite2DummyValPN.insert(std::make_pair(cs,valNode)); consCG->addConstraintNode(new ConstraintNode(valNode),valNode); consCG->addConstraintNode(new ConstraintNode(objNode),objNode); srcret = valNode; }

NodeID dstrec = sccRepNode(cs_return->getId()); if(addCopyEdge(srcret, dstrec)) cpySrcNodes.insert(std::make_pair(srcret,dstrec)); }

void AndersenBase::normalizePointsTo() { SVFIR::MemObjToFieldsMap &memToFieldsMap = pag->getMemToFieldsMap(); SVFIR::NodeOffsetMap &GepObjVarMap = pag->getGepObjNodeMap();

clear GepObjVarMap/memToFieldsMap/nodeToSubsMap/nodeToRepMap for redundant gepnodes and remove those nodes from pag for (NodeID n: redundantGepNodes) { NodeID base = pag->getBaseObjVar(n); GepObjVar *gepNode = SVFUtil::dyn_cast<GepObjVar>(pag->getGNode(n)); assert(gepNode && "Not a gep node in redundantGepNodes set"); const APOffset apOffset = gepNode->getConstantFieldIdx(); GepObjVarMap.erase(std::make_pair(base, apOffset)); memToFieldsMap[base].reset(n); cleanConsCG(n);

pag->removeGNode(gepNode); } }

/*! Initialize analysis

Detect and collapse cycles consisting of only copy edges

Initialize worklist

Reimplemented from SVF::Andersen.

Definition at line 42 of file AndersenSFR.cpp.

{
    AndersenSCD::initialize();
    setDetectPWC(false);   // SCC will detect only copy edges
 
    if (!csc)
        csc = new CSC(_graph, scc.get());
 
    getSCCDetector()->find();
    mergeSccCycle();
}

◆ mergeSrcToTgt()

bool AndersenSFR::mergeSrcToTgt	(	NodeID	nodeId,
		NodeID	newRepId
	)

protectedvirtual

merge nodeId to newRepId. Return true if the newRepId is a PWC node

union pts of node to rep

move the edges from node to rep, and remove the node

if find gep edges inside SCC cycle, the rep node will become a PWC node and its pts should be collapsed later.
if the node to be merged is already a PWC node, the rep node will also become a PWC node as it will have a self-cycle gep edge.

set rep and sub relations

Reimplemented from SVF::Andersen.

Definition at line 69 of file AndersenSFR.cpp.

{
    ConstraintNode* node = consCG->getConstraintNode(nodeId);
    if (!node->strides.empty())
    {
        ConstraintNode* newRepNode = consCG->getConstraintNode(newRepId);
        newRepNode->strides |= node->strides;
    }
    return Andersen::mergeSrcToTgt(nodeId, newRepId);
}

◆ processGepPts()

bool AndersenSFR::processGepPts	(	const PointsTo &	pts,
		const GepCGEdge *	edge
	)

protectedvirtual

Propagate point-to set via a gep edge, using SFR

Reimplemented from SVF::Andersen.

Definition at line 84 of file AndersenSFR.cpp.

{
    ConstraintNode* dst = edge->getDstNode();
    NodeID dstId = dst->getId();
 
    if (!dst->strides.empty() && SVFUtil::isa<NormalGepCGEdge>(edge))        // dst is in pwc
    {
        PointsTo tmpDstPts;
        PointsTo srcInits = pts - getPts(dstId);
 
        if (!srcInits.empty())
        {
            NodeSet sortSrcInits;
            for (NodeID ptd : srcInits)
                sortSrcInits.insert(ptd);
 
            APOffset offset = SVFUtil::dyn_cast<NormalGepCGEdge>(edge)->getConstantFieldIdx();
            fieldExpand(sortSrcInits, offset, dst->strides, tmpDstPts);
        }
 
        if (unionPts(dstId, tmpDstPts))
        {
            pushIntoWorklist(dstId);
            return true;
        }
        else
            return false;
    }
    else
        return Andersen::processGepPts(pts, edge);
}

◆ PWCDetect()

void AndersenSFR::PWCDetect ( )

protectedvirtual

Call the PWC stride calculation method of class CSC.

Reimplemented from SVF::AndersenSCD.

Definition at line 59 of file AndersenSFR.cpp.

{
    AndersenSCD::PWCDetect();
    csc->find(getSCCDetector()->topoNodeStack());
}

◆ releaseAndersenSFR()

static void SVF::AndersenSFR::releaseAndersenSFR ( )

inlinestatic

Definition at line 134 of file AndersenPWC.h.

    {
        if (sfrAndersen)
            delete sfrAndersen;
    }

Member Data Documentation

◆ csc

CSC* SVF::AndersenSFR::csc

private

Definition at line 112 of file AndersenPWC.h.

◆ fieldReps

FieldReps SVF::AndersenSFR::fieldReps

private

Definition at line 114 of file AndersenPWC.h.

◆ sfrAndersen

AndersenSFR * AndersenSFR::sfrAndersen = nullptr

staticprivate

Definition at line 110 of file AndersenPWC.h.

◆ sfrObjNodes

NodeSet SVF::AndersenSFR::sfrObjNodes

private

Definition at line 113 of file AndersenPWC.h.

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

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

Public Types

Public Member Functions

Static Public Member Functions

Protected Member Functions

Private Attributes

Static Private Attributes

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ FieldReps

◆ NodeStrides

◆ SFRTrait

Constructor & Destructor Documentation

◆ AndersenSFR()

◆ ~AndersenSFR()

Member Function Documentation

◆ createAndersenSFR()

◆ fieldExpand()

◆ initialize()

◆ mergeSrcToTgt()

◆ processGepPts()

◆ PWCDetect()

◆ releaseAndersenSFR()

Member Data Documentation

◆ csc

◆ fieldReps

◆ sfrAndersen

◆ sfrObjNodes