#include <OfflineConsG.h>

Inheritance diagram for SVF::OfflineConsG:

Public Types
typedef SCCDetection< OfflineConsG * >	OSCC

typedef Set< LoadCGEdge * >	LoadEdges

typedef Set< StoreCGEdge * >	StoreEdges

Public Types inherited from SVF::ConstraintGraph
typedef Map< NodeID, ConstraintNode * >	ConstraintNodeIDToNodeMapTy

typedef ConstraintEdge::ConstraintEdgeSetTy::iterator	ConstraintNodeIter

typedef Map< NodeID, NodeID >	NodeToRepMap

typedef Map< NodeID, NodeBS >	NodeToSubsMap

typedef FIFOWorkList< NodeID >	WorkList

Public Types inherited from SVF::GenericGraph< ConstraintNode, ConstraintEdge >
typedef ConstraintNode	NodeType

typedef ConstraintEdge	EdgeType

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

typedef IDToNodeMapTy::iterator	iterator
	Node Iterators. More...

typedef IDToNodeMapTy::const_iterator	const_iterator

Public Member Functions
	OfflineConsG (PAG *p)

bool	hasOCGRep (NodeID node) const

NodeID	getOCGRep (NodeID node) const

const NodeToRepMap &	getOCGRepMap () const

bool	isaRef (NodeID node) const

bool	hasRef (NodeID node) const

NodeID	getRef (NodeID node) const

void	solveOfflineSCC (OSCC *oscc)

void	buildOfflineMap (OSCC *oscc)

void	dump (std::string name)

Public Member Functions inherited from SVF::ConstraintGraph
	ConstraintGraph (PAG *p)
	Constructor. More...

virtual	~ConstraintGraph ()
	Destructor. More...

bool	hasEdge (ConstraintNode src, ConstraintNode dst, ConstraintEdge::ConstraintEdgeK kind)

ConstraintEdge *	getEdge (ConstraintNode src, ConstraintNode dst, ConstraintEdge::ConstraintEdgeK kind)
	Get an edge via its src and dst nodes and kind. More...

bool	moveInEdgesToRepNode (ConstraintNode node, ConstraintNode rep)

bool	moveOutEdgesToRepNode (ConstraintNode node, ConstraintNode rep)

bool	moveEdgesToRepNode (ConstraintNode node, ConstraintNode rep)

bool	isZeroOffsettedGepCGEdge (ConstraintEdge *edge) const
	Check if a given edge is a NormalGepCGEdge with 0 offset. More...

void	dump (std::string name)
	Dump graph into dot file. More...

void	print ()
	Print CG into terminal. More...

void	view ()
	View graph from the debugger. More...

ConstraintNode *	getConstraintNode (NodeID id) const
	Get/add/remove constraint node. More...

void	addConstraintNode (ConstraintNode *node, NodeID id)

bool	hasConstraintNode (NodeID id) const

void	removeConstraintNode (ConstraintNode *node)

AddrCGEdge *	addAddrCGEdge (NodeID src, NodeID dst)
	Add a PAG edge into Edge map. More...

CopyCGEdge *	addCopyCGEdge (NodeID src, NodeID dst)
	Add Copy edge. More...

NormalGepCGEdge *	addNormalGepCGEdge (NodeID src, NodeID dst, const LocationSet &ls)
	Add Gep edge. More...

VariantGepCGEdge *	addVariantGepCGEdge (NodeID src, NodeID dst)

LoadCGEdge *	addLoadCGEdge (NodeID src, NodeID dst)
	Add Load edge. More...

StoreCGEdge *	addStoreCGEdge (NodeID src, NodeID dst)
	Add Store edge. More...

ConstraintEdge::ConstraintEdgeSetTy &	getAddrCGEdges ()
	Get PAG edge. More...

ConstraintEdge::ConstraintEdgeSetTy &	getDirectCGEdges ()
	Get Copy/call/ret/gep edges. More...

ConstraintEdge::ConstraintEdgeSetTy &	getLoadCGEdges ()
	Get Load edges. More...

ConstraintEdge::ConstraintEdgeSetTy &	getStoreCGEdges ()
	Get Store edges. More...

void	reTargetDstOfEdge (ConstraintEdge edge, ConstraintNode newDstNode)
	Used for cycle elimination. More...

void	reTargetSrcOfEdge (ConstraintEdge edge, ConstraintNode newSrcNode)
	Remove edge from old src target, change edge dst id and add modifed edge into new src. More...

void	removeAddrEdge (AddrCGEdge *edge)
	Remove addr edge from their src and dst edge sets. More...

void	removeDirectEdge (ConstraintEdge *edge)
	Remove direct edge from their src and dst edge sets. More...

void	removeLoadEdge (LoadCGEdge *edge)
	Remove load edge from their src and dst edge sets. More...

