MLIR  18.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 parent region and delete it.
71  void erase();
72 
73  //===--------------------------------------------------------------------===//
74  // Block argument management
75  //===--------------------------------------------------------------------===//
76 
77  // This is the list of arguments to the block.
79 
80  BlockArgListType getArguments() { return arguments; }
81 
82  /// Return a range containing the types of the arguments for this block.
84 
85  using args_iterator = BlockArgListType::iterator;
86  using reverse_args_iterator = BlockArgListType::reverse_iterator;
87  args_iterator args_begin() { return getArguments().begin(); }
88  args_iterator args_end() { return getArguments().end(); }
91 
92  bool args_empty() { return arguments.empty(); }
93 
94  /// Add one value to the argument list.
96 
97  /// Insert one value to the position in the argument list indicated by the
98  /// given iterator. The existing arguments are shifted. The block is expected
99  /// not to have predecessors.
101 
102  /// Add one argument to the argument list for each type specified in the list.
103  /// `locs` is required to have the same number of elements as `types`.
105  ArrayRef<Location> locs);
106 
107  /// Add one value to the argument list at the specified position.
108  BlockArgument insertArgument(unsigned index, Type type, Location loc);
109 
110  /// Erase the argument at 'index' and remove it from the argument list.
111  void eraseArgument(unsigned index);
112  /// Erases 'num' arguments from the index 'start'.
113  void eraseArguments(unsigned start, unsigned num);
114  /// Erases the arguments that have their corresponding bit set in
115  /// `eraseIndices` and removes them from the argument list.
116  void eraseArguments(const BitVector &eraseIndices);
117  /// Erases arguments using the given predicate. If the predicate returns true,
118  /// that argument is erased.
119  void eraseArguments(function_ref<bool(BlockArgument)> shouldEraseFn);
120 
121  unsigned getNumArguments() { return arguments.size(); }
122  BlockArgument getArgument(unsigned i) { return arguments[i]; }
123 
124  //===--------------------------------------------------------------------===//
125  // Operation list management
126  //===--------------------------------------------------------------------===//
127 
128  /// This is the list of operations in the block.
129  using OpListType = llvm::iplist<Operation>;
130  OpListType &getOperations() { return operations; }
131 
132  // Iteration over the operations in the block.
133  using iterator = OpListType::iterator;
134  using reverse_iterator = OpListType::reverse_iterator;
135 
136  iterator begin() { return operations.begin(); }
137  iterator end() { return operations.end(); }
138  reverse_iterator rbegin() { return operations.rbegin(); }
139  reverse_iterator rend() { return operations.rend(); }
140 
141  bool empty() { return operations.empty(); }
142  void push_back(Operation *op) { operations.push_back(op); }
143  void push_front(Operation *op) { operations.push_front(op); }
144 
145  Operation &back() { return operations.back(); }
146  Operation &front() { return operations.front(); }
147 
148  /// Returns 'op' if 'op' lies in this block, or otherwise finds the
149  /// ancestor operation of 'op' that lies in this block. Returns nullptr if
150  /// the latter fails.
151  /// TODO: This is very specific functionality that should live somewhere else,
152  /// probably in Dominance.cpp.
154 
155  /// This drops all operand uses from operations within this block, which is
156  /// an essential step in breaking cyclic dependences between references when
157  /// they are to be deleted.
158  void dropAllReferences();
159 
160  /// This drops all uses of values defined in this block or in the blocks of
161  /// nested regions wherever the uses are located.
163 
164  /// Returns true if the ordering of the child operations is valid, false
165  /// otherwise.
166  bool isOpOrderValid();
167 
168  /// Invalidates the current ordering of operations.
169  void invalidateOpOrder();
170 
171  /// Verifies the current ordering of child operations matches the
172  /// validOpOrder flag. Returns false if the order is valid, true otherwise.
173  bool verifyOpOrder();
174 
175  /// Recomputes the ordering of child operations within the block.
176  void recomputeOpOrder();
177 
178  /// This class provides iteration over the held operations of a block for a
179  /// specific operation type.
180  template <typename OpT>
182 
183  /// Return an iterator range over the operations within this block that are of
184  /// 'OpT'.
185  template <typename OpT>
187  auto endIt = end();
190  }
191  template <typename OpT>
194  }
195  template <typename OpT>
198  }
199 
200  /// Return an iterator range over the operation within this block excluding
201  /// the terminator operation at the end.
203  if (begin() == end())
204  return {begin(), end()};
205  auto endIt = --end();
206  return {begin(), endIt};
207  }
208 
209  //===--------------------------------------------------------------------===//
210  // Terminator management
211  //===--------------------------------------------------------------------===//
212 
213  /// Get the terminator operation of this block. This function asserts that
214  /// the block might have a valid terminator operation.
216 
217  /// Check whether this block might have a terminator.
218  bool mightHaveTerminator();
219 
220  //===--------------------------------------------------------------------===//
221  // Predecessors and successors.
222  //===--------------------------------------------------------------------===//
223 
224  // Predecessor iteration.
228  }
229  pred_iterator pred_end() { return pred_iterator(nullptr); }
231  return {pred_begin(), pred_end()};
232  }
233 
234  /// Return true if this block has no predecessors.
235  bool hasNoPredecessors() { return pred_begin() == pred_end(); }
236 
237  /// Returns true if this blocks has no successors.
238  bool hasNoSuccessors() { return succ_begin() == succ_end(); }
239 
240  /// If this block has exactly one predecessor, return it. Otherwise, return
241  /// null.
242  ///
243  /// Note that if a block has duplicate predecessors from a single block (e.g.
244  /// if you have a conditional branch with the same block as the true/false
245  /// destinations) is not considered to be a single predecessor.
247 
248  /// If this block has a unique predecessor, i.e., all incoming edges originate
249  /// from one block, return it. Otherwise, return null.
251 
252  // Indexed successor access.
253  unsigned getNumSuccessors();
254  Block *getSuccessor(unsigned i);
255 
256  // Successor iteration.
257  using succ_iterator = SuccessorRange::iterator;
258  succ_iterator succ_begin() { return getSuccessors().begin(); }
259  succ_iterator succ_end() { return getSuccessors().end(); }
261 
262  //===--------------------------------------------------------------------===//
263  // Operation Walkers
264  //===--------------------------------------------------------------------===//
265 
266  /// Walk the operations in this block. The callback method is called for each
267  /// nested region, block or operation, depending on the callback provided.
268  /// The order in which regions, blocks and operations at the same nesting
269  /// level are visited (e.g., lexicographical or reverse lexicographical order)
270  /// is determined by 'Iterator'. The walk order for enclosing regions, blocks
271  /// and operations with respect to their nested ones is specified by 'Order'
272  /// (post-order by default). A callback on a block or operation is allowed to
273  /// erase that block or operation if either:
274  /// * the walk is in post-order, or
275  /// * the walk is in pre-order and the walk is skipped after the erasure.
276  /// See Operation::walk for more details.
277  template <WalkOrder Order = WalkOrder::PostOrder,
278  typename Iterator = ForwardIterator, typename FnT,
279  typename RetT = detail::walkResultType<FnT>>
280  RetT walk(FnT &&callback) {
281  return walk<Order, Iterator>(begin(), end(), std::forward<FnT>(callback));
282  }
283 
284  /// Walk the operations in the specified [begin, end) range of this block. The
285  /// callback method is called for each nested region, block or operation,
286  /// depending on the callback provided. The order in which regions, blocks and
287  /// operations at the same nesting level are visited (e.g., lexicographical or
288  /// reverse lexicographical order) is determined by 'Iterator'. The walk order
289  /// for enclosing regions, blocks and operations with respect to their nested
290  /// ones is specified by 'Order' (post-order by default). This method is
291  /// invoked for void-returning callbacks. A callback on a block or operation
292  /// is allowed to erase that block or operation only if the walk is in
293  /// post-order. See non-void method for pre-order erasure.
294  /// See Operation::walk for more details.
295  template <WalkOrder Order = WalkOrder::PostOrder,
296  typename Iterator = ForwardIterator, typename FnT,
297  typename RetT = detail::walkResultType<FnT>>
298  std::enable_if_t<std::is_same<RetT, void>::value, RetT>
300  for (auto &op : llvm::make_early_inc_range(llvm::make_range(begin, end)))
301  detail::walk<Order, Iterator>(&op, callback);
302  }
303 
304  /// Walk the operations in the specified [begin, end) range of this block. The
305  /// callback method is called for each nested region, block or operation,
306  /// depending on the callback provided. The order in which regions, blocks and
307  /// operations at the same nesting level are visited (e.g., lexicographical or
308  /// reverse lexicographical order) is determined by 'Iterator'. The walk order
309  /// for enclosing regions, blocks and operations with respect to their nested
310  /// ones is specified by 'Order' (post-order by default). This method is
311  /// invoked for skippable or interruptible callbacks. A callback on a block or
312  /// operation is allowed to erase that block or operation if either:
313  /// * the walk is in post-order, or
314  /// * the walk is in pre-order and the walk is skipped after the erasure.
315  /// See Operation::walk for more details.
316  template <WalkOrder Order = WalkOrder::PostOrder,
317  typename Iterator = ForwardIterator, typename FnT,
318  typename RetT = detail::walkResultType<FnT>>
319  std::enable_if_t<std::is_same<RetT, WalkResult>::value, RetT>
321  for (auto &op : llvm::make_early_inc_range(llvm::make_range(begin, end)))
322  if (detail::walk<Order, Iterator>(&op, callback).wasInterrupted())
323  return WalkResult::interrupt();
324  return WalkResult::advance();
325  }
326 
327  //===--------------------------------------------------------------------===//
328  // Other
329  //===--------------------------------------------------------------------===//
330 
331  /// Split the block into two blocks before the specified operation or
332  /// iterator.
333  ///
334  /// Note that all operations BEFORE the specified iterator stay as part of
335  /// the original basic block, and the rest of the operations in the original
336  /// block are moved to the new block, including the old terminator. The
337  /// original block is left without a terminator.
338  ///
339  /// The newly formed Block is returned, and the specified iterator is
340  /// invalidated.
341  Block *splitBlock(iterator splitBefore);
342  Block *splitBlock(Operation *splitBeforeOp) {
343  return splitBlock(iterator(splitBeforeOp));
344  }
345 
346  /// Returns pointer to member of operation list.
348  return &Block::operations;
349  }
350 
351  void print(raw_ostream &os);
352  void print(raw_ostream &os, AsmState &state);
353  void dump();
354 
355  /// Print out the name of the block without printing its body.
356  /// NOTE: The printType argument is ignored. We keep it for compatibility
357  /// with LLVM dominator machinery that expects it to exist.
358  void printAsOperand(raw_ostream &os, bool printType = true);
359  void printAsOperand(raw_ostream &os, AsmState &state);
360 
361 private:
362  /// Pair of the parent object that owns this block and a bit that signifies if
363  /// the operations within this block have a valid ordering.
364  llvm::PointerIntPair<Region *, /*IntBits=*/1, bool> parentValidOpOrderPair;
365 
366  /// This is the list of operations in the block.
367  OpListType operations;
368 
369  /// This is the list of arguments to the block.
370  std::vector<BlockArgument> arguments;
371 
372  Block(Block &) = delete;
373  void operator=(Block &) = delete;
374 
375  friend struct llvm::ilist_traits<Block>;
376 };
377 } // namespace mlir
378 
379 #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:310
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:130
std::enable_if_t< std::is_same< RetT, void >::value, RetT > walk(Block::iterator begin, Block::iterator end, FnT &&callback)
Walk the operations in the specified [begin, end) range of this block.
Definition: Block.h:299
OpListType::iterator iterator
Definition: Block.h:133
Block * splitBlock(Operation *splitBeforeOp)
Definition: Block.h:342
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:68
ValueTypeRange< BlockArgListType > getArgumentTypes()
Return a range containing the types of the arguments for this block.
Definition: Block.cpp:143
unsigned getNumSuccessors()
Definition: Block.cpp:249
void push_front(Operation *op)
Definition: Block.h:143
SuccessorRange::iterator succ_iterator
Definition: Block.h:257
bool empty()
Definition: Block.h:141
BlockArgument getArgument(unsigned i)
Definition: Block.h:122
bool hasNoSuccessors()
Returns true if this blocks has no successors.
Definition: Block.h:238
unsigned getNumArguments()
Definition: Block.h:121
Operation & back()
Definition: Block.h:145
void erase()
Unlink this Block from its parent region and delete it.
Definition: Block.cpp:60
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:181
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:154
Block * splitBlock(iterator splitBefore)
Split the block into two blocks before the specified operation or iterator.
Definition: Block.cpp:302
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:98
op_iterator< OpT > op_begin()
Definition: Block.h:192
BlockArgListType::reverse_iterator reverse_args_iterator
Definition: Block.h:86
args_iterator args_end()
Definition: Block.h:88
succ_iterator succ_end()
Definition: Block.h:259
pred_iterator pred_begin()
Definition: Block.h:226
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:88
bool verifyOpOrder()
Verifies the current ordering of child operations matches the validOpOrder flag.
Definition: Block.cpp:109
SuccessorRange getSuccessors()
Definition: Block.h:260
void invalidateOpOrder()
Invalidates the current ordering of operations.
Definition: Block.cpp:101
Block * getSinglePredecessor()
If this block has exactly one predecessor, return it.
Definition: Block.cpp:264
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:90
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:238
succ_iterator succ_begin()
Definition: Block.h:258
iterator_range< pred_iterator > getPredecessors()
Definition: Block.h:230
BlockArgument addArgument(Type type, Location loc)
Add one value to the argument list.
Definition: Block.cpp:147
RetT walk(FnT &&callback)
Walk the operations in this block.
Definition: Block.h:280
void clear()
Definition: Block.h:35
std::enable_if_t< std::is_same< RetT, WalkResult >::value, RetT > walk(Block::iterator begin, Block::iterator end, FnT &&callback)
Walk the operations in the specified [begin, end) range of this block.
Definition: Block.h:320
void eraseArguments(unsigned start, unsigned num)
Erases 'num' arguments from the index 'start'.
Definition: Block.cpp:195
reverse_iterator rend()
Definition: Block.h:139
OpListType & getOperations()
Definition: Block.h:130
void print(raw_ostream &os)
bool args_empty()
Definition: Block.h:92
bool mightHaveTerminator()
Check whether this block might have a terminator.
Definition: Block.cpp:244
BlockArgListType getArguments()
Definition: Block.h:80
PredecessorIterator pred_iterator
Definition: Block.h:225
Operation & front()
Definition: Block.h:146
iterator end()
Definition: Block.h:137
iterator begin()
Definition: Block.h:136
Block * getUniquePredecessor()
If this block has a unique predecessor, i.e., all incoming edges originate from one block,...
Definition: Block.cpp:275
op_iterator< OpT > op_end()
Definition: Block.h:196
void eraseArgument(unsigned index)
Erase the argument at 'index' and remove it from the argument list.
Definition: Block.cpp:187
iterator_range< op_iterator< OpT > > getOps()
Return an iterator range over the operations within this block that are of 'OpT'.
Definition: Block.h:186
Block * getSuccessor(unsigned i)
Definition: Block.cpp:253
args_iterator args_begin()
Definition: Block.h:87
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:83
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:229
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:142
reverse_args_iterator args_rbegin()
Definition: Block.h:89
bool hasNoPredecessors()
Return true if this block has no predecessors.
Definition: Block.h:235
static OpListType Block::* getSublistAccess(Operation *)
Returns pointer to member of operation list.
Definition: Block.h:347
iterator_range< iterator > without_terminator()
Return an iterator range over the operation within this block excluding the terminator operation at t...
Definition: Block.h:202
Operation * getParentOp()
Returns the closest surrounding operation that contains this block.
Definition: Block.cpp:30
BlockArgListType::iterator args_iterator
Definition: Block.h:85
reverse_iterator rbegin()
Definition: Block.h:138
OpListType::reverse_iterator reverse_iterator
Definition: Block.h:134
llvm::iplist< Operation > OpListType
This is the list of operations in the block.
Definition: Block.h:129
This class represents a single IR object that contains a use list.
Definition: UseDefLists.h:185
BlockOperand * getFirstUse() const
Return the first operand that is using this value, for use by custom use/def iterators.
Definition: UseDefLists.h:271
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
This header declares functions that assist transformations in the MemRef dialect.
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