SVF::SlicedICFGView Class Reference

#include <SlicedGraphs.h>

Public Member Functions
	SlicedICFGView (ICFG *icfg, const OrderedSet< const ICFGNode * > &keepNodes)
	Build an ICFG view from its explicit node membership.
void	getSuccNodes (const ICFGNode *node, std::vector< const ICFGNode * > &out) const
	Get successor nodes (including bridged edges)
void	getPredNodes (const ICFGNode *node, std::vector< const ICFGNode * > &out) const
	Get predecessor nodes (including bridged edges)
bool	isKeptNode (const ICFGNode *node) const
	Check if a node is in the sliced view.
const ICFGNode *	getFunEntry (const FunObjVar *fun) const
	First kept node of fun's entry, or null when fun is outside the view.
const ICFGNode *	getFunExit (const FunObjVar *fun) const
	Kept synthetic exit node of fun, or null when fun is outside the view.
void	getFunICFGNodes (const FunObjVar *fun, std::vector< const ICFGNode * > &out) const
	Kept ICFG nodes of fun.
const OrderedSet< const ICFGNode * > &	getKeptNodes () const
	Get all kept nodes.
const OrderedSet< const ICFGNode * > *	bridgedSuccsOf (const ICFGNode *n) const
const OrderedSet< const ICFGNode * > *	bridgedPredsOf (const ICFGNode *n) const
void	dump (const std::string &filename) const
	Dump sliced ICFG to dot file.
ICFG *	getOriginalICFG () const
	Get original ICFG.

Private Member Functions
void	buildICFGSets (const OrderedSet< const ICFGNode * > &keepNodes)
void	buildBridgedEdges ()

Static Private Member Functions
static void	getLocalSuccessors (const ICFGNode *node, const Map< const ICFGNode *, const ICFGNode * > &callsiteReturnNodes, std::vector< const ICFGNode * > &successors)

Private Attributes
ICFG *	icfg
OrderedSet< const ICFGNode * >	keptNodes
Map< const ICFGNode *, OrderedSet< const ICFGNode * > >	bridgedEdges
Map< const ICFGNode *, OrderedSet< const ICFGNode * > >	bridgedPreds
Set< const ICFGNode * >	keptNodesSet

Detailed Description

Definition at line 58 of file SlicedGraphs.h.

Constructor & Destructor Documentation

SlicedICFGView()

SVF::SlicedICFGView::SlicedICFGView	(	ICFG *	icfg,
		const OrderedSet< const ICFGNode * > &	keepNodes
	)

Build an ICFG view from its explicit node membership.

Definition at line 267 of file SlicedGraphs.cpp.

    : icfg(icfg)
{
    buildICFGSets(keepNodes);
    buildBridgedEdges();
}

Member Function Documentation

bridgedPredsOf()

const OrderedSet< const ICFGNode * > * SVF::SlicedICFGView::bridgedPredsOf ( const ICFGNode *  n ) const

inline

Definition at line 96 of file SlicedGraphs.h.

    {
        auto it = bridgedPreds.find(n);
        return it == bridgedPreds.end() ? nullptr : &it->second;
    }

bridgedSuccsOf()

const OrderedSet< const ICFGNode * > * SVF::SlicedICFGView::bridgedSuccsOf ( const ICFGNode *  n ) const

inline

Bridged (synthetic) successors/predecessors of a kept node, or null if none. The traits iterators use these alongside the node's kept original edges.

Definition at line 91 of file SlicedGraphs.h.

    {
        auto it = bridgedEdges.find(n);
        return it == bridgedEdges.end() ? nullptr : &it->second;
    }

buildBridgedEdges()

void SVF::SlicedICFGView::buildBridgedEdges ( )

private

Definition at line 330 of file SlicedGraphs.cpp.

