ConsG.h

Go to the documentation of this file.

//===- ConsG.h -- Constraint graph representation-----------------------------//
//
//                     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/>.
//
//===----------------------------------------------------------------------===//
 
/*
 * ConstraintGraph.h
 *
 *  Created on: Oct 14, 2013
 *      Author: Yulei Sui
 */
 
#ifndef CONSG_H_
#define CONSG_H_
 
#include "Graphs/ConsGEdge.h"
#include "Graphs/ConsGNode.h"
 
namespace SVF
{
 
class ConstraintGraph :  public GenericGraph<ConstraintNode,ConstraintEdge>
{
 
public:
    typedef OrderedMap<NodeID, ConstraintNode *> ConstraintNodeIDToNodeMapTy;
    typedef ConstraintEdge::ConstraintEdgeSetTy::iterator ConstraintNodeIter;
    typedef Map<NodeID, NodeID> NodeToRepMap;
    typedef Map<NodeID, NodeBS> NodeToSubsMap;
    typedef FIFOWorkList<NodeID> WorkList;
 
protected:
    SVFIR* pag;
    NodeToRepMap nodeToRepMap;
    NodeToSubsMap nodeToSubsMap;
    WorkList nodesToBeCollapsed;
    EdgeID edgeIndex;
 
    ConstraintEdge::ConstraintEdgeSetTy AddrCGEdgeSet;
    ConstraintEdge::ConstraintEdgeSetTy directEdgeSet;
    ConstraintEdge::ConstraintEdgeSetTy LoadCGEdgeSet;
    ConstraintEdge::ConstraintEdgeSetTy StoreCGEdgeSet;
 
    void buildCG();
 
    void destroy();
 
    void clearSolitaries();  // remove nodes that are neither pointers nor connected with any edge
 
    SVFStmt::SVFStmtSetTy& getPAGEdgeSet(SVFStmt::PEDGEK kind)
    {
        return pag->getPTASVFStmtSet(kind);
    }
 
 
    inline NodeID getValueNode(const SVFValue* value) const
    {
        return sccRepNode(pag->getValueNode(value));
    }
 
    inline NodeID getReturnNode(const SVFFunction* value) const
    {
        return pag->getReturnNode(value);
    }
 
    inline NodeID getVarargNode(const SVFFunction* value) const
    {
        return pag->getVarargNode(value);
    }
 
public:
    ConstraintGraph(SVFIR* p): pag(p), edgeIndex(0)
    {
        buildCG();
    }
    virtual ~ConstraintGraph()
    {
        destroy();
    }
 
 
    inline ConstraintNode* getConstraintNode(NodeID id) const
    {
        id = sccRepNode(id);
        return getGNode(id);
    }
    inline void addConstraintNode(ConstraintNode* node, NodeID id)
    {
        addGNode(id,node);
    }
    inline bool hasConstraintNode(NodeID id) const
    {
        id = sccRepNode(id);
        return hasGNode(id);
    }
    inline void removeConstraintNode(ConstraintNode* node)
    {
        removeGNode(node);
    }
 
    inline bool hasEdge(ConstraintNode* src, ConstraintNode* dst, ConstraintEdge::ConstraintEdgeK kind)
    {
        ConstraintEdge edge(src,dst,kind);
        if(kind == ConstraintEdge::Copy ||
                kind == ConstraintEdge::NormalGep || kind == ConstraintEdge::VariantGep)
            return directEdgeSet.find(&edge) != directEdgeSet.end();
        else if(kind == ConstraintEdge::Addr)
            return AddrCGEdgeSet.find(&edge) != AddrCGEdgeSet.end();
        else if(kind == ConstraintEdge::Store)
            return StoreCGEdgeSet.find(&edge) != StoreCGEdgeSet.end();
        else if(kind == ConstraintEdge::Load)
            return LoadCGEdgeSet.find(&edge) != LoadCGEdgeSet.end();
        else
            assert(false && "no other kind!");
        return false;
    }
 
    inline ConstraintEdge* getEdge(ConstraintNode* src, ConstraintNode* dst, ConstraintEdge::ConstraintEdgeK kind)
    {
        ConstraintEdge edge(src,dst,kind);
        if(kind == ConstraintEdge::Copy || kind == ConstraintEdge::NormalGep || kind == ConstraintEdge::VariantGep)
        {
            auto eit = directEdgeSet.find(&edge);
            return *eit;
        }
        else if(kind == ConstraintEdge::Addr)
        {
            auto eit = AddrCGEdgeSet.find(&edge);
            return *eit;
        }
        else if(kind == ConstraintEdge::Store)
        {
            auto eit = StoreCGEdgeSet.find(&edge);
            return *eit;
        }
        else if(kind == ConstraintEdge::Load)
        {
            auto eit = LoadCGEdgeSet.find(&edge);
            return *eit;
        }
        else
        {
            assert(false && "no other kind!");
            return nullptr;
        }
    }
 
 
 
    AddrCGEdge* addAddrCGEdge(NodeID src, NodeID dst);
    CopyCGEdge* addCopyCGEdge(NodeID src, NodeID dst);
    NormalGepCGEdge* addNormalGepCGEdge(NodeID src, NodeID dst, const AccessPath& ap);
    VariantGepCGEdge* addVariantGepCGEdge(NodeID src, NodeID dst);
    LoadCGEdge* addLoadCGEdge(NodeID src, NodeID dst);
    StoreCGEdge* addStoreCGEdge(NodeID src, NodeID dst);
 
 
 
