SVFIR.h

Go to the documentation of this file.

//===- SVFIR.h -- IR of SVF ---------------------------------------------//
//
//                     SVF: Static Value-Flow Analysis
//
// Copyright (C) <2013->  <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/>.
//
//===----------------------------------------------------------------------===//
 
/*
 * SVFIR.h
 *
 *  Created on: 31, 12, 2021
 *      Author: Yulei Sui
 */
 
#ifndef INCLUDE_SVFIR_H_
#define INCLUDE_SVFIR_H_
 
#include "Graphs/IRGraph.h"
 
namespace SVF
{
class CommonCHGraph;
class SVFIR : public IRGraph
{
    friend class SVFIRBuilder;
    friend class ExternalPAG;
    friend class PAGBuilderFromFile;
    friend class TypeBasedHeapCloning;
    friend class SVFIRWriter;
    friend class SVFIRReader;
    friend class BVDataPTAImpl;
 
public:
    typedef Set<const CallICFGNode*> CallSiteSet;
    typedef OrderedMap<const CallICFGNode*,NodeID> CallSiteToFunPtrMap;
    typedef Map<NodeID,CallSiteSet> FunPtrToCallSitesMap;
    typedef Map<NodeID,NodeBS> MemObjToFieldsMap;
    typedef std::vector<const SVFStmt*> SVFStmtList;
    typedef std::vector<const SVFVar*> SVFVarList;
    typedef Map<const SVFVar*,PhiStmt*> PHINodeMap;
    typedef Map<const SVFFunction*,SVFVarList> FunToArgsListMap;
    typedef Map<const CallICFGNode*,SVFVarList> CSToArgsListMap;
    typedef Map<const RetICFGNode*,const SVFVar*> CSToRetMap;
    typedef Map<const SVFFunction*,const SVFVar*> FunToRetMap;
    typedef Map<const SVFFunction*,SVFStmtSet> FunToPAGEdgeSetMap;
    typedef Map<const ICFGNode*,SVFStmtList> ICFGNode2SVFStmtsMap;
    typedef Map<NodeID, NodeID> NodeToNodeMap;
    typedef std::pair<NodeID, APOffset> NodeOffset;
    typedef std::pair<NodeID, AccessPath> NodeAccessPath;
    typedef Map<NodeOffset,NodeID> NodeOffsetMap;
    typedef Map<NodeAccessPath,NodeID> NodeAccessPathMap;
    typedef Map<const SVFValue*, NodeAccessPathMap> GepValueVarMap;
    typedef std::pair<const SVFType*, std::vector<AccessPath>> SVFTypeLocSetsPair;
    typedef Map<NodeID, SVFTypeLocSetsPair> TypeLocSetsMap;
    typedef Map<NodePair,NodeID> NodePairSetMap;
 
private:
    ICFGNode2SVFStmtsMap icfgNode2SVFStmtsMap;  
    ICFGNode2SVFStmtsMap icfgNode2PTASVFStmtsMap;   
    GepValueVarMap GepValObjMap;    
    TypeLocSetsMap typeLocSetsMap;  
    NodeOffsetMap GepObjVarMap; 
    MemObjToFieldsMap memToFieldsMap;   
    SVFStmtSet globSVFStmtSet;  
    PHINodeMap phiNodeMap;  
    FunToArgsListMap funArgsListMap;    
    CSToArgsListMap callSiteArgsListMap;    
    CSToRetMap callSiteRetMap;  
    FunToRetMap funRetMap;  
    CallSiteToFunPtrMap indCallSiteToFunPtrMap; 
    FunPtrToCallSitesMap funPtrToCallSitesMap;  
    OrderedNodeSet candidatePointers;
    SVFModule* svfModule; 
    ICFG* icfg; // ICFG
    CommonCHGraph* chgraph; // class hierarchy graph
    CallSiteSet callSiteSet; 
    PTACallGraph* callGraph; 
 
    static std::unique_ptr<SVFIR> pag;  
 
    SVFIR(bool buildFromFile);
 
    void destroy();
 
public:
 
 
    static inline SVFIR* getPAG(bool buildFromFile = false)
    {
        if (pag == nullptr)
        {
            pag = std::unique_ptr<SVFIR>(new SVFIR(buildFromFile));
        }
        return pag.get();
    }
    static void releaseSVFIR()
    {
        pag = nullptr;
    }
    inline MemObjToFieldsMap& getMemToFieldsMap()
    {
        return memToFieldsMap;
    }
    inline NodeOffsetMap& getGepObjNodeMap()
    {
        return GepObjVarMap;
    }
    inline OrderedNodeSet& getAllValidPtrs()
    {
        return candidatePointers;
    }
    void initialiseCandidatePointers();
 
