SVF::MHP Class Reference

#include <MHP.h>

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

Public Member Functions
	MHP (TCT *t)
	Constructor.
virtual	~MHP ()
	Destructor.
template<class ICFGGraph , class CGGraph >
void	analyze (ICFGGraph icfg, CGGraph cg)
template<class ICFGGraph , class CGGraph >
void	analyzeInterleaving (ICFGGraph icfg, CGGraph cg)
	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

Protected Types
typedef Map< const SVFBasicBlock *, std::vector< CxtStmt > >	BBToSymJoinsMap
typedef Map< CxtStmt, Set< const SVFBasicBlock * > >	SymJoinToLoopMap

Protected Member Functions
const CallGraph::FunctionSet &	getCallee (const CallICFGNode *inst, CallGraph::FunctionSet &callees)
template<class ICFGGraph , class CGGraph >
void	updateNonCandidateFunInterleaving (ICFGGraph icfg, CGGraph cg)
template<class ICFGGraph , class CGGraph >
void	handleNonCandidateFun (ICFGGraph icfg, CGGraph cg, const CxtThreadStmt &cts)
	Handle non-candidate function.
template<class ICFGGraph , class CGGraph >
void	handleFork (ICFGGraph icfg, CGGraph cg, const CxtThreadStmt &cts, NodeID rootTid)
	Handle fork.
template<class ICFGGraph , class CGGraph >
void	handleJoin (ICFGGraph icfg, CGGraph cg, const CxtThreadStmt &cts, NodeID rootTid)
	Handle join.
template<class ICFGGraph , class CGGraph >
void	handleCall (ICFGGraph icfg, CGGraph cg, const CxtThreadStmt &cts, NodeID rootTid)
	Handle call.
template<class ICFGGraph , class CGGraph >
void	handleRet (ICFGGraph icfg, CGGraph cg, const CxtThreadStmt &cts)
	Handle return.
template<class ICFGGraph , class CGGraph >
void	handleIntra (ICFGGraph icfg, CGGraph cg, const CxtThreadStmt &cts)
	Handle intra.
void	buildSymJoinKillTables ()
NodeBS	edgeFlow (const CxtThreadStmt &cts, const ICFGNode *dst)
void	addInterleavingThread (const CxtThreadStmt &tgr, NodeID tid)
	Add/Remove interleaving thread for statement inst.
void	addInterleavingThread (const CxtThreadStmt &tgr, const CxtThreadStmt &src)
void	addInterleavingBits (const CxtThreadStmt &tgr, const NodeBS &bits)
void	rmInterleavingThread (const CxtThreadStmt &tgr, const NodeBS &tids, const ICFGNode *joinsite)
template<class ICFGGraph , class CGGraph >
void	updateAncestorThreads (ICFGGraph icfg, CGGraph cg, NodeID tid)
	Update Ancestor and sibling threads.