void	removeStoreEdge (StoreCGEdge *edge)
	Remove store edge from their src and dst edge sets. More...

NodeID	sccRepNode (NodeID id) const
	SCC rep/sub nodes methods. More...

NodeBS &	sccSubNodes (NodeID id)

void	setRep (NodeID node, NodeID rep)

void	setSubs (NodeID node, NodeBS &subs)

void	resetSubs (NodeID node)

NodeBS &	getSubs (NodeID node)

NodeID	getRep (NodeID node)

void	resetRep (NodeID node)

const PAG::CallSiteToFunPtrMap &	getIndirectCallsites () const
	Wrappers for invoking PAG methods. More...

NodeID	getBlackHoleNode ()

bool	isBlkObjOrConstantObj (NodeID id)

NodeBS &	getAllFieldsObjNode (NodeID id)

NodeID	getBaseObjNode (NodeID id)

bool	isSingleFieldObj (NodeID id) const

NodeID	getGepObjNode (NodeID id, const LocationSet &ls)
	Get a field of a memory object. More...

NodeID	getFIObjNode (NodeID id)
	Get a field-insensitive node of a memory object. More...

bool	isPWCNode (NodeID nodeId)
	Check/Set PWC (positive weight cycle) flag. More...

void	setPWCNode (NodeID nodeId)

bool	hasNodesToBeCollapsed () const
	Add/get nodes to be collapsed. More...

void	addNodeToBeCollapsed (NodeID id)

NodeID	getNextCollapseNode ()

Public Member Functions inherited from SVF::GenericGraph< ConstraintNode, ConstraintEdge >
	GenericGraph ()
	Constructor. More...

virtual	~GenericGraph ()
	Destructor. More...

void	destroy ()
	Release memory. More...

iterator	begin ()
	Iterators. More...

const_iterator	begin () const

iterator	end ()

const_iterator	end () const

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

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

bool	hasGNode (NodeID id) const
	Has a node. More...

void	removeGNode (NodeType *node)
	Delete a node. More...

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

u32_t	getTotalEdgeNum () const

void	incNodeNum ()
	Increase number of node/edge. More...

void	incEdgeNum ()

Protected Member Functions
bool	hasNorRep (NodeID nor) const

void	setNorRep (NodeID nor, NodeID rep)

NodeID	getNorRep (NodeID nor) const

NodeID	solveRep (OSCC *oscc, NodeID rep)

void	buildOfflineCG ()

bool	addRefLoadEdge (NodeID src, NodeID dst)

bool	addRefStoreEdge (NodeID src, NodeID dst)

bool	createRefNode (NodeID nodeId)

Protected Member Functions inherited from SVF::ConstraintGraph
void	buildCG ()

void	destroy ()

PAGEdge::PAGEdgeSetTy &	getPAGEdgeSet (PAGEdge::PEDGEK kind)

NodeID	getValueNode (const Value *value) const
	Wappers used internally, not expose to Andernsen Pass. More...

NodeID	getReturnNode (const SVFFunction *value) const

NodeID	getVarargNode (const SVFFunction *value) const

Protected Attributes
NodeSet	refNodes

NodeToRepMap	nodeToRefMap

NodeToRepMap	norToRepMap

Protected Attributes inherited from SVF::ConstraintGraph
PAG *	pag

NodeToRepMap	nodeToRepMap

NodeToSubsMap	nodeToSubsMap

WorkList	nodesToBeCollapsed

EdgeID	edgeIndex

ConstraintEdge::ConstraintEdgeSetTy	AddrCGEdgeSet

ConstraintEdge::ConstraintEdgeSetTy	directEdgeSet

ConstraintEdge::ConstraintEdgeSetTy	LoadCGEdgeSet

ConstraintEdge::ConstraintEdgeSetTy	StoreCGEdgeSet

Protected Attributes inherited from SVF::GenericGraph< ConstraintNode, ConstraintEdge >
IDToNodeMapTy	IDToNodeMap
	node map More...

Additional Inherited Members
Public Attributes inherited from SVF::GenericGraph< ConstraintNode, ConstraintEdge >
u32_t	edgeNum
	total num of node More...

u32_t	nodeNum
	total num of edge More...

Detailed Description

Offline constraint graph for Andersen's analysis. In OCG, a 'ref' node is used to represent the point-to set of a constraint node. 'Nor' means a constraint node of its corresponding ref node.

Definition at line 44 of file OfflineConsG.h.

Member Typedef Documentation

◆ LoadEdges

typedef Set<LoadCGEdge*> SVF::OfflineConsG::LoadEdges

Definition at line 49 of file OfflineConsG.h.

◆ OSCC

typedef SCCDetection<OfflineConsG*> SVF::OfflineConsG::OSCC

Definition at line 48 of file OfflineConsG.h.

◆ StoreEdges

