PAGEdge.h

Go to the documentation of this file.

//===- PAGEdge.h -- PAG edge class-------------------------------------------//
//
//                     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 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 General Public License for more details.

// You should have received a copy of the GNU General Public License
// along with this program.  If not, see <http://www.gnu.org/licenses/>.
//
//===----------------------------------------------------------------------===//


/*
 * PAGEdge.h
 *
 *  Created on: Nov 10, 2013
 *      Author: Yulei Sui
 */

#ifndef PAGEDGE_H_
#define PAGEDGE_H_

#include "Graphs/GenericGraph.h"
#include "MemoryModel/LocationSet.h"
#include "Graphs/ICFGNode.h"

namespace SVF
{

class PAGNode;

/*
 * PAG edge between nodes
 */
typedef GenericEdge<PAGNode> GenericPAGEdgeTy;
class PAGEdge : public GenericPAGEdgeTy
{

public:
    enum PEDGEK
    {
        Addr, Copy, Store, Load, Call, Ret, NormalGep, VariantGep, ThreadFork, ThreadJoin, Cmp, BinaryOp, UnaryOp
    };

private:
    const Value* value; 
    const BasicBlock *basicBlock;   
    ICFGNode *icfgNode;   
    EdgeID edgeId;                  
public:
    static Size_t totalEdgeNum;     

    PAGEdge(PAGNode* s, PAGNode* d, GEdgeFlag k);
    ~PAGEdge()
    {
    }


    static inline bool classof(const PAGEdge*)
    {
        return true;
    }
    static inline bool classof(const GenericPAGEdgeTy *edge)
    {
        return edge->getEdgeKind() == PAGEdge::Addr ||
               edge->getEdgeKind() == PAGEdge::Copy ||
               edge->getEdgeKind() == PAGEdge::Store ||
               edge->getEdgeKind() == PAGEdge::Load ||
               edge->getEdgeKind() == PAGEdge::Call ||
               edge->getEdgeKind() == PAGEdge::Ret ||
               edge->getEdgeKind() == PAGEdge::NormalGep ||
               edge->getEdgeKind() == PAGEdge::VariantGep ||
               edge->getEdgeKind() == PAGEdge::ThreadFork ||
               edge->getEdgeKind() == PAGEdge::ThreadJoin ||
               edge->getEdgeKind() == PAGEdge::Cmp ||
               edge->getEdgeKind() == PAGEdge::BinaryOp ||
               edge->getEdgeKind() == PAGEdge::UnaryOp;
    }

    inline EdgeID getEdgeID() const
    {
        return edgeId;
    }
    bool isPTAEdge() const;


    inline const Instruction* getInst() const
    {
        return SVFUtil::dyn_cast<Instruction>(value);
    }
    inline void setValue(const Value *val)
    {
        value = val;
    }
    inline const Value* getValue() const
    {
        return value;
    }
    inline void setBB(const BasicBlock *bb)
    {
        basicBlock = bb;
    }
    inline const BasicBlock* getBB() const
    {
        return basicBlock;
    }
    inline void setICFGNode(ICFGNode *node)
    {
        icfgNode = node;
    }
    inline ICFGNode* getICFGNode() const
    {
        return icfgNode;
    }

    static inline GEdgeFlag makeEdgeFlagWithCallInst(GEdgeKind k, const ICFGNode* cs)
    {
        Inst2LabelMap::const_iterator iter = inst2LabelMap.find(cs);
        u64_t label = (iter != inst2LabelMap.end()) ?
                      iter->second : callEdgeLabelCounter++;
        return (label << EdgeKindMaskBits) | k;
    }

    static inline GEdgeFlag makeEdgeFlagWithStoreInst(GEdgeKind k, const ICFGNode* store)
    {
        Inst2LabelMap::const_iterator iter = inst2LabelMap.find(store);
        u64_t label = (iter != inst2LabelMap.end()) ?
                      iter->second : storeEdgeLabelCounter++;
        return (label << EdgeKindMaskBits) | k;
    }

    virtual const std::string toString() const;


    friend raw_ostream& operator<< (raw_ostream &o, const PAGEdge &edge)
    {
        o << edge.toString();
        return o;
    }

