#include <Andersen.h>

Inheritance diagram for SVF::Andersen:

Public Types
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
typedef PTData< NodeID, NodeSet, NodeID, PointsTo >	PTDataTy

typedef DiffPTData< NodeID, NodeSet, NodeID, PointsTo >	DiffPTDataTy

typedef DFPTData< NodeID, NodeSet, NodeID, PointsTo >	DFPTDataTy

typedef VersionedPTData< NodeID, NodeSet, NodeID, PointsTo, VersionedVar, Set< VersionedVar > >	VersionedPTDataTy

typedef MutablePTData< NodeID, NodeSet, NodeID, PointsTo >	MutPTDataTy

typedef MutableDiffPTData< NodeID, NodeSet, NodeID, PointsTo >	MutDiffPTDataTy

typedef MutableDFPTData< NodeID, NodeSet, NodeID, PointsTo >	MutDFPTDataTy

typedef MutableIncDFPTData< NodeID, NodeSet, NodeID, PointsTo >	MutIncDFPTDataTy

typedef MutableVersionedPTData< NodeID, NodeSet, NodeID, PointsTo, VersionedVar, Set< VersionedVar > >	MutVersionedPTDataTy

typedef PersistentPTData< NodeID, NodeSet, NodeID, PointsTo >	PersPTDataTy

typedef PersistentDiffPTData< NodeID, NodeSet, NodeID, PointsTo >	PersDiffPTDataTy

typedef PersistentDFPTData< NodeID, NodeSet, NodeID, PointsTo >	PersDFPTDataTy

typedef PersistentIncDFPTData< NodeID, NodeSet, NodeID, PointsTo >	PersIncDFPTDataTy

typedef PersistentVersionedPTData< NodeID, NodeSet, NodeID, PointsTo, VersionedVar, Set< VersionedVar > >	PersVersionedPTDataTy

Public Types inherited from SVF::PointerAnalysis
typedef Set< const CallICFGNode * >	CallSiteSet
	Indirect call edges type, map a callsite to a set of callees.

typedef SVFIR::CallSiteToFunPtrMap	CallSiteToFunPtrMap

typedef Set< const FunObjVar * >	FunctionSet

typedef OrderedMap< const CallICFGNode *, FunctionSet >	CallEdgeMap

typedef SCCDetection< CallGraph * >	CallGraphSCC

typedef Set< const GlobalObjVar * >	VTableSet

typedef Set< const FunObjVar * >	VFunSet

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

virtual	~Andersen ()
	Destructor.

virtual void	initialize ()
	Initialize analysis.

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)

virtual NodeBS	getMayAliases (NodeID node)
	Collect exactly the SVFIR nodes q for which mayAlias(node, q) holds.

std::vector< NodeBS >	getMayAliasesBatch (const std::vector< NodeID > &nodes)

void	dumpTopLevelPtsTo ()

void	setDetectPWC (bool flag)

