#include <SVFGOPT.h>

Inheritance diagram for SVF::SVFGOPT:

Public Member Functions
	SVFGOPT (std::unique_ptr< MemSSA > mssa, VFGK kind)
	Constructor.

	~SVFGOPT () override=default
	Destructor.

void	setTokeepActualOutFormalIn ()

void	setTokeepAllSelfCycle ()

void	setTokeepContextSelfCycle ()

void	readAndOptSVFG (const std::string &filename)
	Optimised SVFG's aren't written in their optimised form; read full SVFG and optimise it.

void	buildAndWriteSVFG (const std::string &filename)
	Optimised SVFG's shouldn't be written in their optimised form; writes the full SVFG to file before optimising.

Public Member Functions inherited from SVF::SVFG
virtual	~SVFG ()
	Destructor.

SVFGStat *	getStat () const
	Return statistics.

void	clearMSSA ()
	Clear MSSA.

MemSSA *	getMSSA () const
	Get SVFG memory SSA.

PointerAnalysis *	getPTA () const
	Get Pointer Analysis.

SVFGNode *	getSVFGNode (NodeID id) const
	Get a SVFG node.

bool	hasSVFGNode (NodeID id) const
	Whether has the SVFGNode.

void	getInterVFEdgesForIndirectCallSite (const CallICFGNode cs, const FunObjVar callee, SVFGEdgeSetTy &edges)
	Get all inter value flow edges of a indirect call site.

void	dump (const std::string &file, bool simple=false)
	Dump graph into dot file.

virtual void	connectCallerAndCallee (const CallICFGNode cs, const FunObjVar callee, SVFGEdgeSetTy &edges)
	Connect SVFG nodes between caller and callee for indirect call site.

const SVFGNode *	getDefSVFGNode (const PAGNode *pagNode) const
	Given a pagNode, return its definition site.

bool	hasDefSVFGNode (const PAGNode *pagNode) const
	Given a pagNode, return whether it has definition site.

void	performStat ()
	Perform statistics.

bool	hasActualINSVFGNodes (const CallICFGNode *cs) const
	Has a SVFGNode.

bool	hasActualOUTSVFGNodes (const CallICFGNode *cs) const

bool	hasFormalINSVFGNodes (const FunObjVar *fun) const

bool	hasFormalOUTSVFGNodes (const FunObjVar *fun) const

ActualINSVFGNodeSet &	getActualINSVFGNodes (const CallICFGNode *cs)
	Get SVFGNode set.

ActualOUTSVFGNodeSet &	getActualOUTSVFGNodes (const CallICFGNode *cs)

FormalINSVFGNodeSet &	getFormalINSVFGNodes (const FunObjVar *fun)

FormalOUTSVFGNodeSet &	getFormalOUTSVFGNodes (const FunObjVar *fun)

const FunObjVar *	isFunEntrySVFGNode (const SVFGNode *node) const
	Whether a node is function entry SVFGNode.

const CallICFGNode *	isCallSiteRetSVFGNode (const SVFGNode *node) const
	Whether a node is callsite return SVFGNode.

void	removeSVFGEdge (SVFGEdge *edge)
	Remove a SVFG edge.

void	removeSVFGNode (SVFGNode *node)
	Remove a SVFGNode.

bool	addSVFGEdge (SVFGEdge *edge)
	Add SVFG edge.

u32_t	getSVFGNodeNum () const
	Return total SVFG node number.

const DummyVersionPropSVFGNode *	addDummyVersionPropSVFGNode (const NodeID object, const NodeID version)

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

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

virtual MRVer *	getMRVERFromString (const std::string &input)

Public Member Functions inherited from SVF::VFG
	VFG (CallGraph *callgraph, VFGK k=FULLSVFG)
	Constructor.

virtual	~VFG ()
	Destructor.

VFGK	getKind () const
	Get VFG kind.

bool	isPtrOnlySVFG () const
	Return true if this VFG only contains pointer related SVFGNodes for pointer analysis.

SVFIR *	getPAG () const
	Return SVFIR.

CallGraph *	getCallGraph () const
	Return PTACallGraph.

VFGNode *	getVFGNode (NodeID id) const
	Get a VFG node.

bool	hasVFGNode (NodeID id) const
	Whether has the VFGNode.

GlobalVFGNodeSet &	getGlobalVFGNodes ()
	Return global stores.

VFGEdge *	getIntraVFGEdge (const VFGNode src, const VFGNode dst, VFGEdge::VFGEdgeK kind)
	Get a SVFG edge according to src and dst.

void	dump (const std::string &file, bool simple=false)
	Dump graph into dot file.

void	view ()
	Dump graph into dot file.

void	updateCallGraph (PointerAnalysis *pta)
	Update VFG based on pointer analysis results.

CallSiteID	getCallSiteID (const CallICFGNode cs, const FunObjVar func) const
	Get callsite given a callsiteID.

const CallICFGNode *	getCallSite (CallSiteID id) const

const VFGNode *	getDefVFGNode (const PAGNode *pagNode) const
	Given a pagNode, return its definition site.

bool	hasLHSTopLevPtr (const VFGNode *node) const

const PAGNode *	getLHSTopLevPtr (const VFGNode *node) const

bool	hasStmtVFGNode (const PAGEdge *pagEdge) const
	Existence checks for VFGNodes.

bool	hasIntraPHIVFGNode (const PAGNode *pagNode) const

bool	hasBinaryOPVFGNode (const PAGNode *pagNode) const

bool	hasUnaryOPVFGNode (const PAGNode *pagNode) const

bool	hasBranchVFGNode (const PAGNode *pagNode) const

bool	hasCmpVFGNode (const PAGNode *pagNode) const

bool	hasActualParmVFGNode (const PAGNode aparm, const CallICFGNode cs) const

bool	hasActualRetVFGNode (const PAGNode *aret) const

bool	hasFormalParmVFGNode (const PAGNode *fparm) const

bool	hasFormalRetVFGNode (const PAGNode *fret) const

StmtVFGNode *	getStmtVFGNode (const PAGEdge *pagEdge) const
	Get an VFGNode.

IntraPHIVFGNode *	getIntraPHIVFGNode (const PAGNode *pagNode) const

BinaryOPVFGNode *	getBinaryOPVFGNode (const PAGNode *pagNode) const

UnaryOPVFGNode *	getUnaryOPVFGNode (const PAGNode *pagNode) const

BranchVFGNode *	getBranchVFGNode (const PAGNode *pagNode) const

CmpVFGNode *	getCmpVFGNode (const PAGNode *pagNode) const

ActualParmVFGNode *	getActualParmVFGNode (const PAGNode aparm, const CallICFGNode cs) const

ActualRetVFGNode *	getActualRetVFGNode (const PAGNode *aret) const

FormalParmVFGNode *	getFormalParmVFGNode (const PAGNode *fparm) const

FormalRetVFGNode *	getFormalRetVFGNode (const PAGNode *fret) const

const FunObjVar *	isFunEntryVFGNode (const VFGNode *node) const
	Whether a node is function entry VFGNode.

bool	hasBlackHoleConstObjAddrAsDef (const PAGNode *pagNode) const
	Whether a PAGNode has a blackhole or const object as its definition.

VFGEdge *	addIntraDirectVFEdge (NodeID srcId, NodeID dstId)

VFGEdge *	addCallEdge (NodeID srcId, NodeID dstId, CallSiteID csId)

VFGEdge *	addRetEdge (NodeID srcId, NodeID dstId, CallSiteID csId)

void	removeVFGEdge (VFGEdge *edge)
	Remove a SVFG edge.

void	removeVFGNode (VFGNode *node)
	Remove a VFGNode.

VFGEdge *	hasIntraVFGEdge (VFGNode src, VFGNode dst, VFGEdge::VFGEdgeK kind)
	Whether we has a SVFG edge.

VFGEdge *	hasInterVFGEdge (VFGNode src, VFGNode dst, VFGEdge::VFGEdgeK kind, CallSiteID csId)

VFGEdge *	hasThreadVFGEdge (VFGNode src, VFGNode dst, VFGEdge::VFGEdgeK kind)

bool	addVFGEdge (VFGEdge *edge)
	Add VFG edge.

VFGNodeSet &	getVFGNodes (const FunObjVar *fun)

bool	hasVFGNodes (const FunObjVar *fun) const

bool	VFGNodes (const FunObjVar *fun) const

VFGNodeSet::const_iterator	getVFGNodeBegin (const FunObjVar *fun) const

VFGNodeSet::const_iterator	getVFGNodeEnd (const FunObjVar *fun) const

Public Member Functions inherited from SVF::GenericGraph< NodeTy, EdgeTy >
	GenericGraph ()
	Constructor.

virtual	~GenericGraph ()
	Destructor.

void	destroy ()
	Release memory.

iterator	begin ()
	Iterators.

iterator	end ()

const_iterator	begin () const

const_iterator	end () const

void	addGNode (NodeID id, NodeType *node)
	Add a Node.