{
    // bridgedEdges[u] (u kept) = kept nodes reachable from u through removed-only
    // paths = U reachKept(s) over removed successors s of u, where reachKept(r) is
    // computed by SCC-condensing the removed subgraph (cyclic) and propagating
    // kept-reachability over the condensation -- linear, vs. node contraction whose
    // cross-products blow up when the removed region is large (small slices).
 
    // Index the removed nodes and their removed-only adjacency + kept successors.
    std::vector<const ICFGNode*> removed;
    Map<const ICFGNode*, int> removedNodeIndex;
    for (ICFG::iterator it = icfg->begin(), eit = icfg->end();
            it != eit; ++it)
    {
        const ICFGNode* node = it->second;
        if (node == nullptr || keptNodesSet.count(node))
            continue;
        removedNodeIndex[node] = static_cast<int>(removed.size());
        removed.push_back(node);
    }
    const int removedNodeCount = static_cast<int>(removed.size());
 
    // call_i -> ret_i summary for call sites with an omitted callee (some resolved
    // callee entry not retained), for every call site so paths can compose through
    // removed ones. ret_i is in the same caller, so the seed stays intra-procedural.
    Map<const ICFGNode*, const ICFGNode*> seedRet;
    for (ICFG::iterator it = icfg->begin(), eit = icfg->end();
            it != eit; ++it)
    {
        const CallICFGNode* call = SVFUtil::dyn_cast<CallICFGNode>(it->second);
        if (call == nullptr || call->getRetICFGNode() == nullptr)
            continue;
        for (const ICFGEdge* edge : call->getOutEdges())
            if (edge != nullptr && SVFUtil::isa<CallCFGEdge>(edge) &&
                    keptNodesSet.count(edge->getDstNode()) == 0)
            {
                seedRet[call] = call->getRetICFGNode();
                break;
            }
    }
    // Local successors = intra edges + matched call->ret seeds; the only edges
    // contraction may traverse. Original call/ret edges are excluded.
    std::vector<std::vector<int>> removedSuccessors(removedNodeCount);
    std::vector<std::vector<const ICFGNode*>>
                                           keptSuccessors(removedNodeCount);
    std::vector<const ICFGNode*> successors;
    for (int nodeIndex = 0; nodeIndex < removedNodeCount; ++nodeIndex)
    {
        getLocalSuccessors(removed[nodeIndex], seedRet, successors);
        for (const ICFGNode* successor : successors)
        {
            if (keptNodesSet.count(successor))
                keptSuccessors[nodeIndex].push_back(successor);
            else
            {
                const auto found = removedNodeIndex.find(successor);
                if (found != removedNodeIndex.end())
                    removedSuccessors[nodeIndex].push_back(found->second);
            }
        }
    }
 
    // Iterative Tarjan SCC over the removed subgraph. Components are produced in
    // reverse-topological order, so comp ids of a node's successors are < its own.
    std::vector<int> discoveryIndex(removedNodeCount, -1);
    std::vector<int> lowLink(removedNodeCount, 0);
    std::vector<int> component(removedNodeCount, -1);
    std::vector<char> onStack(removedNodeCount, 0);
    std::vector<int> tarjanStack;
    int nextDiscoveryIndex = 0;
    int componentCount = 0;
    for (int root = 0; root < removedNodeCount; ++root)
    {
        if (discoveryIndex[root] != -1)
            continue;
        std::vector<std::pair<int, size_t>> work;
        work.emplace_back(root, 0);
        while (!work.empty())
        {
            const int nodeIndex = work.back().first;
            size_t& successorPosition = work.back().second;
            if (successorPosition == 0)
            {
                discoveryIndex[nodeIndex] =
                    lowLink[nodeIndex] = nextDiscoveryIndex++;
                tarjanStack.push_back(nodeIndex);
                onStack[nodeIndex] = 1;
            }
            bool descend = false;
            while (successorPosition < removedSuccessors[nodeIndex].size())
            {
                const int successorIndex =
                    removedSuccessors[nodeIndex][successorPosition++];
                if (discoveryIndex[successorIndex] == -1)
                {
                    work.emplace_back(successorIndex, 0);
                    descend = true;
                    break;
                }
                if (onStack[successorIndex] &&
                        discoveryIndex[successorIndex] < lowLink[nodeIndex])
                    lowLink[nodeIndex] = discoveryIndex[successorIndex];
            }
            if (descend)
                continue;
            if (lowLink[nodeIndex] == discoveryIndex[nodeIndex])
            {
                while (true)
                {
                    const int componentNode = tarjanStack.back();
                    tarjanStack.pop_back();
                    onStack[componentNode] = 0;
                    component[componentNode] = componentCount;
                    if (componentNode == nodeIndex)
                        break;
                }
                ++componentCount;
            }
            work.pop_back();
            if (!work.empty())
            {
                const int parentIndex = work.back().first;
                if (lowLink[nodeIndex] < lowLink[parentIndex])
                    lowLink[parentIndex] = lowLink[nodeIndex];
            }
        }
    }
 
    // Condensation: base kept-successors and DAG successors per component.
    std::vector<OrderedSet<const ICFGNode*>> baseKept(componentCount);
    std::vector<OrderedSet<int>> componentSuccessors(componentCount);
    for (int nodeIndex = 0; nodeIndex < removedNodeCount; ++nodeIndex)
    {
        const int componentIndex = component[nodeIndex];
        for (const ICFGNode* keptSuccessor : keptSuccessors[nodeIndex])
            baseKept[componentIndex].insert(keptSuccessor);
        for (int successorIndex : removedSuccessors[nodeIndex])
            if (component[successorIndex] != componentIndex)
                componentSuccessors[componentIndex].insert(
                    component[successorIndex]);
    }
 
    // Propagate reachKept in ascending comp order (successors have smaller ids).
    std::vector<OrderedSet<const ICFGNode*>>
                                          reachableKeptNodes(componentCount);
    for (int componentIndex = 0; componentIndex < componentCount;
            ++componentIndex)
    {
        OrderedSet<const ICFGNode*>& reachable =
            reachableKeptNodes[componentIndex];
        reachable = baseKept[componentIndex];
        for (int successorComponent : componentSuccessors[componentIndex])
            reachable.insert(
                reachableKeptNodes[successorComponent].begin(),
                reachableKeptNodes[successorComponent].end());
    }
 
    // bridgedEdges[u] = kept nodes reached from kept u through removed local paths,
    // plus a matched call->ret summary when u is a seeded call site (kept ret).
    for (const ICFGNode* source : keptNodesSet)
    {
        getLocalSuccessors(source, seedRet, successors);
        const auto seedReturn = seedRet.find(source);
        for (const ICFGNode* successor : successors)
        {
            if (keptNodesSet.count(successor))
            {
                // Kept seed target: no real edge exists, so record the bridge; a
                // kept intra target is a real edge handled by getSuccNodes.
                if (seedReturn != seedRet.end() &&
                        seedReturn->second == successor)
                {
                    bridgedEdges[source].insert(successor);
                    bridgedPreds[successor].insert(source);
                }
                continue;
            }
            const auto removedIndex = removedNodeIndex.find(successor);
            if (removedIndex == removedNodeIndex.end())
            {
                SVFUtil::errs()
                        << "[ERROR] Local ICFG successor is neither kept nor indexed\n";
                std::abort();
            }
            for (const ICFGNode* target :
                    reachableKeptNodes[component[removedIndex->second]])
            {
                bridgedEdges[source].insert(target);
                bridgedPreds[target].insert(source);
            }
        }
    }
 
    size_t totalBridgedEdges = 0;
    for (const auto& pair : bridgedEdges)
        totalBridgedEdges += pair.second.size();
    SVFUtil::outs() << "[SlicedICFGView] Built " << totalBridgedEdges
                    << " bridged edges across " << bridgedEdges.size()
                    << " source nodes\n";
}

