SVFIRBuilder.cpp

Go to the documentation of this file.

//===- SVFIRBuilder.cpp -- SVFIR builder-----------------------------------------//
//
//                     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.cpp
 *
 *  Created on: Nov 1, 2013
 *      Author: Yulei Sui
 *  Refactored on: Jan 25, 2024
 *      Author: Xiao Cheng, Yulei Sui
 */
 
#include "SVF-LLVM/SVFIRBuilder.h"
#include "SVF-LLVM/BasicTypes.h"
#include "SVF-LLVM/CHGBuilder.h"
#include "SVF-LLVM/CppUtil.h"
#include "SVF-LLVM/LLVMLoopAnalysis.h"
#include "SVF-LLVM/LLVMUtil.h"
#include "SVF-LLVM/ObjTypeInference.h"
#include "SVF-LLVM/SymbolTableBuilder.h"
#include "SVFIR/PAGBuilderFromFile.h"
#include "Util/CallGraphBuilder.h"
#include "Graphs/CallGraph.h"
#include "Util/Options.h"
#include "Util/SVFUtil.h"
 
using namespace std;
using namespace SVF;
using namespace SVFUtil;
using namespace LLVMUtil;
 
 
SVFIR* SVFIRBuilder::build()
{
    double startTime = SVFStat::getClk(true);
 
    DBOUT(DGENERAL, outs() << pasMsg("\t Building SVFIR ...\n"));
 
    // If the SVFIR has been built before, then we return the unique SVFIR of the program
    if(pag->getNodeNumAfterPAGBuild() > 1)
        return pag;
 
 
    createFunObjVars();
 
    ICFGBuilder icfgbuilder;
    pag->icfg = icfgbuilder.build();
 
    initialiseNodes();
    initialiseAggregateReturns();
    visitGlobal();
 
 
 
    CallGraphBuilder callGraphBuilder;
    std::vector<const FunObjVar*> funset;
    for (const auto& item: llvmModuleSet()->getFunctionSet())
    {
        funset.push_back(llvmModuleSet()->getFunObjVar(item));
    }
    pag->callGraph = callGraphBuilder.buildSVFIRCallGraph(funset);
 
    CHGraph* chg = new CHGraph();
    CHGBuilder chgbuilder(chg);
    chgbuilder.buildCHG();
    pag->setCHG(chg);
 
    for (Module& M : llvmModuleSet()->getLLVMModules())
    {
        for (Module::const_iterator F = M.begin(), E = M.end(); F != E; ++F)
        {
            const Function& fun = *F;
            const FunObjVar* svffun = llvmModuleSet()->getFunObjVar(&fun);
            if(!fun.isDeclaration())
            {
                if (fun.doesNotReturn() == false &&
                        fun.getReturnType()->isVoidTy() == false)
                {
                    pag->addFunRet(svffun,
                                   pag->getValVar(pag->getReturnNode(svffun)));
                }
 
                for (Function::const_arg_iterator I = fun.arg_begin(), E = fun.arg_end();
                        I != E; ++I)
                {
                    setCurrentLocation(&*I,&fun.getEntryBlock());
                    NodeID argValNodeId = llvmModuleSet()->getValueNode(&*I);
                    // if this is the function does not have caller (e.g. main)
                    // or a dead function, shall we create a black hole address edge for it?
                    // it is (1) too conservative, and (2) make FormalParmVFGNode defined at blackhole address PAGEdge.
                    // if(SVFUtil::ArgInNoCallerFunction(&*I)) {
                    //    if(I->getType()->isPointerTy())
                    //        addBlackHoleAddrEdge(argValNodeId);
                    //}
                    pag->addFunArgs(svffun,pag->getValVar(argValNodeId));
                }
                auto returns = aggregateReturnParams.find(&fun);
                if (returns != aggregateReturnParams.end())
                    for (const auto& field : returns->second)
                        pag->addFunArgs(svffun, pag->getValVar(field.second));
            }
            for (Function::const_iterator bit = fun.begin(), ebit = fun.end();
                    bit != ebit; ++bit)
            {
                const BasicBlock& bb = *bit;
                for (BasicBlock::const_iterator it = bb.begin(), eit = bb.end();
                        it != eit; ++it)
                {
                    const Instruction& inst = *it;
                    setCurrentLocation(&inst,&bb);
                    visit(const_cast<Instruction&>(inst));
                }
            }
        }
    }
 
    sanityCheck();
 
    pag->initialiseCandidatePointers();
 
    pag->setNodeNumAfterPAGBuild(pag->getTotalNodeNum());
 
    // dump SVFIR
    if (Options::PAGDotGraph())
        pag->dump("svfir_initial");
 
    // print to command line of the SVFIR graph
    if (Options::PAGPrint())
        pag->print();
 
    // dump ICFG
    if (Options::DumpICFG())
        pag->getICFG()->dump("icfg_initial");
 
    if (Options::LoopAnalysis())
    {
        LLVMLoopAnalysis loopAnalysis;
        loopAnalysis.build(pag->getICFG());
    }
 
    // dump SVFIR as JSON
    if (!Options::DumpJson().empty())
    {
        assert(false && "please implement SVFIRWriter::writeJsonToPath");
    }
 
    double endTime = SVFStat::getClk(true);
    SVFStat::timeOfBuildingSVFIR = (endTime - startTime) / TIMEINTERVAL;
 
    return pag;
}
 
void SVFIRBuilder::initFunObjVar()
{
    for (Module& mod : llvmModuleSet()->getLLVMModules())
    {
        for (const Function& f : mod.functions())
        {
            FunObjVar* svffun = const_cast<FunObjVar*>(llvmModuleSet()->getFunObjVar(&f));
            initSVFBasicBlock(&f);
 
            if (!LLVMUtil::isExtCall(&f))
            {
                initDomTree(svffun, &f);
            }
            const Function *realfun = llvmModuleSet()->getRealDefFun(&f);
            svffun->setRelDefFun(realfun == nullptr ? nullptr : llvmModuleSet()->getFunObjVar(realfun));
        }
    }
 
    // Store annotations of functions in extapi.bc
    for (const auto& pair : llvmModuleSet()->ExtFun2Annotations)
    {
        ExtAPI::getExtAPI()->setExtFuncAnnotations(llvmModuleSet()->getFunObjVar(pair.first), pair.second);
    }
 
}
 
void SVFIRBuilder::initSVFBasicBlock(const Function* func)
{
    FunObjVar *svfFun = const_cast<FunObjVar *>(llvmModuleSet()->getFunObjVar(func));
    for (Function::const_iterator bit = func->begin(), ebit = func->end(); bit != ebit; ++bit)
    {
        const BasicBlock* bb = &*bit;
        SVFBasicBlock* svfbb = llvmModuleSet()->getSVFBasicBlock(bb);
        for (succ_const_iterator succ_it = succ_begin(bb); succ_it != succ_end(bb); succ_it++)
        {
            const SVFBasicBlock* svf_scc_bb = llvmModuleSet()->getSVFBasicBlock(*succ_it);
            svfbb->addSuccBasicBlock(svf_scc_bb);
        }
        for (const_pred_iterator pred_it = pred_begin(bb); pred_it != pred_end(bb); pred_it++)
        {
            const SVFBasicBlock* svf_pred_bb = llvmModuleSet()->getSVFBasicBlock(*pred_it);
            svfbb->addPredBasicBlock(svf_pred_bb);
        }
 
        if (svfbb->getSuccessors().empty())
        {
            if (LLVMUtil::basicBlockHasRetInst(bb))
            {
                assert((LLVMUtil::functionDoesNotRet(func) ||
                        SVFUtil::isa<ReturnInst>(bb->back())) &&
                       "last inst must be return inst");
                svfFun->setExitBlock(svfbb);
            }
        }
    }
    // For no return functions, we set the last block as exit BB
    // This ensures that each function that has definition must have an exit BB
    if (svfFun->hasBasicBlock() && svfFun->exitBlock == nullptr)
    {
        SVFBasicBlock* retBB = const_cast<SVFBasicBlock*>(svfFun->back());
        assert((LLVMUtil::functionDoesNotRet(func) ||
                SVFUtil::isa<ReturnInst>(&func->back().back())) &&
               "last inst must be return inst");
        svfFun->setExitBlock(retBB);
    }
}
 
 
void SVFIRBuilder::initDomTree(FunObjVar* svffun, const Function* fun)
{
    if (fun->isDeclaration())
        return;
    //process and stored dt & df
    DominanceFrontier df;
    DominatorTree& dt = llvmModuleSet()->getDomTree(fun);
    df.analyze(dt);
    LoopInfo loopInfo = LoopInfo(dt);
    PostDominatorTree pdt = PostDominatorTree(const_cast<Function&>(*fun));
    SVFLoopAndDomInfo* ld = svffun->getLoopAndDomInfo();
 
    Map<const SVFBasicBlock*,Set<const SVFBasicBlock*>> & dfBBsMap = ld->getDomFrontierMap();
    for (DominanceFrontierBase::const_iterator dfIter = df.begin(), eDfIter = df.end(); dfIter != eDfIter; dfIter++)
    {
        const BasicBlock* keyBB = dfIter->first;
#if LLVM_VERSION_MAJOR > 16
        const llvm::SetVector<llvm::BasicBlock* >& domSet = dfIter->second;
#else
        const std::set<BasicBlock* >& domSet = dfIter->second;
#endif
        Set<const SVFBasicBlock*>& valueBasicBlocks = dfBBsMap[llvmModuleSet()->getSVFBasicBlock(keyBB)];
        for (const BasicBlock* bbValue:domSet)
        {
            valueBasicBlocks.insert(llvmModuleSet()->getSVFBasicBlock(bbValue));
        }
    }
    std::vector<const SVFBasicBlock*> reachableBBs;
    LLVMUtil::getFunReachableBBs(fun, reachableBBs);
    ld->setReachableBBs(reachableBBs);
 
    for (Function::const_iterator bit = fun->begin(), beit = fun->end(); bit!=beit; ++bit)
    {
        const BasicBlock &bb = *bit;
        SVFBasicBlock* svfBB = llvmModuleSet()->getSVFBasicBlock(&bb);
        if (DomTreeNode* dtNode = dt.getNode(&bb))
        {
            SVFLoopAndDomInfo::BBSet& bbSet = ld->getDomTreeMap()[svfBB];
            for (const auto domBB : *dtNode)
            {
                const auto* domSVFBB = llvmModuleSet()->getSVFBasicBlock(domBB->getBlock());
                bbSet.insert(domSVFBB);
            }
        }
 
        if (DomTreeNode* pdtNode = pdt.getNode(&bb))
        {
            u32_t level = pdtNode->getLevel();
            ld->getBBPDomLevel()[svfBB] = level;
            BasicBlock* idomBB = pdtNode->getIDom()->getBlock();
            const SVFBasicBlock* idom = idomBB == NULL ? NULL: llvmModuleSet()->getSVFBasicBlock(idomBB);
            ld->getBB2PIdom()[svfBB] = idom;
 
            SVFLoopAndDomInfo::BBSet& bbSet = ld->getPostDomTreeMap()[svfBB];
            for (const auto domBB : *pdtNode)
            {
                const auto* domSVFBB = llvmModuleSet()->getSVFBasicBlock(domBB->getBlock());
                bbSet.insert(domSVFBB);
            }
        }
 
        if (const Loop* loop = loopInfo.getLoopFor(&bb))
        {
            for (const BasicBlock* loopBlock : loop->getBlocks())
            {
                const SVFBasicBlock* loopbb = llvmModuleSet()->getSVFBasicBlock(loopBlock);
                ld->addToBB2LoopMap(svfBB, loopbb);
            }
        }
    }
}
 
