SVF::ForkJoinAnalysis Class Reference

#include <MHP.h>

Public Types
enum	ValDomain { Empty , TDAlive , TDDead }
	semilattice Empty==>TDDead==>TDAlive More...
typedef SVFLoopAndDomInfo::LoopBBs	LoopBBs
typedef TCT::InstVec	InstVec
typedef Map< CxtStmt, ValDomain >	CxtStmtToAliveFlagMap
typedef Map< CxtStmt, NodeBS >	CxtStmtToTIDMap
typedef Set< NodePair >	ThreadPairSet
typedef Map< CxtStmt, LoopBBs >	CxtStmtToLoopMap
typedef FIFOWorkList< CxtStmt >	CxtStmtWorkList

Public Member Functions
	ForkJoinAnalysis (TCT *t)
void	collectSCEVInfo ()
	functions More...
void	analyzeForkJoinPair ()
NodeBS &	getDirectlyJoinedTid (const CxtStmt &cs)
	Get directly joined threadIDs based on a context-sensitive join site. More...
NodeBS	getDirAndIndJoinedTid (const CxtStmt &cs)
	Get directly and indirectly joined threadIDs based on a context-sensitive join site. More...
const LoopBBs &	getJoinInSymmetricLoop (const CxtStmt &cs) const
	Whether a context-sensitive join satisfies symmetric loop pattern. More...
bool	hasJoinInSymmetricLoop (const CxtStmt &cs) const
bool	isHBPair (NodeID tid1, NodeID tid2)
	Whether thread t1 happens-before thread t2. More...
bool	isFullJoin (NodeID tid1, NodeID tid2)
	Whether t1 fully joins t2. More...
const ICFGNode *	getExitInstOfParentRoutineFun (NodeID tid) const
	Get exit instruction of the start routine function of tid's parent thread. More...
LoopBBs &	getJoinLoop (const CallICFGNode *inst)
	Get loop for join site. More...
bool	hasJoinLoop (const CallICFGNode *inst)

Private Member Functions
void	handleFork (const CxtStmt &cts, NodeID rootTid)
	Handle fork. More...
void	handleJoin (const CxtStmt &cts, NodeID rootTid)
	Handle join. More...
void	handleCall (const CxtStmt &cts, NodeID rootTid)
	Handle call. More...
void	handleRet (const CxtStmt &cts)
	Handle return. More...
void	handleIntra (const CxtStmt &cts)
	Handle intra. More...
bool	isSameSCEV (const ICFGNode *forkSite, const ICFGNode *joinSite)
	Return true if the fork and join have the same SCEV. More...
bool	sameLoopTripCount (const ICFGNode *forkSite, const ICFGNode *joinSite)
	Same loop trip count. More...
bool	isAliasedForkJoin (const CallICFGNode *forkSite, const CallICFGNode *joinSite)
	Whether it is a matched fork join pair. More...
ValDomain	getMarkedFlag (const CxtStmt &cs)
	Mark thread flags for cxtStmt. More...
void	markCxtStmtFlag (const CxtStmt &tgr, ValDomain flag)
	Initialize TDAlive and TDDead flags. More...
void	markCxtStmtFlag (const CxtStmt &tgr, const CxtStmt &src)
	Transfer function for marking context-sensitive statement. More...
void	clearFlagMap ()
	Clear flags. More...
bool	pushToCTSWorkList (const CxtStmt &cs)
	Worklist operations. More...
CxtStmt	popFromCTSWorkList ()
void	pushCxt (CallStrCxt &cxt, const CallICFGNode *call, const SVFFunction *callee)
	Push calling context. More...
bool	matchCxt (CallStrCxt &cxt, const CallICFGNode *call, const SVFFunction *callee)
	Match context. More...
bool	isTDFork (const ICFGNode *call)
	Whether it is a fork site. More...
bool	isTDJoin (const ICFGNode *call)
	Whether it is a join site. More...
const SVFVar *	getForkedThread (const CallICFGNode *call)
	Get forked thread. More...
const SVFVar *	getJoinedThread (const CallICFGNode *call)
	Get joined thread. More...
const PTACallGraph::FunctionSet &	getCallee (const ICFGNode *inst, PTACallGraph::FunctionSet &callees)
ThreadCallGraph *	getTCG () const
	ThreadCallGraph. More...
void	addDirectlyJoinTID (const CxtStmt &cs, NodeID tid)
	maps a context-sensitive join site to a thread id More...
void	addToHPPair (NodeID tid1, NodeID tid2)
void	addToHBPair (NodeID tid1, NodeID tid2)
void	addToFullJoin (NodeID tid1, NodeID tid2)
	full join and partial join More...
