DCHG.h

Go to the documentation of this file.

//===----- DCHG.h -- CHG using DWARF debug info ---------------------------//
// This is based upon the original CHA.h (now CHG.h).
 
/*
 * DCHG.h
 *
 *  Created on: Aug 23, 2019
 *      Author: Mohamad Barbar
 */
 
// TODO: add a flag such that getCanonicalType returns its arg so
//       that the impl. does not "node collapsing" based on teq.
 
#ifndef DCHG_H_
#define DCHG_H_
 
#include "Graphs/GenericGraph.h"
#include "Graphs/CHG.h"
#include "SVF-LLVM/BasicTypes.h"
#include "SVFIR/SVFModule.h"
#include "Util/SVFUtil.h"
#include "Util/WorkList.h"
 
namespace SVF
{
 
class SVFModule;
class DCHNode;
 
class DCHEdge : public GenericEdge<DCHNode>
{
public:
    enum
    {
        INHERITANCE,  // inheritance relation
        INSTANCE,     // template-instance relation
        FIRST_FIELD,  // src -ff-> dst => dst is first field of src
        STD_DEF       // Edges defined by the standard like (int -std-> char)
        // We also make the char --> void edge a STD_DEF edge.
    };
 
    typedef GenericNode<DCHNode, DCHEdge>::GEdgeSetTy DCHEdgeSetTy;
 
    DCHEdge(DCHNode *src, DCHNode *dst, GEdgeFlag k = 0)
        : GenericEdge<DCHNode>(src, dst, k), offset(0)
    {
    }
 
    u32_t getConstantFieldIdx(void) const
    {
        return offset;
    }
 
    void setOffset(u32_t offset)
    {
        this->offset = offset;
    }
 
private:
    u32_t offset;
};
 
class DCHNode : public GenericNode<DCHNode, DCHEdge>
{
public:
    typedef enum
    {
        PURE_ABSTRACT = 0x1,     // pure virtual abstract class
        MULTI_INHERITANCE = 0x2, // multi inheritance class
        TEMPLATE = 0x04,         // template class
        SCALAR = 0x08            // non-class scalar type
    } CLASSATTR;
 
    typedef std::vector<const Function*> FuncVector;
 
    DCHNode(const DIType* diType, NodeID i = 0, GNodeK k = GNodeK::DCHNodeKd)
        : GenericNode<DCHNode, DCHEdge>(i, k), vtable(nullptr), flags(0)
    {
        this->diType = diType;
        if (diType == nullptr)
        {
            typeName = "null-void";
        }
        else if (diType->getRawName() != nullptr)
        {
            typeName = diType->getName().str();
        }
        else
        {
            typeName = "unnamed!";
        }
    }
 
    ~DCHNode() { }
 
    const DIType * getDIType(void) const
    {
        return diType;
    }
 
    std::string getName() const
    {
        return typeName;
    }
 
 
    inline void setFlag(CLASSATTR mask)
    {
        flags |= mask;
    }
    inline bool hasFlag(CLASSATTR mask) const
    {
        return (flags & mask) == mask;
    }
 
 
    inline void setPureAbstract()
    {
        setFlag(PURE_ABSTRACT);
    }
    inline void setMultiInheritance()
    {
        setFlag(MULTI_INHERITANCE);
    }
    inline void setTemplate()
    {
        setFlag(TEMPLATE);
    }
    inline void setScalar()
    {
        setFlag(SCALAR);
    }
    inline bool isPureAbstract() const
    {
        return hasFlag(PURE_ABSTRACT);
    }
    inline bool isMultiInheritance() const
    {
        return hasFlag(MULTI_INHERITANCE);
    }
    inline bool isTemplate() const
    {
        return hasFlag(TEMPLATE);
    }
    inline bool isScalar() const
    {
        return hasFlag(SCALAR);
    }
 
    void addTypedef(const DIDerivedType *diTypedef)
    {
        typedefs.insert(diTypedef);
    }
 
    const Set<const DIDerivedType *> &getTypedefs(void) const
    {
        return typedefs;
    }
 
    void setVTable(const SVFGlobalValue *vtbl)
    {
        vtable = vtbl;
    }
 
