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

source code of llvm/include/llvm/IR/CFG.h