SVF::CDGBuilder Class Reference

#include <CDGBuilder.h>

Public Member Functions
	CDGBuilder ()
	constructor
	~CDGBuilder ()
	destructor
void	build ()
	start here
void	buildControlDependence (const SVFModule *svfgModule)
	build control dependence for each function
void	buildICFGNodeControlMap ()
	build map at icfg node level

Private Member Functions
void	extractNodesBetweenPdomNodes (const SVFBasicBlock *succ, const SVFBasicBlock *LCA, std::vector< const SVFBasicBlock * > &tgtNodes)
	extract nodes between two nodes in pdom tree
void	dfsNodesBetweenPdomNodes (const SVFBasicBlock *cur, const SVFBasicBlock *tgt, std::vector< const SVFBasicBlock * > &path, std::vector< const SVFBasicBlock * > &tgtNodes, SVFLoopAndDomInfo *ld)
s64_t	getBBSuccessorBranchID (const SVFBasicBlock *BB, const SVFBasicBlock *Succ)
void	updateMap (const SVFBasicBlock *pred, const SVFBasicBlock *bb, s32_t pos)
	update map

Static Private Member Functions
static void	extractBBS (const SVFFunction *func, Map< const SVFBasicBlock *, std::vector< const SVFBasicBlock * > > &res)
	extract basic block edges to be processed

Private Attributes
CDG *	_controlDG
Map< const SVFBasicBlock *, Map< const SVFBasicBlock *, Set< s32_t > > >	_svfcontrolMap
	map a basicblock to its controlling BBs (position, set of BBs)
Map< const SVFBasicBlock *, Map< const SVFBasicBlock *, Set< s32_t > > >	_svfdependentOnMap
	map a basicblock to its dependent on BBs (position, set of BBs)
Map< const ICFGNode *, Map< const ICFGNode *, Set< s32_t > > >	_nodeControlMap
	map an ICFG node to its controlling ICFG nodes (position, set of Nodes)
Map< const ICFGNode *, Map< const ICFGNode *, Set< s32_t > > >	_nodeDependentOnMap
	map an ICFG node to its dependent on ICFG nodes (position, set of Nodes)

Detailed Description

Definition at line 38 of file CDGBuilder.h.

Constructor & Destructor Documentation

CDGBuilder()

SVF::CDGBuilder::CDGBuilder ( )

inline

constructor

Definition at line 43 of file CDGBuilder.h.

                 : _controlDG(CDG::getCDG())
    {
 
    }

~CDGBuilder()

SVF::CDGBuilder::~CDGBuilder ( )

inline

destructor

Definition at line 49 of file CDGBuilder.h.

    {
 
    }

Member Function Documentation

build()

void CDGBuilder::build

(

)

start here

Start here

Definition at line 77 of file CDGBuilder.cpp.

{
    if (_controlDG->getTotalNodeNum() > 0)
        return;
    PAG *pag = PAG::getPAG();
    buildControlDependence(pag->getModule());
    buildICFGNodeControlMap();
}

buildControlDependence()

void CDGBuilder::buildControlDependence

(

const SVFModule *

svfgModule

)

build control dependence for each function

Build control dependence for each function

(1) construct CFG for each function (2) extract basic block edges (pred->succ) on the CFG to be processed succ does not post-dominates pred (!postDT->dominates(succ, pred)) (3) extract nodes from succ to the least common ancestor LCA of pred and succ including LCA if LCA is pred, excluding LCA if LCA is not pred

Parameters

svfgModule

Definition at line 124 of file CDGBuilder.cpp.

{
    CallGraph* svfirCallGraph = PAG::getPAG()->getCallGraph();
    for (const auto& item: *svfirCallGraph)
    {
        const SVFFunction *svfFun = (item.second)->getFunction();
        if (SVFUtil::isExtCall(svfFun)) continue;
        // extract basic block edges to be processed
        Map<const SVFBasicBlock *, std::vector<const SVFBasicBlock *>> BBS;
        extractBBS(svfFun, BBS);
 
        for (const auto &item: BBS)
        {
            const SVFBasicBlock *pred = item.first;
            // for each bb pair
            for (const SVFBasicBlock *succ: item.second)
            {
                const SVFBasicBlock *SVFLCA = const_cast<SVFFunction *>(svfFun)->
                                              getLoopAndDomInfo()->findNearestCommonPDominator(pred, succ);
                std::vector<const SVFBasicBlock *> tgtNodes;
                // no common ancestor, may be exit()
                if (SVFLCA == NULL)
                    tgtNodes.push_back(succ);
                else
                {
                    if (SVFLCA == pred) tgtNodes.push_back(SVFLCA);
                    // from succ to LCA
                    extractNodesBetweenPdomNodes(succ, SVFLCA, tgtNodes);
                }
 
                s64_t pos = getBBSuccessorBranchID(pred, succ);
                for (const SVFBasicBlock *bb: tgtNodes)
                {
                    updateMap(pred, bb, pos);
                }
            }
        }
    }
}

