#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

typedef Set< CxtStmt >	CxtStmtSet

typedef Map< const ICFGNode *, CxtStmtSet >	InstToCxtStmt

Public Member Functions
	ForkJoinAnalysis (TCT *t)

void	collectSCEVInfo ()
	functions

void	analyzeForkJoinPair ()

NodeBS &	getDirectlyJoinedTid (const CxtStmt &cs)
	Get directly joined threadIDs based on a context-sensitive join site.

NodeBS	getDirAndIndJoinedTid (const CxtStmt &cs)
	Get directly and indirectly joined threadIDs based on a context-sensitive join site.

const LoopBBs &	getJoinInSymmetricLoop (const CxtStmt &cs) const
	Whether a context-sensitive join satisfies symmetric loop pattern.

bool	hasJoinInSymmetricLoop (const CxtStmt &cs) const

bool	isHBPair (NodeID tid1, NodeID tid2)
	Whether thread t1 happens-before thread t2.

bool	isFullJoin (NodeID tid1, NodeID tid2)
	Whether t1 fully joins t2.

LoopBBs &	getJoinLoop (const CallICFGNode *inst)
	Get loop for join site.

bool	hasJoinLoop (const CallICFGNode *inst)

Private Member Functions
void	handleFork (const CxtStmt &cts, NodeID rootTid)
	Handle fork.

void	handleJoin (const CxtStmt &cts, NodeID rootTid)
	Handle join.

void	handleCall (const CxtStmt &cts, NodeID rootTid)
	Handle call.

void	handleRet (const CxtStmt &cts)
	Handle return.

void	handleIntra (const CxtStmt &cts)
	Handle intra.

bool	isSameSCEV (const ICFGNode forkSite, const ICFGNode joinSite)
	Return true if the fork and join have the same SCEV.

bool	sameLoopTripCount (const ICFGNode forkSite, const ICFGNode joinSite)
	Same loop trip count.

bool	isAliasedForkJoin (const CallICFGNode forkSite, const CallICFGNode joinSite)
	Whether it is a matched fork join pair.

ValDomain	getMarkedFlag (const CxtStmt &cs)
	Mark thread flags for cxtStmt.

void	markCxtStmtFlag (const CxtStmt &tgr, ValDomain flag)
	Initialize TDAlive and TDDead flags.

void	markCxtStmtFlag (const CxtStmt &tgr, const CxtStmt &src)
	Transfer function for marking context-sensitive statement.

void	clearFlagMap ()
	Clear flags.

bool	pushToCTSWorkList (const CxtStmt &cs)
	Worklist operations.

CxtStmt	popFromCTSWorkList ()

void	pushCxt (CallStrCxt &cxt, const CallICFGNode call, const FunObjVar callee)
	Context helper functions.

bool	matchAndPopCxt (CallStrCxt &cxt, const CallICFGNode call, const FunObjVar callee)
	Match context.

bool	isContextSuffix (const CallStrCxt &lhs, const CallStrCxt call)
	If lhs is a suffix of rhs, including equal.

bool	isTDFork (const ICFGNode *call)
	Whether it is a fork site.

bool	isTDJoin (const ICFGNode *call)
	Whether it is a join site.

const SVFVar *	getForkedThread (const CallICFGNode *call)
	Get forked thread.

const SVFVar *	getJoinedThread (const CallICFGNode *call)
	Get joined thread.

const CallGraph::FunctionSet &	getCallee (const ICFGNode *inst, CallGraph::FunctionSet &callees)

ThreadCallGraph *	getTCG () const
	ThreadCallGraph.

void	addDirectlyJoinTID (const CxtStmt &cs, NodeID tid)
	maps a context-sensitive join site to a thread id

void	addToHPPair (NodeID tid1, NodeID tid2)

void	addToHBPair (NodeID tid1, NodeID tid2)

void	addToFullJoin (NodeID tid1, NodeID tid2)
	full join and partial join

void	addToPartial (NodeID tid1, NodeID tid2)

