//===- 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" usingnamespacemlir; /// 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) { … } /// Return the operand range used to transfer operands from `block` to its /// successor with the given index. static OperandRange getSuccessorOperands(Block *block, unsigned 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) { … } 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 { … }; /// 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 { … }; /// 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 { … }; /// 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 *> { … }; /// Utility-class for transforming a region to only have one single block for /// every return-like operation. class ReturnLikeExitCombiner { … }; } // namespace /// Returns a range of all edges from `block` to each of its successors. static auto successorEdges(Block *block) { … } /// Calculates entry, exit and back edges of the given cycle. static CycleEdges calculateCycleEdges(const llvm::SmallSetVector<Block *, 4> &cycles) { … } /// 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) { … } 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 { … }; } // 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) { … } /// 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) { … } /// 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) { … } /// 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) { … } /// Returns true if this block is an exit block of the region. static bool isRegionExitBlock(Block *block) { … } /// 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) { … } /// 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) { … } /// Checks all preconditions of the transformation prior to any transformations. /// Returns failure if any precondition is violated. static LogicalResult checkTransformationPreconditions(Region ®ion) { … } FailureOr<bool> mlir::transformCFGToSCF(Region ®ion, CFGToSCFInterface &interface, DominanceInfo &dominanceInfo) { … }
Codebase Browser
llvm