SVF::MHP Class Reference

#include <MHP.h>

Public Types
typedef Set< const FunObjVar * >	FunSet
typedef FIFOWorkList< CxtThreadStmt >	CxtThreadStmtWorkList
typedef Set< CxtThreadStmt >	CxtThreadStmtSet
typedef Map< CxtThreadStmt, NodeBS >	ThreadStmtToThreadInterleav
typedef Map< const ICFGNode *, CxtThreadStmtSet >	InstToThreadStmtSetMap
typedef SVFLoopAndDomInfo::LoopBBs	LoopBBs
typedef Set< CxtStmt >	LockSpan
typedef std::pair< const FunObjVar *, const FunObjVar * >	FuncPair
typedef Map< FuncPair, bool >	FuncPairToBool

Public Member Functions
	MHP (TCT *t)
	Constructor.
virtual	~MHP ()
	Destructor.
void	analyze ()
	Start analysis here.
void	analyzeInterleaving ()
	Analyze thread interleaving.
ThreadCallGraph *	getThreadCallGraph () const
	Get ThreadCallGraph.
TCT *	getTCT () const
	Get Thread Creation Tree.
bool	isConnectedfromMain (const FunObjVar *fun)
	Whether the function is connected from main function in thread call graph.
virtual bool	mayHappenInParallel (const ICFGNode *i1, const ICFGNode *i2)
	Interface to query whether two instructions may happen-in-parallel.
virtual bool	mayHappenInParallelCache (const ICFGNode *i1, const ICFGNode *i2)
virtual bool	mayHappenInParallelInst (const ICFGNode *i1, const ICFGNode *i2)
virtual bool	executedByTheSameThread (const ICFGNode *i1, const ICFGNode *i2)
const NodeBS &	getInterleavingThreads (const CxtThreadStmt &cts)
	Get interleaving thread for statement inst.
bool	hasInterleavingThreads (const CxtThreadStmt &cts) const
const CxtThreadStmtSet &	getThreadStmtSet (const ICFGNode *inst) const
	Get/has ThreadStmt.
bool	hasThreadStmtSet (const ICFGNode *inst) const
void	printInterleaving ()
	Print interleaving results.

Public Attributes
u32_t	numOfTotalQueries
	Total number of queries.
u32_t	numOfMHPQueries
	Number of queries are answered as may-happen-in-parallel.
double	interleavingTime
double	interleavingQueriesTime

Private Member Functions
const CallGraph::FunctionSet &	getCallee (const CallICFGNode *inst, CallGraph::FunctionSet &callees)
void	updateNonCandidateFunInterleaving ()
void	handleNonCandidateFun (const CxtThreadStmt &cts)
	Handle non-candidate function.
void	handleFork (const CxtThreadStmt &cts, NodeID rootTid)
	Handle fork.
void	handleJoin (const CxtThreadStmt &cts, NodeID rootTid)
	Handle join.
void	handleCall (const CxtThreadStmt &cts, NodeID rootTid)
	Handle call.
void	handleRet (const CxtThreadStmt &cts)
	Handle return.
void	handleIntra (const CxtThreadStmt &cts)
	Handle intra.
void	addInterleavingThread (const CxtThreadStmt &tgr, NodeID tid)
	Add/Remove interleaving thread for statement inst.
void	addInterleavingThread (const CxtThreadStmt &tgr, const CxtThreadStmt &src)
void	rmInterleavingThread (const CxtThreadStmt &tgr, const NodeBS &tids, const ICFGNode *joinsite)
void	updateAncestorThreads (NodeID tid)
	Update Ancestor and sibling threads.
void	updateSiblingThreads (NodeID tid)
bool	isRecurFullJoin (NodeID parentTid, NodeID curTid)
	Thread curTid can be fully joined by parentTid recursively.
bool	isMustJoin (const NodeID curTid, const ICFGNode *joinsite)
	Whether a join site must join a thread t.
bool	isMultiForkedThread (NodeID curTid)
	A thread is a multiForked thread if it is in a loop or recursion.
void	pushCxt (CallStrCxt &cxt, const CallICFGNode *call, const FunObjVar *callee)
	Push calling context.
bool	matchCxt (CallStrCxt &cxt, const CallICFGNode *call, const FunObjVar *callee)
	Match context.
bool	pushToCTSWorkList (const CxtThreadStmt &cs)
	WorkList helper functions.
CxtThreadStmt	popFromCTSWorkList ()
bool	isTDFork (const ICFGNode *call)
	Whether it is a fork site.
bool	isTDJoin (const ICFGNode *call)
	Whether it is a join site.
NodeBS	getDirAndIndJoinedTid (const CallStrCxt &cxt, const ICFGNode *call)
	Return thread id(s) which are directly or indirectly joined at this join site.
bool	hasJoinInSymmetricLoop (const CallStrCxt &cxt, const ICFGNode *call) const
	Whether a context-sensitive join satisfies symmetric loop pattern.
