LockAnalysis.cpp

Go to the documentation of this file.

//===- LockAnalysis.cpp -- Analysis of locksets-------------//
//
//                     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/>.
//
//===----------------------------------------------------------------------===//
 
/*
 * LocksetAnalysis.cpp
 *
 *  Created on: 26 Aug 2015
 *      Author: pengd
 *
 * Lock analysis. One implementation runs on the whole program or a slice via
 * the templated analyze() (GraphT = SVFIR* or const SlicedSVFIRView*), as used
 * by "Multi-Stage On-Demand Program Slicing for Modular Analysis of
 * Multi-Threaded Programs" (ISSTA 2026).
 */
 
#include "Util/Options.h"
#include "MTA/LockAnalysis.h"
#include "MTA/MTA.h"
#include "MTA/MTASlicer.h"
#include "Util/SVFUtil.h"
#include "Util/PTAStat.h"
#include "Graphs/ThreadCallGraph.h"
#include "SVFIR/SVFIR.h"
#include "Graphs/SlicedGraphs.h"
 
 
using namespace SVF;
using namespace SVFUtil;
 
 
 
template<class ICFGGraph, class CGGraph>
void LockAnalysis::analyze(ICFGGraph icfg, CGGraph cg)
{
 
    collectLockUnlocksites(icfg, cg);
    buildCandidateFuncSetforLock();
 
    DOTIMESTAT(double lockStart = PTAStat::getClk(true));
 
    DBOUT(DGENERAL, outs() << "\tIntra-procedural LockAnalysis\n");
    DBOUT(DMTA, outs() << "\tIntra-procedural LockAnalysis\n");
    analyzeIntraProcedualLock(icfg, cg);
 
    DBOUT(DGENERAL, outs() << "\tCollect context-sensitive locks\n");
    DBOUT(DMTA, outs() << "\tCollect context-sensitive locks\n");
    collectCxtLock(icfg, cg);
 
    DBOUT(DGENERAL, outs() << "\tInter-procedural LockAnalysis\n");
    DBOUT(DMTA, outs() << "\tInter-procedural LockAnalysis\n");
    analyzeLockSpanCxtStmt(icfg, cg);
 
    DOTIMESTAT(double lockEnd = PTAStat::getClk(true));
    DOTIMESTAT(lockTime += (lockEnd - lockStart) / TIMEINTERVAL);
}
 
 
template<class ICFGGraph, class CGGraph>
void LockAnalysis::collectLockUnlocksites(ICFGGraph icfg, CGGraph cg)
{
    ThreadCallGraph* tcg=tct->getThreadCallGraph();
 
    for (const auto& item : *GenericGraphTraits<CGGraph>::getCallGraph(cg))
    {
        const FunObjVar* F = item.second->getFunction();
        for (auto it : *F)
        {
            const SVFBasicBlock* bb = it.second;
            for (const ICFGNode* icfgNode : bb->getICFGNodeList())
            {
                if (!GenericGraphTraits<ICFGGraph>::containsNode(icfg, icfgNode))
                    continue;
                if (isa<CallICFGNode>(icfgNode) && tcg->getThreadAPI()->isTDRelease(cast<CallICFGNode>(icfgNode)))
                {
                    unlocksites.insert(icfgNode);
                }
                if (isa<CallICFGNode>(icfgNode) && tcg->getThreadAPI()->isTDAcquire(cast<CallICFGNode>(icfgNode)))
                {
                    locksites.insert(icfgNode);
                }
            }
        }
    }
}
 
void LockAnalysis::buildCandidateFuncSetforLock()
{
 
    ThreadCallGraph* tcg=tct->getThreadCallGraph();
 
    TCT::PTACGNodeSet visited;
    FIFOWorkList<const CallGraphNode*> worklist;
 
    for (InstSet::iterator it = locksites.begin(), eit = locksites.end(); it != eit; ++it)
    {
        const FunObjVar* fun=(*it)->getFun();
        CallGraphNode* cgnode = tcg->getCallGraphNode(fun);
        if (visited.find(cgnode) == visited.end())
        {
            worklist.push(cgnode);
            visited.insert(cgnode);
        }
    }
    for (InstSet::iterator it = unlocksites.begin(), eit = unlocksites.end(); it != eit; ++it)
    {
        const FunObjVar* fun = (*it)->getFun();
        CallGraphNode* cgnode = tcg->getCallGraphNode(fun);
        if (visited.find(cgnode) == visited.end())
        {
            worklist.push(cgnode);
            visited.insert(cgnode);
        }
    }
    while (!worklist.empty())
    {
        const CallGraphNode* node = worklist.pop();
        lockcandidateFuncSet.insert(node->getFunction());
        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);
            }
        }
    }
}
 
