ICFG.h

Go to the documentation of this file.

//===- ICFG.h ----------------------------------------------------------------//
//
//                     SVF: Static Value-Flow Analysis
//
// Copyright (C) <2013-2018>  <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/>.
//
//===----------------------------------------------------------------------===//
 
/*
 * ICFG.h
 *
 *  Created on: 11 Sep. 2018
 *      Author: Yulei
 */
 
#ifndef INCLUDE_UTIL_ICFG_H_
#define INCLUDE_UTIL_ICFG_H_
 
#include "Graphs/ICFGNode.h"
#include "Graphs/ICFGEdge.h"
#include "Util/WorkList.h"
#include "MemoryModel/SVFLoop.h"
 
namespace SVF
{
 
class PTACallGraph;
 
typedef GenericGraph<ICFGNode,ICFGEdge> GenericICFGTy;
class ICFG : public GenericICFGTy
{
    friend class ICFGBuilder;
    friend class SVFIRWriter;
    friend class SVFIRReader;
    friend class ICFGSimplification;
 
public:
 
    typedef OrderedMap<NodeID, ICFGNode *> ICFGNodeIDToNodeMapTy;
    typedef ICFGEdge::ICFGEdgeSetTy ICFGEdgeSetTy;
    typedef ICFGNodeIDToNodeMapTy::iterator iterator;
    typedef ICFGNodeIDToNodeMapTy::const_iterator const_iterator;
 
    typedef Map<const SVFFunction*, FunEntryICFGNode *> FunToFunEntryNodeMapTy;
    typedef Map<const SVFFunction*, FunExitICFGNode *> FunToFunExitNodeMapTy;
    typedef std::vector<const SVFLoop *> SVFLoopVec;
    typedef Map<const ICFGNode *, SVFLoopVec> ICFGNodeToSVFLoopVec;
 
    NodeID totalICFGNode;
 
private:
    FunToFunEntryNodeMapTy FunToFunEntryNodeMap; 
    FunToFunExitNodeMapTy FunToFunExitNodeMap; 
    GlobalICFGNode* globalBlockNode; 
    ICFGNodeToSVFLoopVec icfgNodeToSVFLoopVec; 
 
    Map<const ICFGNode*, std::vector<const ICFGNode*>> _subNodes; 
    Map<const ICFGNode*, const ICFGNode*> _repNode; 
 
 
public:
    ICFG();
 
    ~ICFG() override;
 
    inline ICFGNode* getICFGNode(NodeID id) const
    {
        return getGNode(id);
    }
 
    inline bool hasICFGNode(NodeID id) const
    {
        return hasGNode(id);
    }
 
 
    ICFGEdge* hasIntraICFGEdge(ICFGNode* src, ICFGNode* dst, ICFGEdge::ICFGEdgeK kind);
    ICFGEdge* hasInterICFGEdge(ICFGNode* src, ICFGNode* dst, ICFGEdge::ICFGEdgeK kind);
    ICFGEdge* hasThreadICFGEdge(ICFGNode* src, ICFGNode* dst, ICFGEdge::ICFGEdgeK kind);
 
    ICFGEdge* getICFGEdge(const ICFGNode* src, const ICFGNode* dst, ICFGEdge::ICFGEdgeK kind);
 
    void dump(const std::string& file, bool simple = false);
 
    void view();
 
    void updateCallGraph(PTACallGraph* callgraph);
 
    inline bool isInLoop(const ICFGNode *node)
    {
        auto it = icfgNodeToSVFLoopVec.find(node);
        return it != icfgNodeToSVFLoopVec.end();
    }
 
    inline void addNodeToSVFLoop(const ICFGNode *node, const SVFLoop* loop)
    {
        icfgNodeToSVFLoopVec[node].push_back(loop);
    }
 
    inline SVFLoopVec& getSVFLoops(const ICFGNode *node)
    {
        auto it = icfgNodeToSVFLoopVec.find(node);
        assert(it != icfgNodeToSVFLoopVec.end() && "node not in loop");
        return it->second;
    }
 
    inline const ICFGNodeToSVFLoopVec& getIcfgNodeToSVFLoopVec() const
    {
        return icfgNodeToSVFLoopVec;
    }
 
protected:
 
    ICFGEdge* addIntraEdge(ICFGNode* srcNode, ICFGNode* dstNode);
    ICFGEdge* addConditionalIntraEdge(ICFGNode* srcNode, ICFGNode* dstNode, s64_t branchCondVal);
    ICFGEdge* addCallEdge(ICFGNode* srcNode, ICFGNode* dstNode);
    ICFGEdge* addRetEdge(ICFGNode* srcNode, ICFGNode* dstNode);
    inline void removeICFGEdge(ICFGEdge* edge)
    {
        edge->getDstNode()->removeIncomingEdge(edge);
        edge->getSrcNode()->removeOutgoingEdge(edge);
        delete edge;
    }
 
    inline void removeICFGNode(ICFGNode* node)
    {
        removeGNode(node);
    }
 
    inline void checkIntraEdgeParents(const ICFGNode *srcNode, const ICFGNode *dstNode)
    {
        const SVFFunction* srcfun = srcNode->getFun();
        const SVFFunction* dstfun = dstNode->getFun();
        if(srcfun != nullptr && dstfun != nullptr)
        {
            assert((srcfun == dstfun) && "src and dst nodes of an intra edge should in the same function!" );
        }
    }
 
