SVF::DDAPass Class Reference

#include <DDAPass.h>

Public Types
typedef SCCDetection< SVFG * >	SVFGSCC
typedef OrderedSet< const SVFGEdge * >	SVFGEdgeSet
typedef std::vector< PointerAnalysis * >	PTAVector

Public Member Functions
	DDAPass ()
	~DDAPass ()
virtual AliasResult	alias (const SVFValue *V1, const SVFValue *V2)
	Interface expose to users of our pointer analysis, given Value infos. More...
virtual AliasResult	alias (NodeID V1, NodeID V2)
	Interface expose to users of our pointer analysis, given PAGNodes. More...
virtual void	runOnModule (SVFIR *module)
	We start from here. More...
virtual void	selectClient (SVFModule *module)
	Select a client. More...
virtual std::string	getPassName () const
	Pass name. More...

Static Public Attributes
static char	ID = 0
	Pass ID. More...

Private Member Functions
void	printQueryPTS ()
	Print queries' pts. More...
void	runPointerAnalysis (SVFIR *module, u32_t kind)
	Create pointer analysis according to specified kind and analyze the module. More...
void	initCxtInsensitiveEdges (PointerAnalysis *pta, const SVFG *svfg, const SVFGSCC *svfgSCC, SVFGEdgeSet &insensitveEdges)
	Context insensitive Edge for DDA. More...
bool	edgeInSVFGSCC (const SVFGSCC *svfgSCC, const SVFGEdge *edge)
	Return TRUE if this edge is inside a SVFG SCC, i.e., src node and dst node are in the same SCC on the SVFG. More...
bool	edgeInCallGraphSCC (PointerAnalysis *pta, const SVFGEdge *edge)
	Return TRUE if this edge is inside a SVFG SCC, i.e., src node and dst node are in the same SCC on the SVFG. More...
void	collectCxtInsenEdgeForRecur (PointerAnalysis *pta, const SVFG *svfg, SVFGEdgeSet &insensitveEdges)
void	collectCxtInsenEdgeForVFCycle (PointerAnalysis *pta, const SVFG *svfg, const SVFGSCC *svfgSCC, SVFGEdgeSet &insensitveEdges)

Private Attributes
std::unique_ptr< PointerAnalysis >	_pta
	pointer analysis to be executed. More...
DDAClient *	_client
	DDA client used. More...

Detailed Description

Demand-Driven Pointer Analysis. This class performs various pointer analysis on the given module.

Definition at line 46 of file DDAPass.h.

Member Typedef Documentation

PTAVector

typedef std::vector<PointerAnalysis*> SVF::DDAPass::PTAVector

Definition at line 54 of file DDAPass.h.

SVFGEdgeSet

typedef OrderedSet<const SVFGEdge*> SVF::DDAPass::SVFGEdgeSet

Definition at line 53 of file DDAPass.h.

SVFGSCC

typedef SCCDetection<SVFG*> SVF::DDAPass::SVFGSCC

Definition at line 52 of file DDAPass.h.

Constructor & Destructor Documentation

DDAPass()

SVF::DDAPass::DDAPass ( )

inline

Definition at line 56 of file DDAPass.h.

: _pta(nullptr), _client(nullptr) {}

~DDAPass()

DDAPass::~DDAPass

(

)

Definition at line 47 of file DDAPass.cpp.

{
    // _pta->dumpStat();
    if (_client != nullptr)
        delete _client;
}

Member Function Documentation

alias() [1/2]

AliasResult DDAPass::alias ( const SVFValue *  V1, const SVFValue *  V2  )

virtual

Interface expose to users of our pointer analysis, given Value infos.

Return alias results based on our points-to/alias analysis TODO: Need to handle PartialAlias and MustAlias here.

TODO: When this method is invoked during compiler optimizations, the IR used for pointer analysis may been changed, so some Values may not find corresponding SVFIR node. In this case, we only check alias between two Values if they both have SVFIR nodes. Otherwise, MayAlias will be returned.

