SVF::SparseObjGraph Class Reference

#include <SparseObjGraph.h>

Inheritance diagram for SVF::SparseObjGraph:

Public Types
typedef SparseObjNode	Node
typedef SparseObjEdge	Edge
Public Types inherited from SVF::GenericGraph< SparseObjNode, SparseObjEdge >
typedef SparseObjNode	NodeType
typedef SparseObjEdge	EdgeType
typedef OrderedMap< NodeID, NodeType * >	IDToNodeMapTy
	NodeID to GenericNode map.
typedef IDToNodeMapTy::iterator	iterator
	Node Iterators.
typedef IDToNodeMapTy::const_iterator	const_iterator

Public Member Functions
	SparseObjGraph (const SVFG &svfg, ICFG &icfg, PointerAnalysis &pta, const SVFIR &svfir)
	Construction uses static graphs and points-to results, not AE state.
	SparseObjGraph (const SparseObjGraph &)=delete
SparseObjGraph &	operator= (const SparseObjGraph &)=delete
const std::vector< const Edge * > &	getInputs (const ICFGNode *node) const
	Return incoming edges at this ICFG location for client-side value flow.
std::string	toString () const
	Describe the static nodes and edges as text, without AE values.
void	dump (const std::string &file)
	Write a DOT graph to <file>.dot through GraphPrinter.
Public Member Functions inherited from SVF::GenericGraph< SparseObjNode, SparseObjEdge >
	GenericGraph ()
	Constructor.
virtual	~GenericGraph ()
	Destructor.
void	destroy ()
	Release memory.
iterator	begin ()
	Iterators.
iterator	end ()
const_iterator	begin () const
const_iterator	end () const
void	addGNode (NodeID id, NodeType *node)
	Add a Node.
NodeType *	getGNode (NodeID id) const
	Get a node.
bool	hasGNode (NodeID id) const
	Has a node.
void	removeGNode (NodeType *node)
	Delete a node.
u32_t	getTotalNodeNum () const
	Get total number of node/edge.
u32_t	getTotalEdgeNum () const
void	incNodeNum ()
	Increase number of node/edge.
void	incEdgeNum ()

Private Member Functions
bool	isBranch (const ICFGNode *node) const
Node *	getOrCreateBaseObjNode (NodeID baseObjId, const ICFGNode *location)
Node *	getBranchNode (NodeID base, const IntraCFGEdge *branch)
void	addRouteEdge (Node *source, Node *target)
void	addEdge (NodeID base, const ICFGNode *source, const ICFGNode *target, const IntraCFGEdge *branch)
void	connectFrom (NodeID base, const ICFGNode *source, const Set< const ICFGNode * > &events, Set< const ICFGNode * > &newSources)

Private Attributes
ICFG &	icfg
Map< NodeID, Map< const ICFGNode *, Node * > >	groupNodes
	Normal nodes are unique by (base, ICFG location); branch nodes by edge.
Map< NodeID, Map< const IntraCFGEdge *, Node * > >	branchNodes
Map< const ICFGNode *, std::vector< const Edge * > >	inputs
Map< const ICFGNode *, Set< NodeID > >	returnedGroups
Map< const ICFGNode *, Map< const FunObjVar *, Set< NodeID > > >	returnedGroupsByCallee

Additional Inherited Members
Public Attributes inherited from SVF::GenericGraph< SparseObjNode, SparseObjEdge >
u32_t	edgeNum
	total num of node
u32_t	nodeNum
	total num of edge
Protected Attributes inherited from SVF::GenericGraph< SparseObjNode, SparseObjEdge >
IDToNodeMapTy	IDToNodeMap
	node map

Detailed Description

Prebuild Obj routes from SVFG object information and ICFG order. Fields and array elements of the same base are packed on one route: D: a[0] = 1; S: a[1] = 7; N: use(a[0]); Program order gives D -> S -> N, rather than two independent packed inputs from D and S. A branch edge gets a synthetic node, but the graph neither computes nor stores intervals; clients check feasibility and refine values.

