SVF::SlicedICFGView Class Reference

#include <SlicedGraphs.h>

Public Member Functions
	SlicedICFGView (ICFG *icfg, CallGraph *cg, const OrderedSet< const ICFGNode * > &keepNodes, const OrderedSet< const FunObjVar * > &keptFunctions, bool buildBridged=true)
	Build complete ICFG view from keepNodes and keptFunctions.
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
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, const OrderedSet< const FunObjVar * > &keptFunctions)
void	buildBridgedEdges ()

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

Detailed Description

Definition at line 66 of file SlicedGraphs.h.

Constructor & Destructor Documentation

SlicedICFGView()

SVF::SlicedICFGView::SlicedICFGView	(	ICFG *	icfg,
		CallGraph *	cg,
		const OrderedSet< const ICFGNode * > &	keepNodes,
		const OrderedSet< const FunObjVar * > &	keptFunctions,
		bool	buildBridged = true
	)

Build complete ICFG view from keepNodes and keptFunctions.

Definition at line 252 of file SlicedGraphs.cpp.

    : icfg(icfg)
{
    buildICFGSets(keepNodes, keptFunctions);
    if (buildBridged)
        buildBridgedEdges();
}

Member Function Documentation

bridgedPredsOf()

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

inline

Definition at line 107 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 102 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 334 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> rid;
    for (ICFG::iterator it = icfg->begin(), eit = icfg->end(); it != eit; ++it)
    {
        const ICFGNode* n = it->second;
        if (n == nullptr || keptNodesSet.count(n)) continue;
        rid[n] = static_cast<int>(removed.size());
        removed.push_back(n);
    }
    const int R = 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* e : call->getOutEdges())
            if (e && SVFUtil::isa<CallCFGEdge>(e) && keptNodesSet.count(e->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.
    auto localSuccs = [&](const ICFGNode* n, std::vector<const ICFGNode*>& out)
    {
        out.clear();
        for (const ICFGEdge* e : n->getOutEdges())
            if (e && SVFUtil::isa<IntraCFGEdge>(e) && e->getDstNode())
                out.push_back(e->getDstNode());
        auto sit = seedRet.find(n);
        if (sit != seedRet.end()) out.push_back(sit->second);
    };
 
    std::vector<std::vector<int>> radj(R);                 // removed -> removed succ ids
    std::vector<std::vector<const ICFGNode*>> keptSucc(R);  // removed -> kept succs
    std::vector<const ICFGNode*> succs;
    for (int i = 0; i < R; ++i)
    {
        localSuccs(removed[i], succs);
        for (const ICFGNode* d : succs)
        {
            if (keptNodesSet.count(d)) keptSucc[i].push_back(d);
            else radj[i].push_back(rid[d]);
        }
    }
 
    // 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> idx(R, -1), low(R, 0), comp(R, -1);
    std::vector<char> onstk(R, 0);
    std::vector<int> tstk;
    int counter = 0, ncomp = 0;
    for (int s0 = 0; s0 < R; ++s0)
    {
        if (idx[s0] != -1) continue;
        std::vector<std::pair<int, size_t>> work;
        work.emplace_back(s0, 0);
        while (!work.empty())
        {
            int v = work.back().first;
            size_t& pi = work.back().second;
            if (pi == 0)
            {
                idx[v] = low[v] = counter++;
                tstk.push_back(v);
                onstk[v] = 1;
            }
            bool descend = false;
            while (pi < radj[v].size())
            {
                int w = radj[v][pi++];
                if (idx[w] == -1)
                {
                    work.emplace_back(w, 0);
                    descend = true;
                    break;
                }
                else if (onstk[w] && idx[w] < low[v]) low[v] = idx[w];
            }
            if (descend) continue;
            if (low[v] == idx[v])
            {
                while (true)
                {
                    int w = tstk.back();
                    tstk.pop_back();
                    onstk[w] = 0;
                    comp[w] = ncomp;
                    if (w == v) break;
                }
                ++ncomp;
            }
            work.pop_back();
            if (!work.empty())
            {
                int p = work.back().first;
                if (low[v] < low[p]) low[p] = low[v];
            }
        }
    }
 
    // Condensation: base kept-successors and DAG successors per component.
    std::vector<OrderedSet<const ICFGNode*>> baseKept(ncomp);
    std::vector<OrderedSet<int>> dagSucc(ncomp);
    for (int i = 0; i < R; ++i)
    {
        int ci = comp[i];
        for (const ICFGNode* k : keptSucc[i]) baseKept[ci].insert(k);
        for (int j : radj[i]) if (comp[j] != ci) dagSucc[ci].insert(comp[j]);
    }
 
    // Propagate reachKept in ascending comp order (successors have smaller ids).
    std::vector<OrderedSet<const ICFGNode*>> reachKept(ncomp);
    for (int c = 0; c < ncomp; ++c)
    {
        OrderedSet<const ICFGNode*>& acc = reachKept[c];
        acc = baseKept[c];
        for (int d : dagSucc[c]) acc.insert(reachKept[d].begin(), reachKept[d].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* u : keptNodesSet)
    {
        localSuccs(u, succs);
        auto sit = seedRet.find(u);
        for (const ICFGNode* s : succs)
        {
            if (keptNodesSet.count(s))
            {
                // Kept seed target: no real edge exists, so record the bridge; a
                // kept intra target is a real edge handled by getSuccNodes.
                if (sit != seedRet.end() && sit->second == s)
                {
                    bridgedEdges[u].insert(s);
                    bridgedPreds[s].insert(u);
                }
                continue;
            }
            for (const ICFGNode* v : reachKept[comp[rid[s]]])
            {
                bridgedEdges[u].insert(v);
                bridgedPreds[v].insert(u);
            }
        }
    }
 
    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, const OrderedSet< const FunObjVar * > &  keptFunctions  )

private

Definition at line 306 of file SlicedGraphs.cpp.

{
    // keepNodes already includes all necessary nodes (call/ret nodes and entry/exit nodes)
    // so we just need to copy them and build edges.
 
    // Copy keepNodes to keptNodes
    keptNodes.clear();
    keptNodes.insert(keepNodes.begin(), keepNodes.end());
 
    // Build keptNodesSet for fast lookup
    keptNodesSet.clear();
    keptNodesSet.insert(keptNodes.begin(), keptNodes.end());
 
    // Build edges: only when both src and dst are in keptNodes
    keptEdges.clear();
    for (const ICFGNode* node : keptNodes)
    {
        for (const ICFGEdge* edge : node->getOutEdges())
        {
            if (edge && keptNodesSet.count(edge->getDstNode()))
            {
                keptEdges.insert(edge);
            }
        }
    }
}

dump()

void SVF::SlicedICFGView::dump

(

const std::string &

filename

)

const

Dump sliced ICFG to dot file.

Definition at line 298 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 (the kept FunEntryICFGNode, else the first kept node of the entry block, else the original entry).

Definition at line 788 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;
    }
    // Otherwise: first kept node in the entry block, or the original entry.
    const ICFGNode* entry = fun->getEntryBlock()->front();
    if (isKeptNode(entry))
        return entry;
    for (const ICFGNode* node : fun->getEntryBlock()->getICFGNodeList())
    {
        if (isKeptNode(node))
            return node;
    }
    return entry;
}

getFunICFGNodes()

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

Kept ICFG nodes of fun.

Definition at line 814 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 95 of file SlicedGraphs.h.

    {
        return keptNodes;
    }

getOriginalICFG()

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

inline

Get original ICFG.

Definition at line 117 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 280 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 267 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 293 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 126 of file SlicedGraphs.h.

bridgedPreds

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

private

Definition at line 129 of file SlicedGraphs.h.

icfg

ICFG* SVF::SlicedICFGView::icfg

private

Definition at line 123 of file SlicedGraphs.h.

keptEdges

OrderedSet<const ICFGEdge*> SVF::SlicedICFGView::keptEdges

private

Definition at line 125 of file SlicedGraphs.h.

keptNodes

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

private

Definition at line 124 of file SlicedGraphs.h.

keptNodesSet

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

private

Definition at line 130 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