SVFVariables.h

Go to the documentation of this file.

//===- SVFSymbols.h -- SVF Variables------------------------//
//
//                     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/>.
//
//===----------------------------------------------------------------------===//
 
/*
 * SVFVariables.h
 *
 *  Created on: Nov 11, 2013
 *      Author: Yulei Sui
 */
 
#ifndef INCLUDE_SVFIR_SVFVARIABLE_H_
#define INCLUDE_SVFIR_SVFVARIABLE_H_
 
#include "Graphs/GenericGraph.h"
#include "SVFIR/SymbolTableInfo.h"
#include "SVFIR/SVFStatements.h"
 
namespace SVF
{
 
class SVFVar;
/*
 * SVFIR program variables (PAGNodes)
 */
typedef GenericNode<SVFVar, SVFStmt> GenericPAGNodeTy;
class SVFVar : public GenericPAGNodeTy
{
    friend class SVFIRWriter;
    friend class SVFIRReader;
    friend class IRGraph;
    friend class SVFIR;
    friend class VFG;
 
public:
    typedef GNodeK PNODEK;
    typedef s64_t GEdgeKind;
 
protected:
    const SVFValue* value; 
    SVFStmt::KindToSVFStmtMapTy InEdgeKindToSetMap;
    SVFStmt::KindToSVFStmtMapTy OutEdgeKindToSetMap;
    bool isPtr; 
 
    SVFVar(NodeID i, PNODEK k) : GenericPAGNodeTy(i, k), value{} {}
 
public:
    SVFVar(const SVFValue* val, NodeID i, PNODEK k);
    virtual ~SVFVar() {}
 
 
    inline const SVFValue* getValue() const
    {
        assert(this->getNodeKind() != DummyValNode &&
               this->getNodeKind() != DummyObjNode &&
               "dummy node do not have value!");
        assert(!SymbolTableInfo::isBlkObjOrConstantObj(this->getId()) &&
               "blackhole and constant obj do not have value");
        assert(value &&
               "value is null (GepObjNode whose basenode is a DummyObj?)");
        return value;
    }
 
    inline virtual const SVFType* getType() const
    {
        return value ? value->getType() : nullptr;
    }
 
    inline bool hasValue() const
    {
        return value != nullptr;
    }
    virtual inline bool isPointer() const
    {
        return isPtr;
    }
    bool isConstDataOrAggDataButNotNullPtr() const;
 
    bool isIsolatedNode() const;
 
    // TODO: (Optimization) Should it return const reference instead of value?
    virtual const std::string getValueName() const = 0;
 
    virtual inline const SVFFunction* getFunction() const
    {
        if (value)
        {
            if (auto inst = SVFUtil::dyn_cast<SVFInstruction>(value))
                return inst->getParent()->getParent();
            else if (auto arg = SVFUtil::dyn_cast<SVFArgument>(value))
                return arg->getParent();
            else if (auto fun = SVFUtil::dyn_cast<SVFFunction>(value))
                return fun;
        }
        return nullptr;
    }
 
    inline SVFStmt::SVFStmtSetTy& getIncomingEdges(SVFStmt::PEDGEK kind)
    {
        return InEdgeKindToSetMap[kind];
    }
    inline SVFStmt::SVFStmtSetTy& getOutgoingEdges(SVFStmt::PEDGEK kind)
    {
        return OutEdgeKindToSetMap[kind];
    }
    inline bool hasIncomingEdges(SVFStmt::PEDGEK kind) const
    {
        SVFStmt::KindToSVFStmtMapTy::const_iterator it = InEdgeKindToSetMap.find(kind);
        if (it != InEdgeKindToSetMap.end())
            return (!it->second.empty());
        else
            return false;
    }
    inline bool hasOutgoingEdges(SVFStmt::PEDGEK kind) const
    {
        SVFStmt::KindToSVFStmtMapTy::const_iterator it = OutEdgeKindToSetMap.find(kind);
        if (it != OutEdgeKindToSetMap.end())
            return (!it->second.empty());
        else
            return false;
    }
 
