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