| //===- CFGToSCF.h - Control Flow Graph to Structured Control Flow *- C++ -*===// |
| // |
| // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| // See https://llvm.org/LICENSE.txt for license information. |
| // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| // |
| //===----------------------------------------------------------------------===// |
| // |
| // This code is an implementation of: |
| // Helge Bahmann, Nico Reissmann, Magnus Jahre, and Jan Christian Meyer. 2015. |
| // Perfect Reconstructability of Control Flow from Demand Dependence Graphs. ACM |
| // Trans. Archit. Code Optim. 11, 4, Article 66 (January 2015), 25 pages. |
| // https://doi.org/10.1145/2693261 |
| // |
| // It defines an algorithm to translate any control flow graph with a single |
| // entry and single exit block into structured control flow operations |
| // consisting of regions of do-while loops and operations conditionally |
| // dispatching to one out of multiple regions before continuing after the |
| // operation. This includes control flow graphs containing irreducible |
| // control flow. |
| // |
| // The implementation here additionally supports the transformation on |
| // regions with multiple exit blocks. This is implemented by first |
| // transforming all occurrences of return-like operations to branch to a |
| // single exit block containing an instance of that return-like operation. |
| // If there are multiple kinds of return-like operations, multiple exit |
| // blocks are created. In that case the transformation leaves behind a |
| // conditional control flow graph operation that dispatches to the given regions |
| // terminating with different kinds of return-like operations each. |
| // |
| // If the function only contains a single kind of return-like operations, |
| // it is guaranteed that all control flow graph ops will be lifted to structured |
| // control flow, and that no more control flow graph ops remain after the |
| // operation. |
| // |
| // The algorithm to lift CFGs consists of two transformations applied after each |
| // other on any single-entry, single-exit region: |
| // 1) Lifting cycles to structured control flow loops |
| // 2) Lifting conditional branches to structured control flow branches |
| // These are then applied recursively on any new single-entry single-exit |
| // regions created by the transformation until no more CFG operations remain. |
| // |
| // The first part of cycle lifting is to detect any cycles in the CFG. |
| // This is done using an algorithm for iterating over SCCs. Every SCC |
| // representing a cycle is then transformed into a structured loop with a single |
| // entry block and a single latch containing the only back edge to the entry |
| // block and the only edge to an exit block outside the loop. Rerouting control |
| // flow to create single entry and exit blocks is achieved via a multiplexer |
| // construct that can be visualized as follows: |
| // +-----+ +-----+ +-----+ |
| // | bb0 | | bb1 |...| bbN | |
| // +--+--+ +--+--+ +-+---+ |
| // | | | |
| // | v | |
| // | +------+ | |
| // | ++ ++<----+ |
| // | | Region | |
| // +>| |<----+ |
| // ++ ++ | |
| // +------+------+ |
| // |
| // The above transforms to: |
| // +-----+ +-----+ +-----+ |
| // | bb0 | | bb1 |...| bbN | |
| // +-----+ +--|--+ ++----+ |
| // | v | |
| // +->+-----+<---+ |
| // | bbM |<-------+ |
| // +---+-+ | |
| // +---+ | +----+ | |
| // | v | | |
| // | +------+ | | |
| // | ++ ++<-+ | |
| // +->| Region | | |
| // ++ ++ | |
| // +------+-------+ |
| // |
| // bbM in the above is the multiplexer block, and any block previously branching |
| // to an entry block of the region are redirected to it. This includes any |
| // branches from within the region. Using a block argument, bbM then dispatches |
| // to the correct entry block of the region dependent on the predecessor. |
| // |
| // A similar transformation is done to create the latch block with the single |
| // back edge and loop exit edge. |
| // |
| // The above form has the advantage that bbM now acts as the loop header |
| // of the loop body. After the transformation on the latch, this results in a |
| // structured loop that can then be lifted to structured control flow. The |
| // conditional branches created in bbM are later lifted to conditional |
| // branches. |
| // |
| // Lifting conditional branches is done by analyzing the *first* conditional |
| // branch encountered in the entry region. The algorithm then identifies |
| // all blocks that are dominated by a specific control flow edge and |
| // the region where control flow continues: |
| // +-----+ |
| // +-----+ bb0 +----+ |
| // v +-----+ v |
| // Region 1 +-+-+ ... +-+-+ Region n |
| // +---+ +---+ |
| // ... ... |
| // | | |
| // | +---+ | |
| // +---->++ ++<---+ |
| // | | |
| // ++ ++ Region T |
| // +---+ |
| // Every region following bb0 consists of 0 or more blocks that eventually |
| // branch to Region T. If there are multiple entry blocks into Region T, a |
| // single entry block is created using a multiplexer block as shown above. |
| // Region 1 to Region n are then lifted together with the conditional control |
| // flow operation terminating bb0 into a structured conditional operation |
| // followed by the operations of the entry block of Region T. |
| //===----------------------------------------------------------------------===// |
| |
| #include "mlir/Transforms/CFGToSCF.h" |
| |
| #include "mlir/IR/RegionGraphTraits.h" |
| #include "mlir/Interfaces/ControlFlowInterfaces.h" |
| #include "mlir/Interfaces/SideEffectInterfaces.h" |
| #include "llvm/ADT/DepthFirstIterator.h" |
| #include "llvm/ADT/MapVector.h" |
| #include "llvm/ADT/SCCIterator.h" |
| #include "llvm/ADT/SetVector.h" |
| #include "llvm/ADT/SmallPtrSet.h" |
| |
| using namespace mlir; |
| |
| /// Returns the mutable operand range used to transfer operands from `block` to |
| /// its successor with the given index. The returned range being mutable allows |
| /// us to modify the operands being transferred. |
| static MutableOperandRange |
| getMutableSuccessorOperands(Block *block, unsigned successorIndex) { |
| auto branchOpInterface = cast<BranchOpInterface>(block->getTerminator()); |
| SuccessorOperands succOps = |
| branchOpInterface.getSuccessorOperands(successorIndex); |
| return succOps.getMutableForwardedOperands(); |
| } |
| |
| /// Return the operand range used to transfer operands from `block` to its |
| /// successor with the given index. |
| static OperandRange getSuccessorOperands(Block *block, |
| unsigned successorIndex) { |
| return getMutableSuccessorOperands(block, successorIndex); |
| } |
| |
| /// Appends all the block arguments from `other` to the block arguments of |
| /// `block`, copying their types and locations. |
| static void addBlockArgumentsFromOther(Block *block, Block *other) { |
| for (BlockArgument arg : other->getArguments()) |
| block->addArgument(arg.getType(), arg.getLoc()); |
| } |
| |
| namespace { |
| |
| /// Class representing an edge in the CFG. Consists of a from-block, a successor |
| /// and corresponding successor operands passed to the block arguments of the |
| /// successor. |
| class Edge { |
| Block *fromBlock; |
| unsigned successorIndex; |
| |
| public: |
| /// Constructs a new edge from `fromBlock` to the successor corresponding to |
| /// `successorIndex`. |
| Edge(Block *fromBlock, unsigned int successorIndex) |
| : fromBlock(fromBlock), successorIndex(successorIndex) {} |
| |
| /// Returns the from-block. |
| Block *getFromBlock() const { return fromBlock; } |
| |
| /// Returns the successor of the edge. |
| Block *getSuccessor() const { |
| return fromBlock->getSuccessor(successorIndex); |
| } |
| |
| /// Sets the successor of the edge, adjusting the terminator in the |
| /// from-block. |
| void setSuccessor(Block *block) const { |
| fromBlock->getTerminator()->setSuccessor(block, successorIndex); |
| } |
| |
| /// Returns the arguments of this edge that are passed to the block arguments |
| /// of the successor. |
| MutableOperandRange getMutableSuccessorOperands() const { |
| return ::getMutableSuccessorOperands(fromBlock, successorIndex); |
| } |
| |
| /// Returns the arguments of this edge that are passed to the block arguments |
| /// of the successor. |
| OperandRange getSuccessorOperands() const { |
| return ::getSuccessorOperands(fromBlock, successorIndex); |
| } |
| }; |
| |
| /// Structure containing the entry, exit and back edges of a cycle. A cycle is a |
| /// generalization of a loop that may have multiple entry edges. See also |
| /// https://llvm.org/docs/CycleTerminology.html. |
| struct CycleEdges { |
| /// All edges from a block outside the cycle to a block inside the cycle. |
| /// The targets of these edges are entry blocks. |
| SmallVector<Edge> entryEdges; |
| /// All edges from a block inside the cycle to a block outside the cycle. |
| SmallVector<Edge> exitEdges; |
| /// All edges from a block inside the cycle to an entry block. |
| SmallVector<Edge> backEdges; |
| }; |
| |
| /// Class used to orchestrate creation of so-called edge multiplexers. |
| /// This class creates a new basic block and routes all inputs edges |
| /// to this basic block before branching to their original target. |
| /// The purpose of this transformation is to create single-entry, |
| /// single-exit regions. |
| class EdgeMultiplexer { |
| public: |
| /// Creates a new edge multiplexer capable of redirecting all edges to one of |
| /// the `entryBlocks`. This creates the multiplexer basic block with |
| /// appropriate block arguments after the first entry block. `extraArgs` |
| /// contains the types of possible extra block arguments passed to the |
| /// multiplexer block that are added to the successor operands of every |
| /// outgoing edge. |
| /// |
| /// NOTE: This does not yet redirect edges to branch to the |
| /// multiplexer block nor code dispatching from the multiplexer code |
| /// to the original successors. |
| /// See `redirectEdge` and `createSwitch`. |
| static EdgeMultiplexer create(Location loc, ArrayRef<Block *> entryBlocks, |
| function_ref<Value(unsigned)> getSwitchValue, |
| function_ref<Value(Type)> getUndefValue, |
| TypeRange extraArgs = {}) { |
| assert(!entryBlocks.empty() && "Require at least one entry block"); |
| |
| auto *multiplexerBlock = new Block; |
| multiplexerBlock->insertAfter(entryBlocks.front()); |
| |
| // To implement the multiplexer block, we have to add the block arguments of |
| // every distinct successor block to the multiplexer block. When redirecting |
| // edges, block arguments designated for blocks that aren't branched to will |
| // be assigned the `getUndefValue`. The amount of block arguments and their |
| // offset is saved in the map for `redirectEdge` to transform the edges. |
| llvm::SmallMapVector<Block *, unsigned, 4> blockArgMapping; |
| for (Block *entryBlock : entryBlocks) { |
| auto [iter, inserted] = blockArgMapping.insert( |
| {entryBlock, multiplexerBlock->getNumArguments()}); |
| if (inserted) |
| addBlockArgumentsFromOther(multiplexerBlock, entryBlock); |
| } |
| |
| // If we have more than one successor, we have to additionally add a |
| // discriminator value, denoting which successor to jump to. |
| // When redirecting edges, an appropriate value will be passed using |
| // `getSwitchValue`. |
| Value discriminator; |
| if (blockArgMapping.size() > 1) |
| discriminator = |
| multiplexerBlock->addArgument(getSwitchValue(0).getType(), loc); |
| |
| multiplexerBlock->addArguments( |
| extraArgs, SmallVector<Location>(extraArgs.size(), loc)); |
| |
| return EdgeMultiplexer(multiplexerBlock, getSwitchValue, getUndefValue, |
| std::move(blockArgMapping), discriminator); |
| } |
| |
| /// Returns the created multiplexer block. |
| Block *getMultiplexerBlock() const { return multiplexerBlock; } |
| |
| /// Redirects `edge` to branch to the multiplexer block before continuing to |
| /// its original target. The edges successor must have originally been part |
| /// of the entry blocks array passed to the `create` function. `extraArgs` |
| /// must be used to pass along any additional values corresponding to |
| /// `extraArgs` in `create`. |
| void redirectEdge(Edge edge, ValueRange extraArgs = {}) const { |
| const auto *result = blockArgMapping.find(edge.getSuccessor()); |
| assert(result != blockArgMapping.end() && |
| "Edge was not originally passed to `create` method."); |
| |
| MutableOperandRange successorOperands = edge.getMutableSuccessorOperands(); |
| |
| // Extra arguments are always appended at the end of the block arguments. |
| unsigned extraArgsBeginIndex = |
| multiplexerBlock->getNumArguments() - extraArgs.size(); |
| // If a discriminator exists, it is right before the extra arguments. |
| std::optional<unsigned> discriminatorIndex = |
| discriminator ? extraArgsBeginIndex - 1 : std::optional<unsigned>{}; |
| |
| SmallVector<Value> newSuccOperands(multiplexerBlock->getNumArguments()); |
| for (BlockArgument argument : multiplexerBlock->getArguments()) { |
| unsigned index = argument.getArgNumber(); |
| if (index >= result->second && |
| index < result->second + edge.getSuccessor()->getNumArguments()) { |
| // Original block arguments to the entry block. |
| newSuccOperands[index] = |
| successorOperands[index - result->second].get(); |
| continue; |
| } |
| |
| // Discriminator value if it exists. |
| if (index == discriminatorIndex) { |
| newSuccOperands[index] = |
| getSwitchValue(result - blockArgMapping.begin()); |
| continue; |
| } |
| |
| // Followed by the extra arguments. |
| if (index >= extraArgsBeginIndex) { |
| newSuccOperands[index] = extraArgs[index - extraArgsBeginIndex]; |
| continue; |
| } |
| |
| // Otherwise undef values for any unused block arguments used by other |
| // entry blocks. |
| newSuccOperands[index] = getUndefValue(argument.getType()); |
| } |
| |
| edge.setSuccessor(multiplexerBlock); |
| successorOperands.assign(newSuccOperands); |
| } |
| |
| /// Creates a switch op using `builder` which dispatches to the original |
| /// successors of the edges passed to `create` minus the ones in `excluded`. |
| /// The builder's insertion point has to be in a block dominated by the |
| /// multiplexer block. All edges to the multiplexer block must have already |
| /// been redirected using `redirectEdge`. |
| void createSwitch( |
| Location loc, OpBuilder &builder, CFGToSCFInterface &interface, |
| const SmallPtrSetImpl<Block *> &excluded = SmallPtrSet<Block *, 1>{}) { |
| // We create the switch by creating a case for all entries and then |
| // splitting of the last entry as a default case. |
| |
| SmallVector<ValueRange> caseArguments; |
| SmallVector<unsigned> caseValues; |
| SmallVector<Block *> caseDestinations; |
| for (auto &&[index, pair] : llvm::enumerate(blockArgMapping)) { |
| auto &&[succ, offset] = pair; |
| if (excluded.contains(succ)) |
| continue; |
| |
| caseValues.push_back(index); |
| caseArguments.push_back(multiplexerBlock->getArguments().slice( |
| offset, succ->getNumArguments())); |
| caseDestinations.push_back(succ); |
| } |
| |
| // If we don't have a discriminator due to only having one entry we have to |
| // create a dummy flag for the switch. |
| Value realDiscriminator = discriminator; |
| if (!realDiscriminator || caseArguments.size() == 1) |
| realDiscriminator = getSwitchValue(0); |
| |
| caseValues.pop_back(); |
| Block *defaultDest = caseDestinations.pop_back_val(); |
| ValueRange defaultArgs = caseArguments.pop_back_val(); |
| |
| assert(!builder.getInsertionBlock()->hasNoPredecessors() && |
| "Edges need to be redirected prior to creating switch."); |
| interface.createCFGSwitchOp(loc, builder, realDiscriminator, caseValues, |
| caseDestinations, caseArguments, defaultDest, |
| defaultArgs); |
| } |
| |
| private: |
| /// Newly created multiplexer block. |
| Block *multiplexerBlock; |
| /// Callback used to create a constant suitable as flag for |
| /// the interfaces `createCFGSwitchOp`. |
| function_ref<Value(unsigned)> getSwitchValue; |
| /// Callback used to create undefined values of a given type. |
| function_ref<Value(Type)> getUndefValue; |
| |
| /// Mapping of the block arguments of an entry block to the corresponding |
| /// block arguments in the multiplexer block. Block arguments of an entry |
| /// block are simply appended ot the multiplexer block. This map simply |
| /// contains the offset to the range in the multiplexer block. |
| llvm::SmallMapVector<Block *, unsigned, 4> blockArgMapping; |
| /// Discriminator value used in the multiplexer block to dispatch to the |
| /// correct entry block. Null value if not required due to only having one |
| /// entry block. |
| Value discriminator; |
| |
| EdgeMultiplexer(Block *multiplexerBlock, |
| function_ref<Value(unsigned)> getSwitchValue, |
| function_ref<Value(Type)> getUndefValue, |
| llvm::SmallMapVector<Block *, unsigned, 4> &&entries, |
| Value dispatchFlag) |
| : multiplexerBlock(multiplexerBlock), getSwitchValue(getSwitchValue), |
| getUndefValue(getUndefValue), blockArgMapping(std::move(entries)), |
| discriminator(dispatchFlag) {} |
| }; |
| |
| /// Alternative implementation of DenseMapInfo<Operation*> using the operation |
| /// equivalence infrastructure to check whether two 'return-like' operations are |
| /// equivalent in the context of this transformation. This means that both |
| /// operations are of the same kind, have the same amount of operands and types |
| /// and the same attributes and properties. The operands themselves don't have |
| /// to be equivalent. |
| struct ReturnLikeOpEquivalence : public llvm::DenseMapInfo<Operation *> { |
| static unsigned getHashValue(const Operation *opC) { |
| return OperationEquivalence::computeHash( |
| const_cast<Operation *>(opC), |
| /*hashOperands=*/OperationEquivalence::ignoreHashValue, |
| /*hashResults=*/OperationEquivalence::ignoreHashValue, |
| OperationEquivalence::IgnoreLocations); |
| } |
| |
| static bool isEqual(const Operation *lhs, const Operation *rhs) { |
| if (lhs == rhs) |
| return true; |
| if (lhs == getTombstoneKey() || lhs == getEmptyKey() || |
| rhs == getTombstoneKey() || rhs == getEmptyKey()) |
| return false; |
| return OperationEquivalence::isEquivalentTo( |
| const_cast<Operation *>(lhs), const_cast<Operation *>(rhs), |
| OperationEquivalence::ignoreValueEquivalence, nullptr, |
| OperationEquivalence::IgnoreLocations); |
| } |
| }; |
| |
| /// Utility-class for transforming a region to only have one single block for |
| /// every return-like operation. |
| class ReturnLikeExitCombiner { |
| public: |
| ReturnLikeExitCombiner(Region &topLevelRegion, CFGToSCFInterface &interface) |
| : topLevelRegion(topLevelRegion), interface(interface) {} |
| |
| /// Transforms `returnLikeOp` to a branch to the only block in the |
| /// region with an instance of `returnLikeOp`s kind. |
| void combineExit(Operation *returnLikeOp, |
| function_ref<Value(unsigned)> getSwitchValue) { |
| auto [iter, inserted] = |
| returnLikeToCombinedExit.insert({returnLikeOp, nullptr}); |
| if (!inserted && iter->first == returnLikeOp) |
| return; |
| |
| Block *exitBlock = iter->second; |
| if (inserted) { |
| exitBlock = new Block; |
| iter->second = exitBlock; |
| topLevelRegion.push_back(exitBlock); |
| exitBlock->addArguments( |
| returnLikeOp->getOperandTypes(), |
| SmallVector<Location>(returnLikeOp->getNumOperands(), |
| returnLikeOp->getLoc())); |
| } |
| |
| auto builder = OpBuilder::atBlockTerminator(returnLikeOp->getBlock()); |
| interface.createSingleDestinationBranch(returnLikeOp->getLoc(), builder, |
| getSwitchValue(0), exitBlock, |
| returnLikeOp->getOperands()); |
| |
| if (!inserted) { |
| returnLikeOp->erase(); |
| return; |
| } |
| |
| returnLikeOp->moveBefore(exitBlock, exitBlock->end()); |
| returnLikeOp->setOperands(exitBlock->getArguments()); |
| } |
| |
| private: |
| /// Mapping of return-like operation to block. All return-like operations |
| /// of the same kind with the same attributes, properties and types are seen |
| /// as equivalent. First occurrence seen is kept in the map. |
| llvm::SmallDenseMap<Operation *, Block *, 4, ReturnLikeOpEquivalence> |
| returnLikeToCombinedExit; |
| Region &topLevelRegion; |
| CFGToSCFInterface &interface; |
| }; |
| |
| } // namespace |
| |
| /// Returns a range of all edges from `block` to each of its successors. |
| static auto successorEdges(Block *block) { |
| return llvm::map_range(llvm::seq(block->getNumSuccessors()), |
| [=](unsigned index) { return Edge(block, index); }); |
| } |
| |
| /// Calculates entry, exit and back edges of the given cycle. |
| static CycleEdges |
| calculateCycleEdges(const llvm::SmallSetVector<Block *, 4> &cycles) { |
| CycleEdges result; |
| SmallPtrSet<Block *, 8> entryBlocks; |
| |
| // First identify all exit and entry edges by checking whether any successors |
| // or predecessors are from outside the cycles. |
| for (Block *block : cycles) { |
| for (auto pred = block->pred_begin(); pred != block->pred_end(); pred++) { |
| if (cycles.contains(*pred)) |
| continue; |
| |
| result.entryEdges.emplace_back(*pred, pred.getSuccessorIndex()); |
| entryBlocks.insert(block); |
| } |
| |
| for (auto &&[succIndex, succ] : llvm::enumerate(block->getSuccessors())) { |
| if (cycles.contains(succ)) |
| continue; |
| |
| result.exitEdges.emplace_back(block, succIndex); |
| } |
| } |
| |
| // With the entry blocks identified, find all the back edges. |
| for (Block *block : cycles) { |
| for (auto &&[succIndex, succ] : llvm::enumerate(block->getSuccessors())) { |
| if (!entryBlocks.contains(succ)) |
| continue; |
| |
| result.backEdges.emplace_back(block, succIndex); |
| } |
| } |
| |
| return result; |
| } |
| |
| /// Creates a single entry block out of multiple entry edges using an edge |
| /// multiplexer and returns it. |
| static EdgeMultiplexer |
| createSingleEntryBlock(Location loc, ArrayRef<Edge> entryEdges, |
| function_ref<Value(unsigned)> getSwitchValue, |
| function_ref<Value(Type)> getUndefValue, |
| CFGToSCFInterface &interface) { |
| auto result = EdgeMultiplexer::create( |
| loc, llvm::map_to_vector(entryEdges, std::mem_fn(&Edge::getSuccessor)), |
| getSwitchValue, getUndefValue); |
| |
| // Redirect the edges prior to creating the switch op. |
| // We guarantee that predecessors are up to date. |
| for (Edge edge : entryEdges) |
| result.redirectEdge(edge); |
| |
| auto builder = OpBuilder::atBlockBegin(result.getMultiplexerBlock()); |
| result.createSwitch(loc, builder, interface); |
| |
| return result; |
| } |
| |
| namespace { |
| /// Special loop properties of a structured loop. |
| /// A structured loop is a loop satisfying all of the following: |
| /// * Has at most one entry, one exit and one back edge. |
| /// * The back edge originates from the same block as the exit edge. |
| struct StructuredLoopProperties { |
| /// Block containing both the single exit edge and the single back edge. |
| Block *latch; |
| /// Loop condition of type equal to a value returned by `getSwitchValue`. |
| Value condition; |
| /// Exit block which is the only successor of the loop. |
| Block *exitBlock; |
| }; |
| } // namespace |
| |
| /// Transforms a loop into a structured loop with only a single back edge and |
| /// exiting edge, originating from the same block. |
| static FailureOr<StructuredLoopProperties> createSingleExitingLatch( |
| Location loc, ArrayRef<Edge> backEdges, ArrayRef<Edge> exitEdges, |
| function_ref<Value(unsigned)> getSwitchValue, |
| function_ref<Value(Type)> getUndefValue, CFGToSCFInterface &interface, |
| ReturnLikeExitCombiner &exitCombiner) { |
| assert(llvm::all_equal( |
| llvm::map_range(backEdges, std::mem_fn(&Edge::getSuccessor))) && |
| "All repetition edges must lead to the single loop header"); |
| |
| // First create the multiplexer block, which will be our latch, for all back |
| // edges and exit edges. We pass an additional argument to the multiplexer |
| // block which indicates whether the latch was reached from what was |
| // originally a back edge or an exit block. |
| // This is later used to branch using the new only back edge. |
| SmallVector<Block *> successors; |
| llvm::append_range( |
| successors, llvm::map_range(backEdges, std::mem_fn(&Edge::getSuccessor))); |
| llvm::append_range( |
| successors, llvm::map_range(exitEdges, std::mem_fn(&Edge::getSuccessor))); |
| auto multiplexer = |
| EdgeMultiplexer::create(loc, successors, getSwitchValue, getUndefValue, |
| /*extraArgs=*/getSwitchValue(0).getType()); |
| |
| auto *latchBlock = multiplexer.getMultiplexerBlock(); |
| |
| // Create a separate exit block that comes right after the latch. |
| auto *exitBlock = new Block; |
| exitBlock->insertAfter(latchBlock); |
| |
| // Since this is a loop, all back edges point to the same loop header. |
| Block *loopHeader = backEdges.front().getSuccessor(); |
| |
| // Redirect the edges prior to creating the switch op. |
| // We guarantee that predecessors are up to date. |
| |
| // Redirecting back edges with `shouldRepeat` as 1. |
| for (Edge backEdge : backEdges) |
| multiplexer.redirectEdge(backEdge, /*extraArgs=*/getSwitchValue(1)); |
| |
| // Redirecting exits edges with `shouldRepeat` as 0. |
| for (Edge exitEdge : exitEdges) |
| multiplexer.redirectEdge(exitEdge, /*extraArgs=*/getSwitchValue(0)); |
| |
| // Create the new only back edge to the loop header. Branch to the |
| // exit block otherwise. |
| Value shouldRepeat = latchBlock->getArguments().back(); |
| { |
| auto builder = OpBuilder::atBlockBegin(latchBlock); |
| interface.createConditionalBranch( |
| loc, builder, shouldRepeat, loopHeader, |
| latchBlock->getArguments().take_front(loopHeader->getNumArguments()), |
| /*falseDest=*/exitBlock, |
| /*falseArgs=*/{}); |
| } |
| |
| { |
| auto builder = OpBuilder::atBlockBegin(exitBlock); |
| if (!exitEdges.empty()) { |
| // Create the switch dispatching to what were originally the multiple exit |
| // blocks. The loop header has to explicitly be excluded in the below |
| // switch as we would otherwise be creating a new loop again. All back |
| // edges leading to the loop header have already been handled in the |
| // switch above. The remaining edges can only jump to blocks outside the |
| // loop. |
| |
| SmallPtrSet<Block *, 1> excluded = {loopHeader}; |
| multiplexer.createSwitch(loc, builder, interface, excluded); |
| } else { |
| // A loop without an exit edge is a statically known infinite loop. |
| // Since structured control flow ops are not terminator ops, the caller |
| // has to create a fitting return-like unreachable terminator operation. |
| FailureOr<Operation *> terminator = interface.createUnreachableTerminator( |
| loc, builder, *latchBlock->getParent()); |
| if (failed(terminator)) |
| return failure(); |
| // Transform the just created transform operation in the case that an |
| // occurrence of it existed in input IR. |
| exitCombiner.combineExit(*terminator, getSwitchValue); |
| } |
| } |
| |
| return StructuredLoopProperties{latchBlock, /*condition=*/shouldRepeat, |
| exitBlock}; |
| } |
| |
| /// Transforms a structured loop into a loop in reduce form. |
| /// |
| /// Reduce form is defined as a structured loop where: |
| /// (0) No values defined within the loop body are used outside the loop body. |
| /// (1) The block arguments and successor operands of the exit block are equal |
| /// to the block arguments of the loop header and the successor operands |
| /// of the back edge. |
| /// |
| /// This is required for many structured control flow ops as they tend |
| /// to not have separate "loop result arguments" and "loop iteration arguments" |
| /// at the end of the block. Rather, the "loop iteration arguments" from the |
| /// last iteration are the result of the loop. |
| /// |
| /// Note that the requirement of (0) is shared with LCSSA form in LLVM. However, |
| /// due to this being a structured loop instead of a general loop, we do not |
| /// require complicated dominance algorithms nor SSA updating making this |
| /// implementation easier than creating a generic LCSSA transformation pass. |
| static SmallVector<Value> |
| transformToReduceLoop(Block *loopHeader, Block *exitBlock, |
| const llvm::SmallSetVector<Block *, 4> &loopBlocks, |
| function_ref<Value(Type)> getUndefValue, |
| DominanceInfo &dominanceInfo) { |
| Block *latch = exitBlock->getSinglePredecessor(); |
| assert(latch && |
| "Exit block must have only latch as predecessor at this point"); |
| assert(exitBlock->getNumArguments() == 0 && |
| "Exit block mustn't have any block arguments at this point"); |
| |
| unsigned loopHeaderIndex = 0; |
| unsigned exitBlockIndex = 1; |
| if (latch->getSuccessor(loopHeaderIndex) != loopHeader) |
| std::swap(loopHeaderIndex, exitBlockIndex); |
| |
| assert(latch->getSuccessor(loopHeaderIndex) == loopHeader); |
| assert(latch->getSuccessor(exitBlockIndex) == exitBlock); |
| |
| MutableOperandRange exitBlockSuccessorOperands = |
| getMutableSuccessorOperands(latch, exitBlockIndex); |
| // Save the values as a vector, not a `MutableOperandRange` as the latter gets |
| // invalidated when mutating the operands through a different |
| // `MutableOperandRange` of the same operation. |
| SmallVector<Value> loopHeaderSuccessorOperands = |
| llvm::to_vector(getSuccessorOperands(latch, loopHeaderIndex)); |
| |
| // Add all values used in the next iteration to the exit block. Replace |
| // any uses that are outside the loop with the newly created exit block. |
| for (Value arg : loopHeaderSuccessorOperands) { |
| BlockArgument exitArg = exitBlock->addArgument(arg.getType(), arg.getLoc()); |
| exitBlockSuccessorOperands.append(arg); |
| arg.replaceUsesWithIf(exitArg, [&](OpOperand &use) { |
| return !loopBlocks.contains(use.getOwner()->getBlock()); |
| }); |
| } |
| |
| // Loop below might add block arguments to the latch and loop header. |
| // Save the block arguments prior to the loop to not process these. |
| SmallVector<BlockArgument> latchBlockArgumentsPrior = |
| llvm::to_vector(latch->getArguments()); |
| SmallVector<BlockArgument> loopHeaderArgumentsPrior = |
| llvm::to_vector(loopHeader->getArguments()); |
| |
| // Go over all values defined within the loop body. If any of them are used |
| // outside the loop body, create a block argument on the exit block and loop |
| // header and replace the outside uses with the exit block argument. |
| // The loop header block argument is added to satisfy requirement (1) in the |
| // reduce form condition. |
| for (Block *loopBlock : loopBlocks) { |
| // Cache dominance queries for loopBlock. |
| // There are likely to be many duplicate queries as there can be many value |
| // definitions within a block. |
| llvm::SmallDenseMap<Block *, bool> dominanceCache; |
| // Returns true if `loopBlock` dominates `block`. |
| auto loopBlockDominates = [&](Block *block) { |
| auto [iter, inserted] = dominanceCache.insert({block, false}); |
| if (!inserted) |
| return iter->second; |
| iter->second = dominanceInfo.dominates(loopBlock, block); |
| return iter->second; |
| }; |
| |
| auto checkValue = [&](Value value) { |
| Value blockArgument; |
| for (OpOperand &use : llvm::make_early_inc_range(value.getUses())) { |
| // Go through all the parent blocks and find the one part of the region |
| // of the loop. If the block is part of the loop, then the value does |
| // not escape the loop through this use. |
| Block *currBlock = use.getOwner()->getBlock(); |
| while (currBlock && currBlock->getParent() != loopHeader->getParent()) |
| currBlock = currBlock->getParentOp()->getBlock(); |
| if (loopBlocks.contains(currBlock)) |
| continue; |
| |
| // Block argument is only created the first time it is required. |
| if (!blockArgument) { |
| blockArgument = |
| exitBlock->addArgument(value.getType(), value.getLoc()); |
| loopHeader->addArgument(value.getType(), value.getLoc()); |
| |
| // `value` might be defined in a block that does not dominate `latch` |
| // but previously dominated an exit block with a use. |
| // In this case, add a block argument to the latch and go through all |
| // predecessors. If the value dominates the predecessor, pass the |
| // value as a successor operand, otherwise pass undef. |
| // The above is unnecessary if the value is a block argument of the |
| // latch or if `value` dominates all predecessors. |
| Value argument = value; |
| if (value.getParentBlock() != latch && |
| llvm::any_of(latch->getPredecessors(), [&](Block *pred) { |
| return !loopBlockDominates(pred); |
| })) { |
| argument = latch->addArgument(value.getType(), value.getLoc()); |
| for (auto iter = latch->pred_begin(); iter != latch->pred_end(); |
| ++iter) { |
| Value succOperand = value; |
| if (!loopBlockDominates(*iter)) |
| succOperand = getUndefValue(value.getType()); |
| |
| getMutableSuccessorOperands(*iter, iter.getSuccessorIndex()) |
| .append(succOperand); |
| } |
| } |
| |
| loopHeaderSuccessorOperands.push_back(argument); |
| for (Edge edge : successorEdges(latch)) |
| edge.getMutableSuccessorOperands().append(argument); |
| } |
| |
| use.set(blockArgument); |
| } |
| }; |
| |
| if (loopBlock == latch) |
| llvm::for_each(latchBlockArgumentsPrior, checkValue); |
| else if (loopBlock == loopHeader) |
| llvm::for_each(loopHeaderArgumentsPrior, checkValue); |
| else |
| llvm::for_each(loopBlock->getArguments(), checkValue); |
| |
| for (Operation &op : *loopBlock) |
| llvm::for_each(op.getResults(), checkValue); |
| } |
| |
| // New block arguments may have been added to the loop header. |
| // Adjust the entry edges to pass undef values to these. |
| for (auto iter = loopHeader->pred_begin(); iter != loopHeader->pred_end(); |
| ++iter) { |
| // Latch successor arguments have already been handled. |
| if (*iter == latch) |
| continue; |
| |
| MutableOperandRange succOps = |
| getMutableSuccessorOperands(*iter, iter.getSuccessorIndex()); |
| succOps.append(llvm::map_to_vector( |
| loopHeader->getArguments().drop_front(succOps.size()), |
| [&](BlockArgument arg) { return getUndefValue(arg.getType()); })); |
| } |
| |
| return loopHeaderSuccessorOperands; |
| } |
| |
| /// Transforms all outer-most cycles in the region with the region entry |
| /// `regionEntry` into structured loops. Returns the entry blocks of any newly |
| /// created regions potentially requiring further transformations. |
| static FailureOr<SmallVector<Block *>> transformCyclesToSCFLoops( |
| Block *regionEntry, function_ref<Value(unsigned)> getSwitchValue, |
| function_ref<Value(Type)> getUndefValue, CFGToSCFInterface &interface, |
| DominanceInfo &dominanceInfo, ReturnLikeExitCombiner &exitCombiner) { |
| SmallVector<Block *> newSubRegions; |
| auto scc = llvm::scc_begin(regionEntry); |
| while (!scc.isAtEnd()) { |
| if (!scc.hasCycle()) { |
| ++scc; |
| continue; |
| } |
| |
| // Save the set and increment the SCC iterator early to avoid our |
| // modifications breaking the SCC iterator. |
| llvm::SmallSetVector<Block *, 4> cycleBlockSet(scc->begin(), scc->end()); |
| ++scc; |
| |
| CycleEdges edges = calculateCycleEdges(cycleBlockSet); |
| Block *loopHeader = edges.entryEdges.front().getSuccessor(); |
| // First turn the cycle into a loop by creating a single entry block if |
| // needed. |
| if (edges.entryEdges.size() > 1) { |
| SmallVector<Edge> edgesToEntryBlocks; |
| llvm::append_range(edgesToEntryBlocks, edges.entryEdges); |
| llvm::append_range(edgesToEntryBlocks, edges.backEdges); |
| |
| EdgeMultiplexer multiplexer = createSingleEntryBlock( |
| loopHeader->getTerminator()->getLoc(), edgesToEntryBlocks, |
| getSwitchValue, getUndefValue, interface); |
| |
| loopHeader = multiplexer.getMultiplexerBlock(); |
| } |
| cycleBlockSet.insert(loopHeader); |
| |
| // Then turn it into a structured loop by creating a single latch. |
| FailureOr<StructuredLoopProperties> loopProperties = |
| createSingleExitingLatch( |
| edges.backEdges.front().getFromBlock()->getTerminator()->getLoc(), |
| edges.backEdges, edges.exitEdges, getSwitchValue, getUndefValue, |
| interface, exitCombiner); |
| if (failed(loopProperties)) |
| return failure(); |
| |
| Block *latchBlock = loopProperties->latch; |
| Block *exitBlock = loopProperties->exitBlock; |
| cycleBlockSet.insert(latchBlock); |
| cycleBlockSet.insert(loopHeader); |
| |
| // Finally, turn it into reduce form. |
| SmallVector<Value> iterationValues = transformToReduceLoop( |
| loopHeader, exitBlock, cycleBlockSet, getUndefValue, dominanceInfo); |
| |
| // Create a block acting as replacement for the loop header and insert |
| // the structured loop into it. |
| auto *newLoopParentBlock = new Block; |
| newLoopParentBlock->insertBefore(loopHeader); |
| addBlockArgumentsFromOther(newLoopParentBlock, loopHeader); |
| |
| Region::BlockListType &blocks = regionEntry->getParent()->getBlocks(); |
| Region loopBody; |
| // Make sure the loop header is the entry block. |
| loopBody.push_back(blocks.remove(loopHeader)); |
| for (Block *block : cycleBlockSet) |
| if (block != latchBlock && block != loopHeader) |
| loopBody.push_back(blocks.remove(block)); |
| // And the latch is the last block. |
| loopBody.push_back(blocks.remove(latchBlock)); |
| |
| Operation *oldTerminator = latchBlock->getTerminator(); |
| oldTerminator->remove(); |
| |
| auto builder = OpBuilder::atBlockBegin(newLoopParentBlock); |
| FailureOr<Operation *> structuredLoopOp = |
| interface.createStructuredDoWhileLoopOp( |
| builder, oldTerminator, newLoopParentBlock->getArguments(), |
| loopProperties->condition, iterationValues, std::move(loopBody)); |
| if (failed(structuredLoopOp)) |
| return failure(); |
| oldTerminator->erase(); |
| |
| newSubRegions.push_back(loopHeader); |
| |
| for (auto &&[oldValue, newValue] : llvm::zip( |
| exitBlock->getArguments(), (*structuredLoopOp)->getResults())) |
| oldValue.replaceAllUsesWith(newValue); |
| |
| loopHeader->replaceAllUsesWith(newLoopParentBlock); |
| // Merge the exit block right after the loop operation. |
| newLoopParentBlock->getOperations().splice(newLoopParentBlock->end(), |
| exitBlock->getOperations()); |
| exitBlock->erase(); |
| } |
| return newSubRegions; |
| } |
| |
| /// Makes sure the branch region only has a single exit. This is required by the |
| /// recursive part of the algorithm, as it expects the CFG to be single-entry |
| /// and single-exit. This is done by simply creating an empty block if there |
| /// is more than one block with an edge to the continuation block. All blocks |
| /// with edges to the continuation are then redirected to this block. A region |
| /// terminator is later placed into the block. |
| static void createSingleExitBranchRegion( |
| ArrayRef<Block *> branchRegion, Block *continuation, |
| SmallVectorImpl<std::pair<Block *, SmallVector<Value>>> &createdEmptyBlocks, |
| Region &conditionalRegion) { |
| Block *singleExitBlock = nullptr; |
| std::optional<Edge> previousEdgeToContinuation; |
| Region::BlockListType &parentBlockList = |
| branchRegion.front()->getParent()->getBlocks(); |
| for (Block *block : branchRegion) { |
| for (Edge edge : successorEdges(block)) { |
| if (edge.getSuccessor() != continuation) |
| continue; |
| |
| if (!previousEdgeToContinuation) { |
| previousEdgeToContinuation = edge; |
| continue; |
| } |
| |
| // If this is not the first edge to the continuation we create the |
| // single exit block and redirect the edges. |
| if (!singleExitBlock) { |
| singleExitBlock = new Block; |
| addBlockArgumentsFromOther(singleExitBlock, continuation); |
| previousEdgeToContinuation->setSuccessor(singleExitBlock); |
| createdEmptyBlocks.emplace_back(singleExitBlock, |
| singleExitBlock->getArguments()); |
| } |
| |
| edge.setSuccessor(singleExitBlock); |
| } |
| |
| conditionalRegion.push_back(parentBlockList.remove(block)); |
| } |
| |
| if (singleExitBlock) |
| conditionalRegion.push_back(singleExitBlock); |
| } |
| |
| /// Returns true if this block is an exit block of the region. |
| static bool isRegionExitBlock(Block *block) { |
| return block->getNumSuccessors() == 0; |
| } |
| |
| /// Transforms the first occurrence of conditional control flow in `regionEntry` |
| /// into conditionally executed regions. Returns the entry block of the created |
| /// regions and the region after the conditional control flow. |
| static FailureOr<SmallVector<Block *>> transformToStructuredCFBranches( |
| Block *regionEntry, function_ref<Value(unsigned)> getSwitchValue, |
| function_ref<Value(Type)> getUndefValue, CFGToSCFInterface &interface, |
| DominanceInfo &dominanceInfo) { |
| // Trivial region. |
| if (regionEntry->getNumSuccessors() == 0) |
| return SmallVector<Block *>{}; |
| |
| if (regionEntry->getNumSuccessors() == 1) { |
| // Single successor we can just splice together. |
| Block *successor = regionEntry->getSuccessor(0); |
| for (auto &&[oldValue, newValue] : llvm::zip( |
| successor->getArguments(), getSuccessorOperands(regionEntry, 0))) |
| oldValue.replaceAllUsesWith(newValue); |
| regionEntry->getTerminator()->erase(); |
| |
| regionEntry->getOperations().splice(regionEntry->end(), |
| successor->getOperations()); |
| successor->erase(); |
| return SmallVector<Block *>{regionEntry}; |
| } |
| |
| // Split the CFG into "#numSuccessor + 1" regions. |
| // For every edge to a successor, the blocks it solely dominates are |
| // determined and become the region following that edge. |
| // The last region is the continuation that follows the branch regions. |
| SmallPtrSet<Block *, 8> notContinuation; |
| notContinuation.insert(regionEntry); |
| SmallVector<SmallVector<Block *>> successorBranchRegions( |
| regionEntry->getNumSuccessors()); |
| for (auto &&[blockList, succ] : |
| llvm::zip(successorBranchRegions, regionEntry->getSuccessors())) { |
| // If the region entry is not the only predecessor, then the edge does not |
| // dominate the block it leads to. |
| if (succ->getSinglePredecessor() != regionEntry) |
| continue; |
| |
| // Otherwise get all blocks it dominates in DFS/pre-order. |
| DominanceInfoNode *node = dominanceInfo.getNode(succ); |
| for (DominanceInfoNode *curr : llvm::depth_first(node)) { |
| blockList.push_back(curr->getBlock()); |
| notContinuation.insert(curr->getBlock()); |
| } |
| } |
| |
| // Finds all relevant edges and checks the shape of the control flow graph at |
| // this point. |
| // Branch regions may either: |
| // * Be post-dominated by the continuation |
| // * Be post-dominated by a return-like op |
| // * Dominate a return-like op and have an edge to the continuation. |
| // |
| // The control flow graph may then be one of three cases: |
| // 1) All branch regions are post-dominated by the continuation. This is the |
| // usual case. If there are multiple entry blocks into the continuation a |
| // single entry block has to be created. A structured control flow op |
| // can then be created from the branch regions. |
| // |
| // 2) No branch region has an edge to a continuation: |
| // +-----+ |
| // +-----+ bb0 +----+ |
| // v +-----+ v |
| // Region 1 +-+--+ ... +-+--+ Region n |
| // |ret1| |ret2| |
| // +----+ +----+ |
| // |
| // This can only occur if every region ends with a different kind of |
| // return-like op. In that case the control flow operation must stay as we are |
| // unable to create a single exit-block. We can nevertheless process all its |
| // successors as they single-entry, single-exit regions. |
| // |
| // 3) Only some branch regions are post-dominated by the continuation. |
| // The other branch regions may either be post-dominated by a return-like op |
| // or lead to either the continuation or return-like op. |
| // In this case we also create a single entry block like in 1) that also |
| // includes all edges to the return-like op: |
| // +-----+ |
| // +-----+ bb0 +----+ |
| // v +-----+ v |
| // Region 1 +-+-+ ... +-+-+ Region n |
| // +---+ +---+ |
| // +---+ |... ... |
| // |ret|<-+ | | |
| // +---+ | +---+ | |
| // +---->++ ++<---+ |
| // | | |
| // ++ ++ Region T |
| // +---+ |
| // This transforms to: |
| // +-----+ |
| // +-----+ bb0 +----+ |
| // v +-----+ v |
| // Region 1 +-+-+ ... +-+-+ Region n |
| // +---+ +---+ |
| // ... +-----+ ... |
| // +---->+ bbM +<---+ |
| // +-----+ |
| // +-----+ | |
| // | v |
| // +---+ | +---+ |
| // |ret+<---+ ++ ++ |
| // +---+ | | |
| // ++ ++ Region T |
| // +---+ |
| // |
| // bb0 to bbM is now a single-entry, single-exit region that applies to case |
| // 1). The control flow op at the end of bbM will trigger case 2. |
| SmallVector<Edge> continuationEdges; |
| bool continuationPostDominatesAllRegions = true; |
| bool noSuccessorHasContinuationEdge = true; |
| for (auto &&[entryEdge, branchRegion] : |
| llvm::zip(successorEdges(regionEntry), successorBranchRegions)) { |
| |
| // If the branch region is empty then the branch target itself is part of |
| // the continuation. |
| if (branchRegion.empty()) { |
| continuationEdges.push_back(entryEdge); |
| noSuccessorHasContinuationEdge = false; |
| continue; |
| } |
| |
| for (Block *block : branchRegion) { |
| if (isRegionExitBlock(block)) { |
| // If a return-like op is part of the branch region then the |
| // continuation no longer post-dominates the branch region. |
| // Add all its incoming edges to edge list to create the single-exit |
| // block for all branch regions. |
| continuationPostDominatesAllRegions = false; |
| for (auto iter = block->pred_begin(); iter != block->pred_end(); |
| ++iter) { |
| continuationEdges.emplace_back(*iter, iter.getSuccessorIndex()); |
| } |
| continue; |
| } |
| |
| for (Edge edge : successorEdges(block)) { |
| if (notContinuation.contains(edge.getSuccessor())) |
| continue; |
| |
| continuationEdges.push_back(edge); |
| noSuccessorHasContinuationEdge = false; |
| } |
| } |
| } |
| |
| // case 2) Keep the control flow op but process its successors further. |
| if (noSuccessorHasContinuationEdge) |
| return llvm::to_vector(regionEntry->getSuccessors()); |
| |
| Block *continuation = llvm::find_singleton<Block>( |
| continuationEdges, [](Edge edge, bool) { return edge.getSuccessor(); }, |
| /*AllowRepeats=*/true); |
| |
| // In case 3) or if not all continuation edges have the same entry block, |
| // create a single entry block as continuation for all branch regions. |
| if (!continuation || !continuationPostDominatesAllRegions) { |
| EdgeMultiplexer multiplexer = createSingleEntryBlock( |
| continuationEdges.front().getFromBlock()->getTerminator()->getLoc(), |
| continuationEdges, getSwitchValue, getUndefValue, interface); |
| continuation = multiplexer.getMultiplexerBlock(); |
| } |
| |
| // Trigger reprocess of case 3) after creating the single entry block. |
| if (!continuationPostDominatesAllRegions) { |
| // Unlike in the general case, we are explicitly revisiting the same region |
| // entry again after having changed its control flow edges and dominance. |
| // We have to therefore explicitly invalidate the dominance tree. |
| dominanceInfo.invalidate(regionEntry->getParent()); |
| return SmallVector<Block *>{regionEntry}; |
| } |
| |
| SmallVector<Block *> newSubRegions; |
| |
| // Empty blocks with the values they return to the parent op. |
| SmallVector<std::pair<Block *, SmallVector<Value>>> createdEmptyBlocks; |
| |
| // Create the branch regions. |
| std::vector<Region> conditionalRegions(successorBranchRegions.size()); |
| for (auto &&[branchRegion, entryEdge, conditionalRegion] : |
| llvm::zip(successorBranchRegions, successorEdges(regionEntry), |
| conditionalRegions)) { |
| if (branchRegion.empty()) { |
| // If no block is part of the branch region, we create a dummy block to |
| // place the region terminator into. |
| createdEmptyBlocks.emplace_back( |
| new Block, llvm::to_vector(entryEdge.getSuccessorOperands())); |
| conditionalRegion.push_back(createdEmptyBlocks.back().first); |
| continue; |
| } |
| |
| createSingleExitBranchRegion(branchRegion, continuation, createdEmptyBlocks, |
| conditionalRegion); |
| |
| // The entries of the branch regions may only have redundant block arguments |
| // since the edge to the branch region is always dominating. |
| Block *subRegionEntryBlock = &conditionalRegion.front(); |
| for (auto &&[oldValue, newValue] : |
| llvm::zip(subRegionEntryBlock->getArguments(), |
| entryEdge.getSuccessorOperands())) |
| oldValue.replaceAllUsesWith(newValue); |
| |
| subRegionEntryBlock->eraseArguments(0, |
| subRegionEntryBlock->getNumArguments()); |
| newSubRegions.push_back(subRegionEntryBlock); |
| } |
| |
| Operation *structuredCondOp; |
| { |
| auto opBuilder = OpBuilder::atBlockTerminator(regionEntry); |
| FailureOr<Operation *> result = interface.createStructuredBranchRegionOp( |
| opBuilder, regionEntry->getTerminator(), |
| continuation->getArgumentTypes(), conditionalRegions); |
| if (failed(result)) |
| return failure(); |
| structuredCondOp = *result; |
| regionEntry->getTerminator()->erase(); |
| } |
| |
| for (auto &&[block, valueRange] : createdEmptyBlocks) { |
| auto builder = OpBuilder::atBlockEnd(block); |
| LogicalResult result = interface.createStructuredBranchRegionTerminatorOp( |
| structuredCondOp->getLoc(), builder, structuredCondOp, nullptr, |
| valueRange); |
| if (failed(result)) |
| return failure(); |
| } |
| |
| // Any leftover users of the continuation must be from unconditional branches |
| // in a branch region. There can only be at most one per branch region as |
| // all branch regions have been made single-entry single-exit above. |
| // Replace them with the region terminator. |
| for (Operation *user : llvm::make_early_inc_range(continuation->getUsers())) { |
| assert(user->getNumSuccessors() == 1); |
| auto builder = OpBuilder::atBlockTerminator(user->getBlock()); |
| LogicalResult result = interface.createStructuredBranchRegionTerminatorOp( |
| user->getLoc(), builder, structuredCondOp, user, |
| getMutableSuccessorOperands(user->getBlock(), 0).getAsOperandRange()); |
| if (failed(result)) |
| return failure(); |
| user->erase(); |
| } |
| |
| for (auto &&[oldValue, newValue] : |
| llvm::zip(continuation->getArguments(), structuredCondOp->getResults())) |
| oldValue.replaceAllUsesWith(newValue); |
| |
| // Splice together the continuations operations with the region entry. |
| regionEntry->getOperations().splice(regionEntry->end(), |
| continuation->getOperations()); |
| |
| continuation->erase(); |
| |
| // After splicing the continuation, the region has to be reprocessed as it has |
| // new successors. |
| newSubRegions.push_back(regionEntry); |
| |
| return newSubRegions; |
| } |
| |
| /// Transforms the region to only have a single block for every kind of |
| /// return-like operation that all previous occurrences of the return-like op |
| /// branch to. If the region only contains a single kind of return-like |
| /// operation, it creates a single-entry and single-exit region. |
| static ReturnLikeExitCombiner createSingleExitBlocksForReturnLike( |
| Region ®ion, function_ref<Value(unsigned)> getSwitchValue, |
| CFGToSCFInterface &interface) { |
| ReturnLikeExitCombiner exitCombiner(region, interface); |
| |
| for (Block &block : region.getBlocks()) { |
| if (block.getNumSuccessors() != 0) |
| continue; |
| exitCombiner.combineExit(block.getTerminator(), getSwitchValue); |
| } |
| |
| return exitCombiner; |
| } |
| |
| /// Checks all preconditions of the transformation prior to any transformations. |
| /// Returns failure if any precondition is violated. |
| static LogicalResult checkTransformationPreconditions(Region ®ion) { |
| for (Block &block : region.getBlocks()) |
| if (block.hasNoPredecessors() && !block.isEntryBlock()) |
| return block.front().emitOpError( |
| "transformation does not support unreachable blocks"); |
| |
| WalkResult result = region.walk([](Operation *operation) { |
| if (operation->getNumSuccessors() == 0) |
| return WalkResult::advance(); |
| |
| // This transformation requires all ops with successors to implement the |
| // branch op interface. It is impossible to adjust their block arguments |
| // otherwise. |
| auto branchOpInterface = dyn_cast<BranchOpInterface>(operation); |
| if (!branchOpInterface) { |
| operation->emitOpError("transformation does not support terminators with " |
| "successors not implementing BranchOpInterface"); |
| return WalkResult::interrupt(); |
| } |
| // Branch operations must have no side effects. Replacing them would not be |
| // valid otherwise. |
| if (!isMemoryEffectFree(branchOpInterface)) { |
| branchOpInterface->emitOpError( |
| "transformation does not support terminators with side effects"); |
| return WalkResult::interrupt(); |
| } |
| |
| for (unsigned index : llvm::seq(operation->getNumSuccessors())) { |
| SuccessorOperands succOps = branchOpInterface.getSuccessorOperands(index); |
| |
| // We cannot support operations with operation-produced successor operands |
| // as it is currently not possible to pass them to any block arguments |
| // other than the first. This breaks creating multiplexer blocks and would |
| // likely need special handling elsewhere too. |
| if (succOps.getProducedOperandCount() == 0) |
| continue; |
| |
| branchOpInterface->emitOpError("transformation does not support " |
| "operations with operation-produced " |
| "successor operands"); |
| return WalkResult::interrupt(); |
| } |
| return WalkResult::advance(); |
| }); |
| return failure(result.wasInterrupted()); |
| } |
| |
| FailureOr<bool> mlir::transformCFGToSCF(Region ®ion, |
| CFGToSCFInterface &interface, |
| DominanceInfo &dominanceInfo) { |
| if (region.empty() || region.hasOneBlock()) |
| return false; |
| |
| if (failed(checkTransformationPreconditions(region))) |
| return failure(); |
| |
| DenseMap<Type, Value> typedUndefCache; |
| auto getUndefValue = [&](Type type) { |
| auto [iter, inserted] = typedUndefCache.insert({type, nullptr}); |
| if (!inserted) |
| return iter->second; |
| |
| auto constantBuilder = OpBuilder::atBlockBegin(®ion.front()); |
| |
| iter->second = |
| interface.getUndefValue(region.getLoc(), constantBuilder, type); |
| return iter->second; |
| }; |
| |
| // The transformation only creates all values in the range of 0 to |
| // max(#numSuccessors). Therefore using a vector instead of a map. |
| SmallVector<Value> switchValueCache; |
| auto getSwitchValue = [&](unsigned value) { |
| if (value < switchValueCache.size()) |
| if (switchValueCache[value]) |
| return switchValueCache[value]; |
| |
| auto constantBuilder = OpBuilder::atBlockBegin(®ion.front()); |
| |
| switchValueCache.resize( |
| std::max<size_t>(switchValueCache.size(), value + 1)); |
| |
| switchValueCache[value] = |
| interface.getCFGSwitchValue(region.getLoc(), constantBuilder, value); |
| return switchValueCache[value]; |
| }; |
| |
| ReturnLikeExitCombiner exitCombiner = |
| createSingleExitBlocksForReturnLike(region, getSwitchValue, interface); |
| |
| // Invalidate any dominance tree on the region as the exit combiner has |
| // added new blocks and edges. |
| dominanceInfo.invalidate(®ion); |
| |
| SmallVector<Block *> workList = {®ion.front()}; |
| while (!workList.empty()) { |
| Block *current = workList.pop_back_val(); |
| |
| // Turn all top-level cycles in the CFG to structured control flow first. |
| // After this transformation, the remaining CFG ops form a DAG. |
| FailureOr<SmallVector<Block *>> newRegions = |
| transformCyclesToSCFLoops(current, getSwitchValue, getUndefValue, |
| interface, dominanceInfo, exitCombiner); |
| if (failed(newRegions)) |
| return failure(); |
| |
| // Add the newly created subregions to the worklist. These are the |
| // bodies of the loops. |
| llvm::append_range(workList, *newRegions); |
| // Invalidate the dominance tree as blocks have been moved, created and |
| // added during the cycle to structured loop transformation. |
| if (!newRegions->empty()) |
| dominanceInfo.invalidate(current->getParent()); |
| |
| newRegions = transformToStructuredCFBranches( |
| current, getSwitchValue, getUndefValue, interface, dominanceInfo); |
| if (failed(newRegions)) |
| return failure(); |
| // Invalidating the dominance tree is generally not required by the |
| // transformation above as the new region entries correspond to unaffected |
| // subtrees in the dominator tree. Only its parent nodes have changed but |
| // won't be visited again. |
| llvm::append_range(workList, *newRegions); |
| } |
| |
| return true; |
| } |