    inline SVFStmt::SVFStmtSetTy::iterator getIncomingEdgesBegin(SVFStmt::PEDGEK kind) const
    {
        SVFStmt::KindToSVFStmtMapTy::const_iterator it = InEdgeKindToSetMap.find(kind);
        assert(it!=InEdgeKindToSetMap.end() && "The node does not have such kind of edge");
        return it->second.begin();
    }
 
    inline SVFStmt::SVFStmtSetTy::iterator getIncomingEdgesEnd(SVFStmt::PEDGEK kind) const
    {
        SVFStmt::KindToSVFStmtMapTy::const_iterator it = InEdgeKindToSetMap.find(kind);
        assert(it!=InEdgeKindToSetMap.end() && "The node does not have such kind of edge");
        return it->second.end();
    }
 
    inline SVFStmt::SVFStmtSetTy::iterator getOutgoingEdgesBegin(SVFStmt::PEDGEK kind) const
    {
        SVFStmt::KindToSVFStmtMapTy::const_iterator it = OutEdgeKindToSetMap.find(kind);
        assert(it!=OutEdgeKindToSetMap.end() && "The node does not have such kind of edge");
        return it->second.begin();
    }
 
    inline SVFStmt::SVFStmtSetTy::iterator getOutgoingEdgesEnd(SVFStmt::PEDGEK kind) const
    {
        SVFStmt::KindToSVFStmtMapTy::const_iterator it = OutEdgeKindToSetMap.find(kind);
        assert(it!=OutEdgeKindToSetMap.end() && "The node does not have such kind of edge");
        return it->second.end();
    }
 
    static inline bool classof(const SVFVar *)
    {
        return true;
    }
 
    static inline bool classof(const GenericPAGNodeTy * node)
    {
        return isSVFVarKind(node->getNodeKind());
    }
 
    static inline bool classof(const SVFBaseNode* node)
    {
        return isSVFVarKind(node->getNodeKind());
    }
 
private:
 
    inline void addInEdge(SVFStmt* inEdge)
    {
        GEdgeKind kind = inEdge->getEdgeKind();
        InEdgeKindToSetMap[kind].insert(inEdge);
        addIncomingEdge(inEdge);
    }
 
    inline void addOutEdge(SVFStmt* outEdge)
    {
        GEdgeKind kind = outEdge->getEdgeKind();
        OutEdgeKindToSetMap[kind].insert(outEdge);
        addOutgoingEdge(outEdge);
    }
    inline bool hasIncomingVariantGepEdge() const
    {
        SVFStmt::KindToSVFStmtMapTy::const_iterator it = InEdgeKindToSetMap.find(SVFStmt::Gep);
        if (it != InEdgeKindToSetMap.end())
        {
            for(auto gep : it->second)
            {
                if(SVFUtil::cast<GepStmt>(gep)->isVariantFieldGep())
                    return true;
            }
        }
        return false;
    }
 
public:
    virtual const std::string toString() const;
 
    void dump() const;
 
 
    friend OutStream& operator<< (OutStream &o, const SVFVar &node)
    {
        o << node.toString();
        return o;
    }
};
 
 
 
/*
 * Value (Pointer) variable
 */
class ValVar: public SVFVar
{
    friend class SVFIRWriter;
    friend class SVFIRReader;
 
private:
    const SVFBaseNode* gNode; // constant, gepValvar, retPN, dummy could be null
protected:
    ValVar(NodeID i, PNODEK ty = ValNode) : SVFVar(i, ty), gNode(nullptr) {}
 
public:
 