    virtual ~SVFIR()
    {
        destroy();
    }
 
    static void handleBlackHole(bool b);
    inline void setModule(SVFModule* mod)
    {
        svfModule = mod;
    }
    inline SVFModule* getModule()
    {
        assert(svfModule && "empty SVFModule! Build SVF IR first!");
        return svfModule;
    }
    inline void setICFG(ICFG* i)
    {
        icfg = i;
    }
    inline ICFG* getICFG() const
    {
        assert(icfg->totalICFGNode>0 && "empty ICFG! Build SVF IR first!");
        return icfg;
    }
    inline void setCHG(CommonCHGraph* c)
    {
        chgraph = c;
    }
    inline CommonCHGraph* getCHG()
    {
        assert(chgraph && "empty ICFG! Build SVF IR first!");
        return chgraph;
    }
 
    inline void setCallGraph(PTACallGraph* c)
    {
        callGraph = c;
    }
    inline PTACallGraph* getCallGraph()
    {
        assert(callGraph && "empty PTACallGraph! Build SVF IR first!");
        return callGraph;
    }
 
 
    inline SVFStmt::SVFStmtSetTy& getSVFStmtSet(SVFStmt::PEDGEK kind)
    {
        return KindToSVFStmtSetMap[kind];
    }
    inline SVFStmt::SVFStmtSetTy& getPTASVFStmtSet(SVFStmt::PEDGEK kind)
    {
        return KindToPTASVFStmtSetMap[kind];
    }
    inline bool hasSVFStmtList(const ICFGNode* inst) const
    {
        return icfgNode2SVFStmtsMap.find(inst) != icfgNode2SVFStmtsMap.end();
    }
    inline bool hasPTASVFStmtList(const ICFGNode* inst) const
    {
        return icfgNode2PTASVFStmtsMap.find(inst) !=
               icfgNode2PTASVFStmtsMap.end();
    }
    inline SVFStmtList& getSVFStmtList(const ICFGNode* inst)
    {
        return icfgNode2SVFStmtsMap[inst];
    }
    inline SVFStmtList& getPTASVFStmtList(const ICFGNode* inst)
    {
        return icfgNode2PTASVFStmtsMap[inst];
    }
    inline void addToSVFStmtList(ICFGNode* inst, SVFStmt* edge)
    {
        edge->setICFGNode(inst);
        icfgNode2SVFStmtsMap[inst].push_back(edge);
        if (edge->isPTAEdge())
            icfgNode2PTASVFStmtsMap[inst].push_back(edge);
    }
    inline void addToTypeLocSetsMap(NodeID argId, SVFTypeLocSetsPair& locSets)
    {
        typeLocSetsMap[argId]=locSets;
    }
    inline SVFTypeLocSetsPair& getTypeLocSetsMap(NodeID argId)
    {
        return typeLocSetsMap[argId];
    }
    inline SVFStmtSet& getGlobalSVFStmtSet()
    {
        return globSVFStmtSet;
    }
    inline const CallSiteSet& getCallSiteSet() const
    {
        return callSiteSet;
    }
    inline bool isPhiNode(const SVFVar* node) const
    {
        return phiNodeMap.find(node) != phiNodeMap.end();
    }
 