Definition at line 297 of file DDAPass.cpp.

{
    SVFIR* pag = _pta->getPAG();
 
    if (pag->hasValueNode(V1) && pag->hasValueNode(V2))
    {
        PAGNode* node1 = pag->getGNode(pag->getValueNode(V1));
        if(pag->isValidTopLevelPtr(node1))
            _pta->computeDDAPts(node1->getId());
 
        PAGNode* node2 = pag->getGNode(pag->getValueNode(V2));
        if(pag->isValidTopLevelPtr(node2))
            _pta->computeDDAPts(node2->getId());
 
        return _pta->alias(V1,V2);
    }
 
    return AliasResult::MayAlias;
}

alias() [2/2]

AliasResult DDAPass::alias ( NodeID  V1, NodeID  V2  )

virtual

Interface expose to users of our pointer analysis, given PAGNodes.

Definition at line 281 of file DDAPass.cpp.

{
    SVFIR* pag = _pta->getPAG();
 
    if(pag->isValidTopLevelPtr(pag->getGNode(node1)))
        _pta->computeDDAPts(node1);
 
    if(pag->isValidTopLevelPtr(pag->getGNode(node2)))
        _pta->computeDDAPts(node2);
 
    return _pta->alias(node1,node2);
}

collectCxtInsenEdgeForRecur()

void DDAPass::collectCxtInsenEdgeForRecur ( PointerAnalysis *  pta, const SVFG *  svfg, SVFGEdgeSet &  insensitveEdges  )

private

Mark insensitive edge for function recursions

Definition at line 196 of file DDAPass.cpp.

{
 
    for (SVFG::SVFGNodeIDToNodeMapTy::const_iterator it = svfg->begin(),eit = svfg->end(); it != eit; ++it)
    {
 
        SVFGEdge::SVFGEdgeSetTy::const_iterator edgeIt = it->second->InEdgeBegin();
        SVFGEdge::SVFGEdgeSetTy::const_iterator edgeEit = it->second->InEdgeEnd();
        for (; edgeIt != edgeEit; ++edgeIt)
        {
            const SVFGEdge* edge = *edgeIt;
            if(edge->isCallVFGEdge() || edge->isRetVFGEdge())
            {
                if(edgeInCallGraphSCC(pta,edge))
                    insensitveEdges.insert(edge);
            }
        }
    }
}

collectCxtInsenEdgeForVFCycle()

void DDAPass::collectCxtInsenEdgeForVFCycle ( PointerAnalysis *  pta, const SVFG *  svfg, const SVFGSCC *  svfgSCC, SVFGEdgeSet &  insensitveEdges  )

private

Mark insensitive edge for value-flow cycles

Definition at line 219 of file DDAPass.cpp.

