SVF::ICFGBuilder Class Reference

#include <ICFGBuilder.h>

Public Types
typedef std::vector< const Instruction * >	InstVec
typedef Set< const Instruction * >	BBSet
typedef Map< const Instruction *, CallICFGNode * >	CSToCallNodeMapTy
typedef Map< const Instruction *, RetICFGNode * >	CSToRetNodeMapTy
typedef Map< const Instruction *, IntraICFGNode * >	InstToBlockNodeMapTy
typedef Map< const Function *, FunEntryICFGNode * >	FunToFunEntryNodeMapTy
typedef Map< const Function *, FunExitICFGNode * >	FunToFunExitNodeMapTy
typedef FIFOWorkList< const Instruction * >	WorkList

Public Member Functions
	ICFGBuilder ()
ICFG *	build ()

Private Member Functions
LLVMModuleSet *	llvmModuleSet ()
CSToRetNodeMapTy &	csToRetNodeMap ()
CSToCallNodeMapTy &	csToCallNodeMap ()
InstToBlockNodeMapTy &	instToBlockNodeMap ()
FunToFunEntryNodeMapTy &	funToFunEntryNodeMap ()
FunToFunExitNodeMapTy &	funToFunExitNodeMap ()

Private Attributes
ICFG *	icfg
BBSet	visited
void	processFunEntry (const Function *fun, WorkList &worklist)
void	processNoPrecessorBasicBlocks (const Function *fun, WorkList &worklist)
void	processFunBody (WorkList &worklist)
void	processFunExit (const Function *fun)
void	checkICFGNodesVisited (const Function *fun)
void	connectGlobalToProgEntry ()
void	addICFGInterEdges (const Instruction *cs, const Function *callee)
	Create edges between ICFG nodes across functions. More...
ICFGNode *	getICFGNode (const Instruction *inst)
bool	hasICFGNode (const Instruction *inst)
CallICFGNode *	getCallICFGNode (const Instruction *cs)
	get a call node More...
RetICFGNode *	getRetICFGNode (const Instruction *cs)
	get a return node More...
IntraICFGNode *	getIntraICFGNode (const Instruction *inst)
	get a intra node More...
FunEntryICFGNode *	getFunEntryICFGNode (const Function *fun)
	get a function entry node More...
FunExitICFGNode *	getFunExitICFGNode (const Function *fun)
	get a function exit node More...
GlobalICFGNode *	getGlobalICFGNode () const
InterICFGNode *	addInterBlockICFGNode (const Instruction *inst)
	Add/Get an inter block ICFGNode. More...
ICFGNode *	addBlockICFGNode (const Instruction *inst)
	Add/Get a basic block ICFGNode. More...
IntraICFGNode *	addIntraBlockICFGNode (const Instruction *inst)
	Add and get IntraBlock ICFGNode. More...
FunEntryICFGNode *	addFunEntryBlock (const Function *fun)
FunExitICFGNode *	addFunExitBlock (const Function *fun)
void	addGlobalICFGNode ()

Detailed Description

Definition at line 41 of file ICFGBuilder.h.

Member Typedef Documentation

BBSet

typedef Set<const Instruction*> SVF::ICFGBuilder::BBSet

Definition at line 47 of file ICFGBuilder.h.

CSToCallNodeMapTy

typedef Map<const Instruction*, CallICFGNode *> SVF::ICFGBuilder::CSToCallNodeMapTy

Definition at line 48 of file ICFGBuilder.h.

CSToRetNodeMapTy

typedef Map<const Instruction*, RetICFGNode *> SVF::ICFGBuilder::CSToRetNodeMapTy

Definition at line 49 of file ICFGBuilder.h.

FunToFunEntryNodeMapTy

typedef Map<const Function*, FunEntryICFGNode *> SVF::ICFGBuilder::FunToFunEntryNodeMapTy

Definition at line 51 of file ICFGBuilder.h.

FunToFunExitNodeMapTy

typedef Map<const Function*, FunExitICFGNode *> SVF::ICFGBuilder::FunToFunExitNodeMapTy

Definition at line 52 of file ICFGBuilder.h.

InstToBlockNodeMapTy

typedef Map<const Instruction*, IntraICFGNode *> SVF::ICFGBuilder::InstToBlockNodeMapTy

Definition at line 50 of file ICFGBuilder.h.

InstVec

typedef std::vector<const Instruction*> SVF::ICFGBuilder::InstVec

Definition at line 46 of file ICFGBuilder.h.

WorkList

typedef FIFOWorkList<const Instruction*> SVF::ICFGBuilder::WorkList

