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