const LoopBBs &	getJoinInSymmetricLoop (const CallStrCxt &cxt, const ICFGNode *call) const
	Whether a context-sensitive join satisfies symmetric loop pattern.
bool	isHBPair (NodeID tid1, NodeID tid2)
	Whether thread t1 happens before t2 based on ForkJoin Analysis.

Private Attributes
ThreadCallGraph *	tcg
	TCG.
TCT *	tct
	TCT.
ForkJoinAnalysis *	fja
	ForJoin Analysis.
CxtThreadStmtWorkList	cxtStmtList
	CxtThreadStmt worklist.
ThreadStmtToThreadInterleav	threadStmtToTheadInterLeav
InstToThreadStmtSetMap	instToTSMap
	Map a statement to its thread interleavings.
FuncPairToBool	nonCandidateFuncMHPRelMap

Detailed Description

This class serves as a base may-happen in parallel analysis for multithreaded program Given a statement under an abstract thread, it tells which abstract threads may be alive at the same time (May-happen-in-parallel).

Definition at line 45 of file MHP.h.

Member Typedef Documentation

CxtThreadStmtSet

typedef Set<CxtThreadStmt> SVF::MHP::CxtThreadStmtSet

Definition at line 51 of file MHP.h.

CxtThreadStmtWorkList

typedef FIFOWorkList<CxtThreadStmt> SVF::MHP::CxtThreadStmtWorkList

Definition at line 50 of file MHP.h.

FuncPair

typedef std::pair<const FunObjVar*,const FunObjVar*> SVF::MHP::FuncPair

Definition at line 58 of file MHP.h.

FuncPairToBool

typedef Map<FuncPair, bool> SVF::MHP::FuncPairToBool

Definition at line 59 of file MHP.h.

FunSet

typedef Set<const FunObjVar*> SVF::MHP::FunSet

Definition at line 49 of file MHP.h.

InstToThreadStmtSetMap

typedef Map<const ICFGNode*,CxtThreadStmtSet> SVF::MHP::InstToThreadStmtSetMap

Definition at line 53 of file MHP.h.

LockSpan

typedef Set<CxtStmt> SVF::MHP::LockSpan

Definition at line 56 of file MHP.h.

LoopBBs

typedef SVFLoopAndDomInfo::LoopBBs SVF::MHP::LoopBBs

Definition at line 54 of file MHP.h.

ThreadStmtToThreadInterleav

typedef Map<CxtThreadStmt,NodeBS> SVF::MHP::ThreadStmtToThreadInterleav

Definition at line 52 of file MHP.h.

Constructor & Destructor Documentation

MHP()

MHP::MHP

(

TCT *

t

)

Constructor.

Constructor

Definition at line 44 of file MHP.cpp.

               : tcg(t->getThreadCallGraph()), tct(t), numOfTotalQueries(0), numOfMHPQueries(0),
    interleavingTime(0), interleavingQueriesTime(0)
{
    fja = new ForkJoinAnalysis(tct);
    fja->analyzeForkJoinPair();
}

~MHP()

MHP::~MHP ( )

virtual

Destructor.

Destructor

Definition at line 54 of file MHP.cpp.

{
    delete fja;
}

Member Function Documentation

addInterleavingThread() [1/2]

void SVF::MHP::addInterleavingThread ( const CxtThreadStmt &  tgr, const CxtThreadStmt &  src  )

inlineprivate

Definition at line 163 of file MHP.h.

    {
        bool changed = threadStmtToTheadInterLeav[tgr] |= threadStmtToTheadInterLeav[src];
        if(changed)
        {
            instToTSMap[tgr.getStmt()].insert(tgr);
            pushToCTSWorkList(tgr);
        }
    }

addInterleavingThread() [2/2]

void SVF::MHP::addInterleavingThread ( const CxtThreadStmt &  tgr, NodeID  tid  )

inlineprivate

Add/Remove interleaving thread for statement inst.

Definition at line 155 of file MHP.h.

    {
        if(threadStmtToTheadInterLeav[tgr].test_and_set(tid))
        {
            instToTSMap[tgr.getStmt()].insert(tgr);
            pushToCTSWorkList(tgr);
        }
    }

analyze()

void MHP::analyze

(

)

Start analysis here.

Start analysis here

Definition at line 62 of file MHP.cpp.

{
    DBOUT(DGENERAL, outs() << pasMsg("MHP interleaving analysis\n"));
    DBOUT(DMTA, outs() << pasMsg("MHP interleaving analysis\n"));
    DOTIMESTAT(double interleavingStart = PTAStat::getClk(true));
    analyzeInterleaving();
    DOTIMESTAT(double interleavingEnd = PTAStat::getClk(true));
    DOTIMESTAT(interleavingTime += (interleavingEnd - interleavingStart) / TIMEINTERVAL);
}

analyzeInterleaving()

void MHP::analyzeInterleaving

(

)

Analyze thread interleaving.

