MSSAMuChi.h

Go to the documentation of this file.

//===- MSSAMuChi.h -- Mu/Chi on MSSA------------------------------------------//
//
//                     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/>.
//
//===----------------------------------------------------------------------===//
 
/*
 * MSSAMuChi.h
 *
 *  Created on: Oct 31, 2013
 *      Author: Yulei Sui
 */
 
#ifndef MSSAMUCHI_H_
#define MSSAMUCHI_H_
 
#include "MSSA/MemRegion.h"
 
namespace SVF
{
 
class MSSADEF;
 
class MRVer
{
 
public:
    typedef MSSADEF MSSADef;
private:
    static u32_t totalVERNum;
    const MemRegion* mr;
    MRVERSION version;
    MRVERID vid;
    MSSADef* def;
public:
    MRVer(const MemRegion* m, MRVERSION v, MSSADef* d) :
        mr(m), version(v), vid(totalVERNum++),def(d)
    {
    }
 
    inline const MemRegion* getMR() const
    {
        return mr;
    }
 
    inline MRVERSION getSSAVersion() const
    {
        return version;
    }
 
    inline MSSADef* getDef() const
    {
        return def;
    }
 
    inline MRVERID getID() const
    {
        return vid;
    }
};
 
 
template<class Cond>
class MSSAMU
{
 
public:
    enum MUTYPE
    {
        LoadMSSAMU, CallMSSAMU, RetMSSAMU
    };
 
protected:
    MUTYPE type;
    const MemRegion* mr;
    MRVer* ver;
    Cond cond;
public:
 
    MSSAMU(MUTYPE t, const MemRegion* m, Cond c) : type(t), mr(m), ver(nullptr), cond(c)
    {
    }
    virtual ~MSSAMU()
    {
    }
 
    inline const MemRegion* getMR() const
    {
        return mr;
    }
    inline MUTYPE getType() const
    {
        return type;
    }
    inline void setVer(MRVer* v)
    {
        assert(v->getMR() == mr && "inserting different memory region?");
        ver = v;
    }
    inline MRVer* getMRVer() const
    {
        assert(ver!=nullptr && "version is nullptr, did not rename?");
        return ver;
    }
    inline Cond getCond() const
    {
        return cond;
    }
 
    inline bool operator < (const MSSAMU & rhs) const
    {
        return mr > rhs.getMR();
    }
    virtual void dump()
    {
        SVFUtil::outs() << "MU(MR_" << mr->getMRID() << "V_" << ver->getSSAVersion() << ") \t" <<
                        this->getMR()->dumpStr() << "\n";
    }
};
 
template<class Cond>
class LoadMU : public MSSAMU<Cond>
{
 
private:
    const LoadStmt* inst;
    const SVFBasicBlock* bb;
 
public:
 
    LoadMU(const SVFBasicBlock* b,const LoadStmt* i, const MemRegion* m, Cond c = true) :
        MSSAMU<Cond>(MSSAMU<Cond>::LoadMSSAMU,m,c), inst(i), bb(b)
    {
    }
    virtual ~LoadMU()
    {
 
    }
 
    inline const LoadStmt* getLoadStmt() const
    {
        return inst;
    }
 
    inline const SVFBasicBlock* getBasicBlock() const
    {
        return bb;
    }
 
 
    static inline bool classof(const LoadMU *)
    {
        return true;
    }
    static inline bool classof(const MSSAMU<Cond> *mu)
    {
        return mu->getType() == MSSAMU<Cond>::LoadMSSAMU;
    }
 
    virtual void dump()
    {
        SVFUtil::outs() << "LDMU(MR_" << this->getMR()->getMRID() << "V_" << this->getMRVer()->getSSAVersion() << ") \t" <<
                        this->getMR()->dumpStr() << "\n";
    }
};
 
template<class Cond>
class CallMU : public MSSAMU<Cond>
{
 
private:
    const CallICFGNode* callsite;
 
public:
 
    CallMU(const CallICFGNode* cs, const MemRegion* m, Cond c = true) :
        MSSAMU<Cond>(MSSAMU<Cond>::CallMSSAMU,m,c), callsite(cs)
    {
    }
    virtual ~CallMU()
    {
 
    }
 
    inline const CallICFGNode* getCallSite() const
    {
        return callsite;
    }
 
    inline const SVFBasicBlock* getBasicBlock() const
    {
        return callsite->getBB();
    }
 
 
    static inline bool classof(const CallMU *)
    {
        return true;
    }
    static inline bool classof(const MSSAMU<Cond> *mu)
    {
        return mu->getType() == MSSAMU<Cond>::CallMSSAMU;
    }
 
    virtual void dump()
    {
        SVFUtil::outs() << "CALMU(MR_" << this->getMR()->getMRID() << "V_" << this->getMRVer()->getSSAVersion() << ") \t" <<
                        this->getMR()->dumpStr() << "\n";
    }
};
 
 
template<class Cond>
class RetMU : public MSSAMU<Cond>
{
private:
    const SVFFunction* fun;
public:
 