    virtual inline IntraICFGNode* addIntraICFGNode(const SVFBasicBlock* bb, bool isRet)
    {
        IntraICFGNode* intraIcfgNode =
            new IntraICFGNode(totalICFGNode++, bb, isRet);
        addICFGNode(intraIcfgNode);
        return intraIcfgNode;
    }
 
    virtual inline CallICFGNode* addCallICFGNode(
        const SVFBasicBlock* bb, const SVFType* ty,
        const SVFFunction* calledFunc, bool isVararg, bool isvcall,
        s32_t vcallIdx, const std::string& funNameOfVcall)
    {
 
        CallICFGNode* callICFGNode =
            new CallICFGNode(totalICFGNode++, bb, ty, calledFunc, isVararg,
                             isvcall, vcallIdx, funNameOfVcall);
        addICFGNode(callICFGNode);
        return callICFGNode;
    }
 
    virtual inline RetICFGNode* addRetICFGNode(CallICFGNode* call)
    {
        RetICFGNode* retICFGNode = new RetICFGNode(totalICFGNode++, call);
        call->setRetICFGNode(retICFGNode);
        addICFGNode(retICFGNode);
        return retICFGNode;
    }
 
    virtual inline FunEntryICFGNode* addFunEntryICFGNode(const SVFFunction* svfFunc)
    {
        FunEntryICFGNode* sNode = new FunEntryICFGNode(totalICFGNode++,svfFunc);
        addICFGNode(sNode);
        return FunToFunEntryNodeMap[svfFunc] = sNode;
    }
 
    virtual inline FunExitICFGNode* addFunExitICFGNode(const SVFFunction* svfFunc)
    {
        FunExitICFGNode* sNode = new FunExitICFGNode(totalICFGNode++, svfFunc);
        addICFGNode(sNode);
        return FunToFunExitNodeMap[svfFunc] = sNode;
    }
 
    virtual inline void addICFGNode(ICFGNode* node)
    {
        addGNode(node->getId(),node);
        _repNode[node] = node;
        _subNodes[node].push_back(node);
    }
 
public:
 
 
 
    FunEntryICFGNode* getFunEntryICFGNode(const SVFFunction*  fun);
 
    FunExitICFGNode* getFunExitICFGNode(const SVFFunction*  fun);
 
    inline GlobalICFGNode* getGlobalICFGNode() const
    {
        return globalBlockNode;
    }
 
    const std::vector<const ICFGNode*>& getSubNodes(const ICFGNode* node) const
    {
        return _subNodes.at(node);
    }
 
    const ICFGNode* getRepNode(const ICFGNode* node) const
    {
        return _repNode.at(node);
    }
 
 
    void updateSubAndRep(const ICFGNode* rep, const ICFGNode* sub)
    {
        addSubNode(rep, sub);
        updateRepNode(rep, sub);
    }
 
private:
    void addSubNode(const ICFGNode* rep, const ICFGNode* sub)
    {
        std::vector<const ICFGNode*>& subNodes = _subNodes[sub];
        if(std::find(subNodes.begin(), subNodes.end(), rep) == subNodes.end())
        {
            subNodes.push_back(rep);
        }
    }
 
    void updateRepNode(const ICFGNode* rep, const ICFGNode* sub)
    {
        _repNode[rep] = sub;
    }
 
    inline bool addICFGEdge(ICFGEdge* edge)
    {
        bool added1 = edge->getDstNode()->addIncomingEdge(edge);
        bool added2 = edge->getSrcNode()->addOutgoingEdge(edge);
        bool all_added = added1 && added2;
        assert(all_added && "ICFGEdge not added?");
        return all_added;
    }
 
    inline FunEntryICFGNode* getFunEntryBlock(const SVFFunction* fun)
    {
        FunToFunEntryNodeMapTy::const_iterator it = FunToFunEntryNodeMap.find(fun);
        if (it == FunToFunEntryNodeMap.end())
            return nullptr;
        return it->second;
    }
 
    inline FunExitICFGNode* getFunExitBlock(const SVFFunction* fun)
    {
        FunToFunExitNodeMapTy::const_iterator it = FunToFunExitNodeMap.find(fun);
        if (it == FunToFunExitNodeMap.end())
            return nullptr;
        return it->second;
    }
 
};
 
} // End namespace SVF
 
namespace SVF
{
/* !
 * GenericGraphTraits specializations for generic graph algorithms.
 * Provide graph traits for traversing from a constraint node using standard graph traversals.
 */
template<> struct GenericGraphTraits<SVF::ICFGNode*> : public GenericGraphTraits<SVF::GenericNode<SVF::ICFGNode,SVF::ICFGEdge>*  >
{
};
 
template<>
struct GenericGraphTraits<Inverse<SVF::ICFGNode *> > : public GenericGraphTraits<Inverse<SVF::GenericNode<SVF::ICFGNode,SVF::ICFGEdge>* > >
{
};
 
template<> struct GenericGraphTraits<SVF::ICFG*> : public GenericGraphTraits<SVF::GenericGraph<SVF::ICFGNode,SVF::ICFGEdge>* >
{
    typedef SVF::ICFGNode *NodeRef;
};
 
} // End namespace llvm
 
#endif /* INCLUDE_UTIL_ICFG_H_ */