SVF::MTASVFGBuilder Class Reference

#include <FSMPTA.h>

Inheritance diagram for SVF::MTASVFGBuilder:

Public Types
typedef PointerAnalysis::CallSiteSet	CallSiteSet
typedef PointerAnalysis::CallEdgeMap	CallEdgeMap
typedef PointerAnalysis::FunctionSet	FunctionSet
typedef Set< const SVFGNode * >	SVFGNodeSet
typedef std::vector< const SVFGNode * >	SVFGNodeVec
typedef NodeBS	SVFGNodeIDSet
typedef Set< const SVFInstruction * >	InstSet
typedef std::pair< NodeID, NodeID >	NodeIDPair
typedef Map< SVFGNodeLockSpan, bool >	PairToBoolMap
Public Types inherited from SVF::SVFGBuilder
typedef PointerAnalysis::CallSiteSet	CallSiteSet
typedef PointerAnalysis::CallEdgeMap	CallEdgeMap
typedef PointerAnalysis::FunctionSet	FunctionSet
typedef SVFG::SVFGEdgeSetTy	SVFGEdgeSet

Public Member Functions
	MTASVFGBuilder (MHP *m, LockAnalysis *la)
	Constructor. More...
virtual	~MTASVFGBuilder ()
	Destructor. More...
Public Member Functions inherited from SVF::SVFGBuilder
	SVFGBuilder (bool _SVFGWithIndCall=false)
	Constructor. More...
virtual	~SVFGBuilder ()=default
	Destructor. More...
SVFG *	buildPTROnlySVFG (BVDataPTAImpl *pta)
SVFG *	buildFullSVFG (BVDataPTAImpl *pta)
SVFG *	getSVFG () const
	Get SVFG instance. More...
void	markValidVFEdge (SVFGEdgeSet &edges)
	Mark feasible VF edge by removing it from set vfEdgesAtIndCallSite. More...
bool	isSpuriousVFEdgeAtIndCallSite (const SVFGEdge *edge)
	Return true if this is an VF Edge pre-connected by Andersen's analysis. More...
virtual std::unique_ptr< MemSSA >	buildMSSA (BVDataPTAImpl *pta, bool ptrOnlyMSSA)
	Build Memory SSA. More...

Static Public Attributes
static u32_t	numOfNewSVFGEdges = 0
	Number of newly added SVFG edges. More...
static u32_t	numOfRemovedSVFGEdges = 0
static u32_t	numOfRemovedPTS = 0

Protected Member Functions
virtual void	buildSVFG ()
	Re-write create SVFG method. More...
Protected Member Functions inherited from SVF::SVFGBuilder
SVFG *	build (BVDataPTAImpl *pta, VFG::VFGK kind)
	Create a DDA SVFG. By default actualOut and FormalIN are removed, unless withAOFI is set true. More...
virtual void	releaseMemory ()
	Release global SVFG. More...

Private Member Functions
bool	recordEdge (NodeID id1, NodeID id2, PointsTo pts)
	Record edges. More...
bool	recordAddingEdge (NodeID id1, NodeID id2, PointsTo pts)
bool	recordRemovingEdge (NodeID id1, NodeID id2, PointsTo pts)
void	performAddingMHPEdges ()
	perform adding/removing MHP Edges in value flow graph More...
void	performRemovingMHPEdges ()
SVFGEdge *	addTDEdges (NodeID srcId, NodeID dstId, PointsTo &pts)
void	connectMHPEdges (PointerAnalysis *pta)
	Connect MHP indirect value-flow edges for two nodes that may-happen-in-parallel. More...
void	handleStoreLoadNonSparse (const StmtSVFGNode *n1, const StmtSVFGNode *n2, PointerAnalysis *pta)
void	handleStoreStoreNonSparse (const StmtSVFGNode *n1, const StmtSVFGNode *n2, PointerAnalysis *pta)
void	handleStoreLoad (const StmtSVFGNode *n1, const StmtSVFGNode *n2, PointerAnalysis *pta)
void	handleStoreStore (const StmtSVFGNode *n1, const StmtSVFGNode *n2, PointerAnalysis *pta)
void	handleStoreLoadWithLockPrecisely (const StmtSVFGNode *n1, const StmtSVFGNode *n2, PointerAnalysis *pta)
void	handleStoreStoreWithLockPrecisely (const StmtSVFGNode *n1, const StmtSVFGNode *n2, PointerAnalysis *pta)
void	mergeSpan (NodeBS comlocks, InstSet &res)
void	readPrecision ()
	For o, n2-o->n1, n1 and n2 are write. Foreach n3:n1->n3, n2->n3; then remove n2->n1. More...
SVFGNodeIDSet	getPrevNodes (const StmtSVFGNode *n)
SVFGNodeIDSet	getSuccNodes (const StmtSVFGNode *n)
SVFGNodeIDSet	getSuccNodes (const StmtSVFGNode *n, NodeID o)
bool	isHeadofSpan (const StmtSVFGNode *n, LockAnalysis::LockSpan lspan)
	whether is a first write in the lock span. More...
bool	isTailofSpan (const StmtSVFGNode *n, LockAnalysis::LockSpan lspan)
	whether is a last write in the lock span. More...
bool	isHeadofSpan (const StmtSVFGNode *n, InstSet mergespan)
bool	isTailofSpan (const StmtSVFGNode *n, InstSet mergespan)
bool	isHeadofSpan (const StmtSVFGNode *n)
bool	isTailofSpan (const StmtSVFGNode *n)
void	collectLoadStoreSVFGNodes ()
	Collect all loads/stores SVFGNodes. More...

Private Attributes
SVFGNodeSet	stnodeSet
	all stores/loads SVFGNodes More...
SVFGNodeSet	ldnodeSet
MHP *	mhp
	MHP class. More...
