IRGraph.cpp

Go to the documentation of this file.

//===- SVFIR.cpp -- Program assignment graph------------------------------------//
//
//                     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 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/>.
//
//===----------------------------------------------------------------------===//
 
/*
 * SVFIR.cpp
 *
 *  Created on: Nov 1, 2013
 *      Author: Yulei Sui
 */
 
#include "Graphs/GraphPrinter.h"
#include "Graphs/ICFG.h"
#include "Graphs/IRGraph.h"
#include "Util/GeneralType.h"
#include "Util/Options.h"
#include "Util/SVFUtil.h"
 
using namespace SVF;
using namespace SVFUtil;
 
void IRGraph::destorySymTable()
{
 
    for (auto &pair: objTypeInfoMap)
    {
        if (ObjTypeInfo* ti = pair.second)
            delete ti;
    }
 
    for (const SVFType* type : svfTypes)
        delete type;
    svfTypes.clear();
 
    for (const StInfo* st : stInfos)
        delete st;
    stInfos.clear();
}
 
IRGraph::~IRGraph()
{
    destorySymTable();
}
 
 
NodeID IRGraph::getReturnNode(const FunObjVar *func) const
{
    FunObjVarToIDMapTy::const_iterator iter =  returnFunObjSymMap.find(func);
    assert(iter!=returnFunObjSymMap.end() && "ret sym not found");
    return iter->second;
}
 
NodeID IRGraph::getVarargNode(const FunObjVar *func) const
{
    FunObjVarToIDMapTy::const_iterator iter =  varargFunObjSymMap.find(func);
    assert(iter!=varargFunObjSymMap.end() && "vararg sym not found");
    return iter->second;
}
void IRGraph::printFlattenFields(const SVFType *type)
{
    if (const SVFArrayType* at = SVFUtil::dyn_cast<SVFArrayType>(type))
    {
        outs() << "  {Type: " << *at << "}\n"
               << "\tarray type "
               << "\t [element size = " << getNumOfFlattenElements(at) << "]\n"
               << "\n";
    }
    else if (const SVFStructType *st = SVFUtil::dyn_cast<SVFStructType>(type))
    {
        outs() <<"  {Type: " << *st << "}\n";
        const std::vector<const SVFType*>& finfo = getTypeInfo(st)->getFlattenFieldTypes();
        int field_idx = 0;
        for(const SVFType* type : finfo)
        {
            outs() << " \tField_idx = " << ++field_idx
                   << ", field type: " << *type << "\n";
        }
        outs() << "\n";
    }
    else if (const SVFPointerType* pt= SVFUtil::dyn_cast<SVFPointerType>(type))
    {
        outs() << *pt << "\n";
    }
    else if (const SVFFunctionType* fu =
                 SVFUtil::dyn_cast<SVFFunctionType>(type))
    {
        outs() << "  {Type: " << *fu << "}\n\n";
    }
    else if (const SVFOtherType* ot = SVFUtil::dyn_cast<SVFOtherType>(type))
    {
        outs() << "  {Type: "<< *ot << "(SVFOtherType)}\n\n";
    }
    else
    {
        assert(type->isSingleValueType() && "not a single value type, then what else!!");
        u32_t eSize = getNumOfFlattenElements(type);
        outs() << "  {Type: " << *type << "}\n"
               << "\t [object size = " << eSize << "]\n"
               << "\n";
    }
}
 
const std::vector<const SVFType *> &IRGraph::getFlattenFieldTypes(const SVFStructType *T)
{
    return getTypeInfo(T)->getFlattenFieldTypes();
}
 
const SVFType *IRGraph::getFlatternedElemType(const SVFType *baseType, u32_t flatten_idx)
{
    if(Options::ModelArrays())
    {
        const std::vector<const SVFType*>& so = getTypeInfo(baseType)->getFlattenElementTypes();
        assert (flatten_idx < so.size() && !so.empty() && "element index out of bounds or struct opaque type, can't get element type!");
        return so[flatten_idx];
    }
    else
    {
        const std::vector<const SVFType*>& so = getTypeInfo(baseType)->getFlattenFieldTypes();
        assert (flatten_idx < so.size() && !so.empty() && "element index out of bounds or struct opaque type, can't get element type!");
        return so[flatten_idx];
    }
}
 