template<class ICFGGraph , class CGGraph >
void	updateSiblingThreads (ICFGGraph icfg, CGGraph cg, 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.

Protected Attributes
ThreadCallGraph *	tcg
	TCG.
TCT *	tct
	TCT.
ForkJoinAnalysis *	fja
	ForJoin Analysis.
CxtThreadStmtWorkList	cxtStmtList
	CxtThreadStmt worklist.
ThreadStmtToThreadInterleav	threadStmtToThreadInterLeav
BBToSymJoinsMap	bbToSymJoins
	Map a statement to its thread interleavings.
SymJoinToLoopMap	symJoinLoop
	symmetric in-loop join -> its loop's blocks
InstToThreadStmtSetMap	instToTSMap
	Map an instruction to its ThreadStmtSet.
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 56 of file MHP.h.

Member Typedef Documentation

BBToSymJoinsMap

typedef Map<const SVFBasicBlock*, std::vector<CxtStmt> > SVF::MHP::BBToSymJoinsMap

protected

Symmetric-join loop-exit kills, applied to EDGE flows (node states stay pure unions, so paths bypassing the join keep their interleavings).

Definition at line 171 of file MHP.h.

CxtThreadStmtSet

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

Definition at line 62 of file MHP.h.

CxtThreadStmtWorkList

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

Definition at line 61 of file MHP.h.

FuncPair

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

Definition at line 69 of file MHP.h.

FuncPairToBool

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

Definition at line 70 of file MHP.h.

FunSet

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

Definition at line 60 of file MHP.h.

InstToThreadStmtSetMap

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

Definition at line 64 of file MHP.h.

LockSpan

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

Definition at line 67 of file MHP.h.

LoopBBs

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

Definition at line 65 of file MHP.h.

SymJoinToLoopMap

typedef Map<CxtStmt, Set<const SVFBasicBlock*> > SVF::MHP::SymJoinToLoopMap

protected

Definition at line 172 of file MHP.h.

ThreadStmtToThreadInterleav

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

Definition at line 63 of file MHP.h.

Constructor & Destructor Documentation

MHP()

MHP::MHP

(

TCT *

t

)

Constructor.

Constructor

Definition at line 54 of file MHP.cpp.

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

~MHP()

MHP::~MHP ( )

virtual

Destructor.

Destructor

Definition at line 110 of file MHP.cpp.

{
    delete fja;
}

Member Function Documentation

addInterleavingBits()

void SVF::MHP::addInterleavingBits ( const CxtThreadStmt &  tgr, const NodeBS &  bits  )

inlineprotected

Definition at line 196 of file MHP.h.

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

addInterleavingThread() [1/2]

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

inlineprotected

Definition at line 187 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  )

inlineprotected

Add/Remove interleaving thread for statement inst.

Definition at line 179 of file MHP.h.

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

analyze()

template<class ICFGGraph , class CGGraph >

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

Start analysis here. One implementation for the whole program and a slice: the compute is templated on the two graphs it traverses – the ICFG (ICFG* whole / const SlicedICFGView* sliced) and the CallGraph (CallGraph* whole / const SlicedThreadCallGraphView* sliced) – and calls their GenericGraphTraits specialisations directly (no wrapper layer).

Start analysis here

Definition at line 120 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(icfg, cg);
    DOTIMESTAT(double interleavingEnd = PTAStat::getClk(true));
    DOTIMESTAT(interleavingTime += (interleavingEnd - interleavingStart) / TIMEINTERVAL);
}

analyzeInterleaving()

template<class ICFGGraph , class CGGraph >

void MHP::analyzeInterleaving	(	ICFGGraph	icfg,
		CGGraph	cg
	)

Analyze thread interleaving.

Analyze thread interleaving

handle non-candidate function

handle candidate function

update non-candidate functions' interleaving

Definition at line 134 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 = GenericGraphTraits<ICFGGraph>::getFunEntry(icfg, routine);
        CxtThreadStmt rootcts(rootTid, ct.getContext(), svfInst);
 
        addInterleavingThread(rootcts, rootTid);
        updateAncestorThreads(icfg, cg, rootTid);
        updateSiblingThreads(icfg, cg, 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(icfg, cg, cts);
            }
            else
            {
                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))
                {
                    handleCall(icfg, cg, cts, rootTid);
                }
                else if (SVFUtil::dyn_cast<FunExitICFGNode>(curInst))
                {
                    handleRet(icfg, cg, cts);
                }
                else
                {
                    handleIntra(icfg, cg, cts);
                }
            }
        }
    }
 
    updateNonCandidateFunInterleaving(icfg, cg);
 
    if (Options::PrintInterLev())
        printInterleaving();
}

buildSymJoinKillTables()

void MHP::buildSymJoinKillTables ( )

protected

Index the SCEV-symmetric in-loop joins by their loop blocks.

Definition at line 65 of file MHP.cpp.

{
    for (const auto& joinAndLoop : fja->getSymmetricLoopJoins())
    {
        Set<const SVFBasicBlock*>& loopBlocks = symJoinLoop[joinAndLoop.first];
        for (const SVFBasicBlock* bb : joinAndLoop.second)
        {
            loopBlocks.insert(bb);
            bbToSymJoins[bb].push_back(joinAndLoop.first);
        }
    }
}

