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