void SVFIRBuilder::createFunObjVars()
{
    std::vector<FunObjVar*> funset;
    // Iterate over all object symbols in the symbol table
    for (const auto* fun: llvmModuleSet()->getFunctionSet())
    {
        u32_t id = llvmModuleSet()->objSyms()[fun];
        // Debug output for adding object node
        DBOUT(DPAGBuild, outs() << "add obj node " << id << "\n");
 
        // Check if the value is a function and add a function object node
        pag->addFunObjNode(id, pag->getObjTypeInfo(id), nullptr);
        llvmModuleSet()->LLVMFun2FunObjVar[fun] = cast<FunObjVar>(pag->getGNode(id));
 
        FunObjVar *funObjVar = SVFUtil::cast<FunObjVar>(pag->getGNode(id));
        funset.push_back(funObjVar);
 
        funObjVar->initFunObjVar(fun->isDeclaration(), LLVMUtil::isIntrinsicFun(fun), fun->hasAddressTaken(),
                                 LLVMUtil::isUncalledFunction(fun), LLVMUtil::functionDoesNotRet(fun), fun->isVarArg(),
                                 SVFUtil::cast<SVFFunctionType>(llvmModuleSet()->getSVFType(fun->getFunctionType())),
                                 new SVFLoopAndDomInfo, nullptr, nullptr,
                                 {}, nullptr);
        BasicBlockGraph* bbGraph = new BasicBlockGraph();
        funObjVar->setBasicBlockGraph(bbGraph);
 
 
        for (const BasicBlock& bb : *fun)
        {
            llvmModuleSet()->addBasicBlock(funObjVar, &bb);
        }
 
        for (auto& bb: *funObjVar->bbGraph)
        {
            bb.second->setFun(funObjVar);
        }
        llvmModuleSet()->addToSVFVar2LLVMValueMap(fun, pag->getGNode(id));
    }
 
    initFunObjVar();
}
 
void SVFIRBuilder::initialiseBaseObjVars()
{
    // Iterate over all object symbols in the symbol table
    for (LLVMModuleSet::ValueToIDMapTy::iterator iter =
                llvmModuleSet()->objSyms().begin(); iter != llvmModuleSet()->objSyms().end();
            ++iter)
    {
        // Debug output for adding object node
        DBOUT(DPAGBuild, outs() << "add obj node " << iter->second << "\n");
 
        // Skip blackhole and constant symbols
        if(iter->second == pag->blackholeSymID() || iter->second == pag->constantSymID())
            continue;
 
        // Get the LLVM value corresponding to the symbol
        const Value* llvmValue = iter->first;
 
        const ICFGNode* icfgNode = nullptr;
        if (const Instruction* inst = SVFUtil::dyn_cast<Instruction>(llvmValue))
        {
            if(llvmModuleSet()->hasICFGNode(inst))
                icfgNode = llvmModuleSet()->getICFGNode(inst);
        }
 
        // Check if the value is a function and add a function object node
        if (SVFUtil::dyn_cast<Function>(llvmValue))
        {
            // already one
        }
        // Check if the value is a heap object and add a heap object node
        else if (LLVMUtil::isHeapObj(llvmValue))
        {
            NodeID id = llvmModuleSet()->getObjectNode(iter->first);
            pag->addHeapObjNode(iter->second, pag->getObjTypeInfo(id), icfgNode);
        }
        // Check if the value is an alloca instruction and add a stack object node
        else if (LLVMUtil::isStackObj(llvmValue))
        {
            NodeID id = llvmModuleSet()->getObjectNode(iter->first);
            pag->addStackObjNode(iter->second, pag->getObjTypeInfo(id), icfgNode);
        }
        else if (auto fpValue = SVFUtil::dyn_cast<ConstantFP>(llvmValue))
        {
            NodeID id = llvmModuleSet()->getObjectNode(iter->first);
            pag->addConstantFPObjNode(iter->second, pag->getObjTypeInfo(id),  LLVMUtil::getDoubleValue(fpValue), icfgNode);
        }
        else if (auto intValue = SVFUtil::dyn_cast<ConstantInt>(llvmValue))
        {
            NodeID id = llvmModuleSet()->getObjectNode(iter->first);
            pag->addConstantIntObjNode(iter->second, pag->getObjTypeInfo(id), LLVMUtil::getIntegerValue(intValue), icfgNode);
        }
        else if (SVFUtil::isa<ConstantPointerNull>(llvmValue))
        {
            NodeID id = llvmModuleSet()->getObjectNode(iter->first);
            pag->addConstantNullPtrObjNode(iter->second, pag->getObjTypeInfo(id), icfgNode);
        }
        else if (SVFUtil::isa<GlobalValue>(llvmValue))
        {
            NodeID id = llvmModuleSet()->getObjectNode(iter->first);
            pag->addGlobalObjNode(iter->second, pag->getObjTypeInfo(id), icfgNode);
        }
        else if (SVFUtil::isa<ConstantData, ConstantExpr, MetadataAsValue, BlockAddress, ConstantAggregate>(llvmValue))
        {
            NodeID id = llvmModuleSet()->getObjectNode(iter->first);
            pag->addConstantDataObjNode(iter->second, pag->getObjTypeInfo(id), icfgNode);
        }
        // Add a generic object node for other types of values
        else
        {
            NodeID id = llvmModuleSet()->getObjectNode(iter->first);
            pag->addObjNode(iter->second, pag->getObjTypeInfo(id), icfgNode);
        }
        llvmModuleSet()->addToSVFVar2LLVMValueMap(llvmValue, pag->getGNode(iter->second));
    }
 
}
 
void SVFIRBuilder::initialiseValVars()
{
    // Iterate over all value symbols in the symbol table
    for (LLVMModuleSet::ValueToIDMapTy::iterator iter =
                llvmModuleSet()->valSyms().begin(); iter != llvmModuleSet()->valSyms().end();
            ++iter)
    {
        // Debug output for adding value node
        DBOUT(DPAGBuild, outs() << "add val node " << iter->second << "\n");
 
        // Skip blackhole and null pointer symbols
        if(iter->second == pag->blkPtrSymID() || iter->second == pag->nullPtrSymID())
            continue;
 
        const ICFGNode* icfgNode = nullptr;
        auto llvmValue = iter->first;
 
        // Check if the value is a function and get its call graph node
        if (const Function* func = SVFUtil::dyn_cast<Function>(llvmValue))
        {
            pag->addFunValNode(iter->second, icfgNode, llvmModuleSet()->getFunObjVar(func), llvmModuleSet()->getSVFType(llvmValue->getType()));
        }
        else if (auto argval = SVFUtil::dyn_cast<Argument>(llvmValue))
        {
            // Formal params are defined at FunEntryICFGNode (where CallPE copies actual args).
            // External (declaration-only) functions have no entry node, so keep nullptr.
            const FunObjVar* funObj = llvmModuleSet()->getFunObjVar(argval->getParent());
            const ICFGNode* entryNode = funObj->isDeclaration() ? nullptr : pag->getICFG()->getFunEntryICFGNode(funObj);
            pag->addArgValNode(
                iter->second, argval->getArgNo(), entryNode,
                funObj, llvmModuleSet()->getSVFType(llvmValue->getType()));
            if (!argval->hasName())
                pag->getGNode(iter->second)->setName("arg_" + std::to_string(argval->getArgNo()));
        }
        else if (auto fpValue = SVFUtil::dyn_cast<ConstantFP>(llvmValue))
        {
            pag->addConstantFPValNode(iter->second, LLVMUtil::getDoubleValue(fpValue), icfgNode, llvmModuleSet()->getSVFType(llvmValue->getType()));
        }
        else if (auto intValue = SVFUtil::dyn_cast<ConstantInt>(llvmValue))
        {
            pag->addConstantIntValNode(iter->second, LLVMUtil::getIntegerValue(intValue), icfgNode, llvmModuleSet()->getSVFType(llvmValue->getType()));
        }
        else if (SVFUtil::isa<ConstantPointerNull>(llvmValue))
        {
            pag->addConstantNullPtrValNode(iter->second, icfgNode, llvmModuleSet()->getSVFType(llvmValue->getType()));
        }
        else if (SVFUtil::isa<GlobalValue>(llvmValue))
        {
            // Global variables are defined at the global ICFG node.
            pag->addGlobalValNode(iter->second, pag->getICFG()->getGlobalICFGNode(),
                                  llvmModuleSet()->getSVFType(llvmValue->getType()));
        }
        else if (SVFUtil::isa<ConstantData, ConstantExpr, MetadataAsValue, BlockAddress, ConstantAggregate>(llvmValue))
        {
            pag->addConstantDataValNode(iter->second, icfgNode, llvmModuleSet()->getSVFType(llvmValue->getType()));
        }
        else if (SVFUtil::isa<InlineAsm>(llvmValue) ||
                 SVFUtil::isa<DSOLocalEquivalent>(llvmValue) ||
                 SVFUtil::isa<NoCFIValue>(llvmValue))
        {
            pag->addAsmPCValNode(iter->second, llvmModuleSet()->getSVFType(llvmValue->getType()));
        }
        else if (const Instruction* inst = SVFUtil::dyn_cast<Instruction>(llvmValue))
        {
            if (LLVMUtil::isIntrinsicInst(inst))
                pag->addIntrinsicValNode(iter->second, llvmModuleSet()->getSVFType(llvmValue->getType()));
            else
            {
                assert(llvmModuleSet()->hasICFGNode(inst) && "LLVM instruction is not associated with an ICFGNode");
                icfgNode = llvmModuleSet()->getICFGNode(inst);
                pag->addValNode(iter->second, llvmModuleSet()->getSVFType(llvmValue->getType()), icfgNode);
            }
        }
        llvmModuleSet()->addToSVFVar2LLVMValueMap(llvmValue,
                pag->getGNode(iter->second));
    }
}
 
 
/*
 * Initial all the nodes from symbol table
 */