Analyze thread interleaving

handle non-candidate function

handle candidate function

update non-candidate functions' interleaving

Definition at line 75 of file MHP.cpp.

{
    for (const std::pair<const NodeID, TCTNode*>& tpair : *tct)
    {
        const CxtThread& ct = tpair.second->getCxtThread();
        NodeID rootTid = tpair.first;
        const FunObjVar* routine = tct->getStartRoutineOfCxtThread(ct);
        const ICFGNode* svfInst = routine->getEntryBlock()->front();
        CxtThreadStmt rootcts(rootTid, ct.getContext(), svfInst);
 
        addInterleavingThread(rootcts, rootTid);
        updateAncestorThreads(rootTid);
        updateSiblingThreads(rootTid);
 
        while (!cxtStmtList.empty())
        {
            CxtThreadStmt cts = popFromCTSWorkList();
            const ICFGNode* curInst = cts.getStmt();
            DBOUT(DMTA, outs() << "-----\nMHP analysis root thread: " << rootTid << " ");
            DBOUT(DMTA, cts.dump());
            DBOUT(DMTA, outs() << "current thread interleaving: < ");
            DBOUT(DMTA, dumpSet(getInterleavingThreads(cts)));
            DBOUT(DMTA, outs() << " >\n-----\n");
 
            if (!tct->isCandidateFun(curInst->getFun()))
            {
                handleNonCandidateFun(cts);
            }
            else
            {
                if (isTDFork(curInst))
                {
                    handleFork(cts, rootTid);
                }
                else if (isTDJoin(curInst))
                {
                    handleJoin(cts, rootTid);
                }
                else if (tct->isCallSite(curInst) && !tct->isExtCall(curInst))
                {
                    handleCall(cts, rootTid);
                    CallGraph::FunctionSet callees;
                    if (!tct->isCandidateFun(getCallee(SVFUtil::cast<CallICFGNode>(curInst), callees)))
                        handleIntra(cts);
                }
                else if (isRetInstNode(curInst))
                {
                    handleRet(cts);
                }
                else
                {
                    handleIntra(cts);
                }
            }
        }
    }
 
    updateNonCandidateFunInterleaving();
 
    if (Options::PrintInterLev())
        printInterleaving();
}

executedByTheSameThread()

bool MHP::executedByTheSameThread ( const ICFGNode *  i1, const ICFGNode *  i2  )

virtual

Definition at line 627 of file MHP.cpp.

{
    if (!hasThreadStmtSet(i1) || !hasThreadStmtSet(i2))
        return true;
 
    const CxtThreadStmtSet& tsSet1 = getThreadStmtSet(i1);
    const CxtThreadStmtSet& tsSet2 = getThreadStmtSet(i2);
    for (const CxtThreadStmt&ts1 : tsSet1)
    {
        for (const CxtThreadStmt& ts2 : tsSet2)
        {
            if (ts1.getTid() != ts2.getTid() || isMultiForkedThread(ts1.getTid()))
                return false;
        }
    }
    return true;
}

getCallee()

const CallGraph::FunctionSet & SVF::MHP::getCallee ( const CallICFGNode *  inst, CallGraph::FunctionSet &  callees  )

inlineprivate

Definition at line 126 of file MHP.h.

    {
        tcg->getCallees(inst, callees);
        return callees;
    }

getDirAndIndJoinedTid()

NodeBS MHP::getDirAndIndJoinedTid ( const CallStrCxt &  cxt, const ICFGNode *  call  )

private

Return thread id(s) which are directly or indirectly joined at this join site.

Return thread id(s) which are directly or indirectly joined at this join site

Definition at line 492 of file MHP.cpp.

{
    CxtStmt cs(cxt, call);
    return fja->getDirAndIndJoinedTid(cs);
}

getInterleavingThreads()

const NodeBS & SVF::MHP::getInterleavingThreads ( const CxtThreadStmt &  cts )

inline

Get interleaving thread for statement inst.

Definition at line 97 of file MHP.h.

    {
        return threadStmtToTheadInterLeav[cts];
    }

getJoinInSymmetricLoop()

const MHP::LoopBBs & MHP::getJoinInSymmetricLoop ( const CallStrCxt &  cxt, const ICFGNode *  call  ) const

private

Whether a context-sensitive join satisfies symmetric loop pattern.

Definition at line 508 of file MHP.cpp.

{
    CxtStmt cs(cxt, call);
    return fja->getJoinInSymmetricLoop(cs);
}

getTCT()

TCT * SVF::MHP::getTCT ( ) const

inline

Get Thread Creation Tree.

Definition at line 80 of file MHP.h.

    {
        return tct;
    }

getThreadCallGraph()

ThreadCallGraph * SVF::MHP::getThreadCallGraph ( ) const

inline

Get ThreadCallGraph.

Definition at line 74 of file MHP.h.

    {
        return tcg;
    }

getThreadStmtSet()

