SVF::ConstraintGraph Class Reference

#include <ConsG.h>

Inheritance diagram for SVF::ConstraintGraph:

Public Types
typedef OrderedMap< 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 OrderedMap< NodeID, NodeType * >	IDToNodeMapTy
	NodeID to GenericNode map.
typedef IDToNodeMapTy::iterator	iterator
	Node Iterators.
typedef IDToNodeMapTy::const_iterator	const_iterator

Public Member Functions
	ConstraintGraph (SVFIR *p)
	Constructor.
virtual	~ConstraintGraph ()
	Destructor.
ConstraintNode *	getConstraintNode (NodeID id) const
	Get/add/remove constraint node.
void	addConstraintNode (ConstraintNode *node, NodeID id)
bool	hasConstraintNode (NodeID id) const
void	removeConstraintNode (ConstraintNode *node)
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.
AddrCGEdge *	addAddrCGEdge (NodeID src, NodeID dst)
	Add a SVFIR edge into Edge map.
CopyCGEdge *	addCopyCGEdge (NodeID src, NodeID dst)
	Add Copy edge.
NormalGepCGEdge *	addNormalGepCGEdge (NodeID src, NodeID dst, const AccessPath &ap)
	Add Gep edge.
VariantGepCGEdge *	addVariantGepCGEdge (NodeID src, NodeID dst)
LoadCGEdge *	addLoadCGEdge (NodeID src, NodeID dst)
	Add Load edge.
StoreCGEdge *	addStoreCGEdge (NodeID src, NodeID dst)
	Add Store edge.
ConstraintEdge::ConstraintEdgeSetTy &	getAddrCGEdges ()
	Get SVFIR edge.
ConstraintEdge::ConstraintEdgeSetTy &	getDirectCGEdges ()
	Get Copy/call/ret/gep edges.
ConstraintEdge::ConstraintEdgeSetTy &	getLoadCGEdges ()
	Get Load edges.
ConstraintEdge::ConstraintEdgeSetTy &	getStoreCGEdges ()
	Get Store edges.
void	reTargetDstOfEdge (ConstraintEdge *edge, ConstraintNode *newDstNode)
	Used for cycle elimination.
void	reTargetSrcOfEdge (ConstraintEdge *edge, ConstraintNode *newSrcNode)
	Remove edge from old src target, change edge dst id and add modified edge into new src.
void	removeAddrEdge (AddrCGEdge *edge)
	Remove addr edge from their src and dst edge sets.
void	removeDirectEdge (ConstraintEdge *edge)
	Remove direct edge from their src and dst edge sets.
void	removeLoadEdge (LoadCGEdge *edge)
	Remove load edge from their src and dst edge sets.
void	removeStoreEdge (StoreCGEdge *edge)
	Remove store edge from their src and dst edge sets.
NodeID	sccRepNode (NodeID id) const
	SCC rep/sub nodes methods.
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)
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.
const SVFIR::CallSiteToFunPtrMap &	getIndirectCallsites () const
	Wrappers for invoking SVFIR methods.
NodeID	getBlackHoleNode ()
bool	isBlkObjOrConstantObj (NodeID id)
NodeBS &	getAllFieldsObjVars (NodeID id)
NodeID	getBaseObjVarID (NodeID id)
bool	isSingleFieldObj (NodeID id) const
NodeID	getGepObjVar (NodeID id, const APOffset &apOffset)
	Get a field of a memory object.
NodeID	getFIObjVar (NodeID id)
	Get a field-insensitive node of a memory object.
bool	isPWCNode (NodeID nodeId)
	Check/Set PWC (positive weight cycle) flag.
void	setPWCNode (NodeID nodeId)
bool	hasNodesToBeCollapsed () const
	Add/get nodes to be collapsed.
void	addNodeToBeCollapsed (NodeID id)
NodeID	getNextCollapseNode ()
void	dump (std::string name)
	Dump graph into dot file.
void	print ()
	Print CG into terminal.
void	view ()
	View graph from the debugger.
Public Member Functions inherited from SVF::GenericGraph< ConstraintNode, ConstraintEdge >
	GenericGraph ()
	Constructor.
virtual	~GenericGraph ()
	Destructor.
void	destroy ()
	Release memory.
iterator	begin ()
	Iterators.
iterator	end ()
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	buildCG ()
void	destroy ()
void	clearSolitaries ()
SVFStmt::SVFStmtSetTy &	getSVFStmtSet (SVFStmt::PEDGEK kind)
NodeID	getReturnNode (const FunObjVar *value) const
	Wrappers used internally, not expose to Andersen Pass.
NodeID	getVarargNode (const FunObjVar *value) const

Protected Attributes
SVFIR *	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

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

Detailed Description

Constraint graph for Andersen's analysis ConstraintNodes are same as PAGNodes ConstraintEdges are self-defined edges (initialized with ConstraintEdges)

Definition at line 44 of file ConsG.h.

Member Typedef Documentation

ConstraintNodeIDToNodeMapTy

typedef OrderedMap<NodeID, ConstraintNode *> SVF::ConstraintGraph::ConstraintNodeIDToNodeMapTy

Definition at line 48 of file ConsG.h.

ConstraintNodeIter

typedef ConstraintEdge::ConstraintEdgeSetTy::iterator SVF::ConstraintGraph::ConstraintNodeIter

Definition at line 49 of file ConsG.h.

NodeToRepMap

typedef Map<NodeID, NodeID> SVF::ConstraintGraph::NodeToRepMap

Definition at line 50 of file ConsG.h.

NodeToSubsMap

typedef Map<NodeID, NodeBS> SVF::ConstraintGraph::NodeToSubsMap

Definition at line 51 of file ConsG.h.

WorkList

typedef FIFOWorkList<NodeID> SVF::ConstraintGraph::WorkList

Definition at line 52 of file ConsG.h.