    inline bool hasFunArgsList(const SVFFunction* func) const
    {
        return (funArgsListMap.find(func) != funArgsListMap.end());
    }
    inline FunToArgsListMap& getFunArgsMap()
    {
        return funArgsListMap;
    }
    inline const SVFVarList& getFunArgsList(const SVFFunction*  func) const
    {
        FunToArgsListMap::const_iterator it = funArgsListMap.find(func);
        assert(it != funArgsListMap.end() && "this function doesn't have arguments");
        return it->second;
    }
    inline bool hasCallSiteArgsMap(const CallICFGNode* cs) const
    {
        return (callSiteArgsListMap.find(cs) != callSiteArgsListMap.end());
    }
    inline CSToArgsListMap& getCallSiteArgsMap()
    {
        return callSiteArgsListMap;
    }
    inline const SVFVarList& getCallSiteArgsList(const CallICFGNode* cs) const
    {
        CSToArgsListMap::const_iterator it = callSiteArgsListMap.find(cs);
        assert(it != callSiteArgsListMap.end() && "this call site doesn't have arguments");
        return it->second;
    }
    inline CSToRetMap& getCallSiteRets()
    {
        return callSiteRetMap;
    }
    inline const SVFVar* getCallSiteRet(const RetICFGNode* cs) const
    {
        CSToRetMap::const_iterator it = callSiteRetMap.find(cs);
        assert(it != callSiteRetMap.end() && "this call site doesn't have return");
        return it->second;
    }
    inline bool callsiteHasRet(const RetICFGNode* cs) const
    {
        return callSiteRetMap.find(cs) != callSiteRetMap.end();
    }
    inline FunToRetMap& getFunRets()
    {
        return funRetMap;
    }
    inline const SVFVar* getFunRet(const SVFFunction*  func) const
    {
        FunToRetMap::const_iterator it = funRetMap.find(func);
        assert(it != funRetMap.end() && "this function doesn't have return");
        return it->second;
    }
    inline bool funHasRet(const SVFFunction* func) const
    {
        return funRetMap.find(func) != funRetMap.end();
    }
 
 
    inline u32_t getFieldValNodeNum() const
    {
        return GepValObjMap.size();
    }
    inline u32_t getFieldObjNodeNum() const
    {
        return GepObjVarMap.size();
    }
 
    NodeID getGepValVar(const SVFValue* curInst, NodeID base,
                        const AccessPath& ap) const;
 
 
    inline const CallSiteToFunPtrMap& getIndirectCallsites() const
    {
        return indCallSiteToFunPtrMap;
    }
    inline NodeID getFunPtr(const CallICFGNode* cs) const
    {
        CallSiteToFunPtrMap::const_iterator it = indCallSiteToFunPtrMap.find(cs);
        assert(it!=indCallSiteToFunPtrMap.end() && "indirect callsite not have a function pointer?");
        return it->second;
    }
    inline const CallSiteSet& getIndCallSites(NodeID funPtr) const
    {
        FunPtrToCallSitesMap::const_iterator it = funPtrToCallSitesMap.find(funPtr);
        assert(it!=funPtrToCallSitesMap.end() && "function pointer not used at any indirect callsite?");
        return it->second;
    }
    inline bool isIndirectCallSites(const CallICFGNode* cs) const
    {
        return (indCallSiteToFunPtrMap.find(cs) != indCallSiteToFunPtrMap.end());
    }
    inline bool isFunPtr(NodeID id) const
    {
        return (funPtrToCallSitesMap.find(id) != funPtrToCallSitesMap.end());
    }
 
    inline SVFStmt* getIntraPAGEdge(NodeID src, NodeID dst, SVFStmt::PEDGEK kind)
    {
        return getIntraPAGEdge(getGNode(src), getGNode(dst), kind);
    }
    inline SVFStmt* getIntraPAGEdge(SVFVar* src, SVFVar* dst, SVFStmt::PEDGEK kind)
    {
        SVFStmt edge(src, dst, kind, false);
        const SVFStmt::SVFStmtSetTy& edgeSet = getSVFStmtSet(kind);
        SVFStmt::SVFStmtSetTy::const_iterator it = edgeSet.find(&edge);
        assert(it != edgeSet.end() && "can not find pag edge");
        return (*it);
    }
 
 
    inline const MemObj* getObject(NodeID id) const
    {
        const SVFVar* node = getGNode(id);
        if (const ObjVar* objPN = SVFUtil::dyn_cast<ObjVar>(node))
            return getObject(objPN);
        else
            return nullptr;
    }
    inline const MemObj*getObject(const ObjVar* node) const
    {
        return node->getMemObj();
    }
 
    NodeID getGepObjVar(const MemObj* obj, const APOffset& ap);
    NodeID getGepObjVar(NodeID id, const APOffset& ap) ;
 
