1//===- LoopUtils.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/Affine/LoopUtils.h"
14#include "mlir/Analysis/SliceAnalysis.h"
15#include "mlir/Dialect/Affine/Analysis/LoopAnalysis.h"
16#include "mlir/Dialect/Affine/Analysis/Utils.h"
17#include "mlir/Dialect/Affine/IR/AffineValueMap.h"
18#include "mlir/Dialect/Affine/Utils.h"
19#include "mlir/Dialect/Func/IR/FuncOps.h"
20#include "mlir/Dialect/MemRef/IR/MemRef.h"
21#include "mlir/Dialect/SCF/IR/SCF.h"
22#include "mlir/IR/IRMapping.h"
23#include "mlir/IR/IntegerSet.h"
24#include "mlir/IR/OperationSupport.h"
25#include "mlir/Transforms/GreedyPatternRewriteDriver.h"
26#include "llvm/ADT/MapVector.h"
27#include "llvm/Support/Debug.h"
28#include "llvm/Support/DebugLog.h"
29#include "llvm/Support/raw_ostream.h"
30#include <optional>
31
32#define DEBUG_TYPE "loop-utils"
33
34using namespace mlir;
35using namespace affine;
36using namespace presburger;
37using llvm::SmallMapVector;
38
39/// Computes the cleanup loop lower bound of the loop being unrolled with
40/// the specified unroll factor; this bound will also be upper bound of the main
41/// part of the unrolled loop. Computes the bound as an AffineMap with its
42/// operands or a null map when the trip count can't be expressed as an affine
43/// expression.
44static void
45getCleanupLoopLowerBound(AffineForOp forOp, unsigned unrollFactor,
46 AffineMap &cleanupLbMap,
47 SmallVectorImpl<Value> &cleanupLbOperands) {
48 AffineMap tripCountMap;
49 SmallVector<Value, 4> tripCountOperands;
50 getTripCountMapAndOperands(forOp, map: &tripCountMap, operands: &tripCountOperands);
51 // Trip count can't be computed.
52 if (!tripCountMap) {
53 cleanupLbMap = AffineMap();
54 return;
55 }
56
57 OpBuilder b(forOp);
58 auto lbMap = forOp.getLowerBoundMap();
59 auto lb = AffineApplyOp::create(builder&: b, location: forOp.getLoc(), map: lbMap,
60 mapOperands: forOp.getLowerBoundOperands());
61
62 // For each upper bound expr, get the range.
63 // Eg: affine.for %i = lb to min (ub1, ub2),
64 // where tripCountExprs yield (tr1, tr2), we create affine.apply's:
65 // lb + tr1 - tr1 % ufactor, lb + tr2 - tr2 % ufactor; the results of all
66 // these affine.apply's make up the cleanup loop lower bound.
67 SmallVector<AffineExpr, 4> bumpExprs(tripCountMap.getNumResults());
68 SmallVector<Value, 4> bumpValues(tripCountMap.getNumResults());
69 int64_t step = forOp.getStepAsInt();
70 for (unsigned i = 0, e = tripCountMap.getNumResults(); i < e; i++) {
71 auto tripCountExpr = tripCountMap.getResult(idx: i);
72 bumpExprs[i] = (tripCountExpr - tripCountExpr % unrollFactor) * step;
73 auto bumpMap = AffineMap::get(dimCount: tripCountMap.getNumDims(),
74 symbolCount: tripCountMap.getNumSymbols(), result: bumpExprs[i]);
75 bumpValues[i] =
76 AffineApplyOp::create(builder&: b, location: forOp.getLoc(), map: bumpMap, mapOperands: tripCountOperands);
77 }
78
79 SmallVector<AffineExpr, 4> newUbExprs(tripCountMap.getNumResults());
80 for (unsigned i = 0, e = bumpExprs.size(); i < e; i++)
81 newUbExprs[i] = b.getAffineDimExpr(position: 0) + b.getAffineDimExpr(position: i + 1);
82
83 cleanupLbOperands.clear();
84 cleanupLbOperands.push_back(Elt: lb);
85 cleanupLbOperands.append(in_start: bumpValues.begin(), in_end: bumpValues.end());
86 cleanupLbMap = AffineMap::get(dimCount: 1 + tripCountMap.getNumResults(), symbolCount: 0, results: newUbExprs,
87 context: b.getContext());
88 // Simplify the cleanupLbMap + cleanupLbOperands.
89 fullyComposeAffineMapAndOperands(map: &cleanupLbMap, operands: &cleanupLbOperands);
90 cleanupLbMap = simplifyAffineMap(map: cleanupLbMap);
91 canonicalizeMapAndOperands(map: &cleanupLbMap, operands: &cleanupLbOperands);
92 // Remove any affine.apply's that became dead from the simplification above.
93 for (auto v : bumpValues)
94 if (v.use_empty())
95 v.getDefiningOp()->erase();
96
97 if (lb.use_empty())
98 lb.erase();
99}
100
101/// Returns the max of the bound given by `map` applied to `operands` and the
102/// lower bound of `forOp`, as a map over the updated `operands`. Returns `map`
103/// unchanged if it is known not to be below the lower bound. Both bounds must
104/// have a single result.
105static AffineMap getMaxWithLowerBound(AffineForOp forOp, AffineMap map,
106 SmallVectorImpl<Value> &operands) {
107 AffineMap lbMap = forOp.getLowerBoundMap();
108 assert(map.getNumResults() == 1 && lbMap.getNumResults() == 1 &&
109 "expected single-result bounds");
110 // Place the dims and symbols of the lower bound after those of `map`.
111 unsigned numDims = map.getNumDims();
112 unsigned numLbDims = lbMap.getNumDims();
113 AffineMap shiftedLbMap =
114 lbMap.shiftDims(shift: numDims).shiftSymbols(shift: map.getNumSymbols());
115 AffineMap maxMap = AffineMap::get(
116 dimCount: shiftedLbMap.getNumDims(), symbolCount: shiftedLbMap.getNumSymbols(),
117 results: {map.getResult(idx: 0), shiftedLbMap.getResult(idx: 0)}, context: forOp.getContext());
118 ValueRange lbOperands = forOp.getLowerBoundOperands();
119 SmallVector<Value, 4> maxOperands(operands.begin(),
120 operands.begin() + numDims);
121 llvm::append_range(C&: maxOperands, R: lbOperands.take_front(n: numLbDims));
122 llvm::append_range(C&: maxOperands,
123 R: ArrayRef<Value>(operands).drop_front(N: numDims));
124 llvm::append_range(C&: maxOperands, R: lbOperands.drop_front(n: numLbDims));
125 fullyComposeAffineMapAndOperands(map: &maxMap, operands: &maxOperands);
126 canonicalizeMapAndOperands(map: &maxMap, operands: &maxOperands);
127 maxMap = simplifyAffineMap(map: maxMap);
128
129 AffineExpr diff =
130 simplifyAffineExpr(expr: maxMap.getResult(idx: 0) - maxMap.getResult(idx: 1),
131 numDims: maxMap.getNumDims(), numSymbols: maxMap.getNumSymbols());
132 if (auto cst = dyn_cast<AffineConstantExpr>(Val&: diff); cst && cst.getValue() >= 0)
133 return map;
134 operands.assign(in_start: maxOperands.begin(), in_end: maxOperands.end());
135 return maxMap;
136}
137
138/// Helper to replace uses of loop carried values (iter_args) and loop
139/// yield values while promoting single iteration affine.for ops.
140static void replaceIterArgsAndYieldResults(AffineForOp forOp) {
141 // Replace uses of iter arguments with iter operands (initial values).
142 auto iterOperands = forOp.getInits();
143 auto iterArgs = forOp.getRegionIterArgs();
144 for (auto e : llvm::zip(t&: iterOperands, u&: iterArgs))
145 std::get<1>(t&: e).replaceAllUsesWith(newValue: std::get<0>(t&: e));
146
147 // Replace uses of loop results with the values yielded by the loop.
148 auto outerResults = forOp.getResults();
149 auto innerResults = forOp.getBody()->getTerminator()->getOperands();
150 for (auto e : llvm::zip(t&: outerResults, u&: innerResults))
151 std::get<0>(t&: e).replaceAllUsesWith(newValue: std::get<1>(t&: e));
152}
153
154/// Promotes the loop body of a forOp to its containing block if the forOp
155/// was known to have a single iteration.
156LogicalResult mlir::affine::promoteIfSingleIteration(AffineForOp forOp) {
157 std::optional<APInt> tripCount = forOp.getStaticTripCount();
158 if (!tripCount || *tripCount != 1)
159 return failure();
160
161 // TODO: extend this for arbitrary affine bounds.
162 if (forOp.getLowerBoundMap().getNumResults() != 1)
163 return failure();
164
165 // Replaces all IV uses to its single iteration value.
166 auto iv = forOp.getInductionVar();
167 auto *parentBlock = forOp->getBlock();
168 if (!iv.use_empty()) {
169 if (forOp.hasConstantLowerBound()) {
170 auto func = forOp->getParentOfType<FunctionOpInterface>();
171 OpBuilder builder(forOp->getContext());
172 if (func)
173 builder.setInsertionPointToStart(&func.getFunctionBody().front());
174 else
175 builder.setInsertionPoint(forOp);
176 auto constOp = arith::ConstantIndexOp::create(
177 builder, location: forOp.getLoc(), value: forOp.getConstantLowerBound());
178 iv.replaceAllUsesWith(newValue: constOp);
179 } else {
180 auto lbOperands = forOp.getLowerBoundOperands();
181 auto lbMap = forOp.getLowerBoundMap();
182 OpBuilder builder(forOp);
183 if (lbMap == builder.getDimIdentityMap()) {
184 // No need of generating an affine.apply.
185 iv.replaceAllUsesWith(newValue: lbOperands[0]);
186 } else {
187 auto affineApplyOp =
188 AffineApplyOp::create(builder, location: forOp.getLoc(), map: lbMap, mapOperands: lbOperands);
189 iv.replaceAllUsesWith(newValue: affineApplyOp);
190 }
191 }
192 }
193
194 replaceIterArgsAndYieldResults(forOp);
195
196 // Move the loop body operations, except for its terminator, to the loop's
197 // containing block.
198 forOp.getBody()->back().erase();
199 parentBlock->getOperations().splice(where: Block::iterator(forOp),
200 L2&: forOp.getBody()->getOperations());
201 forOp.erase();
202 return success();
203}
204
205/// Generates an affine.for op with the specified lower and upper bounds
206/// while generating the right IV remappings to realize shifts for operations in
207/// its body. The operations that go into the loop body are specified in
208/// opGroupQueue starting from the specified offset, and in that order. The
209/// first element of the pair specifies the shift applied to that group of
210/// operations; the shift is multiplied by the loop step before being applied.
211/// Returns nullptr if the generated loop simplifies to a single iteration one.
212static AffineForOp generateShiftedLoop(
213 AffineMap lbMap, AffineMap ubMap,
214 const std::vector<std::pair<uint64_t, ArrayRef<Operation *>>> &opGroupQueue,
215 unsigned offset, AffineForOp srcForOp, OpBuilder b) {
216 auto lbOperands = srcForOp.getLowerBoundOperands();
217 auto ubOperands = srcForOp.getUpperBoundOperands();
218
219 assert(lbMap.getNumInputs() == lbOperands.size());
220 assert(ubMap.getNumInputs() == ubOperands.size());
221
222 auto loopChunk =
223 AffineForOp::create(builder&: b, location: srcForOp.getLoc(), lbOperands, lbMap, ubOperands,
224 ubMap, step: srcForOp.getStepAsInt());
225 auto loopChunkIV = loopChunk.getInductionVar();
226 auto srcIV = srcForOp.getInductionVar();
227
228 IRMapping operandMap;
229
230 auto bodyBuilder = OpBuilder::atBlockTerminator(block: loopChunk.getBody());
231 for (const auto &it : llvm::drop_begin(RangeOrContainer: opGroupQueue, N: offset)) {
232 uint64_t shift = it.first;
233 auto ops = it.second;
234 // All 'same shift' operations get added with their operands being
235 // remapped to results of cloned operations, and their IV used remapped.
236 // Generate the remapping if the shift is not zero: remappedIV = newIV -
237 // shift.
238 if (!srcIV.use_empty() && shift != 0) {
239 auto ivRemap = AffineApplyOp::create(
240 builder&: bodyBuilder, location: srcForOp.getLoc(),
241 map: bodyBuilder.getSingleDimShiftAffineMap(
242 shift: -static_cast<int64_t>(srcForOp.getStepAsInt() * shift)),
243 mapOperands: loopChunkIV);
244 operandMap.map(from: srcIV, to: ivRemap);
245 } else {
246 operandMap.map(from: srcIV, to: loopChunkIV);
247 }
248 for (auto *op : ops)
249 bodyBuilder.clone(op&: *op, mapper&: operandMap);
250 };
251 if (succeeded(Result: promoteIfSingleIteration(forOp: loopChunk)))
252 return AffineForOp();
253 return loopChunk;
254}
255
256// The skewing of operations with respect to one another can be used for
257// example to allow overlap of asynchronous operations (such as DMA
258// communication) with computation, or just relative shifting of operations
259// for better register reuse, locality or parallelism. As such, the shifts are
260// typically expected to be at most of the order of the number of operations.
261// This method should not be used as a substitute for loop distribution/fission.
262// This method uses an algorithm// in time linear in the number of operations
263// in the body of the for loop - (using the 'sweep line' paradigm). This method
264// asserts preservation of SSA dominance. A check for that as well as that for
265// memory-based dependence preservation check rests with the users of this
266// method.
267LogicalResult mlir::affine::affineForOpBodySkew(AffineForOp forOp,
268 ArrayRef<uint64_t> shifts,
269 bool unrollPrologueEpilogue) {
270 assert(forOp.getBody()->getOperations().size() == shifts.size() &&
271 "too few/many shifts");
272 if (forOp.getBody()->begin() == std::prev(x: forOp.getBody()->end()))
273 return success();
274
275 // If the trip counts aren't constant, we would need versioning and
276 // conditional guards (or context information to prevent such versioning). The
277 // better way to pipeline for such loops is to first tile them and extract
278 // constant trip count "full tiles" before applying this.
279 auto mayBeConstTripCount = forOp.getStaticTripCount();
280 if (!mayBeConstTripCount) {
281 LLVM_DEBUG(forOp.emitRemark("non-constant trip count loop not handled"));
282 return success();
283 }
284 uint64_t tripCount = mayBeConstTripCount->getZExtValue();
285
286 assert(isOpwiseShiftValid(forOp, shifts) &&
287 "shifts will lead to an invalid transformation\n");
288
289 int64_t step = forOp.getStepAsInt();
290
291 unsigned numChildOps = shifts.size();
292
293 // Do a linear time (counting) sort for the shifts.
294 uint64_t maxShift = *llvm::max_element(Range&: shifts);
295 if (maxShift >= numChildOps) {
296 // Large shifts are not the typical use case.
297 forOp.emitWarning(message: "not shifting because shifts are unrealistically large");
298 return success();
299 }
300
301 // An array of operation groups sorted by shift amount; each group has all
302 // operations with the same shift in the order in which they appear in the
303 // body of the 'affine.for' op.
304 std::vector<std::vector<Operation *>> sortedOpGroups(maxShift + 1);
305 unsigned pos = 0;
306 for (auto &op : forOp.getBody()->without_terminator()) {
307 auto shift = shifts[pos++];
308 sortedOpGroups[shift].push_back(x: &op);
309 }
310
311 // Unless the shifts have a specific pattern (which actually would be the
312 // common use case), prologue and epilogue are not meaningfully defined.
313 // Nevertheless, if 'unrollPrologueEpilogue' is set, we will treat the first
314 // loop generated as the prologue and the last as epilogue and unroll these
315 // fully.
316 AffineForOp prologue, epilogue;
317
318 // Do a sweep over the sorted shifts while storing open groups in a
319 // vector, and generating loop portions as necessary during the sweep. A block
320 // of operations is paired with its shift.
321 std::vector<std::pair<uint64_t, ArrayRef<Operation *>>> opGroupQueue;
322
323 auto origLbMap = forOp.getLowerBoundMap();
324 uint64_t lbShift = 0;
325 OpBuilder b(forOp);
326 for (uint64_t d = 0, e = sortedOpGroups.size(); d < e; ++d) {
327 // If nothing is shifted by d, continue.
328 if (sortedOpGroups[d].empty())
329 continue;
330 if (!opGroupQueue.empty()) {
331 assert(d > 0 &&
332 "Queue expected to be empty when the first block is found");
333 // The interval for which the loop needs to be generated here is:
334 // [lbShift, min(lbShift + tripCount, d)) and the body of the
335 // loop needs to have all operations in opQueue in that order.
336 AffineForOp res;
337 if (lbShift + tripCount * step < d * step) {
338 res = generateShiftedLoop(
339 lbMap: b.getShiftedAffineMap(map: origLbMap, shift: lbShift),
340 ubMap: b.getShiftedAffineMap(map: origLbMap, shift: lbShift + tripCount * step),
341 opGroupQueue, /*offset=*/0, srcForOp: forOp, b);
342 // Entire loop for the queued op groups generated, empty it.
343 opGroupQueue.clear();
344 lbShift += tripCount * step;
345 } else {
346 res = generateShiftedLoop(lbMap: b.getShiftedAffineMap(map: origLbMap, shift: lbShift),
347 ubMap: b.getShiftedAffineMap(map: origLbMap, shift: d),
348 opGroupQueue, /*offset=*/0, srcForOp: forOp, b);
349 lbShift = d * step;
350 }
351
352 if (res) {
353 // Simplify/canonicalize the affine.for.
354 RewritePatternSet patterns(res.getContext());
355 AffineForOp::getCanonicalizationPatterns(results&: patterns, context: res.getContext());
356 bool erased;
357 (void)applyOpPatternsGreedily(
358 ops: res.getOperation(), patterns: std::move(patterns),
359 config: GreedyRewriteConfig().setStrictness(
360 GreedyRewriteStrictness::ExistingAndNewOps),
361 /*changed=*/nullptr, allErased: &erased);
362 if (!erased && !prologue)
363 prologue = res;
364 if (!erased)
365 epilogue = res;
366 }
367 } else {
368 // Start of first interval.
369 lbShift = d * step;
370 }
371 // Augment the list of operations that get into the current open interval.
372 opGroupQueue.emplace_back(args&: d, args&: sortedOpGroups[d]);
373 }
374
375 // Those operations groups left in the queue now need to be processed (FIFO)
376 // and their loops completed.
377 for (unsigned i = 0, e = opGroupQueue.size(); i < e; ++i) {
378 uint64_t ubShift = (opGroupQueue[i].first + tripCount) * step;
379 epilogue = generateShiftedLoop(lbMap: b.getShiftedAffineMap(map: origLbMap, shift: lbShift),
380 ubMap: b.getShiftedAffineMap(map: origLbMap, shift: ubShift),
381 opGroupQueue, /*offset=*/i, srcForOp: forOp, b);
382 lbShift = ubShift;
383 if (!prologue)
384 prologue = epilogue;
385 }
386
387 // Erase the original for op.
388 forOp.erase();
389
390 if (unrollPrologueEpilogue && prologue)
391 (void)loopUnrollFull(forOp: prologue);
392 if (unrollPrologueEpilogue && !epilogue && epilogue != prologue)
393 (void)loopUnrollFull(forOp: epilogue);
394
395 return success();
396}
397
398/// Checks whether a loop nest is hyper-rectangular or not.
399static LogicalResult
400checkIfHyperRectangular(MutableArrayRef<AffineForOp> input) {
401 FlatAffineValueConstraints cst;
402 SmallVector<Operation *, 8> ops(input.begin(), input.end());
403 // 0-d or 1-d is trivially hyper-rectangular.
404 if (input.size() <= 1)
405 return success();
406 if (failed(Result: getIndexSet(ops, domain: &cst))) {
407 LDBG() << "Index set computation failed!";
408 return failure();
409 }
410 if (!cst.isHyperRectangular(pos: 0, num: input.size())) {
411 LDBG() << "Non-hyperrectangular nests not supported for tiling!";
412 return failure();
413 }
414 return success();
415}
416
417/// Check if the input nest is supported for tiling and whether tiling would be
418/// legal or not.
419template <typename t>
420static LogicalResult performPreTilingChecks(MutableArrayRef<AffineForOp> input,
421 ArrayRef<t> tileSizes) {
422 assert(input.size() == tileSizes.size() && "Too few/many tile sizes");
423
424 if (llvm::any_of(input,
425 [](AffineForOp op) { return op.getNumResults() > 0; })) {
426 LDBG() << "Cannot tile nest where a loop has yield values";
427 return failure();
428 }
429
430 // Check if the supplied `for` ops are all successively nested.
431 if (!isPerfectlyNested(loops: input)) {
432 LDBG() << "input loops not perfectly nested";
433 return failure();
434 }
435
436 // TODO: handle non hyper-rectangular spaces.
437 if (failed(Result: checkIfHyperRectangular(input)))
438 return failure();
439
440 return success();
441}
442
443/// Move the loop body of AffineForOp 'src' from 'src' into the specified
444/// location in destination's body, ignoring the terminator.
445static void moveLoopBodyImpl(AffineForOp src, AffineForOp dest,
446 Block::iterator loc) {
447 auto &ops = src.getBody()->getOperations();
448 dest.getBody()->getOperations().splice(where: loc, L2&: ops, first: ops.begin(),
449 last: std::prev(x: ops.end()));
450}
451
452/// Move the loop body of AffineForOp 'src' from 'src' to the start of dest
453/// body.
454static void moveLoopBody(AffineForOp src, AffineForOp dest) {
455 moveLoopBodyImpl(src, dest, loc: dest.getBody()->begin());
456}
457
458/// Constructs tiled loop nest, without setting the loop bounds and move the
459/// body of the original loop nest to the tiled loop nest.
460static void constructTiledLoopNest(MutableArrayRef<AffineForOp> origLoops,
461 AffineForOp rootAffineForOp, unsigned width,
462 MutableArrayRef<AffineForOp> tiledLoops) {
463 Location loc = rootAffineForOp.getLoc();
464
465 // The outermost among the loops as we add more..
466 Operation *topLoop = rootAffineForOp.getOperation();
467 AffineForOp innermostPointLoop;
468
469 // Add intra-tile (or point) loops.
470 for (unsigned i = 0; i < width; i++) {
471 OpBuilder b(topLoop);
472 // Loop bounds will be set later.
473 AffineForOp pointLoop = AffineForOp::create(builder&: b, location: loc, lowerBound: 0, upperBound: 0);
474 pointLoop.getBody()->getOperations().splice(
475 where: pointLoop.getBody()->begin(), L2&: topLoop->getBlock()->getOperations(),
476 N: topLoop);
477 tiledLoops[2 * width - 1 - i] = pointLoop;
478 topLoop = pointLoop.getOperation();
479 if (i == 0)
480 innermostPointLoop = pointLoop;
481 }
482
483 // Add tile space loops;
484 for (unsigned i = width; i < 2 * width; i++) {
485 OpBuilder b(topLoop);
486 // Loop bounds will be set later.
487 AffineForOp tileSpaceLoop = AffineForOp::create(builder&: b, location: loc, lowerBound: 0, upperBound: 0);
488 tileSpaceLoop.getBody()->getOperations().splice(
489 where: tileSpaceLoop.getBody()->begin(), L2&: topLoop->getBlock()->getOperations(),
490 N: topLoop);
491 tiledLoops[2 * width - i - 1] = tileSpaceLoop;
492 topLoop = tileSpaceLoop.getOperation();
493 }
494
495 // Move the loop body of the original nest to the new one.
496 moveLoopBody(src: origLoops.back(), dest: innermostPointLoop);
497}
498
499/// Set lower and upper bounds of intra-tile loops for parametric tiling.
500// TODO: Handle non-constant lower bounds.
501static void setIntraTileBoundsParametric(OpBuilder &b, AffineForOp origLoop,
502 AffineForOp newInterTileLoop,
503 AffineForOp newIntraTileLoop,
504 Value tileSize) {
505 // The lower bound for the intra-tile loop is represented by an affine map
506 // as (%i, %t0)->((%i - %origlb) * %t0 + %origlb). Similarly, the upper bound
507 // for the intra-tile loop is represented by an affine map as (%i, %t0)->((%i
508 // - %origlb) * %t0) + (%t0 * %origLoopStep) + %origlb), where %i is loop IV
509 // of the corresponding inter-tile loop, %t0 is the corresponding tiling
510 // parameter, %origlb is lower bound and %origLoopStep is the loop step of the
511 // corresponding inter-tile loop.
512
513 assert(origLoop.hasConstantLowerBound() &&
514 "expected input loops to have constant lower bound.");
515
516 // Get lower bound of original loop as an affine expression.
517 AffineExpr origLowerBoundExpr;
518 origLowerBoundExpr =
519 b.getAffineConstantExpr(constant: origLoop.getConstantLowerBound());
520
521 // Add dim operands from original lower/upper bound.
522 SmallVector<Value, 4> lbOperands, ubOperands;
523 AffineBound lb = origLoop.getLowerBound();
524 AffineBound ub = origLoop.getUpperBound();
525 lbOperands.reserve(N: lb.getNumOperands() + 2);
526 ubOperands.reserve(N: ub.getNumOperands() + 2);
527 AffineMap origLbMap = lb.getMap();
528 AffineMap origUbMap = ub.getMap();
529 for (unsigned j = 0, e = origLbMap.getNumDims(); j < e; ++j)
530 lbOperands.push_back(Elt: lb.getOperand(idx: j));
531 for (unsigned j = 0, e = origUbMap.getNumDims(); j < e; ++j)
532 ubOperands.push_back(Elt: ub.getOperand(idx: j));
533
534 // Add a new dim operand in lb/ubOperands corresponding to the origLoop
535 // IV.
536 lbOperands.push_back(Elt: newInterTileLoop.getInductionVar());
537 ubOperands.push_back(Elt: newInterTileLoop.getInductionVar());
538
539 // Get loop IV as an affine expression for lower/upper bound. Size of
540 // lb/ubOperands is guaranteed to be atleast one.
541 AffineExpr lbLoopIvExpr = b.getAffineDimExpr(position: lbOperands.size() - 1);
542 AffineExpr ubLoopIvExpr = b.getAffineDimExpr(position: ubOperands.size() - 1);
543
544 // Add symbol operands from original lower/upper bound.
545 for (unsigned j = 0, e = origLbMap.getNumSymbols(); j < e; ++j)
546 lbOperands.push_back(Elt: lb.getOperand(idx: origLbMap.getNumDims() + j));
547 for (unsigned j = 0, e = origUbMap.getNumSymbols(); j < e; ++j)
548 ubOperands.push_back(Elt: ub.getOperand(idx: origUbMap.getNumDims() + j));
549
550 // Add a new symbol operand which is the tile size for this loop.
551 lbOperands.push_back(Elt: tileSize);
552 ubOperands.push_back(Elt: tileSize);
553
554 SmallVector<AffineExpr, 4> lbBoundExprs;
555 SmallVector<AffineExpr, 4> ubBoundExprs;
556 lbBoundExprs.reserve(N: origLbMap.getNumResults());
557 ubBoundExprs.reserve(N: origUbMap.getNumResults());
558
559 // Get tiling parameter as an affine expression for lb/ub.
560 AffineExpr lbTileParameter = b.getAffineSymbolExpr(position: origLbMap.getNumSymbols());
561 AffineExpr ubTileParameter = b.getAffineSymbolExpr(position: origUbMap.getNumSymbols());
562
563 // Insert lb as inter-tile ((loop IV - origlb) * tilingParameter) + origlb.
564 lbBoundExprs.push_back(
565 Elt: ((lbLoopIvExpr - origLowerBoundExpr) * lbTileParameter) +
566 origLowerBoundExpr);
567
568 // Get the origLoopStep as an affine expression.
569 AffineExpr origLoopStep = b.getAffineConstantExpr(constant: origLoop.getStepAsInt());
570
571 // Insert ub as inter-tile ((loop IV - origlb) * tilingParameter) +
572 // (tilingParameter * origLoopStep) + origlb.
573 ubBoundExprs.push_back(
574 Elt: ((ubLoopIvExpr - origLowerBoundExpr) * ubTileParameter) +
575 (ubTileParameter * origLoopStep) + origLowerBoundExpr);
576
577 ubBoundExprs.append(in_start: origUbMap.getResults().begin(),
578 in_end: origUbMap.getResults().end());
579
580 AffineMap lbMap =
581 AffineMap::get(dimCount: origLbMap.getNumDims() + 1, symbolCount: origLbMap.getNumSymbols() + 1,
582 results: lbBoundExprs, context: b.getContext());
583 newIntraTileLoop.setLowerBound(operands: lbOperands, map: lbMap);
584
585 AffineMap ubMap =
586 AffineMap::get(dimCount: origUbMap.getNumDims() + 1, symbolCount: origUbMap.getNumSymbols() + 1,
587 results: ubBoundExprs, context: b.getContext());
588 newIntraTileLoop.setUpperBound(operands: ubOperands, map: ubMap);
589
590 // Original loop step must be preserved.
591 newIntraTileLoop.setStep(origLoop.getStepAsInt());
592}
593
594/// Set lower and upper bounds of inter-tile loops for parametric tiling.
595// TODO: Handle non-constant lower bounds.
596static void setInterTileBoundsParametric(OpBuilder &b, AffineForOp origLoop,
597 AffineForOp newLoop, Value tileSize) {
598 OperandRange newLbOperands = origLoop.getLowerBoundOperands();
599
600 // The lower bounds for inter-tile loops are same as the corresponding lower
601 // bounds of original loops.
602 newLoop.setLowerBound(operands: newLbOperands, map: origLoop.getLowerBoundMap());
603
604 // The new upper bound map for inter-tile loops, assuming constant lower
605 // bounds, are now originalLowerBound + ceildiv((originalUpperBound -
606 // originalLowerBound), tiling parameter); where tiling parameter is the
607 // respective tile size for that loop. For e.g. if the original ubmap was
608 // ()->(1024), the new map will be
609 // ()[s0]->(ceildiv((1024 -lb) % s0)), where s0 is the tiling parameter.
610 // Therefore a new symbol operand is inserted in the map and the result
611 // expression is overwritten.
612
613 assert(origLoop.hasConstantLowerBound() &&
614 "expected input loops to have constant lower bound.");
615
616 // Get lower bound of original loop as an affine expression.
617 AffineExpr origLowerBoundExpr;
618 origLowerBoundExpr =
619 b.getAffineConstantExpr(constant: origLoop.getConstantLowerBound());
620
621 // Add dim operands from original upper bound.
622 SmallVector<Value, 4> ubOperands;
623 AffineBound ub = origLoop.getUpperBound();
624 ubOperands.reserve(N: ub.getNumOperands() + 1);
625 AffineMap origUbMap = ub.getMap();
626 for (unsigned j = 0, e = origUbMap.getNumDims(); j < e; ++j)
627 ubOperands.push_back(Elt: ub.getOperand(idx: j));
628
629 // Add symbol operands from original upper bound.
630 for (unsigned j = 0, e = origUbMap.getNumSymbols(); j < e; ++j)
631 ubOperands.push_back(Elt: ub.getOperand(idx: origUbMap.getNumDims() + j));
632
633 // Add a new symbol operand which is the tile size for this loop.
634 ubOperands.push_back(Elt: tileSize);
635
636 // Get tiling parameter as an affine expression.
637 AffineExpr tileParameter = b.getAffineSymbolExpr(position: origUbMap.getNumSymbols());
638
639 SmallVector<AffineExpr, 4> boundExprs;
640 boundExprs.reserve(N: origUbMap.getNumResults());
641 int64_t origUpperBound;
642 AffineExpr origUpperBoundExpr;
643
644 // If upper bound for the original loop is constant, then the constant can
645 // be obtained as an affine expression straight away.
646 if (origLoop.hasConstantUpperBound()) {
647 origUpperBound = origLoop.getConstantUpperBound();
648
649 // Get original constant upper bound as an affine expression.
650 origUpperBoundExpr = b.getAffineConstantExpr(constant: origUpperBound);
651
652 // Insert the bound as originalLowerBoundceildiv((originalUpperBound -
653 // originalLowerBound), tilingParameter).
654 boundExprs.push_back(
655 Elt: origLowerBoundExpr +
656 (origUpperBoundExpr - origLowerBoundExpr).ceilDiv(other: tileParameter));
657 } else {
658 // If upper bound for the original loop is not constant then two cases
659 // are possible, although there handeling is the same, 1.) The result of
660 // ubmap has only one result expression. For e.g.
661 // affine.for %i = 5 to %ub
662 //
663 // A symbol operand is added which represents the tiling parameter. The
664 // new loop bounds here will be like ()[s0, s1] -> ((s0 - 5) ceildiv s1 + 5)
665 // where 's0' is the original upper bound and 's1' is the tiling
666 // parameter. 2.) When ubMap has more than one result expression. For e.g.
667 // #map0 = affine_map<()[s0, s1] -> (s0, s1)
668 // affine.for %i = 5 to min #map0()[%s0, %s1]
669 //
670 // A symbol operand is added which represents the tiling parameter. The
671 // new loop bounds will be like ()[s0, s1, s2] -> ((s0 - 5) ceildiv s2 + 5,
672 // (s1 -5) ceildiv s2 + 5), where s2 is the tiling parameter.
673
674 // Insert the bounds as originalLowerBound + ceildiv((originalUpperBound -
675 // originalLowerBound), tilingParameter).
676 for (AffineExpr origUpperBoundExpr : origUbMap.getResults())
677 boundExprs.push_back(
678 Elt: origLowerBoundExpr +
679 (origUpperBoundExpr - origLowerBoundExpr).ceilDiv(other: tileParameter));
680 }
681
682 AffineMap ubMap =
683 AffineMap::get(dimCount: origUbMap.getNumDims(), symbolCount: origUbMap.getNumSymbols() + 1,
684 results: boundExprs, context: b.getContext());
685 newLoop.setUpperBound(operands: ubOperands, map: ubMap);
686
687 // Original loop step must be preserved.
688 newLoop.setStep(origLoop.getStepAsInt());
689}
690
691/// Constructs and sets new loop bounds after tiling for the case of
692/// hyper-rectangular index sets, where the bounds of one dimension do not
693/// depend on other dimensions and tiling parameters are captured from SSA
694/// values. Bounds of each dimension can thus be treated independently,
695/// and deriving the new bounds is much simpler and faster than for the case of
696/// tiling arbitrary polyhedral shapes.
697static void constructParametricallyTiledIndexSetHyperRect(
698 MutableArrayRef<AffineForOp> origLoops,
699 MutableArrayRef<AffineForOp> newLoops, ArrayRef<Value> tileSizes) {
700 assert(!origLoops.empty() && "expected atleast one loop in band");
701 assert(origLoops.size() == tileSizes.size() &&
702 "expected tiling parameter for each loop in band.");
703
704 OpBuilder b(origLoops[0].getOperation());
705 unsigned width = origLoops.size();
706
707 // Set bounds for tile space loops.
708 for (unsigned i = 0; i < width; ++i) {
709 setInterTileBoundsParametric(b, origLoop: origLoops[i], newLoop: newLoops[i], tileSize: tileSizes[i]);
710 }
711
712 // Set bounds for intra-tile loops.
713 for (unsigned i = 0; i < width; ++i) {
714 setIntraTileBoundsParametric(b, origLoop: origLoops[i], newInterTileLoop: newLoops[i],
715 newIntraTileLoop: newLoops[i + width], tileSize: tileSizes[i]);
716 }
717}
718
719/// Constructs and sets new loop bounds after tiling for the case of
720/// hyper-rectangular index sets, where the bounds of one dimension do not
721/// depend on other dimensions. Bounds of each dimension can thus be treated
722/// independently, and deriving the new bounds is much simpler and faster
723/// than for the case of tiling arbitrary polyhedral shapes.
724static void
725constructTiledIndexSetHyperRect(MutableArrayRef<AffineForOp> origLoops,
726 MutableArrayRef<AffineForOp> newLoops,
727 ArrayRef<unsigned> tileSizes) {
728 assert(!origLoops.empty());
729 assert(origLoops.size() == tileSizes.size());
730
731 OpBuilder b(origLoops[0].getOperation());
732 unsigned width = origLoops.size();
733
734 // Bounds for tile space loops.
735 for (unsigned i = 0; i < width; i++) {
736 OperandRange newLbOperands = origLoops[i].getLowerBoundOperands();
737 OperandRange newUbOperands = origLoops[i].getUpperBoundOperands();
738 newLoops[i].setLowerBound(operands: newLbOperands, map: origLoops[i].getLowerBoundMap());
739 newLoops[i].setUpperBound(operands: newUbOperands, map: origLoops[i].getUpperBoundMap());
740 // If the step size of original loop is x and tileSize is y then after
741 // tiling the tile space loops' step size becomes x*y.
742 newLoops[i].setStep(tileSizes[i] * origLoops[i].getStepAsInt());
743 }
744 // Bounds for intra-tile loops.
745 for (unsigned i = 0; i < width; i++) {
746 int64_t largestDiv = getLargestDivisorOfTripCount(forOp: origLoops[i]);
747 AffineForOp forOp = origLoops[i];
748 std::optional<uint64_t> mayBeConstantCount = std::nullopt;
749 if (auto staticTripCount = forOp.getStaticTripCount())
750 mayBeConstantCount = staticTripCount->getZExtValue();
751 // The lower bound is just the tile-space loop.
752 AffineMap lbMap = b.getDimIdentityMap();
753 newLoops[width + i].setLowerBound(
754 /*operands=*/newLoops[i].getInductionVar(), map: lbMap);
755 // The step sizes of intra-tile loops is just the original loops' step size.
756 newLoops[width + i].setStep(origLoops[i].getStepAsInt());
757
758 // Set the upper bound.
759 if (mayBeConstantCount && *mayBeConstantCount < tileSizes[i]) {
760 // Trip count is less than the tile size: upper bound is lower bound +
761 // trip count * stepSize.
762 AffineMap ubMap = b.getSingleDimShiftAffineMap(
763 shift: *mayBeConstantCount * origLoops[i].getStepAsInt());
764 newLoops[width + i].setUpperBound(
765 /*operands=*/newLoops[i].getInductionVar(), map: ubMap);
766 } else if (largestDiv % tileSizes[i] != 0) {
767 // Intra-tile loop ii goes from i to min(i + tileSize * stepSize, ub_i).
768 // Construct the upper bound map; the operands are the original operands
769 // with 'i' (tile-space loop) appended to it. The new upper bound map is
770 // the original one with an additional expression i + tileSize * stepSize
771 // appended.
772
773 // Add dim operands from original upper bound.
774 SmallVector<Value, 4> ubOperands;
775 AffineBound ub = origLoops[i].getUpperBound();
776 ubOperands.reserve(N: ub.getNumOperands() + 1);
777 AffineMap origUbMap = ub.getMap();
778 for (unsigned j = 0, e = origUbMap.getNumDims(); j < e; ++j)
779 ubOperands.push_back(Elt: ub.getOperand(idx: j));
780
781 // Add dim operand for new loop upper bound.
782 ubOperands.push_back(Elt: newLoops[i].getInductionVar());
783
784 // Add symbol operands from original upper bound.
785 for (unsigned j = 0, e = origUbMap.getNumSymbols(); j < e; ++j)
786 ubOperands.push_back(Elt: ub.getOperand(idx: origUbMap.getNumDims() + j));
787
788 SmallVector<AffineExpr, 4> boundExprs;
789 boundExprs.reserve(N: 1 + origUbMap.getNumResults());
790 AffineExpr dim = b.getAffineDimExpr(position: origUbMap.getNumDims());
791 // The new upper bound map is the original one with an additional
792 // expression i + tileSize * stepSize (of original loop) appended.
793 boundExprs.push_back(Elt: dim + tileSizes[i] * origLoops[i].getStepAsInt());
794 boundExprs.append(in_start: origUbMap.getResults().begin(),
795 in_end: origUbMap.getResults().end());
796 AffineMap ubMap =
797 AffineMap::get(dimCount: origUbMap.getNumDims() + 1, symbolCount: origUbMap.getNumSymbols(),
798 results: boundExprs, context: b.getContext());
799 newLoops[width + i].setUpperBound(/*operands=*/ubOperands, map: ubMap);
800 } else {
801 // No need of the min expression.
802 AffineExpr dim = b.getAffineDimExpr(position: 0);
803 AffineMap ubMap = AffineMap::get(
804 dimCount: 1, symbolCount: 0, result: dim + tileSizes[i] * origLoops[i].getStepAsInt());
805 newLoops[width + i].setUpperBound(operands: newLoops[i].getInductionVar(), map: ubMap);
806 }
807 }
808}
809
810LogicalResult
811mlir::affine::tilePerfectlyNested(MutableArrayRef<AffineForOp> input,
812 ArrayRef<unsigned> tileSizes,
813 SmallVectorImpl<AffineForOp> *tiledNest) {
814 if (input.empty())
815 return success();
816
817 if (failed(Result: performPreTilingChecks(input, tileSizes)))
818 return failure();
819
820 MutableArrayRef<AffineForOp> origLoops = input;
821 AffineForOp rootAffineForOp = origLoops[0];
822
823 // Note that width is at least one since the band isn't empty.
824 unsigned width = input.size();
825 SmallVector<AffineForOp, 6> tiledLoops(2 * width);
826
827 // Construct a tiled loop nest without setting their bounds. Bounds are
828 // set later.
829 constructTiledLoopNest(origLoops, rootAffineForOp, width, tiledLoops);
830
831 SmallVector<Value, 8> origLoopIVs;
832 extractForInductionVars(forInsts: input, ivs: &origLoopIVs);
833
834 // Set loop bounds for the tiled loop nest.
835 constructTiledIndexSetHyperRect(origLoops, newLoops: tiledLoops, tileSizes);
836
837 // Replace original IVs with intra-tile loop IVs.
838 for (unsigned i = 0; i < width; i++)
839 origLoopIVs[i].replaceAllUsesWith(newValue: tiledLoops[i + width].getInductionVar());
840
841 // Erase the old loop nest.
842 rootAffineForOp.erase();
843
844 if (tiledNest)
845 *tiledNest = std::move(tiledLoops);
846
847 return success();
848}
849
850/// Tiles the specified band of perfectly nested loops creating tile-space
851/// loops and intra-tile loops, using SSA values as tiling parameters. A band
852/// is a contiguous set of loops.
853LogicalResult mlir::affine::tilePerfectlyNestedParametric(
854 MutableArrayRef<AffineForOp> input, ArrayRef<Value> tileSizes,
855 SmallVectorImpl<AffineForOp> *tiledNest) {
856 if (input.empty())
857 return success();
858
859 if (failed(Result: performPreTilingChecks(input, tileSizes)))
860 return failure();
861
862 MutableArrayRef<AffineForOp> origLoops = input;
863 AffineForOp rootAffineForOp = origLoops[0];
864 unsigned width = input.size();
865 SmallVector<AffineForOp, 6> tiledLoops(2 * width);
866
867 // Construct a tiled loop nest without setting their bounds. Bounds are
868 // set later.
869 constructTiledLoopNest(origLoops, rootAffineForOp, width, tiledLoops);
870
871 SmallVector<Value, 8> origLoopIVs;
872 extractForInductionVars(forInsts: input, ivs: &origLoopIVs);
873
874 // Set loop bounds for the tiled loop nest.
875 constructParametricallyTiledIndexSetHyperRect(origLoops, newLoops: tiledLoops,
876 tileSizes);
877
878 // Replace original IVs with intra-tile loop IVs.
879 for (unsigned i = 0; i < width; i++)
880 origLoopIVs[i].replaceAllUsesWith(newValue: tiledLoops[i + width].getInductionVar());
881
882 // Erase the old loop nest.
883 rootAffineForOp.erase();
884
885 if (tiledNest)
886 *tiledNest = std::move(tiledLoops);
887
888 return success();
889}
890
891/// Get perfectly nested sequence of loops starting at root of loop nest
892/// (the first op being another AffineFor, and the second op - a terminator).
893/// A loop is perfectly nested iff: the first op in the loop's body is another
894/// AffineForOp, and the second op is a terminator).
895void mlir::affine::getPerfectlyNestedLoops(
896 SmallVectorImpl<AffineForOp> &nestedLoops, AffineForOp root) {
897 for (unsigned i = 0; i < std::numeric_limits<unsigned>::max(); ++i) {
898 nestedLoops.push_back(Elt: root);
899 Block &body = root.getRegion().front();
900 if (body.begin() != std::prev(x: body.end(), n: 2))
901 return;
902
903 root = dyn_cast<AffineForOp>(Val: &body.front());
904 if (!root)
905 return;
906 }
907}
908
909/// Unrolls this loop completely.
910LogicalResult mlir::affine::loopUnrollFull(AffineForOp forOp) {
911 std::optional<APInt> mayBeConstantTripCount = forOp.getStaticTripCount();
912 if (mayBeConstantTripCount.has_value()) {
913 uint64_t tripCount = mayBeConstantTripCount->getZExtValue();
914 if (tripCount == 0)
915 return success();
916 if (tripCount == 1)
917 return promoteIfSingleIteration(forOp);
918 return loopUnrollByFactor(forOp, unrollFactor: tripCount);
919 }
920 return failure();
921}
922
923/// Unrolls this loop by the specified factor or by the trip count (if constant)
924/// whichever is lower.
925LogicalResult mlir::affine::loopUnrollUpToFactor(AffineForOp forOp,
926 uint64_t unrollFactor) {
927 std::optional<APInt> mayBeConstantTripCount = forOp.getStaticTripCount();
928 if (mayBeConstantTripCount.has_value() &&
929 mayBeConstantTripCount->ult(RHS: unrollFactor))
930 return loopUnrollByFactor(forOp, unrollFactor: mayBeConstantTripCount->getZExtValue());
931 return loopUnrollByFactor(forOp, unrollFactor);
932}
933
934/// Generates unrolled copies of AffineForOp 'loopBodyBlock', with associated
935/// 'forOpIV' by 'unrollFactor', calling 'ivRemapFn' to remap 'forOpIV' for each
936/// unrolled body. If specified, annotates the Ops in each unrolled iteration
937/// using annotateFn.
938static void generateUnrolledLoop(
939 Block *loopBodyBlock, Value forOpIV, uint64_t unrollFactor,
940 function_ref<Value(unsigned, Value, OpBuilder)> ivRemapFn,
941 function_ref<void(unsigned, Operation *, OpBuilder)> annotateFn,
942 ValueRange iterArgs, ValueRange yieldedValues) {
943 // Builder to insert unrolled bodies just before the terminator of the body of
944 // 'forOp'.
945 auto builder = OpBuilder::atBlockTerminator(block: loopBodyBlock);
946
947 constexpr auto defaultAnnotateFn = [](unsigned, Operation *, OpBuilder) {};
948 if (!annotateFn)
949 annotateFn = defaultAnnotateFn;
950
951 // Keep a pointer to the last non-terminator operation in the original block
952 // so that we know what to clone (since we are doing this in-place).
953 Block::iterator srcBlockEnd = std::prev(x: loopBodyBlock->end(), n: 2);
954
955 // Unroll the contents of 'forOp' (append unrollFactor - 1 additional copies).
956 SmallVector<Value, 4> lastYielded(yieldedValues);
957
958 for (unsigned i = 1; i < unrollFactor; i++) {
959 IRMapping operandMap;
960
961 // Prepare operand map.
962 operandMap.map(from&: iterArgs, to&: lastYielded);
963
964 // If the induction variable is used, create a remapping to the value for
965 // this unrolled instance.
966 if (!forOpIV.use_empty()) {
967 Value ivUnroll = ivRemapFn(i, forOpIV, builder);
968 operandMap.map(from: forOpIV, to: ivUnroll);
969 }
970
971 // Clone the original body of 'forOp'.
972 for (auto it = loopBodyBlock->begin(); it != std::next(x: srcBlockEnd); it++) {
973 Operation *clonedOp = builder.clone(op&: *it, mapper&: operandMap);
974 annotateFn(i, clonedOp, builder);
975 }
976
977 // Update yielded values. Values defined outside the loop body are not in
978 // `operandMap` and stay unchanged.
979 for (unsigned i = 0, e = lastYielded.size(); i < e; i++)
980 lastYielded[i] = operandMap.lookupOrDefault(from: yieldedValues[i]);
981 }
982
983 // Make sure we annotate the Ops in the original body. We do this last so that
984 // any annotations are not copied into the cloned Ops above.
985 for (auto it = loopBodyBlock->begin(); it != std::next(x: srcBlockEnd); it++)
986 annotateFn(0, &*it, builder);
987
988 // Update operands of the yield statement.
989 loopBodyBlock->getTerminator()->setOperands(lastYielded);
990}
991
992/// Helper to generate cleanup loop for unroll or unroll-and-jam when the trip
993/// count is not a multiple of `unrollFactor`.
994static LogicalResult generateCleanupLoopForUnroll(AffineForOp forOp,
995 uint64_t unrollFactor) {
996 // Insert the cleanup loop right after 'forOp'.
997 OpBuilder builder(forOp->getBlock(), std::next(x: Block::iterator(forOp)));
998 auto cleanupForOp = cast<AffineForOp>(Val: builder.clone(op&: *forOp));
999
1000 // Update uses of `forOp` results. `cleanupForOp` should use `forOp` result
1001 // and produce results for the original users of `forOp` results.
1002 auto results = forOp.getResults();
1003 auto cleanupResults = cleanupForOp.getResults();
1004 auto cleanupIterOperands = cleanupForOp.getInits();
1005
1006 for (auto e : llvm::zip(t&: results, u&: cleanupResults, args&: cleanupIterOperands)) {
1007 std::get<0>(t&: e).replaceAllUsesWith(newValue: std::get<1>(t&: e));
1008 cleanupForOp->replaceUsesOfWith(from: std::get<2>(t&: e), to: std::get<0>(t&: e));
1009 }
1010
1011 AffineMap cleanupMap;
1012 SmallVector<Value, 4> cleanupOperands;
1013 getCleanupLoopLowerBound(forOp, unrollFactor, cleanupLbMap&: cleanupMap, cleanupLbOperands&: cleanupOperands);
1014 if (!cleanupMap)
1015 return failure();
1016
1017 // The cleanup loop must not execute if `forOp` does not, but `cleanupMap` is
1018 // below the lower bound of `forOp` if the trip count is negative.
1019 SmallVector<Value, 4> cleanupLbOperands(cleanupOperands);
1020 AffineMap cleanupLbMap =
1021 getMaxWithLowerBound(forOp, map: cleanupMap, operands&: cleanupLbOperands);
1022 cleanupForOp.setLowerBound(operands: cleanupLbOperands, map: cleanupLbMap);
1023 // Promote the loop body up if this has turned into a single iteration loop.
1024 (void)promoteIfSingleIteration(forOp: cleanupForOp);
1025
1026 // Adjust upper bound of the original loop; this is the same as the lower
1027 // bound of the cleanup loop.
1028 forOp.setUpperBound(operands: cleanupOperands, map: cleanupMap);
1029 return success();
1030}
1031
1032/// Unrolls this loop by the specified factor. Returns success if the loop
1033/// is successfully unrolled.
1034LogicalResult mlir::affine::loopUnrollByFactor(
1035 AffineForOp forOp, uint64_t unrollFactor,
1036 function_ref<void(unsigned, Operation *, OpBuilder)> annotateFn,
1037 bool cleanUpUnroll) {
1038 assert(unrollFactor > 0 && "unroll factor should be positive");
1039
1040 std::optional<uint64_t> mayBeConstantTripCount = std::nullopt;
1041 if (auto staticTripCount = forOp.getStaticTripCount())
1042 mayBeConstantTripCount = staticTripCount->getZExtValue();
1043 if (unrollFactor == 1) {
1044 if (mayBeConstantTripCount == 1 && failed(Result: promoteIfSingleIteration(forOp)))
1045 return failure();
1046 return success();
1047 }
1048
1049 // Nothing in the loop body other than the terminator.
1050 if (llvm::hasSingleElement(C&: forOp.getBody()->getOperations()))
1051 return success();
1052
1053 // If the trip count is lower than the unroll factor, no unrolled body.
1054 if (mayBeConstantTripCount && *mayBeConstantTripCount < unrollFactor) {
1055 if (cleanUpUnroll) {
1056 // Unroll the cleanup loop if cleanUpUnroll is specified.
1057 return loopUnrollFull(forOp);
1058 }
1059
1060 return failure();
1061 }
1062
1063 // Generate the cleanup loop if trip count isn't a multiple of unrollFactor.
1064 if (getLargestDivisorOfTripCount(forOp) % unrollFactor != 0) {
1065 // Loops where the lower bound is a max expression or the upper bound is
1066 // a min expression and the trip count doesn't divide the unroll factor
1067 // can't be unrolled since the lower bound of the cleanup loop in such cases
1068 // cannot be expressed as an affine function or a max over affine functions.
1069 if (forOp.getLowerBoundMap().getNumResults() != 1 ||
1070 forOp.getUpperBoundMap().getNumResults() != 1)
1071 return failure();
1072 if (cleanUpUnroll)
1073 // Force unroll including cleanup loop
1074 return loopUnrollFull(forOp);
1075 if (failed(Result: generateCleanupLoopForUnroll(forOp, unrollFactor)))
1076 assert(false && "cleanup loop lower bound map for single result lower "
1077 "and upper bound maps can always be determined");
1078 }
1079
1080 ValueRange iterArgs(forOp.getRegionIterArgs());
1081 auto yieldedValues = forOp.getBody()->getTerminator()->getOperands();
1082
1083 // Scale the step of loop being unrolled by unroll factor.
1084 int64_t step = forOp.getStepAsInt();
1085 forOp.setStep(step * unrollFactor);
1086 generateUnrolledLoop(
1087 loopBodyBlock: forOp.getBody(), forOpIV: forOp.getInductionVar(), unrollFactor,
1088 ivRemapFn: [&](unsigned i, Value iv, OpBuilder b) {
1089 // iv' = iv + i * step
1090 auto d0 = b.getAffineDimExpr(position: 0);
1091 auto bumpMap = AffineMap::get(dimCount: 1, symbolCount: 0, result: d0 + i * step);
1092 return AffineApplyOp::create(builder&: b, location: forOp.getLoc(), map: bumpMap, mapOperands: iv);
1093 },
1094 /*annotateFn=*/annotateFn,
1095 /*iterArgs=*/iterArgs, /*yieldedValues=*/yieldedValues);
1096
1097 // Promote the loop body up if this has turned into a single iteration loop.
1098 (void)promoteIfSingleIteration(forOp);
1099 return success();
1100}
1101
1102LogicalResult mlir::affine::loopUnrollJamUpToFactor(AffineForOp forOp,
1103 uint64_t unrollJamFactor) {
1104 std::optional<APInt> mayBeConstantTripCount = forOp.getStaticTripCount();
1105 if (mayBeConstantTripCount.has_value() &&
1106 mayBeConstantTripCount->getZExtValue() < unrollJamFactor)
1107 return loopUnrollJamByFactor(forOp, unrollJamFactor: mayBeConstantTripCount->getZExtValue());
1108 return loopUnrollJamByFactor(forOp, unrollJamFactor);
1109}
1110
1111/// Check if all control operands of all loops are defined outside of `forOp`
1112/// and return false if not.
1113static bool areInnerBoundsInvariant(AffineForOp forOp) {
1114 auto walkResult = forOp.walk(callback: [&](AffineForOp aForOp) {
1115 for (auto controlOperand : aForOp.getControlOperands()) {
1116 if (!forOp.isDefinedOutsideOfLoop(value: controlOperand))
1117 return WalkResult::interrupt();
1118 }
1119 return WalkResult::advance();
1120 });
1121 return !walkResult.wasInterrupted();
1122}
1123
1124/// Unrolls and jams this loop by the specified factor.
1125LogicalResult mlir::affine::loopUnrollJamByFactor(AffineForOp forOp,
1126 uint64_t unrollJamFactor) {
1127 assert(unrollJamFactor > 0 && "unroll jam factor should be positive");
1128
1129 std::optional<uint64_t> mayBeConstantTripCount = std::nullopt;
1130 if (auto staticTripCount = forOp.getStaticTripCount())
1131 mayBeConstantTripCount = staticTripCount->getZExtValue();
1132 if (unrollJamFactor == 1) {
1133 if (mayBeConstantTripCount == 1 && failed(Result: promoteIfSingleIteration(forOp)))
1134 return failure();
1135 return success();
1136 }
1137
1138 // Nothing in the loop body other than the terminator.
1139 if (llvm::hasSingleElement(C&: forOp.getBody()->getOperations()))
1140 return success();
1141
1142 // If the trip count is lower than the unroll jam factor, no unroll jam.
1143 if (mayBeConstantTripCount && *mayBeConstantTripCount < unrollJamFactor) {
1144 LDBG() << "[failed] trip count < unroll-jam factor";
1145 return failure();
1146 }
1147
1148 // If any control operand of any inner loop of `forOp` is defined within
1149 // `forOp`, no unroll jam.
1150 if (!areInnerBoundsInvariant(forOp))
1151 return failure();
1152
1153 // Gather all sub-blocks to jam upon the loop being unrolled.
1154 JamBlockGatherer<AffineForOp> jbg;
1155 jbg.walk(op: forOp);
1156 auto &subBlocks = jbg.subBlocks;
1157
1158 // Collect loops with iter_args.
1159 SmallVector<AffineForOp, 4> loopsWithIterArgs;
1160 forOp.walk(callback: [&](AffineForOp aForOp) {
1161 if (aForOp.getNumIterOperands() > 0)
1162 loopsWithIterArgs.push_back(Elt: aForOp);
1163 });
1164
1165 // Get supported reductions to be used for creating reduction ops at the end.
1166 SmallVector<LoopReduction> reductions;
1167 if (forOp.getNumIterOperands() > 0)
1168 getSupportedReductions(forOp, supportedReductions&: reductions);
1169
1170 // Generate the cleanup loop if trip count isn't a multiple of
1171 // unrollJamFactor.
1172 if (getLargestDivisorOfTripCount(forOp) % unrollJamFactor != 0) {
1173 // Loops where the lower bound is a max expression or the upper bound is
1174 // a min expression and the trip count doesn't divide the unroll factor
1175 // can't be unrolled since the lower bound of the cleanup loop in such cases
1176 // cannot be expressed as an affine function or a max over affine functions.
1177 if (forOp.getLowerBoundMap().getNumResults() != 1 ||
1178 forOp.getUpperBoundMap().getNumResults() != 1)
1179 return failure();
1180 if (failed(Result: generateCleanupLoopForUnroll(forOp, unrollFactor: unrollJamFactor)))
1181 assert(false && "cleanup loop lower bound map for single result lower "
1182 "and upper bound maps can always be determined");
1183 }
1184
1185 // `operandMaps[i - 1]` carries old->new operand mapping for the ith unrolled
1186 // iteration. There are (`unrollJamFactor` - 1) iterations.
1187 SmallVector<IRMapping, 4> operandMaps(unrollJamFactor - 1);
1188
1189 // For any loop with iter_args, replace it with a new loop that has
1190 // `unrollJamFactor` copies of its iterOperands, iter_args and yield
1191 // operands.
1192 SmallVector<AffineForOp, 4> newLoopsWithIterArgs;
1193 IRRewriter rewriter(forOp.getContext());
1194 for (AffineForOp oldForOp : loopsWithIterArgs) {
1195 SmallVector<Value> dupIterOperands, dupYieldOperands;
1196 ValueRange oldIterOperands = oldForOp.getInits();
1197 ValueRange oldIterArgs = oldForOp.getRegionIterArgs();
1198 ValueRange oldYieldOperands =
1199 cast<AffineYieldOp>(Val: oldForOp.getBody()->getTerminator()).getOperands();
1200 // Get additional iterOperands, iterArgs, and yield operands. We will
1201 // fix iterOperands and yield operands after cloning of sub-blocks.
1202 for (unsigned i = unrollJamFactor - 1; i >= 1; --i) {
1203 dupIterOperands.append(in_start: oldIterOperands.begin(), in_end: oldIterOperands.end());
1204 dupYieldOperands.append(in_start: oldYieldOperands.begin(), in_end: oldYieldOperands.end());
1205 }
1206 // Create a new loop with additional iterOperands, iter_args and yield
1207 // operands. This new loop will take the loop body of the original loop.
1208 bool forOpReplaced = oldForOp == forOp;
1209 AffineForOp newForOp =
1210 cast<AffineForOp>(Val: *oldForOp.replaceWithAdditionalYields(
1211 rewriter, newInitOperands: dupIterOperands, /*replaceInitOperandUsesInLoop=*/false,
1212 newYieldValuesFn: [&](OpBuilder &b, Location loc, ArrayRef<BlockArgument> newBbArgs) {
1213 return dupYieldOperands;
1214 }));
1215 newLoopsWithIterArgs.push_back(Elt: newForOp);
1216 // `forOp` has been replaced with a new loop.
1217 if (forOpReplaced)
1218 forOp = newForOp;
1219 // Update `operandMaps` for `newForOp` iterArgs and results.
1220 ValueRange newIterArgs = newForOp.getRegionIterArgs();
1221 unsigned oldNumIterArgs = oldIterArgs.size();
1222 ValueRange newResults = newForOp.getResults();
1223 unsigned oldNumResults = newResults.size() / unrollJamFactor;
1224 assert(oldNumIterArgs == oldNumResults &&
1225 "oldNumIterArgs must be the same as oldNumResults");
1226 for (unsigned i = unrollJamFactor - 1; i >= 1; --i) {
1227 for (unsigned j = 0; j < oldNumIterArgs; ++j) {
1228 // `newForOp` has `unrollJamFactor` - 1 new sets of iterArgs and
1229 // results. Update `operandMaps[i - 1]` to map old iterArgs and results
1230 // to those in the `i`th new set.
1231 operandMaps[i - 1].map(from: newIterArgs[j],
1232 to: newIterArgs[i * oldNumIterArgs + j]);
1233 operandMaps[i - 1].map(from: newResults[j],
1234 to: newResults[i * oldNumResults + j]);
1235 }
1236 }
1237 }
1238
1239 // Scale the step of loop being unroll-jammed by the unroll-jam factor.
1240 int64_t step = forOp.getStepAsInt();
1241 forOp.setStep(step * unrollJamFactor);
1242
1243 auto forOpIV = forOp.getInductionVar();
1244 // Unroll and jam (appends unrollJamFactor - 1 additional copies).
1245 for (unsigned i = unrollJamFactor - 1; i >= 1; --i) {
1246 for (auto &subBlock : subBlocks) {
1247 // Builder to insert unroll-jammed bodies. Insert right at the end of
1248 // sub-block.
1249 OpBuilder builder(subBlock.first->getBlock(), std::next(x: subBlock.second));
1250
1251 // If the induction variable is used, create a remapping to the value for
1252 // this unrolled instance.
1253 if (!forOpIV.use_empty()) {
1254 // iv' = iv + i * step, i = 1 to unrollJamFactor-1.
1255 auto d0 = builder.getAffineDimExpr(position: 0);
1256 auto bumpMap = AffineMap::get(dimCount: 1, symbolCount: 0, result: d0 + i * step);
1257 auto ivUnroll =
1258 AffineApplyOp::create(builder, location: forOp.getLoc(), map: bumpMap, mapOperands: forOpIV);
1259 operandMaps[i - 1].map(from: forOpIV, to: ivUnroll);
1260 }
1261 // Clone the sub-block being unroll-jammed.
1262 for (auto it = subBlock.first; it != std::next(x: subBlock.second); ++it)
1263 builder.clone(op&: *it, mapper&: operandMaps[i - 1]);
1264 }
1265 // Fix iterOperands and yield op operands of newly created loops.
1266 for (auto newForOp : newLoopsWithIterArgs) {
1267 unsigned oldNumIterOperands =
1268 newForOp.getNumIterOperands() / unrollJamFactor;
1269 unsigned numControlOperands = newForOp.getNumControlOperands();
1270 auto yieldOp = cast<AffineYieldOp>(Val: newForOp.getBody()->getTerminator());
1271 unsigned oldNumYieldOperands = yieldOp.getNumOperands() / unrollJamFactor;
1272 assert(oldNumIterOperands == oldNumYieldOperands &&
1273 "oldNumIterOperands must be the same as oldNumYieldOperands");
1274 for (unsigned j = 0; j < oldNumIterOperands; ++j) {
1275 // The `i`th duplication of an old iterOperand or yield op operand
1276 // needs to be replaced with a mapped value from `operandMaps[i - 1]`
1277 // if such mapped value exists.
1278 newForOp.setOperand(i: numControlOperands + i * oldNumIterOperands + j,
1279 value: operandMaps[i - 1].lookupOrDefault(
1280 from: newForOp.getOperand(i: numControlOperands + j)));
1281 yieldOp.setOperand(
1282 i: i * oldNumYieldOperands + j,
1283 value: operandMaps[i - 1].lookupOrDefault(from: yieldOp.getOperand(i: j)));
1284 }
1285 }
1286 }
1287 if (forOp.getNumResults() > 0) {
1288 // Create reduction ops to combine every `unrollJamFactor` related results
1289 // into one value. For example, for %0:2 = affine.for ... and addf, we add
1290 // %1 = arith.addf %0#0, %0#1, and replace the following uses of %0#0 with
1291 // %1.
1292 rewriter.setInsertionPointAfter(forOp);
1293 auto loc = forOp.getLoc();
1294 unsigned oldNumResults = forOp.getNumResults() / unrollJamFactor;
1295 for (LoopReduction &reduction : reductions) {
1296 unsigned pos = reduction.iterArgPosition;
1297 Value lhs = forOp.getResult(i: pos);
1298 Value rhs;
1299 SmallPtrSet<Operation *, 4> newOps;
1300 for (unsigned i = unrollJamFactor - 1; i >= 1; --i) {
1301 rhs = forOp.getResult(i: i * oldNumResults + pos);
1302 // Create ops based on reduction type.
1303 lhs = arith::getReductionOp(op: reduction.kind, builder&: rewriter, loc, lhs, rhs);
1304 if (!lhs)
1305 return failure();
1306 Operation *op = lhs.getDefiningOp();
1307 assert(op && "Reduction op should have been created");
1308 newOps.insert(Ptr: op);
1309 }
1310 // Replace all uses except those in newly created reduction ops.
1311 forOp.getResult(i: pos).replaceAllUsesExcept(newValue: lhs, exceptions: newOps);
1312 }
1313 }
1314
1315 // Promote the loop body up if this has turned into a single iteration loop.
1316 (void)promoteIfSingleIteration(forOp);
1317 return success();
1318}
1319
1320/// Performs loop interchange on 'forOpA' and 'forOpB', where 'forOpB' is
1321/// nested within 'forOpA' as the only non-terminator operation in its block.
1322void mlir::affine::interchangeLoops(AffineForOp forOpA, AffineForOp forOpB) {
1323 assert(&*forOpA.getBody()->begin() == forOpB.getOperation());
1324 auto &forOpABody = forOpA.getBody()->getOperations();
1325 auto &forOpBBody = forOpB.getBody()->getOperations();
1326
1327 // 1) Splice forOpA's non-terminator operations (which is just forOpB) just
1328 // before forOpA (in ForOpA's parent's block) this should leave 'forOpA's
1329 // body containing only the terminator.
1330 forOpA->getBlock()->getOperations().splice(where: Block::iterator(forOpA),
1331 L2&: forOpABody, first: forOpABody.begin(),
1332 last: std::prev(x: forOpABody.end()));
1333 // 2) Splice forOpB's non-terminator operations into the beginning of forOpA's
1334 // body (this leaves forOpB's body containing only the terminator).
1335 forOpABody.splice(where: forOpABody.begin(), L2&: forOpBBody, first: forOpBBody.begin(),
1336 last: std::prev(x: forOpBBody.end()));
1337 // 3) Splice forOpA into the beginning of forOpB's body.
1338 forOpBBody.splice(where: forOpBBody.begin(), L2&: forOpA->getBlock()->getOperations(),
1339 first: Block::iterator(forOpA));
1340}
1341
1342// Checks each dependence component against the permutation to see if the
1343// desired loop interchange would violate dependences by making the
1344// dependence component lexicographically negative.
1345static bool checkLoopInterchangeDependences(
1346 const std::vector<SmallVector<DependenceComponent, 2>> &depCompsVec,
1347 ArrayRef<AffineForOp> loops, ArrayRef<unsigned> loopPermMap) {
1348 // Invert permutation map.
1349 unsigned maxLoopDepth = loops.size();
1350 SmallVector<unsigned, 4> loopPermMapInv;
1351 loopPermMapInv.resize(N: maxLoopDepth);
1352 for (unsigned i = 0; i < maxLoopDepth; ++i)
1353 loopPermMapInv[loopPermMap[i]] = i;
1354
1355 // Check each dependence component against the permutation to see if the
1356 // desired loop interchange permutation would make the dependence vectors
1357 // lexicographically negative.
1358 // Example 1: [-1, 1][0, 0]
1359 // Example 2: [0, 0][-1, 1]
1360 for (const auto &depComps : depCompsVec) {
1361 assert(depComps.size() >= maxLoopDepth);
1362 // Check if the first non-zero dependence component is positive.
1363 // This iterates through loops in the desired order.
1364 for (unsigned j = 0; j < maxLoopDepth; ++j) {
1365 unsigned permIndex = loopPermMapInv[j];
1366 assert(depComps[permIndex].lb);
1367 int64_t depCompLb = *depComps[permIndex].lb;
1368 if (depCompLb > 0)
1369 break;
1370 if (depCompLb < 0)
1371 return false;
1372 }
1373 }
1374 return true;
1375}
1376
1377/// Checks if the loop interchange permutation 'loopPermMap' of the perfectly
1378/// nested sequence of loops in 'loops' would violate dependences.
1379bool mlir::affine::isValidLoopInterchangePermutation(
1380 ArrayRef<AffineForOp> loops, ArrayRef<unsigned> loopPermMap) {
1381 assert(loopPermMap.size() == loops.size() && "invalid loop perm map");
1382 unsigned maxLoopDepth = loops.size();
1383 if (maxLoopDepth == 1)
1384 return true;
1385
1386 // We cannot guarantee the validity of the interchange if the loops have
1387 // iter_args, since the dependence analysis does not take them into account.
1388 // Conservatively return false in such cases.
1389 if (llvm::any_of(Range&: loops, P: [](AffineForOp loop) {
1390 return loop.getNumIterOperands() > 0;
1391 }))
1392 return false;
1393
1394 // Gather dependence components for dependences between all ops in loop nest
1395 // rooted at 'loops[0]', at loop depths in range [1, maxLoopDepth].
1396 std::vector<SmallVector<DependenceComponent, 2>> depCompsVec;
1397 getDependenceComponents(forOp: loops[0], maxLoopDepth, depCompsVec: &depCompsVec);
1398 return checkLoopInterchangeDependences(depCompsVec, loops, loopPermMap);
1399}
1400
1401/// Returns true if `loops` is a perfectly nested loop nest, where loops appear
1402/// in it from outermost to innermost.
1403[[maybe_unused]] bool
1404mlir::affine::isPerfectlyNested(ArrayRef<AffineForOp> loops) {
1405 assert(!loops.empty() && "no loops provided");
1406
1407 // We already know that the block can't be empty.
1408 auto hasTwoElements = [](Block *block) {
1409 auto secondOpIt = std::next(x: block->begin());
1410 return secondOpIt != block->end() && &*secondOpIt == &block->back();
1411 };
1412
1413 auto enclosingLoop = loops.front();
1414 for (auto loop : loops.drop_front()) {
1415 auto parentForOp = dyn_cast<AffineForOp>(Val: loop->getParentOp());
1416 // parentForOp's body should be just this loop and the terminator.
1417 if (parentForOp != enclosingLoop || !hasTwoElements(parentForOp.getBody()))
1418 return false;
1419 enclosingLoop = loop;
1420 }
1421 return true;
1422}
1423
1424// input[i] should move from position i -> permMap[i]. Returns the position in
1425// `input` that becomes the new outermost loop.
1426unsigned mlir::affine::permuteLoops(ArrayRef<AffineForOp> input,
1427 ArrayRef<unsigned> permMap) {
1428 assert(input.size() == permMap.size() && "invalid permutation map size");
1429 // Check whether the permutation spec is valid. This is a small vector - we'll
1430 // just sort and check if it's iota.
1431 SmallVector<unsigned, 4> checkPermMap(permMap);
1432 llvm::sort(C&: checkPermMap);
1433 if (llvm::any_of(Range: llvm::enumerate(First&: checkPermMap),
1434 P: [](const auto &en) { return en.value() != en.index(); }))
1435 assert(false && "invalid permutation map");
1436
1437 // Nothing to do.
1438 if (input.size() < 2)
1439 return 0;
1440
1441 assert(isPerfectlyNested(input) && "input not perfectly nested");
1442
1443 // Compute the inverse mapping, invPermMap: since input[i] goes to position
1444 // permMap[i], position i of the permuted nest is at input[invPermMap[i]].
1445 SmallVector<std::pair<unsigned, unsigned>, 4> invPermMap;
1446 for (unsigned i = 0, e = input.size(); i < e; ++i)
1447 invPermMap.push_back(Elt: {permMap[i], i});
1448 llvm::sort(C&: invPermMap);
1449
1450 // Move the innermost loop body to the loop that would be the innermost in the
1451 // permuted nest (only if the innermost loop is going to change).
1452 if (permMap.back() != input.size() - 1) {
1453 Block *destBody = ((AffineForOp)input[invPermMap.back().second]).getBody();
1454 Block *srcBody = ((AffineForOp)input.back()).getBody();
1455 destBody->getOperations().splice(where: destBody->begin(),
1456 L2&: srcBody->getOperations(), first: srcBody->begin(),
1457 last: std::prev(x: srcBody->end()));
1458 }
1459
1460 // We'll move each loop in `input` in the reverse order so that its body is
1461 // empty when we are moving it; this incurs zero copies and no erasing.
1462 for (int i = input.size() - 1; i >= 0; --i) {
1463 // If this has to become the outermost loop after permutation, add it to the
1464 // parent block of the original root.
1465 if (permMap[i] == 0) {
1466 // If the root remains the same, nothing to do.
1467 if (i == 0)
1468 continue;
1469 // Make input[i] the new outermost loop moving it into parentBlock.
1470 auto *parentBlock = input[0]->getBlock();
1471 parentBlock->getOperations().splice(where: Block::iterator(input[0]),
1472 L2&: input[i]->getBlock()->getOperations(),
1473 first: Block::iterator(input[i]));
1474 continue;
1475 }
1476
1477 // If the parent in the permuted order is the same as in the original,
1478 // nothing to do.
1479 unsigned parentPosInInput = invPermMap[permMap[i] - 1].second;
1480 if (i > 0 && static_cast<unsigned>(i - 1) == parentPosInInput)
1481 continue;
1482
1483 // Move input[i] to its surrounding loop in the transformed nest.
1484 auto *destBody = ((AffineForOp)input[parentPosInInput]).getBody();
1485 destBody->getOperations().splice(where: destBody->begin(),
1486 L2&: input[i]->getBlock()->getOperations(),
1487 first: Block::iterator(input[i]));
1488 }
1489
1490 return invPermMap[0].second;
1491}
1492
1493// Sinks all sequential loops to the innermost levels (while preserving
1494// relative order among them) and moves all parallel loops to the
1495// outermost (while again preserving relative order among them).
1496AffineForOp mlir::affine::sinkSequentialLoops(AffineForOp forOp) {
1497 SmallVector<AffineForOp, 4> loops;
1498 getPerfectlyNestedLoops(nestedLoops&: loops, root: forOp);
1499 if (loops.size() < 2)
1500 return forOp;
1501
1502 // Gather dependence components for dependences between all ops in loop nest
1503 // rooted at 'loops[0]', at loop depths in range [1, maxLoopDepth].
1504 unsigned maxLoopDepth = loops.size();
1505 std::vector<SmallVector<DependenceComponent, 2>> depCompsVec;
1506 getDependenceComponents(forOp: loops[0], maxLoopDepth, depCompsVec: &depCompsVec);
1507
1508 // Mark loops as either parallel or sequential.
1509 SmallVector<bool, 8> isParallelLoop(maxLoopDepth, true);
1510 for (auto &depComps : depCompsVec) {
1511 assert(depComps.size() >= maxLoopDepth);
1512 for (unsigned j = 0; j < maxLoopDepth; ++j) {
1513 DependenceComponent &depComp = depComps[j];
1514 assert(depComp.lb.has_value() && depComp.ub.has_value());
1515 if (*depComp.lb != 0 || *depComp.ub != 0)
1516 isParallelLoop[j] = false;
1517 }
1518 }
1519
1520 unsigned numParallelLoops = llvm::count(Range&: isParallelLoop, Element: true);
1521
1522 // Compute permutation of loops that sinks sequential loops (and thus raises
1523 // parallel loops) while preserving relative order.
1524 SmallVector<unsigned, 4> loopPermMap(maxLoopDepth);
1525 unsigned nextSequentialLoop = numParallelLoops;
1526 unsigned nextParallelLoop = 0;
1527 for (unsigned i = 0; i < maxLoopDepth; ++i) {
1528 if (isParallelLoop[i]) {
1529 loopPermMap[i] = nextParallelLoop++;
1530 } else {
1531 loopPermMap[i] = nextSequentialLoop++;
1532 }
1533 }
1534
1535 // Check if permutation 'loopPermMap' would violate dependences.
1536 if (!checkLoopInterchangeDependences(depCompsVec, loops, loopPermMap))
1537 return forOp;
1538 // Perform loop interchange according to permutation 'loopPermMap'.
1539 unsigned loopNestRootIndex = permuteLoops(input: loops, permMap: loopPermMap);
1540 return loops[loopNestRootIndex];
1541}
1542
1543// Factors out common behavior to add a new `iv` (resp. `iv` + `offset`) to the
1544// lower (resp. upper) loop bound. When called for both the lower and upper
1545// bounds, the resulting IR resembles:
1546//
1547// ```mlir
1548// affine.for %i = max (`iv, ...) to min (`iv` + `offset`) {
1549// ...
1550// }
1551// ```
1552static void augmentMapAndBounds(OpBuilder &b, Value iv, AffineMap *map,
1553 SmallVector<Value, 4> *operands,
1554 int64_t offset = 0) {
1555 auto bounds = llvm::to_vector<4>(Range: map->getResults());
1556 bounds.push_back(Elt: b.getAffineDimExpr(position: map->getNumDims()) + offset);
1557 operands->insert(I: operands->begin() + map->getNumDims(), Elt: iv);
1558 *map = AffineMap::get(dimCount: map->getNumDims() + 1, symbolCount: map->getNumSymbols(), results: bounds,
1559 context: b.getContext());
1560 canonicalizeMapAndOperands(map, operands);
1561}
1562
1563// Stripmines `forOp` by `factor` and sinks it under each of the `targets`.
1564// Stripmine-sink is a primitive building block for generalized tiling of
1565// imperfectly nested loops.
1566// This transformation is purely mechanical and does not check legality,
1567// profitability or even structural correctness. It is the user's
1568// responsibility to specify `targets` that are dominated by `forOp`.
1569// Returns the new AffineForOps, one per `targets`, nested immediately under
1570// each of the `targets`.
1571static SmallVector<AffineForOp, 8>
1572stripmineSink(AffineForOp forOp, uint64_t factor,
1573 ArrayRef<AffineForOp> targets) {
1574 auto originalStep = forOp.getStepAsInt();
1575 auto scaledStep = originalStep * factor;
1576 forOp.setStep(scaledStep);
1577
1578 OpBuilder b(forOp->getBlock(), std::next(x: Block::iterator(forOp)));
1579
1580 // Lower-bound map creation.
1581 auto lbMap = forOp.getLowerBoundMap();
1582 SmallVector<Value, 4> lbOperands(forOp.getLowerBoundOperands());
1583 augmentMapAndBounds(b, iv: forOp.getInductionVar(), map: &lbMap, operands: &lbOperands);
1584
1585 // Upper-bound map creation.
1586 auto ubMap = forOp.getUpperBoundMap();
1587 SmallVector<Value, 4> ubOperands(forOp.getUpperBoundOperands());
1588 augmentMapAndBounds(b, iv: forOp.getInductionVar(), map: &ubMap, operands: &ubOperands,
1589 /*offset=*/scaledStep);
1590
1591 auto iv = forOp.getInductionVar();
1592 SmallVector<AffineForOp, 8> innerLoops;
1593 for (auto t : targets) {
1594 // Insert newForOp before the terminator of `t`.
1595 auto b = OpBuilder::atBlockTerminator(block: t.getBody());
1596 auto newForOp = AffineForOp::create(builder&: b, location: t.getLoc(), lbOperands, lbMap,
1597 ubOperands, ubMap, step: originalStep);
1598 auto begin = t.getBody()->begin();
1599 // Skip terminator and `newForOp` which is just before the terminator.
1600 auto nOps = t.getBody()->getOperations().size() - 2;
1601 newForOp.getBody()->getOperations().splice(
1602 where: newForOp.getBody()->getOperations().begin(),
1603 L2&: t.getBody()->getOperations(), first: begin, last: std::next(x: begin, n: nOps));
1604 replaceAllUsesInRegionWith(orig: iv, replacement: newForOp.getInductionVar(),
1605 region&: newForOp.getRegion());
1606 innerLoops.push_back(Elt: newForOp);
1607 }
1608
1609 return innerLoops;
1610}
1611
1612SmallVector<SmallVector<AffineForOp, 8>, 8>
1613mlir::affine::tile(ArrayRef<AffineForOp> forOps, ArrayRef<uint64_t> sizes,
1614 ArrayRef<AffineForOp> targets) {
1615 SmallVector<SmallVector<AffineForOp, 8>, 8> res;
1616 SmallVector<AffineForOp, 8> currentTargets(targets);
1617 for (auto it : llvm::zip(t&: forOps, u&: sizes)) {
1618 auto step = stripmineSink(forOp: std::get<0>(t&: it), factor: std::get<1>(t&: it), targets: currentTargets);
1619 res.push_back(Elt: step);
1620 currentTargets = std::move(step);
1621 }
1622 return res;
1623}
1624
1625SmallVector<AffineForOp, 8> mlir::affine::tile(ArrayRef<AffineForOp> forOps,
1626 ArrayRef<uint64_t> sizes,
1627 AffineForOp target) {
1628 SmallVector<AffineForOp, 8> res;
1629 for (auto loops : tile(forOps, sizes, targets: ArrayRef<AffineForOp>(target)))
1630 res.push_back(Elt: llvm::getSingleElement(C&: loops));
1631 return res;
1632}
1633
1634LogicalResult mlir::affine::coalesceLoops(MutableArrayRef<AffineForOp> loops) {
1635 if (loops.size() < 2)
1636 return success();
1637
1638 AffineForOp innermost = loops.back();
1639 AffineForOp outermost = loops.front();
1640 AffineBound ub = outermost.getUpperBound();
1641 AffineMap origUbMap = ub.getMap();
1642 Location loc = outermost.getLoc();
1643 OpBuilder builder(outermost);
1644 for (AffineForOp loop : loops) {
1645 // We only work on normalized loops.
1646 if (loop.getStepAsInt() != 1 || !loop.hasConstantLowerBound() ||
1647 loop.getConstantLowerBound() != 0)
1648 return failure();
1649 }
1650 SmallVector<Value, 4> upperBoundSymbols;
1651 SmallVector<Value, 4> ubOperands(ub.getOperands().begin(),
1652 ub.getOperands().end());
1653
1654 // 1. Store the upper bound of the outermost loop in a variable.
1655 Value prev;
1656 if (!llvm::hasSingleElement(C: origUbMap.getResults()))
1657 prev = AffineMinOp::create(builder, location: loc, map: origUbMap, operands: ubOperands);
1658 else
1659 prev = AffineApplyOp::create(builder, location: loc, map: origUbMap, mapOperands: ubOperands);
1660 upperBoundSymbols.push_back(Elt: prev);
1661
1662 // 2. Emit code computing the upper bound of the coalesced loop as product of
1663 // the number of iterations of all loops.
1664 for (AffineForOp loop : loops.drop_front()) {
1665 ub = loop.getUpperBound();
1666 origUbMap = ub.getMap();
1667 ubOperands = ub.getOperands();
1668 Value upperBound;
1669 // If upper bound map has more than one result, take their minimum.
1670 if (!llvm::hasSingleElement(C: origUbMap.getResults()))
1671 upperBound = AffineMinOp::create(builder, location: loc, map: origUbMap, operands: ubOperands);
1672 else
1673 upperBound = AffineApplyOp::create(builder, location: loc, map: origUbMap, mapOperands: ubOperands);
1674 upperBoundSymbols.push_back(Elt: upperBound);
1675 SmallVector<Value, 4> operands;
1676 operands.push_back(Elt: prev);
1677 operands.push_back(Elt: upperBound);
1678 // Maintain running product of loop upper bounds.
1679 prev = AffineApplyOp::create(
1680 builder, location: loc,
1681 map: AffineMap::get(/*dimCount=*/1,
1682 /*symbolCount=*/1,
1683 result: builder.getAffineDimExpr(position: 0) *
1684 builder.getAffineSymbolExpr(position: 0)),
1685 mapOperands: operands);
1686 }
1687 // Set upper bound of the coalesced loop.
1688 AffineMap newUbMap = AffineMap::get(
1689 /*dimCount=*/0,
1690 /*symbolCount=*/1, results: builder.getAffineSymbolExpr(position: 0), context: builder.getContext());
1691 outermost.setUpperBound(operands: prev, map: newUbMap);
1692
1693 builder.setInsertionPointToStart(outermost.getBody());
1694
1695 // 3. Remap induction variables. For each original loop, the value of the
1696 // induction variable can be obtained by dividing the induction variable of
1697 // the linearized loop by the total number of iterations of the loops nested
1698 // in it modulo the number of iterations in this loop (remove the values
1699 // related to the outer loops):
1700 // iv_i = floordiv(iv_linear, product-of-loop-ranges-until-i) mod range_i.
1701 // Compute these iteratively from the innermost loop by creating a "running
1702 // quotient" of division by the range.
1703 Value previous = outermost.getInductionVar();
1704 for (unsigned idx = loops.size(); idx > 0; --idx) {
1705 if (idx != loops.size()) {
1706 SmallVector<Value, 4> operands;
1707 operands.push_back(Elt: previous);
1708 operands.push_back(Elt: upperBoundSymbols[idx]);
1709 previous = AffineApplyOp::create(builder, location: loc,
1710 map: AffineMap::get(
1711 /*dimCount=*/1, /*symbolCount=*/1,
1712 result: builder.getAffineDimExpr(position: 0).floorDiv(
1713 other: builder.getAffineSymbolExpr(position: 0))),
1714 mapOperands: operands);
1715 }
1716 // Modified value of the induction variables of the nested loops after
1717 // coalescing.
1718 Value inductionVariable;
1719 if (idx == 1) {
1720 inductionVariable = previous;
1721 } else {
1722 SmallVector<Value, 4> applyOperands;
1723 applyOperands.push_back(Elt: previous);
1724 applyOperands.push_back(Elt: upperBoundSymbols[idx - 1]);
1725 inductionVariable = AffineApplyOp::create(
1726 builder, location: loc,
1727 map: AffineMap::get(
1728 /*dimCount=*/1, /*symbolCount=*/1,
1729 result: builder.getAffineDimExpr(position: 0) % builder.getAffineSymbolExpr(position: 0)),
1730 mapOperands: applyOperands);
1731 }
1732 replaceAllUsesInRegionWith(orig: loops[idx - 1].getInductionVar(),
1733 replacement: inductionVariable, region&: loops.back().getRegion());
1734 }
1735
1736 // 4. Move the operations from the innermost just above the second-outermost
1737 // loop, delete the extra terminator and the second-outermost loop.
1738 AffineForOp secondOutermostLoop = loops[1];
1739 innermost.getBody()->back().erase();
1740 outermost.getBody()->getOperations().splice(
1741 where: Block::iterator(secondOutermostLoop.getOperation()),
1742 L2&: innermost.getBody()->getOperations());
1743 for (auto [iter, init] :
1744 llvm::zip_equal(t: secondOutermostLoop.getRegionIterArgs(),
1745 u: secondOutermostLoop.getInits())) {
1746 iter.replaceAllUsesWith(newValue: init);
1747 iter.dropAllUses();
1748 }
1749 secondOutermostLoop.erase();
1750 return success();
1751}
1752
1753void mlir::affine::mapLoopToProcessorIds(scf::ForOp forOp,
1754 ArrayRef<Value> processorId,
1755 ArrayRef<Value> numProcessors) {
1756 assert(processorId.size() == numProcessors.size());
1757 if (processorId.empty())
1758 return;
1759
1760 OpBuilder b(forOp);
1761 Location loc(forOp.getLoc());
1762 AffineExpr lhs, rhs;
1763 bindSymbols(ctx: forOp.getContext(), exprs&: lhs, exprs&: rhs);
1764 auto mulMap = AffineMap::get(dimCount: 0, symbolCount: 2, result: lhs * rhs);
1765 auto addMap = AffineMap::get(dimCount: 0, symbolCount: 2, result: lhs + rhs);
1766
1767 Value linearIndex = processorId.front();
1768 for (unsigned i = 1, e = processorId.size(); i < e; ++i) {
1769 auto mulApplyOp = AffineApplyOp::create(
1770 builder&: b, location: loc, map: mulMap, mapOperands: ValueRange{linearIndex, numProcessors[i]});
1771 linearIndex = AffineApplyOp::create(builder&: b, location: loc, map: addMap,
1772 mapOperands: ValueRange{mulApplyOp, processorId[i]});
1773 }
1774
1775 auto mulApplyOp = AffineApplyOp::create(
1776 builder&: b, location: loc, map: mulMap, mapOperands: ValueRange{linearIndex, forOp.getStep()});
1777 Value lb = AffineApplyOp::create(
1778 builder&: b, location: loc, map: addMap, mapOperands: ValueRange{mulApplyOp, forOp.getLowerBound()});
1779 forOp.setLowerBound(lb);
1780
1781 Value step = forOp.getStep();
1782 for (auto numProcs : numProcessors)
1783 step = AffineApplyOp::create(builder&: b, location: loc, map: mulMap, mapOperands: ValueRange{numProcs, step});
1784 forOp.setStep(step);
1785}
1786
1787/// Given a memref region, determine the lowest depth at which transfers can be
1788/// placed for it, and return the corresponding block, start and end positions
1789/// in the block for placing incoming (read) and outgoing (write) copies
1790/// respectively. The lowest depth depends on whether the region being accessed
1791/// is hoistable with respect to one or more immediately surrounding loops.
1792static void
1793findHighestBlockForPlacement(const MemRefRegion &region, Block &block,
1794 Block::iterator &begin, Block::iterator &end,
1795 Block **copyPlacementBlock,
1796 Block::iterator *copyInPlacementStart,
1797 Block::iterator *copyOutPlacementStart) {
1798 const auto *cst = region.getConstraints();
1799 SmallVector<Value, 4> symbols;
1800 cst->getValues(start: cst->getNumDimVars(), end: cst->getNumDimAndSymbolVars(), values: &symbols);
1801
1802 SmallVector<Operation *, 4> enclosingAffineOps;
1803 getEnclosingAffineOps(op&: *block.begin(), ops: &enclosingAffineOps);
1804 // Walk up loop parents till we find an IV on which this region is
1805 // symbolic/variant or we hit `hoistGuard`.
1806 auto it = enclosingAffineOps.rbegin();
1807 AffineForOp lastInvariantFor;
1808 for (auto e = enclosingAffineOps.rend(); it != e; ++it) {
1809 Operation *enclosingOp = *it;
1810 // We can't hoist past the definition of the memref being copied.
1811 Value memref = region.memref;
1812 if (!memref.getParentRegion()->isAncestor(other: enclosingOp->getParentRegion())) {
1813 LDBG() << "memref definition will end up not dominating hoist location";
1814 break;
1815 }
1816
1817 auto affineFor = dyn_cast<AffineForOp>(Val: enclosingOp);
1818 if (!affineFor)
1819 break;
1820 // TODO: also need to be checking this for regions symbols that
1821 // aren't loop IVs, whether we are within their resp. defs' dominance scope.
1822 if (llvm::is_contained(Range&: symbols, Element: affineFor.getInductionVar()))
1823 break;
1824 lastInvariantFor = affineFor;
1825 }
1826
1827 if (it != enclosingAffineOps.rbegin()) {
1828 *copyInPlacementStart = Block::iterator(lastInvariantFor);
1829 *copyOutPlacementStart = std::next(x: *copyInPlacementStart);
1830 *copyPlacementBlock = lastInvariantFor->getBlock();
1831 } else {
1832 *copyInPlacementStart = begin;
1833 *copyOutPlacementStart = end;
1834 *copyPlacementBlock = &block;
1835 }
1836}
1837
1838// Info comprising stride and number of elements transferred every stride.
1839struct StrideInfo {
1840 int64_t stride;
1841 int64_t numEltPerStride;
1842};
1843
1844/// Returns striding information for a copy/transfer of this region with
1845/// potentially multiple striding levels from outermost to innermost. For an
1846/// n-dimensional region, there can be at most n-1 levels of striding
1847/// successively nested.
1848// TODO: make this work with non-identity layout maps.
1849static void getMultiLevelStrides(const MemRefRegion &region,
1850 ArrayRef<int64_t> bufferShape,
1851 SmallVectorImpl<StrideInfo> *strideInfos) {
1852 if (bufferShape.size() <= 1)
1853 return;
1854
1855 int64_t numEltPerStride = 1;
1856 int64_t stride = 1;
1857 for (int d = bufferShape.size() - 1; d >= 1; d--) {
1858 int64_t dimSize = cast<MemRefType>(Val: region.memref.getType()).getDimSize(idx: d);
1859 stride *= dimSize;
1860 numEltPerStride *= bufferShape[d];
1861 // A stride is needed only if the region has a shorter extent than the
1862 // memref along the dimension *and* has an extent greater than one along the
1863 // next major dimension.
1864 if (bufferShape[d] < dimSize && bufferShape[d - 1] > 1) {
1865 strideInfos->push_back(Elt: {.stride: stride, .numEltPerStride: numEltPerStride});
1866 }
1867 }
1868}
1869
1870/// Generates a point-wise copy from/to a non-zero ranked `memref' to/from
1871/// `fastMemRef' and returns the outermost AffineForOp of the copy loop nest.
1872/// `lbMaps` and `ubMaps` along with `lbOperands` and `ubOperands` hold the
1873/// lower and upper bound information for the copy loop nest. `fastBufOffsets`
1874/// contain the expressions to be subtracted out from the respective copy loop
1875/// iterators in order to index the fast buffer. If `copyOut' is true, generates
1876/// a copy-out; otherwise a copy-in. Builder `b` should be set to the point the
1877/// copy nest is inserted.
1878//
1879/// The copy-in nest is generated as follows as an example for a 2-d region:
1880/// for x = ...
1881/// for y = ...
1882/// fast_buf[x - offset_x][y - offset_y] = memref[x][y]
1883///
1884static AffineForOp
1885generatePointWiseCopy(Location loc, Value memref, Value fastMemRef,
1886 ArrayRef<AffineMap> lbMaps, ArrayRef<Value> lbOperands,
1887 ArrayRef<AffineMap> ubMaps, ArrayRef<Value> ubOperands,
1888 ArrayRef<AffineExpr> fastBufOffsets, bool isCopyOut,
1889 OpBuilder b) {
1890 assert(llvm::all_of(lbMaps, [&](AffineMap lbMap) {
1891 return lbMap.getNumInputs() == lbOperands.size();
1892 }));
1893 assert(llvm::all_of(ubMaps, [&](AffineMap ubMap) {
1894 return ubMap.getNumInputs() == ubOperands.size();
1895 }));
1896
1897 unsigned rank = cast<MemRefType>(Val: memref.getType()).getRank();
1898 // A copy nest can't be generated for 0-ranked memrefs.
1899 assert(rank != 0 && "non-zero rank memref expected");
1900 assert(lbMaps.size() == rank && "wrong number of lb maps");
1901 assert(ubMaps.size() == rank && "wrong number of ub maps");
1902
1903 SmallVector<Value, 4> memIndices;
1904 SmallVector<AffineExpr, 4> fastBufExprs;
1905 SmallVector<Value, 4> fastBufMapOperands;
1906 AffineForOp copyNestRoot;
1907 SmallVector<AffineApplyOp, 4> mayBeDeadApplys;
1908 for (unsigned d = 0; d < rank; ++d) {
1909 auto forOp = createCanonicalizedAffineForOp(b, loc, lbOperands, lbMap: lbMaps[d],
1910 ubOperands, ubMap: ubMaps[d]);
1911 if (d == 0)
1912 copyNestRoot = forOp;
1913
1914 b = OpBuilder::atBlockTerminator(block: forOp.getBody());
1915
1916 auto fastBufOffsetMap =
1917 AffineMap::get(dimCount: lbOperands.size(), symbolCount: 0, result: fastBufOffsets[d]);
1918 auto offset = AffineApplyOp::create(builder&: b, location: loc, map: fastBufOffsetMap, mapOperands: lbOperands);
1919
1920 // Construct the subscript for the fast memref being copied into/from:
1921 // x - offset_x.
1922 fastBufExprs.push_back(Elt: b.getAffineDimExpr(position: 2 * d + 1) -
1923 b.getAffineDimExpr(position: 2 * d));
1924 fastBufMapOperands.push_back(Elt: offset);
1925 fastBufMapOperands.push_back(Elt: forOp.getInductionVar());
1926 mayBeDeadApplys.push_back(Elt: offset);
1927
1928 // Subscript for the slow memref being copied.
1929 memIndices.push_back(Elt: forOp.getInductionVar());
1930 }
1931
1932 auto fastBufMap =
1933 AffineMap::get(dimCount: 2 * rank, /*symbolCount=*/0, results: fastBufExprs, context: b.getContext());
1934 fullyComposeAffineMapAndOperands(map: &fastBufMap, operands: &fastBufMapOperands);
1935 fastBufMap = simplifyAffineMap(map: fastBufMap);
1936 canonicalizeMapAndOperands(map: &fastBufMap, operands: &fastBufMapOperands);
1937
1938 // Drop any dead affine.applys.
1939 for (auto applyOp : mayBeDeadApplys)
1940 if (applyOp.use_empty())
1941 applyOp.erase();
1942
1943 if (!isCopyOut) {
1944 // Copy in.
1945 auto load = AffineLoadOp::create(builder&: b, location: loc, memref, indices: memIndices);
1946 AffineStoreOp::create(builder&: b, location: loc, valueToStore: load, memref: fastMemRef, map: fastBufMap,
1947 mapOperands: fastBufMapOperands);
1948 return copyNestRoot;
1949 }
1950
1951 // Copy out.
1952 auto load =
1953 AffineLoadOp::create(builder&: b, location: loc, memref: fastMemRef, map: fastBufMap, mapOperands: fastBufMapOperands);
1954 AffineStoreOp::create(builder&: b, location: loc, valueToStore: load, memref, indices: memIndices);
1955 return copyNestRoot;
1956}
1957
1958[[maybe_unused]] static InFlightDiagnostic emitRemarkForBlock(Block &block) {
1959 return block.getParentOp()->emitRemark();
1960}
1961
1962/// Creates a buffer in the faster memory space for the specified memref region
1963/// (memref has to be non-zero ranked); generates a copy from the lower memory
1964/// space to this one, and replaces all loads/stores in the block range
1965/// [`begin', `end') of `block' to load/store from that buffer. Returns failure
1966/// if copies could not be generated due to yet unimplemented cases.
1967/// `copyInPlacementStart` and `copyOutPlacementStart` in copyPlacementBlock
1968/// specify the insertion points where the incoming copies and outgoing copies,
1969/// respectively, should be inserted (the insertion happens right before the
1970/// insertion point). Since `begin` can itself be invalidated due to the memref
1971/// rewriting done from this method, the output argument `nBegin` is set to its
1972/// replacement (set to `begin` if no invalidation happens). Since outgoing
1973/// copies could have been inserted at `end`, the output argument `nEnd` is set
1974/// to the new end. `sizeInBytes` is set to the size of the fast buffer
1975/// allocated.
1976static LogicalResult generateCopy(
1977 const MemRefRegion &region, Block *block, Block::iterator begin,
1978 Block::iterator end, Block *copyPlacementBlock,
1979 Block::iterator copyInPlacementStart, Block::iterator copyOutPlacementStart,
1980 const AffineCopyOptions &copyOptions, DenseMap<Value, Value> &fastBufferMap,
1981 DenseSet<Operation *> &copyNests, uint64_t *sizeInBytes,
1982 Block::iterator *nBegin, Block::iterator *nEnd) {
1983 *nBegin = begin;
1984 *nEnd = end;
1985
1986 auto f = begin->getParentOfType<FunctionOpInterface>();
1987 OpBuilder topBuilder(f.getFunctionBody());
1988 Value zeroIndex = arith::ConstantIndexOp::create(builder&: topBuilder, location: f.getLoc(), value: 0);
1989
1990 *sizeInBytes = 0;
1991
1992 if (begin == end)
1993 return success();
1994
1995 // Record the last op in the block for which we are performing copy
1996 // generation. We later do the memref replacement only in [begin, lastCopyOp]
1997 // so that the original memref's used in the data movement code themselves
1998 // don't get replaced.
1999 Operation *lastCopyOp = end->getPrevNode();
2000
2001 // Is the copy out point at the end of the block where we are doing
2002 // explicit copying.
2003 bool isCopyOutAtEndOfBlock = (end == copyOutPlacementStart);
2004
2005 // Copies for read regions are going to be inserted at 'begin'.
2006 OpBuilder prologue(copyPlacementBlock, copyInPlacementStart);
2007 // Copies for write regions are going to be inserted at 'end'.
2008 OpBuilder epilogue(copyPlacementBlock, copyOutPlacementStart);
2009 OpBuilder &b = region.isWrite() ? epilogue : prologue;
2010
2011 // Builder to create constants at the top level.
2012 auto func =
2013 copyPlacementBlock->getParent()->getParentOfType<FunctionOpInterface>();
2014 OpBuilder top(func.getFunctionBody());
2015
2016 auto loc = region.loc;
2017 auto memref = region.memref;
2018 auto memRefType = cast<MemRefType>(Val: memref.getType());
2019
2020 if (!memRefType.getLayout().isIdentity()) {
2021 LDBG() << "Non-identity layout map not yet supported";
2022 return failure();
2023 }
2024
2025 // Indices to use for the copying.
2026 // Indices for the original memref being copied from/to.
2027 SmallVector<Value, 4> memIndices;
2028 // Indices for the faster buffer being copied into/from.
2029 SmallVector<Value, 4> bufIndices;
2030
2031 unsigned rank = memRefType.getRank();
2032 if (rank == 0) {
2033 LDBG() << "Non-zero ranked memrefs supported";
2034 return failure();
2035 }
2036
2037 SmallVector<int64_t, 4> fastBufferShape;
2038
2039 // Compute the extents of the buffer.
2040 SmallVector<AffineMap, 2> lbs;
2041 lbs.reserve(N: rank);
2042 std::optional<int64_t> numElements =
2043 region.getConstantBoundingSizeAndShape(shape: &fastBufferShape, lbs: &lbs);
2044 if (!numElements) {
2045 LDBG() << "Non-constant region size not supported";
2046 return failure();
2047 }
2048
2049 if (llvm::any_of(Range&: lbs, P: [](AffineMap lb) { return lb.getNumResults() > 1; })) {
2050 // This can be supported in the future if needed.
2051 LDBG() << "Max lower bound for memref region start not supported";
2052 return failure();
2053 }
2054
2055 if (*numElements == 0) {
2056 LDBG() << "Nothing to copy";
2057 return success();
2058 }
2059
2060 SmallVector<AffineMap, 4> lbMaps(rank), ubMaps(rank);
2061 for (unsigned i = 0; i < rank; ++i) {
2062 region.getLowerAndUpperBound(pos: i, lbMap&: lbMaps[i], ubMap&: ubMaps[i]);
2063 if (lbMaps[i].getNumResults() == 0 || ubMaps[i].getNumResults() == 0) {
2064 LDBG() << "Missing lower or upper bound for region along dimension: "
2065 << i;
2066 return failure();
2067 }
2068 }
2069
2070 const FlatAffineValueConstraints *cst = region.getConstraints();
2071 // 'regionSymbols' hold values that this memory region is symbolic/parametric
2072 // on; these typically include loop IVs surrounding the level at which the
2073 // copy generation is being done or other valid symbols in MLIR.
2074 SmallVector<Value, 8> regionSymbols;
2075 cst->getValues(start: rank, end: cst->getNumVars(), values: &regionSymbols);
2076
2077 // Construct the access expression for the fast memory buffer. The access
2078 // expression for a particular dimension of the fast buffer is obtained by
2079 // subtracting out the lower bound on the original memref's data region
2080 // along the corresponding dimension.
2081
2082 // Index start offsets for faster memory buffer relative to the original.
2083 SmallVector<AffineExpr, 4> fastBufOffsets;
2084 fastBufOffsets.reserve(N: rank);
2085 for (unsigned d = 0; d < rank; d++) {
2086 assert(lbs[d].getNumSymbols() == cst->getNumCols() - rank - 1 &&
2087 "incorrect bound size");
2088
2089 // Set copy start location for this dimension in the lower memory space
2090 // memref.
2091 if (lbs[d].isSingleConstant()) {
2092 auto indexVal = lbs[d].getSingleConstantResult();
2093 if (indexVal == 0) {
2094 memIndices.push_back(Elt: zeroIndex);
2095 } else {
2096 memIndices.push_back(
2097 Elt: arith::ConstantIndexOp::create(builder&: top, location: loc, value: indexVal).getResult());
2098 }
2099 } else {
2100 // The coordinate for the start location is just the lower bound along the
2101 // corresponding dimension on the memory region (stored in 'offset').
2102 // Remap all inputs of the map to dimensions uniformly since in the
2103 // generate IR we need valid affine symbols as opposed to "symbols" for
2104 // the purpose of the memref region.
2105 SmallVector<AffineExpr> symReplacements(lbs[d].getNumSymbols());
2106 for (unsigned i = 0, e = lbs[d].getNumSymbols(); i < e; ++i)
2107 symReplacements[i] = top.getAffineDimExpr(position: i);
2108 lbs[d] = lbs[d].replaceDimsAndSymbols(
2109 /*dimReplacements=*/{}, symReplacements, numResultDims: lbs[d].getNumSymbols(),
2110 /*numResultSyms=*/0);
2111 memIndices.push_back(
2112 Elt: AffineApplyOp::create(builder&: b, location: loc, map: lbs[d], mapOperands: regionSymbols));
2113 }
2114 // The fast buffer is copied into at location zero; addressing is relative.
2115 bufIndices.push_back(Elt: zeroIndex);
2116
2117 // Record the offsets since they are needed to remap the memory accesses of
2118 // the original memref further below.
2119 fastBufOffsets.push_back(Elt: lbs[d].getResult(idx: 0));
2120 }
2121
2122 // The faster memory space buffer.
2123 Value fastMemRef;
2124
2125 // Check if a buffer was already created.
2126 bool existingBuf = fastBufferMap.count(Val: memref) > 0;
2127 if (!existingBuf) {
2128 AffineMap fastBufferLayout = b.getMultiDimIdentityMap(rank);
2129 auto fastMemRefType =
2130 MemRefType::get(shape: fastBufferShape, elementType: memRefType.getElementType(),
2131 map: fastBufferLayout, memorySpaceInd: copyOptions.fastMemorySpace);
2132
2133 // Create the fast memory space buffer just before the 'affine.for'
2134 // operation.
2135 fastMemRef =
2136 memref::AllocOp::create(builder&: prologue, location: loc, memrefType: fastMemRefType).getResult();
2137 // Record it.
2138 fastBufferMap[memref] = fastMemRef;
2139 // fastMemRefType is a constant shaped memref.
2140 auto maySizeInBytes = getIntOrFloatMemRefSizeInBytes(memRefType: fastMemRefType);
2141 // We don't account for things of unknown size.
2142 *sizeInBytes = maySizeInBytes.value_or(u: 0);
2143
2144 LLVM_DEBUG(emitRemarkForBlock(*block)
2145 << "Creating fast buffer of type " << fastMemRefType
2146 << " and size " << llvm::divideCeil(*sizeInBytes, 1024)
2147 << " KiB\n");
2148 } else {
2149 // Reuse the one already created.
2150 fastMemRef = fastBufferMap[memref];
2151 }
2152
2153 auto numElementsSSA = arith::ConstantIndexOp::create(builder&: top, location: loc, value: *numElements);
2154
2155 Value dmaStride;
2156 Value numEltPerDmaStride;
2157 if (copyOptions.generateDma) {
2158 SmallVector<StrideInfo, 4> dmaStrideInfos;
2159 getMultiLevelStrides(region, bufferShape: fastBufferShape, strideInfos: &dmaStrideInfos);
2160
2161 // TODO: use all stride levels once DmaStartOp is extended for
2162 // multi-level strides.
2163 if (dmaStrideInfos.size() > 1) {
2164 LDBG() << "Only up to one level of stride supported";
2165 return failure();
2166 }
2167
2168 if (!dmaStrideInfos.empty()) {
2169 dmaStride =
2170 arith::ConstantIndexOp::create(builder&: top, location: loc, value: dmaStrideInfos[0].stride);
2171 numEltPerDmaStride = arith::ConstantIndexOp::create(
2172 builder&: top, location: loc, value: dmaStrideInfos[0].numEltPerStride);
2173 }
2174 }
2175
2176 // Create fully composed affine maps for each memref.
2177 auto memAffineMap = b.getMultiDimIdentityMap(rank: memIndices.size());
2178 fullyComposeAffineMapAndOperands(map: &memAffineMap, operands: &memIndices);
2179 auto bufAffineMap = b.getMultiDimIdentityMap(rank: bufIndices.size());
2180 fullyComposeAffineMapAndOperands(map: &bufAffineMap, operands: &bufIndices);
2181
2182 if (!copyOptions.generateDma) {
2183 // Point-wise copy generation.
2184 auto copyNest =
2185 generatePointWiseCopy(loc, memref, fastMemRef, lbMaps,
2186 /*lbOperands=*/regionSymbols, ubMaps,
2187 /*ubOperands=*/regionSymbols, fastBufOffsets,
2188 /*isCopyOut=*/region.isWrite(), b);
2189
2190 // Record this so that we can skip it from yet another copy.
2191 copyNests.insert(V: copyNest);
2192
2193 // Since new ops are being appended (for copy out's), adjust the end to
2194 // mark end of block range being processed if necessary.
2195 if (region.isWrite() && isCopyOutAtEndOfBlock)
2196 *nEnd = Block::iterator(copyNest.getOperation());
2197 } else {
2198 // DMA generation.
2199 // Create a tag (single element 1-d memref) for the DMA.
2200 auto tagMemRefType = MemRefType::get(shape: {1}, elementType: top.getIntegerType(width: 32), map: {},
2201 memorySpaceInd: copyOptions.tagMemorySpace);
2202 auto tagMemRef = memref::AllocOp::create(builder&: prologue, location: loc, memrefType: tagMemRefType);
2203
2204 SmallVector<Value, 4> tagIndices({zeroIndex});
2205 auto tagAffineMap = b.getMultiDimIdentityMap(rank: tagIndices.size());
2206 fullyComposeAffineMapAndOperands(map: &tagAffineMap, operands: &tagIndices);
2207 if (!region.isWrite()) {
2208 // DMA non-blocking read from original buffer to fast buffer.
2209 AffineDmaStartOp::create(builder&: b, location: loc, srcMemRef: memref, srcMap: memAffineMap, srcIndices: memIndices,
2210 destMemRef: fastMemRef, dstMap: bufAffineMap, destIndices: bufIndices, tagMemRef,
2211 tagMap: tagAffineMap, tagIndices, numElements: numElementsSSA,
2212 stride: dmaStride, elementsPerStride: numEltPerDmaStride);
2213 } else {
2214 // DMA non-blocking write from fast buffer to the original memref.
2215 auto op = AffineDmaStartOp::create(
2216 builder&: b, location: loc, srcMemRef: fastMemRef, srcMap: bufAffineMap, srcIndices: bufIndices, destMemRef: memref, dstMap: memAffineMap,
2217 destIndices: memIndices, tagMemRef, tagMap: tagAffineMap, tagIndices, numElements: numElementsSSA,
2218 stride: dmaStride, elementsPerStride: numEltPerDmaStride);
2219 // Since new ops may be appended at 'end' (for outgoing DMAs), adjust the
2220 // end to mark end of block range being processed.
2221 if (isCopyOutAtEndOfBlock)
2222 *nEnd = Block::iterator(op.getOperation());
2223 }
2224
2225 // Matching DMA wait to block on completion; tag always has a 0 index.
2226 AffineDmaWaitOp::create(builder&: b, location: loc, tagMemRef, tagMap: tagAffineMap, tagIndices: zeroIndex,
2227 numElements: numElementsSSA);
2228
2229 // Generate dealloc for the tag.
2230 auto tagDeallocOp = memref::DeallocOp::create(builder&: epilogue, location: loc, memref: tagMemRef);
2231 if (*nEnd == end && isCopyOutAtEndOfBlock)
2232 // Since new ops are being appended (for outgoing DMAs), adjust the end to
2233 // mark end of range of the original.
2234 *nEnd = Block::iterator(tagDeallocOp.getOperation());
2235 }
2236
2237 // Generate dealloc for the buffer.
2238 if (!existingBuf) {
2239 auto bufDeallocOp = memref::DeallocOp::create(builder&: epilogue, location: loc, memref: fastMemRef);
2240 // When generating pointwise copies, `nEnd' has to be set to deallocOp on
2241 // the fast buffer (since it marks the new end insertion point).
2242 if (!copyOptions.generateDma && *nEnd == end && isCopyOutAtEndOfBlock)
2243 *nEnd = Block::iterator(bufDeallocOp.getOperation());
2244 }
2245
2246 // Replace all uses of the old memref with the faster one while remapping
2247 // access indices (subtracting out lower bound offsets for each dimension).
2248 // Ex: to replace load %A[%i, %j] with load %Abuf[%i - %iT, %j - %jT],
2249 // index remap will be (%i, %j) -> (%i - %iT, %j - %jT),
2250 // i.e., affine.apply (d0, d1, d2, d3) -> (d2-d0, d3-d1) (%iT, %jT, %i, %j),
2251 // and (%iT, %jT) will be the 'extraOperands' for 'rep all memref uses with'.
2252 // d2, d3 correspond to the original indices (%i, %j).
2253 SmallVector<AffineExpr, 4> remapExprs;
2254 remapExprs.reserve(N: rank);
2255 for (unsigned i = 0; i < rank; i++) {
2256 // The starting operands of indexRemap will be regionSymbols (the symbols on
2257 // which the memref region is parametric); then those corresponding to
2258 // the memref's original indices follow.
2259 auto dimExpr = b.getAffineDimExpr(position: regionSymbols.size() + i);
2260 remapExprs.push_back(Elt: dimExpr - fastBufOffsets[i]);
2261 }
2262 auto indexRemap = AffineMap::get(dimCount: regionSymbols.size() + rank, symbolCount: 0, results: remapExprs,
2263 context: b.getContext());
2264
2265 // Record the begin since it may be invalidated by memref replacement.
2266 Block::iterator prevOfBegin;
2267 bool isBeginAtStartOfBlock = (begin == block->begin());
2268 if (!isBeginAtStartOfBlock)
2269 prevOfBegin = std::prev(x: begin);
2270
2271 auto userFilterFn = [&](Operation *user) {
2272 auto *ancestorUser = block->findAncestorOpInBlock(op&: *user);
2273 return ancestorUser && !ancestorUser->isBeforeInBlock(other: &*begin) &&
2274 !lastCopyOp->isBeforeInBlock(other: ancestorUser);
2275 };
2276
2277 // *Only* those uses within the range [begin, end) of 'block' are replaced.
2278 (void)replaceAllMemRefUsesWith(oldMemRef: memref, newMemRef: fastMemRef,
2279 /*extraIndices=*/{}, indexRemap,
2280 /*extraOperands=*/regionSymbols,
2281 /*symbolOperands=*/{}, userFilterFn);
2282
2283 *nBegin = isBeginAtStartOfBlock ? block->begin() : std::next(x: prevOfBegin);
2284
2285 return success();
2286}
2287
2288/// Construct the memref region to just include the entire memref. Returns false
2289/// dynamic shaped memref's for now. `numParamLoopIVs` is the number of
2290/// enclosing loop IVs of `op` (starting from the outermost) that the region
2291/// is parametric on.
2292static bool getFullMemRefAsRegion(Operation *op, unsigned numParamLoopIVs,
2293 MemRefRegion *region) {
2294 unsigned rank;
2295 if (auto loadOp = dyn_cast<AffineLoadOp>(Val: op)) {
2296 rank = loadOp.getMemRefType().getRank();
2297 region->memref = loadOp.getMemRef();
2298 region->setWrite(false);
2299 } else if (auto storeOp = dyn_cast<AffineStoreOp>(Val: op)) {
2300 rank = storeOp.getMemRefType().getRank();
2301 region->memref = storeOp.getMemRef();
2302 region->setWrite(true);
2303 } else {
2304 assert(false && "expected load or store op");
2305 return false;
2306 }
2307 auto memRefType = cast<MemRefType>(Val: region->memref.getType());
2308 if (!memRefType.hasStaticShape())
2309 return false;
2310
2311 auto *regionCst = region->getConstraints();
2312
2313 // Just get the first numSymbols IVs, which the memref region is parametric
2314 // on.
2315 SmallVector<AffineForOp, 4> ivs;
2316 getAffineForIVs(op&: *op, loops: &ivs);
2317 ivs.resize(N: numParamLoopIVs);
2318 SmallVector<Value, 4> symbols;
2319 extractForInductionVars(forInsts: ivs, ivs: &symbols);
2320 *regionCst = FlatAffineValueConstraints(rank, numParamLoopIVs, 0);
2321 regionCst->setValues(start: rank, end: rank + numParamLoopIVs, values: symbols);
2322
2323 // Memref dim sizes provide the bounds.
2324 for (unsigned d = 0; d < rank; d++) {
2325 auto dimSize = memRefType.getDimSize(idx: d);
2326 assert(dimSize > 0 && "filtered dynamic shapes above");
2327 regionCst->addBound(type: BoundType::LB, pos: d, value: 0);
2328 regionCst->addBound(type: BoundType::UB, pos: d, value: dimSize - 1);
2329 }
2330 return true;
2331}
2332
2333LogicalResult
2334mlir::affine::affineDataCopyGenerate(Block::iterator begin, Block::iterator end,
2335 const AffineCopyOptions &copyOptions,
2336 std::optional<Value> filterMemRef,
2337 DenseSet<Operation *> &copyNests) {
2338 if (begin == end)
2339 return success();
2340
2341 assert(begin->getBlock() == std::prev(end)->getBlock() &&
2342 "Inconsistent block begin/end args");
2343 assert(end != end->getBlock()->end() && "end can't be the block terminator");
2344
2345 Block *block = begin->getBlock();
2346
2347 // Copies will be generated for this depth, i.e., symbolic in all loops
2348 // surrounding the this block range.
2349 unsigned copyDepth = getNestingDepth(op: &*begin);
2350
2351 LDBG() << "Generating copies at depth " << copyDepth;
2352 LDBG() << "from begin: "
2353 << OpWithFlags(&*begin, OpPrintingFlags().skipRegions());
2354 LDBG() << "to inclusive end: "
2355 << OpWithFlags(&*std::prev(x: end), OpPrintingFlags().skipRegions());
2356
2357 // List of memory regions to copy for. We need a map vector to have a
2358 // guaranteed iteration order to write test cases. CHECK-DAG doesn't help here
2359 // since the alloc's for example are identical except for the SSA id.
2360 SmallMapVector<Value, std::unique_ptr<MemRefRegion>, 4> readRegions;
2361 SmallMapVector<Value, std::unique_ptr<MemRefRegion>, 4> writeRegions;
2362
2363 // Map from original memref's to the fast buffers that their accesses are
2364 // replaced with.
2365 DenseMap<Value, Value> fastBufferMap;
2366
2367 // To check for errors when walking the block.
2368 bool error = false;
2369
2370 // Walk this range of operations to gather all memory regions.
2371 block->walk(begin, end, callback: [&](Operation *opInst) {
2372 Value memref;
2373 MemRefType memrefType;
2374 // Gather regions to allocate to buffers in faster memory space.
2375 if (auto loadOp = dyn_cast<AffineLoadOp>(Val: opInst)) {
2376 memref = loadOp.getMemRef();
2377 memrefType = loadOp.getMemRefType();
2378 } else if (auto storeOp = dyn_cast<AffineStoreOp>(Val: opInst)) {
2379 memref = storeOp.getMemRef();
2380 memrefType = storeOp.getMemRefType();
2381 }
2382 // Not an affine.load/store op.
2383 if (!memref)
2384 return;
2385
2386 if ((filterMemRef.has_value() && filterMemRef != memref) ||
2387 (isa_and_nonnull<IntegerAttr>(Val: memrefType.getMemorySpace()) &&
2388 memrefType.getMemorySpaceAsInt() != copyOptions.slowMemorySpace))
2389 return;
2390
2391 if (!memref.getParentRegion()->isAncestor(other: block->getParent())) {
2392 LDBG() << "memref definition is inside of the depth at "
2393 << "which copy-in/copy-out would happen";
2394 return;
2395 }
2396
2397 // Compute the MemRefRegion accessed.
2398 auto region = std::make_unique<MemRefRegion>(args: opInst->getLoc());
2399 if (failed(Result: region->compute(op: opInst, loopDepth: copyDepth, /*sliceState=*/nullptr,
2400 /*addMemRefDimBounds=*/false))) {
2401 LDBG() << "Error obtaining memory region: semi-affine maps?";
2402 LDBG() << "over-approximating to the entire memref";
2403 if (!getFullMemRefAsRegion(op: opInst, numParamLoopIVs: copyDepth, region: region.get())) {
2404 LDBG() << "non-constant memref sizes not yet supported";
2405 error = true;
2406 return;
2407 }
2408 }
2409
2410 // Each memref has a single buffer associated with it irrespective of how
2411 // many load's and store's happen on it.
2412 // TODO: in the future, when regions don't intersect and satisfy
2413 // other properties (based on load/store regions), we could consider
2414 // multiple buffers per memref.
2415
2416 // Add to the appropriate region if it's not already in it, or take a
2417 // bounding box union with the existing one if it's already in there.
2418 // Note that a memref may have both read and write regions - so update the
2419 // region in the other list if one exists (write in case of read and vice
2420 // versa) since there is a single bounding box for a memref across all reads
2421 // and writes that happen on it.
2422
2423 // Attempts to update; returns true if 'region' exists in targetRegions.
2424 auto updateRegion =
2425 [&](const SmallMapVector<Value, std::unique_ptr<MemRefRegion>, 4>
2426 &targetRegions) {
2427 const auto *const it = targetRegions.find(Key: region->memref);
2428 if (it == targetRegions.end())
2429 return false;
2430
2431 // Perform a union with the existing region.
2432 if (failed(Result: it->second->unionBoundingBox(other: *region))) {
2433 LDBG() << "Memory region bounding box failed; "
2434 << "over-approximating to the entire memref";
2435 // If the union fails, we will overapproximate.
2436 if (!getFullMemRefAsRegion(op: opInst, numParamLoopIVs: copyDepth, region: region.get())) {
2437 LDBG() << "non-constant memref sizes not yet supported";
2438 error = true;
2439 return true;
2440 }
2441 it->second->getConstraints()->clearAndCopyFrom(
2442 other: *region->getConstraints());
2443 } else {
2444 // Union was computed and stored in 'it->second': copy to 'region'.
2445 region->getConstraints()->clearAndCopyFrom(
2446 other: *it->second->getConstraints());
2447 }
2448 return true;
2449 };
2450
2451 bool existsInRead = updateRegion(readRegions);
2452 if (error)
2453 return;
2454 bool existsInWrite = updateRegion(writeRegions);
2455 if (error)
2456 return;
2457
2458 // Finally add it to the region list.
2459 if (region->isWrite() && !existsInWrite) {
2460 writeRegions[region->memref] = std::move(region);
2461 } else if (!region->isWrite() && !existsInRead) {
2462 readRegions[region->memref] = std::move(region);
2463 }
2464 });
2465
2466 if (error) {
2467 LDBG() << "copy generation failed for one or more memref's in this block";
2468 return failure();
2469 }
2470
2471 uint64_t totalCopyBuffersSizeInBytes = 0;
2472 bool ret = true;
2473 auto processRegions =
2474 [&](const SmallMapVector<Value, std::unique_ptr<MemRefRegion>, 4>
2475 &regions) {
2476 for (const auto &regionEntry : regions) {
2477 // For each region, hoist copy in/out past all hoistable
2478 // 'affine.for's.
2479 Block::iterator copyInPlacementStart, copyOutPlacementStart;
2480 Block *copyPlacementBlock;
2481 findHighestBlockForPlacement(
2482 region: *regionEntry.second, block&: *block, begin, end, copyPlacementBlock: &copyPlacementBlock,
2483 copyInPlacementStart: &copyInPlacementStart, copyOutPlacementStart: &copyOutPlacementStart);
2484
2485 uint64_t sizeInBytes;
2486 Block::iterator nBegin, nEnd;
2487 LogicalResult iRet = generateCopy(
2488 region: *regionEntry.second, block, begin, end, copyPlacementBlock,
2489 copyInPlacementStart, copyOutPlacementStart, copyOptions,
2490 fastBufferMap, copyNests, sizeInBytes: &sizeInBytes, nBegin: &nBegin, nEnd: &nEnd);
2491 if (succeeded(Result: iRet)) {
2492 // begin/end could have been invalidated, and need update.
2493 begin = nBegin;
2494 end = nEnd;
2495 totalCopyBuffersSizeInBytes += sizeInBytes;
2496 }
2497 ret = ret & succeeded(Result: iRet);
2498 }
2499 };
2500 processRegions(readRegions);
2501 processRegions(writeRegions);
2502
2503 if (!ret) {
2504 LDBG() << "copy generation failed for one or more memref's in this block";
2505 return failure();
2506 }
2507
2508 // For a range of operations, a note will be emitted at the caller.
2509 AffineForOp forOp;
2510 if (llvm::DebugFlag && (forOp = dyn_cast<AffineForOp>(Val: &*begin))) {
2511 LLVM_DEBUG(forOp.emitRemark()
2512 << llvm::divideCeil(totalCopyBuffersSizeInBytes, 1024)
2513 << " KiB of copy buffers in fast memory space for this block");
2514 }
2515
2516 if (totalCopyBuffersSizeInBytes > copyOptions.fastMemCapacityBytes) {
2517 block->getParentOp()->emitWarning(
2518 message: "total size of all copy buffers' for this block exceeds fast memory "
2519 "capacity");
2520 }
2521
2522 return success();
2523}
2524
2525// A convenience version of affineDataCopyGenerate for all ops in the body of
2526// an AffineForOp.
2527LogicalResult mlir::affine::affineDataCopyGenerate(
2528 AffineForOp forOp, const AffineCopyOptions &copyOptions,
2529 std::optional<Value> filterMemRef, DenseSet<Operation *> &copyNests) {
2530 return affineDataCopyGenerate(begin: forOp.getBody()->begin(),
2531 end: std::prev(x: forOp.getBody()->end()), copyOptions,
2532 filterMemRef, copyNests);
2533}
2534
2535LogicalResult mlir::affine::generateCopyForMemRegion(
2536 const MemRefRegion &memrefRegion, Operation *analyzedOp,
2537 const AffineCopyOptions &copyOptions, CopyGenerateResult &result) {
2538 Block *block = analyzedOp->getBlock();
2539 auto begin = analyzedOp->getIterator();
2540 auto end = std::next(x: begin);
2541 DenseMap<Value, Value> fastBufferMap;
2542 DenseSet<Operation *> copyNests;
2543
2544 auto err = generateCopy(region: memrefRegion, block, begin, end, copyPlacementBlock: block, copyInPlacementStart: begin, copyOutPlacementStart: end,
2545 copyOptions, fastBufferMap, copyNests,
2546 sizeInBytes: &result.sizeInBytes, nBegin: &begin, nEnd: &end);
2547 if (failed(Result: err))
2548 return err;
2549
2550 const auto &en = fastBufferMap.find(Val: memrefRegion.memref);
2551 // In some cases (empty loops), no copy generation would have happened.
2552 if (en == fastBufferMap.end())
2553 return failure();
2554 result.alloc = en->second.getDefiningOp();
2555 assert(result.alloc && "fast buffer expected to be locally allocated");
2556 assert(copyNests.size() <= 1 && "At most one copy nest is expected.");
2557 result.copyNest = copyNests.empty() ? nullptr : *copyNests.begin();
2558 return success();
2559}
2560
2561/// Gathers all AffineForOps in 'block' at 'currLoopDepth' in 'depthToLoops'.
2562static void
2563gatherLoopsInBlock(Block *block, unsigned currLoopDepth,
2564 std::vector<SmallVector<AffineForOp, 2>> &depthToLoops) {
2565 // Add a new empty level to output if it doesn't exist level already.
2566 assert(currLoopDepth <= depthToLoops.size() && "Unexpected currLoopDepth");
2567 if (currLoopDepth == depthToLoops.size())
2568 depthToLoops.emplace_back();
2569
2570 for (auto &op : *block) {
2571 if (auto forOp = dyn_cast<AffineForOp>(Val&: op)) {
2572 depthToLoops[currLoopDepth].push_back(Elt: forOp);
2573 gatherLoopsInBlock(block: forOp.getBody(), currLoopDepth: currLoopDepth + 1, depthToLoops);
2574 }
2575 }
2576}
2577
2578/// Gathers all AffineForOps in 'func.func' grouped by loop depth.
2579void mlir::affine::gatherLoops(
2580 func::FuncOp func, std::vector<SmallVector<AffineForOp, 2>> &depthToLoops) {
2581 for (auto &block : func)
2582 gatherLoopsInBlock(block: &block, /*currLoopDepth=*/0, depthToLoops);
2583
2584 // Remove last loop level from output since it's empty.
2585 if (!depthToLoops.empty()) {
2586 assert(depthToLoops.back().empty() && "Last loop level is not empty?");
2587 depthToLoops.pop_back();
2588 }
2589}
2590
2591AffineForOp mlir::affine::createCanonicalizedAffineForOp(
2592 OpBuilder b, Location loc, ValueRange lbOperands, AffineMap lbMap,
2593 ValueRange ubOperands, AffineMap ubMap, int64_t step) {
2594 SmallVector<Value, 4> lowerOperands(lbOperands);
2595 SmallVector<Value, 4> upperOperands(ubOperands);
2596
2597 fullyComposeAffineMapAndOperands(map: &lbMap, operands: &lowerOperands);
2598 canonicalizeMapAndOperands(map: &lbMap, operands: &lowerOperands);
2599 lbMap = removeDuplicateExprs(map: lbMap);
2600 fullyComposeAffineMapAndOperands(map: &ubMap, operands: &upperOperands);
2601 canonicalizeMapAndOperands(map: &ubMap, operands: &upperOperands);
2602 ubMap = removeDuplicateExprs(map: ubMap);
2603
2604 return AffineForOp::create(builder&: b, location: loc, lbOperands: lowerOperands, lbMap, ubOperands: upperOperands, ubMap,
2605 step);
2606}
2607
2608/// Creates an AffineIfOp that encodes the conditional to choose between
2609/// the constant trip count version and an unknown trip count version of this
2610/// nest of loops. This is used to separate partial and full tiles if `loops`
2611/// has the intra-tile loops. The affine.if op is inserted at the builder
2612/// insertion point of `b`.
2613static AffineIfOp createSeparationCondition(MutableArrayRef<AffineForOp> loops,
2614 OpBuilder b) {
2615 if (loops.empty())
2616 return nullptr;
2617
2618 auto *context = loops[0].getContext();
2619
2620 FlatAffineValueConstraints cst;
2621 SmallVector<Operation *, 8> ops;
2622 llvm::append_range(C&: ops, R&: loops);
2623 (void)getIndexSet(ops, domain: &cst);
2624
2625 // Remove constraints that are independent of these loop IVs.
2626 cst.removeIndependentConstraints(/*pos=*/0, /*num=*/loops.size());
2627
2628 // Construct the constraint set representing the guard for full tiles. The
2629 // lower bound (and upper bound) corresponding to the full tile should be
2630 // larger (and resp. smaller) than any other lower (or upper bound).
2631 SmallVector<int64_t, 8> fullTileLb, fullTileUb;
2632 for (auto loop : loops) {
2633 (void)loop;
2634 // TODO: Non-unit stride is not an issue to generalize to.
2635 assert(loop.getStepAsInt() == 1 && "point loop step expected to be one");
2636 // Mark everything symbols for the purpose of finding a constant diff pair.
2637 cst.setDimSymbolSeparation(/*newSymbolCount=*/cst.getNumDimAndSymbolVars() -
2638 1);
2639 unsigned fullTileLbPos, fullTileUbPos;
2640 if (!((IntegerRelation)cst)
2641 .getConstantBoundOnDimSize(pos: 0, /*lb=*/nullptr,
2642 /*boundFloorDivisor=*/nullptr,
2643 /*ub=*/nullptr, minLbPos: &fullTileLbPos,
2644 minUbPos: &fullTileUbPos)) {
2645 LDBG() << "Can't get constant diff pair for a loop";
2646 return nullptr;
2647 }
2648
2649 SmallVector<unsigned, 4> lbIndices, ubIndices;
2650 cst.getLowerAndUpperBoundIndices(/*pos=*/0, lbIndices: &lbIndices, ubIndices: &ubIndices);
2651
2652 auto fLb = cst.getInequality(idx: fullTileLbPos);
2653 auto fUb = cst.getInequality(idx: fullTileUbPos);
2654 fullTileLb.assign(in_start: fLb.begin(), in_end: fLb.end());
2655 fullTileUb.assign(in_start: fUb.begin(), in_end: fUb.end());
2656
2657 // Full tile lower bound should be >= than any other lower bound.
2658 for (auto lbIndex : lbIndices)
2659 for (unsigned i = 0, e = cst.getNumCols(); i < e; ++i)
2660 cst.atIneq(i: lbIndex, j: i) = fullTileLb[i] - cst.atIneq(i: lbIndex, j: i);
2661
2662 // Full tile upper bound should be <= any other upper bound.
2663 for (auto ubIndex : ubIndices)
2664 for (unsigned i = 0, e = cst.getNumCols(); i < e; ++i)
2665 cst.atIneq(i: ubIndex, j: i) -= fullTileUb[i];
2666
2667 cst.removeVar(pos: 0);
2668 }
2669
2670 // The previous step leads to all zeros for the full tile lb and ub position
2671 // itself; remove those and any other duplicates / trivial redundancies.
2672 cst.removeTrivialRedundancy();
2673
2674 // Turn everything into dims conservatively since we earlier turned all
2675 // trailing ids past point loop IV into symbols. Some of these could be outer
2676 // loop IVs; we'll canonicalize anyway.
2677 cst.setDimSymbolSeparation(0);
2678
2679 IntegerSet ifCondSet = cst.getAsIntegerSet(context);
2680 // ifCondSet can be null if cst was empty -- this can happen if all loops
2681 // in the nest have constant trip counts.
2682 if (!ifCondSet)
2683 return nullptr;
2684
2685 SmallVector<Value, 4> setOperands;
2686 cst.getValues(start: 0, end: cst.getNumDimAndSymbolVars(), values: &setOperands);
2687 canonicalizeSetAndOperands(set: &ifCondSet, operands: &setOperands);
2688 return AffineIfOp::create(builder&: b, location: loops[0].getLoc(), set: ifCondSet, args: setOperands,
2689 /*withElseRegion=*/true);
2690}
2691
2692/// Create the full tile loop nest (along with its body).
2693static LogicalResult
2694createFullTiles(MutableArrayRef<AffineForOp> inputNest,
2695 SmallVectorImpl<AffineForOp> &fullTileLoops, OpBuilder b) {
2696 fullTileLoops.reserve(N: inputNest.size());
2697
2698 // For each loop in the original nest identify a lower/upper bound pair such
2699 // that their difference is a constant.
2700 FlatAffineValueConstraints cst;
2701 for (auto loop : inputNest) {
2702 // TODO: straightforward to generalize to a non-unit stride.
2703 if (loop.getStepAsInt() != 1) {
2704 LDBG() << "[tile separation] non-unit stride not implemented";
2705 return failure();
2706 }
2707 SmallVector<Operation *, 1> loopOp{loop.getOperation()};
2708 (void)getIndexSet(ops: loopOp, domain: &cst);
2709 // We will mark everything other than this loop IV as symbol for getting a
2710 // pair of <lb, ub> with a constant difference.
2711 cst.setDimSymbolSeparation(cst.getNumDimAndSymbolVars() - 1);
2712 unsigned lbPos, ubPos;
2713 if (!((IntegerRelation)cst)
2714 .getConstantBoundOnDimSize(/*pos=*/0, /*lb=*/nullptr,
2715 /*boundFloorDivisor=*/nullptr,
2716 /*ub=*/nullptr, minLbPos: &lbPos, minUbPos: &ubPos) ||
2717 lbPos == ubPos) {
2718 LDBG() << "[tile separation] Can't get constant diff / "
2719 << "equalities not yet handled";
2720 return failure();
2721 }
2722
2723 // Set all variables as dimensions uniformly since some of those marked as
2724 // symbols above could be outer loop IVs (corresponding tile space IVs).
2725 cst.setDimSymbolSeparation(/*newSymbolCount=*/0);
2726
2727 AffineValueMap lbVmap, ubVmap;
2728 cst.getIneqAsAffineValueMap(/*pos=*/0, ineqPos: lbPos, vmap&: lbVmap, context: b.getContext());
2729 cst.getIneqAsAffineValueMap(/*pos=*/0, ineqPos: ubPos, vmap&: ubVmap, context: b.getContext());
2730 AffineForOp fullTileLoop = createCanonicalizedAffineForOp(
2731 b, loc: loop.getLoc(), lbOperands: lbVmap.getOperands(), lbMap: lbVmap.getAffineMap(),
2732 ubOperands: ubVmap.getOperands(), ubMap: ubVmap.getAffineMap());
2733 b = OpBuilder::atBlockTerminator(block: fullTileLoop.getBody());
2734 fullTileLoops.push_back(Elt: fullTileLoop);
2735 }
2736
2737 // Add the body for the full tile loop nest.
2738 IRMapping operandMap;
2739 for (const auto &loopEn : llvm::enumerate(First&: inputNest))
2740 operandMap.map(from: loopEn.value().getInductionVar(),
2741 to: fullTileLoops[loopEn.index()].getInductionVar());
2742 b = OpBuilder::atBlockTerminator(block: fullTileLoops.back().getBody());
2743 for (auto &op : inputNest.back().getBody()->without_terminator())
2744 b.clone(op, mapper&: operandMap);
2745 return success();
2746}
2747
2748LogicalResult
2749mlir::affine::separateFullTiles(MutableArrayRef<AffineForOp> inputNest,
2750 SmallVectorImpl<AffineForOp> *fullTileNest) {
2751 if (inputNest.empty())
2752 return success();
2753
2754 auto firstLoop = inputNest[0];
2755
2756 // Each successive for op has to be nested in the other.
2757 auto prevLoop = firstLoop;
2758 for (auto loop : inputNest.drop_front(N: 1)) {
2759 assert(loop->getParentOp() == prevLoop && "input not contiguously nested");
2760 prevLoop = loop;
2761 }
2762
2763 // Create the full tile loop nest.
2764 SmallVector<AffineForOp, 4> fullTileLoops;
2765 OpBuilder b(firstLoop);
2766 if (failed(Result: createFullTiles(inputNest, fullTileLoops, b))) {
2767 if (!fullTileLoops.empty())
2768 fullTileLoops.front().erase();
2769 return failure();
2770 }
2771
2772 // Create and insert the version select right before the root of the nest.
2773 b = OpBuilder(firstLoop);
2774 AffineIfOp ifOp = createSeparationCondition(loops: inputNest, b);
2775 if (!ifOp) {
2776 fullTileLoops.front().erase();
2777 LDBG() << "All tiles are full tiles, or failure creating "
2778 << "separation condition";
2779 return failure();
2780 }
2781
2782 // Move the full tile into the then block.
2783 Block *thenBlock = ifOp.getThenBlock();
2784 AffineForOp outermostFullTileLoop = fullTileLoops[0];
2785 thenBlock->getOperations().splice(
2786 where: std::prev(x: thenBlock->end()),
2787 L2&: outermostFullTileLoop->getBlock()->getOperations(),
2788 first: Block::iterator(outermostFullTileLoop));
2789
2790 // Move the partial tile into the else block. The partial tile is the same as
2791 // the original loop nest.
2792 Block *elseBlock = ifOp.getElseBlock();
2793 elseBlock->getOperations().splice(where: std::prev(x: elseBlock->end()),
2794 L2&: firstLoop->getBlock()->getOperations(),
2795 first: Block::iterator(firstLoop));
2796
2797 if (fullTileNest)
2798 *fullTileNest = std::move(fullTileLoops);
2799
2800 return success();
2801}
2802
2803LogicalResult affine::coalescePerfectlyNestedAffineLoops(AffineForOp op) {
2804 LogicalResult result(failure());
2805 SmallVector<AffineForOp> loops;
2806 getPerfectlyNestedLoops(nestedLoops&: loops, root: op);
2807 if (loops.size() <= 1)
2808 return success();
2809
2810 // Look for a band of loops that can be coalesced, i.e. perfectly nested
2811 // loops with bounds defined above some loop.
2812 // 1. For each loop, find above which parent loop its operands are
2813 // defined.
2814 SmallVector<unsigned> operandsDefinedAbove(loops.size());
2815 for (unsigned i = 0, e = loops.size(); i < e; ++i) {
2816 operandsDefinedAbove[i] = i;
2817 for (unsigned j = 0; j < i; ++j) {
2818 if (areValuesDefinedAbove(values: loops[i].getOperands(), limit&: loops[j].getRegion())) {
2819 operandsDefinedAbove[i] = j;
2820 break;
2821 }
2822 }
2823 }
2824
2825 // 2. Identify bands of loops such that the operands of all of them are
2826 // defined above the first loop in the band. Traverse the nest bottom-up
2827 // so that modifications don't invalidate the inner loops.
2828 for (unsigned end = loops.size(); end > 0; --end) {
2829 unsigned start = 0;
2830 for (; start < end - 1; ++start) {
2831 auto maxPos =
2832 *std::max_element(first: std::next(x: operandsDefinedAbove.begin(), n: start),
2833 last: std::next(x: operandsDefinedAbove.begin(), n: end));
2834 if (maxPos > start)
2835 continue;
2836 assert(maxPos == start &&
2837 "expected loop bounds to be known at the start of the band");
2838 auto band = llvm::MutableArrayRef(loops.data() + start, end - start);
2839 if (succeeded(Result: coalesceLoops(loops: band)))
2840 result = success();
2841 break;
2842 }
2843 // If a band was found and transformed, keep looking at the loops above
2844 // the outermost transformed loop.
2845 if (start != end - 1)
2846 end = start + 1;
2847 }
2848 return result;
2849}
2850
2851int64_t mlir::affine::numEnclosingInvariantLoops(OpOperand &operand) {
2852 int64_t count = 0;
2853 Operation *currentOp = operand.getOwner();
2854 while (auto loopOp = currentOp->getParentOfType<LoopLikeOpInterface>()) {
2855 if (!loopOp.isDefinedOutsideOfLoop(value: operand.get()))
2856 break;
2857 currentOp = loopOp;
2858 count++;
2859 }
2860 return count;
2861}
2862