Constructor & Destructor Documentation

ConstraintGraph()

SVF::ConstraintGraph::ConstraintGraph ( SVFIR * p )

inline

Constructor.

Definition at line 92 of file ConsG.h.

                             : pag(p), edgeIndex(0)
    {
        buildCG();
    }

~ConstraintGraph()

virtual SVF::ConstraintGraph::~ConstraintGraph ( )

inlinevirtual

Destructor.

Definition at line 97 of file ConsG.h.

    {
        destroy();
    }

Member Function Documentation

addAddrCGEdge()

AddrCGEdge * ConstraintGraph::addAddrCGEdge	(	NodeID	src,
		NodeID	dst )

Add a SVFIR edge into Edge map.

Add Address edge

Add an address edge

Definition at line 206 of file ConsG.cpp.

{
    ConstraintNode* srcNode = getConstraintNode(src);
    ConstraintNode* dstNode = getConstraintNode(dst);
    if (hasEdge(srcNode, dstNode, ConstraintEdge::Addr))
        return nullptr;
    AddrCGEdge* edge = new AddrCGEdge(srcNode, dstNode, edgeIndex++);
 
    bool inserted = AddrCGEdgeSet.insert(edge).second;
    (void)inserted; // Suppress warning of unused variable under release build
    assert(inserted && "new AddrCGEdge not added??");
 
    srcNode->addOutgoingAddrEdge(edge);
    dstNode->addIncomingAddrEdge(edge);
    return edge;
}

addConstraintNode()

void SVF::ConstraintGraph::addConstraintNode ( ConstraintNode * node, NodeID id )

inline

Definition at line 109 of file ConsG.h.

    {
        addGNode(id,node);
    }

addCopyCGEdge()

CopyCGEdge * ConstraintGraph::addCopyCGEdge	(	NodeID	src,
		NodeID	dst )

Add Copy edge.

Add Copy edge

Definition at line 226 of file ConsG.cpp.

{
 
    ConstraintNode* srcNode = getConstraintNode(src);
    ConstraintNode* dstNode = getConstraintNode(dst);
    if (hasEdge(srcNode, dstNode, ConstraintEdge::Copy) || srcNode == dstNode)
        return nullptr;
 
    CopyCGEdge* edge = new CopyCGEdge(srcNode, dstNode, edgeIndex++);
 
    bool inserted = directEdgeSet.insert(edge).second;
    (void)inserted; // Suppress warning of unused variable under release build
    assert(inserted && "new CopyCGEdge not added??");
 
    srcNode->addOutgoingCopyEdge(edge);
    dstNode->addIncomingCopyEdge(edge);
    return edge;
}

addLoadCGEdge()

LoadCGEdge * ConstraintGraph::addLoadCGEdge	(	NodeID	src,
		NodeID	dst )

Add Load edge.

Add Load edge

Definition at line 292 of file ConsG.cpp.

{
    ConstraintNode* srcNode = getConstraintNode(src);
    ConstraintNode* dstNode = getConstraintNode(dst);
    if (hasEdge(srcNode, dstNode, ConstraintEdge::Load))
        return nullptr;
 
    LoadCGEdge* edge = new LoadCGEdge(srcNode, dstNode, edgeIndex++);
 
    bool inserted = LoadCGEdgeSet.insert(edge).second;
    (void)inserted; // Suppress warning of unused variable under release build
    assert(inserted && "new LoadCGEdge not added??");
 
    srcNode->addOutgoingLoadEdge(edge);
    dstNode->addIncomingLoadEdge(edge);
    return edge;
}

addNodeToBeCollapsed()

void SVF::ConstraintGraph::addNodeToBeCollapsed ( NodeID id )

inline

Definition at line 361 of file ConsG.h.

    {
        nodesToBeCollapsed.push(id);
    }

addNormalGepCGEdge()

NormalGepCGEdge * ConstraintGraph::addNormalGepCGEdge	(	NodeID	src,
		NodeID	dst,
		const AccessPath &	ap )

Add Gep edge.

Add Gep edge

Definition at line 249 of file ConsG.cpp.

{
    ConstraintNode* srcNode = getConstraintNode(src);
    ConstraintNode* dstNode = getConstraintNode(dst);
    if (hasEdge(srcNode, dstNode, ConstraintEdge::NormalGep))
        return nullptr;
 
    NormalGepCGEdge* edge =
        new NormalGepCGEdge(srcNode, dstNode, ap, edgeIndex++);
 
    bool inserted = directEdgeSet.insert(edge).second;
    (void)inserted; // Suppress warning of unused variable under release build
    assert(inserted && "new NormalGepCGEdge not added??");
 
    srcNode->addOutgoingGepEdge(edge);
    dstNode->addIncomingGepEdge(edge);
    return edge;
}

addStoreCGEdge()

StoreCGEdge * ConstraintGraph::addStoreCGEdge	(	NodeID	src,
		NodeID	dst )

Add Store edge.

Add Store edge

Definition at line 313 of file ConsG.cpp.

{
    ConstraintNode* srcNode = getConstraintNode(src);
    ConstraintNode* dstNode = getConstraintNode(dst);
    if (hasEdge(srcNode, dstNode, ConstraintEdge::Store))
        return nullptr;
 
    StoreCGEdge* edge = new StoreCGEdge(srcNode, dstNode, edgeIndex++);
 
    bool inserted = StoreCGEdgeSet.insert(edge).second;
    (void)inserted; // Suppress warning of unused variable under release build
    assert(inserted && "new StoreCGEdge not added??");
 
    srcNode->addOutgoingStoreEdge(edge);
    dstNode->addIncomingStoreEdge(edge);
    return edge;
}

addVariantGepCGEdge()

VariantGepCGEdge * ConstraintGraph::addVariantGepCGEdge	(	NodeID	src,
		NodeID	dst )