const CxtThreadStmtSet & SVF::MHP::getThreadStmtSet ( const ICFGNode *  inst ) const

inline

Get/has ThreadStmt.

Definition at line 109 of file MHP.h.

    {
        InstToThreadStmtSetMap::const_iterator it = instToTSMap.find(inst);
        assert(it!=instToTSMap.end() && "no thread access the instruction?");
        return it->second;
    }

handleCall()

void MHP::handleCall ( const CxtThreadStmt &  cts, NodeID  rootTid  )

private

Handle call.

Handle call instruction in the current thread scope (excluding any fork site)

Definition at line 291 of file MHP.cpp.

{
 
    const ICFGNode* call = cts.getStmt();
    const CallStrCxt& curCxt = cts.getContext();
    const CallICFGNode* cbn = cast<CallICFGNode>(call);
    if (tct->getThreadCallGraph()->hasCallGraphEdge(cbn))
    {
        for (CallGraph::CallGraphEdgeSet::const_iterator cgIt = tcg->getCallEdgeBegin(cbn),
                ecgIt = tcg->getCallEdgeEnd(cbn);
                cgIt != ecgIt; ++cgIt)
        {
 
            const FunObjVar* svfcallee = (*cgIt)->getDstNode()->getFunction();
            if (isExtCall(svfcallee))
                continue;
            CallStrCxt newCxt = curCxt;
            const CallICFGNode* callicfgnode = SVFUtil::cast<CallICFGNode>(call);
            pushCxt(newCxt, callicfgnode, svfcallee);
            const ICFGNode* svfEntryInst = svfcallee->getEntryBlock()->front();
            CxtThreadStmt newCts(cts.getTid(), newCxt, svfEntryInst);
            addInterleavingThread(newCts, cts);
        }
    }
}

handleFork()

void MHP::handleFork ( const CxtThreadStmt &  cts, NodeID  rootTid  )

private

Handle fork.

Handle fork

Definition at line 204 of file MHP.cpp.

{
 
    const ICFGNode* call = cts.getStmt();
    const CallStrCxt& curCxt = cts.getContext();
 
    assert(isTDFork(call));
    const CallICFGNode* cbn = cast<CallICFGNode>(call);
    if (tct->getThreadCallGraph()->hasCallGraphEdge(cbn))
    {
 
        for (ThreadCallGraph::ForkEdgeSet::const_iterator cgIt = tcg->getForkEdgeBegin(cbn),
                ecgIt = tcg->getForkEdgeEnd(cbn);
                cgIt != ecgIt; ++cgIt)
        {
            const FunObjVar* svfroutine = (*cgIt)->getDstNode()->getFunction();
            CallStrCxt newCxt = curCxt;
            pushCxt(newCxt, cbn, svfroutine);
            const ICFGNode* stmt = svfroutine->getEntryBlock()->front();
            CxtThread ct(newCxt, call);
            CxtThreadStmt newcts(tct->getTCTNode(ct)->getId(), ct.getContext(), stmt);
            addInterleavingThread(newcts, cts);
        }
    }
    handleIntra(cts);
}

handleIntra()

void MHP::handleIntra ( const CxtThreadStmt &  cts )

private

Handle intra.

Handling intraprocedural statements (successive statements on the CFG )

Definition at line 367 of file MHP.cpp.

{
 
    for(const ICFGEdge* outEdge : cts.getStmt()->getOutEdges())
    {
        if(outEdge->getDstNode()->getFun() == cts.getStmt()->getFun())
        {
            CxtThreadStmt newCts(cts.getTid(), cts.getContext(), outEdge->getDstNode());
            addInterleavingThread(newCts, cts);
        }
    }
}

handleJoin()

void MHP::handleJoin ( const CxtThreadStmt &  cts, NodeID  rootTid  )

private

Handle join.

Handle join

for the join site in a loop loop which does not join the current thread we process the loop exit

Definition at line 234 of file MHP.cpp.

{
 
    const CallStrCxt& curCxt = cts.getContext();
 
    assert(isTDJoin(cts.getStmt()));
 
    const CallICFGNode* call = SVFUtil::cast<CallICFGNode>(cts.getStmt());
 
    NodeBS joinedTids = getDirAndIndJoinedTid(curCxt, call);
    if (!joinedTids.empty())
    {
        if (fja->hasJoinLoop(call))
        {
            std::vector<const SVFBasicBlock*> exitbbs;
            call->getFun()->getExitBlocksOfLoop(call->getBB(), exitbbs);
            while (!exitbbs.empty())
            {
                const SVFBasicBlock* eb = exitbbs.back();
                exitbbs.pop_back();
                const ICFGNode* svfEntryInst = eb->front();
                CxtThreadStmt newCts(cts.getTid(), curCxt, svfEntryInst);
                addInterleavingThread(newCts, cts);
                if (hasJoinInSymmetricLoop(curCxt, call))
                    rmInterleavingThread(newCts, joinedTids, call);
            }
        }
        else
        {
            rmInterleavingThread(cts, joinedTids, call);
            DBOUT(DMTA, outs() << "\n\t match join site " << call->toString() << " for thread " << rootTid << "\n");
        }
    }
    else
    {
        if (fja->hasJoinLoop(call))
        {
            std::vector<const SVFBasicBlock*> exitbbs;
            call->getFun()->getExitBlocksOfLoop(call->getBB(), exitbbs);
            while (!exitbbs.empty())
            {
                const SVFBasicBlock* eb = exitbbs.back();
                exitbbs.pop_back();
                const ICFGNode* svfEntryInst = eb->front();
                CxtThreadStmt newCts(cts.getTid(), cts.getContext(), svfEntryInst);
                addInterleavingThread(newCts, cts);
            }
        }
    }
    handleIntra(cts);
}