    const SVFGlobalValue *getVTable() const
    {
        return vtable;
    }
 
    const std::vector<std::vector<const Function* >> &getVfnVectors(void) const
    {
        return vfnVectors;
    }
 
    std::vector<const Function* > &getVfnVector(unsigned n)
    {
        if (vfnVectors.size() < n + 1)
        {
            vfnVectors.resize(n + 1);
        }
 
        return vfnVectors[n];
    }
 
private:
    const DIType *diType;
    Set<const DIDerivedType *> typedefs;
    const SVFGlobalValue* vtable;
    std::string typeName;
    size_t flags;
    std::vector<const Function* > primaryVTable;
    std::vector<std::vector<const Function*>> vfnVectors;
};
 
class DCHGraph : public CommonCHGraph, public GenericGraph<DCHNode, DCHEdge>
{
public:
    static const DIType* stripQualifiers(const DIType*);
 
    static const DIType* stripArray(const DIType*);
 
    static bool teq(const DIType* t1, const DIType* t2);
 
    static std::string diTypeToStr(const DIType *);
 
    // Returns whether t is an array, a struct, a class, a union, or neither.
    static bool isAgg(const DIType* t);
 
public:
    DCHGraph(const SVFModule *svfMod)
        : svfModule(svfMod), numTypes(0)   // vfID(0), buildingCHGTime(0) {
    {
        this->kind = DI;
    }
 
    virtual ~DCHGraph() { };
 
    virtual void buildCHG(bool extend);
 
    void dump(const std::string& filename)
    {
        GraphPrinter::WriteGraphToFile(SVFUtil::outs(), filename, this);
    }
 
    void print(void);
 
    virtual bool csHasVFnsBasedonCHA(const CallICFGNode* cs) override
    {
        return csHasVtblsBasedonCHA(cs);
    }
 
    virtual const VFunSet &getCSVFsBasedonCHA(const CallICFGNode* cs) override;
 
    virtual bool csHasVtblsBasedonCHA(CallBase* cs)
    {
        assert(false && "not supported");
        const DIType *type = getCanonicalType(getCSStaticType(cs));
        if (!hasNode(type))
        {
            return false;
        }
 
        return getNode(type)->getVTable() != nullptr;
    }
 
    virtual bool csHasVtblsBasedonCHA(const CallICFGNode* cs) override
    {
        assert(false && "not supported!");
        abort();
    }
 
    virtual const VTableSet &getCSVtblsBasedonCHA(const CallICFGNode* cs) override;
    virtual void getVFnsFromVtbls(const CallICFGNode* cs, const VTableSet &vtbls, VFunSet &virtualFunctions) override;
 
    virtual bool isBase(const DIType *a, const DIType *b, bool firstField);
 
    virtual bool isFieldOf(const DIType *f, const DIType *b);
 
    static inline bool classof(const CommonCHGraph *chg)
    {
        return chg->getKind() == DI;
    }
 
    const DIType* getCanonicalType(const DIType* t);
 
    const DIType *getFieldType(const DIType *base, unsigned idx)
    {
        base = getCanonicalType(base);
        if (base == nullptr)
        {
            // Conservative; the base object is untyped, sadly.
            return nullptr;
        }
 
        // For TBHC this is conservative because the union type is lower in the DCHG
        // than its fields. TODO: make more precise.
        if (base->getTag() == dwarf::DW_TAG_union_type)
        {
            return base;
        }
 
        if (base->getTag() == dwarf::DW_TAG_array_type)
        {
            const DICompositeType* cbase =
                SVFUtil::dyn_cast<DICompositeType>(base);
            assert(cbase && "DCHG: bad DIComposite case");
            return cbase->getBaseType();
        }
 
        if (!(base->getTag() == dwarf::DW_TAG_class_type ||
                base->getTag() == dwarf::DW_TAG_structure_type))
        {
            return nullptr;
        }
 
        assert(fieldTypes.find(base) != fieldTypes.end() && "DCHG: base not flattened!");
        std::vector<const DIType *> &fields = fieldTypes[base];
        assert(fields.size() > idx && "DCHG: idx into struct larger than # fields!");
        return getCanonicalType(fields[idx]);
    }
 
