MLIR 24.0.0git
LoopRangeFolding.cpp
Go to the documentation of this file.
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
14
20#include "mlir/IR/IRMapping.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(indVar.getUsers(),
54 [&](Operation *u) { return u == user; }))
55 return failure();
56
57 if (!isa<arith::AddIOp, arith::MulIOp>(user))
58 return failure();
59
60 if (!llvm::all_of(user->getOperands(), canBeFolded))
61 return failure();
62
63 if (auto mulOp = dyn_cast<arith::MulIOp>(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(multiplier);
70 if (!multiplierVal || *multiplierVal <= 0)
71 return failure();
72 }
73
74 rewriter.setInsertionPoint(op);
75 IRMapping lbMap;
76 lbMap.map(indVar, op.getLowerBound());
77 IRMapping ubMap;
78 ubMap.map(indVar, op.getUpperBound());
79 IRMapping stepMap;
80 stepMap.map(indVar, op.getStep());
81
82 Operation *lbFold = rewriter.clone(*user, lbMap);
83 Operation *ubFold = rewriter.clone(*user, ubMap);
84 Operation *stepFold = nullptr;
85 if (auto addOp = dyn_cast<arith::AddIOp>(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(*user, stepMap);
89 } else {
90 stepFold = rewriter.clone(*user, stepMap);
91 }
92
93 rewriter.modifyOpInPlace(op, [&]() {
94 op.setLowerBound(lbFold->getResult(0));
95 op.setUpperBound(ubFold->getResult(0));
96 if (stepFold)
97 op.setStep(stepFold->getResult(0));
98 });
99 rewriter.replaceOp(user, 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>(&getContext());
113 GreedyRewriteConfig config;
114 config.setStrictness(GreedyRewriteStrictness::ExistingOps)
115 .enableFolding(false)
116 .enableConstantCSE(false)
117 .setRegionSimplificationLevel(GreedySimplifyRegionLevel::Disabled);
118 if (failed(
119 applyPatternsGreedily(getOperation(), std::move(patterns), config)))
120 signalPassFailure();
121}
122
123std::unique_ptr<Pass> mlir::createForLoopRangeFoldingPass() {
124 return std::make_unique<ForLoopRangeFolding>();
125}
return success()
LogicalResult initialize(unsigned origNumLoops, ArrayRef< ReassociationIndices > foldedIterationDims)
b getContext())
void map(Value from, Value to)
Inserts a new mapping for 'from' to 'to'.
Definition IRMapping.h:30
Operation * clone(Operation &op, IRMapping &mapper)
Creates a deep copy of the specified operation, remapping any operands that use values outside of the...
Definition Builders.cpp:581
void setInsertionPoint(Block *block, Block::iterator insertPoint)
Set the insertion point to the specified location.
Definition Builders.h:401
OpResult getResult(unsigned idx)
Get the 'idx'th result of this operation.
Definition Operation.h:434
operand_range getOperands()
Returns an iterator on the underlying Value's.
Definition Operation.h:405
virtual void replaceOp(Operation *op, ValueRange newValues)
Replace the results of the given (original) operation with the specified list of values (replacements...
void modifyOpInPlace(Operation *root, CallableT &&callable)
This method is a utility wrapper around an in-place modification of an operation.
bool use_empty() const
Returns true if this value has no uses.
Definition Value.h:208
user_range getUsers() const
Definition Value.h:218
detail::InFlightRemark failed(Location loc, RemarkOpts opts)
Report an optimization remark that failed.
Definition Remarks.h:853
Include the generated interface declarations.
std::optional< int64_t > getConstantIntValue(OpFoldResult ofr)
If ofr is a constant integer or an IntegerAttr, return the integer.
std::unique_ptr< Pass > createForLoopRangeFoldingPass()
Creates a pass which folds arith ops on induction variable into loop range.
LogicalResult applyPatternsGreedily(Region &region, const FrozenRewritePatternSet &patterns, GreedyRewriteConfig config=GreedyRewriteConfig(), bool *changed=nullptr)
Rewrite ops in the given region, which must be isolated from above, by repeatedly applying the highes...
OpRewritePattern is a wrapper around RewritePattern that allows for matching and rewriting against an...