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"
13using namespace mlir;
14
15//===----------------------------------------------------------------------===//
16// Block
17//===----------------------------------------------------------------------===//
18
19Block::~Block() {
20 assert(!verifyOpOrder() && "Expected valid operation ordering.");
21 clear();
22 for (BlockArgument arg : arguments)
23 arg.destroy();
24}
25
26Region *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.
30Operation *Block::getParentOp() {
31 return getParent() ? getParent()->getParentOp() : nullptr;
32}
33
34/// Return if this block is the entry block in the parent region.
35bool 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.
39void 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(where: block->getIterator(), New: this);
43}
44
45void 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(where: block->getIterator(), New: this);
49}
50
51/// Unlink this block from its current region and insert it right before the
52/// specific block.
53void Block::moveBefore(Block *block) {
54 assert(block->getParent() && "cannot insert before a block without a parent");
55 moveBefore(region: block->getParent(), iterator: 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.
60void Block::moveBefore(Region *region, llvm::iplist<Block>::iterator iterator) {
61 region->getBlocks().splice(where: iterator, L2&: getParent()->getBlocks(), first: getIterator());
62}
63
64/// Unlink this Block from its parent Region and delete it.
65void Block::erase() {
66 assert(getParent() && "Block has no parent");
67 getParent()->getBlocks().erase(IT: 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.
73Operation *Block::findAncestorOpInBlock(Operation &op) {
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.
88void Block::dropAllReferences() {
89 for (Operation &i : *this)
90 i.dropAllReferences();
91}
92
93void Block::dropAllDefinedValueUses() {
94 for (auto arg : getArguments())
95 arg.dropAllUses();
96 for (auto &op : *this)
97 op.dropAllDefinedValueUses();
98 dropAllUses();
99}
100
101/// Returns true if the ordering of the child operations is valid, false
102/// otherwise.
103bool Block::isOpOrderValid() { return parentValidOpOrderPair.getInt(); }
104
105/// Invalidates the current ordering of operations.
106void Block::invalidateOpOrder() {
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.
114bool Block::verifyOpOrder() {
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(x: 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.
135void Block::recomputeOpOrder() {
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.
148auto Block::getArgumentTypes() -> ValueTypeRange<BlockArgListType> {
149 return ValueTypeRange<BlockArgListType>(getArguments());
150}
151
152BlockArgument Block::addArgument(Type type, Location loc) {
153 BlockArgument arg = BlockArgument::create(type, owner: this, index: arguments.size(), loc);
154 arguments.push_back(x: arg);
155 return arg;
156}
157
158/// Add one argument to the argument list for each type specified in the list.
159auto Block::addArguments(TypeRange types, ArrayRef<Location> locs)
160 -> iterator_range<args_iterator> {
161 assert(types.size() == locs.size() &&
162 "incorrect number of block argument locations");
163 size_t initialSize = arguments.size();
164 arguments.reserve(n: initialSize + types.size());
165
166 for (auto typeAndLoc : llvm::zip(t&: types, u&: locs))
167 addArgument(type: std::get<0>(t&: typeAndLoc), loc: std::get<1>(t&: typeAndLoc));
168 return {arguments.data() + initialSize, arguments.data() + arguments.size()};
169}
170
171BlockArgument Block::insertArgument(unsigned index, Type type, Location loc) {
172 assert(index <= arguments.size() && "invalid insertion index");
173
174 auto arg = BlockArgument::create(type, owner: this, index, loc);
175 arguments.insert(position: arguments.begin() + index, x: 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(RangeOrContainer&: arguments, N: 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.
186BlockArgument Block::insertArgument(args_iterator it, Type type, Location loc) {
187 assert(getPredecessors().empty() &&
188 "cannot insert arguments to blocks with predecessors");
189 return insertArgument(index: it->getArgNumber(), type, loc);
190}
191
192void Block::eraseArgument(unsigned index) {
193 assert(index < arguments.size());
194 arguments[index].destroy();
195 arguments.erase(position: arguments.begin() + index);
196 for (BlockArgument arg : llvm::drop_begin(RangeOrContainer&: arguments, N: index))
197 arg.setArgNumber(index++);
198}
199
200void 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(first: arguments.begin() + start, last: arguments.begin() + start + num);
205 for (BlockArgument arg : llvm::drop_begin(RangeOrContainer&: arguments, N: start))
206 arg.setArgNumber(start++);
207}
208
209void Block::eraseArguments(const BitVector &eraseIndices) {
210 eraseArguments(
211 shouldEraseFn: [&](BlockArgument arg) { return eraseIndices.test(Idx: arg.getArgNumber()); });
212}
213
214void Block::eraseArguments(function_ref<bool(BlockArgument)> shouldEraseFn) {
215 auto firstDead = llvm::find_if(Range&: arguments, P: 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(x: 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(first: firstDead, last: 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.
243Operation *Block::getTerminator() {
244 assert(mightHaveTerminator());
245 return &back();
246}
247
248/// Check whether this block might have a terminator.
249bool Block::mightHaveTerminator() {
250 return !empty() && back().mightHaveTrait<OpTrait::IsTerminator>();
251}
252
253// Indexed successor access.
254unsigned Block::getNumSuccessors() {
255 return empty() ? 0 : back().getNumSuccessors();
256}
257
258Block *Block::getSuccessor(unsigned i) {
259 assert(i < getNumSuccessors());
260 return getTerminator()->getSuccessor(index: 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.
269Block *Block::getSinglePredecessor() {
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.
280Block *Block::getUniquePredecessor() {
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.
307Block *Block::splitBlock(iterator splitBefore) {
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(where: std::next(x: Region::iterator(this)), New: 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(where: newBB->end(), L2&: getOperations(), first: splitBefore,
316 last: end());
317 return newBB;
318}
319
320//===----------------------------------------------------------------------===//
321// Predecessors
322//===----------------------------------------------------------------------===//
323
324Block *PredecessorIterator::unwrap(BlockOperand &value) {
325 return value.getOwner()->getBlock();
326}
327
328/// Get the successor number in the predecessor terminator.
329unsigned PredecessorIterator::getSuccessorIndex() const {
330 return I->getOperandNumber();
331}
332
333//===----------------------------------------------------------------------===//
334// SuccessorRange
335//===----------------------------------------------------------------------===//
336
337SuccessorRange::SuccessorRange() : SuccessorRange(nullptr, 0) {}
338
339SuccessorRange::SuccessorRange(Block *block) : SuccessorRange() {
340 if (block->empty() || llvm::hasSingleElement(C&: *block->getParent()))
341 return;
342 Operation *term = &block->back();
343 if ((count = term->getNumSuccessors()))
344 base = term->getBlockOperands().data();
345}
346
347SuccessorRange::SuccessorRange(Operation *term) : SuccessorRange() {
348 if ((count = term->getNumSuccessors()))
349 base = term->getBlockOperands().data();
350}
351
352//===----------------------------------------------------------------------===//
353// BlockRange
354//===----------------------------------------------------------------------===//
355
356BlockRange::BlockRange(ArrayRef<Block *> blocks) : BlockRange(nullptr, 0) {
357 if ((count = blocks.size()))
358 base = blocks.data();
359}
360
361BlockRange::BlockRange(SuccessorRange successors)
362 : BlockRange(successors.begin().getBase(), successors.size()) {}
363
364/// See `llvm::detail::indexed_accessor_range_base` for details.
365BlockRange::OwnerT BlockRange::offset_base(OwnerT object, ptrdiff_t index) {
366 if (auto *operand = llvm::dyn_cast_if_present<BlockOperand *>(Val&: object))
367 return {operand + index};
368 return {llvm::dyn_cast_if_present<Block *const *>(Val&: object) + index};
369}
370
371/// See `llvm::detail::indexed_accessor_range_base` for details.
372Block *BlockRange::dereference_iterator(OwnerT object, ptrdiff_t index) {
373 if (const auto *operand = llvm::dyn_cast_if_present<BlockOperand *>(Val&: object))
374 return operand[index].get();
375 return llvm::dyn_cast_if_present<Block *const *>(Val&: object)[index];
376}
377

source code of mlir/lib/IR/Block.cpp