handleNonCandidateFun()

void MHP::handleNonCandidateFun ( const CxtThreadStmt &  cts )

private

Handle non-candidate function.

Handle call instruction in the current thread scope (excluding any fork site)

Definition at line 182 of file MHP.cpp.

{
    const ICFGNode* curInst = cts.getStmt();
    const FunObjVar* curfun = curInst->getFun();
    assert((curInst == curfun->getEntryBlock()->front()) && "curInst is not the entry of non candidate function.");
    const CallStrCxt& curCxt = cts.getContext();
    CallGraphNode* node = tcg->getCallGraphNode(curfun);
    for (CallGraphNode::const_iterator nit = node->OutEdgeBegin(), neit = node->OutEdgeEnd(); nit != neit; nit++)
    {
        const FunObjVar* callee = (*nit)->getDstNode()->getFunction();
        if (!isExtCall(callee))
        {
            const ICFGNode* calleeInst = callee->getEntryBlock()->front();
            CxtThreadStmt newCts(cts.getTid(), curCxt, calleeInst);
            addInterleavingThread(newCts, cts);
        }
    }
}

handleRet()

void MHP::handleRet ( const CxtThreadStmt &  cts )

private

Handle return.

Handle return instruction in the current thread scope (excluding any join site)

Definition at line 320 of file MHP.cpp.

{
    CallGraphNode* curFunNode = tcg->getCallGraphNode(cts.getStmt()->getFun());
    for (CallGraphEdge* edge : curFunNode->getInEdges())
    {
        if (SVFUtil::isa<ThreadForkEdge, ThreadJoinEdge>(edge))
            continue;
        for (CallGraphEdge::CallInstSet::const_iterator cit = (edge)->directCallsBegin(),
                ecit = (edge)->directCallsEnd();
                cit != ecit; ++cit)
        {
            CallStrCxt newCxt = cts.getContext();
            if (matchCxt(newCxt, *cit, curFunNode->getFunction()))
            {
                for(const ICFGEdge* outEdge : cts.getStmt()->getOutEdges())
                {
                    if(outEdge->getDstNode()->getFun() == cts.getStmt()->getFun())
                    {
                        CxtThreadStmt newCts(cts.getTid(), newCxt, outEdge->getDstNode());
                        addInterleavingThread(newCts, cts);
                    }
                }
            }
        }
        for (CallGraphEdge::CallInstSet::const_iterator cit = (edge)->indirectCallsBegin(),
                ecit = (edge)->indirectCallsEnd();
                cit != ecit; ++cit)
        {
            CallStrCxt newCxt = cts.getContext();
            if (matchCxt(newCxt, *cit, curFunNode->getFunction()))
            {
                for(const ICFGEdge* outEdge : cts.getStmt()->getOutEdges())
                {
                    if(outEdge->getDstNode()->getFun() == cts.getStmt()->getFun())
                    {
                        CxtThreadStmt newCts(cts.getTid(), newCxt, outEdge->getDstNode());
                        addInterleavingThread(newCts, cts);
                    }
                }
            }
        }
    }
}

hasInterleavingThreads()

bool SVF::MHP::hasInterleavingThreads ( const CxtThreadStmt &  cts ) const

inline

Definition at line 101 of file MHP.h.

    {
        return threadStmtToTheadInterLeav.find(cts)!=threadStmtToTheadInterLeav.end();
    }

hasJoinInSymmetricLoop()

bool MHP::hasJoinInSymmetricLoop ( const CallStrCxt &  cxt, const ICFGNode *  call  ) const

private

Whether a context-sensitive join satisfies symmetric loop pattern.

Whether a context-sensitive join satisfies symmetric loop pattern

Definition at line 501 of file MHP.cpp.

{
    CxtStmt cs(cxt, call);
    return fja->hasJoinInSymmetricLoop(cs);
}

hasThreadStmtSet()

bool SVF::MHP::hasThreadStmtSet ( const ICFGNode *  inst ) const

inline

Definition at line 115 of file MHP.h.

    {
        return instToTSMap.find(inst)!=instToTSMap.end();
    }

