MTASVFGBuilder.cpp

Go to the documentation of this file.

//===- MTASVFGBuilder.cpp -- Thread-aware SVFG builder for FSAM ---------===//
//
//                     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/>.
//
//===----------------------------------------------------------------------===//
 
/*
 * MTASVFGBuilder.cpp
 *
 *      Author: Jiawei Yang
 *
 * Implements the FSAM thread-aware value-flow construction (CGO'16, §3.3).
 */
 
#include "MTA/MTASVFGBuilder.h"
#include "Graphs/SlicedGraphs.h"
#include "MSSA/MemSSA.h"
#include "MSSA/MemPartition.h"
#include "MemoryModel/PointerAnalysisImpl.h"
#include "Util/SVFUtil.h"
#include "Util/Options.h"
#include "Graphs/ThreadCallGraph.h"
 
using namespace SVF;
using namespace SVFUtil;
 
u32_t MTASVFGBuilder::numOfNewSVFGEdges = 0;
 
namespace
{
template <class BaseMRG>
class ThreadMRG : public BaseMRG
{
public:
    ThreadMRG(BVDataPTAImpl* p, bool ptrOnly) : BaseMRG(p, ptrOnly) {}
 
protected:
    void refineCallsiteModRef(NodeBS& mod, NodeBS& ref,
                              const CallICFGNode* cs, const FunObjVar* callee) override
    {
        if (const ThreadCallGraph* tcg = SVFUtil::dyn_cast<ThreadCallGraph>(this->getCallGraph()))
            if (tcg->hasThreadForkEdge(cs))
            {
                ref = this->getRefSideEffectOfFunction(callee);
                // A fork is a call WITHOUT a return: the spawnee's writes must not
                // be applied as a mod here (which would kill the spawner's own
                // value flow past the fork). They reach later reads via the
                // thread-aware interference edges instead.
                mod.clear();
            }
    }
 
    void propagateAdditionalModRef(CallGraphNode* callGraphNode,
                                   MRGenerator::WorkList& worklist) override
    {
        ThreadCallGraph* tcg = SVFUtil::dyn_cast<ThreadCallGraph>(this->getCallGraph());
        if (tcg == nullptr)
            return;
        ThreadCallGraph::InstSet joinsites;
        tcg->getJoinSites(callGraphNode, joinsites);
        if (joinsites.empty())
            return;
        const NodeBS& spawneeMod = this->getModSideEffectOfFunction(callGraphNode->getFunction());
        for (const CallICFGNode* cs : joinsites)
            // A join exposes the joined thread's writes at the join point. Those
            // writes are not necessarily reachable from pthread_join's handle
            // argument, so use the MOD set as computed for the start routine.
            if (this->addUnfilteredModSideEffectOfCallSite(cs, spawneeMod))
                worklist.push(this->getCallGraph()->getCallGraphNode(cs->getCaller())->getId());
    }
};
} // anonymous namespace
 
// Build a thread-aware MRGenerator wrapping the configured partition strategy, so
// the MemSSA mod-ref generation carries the FSAM fork/join side effects.
std::unique_ptr<MRGenerator> MTASVFGBuilder::createMRGenerator(BVDataPTAImpl* pta, bool ptrOnlyMSSA)
{
    switch (Options::MemPar())
    {
    case MemSSA::MemPartition::Distinct:
        return std::make_unique<ThreadMRG<DistinctMRG>>(pta, ptrOnlyMSSA);
    case MemSSA::MemPartition::IntraDisjoint:
        return std::make_unique<ThreadMRG<IntraDisjointMRG>>(pta, ptrOnlyMSSA);
    case MemSSA::MemPartition::InterDisjoint:
        return std::make_unique<ThreadMRG<InterDisjointMRG>>(pta, ptrOnlyMSSA);
    default:
        assert(false && "unrecognised memory partition strategy");
        return nullptr;
    }
}
 
void MTASVFGBuilder::buildSVFG()
{
    svfg->buildSVFG();
    connectThreadJoinEdges();
    connectMHPEdges(svfg->getMSSA()->getPTA());
}
 
void MTASVFGBuilder::addJoinRetEdge(const FormalOUTSVFGNode* formalOut,
                                    const ActualOUTSVFGNode* actualOut, CallSiteID csId)
{
    NodeBS cpts = formalOut->getPointsTo();
    const NodeBS& dpts = actualOut->getPointsTo();
    if (!cpts.intersects(dpts))
        return;
    cpts &= dpts;
 
    SVFGNode* src = svfg->getSVFGNode(formalOut->getId());
    SVFGNode* dst = svfg->getSVFGNode(actualOut->getId());
    if (SVFGEdge* edge = svfg->hasInterVFGEdge(src, dst, SVFGEdge::RetIndVF, csId))
    {
        SVFUtil::cast<RetIndSVFGEdge>(edge)->addPointsTo(cpts);
    }
    else
    {
        RetIndSVFGEdge* retEdge = new RetIndSVFGEdge(src, dst, csId);
        retEdge->addPointsTo(cpts);
        svfg->addSVFGEdge(retEdge);
    }
}
 
