SVF::MHP Class Reference

#include <MHP.h>

Classes
struct	NodeThreadSummary

Public Types
enum class	StateRepresentation { MaterializedContexts , QuerySummaries }
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 Map< const ICFGNode *, NodeThreadSummary >	InstToThreadSummaryMap
typedef SVFLoopAndDomInfo::LoopBBs	LoopBBs
typedef Set< CxtStmt >	LockSpan
typedef std::pair< const FunObjVar *, const FunObjVar * >	FuncPair
typedef Map< FuncPair, bool >	FuncPairToBool

Public Member Functions
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 NodeThreadSummary *	getThreadSummary (const ICFGNode *inst) const
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.

Static Public Member Functions
template<class ICFGGraph, class CGGraph>
static std::unique_ptr< MHP >	create (TCT *t, ICFGGraph icfg, CGGraph cg, StateRepresentation representation=StateRepresentation::MaterializedContexts)
	Construct MHP and initialize its graph-dependent ForkJoinAnalysis.

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
	MHP (TCT *t, StateRepresentation representation=StateRepresentation::MaterializedContexts)
template<class ICFGGraph, class CGGraph>
void	updateNonCandidateFunInterleaving (ICFGGraph icfg, CGGraph cg)
template<class ICFGGraph, class CGGraph>
void	buildQuerySummaries (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.
InstToThreadSummaryMap	instToThreadSummary
	Exact per-node/per-tid query compression.
Map< const ICFGNode *, const ICFGNode * >	querySummaryOwner
	Non-candidate node -> entry summary.
StateRepresentation	stateRepresentation
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 51 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 195 of file MHP.h.

CxtThreadStmtSet

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

Definition at line 57 of file MHP.h.

CxtThreadStmtWorkList

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

Definition at line 56 of file MHP.h.

FuncPair

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

Definition at line 75 of file MHP.h.

FuncPairToBool

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

Definition at line 76 of file MHP.h.

FunSet

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

Definition at line 55 of file MHP.h.

InstToThreadStmtSetMap

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

Definition at line 59 of file MHP.h.

InstToThreadSummaryMap

typedef Map<const ICFGNode*, NodeThreadSummary> SVF::MHP::InstToThreadSummaryMap

Definition at line 70 of file MHP.h.

LockSpan

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

Definition at line 73 of file MHP.h.

LoopBBs

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

Definition at line 71 of file MHP.h.

SymJoinToLoopMap

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

protected

Definition at line 196 of file MHP.h.

ThreadStmtToThreadInterleav

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

Definition at line 58 of file MHP.h.

Member Enumeration Documentation

StateRepresentation

enum class SVF::MHP::StateRepresentation

strong

Enumerator
MaterializedContexts
QuerySummaries

Definition at line 78 of file MHP.h.

    {
        MaterializedContexts,
        QuerySummaries
    };

Constructor & Destructor Documentation

~MHP()

MHP::~MHP ( )

virtual

Destructor.

Destructor

Definition at line 105 of file MHP.cpp.

{
    delete fja;
}

MHP()

MHP::MHP ( TCT * t, StateRepresentation representation = StateRepresentation::MaterializedContexts )

explicitprotected

Construction is paired with ForkJoinAnalysis initialization by create().

Parameters

representation

Keep per-context copies for clients that enumerate raw states (the pre-analysis detector and slicer). Main-phase clients issue only MHP queries and can use the exact projected query summary instead.

Constructor

Definition at line 48 of file MHP.cpp.

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

Member Function Documentation

addInterleavingBits()

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

inlineprotected

Definition at line 220 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 211 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 203 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 115 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 129 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);
                }
            }
        }
    }

    if (stateRepresentation == StateRepresentation::MaterializedContexts)
        updateNonCandidateFunInterleaving(icfg, cg);
    buildQuerySummaries(icfg, cg);
 
    if (Options::PrintInterLev())
        printInterleaving();
}

buildQuerySummaries()

template<class ICFGGraph, class CGGraph>

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

protected

Build the exact, context-compressed representation used by repeated MHP queries after the context-sensitive fixed point has converged.