void SVFIRBuilder::initialiseNodes()
{
    DBOUT(DPAGBuild, outs() << "Initialise SVFIR Nodes ...\n");
 
 
    pag->addBlackholeObjNode();
    pag->addConstantObjNode();
    pag->addBlackholePtrNode();
    addNullPtrNode();
 
    initialiseBaseObjVars();
    initialiseValVars();
 
    for (LLVMModuleSet::FunToIDMapTy::iterator iter =
                llvmModuleSet()->retSyms().begin(); iter != llvmModuleSet()->retSyms().end();
            ++iter)
    {
        const Value* llvmValue = iter->first;
        // retSyms keys are Function*, not Instruction, so dyn_cast<Instruction> always fails.
        // RetValPN represents the callee's return value, defined at FunExitICFGNode.
        // External functions have no exit node, so keep nullptr.
        const FunObjVar* funObjVar = llvmModuleSet()->getFunObjVar(SVFUtil::cast<Function>(llvmValue));
        const ICFGNode* icfgNode = funObjVar->isDeclaration() ? nullptr : pag->getICFG()->getFunExitICFGNode(funObjVar);
        DBOUT(DPAGBuild, outs() << "add ret node " << iter->second << "\n");
        pag->addRetNode(iter->second,
                        funObjVar,
                        llvmModuleSet()->getSVFType(iter->first->getType()), icfgNode);
        llvmModuleSet()->addToSVFVar2LLVMValueMap(llvmValue, pag->getGNode(iter->second));
        pag->returnFunObjSymMap[funObjVar] = iter->second;
    }
 
    for (LLVMModuleSet::FunToIDMapTy::iterator iter =
                llvmModuleSet()->varargSyms().begin();
            iter != llvmModuleSet()->varargSyms().end(); ++iter)
    {
        const Value* llvmValue = iter->first;
        // varargSyms keys are Function*, not Instruction.
        // Variadic arguments are received at the function entry point.
        // External functions have no entry node, so keep nullptr.
        const FunObjVar* funObjVar = llvmModuleSet()->getFunObjVar(SVFUtil::cast<Function>(llvmValue));
        const ICFGNode* icfgNode = funObjVar->isDeclaration() ? nullptr : pag->getICFG()->getFunEntryICFGNode(funObjVar);
        DBOUT(DPAGBuild, outs() << "add vararg node " << iter->second << "\n");
        pag->addVarargNode(iter->second,
                           funObjVar,
                           llvmModuleSet()->getSVFType(iter->first->getType()), icfgNode);
        llvmModuleSet()->addToSVFVar2LLVMValueMap(llvmValue, pag->getGNode(iter->second));
        pag->varargFunObjSymMap[funObjVar] = iter->second;
    }
 
    for (LLVMModuleSet::ValueToIDMapTy::iterator iter =
                llvmModuleSet()->objSyms().begin(); iter != llvmModuleSet()->objSyms().end(); ++iter)
    {
        DBOUT(DPAGBuild, outs() << "add address edges for constant node " << iter->second << "\n");
        const Value* val = iter->first;
        if (isConstantObjSym(val))
        {
            NodeID ptr = llvmModuleSet()->getValueNode(val);
            if(ptr!= pag->getBlkPtr() && ptr!= pag->getNullPtr())
            {
                setCurrentLocation(val, (SVFBasicBlock*) nullptr);
                addAddrEdge(iter->second, ptr);
            }
        }
    }
 
    assert(pag->getTotalNodeNum() >= pag->getTotalSymNum()
           && "not all node have been initialized!!!");
 
    for (auto& fun: llvmModuleSet()->getFunctionSet())
    {
        for (const Argument& arg : fun->args())
        {
            const_cast<FunObjVar*>(llvmModuleSet()->getFunObjVar(fun))->addArgument(SVFUtil::cast<ArgValVar>(
                        pag->getGNode(llvmModuleSet()->getValueNode(&arg))));
        }
    }
 
}
 
/*
    https://github.com/SVF-tools/SVF/issues/524
    Handling single value types, for constant index, including pointer, integer, etc
    e.g. field_idx = getelementptr i8, %i8* %p, i64 -4
    We can obtain the field index by inferring the byteoffset if %p is casted from a pointer to a struct
    For another example, the following can be an array access.
    e.g. field_idx = getelementptr i8, %struct_type %p, i64 1
 
*/
u32_t SVFIRBuilder::inferFieldIdxFromByteOffset(const llvm::GEPOperator* gepOp, DataLayout *dl, AccessPath& ap, APOffset idx)
{
    return 0;
}
 
bool SVFIRBuilder::computeGepOffset(const User *V, AccessPath& ap)
{
    assert(V);
 
    const llvm::GEPOperator *gepOp = SVFUtil::dyn_cast<const llvm::GEPOperator>(V);
    DataLayout * dataLayout = getDataLayout(llvmModuleSet()->getMainLLVMModule());
    llvm::APInt byteOffset(dataLayout->getIndexSizeInBits(gepOp->getPointerAddressSpace()),0,true);
    if(gepOp && dataLayout && gepOp->accumulateConstantOffset(*dataLayout,byteOffset))
    {
        //s32_t bo = byteOffset.getSExtValue();
    }
 
    bool isConst = true;
 
    bool prevPtrOperand = false;
    for (bridge_gep_iterator gi = bridge_gep_begin(*V), ge = bridge_gep_end(*V);
            gi != ge; ++gi)
    {
        const Type* gepTy = *gi;
        const SVFType* svfGepTy = llvmModuleSet()->getSVFType(gepTy);
 
        assert((prevPtrOperand && svfGepTy->isPointerTy()) == false &&
               "Expect no more than one gep operand to be of a pointer type");
        if(!prevPtrOperand && svfGepTy->isPointerTy()) prevPtrOperand = true;
        const Value* offsetVal = gi.getOperand();
        assert(gepTy != offsetVal->getType() && "iteration and operand have the same type?");
 
        const ArrayType* inferredPtrArrayTy = nullptr;
        const SVFType* idxGepTy = svfGepTy;
        if (svfGepTy->isPointerTy() && gepOp->getSourceElementType()->isSingleValueType())
        {
            const Type* baseObjType =
                LLVMModuleSet::getLLVMModuleSet()->getTypeInference()->inferObjType(gepOp->getPointerOperand());
            if (const auto* arrTy = SVFUtil::dyn_cast<ArrayType>(baseObjType))
            {
                if (arrTy->getElementType()->isPointerTy())
                {
                    inferredPtrArrayTy = arrTy;
                    idxGepTy = llvmModuleSet()->getSVFType(arrTy);
                }
            }
        }
 
        ap.addOffsetVarAndGepTypePair(getPAG()->getValVar(llvmModuleSet()->getValueNode(offsetVal)), idxGepTy);
 
        //The int value of the current index operand
        const ConstantInt* op = SVFUtil::dyn_cast<ConstantInt>(offsetVal);
 
        // if Options::ModelConsts() is disabled. We will treat whole array as one,
        // but we can distinguish different field of an array of struct, e.g. s[1].f1 is different from s[0].f2
        if(const ArrayType* arrTy = SVFUtil::dyn_cast<ArrayType>(gepTy))
        {
            if (!Options::ModelArrays() && arrTy->getElementType()->isPointerTy())
                continue;
            if(!op || (arrTy->getArrayNumElements() <= (u32_t)LLVMUtil::getIntegerValue(op).first))
                continue;
            APOffset idx = (u32_t)LLVMUtil::getIntegerValue(op).first;
            u32_t offset = pag->getFlattenedElemIdx(llvmModuleSet()->getSVFType(arrTy), idx);
            ap.setFldIdx(ap.getConstantStructFldIdx() + offset);
        }
        else if (const StructType *ST = SVFUtil::dyn_cast<StructType>(gepTy))
        {
            assert(op && "non-const offset accessing a struct");
            // guard against negative or out-of-bounds struct indices
            // (e.g. rust hashbrown bucket back-offset: gep { ... }, ptr %p, i64 -1)
            // a negative i64 wraps to a huge uint64_t that overflows u32_t,
            // creating an invalid field index that severs points-to tracking
            uint64_t rawIdx = LLVMUtil::getIntegerValue(op).first;
            if (rawIdx >= ST->getNumElements())
            {
                isConst = false;
                continue;
            }
            APOffset idx = (u32_t)rawIdx;
            u32_t offset = pag->getFlattenedElemIdx(llvmModuleSet()->getSVFType(ST), idx);
            ap.setFldIdx(ap.getConstantStructFldIdx() + offset);
        }
        else if (gepTy->isSingleValueType())
        {
            if (inferredPtrArrayTy)
            {
                if (!op || (inferredPtrArrayTy->getArrayNumElements() <= (u32_t)LLVMUtil::getIntegerValue(op).first))
                    continue;
                APOffset idx = (u32_t)LLVMUtil::getIntegerValue(op).first;
                u32_t offset = pag->getFlattenedElemIdx(llvmModuleSet()->getSVFType(inferredPtrArrayTy), idx);
                ap.setFldIdx(ap.getConstantStructFldIdx() + offset);
                continue;
            }
            // If it's a non-constant offset access
            // If its point-to target is struct or array, it's likely an array accessing (%result = gep %struct.A* %a, i32 %non-const-index)
            // If its point-to target is single value (pointer arithmetic), then it's a variant gep (%result = gep i8* %p, i32 %non-const-index)
            if(!op && gepTy->isPointerTy() && gepOp->getSourceElementType()->isSingleValueType())
            {
                isConst = false;
            }
 
            // The actual index
            //s32_t idx = op->getSExtValue();
 
            // For pointer arithmetic we ignore the byte offset
            // consider using inferFieldIdxFromByteOffset(geopOp,dataLayout,ap,idx)?
            // ap.setFldIdx(ap.getConstantFieldIdx() + inferFieldIdxFromByteOffset(geopOp,idx));
        }
    }
    return isConst;
}
 
void SVFIRBuilder::processCE(const Value* val)
{
    if (const Constant* ref = SVFUtil::dyn_cast<Constant>(val))
    {
        if (const ConstantExpr* gepce = isGepConstantExpr(ref))
        {
            DBOUT(DPAGBuild, outs() << "handle gep constant expression "
                  << LLVMUtil::dumpValue(ref) << "\n");
            const Constant* opnd = gepce->getOperand(0);
            // handle recursive constant express case (gep (bitcast (gep X 1)) 1)
            processCE(opnd);
            auto &GEPOp = llvm::cast<llvm::GEPOperator>(*gepce);
            Type *pType = GEPOp.getSourceElementType();
            AccessPath ap(0, llvmModuleSet()->getSVFType(pType));
            bool constGep = computeGepOffset(gepce, ap);
            // must invoke pag methods here, otherwise it will be a dead recursion cycle
            const Value* cval = getCurrentValue();
            const SVFBasicBlock* cbb = getCurrentBB();
            setCurrentLocation(gepce, (SVFBasicBlock*) nullptr);
            /*
             * The gep edge created are like constexpr (same edge may appear at multiple callsites)
             * so bb/inst of this edge may be rewritten several times, we treat it as global here.
             */
            addGepEdge(llvmModuleSet()->getValueNode(opnd), llvmModuleSet()->getValueNode(gepce), ap, constGep);
            setCurrentLocation(cval, cbb);
        }
        else if (const ConstantExpr* castce = isCastConstantExpr(ref))
        {
            DBOUT(DPAGBuild, outs() << "handle cast constant expression "
                  << LLVMUtil::dumpValue(ref) << "\n");
            const Constant* opnd = castce->getOperand(0);
            processCE(opnd);
            const Value* cval = getCurrentValue();
            const SVFBasicBlock* cbb = getCurrentBB();
            setCurrentLocation(castce, (SVFBasicBlock*) nullptr);
            addCopyEdge(llvmModuleSet()->getValueNode(opnd), llvmModuleSet()->getValueNode(castce), CopyStmt::BITCAST);
            setCurrentLocation(cval, cbb);
        }
        else if (const ConstantExpr* selectce = isSelectConstantExpr(ref))
        {
            DBOUT(DPAGBuild, outs() << "handle select constant expression "
                  << LLVMUtil::dumpValue(ref) << "\n");
            const Constant* src1 = selectce->getOperand(1);
            const Constant* src2 = selectce->getOperand(2);
            processCE(src1);
            processCE(src2);
            const Value* cval = getCurrentValue();
            const SVFBasicBlock* cbb = getCurrentBB();
            setCurrentLocation(selectce, (SVFBasicBlock*) nullptr);
            NodeID cond = llvmModuleSet()->getValueNode(selectce->getOperand(0));
            NodeID nsrc1 = llvmModuleSet()->getValueNode(src1);
            NodeID nsrc2 = llvmModuleSet()->getValueNode(src2);
            NodeID nres = llvmModuleSet()->getValueNode(selectce);
            addSelectStmt(nres,nsrc1, nsrc2, cond);
            setCurrentLocation(cval, cbb);
        }
        // if we meet a int2ptr, then it points-to black hole
        else if (const ConstantExpr* int2Ptrce = isInt2PtrConstantExpr(ref))
        {
            const Constant* opnd = int2Ptrce->getOperand(0);
            processCE(opnd);
            const SVFBasicBlock* cbb = getCurrentBB();
            const Value* cval = getCurrentValue();
            setCurrentLocation(int2Ptrce, (SVFBasicBlock*) nullptr);
            addCopyEdge(llvmModuleSet()->getValueNode(opnd), llvmModuleSet()->getValueNode(int2Ptrce), CopyStmt::INTTOPTR);
            setCurrentLocation(cval, cbb);
        }
        else if (const ConstantExpr* ptr2Intce = isPtr2IntConstantExpr(ref))
        {
            const Constant* opnd = ptr2Intce->getOperand(0);
            processCE(opnd);
            const SVFBasicBlock* cbb = getCurrentBB();
            const Value* cval = getCurrentValue();
            setCurrentLocation(ptr2Intce, (SVFBasicBlock*) nullptr);
            addCopyEdge(llvmModuleSet()->getValueNode(opnd), llvmModuleSet()->getValueNode(ptr2Intce), CopyStmt::PTRTOINT);
            setCurrentLocation(cval, cbb);
        }
        else if(isTruncConstantExpr(ref) || isCmpConstantExpr(ref))
        {
            // we don't handle trunc and cmp instruction for now
            const Value* cval = getCurrentValue();
            const SVFBasicBlock* cbb = getCurrentBB();
            setCurrentLocation(ref, (SVFBasicBlock*) nullptr);
            NodeID dst = llvmModuleSet()->getValueNode(ref);
            addBlackHoleAddrEdge(dst);
            setCurrentLocation(cval, cbb);
        }
        else if (isBinaryConstantExpr(ref))
        {
            // we don't handle binary constant expression like add(x,y) now
            const Value* cval = getCurrentValue();
            const SVFBasicBlock* cbb = getCurrentBB();
            setCurrentLocation(ref, (SVFBasicBlock*) nullptr);
            NodeID dst = llvmModuleSet()->getValueNode(ref);
            addBlackHoleAddrEdge(dst);
            setCurrentLocation(cval, cbb);
        }
        else if (isUnaryConstantExpr(ref))
        {
            // we don't handle unary constant expression like fneg(x) now
            const Value* cval = getCurrentValue();
            const SVFBasicBlock* cbb = getCurrentBB();
            setCurrentLocation(ref, (SVFBasicBlock*) nullptr);
            NodeID dst = llvmModuleSet()->getValueNode(ref);
            addBlackHoleAddrEdge(dst);
            setCurrentLocation(cval, cbb);
        }
        else if (SVFUtil::isa<ConstantAggregate>(ref))
        {
            // we don't handle constant aggregate like constant vectors
        }
        else if (SVFUtil::isa<BlockAddress>(ref))
        {
            // blockaddress instruction (e.g. i8* blockaddress(@run_vm, %182))
            // is treated as constant data object for now, see LLVMUtil.h:397, SymbolTableInfo.cpp:674 and SVFIRBuilder.cpp:183-194
            const Value* cval = getCurrentValue();
            const SVFBasicBlock* cbb = getCurrentBB();
            setCurrentLocation(ref, (SVFBasicBlock*) nullptr);
            NodeID dst = llvmModuleSet()->getValueNode(ref);
            addAddrEdge(pag->getConstantNode(), dst);
            setCurrentLocation(cval, cbb);
        }
        else
        {
            if(SVFUtil::isa<ConstantExpr>(val))
                assert(false && "we don't handle all other constant expression for now!");
        }
    }
}
NodeID SVFIRBuilder::getGlobalVarField(const GlobalVariable *gvar, u32_t offset, SVFType* tpy)
{
 
    // if the global variable do not have any field needs to be initialized
    if (offset == 0 && gvar->getInitializer()->getType()->isSingleValueType())
    {
        return getValueNode(gvar);
    }
    else
    {
        return getGepValVar(gvar, AccessPath(offset), tpy);
    }
}
 
