LLVM 19.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
309template <> struct GraphTraits<const BasicBlock*> {
310 using NodeRef = const BasicBlock *;
312
313 static NodeRef getEntryNode(const BasicBlock *BB) { return BB; }
314
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*>> {
327
328 static NodeRef getEntryNode(Inverse<BasicBlock *> G) { return G.Graph; }
331};
332
333template <> struct GraphTraits<Inverse<const BasicBlock*>> {
334 using NodeRef = const BasicBlock *;
336
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
355
357 return nodes_iterator(F->begin());
358 }
359
361 return nodes_iterator(F->end());
362 }
363
364 static size_t size(Function *F) { return F->size(); }
365};
366template <> struct GraphTraits<const Function*> :
368 static NodeRef getEntryNode(const Function *F) { return &F->getEntryBlock(); }
369
370 // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
372
374 return nodes_iterator(F->begin());
375 }
376
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*>> :
392 return &G.Graph->getEntryBlock();
393 }
394};
395template <> struct GraphTraits<Inverse<const Function*>> :
398 return &G.Graph->getEntryBlock();
399 }
400};
401
402} // end namespace llvm
403
404#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:60
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:220
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
@ Offset
Definition: DWP.cpp:456
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:102
bool succ_empty(const Instruction *I)
Definition: CFG.h:255
auto successors(const MachineBasicBlock *BB)
Interval::succ_iterator succ_begin(Interval *I)
succ_begin/succ_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:99
Interval::pred_iterator pred_end(Interval *I)
Definition: Interval.h:112
SuccIterator< Instruction, BasicBlock > succ_iterator
Definition: CFG.h:242
Interval::pred_iterator pred_begin(Interval *I)
pred_begin/pred_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:109
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
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 ChildIteratorType child_end(NodeRef N)
Definition: CFG.h:306
static nodes_iterator nodes_begin(Function *F)
Definition: CFG.h:356
static nodes_iterator nodes_end(Function *F)
Definition: CFG.h:360
static size_t size(Function *F)
Definition: CFG.h:364
static NodeRef getEntryNode(Function *F)
Definition: CFG.h:351
static ChildIteratorType child_begin(NodeRef N)
Definition: CFG.h:329
static ChildIteratorType child_end(NodeRef N)
Definition: CFG.h:330
static NodeRef getEntryNode(Inverse< BasicBlock * > G)
Definition: CFG.h:328
static NodeRef getEntryNode(Inverse< Function * > G)
Definition: CFG.h:391
static ChildIteratorType child_end(NodeRef N)
Definition: CFG.h:339
static NodeRef getEntryNode(Inverse< const BasicBlock * > G)
Definition: CFG.h:337
static ChildIteratorType child_begin(NodeRef N)
Definition: CFG.h:338
static NodeRef getEntryNode(Inverse< const Function * > G)
Definition: CFG.h:397
static ChildIteratorType child_begin(NodeRef N)
Definition: CFG.h:315
static NodeRef getEntryNode(const BasicBlock *BB)
Definition: CFG.h:313
static ChildIteratorType child_end(NodeRef N)
Definition: CFG.h:316
static size_t size(const Function *F)
Definition: CFG.h:381
static nodes_iterator nodes_begin(const Function *F)
Definition: CFG.h:373
static NodeRef getEntryNode(const Function *F)
Definition: CFG.h:368
static nodes_iterator nodes_end(const Function *F)
Definition: CFG.h:377