#include <VersionedFlowSensitive.h>

Inheritance diagram for SVF::VersionedFlowSensitive:

Classes
class	SCC

Public Types
typedef Map< NodeID, Version >	ObjToVersionMap

typedef Map< VersionedVar, const DummyVersionPropSVFGNode * >	VarToPropNodeMap

typedef std::vector< ObjToVersionMap >	LocVersionMap

typedef Map< NodeID, Map< Version, std::vector< Version > > >	VersionRelianceMap
	(o -> (v -> versions with rely on o:v). More...

Public Types inherited from SVF::FlowSensitive
typedef BVDataPTAImpl::MutDFPTDataTy	MutDFPTDataTy

typedef BVDataPTAImpl::MutDFPTDataTy::DFPtsMap	DFInOutMap

typedef BVDataPTAImpl::MutDFPTDataTy::PtsMap	PtsMap

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

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. More...

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
	VersionedFlowSensitive (SVFIR *_pag, PTATY type=VFS_WPA)
	Constructor. More...

virtual void	initialize () override
	Initialize analysis. More...

virtual void	finalize () override
	Finalize analysis. More...

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

Public Member Functions inherited from SVF::FlowSensitive
	FlowSensitive (SVFIR *_pag, PTATY type=FSSPARSE_WPA)
	Constructor. More...

	~FlowSensitive () override=default
	Destructor. More...

virtual bool	runOnModule (SVFModule *)
	We start from here. More...

void	analyze () override
	Flow sensitive analysis. More...

virtual void	solveConstraints ()

SVFG *	getSVFG () const
	Return SVFG. More...

Public Member Functions inherited from SVF::WPAFSSolver< GraphType >
	WPAFSSolver ()
	Constructor. More...

virtual	~WPAFSSolver ()
	Destructor. More...

virtual NodeID	sccRepNode (NodeID id) const
	SCC methods. More...

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

	~BVDataPTAImpl () override=default
	Destructor. More...

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. More...

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

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. More...

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

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

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

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

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. More...

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

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

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

void	dumpTopLevelPtsTo () override

void	dumpAllPts () override

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

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

PTACallGraph *	getCallGraph () const
	Return call graph. More...

CallGraphSCC *	getCallGraphSCC () const
	Return call graph SCC. More...

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

PTATY	getAnalysisTy () const
	Type of pointer analysis. More...

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

bool	printStat ()
	Whether print statistics. More...

void	disablePrintStat ()
	Whether print statistics. More...

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

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. More...

void	callGraphSCCDetection ()
	PTACallGraph SCC related methods. More...

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

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. More...

bool	isInRecursion (const SVFFunction *fun) const

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

CommonCHGraph *	getCHGraph () const
	get CHGraph More...

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. More...

SVFIR *	getPAG () const

PTAStat *	getStat () const
	Get PTA stat. More...

SVFModule *	getModule () const
	Module. More...

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

virtual	~PointerAnalysis ()
	Destructor. More...

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

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

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

void	printIndCSTargets ()

void	dumpAllTypes ()

void	dumpStat ()
	Dump the statistics. More...

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

bool	containConstantNode (const PointsTo &pts)

virtual bool	isBlkObjOrConstantObj (NodeID ptd) const

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

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 VersionedVar	atKey (NodeID, Version)
	Return key into vPtD for address-taken var of a specific version. More...

static bool	classof (const VersionedFlowSensitive *)
	Methods to support type inquiry through isa, cast, and dyn_cast. More...

static bool	classof (const PointerAnalysis *pta)

static VersionedFlowSensitive *	createVFSWPA (SVFIR *_pag)
	Create single instance of versioned flow-sensitive points-to analysis. More...

static void	releaseVFSWPA ()
	Release flow-sensitive pointer analysis. More...

Static Public Member Functions inherited from SVF::FlowSensitive
static FlowSensitive *	createFSWPA (SVFIR *_pag)
	Create single instance of flow-sensitive pointer analysis. More...

static void	releaseFSWPA ()
	Release flow-sensitive pointer analysis. More...

static bool	classof (const FlowSensitive *)
	Methods for support type inquiry through isa, cast, and dyn_cast. More...

static bool	classof (const PointerAnalysis *pta)

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

Static Public Attributes
static const Version	invalidVersion = 0
	If this version appears, there has been an error. More...

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
virtual bool	processLoad (const LoadSVFGNode *load) override

virtual bool	processStore (const StoreSVFGNode *store) override

virtual void	processNode (NodeID n) override
	Handle various constraints. More...

virtual void	updateConnectedNodes (const SVFGEdgeSetTy &newEdges) override
	Update nodes connected during updating call graph. More...

virtual bool	propAlongIndirectEdge (const IndirectSVFGEdge *) override
	Override to do nothing. Instead, we will use propagateVersion when necessary. More...

virtual void	cluster (void) override
	Override since we want to assign different weights based on versioning. More...

Protected Member Functions inherited from SVF::FlowSensitive
NodeStack &	SCCDetect () override
	SCC detection. More...

bool	propFromSrcToDst (SVFGEdge *edge) override
	Propagation. More...

virtual bool	propAlongDirectEdge (const DirectSVFGEdge *edge)
	Propagate points-to information along a DIRECT SVFG edge. More...

virtual bool	propVarPtsFromSrcToDst (NodeID var, const SVFGNode src, const SVFGNode dst)
	Propagate points-to information of a certain variable from src to dst. More...

virtual bool	propagateFromAPToFP (const ActualParmSVFGNode ap, const SVFGNode dst)

virtual bool	propagateFromFRToAR (const FormalRetSVFGNode fr, const SVFGNode dst)

virtual bool	weakUpdateOutFromIn (const SVFGNode *node)
	Handle weak updates. More...

virtual bool	strongUpdateOutFromIn (const SVFGNode *node, NodeID singleton)
	Handle strong updates. More...

bool	propVarPtsAfterCGUpdated (NodeID var, const SVFGNode src, const SVFGNode dst)

virtual bool	propDFOutToIn (const SVFGNode srcStmt, NodeID srcVar, const SVFGNode dstStmt, NodeID dstVar)

virtual bool	propDFInToIn (const SVFGNode srcStmt, NodeID srcVar, const SVFGNode dstStmt, NodeID dstVar)

bool	updateOutFromIn (const SVFGNode srcStmt, NodeID srcVar, const SVFGNode dstStmt, NodeID dstVar)
	Update data-flow points-to data. More...

virtual bool	updateInFromIn (const SVFGNode srcStmt, NodeID srcVar, const SVFGNode dstStmt, NodeID dstVar)

virtual bool	updateInFromOut (const SVFGNode srcStmt, NodeID srcVar, const SVFGNode dstStmt, NodeID dstVar)

virtual bool	unionPtsFromIn (const SVFGNode *stmt, NodeID srcVar, NodeID dstVar)

virtual bool	unionPtsFromTop (const SVFGNode *stmt, NodeID srcVar, NodeID dstVar)

void	clearAllDFOutVarFlag (const SVFGNode *stmt)

bool	processSVFGNode (SVFGNode *node)

virtual bool	processAddr (const AddrSVFGNode *addr)

virtual bool	processCopy (const CopySVFGNode *copy)

virtual bool	processPhi (const PHISVFGNode *phi)

virtual bool	processGep (const GepSVFGNode *edge)

bool	updateCallGraph (const CallSiteToFunPtrMap &callsites) override
	Update call graph. More...

void	connectCallerAndCallee (const CallEdgeMap &newEdges, SVFGEdgeSetTy &edges)
	Connect nodes in SVFG. More...

bool	isStrongUpdate (const SVFGNode *node, NodeID &singleton)
	Return TRUE if this is a strong update STORE statement. More...

virtual void	countAliases (Set< std::pair< NodeID, NodeID >> cmp, unsigned mayAliases, unsigned noAliases)
	Fills may/noAliases for the location/pointer pairs in cmp. More...

const PointsTo &	getDFInPtsSet (const SVFGNode *stmt, const NodeID node)
	Get points-to set for a node from data flow IN/OUT set at a statement. More...

const PointsTo &	getDFOutPtsSet (const SVFGNode *stmt, const NodeID node)

virtual void	plainMap (void) const
	Sets the global best mapping as a plain mapping, i.e. n -> n. More...

void	svfgStat ()

const DFInOutMap &	getDFInputMap () const

const DFInOutMap &	getDFOutputMap () const

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

virtual	~WPASolver ()=default
	Destructor. More...

SCC *	getSCCDetector () const
	Get SCC detector. More...

const GraphType	graph ()
	Get/Set graph methods. More...

void	setGraph (GraphType g)

virtual NodeStack &	SCCDetect (NodeSet &candidates)

virtual void	initWorklist ()

virtual void	solveWorklist ()

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

virtual void	propagate (GNODE *v)

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

NodeID	popFromWorklist ()
	Worklist operations. More...

virtual void	pushIntoWorklist (NodeID id)

bool	isWorklistEmpty ()

bool	isInWorklist (NodeID id)

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

NodeID	Node_Index (GNODE node)
	Get node ID. More...

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

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. More...

virtual void	onTheFlyThreadCallGraphSolve (const CallSiteToFunPtrMap &callsites, CallEdgeMap &newForkEdges)
	On the fly thread call graph construction respecting forksite. More...

virtual void	normalizePointsTo ()

Protected Member Functions inherited from SVF::PointerAnalysis
const CallSiteToFunPtrMap &	getIndirectCallsites () const
	Return all indirect callsites. More...

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

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

virtual void	validateSuccessTests (std::string fun)

virtual void	validateExpectedFailureTests (std::string fun)

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

Private Types
typedef CoreBitVector	MeldVersion

Private Member Functions
void	prelabel (void)
	Prelabel the SVFG: set y(o) for stores and c(o) for delta nodes to a new version. More...

void	meldLabel (void)
	Meld label the prelabeled SVFG. More...

void	removeAllIndirectSVFGEdges (void)
	Removes all indirect edges in the SVFG. More...

void	propagateVersion (NodeID o, Version v)

void	propagateVersion (const NodeID o, const Version v, const Version vp, bool time=true)

virtual void	buildIsStoreLoadMaps (void)
	Fills in isStoreMap and isLoadMap. More...

virtual bool	isStore (const NodeID l) const
	Returns true if l is a store node. More...

virtual bool	isLoad (const NodeID l) const
	Returns true if l is a load node. More...

virtual void	buildDeltaMaps (void)
	Fills in deltaMap and deltaSourceMap for the SVFG. More...

virtual bool	delta (const NodeID l) const

virtual bool	deltaSource (const NodeID l) const

Version	getVersion (const NodeID l, const NodeID o, const LocVersionMap &lvm) const
	Shared code for getConsume and getYield. They wrap this function. More...

Version	getConsume (const NodeID l, const NodeID o) const
	Returns the consumed version of o at l. If no such version exists, returns invalidVersion. More...

Version	getYield (const NodeID l, const NodeID o) const
	Returns the yielded version of o at l. If no such version exists, returns invalidVersion. More...

void	setVersion (const NodeID l, const NodeID o, const Version v, LocVersionMap &lvm)
	Shared code for setConsume and setYield. They wrap this function. More...

void	setConsume (const NodeID l, const NodeID o, const Version v)
	Sets the consumed version of o at l to v. More...

void	setYield (const NodeID l, const NodeID o, const Version v)
	Sets the yielded version of o at l to v. More...

std::vector< Version > &	getReliantVersions (const NodeID o, const Version v)
	Returns the versions of o which rely on o:v. More...

NodeBS &	getStmtReliance (const NodeID o, const Version v)
	Returns the statements which rely on o:v. More...

void	dumpReliances (void) const
	Dumps versionReliance and stmtReliance. More...

void	dumpLocVersionMaps (void) const
	Dumps maps consume and yield. More...

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

void	writeVersionedAnalysisResultToFile (const std::string &filename)

void	readVersionedAnalysisResultFromFile (std::ifstream &F)

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

Static Private Member Functions
static bool	meld (MeldVersion &mv1, const MeldVersion &mv2)
	Melds v2 into v1 (in place), returns whether a change occurred. More...

static void	dumpMeldVersion (MeldVersion &v)
	Dumps a MeldVersion to stdout. More...

Private Attributes
LocVersionMap	consume

LocVersionMap	yield
	Actual yield map. Yield analogue to consume. More...

VersionRelianceMap	versionReliance
	o -> (version -> versions which rely on it). More...

Map< NodeID, Map< Version, NodeBS > >	stmtReliance
	o x version -> statement nodes which rely on that o/version. More...

VarToPropNodeMap	versionedVarToPropNode

Map< NodeID, NodeID >	equivalentObject

FIFOWorkList< NodeID >	vWorklist

Set< NodeID >	prelabeledObjects

BVDataPTAImpl::VersionedPTDataTy *	vPtD
	Points-to DS for working with versions. More...

std::vector< bool >	deltaMap

std::vector< bool >	deltaSourceMap

std::vector< bool >	isStoreMap
	isStoreMap[l] means SVFG node l is a store node. More...

std::vector< bool >	isLoadMap
	isLoadMap[l] means SVFG node l is a load node. More...

u32_t	numPrelabeledNodes
	Additional statistics. More...

u32_t	numPrelabelVersions
	Number of versions created during prelabeling. More...

double	prelabelingTime
	Time to prelabel SVFG. More...

double	meldLabelingTime
	Time to meld label SVFG. More...

double	versionPropTime
	Time to propagate versions to versions which rely on them. More...

Static Private Attributes
static VersionedFlowSensitive *	vfspta = nullptr

Friends
class	VersionedFlowSensitiveStat

Additional Inherited Members
Public Attributes inherited from SVF::WPASolver< GraphType >
u32_t	numOfIteration
	num of iterations during constraint solving More...

Protected Types inherited from SVF::FlowSensitive
typedef SVFG::SVFGEdgeSetTy	SVFGEdgeSetTy

Protected Attributes inherited from SVF::FlowSensitive
SVFG *	svfg

SVFGBuilder	memSSA

AndersenWaveDiff *	ander

std::vector< std::pair< hclust_fast_methods, std::vector< NodeID > > >	candidateMappings
	Save candidate mappings for evaluation's sake. More...

u32_t	numOfProcessedAddr
	Statistics. More...

u32_t	numOfProcessedCopy
	Number of processed Addr node. More...

u32_t	numOfProcessedGep
	Number of processed Copy node. More...

u32_t	numOfProcessedPhi
	Number of processed Gep node. More...

u32_t	numOfProcessedLoad
	Number of processed Phi node. More...

u32_t	numOfProcessedStore
	Number of processed Load node. More...

u32_t	numOfProcessedActualParam
	Number of processed Store node. More...

u32_t	numOfProcessedFormalRet
	Number of processed actual param node. More...

u32_t	numOfProcessedMSSANode
	Number of processed formal ret node. More...

u32_t	maxSCCSize
	Number of processed mssa node. More...

u32_t	numOfSCC

u32_t	numOfNodesInSCC

double	solveTime
	time of solve. More...

double	sccTime
	time of SCC detection. More...

double	processTime
	time of processNode. More...

double	propagationTime
	time of points-to propagation. More...

double	directPropaTime
	time of points-to propagation of address-taken objects More...

double	indirectPropaTime
	time of points-to propagation of top-level pointers More...

double	updateTime
	time of strong/weak updates. More...

double	addrTime
	time of handling address edges More...

double	copyTime
	time of handling copy edges More...

double	gepTime
	time of handling gep edges More...

double	loadTime
	time of load edges More...

double	storeTime
	time of store edges More...

double	phiTime
	time of phi nodes. More...

double	updateCallGraphTime
	time of updating call graph More...

NodeBS	svfgHasSU

Protected Attributes inherited from SVF::WPAFSSolver< GraphType >
NodeStack	nodeStack
	stack used for processing nodes. More...

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

u32_t	iterationForPrintStat
	print out statistics for i-th iteration More...

GraphType	_graph
	Graph. More...

std::unique_ptr< SCC >	scc
	SCC. More...

WorkList	worklist
	Worklist for resolution. More...

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

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

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

SVFModule *	svfMod
	Module. More...

PTATY	ptaTy
	Pointer analysis Type. More...

PTAImplTy	ptaImplTy
	PTA implementation type. More...

PTAStat *	stat
	Statistics. More...

PTACallGraph *	callgraph
	Call graph used for pointer analysis. More...

CallGraphSCC *	callGraphSCC
	SCC for PTACallGraph. More...

ICFG *	icfg
	Interprocedural control-flow graph. More...

CommonCHGraph *	chgraph
	CHGraph. More...

Static Protected Attributes inherited from SVF::FlowSensitive
static std::unique_ptr< FlowSensitive >	fspta

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

Detailed Description

Versioned flow sensitive whole program pointer analysis

Definition at line 32 of file VersionedFlowSensitive.h.

Member Typedef Documentation

◆ LocVersionMap

typedef std::vector<ObjToVersionMap> SVF::VersionedFlowSensitive::LocVersionMap

Definition at line 43 of file VersionedFlowSensitive.h.

◆ MeldVersion

typedef CoreBitVector SVF::VersionedFlowSensitive::MeldVersion

private

Definition at line 37 of file VersionedFlowSensitive.h.

◆ ObjToVersionMap

typedef Map<NodeID, Version> SVF::VersionedFlowSensitive::ObjToVersionMap

Definition at line 40 of file VersionedFlowSensitive.h.

◆ VarToPropNodeMap

typedef Map<VersionedVar, const DummyVersionPropSVFGNode *> SVF::VersionedFlowSensitive::VarToPropNodeMap

Definition at line 41 of file VersionedFlowSensitive.h.

◆ VersionRelianceMap

typedef Map<NodeID, Map<Version, std::vector<Version> > > SVF::VersionedFlowSensitive::VersionRelianceMap

(o -> (v -> versions with rely on o:v).

Definition at line 45 of file VersionedFlowSensitive.h.

Constructor & Destructor Documentation

◆ VersionedFlowSensitive()

VersionedFlowSensitive::VersionedFlowSensitive	(	SVFIR *	_pag,
		PTATY	type = `VFS_WPA`
	)

Constructor.

Definition at line 30 of file VersionedFlowSensitive.cpp.

     : FlowSensitive(_pag, type)
 {
     numPrelabeledNodes = numPrelabelVersions = 0;
     prelabelingTime = meldLabelingTime = versionPropTime = 0.0;
     // We'll grab vPtD in initialize.
  
     for (SVFIR::const_iterator it = pag->begin(); it != pag->end(); ++it)
     {
         if (SVFUtil::isa<ObjVar>(it->second)) equivalentObject[it->first] = it->first;
     }
  
     assert(!Options::OPTSVFG() && "VFS: -opt-svfg not currently supported with VFS.");
 }

Member Function Documentation

◆ atKey()

VersionedVar VersionedFlowSensitive::atKey	(	NodeID	var,
		Version	version
	)

static

Return key into vPtD for address-taken var of a specific version.

Definition at line 24 of file VersionedFlowSensitive.cpp.

 {
     assert(version != invalidVersion && "VersionedFlowSensitive::atKey: trying to use an invalid version!");
     return std::make_pair(var, version);
 }

◆ buildDeltaMaps()

void VersionedFlowSensitive::buildDeltaMaps ( void )

privatevirtual

Fills in deltaMap and deltaSourceMap for the SVFG.

use pre-analysis call graph to approximate all potential callsites

Definition at line 467 of file VersionedFlowSensitive.cpp.

 {
     deltaMap.resize(svfg->getTotalNodeNum(), false);
  
     // Call block nodes corresponding to all delta nodes.
     Set<const CallICFGNode *> deltaCBNs;
  
     for (SVFG::const_iterator it = svfg->begin(); it != svfg->end(); ++it)
     {
         const NodeID l = it->first;
         const SVFGNode *s = it->second;
  
         // Cases:
         //  * Function entry: can get new incoming indirect edges through ind. callsites.
         //  * Callsite returns: can get new incoming indirect edges if the callsite is indirect.
         //  * Otherwise: static.
         bool isDelta = false;
         if (const SVFFunction *fn = svfg->isFunEntrySVFGNode(s))
         {
             PTACallGraphEdge::CallInstSet callsites;
             ander->getCallGraph()->getIndCallSitesInvokingCallee(fn, callsites);
             isDelta = !callsites.empty();
  
             if (isDelta)
             {
                 // TODO: could we use deltaCBNs in the call above, avoiding this loop?
                 for (const CallICFGNode *cbn : callsites) deltaCBNs.insert(cbn);
             }
         }
         else if (const CallICFGNode *cbn = svfg->isCallSiteRetSVFGNode(s))
         {
             isDelta = cbn->isIndirectCall();
             if (isDelta) deltaCBNs.insert(cbn);
         }
  
         deltaMap[l] = isDelta;
     }
  
     deltaSourceMap.resize(svfg->getTotalNodeNum(), false);
  
     for (SVFG::const_iterator it = svfg->begin(); it != svfg->end(); ++it)
     {
         const NodeID l = it->first;
         const SVFGNode *s = it->second;
  
         if (const CallICFGNode *cbn = SVFUtil::dyn_cast<CallICFGNode>(s->getICFGNode()))
         {
             if (deltaCBNs.find(cbn) != deltaCBNs.end()) deltaSourceMap[l] = true;
         }
  
         // TODO: this is an over-approximation but it sound, marking every formal out as
         //       a delta-source.
         if (SVFUtil::isa<FormalOUTSVFGNode>(s)) deltaSourceMap[l] = true;
     }
 }

◆ buildIsStoreLoadMaps()

void VersionedFlowSensitive::buildIsStoreLoadMaps ( void )

privatevirtual

Fills in isStoreMap and isLoadMap.

Definition at line 444 of file VersionedFlowSensitive.cpp.

 {
     isStoreMap.resize(svfg->getTotalNodeNum(), false);
     isLoadMap.resize(svfg->getTotalNodeNum(), false);
     for (SVFG::const_iterator it = svfg->begin(); it != svfg->end(); ++it)
     {
         if (SVFUtil::isa<StoreSVFGNode>(it->second)) isStoreMap[it->first] = true;
         else if (SVFUtil::isa<LoadSVFGNode>(it->second)) isLoadMap[it->first] = true;
     }
 }

◆ classof() [1/2]

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

inlinestatic

Definition at line 74 of file VersionedFlowSensitive.h.

     {
         return pta->getAnalysisTy() == VFS_WPA;
     }

◆ classof() [2/2]

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

inlinestatic

Methods to support type inquiry through isa, cast, and dyn_cast.

Definition at line 70 of file VersionedFlowSensitive.h.

     {
         return true;
     }

◆ cluster()

void VersionedFlowSensitive::cluster ( void )

overrideprotectedvirtual

Override since we want to assign different weights based on versioning.

Reimplemented from SVF::FlowSensitive.

Definition at line 780 of file VersionedFlowSensitive.cpp.

 {
     std::vector<std::pair<unsigned, unsigned>> keys;
     for (SVFIR::iterator pit = pag->begin(); pit != pag->end(); ++pit)
     {
         unsigned occ = 1;
         unsigned v = pit->first;
         if (Options::PredictPtOcc() && pag->getObject(v) != nullptr) occ = stmtReliance[v].size() + 1;
         assert(occ != 0);
         keys.push_back(std::make_pair(v, occ));
     }
  
     PointsTo::MappingPtr nodeMapping =
         std::make_shared<std::vector<NodeID>>(NodeIDAllocator::Clusterer::cluster(ander, keys, candidateMappings, "aux-ander"));
     PointsTo::MappingPtr reverseNodeMapping =
         std::make_shared<std::vector<NodeID>>(NodeIDAllocator::Clusterer::getReverseNodeMapping(*nodeMapping));
  
     PointsTo::setCurrentBestNodeMapping(nodeMapping, reverseNodeMapping);
 }

◆ createVFSWPA()

static VersionedFlowSensitive* SVF::VersionedFlowSensitive::createVFSWPA ( SVFIR * _pag )

inlinestatic

Create single instance of versioned flow-sensitive points-to analysis.

Definition at line 81 of file VersionedFlowSensitive.h.

     {
         if (vfspta == nullptr)
         {
             vfspta = new VersionedFlowSensitive(_pag);
             vfspta->analyze();
         }
  
         return vfspta;
     }

◆ delta()

bool VersionedFlowSensitive::delta ( const NodeID l ) const

privatevirtual

Returns true if l is a delta node, i.e., may get a new incoming indirect edge due to on-the-fly callgraph construction.

Definition at line 432 of file VersionedFlowSensitive.cpp.

 {
     assert(l < deltaMap.size() && "VFS::delta: deltaMap is missing SVFG nodes!");
     return deltaMap[l];
 }

◆ deltaSource()

bool VersionedFlowSensitive::deltaSource ( const NodeID l ) const

privatevirtual

Returns true if l is a delta-source node, i.e., may get a new outgoing indirect edge to a delta node due to on-the-fly callgraph construction.

Definition at line 438 of file VersionedFlowSensitive.cpp.

 {
     assert(l < deltaSourceMap.size() && "VFS::delta: deltaSourceMap is missing SVFG nodes!");
     return deltaSourceMap[l];
 }

◆ dumpLocVersionMaps()

void VersionedFlowSensitive::dumpLocVersionMaps ( void ) const

private

Dumps maps consume and yield.

Definition at line 907 of file VersionedFlowSensitive.cpp.

 {
     SVFUtil::outs() << "# LocVersion Maps\n";
     for (SVFG::iterator it = svfg->begin(); it != svfg->end(); ++it)
     {
         const NodeID loc = it->first;
         bool locPrinted = false;
         for (const LocVersionMap *lvm :
                 {
                     &consume, &yield
                 })
         {
             if (lvm->at(loc).empty()) continue;
             if (!locPrinted)
             {
                 SVFUtil::outs() << "  " << "SVFG node " << loc << "\n";
                 locPrinted = true;
             }
  
             SVFUtil::outs() << "    " << (lvm == &consume ? "Consume " : "Yield   ") << ": ";
  
             bool first = true;
             for (const ObjToVersionMap::value_type &ov : lvm->at(loc))
             {
                 const NodeID o = ov.first;
                 const Version v = ov.second;
                 SVFUtil::outs() << (first ? "" : ", ") << "<" << o << ", " << v << ">";
                 first = false;
             }
  
             SVFUtil::outs() << "\n";
         }
     }
  
 }

◆ dumpMeldVersion()

void VersionedFlowSensitive::dumpMeldVersion ( MeldVersion & v )

staticprivate

Dumps a MeldVersion to stdout.

Definition at line 943 of file VersionedFlowSensitive.cpp.

 {
     SVFUtil::outs() << "[ ";
     bool first = true;
     for (unsigned e : v)
     {
         if (!first)
         {
             SVFUtil::outs() << ", ";
         }
  
         SVFUtil::outs() << e;
         first = false;
     }
  
     SVFUtil::outs() << " ]";
 }

◆ dumpReliances()

void VersionedFlowSensitive::dumpReliances ( void ) const

private

Dumps versionReliance and stmtReliance.

Definition at line 850 of file VersionedFlowSensitive.cpp.

 {
     SVFUtil::outs() << "# Version reliances\n";
     for (const Map<NodeID, Map<Version, std::vector<Version>>>::value_type &ovrv : versionReliance)
     {
         NodeID o = ovrv.first;
         SVFUtil::outs() << "  Object " << o << "\n";
         for (const Map<Version, std::vector<Version>>::value_type& vrv : ovrv.second)
         {
             Version v = vrv.first;
             SVFUtil::outs() << "    Version " << v << " is a reliance for: ";
  
             bool first = true;
             for (Version rv : vrv.second)
             {
                 if (!first)
                 {
                     SVFUtil::outs() << ", ";
                 }
  
                 SVFUtil::outs() << rv;
                 first = false;
             }
  
             SVFUtil::outs() << "\n";
         }
     }
  
     SVFUtil::outs() << "# Statement reliances\n";
     for (const Map<NodeID, Map<Version, NodeBS>>::value_type &ovss : stmtReliance)
     {
         NodeID o = ovss.first;
         SVFUtil::outs() << "  Object " << o << "\n";
  
         for (const Map<Version, NodeBS>::value_type &vss : ovss.second)
         {
             Version v = vss.first;
             SVFUtil::outs() << "    Version " << v << " is a reliance for statements: ";
  
             const NodeBS &ss = vss.second;
             bool first = true;
             for (NodeID s : ss)
             {
                 if (!first)
                 {
                     SVFUtil::outs() << ", ";
                 }
  
                 SVFUtil::outs() << s;
                 first = false;
             }
  
             SVFUtil::outs() << "\n";
         }
     }
 }

◆ finalize()

void VersionedFlowSensitive::finalize ( )

overridevirtual

Finalize analysis.

Reimplemented from SVF::FlowSensitive.

Definition at line 65 of file VersionedFlowSensitive.cpp.

 {
     FlowSensitive::finalize();
     // vPtD->dumpPTData();
     // dumpReliances();
     // dumpLocVersionMaps();
 }

◆ getConsume()

Version VersionedFlowSensitive::getConsume	(	const NodeID	l,
		const NodeID	o
	)		const

private

Returns the consumed version of o at l. If no such version exists, returns invalidVersion.

Definition at line 810 of file VersionedFlowSensitive.cpp.

 {
     return getVersion(l, o, consume);
 }

◆ getReliantVersions()

std::vector< Version > & VersionedFlowSensitive::getReliantVersions	(	const NodeID	o,
		const Version	v
	)

private

Returns the versions of o which rely on o:v.

Definition at line 840 of file VersionedFlowSensitive.cpp.

 {
     return versionReliance[o][v];
 }

◆ getStmtReliance()

NodeBS & VersionedFlowSensitive::getStmtReliance	(	const NodeID	o,
		const Version	v
	)

private

Returns the statements which rely on o:v.

Definition at line 845 of file VersionedFlowSensitive.cpp.

 {
     return stmtReliance[o][v];
 }

◆ getVersion()

Version VersionedFlowSensitive::getVersion	(	const NodeID	l,
		const NodeID	o,
		const LocVersionMap &	lvm
	)		const

private

Shared code for getConsume and getYield. They wrap this function.

Definition at line 800 of file VersionedFlowSensitive.cpp.

 {
     const Map<NodeID, NodeID>::const_iterator canonObjectIt = equivalentObject.find(o);
     const NodeID op = canonObjectIt == equivalentObject.end() ? o : canonObjectIt->second;
  
     const ObjToVersionMap &ovm = lvm[l];
     const ObjToVersionMap::const_iterator foundVersion = ovm.find(op);
     return foundVersion == ovm.end() ? invalidVersion : foundVersion->second;
 }

◆ getYield()

Version VersionedFlowSensitive::getYield	(	const NodeID	l,
		const NodeID	o
	)		const

private

Returns the yielded version of o at l. If no such version exists, returns invalidVersion.

Definition at line 815 of file VersionedFlowSensitive.cpp.

 {
     // Non-store: consume == yield.
     if (isStore(l)) return getVersion(l, o, yield);
     else return getVersion(l, o, consume);
 }

◆ initialize()

void VersionedFlowSensitive::initialize ( )

overridevirtual

Initialize analysis.

Reimplemented from SVF::FlowSensitive.

Definition at line 45 of file VersionedFlowSensitive.cpp.

 {
     FlowSensitive::initialize();
     // Overwrite the stat FlowSensitive::initialize gave us.
     delete stat;
     stat = new VersionedFlowSensitiveStat(this);
  
     vPtD = getVersionedPTDataTy();
  
     buildIsStoreLoadMaps();
     buildDeltaMaps();
     consume.resize(svfg->getTotalNodeNum());
     yield.resize(svfg->getTotalNodeNum());
  
     prelabel();
     meldLabel();
  
     removeAllIndirectSVFGEdges();
 }

◆ isLoad()

bool VersionedFlowSensitive::isLoad ( const NodeID l ) const

privatevirtual

Returns true if l is a load node.

Definition at line 461 of file VersionedFlowSensitive.cpp.

 {
     assert(l < isLoadMap.size() && "VFS::isLoad: isLoadMap is missing SVFG nodes!");
     return isLoadMap[l];
 }

◆ isStore()

bool VersionedFlowSensitive::isStore ( const NodeID l ) const

privatevirtual

Returns true if l is a store node.

Definition at line 455 of file VersionedFlowSensitive.cpp.

 {
     assert(l < isStoreMap.size() && "VFS::isStore: isStoreMap is missing SVFG nodes!");
     return isStoreMap[l];
 }

◆ meld()

bool VersionedFlowSensitive::meld	(	MeldVersion &	mv1,
		const MeldVersion &	mv2
	)

staticprivate

Melds v2 into v1 (in place), returns whether a change occurred.

Definition at line 426 of file VersionedFlowSensitive.cpp.

 {
     // Meld operator is union of bit vectors.
     return mv1 |= mv2;
 }

◆ meldLabel()

void VersionedFlowSensitive::meldLabel ( void )

private

Meld label the prelabeled SVFG.

Definition at line 120 of file VersionedFlowSensitive.cpp.

 {
     double start = stat->getClk(true);
  
     assert(Options::VersioningThreads() > 0 && "VFS::meldLabel: number of versioning threads must be > 0!");
  
     // Nodes which have at least one object on them given a prelabel + the Andersen's points-to
     // set of interest so we don't keep calling getPts. For Store nodes, we'll fill that in, for
     // MR nodes, we won't as its getPointsTo is cheap.
     // TODO: preferably we cache both for ease and to avoid the dyn_cast/isa, but Andersen's points-to
     // sets are PointsTo and MR's sets are NodeBS, which are incompatible types. Maybe when we can
     // use std::option.
     std::vector<std::pair<const SVFGNode *, const PointsTo *>> prelabeledNodes;
     // Fast query for the above.
     std::vector<bool> isPrelabeled(svfg->getTotalNodeNum(), false);
     while (!vWorklist.empty())
     {
         const NodeID n = vWorklist.pop();
         isPrelabeled[n] = true;
  
         const SVFGNode *sn = svfg->getSVFGNode(n);
         const PointsTo *nPts = nullptr;
         if (const StoreSVFGNode *store = SVFUtil::dyn_cast<StoreSVFGNode>(sn))
         {
             const NodeID p = store->getPAGDstNodeID();
             nPts = &(this->ander->getPts(p));
         }
  
         prelabeledNodes.push_back(std::make_pair(sn, nPts));
     }
  
     // Delta, delta source, store, and load nodes, which require versions during
     // solving, unlike other nodes with which we can make do with the reliance map.
     std::vector<NodeID> nodesWhichNeedVersions;
     for (SVFG::const_iterator it = svfg->begin(); it != svfg->end(); ++it)
     {
         const NodeID n = it->first;
         if (delta(n) || deltaSource(n) || isStore(n) || isLoad(n)) nodesWhichNeedVersions.push_back(n);
     }
  
     std::mutex *versionMutexes = new std::mutex[nodesWhichNeedVersions.size()];
  
     // Map of footprints to the canonical object "owning" the footprint.
     Map<std::vector<const IndirectSVFGEdge *>, NodeID> footprintOwner;
  
     std::queue<NodeID> objectQueue;
     for (const NodeID o : prelabeledObjects)
     {
         // "Touch" maps with o so we don't need to lock on them.
         versionReliance[o];
         stmtReliance[o];
         objectQueue.push(o);
     }
  
     std::mutex objectQueueMutex;
     std::mutex footprintOwnerMutex;
  
     auto meldVersionWorker = [this, &footprintOwner, &objectQueue,
                                     &objectQueueMutex, &footprintOwnerMutex, &versionMutexes,
                                     &prelabeledNodes, &isPrelabeled, &nodesWhichNeedVersions]
          (const unsigned thread)
     {
         while (true)
         {
             NodeID o;
             {
                 std::lock_guard<std::mutex> guard(objectQueueMutex);
                 // No more objects? Done.
                 if (objectQueue.empty()) return;
                 o = objectQueue.front();
                 objectQueue.pop();
             }
  
             // 1. Compute the SCCs for the nodes on the graph overlay of o.
             // For starting nodes, we only need those which did prelabeling for o specifically.
             // TODO: maybe we should move this to prelabel with a map (o -> starting nodes).
             std::vector<const SVFGNode *> osStartingNodes;
             for (std::pair<const SVFGNode *, const PointsTo *> snPts : prelabeledNodes)
             {
                 const SVFGNode *sn = snPts.first;
                 const PointsTo *pts = snPts.second;
                 if (pts != nullptr)
                 {
                     if (pts->test(o)) osStartingNodes.push_back(sn);
                 }
                 else if (const MRSVFGNode *mr = SVFUtil::dyn_cast<MRSVFGNode>(sn))
                 {
                     if (mr->getPointsTo().test(o)) osStartingNodes.push_back(sn);
                 }
                 else
                 {
                     assert(false && "VFS::meldLabel: unexpected prelabeled node!");
                 }
             }
  
             std::vector<int> partOf;
             std::vector<const IndirectSVFGEdge *> footprint;
             unsigned numSCCs = SCC::detectSCCs(this, this->svfg, o, osStartingNodes, partOf, footprint);
  
             // 2. Skip any further processing of a footprint we have seen before.
             {
                 std::lock_guard<std::mutex> guard(footprintOwnerMutex);
                 const Map<std::vector<const IndirectSVFGEdge *>, NodeID>::const_iterator canonOwner
                     = footprintOwner.find(footprint);
                 if (canonOwner == footprintOwner.end())
                 {
                     this->equivalentObject[o] = o;
                     footprintOwner[footprint] = o;
                 }
                 else
                 {
                     this->equivalentObject[o] = canonOwner->second;
                     // Same version and stmt reliance as the canonical. During solving we cannot just reuse
                     // the canonical object's reliance because it may change due to on-the-fly call graph
                     // construction. Something like copy-on-write could be good... probably negligible.
                     this->versionReliance.at(o) = this->versionReliance.at(canonOwner->second);
                     this->stmtReliance.at(o) = this->stmtReliance.at(canonOwner->second);
                     continue;
                 }
             }
  
             // 3. a. Initialise the MeldVersion of prelabeled nodes (SCCs).
             //    b. Initialise a todo list of all the nodes we need to version,
             //       sorted according to topological order.
             // We will use a map of sccs to meld versions for what is consumed.
             std::vector<MeldVersion> sccToMeldVersion(numSCCs);
             // At stores, what is consumed is different to what is yielded, so we
             // maintain that separately.
             Map<NodeID, MeldVersion> storesYieldedMeldVersion;
             // SVFG nodes of interest -- those part of an SCC from the starting nodes.
             std::vector<NodeID> todoList;
             unsigned bit = 0;
             // To calculate reachable nodes, we can see what nodes n exist where
             // partOf[n] != -1. Since the SVFG can be large this can be expensive.
             // Instead, we can gather this from the edges in the footprint and
             // the starting nodes (incase such nodes have no edges).
             // TODO: should be able to do this better: too many redundant inserts.
             Set<NodeID> reachableNodes;
             for (const SVFGNode *sn : osStartingNodes) reachableNodes.insert(sn->getId());
             for (const SVFGEdge *se : footprint)
             {
                 reachableNodes.insert(se->getSrcNode()->getId());
                 reachableNodes.insert(se->getDstNode()->getId());
             }
  
             for (const NodeID n : reachableNodes)
             {
                 if (isPrelabeled[n])
                 {
                     if (this->isStore(n)) storesYieldedMeldVersion[n].set(bit);
                     else sccToMeldVersion[partOf[n]].set(bit);
                     ++bit;
                 }
  
                 todoList.push_back(n);
             }
  
             // Sort topologically so each nodes is only visited once.
             auto cmp = [&partOf](const NodeID a, const NodeID b)
             {
                 return partOf[a] > partOf[b];
             };
             std::sort(todoList.begin(), todoList.end(), cmp);
  
             // 4. a. Do meld versioning.
             //    b. Determine SCC reliances.
             //    c. Build a footprint for o (all edges which it is found on).
             //    d. Determine which SCCs belong to stores.
  
             // sccReliance[x] = { y_1, y_2, ... } if there exists an edge from a node
             // in SCC x to SCC y_i.
             std::vector<Set<int>> sccReliance(numSCCs);
             // Maps SCC to the store it corresponds to or -1 if it doesn't. TODO: unsigned vs signed -- nasty.
             std::vector<int> storeSCC(numSCCs, -1);
             for (size_t i = 0; i < todoList.size(); ++i)
             {
                 const NodeID n = todoList[i];
                 const SVFGNode *sn = this->svfg->getSVFGNode(n);
                 const bool nIsStore = this->isStore(n);
  
                 int nSCC = partOf[n];
                 if (nIsStore) storeSCC[nSCC] = n;
  
                 // Given n -> m, the yielded version of n will be melded into m.
                 // For stores, that is in storesYieldedMeldVersion, otherwise, consume == yield and
                 // we can just use sccToMeldVersion.
                 const MeldVersion &nMV = nIsStore ? storesYieldedMeldVersion[n] : sccToMeldVersion[nSCC];
                 for (const SVFGEdge *e : sn->getOutEdges())
                 {
                     const IndirectSVFGEdge *ie = SVFUtil::dyn_cast<IndirectSVFGEdge>(e);
                     if (!ie) continue;
  
                     const NodeID m = ie->getDstNode()->getId();
                     // Ignoreedges which don't involve o.
                     if (!ie->getPointsTo().test(o)) continue;
  
                     int mSCC = partOf[m];
  
                     // There is an edge from the SCC n belongs to that m belongs to.
                     sccReliance[nSCC].insert(mSCC);
  
                     // Ignore edges to delta nodes (prelabeled consume).
                     // No point propagating when n's SCC == m's SCC (same meld version there)
                     // except when it is a store, because we are actually propagating n's yielded
                     // into m's consumed. Store nodes are in their own SCCs, so it is a self
                     // loop on a store node.
                     if (!this->delta(m) && (nSCC != mSCC || nIsStore))
                     {
                         sccToMeldVersion[mSCC] |= nMV;
                     }
                 }
             }
  
             // 5. Transform meld versions belonging to SCCs into versions.
             Map<MeldVersion, Version> mvv;
             std::vector<Version> sccToVersion(numSCCs, invalidVersion);
             Version curVersion = 0;
             for (u32_t scc = 0; scc < sccToMeldVersion.size(); ++scc)
             {
                 const MeldVersion &mv = sccToMeldVersion[scc];
                 Map<MeldVersion, Version>::const_iterator foundVersion = mvv.find(mv);
                 Version v = foundVersion == mvv.end() ? mvv[mv] = ++curVersion : foundVersion->second;
                 sccToVersion[scc] = v;
             }
  
             sccToMeldVersion.clear();
  
             // Same for storesYieldedMeldVersion.
             Map<NodeID, Version> storesYieldedVersion;
             for (auto const& nmv : storesYieldedMeldVersion)
             {
                 const NodeID n = nmv.first;
                 const MeldVersion &mv = nmv.second;
  
                 Map<MeldVersion, Version>::const_iterator foundVersion = mvv.find(mv);
                 Version v = foundVersion == mvv.end() ? mvv[mv] = ++curVersion : foundVersion->second;
                 storesYieldedVersion[n] = v;
             }
  
             storesYieldedMeldVersion.clear();
  
             mvv.clear();
  
             // 6. From SCC reliance, determine version reliances.
             Map<Version, std::vector<Version>> &osVersionReliance = this->versionReliance.at(o);
             for (u32_t scc = 0; scc < numSCCs; ++scc)
             {
                 if (sccReliance[scc].empty()) continue;
  
                 // Some consume relies on a yield. When it's a store, we need to pick whether to
                 // use the consume or yield unlike when it is not because they are the same.
                 const Version version
                     = storeSCC[scc] != -1 ? storesYieldedVersion[storeSCC[scc]] : sccToVersion[scc];
  
                 std::vector<Version> &reliantVersions = osVersionReliance[version];
                 for (const int reliantSCC : sccReliance[scc])
                 {
                     const Version reliantVersion = sccToVersion[reliantSCC];
                     if (version != reliantVersion)
                     {
                         // sccReliance is a set, no need to worry about duplicates.
                         reliantVersions.push_back(reliantVersion);
                     }
                 }
             }
  
             // 7. a. Save versions for nodes which need them.
             //    b. Fill in stmtReliance.
             // TODO: maybe randomize iteration order for less contention? Needs profiling.
             Map<Version, NodeBS> &osStmtReliance = this->stmtReliance.at(o);
             for (size_t i = 0; i < nodesWhichNeedVersions.size(); ++i)
             {
                 const NodeID n = nodesWhichNeedVersions[i];
                 std::mutex &mutex = versionMutexes[i];
  
                 const int scc = partOf[n];
                 if (scc == -1) continue;
  
                 std::lock_guard<std::mutex> guard(mutex);
  
                 const Version c = sccToVersion[scc];
                 if (c != invalidVersion)
                 {
                     this->setConsume(n, o, c);
                     if (this->isStore(n) || this->isLoad(n)) osStmtReliance[c].set(n);
                 }
  
                 if (this->isStore(n))
                 {
                     const Map<NodeID, Version>::const_iterator yIt = storesYieldedVersion.find(n);
                     if (yIt != storesYieldedVersion.end()) this->setYield(n, o, yIt->second);
                 }
             }
         }
     };
  
     std::vector<std::thread> workers;
     for (unsigned i = 0; i < Options::VersioningThreads(); ++i) workers.push_back(std::thread(meldVersionWorker, i));
     for (std::thread &worker : workers) worker.join();
  
     delete[] versionMutexes;
  
     double end = stat->getClk(true);
     meldLabelingTime = (end - start) / TIMEINTERVAL;
 }

◆ prelabel()

void VersionedFlowSensitive::prelabel ( void )

private

Prelabel the SVFG: set y(o) for stores and c(o) for delta nodes to a new version.

Definition at line 73 of file VersionedFlowSensitive.cpp.

 {
     double start = stat->getClk(true);
     for (SVFG::iterator it = svfg->begin(); it != svfg->end(); ++it)
     {
         NodeID l = it->first;
         const SVFGNode *ln = it->second;
  
         if (const StoreSVFGNode *stn = SVFUtil::dyn_cast<StoreSVFGNode>(ln))
         {
             // l: *p = q.
             // If p points to o (Andersen's), l yields a new version for o.
             NodeID p = stn->getPAGDstNodeID();
             for (NodeID o : ander->getPts(p))
             {
                 prelabeledObjects.insert(o);
             }
  
             vWorklist.push(l);
  
             if (ander->getPts(p).count() != 0) ++numPrelabeledNodes;
         }
         else if (delta(l))
         {
             // The outgoing edges are not only what will later be propagated. SVFGOPT may
             // move around nodes such that there can be an MRSVFGNode with no incoming or
             // outgoing edges which will be added at runtime. In essence, we can no
             // longer rely on the outgoing edges of a delta node when SVFGOPT is enabled.
             const MRSVFGNode *mr = SVFUtil::dyn_cast<MRSVFGNode>(ln);
             if (mr != nullptr)
             {
                 for (const NodeID o : mr->getPointsTo())
                 {
                     prelabeledObjects.insert(o);
                 }
  
                 // Push into worklist because its consume == its yield.
                 vWorklist.push(l);
                 if (mr->getPointsTo().count() != 0) ++numPrelabeledNodes;
             }
         }
     }
  
     double end = stat->getClk(true);
     prelabelingTime = (end - start) / TIMEINTERVAL;
 }

◆ processLoad()

bool VersionedFlowSensitive::processLoad ( const LoadSVFGNode * load )

overrideprotectedvirtual

Process load node

Foreach node \in src pts(dst) = union pts(node)

If o is a field-insensitive object, we should also get all field nodes' points-to sets and pass them to p.

If the ptd is a field-insensitive node, we should also get all field nodes' points-to sets and pass them to pagDst.

Reimplemented from SVF::FlowSensitive.

Definition at line 647 of file VersionedFlowSensitive.cpp.

 {
     double start = stat->getClk();
  
     bool changed = false;
  
     // l: p = *q
     NodeID l = load->getId();
     NodeID p = load->getPAGDstNodeID();
     NodeID q = load->getPAGSrcNodeID();
  
     const PointsTo& qpt = getPts(q);
     // p = *q, the type of p must be a pointer
     if (load->getPAGDstNode()->isPointer())
     {
         for (NodeID o : qpt)
         {
             if (pag->isConstantObj(o)) continue;
  
             const Version c = getConsume(l, o);
             if (c != invalidVersion && vPtD->unionPts(p, atKey(o, c)))
             {
                 changed = true;
             }
  
             if (isFieldInsensitive(o))
             {
                 const NodeBS& fields = getAllFieldsObjVars(o);
                 for (NodeID of : fields)
                 {
                     const Version c = getConsume(l, of);
                     if (c != invalidVersion && vPtD->unionPts(p, atKey(of, c)))
                     {
                         changed = true;
                     }
                 }
             }
         }
     }
     double end = stat->getClk();
     loadTime += (end - start) / TIMEINTERVAL;
     return changed;
 }

◆ processNode()

void VersionedFlowSensitive::processNode ( NodeID nodeId )

overrideprotectedvirtual

Handle various constraints.

Process each SVFG node

Reimplemented from SVF::FlowSensitive.

Definition at line 590 of file VersionedFlowSensitive.cpp.

 {
     SVFGNode* sn = svfg->getSVFGNode(n);
     // Handle DummyVersPropSVFGNode here so we don't have to override the long
     // processSVFGNode. We also don't call propagate based on its result.
     if (const DummyVersionPropSVFGNode *dvp = SVFUtil::dyn_cast<DummyVersionPropSVFGNode>(sn))
     {
         propagateVersion(dvp->getObject(), dvp->getVersion());
     }
     else if (processSVFGNode(sn))
     {
         propagate(&sn);
     }
 }

◆ processStore()

bool VersionedFlowSensitive::processStore ( const StoreSVFGNode * store )

overrideprotectedvirtual

Process store node

foreach node \in dst pts(node) = union pts(src)

STORE statement can only be processed if the pointer on the LHS points to something. If we handle STORE with an empty points-to set, the OUT set will be updated from IN set. Then if LHS pointer points-to one target and it has been identified as a strong update, we can't remove those points-to information computed before this strong update from the OUT set.

check if this is a strong updates store

Reimplemented from SVF::FlowSensitive.

Definition at line 693 of file VersionedFlowSensitive.cpp.

 {
     NodeID p = store->getPAGDstNodeID();
     const PointsTo &ppt = getPts(p);
  
     if (ppt.empty()) return false;
  
     NodeID q = store->getPAGSrcNodeID();
     const PointsTo &qpt = getPts(q);
  
     NodeID l = store->getId();
     // l: *p = q
  
     double start = stat->getClk();
     bool changed = false;
     // The version for these objects would be y_l(o).
     NodeBS changedObjects;
  
     if (!qpt.empty())
     {
         // *p = q, the type of q must be a pointer
         if (store->getPAGSrcNode()->isPointer())
         {
             for (NodeID o : ppt)
             {
                 if (pag->isConstantObj(o)) continue;
  
                 const Version y = getYield(l, o);
                 if (y != invalidVersion && vPtD->unionPts(atKey(o, y), q))
                 {
                     changed = true;
                     changedObjects.set(o);
                 }
             }
         }
     }
  
     double end = stat->getClk();
     storeTime += (end - start) / TIMEINTERVAL;
  
     double updateStart = stat->getClk();
  
     NodeID singleton = 0;
     bool isSU = isStrongUpdate(store, singleton);
     if (isSU) svfgHasSU.set(l);
     else svfgHasSU.reset(l);
  
     // For all objects, perform pts(o:y) = pts(o:y) U pts(o:c) at loc,
     // except when a strong update is taking place.
     for (const ObjToVersionMap::value_type &oc : consume[l])
     {
         const NodeID o = oc.first;
         const Version c = oc.second;
  
         // Strong-updated; don't propagate.
         if (isSU && o == singleton) continue;
  
         const Version y = getYield(l, o);
         if (y != invalidVersion && vPtD->unionPts(atKey(o, y), atKey(o, c)))
         {
             changed = true;
             changedObjects.set(o);
         }
     }
  
     double updateEnd = stat->getClk();
     updateTime += (updateEnd - updateStart) / TIMEINTERVAL;
  
     // Changed objects need to be propagated. Time here should be inconsequential
     // *except* for time taken for propagateVersion, which will time itself.
     if (!changedObjects.empty())
     {
         for (const NodeID o : changedObjects)
         {
             // Definitely has a yielded version (came from prelabelling) as these are
             // the changed objects which must've been pointed to in Andersen's too.
             const Version y = getYield(l, o);
             propagateVersion(o, y);
  
             // Some o/v pairs changed: statements need to know.
             for (NodeID s : getStmtReliance(o, y)) pushIntoWorklist(s);
         }
     }
  
     return changed;
 }

◆ propagateVersion() [1/2]

void VersionedFlowSensitive::propagateVersion	(	const NodeID	o,
		const Version	v,
		const Version	vp,
		bool	time = `true`
	)

private

Propagates version v of o to version vp of o. time indicates whether it should record time taken itself.

Definition at line 560 of file VersionedFlowSensitive.cpp.

 {
     double start = time ? stat->getClk() : 0.0;
  
     const VersionedVar srcVar = atKey(o, v);
     const VersionedVar dstVar = atKey(o, vp);
     if (vPtD->unionPts(dstVar, srcVar))
     {
         // o:vp has changed.
         // Add the dummy propagation node to tell the solver to propagate it later.
         const DummyVersionPropSVFGNode *dvp = nullptr;
         VarToPropNodeMap::const_iterator dvpIt = versionedVarToPropNode.find(dstVar);
         if (dvpIt == versionedVarToPropNode.end())
         {
             dvp = svfg->addDummyVersionPropSVFGNode(o, vp);
             versionedVarToPropNode[dstVar] = dvp;
         }
         else dvp = dvpIt->second;
  
         assert(dvp != nullptr && "VFS::propagateVersion: propagation dummy node not found?");
         pushIntoWorklist(dvp->getId());
  
         // Notify nodes which rely on o:vp that it changed.
         for (NodeID s : getStmtReliance(o, vp)) pushIntoWorklist(s);
     }
  
     double end = time ? stat->getClk() : 0.0;
     if (time) versionPropTime += (end - start) / TIMEINTERVAL;
 }

◆ propagateVersion() [2/2]

void VersionedFlowSensitive::propagateVersion	(	NodeID	o,
		Version	v
	)

private

Propagates version v of o to any version of o which relies on v when o/v is changed. Recursively applies to reliant versions till no new changes are made. Adds any statements which rely on any changes made to the worklist.

Definition at line 546 of file VersionedFlowSensitive.cpp.

 {
     double start = stat->getClk();
  
     const std::vector<Version> &reliantVersions = getReliantVersions(o, v);
     for (Version r : reliantVersions)
     {
         propagateVersion(o, v, r, false);
     }
  
     double end = stat->getClk();
     versionPropTime += (end - start) / TIMEINTERVAL;
 }

◆ propAlongIndirectEdge()

virtual bool SVF::VersionedFlowSensitive::propAlongIndirectEdge ( const IndirectSVFGEdge * )

inlineoverrideprotectedvirtual

Override to do nothing. Instead, we will use propagateVersion when necessary.

Reimplemented from SVF::FlowSensitive.

Definition at line 106 of file VersionedFlowSensitive.h.

     {
         return false;
     }

◆ PTAName()

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

inlineoverridevirtual

Get PTA name.

Reimplemented from SVF::FlowSensitive.

Definition at line 63 of file VersionedFlowSensitive.h.

     {
         return "VersionedFlowSensitive";
     }

◆ readPtsFromFile()

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

overrideprivatevirtual

Initialization for the Solver

Load the pts from file

finalize the analysis

Reimplemented from SVF::FlowSensitive.

Definition at line 961 of file VersionedFlowSensitive.cpp.

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

◆ readVersionedAnalysisResultFromFile()

void VersionedFlowSensitive::readVersionedAnalysisResultFromFile ( std::ifstream & F )

private

Definition at line 1065 of file VersionedFlowSensitive.cpp.

 {
     std::string line;
     std::string delimiter1 = " -> { ";
     std::string delimiter2 = " }";
     while (F.good())
     {
         // Parse a single line in the form of "[ var version ] -> { obj1 obj2 obj3 }"
         getline(F, line);
         if (line == "---VERSIONED---")     break;
         std::string pair = line.substr(line.find("[ ")+1, line.find(" ]"));
  
         // Parse VersionKey
         std::istringstream ss(pair);
         NodeID nodeID;
         Version nodeVersion;
         ss>> nodeID >> nodeVersion;
         VersionedVar keyPair = atKey(nodeID,nodeVersion);
  
         // Parse Point-to set
         size_t pos = line.find(delimiter1);
         if (pos == std::string::npos)    break;
         if (line.back() != '}')     break;
         pos = pos + delimiter1.length();
         size_t len = line.length() - pos - delimiter2.length();
         std::string objs = line.substr(pos, len);
         PointsTo dstPts;
         if (!objs.empty())
         {
             std::istringstream pt(objs);
             NodeID obj;
             while (pt.good())
             {
                 pt >> obj;
                 dstPts.set(obj);
             }
         }
  
         // union point-to reuslt
         vPtD->unionPts(keyPair, dstPts);
     }
  
 }

◆ releaseVFSWPA()

static void SVF::VersionedFlowSensitive::releaseVFSWPA ( )

inlinestatic

Release flow-sensitive pointer analysis.

Definition at line 93 of file VersionedFlowSensitive.h.

     {
         if (vfspta) delete vfspta;
         vfspta = nullptr;
     }

◆ removeAllIndirectSVFGEdges()

void VersionedFlowSensitive::removeAllIndirectSVFGEdges ( void )

private

Removes all indirect edges in the SVFG.

Definition at line 524 of file VersionedFlowSensitive.cpp.

 {
     for (SVFG::iterator nodeIt = svfg->begin(); nodeIt != svfg->end(); ++nodeIt)
     {
         SVFGNode *sn = nodeIt->second;
  
         const SVFGEdgeSetTy &inEdges = sn->getInEdges();
         std::vector<SVFGEdge *> toDeleteFromIn;
         for (SVFGEdge *e : inEdges)
         {
             if (SVFUtil::isa<IndirectSVFGEdge>(e)) toDeleteFromIn.push_back(e);
         }
  
         for (SVFGEdge *e : toDeleteFromIn) svfg->removeSVFGEdge(e);
  
         // Only need to iterate over incoming edges for each node because edges
         // will be deleted from in/out through removeSVFGEdge.
     }
  
     setGraph(svfg);
 }

◆ setConsume()

void VersionedFlowSensitive::setConsume	(	const NodeID	l,
		const NodeID	o,
		const Version	v
	)

private

Sets the consumed version of o at l to v.

Definition at line 828 of file VersionedFlowSensitive.cpp.

 {
     setVersion(l, o, v, consume);
 }

◆ setVersion()

void VersionedFlowSensitive::setVersion	(	const NodeID	l,
		const NodeID	o,
		const Version	v,
		LocVersionMap &	lvm
	)

private

Shared code for setConsume and setYield. They wrap this function.

Definition at line 822 of file VersionedFlowSensitive.cpp.

 {
     ObjToVersionMap &ovm = lvm[l];
     ovm[o] = v;
 }

◆ setYield()

void VersionedFlowSensitive::setYield	(	const NodeID	l,
		const NodeID	o,
		const Version	v
	)

private

Sets the yielded version of o at l to v.

Definition at line 833 of file VersionedFlowSensitive.cpp.

 {
     // Non-store: consume == yield.
     if (isStore(l)) setVersion(l, o, v, yield);
     else setVersion(l, o, v, consume);
 }

◆ solveAndwritePtsToFile()

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

overrideprivatevirtual

Start analysis

Initialization for the Solver

finalize the analysis

Initialization for the Solver

finalize the analysis

Reimplemented from SVF::FlowSensitive.

Definition at line 997 of file VersionedFlowSensitive.cpp.

 {
     initialize();
     if(!filename.empty())
         writeObjVarToFile(filename);
     solveConstraints();
     if(!filename.empty())
     {
         writeVersionedAnalysisResultToFile(filename);
         writeToFile(filename);
     }
     finalize();
 }

◆ updateConnectedNodes()

void VersionedFlowSensitive::updateConnectedNodes ( const SVFGEdgeSetTy & edges )

overrideprotectedvirtual

Update nodes connected during updating call graph.

Push nodes connected during update call graph into worklist so they will be solved during next iteration.

If this is a formal-param or actual-ret node, we need to solve this phi node in next iteration

If this is a formal-in or actual-out node, we need to propagate points-to information from its predecessor node.

If this is a field-insensitive obj, propagate all field node's pts

Reimplemented from SVF::FlowSensitive.

Definition at line 605 of file VersionedFlowSensitive.cpp.

 {
     for (const SVFGEdge *e : newEdges)
     {
         SVFGNode *dstNode = e->getDstNode();
         NodeID src = e->getSrcNode()->getId();
         NodeID dst = dstNode->getId();
  
         if (SVFUtil::isa<PHISVFGNode>(dstNode)
                 || SVFUtil::isa<FormalParmSVFGNode>(dstNode)
                 || SVFUtil::isa<ActualRetSVFGNode>(dstNode))
         {
             pushIntoWorklist(dst);
         }
         else
         {
             const IndirectSVFGEdge *ie = SVFUtil::dyn_cast<IndirectSVFGEdge>(e);
             assert(ie != nullptr && "VFS::updateConnectedNodes: given direct edge?");
  
             assert(delta(dst) && "VFS::updateConnectedNodes: new edges should be to delta nodes!");
             assert(deltaSource(src) && "VFS::updateConnectedNodes: new indirect edges should be from delta source nodes!");
  
             const NodeBS &ept = ie->getPointsTo();
             // For every o, such that src --o--> dst, we need to set up reliance (and propagate).
             for (const NodeID o : ept)
             {
                 Version srcY = getYield(src, o);
                 if (srcY == invalidVersion) continue;
                 Version dstC = getConsume(dst, o);
                 if (dstC == invalidVersion) continue;
  
                 std::vector<Version> &versionsRelyingOnSrcY = getReliantVersions(o, srcY);
                 if (std::find(versionsRelyingOnSrcY.begin(), versionsRelyingOnSrcY.end(), dstC) == versionsRelyingOnSrcY.end())
                 {
                     versionsRelyingOnSrcY.push_back(dstC);
                     propagateVersion(o, srcY, dstC);
                 }
             }
         }
     }
 }

◆ writeVersionedAnalysisResultToFile()

void VersionedFlowSensitive::writeVersionedAnalysisResultToFile ( const std::string & filename )

private

Definition at line 1013 of file VersionedFlowSensitive.cpp.

 {
     SVFUtil::outs() << "Storing Versioned Analysis Result to '" << filename << "'...";
     std::error_code err;
     std::fstream f(filename.c_str(), std::ios_base::app);
     if (!f.good())
     {
         SVFUtil::outs() << "  error opening file for writing!\n";
         return;
     }
  
     for (const VersionedFlowSensitive::LocVersionMap *lvm :
             {
                 &this->consume, &this->yield
             })
     {
         for (const VersionedFlowSensitive::ObjToVersionMap  &lov : *lvm)
         {
             for (const VersionedFlowSensitive::ObjToVersionMap::value_type &ov : lov)
             {
                 const NodeID o = ov.first;
                 const Version v = ov.second;
                 if (vPtD->getPts(atKey(o, v)).empty()) continue;
  
                 f <<"[ " <<o <<" " <<v<<" ]"<< " -> { ";
                 const PointsTo &ovPts = vPtD->getPts(atKey(o, v));
                 if (!ovPts.empty())
                 {
                     for (NodeID n: ovPts)
                     {
                         f << n << " ";
                     }
                 }
                 else
                 {
                     f << " ";
                 }
                 f << "}\n";
             }
         }
     }
  
     f << "---VERSIONED---\n";
  
     f.close();
     if (f.good())
     {
         SVFUtil::outs() << "\n";
         return;
     }
 }

Friends And Related Function Documentation

◆ VersionedFlowSensitiveStat

friend class VersionedFlowSensitiveStat

friend

Definition at line 34 of file VersionedFlowSensitive.h.

Member Data Documentation

◆ consume

LocVersionMap SVF::VersionedFlowSensitive::consume

private

Maps locations to objects to a version. The object version is what is consumed at that location.

Definition at line 197 of file VersionedFlowSensitive.h.

◆ deltaMap

std::vector<bool> SVF::VersionedFlowSensitive::deltaMap

private

deltaMap[l] means SVFG node l is a delta node, i.e., may get new incoming edges due to OTF callgraph construction.

Definition at line 226 of file VersionedFlowSensitive.h.

◆ deltaSourceMap

std::vector<bool> SVF::VersionedFlowSensitive::deltaSourceMap

private

deltaSourceMap[l] means SVFG node l may be a source to a delta node through an dge added as a result of on-the-fly callgraph construction.

Definition at line 231 of file VersionedFlowSensitive.h.

◆ equivalentObject

Map<NodeID, NodeID> SVF::VersionedFlowSensitive::equivalentObject

private

Definition at line 213 of file VersionedFlowSensitive.h.

◆ invalidVersion

const Version VersionedFlowSensitive::invalidVersion = 0

static

If this version appears, there has been an error.

Definition at line 48 of file VersionedFlowSensitive.h.

◆ isLoadMap

std::vector<bool> SVF::VersionedFlowSensitive::isLoadMap

private

isLoadMap[l] means SVFG node l is a load node.

Definition at line 237 of file VersionedFlowSensitive.h.

◆ isStoreMap

std::vector<bool> SVF::VersionedFlowSensitive::isStoreMap

private

isStoreMap[l] means SVFG node l is a store node.

Definition at line 234 of file VersionedFlowSensitive.h.

◆ meldLabelingTime

double SVF::VersionedFlowSensitive::meldLabelingTime

private

Time to meld label SVFG.

Definition at line 245 of file VersionedFlowSensitive.h.

◆ numPrelabeledNodes

u32_t SVF::VersionedFlowSensitive::numPrelabeledNodes

private

Additional statistics.

Number of prelabeled nodes.

Definition at line 241 of file VersionedFlowSensitive.h.

◆ numPrelabelVersions

u32_t SVF::VersionedFlowSensitive::numPrelabelVersions

private

Number of versions created during prelabeling.

Definition at line 242 of file VersionedFlowSensitive.h.

◆ prelabeledObjects

Set<NodeID> SVF::VersionedFlowSensitive::prelabeledObjects

private

Definition at line 219 of file VersionedFlowSensitive.h.

◆ prelabelingTime

double SVF::VersionedFlowSensitive::prelabelingTime

private

Time to prelabel SVFG.

Definition at line 244 of file VersionedFlowSensitive.h.

◆ stmtReliance

Map<NodeID, Map<Version, NodeBS> > SVF::VersionedFlowSensitive::stmtReliance

private

o x version -> statement nodes which rely on that o/version.

Definition at line 204 of file VersionedFlowSensitive.h.

◆ versionedVarToPropNode

VarToPropNodeMap SVF::VersionedFlowSensitive::versionedVarToPropNode

private

Maps an <object, version> pair to the SVFG node indicating that pair needs to be propagated.

Definition at line 208 of file VersionedFlowSensitive.h.

◆ versionPropTime

double SVF::VersionedFlowSensitive::versionPropTime

private

Time to propagate versions to versions which rely on them.

Definition at line 246 of file VersionedFlowSensitive.h.

◆ versionReliance

VersionRelianceMap SVF::VersionedFlowSensitive::versionReliance

private

o -> (version -> versions which rely on it).

Definition at line 202 of file VersionedFlowSensitive.h.

◆ vfspta

VersionedFlowSensitive * VersionedFlowSensitive::vfspta = nullptr

staticprivate

Definition at line 249 of file VersionedFlowSensitive.h.

◆ vPtD

BVDataPTAImpl::VersionedPTDataTy* SVF::VersionedFlowSensitive::vPtD

private

Points-to DS for working with versions.

Definition at line 222 of file VersionedFlowSensitive.h.

◆ vWorklist

FIFOWorkList<NodeID> SVF::VersionedFlowSensitive::vWorklist

private

Worklist for performing meld labeling, takes SVFG node l. Nodes are added when the version they yield is changed.

Definition at line 217 of file VersionedFlowSensitive.h.

◆ yield

LocVersionMap SVF::VersionedFlowSensitive::yield

private

Actual yield map. Yield analogue to consume.

Definition at line 199 of file VersionedFlowSensitive.h.

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

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

Classes

Public Types

Public Member Functions

Static Public Member Functions

Static Public Attributes

Protected Member Functions

Private Types

Private Member Functions

Static Private Member Functions

Private Attributes

Static Private Attributes

Friends

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ LocVersionMap

◆ MeldVersion

◆ ObjToVersionMap

◆ VarToPropNodeMap

◆ VersionRelianceMap

Constructor & Destructor Documentation

◆ VersionedFlowSensitive()

Member Function Documentation

◆ atKey()

◆ buildDeltaMaps()

◆ buildIsStoreLoadMaps()

◆ classof() [1/2]

◆ classof() [2/2]

◆ cluster()

◆ createVFSWPA()

◆ delta()

◆ deltaSource()

◆ dumpLocVersionMaps()

◆ dumpMeldVersion()

◆ dumpReliances()

◆ finalize()

◆ getConsume()

◆ getReliantVersions()

◆ getStmtReliance()

◆ getVersion()

◆ getYield()

◆ initialize()

◆ isLoad()

◆ isStore()

◆ meld()

◆ meldLabel()

◆ prelabel()

◆ processLoad()

◆ processNode()

◆ processStore()

◆ propagateVersion() [1/2]

◆ propagateVersion() [2/2]

◆ propAlongIndirectEdge()

◆ PTAName()

◆ readPtsFromFile()

◆ readVersionedAnalysisResultFromFile()

◆ releaseVFSWPA()

◆ removeAllIndirectSVFGEdges()

◆ setConsume()

◆ setVersion()

◆ setYield()

◆ solveAndwritePtsToFile()

◆ updateConnectedNodes()

◆ writeVersionedAnalysisResultToFile()

Friends And Related Function Documentation

◆ VersionedFlowSensitiveStat

Member Data Documentation

◆ consume

◆ deltaMap

◆ deltaSourceMap

◆ equivalentObject

◆ invalidVersion

◆ isLoadMap

◆ isStoreMap

◆ meldLabelingTime

◆ numPrelabeledNodes

◆ numPrelabelVersions

◆ prelabeledObjects

◆ prelabelingTime

◆ stmtReliance