/*For global variable initialization
 * Give a simple global variable
 * int x = 10;     // store 10 x  (constant, non pointer)                                      |
 * int *y = &x;    // store x y   (pointer type)
 * Given a struct
 * struct Z { int s; int *t;};
 * Global initialization:
 * struct Z z = {10,&x}; // store x z.t  (struct type)
 * struct Z *m = &z;       // store z m  (pointer type)
 * struct Z n = {10,&z.s}; // store z.s n ,  &z.s constant expression (constant expression)
 */
void SVFIRBuilder::InitialGlobal(const GlobalVariable *gvar, Constant *C,
                                 u32_t offset)
{
    DBOUT(DPAGBuild, outs() << "global " << LLVMUtil::dumpValue(gvar)
          << " constant initializer: "
          << LLVMUtil::dumpValue(C) << "\n");
    if (C->getType()->isSingleValueType())
    {
        NodeID src = getValueNode(C);
        // get the field value if it is available, otherwise we create a dummy field node.
        setCurrentLocation(gvar, (SVFBasicBlock*) nullptr);
        NodeID field = getGlobalVarField(gvar, offset, llvmModuleSet()->getSVFType(C->getType()));
 
        if (SVFUtil::isa<GlobalVariable, Function>(C))
        {
            setCurrentLocation(C, (SVFBasicBlock*) nullptr);
            addStoreEdge(src, field);
        }
        else if (SVFUtil::isa<ConstantExpr>(C))
        {
            // add gep edge of C1 itself is a constant expression
            processCE(C);
            setCurrentLocation(C, (SVFBasicBlock*) nullptr);
            addStoreEdge(src, field);
        }
        else if (SVFUtil::isa<BlockAddress>(C))
        {
            // blockaddress instruction (e.g. i8* blockaddress(@run_vm, %182))
            // is treated as constant data object for now, see LLVMUtil.h:397, SymbolTableInfo.cpp:674 and SVFIRBuilder.cpp:183-194
            processCE(C);
            setCurrentLocation(C, (SVFBasicBlock*) nullptr);
            addAddrEdge(pag->getConstantNode(), src);
        }
        else
        {
            setCurrentLocation(C, (SVFBasicBlock*) nullptr);
            addStoreEdge(src, field);
            if (C->getType()->isPtrOrPtrVectorTy() && src != pag->getNullPtr())
                addCopyEdge(pag->getNullPtr(), src, CopyStmt::COPYVAL);
        }
    }
    else if (SVFUtil::isa<ConstantArray, ConstantStruct>(C))
    {
        if(cppUtil::isValVtbl(gvar) && !Options::VtableInSVFIR())
            return;
        for (u32_t i = 0, e = C->getNumOperands(); i != e; i++)
        {
            u32_t off = pag->getFlattenedElemIdx(llvmModuleSet()->getSVFType(C->getType()), i);
            InitialGlobal(gvar, SVFUtil::cast<Constant>(C->getOperand(i)), offset + off);
        }
    }
    else if(ConstantData* data = SVFUtil::dyn_cast<ConstantData>(C))
    {
        if(Options::ModelConsts())
        {
            if(ConstantDataSequential* seq = SVFUtil::dyn_cast<ConstantDataSequential>(data))
            {
                for(u32_t i = 0; i < seq->getNumElements(); i++)
                {
                    u32_t off = pag->getFlattenedElemIdx(llvmModuleSet()->getSVFType(C->getType()), i);
                    Constant* ct = seq->getElementAsConstant(i);
                    InitialGlobal(gvar, ct, offset + off);
                }
            }
            else
            {
                assert((SVFUtil::isa<ConstantAggregateZero, UndefValue>(data)) && "Single value type data should have been handled!");
            }
        }
    }
    else
    {
        //TODO:assert(SVFUtil::isa<ConstantVector>(C),"what else do we have");
    }
}
 
void SVFIRBuilder::visitGlobal()
{
 
    for (Module &M : llvmModuleSet()->getLLVMModules())
    {
        for (Module::global_iterator I = M.global_begin(), E = M.global_end(); I != E; ++I)
        {
            GlobalVariable *gvar = &*I;
            NodeID idx = getValueNode(gvar);
            NodeID obj = getObjectNode(gvar);
 
            setCurrentLocation(gvar, (SVFBasicBlock*) nullptr);
            addAddrEdge(obj, idx);
 
            if (gvar->hasInitializer())
            {
                Constant *C = gvar->getInitializer();
                DBOUT(DPAGBuild, outs() << "add global var node "
                      << LLVMUtil::dumpValue(gvar) << "\n");
                InitialGlobal(gvar, C, 0);
            }
        }
 
 
        for (Module::const_iterator I = M.begin(), E = M.end(); I != E; ++I)
        {
            const Function* fun = &*I;
            NodeID idx = getValueNode(fun);
            NodeID obj = getObjectNode(fun);
 
            DBOUT(DPAGBuild, outs() << "add global function node " << fun->getName().str() << "\n");
            setCurrentLocation(fun, (SVFBasicBlock*) nullptr);
            addAddrEdge(obj, idx);
        }
 
        // Handle global aliases (due to linkage of multiple bc files), e.g., @x = internal alias @y. We need to add a copy from y to x.
        for (Module::alias_iterator I = M.alias_begin(), E = M.alias_end(); I != E; I++)
        {
            const GlobalAlias* alias = &*I;
            NodeID dst = llvmModuleSet()->getValueNode(alias);
            NodeID src = llvmModuleSet()->getValueNode(alias->getAliasee());
            processCE(alias->getAliasee());
            setCurrentLocation(alias, (SVFBasicBlock*) nullptr);
            addCopyEdge(src, dst, CopyStmt::COPYVAL);
        }
    }
}
 
void SVFIRBuilder::visitAllocaInst(AllocaInst &inst)
{
 
    // AllocaInst should always be a pointer type
    assert(SVFUtil::isa<PointerType>(inst.getType()));
 
    DBOUT(DPAGBuild,
          outs() << "process alloca " << LLVMUtil::dumpValue(&inst) << "\n");
    NodeID dst = getValueNode(&inst);
 
    NodeID src = getObjectNode(&inst);
 
    addAddrWithStackArraySz(src, dst, inst);
 
}
 
void SVFIRBuilder::visitPHINode(PHINode &inst)
{
 
    DBOUT(DPAGBuild,
          outs() << "process phi " << LLVMUtil::dumpValue(&inst) << "\n");
 
    NodeID dst = getValueNode(&inst);
 
    for (u32_t i = 0; i < inst.getNumIncomingValues(); ++i)
    {
        const Value* val = inst.getIncomingValue(i);
        const Instruction* incomingInst = SVFUtil::dyn_cast<Instruction>(val);
        bool matched = (incomingInst == nullptr ||
                        incomingInst->getFunction() == inst.getFunction());
        (void) matched; // Suppress warning of unused variable under release build
        assert(matched && "incomingInst's Function incorrect");
        const Instruction* predInst = &inst.getIncomingBlock(i)->back();
        const ICFGNode* icfgNode = llvmModuleSet()->getICFGNode(predInst);
        NodeID src = getValueNode(val);
        addPhiStmt(dst,src,icfgNode);
    }
}
 
/*
 * Visit load instructions
 */
void SVFIRBuilder::visitLoadInst(LoadInst &inst)
{
    DBOUT(DPAGBuild,
          outs() << "process load " << LLVMUtil::dumpValue(&inst) << "\n");
 
    NodeID dst = getValueNode(&inst);
 
    NodeID src = getValueNode(inst.getPointerOperand());
    const Type* loadedTy = inst.getType();
    if (NodeID fieldZero = getDirectAccessFieldZeroValVar(inst.getPointerOperand(), loadedTy))
        src = fieldZero;
 
    addLoadEdge(src, dst);
}
 
void SVFIRBuilder::visitStoreInst(StoreInst &inst)
{
    // StoreInst itself should always not be a pointer type
    assert(!SVFUtil::isa<PointerType>(inst.getType()));
 
    DBOUT(DPAGBuild,
          outs() << "process store " << LLVMUtil::dumpValue(&inst) << "\n");
 
    NodeID dst = getValueNode(inst.getPointerOperand());
    const Type* storedTy = inst.getValueOperand()->getType();
    if (NodeID fieldZero = getDirectAccessFieldZeroValVar(inst.getPointerOperand(), storedTy))
        dst = fieldZero;
 
    NodeID src = getValueNode(inst.getValueOperand());
 
    addStoreEdge(src, dst);
 
}
 
