MHP.cpp

Go to the documentation of this file.

//===- MHP.cpp -- May-happen-in-parallel analysis-------------//
//
//                     SVF: Static Value-Flow Analysis
//
// Copyright (C) <2013->  <Yulei Sui>
//
 
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU Affero General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
 
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU Affero General Public License for more details.
 
// You should have received a copy of the GNU Affero General Public License
// along with this program.  If not, see <http://www.gnu.org/licenses/>.
//
//===----------------------------------------------------------------------===//
 
/*
 * MHP.cpp
 *
 *  Created on: Jan 21, 2014
 *      Author: Yulei Sui, Peng Di
 *
 * May-happen-in-parallel analysis. One implementation runs on the whole program
 * or a slice via the templated analyze(), which is parameterised on the two
 * graphs it traverses (whole ICFG/CallGraph or their sliced views) and calls
 * their GenericGraphTraits directly, as used by "Multi-Stage On-Demand Program Slicing for
 * Modular Analysis of Multi-Threaded Programs" (ISSTA 2026).
 */
 
#include "Util/Options.h"
#include "MTA/MHP.h"
#include "MTA/MTA.h"
#include "MTA/LockAnalysis.h"
#include "MTA/MTASlicer.h"
#include "Util/SVFUtil.h"
#include "Util/PTAStat.h"
#include "Graphs/ThreadCallGraph.h"
#include "Graphs/SlicedGraphs.h"
#include "SVFIR/SVFIR.h"
#include "WPA/Andersen.h"
 
using namespace SVF;
using namespace SVFUtil;
 
MHP::MHP(TCT* t) : tcg(t->getThreadCallGraph()), tct(t), numOfTotalQueries(0), numOfMHPQueries(0),
    interleavingTime(0), interleavingQueriesTime(0)
{
    fja = new ForkJoinAnalysis(tct);
    fja->analyzeForkJoinPair();
    buildSymJoinKillTables();
}
 
void MHP::buildSymJoinKillTables()
{
    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);
        }
    }
}
 
NodeBS MHP::edgeFlow(const CxtThreadStmt& cts, const ICFGNode* dst)
{
    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;
}
 
MHP::~MHP()
{
    delete fja;
}
 
 
template<class ICFGGraph, class CGGraph>
void MHP::analyze(ICFGGraph icfg, CGGraph cg)
{
    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);
}
 
template<class ICFGGraph, class CGGraph>
void MHP::analyzeInterleaving(ICFGGraph icfg, CGGraph cg)
{
    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();
}
 
template<class ICFGGraph, class CGGraph>
void MHP::updateNonCandidateFunInterleaving(ICFGGraph icfg, CGGraph cg)
{
    // 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);
            }
        }
    }
}
 
template<class ICFGGraph, class CGGraph>
void MHP::handleNonCandidateFun(ICFGGraph icfg, CGGraph cg, const CxtThreadStmt& cts)
{
    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);
        }
    }
}
 
template<class ICFGGraph, class CGGraph>
void MHP::handleFork(ICFGGraph icfg, CGGraph cg, const CxtThreadStmt& cts, NodeID rootTid)
{
 
    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);
}
 
template<class ICFGGraph, class CGGraph>
void MHP::handleJoin(ICFGGraph icfg, CGGraph cg, const CxtThreadStmt& cts, NodeID rootTid)
{
 
    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);
}
 
template<class ICFGGraph, class CGGraph>
void MHP::handleCall(ICFGGraph icfg, CGGraph cg, const CxtThreadStmt& cts, NodeID rootTid)
{
 
    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!");
    }
}
 
template<class ICFGGraph, class CGGraph>
void MHP::handleRet(ICFGGraph icfg, CGGraph cg, const CxtThreadStmt& cts)
{
    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);
                            }
                        }
                    }
                }
            }
        }
    }
}
 
template<class ICFGGraph, class CGGraph>
void MHP::handleIntra(ICFGGraph icfg, CGGraph cg, const CxtThreadStmt& cts)
{
    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);
        }
    }
}
 
template<class ICFGGraph, class CGGraph>
void MHP::updateAncestorThreads(ICFGGraph icfg, CGGraph cg, NodeID curTid)
{
    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);
                    }
                }
            }
        }
    }
}
 
template<class ICFGGraph, class CGGraph>
void MHP::updateSiblingThreads(ICFGGraph icfg, CGGraph cg, NodeID curTid)
{
    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");
    }
}
 
