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
 */
 
#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, StateRepresentation representation)
    : tcg(t->getThreadCallGraph()), tct(t),
      stateRepresentation(representation),
      numOfTotalQueries(0), numOfMHPQueries(0),
      interleavingTime(0), interleavingQueriesTime(0)
{
    fja = new ForkJoinAnalysis(tct);
}

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);
                }
            }
        }
    }

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

template<class ICFGGraph, class CGGraph>
void MHP::buildQuerySummaries(ICFGGraph icfg, CGGraph cg)
{
    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;
        }
    }
}
 
const MHP::NodeThreadSummary* MHP::getThreadSummary(const ICFGNode* inst) const
{
    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;
}

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.
    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);
            }
        }
    }
}

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);
    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);
        }
    }
}

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);
    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);
}

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);
    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!");
    }
}

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;
        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);
                            }
                        }
                    }
                }
            }
        }
    }
}

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)
{
    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;
}
 
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)
{
    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;
}

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));
    //         }
    //     }
    // }
}

template<class ICFGGraph, class CGGraph>
void ForkJoinAnalysis::analyzeForkJoinPair(ICFGGraph icfg, CGGraph cg)
{
    for (const std::pair<const NodeID, TCTNode*>& tpair : *tct)
    {
        const CxtThread& ct = tpair.second->getCxtThread();
        const NodeID rootTid = tpair.first;
        clearFlagMap();
        if (const ICFGNode* forkInst = ct.getThread())
        {
            std::vector<const ICFGNode*> successors;
            GenericGraphTraits<ICFGGraph>::getSuccNodes(
                icfg, forkInst, successors);
            for (const ICFGNode* successor : successors)
            {
                if (successor->getFun() == forkInst->getFun())
                {
                    for (const auto& forkSiteCxt : tct->getCxtOfCxtThread(ct))
                    {
                        CxtStmt newCts(forkSiteCxt.second, successor);
                        markCxtStmtFlag(newCts, TDAlive);
                    }
                }
            }
 
            while (!cxtStmtList.empty())
            {
                CxtStmt cts = popFromCTSWorkList();
                const ICFGNode* curInst = cts.getStmt();
                DBOUT(DMTA, outs() << "-----\nForkJoinAnalysis root thread: " << tpair.first << " ");
                DBOUT(DMTA, cts.dump());
                DBOUT(DMTA, outs() << "-----\n");
                if (isTDFork(curInst))
                {
                    handleFork(icfg, cg, cts, rootTid);
                }
                else if (isTDJoin(curInst))
                {
                    handleJoin(icfg, cg, cts, rootTid);
                }
                else if (tct->isCallSite(curInst) && !tct->isExtCall(curInst))
                {
                    const CallICFGNode *callSite = SVFUtil::cast<CallICFGNode>(curInst);
                    CallGraph::FunctionSet callees;
                    GenericGraphTraits<CGGraph>::getCallees(
                        cg, callSite, callees);
                    if (!tct->isCandidateFun(callees))
                    {
                        // Do not dive into non-candidate functions
                        CxtStmt newCts(cts.getContext(), callSite->getRetICFGNode());
                        markCxtStmtFlag(newCts, cts);
                    }
                    else
                    {
                        handleCall(icfg, cg, cts);
                    }
                }
                else if (SVFUtil::dyn_cast<FunExitICFGNode>(curInst))
                {
                    handleRet(icfg, cg, cts);
                }
                else
                {
                    handleIntra(icfg, cts);
                }

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

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

template<class ICFGGraph, class CGGraph>
void ForkJoinAnalysis::handleJoin(ICFGGraph icfg, CGGraph cg,
                                  const CxtStmt& cts, NodeID rootTid)
{
    const ICFGNode* call = cts.getStmt();
    const CallStrCxt& curCxt = cts.getContext();
 
    assert(isTDJoin(call));
    const CallICFGNode* cbn = cast<CallICFGNode>(call);
    CallGraphNode* callerNode = getTCG()->getCallGraphNode(cbn->getFun());
    std::vector<const CallGraphEdge*> outEdges;
    GenericGraphTraits<CGGraph>::getOutEdges(cg, callerNode, outEdges);
    bool hasCallGraphEdge = false;
    for (const CallGraphEdge* edge : outEdges)
    {
        if (GenericGraphTraits<CGGraph>::containsCallSite(cg, edge, cbn))
        {
            hasCallGraphEdge = true;
            break;
        }
    }
    if (hasCallGraphEdge)
    {
        const ICFGNode* forkSite = tct->getTCTNode(rootTid)->getCxtThread().getThread();
        const ICFGNode* joinSite = cts.getStmt();
 
        if (hasJoinLoop(SVFUtil::cast<CallICFGNode>(joinSite)))
        {
            if (isAliasedForkJoin(SVFUtil::cast<CallICFGNode>(forkSite),
                                  SVFUtil::cast<CallICFGNode>(joinSite)) &&
                    isSameSCEV(forkSite,joinSite)
               )
            {
                LoopBBs& joinLoop = getJoinLoop(SVFUtil::cast<CallICFGNode>(joinSite));
                std::vector<const SVFBasicBlock *> exitbbs;
                joinSite->getFun()->getExitBlocksOfLoop(joinSite->getBB(), exitbbs);
                while (!exitbbs.empty())
                {
                    const SVFBasicBlock* eb = exitbbs.back();
                    exitbbs.pop_back();
                    const ICFGNode* svfEntryInst = eb->front();
                    CxtStmt newCts(curCxt, svfEntryInst);
                    addDirectlyJoinTID(cts, rootTid);
                    if (isSameSCEV(forkSite, joinSite))
                    {
                        markCxtStmtFlag(newCts, TDDead);
                        addSymmetricLoopJoin(cts, joinLoop);
                    }
                    else
                        markCxtStmtFlag(cts, TDAlive);
                }
            }
            else
            {
                std::vector<const SVFBasicBlock*> exitbbs;
                joinSite->getFun()->getExitBlocksOfLoop(joinSite->getBB(), exitbbs);
                while (!exitbbs.empty())
                {
                    const SVFBasicBlock* eb = exitbbs.back();
                    exitbbs.pop_back();
                    const ICFGNode* svfEntryInst = eb->front();
                    CxtStmt newCts(curCxt, svfEntryInst);
                    markCxtStmtFlag(newCts, cts);
                }
            }
        }
        else
        {
            if (isAliasedForkJoin(SVFUtil::cast<CallICFGNode>(forkSite),
                                  SVFUtil::cast<CallICFGNode>(joinSite)))
            {
                markCxtStmtFlag(cts, TDDead);
                addDirectlyJoinTID(cts, rootTid);
                DBOUT(DMTA, outs() << "\n\t match join site " << call->toString() << "for thread " << rootTid << "\n");
            }
        }
    }
    handleIntra(icfg, cts);
}

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

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

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

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);
}
 
template void ForkJoinAnalysis::analyzeForkJoinPair<ICFG*, CallGraph*>(
    ICFG*, CallGraph*);
template void ForkJoinAnalysis::analyzeForkJoinPair<
    const SlicedICFGView*, const SlicedThreadCallGraphView*>(
        const SlicedICFGView*, const SlicedThreadCallGraphView*);
 
// 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*);