#include <MTASVFGBuilder.h>

Inheritance diagram for SVF::MTASVFGBuilder:

Classes
class	ThreadVFBuildConfig

struct	ThreadVFCandidate

Public Types
enum class	InterferenceEdgeMode { Analysis , SlicingOnly }

typedef Set< const StmtSVFGNode * >	SVFGNodeSet

typedef NodeBS	SVFGNodeIDSet

typedef std::pair< const StmtSVFGNode , const StmtSVFGNode >	ThreadVFEdge

using	ThreadVFQueryMap = Map< ThreadVFEdge, Set< const ICFGNode * > >

using	ThreadVFCandidateList = std::vector< ThreadVFCandidate >

Public Types inherited from SVF::SVFGBuilder
typedef PointerAnalysis::CallSiteSet	CallSiteSet

typedef PointerAnalysis::CallEdgeMap	CallEdgeMap

typedef PointerAnalysis::FunctionSet	FunctionSet

typedef SVFG::SVFGEdgeSetTy	SVFGEdgeSet

Public Member Functions
	MTASVFGBuilder (MHP mhp, LockAnalysis lockAnalysis, InterferenceEdgeMode edgeMode=InterferenceEdgeMode::Analysis)
	Constructor: driven by the interleaving (MHP) and lock analyses.

	~MTASVFGBuilder () override=default

const ThreadVFQueryMap &	getThreadVFQueryMap () const

void	replaceThreadAwareOverlay (MHP mhp, LockAnalysis lockAnalysis, const ThreadVFBuildConfig &config)

void	clearThreadAwareOverlay ()
	Remove all currently attached thread-aware interference edges.

size_t	getThreadAwareEdgeCount () const

Public Member Functions inherited from SVF::SVFGBuilder
	SVFGBuilder (bool _SVFGWithIndCall=Options::SVFGWithIndirectCall(), bool _SVFGWithPostOpts=Options::OPTSVFG())
	Constructor.

virtual	~SVFGBuilder ()=default
	Destructor.

SVFG *	buildPTROnlySVFG (BVDataPTAImpl *pta)

SVFG *	buildFullSVFG (BVDataPTAImpl *pta)

SVFG *	getSVFG () const
	Get SVFG instance.

void	markValidVFEdge (SVFGEdgeSet &edges)
	Mark feasible VF edge by removing it from set vfEdgesAtIndCallSite.

bool	isSpuriousVFEdgeAtIndCallSite (const SVFGEdge *edge)
	Return true if this is an VF Edge pre-connected by Andersen's analysis.

virtual std::unique_ptr< MemSSA >	buildMSSA (BVDataPTAImpl *pta, bool ptrOnlyMSSA)
	Build Memory SSA.

Protected Member Functions
void	buildSVFG () override
	Rewrite the SVFG build hook: build the stock SVFG, then add MHP edges.

std::unique_ptr< MRGenerator >	createMRGenerator (BVDataPTAImpl *pta, bool ptrOnlyMSSA) override

Protected Member Functions inherited from SVF::SVFGBuilder
SVFG *	build (BVDataPTAImpl *pta, VFG::VFGK kind)
	Create a DDA SVFG. By default actualOut and FormalIN are removed, unless withAOFI is set true.

virtual void	releaseMemory ()
	Release global SVFG.

Private Member Functions
void	collectLoadStoreSVFGNodes ()

bool	isInOverlayScope (const SVFGNode *node) const

void	connectThreadJoinEdges ()

void	addJoinRetEdge (const FormalOUTSVFGNode formalOut, const ActualOUTSVFGNode actualOut, CallSiteID callSiteId)

void	connectMHPEdges (PointerAnalysis *pta)
	Connect inter-thread (interference) value-flow edges for MHP pairs.

void	handleStoreLoad (const StmtSVFGNode store, const StmtSVFGNode load, PointerAnalysis *pta)

void	handleStoreStore (const StmtSVFGNode firstStore, const StmtSVFGNode secondStore, PointerAnalysis *pta)

void	recordThreadVFSource (const StmtSVFGNode source, const StmtSVFGNode destination, bool commonLock)

SVFGEdge *	addTDEdge (NodeID srcId, NodeID dstId, const PointsTo &pts)
	Add a thread-MHP indirect value-flow edge srcId -> dstId carrying pts.

SVFGNodeIDSet	getPredecessorNodes (const StmtSVFGNode *node)
	Lock-span head/tail tests (non-interference lock-pair pruning).

SVFGNodeIDSet	getSuccessorNodes (const StmtSVFGNode *node)

bool	isHeadOfSpan (const StmtSVFGNode *node)

bool	isTailOfSpan (const StmtSVFGNode *node)