    typedef GenericNode<PAGNode,PAGEdge>::GEdgeSetTy PAGEdgeSetTy;
    typedef Map<EdgeID, PAGEdgeSetTy> PAGEdgeToSetMapTy;
    typedef PAGEdgeToSetMapTy PAGKindToEdgeSetMapTy;

private:
    typedef Map<const ICFGNode*, u32_t> Inst2LabelMap;
    static Inst2LabelMap inst2LabelMap; 
    static u64_t callEdgeLabelCounter;  
    static u64_t storeEdgeLabelCounter;  
};



class AddrPE: public PAGEdge
{
private:
    AddrPE();                      
    AddrPE(const AddrPE &);  
    void operator=(const AddrPE &); 
public:

    static inline bool classof(const AddrPE *)
    {
        return true;
    }
    static inline bool classof(const PAGEdge *edge)
    {
        return edge->getEdgeKind() == PAGEdge::Addr;
    }
    static inline bool classof(const GenericPAGEdgeTy *edge)
    {
        return edge->getEdgeKind() == PAGEdge::Addr;
    }

    AddrPE(PAGNode* s, PAGNode* d) : PAGEdge(s,d,PAGEdge::Addr)
    {
    }

    virtual const std::string toString() const;
};


class CopyPE: public PAGEdge
{
private:
    CopyPE();                      
    CopyPE(const CopyPE &);  
    void operator=(const CopyPE &); 
public:

    static inline bool classof(const CopyPE *)
    {
        return true;
    }
    static inline bool classof(const PAGEdge *edge)
    {
        return edge->getEdgeKind() == PAGEdge::Copy;
    }
    static inline bool classof(const GenericPAGEdgeTy *edge)
    {
        return edge->getEdgeKind() == PAGEdge::Copy;
    }

    CopyPE(PAGNode* s, PAGNode* d) : PAGEdge(s,d,PAGEdge::Copy)
    {
    }

    virtual const std::string toString() const;
};


class CmpPE: public PAGEdge
{
private:
    CmpPE();                      
    CmpPE(const CmpPE &);  
    void operator=(const CmpPE &); 
public:

    static inline bool classof(const CmpPE *)
    {
        return true;
    }
    static inline bool classof(const PAGEdge *edge)
    {
        return edge->getEdgeKind() == PAGEdge::Cmp;
    }
    static inline bool classof(const GenericPAGEdgeTy *edge)
    {
        return edge->getEdgeKind() == PAGEdge::Cmp;
    }

    CmpPE(PAGNode* s, PAGNode* d) : PAGEdge(s,d,PAGEdge::Cmp)
    {
    }

    virtual const std::string toString() const;
};


class BinaryOPPE: public PAGEdge
{
private:
    BinaryOPPE();                      
    BinaryOPPE(const BinaryOPPE &);  
    void operator=(const BinaryOPPE &); 
public:

    static inline bool classof(const BinaryOPPE *)
    {
        return true;
    }
    static inline bool classof(const PAGEdge *edge)
    {
        return edge->getEdgeKind() == PAGEdge::BinaryOp;
    }
    static inline bool classof(const GenericPAGEdgeTy *edge)
    {
        return edge->getEdgeKind() == PAGEdge::BinaryOp;
    }

    BinaryOPPE(PAGNode* s, PAGNode* d) : PAGEdge(s,d,PAGEdge::BinaryOp)
    {
    }

    virtual const std::string toString() const;
};

class UnaryOPPE: public PAGEdge
{
private:
    UnaryOPPE();                      
    UnaryOPPE(const UnaryOPPE &);  
    void operator=(const UnaryOPPE &); 
public:

    static inline bool classof(const UnaryOPPE *)
    {
        return true;
    }
    static inline bool classof(const PAGEdge *edge)
    {
        return edge->getEdgeKind() == PAGEdge::UnaryOp;
    }
    static inline bool classof(const GenericPAGEdgeTy *edge)
    {
        return edge->getEdgeKind() == PAGEdge::UnaryOp;
    }

