MLIR  19.0.0git
Block.h
Go to the documentation of this file.
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.
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.
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.
83 
84  BlockArgListType getArguments() { return arguments; }
85 
86  /// Return a range containing the types of the arguments for this block.
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(); }
95 
96  bool args_empty() { return arguments.empty(); }
97 
98  /// Add one value to the argument list.
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.
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`.
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(op); }
147  void push_front(Operation *op) { operations.push_front(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.
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.
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>
186 
187  /// Return an iterator range over the operations within this block that are of
188  /// 'OpT'.
189  template <typename OpT>
191  auto endIt = end();
194  }
195  template <typename OpT>
198  }
199  template <typename OpT>
202  }
203 
204  /// Return an iterator range over the operation within this block excluding
205  /// the terminator operation at the end.
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.
220 
221  /// Check whether this block might have a terminator.
222  bool mightHaveTerminator();
223 
224  //===--------------------------------------------------------------------===//
225  // Predecessors and successors.
226  //===--------------------------------------------------------------------===//
227 
228  // Predecessor iteration.
232  }
233  pred_iterator pred_end() { return pred_iterator(nullptr); }
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.
251 
252  /// If this block has a unique predecessor, i.e., all incoming edges originate
253  /// from one block, return it. Otherwise, return null.
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(); }
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(llvm::make_range(begin, 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(iterator(splitBeforeOp));
371  }
372 
373  /// Returns pointer to member of operation list.
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
This class provides management for the lifetime of the state used when printing the IR.
Definition: AsmState.h:533
This class represents an argument of a Block.
Definition: Value.h:315
A block operand represents an operand that holds a reference to a Block, e.g.
Definition: BlockSupport.h:30
Block represents an ordered list of Operations.
Definition: Block.h:30
void recomputeOpOrder()
Recomputes the ordering of child operations within the block.
Definition: Block.cpp:135
OpListType::iterator iterator
Definition: Block.h:137
Block * splitBlock(Operation *splitBeforeOp)
Definition: Block.h:369
Operation * findAncestorOpInBlock(Operation &op)
Returns 'op' if 'op' lies in this block, or otherwise finds the ancestor operation of 'op' that lies ...
Definition: Block.cpp:73
ValueTypeRange< BlockArgListType > getArgumentTypes()
Return a range containing the types of the arguments for this block.
Definition: Block.cpp:148
unsigned getNumSuccessors()
Definition: Block.cpp:254
void push_front(Operation *op)
Definition: Block.h:147
SuccessorRange::iterator succ_iterator
Definition: Block.h:261
bool empty()
Definition: Block.h:145
BlockArgument getArgument(unsigned i)
Definition: Block.h:126
bool hasNoSuccessors()
Returns true if this blocks has no successors.
Definition: Block.h:242
unsigned getNumArguments()
Definition: Block.h:125
Operation & back()
Definition: Block.h:149
void erase()
Unlink this Block from its parent region and delete it.
Definition: Block.cpp:65
BlockArgument insertArgument(args_iterator it, Type type, Location loc)
Insert one value to the position in the argument list indicated by the given iterator.
Definition: Block.cpp:186
iterator_range< args_iterator > addArguments(TypeRange types, ArrayRef< Location > locs)
Add one argument to the argument list for each type specified in the list.
Definition: Block.cpp:159
Block * splitBlock(iterator splitBefore)
Split the block into two blocks before the specified operation or iterator.
Definition: Block.cpp:307
Block()=default
Region * getParent() const
Provide a 'getParent' method for ilist_node_with_parent methods.
Definition: Block.cpp:26
bool isOpOrderValid()
Returns true if the ordering of the child operations is valid, false otherwise.
Definition: Block.cpp:103
op_iterator< OpT > op_begin()
Definition: Block.h:196
BlockArgListType::reverse_iterator reverse_args_iterator
Definition: Block.h:90
args_iterator args_end()
Definition: Block.h:92
succ_iterator succ_end()
Definition: Block.h:263
pred_iterator pred_begin()
Definition: Block.h:230
void dropAllDefinedValueUses()
This drops all uses of values defined in this block or in the blocks of nested regions wherever the u...
Definition: Block.cpp:93
bool verifyOpOrder()
Verifies the current ordering of child operations matches the validOpOrder flag.
Definition: Block.cpp:114
SuccessorRange getSuccessors()
Definition: Block.h:264
void invalidateOpOrder()
Invalidates the current ordering of operations.
Definition: Block.cpp:106
Block * getSinglePredecessor()
If this block has exactly one predecessor, return it.
Definition: Block.cpp:269
void printAsOperand(raw_ostream &os, bool printType=true)
Print out the name of the block without printing its body.
reverse_args_iterator args_rend()
Definition: Block.h:94
RetT walk(FnT &&callback)
Walk all nested operations, blocks (including this block) or regions, depending on the type of callba...
Definition: Block.h:289
void insertAfter(Block *block)
Insert this block (which must not already be in a region) right after the specified block.
Definition: Block.cpp:45
Operation * getTerminator()
Get the terminator operation of this block.
Definition: Block.cpp:243
succ_iterator succ_begin()
Definition: Block.h:262
iterator_range< pred_iterator > getPredecessors()
Definition: Block.h:234
BlockArgument addArgument(Type type, Location loc)
Add one value to the argument list.
Definition: Block.cpp:152
RetT walk(Block::iterator begin, Block::iterator end, FnT &&callback)
Walk all nested operations, blocks (excluding this block) or regions, depending on the type of callba...
Definition: Block.h:341
void clear()
Definition: Block.h:35
void eraseArguments(unsigned start, unsigned num)
Erases 'num' arguments from the index 'start'.
Definition: Block.cpp:200
reverse_iterator rend()
Definition: Block.h:143
OpListType & getOperations()
Definition: Block.h:134
void print(raw_ostream &os)
bool args_empty()
Definition: Block.h:96
bool mightHaveTerminator()
Check whether this block might have a terminator.
Definition: Block.cpp:249
BlockArgListType getArguments()
Definition: Block.h:84
PredecessorIterator pred_iterator
Definition: Block.h:229
Operation & front()
Definition: Block.h:150
iterator end()
Definition: Block.h:141
iterator begin()
Definition: Block.h:140
Block * getUniquePredecessor()
If this block has a unique predecessor, i.e., all incoming edges originate from one block,...
Definition: Block.cpp:280
op_iterator< OpT > op_end()
Definition: Block.h:200
void eraseArgument(unsigned index)
Erase the argument at 'index' and remove it from the argument list.
Definition: Block.cpp:192
iterator_range< op_iterator< OpT > > getOps()
Return an iterator range over the operations within this block that are of 'OpT'.
Definition: Block.h:190
Block * getSuccessor(unsigned i)
Definition: Block.cpp:258
args_iterator args_begin()
Definition: Block.h:91
bool isEntryBlock()
Return if this block is the entry block in the parent region.
Definition: Block.cpp:35
void dropAllReferences()
This drops all operand uses from operations within this block, which is an essential step in breaking...
Definition: Block.cpp:88
void insertBefore(Block *block)
Insert this block (which must not already be in a region) right before the specified block.
Definition: Block.cpp:39
pred_iterator pred_end()
Definition: Block.h:233
void moveBefore(Block *block)
Unlink this block from its current region and insert it right before the specific block.
Definition: Block.cpp:53
void push_back(Operation *op)
Definition: Block.h:146
reverse_args_iterator args_rbegin()
Definition: Block.h:93
bool hasNoPredecessors()
Return true if this block has no predecessors.
Definition: Block.h:239
static OpListType Block::* getSublistAccess(Operation *)
Returns pointer to member of operation list.
Definition: Block.h:374
iterator_range< iterator > without_terminator()
Return an iterator range over the operation within this block excluding the terminator operation at t...
Definition: Block.h:206
Operation * getParentOp()
Returns the closest surrounding operation that contains this block.
Definition: Block.cpp:30
BlockArgListType::iterator args_iterator
Definition: Block.h:89
reverse_iterator rbegin()
Definition: Block.h:142
OpListType::reverse_iterator reverse_iterator
Definition: Block.h:138
llvm::iplist< Operation > OpListType
This is the list of operations in the block.
Definition: Block.h:133
This class represents a single IR object that contains a use list.
Definition: UseDefLists.h:195
BlockOperand * getFirstUse() const
Return the first operand that is using this value, for use by custom use/def iterators.
Definition: UseDefLists.h:281
This class defines the main interface for locations in MLIR and acts as a non-nullable wrapper around...
Definition: Location.h:63
Operation is the basic unit of execution within MLIR.
Definition: Operation.h:88
Implement a predecessor iterator for blocks.
Definition: BlockSupport.h:51
This class contains a list of basic blocks and a link to the parent operation it is attached to.
Definition: Region.h:26
This class implements the successor iterators for Block.
Definition: BlockSupport.h:73
This class provides an abstraction over the various different ranges of value types.
Definition: TypeRange.h:36
Instances of the Type class are uniqued, have an immutable identifier and an optional mutable compone...
Definition: Types.h:74
This class implements iteration on the types of a given range of values.
Definition: TypeRange.h:131
static WalkResult advance()
Definition: Visitors.h:52
static WalkResult interrupt()
Definition: Visitors.h:51
A utility iterator that filters out operations that are not 'OpT'.
Definition: BlockSupport.h:142
This class provides iteration over the held operations of a block for a specific operation type.
Definition: BlockSupport.h:159
Include the generated interface declarations.
Definition: CallGraph.h:229
void printType(Type type, AsmPrinter &printer)
Prints an LLVM Dialect type.
decltype(walk(nullptr, std::declval< FnT >())) walkResultType
Utility to provide the return type of a templated walk method.
Definition: Visitors.h:466
decltype(first_argument_type(std::declval< T >())) first_argument
Type definition of the first argument to the given callable 'T'.
Definition: Visitors.h:125
Include the generated interface declarations.
WalkOrder
Traversal order for region, block and operation walk utilities.
Definition: Visitors.h:63
This iterator enumerates the elements in "forward" order.
Definition: Visitors.h:66