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
14using namespace mlir;
15
16//===----------------------------------------------------------------------===//
17// Block
18//===----------------------------------------------------------------------===//
19
20Block::~Block() {
21 assert(!verifyOpOrder() && "Expected valid operation ordering.");
22 clear();
23 for (BlockArgument arg : arguments)
24 arg.destroy();
25}
26
27Region *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.
31Operation *Block::getParentOp() {
32 return getParent() ? getParent()->getParentOp() : nullptr;
33}
34
35/// Return if this block is the entry block in the parent region.
36bool 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.
40void 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(where: block->getIterator(), New: this);
44}
45
46void 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(where: block->getIterator(), New: this);
50}
51
52/// Unlink this block from its current region and insert it right before the
53/// specific block.
54void Block::moveBefore(Block *block) {
55 assert(block->getParent() && "cannot insert before a block without a parent");
56 moveBefore(region: block->getParent(), iterator: 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.
61void Block::moveBefore(Region *region, llvm::iplist<Block>::iterator iterator) {
62 region->getBlocks().splice(where: iterator, L2&: getParent()->getBlocks(), first: getIterator());
63}
64
65/// Unlink this Block from its parent Region and delete it.
66void Block::erase() {
67 assert(getParent() && "Block has no parent");
68 getParent()->getBlocks().erase(IT: 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.
74Operation *Block::findAncestorOpInBlock(Operation &op) {
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.
89void Block::dropAllReferences() {
90 for (Operation &i : *this)
91 i.dropAllReferences();
92}
93
94void Block::dropAllDefinedValueUses() {
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.
104bool Block::isOpOrderValid() { return parentValidOpOrderPair.getInt(); }
105
106/// Invalidates the current ordering of operations.
107void Block::invalidateOpOrder() {
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.
115bool Block::verifyOpOrder() {
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(C&: 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.
136void Block::recomputeOpOrder() {
137 parentValidOpOrderPair.setInt(true);
138
139 unsigned orderIndex = 0;
140 for (auto &op : *this)
141 op.orderIndex = (orderIndex += Operation::kOrderStride);
142}
143
144unsigned Block::computeBlockNumber() {
145 assert(getParent() && "cannot compute block number of detached block");
146 return std::distance(first: getParent()->begin(), last: getIterator());
147}
148
149//===----------------------------------------------------------------------===//
150// Argument list management.
151//===----------------------------------------------------------------------===//
152
153/// Return a range containing the types of the arguments for this block.
154auto Block::getArgumentTypes() -> ValueTypeRange<BlockArgListType> {
155 return ValueTypeRange<BlockArgListType>(getArguments());
156}
157
158BlockArgument Block::addArgument(Type type, Location loc) {
159 BlockArgument arg = BlockArgument::create(type, owner: this, index: arguments.size(), loc);
160 arguments.push_back(x: arg);
161 return arg;
162}
163
164/// Add one argument to the argument list for each type specified in the list.
165auto Block::addArguments(TypeRange types, ArrayRef<Location> locs)
166 -> iterator_range<args_iterator> {
167 assert(types.size() == locs.size() &&
168 "incorrect number of block argument locations");
169 size_t initialSize = arguments.size();
170 arguments.reserve(n: initialSize + types.size());
171
172 for (auto typeAndLoc : llvm::zip(t&: types, u&: locs))
173 addArgument(type: std::get<0>(t&: typeAndLoc), loc: std::get<1>(t&: typeAndLoc));
174 return {arguments.data() + initialSize, arguments.data() + arguments.size()};
175}
176
177BlockArgument Block::insertArgument(unsigned index, Type type, Location loc) {
178 assert(index <= arguments.size() && "invalid insertion index");
179
180 auto arg = BlockArgument::create(type, owner: this, index, loc);
181 arguments.insert(position: arguments.begin() + index, x: arg);
182 // Update the cached position for all the arguments after the newly inserted
183 // one.
184 ++index;
185 for (BlockArgument arg : llvm::drop_begin(RangeOrContainer&: arguments, N: index))
186 arg.setArgNumber(index++);
187 return arg;
188}
189
190/// Insert one value to the given position of the argument list. The existing
191/// arguments are shifted. The block is expected not to have predecessors.
192BlockArgument Block::insertArgument(args_iterator it, Type type, Location loc) {
193 assert(getPredecessors().empty() &&
194 "cannot insert arguments to blocks with predecessors");
195 return insertArgument(index: it->getArgNumber(), type, loc);
196}
197
198void Block::eraseArgument(unsigned index) {
199 assert(index < arguments.size());
200 arguments[index].destroy();
201 arguments.erase(position: arguments.begin() + index);
202 for (BlockArgument arg : llvm::drop_begin(RangeOrContainer&: arguments, N: index))
203 arg.setArgNumber(index++);
204}
205
206void Block::eraseArguments(unsigned start, unsigned num) {
207 assert(start + num <= arguments.size());
208 for (unsigned i = 0; i < num; ++i)
209 arguments[start + i].destroy();
210 arguments.erase(first: arguments.begin() + start, last: arguments.begin() + start + num);
211 for (BlockArgument arg : llvm::drop_begin(RangeOrContainer&: arguments, N: start))
212 arg.setArgNumber(start++);
213}
214
215void Block::eraseArguments(const BitVector &eraseIndices) {
216 eraseArguments(
217 shouldEraseFn: [&](BlockArgument arg) { return eraseIndices.test(Idx: arg.getArgNumber()); });
218}
219
220void Block::eraseArguments(function_ref<bool(BlockArgument)> shouldEraseFn) {
221 auto firstDead = llvm::find_if(Range&: arguments, P: shouldEraseFn);
222 if (firstDead == arguments.end())
223 return;
224
225 // Destroy the first dead argument, this avoids reapplying the predicate to
226 // it.
227 unsigned index = firstDead->getArgNumber();
228 firstDead->destroy();
229
230 // Iterate the remaining arguments to remove any that are now dead.
231 for (auto it = std::next(x: firstDead), e = arguments.end(); it != e; ++it) {
232 // Destroy dead arguments, and shift those that are still live.
233 if (shouldEraseFn(*it)) {
234 it->destroy();
235 } else {
236 it->setArgNumber(index++);
237 *firstDead++ = *it;
238 }
239 }
240 arguments.erase(first: firstDead, last: arguments.end());
241}
242
243//===----------------------------------------------------------------------===//
244// Terminator management
245//===----------------------------------------------------------------------===//
246
247/// Get the terminator operation of this block. This function asserts that
248/// the block might have a valid terminator operation.
249Operation *Block::getTerminator() {
250 assert(mightHaveTerminator());
251 return &back();
252}
253
254/// Check whether this block might have a terminator.
255bool Block::mightHaveTerminator() {
256 return !empty() && back().mightHaveTrait<OpTrait::IsTerminator>();
257}
258
259iterator_range<Block::iterator> Block::without_terminator_impl() {
260 // Note: When the op is unregistered, we do not know for sure if the last
261 // op is a terminator. In that case, we include it in `without_terminator`,
262 // but that decision is somewhat arbitrary.
263 if (!back().hasTrait<OpTrait::IsTerminator>())
264 return {begin(), end()};
265 auto endIt = --end();
266 return {begin(), endIt};
267}
268
269// Indexed successor access.
270unsigned Block::getNumSuccessors() {
271 return empty() ? 0 : back().getNumSuccessors();
272}
273
274Block *Block::getSuccessor(unsigned i) {
275 assert(i < getNumSuccessors());
276 return getTerminator()->getSuccessor(index: i);
277}
278
279/// If this block has exactly one predecessor, return it. Otherwise, return
280/// null.
281///
282/// Note that multiple edges from a single block (e.g. if you have a cond
283/// branch with the same block as the true/false destinations) is not
284/// considered to be a single predecessor.
285Block *Block::getSinglePredecessor() {
286 auto it = pred_begin();
287 if (it == pred_end())
288 return nullptr;
289 auto *firstPred = *it;
290 ++it;
291 return it == pred_end() ? firstPred : nullptr;
292}
293
294/// If this block has a unique predecessor, i.e., all incoming edges originate
295/// from one block, return it. Otherwise, return null.
296Block *Block::getUniquePredecessor() {
297 auto it = pred_begin(), e = pred_end();
298 if (it == e)
299 return nullptr;
300
301 // Check for any conflicting predecessors.
302 auto *firstPred = *it;
303 for (++it; it != e; ++it)
304 if (*it != firstPred)
305 return nullptr;
306 return firstPred;
307}
308
309//===----------------------------------------------------------------------===//
310// Other
311//===----------------------------------------------------------------------===//
312
313/// Split the block into two blocks before the specified operation or
314/// iterator.
315///
316/// Note that all operations BEFORE the specified iterator stay as part of
317/// the original basic block, and the rest of the operations in the original
318/// block are moved to the new block, including the old terminator. The
319/// original block is left without a terminator.
320///
321/// The newly formed Block is returned, and the specified iterator is
322/// invalidated.
323Block *Block::splitBlock(iterator splitBefore) {
324 // Start by creating a new basic block, and insert it immediate after this
325 // one in the containing region.
326 auto *newBB = new Block();
327 getParent()->getBlocks().insert(where: std::next(x: Region::iterator(this)), New: newBB);
328
329 // Move all of the operations from the split point to the end of the region
330 // into the new block.
331 newBB->getOperations().splice(where: newBB->end(), L2&: getOperations(), first: splitBefore,
332 last: end());
333 return newBB;
334}
335
336//===----------------------------------------------------------------------===//
337// Predecessors
338//===----------------------------------------------------------------------===//
339
340Block *PredecessorIterator::unwrap(BlockOperand &value) {
341 return value.getOwner()->getBlock();
342}
343
344/// Get the successor number in the predecessor terminator.
345unsigned PredecessorIterator::getSuccessorIndex() const {
346 return I->getOperandNumber();
347}
348
349//===----------------------------------------------------------------------===//
350// Successors
351//===----------------------------------------------------------------------===//
352
353SuccessorRange::SuccessorRange() : SuccessorRange(nullptr, 0) {}
354
355SuccessorRange::SuccessorRange(Block *block) : SuccessorRange() {
356 if (block->empty() || llvm::hasSingleElement(C&: *block->getParent()))
357 return;
358 Operation *term = &block->back();
359 if ((count = term->getNumSuccessors()))
360 base = term->getBlockOperands().data();
361}
362
363SuccessorRange::SuccessorRange(Operation *term) : SuccessorRange() {
364 if ((count = term->getNumSuccessors()))
365 base = term->getBlockOperands().data();
366}
367
368bool Block::isReachable(Block *other, SmallPtrSet<Block *, 16> &&except) {
369 assert(getParent() == other->getParent() && "expected same region");
370 if (except.contains(Ptr: other)) {
371 // Fast path: If `other` is in the `except` set, there can be no path from
372 // "this" to `other` (that does not pass through an excluded block).
373 return false;
374 }
375 SmallVector<Block *> worklist(succ_begin(), succ_end());
376 while (!worklist.empty()) {
377 Block *next = worklist.pop_back_val();
378 if (next == other)
379 return true;
380 // Note: `except` keeps track of already visited blocks.
381 if (!except.insert(Ptr: next).second)
382 continue;
383 worklist.append(in_start: next->succ_begin(), in_end: next->succ_end());
384 }
385 return false;
386}
387
388//===----------------------------------------------------------------------===//
389// BlockRange
390//===----------------------------------------------------------------------===//
391
392BlockRange::BlockRange(ArrayRef<Block *> blocks) : BlockRange(nullptr, 0) {
393 if ((count = blocks.size()))
394 base = blocks.data();
395}
396
397BlockRange::BlockRange(SuccessorRange successors)
398 : BlockRange(successors.begin().getBase(), successors.size()) {}
399
400/// See `llvm::detail::indexed_accessor_range_base` for details.
401BlockRange::OwnerT BlockRange::offset_base(OwnerT object, ptrdiff_t index) {
402 if (auto *operand = llvm::dyn_cast_if_present<BlockOperand *>(Val&: object))
403 return {operand + index};
404 return {llvm::dyn_cast_if_present<Block *const *>(Val&: object) + index};
405}
406
407/// See `llvm::detail::indexed_accessor_range_base` for details.
408Block *BlockRange::dereference_iterator(OwnerT object, ptrdiff_t index) {
409 if (const auto *operand = llvm::dyn_cast_if_present<BlockOperand *>(Val&: object))
410 return operand[index].get();
411 return llvm::dyn_cast_if_present<Block *const *>(Val&: object)[index];
412}
413