Private Attributes
const SlicedSVFGView *	overlayScope = nullptr
	Active overlay configuration; defaults suit VFG_pre.

const ThreadVFCandidateList *	overlayCandidates = nullptr

bool	recordThreadVFQueries = true
	false = skip [THREAD-VF] recording

bool	labelInterferenceEdges = true
	false = VFG_pre (sliced-only): omit edge points-to labels

SVFGNodeSet	storeNodes

SVFGNodeSet	loadNodes

ThreadVFQueryMap	threadVFQueryMap
	[THREAD-VF] per-edge query map (see getThreadVFQueryMap).

MHP *	mhp

LockAnalysis *	lockAnalysis

Map< const StmtSVFGNode *, SVFGNodeIDSet >	predecessorCache

Map< const StmtSVFGNode *, SVFGNodeIDSet >	successorCache

Map< const StmtSVFGNode *, bool >	spanHeadCache

Map< const StmtSVFGNode *, bool >	spanTailCache

SVFGEdgeSet	threadAwareEdges

Additional Inherited Members
Protected Attributes inherited from SVF::SVFGBuilder
SVFGEdgeSet	vfEdgesAtIndCallSite
	SVFG Edges connected at indirect call/ret sites.

std::unique_ptr< SVFG >	svfg

bool	SVFGWithIndCall
	SVFG with precomputed indirect call edges.

bool	SVFGWithPostOpts
	Build optimised version of SVFG.

Detailed Description

Definition at line 46 of file MTASVFGBuilder.h.

Member Typedef Documentation

◆ SVFGNodeIDSet

typedef NodeBS SVF::MTASVFGBuilder::SVFGNodeIDSet

Definition at line 50 of file MTASVFGBuilder.h.

◆ SVFGNodeSet

typedef Set<const StmtSVFGNode*> SVF::MTASVFGBuilder::SVFGNodeSet

Definition at line 49 of file MTASVFGBuilder.h.

◆ ThreadVFCandidateList

using SVF::MTASVFGBuilder::ThreadVFCandidateList = std::vector<ThreadVFCandidate>

Definition at line 116 of file MTASVFGBuilder.h.

◆ ThreadVFEdge

typedef std::pair<const StmtSVFGNode*, const StmtSVFGNode*> SVF::MTASVFGBuilder::ThreadVFEdge

A candidate thread-aware value-flow edge s –o--> s' (src store, dst load/store), keyed by its endpoint SVFG nodes.

Definition at line 70 of file MTASVFGBuilder.h.

◆ ThreadVFQueryMap

using SVF::MTASVFGBuilder::ThreadVFQueryMap = Map<ThreadVFEdge, Set<const ICFGNode*> >

[THREAD-VF] per-edge query map (MSli §4.2, Fig. 6 rule [THREAD-VF]).

While building VFG_pre we record, for every candidate thread-aware value-flow edge (s,s') the construction evaluates, its Query(s –o--> s') set: the endpoints {s,s'} plus — under a common lock — the in-span witnesses Succ_spl(s) / Pred_spl'(s') that decide TL/HD membership, i.e. whether the edge survives the non-interference test (Def. 2). The query is kept per edge (not pre-unioned) so ILA slicing can restrict the sources to the edges that survive the FSPTA slice — ThreadVF(VFG'_pre) — rather than every candidate pair. Feeding the retained edges' queries into ILA slicing makes the sliced MHP/lock reproduce the same value-flow decisions the main phase makes, while keeping the slice minimal.

The value stores only the additional lock-span witnesses; the endpoint ICFG nodes are implicit in the key and consumers must add them back.

Definition at line 87 of file MTASVFGBuilder.h.

Member Enumeration Documentation

◆ InterferenceEdgeMode

enum class SVF::MTASVFGBuilder::InterferenceEdgeMode

strong

Enumerator
Analysis	Build labelled edges for FSMPTA.
SlicingOnly	Build unlabelled connectivity for VFG_pre slicing.

Definition at line 52 of file MTASVFGBuilder.h.

    {
        Analysis,   
        SlicingOnly 
    };

Constructor & Destructor Documentation

◆ MTASVFGBuilder()

SVF::MTASVFGBuilder::MTASVFGBuilder	(	MHP *	mhp,
		LockAnalysis *	lockAnalysis,
		InterferenceEdgeMode	edgeMode = `InterferenceEdgeMode::Analysis`
	)

inline

Constructor: driven by the interleaving (MHP) and lock analyses.

Definition at line 59 of file MTASVFGBuilder.h.

        : SVFGBuilder(),
          labelInterferenceEdges(edgeMode == InterferenceEdgeMode::Analysis),
          mhp(mhp), lockAnalysis(lockAnalysis)
    {
    }

◆ ~MTASVFGBuilder()

SVF::MTASVFGBuilder::~MTASVFGBuilder ( )

overridedefault

Member Function Documentation

◆ addJoinRetEdge()

void MTASVFGBuilder::addJoinRetEdge	(	const FormalOUTSVFGNode *	formalOut,
		const ActualOUTSVFGNode *	actualOut,
		CallSiteID	callSiteId
	)

private

Add a FormalOUT -> ActualOUT inter-procedural indirect ret edge for a join, mirroring SVFG::addInterIndirectVFRetEdge using the public SVFG API (points-to intersection + dedup via hasInterVFGEdge + addSVFGEdge).

Mirror of SVFG::addInterIndirectVFRetEdge over the public SVFG API, so the join edges can be added from the builder without modifying core SVFG.

Definition at line 173 of file MTASVFGBuilder.cpp.

{
    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, callSiteId))
    {
        SVFUtil::cast<RetIndSVFGEdge>(edge)->addPointsTo(cpts);
    }
    else
    {
        RetIndSVFGEdge* retEdge = new RetIndSVFGEdge(src, dst, callSiteId);
        retEdge->addPointsTo(cpts);
        svfg->addSVFGEdge(retEdge);
    }
}

