408 lines · cpp
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-exception6//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// Block18//===----------------------------------------------------------------------===//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 or30/// 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 the39/// 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(block->getIterator(), 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(block->getIterator(), this);50}51 52/// Unlink this block from its current region and insert it right before the53/// specific block.54void 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 the60/// 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(iterator, getParent()->getBlocks(), 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(this);69}70 71/// Returns 'op' if 'op' lies in this block, or otherwise finds the72/// ancestor operation of 'op' that lies in this block. Returns nullptr if73/// the latter fails.74Operation *Block::findAncestorOpInBlock(Operation &op) {75 // Traverse up the operation hierarchy starting from the owner of operand to76 // 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 is87/// an essential step in breaking cyclic dependences between references when88/// 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, false103/// 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 the114/// 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(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 as126 // 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 144//===----------------------------------------------------------------------===//145// Argument list management.146//===----------------------------------------------------------------------===//147 148/// Return a range containing the types of the arguments for this block.149auto Block::getArgumentTypes() -> ValueTypeRange<BlockArgListType> {150 return ValueTypeRange<BlockArgListType>(getArguments());151}152 153BlockArgument Block::addArgument(Type type, Location loc) {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.160auto Block::addArguments(TypeRange types, ArrayRef<Location> locs)161 -> iterator_range<args_iterator> {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 172BlockArgument 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 inserted178 // 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 existing186/// arguments are shifted. The block is expected not to have predecessors.187BlockArgument Block::insertArgument(args_iterator it, Type type, Location loc) {188 assert(getPredecessors().empty() &&189 "cannot insert arguments to blocks with predecessors");190 return insertArgument(it->getArgNumber(), type, loc);191}192 193void 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 201void 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 210void Block::eraseArguments(const BitVector &eraseIndices) {211 eraseArguments(212 [&](BlockArgument arg) { return eraseIndices.test(arg.getArgNumber()); });213}214 215void Block::eraseArguments(function_ref<bool(BlockArgument)> shouldEraseFn) {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 to221 // 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 management240//===----------------------------------------------------------------------===//241 242/// Get the terminator operation of this block. This function asserts that243/// the block might have a valid terminator operation.244Operation *Block::getTerminator() {245 assert(mightHaveTerminator());246 return &back();247}248 249/// Check whether this block might have a terminator.250bool Block::mightHaveTerminator() {251 return !empty() && back().mightHaveTrait<OpTrait::IsTerminator>();252}253 254iterator_range<Block::iterator> Block::without_terminator_impl() {255 // Note: When the op is unregistered, we do not know for sure if the last256 // op is a terminator. In that case, we include it in `without_terminator`,257 // but that decision is somewhat arbitrary.258 if (!back().hasTrait<OpTrait::IsTerminator>())259 return {begin(), end()};260 auto endIt = --end();261 return {begin(), endIt};262}263 264// Indexed successor access.265unsigned Block::getNumSuccessors() {266 return empty() ? 0 : back().getNumSuccessors();267}268 269Block *Block::getSuccessor(unsigned i) {270 assert(i < getNumSuccessors());271 return getTerminator()->getSuccessor(i);272}273 274/// If this block has exactly one predecessor, return it. Otherwise, return275/// null.276///277/// Note that multiple edges from a single block (e.g. if you have a cond278/// branch with the same block as the true/false destinations) is not279/// considered to be a single predecessor.280Block *Block::getSinglePredecessor() {281 auto it = pred_begin();282 if (it == pred_end())283 return nullptr;284 auto *firstPred = *it;285 ++it;286 return it == pred_end() ? firstPred : nullptr;287}288 289/// If this block has a unique predecessor, i.e., all incoming edges originate290/// from one block, return it. Otherwise, return null.291Block *Block::getUniquePredecessor() {292 auto it = pred_begin(), e = pred_end();293 if (it == e)294 return nullptr;295 296 // Check for any conflicting predecessors.297 auto *firstPred = *it;298 for (++it; it != e; ++it)299 if (*it != firstPred)300 return nullptr;301 return firstPred;302}303 304//===----------------------------------------------------------------------===//305// Other306//===----------------------------------------------------------------------===//307 308/// Split the block into two blocks before the specified operation or309/// iterator.310///311/// Note that all operations BEFORE the specified iterator stay as part of312/// the original basic block, and the rest of the operations in the original313/// block are moved to the new block, including the old terminator. The314/// original block is left without a terminator.315///316/// The newly formed Block is returned, and the specified iterator is317/// invalidated.318Block *Block::splitBlock(iterator splitBefore) {319 // Start by creating a new basic block, and insert it immediate after this320 // one in the containing region.321 auto *newBB = new Block();322 getParent()->getBlocks().insert(std::next(Region::iterator(this)), newBB);323 324 // Move all of the operations from the split point to the end of the region325 // into the new block.326 newBB->getOperations().splice(newBB->end(), getOperations(), splitBefore,327 end());328 return newBB;329}330 331//===----------------------------------------------------------------------===//332// Predecessors333//===----------------------------------------------------------------------===//334 335Block *PredecessorIterator::unwrap(BlockOperand &value) {336 return value.getOwner()->getBlock();337}338 339/// Get the successor number in the predecessor terminator.340unsigned PredecessorIterator::getSuccessorIndex() const {341 return I->getOperandNumber();342}343 344//===----------------------------------------------------------------------===//345// Successors346//===----------------------------------------------------------------------===//347 348SuccessorRange::SuccessorRange() : SuccessorRange(nullptr, 0) {}349 350SuccessorRange::SuccessorRange(Block *block) : SuccessorRange() {351 if (block->empty() || llvm::hasSingleElement(*block->getParent()))352 return;353 Operation *term = &block->back();354 if ((count = term->getNumSuccessors()))355 base = term->getBlockOperands().data();356}357 358SuccessorRange::SuccessorRange(Operation *term) : SuccessorRange() {359 if ((count = term->getNumSuccessors()))360 base = term->getBlockOperands().data();361}362 363bool Block::isReachable(Block *other, SmallPtrSet<Block *, 16> &&except) {364 assert(getParent() == other->getParent() && "expected same region");365 if (except.contains(other)) {366 // Fast path: If `other` is in the `except` set, there can be no path from367 // "this" to `other` (that does not pass through an excluded block).368 return false;369 }370 SmallVector<Block *> worklist(succ_begin(), succ_end());371 while (!worklist.empty()) {372 Block *next = worklist.pop_back_val();373 if (next == other)374 return true;375 // Note: `except` keeps track of already visited blocks.376 if (!except.insert(next).second)377 continue;378 worklist.append(next->succ_begin(), next->succ_end());379 }380 return false;381}382 383//===----------------------------------------------------------------------===//384// BlockRange385//===----------------------------------------------------------------------===//386 387BlockRange::BlockRange(ArrayRef<Block *> blocks) : BlockRange(nullptr, 0) {388 if ((count = blocks.size()))389 base = blocks.data();390}391 392BlockRange::BlockRange(SuccessorRange successors)393 : BlockRange(successors.begin().getBase(), successors.size()) {}394 395/// See `llvm::detail::indexed_accessor_range_base` for details.396BlockRange::OwnerT BlockRange::offset_base(OwnerT object, ptrdiff_t index) {397 if (auto *operand = llvm::dyn_cast_if_present<BlockOperand *>(object))398 return {operand + index};399 return {llvm::dyn_cast_if_present<Block *const *>(object) + index};400}401 402/// See `llvm::detail::indexed_accessor_range_base` for details.403Block *BlockRange::dereference_iterator(OwnerT object, ptrdiff_t index) {404 if (const auto *operand = llvm::dyn_cast_if_present<BlockOperand *>(object))405 return operand[index].get();406 return llvm::dyn_cast_if_present<Block *const *>(object)[index];407}408