SVF::MTASlicerBase Class Reference

#include <MTASlicer.h>

Inheritance diagram for SVF::MTASlicerBase:

Public Member Functions
	MTASlicerBase (SVFIR *svfir, AndersenBase *pta, MHP *mhp, LockAnalysis *lockAnalysis, SVFG *svfg=nullptr)

Protected Member Functions
OrderedSet< const VFGNode * >	computeDataDependenceSVFGNodes (const OrderedSet< const SVFStmt * > &seeds, SVFG *svfg)
OrderedSet< const ICFGNode * >	svfgNodesToICFGNodes (const OrderedSet< const VFGNode * > &nodes, const OrderedSet< const SVFStmt * > &seeds)
	Project the retained VFG nodes (plus the seeds) onto their ICFG nodes.
OrderedSet< const CallICFGNode * >	getDependentThreadCreate (const ICFGNode *node)
OrderedSet< const TCTNode * >	getTCTNodeSetFromNode (const ICFGNode *node)
OrderedSet< const ICFGNode * >	getLockSet (const ICFGNode *node)
OrderedSet< const CallICFGNode * >	collectPthreadStatements (const OrderedSet< const ICFGNode * > &sourceNodes)
OrderedSet< const CallICFGNode * >	collectMutexStatements (const OrderedSet< const ICFGNode * > &sourceNodes)
std::pair< OrderedSet< const CallICFGNode * >, OrderedSet< const CallICFGNode * > >	collectCommonThreadStatements (const OrderedSet< const ICFGNode * > &sourceNodes)
void	addSynchronizationDependencies (const OrderedSet< const CallICFGNode * > &pthreadCallNodes, const OrderedSet< const CallICFGNode * > &mutexCallNodes, OrderedSet< const ICFGNode * > &retainedNodes)
OrderedSet< const ICFGNode * >	expandCallDependence (const OrderedSet< const ICFGNode * > &nodes)

Static Protected Member Functions
static void	enqueueSVFGNode (const SVFGNode *node, OrderedSet< const SVFGNode * > &visited, std::deque< const SVFGNode * > &worklist)

Protected Attributes
SVFIR *	svfir
AndersenBase *	pta
MHP *	mhp
LockAnalysis *	lockAnalysis
CallGraph *	callGraph
SVFG *	svfg
	thread-aware VFG_pre (PTA/Single slicers; null for MTA)

Detailed Description

MTASlicerBase - Base class for program slicing.

Holds the shared helper methods and data members used by both concrete slicers (the ILA and FSPTA stages of MultiStageSlicer).

Definition at line 121 of file MTASlicer.h.

Constructor & Destructor Documentation

MTASlicerBase()

SVF::MTASlicerBase::MTASlicerBase	(	SVFIR *	svfir,
		AndersenBase *	pta,
		MHP *	mhp,
		LockAnalysis *	lockAnalysis,
		SVFG *	svfg = nullptr
	)

Definition at line 300 of file MTASlicer.cpp.

    : svfir(svfir), pta(pta), mhp(mhp), lockAnalysis(lockAnalysis), svfg(svfg)
{
    callGraph = pta->getCallGraph();
}

Member Function Documentation

addSynchronizationDependencies()

void SVF::MTASlicerBase::addSynchronizationDependencies ( const OrderedSet< const CallICFGNode * > &  pthreadCallNodes, const OrderedSet< const CallICFGNode * > &  mutexCallNodes, OrderedSet< const ICFGNode * > &  retainedNodes  )

protected

Add synchronization primitives and the control-flow anchors required by the sliced MHP/lock analyses.

Definition at line 625 of file MTASlicer.cpp.

