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
typedef Set< CxtStmt >	CxtStmtSet
typedef Map< const ICFGNode *, CxtStmtSet >	InstToCxtStmt

Public Member Functions
	ForkJoinAnalysis (TCT *t)
void	collectSCEVInfo ()
	functions
template<class ICFGGraph, class CGGraph>
void	analyzeForkJoinPair (ICFGGraph icfg, CGGraph cg)
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)
const CxtStmtToLoopMap &	getSymmetricLoopJoins () const
	All SCEV-symmetric in-loop joins and their loop blocks.

Private Member Functions
template<class ICFGGraph, class CGGraph>
void	handleFork (ICFGGraph icfg, CGGraph cg, const CxtStmt &cts, NodeID rootTid)
	Handle fork.
template<class ICFGGraph, class CGGraph>
void	handleJoin (ICFGGraph icfg, CGGraph cg, const CxtStmt &cts, NodeID rootTid)
	Handle join.
template<class ICFGGraph, class CGGraph>
void	handleCall (ICFGGraph icfg, CGGraph cg, const CxtStmt &cts)
	Handle call.
template<class ICFGGraph, class CGGraph>
void	handleRet (ICFGGraph icfg, CGGraph cg, const CxtStmt &cts)
	Handle return.
template<class ICFGGraph>
void	handleIntra (ICFGGraph icfg, 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.
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
ThreadAPI::ForkJoinAliasCache	forkJoinAliasCache
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 344 of file MHP.h.

Member Typedef Documentation

CxtStmtSet

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

Definition at line 364 of file MHP.h.

CxtStmtToAliveFlagMap

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

Definition at line 358 of file MHP.h.

CxtStmtToLoopMap

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

Definition at line 361 of file MHP.h.

CxtStmtToTIDMap

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

Definition at line 359 of file MHP.h.

CxtStmtWorkList

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

Definition at line 362 of file MHP.h.

InstToCxtStmt

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

Definition at line 365 of file MHP.h.

InstVec

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

Definition at line 357 of file MHP.h.

LoopBBs

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

Definition at line 356 of file MHP.h.

ThreadPairSet

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

Definition at line 360 of file MHP.h.

Member Enumeration Documentation

ValDomain

enum SVF::ForkJoinAnalysis::ValDomain

semilattice Empty==>TDDead==>TDAlive

Enumerator
Empty
TDAlive
TDDead

Definition at line 349 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 367 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 584 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 628 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 605 of file MHP.h.

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

addToHBPair()

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

inlineprivate

Definition at line 597 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 592 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 609 of file MHP.h.

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

analyzeForkJoinPair()

template<class ICFGGraph, class CGGraph>

template void ForkJoinAnalysis::analyzeForkJoinPair< const SlicedICFGView *, const SlicedThreadCallGraphView * >	(	ICFGGraph	icfg,
		CGGraph	cg )

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 962 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())
        {
            std::vector<const ICFGNode*> successors;
            GenericGraphTraits<ICFGGraph>::getSuccNodes(
                icfg, forkInst, successors);
            for (const ICFGNode* successor : successors)
            {
                if (successor->getFun() == forkInst->getFun())
                {
                    for (const auto& forkSiteCxt : tct->getCxtOfCxtThread(ct))
                    {
                        CxtStmt newCts(forkSiteCxt.second, successor);
                        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");
                if (isTDFork(curInst))
                {
                    handleFork(icfg, cg, cts, rootTid);
                }
                else if (isTDJoin(curInst))
                {
                    handleJoin(icfg, cg, cts, rootTid);
                }
                else if (tct->isCallSite(curInst) && !tct->isExtCall(curInst))
                {
                    const CallICFGNode *callSite = SVFUtil::cast<CallICFGNode>(curInst);
                    CallGraph::FunctionSet callees;
                    GenericGraphTraits<CGGraph>::getCallees(
                        cg, callSite, callees);
                    if (!tct->isCandidateFun(callees))
                    {
                        // Do not dive into non-candidate functions
                        CxtStmt newCts(cts.getContext(), callSite->getRetICFGNode());
                        markCxtStmtFlag(newCts, cts);
                    }
                    else
                    {
                        handleCall(icfg, cg, cts);
                    }
                }
                else if (SVFUtil::dyn_cast<FunExitICFGNode>(curInst))
                {
                    handleRet(icfg, cg, cts);
                }
                else
                {
                    handleIntra(icfg, cts);
                }

                for (NodeID parentTid : tct->getParentThreads(rootTid))
                {
                    const CxtThread& parentCxtThread = tct->getTCTNode(parentTid)->getCxtThread();
                    const FunObjVar* parentRoutine = tct->getStartRoutineOfCxtThread(parentCxtThread);
                    if (curInst == GenericGraphTraits<ICFGGraph>::getFunExit(
                                icfg, parentRoutine))
                    {
                        if (getMarkedFlag(cts) != TDAlive)
                            addToFullJoin(parentTid, rootTid);
                        else
                            addToPartial(parentTid, rootTid);
                    }
                }
            }
        }
    }
}