bool MHP::isRecurFullJoin(NodeID parentTid, NodeID curTid)
{
    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;
}
 
bool MHP::isMustJoin(NodeID curTid, const ICFGNode* joinsite)
{
    const CallICFGNode* call = SVFUtil::dyn_cast<CallICFGNode>(joinsite);
    assert(call && isTDJoin(call) && "not a join site!");
    return !isMultiForkedThread(curTid) && !tct->isJoinSiteInRecursion(call);
}
 
NodeBS MHP::getDirAndIndJoinedTid(const CallStrCxt& cxt, const ICFGNode* call)
{
    CxtStmt cs(cxt, call);
    return fja->getDirAndIndJoinedTid(cs);
}
 
bool MHP::hasJoinInSymmetricLoop(const CallStrCxt& cxt, const ICFGNode* call) const
{
    CxtStmt cs(cxt, call);
    return fja->hasJoinInSymmetricLoop(cs);
}
 
const MHP::LoopBBs& MHP::getJoinInSymmetricLoop(const CallStrCxt& cxt, const ICFGNode* call) const
{
    CxtStmt cs(cxt, call);
    return fja->getJoinInSymmetricLoop(cs);
}
 
bool MHP::isHBPair(NodeID tid1, NodeID tid2)
{
    return fja->isHBPair(tid1, tid2);
}
 
bool MHP::isConnectedfromMain(const FunObjVar* fun)
{
    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;
}
 
bool MHP::mayHappenInParallelInst(const ICFGNode* i1, const ICFGNode* i2)
{
 
    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;
}
 
bool MHP::mayHappenInParallelCache(const ICFGNode* i1, const ICFGNode* i2)
{
    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);
}
 
bool MHP::mayHappenInParallel(const ICFGNode* i1, const ICFGNode* i2)
{
    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;
}
 
bool MHP::executedByTheSameThread(const ICFGNode* i1, const ICFGNode* i2)
{
    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;
}
 
void MHP::printInterleaving()
{
    for (const auto& pair : threadStmtToThreadInterLeav)
    {
        outs() << "( t" << pair.first.getTid()
               << pair.first.getStmt()->toString() << " ) ==> [";
        for (unsigned i : pair.second)
        {
            outs() << " " << i << " ";
        }
        outs() << "]\n";
    }
}
 
void ForkJoinAnalysis::collectSCEVInfo()
{
    // typedef Set<const ICFGNode*> CallInstSet;
    // typedef Map<const FunObjVar*, CallInstSet> FunToFJSites;
    // FunToFJSites funToFJSites;
 
    // for (ThreadCallGraph::CallSiteSet::const_iterator it = tct->getThreadCallGraph()->forksitesBegin(),
    //         eit = tct->getThreadCallGraph()->forksitesEnd();
    //         it != eit; ++it)
    // {
    //     const ICFGNode* fork = *it;
    //     funToFJSites[fork->getFun()].insert(fork);
    // }
 
    // for (ThreadCallGraph::CallSiteSet::const_iterator it = tct->getThreadCallGraph()->joinsitesBegin(),
    //         eit = tct->getThreadCallGraph()->joinsitesEnd();
    //         it != eit; ++it)
    // {
    //     const ICFGNode* join = *it;
    //     funToFJSites[join->getFun()].insert(join);
    // }
 
    // for(FunToFJSites::const_iterator it = funToFJSites.begin(), eit = funToFJSites.end(); it!=eit; ++it)
    // {
    //     // ScalarEvolution* SE = MTA::getSE(it->first);
    //     for(CallInstSet::const_iterator sit = it->second.begin(), esit = it->second.end(); sit!=esit; ++sit)
    //     {
    //         const SVFInstruction* callInst =  *sit;
    //         if(tct->getThreadCallGraph()->isForksite(getCBN(callInst)))
    //         {
    //             // const SVFValue* forkSiteTidPtr = getForkedThread(callInst);
    //             // const SCEV *forkSiteTidPtrSCEV = SE->getSCEV(const_cast<Value*>(forkSiteTidPtr));
    //             // const SCEV *baseForkTidPtrSCEV = SE->getSCEV(const_cast<Value*>(getBasePtr(forkSiteTidPtr)));
    //             // forkSiteTidPtrSCEV = getSCEVMinusExpr(forkSiteTidPtrSCEV, baseForkTidPtrSCEV, SE);
    //             // PTASCEV scev(forkSiteTidPtr,nullptr,nullptr);
    //             // fkjnToPTASCEVMap.insert(std::make_pair(callInst,scev));
    //         }
    //         else
    //         {
    //             // const SVFValue* joinSiteTidPtr = getJoinedThread(callInst);
    //             //const SCEV *joinSiteTidPtrSCEV = SE->getSCEV(const_cast<Value*>(joinSiteTidPtr));
    //             //const SCEV *baseJoinTidPtrSCEV = SE->getSCEV(const_cast<Value*>(getBasePtr(joinSiteTidPtr)));
    //             //joinSiteTidPtrSCEV = getSCEVMinusExpr(joinSiteTidPtrSCEV, baseJoinTidPtrSCEV, SE);
 
    //             // PTASCEV scev(joinSiteTidPtr,nullptr,nullptr);
    //             // fkjnToPTASCEVMap.insert(std::make_pair(callInst,scev));
    //         }
    //     }
    // }
}
 