void SVFIRBuilder::visitGetElementPtrInst(GetElementPtrInst &inst)
{
 
    NodeID dst = getValueNode(&inst);
    // GetElementPtrInst should always be a pointer or a vector contains pointers
    // for now we don't handle vector type here
    if(SVFUtil::isa<VectorType>(inst.getType()))
    {
        addBlackHoleAddrEdge(dst);
        return;
    }
 
    assert(SVFUtil::isa<PointerType>(inst.getType()));
 
    DBOUT(DPAGBuild,
          outs() << "process gep " << LLVMUtil::dumpValue(&inst) << "\n");
 
    NodeID src = getValueNode(inst.getPointerOperand());
 
    AccessPath ap(0, llvmModuleSet()->getSVFType(inst.getSourceElementType()));
    bool constGep = computeGepOffset(&inst, ap);
    if (constGep && ap.getConstantStructFldIdx() == 0 && !Options::ModelArrays())
    {
        const Type* baseObjType =
            LLVMModuleSet::getLLVMModuleSet()->getTypeInference()->inferObjType(inst.getPointerOperand());
        if (const auto* arrTy = SVFUtil::dyn_cast<ArrayType>(baseObjType))
        {
            if (arrTy->getElementType()->isPointerTy())
            {
                addCopyEdge(src, dst, CopyStmt::COPYVAL);
                return;
            }
        }
    }
    addGepEdge(src, dst, ap, constGep);
}
 
/*
 * Visit cast instructions
 */
void SVFIRBuilder::visitCastInst(CastInst &inst)
{
 
    DBOUT(DPAGBuild,
          outs() << "process cast " << LLVMUtil::dumpValue(&inst) << "\n");
    NodeID dst = getValueNode(&inst);
 
    const Value* opnd = inst.getOperand(0);
    NodeID src = getValueNode(opnd);
    addCopyEdge(src, dst, getCopyKind(&inst));
}
 
void SVFIRBuilder::visitBinaryOperator(BinaryOperator &inst)
{
    NodeID dst = getValueNode(&inst);
    assert(inst.getNumOperands() == 2 && "not two operands for BinaryOperator?");
    Value* op1 = inst.getOperand(0);
    NodeID op1Node = getValueNode(op1);
    Value* op2 = inst.getOperand(1);
    NodeID op2Node = getValueNode(op2);
    u32_t opcode = inst.getOpcode();
    addBinaryOPEdge(op1Node, op2Node, dst, opcode);
}
 
void SVFIRBuilder::visitUnaryOperator(UnaryOperator &inst)
{
    NodeID dst = getValueNode(&inst);
    assert(inst.getNumOperands() == 1 && "not one operand for Unary instruction?");
    Value* opnd = inst.getOperand(0);
    NodeID src = getValueNode(opnd);
    u32_t opcode = inst.getOpcode();
    addUnaryOPEdge(src, dst, opcode);
}
 
void SVFIRBuilder::visitCmpInst(CmpInst &inst)
{
    NodeID dst = getValueNode(&inst);
    assert(inst.getNumOperands() == 2 && "not two operands for compare instruction?");
    Value* op1 = inst.getOperand(0);
    NodeID op1Node = getValueNode(op1);
    Value* op2 = inst.getOperand(1);
    NodeID op2Node = getValueNode(op2);
    u32_t predicate = inst.getPredicate();
    addCmpEdge(op1Node, op2Node, dst, predicate);
}
 
 
void SVFIRBuilder::visitSelectInst(SelectInst &inst)
{
 
    DBOUT(DPAGBuild,
          outs() << "process select " << LLVMUtil::dumpValue(&inst) << "\n");
 
    NodeID dst = getValueNode(&inst);
    NodeID src1 = getValueNode(inst.getTrueValue());
    NodeID src2 = getValueNode(inst.getFalseValue());
    NodeID cond = getValueNode(inst.getCondition());
    addSelectStmt(dst,src1,src2, cond);
}
 
void SVFIRBuilder::visitCallInst(CallInst &i)
{
    visitCallSite(&i);
}
 
void SVFIRBuilder::visitInvokeInst(InvokeInst &i)
{
    visitCallSite(&i);
}
 
void SVFIRBuilder::visitCallBrInst(CallBrInst &i)
{
    visitCallSite(&i);
}
 
/*
 * Visit callsites
 */
void SVFIRBuilder::visitCallSite(CallBase* cs)
{
 
    // skip llvm intrinsics
    if(isIntrinsicInst(cs))
        return;
 
    DBOUT(DPAGBuild,
          outs() << "process callsite " << LLVMUtil::dumpValue(cs) << "\n");
 
    CallICFGNode* callBlockNode = llvmModuleSet()->getCallICFGNode(cs);
    RetICFGNode* retBlockNode = llvmModuleSet()->getRetICFGNode(cs);
 
    pag->addCallSite(callBlockNode);
 
    for (u32_t i = 0; i < cs->arg_size(); i++)
        pag->addCallSiteArgs(
            callBlockNode,
            pag->getValVar(getValueNode(cs->getArgOperand(i))));
 
    if(!cs->getType()->isVoidTy())
        pag->addCallSiteRets(retBlockNode,pag->getValVar(getValueNode(cs)));
 
    if (const auto* call = SVFUtil::dyn_cast<CallInst>(cs))
        addAggregateCallFields(call);
 
    if (callBlockNode->isVirtualCall())
    {
        const Value* value = cppUtil::getVCallVtblPtr(cs);
        callBlockNode->setVtablePtr(pag->getGNode(getValueNode(value)));
    }
    if (const Function *callee = LLVMUtil::getCallee(cs))
    {
        if (LLVMUtil::isExtCall(callee))
        {
            handleExtCall(cs, callee);
        }
        else
        {
            handleDirectCall(cs, callee);
        }
    }
    else
    {
        //If the callee was not identified as a function (null F), this is indirect.
        handleIndCall(cs);
    }
}
 
void SVFIRBuilder::visitReturnInst(ReturnInst &inst)
{
 
    // ReturnInst itself should always not be a pointer type
    assert(!SVFUtil::isa<PointerType>(inst.getType()));
 
    DBOUT(DPAGBuild,
          outs() << "process return " << LLVMUtil::dumpValue(&inst) << "\n");
 
    addAggregateReturnStores(inst);
 
    if(Value* src = inst.getReturnValue())
    {
        const FunObjVar *F = llvmModuleSet()->getFunObjVar(inst.getParent()->getParent());
 
        NodeID rnF = getReturnNode(F);
        NodeID vnS = getValueNode(src);
        const ICFGNode* icfgNode = llvmModuleSet()->getICFGNode(&inst);
        //vnS may be null if src is a null ptr
        addPhiStmt(rnF,vnS,icfgNode);
    }
}
 
 
static const Type* getAggregateFieldType(const Type* type,
        const std::vector<unsigned>& indices)
{
    for (unsigned index : indices)
    {
        if (const auto* structure = SVFUtil::dyn_cast<StructType>(type))
        {
            if (index >= structure->getNumElements())
                return nullptr;
            type = structure->getElementType(index);
        }
        else if (const auto* array = SVFUtil::dyn_cast<ArrayType>(type))
        {
            if (index >= array->getNumElements())
                return nullptr;
            type = array->getElementType();
        }
        else if (const auto* vector = SVFUtil::dyn_cast<llvm::FixedVectorType>(type))
        {
            if (index >= vector->getNumElements())
                return nullptr;
            type = vector->getElementType();
        }
        else
            return nullptr;
    }
    return type;
}
 
bool SVFIRBuilder::getAggregateFieldOperands(const AggregateFieldKey& field,
        std::vector<AggregateFieldKey>& operands)
{
    const Value* value = field.first;
    const AggregateField& path = field.second;
    if (path.empty())
        return value->getType()->isPointerTy() && !SVFUtil::isa<ConstantExpr>(value) &&
               !SVFUtil::isa<UndefValue>(value) && llvmModuleSet()->hasValueNode(value);
    if (const auto* insert = SVFUtil::dyn_cast<InsertValueInst>(value))
    {
        const auto insertedPath = insert->getIndices();
        const size_t commonLength = std::min(insertedPath.size(), path.size());
        if (!std::equal(insertedPath.begin(), insertedPath.begin() + commonLength, path.begin()))
            operands.emplace_back(insert->getAggregateOperand(), path);
        else if (insertedPath.size() <= path.size())
            operands.emplace_back(insert->getInsertedValueOperand(),
                                  AggregateField(path.begin() + insertedPath.size(), path.end()));
        else
            return false;
    }
    else if (const auto* extract = SVFUtil::dyn_cast<ExtractValueInst>(value))
    {
        AggregateField outer(extract->idx_begin(), extract->idx_end());
        outer.insert(outer.end(), path.begin(), path.end());
        operands.emplace_back(extract->getAggregateOperand(), std::move(outer));
    }
    else if (const auto* phi = SVFUtil::dyn_cast<PHINode>(value))
    {
        for (const Value* incoming : phi->incoming_values())
            operands.emplace_back(incoming, path);
    }
    else if (const auto* select = SVFUtil::dyn_cast<SelectInst>(value))
    {
        if (!select->getCondition()->getType()->isIntegerTy(1))
            return false;
        operands.emplace_back(select->getTrueValue(), path);
        operands.emplace_back(select->getFalseValue(), path);
    }
    else if (const auto* freeze = SVFUtil::dyn_cast<FreezeInst>(value))
        operands.emplace_back(freeze->getOperand(0), path);
    else if (const auto* insert = SVFUtil::dyn_cast<InsertElementInst>(value))
    {
        const auto* vector = SVFUtil::dyn_cast<llvm::FixedVectorType>(insert->getType());
        const auto* index = SVFUtil::dyn_cast<ConstantInt>(insert->getOperand(2));
        if (!vector || path.size() != 1 || !index ||
                index->getValue().uge(vector->getNumElements()))
            return false;
        if (index->getZExtValue() == path.front())
            operands.emplace_back(insert->getOperand(1), AggregateField{});
        else
            operands.emplace_back(insert->getOperand(0), path);
    }
    else if (const auto* shuffle = SVFUtil::dyn_cast<ShuffleVectorInst>(value))
    {
        const auto* vector = SVFUtil::dyn_cast<llvm::FixedVectorType>(shuffle->getOperand(0)->getType());
        if (!vector || path.size() != 1)
            return false;
        int index = shuffle->getMaskValue(path.front());
        if (index < 0)
            return false;
        unsigned width = vector->getNumElements();
        operands.emplace_back(shuffle->getOperand(static_cast<unsigned>(index) / width),
                              AggregateField{static_cast<unsigned>(index) % width});
    }
    else if (const auto* constant = SVFUtil::dyn_cast<Constant>(value))
    {
        for (unsigned index : path)
        {
            constant = constant->getAggregateElement(index);
            if (!constant)
                return false;
        }
        operands.emplace_back(constant, AggregateField{});
    }
    else
        // Aggregate arguments, calls and loads need their own field interfaces.
        return false;
    return !operands.empty();
}
 
