#include <Andersen.h>

Inheritance diagram for SVF::AndersenBase:

Public Types
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
	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 void	initialize () override
	Initialize analysis.

virtual void	finalize () override
	Finalize analysis.

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)

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

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	unionPts (NodeID id, const PointsTo &target)

virtual bool	unionPts (NodeID id, NodeID ptd)

virtual bool	addPts (NodeID id, NodeID ptd)

virtual void	clearAllPts ()
	Clear all data.

virtual void	expandFIObjs (const PointsTo &pts, PointsTo &expandedPts)
	Expand FI objects.

virtual void	expandFIObjs (const NodeBS &pts, NodeBS &expandedPts)
	TODO: remove repetition.

void	remapPointsToSets (void)
	Remap all points-to sets to use the current mapping.

virtual void	writeToFile (const std::string &filename)
	Interface for analysis result storage on filesystem.

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

virtual void	writePtsResultToFile (std::fstream &f)

virtual void	writeGepObjVarMapToFile (std::fstream &f)

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

virtual void	readPtsResultFromFile (std::ifstream &f)

virtual void	readGepObjVarMapFromFile (std::ifstream &f)

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

AliasResult	alias (const SVFVar V1, const SVFVar V2) override
	Interface expose to users of our pointer analysis, given Value infos.

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

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

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

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

void	dumpTopLevelPtsTo () override

void	dumpAllPts () override

bool	mayAlias (const SVFVar V1, const SVFVar V2)

bool	mayAlias (NodeID node1, NodeID node2)

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

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

CallGraph *	getCallGraph () const
	Return call graph.

CallGraphSCC *	getCallGraphSCC () const
	Return call graph SCC.

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

PTATY	getAnalysisTy () const
	Type of pointer analysis.

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

bool	printStat ()
	Whether print statistics.

void	disablePrintStat ()
	Whether print statistics.

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

bool	hasIndCSCallees (const CallICFGNode *cs) const

const FunctionSet &	getIndCSCallees (const CallICFGNode *cs) const

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

void	callGraphSCCDetection ()
	PTACallGraph SCC related methods.

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

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

bool	isInRecursion (const FunObjVar *fun) const

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

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.

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

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

virtual NodeBS	getMayAliases (NodeID node)

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

bool	mayAlias (NodeID node1, NodeID node2)

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

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

void	printIndCSTargets ()

void	dumpAllTypes ()

void	dumpStat ()
	Dump the statistics.

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

bool	containConstantNode (const PointsTo &pts)

virtual bool	isBlkObjOrConstantObj (NodeID ptd) const

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

bool	isArrayMemObj (NodeID id) const

bool	isFIObjNode (NodeID id) const

NodeID	getBaseObjVarID (NodeID id)

NodeID	getFIObjVar (NodeID id)

NodeID	getGepObjVar (NodeID id, const APOffset &ap)

virtual const NodeBS &	getAllFieldsObjVars (NodeID id)

void	setObjFieldInsensitive (NodeID id)

bool	isFieldInsensitive (NodeID id) const

Static Public Member Functions
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)

Public Attributes
NodeBS	redundantGepNodes

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

Static Public Attributes
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 Member Functions
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 ()
	SCC detection.

virtual NodeStack &	SCCDetect (NodeSet &candidates)

virtual void	initWorklist ()

virtual void	solveWorklist ()

virtual void	processNode (NodeID)
	Following methods are to be implemented in child class, in order to achieve a fully worked PTA.

virtual void	collapseFields ()
	collapse positive weight cycles of a graph

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.

Protected Attributes
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
Static Protected Attributes inherited from SVF::PointerAnalysis
static SVFIR *	pag = nullptr
	SVFIR.

Detailed Description

Definition at line 59 of file Andersen.h.

Member Typedef Documentation

◆ CallSite2DummyValPN

typedef OrderedMap<const CallICFGNode*, NodeID> SVF::AndersenBase::CallSite2DummyValPN

Definition at line 62 of file Andersen.h.

Constructor & Destructor Documentation

◆ AndersenBase()

SVF::AndersenBase::AndersenBase	(	SVFIR *	_pag,
		PTATY	type = `PTATY::Andersen_BASE`,
		bool	alias_check = `true`
	)

inline

Constructor.

Definition at line 67 of file Andersen.h.

        :  BVDataPTAImpl(_pag, type, alias_check), consCG(nullptr)
    {
        iterationForPrintStat = OnTheFlyIterBudgetForStat;
    }

◆ ~AndersenBase()

AndersenBase::~AndersenBase ( )

override

Destructor.

Destructor

Definition at line 73 of file Andersen.cpp.

{
    delete consCG;
    consCG = nullptr;
}

Member Function Documentation