Add variant gep edge

Definition at line 271 of file ConsG.cpp.

{
    ConstraintNode* srcNode = getConstraintNode(src);
    ConstraintNode* dstNode = getConstraintNode(dst);
    if (hasEdge(srcNode, dstNode, ConstraintEdge::VariantGep))
        return nullptr;
 
    VariantGepCGEdge* edge = new VariantGepCGEdge(srcNode, dstNode, edgeIndex++);
 
    bool inserted = directEdgeSet.insert(edge).second;
    (void)inserted; // Suppress warning of unused variable under release build
    assert(inserted && "new VariantGepCGEdge not added??");
 
    srcNode->addOutgoingGepEdge(edge);
    dstNode->addIncomingGepEdge(edge);
    return edge;
}

buildCG()

void ConstraintGraph::buildCG ( )

protected

Start building constraint graph

Definition at line 42 of file ConsG.cpp.

{
 
    // initialize nodes
    for(SVFIR::iterator it = pag->begin(), eit = pag->end(); it!=eit; ++it)
    {
        addConstraintNode(new ConstraintNode(it->first), it->first);
    }
 
    // initialize edges
    SVFStmt::SVFStmtSetTy& addrs = getSVFStmtSet(SVFStmt::Addr);
    for (SVFStmt::SVFStmtSetTy::iterator iter = addrs.begin(), eiter =
                addrs.end(); iter != eiter; ++iter)
    {
        const AddrStmt* edge = SVFUtil::cast<AddrStmt>(*iter);
        addAddrCGEdge(edge->getRHSVarID(),edge->getLHSVarID());
    }
 
    SVFStmt::SVFStmtSetTy& copys = getSVFStmtSet(SVFStmt::Copy);
    for (SVFStmt::SVFStmtSetTy::iterator iter = copys.begin(), eiter =
                copys.end(); iter != eiter; ++iter)
    {
        const CopyStmt* edge = SVFUtil::cast<CopyStmt>(*iter);
        if(edge->isBitCast() || edge->isValueCopy())
            addCopyCGEdge(edge->getRHSVarID(),edge->getLHSVarID());
    }
 
    SVFStmt::SVFStmtSetTy& phis = getSVFStmtSet(SVFStmt::Phi);
    for (SVFStmt::SVFStmtSetTy::iterator iter = phis.begin(), eiter =
                phis.end(); iter != eiter; ++iter)
    {
        const PhiStmt* edge = SVFUtil::cast<PhiStmt>(*iter);
        for(const auto opVar : edge->getOpndVars())
            addCopyCGEdge(opVar->getId(),edge->getResID());
    }
 
    SVFStmt::SVFStmtSetTy& selects = getSVFStmtSet(SVFStmt::Select);
    for (SVFStmt::SVFStmtSetTy::iterator iter = selects.begin(), eiter =
                selects.end(); iter != eiter; ++iter)
    {
        const SelectStmt* edge = SVFUtil::cast<SelectStmt>(*iter);
        for(const auto opVar : edge->getOpndVars())
            addCopyCGEdge(opVar->getId(),edge->getResID());
    }
 
    SVFStmt::SVFStmtSetTy& calls = getSVFStmtSet(SVFStmt::Call);
    for (SVFStmt::SVFStmtSetTy::iterator iter = calls.begin(), eiter =
                calls.end(); iter != eiter; ++iter)
    {
        const CallPE* callPE = SVFUtil::cast<CallPE>(*iter);
        for(u32_t i = 0; i < callPE->getOpVarNum(); i++)
            addCopyCGEdge(callPE->getOpVarID(i), callPE->getResID());
    }
 
    SVFStmt::SVFStmtSetTy& rets = getSVFStmtSet(SVFStmt::Ret);
    for (SVFStmt::SVFStmtSetTy::iterator iter = rets.begin(), eiter =
                rets.end(); iter != eiter; ++iter)
    {
        const RetPE* edge = SVFUtil::cast<RetPE>(*iter);
        addCopyCGEdge(edge->getRHSVarID(),edge->getLHSVarID());
    }
 
    SVFStmt::SVFStmtSetTy& tdfks = getSVFStmtSet(SVFStmt::ThreadFork);
    for (SVFStmt::SVFStmtSetTy::iterator iter = tdfks.begin(), eiter =
                tdfks.end(); iter != eiter; ++iter)
    {
        const TDForkPE* forkPE = SVFUtil::cast<TDForkPE>(*iter);
        for(u32_t i = 0; i < forkPE->getOpVarNum(); i++)
            addCopyCGEdge(forkPE->getOpVarID(i), forkPE->getResID());
    }
 
    SVFStmt::SVFStmtSetTy& tdjns = getSVFStmtSet(SVFStmt::ThreadJoin);
    for (SVFStmt::SVFStmtSetTy::iterator iter = tdjns.begin(), eiter =
                tdjns.end(); iter != eiter; ++iter)
    {
        const TDJoinPE* edge = SVFUtil::cast<TDJoinPE>(*iter);
        addCopyCGEdge(edge->getRHSVarID(),edge->getLHSVarID());
    }
 
    SVFStmt::SVFStmtSetTy& ngeps = getSVFStmtSet(SVFStmt::Gep);
    for (SVFStmt::SVFStmtSetTy::iterator iter = ngeps.begin(), eiter =
                ngeps.end(); iter != eiter; ++iter)
    {
        GepStmt* edge = SVFUtil::cast<GepStmt>(*iter);
        if(edge->isVariantFieldGep())
            addVariantGepCGEdge(edge->getRHSVarID(),edge->getLHSVarID());
        else
            addNormalGepCGEdge(edge->getRHSVarID(),edge->getLHSVarID(),edge->getAccessPath());
    }
 
    SVFStmt::SVFStmtSetTy& loads = getSVFStmtSet(SVFStmt::Load);
    for (SVFStmt::SVFStmtSetTy::iterator iter = loads.begin(), eiter =
                loads.end(); iter != eiter; ++iter)
    {
        LoadStmt* edge = SVFUtil::cast<LoadStmt>(*iter);
        addLoadCGEdge(edge->getRHSVarID(),edge->getLHSVarID());
    }
 
    SVFStmt::SVFStmtSetTy& stores = getSVFStmtSet(SVFStmt::Store);
    for (SVFStmt::SVFStmtSetTy::iterator iter = stores.begin(), eiter =
                stores.end(); iter != eiter; ++iter)
    {
        StoreStmt* edge = SVFUtil::cast<StoreStmt>(*iter);
        addStoreCGEdge(edge->getRHSVarID(),edge->getLHSVarID());
    }
 
    clearSolitaries();
}

