SVF::PCG Class Reference

#include <PCG.h>

Public Types
typedef Set< const SVFFunction * >	FunSet
typedef std::vector< const SVFFunction * >	FunVec
typedef Set< const SVFInstruction * >	CallInstSet
typedef FIFOWorkList< const SVFFunction * >	FunWorkList
typedef FIFOWorkList< const SVFBasicBlock * >	BBWorkList

Public Member Functions
	PCG (PointerAnalysis *an)
	Constructor. More...
virtual bool	analyze ()
	We start the pass here. More...
virtual	~PCG ()
	Destructor. More...
CallICFGNode *	getCallICFGNode (const SVFInstruction *inst)
virtual bool	mayHappenInParallel (const SVFInstruction *i1, const SVFInstruction *i2) const
	Interface to query whether two function may happen-in-parallel. More...
bool	mayHappenInParallelBetweenFunctions (const SVFFunction *fun1, const SVFFunction *fun2) const
const FunSet &	getMHPFunctions () const
void	initFromThreadAPI (SVFModule *module)
	Initialize spawner and spawnee sets with threadAPI. More...
void	inferFromCallGraph ()
	Infer spawner spawnee and followers sets by traversing on callGraph. More...
void	collectSpawners ()
void	collectSpawnees ()
void	collectFollowers ()
void	identifyFollowers ()
const FunSet &	getSpawners () const
	Get spawners/spawnees/followers. More...
const FunSet &	getSpawnees () const
const FunSet &	getFollowers () const
FunSet::const_iterator	spawnersBegin (const SVFFunction *fun) const
	Iterators for thread properties of a procedure. More...
FunSet::const_iterator	spawnersEnd (const SVFFunction *fun) const
FunSet::const_iterator	spawneesBegin (const SVFFunction *fun) const
FunSet::const_iterator	spawneesEnd (const SVFFunction *fun) const
FunSet::const_iterator	followersBegin (const SVFFunction *fun) const
FunSet::const_iterator	followersEnd (const SVFFunction *fun) const
void	interferenceAnalysis ()
	Thread interferenceAnalysis. More...
void	printResults ()
	Print analysis results. More...
void	printTDFuns ()

Private Member Functions
bool	isSpawnerFun (const SVFFunction *fun) const
	Add/Get methods for thread properties of a procedure. More...
bool	isSpawneeFun (const SVFFunction *fun) const
bool	isFollowerFun (const SVFFunction *fun) const
bool	addSpawnerFun (const SVFFunction *fun)
bool	addSpawneeFun (const SVFFunction *fun)
bool	addFollowerFun (const SVFFunction *fun)
bool	addSpawnsite (const SVFInstruction *callInst)
	Add/search spawn sites which directly or indirectly create a thread. More...
bool	isSpawnsite (const SVFInstruction *callInst)
CallInstSet::const_iterator	spawnSitesBegin () const
	Spawn sites iterators. More...
CallInstSet::const_iterator	spawnSitesEnd () const

Private Attributes
FunSet	spawners
FunSet	spawnees
FunSet	followers
FunSet	mhpfuns
PTACallGraph *	callgraph
SVFModule *	mod
PointerAnalysis *	pta
ThreadAPI *	tdAPI
CallInstSet	spawnCallSites
	Callsites direct or Indirect call a function which spawn a thread. More...

Detailed Description

This class serves as a base may-happen in parallel analysis for multithreaded program It distinguish thread spawner, spawnee, follower in procedure level by modeling pthread_create, pthread_join, pthread_exit, pthread_cancel synchronization operations

Definition at line 50 of file PCG.h.

Member Typedef Documentation

BBWorkList

typedef FIFOWorkList<const SVFBasicBlock*> SVF::PCG::BBWorkList

Definition at line 58 of file PCG.h.

CallInstSet

typedef Set<const SVFInstruction*> SVF::PCG::CallInstSet

Definition at line 56 of file PCG.h.

FunSet

typedef Set<const SVFFunction*> SVF::PCG::FunSet

Definition at line 54 of file PCG.h.

FunVec

typedef std::vector<const SVFFunction*> SVF::PCG::FunVec

Definition at line 55 of file PCG.h.

FunWorkList

typedef FIFOWorkList<const SVFFunction*> SVF::PCG::FunWorkList

Definition at line 57 of file PCG.h.

Constructor & Destructor Documentation

PCG()

SVF::PCG::PCG ( PointerAnalysis *  an )

inline

Constructor.

