#include <MHP.h>

Public Types
typedef Set< const FunObjVar * >	FunSet

typedef FIFOWorkList< CxtThreadStmt >	CxtThreadStmtWorkList

typedef Set< CxtThreadStmt >	CxtThreadStmtSet

typedef Map< CxtThreadStmt, NodeBS >	ThreadStmtToThreadInterleav

typedef Map< const ICFGNode *, CxtThreadStmtSet >	InstToThreadStmtSetMap

typedef SVFLoopAndDomInfo::LoopBBs	LoopBBs

typedef Set< CxtStmt >	LockSpan

typedef std::pair< const FunObjVar , const FunObjVar >	FuncPair

typedef Map< FuncPair, bool >	FuncPairToBool

Public Member Functions
	MHP (TCT *t)
	Constructor.

virtual	~MHP ()
	Destructor.

void	analyze ()
	Start analysis here.

void	analyzeInterleaving ()
	Analyze thread interleaving.

ThreadCallGraph *	getThreadCallGraph () const
	Get ThreadCallGraph.

TCT *	getTCT () const
	Get Thread Creation Tree.

bool	isConnectedfromMain (const FunObjVar *fun)
	Whether the function is connected from main function in thread call graph.

virtual bool	mayHappenInParallel (const ICFGNode i1, const ICFGNode i2)
	Interface to query whether two instructions may happen-in-parallel.

virtual bool	mayHappenInParallelCache (const ICFGNode i1, const ICFGNode i2)

virtual bool	mayHappenInParallelInst (const ICFGNode i1, const ICFGNode i2)

virtual bool	executedByTheSameThread (const ICFGNode i1, const ICFGNode i2)

const NodeBS &	getInterleavingThreads (const CxtThreadStmt &cts)
	Get interleaving thread for statement inst.

bool	hasInterleavingThreads (const CxtThreadStmt &cts) const

const CxtThreadStmtSet &	getThreadStmtSet (const ICFGNode *inst) const
	Get/has ThreadStmt.

bool	hasThreadStmtSet (const ICFGNode *inst) const

void	printInterleaving ()
	Print interleaving results.

Public Attributes
u32_t	numOfTotalQueries
	Total number of queries.

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

double	interleavingTime

double	interleavingQueriesTime

Private Member Functions
const CallGraph::FunctionSet &	getCallee (const CallICFGNode *inst, CallGraph::FunctionSet &callees)

void	updateNonCandidateFunInterleaving ()

void	handleNonCandidateFun (const CxtThreadStmt &cts)
	Handle non-candidate function.

void	handleFork (const CxtThreadStmt &cts, NodeID rootTid)
	Handle fork.

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

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

void	handleRet (const CxtThreadStmt &cts)
	Handle return.

void	handleIntra (const CxtThreadStmt &cts)
	Handle intra.

void	addInterleavingThread (const CxtThreadStmt &tgr, NodeID tid)
	Add/Remove interleaving thread for statement inst.

void	addInterleavingThread (const CxtThreadStmt &tgr, const CxtThreadStmt &src)

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

void	updateAncestorThreads (NodeID tid)
	Update Ancestor and sibling threads.

void	updateSiblingThreads (NodeID tid)

bool	isRecurFullJoin (NodeID parentTid, NodeID curTid)
	Thread curTid can be fully joined by parentTid recursively.

bool	isMustJoin (const NodeID curTid, const ICFGNode *joinsite)
	Whether a join site must join a thread t.

bool	isMultiForkedThread (NodeID curTid)
	A thread is a multiForked thread if it is in a loop or recursion.

void	pushCxt (CallStrCxt &cxt, const CallICFGNode call, const FunObjVar callee)
	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	pushToCTSWorkList (const CxtThreadStmt &cs)
	WorkList helper functions.

CxtThreadStmt	popFromCTSWorkList ()

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

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

NodeBS	getDirAndIndJoinedTid (const CallStrCxt &cxt, const ICFGNode *call)
	Return thread id(s) which are directly or indirectly joined at this join site.