NodeType *	getGNode (NodeID id) const
	Get a node.

bool	hasGNode (NodeID id) const
	Has a node.

void	removeGNode (NodeType *node)
	Delete a node.

u32_t	getTotalNodeNum () const
	Get total number of node/edge.

u32_t	getTotalEdgeNum () const

void	incNodeNum ()
	Increase number of node/edge.

void	incEdgeNum ()

Protected Member Functions
void	buildSVFG () override
	Start building SVFG.

void	optimiseSVFG ()
	Separate optimisation function to avoid duplicate code.

void	connectAParamAndFParam (const PAGNode cs_arg, const PAGNode fun_arg, const CallICFGNode *, CallSiteID csId, SVFGEdgeSetTy &edges) override
	Connect SVFG nodes between caller and callee for indirect call sites.

void	connectFRetAndARet (const PAGNode fun_ret, const PAGNode cs_ret, CallSiteID csId, SVFGEdgeSetTy &edges) override
	Connect formal-ret and actual ret.

void	connectAInAndFIn (const ActualINSVFGNode actualIn, const FormalINSVFGNode formalIn, CallSiteID csId, SVFGEdgeSetTy &edges) override
	Connect actual-in and formal-in.

void	connectFOutAndAOut (const FormalOUTSVFGNode formalOut, const ActualOUTSVFGNode actualOut, CallSiteID csId, SVFGEdgeSetTy &edges) override
	Connect formal-out and actual-out.

NodeID	getActualINDef (NodeID ai) const
	Get def-site of actual-in/formal-out.

NodeID	getFormalOUTDef (NodeID fo) const

Protected Member Functions inherited from SVF::SVFG
void	destroy ()
	Clean up memory.

	SVFG (std::unique_ptr< MemSSA > mssa, VFGK k)
	Constructor.

SVFGEdge *	addIntraIndirectVFEdge (NodeID srcId, NodeID dstId, const NodeBS &cpts)
	Add indirect def-use edges of a memory region between two statements,.

SVFGEdge *	addCallIndirectVFEdge (NodeID srcId, NodeID dstId, const NodeBS &cpts, CallSiteID csId)

SVFGEdge *	addRetIndirectVFEdge (NodeID srcId, NodeID dstId, const NodeBS &cpts, CallSiteID csId)

SVFGEdge *	addThreadMHPIndirectVFEdge (NodeID srcId, NodeID dstId, const NodeBS &cpts)

SVFGEdge *	addInterIndirectVFCallEdge (const ActualINSVFGNode src, const FormalINSVFGNode dst, CallSiteID csId)
	Add inter VF edge from callsite mu to function entry chi.

SVFGEdge *	addInterIndirectVFRetEdge (const FormalOUTSVFGNode src, const ActualOUTSVFGNode dst, CallSiteID csId)
	Add inter VF edge from function exit mu to callsite chi.

virtual void	getInterVFEdgeAtIndCSFromAPToFP (const PAGNode cs_arg, const PAGNode fun_arg, const CallICFGNode *, CallSiteID csId, SVFGEdgeSetTy &edges)
	Get inter value flow edges between indirect call site and callee.

virtual void	getInterVFEdgeAtIndCSFromFRToAR (const PAGNode fun_ret, const PAGNode cs_ret, CallSiteID csId, SVFGEdgeSetTy &edges)

virtual void	getInterVFEdgeAtIndCSFromAInToFIn (ActualINSVFGNode actualIn, const FunObjVar callee, SVFGEdgeSetTy &edges)

virtual void	getInterVFEdgeAtIndCSFromFOutToAOut (ActualOUTSVFGNode actualOut, const FunObjVar callee, SVFGEdgeSetTy &edges)

void	setDef (const PAGNode pagNode, const SVFGNode node)
	Given a PAGNode, set/get its def SVFG node (definition of top level pointers)

NodeID	getDef (const PAGNode *pagNode) const

bool	hasDef (const PAGNode *pagNode) const

void	setDef (const MRVer mvar, const SVFGNode node)
	Given a MSSADef, set/get its def SVFG node (definition of address-taken variables)

NodeID	getDef (const MRVer *mvar) const

void	addSVFGNodesForAddrTakenVars ()
	Create SVFG nodes for address-taken variables.

void	connectIndirectSVFGEdges ()
	Connect direct SVFG edges between two SVFG nodes (value-flow of top address-taken variables)

void	connectFromGlobalToProgEntry ()
	Connect indirect SVFG edges from global initializers (store) to main function entry.

virtual void	addSVFGNode (SVFGNode node, ICFGNode icfgNode)
	Add SVFG node.

void	addFormalINSVFGNode (const FunEntryICFGNode funEntry, const MRVer resVer, const NodeID nodeId)
	Add memory Function entry chi SVFG node.

void	addFormalOUTSVFGNode (const FunExitICFGNode funExit, const MRVer ver, const NodeID nodeId)
	Add memory Function return mu SVFG node.

void	addActualINSVFGNode (const CallICFGNode callsite, const MRVer ver, const NodeID nodeId)
	Add memory callsite mu SVFG node.

void	addActualOUTSVFGNode (const CallICFGNode callsite, const MRVer resVer, const NodeID nodeId)
	Add memory callsite chi SVFG node.

void	addIntraMSSAPHISVFGNode (ICFGNode BlockICFGNode, const Map< u32_t, const MRVer >::const_iterator opVerBegin, const Map< u32_t, const MRVer * >::const_iterator opVerEnd, const MRVer *resVer, const NodeID nodeId)
	Add memory SSA PHI SVFG node.

bool	hasFuncEntryChi (const FunObjVar *func) const
	Has function for EntryCHI/RetMU/CallCHI/CallMU.

bool	hasFuncRetMu (const FunObjVar *func) const

bool	hasCallSiteChi (const CallICFGNode *cs) const

bool	hasCallSiteMu (const CallICFGNode *cs) const

Protected Member Functions inherited from SVF::VFG
void	destroy ()
	Clean up memory.

void	checkIntraEdgeParents (const VFGNode srcNode, const VFGNode dstNode)
	sanitize Intra edges, verify that both nodes belong to the same function.

VFGEdge *	addInterEdgeFromAPToFP (ActualParmVFGNode src, FormalParmVFGNode dst, CallSiteID csId)
	Add inter VF edge from actual to formal parameters.

VFGEdge *	addInterEdgeFromFRToAR (FormalRetVFGNode src, ActualRetVFGNode dst, CallSiteID csId)
	Add inter VF edge from callee return to callsite receive parameter.

VFGEdge *	addInterEdgeFromAPToFP (NodeID src, NodeID dst, CallSiteID csId)
	Add inter VF edge from actual to formal parameters.

VFGEdge *	addInterEdgeFromFRToAR (NodeID src, NodeID dst, CallSiteID csId)
	Add inter VF edge from callee return to callsite receive parameter.

void	setDef (const PAGNode pagNode, const VFGNode node)
	Given a PAGNode, set/get its def VFG node (definition of top level pointers)

NodeID	getDef (const PAGNode *pagNode) const

bool	hasDef (const PAGNode *pagNode) const

void	addVFGNodes ()
	Create VFG nodes.

virtual SVFStmt::SVFStmtSetTy &	getPAGEdgeSet (SVFStmt::PEDGEK kind)
	Get PAGEdge set.

virtual bool	isInterestedPAGNode (const SVFVar *node) const

void	connectDirectVFGEdges ()
	Create edges between VFG nodes within a function.

void	addVFGInterEdges (const CallICFGNode cs, const FunObjVar callee)
	Create edges between VFG nodes across functions.

bool	isPhiCopyEdge (const PAGEdge *copy) const

virtual void	addVFGNode (VFGNode vfgNode, ICFGNode icfgNode)
	Add a VFG node.

void	addStmtVFGNode (StmtVFGNode node, const PAGEdge pagEdge)
	Add a VFG node for program statement.

void	addNullPtrVFGNode (const PAGNode *pagNode)

void	addAddrVFGNode (const AddrStmt *addr)
	Add an Address VFG node.

void	addCopyVFGNode (const CopyStmt *copy)
	Add a Copy VFG node.

void	addGepVFGNode (const GepStmt *gep)
	Add a Gep VFG node.

void	addLoadVFGNode (const LoadStmt *load)
	Add a Load VFG node.

void	addStoreVFGNode (const StoreStmt *store)

void	addActualParmVFGNode (const PAGNode aparm, const CallICFGNode cs)

void	addFormalParmVFGNode (const PAGNode fparm, const FunObjVar fun, CallPESet &callPEs)
	Add a formal parameter VFG node.

void	addFormalRetVFGNode (const PAGNode uniqueFunRet, const FunObjVar fun, RetPESet &retPEs)

void	addActualRetVFGNode (const PAGNode ret, const CallICFGNode cs)
	Add a callsite Receive VFG node.

void	addIntraPHIVFGNode (const MultiOpndStmt *edge)
	Add an llvm PHI VFG node.