Definition at line 133 of file PCG.h.

                             : pta(an)
    {
        mod = pta->getModule();
        tdAPI=ThreadAPI::getThreadAPI();
        callgraph = pta->getPTACallGraph();
    }

~PCG()

virtual SVF::PCG::~PCG ( )

inlinevirtual

Destructor.

Definition at line 144 of file PCG.h.

    {
    }

Member Function Documentation

addFollowerFun()

bool SVF::PCG::addFollowerFun ( const SVFFunction *  fun )

inlineprivate

Definition at line 99 of file PCG.h.

    {
        if (fun->isDeclaration())
            return false;
        return followers.insert(fun).second;
    }

addSpawneeFun()

bool SVF::PCG::addSpawneeFun ( const SVFFunction *  fun )

inlineprivate

Definition at line 93 of file PCG.h.

    {
        if (fun->isDeclaration())
            return false;
        return spawnees.insert(fun).second;
    }

addSpawnerFun()

bool SVF::PCG::addSpawnerFun ( const SVFFunction *  fun )

inlineprivate

Definition at line 87 of file PCG.h.

    {
        if (fun->isDeclaration())
            return false;
        return spawners.insert(fun).second;
    }

addSpawnsite()

bool SVF::PCG::addSpawnsite ( const SVFInstruction *  callInst )

inlineprivate

Add/search spawn sites which directly or indirectly create a thread.

Definition at line 109 of file PCG.h.

    {
        return spawnCallSites.insert(callInst).second;
    }

analyze()

bool PCG::analyze ( )

virtual

We start the pass here.

Whether two functions may happen in parallel

Definition at line 49 of file PCG.cpp.

{
 
    //callgraph = new PTACallGraph(mod);
 
    DBOUT(DMTA, outs() << pasMsg("Starting MHP analysis\n"));
 
    initFromThreadAPI(mod);
 
    inferFromCallGraph();
 
    //interferenceAnalysis();
 
    //if (Options::TDPrint()) {
    //printResults();
    //tdAPI->performAPIStat(mod);
    //}
    return false;
}

collectFollowers()

void PCG::collectFollowers

(

)

collect follower procedures which may be called after pthread_create is invoked directly or indirectly a procedure which is called from a follower is also a follower.

identify initial followers

find all the followers recursively on call graph

Definition at line 265 of file PCG.cpp.

{
 
    identifyFollowers();
 
    FunWorkList worklist;
    for (FunSet::iterator it = followers.begin(), eit = followers.end(); it != eit; ++it)
    {
        worklist.push(*it);
    }
    while (!worklist.empty())
    {
        const SVFFunction* svffun = worklist.pop();
        PTACallGraphNode* funNode = callgraph->getCallGraphNode(svffun);
        for (PTACallGraphNode::const_iterator it = funNode->OutEdgeBegin(), eit = funNode->OutEdgeEnd(); it != eit;
                ++it)
        {
            const SVFFunction* caller = (*it)->getDstNode()->getFunction();
            if (isFollowerFun(caller) == false)
            {
                worklist.push(caller);
                addFollowerFun(caller);
            }
        }
    }
}

collectSpawnees()

void PCG::collectSpawnees

(

)

spawnee: given a spawnee, all its callees on callgraph are spawnees

find all the spawnees recursively on call graph

Definition at line 187 of file PCG.cpp.

{
 
    FunWorkList worklist;
    for (FunSet::iterator it = spawnees.begin(), eit = spawnees.end(); it != eit; ++it)
    {
        worklist.push(*it);
    }
    while (!worklist.empty())
    {
        const SVFFunction* svffun = worklist.pop();
        PTACallGraphNode* funNode = callgraph->getCallGraphNode(svffun);
        for (PTACallGraphNode::const_iterator it = funNode->OutEdgeBegin(), eit = funNode->OutEdgeEnd(); it != eit;
                ++it)
        {
            const SVFFunction* caller = (*it)->getDstNode()->getFunction();
            if (isSpawneeFun(caller) == false)
            {
                worklist.push(caller);
                addSpawneeFun(caller);
            }
        }
    }
}

collectSpawners()

void PCG::collectSpawners

(

)

spawner: given a spawner, all its callers on callgraph are spawners

find all the spawners recursively on call graph

add all the callsites from callers to callee (spawner) as a spawn site.

Definition at line 146 of file PCG.cpp.