bool	hasJoinInSymmetricLoop (const CallStrCxt &cxt, const ICFGNode *call) const
	Whether a context-sensitive join satisfies symmetric loop pattern.

const LoopBBs &	getJoinInSymmetricLoop (const CallStrCxt &cxt, const ICFGNode *call) const
	Whether a context-sensitive join satisfies symmetric loop pattern.

bool	isHBPair (NodeID tid1, NodeID tid2)
	Whether thread t1 happens before t2 based on ForkJoin Analysis.

Private Attributes
ThreadCallGraph *	tcg
	TCG.

TCT *	tct
	TCT.

ForkJoinAnalysis *	fja
	ForJoin Analysis.

CxtThreadStmtWorkList	cxtStmtList
	CxtThreadStmt worklist.

ThreadStmtToThreadInterleav	threadStmtToThreadInterLeav

InstToThreadStmtSetMap	instToTSMap
	Map a statement to its thread interleavings.

FuncPairToBool	nonCandidateFuncMHPRelMap

Detailed Description

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

Definition at line 45 of file MHP.h.

Member Typedef Documentation

◆ CxtThreadStmtSet

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

Definition at line 51 of file MHP.h.

◆ CxtThreadStmtWorkList

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

Definition at line 50 of file MHP.h.

◆ FuncPair

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

Definition at line 58 of file MHP.h.

◆ FuncPairToBool

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

Definition at line 59 of file MHP.h.

◆ FunSet

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

Definition at line 49 of file MHP.h.

◆ InstToThreadStmtSetMap

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

Definition at line 53 of file MHP.h.

◆ LockSpan

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

Definition at line 56 of file MHP.h.

◆ LoopBBs

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

Definition at line 54 of file MHP.h.

◆ ThreadStmtToThreadInterleav

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

Definition at line 52 of file MHP.h.

Constructor & Destructor Documentation

◆ MHP()

MHP::MHP ( TCT * t )

Constructor.

Constructor

Definition at line 44 of file MHP.cpp.

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

◆ ~MHP()

MHP::~MHP ( )

virtual

Destructor.

Destructor

Definition at line 54 of file MHP.cpp.

{
    delete fja;
}

Member Function Documentation

◆ addInterleavingThread() [1/2]

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

inlineprivate

Definition at line 163 of file MHP.h.

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

◆ addInterleavingThread() [2/2]

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

inlineprivate

Add/Remove interleaving thread for statement inst.

Definition at line 155 of file MHP.h.

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

◆ analyze()

void MHP::analyze ( )

Start analysis here.

Start analysis here

Definition at line 62 of file MHP.cpp.

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

◆ analyzeInterleaving()

void MHP::analyzeInterleaving ( )

Analyze thread interleaving.

Analyze thread interleaving

handle non-candidate function

handle candidate function

update non-candidate functions' interleaving

Definition at line 75 of file MHP.cpp.

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

◆ executedByTheSameThread()

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

virtual

Definition at line 665 of file MHP.cpp.

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

◆ getCallee()

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

inlineprivate

Definition at line 126 of file MHP.h.

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

◆ getDirAndIndJoinedTid()

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

private

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

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

Definition at line 530 of file MHP.cpp.

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

◆ getInterleavingThreads()

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

inline

Get interleaving thread for statement inst.

Definition at line 97 of file MHP.h.

    {
        return threadStmtToThreadInterLeav[cts];
    }

◆ getJoinInSymmetricLoop()

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

private

Whether a context-sensitive join satisfies symmetric loop pattern.

Definition at line 546 of file MHP.cpp.

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

◆ getTCT()

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

inline

Get Thread Creation Tree.

Definition at line 80 of file MHP.h.

    {
        return tct;
    }

◆ getThreadCallGraph()

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

inline

Get ThreadCallGraph.

Definition at line 74 of file MHP.h.

    {
        return tcg;
    }

◆ getThreadStmtSet()

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

inline

Get/has ThreadStmt.

Definition at line 109 of file MHP.h.

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

◆ handleCall()

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

private

Handle call.

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

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.