buildICFGSets()

void SVF::SlicedICFGView::buildICFGSets ( const OrderedSet< const ICFGNode * > &  keepNodes )

private

Definition at line 319 of file SlicedGraphs.cpp.

{
    keptNodes.clear();
    keptNodes.insert(keepNodes.begin(), keepNodes.end());
 
    // Build keptNodesSet for fast lookup
    keptNodesSet.clear();
    keptNodesSet.insert(keptNodes.begin(), keptNodes.end());
}

dump()

void SVF::SlicedICFGView::dump

(

const std::string &

filename

)

const

Dump sliced ICFG to dot file.

Definition at line 311 of file SlicedGraphs.cpp.

{
    // Kept nodes + kept original edges + bridged edges are all produced by the
    // GenericGraphTraits<const SlicedICFGView*> iterators; GraphWriter styles
    // bridged edges dashed via DOTGraphTraits::getEdgeAttributes.
    GraphPrinter::WriteGraphToFile(SVFUtil::outs(), filename, this);
}

getFunEntry()

const ICFGNode * SVF::SlicedICFGView::getFunEntry

(

const FunObjVar *

fun

)

const

First kept node of fun's entry, or null when fun is outside the view.

Definition at line 883 of file SlicedGraphs.cpp.

{
    // Prefer the kept FunEntryICFGNode: MultiStageSlicer::expandCallDependence keeps it
    // for every kept function and buildBridgedEdges links it to the kept body, so
    // the MHP interleaving fixpoint can flow from it to every kept statement.
    // The entry basic block's first instruction, by contrast, may be sliced out;
    // returning it (a removed node) would strand the root/thread seed there --
    // getSuccNodes() yields nothing for a non-kept node -- so the function body
    // would never receive the thread's interleaving (a soundness bug).
    if (const ICFGNode* fe = icfg->getFunEntryICFGNode(fun))
    {
        if (isKeptNode(fe))
            return fe;
    }
    // A view constructor always retains the synthetic entry. Keep the fallback
    // for defensive compatibility with directly constructed SlicedICFGViews,
    // but never return a node outside this view.
    const ICFGNode* entry = fun->getEntryBlock()->front();
    if (isKeptNode(entry))
        return entry;
    for (const ICFGNode* node : fun->getEntryBlock()->getICFGNodeList())
    {
        if (isKeptNode(node))
            return node;
    }
    return nullptr;
}

getFunExit()

const ICFGNode * SVF::SlicedICFGView::getFunExit

