1//===- Utils.cpp ---- Misc utilities for loop transformation ----------===//
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 miscellaneous loop transformation routines.
10//
11//===----------------------------------------------------------------------===//
12
13#include "mlir/Dialect/SCF/Utils/Utils.h"
14#include "mlir/Analysis/SliceAnalysis.h"
15#include "mlir/Dialect/Affine/IR/AffineOps.h"
16#include "mlir/Dialect/Arith/IR/Arith.h"
17#include "mlir/Dialect/Arith/Utils/Utils.h"
18#include "mlir/Dialect/Func/IR/FuncOps.h"
19#include "mlir/Dialect/SCF/IR/SCF.h"
20#include "mlir/IR/IRMapping.h"
21#include "mlir/IR/OpDefinition.h"
22#include "mlir/IR/PatternMatch.h"
23#include "mlir/Interfaces/SideEffectInterfaces.h"
24#include "mlir/Transforms/RegionUtils.h"
25#include "llvm/ADT/APInt.h"
26#include "llvm/ADT/STLExtras.h"
27#include "llvm/ADT/SmallVector.h"
28#include "llvm/ADT/SmallVectorExtras.h"
29#include "llvm/Support/DebugLog.h"
30#include <cstdint>
31
32using namespace mlir;
33
34#define DEBUG_TYPE "scf-utils"
35
36SmallVector<scf::ForOp> mlir::replaceLoopNestWithNewYields(
37 RewriterBase &rewriter, MutableArrayRef<scf::ForOp> loopNest,
38 ValueRange newIterOperands, const NewYieldValuesFn &newYieldValuesFn,
39 bool replaceIterOperandsUsesInLoop) {
40 if (loopNest.empty())
41 return {};
42 // This method is recursive (to make it more readable). Adding an
43 // assertion here to limit the recursion. (See
44 // https://discourse.llvm.org/t/rfc-update-to-mlir-developer-policy-on-recursion/62235)
45 assert(loopNest.size() <= 10 &&
46 "exceeded recursion limit when yielding value from loop nest");
47
48 // To yield a value from a perfectly nested loop nest, the following
49 // pattern needs to be created, i.e. starting with
50 //
51 // ```mlir
52 // scf.for .. {
53 // scf.for .. {
54 // scf.for .. {
55 // %value = ...
56 // }
57 // }
58 // }
59 // ```
60 //
61 // needs to be modified to
62 //
63 // ```mlir
64 // %0 = scf.for .. iter_args(%arg0 = %init) {
65 // %1 = scf.for .. iter_args(%arg1 = %arg0) {
66 // %2 = scf.for .. iter_args(%arg2 = %arg1) {
67 // %value = ...
68 // scf.yield %value
69 // }
70 // scf.yield %2
71 // }
72 // scf.yield %1
73 // }
74 // ```
75 //
76 // The inner most loop is handled using the `replaceWithAdditionalYields`
77 // that works on a single loop.
78 if (loopNest.size() == 1) {
79 auto innerMostLoop =
80 cast<scf::ForOp>(Val: *loopNest.back().replaceWithAdditionalYields(
81 rewriter, newInitOperands: newIterOperands, replaceInitOperandUsesInLoop: replaceIterOperandsUsesInLoop,
82 newYieldValuesFn));
83 return {innerMostLoop};
84 }
85 // The outer loops are modified by calling this method recursively
86 // - The return value of the inner loop is the value yielded by this loop.
87 // - The region iter args of this loop are the init_args for the inner loop.
88 SmallVector<scf::ForOp> newLoopNest;
89 NewYieldValuesFn fn =
90 [&](OpBuilder &innerBuilder, Location loc,
91 ArrayRef<BlockArgument> innerNewBBArgs) -> SmallVector<Value> {
92 newLoopNest = replaceLoopNestWithNewYields(rewriter, loopNest: loopNest.drop_front(),
93 newIterOperands: innerNewBBArgs, newYieldValuesFn,
94 replaceIterOperandsUsesInLoop);
95 return llvm::map_to_vector(
96 C: newLoopNest.front().getResults().take_back(n: innerNewBBArgs.size()),
97 F: [](OpResult r) -> Value { return r; });
98 };
99 scf::ForOp outerMostLoop =
100 cast<scf::ForOp>(Val: *loopNest.front().replaceWithAdditionalYields(
101 rewriter, newInitOperands: newIterOperands, replaceInitOperandUsesInLoop: replaceIterOperandsUsesInLoop, newYieldValuesFn: fn));
102 newLoopNest.insert(I: newLoopNest.begin(), Elt: outerMostLoop);
103 return newLoopNest;
104}
105
106/// Outline a region with a single block into a new FuncOp.
107/// Assumes the FuncOp result types is the type of the yielded operands of the
108/// single block. This constraint makes it easy to determine the result.
109/// This method also clones the `arith::ConstantIndexOp` at the start of
110/// `outlinedFuncBody` to alloc simple canonicalizations. If `callOp` is
111/// provided, it will be set to point to the operation that calls the outlined
112/// function.
113// TODO: support more than single-block regions.
114// TODO: more flexible constant handling.
115FailureOr<func::FuncOp> mlir::outlineSingleBlockRegion(RewriterBase &rewriter,
116 Location loc,
117 Region &region,
118 StringRef funcName,
119 func::CallOp *callOp) {
120 assert(!funcName.empty() && "funcName cannot be empty");
121 if (!region.hasOneBlock())
122 return failure();
123
124 Block *originalBlock = &region.front();
125 Operation *originalTerminator = originalBlock->getTerminator();
126
127 // Outline before current function.
128 OpBuilder::InsertionGuard g(rewriter);
129 rewriter.setInsertionPoint(region.getParentOfType<FunctionOpInterface>());
130
131 SetVector<Value> captures;
132 getUsedValuesDefinedAbove(regions: region, values&: captures);
133
134 ValueRange outlinedValues(captures.getArrayRef());
135 SmallVector<Type> outlinedFuncArgTypes;
136 SmallVector<Location> outlinedFuncArgLocs;
137 // Region's arguments are exactly the first block's arguments as per
138 // Region::getArguments().
139 // Func's arguments are cat(regions's arguments, captures arguments).
140 for (BlockArgument arg : region.getArguments()) {
141 outlinedFuncArgTypes.push_back(Elt: arg.getType());
142 outlinedFuncArgLocs.push_back(Elt: arg.getLoc());
143 }
144 for (Value value : outlinedValues) {
145 outlinedFuncArgTypes.push_back(Elt: value.getType());
146 outlinedFuncArgLocs.push_back(Elt: value.getLoc());
147 }
148 FunctionType outlinedFuncType =
149 FunctionType::get(context: rewriter.getContext(), inputs: outlinedFuncArgTypes,
150 results: originalTerminator->getOperandTypes());
151 auto outlinedFunc =
152 func::FuncOp::create(builder&: rewriter, location: loc, name: funcName, type: outlinedFuncType);
153 Block *outlinedFuncBody = outlinedFunc.addEntryBlock();
154
155 // Merge blocks while replacing the original block operands.
156 // Warning: `mergeBlocks` erases the original block, reconstruct it later.
157 int64_t numOriginalBlockArguments = originalBlock->getNumArguments();
158 auto outlinedFuncBlockArgs = outlinedFuncBody->getArguments();
159 {
160 OpBuilder::InsertionGuard g(rewriter);
161 rewriter.setInsertionPointToEnd(outlinedFuncBody);
162 rewriter.mergeBlocks(
163 source: originalBlock, dest: outlinedFuncBody,
164 argValues: outlinedFuncBlockArgs.take_front(N: numOriginalBlockArguments));
165 // Explicitly set up a new ReturnOp terminator.
166 rewriter.setInsertionPointToEnd(outlinedFuncBody);
167 func::ReturnOp::create(builder&: rewriter, location: loc, resultTypes: originalTerminator->getResultTypes(),
168 operands: originalTerminator->getOperands());
169 }
170
171 // Reconstruct the block that was deleted and add a
172 // terminator(call_results).
173 Block *newBlock = rewriter.createBlock(
174 parent: &region, insertPt: region.begin(),
175 argTypes: TypeRange{outlinedFuncArgTypes}.take_front(n: numOriginalBlockArguments),
176 locs: ArrayRef<Location>(outlinedFuncArgLocs)
177 .take_front(N: numOriginalBlockArguments));
178 {
179 OpBuilder::InsertionGuard g(rewriter);
180 rewriter.setInsertionPointToEnd(newBlock);
181 SmallVector<Value> callValues;
182 llvm::append_range(C&: callValues, R: newBlock->getArguments());
183 llvm::append_range(C&: callValues, R&: outlinedValues);
184 auto call = func::CallOp::create(builder&: rewriter, location: loc, callee: outlinedFunc, operands: callValues);
185 if (callOp)
186 *callOp = call;
187
188 // `originalTerminator` was moved to `outlinedFuncBody` and is still valid.
189 // Clone `originalTerminator` to take the callOp results then erase it from
190 // `outlinedFuncBody`.
191 IRMapping bvm;
192 bvm.map(from: originalTerminator->getOperands(), to: call->getResults());
193 rewriter.clone(op&: *originalTerminator, mapper&: bvm);
194 rewriter.eraseOp(op: originalTerminator);
195 }
196
197 // Lastly, explicit RAUW outlinedValues, only for uses within `outlinedFunc`.
198 // Clone the `arith::ConstantIndexOp` at the start of `outlinedFuncBody`.
199 for (auto it : llvm::zip(t&: outlinedValues, u: outlinedFuncBlockArgs.take_back(
200 N: outlinedValues.size()))) {
201 Value orig = std::get<0>(t&: it);
202 Value repl = std::get<1>(t&: it);
203 {
204 OpBuilder::InsertionGuard g(rewriter);
205 rewriter.setInsertionPointToStart(outlinedFuncBody);
206 if (Operation *cst = orig.getDefiningOp<arith::ConstantIndexOp>()) {
207 repl = rewriter.clone(op&: *cst)->getResult(idx: 0);
208 }
209 }
210 orig.replaceUsesWithIf(newValue: repl, shouldReplace: [&](OpOperand &opOperand) {
211 return outlinedFunc->isProperAncestor(other: opOperand.getOwner());
212 });
213 }
214
215 return outlinedFunc;
216}
217
218LogicalResult mlir::outlineIfOp(RewriterBase &b, scf::IfOp ifOp,
219 func::FuncOp *thenFn, StringRef thenFnName,
220 func::FuncOp *elseFn, StringRef elseFnName) {
221 IRRewriter rewriter(b);
222 Location loc = ifOp.getLoc();
223 FailureOr<func::FuncOp> outlinedFuncOpOrFailure;
224 if (thenFn && !ifOp.getThenRegion().empty()) {
225 outlinedFuncOpOrFailure = outlineSingleBlockRegion(
226 rewriter, loc, region&: ifOp.getThenRegion(), funcName: thenFnName);
227 if (failed(Result: outlinedFuncOpOrFailure))
228 return failure();
229 *thenFn = *outlinedFuncOpOrFailure;
230 }
231 if (elseFn && !ifOp.getElseRegion().empty()) {
232 outlinedFuncOpOrFailure = outlineSingleBlockRegion(
233 rewriter, loc, region&: ifOp.getElseRegion(), funcName: elseFnName);
234 if (failed(Result: outlinedFuncOpOrFailure))
235 return failure();
236 *elseFn = *outlinedFuncOpOrFailure;
237 }
238 return success();
239}
240
241bool mlir::getInnermostParallelLoops(Operation *rootOp,
242 SmallVectorImpl<scf::ParallelOp> &result) {
243 assert(rootOp != nullptr && "Root operation must not be a nullptr.");
244 bool rootEnclosesPloops = false;
245 for (Region &region : rootOp->getRegions()) {
246 for (Block &block : region.getBlocks()) {
247 for (Operation &op : block) {
248 bool enclosesPloops = getInnermostParallelLoops(rootOp: &op, result);
249 rootEnclosesPloops |= enclosesPloops;
250 if (auto ploop = dyn_cast<scf::ParallelOp>(Val&: op)) {
251 rootEnclosesPloops = true;
252
253 // Collect parallel loop if it is an innermost one.
254 if (!enclosesPloops)
255 result.push_back(Elt: ploop);
256 }
257 }
258 }
259 }
260 return rootEnclosesPloops;
261}
262
263// Build the IR that performs ceil division of a positive value by a constant:
264// ceildiv(a, B) = divis(a + (B-1), B)
265// where divis is rounding-to-zero division.
266static Value ceilDivPositive(OpBuilder &builder, Location loc, Value dividend,
267 int64_t divisor) {
268 assert(divisor > 0 && "expected positive divisor");
269 assert(dividend.getType().isIntOrIndex() &&
270 "expected integer or index-typed value");
271
272 Value divisorMinusOneCst = arith::ConstantOp::create(
273 builder, location: loc, value: builder.getIntegerAttr(type: dividend.getType(), value: divisor - 1));
274 Value divisorCst = arith::ConstantOp::create(
275 builder, location: loc, value: builder.getIntegerAttr(type: dividend.getType(), value: divisor));
276 Value sum = arith::AddIOp::create(builder, location: loc, lhs: dividend, rhs: divisorMinusOneCst);
277 return arith::DivUIOp::create(builder, location: loc, lhs: sum, rhs: divisorCst);
278}
279
280// Build the IR that performs ceil division of a positive value by another
281// positive value:
282// ceildiv(a, b) = divis(a + (b - 1), b)
283// where divis is rounding-to-zero division.
284static Value ceilDivPositive(OpBuilder &builder, Location loc, Value dividend,
285 Value divisor) {
286 assert(dividend.getType().isIntOrIndex() &&
287 "expected integer or index-typed value");
288 Value cstOne = arith::ConstantOp::create(
289 builder, location: loc, value: builder.getOneAttr(type: dividend.getType()));
290 Value divisorMinusOne = arith::SubIOp::create(builder, location: loc, lhs: divisor, rhs: cstOne);
291 Value sum = arith::AddIOp::create(builder, location: loc, lhs: dividend, rhs: divisorMinusOne);
292 return arith::DivUIOp::create(builder, location: loc, lhs: sum, rhs: divisor);
293}
294
295void mlir::generateUnrolledLoop(
296 Block *loopBodyBlock, Value iv, uint64_t unrollFactor,
297 function_ref<Value(unsigned, Value, OpBuilder)> ivRemapFn,
298 function_ref<void(unsigned, Operation *, OpBuilder)> annotateFn,
299 ValueRange iterArgs, ValueRange yieldedValues,
300 IRMapping *clonedToSrcOpsMap) {
301
302 // Check if the op was cloned from another source op, and return it if found
303 // (or the same op if not found)
304 auto findOriginalSrcOp =
305 [](Operation *op, const IRMapping &clonedToSrcOpsMap) -> Operation * {
306 Operation *srcOp = op;
307 // If the source op derives from another op: traverse the chain to find the
308 // original source op
309 while (srcOp && clonedToSrcOpsMap.contains(from: srcOp))
310 srcOp = clonedToSrcOpsMap.lookup(from: srcOp);
311 return srcOp;
312 };
313
314 // Builder to insert unrolled bodies just before the terminator of the body of
315 // the loop.
316 auto builder = OpBuilder::atBlockTerminator(block: loopBodyBlock);
317
318 static const auto noopAnnotateFn = [](unsigned, Operation *, OpBuilder) {};
319 if (!annotateFn)
320 annotateFn = noopAnnotateFn;
321
322 // Keep a pointer to the last non-terminator operation in the original block
323 // so that we know what to clone (since we are doing this in-place).
324 Block::iterator srcBlockEnd = std::prev(x: loopBodyBlock->end(), n: 2);
325
326 // Unroll the contents of the loop body (append unrollFactor - 1 additional
327 // copies).
328 SmallVector<Value, 4> lastYielded(yieldedValues);
329
330 for (unsigned i = 1; i < unrollFactor; i++) {
331 // Prepare operand map.
332 IRMapping operandMap;
333 operandMap.map(from&: iterArgs, to&: lastYielded);
334
335 // If the induction variable is used, create a remapping to the value for
336 // this unrolled instance.
337 if (!iv.use_empty()) {
338 Value ivUnroll = ivRemapFn(i, iv, builder);
339 operandMap.map(from: iv, to: ivUnroll);
340 }
341
342 // Clone the original body of 'forOp'.
343 for (auto it = loopBodyBlock->begin(); it != std::next(x: srcBlockEnd); it++) {
344 Operation *srcOp = &(*it);
345 Operation *clonedOp = builder.clone(op&: *srcOp, mapper&: operandMap);
346 annotateFn(i, clonedOp, builder);
347 if (clonedToSrcOpsMap)
348 clonedToSrcOpsMap->map(from: clonedOp,
349 to: findOriginalSrcOp(srcOp, *clonedToSrcOpsMap));
350 }
351
352 // Update yielded values.
353 for (unsigned i = 0, e = lastYielded.size(); i < e; i++)
354 lastYielded[i] = operandMap.lookupOrDefault(from: yieldedValues[i]);
355 }
356
357 // Make sure we annotate the Ops in the original body. We do this last so that
358 // any annotations are not copied into the cloned Ops above.
359 for (auto it = loopBodyBlock->begin(); it != std::next(x: srcBlockEnd); it++)
360 annotateFn(0, &*it, builder);
361
362 // Update operands of the yield statement.
363 loopBodyBlock->getTerminator()->setOperands(lastYielded);
364}
365
366/// Splits `forOp` into two consecutive loops at `splitPoint`.
367FailureOr<std::pair<scf::ForOp, scf::ForOp>>
368mlir::splitForOpAtPoint(RewriterBase &rewriter, scf::ForOp forOp,
369 Value splitPoint) {
370 if (splitPoint.getType() != forOp.getLowerBound().getType())
371 return failure();
372
373 // Reject statically known violations of the split preconditions.
374 bool isUnsigned = forOp.getUnsignedCmp();
375 Value lbVal = forOp.getLowerBound();
376 Value ubVal = forOp.getUpperBound();
377 Value stepVal = forOp.getStep();
378 auto checkSplitPoint = [&](auto getBound) -> LogicalResult {
379 auto lb = getBound(lbVal);
380 auto ub = getBound(ubVal);
381 auto step = getBound(stepVal);
382 auto split = getBound(splitPoint);
383 if ((lb && split && *lb > *split) || (split && ub && *split >= *ub) ||
384 (step && *step <= 0))
385 return failure();
386 if (lb && step && split && (*split - *lb) % *step != 0)
387 return failure();
388 return success();
389 };
390 if (failed(Result: isUnsigned ? checkSplitPoint(getConstantUIntValue)
391 : checkSplitPoint(getConstantIntValue)))
392 return failure();
393
394 OpBuilder::InsertionGuard guard(rewriter);
395 rewriter.setInsertionPointAfter(forOp);
396 auto firstForOp = cast<scf::ForOp>(Val: rewriter.clone(op&: *forOp));
397 auto secondForOp = cast<scf::ForOp>(Val: rewriter.clone(op&: *forOp));
398 rewriter.modifyOpInPlace(root: firstForOp,
399 callable: [&] { firstForOp.setUpperBound(splitPoint); });
400 rewriter.modifyOpInPlace(root: secondForOp,
401 callable: [&] { secondForOp.setLowerBound(splitPoint); });
402
403 // Chain iter-args across the split:
404 // - `secondForOp` is initialized from `firstForOp`'s results.
405 // - Users of `forOp`'s results are redirected to `secondForOp`'s results,
406 // so downstream code observes the final carried values.
407 rewriter.modifyOpInPlace(root: secondForOp, callable: [&] {
408 secondForOp->setOperands(start: secondForOp.getNumControlOperands(),
409 length: secondForOp.getInitArgs().size(),
410 operands: firstForOp.getResults());
411 });
412 rewriter.replaceOp(op: forOp, newValues: secondForOp.getResults());
413
414 return std::pair<scf::ForOp, scf::ForOp>{firstForOp, secondForOp};
415}
416
417/// Unrolls 'forOp' by 'unrollFactor', returns the unrolled main loop and the
418/// epilogue loop, if the loop is unrolled.
419FailureOr<UnrolledLoopInfo> mlir::loopUnrollByFactor(
420 scf::ForOp forOp, uint64_t unrollFactor,
421 function_ref<void(unsigned, Operation *, OpBuilder)> annotateFn,
422 bool shouldPromoteIfSingleIteration) {
423 assert(unrollFactor > 0 && "expected positive unroll factor");
424
425 // Return if the loop body is empty.
426 if (llvm::hasSingleElement(C&: forOp.getBody()->getOperations()))
427 return UnrolledLoopInfo{.mainLoopOp: forOp, .epilogueLoopOp: std::nullopt};
428
429 // Compute tripCount = ceilDiv((upperBound - lowerBound), step) and populate
430 // 'upperBoundUnrolled' and 'stepUnrolled' for static and dynamic cases.
431 OpBuilder boundsBuilder(forOp);
432 IRRewriter rewriter(forOp.getContext());
433 auto loc = forOp.getLoc();
434 Value step = forOp.getStep();
435 Value upperBoundUnrolled;
436 Value stepUnrolled;
437 bool generateEpilogueLoop = true;
438
439 std::optional<APInt> constTripCount = forOp.getStaticTripCount();
440 // A static trip count does not imply constant bounds: it is also known when
441 // the lower and the upper bound are the same value (zero iterations), when
442 // the lower bound is zero and the upper bound is the step (one iteration),
443 // and when the upper bound is a constant offset from a non-constant lower
444 // bound. The computation below reads all three bounds as constants, so fall
445 // back to the dynamic case unless they are.
446 if (constTripCount && !(getConstantAPIntValue(ofr: forOp.getLowerBound()) &&
447 getConstantAPIntValue(ofr: forOp.getUpperBound()) &&
448 getConstantAPIntValue(ofr: step)))
449 constTripCount = std::nullopt;
450 if (constTripCount) {
451 // Constant loop bounds computation.
452 bool isUnsignedLoop = forOp.getUnsignedCmp();
453 // For unsigned loops, bounds must be zero-extended: narrow integer types
454 // (e.g. i1, i2, i3) may have bit patterns that are negative in a signed
455 // context (e.g., i1 value 1 has getSExtValue() == -1, getZExtValue() == 1).
456 // Zero-extension is only safe when the unsigned value fits in int64_t, i.e.
457 // the type's bitwidth is < 64. Bail out for 64-bit unsigned loops.
458 if (isUnsignedLoop) {
459 if (auto intTy = dyn_cast<IntegerType>(Val: forOp.getUpperBound().getType()))
460 if (intTy.getWidth() >= 64)
461 return failure();
462 }
463 auto getLoopBound = [&](Value v) -> int64_t {
464 auto apInt = getConstantAPIntValue(ofr: v);
465 assert(apInt && "expected constant loop bound");
466 return isUnsignedLoop ? static_cast<int64_t>(apInt->first.getZExtValue())
467 : apInt->first.getSExtValue();
468 };
469 int64_t lbCst = getLoopBound(forOp.getLowerBound());
470 int64_t ubCst = getLoopBound(forOp.getUpperBound());
471 int64_t stepCst = getLoopBound(step);
472 if (unrollFactor == 1) {
473 if (shouldPromoteIfSingleIteration && constTripCount->isOne() &&
474 failed(Result: forOp.promoteIfSingleIteration(rewriter)))
475 return failure();
476 return UnrolledLoopInfo{.mainLoopOp: forOp, .epilogueLoopOp: std::nullopt};
477 }
478
479 uint64_t tripCount = constTripCount->getZExtValue();
480 uint64_t tripCountEvenMultiple = tripCount - tripCount % unrollFactor;
481 int64_t upperBoundUnrolledCst = lbCst + tripCountEvenMultiple * stepCst;
482 int64_t stepUnrolledCst = stepCst * unrollFactor;
483
484 // Create constant for 'upperBoundUnrolled' and set epilogue loop flag.
485 generateEpilogueLoop = upperBoundUnrolledCst < ubCst;
486 if (generateEpilogueLoop)
487 upperBoundUnrolled = arith::ConstantOp::create(
488 builder&: boundsBuilder, location: loc,
489 value: boundsBuilder.getIntegerAttr(type: forOp.getUpperBound().getType(),
490 value: upperBoundUnrolledCst));
491 else
492 upperBoundUnrolled = forOp.getUpperBound();
493
494 // Create constant for 'stepUnrolled'. When the main loop has zero
495 // iterations (tripCountEvenMultiple == 0), keep the original step.
496 // stepCst * unrollFactor may produce a value that, when truncated to the
497 // bound type's bitwidth during IntegerAttr construction, wraps to zero; a
498 // zero step causes constantTripCount to return nullopt instead of 0, which
499 // prevents the zero-trip main loop from being elided.
500 bool mainLoopHasNoIter = (tripCountEvenMultiple == 0);
501 bool stepUnchanged = (stepCst == stepUnrolledCst);
502 stepUnrolled =
503 (mainLoopHasNoIter || stepUnchanged)
504 ? step
505 : arith::ConstantOp::create(builder&: boundsBuilder, location: loc,
506 value: boundsBuilder.getIntegerAttr(
507 type: step.getType(), value: stepUnrolledCst));
508 } else {
509 // Dynamic loop bounds computation.
510 // TODO: Add dynamic asserts for negative lb/ub/step, or
511 // consider using ceilDiv from AffineApplyExpander.
512 auto lowerBound = forOp.getLowerBound();
513 auto upperBound = forOp.getUpperBound();
514 Value diff =
515 arith::SubIOp::create(builder&: boundsBuilder, location: loc, lhs: upperBound, rhs: lowerBound);
516 Value zero = arith::ConstantOp::create(
517 builder&: boundsBuilder, location: loc, value: boundsBuilder.getZeroAttr(type: diff.getType()));
518 Value nonEmpty = arith::CmpIOp::create(builder&: boundsBuilder, location: loc,
519 predicate: forOp.getUnsignedCmp()
520 ? arith::CmpIPredicate::ult
521 : arith::CmpIPredicate::slt,
522 lhs: lowerBound, rhs: upperBound);
523 diff = arith::SelectOp::create(builder&: boundsBuilder, location: loc, condition: nonEmpty, true_value: diff, false_value: zero);
524
525 Value tripCount = ceilDivPositive(builder&: boundsBuilder, loc, dividend: diff, divisor: step);
526 Value unrollFactorCst = arith::ConstantOp::create(
527 builder&: boundsBuilder, location: loc,
528 value: boundsBuilder.getIntegerAttr(type: tripCount.getType(), value: unrollFactor));
529 Value tripCountRem =
530 arith::RemSIOp::create(builder&: boundsBuilder, location: loc, lhs: tripCount, rhs: unrollFactorCst);
531 // Compute tripCountEvenMultiple = tripCount - (tripCount % unrollFactor)
532 Value tripCountEvenMultiple =
533 arith::SubIOp::create(builder&: boundsBuilder, location: loc, lhs: tripCount, rhs: tripCountRem);
534 // Compute upperBoundUnrolled = UpperBound + tripCountEvenMultiple * step
535 upperBoundUnrolled = arith::AddIOp::create(
536 builder&: boundsBuilder, location: loc, lhs: lowerBound,
537 rhs: arith::MulIOp::create(builder&: boundsBuilder, location: loc, lhs: tripCountEvenMultiple, rhs: step));
538 // Compute stepUnrolled = step * unrollFactor
539 stepUnrolled =
540 arith::MulIOp::create(builder&: boundsBuilder, location: loc, lhs: step, rhs: unrollFactorCst);
541 }
542
543 UnrolledLoopInfo resultLoops;
544
545 // Create epilogue clean up loop starting at 'upperBoundUnrolled'.
546 if (generateEpilogueLoop) {
547 auto splitLoops = splitForOpAtPoint(rewriter, forOp, splitPoint: upperBoundUnrolled);
548 if (failed(Result: splitLoops))
549 return failure();
550 forOp = splitLoops->first;
551 scf::ForOp epilogueForOp = splitLoops->second;
552 if (!shouldPromoteIfSingleIteration ||
553 epilogueForOp.promoteIfSingleIteration(rewriter).failed())
554 resultLoops.epilogueLoopOp = epilogueForOp;
555 } else {
556 forOp.setUpperBound(upperBoundUnrolled);
557 }
558
559 // Create unrolled loop.
560 forOp.setStep(stepUnrolled);
561
562 auto iterArgs = ValueRange(forOp.getRegionIterArgs());
563 auto yieldedValues = forOp.getBody()->getTerminator()->getOperands();
564
565 generateUnrolledLoop(
566 loopBodyBlock: forOp.getBody(), iv: forOp.getInductionVar(), unrollFactor,
567 ivRemapFn: [&](unsigned i, Value iv, OpBuilder b) {
568 // iv' = iv + step * i;
569 auto stride = arith::MulIOp::create(
570 builder&: b, location: loc, lhs: step,
571 rhs: arith::ConstantOp::create(builder&: b, location: loc,
572 value: b.getIntegerAttr(type: iv.getType(), value: i)));
573 return arith::AddIOp::create(builder&: b, location: loc, lhs: iv, rhs: stride);
574 },
575 annotateFn, iterArgs, yieldedValues);
576 // Promote the loop body up if this has turned into a single iteration loop
577 // and `shouldPromoteIfSingleIteration` is true.
578 if (!shouldPromoteIfSingleIteration ||
579 forOp.promoteIfSingleIteration(rewriter).failed())
580 resultLoops.mainLoopOp = forOp;
581 return resultLoops;
582}
583
584/// Unrolls this loop completely.
585LogicalResult mlir::loopUnrollFull(scf::ForOp forOp) {
586 IRRewriter rewriter(forOp.getContext());
587 std::optional<APInt> mayBeConstantTripCount = forOp.getStaticTripCount();
588 if (!mayBeConstantTripCount.has_value())
589 return failure();
590 const APInt &tripCount = *mayBeConstantTripCount;
591 if (tripCount.isZero())
592 return success();
593 if (tripCount.isOne())
594 return forOp.promoteIfSingleIteration(rewriter);
595 return loopUnrollByFactor(forOp, unrollFactor: tripCount.getZExtValue());
596}
597
598/// Check if bounds of all inner loops are defined outside of `forOp`
599/// and return false if not.
600static bool areInnerBoundsInvariant(scf::ForOp forOp) {
601 auto walkResult = forOp.walk(callback: [&](scf::ForOp innerForOp) {
602 if (!forOp.isDefinedOutsideOfLoop(value: innerForOp.getLowerBound()) ||
603 !forOp.isDefinedOutsideOfLoop(value: innerForOp.getUpperBound()) ||
604 !forOp.isDefinedOutsideOfLoop(value: innerForOp.getStep()))
605 return WalkResult::interrupt();
606
607 return WalkResult::advance();
608 });
609 return !walkResult.wasInterrupted();
610}
611
612/// Unrolls and jams this loop by the specified factor.
613LogicalResult mlir::loopUnrollJamByFactor(scf::ForOp forOp,
614 uint64_t unrollJamFactor) {
615 assert(unrollJamFactor > 0 && "unroll jam factor should be positive");
616
617 if (unrollJamFactor == 1)
618 return success();
619
620 // If any control operand of any inner loop of `forOp` is defined within
621 // `forOp`, no unroll jam.
622 if (!areInnerBoundsInvariant(forOp)) {
623 LDBG() << "failed to unroll and jam: inner bounds are not invariant";
624 return failure();
625 }
626
627 // Currently, for operations with results are not supported.
628 if (forOp->getNumResults() > 0) {
629 LDBG() << "failed to unroll and jam: unsupported loop with results";
630 return failure();
631 }
632
633 // Currently, only constant trip count that divided by the unroll factor is
634 // supported.
635 std::optional<APInt> tripCount = forOp.getStaticTripCount();
636 if (!tripCount.has_value()) {
637 // If the trip count is dynamic, do not unroll & jam.
638 LDBG() << "failed to unroll and jam: trip count could not be determined";
639 return failure();
640 }
641 uint64_t tripCountValue = tripCount->getZExtValue();
642 if (tripCountValue == 0)
643 return success();
644 if (unrollJamFactor > tripCountValue) {
645 LDBG() << "unroll and jam factor is greater than trip count, set factor to "
646 "trip "
647 "count";
648 unrollJamFactor = tripCountValue;
649 } else if (tripCountValue % unrollJamFactor != 0) {
650 LDBG() << "failed to unroll and jam: unsupported trip count that is not a "
651 "multiple of unroll jam factor";
652 return failure();
653 }
654
655 // Nothing in the loop body other than the terminator.
656 if (llvm::hasSingleElement(C&: forOp.getBody()->getOperations()))
657 return success();
658
659 // Gather all sub-blocks to jam upon the loop being unrolled.
660 JamBlockGatherer<scf::ForOp> jbg;
661 jbg.walk(op: forOp);
662 auto &subBlocks = jbg.subBlocks;
663
664 // Collect inner loops.
665 SmallVector<scf::ForOp> innerLoops;
666 forOp.walk(callback: [&](scf::ForOp innerForOp) { innerLoops.push_back(Elt: innerForOp); });
667
668 // `operandMaps[i - 1]` carries old->new operand mapping for the ith unrolled
669 // iteration. There are (`unrollJamFactor` - 1) iterations.
670 SmallVector<IRMapping> operandMaps(unrollJamFactor - 1);
671
672 // For any loop with iter_args, replace it with a new loop that has
673 // `unrollJamFactor` copies of its iterOperands, iter_args and yield
674 // operands.
675 SmallVector<scf::ForOp> newInnerLoops;
676 IRRewriter rewriter(forOp.getContext());
677 for (scf::ForOp oldForOp : innerLoops) {
678 SmallVector<Value> dupIterOperands, dupYieldOperands;
679 ValueRange oldIterOperands = oldForOp.getInits();
680 ValueRange oldIterArgs = oldForOp.getRegionIterArgs();
681 ValueRange oldYieldOperands =
682 cast<scf::YieldOp>(Val: oldForOp.getBody()->getTerminator()).getOperands();
683 // Get additional iterOperands, iterArgs, and yield operands. We will
684 // fix iterOperands and yield operands after cloning of sub-blocks.
685 for (unsigned i = unrollJamFactor - 1; i >= 1; --i) {
686 dupIterOperands.append(in_start: oldIterOperands.begin(), in_end: oldIterOperands.end());
687 dupYieldOperands.append(in_start: oldYieldOperands.begin(), in_end: oldYieldOperands.end());
688 }
689 // Create a new loop with additional iterOperands, iter_args and yield
690 // operands. This new loop will take the loop body of the original loop.
691 bool forOpReplaced = oldForOp == forOp;
692 scf::ForOp newForOp =
693 cast<scf::ForOp>(Val: *oldForOp.replaceWithAdditionalYields(
694 rewriter, newInitOperands: dupIterOperands, /*replaceInitOperandUsesInLoop=*/false,
695 newYieldValuesFn: [&](OpBuilder &b, Location loc, ArrayRef<BlockArgument> newBbArgs) {
696 return dupYieldOperands;
697 }));
698 newInnerLoops.push_back(Elt: newForOp);
699 // `forOp` has been replaced with a new loop.
700 if (forOpReplaced)
701 forOp = newForOp;
702 // Update `operandMaps` for `newForOp` iterArgs and results.
703 ValueRange newIterArgs = newForOp.getRegionIterArgs();
704 unsigned oldNumIterArgs = oldIterArgs.size();
705 ValueRange newResults = newForOp.getResults();
706 unsigned oldNumResults = newResults.size() / unrollJamFactor;
707 assert(oldNumIterArgs == oldNumResults &&
708 "oldNumIterArgs must be the same as oldNumResults");
709 for (unsigned i = unrollJamFactor - 1; i >= 1; --i) {
710 for (unsigned j = 0; j < oldNumIterArgs; ++j) {
711 // `newForOp` has `unrollJamFactor` - 1 new sets of iterArgs and
712 // results. Update `operandMaps[i - 1]` to map old iterArgs and results
713 // to those in the `i`th new set.
714 operandMaps[i - 1].map(from: newIterArgs[j],
715 to: newIterArgs[i * oldNumIterArgs + j]);
716 operandMaps[i - 1].map(from: newResults[j],
717 to: newResults[i * oldNumResults + j]);
718 }
719 }
720 }
721
722 // Scale the step of loop being unroll-jammed by the unroll-jam factor.
723 rewriter.setInsertionPoint(forOp);
724 int64_t step = forOp.getConstantStep()->getSExtValue();
725 auto newStep = rewriter.createOrFold<arith::MulIOp>(
726 location: forOp.getLoc(), args: forOp.getStep(),
727 args: rewriter.createOrFold<arith::ConstantOp>(
728 location: forOp.getLoc(), args: rewriter.getIndexAttr(value: unrollJamFactor)));
729 forOp.setStep(newStep);
730 auto forOpIV = forOp.getInductionVar();
731
732 // Unroll and jam (appends unrollJamFactor - 1 additional copies).
733 for (unsigned i = unrollJamFactor - 1; i >= 1; --i) {
734 for (auto &subBlock : subBlocks) {
735 // Builder to insert unroll-jammed bodies. Insert right at the end of
736 // sub-block.
737 OpBuilder builder(subBlock.first->getBlock(), std::next(x: subBlock.second));
738
739 // If the induction variable is used, create a remapping to the value for
740 // this unrolled instance.
741 if (!forOpIV.use_empty()) {
742 // iv' = iv + i * step, i = 1 to unrollJamFactor-1.
743 auto ivTag = builder.createOrFold<arith::ConstantOp>(
744 location: forOp.getLoc(), args: builder.getIndexAttr(value: step * i));
745 auto ivUnroll =
746 builder.createOrFold<arith::AddIOp>(location: forOp.getLoc(), args&: forOpIV, args&: ivTag);
747 operandMaps[i - 1].map(from: forOpIV, to: ivUnroll);
748 }
749 // Clone the sub-block being unroll-jammed.
750 for (auto it = subBlock.first; it != std::next(x: subBlock.second); ++it)
751 builder.clone(op&: *it, mapper&: operandMaps[i - 1]);
752 }
753 // Fix iterOperands and yield op operands of newly created loops.
754 for (auto newForOp : newInnerLoops) {
755 unsigned oldNumIterOperands =
756 newForOp.getNumRegionIterArgs() / unrollJamFactor;
757 unsigned numControlOperands = newForOp.getNumControlOperands();
758 auto yieldOp = cast<scf::YieldOp>(Val: newForOp.getBody()->getTerminator());
759 unsigned oldNumYieldOperands = yieldOp.getNumOperands() / unrollJamFactor;
760 assert(oldNumIterOperands == oldNumYieldOperands &&
761 "oldNumIterOperands must be the same as oldNumYieldOperands");
762 for (unsigned j = 0; j < oldNumIterOperands; ++j) {
763 // The `i`th duplication of an old iterOperand or yield op operand
764 // needs to be replaced with a mapped value from `operandMaps[i - 1]`
765 // if such mapped value exists.
766 newForOp.setOperand(i: numControlOperands + i * oldNumIterOperands + j,
767 value: operandMaps[i - 1].lookupOrDefault(
768 from: newForOp.getOperand(i: numControlOperands + j)));
769 yieldOp.setOperand(
770 i: i * oldNumYieldOperands + j,
771 value: operandMaps[i - 1].lookupOrDefault(from: yieldOp.getOperand(i: j)));
772 }
773 }
774 }
775
776 // Promote the loop body up if this has turned into a single iteration loop.
777 (void)forOp.promoteIfSingleIteration(rewriter);
778 return success();
779}
780
781static Range emitNormalizedLoopBoundsForIndexType(RewriterBase &rewriter,
782 Location loc, OpFoldResult lb,
783 OpFoldResult ub,
784 OpFoldResult step) {
785 Range normalizedLoopBounds;
786 normalizedLoopBounds.offset = rewriter.getIndexAttr(value: 0);
787 normalizedLoopBounds.stride = rewriter.getIndexAttr(value: 1);
788 AffineExpr s0, s1, s2;
789 bindSymbols(ctx: rewriter.getContext(), exprs&: s0, exprs&: s1, exprs&: s2);
790 AffineExpr e = (s1 - s0).ceilDiv(other: s2);
791 normalizedLoopBounds.size =
792 affine::makeComposedFoldedAffineApply(b&: rewriter, loc, expr: e, operands: {lb, ub, step});
793 return normalizedLoopBounds;
794}
795
796Range mlir::emitNormalizedLoopBounds(RewriterBase &rewriter, Location loc,
797 OpFoldResult lb, OpFoldResult ub,
798 OpFoldResult step) {
799 if (getType(ofr: lb).isIndex()) {
800 return emitNormalizedLoopBoundsForIndexType(rewriter, loc, lb, ub, step);
801 }
802 // For non-index types, generate `arith` instructions
803 // Check if the loop is already known to have a constant zero lower bound or
804 // a constant one step.
805 bool isZeroBased = false;
806 if (auto lbCst = getConstantIntValue(ofr: lb))
807 isZeroBased = lbCst.value() == 0;
808
809 bool isStepOne = false;
810 if (auto stepCst = getConstantIntValue(ofr: step))
811 isStepOne = stepCst.value() == 1;
812
813 Type rangeType = getType(ofr: lb);
814 assert(rangeType == getType(ub) && rangeType == getType(step) &&
815 "expected matching types");
816
817 // Compute the number of iterations the loop executes: ceildiv(ub - lb, step)
818 // assuming the step is strictly positive. Update the bounds and the step
819 // of the loop to go from 0 to the number of iterations, if necessary.
820 if (isZeroBased && isStepOne)
821 return {.offset: lb, .size: ub, .stride: step};
822
823 OpFoldResult diff = ub;
824 if (!isZeroBased) {
825 diff = rewriter.createOrFold<arith::SubIOp>(
826 location: loc, args: getValueOrCreateConstantIntOp(b&: rewriter, loc, ofr: ub),
827 args: getValueOrCreateConstantIntOp(b&: rewriter, loc, ofr: lb));
828 }
829 OpFoldResult newUpperBound = diff;
830 if (!isStepOne) {
831 newUpperBound = rewriter.createOrFold<arith::CeilDivSIOp>(
832 location: loc, args: getValueOrCreateConstantIntOp(b&: rewriter, loc, ofr: diff),
833 args: getValueOrCreateConstantIntOp(b&: rewriter, loc, ofr: step));
834 }
835
836 OpFoldResult newLowerBound = rewriter.getZeroAttr(type: rangeType);
837 OpFoldResult newStep = rewriter.getOneAttr(type: rangeType);
838
839 return {.offset: newLowerBound, .size: newUpperBound, .stride: newStep};
840}
841
842static void denormalizeInductionVariableForIndexType(RewriterBase &rewriter,
843 Location loc,
844 Value normalizedIv,
845 OpFoldResult origLb,
846 OpFoldResult origStep) {
847 AffineExpr d0, s0, s1;
848 bindSymbols(ctx: rewriter.getContext(), exprs&: s0, exprs&: s1);
849 bindDims(ctx: rewriter.getContext(), exprs&: d0);
850 AffineExpr e = d0 * s1 + s0;
851 OpFoldResult denormalizedIv = affine::makeComposedFoldedAffineApply(
852 b&: rewriter, loc, expr: e, operands: ArrayRef<OpFoldResult>{normalizedIv, origLb, origStep});
853 Value denormalizedIvVal =
854 getValueOrCreateConstantIndexOp(b&: rewriter, loc, ofr: denormalizedIv);
855 SmallPtrSet<Operation *, 1> preservedUses;
856 // If an `affine.apply` operation is generated for denormalization, the use
857 // of `origLb` in those ops must not be replaced. These arent not generated
858 // when `origLb == 0` and `origStep == 1`.
859 if (!isZeroInteger(v: origLb) || !isOneInteger(v: origStep)) {
860 if (Operation *preservedUse = denormalizedIvVal.getDefiningOp()) {
861 preservedUses.insert(Ptr: preservedUse);
862 }
863 }
864 rewriter.replaceAllUsesExcept(from: normalizedIv, to: denormalizedIvVal, preservedUsers: preservedUses);
865}
866
867void mlir::denormalizeInductionVariable(RewriterBase &rewriter, Location loc,
868 Value normalizedIv, OpFoldResult origLb,
869 OpFoldResult origStep) {
870 if (getType(ofr: origLb).isIndex()) {
871 return denormalizeInductionVariableForIndexType(rewriter, loc, normalizedIv,
872 origLb, origStep);
873 }
874 Value denormalizedIv;
875 SmallPtrSet<Operation *, 2> preserve;
876 bool isStepOne = isOneInteger(v: origStep);
877 bool isZeroBased = isZeroInteger(v: origLb);
878
879 Value scaled = normalizedIv;
880 if (!isStepOne) {
881 Value origStepValue =
882 getValueOrCreateConstantIntOp(b&: rewriter, loc, ofr: origStep);
883 scaled = arith::MulIOp::create(builder&: rewriter, location: loc, lhs: normalizedIv, rhs: origStepValue);
884 preserve.insert(Ptr: scaled.getDefiningOp());
885 }
886 denormalizedIv = scaled;
887 if (!isZeroBased) {
888 Value origLbValue = getValueOrCreateConstantIntOp(b&: rewriter, loc, ofr: origLb);
889 denormalizedIv = arith::AddIOp::create(builder&: rewriter, location: loc, lhs: scaled, rhs: origLbValue);
890 preserve.insert(Ptr: denormalizedIv.getDefiningOp());
891 }
892
893 rewriter.replaceAllUsesExcept(from: normalizedIv, to: denormalizedIv, preservedUsers: preserve);
894}
895
896static OpFoldResult getProductOfIndexes(RewriterBase &rewriter, Location loc,
897 ArrayRef<OpFoldResult> values) {
898 assert(!values.empty() && "unexecpted empty array");
899 AffineExpr s0, s1;
900 bindSymbols(ctx: rewriter.getContext(), exprs&: s0, exprs&: s1);
901 AffineExpr mul = s0 * s1;
902 OpFoldResult products = rewriter.getIndexAttr(value: 1);
903 for (auto v : values) {
904 products = affine::makeComposedFoldedAffineApply(
905 b&: rewriter, loc, expr: mul, operands: ArrayRef<OpFoldResult>{products, v});
906 }
907 return products;
908}
909
910/// Helper function to multiply a sequence of values.
911static Value getProductOfIntsOrIndexes(RewriterBase &rewriter, Location loc,
912 ArrayRef<Value> values) {
913 assert(!values.empty() && "unexpected empty list");
914 if (getType(ofr: values.front()).isIndex()) {
915 SmallVector<OpFoldResult> ofrs = getAsOpFoldResult(values);
916 OpFoldResult product = getProductOfIndexes(rewriter, loc, values: ofrs);
917 return getValueOrCreateConstantIndexOp(b&: rewriter, loc, ofr: product);
918 }
919 std::optional<Value> productOf;
920 for (auto v : values) {
921 auto vOne = getConstantIntValue(ofr: v);
922 if (vOne && vOne.value() == 1)
923 continue;
924 if (productOf)
925 productOf = arith::MulIOp::create(builder&: rewriter, location: loc, lhs: productOf.value(), rhs: v)
926 .getResult();
927 else
928 productOf = v;
929 }
930 if (!productOf) {
931 productOf = arith::ConstantOp::create(
932 builder&: rewriter, location: loc, value: rewriter.getOneAttr(type: getType(ofr: values.front())))
933 .getResult();
934 }
935 return productOf.value();
936}
937
938/// For each original loop, the value of the
939/// induction variable can be obtained by dividing the induction variable of
940/// the linearized loop by the total number of iterations of the loops nested
941/// in it modulo the number of iterations in this loop (remove the values
942/// related to the outer loops):
943/// iv_i = floordiv(iv_linear, product-of-loop-ranges-until-i) mod range_i.
944/// Compute these iteratively from the innermost loop by creating a "running
945/// quotient" of division by the range.
946static std::pair<SmallVector<Value>, SmallPtrSet<Operation *, 2>>
947delinearizeInductionVariable(RewriterBase &rewriter, Location loc,
948 Value linearizedIv, ArrayRef<Value> ubs) {
949
950 if (linearizedIv.getType().isIndex()) {
951 Operation *delinearizedOp = affine::AffineDelinearizeIndexOp::create(
952 builder&: rewriter, location: loc, linear_index: linearizedIv, basis: ubs);
953 auto resultVals = llvm::map_to_vector(
954 C: delinearizedOp->getResults(), F: [](OpResult r) -> Value { return r; });
955 return {resultVals, SmallPtrSet<Operation *, 2>{delinearizedOp}};
956 }
957
958 SmallVector<Value> delinearizedIvs(ubs.size());
959 SmallPtrSet<Operation *, 2> preservedUsers;
960
961 llvm::BitVector isUbOne(ubs.size());
962 for (auto [index, ub] : llvm::enumerate(First&: ubs)) {
963 auto ubCst = getConstantIntValue(ofr: ub);
964 if (ubCst && ubCst.value() == 1)
965 isUbOne.set(index);
966 }
967
968 // Prune the lead ubs that are all ones.
969 unsigned numLeadingOneUbs = 0;
970 for (auto [index, ub] : llvm::enumerate(First&: ubs)) {
971 if (!isUbOne.test(Idx: index)) {
972 break;
973 }
974 delinearizedIvs[index] = arith::ConstantOp::create(
975 builder&: rewriter, location: loc, value: rewriter.getZeroAttr(type: ub.getType()));
976 numLeadingOneUbs++;
977 }
978
979 Value previous = linearizedIv;
980 for (unsigned i = numLeadingOneUbs, e = ubs.size(); i < e; ++i) {
981 unsigned idx = ubs.size() - (i - numLeadingOneUbs) - 1;
982 if (i != numLeadingOneUbs && !isUbOne.test(Idx: idx + 1)) {
983 previous = arith::DivSIOp::create(builder&: rewriter, location: loc, lhs: previous, rhs: ubs[idx + 1]);
984 preservedUsers.insert(Ptr: previous.getDefiningOp());
985 }
986 Value iv = previous;
987 if (i != e - 1) {
988 if (!isUbOne.test(Idx: idx)) {
989 iv = arith::RemSIOp::create(builder&: rewriter, location: loc, lhs: previous, rhs: ubs[idx]);
990 preservedUsers.insert(Ptr: iv.getDefiningOp());
991 } else {
992 iv = arith::ConstantOp::create(
993 builder&: rewriter, location: loc, value: rewriter.getZeroAttr(type: ubs[idx].getType()));
994 }
995 }
996 delinearizedIvs[idx] = iv;
997 }
998 return {delinearizedIvs, preservedUsers};
999}
1000
1001LogicalResult mlir::coalesceLoops(RewriterBase &rewriter,
1002 MutableArrayRef<scf::ForOp> loops) {
1003 if (loops.size() < 2)
1004 return failure();
1005
1006 scf::ForOp innermost = loops.back();
1007 scf::ForOp outermost = loops.front();
1008
1009 // Bail out if any loop has a known zero step, as normalization
1010 // would result in a division by zero.
1011 for (auto loop : loops) {
1012 if (auto step = getConstantIntValue(ofr: loop.getStep())) {
1013 if (step.value() == 0) {
1014 return failure();
1015 }
1016 }
1017 }
1018 // 1. Make sure all loops iterate from 0 to upperBound with step 1. This
1019 // allows the following code to assume upperBound is the number of iterations.
1020 for (auto loop : loops) {
1021 OpBuilder::InsertionGuard g(rewriter);
1022 rewriter.setInsertionPoint(outermost);
1023 Value lb = loop.getLowerBound();
1024 Value ub = loop.getUpperBound();
1025 Value step = loop.getStep();
1026 auto newLoopRange =
1027 emitNormalizedLoopBounds(rewriter, loc: loop.getLoc(), lb, ub, step);
1028
1029 rewriter.modifyOpInPlace(root: loop, callable: [&]() {
1030 loop.setLowerBound(getValueOrCreateConstantIntOp(b&: rewriter, loc: loop.getLoc(),
1031 ofr: newLoopRange.offset));
1032 loop.setUpperBound(getValueOrCreateConstantIntOp(b&: rewriter, loc: loop.getLoc(),
1033 ofr: newLoopRange.size));
1034 loop.setStep(getValueOrCreateConstantIntOp(b&: rewriter, loc: loop.getLoc(),
1035 ofr: newLoopRange.stride));
1036 });
1037 rewriter.setInsertionPointToStart(innermost.getBody());
1038 denormalizeInductionVariable(rewriter, loc: loop.getLoc(),
1039 normalizedIv: loop.getInductionVar(), origLb: lb, origStep: step);
1040 }
1041
1042 // 2. Emit code computing the upper bound of the coalesced loop as product
1043 // of the number of iterations of all loops.
1044 OpBuilder::InsertionGuard g(rewriter);
1045 rewriter.setInsertionPoint(outermost);
1046 Location loc = outermost.getLoc();
1047 SmallVector<Value> upperBounds = llvm::map_to_vector(
1048 C&: loops, F: [](auto loop) { return loop.getUpperBound(); });
1049 Value upperBound = getProductOfIntsOrIndexes(rewriter, loc, values: upperBounds);
1050 outermost.setUpperBound(upperBound);
1051
1052 // Insert delinearization at the start of the outermost loop body.
1053 rewriter.setInsertionPointToStart(outermost.getBody());
1054 auto [delinearizeIvs, preservedUsers] = delinearizeInductionVariable(
1055 rewriter, loc, linearizedIv: outermost.getInductionVar(), ubs: upperBounds);
1056 rewriter.replaceAllUsesExcept(from: outermost.getInductionVar(), to: delinearizeIvs[0],
1057 preservedUsers);
1058
1059 for (int i = loops.size() - 1; i > 0; --i) {
1060 auto outerLoop = loops[i - 1];
1061 auto innerLoop = loops[i];
1062
1063 Operation *innerTerminator = innerLoop.getBody()->getTerminator();
1064 auto yieldedVals = llvm::to_vector(Range: innerTerminator->getOperands());
1065 assert(llvm::equal(outerLoop.getRegionIterArgs(), innerLoop.getInitArgs()));
1066 for (Value &yieldedVal : yieldedVals) {
1067 // The yielded value may be the induction variable of the inner loop,
1068 // which is about to be inlined and whose block argument is about to
1069 // be destroyed. Use its replacement value instead.
1070 if (yieldedVal == innerLoop.getInductionVar()) {
1071 yieldedVal = delinearizeIvs[i];
1072 continue;
1073 }
1074 // The yielded value may be an iteration argument of the inner loop
1075 // which is about to be inlined.
1076 auto iter = llvm::find(Range: innerLoop.getRegionIterArgs(), Val: yieldedVal);
1077 if (iter != innerLoop.getRegionIterArgs().end()) {
1078 unsigned iterArgIndex = iter - innerLoop.getRegionIterArgs().begin();
1079 // `outerLoop` iter args identical to the `innerLoop` init args.
1080 assert(iterArgIndex < innerLoop.getInitArgs().size());
1081 yieldedVal = innerLoop.getInitArgs()[iterArgIndex];
1082 }
1083 }
1084 rewriter.eraseOp(op: innerTerminator);
1085
1086 SmallVector<Value> innerBlockArgs;
1087 innerBlockArgs.push_back(Elt: delinearizeIvs[i]);
1088 llvm::append_range(C&: innerBlockArgs, R: outerLoop.getRegionIterArgs());
1089 rewriter.inlineBlockBefore(source: innerLoop.getBody(), dest: outerLoop.getBody(),
1090 before: Block::iterator(innerLoop), argValues: innerBlockArgs);
1091 rewriter.replaceOp(op: innerLoop, newValues: yieldedVals);
1092 }
1093 return success();
1094}
1095
1096LogicalResult mlir::coalesceLoops(MutableArrayRef<scf::ForOp> loops) {
1097 if (loops.empty()) {
1098 return failure();
1099 }
1100 IRRewriter rewriter(loops.front().getContext());
1101 return coalesceLoops(rewriter, loops);
1102}
1103
1104LogicalResult mlir::coalescePerfectlyNestedSCFForLoops(scf::ForOp op) {
1105 LogicalResult result(failure());
1106 SmallVector<scf::ForOp> loops;
1107 getPerfectlyNestedLoops(nestedLoops&: loops, root: op);
1108
1109 // Look for a band of loops that can be coalesced, i.e. perfectly nested
1110 // loops with bounds defined above some loop.
1111
1112 // 1. For each loop, find above which parent loop its bounds operands are
1113 // defined.
1114 SmallVector<unsigned> operandsDefinedAbove(loops.size());
1115 for (unsigned i = 0, e = loops.size(); i < e; ++i) {
1116 operandsDefinedAbove[i] = i;
1117 for (unsigned j = 0; j < i; ++j) {
1118 SmallVector<Value> boundsOperands = {loops[i].getLowerBound(),
1119 loops[i].getUpperBound(),
1120 loops[i].getStep()};
1121 if (areValuesDefinedAbove(values: boundsOperands, limit&: loops[j].getRegion())) {
1122 operandsDefinedAbove[i] = j;
1123 break;
1124 }
1125 }
1126 }
1127
1128 // 2. For each inner loop check that the iter_args for the immediately outer
1129 // loop are the init for the immediately inner loop and that the yields of the
1130 // return of the inner loop is the yield for the immediately outer loop. Keep
1131 // track of where the chain starts from for each loop.
1132 SmallVector<unsigned> iterArgChainStart(loops.size());
1133 iterArgChainStart[0] = 0;
1134 for (unsigned i = 1, e = loops.size(); i < e; ++i) {
1135 // By default set the start of the chain to itself.
1136 iterArgChainStart[i] = i;
1137 auto outerloop = loops[i - 1];
1138 auto innerLoop = loops[i];
1139 if (outerloop.getNumRegionIterArgs() != innerLoop.getNumRegionIterArgs()) {
1140 continue;
1141 }
1142 if (!llvm::equal(LRange: outerloop.getRegionIterArgs(), RRange: innerLoop.getInitArgs())) {
1143 continue;
1144 }
1145 auto outerloopTerminator = outerloop.getBody()->getTerminator();
1146 if (!llvm::equal(LRange: outerloopTerminator->getOperands(),
1147 RRange: innerLoop.getResults())) {
1148 continue;
1149 }
1150 iterArgChainStart[i] = iterArgChainStart[i - 1];
1151 }
1152
1153 // 3. Identify bands of loops such that the operands of all of them are
1154 // defined above the first loop in the band. Traverse the nest bottom-up
1155 // so that modifications don't invalidate the inner loops.
1156 for (unsigned end = loops.size(); end > 0; --end) {
1157 unsigned start = 0;
1158 for (; start < end - 1; ++start) {
1159 auto maxPos =
1160 *std::max_element(first: std::next(x: operandsDefinedAbove.begin(), n: start),
1161 last: std::next(x: operandsDefinedAbove.begin(), n: end));
1162 if (maxPos > start)
1163 continue;
1164 if (iterArgChainStart[end - 1] > start)
1165 continue;
1166 auto band = llvm::MutableArrayRef(loops.data() + start, end - start);
1167 if (succeeded(Result: coalesceLoops(loops: band)))
1168 result = success();
1169 break;
1170 }
1171 // If a band was found and transformed, keep looking at the loops above
1172 // the outermost transformed loop.
1173 if (start != end - 1)
1174 end = start + 1;
1175 }
1176 return result;
1177}
1178
1179void mlir::collapseParallelLoops(
1180 RewriterBase &rewriter, scf::ParallelOp loops,
1181 ArrayRef<std::vector<unsigned>> combinedDimensions) {
1182 OpBuilder::InsertionGuard g(rewriter);
1183 rewriter.setInsertionPoint(loops);
1184 Location loc = loops.getLoc();
1185
1186 // Presort combined dimensions.
1187 auto sortedDimensions = llvm::to_vector<3>(Range&: combinedDimensions);
1188 for (auto &dims : sortedDimensions)
1189 llvm::sort(C&: dims);
1190
1191 // Normalize ParallelOp's iteration pattern.
1192 SmallVector<Value, 3> normalizedUpperBounds;
1193 for (unsigned i = 0, e = loops.getNumLoops(); i < e; ++i) {
1194 OpBuilder::InsertionGuard g2(rewriter);
1195 rewriter.setInsertionPoint(loops);
1196 Value lb = loops.getLowerBound()[i];
1197 Value ub = loops.getUpperBound()[i];
1198 Value step = loops.getStep()[i];
1199 auto newLoopRange = emitNormalizedLoopBounds(rewriter, loc, lb, ub, step);
1200 normalizedUpperBounds.push_back(Elt: getValueOrCreateConstantIntOp(
1201 b&: rewriter, loc: loops.getLoc(), ofr: newLoopRange.size));
1202
1203 rewriter.setInsertionPointToStart(loops.getBody());
1204 denormalizeInductionVariable(rewriter, loc, normalizedIv: loops.getInductionVars()[i], origLb: lb,
1205 origStep: step);
1206 }
1207
1208 // Combine iteration spaces.
1209 SmallVector<Value, 3> lowerBounds, upperBounds, steps;
1210 auto cst0 = arith::ConstantIndexOp::create(builder&: rewriter, location: loc, value: 0);
1211 auto cst1 = arith::ConstantIndexOp::create(builder&: rewriter, location: loc, value: 1);
1212 for (auto &sortedDimension : sortedDimensions) {
1213 Value newUpperBound = arith::ConstantIndexOp::create(builder&: rewriter, location: loc, value: 1);
1214 for (auto idx : sortedDimension) {
1215 newUpperBound = arith::MulIOp::create(builder&: rewriter, location: loc, lhs: newUpperBound,
1216 rhs: normalizedUpperBounds[idx]);
1217 }
1218 lowerBounds.push_back(Elt: cst0);
1219 steps.push_back(Elt: cst1);
1220 upperBounds.push_back(Elt: newUpperBound);
1221 }
1222
1223 // Create new ParallelLoop with conversions to the original induction values.
1224 // The loop below uses divisions to get the relevant range of values in the
1225 // new induction value that represent each range of the original induction
1226 // value. The remainders then determine based on that range, which iteration
1227 // of the original induction value this represents. This is a normalized value
1228 // that is un-normalized already by the previous logic.
1229 auto newPloop = scf::ParallelOp::create(
1230 builder&: rewriter, location: loc, lowerBounds, upperBounds, steps,
1231 bodyBuilderFn: [&](OpBuilder &insideBuilder, Location, ValueRange ploopIVs) {
1232 for (unsigned i = 0, e = combinedDimensions.size(); i < e; ++i) {
1233 Value previous = ploopIVs[i];
1234 unsigned numberCombinedDimensions = combinedDimensions[i].size();
1235 // Iterate over all except the last induction value.
1236 for (unsigned j = numberCombinedDimensions - 1; j > 0; --j) {
1237 unsigned idx = combinedDimensions[i][j];
1238
1239 // Determine the current induction value's current loop iteration
1240 Value iv = arith::RemSIOp::create(builder&: insideBuilder, location: loc, lhs: previous,
1241 rhs: normalizedUpperBounds[idx]);
1242 replaceAllUsesInRegionWith(orig: loops.getBody()->getArgument(i: idx), replacement: iv,
1243 region&: loops.getRegion());
1244
1245 // Remove the effect of the current induction value to prepare for
1246 // the next value.
1247 previous = arith::DivSIOp::create(builder&: insideBuilder, location: loc, lhs: previous,
1248 rhs: normalizedUpperBounds[idx]);
1249 }
1250
1251 // The final induction value is just the remaining value.
1252 unsigned idx = combinedDimensions[i][0];
1253 replaceAllUsesInRegionWith(orig: loops.getBody()->getArgument(i: idx),
1254 replacement: previous, region&: loops.getRegion());
1255 }
1256 });
1257
1258 // Replace the old loop with the new loop.
1259 loops.getBody()->back().erase();
1260 newPloop.getBody()->getOperations().splice(
1261 where: Block::iterator(newPloop.getBody()->back()),
1262 L2&: loops.getBody()->getOperations());
1263 loops.erase();
1264}
1265
1266// Hoist the ops within `outer` that appear before `inner`.
1267// Such ops include the ops that have been introduced by parametric tiling.
1268// Ops that come from triangular loops (i.e. that belong to the program slice
1269// rooted at `outer`) and ops that have side effects cannot be hoisted.
1270// Return failure when any op fails to hoist.
1271static LogicalResult hoistOpsBetween(scf::ForOp outer, scf::ForOp inner) {
1272 SetVector<Operation *> forwardSlice;
1273 ForwardSliceOptions options;
1274 options.filter = [&inner](Operation *op) {
1275 return op != inner.getOperation();
1276 };
1277 getForwardSlice(root: outer.getInductionVar(), forwardSlice: &forwardSlice, options);
1278 LogicalResult status = success();
1279 SmallVector<Operation *, 8> toHoist;
1280 for (auto &op : outer.getBody()->without_terminator()) {
1281 // Stop when encountering the inner loop.
1282 if (&op == inner.getOperation())
1283 break;
1284 // Skip over non-hoistable ops.
1285 if (forwardSlice.count(key: &op) > 0) {
1286 status = failure();
1287 continue;
1288 }
1289 // Skip intermediate scf::ForOp, these are not considered a failure.
1290 if (isa<scf::ForOp>(Val: op))
1291 continue;
1292 // Skip other ops with regions.
1293 if (op.getNumRegions() > 0) {
1294 status = failure();
1295 continue;
1296 }
1297 // Skip if op has side effects.
1298 // TODO: loads to immutable memory regions are ok.
1299 if (!isMemoryEffectFree(op: &op)) {
1300 status = failure();
1301 continue;
1302 }
1303 toHoist.push_back(Elt: &op);
1304 }
1305 auto *outerForOp = outer.getOperation();
1306 for (auto *op : toHoist)
1307 op->moveBefore(existingOp: outerForOp);
1308 return status;
1309}
1310
1311// Traverse the interTile and intraTile loops and try to hoist ops such that
1312// bands of perfectly nested loops are isolated.
1313// Return failure if either perfect interTile or perfect intraTile bands cannot
1314// be formed.
1315static LogicalResult tryIsolateBands(const TileLoops &tileLoops) {
1316 LogicalResult status = success();
1317 const Loops &interTile = tileLoops.first;
1318 const Loops &intraTile = tileLoops.second;
1319 auto size = interTile.size();
1320 assert(size == intraTile.size());
1321 if (size <= 1)
1322 return success();
1323 for (unsigned s = 1; s < size; ++s)
1324 status = succeeded(Result: status) ? hoistOpsBetween(outer: intraTile[0], inner: intraTile[s])
1325 : failure();
1326 for (unsigned s = 1; s < size; ++s)
1327 status = succeeded(Result: status) ? hoistOpsBetween(outer: interTile[0], inner: interTile[s])
1328 : failure();
1329 return status;
1330}
1331
1332/// Collect perfectly nested loops starting from `rootForOps`. Loops are
1333/// perfectly nested if each loop is the first and only non-terminator operation
1334/// in the parent loop. Collect at most `maxLoops` loops and append them to
1335/// `forOps`.
1336template <typename T>
1337static void getPerfectlyNestedLoopsImpl(
1338 SmallVectorImpl<T> &forOps, T rootForOp,
1339 unsigned maxLoops = std::numeric_limits<unsigned>::max()) {
1340 for (unsigned i = 0; i < maxLoops; ++i) {
1341 forOps.push_back(rootForOp);
1342 Block &body = rootForOp.getRegion().front();
1343 if (body.begin() != std::prev(x: body.end(), n: 2))
1344 return;
1345
1346 rootForOp = dyn_cast<T>(&body.front());
1347 if (!rootForOp)
1348 return;
1349 }
1350}
1351
1352static Loops stripmineSink(scf::ForOp forOp, Value factor,
1353 ArrayRef<scf::ForOp> targets) {
1354 auto originalStep = forOp.getStep();
1355 auto iv = forOp.getInductionVar();
1356 bool isUnsigned = forOp.getUnsignedCmp();
1357
1358 OpBuilder b(forOp);
1359 forOp.setStep(arith::MulIOp::create(builder&: b, location: forOp.getLoc(), lhs: originalStep, rhs: factor));
1360
1361 Loops innerLoops;
1362 for (auto t : targets) {
1363 // Save information for splicing ops out of t when done
1364 auto begin = t.getBody()->begin();
1365 auto nOps = t.getBody()->getOperations().size();
1366
1367 // Insert newForOp before the terminator of `t`.
1368 auto b = OpBuilder::atBlockTerminator(block: (t.getBody()));
1369 Value stepped = arith::AddIOp::create(builder&: b, location: t.getLoc(), lhs: iv, rhs: forOp.getStep());
1370 Value ub;
1371 if (isUnsigned)
1372 ub =
1373 arith::MinUIOp::create(builder&: b, location: t.getLoc(), lhs: forOp.getUpperBound(), rhs: stepped);
1374 else
1375 ub =
1376 arith::MinSIOp::create(builder&: b, location: t.getLoc(), lhs: forOp.getUpperBound(), rhs: stepped);
1377
1378 // Splice [begin, begin + nOps - 1) into `newForOp` and replace uses.
1379 auto newForOp =
1380 scf::ForOp::create(builder&: b, location: t.getLoc(), lowerBound: iv, upperBound: ub, step: originalStep,
1381 /*initArgs=*/t.getRegionIterArgs(),
1382 /*bodyBuilder=*/odsArg4: nullptr, /*unsignedCmp=*/isUnsigned);
1383 newForOp.getBody()->getOperations().splice(
1384 where: newForOp.getBody()->getOperations().begin(),
1385 L2&: t.getBody()->getOperations(), first: begin, last: std::next(x: begin, n: nOps - 1));
1386 replaceAllUsesInRegionWith(orig: iv, replacement: newForOp.getInductionVar(),
1387 region&: newForOp.getRegion());
1388
1389 // Thread the iter_args of `t` through `newForOp`.
1390 if (!t.getInitArgs().empty()) {
1391 Operation *yieldOp = t.getBody()->getTerminator();
1392 yieldOp->moveBefore(block: newForOp.getBody(), iterator: newForOp.getBody()->end());
1393 for (auto [oldArg, newArg] :
1394 llvm::zip_equal(t: t.getRegionIterArgs(), u: newForOp.getRegionIterArgs()))
1395 replaceAllUsesInRegionWith(orig: oldArg, replacement: newArg, region&: newForOp.getRegion());
1396 b.setInsertionPointToEnd(t.getBody());
1397 scf::YieldOp::create(builder&: b, location: t.getLoc(), results: newForOp.getResults());
1398 }
1399
1400 innerLoops.push_back(Elt: newForOp);
1401 }
1402
1403 return innerLoops;
1404}
1405
1406SmallVector<Loops, 8> mlir::tile(ArrayRef<scf::ForOp> forOps,
1407 ArrayRef<Value> sizes,
1408 ArrayRef<scf::ForOp> targets) {
1409 SmallVector<SmallVector<scf::ForOp, 8>, 8> res;
1410 SmallVector<scf::ForOp, 8> currentTargets(targets);
1411 for (auto it : llvm::zip(t&: forOps, u&: sizes)) {
1412 auto step = stripmineSink(forOp: std::get<0>(t&: it), factor: std::get<1>(t&: it), targets: currentTargets);
1413 res.push_back(Elt: step);
1414 currentTargets = step;
1415 }
1416 return res;
1417}
1418
1419Loops mlir::tile(ArrayRef<scf::ForOp> forOps, ArrayRef<Value> sizes,
1420 scf::ForOp target) {
1421 SmallVector<scf::ForOp, 8> res;
1422 for (auto loops : tile(forOps, sizes, targets: ArrayRef<scf::ForOp>(target)))
1423 res.push_back(Elt: llvm::getSingleElement(C&: loops));
1424 return res;
1425}
1426
1427Loops mlir::tilePerfectlyNested(scf::ForOp rootForOp, ArrayRef<Value> sizes) {
1428 // Collect perfectly nested loops. If more size values provided than nested
1429 // loops available, truncate `sizes`.
1430 SmallVector<scf::ForOp, 4> forOps;
1431 forOps.reserve(N: sizes.size());
1432 getPerfectlyNestedLoopsImpl(forOps, rootForOp, maxLoops: sizes.size());
1433 if (forOps.size() < sizes.size())
1434 sizes = sizes.take_front(N: forOps.size());
1435
1436 return ::tile(forOps, sizes, target: forOps.back());
1437}
1438
1439void mlir::getPerfectlyNestedLoops(SmallVectorImpl<scf::ForOp> &nestedLoops,
1440 scf::ForOp root) {
1441 getPerfectlyNestedLoopsImpl(forOps&: nestedLoops, rootForOp: root);
1442}
1443
1444TileLoops mlir::extractFixedOuterLoops(scf::ForOp rootForOp,
1445 ArrayRef<int64_t> sizes) {
1446 // Collect perfectly nested loops. If more size values provided than nested
1447 // loops available, truncate `sizes`.
1448 SmallVector<scf::ForOp, 4> forOps;
1449 forOps.reserve(N: sizes.size());
1450 getPerfectlyNestedLoopsImpl(forOps, rootForOp, maxLoops: sizes.size());
1451 if (forOps.size() < sizes.size())
1452 sizes = sizes.take_front(N: forOps.size());
1453
1454 // Compute the tile sizes such that i-th outer loop executes size[i]
1455 // iterations. Given that the loop current executes
1456 // numIterations = ceildiv((upperBound - lowerBound), step)
1457 // iterations, we need to tile with size ceildiv(numIterations, size[i]).
1458 SmallVector<Value, 4> tileSizes;
1459 tileSizes.reserve(N: sizes.size());
1460 for (unsigned i = 0, e = sizes.size(); i < e; ++i) {
1461 assert(sizes[i] > 0 && "expected strictly positive size for strip-mining");
1462
1463 auto forOp = forOps[i];
1464 OpBuilder builder(forOp);
1465 auto loc = forOp.getLoc();
1466 Value diff = arith::SubIOp::create(builder, location: loc, lhs: forOp.getUpperBound(),
1467 rhs: forOp.getLowerBound());
1468 Value numIterations = ceilDivPositive(builder, loc, dividend: diff, divisor: forOp.getStep());
1469 Value iterationsPerBlock =
1470 ceilDivPositive(builder, loc, dividend: numIterations, divisor: sizes[i]);
1471 tileSizes.push_back(Elt: iterationsPerBlock);
1472 }
1473
1474 // Call parametric tiling with the given sizes.
1475 auto intraTile = tile(forOps, sizes: tileSizes, target: forOps.back());
1476 TileLoops tileLoops = std::make_pair(x&: forOps, y&: intraTile);
1477
1478 // TODO: for now we just ignore the result of band isolation.
1479 // In the future, mapping decisions may be impacted by the ability to
1480 // isolate perfectly nested bands.
1481 (void)tryIsolateBands(tileLoops);
1482
1483 return tileLoops;
1484}
1485
1486scf::ForallOp mlir::fuseIndependentSiblingForallLoops(scf::ForallOp target,
1487 scf::ForallOp source,
1488 RewriterBase &rewriter) {
1489 unsigned numTargetOuts = target.getNumResults();
1490 unsigned numSourceOuts = source.getNumResults();
1491
1492 // Create fused shared_outs.
1493 SmallVector<Value> fusedOuts;
1494 llvm::append_range(C&: fusedOuts, R: target.getOutputs());
1495 llvm::append_range(C&: fusedOuts, R: source.getOutputs());
1496
1497 // Create a new scf.forall op after the source loop.
1498 rewriter.setInsertionPointAfter(source);
1499 scf::ForallOp fusedLoop = scf::ForallOp::create(
1500 builder&: rewriter, location: source.getLoc(), lbs: source.getMixedLowerBound(),
1501 ubs: source.getMixedUpperBound(), steps: source.getMixedStep(), outputs: fusedOuts,
1502 mapping: source.getMapping());
1503
1504 // Map control operands.
1505 IRMapping mapping;
1506 mapping.map(from: target.getInductionVars(), to: fusedLoop.getInductionVars());
1507 mapping.map(from: source.getInductionVars(), to: fusedLoop.getInductionVars());
1508
1509 // Map shared outs.
1510 mapping.map(from: target.getRegionIterArgs(),
1511 to: fusedLoop.getRegionIterArgs().take_front(N: numTargetOuts));
1512 mapping.map(from: source.getRegionIterArgs(),
1513 to: fusedLoop.getRegionIterArgs().take_back(N: numSourceOuts));
1514
1515 // Append everything except the terminator into the fused operation.
1516 rewriter.setInsertionPointToStart(fusedLoop.getBody());
1517 for (Operation &op : target.getBody()->without_terminator())
1518 rewriter.clone(op, mapper&: mapping);
1519 for (Operation &op : source.getBody()->without_terminator())
1520 rewriter.clone(op, mapper&: mapping);
1521
1522 // Fuse the old terminator in_parallel ops into the new one.
1523 scf::InParallelOp targetTerm = target.getTerminator();
1524 scf::InParallelOp sourceTerm = source.getTerminator();
1525 scf::InParallelOp fusedTerm = fusedLoop.getTerminator();
1526 rewriter.setInsertionPointToStart(fusedTerm.getBody());
1527 for (Operation &op : targetTerm.getYieldingOps())
1528 rewriter.clone(op, mapper&: mapping);
1529 for (Operation &op : sourceTerm.getYieldingOps())
1530 rewriter.clone(op, mapper&: mapping);
1531
1532 // Replace old loops by substituting their uses by results of the fused loop.
1533 rewriter.replaceOp(op: target, newValues: fusedLoop.getResults().take_front(n: numTargetOuts));
1534 rewriter.replaceOp(op: source, newValues: fusedLoop.getResults().take_back(n: numSourceOuts));
1535
1536 return fusedLoop;
1537}
1538
1539scf::ForOp mlir::fuseIndependentSiblingForLoops(scf::ForOp target,
1540 scf::ForOp source,
1541 RewriterBase &rewriter) {
1542 assert(source.getUnsignedCmp() == target.getUnsignedCmp() &&
1543 "incompatible signedness");
1544 unsigned numTargetOuts = target.getNumResults();
1545 unsigned numSourceOuts = source.getNumResults();
1546
1547 // Create fused init_args, with target's init_args before source's init_args.
1548 SmallVector<Value> fusedInitArgs;
1549 llvm::append_range(C&: fusedInitArgs, R: target.getInitArgs());
1550 llvm::append_range(C&: fusedInitArgs, R: source.getInitArgs());
1551
1552 // Create a new scf.for op after the source loop (with scf.yield terminator
1553 // (without arguments) only in case its init_args is empty).
1554 rewriter.setInsertionPointAfter(source);
1555 scf::ForOp fusedLoop = scf::ForOp::create(
1556 builder&: rewriter, location: source.getLoc(), lowerBound: source.getLowerBound(), upperBound: source.getUpperBound(),
1557 step: source.getStep(), initArgs: fusedInitArgs, /*bodyBuilder=*/odsArg4: nullptr,
1558 unsignedCmp: source.getUnsignedCmp());
1559
1560 // Map original induction variables and operands to those of the fused loop.
1561 IRMapping mapping;
1562 mapping.map(from: target.getInductionVar(), to: fusedLoop.getInductionVar());
1563 mapping.map(from: target.getRegionIterArgs(),
1564 to: fusedLoop.getRegionIterArgs().take_front(N: numTargetOuts));
1565 mapping.map(from: source.getInductionVar(), to: fusedLoop.getInductionVar());
1566 mapping.map(from: source.getRegionIterArgs(),
1567 to: fusedLoop.getRegionIterArgs().take_back(N: numSourceOuts));
1568
1569 // Merge target's body into the new (fused) for loop and then source's body.
1570 rewriter.setInsertionPointToStart(fusedLoop.getBody());
1571 for (Operation &op : target.getBody()->without_terminator())
1572 rewriter.clone(op, mapper&: mapping);
1573 for (Operation &op : source.getBody()->without_terminator())
1574 rewriter.clone(op, mapper&: mapping);
1575
1576 // Build fused yield results by appropriately mapping original yield operands.
1577 SmallVector<Value> yieldResults;
1578 for (Value operand : target.getBody()->getTerminator()->getOperands())
1579 yieldResults.push_back(Elt: mapping.lookupOrDefault(from: operand));
1580 for (Value operand : source.getBody()->getTerminator()->getOperands())
1581 yieldResults.push_back(Elt: mapping.lookupOrDefault(from: operand));
1582 if (!yieldResults.empty())
1583 scf::YieldOp::create(builder&: rewriter, location: source.getLoc(), results: yieldResults);
1584
1585 // Replace old loops by substituting their uses by results of the fused loop.
1586 rewriter.replaceOp(op: target, newValues: fusedLoop.getResults().take_front(n: numTargetOuts));
1587 rewriter.replaceOp(op: source, newValues: fusedLoop.getResults().take_back(n: numSourceOuts));
1588
1589 return fusedLoop;
1590}
1591
1592FailureOr<scf::ForallOp> mlir::normalizeForallOp(RewriterBase &rewriter,
1593 scf::ForallOp forallOp) {
1594 SmallVector<OpFoldResult> lbs = forallOp.getMixedLowerBound();
1595 SmallVector<OpFoldResult> ubs = forallOp.getMixedUpperBound();
1596 SmallVector<OpFoldResult> steps = forallOp.getMixedStep();
1597
1598 if (forallOp.isNormalized())
1599 return forallOp;
1600
1601 OpBuilder::InsertionGuard g(rewriter);
1602 auto loc = forallOp.getLoc();
1603 rewriter.setInsertionPoint(forallOp);
1604 SmallVector<OpFoldResult> newUbs;
1605 for (auto [lb, ub, step] : llvm::zip_equal(t&: lbs, u&: ubs, args&: steps)) {
1606 Range normalizedLoopParams =
1607 emitNormalizedLoopBounds(rewriter, loc, lb, ub, step);
1608 newUbs.push_back(Elt: normalizedLoopParams.size);
1609 }
1610 (void)foldDynamicIndexList(ofrs&: newUbs);
1611
1612 // Use the normalized builder since the lower bounds are always 0 and the
1613 // steps are always 1.
1614 auto normalizedForallOp = scf::ForallOp::create(
1615 builder&: rewriter, location: loc, ubs: newUbs, outputs: forallOp.getOutputs(), mapping: forallOp.getMapping(),
1616 bodyBuilderFn: [](OpBuilder &, Location, ValueRange) {});
1617
1618 rewriter.inlineRegionBefore(region&: forallOp.getBodyRegion(),
1619 parent&: normalizedForallOp.getBodyRegion(),
1620 before: normalizedForallOp.getBodyRegion().begin());
1621 // Remove the original empty block in the new loop.
1622 rewriter.eraseBlock(block: &normalizedForallOp.getBodyRegion().back());
1623
1624 rewriter.setInsertionPointToStart(normalizedForallOp.getBody());
1625 // Update the users of the original loop variables.
1626 for (auto [idx, iv] :
1627 llvm::enumerate(First: normalizedForallOp.getInductionVars())) {
1628 auto origLb = getValueOrCreateConstantIndexOp(b&: rewriter, loc, ofr: lbs[idx]);
1629 auto origStep = getValueOrCreateConstantIndexOp(b&: rewriter, loc, ofr: steps[idx]);
1630 denormalizeInductionVariable(rewriter, loc, normalizedIv: iv, origLb, origStep);
1631 }
1632
1633 rewriter.replaceOp(op: forallOp, newOp: normalizedForallOp);
1634 return normalizedForallOp;
1635}
1636
1637bool mlir::isPerfectlyNestedForLoops(
1638 MutableArrayRef<LoopLikeOpInterface> loops) {
1639 assert(!loops.empty() && "unexpected empty loop nest");
1640 if (loops.size() == 1)
1641 return isa_and_nonnull<scf::ForOp>(Val: loops.front().getOperation());
1642 for (auto [outerLoop, innerLoop] :
1643 llvm::zip_equal(t: loops.drop_back(), u: loops.drop_front())) {
1644 auto outerFor = dyn_cast_or_null<scf::ForOp>(Val: outerLoop.getOperation());
1645 auto innerFor = dyn_cast_or_null<scf::ForOp>(Val: innerLoop.getOperation());
1646 if (!outerFor || !innerFor)
1647 return false;
1648 auto outerBBArgs = outerFor.getRegionIterArgs();
1649 auto innerIterArgs = innerFor.getInitArgs();
1650 if (outerBBArgs.size() != innerIterArgs.size())
1651 return false;
1652
1653 for (auto [outerBBArg, innerIterArg] :
1654 llvm::zip_equal(t&: outerBBArgs, u&: innerIterArgs)) {
1655 if (!llvm::hasSingleElement(C: outerBBArg.getUses()) ||
1656 innerIterArg != outerBBArg)
1657 return false;
1658 }
1659
1660 ValueRange outerYields =
1661 cast<scf::YieldOp>(Val: outerFor.getBody()->getTerminator())->getOperands();
1662 ValueRange innerResults = innerFor.getResults();
1663 if (outerYields.size() != innerResults.size())
1664 return false;
1665 for (auto [outerYield, innerResult] :
1666 llvm::zip_equal(t&: outerYields, u&: innerResults)) {
1667 if (!llvm::hasSingleElement(C: innerResult.getUses()) ||
1668 outerYield != innerResult)
1669 return false;
1670 }
1671 }
1672 return true;
1673}
1674
1675llvm::SmallVector<std::tuple<int64_t, int64_t, int64_t>>
1676mlir::getConstLoopBounds(mlir::LoopLikeOpInterface loopOp) {
1677 std::optional<SmallVector<OpFoldResult>> loBnds = loopOp.getLoopLowerBounds();
1678 std::optional<SmallVector<OpFoldResult>> upBnds = loopOp.getLoopUpperBounds();
1679 std::optional<SmallVector<OpFoldResult>> steps = loopOp.getLoopSteps();
1680 if (!loBnds || !upBnds || !steps)
1681 return {};
1682 llvm::SmallVector<std::tuple<int64_t, int64_t, int64_t>> loopRanges;
1683 for (auto [lb, ub, step] : llvm::zip(t&: *loBnds, u&: *upBnds, args&: *steps)) {
1684 auto lbCst = getConstantIntValue(ofr: lb);
1685 auto ubCst = getConstantIntValue(ofr: ub);
1686 auto stepCst = getConstantIntValue(ofr: step);
1687 if (!lbCst || !ubCst || !stepCst)
1688 return {};
1689 loopRanges.emplace_back(Args&: *lbCst, Args&: *ubCst, Args&: *stepCst);
1690 }
1691 return loopRanges;
1692}
1693
1694llvm::SmallVector<llvm::APInt>
1695mlir::getConstLoopTripCounts(mlir::LoopLikeOpInterface loopOp) {
1696 std::optional<SmallVector<OpFoldResult>> loBnds = loopOp.getLoopLowerBounds();
1697 std::optional<SmallVector<OpFoldResult>> upBnds = loopOp.getLoopUpperBounds();
1698 std::optional<SmallVector<OpFoldResult>> steps = loopOp.getLoopSteps();
1699 if (!loBnds || !upBnds || !steps)
1700 return {};
1701 llvm::SmallVector<llvm::APInt> tripCounts;
1702 for (auto [lb, ub, step] : llvm::zip(t&: *loBnds, u&: *upBnds, args&: *steps)) {
1703 // TODO(#178506): Signedness is not handled correctly here.
1704 std::optional<llvm::APInt> numIter = constantTripCount(
1705 lb, ub, step, /*isSigned=*/true, computeUbMinusLb: scf::computeUbMinusLb);
1706 if (!numIter)
1707 return {};
1708 tripCounts.push_back(Elt: *numIter);
1709 }
1710 return tripCounts;
1711}
1712
1713FailureOr<scf::ParallelOp> mlir::parallelLoopUnrollByFactors(
1714 scf::ParallelOp op, ArrayRef<uint64_t> unrollFactors,
1715 RewriterBase &rewriter,
1716 function_ref<void(unsigned, Operation *, OpBuilder)> annotateFn,
1717 IRMapping *clonedToSrcOpsMap) {
1718 const unsigned numLoops = op.getNumLoops();
1719 assert(llvm::none_of(unrollFactors, [](uint64_t f) { return f == 0; }) &&
1720 "Expected positive unroll factors");
1721 assert((!unrollFactors.empty() && (unrollFactors.size() <= numLoops)) &&
1722 "Expected non-empty unroll factors of size <= to the number of loops");
1723
1724 // Bail out if no valid unroll factors were provided
1725 if (llvm::all_of(Range&: unrollFactors, P: [](uint64_t f) { return f == 1; }))
1726 return rewriter.notifyMatchFailure(
1727 arg&: op, msg: "Unrolling not applied if all factors are 1");
1728
1729 // Return if the loop body is empty.
1730 if (llvm::hasSingleElement(C&: op.getBody()->getOperations()))
1731 return rewriter.notifyMatchFailure(arg&: op, msg: "Cannot unroll an empty loop body");
1732
1733 // If the provided unroll factors do not cover all the loop dims, they are
1734 // applied to the inner loop dimensions.
1735 const unsigned firstLoopDimIdx = numLoops - unrollFactors.size();
1736
1737 // Make sure that the unroll factors divide the iteration space evenly
1738 // TODO: Support unrolling loops with dynamic iteration spaces.
1739 const llvm::SmallVector<llvm::APInt> tripCounts = getConstLoopTripCounts(loopOp: op);
1740 if (tripCounts.empty())
1741 return rewriter.notifyMatchFailure(
1742 arg&: op, msg: "Failed to compute constant trip counts for the loop. Note that "
1743 "dynamic loop sizes are not supported.");
1744
1745 for (unsigned dimIdx = firstLoopDimIdx; dimIdx < numLoops; dimIdx++) {
1746 const uint64_t unrollFactor = unrollFactors[dimIdx - firstLoopDimIdx];
1747 if (tripCounts[dimIdx].urem(RHS: unrollFactor) != 0)
1748 return rewriter.notifyMatchFailure(
1749 arg&: op, msg: "Unroll factors don't divide the iteration space evenly");
1750 }
1751
1752 std::optional<SmallVector<OpFoldResult>> maybeFoldSteps = op.getLoopSteps();
1753 if (!maybeFoldSteps)
1754 return rewriter.notifyMatchFailure(arg&: op, msg: "Failed to retrieve loop steps");
1755 llvm::SmallVector<size_t> steps{};
1756 for (auto step : *maybeFoldSteps)
1757 steps.push_back(Elt: static_cast<size_t>(*getConstantIntValue(ofr: step)));
1758
1759 for (unsigned dimIdx = firstLoopDimIdx; dimIdx < numLoops; dimIdx++) {
1760 const uint64_t unrollFactor = unrollFactors[dimIdx - firstLoopDimIdx];
1761 if (unrollFactor == 1)
1762 continue;
1763 const size_t origStep = steps[dimIdx];
1764 const int64_t newStep = origStep * unrollFactor;
1765 IRMapping clonedToSrcOpsMap;
1766
1767 ValueRange iterArgs = ValueRange(op.getRegionIterArgs());
1768 auto yieldedValues = op.getBody()->getTerminator()->getOperands();
1769
1770 generateUnrolledLoop(
1771 loopBodyBlock: op.getBody(), iv: op.getInductionVars()[dimIdx], unrollFactor,
1772 ivRemapFn: [&](unsigned i, Value iv, OpBuilder b) {
1773 // iv' = iv + step * i;
1774 const AffineExpr expr = b.getAffineDimExpr(position: 0) + (origStep * i);
1775 const auto map =
1776 b.getDimIdentityMap().dropResult(pos: 0).insertResult(expr, pos: 0);
1777 return affine::AffineApplyOp::create(builder&: b, location: iv.getLoc(), map,
1778 mapOperands: ValueRange{iv});
1779 },
1780 /*annotateFn*/ annotateFn, iterArgs, yieldedValues, clonedToSrcOpsMap: &clonedToSrcOpsMap);
1781
1782 // Update loop step
1783 auto prevInsertPoint = rewriter.saveInsertionPoint();
1784 rewriter.setInsertionPoint(op);
1785 op.getStepMutable()[dimIdx].assign(
1786 value: arith::ConstantIndexOp::create(builder&: rewriter, location: op.getLoc(), value: newStep));
1787 rewriter.restoreInsertionPoint(ip: prevInsertPoint);
1788 }
1789 return op;
1790}
1791