void	addToPartial (NodeID tid1, NodeID tid2)
void	addSymmetricLoopJoin (const CxtStmt &cs, LoopBBs &lp)
	Add inloop join. More...

Private Attributes
TCT *	tct
CxtStmtToAliveFlagMap	cxtStmtToAliveFlagMap
	flags for context-sensitive statements More...
CxtStmtWorkList	cxtStmtList
	context-sensitive statement worklist More...
CxtStmtToTIDMap	directJoinMap
	maps a context-sensitive join site to directly joined thread ids More...
CxtStmtToTIDMap	dirAndIndJoinMap
	maps a context-sensitive join site to directly and indirectly joined thread ids More...
CxtStmtToLoopMap	cxtJoinInLoop
	a set of context-sensitive join inside loop More...
ThreadPairSet	HBPair
	thread happens-before pair More...
ThreadPairSet	HPPair
	threads happen-in-parallel More...
ThreadPairSet	fullJoin
	t1 fully joins t2 along all program path More...
ThreadPairSet	partialJoin
	t1 partially joins t2 along some program path(s) More...

Detailed Description

Definition at line 273 of file MHP.h.

Member Typedef Documentation

CxtStmtToAliveFlagMap

typedef Map<CxtStmt,ValDomain> SVF::ForkJoinAnalysis::CxtStmtToAliveFlagMap

Definition at line 287 of file MHP.h.

CxtStmtToLoopMap

typedef Map<CxtStmt, LoopBBs> SVF::ForkJoinAnalysis::CxtStmtToLoopMap

Definition at line 290 of file MHP.h.

CxtStmtToTIDMap

typedef Map<CxtStmt,NodeBS> SVF::ForkJoinAnalysis::CxtStmtToTIDMap

Definition at line 288 of file MHP.h.

CxtStmtWorkList

typedef FIFOWorkList<CxtStmt> SVF::ForkJoinAnalysis::CxtStmtWorkList

Definition at line 291 of file MHP.h.

InstVec

typedef TCT::InstVec SVF::ForkJoinAnalysis::InstVec

Definition at line 286 of file MHP.h.

LoopBBs

typedef SVFLoopAndDomInfo::LoopBBs SVF::ForkJoinAnalysis::LoopBBs

Definition at line 285 of file MHP.h.

ThreadPairSet

typedef Set<NodePair> SVF::ForkJoinAnalysis::ThreadPairSet

Definition at line 289 of file MHP.h.

Member Enumeration Documentation

ValDomain

enum SVF::ForkJoinAnalysis::ValDomain

semilattice Empty==>TDDead==>TDAlive

Enumerator
Empty
TDAlive
TDDead

Definition at line 278 of file MHP.h.

    {
        Empty,  // initial(dummy) state
        TDAlive,  // thread is alive
        TDDead,  //  thread is dead
    };

Constructor & Destructor Documentation

ForkJoinAnalysis()

SVF::ForkJoinAnalysis::ForkJoinAnalysis ( TCT *  t )

inline

Definition at line 293 of file MHP.h.

                             : tct(t)
    {
        collectSCEVInfo();
    }

Member Function Documentation

addDirectlyJoinTID()

void SVF::ForkJoinAnalysis::addDirectlyJoinTID ( const CxtStmt &  cs, NodeID  tid  )

inlineprivate

maps a context-sensitive join site to a thread id

Definition at line 496 of file MHP.h.

    {
        directJoinMap[cs].set(tid);
    }

addSymmetricLoopJoin()

void SVF::ForkJoinAnalysis::addSymmetricLoopJoin ( const CxtStmt &  cs, LoopBBs &  lp  )

inlineprivate

Add inloop join.

Definition at line 528 of file MHP.h.

    {
        cxtJoinInLoop[cs] = lp;
    }

addToFullJoin()

void SVF::ForkJoinAnalysis::addToFullJoin ( NodeID  tid1, NodeID  tid2  )

inlineprivate

full join and partial join

Definition at line 517 of file MHP.h.

    {
        fullJoin.insert(std::make_pair(tid1,tid2));
    }

addToHBPair()

void SVF::ForkJoinAnalysis::addToHBPair ( NodeID  tid1, NodeID  tid2  )

inlineprivate

Definition at line 509 of file MHP.h.

    {
        HBPair.insert(std::make_pair(tid1,tid2));
    }

addToHPPair()

void SVF::ForkJoinAnalysis::addToHPPair ( NodeID  tid1, NodeID  tid2  )

inlineprivate

happen-in-parallel pair happens-before pair

Definition at line 504 of file MHP.h.

    {
        HPPair.insert(std::make_pair(tid1,tid2));
        HPPair.insert(std::make_pair(tid2,tid1));
    }

addToPartial()

void SVF::ForkJoinAnalysis::addToPartial ( NodeID  tid1, NodeID  tid2  )