void ForkJoinAnalysis::analyzeForkJoinPair()
{
    for (const std::pair<const NodeID, TCTNode*>& tpair : *tct)
    {
        const CxtThread& ct = tpair.second->getCxtThread();
        const NodeID rootTid = tpair.first;
        clearFlagMap();
        if (const ICFGNode* forkInst = ct.getThread())
        {
            for(const ICFGEdge* outEdge : forkInst->getOutEdges())
            {
                if(outEdge->getDstNode()->getFun() == forkInst->getFun())
                {
                    for (const auto& forkSiteCxt : tct->getCxtOfCxtThread(ct))
                    {
                        CxtStmt newCts(forkSiteCxt.second, outEdge->getDstNode());
                        markCxtStmtFlag(newCts, TDAlive);
                    }
                }
            }
 
            while (!cxtStmtList.empty())
            {
                CxtStmt cts = popFromCTSWorkList();
                const ICFGNode* curInst = cts.getStmt();
                DBOUT(DMTA, outs() << "-----\nForkJoinAnalysis root thread: " << tpair.first << " ");
                DBOUT(DMTA, cts.dump());
                DBOUT(DMTA, outs() << "-----\n");
                CallGraph::FunctionSet callees;
                if (isTDFork(curInst))
                {
                    handleFork(cts, rootTid);
                }
                else if (isTDJoin(curInst))
                {
                    handleJoin(cts, rootTid);
                }
                else if (tct->isCallSite(curInst) && !tct->isExtCall(curInst))
                {
                    const CallICFGNode *callSite = SVFUtil::cast<CallICFGNode>(curInst);
                    CallGraph::FunctionSet callees;
                    if (!tct->isCandidateFun(getCallee(callSite, callees)))
                    {
                        // Do not dive into non-candidate functions
                        CxtStmt newCts(cts.getContext(), callSite->getRetICFGNode());
                        markCxtStmtFlag(newCts, cts);
                    }
                    else
                    {
                        handleCall(cts, rootTid);
                    }
                }
                else if (SVFUtil::dyn_cast<FunExitICFGNode>(curInst))
                {
                    handleRet(cts);
                }
                else
                {
                    handleIntra(cts);
                }
 
                for (NodeID parentTid : tct->getParentThreads(rootTid))
                {
                    const CxtThread& parentCxtThread = tct->getTCTNode(parentTid)->getCxtThread();
                    const FunObjVar* parentRoutine = tct->getStartRoutineOfCxtThread(parentCxtThread);
                    if (curInst == parentRoutine->getExitBB()->back())
                    {
                        if (getMarkedFlag(cts) != TDAlive)
                            addToFullJoin(parentTid, rootTid);
                        else
                            addToPartial(parentTid, rootTid);
                    }
                }
            }
        }
    }
}
 
void ForkJoinAnalysis::handleFork(const CxtStmt& cts, NodeID rootTid)
{
    const ICFGNode* call = cts.getStmt();
    const CallStrCxt& curCxt = cts.getContext();
 
    assert(isTDFork(call));
    const CallICFGNode* cbn = cast<CallICFGNode>(call);
    if (getTCG()->hasThreadForkEdge(cbn))
    {
        for (ThreadCallGraph::ForkEdgeSet::const_iterator cgIt = getTCG()->getForkEdgeBegin(cbn),
                ecgIt = getTCG()->getForkEdgeEnd(cbn);
                cgIt != ecgIt; ++cgIt)
        {
            const FunObjVar* callee = (*cgIt)->getDstNode()->getFunction();
            CallStrCxt newCxt = curCxt;
            pushCxt(newCxt, cbn, callee);
            CxtThread ct(newCxt, call);
            if (getMarkedFlag(cts) != TDAlive)
                addToHBPair(rootTid, tct->getTCTNode(ct)->getId());
            else
                addToHPPair(rootTid, tct->getTCTNode(ct)->getId());
        }
    }
    handleIntra(cts);
}
 