isConnectedfromMain()

bool MHP::isConnectedfromMain

(

const FunObjVar *

fun

)

Whether the function is connected from main function in thread call graph.

Definition at line 522 of file MHP.cpp.

{
    CallGraphNode* cgnode = tcg->getCallGraphNode(fun);
    FIFOWorkList<const CallGraphNode*> worklist;
    TCT::PTACGNodeSet visited;
    worklist.push(cgnode);
    visited.insert(cgnode);
    while (!worklist.empty())
    {
        const CallGraphNode* node = worklist.pop();
        if ("main" == node->getFunction()->getName())
            return true;
        for (CallGraphNode::const_iterator nit = node->InEdgeBegin(), neit = node->InEdgeEnd(); nit != neit; nit++)
        {
            const CallGraphNode* srcNode = (*nit)->getSrcNode();
            if (visited.find(srcNode) == visited.end())
            {
                visited.insert(srcNode);
                worklist.push(srcNode);
            }
        }
    }
    return false;
}

isHBPair()

bool MHP::isHBPair ( NodeID  tid1, NodeID  tid2  )

private

Whether thread t1 happens before t2 based on ForkJoin Analysis.

Whether two thread t1 happens-fore t2

Definition at line 517 of file MHP.cpp.

{
    return fja->isHBPair(tid1, tid2);
}

isMultiForkedThread()

bool SVF::MHP::isMultiForkedThread ( NodeID  curTid )

inlineprivate

A thread is a multiForked thread if it is in a loop or recursion.

Definition at line 200 of file MHP.h.

    {
        return tct->getTCTNode(curTid)->isMultiforked();
    }

isMustJoin()

bool MHP::isMustJoin ( const NodeID  curTid, const ICFGNode *  joinsite  )

private

Whether a join site must join a thread t.

A join site must join t if (1) t is not a multiforked thread (2) the join site of t is not in recursion

Definition at line 482 of file MHP.cpp.

{
    const CallICFGNode* call = SVFUtil::dyn_cast<CallICFGNode>(joinsite);
    assert(call && isTDJoin(call) && "not a join site!");
    return !isMultiForkedThread(curTid) && !tct->isJoinSiteInRecursion(call);
}

isRecurFullJoin()

bool MHP::isRecurFullJoin ( NodeID  parentTid, NodeID  curTid  )

private

Thread curTid can be fully joined by parentTid recursively.

Whether curTid can be fully joined by parentTid recursively

Definition at line 447 of file MHP.cpp.

{
    if (parentTid == curTid)
        return true;
 
    const TCTNode* curNode = tct->getTCTNode(curTid);
    FIFOWorkList<const TCTNode*> worklist;
    worklist.push(curNode);
    while (!worklist.empty())
    {
        const TCTNode* node = worklist.pop();
        for (TCTEdge* edge : node->getInEdges())
        {
            NodeID srcID = edge->getSrcID();
            if (fja->isFullJoin(srcID, node->getId()))
            {
                if (srcID == parentTid)
                    return true;
                else
                    worklist.push(edge->getSrcNode());
            }
            else
            {
                return false;
            }
        }
    }
    return false;
}

isTDFork()

bool SVF::MHP::isTDFork ( const ICFGNode *  call )

inlineprivate

Whether it is a fork site.

Definition at line 228 of file MHP.h.

    {
        const CallICFGNode* fork = SVFUtil::dyn_cast<CallICFGNode>(call);
        return fork && tcg->getThreadAPI()->isTDFork(fork);
    }

isTDJoin()

bool SVF::MHP::isTDJoin ( const ICFGNode *  call )

inlineprivate

Whether it is a join site.

Definition at line 234 of file MHP.h.

    {
        const CallICFGNode* join = SVFUtil::dyn_cast<CallICFGNode>(call);
        return join && tcg->getThreadAPI()->isTDJoin(join);
    }

matchCxt()

bool SVF::MHP::matchCxt ( CallStrCxt &  cxt, const CallICFGNode *  call, const FunObjVar *  callee  )

inlineprivate

Match context.

Definition at line 210 of file MHP.h.

    {
        return tct->matchCxt(cxt,call,callee);
    }

mayHappenInParallel()

bool MHP::mayHappenInParallel ( const ICFGNode *  i1, const ICFGNode *  i2  )

virtual

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

Definition at line 615 of file MHP.cpp.

{
    numOfTotalQueries++;
 
    DOTIMESTAT(double queryStart = PTAStat::getClk(true));
    bool mhp = mayHappenInParallelCache(i1, i2);
    DOTIMESTAT(double queryEnd = PTAStat::getClk(true));
    DOTIMESTAT(interleavingQueriesTime += (queryEnd - queryStart) / TIMEINTERVAL);
 
    return mhp;
}

mayHappenInParallelCache()

bool MHP::mayHappenInParallelCache ( const ICFGNode *  i1, const ICFGNode *  i2  )

virtual