◆ addCopyEdge()

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

pure virtual

Add copy edge on constraint graph.

Implemented in SVF::Andersen, SVF::AndersenSCD, SVF::Steensgaard, and SVF::TypeAnalysis.

◆ analyze()

void AndersenBase::analyze ( )

overridevirtual

Andersen analysis.

Andersen analysis

Implements SVF::PointerAnalysis.

Reimplemented in SVF::TypeAnalysis.

Definition at line 150 of file Andersen.cpp.

{
    if(!Options::ReadAnder().empty())
    {
        readPtsFromFile(Options::ReadAnder());
    }
    else
    {
        if(Options::WriteAnder().empty())
        {
            initialize();
            solveConstraints();
            finalize();
        }
        else
        {
            solveAndwritePtsToFile(Options::WriteAnder());
        }
    }
}

◆ classof() [1/2]

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

inlinestatic

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

Definition at line 107 of file Andersen.h.

    {
        return true;
    }

◆ classof() [2/2]

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

inlinestatic

Definition at line 111 of file Andersen.h.

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

◆ cleanConsCG()

void AndersenBase::cleanConsCG ( NodeID id )

remove redundant gepnodes in constraint graph

Definition at line 197 of file Andersen.cpp.

{
    // Remove only this node from its representative's members. Erasing the whole
    // member set would leave every other member mapped to a representative that no
    // longer lists it, so sccSubNodes would stop being the inverse of sccRepNode.
    consCG->getSubs(consCG->sccRepNode(id)).reset(id);
    for (NodeID sub: consCG->getSubs(id))
        consCG->resetRep(sub);
    consCG->resetSubs(id);
    consCG->resetRep(id);
    assert(!consCG->hasGNode(id) && "this is either a rep nodeid or a sub nodeid should have already been merged to its field-insensitive base! ");
}

◆ connectCaller2CalleeParams()

virtual void SVF::AndersenBase::connectCaller2CalleeParams	(	const CallICFGNode *	cs,
		const FunObjVar *	F,
		NodePairSet &	cpySrcNodes
	)

virtual

Connect formal and actual parameters for indirect callsites.

◆ connectCaller2ForkedFunParams()

void AndersenBase::connectCaller2ForkedFunParams	(	const CallICFGNode *	cs,
		const FunObjVar *	F,
		NodePairSet &	cpySrcNodes
	)

virtual

Connect formal and actual parameters for indirect forksites.

Connect formal and actual parameters for indirect forksites

Definition at line 264 of file Andersen.cpp.

{
    assert(F);
 
    DBOUT(DAndersen, outs() << "connect parameters from indirect forksite "
          << cs->valueOnlyToString() << " to forked function "
          << *F << "\n");
 
    ThreadCallGraph *tdCallGraph = SVFUtil::dyn_cast<ThreadCallGraph>(callgraph);
 
    const PAGNode *cs_arg = tdCallGraph->getThreadAPI()->getActualParmAtForkSite(cs);
    const PAGNode *fun_arg = tdCallGraph->getThreadAPI()->getFormalParmOfForkedFun(F);
 
    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));
        }
    }
}

◆ finalize()

void AndersenBase::finalize ( )

overridevirtual

Finalize analysis.

Finalize analysis

dump constraint graph if PAGDotGraph flag is enabled

Reimplemented from SVF::PointerAnalysis.

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

Definition at line 98 of file Andersen.cpp.

{
    if (Options::ConsCGDotGraph())
        consCG->dump("consCG_final");
 
    if (Options::PrintCGGraph())
        consCG->print();
    BVDataPTAImpl::finalize();
}

◆ getConstraintGraph()

ConstraintGraph * SVF::AndersenBase::getConstraintGraph ( )

inline

Get constraint graph.

Definition at line 124 of file Andersen.h.

    {
        return consCG;
    }

◆ heapAllocatorViaIndCall()

void SVF::AndersenBase::heapAllocatorViaIndCall	(	const CallICFGNode *	cs,
		NodePairSet &	cpySrcNodes
	)

protected

◆ initialize()

void AndersenBase::initialize ( )

overridevirtual

Initialize analysis.

Initialize analysis

Build SVFIR

Create statistic class

Build Constraint Graph

Reimplemented from SVF::PointerAnalysis.

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

Definition at line 82 of file Andersen.cpp.

{
    PointerAnalysis::initialize();
    stat = new AndersenStat(this);
    consCG = new ConstraintGraph(pag);
    setGraph(consCG);
    if (Options::ConsCGDotGraph())
        consCG->dump("consCG_initial");
}

◆ normalizePointsTo()

virtual void SVF::AndersenBase::normalizePointsTo ( )

overridevirtual

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

◆ printStat()