Definition at line 60 of file SparseObjGraph.h.

Member Typedef Documentation

Edge

typedef SparseObjEdge SVF::SparseObjGraph::Edge

Definition at line 64 of file SparseObjGraph.h.

Node

typedef SparseObjNode SVF::SparseObjGraph::Node

Definition at line 63 of file SparseObjGraph.h.

Constructor & Destructor Documentation

SparseObjGraph() [1/2]

SparseObjGraph::SparseObjGraph	(	const SVFG &	svfg,
		ICFG &	icfg,
		PointerAnalysis &	pta,
		const SVFIR &	svfir )

Construction uses static graphs and points-to results, not AE state.

Definition at line 30 of file SparseObjGraph.cpp.

                                                                         : icfg(graph)
{
    //Step 1 collect key: All base Obj ID, value: all def-use sites related to the base id
    Map<NodeID, Set<const ICFGNode*>> eventsByBase;
    for (auto it = svfg.begin(); it != svfg.end(); ++it)
    {
        const VFGNode* vfg = it->second;
        const ICFGNode* location = vfg->getICFGNode();
        // Only in-function SVFG nodes participate here; global entry routes
        // are connected below.
        if (location && location->getFun())
        {
            // An indirect call edge identifies the packed Obj passed to the
            // callee: C: f(&x) -> P: callee entry. Register both C and P as
            // events for x so intra-function routing stops and resumes there;
            // addEdge connects the interprocedural C -> P edge separately.
            for (const VFGEdge* edge : vfg->getInEdges())
            {
                if (const auto* call = SVFUtil::dyn_cast<CallIndSVFGEdge>(edge))
                {
                    const ICFGNode* caller = call->getSrcNode()->getICFGNode();
                    if (caller)
                    {
                        for (NodeID obj : call->getPointsTo())
                        {
                            if (!svfir.isNullOrBlkObj(obj))
                            {
                                const NodeID base = svfir.getBaseObject(obj)->getId();
                                eventsByBase[base].insert(caller);
                                eventsByBase[base].insert(location);
                                addEdge(base, caller, location, nullptr);
                            }
                        }
                    }
                }
            }
 
            // MRSVFGNode already supplies points-to objects. Group each by
            // base without modifying the SVFG or strong/weak update rules.
            const ValVar* pointer = nullptr;
            if (const auto* memory = SVFUtil::dyn_cast<MRSVFGNode>(vfg))
            {
                for (NodeID obj : memory->getPointsTo())
                {
                    if (!svfir.isNullOrBlkObj(obj))
                    {
                        const NodeID base = svfir.getBaseObject(obj)->getId();
                        eventsByBase[base].insert(location);
                        getOrCreateBaseObjNode(base, location);
                    }
                }
            }
            else if (const auto* store = SVFUtil::dyn_cast<StoreVFGNode>(vfg))
                pointer = store->getLHSVar();
            else if (const auto* load = SVFUtil::dyn_cast<LoadVFGNode>(vfg))
                pointer = load->getRHSVar();
 
            // Resolve ordinary load/store targets with points-to analysis.
            // If p points to a[1], record a's base so a[0] and a[1] travel
            // through this location as one packed Obj.
            if (pointer)
            {
                for (NodeID obj : pta.getPts(pointer->getId()))
                {
                    if (!svfir.isNullOrBlkObj(obj))
                    {
                        const NodeID base = svfir.getBaseObject(obj)->getId();
                        eventsByBase[base].insert(location);
                        getOrCreateBaseObjNode(base, location);
                    }
                }
            }
        }
    }
 
    // Step 2: connect callee Obj outputs to the caller return location.
    // For C: f(&x); R: return from the call, a RetIndSVFGEdge for x gives
    // callee-output -> R, where AE can read the computed Obj value.
    for (auto it = icfg.begin(); it != icfg.end(); ++it)
    {
        if (const auto* ret = SVFUtil::dyn_cast<RetICFGNode>(it->second))
        {
            for (const VFGNode* target : ret->getVFGNodes())
            {
                for (const VFGEdge* edge : target->getInEdges())
                {
                    if (const auto* output = SVFUtil::dyn_cast<RetIndSVFGEdge>(edge))
                    {
                        const ICFGNode* source = output->getSrcNode()->getICFGNode();
                        if (source)
                        {
                            for (NodeID obj : output->getPointsTo())
                            {
                                if (!svfir.isNullOrBlkObj(obj))
                                {
                                    const NodeID base = svfir.getBaseObject(obj)->getId();
                                    returnedGroups[ret].insert(base);
                                    if (source->getFun())
                                        returnedGroupsByCallee[ret][source->getFun()].insert(base);
                                    eventsByBase[base].insert(ret);
                                    if (source->getFun())
                                        eventsByBase[base].insert(source);
                                    addEdge(base, source, ret, nullptr);
                                }
                            }
                        }
                    }
                }
            }
        }
    }
 
    // Step 3: connect consecutive Obj events in ICFG order within each function.
    // D: a[0]=1; S: a[1]=7; N: use(a[0]) becomes D -> S -> N.
    // Branches, calls, and returns also stop a route, even if they were not
    // among the initial SVFG events.
    for (const auto& [base, events] : eventsByBase)
    {
        Set<const ICFGNode*> sources = events;
        for (const ICFGNode* event : events)
            sources.insert(icfg.getFunEntryICFGNode(event->getFun()));
 
        // Connect global objects from global initialization to function entries.
        if (svfir.getBaseObject(base)->isGlobalObj())
        {
            const ICFGNode* global = icfg.getGlobalICFGNode();
            for (const ICFGEdge* edge : global->getOutEdges())
            {
                const ICFGNode* entry = edge->getDstNode();
                if (SVFUtil::isa<FunEntryICFGNode>(entry) && sources.count(entry))
                    addEdge(base, global, entry, nullptr);
            }
        }
 
        // Branch/call/return sites found by connectFrom become sources for
        // the next segment. This queue is used only during graph construction.
        std::vector<const ICFGNode*> pending(sources.begin(), sources.end());
        for (size_t i = 0; i < pending.size(); ++i)
        {
            Set<const ICFGNode*> newSources;
            connectFrom(base, pending[i], events, newSources);
            for (const ICFGNode* event : newSources)
            {
                if (sources.insert(event).second)
                    pending.push_back(event);
            }
        }
    }
 
}

