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