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 ()=default
ICFG *	build ()

Private Member Functions
LLVMModuleSet *	llvmModuleSet ()

Private Attributes
ICFG *	icfg
BBSet	visited
void	processFunEntry (const Function *fun, WorkList &worklist)
void	processUnreachableFromEntry (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.
ICFGNode *	getICFGNode (const Instruction *inst)
bool	hasICFGNode (const Instruction *inst)
CallICFGNode *	getCallICFGNode (const Instruction *cs)
	get a call node
RetICFGNode *	getRetICFGNode (const Instruction *cs)
	get a return node
IntraICFGNode *	getIntraICFGNode (const Instruction *inst)
	get a intra node
FunEntryICFGNode *	getFunEntryICFGNode (const Function *fun)
	get a function entry node
FunExitICFGNode *	getFunExitICFGNode (const Function *fun)
	get a function exit node
GlobalICFGNode *	getGlobalICFGNode () const
InterICFGNode *	addInterBlockICFGNode (const Instruction *inst)
	Add/Get an inter block ICFGNode.
ICFGNode *	addBlockICFGNode (const Instruction *inst)
	Add/Get a basic block ICFGNode.
IntraICFGNode *	addIntraBlockICFGNode (const Instruction *inst)
	Add and get IntraBlock ICFGNode.
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 ( )

default

Member Function Documentation

addBlockICFGNode()

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

inlineprivate

Add/Get a basic block ICFGNode.

Definition at line 330 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 354 of file ICFGBuilder.cpp.

{
    return llvmModuleSet()->FunToFunEntryNodeMap[fun] =
               icfg->addFunEntryICFGNode(llvmModuleSet()->getFunObjVar(fun));
}

addFunExitBlock()

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

inlineprivate

Definition at line 360 of file ICFGBuilder.cpp.

{
    return llvmModuleSet()->FunToFunExitNodeMap[fun] =
               icfg->addFunExitICFGNode(llvmModuleSet()->getFunObjVar(fun));
}

addGlobalICFGNode()

void SVF::ICFGBuilder::addGlobalICFGNode ( )

inlineprivate

Definition at line 148 of file ICFGBuilder.h.

    {
        icfg->globalBlockNode = new GlobalICFGNode(icfg->totalICFGNode++);
        icfg->addGlobalICFGNode(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 277 of file ICFGBuilder.cpp.

{
 
    CallICFGNode* callICFGNode = getCallICFGNode(cs);
    RetICFGNode* retBlockNode = getRetICFGNode(cs);

    if(callee)
    {
        const FunObjVar* svfFun =
            llvmModuleSet()->getFunObjVar(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 239 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);
    const FunObjVar* calledFunc = nullptr;
    auto called_llvmval = cb->getCalledOperand()->stripPointerCasts();
    if (const Function* called_llvmfunc = SVFUtil::dyn_cast<Function>(called_llvmval))
    {
        calledFunc = llvmModuleSet()->getFunObjVar(called_llvmfunc);
    }
    else
    {
        assert(SVFUtil::dyn_cast<Function>(called_llvmval) == nullptr && "must be nullptr");
    }
 
    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) : "");
    llvmModuleSet()->addInstructionMap(inst, callICFGNode);
 
    assert(llvmModuleSet()->getRetBlock(inst)==nullptr && "duplicate RetICFGNode");
    RetICFGNode* retICFGNode = icfg->addRetICFGNode(callICFGNode);
    llvmModuleSet()->addInstructionMap(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 343 of file ICFGBuilder.cpp.

{
    IntraICFGNode* node = llvmModuleSet()->getIntraBlock(inst);
    (void)node; // Suppress warning of unused variable under release build
    assert (node==nullptr && "no IntraICFGNode for this instruction?");
    IntraICFGNode* sNode = icfg->addIntraICFGNode(
                               llvmModuleSet()->getSVFBasicBlock(inst->getParent()), SVFUtil::isa<ReturnInst>(inst));
    llvmModuleSet()->addInstructionMap(inst, sNode);
    return sNode;
}

build()

ICFG * ICFGBuilder::build

(

)

Create ICFG nodes and edges

Definition at line 45 of file ICFGBuilder.cpp.

{
    icfg = new ICFG();
    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);
            processUnreachableFromEntry(fun, worklist);
            processFunBody(worklist);
            processFunExit(fun);
 
            checkICFGNodesVisited(fun);
        }
 
    }
    connectGlobalToProgEntry();
    return icfg;
}

checkICFGNodesVisited()

void ICFGBuilder::checkICFGNodesVisited ( const Function * fun )

private

Definition at line 87 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 311 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
        }
    }
}

getCallICFGNode()

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

inlineprivate

get a call node

Definition at line 104 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 120 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 125 of file ICFGBuilder.h.

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

getGlobalICFGNode()

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

inlineprivate

Definition at line 130 of file ICFGBuilder.h.

    {
        return icfg->getGlobalICFGNode();
    }

getICFGNode()

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

inlineprivate

Definition at line 93 of file ICFGBuilder.h.

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

getIntraICFGNode()

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

inlineprivate

get a intra node

Definition at line 114 of file ICFGBuilder.h.

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

getRetICFGNode()

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

inlineprivate

get a return node

Definition at line 109 of file ICFGBuilder.h.

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

hasICFGNode()

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

inlineprivate

Definition at line 98 of file ICFGBuilder.h.

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

llvmModuleSet()

LLVMModuleSet * SVF::ICFGBuilder::llvmModuleSet ( )

inlineprivate

Definition at line 67 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 148 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 = LLVMUtil::getIntegerValue(condVal).first;
                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 103 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 216 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);
            }
        }
    }
}

processUnreachableFromEntry()

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

private

bbs unreachable from function entry

Definition at line 129 of file ICFGBuilder.cpp.

{
    SVFLoopAndDomInfo* pInfo =
        llvmModuleSet()->getFunObjVar(fun)->getLoopAndDomInfo();
    for (const auto& bb : *fun)
    {
        if (pInfo->isUnreachable(llvmModuleSet()->getSVFBasicBlock(&bb)) &&
                !visited.count(&bb.front()))
        {
            visited.insert(&bb.front());
            (void)addBlockICFGNode(&bb.front());
            worklist.push(&bb.front());
        }
    }
}

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 155 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