clearSolitaries()

void ConstraintGraph::clearSolitaries ( )

protected

Remove nodes that are neither pointers nor connected with any edge

We don't remove return SVFVar from an indirect callsite

Definition at line 154 of file ConsG.cpp.

{
    NodeSet retFromIndCalls;
    for(auto cs_pair : pag->getIndirectCallsites())
    {
        const RetICFGNode* retBlockNode = cs_pair.first->getRetICFGNode();
        if(pag->callsiteHasRet(retBlockNode))
            retFromIndCalls.insert(pag->getCallSiteRet(retBlockNode)->getId());
    }
 
    Set<ConstraintNode*> nodesToRemove;
    for (auto it = this->begin(); it != this->end(); ++it)
    {
        if (it->second->hasIncomingEdge() || it->second->hasOutgoingEdge())
            continue;
        if (pag->getSVFVar(it->first)->isPointer())
            continue;
        if (retFromIndCalls.find(it->first)!=retFromIndCalls.end())
            continue;
        nodesToRemove.insert(it->second);
    }
 
    for (auto node : nodesToRemove)
        removeConstraintNode(node);
}

destroy()

void ConstraintGraph::destroy ( )

protected

Memory has been cleaned up at GenericGraph

Definition at line 184 of file ConsG.cpp.

{
}

dump()

void ConstraintGraph::dump

(

std::string

name

)

Dump graph into dot file.

Dump constraint graph

Definition at line 595 of file ConsG.cpp.

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

getAddrCGEdges()

ConstraintEdge::ConstraintEdgeSetTy & SVF::ConstraintGraph::getAddrCGEdges ( )

inline

Get SVFIR edge.

Get Address edges

Definition at line 191 of file ConsG.h.

    {
        return AddrCGEdgeSet;
    }

getAllFieldsObjVars()

NodeBS & SVF::ConstraintGraph::getAllFieldsObjVars ( NodeID id )

inline

Definition at line 311 of file ConsG.h.

    {
        return pag->getAllFieldsObjVars(id);
    }

getBaseObjVarID()

NodeID SVF::ConstraintGraph::getBaseObjVarID ( NodeID id )

inline

Definition at line 315 of file ConsG.h.

    {
        return pag->getBaseObjVarID(id);
    }

getBlackHoleNode()

NodeID SVF::ConstraintGraph::getBlackHoleNode ( )

inline

Definition at line 303 of file ConsG.h.

    {
        return pag->getBlackHoleNode();
    }

getConstraintNode()

ConstraintNode * SVF::ConstraintGraph::getConstraintNode ( NodeID id ) const

inline

Get/add/remove constraint node.

Definition at line 104 of file ConsG.h.

    {
        id = sccRepNode(id);
        return getGNode(id);
    }

getDirectCGEdges()

ConstraintEdge::ConstraintEdgeSetTy & SVF::ConstraintGraph::getDirectCGEdges ( )

inline

Get Copy/call/ret/gep edges.

Definition at line 196 of file ConsG.h.

    {
        return directEdgeSet;
    }

getEdge()

ConstraintEdge * SVF::ConstraintGraph::getEdge ( ConstraintNode * src, ConstraintNode * dst, ConstraintEdge::ConstraintEdgeK kind )

inline

Get an edge via its src and dst nodes and kind.

Definition at line 143 of file ConsG.h.

    {
        ConstraintEdge edge(src,dst,kind);
        if(kind == ConstraintEdge::Copy || kind == ConstraintEdge::NormalGep || kind == ConstraintEdge::VariantGep)
        {
            auto eit = directEdgeSet.find(&edge);
            return *eit;
        }
        else if(kind == ConstraintEdge::Addr)
        {
            auto eit = AddrCGEdgeSet.find(&edge);
            return *eit;
        }
        else if(kind == ConstraintEdge::Store)
        {
            auto eit = StoreCGEdgeSet.find(&edge);
            return *eit;
        }
        else if(kind == ConstraintEdge::Load)
        {
            auto eit = LoadCGEdgeSet.find(&edge);
            return *eit;
        }
        else
        {
            assert(false && "no other kind!");
            return nullptr;
        }
    }

getFIObjVar()

NodeID SVF::ConstraintGraph::getFIObjVar ( NodeID id )

inline

Get a field-insensitive node of a memory object.

The fi obj in PAG must be either an existing node or merged to another rep node in ConsG

Definition at line 334 of file ConsG.h.

    {
        NodeID fi = pag->getFIObjVar(id);
        assert((hasConstraintNode(fi) || sccRepNode(fi) != fi) && "non-existing fi obj??");
        return fi;
    }

getGepObjVar()

NodeID SVF::ConstraintGraph::getGepObjVar ( NodeID id, const APOffset & apOffset )

inline

Get a field of a memory object.

Create a node when it is (1) not exist on graph and (2) not merged

Definition at line 325 of file ConsG.h.

    {
        NodeID gep =  pag->getGepObjVar(id, apOffset);
        if(sccRepNode(gep)==gep && hasConstraintNode(gep)==false)
            addConstraintNode(new ConstraintNode(gep),gep);
        return gep;
    }