const SVFType *IRGraph::getOriginalElemType(const SVFType *baseType, u32_t origId) const
{
    return getTypeInfo(baseType)->getOriginalElemType(origId);
}
 
u32_t IRGraph::getFlattenedElemIdx(const SVFType *T, u32_t origId)
{
    if(Options::ModelArrays())
    {
        const std::vector<u32_t>& so = getTypeInfo(T)->getFlattenedElemIdxVec();
        assert ((unsigned)origId < so.size() && !so.empty() && "element index out of bounds, can't get flattened index!");
        return so[origId];
    }
    else
    {
        if(SVFUtil::isa<SVFStructType>(T))
        {
            const std::vector<u32_t>& so = getTypeInfo(T)->getFlattenedFieldIdxVec();
            assert ((unsigned)origId < so.size() && !so.empty() && "Struct index out of bounds, can't get flattened index!");
            return so[origId];
        }
        else if(SVFUtil::isa<SVFArrayType>(T))
        {
            return 0;
        }
        else
        {
            // Under LLVM's opaque pointers, the SVFType resolved for a GEP base can fold to
            // something other than a struct/array SVFType even though the corresponding LLVM
            // aggregate genuinely is a StructType/ArrayType (seen integrating SVF against an
            // LLVM 21 -O0 build). Report the concrete type so a future hit of this branch is
            // diagnosable rather than guessed at, then fall back to element 0 instead of
            // crashing (the printed type survives into release builds even when the assert
            // below is compiled out).
            SVFUtil::errs() << "getFlattenedElemIdx: type is neither struct nor array: "
                            << T->toString() << "\n";
            assert(false && "getFlattenedElemIdx: type is neither struct nor array (see printed type above)");
            return 0;
        }
    }
}
 
u32_t IRGraph::getNumOfFlattenElements(const SVFType *T)
{
    if(Options::ModelArrays())
        return getTypeInfo(T)->getNumOfFlattenElements();
    else
        return getTypeInfo(T)->getNumOfFlattenFields();
}
 
const ObjTypeInfo *IRGraph::createDummyObjTypeInfo(NodeID symId, const SVFType *type)
{
    if (objTypeInfoMap.find(symId)==objTypeInfoMap.end())
    {
        ObjTypeInfo* ti = createObjTypeInfo(type);
        objTypeInfoMap[symId] = ti;
    }
    ObjTypeInfo* ti = objTypeInfoMap[symId];
    return ti;
}
 
APOffset IRGraph::getModulusOffset(const BaseObjVar *baseObj, const APOffset &apOffset)
{
 
    APOffset offset = apOffset;
    if(offset < 0)
    {
        writeWrnMsg("try to create a gep node with negative offset.");
        offset = std::abs(offset);
    }
    u32_t maxOffset = baseObj->getMaxFieldOffsetLimit();
 
    if (maxOffset == 0)
        offset = 0;
    else if (Options::MaxFieldLimit() < maxOffset)
        offset = offset % maxOffset;
    else if ((u32_t)offset > maxOffset - 1)
    {
        if (Options::CyclicFldIdx())
            offset = offset % maxOffset;
        else
            offset = maxOffset - 1;
    }
 
    return offset;
}
 
ObjTypeInfo *IRGraph::createObjTypeInfo(const SVFType *type)
{
 
    ObjTypeInfo* typeInfo = new ObjTypeInfo(type, Options::MaxFieldLimit());
    if(type && type->isPointerTy())
    {
        typeInfo->setFlag(ObjTypeInfo::HEAP_OBJ);
    }
    return typeInfo;
}
 
const StInfo *IRGraph::getTypeInfo(const SVFType *T) const
{
    assert(T);
    SVFTypeSet::const_iterator it = svfTypes.find(T);
    assert(it != svfTypes.end() && "type info not found? collect them first during SVFIR Building");
    return (*it)->getTypeInfo();
}
 
