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;
 
/*
 * Graph representation of SVF IR.
 * It can be seen as a program assignment graph (PAG).
 */
class IRGraph : public GenericGraph<SVFVar, SVFStmt>
{
    friend class SVFIRWriter;
    friend class SVFIRReader;
 
public:
    typedef Set<const SVFStmt*> SVFStmtSet;
    typedef Map<const SVFValue*,SVFStmtSet> ValueToEdgeMap;
 
protected:
    SVFStmt::KindToSVFStmtMapTy KindToSVFStmtSetMap; 
    SVFStmt::KindToSVFStmtMapTy KindToPTASVFStmtSetMap; 
    bool fromFile; 
    NodeID nodeNumAfterPAGBuild; 
    u32_t totalPTAPAGEdge;
    ValueToEdgeMap valueToEdgeMap; 
    SymbolTableInfo* symInfo;
 
    inline NodeID addNode(SVFVar* node, NodeID i)
    {
        addGNode(i,node);
        return i;
    }
    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);
 
    inline void mapValueToEdge(const SVFValue* V, SVFStmt *edge)
    {
        auto inserted = valueToEdgeMap.emplace(V, SVFStmtSet{edge});
        if (!inserted.second)
        {
            inserted.first->second.emplace(edge);
        }
    }
    inline const MemObj* getMemObj(const SVFValue* val) const
    {
        return symInfo->getObj(symInfo->getObjSym(val));
    }
 
public:
    IRGraph(bool buildFromFile)
        : fromFile(buildFromFile), nodeNumAfterPAGBuild(0), totalPTAPAGEdge(0)
    {
        symInfo = SymbolTableInfo::SymbolInfo();
        // insert dummy value if a correct value cannot be found
        valueToEdgeMap[nullptr] = SVFStmtSet();
    }
 
    virtual ~IRGraph();
 
    inline SymbolTableInfo* getSymbolInfo() const
    {
        return symInfo;
    }
    inline bool isBuiltFromFile()
    {
        return fromFile;
    }
    inline const SVFStmtSet& getValueEdges(const SVFValue* V)
    {
        auto it = valueToEdgeMap.find(V);
        if (it == valueToEdgeMap.end())
        {
            //special empty set
            return valueToEdgeMap.at(nullptr);
        }
        return it->second;
    }
 
    inline NodeID getValueNode(const SVFValue* V)
    {
        return symInfo->getValSym(V);
    }
    inline bool hasValueNode(const SVFValue* V)
    {
        return symInfo->hasValSym(V);
    }
    inline NodeID getObjectNode(const SVFValue* V)
    {
        return symInfo->getObjSym(V);
    }
    inline NodeID getReturnNode(const SVFFunction* func) const
    {
        return symInfo->getRetSym(func);
    }
    inline NodeID getVarargNode(const SVFFunction* func) const
    {
        return symInfo->getVarargSym(func);
    }
    inline NodeID getBlackHoleNode() const
    {
        return symInfo->blackholeSymID();
    }
    inline NodeID getConstantNode() const
    {
        return symInfo->constantSymID();
    }
    inline NodeID getBlkPtr() const
    {
        return symInfo->blkPtrSymID();
    }
    inline NodeID getNullPtr() const
    {
        return symInfo->nullPtrSymID();
    }
    inline const MemObj* getBlackHoleObj() const
    {
        return symInfo->getBlkObj();
    }
    inline const MemObj* getConstantObj() const
    {
        return symInfo->getConstantObj();
    }
 
    inline u32_t getValueNodeNum() const
    {
        return symInfo->valSyms().size();
    }
    inline u32_t getObjectNodeNum() const
    {
        return symInfo->idToObjMap().size();
    }
    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 dump(std::string name);
 
    void view();
};
 
}
 
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_ */