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
27namespace mlir {
28#define GEN_PASS_DEF_SCFTOCONTROLFLOWPASS
29#include "mlir/Conversion/Passes.h.inc"
30} // namespace mlir
31
32using namespace mlir;
33using namespace mlir::scf;
34
35namespace {
36
37struct 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//
104struct 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//
197struct IfLowering : public OpRewritePattern<IfOp> {
198 using OpRewritePattern<IfOp>::OpRewritePattern;
199
200 LogicalResult matchAndRewrite(IfOp ifOp,
201 PatternRewriter &rewriter) const override;
202};
203
204struct ExecuteRegionLowering : public OpRewritePattern<ExecuteRegionOp> {
205 using OpRewritePattern<ExecuteRegionOp>::OpRewritePattern;
206
207 LogicalResult matchAndRewrite(ExecuteRegionOp op,
208 PatternRewriter &rewriter) const override;
209};
210
211struct 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.
277struct 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.
288struct 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.
296struct 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.
307struct 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
316static 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
330LogicalResult 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
409LogicalResult 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
465LogicalResult
466ExecuteRegionLowering::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 &region = op.getRegion();
475 rewriter.setInsertionPointToEnd(condBlock);
476 cf::BranchOp::create(builder&: rewriter, location: loc, dest: &region.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
499LogicalResult
500ParallelLowering::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
585LogicalResult 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
628LogicalResult
629DoWhileLowering::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
674LogicalResult
675IndexSwitchLowering::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 &region) -> FailureOr<Block *> {
690 Block *block = &region.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
735LogicalResult ForallLowering::matchAndRewrite(ForallOp forallOp,
736 PatternRewriter &rewriter) const {
737 return scf::forallToParallelLoop(rewriter, forallOp);
738}
739
740void 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
748void 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