Static Value-Flow Analysis
Loading...
Searching...
No Matches
BasicBlockG.h
Go to the documentation of this file.
1//===- BasicBlockG.h -- BasicBlock node------------------------------------------------//
2//
3// SVF: Static Value-Flow Analysis
4//
5// Copyright (C) <2013-2025> <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 * ICFGNode.h
25 *
26 * Created on: 23 Jan, 2025
27 * Author: Jiawei, Xiao
28 */
29
30#ifndef BASICBLOCKGRAPH_H_
31#define BASICBLOCKGRAPH_H_
32#include "GenericGraph.h"
33#include <sstream>
34#include <algorithm>
35
36
37namespace SVF
38{
39class SVFBasicBlock;
40class BasicBlockEdge;
41class ICFGNode;
42class FunObjVar;
43
46{
47
48public:
55
57
59 {
60 o << edge.toString();
61 return o;
62 }
64
65 virtual const std::string toString() const;
66};
67
68
71{
72 friend class LLVMModuleSet;
73 friend class SVFIRBuilder;
74 friend class FunObjVar;
75 friend class ICFGBuilder;
76 friend class ICFG;
77
78public:
79 typedef std::vector<const ICFGNode*>::const_iterator const_iterator;
80 std::vector<const SVFBasicBlock*> succBBs;
81 std::vector<const SVFBasicBlock*> predBBs;
82
83private:
84 std::vector<const ICFGNode*> allICFGNodes;
85 const FunObjVar* fun;
86
87
88
89protected:
91
92 inline void addICFGNode(const ICFGNode* icfgNode)
93 {
95 icfgNode) == getICFGNodeList().end() && "duplicated icfgnode");
96 allICFGNodes.push_back(icfgNode);
97 }
98
100
101public:
107 SVFBasicBlock() = delete;
109 {
110
111 }
112
113 static inline bool classof(const SVFValue* node)
114 {
115 return node->getNodeKind() == SVFValue::BasicBlockKd;
116 }
117
118 static inline bool classof(const SVFBasicBlock* node)
119 {
120 return true;
121 }
122
125 {
126 o << node.toString();
127 return o;
128 }
130
131
132 inline const std::vector<const ICFGNode*>& getICFGNodeList() const
133 {
134 return allICFGNodes;
135 }
136
137 inline const_iterator begin() const
138 {
139 return allICFGNodes.begin();
140 }
141
142 inline const_iterator end() const
143 {
144 return allICFGNodes.end();
145 }
146
147
148 inline void setFun(const FunObjVar* f)
149 {
150 fun = f;
151 }
152
154 {
155 // check if the edge already exists
156 for (auto edge: this->getOutEdges())
157 {
158 if (edge->getDstNode() == succ2)
159 return;
160 }
161
162 SVFBasicBlock* succ = const_cast<SVFBasicBlock*>(succ2);
164 this->addOutgoingEdge(edge);
165 succ->addIncomingEdge(edge);
166 this->succBBs.push_back(succ);
167 succ->predBBs.push_back(this);
168 }
169
171 {
172 // check if the edge already exists
173 for (auto edge: this->getInEdges())
174 {
175 if (edge->getSrcNode() == pred2)
176 return;
177 }
178 SVFBasicBlock* pred = const_cast<SVFBasicBlock*>(pred2);
180 this->addIncomingEdge(edge);
181 pred->addOutgoingEdge(edge);
182 this->predBBs.push_back(pred);
183 pred->succBBs.push_back(this);
184 }
185
186 inline const FunObjVar* getParent() const
187 {
188 assert(fun && "Function is null?");
189 return fun;
190 }
191
192 inline const FunObjVar* getFunction() const
193 {
194 assert(fun && "Function is null?");
195 return fun;
196 }
197
198 inline const ICFGNode* front() const
199 {
200 assert(!allICFGNodes.empty() && "bb empty?");
201 return allICFGNodes.front();
202 }
203
204 inline const ICFGNode* back() const
205 {
206 assert(!allICFGNodes.empty() && "bb empty?");
207 return allICFGNodes.back();
208 }
209
210 inline std::vector<const SVFBasicBlock*> getSuccessors() const
211 {
212 std::vector<const SVFBasicBlock*> res;
213 for (auto edge : this->getOutEdges())
214 {
215 res.push_back(edge->getDstNode());
216 }
217 return res;
218 }
219
220 inline std::vector<const SVFBasicBlock*> getPredecessors() const
221 {
222 std::vector<const SVFBasicBlock*> res;
223 for (auto edge : this->getInEdges())
224 {
225 res.push_back(edge->getSrcNode());
226 }
227 return res;
228 }
230 {
231 return this->getOutEdges().size();
232 }
234 {
235 u32_t i = 0;
236 for (const SVFBasicBlock* SuccBB: succBBs)
237 {
238 if (SuccBB == Succ)
239 return i;
240 i++;
241 }
242 assert(false && "Didn't find successor edge?");
243 return 0;
244 }
246 {
247 u32_t i = 0;
248 for (const SVFBasicBlock* SuccBB: succBBs)
249 {
250 if (SuccBB == Succ)
251 return i;
252 i++;
253 }
254 assert(false && "Didn't find successor edge?");
255 return 0;
256
257 }
259 {
260 u32_t pos = 0;
261 for (const SVFBasicBlock* PredBB : succbb->getPredecessors())
262 {
263 if(PredBB == this)
264 return pos;
265 ++pos;
266 }
267 assert(false && "Didn't find predecessor edge?");
268 return pos;
269 }
271 {
272 u32_t pos = 0;
273 for (const SVFBasicBlock* PredBB : succbb->getPredecessors())
274 {
275 if(PredBB == this)
276 return pos;
277 ++pos;
278 }
279 assert(false && "Didn't find predecessor edge?");
280 return pos;
281 }
282
283 const std::string toString() const;
284
285};
286
287
288
291{
292private:
293 NodeID id{0};
294public:
297 {
298
299 }
300
301 SVFBasicBlock* addBasicBlock(const std::string& bbname)
302 {
303 id++;
304 SVFBasicBlock* bb = new SVFBasicBlock(id, nullptr);
305 addGNode(id, bb);
306 bb->setName(bbname);
307 return bb;
308 }
309
310};
311}
312
313#endif
friend OutStream & operator<<(OutStream &o, const BasicBlockEdge &edge)
Overloading operator << for dumping ICFG node ID.
Definition BasicBlockG.h:58
BasicBlockEdge(SVFBasicBlock *s, SVFBasicBlock *d)
Constructor.
Definition BasicBlockG.h:50
virtual const std::string toString() const
~BasicBlockEdge()
Destructor.
Definition BasicBlockG.h:54
SVFBasicBlock * addBasicBlock(const std::string &bbname)
BasicBlockGraph()
Constructor.
void addGNode(NodeID id, NodeType *node)
Add a Node.
const GEdgeSetTy & getOutEdges() const
const GEdgeSetTy & getInEdges() const
bool addIncomingEdge(EdgeType *inEdge)
Add incoming and outgoing edges.
bool addOutgoingEdge(EdgeType *outEdge)
static bool classof(const SVFValue *node)
const FunObjVar * fun
Definition BasicBlockG.h:85
u32_t getBBSuccessorPos(const SVFBasicBlock *Succ) const
const FunObjVar * getParent() const
SVFBasicBlock(NodeID id, const FunObjVar *f)
Constructor without name.
void setFun(const FunObjVar *f)
void addPredBasicBlock(const SVFBasicBlock *pred2)
std::vector< const SVFBasicBlock * > getPredecessors() const
const std::vector< const ICFGNode * > & getICFGNodeList() const
const FunObjVar * getFunction() const
const std::string toString() const
void addSuccBasicBlock(const SVFBasicBlock *succ2)
void addICFGNode(const ICFGNode *icfgNode)
Function where this BasicBlock is.
Definition BasicBlockG.h:92
friend OutStream & operator<<(OutStream &o, const SVFBasicBlock &node)
const ICFGNode * front() const
std::vector< const SVFBasicBlock * > succBBs
Definition BasicBlockG.h:80
u32_t getBBPredecessorPos(const SVFBasicBlock *succbb)
u32_t getBBPredecessorPos(const SVFBasicBlock *succbb) const
std::vector< constICFGNode * >::const_iterator const_iterator
Definition BasicBlockG.h:79
std::vector< const ICFGNode * > allICFGNodes
all ICFGNodes in this BasicBlock
Definition BasicBlockG.h:84
static bool classof(const SVFBasicBlock *node)
const_iterator end() const
const_iterator begin() const
u32_t getBBSuccessorPos(const SVFBasicBlock *Succ)
SVFBasicBlock()=delete
u32_t getNumSuccessors() const
std::vector< const SVFBasicBlock * > predBBs
Definition BasicBlockG.h:81
const ICFGNode * back() const
std::vector< const SVFBasicBlock * > getSuccessors() const
GNodeK getNodeKind() const
Get node kind.
Definition SVFValue.h:166
NodeID id
Node ID.
Definition SVFValue.h:205
virtual void setName(const std::string &nameInfo)
Definition SVFValue.h:176
for isBitcode
Definition BasicTypes.h:68
u32_t NodeID
Definition GeneralType.h:56
std::ostream OutStream
Definition GeneralType.h:46
GenericNode< SVFBasicBlock, BasicBlockEdge > GenericBasicBlockNodeTy
Definition BasicBlockG.h:69
llvm::IRBuilder IRBuilder
Definition BasicTypes.h:74
GenericEdge< SVFBasicBlock > GenericBasicBlockEdgeTy
Definition BasicBlockG.h:44
unsigned u32_t
Definition GeneralType.h:47
GenericGraph< SVFBasicBlock, BasicBlockEdge > GenericBasicBlockGraphTy