const CxtStmtSet &	getCxtStmtsFromInst (const ICFGNode *inst) const
	Get CxtStmtSet for an instruction.

bool	hasCxtStmtsFromInst (const ICFGNode *inst) const

void	addSymmetricLoopJoin (const CxtStmt &cs, LoopBBs &lp)
	Add inloop join.

Private Attributes
TCT *	tct

CxtStmtToAliveFlagMap	cxtStmtToAliveFlagMap
	flags for context-sensitive statements

CxtStmtWorkList	cxtStmtList
	context-sensitive statement worklist

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

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

CxtStmtToLoopMap	cxtJoinInLoop
	a set of context-sensitive join inside loop

ThreadPairSet	HBPair
	thread happens-before pair

ThreadPairSet	HPPair
	threads happen-in-parallel

ThreadPairSet	fullJoin
	t1 fully joins t2 along all program path

ThreadPairSet	partialJoin
	t1 partially joins t2 along some program path(s)

InstToCxtStmt	instToCxtStmt
	Map a statement to all its context-sensitive statements.

Detailed Description

Definition at line 286 of file MHP.h.

Member Typedef Documentation

◆ CxtStmtSet

typedef Set<CxtStmt> SVF::ForkJoinAnalysis::CxtStmtSet

Definition at line 306 of file MHP.h.

◆ CxtStmtToAliveFlagMap

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

Definition at line 300 of file MHP.h.

◆ CxtStmtToLoopMap

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

Definition at line 303 of file MHP.h.

◆ CxtStmtToTIDMap

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

Definition at line 301 of file MHP.h.

◆ CxtStmtWorkList

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

Definition at line 304 of file MHP.h.

◆ InstToCxtStmt

typedef Map<const ICFGNode*, CxtStmtSet> SVF::ForkJoinAnalysis::InstToCxtStmt

Definition at line 307 of file MHP.h.

◆ InstVec

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

Definition at line 299 of file MHP.h.

◆ LoopBBs

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

Definition at line 298 of file MHP.h.

◆ ThreadPairSet

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

Definition at line 302 of file MHP.h.

Member Enumeration Documentation

◆ ValDomain

enum SVF::ForkJoinAnalysis::ValDomain

semilattice Empty==>TDDead==>TDAlive

Enumerator
Empty
TDAlive
TDDead

Definition at line 291 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 310 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 520 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 564 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 541 of file MHP.h.

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

◆ addToHBPair()

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

inlineprivate

Definition at line 533 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 528 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 545 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

Start from the instruction next to the fork site

Propagate to the return site of the call instruction, only if the callee is a non-candidate function, while for candidate function, return site should be handled after the callee is handled.

If the current instruction is an exit instruction of the start routine of a parent context thread, we need to update the join information the parent context thread.

