SVFIRBuilder.h

Go to the documentation of this file.

//===- SVFIRBuilder.h -- Building SVFIR-------------------------------------------//
//
//                     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/>.
//
//===----------------------------------------------------------------------===//
 
/*
 * SVFIRBuilder.h
 *
 *  Created on: Nov 1, 2013
 *      Author: Yulei Sui
 *  Refactored on: Jan 25, 2024
 *      Author: Xiao Cheng, Yulei Sui
 */
 
#ifndef PAGBUILDER_H_
#define PAGBUILDER_H_
 
#include "SVFIR/SVFIR.h"
#include "SVF-LLVM/BasicTypes.h"
#include "SVF-LLVM/ICFGBuilder.h"
#include "SVF-LLVM/LLVMModule.h"
#include "SVF-LLVM/LLVMUtil.h"
 
namespace SVF
{
 
class SVFIRBuilder: public llvm::InstVisitor<SVFIRBuilder>
{
    friend class GraphDBSVFIRBuilder;
 
private:
    SVFIR* pag;
    const SVFBasicBlock* curBB; 
    const Value* curVal;    
 
 
    using AggregateField = std::vector<unsigned>;
    using AggregateFieldKey = std::pair<const Value*, AggregateField>;
    Map<AggregateFieldKey, NodeID> aggregateFieldNodes;
 
    bool getAggregateFieldOperands(const AggregateFieldKey& field,
                                   std::vector<AggregateFieldKey>& operands);
    bool getAggregateFieldNode(const Value* aggregate, const AggregateField& indices,
                               NodeID& node);
 
    struct AggregateCallField
    {
        NodeID object;  
        NodeID address; 
        NodeID value;   
    };
    struct AggregateCall
    {
        const Instruction* continuation;
        std::map<AggregateField, AggregateCallField> fields;
    };
    Map<const Function*, std::map<AggregateField, NodeID>> aggregateReturnParams;
    Map<const CallInst*, AggregateCall> aggregateCalls;
 
    void initialiseAggregateReturns();
    void addAggregateCallFields(const CallInst* call);
    void addAggregateReturnStores(ReturnInst& inst);
 
public:
    SVFIRBuilder(): pag(SVFIR::getPAG()), curBB(nullptr),curVal(nullptr)
    {
    }
    virtual ~SVFIRBuilder()
    {
    }
 
    virtual SVFIR* build();
 
    SVFIR* getPAG() const
    {
        return pag;
    }
 
    void createFunObjVars();
    void initFunObjVar();
 
 
    void initialiseNodes();
    void initialiseBaseObjVars();
    void initialiseValVars();
 
    void initSVFBasicBlock(const Function* func);
 
    void initDomTree(FunObjVar* func, const Function* f);
 
    void addEdge(NodeID src, NodeID dst, SVFStmt::PEDGEK kind,
                 APOffset offset = 0, Instruction* cs = nullptr);
    // @}
 
    void sanityCheck();
 
 
    // GetValNode - Return the value node according to a LLVM Value.
    NodeID getValueNode(const Value* V)
    {
        // first handle gep edge if val if a constant expression
        processCE(V);
 
        // strip off the constant cast and return the value node
        return llvmModuleSet()->getValueNode(V);
    }
 
    inline NodeID getObjectNode(const Value* V)
    {
        return llvmModuleSet()->getObjectNode(V);
    }
 
    inline NodeID getReturnNode(const FunObjVar *func)
    {
        return pag->getReturnNode(func);
    }
 
    inline NodeID getVarargNode(const FunObjVar *func)
    {
        return pag->getVarargNode(func);
    }
 
 
 
    // Instructions that cannot be folded away.
    virtual void visitAllocaInst(AllocaInst &AI);
    void visitPHINode(PHINode &I);
    void visitStoreInst(StoreInst &I);
    void visitLoadInst(LoadInst &I);
    void visitGetElementPtrInst(GetElementPtrInst &I);
    void visitCallInst(CallInst &I);
    void visitInvokeInst(InvokeInst &II);
    void visitCallBrInst(CallBrInst &I);
    void visitCallSite(CallBase* cs);
    void visitReturnInst(ReturnInst &I);
    void visitCastInst(CastInst &I);
    void visitSelectInst(SelectInst &I);
    void visitExtractValueInst(ExtractValueInst  &EVI);
    void visitBranchInst(BranchInst &I);
    void visitSwitchInst(SwitchInst &I);
    void visitInsertValueInst(InsertValueInst &I)
    {
        addBlackHoleAddrEdge(getValueNode(&I));
    }
    // TerminatorInst and UnwindInst have been removed since llvm-8.0.0
    // void visitTerminatorInst(TerminatorInst &TI) {}
    // void visitUnwindInst(UnwindInst &I) { /*returns void*/}
 
