IRGraph.h

Go to the documentation of this file.

//===- SVFIR.h -- SVF IR Graph or PAG (Program Assignment Graph)--------------//
//
//                     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/>.
//
//===----------------------------------------------------------------------===//
 
/*
 * IRGraph.h
 *
 *  Created on: Nov 1, 2013
 *      Author: Yulei Sui
 */
 
 
#ifndef IRGRAPH_H_
#define IRGRAPH_H_
 
#include "SVFIR/SVFStatements.h"
#include "SVFIR/SVFVariables.h"
#include "Util/NodeIDAllocator.h"
#include "Util/SVFUtil.h"
#include "Graphs/ICFG.h"
 
namespace SVF
{
typedef SVFVar PAGNode;
typedef SVFStmt PAGEdge;
 
class ObjTypeInfo;
 
/*
 * Graph representation of SVF IR.
 * It can be seen as a program assignment graph (PAG).
 */
class IRGraph : public GenericGraph<SVFVar, SVFStmt>
{
    friend class SVFIRBuilder;
    friend class SymbolTableBuilder;
 
public:
 
    enum SYMTYPE
    {
        NullPtr,
        BlkPtr,
        BlackHole,
        ConstantObj,
        ValSymbol,
        ObjSymbol,
        RetSymbol,
        VarargSymbol
    };
 
    //{@
    typedef OrderedMap<NodeID, ObjTypeInfo*> IDToTypeInfoMapTy;
 
    typedef OrderedMap<const FunObjVar*, NodeID> FunObjVarToIDMapTy;
 
    typedef Set<const SVFType*> SVFTypeSet;
 
private:
    FunObjVarToIDMapTy returnFunObjSymMap; 
    FunObjVarToIDMapTy varargFunObjSymMap; 
    IDToTypeInfoMapTy objTypeInfoMap;       
 
    SVFTypeSet svfTypes;
 
    Set<const StInfo*> stInfos;
 
    NodeID totalSymNum;
 
    void destorySymTable();
 
public:
    typedef Set<const SVFStmt*> SVFStmtSet;
 
protected:
    SVFStmt::KindToSVFStmtMapTy KindToSVFStmtSetMap; 
    SVFStmt::KindToSVFStmtMapTy KindToPTASVFStmtSetMap; 
    bool fromFile; 
    NodeID nodeNumAfterPAGBuild; 
    u32_t totalPTAPAGEdge;
    u32_t valVarNum;
    u32_t objVarNum;
 
    inline NodeID addNode(SVFVar* node)
    {
        assert(node && "cannot add a null node");
        addGNode(node->getId(),node);
        return node->getId();
    }
    bool addEdge(SVFVar* src, SVFVar* dst, SVFStmt* edge);
 
    SVFStmt* hasNonlabeledEdge(SVFVar* src, SVFVar* dst, SVFStmt::PEDGEK kind);
    SVFStmt* hasLabeledEdge(SVFVar* src, SVFVar* dst, SVFStmt::PEDGEK kind,
                            const ICFGNode* cs);
    SVFStmt* hasLabeledEdge(SVFVar* src, SVFVar* op1, SVFStmt::PEDGEK kind,
                            const SVFVar* op2);
 
public:
    IRGraph(bool buildFromFile)
        : totalSymNum(0), fromFile(buildFromFile), nodeNumAfterPAGBuild(0), totalPTAPAGEdge(0), valVarNum(0), objVarNum(0),
          maxStruct(nullptr), maxStSize(0)
    {
    }
 
    virtual ~IRGraph();
 
 
    inline bool isBuiltFromFile()
    {
        return fromFile;
    }
 
    // @{
    static inline bool isBlkPtr(NodeID id)
    {
        return (id == BlkPtr);
    }
    static inline bool isNullPtr(NodeID id)
    {
        return (id == NullPtr);
    }
    static inline bool isBlkObj(NodeID id)
    {
        return (id == BlackHole);
    }
    static inline bool isConstantSym(NodeID id)
    {
        return (id == ConstantObj);
    }
    static inline bool isBlkObjOrConstantObj(NodeID id)
    {
        return (isBlkObj(id) || isConstantSym(id));
    }
 
    inline NodeID blkPtrSymID() const
    {
        return BlkPtr;
    }
 
    inline NodeID nullPtrSymID() const
    {
        return NullPtr;
    }
 
    inline NodeID constantSymID() const
    {
        return ConstantObj;
    }
 
    inline NodeID blackholeSymID() const
    {
        return BlackHole;
    }
 
 
    inline u32_t getTotalSymNum() const
    {
        return totalSymNum;
    }
    inline u32_t getMaxStructSize() const
    {
        return maxStSize;
    }
 
 
    inline IDToTypeInfoMapTy& idToObjTypeInfoMap()
    {
        return objTypeInfoMap;
    }
 