inlineprivate

Definition at line 521 of file MHP.h.

    {
        partialJoin.insert(std::make_pair(tid1,tid2));
    }

analyzeForkJoinPair()

void ForkJoinAnalysis::analyzeForkJoinPair

(

)

context-sensitive forward traversal from each fork site. Generate following results (1) fork join pair, maps a context-sensitive join site to its corresponding thread ids (2) never happen-in-parallel thread pairs

Context-sensitive forward traversal from each fork site

Definition at line 721 of file MHP.cpp.

{
    for (const std::pair<const NodeID, TCTNode*>& tpair : *tct)
    {
        const CxtThread& ct = tpair.second->getCxtThread();
        const NodeID rootTid = tpair.first;
        clearFlagMap();
        if (const ICFGNode* forkInst = ct.getThread())
        {
            CallStrCxt forkSiteCxt = tct->getCxtOfCxtThread(ct);
            const ICFGNode* exitInst = getExitInstOfParentRoutineFun(rootTid);
 
            for(const ICFGEdge* outEdge : forkInst->getOutEdges())
            {
                if(outEdge->getDstNode()->getFun() == forkInst->getFun())
                {
                    CxtStmt newCts(forkSiteCxt, outEdge->getDstNode());
                    markCxtStmtFlag(newCts, TDAlive);
                }
            }
 
            while (!cxtStmtList.empty())
            {
                CxtStmt cts = popFromCTSWorkList();
                const ICFGNode* curInst = cts.getStmt();
                DBOUT(DMTA, outs() << "-----\nForkJoinAnalysis root thread: " << tpair.first << " ");
                DBOUT(DMTA, cts.dump());
                DBOUT(DMTA, outs() << "-----\n");
                PTACallGraph::FunctionSet callees;
                if (isTDFork(curInst))
                {
                    handleFork(cts, rootTid);
                }
                else if (isTDJoin(curInst))
                {
                    handleJoin(cts, rootTid);
                }
                else if (tct->isCallSite(curInst) && tct->isCandidateFun(getCallee(curInst, callees)))
                {
 
                    handleCall(cts, rootTid);
                }
                else if (isRetInstNode(curInst))
                {
                    handleRet(cts);
                }
                else
                {
                    handleIntra(cts);
                }
 
                if (curInst == exitInst)
                {
                    if (getMarkedFlag(cts) != TDAlive)
                        addToFullJoin(tct->getParentThread(rootTid), rootTid);
                    else
                        addToPartial(tct->getParentThread(rootTid), rootTid);
                }
            }
        }
    }
}

clearFlagMap()

void SVF::ForkJoinAnalysis::clearFlagMap ( )

inlineprivate

Clear flags.

Definition at line 432 of file MHP.h.

    {
        cxtStmtToAliveFlagMap.clear();
        cxtStmtList.clear();
    }

collectSCEVInfo()

void ForkJoinAnalysis::collectSCEVInfo

(

)

functions

Collect SCEV pass information for pointers at fork/join sites Because ScalarEvolution is a function pass, previous knowledge of a function may be overwritten when analyzing a new function. We use a internal wrapper class PTASCEV to record all the necessary information for determining symmetric fork/join inside loops

Definition at line 667 of file MHP.cpp.

