SVFGOPT.h

Go to the documentation of this file.

//===- SVFGOPT.h -- SVFG optimizer--------------------------------------------//
//
//                     SVF: Static Value-Flow Analysis
//
// Copyright (C) <2013-2017>  <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: SVFGOPT.h
 * @author: yesen
 * @date: 20/03/2014
 * @version: 1.0
 *
 * @section LICENSE
 *
 * @section DESCRIPTION
 *
 */
 
 
#ifndef SVFGOPT_H_
#define SVFGOPT_H_
 
 
#include "Graphs/SVFG.h"
#include "Util/WorkList.h"
 
namespace SVF
{

class SVFGOPT : public SVFG
{
    typedef Set<SVFGNode*> SVFGNodeSet;
    typedef Map<NodeID, NodeID> NodeIDToNodeIDMap;
    typedef FIFOWorkList<const MSSAPHISVFGNode*> WorkList;
 
public:
    SVFGOPT(std::unique_ptr<MemSSA> mssa, VFGK kind) : SVFG(std::move(mssa), kind)
    {
        keepAllSelfCycle = keepContextSelfCycle = keepActualOutFormalIn = false;
    }

    ~SVFGOPT() override = default;
 
    inline void setTokeepActualOutFormalIn()
    {
        keepActualOutFormalIn = true;
    }
    inline void setTokeepAllSelfCycle()
    {
        keepAllSelfCycle = true;
    }
    inline void setTokeepContextSelfCycle()
    {
        keepContextSelfCycle = true;
    }

    void readAndOptSVFG(const std::string &filename);

    void buildAndWriteSVFG(const std::string &filename);
 
protected:
    void buildSVFG() override;

    void optimiseSVFG();


    inline void connectAParamAndFParam(const ValVar* cs_arg, const ValVar* fun_arg, const CallICFGNode*, CallSiteID csId, SVFGEdgeSetTy& edges) override
    {
        NodeID phiId = getDef(fun_arg);
        SVFGEdge* edge = addCallEdge(getDef(cs_arg), phiId, csId);
        if (edge != nullptr)
        {
            PHISVFGNode* phi = SVFUtil::cast<PHISVFGNode>(getSVFGNode(phiId));
            addInterPHIOperands(phi, cs_arg);
            edges.insert(edge);
        }
    }

    inline void connectFRetAndARet(const ValVar* fun_ret, const ValVar* cs_ret, CallSiteID csId, SVFGEdgeSetTy& edges) override
    {
        NodeID phiId = getDef(cs_ret);
        NodeID retdef = getDef(fun_ret);
        if (pag->isPhiNode(fun_ret)==false)
            return;
 
        SVFGEdge* edge = addRetEdge(retdef, phiId, csId);
        if (edge != nullptr)
        {
            PHISVFGNode* phi = SVFUtil::cast<PHISVFGNode>(getSVFGNode(phiId));
            addInterPHIOperands(phi, fun_ret);
            edges.insert(edge);
        }
    }

    inline void connectAInAndFIn(const ActualINSVFGNode* actualIn, const FormalINSVFGNode* formalIn, CallSiteID csId, SVFGEdgeSetTy& edges) override
    {
        NodeBS intersection = actualIn->getPointsTo();
        intersection &= formalIn->getPointsTo();
        if (intersection.empty() == false)
        {
            NodeID aiDef = getActualINDef(actualIn->getId());
            SVFGEdge* edge = addCallIndirectSVFGEdge(aiDef,formalIn->getId(),csId,intersection);
            if (edge != nullptr)
                edges.insert(edge);
        }
    }

    inline void connectFOutAndAOut(const FormalOUTSVFGNode* formalOut, const ActualOUTSVFGNode* actualOut, CallSiteID csId, SVFGEdgeSetTy& edges) override
    {
        NodeBS intersection = formalOut->getPointsTo();
        intersection &= actualOut->getPointsTo();
        if (intersection.empty() == false)
        {
            NodeID foDef = getFormalOUTDef(formalOut->getId());
            SVFGEdge* edge = addRetIndirectSVFGEdge(foDef,actualOut->getId(),csId,intersection);
            if (edge != nullptr)
                edges.insert(edge);
        }
    }



    inline NodeID getActualINDef(NodeID ai) const
    {
        NodeIDToNodeIDMap::const_iterator it = actualInToDefMap.find(ai);
        assert(it != actualInToDefMap.end() && "can not find actual-in's def");
        return it->second;
    }
    inline NodeID getFormalOUTDef(NodeID fo) const
    {
        NodeIDToNodeIDMap::const_iterator it = formalOutToDefMap.find(fo);
        assert(it != formalOutToDefMap.end() && "can not find formal-out's def");
        return it->second;
    }

 
private:
    void parseSelfCycleHandleOption();



    SVFGEdge* addCallIndirectSVFGEdge(NodeID srcId, NodeID dstId, CallSiteID csid, const NodeBS& cpts);
    SVFGEdge* addRetIndirectSVFGEdge(NodeID srcId, NodeID dstId, CallSiteID csid, const NodeBS& cpts);

    void handleInterValueFlow();


