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