LLVM 22.0.0git
CFG.h
Go to the documentation of this file.
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
23#include "llvm/ADT/iterator.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
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:
52 USE_iterator It;
53
55 // Loop to ignore non-terminator uses (for example BlockAddresses).
56 while (!It.atEnd()) {
57 if (auto *Inst = dyn_cast<Instruction>(*It)) {
58 assert(Inst->isTerminator() && "BasicBlock used in non-terminator");
59 break;
60 }
61
62 ++It;
63 }
64 }
65
66public:
67 PredIterator() = default;
68 explicit inline PredIterator(Ptr *bb) : It(bb->user_begin()) {
70 }
71 inline PredIterator(Ptr *bb, bool) : It(bb->user_end()) {}
72
73 inline bool operator==(const Self& x) const { return It == x.It; }
74 inline bool operator!=(const Self& x) const { return !operator==(x); }
75
76 inline reference operator*() const {
77 assert(!It.atEnd() && "pred_iterator out of range!");
78 return cast<Instruction>(*It)->getParent();
79 }
80 inline pointer *operator->() const { return &operator*(); }
81
82 inline Self& operator++() { // Preincrement
83 assert(!It.atEnd() && "pred_iterator out of range!");
85 return *this;
86 }
87
88 inline Self operator++(int) { // Postincrement
89 Self tmp = *this; ++*this; return tmp;
90 }
91
92 /// getOperandNo - Return the operand number in the predecessor's
93 /// terminator of the successor.
94 unsigned getOperandNo() const {
95 return It.getOperandNo();
96 }
97
98 /// getUse - Return the operand Use in the predecessor's terminator
99 /// of the successor.
100 Use &getUse() const {
101 return It.getUse();
102 }
103};
104
110
113 return const_pred_iterator(BB);
114}
115inline pred_iterator pred_end(BasicBlock *BB) { return pred_iterator(BB, true);}
117 return const_pred_iterator(BB, true);
118}
119inline bool pred_empty(const BasicBlock *BB) {
120 return pred_begin(BB) == pred_end(BB);
121}
122/// Get the number of predecessors of \p BB. This is a linear time operation.
123/// Use \ref BasicBlock::hasNPredecessors() or hasNPredecessorsOrMore if able.
124inline unsigned pred_size(const BasicBlock *BB) {
125 return std::distance(pred_begin(BB), pred_end(BB));
126}
128 return pred_range(pred_begin(BB), pred_end(BB));
129}
131 return const_pred_range(pred_begin(BB), pred_end(BB));
132}
133
134//===----------------------------------------------------------------------===//
135// Instruction and BasicBlock succ_iterator helpers
136//===----------------------------------------------------------------------===//
137
138template <class InstructionT, class BlockT>
140 : public iterator_facade_base<SuccIterator<InstructionT, BlockT>,
141 std::random_access_iterator_tag, BlockT, int,
142 BlockT *, BlockT *> {
143public:
144 using value_type = BlockT *;
145 using difference_type = std::ptrdiff_t;
146 using pointer = BlockT *;
147 using reference = BlockT *;
148
149private:
150 InstructionT *Inst;
151 int Idx;
153
154 inline bool index_is_valid(int Idx) {
155 // Note that we specially support the index of zero being valid even in the
156 // face of a null instruction.
157 return Idx >= 0 && (Idx == 0 || Idx <= (int)Inst->getNumSuccessors());
158 }
159
160 /// Proxy object to allow write access in operator[]
161 class SuccessorProxy {
162 Self It;
163
164 public:
165 explicit SuccessorProxy(const Self &It) : It(It) {}
166
167 SuccessorProxy(const SuccessorProxy &) = default;
168
169 SuccessorProxy &operator=(SuccessorProxy RHS) {
170 *this = reference(RHS);
171 return *this;
172 }
173
174 SuccessorProxy &operator=(reference RHS) {
175 It.Inst->setSuccessor(It.Idx, RHS);
176 return *this;
177 }
178
179 operator reference() const { return *It; }
180 };
181
182public:
183 // begin iterator
184 explicit inline SuccIterator(InstructionT *Inst) : Inst(Inst), Idx(0) {}
185 // end iterator
186 inline SuccIterator(InstructionT *Inst, bool) : Inst(Inst) {
187 if (Inst)
188 Idx = Inst->getNumSuccessors();
189 else
190 // Inst == NULL happens, if a basic block is not fully constructed and
191 // consequently getTerminator() returns NULL. In this case we construct
192 // a SuccIterator which describes a basic block that has zero
193 // successors.
194 // Defining SuccIterator for incomplete and malformed CFGs is especially
195 // useful for debugging.
196 Idx = 0;
197 }
198
199 /// This is used to interface between code that wants to
200 /// operate on terminator instructions directly.
201 int getSuccessorIndex() const { return Idx; }
202
203 inline bool operator==(const Self &x) const { return Idx == x.Idx; }
204
205 inline BlockT *operator*() const { return Inst->getSuccessor(Idx); }
206
207 // We use the basic block pointer directly for operator->.
208 inline BlockT *operator->() const { return operator*(); }
209
210 inline bool operator<(const Self &RHS) const {
211 assert(Inst == RHS.Inst && "Cannot compare iterators of different blocks!");
212 return Idx < RHS.Idx;
213 }
214
215 int operator-(const Self &RHS) const {
216 assert(Inst == RHS.Inst && "Cannot compare iterators of different blocks!");
217 return Idx - RHS.Idx;
218 }
219
220 inline Self &operator+=(int RHS) {
221 int NewIdx = Idx + RHS;
222 assert(index_is_valid(NewIdx) && "Iterator index out of bound");
223 Idx = NewIdx;
224 return *this;
225 }
226
227 inline Self &operator-=(int RHS) { return operator+=(-RHS); }
228
229 // Specially implement the [] operation using a proxy object to support
230 // assignment.
231 inline SuccessorProxy operator[](int Offset) {
232 Self TmpIt = *this;
233 TmpIt += Offset;
234 return SuccessorProxy(TmpIt);
235 }
236
237 /// Get the source BlockT of this iterator.
238 inline BlockT *getSource() {
239 assert(Inst && "Source not available, if basic block was malformed");
240 return Inst->getParent();
241 }
242};
243
248
255 return const_succ_iterator(I, true);
256}
257inline bool succ_empty(const Instruction *I) {
258 return succ_begin(I) == succ_end(I);
259}
260inline unsigned succ_size(const Instruction *I) {
261 return std::distance(succ_begin(I), succ_end(I));
262}
269
271 return succ_iterator(BB->getTerminator());
272}
277 return succ_iterator(BB->getTerminator(), true);
278}
280 return const_succ_iterator(BB->getTerminator(), true);
281}
282inline bool succ_empty(const BasicBlock *BB) {
283 return succ_begin(BB) == succ_end(BB);
284}
285inline unsigned succ_size(const BasicBlock *BB) {
286 return std::distance(succ_begin(BB), succ_end(BB));
287}
289 return succ_range(succ_begin(BB), succ_end(BB));
290}
292 return const_succ_range(succ_begin(BB), succ_end(BB));
293}
294
295//===--------------------------------------------------------------------===//
296// GraphTraits specializations for basic block graphs (CFGs)
297//===--------------------------------------------------------------------===//
298
299// Provide specializations of GraphTraits to be able to treat a function as a
300// graph of basic blocks...
301
302template <> struct GraphTraits<BasicBlock*> {
305
306 static NodeRef getEntryNode(BasicBlock *BB) { return BB; }
309
310 static unsigned getNumber(const BasicBlock *BB) { return BB->getNumber(); }
311};
312
314 "GraphTraits getNumber() not detected");
315
316template <> struct GraphTraits<const BasicBlock*> {
317 using NodeRef = const BasicBlock *;
319
320 static NodeRef getEntryNode(const BasicBlock *BB) { return BB; }
321
324
325 static unsigned getNumber(const BasicBlock *BB) { return BB->getNumber(); }
326};
327
329 "GraphTraits getNumber() not detected");
330
331// Provide specializations of GraphTraits to be able to treat a function as a
332// graph of basic blocks... and to walk it in inverse order. Inverse order for
333// a function is considered to be when traversing the predecessor edges of a BB
334// instead of the successor edges.
335//
336template <> struct GraphTraits<Inverse<BasicBlock*>> {
339
340 static NodeRef getEntryNode(Inverse<BasicBlock *> G) { return G.Graph; }
343
344 static unsigned getNumber(const BasicBlock *BB) { return BB->getNumber(); }
345};
346
348 "GraphTraits getNumber() not detected");
349
350template <> struct GraphTraits<Inverse<const BasicBlock*>> {
351 using NodeRef = const BasicBlock *;
353
357
358 static unsigned getNumber(const BasicBlock *BB) { return BB->getNumber(); }
359};
360
362 "GraphTraits getNumber() not detected");
363
364//===--------------------------------------------------------------------===//
365// GraphTraits specializations for function basic block graphs (CFGs)
366//===--------------------------------------------------------------------===//
367
368// Provide specializations of GraphTraits to be able to treat a function as a
369// graph of basic blocks... these are the same as the basic block iterators,
370// except that the root node is implicitly the first node of the function.
371//
372template <> struct GraphTraits<Function*> : public GraphTraits<BasicBlock*> {
373 static NodeRef getEntryNode(Function *F) { return &F->getEntryBlock(); }
374
375 // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
377
379 return nodes_iterator(F->begin());
380 }
381
383 return nodes_iterator(F->end());
384 }
385
386 static size_t size(Function *F) { return F->size(); }
387
388 static unsigned getMaxNumber(const Function *F) {
389 return F->getMaxBlockNumber();
390 }
391 static unsigned getNumberEpoch(const Function *F) {
392 return F->getBlockNumberEpoch();
393 }
394};
395template <> struct GraphTraits<const Function*> :
397 static NodeRef getEntryNode(const Function *F) { return &F->getEntryBlock(); }
398
399 // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
401
403 return nodes_iterator(F->begin());
404 }
405
407 return nodes_iterator(F->end());
408 }
409
410 static size_t size(const Function *F) { return F->size(); }
411
412 static unsigned getMaxNumber(const Function *F) {
413 return F->getMaxBlockNumber();
414 }
415 static unsigned getNumberEpoch(const Function *F) {
416 return F->getBlockNumberEpoch();
417 }
418};
419
420// Provide specializations of GraphTraits to be able to treat a function as a
421// graph of basic blocks... and to walk it in inverse order. Inverse order for
422// a function is considered to be when traversing the predecessor edges of a BB
423// instead of the successor edges.
424//
425template <> struct GraphTraits<Inverse<Function*>> :
428 return &G.Graph->getEntryBlock();
429 }
430
431 static unsigned getMaxNumber(const Function *F) {
432 return F->getMaxBlockNumber();
433 }
434 static unsigned getNumberEpoch(const Function *F) {
435 return F->getBlockNumberEpoch();
436 }
437};
438template <> struct GraphTraits<Inverse<const Function*>> :
441 return &G.Graph->getEntryBlock();
442 }
443
444 static unsigned getMaxNumber(const Function *F) {
445 return F->getMaxBlockNumber();
446 }
447 static unsigned getNumberEpoch(const Function *F) {
448 return F->getBlockNumberEpoch();
449 }
450};
451
452} // end namespace llvm
453
454#endif // LLVM_IR_CFG_H
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
aarch64 promote const
This file defines the little GraphTraits<X> template class that should be specialized by classes that...
#define F(x, y, z)
Definition MD5.cpp:55
#define I(x, y, z)
Definition MD5.cpp:58
#define G(x, y, z)
Definition MD5.cpp:56
Value * RHS
LLVM Basic Block Representation.
Definition BasicBlock.h:62
unsigned getNumber() const
Definition BasicBlock.h:95
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition BasicBlock.h:233
bool operator==(const Self &x) const
Definition CFG.h:73
Self & operator++()
Definition CFG.h:82
PredIterator(Ptr *bb)
Definition CFG.h:68
void advancePastNonTerminators()
Definition CFG.h:54
PredIterator()=default
Self operator++(int)
Definition CFG.h:88
PredIterator(Ptr *bb, bool)
Definition CFG.h:71
bool operator!=(const Self &x) const
Definition CFG.h:74
Ptr ** pointer
Definition CFG.h:47
std::forward_iterator_tag iterator_category
Definition CFG.h:44
reference operator*() const
Definition CFG.h:76
PredIterator< Ptr, USE_iterator > Self
Definition CFG.h:51
std::ptrdiff_t difference_type
Definition CFG.h:46
pointer * operator->() const
Definition CFG.h:80
unsigned getOperandNo() const
getOperandNo - Return the operand number in the predecessor's terminator of the successor.
Definition CFG.h:94
Ptr * value_type
Definition CFG.h:45
Use & getUse() const
getUse - Return the operand Use in the predecessor's terminator of the successor.
Definition CFG.h:100
Ptr * reference
Definition CFG.h:48
std::ptrdiff_t difference_type
Definition CFG.h:145
BlockT * value_type
Definition CFG.h:144
bool operator==(const Self &x) const
Definition CFG.h:203
SuccIterator(InstructionT *Inst, bool)
Definition CFG.h:186
Self & operator-=(int RHS)
Definition CFG.h:227
BlockT * reference
Definition CFG.h:147
int getSuccessorIndex() const
This is used to interface between code that wants to operate on terminator instructions directly.
Definition CFG.h:201
BlockT * operator->() const
Definition CFG.h:208
bool operator<(const Self &RHS) const
Definition CFG.h:210
BlockT * operator*() const
Definition CFG.h:205
BlockT * getSource()
Get the source BlockT of this iterator.
Definition CFG.h:238
SuccessorProxy operator[](int Offset)
Definition CFG.h:231
BlockT * pointer
Definition CFG.h:146
Self & operator+=(int RHS)
Definition CFG.h:220
int operator-(const Self &RHS) const
Definition CFG.h:215
SuccIterator(InstructionT *Inst)
Definition CFG.h:184
A Use represents the edge between a Value definition and its users.
Definition Use.h:35
CRTP base class which implements the entire standard iterator facade in terms of a minimal subset of ...
Definition iterator.h:80
A range adaptor for a pair of iterators.
This provides a very simple, boring adaptor for a begin and end iterator into a range type.
This is an optimization pass for GlobalISel generic memory operations.
@ Offset
Definition DWP.cpp:477
bool succ_empty(const Instruction *I)
Definition CFG.h:257
iterator_range< pred_iterator > pred_range
Definition CFG.h:108
iterator_range< succ_iterator > succ_range
Definition CFG.h:246
auto pred_end(const MachineBasicBlock *BB)
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:643
auto successors(const MachineBasicBlock *BB)
constexpr bool GraphHasNodeNumbers
Indicate whether a GraphTraits<NodeT>::getNumber() is supported.
iterator_range< const_pred_iterator > const_pred_range
Definition CFG.h:109
auto pred_size(const MachineBasicBlock *BB)
PredIterator< const BasicBlock, Value::const_user_iterator > const_pred_iterator
Definition CFG.h:106
auto succ_size(const MachineBasicBlock *BB)
RNSuccIterator< NodeRef, BlockT, RegionT > succ_begin(NodeRef Node)
RNSuccIterator< NodeRef, BlockT, RegionT > succ_end(NodeRef Node)
PredIterator< BasicBlock, Value::user_iterator > pred_iterator
Definition CFG.h:105
auto pred_begin(const MachineBasicBlock *BB)
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:559
auto predecessors(const MachineBasicBlock *BB)
SuccIterator< Instruction, BasicBlock > succ_iterator
Definition CFG.h:244
bool pred_empty(const BasicBlock *BB)
Definition CFG.h:119
SuccIterator< const Instruction, const BasicBlock > const_succ_iterator
Definition CFG.h:245
iterator_range< const_succ_iterator > const_succ_range
Definition CFG.h:247
#define N
static NodeRef getEntryNode(BasicBlock *BB)
Definition CFG.h:306
succ_iterator ChildIteratorType
Definition CFG.h:304
static ChildIteratorType child_begin(NodeRef N)
Definition CFG.h:307
static unsigned getNumber(const BasicBlock *BB)
Definition CFG.h:310
static ChildIteratorType child_end(NodeRef N)
Definition CFG.h:308
static unsigned getMaxNumber(const Function *F)
Definition CFG.h:388
static nodes_iterator nodes_begin(Function *F)
Definition CFG.h:378
static unsigned getNumberEpoch(const Function *F)
Definition CFG.h:391
static nodes_iterator nodes_end(Function *F)
Definition CFG.h:382
static size_t size(Function *F)
Definition CFG.h:386
static NodeRef getEntryNode(Function *F)
Definition CFG.h:373
pointer_iterator< Function::iterator > nodes_iterator
Definition CFG.h:376
static ChildIteratorType child_begin(NodeRef N)
Definition CFG.h:341
static unsigned getNumber(const BasicBlock *BB)
Definition CFG.h:344
static ChildIteratorType child_end(NodeRef N)
Definition CFG.h:342
static NodeRef getEntryNode(Inverse< BasicBlock * > G)
Definition CFG.h:340
static unsigned getNumberEpoch(const Function *F)
Definition CFG.h:434
static unsigned getMaxNumber(const Function *F)
Definition CFG.h:431
static NodeRef getEntryNode(Inverse< Function * > G)
Definition CFG.h:427
static ChildIteratorType child_end(NodeRef N)
Definition CFG.h:356
static NodeRef getEntryNode(Inverse< const BasicBlock * > G)
Definition CFG.h:354
static ChildIteratorType child_begin(NodeRef N)
Definition CFG.h:355
static unsigned getNumber(const BasicBlock *BB)
Definition CFG.h:358
static unsigned getMaxNumber(const Function *F)
Definition CFG.h:444
static NodeRef getEntryNode(Inverse< const Function * > G)
Definition CFG.h:440
static unsigned getNumberEpoch(const Function *F)
Definition CFG.h:447
static ChildIteratorType child_begin(NodeRef N)
Definition CFG.h:322
static unsigned getNumber(const BasicBlock *BB)
Definition CFG.h:325
static NodeRef getEntryNode(const BasicBlock *BB)
Definition CFG.h:320
const_succ_iterator ChildIteratorType
Definition CFG.h:318
static ChildIteratorType child_end(NodeRef N)
Definition CFG.h:323
static size_t size(const Function *F)
Definition CFG.h:410
static nodes_iterator nodes_begin(const Function *F)
Definition CFG.h:402
static NodeRef getEntryNode(const Function *F)
Definition CFG.h:397
static unsigned getNumberEpoch(const Function *F)
Definition CFG.h:415
static unsigned getMaxNumber(const Function *F)
Definition CFG.h:412
static nodes_iterator nodes_end(const Function *F)
Definition CFG.h:406
pointer_iterator< Function::const_iterator > nodes_iterator
Definition CFG.h:400
typename Function *::UnknownGraphTypeError NodeRef
Definition GraphTraits.h:95