MemRegion.h

Go to the documentation of this file.

//===- MemRegion.h -- Memory region -----------------------------------------//
//
//                     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/>.
//
//===----------------------------------------------------------------------===//
 
/*
 * MemoryRegion.h
 *
 *  Created on: Jul 14, 2013
 *      Author: Yulei Sui
 * The implementation is based on
 * Yulei Sui, Hua Yan, Yunpeng Zhang, Jingling Xue and Zheng Zheng.
 * "Parallel Construction of Interprocedural Memory SSA Form".
 * Journal of Systems and Software (JSS'16)
 */
 
#ifndef MEMORYREGION_H_
#define MEMORYREGION_H_
 
#include "Graphs/ICFG.h"
#include "Graphs/PTACallGraph.h"
#include "Graphs/SCC.h"
#include "SVFIR/SVFIR.h"
#include "Util/WorkList.h"
 
#include <set>
 
namespace SVF
{
 
class BVDataPTAImpl;
 
typedef NodeID MRID;
typedef NodeID MRVERID;
typedef NodeID MRVERSION;
 
class MemRegion
{
 
public:
    typedef bool Condition;
private:
    static u32_t totalMRNum;
    MRID rid;
    const NodeBS cptsSet;
 
public:
    MemRegion(const NodeBS& cp) :
        rid(++totalMRNum), cptsSet(cp)
    {
    }
    ~MemRegion()
    {
    }
 
    inline MRID getMRID() const
    {
        return rid;
    }
    inline const NodeBS &getPointsTo() const
    {
        return cptsSet;
    }
    inline bool operator==(const MemRegion* rhs) const
    {
        return this->getPointsTo() == rhs->getPointsTo();
    }
    inline std::string dumpStr() const
    {
        std::string str;
        str += "pts{";
        for (NodeBS::iterator ii = cptsSet.begin(), ie = cptsSet.end();
                ii != ie; ii++)
        {
            char int2str[16];
            snprintf(int2str, sizeof(int2str), "%d", *ii);
            str += int2str;
            str += " ";
        }
        str += "}";
        return str;
    }
 
 
    typedef struct equalMemRegion
    {
        bool operator()(const MemRegion* lhs, const MemRegion* rhs) const
        {
            return SVFUtil::cmpNodeBS(lhs->getPointsTo(), rhs->getPointsTo());
        }
    } equalMemRegion;
 
    inline u32_t getRegionSize() const
    {
        return cptsSet.count();
    }
};
 
class MRGenerator
{
 
public:
    typedef FIFOWorkList<NodeID> WorkList;
 
 
 
 
    typedef OrderedSet<const MemRegion*, MemRegion::equalMemRegion> MRSet;
    typedef Map<const PAGEdge*, const SVFFunction*> PAGEdgeToFunMap;
    typedef OrderedSet<NodeBS, SVFUtil::equalNodeBS> PointsToList;
    typedef Map<const SVFFunction*, NodeBS> FunToPointsToMap;
    typedef Map<const SVFFunction*, PointsToList> FunToPointsTosMap;
    typedef OrderedMap<NodeBS, NodeBS, SVFUtil::equalNodeBS> PtsToRepPtsSetMap;
 
    typedef Map<const SVFFunction*, MRSet> FunToMRsMap;
 
    typedef Map<const LoadStmt*, MRSet> LoadsToMRsMap;
    typedef Map<const StoreStmt*, MRSet> StoresToMRsMap;
    typedef Map<const CallICFGNode*, MRSet> CallSiteToMRsMap;
 
 
    typedef Map<const LoadStmt*, NodeBS> LoadsToPointsToMap;
    typedef Map<const StoreStmt*, NodeBS> StoresToPointsToMap;
    typedef Map<const CallICFGNode*, NodeBS> CallSiteToPointsToMap;
 
 
 
    typedef Map<const SVFFunction*, NodeBS> FunToNodeBSMap;
    typedef Map<const CallICFGNode*, NodeBS> CallSiteToNodeBSMap;
 
    typedef Map<NodeID, NodeBS> NodeToPTSSMap;
 
    typedef SVFIR::SVFStmtList SVFStmtList;
    typedef SCCDetection<PTACallGraph*> SCC;
 
    MRSet& getMRSet()
    {
        return memRegSet;
    }
 
    inline const NodeBS& getRepPointsTo(const NodeBS& cpts) const
    {
        PtsToRepPtsSetMap::const_iterator it = cptsToRepCPtsMap.find(cpts);
        assert(it!=cptsToRepCPtsMap.end() && "can not find superset of cpts??");
        return it->second;
    }
    const MemRegion* getMR(const NodeBS& cpts) const;
 
private:
 