bool IRGraph::addEdge(SVFVar* src, SVFVar* dst, SVFStmt* edge)
{
 
    DBOUT(DPAGBuild,
          outs() << "add edge from " << src->getId() << " kind :"
          << src->getNodeKind() << " to " << dst->getId()
          << " kind :" << dst->getNodeKind() << "\n");
    src->addOutEdge(edge);
    dst->addInEdge(edge);
    return true;
}
 
SVFStmt* IRGraph::hasNonlabeledEdge(SVFVar* src, SVFVar* dst, SVFStmt::PEDGEK kind)
{
    SVFStmt edge(src,dst,kind, false);
    return hasEdge(&edge, kind);
}
 
SVFStmt* IRGraph::hasLabeledEdge(SVFVar* src, SVFVar* op1, SVFStmt::PEDGEK kind, const SVFVar* op2)
{
    SVFStmt edge(src,op1,SVFStmt::makeEdgeFlagWithAddionalOpnd(kind,op2), false);
    SVFStmt::SVFStmtSetTy::iterator it = KindToSVFStmtSetMap[kind].find(&edge);
    if (it != KindToSVFStmtSetMap[kind].end())
    {
        return *it;
    }
    return nullptr;
}
 
SVFStmt* IRGraph::hasLabeledEdge(SVFVar* src, SVFVar* dst, SVFStmt::PEDGEK kind, const ICFGNode* callInst)
{
    SVFStmt edge(src,dst,SVFStmt::makeEdgeFlagWithCallInst(kind,callInst), false);
    SVFStmt::SVFStmtSetTy::iterator it = KindToSVFStmtSetMap[kind].find(&edge);
    if (it != KindToSVFStmtSetMap[kind].end())
    {
        return *it;
    }
    return nullptr;
}
 
SVFStmt* IRGraph::hasEdge(SVFStmt* edge, SVFStmt::PEDGEK kind)
{
    SVFStmt::SVFStmtSetTy::iterator it = KindToSVFStmtSetMap[kind].find(edge);
    if (it != KindToSVFStmtSetMap[kind].end())
    {
        return *it;
    }
    return nullptr;
}
 
 
void IRGraph::dump(std::string name)
{
    GraphPrinter::WriteGraphToFile(outs(), name, this);
}
 
void IRGraph::view()
{
    SVF::ViewGraph(this, "ProgramAssignmentGraph");
}
 
 
u32_t IRGraph::getValueNodeNum()
{
    if (valVarNum != 0) return valVarNum;
    u32_t num = 0;
    for (const auto& item: *this)
    {
        if (SVFUtil::isa<ValVar>(item.second))
            num++;
    }
    return valVarNum = num;
}
 
 
u32_t IRGraph::getObjectNodeNum()
{
    if (objVarNum != 0) return objVarNum;
    u32_t num = 0;
    for (const auto& item: *this)
    {
        if (SVFUtil::isa<ObjVar>(item.second))
            num++;
    }
    return objVarNum = num;
}
 
 
 
namespace SVF
{
template<>
struct DOTGraphTraits<IRGraph*> : public DefaultDOTGraphTraits
{
 
    typedef SVFVar NodeType;
    typedef NodeType::iterator ChildIteratorType;
    DOTGraphTraits(bool isSimple = false) :
        DefaultDOTGraphTraits(isSimple)
    {
    }
 
    static std::string getGraphName(IRGraph *graph)
    {
        return graph->getGraphName();
    }
 
    static bool isNodeHidden(SVFVar *node, IRGraph *)
    {
        if (Options::ShowHiddenNode()) return false;
        else return node->isIsolatedNode();
    }
 
    static std::string getNodeLabel(SVFVar *node, IRGraph*)
    {
        std::string str;
        std::stringstream rawstr(str);
        // print function info
        if (node->getFunction())
            rawstr << "[" << node->getFunction()->getName() << "] ";
 
        rawstr << node->toString();
 
        return rawstr.str();
 
    }
 