    static inline bool classof(const ValVar*)
    {
        return true;
    }
    static inline bool classof(const SVFVar* node)
    {
        return isValVarKinds(node->getNodeKind());
    }
    static inline bool classof(const GenericPAGNodeTy* node)
    {
        return isValVarKinds(node->getNodeKind());
    }
    static inline bool classof(const SVFBaseNode* node)
    {
        return isValVarKinds(node->getNodeKind());
    }
 
    ValVar(const SVFValue* val, NodeID i, PNODEK ty = ValNode, const SVFBaseNode* node = nullptr)
        : SVFVar(val, i, ty), gNode(node)
    {
    }
    inline const std::string getValueName() const
    {
        if (value)
            return value->getName();
        return "";
    }
 
    const SVFBaseNode* getGNode() const
    {
        return gNode;
    }
 
    virtual const std::string toString() const;
};
 
/*
 * Memory Object variable
 */
class ObjVar: public SVFVar
{
    friend class SVFIRWriter;
    friend class SVFIRReader;
 
protected:
    const MemObj* mem;  
    ObjVar(NodeID i, PNODEK ty = ObjNode) : SVFVar(i, ty), mem{} {}
    ObjVar(const SVFValue* val, NodeID i, const MemObj* m, PNODEK ty = ObjNode) :
        SVFVar(val, i, ty), mem(m)
    {
    }
public:
 
    static inline bool classof(const ObjVar*)
    {
        return true;
    }
    static inline bool classof(const SVFVar* node)
    {
        return isObjVarKinds(node->getNodeKind());
    }
    static inline bool classof(const GenericPAGNodeTy* node)
    {
        return isObjVarKinds(node->getNodeKind());
    }
    static inline bool classof(const SVFBaseNode* node)
    {
        return isObjVarKinds(node->getNodeKind());
    }
 
    const MemObj* getMemObj() const
    {
        return mem;
    }
 
    virtual const std::string getValueName() const
    {
        if (value)
            return value->getName();
        return "";
    }
    inline virtual const SVFType* getType() const
    {
        return mem->getType();
    }
 
    virtual const std::string toString() const;
};
 
 
/*
 * Gep Value (Pointer) variable, this variable can be dynamic generated for field sensitive analysis
 * e.g. memcpy, temp gep value variable needs to be created
 * Each Gep Value variable is connected to base value variable via gep edge
 */
class GepValVar: public ValVar
{
    friend class SVFIRWriter;
    friend class SVFIRReader;
 
private:
    AccessPath ap;  // AccessPath
    const SVFType* gepValType;
 
    GepValVar(NodeID i) : ValVar(i, GepValNode), gepValType{} {}
 
public:
 
    static inline bool classof(const GepValVar *)
    {
        return true;
    }
    static inline bool classof(const ValVar * node)
    {
        return node->getNodeKind() == SVFVar::GepValNode;
    }
    static inline bool classof(const SVFVar *node)
    {
        return node->getNodeKind() == SVFVar::GepValNode;
    }
    static inline bool classof(const GenericPAGNodeTy *node)
    {
        return node->getNodeKind() == SVFVar::GepValNode;
    }
 
    GepValVar(const SVFValue* val, NodeID i, const AccessPath& ap,
              const SVFType* ty)
        : ValVar(val, i, GepValNode), ap(ap), gepValType(ty)
    {
    }
 
    inline APOffset getConstantFieldIdx() const
    {
        return ap.getConstantStructFldIdx();
    }
 
    inline const std::string getValueName() const
    {
        if (value)
            return value->getName() + "_" +
                   std::to_string(getConstantFieldIdx());
        return "offset_" + std::to_string(getConstantFieldIdx());
    }
 
    inline const SVFType* getType() const
    {
        return gepValType;
    }
 
    virtual const std::string toString() const;
};
 
 
/*
 * Gep Obj variable, this is dynamic generated for field sensitive analysis
 * Each gep obj variable is one field of a MemObj (base)
 */
class GepObjVar: public ObjVar
{
    friend class SVFIRWriter;
    friend class SVFIRReader;
 
private:
    APOffset apOffset = 0;
    NodeID base = 0;
 