{
 
    OrderedSet<NodePair> insensitvefunPairs;
 
    for (SVFG::SVFGNodeIDToNodeMapTy::const_iterator it = svfg->begin(),eit = svfg->end(); it != eit; ++it)
    {
 
        SVFGEdge::SVFGEdgeSetTy::const_iterator edgeIt = it->second->InEdgeBegin();
        SVFGEdge::SVFGEdgeSetTy::const_iterator edgeEit = it->second->InEdgeEnd();
        for (; edgeIt != edgeEit; ++edgeIt)
        {
            const SVFGEdge* edge = *edgeIt;
            if(edge->isCallVFGEdge() || edge->isRetVFGEdge())
            {
                if(this->edgeInSVFGSCC(svfgSCC,edge))
                {
 
                    const SVFFunction* srcFun = edge->getSrcNode()->getICFGNode()->getFun();
                    const SVFFunction* dstFun = edge->getDstNode()->getICFGNode()->getFun();
 
                    if(srcFun && dstFun)
                    {
                        NodeID src = pta->getCallGraph()->getCallGraphNode(srcFun)->getId();
                        NodeID dst = pta->getCallGraph()->getCallGraphNode(dstFun)->getId();
                        insensitvefunPairs.insert(std::make_pair(src,dst));
                        insensitvefunPairs.insert(std::make_pair(dst,src));
                    }
                    else
                        assert(edge->isRetVFGEdge() == false && "should not be an inter-procedural return edge" );
                }
            }
        }
    }
 
    for(SVFG::SVFGNodeIDToNodeMapTy::const_iterator it = svfg->begin(),eit = svfg->end(); it != eit; ++it)
    {
        SVFGEdge::SVFGEdgeSetTy::const_iterator edgeIt = it->second->InEdgeBegin();
        SVFGEdge::SVFGEdgeSetTy::const_iterator edgeEit = it->second->InEdgeEnd();
        for (; edgeIt != edgeEit; ++edgeIt)
        {
            const SVFGEdge* edge = *edgeIt;
 
            if(edge->isCallVFGEdge() || edge->isRetVFGEdge())
            {
                const SVFFunction* srcFun = edge->getSrcNode()->getICFGNode()->getFun();
                const SVFFunction* dstFun = edge->getDstNode()->getICFGNode()->getFun();
 
                if(srcFun && dstFun)
                {
                    NodeID src = pta->getCallGraph()->getCallGraphNode(srcFun)->getId();
                    NodeID dst = pta->getCallGraph()->getCallGraphNode(dstFun)->getId();
                    if(insensitvefunPairs.find(std::make_pair(src,dst))!=insensitvefunPairs.end())
                        insensitveEdges.insert(edge);
                    else if(insensitvefunPairs.find(std::make_pair(dst,src))!=insensitvefunPairs.end())
                        insensitveEdges.insert(edge);
                }
            }
        }
    }
}

edgeInCallGraphSCC()

bool DDAPass::edgeInCallGraphSCC ( PointerAnalysis *  pta, const SVFGEdge *  edge  )

private

Return TRUE if this edge is inside a SVFG SCC, i.e., src node and dst node are in the same SCC on the SVFG.

Whether call graph edge in SVFG SCC

Definition at line 178 of file DDAPass.cpp.

{
    const SVFFunction* srcFun = edge->getSrcNode()->getICFGNode()->getFun();
    const SVFFunction* dstFun = edge->getDstNode()->getICFGNode()->getFun();
 
    if(srcFun && dstFun)
    {
        return pta->inSameCallGraphSCC(srcFun,dstFun);
    }
 
    assert(edge->isRetVFGEdge() == false && "should not be an inter-procedural return edge" );
 
    return false;
}

edgeInSVFGSCC()

bool DDAPass::edgeInSVFGSCC ( const SVFGSCC *  svfgSCC, const SVFGEdge *  edge  )

private

Return TRUE if this edge is inside a SVFG SCC, i.e., src node and dst node are in the same SCC on the SVFG.

Whether SVFG edge in a SCC cycle

Definition at line 170 of file DDAPass.cpp.

{
    return (svfgSCC->repNode(edge->getSrcID()) == svfgSCC->repNode(edge->getDstID()));
}

getPassName()

virtual std::string SVF::DDAPass::getPassName ( ) const

inlinevirtual

Pass name.

Definition at line 72 of file DDAPass.h.

    {
        return "DDAPass";
    }

initCxtInsensitiveEdges()

void DDAPass::initCxtInsensitiveEdges ( PointerAnalysis *  pta, const SVFG *  svfg, const SVFGSCC *  svfgSCC, SVFGEdgeSet &  insensitveEdges  )

private

Context insensitive Edge for DDA.

Initialize context insensitive Edge for DDA

Definition at line 159 of file DDAPass.cpp.

{
    if(Options::InsenRecur())
        collectCxtInsenEdgeForRecur(pta,svfg,insensitveEdges);
    else if(Options::InsenCycle())
        collectCxtInsenEdgeForVFCycle(pta,svfg,svfgSCC,insensitveEdges);
}

printQueryPTS()

void DDAPass::printQueryPTS ( )