    RetMU(const SVFFunction* f, const MemRegion* m, Cond c = true) :
        MSSAMU<Cond>(MSSAMU<Cond>::RetMSSAMU,m,c), fun(f)
    {
    }
    virtual ~RetMU() {}
 
    inline const SVFFunction* getFunction() const
    {
        return fun;
    }
 
 
    static inline bool classof(const RetMU *)
    {
        return true;
    }
    static inline bool classof(const MSSAMU<Cond> *mu)
    {
        return mu->getType() == MSSAMU<Cond>::RetMSSAMU;
    }
 
    virtual void dump()
    {
        SVFUtil::outs() << "RETMU(MR_" << this->getMR()->getMRID() << "V_" << this->getMRVer()->getSSAVersion() << ") \t" <<
                        this->getMR()->dumpStr() << "\n";
    }
};
 
 
class MSSADEF
{
 
public:
    enum DEFTYPE
    {
        SSACHI,
        StoreMSSACHI,
        CallMSSACHI,
        EntryMSSACHI,
        SSAPHI
    };
 
protected:
    DEFTYPE type;
    const MemRegion* mr;
    MRVer* resVer;
 
public:
 
    MSSADEF(DEFTYPE t, const MemRegion* m): type(t), mr(m), resVer(nullptr)
    {
 
    }
    virtual ~MSSADEF() {}
 
    inline const MemRegion* getMR() const
    {
        return mr;
    }
 
    inline DEFTYPE getType() const
    {
        return type;
    }
 
    inline void setResVer(MRVer* v)
    {
        assert(v->getMR() == mr && "inserting different memory region?");
        resVer = v;
    }
 
    inline MRVer* getResVer() const
    {
        assert(resVer!=nullptr && "version is nullptr, did not rename?");
        return resVer;
    }
 
    inline bool operator < (const MSSADEF & rhs) const
    {
        return mr > rhs.getMR();
    }
 
    virtual void dump()
    {
        SVFUtil::outs() << "DEF(MR_" << mr->getMRID() << "V_" << resVer->getSSAVersion() << ")\n";
    }
};
 
template<class Cond>
class MSSACHI : public MSSADEF
{
 
private:
    MRVer* opVer;
    Cond cond;
public:
    typedef typename MSSADEF::DEFTYPE CHITYPE;
 
    MSSACHI(CHITYPE t, const MemRegion* m, Cond c): MSSADEF(t,m), opVer(nullptr), cond(c)
    {
 
    }
    virtual ~MSSACHI() {}
 
    inline void setOpVer(MRVer* v)
    {
        assert(v->getMR() == this->getMR() && "inserting different memory region?");
        opVer = v;
    }
 
    inline MRVer* getOpVer() const
    {
        assert(opVer!=nullptr && "version is nullptr, did not rename?");
        return opVer;
    }
 
    inline Cond getCond() const
    {
        return cond;
    }
 
 
    static inline bool classof(const MSSACHI * chi)
    {
        return true;
    }
    static inline bool classof(const MSSADEF *chi)
    {
        return chi->getType() == MSSADEF::EntryMSSACHI ||
               chi->getType() == MSSADEF::StoreMSSACHI ||
               chi->getType() == MSSADEF::SSACHI ;
    }
 
    virtual void dump()
    {
        SVFUtil::outs() << "MR_" << this->getMR()->getMRID() << "V_" << this->getResVer()->getSSAVersion() <<
                        " = CHI(MR_" << this->getMR()->getMRID() << "V_" << opVer->getSSAVersion() << ") \t" <<
                        this->getMR()->dumpStr() << "\n";
    }
};
 
template<class Cond>
class StoreCHI : public MSSACHI<Cond>
{
private:
    const SVFBasicBlock* bb;
    const StoreStmt* inst;
public:
 
    StoreCHI(const SVFBasicBlock* b, const StoreStmt* i, const MemRegion* m, Cond c = true) :
        MSSACHI<Cond>(MSSADEF::StoreMSSACHI,m,c), bb(b), inst(i)
    {
    }
    virtual ~StoreCHI()
    {
    }
 
    inline const SVFBasicBlock* getBasicBlock() const
    {
        return bb;
    }
 
    inline const StoreStmt* getStoreStmt() const
    {
        return inst;
    }
 
 
    static inline bool classof(const StoreCHI * chi)
    {
        return true;
    }
    static inline bool classof(const MSSACHI<Cond> * chi)
    {
        return chi->getType() == MSSADEF::StoreMSSACHI;
    }
    static inline bool classof(const MSSADEF *chi)
    {
        return chi->getType() == MSSADEF::StoreMSSACHI;
    }
 
    virtual void dump()
    {
        SVFUtil::outs() << this->getMR()->getMRID() << "V_" << this->getResVer()->getSSAVersion() <<
                        " = STCHI(MR_" << this->getMR()->getMRID() << "V_" << this->getOpVer()->getSSAVersion() << ") \t" <<
                        this->getMR()->dumpStr() << "\n";
    }
};
 
 
template<class Cond>
class CallCHI : public MSSACHI<Cond>
{
private:
    const CallICFGNode* callsite;
public:
 
