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
23namespace mlir {
24#define GEN_PASS_DEF_SCFFORLOOPRANGEFOLDING
25#include "mlir/Dialect/SCF/Transforms/Passes.h.inc"
26} // namespace mlir
27
28using namespace mlir;
29using namespace mlir::scf;
30
31namespace {
32struct 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
104struct ForLoopRangeFolding
105 : public impl::SCFForLoopRangeFoldingBase<ForLoopRangeFolding> {
106 void runOnOperation() override;
107};
108} // namespace
109
110void 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
123std::unique_ptr<Pass> mlir::createForLoopRangeFoldingPass() {
124 return std::make_unique<ForLoopRangeFolding>();
125}
126