| 1 | //===- LoopRangeFolding.cpp - Code to perform loop range folding-----------===// |
| 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 loop range folding. |
| 10 | // |
| 11 | //===----------------------------------------------------------------------===// |
| 12 | |
| 13 | #include "mlir/Dialect/SCF/Transforms/Passes.h" |
| 14 | |
| 15 | #include "mlir/Dialect/Arith/IR/Arith.h" |
| 16 | #include "mlir/Dialect/SCF/IR/SCF.h" |
| 17 | #include "mlir/Dialect/SCF/Transforms/Transforms.h" |
| 18 | #include "mlir/Dialect/SCF/Utils/Utils.h" |
| 19 | #include "mlir/Dialect/Utils/StaticValueUtils.h" |
| 20 | #include "mlir/IR/IRMapping.h" |
| 21 | #include "mlir/Transforms/GreedyPatternRewriteDriver.h" |
| 22 | |
| 23 | namespace mlir { |
| 24 | #define GEN_PASS_DEF_SCFFORLOOPRANGEFOLDING |
| 25 | #include "mlir/Dialect/SCF/Transforms/Passes.h.inc" |
| 26 | } // namespace mlir |
| 27 | |
| 28 | using namespace mlir; |
| 29 | using namespace mlir::scf; |
| 30 | |
| 31 | namespace { |
| 32 | struct ForLoopRangeFoldingPattern : public OpRewritePattern<ForOp> { |
| 33 | using Base::Base; |
| 34 | |
| 35 | void initialize() { setHasBoundedRewriteRecursion(); } |
| 36 | |
| 37 | LogicalResult matchAndRewrite(ForOp op, |
| 38 | PatternRewriter &rewriter) const override { |
| 39 | Value indVar = op.getInductionVar(); |
| 40 | |
| 41 | auto canBeFolded = [&](Value value) { |
| 42 | return op.isDefinedOutsideOfLoop(value) || value == indVar; |
| 43 | }; |
| 44 | |
| 45 | // If the induction variable is used by more than one operation, we can't |
| 46 | // fold its arith ops into the loop range. Note that a single operation |
| 47 | // may use the induction variable several times (e.g. `arith.addi %i, |
| 48 | // %i`), so check for a single user rather than a single use. |
| 49 | if (indVar.use_empty()) |
| 50 | return failure(); |
| 51 | |
| 52 | Operation *user = *indVar.getUsers().begin(); |
| 53 | if (!llvm::all_of(Range: indVar.getUsers(), |
| 54 | P: [&](Operation *u) { return u == user; })) |
| 55 | return failure(); |
| 56 | |
| 57 | if (!isa<arith::AddIOp, arith::MulIOp>(Val: user)) |
| 58 | return failure(); |
| 59 | |
| 60 | if (!llvm::all_of(Range: user->getOperands(), P: canBeFolded)) |
| 61 | return failure(); |
| 62 | |
| 63 | if (auto mulOp = dyn_cast<arith::MulIOp>(Val: user)) { |
| 64 | // Only fold if the multiplier is a known strictly positive constant. |
| 65 | // Multiplying by zero or a negative value would produce an invalid |
| 66 | // step (scf.for requires a strictly positive step). |
| 67 | Value multiplier = |
| 68 | (mulOp.getLhs() == indVar) ? mulOp.getRhs() : mulOp.getLhs(); |
| 69 | std::optional<int64_t> multiplierVal = getConstantIntValue(ofr: multiplier); |
| 70 | if (!multiplierVal || *multiplierVal <= 0) |
| 71 | return failure(); |
| 72 | } |
| 73 | |
| 74 | rewriter.setInsertionPoint(op); |
| 75 | IRMapping lbMap; |
| 76 | lbMap.map(from: indVar, to: op.getLowerBound()); |
| 77 | IRMapping ubMap; |
| 78 | ubMap.map(from: indVar, to: op.getUpperBound()); |
| 79 | IRMapping stepMap; |
| 80 | stepMap.map(from: indVar, to: op.getStep()); |
| 81 | |
| 82 | Operation *lbFold = rewriter.clone(op&: *user, mapper&: lbMap); |
| 83 | Operation *ubFold = rewriter.clone(op&: *user, mapper&: ubMap); |
| 84 | Operation *stepFold = nullptr; |
| 85 | if (auto addOp = dyn_cast<arith::AddIOp>(Val: user)) { |
| 86 | // `arith.addi %i, %i` is `2 * %i`, so the step has to be doubled too. |
| 87 | if (addOp.getLhs() == indVar && addOp.getRhs() == indVar) |
| 88 | stepFold = rewriter.clone(op&: *user, mapper&: stepMap); |
| 89 | } else { |
| 90 | stepFold = rewriter.clone(op&: *user, mapper&: stepMap); |
| 91 | } |
| 92 | |
| 93 | rewriter.modifyOpInPlace(root: op, callable: [&]() { |
| 94 | op.setLowerBound(lbFold->getResult(idx: 0)); |
| 95 | op.setUpperBound(ubFold->getResult(idx: 0)); |
| 96 | if (stepFold) |
| 97 | op.setStep(stepFold->getResult(idx: 0)); |
| 98 | }); |
| 99 | rewriter.replaceOp(op: user, newValues: indVar); |
| 100 | return success(); |
| 101 | } |
| 102 | }; |
| 103 | |
| 104 | struct ForLoopRangeFolding |
| 105 | : public impl::SCFForLoopRangeFoldingBase<ForLoopRangeFolding> { |
| 106 | void runOnOperation() override; |
| 107 | }; |
| 108 | } // namespace |
| 109 | |
| 110 | void ForLoopRangeFolding::runOnOperation() { |
| 111 | RewritePatternSet patterns(&getContext()); |
| 112 | patterns.add<ForLoopRangeFoldingPattern>(arg: &getContext()); |
| 113 | GreedyRewriteConfig config; |
| 114 | config.setStrictness(GreedyRewriteStrictness::ExistingOps) |
| 115 | .enableFolding(enable: false) |
| 116 | .enableConstantCSE(enable: false) |
| 117 | .setRegionSimplificationLevel(GreedySimplifyRegionLevel::Disabled); |
| 118 | if (failed( |
| 119 | Result: applyPatternsGreedily(op: getOperation(), patterns: std::move(patterns), config))) |
| 120 | signalPassFailure(); |
| 121 | } |
| 122 | |
| 123 | std::unique_ptr<Pass> mlir::createForLoopRangeFoldingPass() { |
| 124 | return std::make_unique<ForLoopRangeFolding>(); |
| 125 | } |
| 126 | |