LLVM 20.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 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()) {
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!");
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
109
112 return const_pred_iterator(BB);
113}
114inline pred_iterator pred_end(BasicBlock *BB) { return pred_iterator(BB, true);}
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(pred_begin(BB), pred_end(BB));
125}
127 return pred_range(pred_begin(BB), pred_end(BB));
128}
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>
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;
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); }
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
246
249 return const_succ_iterator(I);
250}
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(succ_begin(I), succ_end(I));
260}
262 return succ_range(succ_begin(I), succ_end(I));
263}
266}
267
269 return succ_iterator(BB->getTerminator());
270}
273}
275 return succ_iterator(BB->getTerminator(), true);
276}
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(succ_begin(BB), succ_end(BB));
285}
287 return succ_range(succ_begin(BB), succ_end(BB));
288}
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*> {
303
304 static NodeRef getEntryNode(BasicBlock *BB) { return BB; }
307
308 static unsigned getNumber(const BasicBlock *BB) { return BB->getNumber(); }
309};
310
311static_assert(GraphHasNodeNumbers<BasicBlock *>,
312 "GraphTraits getNumber() not detected");
313
314template <> struct GraphTraits<const BasicBlock*> {
315 using NodeRef = const BasicBlock *;
317
318 static NodeRef getEntryNode(const BasicBlock *BB) { return BB; }
319
322
323 static unsigned getNumber(const BasicBlock *BB) { return BB->getNumber(); }
324};
325
326static_assert(GraphHasNodeNumbers<const BasicBlock *>,
327 "GraphTraits getNumber() not detected");
328
329// Provide specializations of GraphTraits to be able to treat a function as a
330// graph of basic blocks... and to walk it in inverse order. Inverse order for
331// a function is considered to be when traversing the predecessor edges of a BB
332// instead of the successor edges.
333//
334template <> struct GraphTraits<Inverse<BasicBlock*>> {
337
338 static NodeRef getEntryNode(Inverse<BasicBlock *> G) { return G.Graph; }
341
342 static unsigned getNumber(const BasicBlock *BB) { return BB->getNumber(); }
343};
344
345static_assert(GraphHasNodeNumbers<Inverse<BasicBlock *>>,
346 "GraphTraits getNumber() not detected");
347
348template <> struct GraphTraits<Inverse<const BasicBlock*>> {
349 using NodeRef = const BasicBlock *;
351
355
356 static unsigned getNumber(const BasicBlock *BB) { return BB->getNumber(); }
357};
358
359static_assert(GraphHasNodeNumbers<Inverse<const BasicBlock *>>,
360 "GraphTraits getNumber() not detected");
361
362//===--------------------------------------------------------------------===//
363// GraphTraits specializations for function basic block graphs (CFGs)
364//===--------------------------------------------------------------------===//
365
366// Provide specializations of GraphTraits to be able to treat a function as a
367// graph of basic blocks... these are the same as the basic block iterators,
368// except that the root node is implicitly the first node of the function.
369//
370template <> struct GraphTraits<Function*> : public GraphTraits<BasicBlock*> {
371 static NodeRef getEntryNode(Function *F) { return &F->getEntryBlock(); }
372
373 // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
375
377 return nodes_iterator(F->begin());
378 }
379
381 return nodes_iterator(F->end());
382 }
383
384 static size_t size(Function *F) { return F->size(); }
385
386 static unsigned getMaxNumber(const Function *F) {
387 return F->getMaxBlockNumber();
388 }
389 static unsigned getNumberEpoch(const Function *F) {
390 return F->getBlockNumberEpoch();
391 }
392};
393template <> struct GraphTraits<const Function*> :
395 static NodeRef getEntryNode(const Function *F) { return &F->getEntryBlock(); }
396
397 // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
399
401 return nodes_iterator(F->begin());
402 }
403
405 return nodes_iterator(F->end());
406 }
407
408 static size_t size(const Function *F) { return F->size(); }
409
410 static unsigned getMaxNumber(const Function *F) {
411 return F->getMaxBlockNumber();
412 }
413 static unsigned getNumberEpoch(const Function *F) {
414 return F->getBlockNumberEpoch();
415 }
416};
417
418// Provide specializations of GraphTraits to be able to treat a function as a
419// graph of basic blocks... and to walk it in inverse order. Inverse order for
420// a function is considered to be when traversing the predecessor edges of a BB
421// instead of the successor edges.
422//
423template <> struct GraphTraits<Inverse<Function*>> :
426 return &G.Graph->getEntryBlock();
427 }
428
429 static unsigned getMaxNumber(const Function *F) {
430 return F->getMaxBlockNumber();
431 }
432 static unsigned getNumberEpoch(const Function *F) {
433 return F->getBlockNumberEpoch();
434 }
435};
436template <> struct GraphTraits<Inverse<const Function*>> :
439 return &G.Graph->getEntryBlock();
440 }
441
442 static unsigned getMaxNumber(const Function *F) {
443 return F->getMaxBlockNumber();
444 }
445 static unsigned getNumberEpoch(const Function *F) {
446 return F->getBlockNumberEpoch();
447 }
448};
449
450} // end namespace llvm
451
452#endif // LLVM_IR_CFG_H
aarch64 promote const
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
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
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Value * RHS
LLVM Basic Block Representation.
Definition: BasicBlock.h:61
unsigned getNumber() const
Definition: BasicBlock.h:104
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:239
bool operator==(const Self &x) const
Definition: CFG.h:72
Self & operator++()
Definition: CFG.h:81
Ptr * pointer
Definition: CFG.h:47
PredIterator(Ptr *bb)
Definition: CFG.h:67
void advancePastNonTerminators()
Definition: CFG.h:54
PredIterator()=default
Self operator++(int)
Definition: CFG.h:87
PredIterator(Ptr *bb, bool)
Definition: CFG.h:70
bool operator!=(const Self &x) const
Definition: CFG.h:73
USE_iterator It
Definition: CFG.h:52
std::forward_iterator_tag iterator_category
Definition: CFG.h:44
reference operator*() const
Definition: CFG.h:75
Ptr value_type
Definition: CFG.h:45
std::ptrdiff_t difference_type
Definition: CFG.h:46
pointer * operator->() const
Definition: CFG.h:79
unsigned getOperandNo() const
getOperandNo - Return the operand number in the predecessor's terminator of the successor.
Definition: CFG.h:93
Use & getUse() const
getUse - Return the operand Use in the predecessor's terminator of the successor.
Definition: CFG.h:99
Ptr * reference
Definition: CFG.h:48
bool operator==(const Self &x) const
Definition: CFG.h:201
SuccIterator(InstructionT *Inst, bool)
Definition: CFG.h:184
int difference_type
Definition: CFG.h:143
Self & operator-=(int RHS)
Definition: CFG.h:225
BlockT * reference
Definition: CFG.h:145
int getSuccessorIndex() const
This is used to interface between code that wants to operate on terminator instructions directly.
Definition: CFG.h:199
BlockT * operator->() const
Definition: CFG.h:206
bool operator<(const Self &RHS) const
Definition: CFG.h:208
BlockT * operator*() const
Definition: CFG.h:203
BlockT * getSource()
Get the source BlockT of this iterator.
Definition: CFG.h:236
SuccessorProxy operator[](int Offset)
Definition: CFG.h:229
BlockT * pointer
Definition: CFG.h:144
Self & operator+=(int RHS)
Definition: CFG.h:218
int operator-(const Self &RHS) const
Definition: CFG.h:213
SuccIterator(InstructionT *Inst)
Definition: CFG.h:182
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
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.
NodeAddr< UseNode * > Use
Definition: RDFGraph.h:385
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
pred_iterator pred_end(BasicBlock *BB)
Definition: CFG.h:114
@ Offset
Definition: DWP.cpp:480
bool succ_empty(const Instruction *I)
Definition: CFG.h:255
auto successors(const MachineBasicBlock *BB)
pred_iterator pred_begin(BasicBlock *BB)
Definition: CFG.h:110
SuccIterator< Instruction, BasicBlock > succ_iterator
Definition: CFG.h:242
iterator_range< succ_iterator > succ_range
Definition: CFG.h:244
iterator_range< const_succ_iterator > const_succ_range
Definition: CFG.h:245
iterator_range< pred_iterator > pred_range
Definition: CFG.h:107
RNSuccIterator< NodeRef, BlockT, RegionT > succ_begin(NodeRef Node)
RNSuccIterator< NodeRef, BlockT, RegionT > succ_end(NodeRef Node)
iterator_range< const_pred_iterator > const_pred_range
Definition: CFG.h:108
PredIterator< const BasicBlock, Value::const_user_iterator > const_pred_iterator
Definition: CFG.h:106
auto predecessors(const MachineBasicBlock *BB)
bool pred_empty(const BasicBlock *BB)
Definition: CFG.h:118
PredIterator< BasicBlock, Value::user_iterator > pred_iterator
Definition: CFG.h:104
unsigned succ_size(const MachineBasicBlock *BB)
unsigned pred_size(const MachineBasicBlock *BB)
SuccIterator< const Instruction, const BasicBlock > const_succ_iterator
Definition: CFG.h:243
#define N
static NodeRef getEntryNode(BasicBlock *BB)
Definition: CFG.h:304
static ChildIteratorType child_begin(NodeRef N)
Definition: CFG.h:305
static unsigned getNumber(const BasicBlock *BB)
Definition: CFG.h:308
static ChildIteratorType child_end(NodeRef N)
Definition: CFG.h:306
static unsigned getMaxNumber(const Function *F)
Definition: CFG.h:386
static nodes_iterator nodes_begin(Function *F)
Definition: CFG.h:376
static unsigned getNumberEpoch(const Function *F)
Definition: CFG.h:389
static nodes_iterator nodes_end(Function *F)
Definition: CFG.h:380
static size_t size(Function *F)
Definition: CFG.h:384
static NodeRef getEntryNode(Function *F)
Definition: CFG.h:371
static ChildIteratorType child_begin(NodeRef N)
Definition: CFG.h:339
static unsigned getNumber(const BasicBlock *BB)
Definition: CFG.h:342
static ChildIteratorType child_end(NodeRef N)
Definition: CFG.h:340
static NodeRef getEntryNode(Inverse< BasicBlock * > G)
Definition: CFG.h:338
static unsigned getNumberEpoch(const Function *F)
Definition: CFG.h:432
static unsigned getMaxNumber(const Function *F)
Definition: CFG.h:429
static NodeRef getEntryNode(Inverse< Function * > G)
Definition: CFG.h:425
static ChildIteratorType child_end(NodeRef N)
Definition: CFG.h:354
static NodeRef getEntryNode(Inverse< const BasicBlock * > G)
Definition: CFG.h:352
static ChildIteratorType child_begin(NodeRef N)
Definition: CFG.h:353
static unsigned getNumber(const BasicBlock *BB)
Definition: CFG.h:356
static unsigned getMaxNumber(const Function *F)
Definition: CFG.h:442
static NodeRef getEntryNode(Inverse< const Function * > G)
Definition: CFG.h:438
static unsigned getNumberEpoch(const Function *F)
Definition: CFG.h:445
static ChildIteratorType child_begin(NodeRef N)
Definition: CFG.h:320
static unsigned getNumber(const BasicBlock *BB)
Definition: CFG.h:323
static NodeRef getEntryNode(const BasicBlock *BB)
Definition: CFG.h:318
static ChildIteratorType child_end(NodeRef N)
Definition: CFG.h:321
static size_t size(const Function *F)
Definition: CFG.h:408
static nodes_iterator nodes_begin(const Function *F)
Definition: CFG.h:400
static NodeRef getEntryNode(const Function *F)
Definition: CFG.h:395
static unsigned getNumberEpoch(const Function *F)
Definition: CFG.h:413
static unsigned getMaxNumber(const Function *F)
Definition: CFG.h:410
static nodes_iterator nodes_end(const Function *F)
Definition: CFG.h:404