Static Value-Flow Analysis
Loading...
Searching...
No Matches
ICFG.h
Go to the documentation of this file.
1//===- ICFG.h ----------------------------------------------------------------//
2//
3// SVF: Static Value-Flow Analysis
4//
5// Copyright (C) <2013-2018> <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 * ICFG.h
25 *
26 * Created on: 11 Sep. 2018
27 * Author: Yulei
28 */
29
30#ifndef INCLUDE_UTIL_ICFG_H_
31#define INCLUDE_UTIL_ICFG_H_
32
33#include "Graphs/ICFGNode.h"
34#include "Graphs/ICFGEdge.h"
35#include "Util/WorkList.h"
36#include "MemoryModel/SVFLoop.h"
37
38namespace SVF
39{
40
41class CallGraph;
42
47class ICFG : public GenericICFGTy
48{
49 friend class ICFGBuilder;
50 friend class SVFIRWriter;
51 friend class SVFIRReader;
52 friend class ICFGSimplification;
53
54public:
55
58 typedef ICFGNodeIDToNodeMapTy::iterator iterator;
59 typedef ICFGNodeIDToNodeMapTy::const_iterator const_iterator;
60
63 typedef std::vector<const SVFLoop *> SVFLoopVec;
65
67
68private:
73
74public:
76 ICFG();
77
79 ~ICFG() override;
80
82 inline ICFGNode* getICFGNode(NodeID id) const
83 {
84 return getGNode(id);
85 }
86
88 inline bool hasICFGNode(NodeID id) const
89 {
90 return hasGNode(id);
91 }
92
94
99
101 ICFGEdge* getICFGEdge(const ICFGNode* src, const ICFGNode* dst, ICFGEdge::ICFGEdgeK kind);
102
104 void dump(const std::string& file, bool simple = false);
105
107 void view();
108
110 void updateCallGraph(CallGraph* callgraph);
111
113 inline bool isInLoop(const ICFGNode *node)
114 {
115 auto it = icfgNodeToSVFLoopVec.find(node);
116 return it != icfgNodeToSVFLoopVec.end();
117 }
118
120 inline void addNodeToSVFLoop(const ICFGNode *node, const SVFLoop* loop)
121 {
122 icfgNodeToSVFLoopVec[node].push_back(loop);
123 }
124
126 inline SVFLoopVec& getSVFLoops(const ICFGNode *node)
127 {
128 auto it = icfgNodeToSVFLoopVec.find(node);
129 assert(it != icfgNodeToSVFLoopVec.end() && "node not in loop");
130 return it->second;
131 }
132
134 {
136 }
137
138protected:
140
146
148 {
149 edge->getDstNode()->removeIncomingEdge(edge);
150 edge->getSrcNode()->removeOutgoingEdge(edge);
151 delete edge;
152 }
153
155 inline void removeICFGNode(ICFGNode* node)
156 {
157 removeGNode(node);
158 }
159
162 {
163 const FunObjVar* srcfun = srcNode->getFun();
164 const FunObjVar* dstfun = dstNode->getFun();
165 if(srcfun != nullptr && dstfun != nullptr)
166 {
167 assert((srcfun == dstfun) && "src and dst nodes of an intra edge should in the same function!" );
168 }
169 }
170
171 virtual inline IntraICFGNode* addIntraICFGNode(const SVFBasicBlock* bb, bool isRet)
172 {
174 new IntraICFGNode(totalICFGNode++, bb, isRet);
176 return intraIcfgNode;
177 }
178
180 const SVFBasicBlock* bb, const SVFType* ty,
181 const FunObjVar* calledFunc, bool isVararg, bool isvcall,
182 s32_t vcallIdx, const std::string& funNameOfVcall)
183 {
184
186 new CallICFGNode(totalICFGNode++, bb, ty, calledFunc, isVararg,
187 isvcall, vcallIdx, funNameOfVcall);
189 return callICFGNode;
190 }
191
193 {
197 return retICFGNode;
198 }
199
206
213
215 virtual inline void addICFGNode(ICFGNode* node)
216 {
217 addGNode(node->getId(),node);
218 }
219
220public:
223
224
225
227
229
231 {
232 return globalBlockNode;
233 }
235
236private:
239 {
240 bool added1 = edge->getDstNode()->addIncomingEdge(edge);
241 bool added2 = edge->getSrcNode()->addOutgoingEdge(edge);
242 bool all_added = added1 && added2;
243 assert(all_added && "ICFGEdge not added?");
244 return all_added;
245 }
246
249 {
250 FunToFunEntryNodeMapTy::const_iterator it = FunToFunEntryNodeMap.find(fun);
251 if (it == FunToFunEntryNodeMap.end())
252 return nullptr;
253 return it->second;
254 }
255
258 {
259 FunToFunExitNodeMapTy::const_iterator it = FunToFunExitNodeMap.find(fun);
260 if (it == FunToFunExitNodeMap.end())
261 return nullptr;
262 return it->second;
263 }
264
265};
266
267} // End namespace SVF
268
269namespace SVF
270{
271/* !
272 * GenericGraphTraits specializations for generic graph algorithms.
273 * Provide graph traits for traversing from a constraint node using standard graph traversals.
274 */
275template<> struct GenericGraphTraits<SVF::ICFGNode*> : public GenericGraphTraits<SVF::GenericNode<SVF::ICFGNode,SVF::ICFGEdge>* >
276{
277};
278
280template<>
281struct GenericGraphTraits<Inverse<SVF::ICFGNode *> > : public GenericGraphTraits<Inverse<SVF::GenericNode<SVF::ICFGNode,SVF::ICFGEdge>* > >
282{
283};
284
285template<> struct GenericGraphTraits<SVF::ICFG*> : public GenericGraphTraits<SVF::GenericGraph<SVF::ICFGNode,SVF::ICFGEdge>* >
286{
288};
289
290} // End namespace llvm
291
292#endif /* INCLUDE_UTIL_ICFG_H_ */
void setRetICFGNode(const RetICFGNode *r)
Return callsite.
Definition ICFGNode.h:458
void addGNode(NodeID id, NodeType *node)
Add a Node.
void removeGNode(NodeType *node)
Delete a node.
bool hasGNode(NodeID id) const
Has a node.
NodeType * getGNode(NodeID id) const
Get a node.
GenericNode< ICFGNode, ICFGEdge >::GEdgeSetTy ICFGEdgeSetTy
Definition ICFGEdge.h:90
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
void view()
View graph from the debugger.
Definition ICFG.cpp:419
virtual void addICFGNode(ICFGNode *node)
Add a ICFG node.
Definition ICFG.h:215
bool hasICFGNode(NodeID id) const
Whether has the ICFGNode.
Definition ICFG.h:88
ICFGEdge::ICFGEdgeSetTy ICFGEdgeSetTy
Definition ICFG.h:57
ICFGEdge * hasThreadICFGEdge(ICFGNode *src, ICFGNode *dst, ICFGEdge::ICFGEdgeK kind)
Definition ICFG.cpp:293
const ICFGNodeToSVFLoopVec & getIcfgNodeToSVFLoopVec() const
Definition ICFG.h:133
void removeICFGNode(ICFGNode *node)
Remove a ICFGNode.
Definition ICFG.h:155
Map< const FunObjVar *, FunExitICFGNode * > FunToFunExitNodeMapTy
Definition ICFG.h:62
Map< const ICFGNode *, SVFLoopVec > ICFGNodeToSVFLoopVec
Definition ICFG.h:64
bool addICFGEdge(ICFGEdge *edge)
Add ICFG edge, only used by addIntraEdge, addCallEdge, addRetEdge etc.
Definition ICFG.h:238
friend class ICFGSimplification
Definition ICFG.h:52
ICFGNodeIDToNodeMapTy::iterator iterator
Definition ICFG.h:58
virtual RetICFGNode * addRetICFGNode(CallICFGNode *call)
Definition ICFG.h:192
void removeICFGEdge(ICFGEdge *edge)
Remove a ICFG edge.
Definition ICFG.h:147
ICFGEdge * getICFGEdge(const ICFGNode *src, const ICFGNode *dst, ICFGEdge::ICFGEdgeK kind)
Get a SVFG edge according to src and dst.
Definition ICFG.cpp:311
NodeID totalICFGNode
Definition ICFG.h:66
Map< const FunObjVar *, FunEntryICFGNode * > FunToFunEntryNodeMapTy
Definition ICFG.h:61
ICFGNode * getICFGNode(NodeID id) const
Get a ICFG node.
Definition ICFG.h:82
ICFG()
Constructor.
Definition ICFG.cpp:218
FunToFunEntryNodeMapTy FunToFunEntryNodeMap
map a function to its FunExitICFGNode
Definition ICFG.h:69
virtual IntraICFGNode * addIntraICFGNode(const SVFBasicBlock *bb, bool isRet)
Definition ICFG.h:171
void checkIntraEdgeParents(const ICFGNode *srcNode, const ICFGNode *dstNode)
sanitize Intra edges, verify that both nodes belong to the same function.
Definition ICFG.h:161
ICFGEdge * addCallEdge(ICFGNode *srcNode, ICFGNode *dstNode)
Definition ICFG.cpp:374
ICFGNodeToSVFLoopVec icfgNodeToSVFLoopVec
map ICFG node to the SVF loops where it resides
Definition ICFG.h:72
FunExitICFGNode * getFunExitICFGNode(const FunObjVar *fun)
Add a function exit node.
Definition ICFG.cpp:249
ICFGEdge * hasInterICFGEdge(ICFGNode *src, ICFGNode *dst, ICFGEdge::ICFGEdgeK kind)
Definition ICFG.cpp:276
void addNodeToSVFLoop(const ICFGNode *node, const SVFLoop *loop)
Insert (node, loop) to icfgNodeToSVFLoopVec.
Definition ICFG.h:120
GlobalICFGNode * globalBlockNode
unique basic block for all globals
Definition ICFG.h:71
ICFGNodeIDToNodeMapTy::const_iterator const_iterator
Definition ICFG.h:59
friend class SVFIRReader
Definition ICFG.h:51
void dump(const std::string &file, bool simple=false)
Dump graph into dot file.
Definition ICFG.cpp:411
virtual FunExitICFGNode * addFunExitICFGNode(const FunObjVar *svfFunc)
Definition ICFG.h:207
ICFGEdge * addRetEdge(ICFGNode *srcNode, ICFGNode *dstNode)
Definition ICFG.cpp:392
void updateCallGraph(CallGraph *callgraph)
update ICFG for indirect calls
Definition ICFG.cpp:427
ICFGEdge * hasIntraICFGEdge(ICFGNode *src, ICFGNode *dst, ICFGEdge::ICFGEdgeK kind)
Whether we has a SVFG edge.
Definition ICFG.cpp:259
FunToFunExitNodeMapTy FunToFunExitNodeMap
map a function to its FunEntryICFGNode
Definition ICFG.h:70
ICFGEdge * addConditionalIntraEdge(ICFGNode *srcNode, ICFGNode *dstNode, s64_t branchCondVal)
Definition ICFG.cpp:352
OrderedMap< NodeID, ICFGNode * > ICFGNodeIDToNodeMapTy
Definition ICFG.h:56
FunExitICFGNode * getFunExitBlock(const FunObjVar *fun)
Get/Add a function exit node.
Definition ICFG.h:257
friend class SVFIRWriter
Definition ICFG.h:50
std::vector< const SVFLoop * > SVFLoopVec
Definition ICFG.h:63
ICFGEdge * addIntraEdge(ICFGNode *srcNode, ICFGNode *dstNode)
Add intraprocedural and interprocedural control-flow edges.
Definition ICFG.cpp:333
FunEntryICFGNode * getFunEntryICFGNode(const FunObjVar *fun)
Add a function entry node.
Definition ICFG.cpp:242
bool isInLoop(const ICFGNode *node)
Whether node is in a loop.
Definition ICFG.h:113
~ICFG() override
Destructor.
Definition ICFG.cpp:222
GlobalICFGNode * getGlobalICFGNode() const
Definition ICFG.h:230
FunEntryICFGNode * getFunEntryBlock(const FunObjVar *fun)
Get/Add a function entry node.
Definition ICFG.h:248
SVFLoopVec & getSVFLoops(const ICFGNode *node)
Get loops where a node resides.
Definition ICFG.h:126
NodeID getId() const
Get ID.
Definition SVFValue.h:158
for isBitcode
Definition BasicTypes.h:68
u32_t NodeID
Definition GeneralType.h:56
llvm::IRBuilder IRBuilder
Definition BasicTypes.h:74
signed s32_t
Definition GeneralType.h:48
signed long long s64_t
Definition GeneralType.h:50
GenericGraph< ICFGNode, ICFGEdge > GenericICFGTy
Definition ICFG.h:46