    inline NodeID getFIObjVar(const MemObj* obj) const
    {
        return obj->getId();
    }
    inline NodeID getFIObjVar(NodeID id) const
    {
        return getBaseObjVar(id);
    }
 
 
    inline bool isBlkPtr(NodeID id) const
    {
        return (SymbolTableInfo::isBlkPtr(id));
    }
    inline bool isNullPtr(NodeID id) const
    {
        return (SymbolTableInfo::isNullPtr(id));
    }
    inline bool isBlkObjOrConstantObj(NodeID id) const
    {
        return (isBlkObj(id) || isConstantObj(id));
    }
    inline bool isBlkObj(NodeID id) const
    {
        return SymbolTableInfo::isBlkObj(id);
    }
    inline bool isConstantObj(NodeID id) const
    {
        const MemObj* obj = getObject(id);
        assert(obj && "not an object node?");
        return SymbolTableInfo::isConstantObj(id) ||
               obj->isConstDataOrConstGlobal();
    }
 
 
    inline NodeID getBaseObjVar(NodeID id) const
    {
        return getBaseObj(id)->getId();
    }
    inline const MemObj* getBaseObj(NodeID id) const
    {
        const SVFVar* node = pag->getGNode(id);
        assert(SVFUtil::isa<ObjVar>(node) && "need an object node");
        const ObjVar* obj = SVFUtil::cast<ObjVar>(node);
        return obj->getMemObj();
    }
 
 
    NodeBS& getAllFieldsObjVars(const MemObj* obj);
    NodeBS& getAllFieldsObjVars(NodeID id);
    NodeBS getFieldsAfterCollapse(NodeID id);
    inline NodeID addDummyValNode()
    {
        return addDummyValNode(NodeIDAllocator::get()->allocateValueId());
    }
    inline NodeID addDummyObjNode(const SVFType* type)
    {
        return addDummyObjNode(NodeIDAllocator::get()->allocateObjectId(), type);
    }
 
    bool isValidPointer(NodeID nodeId) const;
 
    bool isValidTopLevelPtr(const SVFVar* node);
 
    void print();
 
private:
 
    inline void addToStmt2TypeMap(SVFStmt* edge)
    {
        bool added = KindToSVFStmtSetMap[edge->getEdgeKind()].insert(edge).second;
        (void)added; // Suppress warning of unused variable under release build
        assert(added && "duplicated edge, not added!!!");
        if (edge->isPTAEdge() || (SVFUtil::isa<CopyStmt>(edge) && SVFUtil::cast<CopyStmt>(edge)->isInt2Ptr()))
        {
            totalPTAPAGEdge++;
            KindToPTASVFStmtSetMap[edge->getEdgeKind()].insert(edge);
        }
    }
 
    inline void addFunArgs(const SVFFunction* fun, const SVFVar* arg)
    {
        FunEntryICFGNode* funEntryBlockNode = icfg->getFunEntryICFGNode(fun);
        funEntryBlockNode->addFormalParms(arg);
        funArgsListMap[fun].push_back(arg);
    }
    inline void addFunRet(const SVFFunction* fun, const SVFVar* ret)
    {
        FunExitICFGNode* funExitBlockNode = icfg->getFunExitICFGNode(fun);
        funExitBlockNode->addFormalRet(ret);
        funRetMap[fun] = ret;
    }
    inline void addCallSiteArgs(CallICFGNode* callBlockNode,const SVFVar* arg)
    {
        callBlockNode->addActualParms(arg);
        callSiteArgsListMap[callBlockNode].push_back(arg);
    }
    inline void addCallSiteRets(RetICFGNode* retBlockNode,const SVFVar* arg)
    {
        retBlockNode->addActualRet(arg);
        callSiteRetMap[retBlockNode]= arg;
    }
    inline void addIndirectCallsites(const CallICFGNode* cs,NodeID funPtr)
    {
        bool added = indCallSiteToFunPtrMap.emplace(cs, funPtr).second;
        (void) added;
        funPtrToCallSitesMap[funPtr].insert(cs);
        assert(added && "adding the same indirect callsite twice?");
    }
 
 
    inline NodeID addValNode(const SVFValue* val, NodeID i, const SVFBaseNode* gNode)
    {
        SVFVar *node = new ValVar(val,i, ValVar::ValNode, gNode);
        return addValNode(val, node, i);
    }
    inline NodeID addObjNode(const SVFValue* val, NodeID i)
    {
        const MemObj* mem = getMemObj(val);
        assert(mem->getId() == i && "not same object id?");
        return addFIObjNode(mem);
    }
    inline NodeID addRetNode(const SVFFunction* val, NodeID i)
    {
        SVFVar *node = new RetPN(val,i);
        return addRetNode(val, node, i);
    }
    inline NodeID addVarargNode(const SVFFunction* val, NodeID i)
    {
        SVFVar *node = new VarArgPN(val,i);
        return addNode(node,i);
    }
 