Definition at line 760 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())
        {
            for(const ICFGEdge* outEdge : forkInst->getOutEdges())
            {
                if(outEdge->getDstNode()->getFun() == forkInst->getFun())
                {
                    for (const auto& forkSiteCxt : tct->getCxtOfCxtThread(ct))
                    {
                        CxtStmt newCts(forkSiteCxt.second, 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");
                CallGraph::FunctionSet callees;
                if (isTDFork(curInst))
                {
                    handleFork(cts, rootTid);
                }
                else if (isTDJoin(curInst))
                {
                    handleJoin(cts, rootTid);
                }
                else if (tct->isCallSite(curInst) && !tct->isExtCall(curInst))
                {
                    const CallICFGNode *callSite = SVFUtil::cast<CallICFGNode>(curInst);
                    CallGraph::FunctionSet callees;
                    if (!tct->isCandidateFun(getCallee(callSite, callees)))
                    {
                        // Do not dive into non-candidate functions
                        CxtStmt newCts(cts.getContext(), callSite->getRetICFGNode());
                        markCxtStmtFlag(newCts, cts);
                    }
                    else
                    {
                        handleCall(cts, rootTid);
                    }
                }
                else if (SVFUtil::dyn_cast<FunExitICFGNode>(curInst))
                {
                    handleRet(cts);
                }
                else
                {
                    handleIntra(cts);
                }
 
                for (NodeID parentTid : tct->getParentThreads(rootTid))
                {
                    const CxtThread& parentCxtThread = tct->getTCTNode(parentTid)->getCxtThread();
                    const FunObjVar* parentRoutine = tct->getStartRoutineOfCxtThread(parentCxtThread);
                    if (curInst == parentRoutine->getExitBB()->back())
                    {
                        if (getMarkedFlag(cts) != TDAlive)
                            addToFullJoin(parentTid, rootTid);
                        else
                            addToPartial(parentTid, rootTid);
                    }
                }
            }
        }
    }
}

◆ clearFlagMap()

void SVF::ForkJoinAnalysis::clearFlagMap ( )

inlineprivate

Clear flags.

Definition at line 445 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 706 of file MHP.cpp.

{
    // typedef Set<const ICFGNode*> CallInstSet;
    // typedef Map<const FunObjVar*, 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 CallGraph::FunctionSet & SVF::ForkJoinAnalysis::getCallee	(	const ICFGNode *	inst,
		CallGraph::FunctionSet &	callees
	)

inlineprivate

Definition at line 509 of file MHP.h.

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

◆ getCxtStmtsFromInst()

const CxtStmtSet & SVF::ForkJoinAnalysis::getCxtStmtsFromInst ( const ICFGNode * inst ) const

inlineprivate

Get CxtStmtSet for an instruction.

Definition at line 552 of file MHP.h.

    {
        InstToCxtStmt::const_iterator it = instToCxtStmt.find(inst);
        assert(it!=instToCxtStmt.end() && "no CxtStmt for the instruction?");
        return it->second;
    }

◆ 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 1061 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 323 of file MHP.h.

    {
        return directJoinMap[cs];
    }

◆ getForkedThread()

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

inlineprivate

Get forked thread.

Definition at line 500 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 505 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 331 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 358 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 397 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 515 of file MHP.h.

    {
        return tct->getThreadCallGraph();
    }

◆ handleCall()

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

private

Handle call.

Definition at line 942 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 (CallGraph::CallGraphEdgeSet::const_iterator cgIt = getTCG()->getCallEdgeBegin(cbn),
                ecgIt = getTCG()->getCallEdgeEnd(cbn);
                cgIt != ecgIt; ++cgIt)
        {
            const FunObjVar* 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 846 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 FunObjVar* 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 1040 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 873 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 (hasJoinLoop(SVFUtil::cast<CallICFGNode>(joinSite)))
        {
            if (isAliasedForkJoin(SVFUtil::cast<CallICFGNode>(forkSite),
                                  SVFUtil::cast<CallICFGNode>(joinSite)) &&
                    isSameSCEV(forkSite,joinSite)
               )
            {
                LoopBBs& joinLoop = getJoinLoop(SVFUtil::cast<CallICFGNode>(joinSite));
                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
            {
                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);
                }
            }
        }
        else
        {
            if (isAliasedForkJoin(SVFUtil::cast<CallICFGNode>(forkSite),
                                  SVFUtil::cast<CallICFGNode>(joinSite)))
            {
                markCxtStmtFlag(cts, TDDead);
                addDirectlyJoinTID(cts, rootTid);
                DBOUT(DMTA, outs() << "\n\t match join site " << call->toString() << "for thread " << rootTid << "\n");
            }
        }
    }
    handleIntra(cts);
}

◆ handleRet()

void ForkJoinAnalysis::handleRet ( const CxtStmt & cts )

private

Handle return.

Definition at line 967 of file MHP.cpp.