LockAnalysis *	lockana
Set< NodeIDPair >	recordedges
Map< NodeIDPair, PointsTo >	edge2pts
Map< const StmtSVFGNode *, SVFGNodeIDSet >	prevset
Map< const StmtSVFGNode *, SVFGNodeIDSet >	succset
Map< const StmtSVFGNode *, bool >	headmap
Map< const StmtSVFGNode *, bool >	tailmap
PairToBoolMap	pairheadmap
PairToBoolMap	pairtailmap

Static Private Attributes
static const u32_t	ADDEDGE_NOEDGE = 0
static const u32_t	ADDEDGE_NONSPARSE = 1
static const u32_t	ADDEDGE_ALLOPT = 2
static const u32_t	ADDEDGE_NOMHP = 3
static const u32_t	ADDEDGE_NOALIAS = 4
static const u32_t	ADDEDGE_NOLOCK = 5
static const u32_t	ADDEDGE_NORP = 6

Additional Inherited Members
Protected Attributes inherited from SVF::SVFGBuilder
SVFGEdgeSet	vfEdgesAtIndCallSite
	SVFG Edges connected at indirect call/ret sites. More...
std::unique_ptr< SVFG >	svfg
bool	SVFGWithIndCall
	SVFG with precomputed indirect call edges. More...

Detailed Description

SVFG builder for DDA

Definition at line 97 of file FSMPTA.h.

Member Typedef Documentation

CallEdgeMap

typedef PointerAnalysis::CallEdgeMap SVF::MTASVFGBuilder::CallEdgeMap

Definition at line 102 of file FSMPTA.h.

CallSiteSet

typedef PointerAnalysis::CallSiteSet SVF::MTASVFGBuilder::CallSiteSet

Definition at line 101 of file FSMPTA.h.

FunctionSet

typedef PointerAnalysis::FunctionSet SVF::MTASVFGBuilder::FunctionSet

Definition at line 103 of file FSMPTA.h.

InstSet

typedef Set<const SVFInstruction*> SVF::MTASVFGBuilder::InstSet

Definition at line 107 of file FSMPTA.h.

NodeIDPair

typedef std::pair<NodeID,NodeID> SVF::MTASVFGBuilder::NodeIDPair

Definition at line 108 of file FSMPTA.h.

PairToBoolMap

typedef Map<SVFGNodeLockSpan, bool> SVF::MTASVFGBuilder::PairToBoolMap

Definition at line 109 of file FSMPTA.h.

SVFGNodeIDSet

typedef NodeBS SVF::MTASVFGBuilder::SVFGNodeIDSet

Definition at line 106 of file FSMPTA.h.

SVFGNodeSet

typedef Set<const SVFGNode*> SVF::MTASVFGBuilder::SVFGNodeSet

Definition at line 104 of file FSMPTA.h.

SVFGNodeVec

typedef std::vector<const SVFGNode*> SVF::MTASVFGBuilder::SVFGNodeVec

Definition at line 105 of file FSMPTA.h.

Constructor & Destructor Documentation

MTASVFGBuilder()

SVF::MTASVFGBuilder::MTASVFGBuilder ( MHP *  m, LockAnalysis *  la  )

inline

Constructor.

Definition at line 112 of file FSMPTA.h.

                                             : SVFGBuilder(), mhp(m), lockana(la)
    {
    }

~MTASVFGBuilder()

virtual SVF::MTASVFGBuilder::~MTASVFGBuilder ( )

inlinevirtual

Destructor.

Definition at line 117 of file FSMPTA.h.

{}

Member Function Documentation

addTDEdges()

SVFGEdge * MTASVFGBuilder::addTDEdges ( NodeID  srcId, NodeID  dstId, PointsTo &  pts  )

private

Definition at line 125 of file FSMPTA.cpp.

{
 
    SVFGNode* srcNode = svfg->getSVFGNode(srcId);
    SVFGNode* dstNode = svfg->getSVFGNode(dstId);
 
    if(SVFGEdge* edge = svfg->hasThreadVFGEdge(srcNode,dstNode,SVFGEdge::TheadMHPIndirectVF))
    {
        assert(SVFUtil::isa<IndirectSVFGEdge>(edge) && "this should be a indirect value flow edge!");
        return (SVFUtil::cast<IndirectSVFGEdge>(edge)->addPointsTo(pts.toNodeBS()) ? edge : nullptr);
    }
    else
    {
        MTASVFGBuilder::numOfNewSVFGEdges++;
        ThreadMHPIndSVFGEdge* indirectEdge = new ThreadMHPIndSVFGEdge(srcNode,dstNode);
        indirectEdge->addPointsTo(pts.toNodeBS());
        return (svfg->addSVFGEdge(indirectEdge) ? indirectEdge : nullptr);
    }
}

buildSVFG()

void MTASVFGBuilder::buildSVFG ( )

protectedvirtual

Re-write create SVFG method.

Reimplemented from SVF::SVFGBuilder.

Definition at line 47 of file FSMPTA.cpp.

{
    MemSSA* mssa = svfg->getMSSA();
    svfg->buildSVFG();
    if (ADDEDGE_NOEDGE != Options::AddModelFlag())
    {
        DBOUT(DGENERAL, outs() << SVFUtil::pasMsg("FSMPTA adding edge\n"));
        DBOUT(DMTA, outs() << SVFUtil::pasMsg("FSMPTA adding edge\n"));
        connectMHPEdges(mssa->getPTA());
    }
    if (mssa->getPTA()->printStat())
        svfg->performStat();
}

collectLoadStoreSVFGNodes()

void MTASVFGBuilder::collectLoadStoreSVFGNodes ( )

private

Collect all loads/stores SVFGNodes.

Definition at line 64 of file FSMPTA.cpp.

