[Alignment][NFC] Convert StoreInst to MaybeAlign
[llvm-complete.git] / include / llvm / IR / CFG.h
blob55aff7137e86f61a3735a842691c6adf432b21c9
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 //===----------------------------------------------------------------------===//
19 #ifndef LLVM_IR_CFG_H
20 #define LLVM_IR_CFG_H
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/InstrTypes.h"
28 #include "llvm/IR/Value.h"
29 #include "llvm/Support/Casting.h"
30 #include "llvm/Support/type_traits.h"
31 #include <cassert>
32 #include <cstddef>
33 #include <iterator>
35 namespace llvm {
37 //===----------------------------------------------------------------------===//
38 // BasicBlock pred_iterator definition
39 //===----------------------------------------------------------------------===//
41 template <class Ptr, class USE_iterator> // Predecessor Iterator
42 class PredIterator : public std::iterator<std::forward_iterator_tag,
43 Ptr, ptrdiff_t, Ptr*, Ptr*> {
44 using super =
45 std::iterator<std::forward_iterator_tag, Ptr, ptrdiff_t, Ptr*, Ptr*>;
46 using Self = PredIterator<Ptr, USE_iterator>;
47 USE_iterator It;
49 inline void advancePastNonTerminators() {
50 // Loop to ignore non-terminator uses (for example BlockAddresses).
51 while (!It.atEnd()) {
52 if (auto *Inst = dyn_cast<Instruction>(*It))
53 if (Inst->isTerminator())
54 break;
56 ++It;
60 public:
61 using pointer = typename super::pointer;
62 using reference = typename super::reference;
64 PredIterator() = default;
65 explicit inline PredIterator(Ptr *bb) : It(bb->user_begin()) {
66 advancePastNonTerminators();
68 inline PredIterator(Ptr *bb, bool) : It(bb->user_end()) {}
70 inline bool operator==(const Self& x) const { return It == x.It; }
71 inline bool operator!=(const Self& x) const { return !operator==(x); }
73 inline reference operator*() const {
74 assert(!It.atEnd() && "pred_iterator out of range!");
75 return cast<Instruction>(*It)->getParent();
77 inline pointer *operator->() const { return &operator*(); }
79 inline Self& operator++() { // Preincrement
80 assert(!It.atEnd() && "pred_iterator out of range!");
81 ++It; advancePastNonTerminators();
82 return *this;
85 inline Self operator++(int) { // Postincrement
86 Self tmp = *this; ++*this; return tmp;
89 /// getOperandNo - Return the operand number in the predecessor's
90 /// terminator of the successor.
91 unsigned getOperandNo() const {
92 return It.getOperandNo();
95 /// getUse - Return the operand Use in the predecessor's terminator
96 /// of the successor.
97 Use &getUse() const {
98 return It.getUse();
102 using pred_iterator = PredIterator<BasicBlock, Value::user_iterator>;
103 using const_pred_iterator =
104 PredIterator<const BasicBlock, Value::const_user_iterator>;
105 using pred_range = iterator_range<pred_iterator>;
106 using pred_const_range = iterator_range<const_pred_iterator>;
108 inline pred_iterator pred_begin(BasicBlock *BB) { return pred_iterator(BB); }
109 inline const_pred_iterator pred_begin(const BasicBlock *BB) {
110 return const_pred_iterator(BB);
112 inline pred_iterator pred_end(BasicBlock *BB) { return pred_iterator(BB, true);}
113 inline const_pred_iterator pred_end(const BasicBlock *BB) {
114 return const_pred_iterator(BB, true);
116 inline bool pred_empty(const BasicBlock *BB) {
117 return pred_begin(BB) == pred_end(BB);
119 /// Get the number of predecessors of \p BB. This is a linear time operation.
120 /// Use \ref BasicBlock::hasNPredecessors() or hasNPredecessorsOrMore if able.
121 inline unsigned pred_size(const BasicBlock *BB) {
122 return std::distance(pred_begin(BB), pred_end(BB));
124 inline pred_range predecessors(BasicBlock *BB) {
125 return pred_range(pred_begin(BB), pred_end(BB));
127 inline pred_const_range predecessors(const BasicBlock *BB) {
128 return pred_const_range(pred_begin(BB), pred_end(BB));
131 //===----------------------------------------------------------------------===//
132 // Instruction and BasicBlock succ_iterator helpers
133 //===----------------------------------------------------------------------===//
135 template <class InstructionT, class BlockT>
136 class SuccIterator
137 : public iterator_facade_base<SuccIterator<InstructionT, BlockT>,
138 std::random_access_iterator_tag, BlockT, int,
139 BlockT *, BlockT *> {
140 public:
141 using difference_type = int;
142 using pointer = BlockT *;
143 using reference = BlockT *;
145 private:
146 InstructionT *Inst;
147 int Idx;
148 using Self = SuccIterator<InstructionT, BlockT>;
150 inline bool index_is_valid(int Idx) {
151 // Note that we specially support the index of zero being valid even in the
152 // face of a null instruction.
153 return Idx >= 0 && (Idx == 0 || Idx <= (int)Inst->getNumSuccessors());
156 /// Proxy object to allow write access in operator[]
157 class SuccessorProxy {
158 Self It;
160 public:
161 explicit SuccessorProxy(const Self &It) : It(It) {}
163 SuccessorProxy(const SuccessorProxy &) = default;
165 SuccessorProxy &operator=(SuccessorProxy RHS) {
166 *this = reference(RHS);
167 return *this;
170 SuccessorProxy &operator=(reference RHS) {
171 It.Inst->setSuccessor(It.Idx, RHS);
172 return *this;
175 operator reference() const { return *It; }
178 public:
179 // begin iterator
180 explicit inline SuccIterator(InstructionT *Inst) : Inst(Inst), Idx(0) {}
181 // end iterator
182 inline SuccIterator(InstructionT *Inst, bool) : Inst(Inst) {
183 if (Inst)
184 Idx = Inst->getNumSuccessors();
185 else
186 // Inst == NULL happens, if a basic block is not fully constructed and
187 // consequently getTerminator() returns NULL. In this case we construct
188 // a SuccIterator which describes a basic block that has zero
189 // successors.
190 // Defining SuccIterator for incomplete and malformed CFGs is especially
191 // useful for debugging.
192 Idx = 0;
195 /// This is used to interface between code that wants to
196 /// operate on terminator instructions directly.
197 int getSuccessorIndex() const { return Idx; }
199 inline bool operator==(const Self &x) const { return Idx == x.Idx; }
201 inline BlockT *operator*() const { return Inst->getSuccessor(Idx); }
203 // We use the basic block pointer directly for operator->.
204 inline BlockT *operator->() const { return operator*(); }
206 inline bool operator<(const Self &RHS) const {
207 assert(Inst == RHS.Inst && "Cannot compare iterators of different blocks!");
208 return Idx < RHS.Idx;
211 int operator-(const Self &RHS) const {
212 assert(Inst == RHS.Inst && "Cannot compare iterators of different blocks!");
213 return Idx - RHS.Idx;
216 inline Self &operator+=(int RHS) {
217 int NewIdx = Idx + RHS;
218 assert(index_is_valid(NewIdx) && "Iterator index out of bound");
219 Idx = NewIdx;
220 return *this;
223 inline Self &operator-=(int RHS) { return operator+=(-RHS); }
225 // Specially implement the [] operation using a proxy object to support
226 // assignment.
227 inline SuccessorProxy operator[](int Offset) {
228 Self TmpIt = *this;
229 TmpIt += Offset;
230 return SuccessorProxy(TmpIt);
233 /// Get the source BlockT of this iterator.
234 inline BlockT *getSource() {
235 assert(Inst && "Source not available, if basic block was malformed");
236 return Inst->getParent();
240 using succ_iterator = SuccIterator<Instruction, BasicBlock>;
241 using succ_const_iterator = SuccIterator<const Instruction, const BasicBlock>;
242 using succ_range = iterator_range<succ_iterator>;
243 using succ_const_range = iterator_range<succ_const_iterator>;
245 inline succ_iterator succ_begin(Instruction *I) { return succ_iterator(I); }
246 inline succ_const_iterator succ_begin(const Instruction *I) {
247 return succ_const_iterator(I);
249 inline succ_iterator succ_end(Instruction *I) { return succ_iterator(I, true); }
250 inline succ_const_iterator succ_end(const Instruction *I) {
251 return succ_const_iterator(I, true);
253 inline bool succ_empty(const Instruction *I) {
254 return succ_begin(I) == succ_end(I);
256 inline unsigned succ_size(const Instruction *I) {
257 return std::distance(succ_begin(I), succ_end(I));
259 inline succ_range successors(Instruction *I) {
260 return succ_range(succ_begin(I), succ_end(I));
262 inline succ_const_range successors(const Instruction *I) {
263 return succ_const_range(succ_begin(I), succ_end(I));
266 inline succ_iterator succ_begin(BasicBlock *BB) {
267 return succ_iterator(BB->getTerminator());
269 inline succ_const_iterator succ_begin(const BasicBlock *BB) {
270 return succ_const_iterator(BB->getTerminator());
272 inline succ_iterator succ_end(BasicBlock *BB) {
273 return succ_iterator(BB->getTerminator(), true);
275 inline succ_const_iterator succ_end(const BasicBlock *BB) {
276 return succ_const_iterator(BB->getTerminator(), true);
278 inline bool succ_empty(const BasicBlock *BB) {
279 return succ_begin(BB) == succ_end(BB);
281 inline unsigned succ_size(const BasicBlock *BB) {
282 return std::distance(succ_begin(BB), succ_end(BB));
284 inline succ_range successors(BasicBlock *BB) {
285 return succ_range(succ_begin(BB), succ_end(BB));
287 inline succ_const_range successors(const BasicBlock *BB) {
288 return succ_const_range(succ_begin(BB), succ_end(BB));
291 //===--------------------------------------------------------------------===//
292 // GraphTraits specializations for basic block graphs (CFGs)
293 //===--------------------------------------------------------------------===//
295 // Provide specializations of GraphTraits to be able to treat a function as a
296 // graph of basic blocks...
298 template <> struct GraphTraits<BasicBlock*> {
299 using NodeRef = BasicBlock *;
300 using ChildIteratorType = succ_iterator;
302 static NodeRef getEntryNode(BasicBlock *BB) { return BB; }
303 static ChildIteratorType child_begin(NodeRef N) { return succ_begin(N); }
304 static ChildIteratorType child_end(NodeRef N) { return succ_end(N); }
307 template <> struct GraphTraits<const BasicBlock*> {
308 using NodeRef = const BasicBlock *;
309 using ChildIteratorType = succ_const_iterator;
311 static NodeRef getEntryNode(const BasicBlock *BB) { return BB; }
313 static ChildIteratorType child_begin(NodeRef N) { return succ_begin(N); }
314 static ChildIteratorType child_end(NodeRef N) { return succ_end(N); }
317 // Provide specializations of GraphTraits to be able to treat a function as a
318 // graph of basic blocks... and to walk it in inverse order. Inverse order for
319 // a function is considered to be when traversing the predecessor edges of a BB
320 // instead of the successor edges.
322 template <> struct GraphTraits<Inverse<BasicBlock*>> {
323 using NodeRef = BasicBlock *;
324 using ChildIteratorType = pred_iterator;
326 static NodeRef getEntryNode(Inverse<BasicBlock *> G) { return G.Graph; }
327 static ChildIteratorType child_begin(NodeRef N) { return pred_begin(N); }
328 static ChildIteratorType child_end(NodeRef N) { return pred_end(N); }
331 template <> struct GraphTraits<Inverse<const BasicBlock*>> {
332 using NodeRef = const BasicBlock *;
333 using ChildIteratorType = const_pred_iterator;
335 static NodeRef getEntryNode(Inverse<const BasicBlock *> G) { return G.Graph; }
336 static ChildIteratorType child_begin(NodeRef N) { return pred_begin(N); }
337 static ChildIteratorType child_end(NodeRef N) { return pred_end(N); }
340 //===--------------------------------------------------------------------===//
341 // GraphTraits specializations for function basic block graphs (CFGs)
342 //===--------------------------------------------------------------------===//
344 // Provide specializations of GraphTraits to be able to treat a function as a
345 // graph of basic blocks... these are the same as the basic block iterators,
346 // except that the root node is implicitly the first node of the function.
348 template <> struct GraphTraits<Function*> : public GraphTraits<BasicBlock*> {
349 static NodeRef getEntryNode(Function *F) { return &F->getEntryBlock(); }
351 // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
352 using nodes_iterator = pointer_iterator<Function::iterator>;
354 static nodes_iterator nodes_begin(Function *F) {
355 return nodes_iterator(F->begin());
358 static nodes_iterator nodes_end(Function *F) {
359 return nodes_iterator(F->end());
362 static size_t size(Function *F) { return F->size(); }
364 template <> struct GraphTraits<const Function*> :
365 public GraphTraits<const BasicBlock*> {
366 static NodeRef getEntryNode(const Function *F) { return &F->getEntryBlock(); }
368 // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
369 using nodes_iterator = pointer_iterator<Function::const_iterator>;
371 static nodes_iterator nodes_begin(const Function *F) {
372 return nodes_iterator(F->begin());
375 static nodes_iterator nodes_end(const Function *F) {
376 return nodes_iterator(F->end());
379 static size_t size(const Function *F) { return F->size(); }
382 // Provide specializations of GraphTraits to be able to treat a function as a
383 // graph of basic blocks... and to walk it in inverse order. Inverse order for
384 // a function is considered to be when traversing the predecessor edges of a BB
385 // instead of the successor edges.
387 template <> struct GraphTraits<Inverse<Function*>> :
388 public GraphTraits<Inverse<BasicBlock*>> {
389 static NodeRef getEntryNode(Inverse<Function *> G) {
390 return &G.Graph->getEntryBlock();
393 template <> struct GraphTraits<Inverse<const Function*>> :
394 public GraphTraits<Inverse<const BasicBlock*>> {
395 static NodeRef getEntryNode(Inverse<const Function *> G) {
396 return &G.Graph->getEntryBlock();
400 } // end namespace llvm
402 #endif // LLVM_IR_CFG_H