Classes
struct	NodeData

Static Public Member Functions
static unsigned	detectSCCs (VersionedFlowSensitive vfs, const SVFG svfg, const NodeID object, const std::vector< const SVFGNode * > &startingNodes, std::vector< int > &partOf, std::vector< const IndirectSVFGEdge * > &footprint)

Private Types
typedef struct SVF::VersionedFlowSensitive::SCC::NodeData	NodeData

Static Private Member Functions
static void	visit (VersionedFlowSensitive vfs, const NodeID object, std::vector< int > &partOf, std::vector< const IndirectSVFGEdge > &footprint, std::vector< NodeData > &nodeData, std::stack< const SVFGNode * > &stack, int &index, int &currentSCC, const SVFGNode *v)
	Called by detectSCCs then called recursively.

Detailed Description

Definition at line 252 of file VersionedFlowSensitive.h.

Member Typedef Documentation

◆ NodeData

typedef struct SVF::VersionedFlowSensitive::SCC::NodeData SVF::VersionedFlowSensitive::SCC::NodeData

private

Member Function Documentation

◆ detectSCCs()

unsigned VersionedFlowSensitive::SCC::detectSCCs	(	VersionedFlowSensitive *	vfs,
		const SVFG *	svfg,
		const NodeID	object,
		const std::vector< const SVFGNode * > &	startingNodes,
		std::vector< int > &	partOf,
		std::vector< const IndirectSVFGEdge * > &	footprint
	)

static

Determines the strongly connected components of svfg following only edges labelled with object. partOf[n] = scc means nodes n is part of SCC scc. startingNodes contains the nodes to begin the search from. After completion, footprint will contain all edges which object appears on (as reached through the algorithm described above) sorted.

This is not a general SCC detection but specifically for versioning, so edges to delta nodes are skipped as they are prelabelled. Edges to stores are also skipped to as they yield a new version (they cannot be part of an SCC containing more than themselves). Skipped edges still form part of the footprint.

Definition at line 1113 of file VersionedFlowSensitive.cpp.

{
    partOf.resize(svfg->getTotalNodeNum());
    std::fill(partOf.begin(), partOf.end(), -1);
    footprint.clear();
 
    std::vector<NodeData> nodeData(svfg->getTotalNodeNum(), { -1, -1, false});
    std::stack<const SVFGNode *> stack;
 
    int index = 0;
    int currentSCC = 0;
 
    for (const SVFGNode *v : startingNodes)
    {
        if (nodeData[v->getId()].index == -1)
        {
            visit(vfs, object, partOf, footprint, nodeData, stack, index, currentSCC, v);
        }
    }
 
    // Make sure footprints with the same edges pass ==/hash the same.
    std::sort(footprint.begin(), footprint.end());
 
    return currentSCC;
}

◆ visit()

void VersionedFlowSensitive::SCC::visit	(	VersionedFlowSensitive *	vfs,
		const NodeID	object,
		std::vector< int > &	partOf,
		std::vector< const IndirectSVFGEdge * > &	footprint,
		std::vector< NodeData > &	nodeData,
		std::stack< const SVFGNode * > &	stack,
		int &	index,
		int &	currentSCC,
		const SVFGNode *	v
	)

staticprivate

Called by detectSCCs then called recursively.

Definition at line 1143 of file VersionedFlowSensitive.cpp.

{
    const NodeID vId = v->getId();
 
    nodeData[vId].index = index;
    nodeData[vId].lowlink = index;
    ++index;
 
    stack.push(v);
    nodeData[vId].onStack = true;
 
    for (const SVFGEdge *e : v->getOutEdges())
    {
        const IndirectSVFGEdge *ie = SVFUtil::dyn_cast<IndirectSVFGEdge>(e);
        if (!ie) continue;
 
        const SVFGNode *w = ie->getDstNode();
        const NodeID wId = w->getId();
 
        // If object is not part of the edge, there is no edge from v to w.
        if (!ie->getPointsTo().test(object)) continue;
 
        // Even if we don't count edges to stores and deltas for SCCs' sake, they
        // are relevant to the footprint as a propagation still occurs over such edges.
        footprint.push_back(ie);
 
        // Ignore edges to delta nodes because they are prelabeled so cannot
        // be part of the SCC v is in (already in nodesTodo from the prelabeled set).
        // Similarly, store nodes.
        if (vfs->delta(wId) || vfs->isStore(wId)) continue;
 
        if (nodeData[wId].index == -1)
        {
            visit(vfs, object, partOf, footprint, nodeData, stack, index, currentSCC, w);
            nodeData[vId].lowlink = std::min(nodeData[vId].lowlink, nodeData[wId].lowlink);
        }
        else if (nodeData[wId].onStack)
        {
            nodeData[vId].lowlink = std::min(nodeData[vId].lowlink, nodeData[wId].index);
        }
    }
 
    if (nodeData[vId].lowlink == nodeData[vId].index)
    {
        const SVFGNode *w = nullptr;
        do
        {
            w = stack.top();
            stack.pop();
            const NodeID wId = w->getId();
            nodeData[wId].onStack = false;
            partOf[wId] = currentSCC;
        }
        while (w != v);
 
        // For the next SCC.
        ++currentSCC;
    }
}

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

/home/runner/work/SVF/SVF/svf/include/WPA/VersionedFlowSensitive.h
/home/runner/work/SVF/SVF/svf/lib/WPA/VersionedFlowSensitive.cpp

Classes

Static Public Member Functions