    CallCHI(const CallICFGNode* cs, const MemRegion* m, Cond c = true) :
        MSSACHI<Cond>(MSSADEF::CallMSSACHI,m,c), callsite(cs)
    {
    }
    virtual ~CallCHI()
    {
    }
 
    inline const SVFBasicBlock* getBasicBlock() const
    {
        return callsite->getBB();
    }
 
    inline const CallICFGNode* getCallSite() const
    {
        return callsite;
    }
 
 
    static inline bool classof(const CallCHI * chi)
    {
        return true;
    }
    static inline bool classof(const MSSACHI<Cond> * chi)
    {
        return chi->getType() == MSSADEF::CallMSSACHI;
    }
    static inline bool classof(const MSSADEF *chi)
    {
        return chi->getType() == MSSADEF::CallMSSACHI;
    }
 
    virtual void dump()
    {
        SVFUtil::outs() << this->getMR()->getMRID() << "V_" << this->getResVer()->getSSAVersion() <<
                        " = CALCHI(MR_" << this->getMR()->getMRID() << "V_" << this->getOpVer()->getSSAVersion() << ") \t" <<
                        this->getMR()->dumpStr() << "\n";
    }
};
 
template<class Cond>
class EntryCHI : public MSSACHI<Cond>
{
private:
    const SVFFunction* fun;
public:
 
    EntryCHI(const SVFFunction* f, const MemRegion* m, Cond c = true) :
        MSSACHI<Cond>(MSSADEF::EntryMSSACHI,m,c),fun(f)
    {
    }
    virtual ~EntryCHI()
    {
    }
 
    inline const SVFFunction* getFunction() const
    {
        return fun;
    }
 
 
    static inline bool classof(const EntryCHI * chi)
    {
        return true;
    }
    static inline bool classof(const MSSACHI<Cond> * chi)
    {
        return chi->getType() == MSSADEF::EntryMSSACHI;
    }
    static inline bool classof(const MSSADEF *chi)
    {
        return chi->getType() == MSSADEF::EntryMSSACHI;
    }
 
    virtual void dump()
    {
        SVFUtil::outs() << this->getMR()->getMRID() << "V_" << this->getResVer()->getSSAVersion() <<
                        " = ENCHI(MR_" << this->getMR()->getMRID() << "V_" << this->getOpVer()->getSSAVersion() << ") \t" <<
                        this->getMR()->dumpStr() << "\n";
    }
};
 
/*
 * Memory SSA Select, similar to PHINode
 */
template<class Cond>
class MSSAPHI : public MSSADEF
{
 
public:
    typedef Map<u32_t,const MRVer*> OPVers;
private:
    const SVFBasicBlock* bb;
    OPVers opVers;
    Cond cond;
public:
 
    MSSAPHI(const SVFBasicBlock* b, const MemRegion* m, Cond c = true) :
        MSSADEF(MSSADEF::SSAPHI,m), bb(b), cond(c)
    {
    }
    virtual ~MSSAPHI()
    {
    }
 
    inline void setOpVer(const MRVer* v, u32_t pos)
    {
        assert(v->getMR() == this->getMR() && "inserting different memory region?");
        opVers[pos] = v;
    }
 
    inline const MRVer* getOpVer(u32_t pos) const
    {
        OPVers::const_iterator it = opVers.find(pos);
        assert(it!=opVers.end() && "version is nullptr, did not rename?");
        return it->second;
    }
 
    inline u32_t getOpVerNum() const
    {
        return opVers.size();
    }
 
 
    inline OPVers::const_iterator opVerBegin() const
    {
        return opVers.begin();
    }
    inline OPVers::const_iterator opVerEnd() const
    {
        return opVers.end();
    }
 
    inline const SVFBasicBlock* getBasicBlock() const
    {
        return bb;
    }
 
    inline Cond getCond() const
    {
        return cond;
    }
 
 
    static inline bool classof(const MSSAPHI * phi)
    {
        return true;
    }
    static inline bool classof(const MSSADEF *phi)
    {
        return phi->getType() == MSSADEF::SSAPHI ;
    }
 
    virtual void dump()
    {
        SVFUtil::outs() << this->getMR()->getMRID() << "V_" << this->getResVer()->getSSAVersion() <<
                        " = PHI(";
        for(OPVers::iterator it = opVers.begin(), eit = opVers.end(); it!=eit; ++it)
            SVFUtil::outs() << "MR_" << this->getMR()->getMRID() << "V_" << it->second->getSSAVersion() << ", ";
 
        SVFUtil::outs() << ")\n";
    }
};
 
std::ostream& operator<<(std::ostream &o, const MRVer& mrver);
} // End namespace SVF
 
#endif /* MSSAMUCHI_H_ */