◆ addTDEdge()

SVFGEdge * MTASVFGBuilder::addTDEdge	(	NodeID	srcId,
		NodeID	dstId,
		const PointsTo &	pts
	)

private

Add a thread-MHP indirect value-flow edge srcId -> dstId carrying pts.

Add (or merge into) a thread-MHP indirect value-flow edge src -> dst.

Definition at line 270 of file MTASVFGBuilder.cpp.

{
    SVFGNode* srcNode = svfg->getSVFGNode(srcId);
    SVFGNode* dstNode = svfg->getSVFGNode(dstId);
    assert(isInOverlayScope(srcNode) && isInOverlayScope(dstNode) &&
           "thread-aware overlay edge escaped its construction scope");
 
    // VFG_pre (sliced-only) mode: keep the edge for connectivity but omit its
    // points-to label -- no slice consumer reads it.
    if (!labelInterferenceEdges)
    {
        if (SVFGEdge* edge = svfg->hasThreadVFGEdge(srcNode, dstNode, SVFGEdge::TheadMHPIndirectVF))
            return edge;
        ThreadMHPIndSVFGEdge* indirectEdge = new ThreadMHPIndSVFGEdge(srcNode, dstNode);
        if (svfg->addSVFGEdge(indirectEdge))
        {
            threadAwareEdges.insert(indirectEdge);
            return indirectEdge;
        }
        return nullptr;
    }
 
    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
    {
        ThreadMHPIndSVFGEdge* indirectEdge = new ThreadMHPIndSVFGEdge(srcNode, dstNode);
        indirectEdge->addPointsTo(pts.toNodeBS());
        if (svfg->addSVFGEdge(indirectEdge))
        {
            threadAwareEdges.insert(indirectEdge);
            return indirectEdge;
        }
        return nullptr;
    }
}

◆ buildSVFG()

void MTASVFGBuilder::buildSVFG ( )

overrideprotectedvirtual

Rewrite the SVFG build hook: build the stock SVFG, then add MHP edges.

Build the stock (thread-oblivious) SVFG, add the FSAM join-related def-use edges (relocated out of core SVFG.cpp), then add thread-aware MHP edges.

Reimplemented from SVF::SVFGBuilder.

Definition at line 126 of file MTASVFGBuilder.cpp.

{
    svfg->buildSVFG();
    connectThreadJoinEdges();
    connectMHPEdges(svfg->getMSSA()->getPTA());
}

◆ clearThreadAwareOverlay()

void MTASVFGBuilder::clearThreadAwareOverlay ( )

Remove all currently attached thread-aware interference edges.

Definition at line 133 of file MTASVFGBuilder.cpp.

{
    for (SVFGEdge* edge : threadAwareEdges)
        svfg->removeSVFGEdge(edge);
    threadAwareEdges.clear();
}

◆ collectLoadStoreSVFGNodes()

void MTASVFGBuilder::collectLoadStoreSVFGNodes ( )

private

Collect the store/load SVFG nodes to pair for interference edges (all of them, or – when a slice is set – only the kept ones).

Collect all store/load SVFG nodes.

Definition at line 242 of file MTASVFGBuilder.cpp.

{
    for (SVFG::const_iterator it = svfg->begin(), eit = svfg->end(); it != eit; ++it)
    {
        const SVFGNode* svfgNode = it->second;
        const bool isLoad = SVFUtil::isa<LoadSVFGNode>(svfgNode);
        if (!isLoad && !SVFUtil::isa<StoreSVFGNode>(svfgNode))
            continue;
        const StmtSVFGNode* node = SVFUtil::cast<StmtSVFGNode>(svfgNode);
        if (node->getICFGNode() == nullptr)
            continue;
        if (!isInOverlayScope(node))
            continue;
        if (isLoad)
            loadNodes.insert(node);
        else
            storeNodes.insert(node);
    }
}