    NodeID addGepValNode(const SVFValue* curInst,const SVFValue* val, const AccessPath& ap, NodeID i, const SVFType* type);
    NodeID addGepObjNode(const MemObj* obj, const APOffset& apOffset, const NodeID gepId);
    NodeID addFIObjNode(const MemObj* obj);
 
 
    inline NodeID addDummyValNode(NodeID i)
    {
        return addValNode(nullptr, new DummyValVar(i), i);
    }
    inline NodeID addDummyObjNode(NodeID i, const SVFType* type)
    {
        const MemObj* mem = addDummyMemObj(i, type);
        return addObjNode(nullptr, new DummyObjVar(i,mem), i);
    }
    inline const MemObj* addDummyMemObj(NodeID i, const SVFType* type)
    {
        return getSymbolInfo()->createDummyObj(i,type);
    }
    inline NodeID addBlackholeObjNode()
    {
        return addObjNode(
                   nullptr, new DummyObjVar(getBlackHoleNode(), getBlackHoleObj()),
                   getBlackHoleNode());
    }
    inline NodeID addConstantObjNode()
    {
        return addObjNode(nullptr,
                          new DummyObjVar(getConstantNode(), getConstantObj()),
                          getConstantNode());
    }
    inline NodeID addBlackholePtrNode()
    {
        return addDummyValNode(getBlkPtr());
    }
 
    inline NodeID addValNode(const SVFValue*, SVFVar *node, NodeID i)
    {
        assert(hasGNode(i) == false &&
               "This NodeID clashes here. Please check NodeIDAllocator. Switch "
               "Strategy::DBUG to SEQ or DENSE");
        return addNode(node, i);
    }
    inline NodeID addObjNode(const SVFValue*, SVFVar *node, NodeID i)
    {
        assert(hasGNode(i) == false &&
               "This NodeID clashes here. Please check NodeIDAllocator. Switch "
               "Strategy::DBUG to SEQ or DENSE");
        return addNode(node, i);
    }
    inline NodeID addRetNode(const SVFFunction*, SVFVar *node, NodeID i)
    {
        return addNode(node,i);
    }
    inline NodeID addVarargNode(const SVFFunction*, SVFVar *node, NodeID i)
    {
        return addNode(node,i);
    }
 
    inline void addGlobalPAGEdge(const SVFStmt* edge)
    {
        globSVFStmtSet.insert(edge);
    }
    inline void addCallSite(const CallICFGNode* call)
    {
        callSiteSet.insert(call);
    }
 
    AddrStmt* addAddrStmt(NodeID src, NodeID dst);
    CopyStmt* addCopyStmt(NodeID src, NodeID dst, CopyStmt::CopyKind type);
 
    PhiStmt*  addPhiStmt(NodeID res, NodeID opnd, const ICFGNode* pred);
    SelectStmt*  addSelectStmt(NodeID res, NodeID op1, NodeID op2, NodeID cond);
    CmpStmt* addCmpStmt(NodeID op1, NodeID op2, NodeID dst, u32_t predict);
    BinaryOPStmt* addBinaryOPStmt(NodeID op1, NodeID op2, NodeID dst,
                                  u32_t opcode);
    UnaryOPStmt* addUnaryOPStmt(NodeID src, NodeID dst, u32_t opcode);
    BranchStmt* addBranchStmt(NodeID br, NodeID cond,
                              const BranchStmt::SuccAndCondPairVec& succs);
    LoadStmt* addLoadStmt(NodeID src, NodeID dst);
    StoreStmt* addStoreStmt(NodeID src, NodeID dst, const ICFGNode* val);
    CallPE* addCallPE(NodeID src, NodeID dst, const CallICFGNode* cs,
                      const FunEntryICFGNode* entry);
    RetPE* addRetPE(NodeID src, NodeID dst, const CallICFGNode* cs,
                    const FunExitICFGNode* exit);
    GepStmt* addGepStmt(NodeID src, NodeID dst, const AccessPath& ap,
                        bool constGep);
    GepStmt* addNormalGepStmt(NodeID src, NodeID dst, const AccessPath& ap);
    GepStmt* addVariantGepStmt(NodeID src, NodeID dst, const AccessPath& ap);
    TDForkPE* addThreadForkPE(NodeID src, NodeID dst, const CallICFGNode* cs,
                              const FunEntryICFGNode* entry);
    TDJoinPE* addThreadJoinPE(NodeID src, NodeID dst, const CallICFGNode* cs,
                              const FunExitICFGNode* exit);
 
    SVFStmt* addBlackHoleAddrStmt(NodeID node);
};
 
typedef SVFIR PAG;
 
} // End namespace SVF
 
 
 
#endif /* INCLUDE_SVFIR_H_ */