    UnaryOPPE(PAGNode* s, PAGNode* d) : PAGEdge(s,d,PAGEdge::UnaryOp)
    {
    }

    virtual const std::string toString() const;
};


class StorePE: public PAGEdge
{
private:
    StorePE();                      
    StorePE(const StorePE &);  
    void operator=(const StorePE &); 

public:

    static inline bool classof(const StorePE *)
    {
        return true;
    }
    static inline bool classof(const PAGEdge *edge)
    {
        return edge->getEdgeKind() == PAGEdge::Store;
    }
    static inline bool classof(const GenericPAGEdgeTy *edge)
    {
        return edge->getEdgeKind() == PAGEdge::Store;
    }

    StorePE(PAGNode* s, PAGNode* d, const IntraBlockNode* st) :
        PAGEdge(s, d, makeEdgeFlagWithStoreInst(PAGEdge::Store, st))
    {
    }

    virtual const std::string toString() const;
};


class LoadPE: public PAGEdge
{
private:
    LoadPE();                      
    LoadPE(const LoadPE &);  
    void operator=(const LoadPE &); 

public:

    static inline bool classof(const LoadPE *)
    {
        return true;
    }
    static inline bool classof(const PAGEdge *edge)
    {
        return edge->getEdgeKind() == PAGEdge::Load;
    }
    static inline bool classof(const GenericPAGEdgeTy *edge)
    {
        return edge->getEdgeKind() == PAGEdge::Load;
    }

    LoadPE(PAGNode* s, PAGNode* d) : PAGEdge(s,d,PAGEdge::Load)
    {
    }

    virtual const std::string toString() const;
};


class GepPE: public PAGEdge
{
private:
    GepPE();                      
    GepPE(const GepPE &);  
    void operator=(const GepPE &); 

public:

    static inline bool classof(const GepPE *)
    {
        return true;
    }
    static inline bool classof(const PAGEdge *edge)
    {
        return  edge->getEdgeKind() == PAGEdge::NormalGep ||
                edge->getEdgeKind() == PAGEdge::VariantGep;
    }
    static inline bool classof(const GenericPAGEdgeTy *edge)
    {
        return  edge->getEdgeKind() == PAGEdge::NormalGep ||
                edge->getEdgeKind() == PAGEdge::VariantGep;
    }

protected:
    GepPE(PAGNode* s, PAGNode* d, PEDGEK k) : PAGEdge(s,d,k)
    {

    }

    virtual const std::string toString() const;
};


class NormalGepPE : public GepPE
{
private:
    NormalGepPE(); 
    NormalGepPE(const NormalGepPE&); 
    void operator=(const NormalGepPE&); 

    LocationSet ls; 

public:

    static inline bool classof(const NormalGepPE *)
    {
        return true;
    }
    static inline bool classof(const GepPE *edge)
    {
        return edge->getEdgeKind() == PAGEdge::NormalGep;
    }
    static inline bool classof(const PAGEdge *edge)
    {
        return edge->getEdgeKind() == PAGEdge::NormalGep;
    }
    static inline bool classof(const GenericPAGEdgeTy *edge)
    {
        return edge->getEdgeKind() == PAGEdge::NormalGep;
    }

    NormalGepPE(PAGNode* s, PAGNode* d, const LocationSet& l) : GepPE(s,d,PAGEdge::NormalGep), ls(l)
    {}

    inline u32_t getOffset() const
    {
        return ls.getOffset();
    }
    inline const LocationSet& getLocationSet() const
    {
        return ls;
    }

    virtual const std::string toString() const;
};

class VariantGepPE : public GepPE
{
private:
    VariantGepPE(); 
    VariantGepPE(const VariantGepPE&); 
    void operator=(const VariantGepPE&); 

public:

    static inline bool classof(const VariantGepPE *)
    {
        return true;
    }
    static inline bool classof(const GepPE *edge)
    {
        return edge->getEdgeKind() == PAGEdge::VariantGep;
    }
    static inline bool classof(const PAGEdge *edge)
    {
        return edge->getEdgeKind() == PAGEdge::VariantGep;
    }
    static inline bool classof(const GenericPAGEdgeTy *edge)
    {
        return edge->getEdgeKind() == PAGEdge::VariantGep;
    }