buildICFGNodeControlMap()

void CDGBuilder::buildICFGNodeControlMap

(

)

build map at icfg node level

Build map at ICFG node level

Definition at line 188 of file CDGBuilder.cpp.

{
    for (const auto &it: _svfcontrolMap)
    {
        for (const auto &it2: it.second)
        {
            const SVFBasicBlock *controllingBB = it2.first;
            const ICFGNode *controlNode = it.first->getICFGNodeList().back();
            if (const CallICFGNode* callNode =
                        SVFUtil::dyn_cast<CallICFGNode>(controlNode))
            {
                // not a branch statement:
                //  invoke void %3(ptr noundef nonnull align 8 dereferenceable(8) %1, ptr noundef %2)
                //          to label %invoke.cont1 unwind label %lpad
                controlNode = callNode->getRetICFGNode();
            }
            if (!controlNode) continue;
            // controlNode control at pos
            for (const auto &controllee: controllingBB->getICFGNodeList())
            {
                _nodeControlMap[controlNode][controllee].insert(it2.second.begin(), it2.second.end());
                _nodeDependentOnMap[controllee][controlNode].insert(it2.second.begin(), it2.second.end());
                for (s32_t pos: it2.second)
                {
                    if (const IntraICFGNode* intraNode =
                                dyn_cast<IntraICFGNode>(controlNode))
                    {
                        assert(intraNode->getSVFStmts().size() == 1 &&
                               "not a branch stmt?");
                        const SVFVar* condition =
                            SVFUtil::cast<BranchStmt>(
                                intraNode->getSVFStmts().front())
                            ->getCondition();
                        _controlDG->addCDGEdgeFromSrcDst(controlNode, controllee,
                                                         condition,
                                                         pos);
                    }
                    else
                    {
                        // not a branch statement:
                        //  invoke void %3(ptr noundef nonnull align 8 dereferenceable(8) %1, ptr noundef %2)
                        //          to label %invoke.cont1 unwind label %lpad
                        SVFIR* pag = PAG::getPAG();
                        _controlDG->addCDGEdgeFromSrcDst(
                            controlNode, controllee,
                            pag->getGNode(pag->getNullPtr()), pos);
                    }
 
                }
            }
        }
    }
}

dfsNodesBetweenPdomNodes()

void CDGBuilder::dfsNodesBetweenPdomNodes ( const SVFBasicBlock *  cur, const SVFBasicBlock *  tgt, std::vector< const SVFBasicBlock * > &  path, std::vector< const SVFBasicBlock * > &  tgtNodes, SVFLoopAndDomInfo *  ld  )

private

Definition at line 35 of file CDGBuilder.cpp.

{
    path.push_back(cur);
    if (cur == tgt)
    {
        tgtNodes.insert(tgtNodes.end(), path.begin() + 1, path.end());
    }
    else
    {
        auto it = ld->getPostDomTreeMap().find(cur);
        for (const auto &nxt: it->second)
        {
            dfsNodesBetweenPdomNodes(nxt, tgt, path, tgtNodes, ld);
        }
    }
    path.pop_back();
}

extractBBS()

void CDGBuilder::extractBBS ( const SVFFunction *  func, Map< const SVFBasicBlock *, std::vector< const SVFBasicBlock * > > &  res  )

staticprivate

extract basic block edges to be processed

(2) extract basic block edges on the CFG (pred->succ) to be processed succ does not post-dominates pred (!postDT->dominates(succ, pred))

Parameters

func
res

Definition at line 171 of file CDGBuilder.cpp.