{
 
    for (SVFG::const_iterator it = svfg->begin(), eit = svfg->end(); it != eit; ++it)
    {
        const SVFGNode* snode = it->second;
        if (SVFUtil::isa<LoadSVFGNode>(snode))
        {
            const StmtSVFGNode* node = SVFUtil::cast<StmtSVFGNode>(snode);
            if (node->getInst())
            {
                ldnodeSet.insert(node);
            }
        }
        if (SVFUtil::isa<StoreSVFGNode>(snode))
        {
            const StmtSVFGNode* node = SVFUtil::cast<StmtSVFGNode>(snode);
            if (node->getInst())
            {
                stnodeSet.insert(node);
            }
        }
    }
}

connectMHPEdges()

void MTASVFGBuilder::connectMHPEdges ( PointerAnalysis *  pta )

private

Connect MHP indirect value-flow edges for two nodes that may-happen-in-parallel.

todo: we ignore rule 2 and 3. but so far I haven't added intra-thread value flow affected by fork and inter-thread value flow affected by join

Definition at line 706 of file FSMPTA.cpp.

{
    PCG* pcg = new PCG(pta);
    if ((ADDEDGE_NONSPARSE==Options::AddModelFlag()) && Options::UsePCG())
    {
        pcg->analyze();
    }
    collectLoadStoreSVFGNodes();
    recordedges.clear();
    edge2pts.clear();
 
    for (SVFGNodeSet::const_iterator it1 = stnodeSet.begin(), eit1 =  stnodeSet.end(); it1!=eit1; ++it1)
    {
        const StmtSVFGNode* n1 = SVFUtil::cast<StmtSVFGNode>(*it1);
        const SVFInstruction* i1 = n1->getInst();
 
        for (SVFGNodeSet::const_iterator it2 = ldnodeSet.begin(), eit2 = ldnodeSet.end(); it2 != eit2; ++it2)
        {
            const StmtSVFGNode* n2 = SVFUtil::cast<StmtSVFGNode>(*it2);
            const SVFInstruction* i2 = n2->getInst();
            if (ADDEDGE_NONSPARSE==Options::AddModelFlag())
            {
                if (Options::UsePCG())
                {
                    if (pcg->mayHappenInParallel(i1, i2) || mhp->mayHappenInParallel(i1, i2))
                        handleStoreLoadNonSparse(n1, n2, pta);
                }
                else
                {
                    handleStoreLoadNonSparse(n1, n2, pta);
                }
            }
            else
            {
                handleStoreLoad(n1, n2, pta);
            }
        }
 
        for (SVFGNodeSet::const_iterator it2 = std::next(it1), eit2 =  stnodeSet.end(); it2!=eit2; ++it2)
        {
            const StmtSVFGNode* n2 = SVFUtil::cast<StmtSVFGNode>(*it2);
            const SVFInstruction* i2 = n2->getInst();
            if (ADDEDGE_NONSPARSE == Options::AddModelFlag())
            {
                if (Options::UsePCG())
                {
                    if(pcg->mayHappenInParallel(i1, i2) || mhp->mayHappenInParallel(i1, i2))
                        handleStoreStoreNonSparse(n1, n2, pta);
                }
                else
                {
                    handleStoreStoreNonSparse(n1, n2, pta);
                }
            }
            else
            {
                handleStoreStore(n1, n2, pta);
            }
        }
    }
 
    if(Options::ReadPrecisionTDEdge() && ADDEDGE_NORP!=Options::AddModelFlag())
    {
        DBOUT(DGENERAL,outs()<<"Read precision edge removing \n");
        DBOUT(DMTA,outs()<<"Read precision edge removing \n");
        readPrecision();
    }
}

getPrevNodes()

MTASVFGBuilder::SVFGNodeIDSet MTASVFGBuilder::getPrevNodes ( const StmtSVFGNode *  n )

private

Definition at line 344 of file FSMPTA.cpp.

{
    if (prevset.find(n)!=prevset.end())
        return prevset[n];
 
    SVFGNodeIDSet prev;
    SVFGNodeSet worklist;
    SVFGNodeSet visited;
 
    for (SVFGEdge::SVFGEdgeSetTy::iterator iter = n->InEdgeBegin(); iter != n->InEdgeEnd(); ++iter)
    {
        SVFGEdge* edge = *iter;
        if (edge->isIndirectVFGEdge())
        {
            worklist.insert(edge->getSrcNode());
        }
    }
 
    while (!worklist.empty())
    {
        const SVFGNode* node =  *worklist.begin();
        worklist.erase(worklist.begin());
        visited.insert(node);
        if (SVFUtil::isa<StoreSVFGNode>(node))
            prev.set(node->getId());
        else
        {
            for (SVFGEdge::SVFGEdgeSetTy::iterator iter = node->InEdgeBegin(); iter != node->InEdgeEnd(); ++iter)
            {
                SVFGEdge* edge = *iter;
                if (edge->isIndirectVFGEdge() && visited.find(edge->getSrcNode())==visited.end())
                    worklist.insert(edge->getSrcNode());
            }
        }
    }
    prevset[n]=prev;
    return prev;
}

getSuccNodes() [1/2]

MTASVFGBuilder::SVFGNodeIDSet MTASVFGBuilder::getSuccNodes ( const StmtSVFGNode *  n )

private

Definition at line 382 of file FSMPTA.cpp.