◆ connectMHPEdges()

void MTASVFGBuilder::connectMHPEdges ( PointerAnalysis * pta )

private

Connect inter-thread (interference) value-flow edges for MHP pairs.

For every MHP store/load and store/store pair, add the thread-aware (interference) value-flow edges.

Definition at line 600 of file MTASVFGBuilder.cpp.

{
    if (overlayCandidates != nullptr)
    {
        // The pre-analysis candidate set is a conservative directed universe.
        // Traverse it directly so main overlay construction is proportional to
        // retained candidates instead of re-enumerating every alias pair.
        OrderedSet<ThreadVFCandidate> processedStorePairs;
        for (const ThreadVFCandidate& candidate : *overlayCandidates)
        {
            const StmtSVFGNode* src = SVFUtil::dyn_cast<StmtSVFGNode>(
                                          svfg->getSVFGNode(
                                              candidate.sourceNodeId));
            const StmtSVFGNode* dst = SVFUtil::dyn_cast<StmtSVFGNode>(
                                          svfg->getSVFGNode(
                                              candidate.destinationNodeId));
            assert(src != nullptr && dst != nullptr &&
                   "thread-aware candidates must reference statement nodes");
            assert(SVFUtil::isa<StoreSVFGNode>(src) &&
                   "thread-aware candidate source must be a store");
            assert(isInOverlayScope(src) && isInOverlayScope(dst) &&
                   "thread-aware candidate escaped its selected scope");
 
            if (SVFUtil::isa<LoadSVFGNode>(dst))
                handleStoreLoad(src, dst, pta);
            else if (SVFUtil::isa<StoreSVFGNode>(dst))
            {
                const ThreadVFCandidate canonicalPair =
                    candidate.sourceNodeId < candidate.destinationNodeId
                    ? candidate
                    : ThreadVFCandidate(candidate.destinationNodeId,
                                        candidate.sourceNodeId);
                if (processedStorePairs.insert(canonicalPair).second)
                    // Main ILA re-decides the unordered pair once; the handler
                    // emits whichever directed edges pass the lock-span rules.
                    handleStoreStore(src, dst, pta);
            }
        }
        return;
    }
 
    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> objectToStoreIds;
    Map<NodeID, SVFGNodeIDSet> objectToLoadIds;
    for (const StmtSVFGNode* store : storeNodes)
        for (NodeID objectId : pta->getPts(store->getDstNodeID()))
            objectToStoreIds[objectId].set(store->getId());
    for (const StmtSVFGNode* load : loadNodes)
        for (NodeID objectId : pta->getPts(load->getSrcNodeID()))
            objectToLoadIds[objectId].set(load->getId());
 
    for (const StmtSVFGNode* store : storeNodes)
    {
        SVFGNodeIDSet candidateLoads;
        SVFGNodeIDSet candidateStores;
        for (NodeID objectId : pta->getPts(store->getDstNodeID()))
        {
            candidateStores |= objectToStoreIds[objectId];
            const auto loads = objectToLoadIds.find(objectId);
            if (loads != objectToLoadIds.end())
                candidateLoads |= loads->second;
        }
 
        for (NodeID loadId : candidateLoads)
        {
            const StmtSVFGNode* load =
                SVFUtil::cast<StmtSVFGNode>(svfg->getSVFGNode(loadId));
            handleStoreLoad(store, load, pta);
        }
 
        // Visit each unordered store pair once: only partners with a larger id.
        const NodeID storeId = store->getId();
        for (NodeID otherId : candidateStores)
        {
            if (otherId <= storeId)
                continue;
            const StmtSVFGNode* other =
                SVFUtil::cast<StmtSVFGNode>(svfg->getSVFGNode(otherId));
            handleStoreStore(store, other, pta);
        }
    }
}

◆ connectThreadJoinEdges()

void MTASVFGBuilder::connectThreadJoinEdges ( )

private

FSAM join-related thread-oblivious value flow (the "return" half of treating a join as a call without a forward): connect each start routine's exit defs (FormalOUT) to the ActualOUT at every site that joins it (FormalOUT -> ActualOUT ret edge). Done here as a post-pass over the stock SVFG, so core SVFG.cpp stays unmodified.

