1//===- Block.h - MLIR Block Class -------------------------------*- 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//
9// This file defines the Block class.
10//
11//===----------------------------------------------------------------------===//
12
13#ifndef MLIR_IR_BLOCK_H
14#define MLIR_IR_BLOCK_H
15
16#include "mlir/IR/BlockSupport.h"
17#include "mlir/IR/Visitors.h"
18
19namespace llvm {
20class BitVector;
21} // namespace llvm
22
23namespace mlir {
24class TypeRange;
25template <typename ValueRangeT>
26class ValueTypeRange;
27
28/// `Block` represents an ordered list of `Operation`s.
29class Block : public IRObjectWithUseList<BlockOperand>,
30 public llvm::ilist_node_with_parent<Block, Region> {
31public:
32 explicit Block() = default;
33 ~Block();
34
35 void clear() {
36 // Drop all references from within this block.
37 dropAllReferences();
38
39 // Clear operations in the reverse order so that uses are destroyed
40 // before their defs.
41 while (!empty())
42 operations.pop_back();
43 }
44
45 /// Provide a 'getParent' method for ilist_node_with_parent methods.
46 /// We mark it as a const function because ilist_node_with_parent specifically
47 /// requires a 'getParent() const' method. Once ilist_node removes this
48 /// constraint, we should drop the const to fit the rest of the MLIR const
49 /// model.
50 Region *getParent() const;
51
52 /// Returns the closest surrounding operation that contains this block.
53 Operation *getParentOp();
54
55 /// Return if this block is the entry block in the parent region.
56 bool isEntryBlock();
57
58 /// Insert this block (which must not already be in a region) right before
59 /// the specified block.
60 void insertBefore(Block *block);
61
62 /// Insert this block (which must not already be in a region) right after
63 /// the specified block.
64 void insertAfter(Block *block);
65
66 /// Unlink this block from its current region and insert it right before the
67 /// specific block.
68 void moveBefore(Block *block);
69
70 /// Unlink this block from its current region and insert it right before the
71 /// block that the given iterator points to in the region region.
72 void moveBefore(Region *region, llvm::iplist<Block>::iterator iterator);
73
74 /// Unlink this Block from its parent region and delete it.
75 void erase();
76
77 //===--------------------------------------------------------------------===//
78 // Block argument management
79 //===--------------------------------------------------------------------===//
80
81 // This is the list of arguments to the block.
82 using BlockArgListType = MutableArrayRef<BlockArgument>;
83
84 BlockArgListType getArguments() { return arguments; }
85
86 /// Return a range containing the types of the arguments for this block.
87 ValueTypeRange<BlockArgListType> getArgumentTypes();
88
89 using args_iterator = BlockArgListType::iterator;
90 using reverse_args_iterator = BlockArgListType::reverse_iterator;
91 args_iterator args_begin() { return getArguments().begin(); }
92 args_iterator args_end() { return getArguments().end(); }
93 reverse_args_iterator args_rbegin() { return getArguments().rbegin(); }
94 reverse_args_iterator args_rend() { return getArguments().rend(); }
95
96 bool args_empty() { return arguments.empty(); }
97
98 /// Add one value to the argument list.
99 BlockArgument addArgument(Type type, Location loc);
100
101 /// Insert one value to the position in the argument list indicated by the
102 /// given iterator. The existing arguments are shifted. The block is expected
103 /// not to have predecessors.
104 BlockArgument insertArgument(args_iterator it, Type type, Location loc);
105
106 /// Add one argument to the argument list for each type specified in the list.
107 /// `locs` is required to have the same number of elements as `types`.
108 iterator_range<args_iterator> addArguments(TypeRange types,
109 ArrayRef<Location> locs);
110
111 /// Add one value to the argument list at the specified position.
112 BlockArgument insertArgument(unsigned index, Type type, Location loc);
113
114 /// Erase the argument at 'index' and remove it from the argument list.
115 void eraseArgument(unsigned index);
116 /// Erases 'num' arguments from the index 'start'.
117 void eraseArguments(unsigned start, unsigned num);
118 /// Erases the arguments that have their corresponding bit set in
119 /// `eraseIndices` and removes them from the argument list.
120 void eraseArguments(const BitVector &eraseIndices);
121 /// Erases arguments using the given predicate. If the predicate returns true,
122 /// that argument is erased.
123 void eraseArguments(function_ref<bool(BlockArgument)> shouldEraseFn);
124
125 unsigned getNumArguments() { return arguments.size(); }
126 BlockArgument getArgument(unsigned i) { return arguments[i]; }
127
128 //===--------------------------------------------------------------------===//
129 // Operation list management
130 //===--------------------------------------------------------------------===//
131
132 /// This is the list of operations in the block.
133 using OpListType = llvm::iplist<Operation>;
134 OpListType &getOperations() { return operations; }
135
136 // Iteration over the operations in the block.
137 using iterator = OpListType::iterator;
138 using reverse_iterator = OpListType::reverse_iterator;
139
140 iterator begin() { return operations.begin(); }
141 iterator end() { return operations.end(); }
142 reverse_iterator rbegin() { return operations.rbegin(); }
143 reverse_iterator rend() { return operations.rend(); }
144
145 bool empty() { return operations.empty(); }
146 void push_back(Operation *op) { operations.push_back(val: op); }
147 void push_front(Operation *op) { operations.push_front(val: op); }
148
149 Operation &back() { return operations.back(); }
150 Operation &front() { return operations.front(); }
151
152 /// Returns 'op' if 'op' lies in this block, or otherwise finds the
153 /// ancestor operation of 'op' that lies in this block. Returns nullptr if
154 /// the latter fails.
155 /// TODO: This is very specific functionality that should live somewhere else,
156 /// probably in Dominance.cpp.
157 Operation *findAncestorOpInBlock(Operation &op);
158
159 /// This drops all operand uses from operations within this block, which is
160 /// an essential step in breaking cyclic dependences between references when
161 /// they are to be deleted.
162 void dropAllReferences();
163
164 /// This drops all uses of values defined in this block or in the blocks of
165 /// nested regions wherever the uses are located.
166 void dropAllDefinedValueUses();
167
168 /// Returns true if the ordering of the child operations is valid, false
169 /// otherwise.
170 bool isOpOrderValid();
171
172 /// Invalidates the current ordering of operations.
173 void invalidateOpOrder();
174
175 /// Verifies the current ordering of child operations matches the
176 /// validOpOrder flag. Returns false if the order is valid, true otherwise.
177 bool verifyOpOrder();
178
179 /// Recomputes the ordering of child operations within the block.
180 void recomputeOpOrder();
181
182 /// This class provides iteration over the held operations of a block for a
183 /// specific operation type.
184 template <typename OpT>
185 using op_iterator = detail::op_iterator<OpT, iterator>;
186
187 /// Return an iterator range over the operations within this block that are of
188 /// 'OpT'.
189 template <typename OpT>
190 iterator_range<op_iterator<OpT>> getOps() {
191 auto endIt = end();
192 return {detail::op_filter_iterator<OpT, iterator>(begin(), endIt),
193 detail::op_filter_iterator<OpT, iterator>(endIt, endIt)};
194 }
195 template <typename OpT>
196 op_iterator<OpT> op_begin() {
197 return detail::op_filter_iterator<OpT, iterator>(begin(), end());
198 }
199 template <typename OpT>
200 op_iterator<OpT> op_end() {
201 return detail::op_filter_iterator<OpT, iterator>(end(), end());
202 }
203
204 /// Return an iterator range over the operation within this block excluding
205 /// the terminator operation at the end.
206 iterator_range<iterator> without_terminator() {
207 if (begin() == end())
208 return {begin(), end()};
209 auto endIt = --end();
210 return {begin(), endIt};
211 }
212
213 //===--------------------------------------------------------------------===//
214 // Terminator management
215 //===--------------------------------------------------------------------===//
216
217 /// Get the terminator operation of this block. This function asserts that
218 /// the block might have a valid terminator operation.
219 Operation *getTerminator();
220
221 /// Check whether this block might have a terminator.
222 bool mightHaveTerminator();
223
224 //===--------------------------------------------------------------------===//
225 // Predecessors and successors.
226 //===--------------------------------------------------------------------===//
227
228 // Predecessor iteration.
229 using pred_iterator = PredecessorIterator;
230 pred_iterator pred_begin() {
231 return pred_iterator((BlockOperand *)getFirstUse());
232 }
233 pred_iterator pred_end() { return pred_iterator(nullptr); }
234 iterator_range<pred_iterator> getPredecessors() {
235 return {pred_begin(), pred_end()};
236 }
237
238 /// Return true if this block has no predecessors.
239 bool hasNoPredecessors() { return pred_begin() == pred_end(); }
240
241 /// Returns true if this blocks has no successors.
242 bool hasNoSuccessors() { return succ_begin() == succ_end(); }
243
244 /// If this block has exactly one predecessor, return it. Otherwise, return
245 /// null.
246 ///
247 /// Note that if a block has duplicate predecessors from a single block (e.g.
248 /// if you have a conditional branch with the same block as the true/false
249 /// destinations) is not considered to be a single predecessor.
250 Block *getSinglePredecessor();
251
252 /// If this block has a unique predecessor, i.e., all incoming edges originate
253 /// from one block, return it. Otherwise, return null.
254 Block *getUniquePredecessor();
255
256 // Indexed successor access.
257 unsigned getNumSuccessors();
258 Block *getSuccessor(unsigned i);
259
260 // Successor iteration.
261 using succ_iterator = SuccessorRange::iterator;
262 succ_iterator succ_begin() { return getSuccessors().begin(); }
263 succ_iterator succ_end() { return getSuccessors().end(); }
264 SuccessorRange getSuccessors() { return SuccessorRange(this); }
265
266 //===--------------------------------------------------------------------===//
267 // Walkers
268 //===--------------------------------------------------------------------===//
269
270 /// Walk all nested operations, blocks (including this block) or regions,
271 /// depending on the type of callback.
272 ///
273 /// The order in which operations, blocks or regions at the same nesting
274 /// level are visited (e.g., lexicographical or reverse lexicographical order)
275 /// is determined by `Iterator`. The walk order for enclosing operations,
276 /// blocks or regions with respect to their nested ones is specified by
277 /// `Order` (post-order by default).
278 ///
279 /// A callback on a operation or block is allowed to erase that operation or
280 /// block if either:
281 /// * the walk is in post-order, or
282 /// * the walk is in pre-order and the walk is skipped after the erasure.
283 ///
284 /// See Operation::walk for more details.
285 template <WalkOrder Order = WalkOrder::PostOrder,
286 typename Iterator = ForwardIterator, typename FnT,
287 typename ArgT = detail::first_argument<FnT>,
288 typename RetT = detail::walkResultType<FnT>>
289 RetT walk(FnT &&callback) {
290 if constexpr (std::is_same<ArgT, Block *>::value &&
291 Order == WalkOrder::PreOrder) {
292 // Pre-order walk on blocks: invoke the callback on this block.
293 if constexpr (std::is_same<RetT, void>::value) {
294 callback(this);
295 } else {
296 RetT result = callback(this);
297 if (result.wasSkipped())
298 return WalkResult::advance();
299 if (result.wasInterrupted())
300 return WalkResult::interrupt();
301 }
302 }
303
304 // Walk nested operations, blocks or regions.
305 if constexpr (std::is_same<RetT, void>::value) {
306 walk<Order, Iterator>(begin(), end(), std::forward<FnT>(callback));
307 } else {
308 if (walk<Order, Iterator>(begin(), end(), std::forward<FnT>(callback))
309 .wasInterrupted())
310 return WalkResult::interrupt();
311 }
312
313 if constexpr (std::is_same<ArgT, Block *>::value &&
314 Order == WalkOrder::PostOrder) {
315 // Post-order walk on blocks: invoke the callback on this block.
316 return callback(this);
317 }
318 if constexpr (!std::is_same<RetT, void>::value)
319 return WalkResult::advance();
320 }
321
322 /// Walk all nested operations, blocks (excluding this block) or regions,
323 /// depending on the type of callback, in the specified [begin, end) range of
324 /// this block.
325 ///
326 /// The order in which operations, blocks or regions at the same nesting
327 /// level are visited (e.g., lexicographical or reverse lexicographical order)
328 /// is determined by `Iterator`. The walk order for enclosing operations,
329 /// blocks or regions with respect to their nested ones is specified by
330 /// `Order` (post-order by default).
331 ///
332 /// A callback on a operation or block is allowed to erase that operation or
333 /// block if either:
334 /// * the walk is in post-order, or
335 /// * the walk is in pre-order and the walk is skipped after the erasure.
336 ///
337 /// See Operation::walk for more details.
338 template <WalkOrder Order = WalkOrder::PostOrder,
339 typename Iterator = ForwardIterator, typename FnT,
340 typename RetT = detail::walkResultType<FnT>>
341 RetT walk(Block::iterator begin, Block::iterator end, FnT &&callback) {
342 for (auto &op : llvm::make_early_inc_range(Range: llvm::make_range(x: begin, y: end))) {
343 if constexpr (std::is_same<RetT, WalkResult>::value) {
344 if (detail::walk<Order, Iterator>(&op, callback).wasInterrupted())
345 return WalkResult::interrupt();
346 } else {
347 detail::walk<Order, Iterator>(&op, callback);
348 }
349 }
350 if constexpr (std::is_same<RetT, WalkResult>::value)
351 return WalkResult::advance();
352 }
353
354 //===--------------------------------------------------------------------===//
355 // Other
356 //===--------------------------------------------------------------------===//
357
358 /// Split the block into two blocks before the specified operation or
359 /// iterator.
360 ///
361 /// Note that all operations BEFORE the specified iterator stay as part of
362 /// the original basic block, and the rest of the operations in the original
363 /// block are moved to the new block, including the old terminator. The
364 /// original block is left without a terminator.
365 ///
366 /// The newly formed Block is returned, and the specified iterator is
367 /// invalidated.
368 Block *splitBlock(iterator splitBefore);
369 Block *splitBlock(Operation *splitBeforeOp) {
370 return splitBlock(splitBefore: iterator(splitBeforeOp));
371 }
372
373 /// Returns pointer to member of operation list.
374 static OpListType Block::*getSublistAccess(Operation *) {
375 return &Block::operations;
376 }
377
378 void print(raw_ostream &os);
379 void print(raw_ostream &os, AsmState &state);
380 void dump();
381
382 /// Print out the name of the block without printing its body.
383 /// NOTE: The printType argument is ignored. We keep it for compatibility
384 /// with LLVM dominator machinery that expects it to exist.
385 void printAsOperand(raw_ostream &os, bool printType = true);
386 void printAsOperand(raw_ostream &os, AsmState &state);
387
388private:
389 /// Pair of the parent object that owns this block and a bit that signifies if
390 /// the operations within this block have a valid ordering.
391 llvm::PointerIntPair<Region *, /*IntBits=*/1, bool> parentValidOpOrderPair;
392
393 /// This is the list of operations in the block.
394 OpListType operations;
395
396 /// This is the list of arguments to the block.
397 std::vector<BlockArgument> arguments;
398
399 Block(Block &) = delete;
400 void operator=(Block &) = delete;
401
402 friend struct llvm::ilist_traits<Block>;
403};
404} // namespace mlir
405
406#endif // MLIR_IR_BLOCK_H
407

source code of mlir/include/mlir/IR/Block.h