    void visitBinaryOperator(BinaryOperator &I);
    void visitUnaryOperator(UnaryOperator &I);
    void visitCmpInst(CmpInst &I);
 
    void visitVAArgInst(VAArgInst&);
    void visitVACopyInst(VACopyInst&) {}
    void visitVAEndInst(VAEndInst&) {}
    void visitVAStartInst(VAStartInst&) {}
 
    void visitFreezeInst(FreezeInst& I);
 
    void visitExtractElementInst(ExtractElementInst &I);
 
    void visitInsertElementInst(InsertElementInst &I)
    {
        addBlackHoleAddrEdge(getValueNode(&I));
    }
    void visitShuffleVectorInst(ShuffleVectorInst &I)
    {
        addBlackHoleAddrEdge(getValueNode(&I));
    }
    void visitLandingPadInst(LandingPadInst &I)
    {
        addBlackHoleAddrEdge(getValueNode(&I));
    }
 
    void visitResumeInst(ResumeInst&)   /*returns void*/
    {
    }
    void visitUnreachableInst(UnreachableInst&)   /*returns void*/
    {
    }
    void visitFenceInst(FenceInst &I)   /*returns void*/
    {
        addBlackHoleAddrEdge(getValueNode(&I));
    }
    void visitAtomicCmpXchgInst(AtomicCmpXchgInst &I)
    {
        addBlackHoleAddrEdge(getValueNode(&I));
    }
    void visitAtomicRMWInst(AtomicRMWInst &I)
    {
        addBlackHoleAddrEdge(getValueNode(&I));
    }
 
    inline void visitInstruction(Instruction&)
    {
        // If a new instruction is added to LLVM that we don't handle.
        // TODO: ignore here:
    }
    //}@
 
    void updateCallGraph(CallGraph* callgraph);
 
protected:
 
    void visitGlobal();
    void InitialGlobal(const GlobalVariable *gvar, Constant *C,
                       u32_t offset);
    NodeID getGlobalVarField(const GlobalVariable *gvar, u32_t offset, SVFType* tpy);
 
    void processCE(const Value* val);
 
    u32_t inferFieldIdxFromByteOffset(const llvm::GEPOperator* gepOp, DataLayout *dl, AccessPath& ap, APOffset idx);
 
    bool computeGepOffset(const User *V, AccessPath& ap);
 
    const Value* getBaseValueForExtArg(const Value* V);
 
    void handleDirectCall(CallBase* cs, const Function *F);
 
    void handleIndCall(CallBase* cs);
 
 
    virtual const Type *getBaseTypeAndFlattenedFields(const Value *V, std::vector<AccessPath> &fields, const Value* szValue);
    virtual void addComplexConsForExt(Value *D, Value *S, const Value* sz);
    virtual void handleNondetArgStoreAtExtCall(const CallBase* cs, const CallICFGNode* callICFGNode);
    virtual void handleExtCall(const CallBase* cs, const Function* callee);
 
    inline void setCurrentLocation(const Value* val, const BasicBlock* bb)
    {
        curBB = (bb == nullptr? nullptr : llvmModuleSet()->getSVFBasicBlock(bb));
        curVal = (val == nullptr ? nullptr: val);
    }
    inline void setCurrentLocation(const Value* val, const SVFBasicBlock* bb)
    {
        curBB = bb;
        curVal = val;
    }
    inline const Value* getCurrentValue() const
    {
        return curVal;
    }
    inline const SVFBasicBlock* getCurrentBB() const
    {
        return curBB;
    }
 
    void addGlobalBlackHoleAddrEdge(NodeID node, const ConstantExpr *int2Ptrce)
    {
        const Value* cval = getCurrentValue();
        const SVFBasicBlock* cbb = getCurrentBB();
        setCurrentLocation(int2Ptrce,(SVFBasicBlock*) nullptr);
        addBlackHoleAddrEdge(node);
        setCurrentLocation(cval,cbb);
    }
 
    inline NodeID addNullPtrNode()
    {
        LLVMContext& cxt = llvmModuleSet()->getContext();
        ConstantPointerNull* constNull = ConstantPointerNull::get(PointerType::getUnqual(cxt));
        NodeID nullPtr = pag->addConstantNullPtrValNode(pag->getNullPtr(), nullptr, llvmModuleSet()->getSVFType(constNull->getType()));
        llvmModuleSet()->addToSVFVar2LLVMValueMap(constNull, pag->getGNode(pag->getNullPtr()));
        setCurrentLocation(constNull, (SVFBasicBlock*) nullptr);
        addBlackHoleAddrEdge(pag->getBlkPtr());
        return nullPtr;
    }
 