void MTASVFGBuilder::connectThreadJoinEdges()
{
    ThreadCallGraph* tcg =
        SVFUtil::dyn_cast<ThreadCallGraph>(svfg->getMSSA()->getPTA()->getCallGraph());
    if (tcg == nullptr)
        return;
 
    MemSSA* mssa = svfg->getMSSA();
    for (SVFG::const_iterator it = svfg->begin(), eit = svfg->end(); it != eit; ++it)
    {
        const FormalOUTSVFGNode* formalOut = SVFUtil::dyn_cast<FormalOUTSVFGNode>(it->second);
        if (formalOut == nullptr)
            continue;
 
        ThreadCallGraph::InstSet joinsites;
        tcg->getJoinSites(tcg->getCallGraphNode(formalOut->getFun()), joinsites);
        for (const CallICFGNode* cs : joinsites)
        {
            if (!mssa->hasCHI(cs))
                continue;
            SVFG::ActualOUTSVFGNodeSet& actualOuts = svfg->getActualOUTSVFGNodes(cs);
            for (NodeID aoId : actualOuts)
            {
                const ActualOUTSVFGNode* actualOut =
                    SVFUtil::cast<ActualOUTSVFGNode>(svfg->getSVFGNode(aoId));
                addJoinRetEdge(formalOut, actualOut, svfg->getCallSiteID(cs, formalOut->getFun()));
            }
        }
    }
}
 
void MTASVFGBuilder::collectLoadStoreSVFGNodes()
{
    for (SVFG::const_iterator it = svfg->begin(), eit = svfg->end(); it != eit; ++it)
    {
        const SVFGNode* snode = it->second;
        const bool isLoad = SVFUtil::isa<LoadSVFGNode>(snode);
        if (!isLoad && !SVFUtil::isa<StoreSVFGNode>(snode))
            continue;
        const StmtSVFGNode* node = SVFUtil::cast<StmtSVFGNode>(snode);
        const ICFGNode* icfg = node->getICFGNode();
        if (icfg == nullptr)
            continue;
        // Main-solve slice restriction: an interference edge touching a sliced-out
        // node is inert in the gated FSAM solve, so skip building it here.
        if (icfgSlice != nullptr && !icfgSlice->isKeptNode(icfg))
            continue;
        if (isLoad)
            ldnodeSet.insert(node);
        else
            stnodeSet.insert(node);
    }
}
 
SVFGEdge* MTASVFGBuilder::addTDEdge(NodeID srcId, NodeID dstId, const PointsTo& pts)
{
    SVFGNode* srcNode = svfg->getSVFGNode(srcId);
    SVFGNode* dstNode = svfg->getSVFGNode(dstId);
 
    if (SVFGEdge* edge = svfg->hasThreadVFGEdge(srcNode, dstNode, SVFGEdge::TheadMHPIndirectVF))
    {
        assert(SVFUtil::isa<IndirectSVFGEdge>(edge) && "should be an indirect value-flow edge!");
        return (SVFUtil::cast<IndirectSVFGEdge>(edge)->addPointsTo(pts.toNodeBS()) ? edge : nullptr);
    }
    else
    {
        numOfNewSVFGEdges++;
        ThreadMHPIndSVFGEdge* indirectEdge = new ThreadMHPIndSVFGEdge(srcNode, dstNode);
        indirectEdge->addPointsTo(pts.toNodeBS());
        return (svfg->addSVFGEdge(indirectEdge) ? indirectEdge : nullptr);
    }
}
 
MTASVFGBuilder::SVFGNodeIDSet MTASVFGBuilder::getPrevNodes(const StmtSVFGNode* n)
{
    if (prevset.find(n) != prevset.end())
        return prevset[n];
 
    SVFGNodeIDSet prev;
    Set<const SVFGNode*> worklist;
    Set<const SVFGNode*> visited;
 
    for (SVFGEdge::SVFGEdgeSetTy::iterator iter = n->InEdgeBegin(); iter != n->InEdgeEnd(); ++iter)
    {
        SVFGEdge* edge = *iter;
        if (edge->isIndirectVFGEdge())
            worklist.insert(edge->getSrcNode());
    }
 
    while (!worklist.empty())
    {
        const SVFGNode* node = *worklist.begin();
        worklist.erase(worklist.begin());
        visited.insert(node);
        if (SVFUtil::isa<StoreSVFGNode>(node))
            prev.set(node->getId());
        else
        {
            for (SVFGEdge::SVFGEdgeSetTy::iterator iter = node->InEdgeBegin(); iter != node->InEdgeEnd(); ++iter)
            {
                SVFGEdge* edge = *iter;
                if (edge->isIndirectVFGEdge() && visited.find(edge->getSrcNode()) == visited.end())
                    worklist.insert(edge->getSrcNode());
            }
        }
    }
    prevset[n] = prev;
    return prev;
}
 
