1//===- ParallelLoopTiling.cpp - Tiles scf.parallel ------------------------===//
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 tiling on parallel loops.
10//
11//===----------------------------------------------------------------------===//
12
13#include "mlir/Dialect/SCF/Transforms/Passes.h"
14
15#include "mlir/Dialect/Affine/IR/AffineOps.h"
16#include "mlir/Dialect/Arith/IR/Arith.h"
17#include "mlir/Dialect/SCF/IR/SCF.h"
18#include "mlir/Dialect/SCF/Transforms/Transforms.h"
19#include "mlir/Dialect/SCF/Utils/Utils.h"
20
21namespace mlir {
22#define GEN_PASS_DEF_SCFPARALLELLOOPTILING
23#include "mlir/Dialect/SCF/Transforms/Passes.h.inc"
24} // namespace mlir
25
26using namespace mlir;
27using namespace mlir::scf;
28
29/// Tile a parallel loop of the form
30/// scf.parallel (%i0, %i1) = (%arg0, %arg1) to (%arg2, %arg3)
31/// step (%arg4, %arg5)
32///
33/// into
34/// scf.parallel (%i0, %i1) = (%arg0, %arg1) to (%arg2, %arg3)
35/// step (%arg4*tileSize[0],
36/// %arg5*tileSize[1])
37/// scf.parallel (%j0, %j1) = (0, 0) to (min(%arg4*tileSize[0], %arg2-%i0)
38/// min(%arg5*tileSize[1], %arg3-%i1))
39/// step (%arg4, %arg5)
40///
41/// or, when no-min-max-bounds is true, into
42/// scf.parallel (%i0, %i1) = (%arg0, %arg1) to (%arg2, %arg3)
43/// step (%arg4*tileSize[0],
44/// %arg5*tileSize[1])
45/// scf.parallel (%j0, %j1) = (0, 0) to (%arg4*tileSize[0],
46/// %arg5*tileSize[1])
47/// step (%arg4, %arg5)
48/// %inbound = (%j0 * %arg4 + %i0 < %arg2) &&
49/// (%j1 * %arg5 + %i1 < %arg3)
50/// scf.if (%inbound)
51/// ....
52///
53/// where the uses of %i0 and %i1 in the loop body are replaced by
54/// %i0 + j0 and %i1 + %j1.
55///
56/// The old loop is replaced with the new one.
57std::pair<ParallelOp, ParallelOp>
58mlir::scf::tileParallelLoop(ParallelOp op, ArrayRef<int64_t> tileSizes,
59 bool noMinMaxBounds) {
60 OpBuilder b(op);
61 auto zero = arith::ConstantIndexOp::create(builder&: b, location: op.getLoc(), value: 0);
62 SmallVector<Value, 2> tileSizeConstants;
63 tileSizeConstants.reserve(N: op.getUpperBound().size());
64 for (size_t i = 0, end = op.getUpperBound().size(); i != end; ++i) {
65 if (i < tileSizes.size())
66 tileSizeConstants.push_back(
67 Elt: arith::ConstantIndexOp::create(builder&: b, location: op.getLoc(), value: tileSizes[i]));
68 else
69 // Just pick 1 for the remaining dimensions.
70 tileSizeConstants.push_back(
71 Elt: arith::ConstantIndexOp::create(builder&: b, location: op.getLoc(), value: 1));
72 }
73
74 // Create the outer loop with adjusted steps.
75 SmallVector<Value, 2> newSteps;
76 newSteps.reserve(N: op.getStep().size());
77 for (auto step : llvm::zip(t: op.getStep(), u&: tileSizeConstants)) {
78 newSteps.push_back(Elt: arith::MulIOp::create(builder&: b, location: op.getLoc(), lhs: std::get<0>(t&: step),
79 rhs: std::get<1>(t&: step)));
80 }
81 auto outerLoop = ParallelOp::create(builder&: b, location: op.getLoc(), lowerBounds: op.getLowerBound(),
82 upperBounds: op.getUpperBound(), steps: newSteps);
83 outerLoop.setUnsignedCmp(op.getUnsignedCmp());
84 b.setInsertionPointToStart(outerLoop.getBody());
85
86 // Compute min(size, dim - offset) to avoid out-of-bounds accesses.
87 auto minMap = AffineMap::get(
88 /*dimCount=*/3, /*symbolCount=*/0,
89 results: {getAffineDimExpr(/*position=*/0, context: b.getContext()),
90 getAffineDimExpr(/*position=*/1, context: b.getContext()) -
91 getAffineDimExpr(/*position=*/2, context: b.getContext())},
92 context: b.getContext());
93
94 // Create the inner loop with adjusted bounds.
95 SmallVector<Value, 2> newBounds;
96 newBounds.reserve(N: op.getUpperBound().size());
97 bool needInboundCheck = false;
98 for (auto [lowerBound, upperBound, newStep, iv, step, tileSizeConstant] :
99 llvm::zip(t: outerLoop.getLowerBound(), u: outerLoop.getUpperBound(),
100 args: outerLoop.getStep(), args: outerLoop.getInductionVars(),
101 args: op.getStep(), args&: tileSizeConstants)) {
102 // Collect the statically known loop bounds
103 auto lowerBoundConstant =
104 lowerBound.getDefiningOp<arith::ConstantIndexOp>();
105 auto upperBoundConstant =
106 upperBound.getDefiningOp<arith::ConstantIndexOp>();
107 auto stepConstant = step.getDefiningOp<arith::ConstantIndexOp>();
108 auto tileSize =
109 cast<arith::ConstantIndexOp>(Val: tileSizeConstant.getDefiningOp()).value();
110 // If the loop bounds and the loop step are constant and if the number of
111 // loop iterations is an integer multiple of the tile size, we use a static
112 // bound for the inner loop.
113 if (lowerBoundConstant && upperBoundConstant && stepConstant) {
114 auto numIterations = llvm::divideCeil(Numerator: upperBoundConstant.value() -
115 lowerBoundConstant.value(),
116 Denominator: stepConstant.value());
117 if (numIterations % tileSize == 0) {
118 newBounds.push_back(Elt: newStep);
119 continue;
120 }
121 }
122
123 // For InboundCheck mode, just use the variable outer step
124 if (noMinMaxBounds) {
125 newBounds.push_back(Elt: newStep);
126 needInboundCheck = true;
127 continue;
128 }
129
130 // Otherwise, we dynamically compute the bound for
131 // each iteration of the outer loop.
132 newBounds.push_back(
133 Elt: affine::AffineMinOp::create(builder&: b, location: op.getLoc(), resultType0: b.getIndexType(), map: minMap,
134 operands: ValueRange{newStep, upperBound, iv}));
135 }
136 auto innerLoop = ParallelOp::create(
137 builder&: b, location: op.getLoc(), lowerBounds: SmallVector<Value, 2>(newBounds.size(), zero), upperBounds: newBounds,
138 steps: op.getStep());
139 innerLoop.setUnsignedCmp(op.getUnsignedCmp());
140
141 if (noMinMaxBounds && needInboundCheck) {
142 b.setInsertionPointToStart(innerLoop.getBody());
143 // Insert in-bound check
144 Value inbound =
145 arith::ConstantIntOp::create(builder&: b, location: op.getLoc(), type: b.getIntegerType(width: 1), value: 1);
146 arith::CmpIPredicate predicate = op.getUnsignedCmp()
147 ? arith::CmpIPredicate::ult
148 : arith::CmpIPredicate::slt;
149 for (auto [outerUpperBound, outerIV, innerIV, innerStep] :
150 llvm::zip(t: outerLoop.getUpperBound(), u: outerLoop.getInductionVars(),
151 args: innerLoop.getInductionVars(), args: innerLoop.getStep())) {
152 // %in_bound = %in_bound &&
153 // (%inner_iv * %inner_step + %outer_iv < %outer_upper_bound)
154 Value index = arith::AddIOp::create(
155 builder&: b, location: op.getLoc(),
156 lhs: arith::MulIOp::create(builder&: b, location: op.getLoc(), lhs: innerIV, rhs: innerStep), rhs: outerIV);
157 Value dimInbound = arith::CmpIOp::create(builder&: b, location: op.getLoc(), predicate, lhs: index,
158 rhs: outerUpperBound);
159 inbound = arith::AndIOp::create(builder&: b, location: op.getLoc(), lhs: inbound, rhs: dimInbound);
160 }
161 auto ifInbound = IfOp::create(builder&: b, location: op.getLoc(),
162 /*resultTypes*/ ArrayRef<Type>{}, cond: inbound,
163 /*hasElseRegion*/ withElseRegion: false);
164 ifInbound.getThenRegion().takeBody(other&: op.getRegion());
165 Block &thenBlock = ifInbound.getThenRegion().front();
166 // Replace the scf.reduce terminator with an scf.yield terminator.
167 Operation *reduceOp = thenBlock.getTerminator();
168 b.setInsertionPointToEnd(&thenBlock);
169 scf::YieldOp::create(builder&: b, location: reduceOp->getLoc());
170 reduceOp->erase();
171 b.setInsertionPointToStart(innerLoop.getBody());
172 for (const auto &ivs : llvm::enumerate(First: llvm::zip(
173 t: innerLoop.getInductionVars(), u: outerLoop.getInductionVars()))) {
174 auto newIndex = arith::AddIOp::create(
175 builder&: b, location: op.getLoc(), lhs: std::get<0>(t&: ivs.value()), rhs: std::get<1>(t&: ivs.value()));
176 thenBlock.getArgument(i: ivs.index())
177 .replaceAllUsesExcept(newValue: newIndex, exceptedUser: newIndex);
178 }
179 thenBlock.eraseArguments(start: 0, num: thenBlock.getNumArguments());
180 } else {
181 innerLoop.getRegion().takeBody(other&: op.getRegion());
182 b.setInsertionPointToStart(innerLoop.getBody());
183 for (auto ivs : llvm::zip(t: innerLoop.getInductionVars(),
184 u: outerLoop.getInductionVars())) {
185 Value innerIndex = std::get<0>(t&: ivs);
186 auto newIndex = arith::AddIOp::create(builder&: b, location: op.getLoc(), lhs: std::get<0>(t&: ivs),
187 rhs: std::get<1>(t&: ivs));
188 innerIndex.replaceAllUsesExcept(newValue: newIndex, exceptedUser: newIndex);
189 }
190 }
191
192 op.erase();
193 return std::make_pair(x&: outerLoop, y&: innerLoop);
194}
195
196namespace {
197struct ParallelLoopTiling
198 : public impl::SCFParallelLoopTilingBase<ParallelLoopTiling> {
199 ParallelLoopTiling() = default;
200 explicit ParallelLoopTiling(ArrayRef<int64_t> tileSizes,
201 bool noMinMaxBounds = false) {
202 this->tileSizes = tileSizes;
203 this->noMinMaxBounds = noMinMaxBounds;
204 }
205
206 void runOnOperation() override {
207 for (auto tileSize : tileSizes)
208 if (tileSize == 0) {
209 mlir::emitError(loc: mlir::UnknownLoc::get(context: &Pass::getContext()),
210 message: "tile size cannot be 0");
211 return signalPassFailure();
212 }
213 auto *parentOp = getOperation();
214 SmallVector<ParallelOp, 2> innermostPloops;
215 getInnermostParallelLoops(rootOp: parentOp, result&: innermostPloops);
216 for (ParallelOp ploop : innermostPloops) {
217 // FIXME: Add reduction support.
218 if (ploop.getNumReductions() == 0)
219 tileParallelLoop(op: ploop, tileSizes, noMinMaxBounds);
220 }
221 }
222};
223} // namespace
224
225std::unique_ptr<Pass>
226mlir::createParallelLoopTilingPass(ArrayRef<int64_t> tileSizes,
227 bool noMinMaxBounds) {
228 return std::make_unique<ParallelLoopTiling>(args&: tileSizes, args&: noMinMaxBounds);
229}
230