    NodeID getGepValVar(const Value* val, const AccessPath& ap, const SVFType* elementType);
 
    NodeID getDirectAccessFieldZeroValVar(const Value* ptr, const Type* accessTy);
 
    void setCurrentBBAndValueForPAGEdge(PAGEdge* edge);
 
    inline void addBlackHoleAddrEdge(NodeID node)
    {
        if(PAGEdge *edge = pag->addBlackHoleAddrStmt(node))
            setCurrentBBAndValueForPAGEdge(edge);
    }
 
    inline AddrStmt* addAddrEdge(NodeID src, NodeID dst)
    {
        if(AddrStmt *edge = pag->addAddrStmt(src, dst))
        {
            setCurrentBBAndValueForPAGEdge(edge);
            return edge;
        }
        return nullptr;
    }
 
    inline AddrStmt* addAddrWithStackArraySz(NodeID src, NodeID dst, llvm::AllocaInst& inst)
    {
        AddrStmt* edge = addAddrEdge(src, dst);
        if (inst.getArraySize())
        {
            edge->addArrSize(pag->getGNode(getValueNode(inst.getArraySize())));
        }
        return edge;
    }
 
    inline AddrStmt* addAddrWithHeapSz(NodeID src, NodeID dst, const CallBase* cs)
    {
        // get name of called function
        AddrStmt* edge = addAddrEdge(src, dst);
 
        llvm::Function* calledFunc = cs->getCalledFunction();
        std::string functionName;
        if (calledFunc)
        {
            functionName = calledFunc->getName().str();
        }
        else
        {
            SVFUtil::writeWrnMsg("not support indirect call to add AddrStmt.\n");
        }
        if (functionName == "malloc")
        {
            if (cs->arg_size() > 0)
            {
                const llvm::Value* val = cs->getArgOperand(0);
                edge->addArrSize(pag->getGNode(getValueNode(val)));
            }
        }
        // Check if the function called is 'calloc' and process its arguments.
        // e.g. "%5 = call i8* @calloc(1, 8)", edge should add two SVFValue (1 and 8)
        else if (functionName == "calloc")
        {
            if (cs->arg_size() > 1)
            {
                edge->addArrSize(
                    pag->getGNode(getValueNode(cs->getArgOperand(0))));
                edge->addArrSize(
                    pag->getGNode(getValueNode(cs->getArgOperand(1))));
            }
        }
        else
        {
            if (cs->arg_size() > 0)
            {
                const llvm::Value* val = cs->getArgOperand(0);
                edge->addArrSize(pag->getGNode(getValueNode(val)));
            }
        }
        return edge;
    }
 
    inline CopyStmt* addCopyEdge(NodeID src, NodeID dst, CopyStmt::CopyKind kind)
    {
        if(CopyStmt *edge = pag->addCopyStmt(src, dst, kind))
        {
            setCurrentBBAndValueForPAGEdge(edge);
            return edge;
        }
        return nullptr;
    }
 
    inline CopyStmt::CopyKind getCopyKind(const Value* val)
    {
        // COPYVAL, ZEXT, SEXT, BITCAST, FPTRUNC, FPTOUI, FPTOSI, UITOFP, SITOFP, INTTOPTR, PTRTOINT
        if (const Instruction* inst = SVFUtil::dyn_cast<Instruction>(val))
        {
            switch (inst->getOpcode())
            {
            case Instruction::ZExt:
                return CopyStmt::ZEXT;
            case Instruction::SExt:
                return CopyStmt::SEXT;
            case Instruction::BitCast:
                return CopyStmt::BITCAST;
            case Instruction ::Trunc:
                return CopyStmt::TRUNC;
            case Instruction::FPTrunc:
                return CopyStmt::FPTRUNC;
            case Instruction::FPToUI:
                return CopyStmt::FPTOUI;
            case Instruction::FPToSI:
                return CopyStmt::FPTOSI;
            case Instruction::UIToFP:
                return CopyStmt::UITOFP;
            case Instruction::SIToFP:
                return CopyStmt::SITOFP;
            case Instruction::IntToPtr:
                return CopyStmt::INTTOPTR;
            case Instruction::PtrToInt:
                return CopyStmt::PTRTOINT;
            default:
                return CopyStmt::COPYVAL;
            }
        }
        assert (false && "Unknown cast inst!");
        abort();
    }
 