{
    if (succset.find(n)!=succset.end())
        return succset[n];
 
    SVFGNodeIDSet succ;
    SVFGNodeSet worklist;
    SVFGNodeSet visited;
 
    for (SVFGEdge::SVFGEdgeSetTy::iterator iter = n->OutEdgeBegin(); iter != n->OutEdgeEnd(); ++iter)
    {
        SVFGEdge* edge = *iter;
        if (edge->isIndirectVFGEdge())
        {
            worklist.insert(edge->getDstNode());
        }
    }
 
    while (!worklist.empty())
    {
        const SVFGNode* node = *worklist.begin();
        worklist.erase(worklist.begin());
        visited.insert(node);
        if (SVFUtil::isa<StoreSVFGNode, LoadSVFGNode>(node))
            succ.set(node->getId());
        else
        {
            for (SVFGEdge::SVFGEdgeSetTy::iterator iter = node->OutEdgeBegin(); iter != node->OutEdgeEnd(); ++iter)
            {
                SVFGEdge* edge = *iter;
                if (edge->isIndirectVFGEdge() && visited.find(edge->getDstNode()) == visited.end())
                    worklist.insert(edge->getDstNode());
            }
        }
    }
    succset[n]=succ;
    return succ;
}

getSuccNodes() [2/2]

MTASVFGBuilder::SVFGNodeIDSet MTASVFGBuilder::getSuccNodes ( const StmtSVFGNode *  n, NodeID  o  )

private

Definition at line 420 of file FSMPTA.cpp.

{
 
    SVFGNodeIDSet succ;
    SVFGNodeSet worklist;
    SVFGNodeSet visited;
 
    for (SVFGEdge::SVFGEdgeSetTy::iterator iter = n->OutEdgeBegin(); iter != n->OutEdgeEnd(); ++iter)
    {
        SVFGEdge* edge = *iter;
        if (edge->isIndirectVFGEdge())
        {
            IndirectSVFGEdge* e = SVFUtil::cast<IndirectSVFGEdge>(edge);
            NodeBS pts = e->getPointsTo();
            if(pts.test(o))
                worklist.insert(edge->getDstNode());
        }
    }
 
    while (!worklist.empty())
    {
        const SVFGNode* node = *worklist.begin();
        worklist.erase(worklist.begin());
        visited.insert(node);
        if (SVFUtil::isa<StoreSVFGNode, LoadSVFGNode>(node))
            succ.set(node->getId());
        else
        {
            for (SVFGEdge::SVFGEdgeSetTy::iterator iter = node->OutEdgeBegin(); iter != node->OutEdgeEnd(); ++iter)
            {
                SVFGEdge* edge = *iter;
                if (edge->isIndirectVFGEdge() && visited.find(edge->getDstNode()) == visited.end())
                {
                    IndirectSVFGEdge* e = SVFUtil::cast<IndirectSVFGEdge>(edge);
                    NodeBS pts = e->getPointsTo();
                    if(pts.test(o))
                        worklist.insert(edge->getDstNode());
                }
            }
        }
    }
 
    return succ;
}

handleStoreLoad()

void MTASVFGBuilder::handleStoreLoad ( const StmtSVFGNode *  n1, const StmtSVFGNode *  n2, PointerAnalysis *  pta  )

private

MHP

Alias

Lock todo: we only consider all cxtstmt of one instruction in one lock span, otherwise we think this instruction is not locked This constraint is too strong. All cxt lock under different cxt cannot be identified.

Definition at line 484 of file FSMPTA.cpp.

{
    const SVFInstruction* i1 = n1->getInst();
    const SVFInstruction* i2 = n2->getInst();
    if (ADDEDGE_NOMHP!=Options::AddModelFlag() && !mhp->mayHappenInParallel(i1, i2))
        return;
    if (ADDEDGE_NOALIAS!=Options::AddModelFlag() && !pta->alias(n1->getPAGDstNodeID(), n2->getPAGSrcNodeID()))
        return;
 
 
    PointsTo pts = pta->getPts(n1->getPAGDstNodeID());
    pts &= pta->getPts(n2->getPAGSrcNodeID());
 
 
 
    if (ADDEDGE_NOLOCK!=Options::AddModelFlag() && lockana->isProtectedByCommonLock(i1, i2))
    {
        if (isTailofSpan(n1) && isHeadofSpan(n2))
            addTDEdges(n1->getId(), n2->getId(), pts);
    }
    else
    {
        addTDEdges(n1->getId(), n2->getId(), pts);
    }
}

handleStoreLoadNonSparse()

void MTASVFGBuilder::handleStoreLoadNonSparse ( const StmtSVFGNode *  n1, const StmtSVFGNode *  n2, PointerAnalysis *  pta  )

private

Definition at line 465 of file FSMPTA.cpp.

{
    PointsTo pts = pta->getPts(n1->getPAGDstNodeID());
    pts &= pta->getPts(n2->getPAGSrcNodeID());
 
    addTDEdges(n1->getId(), n2->getId(), pts);
}

handleStoreLoadWithLockPrecisely()

void MTASVFGBuilder::handleStoreLoadWithLockPrecisely ( const StmtSVFGNode *  n1, const StmtSVFGNode *  n2, PointerAnalysis *  pta  )

private

Definition at line 547 of file FSMPTA.cpp.

{
    if (!pta->alias(n1->getPAGDstNodeID(), n2->getPAGSrcNodeID()))
        return;
 
//    PointsTo pts = pta->getPts(n1->getPAGDstNodeID());
//    pts &= pta->getPts(n2->getPAGSrcNodeID());
//
//    const SVFInstruction* i1 = n1->getInst();
//    const SVFInstruction* i2 = n2->getInst();
//
//    NodeBS comlocks1;
//    NodeBS comlocks2;
//    lockana->getCommonLocks(i1, i2, comlocks1, comlocks2);
//
//    outs()<<comlocks1.count() << "  "<< comlocks2.count()<<"\n";
 
 
//    if(comlocks1.count() && comlocks2.count()) {
//        bool n1istail = false;
//        for (NodeBS::iterator it1 = comlocks1.begin(), ie1 = comlocks1.end(); it1 != ie1; ++it1) {
//            LockAnalysis::LockSpan lspan1 = lockana->getSpanfromCxtLock(*it1);
//            /// exist lock span, n1 is tail;
//            if (isTailofSpan(n1, lspan1))
//                n1istail = true;
//        }
//
//        bool n2ishead = false;
//        for (NodeBS::iterator it2 = comlocks2.begin(), ie2 = comlocks2.end(); it2 != ie2; ++it2) {
//            LockAnalysis::LockSpan lspan2 = lockana->getSpanfromCxtLock(*it2);
//            /// exist lock span, n2 is head;
//            if (isHeadofSpan(n2, lspan2))
//                n2ishead = true;
//        }
//
//        if (n1istail && n2ishead)
//            addTDEdges(n1->getId(), n2->getId(), pts);
//    } else {
//        addTDEdges(n1->getId(), n2->getId(), pts);
//    }
}