template<class ICFGGraph, class CGGraph>
void LockAnalysis::analyzeIntraProcedualLock(ICFGGraph icfg, CGGraph cg)
{
 
    // Identify the protected Instructions.
    for (InstSet::const_iterator it = locksites.begin(), ie = locksites.end(); it != ie; ++it)
    {
        const ICFGNode* lockSite = *it;
        assert(isCallSite(lockSite) && "Lock acquire instruction must be a CallSite");
 
        // Perform forward traversal
        InstSet forwardInsts;
        InstSet backwardInsts;
        InstSet unlockSet;
 
        bool forward = intraForwardTraverse(icfg, cg,lockSite,unlockSet,forwardInsts);
        bool backward = intraBackwardTraverse(icfg, cg,unlockSet,backwardInsts);
 
        if(forward && backward)
            addIntraLock(lockSite,forwardInsts);
        else if(forward && !backward)
            addCondIntraLock(lockSite,forwardInsts);
    }
}
 
template<class ICFGGraph, class CGGraph>
bool LockAnalysis::intraForwardTraverse(ICFGGraph icfg, CGGraph cg, const ICFGNode* lockSite, InstSet& unlockSet, InstSet& forwardInsts)
{
 
    const FunObjVar* svfFun = lockSite->getFun();
 
    InstVec worklist;
    worklist.push_back(lockSite);
    while (!worklist.empty())
    {
        const ICFGNode *I = worklist.back();
        worklist.pop_back();
        const ICFGNode* exitInst = svfFun->getExitBB()->back();
        if(exitInst == I)
            return false;
 
        // Skip the visited Instructions.
        if (forwardInsts.find(I)!=forwardInsts.end())
            continue;
        forwardInsts.insert(I);
 
        if (isTDRelease(I) && isAliasedLocks(lockSite, I))
        {
            unlockSet.insert(I);
            DBOUT(DMTA, outs() << "LockAnalysis ci lock   -- " << lockSite->getSourceLoc()<<"\n");
            DBOUT(DMTA, outs() << "LockAnalysis ci unlock -- " << I->getSourceLoc()<<"\n");
            continue;
        }
 
        std::vector<const ICFGNode*> succ;
        GenericGraphTraits<ICFGGraph>::getSuccNodes(icfg, I, succ);
        for (const ICFGNode* dst : succ)
        {
            if(dst->getFun() == I->getFun())
            {
                worklist.push_back(dst);
            }
        }
    }
 
    return true;
}
 
 
template<class ICFGGraph, class CGGraph>
bool LockAnalysis::intraBackwardTraverse(ICFGGraph icfg, CGGraph cg, const InstSet& unlockSet, InstSet& backwardInsts)
{
 
    InstVec worklist;
    for(InstSet::const_iterator it = unlockSet.begin(), eit = unlockSet.end(); it!=eit; ++it)
    {
        const ICFGNode* unlockSite = *it;
        const ICFGNode* entryInst = unlockSite->getFun()->getEntryBlock()->back();
        worklist.push_back(*it);
 
        while (!worklist.empty())
        {
            const ICFGNode *I = worklist.back();
            worklist.pop_back();
 
            if(entryInst == I)
                return false;
 
            // Skip the visited Instructions.
            if (backwardInsts.find(I)!=backwardInsts.end())
                continue;
            backwardInsts.insert(I);
 
            if (isTDAcquire(I) && isAliasedLocks(unlockSite, I))
            {
                DBOUT(DMTA, outs() << "LockAnalysis ci lock   -- " << I->getSourceLoc()<<"\n");
                DBOUT(DMTA, outs() << "LockAnalysis ci unlock -- " << unlockSite->getSourceLoc()<<"\n");
                continue;
            }
 
            std::vector<const ICFGNode*> pred;
            GenericGraphTraits<ICFGGraph>::getPredNodes(icfg, I, pred);
            for (const ICFGNode* src : pred)
            {
                if(src->getFun() == I->getFun())
                {
                    worklist.push_back(src);
                }
            }
        }
    }
 
    return true;
}
 
 
template<class ICFGGraph, class CGGraph>
void LockAnalysis::collectCxtLock(ICFGGraph icfg, CGGraph cg)
{
    const TCT::FunSet& entryFuncSet = tct->getEntryProcs();
    for (TCT::FunSet::const_iterator it = entryFuncSet.begin(), eit = entryFuncSet.end(); it != eit; ++it)
    {
        if (!isLockCandidateFun(*it))
            continue;
        CallStrCxt cxt;
        CxtLockProc t(cxt, *it);
        pushToCTPWorkList(t);
    }
 
    while (!clpList.empty())
    {
        CxtLockProc clp = popFromCTPWorkList();
        CallGraphNode* cgNode = getTCG()->getCallGraphNode(clp.getProc());
        // lzh TODO.
        if (!isLockCandidateFun(cgNode->getFunction()))
            continue;
 
        for (CallGraphNode::const_iterator nit = cgNode->OutEdgeBegin(), neit = cgNode->OutEdgeEnd(); nit != neit; nit++)
        {
            const CallGraphEdge* cgEdge = (*nit);
 
            for (CallGraphEdge::CallInstSet::const_iterator cit = cgEdge->directCallsBegin(), ecit = cgEdge->directCallsEnd();
                    cit != ecit; ++cit)
            {
                DBOUT(DMTA,
                      outs() << "\nCollecting CxtLocks: handling direct call:" << **cit << "\t" << cgEdge->getSrcNode()->getFunction()->getName()
                      << "-->" << cgEdge->getDstNode()->getFunction()->getName() << "\n");
                handleCallRelation(icfg, cg, clp, cgEdge, *cit);
            }
            for (CallGraphEdge::CallInstSet::const_iterator ind = cgEdge->indirectCallsBegin(), eind = cgEdge->indirectCallsEnd();
                    ind != eind; ++ind)
            {
                DBOUT(DMTA,
                      outs() << "\nCollecting CxtLocks: handling indirect call:" << **ind << "\t"
                      << cgEdge->getSrcNode()->getFunction()->getName() << "-->" << cgEdge->getDstNode()->getFunction()->getName()
                      << "\n");
                handleCallRelation(icfg, cg, clp, cgEdge, *ind);
            }
        }
    }
}
 
 
template<class ICFGGraph, class CGGraph>
void LockAnalysis::handleCallRelation(ICFGGraph icfg, CGGraph cg, CxtLockProc& clp, const CallGraphEdge* cgEdge, const CallICFGNode* cs)
{
 
    CallStrCxt cxt(clp.getContext());
    const ICFGNode* curNode = cs;
    if (!GenericGraphTraits<ICFGGraph>::containsNode(icfg, curNode))
        return;
    if (isTDAcquire(curNode))
    {
        addCxtLock(cxt,curNode);
        return;
    }
    const FunObjVar* svfcallee = cgEdge->getDstNode()->getFunction();
    pushCxt(cxt, SVFUtil::cast<CallICFGNode>(curNode), svfcallee);
 
    CxtLockProc newclp(cxt, svfcallee);
    if (pushToCTPWorkList(newclp))
    {
        DBOUT(DMTA, outs() << "LockAnalysis Process CallRet old clp --"; clp.dump());
        DBOUT(DMTA, outs() << "LockAnalysis Process CallRet new clp --"; newclp.dump());
    }
 
}
 