    inline const IDToTypeInfoMapTy& idToObjTypeInfoMap() const
    {
        return objTypeInfoMap;
    }
 
    inline FunObjVarToIDMapTy& retFunObjSyms()
    {
        return returnFunObjSymMap;
    }
 
    inline FunObjVarToIDMapTy& varargFunObjSyms()
    {
        return varargFunObjSymMap;
    }
 
 
    inline ObjTypeInfo* getObjTypeInfo(NodeID id) const
    {
        IDToTypeInfoMapTy::const_iterator iter = objTypeInfoMap.find(id);
        assert(iter!=objTypeInfoMap.end() && "obj type info not found");
        return iter->second;
    }
 
    NodeID getReturnNode(const FunObjVar*func) const;
 
    NodeID getVarargNode(const FunObjVar*func) const;
 
    inline NodeID getBlackHoleNode() const
    {
        return blackholeSymID();
    }
    inline NodeID getConstantNode() const
    {
        return constantSymID();
    }
    inline NodeID getBlkPtr() const
    {
        return blkPtrSymID();
    }
    inline NodeID getNullPtr() const
    {
        return nullPtrSymID();
    }
 
    u32_t getValueNodeNum();
 
    u32_t getObjectNodeNum();
 
 
    inline const SVFTypeSet& getSVFTypes() const
    {
        return svfTypes;
    }
 
    inline const Set<const StInfo*>& getStInfos() const
    {
        return stInfos;
    }
 
    virtual APOffset getModulusOffset(const BaseObjVar* baseObj, const APOffset& apOffset);
 
 
    const StInfo* getTypeInfo(const SVFType* T) const;
    inline bool hasSVFTypeInfo(const SVFType* T)
    {
        return svfTypes.find(T) != svfTypes.end();
    }
 
    ObjTypeInfo* createObjTypeInfo(const SVFType* type);
 
    const ObjTypeInfo* createDummyObjTypeInfo(NodeID symId, const SVFType* type);
 
    u32_t getNumOfFlattenElements(const SVFType* T);
    u32_t getFlattenedElemIdx(const SVFType* T, u32_t origId);
    const SVFType* getFlatternedElemType(const SVFType* baseType, u32_t flatten_idx);
    const SVFType* getOriginalElemType(const SVFType* baseType, u32_t origId) const;
 
    void printFlattenFields(const SVFType* type);
 
 
    inline u32_t getNodeNumAfterPAGBuild() const
    {
        return nodeNumAfterPAGBuild;
    }
    inline void setNodeNumAfterPAGBuild(u32_t num)
    {
        nodeNumAfterPAGBuild = num;
    }
 
    inline u32_t getPAGNodeNum() const
    {
        return nodeNum;
    }
    inline u32_t getPAGEdgeNum() const
    {
        return edgeNum;
    }
    inline u32_t getPTAPAGEdgeNum() const
    {
        return totalPTAPAGEdge;
    }
    inline std::string getGraphName() const
    {
        return "SVFIR";
    }
 
    void dumpSymTable();
 
    void dump(std::string name);
 
    void view();
 
 
 
    const SVFType* maxStruct;
 
    u32_t maxStSize;
 
    inline void addTypeInfo(const SVFType* ty)
    {
        bool inserted = svfTypes.insert(ty).second;
        if(!inserted)
            assert(false && "this type info has been added before");
    }
 
    inline void addStInfo(StInfo* stInfo)
    {
        stInfos.insert(stInfo);
    }
 
protected:
 
    const std::vector<const SVFType*>& getFlattenFieldTypes(const SVFStructType *T);
};
 
}
 
namespace SVF
{
 
/* !
 * GenericGraphTraits specializations of SVFIR to be used for the generic graph algorithms.
 * Provide graph traits for traversing from a SVFIR node using standard graph traversals.
 */
template<> struct GenericGraphTraits<SVF::SVFVar*> : public GenericGraphTraits<SVF::GenericNode<SVF::SVFVar,SVF::SVFStmt>*  >
{
};
 
template<> struct GenericGraphTraits<Inverse<SVF::SVFVar *> > : public GenericGraphTraits<Inverse<SVF::GenericNode<SVF::SVFVar,SVF::SVFStmt>* > >
{
};
 
template<> struct GenericGraphTraits<SVF::IRGraph*> : public GenericGraphTraits<SVF::GenericGraph<SVF::SVFVar,SVF::SVFStmt>* >
{
    typedef SVF::SVFVar* NodeRef;
};
 
} // End namespace llvm
#endif /* IRGRAPH_H_ */