Public Member Functions inherited from SVF::AndersenBase
	AndersenBase (SVFIR *_pag, PTATY type=PTATY::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	updateCallGraph (const CallSiteToFunPtrMap &) override
	Update call graph.

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

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

virtual void	connectCaller2CalleeParams (const CallICFGNode cs, const FunObjVar 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, 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 SVFVar V1, const SVFVar V2) override
	Interface expose to users of our pointer analysis, given Value infos.

AliasResult	alias (NodeID node1, NodeID node2) override
	Interface expose to users of our pointer analysis, given PAGNodeID.

virtual AliasResult	alias (const PointsTo &pts1, const PointsTo &pts2)
	Interface expose to users of our pointer analysis, given two pts.

bool	mayAlias (const PointsTo &pts1, const PointsTo &pts2)
	Convenience bool wrappers: return true if the two operands may/must/partial alias.

void	dumpCPts () override
	dump and debug, print out conditional pts

void	dumpTopLevelPtsTo () override

void	dumpAllPts () override

bool	mayAlias (const SVFVar V1, const SVFVar V2)

bool	mayAlias (NodeID node1, NodeID node2)

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

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

CallGraph *	getCallGraph () const
	Return call graph.

CallGraphSCC *	getCallGraphSCC () const
	Return call graph SCC.

	PointerAnalysis (SVFIR *pag, PTATY ty=PTATY::Default_PTA, bool alias_check=true)
	Constructor.

PTATY	getAnalysisTy () const
	Type of pointer analysis.

PTAImplTy	getImplTy () const
	Return implementation type of the pointer analysis.

bool	printStat ()
	Whether print statistics.

void	disablePrintStat ()
	Whether print statistics.

CallEdgeMap &	getIndCallMap ()
	Get callees from an indirect callsite.

bool	hasIndCSCallees (const CallICFGNode *cs) const

const FunctionSet &	getIndCSCallees (const CallICFGNode *cs) const

virtual void	resolveIndCalls (const CallICFGNode *cs, const PointsTo &target, CallEdgeMap &newEdges)
	Resolve indirect call edges.

void	callGraphSCCDetection ()
	PTACallGraph SCC related methods.

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

bool	inSameCallGraphSCC (const FunObjVar fun1, const FunObjVar fun2)
	Return TRUE if this edge is inside a PTACallGraph SCC, i.e., src node and dst node are in the same SCC on the SVFG.

bool	isInRecursion (const FunObjVar *fun) const

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

CommonCHGraph *	getCHGraph () const
	get CHGraph

void	getVFnsFromCHA (const CallICFGNode *cs, VFunSet &vfns)

void	getVFnsFromPts (const CallICFGNode *cs, const PointsTo &target, VFunSet &vfns)

void	connectVCallToVFns (const CallICFGNode *cs, const VFunSet &vfns, CallEdgeMap &newEdges)

virtual void	resolveCPPIndCalls (const CallICFGNode *cs, const PointsTo &target, CallEdgeMap &newEdges)
	Resolve cpp indirect call edges.

SVFIR *	getPAG () const

PTAStat *	getStat () const
	Get PTA stat.

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

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

bool	mayAlias (const SVFVar V1, const SVFVar V2)
	Convenience bool wrappers: return true if the two operands may/must/partial alias.

bool	mayAlias (NodeID node1, NodeID node2)

void	printIndCSTargets (const CallICFGNode *cs, const FunctionSet &targets)
	Print targets of a function pointer.

virtual void	dumpPts (NodeID ptr, const PointsTo &pts)

void	printIndCSTargets ()

void	dumpAllTypes ()

void	dumpStat ()
	Dump the statistics.

bool	containBlackHoleNode (const PointsTo &pts)
	Determine whether a points-to contains a black hole or constant node.

bool	containConstantNode (const PointsTo &pts)

virtual bool	isBlkObjOrConstantObj (NodeID ptd) const

bool	isHeapMemObj (NodeID id) const
	Whether this object is heap or array.

bool	isArrayMemObj (NodeID id) const

bool	isFIObjNode (NodeID id) const

NodeID	getBaseObjVarID (NodeID id)

NodeID	getFIObjVar (NodeID id)

NodeID	getGepObjVar (NodeID id, const APOffset &ap)

virtual const NodeBS &	getAllFieldsObjVars (NodeID id)

void	setObjFieldInsensitive (NodeID id)

bool	isFieldInsensitive (NodeID id) const

Static Public Member Functions
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
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	handleCopyGep (ConstraintNode *node)

virtual void	handleLoadStore (ConstraintNode *node)

virtual void	processAddr (const AddrCGEdge *addr)

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

virtual bool	addCopyEdge (NodeID src, NodeID dst)
	Add copy edge on constraint graph.

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

virtual bool	mergeSrcToTgt (NodeID srcId, NodeID tgtId)

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.

virtual NodeStack &	SCCDetect ()
	SCC detection.

std::optional< NodeBS >	collectMayAliasesFromIndex (const PointsTo &expandedPts)

virtual void	validateSuccessTests (std::string fun)
	Also check getMayAliases on the pointers that the alias tests use.

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

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	validateExpectedFailureTests (std::string fun)

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

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

PTATY	ptaTy
	Pointer analysis Type.

PTAImplTy	ptaImplTy
	PTA implementation type.

PTAStat *	stat
	Statistics.

CallGraph *	callgraph
	Call graph used for pointer analysis.

CallGraphSCC *	callGraphSCC
	SCC for PTACallGraph.

ICFG *	icfg
	Interprocedural control-flow graph.

CommonCHGraph *	chgraph
	CHGraph.

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_"

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

Detailed Description

Inclusion-based Pointer Analysis

Definition at line 192 of file Andersen.h.

Member Typedef Documentation

◆ CGSCC

typedef SCCDetection<ConstraintGraph*> SVF::Andersen::CGSCC

Definition at line 197 of file Andersen.h.

Constructor & Destructor Documentation

◆ Andersen()

SVF::Andersen::Andersen	(	SVFIR *	_pag,
		PTATY	type = `PTATY::Andersen_WPA`,
		bool	alias_check = `true`
	)

inline

Constructor.

Definition at line 200 of file Andersen.h.

        :  AndersenBase(_pag, type, alias_check)
    {
    }

◆ ~Andersen()

virtual SVF::Andersen::~Andersen ( )

inlinevirtual

Destructor.

Definition at line 206 of file Andersen.h.

    {
 
    }

Member Function Documentation

◆ addCopyEdge()

virtual bool SVF::Andersen::addCopyEdge	(	NodeID	src,
		NodeID	dst
	)

inlineprotectedvirtual

Add copy edge on constraint graph.

Implements SVF::AndersenBase.

Reimplemented in SVF::AndersenSCD.

Definition at line 338 of file Andersen.h.

    {
        if (consCG->addCopyCGEdge(src, dst))
        {
            updatePropaPts(src, dst);
            return true;
        }
        return false;
    }

◆ classof() [1/2]

static bool SVF::Andersen::classof ( const Andersen * )

inlinestatic

Methods for support type inquiry through isa, cast, and dyn_cast:

Definition at line 228 of file Andersen.h.

    {
        return true;
    }

◆ classof() [2/2]

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

inlinestatic

Definition at line 232 of file Andersen.h.

    {
        return (pta->getAnalysisTy() == PTATY::Andersen_WPA
                || pta->getAnalysisTy() == PTATY::AndersenWaveDiff_WPA
                || pta->getAnalysisTy() == PTATY::AndersenSCD_WPA
                || pta->getAnalysisTy() == PTATY::AndersenSFR_WPA);
    }

◆ clearPropaPts()

void SVF::Andersen::clearPropaPts ( NodeID src )

inlineprotected

Definition at line 309 of file Andersen.h.

    {
        if (Options::DiffPts())
        {
            NodeID rep = sccRepNode(src);
            getDiffPTDataTy()->clearPropaPts(rep);
        }
    }

◆ cluster()

void Andersen::cluster ( void ) const

protectedvirtual

Runs a Steensgaard analysis and performs clustering based on those results set the global best mapping.

Definition at line 1121 of file Andersen.cpp.

{
    assert(Options::MaxFieldLimit() == 0 && "Andersen::cluster: clustering for Andersen's is currently only supported in field-insensitive analysis");
    Steensgaard *steens = Steensgaard::createSteensgaard(pag);
    std::vector<std::pair<unsigned, unsigned>> keys;
    for (SVFIR::iterator pit = pag->begin(); pit != pag->end(); ++pit)
    {
        keys.push_back(std::make_pair(pit->first, 1));
    }
 
    std::vector<std::pair<hclust_fast_methods, std::vector<NodeID>>> candidates;
    PointsTo::MappingPtr nodeMapping =
        std::make_shared<std::vector<NodeID>>(
            NodeIDAllocator::Clusterer::cluster(steens, keys, candidates, "aux-steens", print_stat)
        );
    PointsTo::MappingPtr reverseNodeMapping =
        std::make_shared<std::vector<NodeID>>(NodeIDAllocator::Clusterer::getReverseNodeMapping(*nodeMapping));
 
    PointsTo::setCurrentBestNodeMapping(nodeMapping, reverseNodeMapping);
}

◆ collapseField()

bool Andersen::collapseField ( NodeID nodeId )

protected

Collapse field. make struct with the same base as nodeId become field-insensitive.

Black hole doesn't have structures, no collapse is needed. In later versions, instead of using base node to represent the struct, we'll create new field-insensitive node. To avoid creating a new "black hole" node, do not collapse field for black hole node.

Definition at line 791 of file Andersen.cpp.

{
    if (consCG->isBlkObjOrConstantObj(nodeId))
        return false;
 
    bool changed = false;
 
    double start = stat->getClk();
 
    // set base node field-insensitive.
    setObjFieldInsensitive(nodeId);
 
    // replace all occurrences of each field with the field-insensitive node
    NodeID baseId = consCG->getFIObjVar(nodeId);
    NodeID baseRepNodeId = consCG->sccRepNode(baseId);
    NodeBS & allFields = consCG->getAllFieldsObjVars(baseId);
    for (NodeBS::iterator fieldIt = allFields.begin(), fieldEit = allFields.end(); fieldIt != fieldEit; fieldIt++)
    {
        NodeID fieldId = *fieldIt;
        if (fieldId != baseId)
        {
            // use the reverse pts of this field node to find all pointers point to it
            const NodeSet revPts = getRevPts(fieldId);
            for (const NodeID o : revPts)
            {
                // change the points-to target from field to base node
                clearPts(o, fieldId);
                addPts(o, baseId);
                pushIntoWorklist(o);
 
                changed = true;
            }
            // merge field node into base node, including edges and pts.
            NodeID fieldRepNodeId = consCG->sccRepNode(fieldId);
            mergeNodeToRep(fieldRepNodeId, baseRepNodeId);
            if (fieldId != baseRepNodeId)
            {
                // gep node fieldId becomes redundant if it is merged to its base node who is set as field-insensitive
                // two node IDs should be different otherwise this field is actually the base and should not be removed.
                redundantGepNodes.set(fieldId);
            }
        }
    }
 
    if (consCG->isPWCNode(baseRepNodeId))
        if (collapseNodePts(baseRepNodeId))
            changed = true;
 
    double end = stat->getClk();
    timeOfCollapse += (end - start) / TIMEINTERVAL;
 
    return changed;
}

◆ collapseFields()

void Andersen::collapseFields ( )

protectedvirtual

collapse positive weight cycles of a graph

Reimplemented from SVF::WPASolver< GraphType >.

Definition at line 717 of file Andersen.cpp.

{
    while (consCG->hasNodesToBeCollapsed())
    {
        NodeID node = consCG->getNextCollapseNode();
        // collapseField() may change the points-to set of the nodes which have been processed
        // before, in this case, we may need to re-do the analysis.
        if (collapseField(node))
            reanalyze = true;
    }
}

◆ collapseNodePts()

bool Andersen::collapseNodePts ( NodeID nodeId )

protected

Collapse node's points-to set. Change all points-to elements into field-insensitive.

Points to set may be changed during collapse, so use a clone instead.

Definition at line 771 of file Andersen.cpp.

{
    bool changed = false;
    const PointsTo& nodePts = getPts(nodeId);
    PointsTo ptsClone = nodePts;
    for (PointsTo::iterator ptsIt = ptsClone.begin(), ptsEit = ptsClone.end(); ptsIt != ptsEit; ptsIt++)
    {
        if (isFieldInsensitive(*ptsIt))
            continue;
 
        if (collapseField(*ptsIt))
            changed = true;
    }
    return changed;
}

◆ collapsePWCNode()

void Andersen::collapsePWCNode ( NodeID nodeId )

protectedvirtual

Collapse a field object into its base for field insensitive analysis.

Detect and collapse PWC nodes produced by processing gep edges, under the constraint of field limit.

Definition at line 708 of file Andersen.cpp.

{
    // If a node is a PWC node, collapse all its points-to target.
    // collapseNodePts() may change the points-to set of the nodes which have been processed
    // before, in this case, we may need to re-do the analysis.
    if (consCG->isPWCNode(nodeId) && collapseNodePts(nodeId))
        reanalyze = true;
}

◆ collectMayAliasesFromIndex()

std::optional< NodeBS > Andersen::collectMayAliasesFromIndex ( const PointsTo & expandedPts )

protected

Answer a may-alias query from the reverse points-to sets. Returns nullopt when those sets cannot answer it, leaving the caller to try every node.

Answer a may-alias query from the reverse points-to sets, which say which nodes may point to a given object.

Two nodes may alias exactly when their expanded points-to sets share an object. For every object in this query's expanded set, collect all raw points-to objects whose expansion can contain it: the object itself, its base, and every field of a field-insensitive base. The reverse sets of those objects therefore name the complete answer. The black-hole reverse set supplies nodes that alias everything.

Returns nullopt when reverse points-to sets are unavailable or the query itself points to the black hole, leaving the caller to try every node.

Definition at line 1023 of file Andersen.cpp.

{
    if (!getPTDataTy()->hasReversePts() || containBlackHoleNode(expandedPts))
        return std::nullopt;
 
    NodeBS objects;
    const u32_t nodeBound = pag->getTotalNodeNum();
    for (NodeID object : expandedPts)
    {
        objects.set(object);
        const NodeID base = pag->getBaseObjVarID(object);
        objects.set(base);
        if (isFieldInsensitive(base))
            objects |= pag->getAllFieldsObjVars(base);
    }
    objects.set(pag->getBlackHoleNode());
 
    const size_t wordCount = (static_cast<size_t>(nodeBound) +
                              CoreBitVector::WordSize - 1) / CoreBitVector::WordSize;
    CoreBitVector representatives(wordCount);
    for (NodeID object : objects)
    {
        for (NodeID key : getRevPts(object))
        {
            const NodeID representative = sccRepNode(key);
            // Reverse points-to sets can retain stale postings. Confirm the
            // posting with one current-set bit test before treating it as an
            // alias witness, unless an earlier object already confirmed it.
            if (!representatives.test(representative) &&
                    getPts(representative).test(object))
                representatives.set(representative);
        }
    }
 
    // SCC subnode sets are individually ordered, but their concatenation is
    // not globally ordered. Collect them densely before inserting into the
    // sparse result, where backward insertions would be costly.
    CoreBitVector answer(wordCount);
    for (NodeID representative : representatives)
    {
        for (NodeID subNode : sccSubNodes(representative))
            answer.set(subNode);
    }
 
    // normalizePointsTo can remove field nodes while their ids remain in
    // points-to sets. Do not return those stale nodes.
    NodeBS aliases;
    for (NodeID id : answer)
    {
        if (pag->hasGNode(id))
            aliases.set(id);
    }
    return aliases;
}

◆ computeDiffPts()

virtual void SVF::Andersen::computeDiffPts ( NodeID id )

inlineprotectedvirtual

Handle diff points-to set.

Definition at line 283 of file Andersen.h.

    {
        if (Options::DiffPts())
        {
            NodeID rep = sccRepNode(id);
            getDiffPTDataTy()->computeDiffPts(rep, getDiffPTDataTy()->getPts(rep));
        }
    }

◆ dumpTopLevelPtsTo()

void Andersen::dumpTopLevelPtsTo ( )

virtual

Print pag nodes' pts by an ascending order

Reimplemented from SVF::PointerAnalysis.

Definition at line 1145 of file Andersen.cpp.

{
    for (OrderedNodeSet::iterator nIter = this->getAllValidPtrs().begin();
            nIter != this->getAllValidPtrs().end(); ++nIter)
    {
        const SVFVar* node = getPAG()->getSVFVar(*nIter);
        if (getPAG()->isValidTopLevelPtr(node))
        {
            const PointsTo& pts = this->getPts(node->getId());
            outs() << "\nNodeID " << node->getId() << " ";
 
            if (pts.empty())
            {
                outs() << "\t\tPointsTo: {empty}\n";
            }
            else
            {
                outs() << "\t\tPointsTo: { ";
 
                multiset<u32_t> line;
                for (PointsTo::iterator it = pts.begin(), eit = pts.end();
                        it != eit; ++it)
                {
                    line.insert(*it);
                }
                for (multiset<u32_t>::const_iterator it = line.begin(); it != line.end(); ++it)
                {
                    if(Options::PrintFieldWithBasePrefix())
                        if (auto gepNode = pag->getGepObjVar(*it))
                            outs() << gepNode->getBaseNode() << "_" << gepNode->getConstantFieldIdx() << " ";
                        else
                            outs() << *it << " ";
                    else
                        outs() << *it << " ";
                }
                outs() << "}\n";
            }
        }
    }
 
    outs().flush();
}

◆ finalize()

void Andersen::finalize ( )

virtual

Finalize analysis.

Finalize analysis

sanitize field insensitive obj TODO: Fields has been collapsed during Andersen::collapseField().

Reimplemented from SVF::AndersenBase.

Reimplemented in SVF::AndersenWaveDiff.

Definition at line 452 of file Andersen.cpp.

{
    // TODO: broken
    if (Options::ClusterAnder())
    {
        Map<std::string, std::string> stats;
        const PTDataTy *ptd = getPTDataTy();
        // TODO: should we use liveOnly?
        // TODO: parameterise final arg.
        NodeIDAllocator::Clusterer::evaluate(*PointsTo::getCurrentBestNodeMapping(), ptd->getAllPts(true), stats, true);
        if (print_stat)
        {
            NodeIDAllocator::Clusterer::printStats("post-main", stats);
        }
    }
 
    //  sanitizePts();
    AndersenBase::finalize();
}

◆ getDiffPts()

virtual const PointsTo & SVF::Andersen::getDiffPts ( NodeID id )

inlineprotectedvirtual

Definition at line 291 of file Andersen.h.

    {
        NodeID rep = sccRepNode(id);
        if (Options::DiffPts())
            return getDiffPTDataTy()->getDiffPts(rep);
        else
            return getPTDataTy()->getPts(rep);
    }

◆ getMayAliases()

NodeBS Andersen::getMayAliases ( NodeID node )

virtual

Collect exactly the SVFIR nodes q for which mayAlias(node, q) holds.

Collect every SVFIR node that may alias the given node.

Reimplemented from SVF::PointerAnalysis.

Definition at line 938 of file Andersen.cpp.

{
    // Reuse this expansion for the index lookup and, when necessary, every
    // comparison in the exhaustive fallback.
    PointsTo expandedPts;
    expandFIObjs(getPts(node), expandedPts);
    if (auto aliases = collectMayAliasesFromIndex(expandedPts))
        return std::move(*aliases);
 
    NodeBS aliases;
    const bool queryPointsToBlackHole = containBlackHoleNode(expandedPts);
    for (SVFIR::iterator it = pag->begin(), eit = pag->end(); it != eit; ++it)
    {
        const NodeID candidate = it->first;
        if (queryPointsToBlackHole)
        {
            aliases.set(candidate);
            continue;
        }
 
        PointsTo candidatePts;
        expandFIObjs(getPts(candidate), candidatePts);
        if (containBlackHoleNode(candidatePts) ||
                expandedPts.intersects(candidatePts))
            aliases.set(candidate);
    }
    return aliases;
}

◆ getMayAliasesBatch()

std::vector< NodeBS > Andersen::getMayAliasesBatch ( const std::vector< NodeID > & nodes )

Query multiple pointers, reusing answers for equal points-to sets within this call.

Parameters

nodes Input SVFIR node IDs in query order.

Returns: One owned alias set per input: result[i] equals getMayAliases(nodes[i]). Duplicates are preserved; empty input returns an empty vector. The analysis, SVFIR, SCCs and points-to mapping must stay unchanged during the call. Equal points-to sets must imply equal answers, including in subclass overrides. Cache limits exclude the returned results; split large inputs to limit output storage.

Reuse answers only within a batch whose analysis state is unchanged. For example, queries for p and q with pts(p) = pts(q) = {o} need the same reverse-index walk. Keep the cache local so later batches and scalar queries observe current state.

Definition at line 972 of file Andersen.cpp.

{
    std::vector<NodeBS> results;
    results.reserve(nodes.size());
    Map<PointsTo, NodeBS> answers;
    size_t cachedMembers = 0;
    // Bound the reuse cache separately from the caller-owned results.
    constexpr size_t maxCachedSets = 256;
    constexpr size_t maxCachedMembers = 1 << 20;
    for (NodeID node : nodes)
    {
        const PointsTo& pts = getPts(node);
        auto cached = answers.find(pts);
        if (cached != answers.end())
        {
            results.push_back(cached->second);
            continue;
        }
 
        NodeBS aliases = getMayAliases(node);
        const size_t members = static_cast<size_t>(pts.count()) + aliases.count();
        if (members > maxCachedMembers)
        {
            results.push_back(std::move(aliases));
            continue;
        }
        if (answers.size() == maxCachedSets || cachedMembers > maxCachedMembers - members)
        {
            answers.clear();
            cachedMembers = 0;
        }
        auto inserted = answers.emplace(pts, std::move(aliases));
        cachedMembers += members;
        results.push_back(inserted.first->second);
    }
    return results;
}

◆ getPts()

virtual const PointsTo & SVF::Andersen::getPts ( NodeID id )

inlinevirtual

Operation of points-to set.

Implements SVF::PointerAnalysis.

Definition at line 242 of file Andersen.h.

    {
        return getPTDataTy()->getPts(sccRepNode(id));
    }

◆ handleCopyGep()

void Andersen::handleCopyGep ( ConstraintNode * node )

protectedvirtual

Process copy and gep edges

Reimplemented in SVF::AndersenSCD.

Definition at line 498 of file Andersen.cpp.

{
    NodeID nodeId = node->getId();
    computeDiffPts(nodeId);
 
    if (!getDiffPts(nodeId).empty())
    {
        for (ConstraintEdge* edge : node->getCopyOutEdges())
            processCopy(nodeId, edge);
        for (ConstraintEdge* edge : node->getGepOutEdges())
        {
            if (GepCGEdge* gepEdge = SVFUtil::dyn_cast<GepCGEdge>(edge))
                processGep(nodeId, gepEdge);
        }
    }
}

◆ handleLoadStore()

void Andersen::handleLoadStore ( ConstraintNode * node )

protectedvirtual

Process load and store edges

Reimplemented in SVF::AndersenSCD.

Definition at line 518 of file Andersen.cpp.

{
    NodeID nodeId = node->getId();
    for (PointsTo::iterator piter = getPts(nodeId).begin(), epiter =
                getPts(nodeId).end(); piter != epiter; ++piter)
    {
        NodeID ptd = *piter;
        // handle load
        for (ConstraintNode::const_iterator it = node->outgoingLoadsBegin(),
                eit = node->outgoingLoadsEnd(); it != eit; ++it)
        {
            if (processLoad(ptd, *it))
                pushIntoWorklist(ptd);
        }
 
        // handle store
        for (ConstraintNode::const_iterator it = node->incomingStoresBegin(),
                eit = node->incomingStoresEnd(); it != eit; ++it)
        {
            if (processStore(ptd, *it))
                pushIntoWorklist((*it)->getSrcID());
        }
    }
}

◆ initialize()

void Andersen::initialize ( )

virtual

Initialize analysis.

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

void AndersenBase::connectCaller2CalleeParams(const CallICFGNode* cs, const FunObjVar* 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::ValVarList& csArgList = pag->getCallSiteArgsList(callBlockNode); const SVFIR::ValVarList& funArgList = pag->getFunArgsList(F); Go through the fixed parameters. DBOUT(DPAGBuild, outs() << " args:"); SVFIR::ValVarList::const_iterator funArgIt = funArgList.begin(), funArgEit = funArgList.end(); SVFIR::ValVarList::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::OffsetToGepVarMap &GepObjVarMap = pag->getGepObjNodeMap();

clear GepObjVarMap/memToFieldsMap/nodeToSubsMap/nodeToRepMap for redundant gepnodes and remove those nodes from pag for (NodeID n: redundantGepNodes) { NodeID base = pag->getBaseObjVarID(n); const GepObjVar* gepNode = pag->getGepObjVar(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(const_cast<GepObjVar*>(gepNode)); } }

/*! Initialize analysis

Initialize worklist

Reimplemented from SVF::AndersenBase.

Reimplemented in SVF::AndersenWaveDiff, and SVF::AndersenSFR.

Definition at line 438 of file Andersen.cpp.

{
    resetData();
    AndersenBase::initialize();
 
    if (Options::ClusterAnder()) cluster();
 
    processAllAddr();
}

◆ initWorklist()

virtual void SVF::Andersen::initWorklist ( )

inlineprotectedvirtual

Reimplemented from SVF::WPASolver< GraphType >.

Definition at line 318 of file Andersen.h.

318{}

◆ mergeNodeToRep()

void Andersen::mergeNodeToRep	(	NodeID	nodeId,
		NodeID	newRepId
	)

protectedvirtual

Merge sub node to its rep.

Definition at line 907 of file Andersen.cpp.

{
 
    if (mergeSrcToTgt(nodeId,newRepId))
        consCG->setPWCNode(newRepId);
}

◆ mergeSccCycle()

void Andersen::mergeSccCycle ( )

protected

Definition at line 732 of file Andersen.cpp.

{
    NodeStack topoOrder = getSCCDetector()->topoNodeStack();
 
    while (!topoOrder.empty())
    {
        NodeID repNodeId = topoOrder.top();
        topoOrder.pop();
        const NodeBS& subNodes = getSCCDetector()->subNodes(repNodeId);
        // merge sub nodes to rep node
        mergeSccNodes(repNodeId, subNodes);
        if (subNodes.count() > 1)
        {
            pushIntoWorklist(repNodeId);
            reanalyze = true;
        }
    }
}

◆ mergeSccNodes()

void Andersen::mergeSccNodes	(	NodeID	repNodeId,
		const NodeBS &	subNodes
	)

protected

Merge sub node in a SCC cycle to their rep node.

Union points-to of subscc nodes into its rep nodes Move incoming/outgoing direct edges of sub node to rep node

Definition at line 756 of file Andersen.cpp.

{
    for (NodeBS::iterator nodeIt = subNodes.begin(); nodeIt != subNodes.end(); nodeIt++)
    {
        NodeID subNodeId = *nodeIt;
        if (subNodeId != repNodeId)
        {
            mergeNodeToRep(subNodeId, repNodeId);
        }
    }
}

◆ mergeSrcToTgt()

bool Andersen::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 in SVF::AndersenSFR.

Definition at line 876 of file Andersen.cpp.

{
 
    if(nodeId==newRepId)
        return false;
 
    updatePropaPts(newRepId, nodeId);
    unionPts(newRepId,nodeId);
 
    ConstraintNode* node = consCG->getConstraintNode(nodeId);
    bool pwc = consCG->moveEdgesToRepNode(node, consCG->getConstraintNode(newRepId));
 
    if(node->isPWCNode())
        pwc = true;
 
    updateNodeRepAndSubs(node->getId(),newRepId);
 
    consCG->removeConstraintNode(node);
 
    return pwc;
}

◆ processAddr()

void Andersen::processAddr ( const AddrCGEdge * addr )

protectedvirtual

Process address edges

Reimplemented in SVF::AndersenSCD.

Definition at line 560 of file Andersen.cpp.

{
    numOfProcessedAddr++;
 
    NodeID dst = addr->getDstID();
    NodeID src = addr->getSrcID();
    if(addPts(dst,src))
        pushIntoWorklist(dst);
}

◆ processAllAddr()

void Andersen::processAllAddr ( )

protected

handling various constraints

Process address edges

Definition at line 546 of file Andersen.cpp.

{
    for (ConstraintGraph::const_iterator nodeIt = consCG->begin(), nodeEit = consCG->end(); nodeIt != nodeEit; nodeIt++)
    {
        ConstraintNode * cgNode = nodeIt->second;
        for (ConstraintNode::const_iterator it = cgNode->incomingAddrsBegin(), eit = cgNode->incomingAddrsEnd();
                it != eit; ++it)
            processAddr(SVFUtil::cast<AddrCGEdge>(*it));
    }
}

◆ processCopy()

bool Andersen::processCopy	(	NodeID	node,
		const ConstraintEdge *	edge
	)

protectedvirtual

Process copy edges src –copy--> dst, union pts(dst) with pts(src)

Definition at line 615 of file Andersen.cpp.

{
    numOfProcessedCopy++;
 
    assert((SVFUtil::isa<CopyCGEdge>(edge)) && "not copy/call/ret ??");
    NodeID dst = edge->getDstID();
    const PointsTo& srcPts = getDiffPts(node);
 
    bool changed = unionPts(dst, srcPts);
    if (changed)
        pushIntoWorklist(dst);
    return changed;
}

◆ processGep()

bool Andersen::processGep	(	NodeID	node,
		const GepCGEdge *	edge
	)

protectedvirtual

Process gep edges src –gep--> dst, for each srcPtdNode \in pts(src) ==> add fieldSrcPtdNode into tmpDstPts union pts(dst) with tmpDstPts

Definition at line 635 of file Andersen.cpp.

{
    const PointsTo& srcPts = getDiffPts(edge->getSrcID());
    return processGepPts(srcPts, edge);
}

◆ processGepPts()

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

protectedvirtual

Compute points-to for gep edges

Reimplemented in SVF::AndersenSFR.

Definition at line 644 of file Andersen.cpp.

{
    numOfProcessedGep++;
 
    PointsTo tmpDstPts;
    if (SVFUtil::isa<VariantGepCGEdge>(edge))
    {
        // If a pointer is connected by a variant gep edge,
        // then set this memory object to be field insensitive,
        // unless the object is a black hole/constant.
        for (NodeID o : pts)
        {
            if (consCG->isBlkObjOrConstantObj(o))
            {
                tmpDstPts.set(o);
                continue;
            }
 
            if (!isFieldInsensitive(o))
            {
                setObjFieldInsensitive(o);
                consCG->addNodeToBeCollapsed(consCG->getBaseObjVarID(o));
            }
 
            // Add the field-insensitive node into pts.
            NodeID baseId = consCG->getFIObjVar(o);
            tmpDstPts.set(baseId);
        }
    }
    else if (const NormalGepCGEdge* normalGepEdge = SVFUtil::dyn_cast<NormalGepCGEdge>(edge))
    {
        // TODO: after the node is set to field insensitive, handling invariant
        // gep edge may lose precision because offsets here are ignored, and the
        // base object is always returned.
        for (NodeID o : pts)
        {
            if (consCG->isBlkObjOrConstantObj(o) || isFieldInsensitive(o))
            {
                tmpDstPts.set(o);
                continue;
            }
 
            NodeID fieldSrcPtdNode = consCG->getGepObjVar(o, normalGepEdge->getAccessPath().getConstantStructFldIdx());
            tmpDstPts.set(fieldSrcPtdNode);
        }
    }
    else
    {
        assert(false && "Andersen::processGepPts: New type GEP edge type?");
    }
 
    NodeID dstId = edge->getDstID();
    if (unionPts(dstId, tmpDstPts))
    {
        pushIntoWorklist(dstId);
        return true;
    }
 
    return false;
}

◆ processLoad()

bool Andersen::processLoad	(	NodeID	node,
		const ConstraintEdge *	load
	)

protectedvirtual

Process load edges src –load--> dst, node \in pts(src) ==> node–copy-->dst

TODO: New copy edges are also added for black hole obj node to make gcc in spec 2000 pass the flow-sensitive analysis. Try to handle black hole obj in an appropriate way.

Definition at line 575 of file Andersen.cpp.

{
//  if (pag->isBlkObjOrConstantObj(node))
    if (pag->isConstantObj(node) || pag->getSVFVar(load->getDstID())->isPointer() == false)
        return false;
 
    numOfProcessedLoad++;
 
    NodeID dst = load->getDstID();
    return addCopyEdge(node, dst);
}

◆ processNode()

void Andersen::processNode ( NodeID nodeId )

protectedvirtual

Override WPASolver function in order to use the default solver.

Start constraint solving

Reimplemented from SVF::WPASolver< GraphType >.

Reimplemented in SVF::AndersenWaveDiff.

Definition at line 477 of file Andersen.cpp.

{
    // sub nodes do not need to be processed
    if (sccRepNode(nodeId) != nodeId)
        return;
 
    ConstraintNode* node = consCG->getConstraintNode(nodeId);
    double insertStart = stat->getClk();
    handleLoadStore(node);
    double insertEnd = stat->getClk();
    timeOfProcessLoadStore += (insertEnd - insertStart) / TIMEINTERVAL;
 
    double propStart = stat->getClk();
    handleCopyGep(node);
    double propEnd = stat->getClk();
    timeOfProcessCopyGep += (propEnd - propStart) / TIMEINTERVAL;
}

◆ processStore()

bool Andersen::processStore	(	NodeID	node,
		const ConstraintEdge *	store
	)

protectedvirtual

Process store edges src –store--> dst, node \in pts(dst) ==> src–copy-->node

TODO: New copy edges are also added for black hole obj node to make gcc in spec 2000 pass the flow-sensitive analysis. Try to handle black hole obj in an appropriate way

Definition at line 595 of file Andersen.cpp.

{
//  if (pag->isBlkObjOrConstantObj(node))
    if (pag->isConstantObj(node) || pag->getSVFVar(store->getSrcID())->isPointer() == false)
        return false;
 
    numOfProcessedStore++;
 
    NodeID src = store->getSrcID();
    return addCopyEdge(src, node);
}

◆ PTAName()

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

inlineprotectedvirtual

Get PTA name.

Reimplemented from SVF::PointerAnalysis.

Definition at line 404 of file Andersen.h.

    {
        return "AndersenWPA";
    }

◆ resetData()

void SVF::Andersen::resetData ( )

inline

Reset data.

Definition at line 218 of file Andersen.h.

    {
        AveragePointsToSetSize = 0;
        MaxPointsToSetSize = 0;
        timeOfProcessCopyGep = 0;
        timeOfProcessLoadStore = 0;
    }

◆ sanitizePts()

void SVF::Andersen::sanitizePts ( )

inlineprotected

Sanitize pts for field insensitive objects.

Definition at line 382 of file Andersen.h.

    {
        for(ConstraintGraph::iterator it = consCG->begin(), eit = consCG->end(); it!=eit; ++it)
        {
            const PointsTo& pts = getPts(it->first);
            NodeBS fldInsenObjs;
 
            for (NodeID o : pts)
            {
                if(isFieldInsensitive(o))
                    fldInsenObjs.set(o);
            }
 
            for (NodeID o : fldInsenObjs)
            {
                const NodeBS &allFields = consCG->getAllFieldsObjVars(o);
                for (NodeID f : allFields) addPts(it->first, f);
            }
        }
    }

◆ SCCDetect()

NodeStack & Andersen::SCCDetect ( )

protectedvirtual

SCC detection.

SCC detection on constraint graph

Reimplemented from SVF::WPASolver< GraphType >.

Reimplemented in SVF::AndersenSCD.

Definition at line 852 of file Andersen.cpp.

{
    numOfSCCDetection++;
 
    double sccStart = stat->getClk();
    WPAConstraintSolver::SCCDetect();
    double sccEnd = stat->getClk();
 
    timeOfSCCDetection +=  (sccEnd - sccStart)/TIMEINTERVAL;
 
    double mergeStart = stat->getClk();
 
    mergeSccCycle();
 
    double mergeEnd = stat->getClk();
 
    timeOfSCCMerges +=  (mergeEnd - mergeStart)/TIMEINTERVAL;
 
    return getSCCDetector()->topoNodeStack();
}

◆ setDetectPWC()

void SVF::Andersen::setDetectPWC ( bool flag )

inline

Definition at line 273 of file Andersen.h.

    {
        Options::DetectPWC.setValue(flag);
    }

◆ unionPts() [1/2]

virtual bool SVF::Andersen::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 from SVF::BVDataPTAImpl.

Definition at line 246 of file Andersen.h.

    {
        id = sccRepNode(id);
        return getPTDataTy()->unionPts(id, target);
    }

◆ unionPts() [2/2]

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

inlinevirtual

Reimplemented from SVF::BVDataPTAImpl.

Definition at line 251 of file Andersen.h.

    {
        id = sccRepNode(id);
        ptd = sccRepNode(ptd);
        return getPTDataTy()->unionPts(id,ptd);
    }

◆ updateNodeRepAndSubs()

void Andersen::updateNodeRepAndSubs	(	NodeID	nodeId,
		NodeID	newRepId
	)

protected

Updates subnodes of its rep, and rep node of its subs.

update nodeToRepMap, for each subs of current node updates its rep to newRepId

Definition at line 917 of file Andersen.cpp.

{
    consCG->setRep(nodeId,newRepId);
    NodeBS repSubs;
    repSubs.set(nodeId);
    //  update nodeToSubsMap, union its subs with its rep Subs
    NodeBS& nodeSubs = consCG->sccSubNodes(nodeId);
    for(NodeBS::iterator sit = nodeSubs.begin(), esit = nodeSubs.end(); sit!=esit; ++sit)
    {
        NodeID subId = *sit;
        consCG->setRep(subId,newRepId);
    }
    repSubs |= nodeSubs;
    consCG->setSubs(newRepId,repSubs);
    consCG->resetSubs(nodeId);
}

◆ updatePropaPts()

void SVF::Andersen::updatePropaPts	(	NodeID	dstId,
		NodeID	srcId
	)

inlineprotected

Handle propagated points-to set.

Definition at line 301 of file Andersen.h.

    {
        if (!Options::DiffPts())
            return;
        NodeID srcRep = sccRepNode(srcId);
        NodeID dstRep = sccRepNode(dstId);
        getDiffPTDataTy()->updatePropaPtsMap(srcRep, dstRep);
    }

◆ validateSuccessTests()

void Andersen::validateSuccessTests ( std::string fun )

protectedvirtual

Also check getMayAliases on the pointers that the alias tests use.

Run the alias tests, then check getMayAliases on every pointer they use: it must return exactly the nodes that mayAlias reports

Reimplemented from SVF::PointerAnalysis.

Definition at line 1082 of file Andersen.cpp.

{
    AndersenBase::validateSuccessTests(fun);
 
    PointerAnalysis* pta = this;
    const FunObjVar* checkFun = pag->getFunObjVar(fun);
    if (!checkFun)
        return;
    for (const CallICFGNode* callNode : pag->getCallSiteSet())
    {
        if (callNode->getCalledFunction() != checkFun)
            continue;
        std::vector<NodeID> queries;
        for (u32_t i = 0; i < callNode->arg_size(); ++i)
            queries.push_back(callNode->getArgument(i)->getId());
        const std::vector<NodeBS> aliases = getMayAliasesBatch(queries);
        assert(aliases.size() == queries.size() && "getMayAliasesBatch result count mismatch!");
        for (size_t i = 0; i < queries.size(); ++i)
        {
            const NodeID ptr = queries[i];
            NodeBS expected;
            for (SVFIR::iterator it = pag->begin(), eit = pag->end(); it != eit; ++it)
            {
                if (mayAlias(ptr, it->first))
                    expected.set(it->first);
            }
            if (aliases[i] == expected && pta->getMayAliases(ptr) == expected)
                outs() << sucMsg("\t SUCCESS :") << "getMayAliases check <id:" << ptr << "> at ("
                       << callNode->getSourceLoc() << ")\n";
            else
            {
                SVFUtil::errs() << errMsg("\t FAILURE :") << "getMayAliases check <id:" << ptr
                                << "> at (" << callNode->getSourceLoc() << ")\n";
                assert(false && "getMayAliases disagrees with mayAlias!");
            }
        }
    }
}

Member Data Documentation

◆ callsite2DummyValPN

CallSite2DummyValPN SVF::Andersen::callsite2DummyValPN

protected

Map an instruction to a dummy obj which created at an indirect callsite, which invokes a heap allocator.

Definition at line 280 of file Andersen.h.

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

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

Public Types

Public Member Functions

Static Public Member Functions

Protected Member Functions

Protected Attributes

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ CGSCC

Constructor & Destructor Documentation

◆ Andersen()

◆ ~Andersen()

Member Function Documentation

◆ addCopyEdge()

◆ classof() [1/2]

◆ classof() [2/2]

◆ clearPropaPts()

◆ cluster()

◆ collapseField()

◆ collapseFields()

◆ collapseNodePts()

◆ collapsePWCNode()

◆ collectMayAliasesFromIndex()

◆ computeDiffPts()

◆ dumpTopLevelPtsTo()

◆ finalize()

◆ getDiffPts()

◆ getMayAliases()

◆ getMayAliasesBatch()

◆ getPts()

◆ handleCopyGep()

◆ handleLoadStore()

◆ initialize()

◆ initWorklist()

◆ mergeNodeToRep()

◆ mergeSccCycle()

◆ mergeSccNodes()

◆ mergeSrcToTgt()

◆ processAddr()

◆ processAllAddr()

◆ processCopy()

◆ processGep()

◆ processGepPts()

◆ processLoad()

◆ processNode()

◆ processStore()

◆ PTAName()

◆ resetData()

◆ sanitizePts()

◆ SCCDetect()

◆ setDetectPWC()

◆ unionPts() [1/2]

◆ unionPts() [2/2]

◆ updateNodeRepAndSubs()

◆ updatePropaPts()

◆ validateSuccessTests()

Member Data Documentation

◆ callsite2DummyValPN