private

Print queries' pts.

Print queries' pts

Definition at line 325 of file DDAPass.cpp.

{
    const OrderedNodeSet& candidates = _client->getCandidateQueries();
    for (OrderedNodeSet::const_iterator it = candidates.begin(), eit = candidates.end(); it != eit; ++it)
    {
        const PointsTo& pts = _pta->getPts(*it);
        _pta->dumpPts(*it,pts);
    }
}

runOnModule()

void DDAPass::runOnModule ( SVFIR *  module )

virtual

We start from here.

initialization for llvm alias analyzer

Definition at line 55 of file DDAPass.cpp.

{
    //InitializeAliasAnalysis(this, getDataLayout(&module));
 
    selectClient(pag->getModule());
 
    for (u32_t i = PointerAnalysis::FlowS_DDA;
            i < PointerAnalysis::Default_PTA; i++)
    {
        PointerAnalysis::PTATY iPtTy = static_cast<PointerAnalysis::PTATY>(i);
        if (Options::DDASelected(iPtTy))
            runPointerAnalysis(pag, i);
    }
}

runPointerAnalysis()

void DDAPass::runPointerAnalysis ( SVFIR *  module, u32_t  kind  )

private

Create pointer analysis according to specified kind and analyze the module.

Initialize pointer analysis.

initialize

compute points-to

finalize

Definition at line 108 of file DDAPass.cpp.

{
 
    ContextCond::setMaxPathLen(Options::MaxPathLen());
    ContextCond::setMaxCxtLen(Options::MaxContextLen());
 
    switch (kind)
    {
    case PointerAnalysis::Cxt_DDA:
    {
        _pta = std::make_unique<ContextDDA>(pag, _client);
        break;
    }
    case PointerAnalysis::FlowS_DDA:
    {
        _pta = std::make_unique<FlowDDA>(pag, _client);
        break;
    }
    default:
        outs() << "This pointer analysis has not been implemented yet.\n";
        break;
    }
 
    if(Options::WPANum())
    {
        _client->collectWPANum(pag->getModule());
    }
    else
    {
        _pta->initialize();
        _client->answerQueries(_pta.get());
        _pta->finalize();
        if(Options::PrintCPts())
            _pta->dumpCPts();
 
        if (_pta->printStat())
            _client->performStat(_pta.get());
 
        if (Options::PrintQueryPts())
            printQueryPTS();
    }
}

selectClient()

void DDAPass::selectClient ( SVFModule *  module )

virtual

Select a client.

select a client to initialize queries

solve function pointer

allow user specify queries

Definition at line 72 of file DDAPass.cpp.

{
 
    if (!Options::UserInputQuery().empty())
    {
        if (Options::UserInputQuery() == "funptr")
        {
            _client = new FunptrDDAClient(module);
        }
        else if (Options::UserInputQuery() == "alias")
        {
            _client = new AliasDDAClient(module);
        }
        else
        {
            _client = new DDAClient(module);
            if (Options::UserInputQuery() != "all")
            {
                u32_t buf; // Have a buffer
                stringstream ss(Options::UserInputQuery()); // Insert the user input string into a stream
                while (ss >> buf)
                    _client->setQuery(buf);
            }
        }
    }
    else
    {
        assert(false && "Please specify query options!");
    }
 
    _client->initialise(module);
}

Member Data Documentation

_client

DDAClient* SVF::DDAPass::_client

private

DDA client used.

Definition at line 93 of file DDAPass.h.

_pta

std::unique_ptr<PointerAnalysis> SVF::DDAPass::_pta

private

pointer analysis to be executed.

Definition at line 92 of file DDAPass.h.

ID

char DDAPass::ID = 0

static

Pass ID.

Definition at line 51 of file DDAPass.h.

---

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

• /home/runner/work/SVF/SVF/svf/include/DDA/DDAPass.h
• /home/runner/work/SVF/SVF/svf/lib/DDA/DDAPass.cpp