Compress the converged context-sensitive states for repeated MHP queries. Contexts are retained in the propagation maps; this is a query-only index and therefore cannot change the fixed point.

Definition at line 201 of file MHP.cpp.

{
    instToThreadSummary.clear();
    querySummaryOwner.clear();
    for (const auto& instAndStates : instToTSMap)
    {
        NodeThreadSummary& summary = instToThreadSummary[instAndStates.first];
        for (const CxtThreadStmt& state : instAndStates.second)
        {
            const NodeID tid = state.getTid();
            summary.tids.set(tid);
            ThreadStmtToThreadInterleav::const_iterator it =
                threadStmtToThreadInterLeav.find(state);
            assert(it != threadStmtToThreadInterLeav.end() &&
                   "MHP query summary requires a converged context state");
            summary.interleavingByTid[tid] |= it->second;
        }
    }
 
    if (stateRepresentation == StateRepresentation::MaterializedContexts)
        return;
 
    // The materialized representation copies a non-candidate function entry's state
    // unchanged to each of that function's nodes. Main-phase clients need only
    // query answers, so project the already-compressed entry summary instead of
    // creating one CxtThreadStmt and one NodeBS per context at every node.
    using CGTraits = GenericGraphTraits<CGGraph>;
    for (auto nodeIt = CGTraits::nodes_begin(cg),
            nodeEnd = CGTraits::nodes_end(cg); nodeIt != nodeEnd; ++nodeIt)
    {
        const CallGraphNode* callGraphNode = CGTraits::getRawNode(*nodeIt);
        const FunObjVar* fun = callGraphNode->getFunction();
        if (tct->isCandidateFun(fun) || isExtCall(fun))
            continue;
 
        const ICFGNode* entryNode =
            GenericGraphTraits<ICFGGraph>::getFunEntry(icfg, fun);
        InstToThreadSummaryMap::const_iterator entryIt =
            instToThreadSummary.find(entryNode);
        if (entryIt == instToThreadSummary.end())
            continue;
 
        std::vector<const ICFGNode*> funICFGNodes;
        GenericGraphTraits<ICFGGraph>::getFunICFGNodes(icfg, fun, funICFGNodes);
        for (const ICFGNode* node : funICFGNodes)
        {
            if (node == entryNode)
                continue;
            const bool inserted = querySummaryOwner.emplace(node, entryNode).second;
            assert(inserted && instToThreadSummary.find(node) == instToThreadSummary.end() &&
                   "non-candidate internal node unexpectedly had a raw MHP state");
            (void)inserted;
        }
    }
}

buildSymJoinKillTables()

void MHP::buildSymJoinKillTables ( )

protected

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

Definition at line 60 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);
        }
    }
}

create()

template<class ICFGGraph, class CGGraph>

std::unique_ptr< MHP > SVF::MHP::create ( TCT * t, ICFGGraph icfg, CGGraph cg, StateRepresentation representation = StateRepresentation::MaterializedContexts )

static

Construct MHP and initialize its graph-dependent ForkJoinAnalysis.

Definition at line 646 of file MHP.h.

{
    std::unique_ptr<MHP> mhp(new MHP(t, representation));
    mhp->fja->analyzeForkJoinPair(icfg, cg);
    mhp->buildSymJoinKillTables();
    return mhp;
}

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

{
    const NodeThreadSummary* summary1 = getThreadSummary(i1);
    const NodeThreadSummary* summary2 = getThreadSummary(i2);
    if (summary1 == nullptr || summary2 == nullptr)
        return true;
 
    for (NodeID tid1 : summary1->tids)
    {
        for (NodeID tid2 : summary2->tids)
        {
            if (tid1 != tid2 || isMultiForkedThread(tid1))
                return false;
        }
    }
    return true;
}

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 729 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 130 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 745 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 110 of file MHP.h.

    {
        return tct;
    }

getThreadCallGraph()

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

inline

Get ThreadCallGraph.

Definition at line 104 of file MHP.h.

    {
        return tcg;
    }

getThreadStmtSet()

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

inline

Get/has ThreadStmt.

Definition at line 142 of file MHP.h.

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

getThreadSummary()

const MHP::NodeThreadSummary * MHP::getThreadSummary