bool LockAnalysis::isAliasedLocks(const ICFGNode* i1, const ICFGNode* i2)
{
    return tct->getPTA()->alias(getLockVal(i1)->getId(), getLockVal(i2)->getId());
}
 
template<class ICFGGraph, class CGGraph>
void LockAnalysis::analyzeLockSpanCxtStmt(ICFGGraph icfg, CGGraph cg)
{
 
    const TCT::FunSet& entryFuncSet = tct->getEntryProcs();
    for (TCT::FunSet::const_iterator it = entryFuncSet.begin(), eit = entryFuncSet.end(); it != eit; ++it)
    {
        if (!isLockCandidateFun(*it))
            continue;
        CallStrCxt cxt;
        const ICFGNode* frontInst = GenericGraphTraits<ICFGGraph>::getFunEntry(icfg, *it);
        if (!GenericGraphTraits<ICFGGraph>::containsNode(icfg, frontInst))
            continue;
        CxtStmt cxtstmt(cxt, frontInst);
        pushToCTSWorkList(cxtstmt);
    }
 
    while (!cxtStmtList.empty())
    {
        CxtStmt cts = popFromCTSWorkList();
 
        touchCxtStmt(cts);
        const ICFGNode* curInst = cts.getStmt();
        if (!GenericGraphTraits<ICFGGraph>::containsNode(icfg, curInst))
            continue;
        instToCxtStmtSet[curInst].insert(cts);
 
        DBOUT(DMTA, outs() << "\nVisit cxtStmt: ");
        DBOUT(DMTA, cts.dump());
 
        DBOUT(DMTA, outs() << "\nIts cxt lock sets: ");
        DBOUT(DMTA, printLocks(cts));
 
        if (isTDFork(curInst))
        {
            handleFork(icfg, cg, cts);
        }
        else if (isTDAcquire(curInst))
        {
            assert(hasCxtLock(cts) && "context-sensitive lock not found!!");
            if(addCxtStmtToSpan(cts,cts))
                handleIntra(icfg, cg, cts);
        }
        else if (isTDRelease(curInst))
        {
            if(removeCxtStmtToSpan(cts,cts))
                handleIntra(icfg, cg, cts);
        }
        else if (isCallSite(curInst) && !isExtCall(curInst))
        {
            handleCall(icfg, cg, cts);
        }
        else if (SVFUtil::dyn_cast<FunExitICFGNode>(curInst))
        {
            handleRet(icfg, cg, cts);
        }
        else
        {
            handleIntra(icfg, cg, cts);
        }
 
    }
 
}
 
 
void LockAnalysis::printLocks(const CxtStmt& cts)
{
    const CxtLockSet & lockset = getCxtLockfromCxtStmt(cts);
    outs() << "\nlock sets size = " << lockset.size() << "\n";
    for (CxtLockSet::const_iterator it = lockset.begin(), eit = lockset.end(); it != eit; ++it)
    {
        (*it).dump();
    }
}
 
 
 