{
    // typedef Set<const ICFGNode*> CallInstSet;
    // typedef Map<const SVFFunction*, CallInstSet> FunToFJSites;
    // FunToFJSites funToFJSites;
 
    // for (ThreadCallGraph::CallSiteSet::const_iterator it = tct->getThreadCallGraph()->forksitesBegin(),
    //         eit = tct->getThreadCallGraph()->forksitesEnd();
    //         it != eit; ++it)
    // {
    //     const ICFGNode* fork = *it;
    //     funToFJSites[fork->getFun()].insert(fork);
    // }
 
    // for (ThreadCallGraph::CallSiteSet::const_iterator it = tct->getThreadCallGraph()->joinsitesBegin(),
    //         eit = tct->getThreadCallGraph()->joinsitesEnd();
    //         it != eit; ++it)
    // {
    //     const ICFGNode* join = *it;
    //     funToFJSites[join->getFun()].insert(join);
    // }
 
    // for(FunToFJSites::const_iterator it = funToFJSites.begin(), eit = funToFJSites.end(); it!=eit; ++it)
    // {
    //     // ScalarEvolution* SE = MTA::getSE(it->first);
    //     for(CallInstSet::const_iterator sit = it->second.begin(), esit = it->second.end(); sit!=esit; ++sit)
    //     {
    //         const SVFInstruction* callInst =  *sit;
    //         if(tct->getThreadCallGraph()->isForksite(getCBN(callInst)))
    //         {
    //             // const SVFValue* forkSiteTidPtr = getForkedThread(callInst);
    //             // const SCEV *forkSiteTidPtrSCEV = SE->getSCEV(const_cast<Value*>(forkSiteTidPtr));
    //             // const SCEV *baseForkTidPtrSCEV = SE->getSCEV(const_cast<Value*>(getBasePtr(forkSiteTidPtr)));
    //             // forkSiteTidPtrSCEV = getSCEVMinusExpr(forkSiteTidPtrSCEV, baseForkTidPtrSCEV, SE);
    //             // PTASCEV scev(forkSiteTidPtr,nullptr,nullptr);
    //             // fkjnToPTASCEVMap.insert(std::make_pair(callInst,scev));
    //         }
    //         else
    //         {
    //             // const SVFValue* joinSiteTidPtr = getJoinedThread(callInst);
    //             //const SCEV *joinSiteTidPtrSCEV = SE->getSCEV(const_cast<Value*>(joinSiteTidPtr));
    //             //const SCEV *baseJoinTidPtrSCEV = SE->getSCEV(const_cast<Value*>(getBasePtr(joinSiteTidPtr)));
    //             //joinSiteTidPtrSCEV = getSCEVMinusExpr(joinSiteTidPtrSCEV, baseJoinTidPtrSCEV, SE);
 
    //             // PTASCEV scev(joinSiteTidPtr,nullptr,nullptr);
    //             // fkjnToPTASCEVMap.insert(std::make_pair(callInst,scev));
    //         }
    //     }
    // }
}

getCallee()

const PTACallGraph::FunctionSet& SVF::ForkJoinAnalysis::getCallee ( const ICFGNode *  inst, PTACallGraph::FunctionSet &  callees  )

inlineprivate

Definition at line 485 of file MHP.h.

    {
        getTCG()->getCallees(SVFUtil::cast<CallICFGNode>(inst), callees);
        return callees;
    }

getDirAndIndJoinedTid()

NodeBS ForkJoinAnalysis::getDirAndIndJoinedTid

(

const CxtStmt &

cs

)

Get directly and indirectly joined threadIDs based on a context-sensitive join site.

Return thread id(s) which are joined at this join site (1) thread t1 directly joins thread t2 (2) thread t1 indirectly joins thread t3 via directly joining t2 (t2 fully joins its child thread t3)

Definition at line 974 of file MHP.cpp.

{
 
    CxtStmtToTIDMap::const_iterator it = dirAndIndJoinMap.find(cs);
    if (it != dirAndIndJoinMap.end())
        return it->second;
 
    const NodeBS& directJoinTids = getDirectlyJoinedTid(cs);
    NodeBS allJoinTids = directJoinTids;
 
    FIFOWorkList<NodeID> worklist;
    for (unsigned id : directJoinTids)
    {
        worklist.push(id);
    }
 
    while (!worklist.empty())
    {
        NodeID tid = worklist.pop();
        TCTNode* node = tct->getTCTNode(tid);
        for (TCT::ThreadCreateEdgeSet::const_iterator it = tct->getChildrenBegin(node), eit = tct->getChildrenEnd(node); it != eit; ++it)
        {
            NodeID childTid = (*it)->getDstID();
            if (isFullJoin(tid, childTid))
            {
                allJoinTids.set(childTid);
                worklist.push(childTid);
            }
        }
    }
 
    dirAndIndJoinMap[cs] = allJoinTids;
 
    return allJoinTids;
}

getDirectlyJoinedTid()

NodeBS& SVF::ForkJoinAnalysis::getDirectlyJoinedTid ( const CxtStmt &  cs )

inline

Get directly joined threadIDs based on a context-sensitive join site.

Definition at line 306 of file MHP.h.

    {
        return directJoinMap[cs];
    }

getExitInstOfParentRoutineFun()

const ICFGNode* SVF::ForkJoinAnalysis::getExitInstOfParentRoutineFun ( NodeID  tid ) const

inline

Get exit instruction of the start routine function of tid's parent thread.

Definition at line 341 of file MHP.h.

    {
        NodeID parentTid = tct->getParentThread(tid);
        const CxtThread& parentct = tct->getTCTNode(parentTid)->getCxtThread();
        const SVFFunction* parentRoutine = tct->getStartRoutineOfCxtThread(parentct);
        return parentRoutine->getExitBB()->back();
    }

getForkedThread()

const SVFVar* SVF::ForkJoinAnalysis::getForkedThread ( const CallICFGNode *  call )

inlineprivate

Get forked thread.

Definition at line 476 of file MHP.h.

    {
        return getTCG()->getThreadAPI()->getForkedThread(call);
    }

getJoinedThread()