SparseObjGraph() [2/2]

SVF::SparseObjGraph::SparseObjGraph ( const SparseObjGraph & )

delete

Member Function Documentation

addEdge()

void SparseObjGraph::addEdge ( NodeID base, const ICFGNode * source, const ICFGNode * target, const IntraCFGEdge * branch )

private

Definition at line 238 of file SparseObjGraph.cpp.

{
    // B: if (z > 0) { use(x); use(z); }, with ordinary loads and no aliasing.
    // For base=z, connectFrom passes source=B, target=N (the z use), and
    // B's true edge. The intervening use(x) adds no z edge. The same route
    // applies when N immediately follows B. inputs[N] records the branch
    // node -> N; AE checks feasibility and refines z when reading that edge.
    Node* from = getOrCreateBaseObjNode(base, source);
    Node* to = getOrCreateBaseObjNode(base, target);
    Node* input = branch ? getBranchNode(base, branch) : from;
    if (branch)
        addRouteEdge(from, input);
    addRouteEdge(input, to);
}

addRouteEdge()

void SparseObjGraph::addRouteEdge ( Node * source, Node * target )

private

Definition at line 221 of file SparseObjGraph.cpp.

{
    Edge candidate(source, target);
    if (source->hasOutgoingEdge(&candidate))
        return;
 
    Edge* edge = new Edge(source, target);
    const bool addedOut = source->addOutgoingEdge(edge);
    const bool addedIn = target->addIncomingEdge(edge);
    assert(addedOut && addedIn);
    (void)addedOut;
    (void)addedIn;
    incEdgeNum();
    if (!target->branch)
        inputs[target->location].push_back(edge);
}