template<class ICFGGraph, class CGGraph>
void LockAnalysis::handleFork(ICFGGraph icfg, CGGraph cg, const CxtStmt& cts)
{
    const CallStrCxt& curCxt = cts.getContext();
    const CallICFGNode* call = SVFUtil::dyn_cast<CallICFGNode>(cts.getStmt());
    if(getTCG()->hasThreadForkEdge(call))
    {
        for (ThreadCallGraph::ForkEdgeSet::const_iterator cgIt = getTCG()->getForkEdgeBegin(call),
                ecgIt = getTCG()->getForkEdgeEnd(call); cgIt != ecgIt; ++cgIt)
        {
            const FunObjVar* svfcallee = (*cgIt)->getDstNode()->getFunction();
            CallStrCxt newCxt = curCxt;
            pushCxt(newCxt,call,svfcallee);
            const ICFGNode* svfInst = GenericGraphTraits<ICFGGraph>::getFunEntry(icfg, svfcallee);
            if (!GenericGraphTraits<ICFGGraph>::containsNode(icfg, svfInst))
                continue;
            CxtStmt newCts(newCxt, svfInst);
            markCxtStmtFlag(newCts, cts);
        }
    }
    handleIntra(icfg, cg, cts);
}
 
template<class ICFGGraph, class CGGraph>
void LockAnalysis::handleCall(ICFGGraph icfg, CGGraph cg, const CxtStmt& cts)
{
 
    const CallStrCxt& curCxt = cts.getContext();
    const CallICFGNode* call = SVFUtil::dyn_cast<CallICFGNode>(cts.getStmt());
    if (getTCG()->hasCallGraphEdge(call))
    {
        for (CallGraph::CallGraphEdgeSet::const_iterator cgIt = getTCG()->getCallEdgeBegin(call), ecgIt = getTCG()->getCallEdgeEnd(call);
                cgIt != ecgIt; ++cgIt)
        {
            const FunObjVar* svfcallee = (*cgIt)->getDstNode()->getFunction();
            if (SVFUtil::isExtCall(svfcallee))
                continue;
            CallStrCxt newCxt = curCxt;
            pushCxt(newCxt, call, svfcallee);
            const ICFGNode* svfInst = GenericGraphTraits<ICFGGraph>::getFunEntry(icfg, svfcallee);
            if (!GenericGraphTraits<ICFGGraph>::containsNode(icfg, svfInst))
                continue;
            CxtStmt newCts(newCxt, svfInst);
            markCxtStmtFlag(newCts, cts);
 
            // Return-flow rendezvous (see MHP::handleCall): forward an already
            // computed callee-exit lockset to this callsite's return site.
            if (svfcallee->hasBasicBlock())
            {
                const ICFGNode* exitInst = svfcallee->getExitBB()->back();
                CxtStmt exitCts(newCxt, exitInst);
                if (GenericGraphTraits<ICFGGraph>::containsNode(icfg, exitInst) && hasCxtLockfromCxtStmt(exitCts))
                {
                    const ICFGNode* retNode = call->getRetICFGNode();
                    if (GenericGraphTraits<ICFGGraph>::containsNode(icfg, retNode))
                    {
                        CxtStmt retCts(curCxt, retNode);
                        markCxtStmtFlag(retCts, exitCts);
                    }
                }
            }
        }
    }
}
 