const SVFVar* SVF::ForkJoinAnalysis::getJoinedThread ( const CallICFGNode *  call )

inlineprivate

Get joined thread.

Definition at line 481 of file MHP.h.

    {
        return getTCG()->getThreadAPI()->getJoinedThread(call);
    }

getJoinInSymmetricLoop()

const LoopBBs& SVF::ForkJoinAnalysis::getJoinInSymmetricLoop ( const CxtStmt &  cs ) const

inline

Whether a context-sensitive join satisfies symmetric loop pattern.

Definition at line 314 of file MHP.h.

    {
        CxtStmtToLoopMap::const_iterator it = cxtJoinInLoop.find(cs);
        assert(it!=cxtJoinInLoop.end() && "does not have the loop");
        return it->second;
    }

getJoinLoop()

LoopBBs& SVF::ForkJoinAnalysis::getJoinLoop ( const CallICFGNode *  inst )

inline

Get loop for join site.

Definition at line 350 of file MHP.h.

    {
        return tct->getJoinLoop(inst);
    }

getMarkedFlag()

ValDomain SVF::ForkJoinAnalysis::getMarkedFlag ( const CxtStmt &  cs )

inlineprivate

Mark thread flags for cxtStmt.

Get the flag for a cxtStmt

Definition at line 389 of file MHP.h.

    {
        CxtStmtToAliveFlagMap::const_iterator it = cxtStmtToAliveFlagMap.find(cs);
        if(it==cxtStmtToAliveFlagMap.end())
        {
            cxtStmtToAliveFlagMap[cs] = Empty;
            return Empty;
        }
        else
            return it->second;
    }

getTCG()

ThreadCallGraph* SVF::ForkJoinAnalysis::getTCG ( ) const

inlineprivate

ThreadCallGraph.

Definition at line 491 of file MHP.h.

    {
        return tct->getThreadCallGraph();
    }

handleCall()

void ForkJoinAnalysis::handleCall ( const CxtStmt &  cts, NodeID  rootTid  )

private

Handle call.

Definition at line 877 of file MHP.cpp.

{
 
    const ICFGNode* call = cts.getStmt();
    const CallStrCxt& curCxt = cts.getContext();
    const CallICFGNode* cbn = SVFUtil::cast<CallICFGNode>(call);
    if (getTCG()->hasCallGraphEdge(cbn))
    {
        for (PTACallGraph::CallGraphEdgeSet::const_iterator cgIt = getTCG()->getCallEdgeBegin(cbn),
                ecgIt = getTCG()->getCallEdgeEnd(cbn);
                cgIt != ecgIt; ++cgIt)
        {
            const SVFFunction* svfcallee = (*cgIt)->getDstNode()->getFunction();
            if (isExtCall(svfcallee))
                continue;
            CallStrCxt newCxt = curCxt;
            pushCxt(newCxt, cbn, svfcallee);
            const ICFGNode* svfEntryInst = svfcallee->getEntryBlock()->front();
            CxtStmt newCts(newCxt, svfEntryInst);
            markCxtStmtFlag(newCts, cts);
        }
    }
}

handleFork()

void ForkJoinAnalysis::handleFork ( const CxtStmt &  cts, NodeID  rootTid  )

private

Handle fork.

Definition at line 785 of file MHP.cpp.

{
    const ICFGNode* call = cts.getStmt();
    const CallStrCxt& curCxt = cts.getContext();
 
    assert(isTDFork(call));
    const CallICFGNode* cbn = cast<CallICFGNode>(call);
    if (getTCG()->hasThreadForkEdge(cbn))
    {
        for (ThreadCallGraph::ForkEdgeSet::const_iterator cgIt = getTCG()->getForkEdgeBegin(cbn),
                ecgIt = getTCG()->getForkEdgeEnd(cbn);
                cgIt != ecgIt; ++cgIt)
        {
            const SVFFunction* callee = (*cgIt)->getDstNode()->getFunction();
            CallStrCxt newCxt = curCxt;
            pushCxt(newCxt, cbn, callee);
            CxtThread ct(newCxt, call);
            if (getMarkedFlag(cts) != TDAlive)
                addToHBPair(rootTid, tct->getTCTNode(ct)->getId());
            else
                addToHPPair(rootTid, tct->getTCTNode(ct)->getId());
        }
    }
    handleIntra(cts);
}

handleIntra()

void ForkJoinAnalysis::handleIntra ( const CxtStmt &  cts )

private

Handle intra.

Definition at line 953 of file MHP.cpp.

{
 
    const ICFGNode* curInst = cts.getStmt();
    const CallStrCxt& curCxt = cts.getContext();
 
    for(const ICFGEdge* outEdge : curInst->getOutEdges())
    {
        if(outEdge->getDstNode()->getFun() == curInst->getFun())
        {
            CxtStmt newCts(curCxt, outEdge->getDstNode());
            markCxtStmtFlag(newCts, cts);
        }
    }
}