Definition at line 288 of file MHP.cpp.

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

◆ handleFork()

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

private

Handle fork.

Handle fork

Definition at line 201 of file MHP.cpp.

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

◆ handleIntra()

void MHP::handleIntra ( const CxtThreadStmt & cts )

private

Handle intra.

Handling intraprocedural statements (successive statements on the CFG )

Definition at line 403 of file MHP.cpp.

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

◆ handleJoin()

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

private

Handle join.

Handle join

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

Definition at line 231 of file MHP.cpp.

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

◆ handleNonCandidateFun()

void MHP::handleNonCandidateFun ( const CxtThreadStmt & cts )

private

Handle non-candidate function.

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

Definition at line 179 of file MHP.cpp.

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

◆ handleRet()

void MHP::handleRet ( const CxtThreadStmt & cts )

private

Handle return.

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

Definition at line 334 of file MHP.cpp.

{
    CallGraphNode* curFunNode = tcg->getCallGraphNode(cts.getStmt()->getFun());
    for (CallGraphEdge* edge : curFunNode->getInEdges())
    {
        if (SVFUtil::isa<ThreadForkEdge, ThreadJoinEdge>(edge))
            continue;
        for (CallGraphEdge::CallInstSet::const_iterator cit = (edge)->directCallsBegin(),
                ecit = (edge)->directCallsEnd();
                cit != ecit; ++cit)
        {
            CallStrCxt newCxt = cts.getContext();
            if (matchAndPopCxt(newCxt, *cit, curFunNode->getFunction()))
            {
                for(const ICFGEdge* outEdge : cts.getStmt()->getOutEdges())
                {
                    if(outEdge->getDstNode()->getFun() == (*cit)->getFun())
                    {
                        // Iterate over callSite's call string context and use as the successor's context
                        if (!hasThreadStmtSet(*cit))
                            continue;
                        for (const CxtThreadStmt& cxtThreadStmt: getThreadStmtSet(*cit))
                        {
                            CallStrCxt callSiteCxt = cxtThreadStmt.getContext();
                            // If new context is a suffix of the call site context
                            if (isContextSuffix(newCxt, callSiteCxt))
                            {
                                CxtThreadStmt newCts(cts.getTid(), callSiteCxt, outEdge->getDstNode());
                                addInterleavingThread(newCts, cts);
                            }
                        }
                    }
                }
            }
        }
        for (CallGraphEdge::CallInstSet::const_iterator cit = (edge)->indirectCallsBegin(),
                ecit = (edge)->indirectCallsEnd();
                cit != ecit; ++cit)
        {
            CallStrCxt newCxt = cts.getContext();
            if (matchAndPopCxt(newCxt, *cit, curFunNode->getFunction()))
            {
                for(const ICFGEdge* outEdge : cts.getStmt()->getOutEdges())
                {
                    if(outEdge->getDstNode()->getFun() == (*cit)->getFun())
                    {
                        // Iterate over callSite's call string context and use as the successor's context
                        if (!hasThreadStmtSet(*cit))
                            continue;
                        for (const CxtThreadStmt& cxtThreadStmt: getThreadStmtSet(*cit))
                        {
                            CallStrCxt callSiteCxt = cxtThreadStmt.getContext();
                            // If new context is a suffix of the call site context
                            if (isContextSuffix(newCxt, callSiteCxt))
                            {
                                CxtThreadStmt newCts(cts.getTid(), callSiteCxt, outEdge->getDstNode());
                                addInterleavingThread(newCts, cts);
                            }
                        }
                    }
                }
            }
        }
    }
}

◆ hasInterleavingThreads()

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

inline

Definition at line 101 of file MHP.h.

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

◆ hasJoinInSymmetricLoop()

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

private

Whether a context-sensitive join satisfies symmetric loop pattern.

Whether a context-sensitive join satisfies symmetric loop pattern

Definition at line 539 of file MHP.cpp.

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

◆ hasThreadStmtSet()

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

inline

Definition at line 115 of file MHP.h.

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

◆ isConnectedfromMain()