{
    for (const CallICFGNode* callNode : pthreadCallNodes)
    {
        sliceResult.insert(callNode);
        if (callNode->getRetICFGNode() != nullptr)
            sliceResult.insert(callNode->getRetICFGNode());
    }
    for (const CallICFGNode* callNode : mutexCallNodes)
    {
        sliceResult.insert(callNode);
        if (callNode->getRetICFGNode() != nullptr)
            sliceResult.insert(callNode->getRetICFGNode());
    }
 
    for (const CallICFGNode* mutexCallNode : mutexCallNodes)
    {
        const FunObjVar* fun = mutexCallNode->getFun();
        if (fun == nullptr)
            continue;
        if (const SVFBasicBlock* entry = fun->getEntryBlock())
        {
            sliceResult.insert(entry->front());
            sliceResult.insert(entry->back());
        }
        if (const SVFBasicBlock* exit = fun->getExitBB())
            sliceResult.insert(exit->back());
    }
 
    ThreadAPI* threadAPI = mhp->getThreadCallGraph()->getThreadAPI();
    for (const CallICFGNode* callNode : pthreadCallNodes)
    {
        if (!threadAPI->isTDJoin(callNode) || callNode->getBB() == nullptr)
            continue;
        std::vector<const SVFBasicBlock*> exitBlocks;
        callNode->getFun()->getExitBlocksOfLoop(callNode->getBB(), exitBlocks);
        for (const SVFBasicBlock* exitBlock : exitBlocks)
            if (!exitBlock->getICFGNodeList().empty())
                sliceResult.insert(exitBlock->front());
    }
}

collectCommonThreadStatements()

std::pair< OrderedSet< const CallICFGNode * >, OrderedSet< const CallICFGNode * > > SVF::MTASlicerBase::collectCommonThreadStatements ( const OrderedSet< const ICFGNode * > &  sourceNodes )

protected

Collect common pthread and mutex statements (shared by PTA and MTA slicing).

Parameters

sourceNodes

Complete ILA source set ([INIT] union [THREAD-VF])

Returns

Pair of (pthreadCallNodes, mutexCallNodes)

Definition at line 595 of file MTASlicer.cpp.

{
    // Step 1: Collect pthread-related statements, i.e., pthread_create and pthread_join
    OrderedSet<const CallICFGNode*> pthreadCallNodes =
        collectPthreadStatements(sourceNodes);
 
    // Step 2: Collect mutex-related statements
    OrderedSet<const CallICFGNode*> mutexCallNodes =
        collectMutexStatements(sourceNodes);
 
    return std::make_pair(pthreadCallNodes, mutexCallNodes);
}

collectMutexStatements()

OrderedSet< const CallICFGNode * > SVF::MTASlicerBase::collectMutexStatements ( const OrderedSet< const ICFGNode * > &  sourceNodes )

protected

Definition at line 534 of file MTASlicer.cpp.

{
    OrderedSet<const CallICFGNode*> mutexCallNodes;
 
    ThreadCallGraph* tcg = mhp->getThreadCallGraph();
    ThreadAPI* threadAPI = tcg->getThreadAPI();
 
    // Map mutex_lock nodes to their corresponding mutex_unlock nodes
    OrderedSet<const CallICFGNode*> mutexLockCallNodes;
 
    // First pass: collect all mutex_lock nodes from lock sets
    for (const ICFGNode* sourceNode : sourceNodes)
    {
        OrderedSet<const ICFGNode*> lockSet = getLockSet(sourceNode);
        for (const ICFGNode* lockNode : lockSet)
        {
            const CallICFGNode* lockCallNode =
                SVFUtil::dyn_cast<CallICFGNode>(lockNode);
            if (lockCallNode != nullptr &&
                    threadAPI->isTDAcquire(lockCallNode))
            {
                mutexCallNodes.insert(lockCallNode);
                mutexLockCallNodes.insert(lockCallNode);
            }
        }
    }
 
    // Second pass: find corresponding mutex_unlock nodes
    ICFG* icfg = svfir->getICFG();
    for (ICFG::iterator it = icfg->begin(), eit = icfg->end();
            it != eit; ++it)
    {
        const ICFGNode* node = it->second;
        const CallICFGNode* callNode = SVFUtil::dyn_cast<CallICFGNode>(node);
        if (callNode != nullptr && threadAPI->isTDRelease(callNode))
        {
            const SVFVar* unlockVar = threadAPI->getLockVal(callNode);
            if (unlockVar != nullptr)
            {
                for (const CallICFGNode* lockCallNode : mutexLockCallNodes)
                {
                    if (lockCallNode != nullptr)
                    {
                        const SVFVar* lockVar = threadAPI->getLockVal(lockCallNode);
                        if (lockVar != nullptr &&
                                pta->alias(unlockVar->getId(), lockVar->getId()))
                        {
                            mutexCallNodes.insert(callNode);
                        }
                    }
                }
            }
        }
    }
 
    return mutexCallNodes;
}