template<class ICFGGraph, class CGGraph>
void LockAnalysis::handleRet(ICFGGraph icfg, CGGraph cg, const CxtStmt& cts)
{
 
    const ICFGNode* curInst = cts.getStmt();
    const CallStrCxt& curCxt = cts.getContext();
    const FunObjVar* svffun = curInst->getFun();
    CallGraphNode* curFunNode = getTCG()->getCallGraphNode(svffun);
 
    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 = curCxt;
            const ICFGNode* inst = *cit;
            if (matchCxt(newCxt, SVFUtil::cast<CallICFGNode>(inst), curFunNode->getFunction()))
            {
                std::vector<const ICFGNode*> succ;
                GenericGraphTraits<ICFGGraph>::getSuccNodes(icfg, curInst, succ);
                for (const ICFGNode* dst : succ)
                {
                    if(dst->getFun() == inst->getFun())
                    {
                        // Iterate over callSite's call string context and use as the successor's context
                        if (!hasCxtStmtFromInst(*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, dst);
                                markCxtStmtFlag(newCts, cts);
                            }
                        }
                    }
                }
            }
        }
        for (CallGraphEdge::CallInstSet::const_iterator cit = (edge)->indirectCallsBegin(), ecit = (edge)->indirectCallsEnd();
                cit != ecit; ++cit)
        {
            CallStrCxt newCxt = curCxt;
            const ICFGNode* inst = *cit;
            if (matchCxt(newCxt, SVFUtil::cast<CallICFGNode>(inst), curFunNode->getFunction()))
            {
                std::vector<const ICFGNode*> succ;
                GenericGraphTraits<ICFGGraph>::getSuccNodes(icfg, curInst, succ);
                for (const ICFGNode* dst : succ)
                {
                    if(dst->getFun() == inst->getFun())
                    {
                        // Iterate over callSite's call string context and use as the successor's context
                        if (!hasCxtStmtFromInst(*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, dst);
                                markCxtStmtFlag(newCts, cts);
                            }
                        }
                    }
                }
            }
        }
    }
}
 
template<class ICFGGraph, class CGGraph>
void LockAnalysis::handleIntra(ICFGGraph icfg, CGGraph cg, const CxtStmt& cts)
{
 
    const ICFGNode* curInst = cts.getStmt();
    const CallStrCxt& curCxt = cts.getContext();
 
    std::vector<const ICFGNode*> succ;
    GenericGraphTraits<ICFGGraph>::getSuccNodes(icfg, curInst, succ);
    for (const ICFGNode* dst : succ)
    {
        if(dst->getFun() == curInst->getFun())
        {
            CxtStmt newCts(curCxt, dst);
            markCxtStmtFlag(newCts, cts);
        }
    }
}
 