Definition at line 59 of file ICFGBuilder.h.

Constructor & Destructor Documentation

ICFGBuilder()

SVF::ICFGBuilder::ICFGBuilder ( )

inline

Definition at line 61 of file ICFGBuilder.h.

                 : icfg(new ICFG())
    {
 
    }

Member Function Documentation

addBlockICFGNode()

ICFGNode * ICFGBuilder::addBlockICFGNode ( const Instruction *  inst )

inlineprivate

Add/Get a basic block ICFGNode.

Definition at line 331 of file ICFGBuilder.cpp.

{
    ICFGNode* node;
    if(LLVMUtil::isNonInstricCallSite(inst))
        node = addInterBlockICFGNode(inst);
    else
        node = addIntraBlockICFGNode(inst);
    const_cast<SVFBasicBlock*>(
        llvmModuleSet()->getSVFBasicBlock(inst->getParent()))
    ->addICFGNode(node);
    return node;
}

addFunEntryBlock()

FunEntryICFGNode * ICFGBuilder::addFunEntryBlock ( const Function *  fun )

private

Definition at line 355 of file ICFGBuilder.cpp.

{
    return funToFunEntryNodeMap()[fun] =
               icfg->addFunEntryICFGNode(llvmModuleSet()->getSVFFunction(fun));
}

addFunExitBlock()

FunExitICFGNode * ICFGBuilder::addFunExitBlock ( const Function *  fun )

inlineprivate

Definition at line 361 of file ICFGBuilder.cpp.

{
    return funToFunExitNodeMap()[fun] =
               icfg->addFunExitICFGNode(llvmModuleSet()->getSVFFunction(fun));
}

addGlobalICFGNode()

void SVF::ICFGBuilder::addGlobalICFGNode ( )

inlineprivate

Definition at line 175 of file ICFGBuilder.h.

    {
        icfg->globalBlockNode = new GlobalICFGNode(icfg->totalICFGNode++);
        icfg->addICFGNode(icfg->globalBlockNode);
    }

addICFGInterEdges()

void ICFGBuilder::addICFGInterEdges ( const Instruction *  cs, const Function *  callee  )

private

Create edges between ICFG nodes across functions.

Create edges between ICFG nodes across functions

direct call

if this is an external function (no function body)

otherwise connect interprocedural edges

