Static Value-Flow Analysis
Loading...
Searching...
No Matches
ICFGBuilder.cpp
Go to the documentation of this file.
1//===- ICFGBuilder.cpp ----------------------------------------------------------------//
2//
3// SVF: Static Value-Flow Analysis
4//
5// Copyright (C) <2013-> <Yulei Sui>
6//
7
8// This program is free software: you can redistribute it and/or modify
9// it under the terms of the GNU Affero General Public License as published by
10// the Free Software Foundation, either version 3 of the License, or
11// (at your option) any later version.
12
13// This program is distributed in the hope that it will be useful,
14// but WITHOUT ANY WARRANTY; without even the implied warranty of
15// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16// GNU Affero General Public License for more details.
17
18// You should have received a copy of the GNU Affero General Public License
19// along with this program. If not, see <http://www.gnu.org/licenses/>.
20//
21//===----------------------------------------------------------------------===//
22
23
24/*
25 * ICFGBuilder.cpp
26 *
27 * Created on:
28 * Author: yulei
29 * Refactored on:
30 * Author: Xiao Cheng, Yulei Sui
31 */
32
34#include "SVF-LLVM/CppUtil.h"
35#include "SVF-LLVM/LLVMModule.h"
36#include "SVF-LLVM/LLVMUtil.h"
37
38using namespace SVF;
39using namespace SVFUtil;
40
41
46{
47 icfg = new ICFG();
48 DBOUT(DGENERAL, outs() << pasMsg("\t Building ICFG ...\n"));
49 // Add the unique global ICFGNode at the entry of a program (before the main method).
51
52 // Add function entry and exit
54 {
55 for (Module::const_iterator F = M.begin(), E = M.end(); F != E; ++F)
56 {
57 const Function *fun = &*F;
58 if (fun->isDeclaration())
59 continue;
61 addFunExitBlock(fun);
62 }
63
64 }
65
67 {
68 for (Module::const_iterator F = M.begin(), E = M.end(); F != E; ++F)
69 {
70 const Function *fun = &*F;
71 if (fun->isDeclaration())
72 continue;
73 WorkList worklist;
74 processFunEntry(fun,worklist);
75 processUnreachableFromEntry(fun, worklist);
76 processFunBody(worklist);
77 processFunExit(fun);
78
80 }
81
82 }
84 return icfg;
85}
86
88{
89 for (const auto& bb: *fun)
90 {
91 for (const auto& inst: bb)
92 {
94 continue;
95 assert(visited.count(&inst) && "inst never visited");
96 assert(hasICFGNode(&inst) && "icfgnode not created");
97 }
98 }
99}
104{
106 const Instruction* entryInst = &((fun->getEntryBlock()).front());
107
111 else
112 insts.push_back(entryInst);
113 for (InstVec::const_iterator nit = insts.begin(), enit = insts.end();
114 nit != enit; ++nit)
115 {
116 visited.insert(*nit);
117 ICFGNode* instNode = addBlockICFGNode(*nit); //add interprocedural edge
118 worklist.push(*nit);
120 }
121
122
123
124}
125
130{
133 for (const auto& bb : *fun)
134 {
135 if (pInfo->isUnreachable(llvmModuleSet()->getSVFBasicBlock(&bb)) &&
136 !visited.count(&bb.front()))
137 {
138 visited.insert(&bb.front());
139 (void)addBlockICFGNode(&bb.front());
140 worklist.push(&bb.front());
141 }
142 }
143}
144
149{
151 while (!worklist.empty())
152 {
153 const Instruction* inst = worklist.pop();
155 if (SVFUtil::isa<ReturnInst>(inst))
156 {
157 FunExitICFGNode* FunExitICFGNode = getFunExitICFGNode(inst->getFunction());
159 }
162 s64_t branchID = 0;
163 for (InstVec::const_iterator nit = nextInsts.begin(), enit =
164 nextInsts.end(); nit != enit; ++nit)
165 {
166 const Instruction* succ = *nit;
168 if (visited.find(succ) != visited.end())
169 {
171 }
172 else
173 {
174 visited.insert(succ);
176 worklist.push(succ);
177 }
178
179
181 {
184 }
185
186 if (const BranchInst* br = SVFUtil::dyn_cast<BranchInst>(inst))
187 {
188 assert(branchID <= 1 && "if/else has more than two branches?");
189 if(br->isConditional())
191 else
193 }
194 else if (const SwitchInst* si = SVFUtil::dyn_cast<SwitchInst>(inst))
195 {
197 const ConstantInt* condVal = const_cast<SwitchInst*>(si)->findCaseDest(const_cast<BasicBlock*>(succ->getParent()));
199 s64_t val = -1;
200 if (condVal && condVal->getBitWidth() <= 64)
203 }
204 else
206 branchID++;
207 }
208 }
209}
210
217{
219
220 for (const auto& bb : *f)
221 {
222 for (const auto& inst : bb)
223 {
224 if (SVFUtil::isa<ReturnInst>(&inst))
225 {
227 }
228 }
229 }
230}
231
232
233
234
240{
241 assert(LLVMUtil::isCallSite(inst) && "not a call instruction?");
242 assert(LLVMUtil::isNonInstricCallSite(inst) && "associating an intrinsic debug instruction with an ICFGNode!");
243 assert(llvmModuleSet()->getCallBlock(inst)==nullptr && "duplicate CallICFGNode");
244 const CallBase* cb = SVFUtil::dyn_cast<CallBase>(inst);
246 const FunObjVar* calledFunc = nullptr;
247 auto called_llvmval = cb->getCalledOperand()->stripPointerCasts();
248 if (const Function* called_llvmfunc = SVFUtil::dyn_cast<Function>(called_llvmval))
249 {
251 }
252 else
253 {
254 assert(SVFUtil::dyn_cast<Function>(called_llvmval) == nullptr && "must be nullptr");
255 }
256
257 SVFBasicBlock* bb = llvmModuleSet()->getSVFBasicBlock(inst->getParent());
258
260 bb, llvmModuleSet()->getSVFType(inst->getType()),
261 calledFunc, cb->getFunctionType()->isVarArg(), isvcall,
265
266 assert(llvmModuleSet()->getRetBlock(inst)==nullptr && "duplicate RetICFGNode");
269
270 addICFGInterEdges(inst, LLVMUtil::getCallee(SVFUtil::cast<CallBase>(inst))); //creating interprocedural edges
271 return callICFGNode;
272}
273
308/*
309* Add the global initialization statements immediately after the function entry of main
310*/
312{
314 {
316 {
317 // main function
322 }
323 else
324 {
325 // not main function
326 }
327 }
328}
329
331{
332 ICFGNode* node;
334 node = addInterBlockICFGNode(inst);
335 else
336 node = addIntraBlockICFGNode(inst);
337 const_cast<SVFBasicBlock*>(
338 llvmModuleSet()->getSVFBasicBlock(inst->getParent()))
339 ->addICFGNode(node);
340 return node;
341}
342
344{
346 assert (node==nullptr && "no IntraICFGNode for this instruction?");
348 llvmModuleSet()->getSVFBasicBlock(inst->getParent()), SVFUtil::isa<ReturnInst>(inst));
350 return sNode;
351}
352
358
360{
361 return llvmModuleSet()->FunToFunExitNodeMap[fun] =
362 icfg->addFunExitICFGNode(llvmModuleSet()->getFunObjVar(fun));
363}
#define DBOUT(TYPE, X)
LLVM debug macros, define type of your DBUG model of each pass.
Definition SVFType.h:512
#define DGENERAL
Definition SVFType.h:518
bool push(const Data &data)
Definition WorkList.h:165
bool empty() const
Definition WorkList.h:146
const SVFFunctionType * getFunctionType() const
Returns the FunctionType.
SVFLoopAndDomInfo * getLoopAndDomInfo() const
ICFGNode * getICFGNode(const Instruction *inst)
Definition ICFGBuilder.h:93
FunEntryICFGNode * addFunEntryBlock(const Function *fun)
void connectGlobalToProgEntry()
FunEntryICFGNode * getFunEntryICFGNode(const Function *fun)
get a function entry node
FunExitICFGNode * getFunExitICFGNode(const Function *fun)
get a function exit node
IntraICFGNode * addIntraBlockICFGNode(const Instruction *inst)
Add and get IntraBlock ICFGNode.
CallICFGNode * getCallICFGNode(const Instruction *cs)
get a call node
std::vector< const Instruction * > InstVec
Definition ICFGBuilder.h:46
LLVMModuleSet * llvmModuleSet()
Definition ICFGBuilder.h:67
void addGlobalICFGNode()
void processUnreachableFromEntry(const Function *fun, WorkList &worklist)
InterICFGNode * addInterBlockICFGNode(const Instruction *inst)
Add/Get an inter block ICFGNode.
bool hasICFGNode(const Instruction *inst)
Definition ICFGBuilder.h:98
void processFunBody(WorkList &worklist)
GlobalICFGNode * getGlobalICFGNode() const
void checkICFGNodesVisited(const Function *fun)
void processFunEntry(const Function *fun, WorkList &worklist)
FunExitICFGNode * addFunExitBlock(const Function *fun)
ICFGNode * addBlockICFGNode(const Instruction *inst)
Add/Get a basic block ICFGNode.
RetICFGNode * getRetICFGNode(const Instruction *cs)
get a return node
void addICFGInterEdges(const Instruction *cs, const Function *callee)
Create edges between ICFG nodes across functions.
void processFunExit(const Function *fun)
virtual FunEntryICFGNode * addFunEntryICFGNode(const FunObjVar *svfFunc)
Definition ICFG.h:200
virtual CallICFGNode * addCallICFGNode(const SVFBasicBlock *bb, const SVFType *ty, const FunObjVar *calledFunc, bool isVararg, bool isvcall, s32_t vcallIdx, const std::string &funNameOfVcall)
Definition ICFG.h:179
bool addICFGEdge(ICFGEdge *edge)
Add ICFG edge, only used by addIntraEdge, addCallEdge, addRetEdge etc.
Definition ICFG.h:238
virtual RetICFGNode * addRetICFGNode(CallICFGNode *call)
Definition ICFG.h:192
virtual IntraICFGNode * addIntraICFGNode(const SVFBasicBlock *bb, bool isRet)
Definition ICFG.h:171
ICFGEdge * addCallEdge(ICFGNode *srcNode, ICFGNode *dstNode)
Definition ICFG.cpp:374
virtual FunExitICFGNode * addFunExitICFGNode(const FunObjVar *svfFunc)
Definition ICFG.h:207
ICFGEdge * addRetEdge(ICFGNode *srcNode, ICFGNode *dstNode)
Definition ICFG.cpp:392
ICFGEdge * addConditionalIntraEdge(ICFGNode *srcNode, ICFGNode *dstNode, s64_t branchCondVal)
Definition ICFG.cpp:352
ICFGEdge * addIntraEdge(ICFGNode *srcNode, ICFGNode *dstNode)
Add intraprocedural and interprocedural control-flow edges.
Definition ICFG.cpp:333
IntraICFGNode * getIntraBlock(const Instruction *inst)
Definition LLVMModule.h:500
const FunObjVar * getFunObjVar(const Function *fun) const
Definition LLVMModule.h:267
SVFBasicBlock * getSVFBasicBlock(const BasicBlock *bb)
Definition LLVMModule.h:298
void addInstructionMap(const Instruction *inst, CallICFGNode *svfInst)
Definition LLVMModule.h:239
const std::vector< std::reference_wrapper< Module > > & getLLVMModules() const
Definition LLVMModule.h:157
FunToFunEntryNodeMapTy FunToFunEntryNodeMap
map a function to its FunExitICFGNode
Definition LLVMModule.h:109
FunToFunExitNodeMapTy FunToFunExitNodeMap
map a function to its FunEntryICFGNode
Definition LLVMModule.h:110
bool isVarArg() const
Definition SVFType.h:355
bool isIntrinsicInst(const Instruction *inst)
Return true if it is an intrinsic instruction.
Definition LLVMUtil.cpp:202
bool isCallSite(const Instruction *inst)
Whether an instruction is a call or invoke instruction.
Definition LLVMUtil.h:44
std::pair< s64_t, u64_t > getIntegerValue(const ConstantInt *intValue)
Definition LLVMUtil.h:82
void getNextInsts(const Instruction *curInst, std::vector< const Instruction * > &instList)
Get the next instructions following control flow.
Definition LLVMUtil.cpp:573
const Function * getProgEntryFunction(Module &module)
Get program entry function from module.
Definition LLVMUtil.h:418
const Function * getCallee(const CallBase *cs)
Definition LLVMUtil.h:97
bool isNonInstricCallSite(const Instruction *inst)
Whether an instruction is a callsite in the application code, excluding llvm intrinsic calls.
Definition LLVMUtil.cpp:720
std::string pasMsg(const std::string &msg)
Print each pass/phase message by converting a string into blue string output.
Definition SVFUtil.cpp:101
bool isExtCall(const FunObjVar *fun)
Definition SVFUtil.cpp:437
std::ostream & outs()
Overwrite llvm::outs()
Definition SVFUtil.h:52
std::string getFunNameOfVCallSite(const CallBase *cs)
Definition CppUtil.cpp:635
s32_t getVCallIdx(const CallBase *cs)
Definition CppUtil.cpp:646
bool isVirtualCallSite(const CallBase *cs)
Definition CppUtil.cpp:352
for isBitcode
Definition BasicTypes.h:68
llvm::CallBase CallBase
Definition BasicTypes.h:146
llvm::BasicBlock BasicBlock
Definition BasicTypes.h:86
llvm::SwitchInst SwitchInst
Definition BasicTypes.h:155
llvm::Function Function
Definition BasicTypes.h:85
llvm::Instruction Instruction
Definition BasicTypes.h:87
llvm::IRBuilder IRBuilder
Definition BasicTypes.h:74
llvm::Module Module
Definition BasicTypes.h:84
llvm::BranchInst BranchInst
Definition BasicTypes.h:154
signed long long s64_t
Definition GeneralType.h:50
llvm::ConstantInt ConstantInt
Definition BasicTypes.h:125