handleJoin()

void ForkJoinAnalysis::handleJoin ( const CxtStmt &  cts, NodeID  rootTid  )

private

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 812 of file MHP.cpp.

{
    const ICFGNode* call = cts.getStmt();
    const CallStrCxt& curCxt = cts.getContext();
 
    assert(isTDJoin(call));
    const CallICFGNode* cbn = cast<CallICFGNode>(call);
    if (getTCG()->hasCallGraphEdge(cbn))
    {
        const ICFGNode* forkSite = tct->getTCTNode(rootTid)->getCxtThread().getThread();
        const ICFGNode* joinSite = cts.getStmt();
 
        if (isAliasedForkJoin(SVFUtil::cast<CallICFGNode>(forkSite), SVFUtil::cast<CallICFGNode>(joinSite)))
        {
            if (hasJoinLoop(SVFUtil::cast<CallICFGNode>(forkSite)))
            {
                LoopBBs& joinLoop = getJoinLoop(SVFUtil::cast<CallICFGNode>(forkSite));
                std::vector<const SVFBasicBlock *> exitbbs;
                joinSite->getFun()->getExitBlocksOfLoop(joinSite->getBB(), exitbbs);
                while (!exitbbs.empty())
                {
                    const SVFBasicBlock* eb = exitbbs.back();
                    exitbbs.pop_back();
                    const ICFGNode* svfEntryInst = eb->front();
                    CxtStmt newCts(curCxt, svfEntryInst);
                    addDirectlyJoinTID(cts, rootTid);
                    if (isSameSCEV(forkSite, joinSite))
                    {
                        markCxtStmtFlag(newCts, TDDead);
                        addSymmetricLoopJoin(cts, joinLoop);
                    }
                    else
                        markCxtStmtFlag(cts, TDAlive);
                }
            }
            else
            {
                markCxtStmtFlag(cts, TDDead);
                addDirectlyJoinTID(cts, rootTid);
                DBOUT(DMTA, outs() << "\n\t match join site " << call->toString() << "for thread " << rootTid << "\n");
            }
        }
        else
        {
            if (hasJoinLoop(SVFUtil::cast<CallICFGNode>(forkSite)))
            {
                std::vector<const SVFBasicBlock*> exitbbs;
                joinSite->getFun()->getExitBlocksOfLoop(joinSite->getBB(), exitbbs);
                while (!exitbbs.empty())
                {
                    const SVFBasicBlock* eb = exitbbs.back();
                    exitbbs.pop_back();
                    const ICFGNode* svfEntryInst = eb->front();
                    CxtStmt newCts(curCxt, svfEntryInst);
                    markCxtStmtFlag(newCts, cts);
                }
            }
        }
    }
    handleIntra(cts);
}

handleRet()

void ForkJoinAnalysis::handleRet ( const CxtStmt &  cts )

private

Handle return.

Definition at line 902 of file MHP.cpp.

{
    const ICFGNode* curInst = cts.getStmt();
    const CallStrCxt& curCxt = cts.getContext();
 
    PTACallGraphNode* curFunNode = getTCG()->getCallGraphNode(curInst->getFun());
    for (PTACallGraphEdge* edge : curFunNode->getInEdges())
    {
        if (SVFUtil::isa<ThreadForkEdge, ThreadJoinEdge>(edge))
            continue;
        for (PTACallGraphEdge::CallInstSet::const_iterator cit = edge->directCallsBegin(),
                ecit = edge->directCallsEnd();
                cit != ecit; ++cit)
        {
            CallStrCxt newCxt = curCxt;
            const ICFGNode* curNode = (*cit);
            if (matchCxt(newCxt, SVFUtil::cast<CallICFGNode>(curNode), curFunNode->getFunction()))
            {
                for(const ICFGEdge* outEdge : curNode->getOutEdges())
                {
                    if(outEdge->getDstNode()->getFun() == curNode->getFun())
                    {
                        CxtStmt newCts(newCxt, outEdge->getDstNode());
                        markCxtStmtFlag(newCts, cts);
                    }
                }
            }
        }
        for (PTACallGraphEdge::CallInstSet::const_iterator cit = edge->indirectCallsBegin(),
                ecit = edge->indirectCallsEnd();
                cit != ecit; ++cit)
        {
            CallStrCxt newCxt = curCxt;
            const ICFGNode* curNode = (*cit);
 
            if (matchCxt(newCxt, SVFUtil::cast<CallICFGNode>(curNode), curFunNode->getFunction()))
            {
                for(const ICFGEdge* outEdge : curNode->getOutEdges())
                {
                    if(outEdge->getDstNode()->getFun() == curNode->getFun())
                    {
                        CxtStmt newCts(newCxt, outEdge->getDstNode());
                        markCxtStmtFlag(newCts, cts);
                    }
                }
            }
        }
    }
}