{
 
    FunWorkList worklist;
    for (FunSet::iterator it = spawners.begin(), eit = spawners.end(); it != eit; ++it)
    {
        worklist.push(*it);
    }
    while (!worklist.empty())
    {
        const SVFFunction* svffun = worklist.pop();
        PTACallGraphNode* funNode = callgraph->getCallGraphNode(svffun);
        for (PTACallGraphNode::const_iterator it = funNode->InEdgeBegin(), eit = funNode->InEdgeEnd(); it != eit;
                ++it)
        {
            PTACallGraphEdge* callEdge = (*it);
            const SVFFunction* caller = callEdge->getSrcNode()->getFunction();
            if (isSpawnerFun(caller) == false)
            {
                worklist.push(caller);
                addSpawnerFun(caller);
            }
            for (PTACallGraphEdge::CallInstSet::const_iterator dit = callEdge->directCallsBegin(), deit =
                        callEdge->directCallsEnd(); dit != deit; ++dit)
            {
                addSpawnsite((*dit)->getCallSite());
            }
            for (PTACallGraphEdge::CallInstSet::const_iterator dit = callEdge->indirectCallsBegin(), deit =
                        callEdge->indirectCallsEnd(); dit != deit; ++dit)
            {
                addSpawnsite((*dit)->getCallSite());
            }
        }
    }
}

followersBegin()

FunSet::const_iterator SVF::PCG::followersBegin ( const SVFFunction *  fun ) const

inline

Definition at line 206 of file PCG.h.

    {
        return followers.begin();
    }

followersEnd()

FunSet::const_iterator SVF::PCG::followersEnd ( const SVFFunction *  fun ) const

inline

Definition at line 210 of file PCG.h.

    {
        return followers.end();
    }

getCallICFGNode()

CallICFGNode* SVF::PCG::getCallICFGNode ( const SVFInstruction *  inst )

inline

Definition at line 148 of file PCG.h.

    {
        return pta->getICFG()->getCallICFGNode(inst);
    }

getFollowers()

const FunSet& SVF::PCG::getFollowers ( ) const

inline

Definition at line 182 of file PCG.h.

    {
        return followers;
    }

getMHPFunctions()

const FunSet& SVF::PCG::getMHPFunctions ( ) const

inline

Definition at line 155 of file PCG.h.

    {
        return mhpfuns;
    }

getSpawnees()

const FunSet& SVF::PCG::getSpawnees ( ) const

inline

Definition at line 178 of file PCG.h.

    {
        return spawnees;
    }

getSpawners()

const FunSet& SVF::PCG::getSpawners ( ) const

inline

Get spawners/spawnees/followers.

Definition at line 174 of file PCG.h.

    {
        return spawners;
    }

identifyFollowers()

void PCG::identifyFollowers

(

)

Identify initial followers a procedure whose callsite lies in a control flow path that starts just after a spawner's callsite

Definition at line 217 of file PCG.cpp.

{
 
    for (CallInstSet::const_iterator sit = spawnSitesBegin(), esit = spawnSitesEnd(); sit != esit; ++sit)
    {
        const SVFInstruction* inst = *sit;
        BBWorkList bb_worklist;
        Set<const SVFBasicBlock*> visitedBBs;
        bb_worklist.push(inst->getParent());
        while (!bb_worklist.empty())
        {
            const SVFBasicBlock* bb = bb_worklist.pop();
            for (SVFBasicBlock::const_iterator it = bb->begin(), eit = bb->end(); it != eit; ++it)
            {
                const SVFInstruction* inst = *it;
                // mark the callee of this callsite as follower
                // if this is an call/invoke instruction but not a spawn site
                if ((SVFUtil::isCallSite(inst)) && !isSpawnsite(inst) && !SVFUtil::isIntrinsicInst(inst))
                {
                    CallICFGNode* cbn = getCallICFGNode(inst);
                    if (callgraph->hasCallGraphEdge(cbn))
                    {
                        for (PTACallGraph::CallGraphEdgeSet::const_iterator cgIt = callgraph->getCallEdgeBegin(cbn),
                                ecgIt = callgraph->getCallEdgeEnd(cbn); cgIt != ecgIt; ++cgIt)
                        {
                            const PTACallGraphEdge* edge = *cgIt;
                            addFollowerFun(edge->getDstNode()->getFunction());
                        }
                    }
                }
            }
            for (const SVFBasicBlock* svf_scc_bb : bb->getSuccessors())
            {
                if (visitedBBs.count(svf_scc_bb) == 0)
                {
                    visitedBBs.insert(svf_scc_bb);
                    bb_worklist.push(svf_scc_bb);
                }
            }
        }
    }
 
}