void	addCmpVFGNode (const CmpStmt *edge)
	Add a Compare VFG node.

void	addBinaryOPVFGNode (const BinaryOPStmt *edge)
	Add a BinaryOperator VFG node.

void	addUnaryOPVFGNode (const UnaryOPStmt *edge)
	Add a UnaryOperator VFG node.

void	addBranchVFGNode (const BranchStmt *edge)
	Add a BranchVFGNode.

Private Types
typedef Set< SVFGNode * >	SVFGNodeSet

typedef Map< NodeID, NodeID >	NodeIDToNodeIDMap

typedef FIFOWorkList< const MSSAPHISVFGNode * >	WorkList

Private Member Functions
void	parseSelfCycleHandleOption ()

SVFGEdge *	addCallIndirectSVFGEdge (NodeID srcId, NodeID dstId, CallSiteID csid, const NodeBS &cpts)
	Add inter-procedural value flow edge.

SVFGEdge *	addRetIndirectSVFGEdge (NodeID srcId, NodeID dstId, CallSiteID csid, const NodeBS &cpts)
	Add indirect ret edge from src to dst with one call site ID.

void	handleInterValueFlow ()

void	replaceFParamARetWithPHI (PHISVFGNode phi, SVFGNode svfgNode)
	Replace FormalParam/ActualRet node with PHI node.

void	retargetEdgesOfAInFOut (SVFGNode *node)
	Retarget edges related to actual-in/-out and formal-in/-out.

void	retargetEdgesOfAOutFIn (SVFGNode *node)
	Connect actual-out/formal-in's predecessors to their successors directly.

void	handleIntraValueFlow ()
	Remove MSSAPHI SVFG nodes.

void	initialWorkList ()
	Initial work list with MSSAPHI nodes which may be removed.

bool	addIntoWorklist (const SVFGNode *node)

void	bypassMSSAPHINode (const MSSAPHISVFGNode *node)
	Remove MSSAPHI node if possible.

bool	checkSelfCycleEdges (const MSSAPHISVFGNode *node)
	Remove self cycle edges if needed. Return TRUE if some self cycle edges remained.

bool	addNewSVFGEdge (NodeID srcId, NodeID dstId, const SVFGEdge preEdge, const SVFGEdge succEdge)
	Add new SVFG edge from src to dst.

bool	bothInterEdges (const SVFGEdge edge1, const SVFGEdge edge2) const
	Return TRUE if both edges are indirect call/ret edges.

void	addInterPHIOperands (PHISVFGNode phi, const PAGNode operand)

InterPHISVFGNode *	addInterPHIForFP (const FormalParmSVFGNode *fp)
	Add inter PHI SVFG node for formal parameter.

InterPHISVFGNode *	addInterPHIForAR (const ActualRetSVFGNode *ar)
	Add inter PHI SVFG node for actual return.

void	resetDef (const PAGNode pagNode, const SVFGNode node)

bool	isDefOfAInFOut (const SVFGNode *node)

bool	actualInOfIndCS (const ActualINSVFGNode *ai) const
	Check if actual-in/actual-out exist at indirect call site.

bool	actualOutOfIndCS (const ActualOUTSVFGNode *ao) const

bool	formalInOfAddressTakenFunc (const FormalINSVFGNode *fi) const
	Check if formal-in/formal-out reside in address-taken function.

bool	formalOutOfAddressTakenFunc (const FormalOUTSVFGNode *fo) const

bool	isConnectingTwoCallSites (const SVFGNode *node) const
	Return TRUE if this node has both incoming call/ret and outgoing call/ret edges.

bool	canBeRemoved (const SVFGNode *node)

void	removeAllEdges (const SVFGNode *node)
	Remove edges of a SVFG node.

void	removeInEdges (const SVFGNode *node)

void	removeOutEdges (const SVFGNode *node)


void	setActualINDef (NodeID ai, NodeID def)

void	setFormalOUTDef (NodeID fo, NodeID def)

Private Attributes
NodeIDToNodeIDMap	actualInToDefMap
	map actual-in to its def-site node

NodeIDToNodeIDMap	formalOutToDefMap
	map formal-out to its def-site node

NodeBS	defNodes
	preserved def nodes of formal-in/actual-out

WorkList	worklist
	storing MSSAPHI nodes which may be removed.

bool	keepActualOutFormalIn

bool	keepAllSelfCycle

bool	keepContextSelfCycle

Additional Inherited Members
Public Types inherited from SVF::SVFG
typedef VFGNodeIDToNodeMapTy	SVFGNodeIDToNodeMapTy

typedef Map< const PAGNode *, NodeID >	PAGNodeToDefMapTy

typedef Map< const MRVer *, NodeID >	MSSAVarToDefMapTy

typedef NodeBS	ActualINSVFGNodeSet

typedef NodeBS	ActualOUTSVFGNodeSet

typedef NodeBS	FormalINSVFGNodeSet

typedef NodeBS	FormalOUTSVFGNodeSet

typedef Map< const CallICFGNode *, ActualINSVFGNodeSet >	CallSiteToActualINsMapTy

typedef Map< const CallICFGNode *, ActualOUTSVFGNodeSet >	CallSiteToActualOUTsMapTy

typedef Map< const FunObjVar *, FormalINSVFGNodeSet >	FunctionToFormalINsMapTy

typedef Map< const FunObjVar *, FormalOUTSVFGNodeSet >	FunctionToFormalOUTsMapTy

typedef MemSSA::MUSet	MUSet

typedef MemSSA::CHISet	CHISet

typedef MemSSA::PHISet	PHISet

typedef MemSSA::MU	MU

typedef MemSSA::CHI	CHI

typedef MemSSA::LOADMU	LOADMU

typedef MemSSA::STORECHI	STORECHI

typedef MemSSA::RETMU	RETMU

typedef MemSSA::ENTRYCHI	ENTRYCHI

typedef MemSSA::CALLCHI	CALLCHI

typedef MemSSA::CALLMU	CALLMU

Public Types inherited from SVF::VFG
enum	VFGK { FULLSVFG , PTRONLYSVFG , FULLSVFG_OPT , PTRONLYSVFG_OPT }
	VFG kind. More...

typedef OrderedMap< NodeID, VFGNode * >	VFGNodeIDToNodeMapTy

typedef Set< VFGNode * >	VFGNodeSet

typedef Map< const PAGNode *, NodeID >	PAGNodeToDefMapTy

typedef Map< std::pair< NodeID, const CallICFGNode * >, ActualParmVFGNode * >	PAGNodeToActualParmMapTy

typedef Map< const PAGNode , ActualRetVFGNode >	PAGNodeToActualRetMapTy

typedef Map< const PAGNode , FormalParmVFGNode >	PAGNodeToFormalParmMapTy

typedef Map< const PAGNode , FormalRetVFGNode >	PAGNodeToFormalRetMapTy

typedef Map< const PAGEdge , StmtVFGNode >	PAGEdgeToStmtVFGNodeMapTy

typedef Map< const PAGNode , IntraPHIVFGNode >	PAGNodeToPHIVFGNodeMapTy

typedef Map< const PAGNode , BinaryOPVFGNode >	PAGNodeToBinaryOPVFGNodeMapTy

typedef Map< const PAGNode , UnaryOPVFGNode >	PAGNodeToUnaryOPVFGNodeMapTy

typedef Map< const PAGNode , BranchVFGNode >	PAGNodeToBranchVFGNodeMapTy

typedef Map< const PAGNode , CmpVFGNode >	PAGNodeToCmpVFGNodeMapTy

typedef Map< const FunObjVar *, VFGNodeSet >	FunToVFGNodesMapTy

typedef FormalParmVFGNode::CallPESet	CallPESet

typedef FormalRetVFGNode::RetPESet	RetPESet

typedef VFGEdge::VFGEdgeSetTy	VFGEdgeSetTy

typedef VFGEdge::SVFGEdgeSetTy	SVFGEdgeSetTy

typedef VFGEdge::VFGEdgeSetTy::iterator	VFGNodeIter

typedef VFGNodeIDToNodeMapTy::iterator	iterator

typedef VFGNodeIDToNodeMapTy::const_iterator	const_iterator

typedef SVFIR::SVFStmtSet	SVFStmtSet

typedef Set< const VFGNode * >	GlobalVFGNodeSet

typedef Set< const PAGNode * >	PAGNodeSet

Public Types inherited from SVF::GenericGraph< NodeTy, EdgeTy >
typedef NodeTy	NodeType

typedef EdgeTy	EdgeType

typedef OrderedMap< NodeID, NodeType * >	IDToNodeMapTy
	NodeID to GenericNode map.

typedef IDToNodeMapTy::iterator	iterator
	Node Iterators.

typedef IDToNodeMapTy::const_iterator	const_iterator

Public Attributes inherited from SVF::GenericGraph< NodeTy, EdgeTy >
u32_t	edgeNum
	total num of node

u32_t	nodeNum
	total num of edge