void ForkJoinAnalysis::handleJoin(const CxtStmt& cts, NodeID rootTid)
{
    const ICFGNode* call = cts.getStmt();
    const CallStrCxt& curCxt = cts.getContext();
 
    assert(isTDJoin(call));
    const CallICFGNode* cbn = cast<CallICFGNode>(call);
    if (getTCG()->hasCallGraphEdge(cbn))
    {
        const ICFGNode* forkSite = tct->getTCTNode(rootTid)->getCxtThread().getThread();
        const ICFGNode* joinSite = cts.getStmt();
 
        if (hasJoinLoop(SVFUtil::cast<CallICFGNode>(joinSite)))
        {
            if (isAliasedForkJoin(SVFUtil::cast<CallICFGNode>(forkSite),
                                  SVFUtil::cast<CallICFGNode>(joinSite)) &&
                    isSameSCEV(forkSite,joinSite)
               )
            {
                LoopBBs& joinLoop = getJoinLoop(SVFUtil::cast<CallICFGNode>(joinSite));
                std::vector<const SVFBasicBlock *> exitbbs;
                joinSite->getFun()->getExitBlocksOfLoop(joinSite->getBB(), exitbbs);
                while (!exitbbs.empty())
                {
                    const SVFBasicBlock* eb = exitbbs.back();
                    exitbbs.pop_back();
                    const ICFGNode* svfEntryInst = eb->front();
                    CxtStmt newCts(curCxt, svfEntryInst);
                    addDirectlyJoinTID(cts, rootTid);
                    if (isSameSCEV(forkSite, joinSite))
                    {
                        markCxtStmtFlag(newCts, TDDead);
                        addSymmetricLoopJoin(cts, joinLoop);
                    }
                    else
                        markCxtStmtFlag(cts, TDAlive);
                }
            }
            else
            {
                std::vector<const SVFBasicBlock*> exitbbs;
                joinSite->getFun()->getExitBlocksOfLoop(joinSite->getBB(), exitbbs);
                while (!exitbbs.empty())
                {
                    const SVFBasicBlock* eb = exitbbs.back();
                    exitbbs.pop_back();
                    const ICFGNode* svfEntryInst = eb->front();
                    CxtStmt newCts(curCxt, svfEntryInst);
                    markCxtStmtFlag(newCts, cts);
                }
            }
        }
        else
        {
            if (isAliasedForkJoin(SVFUtil::cast<CallICFGNode>(forkSite),
                                  SVFUtil::cast<CallICFGNode>(joinSite)))
            {
                markCxtStmtFlag(cts, TDDead);
                addDirectlyJoinTID(cts, rootTid);
                DBOUT(DMTA, outs() << "\n\t match join site " << call->toString() << "for thread " << rootTid << "\n");
            }
        }
    }
    handleIntra(cts);
}
 
void ForkJoinAnalysis::handleCall(const CxtStmt& cts, NodeID rootTid)
{
 
    const ICFGNode* call = cts.getStmt();
    const CallStrCxt& curCxt = cts.getContext();
    const CallICFGNode* cbn = SVFUtil::cast<CallICFGNode>(call);
    if (getTCG()->hasCallGraphEdge(cbn))
    {
        for (CallGraph::CallGraphEdgeSet::const_iterator cgIt = getTCG()->getCallEdgeBegin(cbn),
                ecgIt = getTCG()->getCallEdgeEnd(cbn);
                cgIt != ecgIt; ++cgIt)
        {
            const FunObjVar* svfcallee = (*cgIt)->getDstNode()->getFunction();
            if (isExtCall(svfcallee))
                continue;
            CallStrCxt newCxt = curCxt;
            pushCxt(newCxt, cbn, svfcallee);
            const ICFGNode* svfEntryInst = svfcallee->getEntryBlock()->front();
            CxtStmt newCts(newCxt, svfEntryInst);
            markCxtStmtFlag(newCts, cts);
        }
    }
}
 