inferFromCallGraph()

void PCG::inferFromCallGraph

(

)

Infer spawner spawnee and followers sets by traversing on callGraph.

Infer spawners and spawnees from call graph. The inference are recursively done spawners: procedures may create a thread and return with the created thread still running spawnees: procedures may be executed as a spawned thread followers: procedures may be invoked by a thread after the thread returns from a spawner (procedure may be called after pthread_creat is called).

Definition at line 133 of file PCG.cpp.

{
 
    collectSpawners();
 
    collectSpawnees();
 
    collectFollowers();
}

initFromThreadAPI()

void PCG::initFromThreadAPI

(

SVFModule *

module

)

Initialize spawner and spawnee sets with threadAPI.

Initialize thread spawners and spawnees from threadAPI functions a procedure is a spawner if it creates a thread and the created thread is still existent on its return a procedure is a spawnee if it is created by fork call

TODO: handle indirect call here for the fork Fun

Definition at line 96 of file PCG.cpp.

{
    for (const SVFFunction* fun : module->getFunctionSet())
    {
        for (const SVFBasicBlock* svfbb : fun->getBasicBlockList())
        {
            for (const SVFInstruction* inst : svfbb->getInstructionList())
            {
                if (tdAPI->isTDFork(inst))
                {
                    const SVFValue* forkVal = tdAPI->getForkedFun(inst);
                    if (const SVFFunction* svForkfun = SVFUtil::dyn_cast<SVFFunction>(forkVal))
                    {
                        addSpawnsite(inst);
                        spawners.insert(fun);
                        spawnees.insert(svForkfun);
                    }
                    else
                    {
                        writeWrnMsg("pthread create");
                        outs() << inst->toString() << "\n";
                        writeWrnMsg("invoke spawnee indirectly");
                    }
                }
            }
        }
    }
}

interferenceAnalysis()

void PCG::interferenceAnalysis

(

)

Thread interferenceAnalysis.

Thread interference analysis, Suppose we have a undirected graph G = {F,E,I} F denotes procedure, E represents interference edge (x,y) \in E, x \in F, y \in F means execution of x in one thread may overlap execution of y in another thread I(x,y) is a set of memory locations for this interference edge

Definition at line 302 of file PCG.cpp.

{
 
//  DBOUT(DMTA, outs() << pasMsg("Starting Race Detection\n"));
 
    PCG::FunVec worklist;
    for (SVFModule::const_iterator F = mod->begin(), E = mod->end(); F != E; ++F)
    {
        const SVFFunction* fun = *F;
        if (isExtCall(fun))
            continue;
        worklist.push_back(fun);
    }
 
    while (!worklist.empty())
    {
        const SVFFunction* fun1 = worklist.back();
        worklist.pop_back();
 
        bool ismhpfun = false;
        for (PCG::FunVec::iterator it = worklist.begin(), eit = worklist.end(); it != eit; ++it)
        {
            const SVFFunction* fun2 = *it;
            if (mayHappenInParallelBetweenFunctions(fun1, fun2))
            {
                ismhpfun = true;
                mhpfuns.insert(fun2);
            }
        }
        if (ismhpfun)
        {
            mhpfuns.insert(fun1);
        }
    }
}

isFollowerFun()

bool SVF::PCG::isFollowerFun ( const SVFFunction *  fun ) const

inlineprivate

Definition at line 83 of file PCG.h.

    {
        return followers.find(fun) != followers.end();
    }

isSpawneeFun()

bool SVF::PCG::isSpawneeFun ( const SVFFunction *  fun ) const

inlineprivate

Definition at line 79 of file PCG.h.

    {
        return spawnees.find(fun) != spawnees.end();
    }

isSpawnerFun()

bool SVF::PCG::isSpawnerFun ( const SVFFunction *  fun ) const

inlineprivate

Add/Get methods for thread properties of a procedure.

Definition at line 75 of file PCG.h.

    {
        return spawners.find(fun) != spawners.end();
    }

isSpawnsite()

bool SVF::PCG::isSpawnsite ( const SVFInstruction *  callInst )

inlineprivate

Definition at line 113 of file PCG.h.

    {
        return spawnCallSites.find(callInst) != spawnCallSites.end();
    }

mayHappenInParallel()

bool PCG::mayHappenInParallel ( const SVFInstruction *  i1, const SVFInstruction *  i2  ) const

virtual