Protected Attributes inherited from SVF::SVFG
MSSAVarToDefMapTy	MSSAVarToDefMap
	map a memory SSA operator to its definition SVFG node

CallSiteToActualINsMapTy	callSiteToActualINMap

CallSiteToActualOUTsMapTy	callSiteToActualOUTMap

FunctionToFormalINsMapTy	funToFormalINMap

FunctionToFormalOUTsMapTy	funToFormalOUTMap

SVFGStat *	stat

std::unique_ptr< MemSSA >	mssa

PointerAnalysis *	pta

Protected Attributes inherited from SVF::VFG
NodeID	totalVFGNode

PAGNodeToDefMapTy	PAGNodeToDefMap
	map a pag node to its definition SVG node

PAGNodeToActualParmMapTy	PAGNodeToActualParmMap
	map a PAGNode to an actual parameter

PAGNodeToActualRetMapTy	PAGNodeToActualRetMap
	map a PAGNode to an actual return

PAGNodeToFormalParmMapTy	PAGNodeToFormalParmMap
	map a PAGNode to a formal parameter

PAGNodeToFormalRetMapTy	PAGNodeToFormalRetMap
	map a PAGNode to a formal return

PAGNodeToPHIVFGNodeMapTy	PAGNodeToIntraPHIVFGNodeMap
	map a PAGNode to its PHIVFGNode

PAGNodeToBinaryOPVFGNodeMapTy	PAGNodeToBinaryOPVFGNodeMap
	map a PAGNode to its BinaryOPVFGNode

PAGNodeToUnaryOPVFGNodeMapTy	PAGNodeToUnaryOPVFGNodeMap
	map a PAGNode to its UnaryOPVFGNode

PAGNodeToBranchVFGNodeMapTy	PAGNodeToBranchVFGNodeMap
	map a PAGNode to its BranchVFGNode

PAGNodeToCmpVFGNodeMapTy	PAGNodeToCmpVFGNodeMap
	map a PAGNode to its CmpVFGNode

PAGEdgeToStmtVFGNodeMapTy	PAGEdgeToStmtVFGNodeMap
	map a PAGEdge to its StmtVFGNode

FunToVFGNodesMapTy	funToVFGNodesMap
	map a function to its VFGNodes;

GlobalVFGNodeSet	globalVFGNodes
	set of global store VFG nodes

CallGraph *	callgraph

SVFIR *	pag

VFGK	kind

Protected Attributes inherited from SVF::GenericGraph< NodeTy, EdgeTy >
IDToNodeMapTy	IDToNodeMap
	node map

Detailed Description

Optimised SVFG.

FormalParam/ActualRet is converted into Phi. ActualParam/FormalRet becomes the operands of Phi nodes created at callee/caller's entry/callsite.
ActualIns/ActualOuts resides at direct call sites id removed. Sources of its incoming edges are connected with the destinations of its outgoing edges directly.
FormalIns/FormalOuts reside at the entry/exit of non-address-taken functions is removed as ActualIn/ActualOuts.
MSSAPHI nodes are removed if it have no self cycle. Otherwise depends on user option.

Definition at line 56 of file SVFGOPT.h.

Member Typedef Documentation

◆ NodeIDToNodeIDMap

typedef Map<NodeID, NodeID> SVF::SVFGOPT::NodeIDToNodeIDMap

private

Definition at line 59 of file SVFGOPT.h.

◆ SVFGNodeSet

typedef Set<SVFGNode*> SVF::SVFGOPT::SVFGNodeSet

private

Definition at line 58 of file SVFGOPT.h.

◆ WorkList

typedef FIFOWorkList<const MSSAPHISVFGNode*> SVF::SVFGOPT::WorkList

private

Definition at line 60 of file SVFGOPT.h.

Constructor & Destructor Documentation

◆ SVFGOPT()

SVF::SVFGOPT::SVFGOPT	(	std::unique_ptr< MemSSA >	mssa,
		VFGK	kind
	)

inline

Constructor.

Definition at line 64 of file SVFGOPT.h.

                                                   : SVFG(std::move(mssa), kind)
    {
        keepAllSelfCycle = keepContextSelfCycle = keepActualOutFormalIn = false;
    }

◆ ~SVFGOPT()

SVF::SVFGOPT::~SVFGOPT ( )

overridedefault

Destructor.

Member Function Documentation

◆ actualInOfIndCS()

bool SVF::SVFGOPT::actualInOfIndCS ( const ActualINSVFGNode * ai ) const

inlineprivate

Check if actual-in/actual-out exist at indirect call site.

Definition at line 302 of file SVFGOPT.h.

    {
        return (SVFIR::getPAG()->isIndirectCallSites(ai->getCallSite()));
    }

◆ actualOutOfIndCS()

bool SVF::SVFGOPT::actualOutOfIndCS ( const ActualOUTSVFGNode * ao ) const

inlineprivate

Definition at line 306 of file SVFGOPT.h.

    {
        return (SVFIR::getPAG()->isIndirectCallSites(ao->getCallSite()));
    }

◆ addCallIndirectSVFGEdge()

SVFGEdge * SVFGOPT::addCallIndirectSVFGEdge	(	NodeID	srcId,
		NodeID	dstId,
		CallSiteID	csid,
		const NodeBS &	cpts
	)

private

Add inter-procedural value flow edge.

Add indirect call edge from src to dst with one call site ID.

Definition at line 88 of file SVFGOPT.cpp.

{
    if (Options::ContextInsensitive())
        return addIntraIndirectVFEdge(srcId, dstId, cpts);
    else
        return addCallIndirectVFEdge(srcId, dstId, cpts, csid);
}

◆ addInterPHIForAR()

InterPHISVFGNode * SVF::SVFGOPT::addInterPHIForAR ( const ActualRetSVFGNode * ar )

inlineprivate

Add inter PHI SVFG node for actual return.

Definition at line 261 of file SVFGOPT.h.

    {
        InterPHISVFGNode* sNode = new InterPHISVFGNode(totalVFGNode++,ar);
        addSVFGNode(sNode, const_cast<RetICFGNode*>(
                        ar->getCallSite()->getRetICFGNode()));
        resetDef(ar->getRev(),sNode);
        return sNode;
    }

◆ addInterPHIForFP()

InterPHISVFGNode * SVF::SVFGOPT::addInterPHIForFP ( const FormalParmSVFGNode * fp )

inlineprivate

Add inter PHI SVFG node for formal parameter.

Definition at line 253 of file SVFGOPT.h.

    {
        InterPHISVFGNode* sNode = new InterPHISVFGNode(totalVFGNode++,fp);
        addSVFGNode(sNode, pag->getICFG()->getFunEntryICFGNode(fp->getFun()));
        resetDef(fp->getParam(),sNode);
        return sNode;
    }

◆ addInterPHIOperands()

void SVF::SVFGOPT::addInterPHIOperands	(	PHISVFGNode *	phi,
		const PAGNode *	operand
	)

inlineprivate

Definition at line 247 of file SVFGOPT.h.

    {
        phi->setOpVer(phi->getOpVerNum(), operand);
    }

◆ addIntoWorklist()

bool SVF::SVFGOPT::addIntoWorklist ( const SVFGNode * node )

inlineprivate

Only MSSAPHI node which satisfy following conditions will be removed:

it's not def-site of actual-in/formal-out;
it doesn't have incoming and outgoing call/ret at the same time.

Definition at line 220 of file SVFGOPT.h.

    {
        if (const MSSAPHISVFGNode* phi = SVFUtil::dyn_cast<MSSAPHISVFGNode>(node))
        {
            if (isConnectingTwoCallSites(phi) == false && isDefOfAInFOut(phi) == false)
                return worklist.push(phi);
        }
        return false;
    }

◆ addNewSVFGEdge()

bool SVFGOPT::addNewSVFGEdge	(	NodeID	srcId,
		NodeID	dstId,
		const SVFGEdge *	preEdge,
		const SVFGEdge *	succEdge
	)

private

Add new SVFG edge from src to dst.

Add new SVFG edge from src to dst. The edge's kind depends on preEdge and succEdge. Self-cycle edges may be added here.

Definition at line 543 of file SVFGOPT.cpp.