edgeFlow()

NodeBS MHP::edgeFlow ( const CxtThreadStmt &  cts, const ICFGNode *  dst  )

protected

Flow along edge cts.stmt -> dst: an edge leaving a symmetric join loop drops the joined tids (edge kill; the destination's state is never subtracted from).

Definition at line 82 of file MHP.cpp.

{
    NodeBS flow = getInterleavingThreads(cts);
    const SVFBasicBlock* srcBB = cts.getStmt()->getBB();
    const SVFBasicBlock* dstBB = dst->getBB();
    if (srcBB == nullptr || dstBB == nullptr || srcBB == dstBB)
        return flow;
    BBToSymJoinsMap::const_iterator it = bbToSymJoins.find(srcBB);
    if (it == bbToSymJoins.end())
        return flow;
    for (const CxtStmt& join : it->second)
    {
        if (join.getContext() != cts.getContext())
            continue;
        const Set<const SVFBasicBlock*>& loopBlocks = symJoinLoop[join];
        if (loopBlocks.find(dstBB) != loopBlocks.end())
            continue;                                  // edge stays inside the loop
        if (!isMustJoin(cts.getTid(), join.getStmt()))
            continue;
        flow.intersectWithComplement(
            getDirAndIndJoinedTid(join.getContext(), join.getStmt()));
    }
    return flow;
}

executedByTheSameThread()

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

virtual

Definition at line 775 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  )

inlineprotected

Definition at line 141 of file MHP.h.

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

getDirAndIndJoinedTid()

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

protected

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 640 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 112 of file MHP.h.

    {
        return threadStmtToThreadInterLeav[cts];
    }

getJoinInSymmetricLoop()

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

protected

Whether a context-sensitive join satisfies symmetric loop pattern.

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

    {
        return tct;
    }

getThreadCallGraph()

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

inline

Get ThreadCallGraph.

Definition at line 89 of file MHP.h.

    {
        return tcg;
    }

getThreadStmtSet()

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

inline

Get/has ThreadStmt.

Definition at line 124 of file MHP.h.

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

handleCall()

template<class ICFGGraph , class CGGraph >

void MHP::handleCall ( ICFGGraph  icfg, CGGraph  cg, const CxtThreadStmt &  cts, NodeID  rootTid  )

protected

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 358 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 = GenericGraphTraits<ICFGGraph>::getFunEntry(icfg, svfcallee);
            CxtThreadStmt newCts(cts.getTid(), newCxt, svfEntryInst);
            addInterleavingThread(newCts, cts);
 
            // Return-flow rendezvous: if the callee's exit already has state
            // under newCxt, forward it now (handleRet cannot see late callsites).
            if (tct->isCandidateFun(svfcallee) && svfcallee->hasBasicBlock())
            {
                const ICFGNode* exitInst = svfcallee->getExitBB()->back();
                CxtThreadStmt exitCts(cts.getTid(), newCxt, exitInst);
                if (threadStmtToThreadInterLeav.find(exitCts) != threadStmtToThreadInterLeav.end())
                {
                    CxtThreadStmt retCts(cts.getTid(), curCxt, cbn->getRetICFGNode());
                    addInterleavingThread(retCts, exitCts);
                }
            }
        }
    }
 
    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()

template<class ICFGGraph , class CGGraph >

void MHP::handleFork ( ICFGGraph  icfg, CGGraph  cg, const CxtThreadStmt &  cts, NodeID  rootTid  )

protected

Handle fork.

Handle fork

Definition at line 263 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 = GenericGraphTraits<ICFGGraph>::getFunEntry(icfg, svfroutine);
            CxtThread ct(newCxt, call);
            CxtThreadStmt newcts(tct->getTCTNode(ct)->getId(), ct.getContext(), stmt);
            addInterleavingThread(newcts, cts);
        }
    }
    handleIntra(icfg, cg, cts);
}

handleIntra()

template<class ICFGGraph , class CGGraph >

void MHP::handleIntra ( ICFGGraph  icfg, CGGraph  cg, const CxtThreadStmt &  cts  )