void LockAnalysis::pushCxt(CallStrCxt& cxt, const CallICFGNode* call, const FunObjVar* callee)
{
    tct->pushCxt(cxt,call,callee);
}
 
bool LockAnalysis::matchCxt(CallStrCxt& cxt, const CallICFGNode* call, const FunObjVar* callee)
{
    const FunObjVar* svfcaller = call->getFun();
    CallSiteID csId = getTCG()->getCallSiteID(call, callee);
 
//    /// handle calling context for candidate functions only
//    if (isLockCandidateFun(caller) == false)
//        return true;
 
    if (cxt.empty())
        return true;
 
    if (tct->inSameCallGraphSCC(getTCG()->getCallGraphNode(svfcaller), getTCG()->getCallGraphNode(callee)) == false)
    {
        if (cxt.back() == csId)
            cxt.pop_back();
        else
            return false;
        DBOUT(DMTA, tct->dumpCxt(cxt));
    }
    return true;
}
 
bool LockAnalysis::isContextSuffix(const CallStrCxt& lhs, const CallStrCxt& call)
{
    return tct->isContextSuffix(lhs,call);
}
 
 
bool LockAnalysis::isProtectedByCommonLock(const ICFGNode *i1, const ICFGNode *i2)
{
    numOfTotalQueries++;
    bool commonlock = false;
    DOTIMESTAT(double queryStart = PTAStat::getClk(true));
    if (isInsideIntraLock(i1) && isInsideIntraLock(i2))
        commonlock = isProtectedByCommonCILock(i1,i2) ;
    else
        commonlock = isProtectedByCommonCxtLock(i1,i2);
    DOTIMESTAT(double queryEnd = PTAStat::getClk(true));
    DOTIMESTAT(lockQueriesTime += (queryEnd - queryStart) / TIMEINTERVAL);
    return commonlock;
}
 
bool LockAnalysis::isProtectedByCommonCILock(const ICFGNode *i1, const ICFGNode *i2)
{
 
    if(!isInsideCondIntraLock(i1) && !isInsideCondIntraLock(i2))
    {
        const InstSet& lockset1 = getIntraLockSet(i1);
        const InstSet& lockset2 = getIntraLockSet(i2);
        for (InstSet::const_iterator cil1 = lockset1.begin(), ecil1 = lockset1.end(); cil1!=ecil1; ++cil1)
        {
            for (InstSet::const_iterator cil2=lockset2.begin(), ecil2=lockset2.end(); cil2!=ecil2; ++cil2)
            {
                if (isAliasedLocks(*cil1, *cil2))
                    return true;
            }
        }
    }
    return false;
}
 
bool LockAnalysis::isProtectedByCommonCxtLock(const CxtStmt& cxtStmt1, const CxtStmt& cxtStmt2)
{
    if(!hasCxtLockfromCxtStmt(cxtStmt1) || !hasCxtLockfromCxtStmt(cxtStmt2))
        return true;
    const CxtLockSet& lockset1 = getCxtLockfromCxtStmt(cxtStmt1);
    const CxtLockSet& lockset2 = getCxtLockfromCxtStmt(cxtStmt2);
    return alias(lockset1,lockset2);
}
 