{
    assert(SVFUtil::isa<IndirectSVFGEdge>(preEdge) && SVFUtil::isa<IndirectSVFGEdge>(succEdge)
           && "either pre or succ edge is not indirect SVFG edge");
 
    const IndirectSVFGEdge* preIndEdge = SVFUtil::cast<IndirectSVFGEdge>(preEdge);
    const IndirectSVFGEdge* succIndEdge = SVFUtil::cast<IndirectSVFGEdge>(succEdge);
 
    NodeBS intersection = preIndEdge->getPointsTo();
    intersection &= succIndEdge->getPointsTo();
 
    if (intersection.empty())
        return false;
 
    assert(bothInterEdges(preEdge, succEdge) == false && "both edges are inter edges");
 
    if (const CallIndSVFGEdge* preCallEdge = SVFUtil::dyn_cast<CallIndSVFGEdge>(preEdge))
    {
        return addCallIndirectSVFGEdge(srcId, dstId, preCallEdge->getCallSiteId(), intersection);
    }
    else if (const CallIndSVFGEdge* succCallEdge = SVFUtil::dyn_cast<CallIndSVFGEdge>(succEdge))
    {
        return addCallIndirectSVFGEdge(srcId, dstId, succCallEdge->getCallSiteId(), intersection);
    }
    else if (const RetIndSVFGEdge* preRetEdge = SVFUtil::dyn_cast<RetIndSVFGEdge>(preEdge))
    {
        return addRetIndirectSVFGEdge(srcId, dstId, preRetEdge->getCallSiteId(), intersection);
    }
    else if (const RetIndSVFGEdge* succRetEdge = SVFUtil::dyn_cast<RetIndSVFGEdge>(succEdge))
    {
        return addRetIndirectSVFGEdge(srcId, dstId, succRetEdge->getCallSiteId(), intersection);
    }
    else
    {
        return addIntraIndirectVFEdge(srcId, dstId, intersection);
    }
 
    return false;
}

◆ addRetIndirectSVFGEdge()

SVFGEdge * SVFGOPT::addRetIndirectSVFGEdge	(	NodeID	srcId,
		NodeID	dstId,
		CallSiteID	csid,
		const NodeBS &	cpts
	)

private

Add indirect ret edge from src to dst with one call site ID.

Definition at line 99 of file SVFGOPT.cpp.

{
    if (Options::ContextInsensitive())
        return addIntraIndirectVFEdge(srcId, dstId, cpts);
    else
        return addRetIndirectVFEdge(srcId, dstId, cpts, csid);
}

◆ bothInterEdges()

bool SVF::SVFGOPT::bothInterEdges	(	const SVFGEdge *	edge1,
		const SVFGEdge *	edge2
	)		const

inlineprivate

Return TRUE if both edges are indirect call/ret edges.

Definition at line 240 of file SVFGOPT.h.

    {
        bool inter1 = SVFUtil::isa<CallIndSVFGEdge, RetIndSVFGEdge>(edge1);
        bool inter2 = SVFUtil::isa<CallIndSVFGEdge, RetIndSVFGEdge>(edge2);
        return (inter1 && inter2);
    }

◆ buildAndWriteSVFG()

void SVFGOPT::buildAndWriteSVFG ( const std::string & filename )

Optimised SVFG's shouldn't be written in their optimised form; writes the full SVFG to file before optimising.

Shouldn't write optimised SVFG to file; writes the built SVFG to file before optimisation.

Definition at line 54 of file SVFGOPT.cpp.

{
    SVFG::buildSVFG();
    SVFG::writeToFile(filename);
    optimiseSVFG();
}

◆ buildSVFG()

void SVFGOPT::buildSVFG ( )

overrideprotectedvirtual

Start building SVFG.

Build SVFG 1) build SVFG nodes a) statements for top level pointers (PAGEdges) b) operators of address-taken variables (MSSAPHI and MSSACHI) 2) connect SVFG edges a) between two statements (PAGEdges) b) between two memory SSA operators (MSSAPHI MSSAMU and MSSACHI)

Reimplemented from SVF::SVFG.

Definition at line 61 of file SVFGOPT.cpp.

{
    SVFG::buildSVFG();
    optimiseSVFG();
}

◆ bypassMSSAPHINode()

void SVFGOPT::bypassMSSAPHINode ( const MSSAPHISVFGNode * node )

private

Remove MSSAPHI node if possible.

Remove MSSAPHI node if possible

add new edges from predecessor to all successors.

if no new edge is added, the number of dst node's incoming edges may be decreased. try to analyze it again.

if no new edge is added, the number of src node's outgoing edges may be decreased. try to analyze it again.

Definition at line 500 of file SVFGOPT.cpp.

{
    SVFGNode::const_iterator inEdgeIt = node->InEdgeBegin();
    SVFGNode::const_iterator inEdgeEit = node->InEdgeEnd();
    for (; inEdgeIt != inEdgeEit; ++inEdgeIt)
    {
        const SVFGEdge* preEdge = *inEdgeIt;
        const SVFGNode* srcNode = preEdge->getSrcNode();
 
        bool added = false;
        SVFGNode::const_iterator outEdgeIt = node->OutEdgeBegin();
        SVFGNode::const_iterator outEdgeEit = node->OutEdgeEnd();
        for (; outEdgeIt != outEdgeEit; ++outEdgeIt)
        {
            const SVFGEdge* succEdge = *outEdgeIt;
            const SVFGNode* dstNode = (*outEdgeIt)->getDstNode();
            if (srcNode->getId() != dstNode->getId()
                    && addNewSVFGEdge(srcNode->getId(), dstNode->getId(), preEdge, succEdge))
                added = true;
            else
            {
                addIntoWorklist(dstNode);
            }
        }
 
        if (added == false)
        {
            addIntoWorklist(srcNode);
        }
    }
 
    removeAllEdges(node);
}

◆ canBeRemoved()

bool SVFGOPT::canBeRemoved ( const SVFGNode * node )

private

Return TRUE if this SVFGNode can be removed. Nodes can be removed if it is:

ActualParam/FormalParam/ActualRet/FormalRet
ActualIN if it doesn't reside at indirect call site
FormalIN if it doesn't reside at the entry of address-taken function and it's not definition site of ActualIN
ActualOUT if it doesn't reside at indirect call site and it's not definition site of FormalOUT
FormalOUT if it doesn't reside at the exit of address-taken function

Now each SVFG edge can only be associated with one call site id, so if this node has both incoming call/ret and outgoing call/ret edges, we don't remove this node.

Definition at line 354 of file SVFGOPT.cpp.

{
    if (SVFUtil::isa<ActualParmSVFGNode, FormalParmSVFGNode,
            ActualRetSVFGNode, FormalRetSVFGNode>(node))
        return true;
    else if (SVFUtil::isa<ActualINSVFGNode, ActualOUTSVFGNode, FormalINSVFGNode,
             FormalOUTSVFGNode, MSSAPHISVFGNode>(node))
    {
        if (isConnectingTwoCallSites(node))
            return false;
 
        if (const ActualINSVFGNode* ai = SVFUtil::dyn_cast<ActualINSVFGNode>(node))
        {
            return (actualInOfIndCS(ai) == false);
        }
        else if (const ActualOUTSVFGNode* ao = SVFUtil::dyn_cast<ActualOUTSVFGNode>(node))
        {
            return (actualOutOfIndCS(ao) == false && isDefOfAInFOut(node) == false);
        }
        else if (const FormalINSVFGNode* fi = SVFUtil::dyn_cast<FormalINSVFGNode>(node))
        {
            return (formalInOfAddressTakenFunc(fi) == false && isDefOfAInFOut(node) == false);
        }
        else if (const FormalOUTSVFGNode* fo = SVFUtil::dyn_cast<FormalOUTSVFGNode>(node))
        {
            return (formalOutOfAddressTakenFunc(fo) == false);
        }
    }
 
    return false;
}

◆ checkSelfCycleEdges()

bool SVFGOPT::checkSelfCycleEdges ( const MSSAPHISVFGNode * node )

private

Remove self cycle edges if needed. Return TRUE if some self cycle edges remained.

Remove self cycle edges according to specified options:

keepAllSelfCycle = TRUE: all self cycle edges are kept;
keepContextSelfCycle = TRUE: all self cycle edges related-to context are kept;
Otherwise, all self cycle edges are NOT kept. Return TRUE if some self cycle edges remain in this node.

There's no need to check other edge if we do not remove self cycle

Continue checking and remove other self cycle which are NOT context-related

Definition at line 462 of file SVFGOPT.cpp.

{
    bool hasSelfCycle = false;
 
    SVFGEdge::SVFGEdgeSetTy inEdges = node->getInEdges();
    SVFGNode::const_iterator inEdgeIt = inEdges.begin();
    SVFGNode::const_iterator inEdgeEit = inEdges.end();
    for (; inEdgeIt != inEdgeEit; ++inEdgeIt)
    {
        SVFGEdge* preEdge = *inEdgeIt;
 
        if (preEdge->getSrcID() == preEdge->getDstID())
        {
            if (keepAllSelfCycle)
            {
                hasSelfCycle = true;
                break;  
            }
            else if (keepContextSelfCycle &&
                     SVFUtil::isa<CallIndSVFGEdge, RetIndSVFGEdge>(preEdge))
            {
                hasSelfCycle = true;
                continue;   
            }
            else
            {
                assert(SVFUtil::isa<IndirectSVFGEdge>(preEdge) && "can only remove indirect SVFG edge");
                removeSVFGEdge(preEdge);
            }
        }
    }
 
    return hasSelfCycle;
}

◆ connectAInAndFIn()

void SVF::SVFGOPT::connectAInAndFIn	(	const ActualINSVFGNode *	actualIn,
		const FormalINSVFGNode *	formalIn,
		CallSiteID	csId,
		SVFGEdgeSetTy &	edges
	)