indirect call (don't know callee)

Definition at line 278 of file ICFGBuilder.cpp.

{
 
    CallICFGNode* callICFGNode = getCallICFGNode(cs);
    RetICFGNode* retBlockNode = getRetICFGNode(cs);
 
    if(callee)
    {
        SVFFunction* svfFun =
            llvmModuleSet()->getSVFFunction(callee);
        if (SVFUtil::isExtCall(svfFun))
        {
            icfg->addIntraEdge(callICFGNode, retBlockNode);
        }
        else
        {
            FunEntryICFGNode* calleeEntryNode = getFunEntryICFGNode(callee);
            FunExitICFGNode* calleeExitNode = getFunExitICFGNode(callee);
            icfg->addCallEdge(callICFGNode, calleeEntryNode);
            icfg->addRetEdge(calleeExitNode, retBlockNode);
        }
    }
    else
    {
        icfg->addIntraEdge(callICFGNode, retBlockNode);
    }
}

addInterBlockICFGNode()

InterICFGNode * ICFGBuilder::addInterBlockICFGNode ( const Instruction *  inst )

private

Add/Get an inter block ICFGNode.

(1) Add and get CallBlockICFGNode (2) Handle call instruction by creating interprocedural edges

Definition at line 237 of file ICFGBuilder.cpp.

{
    assert(LLVMUtil::isCallSite(inst) && "not a call instruction?");
    assert(LLVMUtil::isNonInstricCallSite(inst) && "associating an intrinsic debug instruction with an ICFGNode!");
    assert(llvmModuleSet()->getCallBlock(inst)==nullptr && "duplicate CallICFGNode");
    const CallBase* cb = SVFUtil::dyn_cast<CallBase>(inst);
    bool isvcall = cppUtil::isVirtualCallSite(cb);
    SVFFunction* calledFunc = nullptr;
    auto called_llvmval = cb->getCalledOperand()->stripPointerCasts();
    if (const Function* called_llvmfunc = SVFUtil::dyn_cast<Function>(called_llvmval))
    {
        calledFunc = llvmModuleSet()->getSVFFunction(called_llvmfunc);
    }
    else
    {
        calledFunc = SVFUtil::dyn_cast<SVFFunction>(
                         llvmModuleSet()->getSVFValue(called_llvmval));
    }
 
    SVFBasicBlock* bb = llvmModuleSet()->getSVFBasicBlock(inst->getParent());
 
    CallICFGNode* callICFGNode = icfg->addCallICFGNode(
                                     bb, llvmModuleSet()->getSVFType(inst->getType()),
                                     calledFunc, cb->getFunctionType()->isVarArg(), isvcall,
                                     isvcall ? cppUtil::getVCallIdx(cb) : 0,
                                     isvcall ? cppUtil::getFunNameOfVCallSite(cb) : "");
    csToCallNodeMap()[inst] = callICFGNode;
    llvmModuleSet()->setValueAttr(inst, callICFGNode);
 
    assert(llvmModuleSet()->getRetBlock(inst)==nullptr && "duplicate RetICFGNode");
    RetICFGNode* retICFGNode = icfg->addRetICFGNode(callICFGNode);
    csToRetNodeMap()[inst] = retICFGNode;
    llvmModuleSet()->setValueAttr(inst, retICFGNode);
 
    addICFGInterEdges(inst, LLVMUtil::getCallee(SVFUtil::cast<CallBase>(inst)));    //creating interprocedural edges
    return callICFGNode;
}

addIntraBlockICFGNode()

IntraICFGNode * ICFGBuilder::addIntraBlockICFGNode ( const Instruction *  inst )

private

Add and get IntraBlock ICFGNode.

Definition at line 344 of file ICFGBuilder.cpp.

{
    IntraICFGNode* node = llvmModuleSet()->getIntraBlock(inst);
    assert (node==nullptr && "no IntraICFGNode for this instruction?");
    IntraICFGNode* sNode = icfg->addIntraICFGNode(
                               llvmModuleSet()->getSVFBasicBlock(inst->getParent()), SVFUtil::isa<ReturnInst>(inst));
    instToBlockNodeMap()[inst] = sNode;
    llvmModuleSet()->setValueAttr(inst, sNode);
    return sNode;
}

build()

ICFG * ICFGBuilder::build

(

)

Create ICFG nodes and edges

Definition at line 43 of file ICFGBuilder.cpp.

{
    DBOUT(DGENERAL, outs() << pasMsg("\t Building ICFG ...\n"));
    // Add the unique global ICFGNode at the entry of a program (before the main method).
    addGlobalICFGNode();
 
    // Add function entry and exit
    for (Module &M : llvmModuleSet()->getLLVMModules())
    {
        for (Module::const_iterator F = M.begin(), E = M.end(); F != E; ++F)
        {
            const Function *fun = &*F;
            if (fun->isDeclaration())
                continue;
            addFunEntryBlock(fun);
            addFunExitBlock(fun);
        }
 
    }
 
    for (Module &M : llvmModuleSet()->getLLVMModules())
    {
        for (Module::const_iterator F = M.begin(), E = M.end(); F != E; ++F)
        {
            const Function *fun = &*F;
            if (fun->isDeclaration())
                continue;
            WorkList worklist;
            processFunEntry(fun,worklist);
            processNoPrecessorBasicBlocks(fun, worklist);
            processFunBody(worklist);
            processFunExit(fun);
 
            checkICFGNodesVisited(fun);
        }
 
    }
    connectGlobalToProgEntry();
    return icfg;
}

checkICFGNodesVisited()

void ICFGBuilder::checkICFGNodesVisited ( const Function *  fun )

private

Definition at line 84 of file ICFGBuilder.cpp.

{
    for (const auto& bb: *fun)
    {
        for (const auto& inst: bb)
        {
            if(LLVMUtil::isIntrinsicInst(&inst))
                continue;
            assert(visited.count(&inst) && "inst never visited");
            assert(hasICFGNode(&inst) && "icfgnode not created");
        }
    }
}

connectGlobalToProgEntry()

void ICFGBuilder::connectGlobalToProgEntry ( )

private

Definition at line 312 of file ICFGBuilder.cpp.

{
    for (Module &M : llvmModuleSet()->getLLVMModules())
    {
        if (const Function* mainFunc = LLVMUtil::getProgEntryFunction(M))
        {
            // main function
            FunEntryICFGNode* entryNode = getFunEntryICFGNode(mainFunc);
            GlobalICFGNode* globalNode = getGlobalICFGNode();
            IntraCFGEdge* intraEdge = new IntraCFGEdge(globalNode, entryNode);
            icfg->addICFGEdge(intraEdge);
        }
        else
        {
            // not main function
        }
    }
}

csToCallNodeMap()

CSToCallNodeMapTy& SVF::ICFGBuilder::csToCallNodeMap ( )

inlineprivate

Definition at line 79 of file ICFGBuilder.h.

    {
        return llvmModuleSet()->CSToCallNodeMap;
    }

csToRetNodeMap()

CSToRetNodeMapTy& SVF::ICFGBuilder::csToRetNodeMap ( )

inlineprivate

Definition at line 74 of file ICFGBuilder.h.

    {
        return llvmModuleSet()->CSToRetNodeMap;
    }

funToFunEntryNodeMap()

FunToFunEntryNodeMapTy& SVF::ICFGBuilder::funToFunEntryNodeMap ( )

inlineprivate

Definition at line 89 of file ICFGBuilder.h.

    {
        return llvmModuleSet()->FunToFunEntryNodeMap;
    }

funToFunExitNodeMap()

FunToFunExitNodeMapTy& SVF::ICFGBuilder::funToFunExitNodeMap ( )

inlineprivate

Definition at line 94 of file ICFGBuilder.h.

    {
        return llvmModuleSet()->FunToFunExitNodeMap;
    }

getCallICFGNode()

CallICFGNode* SVF::ICFGBuilder::getCallICFGNode ( const Instruction *  cs )

inlineprivate

get a call node

Definition at line 131 of file ICFGBuilder.h.

    {
        return llvmModuleSet()->getCallICFGNode(cs);
    }

getFunEntryICFGNode()

FunEntryICFGNode* SVF::ICFGBuilder::getFunEntryICFGNode ( const Function *  fun )

inlineprivate

get a function entry node

Definition at line 147 of file ICFGBuilder.h.

    {
        return llvmModuleSet()->getFunEntryICFGNode(fun);
    }

getFunExitICFGNode()

FunExitICFGNode* SVF::ICFGBuilder::getFunExitICFGNode ( const Function *  fun )

inlineprivate

get a function exit node

Definition at line 152 of file ICFGBuilder.h.

    {
        return llvmModuleSet()->getFunExitICFGNode(fun);
    }

getGlobalICFGNode()

GlobalICFGNode* SVF::ICFGBuilder::getGlobalICFGNode ( ) const

inlineprivate

Definition at line 157 of file ICFGBuilder.h.

    {
        return icfg->getGlobalICFGNode();
    }

getICFGNode()

ICFGNode* SVF::ICFGBuilder::getICFGNode ( const Instruction *  inst )

inlineprivate

Definition at line 120 of file ICFGBuilder.h.

    {
        return llvmModuleSet()->getICFGNode(inst);
    }

getIntraICFGNode()

IntraICFGNode* SVF::ICFGBuilder::getIntraICFGNode ( const Instruction *  inst )

inlineprivate

get a intra node

Definition at line 141 of file ICFGBuilder.h.

    {
        return llvmModuleSet()->getIntraICFGNode(inst);
    }

getRetICFGNode()

RetICFGNode* SVF::ICFGBuilder::getRetICFGNode ( const Instruction *  cs )

inlineprivate

get a return node

Definition at line 136 of file ICFGBuilder.h.

    {
        return llvmModuleSet()->getRetICFGNode(cs);
    }

hasICFGNode()

bool SVF::ICFGBuilder::hasICFGNode ( const Instruction *  inst )

inlineprivate

Definition at line 125 of file ICFGBuilder.h.

    {
        return llvmModuleSet()->hasICFGNode(inst);
    }

instToBlockNodeMap()

InstToBlockNodeMapTy& SVF::ICFGBuilder::instToBlockNodeMap ( )

inlineprivate

Definition at line 84 of file ICFGBuilder.h.

    {
        return llvmModuleSet()->InstToBlockNodeMap;
    }

llvmModuleSet()

LLVMModuleSet* SVF::ICFGBuilder::llvmModuleSet ( )

inlineprivate

Definition at line 69 of file ICFGBuilder.h.

    {
        return LLVMModuleSet::getLLVMModuleSet();
    }

processFunBody()

void ICFGBuilder::processFunBody ( WorkList &  worklist )

private

function body

function body

branch condition value

default case is set to -1;

Definition at line 146 of file ICFGBuilder.cpp.

{
    while (!worklist.empty())
    {
        const Instruction* inst = worklist.pop();
        ICFGNode* srcNode = getICFGNode(inst);
        if (SVFUtil::isa<ReturnInst>(inst))
        {
            FunExitICFGNode* FunExitICFGNode = getFunExitICFGNode(inst->getFunction());
            icfg->addIntraEdge(srcNode, FunExitICFGNode);
        }
        InstVec nextInsts;
        LLVMUtil::getNextInsts(inst, nextInsts);
        s64_t branchID = 0;
        for (InstVec::const_iterator nit = nextInsts.begin(), enit =
                    nextInsts.end(); nit != enit; ++nit)
        {
            const Instruction* succ = *nit;
            ICFGNode* dstNode;
            if (visited.find(succ) != visited.end())
            {
                dstNode = getICFGNode(succ);
            }
            else
            {
                visited.insert(succ);
                dstNode = addBlockICFGNode(succ);
                worklist.push(succ);
            }
 
 
            if (LLVMUtil::isNonInstricCallSite(inst))
            {
                RetICFGNode* retICFGNode = getRetICFGNode(inst);
                srcNode = retICFGNode;
            }
 
            if (const BranchInst* br = SVFUtil::dyn_cast<BranchInst>(inst))
            {
                assert(branchID <= 1 && "if/else has more than two branches?");
                if(br->isConditional())
                    icfg->addConditionalIntraEdge(srcNode, dstNode, 1 - branchID);
                else
                    icfg->addIntraEdge(srcNode, dstNode);
            }
            else if (const SwitchInst* si = SVFUtil::dyn_cast<SwitchInst>(inst))
            {
                const ConstantInt* condVal = const_cast<SwitchInst*>(si)->findCaseDest(const_cast<BasicBlock*>(succ->getParent()));
                s64_t val = -1;
                if (condVal && condVal->getBitWidth() <= 64)
                    val = condVal->getSExtValue();
                icfg->addConditionalIntraEdge(srcNode, dstNode,val);
            }
            else
                icfg->addIntraEdge(srcNode, dstNode);
            branchID++;
        }
    }
}

processFunEntry()

void ICFGBuilder::processFunEntry ( const Function *  fun, WorkList &  worklist  )

private

Create edges between ICFG nodes within a function

function entry

Definition at line 100 of file ICFGBuilder.cpp.

{
    FunEntryICFGNode* FunEntryICFGNode = getFunEntryICFGNode(fun);
    const Instruction* entryInst = &((fun->getEntryBlock()).front());
 
    InstVec insts;
    if (LLVMUtil::isIntrinsicInst(entryInst))
        LLVMUtil::getNextInsts(entryInst, insts);
    else
        insts.push_back(entryInst);
    for (InstVec::const_iterator nit = insts.begin(), enit = insts.end();
            nit != enit; ++nit)
    {
        visited.insert(*nit);
        ICFGNode* instNode = addBlockICFGNode(*nit);           //add interprocedural edge
        worklist.push(*nit);
        icfg->addIntraEdge(FunEntryICFGNode, instNode);
    }
 
 
 
}

processFunExit()

void ICFGBuilder::processFunExit ( const Function *  f )

private

function exit e.g., exit(0). In LLVM, it usually manifests as "unreachable" instruction If a function has multiple exit(0), we will only have one "unreachle" instruction after the UnifyFunctionExitNodes pass.

Definition at line 214 of file ICFGBuilder.cpp.

{
    FunExitICFGNode* FunExitICFGNode = getFunExitICFGNode(f);
 
    for (const auto& bb : *f)
    {
        for (const auto& inst : bb)
        {
            if (SVFUtil::isa<ReturnInst>(&inst))
            {
                icfg->addIntraEdge(getICFGNode(&inst), FunExitICFGNode);
            }
        }
    }
}

processNoPrecessorBasicBlocks()

void ICFGBuilder::processNoPrecessorBasicBlocks ( const Function *  fun, WorkList &  worklist  )

private

bbs with no predecessors

Definition at line 126 of file ICFGBuilder.cpp.

{
    for (const auto& bb: *fun)
    {
        for (const auto& inst: bb)
        {
            if (LLVMUtil::isNoPrecessorBasicBlock(inst.getParent()) &&
                    !visited.count(&inst))
            {
                visited.insert(&inst);
                (void)addBlockICFGNode(&inst);
                worklist.push(&inst);
            }
        }
    }
}

Member Data Documentation

icfg

ICFG* SVF::ICFGBuilder::icfg

private

Definition at line 56 of file ICFGBuilder.h.

visited

BBSet SVF::ICFGBuilder::visited

private

Definition at line 182 of file ICFGBuilder.h.

---

The documentation for this class was generated from the following files:

• /home/runner/work/SVF/SVF/svf-llvm/include/SVF-LLVM/ICFGBuilder.h
• /home/runner/work/SVF/SVF/svf-llvm/lib/ICFGBuilder.cpp