connectFrom()

void SparseObjGraph::connectFrom ( NodeID base, const ICFGNode * source, const Set< const ICFGNode * > & events, Set< const ICFGNode * > & newSources )

private

Definition at line 255 of file SparseObjGraph.cpp.

{
    // From one Obj event, find the next event or control boundary in this
    // function. Feasibility is not checked here, so AE states share the route.
    const FunObjVar* fun = source->getFun();
    if (!fun)
        return;
 
    std::vector<std::pair<const ICFGNode*, const IntraCFGEdge*>> first;
    // inter-procedure
    if (const auto* call = SVFUtil::dyn_cast<CallICFGNode>(source))
    {
        const RetICFGNode* ret = call->getRetICFGNode();
        bool needsCallerToRetEdge = !returnedGroups[ret].count(base);
        for (const ICFGEdge* out : call->getOutEdges())
        {
            const auto* callEdge = SVFUtil::dyn_cast<CallCFGEdge>(out);
            if (callEdge && !returnedGroupsByCallee[ret][out->getDstNode()->getFun()].count(base))
                needsCallerToRetEdge = true;
        }
        // C may call f_write(&x) or f_noop(&x). If a callee has no return
        // edge for x, retain C -> R so that candidate carries the pre-call
        // value; a candidate with a return edge uses callee-output -> R.
        if (needsCallerToRetEdge)
            first.emplace_back(call->getRetICFGNode(), nullptr);
    }
    else
        // intra-procedure
    {
        for (const ICFGEdge* out : source->getOutEdges())
        {
            if (const auto* intra = SVFUtil::dyn_cast<IntraCFGEdge>(out))
                first.emplace_back(intra->getDstNode(),
                                   intra->getCondition() ? intra : nullptr);
        }
    }
 
    for (const auto& [start, branch] : first)
    {
        // Cross ordinary ICFG nodes between events; stop at a branch, call,
        // return, or the next Obj event, which starts another route segment.
        // For base=z: B: if (z > 0) { Ux: use(x); Uz: use(z); }.
        // With ordinary non-aliasing loads, Ux is not a z event; traverse
        // past Ux and call addEdge(z, B, Uz, true edge) at Uz.
        Set<const ICFGNode*> visited;
        std::deque<const ICFGNode*> pending{start};
        while (!pending.empty())
        {
            const ICFGNode* current = pending.front();
            pending.pop_front();
            if (current && current->getFun() == fun &&
                    visited.insert(current).second)
            {
                const bool objSite = events.count(current);
                const bool controlBoundary = isBranch(current) ||
                                             SVFUtil::isa<CallICFGNode>(current) ||
                                             SVFUtil::isa<RetICFGNode>(current);
                if (objSite || controlBoundary)
                {
                    addEdge(base, source, current, branch);
                    if (!objSite)
                        newSources.insert(current);
                }
                else
                {
                    for (const ICFGEdge* out : current->getOutEdges())
                    {
                        if (const auto* intra = SVFUtil::dyn_cast<IntraCFGEdge>(out))
                            pending.push_back(intra->getDstNode());
                    }
                }
            }
        }
    }
}

dump()

void SparseObjGraph::dump

(

const std::string &

file

)

Write a DOT graph to <file>.dot through GraphPrinter.

Definition at line 380 of file SparseObjGraph.cpp.

{
    GraphPrinter::WriteGraphToFile(SVFUtil::outs(), file, this);
}