inlineoverrideprotectedvirtual

Connect actual-in and formal-in.

Reimplemented from SVF::SVFG.

Definition at line 129 of file SVFGOPT.h.

    {
        NodeBS intersection = actualIn->getPointsTo();
        intersection &= formalIn->getPointsTo();
        if (intersection.empty() == false)
        {
            NodeID aiDef = getActualINDef(actualIn->getId());
            SVFGEdge* edge = addCallIndirectSVFGEdge(aiDef,formalIn->getId(),csId,intersection);
            if (edge != nullptr)
                edges.insert(edge);
        }
    }

◆ connectAParamAndFParam()

void SVF::SVFGOPT::connectAParamAndFParam	(	const PAGNode *	cs_arg,
		const PAGNode *	fun_arg,
		const CallICFGNode *	,
		CallSiteID	csId,
		SVFGEdgeSetTy &	edges
	)

inlineoverrideprotectedvirtual

Connect SVFG nodes between caller and callee for indirect call sites.

Reimplemented from SVF::VFG.

Definition at line 98 of file SVFGOPT.h.

    {
        NodeID phiId = getDef(fun_arg);
        SVFGEdge* edge = addCallEdge(getDef(cs_arg), phiId, csId);
        if (edge != nullptr)
        {
            PHISVFGNode* phi = SVFUtil::cast<PHISVFGNode>(getSVFGNode(phiId));
            addInterPHIOperands(phi, cs_arg);
            edges.insert(edge);
        }
    }

◆ connectFOutAndAOut()

void SVF::SVFGOPT::connectFOutAndAOut	(	const FormalOUTSVFGNode *	formalOut,
		const ActualOUTSVFGNode *	actualOut,
		CallSiteID	csId,
		SVFGEdgeSetTy &	edges
	)

inlineoverrideprotectedvirtual

Connect formal-out and actual-out.

Reimplemented from SVF::SVFG.

Definition at line 142 of file SVFGOPT.h.

    {
        NodeBS intersection = formalOut->getPointsTo();
        intersection &= actualOut->getPointsTo();
        if (intersection.empty() == false)
        {
            NodeID foDef = getFormalOUTDef(formalOut->getId());
            SVFGEdge* edge = addRetIndirectSVFGEdge(foDef,actualOut->getId(),csId,intersection);
            if (edge != nullptr)
                edges.insert(edge);
        }
    }

◆ connectFRetAndARet()

void SVF::SVFGOPT::connectFRetAndARet	(	const PAGNode *	fun_ret,
		const PAGNode *	cs_ret,
		CallSiteID	csId,
		SVFGEdgeSetTy &	edges
	)

inlineoverrideprotectedvirtual

Connect formal-ret and actual ret.

If a function does not have any return instruction. The def of a FormalRetVFGNode is itself (see VFG.h: addFormalRetVFGNode). Therefore, we do not connect return edge from a function without any return instruction (i.e., pag->isPhiNode(fun_ret)==false) because unique fun_ret PAGNode was not collected as a PhiNode in SVFIRBuilder::visitReturnInst

Reimplemented from SVF::VFG.

Definition at line 110 of file SVFGOPT.h.

    {
        NodeID phiId = getDef(cs_ret);
        NodeID retdef = getDef(fun_ret);
        if (pag->isPhiNode(fun_ret)==false)
            return;
 
        SVFGEdge* edge = addRetEdge(retdef, phiId, csId);
        if (edge != nullptr)
        {
            PHISVFGNode* phi = SVFUtil::cast<PHISVFGNode>(getSVFGNode(phiId));
            addInterPHIOperands(phi, fun_ret);
            edges.insert(edge);
        }
    }

◆ formalInOfAddressTakenFunc()

bool SVF::SVFGOPT::formalInOfAddressTakenFunc ( const FormalINSVFGNode * fi ) const

inlineprivate

Check if formal-in/formal-out reside in address-taken function.

Definition at line 314 of file SVFGOPT.h.

    {
        return (fi->getFun()->hasAddressTaken());
    }

◆ formalOutOfAddressTakenFunc()

bool SVF::SVFGOPT::formalOutOfAddressTakenFunc ( const FormalOUTSVFGNode * fo ) const

inlineprivate

Definition at line 318 of file SVFGOPT.h.

    {
        return (fo->getFun()->hasAddressTaken());
    }

◆ getActualINDef()

NodeID SVF::SVFGOPT::getActualINDef ( NodeID ai ) const

inlineprotected

Get def-site of actual-in/formal-out.

Definition at line 158 of file SVFGOPT.h.

    {
        NodeIDToNodeIDMap::const_iterator it = actualInToDefMap.find(ai);
        assert(it != actualInToDefMap.end() && "can not find actual-in's def");
        return it->second;
    }

◆ getFormalOUTDef()

NodeID SVF::SVFGOPT::getFormalOUTDef ( NodeID fo ) const

inlineprotected

Definition at line 164 of file SVFGOPT.h.

    {
        NodeIDToNodeIDMap::const_iterator it = formalOutToDefMap.find(fo);
        assert(it != formalOutToDefMap.end() && "can not find formal-out's def");
        return it->second;
    }

◆ handleInterValueFlow()

void SVFGOPT::handleInterValueFlow ( )

private

Convert FormalParmSVFGNode into PHISVFGNode and add all ActualParmSVFGNoe which may propagate pts to it as phi's operands.
Do the same thing for ActualRetSVFGNode and FormalRetSVFGNode.
Record def site of ActualINSVFGNode. Remove all its edges and connect its predecessors and successors.
Do the same thing for FormalOUTSVFGNode as 3.
Remove ActualINSVFGNode/FormalINSVFGNode/ActualOUTSVFGNode/FormalOUTSVFGNode if they will not be used when updating call graph.

reset def of address-taken variable

Definition at line 110 of file SVFGOPT.cpp.

{
    SVFGNodeSet candidates;
    for (SVFGNodeIDToNodeMapTy::iterator it = SVFG::begin(), eit = SVFG::end();
            it!=eit; ++it)
    {
        SVFGNode* node = it->second;
        if (SVFUtil::isa<ActualParmSVFGNode, ActualRetSVFGNode, FormalParmSVFGNode,
                FormalRetSVFGNode, ActualINSVFGNode, ActualOUTSVFGNode,
                FormalINSVFGNode, FormalOUTSVFGNode>(node))
            candidates.insert(node);
    }
 
    SVFGNodeSet nodesToBeDeleted;
    for (SVFGNodeSet::const_iterator it = candidates.begin(), eit = candidates.end();
            it!=eit; ++it)
    {
        SVFGNode* node = *it;
        if (FormalParmSVFGNode* fp = SVFUtil::dyn_cast<FormalParmSVFGNode>(node))
        {
            replaceFParamARetWithPHI(addInterPHIForFP(fp), fp);
            nodesToBeDeleted.insert(fp);
        }
        else if (ActualRetSVFGNode* ar = SVFUtil::dyn_cast<ActualRetSVFGNode>(node))
        {
            replaceFParamARetWithPHI(addInterPHIForAR(ar), ar);
            nodesToBeDeleted.insert(ar);
        }
        else if (SVFUtil::isa<ActualParmSVFGNode, FormalRetSVFGNode>(node))
        {
            nodesToBeDeleted.insert(node);
        }
        else if (SVFUtil::isa<ActualINSVFGNode, FormalOUTSVFGNode>(node))
        {
            retargetEdgesOfAInFOut(node);
            nodesToBeDeleted.insert(node);
        }
        else if (SVFUtil::isa<ActualOUTSVFGNode, FormalINSVFGNode>(node))
        {
            if(keepActualOutFormalIn == false)
                nodesToBeDeleted.insert(node);
        }
    }
 
    for (SVFGNodeSet::iterator it = nodesToBeDeleted.begin(), eit = nodesToBeDeleted.end(); it != eit; ++it)
    {
        SVFGNode* node = *it;
        if (canBeRemoved(node))
        {
            if (SVFUtil::isa<ActualOUTSVFGNode, FormalINSVFGNode>(node))
                retargetEdgesOfAOutFIn(node);   
 
            removeAllEdges(node);
            removeSVFGNode(node);
        }
    }
}

◆ handleIntraValueFlow()

void SVFGOPT::handleIntraValueFlow ( )

private

Remove MSSAPHI SVFG nodes.

Skip nodes which have self cycle

remove node's edges if it only has incoming or outgoing edges.

remove all the incoming edges;

remove all the outgoing edges;

remove this node if it has no edges

Definition at line 411 of file SVFGOPT.cpp.