void ForkJoinAnalysis::handleRet(const CxtStmt& cts)
{
    const ICFGNode* curInst = cts.getStmt();
    const CallStrCxt& curCxt = cts.getContext();
 
    CallGraphNode* curFunNode = getTCG()->getCallGraphNode(curInst->getFun());
    for (CallGraphEdge* edge : curFunNode->getInEdges())
    {
        if (SVFUtil::isa<ThreadForkEdge, ThreadJoinEdge>(edge))
            continue;
        for (CallGraphEdge::CallInstSet::const_iterator cit = edge->directCallsBegin(),
                ecit = edge->directCallsEnd();
                cit != ecit; ++cit)
        {
            CallStrCxt newCxt = curCxt;
            const ICFGNode* curNode = (*cit);
            if (matchAndPopCxt(newCxt, SVFUtil::cast<CallICFGNode>(curNode), curFunNode->getFunction()))
            {
                for(const ICFGEdge* outEdge : curNode->getOutEdges())
                {
                    if(outEdge->getDstNode()->getFun() == curNode->getFun())
                    {
                        // Iterate over callSite's call string context and use as the successor's context
                        if (!hasCxtStmtsFromInst(*cit))
                            continue;
                        for (const CxtStmt& cxtStmt: getCxtStmtsFromInst(*cit))
                        {
                            CallStrCxt callSiteCxt = cxtStmt.getContext();
                            // If new context is a suffix of the call site context
                            if (isContextSuffix(newCxt, callSiteCxt))
                            {
                                CxtStmt newCts(callSiteCxt, outEdge->getDstNode());
                                markCxtStmtFlag(newCts, cts);
                            }
                        }
                    }
                }
            }
        }
        for (CallGraphEdge::CallInstSet::const_iterator cit = edge->indirectCallsBegin(),
                ecit = edge->indirectCallsEnd();
                cit != ecit; ++cit)
        {
            CallStrCxt newCxt = curCxt;
            const ICFGNode* curNode = (*cit);
 
            if (matchAndPopCxt(newCxt, SVFUtil::cast<CallICFGNode>(curNode), curFunNode->getFunction()))
            {
                for(const ICFGEdge* outEdge : curNode->getOutEdges())
                {
                    if(outEdge->getDstNode()->getFun() == curNode->getFun())
                    {
                        // Iterate over callSite's call string context and use as the successor's context
                        if (!hasCxtStmtsFromInst(*cit))
                            continue;
                        for (const CxtStmt& cxtStmt: getCxtStmtsFromInst(*cit))
                        {
                            CallStrCxt callSiteCxt = cxtStmt.getContext();
                            // If new context is a suffix of the call site context
                            if (isContextSuffix(newCxt, callSiteCxt))
                            {
                                CxtStmt newCts(callSiteCxt, outEdge->getDstNode());
                                markCxtStmtFlag(newCts, cts);
                            }
                        }
                    }
                }
            }
        }
    }
}
 
void ForkJoinAnalysis::handleIntra(const CxtStmt& cts)
{
 
    const ICFGNode* curInst = cts.getStmt();
    const CallStrCxt& curCxt = cts.getContext();
 
    for(const ICFGEdge* outEdge : curInst->getOutEdges())
    {
        if(outEdge->getDstNode()->getFun() == curInst->getFun())
        {
            CxtStmt newCts(curCxt, outEdge->getDstNode());
            markCxtStmtFlag(newCts, cts);
        }
    }
}
 
NodeBS ForkJoinAnalysis::getDirAndIndJoinedTid(const CxtStmt& cs)
{
 
    CxtStmtToTIDMap::const_iterator it = dirAndIndJoinMap.find(cs);
    if (it != dirAndIndJoinMap.end())
        return it->second;
 
    const NodeBS& directJoinTids = getDirectlyJoinedTid(cs);
    NodeBS allJoinTids = directJoinTids;
 
    FIFOWorkList<NodeID> worklist;
    for (unsigned id : directJoinTids)
    {
        worklist.push(id);
    }
 
    while (!worklist.empty())
    {
        NodeID tid = worklist.pop();
        TCTNode* node = tct->getTCTNode(tid);
        for (TCT::ThreadCreateEdgeSet::const_iterator it = tct->getChildrenBegin(node), eit = tct->getChildrenEnd(node); it != eit; ++it)
        {
            NodeID childTid = (*it)->getDstID();
            if (isFullJoin(tid, childTid))
            {
                allJoinTids.set(childTid);
                worklist.push(childTid);
            }
        }
    }
 
    dirAndIndJoinMap[cs] = allJoinTids;
 
    return allJoinTids;
}
 