protected

Handle intra.

Handling intraprocedural statements (successive statements on the CFG )

Definition at line 496 of file MHP.cpp.

{
    const SVFBasicBlock* srcBB = cts.getStmt()->getBB();
    const bool mayExitSymJoinLoop =
        srcBB != nullptr && bbToSymJoins.find(srcBB) != bbToSymJoins.end();
 
    std::vector<const ICFGNode*> succ;
    GenericGraphTraits<ICFGGraph>::getSuccNodes(icfg, cts.getStmt(), succ);
    for (const ICFGNode* dst : succ)
    {
        if(dst->getFun() == cts.getStmt()->getFun())
        {
            CxtThreadStmt newCts(cts.getTid(), cts.getContext(), dst);
            if (mayExitSymJoinLoop)
                addInterleavingBits(newCts, edgeFlow(cts, dst));
            else
                addInterleavingThread(newCts, cts);
        }
    }
}

handleJoin()

template<class ICFGGraph , class CGGraph >

void MHP::handleJoin ( ICFGGraph  icfg, CGGraph  cg, const CxtThreadStmt &  cts, NodeID  rootTid  )

protected

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 294 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))
        {
            // Seed the loop exits with the flow along the exiting edge (see
            // edgeFlow): the kill applies to the flow, not the exit's state.
            NodeBS flow = getInterleavingThreads(cts);
            if (hasJoinInSymmetricLoop(curCxt, call) && isMustJoin(cts.getTid(), call))
                flow.intersectWithComplement(joinedTids);
 
            std::vector<const SVFBasicBlock*> exitbbs;
            call->getFun()->getExitBlocksOfLoop(call->getBB(), exitbbs);
            while (!exitbbs.empty())
            {
                const SVFBasicBlock* eb = exitbbs.back();
                exitbbs.pop_back();
                // Seed the post-join interleaving at the loop-exit entry. The slicer
                // retains these entries as anchors, so the seed always lands on a kept
                // node (no runtime projection needed).
                CxtThreadStmt newCts(cts.getTid(), curCxt, eb->front());
                addInterleavingBits(newCts, flow);
            }
        }
        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();
                // Seed at the loop-exit entry (a retained anchor; see above).
                CxtThreadStmt newCts(cts.getTid(), cts.getContext(), eb->front());
                addInterleavingThread(newCts, cts);
            }
        }
    }
    handleIntra(icfg, cg, cts);
}

handleNonCandidateFun()

template<class ICFGGraph , class CGGraph >

void MHP::handleNonCandidateFun ( ICFGGraph  icfg, CGGraph  cg, const CxtThreadStmt &  cts  )

protected

Handle non-candidate function.

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

Definition at line 240 of file MHP.cpp.

{
    const ICFGNode* curInst = cts.getStmt();
    const FunObjVar* curfun = curInst->getFun();
    assert((curInst == GenericGraphTraits<ICFGGraph>::getFunEntry(icfg, curfun)) && "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 = GenericGraphTraits<ICFGGraph>::getFunEntry(icfg, callee);
            CxtThreadStmt newCts(cts.getTid(), curCxt, calleeInst);
            addInterleavingThread(newCts, cts);
        }
    }
}

handleRet()

template<class ICFGGraph , class CGGraph >

void MHP::handleRet ( ICFGGraph  icfg, CGGraph  cg, const CxtThreadStmt &  cts  )

protected

Handle return.

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

Definition at line 418 of file MHP.cpp.