bool LockAnalysis::isProtectedByCommonCxtLock(const ICFGNode *i1, const ICFGNode *i2)
{
    if(!hasCxtStmtFromInst(i1) || !hasCxtStmtFromInst(i2))
        return false;
    const CxtStmtSet& ctsset1 = getCxtStmtsFromInst(i1);
    const CxtStmtSet& ctsset2 = getCxtStmtsFromInst(i2);
    for (CxtStmtSet::const_iterator cts1 = ctsset1.begin(), ects1 = ctsset1.end(); cts1 != ects1; cts1++)
    {
        const CxtStmt& cxtStmt1 = *cts1;
        for (CxtStmtSet::const_iterator cts2 = ctsset2.begin(), ects2 = ctsset2.end(); cts2 != ects2; cts2++)
        {
            const CxtStmt& cxtStmt2 = *cts2;
            if(cxtStmt1==cxtStmt2)
            {
                // i1==i2 under the same context: a self-race between two dynamic
                // instances of one statement (e.g. a thread forked in a loop).
                // This is the ONLY pair the loop produces for such a query, so
                // skipping it would fall through to the vacuous "protected" return
                // below and drop a real race. The two instances are mutually
                // excluded only if this context actually holds a (non-empty) lock.
                if(!hasCxtLockfromCxtStmt(cxtStmt1) || getCxtLockfromCxtStmt(cxtStmt1).empty())
                    return false;
                continue;
            }
            if(isProtectedByCommonCxtLock(cxtStmt1,cxtStmt2)==false)
                return false;
        }
    }
    return true;
}
 
 
bool LockAnalysis::isInSameSpan(const ICFGNode *i1, const ICFGNode *i2)
{
    DOTIMESTAT(double queryStart = PTAStat::getClk(true));
 
    bool sameSpan = false;
    if (isInsideIntraLock(i1) && isInsideIntraLock(i2))
        sameSpan = isInSameCISpan(i1, i2);
    else
        sameSpan = isInSameCSSpan(i1, i2);
 
    DOTIMESTAT(double queryEnd = PTAStat::getClk(true));
    DOTIMESTAT(lockQueriesTime += (queryEnd - queryStart) / TIMEINTERVAL);
    return sameSpan;
}
 
bool LockAnalysis::isInSameCISpan(const ICFGNode *i1, const ICFGNode *i2) const
{
    if(!isInsideCondIntraLock(i1) && !isInsideCondIntraLock(i2))
    {
        const InstSet& lockset1 = getIntraLockSet(i1);
        const InstSet& lockset2 = getIntraLockSet(i2);
        for (InstSet::const_iterator cil1 = lockset1.begin(), ecil1 = lockset1.end(); cil1!=ecil1; ++cil1)
        {
            for (InstSet::const_iterator cil2=lockset2.begin(), ecil2=lockset2.end(); cil2!=ecil2; ++cil2)
            {
                if (*cil1==*cil2)
                    return true;
            }
        }
    }
    return false;
}
 
bool LockAnalysis::isInSameCSSpan(const CxtStmt& cxtStmt1, const CxtStmt& cxtStmt2) const
{
    if(!hasCxtLockfromCxtStmt(cxtStmt1) || !hasCxtLockfromCxtStmt(cxtStmt2))
        return true;
    const CxtLockSet& lockset1 = getCxtLockfromCxtStmt(cxtStmt1);
    const CxtLockSet& lockset2 = getCxtLockfromCxtStmt(cxtStmt2);
    return intersects(lockset1,lockset2);
}
bool LockAnalysis::isInSameCSSpan(const ICFGNode *I1, const ICFGNode *I2) const
{
    if(!hasCxtStmtFromInst(I1) || !hasCxtStmtFromInst(I2))
        return false;
    const CxtStmtSet& ctsset1 = getCxtStmtsFromInst(I1);
    const CxtStmtSet& ctsset2 = getCxtStmtsFromInst(I2);
 
    for (CxtStmtSet::const_iterator cts1 = ctsset1.begin(), ects1 = ctsset1.end(); cts1 != ects1; cts1++)
    {
        const CxtStmt& cxtStmt1 = *cts1;
        for (CxtStmtSet::const_iterator cts2 = ctsset2.begin(), ects2 = ctsset2.end(); cts2 != ects2; cts2++)
        {
            const CxtStmt& cxtStmt2 = *cts2;
            if(cxtStmt1==cxtStmt2) continue;
            if(isInSameCSSpan(cxtStmt1,cxtStmt2)==false)
                return false;
        }
    }
    return true;
}
 
// The two graphs the lock analysis runs on; the algorithm above is written once
// and instantiated for both (all internal templates instantiate transitively).
template void LockAnalysis::analyze<ICFG*, CallGraph*>(ICFG*, CallGraph*);
template void LockAnalysis::analyze<const SlicedICFGView*, const SlicedThreadCallGraphView*>(const SlicedICFGView*, const SlicedThreadCallGraphView*);