Definition at line 593 of file MHP.cpp.

{
    if (!tct->isCandidateFun(i1->getFun()) && !tct->isCandidateFun(i2->getFun()))
    {
        FuncPair funpair = std::make_pair(i1->getFun(), i2->getFun());
        FuncPairToBool::const_iterator it = nonCandidateFuncMHPRelMap.find(funpair);
        if (it == nonCandidateFuncMHPRelMap.end())
        {
            bool mhp = mayHappenInParallelInst(i1, i2);
            nonCandidateFuncMHPRelMap[funpair] = mhp;
            return mhp;
        }
        else
        {
            if (it->second)
                numOfMHPQueries++;
            return it->second;
        }
    }
    return mayHappenInParallelInst(i1, i2);
}

mayHappenInParallelInst()

bool MHP::mayHappenInParallelInst ( const ICFGNode *  i1, const ICFGNode *  i2  )

virtual

Answer MHP queries For a pair of ThreadStmts (t1,s1) = <l1> (t2,s2) = <l2> They may happen in parallel if (1) t1 == t2 and t1 inloop/incycle (2) t1!=t2 and t1 \in l2 and t2 \in l1

TODO: Any instruction in dead function is assumed no MHP with others

Definition at line 557 of file MHP.cpp.

{
 
    if (!hasThreadStmtSet(i1) || !hasThreadStmtSet(i2))
        return false;
 
    const CxtThreadStmtSet& tsSet1 = getThreadStmtSet(i1);
    const CxtThreadStmtSet& tsSet2 = getThreadStmtSet(i2);
    for (const CxtThreadStmt& ts1 : tsSet1)
    {
        NodeBS l1 = getInterleavingThreads(ts1);
        for (const CxtThreadStmt& ts2 : tsSet2)
        {
            NodeBS l2 = getInterleavingThreads(ts2);
            if (ts1.getTid() != ts2.getTid())
            {
                if (l1.test(ts2.getTid()) && l2.test(ts1.getTid()))
                {
                    numOfMHPQueries++;
                    return true;
                }
            }
            else
            {
                if (isMultiForkedThread(ts1.getTid()))
                {
                    numOfMHPQueries++;
                    return true;
                }
            }
        }
    }
    return false;
}

popFromCTSWorkList()

CxtThreadStmt SVF::MHP::popFromCTSWorkList ( )

inlineprivate

Definition at line 221 of file MHP.h.

    {
        CxtThreadStmt ctp = cxtStmtList.pop();
        return ctp;
    }

printInterleaving()

void MHP::printInterleaving

(

)

Print interleaving results.

Print interleaving results

Definition at line 648 of file MHP.cpp.

{
    for (const auto& pair : threadStmtToTheadInterLeav)
    {
        outs() << "( t" << pair.first.getTid()
               << pair.first.getStmt()->toString() << " ) ==> [";
        for (unsigned i : pair.second)
        {
            outs() << " " << i << " ";
        }
        outs() << "]\n";
    }
}

pushCxt()

void SVF::MHP::pushCxt ( CallStrCxt &  cxt, const CallICFGNode *  call, const FunObjVar *  callee  )

inlineprivate

Push calling context.

Definition at line 205 of file MHP.h.

    {
        tct->pushCxt(cxt,call,callee);
    }

pushToCTSWorkList()

bool SVF::MHP::pushToCTSWorkList ( const CxtThreadStmt &  cs )

inlineprivate

WorkList helper functions.

Definition at line 217 of file MHP.h.

    {
        return cxtStmtList.push(cs);
    }

rmInterleavingThread()

void SVF::MHP::rmInterleavingThread ( const CxtThreadStmt &  tgr, const NodeBS &  tids, const ICFGNode *  joinsite  )

inlineprivate

Definition at line 172 of file MHP.h.

    {
        NodeBS joinedTids;
        for(NodeBS::iterator it = tids.begin(), eit = tids.end(); it!=eit; ++it)
        {
            if(isMustJoin(tgr.getTid(),joinsite))
                joinedTids.set(*it);
        }
        if(threadStmtToTheadInterLeav[tgr].intersectWithComplement(joinedTids))
        {
            pushToCTSWorkList(tgr);
        }
    }

updateAncestorThreads()

void MHP::updateAncestorThreads ( NodeID  curTid )

private

Update Ancestor and sibling threads.

Update interleavings of ancestor threads according to TCT

Definition at line 383 of file MHP.cpp.

{
    NodeBS tds = tct->getAncestorThread(curTid);
    DBOUT(DMTA, outs() << "##Ancestor thread of " << curTid << " is : ");
    DBOUT(DMTA, dumpSet(tds));
    DBOUT(DMTA, outs() << "\n");
    tds.set(curTid);
 
    for (const unsigned i : tds)
    {
        const CxtThread& ct = tct->getTCTNode(i)->getCxtThread();
        if (const ICFGNode* forkInst = ct.getThread())
        {
            CallStrCxt forkSiteCxt = tct->getCxtOfCxtThread(ct);
            for(const ICFGEdge* outEdge : forkInst->getOutEdges())
            {
                if(outEdge->getDstNode()->getFun() == forkInst->getFun())
                {
                    CxtThreadStmt cts(tct->getParentThread(i), forkSiteCxt, outEdge->getDstNode());
                    addInterleavingThread(cts, curTid);
                }
            }
        }
    }
}

