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