clearFlagMap()

void SVF::ForkJoinAnalysis::clearFlagMap ( )

inlineprivate

Clear flags.

Definition at line 514 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 907 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));
    //         }
    //     }
    // }
}

getCxtStmtsFromInst()

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

inlineprivate

Get CxtStmtSet for an instruction.

Definition at line 616 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 1306 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 381 of file MHP.h.

    {
        return directJoinMap[cs];
    }

getForkedThread()

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

inlineprivate

Get forked thread.

Definition at line 569 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 574 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 389 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 416 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 466 of file MHP.h.

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

getSymmetricLoopJoins()

const CxtStmtToLoopMap & SVF::ForkJoinAnalysis::getSymmetricLoopJoins ( ) const

inline

All SCEV-symmetric in-loop joins and their loop blocks.

Definition at line 425 of file MHP.h.

    {
        return cxtJoinInLoop;
    }

getTCG()

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

inlineprivate

ThreadCallGraph.

Definition at line 579 of file MHP.h.

    {
        return tct->getThreadCallGraph();
    }

handleCall()

template<class ICFGGraph, class CGGraph>

void ForkJoinAnalysis::handleCall ( ICFGGraph icfg, CGGraph cg, const CxtStmt & cts )

private

Handle call.

Definition at line 1169 of file MHP.cpp.

{
    const ICFGNode* call = cts.getStmt();
    const CallStrCxt& curCxt = cts.getContext();
    const CallICFGNode* cbn = SVFUtil::cast<CallICFGNode>(call);
    CallGraphNode* callerNode = getTCG()->getCallGraphNode(cbn->getFun());
    std::vector<const CallGraphEdge*> outEdges;
    GenericGraphTraits<CGGraph>::getOutEdges(cg, callerNode, outEdges);
    for (const CallGraphEdge* edge : outEdges)
    {
        if (edge->getEdgeKind() != CallGraphEdge::CallRetEdge ||
                !GenericGraphTraits<CGGraph>::containsCallSite(cg, edge, cbn))
            continue;
        const FunObjVar* svfcallee = edge->getDstNode()->getFunction();
        if (isExtCall(svfcallee))
            continue;
        CallStrCxt newCxt = curCxt;
        pushCxt(newCxt, cbn, svfcallee);
        const ICFGNode* svfEntryInst =
            GenericGraphTraits<ICFGGraph>::getFunEntry(icfg, svfcallee);
        if (svfEntryInst == nullptr)
            continue;
        CxtStmt newCts(newCxt, svfEntryInst);
        markCxtStmtFlag(newCts, cts);
    }
}

handleFork()

template<class ICFGGraph, class CGGraph>

void ForkJoinAnalysis::handleFork ( ICFGGraph icfg, CGGraph cg, const CxtStmt & cts, NodeID rootTid )

private

Handle fork.

Definition at line 1054 of file MHP.cpp.