handleStoreStore()

void MTASVFGBuilder::handleStoreStore ( const StmtSVFGNode *  n1, const StmtSVFGNode *  n2, PointerAnalysis *  pta  )

private

MHP

Alias

Lock

Definition at line 518 of file FSMPTA.cpp.

{
    const SVFInstruction* i1 = n1->getInst();
    const SVFInstruction* i2 = n2->getInst();
    if (ADDEDGE_NOMHP!=Options::AddModelFlag() && !mhp->mayHappenInParallel(i1, i2))
        return;
    if (ADDEDGE_NOALIAS!=Options::AddModelFlag() && !pta->alias(n1->getPAGDstNodeID(), n2->getPAGDstNodeID()))
        return;
 
    PointsTo pts = pta->getPts(n1->getPAGDstNodeID());
    pts &= pta->getPts(n2->getPAGDstNodeID());
 
    if (ADDEDGE_NOLOCK!=Options::AddModelFlag() && lockana->isProtectedByCommonLock(i1, i2))
    {
        if (isTailofSpan(n1) && isHeadofSpan(n2))
            addTDEdges(n1->getId(), n2->getId(), pts);
        if (isTailofSpan(n2) && isHeadofSpan(n1))
            addTDEdges(n2->getId(), n1->getId(), pts);
    }
    else
    {
        addTDEdges(n1->getId(), n2->getId(), pts);
        addTDEdges(n2->getId(), n1->getId(), pts);
    }
}

handleStoreStoreNonSparse()

void MTASVFGBuilder::handleStoreStoreNonSparse ( const StmtSVFGNode *  n1, const StmtSVFGNode *  n2, PointerAnalysis *  pta  )

private

Definition at line 475 of file FSMPTA.cpp.

{
    PointsTo pts = pta->getPts(n1->getPAGDstNodeID());
    pts &= pta->getPts(n2->getPAGDstNodeID());
 
    addTDEdges(n1->getId(), n2->getId(), pts);
    addTDEdges(n2->getId(), n1->getId(), pts);
}

handleStoreStoreWithLockPrecisely()

void MTASVFGBuilder::handleStoreStoreWithLockPrecisely ( const StmtSVFGNode *  n1, const StmtSVFGNode *  n2, PointerAnalysis *  pta  )

private

Definition at line 588 of file FSMPTA.cpp.

{
    if (!pta->alias(n1->getPAGDstNodeID(), n2->getPAGDstNodeID()))
        return;
 
//    PointsTo pts = pta->getPts(n1->getPAGDstNodeID());
//    pts &= pta->getPts(n2->getPAGDstNodeID());
//
//    const SVFInstruction* i1 = n1->getInst();
//    const SVFInstruction* i2 = n2->getInst();
 
 
//    NodeBS comlocks1;
//    NodeBS comlocks2;
//    lockana->getCommonLocks(i1, i2, comlocks1, comlocks2);
//    if(comlocks1.count() && comlocks2.count()) {
//        bool n1istail = false;
//        for (NodeBS::iterator it1 = comlocks1.begin(), ie1 = comlocks1.end(); it1 != ie1; ++it1) {
//            LockAnalysis::LockSpan lspan1 = lockana->getSpanfromCxtLock(*it1);
//            /// exist lock span, n1 is tail;
//            if (isTailofSpan(n1, lspan1))
//                n1istail = true;
//        }
//        bool n2ishead = false;
//        for (NodeBS::iterator it2 = comlocks2.begin(), ie2 = comlocks2.end(); it2 != ie2; ++it2) {
//            LockAnalysis::LockSpan lspan2 = lockana->getSpanfromCxtLock(*it2);
//            /// exist lock span, n2 is head;
//            if (isHeadofSpan(n2, lspan2))
//                n2ishead = true;
//        }
//        if (n1istail && n2ishead)
//            addTDEdges(n1->getId(), n2->getId(), pts);
//
//
//
//        bool n2istail = false;
//        for (NodeBS::iterator it2 = comlocks2.begin(), ie2 = comlocks2.end(); it2 != ie2; ++it2) {
//            LockAnalysis::LockSpan lspan2 = lockana->getSpanfromCxtLock(*it2);
//            /// exist lock span, n2 is tail;
//            if (isTailofSpan(n2, lspan2))
//                n2istail = true;
//        }
//        bool n1ishead = false;
//        for (NodeBS::iterator it1 = comlocks1.begin(), ie1 = comlocks1.end(); it1 != ie1; ++it1) {
//            LockAnalysis::LockSpan lspan1 = lockana->getSpanfromCxtLock(*it1);
//            /// exist lock span, n1 is head;
//            if (isHeadofSpan(n1, lspan1))
//                n1ishead = true;
//        }
//        if (n2istail && n1ishead)
//            addTDEdges(n2->getId(), n1->getId(), pts);
//
//    } else {
//        addTDEdges(n1->getId(), n2->getId(), pts);
//        addTDEdges(n2->getId(), n1->getId(), pts);
//    }
}

