1 //===- CFG.h ----------------------------------------------------*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 /// \file
9 ///
10 /// This file provides various utilities for inspecting and working with the
11 /// control flow graph in LLVM IR. This includes generic facilities for
12 /// iterating successors and predecessors of basic blocks, the successors of
13 /// specific terminator instructions, etc. It also defines specializations of
14 /// GraphTraits that allow Function and BasicBlock graphs to be treated as
15 /// proper graphs for generic algorithms.
16 ///
17 //===----------------------------------------------------------------------===//
18
19 #ifndef LLVM_IR_CFG_H
20 #define LLVM_IR_CFG_H
21
22 #include "llvm/ADT/GraphTraits.h"
23 #include "llvm/ADT/iterator.h"
24 #include "llvm/ADT/iterator_range.h"
25 #include "llvm/IR/Function.h"
26 #include "llvm/IR/Value.h"
27 #include "llvm/Support/Casting.h"
28 #include <cassert>
29 #include <cstddef>
30 #include <iterator>
31
32 namespace llvm {
33
34 class BasicBlock;
35 class Instruction;
36 class Use;
37
38 //===----------------------------------------------------------------------===//
39 // BasicBlock pred_iterator definition
40 //===----------------------------------------------------------------------===//
41
42 template <class Ptr, class USE_iterator> // Predecessor Iterator
43 class PredIterator : public std::iterator<std::forward_iterator_tag,
44 Ptr, ptrdiff_t, Ptr*, Ptr*> {
45 using super =
46 std::iterator<std::forward_iterator_tag, Ptr, ptrdiff_t, Ptr*, Ptr*>;
47 using Self = PredIterator<Ptr, USE_iterator>;
48 USE_iterator It;
49
advancePastNonTerminators()50 inline void advancePastNonTerminators() {
51 // Loop to ignore non-terminator uses (for example BlockAddresses).
52 while (!It.atEnd()) {
53 if (auto *Inst = dyn_cast<Instruction>(*It))
54 if (Inst->isTerminator())
55 break;
56
57 ++It;
58 }
59 }
60
61 public:
62 using pointer = typename super::pointer;
63 using reference = typename super::reference;
64
65 PredIterator() = default;
PredIterator(Ptr * bb)66 explicit inline PredIterator(Ptr *bb) : It(bb->user_begin()) {
67 advancePastNonTerminators();
68 }
PredIterator(Ptr * bb,bool)69 inline PredIterator(Ptr *bb, bool) : It(bb->user_end()) {}
70
71 inline bool operator==(const Self& x) const { return It == x.It; }
72 inline bool operator!=(const Self& x) const { return !operator==(x); }
73
74 inline reference operator*() const {
75 assert(!It.atEnd() && "pred_iterator out of range!");
76 return cast<Instruction>(*It)->getParent();
77 }
78 inline pointer *operator->() const { return &operator*(); }
79
80 inline Self& operator++() { // Preincrement
81 assert(!It.atEnd() && "pred_iterator out of range!");
82 ++It; advancePastNonTerminators();
83 return *this;
84 }
85
86 inline Self operator++(int) { // Postincrement
87 Self tmp = *this; ++*this; return tmp;
88 }
89
90 /// getOperandNo - Return the operand number in the predecessor's
91 /// terminator of the successor.
getOperandNo()92 unsigned getOperandNo() const {
93 return It.getOperandNo();
94 }
95
96 /// getUse - Return the operand Use in the predecessor's terminator
97 /// of the successor.
getUse()98 Use &getUse() const {
99 return It.getUse();
100 }
101 };
102
103 using pred_iterator = PredIterator<BasicBlock, Value::user_iterator>;
104 using const_pred_iterator =
105 PredIterator<const BasicBlock, Value::const_user_iterator>;
106 using pred_range = iterator_range<pred_iterator>;
107 using const_pred_range = iterator_range<const_pred_iterator>;
108
pred_begin(BasicBlock * BB)109 inline pred_iterator pred_begin(BasicBlock *BB) { return pred_iterator(BB); }
pred_begin(const BasicBlock * BB)110 inline const_pred_iterator pred_begin(const BasicBlock *BB) {
111 return const_pred_iterator(BB);
112 }
pred_end(BasicBlock * BB)113 inline pred_iterator pred_end(BasicBlock *BB) { return pred_iterator(BB, true);}
pred_end(const BasicBlock * BB)114 inline const_pred_iterator pred_end(const BasicBlock *BB) {
115 return const_pred_iterator(BB, true);
116 }
pred_empty(const BasicBlock * BB)117 inline bool pred_empty(const BasicBlock *BB) {
118 return pred_begin(BB) == pred_end(BB);
119 }
120 /// Get the number of predecessors of \p BB. This is a linear time operation.
121 /// Use \ref BasicBlock::hasNPredecessors() or hasNPredecessorsOrMore if able.
pred_size(const BasicBlock * BB)122 inline unsigned pred_size(const BasicBlock *BB) {
123 return std::distance(pred_begin(BB), pred_end(BB));
124 }
predecessors(BasicBlock * BB)125 inline pred_range predecessors(BasicBlock *BB) {
126 return pred_range(pred_begin(BB), pred_end(BB));
127 }
predecessors(const BasicBlock * BB)128 inline const_pred_range predecessors(const BasicBlock *BB) {
129 return const_pred_range(pred_begin(BB), pred_end(BB));
130 }
131
132 //===----------------------------------------------------------------------===//
133 // Instruction and BasicBlock succ_iterator helpers
134 //===----------------------------------------------------------------------===//
135
136 template <class InstructionT, class BlockT>
137 class SuccIterator
138 : public iterator_facade_base<SuccIterator<InstructionT, BlockT>,
139 std::random_access_iterator_tag, BlockT, int,
140 BlockT *, BlockT *> {
141 public:
142 using difference_type = int;
143 using pointer = BlockT *;
144 using reference = BlockT *;
145
146 private:
147 InstructionT *Inst;
148 int Idx;
149 using Self = SuccIterator<InstructionT, BlockT>;
150
index_is_valid(int Idx)151 inline bool index_is_valid(int Idx) {
152 // Note that we specially support the index of zero being valid even in the
153 // face of a null instruction.
154 return Idx >= 0 && (Idx == 0 || Idx <= (int)Inst->getNumSuccessors());
155 }
156
157 /// Proxy object to allow write access in operator[]
158 class SuccessorProxy {
159 Self It;
160
161 public:
SuccessorProxy(const Self & It)162 explicit SuccessorProxy(const Self &It) : It(It) {}
163
164 SuccessorProxy(const SuccessorProxy &) = default;
165
166 SuccessorProxy &operator=(SuccessorProxy RHS) {
167 *this = reference(RHS);
168 return *this;
169 }
170
171 SuccessorProxy &operator=(reference RHS) {
172 It.Inst->setSuccessor(It.Idx, RHS);
173 return *this;
174 }
175
reference()176 operator reference() const { return *It; }
177 };
178
179 public:
180 // begin iterator
SuccIterator(InstructionT * Inst)181 explicit inline SuccIterator(InstructionT *Inst) : Inst(Inst), Idx(0) {}
182 // end iterator
SuccIterator(InstructionT * Inst,bool)183 inline SuccIterator(InstructionT *Inst, bool) : Inst(Inst) {
184 if (Inst)
185 Idx = Inst->getNumSuccessors();
186 else
187 // Inst == NULL happens, if a basic block is not fully constructed and
188 // consequently getTerminator() returns NULL. In this case we construct
189 // a SuccIterator which describes a basic block that has zero
190 // successors.
191 // Defining SuccIterator for incomplete and malformed CFGs is especially
192 // useful for debugging.
193 Idx = 0;
194 }
195
196 /// This is used to interface between code that wants to
197 /// operate on terminator instructions directly.
getSuccessorIndex()198 int getSuccessorIndex() const { return Idx; }
199
200 inline bool operator==(const Self &x) const { return Idx == x.Idx; }
201
202 inline BlockT *operator*() const { return Inst->getSuccessor(Idx); }
203
204 // We use the basic block pointer directly for operator->.
205 inline BlockT *operator->() const { return operator*(); }
206
207 inline bool operator<(const Self &RHS) const {
208 assert(Inst == RHS.Inst && "Cannot compare iterators of different blocks!");
209 return Idx < RHS.Idx;
210 }
211
212 int operator-(const Self &RHS) const {
213 assert(Inst == RHS.Inst && "Cannot compare iterators of different blocks!");
214 return Idx - RHS.Idx;
215 }
216
217 inline Self &operator+=(int RHS) {
218 int NewIdx = Idx + RHS;
219 assert(index_is_valid(NewIdx) && "Iterator index out of bound");
220 Idx = NewIdx;
221 return *this;
222 }
223
224 inline Self &operator-=(int RHS) { return operator+=(-RHS); }
225
226 // Specially implement the [] operation using a proxy object to support
227 // assignment.
228 inline SuccessorProxy operator[](int Offset) {
229 Self TmpIt = *this;
230 TmpIt += Offset;
231 return SuccessorProxy(TmpIt);
232 }
233
234 /// Get the source BlockT of this iterator.
getSource()235 inline BlockT *getSource() {
236 assert(Inst && "Source not available, if basic block was malformed");
237 return Inst->getParent();
238 }
239 };
240
241 using succ_iterator = SuccIterator<Instruction, BasicBlock>;
242 using const_succ_iterator = SuccIterator<const Instruction, const BasicBlock>;
243 using succ_range = iterator_range<succ_iterator>;
244 using const_succ_range = iterator_range<const_succ_iterator>;
245
succ_begin(Instruction * I)246 inline succ_iterator succ_begin(Instruction *I) { return succ_iterator(I); }
succ_begin(const Instruction * I)247 inline const_succ_iterator succ_begin(const Instruction *I) {
248 return const_succ_iterator(I);
249 }
succ_end(Instruction * I)250 inline succ_iterator succ_end(Instruction *I) { return succ_iterator(I, true); }
succ_end(const Instruction * I)251 inline const_succ_iterator succ_end(const Instruction *I) {
252 return const_succ_iterator(I, true);
253 }
succ_empty(const Instruction * I)254 inline bool succ_empty(const Instruction *I) {
255 return succ_begin(I) == succ_end(I);
256 }
succ_size(const Instruction * I)257 inline unsigned succ_size(const Instruction *I) {
258 return std::distance(succ_begin(I), succ_end(I));
259 }
successors(Instruction * I)260 inline succ_range successors(Instruction *I) {
261 return succ_range(succ_begin(I), succ_end(I));
262 }
successors(const Instruction * I)263 inline const_succ_range successors(const Instruction *I) {
264 return const_succ_range(succ_begin(I), succ_end(I));
265 }
266
succ_begin(BasicBlock * BB)267 inline succ_iterator succ_begin(BasicBlock *BB) {
268 return succ_iterator(BB->getTerminator());
269 }
succ_begin(const BasicBlock * BB)270 inline const_succ_iterator succ_begin(const BasicBlock *BB) {
271 return const_succ_iterator(BB->getTerminator());
272 }
succ_end(BasicBlock * BB)273 inline succ_iterator succ_end(BasicBlock *BB) {
274 return succ_iterator(BB->getTerminator(), true);
275 }
succ_end(const BasicBlock * BB)276 inline const_succ_iterator succ_end(const BasicBlock *BB) {
277 return const_succ_iterator(BB->getTerminator(), true);
278 }
succ_empty(const BasicBlock * BB)279 inline bool succ_empty(const BasicBlock *BB) {
280 return succ_begin(BB) == succ_end(BB);
281 }
succ_size(const BasicBlock * BB)282 inline unsigned succ_size(const BasicBlock *BB) {
283 return std::distance(succ_begin(BB), succ_end(BB));
284 }
successors(BasicBlock * BB)285 inline succ_range successors(BasicBlock *BB) {
286 return succ_range(succ_begin(BB), succ_end(BB));
287 }
successors(const BasicBlock * BB)288 inline const_succ_range successors(const BasicBlock *BB) {
289 return const_succ_range(succ_begin(BB), succ_end(BB));
290 }
291
292 //===--------------------------------------------------------------------===//
293 // GraphTraits specializations for basic block graphs (CFGs)
294 //===--------------------------------------------------------------------===//
295
296 // Provide specializations of GraphTraits to be able to treat a function as a
297 // graph of basic blocks...
298
299 template <> struct GraphTraits<BasicBlock*> {
300 using NodeRef = BasicBlock *;
301 using ChildIteratorType = succ_iterator;
302
303 static NodeRef getEntryNode(BasicBlock *BB) { return BB; }
304 static ChildIteratorType child_begin(NodeRef N) { return succ_begin(N); }
305 static ChildIteratorType child_end(NodeRef N) { return succ_end(N); }
306 };
307
308 template <> struct GraphTraits<const BasicBlock*> {
309 using NodeRef = const BasicBlock *;
310 using ChildIteratorType = const_succ_iterator;
311
312 static NodeRef getEntryNode(const BasicBlock *BB) { return BB; }
313
314 static ChildIteratorType child_begin(NodeRef N) { return succ_begin(N); }
315 static ChildIteratorType child_end(NodeRef N) { return succ_end(N); }
316 };
317
318 // Provide specializations of GraphTraits to be able to treat a function as a
319 // graph of basic blocks... and to walk it in inverse order. Inverse order for
320 // a function is considered to be when traversing the predecessor edges of a BB
321 // instead of the successor edges.
322 //
323 template <> struct GraphTraits<Inverse<BasicBlock*>> {
324 using NodeRef = BasicBlock *;
325 using ChildIteratorType = pred_iterator;
326
327 static NodeRef getEntryNode(Inverse<BasicBlock *> G) { return G.Graph; }
328 static ChildIteratorType child_begin(NodeRef N) { return pred_begin(N); }
329 static ChildIteratorType child_end(NodeRef N) { return pred_end(N); }
330 };
331
332 template <> struct GraphTraits<Inverse<const BasicBlock*>> {
333 using NodeRef = const BasicBlock *;
334 using ChildIteratorType = const_pred_iterator;
335
336 static NodeRef getEntryNode(Inverse<const BasicBlock *> G) { return G.Graph; }
337 static ChildIteratorType child_begin(NodeRef N) { return pred_begin(N); }
338 static ChildIteratorType child_end(NodeRef N) { return pred_end(N); }
339 };
340
341 //===--------------------------------------------------------------------===//
342 // GraphTraits specializations for function basic block graphs (CFGs)
343 //===--------------------------------------------------------------------===//
344
345 // Provide specializations of GraphTraits to be able to treat a function as a
346 // graph of basic blocks... these are the same as the basic block iterators,
347 // except that the root node is implicitly the first node of the function.
348 //
349 template <> struct GraphTraits<Function*> : public GraphTraits<BasicBlock*> {
350 static NodeRef getEntryNode(Function *F) { return &F->getEntryBlock(); }
351
352 // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
353 using nodes_iterator = pointer_iterator<Function::iterator>;
354
355 static nodes_iterator nodes_begin(Function *F) {
356 return nodes_iterator(F->begin());
357 }
358
359 static nodes_iterator nodes_end(Function *F) {
360 return nodes_iterator(F->end());
361 }
362
363 static size_t size(Function *F) { return F->size(); }
364 };
365 template <> struct GraphTraits<const Function*> :
366 public GraphTraits<const BasicBlock*> {
367 static NodeRef getEntryNode(const Function *F) { return &F->getEntryBlock(); }
368
369 // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
370 using nodes_iterator = pointer_iterator<Function::const_iterator>;
371
372 static nodes_iterator nodes_begin(const Function *F) {
373 return nodes_iterator(F->begin());
374 }
375
376 static nodes_iterator nodes_end(const Function *F) {
377 return nodes_iterator(F->end());
378 }
379
380 static size_t size(const Function *F) { return F->size(); }
381 };
382
383 // Provide specializations of GraphTraits to be able to treat a function as a
384 // graph of basic blocks... and to walk it in inverse order. Inverse order for
385 // a function is considered to be when traversing the predecessor edges of a BB
386 // instead of the successor edges.
387 //
388 template <> struct GraphTraits<Inverse<Function*>> :
389 public GraphTraits<Inverse<BasicBlock*>> {
390 static NodeRef getEntryNode(Inverse<Function *> G) {
391 return &G.Graph->getEntryBlock();
392 }
393 };
394 template <> struct GraphTraits<Inverse<const Function*>> :
395 public GraphTraits<Inverse<const BasicBlock*>> {
396 static NodeRef getEntryNode(Inverse<const Function *> G) {
397 return &G.Graph->getEntryBlock();
398 }
399 };
400
401 } // end namespace llvm
402
403 #endif // LLVM_IR_CFG_H
404