getIndirectCallsites()

const SVFIR::CallSiteToFunPtrMap & SVF::ConstraintGraph::getIndirectCallsites ( ) const

inline

Wrappers for invoking SVFIR methods.

Definition at line 299 of file ConsG.h.

    {
        return pag->getIndirectCallsites();
    }

getLoadCGEdges()

ConstraintEdge::ConstraintEdgeSetTy & SVF::ConstraintGraph::getLoadCGEdges ( )

inline

Get Load edges.

Definition at line 201 of file ConsG.h.

    {
        return LoadCGEdgeSet;
    }

getNextCollapseNode()

NodeID SVF::ConstraintGraph::getNextCollapseNode ( )

inline

Definition at line 365 of file ConsG.h.

    {
        return nodesToBeCollapsed.pop();
    }

getRep()

NodeID SVF::ConstraintGraph::getRep ( NodeID node )

inline

Definition at line 259 of file ConsG.h.

    {
        return nodeToRepMap[node];
    }

getReturnNode()

NodeID SVF::ConstraintGraph::getReturnNode ( const FunObjVar * value ) const

inlineprotected

Wrappers used internally, not expose to Andersen Pass.

Definition at line 79 of file ConsG.h.

    {
        return pag->getReturnNode(value);
    }

getStoreCGEdges()

ConstraintEdge::ConstraintEdgeSetTy & SVF::ConstraintGraph::getStoreCGEdges ( )

inline

Get Store edges.

Definition at line 206 of file ConsG.h.

    {
        return StoreCGEdgeSet;
    }

getSubs()

NodeBS & SVF::ConstraintGraph::getSubs ( NodeID node )

inline

Definition at line 255 of file ConsG.h.

    {
        return nodeToSubsMap[node];
    }

getSVFStmtSet()

SVFStmt::SVFStmtSetTy & SVF::ConstraintGraph::getSVFStmtSet ( SVFStmt::PEDGEK kind )

inlineprotected

Definition at line 72 of file ConsG.h.

    {
        return pag->getPTASVFStmtSet(kind);
    }

getVarargNode()

NodeID SVF::ConstraintGraph::getVarargNode ( const FunObjVar * value ) const

inlineprotected

Definition at line 84 of file ConsG.h.

    {
        return pag->getVarargNode(value);
    }

hasConstraintNode()

bool SVF::ConstraintGraph::hasConstraintNode ( NodeID id ) const

inline

Definition at line 113 of file ConsG.h.

    {
        id = sccRepNode(id);
        return hasGNode(id);
    }

hasEdge()

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

inline

Definition at line 125 of file ConsG.h.

    {
        ConstraintEdge edge(src,dst,kind);
        if(kind == ConstraintEdge::Copy ||
                kind == ConstraintEdge::NormalGep || kind == ConstraintEdge::VariantGep)
            return directEdgeSet.find(&edge) != directEdgeSet.end();
        else if(kind == ConstraintEdge::Addr)
            return AddrCGEdgeSet.find(&edge) != AddrCGEdgeSet.end();
        else if(kind == ConstraintEdge::Store)
            return StoreCGEdgeSet.find(&edge) != StoreCGEdgeSet.end();
        else if(kind == ConstraintEdge::Load)
            return LoadCGEdgeSet.find(&edge) != LoadCGEdgeSet.end();
        else
            assert(false && "no other kind!");
        return false;
    }

hasNodesToBeCollapsed()

bool SVF::ConstraintGraph::hasNodesToBeCollapsed ( ) const

inline

Add/get nodes to be collapsed.

Definition at line 357 of file ConsG.h.

    {
        return (!nodesToBeCollapsed.empty());
    }

isBlkObjOrConstantObj()

bool SVF::ConstraintGraph::isBlkObjOrConstantObj ( NodeID id )

inline

Definition at line 307 of file ConsG.h.

    {
        return pag->isBlkObjOrConstantObj(id);
    }

isPWCNode()

bool SVF::ConstraintGraph::isPWCNode ( NodeID nodeId )

inline

Check/Set PWC (positive weight cycle) flag.

Definition at line 345 of file ConsG.h.

    {
        return getConstraintNode(nodeId)->isPWCNode();
    }

isSingleFieldObj()

bool SVF::ConstraintGraph::isSingleFieldObj ( NodeID id ) const

inline

Definition at line 319 of file ConsG.h.

    {
        const BaseObjVar* baseObj = pag->getBaseObject(id);
        return (baseObj->getMaxFieldOffsetLimit() == 1);
    }

isZeroOffsettedGepCGEdge()

bool SVF::ConstraintGraph::isZeroOffsettedGepCGEdge ( ConstraintEdge * edge ) const

inline

Check if a given edge is a NormalGepCGEdge with 0 offset.

Definition at line 289 of file ConsG.h.

    {
        if (NormalGepCGEdge *normalGepCGEdge = SVFUtil::dyn_cast<NormalGepCGEdge>(edge))
            if (0 == normalGepCGEdge->getConstantFieldIdx())
                return true;
        return false;
    }

moveEdgesToRepNode()

bool SVF::ConstraintGraph::moveEdgesToRepNode ( ConstraintNode * node, ConstraintNode * rep )

inline

Move incoming/outgoing direct edges of a sub node to its rep node Return TRUE if there's a gep edge inside this SCC (PWC).

Definition at line 281 of file ConsG.h.

    {
        bool gepIn = moveInEdgesToRepNode(node, rep);
        bool gepOut = moveOutEdgesToRepNode(node, rep);
        return (gepIn || gepOut);
    }

moveInEdgesToRepNode()

bool ConstraintGraph::moveInEdgesToRepNode	(	ConstraintNode *	node,
		ConstraintNode *	rep )