    const std::vector<const DIType *> &getFieldTypes(const DIType *base)
    {
        base = getCanonicalType(base);
        assert(fieldTypes.find(base) != fieldTypes.end() && "DCHG: base not flattened!");
        return fieldTypes[base];
    }
 
    // Returns the number of fields in base (length of getFieldTypes).
    unsigned getNumFields(const DIType *base)
    {
        base = getCanonicalType(base);
        assert(fieldTypes.find(base) != fieldTypes.end() && "DCHG: base not flattened!");
        return fieldTypes[base].size();
    }
 
    const Set<const DIType *> &getAggs(const DIType *base)
    {
        base = getCanonicalType(base);
        assert(containingAggs.find(base) != containingAggs.end() && "DCHG: aggregates not gathered for base!");
        return containingAggs[base];
    }
 
    bool isFirstField(const DIType* f, const DIType* b);
 
protected:
    const SVFModule* svfModule;
    bool extended = false;
    Map<const DIType*, DCHNode*> diTypeToNodeMap;
    Map<const SVFGlobalValue*, const DIType*> vtblToTypeMap;
    Map<const DIType*, NodeBS> chaMap;
    Map<const DIType*, NodeBS> chaFFMap;
    Map<const DIType*, VTableSet> vtblCHAMap;
    Map<const CallICFGNode*, VFunSet> csCHAMap;
    Map<const DIType*, const DIType*> canonicalTypeMap;
    Set<const DIType*> canonicalTypes;
    Map<const DIType*, std::vector<const DIType*>> fieldTypes;
    Map<const DIType*, Set<const DIType*>> containingAggs;
 
private:
    void handleDIBasicType(const DIBasicType* basicType);
    void handleDICompositeType(const DICompositeType* compositeType);
    void handleDIDerivedType(const DIDerivedType* derivedType);
    void handleDISubroutineType(const DISubroutineType* subroutineType);
 
    void buildVTables(const SVFModule& module);
 
    const NodeBS& cha(const DIType* type, bool firstField);
 
    void handleTypedef(const DIType* typedefType);
 
    void flatten(const DICompositeType* type);
 
    void gatherAggs(const DICompositeType* type);
 
    DCHNode* getOrCreateNode(const DIType* type);
 
    const DIType* getCSStaticType(CallBase* cs) const;
 
    const DIType *getCSStaticType(const CallICFGNode* cs) const
    {
        assert(false && "not supported!");
        abort();
    }
 
    bool hasNode(const DIType* type)
    {
        type = getCanonicalType(type);
        return diTypeToNodeMap.find(type) != diTypeToNodeMap.end();
    }
 
    DCHNode* getNode(const DIType* type)
    {
        type = getCanonicalType(type);
        if (hasNode(type))
        {
            return diTypeToNodeMap.at(type);
        }
 
        return nullptr;
    }
 
 
    DCHEdge* addEdge(const DIType* t1, const DIType* t2, DCHEdge::GEdgeKind et);
    DCHEdge* hasEdge(const DIType* t1, const DIType* t2, DCHEdge::GEdgeKind et);
 
    NodeID numTypes;
};
 
} // End namespace SVF
 
namespace SVF
{
/* !
 * GenericGraphTraits specializations for generic graph algorithms.
 * Provide graph traits for traversing from a constraint node using standard graph traversals.
 */
template<> struct GenericGraphTraits<SVF::DCHNode*> : public GenericGraphTraits<SVF::GenericNode<SVF::DCHNode,SVF::DCHEdge>*  >
{
};
 
template<>
struct GenericGraphTraits<Inverse<SVF::DCHNode*> > : public GenericGraphTraits<Inverse<SVF::GenericNode<SVF::DCHNode,SVF::DCHEdge>* > >
{
};
 
template<> struct GenericGraphTraits<SVF::DCHGraph*> : public GenericGraphTraits<SVF::GenericGraph<SVF::DCHNode,SVF::DCHEdge>* >
{
    typedef SVF::DCHNode *NodeRef;
};
 
} // End namespace llvm
 
#endif /* DCHG_H_ */