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