    inline ConstraintEdge::ConstraintEdgeSetTy& getAddrCGEdges()
    {
        return AddrCGEdgeSet;
    }
    inline ConstraintEdge::ConstraintEdgeSetTy& getDirectCGEdges()
    {
        return directEdgeSet;
    }
    inline ConstraintEdge::ConstraintEdgeSetTy& getLoadCGEdges()
    {
        return LoadCGEdgeSet;
    }
    inline ConstraintEdge::ConstraintEdgeSetTy& getStoreCGEdges()
    {
        return StoreCGEdgeSet;
    }
 
 
 
    void reTargetDstOfEdge(ConstraintEdge* edge, ConstraintNode* newDstNode);
    void reTargetSrcOfEdge(ConstraintEdge* edge, ConstraintNode* newSrcNode);
    void removeAddrEdge(AddrCGEdge* edge);
    void removeDirectEdge(ConstraintEdge* edge);
    void removeLoadEdge(LoadCGEdge* edge);
    void removeStoreEdge(StoreCGEdge* edge);
 
 
    inline NodeID sccRepNode(NodeID id) const
    {
        NodeToRepMap::const_iterator it = nodeToRepMap.find(id);
        if(it==nodeToRepMap.end())
            return id;
        else
            return it->second;
    }
    inline NodeBS& sccSubNodes(NodeID id)
    {
        nodeToSubsMap[id].set(id);
        return nodeToSubsMap[id];
    }
    inline void setRep(NodeID node, NodeID rep)
    {
        nodeToRepMap[node] = rep;
    }
    inline void setSubs(NodeID node, NodeBS& subs)
    {
        nodeToSubsMap[node] |= subs;
    }
    inline void resetSubs(NodeID node)
    {
        nodeToSubsMap.erase(node);
    }
    inline NodeBS& getSubs(NodeID node)
    {
        return nodeToSubsMap[node];
    }
    inline NodeID getRep(NodeID node)
    {
        return nodeToRepMap[node];
    }
    inline void resetRep(NodeID node)
    {
        nodeToRepMap.erase(node);
    }
 
    bool moveInEdgesToRepNode(ConstraintNode*node, ConstraintNode* rep );
 
    bool moveOutEdgesToRepNode(ConstraintNode*node, ConstraintNode* rep );
 
    inline bool moveEdgesToRepNode(ConstraintNode*node, ConstraintNode* rep )
    {
        bool gepIn = moveInEdgesToRepNode(node, rep);
        bool gepOut = moveOutEdgesToRepNode(node, rep);
        return (gepIn || gepOut);
    }
 
    inline bool isZeroOffsettedGepCGEdge(ConstraintEdge *edge) const
    {
        if (NormalGepCGEdge *normalGepCGEdge = SVFUtil::dyn_cast<NormalGepCGEdge>(edge))
            if (0 == normalGepCGEdge->getConstantFieldIdx())
                return true;
        return false;
    }
 
 
    inline const SVFIR::CallSiteToFunPtrMap& getIndirectCallsites() const
    {
        return pag->getIndirectCallsites();
    }
    inline NodeID getBlackHoleNode()
    {
        return pag->getBlackHoleNode();
    }
    inline bool isBlkObjOrConstantObj(NodeID id)
    {
        return pag->isBlkObjOrConstantObj(id);
    }
    inline NodeBS& getAllFieldsObjVars(NodeID id)
    {
        return pag->getAllFieldsObjVars(id);
    }
    inline NodeID getBaseObjVar(NodeID id)
    {
        return pag->getBaseObjVar(id);
    }
    inline bool isSingleFieldObj(NodeID id) const
    {
        const MemObj* mem = pag->getBaseObj(id);
        return (mem->getMaxFieldOffsetLimit() == 1);
    }
    inline NodeID getGepObjVar(NodeID id, const APOffset& apOffset)
    {
        NodeID gep =  pag->getGepObjVar(id, apOffset);
        if(sccRepNode(gep)==gep && hasConstraintNode(gep)==false)
            addConstraintNode(new ConstraintNode(gep),gep);
        return gep;
    }
    inline NodeID getFIObjVar(NodeID id)
    {
        NodeID fi = pag->getFIObjVar(id);
        assert((hasConstraintNode(fi) || sccRepNode(fi) != fi) && "non-existing fi obj??");
        return fi;
    }
 
 
    inline bool isPWCNode(NodeID nodeId)
    {
        return getConstraintNode(nodeId)->isPWCNode();
    }
    inline void setPWCNode(NodeID nodeId)
    {
        getConstraintNode(nodeId)->setPWCNode();
    }
 
 
    inline bool hasNodesToBeCollapsed() const
    {
        return (!nodesToBeCollapsed.empty());
    }
    inline void addNodeToBeCollapsed(NodeID id)
    {
        nodesToBeCollapsed.push(id);
    }
    inline NodeID getNextCollapseNode()
    {
        return nodesToBeCollapsed.pop();
    }
 
    void dump(std::string name);
    void print();
 
    void view();
};
 
 
/* !
 * GenericGraphTraits specializations for the generic graph algorithms.
 * Provide graph traits for traversing from a constraint node using standard graph traversals.
 */
template<> struct GenericGraphTraits<SVF::ConstraintNode*> : public GenericGraphTraits<SVF::GenericNode<SVF::ConstraintNode,SVF::ConstraintEdge>*  >
{
};
 
template<>
struct GenericGraphTraits<Inverse<SVF::ConstraintNode *> > : public GenericGraphTraits<Inverse<SVF::GenericNode<SVF::ConstraintNode,SVF::ConstraintEdge>* > >
{
};
 
template<> struct GenericGraphTraits<SVF::ConstraintGraph*> : public GenericGraphTraits<SVF::GenericGraph<SVF::ConstraintNode,SVF::ConstraintEdge>* >
{
    typedef SVF::ConstraintNode *NodeRef;
};
 
} // End namespace SVF
 
#endif /* CONSG_H_ */