{
    for (const auto &bb: *func)
    {
        for (const auto &succ: bb->getSuccessors())
        {
            if (func->postDominate(succ, bb))
                continue;
            res[bb].push_back(succ);
        }
    }
}

extractNodesBetweenPdomNodes()

void CDGBuilder::extractNodesBetweenPdomNodes ( const SVFBasicBlock *  succ, const SVFBasicBlock *  LCA, std::vector< const SVFBasicBlock * > &  tgtNodes  )

private

extract nodes between two nodes in pdom tree

(3) extract nodes from succ to the least common ancestor LCA of pred and succ including LCA if LCA is pred, excluding LCA if LCA is not pred

Parameters

succ
LCA
tgtNodes

Definition at line 65 of file CDGBuilder.cpp.

{
    if (succ == LCA) return;
    std::vector<const SVFBasicBlock *> path;
    SVFLoopAndDomInfo *ld = const_cast<SVFFunction *>(LCA->getFunction())->getLoopAndDomInfo();
    dfsNodesBetweenPdomNodes(LCA, succ, path, tgtNodes, ld);
}

getBBSuccessorBranchID()

s64_t CDGBuilder::getBBSuccessorBranchID ( const SVFBasicBlock *  BB, const SVFBasicBlock *  Succ  )

private

Definition at line 87 of file CDGBuilder.cpp.

{
    ICFG *icfg = PAG::getPAG()->getICFG();
    assert(!BB->getICFGNodeList().empty() && "empty bb?");
    const ICFGNode *pred = BB->back();
    if (const CallICFGNode* callNode = dyn_cast<CallICFGNode>(pred))
    {
        // not a branch statement:
        //  invoke void %3(ptr noundef nonnull align 8 dereferenceable(8) %1, ptr noundef %2)
        //          to label %invoke.cont1 unwind label %lpad
        pred = callNode->getRetICFGNode();
    }
    const ICFGEdge *edge = icfg->getICFGEdge(pred, Succ->front(), ICFGEdge::ICFGEdgeK::IntraCF);
    if (const IntraCFGEdge *intraEdge = SVFUtil::dyn_cast<IntraCFGEdge>(edge))
    {
        if(intraEdge->getCondition())
            return intraEdge->getSuccessorCondValue();
        else
            return 0;
    }
    else
    {
        assert(false && "not intra edge?");
        abort();
    }
}

updateMap()

void SVF::CDGBuilder::updateMap ( const SVFBasicBlock *  pred, const SVFBasicBlock *  bb, s32_t  pos  )

inlineprivate

update map

Definition at line 90 of file CDGBuilder.h.

    {
        _svfcontrolMap[pred][bb].insert(pos);
        _svfdependentOnMap[bb][pred].insert(pos);
    }

Member Data Documentation

_controlDG

CDG* SVF::CDGBuilder::_controlDG

private

Definition at line 98 of file CDGBuilder.h.

_nodeControlMap

Map<const ICFGNode *, Map<const ICFGNode *, Set<s32_t> > > SVF::CDGBuilder::_nodeControlMap

private

map an ICFG node to its controlling ICFG nodes (position, set of Nodes)

Definition at line 101 of file CDGBuilder.h.

_nodeDependentOnMap

Map<const ICFGNode *, Map<const ICFGNode *, Set<s32_t> > > SVF::CDGBuilder::_nodeDependentOnMap

private

map an ICFG node to its dependent on ICFG nodes (position, set of Nodes)

Definition at line 102 of file CDGBuilder.h.

_svfcontrolMap

Map<const SVFBasicBlock *, Map<const SVFBasicBlock *, Set<s32_t> > > SVF::CDGBuilder::_svfcontrolMap

private

map a basicblock to its controlling BBs (position, set of BBs)

Definition at line 99 of file CDGBuilder.h.

_svfdependentOnMap

Map<const SVFBasicBlock *, Map<const SVFBasicBlock *, Set<s32_t> > > SVF::CDGBuilder::_svfdependentOnMap

private

map a basicblock to its dependent on BBs (position, set of BBs)

Definition at line 100 of file CDGBuilder.h.

---

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

• /home/runner/work/SVF/SVF/svf/include/Util/CDGBuilder.h
• /home/runner/work/SVF/SVF/svf/lib/Util/CDGBuilder.cpp