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 | namespace llvm { |
20 | class BitVector; |
21 | } // namespace llvm |
22 | |
23 | namespace mlir { |
24 | class TypeRange; |
25 | template <typename ValueRangeT> |
26 | class ValueTypeRange; |
27 | |
28 | /// `Block` represents an ordered list of `Operation`s. |
29 | class Block : public IRObjectWithUseList<BlockOperand>, |
30 | public llvm::ilist_node_with_parent<Block, Region> { |
31 | public: |
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 | |
388 | private: |
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 | |