Move incoming direct edges of a sub node which is outside the SCC to its rep node Remove incoming direct edges of a sub node which is inside the SCC from its rep node Return TRUE if there's a gep edge inside this SCC (PWC).

Move incoming direct edges of a sub node which is outside SCC to its rep node Remove incoming direct edges of a sub node which is inside SCC from its rep node

only copy and gep edge can be removed

Definition at line 478 of file ConsG.cpp.

{
    std::vector<ConstraintEdge*> sccEdges;
    std::vector<ConstraintEdge*> nonSccEdges;
    for (ConstraintNode::const_iterator it = node->InEdgeBegin(), eit = node->InEdgeEnd(); it != eit;
            ++it)
    {
        ConstraintEdge* subInEdge = *it;
        if(sccRepNode(subInEdge->getSrcID()) != rep->getId())
            nonSccEdges.push_back(subInEdge);
        else
        {
            sccEdges.push_back(subInEdge);
        }
    }
    // if this edge is outside scc, then re-target edge dst to rep
    while(!nonSccEdges.empty())
    {
        ConstraintEdge* edge = nonSccEdges.back();
        nonSccEdges.pop_back();
        reTargetDstOfEdge(edge,rep);
    }
 
    bool criticalGepInsideSCC = false;
    // if this edge is inside scc, then remove this edge and two end nodes
    while(!sccEdges.empty())
    {
        ConstraintEdge* edge = sccEdges.back();
        sccEdges.pop_back();
        if(SVFUtil::isa<CopyCGEdge>(edge))
            removeDirectEdge(edge);
        else if (SVFUtil::isa<GepCGEdge>(edge))
        {
            // If the GEP is critical (i.e. may have a non-zero offset),
            // then it brings impact on field-sensitivity.
            if (!isZeroOffsettedGepCGEdge(edge))
            {
                criticalGepInsideSCC = true;
            }
            removeDirectEdge(edge);
        }
        else if(SVFUtil::isa<LoadCGEdge, StoreCGEdge>(edge))
            reTargetDstOfEdge(edge,rep);
        else if(AddrCGEdge* addr = SVFUtil::dyn_cast<AddrCGEdge>(edge))
        {
            removeAddrEdge(addr);
        }
        else
            assert(false && "no such edge");
    }
    return criticalGepInsideSCC;
}

moveOutEdgesToRepNode()

bool ConstraintGraph::moveOutEdgesToRepNode	(	ConstraintNode *	node,
		ConstraintNode *	rep )

Move outgoing direct edges of a sub node which is outside the SCC to its rep node Remove outgoing direct edges of sub node which is inside the SCC from its rep node Return TRUE if there's a gep edge inside this SCC (PWC).

Move outgoing direct edges of a sub node which is outside SCC to its rep node Remove outgoing direct edges of a sub node which is inside SCC from its rep node

only copy and gep edge can be removed

Definition at line 536 of file ConsG.cpp.

{
 
    std::vector<ConstraintEdge*> sccEdges;
    std::vector<ConstraintEdge*> nonSccEdges;
 
    for (ConstraintNode::const_iterator it = node->OutEdgeBegin(), eit = node->OutEdgeEnd(); it != eit;
            ++it)
    {
        ConstraintEdge* subOutEdge = *it;
        if(sccRepNode(subOutEdge->getDstID()) != rep->getId())
            nonSccEdges.push_back(subOutEdge);
        else
        {
            sccEdges.push_back(subOutEdge);
        }
    }
    // if this edge is outside scc, then re-target edge src to rep
    while(!nonSccEdges.empty())
    {
        ConstraintEdge* edge = nonSccEdges.back();
        nonSccEdges.pop_back();
        reTargetSrcOfEdge(edge,rep);
    }
    bool criticalGepInsideSCC = false;
    // if this edge is inside scc, then remove this edge and two end nodes
    while(!sccEdges.empty())
    {
        ConstraintEdge* edge = sccEdges.back();
        sccEdges.pop_back();
        if(SVFUtil::isa<CopyCGEdge>(edge))
            removeDirectEdge(edge);
        else if (SVFUtil::isa<GepCGEdge>(edge))
        {
            // If the GEP is critical (i.e. may have a non-zero offset),
            // then it brings impact on field-sensitivity.
            if (!isZeroOffsettedGepCGEdge(edge))
            {
                criticalGepInsideSCC = true;
            }
            removeDirectEdge(edge);
        }
        else if(SVFUtil::isa<LoadCGEdge, StoreCGEdge>(edge))
            reTargetSrcOfEdge(edge,rep);
        else if(AddrCGEdge* addr = SVFUtil::dyn_cast<AddrCGEdge>(edge))
        {
            removeAddrEdge(addr);
        }
        else
            assert(false && "no such edge");
    }
    return criticalGepInsideSCC;
}

print()

void ConstraintGraph::print

(

)

Print CG into terminal.

Print this constraint graph including its nodes and edges

Definition at line 603 of file ConsG.cpp.

