1//===- ControlFlowOps.cpp - ControlFlow Operations ------------------------===//
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#include "mlir/Dialect/ControlFlow/IR/ControlFlowOps.h"
10
11#include "mlir/Conversion/ConvertToLLVM/ToLLVMInterface.h"
12#include "mlir/Dialect/Arith/IR/Arith.h"
13#include "mlir/Dialect/Bufferization/IR/BufferDeallocationOpInterface.h"
14#include "mlir/Dialect/Bufferization/IR/BufferizableOpInterface.h"
15#include "mlir/Dialect/UB/IR/UBOps.h"
16#include "mlir/IR/AffineExpr.h"
17#include "mlir/IR/AffineMap.h"
18#include "mlir/IR/Builders.h"
19#include "mlir/IR/BuiltinTypes.h"
20#include "mlir/IR/IRMapping.h"
21#include "mlir/IR/Matchers.h"
22#include "mlir/IR/OpImplementation.h"
23#include "mlir/IR/PatternMatch.h"
24#include "mlir/IR/TypeUtilities.h"
25#include "mlir/IR/Value.h"
26#include "mlir/Transforms/InliningUtils.h"
27#include "llvm/ADT/STLExtras.h"
28#include <numeric>
29
30#include "mlir/Dialect/ControlFlow/IR/ControlFlowOpsDialect.cpp.inc"
31
32using namespace mlir;
33using namespace mlir::cf;
34
35//===----------------------------------------------------------------------===//
36// ControlFlowDialect Interfaces
37//===----------------------------------------------------------------------===//
38namespace {
39/// This class defines the interface for handling inlining with control flow
40/// operations.
41struct ControlFlowInlinerInterface : public DialectInlinerInterface {
42 using DialectInlinerInterface::DialectInlinerInterface;
43 ~ControlFlowInlinerInterface() override = default;
44
45 /// All control flow operations can be inlined.
46 bool isLegalToInline(Operation *call, Operation *callable,
47 bool wouldBeCloned) const final {
48 return true;
49 }
50 bool isLegalToInline(Operation *, Region *, bool, IRMapping &) const final {
51 return true;
52 }
53
54 /// ControlFlow terminator operations don't really need any special handing.
55 void handleTerminator(Operation *op, Block *newDest) const final {}
56};
57} // namespace
58
59//===----------------------------------------------------------------------===//
60// ControlFlowDialect
61//===----------------------------------------------------------------------===//
62
63void ControlFlowDialect::initialize() {
64 addOperations<
65#define GET_OP_LIST
66#include "mlir/Dialect/ControlFlow/IR/ControlFlowOps.cpp.inc"
67 >();
68 addInterfaces<ControlFlowInlinerInterface>();
69 declarePromisedInterface<ConvertToLLVMPatternInterface, ControlFlowDialect>();
70 declarePromisedInterfaces<bufferization::BufferizableOpInterface, BranchOp,
71 CondBranchOp>();
72 declarePromisedInterface<bufferization::BufferDeallocationOpInterface,
73 CondBranchOp>();
74}
75
76//===----------------------------------------------------------------------===//
77// AssertOp
78//===----------------------------------------------------------------------===//
79
80LogicalResult AssertOp::canonicalize(AssertOp op, PatternRewriter &rewriter) {
81 // Erase assertion if argument is constant true.
82 if (matchPattern(value: op.getArg(), pattern: m_One())) {
83 rewriter.eraseOp(op);
84 return success();
85 }
86 return failure();
87}
88
89// This side effect models "program termination".
90void AssertOp::getEffects(
91 SmallVectorImpl<SideEffects::EffectInstance<MemoryEffects::Effect>>
92 &effects) {
93 effects.emplace_back(Args: MemoryEffects::Write::get());
94}
95
96//===----------------------------------------------------------------------===//
97// BranchOp
98//===----------------------------------------------------------------------===//
99
100/// Given a successor, try to collapse it to a new destination if it only
101/// contains a passthrough unconditional branch. If the successor is
102/// collapsable, `successor` and `successorOperands` are updated to reference
103/// the new destination and values. `argStorage` is used as storage if operands
104/// to the collapsed successor need to be remapped. It must outlive uses of
105/// successorOperands.
106static LogicalResult collapseBranch(Block *&successor,
107 ValueRange &successorOperands,
108 SmallVectorImpl<Value> &argStorage) {
109 // Check that the successor only contains a unconditional branch.
110 if (std::next(x: successor->begin()) != successor->end())
111 return failure();
112 // Check that the terminator is an unconditional branch.
113 BranchOp successorBranch = dyn_cast<BranchOp>(Val: successor->getTerminator());
114 if (!successorBranch)
115 return failure();
116 // Check that the arguments are only used within the terminator.
117 for (BlockArgument arg : successor->getArguments()) {
118 for (Operation *user : arg.getUsers())
119 if (user != successorBranch)
120 return failure();
121 }
122 // Don't try to collapse branches to infinite loops.
123 Block *successorDest = successorBranch.getDest();
124 if (successorDest == successor)
125 return failure();
126 // Don't try to collapse branches which participate in a cycle.
127 BranchOp nextBranch = dyn_cast<BranchOp>(Val: successorDest->getTerminator());
128 llvm::DenseSet<Block *> visited{successor, successorDest};
129 while (nextBranch) {
130 Block *nextBranchDest = nextBranch.getDest();
131 if (visited.contains(V: nextBranchDest))
132 return failure();
133 visited.insert(V: nextBranchDest);
134 nextBranch = dyn_cast<BranchOp>(Val: nextBranchDest->getTerminator());
135 }
136
137 // Update the operands to the successor. If the branch parent has no
138 // arguments, we can use the branch operands directly.
139 OperandRange operands = successorBranch.getOperands();
140 if (successor->args_empty()) {
141 successor = successorDest;
142 successorOperands = operands;
143 return success();
144 }
145
146 // Otherwise, we need to remap any argument operands.
147 for (Value operand : operands) {
148 BlockArgument argOperand = llvm::dyn_cast<BlockArgument>(Val&: operand);
149 if (argOperand && argOperand.getOwner() == successor)
150 argStorage.push_back(Elt: successorOperands[argOperand.getArgNumber()]);
151 else
152 argStorage.push_back(Elt: operand);
153 }
154 successor = successorDest;
155 successorOperands = argStorage;
156 return success();
157}
158
159/// Simplify a branch to a block that has a single predecessor. This effectively
160/// merges the two blocks.
161static LogicalResult
162simplifyBrToBlockWithSinglePred(BranchOp op, PatternRewriter &rewriter) {
163 // Check that the successor block has a single predecessor.
164 Block *succ = op.getDest();
165 Block *opParent = op->getBlock();
166 if (succ == opParent || !llvm::hasSingleElement(C: succ->getPredecessors()))
167 return failure();
168
169 // If any branch operand is itself a block argument of the successor, merging
170 // would call replaceAllUsesWith(arg, arg) — a no-op — leaving dangling uses
171 // of that argument after the successor block is erased.
172 for (Value operand : op.getOperands())
173 if (auto ba = dyn_cast<BlockArgument>(Val&: operand))
174 if (ba.getOwner() == succ)
175 return failure();
176
177 // Merge the successor into the current block and erase the branch.
178 SmallVector<Value> brOperands(op.getOperands());
179 rewriter.eraseOp(op);
180 rewriter.mergeBlocks(source: succ, dest: opParent, argValues: brOperands);
181 return success();
182}
183
184/// br ^bb1
185/// ^bb1
186/// br ^bbN(...)
187///
188/// -> br ^bbN(...)
189///
190static LogicalResult simplifyPassThroughBr(BranchOp op,
191 PatternRewriter &rewriter) {
192 Block *dest = op.getDest();
193 ValueRange destOperands = op.getOperands();
194 SmallVector<Value, 4> destOperandStorage;
195
196 // Try to collapse the successor if it points somewhere other than this
197 // block.
198 if (dest == op->getBlock() ||
199 failed(Result: collapseBranch(successor&: dest, successorOperands&: destOperands, argStorage&: destOperandStorage)))
200 return failure();
201
202 // Create a new branch with the collapsed successor.
203 rewriter.replaceOpWithNewOp<BranchOp>(op, args&: dest, args&: destOperands);
204 return success();
205}
206
207/// If all incoming values for a block argument from all predecessors are the
208/// same SSA value, replace uses of the block argument with that value. This
209/// allows the block argument to be removed by dead code elimination.
210///
211/// %c = arith.constant 0 : i32
212/// cf.br ^bb1(%c : i32) // pred 1
213/// cf.br ^bb1(%c : i32) // pred 2
214/// ^bb1(%arg0: i32):
215/// use(%arg0)
216/// ->
217/// ^bb1(%arg0: i32):
218/// use(%c) // %arg0 has no uses and can be removed
219///
220static LogicalResult simplifyUniformBlockArgs(Block *dest,
221 PatternRewriter &rewriter) {
222 if (dest->hasNoPredecessors() ||
223 llvm::hasSingleElement(C: dest->getPredecessors()))
224 return failure();
225
226 bool changed = false;
227 for (BlockArgument arg : dest->getArguments()) {
228 if (arg.use_empty())
229 continue;
230
231 Value commonValue;
232 for (Block *pred : dest->getPredecessors()) {
233 auto branch = dyn_cast<BranchOpInterface>(Val: pred->getTerminator());
234 if (!branch) {
235 commonValue = Value();
236 break;
237 }
238
239 for (auto [i, succ] : llvm::enumerate(First: branch->getSuccessors())) {
240 if (succ != dest)
241 continue;
242
243 // Produced operands are modeled by BranchOpInterface as null Values.
244 Value val = branch.getSuccessorOperands(index: i)[arg.getArgNumber()];
245 if (commonValue && commonValue != val) {
246 commonValue = Value();
247 break;
248 }
249 commonValue = val;
250 }
251
252 if (!commonValue)
253 break;
254 }
255
256 if (commonValue && commonValue != arg) {
257 rewriter.replaceAllUsesWith(from: arg, to: commonValue);
258 changed = true;
259 }
260 }
261 return success(IsSuccess: changed);
262}
263
264namespace {
265/// Replaces block arguments with a uniform incoming value across all
266/// predecessors, for any op implementing BranchOpInterface.
267struct SimplifyUniformBlockArguments
268 : public OpInterfaceRewritePattern<BranchOpInterface> {
269 using Base::Base;
270 LogicalResult matchAndRewrite(BranchOpInterface op,
271 PatternRewriter &rewriter) const override {
272 bool changed = false;
273 for (Block *succ : op->getSuccessors())
274 changed |= succeeded(Result: simplifyUniformBlockArgs(dest: succ, rewriter));
275 return success(IsSuccess: changed);
276 }
277};
278} // namespace
279
280LogicalResult BranchOp::canonicalize(BranchOp op, PatternRewriter &rewriter) {
281 return success(IsSuccess: succeeded(Result: simplifyBrToBlockWithSinglePred(op, rewriter)) ||
282 succeeded(Result: simplifyPassThroughBr(op, rewriter)) ||
283 succeeded(Result: simplifyUniformBlockArgs(dest: op.getDest(), rewriter)));
284}
285
286void BranchOp::setDest(Block *block) { return setSuccessor(block); }
287
288void BranchOp::eraseOperand(unsigned index) { (*this)->eraseOperand(idx: index); }
289
290SuccessorOperands BranchOp::getSuccessorOperands(unsigned index) {
291 assert(index == 0 && "invalid successor index");
292 return SuccessorOperands(getDestOperandsMutable());
293}
294
295Block *BranchOp::getSuccessorForOperands(ArrayRef<Attribute>) {
296 return getDest();
297}
298
299//===----------------------------------------------------------------------===//
300// CondBranchOp
301//===----------------------------------------------------------------------===//
302
303namespace {
304/// cf.cond_br true, ^bb1, ^bb2
305/// -> br ^bb1
306/// cf.cond_br false, ^bb1, ^bb2
307/// -> br ^bb2
308///
309struct SimplifyConstCondBranchPred : public OpRewritePattern<CondBranchOp> {
310 using Base::Base;
311
312 LogicalResult matchAndRewrite(CondBranchOp condbr,
313 PatternRewriter &rewriter) const override {
314 if (matchPattern(value: condbr.getCondition(), pattern: m_NonZero())) {
315 // True branch taken.
316 rewriter.replaceOpWithNewOp<BranchOp>(op: condbr, args: condbr.getTrueDest(),
317 args: condbr.getTrueOperands());
318 return success();
319 }
320 if (matchPattern(value: condbr.getCondition(), pattern: m_Zero())) {
321 // False branch taken.
322 rewriter.replaceOpWithNewOp<BranchOp>(op: condbr, args: condbr.getFalseDest(),
323 args: condbr.getFalseOperands());
324 return success();
325 }
326 return failure();
327 }
328};
329
330/// cf.cond_br %cond, ^bb1, ^bb2
331/// ^bb1
332/// br ^bbN(...)
333/// ^bb2
334/// br ^bbK(...)
335///
336/// -> cf.cond_br %cond, ^bbN(...), ^bbK(...)
337///
338struct SimplifyPassThroughCondBranch : public OpRewritePattern<CondBranchOp> {
339 using OpRewritePattern<CondBranchOp>::OpRewritePattern;
340
341 LogicalResult matchAndRewrite(CondBranchOp condbr,
342 PatternRewriter &rewriter) const override {
343 Block *trueDest = condbr.getTrueDest(), *falseDest = condbr.getFalseDest();
344 ValueRange trueDestOperands = condbr.getTrueOperands();
345 ValueRange falseDestOperands = condbr.getFalseOperands();
346 SmallVector<Value, 4> trueDestOperandStorage, falseDestOperandStorage;
347
348 // Try to collapse one of the current successors.
349 LogicalResult collapsedTrue =
350 collapseBranch(successor&: trueDest, successorOperands&: trueDestOperands, argStorage&: trueDestOperandStorage);
351 LogicalResult collapsedFalse =
352 collapseBranch(successor&: falseDest, successorOperands&: falseDestOperands, argStorage&: falseDestOperandStorage);
353 if (failed(Result: collapsedTrue) && failed(Result: collapsedFalse))
354 return failure();
355
356 // Create a new branch with the collapsed successors.
357 rewriter.replaceOpWithNewOp<CondBranchOp>(
358 op: condbr, args: condbr.getCondition(), args&: trueDest, args&: trueDestOperands, args&: falseDest,
359 args&: falseDestOperands, args: condbr.getWeights());
360 return success();
361 }
362};
363
364/// cf.cond_br %cond, ^bb1(A, ..., N), ^bb1(A, ..., N)
365/// -> br ^bb1(A, ..., N)
366///
367/// cf.cond_br %cond, ^bb1(A), ^bb1(B)
368/// -> %select = arith.select %cond, A, B
369/// br ^bb1(%select)
370///
371struct SimplifyCondBranchIdenticalSuccessors
372 : public OpRewritePattern<CondBranchOp> {
373 using OpRewritePattern<CondBranchOp>::OpRewritePattern;
374
375 LogicalResult matchAndRewrite(CondBranchOp condbr,
376 PatternRewriter &rewriter) const override {
377 // Check that the true and false destinations are the same and have the same
378 // operands.
379 Block *trueDest = condbr.getTrueDest();
380 if (trueDest != condbr.getFalseDest())
381 return failure();
382
383 // If all of the operands match, no selects need to be generated.
384 OperandRange trueOperands = condbr.getTrueOperands();
385 OperandRange falseOperands = condbr.getFalseOperands();
386 if (trueOperands == falseOperands) {
387 rewriter.replaceOpWithNewOp<BranchOp>(op: condbr, args&: trueDest, args&: trueOperands);
388 return success();
389 }
390
391 // Otherwise, if the current block is the only predecessor insert selects
392 // for any mismatched branch operands.
393 if (trueDest->getUniquePredecessor() != condbr->getBlock())
394 return failure();
395
396 // Generate a select for any operands that differ between the two.
397 SmallVector<Value, 8> mergedOperands;
398 mergedOperands.reserve(N: trueOperands.size());
399 Value condition = condbr.getCondition();
400 for (auto it : llvm::zip(t&: trueOperands, u&: falseOperands)) {
401 if (std::get<0>(t&: it) == std::get<1>(t&: it))
402 mergedOperands.push_back(Elt: std::get<0>(t&: it));
403 else
404 mergedOperands.push_back(
405 Elt: arith::SelectOp::create(builder&: rewriter, location: condbr.getLoc(), condition,
406 true_value: std::get<0>(t&: it), false_value: std::get<1>(t&: it)));
407 }
408
409 rewriter.replaceOpWithNewOp<BranchOp>(op: condbr, args&: trueDest, args&: mergedOperands);
410 return success();
411 }
412};
413
414/// ...
415/// cf.cond_br %cond, ^bb1(...), ^bb2(...)
416/// ...
417/// ^bb1: // has single predecessor
418/// ...
419/// cf.cond_br %cond, ^bb3(...), ^bb4(...)
420///
421/// ->
422///
423/// ...
424/// cf.cond_br %cond, ^bb1(...), ^bb2(...)
425/// ...
426/// ^bb1: // has single predecessor
427/// ...
428/// br ^bb3(...)
429///
430struct SimplifyCondBranchFromCondBranchOnSameCondition
431 : public OpRewritePattern<CondBranchOp> {
432 using OpRewritePattern<CondBranchOp>::OpRewritePattern;
433
434 LogicalResult matchAndRewrite(CondBranchOp condbr,
435 PatternRewriter &rewriter) const override {
436 // Check that we have a single distinct predecessor.
437 Block *currentBlock = condbr->getBlock();
438 Block *predecessor = currentBlock->getSinglePredecessor();
439 if (!predecessor)
440 return failure();
441
442 // Check that the predecessor terminates with a conditional branch to this
443 // block and that it branches on the same condition.
444 auto predBranch = dyn_cast<CondBranchOp>(Val: predecessor->getTerminator());
445 if (!predBranch || condbr.getCondition() != predBranch.getCondition())
446 return failure();
447
448 // Fold this branch to an unconditional branch.
449 if (currentBlock == predBranch.getTrueDest())
450 rewriter.replaceOpWithNewOp<BranchOp>(op: condbr, args: condbr.getTrueDest(),
451 args: condbr.getTrueDestOperands());
452 else
453 rewriter.replaceOpWithNewOp<BranchOp>(op: condbr, args: condbr.getFalseDest(),
454 args: condbr.getFalseDestOperands());
455 return success();
456 }
457};
458
459/// cf.cond_br %arg0, ^trueB, ^falseB
460///
461/// ^trueB:
462/// "test.consumer1"(%arg0) : (i1) -> ()
463/// ...
464///
465/// ^falseB:
466/// "test.consumer2"(%arg0) : (i1) -> ()
467/// ...
468///
469/// ->
470///
471/// cf.cond_br %arg0, ^trueB, ^falseB
472/// ^trueB:
473/// "test.consumer1"(%true) : (i1) -> ()
474/// ...
475///
476/// ^falseB:
477/// "test.consumer2"(%false) : (i1) -> ()
478/// ...
479struct CondBranchTruthPropagation : public OpRewritePattern<CondBranchOp> {
480 using OpRewritePattern<CondBranchOp>::OpRewritePattern;
481
482 LogicalResult matchAndRewrite(CondBranchOp condbr,
483 PatternRewriter &rewriter) const override {
484 // Check that we have a single distinct predecessor.
485 bool replaced = false;
486 Type ty = rewriter.getI1Type();
487
488 // These variables serve to prevent creating duplicate constants
489 // and hold constant true or false values.
490 Value constantTrue = nullptr;
491 Value constantFalse = nullptr;
492
493 // TODO These checks can be expanded to encompas any use with only
494 // either the true of false edge as a predecessor. For now, we fall
495 // back to checking the single predecessor is given by the true/fasle
496 // destination, thereby ensuring that only that edge can reach the
497 // op.
498 if (condbr.getTrueDest()->getSinglePredecessor()) {
499 for (OpOperand &use :
500 llvm::make_early_inc_range(Range: condbr.getCondition().getUses())) {
501 if (use.getOwner()->getBlock() == condbr.getTrueDest()) {
502 replaced = true;
503
504 if (!constantTrue)
505 constantTrue = arith::ConstantOp::create(
506 builder&: rewriter, location: condbr.getLoc(), result: ty, value: rewriter.getBoolAttr(value: true));
507
508 rewriter.modifyOpInPlace(root: use.getOwner(),
509 callable: [&] { use.set(constantTrue); });
510 }
511 }
512 }
513 if (condbr.getFalseDest()->getSinglePredecessor()) {
514 for (OpOperand &use :
515 llvm::make_early_inc_range(Range: condbr.getCondition().getUses())) {
516 if (use.getOwner()->getBlock() == condbr.getFalseDest()) {
517 replaced = true;
518
519 if (!constantFalse)
520 constantFalse = arith::ConstantOp::create(
521 builder&: rewriter, location: condbr.getLoc(), result: ty, value: rewriter.getBoolAttr(value: false));
522
523 rewriter.modifyOpInPlace(root: use.getOwner(),
524 callable: [&] { use.set(constantFalse); });
525 }
526 }
527 }
528 return success(IsSuccess: replaced);
529 }
530};
531
532/// Returns true if `block` contains only `ub.unreachable`.
533static bool isUnreachableBlock(Block *block) {
534 return llvm::hasSingleElement(C&: *block) &&
535 isa<ub::UnreachableOp>(Val: block->getTerminator());
536}
537
538/// If the destination block of a conditional branch contains only
539/// ub.unreachable, unconditionally branch to the other destination.
540struct DropUnreachableCondBranch : public OpRewritePattern<CondBranchOp> {
541 using OpRewritePattern<CondBranchOp>::OpRewritePattern;
542
543 LogicalResult matchAndRewrite(CondBranchOp condbr,
544 PatternRewriter &rewriter) const override {
545 // If the "true" destination is unreachable, branch to the "false"
546 // destination.
547 Block *trueDest = condbr.getTrueDest();
548 Block *falseDest = condbr.getFalseDest();
549 if (isUnreachableBlock(block: trueDest)) {
550 rewriter.replaceOpWithNewOp<BranchOp>(op: condbr, args&: falseDest,
551 args: condbr.getFalseOperands());
552 return success();
553 }
554
555 // If the "false" destination is unreachable, branch to the "true"
556 // destination.
557 if (isUnreachableBlock(block: falseDest)) {
558 rewriter.replaceOpWithNewOp<BranchOp>(op: condbr, args&: trueDest,
559 args: condbr.getTrueOperands());
560 return success();
561 }
562
563 return failure();
564 }
565};
566} // namespace
567
568void CondBranchOp::getCanonicalizationPatterns(RewritePatternSet &results,
569 MLIRContext *context) {
570 results.add<SimplifyConstCondBranchPred, SimplifyPassThroughCondBranch,
571 SimplifyCondBranchIdenticalSuccessors,
572 SimplifyCondBranchFromCondBranchOnSameCondition,
573 CondBranchTruthPropagation, DropUnreachableCondBranch,
574 SimplifyUniformBlockArguments>(arg&: context);
575}
576
577SuccessorOperands CondBranchOp::getSuccessorOperands(unsigned index) {
578 assert(index < getNumSuccessors() && "invalid successor index");
579 return SuccessorOperands(index == trueIndex ? getTrueDestOperandsMutable()
580 : getFalseDestOperandsMutable());
581}
582
583Block *CondBranchOp::getSuccessorForOperands(ArrayRef<Attribute> operands) {
584 if (IntegerAttr condAttr =
585 llvm::dyn_cast_or_null<IntegerAttr>(Val: operands.front()))
586 return condAttr.getValue().isOne() ? getTrueDest() : getFalseDest();
587 return nullptr;
588}
589
590//===----------------------------------------------------------------------===//
591// SwitchOp
592//===----------------------------------------------------------------------===//
593
594void SwitchOp::build(OpBuilder &builder, OperationState &result, Value value,
595 Block *defaultDestination, ValueRange defaultOperands,
596 DenseIntElementsAttr caseValues,
597 BlockRange caseDestinations,
598 ArrayRef<ValueRange> caseOperands) {
599 build(odsBuilder&: builder, odsState&: result, flag: value, defaultOperands, caseOperands, case_values: caseValues,
600 defaultDestination, caseDestinations);
601}
602
603void SwitchOp::build(OpBuilder &builder, OperationState &result, Value value,
604 Block *defaultDestination, ValueRange defaultOperands,
605 ArrayRef<APInt> caseValues, BlockRange caseDestinations,
606 ArrayRef<ValueRange> caseOperands) {
607 DenseIntElementsAttr caseValuesAttr;
608 if (!caseValues.empty()) {
609 ShapedType caseValueType = VectorType::get(
610 shape: static_cast<int64_t>(caseValues.size()), elementType: value.getType());
611 caseValuesAttr = DenseIntElementsAttr::get(type: caseValueType, arg&: caseValues);
612 }
613 build(builder, result, value, defaultDestination, defaultOperands,
614 caseValues: caseValuesAttr, caseDestinations, caseOperands);
615}
616
617void SwitchOp::build(OpBuilder &builder, OperationState &result, Value value,
618 Block *defaultDestination, ValueRange defaultOperands,
619 ArrayRef<int32_t> caseValues, BlockRange caseDestinations,
620 ArrayRef<ValueRange> caseOperands) {
621 DenseIntElementsAttr caseValuesAttr;
622 if (!caseValues.empty()) {
623 ShapedType caseValueType = VectorType::get(
624 shape: static_cast<int64_t>(caseValues.size()), elementType: value.getType());
625 caseValuesAttr = DenseIntElementsAttr::get(type: caseValueType, arg&: caseValues);
626 }
627 build(builder, result, value, defaultDestination, defaultOperands,
628 caseValues: caseValuesAttr, caseDestinations, caseOperands);
629}
630
631/// <cases> ::= `default` `:` bb-id (`(` ssa-use-and-type-list `)`)?
632/// ( `,` integer `:` bb-id (`(` ssa-use-and-type-list `)`)? )*
633static ParseResult parseSwitchOpCases(
634 OpAsmParser &parser, Type &flagType, Block *&defaultDestination,
635 SmallVectorImpl<OpAsmParser::UnresolvedOperand> &defaultOperands,
636 SmallVectorImpl<Type> &defaultOperandTypes,
637 DenseIntElementsAttr &caseValues,
638 SmallVectorImpl<Block *> &caseDestinations,
639 SmallVectorImpl<SmallVector<OpAsmParser::UnresolvedOperand>> &caseOperands,
640 SmallVectorImpl<SmallVector<Type>> &caseOperandTypes) {
641 if (parser.parseKeyword(keyword: "default") || parser.parseColon() ||
642 parser.parseSuccessor(dest&: defaultDestination))
643 return failure();
644 if (succeeded(Result: parser.parseOptionalLParen())) {
645 if (parser.parseOperandList(result&: defaultOperands,
646 delimiter: OpAsmParser::Delimiter::None) ||
647 parser.parseColonTypeList(result&: defaultOperandTypes) || parser.parseRParen())
648 return failure();
649 }
650
651 SmallVector<APInt> values;
652 unsigned bitWidth = flagType.getIntOrFloatBitWidth();
653 while (succeeded(Result: parser.parseOptionalComma())) {
654 SMLoc valueLoc = parser.getCurrentLocation();
655 APInt value;
656 if (failed(Result: parser.parseInteger(result&: value)))
657 return failure();
658 if (value.isNegative() ? !value.isSignedIntN(N: bitWidth)
659 : !value.isIntN(N: bitWidth))
660 return parser.emitError(loc: valueLoc)
661 << "case value is out of range for " << flagType;
662 values.push_back(Elt: value.sextOrTrunc(width: bitWidth));
663
664 Block *destination;
665 SmallVector<OpAsmParser::UnresolvedOperand> operands;
666 SmallVector<Type> operandTypes;
667 if (failed(Result: parser.parseColon()) ||
668 failed(Result: parser.parseSuccessor(dest&: destination)))
669 return failure();
670 if (succeeded(Result: parser.parseOptionalLParen())) {
671 if (failed(Result: parser.parseOperandList(result&: operands,
672 delimiter: OpAsmParser::Delimiter::None)) ||
673 failed(Result: parser.parseColonTypeList(result&: operandTypes)) ||
674 failed(Result: parser.parseRParen()))
675 return failure();
676 }
677 caseDestinations.push_back(Elt: destination);
678 caseOperands.emplace_back(Args&: operands);
679 caseOperandTypes.emplace_back(Args&: operandTypes);
680 }
681
682 if (!values.empty()) {
683 ShapedType caseValueType =
684 VectorType::get(shape: static_cast<int64_t>(values.size()), elementType: flagType);
685 caseValues = DenseIntElementsAttr::get(type: caseValueType, arg&: values);
686 }
687 return success();
688}
689
690static void printSwitchOpCases(
691 OpAsmPrinter &p, SwitchOp op, Type flagType, Block *defaultDestination,
692 OperandRange defaultOperands, TypeRange defaultOperandTypes,
693 DenseIntElementsAttr caseValues, SuccessorRange caseDestinations,
694 OperandRangeRange caseOperands, const TypeRangeRange &caseOperandTypes) {
695 p << " default: ";
696 p.printSuccessorAndUseList(successor: defaultDestination, succOperands: defaultOperands);
697
698 if (!caseValues)
699 return;
700
701 for (const auto &it : llvm::enumerate(First: caseValues.getValues<APInt>())) {
702 p << ',';
703 p.printNewline();
704 p << " ";
705 p << it.value();
706 p << ": ";
707 p.printSuccessorAndUseList(successor: caseDestinations[it.index()],
708 succOperands: caseOperands[it.index()]);
709 }
710 p.printNewline();
711}
712
713LogicalResult SwitchOp::verify() {
714 auto caseValues = getCaseValues();
715 auto caseDestinations = getCaseDestinations();
716
717 if (!caseValues && caseDestinations.empty())
718 return success();
719
720 Type flagType = getFlag().getType();
721 Type caseValueType = caseValues->getType().getElementType();
722 if (caseValueType != flagType)
723 return emitOpError() << "'flag' type (" << flagType
724 << ") should match case value type (" << caseValueType
725 << ")";
726
727 if (caseValues &&
728 caseValues->size() != static_cast<int64_t>(caseDestinations.size()))
729 return emitOpError() << "number of case values (" << caseValues->size()
730 << ") should match number of "
731 "case destinations ("
732 << caseDestinations.size() << ")";
733 return success();
734}
735
736SuccessorOperands SwitchOp::getSuccessorOperands(unsigned index) {
737 assert(index < getNumSuccessors() && "invalid successor index");
738 return SuccessorOperands(index == 0 ? getDefaultOperandsMutable()
739 : getCaseOperandsMutable(index: index - 1));
740}
741
742Block *SwitchOp::getSuccessorForOperands(ArrayRef<Attribute> operands) {
743 std::optional<DenseIntElementsAttr> caseValues = getCaseValues();
744
745 if (!caseValues)
746 return getDefaultDestination();
747
748 SuccessorRange caseDests = getCaseDestinations();
749 if (auto value = llvm::dyn_cast_or_null<IntegerAttr>(Val: operands.front())) {
750 for (const auto &it : llvm::enumerate(First: caseValues->getValues<APInt>()))
751 if (it.value() == value.getValue())
752 return caseDests[it.index()];
753 return getDefaultDestination();
754 }
755 return nullptr;
756}
757
758/// switch %flag : i32, [
759/// default: ^bb1
760/// ]
761/// -> br ^bb1
762static LogicalResult simplifySwitchWithOnlyDefault(SwitchOp op,
763 PatternRewriter &rewriter) {
764 if (!op.getCaseDestinations().empty())
765 return failure();
766
767 rewriter.replaceOpWithNewOp<BranchOp>(op, args: op.getDefaultDestination(),
768 args: op.getDefaultOperands());
769 return success();
770}
771
772/// switch %flag : i32, [
773/// default: ^bb1,
774/// 42: ^bb1,
775/// 43: ^bb2
776/// ]
777/// ->
778/// switch %flag : i32, [
779/// default: ^bb1,
780/// 43: ^bb2
781/// ]
782static LogicalResult
783dropSwitchCasesThatMatchDefault(SwitchOp op, PatternRewriter &rewriter) {
784 SmallVector<Block *> newCaseDestinations;
785 SmallVector<ValueRange> newCaseOperands;
786 SmallVector<APInt> newCaseValues;
787 bool requiresChange = false;
788 auto caseValues = op.getCaseValues();
789 auto caseDests = op.getCaseDestinations();
790
791 for (const auto &it : llvm::enumerate(First: caseValues->getValues<APInt>())) {
792 if (caseDests[it.index()] == op.getDefaultDestination() &&
793 op.getCaseOperands(index: it.index()) == op.getDefaultOperands()) {
794 requiresChange = true;
795 continue;
796 }
797 newCaseDestinations.push_back(Elt: caseDests[it.index()]);
798 newCaseOperands.push_back(Elt: op.getCaseOperands(index: it.index()));
799 newCaseValues.push_back(Elt: it.value());
800 }
801
802 if (!requiresChange)
803 return failure();
804
805 rewriter.replaceOpWithNewOp<SwitchOp>(
806 op, args: op.getFlag(), args: op.getDefaultDestination(), args: op.getDefaultOperands(),
807 args&: newCaseValues, args&: newCaseDestinations, args&: newCaseOperands);
808 return success();
809}
810
811/// Drop cases whose destination block contains only ub.unreachable. If the
812/// default destination is unreachable, the last remaining case becomes the new
813/// default destination, or the switch is replaced by ub.unreachable if no case
814/// remains.
815/// switch %flag : i32, [
816/// default: ^bb1,
817/// 42: ^bb2,
818/// 43: ^bb3
819/// ]
820/// ^bb3:
821/// ub.unreachable
822/// -> switch %flag : i32, [
823/// default: ^bb1,
824/// 42: ^bb2
825/// ]
826static LogicalResult dropUnreachableSwitchCases(SwitchOp op,
827 PatternRewriter &rewriter) {
828 std::optional<DenseIntElementsAttr> caseValues = op.getCaseValues();
829 if (!caseValues)
830 return failure();
831
832 SmallVector<APInt> newCaseValues;
833 SmallVector<Block *> newCaseDestinations;
834 SmallVector<ValueRange> newCaseOperands;
835 auto caseDests = op.getCaseDestinations();
836 for (const auto &it : llvm::enumerate(First: caseValues->getValues<APInt>())) {
837 if (isUnreachableBlock(block: caseDests[it.index()]))
838 continue;
839 newCaseValues.push_back(Elt: it.value());
840 newCaseDestinations.push_back(Elt: caseDests[it.index()]);
841 newCaseOperands.push_back(Elt: op.getCaseOperands(index: it.index()));
842 }
843
844 Block *defaultDest = op.getDefaultDestination();
845 ValueRange defaultOperands = op.getDefaultOperands();
846 if (isUnreachableBlock(block: defaultDest)) {
847 // Every destination is unreachable, so the switch itself is unreachable.
848 if (newCaseDestinations.empty()) {
849 rewriter.replaceOpWithNewOp<ub::UnreachableOp>(op);
850 return success();
851 }
852 // Any value not matching a remaining case is undefined behavior, so the
853 // last remaining case can serve as the default destination.
854 defaultDest = newCaseDestinations.pop_back_val();
855 defaultOperands = newCaseOperands.pop_back_val();
856 newCaseValues.pop_back();
857 } else if (newCaseDestinations.size() == caseDests.size()) {
858 return failure();
859 }
860
861 if (newCaseDestinations.empty()) {
862 rewriter.replaceOpWithNewOp<BranchOp>(op, args&: defaultDest, args&: defaultOperands);
863 return success();
864 }
865 rewriter.replaceOpWithNewOp<SwitchOp>(op, args: op.getFlag(), args&: defaultDest,
866 args&: defaultOperands, args&: newCaseValues,
867 args&: newCaseDestinations, args&: newCaseOperands);
868 return success();
869}
870
871/// Helper for folding a switch with a constant value.
872/// switch %c_42 : i32, [
873/// default: ^bb1 ,
874/// 42: ^bb2,
875/// 43: ^bb3
876/// ]
877/// -> br ^bb2
878static void foldSwitch(SwitchOp op, PatternRewriter &rewriter,
879 const APInt &caseValue) {
880 auto caseValues = op.getCaseValues();
881 for (const auto &it : llvm::enumerate(First: caseValues->getValues<APInt>())) {
882 if (it.value() == caseValue) {
883 rewriter.replaceOpWithNewOp<BranchOp>(
884 op, args: op.getCaseDestinations()[it.index()],
885 args: op.getCaseOperands(index: it.index()));
886 return;
887 }
888 }
889 rewriter.replaceOpWithNewOp<BranchOp>(op, args: op.getDefaultDestination(),
890 args: op.getDefaultOperands());
891}
892
893/// switch %c_42 : i32, [
894/// default: ^bb1,
895/// 42: ^bb2,
896/// 43: ^bb3
897/// ]
898/// -> br ^bb2
899static LogicalResult simplifyConstSwitchValue(SwitchOp op,
900 PatternRewriter &rewriter) {
901 APInt caseValue;
902 if (!matchPattern(value: op.getFlag(), pattern: m_ConstantInt(bind_value: &caseValue)))
903 return failure();
904
905 foldSwitch(op, rewriter, caseValue);
906 return success();
907}
908
909/// switch %c_42 : i32, [
910/// default: ^bb1,
911/// 42: ^bb2,
912/// ]
913/// ^bb2:
914/// br ^bb3
915/// ->
916/// switch %c_42 : i32, [
917/// default: ^bb1,
918/// 42: ^bb3,
919/// ]
920static LogicalResult simplifyPassThroughSwitch(SwitchOp op,
921 PatternRewriter &rewriter) {
922 SmallVector<Block *> newCaseDests;
923 SmallVector<ValueRange> newCaseOperands;
924 SmallVector<SmallVector<Value>> argStorage;
925 auto caseValues = op.getCaseValues();
926 argStorage.reserve(N: caseValues->size() + 1);
927 auto caseDests = op.getCaseDestinations();
928 bool requiresChange = false;
929 for (int64_t i = 0, size = caseValues->size(); i < size; ++i) {
930 Block *caseDest = caseDests[i];
931 ValueRange caseOperands = op.getCaseOperands(index: i);
932 argStorage.emplace_back();
933 if (succeeded(Result: collapseBranch(successor&: caseDest, successorOperands&: caseOperands, argStorage&: argStorage.back())))
934 requiresChange = true;
935
936 newCaseDests.push_back(Elt: caseDest);
937 newCaseOperands.push_back(Elt: caseOperands);
938 }
939
940 Block *defaultDest = op.getDefaultDestination();
941 ValueRange defaultOperands = op.getDefaultOperands();
942 argStorage.emplace_back();
943
944 if (succeeded(
945 Result: collapseBranch(successor&: defaultDest, successorOperands&: defaultOperands, argStorage&: argStorage.back())))
946 requiresChange = true;
947
948 if (!requiresChange)
949 return failure();
950
951 rewriter.replaceOpWithNewOp<SwitchOp>(op, args: op.getFlag(), args&: defaultDest,
952 args&: defaultOperands, args&: *caseValues,
953 args&: newCaseDests, args&: newCaseOperands);
954 return success();
955}
956
957/// switch %flag : i32, [
958/// default: ^bb1,
959/// 42: ^bb2,
960/// ]
961/// ^bb2:
962/// switch %flag : i32, [
963/// default: ^bb3,
964/// 42: ^bb4
965/// ]
966/// ->
967/// switch %flag : i32, [
968/// default: ^bb1,
969/// 42: ^bb2,
970/// ]
971/// ^bb2:
972/// br ^bb4
973///
974/// and
975///
976/// switch %flag : i32, [
977/// default: ^bb1,
978/// 42: ^bb2,
979/// ]
980/// ^bb2:
981/// switch %flag : i32, [
982/// default: ^bb3,
983/// 43: ^bb4
984/// ]
985/// ->
986/// switch %flag : i32, [
987/// default: ^bb1,
988/// 42: ^bb2,
989/// ]
990/// ^bb2:
991/// br ^bb3
992static LogicalResult
993simplifySwitchFromSwitchOnSameCondition(SwitchOp op,
994 PatternRewriter &rewriter) {
995 // Check that we have a single distinct predecessor.
996 Block *currentBlock = op->getBlock();
997 Block *predecessor = currentBlock->getSinglePredecessor();
998 if (!predecessor)
999 return failure();
1000
1001 // Check that the predecessor terminates with a switch branch to this block
1002 // and that it branches on the same condition and that this branch isn't the
1003 // default destination.
1004 auto predSwitch = dyn_cast<SwitchOp>(Val: predecessor->getTerminator());
1005 if (!predSwitch || op.getFlag() != predSwitch.getFlag() ||
1006 predSwitch.getDefaultDestination() == currentBlock)
1007 return failure();
1008
1009 // Fold this switch to an unconditional branch.
1010 SuccessorRange predDests = predSwitch.getCaseDestinations();
1011 auto it = llvm::find(Range&: predDests, Val: currentBlock);
1012 if (it != predDests.end()) {
1013 std::optional<DenseIntElementsAttr> predCaseValues =
1014 predSwitch.getCaseValues();
1015 foldSwitch(op, rewriter,
1016 caseValue: predCaseValues->getValues<APInt>()[it - predDests.begin()]);
1017 } else {
1018 rewriter.replaceOpWithNewOp<BranchOp>(op, args: op.getDefaultDestination(),
1019 args: op.getDefaultOperands());
1020 }
1021 return success();
1022}
1023
1024/// switch %flag : i32, [
1025/// default: ^bb1,
1026/// 42: ^bb2
1027/// ]
1028/// ^bb1:
1029/// switch %flag : i32, [
1030/// default: ^bb3,
1031/// 42: ^bb4,
1032/// 43: ^bb5
1033/// ]
1034/// ->
1035/// switch %flag : i32, [
1036/// default: ^bb1,
1037/// 42: ^bb2,
1038/// ]
1039/// ^bb1:
1040/// switch %flag : i32, [
1041/// default: ^bb3,
1042/// 43: ^bb5
1043/// ]
1044static LogicalResult
1045simplifySwitchFromDefaultSwitchOnSameCondition(SwitchOp op,
1046 PatternRewriter &rewriter) {
1047 // Check that we have a single distinct predecessor.
1048 Block *currentBlock = op->getBlock();
1049 Block *predecessor = currentBlock->getSinglePredecessor();
1050 if (!predecessor)
1051 return failure();
1052
1053 // Check that the predecessor terminates with a switch branch to this block
1054 // and that it branches on the same condition and that this branch is the
1055 // default destination.
1056 auto predSwitch = dyn_cast<SwitchOp>(Val: predecessor->getTerminator());
1057 if (!predSwitch || op.getFlag() != predSwitch.getFlag() ||
1058 predSwitch.getDefaultDestination() != currentBlock)
1059 return failure();
1060
1061 // Delete case values that are not possible here.
1062 DenseSet<APInt> caseValuesToRemove;
1063 auto predDests = predSwitch.getCaseDestinations();
1064 auto predCaseValues = predSwitch.getCaseValues();
1065 for (int64_t i = 0, size = predCaseValues->size(); i < size; ++i)
1066 if (currentBlock != predDests[i])
1067 caseValuesToRemove.insert(V: predCaseValues->getValues<APInt>()[i]);
1068
1069 SmallVector<Block *> newCaseDestinations;
1070 SmallVector<ValueRange> newCaseOperands;
1071 SmallVector<APInt> newCaseValues;
1072 bool requiresChange = false;
1073
1074 auto caseValues = op.getCaseValues();
1075 auto caseDests = op.getCaseDestinations();
1076 for (const auto &it : llvm::enumerate(First: caseValues->getValues<APInt>())) {
1077 if (caseValuesToRemove.contains(V: it.value())) {
1078 requiresChange = true;
1079 continue;
1080 }
1081 newCaseDestinations.push_back(Elt: caseDests[it.index()]);
1082 newCaseOperands.push_back(Elt: op.getCaseOperands(index: it.index()));
1083 newCaseValues.push_back(Elt: it.value());
1084 }
1085
1086 if (!requiresChange)
1087 return failure();
1088
1089 rewriter.replaceOpWithNewOp<SwitchOp>(
1090 op, args: op.getFlag(), args: op.getDefaultDestination(), args: op.getDefaultOperands(),
1091 args&: newCaseValues, args&: newCaseDestinations, args&: newCaseOperands);
1092 return success();
1093}
1094
1095void SwitchOp::getCanonicalizationPatterns(RewritePatternSet &results,
1096 MLIRContext *context) {
1097 results.add(implFn: &simplifySwitchWithOnlyDefault)
1098 .add(implFn: &dropSwitchCasesThatMatchDefault)
1099 .add(implFn: &dropUnreachableSwitchCases)
1100 .add(implFn: &simplifyConstSwitchValue)
1101 .add(implFn: &simplifyPassThroughSwitch)
1102 .add(implFn: &simplifySwitchFromSwitchOnSameCondition)
1103 .add(implFn: &simplifySwitchFromDefaultSwitchOnSameCondition)
1104 .add<SimplifyUniformBlockArguments>(arg&: context);
1105}
1106
1107//===----------------------------------------------------------------------===//
1108// TableGen'd op method definitions
1109//===----------------------------------------------------------------------===//
1110
1111#define GET_OP_CLASSES
1112#include "mlir/Dialect/ControlFlow/IR/ControlFlowOps.cpp.inc"
1113