{
    CallGraphNode* curFunNode = tcg->getCallGraphNode(cts.getStmt()->getFun());
    std::vector<const CallGraphEdge*> inEdges;
    GenericGraphTraits<CGGraph>::getInEdges(cg, curFunNode, inEdges);
    for (const CallGraphEdge* edgeConst : inEdges)
    {
        if (SVFUtil::isa<ThreadForkEdge, ThreadJoinEdge>(edgeConst))
            continue;
        // Need non-const for directCallsBegin/End
        CallGraphEdge* edge = const_cast<CallGraphEdge*>(edgeConst);
        for (CallGraphEdge::CallInstSet::const_iterator cit = (edge)->directCallsBegin(),
                ecit = (edge)->directCallsEnd();
                cit != ecit; ++cit)
        {
            CallStrCxt newCxt = cts.getContext();
            if (matchAndPopCxt(newCxt, *cit, curFunNode->getFunction()))
            {
                std::vector<const ICFGNode*> succ;
                GenericGraphTraits<ICFGGraph>::getSuccNodes(icfg, cts.getStmt(), succ);
                for (const ICFGNode* dst : succ)
                {
                    if(dst->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, dst);
                                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()))
            {
                std::vector<const ICFGNode*> succ;
                GenericGraphTraits<ICFGGraph>::getSuccNodes(icfg, cts.getStmt(), succ);
                for (const ICFGNode* dst : succ)
                {
                    if(dst->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, dst);
                                addInterleavingThread(newCts, cts);
                            }
                        }
                    }
                }
            }
        }
    }
}

hasInterleavingThreads()

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

inline

Definition at line 116 of file MHP.h.

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

hasJoinInSymmetricLoop()

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

protected

Whether a context-sensitive join satisfies symmetric loop pattern.

Whether a context-sensitive join satisfies symmetric loop pattern

Definition at line 649 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 130 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 670 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 (SVFUtil::isProgEntryFunction(node->getFunction()))
            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  )

inlineprotected

If lhs is a suffix of rhs, including equal.

Definition at line 254 of file MHP.h.

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

isHBPair()

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

protected

Whether thread t1 happens before t2 based on ForkJoin Analysis.

Whether two thread t1 happens-fore t2

Definition at line 665 of file MHP.cpp.

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

isMultiForkedThread()

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

inlineprotected

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

Definition at line 233 of file MHP.h.

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

isMustJoin()

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

protected

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 630 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  )

protected

Thread curTid can be fully joined by parentTid recursively.

Whether curTid can be fully joined by parentTid recursively

Definition at line 595 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 )

inlineprotected

Whether it is a fork site.

Definition at line 273 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 )

inlineprotected

Whether it is a join site.

Definition at line 279 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  )

inlineprotected

Match context.

Definition at line 249 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 763 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 741 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 705 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 ( )

inlineprotected

Definition at line 266 of file MHP.h.

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

printInterleaving()

void MHP::printInterleaving

(

)

Print interleaving results.

Print interleaving results

Definition at line 796 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  )

inlineprotected

Context helper functions.

Push calling context

handle calling context for candidate functions only

Definition at line 241 of file MHP.h.

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

pushToCTSWorkList()

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

inlineprotected

WorkList helper functions.

Definition at line 262 of file MHP.h.

    {
        return cxtStmtList.push(cs);
    }

rmInterleavingThread()

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

inlineprotected

Definition at line 205 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()

template<class ICFGGraph , class CGGraph >

void MHP::updateAncestorThreads ( ICFGGraph  icfg, CGGraph  cg, NodeID  curTid  )

protected

Update Ancestor and sibling threads.

Update interleavings of ancestor threads according to TCT

Definition at line 521 of file MHP.cpp.

{
    NodeBS ancestorAndSelfTids = tct->getAncestorThreads(curTid);
    DBOUT(DMTA, outs() << "##Ancestor thread of " << curTid << " is : ");
    DBOUT(DMTA, dumpSet(ancestorAndSelfTids));
    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())
        {
            // Mark the fork site's successors under the graph, so a sliced run
            // marks kept successors (a marker on a removed node would strand).
            std::vector<const ICFGNode*> succ;
            GenericGraphTraits<ICFGGraph>::getSuccNodes(icfg, forkInst, succ);
            for(const ICFGNode* dst : succ)
            {
                // Ensure dst node is in the same function as forkInst
                if(dst->getFun() == forkInst->getFun())
                {
                    for (const auto& forkSiteCxt : tct->getCxtOfCxtThread(ct))
                    {
                        CxtThreadStmt cts(forkSiteCxt.first, forkSiteCxt.second, dst);
                        addInterleavingThread(cts, curTid);
                    }
                }
            }
        }
    }
}