void SVF::AndersenBase::printStat ( )

inline

dump statistics

Definition at line 145 of file Andersen.h.

    {
        PointerAnalysis::dumpStat();
    }

◆ readPtsFromFile()

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

virtual

Andersen analysis: read pointer analysis result from file

Definition at line 174 of file Andersen.cpp.

{
    initialize();
    if (!filename.empty())
        this->readFromFile(filename);
    finalize();
}

◆ sccRepNode()

NodeID SVF::AndersenBase::sccRepNode ( NodeID id ) const

inlineoverridevirtual

SCC methods.

Reimplemented from SVF::WPASolver< GraphType >.

Reimplemented in SVF::Steensgaard.

Definition at line 131 of file Andersen.h.

    {
        return consCG->sccRepNode(id);
    }

◆ sccSubNodes()

NodeBS & SVF::AndersenBase::sccSubNodes ( NodeID repId )

inline

Definition at line 135 of file Andersen.h.

    {
        return consCG->sccSubNodes(repId);
    }

◆ solveAndwritePtsToFile()

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

virtual

Andersen analysis: solve constraints and write pointer analysis result to file

Initialization for the Solver

Definition at line 185 of file Andersen.cpp.

{
    initialize();
    if (!filename.empty())
        this->writeObjVarToFile(filename);
    solveConstraints();
    if (!filename.empty())
        this->writeToFile(filename);
    finalize();
}

◆ solveConstraints()

void AndersenBase::solveConstraints ( )

virtual

Definition at line 109 of file Andersen.cpp.

{
    // Start solving constraints
    DBOUT(DGENERAL, outs() << SVFUtil::pasMsg("Start Solving Constraints\n"));
 
    bool timeLimited = Options::AnderTimeLimit() > 0;
    if (timeLimited)
    {
        assert(Options::FsTimeLimit() == 0 && "both -ander-time-limit and -fs-time-limit set.");
        SVFUtil::startAnalysisLimitTimer(Options::AnderTimeLimit());
    }
 
    initWorklist();
    do
    {
        numOfIteration++;
        if (0 == numOfIteration % iterationForPrintStat)
            printStat();
 
        reanalyze = false;
 
        solveWorklist();
 
        if (updateCallGraph(getIndirectCallsites()))
            reanalyze = true;
 
    }
    while (reanalyze);
 
    // Analysis is finished, reset the alarm if we set it.
    if (timeLimited)
    {
        SVFUtil::stopAnalysisLimitTimer();
    }
 
    DBOUT(DGENERAL, outs() << SVFUtil::pasMsg("Finish Solving Constraints\n"));
}

◆ updateCallGraph()

bool AndersenBase::updateCallGraph ( const CallSiteToFunPtrMap & callsites )

overridevirtual

Update call graph.

nodes as a src of a generated new copy edge

Reimplemented from SVF::BVDataPTAImpl.

Reimplemented in SVF::AndersenSCD.

Definition at line 210 of file Andersen.cpp.

{
 
    double cgUpdateStart = stat->getClk();
 
    CallEdgeMap newEdges;
    onTheFlyCallGraphSolve(callsites, newEdges);
    NodePairSet cpySrcNodes; 
    for (CallEdgeMap::iterator it = newEdges.begin(), eit = newEdges.end();
            it != eit; ++it)
    {
        for (FunctionSet::iterator cit = it->second.begin(),
                ecit = it->second.end();
                cit != ecit; ++cit)
        {
            connectCaller2CalleeParams(it->first, *cit, cpySrcNodes);
        }
    }
 
    bool hasNewForkEdges = updateThreadCallGraph(callsites, cpySrcNodes);
 
    for (NodePairSet::iterator it = cpySrcNodes.begin(),
            eit = cpySrcNodes.end();
            it != eit; ++it)
    {
        pushIntoWorklist(it->first);
    }
 
    double cgUpdateEnd = stat->getClk();
    timeOfUpdateCallGraph += (cgUpdateEnd - cgUpdateStart) / TIMEINTERVAL;
 
    return ((!newEdges.empty()) || hasNewForkEdges);
}

◆ updateThreadCallGraph()

bool AndersenBase::updateThreadCallGraph	(	const CallSiteToFunPtrMap &	callsites,
		NodePairSet &	cpySrcNodes
	)

virtual

Update thread call graph.

Definition at line 244 of file Andersen.cpp.

{
    CallEdgeMap newForkEdges;
    onTheFlyThreadCallGraphSolve(callsites, newForkEdges);
    for (CallEdgeMap::iterator it = newForkEdges.begin(), eit = newForkEdges.end(); it != eit; it++)
    {
        for (FunctionSet::iterator cit = it->second.begin(),
                ecit = it->second.end();
                cit != ecit; ++cit)
        {
            connectCaller2ForkedFunParams(it->first, *cit, cpySrcNodes);
        }
    }
    return !newForkEdges.empty();
}