collectPthreadStatements()

OrderedSet< const CallICFGNode * > SVF::MTASlicerBase::collectPthreadStatements ( const OrderedSet< const ICFGNode * > &  sourceNodes )

protected

Definition at line 481 of file MTASlicer.cpp.

{
    OrderedSet<const CallICFGNode*> pthreadCallNodes;
 
    ThreadCallGraph* tcg = mhp->getThreadCallGraph();
    ThreadAPI* threadAPI = tcg->getThreadAPI();
 
    // Map pthread_create nodes to their corresponding pthread_join nodes
    OrderedSet<const CallICFGNode*> pthreadCreateNodes;
 
    // First pass: collect all pthread_create nodes
    for (const ICFGNode* sourceNode : sourceNodes)
    {
        OrderedSet<const CallICFGNode*> forkSites =
            getDependentThreadCreate(sourceNode);
        for (const CallICFGNode* forkCallNode : forkSites)
        {
            pthreadCallNodes.insert(forkCallNode);
            pthreadCreateNodes.insert(forkCallNode);
        }
    }
 
    // Second pass: find corresponding pthread_join nodes
    ICFG* icfg = svfir->getICFG();
    for (ICFG::iterator it = icfg->begin(), eit = icfg->end();
            it != eit; ++it)
    {
        const ICFGNode* node = it->second;
        const CallICFGNode* callNode = SVFUtil::dyn_cast<CallICFGNode>(node);
        if (callNode != nullptr && threadAPI->isTDJoin(callNode))
        {
            const SVFVar* joinThread = threadAPI->getJoinedThread(callNode);
            if (joinThread != nullptr)
            {
                for (const CallICFGNode* createCallNode : pthreadCreateNodes)
                {
                    const SVFVar* forkedThread = threadAPI->getForkedThread(createCallNode);
                    if (forkedThread != nullptr &&
                            threadAPI->isAliasedForkJoin(
                                pta, forkedThread, joinThread))
                    {
                        pthreadCallNodes.insert(callNode);
                    }
                }
            }
        }
    }
 
    return pthreadCallNodes;
}

computeDataDependenceSVFGNodes()

OrderedSet< const SVFGNode * > SVF::MTASlicerBase::computeDataDependenceSVFGNodes ( const OrderedSet< const SVFStmt * > &  seeds, SVFG *  svfg  )

protected