bool SVFIRBuilder::getAggregateFieldNode(const Value* aggregate,
        const AggregateField& indices, NodeID& node)
{
    const AggregateFieldKey root{aggregate, indices};
    Map<AggregateFieldKey, std::vector<AggregateFieldKey>> definitions;
    std::vector<AggregateFieldKey> worklist{root};
    while (!worklist.empty())
    {
        AggregateFieldKey field = std::move(worklist.back());
        worklist.pop_back();
        if (aggregateFieldNodes.count(field) || definitions.count(field))
            continue;
        const Type* type = getAggregateFieldType(field.first->getType(), field.second);
        if (!type || !type->isPointerTy())
            return false;
        auto& operands = definitions[field];
        if (!getAggregateFieldOperands(field, operands))
            return false;
        worklist.insert(worklist.end(), operands.begin(), operands.end());
    }
 
    // Validate the entire dependency graph before changing SVFIR. Allocate every
    // field before wiring definitions, including loop-carried Phi/Select cycles.
    for (const auto& definition : definitions)
    {
        const AggregateFieldKey& field = definition.first;
        NodeID id;
        if (field.second.empty())
            id = getValueNode(field.first);
        else if (SVFUtil::isa<Constant>(field.first))
            id = getValueNode(definition.second.front().first);
        else
        {
            const auto* producer = SVFUtil::cast<Instruction>(field.first);
            const Type* type = getAggregateFieldType(producer->getType(), field.second);
            id = NodeIDAllocator::get()->allocateValueId();
            pag->addValNode(id, llvmModuleSet()->getSVFType(type),
                            llvmModuleSet()->getICFGNode(producer));
            llvmModuleSet()->addToSVFVar2LLVMValueMap(producer, pag->getGNode(id));
        }
        aggregateFieldNodes.emplace(field, id);
    }
 
    const Value* savedValue = curVal;
    const SVFBasicBlock* savedBB = curBB;
    for (const auto& definition : definitions)
    {
        const AggregateFieldKey& field = definition.first;
        if (field.second.empty() || SVFUtil::isa<Constant>(field.first))
            continue;
        const auto* producer = SVFUtil::cast<Instruction>(field.first);
        const auto& operands = definition.second;
        NodeID dst = aggregateFieldNodes.at(field);
        setCurrentLocation(producer, producer->getParent());
        if (const auto* phi = SVFUtil::dyn_cast<PHINode>(producer))
        {
            for (unsigned i = 0; i < operands.size(); ++i)
                addPhiStmt(dst, aggregateFieldNodes.at(operands[i]),
                           llvmModuleSet()->getICFGNode(phi->getIncomingBlock(i)->getTerminator()));
        }
        else if (const auto* select = SVFUtil::dyn_cast<SelectInst>(producer))
            addSelectStmt(dst, aggregateFieldNodes.at(operands[0]),
                          aggregateFieldNodes.at(operands[1]), getValueNode(select->getCondition()));
        else
            addCopyEdge(aggregateFieldNodes.at(operands.front()), dst, CopyStmt::COPYVAL);
    }
    setCurrentLocation(savedValue, savedBB);
    node = aggregateFieldNodes.at(root);
    return true;
}
 
static bool canModelAggregateReturn(const Function* fun)
{
    if (!fun || LLVMUtil::isExtCall(fun) || fun->isVarArg() ||
            fun->doesNotReturn() || !fun->getReturnType()->isAggregateType() ||
            fun->hasAddressTaken())
        return false;
    for (const User* user : fun->users())
    {
        const auto* call = SVFUtil::dyn_cast<CallInst>(user);
        if (!call || call->getCalledFunction() != fun ||
                call->getFunctionType() != fun->getFunctionType())
            return false;
    }
    return true;
}
 
void SVFIRBuilder::initialiseAggregateReturns()
{
    std::vector<AggregateFieldKey> worklist;
    for (Module& module : llvmModuleSet()->getLLVMModules())
        for (const Function& fun : module)
            for (const BasicBlock& bb : fun)
                for (const Instruction& inst : bb)
                {
                    if (const auto* extract = SVFUtil::dyn_cast<ExtractValueInst>(&inst))
                    {
                        if (extract->getType()->isPointerTy())
                            worklist.emplace_back(extract->getAggregateOperand(),
                                                  AggregateField(extract->idx_begin(), extract->idx_end()));
                    }
                    else if (const auto* extract = SVFUtil::dyn_cast<ExtractElementInst>(&inst))
                    {
                        const auto* vector = SVFUtil::dyn_cast<llvm::FixedVectorType>(extract->getVectorOperandType());
                        const auto* index = SVFUtil::dyn_cast<ConstantInt>(extract->getIndexOperand());
                        if (extract->getType()->isPointerTy() && vector && index &&
                                index->getValue().ult(vector->getNumElements()))
                            worklist.emplace_back(extract->getVectorOperand(),
                                                  AggregateField{static_cast<unsigned>(index->getZExtValue())});
                    }
                }
 
    // Discover callee demands without materializing local field definitions.
    // Calls cross into return operands; other producers use the shared grammar.
    Set<AggregateFieldKey> visited;
    while (!worklist.empty())
    {
        AggregateFieldKey field = std::move(worklist.back());
        worklist.pop_back();
        if (!visited.insert(field).second || field.second.empty())
            continue;
        if (const auto* call = SVFUtil::dyn_cast<CallInst>(field.first))
        {
            const Function* callee = call->getCalledFunction();
            if (!canModelAggregateReturn(callee) ||
                    !aggregateReturnParams[callee].emplace(field.second, 0).second)
                continue;
            for (const BasicBlock& bb : *callee)
                if (const auto* ret = SVFUtil::dyn_cast<ReturnInst>(bb.getTerminator()))
                    if (ret->getReturnValue())
                        worklist.emplace_back(ret->getReturnValue(), field.second);
        }
        else
        {
            std::vector<AggregateFieldKey> operands;
            if (getAggregateFieldOperands(field, operands))
                worklist.insert(worklist.end(), operands.begin(), operands.end());
        }
    }
 
    const SVFType* pointerType = llvmModuleSet()->getSVFType(
                                     PointerType::getUnqual(llvmModuleSet()->getContext()));
    const Value* savedValue = curVal;
    const SVFBasicBlock* savedBB = curBB;
    // Serialized points-to sets use NodeIDs. Allocate in function order,
    // independent of pointer-keyed hash table iteration.
    for (const Function* fun : llvmModuleSet()->getFunctionSet())
    {
        auto found = aggregateReturnParams.find(fun);
        if (found == aggregateReturnParams.end())
            continue;
        auto& fields = found->second;
        FunObjVar* svfFun = const_cast<FunObjVar*>(llvmModuleSet()->getFunObjVar(fun));
        const FunEntryICFGNode* entry = pag->getICFG()->getFunEntryICFGNode(svfFun);
        for (auto& field : fields)
        {
            NodeID id = NodeIDAllocator::get()->allocateValueId();
            pag->addArgValNode(id, svfFun->arg_size(), entry, svfFun, pointerType);
            auto* arg = SVFUtil::cast<ArgValVar>(pag->getGNode(id));
            svfFun->addArgument(arg);
            // Like RetValPN, the synthetic parameter uses its function as a
            // diagnostic source; it does not add or replace an LLVM argument.
            llvmModuleSet()->addToSVFVar2LLVMValueMap(fun, arg);
            arg->setName("aggregate_return_" + std::to_string(arg->getArgNo()));
            field.second = id;
        }
        // LLVM use-list order can change on bitcode reload. Order calls by
        // their ICFG IDs so each call receives the same slot IDs on readback.
        std::vector<const CallInst*> calls;
        for (const User* user : fun->users())
            calls.push_back(SVFUtil::cast<CallInst>(user));
        std::sort(calls.begin(), calls.end(), [this](const CallInst* lhs,
                  const CallInst* rhs)
        {
            return llvmModuleSet()->getCallICFGNode(lhs)->getId() <
                   llvmModuleSet()->getCallICFGNode(rhs)->getId();
        });
        // Include calls with unused results to keep actual/formal lists aligned.
        for (const CallInst* call : calls)
        {
            std::vector<const Instruction*> next;
            LLVMUtil::getNextInsts(call, next);
            assert(next.size() == 1 && "ordinary call must have one continuation");
            AggregateCall& model = aggregateCalls[call];
            model.continuation = next.front();
            ICFGNode* callNode = llvmModuleSet()->getCallICFGNode(call);
            ICFGNode* resumeNode = llvmModuleSet()->getICFGNode(model.continuation);
            setCurrentLocation(model.continuation, model.continuation->getParent());
            for (const auto& field : fields)
            {
                // DummyObjVar keeps the static slot nonlocal to the callee in MemSSA.
                // Later extracts read the SSA snapshot, not the reused slot contents.
                NodeID object = pag->addDummyObjNode(pointerType);
                pag->getAllFieldsObjVars(object).set(object);
                pag->getObjTypeInfo(object)->setNumOfElements(1);
                pag->getObjTypeInfo(object)->setByteSizeOfObj(pointerType->getByteSize());
                NodeID address = pag->addDummyValNode(NodeIDAllocator::get()->allocateValueId(), callNode);
                NodeID value = pag->addDummyValNode(NodeIDAllocator::get()->allocateValueId(), resumeNode);
                model.fields.emplace(field.first, AggregateCallField{object, address, value});
                // Call fields use the same identity as local aggregate fields.
                aggregateFieldNodes.emplace(AggregateFieldKey{call, field.first}, value);
                // Snapshots must precede field statements at the continuation,
                // even when LLVM block order differs from dominance order.
                addLoadEdge(address, value);
            }
        }
    }
    setCurrentLocation(savedValue, savedBB);
}
 
void SVFIRBuilder::addAggregateCallFields(const CallInst* call)
{
    auto found = aggregateCalls.find(call);
    if (found == aggregateCalls.end())
        return;
    const AggregateCall& model = found->second;
    CallICFGNode* callNode = llvmModuleSet()->getCallICFGNode(call);
    const FunObjVar* callee = llvmModuleSet()->getFunObjVar(call->getCalledFunction());
    FunEntryICFGNode* entry = pag->getICFG()->getFunEntryICFGNode(callee);
    const auto& params = aggregateReturnParams.at(call->getCalledFunction());
    for (const auto& field : model.fields)
    {
        const AggregateCallField& nodes = field.second;
        addAddrEdge(nodes.object, nodes.address);
        pag->addCallSiteArgs(callNode, pag->getValVar(nodes.address));
        addCallEdge(nodes.address, params.at(field.first), callNode, entry);
    }
}
 
void SVFIRBuilder::addAggregateReturnStores(ReturnInst& inst)
{
    auto found = aggregateReturnParams.find(inst.getFunction());
    if (found == aggregateReturnParams.end() || !inst.getReturnValue())
        return;
    // Keep each store on its own return path, before the shared function exit.
    ICFGNode* location = llvmModuleSet()->getICFGNode(&inst);
    for (const auto& field : found->second)
    {
        NodeID value;
        if (!getAggregateFieldNode(inst.getReturnValue(), field.first, value))
        {
            value = pag->addDummyValNode(NodeIDAllocator::get()->allocateValueId(), location);
            addBlackHoleAddrEdge(value);
        }
        addStoreEdge(value, field.second);
    }
}
 
void SVFIRBuilder::visitExtractValueInst(ExtractValueInst &inst)
{
    NodeID dst = getValueNode(&inst);
    NodeID field;
    if (inst.getType()->isPointerTy() &&
            getAggregateFieldNode(inst.getAggregateOperand(),
                                  AggregateField(inst.idx_begin(), inst.idx_end()), field))
        addCopyEdge(field, dst, CopyStmt::COPYVAL);
    else
        addBlackHoleAddrEdge(dst);
}
 
void SVFIRBuilder::visitExtractElementInst(ExtractElementInst &inst)
{
    NodeID dst = getValueNode(&inst);
    NodeID field;
    const auto* vector = SVFUtil::dyn_cast<llvm::FixedVectorType>(inst.getVectorOperandType());
    const auto* index = SVFUtil::dyn_cast<ConstantInt>(inst.getIndexOperand());
    if (inst.getType()->isPointerTy() && vector && index &&
            index->getValue().ult(vector->getNumElements()) &&
            getAggregateFieldNode(inst.getVectorOperand(),
                                  AggregateField{static_cast<unsigned>(index->getZExtValue())}, field))
        addCopyEdge(field, dst, CopyStmt::COPYVAL);
    else
        addBlackHoleAddrEdge(dst);
}
 