{
    const ICFGNode* curInst = cts.getStmt();
    const CallStrCxt& curCxt = cts.getContext();
 
    CallGraphNode* curFunNode = getTCG()->getCallGraphNode(curInst->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 = curCxt;
            const ICFGNode* curNode = (*cit);
            if (matchAndPopCxt(newCxt, SVFUtil::cast<CallICFGNode>(curNode), curFunNode->getFunction()))
            {
                for(const ICFGEdge* outEdge : curNode->getOutEdges())
                {
                    if(outEdge->getDstNode()->getFun() == curNode->getFun())
                    {
                        // Iterate over callSite's call string context and use as the successor's context
                        if (!hasCxtStmtsFromInst(*cit))
                            continue;
                        for (const CxtStmt& cxtStmt: getCxtStmtsFromInst(*cit))
                        {
                            CallStrCxt callSiteCxt = cxtStmt.getContext();
                            // If new context is a suffix of the call site context
                            if (isContextSuffix(newCxt, callSiteCxt))
                            {
                                CxtStmt newCts(callSiteCxt, outEdge->getDstNode());
                                markCxtStmtFlag(newCts, cts);
                            }
                        }
                    }
                }
            }
        }
        for (CallGraphEdge::CallInstSet::const_iterator cit = edge->indirectCallsBegin(),
                ecit = edge->indirectCallsEnd();
                cit != ecit; ++cit)
        {
            CallStrCxt newCxt = curCxt;
            const ICFGNode* curNode = (*cit);
 
            if (matchAndPopCxt(newCxt, SVFUtil::cast<CallICFGNode>(curNode), curFunNode->getFunction()))
            {
                for(const ICFGEdge* outEdge : curNode->getOutEdges())
                {
                    if(outEdge->getDstNode()->getFun() == curNode->getFun())
                    {
                        // Iterate over callSite's call string context and use as the successor's context
                        if (!hasCxtStmtsFromInst(*cit))
                            continue;
                        for (const CxtStmt& cxtStmt: getCxtStmtsFromInst(*cit))
                        {
                            CallStrCxt callSiteCxt = cxtStmt.getContext();
                            // If new context is a suffix of the call site context
                            if (isContextSuffix(newCxt, callSiteCxt))
                            {
                                CxtStmt newCts(callSiteCxt, outEdge->getDstNode());
                                markCxtStmtFlag(newCts, cts);
                            }
                        }
                    }
                }
            }
        }
    }
}

◆ hasCxtStmtsFromInst()

bool SVF::ForkJoinAnalysis::hasCxtStmtsFromInst ( const ICFGNode * inst ) const

inlineprivate

Definition at line 558 of file MHP.h.

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

◆ hasJoinInSymmetricLoop()

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

inline

Definition at line 337 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 362 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 390 of file MHP.h.

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

◆ isContextSuffix()

bool SVF::ForkJoinAnalysis::isContextSuffix	(	const CallStrCxt &	lhs,
		const CallStrCxt	call
	)

inlineprivate

If lhs is a suffix of rhs, including equal.

Definition at line 481 of file MHP.h.

    {
        return tct->isContextSuffix(lhs,call);
    }

◆ isFullJoin()

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

inline

Whether t1 fully joins t2.

Definition at line 350 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 343 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 1136 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 488 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 494 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 421 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))
        {
            instToCxtStmt[tgr.getStmt()].insert(tgr);
            pushToCTSWorkList(tgr);
        }
    }

◆ markCxtStmtFlag() [2/2]

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

inlineprivate

Initialize TDAlive and TDDead flags.

Definition at line 409 of file MHP.h.

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

◆ matchAndPopCxt()

bool SVF::ForkJoinAnalysis::matchAndPopCxt	(	CallStrCxt &	cxt,
		const CallICFGNode *	call,
		const FunObjVar *	callee
	)

inlineprivate

Match context.

Definition at line 476 of file MHP.h.

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

◆ popFromCTSWorkList()

CxtStmt SVF::ForkJoinAnalysis::popFromCTSWorkList ( )

inlineprivate

Definition at line 458 of file MHP.h.

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

◆ pushCxt()

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

inlineprivate

Context helper functions.

Push calling context

handle calling context for candidate functions only

Definition at line 468 of file MHP.h.

    {
        if(tct->isCandidateFun(call->getFun()) == false)
            return;
        tct->pushCxt(cxt,call,callee);
    }