updateNonCandidateFunInterleaving()

template<class ICFGGraph , class CGGraph >

void MHP::updateNonCandidateFunInterleaving ( ICFGGraph  icfg, CGGraph  cg  )

protected

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

Update non-candidate functions' interleaving

Definition at line 202 of file MHP.cpp.

{
    // Copy each non-candidate function entry's interleaving to the function's
    // other nodes under the graph. Runs after the worklist has drained, so
    // addInterleavingThread's push is inert.
    for (const auto& item : *GenericGraphTraits<CGGraph>::getCallGraph(cg))
    {
        const FunObjVar* fun = item.second->getFunction();
        if (tct->isCandidateFun(fun) || isExtCall(fun))
            continue;
 
        const ICFGNode* entryNode = GenericGraphTraits<ICFGGraph>::getFunEntry(icfg, fun);
        if (!hasThreadStmtSet(entryNode))
            continue;
 
        const CxtThreadStmtSet& tsSet = getThreadStmtSet(entryNode);
 
        std::vector<const ICFGNode*> funICFGNodes;
        GenericGraphTraits<ICFGGraph>::getFunICFGNodes(icfg, fun, funICFGNodes);
 
        for (const CxtThreadStmt& cts : tsSet)
        {
            const CallStrCxt& curCxt = cts.getContext();
            for (const ICFGNode* curNode : funICFGNodes)
            {
                if (curNode == entryNode)
                    continue;
                CxtThreadStmt newCts(cts.getTid(), curCxt, curNode);
                addInterleavingThread(newCts, cts);
            }
        }
    }
}

updateSiblingThreads()

template<class ICFGGraph , class CGGraph >

void MHP::updateSiblingThreads ( ICFGGraph  icfg, CGGraph  cg, NodeID  curTid  )

protected

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 565 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);
            // The entry node under the graph: the same node the sibling thread's
            // own propagation starts from (see analyzeInterleaving's root cts).
            const ICFGNode* stmt = GenericGraphTraits<ICFGGraph>::getFunEntry(icfg, routine);
            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

bbToSymJoins

BBToSymJoinsMap SVF::MHP::bbToSymJoins

protected

Map a statement to its thread interleavings.

loop block -> symmetric in-loop joins of that loop

Definition at line 302 of file MHP.h.

cxtStmtList

CxtThreadStmtWorkList SVF::MHP::cxtStmtList

protected

CxtThreadStmt worklist.

Definition at line 300 of file MHP.h.

fja

ForkJoinAnalysis* SVF::MHP::fja

protected

ForJoin Analysis.

Definition at line 299 of file MHP.h.

instToTSMap

InstToThreadStmtSetMap SVF::MHP::instToTSMap

protected

Map an instruction to its ThreadStmtSet.

Definition at line 304 of file MHP.h.

interleavingQueriesTime

double SVF::MHP::interleavingQueriesTime

Definition at line 311 of file MHP.h.

interleavingTime

double SVF::MHP::interleavingTime

Definition at line 310 of file MHP.h.

nonCandidateFuncMHPRelMap

FuncPairToBool SVF::MHP::nonCandidateFuncMHPRelMap

protected

Definition at line 305 of file MHP.h.

numOfMHPQueries

u32_t SVF::MHP::numOfMHPQueries

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

Definition at line 309 of file MHP.h.

numOfTotalQueries

u32_t SVF::MHP::numOfTotalQueries

Total number of queries.

Definition at line 308 of file MHP.h.

symJoinLoop

SymJoinToLoopMap SVF::MHP::symJoinLoop

protected

symmetric in-loop join -> its loop's blocks

Definition at line 303 of file MHP.h.

tcg

ThreadCallGraph* SVF::MHP::tcg

protected

TCG.

Definition at line 297 of file MHP.h.

tct

TCT* SVF::MHP::tct

protected

TCT.

Definition at line 298 of file MHP.h.

threadStmtToThreadInterLeav

ThreadStmtToThreadInterleav SVF::MHP::threadStmtToThreadInterLeav

protected

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