FSAM join-related def-use (the "return" half of treating a join as a call without a forward): for every FormalOUT (a start routine's exit def), connect it to the ActualOUT at each site that joins that routine. Relocated here from core SVFG::connectIndirectSVFGEdges so the stock SVFG stays unmodified.

Definition at line 204 of file MTASVFGBuilder.cpp.

{
    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* callSite : joinSites)
        {
            if (!mssa->hasCHI(callSite))
                continue;
            SVFG::ActualOUTSVFGNodeSet& actualOuts =
                svfg->getActualOUTSVFGNodes(callSite);
            for (NodeID actualOutId : actualOuts)
            {
                const ActualOUTSVFGNode* actualOut =
                    SVFUtil::cast<ActualOUTSVFGNode>(
                        svfg->getSVFGNode(actualOutId));
                addJoinRetEdge(
                    formalOut, actualOut,
                    svfg->getCallSiteID(callSite, formalOut->getFun()));
            }
        }
    }
}

◆ createMRGenerator()

std::unique_ptr< MRGenerator > MTASVFGBuilder::createMRGenerator	(	BVDataPTAImpl *	pta,
		bool	ptrOnlyMSSA
	)

overrideprotectedvirtual

Inject a thread-aware MRGenerator so the MemSSA mod-ref carries the FSAM fork/join side effects (relocated here from core MemRegion).

Reimplemented from SVF::SVFGBuilder.

Definition at line 106 of file MTASVFGBuilder.cpp.

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

◆ getPredecessorNodes()

MTASVFGBuilder::SVFGNodeIDSet MTASVFGBuilder::getPredecessorNodes ( const StmtSVFGNode * node )

private

Lock-span head/tail tests (non-interference lock-pair pruning).

Backward reachable store SVFG nodes via indirect value flow (lock-span head test).

Definition at line 313 of file MTASVFGBuilder.cpp.

{
    const auto found = predecessorCache.find(node);
    if (found != predecessorCache.end())
        return found->second;
 
    SVFGNodeIDSet predecessors;
    Set<const SVFGNode*> worklist;
    Set<const SVFGNode*> visited;
 
    for (SVFGEdge::SVFGEdgeSetTy::iterator iter = node->InEdgeBegin();
            iter != node->InEdgeEnd(); ++iter)
    {
        SVFGEdge* edge = *iter;
        if (edge->isIndirectVFGEdge() && !edge->isThreadMHPIndirectVFGEdge() &&
                isInOverlayScope(edge->getSrcNode()))
            worklist.insert(edge->getSrcNode());
    }
 
    while (!worklist.empty())
    {
        const SVFGNode* node = *worklist.begin();
        worklist.erase(worklist.begin());
        visited.insert(node);
        if (SVFUtil::isa<StoreSVFGNode>(node))
            predecessors.set(node->getId());
        else
        {
            for (SVFGEdge::SVFGEdgeSetTy::iterator iter = node->InEdgeBegin(); iter != node->InEdgeEnd(); ++iter)
            {
                SVFGEdge* edge = *iter;
                if (edge->isIndirectVFGEdge() &&
                        !edge->isThreadMHPIndirectVFGEdge() &&
                        isInOverlayScope(edge->getSrcNode()) &&
                        visited.find(edge->getSrcNode()) == visited.end())
                    worklist.insert(edge->getSrcNode());
            }
        }
    }
    predecessorCache[node] = predecessors;
    return predecessors;
}

◆ getSuccessorNodes()

MTASVFGBuilder::SVFGNodeIDSet MTASVFGBuilder::getSuccessorNodes ( const StmtSVFGNode * node )

private

Forward reachable store/load SVFG nodes via indirect value flow (lock-span tail test).

Definition at line 360 of file MTASVFGBuilder.cpp.

{
    const auto found = successorCache.find(node);
    if (found != successorCache.end())
        return found->second;
 
    SVFGNodeIDSet successors;
    Set<const SVFGNode*> worklist;
    Set<const SVFGNode*> visited;
 
    for (SVFGEdge::SVFGEdgeSetTy::iterator iter = node->OutEdgeBegin();
            iter != node->OutEdgeEnd(); ++iter)
    {
        SVFGEdge* edge = *iter;
        if (edge->isIndirectVFGEdge() && !edge->isThreadMHPIndirectVFGEdge() &&
                isInOverlayScope(edge->getDstNode()))
            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))
            successors.set(node->getId());
        else
        {
            for (SVFGEdge::SVFGEdgeSetTy::iterator iter = node->OutEdgeBegin(); iter != node->OutEdgeEnd(); ++iter)
            {
                SVFGEdge* edge = *iter;
                if (edge->isIndirectVFGEdge() &&
                        !edge->isThreadMHPIndirectVFGEdge() &&
                        isInOverlayScope(edge->getDstNode()) &&
                        visited.find(edge->getDstNode()) == visited.end())
                    worklist.insert(edge->getDstNode());
            }
        }
    }
    successorCache[node] = successors;
    return successors;
}