    BVDataPTAImpl* pta;
    SCC* callGraphSCC;
    PTACallGraph* callGraph;
    bool ptrOnlyMSSA;
 
    FunToMRsMap funToMRsMap;
    LoadsToMRsMap loadsToMRsMap;
    StoresToMRsMap storesToMRsMap;
    CallSiteToMRsMap callsiteToRefMRsMap;
    CallSiteToMRsMap callsiteToModMRsMap;
    LoadsToPointsToMap loadsToPointsToMap;
    StoresToPointsToMap storesToPointsToMap;
    CallSiteToPointsToMap callsiteToRefPointsToMap;
    CallSiteToPointsToMap callsiteToModPointsToMap;
 
    FunToPointsTosMap funToPointsToMap;
    PAGEdgeToFunMap pagEdgeToFunMap;
 
    FunToPointsToMap funToRefsMap;
    FunToPointsToMap funToModsMap;
    CallSiteToPointsToMap csToRefsMap;
    CallSiteToPointsToMap csToModsMap;
    CallSiteToPointsToMap csToCallSiteArgsPtsMap;
    CallSiteToPointsToMap csToCallSiteRetPtsMap;
 
    NodeToPTSSMap cachedPtsChainMap;
 
    NodeBS allGlobals;
 
    void destroy();
 
    //Get all objects might pass into callee from a callsite
    void collectCallSitePts(const CallICFGNode* cs);
 
    //Recursive collect points-to chain
    NodeBS& CollectPtsChain(NodeID id);
 
    inline NodeBS& getCallSiteArgsPts(const CallICFGNode* cs)
    {
        return csToCallSiteArgsPtsMap[cs];
    }
    inline NodeBS& getCallSiteRetPts(const CallICFGNode* cs)
    {
        return csToCallSiteRetPtsMap[cs];
    }
    bool isNonLocalObject(NodeID id, const SVFFunction* curFun) const;
 
    void getEscapObjviaGlobals(NodeBS& globs, const NodeBS& pts);
 
    void getCallGraphSCCRevTopoOrder(WorkList& worklist);
 
protected:
    MRGenerator(BVDataPTAImpl* p, bool ptrOnly);
 
    MRSet memRegSet;
    PtsToRepPtsSetMap cptsToRepCPtsMap;
 
    void createMR(const SVFFunction* fun, const NodeBS& cpts);
 
    void collectGlobals();
 
    virtual void collectModRefForLoadStore();
 
    virtual void collectModRefForCall();
 
    virtual void partitionMRs();
 
    virtual void updateAliasMRs();
 
    virtual void sortPointsTo(const NodeBS& cpts);
 
    virtual inline bool isAliasedMR(const NodeBS& cpts, const MemRegion* mr)
    {
        return mr->getPointsTo().intersects(cpts);
    }
    virtual inline void getAliasMemRegions(MRSet& aliasMRs, const NodeBS& cpts, const SVFFunction* fun)
    {
        for(MRSet::const_iterator it = funToMRsMap[fun].begin(), eit = funToMRsMap[fun].end(); it!=eit; ++it)
        {
            if(isAliasedMR(cpts,*it))
                aliasMRs.insert(*it);
        }
    }
 
    virtual inline void getMRsForLoad(MRSet& aliasMRs, const NodeBS& cpts, const SVFFunction*)
    {
        const MemRegion* mr = getMR(cpts);
        aliasMRs.insert(mr);
    }
 
    virtual inline void getMRsForCallSiteRef(MRSet& aliasMRs, const NodeBS& cpts, const SVFFunction*)
    {
        const MemRegion* mr = getMR(cpts);
        aliasMRs.insert(mr);
    }
 
    virtual void modRefAnalysis(PTACallGraphNode* callGraphNode, WorkList& worklist);
 
    virtual bool handleCallsiteModRef(NodeBS& mod, NodeBS& ref, const CallICFGNode* cs, const SVFFunction* fun);
 
 
 