Interface to query whether two function may happen-in-parallel.

Definition at line 83 of file PCG.cpp.

{
    const SVFFunction* fun1 = i1->getFunction();
    const SVFFunction* fun2 = i2->getFunction();
    return mayHappenInParallelBetweenFunctions(fun1, fun2);
}

mayHappenInParallelBetweenFunctions()

bool PCG::mayHappenInParallelBetweenFunctions	(	const SVFFunction *	fun1,
		const SVFFunction *	fun2
	)		const

Definition at line 69 of file PCG.cpp.

{
    // if neither of functions are spawnees, then they won't happen in parallel
    if (isSpawneeFun(fun1) == false && isSpawneeFun(fun2) == false)
        return false;
    // if there exit one of the function are not spawner, spawnee or follower, then they won't happen in parallel
    if (isSpawnerFun(fun1) == false && isSpawneeFun(fun1) == false && isFollowerFun(fun1) == false)
        return false;
    if (isSpawnerFun(fun2) == false && isSpawneeFun(fun2) == false && isFollowerFun(fun2) == false)
        return false;
 
    return true;
}

printResults()

void PCG::printResults

(

)

Print analysis results.

Print analysis results

Definition at line 341 of file PCG.cpp.

{
 
    printTDFuns();
}

printTDFuns()

void PCG::printTDFuns

(

)

Print Thread sensitive properties for each function

Definition at line 350 of file PCG.cpp.

{
 
    for (SVFModule::const_iterator fi = mod->begin(), efi = mod->end(); fi != efi; ++fi)
    {
        const SVFFunction* fun = (*fi);
        if (fun->isDeclaration())
            continue;
 
        std::string isSpawner = isSpawnerFun(fun) ? " SPAWNER " : "";
        std::string isSpawnee = isSpawneeFun(fun) ? " CHILDREN " : "";
        std::string isFollower = isFollowerFun(fun) ? " FOLLOWER " : "";
        outs() << fun->getName() << " [" << isSpawner << isSpawnee << isFollower << "]\n";
    }
}

spawneesBegin()

FunSet::const_iterator SVF::PCG::spawneesBegin ( const SVFFunction *  fun ) const

inline

Definition at line 198 of file PCG.h.

    {
        return spawnees.begin();
    }

spawneesEnd()

FunSet::const_iterator SVF::PCG::spawneesEnd ( const SVFFunction *  fun ) const

inline

Definition at line 202 of file PCG.h.

    {
        return spawnees.end();
    }

spawnersBegin()

FunSet::const_iterator SVF::PCG::spawnersBegin ( const SVFFunction *  fun ) const

inline

Iterators for thread properties of a procedure.

Definition at line 190 of file PCG.h.

    {
        return spawners.begin();
    }

spawnersEnd()

FunSet::const_iterator SVF::PCG::spawnersEnd ( const SVFFunction *  fun ) const

inline

Definition at line 194 of file PCG.h.

    {
        return spawners.end();
    }

spawnSitesBegin()

CallInstSet::const_iterator SVF::PCG::spawnSitesBegin ( ) const

inlineprivate

Spawn sites iterators.

Definition at line 120 of file PCG.h.

    {
        return spawnCallSites.begin();
    }

spawnSitesEnd()

CallInstSet::const_iterator SVF::PCG::spawnSitesEnd ( ) const

inlineprivate

Definition at line 124 of file PCG.h.

    {
        return spawnCallSites.end();
    }

Member Data Documentation

callgraph

PTACallGraph* SVF::PCG::callgraph

private

Definition at line 65 of file PCG.h.

followers

FunSet SVF::PCG::followers

private

Definition at line 63 of file PCG.h.

mhpfuns

FunSet SVF::PCG::mhpfuns

private

Definition at line 64 of file PCG.h.

mod

SVFModule* SVF::PCG::mod

private

Definition at line 66 of file PCG.h.

pta

PointerAnalysis* SVF::PCG::pta

private

Definition at line 67 of file PCG.h.

spawnCallSites

CallInstSet SVF::PCG::spawnCallSites

private

Callsites direct or Indirect call a function which spawn a thread.

Definition at line 71 of file PCG.h.

spawnees

FunSet SVF::PCG::spawnees

private

Definition at line 62 of file PCG.h.

spawners

FunSet SVF::PCG::spawners

private

Definition at line 61 of file PCG.h.

tdAPI

ThreadAPI* SVF::PCG::tdAPI

private

Definition at line 68 of file PCG.h.

---

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

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