// static bool accessSameArrayIndex(const GetElementPtrInst* ptr1, const GetElementPtrInst* ptr2)
// {
 
//     std::vector<u32_t> ptr1vec;
//     for (gep_type_iterator gi = gep_type_begin(*ptr1), ge = gep_type_end(*ptr1);
//             gi != ge; ++gi)
//     {
//         if(SVFConstantInt* ci = SVFUtil::dyn_cast<SVFConstantInt>(LLVMModuleSet::getLLVMModuleSet()->getSVFValue(gi.getOperand())))
//         {
//             s32_t idx = ci->getSExtValue();
//             ptr1vec.push_back(idx);
//         }
//         else
//             return false;
//     }
 
//     std::vector<u32_t> ptr2vec;
//     for (gep_type_iterator gi = gep_type_begin(*ptr2), ge = gep_type_end(*ptr2);
//             gi != ge; ++gi)
//     {
//         if(SVFConstantInt* ci = SVFUtil::dyn_cast<SVFConstantInt>(LLVMModuleSet::getLLVMModuleSet()->getSVFValue(gi.getOperand())))
//         {
//             s32_t idx = ci->getSExtValue();
//             ptr2vec.push_back(idx);
//         }
//         else
//             return false;
//     }
 
//     return ptr1vec==ptr2vec;
// }
 
bool ForkJoinAnalysis::isSameSCEV(const ICFGNode* forkSite, const ICFGNode* joinSite)
{
 
    // const PTASCEV& forkse = fkjnToPTASCEVMap[forkSite];
    // const PTASCEV& joinse = fkjnToPTASCEVMap[joinSite];
 
    // //if(sameLoopTripCount(forkSite,joinSite) == false)
    // //  return false;
 
    // if(forkse.inloop && joinse.inloop)
    //     return forkse.start==joinse.start && forkse.step == joinse.step && forkse.tripcount <= joinse.tripcount;
    // else if(SVFUtil::isa<GetElementPtrInst>(forkse.ptr) && SVFUtil::isa<GetElementPtrInst>(joinse.ptr))
    //     return accessSameArrayIndex(SVFUtil::cast<GetElementPtrInst>(forkse.ptr),SVFUtil::cast<GetElementPtrInst>(joinse.ptr));
    // else if(SVFUtil::isa<GetElementPtrInst, GetElementPtrInst>(joinse.ptr))
    //     return false;
    // else
    //     return true;
 
    return false;
}
 
bool ForkJoinAnalysis::sameLoopTripCount(const ICFGNode* forkSite, const ICFGNode* joinSite)
{
 
    // ScalarEvolution* forkSE = getSE(forkSite);
    // ScalarEvolution* joinSE = getSE(joinSite);
 
    // if(tct->hasLoop(forkSite) == false || tct->hasLoop(joinSite) == false)
    //     return false;
 
    // // Get loops
    // const LoopBBs& forkSiteLoop = tct->getLoop(forkSite);
    // const LoopBBs& joinSiteLoop = tct->getLoop(joinSite);
 
    // const SCEV* forkLoopCountScev = forkSE->getBackedgeTakenCount(forkSiteLoop);
    // const SCEV* joinLoopCountScev = joinSE->getBackedgeTakenCount(joinSiteLoop);
 
    // if(forkLoopCountScev!=forkSE->getCouldNotCompute())
    // {
    //     if(forkLoopCountScev==joinLoopCountScev)
    //     {
    //         return true;
    //     }
    // }
    return false;
}
 
bool ForkJoinAnalysis::isAliasedForkJoin(const CallICFGNode* forkSite,
        const CallICFGNode* joinSite)
{
    return getTCG()->getThreadAPI()->isAliasedForkJoin(tct->getPTA(),
            getForkedThread(forkSite), getJoinedThread(joinSite), forkJoinAliasCache);
}
 
// The two graphs the MHP analysis runs on; the algorithm above is written once
// and instantiated for both (all internal templates instantiate transitively).
template void MHP::analyze<ICFG*, CallGraph*>(ICFG*, CallGraph*);
template void MHP::analyze<const SlicedICFGView*, const SlicedThreadCallGraphView*>(const SlicedICFGView*, const SlicedThreadCallGraphView*);