(

const FunObjVar *

fun

)

const

Kept synthetic exit node of fun, or null when fun is outside the view.

Definition at line 911 of file SlicedGraphs.cpp.

{
    const ICFGNode* exit = icfg->getFunExitICFGNode(fun);
    return isKeptNode(exit) ? exit : nullptr;
}

getFunICFGNodes()

void SVF::SlicedICFGView::getFunICFGNodes	(	const FunObjVar *	fun,
		std::vector< const ICFGNode * > &	out
	)		const

Kept ICFG nodes of fun.

Definition at line 917 of file SlicedGraphs.cpp.

{
    out.clear();
    for (auto it : *fun)
    {
        const SVFBasicBlock* svfbb = it.second;
        for (const ICFGNode* node : svfbb->getICFGNodeList())
            if (isKeptNode(node))
                out.push_back(node);
    }
}

getKeptNodes()

const OrderedSet< const ICFGNode * > & SVF::SlicedICFGView::getKeptNodes ( ) const

inline

Get all kept nodes.

Definition at line 84 of file SlicedGraphs.h.

    {
        return keptNodes;
    }

getLocalSuccessors()

void SVF::SlicedICFGView::getLocalSuccessors ( const ICFGNode *  node, const Map< const ICFGNode *, const ICFGNode * > &  callsiteReturnNodes, std::vector< const ICFGNode * > &  successors  )

staticprivate

Definition at line 531 of file SlicedGraphs.cpp.

{
    successors.clear();
    for (const ICFGEdge* edge : node->getOutEdges())
        if (edge != nullptr && SVFUtil::isa<IntraCFGEdge>(edge) &&
                edge->getDstNode() != nullptr)
            successors.push_back(edge->getDstNode());
 
    const auto returnNode = callsiteReturnNodes.find(node);
    if (returnNode != callsiteReturnNodes.end())
        successors.push_back(returnNode->second);
}

getOriginalICFG()

ICFG * SVF::SlicedICFGView::getOriginalICFG ( ) const

inline

Get original ICFG.

Definition at line 106 of file SlicedGraphs.h.

    {
        return icfg;
    }

getPredNodes()

void SVF::SlicedICFGView::getPredNodes	(	const ICFGNode *	node,
		std::vector< const ICFGNode * > &	out
	)		const

Get predecessor nodes (including bridged edges)

Definition at line 292 of file SlicedGraphs.cpp.

{
    out.clear();
    if (!isKeptNode(node))
    {
        return;
    }
    using GT = GenericGraphTraits<Inverse<const SlicedICFGView*>>;
    const SlicedICFGNodeRef n{this, node};
    for (auto it = GT::child_begin(n), e = GT::child_end(n); it != e; ++it)
        out.push_back((*it).raw);
}

getSuccNodes()

void SVF::SlicedICFGView::getSuccNodes	(	const ICFGNode *	node,
		std::vector< const ICFGNode * > &	out
	)		const

Get successor nodes (including bridged edges)

Definition at line 278 of file SlicedGraphs.cpp.

{
    out.clear();
    if (!isKeptNode(node))
    {
        return;
    }
    using GT = GenericGraphTraits<const SlicedICFGView*>;
    const SlicedICFGNodeRef n{this, node};
    for (auto it = GT::child_begin(n), e = GT::child_end(n); it != e; ++it)
        out.push_back((*it).raw);
}

isKeptNode()

bool SVF::SlicedICFGView::isKeptNode

(

const ICFGNode *

node

)

const

Check if a node is in the sliced view.

Definition at line 306 of file SlicedGraphs.cpp.

{
    return keptNodesSet.count(node) > 0;
}

Member Data Documentation

bridgedEdges

Map<const ICFGNode*, OrderedSet<const ICFGNode*> > SVF::SlicedICFGView::bridgedEdges

private

Definition at line 114 of file SlicedGraphs.h.

bridgedPreds

Map<const ICFGNode*, OrderedSet<const ICFGNode*> > SVF::SlicedICFGView::bridgedPreds

private

Definition at line 117 of file SlicedGraphs.h.

icfg

ICFG* SVF::SlicedICFGView::icfg

private

Definition at line 112 of file SlicedGraphs.h.

keptNodes

OrderedSet<const ICFGNode*> SVF::SlicedICFGView::keptNodes

private

Definition at line 113 of file SlicedGraphs.h.

keptNodesSet

Set<const ICFGNode*> SVF::SlicedICFGView::keptNodesSet

private

Definition at line 118 of file SlicedGraphs.h.

---

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

• /home/runner/work/SVF/SVF/svf/include/Graphs/SlicedGraphs.h
• /home/runner/work/SVF/SVF/svf/lib/Graphs/SlicedGraphs.cpp