◆ pushToCTSWorkList()

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

inlineprivate

Worklist operations.

Definition at line 454 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 1160 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 573 of file MHP.h.

◆ cxtStmtList

CxtStmtWorkList SVF::ForkJoinAnalysis::cxtStmtList

private

context-sensitive statement worklist

Definition at line 570 of file MHP.h.

◆ cxtStmtToAliveFlagMap

CxtStmtToAliveFlagMap SVF::ForkJoinAnalysis::cxtStmtToAliveFlagMap

private

flags for context-sensitive statements

Definition at line 569 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 572 of file MHP.h.

◆ directJoinMap

CxtStmtToTIDMap SVF::ForkJoinAnalysis::directJoinMap

private

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

Definition at line 571 of file MHP.h.

◆ fullJoin

ThreadPairSet SVF::ForkJoinAnalysis::fullJoin

private

t1 fully joins t2 along all program path

Definition at line 576 of file MHP.h.

◆ HBPair

ThreadPairSet SVF::ForkJoinAnalysis::HBPair

private

thread happens-before pair

Definition at line 574 of file MHP.h.

◆ HPPair

ThreadPairSet SVF::ForkJoinAnalysis::HPPair

private

threads happen-in-parallel

Definition at line 575 of file MHP.h.

◆ instToCxtStmt

InstToCxtStmt SVF::ForkJoinAnalysis::instToCxtStmt

private

Map a statement to all its context-sensitive statements.

Definition at line 578 of file MHP.h.

◆ partialJoin

ThreadPairSet SVF::ForkJoinAnalysis::partialJoin

private

t1 partially joins t2 along some program path(s)

Definition at line 577 of file MHP.h.

◆ tct

TCT* SVF::ForkJoinAnalysis::tct

private

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

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ CxtStmtSet

◆ CxtStmtToAliveFlagMap

◆ CxtStmtToLoopMap

◆ CxtStmtToTIDMap

◆ CxtStmtWorkList

◆ InstToCxtStmt

◆ InstVec

◆ LoopBBs

◆ ThreadPairSet

Member Enumeration Documentation

◆ ValDomain

Constructor & Destructor Documentation

◆ ForkJoinAnalysis()

Member Function Documentation

◆ addDirectlyJoinTID()

◆ addSymmetricLoopJoin()

◆ addToFullJoin()

◆ addToHBPair()

◆ addToHPPair()

◆ addToPartial()

◆ analyzeForkJoinPair()

◆ clearFlagMap()

◆ collectSCEVInfo()

◆ getCallee()

◆ getCxtStmtsFromInst()

◆ getDirAndIndJoinedTid()

◆ getDirectlyJoinedTid()

◆ getForkedThread()

◆ getJoinedThread()

◆ getJoinInSymmetricLoop()

◆ getJoinLoop()

◆ getMarkedFlag()

◆ getTCG()

◆ handleCall()

◆ handleFork()

◆ handleIntra()

◆ handleJoin()

◆ handleRet()

◆ hasCxtStmtsFromInst()

◆ hasJoinInSymmetricLoop()

◆ hasJoinLoop()

◆ isAliasedForkJoin()

◆ isContextSuffix()

◆ isFullJoin()

◆ isHBPair()

◆ isSameSCEV()

◆ isTDFork()

◆ isTDJoin()

◆ markCxtStmtFlag() [1/2]

◆ markCxtStmtFlag() [2/2]

◆ matchAndPopCxt()

◆ popFromCTSWorkList()

◆ pushCxt()

◆ pushToCTSWorkList()

◆ sameLoopTripCount()

Member Data Documentation

◆ cxtJoinInLoop

◆ cxtStmtList

◆ cxtStmtToAliveFlagMap

◆ dirAndIndJoinMap

◆ directJoinMap

◆ fullJoin

◆ HBPair

◆ HPPair

◆ instToCxtStmt

◆ partialJoin

◆ tct