DDAPass.cpp

Go to the documentation of this file.

//===- DDAPass.cpp -- Demand-driven analysis driver pass-------------//
//
//                     SVF: Static Value-Flow Analysis
//
// Copyright (C) <2013->  <Yulei Sui>
//
 
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU Affero General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
 
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU Affero General Public License for more details.
 
// You should have received a copy of the GNU Affero General Public License
// along with this program.  If not, see <http://www.gnu.org/licenses/>.
//
//===----------------------------------------------------------------------===//
 
 
/*
 * @file: DDAPass.cpp
 * @author: Yulei Sui
 * @date: 01/07/2014
 */
 
 
#include "Util/Options.h"
#include "MemoryModel/PointerAnalysis.h"
#include "DDA/DDAPass.h"
#include "DDA/FlowDDA.h"
#include "DDA/ContextDDA.h"
#include "DDA/DDAClient.h"
 
#include <sstream>
#include <limits.h>
 
using namespace SVF;
using namespace SVFUtil;
using namespace std;
 
char DDAPass::ID = 0;
 
DDAPass::~DDAPass()
{
    // _pta->dumpStat();
    if (_client != nullptr)
        delete _client;
}
 
 
void DDAPass::runOnModule(SVFIR* pag)
{
    //InitializeAliasAnalysis(this, getDataLayout(&module));
 
    selectClient();
 
    for (u32_t i = PTATY::FlowS_DDA; i < PTATY::Default_PTA; i++)
    {
        PTATY iPtTy = static_cast<PTATY>(i);
        if (Options::DDASelected(iPtTy))
            runPointerAnalysis(pag, i);
    }
}

void DDAPass::selectClient()
{
 
    if (!Options::UserInputQuery().empty())
    {
        if (Options::UserInputQuery() == "funptr")
        {
            _client = new FunptrDDAClient();
        }
        else if (Options::UserInputQuery() == "alias")
        {
            _client = new AliasDDAClient();
        }
        else
        {
            _client = new DDAClient();
            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();
}

void DDAPass::runPointerAnalysis(SVFIR* pag, u32_t kind)
{
 
    ContextCond::setMaxPathLen(Options::MaxPathLen());
    ContextCond::setMaxCxtLen(Options::MaxContextLen());

    switch (kind)
    {
    case PTATY::Cxt_DDA:
    {
        _pta = std::make_unique<ContextDDA>(pag, _client);
        break;
    }
    case PTATY::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();
    }
    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();
    }
}
 

void DDAPass::initCxtInsensitiveEdges(PointerAnalysis* pta, const SVFG* svfg,const SVFGSCC* svfgSCC, SVFGEdgeSet& insensitveEdges)
{
    if(Options::InsenRecur())
        collectCxtInsenEdgeForRecur(pta,svfg,insensitveEdges);
    else if(Options::InsenCycle())
        collectCxtInsenEdgeForVFCycle(pta,svfg,svfgSCC,insensitveEdges);
}

bool DDAPass::edgeInSVFGSCC(const SVFGSCC* svfgSCC,const SVFGEdge* edge)
{
    return (svfgSCC->repNode(edge->getSrcID()) == svfgSCC->repNode(edge->getDstID()));
}

bool DDAPass::edgeInCallGraphSCC(PointerAnalysis* pta,const SVFGEdge* edge)
{
    const FunObjVar* srcFun = edge->getSrcNode()->getICFGNode()->getFun();
    const FunObjVar* 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;
}

void DDAPass::collectCxtInsenEdgeForRecur(PointerAnalysis* pta, const SVFG* svfg,SVFGEdgeSet& insensitveEdges)
{
 
    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);
            }
        }
    }
}

void DDAPass::collectCxtInsenEdgeForVFCycle(PointerAnalysis* pta, const SVFG* svfg,const SVFGSCC* svfgSCC, SVFGEdgeSet& insensitveEdges)
{
 
    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 FunObjVar* srcFun = edge->getSrcNode()->getICFGNode()->getFun();
                    const FunObjVar* 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 FunObjVar* srcFun = edge->getSrcNode()->getICFGNode()->getFun();
                const FunObjVar* 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);
                }
            }
        }
    }
}
 
AliasResult DDAPass::alias(NodeID node1, NodeID node2)
{
    SVFIR* pag = _pta->getPAG();
 
    if(pag->isValidTopLevelPtr(pag->getSVFVar(node1)))
        _pta->computeDDAPts(node1);
 
    if(pag->isValidTopLevelPtr(pag->getSVFVar(node2)))
        _pta->computeDDAPts(node2);
 
    return _pta->alias(node1,node2);
}
 

void DDAPass::printQueryPTS()
{
    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);
    }
}