bool MHP::isConnectedfromMain ( const FunObjVar * fun )

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

Definition at line 560 of file MHP.cpp.

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

◆ isContextSuffix()

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

inlineprivate

If lhs is a suffix of rhs, including equal.

Definition at line 221 of file MHP.h.

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

◆ isHBPair()

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

private

Whether thread t1 happens before t2 based on ForkJoin Analysis.

Whether two thread t1 happens-fore t2

Definition at line 555 of file MHP.cpp.

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

◆ isMultiForkedThread()

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

inlineprivate

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

Definition at line 200 of file MHP.h.

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

◆ isMustJoin()

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

private

Whether a join site must join a thread t.

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

Definition at line 520 of file MHP.cpp.

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

◆ isRecurFullJoin()

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

private

Thread curTid can be fully joined by parentTid recursively.

Whether curTid can be fully joined by parentTid recursively

Definition at line 485 of file MHP.cpp.

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

◆ isTDFork()

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

inlineprivate

Whether it is a fork site.

Definition at line 240 of file MHP.h.

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

◆ isTDJoin()

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

inlineprivate

Whether it is a join site.

Definition at line 246 of file MHP.h.

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

◆ matchAndPopCxt()

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

inlineprivate

Match context.

Definition at line 216 of file MHP.h.

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

◆ mayHappenInParallel()

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

virtual

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

Definition at line 653 of file MHP.cpp.

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

◆ mayHappenInParallelCache()

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

virtual

Definition at line 631 of file MHP.cpp.

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

◆ mayHappenInParallelInst()

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

virtual

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

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

Definition at line 595 of file MHP.cpp.

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

◆ popFromCTSWorkList()

CxtThreadStmt SVF::MHP::popFromCTSWorkList ( )

inlineprivate

Definition at line 233 of file MHP.h.

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

◆ printInterleaving()

void MHP::printInterleaving ( )

Print interleaving results.

Print interleaving results

Definition at line 686 of file MHP.cpp.

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

◆ pushCxt()

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

inlineprivate

Context helper functions.

Push calling context

handle calling context for candidate functions only

Definition at line 208 of file MHP.h.

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

◆ pushToCTSWorkList()

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

inlineprivate

WorkList helper functions.

Definition at line 229 of file MHP.h.

    {
        return cxtStmtList.push(cs);
    }

◆ rmInterleavingThread()

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

inlineprivate

Definition at line 172 of file MHP.h.

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

◆ updateAncestorThreads()

void MHP::updateAncestorThreads ( NodeID curTid )

private

Update Ancestor and sibling threads.

Update interleavings of ancestor threads according to TCT

Definition at line 418 of file MHP.cpp.

{
    NodeBS ancestorAndSelfTids = tct->getAncestorThreads(curTid);
    DBOUT(DMTA, outs() << "##Ancestor thread of " << curTid << " is : ");
    DBOUT(DMTA, dumpSet(tds));
    DBOUT(DMTA, outs() << "\n");
    ancestorAndSelfTids.set(curTid);
 
    for (const unsigned tid : ancestorAndSelfTids)
    {
        const CxtThread& ct = tct->getTCTNode(tid)->getCxtThread();
        if (const ICFGNode* forkInst = ct.getThread())
        {
            for(const ICFGEdge* outEdge : forkInst->getOutEdges())
            {
                // Ensure dst node is in the same function as forkInst
                if(outEdge->getDstNode()->getFun() == forkInst->getFun())
                {
                    for (const auto& forkSiteCxt : tct->getCxtOfCxtThread(ct))
                    {
                        CxtThreadStmt cts(forkSiteCxt.first, forkSiteCxt.second, outEdge->getDstNode());
                        addInterleavingThread(cts, curTid);
                    }
                }
            }
        }
    }
}

◆ updateNonCandidateFunInterleaving()

void MHP::updateNonCandidateFunInterleaving ( )

private

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

Update non-candidate functions' interleaving

Definition at line 141 of file MHP.cpp.

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

◆ updateSiblingThreads()