typedef Set<StoreCGEdge*> SVF::OfflineConsG::StoreEdges

Definition at line 50 of file OfflineConsG.h.

Constructor & Destructor Documentation

◆ OfflineConsG()

SVF::OfflineConsG::OfflineConsG ( PAG * p )

inline

Definition at line 58 of file OfflineConsG.h.

                          : ConstraintGraph(p),
         nodeToRefMap( {}), norToRepMap({})
     {
         buildOfflineCG();
     }

Member Function Documentation

◆ addRefLoadEdge()

bool OfflineConsG::addRefLoadEdge	(	NodeID	src,
		NodeID	dst
	)

protected

Add a copy edge between the ref node of src node and dst node, while meeting a LOAD constraint.

Definition at line 86 of file OfflineConsG.cpp.

 {
     createRefNode(src);
     NodeID ref = nodeToRefMap[src];
     return addCopyCGEdge(ref, dst);
 }

◆ addRefStoreEdge()

bool OfflineConsG::addRefStoreEdge	(	NodeID	src,
		NodeID	dst
	)

protected

Add a copy edge between src node and the ref node of dst node, while meeting a STORE constraint.

Definition at line 97 of file OfflineConsG.cpp.

 {
     createRefNode(dst);
     NodeID ref = nodeToRefMap[dst];
     return addCopyCGEdge(src, ref);
 }

◆ buildOfflineCG()

void OfflineConsG::buildOfflineCG ( )

protected

Builder of offline constraint graph

Definition at line 39 of file OfflineConsG.cpp.

 {
     LoadEdges loads;
     StoreEdges stores;
 
     // Add a copy edge between the ref node of src node and dst node
     for (ConstraintEdge::ConstraintEdgeSetTy::iterator it = LoadCGEdgeSet.begin(), eit =
                 LoadCGEdgeSet.end(); it != eit; ++it)
     {
         LoadCGEdge *load = SVFUtil::dyn_cast<LoadCGEdge>(*it);
         loads.insert(load);
         NodeID src = load->getSrcID();
         NodeID dst = load->getDstID();
         addRefLoadEdge(src, dst);
     }
     // Add a copy edge between src node and the ref node of dst node
     for (ConstraintEdge::ConstraintEdgeSetTy::iterator it = StoreCGEdgeSet.begin(), eit =
                 StoreCGEdgeSet.end(); it != eit; ++it)
     {
         StoreCGEdge *store = SVFUtil::dyn_cast<StoreCGEdge>(*it);
         stores.insert(store);
         NodeID src = store->getSrcID();
         NodeID dst = store->getDstID();
         addRefStoreEdge(src, dst);
     }
 
     // Dump offline graph with all edges
     dump("oCG_initial");
 
     // Remove load and store edges in offline constraint graph
     for (LoadEdges::iterator it = loads.begin(), eit = loads.end(); it != eit; ++it)
     {
         removeLoadEdge(*it);
     }
     for (StoreEdges::iterator it = stores.begin(), eit = stores.end(); it != eit; ++it)
     {
         removeStoreEdge(*it);
     }
 
     // Dump offline graph with removed load and store edges
     dump("oCG_final");
 }

◆ buildOfflineMap()

void OfflineConsG::buildOfflineMap ( OSCC * oscc )

Build offline node to rep map, which only collect nodes having a ref node

Definition at line 133 of file OfflineConsG.cpp.

 {
     for (NodeToRepMap::const_iterator it = nodeToRefMap.begin(); it != nodeToRefMap.end(); ++it)
     {
         NodeID node = it->first;
         NodeID ref = getRef(node);
         NodeID rep = solveRep(oscc,oscc->repNode(ref));
         if (!isaRef(rep) && !isaRef(node))
             setNorRep(node, rep);
     }
 }

◆ createRefNode()

bool OfflineConsG::createRefNode ( NodeID nodeId )

protected

Create a ref node for a constraint node if it does not have one

Definition at line 107 of file OfflineConsG.cpp.

 {
     if (hasRef(nodeId))
         return false;
 
     NodeID refId = pag->addDummyValNode();
     ConstraintNode* node = new ConstraintNode(refId);
     addConstraintNode(node, refId);
     refNodes.insert(refId);
     nodeToRefMap[nodeId] = refId;
     return true;
 }

◆ dump()

void OfflineConsG::dump ( std::string name )

Dump offline constraint graph

Definition at line 169 of file OfflineConsG.cpp.

 {
     if (Options::OCGDotGraph)
         GraphPrinter::WriteGraphToFile(outs(), name, this);
 }

◆ getNorRep()

NodeID SVF::OfflineConsG::getNorRep ( NodeID nor ) const

inlineprotected

Definition at line 121 of file OfflineConsG.h.

     {
         NodeToRepMap::const_iterator it = norToRepMap.find(nor);
         assert(it != norToRepMap.end() && "No such rep node in nor to rep map!");
         return it->second;
     };