isHeadofSpan() [1/3]

bool MTASVFGBuilder::isHeadofSpan ( const StmtSVFGNode *  n )

private

whether for all lockspans that n belongs to, n is the first write. strong constraints but scalable

Definition at line 243 of file FSMPTA.cpp.

{
    if (headmap.find(n) != headmap.end())
        return headmap[n];
 
    SVFGNodeIDSet prev = getPrevNodes(n);
 
    for (SVFGNodeIDSet::iterator it = prev.begin(), eit = prev.end(); it != eit; ++it)
    {
        assert(SVFUtil::isa<StoreSVFGNode>(svfg->getSVFGNode(*it)) && "prev is not a store node");
        const StmtSVFGNode* prevNode = SVFUtil::dyn_cast<StmtSVFGNode>(svfg->getSVFGNode(*it));
        const SVFInstruction* prevIns = prevNode->getInst();
 
        if (lockana->isInSameSpan(prevIns, n->getInst()))
        {
            headmap[n]=false;
            return false;
        }
    }
    headmap[n]=true;
    return true;
}

isHeadofSpan() [2/3]

bool MTASVFGBuilder::isHeadofSpan ( const StmtSVFGNode *  n, InstSet  mergespan  )

private

Definition at line 225 of file FSMPTA.cpp.

{
 
    SVFGNodeIDSet prev = getPrevNodes(n);
 
    for (SVFGNodeIDSet::iterator it = prev.begin(), eit = prev.end(); it != eit; ++it)
    {
        assert (SVFUtil::isa<StoreSVFGNode>(svfg->getSVFGNode(*it)) && "prev is not a store node");
        const StmtSVFGNode* prevNode = SVFUtil::dyn_cast<StmtSVFGNode>(svfg->getSVFGNode(*it));
        const SVFInstruction* prevIns = prevNode->getInst();
        if (mergespan.find(prevIns)!=mergespan.end())
            return false;
    }
    return true;
}

isHeadofSpan() [3/3]

bool MTASVFGBuilder::isHeadofSpan ( const StmtSVFGNode *  n, LockAnalysis::LockSpan  lspan  )

private

whether is a first write in the lock span.

Definition at line 201 of file FSMPTA.cpp.

{
    SVFGNodeLockSpan pair(n,lspan);
    if (pairheadmap.find(pair) != pairheadmap.end())
        return pairheadmap[pair];
 
    SVFGNodeIDSet prev = getPrevNodes(n);
 
    for (SVFGNodeIDSet::iterator it = prev.begin(), eit = prev.end(); it != eit; ++it)
    {
        assert (SVFUtil::isa<StoreSVFGNode>(svfg->getSVFGNode(*it)) && "prev is not a store node");
        const StmtSVFGNode* prevNode = SVFUtil::dyn_cast<StmtSVFGNode>(svfg->getSVFGNode(*it));
        const SVFInstruction* prevIns = prevNode->getInst();
 
        if (lockana->hasOneCxtInLockSpan(prevIns, lspan))
        {
            pairheadmap[pair]=false;
            return false;
        }
    }
    pairheadmap[pair]=true;
    return true;
}

isTailofSpan() [1/3]

bool MTASVFGBuilder::isTailofSpan ( const StmtSVFGNode *  n )

private

whether for all lockspans that n belongs to, n is the last write. strong constraints but scalable

Definition at line 316 of file FSMPTA.cpp.

{
    assert(SVFUtil::isa<StoreSVFGNode>(n) && "Node is not a store node");
 
    if (tailmap.find(n) != tailmap.end())
        return tailmap[n];
 
    SVFGNodeIDSet succ = getSuccNodes(n);
 
    for (SVFGNodeIDSet::iterator it = succ.begin(), eit = succ.end(); it != eit; ++it)
    {
        assert((SVFUtil::isa<StoreSVFGNode, LoadSVFGNode>(svfg->getSVFGNode(*it))) && "succ is not a store/load node");
        if (SVFUtil::isa<LoadSVFGNode>(svfg->getSVFGNode(*it)))
            continue;
 
        const StmtSVFGNode* succNode = SVFUtil::dyn_cast<StmtSVFGNode>(svfg->getSVFGNode(*it));
        const SVFInstruction* succIns = succNode->getInst();
 
        if (lockana->isInSameSpan(succIns, n->getInst()))
        {
            tailmap[n] = false;
            return false;
        }
    }
    tailmap[n]=true;
    return true;
}

isTailofSpan() [2/3]

bool MTASVFGBuilder::isTailofSpan ( const StmtSVFGNode *  n, InstSet  mergespan  )

private

Definition at line 266 of file FSMPTA.cpp.

{
 
    SVFGNodeIDSet succ = getSuccNodes(n);
 
    for (SVFGNodeIDSet::iterator it = succ.begin(), eit = succ.end(); it != eit; ++it)
    {
        assert((SVFUtil::isa<StoreSVFGNode, LoadSVFGNode>(svfg->getSVFGNode(*it))) &&
               "succ is not a store/load node");
        const StmtSVFGNode* succNode = SVFUtil::dyn_cast<StmtSVFGNode>(svfg->getSVFGNode(*it));
        const SVFInstruction* succIns = succNode->getInst();
 
        if (mergespan.find(succIns)!=mergespan.end())
            return false;
    }
    return true;
}

isTailofSpan() [3/3]

bool MTASVFGBuilder::isTailofSpan ( const StmtSVFGNode *  n, LockAnalysis::LockSpan  lspan  )

private

whether is a last write in the lock span.

Definition at line 285 of file FSMPTA.cpp.