    //  only for reading from file when we don't have MemObj*
    GepObjVar(NodeID i, PNODEK ty = GepObjNode) : ObjVar(i, ty) {}
 
public:
 
    static inline bool classof(const GepObjVar*)
    {
        return true;
    }
    static inline bool classof(const ObjVar* node)
    {
        return node->getNodeKind() == SVFVar::GepObjNode;
    }
    static inline bool classof(const SVFVar* node)
    {
        return node->getNodeKind() == SVFVar::GepObjNode;
    }
    static inline bool classof(const GenericPAGNodeTy* node)
    {
        return node->getNodeKind() == SVFVar::GepObjNode;
    }
    static inline bool classof(const SVFBaseNode* node)
    {
        return node->getNodeKind() == SVFVar::GepObjNode;
    }
 
    GepObjVar(const MemObj* mem, NodeID i, const APOffset& apOffset,
              PNODEK ty = GepObjNode)
        : ObjVar(mem->getValue(), i, mem, ty), apOffset(apOffset)
    {
        base = mem->getId();
    }
 
    inline APOffset getConstantFieldIdx() const
    {
        return apOffset;
    }
 
    inline void setBaseNode(NodeID bs)
    {
        this->base = bs;
    }
 
    inline NodeID getBaseNode(void) const
    {
        return base;
    }
 
    inline virtual const SVFType* getType() const
    {
        return SymbolTableInfo::SymbolInfo()->getFlatternedElemType(mem->getType(), apOffset);
    }
 
    inline const std::string getValueName() const
    {
        if (value)
            return value->getName() + "_" + std::to_string(apOffset);
        return "offset_" + std::to_string(apOffset);
    }
 
    virtual const std::string toString() const;
};
 
/*
 * Field-insensitive Gep Obj variable, this is dynamic generated for field sensitive analysis
 * Each field-insensitive gep obj node represents all fields of a MemObj (base)
 */
class FIObjVar: public ObjVar
{
    friend class SVFIRWriter;
    friend class SVFIRReader;
 
private:
    FIObjVar(NodeID i, PNODEK ty = FIObjNode) : ObjVar(i, ty) {}
 
public:
 
    static inline bool classof(const FIObjVar*)
    {
        return true;
    }
    static inline bool classof(const ObjVar* node)
    {
        return node->getNodeKind() == SVFVar::FIObjNode;
    }
    static inline bool classof(const SVFVar* node)
    {
        return node->getNodeKind() == SVFVar::FIObjNode;
    }
    static inline bool classof(const GenericPAGNodeTy* node)
    {
        return node->getNodeKind() == SVFVar::FIObjNode;
    }
    static inline bool classof(const SVFBaseNode* node)
    {
        return node->getNodeKind() == SVFVar::FIObjNode;
    }
 
    FIObjVar(const SVFValue* val, NodeID i, const MemObj* mem,
             PNODEK ty = FIObjNode)
        : ObjVar(val, i, mem, ty)
    {
    }
 
    inline const std::string getValueName() const
    {
        if (value)
            return value->getName() + " (base object)";
        return " (base object)";
    }
 
    virtual const std::string toString() const;
};
 
/*
 * Unique Return node of a procedure
 */
class RetPN: public ValVar
{
    friend class SVFIRWriter;
    friend class SVFIRReader;
 
private:
    RetPN(NodeID i) : ValVar(i, RetNode) {}
 
public:
    static inline bool classof(const RetPN*)
    {
        return true;
    }
    static inline bool classof(const SVFVar* node)
    {
        return node->getNodeKind() == SVFVar::RetNode;
    }
    static inline bool classof(const ValVar* node)
    {
        return node->getNodeKind() == SVFVar::RetNode;
    }
    static inline bool classof(const GenericPAGNodeTy* node)
    {
        return node->getNodeKind() == SVFVar::RetNode;
    }
    static inline bool classof(const SVFBaseNode* node)
    {
        return node->getNodeKind() == SVFVar::RetNode;
    }
 