    inline void addCPtsToStore(NodeBS& cpts, const StoreStmt *st, const SVFFunction* fun)
    {
        storesToPointsToMap[st] = cpts;
        funToPointsToMap[fun].insert(cpts);
        addModSideEffectOfFunction(fun,cpts);
    }
    inline void addCPtsToLoad(NodeBS& cpts, const LoadStmt *ld, const SVFFunction* fun)
    {
        loadsToPointsToMap[ld] = cpts;
        funToPointsToMap[fun].insert(cpts);
        addRefSideEffectOfFunction(fun,cpts);
    }
    inline void addCPtsToCallSiteRefs(NodeBS& cpts, const CallICFGNode* cs)
    {
        callsiteToRefPointsToMap[cs] |= cpts;
        funToPointsToMap[cs->getCaller()].insert(cpts);
    }
    inline void addCPtsToCallSiteMods(NodeBS& cpts, const CallICFGNode* cs)
    {
        callsiteToModPointsToMap[cs] |= cpts;
        funToPointsToMap[cs->getCaller()].insert(cpts);
    }
    inline bool hasCPtsList(const SVFFunction* fun) const
    {
        return funToPointsToMap.find(fun)!=funToPointsToMap.end();
    }
    inline PointsToList& getPointsToList(const SVFFunction* fun)
    {
        return funToPointsToMap[fun];
    }
    inline FunToPointsTosMap& getFunToPointsToList()
    {
        return funToPointsToMap;
    }
 
 
    void addRefSideEffectOfFunction(const SVFFunction* fun, const NodeBS& refs);
    void addModSideEffectOfFunction(const SVFFunction* fun, const NodeBS& mods);
    bool addRefSideEffectOfCallSite(const CallICFGNode* cs, const NodeBS& refs);
    bool addModSideEffectOfCallSite(const CallICFGNode* cs, const NodeBS& mods);
 
    inline const NodeBS& getRefSideEffectOfFunction(const SVFFunction* fun)
    {
        return funToRefsMap[fun];
    }
    inline const NodeBS& getModSideEffectOfFunction(const SVFFunction* fun)
    {
        return funToModsMap[fun];
    }
    inline const NodeBS& getRefSideEffectOfCallSite(const CallICFGNode* cs)
    {
        return csToRefsMap[cs];
    }
    inline const NodeBS& getModSideEffectOfCallSite(const CallICFGNode* cs)
    {
        return csToModsMap[cs];
    }
    inline bool hasRefSideEffectOfCallSite(const CallICFGNode* cs)
    {
        return csToRefsMap.find(cs) != csToRefsMap.end();
    }
    inline bool hasModSideEffectOfCallSite(const CallICFGNode* cs)
    {
        return csToModsMap.find(cs) != csToModsMap.end();
    }
 
public:
    inline u32_t getMRNum() const
    {
        return memRegSet.size();
    }
 
    virtual ~MRGenerator()
    {
        destroy();
    }
 
    virtual void generateMRs();
 
    const SVFFunction* getFunction(const PAGEdge* pagEdge) const
    {
        PAGEdgeToFunMap::const_iterator it = pagEdgeToFunMap.find(pagEdge);
        assert(it!=pagEdgeToFunMap.end() && "can not find its function, it is a global SVFIR edge");
        return it->second;
    }
 
    inline MRSet& getFunMRSet(const SVFFunction* fun)
    {
        return funToMRsMap[fun];
    }
    inline MRSet& getLoadMRSet(const LoadStmt* load)
    {
        return loadsToMRsMap[load];
    }
    inline MRSet& getStoreMRSet(const StoreStmt* store)
    {
        return storesToMRsMap[store];
    }
    inline bool hasRefMRSet(const CallICFGNode* cs)
    {
        return callsiteToRefMRsMap.find(cs)!=callsiteToRefMRsMap.end();
    }
    inline bool hasModMRSet(const CallICFGNode* cs)
    {
        return callsiteToModMRsMap.find(cs)!=callsiteToModMRsMap.end();
    }
    inline MRSet& getCallSiteRefMRSet(const CallICFGNode* cs)
    {
        return callsiteToRefMRsMap[cs];
    }
    inline MRSet& getCallSiteModMRSet(const CallICFGNode* cs)
    {
        return callsiteToModMRsMap[cs];
    }
 
    bool hasSVFStmtList(const ICFGNode* icfgNode);
    SVFStmtList& getPAGEdgesFromInst(const ICFGNode* node);
 
 
 
    NodeBS getModInfoForCall(const CallICFGNode* cs);
    NodeBS getRefInfoForCall(const CallICFGNode* cs);
    ModRefInfo getModRefInfo(const CallICFGNode* cs);
    ModRefInfo getModRefInfo(const CallICFGNode* cs, const SVFValue* V);
    ModRefInfo getModRefInfo(const CallICFGNode* cs1, const CallICFGNode* cs2);
 
};
 
} // End namespace SVF
 
#endif /* MEMORYREGION_H_ */