{
    parseSelfCycleHandleOption();
 
    initialWorkList();
 
    while (!worklist.empty())
    {
        const MSSAPHISVFGNode* node = worklist.pop();
 
        if (checkSelfCycleEdges(node))
            continue;
 
        if (node->hasOutgoingEdge() && node->hasIncomingEdge())
            bypassMSSAPHINode(node);
 
        if (node->hasIncomingEdge() && node->hasOutgoingEdge() == false)
        {
            SVFGNode::const_iterator edgeIt = node->InEdgeBegin();
            SVFGNode::const_iterator edgeEit = node->InEdgeEnd();
            for (; edgeIt != edgeEit; ++edgeIt)
                addIntoWorklist((*edgeIt)->getSrcNode());
 
            removeInEdges(node);
        }
        else if (node->hasOutgoingEdge() && node->hasIncomingEdge() == false)
        {
            SVFGNode::const_iterator edgeIt = node->OutEdgeBegin();
            SVFGNode::const_iterator edgeEit = node->OutEdgeEnd();
            for (; edgeIt != edgeEit; ++edgeIt)
                addIntoWorklist((*edgeIt)->getDstNode());
 
            removeOutEdges(node);
        }
 
        if (node->hasIncomingEdge() == false && node->hasOutgoingEdge() == false)
            removeSVFGNode(const_cast<MSSAPHISVFGNode*>(node));
    }
}

◆ initialWorkList()

void SVF::SVFGOPT::initialWorkList ( )

inlineprivate

Initial work list with MSSAPHI nodes which may be removed.

Definition at line 211 of file SVFGOPT.h.

    {
        for (SVFG::const_iterator it = begin(), eit = end(); it != eit; ++it)
            addIntoWorklist(it->second);
    }

◆ isConnectingTwoCallSites()

bool SVFGOPT::isConnectingTwoCallSites ( const SVFGNode * node ) const

private

Return TRUE if this node has both incoming call/ret and outgoing call/ret edges.

Definition at line 312 of file SVFGOPT.cpp.

{
    bool hasInCallRet = false;
    bool hasOutCallRet = false;
 
    SVFGNode::const_iterator edgeIt = node->InEdgeBegin();
    SVFGNode::const_iterator edgeEit = node->InEdgeEnd();
    for (; edgeIt != edgeEit; ++edgeIt)
    {
        if (SVFUtil::isa<CallIndSVFGEdge, RetIndSVFGEdge>(*edgeIt))
        {
            hasInCallRet = true;
            break;
        }
    }
 
    edgeIt = node->OutEdgeBegin();
    edgeEit = node->OutEdgeEnd();
    for (; edgeIt != edgeEit; ++edgeIt)
    {
        if (SVFUtil::isa<CallIndSVFGEdge, RetIndSVFGEdge>(*edgeIt))
        {
            hasOutCallRet = true;
            break;
        }
    }
 
    if (hasInCallRet && hasOutCallRet)
        return true;
    else
        return false;
}

◆ isDefOfAInFOut()

bool SVF::SVFGOPT::isDefOfAInFOut ( const SVFGNode * node )

inlineprivate

Definition at line 295 of file SVFGOPT.h.

    {
        return defNodes.test(node->getId());
    }

◆ optimiseSVFG()

void SVFGOPT::optimiseSVFG ( )

protected

Separate optimisation function to avoid duplicate code.

Separate function to optimise the SVFG to avoid duplicate code.

Definition at line 68 of file SVFGOPT.cpp.

{
    if(Options::DumpVFG())
        dump("SVFG_before_opt");
 
    DBOUT(DGENERAL, outs() << SVFUtil::pasMsg("\tSVFG Optimisation\n"));
 
    keepActualOutFormalIn = Options::KeepAOFI();
 
    stat->sfvgOptStart();
    handleInterValueFlow();
 
    handleIntraValueFlow();
    stat->sfvgOptEnd();
 
}

◆ parseSelfCycleHandleOption()

void SVFGOPT::parseSelfCycleHandleOption ( )

private

Definition at line 392 of file SVFGOPT.cpp.

{
    std::string choice = (Options::SelfCycle().empty()) ? "" : Options::SelfCycle();
    if (choice.empty() || choice == KeepAllSelfCycle)
        keepAllSelfCycle = true;
    else if (choice == KeepContextSelfCycle)
        keepContextSelfCycle = true;
    else if (choice == KeepNoneSelfCycle)
        keepAllSelfCycle = keepContextSelfCycle = false;
    else
    {
        SVFUtil::writeWrnMsg("Unrecognised option. All self cycle edges will be kept.");
        keepAllSelfCycle = true;
    }
}

◆ readAndOptSVFG()

void SVFGOPT::readAndOptSVFG ( const std::string & filename )

Optimised SVFG's aren't written in their optimised form; read full SVFG and optimise it.

Optimised SVFGs aren't written to file; reads the full SVFG and optimises it.

Definition at line 47 of file SVFGOPT.cpp.

{
    SVFG::readFile(filename);
    optimiseSVFG();
}

◆ removeAllEdges()

void SVF::SVFGOPT::removeAllEdges ( const SVFGNode * node )

inlineprivate

Remove edges of a SVFG node.

Definition at line 340 of file SVFGOPT.h.

    {
        removeInEdges(node);
        removeOutEdges(node);
    }

◆ removeInEdges()

void SVF::SVFGOPT::removeInEdges ( const SVFGNode * node )

inlineprivate

remove incoming edges

Definition at line 345 of file SVFGOPT.h.

    {
        while (node->hasIncomingEdge())
            removeSVFGEdge(*(node->InEdgeBegin()));
    }

◆ removeOutEdges()

void SVF::SVFGOPT::removeOutEdges ( const SVFGNode * node )

inlineprivate

Definition at line 351 of file SVFGOPT.h.

    {
        while (node->hasOutgoingEdge())
            removeSVFGEdge(*(node->OutEdgeBegin()));
    }

◆ replaceFParamARetWithPHI()

void SVFGOPT::replaceFParamARetWithPHI	(	PHISVFGNode *	phi,
		SVFGNode *	svfgNode
	)

private

Replace FormalParam/ActualRet node with PHI node.

create a new PHISVFGNode.

migrate formal-param's edges to phi node.

add actual-param/formal-ret into phi's operand list

Definition at line 171 of file SVFGOPT.cpp.

{
    assert((SVFUtil::isa<FormalParmSVFGNode, ActualRetSVFGNode>(svfgNode))
           && "expecting a formal param or actual ret svfg node");
 
    NodeID phiId = phi->getId();
    for (SVFGNode::const_iterator it = svfgNode->OutEdgeBegin(), eit = svfgNode->OutEdgeEnd();
            it != eit; ++it)
    {
        const SVFGEdge* outEdge = *it;
        SVFGNode* dstNode = outEdge->getDstNode();
        NodeID dstId = dstNode->getId();
        if (const CallDirSVFGEdge* callEdge = SVFUtil::dyn_cast<CallDirSVFGEdge>(outEdge))
            addCallEdge(phiId, dstId, callEdge->getCallSiteId());
        else if (const RetDirSVFGEdge* retEdge = SVFUtil::dyn_cast<RetDirSVFGEdge>(outEdge))
            addRetEdge(phiId, dstId, retEdge->getCallSiteId());
        else
            addIntraDirectVFEdge(phiId, dstId);
    }
 
    if (FormalParmSVFGNode* fp = SVFUtil::dyn_cast<FormalParmSVFGNode>(svfgNode))
    {
        for (SVFGNode::iterator it = svfgNode->InEdgeBegin(), eit = svfgNode->InEdgeEnd();
                it != eit; ++it)
        {
            ActualParmSVFGNode* ap = SVFUtil::cast<ActualParmSVFGNode>((*it)->getSrcNode());
            addInterPHIOperands(phi, ap->getParam());
            // connect actual param's def node to phi node
            addCallEdge(getDef(ap->getParam()), phiId, getCallSiteID(ap->getCallSite(), fp->getFun()));
        }
    }
    else if (ActualRetSVFGNode* ar = SVFUtil::dyn_cast<ActualRetSVFGNode>(svfgNode))
    {
        for (SVFGNode::iterator it = svfgNode->InEdgeBegin(), eit = svfgNode->InEdgeEnd();
                it != eit; ++it)
        {
            FormalRetSVFGNode* fr = SVFUtil::cast<FormalRetSVFGNode>((*it)->getSrcNode());
            addInterPHIOperands(phi, fr->getRet());
            // connect formal return's def node to phi node
            addRetEdge(getDef(fr->getRet()), phiId, getCallSiteID(ar->getCallSite(), fr->getFun()));
        }
    }
 
    removeAllEdges(svfgNode);
}

◆ resetDef()

void SVF::SVFGOPT::resetDef	(	const PAGNode *	pagNode,
		const SVFGNode *	node
	)

inlineprivate

Definition at line 270 of file SVFGOPT.h.

    {
        PAGNodeToDefMapTy::iterator it = PAGNodeToDefMap.find(pagNode);
        assert(it != PAGNodeToDefMap.end() && "a SVFIR node doesn't have definition before");
        it->second = node->getId();
    }

◆ retargetEdgesOfAInFOut()

void SVFGOPT::retargetEdgesOfAInFOut ( SVFGNode * node )

private

Retarget edges related to actual-in/-out and formal-in/-out.