MTASVFGBuilder::SVFGNodeIDSet MTASVFGBuilder::getSuccNodes(const StmtSVFGNode* n)
{
    if (succset.find(n) != succset.end())
        return succset[n];
 
    SVFGNodeIDSet succ;
    Set<const SVFGNode*> worklist;
    Set<const SVFGNode*> visited;
 
    for (SVFGEdge::SVFGEdgeSetTy::iterator iter = n->OutEdgeBegin(); iter != n->OutEdgeEnd(); ++iter)
    {
        SVFGEdge* edge = *iter;
        if (edge->isIndirectVFGEdge())
            worklist.insert(edge->getDstNode());
    }
 
    while (!worklist.empty())
    {
        const SVFGNode* node = *worklist.begin();
        worklist.erase(worklist.begin());
        visited.insert(node);
        if (SVFUtil::isa<StoreSVFGNode, LoadSVFGNode>(node))
            succ.set(node->getId());
        else
        {
            for (SVFGEdge::SVFGEdgeSetTy::iterator iter = node->OutEdgeBegin(); iter != node->OutEdgeEnd(); ++iter)
            {
                SVFGEdge* edge = *iter;
                if (edge->isIndirectVFGEdge() && visited.find(edge->getDstNode()) == visited.end())
                    worklist.insert(edge->getDstNode());
            }
        }
    }
    succset[n] = succ;
    return succ;
}
 
bool MTASVFGBuilder::isHeadOfSpan(const StmtSVFGNode* n)
{
    if (headmap.find(n) != headmap.end())
        return headmap[n];
 
    SVFGNodeIDSet prev = getPrevNodes(n);
    for (NodeID id : prev)
    {
        const StmtSVFGNode* prevNode = SVFUtil::dyn_cast<StmtSVFGNode>(svfg->getSVFGNode(id));
        if (prevNode && lockana->isInSameSpan(prevNode->getICFGNode(), n->getICFGNode()))
        {
            headmap[n] = false;
            return false;
        }
    }
    headmap[n] = true;
    return true;
}
 
bool MTASVFGBuilder::isTailOfSpan(const StmtSVFGNode* n)
{
    assert(SVFUtil::isa<StoreSVFGNode>(n) && "tail test only for store nodes");
 
    if (tailmap.find(n) != tailmap.end())
        return tailmap[n];
 
    SVFGNodeIDSet succ = getSuccNodes(n);
    for (NodeID id : succ)
    {
        const SVFGNode* sn = svfg->getSVFGNode(id);
        if (SVFUtil::isa<LoadSVFGNode>(sn))
            continue;
        const StmtSVFGNode* succNode = SVFUtil::dyn_cast<StmtSVFGNode>(sn);
        if (succNode && lockana->isInSameSpan(succNode->getICFGNode(), n->getICFGNode()))
        {
            tailmap[n] = false;
            return false;
        }
    }
    tailmap[n] = true;
    return true;
}
 
void MTASVFGBuilder::recordThreadVFSource(const StmtSVFGNode* s, const StmtSVFGNode* sp, bool commonLock)
{
    // Per-edge Query set. The endpoints are NOT duplicated into the value --
    // they are recoverable from the map key -- so the value holds only the
    // additional in-span witnesses below (empty for the common lock-free case).
    std::set<const ICFGNode*>& query = threadVFQueryMap[ {s, sp}];
 
    if (!commonLock)
        return;
 
    // Succ_spl(s) = { x in s's span | x is a store, s --o--> x } (tail witnesses).
    for (NodeID id : getSuccNodes(s))
    {
        const SVFGNode* sn = svfg->getSVFGNode(id);
        if (!SVFUtil::isa<StoreSVFGNode>(sn))
            continue;
        const StmtSVFGNode* succNode = SVFUtil::cast<StmtSVFGNode>(sn);
        if (lockana->isInSameSpan(succNode->getICFGNode(), s->getICFGNode()))
            query.insert(succNode->getICFGNode());
    }
 
    // Pred_spl'(sp) = { x in sp's span | x --o--> sp } (head witnesses).
    for (NodeID id : getPrevNodes(sp))
    {
        const StmtSVFGNode* prevNode = SVFUtil::dyn_cast<StmtSVFGNode>(svfg->getSVFGNode(id));
        if (prevNode && lockana->isInSameSpan(prevNode->getICFGNode(), sp->getICFGNode()))
            query.insert(prevNode->getICFGNode());
    }
}
 
