MLIR  17.0.0git
Block.cpp
Go to the documentation of this file.
1 //===- Block.cpp - MLIR Block Class ---------------------------------------===//
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 #include "mlir/IR/Block.h"
10 #include "mlir/IR/Builders.h"
11 #include "mlir/IR/Operation.h"
12 #include "llvm/ADT/BitVector.h"
13 using namespace mlir;
14 
15 //===----------------------------------------------------------------------===//
16 // Block
17 //===----------------------------------------------------------------------===//
18 
20  assert(!verifyOpOrder() && "Expected valid operation ordering.");
21  clear();
22  for (BlockArgument arg : arguments)
23  arg.destroy();
24 }
25 
26 Region *Block::getParent() const { return parentValidOpOrderPair.getPointer(); }
27 
28 /// Returns the closest surrounding operation that contains this block or
29 /// nullptr if this block is unlinked.
31  return getParent() ? getParent()->getParentOp() : nullptr;
32 }
33 
34 /// Return if this block is the entry block in the parent region.
35 bool Block::isEntryBlock() { return this == &getParent()->front(); }
36 
37 /// Insert this block (which must not already be in a region) right before the
38 /// specified block.
39 void Block::insertBefore(Block *block) {
40  assert(!getParent() && "already inserted into a block!");
41  assert(block->getParent() && "cannot insert before a block without a parent");
42  block->getParent()->getBlocks().insert(block->getIterator(), this);
43 }
44 
45 /// Unlink this block from its current region and insert it right before the
46 /// specific block.
47 void Block::moveBefore(Block *block) {
48  assert(block->getParent() && "cannot insert before a block without a parent");
49  block->getParent()->getBlocks().splice(
50  block->getIterator(), getParent()->getBlocks(), getIterator());
51 }
52 
53 /// Unlink this Block from its parent Region and delete it.
54 void Block::erase() {
55  assert(getParent() && "Block has no parent");
56  getParent()->getBlocks().erase(this);
57 }
58 
59 /// Returns 'op' if 'op' lies in this block, or otherwise finds the
60 /// ancestor operation of 'op' that lies in this block. Returns nullptr if
61 /// the latter fails.
63  // Traverse up the operation hierarchy starting from the owner of operand to
64  // find the ancestor operation that resides in the block of 'forOp'.
65  auto *currOp = &op;
66  while (currOp->getBlock() != this) {
67  currOp = currOp->getParentOp();
68  if (!currOp)
69  return nullptr;
70  }
71  return currOp;
72 }
73 
74 /// This drops all operand uses from operations within this block, which is
75 /// an essential step in breaking cyclic dependences between references when
76 /// they are to be deleted.
78  for (Operation &i : *this)
80 }
81 
83  for (auto arg : getArguments())
84  arg.dropAllUses();
85  for (auto &op : *this)
86  op.dropAllDefinedValueUses();
87  dropAllUses();
88 }
89 
90 /// Returns true if the ordering of the child operations is valid, false
91 /// otherwise.
92 bool Block::isOpOrderValid() { return parentValidOpOrderPair.getInt(); }
93 
94 /// Invalidates the current ordering of operations.
96  // Validate the current ordering.
97  assert(!verifyOpOrder());
98  parentValidOpOrderPair.setInt(false);
99 }
100 
101 /// Verifies the current ordering of child operations. Returns false if the
102 /// order is valid, true otherwise.
104  // The order is already known to be invalid.
105  if (!isOpOrderValid())
106  return false;
107  // The order is valid if there are less than 2 operations.
108  if (operations.empty() || std::next(operations.begin()) == operations.end())
109  return false;
110 
111  Operation *prev = nullptr;
112  for (auto &i : *this) {
113  // The previous operation must have a smaller order index than the next as
114  // it appears earlier in the list.
115  if (prev && prev->orderIndex != Operation::kInvalidOrderIdx &&
116  prev->orderIndex >= i.orderIndex)
117  return true;
118  prev = &i;
119  }
120  return false;
121 }
122 
123 /// Recomputes the ordering of child operations within the block.
125  parentValidOpOrderPair.setInt(true);
126 
127  unsigned orderIndex = 0;
128  for (auto &op : *this)
129  op.orderIndex = (orderIndex += Operation::kOrderStride);
130 }
131 
132 //===----------------------------------------------------------------------===//
133 // Argument list management.
134 //===----------------------------------------------------------------------===//
135 
136 /// Return a range containing the types of the arguments for this block.
138  return ValueTypeRange<BlockArgListType>(getArguments());
139 }
140 
142  BlockArgument arg = BlockArgument::create(type, this, arguments.size(), loc);
143  arguments.push_back(arg);
144  return arg;
145 }
146 
147 /// Add one argument to the argument list for each type specified in the list.
150  assert(types.size() == locs.size() &&
151  "incorrect number of block argument locations");
152  size_t initialSize = arguments.size();
153  arguments.reserve(initialSize + types.size());
154 
155  for (auto typeAndLoc : llvm::zip(types, locs))
156  addArgument(std::get<0>(typeAndLoc), std::get<1>(typeAndLoc));
157  return {arguments.data() + initialSize, arguments.data() + arguments.size()};
158 }
159 
160 BlockArgument Block::insertArgument(unsigned index, Type type, Location loc) {
161  assert(index <= arguments.size() && "invalid insertion index");
162 
163  auto arg = BlockArgument::create(type, this, index, loc);
164  arguments.insert(arguments.begin() + index, arg);
165  // Update the cached position for all the arguments after the newly inserted
166  // one.
167  ++index;
168  for (BlockArgument arg : llvm::drop_begin(arguments, index))
169  arg.setArgNumber(index++);
170  return arg;
171 }
172 
173 /// Insert one value to the given position of the argument list. The existing
174 /// arguments are shifted. The block is expected not to have predecessors.
176  assert(getPredecessors().empty() &&
177  "cannot insert arguments to blocks with predecessors");
178  return insertArgument(it->getArgNumber(), type, loc);
179 }
180 
181 void Block::eraseArgument(unsigned index) {
182  assert(index < arguments.size());
183  arguments[index].destroy();
184  arguments.erase(arguments.begin() + index);
185  for (BlockArgument arg : llvm::drop_begin(arguments, index))
186  arg.setArgNumber(index++);
187 }
188 
189 void Block::eraseArguments(unsigned start, unsigned num) {
190  assert(start + num <= arguments.size());
191  for (unsigned i = 0; i < num; ++i)
192  arguments[start + i].destroy();
193  arguments.erase(arguments.begin() + start, arguments.begin() + start + num);
194  for (BlockArgument arg : llvm::drop_begin(arguments, start))
195  arg.setArgNumber(start++);
196 }
197 
198 void Block::eraseArguments(const BitVector &eraseIndices) {
200  [&](BlockArgument arg) { return eraseIndices.test(arg.getArgNumber()); });
201 }
202 
204  auto firstDead = llvm::find_if(arguments, shouldEraseFn);
205  if (firstDead == arguments.end())
206  return;
207 
208  // Destroy the first dead argument, this avoids reapplying the predicate to
209  // it.
210  unsigned index = firstDead->getArgNumber();
211  firstDead->destroy();
212 
213  // Iterate the remaining arguments to remove any that are now dead.
214  for (auto it = std::next(firstDead), e = arguments.end(); it != e; ++it) {
215  // Destroy dead arguments, and shift those that are still live.
216  if (shouldEraseFn(*it)) {
217  it->destroy();
218  } else {
219  it->setArgNumber(index++);
220  *firstDead++ = *it;
221  }
222  }
223  arguments.erase(firstDead, arguments.end());
224 }
225 
226 //===----------------------------------------------------------------------===//
227 // Terminator management
228 //===----------------------------------------------------------------------===//
229 
230 /// Get the terminator operation of this block. This function asserts that
231 /// the block has a valid terminator operation.
233  assert(!empty() && back().mightHaveTrait<OpTrait::IsTerminator>());
234  return &back();
235 }
236 
237 // Indexed successor access.
239  return empty() ? 0 : back().getNumSuccessors();
240 }
241 
243  assert(i < getNumSuccessors());
244  return getTerminator()->getSuccessor(i);
245 }
246 
247 /// If this block has exactly one predecessor, return it. Otherwise, return
248 /// null.
249 ///
250 /// Note that multiple edges from a single block (e.g. if you have a cond
251 /// branch with the same block as the true/false destinations) is not
252 /// considered to be a single predecessor.
254  auto it = pred_begin();
255  if (it == pred_end())
256  return nullptr;
257  auto *firstPred = *it;
258  ++it;
259  return it == pred_end() ? firstPred : nullptr;
260 }
261 
262 /// If this block has a unique predecessor, i.e., all incoming edges originate
263 /// from one block, return it. Otherwise, return null.
265  auto it = pred_begin(), e = pred_end();
266  if (it == e)
267  return nullptr;
268 
269  // Check for any conflicting predecessors.
270  auto *firstPred = *it;
271  for (++it; it != e; ++it)
272  if (*it != firstPred)
273  return nullptr;
274  return firstPred;
275 }
276 
277 //===----------------------------------------------------------------------===//
278 // Other
279 //===----------------------------------------------------------------------===//
280 
281 /// Split the block into two blocks before the specified operation or
282 /// iterator.
283 ///
284 /// Note that all operations BEFORE the specified iterator stay as part of
285 /// the original basic block, and the rest of the operations in the original
286 /// block are moved to the new block, including the old terminator. The
287 /// original block is left without a terminator.
288 ///
289 /// The newly formed Block is returned, and the specified iterator is
290 /// invalidated.
292  // Start by creating a new basic block, and insert it immediate after this
293  // one in the containing region.
294  auto *newBB = new Block();
295  getParent()->getBlocks().insert(std::next(Region::iterator(this)), newBB);
296 
297  // Move all of the operations from the split point to the end of the region
298  // into the new block.
299  newBB->getOperations().splice(newBB->end(), getOperations(), splitBefore,
300  end());
301  return newBB;
302 }
303 
304 //===----------------------------------------------------------------------===//
305 // Predecessors
306 //===----------------------------------------------------------------------===//
307 
308 Block *PredecessorIterator::unwrap(BlockOperand &value) {
309  return value.getOwner()->getBlock();
310 }
311 
312 /// Get the successor number in the predecessor terminator.
314  return I->getOperandNumber();
315 }
316 
317 //===----------------------------------------------------------------------===//
318 // SuccessorRange
319 //===----------------------------------------------------------------------===//
320 
322 
324  if (block->empty() || llvm::hasSingleElement(*block->getParent()))
325  return;
326  Operation *term = &block->back();
327  if ((count = term->getNumSuccessors()))
328  base = term->getBlockOperands().data();
329 }
330 
332  if ((count = term->getNumSuccessors()))
333  base = term->getBlockOperands().data();
334 }
335 
336 //===----------------------------------------------------------------------===//
337 // BlockRange
338 //===----------------------------------------------------------------------===//
339 
341  if ((count = blocks.size()))
342  base = blocks.data();
343 }
344 
346  : BlockRange(successors.begin().getBase(), successors.size()) {}
347 
348 /// See `llvm::detail::indexed_accessor_range_base` for details.
349 BlockRange::OwnerT BlockRange::offset_base(OwnerT object, ptrdiff_t index) {
350  if (auto *operand = object.dyn_cast<BlockOperand *>())
351  return {operand + index};
352  return {object.dyn_cast<Block *const *>() + index};
353 }
354 
355 /// See `llvm::detail::indexed_accessor_range_base` for details.
356 Block *BlockRange::dereference_iterator(OwnerT object, ptrdiff_t index) {
357  if (const auto *operand = object.dyn_cast<BlockOperand *>())
358  return operand[index].get();
359  return object.dyn_cast<Block *const *>()[index];
360 }
This class represents an argument of a Block.
Definition: Value.h:304
unsigned getArgNumber() const
Returns the number of this argument.
Definition: Value.h:316
A block operand represents an operand that holds a reference to a Block, e.g.
Definition: BlockSupport.h:30
This class provides an abstraction over the different types of ranges over Blocks.
Definition: BlockSupport.h:106
BlockRange(ArrayRef< Block * > blocks=std::nullopt)
Definition: Block.cpp:340
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:124
OpListType::iterator iterator
Definition: Block.h:129
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:62
ValueTypeRange< BlockArgListType > getArgumentTypes()
Return a range containing the types of the arguments for this block.
Definition: Block.cpp:137
unsigned getNumSuccessors()
Definition: Block.cpp:238
bool empty()
Definition: Block.h:137
Operation & back()
Definition: Block.h:141
void erase()
Unlink this Block from its parent region and delete it.
Definition: Block.cpp:54
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:175
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:148
Block * splitBlock(iterator splitBefore)
Split the block into two blocks before the specified operation or iterator.
Definition: Block.cpp:291
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:92
pred_iterator pred_begin()
Definition: Block.h:219
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:82
bool verifyOpOrder()
Verifies the current ordering of child operations matches the validOpOrder flag.
Definition: Block.cpp:103
void invalidateOpOrder()
Invalidates the current ordering of operations.
Definition: Block.cpp:95
Block * getSinglePredecessor()
If this block has exactly one predecessor, return it.
Definition: Block.cpp:253
Operation * getTerminator()
Get the terminator operation of this block.
Definition: Block.cpp:232
iterator_range< pred_iterator > getPredecessors()
Definition: Block.h:223
BlockArgument addArgument(Type type, Location loc)
Add one value to the argument list.
Definition: Block.cpp:141
void clear()
Definition: Block.h:35
void eraseArguments(unsigned start, unsigned num)
Erases 'num' arguments from the index 'start'.
Definition: Block.cpp:189
OpListType & getOperations()
Definition: Block.h:126
BlockArgListType getArguments()
Definition: Block.h:76
iterator end()
Definition: Block.h:133
Block * getUniquePredecessor()
If this block has a unique predecessor, i.e., all incoming edges originate from one block,...
Definition: Block.cpp:264
void eraseArgument(unsigned index)
Erase the argument at 'index' and remove it from the argument list.
Definition: Block.cpp:181
Block * getSuccessor(unsigned i)
Definition: Block.cpp:242
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:77
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:222
void moveBefore(Block *block)
Unlink this block from its current region and insert it right before the specific block.
Definition: Block.cpp:47
Operation * getParentOp()
Returns the closest surrounding operation that contains this block.
Definition: Block.cpp:30
BlockArgListType::iterator args_iterator
Definition: Block.h:81
void dropAllUses()
Drop all uses of this object from their respective owners.
Definition: UseDefLists.h:179
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:75
Block * getSuccessor(unsigned index)
Definition: Operation.h:572
unsigned getNumSuccessors()
Definition: Operation.h:570
void dropAllReferences()
This drops all operand uses from this operation, which is an essential step in breaking cyclic depend...
Definition: Operation.cpp:472
Operation * getParentOp()
Returns the closest surrounding operation that contains this operation or nullptr if this is a top-le...
Definition: Operation.h:218
Block * getBlock()
Returns the operation block that contains this operation.
Definition: Operation.h:197
MutableArrayRef< BlockOperand > getBlockOperands()
Definition: Operation.h:559
unsigned getSuccessorIndex() const
Get the successor number in the predecessor terminator.
Definition: Block.cpp:313
This class contains a list of basic blocks and a link to the parent operation it is attached to.
Definition: Region.h:26
Operation * getParentOp()
Return the parent operation this region is attached to.
Definition: Region.h:200
BlockListType & getBlocks()
Definition: Region.h:45
Block & front()
Definition: Region.h:65
BlockListType::iterator iterator
Definition: Region.h:52
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
Operation * getOwner() const
Return the owner of this operand.
Definition: UseDefLists.h:40
This header declares functions that assit transformations in the MemRef dialect.