(

const ICFGNode *

inst

)

const

Representation-independent per-thread summary used by MHP clients. Available after analyze() in both materialized and summary-only modes.

Definition at line 257 of file MHP.cpp.

{
    InstToThreadSummaryMap::const_iterator it = instToThreadSummary.find(inst);
    if (it != instToThreadSummary.end())
        return &it->second;
    const auto ownerIt = querySummaryOwner.find(inst);
    if (ownerIt == querySummaryOwner.end())
        return nullptr;
    it = instToThreadSummary.find(ownerIt->second);
    assert(it != instToThreadSummary.end() &&
           "non-candidate query-summary owner has no entry summary");
    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 438 of file MHP.cpp.

{
 
    const ICFGNode* call = cts.getStmt();
    const CallStrCxt& curCxt = cts.getContext();
    const CallICFGNode* cbn = cast<CallICFGNode>(call);
    CallGraphNode* callerNode = tcg->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;
        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 =
                GenericGraphTraits<ICFGGraph>::getFunExit(icfg, svfcallee);
            if (exitInst == nullptr)
                continue;
            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;
        GenericGraphTraits<CGGraph>::getCallees(cg, callSite, callees);
        if (!tct->isCandidateFun(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 341 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 = tcg->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* svfroutine = edge->getDstNode()->getFunction();
        CallStrCxt newCxt = curCxt;
        pushCxt(newCxt, cbn, svfroutine);
        const ICFGNode* stmt = GenericGraphTraits<ICFGGraph>::getFunEntry(icfg, svfroutine);
        CxtThread ct(newCxt, call);
        if (!tct->hasTCTNode(ct))
            continue;
        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 585 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 374 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 316 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);
    std::vector<const CallGraphEdge*> outEdges;
    GenericGraphTraits<CGGraph>::getOutEdges(cg, node, outEdges);
    for (const CallGraphEdge* edge : outEdges)
    {
        const FunObjVar* callee = edge->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 507 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;
        std::vector<const CallICFGNode*> directCalls;
        GenericGraphTraits<CGGraph>::getDirectCalls(cg, edgeConst, directCalls);
        for (const CallICFGNode* callSite : directCalls)
        {
            CallStrCxt newCxt = cts.getContext();
            if (matchAndPopCxt(newCxt, callSite, curFunNode->getFunction()))
            {
                std::vector<const ICFGNode*> succ;
                GenericGraphTraits<ICFGGraph>::getSuccNodes(icfg, cts.getStmt(), succ);
                for (const ICFGNode* dst : succ)
                {
                    if(dst->getFun() == callSite->getFun())
                    {
                        // Iterate over callSite's call string context and use as the successor's context
                        if (!hasThreadStmtSet(callSite))
                            continue;
                        for (const CxtThreadStmt& cxtThreadStmt:
                                getThreadStmtSet(callSite))
                        {
                            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);
                            }
                        }
                    }
                }
            }
        }
        std::vector<const CallICFGNode*> indirectCalls;
        GenericGraphTraits<CGGraph>::getIndirectCalls(cg, edgeConst, indirectCalls);
        for (const CallICFGNode* callSite : indirectCalls)
        {
            CallStrCxt newCxt = cts.getContext();
            if (matchAndPopCxt(newCxt, callSite, curFunNode->getFunction()))
            {
                std::vector<const ICFGNode*> succ;
                GenericGraphTraits<ICFGGraph>::getSuccNodes(icfg, cts.getStmt(), succ);
                for (const ICFGNode* dst : succ)
                {
                    if(dst->getFun() == callSite->getFun())
                    {
                        // Iterate over callSite's call string context and use as the successor's context
                        if (!hasThreadStmtSet(callSite))
                            continue;
                        for (const CxtThreadStmt& cxtThreadStmt:
                                getThreadStmtSet(callSite))
                        {
                            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 134 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 738 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 148 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 759 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 278 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 754 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 257 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 719 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 684 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 297 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 303 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 273 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 854 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 832 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 794 of file MHP.cpp.

{
    const NodeThreadSummary* summary1 = getThreadSummary(i1);
    const NodeThreadSummary* summary2 = getThreadSummary(i2);
    if (summary1 == nullptr || summary2 == nullptr)
        return false;
 
    // Original rule for distinct tids:
    //   exists c1,c2. L(i1,tid1,c1)[tid2] && L(i2,tid2,c2)[tid1].
    // The two context choices are independent, so this is exactly equivalent
    // to testing the two per-tid context unions. No context correlation is lost.
    for (NodeID tid1 : summary1->tids)
    {
        if (summary2->tids.test(tid1) && isMultiForkedThread(tid1))
        {
            numOfMHPQueries++;
            return true;
        }
 
        const auto firstFlowIt = summary1->interleavingByTid.find(tid1);
        assert(firstFlowIt != summary1->interleavingByTid.end());
        for (NodeID tid2 : firstFlowIt->second)
        {
            if (tid1 == tid2 || !summary2->tids.test(tid2))
                continue;
            const auto secondFlowIt = summary2->interleavingByTid.find(tid2);
            assert(secondFlowIt != summary2->interleavingByTid.end());
            if (secondFlowIt->second.test(tid1))
            {
                numOfMHPQueries++;
                return true;
            }
        }
    }
    return false;
}

popFromCTSWorkList()

CxtThreadStmt SVF::MHP::popFromCTSWorkList ( )

inlineprotected

Definition at line 290 of file MHP.h.

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

printInterleaving()

void MHP::printInterleaving

(

)

Print interleaving results.

Print interleaving results

Definition at line 887 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 265 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 286 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 229 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 610 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 275 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.
    using CGTraits = GenericGraphTraits<CGGraph>;
    for (auto nodeIt = CGTraits::nodes_begin(cg),
            nodeEnd = CGTraits::nodes_end(cg); nodeIt != nodeEnd; ++nodeIt)
    {
        const CallGraphNode* callGraphNode = CGTraits::getRawNode(*nodeIt);
        const FunObjVar* fun = callGraphNode->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 654 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 326 of file MHP.h.

cxtStmtList

CxtThreadStmtWorkList SVF::MHP::cxtStmtList

protected

CxtThreadStmt worklist.

Definition at line 324 of file MHP.h.

fja

ForkJoinAnalysis* SVF::MHP::fja

protected

ForJoin Analysis.

Definition at line 323 of file MHP.h.

instToThreadSummary

InstToThreadSummaryMap SVF::MHP::instToThreadSummary

protected

Exact per-node/per-tid query compression.

Definition at line 329 of file MHP.h.

instToTSMap

InstToThreadStmtSetMap SVF::MHP::instToTSMap

protected

Map an instruction to its ThreadStmtSet.

Definition at line 328 of file MHP.h.

interleavingQueriesTime

double SVF::MHP::interleavingQueriesTime

Definition at line 338 of file MHP.h.

interleavingTime

double SVF::MHP::interleavingTime

Definition at line 337 of file MHP.h.

nonCandidateFuncMHPRelMap

FuncPairToBool SVF::MHP::nonCandidateFuncMHPRelMap

protected

Definition at line 332 of file MHP.h.

numOfMHPQueries

u32_t SVF::MHP::numOfMHPQueries

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

Definition at line 336 of file MHP.h.

numOfTotalQueries

u32_t SVF::MHP::numOfTotalQueries

Total number of queries.

Definition at line 335 of file MHP.h.

querySummaryOwner

Map<const ICFGNode*, const ICFGNode*> SVF::MHP::querySummaryOwner

protected

Non-candidate node -> entry summary.

Definition at line 330 of file MHP.h.

stateRepresentation

StateRepresentation SVF::MHP::stateRepresentation

protected

Definition at line 331 of file MHP.h.

symJoinLoop

SymJoinToLoopMap SVF::MHP::symJoinLoop

protected

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

Definition at line 327 of file MHP.h.

tcg

ThreadCallGraph* SVF::MHP::tcg

protected

TCG.

Definition at line 321 of file MHP.h.

tct

TCT* SVF::MHP::tct

protected

TCT.

Definition at line 322 of file MHP.h.

threadStmtToThreadInterLeav

ThreadStmtToThreadInterleav SVF::MHP::threadStmtToThreadInterLeav

protected

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