    inline void addPhiStmt(NodeID res, NodeID opnd, const ICFGNode* pred)
    {
        if(PhiStmt *edge = pag->addPhiStmt(res,opnd,pred))
            setCurrentBBAndValueForPAGEdge(edge);
    }
    inline void addSelectStmt(NodeID res, NodeID op1, NodeID op2, NodeID cond)
    {
        if(SelectStmt *edge = pag->addSelectStmt(res,op1,op2,cond))
            setCurrentBBAndValueForPAGEdge(edge);
    }
    inline void addCmpEdge(NodeID op1, NodeID op2, NodeID dst, u32_t predict)
    {
        if(CmpStmt *edge = pag->addCmpStmt(op1, op2, dst, predict))
            setCurrentBBAndValueForPAGEdge(edge);
    }
    inline void addBinaryOPEdge(NodeID op1, NodeID op2, NodeID dst, u32_t opcode)
    {
        if(BinaryOPStmt *edge = pag->addBinaryOPStmt(op1, op2, dst, opcode))
            setCurrentBBAndValueForPAGEdge(edge);
    }
    inline void addUnaryOPEdge(NodeID src, NodeID dst, u32_t opcode)
    {
        if(UnaryOPStmt *edge = pag->addUnaryOPStmt(src, dst, opcode))
            setCurrentBBAndValueForPAGEdge(edge);
    }
    inline void addBranchStmt(NodeID br, NodeID cond, const BranchStmt::SuccAndCondPairVec& succs)
    {
        if(BranchStmt *edge = pag->addBranchStmt(br, cond, succs))
            setCurrentBBAndValueForPAGEdge(edge);
    }
    inline void addLoadEdge(NodeID src, NodeID dst)
    {
        if(LoadStmt *edge = pag->addLoadStmt(src, dst))
            setCurrentBBAndValueForPAGEdge(edge);
    }
    inline void addStoreEdge(NodeID src, NodeID dst)
    {
        ICFGNode* node;
        if (const Instruction* inst = SVFUtil::dyn_cast<Instruction>(curVal))
            node = llvmModuleSet()->getICFGNode(
                       SVFUtil::cast<Instruction>(inst));
        else
            node = nullptr;
        if (StoreStmt* edge = pag->addStoreStmt(src, dst, node))
            setCurrentBBAndValueForPAGEdge(edge);
    }
    inline void addCallEdge(NodeID src, NodeID dst, const CallICFGNode* cs, const FunEntryICFGNode* entry)
    {
        if (CallPE* edge = pag->addCallPE(src, dst, cs, entry))
            setCurrentBBAndValueForPAGEdge(edge);
    }
    inline void addRetEdge(NodeID src, NodeID dst, const CallICFGNode* cs, const FunExitICFGNode* exit)
    {
        if (RetPE* edge = pag->addRetPE(src, dst, cs, exit))
            setCurrentBBAndValueForPAGEdge(edge);
    }
    inline void addGepEdge(NodeID src, NodeID dst, const AccessPath& ap, bool constGep)
    {
        if (GepStmt* edge = pag->addGepStmt(src, dst, ap, constGep))
            setCurrentBBAndValueForPAGEdge(edge);
    }
    inline void addNormalGepEdge(NodeID src, NodeID dst, const AccessPath& ap)
    {
        if (GepStmt* edge = pag->addNormalGepStmt(src, dst, ap))
            setCurrentBBAndValueForPAGEdge(edge);
    }
    inline void addVariantGepEdge(NodeID src, NodeID dst, const AccessPath& ap)
    {
        if (GepStmt* edge = pag->addVariantGepStmt(src, dst, ap))
            setCurrentBBAndValueForPAGEdge(edge);
    }
    inline void addThreadForkEdge(NodeID src, NodeID dst, const CallICFGNode* cs, const FunEntryICFGNode* entry)
    {
        if (TDForkPE* edge = pag->addThreadForkPE(src, dst, cs, entry))
            setCurrentBBAndValueForPAGEdge(edge);
    }
    inline void addThreadJoinEdge(NodeID src, NodeID dst, const CallICFGNode* cs, const FunExitICFGNode* exit)
    {
        if (TDJoinPE* edge = pag->addThreadJoinPE(src, dst, cs, exit))
            setCurrentBBAndValueForPAGEdge(edge);
    }
 
    AccessPath getAccessPathFromBaseNode(NodeID nodeId);
 
private:
    LLVMModuleSet* llvmModuleSet()
    {
        return LLVMModuleSet::getLLVMModuleSet();
    }
};
 
} // End namespace SVF
 
#endif /* PAGBUILDER_H_ */