void SVFIRBuilder::visitBranchInst(BranchInst &inst)
{
    NodeID brinst = getValueNode(&inst);
    NodeID cond;
    if (inst.isConditional())
        cond = getValueNode(inst.getCondition());
    else
        cond = pag->getNullPtr();
 
    assert(inst.getNumSuccessors() <= 2 && "if/else has more than two branches?");
 
    BranchStmt::SuccAndCondPairVec successors;
    std::vector<const Instruction*> nextInsts;
    LLVMUtil::getNextInsts(&inst, nextInsts);
    u32_t branchID = 0;
    for (const Instruction* succInst : nextInsts)
    {
        assert(branchID <= 1 && "if/else has more than two branches?");
        const ICFGNode* icfgNode = llvmModuleSet()->getICFGNode(succInst);
        successors.push_back(std::make_pair(icfgNode, 1-branchID));
        branchID++;
    }
    addBranchStmt(brinst, cond, successors);
    if (inst.isConditional())
    {
        for (auto& edge : llvmModuleSet()->getICFGNode(&inst)->getOutEdges())
        {
            if (IntraCFGEdge* intraEdge = SVFUtil::dyn_cast<IntraCFGEdge>(edge))
            {
                intraEdge->setConditionVar(pag->getGNode(cond));
            }
        }
    }
}
 
 
 
void SVFIRBuilder::visitSwitchInst(SwitchInst &inst)
{
    NodeID brinst = getValueNode(&inst);
    NodeID cond = getValueNode(inst.getCondition());
 
    BranchStmt::SuccAndCondPairVec successors;
    std::vector<const Instruction*> nextInsts;
    LLVMUtil::getNextInsts(&inst, nextInsts);
    for (const Instruction* succInst : nextInsts)
    {
        const ConstantInt* condVal = inst.findCaseDest(const_cast<BasicBlock*>(succInst->getParent()));
        s64_t val = -1;
        if (condVal && condVal->getBitWidth() <= 64)
            val = (u32_t)LLVMUtil::getIntegerValue(condVal).first;
        const ICFGNode* icfgNode = llvmModuleSet()->getICFGNode(succInst);
        successors.push_back(std::make_pair(icfgNode, val));
    }
    addBranchStmt(brinst, cond, successors);
    for (auto& edge : llvmModuleSet()->getICFGNode(&inst)->getOutEdges())
    {
        if (IntraCFGEdge* intraEdge = SVFUtil::dyn_cast<IntraCFGEdge>(edge))
        {
            intraEdge->setConditionVar(pag->getGNode(cond));
        }
    }
}
 
 
void SVFIRBuilder::visitVAArgInst(VAArgInst &inst)
{
    NodeID dst = getValueNode(&inst);
    Value* opnd = inst.getPointerOperand();
    NodeID src = getValueNode(opnd);
    addCopyEdge(src, dst, CopyStmt::COPYVAL);
}
 
void SVFIRBuilder::visitFreezeInst(FreezeInst &inst)
{
    NodeID dst = getValueNode(&inst);
    for (u32_t i = 0; i < inst.getNumOperands(); i++)
    {
        Value* opnd = inst.getOperand(i);
        NodeID src = getValueNode(opnd);
        addCopyEdge(src, dst, CopyStmt::COPYVAL);
    }
}
 
 
void SVFIRBuilder::handleDirectCall(CallBase* cs, const Function *F)
{
 
    assert(F);
    CallICFGNode* callICFGNode = llvmModuleSet()->getCallICFGNode(cs);
    const FunObjVar* svffun = llvmModuleSet()->getFunObjVar(F);
    DBOUT(DPAGBuild, outs() << "handle direct call " << LLVMUtil::dumpValue(cs)
          << " callee " << F->getName().str() << "\n");
 
    //Only handle the ret.val. if it's used as a ptr.
    NodeID dstrec = getValueNode(cs);
    //Does it actually return a ptr?
    if (!cs->getType()->isVoidTy())
    {
        NodeID srcret = getReturnNode(svffun);
        FunExitICFGNode* exitICFGNode = pag->getICFG()->getFunExitICFGNode(svffun);
        addRetEdge(srcret, dstrec,callICFGNode, exitICFGNode);
    }
    //Iterators for the actual and formal parameters
    u32_t itA = 0, ieA = cs->arg_size();
    Function::const_arg_iterator itF = F->arg_begin(), ieF = F->arg_end();
    //Go through the fixed parameters.
    DBOUT(DPAGBuild, outs() << "      args:");
    for (; itF != ieF; ++itA, ++itF)
    {
        //Some programs (e.g. Linux kernel) leave unneeded parameters empty.
        if (itA == ieA)
        {
            DBOUT(DPAGBuild, outs() << " !! not enough args\n");
            break;
        }
        const Value* AA = cs->getArgOperand(itA), *FA = &*itF; //current actual/formal arg
 
        DBOUT(DPAGBuild, outs() << "process actual parm "
              << LLVMUtil::dumpValue(AA) << "\n");
 
        NodeID dstFA = getValueNode(FA);
        NodeID srcAA = getValueNode(AA);
        FunEntryICFGNode* entry = pag->getICFG()->getFunEntryICFGNode(svffun);
        addCallEdge(srcAA, dstFA, callICFGNode, entry);
    }
    //Any remaining actual args must be varargs.
    if (F->isVarArg())
    {
        NodeID vaF = getVarargNode(svffun);
        DBOUT(DPAGBuild, outs() << "\n      varargs:");
        for (; itA != ieA; ++itA)
        {
            const Value* AA = cs->getArgOperand(itA);
            NodeID vnAA = getValueNode(AA);
            FunEntryICFGNode* entry = pag->getICFG()->getFunEntryICFGNode(svffun);
            addCallEdge(vnAA,vaF, callICFGNode,entry);
        }
    }
    if(itA != ieA)
    {
        writeWrnMsg("too many args to non-vararg func.");
        writeWrnMsg("(" + callICFGNode->getSourceLoc() + ")");
 
    }
}
 
const Value* SVFIRBuilder::getBaseValueForExtArg(const Value* V)
{
    const Value*  value = stripAllCasts(V);
    assert(value && "null ptr?");
    auto getGlobalFieldFromByteOffset =
        [this](const GlobalVariable* glob, int64_t byteOffset) -> const Value*
    {
        if (!glob || !glob->hasInitializer())
            return nullptr;
 
        auto* initializer = SVFUtil::dyn_cast<ConstantStruct>(glob->getInitializer());
        auto* structType = SVFUtil::dyn_cast<StructType>(glob->getValueType());
        if (!initializer || !structType)
            return nullptr;
 
        DataLayout* dataLayout = getDataLayout(llvmModuleSet()->getMainLLVMModule());
        const StructLayout* layout =
        dataLayout->getStructLayout(const_cast<StructType*>(structType));
        for (u32_t fieldIdx = 0; fieldIdx < initializer->getNumOperands(); ++fieldIdx)
        {
            if (layout->getElementOffset(fieldIdx) != static_cast<uint64_t>(byteOffset))
                continue;
            if (auto* ptrValue =
                    SVFUtil::dyn_cast<llvm::GlobalVariable>(initializer->getOperand(fieldIdx)))
                return ptrValue;
            return nullptr;
        }
        return nullptr;
    };
 
    if(const GetElementPtrInst* gep = SVFUtil::dyn_cast<GetElementPtrInst>(value))
    {
        APOffset totalidx = 0;
        for (bridge_gep_iterator gi = bridge_gep_begin(gep), ge = bridge_gep_end(gep); gi != ge; ++gi)
        {
            if(const ConstantInt* op = SVFUtil::dyn_cast<ConstantInt>(gi.getOperand()))
                totalidx += LLVMUtil::getIntegerValue(op).first;
        }
        if(totalidx == 0 && !SVFUtil::isa<StructType>(value->getType()))
            value = gep->getPointerOperand();
    }
    else if (const LoadInst* load = SVFUtil::dyn_cast<LoadInst>(value))
    {
        const Value* loadP = load->getPointerOperand();
        if (const GetElementPtrInst* gep = SVFUtil::dyn_cast<GetElementPtrInst>(loadP))
        {
            DataLayout* dataLayout = getDataLayout(llvmModuleSet()->getMainLLVMModule());
            llvm::APInt byteOffset(dataLayout->getIndexSizeInBits(gep->getPointerAddressSpace()), 0, true);
            const bool hasByteOffset = dataLayout && gep->accumulateConstantOffset(*dataLayout, byteOffset);
 
            const Value * pointer_operand = gep->getPointerOperand();
            if (auto *glob = SVFUtil::dyn_cast<GlobalVariable>(pointer_operand))
            {
                if (hasByteOffset)
                {
                    if (const Value* ptrValue = getGlobalFieldFromByteOffset(glob, byteOffset.getSExtValue()))
                        return ptrValue;
                }
            }
            else if (hasByteOffset && !byteOffset.isNegative() &&
                     SVFUtil::isa<AllocaInst>(pointer_operand) && load->getType()->isPointerTy())
            {
                const u64_t offset = byteOffset.getZExtValue();
                const u64_t accessBytes = dataLayout->getPointerSize(gep->getPointerAddressSpace());
 
                auto isCoveredByMemcpy = [offset, accessBytes](const CallBase* cs) -> bool
                {
                    if (cs->arg_size() < 3)
                        return false;
 
                    const auto* copySize = SVFUtil::dyn_cast<ConstantInt>(cs->getArgOperand(2));
                    if (!copySize)
                    {
                        return false;
                    }
 
                    const u64_t copyBytes = copySize->getZExtValue();
                    return copyBytes >= accessBytes && copyBytes - accessBytes >= offset;
                };
 
                auto hasInterveningWrite = [load](const Instruction* from) -> bool
                {
                    if (from->getParent() != load->getParent() || !from->comesBefore(load))
                        return true;
 
                    auto it = from->getIterator();
                    const auto end = load->getIterator();
                    while (++it != end)
                    {
                        if (it->mayWriteToMemory())
                            return true;
                    }
                    return false;
                };
 
                for (const auto& use : pointer_operand->users())
                {
                    const auto* cs = SVFUtil::dyn_cast<CallBase>(use);
                    if (!cs || cs->getParent() != load->getParent() ||
                            cs->arg_size() < 1 ||
                            stripAllCasts(cs->getArgOperand(0)) != pointer_operand)
                        continue;
 
                    const Function* calledFun = cs->getCalledFunction();
                    if (!LLVMUtil::isMemcpyExtFun(calledFun) || !isCoveredByMemcpy(cs) ||
                            hasInterveningWrite(cs))
                        continue;
 
                    const Value* copiedFrom = getBaseValueForExtArg(cs->getArgOperand(1));
                    if (const auto* copiedGlob = SVFUtil::dyn_cast<GlobalVariable>(copiedFrom))
                    {
                        if (const Value* ptrValue =
                                    getGlobalFieldFromByteOffset(copiedGlob, byteOffset.getSExtValue()))
                            return ptrValue;
                    }
                }
            }
        }
    }
 
    return value;
}
 
void SVFIRBuilder::handleIndCall(CallBase* cs)
{
    const CallICFGNode* cbn = llvmModuleSet()->getCallICFGNode(cs);
    NodeID indFunPtrId = llvmModuleSet()->getValueNode(cs->getCalledOperand());
    const_cast<CallICFGNode*>(cbn)->setIndFunPtr(pag->getGNode(indFunPtrId));
    pag->addIndirectCallsites(cbn,indFunPtrId);
}
 