{
 
    outs() << "-----------------ConstraintGraph--------------------------------------\n";
 
    ConstraintEdge::ConstraintEdgeSetTy& addrs = this->getAddrCGEdges();
    for (ConstraintEdge::ConstraintEdgeSetTy::iterator iter = addrs.begin(),
            eiter = addrs.end(); iter != eiter; ++iter)
    {
        outs() << (*iter)->getSrcID() << " -- Addr --> " << (*iter)->getDstID()
               << "\n";
    }
 
    ConstraintEdge::ConstraintEdgeSetTy& directs = this->getDirectCGEdges();
    for (ConstraintEdge::ConstraintEdgeSetTy::iterator iter = directs.begin(),
            eiter = directs.end(); iter != eiter; ++iter)
    {
        if (CopyCGEdge* copy = SVFUtil::dyn_cast<CopyCGEdge>(*iter))
        {
            outs() << copy->getSrcID() << " -- Copy --> " << copy->getDstID()
                   << "\n";
        }
        else if (NormalGepCGEdge* ngep = SVFUtil::dyn_cast<NormalGepCGEdge>(*iter))
        {
            outs() << ngep->getSrcID() << " -- NormalGep (" << ngep->getConstantFieldIdx()
                   << ") --> " << ngep->getDstID() << "\n";
        }
        else if (VariantGepCGEdge* vgep = SVFUtil::dyn_cast<VariantGepCGEdge>(*iter))
        {
            outs() << vgep->getSrcID() << " -- VarintGep --> "
                   << vgep->getDstID() << "\n";
        }
        else
            assert(false && "wrong constraint edge kind!");
    }
 
    ConstraintEdge::ConstraintEdgeSetTy& loads = this->getLoadCGEdges();
    for (ConstraintEdge::ConstraintEdgeSetTy::iterator iter = loads.begin(),
            eiter = loads.end(); iter != eiter; ++iter)
    {
        outs() << (*iter)->getSrcID() << " -- Load --> " << (*iter)->getDstID()
               << "\n";
    }
 
    ConstraintEdge::ConstraintEdgeSetTy& stores = this->getStoreCGEdges();
    for (ConstraintEdge::ConstraintEdgeSetTy::iterator iter = stores.begin(),
            eiter = stores.end(); iter != eiter; ++iter)
    {
        outs() << (*iter)->getSrcID() << " -- Store --> " << (*iter)->getDstID()
               << "\n";
    }
 
    outs()
            << "--------------------------------------------------------------\n";
 
}

removeAddrEdge()

void ConstraintGraph::removeAddrEdge

(

AddrCGEdge *

edge

)

Remove addr edge from their src and dst edge sets.

Remove addr edge from their src and dst edge sets

Definition at line 424 of file ConsG.cpp.

{
    getConstraintNode(edge->getSrcID())->removeOutgoingAddrEdge(edge);
    getConstraintNode(edge->getDstID())->removeIncomingAddrEdge(edge);
    u32_t num = AddrCGEdgeSet.erase(edge);
    (void)num; // Suppress warning of unused variable under release build
    assert(num && "edge not in the set, can not remove!!!");
    delete edge;
}

removeConstraintNode()

void SVF::ConstraintGraph::removeConstraintNode ( ConstraintNode * node )

inline

Definition at line 118 of file ConsG.h.

    {
        removeGNode(node);
    }

removeDirectEdge()

void ConstraintGraph::removeDirectEdge

(

ConstraintEdge *

edge

)

Remove direct edge from their src and dst edge sets.

Remove edges from their src and dst edge sets

Definition at line 463 of file ConsG.cpp.

{
 
    getConstraintNode(edge->getSrcID())->removeOutgoingDirectEdge(edge);
    getConstraintNode(edge->getDstID())->removeIncomingDirectEdge(edge);
    u32_t num = directEdgeSet.erase(edge);
    (void)num; // Suppress warning of unused variable under release build
    assert(num && "edge not in the set, can not remove!!!");
    delete edge;
}

removeLoadEdge()

void ConstraintGraph::removeLoadEdge

(

LoadCGEdge *

edge

)

Remove load edge from their src and dst edge sets.

Remove load edge from their src and dst edge sets

Definition at line 437 of file ConsG.cpp.

{
    getConstraintNode(edge->getSrcID())->removeOutgoingLoadEdge(edge);
    getConstraintNode(edge->getDstID())->removeIncomingLoadEdge(edge);
    u32_t num = LoadCGEdgeSet.erase(edge);
    (void)num; // Suppress warning of unused variable under release build
    assert(num && "edge not in the set, can not remove!!!");
    delete edge;
}

removeStoreEdge()

void ConstraintGraph::removeStoreEdge

(

StoreCGEdge *

edge

)

Remove store edge from their src and dst edge sets.

Remove store edge from their src and dst edge sets

Definition at line 450 of file ConsG.cpp.

{
    getConstraintNode(edge->getSrcID())->removeOutgoingStoreEdge(edge);
    getConstraintNode(edge->getDstID())->removeIncomingStoreEdge(edge);
    u32_t num = StoreCGEdgeSet.erase(edge);
    (void)num; // Suppress warning of unused variable under release build
    assert(num && "edge not in the set, can not remove!!!");
    delete edge;
}

resetRep()

void SVF::ConstraintGraph::resetRep ( NodeID node )

inline

Definition at line 263 of file ConsG.h.

    {
        nodeToRepMap.erase(node);
    }

resetSubs()

void SVF::ConstraintGraph::resetSubs ( NodeID node )

inline

Definition at line 251 of file ConsG.h.

    {
        nodeToSubsMap.erase(node);
    }

reTargetDstOfEdge()

void ConstraintGraph::reTargetDstOfEdge	(	ConstraintEdge *	edge,
		ConstraintNode *	newDstNode )

Used for cycle elimination.

Remove edge from old dst target, change edge dst id and add modified edge into new dst

Re-target dst node of an edge

(1) Remove edge from old dst target, (2) Change edge dst id and (3) Add modified edge into new dst

Definition at line 339 of file ConsG.cpp.