{
    const ICFGNode* call = cts.getStmt();
    const CallStrCxt& curCxt = cts.getContext();
 
    assert(isTDFork(call));
    const CallICFGNode* cbn = cast<CallICFGNode>(call);
    CallGraphNode* callerNode = getTCG()->getCallGraphNode(cbn->getFun());
    std::vector<const CallGraphEdge*> outEdges;
    GenericGraphTraits<CGGraph>::getOutEdges(cg, callerNode, outEdges);
    for (const CallGraphEdge* edge : outEdges)
    {
        if (edge->getEdgeKind() != CallGraphEdge::TDForkEdge ||
                !GenericGraphTraits<CGGraph>::containsCallSite(cg, edge, cbn))
            continue;
        const FunObjVar* callee = edge->getDstNode()->getFunction();
        CallStrCxt newCxt = curCxt;
        pushCxt(newCxt, cbn, callee);
        CxtThread ct(newCxt, call);
        if (!tct->hasTCTNode(ct))
            continue;
        if (getMarkedFlag(cts) != TDAlive)
            addToHBPair(rootTid, tct->getTCTNode(ct)->getId());
        else
            addToHPPair(rootTid, tct->getTCTNode(ct)->getId());
    }
    handleIntra(icfg, cts);
}

handleIntra()

template<class ICFGGraph>

void ForkJoinAnalysis::handleIntra ( ICFGGraph icfg, const CxtStmt & cts )

private

Handle intra.

Definition at line 1283 of file MHP.cpp.

{
    const ICFGNode* curInst = cts.getStmt();
    const CallStrCxt& curCxt = cts.getContext();
 
    std::vector<const ICFGNode*> successors;
    GenericGraphTraits<ICFGGraph>::getSuccNodes(icfg, curInst, successors);
    for (const ICFGNode* successor : successors)
    {
        if (successor->getFun() == curInst->getFun())
        {
            CxtStmt newCts(curCxt, successor);
            markCxtStmtFlag(newCts, cts);
        }
    }
}

handleJoin()

template<class ICFGGraph, class CGGraph>