◆ getThreadAwareEdgeCount()

size_t SVF::MTASVFGBuilder::getThreadAwareEdgeCount ( ) const

inline

Definition at line 157 of file MTASVFGBuilder.h.

    {
        return threadAwareEdges.size();
    }

◆ getThreadVFQueryMap()

const ThreadVFQueryMap & SVF::MTASVFGBuilder::getThreadVFQueryMap ( ) const

inline

Definition at line 88 of file MTASVFGBuilder.h.

    {
        return threadVFQueryMap;
    }

◆ handleStoreLoad()

void MTASVFGBuilder::handleStoreLoad	(	const StmtSVFGNode *	store,
		const StmtSVFGNode *	load,
		PointerAnalysis *	pta
	)

private

Store -> Load interference: add a thread-aware def-use edge if the store may happen in parallel with and may alias the load, unless excluded by a common lock (then only when the store is a span tail and the load a span head).

Definition at line 507 of file MTASVFGBuilder.cpp.

{
    const ICFGNode* storeNode = store->getICFGNode();
    const ICFGNode* loadNode = load->getICFGNode();
 
    const bool mayParallel = mhp->mayHappenInParallel(storeNode, loadNode);
    if (!mayParallel)
        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.
    // The label is only needed when the edge will be solved (main FSMPTA); in
    // VFG_pre (sliced-only) mode skip the intersection -- it is never read.
    PointsTo pts;
    if (labelInterferenceEdges)
    {
        pts = pta->getPts(store->getDstNodeID());
        pts &= pta->getPts(load->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.
    const bool commonLock =
        lockAnalysis->isProtectedByCommonLock(storeNode, loadNode);
    if (recordThreadVFQueries)
        recordThreadVFSource(store, load, commonLock);
 
    if (commonLock)
    {
        if (isTailOfSpan(store) && isHeadOfSpan(load))
            addTDEdge(store->getId(), load->getId(), pts);
    }
    else
    {
        addTDEdge(store->getId(), load->getId(), pts);
    }
}

◆ handleStoreStore()

void MTASVFGBuilder::handleStoreStore	(	const StmtSVFGNode *	firstStore,
		const StmtSVFGNode *	secondStore,
		PointerAnalysis *	pta
	)

private

Store -> Store interference (symmetric): add thread-aware def-use edges in both directions, with the same lock-span pruning as store/load.

Definition at line 553 of file MTASVFGBuilder.cpp.

{
    const ICFGNode* firstNode = firstStore->getICFGNode();
    const ICFGNode* secondNode = secondStore->getICFGNode();
 
    const bool mayParallel = mhp->mayHappenInParallel(firstNode, secondNode);
    if (!mayParallel)
        return;
 
    // No alias() re-check: see handleStoreLoad -- bucketing already guarantees a
    // shared raw object. Skip the label intersection in VFG_pre (sliced-only) mode.
    PointsTo pts;
    if (labelInterferenceEdges)
    {
        pts = pta->getPts(firstStore->getDstNodeID());
        pts &= pta->getPts(secondStore->getDstNodeID());
    }
 
    // Both directions are candidate thread-aware edges; extract sources for each.
    const bool commonLock =
        lockAnalysis->isProtectedByCommonLock(firstNode, secondNode);
    if (recordThreadVFQueries)
    {
        recordThreadVFSource(firstStore, secondStore, commonLock);
        recordThreadVFSource(secondStore, firstStore, commonLock);
    }
 
    if (commonLock)
    {
        if (isTailOfSpan(firstStore) && isHeadOfSpan(secondStore))
            addTDEdge(firstStore->getId(), secondStore->getId(), pts);
        if (isTailOfSpan(secondStore) && isHeadOfSpan(firstStore))
            addTDEdge(secondStore->getId(), firstStore->getId(), pts);
    }
    else
    {
        addTDEdge(firstStore->getId(), secondStore->getId(), pts);
        addTDEdge(secondStore->getId(), firstStore->getId(), pts);
    }
}

◆ isHeadOfSpan()

bool MTASVFGBuilder::isHeadOfSpan ( const StmtSVFGNode * node )

private

Whether, for all lock spans n belongs to, n is the first write (span head).

Definition at line 407 of file MTASVFGBuilder.cpp.

{
    const auto found = spanHeadCache.find(node);
    if (found != spanHeadCache.end())
        return found->second;
 
    const SVFGNodeIDSet predecessors = getPredecessorNodes(node);
    for (NodeID id : predecessors)
    {
        const StmtSVFGNode* prevNode = SVFUtil::dyn_cast<StmtSVFGNode>(svfg->getSVFGNode(id));
        if (prevNode != nullptr && lockAnalysis->isInSameSpan(
                    prevNode->getICFGNode(), node->getICFGNode()))
        {
            spanHeadCache[node] = false;
            return false;
        }
    }
    spanHeadCache[node] = true;
    return true;
}

◆ isInOverlayScope()

bool MTASVFGBuilder::isInOverlayScope ( const SVFGNode * node ) const

private

Definition at line 262 of file MTASVFGBuilder.cpp.

{
    return overlayScope == nullptr || overlayScope->isKeptNode(node);
}

◆ isTailOfSpan()

bool MTASVFGBuilder::isTailOfSpan ( const StmtSVFGNode * node )

private

Whether, for all lock spans n belongs to, n is the last write (span tail).

Definition at line 431 of file MTASVFGBuilder.cpp.

{
    assert(SVFUtil::isa<StoreSVFGNode>(node) &&
           "tail test only for store nodes");
 
    const auto found = spanTailCache.find(node);
    if (found != spanTailCache.end())
        return found->second;
 
    const SVFGNodeIDSet successors = getSuccessorNodes(node);
    for (NodeID id : successors)
    {
        const SVFGNode* successor = svfg->getSVFGNode(id);
        if (SVFUtil::isa<LoadSVFGNode>(successor))
            continue;
        const StmtSVFGNode* successorStatement =
            SVFUtil::dyn_cast<StmtSVFGNode>(successor);
        if (successorStatement != nullptr && lockAnalysis->isInSameSpan(
                    successorStatement->getICFGNode(), node->getICFGNode()))
        {
            spanTailCache[node] = false;
            return false;
        }
    }
    spanTailCache[node] = true;
    return true;
}

◆ recordThreadVFSource()

void MTASVFGBuilder::recordThreadVFSource	(	const StmtSVFGNode *	source,
		const StmtSVFGNode *	destination,
		bool	commonLock
	)

private

Record the [THREAD-VF] slicing sources for one candidate pair s –o--> s' (source = store, destination = load/store). Adds the endpoints, and — when the pair is protected by a common lock — the in-span successor/predecessor witnesses needed to re-decide the non-interference (tail/head) test.

Record the per-edge [THREAD-VF] query for one candidate pair s –o--> s' (see getThreadVFQueryMap for the rule): the endpoints, plus – under a common lock – the in-span Succ_spl(s) / Pred_spl'(s') witnesses. Enumerated fully (the tail/head boolean tests short-circuit; source extraction must not).

Definition at line 465 of file MTASVFGBuilder.cpp.

{
    // 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).
    Set<const ICFGNode*>& query =
        threadVFQueryMap[ {source, destination}];
 
    if (!commonLock)
        return;
 
    // Succ_spl(s) = { x in s's span | x is a store, s --o--> x }.
    for (NodeID id : getSuccessorNodes(source))
    {
        const SVFGNode* successor = svfg->getSVFGNode(id);
        if (!SVFUtil::isa<StoreSVFGNode>(successor))
            continue;
        const StmtSVFGNode* successorStatement =
            SVFUtil::cast<StmtSVFGNode>(successor);
        if (lockAnalysis->isInSameSpan(
                    successorStatement->getICFGNode(), source->getICFGNode()))
            query.insert(successorStatement->getICFGNode());
    }
 
    // Pred_spl'(s') = { x in s' span | x --o--> s' }.
    for (NodeID id : getPredecessorNodes(destination))
    {
        const StmtSVFGNode* prevNode =
            SVFUtil::dyn_cast<StmtSVFGNode>(svfg->getSVFGNode(id));
        if (prevNode != nullptr && lockAnalysis->isInSameSpan(
                    prevNode->getICFGNode(), destination->getICFGNode()))
            query.insert(prevNode->getICFGNode());
    }
}

◆ replaceThreadAwareOverlay()

void MTASVFGBuilder::replaceThreadAwareOverlay	(	MHP *	mhp,
		LockAnalysis *	lockAnalysis,
		const ThreadVFBuildConfig &	config
	)

Replace only the ILA-dependent thread-aware overlay. The underlying MemorySSA, stock SVFG, and fork/join value flow remain unchanged.

Definition at line 140 of file MTASVFGBuilder.cpp.

{
    assert(svfg != nullptr && "base SVFG must be built before replacing its overlay");
    assert(mainMHP != nullptr && mainLockAnalysis != nullptr &&
           "thread-aware overlay requires main ILA results");
 
    clearThreadAwareOverlay();
    mhp = mainMHP;
    lockAnalysis = mainLockAnalysis;
    overlayScope = config.scope;
    overlayCandidates = config.candidates;
    recordThreadVFQueries = false;
    labelInterferenceEdges = true;
 
    storeNodes.clear();
    loadNodes.clear();
    threadVFQueryMap.clear();
    predecessorCache.clear();
    successorCache.clear();
    spanHeadCache.clear();
    spanTailCache.clear();
 
    connectMHPEdges(svfg->getMSSA()->getPTA());
    overlayScope = nullptr;
    overlayCandidates = nullptr;
}

Member Data Documentation

◆ labelInterferenceEdges

bool SVF::MTASVFGBuilder::labelInterferenceEdges = true

private

false = VFG_pre (sliced-only): omit edge points-to labels

Definition at line 175 of file MTASVFGBuilder.h.

◆ loadNodes

SVFGNodeSet SVF::MTASVFGBuilder::loadNodes

private

Definition at line 225 of file MTASVFGBuilder.h.

◆ lockAnalysis

LockAnalysis* SVF::MTASVFGBuilder::lockAnalysis

private

Definition at line 230 of file MTASVFGBuilder.h.

◆ mhp

MHP* SVF::MTASVFGBuilder::mhp

private

Definition at line 229 of file MTASVFGBuilder.h.

◆ overlayCandidates

const ThreadVFCandidateList* SVF::MTASVFGBuilder::overlayCandidates = nullptr

private

Definition at line 173 of file MTASVFGBuilder.h.

◆ overlayScope

const SlicedSVFGView* SVF::MTASVFGBuilder::overlayScope = nullptr

private

Active overlay configuration; defaults suit VFG_pre.

null = whole base SVFG

Definition at line 172 of file MTASVFGBuilder.h.

◆ predecessorCache

Map<const StmtSVFGNode*, SVFGNodeIDSet> SVF::MTASVFGBuilder::predecessorCache

private

Definition at line 232 of file MTASVFGBuilder.h.

◆ recordThreadVFQueries

bool SVF::MTASVFGBuilder::recordThreadVFQueries = true

private

false = skip [THREAD-VF] recording

Definition at line 174 of file MTASVFGBuilder.h.

◆ spanHeadCache

Map<const StmtSVFGNode*, bool> SVF::MTASVFGBuilder::spanHeadCache

private

Definition at line 234 of file MTASVFGBuilder.h.

◆ spanTailCache

Map<const StmtSVFGNode*, bool> SVF::MTASVFGBuilder::spanTailCache

private

Definition at line 235 of file MTASVFGBuilder.h.

◆ storeNodes

SVFGNodeSet SVF::MTASVFGBuilder::storeNodes

private

Definition at line 224 of file MTASVFGBuilder.h.

◆ successorCache

Map<const StmtSVFGNode*, SVFGNodeIDSet> SVF::MTASVFGBuilder::successorCache

private

Definition at line 233 of file MTASVFGBuilder.h.

◆ threadAwareEdges

SVFGEdgeSet SVF::MTASVFGBuilder::threadAwareEdges

private

Definition at line 236 of file MTASVFGBuilder.h.

◆ threadVFQueryMap

ThreadVFQueryMap SVF::MTASVFGBuilder::threadVFQueryMap

private

[THREAD-VF] per-edge query map (see getThreadVFQueryMap).

Definition at line 228 of file MTASVFGBuilder.h.

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

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

Classes

Public Types

Public Member Functions

Protected Member Functions

Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ SVFGNodeIDSet

◆ SVFGNodeSet

◆ ThreadVFCandidateList

◆ ThreadVFEdge

◆ ThreadVFQueryMap

Member Enumeration Documentation

◆ InterferenceEdgeMode

Constructor & Destructor Documentation

◆ MTASVFGBuilder()

◆ ~MTASVFGBuilder()

Member Function Documentation

◆ addJoinRetEdge()

◆ addTDEdge()

◆ buildSVFG()

◆ clearThreadAwareOverlay()

◆ collectLoadStoreSVFGNodes()

◆ connectMHPEdges()

◆ connectThreadJoinEdges()

◆ createMRGenerator()

◆ getPredecessorNodes()

◆ getSuccessorNodes()

◆ getThreadAwareEdgeCount()

◆ getThreadVFQueryMap()

◆ handleStoreLoad()

◆ handleStoreStore()

◆ isHeadOfSpan()

◆ isInOverlayScope()

◆ isTailOfSpan()

◆ recordThreadVFSource()

◆ replaceThreadAwareOverlay()

Member Data Documentation

◆ labelInterferenceEdges

◆ loadNodes

◆ lockAnalysis

◆ mhp

◆ overlayCandidates

◆ overlayScope

◆ predecessorCache

◆ recordThreadVFQueries

◆ spanHeadCache

◆ spanTailCache

◆ storeNodes

◆ successorCache

◆ threadAwareEdges

◆ threadVFQueryMap