void MTASVFGBuilder::handleStoreLoad(const StmtSVFGNode* n1, const StmtSVFGNode* n2, PointerAnalysis* pta)
{
    const ICFGNode* i1 = n1->getICFGNode();
    const ICFGNode* i2 = n2->getICFGNode();
 
    if (!mhp->mayHappenInParallel(i1, i2))
        return;
 
    // No alias() re-check: the bucketed candidate generator only pairs accesses
    // whose raw points-to sets share an object, so the intersection below is
    // non-empty by construction and alias() could never answer NoAlias here.
    PointsTo pts = pta->getPts(n1->getDstNodeID());
    pts &= pta->getPts(n2->getSrcNodeID());
 
    // [THREAD-VF] source extraction runs for every candidate pair (both the
    // pairs that survive and the ones the lock test prunes), so the sliced ILA
    // can re-derive whether the edge holds.
    bool commonLock = lockana->isProtectedByCommonLock(i1, i2);
    if (recordThreadVF)
        recordThreadVFSource(n1, n2, commonLock);
 
    if (commonLock)
    {
        if (isTailOfSpan(n1) && isHeadOfSpan(n2))
            addTDEdge(n1->getId(), n2->getId(), pts);
    }
    else
    {
        addTDEdge(n1->getId(), n2->getId(), pts);
    }
}
 
void MTASVFGBuilder::handleStoreStore(const StmtSVFGNode* n1, const StmtSVFGNode* n2, PointerAnalysis* pta)
{
    const ICFGNode* i1 = n1->getICFGNode();
    const ICFGNode* i2 = n2->getICFGNode();
 
    if (!mhp->mayHappenInParallel(i1, i2))
        return;
 
    // No alias() re-check: see handleStoreLoad -- bucketing already guarantees a
    // shared raw object.
    PointsTo pts = pta->getPts(n1->getDstNodeID());
    pts &= pta->getPts(n2->getDstNodeID());
 
    // Both directions are candidate thread-aware edges; extract sources for each.
    bool commonLock = lockana->isProtectedByCommonLock(i1, i2);
    if (recordThreadVF)
    {
        recordThreadVFSource(n1, n2, commonLock);
        recordThreadVFSource(n2, n1, commonLock);
    }
 
    if (commonLock)
    {
        if (isTailOfSpan(n1) && isHeadOfSpan(n2))
            addTDEdge(n1->getId(), n2->getId(), pts);
        if (isTailOfSpan(n2) && isHeadOfSpan(n1))
            addTDEdge(n2->getId(), n1->getId(), pts);
    }
    else
    {
        addTDEdge(n1->getId(), n2->getId(), pts);
        addTDEdge(n2->getId(), n1->getId(), pts);
    }
}
 
void MTASVFGBuilder::connectMHPEdges(PointerAnalysis* pta)
{
    collectLoadStoreSVFGNodes();
 
    // Inverted access index (object -> access-node bitset): unioning the
    // bitsets per store visits each may-alias pair exactly once, no dedup tables.
    Map<NodeID, SVFGNodeIDSet> objToStoreIds;
    Map<NodeID, SVFGNodeIDSet> objToLoadIds;
    for (const StmtSVFGNode* store : stnodeSet)
        for (NodeID obj : pta->getPts(store->getDstNodeID()))
            objToStoreIds[obj].set(store->getId());
    for (const StmtSVFGNode* load : ldnodeSet)
        for (NodeID obj : pta->getPts(load->getSrcNodeID()))
            objToLoadIds[obj].set(load->getId());
 
    for (const StmtSVFGNode* store : stnodeSet)
    {
        SVFGNodeIDSet candLoads, candStores;
        for (NodeID obj : pta->getPts(store->getDstNodeID()))
        {
            candStores |= objToStoreIds[obj];
            Map<NodeID, SVFGNodeIDSet>::const_iterator lIt = objToLoadIds.find(obj);
            if (lIt != objToLoadIds.end())
                candLoads |= lIt->second;
        }
 
        for (NodeID loadId : candLoads)
            handleStoreLoad(store, SVFUtil::cast<StmtSVFGNode>(svfg->getSVFGNode(loadId)), pta);
 
        // Visit each unordered store pair once: only partners with a larger id.
        const NodeID storeId = store->getId();
        for (NodeID otherId : candStores)
        {
            if (otherId <= storeId)
                continue;
            handleStoreStore(store, SVFUtil::cast<StmtSVFGNode>(svfg->getSVFGNode(otherId)), pta);
        }
    }
}