{
    assert(SVFUtil::isa<StoreSVFGNode>(n) && "Node is not a store node");
 
    SVFGNodeLockSpan pair(n,lspan);
    if (pairtailmap.find(pair) != pairtailmap.end())
        return pairtailmap[pair];
 
    SVFGNodeIDSet succ = getSuccNodes(n);
    for (SVFGNodeIDSet::iterator it = succ.begin(), eit = succ.end(); it != eit; ++it)
    {
        assert((SVFUtil::isa<StoreSVFGNode, LoadSVFGNode>(svfg->getSVFGNode(*it))) &&
               "succ is not a store/load node");
        if (SVFUtil::isa<LoadSVFGNode>(svfg->getSVFGNode(*it)))
            continue;
        const StmtSVFGNode* succNode = SVFUtil::dyn_cast<StmtSVFGNode>(svfg->getSVFGNode(*it));
        const SVFInstruction* succIns = succNode->getInst();
 
        if (lockana->hasOneCxtInLockSpan(succIns, lspan))
        {
            pairtailmap[pair]=false;
            return false;
        }
    }
    pairtailmap[pair]=true;
    return true;
}

mergeSpan()

void MTASVFGBuilder::mergeSpan ( NodeBS  comlocks, InstSet &  res  )

private

Definition at line 647 of file FSMPTA.cpp.

{
//    for (NodeBS::iterator it = comlocks.begin(), ie = comlocks.end(); it != ie; ++it) {
//        LockAnalysis::LockSpan lspan = lockana->getSpanfromCxtLock(*it);
//        for (LockAnalysis::LockSpan::const_iterator cts = lspan.begin(), ects = lspan.end(); cts!=ects; ++cts) {
//            res.insert((*cts).getStmt());
//        }
//    }
}

performAddingMHPEdges()

void MTASVFGBuilder::performAddingMHPEdges ( )

private

perform adding/removing MHP Edges in value flow graph

Definition at line 113 of file FSMPTA.cpp.

{
    MTASVFGBuilder::numOfNewSVFGEdges = recordedges.size();
    while (!recordedges.empty())
    {
        std::pair<NodeID, NodeID> edgepair = *recordedges.begin();
        PointsTo pts = edge2pts[edgepair];
        recordedges.erase(recordedges.begin());
        addTDEdges(edgepair.first, edgepair.second, pts);
    }
}

performRemovingMHPEdges()

void MTASVFGBuilder::performRemovingMHPEdges ( )

private

Definition at line 145 of file FSMPTA.cpp.

{
    while (!recordedges.empty())
    {
        std::pair<NodeID, NodeID> edgepair = *recordedges.begin();
        recordedges.erase(recordedges.begin());
 
        PointsTo remove_pts = edge2pts[edgepair];
        const StmtSVFGNode*  n1 = SVFUtil::cast<StmtSVFGNode>(svfg->getSVFGNode(edgepair.first));
        const StmtSVFGNode*  n2 = SVFUtil::cast<StmtSVFGNode>(svfg->getSVFGNode(edgepair.second));
 
        assert (n1&&n2 && "one node of removed pair is null");
        assert (n1->hasOutgoingEdge() && "n1 doesn't have out edge");
        assert (n2->hasIncomingEdge() && "n2 doesn't have in edge");
 
        Set<SVFGEdge*> removededges;
        for (SVFGEdge::SVFGEdgeSetTy::iterator iter = n1->OutEdgeBegin(); iter != n1->OutEdgeEnd(); ++iter)
        {
            SVFGEdge* edge = *iter;
            if (edge->isIndirectVFGEdge() && (edge->getDstNode()==n2))
            {
                IndirectSVFGEdge* e = SVFUtil::cast<IndirectSVFGEdge>(edge);
                const NodeBS& pts = e->getPointsTo();
                for (PointsTo::iterator o = remove_pts.begin(), eo = remove_pts.end(); o != eo; ++o)
                {
                    if (const_cast<NodeBS&>(pts).test(*o))
                    {
                        const_cast<NodeBS&>(pts).reset(*o);
                        MTASVFGBuilder::numOfRemovedPTS ++;
                    }
                }
 
                if (0 == e->getPointsTo().count())
                {
                    removededges.insert(edge);
                }
            }
        }
 
        while(!removededges.empty())
        {
            SVFGEdge* edge = *removededges.begin();
            removededges.erase(removededges.begin());
            svfg->removeSVFGEdge(edge);
            DBOUT(DMTA,outs()<<"Read Precision remove: "<<edge->getSrcID()<<" -> "<<edge->getDstID()<<"\n");
            MTASVFGBuilder::numOfRemovedSVFGEdges++;
        }
    }
}

readPrecision()

void MTASVFGBuilder::readPrecision ( )

private

For o, n2-o->n1, n1 and n2 are write. Foreach n3:n1->n3, n2->n3; then remove n2->n1.

Definition at line 658 of file FSMPTA.cpp.

{
 
    recordedges.clear();
    edge2pts.clear();
 
    for (SVFGNodeSet::iterator it1 = stnodeSet.begin(), eit1 = stnodeSet.end(); it1 != eit1; ++it1)
    {
        const StmtSVFGNode* n1 = SVFUtil::cast<StmtSVFGNode>(*it1);
 
        for (SVFGEdge::SVFGEdgeSetTy::iterator iter = n1->InEdgeBegin(); iter != n1->InEdgeEnd(); ++iter)
        {
            SVFGEdge* edge = *iter;
            if (edge->isIndirectVFGEdge() && SVFUtil::isa<StoreSVFGNode>(edge->getSrcNode()))
            {
                const StmtSVFGNode* n2 = SVFUtil::cast<StmtSVFGNode>(edge->getSrcNode());
 
                IndirectSVFGEdge* e = SVFUtil::cast<IndirectSVFGEdge>(edge);
                NodeBS pts = e->getPointsTo();
                PointsTo remove_pts;
 
                for (NodeBS::iterator o = pts.begin(), eo = pts.end(); o != eo; ++o)
                {
                    SVFGNodeIDSet succ1 = getSuccNodes(n1, *o);
                    SVFGNodeIDSet succ2 = getSuccNodes(n2, *o);
 
                    bool remove = true;
                    for (SVFGNodeIDSet::iterator sn1 = succ1.begin(), esn1 = succ1.end(); sn1 != esn1; sn1++)
                    {
                        if (!succ2.test(*sn1))
                        {
                            remove = false;
                            break;
                        }
                    }
                    if (remove)
                        remove_pts.set(*o);
                }
 
                if (remove_pts.count())
                    recordRemovingEdge(n2->getId(), n1->getId(), remove_pts);
            }
        }
    }
 
    performRemovingMHPEdges();
}