    VariantGepPE(PAGNode* s, PAGNode* d) : GepPE(s,d,PAGEdge::VariantGep) {}

    virtual const std::string toString() const;

};


class CallPE: public PAGEdge
{
private:
    CallPE();                      
    CallPE(const CallPE &);  
    void operator=(const CallPE &); 

    const CallBlockNode* inst;      
public:

    static inline bool classof(const CallPE *)
    {
        return true;
    }
    static inline bool classof(const PAGEdge *edge)
    {
        return edge->getEdgeKind() == PAGEdge::Call
            || edge->getEdgeKind() == PAGEdge::ThreadFork;
    }
    static inline bool classof(const GenericPAGEdgeTy *edge)
    {
        return edge->getEdgeKind() == PAGEdge::Call
            || edge->getEdgeKind() == PAGEdge::ThreadFork;
    }

    CallPE(PAGNode* s, PAGNode* d, const CallBlockNode* i, GEdgeKind k = PAGEdge::Call) :
        PAGEdge(s,d,makeEdgeFlagWithCallInst(k,i)), inst(i)
    {
    }


    inline const CallBlockNode* getCallInst() const
    {
        return inst;
    }
    inline const CallBlockNode* getCallSite() const
    {
        return inst;
    }

    virtual const std::string toString() const;
};


class RetPE: public PAGEdge
{
private:
    RetPE();                      
    RetPE(const RetPE &);  
    void operator=(const RetPE &); 

    const CallBlockNode* inst;      
public:

    static inline bool classof(const RetPE *)
    {
        return true;
    }
    static inline bool classof(const PAGEdge *edge)
    {
        return edge->getEdgeKind() == PAGEdge::Ret
            || edge->getEdgeKind() == PAGEdge::ThreadJoin;
    }
    static inline bool classof(const GenericPAGEdgeTy *edge)
    {
        return edge->getEdgeKind() == PAGEdge::Ret
            || edge->getEdgeKind() == PAGEdge::ThreadJoin;
    }

    RetPE(PAGNode* s, PAGNode* d, const CallBlockNode* i, GEdgeKind k = PAGEdge::Ret) :
        PAGEdge(s,d,makeEdgeFlagWithCallInst(k,i)), inst(i)
    {
    }


    inline const CallBlockNode* getCallInst() const
    {
        return inst;
    }
    inline const CallBlockNode* getCallSite() const
    {
        return inst;
    }

    virtual const std::string toString() const;
};


class TDForkPE: public CallPE
{
private:
    TDForkPE();                      
    TDForkPE(const TDForkPE &);  
    void operator=(const TDForkPE &); 

public:

    static inline bool classof(const TDForkPE *)
    {
        return true;
    }
    static inline bool classof(const PAGEdge *edge)
    {
        return edge->getEdgeKind() == PAGEdge::ThreadFork;
    }
    static inline bool classof(const GenericPAGEdgeTy *edge)
    {
        return edge->getEdgeKind() == PAGEdge::ThreadFork;
    }

    TDForkPE(PAGNode* s, PAGNode* d, const CallBlockNode* i) :
        CallPE(s,d,i,PAGEdge::ThreadFork)
    {
    }

    virtual const std::string toString() const;
};



class TDJoinPE: public RetPE
{
private:
    TDJoinPE();                      
    TDJoinPE(const TDJoinPE &);  
    void operator=(const TDJoinPE &); 

public:

    static inline bool classof(const TDJoinPE *)
    {
        return true;
    }
    static inline bool classof(const PAGEdge *edge)
    {
        return edge->getEdgeKind() == PAGEdge::ThreadJoin;
    }
    static inline bool classof(const GenericPAGEdgeTy *edge)
    {
        return edge->getEdgeKind() == PAGEdge::ThreadJoin;
    }

    TDJoinPE(PAGNode* s, PAGNode* d, const CallBlockNode* i) :
        RetPE(s,d,i,PAGEdge::ThreadJoin)
    {
    }

    virtual const std::string toString() const;
};

} // End namespace SVF

#endif /* PAGEDGE_H_ */