//===- SCFToControlFlow.cpp - SCF to CF conversion ------------------------===// // // 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 file implements a pass to convert scf.for, scf.if and loop.terminator // ops into standard CFG ops. // //===----------------------------------------------------------------------===// #include "mlir/Conversion/SCFToControlFlow/SCFToControlFlow.h" #include "mlir/Dialect/Arith/IR/Arith.h" #include "mlir/Dialect/ControlFlow/IR/ControlFlowOps.h" #include "mlir/Dialect/LLVMIR/LLVMDialect.h" #include "mlir/Dialect/SCF/IR/SCF.h" #include "mlir/Dialect/SCF/Transforms/Transforms.h" #include "mlir/IR/Builders.h" #include "mlir/IR/BuiltinOps.h" #include "mlir/IR/IRMapping.h" #include "mlir/IR/MLIRContext.h" #include "mlir/IR/PatternMatch.h" #include "mlir/Transforms/DialectConversion.h" #include "mlir/Transforms/Passes.h" namespace mlir { #define GEN_PASS_DEF_SCFTOCONTROLFLOW #include "mlir/Conversion/Passes.h.inc" } // namespace mlir usingnamespacemlir; usingnamespacemlir::scf; namespace { struct SCFToControlFlowPass : public impl::SCFToControlFlowBase<SCFToControlFlowPass> { … }; // Create a CFG subgraph for the loop around its body blocks (if the body // contained other loops, they have been already lowered to a flow of blocks). // Maintain the invariants that a CFG subgraph created for any loop has a single // entry and a single exit, and that the entry/exit blocks are respectively // first/last blocks in the parent region. The original loop operation is // replaced by the initialization operations that set up the initial value of // the loop induction variable (%iv) and computes the loop bounds that are loop- // invariant for affine loops. The operations following the original scf.for // are split out into a separate continuation (exit) block. A condition block is // created before the continuation block. It checks the exit condition of the // loop and branches either to the continuation block, or to the first block of // the body. The condition block takes as arguments the values of the induction // variable followed by loop-carried values. Since it dominates both the body // blocks and the continuation block, loop-carried values are visible in all of // those blocks. Induction variable modification is appended to the last block // of the body (which is the exit block from the body subgraph thanks to the // invariant we maintain) along with a branch that loops back to the condition // block. Loop-carried values are the loop terminator operands, which are // forwarded to the branch. // // +---------------------------------+ // | <code before the ForOp> | // | <definitions of %init...> | // | <compute initial %iv value> | // | cf.br cond(%iv, %init...) | // +---------------------------------+ // | // -------| | // | v v // | +--------------------------------+ // | | cond(%iv, %init...): | // | | <compare %iv to upper bound> | // | | cf.cond_br %r, body, end | // | +--------------------------------+ // | | | // | | -------------| // | v | // | +--------------------------------+ | // | | body-first: | | // | | <%init visible by dominance> | | // | | <body contents> | | // | +--------------------------------+ | // | | | // | ... | // | | | // | +--------------------------------+ | // | | body-last: | | // | | <body contents> | | // | | <operands of yield = %yields>| | // | | %new_iv =<add step to %iv> | | // | | cf.br cond(%new_iv, %yields) | | // | +--------------------------------+ | // | | | // |----------- |-------------------- // v // +--------------------------------+ // | end: | // | <code after the ForOp> | // | <%init visible by dominance> | // +--------------------------------+ // struct ForLowering : public OpRewritePattern<ForOp> { … }; // Create a CFG subgraph for the scf.if operation (including its "then" and // optional "else" operation blocks). We maintain the invariants that the // subgraph has a single entry and a single exit point, and that the entry/exit // blocks are respectively the first/last block of the enclosing region. The // operations following the scf.if are split into a continuation (subgraph // exit) block. The condition is lowered to a chain of blocks that implement the // short-circuit scheme. The "scf.if" operation is replaced with a conditional // branch to either the first block of the "then" region, or to the first block // of the "else" region. In these blocks, "scf.yield" is unconditional branches // to the post-dominating block. When the "scf.if" does not return values, the // post-dominating block is the same as the continuation block. When it returns // values, the post-dominating block is a new block with arguments that // correspond to the values returned by the "scf.if" that unconditionally // branches to the continuation block. This allows block arguments to dominate // any uses of the hitherto "scf.if" results that they replaced. (Inserting a // new block allows us to avoid modifying the argument list of an existing // block, which is illegal in a conversion pattern). When the "else" region is // empty, which is only allowed for "scf.if"s that don't return values, the // condition branches directly to the continuation block. // // CFG for a scf.if with else and without results. // // +--------------------------------+ // | <code before the IfOp> | // | cf.cond_br %cond, %then, %else | // +--------------------------------+ // | | // | --------------| // v | // +--------------------------------+ | // | then: | | // | <then contents> | | // | cf.br continue | | // +--------------------------------+ | // | | // |---------- |------------- // | V // | +--------------------------------+ // | | else: | // | | <else contents> | // | | cf.br continue | // | +--------------------------------+ // | | // ------| | // v v // +--------------------------------+ // | continue: | // | <code after the IfOp> | // +--------------------------------+ // // CFG for a scf.if with results. // // +--------------------------------+ // | <code before the IfOp> | // | cf.cond_br %cond, %then, %else | // +--------------------------------+ // | | // | --------------| // v | // +--------------------------------+ | // | then: | | // | <then contents> | | // | cf.br dom(%args...) | | // +--------------------------------+ | // | | // |---------- |------------- // | V // | +--------------------------------+ // | | else: | // | | <else contents> | // | | cf.br dom(%args...) | // | +--------------------------------+ // | | // ------| | // v v // +--------------------------------+ // | dom(%args...): | // | cf.br continue | // +--------------------------------+ // | // v // +--------------------------------+ // | continue: | // | <code after the IfOp> | // +--------------------------------+ // struct IfLowering : public OpRewritePattern<IfOp> { … }; struct ExecuteRegionLowering : public OpRewritePattern<ExecuteRegionOp> { … }; struct ParallelLowering : public OpRewritePattern<mlir::scf::ParallelOp> { … }; /// Create a CFG subgraph for this loop construct. The regions of the loop need /// not be a single block anymore (for example, if other SCF constructs that /// they contain have been already converted to CFG), but need to be single-exit /// from the last block of each region. The operations following the original /// WhileOp are split into a new continuation block. Both regions of the WhileOp /// are inlined, and their terminators are rewritten to organize the control /// flow implementing the loop as follows. /// /// +---------------------------------+ /// | <code before the WhileOp> | /// | cf.br ^before(%operands...) | /// +---------------------------------+ /// | /// -------| | /// | v v /// | +--------------------------------+ /// | | ^before(%bargs...): | /// | | %vals... = <some payload> | /// | +--------------------------------+ /// | | /// | ... /// | | /// | +--------------------------------+ /// | | ^before-last: /// | | %cond = <compute condition> | /// | | cf.cond_br %cond, | /// | | ^after(%vals...), ^cont | /// | +--------------------------------+ /// | | | /// | | -------------| /// | v | /// | +--------------------------------+ | /// | | ^after(%aargs...): | | /// | | <body contents> | | /// | +--------------------------------+ | /// | | | /// | ... | /// | | | /// | +--------------------------------+ | /// | | ^after-last: | | /// | | %yields... = <some payload> | | /// | | cf.br ^before(%yields...) | | /// | +--------------------------------+ | /// | | | /// |----------- |-------------------- /// v /// +--------------------------------+ /// | ^cont: | /// | <code after the WhileOp> | /// | <%vals from 'before' region | /// | visible by dominance> | /// +--------------------------------+ /// /// Values are communicated between ex-regions (the groups of blocks that used /// to form a region before inlining) through block arguments of their /// entry blocks, which are visible in all other dominated blocks. Similarly, /// the results of the WhileOp are defined in the 'before' region, which is /// required to have a single existing block, and are therefore accessible in /// the continuation block due to dominance. struct WhileLowering : public OpRewritePattern<WhileOp> { … }; /// Optimized version of the above for the case of the "after" region merely /// forwarding its arguments back to the "before" region (i.e., a "do-while" /// loop). This avoid inlining the "after" region completely and branches back /// to the "before" entry instead. struct DoWhileLowering : public OpRewritePattern<WhileOp> { … }; /// Lower an `scf.index_switch` operation to a `cf.switch` operation. struct IndexSwitchLowering : public OpRewritePattern<IndexSwitchOp> { … }; /// Lower an `scf.forall` operation to an `scf.parallel` op, assuming that it /// has no shared outputs. Ops with shared outputs should be bufferized first. /// Specialized lowerings for `scf.forall` (e.g., for GPUs) exist in other /// dialects/passes. struct ForallLowering : public OpRewritePattern<mlir::scf::ForallOp> { … }; } // namespace LogicalResult ForLowering::matchAndRewrite(ForOp forOp, PatternRewriter &rewriter) const { … } LogicalResult IfLowering::matchAndRewrite(IfOp ifOp, PatternRewriter &rewriter) const { … } LogicalResult ExecuteRegionLowering::matchAndRewrite(ExecuteRegionOp op, PatternRewriter &rewriter) const { … } LogicalResult ParallelLowering::matchAndRewrite(ParallelOp parallelOp, PatternRewriter &rewriter) const { … } LogicalResult WhileLowering::matchAndRewrite(WhileOp whileOp, PatternRewriter &rewriter) const { … } LogicalResult DoWhileLowering::matchAndRewrite(WhileOp whileOp, PatternRewriter &rewriter) const { … } LogicalResult IndexSwitchLowering::matchAndRewrite(IndexSwitchOp op, PatternRewriter &rewriter) const { … } LogicalResult ForallLowering::matchAndRewrite(ForallOp forallOp, PatternRewriter &rewriter) const { … } void mlir::populateSCFToControlFlowConversionPatterns( RewritePatternSet &patterns) { … } void SCFToControlFlowPass::runOnOperation() { … } std::unique_ptr<Pass> mlir::createConvertSCFToCFPass() { … }
Codebase Browser
llvm