getBranchNode()

SparseObjGraph::Node * SparseObjGraph::getBranchNode ( NodeID base, const IntraCFGEdge * branch )

private

Definition at line 207 of file SparseObjGraph.cpp.

{
    // B: if (x > 0) -> N: use(x). B's true and false edges have distinct
    // nodes; the nodes store edge identity, not AE's refined interval.
    Node*& node = branchNodes[base][branch];
    if (!node)
    {
        node = new Node(getTotalNodeNum(), base, branch->getSrcNode(), branch);
        addGNode(node->getId(), node);
    }
    return node;
}

getInputs()

const std::vector< const SparseObjGraph::Edge * > & SparseObjGraph::getInputs

(

const ICFGNode *

node

)

const

Return incoming edges at this ICFG location for client-side value flow.

Definition at line 335 of file SparseObjGraph.cpp.

{
    static const std::vector<const Edge*> empty;
    const auto it = inputs.find(node);
    return it == inputs.end() ? empty : it->second;
}

getOrCreateBaseObjNode()

SparseObjGraph::Node * SparseObjGraph::getOrCreateBaseObjNode ( NodeID baseObjId, const ICFGNode * location )

private

Definition at line 194 of file SparseObjGraph.cpp.

{
    // One node per (base, ICFG location) may group several SVFG nodes.
    Node*& node = groupNodes[baseObjId][location];
    if (!node)
    {
        node = new Node(getTotalNodeNum(), baseObjId, location, nullptr);
        addGNode(node->getId(), node);
    }
    return node;
}

isBranch()

bool SparseObjGraph::isBranch ( const ICFGNode * node ) const

private

Definition at line 182 of file SparseObjGraph.cpp.

{
    // Only conditional intra-function ICFG edges count as branches.
    for (const ICFGEdge* out : node->getOutEdges())
    {
        const auto* intra = SVFUtil::dyn_cast<IntraCFGEdge>(out);
        if (intra && intra->getCondition())
            return true;
    }
    return false;
}

operator=()

SparseObjGraph & SVF::SparseObjGraph::operator= ( const SparseObjGraph & )

delete

toString()

std::string SparseObjGraph::toString

(

)

const

Describe the static nodes and edges as text, without AE values.

Definition at line 342 of file SparseObjGraph.cpp.

{
    std::ostringstream out;
    for (const auto& entry : *this)
        out << entry.second->toString() << '\n';
    for (const auto& entry : *this)
        for (const Edge* edge : entry.second->getOutEdges())
            out << edge->toString() << '\n';
    return out.str();
}

Member Data Documentation

branchNodes

Map<NodeID, Map<const IntraCFGEdge*, Node*> > SVF::SparseObjGraph::branchNodes

private

Definition at line 93 of file SparseObjGraph.h.

groupNodes

Map<NodeID, Map<const ICFGNode*, Node*> > SVF::SparseObjGraph::groupNodes

private

Normal nodes are unique by (base, ICFG location); branch nodes by edge.

Definition at line 92 of file SparseObjGraph.h.

icfg

ICFG& SVF::SparseObjGraph::icfg

private

Definition at line 90 of file SparseObjGraph.h.

inputs

Map<const ICFGNode*, std::vector<const Edge*> > SVF::SparseObjGraph::inputs

private

Definition at line 94 of file SparseObjGraph.h.

returnedGroups

Map<const ICFGNode*, Set<NodeID> > SVF::SparseObjGraph::returnedGroups

private

Bases with a callee-output to caller-return SVFG edge. The second map distinguishes callees when deciding whether a multi-target call bypasses.

Definition at line 97 of file SparseObjGraph.h.

returnedGroupsByCallee

Map<const ICFGNode*, Map<const FunObjVar*, Set<NodeID> > > SVF::SparseObjGraph::returnedGroupsByCallee

private

Definition at line 98 of file SparseObjGraph.h.

---

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

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