updateNonCandidateFunInterleaving()

void MHP::updateNonCandidateFunInterleaving ( )

private

Update non-candidate functions' interleaving. Copy interleaving threads of the entry inst to other insts.

Update non-candidate functions' interleaving

Definition at line 144 of file MHP.cpp.

{
    for (const auto& item : *PAG::getPAG()->getCallGraph())
    {
        const FunObjVar* fun = item.second->getFunction();
        if (!tct->isCandidateFun(fun) && !isExtCall(fun))
        {
            const ICFGNode* entryNode = fun->getEntryBlock()->front();
 
            if (!hasThreadStmtSet(entryNode))
                continue;
 
            const CxtThreadStmtSet& tsSet = getThreadStmtSet(entryNode);
 
            for (const CxtThreadStmt& cts : tsSet)
            {
                const CallStrCxt& curCxt = cts.getContext();
 
                for (auto it : *fun)
                {
                    const SVFBasicBlock* svfbb = it.second;
                    for (const ICFGNode* curNode : svfbb->getICFGNodeList())
                    {
                        if (curNode == entryNode)
                            continue;
                        CxtThreadStmt newCts(cts.getTid(), curCxt, curNode);
                        threadStmtToTheadInterLeav[newCts] |= threadStmtToTheadInterLeav[cts];
                        instToTSMap[curNode].insert(newCts);
                    }
                }
            }
        }
    }
}

updateSiblingThreads()

void MHP::updateSiblingThreads ( NodeID  curTid )

private

Update interleavings of sibling threads according to TCT

Exclude sibling thread that never happen in parallel based on ForkJoinAnalysis

The interleaving of a thread t is not unnecessary to be updated if (1) t HB Sibling and t fully joins curTid recursively or (2) Sibling HB t

Definition at line 419 of file MHP.cpp.

{
    NodeBS tds = tct->getAncestorThread(curTid);
    tds.set(curTid);
    for (const unsigned tid : tds)
    {
        NodeBS siblingTds = tct->getSiblingThread(tid);
        for (const unsigned stid : siblingTds)
        {
            if ((isHBPair(tid, stid) && isRecurFullJoin(tid, curTid)) || isHBPair(stid, tid))
                continue;
 
            const CxtThread& ct = tct->getTCTNode(stid)->getCxtThread();
            const FunObjVar* routine = tct->getStartRoutineOfCxtThread(ct);
            const ICFGNode* stmt = routine->getEntryBlock()->front();
            CxtThreadStmt cts(stid, ct.getContext(), stmt);
            addInterleavingThread(cts, curTid);
        }
 
        DBOUT(DMTA, outs() << "##Sibling thread of " << curTid << " is : ");
        DBOUT(DMTA, dumpSet(siblingTds));
        DBOUT(DMTA, outs() << "\n");
    }
}

Member Data Documentation

cxtStmtList

CxtThreadStmtWorkList SVF::MHP::cxtStmtList

private

CxtThreadStmt worklist.

Definition at line 255 of file MHP.h.

fja

ForkJoinAnalysis* SVF::MHP::fja

private

ForJoin Analysis.

Definition at line 254 of file MHP.h.

instToTSMap

InstToThreadStmtSetMap SVF::MHP::instToTSMap

private

Map a statement to its thread interleavings.

Map an instruction to its ThreadStmtSet

Definition at line 257 of file MHP.h.

interleavingQueriesTime

double SVF::MHP::interleavingQueriesTime

Definition at line 265 of file MHP.h.

interleavingTime

double SVF::MHP::interleavingTime

Definition at line 264 of file MHP.h.

nonCandidateFuncMHPRelMap

FuncPairToBool SVF::MHP::nonCandidateFuncMHPRelMap

private

Definition at line 258 of file MHP.h.

numOfMHPQueries

u32_t SVF::MHP::numOfMHPQueries

Number of queries are answered as may-happen-in-parallel.

Definition at line 263 of file MHP.h.

numOfTotalQueries

u32_t SVF::MHP::numOfTotalQueries

Total number of queries.

Definition at line 262 of file MHP.h.

tcg

ThreadCallGraph* SVF::MHP::tcg

private

TCG.

Definition at line 252 of file MHP.h.

tct

TCT* SVF::MHP::tct

private

TCT.

Definition at line 253 of file MHP.h.

threadStmtToTheadInterLeav

ThreadStmtToThreadInterleav SVF::MHP::threadStmtToTheadInterLeav

private

Definition at line 256 of file MHP.h.

---

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

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