◆ getOCGRep()

NodeID SVF::OfflineConsG::getOCGRep ( NodeID node ) const

inline

Definition at line 70 of file OfflineConsG.h.

     {
         return getNorRep(node);
     }

◆ getOCGRepMap()

const NodeToRepMap& SVF::OfflineConsG::getOCGRepMap ( ) const

inline

Definition at line 75 of file OfflineConsG.h.

     {
         return norToRepMap;
     }

◆ getRef()

NodeID SVF::OfflineConsG::getRef ( NodeID node ) const

inline

Definition at line 93 of file OfflineConsG.h.

     {
         NodeToRepMap::const_iterator it = nodeToRefMap.find(node);
         assert(it != nodeToRefMap.end() && "No such ref node in ref to node map!");
         return it->second;
     }

◆ hasNorRep()

bool SVF::OfflineConsG::hasNorRep ( NodeID nor ) const

inlineprotected

Definition at line 110 of file OfflineConsG.h.

     {
         NodeToRepMap::const_iterator it = norToRepMap.find(nor);
         return it != norToRepMap.end();
     };

◆ hasOCGRep()

bool SVF::OfflineConsG::hasOCGRep ( NodeID node ) const

inline

Definition at line 65 of file OfflineConsG.h.

     {
         return hasNorRep(node);
     }

◆ hasRef()

bool SVF::OfflineConsG::hasRef ( NodeID node ) const

inline

Definition at line 87 of file OfflineConsG.h.

     {
         NodeToRepMap::const_iterator it = nodeToRefMap.find(node);
         return it != nodeToRefMap.end();
     };

◆ isaRef()

bool SVF::OfflineConsG::isaRef ( NodeID node ) const

inline

Definition at line 81 of file OfflineConsG.h.

     {
         NodeSet::const_iterator it = refNodes.find(node);
         return it != refNodes.end();
     };

◆ setNorRep()

void SVF::OfflineConsG::setNorRep	(	NodeID	nor,
		NodeID	rep
	)

inlineprotected

Definition at line 116 of file OfflineConsG.h.

     {
         norToRepMap.insert(std::pair<NodeID, NodeID>(nor, rep));
     };

◆ solveOfflineSCC()

void OfflineConsG::solveOfflineSCC ( OSCC * oscc )

Use a offline SCC detector to solve node relations in OCG. Generally, the 'oscc' should be solved first.

Definition at line 124 of file OfflineConsG.cpp.

 {
     // Build offline nodeToRepMap
     buildOfflineMap(oscc);
 }

◆ solveRep()

NodeID OfflineConsG::solveRep	(	OSCC *	oscc,
		NodeID	rep
	)

protected

The rep nodes of offline constraint graph are possible to be 'ref' nodes. These nodes should be replaced by one of its sub nodes which is not a ref node.

Definition at line 149 of file OfflineConsG.cpp.

 {
     if (isaRef(rep))
     {
         NodeBS subNodes = oscc->subNodes(rep);
         for (NodeBS::iterator subIt = subNodes.begin(), subEit = subNodes.end(); subIt != subEit; ++subIt)
         {
             if (isaRef(*subIt))
             {
                 rep = *subIt;
                 break;
             }
         }
     }
     return rep;
 }

Member Data Documentation

◆ nodeToRefMap

NodeToRepMap SVF::OfflineConsG::nodeToRefMap

protected

Definition at line 54 of file OfflineConsG.h.

◆ norToRepMap

NodeToRepMap SVF::OfflineConsG::norToRepMap

protected

Definition at line 55 of file OfflineConsG.h.

◆ refNodes

NodeSet SVF::OfflineConsG::refNodes

protected

Definition at line 53 of file OfflineConsG.h.

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

/home/runner/work/SVF-1/SVF-1/include/Graphs/OfflineConsG.h
/home/runner/work/SVF-1/SVF-1/lib/Graphs/OfflineConsG.cpp

Public Types

Public Member Functions

Protected Member Functions

Protected Attributes

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ LoadEdges

◆ OSCC

◆ StoreEdges

Constructor & Destructor Documentation

◆ OfflineConsG()

Member Function Documentation

◆ addRefLoadEdge()

◆ addRefStoreEdge()

◆ buildOfflineCG()

◆ buildOfflineMap()

◆ createRefNode()

◆ dump()

◆ getNorRep()

◆ getOCGRep()

◆ getOCGRepMap()

◆ getRef()

◆ hasNorRep()

◆ hasOCGRep()

◆ hasRef()

◆ isaRef()

◆ setNorRep()

◆ solveOfflineSCC()

◆ solveRep()

Member Data Documentation

◆ nodeToRefMap

◆ norToRepMap

◆ refNodes