| 1 | //===- SCFToControlFlow.cpp - SCF to CF conversion ------------------------===// |
| 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-exception |
| 6 | // |
| 7 | //===----------------------------------------------------------------------===// |
| 8 | // |
| 9 | // This file implements a pass to convert scf.for, scf.if and loop.terminator |
| 10 | // ops into standard CFG ops. |
| 11 | // |
| 12 | //===----------------------------------------------------------------------===// |
| 13 | |
| 14 | #include "mlir/Conversion/SCFToControlFlow/SCFToControlFlow.h" |
| 15 | |
| 16 | #include "mlir/Conversion/SCFToControlFlow/SCFToControlFlowDialectInterface.h" |
| 17 | #include "mlir/Dialect/Arith/IR/Arith.h" |
| 18 | #include "mlir/Dialect/ControlFlow/IR/ControlFlowOps.h" |
| 19 | #include "mlir/Dialect/SCF/IR/SCF.h" |
| 20 | #include "mlir/Dialect/SCF/Transforms/Transforms.h" |
| 21 | #include "mlir/IR/Builders.h" |
| 22 | #include "mlir/IR/MLIRContext.h" |
| 23 | #include "mlir/IR/PatternMatch.h" |
| 24 | #include "mlir/Transforms/DialectConversion.h" |
| 25 | #include "mlir/Transforms/Passes.h" |
| 26 | |
| 27 | namespace mlir { |
| 28 | #define GEN_PASS_DEF_SCFTOCONTROLFLOWPASS |
| 29 | #include "mlir/Conversion/Passes.h.inc" |
| 30 | } // namespace mlir |
| 31 | |
| 32 | using namespace mlir; |
| 33 | using namespace mlir::scf; |
| 34 | |
| 35 | namespace { |
| 36 | |
| 37 | struct SCFToControlFlowPass |
| 38 | : public impl::SCFToControlFlowPassBase<SCFToControlFlowPass> { |
| 39 | using Base::Base; |
| 40 | void runOnOperation() override; |
| 41 | }; |
| 42 | |
| 43 | // Create a CFG subgraph for the loop around its body blocks (if the body |
| 44 | // contained other loops, they have been already lowered to a flow of blocks). |
| 45 | // Maintain the invariants that a CFG subgraph created for any loop has a single |
| 46 | // entry and a single exit, and that the entry/exit blocks are respectively |
| 47 | // first/last blocks in the parent region. The original loop operation is |
| 48 | // replaced by the initialization operations that set up the initial value of |
| 49 | // the loop induction variable (%iv) and computes the loop bounds that are loop- |
| 50 | // invariant for affine loops. The operations following the original scf.for |
| 51 | // are split out into a separate continuation (exit) block. A condition block is |
| 52 | // created before the continuation block. It checks the exit condition of the |
| 53 | // loop and branches either to the continuation block, or to the first block of |
| 54 | // the body. The condition block takes as arguments the values of the induction |
| 55 | // variable followed by loop-carried values. Since it dominates both the body |
| 56 | // blocks and the continuation block, loop-carried values are visible in all of |
| 57 | // those blocks. Induction variable modification is appended to the last block |
| 58 | // of the body (which is the exit block from the body subgraph thanks to the |
| 59 | // invariant we maintain) along with a branch that loops back to the condition |
| 60 | // block. Loop-carried values are the loop terminator operands, which are |
| 61 | // forwarded to the branch. |
| 62 | // |
| 63 | // +---------------------------------+ |
| 64 | // | <code before the ForOp> | |
| 65 | // | <definitions of %init...> | |
| 66 | // | <compute initial %iv value> | |
| 67 | // | cf.br cond(%iv, %init...) | |
| 68 | // +---------------------------------+ |
| 69 | // | |
| 70 | // -------| | |
| 71 | // | v v |
| 72 | // | +--------------------------------+ |
| 73 | // | | cond(%iv, %init...): | |
| 74 | // | | <compare %iv to upper bound> | |
| 75 | // | | cf.cond_br %r, body, end | |
| 76 | // | +--------------------------------+ |
| 77 | // | | | |
| 78 | // | | -------------| |
| 79 | // | v | |
| 80 | // | +--------------------------------+ | |
| 81 | // | | body-first: | | |
| 82 | // | | <%init visible by dominance> | | |
| 83 | // | | <body contents> | | |
| 84 | // | +--------------------------------+ | |
| 85 | // | | | |
| 86 | // | ... | |
| 87 | // | | | |
| 88 | // | +--------------------------------+ | |
| 89 | // | | body-last: | | |
| 90 | // | | <body contents> | | |
| 91 | // | | <operands of yield = %yields>| | |
| 92 | // | | %new_iv =<add step to %iv> | | |
| 93 | // | | cf.br cond(%new_iv, %yields) | | |
| 94 | // | +--------------------------------+ | |
| 95 | // | | | |
| 96 | // |----------- |-------------------- |
| 97 | // v |
| 98 | // +--------------------------------+ |
| 99 | // | end: | |
| 100 | // | <code after the ForOp> | |
| 101 | // | <%init visible by dominance> | |
| 102 | // +--------------------------------+ |
| 103 | // |
| 104 | struct ForLowering : public OpRewritePattern<ForOp> { |
| 105 | using OpRewritePattern<ForOp>::OpRewritePattern; |
| 106 | |
| 107 | LogicalResult matchAndRewrite(ForOp forOp, |
| 108 | PatternRewriter &rewriter) const override; |
| 109 | }; |
| 110 | |
| 111 | // Create a CFG subgraph for the scf.if operation (including its "then" and |
| 112 | // optional "else" operation blocks). We maintain the invariants that the |
| 113 | // subgraph has a single entry and a single exit point, and that the entry/exit |
| 114 | // blocks are respectively the first/last block of the enclosing region. The |
| 115 | // operations following the scf.if are split into a continuation (subgraph |
| 116 | // exit) block. The condition is lowered to a chain of blocks that implement the |
| 117 | // short-circuit scheme. The "scf.if" operation is replaced with a conditional |
| 118 | // branch to either the first block of the "then" region, or to the first block |
| 119 | // of the "else" region. In these blocks, "scf.yield" is unconditional branches |
| 120 | // to the post-dominating block. When the "scf.if" does not return values, the |
| 121 | // post-dominating block is the same as the continuation block. When it returns |
| 122 | // values, the post-dominating block is a new block with arguments that |
| 123 | // correspond to the values returned by the "scf.if" that unconditionally |
| 124 | // branches to the continuation block. This allows block arguments to dominate |
| 125 | // any uses of the hitherto "scf.if" results that they replaced. (Inserting a |
| 126 | // new block allows us to avoid modifying the argument list of an existing |
| 127 | // block, which is illegal in a conversion pattern). When the "else" region is |
| 128 | // empty, which is only allowed for "scf.if"s that don't return values, the |
| 129 | // condition branches directly to the continuation block. |
| 130 | // |
| 131 | // CFG for a scf.if with else and without results. |
| 132 | // |
| 133 | // +--------------------------------+ |
| 134 | // | <code before the IfOp> | |
| 135 | // | cf.cond_br %cond, %then, %else | |
| 136 | // +--------------------------------+ |
| 137 | // | | |
| 138 | // | --------------| |
| 139 | // v | |
| 140 | // +--------------------------------+ | |
| 141 | // | then: | | |
| 142 | // | <then contents> | | |
| 143 | // | cf.br continue | | |
| 144 | // +--------------------------------+ | |
| 145 | // | | |
| 146 | // |---------- |------------- |
| 147 | // | V |
| 148 | // | +--------------------------------+ |
| 149 | // | | else: | |
| 150 | // | | <else contents> | |
| 151 | // | | cf.br continue | |
| 152 | // | +--------------------------------+ |
| 153 | // | | |
| 154 | // ------| | |
| 155 | // v v |
| 156 | // +--------------------------------+ |
| 157 | // | continue: | |
| 158 | // | <code after the IfOp> | |
| 159 | // +--------------------------------+ |
| 160 | // |
| 161 | // CFG for a scf.if with results. |
| 162 | // |
| 163 | // +--------------------------------+ |
| 164 | // | <code before the IfOp> | |
| 165 | // | cf.cond_br %cond, %then, %else | |
| 166 | // +--------------------------------+ |
| 167 | // | | |
| 168 | // | --------------| |
| 169 | // v | |
| 170 | // +--------------------------------+ | |
| 171 | // | then: | | |
| 172 | // | <then contents> | | |
| 173 | // | cf.br dom(%args...) | | |
| 174 | // +--------------------------------+ | |
| 175 | // | | |
| 176 | // |---------- |------------- |
| 177 | // | V |
| 178 | // | +--------------------------------+ |
| 179 | // | | else: | |
| 180 | // | | <else contents> | |
| 181 | // | | cf.br dom(%args...) | |
| 182 | // | +--------------------------------+ |
| 183 | // | | |
| 184 | // ------| | |
| 185 | // v v |
| 186 | // +--------------------------------+ |
| 187 | // | dom(%args...): | |
| 188 | // | cf.br continue | |
| 189 | // +--------------------------------+ |
| 190 | // | |
| 191 | // v |
| 192 | // +--------------------------------+ |
| 193 | // | continue: | |
| 194 | // | <code after the IfOp> | |
| 195 | // +--------------------------------+ |
| 196 | // |
| 197 | struct IfLowering : public OpRewritePattern<IfOp> { |
| 198 | using OpRewritePattern<IfOp>::OpRewritePattern; |
| 199 | |
| 200 | LogicalResult matchAndRewrite(IfOp ifOp, |
| 201 | PatternRewriter &rewriter) const override; |
| 202 | }; |
| 203 | |
| 204 | struct ExecuteRegionLowering : public OpRewritePattern<ExecuteRegionOp> { |
| 205 | using OpRewritePattern<ExecuteRegionOp>::OpRewritePattern; |
| 206 | |
| 207 | LogicalResult matchAndRewrite(ExecuteRegionOp op, |
| 208 | PatternRewriter &rewriter) const override; |
| 209 | }; |
| 210 | |
| 211 | struct ParallelLowering : public OpRewritePattern<mlir::scf::ParallelOp> { |
| 212 | using OpRewritePattern<mlir::scf::ParallelOp>::OpRewritePattern; |
| 213 | |
| 214 | LogicalResult matchAndRewrite(mlir::scf::ParallelOp parallelOp, |
| 215 | PatternRewriter &rewriter) const override; |
| 216 | }; |
| 217 | |
| 218 | /// Create a CFG subgraph for this loop construct. The regions of the loop need |
| 219 | /// not be a single block anymore (for example, if other SCF constructs that |
| 220 | /// they contain have been already converted to CFG), but need to be single-exit |
| 221 | /// from the last block of each region. The operations following the original |
| 222 | /// WhileOp are split into a new continuation block. Both regions of the WhileOp |
| 223 | /// are inlined, and their terminators are rewritten to organize the control |
| 224 | /// flow implementing the loop as follows. |
| 225 | /// |
| 226 | /// +---------------------------------+ |
| 227 | /// | <code before the WhileOp> | |
| 228 | /// | cf.br ^before(%operands...) | |
| 229 | /// +---------------------------------+ |
| 230 | /// | |
| 231 | /// -------| | |
| 232 | /// | v v |
| 233 | /// | +--------------------------------+ |
| 234 | /// | | ^before(%bargs...): | |
| 235 | /// | | %vals... = <some payload> | |
| 236 | /// | +--------------------------------+ |
| 237 | /// | | |
| 238 | /// | ... |
| 239 | /// | | |
| 240 | /// | +--------------------------------+ |
| 241 | /// | | ^before-last: |
| 242 | /// | | %cond = <compute condition> | |
| 243 | /// | | cf.cond_br %cond, | |
| 244 | /// | | ^after(%vals...), ^cont | |
| 245 | /// | +--------------------------------+ |
| 246 | /// | | | |
| 247 | /// | | -------------| |
| 248 | /// | v | |
| 249 | /// | +--------------------------------+ | |
| 250 | /// | | ^after(%aargs...): | | |
| 251 | /// | | <body contents> | | |
| 252 | /// | +--------------------------------+ | |
| 253 | /// | | | |
| 254 | /// | ... | |
| 255 | /// | | | |
| 256 | /// | +--------------------------------+ | |
| 257 | /// | | ^after-last: | | |
| 258 | /// | | %yields... = <some payload> | | |
| 259 | /// | | cf.br ^before(%yields...) | | |
| 260 | /// | +--------------------------------+ | |
| 261 | /// | | | |
| 262 | /// |----------- |-------------------- |
| 263 | /// v |
| 264 | /// +--------------------------------+ |
| 265 | /// | ^cont: | |
| 266 | /// | <code after the WhileOp> | |
| 267 | /// | <%vals from 'before' region | |
| 268 | /// | visible by dominance> | |
| 269 | /// +--------------------------------+ |
| 270 | /// |
| 271 | /// Values are communicated between ex-regions (the groups of blocks that used |
| 272 | /// to form a region before inlining) through block arguments of their |
| 273 | /// entry blocks, which are visible in all other dominated blocks. Similarly, |
| 274 | /// the results of the WhileOp are defined in the 'before' region, which is |
| 275 | /// required to have a single existing block, and are therefore accessible in |
| 276 | /// the continuation block due to dominance. |
| 277 | struct WhileLowering : public OpRewritePattern<WhileOp> { |
| 278 | using OpRewritePattern<WhileOp>::OpRewritePattern; |
| 279 | |
| 280 | LogicalResult matchAndRewrite(WhileOp whileOp, |
| 281 | PatternRewriter &rewriter) const override; |
| 282 | }; |
| 283 | |
| 284 | /// Optimized version of the above for the case of the "after" region merely |
| 285 | /// forwarding its arguments back to the "before" region (i.e., a "do-while" |
| 286 | /// loop). This avoid inlining the "after" region completely and branches back |
| 287 | /// to the "before" entry instead. |
| 288 | struct DoWhileLowering : public OpRewritePattern<WhileOp> { |
| 289 | using OpRewritePattern<WhileOp>::OpRewritePattern; |
| 290 | |
| 291 | LogicalResult matchAndRewrite(WhileOp whileOp, |
| 292 | PatternRewriter &rewriter) const override; |
| 293 | }; |
| 294 | |
| 295 | /// Lower an `scf.index_switch` operation to a `cf.switch` operation. |
| 296 | struct IndexSwitchLowering : public OpRewritePattern<IndexSwitchOp> { |
| 297 | using Base::Base; |
| 298 | |
| 299 | LogicalResult matchAndRewrite(IndexSwitchOp op, |
| 300 | PatternRewriter &rewriter) const override; |
| 301 | }; |
| 302 | |
| 303 | /// Lower an `scf.forall` operation to an `scf.parallel` op, assuming that it |
| 304 | /// has no shared outputs. Ops with shared outputs should be bufferized first. |
| 305 | /// Specialized lowerings for `scf.forall` (e.g., for GPUs) exist in other |
| 306 | /// dialects/passes. |
| 307 | struct ForallLowering : public OpRewritePattern<mlir::scf::ForallOp> { |
| 308 | using OpRewritePattern<mlir::scf::ForallOp>::OpRewritePattern; |
| 309 | |
| 310 | LogicalResult matchAndRewrite(mlir::scf::ForallOp forallOp, |
| 311 | PatternRewriter &rewriter) const override; |
| 312 | }; |
| 313 | |
| 314 | } // namespace |
| 315 | |
| 316 | static void propagateLoopAttrs(Operation *from, Operation *to) { |
| 317 | SmallVector<NamedAttribute> loopAttrs; |
| 318 | llvm::copy_if( |
| 319 | Range: from->getDiscardableAttrs(), Out: std::back_inserter(x&: loopAttrs), |
| 320 | P: [](NamedAttribute attr) { |
| 321 | auto *interface = |
| 322 | attr.getValue() |
| 323 | .getDialect() |
| 324 | .getRegisteredInterface<SCFToControlFlowDialectInterface>(); |
| 325 | return interface && interface->shouldPropagateLoopAttribute(attr); |
| 326 | }); |
| 327 | to->setDiscardableAttrs(loopAttrs); |
| 328 | } |
| 329 | |
| 330 | LogicalResult ForLowering::matchAndRewrite(ForOp forOp, |
| 331 | PatternRewriter &rewriter) const { |
| 332 | Location loc = forOp.getLoc(); |
| 333 | |
| 334 | // Start by splitting the block containing the 'scf.for' into two parts. |
| 335 | // The part before will get the init code, the part after will be the end |
| 336 | // point. |
| 337 | auto *initBlock = rewriter.getInsertionBlock(); |
| 338 | auto initPosition = rewriter.getInsertionPoint(); |
| 339 | auto *endBlock = rewriter.splitBlock(block: initBlock, before: initPosition); |
| 340 | |
| 341 | // Use the first block of the loop body as the condition block since it is the |
| 342 | // block that has the induction variable and loop-carried values as arguments. |
| 343 | // Split out all operations from the first block into a new block. Move all |
| 344 | // body blocks from the loop body region to the region containing the loop. |
| 345 | auto *conditionBlock = &forOp.getRegion().front(); |
| 346 | auto *firstBodyBlock = |
| 347 | rewriter.splitBlock(block: conditionBlock, before: conditionBlock->begin()); |
| 348 | auto *lastBodyBlock = &forOp.getRegion().back(); |
| 349 | rewriter.inlineRegionBefore(region&: forOp.getRegion(), before: endBlock); |
| 350 | auto iv = conditionBlock->getArgument(i: 0); |
| 351 | |
| 352 | // Append the induction variable stepping logic to the last body block and |
| 353 | // branch back to the condition block. Loop-carried values are taken from |
| 354 | // operands of the loop terminator. |
| 355 | Operation *terminator = lastBodyBlock->getTerminator(); |
| 356 | rewriter.setInsertionPointToEnd(lastBodyBlock); |
| 357 | auto step = forOp.getStep(); |
| 358 | // `scf.for` requires `LB + n*Step` to be representable in the induction |
| 359 | // variable type, so the increment cannot wrap in the signed (or, with |
| 360 | // `unsignedCmp`, unsigned) interpretation of the bounds. |
| 361 | arith::IntegerOverflowFlags overflowFlags = |
| 362 | forOp.getUnsignedCmp() ? arith::IntegerOverflowFlags::nuw |
| 363 | : arith::IntegerOverflowFlags::nsw; |
| 364 | auto stepped = |
| 365 | arith::AddIOp::create(builder&: rewriter, location: loc, lhs: iv, rhs: step, overflowFlags).getResult(); |
| 366 | if (!stepped) |
| 367 | return failure(); |
| 368 | |
| 369 | SmallVector<Value, 8> loopCarried; |
| 370 | loopCarried.push_back(Elt: stepped); |
| 371 | loopCarried.append(in_start: terminator->operand_begin(), in_end: terminator->operand_end()); |
| 372 | auto branchOp = |
| 373 | cf::BranchOp::create(builder&: rewriter, location: loc, dest: conditionBlock, destOperands: loopCarried); |
| 374 | |
| 375 | propagateLoopAttrs(from: forOp, to: branchOp); |
| 376 | rewriter.eraseOp(op: terminator); |
| 377 | |
| 378 | // Compute loop bounds before branching to the condition. |
| 379 | rewriter.setInsertionPointToEnd(initBlock); |
| 380 | Value lowerBound = forOp.getLowerBound(); |
| 381 | Value upperBound = forOp.getUpperBound(); |
| 382 | if (!lowerBound || !upperBound) |
| 383 | return failure(); |
| 384 | |
| 385 | // The initial values of loop-carried values is obtained from the operands |
| 386 | // of the loop operation. |
| 387 | SmallVector<Value, 8> destOperands; |
| 388 | destOperands.push_back(Elt: lowerBound); |
| 389 | llvm::append_range(C&: destOperands, R: forOp.getInitArgs()); |
| 390 | cf::BranchOp::create(builder&: rewriter, location: loc, dest: conditionBlock, destOperands); |
| 391 | |
| 392 | // With the body block done, we can fill in the condition block. |
| 393 | rewriter.setInsertionPointToEnd(conditionBlock); |
| 394 | arith::CmpIPredicate predicate = forOp.getUnsignedCmp() |
| 395 | ? arith::CmpIPredicate::ult |
| 396 | : arith::CmpIPredicate::slt; |
| 397 | auto comparison = |
| 398 | arith::CmpIOp::create(builder&: rewriter, location: loc, predicate, lhs: iv, rhs: upperBound); |
| 399 | |
| 400 | cf::CondBranchOp::create(builder&: rewriter, location: loc, condition: comparison, trueDest: firstBodyBlock, |
| 401 | trueOperands: ArrayRef<Value>(), falseDest: endBlock, falseOperands: ArrayRef<Value>()); |
| 402 | |
| 403 | // The result of the loop operation is the values of the condition block |
| 404 | // arguments except the induction variable on the last iteration. |
| 405 | rewriter.replaceOp(op: forOp, newValues: conditionBlock->getArguments().drop_front()); |
| 406 | return success(); |
| 407 | } |
| 408 | |
| 409 | LogicalResult IfLowering::matchAndRewrite(IfOp ifOp, |
| 410 | PatternRewriter &rewriter) const { |
| 411 | auto loc = ifOp.getLoc(); |
| 412 | |
| 413 | // Start by splitting the block containing the 'scf.if' into two parts. |
| 414 | // The part before will contain the condition, the part after will be the |
| 415 | // continuation point. |
| 416 | auto *condBlock = rewriter.getInsertionBlock(); |
| 417 | auto opPosition = rewriter.getInsertionPoint(); |
| 418 | auto *remainingOpsBlock = rewriter.splitBlock(block: condBlock, before: opPosition); |
| 419 | Block *continueBlock; |
| 420 | if (ifOp.getNumResults() == 0) { |
| 421 | continueBlock = remainingOpsBlock; |
| 422 | } else { |
| 423 | continueBlock = |
| 424 | rewriter.createBlock(insertBefore: remainingOpsBlock, argTypes: ifOp.getResultTypes(), |
| 425 | locs: SmallVector<Location>(ifOp.getNumResults(), loc)); |
| 426 | cf::BranchOp::create(builder&: rewriter, location: loc, dest: remainingOpsBlock); |
| 427 | } |
| 428 | |
| 429 | // Move blocks from the "then" region to the region containing 'scf.if', |
| 430 | // place it before the continuation block, and branch to it. |
| 431 | auto &thenRegion = ifOp.getThenRegion(); |
| 432 | auto *thenBlock = &thenRegion.front(); |
| 433 | Operation *thenTerminator = thenRegion.back().getTerminator(); |
| 434 | ValueRange thenTerminatorOperands = thenTerminator->getOperands(); |
| 435 | rewriter.setInsertionPointToEnd(&thenRegion.back()); |
| 436 | cf::BranchOp::create(builder&: rewriter, location: loc, dest: continueBlock, destOperands: thenTerminatorOperands); |
| 437 | rewriter.eraseOp(op: thenTerminator); |
| 438 | rewriter.inlineRegionBefore(region&: thenRegion, before: continueBlock); |
| 439 | |
| 440 | // Move blocks from the "else" region (if present) to the region containing |
| 441 | // 'scf.if', place it before the continuation block and branch to it. It |
| 442 | // will be placed after the "then" regions. |
| 443 | auto *elseBlock = continueBlock; |
| 444 | auto &elseRegion = ifOp.getElseRegion(); |
| 445 | if (!elseRegion.empty()) { |
| 446 | elseBlock = &elseRegion.front(); |
| 447 | Operation *elseTerminator = elseRegion.back().getTerminator(); |
| 448 | ValueRange elseTerminatorOperands = elseTerminator->getOperands(); |
| 449 | rewriter.setInsertionPointToEnd(&elseRegion.back()); |
| 450 | cf::BranchOp::create(builder&: rewriter, location: loc, dest: continueBlock, destOperands: elseTerminatorOperands); |
| 451 | rewriter.eraseOp(op: elseTerminator); |
| 452 | rewriter.inlineRegionBefore(region&: elseRegion, before: continueBlock); |
| 453 | } |
| 454 | |
| 455 | rewriter.setInsertionPointToEnd(condBlock); |
| 456 | cf::CondBranchOp::create(builder&: rewriter, location: loc, condition: ifOp.getCondition(), trueDest: thenBlock, |
| 457 | /*trueArgs=*/trueOperands: ArrayRef<Value>(), falseDest: elseBlock, |
| 458 | /*falseArgs=*/falseOperands: ArrayRef<Value>()); |
| 459 | |
| 460 | // Ok, we're done! |
| 461 | rewriter.replaceOp(op: ifOp, newValues: continueBlock->getArguments()); |
| 462 | return success(); |
| 463 | } |
| 464 | |
| 465 | LogicalResult |
| 466 | ExecuteRegionLowering::matchAndRewrite(ExecuteRegionOp op, |
| 467 | PatternRewriter &rewriter) const { |
| 468 | auto loc = op.getLoc(); |
| 469 | |
| 470 | auto *condBlock = rewriter.getInsertionBlock(); |
| 471 | auto opPosition = rewriter.getInsertionPoint(); |
| 472 | auto *remainingOpsBlock = rewriter.splitBlock(block: condBlock, before: opPosition); |
| 473 | |
| 474 | auto ®ion = op.getRegion(); |
| 475 | rewriter.setInsertionPointToEnd(condBlock); |
| 476 | cf::BranchOp::create(builder&: rewriter, location: loc, dest: ®ion.front()); |
| 477 | |
| 478 | for (Block &block : region) { |
| 479 | if (auto terminator = dyn_cast<scf::YieldOp>(Val: block.getTerminator())) { |
| 480 | ValueRange terminatorOperands = terminator->getOperands(); |
| 481 | rewriter.setInsertionPointToEnd(&block); |
| 482 | cf::BranchOp::create(builder&: rewriter, location: terminator.getLoc(), dest: remainingOpsBlock, |
| 483 | destOperands: terminatorOperands); |
| 484 | rewriter.eraseOp(op: terminator); |
| 485 | } |
| 486 | } |
| 487 | |
| 488 | rewriter.inlineRegionBefore(region, before: remainingOpsBlock); |
| 489 | |
| 490 | SmallVector<Value> vals; |
| 491 | SmallVector<Location> argLocs(op.getNumResults(), op->getLoc()); |
| 492 | for (auto arg : |
| 493 | remainingOpsBlock->addArguments(types: op->getResultTypes(), locs: argLocs)) |
| 494 | vals.push_back(Elt: arg); |
| 495 | rewriter.replaceOp(op, newValues: vals); |
| 496 | return success(); |
| 497 | } |
| 498 | |
| 499 | LogicalResult |
| 500 | ParallelLowering::matchAndRewrite(ParallelOp parallelOp, |
| 501 | PatternRewriter &rewriter) const { |
| 502 | Location loc = parallelOp.getLoc(); |
| 503 | auto reductionOp = dyn_cast<ReduceOp>(Val: parallelOp.getBody()->getTerminator()); |
| 504 | if (!reductionOp) { |
| 505 | return failure(); |
| 506 | } |
| 507 | |
| 508 | // For a parallel loop, we essentially need to create an n-dimensional loop |
| 509 | // nest. We do this by translating to scf.for ops and have those lowered in |
| 510 | // a further rewrite. If a parallel loop contains reductions (and thus returns |
| 511 | // values), forward the initial values for the reductions down the loop |
| 512 | // hierarchy and bubble up the results by modifying the "yield" terminator. |
| 513 | SmallVector<Value, 4> iterArgs = llvm::to_vector<4>(Range: parallelOp.getInitVals()); |
| 514 | SmallVector<Value, 4> ivs; |
| 515 | ivs.reserve(N: parallelOp.getNumLoops()); |
| 516 | bool first = true; |
| 517 | SmallVector<Value, 4> loopResults(iterArgs); |
| 518 | ForOp innermostForOp; |
| 519 | for (auto [iv, lower, upper, step] : |
| 520 | llvm::zip(t: parallelOp.getInductionVars(), u: parallelOp.getLowerBound(), |
| 521 | args: parallelOp.getUpperBound(), args: parallelOp.getStep())) { |
| 522 | ForOp forOp = |
| 523 | ForOp::create(builder&: rewriter, location: loc, lowerBound: lower, upperBound: upper, step, initArgs: iterArgs, |
| 524 | /*bodyBuilder=*/odsArg4: nullptr, unsignedCmp: parallelOp.getUnsignedCmp()); |
| 525 | innermostForOp = forOp; |
| 526 | ivs.push_back(Elt: forOp.getInductionVar()); |
| 527 | auto iterRange = forOp.getRegionIterArgs(); |
| 528 | iterArgs.assign(in_start: iterRange.begin(), in_end: iterRange.end()); |
| 529 | |
| 530 | if (first) { |
| 531 | // Store the results of the outermost loop that will be used to replace |
| 532 | // the results of the parallel loop when it is fully rewritten. |
| 533 | loopResults.assign(in_start: forOp.result_begin(), in_end: forOp.result_end()); |
| 534 | first = false; |
| 535 | } else if (!forOp.getResults().empty()) { |
| 536 | // A loop is constructed with an empty "yield" terminator if there are |
| 537 | // no results. |
| 538 | rewriter.setInsertionPointToEnd(rewriter.getInsertionBlock()); |
| 539 | scf::YieldOp::create(builder&: rewriter, location: loc, results: forOp.getResults()); |
| 540 | } |
| 541 | |
| 542 | rewriter.setInsertionPointToStart(forOp.getBody()); |
| 543 | } |
| 544 | |
| 545 | // Serializing into the for nest would drop loop annotations. The loop above |
| 546 | // emits one scf.for per dimension, so the attributes go to the innermost one, |
| 547 | // which runs the body. |
| 548 | if (innermostForOp) |
| 549 | propagateLoopAttrs(from: parallelOp, to: innermostForOp); |
| 550 | |
| 551 | // First, merge reduction blocks into the main region. |
| 552 | SmallVector<Value> yieldOperands; |
| 553 | yieldOperands.reserve(N: parallelOp.getNumResults()); |
| 554 | for (int64_t i = 0, e = parallelOp.getNumResults(); i < e; ++i) { |
| 555 | Block &reductionBody = reductionOp.getReductions()[i].front(); |
| 556 | Value arg = iterArgs[yieldOperands.size()]; |
| 557 | yieldOperands.push_back( |
| 558 | Elt: cast<ReduceReturnOp>(Val: reductionBody.getTerminator()).getResult()); |
| 559 | rewriter.eraseOp(op: reductionBody.getTerminator()); |
| 560 | rewriter.inlineBlockBefore(source: &reductionBody, op: reductionOp, |
| 561 | argValues: {arg, reductionOp.getOperands()[i]}); |
| 562 | } |
| 563 | rewriter.eraseOp(op: reductionOp); |
| 564 | |
| 565 | // Then merge the loop body without the terminator. |
| 566 | Block *newBody = rewriter.getInsertionBlock(); |
| 567 | if (newBody->empty()) |
| 568 | rewriter.mergeBlocks(source: parallelOp.getBody(), dest: newBody, argValues: ivs); |
| 569 | else |
| 570 | rewriter.inlineBlockBefore(source: parallelOp.getBody(), op: newBody->getTerminator(), |
| 571 | argValues: ivs); |
| 572 | |
| 573 | // Finally, create the terminator if required (for loops with no results, it |
| 574 | // has been already created in loop construction). |
| 575 | if (!yieldOperands.empty()) { |
| 576 | rewriter.setInsertionPointToEnd(rewriter.getInsertionBlock()); |
| 577 | scf::YieldOp::create(builder&: rewriter, location: loc, results: yieldOperands); |
| 578 | } |
| 579 | |
| 580 | rewriter.replaceOp(op: parallelOp, newValues: loopResults); |
| 581 | |
| 582 | return success(); |
| 583 | } |
| 584 | |
| 585 | LogicalResult WhileLowering::matchAndRewrite(WhileOp whileOp, |
| 586 | PatternRewriter &rewriter) const { |
| 587 | OpBuilder::InsertionGuard guard(rewriter); |
| 588 | Location loc = whileOp.getLoc(); |
| 589 | |
| 590 | // Split the current block before the WhileOp to create the inlining point. |
| 591 | Block *currentBlock = rewriter.getInsertionBlock(); |
| 592 | Block *continuation = |
| 593 | rewriter.splitBlock(block: currentBlock, before: rewriter.getInsertionPoint()); |
| 594 | |
| 595 | // Inline both regions. |
| 596 | Block *after = whileOp.getAfterBody(); |
| 597 | Block *before = whileOp.getBeforeBody(); |
| 598 | rewriter.inlineRegionBefore(region&: whileOp.getAfter(), before: continuation); |
| 599 | rewriter.inlineRegionBefore(region&: whileOp.getBefore(), before: after); |
| 600 | |
| 601 | // Branch to the "before" region. |
| 602 | rewriter.setInsertionPointToEnd(currentBlock); |
| 603 | cf::BranchOp::create(builder&: rewriter, location: loc, dest: before, destOperands: whileOp.getInits()); |
| 604 | |
| 605 | // Replace terminators with branches. Assuming bodies are SESE, which holds |
| 606 | // given only the patterns from this file, we only need to look at the last |
| 607 | // block. This should be reconsidered if we allow break/continue in SCF. |
| 608 | rewriter.setInsertionPointToEnd(before); |
| 609 | auto condOp = cast<ConditionOp>(Val: before->getTerminator()); |
| 610 | SmallVector<Value> args = llvm::to_vector(Range: condOp.getArgs()); |
| 611 | rewriter.replaceOpWithNewOp<cf::CondBranchOp>(op: condOp, args: condOp.getCondition(), |
| 612 | args&: after, args: condOp.getArgs(), |
| 613 | args&: continuation, args: ValueRange()); |
| 614 | |
| 615 | rewriter.setInsertionPointToEnd(after); |
| 616 | auto yieldOp = cast<scf::YieldOp>(Val: after->getTerminator()); |
| 617 | auto latch = rewriter.replaceOpWithNewOp<cf::BranchOp>(op: yieldOp, args&: before, |
| 618 | args: yieldOp.getResults()); |
| 619 | |
| 620 | propagateLoopAttrs(from: whileOp, to: latch); |
| 621 | // Replace the op with values "yielded" from the "before" region, which are |
| 622 | // visible by dominance. |
| 623 | rewriter.replaceOp(op: whileOp, newValues: args); |
| 624 | |
| 625 | return success(); |
| 626 | } |
| 627 | |
| 628 | LogicalResult |
| 629 | DoWhileLowering::matchAndRewrite(WhileOp whileOp, |
| 630 | PatternRewriter &rewriter) const { |
| 631 | Block &afterBlock = *whileOp.getAfterBody(); |
| 632 | if (!llvm::hasSingleElement(C&: afterBlock)) |
| 633 | return rewriter.notifyMatchFailure(arg&: whileOp, |
| 634 | msg: "do-while simplification applicable " |
| 635 | "only if 'after' region has no payload" ); |
| 636 | |
| 637 | auto yield = dyn_cast<scf::YieldOp>(Val: &afterBlock.front()); |
| 638 | if (!yield || yield.getResults() != afterBlock.getArguments()) |
| 639 | return rewriter.notifyMatchFailure(arg&: whileOp, |
| 640 | msg: "do-while simplification applicable " |
| 641 | "only to forwarding 'after' regions" ); |
| 642 | |
| 643 | // Split the current block before the WhileOp to create the inlining point. |
| 644 | OpBuilder::InsertionGuard guard(rewriter); |
| 645 | Block *currentBlock = rewriter.getInsertionBlock(); |
| 646 | Block *continuation = |
| 647 | rewriter.splitBlock(block: currentBlock, before: rewriter.getInsertionPoint()); |
| 648 | |
| 649 | // Only the "before" region should be inlined. |
| 650 | Block *before = whileOp.getBeforeBody(); |
| 651 | rewriter.inlineRegionBefore(region&: whileOp.getBefore(), before: continuation); |
| 652 | |
| 653 | // Branch to the "before" region. |
| 654 | rewriter.setInsertionPointToEnd(currentBlock); |
| 655 | cf::BranchOp::create(builder&: rewriter, location: whileOp.getLoc(), dest: before, destOperands: whileOp.getInits()); |
| 656 | |
| 657 | // Loop around the "before" region based on condition. |
| 658 | rewriter.setInsertionPointToEnd(before); |
| 659 | auto condOp = cast<ConditionOp>(Val: before->getTerminator()); |
| 660 | auto latch = cf::CondBranchOp::create( |
| 661 | builder&: rewriter, location: condOp.getLoc(), condition: condOp.getCondition(), trueDest: before, |
| 662 | trueOperands: condOp.getArgs(), falseDest: continuation, falseOperands: ValueRange()); |
| 663 | |
| 664 | propagateLoopAttrs(from: whileOp, to: latch); |
| 665 | // Replace the op with values "yielded" from the "before" region, which are |
| 666 | // visible by dominance. |
| 667 | rewriter.replaceOp(op: whileOp, newValues: condOp.getArgs()); |
| 668 | |
| 669 | // Erase the condition op. |
| 670 | rewriter.eraseOp(op: condOp); |
| 671 | return success(); |
| 672 | } |
| 673 | |
| 674 | LogicalResult |
| 675 | IndexSwitchLowering::matchAndRewrite(IndexSwitchOp op, |
| 676 | PatternRewriter &rewriter) const { |
| 677 | // Split the block at the op. |
| 678 | Block *condBlock = rewriter.getInsertionBlock(); |
| 679 | Block *continueBlock = rewriter.splitBlock(block: condBlock, before: Block::iterator(op)); |
| 680 | |
| 681 | // Create the arguments on the continue block with which to replace the |
| 682 | // results of the op. |
| 683 | SmallVector<Value> results; |
| 684 | results.reserve(N: op.getNumResults()); |
| 685 | for (Type resultType : op.getResultTypes()) |
| 686 | results.push_back(Elt: continueBlock->addArgument(type: resultType, loc: op.getLoc())); |
| 687 | |
| 688 | // Handle the regions. |
| 689 | auto convertRegion = [&](Region ®ion) -> FailureOr<Block *> { |
| 690 | Block *block = ®ion.front(); |
| 691 | |
| 692 | // Convert the yield terminator to a branch to the continue block. |
| 693 | auto yield = cast<scf::YieldOp>(Val: block->getTerminator()); |
| 694 | rewriter.setInsertionPoint(yield); |
| 695 | rewriter.replaceOpWithNewOp<cf::BranchOp>(op: yield, args&: continueBlock, |
| 696 | args: yield.getOperands()); |
| 697 | |
| 698 | // Inline the region. |
| 699 | rewriter.inlineRegionBefore(region, before: continueBlock); |
| 700 | return block; |
| 701 | }; |
| 702 | |
| 703 | // Convert the case regions. |
| 704 | SmallVector<Block *> caseSuccessors; |
| 705 | SmallVector<APInt> caseValues; |
| 706 | caseSuccessors.reserve(N: op.getCases().size()); |
| 707 | caseValues.reserve(N: op.getCases().size()); |
| 708 | for (auto [region, value] : llvm::zip(t: op.getCaseRegions(), u: op.getCases())) { |
| 709 | FailureOr<Block *> block = convertRegion(region); |
| 710 | if (failed(Result: block)) |
| 711 | return failure(); |
| 712 | caseSuccessors.push_back(Elt: *block); |
| 713 | caseValues.push_back(Elt: APInt(64, value)); |
| 714 | } |
| 715 | |
| 716 | // Convert the default region. |
| 717 | FailureOr<Block *> defaultBlock = convertRegion(op.getDefaultRegion()); |
| 718 | if (failed(Result: defaultBlock)) |
| 719 | return failure(); |
| 720 | |
| 721 | // Create the switch. |
| 722 | rewriter.setInsertionPointToEnd(condBlock); |
| 723 | SmallVector<ValueRange> caseOperands(caseSuccessors.size(), {}); |
| 724 | |
| 725 | // Cast switch index to i64 to avoid truncation for large case values. |
| 726 | Value caseValue = arith::IndexCastOp::create( |
| 727 | builder&: rewriter, location: op.getLoc(), out: rewriter.getI64Type(), in: op.getArg()); |
| 728 | |
| 729 | cf::SwitchOp::create(builder&: rewriter, location: op.getLoc(), flag: caseValue, defaultDestination: *defaultBlock, |
| 730 | defaultOperands: ValueRange(), caseValues, caseDestinations: caseSuccessors, caseOperands); |
| 731 | rewriter.replaceOp(op, newValues: continueBlock->getArguments()); |
| 732 | return success(); |
| 733 | } |
| 734 | |
| 735 | LogicalResult ForallLowering::matchAndRewrite(ForallOp forallOp, |
| 736 | PatternRewriter &rewriter) const { |
| 737 | return scf::forallToParallelLoop(rewriter, forallOp); |
| 738 | } |
| 739 | |
| 740 | void mlir::populateSCFToControlFlowConversionPatterns( |
| 741 | RewritePatternSet &patterns) { |
| 742 | patterns.add<ForallLowering, ForLowering, IfLowering, ParallelLowering, |
| 743 | WhileLowering, ExecuteRegionLowering, IndexSwitchLowering>( |
| 744 | arg: patterns.getContext()); |
| 745 | patterns.add<DoWhileLowering>(arg: patterns.getContext(), /*benefit=*/args: 2); |
| 746 | } |
| 747 | |
| 748 | void SCFToControlFlowPass::runOnOperation() { |
| 749 | RewritePatternSet patterns(&getContext()); |
| 750 | populateSCFToControlFlowConversionPatterns(patterns); |
| 751 | |
| 752 | // Configure conversion to lower out SCF operations. |
| 753 | ConversionTarget target(getContext()); |
| 754 | target.addIllegalOp<scf::ForallOp, scf::ForOp, scf::IfOp, scf::IndexSwitchOp, |
| 755 | scf::ParallelOp, scf::WhileOp, scf::ExecuteRegionOp>(); |
| 756 | target.markUnknownOpDynamicallyLegal(fn: [](Operation *) { return true; }); |
| 757 | ConversionConfig config; |
| 758 | config.allowPatternRollback = allowPatternRollback; |
| 759 | if (failed(Result: applyPartialConversion(op: getOperation(), target, patterns: std::move(patterns), |
| 760 | config))) |
| 761 | signalPassFailure(); |
| 762 | } |
| 763 | |