void SVFIRBuilder::updateCallGraph(CallGraph* callgraph)
{
    CallGraph::CallEdgeMap::const_iterator iter = callgraph->getIndCallMap().begin();
    CallGraph::CallEdgeMap::const_iterator eiter = callgraph->getIndCallMap().end();
    for (; iter != eiter; iter++)
    {
        const CallICFGNode* callBlock = iter->first;
        const CallBase* callbase = SVFUtil::cast<CallBase>(llvmModuleSet()->getLLVMValue(callBlock));
        assert(callBlock->isIndirectCall() && "this is not an indirect call?");
        const CallGraph::FunctionSet& functions = iter->second;
        for (CallGraph::FunctionSet::const_iterator func_iter = functions.begin(); func_iter != functions.end(); func_iter++)
        {
            const Function* callee = SVFUtil::cast<Function>(llvmModuleSet()->getLLVMValue(*func_iter));
 
            if (isExtCall(*func_iter))
            {
                setCurrentLocation(callee, callee->empty() ? nullptr : &callee->getEntryBlock());
                handleExtCall(callbase, callee);
            }
            else
            {
                setCurrentLocation(llvmModuleSet()->getLLVMValue(callBlock), callBlock->getBB());
                handleDirectCall(const_cast<CallBase*>(callbase), callee);
            }
        }
    }
 
    // dump SVFIR
    if (Options::PAGDotGraph())
        pag->dump("svfir_final");
}
 
/*
 * TODO: more sanity checks might be needed here
 */
void SVFIRBuilder::sanityCheck()
{
    for (SVFIR::iterator nIter = pag->begin(); nIter != pag->end(); ++nIter)
    {
        (void) pag->getGNode(nIter->first);
        //TODO::
        // (1)  every source(root) node of a pag tree should be object node
        //       if a node has no incoming edge, but has outgoing edges
        //       then it has to be an object node.
        // (2)  make sure every variable should be initialized
        //      otherwise it causes the a null pointer, the aliasing relation may not be captured
        //      when loading a pointer value should make sure
        //      some value has been store into this pointer before
        //      q = load p, some value should stored into p first like store w p;
        // (3)  make sure PAGNode should not have a const expr value (pointer should have unique def)
        // (4)  look closely into addComplexConsForExt, make sure program locations(e.g.,inst bb)
        //      are set correctly for dummy gepval node
        // (5)  reduce unnecessary copy edge (const casts) and ensure correctness.
    }
}
 
 
NodeID SVFIRBuilder::getGepValVar(const Value* val, const AccessPath& ap, const SVFType* elementType)
{
    NodeID base = getValueNode(val);
    NodeID gepval = pag->getGepValVar(llvmModuleSet()->getValueNode(curVal), base, ap);
    if (gepval==UINT_MAX)
    {
        assert(((int) UINT_MAX)==-1 && "maximum limit of unsigned int is not -1?");
        /*
         * getGepValVar can only be called from two places:
         * 1. SVFIRBuilder::addComplexConsForExt to handle external calls
         * 2. SVFIRBuilder::getGlobalVarField to initialize global variable
         * so curVal can only be
         * 1. Instruction
         * 2. GlobalVariable
         */
        assert(
            (SVFUtil::isa<Instruction>(curVal) || SVFUtil::isa<GlobalVariable>(curVal)) && "curVal not an instruction or a globalvariable?");
 
        // We assume every GepValNode and its GepEdge to the baseNode are unique across the whole program
        // We preserve the current BB information to restore it after creating the gepNode
        const Value* cval = getCurrentValue();
        const SVFBasicBlock* cbb = getCurrentBB();
        setCurrentLocation(curVal, (SVFBasicBlock*) nullptr);
        LLVMModuleSet* llvmmodule = llvmModuleSet();
        const ICFGNode* node = nullptr;
        if (const Instruction* inst = SVFUtil::dyn_cast<Instruction>(curVal))
        {
            if (llvmmodule->hasICFGNode(inst))
            {
                node = llvmmodule->getICFGNode(inst);
            }
        }
        else if (SVFUtil::isa<GlobalVariable>(curVal))
        {
            // GEP on a global variable: the resulting GepValVar belongs to the global ICFG node.
            node = pag->getICFG()->getGlobalICFGNode();
        }
        NodeID gepNode = pag->addGepValNode(llvmModuleSet()->getValueNode(curVal), cast<ValVar>(pag->getGNode(getValueNode(val))), ap,
                                            NodeIDAllocator::get()->allocateValueId(),
                                            llvmmodule->getSVFType(PointerType::getUnqual(llvmmodule->getContext())), node);
        addGepEdge(base, gepNode, ap, true);
        setCurrentLocation(cval, cbb);
        return gepNode;
    }
    else
        return gepval;
}
 
NodeID SVFIRBuilder::getDirectAccessFieldZeroValVar(const Value* ptr, const Type* accessTy)
{
    if (!Options::ModelArrays() || SVFUtil::isa<llvm::GEPOperator>(ptr))
        return 0;
 
    const Type* objTy =
        LLVMModuleSet::getLLVMModuleSet()->getTypeInference()->inferObjType(ptr);
    const ArrayType* arrTy = SVFUtil::dyn_cast<ArrayType>(objTy);
    if (!arrTy || !arrTy->getElementType()->isPointerTy() ||
            arrTy->getElementType() != accessTy)
        return 0;
 
    AccessPath ap(0, llvmModuleSet()->getSVFType(arrTy));
    return getGepValVar(ptr, ap, llvmModuleSet()->getSVFType(accessTy));
}
 
 
/*
 * curVal   <-------->  PAGEdge
 * Instruction          Any Edge
 * Argument             CopyEdge  (SVFIR::addFormalParamBlackHoleAddrEdge)
 * ConstantExpr         CopyEdge  (Int2PtrConstantExpr   CastConstantExpr  SVFIRBuilder::processCE)
 *                      GepEdge   (GepConstantExpr   SVFIRBuilder::processCE)
 * ConstantPointerNull  CopyEdge  (3-->2 NullPtr-->BlkPtr SVFIR::addNullPtrNode)
 *                      AddrEdge  (0-->2 BlkObj-->BlkPtr SVFIR::addNullPtrNode)
 * GlobalVariable       AddrEdge  (SVFIRBuilder::visitGlobal)
 *                      GepEdge   (SVFIRBuilder::getGlobalVarField)
 * Function             AddrEdge  (SVFIRBuilder::visitGlobal)
 * Constant             StoreEdge (SVFIRBuilder::InitialGlobal)
 */
void SVFIRBuilder::setCurrentBBAndValueForPAGEdge(PAGEdge* edge)
{
    if (SVFIR::pagReadFromTXT())
        return;
 
    assert(curVal && "current Val is nullptr?");
    edge->setBB(curBB!=nullptr ? curBB : nullptr);
    edge->setValue(pag->getGNode(llvmModuleSet()->getValueNode(curVal)));
    ICFGNode* icfgNode = pag->getICFG()->getGlobalICFGNode();
    LLVMModuleSet* llvmMS = llvmModuleSet();
    if (const Instruction* curInst = SVFUtil::dyn_cast<Instruction>(curVal))
    {
        const FunObjVar* srcFun = edge->getSrcNode()->getFunction();
        const FunObjVar* dstFun = edge->getDstNode()->getFunction();
        if(srcFun!=nullptr && !SVFUtil::isa<RetPE>(edge) && !SVFUtil::isa<FunValVar>(edge->getSrcNode()) && !SVFUtil::isa<FunObjVar>(edge->getSrcNode()))
        {
            assert(srcFun==llvmMS->getFunObjVar(curInst->getFunction()) && "SrcNode of the PAGEdge not in the same function?");
        }
        if(dstFun!=nullptr && !SVFUtil::isa<CallPE>(edge) && !SVFUtil::isa<RetValPN>(edge->getDstNode()))
        {
            assert(dstFun==llvmMS->getFunObjVar(curInst->getFunction()) && "DstNode of the PAGEdge not in the same function?");
        }
 
        if (!(SVFUtil::isa<GepStmt>(edge) && SVFUtil::isa<GepValVar>(edge->getDstNode())))
            assert(curBB && "instruction does not have a basic block??");
 
        if(SVFUtil::isa<ReturnInst>(curInst) && SVFUtil::isa<PhiStmt>(edge))
        {
            icfgNode = pag->getICFG()->getFunExitICFGNode(llvmMS->getFunObjVar(curInst->getFunction()));
        }
        else if(const CallPE* callPE = SVFUtil::dyn_cast<CallPE>(edge))
        {
            icfgNode = const_cast<FunEntryICFGNode*>(callPE->getFunEntryICFGNode());
        }
        else if(SVFUtil::isa<RetPE>(edge))
        {
            icfgNode = llvmMS->getRetICFGNode(SVFUtil::cast<Instruction>(curInst));
        }
        else
        {
            icfgNode = llvmMS->getICFGNode(SVFUtil::cast<Instruction>(curInst));
        }
    }
    else if (const Argument* arg = SVFUtil::dyn_cast<Argument>(curVal))
    {
        assert(curBB && (curBB->getParent()->getEntryBlock() == curBB));
        icfgNode = pag->getICFG()->getFunEntryICFGNode(
                       llvmModuleSet()->getFunObjVar(SVFUtil::cast<Function>(arg->getParent())));
    }
    else if (SVFUtil::isa<Constant>(curVal) ||
             SVFUtil::isa<Function>(curVal) ||
             SVFUtil::isa<MetadataAsValue>(curVal))
    {
        if (!curBB)
            pag->addGlobalPAGEdge(edge);
        else
        {
            icfgNode = const_cast<ICFGNode*>(curBB->front());
        }
    }
    else
    {
        assert(false && "what else value can we have?");
    }
 
    pag->addToSVFStmtList(icfgNode,edge);
    icfgNode->addSVFStmt(edge);
    if(const CallPE* callPE = SVFUtil::dyn_cast<CallPE>(edge))
    {
        FunEntryICFGNode* entryNode = const_cast<FunEntryICFGNode*>(callPE->getFunEntryICFGNode());
        for(u32_t i = 0; i < callPE->getOpVarNum(); i++)
        {
            CallICFGNode* callNode = const_cast<CallICFGNode*>(callPE->getOpCallICFGNode(i));
            if(ICFGEdge* icfgEdge = pag->getICFG()->hasInterICFGEdge(callNode, entryNode, ICFGEdge::CallCF))
                SVFUtil::cast<CallCFGEdge>(icfgEdge)->addCallPE(callPE);
        }
    }
    else if(const RetPE* retPE = SVFUtil::dyn_cast<RetPE>(edge))
    {
        RetICFGNode* retNode = const_cast<RetICFGNode*>(retPE->getCallSite()->getRetICFGNode());
        FunExitICFGNode* exitNode = const_cast<FunExitICFGNode*>(retPE->getFunExitICFGNode());
        if(ICFGEdge* edge = pag->getICFG()->hasInterICFGEdge(exitNode, retNode, ICFGEdge::RetCF))
            SVFUtil::cast<RetCFGEdge>(edge)->addRetPE(retPE);
    }
}
 
 
AccessPath SVFIRBuilder::getAccessPathFromBaseNode(NodeID nodeId)
{
    SVFVar* node  = pag->getGNode(nodeId);
    SVFStmt::SVFStmtSetTy& geps = node->getIncomingEdges(SVFStmt::Gep);
    if(geps.empty())
        return AccessPath(0);
 
    assert(geps.size()==1 && "one node can only be connected by at most one gep edge!");
    SVFVar::iterator it = geps.begin();
    const GepStmt* gepEdge = SVFUtil::cast<GepStmt>(*it);
    if(gepEdge->isVariantFieldGep())
        return AccessPath(0);
    else
        return gepEdge->getAccessPath();
}