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

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