    void replaceFParamARetWithPHI(PHISVFGNode* phi, SVFGNode* svfgNode);



    void retargetEdgesOfAInFOut(SVFGNode* node);
    void retargetEdgesOfAOutFIn(SVFGNode* node);

    void handleIntraValueFlow();

    inline void initialWorkList()
    {
        for (SVFG::const_iterator it = begin(), eit = end(); it != eit; ++it)
            addIntoWorklist(it->second);
    }

    inline bool addIntoWorklist(const SVFGNode* node)
    {
        if (const MSSAPHISVFGNode* phi = SVFUtil::dyn_cast<MSSAPHISVFGNode>(node))
        {
            if (isConnectingTwoCallSites(phi) == false && isDefOfAInFOut(phi) == false)
                return worklist.push(phi);
        }
        return false;
    }

    void bypassMSSAPHINode(const MSSAPHISVFGNode* node);

    bool checkSelfCycleEdges(const MSSAPHISVFGNode* node);

    bool addNewSVFGEdge(NodeID srcId, NodeID dstId, const SVFGEdge* preEdge, const SVFGEdge* succEdge);

    inline bool bothInterEdges(const SVFGEdge* edge1, const SVFGEdge* edge2) const
    {
        bool inter1 = SVFUtil::isa<CallIndSVFGEdge, RetIndSVFGEdge>(edge1);
        bool inter2 = SVFUtil::isa<CallIndSVFGEdge, RetIndSVFGEdge>(edge2);
        return (inter1 && inter2);
    }
 
    inline void addInterPHIOperands(PHISVFGNode* phi, const ValVar* operand)
    {
        phi->setOpVer(phi->getOpVerNum(), operand);
    }

    inline InterPHISVFGNode* addInterPHIForFP(const FormalParmSVFGNode* fp)
    {
        InterPHISVFGNode* sNode = new InterPHISVFGNode(totalVFGNode++,fp);
        addSVFGNode(sNode, pag->getICFG()->getFunEntryICFGNode(fp->getFun()));
        resetDef(fp->getParam(),sNode);
        return sNode;
    }

    inline InterPHISVFGNode* addInterPHIForAR(const ActualRetSVFGNode* ar)
    {
        InterPHISVFGNode* sNode = new InterPHISVFGNode(totalVFGNode++,ar);
        addSVFGNode(sNode, const_cast<RetICFGNode*>(
                        ar->getCallSite()->getRetICFGNode()));
        resetDef(ar->getRev(),sNode);
        return sNode;
    }
 
    inline void resetDef(const ValVar* valVar, const SVFGNode* node)
    {
        ValVarToDefMapTy::iterator it = ValVarToDefMap.find(valVar);
        assert(it != ValVarToDefMap.end() && "a SVFIR node doesn't have definition before");
        it->second = node->getId();
    }

    inline void setActualINDef(NodeID ai, NodeID def)
    {
        bool inserted = actualInToDefMap.emplace(ai, def).second;
        (void)inserted; // Suppress warning of unused variable under release build
        assert(inserted && "can not set actual-in's def twice");
        defNodes.set(def);
    }
    inline void setFormalOUTDef(NodeID fo, NodeID def)
    {
        bool inserted = formalOutToDefMap.emplace(fo, def).second;
        (void) inserted;
        assert(inserted && "can not set formal-out's def twice");
        defNodes.set(def);
    }

 
    inline bool isDefOfAInFOut(const SVFGNode* node)
    {
        return defNodes.test(node->getId());
    }


    inline bool actualInOfIndCS(const ActualINSVFGNode* ai) const
    {
        return (SVFIR::getPAG()->isIndirectCallSites(ai->getCallSite()));
    }
    inline bool actualOutOfIndCS(const ActualOUTSVFGNode* ao) const
    {
        return (SVFIR::getPAG()->isIndirectCallSites(ao->getCallSite()));
    }



    inline bool formalInOfAddressTakenFunc(const FormalINSVFGNode* fi) const
    {
        return (fi->getFun()->hasAddressTaken());
    }
    inline bool formalOutOfAddressTakenFunc(const FormalOUTSVFGNode* fo) const
    {
        return (fo->getFun()->hasAddressTaken());
    }


    bool isConnectingTwoCallSites(const SVFGNode* node) const;

    bool canBeRemoved(const SVFGNode * node);


    inline void removeAllEdges(const SVFGNode* node)
    {
        removeInEdges(node);
        removeOutEdges(node);
    }
    inline void removeInEdges(const SVFGNode* node)
    {
        while (node->hasIncomingEdge())
            removeSVFGEdge(*(node->InEdgeBegin()));
    }
    inline void removeOutEdges(const SVFGNode* node)
    {
        while (node->hasOutgoingEdge())
            removeSVFGEdge(*(node->OutEdgeBegin()));
    }

 
 
    NodeIDToNodeIDMap actualInToDefMap; 
    NodeIDToNodeIDMap formalOutToDefMap;    
    NodeBS defNodes;    
 
    WorkList worklist;  
 
    bool keepActualOutFormalIn;
    bool keepAllSelfCycle;
    bool keepContextSelfCycle;
};
 
} // End namespace SVF
 
#endif /* SVFGOPT_H_ */