hasJoinInSymmetricLoop()

bool SVF::ForkJoinAnalysis::hasJoinInSymmetricLoop ( const CxtStmt &  cs ) const

inline

Definition at line 320 of file MHP.h.

    {
        CxtStmtToLoopMap::const_iterator it = cxtJoinInLoop.find(cs);
        return it!=cxtJoinInLoop.end();
    }

hasJoinLoop()

bool SVF::ForkJoinAnalysis::hasJoinLoop ( const CallICFGNode *  inst )

inline

Definition at line 354 of file MHP.h.

    {
        return tct->hasJoinLoop(inst);
    }

isAliasedForkJoin()

bool SVF::ForkJoinAnalysis::isAliasedForkJoin ( const CallICFGNode *  forkSite, const CallICFGNode *  joinSite  )

inlineprivate

Whether it is a matched fork join pair.

Definition at line 382 of file MHP.h.

    {
        return tct->getPTA()->alias(getForkedThread(forkSite)->getId(), getJoinedThread(joinSite)->getId()) && isSameSCEV(forkSite,joinSite);
    }

isFullJoin()

bool SVF::ForkJoinAnalysis::isFullJoin ( NodeID  tid1, NodeID  tid2  )

inline

Whether t1 fully joins t2.

Definition at line 333 of file MHP.h.

    {
        bool full = fullJoin.find(std::make_pair(tid1,tid2))!=fullJoin.end();
        bool partial = partialJoin.find(std::make_pair(tid1,tid2))!=partialJoin.end();
        return full && !partial;
    }

isHBPair()

bool SVF::ForkJoinAnalysis::isHBPair ( NodeID  tid1, NodeID  tid2  )

inline

Whether thread t1 happens-before thread t2.

Definition at line 326 of file MHP.h.

    {
        bool nonhp = HBPair.find(std::make_pair(tid1,tid2))!=HBPair.end();
        bool hp = HPPair.find(std::make_pair(tid1,tid2))!=HPPair.end();
        return nonhp && !hp;
    }

isSameSCEV()

bool ForkJoinAnalysis::isSameSCEV ( const ICFGNode *  forkSite, const ICFGNode *  joinSite  )

private

Return true if the fork and join have the same SCEV.

We assume a pair of fork and join sites are must-alias if they have same PTASCEV (1) SCEV not inside loop (2) SCEV inside two symmetric loops, then pointers of fork thread and join thread should have same scev start and step. and should have same loop trip count

Definition at line 1049 of file MHP.cpp.

{
 
    // const PTASCEV& forkse = fkjnToPTASCEVMap[forkSite];
    // const PTASCEV& joinse = fkjnToPTASCEVMap[joinSite];
 
    // //if(sameLoopTripCount(forkSite,joinSite) == false)
    // //  return false;
 
    // if(forkse.inloop && joinse.inloop)
    //     return forkse.start==joinse.start && forkse.step == joinse.step && forkse.tripcount <= joinse.tripcount;
    // else if(SVFUtil::isa<GetElementPtrInst>(forkse.ptr) && SVFUtil::isa<GetElementPtrInst>(joinse.ptr))
    //     return accessSameArrayIndex(SVFUtil::cast<GetElementPtrInst>(forkse.ptr),SVFUtil::cast<GetElementPtrInst>(joinse.ptr));
    // else if(SVFUtil::isa<GetElementPtrInst, GetElementPtrInst>(joinse.ptr))
    //     return false;
    // else
    //     return true;
 
    return false;
}

isTDFork()

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

inlineprivate

Whether it is a fork site.

Definition at line 464 of file MHP.h.

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

isTDJoin()

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

inlineprivate

Whether it is a join site.

Definition at line 470 of file MHP.h.

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

markCxtStmtFlag() [1/2]

void SVF::ForkJoinAnalysis::markCxtStmtFlag ( const CxtStmt &  tgr, const CxtStmt &  src  )

inlineprivate

Transfer function for marking context-sensitive statement.

alive is at the bottom of the semilattice, nothing needs to be done here

Definition at line 409 of file MHP.h.

    {
        ValDomain flag_tgr = getMarkedFlag(tgr);
        ValDomain flag_src = getMarkedFlag(src);
        if(flag_tgr == Empty)
        {
            cxtStmtToAliveFlagMap[tgr] = flag_src;
        }
        else if(flag_tgr == TDDead)
        {
            if(flag_src==TDAlive)
                cxtStmtToAliveFlagMap[tgr] = TDAlive;
        }
        else
        {
        }
        if(flag_tgr!=getMarkedFlag(tgr))
        {
            pushToCTSWorkList(tgr);
        }
    }

