1353 lines · cpp
1//===- CFGToSCF.h - Control Flow Graph to Structured Control Flow *- C++ -*===//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// This code is an implementation of:10// Helge Bahmann, Nico Reissmann, Magnus Jahre, and Jan Christian Meyer. 2015.11// Perfect Reconstructability of Control Flow from Demand Dependence Graphs. ACM12// Trans. Archit. Code Optim. 11, 4, Article 66 (January 2015), 25 pages.13// https://doi.org/10.1145/269326114//15// It defines an algorithm to translate any control flow graph with a single16// entry and single exit block into structured control flow operations17// consisting of regions of do-while loops and operations conditionally18// dispatching to one out of multiple regions before continuing after the19// operation. This includes control flow graphs containing irreducible20// control flow.21//22// The implementation here additionally supports the transformation on23// regions with multiple exit blocks. This is implemented by first24// transforming all occurrences of return-like operations to branch to a25// single exit block containing an instance of that return-like operation.26// If there are multiple kinds of return-like operations, multiple exit27// blocks are created. In that case the transformation leaves behind a28// conditional control flow graph operation that dispatches to the given regions29// terminating with different kinds of return-like operations each.30//31// If the function only contains a single kind of return-like operations,32// it is guaranteed that all control flow graph ops will be lifted to structured33// control flow, and that no more control flow graph ops remain after the34// operation.35//36// The algorithm to lift CFGs consists of two transformations applied after each37// other on any single-entry, single-exit region:38// 1) Lifting cycles to structured control flow loops39// 2) Lifting conditional branches to structured control flow branches40// These are then applied recursively on any new single-entry single-exit41// regions created by the transformation until no more CFG operations remain.42//43// The first part of cycle lifting is to detect any cycles in the CFG.44// This is done using an algorithm for iterating over SCCs. Every SCC45// representing a cycle is then transformed into a structured loop with a single46// entry block and a single latch containing the only back edge to the entry47// block and the only edge to an exit block outside the loop. Rerouting control48// flow to create single entry and exit blocks is achieved via a multiplexer49// construct that can be visualized as follows:50// +-----+ +-----+ +-----+51// | bb0 | | bb1 |...| bbN |52// +--+--+ +--+--+ +-+---+53// | | |54// | v |55// | +------+ |56// | ++ ++<----+57// | | Region |58// +>| |<----+59// ++ ++ |60// +------+------+61//62// The above transforms to:63// +-----+ +-----+ +-----+64// | bb0 | | bb1 |...| bbN |65// +-----+ +--|--+ ++----+66// | v |67// +->+-----+<---+68// | bbM |<-------+69// +---+-+ |70// +---+ | +----+ |71// | v | |72// | +------+ | |73// | ++ ++<-+ |74// +->| Region | |75// ++ ++ |76// +------+-------+77//78// bbM in the above is the multiplexer block, and any block previously branching79// to an entry block of the region are redirected to it. This includes any80// branches from within the region. Using a block argument, bbM then dispatches81// to the correct entry block of the region dependent on the predecessor.82//83// A similar transformation is done to create the latch block with the single84// back edge and loop exit edge.85//86// The above form has the advantage that bbM now acts as the loop header87// of the loop body. After the transformation on the latch, this results in a88// structured loop that can then be lifted to structured control flow. The89// conditional branches created in bbM are later lifted to conditional90// branches.91//92// Lifting conditional branches is done by analyzing the *first* conditional93// branch encountered in the entry region. The algorithm then identifies94// all blocks that are dominated by a specific control flow edge and95// the region where control flow continues:96// +-----+97// +-----+ bb0 +----+98// v +-----+ v99// Region 1 +-+-+ ... +-+-+ Region n100// +---+ +---+101// ... ...102// | |103// | +---+ |104// +---->++ ++<---+105// | |106// ++ ++ Region T107// +---+108// Every region following bb0 consists of 0 or more blocks that eventually109// branch to Region T. If there are multiple entry blocks into Region T, a110// single entry block is created using a multiplexer block as shown above.111// Region 1 to Region n are then lifted together with the conditional control112// flow operation terminating bb0 into a structured conditional operation113// followed by the operations of the entry block of Region T.114//===----------------------------------------------------------------------===//115 116#include "mlir/Transforms/CFGToSCF.h"117 118#include "mlir/Interfaces/ControlFlowInterfaces.h"119#include "mlir/Interfaces/SideEffectInterfaces.h"120#include "llvm/ADT/DepthFirstIterator.h"121#include "llvm/ADT/MapVector.h"122#include "llvm/ADT/SCCIterator.h"123#include "llvm/ADT/SetVector.h"124 125using namespace mlir;126 127/// Returns the mutable operand range used to transfer operands from `block` to128/// its successor with the given index. The returned range being mutable allows129/// us to modify the operands being transferred.130static MutableOperandRange131getMutableSuccessorOperands(Block *block, unsigned successorIndex) {132 auto branchOpInterface = cast<BranchOpInterface>(block->getTerminator());133 SuccessorOperands succOps =134 branchOpInterface.getSuccessorOperands(successorIndex);135 return succOps.getMutableForwardedOperands();136}137 138/// Return the operand range used to transfer operands from `block` to its139/// successor with the given index.140static OperandRange getSuccessorOperands(Block *block,141 unsigned successorIndex) {142 return getMutableSuccessorOperands(block, successorIndex);143}144 145/// Appends all the block arguments from `other` to the block arguments of146/// `block`, copying their types and locations.147static void addBlockArgumentsFromOther(Block *block, Block *other) {148 for (BlockArgument arg : other->getArguments())149 block->addArgument(arg.getType(), arg.getLoc());150}151 152namespace {153 154/// Class representing an edge in the CFG. Consists of a from-block, a successor155/// and corresponding successor operands passed to the block arguments of the156/// successor.157class Edge {158 Block *fromBlock;159 unsigned successorIndex;160 161public:162 /// Constructs a new edge from `fromBlock` to the successor corresponding to163 /// `successorIndex`.164 Edge(Block *fromBlock, unsigned int successorIndex)165 : fromBlock(fromBlock), successorIndex(successorIndex) {}166 167 /// Returns the from-block.168 Block *getFromBlock() const { return fromBlock; }169 170 /// Returns the successor of the edge.171 Block *getSuccessor() const {172 return fromBlock->getSuccessor(successorIndex);173 }174 175 /// Sets the successor of the edge, adjusting the terminator in the176 /// from-block.177 void setSuccessor(Block *block) const {178 fromBlock->getTerminator()->setSuccessor(block, successorIndex);179 }180 181 /// Returns the arguments of this edge that are passed to the block arguments182 /// of the successor.183 MutableOperandRange getMutableSuccessorOperands() const {184 return ::getMutableSuccessorOperands(fromBlock, successorIndex);185 }186 187 /// Returns the arguments of this edge that are passed to the block arguments188 /// of the successor.189 OperandRange getSuccessorOperands() const {190 return ::getSuccessorOperands(fromBlock, successorIndex);191 }192};193 194/// Structure containing the entry, exit and back edges of a cycle. A cycle is a195/// generalization of a loop that may have multiple entry edges. See also196/// https://llvm.org/docs/CycleTerminology.html.197struct CycleEdges {198 /// All edges from a block outside the cycle to a block inside the cycle.199 /// The targets of these edges are entry blocks.200 SmallVector<Edge> entryEdges;201 /// All edges from a block inside the cycle to a block outside the cycle.202 SmallVector<Edge> exitEdges;203 /// All edges from a block inside the cycle to an entry block.204 SmallVector<Edge> backEdges;205};206 207/// Class used to orchestrate creation of so-called edge multiplexers.208/// This class creates a new basic block and routes all inputs edges209/// to this basic block before branching to their original target.210/// The purpose of this transformation is to create single-entry,211/// single-exit regions.212class EdgeMultiplexer {213public:214 /// Creates a new edge multiplexer capable of redirecting all edges to one of215 /// the `entryBlocks`. This creates the multiplexer basic block with216 /// appropriate block arguments after the first entry block. `extraArgs`217 /// contains the types of possible extra block arguments passed to the218 /// multiplexer block that are added to the successor operands of every219 /// outgoing edge.220 ///221 /// NOTE: This does not yet redirect edges to branch to the222 /// multiplexer block nor code dispatching from the multiplexer code223 /// to the original successors.224 /// See `redirectEdge` and `createSwitch`.225 static EdgeMultiplexer create(Location loc, ArrayRef<Block *> entryBlocks,226 function_ref<Value(unsigned)> getSwitchValue,227 function_ref<Value(Type)> getUndefValue,228 TypeRange extraArgs = {}) {229 assert(!entryBlocks.empty() && "Require at least one entry block");230 231 auto *multiplexerBlock = new Block;232 multiplexerBlock->insertAfter(entryBlocks.front());233 234 // To implement the multiplexer block, we have to add the block arguments of235 // every distinct successor block to the multiplexer block. When redirecting236 // edges, block arguments designated for blocks that aren't branched to will237 // be assigned the `getUndefValue`. The amount of block arguments and their238 // offset is saved in the map for `redirectEdge` to transform the edges.239 llvm::SmallMapVector<Block *, unsigned, 4> blockArgMapping;240 for (Block *entryBlock : entryBlocks) {241 auto [iter, inserted] = blockArgMapping.insert(242 {entryBlock, multiplexerBlock->getNumArguments()});243 if (inserted)244 addBlockArgumentsFromOther(multiplexerBlock, entryBlock);245 }246 247 // If we have more than one successor, we have to additionally add a248 // discriminator value, denoting which successor to jump to.249 // When redirecting edges, an appropriate value will be passed using250 // `getSwitchValue`.251 Value discriminator;252 if (blockArgMapping.size() > 1)253 discriminator =254 multiplexerBlock->addArgument(getSwitchValue(0).getType(), loc);255 256 multiplexerBlock->addArguments(257 extraArgs, SmallVector<Location>(extraArgs.size(), loc));258 259 return EdgeMultiplexer(multiplexerBlock, getSwitchValue, getUndefValue,260 std::move(blockArgMapping), discriminator);261 }262 263 /// Returns the created multiplexer block.264 Block *getMultiplexerBlock() const { return multiplexerBlock; }265 266 /// Redirects `edge` to branch to the multiplexer block before continuing to267 /// its original target. The edges successor must have originally been part268 /// of the entry blocks array passed to the `create` function. `extraArgs`269 /// must be used to pass along any additional values corresponding to270 /// `extraArgs` in `create`.271 void redirectEdge(Edge edge, ValueRange extraArgs = {}) const {272 const auto *result = blockArgMapping.find(edge.getSuccessor());273 assert(result != blockArgMapping.end() &&274 "Edge was not originally passed to `create` method.");275 276 MutableOperandRange successorOperands = edge.getMutableSuccessorOperands();277 278 // Extra arguments are always appended at the end of the block arguments.279 unsigned extraArgsBeginIndex =280 multiplexerBlock->getNumArguments() - extraArgs.size();281 // If a discriminator exists, it is right before the extra arguments.282 std::optional<unsigned> discriminatorIndex =283 discriminator ? extraArgsBeginIndex - 1 : std::optional<unsigned>{};284 285 SmallVector<Value> newSuccOperands(multiplexerBlock->getNumArguments());286 for (BlockArgument argument : multiplexerBlock->getArguments()) {287 unsigned index = argument.getArgNumber();288 if (index >= result->second &&289 index < result->second + edge.getSuccessor()->getNumArguments()) {290 // Original block arguments to the entry block.291 newSuccOperands[index] =292 successorOperands[index - result->second].get();293 continue;294 }295 296 // Discriminator value if it exists.297 if (index == discriminatorIndex) {298 newSuccOperands[index] =299 getSwitchValue(result - blockArgMapping.begin());300 continue;301 }302 303 // Followed by the extra arguments.304 if (index >= extraArgsBeginIndex) {305 newSuccOperands[index] = extraArgs[index - extraArgsBeginIndex];306 continue;307 }308 309 // Otherwise undef values for any unused block arguments used by other310 // entry blocks.311 newSuccOperands[index] = getUndefValue(argument.getType());312 }313 314 edge.setSuccessor(multiplexerBlock);315 successorOperands.assign(newSuccOperands);316 }317 318 /// Creates a switch op using `builder` which dispatches to the original319 /// successors of the edges passed to `create` minus the ones in `excluded`.320 /// The builder's insertion point has to be in a block dominated by the321 /// multiplexer block. All edges to the multiplexer block must have already322 /// been redirected using `redirectEdge`.323 void createSwitch(324 Location loc, OpBuilder &builder, CFGToSCFInterface &interface,325 const SmallPtrSetImpl<Block *> &excluded = SmallPtrSet<Block *, 1>{}) {326 // We create the switch by creating a case for all entries and then327 // splitting of the last entry as a default case.328 329 SmallVector<ValueRange> caseArguments;330 SmallVector<unsigned> caseValues;331 SmallVector<Block *> caseDestinations;332 for (auto &&[index, pair] : llvm::enumerate(blockArgMapping)) {333 auto &&[succ, offset] = pair;334 if (excluded.contains(succ))335 continue;336 337 caseValues.push_back(index);338 caseArguments.push_back(multiplexerBlock->getArguments().slice(339 offset, succ->getNumArguments()));340 caseDestinations.push_back(succ);341 }342 343 // If we don't have a discriminator due to only having one entry we have to344 // create a dummy flag for the switch.345 Value realDiscriminator = discriminator;346 if (!realDiscriminator || caseArguments.size() == 1)347 realDiscriminator = getSwitchValue(0);348 349 caseValues.pop_back();350 Block *defaultDest = caseDestinations.pop_back_val();351 ValueRange defaultArgs = caseArguments.pop_back_val();352 353 assert(!builder.getInsertionBlock()->hasNoPredecessors() &&354 "Edges need to be redirected prior to creating switch.");355 interface.createCFGSwitchOp(loc, builder, realDiscriminator, caseValues,356 caseDestinations, caseArguments, defaultDest,357 defaultArgs);358 }359 360private:361 /// Newly created multiplexer block.362 Block *multiplexerBlock;363 /// Callback used to create a constant suitable as flag for364 /// the interfaces `createCFGSwitchOp`.365 function_ref<Value(unsigned)> getSwitchValue;366 /// Callback used to create undefined values of a given type.367 function_ref<Value(Type)> getUndefValue;368 369 /// Mapping of the block arguments of an entry block to the corresponding370 /// block arguments in the multiplexer block. Block arguments of an entry371 /// block are simply appended ot the multiplexer block. This map simply372 /// contains the offset to the range in the multiplexer block.373 llvm::SmallMapVector<Block *, unsigned, 4> blockArgMapping;374 /// Discriminator value used in the multiplexer block to dispatch to the375 /// correct entry block. Null value if not required due to only having one376 /// entry block.377 Value discriminator;378 379 EdgeMultiplexer(Block *multiplexerBlock,380 function_ref<Value(unsigned)> getSwitchValue,381 function_ref<Value(Type)> getUndefValue,382 llvm::SmallMapVector<Block *, unsigned, 4> &&entries,383 Value dispatchFlag)384 : multiplexerBlock(multiplexerBlock), getSwitchValue(getSwitchValue),385 getUndefValue(getUndefValue), blockArgMapping(std::move(entries)),386 discriminator(dispatchFlag) {}387};388 389/// Alternative implementation of DenseMapInfo<Operation*> using the operation390/// equivalence infrastructure to check whether two 'return-like' operations are391/// equivalent in the context of this transformation. This means that both392/// operations are of the same kind, have the same amount of operands and types393/// and the same attributes and properties. The operands themselves don't have394/// to be equivalent.395struct ReturnLikeOpEquivalence : public llvm::DenseMapInfo<Operation *> {396 static unsigned getHashValue(const Operation *opC) {397 return OperationEquivalence::computeHash(398 const_cast<Operation *>(opC),399 /*hashOperands=*/OperationEquivalence::ignoreHashValue,400 /*hashResults=*/OperationEquivalence::ignoreHashValue,401 OperationEquivalence::IgnoreLocations);402 }403 404 static bool isEqual(const Operation *lhs, const Operation *rhs) {405 if (lhs == rhs)406 return true;407 if (lhs == getTombstoneKey() || lhs == getEmptyKey() ||408 rhs == getTombstoneKey() || rhs == getEmptyKey())409 return false;410 return OperationEquivalence::isEquivalentTo(411 const_cast<Operation *>(lhs), const_cast<Operation *>(rhs),412 OperationEquivalence::ignoreValueEquivalence, nullptr,413 OperationEquivalence::IgnoreLocations);414 }415};416 417/// Utility-class for transforming a region to only have one single block for418/// every return-like operation.419class ReturnLikeExitCombiner {420public:421 ReturnLikeExitCombiner(Region &topLevelRegion, CFGToSCFInterface &interface)422 : topLevelRegion(topLevelRegion), interface(interface) {}423 424 /// Transforms `returnLikeOp` to a branch to the only block in the425 /// region with an instance of `returnLikeOp`s kind.426 void combineExit(Operation *returnLikeOp,427 function_ref<Value(unsigned)> getSwitchValue) {428 auto [iter, inserted] = returnLikeToCombinedExit.try_emplace(returnLikeOp);429 if (!inserted && iter->first == returnLikeOp)430 return;431 432 Block *exitBlock = iter->second;433 if (inserted) {434 exitBlock = new Block;435 iter->second = exitBlock;436 topLevelRegion.push_back(exitBlock);437 exitBlock->addArguments(438 returnLikeOp->getOperandTypes(),439 SmallVector<Location>(returnLikeOp->getNumOperands(),440 returnLikeOp->getLoc()));441 }442 443 auto builder = OpBuilder::atBlockTerminator(returnLikeOp->getBlock());444 interface.createSingleDestinationBranch(returnLikeOp->getLoc(), builder,445 getSwitchValue(0), exitBlock,446 returnLikeOp->getOperands());447 448 if (!inserted) {449 returnLikeOp->erase();450 return;451 }452 453 returnLikeOp->moveBefore(exitBlock, exitBlock->end());454 returnLikeOp->setOperands(exitBlock->getArguments());455 }456 457private:458 /// Mapping of return-like operation to block. All return-like operations459 /// of the same kind with the same attributes, properties and types are seen460 /// as equivalent. First occurrence seen is kept in the map.461 llvm::SmallDenseMap<Operation *, Block *, 4, ReturnLikeOpEquivalence>462 returnLikeToCombinedExit;463 Region &topLevelRegion;464 CFGToSCFInterface &interface;465};466 467} // namespace468 469/// Returns a range of all edges from `block` to each of its successors.470static auto successorEdges(Block *block) {471 return llvm::map_range(llvm::seq(block->getNumSuccessors()),472 [=](unsigned index) { return Edge(block, index); });473}474 475/// Calculates entry, exit and back edges of the given cycle.476static CycleEdges477calculateCycleEdges(const llvm::SmallSetVector<Block *, 4> &cycles) {478 CycleEdges result;479 SmallPtrSet<Block *, 8> entryBlocks;480 481 // First identify all exit and entry edges by checking whether any successors482 // or predecessors are from outside the cycles.483 for (Block *block : cycles) {484 for (auto pred = block->pred_begin(); pred != block->pred_end(); pred++) {485 if (cycles.contains(*pred))486 continue;487 488 result.entryEdges.emplace_back(*pred, pred.getSuccessorIndex());489 entryBlocks.insert(block);490 }491 492 for (auto &&[succIndex, succ] : llvm::enumerate(block->getSuccessors())) {493 if (cycles.contains(succ))494 continue;495 496 result.exitEdges.emplace_back(block, succIndex);497 }498 }499 500 // With the entry blocks identified, find all the back edges.501 for (Block *block : cycles) {502 for (auto &&[succIndex, succ] : llvm::enumerate(block->getSuccessors())) {503 if (!entryBlocks.contains(succ))504 continue;505 506 result.backEdges.emplace_back(block, succIndex);507 }508 }509 510 return result;511}512 513/// Creates a single entry block out of multiple entry edges using an edge514/// multiplexer and returns it.515static EdgeMultiplexer516createSingleEntryBlock(Location loc, ArrayRef<Edge> entryEdges,517 function_ref<Value(unsigned)> getSwitchValue,518 function_ref<Value(Type)> getUndefValue,519 CFGToSCFInterface &interface) {520 auto result = EdgeMultiplexer::create(521 loc, llvm::map_to_vector(entryEdges, std::mem_fn(&Edge::getSuccessor)),522 getSwitchValue, getUndefValue);523 524 // Redirect the edges prior to creating the switch op.525 // We guarantee that predecessors are up to date.526 for (Edge edge : entryEdges)527 result.redirectEdge(edge);528 529 auto builder = OpBuilder::atBlockBegin(result.getMultiplexerBlock());530 result.createSwitch(loc, builder, interface);531 532 return result;533}534 535namespace {536/// Special loop properties of a structured loop.537/// A structured loop is a loop satisfying all of the following:538/// * Has at most one entry, one exit and one back edge.539/// * The back edge originates from the same block as the exit edge.540struct StructuredLoopProperties {541 /// Block containing both the single exit edge and the single back edge.542 Block *latch;543 /// Loop condition of type equal to a value returned by `getSwitchValue`.544 Value condition;545 /// Exit block which is the only successor of the loop.546 Block *exitBlock;547};548} // namespace549 550/// Transforms a loop into a structured loop with only a single back edge and551/// exiting edge, originating from the same block.552static FailureOr<StructuredLoopProperties> createSingleExitingLatch(553 Location loc, ArrayRef<Edge> backEdges, ArrayRef<Edge> exitEdges,554 function_ref<Value(unsigned)> getSwitchValue,555 function_ref<Value(Type)> getUndefValue, CFGToSCFInterface &interface,556 ReturnLikeExitCombiner &exitCombiner) {557 assert(llvm::all_equal(558 llvm::map_range(backEdges, std::mem_fn(&Edge::getSuccessor))) &&559 "All repetition edges must lead to the single loop header");560 561 // First create the multiplexer block, which will be our latch, for all back562 // edges and exit edges. We pass an additional argument to the multiplexer563 // block which indicates whether the latch was reached from what was564 // originally a back edge or an exit block.565 // This is later used to branch using the new only back edge.566 SmallVector<Block *> successors;567 llvm::append_range(568 successors, llvm::map_range(backEdges, std::mem_fn(&Edge::getSuccessor)));569 llvm::append_range(570 successors, llvm::map_range(exitEdges, std::mem_fn(&Edge::getSuccessor)));571 auto multiplexer =572 EdgeMultiplexer::create(loc, successors, getSwitchValue, getUndefValue,573 /*extraArgs=*/getSwitchValue(0).getType());574 575 auto *latchBlock = multiplexer.getMultiplexerBlock();576 577 // Create a separate exit block that comes right after the latch.578 auto *exitBlock = new Block;579 exitBlock->insertAfter(latchBlock);580 581 // Since this is a loop, all back edges point to the same loop header.582 Block *loopHeader = backEdges.front().getSuccessor();583 584 // Redirect the edges prior to creating the switch op.585 // We guarantee that predecessors are up to date.586 587 // Redirecting back edges with `shouldRepeat` as 1.588 for (Edge backEdge : backEdges)589 multiplexer.redirectEdge(backEdge, /*extraArgs=*/getSwitchValue(1));590 591 // Redirecting exits edges with `shouldRepeat` as 0.592 for (Edge exitEdge : exitEdges)593 multiplexer.redirectEdge(exitEdge, /*extraArgs=*/getSwitchValue(0));594 595 // Create the new only back edge to the loop header. Branch to the596 // exit block otherwise.597 Value shouldRepeat = latchBlock->getArguments().back();598 {599 auto builder = OpBuilder::atBlockBegin(latchBlock);600 interface.createConditionalBranch(601 loc, builder, shouldRepeat, loopHeader,602 latchBlock->getArguments().take_front(loopHeader->getNumArguments()),603 /*falseDest=*/exitBlock,604 /*falseArgs=*/{});605 }606 607 {608 auto builder = OpBuilder::atBlockBegin(exitBlock);609 if (!exitEdges.empty()) {610 // Create the switch dispatching to what were originally the multiple exit611 // blocks. The loop header has to explicitly be excluded in the below612 // switch as we would otherwise be creating a new loop again. All back613 // edges leading to the loop header have already been handled in the614 // switch above. The remaining edges can only jump to blocks outside the615 // loop.616 617 SmallPtrSet<Block *, 1> excluded = {loopHeader};618 multiplexer.createSwitch(loc, builder, interface, excluded);619 } else {620 // A loop without an exit edge is a statically known infinite loop.621 // Since structured control flow ops are not terminator ops, the caller622 // has to create a fitting return-like unreachable terminator operation.623 FailureOr<Operation *> terminator = interface.createUnreachableTerminator(624 loc, builder, *latchBlock->getParent());625 if (failed(terminator))626 return failure();627 // Transform the just created transform operation in the case that an628 // occurrence of it existed in input IR.629 exitCombiner.combineExit(*terminator, getSwitchValue);630 }631 }632 633 return StructuredLoopProperties{latchBlock, /*condition=*/shouldRepeat,634 exitBlock};635}636 637/// Transforms a structured loop into a loop in reduce form.638///639/// Reduce form is defined as a structured loop where:640/// (0) No values defined within the loop body are used outside the loop body.641/// (1) The block arguments and successor operands of the exit block are equal642/// to the block arguments of the loop header and the successor operands643/// of the back edge.644///645/// This is required for many structured control flow ops as they tend646/// to not have separate "loop result arguments" and "loop iteration arguments"647/// at the end of the block. Rather, the "loop iteration arguments" from the648/// last iteration are the result of the loop.649///650/// Note that the requirement of (0) is shared with LCSSA form in LLVM. However,651/// due to this being a structured loop instead of a general loop, we do not652/// require complicated dominance algorithms nor SSA updating making this653/// implementation easier than creating a generic LCSSA transformation pass.654static SmallVector<Value>655transformToReduceLoop(Block *loopHeader, Block *exitBlock,656 const llvm::SmallSetVector<Block *, 4> &loopBlocks,657 function_ref<Value(Type)> getUndefValue,658 DominanceInfo &dominanceInfo) {659 Block *latch = exitBlock->getSinglePredecessor();660 assert(latch &&661 "Exit block must have only latch as predecessor at this point");662 assert(exitBlock->getNumArguments() == 0 &&663 "Exit block mustn't have any block arguments at this point");664 665 unsigned loopHeaderIndex = 0;666 unsigned exitBlockIndex = 1;667 if (latch->getSuccessor(loopHeaderIndex) != loopHeader)668 std::swap(loopHeaderIndex, exitBlockIndex);669 670 assert(latch->getSuccessor(loopHeaderIndex) == loopHeader);671 assert(latch->getSuccessor(exitBlockIndex) == exitBlock);672 673 MutableOperandRange exitBlockSuccessorOperands =674 getMutableSuccessorOperands(latch, exitBlockIndex);675 // Save the values as a vector, not a `MutableOperandRange` as the latter gets676 // invalidated when mutating the operands through a different677 // `MutableOperandRange` of the same operation.678 SmallVector<Value> loopHeaderSuccessorOperands =679 llvm::to_vector(getSuccessorOperands(latch, loopHeaderIndex));680 681 // Add all values used in the next iteration to the exit block. Replace682 // any uses that are outside the loop with the newly created exit block.683 for (Value arg : loopHeaderSuccessorOperands) {684 BlockArgument exitArg = exitBlock->addArgument(arg.getType(), arg.getLoc());685 exitBlockSuccessorOperands.append(arg);686 arg.replaceUsesWithIf(exitArg, [&](OpOperand &use) {687 return !loopBlocks.contains(use.getOwner()->getBlock());688 });689 }690 691 // Loop below might add block arguments to the latch and loop header.692 // Save the block arguments prior to the loop to not process these.693 SmallVector<BlockArgument> latchBlockArgumentsPrior =694 llvm::to_vector(latch->getArguments());695 SmallVector<BlockArgument> loopHeaderArgumentsPrior =696 llvm::to_vector(loopHeader->getArguments());697 698 // Go over all values defined within the loop body. If any of them are used699 // outside the loop body, create a block argument on the exit block and loop700 // header and replace the outside uses with the exit block argument.701 // The loop header block argument is added to satisfy requirement (1) in the702 // reduce form condition.703 for (Block *loopBlock : loopBlocks) {704 // Cache dominance queries for loopBlock.705 // There are likely to be many duplicate queries as there can be many value706 // definitions within a block.707 llvm::SmallDenseMap<Block *, bool> dominanceCache;708 // Returns true if `loopBlock` dominates `block`.709 auto loopBlockDominates = [&](Block *block) {710 auto [iter, inserted] = dominanceCache.try_emplace(block);711 if (!inserted)712 return iter->second;713 iter->second = dominanceInfo.dominates(loopBlock, block);714 return iter->second;715 };716 717 auto checkValue = [&](Value value) {718 Value blockArgument;719 for (OpOperand &use : llvm::make_early_inc_range(value.getUses())) {720 // Go through all the parent blocks and find the one part of the region721 // of the loop. If the block is part of the loop, then the value does722 // not escape the loop through this use.723 Block *currBlock = use.getOwner()->getBlock();724 while (currBlock && currBlock->getParent() != loopHeader->getParent())725 currBlock = currBlock->getParentOp()->getBlock();726 if (loopBlocks.contains(currBlock))727 continue;728 729 // Block argument is only created the first time it is required.730 if (!blockArgument) {731 blockArgument =732 exitBlock->addArgument(value.getType(), value.getLoc());733 loopHeader->addArgument(value.getType(), value.getLoc());734 735 // `value` might be defined in a block that does not dominate `latch`736 // but previously dominated an exit block with a use.737 // In this case, add a block argument to the latch and go through all738 // predecessors. If the value dominates the predecessor, pass the739 // value as a successor operand, otherwise pass undef.740 // The above is unnecessary if the value is a block argument of the741 // latch or if `value` dominates all predecessors.742 Value argument = value;743 if (value.getParentBlock() != latch &&744 llvm::any_of(latch->getPredecessors(), [&](Block *pred) {745 return !loopBlockDominates(pred);746 })) {747 argument = latch->addArgument(value.getType(), value.getLoc());748 for (auto iter = latch->pred_begin(); iter != latch->pred_end();749 ++iter) {750 Value succOperand = value;751 if (!loopBlockDominates(*iter))752 succOperand = getUndefValue(value.getType());753 754 getMutableSuccessorOperands(*iter, iter.getSuccessorIndex())755 .append(succOperand);756 }757 }758 759 loopHeaderSuccessorOperands.push_back(argument);760 for (Edge edge : successorEdges(latch))761 edge.getMutableSuccessorOperands().append(argument);762 }763 764 use.set(blockArgument);765 }766 };767 768 if (loopBlock == latch)769 llvm::for_each(latchBlockArgumentsPrior, checkValue);770 else if (loopBlock == loopHeader)771 llvm::for_each(loopHeaderArgumentsPrior, checkValue);772 else773 llvm::for_each(loopBlock->getArguments(), checkValue);774 775 for (Operation &op : *loopBlock)776 llvm::for_each(op.getResults(), checkValue);777 }778 779 // New block arguments may have been added to the loop header.780 // Adjust the entry edges to pass undef values to these.781 for (auto iter = loopHeader->pred_begin(); iter != loopHeader->pred_end();782 ++iter) {783 // Latch successor arguments have already been handled.784 if (*iter == latch)785 continue;786 787 MutableOperandRange succOps =788 getMutableSuccessorOperands(*iter, iter.getSuccessorIndex());789 succOps.append(llvm::map_to_vector(790 loopHeader->getArguments().drop_front(succOps.size()),791 [&](BlockArgument arg) { return getUndefValue(arg.getType()); }));792 }793 794 return loopHeaderSuccessorOperands;795}796 797/// Transforms all outer-most cycles in the region with the region entry798/// `regionEntry` into structured loops. Returns the entry blocks of any newly799/// created regions potentially requiring further transformations.800static FailureOr<SmallVector<Block *>> transformCyclesToSCFLoops(801 Block *regionEntry, function_ref<Value(unsigned)> getSwitchValue,802 function_ref<Value(Type)> getUndefValue, CFGToSCFInterface &interface,803 DominanceInfo &dominanceInfo, ReturnLikeExitCombiner &exitCombiner) {804 SmallVector<Block *> newSubRegions;805 auto scc = llvm::scc_begin(regionEntry);806 while (!scc.isAtEnd()) {807 if (!scc.hasCycle()) {808 ++scc;809 continue;810 }811 812 // Save the set and increment the SCC iterator early to avoid our813 // modifications breaking the SCC iterator.814 llvm::SmallSetVector<Block *, 4> cycleBlockSet(scc->begin(), scc->end());815 ++scc;816 817 CycleEdges edges = calculateCycleEdges(cycleBlockSet);818 Block *loopHeader = edges.entryEdges.front().getSuccessor();819 // First turn the cycle into a loop by creating a single entry block if820 // needed.821 if (edges.entryEdges.size() > 1) {822 SmallVector<Edge> edgesToEntryBlocks;823 llvm::append_range(edgesToEntryBlocks, edges.entryEdges);824 llvm::append_range(edgesToEntryBlocks, edges.backEdges);825 826 EdgeMultiplexer multiplexer = createSingleEntryBlock(827 loopHeader->getTerminator()->getLoc(), edgesToEntryBlocks,828 getSwitchValue, getUndefValue, interface);829 830 loopHeader = multiplexer.getMultiplexerBlock();831 }832 cycleBlockSet.insert(loopHeader);833 834 // Then turn it into a structured loop by creating a single latch.835 FailureOr<StructuredLoopProperties> loopProperties =836 createSingleExitingLatch(837 edges.backEdges.front().getFromBlock()->getTerminator()->getLoc(),838 edges.backEdges, edges.exitEdges, getSwitchValue, getUndefValue,839 interface, exitCombiner);840 if (failed(loopProperties))841 return failure();842 843 Block *latchBlock = loopProperties->latch;844 Block *exitBlock = loopProperties->exitBlock;845 cycleBlockSet.insert(latchBlock);846 cycleBlockSet.insert(loopHeader);847 848 // Finally, turn it into reduce form.849 SmallVector<Value> iterationValues = transformToReduceLoop(850 loopHeader, exitBlock, cycleBlockSet, getUndefValue, dominanceInfo);851 852 // Create a block acting as replacement for the loop header and insert853 // the structured loop into it.854 auto *newLoopParentBlock = new Block;855 newLoopParentBlock->insertBefore(loopHeader);856 addBlockArgumentsFromOther(newLoopParentBlock, loopHeader);857 858 Region::BlockListType &blocks = regionEntry->getParent()->getBlocks();859 Region loopBody;860 // Make sure the loop header is the entry block.861 loopBody.push_back(blocks.remove(loopHeader));862 for (Block *block : cycleBlockSet)863 if (block != latchBlock && block != loopHeader)864 loopBody.push_back(blocks.remove(block));865 // And the latch is the last block.866 loopBody.push_back(blocks.remove(latchBlock));867 868 Operation *oldTerminator = latchBlock->getTerminator();869 oldTerminator->remove();870 871 auto builder = OpBuilder::atBlockBegin(newLoopParentBlock);872 FailureOr<Operation *> structuredLoopOp =873 interface.createStructuredDoWhileLoopOp(874 builder, oldTerminator, newLoopParentBlock->getArguments(),875 loopProperties->condition, iterationValues, std::move(loopBody));876 if (failed(structuredLoopOp))877 return failure();878 oldTerminator->erase();879 880 newSubRegions.push_back(loopHeader);881 882 for (auto &&[oldValue, newValue] : llvm::zip(883 exitBlock->getArguments(), (*structuredLoopOp)->getResults()))884 oldValue.replaceAllUsesWith(newValue);885 886 loopHeader->replaceAllUsesWith(newLoopParentBlock);887 // Merge the exit block right after the loop operation.888 newLoopParentBlock->getOperations().splice(newLoopParentBlock->end(),889 exitBlock->getOperations());890 exitBlock->erase();891 }892 return newSubRegions;893}894 895/// Makes sure the branch region only has a single exit. This is required by the896/// recursive part of the algorithm, as it expects the CFG to be single-entry897/// and single-exit. This is done by simply creating an empty block if there898/// is more than one block with an edge to the continuation block. All blocks899/// with edges to the continuation are then redirected to this block. A region900/// terminator is later placed into the block.901static void createSingleExitBranchRegion(902 ArrayRef<Block *> branchRegion, Block *continuation,903 SmallVectorImpl<std::pair<Block *, SmallVector<Value>>> &createdEmptyBlocks,904 Region &conditionalRegion) {905 Block *singleExitBlock = nullptr;906 std::optional<Edge> previousEdgeToContinuation;907 Region::BlockListType &parentBlockList =908 branchRegion.front()->getParent()->getBlocks();909 for (Block *block : branchRegion) {910 for (Edge edge : successorEdges(block)) {911 if (edge.getSuccessor() != continuation)912 continue;913 914 if (!previousEdgeToContinuation) {915 previousEdgeToContinuation = edge;916 continue;917 }918 919 // If this is not the first edge to the continuation we create the920 // single exit block and redirect the edges.921 if (!singleExitBlock) {922 singleExitBlock = new Block;923 addBlockArgumentsFromOther(singleExitBlock, continuation);924 previousEdgeToContinuation->setSuccessor(singleExitBlock);925 createdEmptyBlocks.emplace_back(singleExitBlock,926 singleExitBlock->getArguments());927 }928 929 edge.setSuccessor(singleExitBlock);930 }931 932 conditionalRegion.push_back(parentBlockList.remove(block));933 }934 935 if (singleExitBlock)936 conditionalRegion.push_back(singleExitBlock);937}938 939/// Returns true if this block is an exit block of the region.940static bool isRegionExitBlock(Block *block) {941 return block->getNumSuccessors() == 0;942}943 944/// Transforms the first occurrence of conditional control flow in `regionEntry`945/// into conditionally executed regions. Returns the entry block of the created946/// regions and the region after the conditional control flow.947static FailureOr<SmallVector<Block *>> transformToStructuredCFBranches(948 Block *regionEntry, function_ref<Value(unsigned)> getSwitchValue,949 function_ref<Value(Type)> getUndefValue, CFGToSCFInterface &interface,950 DominanceInfo &dominanceInfo) {951 // Trivial region.952 if (regionEntry->getNumSuccessors() == 0)953 return SmallVector<Block *>{};954 955 if (regionEntry->getNumSuccessors() == 1) {956 // Single successor we can just splice together.957 Block *successor = regionEntry->getSuccessor(0);958 for (auto &&[oldValue, newValue] : llvm::zip(959 successor->getArguments(), getSuccessorOperands(regionEntry, 0)))960 oldValue.replaceAllUsesWith(newValue);961 regionEntry->getTerminator()->erase();962 963 regionEntry->getOperations().splice(regionEntry->end(),964 successor->getOperations());965 successor->erase();966 return SmallVector<Block *>{regionEntry};967 }968 969 // Split the CFG into "#numSuccessor + 1" regions.970 // For every edge to a successor, the blocks it solely dominates are971 // determined and become the region following that edge.972 // The last region is the continuation that follows the branch regions.973 SmallPtrSet<Block *, 8> notContinuation;974 notContinuation.insert(regionEntry);975 SmallVector<SmallVector<Block *>> successorBranchRegions(976 regionEntry->getNumSuccessors());977 for (auto &&[blockList, succ] :978 llvm::zip(successorBranchRegions, regionEntry->getSuccessors())) {979 // If the region entry is not the only predecessor, then the edge does not980 // dominate the block it leads to.981 if (succ->getSinglePredecessor() != regionEntry)982 continue;983 984 // Otherwise get all blocks it dominates in DFS/pre-order.985 DominanceInfoNode *node = dominanceInfo.getNode(succ);986 for (DominanceInfoNode *curr : llvm::depth_first(node)) {987 blockList.push_back(curr->getBlock());988 notContinuation.insert(curr->getBlock());989 }990 }991 992 // Finds all relevant edges and checks the shape of the control flow graph at993 // this point.994 // Branch regions may either:995 // * Be post-dominated by the continuation996 // * Be post-dominated by a return-like op997 // * Dominate a return-like op and have an edge to the continuation.998 //999 // The control flow graph may then be one of three cases:1000 // 1) All branch regions are post-dominated by the continuation. This is the1001 // usual case. If there are multiple entry blocks into the continuation a1002 // single entry block has to be created. A structured control flow op1003 // can then be created from the branch regions.1004 //1005 // 2) No branch region has an edge to a continuation:1006 // +-----+1007 // +-----+ bb0 +----+1008 // v +-----+ v1009 // Region 1 +-+--+ ... +-+--+ Region n1010 // |ret1| |ret2|1011 // +----+ +----+1012 //1013 // This can only occur if every region ends with a different kind of1014 // return-like op. In that case the control flow operation must stay as we are1015 // unable to create a single exit-block. We can nevertheless process all its1016 // successors as they single-entry, single-exit regions.1017 //1018 // 3) Only some branch regions are post-dominated by the continuation.1019 // The other branch regions may either be post-dominated by a return-like op1020 // or lead to either the continuation or return-like op.1021 // In this case we also create a single entry block like in 1) that also1022 // includes all edges to the return-like op:1023 // +-----+1024 // +-----+ bb0 +----+1025 // v +-----+ v1026 // Region 1 +-+-+ ... +-+-+ Region n1027 // +---+ +---+1028 // +---+ |... ...1029 // |ret|<-+ | |1030 // +---+ | +---+ |1031 // +---->++ ++<---+1032 // | |1033 // ++ ++ Region T1034 // +---+1035 // This transforms to:1036 // +-----+1037 // +-----+ bb0 +----+1038 // v +-----+ v1039 // Region 1 +-+-+ ... +-+-+ Region n1040 // +---+ +---+1041 // ... +-----+ ...1042 // +---->+ bbM +<---+1043 // +-----+1044 // +-----+ |1045 // | v1046 // +---+ | +---+1047 // |ret+<---+ ++ ++1048 // +---+ | |1049 // ++ ++ Region T1050 // +---+1051 //1052 // bb0 to bbM is now a single-entry, single-exit region that applies to case1053 // 1). The control flow op at the end of bbM will trigger case 2.1054 SmallVector<Edge> continuationEdges;1055 bool continuationPostDominatesAllRegions = true;1056 bool noSuccessorHasContinuationEdge = true;1057 for (auto &&[entryEdge, branchRegion] :1058 llvm::zip(successorEdges(regionEntry), successorBranchRegions)) {1059 1060 // If the branch region is empty then the branch target itself is part of1061 // the continuation.1062 if (branchRegion.empty()) {1063 continuationEdges.push_back(entryEdge);1064 noSuccessorHasContinuationEdge = false;1065 continue;1066 }1067 1068 for (Block *block : branchRegion) {1069 if (isRegionExitBlock(block)) {1070 // If a return-like op is part of the branch region then the1071 // continuation no longer post-dominates the branch region.1072 // Add all its incoming edges to edge list to create the single-exit1073 // block for all branch regions.1074 continuationPostDominatesAllRegions = false;1075 for (auto iter = block->pred_begin(); iter != block->pred_end();1076 ++iter) {1077 continuationEdges.emplace_back(*iter, iter.getSuccessorIndex());1078 }1079 continue;1080 }1081 1082 for (Edge edge : successorEdges(block)) {1083 if (notContinuation.contains(edge.getSuccessor()))1084 continue;1085 1086 continuationEdges.push_back(edge);1087 noSuccessorHasContinuationEdge = false;1088 }1089 }1090 }1091 1092 // case 2) Keep the control flow op but process its successors further.1093 if (noSuccessorHasContinuationEdge)1094 return llvm::to_vector(regionEntry->getSuccessors());1095 1096 Block *continuation = llvm::find_singleton<Block>(1097 continuationEdges, [](Edge edge, bool) { return edge.getSuccessor(); },1098 /*AllowRepeats=*/true);1099 1100 // In case 3) or if not all continuation edges have the same entry block,1101 // create a single entry block as continuation for all branch regions.1102 if (!continuation || !continuationPostDominatesAllRegions) {1103 EdgeMultiplexer multiplexer = createSingleEntryBlock(1104 continuationEdges.front().getFromBlock()->getTerminator()->getLoc(),1105 continuationEdges, getSwitchValue, getUndefValue, interface);1106 continuation = multiplexer.getMultiplexerBlock();1107 }1108 1109 // Trigger reprocess of case 3) after creating the single entry block.1110 if (!continuationPostDominatesAllRegions) {1111 // Unlike in the general case, we are explicitly revisiting the same region1112 // entry again after having changed its control flow edges and dominance.1113 // We have to therefore explicitly invalidate the dominance tree.1114 dominanceInfo.invalidate(regionEntry->getParent());1115 return SmallVector<Block *>{regionEntry};1116 }1117 1118 SmallVector<Block *> newSubRegions;1119 1120 // Empty blocks with the values they return to the parent op.1121 SmallVector<std::pair<Block *, SmallVector<Value>>> createdEmptyBlocks;1122 1123 // Create the branch regions.1124 std::vector<Region> conditionalRegions(successorBranchRegions.size());1125 for (auto &&[branchRegion, entryEdge, conditionalRegion] :1126 llvm::zip(successorBranchRegions, successorEdges(regionEntry),1127 conditionalRegions)) {1128 if (branchRegion.empty()) {1129 // If no block is part of the branch region, we create a dummy block to1130 // place the region terminator into.1131 createdEmptyBlocks.emplace_back(1132 new Block, llvm::to_vector(entryEdge.getSuccessorOperands()));1133 conditionalRegion.push_back(createdEmptyBlocks.back().first);1134 continue;1135 }1136 1137 createSingleExitBranchRegion(branchRegion, continuation, createdEmptyBlocks,1138 conditionalRegion);1139 1140 // The entries of the branch regions may only have redundant block arguments1141 // since the edge to the branch region is always dominating.1142 Block *subRegionEntryBlock = &conditionalRegion.front();1143 for (auto &&[oldValue, newValue] :1144 llvm::zip(subRegionEntryBlock->getArguments(),1145 entryEdge.getSuccessorOperands()))1146 oldValue.replaceAllUsesWith(newValue);1147 1148 subRegionEntryBlock->eraseArguments(0,1149 subRegionEntryBlock->getNumArguments());1150 newSubRegions.push_back(subRegionEntryBlock);1151 }1152 1153 Operation *structuredCondOp;1154 {1155 auto opBuilder = OpBuilder::atBlockTerminator(regionEntry);1156 FailureOr<Operation *> result = interface.createStructuredBranchRegionOp(1157 opBuilder, regionEntry->getTerminator(),1158 continuation->getArgumentTypes(), conditionalRegions);1159 if (failed(result))1160 return failure();1161 structuredCondOp = *result;1162 regionEntry->getTerminator()->erase();1163 }1164 1165 for (auto &&[block, valueRange] : createdEmptyBlocks) {1166 auto builder = OpBuilder::atBlockEnd(block);1167 LogicalResult result = interface.createStructuredBranchRegionTerminatorOp(1168 structuredCondOp->getLoc(), builder, structuredCondOp, nullptr,1169 valueRange);1170 if (failed(result))1171 return failure();1172 }1173 1174 // Any leftover users of the continuation must be from unconditional branches1175 // in a branch region. There can only be at most one per branch region as1176 // all branch regions have been made single-entry single-exit above.1177 // Replace them with the region terminator.1178 for (Operation *user : llvm::make_early_inc_range(continuation->getUsers())) {1179 assert(user->getNumSuccessors() == 1);1180 auto builder = OpBuilder::atBlockTerminator(user->getBlock());1181 LogicalResult result = interface.createStructuredBranchRegionTerminatorOp(1182 user->getLoc(), builder, structuredCondOp, user,1183 getMutableSuccessorOperands(user->getBlock(), 0).getAsOperandRange());1184 if (failed(result))1185 return failure();1186 user->erase();1187 }1188 1189 for (auto &&[oldValue, newValue] :1190 llvm::zip(continuation->getArguments(), structuredCondOp->getResults()))1191 oldValue.replaceAllUsesWith(newValue);1192 1193 // Splice together the continuations operations with the region entry.1194 regionEntry->getOperations().splice(regionEntry->end(),1195 continuation->getOperations());1196 1197 continuation->erase();1198 1199 // After splicing the continuation, the region has to be reprocessed as it has1200 // new successors.1201 newSubRegions.push_back(regionEntry);1202 1203 return newSubRegions;1204}1205 1206/// Transforms the region to only have a single block for every kind of1207/// return-like operation that all previous occurrences of the return-like op1208/// branch to. If the region only contains a single kind of return-like1209/// operation, it creates a single-entry and single-exit region.1210static ReturnLikeExitCombiner createSingleExitBlocksForReturnLike(1211 Region ®ion, function_ref<Value(unsigned)> getSwitchValue,1212 CFGToSCFInterface &interface) {1213 ReturnLikeExitCombiner exitCombiner(region, interface);1214 1215 for (Block &block : region.getBlocks()) {1216 if (block.getNumSuccessors() != 0)1217 continue;1218 exitCombiner.combineExit(block.getTerminator(), getSwitchValue);1219 }1220 1221 return exitCombiner;1222}1223 1224/// Checks all preconditions of the transformation prior to any transformations.1225/// Returns failure if any precondition is violated.1226static LogicalResult checkTransformationPreconditions(Region ®ion) {1227 for (Block &block : region.getBlocks())1228 if (block.hasNoPredecessors() && !block.isEntryBlock())1229 return block.front().emitOpError(1230 "transformation does not support unreachable blocks");1231 1232 WalkResult result = region.walk([](Operation *operation) {1233 if (operation->getNumSuccessors() == 0)1234 return WalkResult::advance();1235 1236 // This transformation requires all ops with successors to implement the1237 // branch op interface. It is impossible to adjust their block arguments1238 // otherwise.1239 auto branchOpInterface = dyn_cast<BranchOpInterface>(operation);1240 if (!branchOpInterface) {1241 operation->emitOpError("transformation does not support terminators with "1242 "successors not implementing BranchOpInterface");1243 return WalkResult::interrupt();1244 }1245 // Branch operations must have no side effects. Replacing them would not be1246 // valid otherwise.1247 if (!isMemoryEffectFree(branchOpInterface)) {1248 branchOpInterface->emitOpError(1249 "transformation does not support terminators with side effects");1250 return WalkResult::interrupt();1251 }1252 1253 for (unsigned index : llvm::seq(operation->getNumSuccessors())) {1254 SuccessorOperands succOps = branchOpInterface.getSuccessorOperands(index);1255 1256 // We cannot support operations with operation-produced successor operands1257 // as it is currently not possible to pass them to any block arguments1258 // other than the first. This breaks creating multiplexer blocks and would1259 // likely need special handling elsewhere too.1260 if (succOps.getProducedOperandCount() == 0)1261 continue;1262 1263 branchOpInterface->emitOpError("transformation does not support "1264 "operations with operation-produced "1265 "successor operands");1266 return WalkResult::interrupt();1267 }1268 return WalkResult::advance();1269 });1270 return failure(result.wasInterrupted());1271}1272 1273FailureOr<bool> mlir::transformCFGToSCF(Region ®ion,1274 CFGToSCFInterface &interface,1275 DominanceInfo &dominanceInfo) {1276 if (region.empty() || region.hasOneBlock())1277 return false;1278 1279 if (failed(checkTransformationPreconditions(region)))1280 return failure();1281 1282 DenseMap<Type, Value> typedUndefCache;1283 auto getUndefValue = [&](Type type) {1284 auto [iter, inserted] = typedUndefCache.try_emplace(type);1285 if (!inserted)1286 return iter->second;1287 1288 auto constantBuilder = OpBuilder::atBlockBegin(®ion.front());1289 1290 iter->second =1291 interface.getUndefValue(region.getLoc(), constantBuilder, type);1292 return iter->second;1293 };1294 1295 // The transformation only creates all values in the range of 0 to1296 // max(#numSuccessors). Therefore using a vector instead of a map.1297 SmallVector<Value> switchValueCache;1298 auto getSwitchValue = [&](unsigned value) {1299 if (value < switchValueCache.size())1300 if (switchValueCache[value])1301 return switchValueCache[value];1302 1303 auto constantBuilder = OpBuilder::atBlockBegin(®ion.front());1304 1305 switchValueCache.resize(1306 std::max<size_t>(switchValueCache.size(), value + 1));1307 1308 switchValueCache[value] =1309 interface.getCFGSwitchValue(region.getLoc(), constantBuilder, value);1310 return switchValueCache[value];1311 };1312 1313 ReturnLikeExitCombiner exitCombiner =1314 createSingleExitBlocksForReturnLike(region, getSwitchValue, interface);1315 1316 // Invalidate any dominance tree on the region as the exit combiner has1317 // added new blocks and edges.1318 dominanceInfo.invalidate(®ion);1319 1320 SmallVector<Block *> workList = {®ion.front()};1321 while (!workList.empty()) {1322 Block *current = workList.pop_back_val();1323 1324 // Turn all top-level cycles in the CFG to structured control flow first.1325 // After this transformation, the remaining CFG ops form a DAG.1326 FailureOr<SmallVector<Block *>> newRegions =1327 transformCyclesToSCFLoops(current, getSwitchValue, getUndefValue,1328 interface, dominanceInfo, exitCombiner);1329 if (failed(newRegions))1330 return failure();1331 1332 // Add the newly created subregions to the worklist. These are the1333 // bodies of the loops.1334 llvm::append_range(workList, *newRegions);1335 // Invalidate the dominance tree as blocks have been moved, created and1336 // added during the cycle to structured loop transformation.1337 if (!newRegions->empty())1338 dominanceInfo.invalidate(current->getParent());1339 1340 newRegions = transformToStructuredCFBranches(1341 current, getSwitchValue, getUndefValue, interface, dominanceInfo);1342 if (failed(newRegions))1343 return failure();1344 // Invalidating the dominance tree is generally not required by the1345 // transformation above as the new region entries correspond to unaffected1346 // subtrees in the dominator tree. Only its parent nodes have changed but1347 // won't be visited again.1348 llvm::append_range(workList, *newRegions);1349 }1350 1351 return true;1352}1353