The SVFG-node granularity of the data-dependence slice above: the set of VFG nodes reachable backward from the seeds. ThreadVF(VFG'_pre) is exactly the thread-aware edges whose both endpoints lie in this set, so ILA slicing uses it to restrict the [THREAD-VF] sources to surviving edges.

Definition at line 405 of file MTASlicer.cpp.

{
 
    assert(svfg != nullptr && "data-dependence slice requires the thread-aware VFG_pre");
 
    OrderedSet<const SVFGNode*> visited;
    std::deque<const SVFGNode*> worklist;
 
    // Seed from the value-flow nodes of the given (e.g. race target) statements.
    // VFG_pre is a pointer-only SVFG, so a load/store of a NON-pointer value (the
    // usual case -- a race on an int/float field) has no statement node. For those
    // we must still preserve the points-to of the dereferenced address pointer, or
    // the sliced flow-sensitive solve sees an empty slice for it, computes empty
    // points-to, and drops the race (a soundness bug). So additionally seed from the
    // definition of each load/store's address pointer (always a pointer, hence
    // always in the pointer-only SVFG); its backward closure keeps the pointer's
    // def chain regardless of the value type.
    for (const SVFStmt* stmt : seeds)
    {
        if (svfg->hasStmtVFGNode(stmt))
            enqueueSVFGNode(svfg->getStmtVFGNode(stmt), visited, worklist);
 
        NodeID addrPtr = 0;
        if (const LoadStmt* load = SVFUtil::dyn_cast<LoadStmt>(stmt))
            addrPtr = load->getRHSVarID();
        else if (const StoreStmt* store = SVFUtil::dyn_cast<StoreStmt>(stmt))
            addrPtr = store->getLHSVarID();
        if (addrPtr != 0)
        {
            // getDefSVFGNode takes a ValVar (the address pointer is a top-level
            // value variable).
            const ValVar* ptrNode = SVFUtil::dyn_cast<ValVar>(svfir->getGNode(addrPtr));
            if (ptrNode != nullptr && svfg->hasDefSVFGNode(ptrNode))
                enqueueSVFGNode(svfg->getDefSVFGNode(ptrNode), visited, worklist);
        }
    }
 
    // Backward over every value-flow edge.
    while (!worklist.empty())
    {
        const SVFGNode* node = worklist.front();
        worklist.pop_front();
        for (const VFGEdge* edge : node->getInEdges())
            enqueueSVFGNode(edge->getSrcNode(), visited, worklist);
    }
 
    return visited;
}

enqueueSVFGNode()

void SVF::MTASlicerBase::enqueueSVFGNode ( const SVFGNode *  node, OrderedSet< const SVFGNode * > &  visited, std::deque< const SVFGNode * > &  worklist  )

staticprotected

Definition at line 455 of file MTASlicer.cpp.

{
    if (node != nullptr && visited.insert(node).second)
        worklist.push_back(node);
}

expandCallDependence()

OrderedSet< const ICFGNode * > SVF::MTASlicerBase::expandCallDependence ( const OrderedSet< const ICFGNode * > &  nodes )

protected

Call-dependence expansion (used by MultiStageSlicer): take the kept functions of the given nodes, close upward over the call graph (every transitive caller), then add each kept function's entry/exit nodes and the call/ret nodes of every call site targeting it.

Parameters

nodes

Current set of ICFG nodes

Returns

The input nodes plus the call/ret and entry/exit nodes above

Definition at line 671 of file MTASlicer.cpp.

{
 
    // Determine keptFunctions from the given nodes
    OrderedSet<const FunObjVar*> keptFunctions;
    for (const ICFGNode* node : nodes)
    {
        if (node != nullptr && node->getFun() != nullptr)
        {
            keptFunctions.insert(node->getFun());
        }
    }
 
    // Build ancestor closure (upward traversal in call graph)
    std::queue<const FunObjVar*> functionWorklist;
    for (const FunObjVar* fun : keptFunctions)
        functionWorklist.push(fun);
 
    Map<const FunObjVar*, const CallGraphNode*> functionToNode;
    for (auto it = callGraph->begin(), eit = callGraph->end();
            it != eit; ++it)
    {
        const CallGraphNode* node = it->second;
        if (node != nullptr && node->getFunction() != nullptr)
            functionToNode[node->getFunction()] = node;
    }
 
    OrderedSet<const FunObjVar*> visitedFunctions = keptFunctions;
    while (!functionWorklist.empty())
    {
        const FunObjVar* target = functionWorklist.front();
        functionWorklist.pop();
        const auto nodeIt = functionToNode.find(target);
        if (nodeIt == functionToNode.end())
            continue;
 
        const CallGraphNode* node = nodeIt->second;
        for (const CallGraphEdge* inEdge : node->getInEdges())
        {
            if (inEdge == nullptr)
                continue;
            const CallGraphNode* callerNode = inEdge->getSrcNode();
            if (callerNode != nullptr && callerNode->getFunction() != nullptr)
            {
                const FunObjVar* callerFun = callerNode->getFunction();
                if (visitedFunctions.find(callerFun) == visitedFunctions.end())
                {
                    keptFunctions.insert(callerFun);
                    visitedFunctions.insert(callerFun);
                    functionWorklist.push(callerFun);
                }
            }
        }
    }
 
    // For each keptFunction, add call/ret nodes and entry/exit nodes
    ICFG* icfg = svfir->getICFG();
    OrderedSet<const ICFGNode*> expandedNodes = nodes;
    for (const FunObjVar* fun : keptFunctions)
    {
        if (fun == nullptr)
            continue;
 
        // Add function entry/exit nodes
        if (fun->hasBasicBlock())
        {
            if (FunEntryICFGNode* entry = icfg->getFunEntryICFGNode(fun))
                expandedNodes.insert(entry);
            if (FunExitICFGNode* exit = icfg->getFunExitICFGNode(fun))
                expandedNodes.insert(exit);
        }
 
        // Find all call/ret nodes that call this function
        const auto funNodeIt = functionToNode.find(fun);
        if (funNodeIt != functionToNode.end())
        {
            const CallGraphNode* calleeNode = funNodeIt->second;
 
            // Traverse all edges that call this function
            for (const CallGraphEdge* inEdge : calleeNode->getInEdges())
            {
                if (inEdge == nullptr)
                    continue;
 
                const CallGraphEdge::CallInstSet& directCalls =
                    inEdge->getDirectCalls();
                const CallGraphEdge::CallInstSet& indirectCalls =
                    inEdge->getIndirectCalls();
 
                for (const CallICFGNode* callNode : directCalls)
                {
                    if (callNode != nullptr)
                    {
                        expandedNodes.insert(callNode);
                        const RetICFGNode* retNode = callNode->getRetICFGNode();
                        if (retNode != nullptr)
                            expandedNodes.insert(retNode);
                    }
                }
 
                for (const CallICFGNode* callNode : indirectCalls)
                {
                    if (callNode != nullptr)
                    {
                        expandedNodes.insert(callNode);
                        const RetICFGNode* retNode = callNode->getRetICFGNode();
                        if (retNode != nullptr)
                            expandedNodes.insert(retNode);
                    }
                }
            }
        }
    }
 
    return expandedNodes;
}

getDependentThreadCreate()

OrderedSet< const CallICFGNode * > SVF::MTASlicerBase::getDependentThreadCreate ( const ICFGNode *  node )

protected

Definition at line 375 of file MTASlicer.cpp.

{
    OrderedSet<const CallICFGNode*> forkSites;
    OrderedSet<const TCTNode*> tctNodeSet = getTCTNodeSetFromNode(node);
    ThreadAPI* threadAPI = mhp->getThreadCallGraph()->getThreadAPI();
 
    TCT* tct = mhp->getTCT();
    for (const TCTNode* tctNode : tctNodeSet)
    {
        NodeBS dependentThreads = tct->getAncestorThreads(tctNode->getId());
        dependentThreads.set(tctNode->getId());
        for (NodeID tid : dependentThreads)
        {
            const ICFGNode* forkSite =
                tct->getTCTNode(tid)->getCxtThread().getThread();
            const CallICFGNode* forkCall =
                SVFUtil::dyn_cast<CallICFGNode>(forkSite);
            if (forkCall != nullptr && threadAPI->isTDFork(forkCall))
                forkSites.insert(forkCall);
        }
    }
 
    return forkSites;
}

getLockSet()

OrderedSet< const ICFGNode * > SVF::MTASlicerBase::getLockSet ( const ICFGNode *  node )

protected

Definition at line 308 of file MTASlicer.cpp.

{
    OrderedSet<const ICFGNode*> allLockSites;
 
    // Synchronization dependence is based on may-lock spans. Retain both the
    // unconditional locks used to prove mutual exclusion and conditional locks
    // whose spans can affect the sliced lock analysis' classification.
    if (lockAnalysis->hasIntraLockSet(node))
    {
        const LockAnalysis::InstSet& intraLocks = lockAnalysis->getIntraLockSet(node);
        for (const ICFGNode* lockSite : intraLocks)
        {
            allLockSites.insert(lockSite);
        }
    }
    if (lockAnalysis->isInsideCondIntraLock(node))
    {
        const LockAnalysis::InstSet& conditionalLocks =
            lockAnalysis->getCondIntraLockSet(node);
        for (const ICFGNode* lockSite : conditionalLocks)
        {
            allLockSites.insert(lockSite);
        }
    }
 
    // Get context-sensitive locks
    if (lockAnalysis->hasCxtStmtFromInst(node))
    {
        const LockAnalysis::CxtStmtSet& cxtStmts = lockAnalysis->getCxtStmtsFromInst(node);
        for (const CxtStmt& cxtStmt : cxtStmts)
        {
            if (lockAnalysis->hasCxtLockFromCxtStmt(cxtStmt))
            {
                const LockAnalysis::CxtLockSet& cxtLocks =
                    lockAnalysis->getCxtLockFromCxtStmt(cxtStmt);
                for (const LockAnalysis::CxtLock& cxtLock : cxtLocks)
                {
                    allLockSites.insert(cxtLock.getStmt());
                }
            }
        }
    }
 
    return allLockSites;
}

getTCTNodeSetFromNode()

OrderedSet< const TCTNode * > SVF::MTASlicerBase::getTCTNodeSetFromNode ( const ICFGNode *  node )

protected

Definition at line 355 of file MTASlicer.cpp.

{
    OrderedSet<const TCTNode*> tctNodeSet;
 
    if (mhp->hasThreadStmtSet(node))
    {
        for (const CxtThreadStmt& cts : mhp->getThreadStmtSet(node))
        {
            if (mhp->getTCT()->hasGNode(cts.getTid()))
            {
                tctNodeSet.insert(mhp->getTCT()->getTCTNode(cts.getTid()));
            }
        }
    }
 
    return tctNodeSet;
}

svfgNodesToICFGNodes()

OrderedSet< const ICFGNode * > SVF::MTASlicerBase::svfgNodesToICFGNodes ( const OrderedSet< const VFGNode * > &  nodes, const OrderedSet< const SVFStmt * > &  seeds  )

protected

Project the retained VFG nodes (plus the seeds) onto their ICFG nodes.

Definition at line 464 of file MTASlicer.cpp.

{
    OrderedSet<const ICFGNode*> result;
    for (const SVFGNode* node : nodes)
        if (const StmtVFGNode* statementNode =
                    SVFUtil::dyn_cast<StmtVFGNode>(node))
            if (statementNode->getICFGNode() != nullptr)
                result.insert(statementNode->getICFGNode());
    for (const SVFStmt* stmt : seeds)
        if (stmt != nullptr && stmt->getICFGNode() != nullptr)
            result.insert(stmt->getICFGNode());
    return result;
}

Member Data Documentation

callGraph

CallGraph* SVF::MTASlicerBase::callGraph

protected

Definition at line 132 of file MTASlicer.h.

lockAnalysis

LockAnalysis* SVF::MTASlicerBase::lockAnalysis

protected

Definition at line 131 of file MTASlicer.h.

mhp

MHP* SVF::MTASlicerBase::mhp

protected

Definition at line 130 of file MTASlicer.h.

pta

AndersenBase* SVF::MTASlicerBase::pta

protected

Definition at line 129 of file MTASlicer.h.

svfg

SVFG* SVF::MTASlicerBase::svfg

protected

thread-aware VFG_pre (PTA/Single slicers; null for MTA)

Definition at line 133 of file MTASlicer.h.

svfir

SVFIR* SVF::MTASlicerBase::svfir

protected

Definition at line 128 of file MTASlicer.h.

---

The documentation for this class was generated from the following files:

• /home/runner/work/SVF/SVF/svf/include/MTA/MTASlicer.h
• /home/runner/work/SVF/SVF/svf/lib/MTA/MTASlicer.cpp