Member Data Documentation

◆ AveragePointsToSetSize

u32_t AndersenBase::AveragePointsToSetSize = 0

static

Definition at line 171 of file Andersen.h.

◆ callsite2DummyValPN

CallSite2DummyValPN SVF::AndersenBase::callsite2DummyValPN

protected

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

Definition at line 182 of file Andersen.h.

◆ consCG

ConstraintGraph* SVF::AndersenBase::consCG

protected

Constraint Graph.

Definition at line 180 of file Andersen.h.

◆ MaxPointsToSetSize

u32_t AndersenBase::MaxPointsToSetSize = 0

static

Definition at line 172 of file Andersen.h.

◆ numOfFieldExpand

u32_t AndersenBase::numOfFieldExpand = 0

static

Definition at line 165 of file Andersen.h.

◆ numOfProcessedAddr

u32_t AndersenBase::numOfProcessedAddr = 0

static

Statistics.

Definition at line 159 of file Andersen.h.

◆ numOfProcessedCopy

u32_t AndersenBase::numOfProcessedCopy = 0

static

Number of processed Addr edge.

Definition at line 160 of file Andersen.h.

◆ numOfProcessedGep

u32_t AndersenBase::numOfProcessedGep = 0

static

Number of processed Copy edge.

Definition at line 161 of file Andersen.h.

◆ numOfProcessedLoad

u32_t AndersenBase::numOfProcessedLoad = 0

static

Number of processed Gep edge.

Definition at line 162 of file Andersen.h.

◆ numOfProcessedStore

u32_t AndersenBase::numOfProcessedStore = 0

static

Number of processed Load edge.

Definition at line 163 of file Andersen.h.

◆ numOfSCCDetection

u32_t AndersenBase::numOfSCCDetection = 0

static

Definition at line 167 of file Andersen.h.

◆ numOfSfrs

u32_t AndersenBase::numOfSfrs = 0

static

Number of processed Store edge.

Definition at line 164 of file Andersen.h.

◆ redundantGepNodes

NodeBS SVF::AndersenBase::redundantGepNodes

Definition at line 155 of file Andersen.h.

◆ timeOfCollapse

double AndersenBase::timeOfCollapse = 0

static

Definition at line 170 of file Andersen.h.

◆ timeOfProcessCopyGep

double AndersenBase::timeOfProcessCopyGep = 0

static

Definition at line 173 of file Andersen.h.

◆ timeOfProcessLoadStore

double AndersenBase::timeOfProcessLoadStore = 0

static

Definition at line 174 of file Andersen.h.

◆ timeOfSCCDetection

double AndersenBase::timeOfSCCDetection = 0

static

Definition at line 168 of file Andersen.h.

◆ timeOfSCCMerges

double AndersenBase::timeOfSCCMerges = 0

static

Definition at line 169 of file Andersen.h.

◆ timeOfUpdateCallGraph

double AndersenBase::timeOfUpdateCallGraph = 0

static

Definition at line 175 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

Public Attributes

Static Public Attributes

Protected Member Functions

Protected Attributes

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ CallSite2DummyValPN

Constructor & Destructor Documentation

◆ AndersenBase()

◆ ~AndersenBase()

Member Function Documentation

◆ addCopyEdge()

◆ analyze()

◆ classof() [1/2]

◆ classof() [2/2]

◆ cleanConsCG()

◆ connectCaller2CalleeParams()

◆ connectCaller2ForkedFunParams()

◆ finalize()

◆ getConstraintGraph()

◆ heapAllocatorViaIndCall()

◆ initialize()

◆ normalizePointsTo()

◆ printStat()

◆ readPtsFromFile()

◆ sccRepNode()

◆ sccSubNodes()

◆ solveAndwritePtsToFile()

◆ solveConstraints()

◆ updateCallGraph()

◆ updateThreadCallGraph()

Member Data Documentation

◆ AveragePointsToSetSize

◆ callsite2DummyValPN

◆ consCG

◆ MaxPointsToSetSize

◆ numOfFieldExpand

◆ numOfProcessedAddr

◆ numOfProcessedCopy

◆ numOfProcessedGep

◆ numOfProcessedLoad

◆ numOfProcessedStore

◆ numOfSCCDetection

◆ numOfSfrs

◆ redundantGepNodes

◆ timeOfCollapse

◆ timeOfProcessCopyGep

◆ timeOfProcessLoadStore

◆ timeOfSCCDetection

◆ timeOfSCCMerges

◆ timeOfUpdateCallGraph