void ForkJoinAnalysis::handleJoin ( ICFGGraph icfg, CGGraph cg, 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 1086 of file MHP.cpp.

{
    const ICFGNode* call = cts.getStmt();
    const CallStrCxt& curCxt = cts.getContext();
 
    assert(isTDJoin(call));
    const CallICFGNode* cbn = cast<CallICFGNode>(call);
    CallGraphNode* callerNode = getTCG()->getCallGraphNode(cbn->getFun());
    std::vector<const CallGraphEdge*> outEdges;
    GenericGraphTraits<CGGraph>::getOutEdges(cg, callerNode, outEdges);
    bool hasCallGraphEdge = false;
    for (const CallGraphEdge* edge : outEdges)
    {
        if (GenericGraphTraits<CGGraph>::containsCallSite(cg, edge, cbn))
        {
            hasCallGraphEdge = true;
            break;
        }
    }
    if (hasCallGraphEdge)
    {
        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(icfg, cts);
}

handleRet()

template<class ICFGGraph, class CGGraph>

void ForkJoinAnalysis::handleRet ( ICFGGraph icfg, CGGraph cg, const CxtStmt & cts )

private

Handle return.

Definition at line 1199 of file MHP.cpp.

{
    const ICFGNode* curInst = cts.getStmt();
    const CallStrCxt& curCxt = cts.getContext();
 
    CallGraphNode* curFunNode = getTCG()->getCallGraphNode(curInst->getFun());
    std::vector<const CallGraphEdge*> inEdges;
    GenericGraphTraits<CGGraph>::getInEdges(cg, curFunNode, inEdges);
    for (const CallGraphEdge* edge : inEdges)
    {
        if (SVFUtil::isa<ThreadForkEdge, ThreadJoinEdge>(edge))
            continue;
        std::vector<const CallICFGNode*> directCalls;
        GenericGraphTraits<CGGraph>::getDirectCalls(cg, edge, directCalls);
        for (const CallICFGNode* callSite : directCalls)
        {
            CallStrCxt newCxt = curCxt;
            if (matchAndPopCxt(newCxt, callSite,
                               curFunNode->getFunction()))
            {
                std::vector<const ICFGNode*> successors;
                GenericGraphTraits<ICFGGraph>::getSuccNodes(
                    icfg, callSite, successors);
                for (const ICFGNode* successor : successors)
                {
                    if (successor->getFun() == callSite->getFun())
                    {
                        // Iterate over callSite's call string context and use as the successor's context
                        if (!hasCxtStmtsFromInst(callSite))
                            continue;
                        for (const CxtStmt& cxtStmt:
                                getCxtStmtsFromInst(callSite))
                        {
                            CallStrCxt callSiteCxt = cxtStmt.getContext();
                            // If new context is a suffix of the call site context
                            if (isContextSuffix(newCxt, callSiteCxt))
                            {
                                CxtStmt newCts(callSiteCxt, successor);
                                markCxtStmtFlag(newCts, cts);
                            }
                        }
                    }
                }
            }
        }
        std::vector<const CallICFGNode*> indirectCalls;
        GenericGraphTraits<CGGraph>::getIndirectCalls(cg, edge, indirectCalls);
        for (const CallICFGNode* callSite : indirectCalls)
        {
            CallStrCxt newCxt = curCxt;
            if (matchAndPopCxt(newCxt, callSite,
                               curFunNode->getFunction()))
            {
                std::vector<const ICFGNode*> successors;
                GenericGraphTraits<ICFGGraph>::getSuccNodes(
                    icfg, callSite, successors);
                for (const ICFGNode* successor : successors)
                {
                    if (successor->getFun() == callSite->getFun())
                    {
                        // Iterate over callSite's call string context and use as the successor's context
                        if (!hasCxtStmtsFromInst(callSite))
                            continue;
                        for (const CxtStmt& cxtStmt:
                                getCxtStmtsFromInst(callSite))
                        {
                            CallStrCxt callSiteCxt = cxtStmt.getContext();
                            // If new context is a suffix of the call site context
                            if (isContextSuffix(newCxt, callSiteCxt))
                            {
                                CxtStmt newCts(callSiteCxt, successor);
                                markCxtStmtFlag(newCts, cts);
                            }
                        }
                    }
                }
            }
        }
    }
}

hasCxtStmtsFromInst()

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

inlineprivate

Definition at line 622 of file MHP.h.

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

hasJoinInSymmetricLoop()

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

inline

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

    {
        return tct->hasJoinLoop(inst);
    }

isAliasedForkJoin()

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

private

Whether it is a matched fork join pair.

Definition at line 1431 of file MHP.cpp.

{
    return getTCG()->getThreadAPI()->isAliasedForkJoin(tct->getPTA(),
            getForkedThread(forkSite), getJoinedThread(joinSite), forkJoinAliasCache);
}

isContextSuffix()

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

inlineprivate

If lhs is a suffix of rhs, including equal.

Definition at line 550 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 408 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 401 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 1381 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 557 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 563 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 490 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 478 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 545 of file MHP.h.

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

popFromCTSWorkList()

CxtStmt SVF::ForkJoinAnalysis::popFromCTSWorkList ( )

inlineprivate

Definition at line 527 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 537 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 523 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 1405 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 637 of file MHP.h.

cxtStmtList

CxtStmtWorkList SVF::ForkJoinAnalysis::cxtStmtList

private

context-sensitive statement worklist

Definition at line 634 of file MHP.h.

cxtStmtToAliveFlagMap

CxtStmtToAliveFlagMap SVF::ForkJoinAnalysis::cxtStmtToAliveFlagMap

private

flags for context-sensitive statements

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

directJoinMap

CxtStmtToTIDMap SVF::ForkJoinAnalysis::directJoinMap

private

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

Definition at line 635 of file MHP.h.

forkJoinAliasCache

ThreadAPI::ForkJoinAliasCache SVF::ForkJoinAnalysis::forkJoinAliasCache

private

Definition at line 462 of file MHP.h.

fullJoin

ThreadPairSet SVF::ForkJoinAnalysis::fullJoin

private

t1 fully joins t2 along all program path

Definition at line 640 of file MHP.h.

HBPair

ThreadPairSet SVF::ForkJoinAnalysis::HBPair

private

thread happens-before pair

Definition at line 638 of file MHP.h.

HPPair

ThreadPairSet SVF::ForkJoinAnalysis::HPPair

private

threads happen-in-parallel

Definition at line 639 of file MHP.h.

instToCxtStmt

InstToCxtStmt SVF::ForkJoinAnalysis::instToCxtStmt

private

Map a statement to all its context-sensitive statements.

Definition at line 642 of file MHP.h.

partialJoin

ThreadPairSet SVF::ForkJoinAnalysis::partialJoin

private

t1 partially joins t2 along some program path(s)

Definition at line 641 of file MHP.h.

tct

TCT* SVF::ForkJoinAnalysis::tct

private

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