void MHP::updateSiblingThreads ( NodeID curTid )

private

Update interleavings of sibling threads according to TCT

Exclude sibling thread that never happen in parallel based on ForkJoinAnalysis

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

Definition at line 457 of file MHP.cpp.

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

Member Data Documentation

◆ cxtStmtList

CxtThreadStmtWorkList SVF::MHP::cxtStmtList

private

CxtThreadStmt worklist.

Definition at line 267 of file MHP.h.

◆ fja

ForkJoinAnalysis* SVF::MHP::fja

private

ForJoin Analysis.

Definition at line 266 of file MHP.h.

◆ instToTSMap

InstToThreadStmtSetMap SVF::MHP::instToTSMap

private

Map a statement to its thread interleavings.

Map an instruction to its ThreadStmtSet

Definition at line 269 of file MHP.h.

◆ interleavingQueriesTime

double SVF::MHP::interleavingQueriesTime

Definition at line 277 of file MHP.h.

◆ interleavingTime

double SVF::MHP::interleavingTime

Definition at line 276 of file MHP.h.

◆ nonCandidateFuncMHPRelMap

FuncPairToBool SVF::MHP::nonCandidateFuncMHPRelMap

private

Definition at line 270 of file MHP.h.

◆ numOfMHPQueries

u32_t SVF::MHP::numOfMHPQueries

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

Definition at line 275 of file MHP.h.

◆ numOfTotalQueries

u32_t SVF::MHP::numOfTotalQueries

Total number of queries.

Definition at line 274 of file MHP.h.

◆ tcg

ThreadCallGraph* SVF::MHP::tcg

private

TCG.

Definition at line 264 of file MHP.h.

◆ tct

TCT* SVF::MHP::tct

private

TCT.

Definition at line 265 of file MHP.h.

◆ threadStmtToThreadInterLeav

ThreadStmtToThreadInterleav SVF::MHP::threadStmtToThreadInterLeav

private

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

Public Attributes

Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ CxtThreadStmtSet

◆ CxtThreadStmtWorkList

◆ FuncPair

◆ FuncPairToBool

◆ FunSet

◆ InstToThreadStmtSetMap

◆ LockSpan

◆ LoopBBs

◆ ThreadStmtToThreadInterleav

Constructor & Destructor Documentation

◆ MHP()

◆ ~MHP()

Member Function Documentation

◆ addInterleavingThread() [1/2]

◆ addInterleavingThread() [2/2]

◆ analyze()

◆ analyzeInterleaving()

◆ executedByTheSameThread()

◆ getCallee()

◆ getDirAndIndJoinedTid()

◆ getInterleavingThreads()

◆ getJoinInSymmetricLoop()

◆ getTCT()

◆ getThreadCallGraph()

◆ getThreadStmtSet()

◆ handleCall()

◆ handleFork()

◆ handleIntra()

◆ handleJoin()

◆ handleNonCandidateFun()

◆ handleRet()

◆ hasInterleavingThreads()

◆ hasJoinInSymmetricLoop()

◆ hasThreadStmtSet()

◆ isConnectedfromMain()

◆ isContextSuffix()

◆ isHBPair()

◆ isMultiForkedThread()

◆ isMustJoin()

◆ isRecurFullJoin()

◆ isTDFork()

◆ isTDJoin()

◆ matchAndPopCxt()

◆ mayHappenInParallel()

◆ mayHappenInParallelCache()

◆ mayHappenInParallelInst()

◆ popFromCTSWorkList()

◆ printInterleaving()

◆ pushCxt()

◆ pushToCTSWorkList()

◆ rmInterleavingThread()

◆ updateAncestorThreads()

◆ updateNonCandidateFunInterleaving()

◆ updateSiblingThreads()

Member Data Documentation

◆ cxtStmtList

◆ fja

◆ instToTSMap

◆ interleavingQueriesTime

◆ interleavingTime

◆ nonCandidateFuncMHPRelMap

◆ numOfMHPQueries

◆ numOfTotalQueries

◆ tcg

◆ tct

◆ threadStmtToThreadInterLeav