    static std::string getNodeAttributes(SVFVar *node, IRGraph*)
    {
        if (SVFUtil::isa<ValVar>(node))
        {
            if(SVFUtil::isa<GepValVar>(node))
                return "shape=hexagon";
            else if (SVFUtil::isa<DummyValVar>(node))
                return "shape=diamond";
            else
                return "shape=box";
        }
        else if (SVFUtil::isa<ObjVar>(node))
        {
            if(SVFUtil::isa<GepObjVar>(node))
                return "shape=doubleoctagon";
            else if(SVFUtil::isa<BaseObjVar>(node))
                return "shape=box3d";
            else if (SVFUtil::isa<DummyObjVar>(node))
                return "shape=tab";
            else
                return "shape=component";
        }
        else if (SVFUtil::isa<RetValPN>(node))
        {
            return "shape=Mrecord";
        }
        else if (SVFUtil::isa<VarArgValPN>(node))
        {
            return "shape=octagon";
        }
        else
        {
            assert(0 && "no such kind!!");
        }
        return "";
    }
 
    template<class EdgeIter>
    static std::string getEdgeAttributes(SVFVar*, EdgeIter EI, IRGraph*)
    {
        std::string str;
        std::stringstream rawstr(str);
 
        rawstr << "shape=record";
 
        const SVFStmt* edge = *(EI.getCurrent());
        assert(edge && "No edge found!!");
        if (SVFUtil::isa<AddrStmt>(edge))
        {
            rawstr << ",color=green";
        }
        else if (SVFUtil::isa<CopyStmt>(edge))
        {
            rawstr << ",color=black";
        }
        else if (SVFUtil::isa<GepStmt>(edge))
        {
            rawstr << ",color=\"purple:purple\"";
        }
        else if (SVFUtil::isa<StoreStmt>(edge))
        {
            rawstr << ",color=blue";
        }
        else if (SVFUtil::isa<LoadStmt>(edge))
        {
            rawstr << ",color=red";
        }
        else if (SVFUtil::isa<PhiStmt>(edge))
        {
            rawstr << ",color=grey";
        }
        else if (SVFUtil::isa<SelectStmt>(edge))
        {
            rawstr << ",color=grey";
        }
        else if (SVFUtil::isa<CmpStmt>(edge))
        {
            rawstr << ",color=grey";
        }
        else if (SVFUtil::isa<BinaryOPStmt>(edge))
        {
            rawstr << ",color=grey";
        }
        else if (SVFUtil::isa<UnaryOPStmt>(edge))
        {
            rawstr << ",color=grey";
        }
        else if (SVFUtil::isa<BranchStmt>(edge))
        {
            rawstr << ",color=grey";
        }
        else if (SVFUtil::isa<TDForkPE>(edge))
        {
            rawstr << ",color=Turquoise";
        }
        else if (SVFUtil::isa<TDJoinPE>(edge))
        {
            rawstr << ",color=Turquoise";
        }
        else if (SVFUtil::isa<CallPE>(edge))
        {
            rawstr << ",color=black,style=dashed";
        }
        else if (SVFUtil::isa<RetPE>(edge))
        {
            rawstr << ",color=black,style=dotted";
        }
        else
        {
            assert(false && "No such kind edge!!");
        }
 
        return rawstr.str();
    }
 
    template<class EdgeIter>
    static std::string getEdgeSourceLabel(SVFVar*, EdgeIter EI)
    {
        const SVFStmt* edge = *(EI.getCurrent());
        assert(edge && "No edge found!!");
        if(const CallPE* calledge = SVFUtil::dyn_cast<CallPE>(edge))
        {
            return calledge->getFunEntryICFGNode()->getSourceLoc();
        }
        else if(const RetPE* retedge = SVFUtil::dyn_cast<RetPE>(edge))
        {
            return retedge->getCallSite()->getSourceLoc();
        }
        return "";
    }
};
} // End namespace llvm