markCxtStmtFlag() [2/2]

void SVF::ForkJoinAnalysis::markCxtStmtFlag ( const CxtStmt &  tgr, ValDomain  flag  )

inlineprivate

Initialize TDAlive and TDDead flags.

Definition at line 401 of file MHP.h.

    {
        ValDomain flag_tgr = getMarkedFlag(tgr);
        cxtStmtToAliveFlagMap[tgr] = flag;
        if(flag_tgr!=getMarkedFlag(tgr))
            pushToCTSWorkList(tgr);
    }

matchCxt()

bool SVF::ForkJoinAnalysis::matchCxt ( CallStrCxt &  cxt, const CallICFGNode *  call, const SVFFunction *  callee  )

inlineprivate

Match context.

Definition at line 458 of file MHP.h.

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

popFromCTSWorkList()

CxtStmt SVF::ForkJoinAnalysis::popFromCTSWorkList ( )

inlineprivate

Definition at line 445 of file MHP.h.

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

pushCxt()

void SVF::ForkJoinAnalysis::pushCxt ( CallStrCxt &  cxt, const CallICFGNode *  call, const SVFFunction *  callee  )

inlineprivate

Push calling context.

Definition at line 453 of file MHP.h.

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

pushToCTSWorkList()

bool SVF::ForkJoinAnalysis::pushToCTSWorkList ( const CxtStmt &  cs )

inlineprivate

Worklist operations.

Definition at line 441 of file MHP.h.

    {
        return cxtStmtList.push(cs);
    }

sameLoopTripCount()

bool ForkJoinAnalysis::sameLoopTripCount ( const ICFGNode *  forkSite, const ICFGNode *  joinSite  )

private

Same loop trip count.

The fork and join have same loop trip count

Definition at line 1073 of file MHP.cpp.

{
 
    // ScalarEvolution* forkSE = getSE(forkSite);
    // ScalarEvolution* joinSE = getSE(joinSite);
 
    // if(tct->hasLoop(forkSite) == false || tct->hasLoop(joinSite) == false)
    //     return false;
 
    // // Get loops
    // const LoopBBs& forkSiteLoop = tct->getLoop(forkSite);
    // const LoopBBs& joinSiteLoop = tct->getLoop(joinSite);
 
    // const SCEV* forkLoopCountScev = forkSE->getBackedgeTakenCount(forkSiteLoop);
    // const SCEV* joinLoopCountScev = joinSE->getBackedgeTakenCount(joinSiteLoop);
 
    // if(forkLoopCountScev!=forkSE->getCouldNotCompute())
    // {
    //     if(forkLoopCountScev==joinLoopCountScev)
    //     {
    //         return true;
    //     }
    // }
    return false;
}

Member Data Documentation

cxtJoinInLoop

CxtStmtToLoopMap SVF::ForkJoinAnalysis::cxtJoinInLoop

private

a set of context-sensitive join inside loop

Definition at line 537 of file MHP.h.

cxtStmtList

CxtStmtWorkList SVF::ForkJoinAnalysis::cxtStmtList

private

context-sensitive statement worklist

Definition at line 534 of file MHP.h.

cxtStmtToAliveFlagMap

CxtStmtToAliveFlagMap SVF::ForkJoinAnalysis::cxtStmtToAliveFlagMap

private

flags for context-sensitive statements

Definition at line 533 of file MHP.h.

dirAndIndJoinMap

CxtStmtToTIDMap SVF::ForkJoinAnalysis::dirAndIndJoinMap

private

maps a context-sensitive join site to directly and indirectly joined thread ids

Definition at line 536 of file MHP.h.

directJoinMap

CxtStmtToTIDMap SVF::ForkJoinAnalysis::directJoinMap

private

maps a context-sensitive join site to directly joined thread ids

Definition at line 535 of file MHP.h.

fullJoin

ThreadPairSet SVF::ForkJoinAnalysis::fullJoin

private

t1 fully joins t2 along all program path

Definition at line 540 of file MHP.h.

HBPair

ThreadPairSet SVF::ForkJoinAnalysis::HBPair

private

thread happens-before pair

Definition at line 538 of file MHP.h.

HPPair

ThreadPairSet SVF::ForkJoinAnalysis::HPPair

private

threads happen-in-parallel

Definition at line 539 of file MHP.h.

partialJoin

ThreadPairSet SVF::ForkJoinAnalysis::partialJoin

private

t1 partially joins t2 along some program path(s)

Definition at line 541 of file MHP.h.

tct

TCT* SVF::ForkJoinAnalysis::tct

private

Definition at line 532 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