    RetPN(const SVFFunction* val, NodeID i) : ValVar(val, i, RetNode) {}
 
    const std::string getValueName() const
    {
        return value->getName() + "_ret";
    }
 
    virtual const std::string toString() const;
};
 
/*
 * Unique vararg node of a procedure
 */
class VarArgPN: public ValVar
{
    friend class SVFIRWriter;
    friend class SVFIRReader;
 
private:
    VarArgPN(NodeID i) : ValVar(i, VarargNode) {}
 
public:
    static inline bool classof(const VarArgPN*)
    {
        return true;
    }
    static inline bool classof(const SVFVar* node)
    {
        return node->getNodeKind() == SVFVar::VarargNode;
    }
    static inline bool classof(const ValVar* node)
    {
        return node->getNodeKind() == SVFVar::VarargNode;
    }
    static inline bool classof(const GenericPAGNodeTy* node)
    {
        return node->getNodeKind() == SVFVar::VarargNode;
    }
    static inline bool classof(const SVFBaseNode* node)
    {
        return node->getNodeKind() == SVFVar::VarargNode;
    }
 
    VarArgPN(const SVFFunction* val, NodeID i) : ValVar(val, i, VarargNode) {}
 
    inline const std::string getValueName() const
    {
        return value->getName() + "_vararg";
    }
 
    virtual const std::string toString() const;
};
 
/*
 * Dummy variable without any LLVM value
 */
class DummyValVar: public ValVar
{
    friend class SVFIRWriter;
    friend class SVFIRReader;
 
public:
    static inline bool classof(const DummyValVar*)
    {
        return true;
    }
    static inline bool classof(const SVFVar* node)
    {
        return node->getNodeKind() == SVFVar::DummyValNode;
    }
    static inline bool classof(const ValVar* node)
    {
        return node->getNodeKind() == SVFVar::DummyValNode;
    }
    static inline bool classof(const GenericPAGNodeTy* node)
    {
        return node->getNodeKind() == SVFVar::DummyValNode;
    }
    static inline bool classof(const SVFBaseNode* node)
    {
        return node->getNodeKind() == SVFVar::DummyValNode;
    }
 
    DummyValVar(NodeID i) : ValVar(nullptr, i, DummyValNode) {}
 
    inline const std::string getValueName() const
    {
        return "dummyVal";
    }
 
    virtual const std::string toString() const;
};
 
/*
 * Dummy object variable
 */
class DummyObjVar: public ObjVar
{
    friend class SVFIRWriter;
    friend class SVFIRReader;
 
private:
    DummyObjVar(NodeID i) : ObjVar(i, DummyObjNode) {}
 
public:
    static inline bool classof(const DummyObjVar*)
    {
        return true;
    }
    static inline bool classof(const SVFVar* node)
    {
        return node->getNodeKind() == SVFVar::DummyObjNode;
    }
    static inline bool classof(const ObjVar* node)
    {
        return node->getNodeKind() == SVFVar::DummyObjNode;
    }
    static inline bool classof(const GenericPAGNodeTy* node)
    {
        return node->getNodeKind() == SVFVar::DummyObjNode;
    }
 
    static inline bool classof(const SVFBaseNode* node)
    {
        return node->getNodeKind() == SVFVar::DummyObjNode;
    }
 
    DummyObjVar(NodeID i, const MemObj* m, PNODEK ty = DummyObjNode)
        : ObjVar(nullptr, i, m, ty)
    {
    }
 
    inline const std::string getValueName() const
    {
        return "dummyObj";
    }
 
    virtual const std::string toString() const;
};
 
} // End namespace SVF
 
#endif /* INCLUDE_SVFIR_SVFVARIABLE_H_ */