Record def sites of actual-in/formal-out and connect from those def-sites to formal-in/actual-out directly if they exist.

Definition at line 224 of file SVFGOPT.cpp.

{
    assert(node->getInEdges().size() == 1 && "actual-in/formal-out can only have one incoming edge as its def size");
 
    SVFGNode* def = nullptr;
    NodeBS inPointsTo;
 
    SVFGNode::const_iterator it = node->InEdgeBegin();
    SVFGNode::const_iterator eit = node->InEdgeEnd();
    for (; it != eit; ++it)
    {
        const IndirectSVFGEdge* inEdge = SVFUtil::cast<IndirectSVFGEdge>(*it);
        inPointsTo = inEdge->getPointsTo();
 
        def = inEdge->getSrcNode();
        if (SVFUtil::isa<ActualINSVFGNode>(node))
            setActualINDef(node->getId(), def->getId());
        else if (SVFUtil::isa<FormalOUTSVFGNode>(node))
            setFormalOUTDef(node->getId(), def->getId());
    }
 
    it = node->OutEdgeBegin(), eit = node->OutEdgeEnd();
    for (; it != eit; ++it)
    {
        const IndirectSVFGEdge* outEdge = SVFUtil::cast<IndirectSVFGEdge>(*it);
        NodeBS intersection = inPointsTo;
        intersection &= outEdge->getPointsTo();
 
        if (intersection.empty())
            continue;
 
        SVFGNode* dstNode = outEdge->getDstNode();
        if (const CallIndSVFGEdge* callEdge = SVFUtil::dyn_cast<CallIndSVFGEdge>(outEdge))
            addCallIndirectSVFGEdge(def->getId(), dstNode->getId(), callEdge->getCallSiteId(), intersection);
        else if (const RetIndSVFGEdge* retEdge = SVFUtil::dyn_cast<RetIndSVFGEdge>(outEdge))
            addRetIndirectSVFGEdge(def->getId(), dstNode->getId(), retEdge->getCallSiteId(), intersection);
        else
            assert(false && "expecting an inter-procedural SVFG edge");
    }
 
    removeAllEdges(node);
}

◆ retargetEdgesOfAOutFIn()

void SVFGOPT::retargetEdgesOfAOutFIn ( SVFGNode * node )

private

Connect actual-out/formal-in's predecessors to their successors directly.

Definition at line 270 of file SVFGOPT.cpp.

{
    SVFGNode::const_iterator inIt = node->InEdgeBegin();
    SVFGNode::const_iterator inEit = node->InEdgeEnd();
    for (; inIt != inEit; ++inIt)
    {
        const IndirectSVFGEdge* inEdge = SVFUtil::cast<IndirectSVFGEdge>(*inIt);
        NodeID srcId = inEdge->getSrcID();
 
        SVFGNode::const_iterator outIt = node->OutEdgeBegin();
        SVFGNode::const_iterator outEit = node->OutEdgeEnd();
        for (; outIt != outEit; ++outIt)
        {
            const IndirectSVFGEdge* outEdge = SVFUtil::cast<IndirectSVFGEdge>(*outIt);
 
            NodeBS intersection = inEdge->getPointsTo();
            intersection &= outEdge->getPointsTo();
            if (intersection.empty())
                continue;
 
            NodeID dstId = outEdge->getDstID();
            if (const RetIndSVFGEdge* retEdge = SVFUtil::dyn_cast<RetIndSVFGEdge>(inEdge))
            {
                addRetIndirectSVFGEdge(srcId, dstId, retEdge->getCallSiteId(), intersection);
            }
            else if (const CallIndSVFGEdge* callEdge = SVFUtil::dyn_cast<CallIndSVFGEdge>(inEdge))
            {
                addCallIndirectSVFGEdge(srcId, dstId, callEdge->getCallSiteId(), intersection);
            }
            else
            {
                addIntraIndirectVFEdge(srcId, dstId, intersection);
            }
        }
    }
 
    removeAllEdges(node);
}

◆ setActualINDef()

void SVF::SVFGOPT::setActualINDef	(	NodeID	ai,
		NodeID	def
	)

inlineprivate

Set def-site of actual-in/formal-out.

Definition at line 279 of file SVFGOPT.h.

    {
        bool inserted = actualInToDefMap.emplace(ai, def).second;
        (void)inserted; // Suppress warning of unused variable under release build
        assert(inserted && "can not set actual-in's def twice");
        defNodes.set(def);
    }

◆ setFormalOUTDef()

void SVF::SVFGOPT::setFormalOUTDef	(	NodeID	fo,
		NodeID	def
	)

inlineprivate

Definition at line 286 of file SVFGOPT.h.

    {
        bool inserted = formalOutToDefMap.emplace(fo, def).second;
        (void) inserted;
        assert(inserted && "can not set formal-out's def twice");
        defNodes.set(def);
    }

◆ setTokeepActualOutFormalIn()

void SVF::SVFGOPT::setTokeepActualOutFormalIn ( )

inline

Definition at line 71 of file SVFGOPT.h.

    {
        keepActualOutFormalIn = true;
    }

◆ setTokeepAllSelfCycle()

void SVF::SVFGOPT::setTokeepAllSelfCycle ( )

inline

Definition at line 75 of file SVFGOPT.h.

    {
        keepAllSelfCycle = true;
    }

◆ setTokeepContextSelfCycle()

void SVF::SVFGOPT::setTokeepContextSelfCycle ( )

inline

Definition at line 79 of file SVFGOPT.h.

    {
        keepContextSelfCycle = true;
    }

Member Data Documentation

◆ actualInToDefMap

NodeIDToNodeIDMap SVF::SVFGOPT::actualInToDefMap

private

map actual-in to its def-site node

Definition at line 359 of file SVFGOPT.h.

◆ defNodes

NodeBS SVF::SVFGOPT::defNodes

private

preserved def nodes of formal-in/actual-out

Definition at line 361 of file SVFGOPT.h.

◆ formalOutToDefMap

NodeIDToNodeIDMap SVF::SVFGOPT::formalOutToDefMap

private

map formal-out to its def-site node

Definition at line 360 of file SVFGOPT.h.

◆ keepActualOutFormalIn

bool SVF::SVFGOPT::keepActualOutFormalIn

private

Definition at line 365 of file SVFGOPT.h.

◆ keepAllSelfCycle

bool SVF::SVFGOPT::keepAllSelfCycle

private

Definition at line 366 of file SVFGOPT.h.

◆ keepContextSelfCycle

bool SVF::SVFGOPT::keepContextSelfCycle

private

Definition at line 367 of file SVFGOPT.h.

◆ worklist

WorkList SVF::SVFGOPT::worklist

private

storing MSSAPHI nodes which may be removed.

Definition at line 363 of file SVFGOPT.h.

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

/home/runner/work/SVF/SVF/svf/include/Graphs/SVFGOPT.h
/home/runner/work/SVF/SVF/svf/lib/Graphs/SVFGOPT.cpp

Public Member Functions

Protected Member Functions

Private Types

Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ NodeIDToNodeIDMap

◆ SVFGNodeSet

◆ WorkList

Constructor & Destructor Documentation

◆ SVFGOPT()

◆ ~SVFGOPT()

Member Function Documentation

◆ actualInOfIndCS()

◆ actualOutOfIndCS()

◆ addCallIndirectSVFGEdge()

◆ addInterPHIForAR()

◆ addInterPHIForFP()

◆ addInterPHIOperands()

◆ addIntoWorklist()

◆ addNewSVFGEdge()

◆ addRetIndirectSVFGEdge()

◆ bothInterEdges()

◆ buildAndWriteSVFG()

◆ buildSVFG()

◆ bypassMSSAPHINode()

◆ canBeRemoved()

◆ checkSelfCycleEdges()

◆ connectAInAndFIn()

◆ connectAParamAndFParam()

◆ connectFOutAndAOut()

◆ connectFRetAndARet()

◆ formalInOfAddressTakenFunc()

◆ formalOutOfAddressTakenFunc()

◆ getActualINDef()

◆ getFormalOUTDef()

◆ handleInterValueFlow()

◆ handleIntraValueFlow()

◆ initialWorkList()

◆ isConnectingTwoCallSites()

◆ isDefOfAInFOut()

◆ optimiseSVFG()

◆ parseSelfCycleHandleOption()

◆ readAndOptSVFG()

◆ removeAllEdges()

◆ removeInEdges()

◆ removeOutEdges()

◆ replaceFParamARetWithPHI()

◆ resetDef()

◆ retargetEdgesOfAInFOut()

◆ retargetEdgesOfAOutFIn()

◆ setActualINDef()

◆ setFormalOUTDef()

◆ setTokeepActualOutFormalIn()

◆ setTokeepAllSelfCycle()

◆ setTokeepContextSelfCycle()

Member Data Documentation

◆ actualInToDefMap

◆ defNodes

◆ formalOutToDefMap

◆ keepActualOutFormalIn

◆ keepAllSelfCycle

◆ keepContextSelfCycle

◆ worklist