recordAddingEdge()

bool MTASVFGBuilder::recordAddingEdge ( NodeID  id1, NodeID  id2, PointsTo  pts  )

private

Definition at line 103 of file FSMPTA.cpp.

{
    return recordEdge(id1, id2, pts);
}

recordEdge()

bool MTASVFGBuilder::recordEdge ( NodeID  id1, NodeID  id2, PointsTo  pts  )

private

Record edges.

Definition at line 88 of file FSMPTA.cpp.

{
    NodeIDPair pair = std::make_pair(id1, id2);
    if (recordedges.find(pair) == recordedges.end())
    {
        recordedges.insert(pair);
        edge2pts[pair] = pts;
        return true;
    }
    else
    {
        edge2pts[pair] |= pts;
    }
    return false;
}

recordRemovingEdge()

bool MTASVFGBuilder::recordRemovingEdge ( NodeID  id1, NodeID  id2, PointsTo  pts  )

private

Definition at line 108 of file FSMPTA.cpp.

{
    return recordEdge(id1, id2, pts);
}

Member Data Documentation

ADDEDGE_ALLOPT

const u32_t SVF::MTASVFGBuilder::ADDEDGE_ALLOPT = 2

staticprivate

Definition at line 189 of file FSMPTA.h.

ADDEDGE_NOALIAS

const u32_t SVF::MTASVFGBuilder::ADDEDGE_NOALIAS = 4

staticprivate

Definition at line 191 of file FSMPTA.h.

ADDEDGE_NOEDGE

const u32_t SVF::MTASVFGBuilder::ADDEDGE_NOEDGE = 0

staticprivate

Definition at line 187 of file FSMPTA.h.

ADDEDGE_NOLOCK

const u32_t SVF::MTASVFGBuilder::ADDEDGE_NOLOCK = 5

staticprivate

Definition at line 192 of file FSMPTA.h.

ADDEDGE_NOMHP

const u32_t SVF::MTASVFGBuilder::ADDEDGE_NOMHP = 3

staticprivate

Definition at line 190 of file FSMPTA.h.

ADDEDGE_NONSPARSE

const u32_t SVF::MTASVFGBuilder::ADDEDGE_NONSPARSE = 1

staticprivate

Definition at line 188 of file FSMPTA.h.

ADDEDGE_NORP

const u32_t SVF::MTASVFGBuilder::ADDEDGE_NORP = 6

staticprivate

Definition at line 193 of file FSMPTA.h.

edge2pts

Map<NodeIDPair, PointsTo> SVF::MTASVFGBuilder::edge2pts

private

Definition at line 174 of file FSMPTA.h.

headmap

Map<const StmtSVFGNode*, bool> SVF::MTASVFGBuilder::headmap

private

Definition at line 180 of file FSMPTA.h.

ldnodeSet

SVFGNodeSet SVF::MTASVFGBuilder::ldnodeSet

private

Definition at line 167 of file FSMPTA.h.

lockana

LockAnalysis* SVF::MTASVFGBuilder::lockana

private

Definition at line 171 of file FSMPTA.h.

mhp

MHP* SVF::MTASVFGBuilder::mhp

private

MHP class.

Definition at line 170 of file FSMPTA.h.

numOfNewSVFGEdges

u32_t MTASVFGBuilder::numOfNewSVFGEdges = 0

static

Number of newly added SVFG edges.

Definition at line 120 of file FSMPTA.h.

numOfRemovedPTS

u32_t MTASVFGBuilder::numOfRemovedPTS = 0

static

Definition at line 122 of file FSMPTA.h.

numOfRemovedSVFGEdges

u32_t MTASVFGBuilder::numOfRemovedSVFGEdges = 0

static

Definition at line 121 of file FSMPTA.h.

pairheadmap

PairToBoolMap SVF::MTASVFGBuilder::pairheadmap

private

Definition at line 183 of file FSMPTA.h.

pairtailmap

PairToBoolMap SVF::MTASVFGBuilder::pairtailmap

private

Definition at line 184 of file FSMPTA.h.

prevset

Map<const StmtSVFGNode*, SVFGNodeIDSet> SVF::MTASVFGBuilder::prevset

private

Definition at line 177 of file FSMPTA.h.

recordedges

Set<NodeIDPair> SVF::MTASVFGBuilder::recordedges

private

Definition at line 173 of file FSMPTA.h.

stnodeSet

SVFGNodeSet SVF::MTASVFGBuilder::stnodeSet

private

all stores/loads SVFGNodes

Definition at line 166 of file FSMPTA.h.

succset

Map<const StmtSVFGNode*, SVFGNodeIDSet> SVF::MTASVFGBuilder::succset

private

Definition at line 178 of file FSMPTA.h.

tailmap

Map<const StmtSVFGNode*, bool> SVF::MTASVFGBuilder::tailmap

private

Definition at line 181 of file FSMPTA.h.

---

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

• /home/runner/work/SVF/SVF/svf/include/MTA/FSMPTA.h
• /home/runner/work/SVF/SVF/svf/lib/MTA/FSMPTA.cpp