{
    NodeID newDstNodeID = newDstNode->getId();
    NodeID srcId = edge->getSrcID();
    if(LoadCGEdge* load = SVFUtil::dyn_cast<LoadCGEdge>(edge))
    {
        removeLoadEdge(load);
        addLoadCGEdge(srcId,newDstNodeID);
    }
    else if(StoreCGEdge* store = SVFUtil::dyn_cast<StoreCGEdge>(edge))
    {
        removeStoreEdge(store);
        addStoreCGEdge(srcId,newDstNodeID);
    }
    else if(CopyCGEdge* copy = SVFUtil::dyn_cast<CopyCGEdge>(edge))
    {
        removeDirectEdge(copy);
        addCopyCGEdge(srcId,newDstNodeID);
    }
    else if(NormalGepCGEdge* gep = SVFUtil::dyn_cast<NormalGepCGEdge>(edge))
    {
        const AccessPath ap = gep->getAccessPath();
        removeDirectEdge(gep);
        addNormalGepCGEdge(srcId,newDstNodeID, ap);
    }
    else if(VariantGepCGEdge* gep = SVFUtil::dyn_cast<VariantGepCGEdge>(edge))
    {
        removeDirectEdge(gep);
        addVariantGepCGEdge(srcId,newDstNodeID);
    }
    else if(AddrCGEdge* addr = SVFUtil::dyn_cast<AddrCGEdge>(edge))
    {
        removeAddrEdge(addr);
    }
    else
        assert(false && "no other edge type!!");
}

reTargetSrcOfEdge()

void ConstraintGraph::reTargetSrcOfEdge	(	ConstraintEdge *	edge,
		ConstraintNode *	newSrcNode )

Remove edge from old src target, change edge dst id and add modified edge into new src.

Re-target src node of an edge (1) Remove edge from old src target, (2) Change edge src id and (3) Add modified edge into new src

Definition at line 383 of file ConsG.cpp.

{
    NodeID newSrcNodeID = newSrcNode->getId();
    NodeID dstId = edge->getDstID();
    if(LoadCGEdge* load = SVFUtil::dyn_cast<LoadCGEdge>(edge))
    {
        removeLoadEdge(load);
        addLoadCGEdge(newSrcNodeID,dstId);
    }
    else if(StoreCGEdge* store = SVFUtil::dyn_cast<StoreCGEdge>(edge))
    {
        removeStoreEdge(store);
        addStoreCGEdge(newSrcNodeID,dstId);
    }
    else if(CopyCGEdge* copy = SVFUtil::dyn_cast<CopyCGEdge>(edge))
    {
        removeDirectEdge(copy);
        addCopyCGEdge(newSrcNodeID,dstId);
    }
    else if(NormalGepCGEdge* gep = SVFUtil::dyn_cast<NormalGepCGEdge>(edge))
    {
        const AccessPath ap = gep->getAccessPath();
        removeDirectEdge(gep);
        addNormalGepCGEdge(newSrcNodeID, dstId, ap);
    }
    else if(VariantGepCGEdge* gep = SVFUtil::dyn_cast<VariantGepCGEdge>(edge))
    {
        removeDirectEdge(gep);
        addVariantGepCGEdge(newSrcNodeID,dstId);
    }
    else if(AddrCGEdge* addr = SVFUtil::dyn_cast<AddrCGEdge>(edge))
    {
        removeAddrEdge(addr);
    }
    else
        assert(false && "no other edge type!!");
}

sccRepNode()

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

inline

SCC rep/sub nodes methods.

Definition at line 230 of file ConsG.h.

    {
        NodeToRepMap::const_iterator it = nodeToRepMap.find(id);
        if(it==nodeToRepMap.end())
            return id;
        else
            return it->second;
    }

sccSubNodes()

NodeBS & SVF::ConstraintGraph::sccSubNodes ( NodeID id )

inline

Definition at line 238 of file ConsG.h.

    {
        nodeToSubsMap[id].set(id);
        return nodeToSubsMap[id];
    }

setPWCNode()

void SVF::ConstraintGraph::setPWCNode ( NodeID nodeId )

inline

Definition at line 349 of file ConsG.h.

    {
        getConstraintNode(nodeId)->setPWCNode();
    }

setRep()

void SVF::ConstraintGraph::setRep ( NodeID node, NodeID rep )

inline

Definition at line 243 of file ConsG.h.

    {
        nodeToRepMap[node] = rep;
    }

setSubs()

void SVF::ConstraintGraph::setSubs ( NodeID node, NodeBS & subs )

inline

Definition at line 247 of file ConsG.h.

    {
        nodeToSubsMap[node] |= subs;
    }

view()

void ConstraintGraph::view

(

)

View graph from the debugger.

View dot graph of Constraint graph from debugger.

Definition at line 663 of file ConsG.cpp.

{
    SVF::ViewGraph(this, "Constraint Graph");
}

Member Data Documentation

AddrCGEdgeSet

ConstraintEdge::ConstraintEdgeSetTy SVF::ConstraintGraph::AddrCGEdgeSet

protected

Definition at line 61 of file ConsG.h.

directEdgeSet

ConstraintEdge::ConstraintEdgeSetTy SVF::ConstraintGraph::directEdgeSet

protected

Definition at line 62 of file ConsG.h.

edgeIndex

EdgeID SVF::ConstraintGraph::edgeIndex

protected

Definition at line 59 of file ConsG.h.

LoadCGEdgeSet

ConstraintEdge::ConstraintEdgeSetTy SVF::ConstraintGraph::LoadCGEdgeSet

protected

Definition at line 63 of file ConsG.h.

nodesToBeCollapsed

WorkList SVF::ConstraintGraph::nodesToBeCollapsed

protected

Definition at line 58 of file ConsG.h.

nodeToRepMap

NodeToRepMap SVF::ConstraintGraph::nodeToRepMap

protected

Definition at line 56 of file ConsG.h.

nodeToSubsMap

NodeToSubsMap SVF::ConstraintGraph::nodeToSubsMap

protected

Definition at line 57 of file ConsG.h.

pag

SVFIR* SVF::ConstraintGraph::pag

protected

Definition at line 55 of file ConsG.h.

StoreCGEdgeSet

ConstraintEdge::ConstraintEdgeSetTy SVF::ConstraintGraph::StoreCGEdgeSet

protected

Definition at line 64 of file ConsG.h.

---

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

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