1//===- LoopSpecialization.cpp - scf.parallel/SCR.for specialization -------===//
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// Specializes parallel loops and for loops for easier unrolling and
10// vectorization.
11//
12//===----------------------------------------------------------------------===//
13
14#include "mlir/Dialect/SCF/Transforms/Passes.h"
15
16#include "mlir/Dialect/Affine/Analysis/AffineStructures.h"
17#include "mlir/Dialect/Affine/IR/AffineOps.h"
18#include "mlir/Dialect/Arith/IR/Arith.h"
19#include "mlir/Dialect/SCF/IR/SCF.h"
20#include "mlir/Dialect/SCF/Transforms/Transforms.h"
21#include "mlir/Dialect/SCF/Utils/AffineCanonicalizationUtils.h"
22#include "mlir/Dialect/Utils/StaticValueUtils.h"
23#include "mlir/IR/AffineExpr.h"
24#include "mlir/IR/IRMapping.h"
25#include "mlir/IR/PatternMatch.h"
26#include "mlir/Transforms/GreedyPatternRewriteDriver.h"
27
28namespace mlir {
29#define GEN_PASS_DEF_SCFFORLOOPPEELING
30#define GEN_PASS_DEF_SCFFORLOOPSPECIALIZATION
31#define GEN_PASS_DEF_SCFPARALLELLOOPSPECIALIZATION
32#include "mlir/Dialect/SCF/Transforms/Passes.h.inc"
33} // namespace mlir
34
35using namespace mlir;
36using namespace mlir::affine;
37using scf::ForOp;
38using scf::ParallelOp;
39
40/// Rewrite a parallel loop with bounds defined by an affine.min with a constant
41/// into 2 loops after checking if the bounds are equal to that constant. This
42/// is beneficial if the loop will almost always have the constant bound and
43/// that version can be fully unrolled and vectorized.
44static void specializeParallelLoopForUnrolling(ParallelOp op) {
45 SmallVector<int64_t, 2> constantIndices;
46 constantIndices.reserve(N: op.getUpperBound().size());
47 for (auto bound : op.getUpperBound()) {
48 auto minOp = bound.getDefiningOp<AffineMinOp>();
49 if (!minOp)
50 return;
51 int64_t minConstant = std::numeric_limits<int64_t>::max();
52 for (AffineExpr expr : minOp.getMap().getResults()) {
53 if (auto constantIndex = dyn_cast<AffineConstantExpr>(Val&: expr))
54 minConstant = std::min(a: minConstant, b: constantIndex.getValue());
55 }
56 if (minConstant == std::numeric_limits<int64_t>::max())
57 return;
58 constantIndices.push_back(Elt: minConstant);
59 }
60
61 OpBuilder b(op);
62 IRMapping map;
63 Value cond;
64 for (auto bound : llvm::zip(t: op.getUpperBound(), u&: constantIndices)) {
65 Value constant =
66 arith::ConstantIndexOp::create(builder&: b, location: op.getLoc(), value: std::get<1>(t&: bound));
67 Value cmp = arith::CmpIOp::create(builder&: b, location: op.getLoc(), predicate: arith::CmpIPredicate::eq,
68 lhs: std::get<0>(t&: bound), rhs: constant);
69 cond = cond ? arith::AndIOp::create(builder&: b, location: op.getLoc(), lhs: cond, rhs: cmp) : cmp;
70 map.map(from: std::get<0>(t&: bound), to: constant);
71 }
72 auto ifOp = scf::IfOp::create(builder&: b, location: op.getLoc(), resultTypes: op.getResultTypes(), cond,
73 /*addThenBlock=*/true, /*addElseBlock=*/true);
74
75 OpBuilder thenBuilder = OpBuilder::atBlockEnd(block: &ifOp.getThenRegion().front());
76 Operation *thenOp = thenBuilder.clone(op&: *op.getOperation(), mapper&: map);
77 scf::YieldOp::create(builder&: thenBuilder, location: op.getLoc(), results: thenOp->getResults());
78
79 OpBuilder elseBuilder = OpBuilder::atBlockEnd(block: &ifOp.getElseRegion().front());
80 Operation *elseOp = elseBuilder.clone(op&: *op.getOperation());
81 scf::YieldOp::create(builder&: elseBuilder, location: op.getLoc(), results: elseOp->getResults());
82
83 op.replaceAllUsesWith(values: ifOp.getResults());
84 op.erase();
85}
86
87/// Rewrite a for loop with bounds defined by an affine.min with a constant into
88/// 2 loops after checking if the bounds are equal to that constant. This is
89/// beneficial if the loop will almost always have the constant bound and that
90/// version can be fully unrolled and vectorized.
91static void specializeForLoopForUnrolling(ForOp op) {
92 auto bound = op.getUpperBound();
93 auto minOp = bound.getDefiningOp<AffineMinOp>();
94 if (!minOp)
95 return;
96 AffineMap canonicalizedMap = minOp.getMap();
97 SmallVector<Value> operands(minOp.getMapOperands());
98 affine::canonicalizeMapAndOperands(map: &canonicalizedMap, operands: &operands);
99 int64_t minConstant = std::numeric_limits<int64_t>::max();
100 for (AffineExpr expr : canonicalizedMap.getResults()) {
101 if (auto constantIndex = dyn_cast<AffineConstantExpr>(Val&: expr))
102 minConstant = std::min(a: minConstant, b: constantIndex.getValue());
103 }
104 if (minConstant == std::numeric_limits<int64_t>::max())
105 return;
106
107 OpBuilder b(op);
108 IRMapping map;
109 Value constant = arith::ConstantOp::create(
110 builder&: b, location: op.getLoc(),
111 value: IntegerAttr::get(type: op.getUpperBound().getType(), value: minConstant));
112 Value cond = arith::CmpIOp::create(builder&: b, location: op.getLoc(), predicate: arith::CmpIPredicate::eq,
113 lhs: bound, rhs: constant);
114 map.map(from: bound, to: constant);
115 auto ifOp = scf::IfOp::create(builder&: b, location: op.getLoc(), resultTypes: op->getResultTypes(), cond,
116 /*withElseRegion=*/true);
117
118 OpBuilder thenB = ifOp.getThenBodyBuilder();
119 Operation *thenLoop = thenB.clone(op&: *op.getOperation(), mapper&: map);
120 OpBuilder elseB = ifOp.getElseBodyBuilder();
121 Operation *elseLoop = elseB.clone(op&: *op.getOperation());
122
123 if (op->getNumResults() > 0) {
124 scf::YieldOp::create(builder&: thenB, location: op.getLoc(), results: thenLoop->getResults());
125 scf::YieldOp::create(builder&: elseB, location: op.getLoc(), results: elseLoop->getResults());
126 op->replaceAllUsesWith(values: ifOp.getResults());
127 }
128 op.erase();
129}
130
131/// Rewrite a for loop with bounds/step that potentially do not divide evenly
132/// into a for loop where the step divides the iteration space evenly, followed
133/// by another scf.for for the last (partial) iteration (if any).
134///
135/// This function rewrites the given scf.for loop in-place and creates a new
136/// scf.for operation for the last iteration. It replaces all uses of the
137/// unpeeled loop with the results of the newly generated scf.for.
138///
139/// The newly generated scf.for operation is returned via `partialIteration`.
140/// The boundary at which the loop is split (new upper bound) is returned via
141/// `splitBound`. The return value indicates whether the loop was rewritten or
142/// not.
143///
144/// Note: Loops with a step size of 0 cannot be peeled. Applying this function
145/// to such a loop may result in IR with undefined behavior.
146static LogicalResult peelForLoop(RewriterBase &b, ForOp forOp,
147 ForOp &partialIteration, Value &splitBound) {
148 RewriterBase::InsertionGuard guard(b);
149 Value lbVal = forOp.getLowerBound();
150 Value ubVal = forOp.getUpperBound();
151 Value stepVal = forOp.getStep();
152 b.setInsertionPoint(forOp);
153 auto loc = forOp.getLoc();
154
155 bool isUnsigned = forOp.getUnsignedCmp();
156 IntegerAttr lbAttr, ubAttr, stepAttr;
157 if (matchPattern(value: stepVal, pattern: m_Constant(bind_value: &stepAttr))) {
158 APInt step = stepAttr.getValue();
159 if (isUnsigned ? step.ule(RHS: 1) : step.sle(RHS: 1))
160 return failure();
161 }
162 if (matchPattern(value: lbVal, pattern: m_Constant(bind_value: &lbAttr)) &&
163 matchPattern(value: ubVal, pattern: m_Constant(bind_value: &ubAttr))) {
164
165 APInt lb = lbAttr.getValue();
166 APInt ub = ubAttr.getValue();
167
168 if (isUnsigned ? ub.ule(RHS: lb) : ub.sle(RHS: lb))
169 return failure();
170
171 // lb < ub here, so ub - lb as an unsigned value is the exact distance, even
172 // for signed loops whose range exceeds the signed max. hence urem for both.
173 if (stepAttr && (ub - lb).urem(RHS: stepAttr.getValue()).isZero())
174 return failure();
175 }
176
177 // affine reasoning is signed and index-only,
178 // so use it only for signed index loops.
179 if (!isUnsigned && forOp.getInductionVar().getType().isIndex()) {
180 AffineExpr sym0, sym1, sym2;
181 bindSymbols(ctx: b.getContext(), exprs&: sym0, exprs&: sym1, exprs&: sym2);
182 SmallVector<Value> operands{forOp.getLowerBound(), forOp.getUpperBound(),
183 forOp.getStep()};
184 AffineMap map = AffineMap::get(dimCount: 0, symbolCount: 3, result: {(sym1 - sym0) % sym2});
185 affine::fullyComposeAffineMapAndOperands(map: &map, operands: &operands);
186 if (auto constExpr = dyn_cast<AffineConstantExpr>(Val: map.getResult(idx: 0)))
187 if (constExpr.getValue() == 0)
188 return failure();
189 }
190
191 // split = ub - ((ub - min(lb, ub)) remui step), with a signed or unsigned min
192 // to match the loop. For ub <= lb the min gives a zero remainder, so
193 // split = ub and both loops stay empty. For ub > lb the wrapping subtraction
194 // is the exact distance when read as unsigned, even beyond the signed range,
195 // which is why remui is used for signed loops as well.
196 Value lbEff = isUnsigned ? b.createOrFold<arith::MinUIOp>(location: loc, args&: lbVal, args&: ubVal)
197 : b.createOrFold<arith::MinSIOp>(location: loc, args&: lbVal, args&: ubVal);
198 Value diff = b.createOrFold<arith::SubIOp>(location: loc, args&: ubVal, args&: lbEff);
199 Value rem = b.createOrFold<arith::RemUIOp>(location: loc, args&: diff, args&: stepVal);
200 splitBound = b.createOrFold<arith::SubIOp>(location: loc, args&: ubVal, args&: rem);
201
202 // Create ForOp for partial iteration.
203 b.setInsertionPointAfter(forOp);
204 partialIteration = cast<ForOp>(Val: b.clone(op&: *forOp.getOperation()));
205 partialIteration.getLowerBoundMutable().assign(value: splitBound);
206 b.replaceAllUsesWith(from: forOp.getResults(), to: partialIteration->getResults());
207 partialIteration.getInitArgsMutable().assign(values: forOp->getResults());
208
209 // Set new upper loop bound.
210 b.modifyOpInPlace(root: forOp,
211 callable: [&]() { forOp.getUpperBoundMutable().assign(value: splitBound); });
212
213 return success();
214}
215
216static void rewriteAffineOpAfterPeeling(RewriterBase &rewriter, ForOp forOp,
217 ForOp partialIteration,
218 Value previousUb) {
219 Value mainIv = forOp.getInductionVar();
220 Value partialIv = partialIteration.getInductionVar();
221 assert(forOp.getStep() == partialIteration.getStep() &&
222 "expected same step in main and partial loop");
223 Value step = forOp.getStep();
224
225 forOp.walk(callback: [&](Operation *affineOp) {
226 if (!isa<AffineMinOp, AffineMaxOp>(Val: affineOp))
227 return WalkResult::advance();
228 (void)scf::rewritePeeledMinMaxOp(rewriter, op: affineOp, iv: mainIv, ub: previousUb,
229 step,
230 /*insideLoop=*/true);
231 return WalkResult::advance();
232 });
233 partialIteration.walk(callback: [&](Operation *affineOp) {
234 if (!isa<AffineMinOp, AffineMaxOp>(Val: affineOp))
235 return WalkResult::advance();
236 (void)scf::rewritePeeledMinMaxOp(rewriter, op: affineOp, iv: partialIv, ub: previousUb,
237 step, /*insideLoop=*/false);
238 return WalkResult::advance();
239 });
240}
241
242LogicalResult mlir::scf::peelForLoopAndSimplifyBounds(RewriterBase &rewriter,
243 ForOp forOp,
244 ForOp &partialIteration) {
245 Value previousUb = forOp.getUpperBound();
246 Value splitBound;
247 if (failed(Result: peelForLoop(b&: rewriter, forOp, partialIteration, splitBound)))
248 return failure();
249
250 // The affine.min/max simplification relies on signed reasoning, which does
251 // not hold for unsigned loops, so leave those ops untouched.
252 if (forOp.getUnsignedCmp())
253 return success();
254
255 // Rewrite affine.min and affine.max ops.
256 rewriteAffineOpAfterPeeling(rewriter, forOp, partialIteration, previousUb);
257
258 return success();
259}
260
261/// Rewrites the original scf::ForOp as two scf::ForOp Ops, the first
262/// scf::ForOp corresponds to the first iteration of the loop which can be
263/// canonicalized away in the following optimizations. The second loop Op
264/// contains the remaining iterations, with a lower bound updated as the
265/// original lower bound plus the step (i.e. skips the first iteration).
266LogicalResult mlir::scf::peelForLoopFirstIteration(RewriterBase &b, ForOp forOp,
267 ForOp &firstIteration) {
268 RewriterBase::InsertionGuard guard(b);
269 Value lbVal = forOp.getLowerBound();
270 Value ubVal = forOp.getUpperBound();
271 Value stepVal = forOp.getStep();
272 auto loc = forOp.getLoc();
273
274 Value splitBound;
275 b.setInsertionPoint(forOp);
276 bool isUnsigned = forOp.getUnsignedCmp();
277 IntegerAttr lbAttr, ubAttr, stepAttr;
278 bool isStepConst = matchPattern(value: stepVal, pattern: m_Constant(bind_value: &stepAttr));
279
280 if (isStepConst) {
281 APInt step = stepAttr.getValue();
282 if (isUnsigned ? step.ult(RHS: 1) : step.slt(RHS: 1))
283 return failure();
284 }
285 if (matchPattern(value: lbVal, pattern: m_Constant(bind_value: &lbAttr)) &&
286 matchPattern(value: ubVal, pattern: m_Constant(bind_value: &ubAttr)) && isStepConst) {
287
288 APInt lb = lbAttr.getValue();
289 APInt ub = ubAttr.getValue();
290 APInt step = stepAttr.getValue();
291
292 if (isUnsigned ? ub.ule(RHS: lb) : ub.sle(RHS: lb))
293 return failure();
294
295 // Peeling is not needed if there is at most one iteration. scf.for requires
296 // a positive step, so the trip count is ceil((UB - LB) / Step) when UB > LB
297 // and 0 otherwise. With a positive step, "UB - LB <= Step" therefore covers
298 // both the empty loop and the single-iteration loop. works for both signed
299 // and unsigned values since the difference is verified to be positive by
300 // ub.ule(lb) : ub.sle(lb)
301 if ((ub - lb).ule(RHS: step))
302 return failure();
303 }
304
305 // split = max(lb, min(lb + step, ub)): the first loop runs one iteration,
306 // or none if the loop is empty. If lb + step wraps, the loop has at most
307 // one iteration and split falls back to lb, so the main loop does the work.
308 Value sum = b.createOrFold<arith::AddIOp>(location: loc, args&: lbVal, args&: stepVal);
309 Value capped = isUnsigned ? b.createOrFold<arith::MinUIOp>(location: loc, args&: sum, args&: ubVal)
310 : b.createOrFold<arith::MinSIOp>(location: loc, args&: sum, args&: ubVal);
311 splitBound = isUnsigned ? b.createOrFold<arith::MaxUIOp>(location: loc, args&: lbVal, args&: capped)
312 : b.createOrFold<arith::MaxSIOp>(location: loc, args&: lbVal, args&: capped);
313
314 // Peel the first iteration.
315 firstIteration = cast<ForOp>(Val: b.clone(op&: *forOp.getOperation()));
316 b.modifyOpInPlace(root: firstIteration, callable: [&]() {
317 firstIteration.getUpperBoundMutable().assign(value: splitBound);
318 });
319 // Update main loop with new lower bound.
320 b.modifyOpInPlace(root: forOp, callable: [&]() {
321 forOp.getInitArgsMutable().assign(values: firstIteration->getResults());
322 forOp.getLowerBoundMutable().assign(value: splitBound);
323 });
324
325 return success();
326}
327
328scf::IfOp mlir::scf::convertPartialIterationToIf(RewriterBase &rewriter,
329 ForOp partialIteration) {
330 RewriterBase::InsertionGuard guard(rewriter);
331 rewriter.setInsertionPoint(partialIteration);
332 Location loc = partialIteration.getLoc();
333
334 // The partial iteration runs at most once: once if lb < ub, else not at all.
335 auto pred = partialIteration.getUnsignedCmp() ? arith::CmpIPredicate::ult
336 : arith::CmpIPredicate::slt;
337 Value cond = arith::CmpIOp::create(builder&: rewriter, location: loc, predicate: pred,
338 lhs: partialIteration.getLowerBound(),
339 rhs: partialIteration.getUpperBound());
340 bool hasResults = partialIteration.getNumResults() > 0;
341 auto ifOp = IfOp::create(builder&: rewriter, location: loc, resultTypes: partialIteration.getResultTypes(),
342 cond, /*addThenBlock=*/true,
343 /*addElseBlock=*/hasResults);
344
345 // Move the body into the "then" block. Its scf.yield becomes the terminator.
346 SmallVector<Value> replacements = {partialIteration.getLowerBound()};
347 llvm::append_range(C&: replacements, R: partialIteration.getInitArgs());
348 rewriter.inlineBlockBefore(source: partialIteration.getBody(), dest: ifOp.thenBlock(),
349 before: ifOp.thenBlock()->end(), argValues: replacements);
350
351 // If the loop does not run, it returns its init args.
352 if (hasResults) {
353 rewriter.setInsertionPointToStart(ifOp.elseBlock());
354 YieldOp::create(builder&: rewriter, location: loc, results: partialIteration.getInitArgs());
355 }
356
357 rewriter.replaceOp(op: partialIteration, newValues: ifOp.getResults());
358 return ifOp;
359}
360
361static constexpr char kPeeledLoopLabel[] = "__peeled_loop__";
362static constexpr char kPartialIterationLabel[] = "__partial_iteration__";
363
364namespace {
365struct ForLoopPeelingPattern : public OpRewritePattern<ForOp> {
366 ForLoopPeelingPattern(MLIRContext *ctx, bool peelFront, bool skipPartial,
367 bool partialAsIf)
368 : OpRewritePattern<ForOp>(ctx), peelFront(peelFront),
369 skipPartial(skipPartial), partialAsIf(partialAsIf) {}
370
371 LogicalResult matchAndRewrite(ForOp forOp,
372 PatternRewriter &rewriter) const override {
373
374 // Do not peel already peeled loops.
375 if (forOp->hasDiscardableAttr(name: kPeeledLoopLabel))
376 return failure();
377
378 scf::ForOp partialIteration;
379 // The case for peeling the first iteration of the loop.
380 if (peelFront) {
381 if (failed(
382 Result: peelForLoopFirstIteration(b&: rewriter, forOp, firstIteration&: partialIteration))) {
383 return failure();
384 }
385 } else {
386 if (skipPartial) {
387 // No peeling of loops inside the partial iteration of another peeled
388 // loop. The partial iteration is an scf.for, or an scf.if if
389 // `partialAsIf` is set.
390 Operation *op = forOp.getOperation();
391 while ((op = op->getParentOp())) {
392 if (op->hasDiscardableAttr(name: kPartialIterationLabel))
393 return failure();
394 }
395 }
396 // Apply loop peeling.
397 if (failed(
398 Result: peelForLoopAndSimplifyBounds(rewriter, forOp, partialIteration)))
399 return failure();
400 }
401
402 Operation *partialOp = partialIteration;
403 if (partialAsIf)
404 partialOp = convertPartialIterationToIf(rewriter, partialIteration);
405
406 // Apply label, so that the same loop is not rewritten a second time.
407 rewriter.modifyOpInPlace(root: partialOp, callable: [&]() {
408 partialOp->setDiscardableAttr(name: kPeeledLoopLabel, value: rewriter.getUnitAttr());
409 partialOp->setDiscardableAttr(name: kPartialIterationLabel,
410 value: rewriter.getUnitAttr());
411 });
412 rewriter.modifyOpInPlace(root: forOp, callable: [&]() {
413 forOp->setDiscardableAttr(name: kPeeledLoopLabel, value: rewriter.getUnitAttr());
414 });
415 return success();
416 }
417
418 // If set to true, the first iteration of the loop will be peeled. Otherwise,
419 // the unevenly divisible loop will be peeled at the end.
420 bool peelFront;
421
422 /// If set to true, loops inside partial iterations of another peeled loop
423 /// are not peeled. This reduces the size of the generated code. Partial
424 /// iterations are not usually performance critical.
425 /// Note: Takes into account the entire chain of parent operations, not just
426 /// the direct parent.
427 bool skipPartial;
428
429 /// If set to true, the partial iteration is emitted as an scf.if instead of
430 /// an scf.for.
431 bool partialAsIf;
432};
433} // namespace
434
435namespace {
436struct ParallelLoopSpecialization
437 : public impl::SCFParallelLoopSpecializationBase<
438 ParallelLoopSpecialization> {
439 void runOnOperation() override {
440 getOperation()->walk(
441 callback: [](ParallelOp op) { specializeParallelLoopForUnrolling(op); });
442 }
443};
444
445struct ForLoopSpecialization
446 : public impl::SCFForLoopSpecializationBase<ForLoopSpecialization> {
447 void runOnOperation() override {
448 getOperation()->walk(callback: [](ForOp op) { specializeForLoopForUnrolling(op); });
449 }
450};
451
452struct ForLoopPeeling : public impl::SCFForLoopPeelingBase<ForLoopPeeling> {
453 using impl::SCFForLoopPeelingBase<ForLoopPeeling>::SCFForLoopPeelingBase;
454
455 void runOnOperation() override {
456 auto *parentOp = getOperation();
457 MLIRContext *ctx = parentOp->getContext();
458 RewritePatternSet patterns(ctx);
459 patterns.add<ForLoopPeelingPattern>(arg&: ctx, args&: peelFront, args&: skipPartial,
460 args&: partialAsIf);
461 (void)applyPatternsGreedily(op: parentOp, patterns: std::move(patterns));
462
463 // Drop the markers.
464 parentOp->walk(callback: [](Operation *op) {
465 op->removeDiscardableAttr(name: kPeeledLoopLabel);
466 op->removeDiscardableAttr(name: kPartialIterationLabel);
467 });
468 }
469};
470} // namespace
471
472std::unique_ptr<Pass> mlir::createParallelLoopSpecializationPass() {
473 return std::make_unique<ParallelLoopSpecialization>();
474}
475
476std::unique_ptr<Pass> mlir::createForLoopSpecializationPass() {
477 return std::make_unique<ForLoopSpecialization>();
478}
479