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

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