1//===- Utils.cpp ---- Utilities for affine dialect 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 transformation utilities for the Affine
10// dialect.
11//
12//===----------------------------------------------------------------------===//
13
14#include "mlir/Dialect/Affine/Utils.h"
15
16#include "mlir/Dialect/Affine/Analysis/Utils.h"
17#include "mlir/Dialect/Affine/IR/AffineOps.h"
18#include "mlir/Dialect/Affine/IR/AffineValueMap.h"
19#include "mlir/Dialect/Affine/LoopUtils.h"
20#include "mlir/Dialect/Arith/Utils/Utils.h"
21#include "mlir/Dialect/Func/IR/FuncOps.h"
22#include "mlir/Dialect/MemRef/IR/MemRef.h"
23#include "mlir/Dialect/Utils/IndexingUtils.h"
24#include "mlir/IR/AffineExprVisitor.h"
25#include "mlir/IR/Dominance.h"
26#include "mlir/IR/IRMapping.h"
27#include "mlir/IR/IntegerSet.h"
28#include "mlir/Transforms/GreedyPatternRewriteDriver.h"
29#include "llvm/ADT/SmallVectorExtras.h"
30#include <optional>
31
32#define DEBUG_TYPE "affine-utils"
33
34using namespace mlir;
35using namespace affine;
36using namespace presburger;
37
38namespace {
39/// Visit affine expressions recursively and build the sequence of operations
40/// that correspond to it. Visitation functions return an Value of the
41/// expression subtree they visited or `nullptr` on error.
42class AffineApplyExpander
43 : public AffineExprVisitor<AffineApplyExpander, Value> {
44public:
45 /// This internal class expects arguments to be non-null, checks must be
46 /// performed at the call site.
47 AffineApplyExpander(OpBuilder &builder, ValueRange dimValues,
48 ValueRange symbolValues, Location loc)
49 : builder(builder), dimValues(dimValues), symbolValues(symbolValues),
50 loc(loc) {}
51
52 template <typename OpTy>
53 Value buildBinaryExpr(AffineBinaryOpExpr expr,
54 arith::IntegerOverflowFlags overflowFlags =
55 arith::IntegerOverflowFlags::none) {
56 auto lhs = visit(expr: expr.getLHS());
57 auto rhs = visit(expr: expr.getRHS());
58 if (!lhs || !rhs)
59 return nullptr;
60 auto op = OpTy::create(builder, loc, lhs, rhs, overflowFlags);
61 return op.getResult();
62 }
63
64 Value visitAddExpr(AffineBinaryOpExpr expr) {
65 return buildBinaryExpr<arith::AddIOp>(expr);
66 }
67
68 Value visitMulExpr(AffineBinaryOpExpr expr) {
69 return buildBinaryExpr<arith::MulIOp>(expr,
70 overflowFlags: arith::IntegerOverflowFlags::nsw);
71 }
72
73 /// Euclidean modulo operation: negative RHS is not allowed.
74 /// Remainder of the euclidean integer division is always non-negative.
75 ///
76 /// Implemented as
77 ///
78 /// a mod b =
79 /// let remainder = srem a, b;
80 /// negative = a < 0 in
81 /// select negative, remainder + b, remainder.
82 Value visitModExpr(AffineBinaryOpExpr expr) {
83 if (auto rhsConst = dyn_cast<AffineConstantExpr>(Val: expr.getRHS())) {
84 if (rhsConst.getValue() <= 0) {
85 emitError(loc, message: "modulo by non-positive value is not supported");
86 return nullptr;
87 }
88 }
89
90 auto lhs = visit(expr: expr.getLHS());
91 auto rhs = visit(expr: expr.getRHS());
92 assert(lhs && rhs && "unexpected affine expr lowering failure");
93
94 Value remainder = arith::RemSIOp::create(builder, location: loc, lhs, rhs);
95 Value zeroCst = arith::ConstantIndexOp::create(builder, location: loc, value: 0);
96 Value isRemainderNegative = arith::CmpIOp::create(
97 builder, location: loc, predicate: arith::CmpIPredicate::slt, lhs: remainder, rhs: zeroCst);
98 Value correctedRemainder =
99 arith::AddIOp::create(builder, location: loc, lhs: remainder, rhs);
100 Value result = arith::SelectOp::create(builder, location: loc, condition: isRemainderNegative,
101 true_value: correctedRemainder, false_value: remainder);
102 return result;
103 }
104
105 /// Floor division operation (rounds towards negative infinity).
106 ///
107 /// For positive divisors, it can be implemented without branching and with a
108 /// single division operation as
109 ///
110 /// a floordiv b =
111 /// let negative = a < 0 in
112 /// let absolute = negative ? -a - 1 : a in
113 /// let quotient = absolute / b in
114 /// negative ? -quotient - 1 : quotient
115 ///
116 /// Note: this lowering does not use arith.floordivsi because the lowering of
117 /// that to arith.divsi (see populateCeilFloorDivExpandOpsPatterns) generates
118 /// not one but two arith.divsi. That could be changed to one divsi, but one
119 /// way or another, going through arith.floordivsi will result in more complex
120 /// IR because arith.floordivsi is more general than affine floordiv in that
121 /// it supports negative RHS.
122 Value visitFloorDivExpr(AffineBinaryOpExpr expr) {
123 if (auto rhsConst = dyn_cast<AffineConstantExpr>(Val: expr.getRHS())) {
124 if (rhsConst.getValue() <= 0) {
125 emitError(loc, message: "division by non-positive value is not supported");
126 return nullptr;
127 }
128 }
129 auto lhs = visit(expr: expr.getLHS());
130 auto rhs = visit(expr: expr.getRHS());
131 assert(lhs && rhs && "unexpected affine expr lowering failure");
132
133 Value zeroCst = arith::ConstantIndexOp::create(builder, location: loc, value: 0);
134 Value noneCst = arith::ConstantIndexOp::create(builder, location: loc, value: -1);
135 Value negative = arith::CmpIOp::create(
136 builder, location: loc, predicate: arith::CmpIPredicate::slt, lhs, rhs: zeroCst);
137 Value negatedDecremented =
138 arith::SubIOp::create(builder, location: loc, lhs: noneCst, rhs: lhs);
139 Value dividend = arith::SelectOp::create(builder, location: loc, condition: negative,
140 true_value: negatedDecremented, false_value: lhs);
141 Value quotient = arith::DivSIOp::create(builder, location: loc, lhs: dividend, rhs);
142 Value correctedQuotient =
143 arith::SubIOp::create(builder, location: loc, lhs: noneCst, rhs: quotient);
144 Value result = arith::SelectOp::create(builder, location: loc, condition: negative,
145 true_value: correctedQuotient, false_value: quotient);
146 return result;
147 }
148
149 /// Ceiling division operation (rounds towards positive infinity).
150 ///
151 /// For positive divisors, it can be implemented without branching and with a
152 /// single division operation as
153 ///
154 /// a ceildiv b =
155 /// let negative = a <= 0 in
156 /// let absolute = negative ? -a : a - 1 in
157 /// let quotient = absolute / b in
158 /// negative ? -quotient : quotient + 1
159 ///
160 /// Note: not using arith.ceildivsi for the same reason as explained in the
161 /// visitFloorDivExpr comment.
162 Value visitCeilDivExpr(AffineBinaryOpExpr expr) {
163 if (auto rhsConst = dyn_cast<AffineConstantExpr>(Val: expr.getRHS())) {
164 if (rhsConst.getValue() <= 0) {
165 emitError(loc, message: "division by non-positive value is not supported");
166 return nullptr;
167 }
168 }
169 auto lhs = visit(expr: expr.getLHS());
170 auto rhs = visit(expr: expr.getRHS());
171 assert(lhs && rhs && "unexpected affine expr lowering failure");
172
173 Value zeroCst = arith::ConstantIndexOp::create(builder, location: loc, value: 0);
174 Value oneCst = arith::ConstantIndexOp::create(builder, location: loc, value: 1);
175 Value nonPositive = arith::CmpIOp::create(
176 builder, location: loc, predicate: arith::CmpIPredicate::sle, lhs, rhs: zeroCst);
177 Value negated = arith::SubIOp::create(builder, location: loc, lhs: zeroCst, rhs: lhs);
178 Value decremented = arith::SubIOp::create(builder, location: loc, lhs, rhs: oneCst);
179 Value dividend = arith::SelectOp::create(builder, location: loc, condition: nonPositive, true_value: negated,
180 false_value: decremented);
181 Value quotient = arith::DivSIOp::create(builder, location: loc, lhs: dividend, rhs);
182 Value negatedQuotient =
183 arith::SubIOp::create(builder, location: loc, lhs: zeroCst, rhs: quotient);
184 Value incrementedQuotient =
185 arith::AddIOp::create(builder, location: loc, lhs: quotient, rhs: oneCst);
186 Value result = arith::SelectOp::create(
187 builder, location: loc, condition: nonPositive, true_value: negatedQuotient, false_value: incrementedQuotient);
188 return result;
189 }
190
191 Value visitConstantExpr(AffineConstantExpr expr) {
192 auto op = arith::ConstantIndexOp::create(builder, location: loc, value: expr.getValue());
193 return op.getResult();
194 }
195
196 Value visitDimExpr(AffineDimExpr expr) {
197 assert(expr.getPosition() < dimValues.size() &&
198 "affine dim position out of range");
199 return dimValues[expr.getPosition()];
200 }
201
202 Value visitSymbolExpr(AffineSymbolExpr expr) {
203 assert(expr.getPosition() < symbolValues.size() &&
204 "symbol dim position out of range");
205 return symbolValues[expr.getPosition()];
206 }
207
208private:
209 OpBuilder &builder;
210 ValueRange dimValues;
211 ValueRange symbolValues;
212
213 Location loc;
214};
215} // namespace
216
217/// Create a sequence of operations that implement the `expr` applied to the
218/// given dimension and symbol values.
219mlir::Value mlir::affine::expandAffineExpr(OpBuilder &builder, Location loc,
220 AffineExpr expr,
221 ValueRange dimValues,
222 ValueRange symbolValues) {
223 return AffineApplyExpander(builder, dimValues, symbolValues, loc).visit(expr);
224}
225
226/// Create a sequence of operations that implement the `affineMap` applied to
227/// the given `operands` (as it it were an AffineApplyOp).
228std::optional<SmallVector<Value, 8>>
229mlir::affine::expandAffineMap(OpBuilder &builder, Location loc,
230 AffineMap affineMap, ValueRange operands) {
231 auto numDims = affineMap.getNumDims();
232 auto expanded = llvm::map_to_vector<8>(
233 C: affineMap.getResults(),
234 F: [numDims, &builder, loc, operands](AffineExpr expr) {
235 return expandAffineExpr(builder, loc, expr,
236 dimValues: operands.take_front(n: numDims),
237 symbolValues: operands.drop_front(n: numDims));
238 });
239 if (llvm::all_of(Range&: expanded, P: [](Value v) { return v; }))
240 return expanded;
241 return std::nullopt;
242}
243
244/// Promotes the `then` or the `else` block of `ifOp` (depending on whether
245/// `elseBlock` is false or true) into `ifOp`'s containing block, and discards
246/// the rest of the op.
247static void promoteIfBlock(AffineIfOp ifOp, bool elseBlock) {
248 if (elseBlock)
249 assert(ifOp.hasElse() && "else block expected");
250
251 Block *destBlock = ifOp->getBlock();
252 Block *srcBlock = elseBlock ? ifOp.getElseBlock() : ifOp.getThenBlock();
253 destBlock->getOperations().splice(
254 where: Block::iterator(ifOp), L2&: srcBlock->getOperations(), first: srcBlock->begin(),
255 last: std::prev(x: srcBlock->end()));
256 ifOp.erase();
257}
258
259/// Returns the outermost affine.for/parallel op that the `ifOp` is invariant
260/// on. The `ifOp` could be hoisted and placed right before such an operation.
261/// This method assumes that the ifOp has been canonicalized (to be correct and
262/// effective).
263static Operation *getOutermostInvariantForOp(AffineIfOp ifOp) {
264 // Walk up the parents past all for op that this conditional is invariant on.
265 auto ifOperands = ifOp.getOperands();
266 Operation *res = ifOp;
267 while (!res->getParentOp()->hasTrait<OpTrait::IsIsolatedFromAbove>()) {
268 auto *parentOp = res->getParentOp();
269 if (auto forOp = dyn_cast<AffineForOp>(Val: parentOp)) {
270 if (llvm::is_contained(Range&: ifOperands, Element: forOp.getInductionVar()))
271 break;
272 } else if (auto parallelOp = dyn_cast<AffineParallelOp>(Val: parentOp)) {
273 if (llvm::any_of(Range: parallelOp.getIVs(), P: [&](Value iv) {
274 return llvm::is_contained(Range&: ifOperands, Element: iv);
275 }))
276 break;
277 } else if (!isa<AffineIfOp>(Val: parentOp)) {
278 // Won't walk up past anything other than affine.for/if ops.
279 break;
280 }
281 // You can always hoist up past any affine.if ops.
282 res = parentOp;
283 }
284 return res;
285}
286
287/// A helper for the mechanics of mlir::hoistAffineIfOp. Hoists `ifOp` just over
288/// `hoistOverOp`. Returns the new hoisted op if any hoisting happened,
289/// otherwise the same `ifOp`.
290static AffineIfOp hoistAffineIfOp(AffineIfOp ifOp, Operation *hoistOverOp) {
291 // No hoisting to do.
292 if (hoistOverOp == ifOp)
293 return ifOp;
294
295 // Create the hoisted 'if' first. Then, clone the op we are hoisting over for
296 // the else block. Then drop the else block of the original 'if' in the 'then'
297 // branch while promoting its then block, and analogously drop the 'then'
298 // block of the original 'if' from the 'else' branch while promoting its else
299 // block.
300 IRMapping operandMap;
301 OpBuilder b(hoistOverOp);
302 auto hoistedIfOp = AffineIfOp::create(builder&: b, location: ifOp.getLoc(), set: ifOp.getIntegerSet(),
303 args: ifOp.getOperands(),
304 /*elseBlock=*/withElseRegion: true);
305
306 // Create a clone of hoistOverOp to use for the else branch of the hoisted
307 // conditional. The else block may get optimized away if empty.
308 Operation *hoistOverOpClone = nullptr;
309 // We use this unique name to identify/find `ifOp`'s clone in the else
310 // version.
311 StringAttr idForIfOp = b.getStringAttr(bytes: "__mlir_if_hoisting");
312 operandMap.clear();
313 b.setInsertionPointAfter(hoistOverOp);
314 // We'll set an attribute to identify this op in a clone of this sub-tree.
315 ifOp->setDiscardableAttr(name: idForIfOp, value: b.getBoolAttr(value: true));
316 hoistOverOpClone = b.clone(op&: *hoistOverOp, mapper&: operandMap);
317
318 // Promote the 'then' block of the original affine.if in the then version.
319 promoteIfBlock(ifOp, /*elseBlock=*/false);
320
321 // Move the then version to the hoisted if op's 'then' block.
322 auto *thenBlock = hoistedIfOp.getThenBlock();
323 thenBlock->getOperations().splice(where: thenBlock->begin(),
324 L2&: hoistOverOp->getBlock()->getOperations(),
325 first: Block::iterator(hoistOverOp));
326
327 // Find the clone of the original affine.if op in the else version.
328 AffineIfOp ifCloneInElse;
329 hoistOverOpClone->walk(callback: [&](AffineIfOp ifClone) {
330 if (!ifClone->getDiscardableAttr(name: idForIfOp))
331 return WalkResult::advance();
332 ifCloneInElse = ifClone;
333 return WalkResult::interrupt();
334 });
335 assert(ifCloneInElse && "if op clone should exist");
336 // For the else block, promote the else block of the original 'if' if it had
337 // one; otherwise, the op itself is to be erased.
338 if (!ifCloneInElse.hasElse())
339 ifCloneInElse.erase();
340 else
341 promoteIfBlock(ifOp: ifCloneInElse, /*elseBlock=*/true);
342
343 // Move the else version into the else block of the hoisted if op.
344 auto *elseBlock = hoistedIfOp.getElseBlock();
345 elseBlock->getOperations().splice(
346 where: elseBlock->begin(), L2&: hoistOverOpClone->getBlock()->getOperations(),
347 first: Block::iterator(hoistOverOpClone));
348
349 return hoistedIfOp;
350}
351
352LogicalResult
353mlir::affine::affineParallelize(AffineForOp forOp,
354 ArrayRef<LoopReduction> parallelReductions,
355 AffineParallelOp *resOp) {
356 // Fail early if there are iter arguments that are not reductions.
357 unsigned numReductions = parallelReductions.size();
358 if (numReductions != forOp.getNumIterOperands())
359 return failure();
360
361 Location loc = forOp.getLoc();
362 OpBuilder outsideBuilder(forOp);
363 AffineMap lowerBoundMap = forOp.getLowerBoundMap();
364 ValueRange lowerBoundOperands = forOp.getLowerBoundOperands();
365 AffineMap upperBoundMap = forOp.getUpperBoundMap();
366 ValueRange upperBoundOperands = forOp.getUpperBoundOperands();
367
368 // Creating empty 1-D affine.parallel op.
369 auto reducedValues = llvm::map_to_vector<4>(
370 C&: parallelReductions, F: [](const LoopReduction &red) { return red.value; });
371 auto reductionKinds = llvm::map_to_vector<4>(
372 C&: parallelReductions, F: [](const LoopReduction &red) { return red.kind; });
373 AffineParallelOp newPloop = AffineParallelOp::create(
374 builder&: outsideBuilder, location: loc, resultTypes: ValueRange(reducedValues).getTypes(), reductions: reductionKinds,
375 lbMaps: llvm::ArrayRef(lowerBoundMap), lbArgs: lowerBoundOperands,
376 ubMaps: llvm::ArrayRef(upperBoundMap), ubArgs: upperBoundOperands,
377 steps: llvm::ArrayRef(forOp.getStepAsInt()));
378 // Steal the body of the old affine for op.
379 newPloop.getRegion().takeBody(other&: forOp.getRegion());
380 Operation *yieldOp = &newPloop.getBody()->back();
381
382 // Handle the initial values of reductions because the parallel loop always
383 // starts from the neutral value.
384 SmallVector<Value> newResults;
385 newResults.reserve(N: numReductions);
386 for (unsigned i = 0; i < numReductions; ++i) {
387 Value init = forOp.getInits()[i];
388 // This works because we are only handling single-op reductions at the
389 // moment. A switch on reduction kind or a mechanism to collect operations
390 // participating in the reduction will be necessary for multi-op reductions.
391 Operation *reductionOp = yieldOp->getOperand(idx: i).getDefiningOp();
392 assert(reductionOp && "yielded value is expected to be produced by an op");
393 outsideBuilder.getInsertionBlock()->getOperations().splice(
394 where: outsideBuilder.getInsertionPoint(), L2&: newPloop.getBody()->getOperations(),
395 N: reductionOp);
396 reductionOp->setOperands({init, newPloop->getResult(idx: i)});
397 forOp->getResult(idx: i).replaceAllUsesWith(newValue: reductionOp->getResult(idx: 0));
398 }
399
400 // Update the loop terminator to yield reduced values bypassing the reduction
401 // operation itself (now moved outside of the loop) and erase the block
402 // arguments that correspond to reductions. Note that the loop always has one
403 // "main" induction variable whenc coming from a non-parallel for.
404 unsigned numIVs = 1;
405 yieldOp->setOperands(reducedValues);
406 newPloop.getBody()->eraseArguments(start: numIVs, num: numReductions);
407
408 forOp.erase();
409 if (resOp)
410 *resOp = newPloop;
411 return success();
412}
413
414// Returns success if any hoisting happened.
415LogicalResult mlir::affine::hoistAffineIfOp(AffineIfOp ifOp, bool *folded) {
416 // Bail out early if the ifOp returns a result. TODO: Consider how to
417 // properly support this case.
418 if (ifOp.getNumResults() != 0)
419 return failure();
420
421 // Apply canonicalization patterns and folding - this is necessary for the
422 // hoisting check to be correct (operands should be composed), and to be more
423 // effective (no unused operands). Since the pattern rewriter's folding is
424 // entangled with application of patterns, we may fold/end up erasing the op,
425 // in which case we return with `folded` being set.
426 RewritePatternSet patterns(ifOp.getContext());
427 AffineIfOp::getCanonicalizationPatterns(results&: patterns, context: ifOp.getContext());
428 FrozenRewritePatternSet frozenPatterns(std::move(patterns));
429 bool erased;
430 (void)applyOpPatternsGreedily(
431 ops: ifOp.getOperation(), patterns: frozenPatterns,
432 config: GreedyRewriteConfig().setStrictness(GreedyRewriteStrictness::ExistingOps),
433 /*changed=*/nullptr, allErased: &erased);
434 if (erased) {
435 if (folded)
436 *folded = true;
437 return failure();
438 }
439 if (folded)
440 *folded = false;
441
442 // The folding above should have ensured this.
443 assert(llvm::all_of(ifOp.getOperands(),
444 [](Value v) {
445 return isTopLevelValue(v) || isAffineInductionVar(v);
446 }) &&
447 "operands not composed");
448
449 // We are going hoist as high as possible.
450 // TODO: this could be customized in the future.
451 auto *hoistOverOp = getOutermostInvariantForOp(ifOp);
452
453 AffineIfOp hoistedIfOp = ::hoistAffineIfOp(ifOp, hoistOverOp);
454 // Nothing to hoist over.
455 if (hoistedIfOp == ifOp)
456 return failure();
457
458 // Canonicalize to remove dead else blocks (happens whenever an 'if' moves up
459 // a sequence of affine.fors that are all perfectly nested).
460 (void)applyPatternsGreedily(
461 op: hoistedIfOp->getParentWithTrait<OpTrait::IsIsolatedFromAbove>(),
462 patterns: frozenPatterns);
463
464 return success();
465}
466
467// Return the min expr after replacing the given dim.
468AffineExpr mlir::affine::substWithMin(AffineExpr e, AffineExpr dim,
469 AffineExpr min, AffineExpr max,
470 bool positivePath) {
471 if (e == dim)
472 return positivePath ? min : max;
473 if (auto bin = dyn_cast<AffineBinaryOpExpr>(Val&: e)) {
474 AffineExpr lhs = bin.getLHS();
475 AffineExpr rhs = bin.getRHS();
476 if (bin.getKind() == mlir::AffineExprKind::Add)
477 return substWithMin(e: lhs, dim, min, max, positivePath) +
478 substWithMin(e: rhs, dim, min, max, positivePath);
479
480 auto c1 = dyn_cast<AffineConstantExpr>(Val: bin.getLHS());
481 auto c2 = dyn_cast<AffineConstantExpr>(Val: bin.getRHS());
482 if (c1 && c1.getValue() < 0)
483 return getAffineBinaryOpExpr(
484 kind: bin.getKind(), lhs: c1, rhs: substWithMin(e: rhs, dim, min, max, positivePath: !positivePath));
485 if (c2 && c2.getValue() < 0)
486 return getAffineBinaryOpExpr(
487 kind: bin.getKind(), lhs: substWithMin(e: lhs, dim, min, max, positivePath: !positivePath), rhs: c2);
488 return getAffineBinaryOpExpr(
489 kind: bin.getKind(), lhs: substWithMin(e: lhs, dim, min, max, positivePath),
490 rhs: substWithMin(e: rhs, dim, min, max, positivePath));
491 }
492 return e;
493}
494
495void mlir::affine::normalizeAffineParallel(AffineParallelOp op) {
496 // Loops with min/max in bounds are not normalized at the moment.
497 if (op.hasMinMaxBounds())
498 return;
499
500 AffineMap lbMap = op.getLowerBoundsMap();
501 SmallVector<int64_t, 8> steps = op.getSteps();
502 // No need to do any work if the parallel op is already normalized.
503 bool isAlreadyNormalized =
504 llvm::all_of(Range: llvm::zip(t&: steps, u: lbMap.getResults()), P: [](auto tuple) {
505 int64_t step = std::get<0>(tuple);
506 auto lbExpr = dyn_cast<AffineConstantExpr>(std::get<1>(tuple));
507 return lbExpr && lbExpr.getValue() == 0 && step == 1;
508 });
509 if (isAlreadyNormalized)
510 return;
511
512 AffineValueMap ranges;
513 AffineValueMap::difference(a: op.getUpperBoundsValueMap(),
514 b: op.getLowerBoundsValueMap(), res: &ranges);
515 auto builder = OpBuilder::atBlockBegin(block: op.getBody());
516 auto zeroExpr = builder.getAffineConstantExpr(constant: 0);
517 SmallVector<AffineExpr, 8> lbExprs;
518 SmallVector<AffineExpr, 8> ubExprs;
519 for (unsigned i = 0, e = steps.size(); i < e; ++i) {
520 int64_t step = steps[i];
521
522 // Adjust the lower bound to be 0.
523 lbExprs.push_back(Elt: zeroExpr);
524
525 // Adjust the upper bound expression: 'range / step'.
526 AffineExpr ubExpr = ranges.getResult(i).ceilDiv(v: step);
527 ubExprs.push_back(Elt: ubExpr);
528
529 // Adjust the corresponding IV: 'lb + i * step'.
530 BlockArgument iv = op.getBody()->getArgument(i);
531 AffineExpr lbExpr = lbMap.getResult(idx: i);
532 unsigned nDims = lbMap.getNumDims();
533 auto expr = lbExpr + builder.getAffineDimExpr(position: nDims) * step;
534 auto map = AffineMap::get(/*dimCount=*/nDims + 1,
535 /*symbolCount=*/lbMap.getNumSymbols(), result: expr);
536
537 // Use an 'affine.apply' op that will be simplified later in subsequent
538 // canonicalizations.
539 OperandRange lbOperands = op.getLowerBoundsOperands();
540 OperandRange dimOperands = lbOperands.take_front(n: nDims);
541 OperandRange symbolOperands = lbOperands.drop_front(n: nDims);
542 SmallVector<Value, 8> applyOperands{dimOperands};
543 applyOperands.push_back(Elt: iv);
544 applyOperands.append(in_start: symbolOperands.begin(), in_end: symbolOperands.end());
545 auto apply =
546 AffineApplyOp::create(builder, location: op.getLoc(), map, mapOperands: applyOperands);
547 iv.replaceAllUsesExcept(newValue: apply, exceptedUser: apply);
548 }
549
550 SmallVector<int64_t, 8> newSteps(op.getNumDims(), 1);
551 op.setSteps(std::move(newSteps));
552 auto newLowerMap = AffineMap::get(
553 /*dimCount=*/0, /*symbolCount=*/0, results: lbExprs, context: op.getContext());
554 op.setLowerBounds(operands: {}, map: newLowerMap);
555 auto newUpperMap = AffineMap::get(dimCount: ranges.getNumDims(), symbolCount: ranges.getNumSymbols(),
556 results: ubExprs, context: op.getContext());
557 op.setUpperBounds(operands: ranges.getOperands(), map: newUpperMap);
558}
559
560LogicalResult mlir::affine::normalizeAffineFor(AffineForOp op,
561 bool promoteSingleIter) {
562 if (promoteSingleIter && succeeded(Result: promoteIfSingleIteration(forOp: op)))
563 return success();
564
565 // Check if the forop is already normalized.
566 if (op.hasConstantLowerBound() && (op.getConstantLowerBound() == 0) &&
567 (op.getStep() == 1))
568 return success();
569
570 // Check if the lower bound has a single result only. Loops with a max lower
571 // bound can't be normalized without additional support like
572 // affine.execute_region's. If the lower bound does not have a single result
573 // then skip this op.
574 if (op.getLowerBoundMap().getNumResults() != 1)
575 return failure();
576
577 Location loc = op.getLoc();
578 OpBuilder opBuilder(op);
579 int64_t origLoopStep = op.getStepAsInt();
580
581 // Construct the new upper bound value map.
582 AffineMap oldLbMap = op.getLowerBoundMap();
583 AffineValueMap lbMap(oldLbMap, op.getLowerBoundOperands());
584 AffineValueMap ubValueMap(op.getUpperBoundMap(), op.getUpperBoundOperands());
585 AffineValueMap newUbValueMap;
586 // Subtract the single lower bound from each upper bound.
587 AffineValueMap::cartesianProductDifference(a: ubValueMap, b: lbMap, res: &newUbValueMap);
588 (void)newUbValueMap.canonicalize();
589
590 // Scale down the upper bound value map by the loop step.
591 unsigned numResult = newUbValueMap.getNumResults();
592 SmallVector<AffineExpr> scaleDownExprs(numResult);
593 for (unsigned i = 0; i < numResult; ++i)
594 scaleDownExprs[i] = opBuilder.getAffineDimExpr(position: i).ceilDiv(v: origLoopStep);
595 // `scaleDownMap` is (d0, d1, ..., d_n) -> (d0 / step, d1 / step, ..., d_n /
596 // step). Where `n` is the number of results in the upper bound map.
597 AffineMap scaleDownMap =
598 AffineMap::get(dimCount: numResult, symbolCount: 0, results: scaleDownExprs, context: op.getContext());
599 AffineMap newUbMap = scaleDownMap.compose(map: newUbValueMap.getAffineMap());
600
601 // Set the newly create upper bound map and operands.
602 op.setUpperBound(operands: newUbValueMap.getOperands(), map: newUbMap);
603 op.setLowerBound(operands: {}, map: opBuilder.getConstantAffineMap(val: 0));
604 op.setStep(1);
605
606 // Calculate the Value of new loopIV. Create affine.apply for the value of
607 // the loopIV in normalized loop.
608 opBuilder.setInsertionPointToStart(op.getBody());
609 // Construct an affine.apply op mapping the new IV to the old IV.
610 AffineMap scaleIvMap =
611 AffineMap::get(dimCount: 1, symbolCount: 0, result: -opBuilder.getAffineDimExpr(position: 0) * origLoopStep);
612 AffineValueMap scaleIvValueMap(scaleIvMap, ValueRange{op.getInductionVar()});
613 AffineValueMap newIvToOldIvMap;
614 AffineValueMap::difference(a: lbMap, b: scaleIvValueMap, res: &newIvToOldIvMap);
615 (void)newIvToOldIvMap.canonicalize();
616 auto newIV =
617 AffineApplyOp::create(builder&: opBuilder, location: loc, map: newIvToOldIvMap.getAffineMap(),
618 mapOperands: newIvToOldIvMap.getOperands());
619 op.getInductionVar().replaceAllUsesExcept(newValue: newIV->getResult(idx: 0), exceptedUser: newIV);
620 return success();
621}
622
623/// Returns true if the memory operation of `destAccess` depends on `srcAccess`
624/// inside of the innermost common surrounding affine loop between the two
625/// accesses.
626static bool mustReachAtInnermost(const MemRefAccess &srcAccess,
627 const MemRefAccess &destAccess) {
628 // Affine dependence analysis is possible only if both ops in the same
629 // AffineScope.
630 if (getAffineAnalysisScope(op: srcAccess.opInst) !=
631 getAffineAnalysisScope(op: destAccess.opInst))
632 return false;
633
634 unsigned nsLoops =
635 getNumCommonSurroundingLoops(a&: *srcAccess.opInst, b&: *destAccess.opInst);
636 DependenceResult result =
637 checkMemrefAccessDependence(srcAccess, dstAccess: destAccess, loopDepth: nsLoops + 1);
638 return hasDependence(result);
639}
640
641/// Returns true if `srcMemOp` may have an effect on `destMemOp` within the
642/// scope of the outermost `minSurroundingLoops` loops that surround them.
643/// `srcMemOp` and `destMemOp` are expected to be affine read/write ops.
644static bool mayHaveEffect(Operation *srcMemOp, Operation *destMemOp,
645 unsigned minSurroundingLoops) {
646 MemRefAccess srcAccess(srcMemOp);
647 MemRefAccess destAccess(destMemOp);
648
649 // Affine dependence analysis here is applicable only if both ops operate on
650 // the same memref and if `srcMemOp` and `destMemOp` are in the same
651 // AffineScope. Also, we can only check if our affine scope is isolated from
652 // above; otherwise, values can from outside of the affine scope that the
653 // check below cannot analyze.
654 Region *srcScope = getAffineAnalysisScope(op: srcMemOp);
655 if (srcAccess.memref == destAccess.memref &&
656 srcScope == getAffineAnalysisScope(op: destMemOp)) {
657 unsigned nsLoops = getNumCommonSurroundingLoops(a&: *srcMemOp, b&: *destMemOp);
658 FlatAffineValueConstraints dependenceConstraints;
659 for (unsigned d = nsLoops + 1; d > minSurroundingLoops; d--) {
660 DependenceResult result = checkMemrefAccessDependence(
661 srcAccess, dstAccess: destAccess, loopDepth: d, dependenceConstraints: &dependenceConstraints,
662 /*dependenceComponents=*/nullptr);
663 // A dependence failure or the presence of a dependence implies a
664 // side effect.
665 if (!noDependence(result))
666 return true;
667 }
668 // No side effect was seen.
669 return false;
670 }
671 // TODO: Check here if the memrefs alias: there is no side effect if
672 // `srcAccess.memref` and `destAccess.memref` don't alias.
673 return true;
674}
675
676template <typename EffectType, typename T>
677bool mlir::affine::hasNoInterveningEffect(
678 Operation *start, T memOp,
679 llvm::function_ref<bool(Value, Value)> mayAlias) {
680 // A boolean representing whether an intervening operation could have impacted
681 // memOp.
682 bool hasSideEffect = false;
683
684 // Check whether the effect on memOp can be caused by a given operation op.
685 Value memref = memOp.getMemRef();
686 std::function<void(Operation *)> checkOperation = [&](Operation *op) {
687 // If the effect has alreay been found, early exit,
688 if (hasSideEffect)
689 return;
690
691 if (auto memEffect = dyn_cast<MemoryEffectOpInterface>(Val: op)) {
692 SmallVector<MemoryEffects::EffectInstance, 1> effects;
693 memEffect.getEffects(effects);
694
695 bool opMayHaveEffect = false;
696 for (auto effect : effects) {
697 // If op causes EffectType on a potentially aliasing location for
698 // memOp, mark as having the effect.
699 if (isa<EffectType>(effect.getEffect())) {
700 if (effect.getValue() && effect.getValue() != memref &&
701 !mayAlias(effect.getValue(), memref))
702 continue;
703 opMayHaveEffect = true;
704 break;
705 }
706 }
707
708 if (!opMayHaveEffect)
709 return;
710
711 // If the side effect comes from an affine read or write, try to
712 // prove the side effecting `op` cannot reach `memOp`.
713 if (isa<AffineReadOpInterface, AffineWriteOpInterface>(Val: op)) {
714 // For ease, let's consider the case that `op` is a store and
715 // we're looking for other potential stores that overwrite memory after
716 // `start`, and before being read in `memOp`. In this case, we only
717 // need to consider other potential stores with depth >
718 // minSurroundingLoops since `start` would overwrite any store with a
719 // smaller number of surrounding loops before.
720 unsigned minSurroundingLoops =
721 getNumCommonSurroundingLoops(*start, *memOp);
722 if (mayHaveEffect(op, memOp, minSurroundingLoops))
723 hasSideEffect = true;
724 return;
725 }
726
727 // We have an op with a memory effect and we cannot prove if it
728 // intervenes.
729 hasSideEffect = true;
730 return;
731 }
732
733 if (op->hasTrait<OpTrait::HasRecursiveMemoryEffects>()) {
734 // Recurse into the regions for this op and check whether the internal
735 // operations may have the side effect `EffectType` on memOp.
736 for (Region &region : op->getRegions())
737 for (Block &block : region)
738 for (Operation &op : block)
739 checkOperation(&op);
740 return;
741 }
742
743 // Otherwise, conservatively assume generic operations have the effect
744 // on the operation
745 hasSideEffect = true;
746 };
747
748 // Check all paths from ancestor op `parent` to the operation `to` for the
749 // effect. It is known that `to` must be contained within `parent`.
750 auto until = [&](Operation *parent, Operation *to) {
751 // TODO check only the paths from `parent` to `to`.
752 // Currently we fallback and check the entire parent op, rather than
753 // just the paths from the parent path, stopping after reaching `to`.
754 // This is conservatively correct, but could be made more aggressive.
755 assert(parent->isAncestor(to));
756 checkOperation(parent);
757 };
758
759 // Check for all paths from operation `from` to operation `untilOp` for the
760 // given memory effect.
761 std::function<void(Operation *, Operation *)> recur =
762 [&](Operation *from, Operation *untilOp) {
763 assert(
764 from->getParentRegion()->isAncestor(untilOp->getParentRegion()) &&
765 "Checking for side effect between two operations without a common "
766 "ancestor");
767
768 // If the operations are in different regions, recursively consider all
769 // path from `from` to the parent of `to` and all paths from the parent
770 // of `to` to `to`.
771 if (from->getParentRegion() != untilOp->getParentRegion()) {
772 recur(from, untilOp->getParentOp());
773 until(untilOp->getParentOp(), untilOp);
774 return;
775 }
776
777 // Now, assuming that `from` and `to` exist in the same region, perform
778 // a CFG traversal to check all the relevant operations.
779
780 // Additional blocks to consider.
781 SmallVector<Block *, 2> todoBlocks;
782 {
783 // First consider the parent block of `from` an check all operations
784 // after `from`.
785 for (auto iter = ++from->getIterator(), end = from->getBlock()->end();
786 iter != end && &*iter != untilOp; ++iter) {
787 checkOperation(&*iter);
788 }
789
790 // If the parent of `from` doesn't contain `to`, add the successors
791 // to the list of blocks to check.
792 if (untilOp->getBlock() != from->getBlock())
793 for (Block *succ : from->getBlock()->getSuccessors())
794 todoBlocks.push_back(Elt: succ);
795 }
796
797 SmallPtrSet<Block *, 4> done;
798 // Traverse the CFG until hitting `to`.
799 while (!todoBlocks.empty()) {
800 Block *blk = todoBlocks.pop_back_val();
801 if (done.count(Ptr: blk))
802 continue;
803 done.insert(Ptr: blk);
804 for (auto &op : *blk) {
805 if (&op == untilOp)
806 break;
807 checkOperation(&op);
808 if (&op == blk->getTerminator())
809 for (Block *succ : blk->getSuccessors())
810 todoBlocks.push_back(Elt: succ);
811 }
812 }
813 };
814 recur(start, memOp);
815 return !hasSideEffect;
816}
817
818/// Attempt to eliminate loadOp by replacing it with a value stored into memory
819/// which the load is guaranteed to retrieve. This check involves three
820/// components: 1) The store and load must be on the same location 2) The store
821/// must dominate (and therefore must always occur prior to) the load 3) No
822/// other operations will overwrite the memory loaded between the given load
823/// and store. If such a value exists, the replaced `loadOp` will be added to
824/// `loadOpsToErase` and its memref will be added to `memrefsToErase`.
825static void forwardStoreToLoad(
826 AffineReadOpInterface loadOp, SmallVectorImpl<Operation *> &loadOpsToErase,
827 SmallPtrSetImpl<Value> &memrefsToErase, DominanceInfo &domInfo,
828 llvm::function_ref<bool(Value, Value)> mayAlias) {
829
830 // The store op candidate for forwarding that satisfies all conditions
831 // to replace the load, if any.
832 Operation *lastWriteStoreOp = nullptr;
833
834 for (auto storeOp : llvm::make_isa_range<AffineWriteOpInterface>(
835 Range: loadOp.getMemRef().getUsers())) {
836 MemRefAccess srcAccess(storeOp);
837 MemRefAccess destAccess(loadOp);
838
839 // 1. Check if the store and the load have mathematically equivalent
840 // affine access functions; this implies that they statically refer to the
841 // same single memref element. As an example this filters out cases like:
842 // store %A[%i0 + 1]
843 // load %A[%i0]
844 // store %A[%M]
845 // load %A[%N]
846 // Use the AffineValueMap difference based memref access equality checking.
847 if (srcAccess != destAccess)
848 continue;
849
850 // 2. The store has to dominate the load op to be candidate.
851 if (!domInfo.dominates(a: storeOp, b: loadOp))
852 continue;
853
854 // 3. The store must reach the load. Access function equivalence only
855 // guarantees this for accesses in the same block. The load could be in a
856 // nested block that is unreachable.
857 if (!mustReachAtInnermost(srcAccess, destAccess))
858 continue;
859
860 // 4. Ensure there is no intermediate operation which could replace the
861 // value in memory.
862 if (!affine::hasNoInterveningEffect<MemoryEffects::Write>(start: storeOp, memOp: loadOp,
863 mayAlias))
864 continue;
865
866 // We now have a candidate for forwarding.
867 assert(lastWriteStoreOp == nullptr &&
868 "multiple simultaneous replacement stores");
869 lastWriteStoreOp = storeOp;
870 }
871
872 if (!lastWriteStoreOp)
873 return;
874
875 // Perform the actual store to load forwarding.
876 Value storeVal =
877 cast<AffineWriteOpInterface>(Val: lastWriteStoreOp).getValueToStore();
878 // Check if 2 values have the same shape. This is needed for affine vector
879 // loads and stores.
880 if (storeVal.getType() != loadOp.getValue().getType())
881 return;
882 loadOp.getValue().replaceAllUsesWith(newValue: storeVal);
883 // Record the memref for a later sweep to optimize away.
884 memrefsToErase.insert(Ptr: loadOp.getMemRef());
885 // Record this to erase later.
886 loadOpsToErase.push_back(Elt: loadOp);
887}
888
889template bool
890mlir::affine::hasNoInterveningEffect<mlir::MemoryEffects::Read,
891 affine::AffineReadOpInterface>(
892 mlir::Operation *, affine::AffineReadOpInterface,
893 llvm::function_ref<bool(Value, Value)>);
894
895// This attempts to find stores which have no impact on the final result.
896// A writing op writeA will be eliminated if there exists an op writeB if
897// 1) writeA and writeB have mathematically equivalent affine access functions.
898// 2) writeB writes the same type as writeA (so it fully covers writeA's bytes).
899// 3) writeB postdominates writeA.
900// 4) There is no potential read between writeA and writeB.
901static void findUnusedStore(AffineWriteOpInterface writeA,
902 SmallVectorImpl<Operation *> &opsToErase,
903 PostDominanceInfo &postDominanceInfo,
904 llvm::function_ref<bool(Value, Value)> mayAlias) {
905
906 // Only consider writing operations.
907 for (auto writeB : llvm::make_isa_range<AffineWriteOpInterface>(
908 Range: writeA.getMemRef().getUsers())) {
909 // The operations must be distinct.
910 if (writeB == writeA)
911 continue;
912
913 // Both operations must lie in the same region.
914 if (writeB->getParentRegion() != writeA->getParentRegion())
915 continue;
916
917 // Both operations must write to the same memory.
918 MemRefAccess srcAccess(writeB);
919 MemRefAccess destAccess(writeA);
920
921 if (srcAccess != destAccess)
922 continue;
923
924 // Check that the store types match. If types differ, writeB may not cover
925 // all bytes written by writeA (e.g. a narrower vector type), so
926 // conservatively assume writeA is not dead.
927 // One could be tempted whether writeA type is smaller than writeB, however
928 // it can become tricky with cases like vector<4xi6> vs vector<3xi8> due to
929 // padding that can be datalayout dependent.
930 if (writeA.getValueToStore().getType() !=
931 writeB.getValueToStore().getType())
932 continue;
933
934 // writeB must postdominate writeA.
935 if (!postDominanceInfo.postDominates(a: writeB, b: writeA))
936 continue;
937
938 // There cannot be an operation which reads from memory between
939 // the two writes.
940 if (!affine::hasNoInterveningEffect<MemoryEffects::Read>(start: writeA, memOp: writeB,
941 mayAlias))
942 continue;
943
944 opsToErase.push_back(Elt: writeA);
945 break;
946 }
947}
948
949// The load to load forwarding / redundant load elimination is similar to the
950// store to load forwarding.
951// loadA will be be replaced with loadB if:
952// 1) loadA and loadB have mathematically equivalent affine access functions.
953// 2) loadB dominates loadA.
954// 3) There is no write between loadA and loadB.
955static void loadCSE(AffineReadOpInterface loadA,
956 SmallVectorImpl<Operation *> &loadOpsToErase,
957 DominanceInfo &domInfo,
958 llvm::function_ref<bool(Value, Value)> mayAlias) {
959 SmallVector<AffineReadOpInterface, 4> loadCandidates;
960 for (auto *user : loadA.getMemRef().getUsers()) {
961 auto loadB = dyn_cast<AffineReadOpInterface>(Val: user);
962 if (!loadB || loadB == loadA)
963 continue;
964
965 MemRefAccess srcAccess(loadB);
966 MemRefAccess destAccess(loadA);
967
968 // 1. The accesses should be to be to the same location.
969 if (srcAccess != destAccess) {
970 continue;
971 }
972
973 // 2. loadB should dominate loadA.
974 if (!domInfo.dominates(a: loadB, b: loadA))
975 continue;
976
977 // 3. There should not be a write between loadA and loadB.
978 if (!affine::hasNoInterveningEffect<MemoryEffects::Write>(
979 start: loadB.getOperation(), memOp: loadA, mayAlias))
980 continue;
981
982 // Check if two values have the same shape. This is needed for affine vector
983 // loads.
984 if (loadB.getValue().getType() != loadA.getValue().getType())
985 continue;
986
987 loadCandidates.push_back(Elt: loadB);
988 }
989
990 // Of the legal load candidates, use the one that dominates all others
991 // to minimize the subsequent need to loadCSE
992 Value loadB;
993 for (AffineReadOpInterface option : loadCandidates) {
994 if (llvm::all_of(Range&: loadCandidates, P: [&](AffineReadOpInterface depStore) {
995 return depStore == option ||
996 domInfo.dominates(a: option.getOperation(),
997 b: depStore.getOperation());
998 })) {
999 loadB = option.getValue();
1000 break;
1001 }
1002 }
1003
1004 if (loadB) {
1005 loadA.getValue().replaceAllUsesWith(newValue: loadB);
1006 // Record this to erase later.
1007 loadOpsToErase.push_back(Elt: loadA);
1008 }
1009}
1010
1011// The store to load forwarding and load CSE rely on three conditions:
1012//
1013// 1) store/load providing a replacement value and load being replaced need to
1014// have mathematically equivalent affine access functions (checked after full
1015// composition of load/store operands); this implies that they access the same
1016// single memref element for all iterations of the common surrounding loop,
1017//
1018// 2) the store/load op should dominate the load op,
1019//
1020// 3) no operation that may write to memory read by the load being replaced can
1021// occur after executing the instruction (load or store) providing the
1022// replacement value and before the load being replaced (thus potentially
1023// allowing overwriting the memory read by the load).
1024//
1025// The above conditions are simple to check, sufficient, and powerful for most
1026// cases in practice - they are sufficient, but not necessary --- since they
1027// don't reason about loops that are guaranteed to execute at least once or
1028// multiple sources to forward from.
1029//
1030// TODO: more forwarding can be done when support for
1031// loop/conditional live-out SSA values is available.
1032// TODO: do general dead store elimination for memref's. This pass
1033// currently only eliminates the stores only if no other loads/uses (other
1034// than dealloc) remain.
1035//
1036void mlir::affine::affineScalarReplace(func::FuncOp f, DominanceInfo &domInfo,
1037 PostDominanceInfo &postDomInfo,
1038 AliasAnalysis &aliasAnalysis) {
1039 // Load op's whose results were replaced by those forwarded from stores.
1040 SmallVector<Operation *, 8> opsToErase;
1041
1042 // A list of memref's that are potentially dead / could be eliminated.
1043 SmallPtrSet<Value, 4> memrefsToErase;
1044
1045 auto mayAlias = [&](Value val1, Value val2) -> bool {
1046 return !aliasAnalysis.alias(lhs: val1, rhs: val2).isNo();
1047 };
1048
1049 // Walk all load's and perform store to load forwarding.
1050 f.walk(callback: [&](AffineReadOpInterface loadOp) {
1051 forwardStoreToLoad(loadOp, loadOpsToErase&: opsToErase, memrefsToErase, domInfo, mayAlias);
1052 });
1053 for (auto *op : opsToErase)
1054 op->erase();
1055 opsToErase.clear();
1056
1057 // Walk all store's and perform unused store elimination
1058 f.walk(callback: [&](AffineWriteOpInterface storeOp) {
1059 findUnusedStore(writeA: storeOp, opsToErase, postDominanceInfo&: postDomInfo, mayAlias);
1060 });
1061 for (auto *op : opsToErase)
1062 op->erase();
1063 opsToErase.clear();
1064
1065 // Check if the store fwd'ed memrefs are now left with only stores and
1066 // deallocs and can thus be completely deleted. Note: the canonicalize pass
1067 // should be able to do this as well, but we'll do it here since we collected
1068 // these anyway.
1069 for (auto memref : memrefsToErase) {
1070 // If the memref hasn't been locally alloc'ed, skip.
1071 Operation *defOp = memref.getDefiningOp();
1072 if (!defOp || !hasSingleEffect<MemoryEffects::Allocate>(op: defOp, value: memref))
1073 // TODO: if the memref was returned by a 'call' operation, we
1074 // could still erase it if the call had no side-effects.
1075 continue;
1076 if (llvm::any_of(Range: memref.getUsers(), P: [&](Operation *ownerOp) {
1077 return !isa<AffineWriteOpInterface>(Val: ownerOp) &&
1078 !hasSingleEffect<MemoryEffects::Free>(op: ownerOp, value: memref);
1079 }))
1080 continue;
1081
1082 // Erase all stores, the dealloc, and the alloc on the memref.
1083 for (auto *user : llvm::make_early_inc_range(Range: memref.getUsers()))
1084 user->erase();
1085 defOp->erase();
1086 }
1087
1088 // To eliminate as many loads as possible, run load CSE after eliminating
1089 // stores. Otherwise, some stores are wrongly seen as having an intervening
1090 // effect.
1091 f.walk(callback: [&](AffineReadOpInterface loadOp) {
1092 loadCSE(loadA: loadOp, loadOpsToErase&: opsToErase, domInfo, mayAlias);
1093 });
1094 for (auto *op : opsToErase)
1095 op->erase();
1096}
1097
1098// Checks if `op` is non dereferencing.
1099// TODO: This hardcoded check will be removed once the right interface is added.
1100static bool isDereferencingOp(Operation *op) {
1101 return isa<AffineMapAccessInterface, memref::LoadOp, memref::StoreOp>(Val: op);
1102}
1103
1104// Perform the replacement in `op`.
1105LogicalResult mlir::affine::replaceAllMemRefUsesWith(
1106 Value oldMemRef, Value newMemRef, Operation *op,
1107 ArrayRef<Value> extraIndices, AffineMap indexRemap,
1108 ArrayRef<Value> extraOperands, ArrayRef<Value> symbolOperands,
1109 bool allowNonDereferencingOps) {
1110 unsigned newMemRefRank = cast<MemRefType>(Val: newMemRef.getType()).getRank();
1111 (void)newMemRefRank; // unused in opt mode
1112 unsigned oldMemRefRank = cast<MemRefType>(Val: oldMemRef.getType()).getRank();
1113 (void)oldMemRefRank; // unused in opt mode
1114 if (indexRemap) {
1115 assert(indexRemap.getNumSymbols() == symbolOperands.size() &&
1116 "symbolic operand count mismatch");
1117 assert(indexRemap.getNumInputs() ==
1118 extraOperands.size() + oldMemRefRank + symbolOperands.size());
1119 assert(indexRemap.getNumResults() + extraIndices.size() == newMemRefRank);
1120 } else {
1121 assert(oldMemRefRank + extraIndices.size() == newMemRefRank);
1122 }
1123
1124 // Assert same elemental type.
1125 assert(cast<MemRefType>(oldMemRef.getType()).getElementType() ==
1126 cast<MemRefType>(newMemRef.getType()).getElementType());
1127
1128 SmallVector<unsigned, 2> usePositions;
1129 for (const auto &opEntry : llvm::enumerate(First: op->getOperands())) {
1130 if (opEntry.value() == oldMemRef)
1131 usePositions.push_back(Elt: opEntry.index());
1132 }
1133
1134 // If memref doesn't appear, nothing to do.
1135 if (usePositions.empty())
1136 return success();
1137
1138 unsigned memRefOperandPos = usePositions.front();
1139
1140 OpBuilder builder(op);
1141 // The following checks if op is dereferencing memref and performs the access
1142 // index rewrites.
1143 if (!isDereferencingOp(op)) {
1144 if (!allowNonDereferencingOps) {
1145 // Failure: memref used in a non-dereferencing context (potentially
1146 // escapes); no replacement in these cases unless allowNonDereferencingOps
1147 // is set.
1148 return failure();
1149 }
1150 for (unsigned pos : usePositions)
1151 op->setOperand(idx: pos, value: newMemRef);
1152 return success();
1153 }
1154
1155 if (usePositions.size() > 1) {
1156 // TODO: extend it for this case when needed (rare).
1157 LLVM_DEBUG(llvm::dbgs()
1158 << "multiple dereferencing uses in a single op not supported");
1159 return failure();
1160 }
1161
1162 // Perform index rewrites for the dereferencing op and then replace the op.
1163 SmallVector<Value, 4> oldMapOperands;
1164 AffineMap oldMap;
1165 unsigned oldMemRefNumIndices = oldMemRefRank;
1166 auto startIdx = op->operand_begin() + memRefOperandPos + 1;
1167 auto affMapAccInterface = dyn_cast<AffineMapAccessInterface>(Val: op);
1168 if (affMapAccInterface) {
1169 // If `op` implements AffineMapAccessInterface, we can get the indices by
1170 // quering the number of map operands from the operand list from a certain
1171 // offset (`memRefOperandPos` in this case).
1172 NamedAttribute oldMapAttrPair =
1173 affMapAccInterface.getAffineMapAttrForMemRef(memref: oldMemRef);
1174 oldMap = cast<AffineMapAttr>(Val: oldMapAttrPair.getValue()).getValue();
1175 oldMemRefNumIndices = oldMap.getNumInputs();
1176 }
1177 oldMapOperands.assign(in_start: startIdx, in_end: startIdx + oldMemRefNumIndices);
1178
1179 // Apply 'oldMemRefOperands = oldMap(oldMapOperands)'.
1180 SmallVector<Value, 4> oldMemRefOperands;
1181 SmallVector<Value, 4> affineApplyOps;
1182 oldMemRefOperands.reserve(N: oldMemRefRank);
1183 if (affMapAccInterface &&
1184 oldMap != builder.getMultiDimIdentityMap(rank: oldMap.getNumDims())) {
1185 for (auto resultExpr : oldMap.getResults()) {
1186 auto singleResMap = AffineMap::get(dimCount: oldMap.getNumDims(),
1187 symbolCount: oldMap.getNumSymbols(), result: resultExpr);
1188 auto afOp = AffineApplyOp::create(builder, location: op->getLoc(), map: singleResMap,
1189 mapOperands: oldMapOperands);
1190 oldMemRefOperands.push_back(Elt: afOp);
1191 affineApplyOps.push_back(Elt: afOp);
1192 }
1193 } else {
1194 oldMemRefOperands.assign(in_start: oldMapOperands.begin(), in_end: oldMapOperands.end());
1195 }
1196
1197 // Construct new indices as a remap of the old ones if a remapping has been
1198 // provided. The indices of a memref come right after it, i.e.,
1199 // at position memRefOperandPos + 1.
1200 SmallVector<Value, 4> remapOperands;
1201 remapOperands.reserve(N: extraOperands.size() + oldMemRefRank +
1202 symbolOperands.size());
1203 remapOperands.append(in_start: extraOperands.begin(), in_end: extraOperands.end());
1204 remapOperands.append(in_start: oldMemRefOperands.begin(), in_end: oldMemRefOperands.end());
1205 remapOperands.append(in_start: symbolOperands.begin(), in_end: symbolOperands.end());
1206
1207 SmallVector<Value, 4> remapOutputs;
1208 remapOutputs.reserve(N: oldMemRefRank);
1209 if (indexRemap &&
1210 indexRemap != builder.getMultiDimIdentityMap(rank: indexRemap.getNumDims())) {
1211 // Remapped indices.
1212 for (auto resultExpr : indexRemap.getResults()) {
1213 auto singleResMap = AffineMap::get(
1214 dimCount: indexRemap.getNumDims(), symbolCount: indexRemap.getNumSymbols(), result: resultExpr);
1215 auto afOp = AffineApplyOp::create(builder, location: op->getLoc(), map: singleResMap,
1216 mapOperands: remapOperands);
1217 remapOutputs.push_back(Elt: afOp);
1218 affineApplyOps.push_back(Elt: afOp);
1219 }
1220 } else {
1221 // No remapping specified.
1222 remapOutputs.assign(in_start: remapOperands.begin(), in_end: remapOperands.end());
1223 }
1224 SmallVector<Value, 4> newMapOperands;
1225 newMapOperands.reserve(N: newMemRefRank);
1226
1227 // Prepend 'extraIndices' in 'newMapOperands'.
1228 for (Value extraIndex : extraIndices) {
1229 assert((isValidDim(extraIndex) || isValidSymbol(extraIndex)) &&
1230 "invalid memory op index");
1231 newMapOperands.push_back(Elt: extraIndex);
1232 }
1233
1234 // Append 'remapOutputs' to 'newMapOperands'.
1235 newMapOperands.append(in_start: remapOutputs.begin(), in_end: remapOutputs.end());
1236
1237 // Create new fully composed AffineMap for new op to be created.
1238 assert(newMapOperands.size() == newMemRefRank);
1239 auto newMap = builder.getMultiDimIdentityMap(rank: newMemRefRank);
1240 fullyComposeAffineMapAndOperands(map: &newMap, operands: &newMapOperands);
1241 newMap = simplifyAffineMap(map: newMap);
1242 canonicalizeMapAndOperands(map: &newMap, operands: &newMapOperands);
1243 // Remove any affine.apply's that became dead as a result of composition.
1244 for (Value value : affineApplyOps)
1245 if (value.use_empty())
1246 value.getDefiningOp()->erase();
1247
1248 OperationState state(op->getLoc(), op->getName());
1249 // Construct the new operation using this memref.
1250 state.operands.reserve(N: op->getNumOperands() + extraIndices.size());
1251 // Insert the non-memref operands.
1252 state.operands.append(in_start: op->operand_begin(),
1253 in_end: op->operand_begin() + memRefOperandPos);
1254 // Insert the new memref value.
1255 state.operands.push_back(Elt: newMemRef);
1256
1257 // Insert the new memref map operands.
1258 if (affMapAccInterface) {
1259 state.operands.append(in_start: newMapOperands.begin(), in_end: newMapOperands.end());
1260 } else {
1261 // In the case of dereferencing ops not implementing
1262 // AffineMapAccessInterface, we need to apply the values of `newMapOperands`
1263 // to the `newMap` to get the correct indices.
1264 for (unsigned i = 0; i < newMemRefRank; i++) {
1265 state.operands.push_back(Elt: AffineApplyOp::create(
1266 builder, location: op->getLoc(),
1267 map: AffineMap::get(dimCount: newMap.getNumDims(), symbolCount: newMap.getNumSymbols(),
1268 result: newMap.getResult(idx: i)),
1269 mapOperands: newMapOperands));
1270 }
1271 }
1272
1273 // Insert the remaining operands unmodified.
1274 unsigned oldMapNumInputs = oldMapOperands.size();
1275 state.operands.append(in_start: op->operand_begin() + memRefOperandPos + 1 +
1276 oldMapNumInputs,
1277 in_end: op->operand_end());
1278 // Result types don't change. Both memref's are of the same elemental type.
1279 state.types.reserve(N: op->getNumResults());
1280 for (auto result : op->getResults())
1281 state.types.push_back(Elt: result.getType());
1282
1283 // Add attribute for 'newMap', other Attributes do not change.
1284 auto newMapAttr = AffineMapAttr::get(value: newMap);
1285 state.addAttributes(newAttributes: op->getDiscardableAttrDictionary().getValue());
1286 state.propertiesAttr = op->getPropertiesAsAttribute();
1287
1288 // Create the new operation.
1289 auto *repOp = builder.create(state);
1290 if (affMapAccInterface) {
1291 StringAttr mapAttrName =
1292 affMapAccInterface.getAffineMapAttrForMemRef(memref: oldMemRef).getName();
1293 repOp->setInherentAttr(name: mapAttrName, value: newMapAttr);
1294 }
1295 op->replaceAllUsesWith(values&: repOp);
1296 op->erase();
1297
1298 return success();
1299}
1300
1301LogicalResult mlir::affine::replaceAllMemRefUsesWith(
1302 Value oldMemRef, Value newMemRef, ArrayRef<Value> extraIndices,
1303 AffineMap indexRemap, ArrayRef<Value> extraOperands,
1304 ArrayRef<Value> symbolOperands,
1305 llvm::function_ref<bool(Operation *)> userFilterFn,
1306 bool allowNonDereferencingOps, bool replaceInDeallocOp) {
1307 unsigned newMemRefRank = cast<MemRefType>(Val: newMemRef.getType()).getRank();
1308 (void)newMemRefRank; // unused in opt mode
1309 unsigned oldMemRefRank = cast<MemRefType>(Val: oldMemRef.getType()).getRank();
1310 (void)oldMemRefRank;
1311 if (indexRemap) {
1312 assert(indexRemap.getNumSymbols() == symbolOperands.size() &&
1313 "symbol operand count mismatch");
1314 assert(indexRemap.getNumInputs() ==
1315 extraOperands.size() + oldMemRefRank + symbolOperands.size());
1316 assert(indexRemap.getNumResults() + extraIndices.size() == newMemRefRank);
1317 } else {
1318 assert(oldMemRefRank + extraIndices.size() == newMemRefRank);
1319 }
1320
1321 // Assert same elemental type.
1322 assert(cast<MemRefType>(oldMemRef.getType()).getElementType() ==
1323 cast<MemRefType>(newMemRef.getType()).getElementType());
1324
1325 // Walk all uses of old memref; collect ops to perform replacement. We use a
1326 // DenseSet since an operation could potentially have multiple uses of a
1327 // memref (although rare), and the replacement later is going to erase ops.
1328 DenseSet<Operation *> opsToReplace;
1329 for (auto *user : oldMemRef.getUsers()) {
1330 // Check if this user doesn't pass the filter.
1331 if (userFilterFn && !userFilterFn(user))
1332 continue;
1333
1334 // Skip dealloc's - no replacement is necessary, and a memref replacement
1335 // at other uses doesn't hurt these dealloc's.
1336 if (hasSingleEffect<MemoryEffects::Free>(op: user, value: oldMemRef) &&
1337 !replaceInDeallocOp)
1338 continue;
1339
1340 // Check if the memref was used in a non-dereferencing context. It is fine
1341 // for the memref to be used in a non-dereferencing way outside of the
1342 // region where this replacement is happening.
1343 if (!isa<AffineMapAccessInterface>(Val: *user)) {
1344 if (!allowNonDereferencingOps) {
1345 LLVM_DEBUG(
1346 llvm::dbgs()
1347 << "Memref replacement failed: non-deferencing memref user: \n"
1348 << *user << '\n');
1349 return failure();
1350 }
1351 // Non-dereferencing ops with the MemRefsNormalizable trait are
1352 // supported for replacement.
1353 if (!user->hasTrait<OpTrait::MemRefsNormalizable>()) {
1354 LLVM_DEBUG(llvm::dbgs() << "Memref replacement failed: use without a "
1355 "memrefs normalizable trait: \n"
1356 << *user << '\n');
1357 return failure();
1358 }
1359 }
1360
1361 // We'll first collect and then replace --- since replacement erases the
1362 // user that has the use, and that user could be postDomFilter or domFilter
1363 // itself!
1364 opsToReplace.insert(V: user);
1365 }
1366
1367 for (auto *user : opsToReplace) {
1368 if (failed(Result: replaceAllMemRefUsesWith(
1369 oldMemRef, newMemRef, op: user, extraIndices, indexRemap, extraOperands,
1370 symbolOperands, allowNonDereferencingOps)))
1371 return failure();
1372 }
1373
1374 return success();
1375}
1376
1377/// Given an operation, inserts one or more single result affine
1378/// apply operations, results of which are exclusively used by this operation
1379/// operation. The operands of these newly created affine apply ops are
1380/// guaranteed to be loop iterators or terminal symbols of a function.
1381///
1382/// Before
1383///
1384/// affine.for %i = 0 to #map(%N)
1385/// %idx = affine.apply (d0) -> (d0 mod 2) (%i)
1386/// "send"(%idx, %A, ...)
1387/// "compute"(%idx)
1388///
1389/// After
1390///
1391/// affine.for %i = 0 to #map(%N)
1392/// %idx = affine.apply (d0) -> (d0 mod 2) (%i)
1393/// "send"(%idx, %A, ...)
1394/// %idx_ = affine.apply (d0) -> (d0 mod 2) (%i)
1395/// "compute"(%idx_)
1396///
1397/// This allows applying different transformations on send and compute (for eg.
1398/// different shifts/delays).
1399///
1400/// Returns nullptr either if none of opInst's operands were the result of an
1401/// affine.apply and thus there was no affine computation slice to create, or if
1402/// all the affine.apply op's supplying operands to this opInst did not have any
1403/// uses besides this opInst; otherwise returns the list of affine.apply
1404/// operations created in output argument `sliceOps`.
1405void mlir::affine::createAffineComputationSlice(
1406 Operation *opInst, SmallVectorImpl<AffineApplyOp> *sliceOps) {
1407 // Collect all operands that are results of affine apply ops.
1408 SmallVector<Value, 4> subOperands;
1409 subOperands.reserve(N: opInst->getNumOperands());
1410 for (auto operand : opInst->getOperands())
1411 if (isa_and_nonnull<AffineApplyOp>(Val: operand.getDefiningOp()))
1412 subOperands.push_back(Elt: operand);
1413
1414 // Gather sequence of AffineApplyOps reachable from 'subOperands'.
1415 SmallVector<Operation *, 4> affineApplyOps;
1416 getReachableAffineApplyOps(operands: subOperands, affineApplyOps);
1417 // Skip transforming if there are no affine maps to compose.
1418 if (affineApplyOps.empty())
1419 return;
1420
1421 // Check if all uses of the affine apply op's lie only in this op op, in
1422 // which case there would be nothing to do.
1423 bool localized = true;
1424 for (auto *op : affineApplyOps) {
1425 for (auto result : op->getResults()) {
1426 for (auto *user : result.getUsers()) {
1427 if (user != opInst) {
1428 localized = false;
1429 break;
1430 }
1431 }
1432 }
1433 }
1434 if (localized)
1435 return;
1436
1437 OpBuilder builder(opInst);
1438 SmallVector<Value, 4> composedOpOperands(subOperands);
1439 auto composedMap = builder.getMultiDimIdentityMap(rank: composedOpOperands.size());
1440 fullyComposeAffineMapAndOperands(map: &composedMap, operands: &composedOpOperands);
1441
1442 // Create an affine.apply for each of the map results.
1443 sliceOps->reserve(N: composedMap.getNumResults());
1444 for (auto resultExpr : composedMap.getResults()) {
1445 auto singleResMap = AffineMap::get(dimCount: composedMap.getNumDims(),
1446 symbolCount: composedMap.getNumSymbols(), result: resultExpr);
1447 sliceOps->push_back(Elt: AffineApplyOp::create(
1448 builder, location: opInst->getLoc(), map: singleResMap, mapOperands: composedOpOperands));
1449 }
1450
1451 // Construct the new operands that include the results from the composed
1452 // affine apply op above instead of existing ones (subOperands). So, they
1453 // differ from opInst's operands only for those operands in 'subOperands', for
1454 // which they will be replaced by the corresponding one from 'sliceOps'.
1455 SmallVector<Value, 4> newOperands(opInst->getOperands());
1456 for (Value &operand : newOperands) {
1457 // Replace the subOperands from among the new operands.
1458 unsigned j, f;
1459 for (j = 0, f = subOperands.size(); j < f; j++) {
1460 if (operand == subOperands[j])
1461 break;
1462 }
1463 if (j < subOperands.size())
1464 operand = (*sliceOps)[j];
1465 }
1466 for (unsigned idx = 0, e = newOperands.size(); idx < e; idx++)
1467 opInst->setOperand(idx, value: newOperands[idx]);
1468}
1469
1470/// Enum to set patterns of affine expr in tiled-layout map.
1471/// TileFloorDiv: <dim expr> div <tile size>
1472/// TileMod: <dim expr> mod <tile size>
1473/// TileNone: None of the above
1474/// Example:
1475/// #tiled_2d_128x256 = affine_map<(d0, d1)
1476/// -> (d0 div 128, d1 div 256, d0 mod 128, d1 mod 256)>
1477/// "d0 div 128" and "d1 div 256" ==> TileFloorDiv
1478/// "d0 mod 128" and "d1 mod 256" ==> TileMod
1479enum TileExprPattern { TileFloorDiv, TileMod, TileNone };
1480
1481/// Check if `map` is a tiled layout. In the tiled layout, specific k dimensions
1482/// being floordiv'ed by respective tile sizes appeare in a mod with the same
1483/// tile sizes, and no other expression involves those k dimensions. This
1484/// function stores a vector of tuples (`tileSizePos`) including AffineExpr for
1485/// tile size, positions of corresponding `floordiv` and `mod`. If it is not a
1486/// tiled layout, an empty vector is returned.
1487static LogicalResult getTileSizePos(
1488 AffineMap map,
1489 SmallVectorImpl<std::tuple<AffineExpr, unsigned, unsigned>> &tileSizePos) {
1490 // Create `floordivExprs` which is a vector of tuples including LHS and RHS of
1491 // `floordiv` and its position in `map` output.
1492 // Example: #tiled_2d_128x256 = affine_map<(d0, d1)
1493 // -> (d0 div 128, d1 div 256, d0 mod 128, d1 mod 256)>
1494 // In this example, `floordivExprs` includes {d0, 128, 0} and {d1, 256, 1}.
1495 SmallVector<std::tuple<AffineExpr, AffineExpr, unsigned>, 4> floordivExprs;
1496 unsigned pos = 0;
1497 for (AffineExpr expr : map.getResults()) {
1498 if (expr.getKind() == AffineExprKind::FloorDiv) {
1499 AffineBinaryOpExpr binaryExpr = cast<AffineBinaryOpExpr>(Val&: expr);
1500 if (isa<AffineConstantExpr>(Val: binaryExpr.getRHS()))
1501 floordivExprs.emplace_back(
1502 Args: std::make_tuple(args: binaryExpr.getLHS(), args: binaryExpr.getRHS(), args&: pos));
1503 }
1504 pos++;
1505 }
1506 // Not tiled layout if `floordivExprs` is empty.
1507 if (floordivExprs.empty()) {
1508 tileSizePos = SmallVector<std::tuple<AffineExpr, unsigned, unsigned>>{};
1509 return success();
1510 }
1511
1512 // Check if LHS of `floordiv` is used in LHS of `mod`. If not used, `map` is
1513 // not tiled layout.
1514 for (std::tuple<AffineExpr, AffineExpr, unsigned> fexpr : floordivExprs) {
1515 AffineExpr floordivExprLHS = std::get<0>(t&: fexpr);
1516 AffineExpr floordivExprRHS = std::get<1>(t&: fexpr);
1517 unsigned floordivPos = std::get<2>(t&: fexpr);
1518
1519 // Walk affinexpr of `map` output except `fexpr`, and check if LHS and RHS
1520 // of `fexpr` are used in LHS and RHS of `mod`. If LHS of `fexpr` is used
1521 // other expr, the map is not tiled layout. Example of non tiled layout:
1522 // affine_map<(d0, d1, d2) -> (d0, d1, d2 floordiv 256, d2 floordiv 256)>
1523 // affine_map<(d0, d1, d2) -> (d0, d1, d2 floordiv 256, d2 mod 128)>
1524 // affine_map<(d0, d1, d2) -> (d0, d1, d2 floordiv 256, d2 mod 256, d2 mod
1525 // 256)>
1526 bool found = false;
1527 pos = 0;
1528 for (AffineExpr expr : map.getResults()) {
1529 bool notTiled = false;
1530 if (pos != floordivPos) {
1531 expr.walk(callback: [&](AffineExpr e) {
1532 if (e == floordivExprLHS) {
1533 if (expr.getKind() == AffineExprKind::Mod) {
1534 AffineBinaryOpExpr binaryExpr = cast<AffineBinaryOpExpr>(Val&: expr);
1535 // If LHS and RHS of `mod` are the same with those of floordiv.
1536 if (floordivExprLHS == binaryExpr.getLHS() &&
1537 floordivExprRHS == binaryExpr.getRHS()) {
1538 // Save tile size (RHS of `mod`), and position of `floordiv` and
1539 // `mod` if same expr with `mod` is not found yet.
1540 if (!found) {
1541 tileSizePos.emplace_back(
1542 Args: std::make_tuple(args: binaryExpr.getRHS(), args&: floordivPos, args&: pos));
1543 found = true;
1544 } else {
1545 // Non tiled layout: Have multilpe `mod` with the same LHS.
1546 // eg. affine_map<(d0, d1, d2) -> (d0, d1, d2 floordiv 256, d2
1547 // mod 256, d2 mod 256)>
1548 notTiled = true;
1549 }
1550 } else {
1551 // Non tiled layout: RHS of `mod` is different from `floordiv`.
1552 // eg. affine_map<(d0, d1, d2) -> (d0, d1, d2 floordiv 256, d2
1553 // mod 128)>
1554 notTiled = true;
1555 }
1556 } else {
1557 // Non tiled layout: LHS is the same, but not `mod`.
1558 // eg. affine_map<(d0, d1, d2) -> (d0, d1, d2 floordiv 256, d2
1559 // floordiv 256)>
1560 notTiled = true;
1561 }
1562 }
1563 });
1564 }
1565 if (notTiled) {
1566 tileSizePos = SmallVector<std::tuple<AffineExpr, unsigned, unsigned>>{};
1567 return success();
1568 }
1569 pos++;
1570 }
1571 }
1572 return success();
1573}
1574
1575/// Check if `dim` dimension of memrefType with `layoutMap` becomes dynamic
1576/// after normalization. Dimensions that include dynamic dimensions in the map
1577/// output will become dynamic dimensions. Return true if `dim` is dynamic
1578/// dimension.
1579///
1580/// Example:
1581/// #map0 = affine_map<(d0, d1) -> (d0, d1 floordiv 32, d1 mod 32)>
1582///
1583/// If d1 is dynamic dimension, 2nd and 3rd dimension of map output are dynamic.
1584/// memref<4x?xf32, #map0> ==> memref<4x?x?xf32>
1585static bool
1586isNormalizedMemRefDynamicDim(unsigned dim, AffineMap layoutMap,
1587 SmallVectorImpl<unsigned> &inMemrefTypeDynDims) {
1588 AffineExpr expr = layoutMap.getResults()[dim];
1589 // Check if affine expr of the dimension includes dynamic dimension of input
1590 // memrefType.
1591 MLIRContext *context = layoutMap.getContext();
1592 return expr
1593 .walk(callback: [&](AffineExpr e) {
1594 if (isa<AffineDimExpr>(Val: e) &&
1595 llvm::any_of(Range&: inMemrefTypeDynDims, P: [&](unsigned dim) {
1596 return e == getAffineDimExpr(position: dim, context);
1597 }))
1598 return WalkResult::interrupt();
1599 return WalkResult::advance();
1600 })
1601 .wasInterrupted();
1602}
1603
1604/// Create affine expr to calculate dimension size for a tiled-layout map.
1605static AffineExpr createDimSizeExprForTiledLayout(AffineExpr oldMapOutput,
1606 TileExprPattern pat) {
1607 // Create map output for the patterns.
1608 // "floordiv <tile size>" ==> "ceildiv <tile size>"
1609 // "mod <tile size>" ==> "<tile size>"
1610 AffineExpr newMapOutput;
1611 AffineBinaryOpExpr binaryExpr = nullptr;
1612 switch (pat) {
1613 case TileExprPattern::TileMod:
1614 binaryExpr = cast<AffineBinaryOpExpr>(Val&: oldMapOutput);
1615 newMapOutput = binaryExpr.getRHS();
1616 break;
1617 case TileExprPattern::TileFloorDiv:
1618 binaryExpr = cast<AffineBinaryOpExpr>(Val&: oldMapOutput);
1619 newMapOutput = getAffineBinaryOpExpr(
1620 kind: AffineExprKind::CeilDiv, lhs: binaryExpr.getLHS(), rhs: binaryExpr.getRHS());
1621 break;
1622 default:
1623 newMapOutput = oldMapOutput;
1624 }
1625 return newMapOutput;
1626}
1627
1628/// Create new maps to calculate each dimension size of `newMemRefType`, and
1629/// create `newDynamicSizes` from them by using AffineApplyOp.
1630///
1631/// Steps for normalizing dynamic memrefs for a tiled layout map
1632/// Example:
1633/// #map0 = affine_map<(d0, d1) -> (d0, d1 floordiv 32, d1 mod 32)>
1634/// %0 = dim %arg0, %c1 :memref<4x?xf32>
1635/// %1 = alloc(%0) : memref<4x?xf32, #map0>
1636///
1637/// (Before this function)
1638/// 1. Check if `map`(#map0) is a tiled layout using `getTileSizePos()`. Only
1639/// single layout map is supported.
1640///
1641/// 2. Create normalized memrefType using `isNormalizedMemRefDynamicDim()`. It
1642/// is memref<4x?x?xf32> in the above example.
1643///
1644/// (In this function)
1645/// 3. Create new maps to calculate each dimension of the normalized memrefType
1646/// using `createDimSizeExprForTiledLayout()`. In the tiled layout, the
1647/// dimension size can be calculated by replacing "floordiv <tile size>" with
1648/// "ceildiv <tile size>" and "mod <tile size>" with "<tile size>".
1649/// - New map in the above example
1650/// #map0 = affine_map<(d0, d1) -> (d0)>
1651/// #map1 = affine_map<(d0, d1) -> (d1 ceildiv 32)>
1652/// #map2 = affine_map<(d0, d1) -> (32)>
1653///
1654/// 4. Create AffineApplyOp to apply the new maps. The output of AffineApplyOp
1655/// is used in dynamicSizes of new AllocOp.
1656/// %0 = dim %arg0, %c1 : memref<4x?xf32>
1657/// %c4 = arith.constant 4 : index
1658/// %1 = affine.apply #map1(%c4, %0)
1659/// %2 = affine.apply #map2(%c4, %0)
1660template <typename AllocLikeOp>
1661static void createNewDynamicSizes(MemRefType oldMemRefType,
1662 MemRefType newMemRefType, AffineMap map,
1663 AllocLikeOp allocOp, OpBuilder b,
1664 SmallVectorImpl<Value> &newDynamicSizes) {
1665 // Create new input for AffineApplyOp.
1666 SmallVector<Value, 4> inAffineApply;
1667 ArrayRef<int64_t> oldMemRefShape = oldMemRefType.getShape();
1668 unsigned dynIdx = 0;
1669 for (unsigned d = 0; d < oldMemRefType.getRank(); ++d) {
1670 if (oldMemRefShape[d] < 0) {
1671 // Use dynamicSizes of allocOp for dynamic dimension.
1672 inAffineApply.emplace_back(allocOp.getDynamicSizes()[dynIdx]);
1673 dynIdx++;
1674 } else {
1675 // Create ConstantOp for static dimension.
1676 auto constantAttr = b.getIntegerAttr(type: b.getIndexType(), value: oldMemRefShape[d]);
1677 inAffineApply.emplace_back(
1678 arith::ConstantOp::create(b, allocOp.getLoc(), constantAttr));
1679 }
1680 }
1681
1682 // Create new map to calculate each dimension size of new memref for each
1683 // original map output. Only for dynamic dimesion of `newMemRefType`.
1684 unsigned newDimIdx = 0;
1685 ArrayRef<int64_t> newMemRefShape = newMemRefType.getShape();
1686 SmallVector<std::tuple<AffineExpr, unsigned, unsigned>> tileSizePos;
1687 (void)getTileSizePos(map, tileSizePos);
1688 for (AffineExpr expr : map.getResults()) {
1689 if (newMemRefShape[newDimIdx] < 0) {
1690 // Create new maps to calculate each dimension size of new memref.
1691 enum TileExprPattern pat = TileExprPattern::TileNone;
1692 for (auto pos : tileSizePos) {
1693 if (newDimIdx == std::get<1>(t&: pos))
1694 pat = TileExprPattern::TileFloorDiv;
1695 else if (newDimIdx == std::get<2>(t&: pos))
1696 pat = TileExprPattern::TileMod;
1697 }
1698 AffineExpr newMapOutput = createDimSizeExprForTiledLayout(oldMapOutput: expr, pat);
1699 AffineMap newMap =
1700 AffineMap::get(dimCount: map.getNumInputs(), symbolCount: map.getNumSymbols(), result: newMapOutput);
1701 Value affineApp =
1702 AffineApplyOp::create(b, allocOp.getLoc(), newMap, inAffineApply);
1703 newDynamicSizes.emplace_back(Args&: affineApp);
1704 }
1705 newDimIdx++;
1706 }
1707}
1708
1709template <typename AllocLikeOp>
1710LogicalResult mlir::affine::normalizeMemRef(AllocLikeOp allocOp) {
1711 MemRefType memrefType = allocOp.getType();
1712 OpBuilder b(allocOp);
1713
1714 // Fetch a new memref type after normalizing the old memref to have an
1715 // identity map layout.
1716 MemRefType newMemRefType = normalizeMemRefType(memrefType);
1717 if (newMemRefType == memrefType)
1718 // Either memrefType already had an identity map or the map couldn't be
1719 // transformed to an identity map.
1720 return failure();
1721
1722 Value oldMemRef = allocOp.getResult();
1723
1724 SmallVector<Value, 4> symbolOperands(allocOp.getSymbolOperands());
1725 AffineMap layoutMap = memrefType.getLayout().getAffineMap();
1726 AllocLikeOp newAlloc;
1727 // Check if `layoutMap` is a tiled layout. Only single layout map is
1728 // supported for normalizing dynamic memrefs.
1729 SmallVector<std::tuple<AffineExpr, unsigned, unsigned>> tileSizePos;
1730 (void)getTileSizePos(map: layoutMap, tileSizePos);
1731 if (newMemRefType.getNumDynamicDims() > 0 && !tileSizePos.empty()) {
1732 auto oldMemRefType = cast<MemRefType>(Val: oldMemRef.getType());
1733 SmallVector<Value, 4> newDynamicSizes;
1734 createNewDynamicSizes(oldMemRefType, newMemRefType, layoutMap, allocOp, b,
1735 newDynamicSizes);
1736 // Add the new dynamic sizes in new AllocOp.
1737 newAlloc = AllocLikeOp::create(b, allocOp.getLoc(), newMemRefType,
1738 newDynamicSizes, allocOp.getAlignmentAttr());
1739 } else {
1740 newAlloc = AllocLikeOp::create(b, allocOp.getLoc(), newMemRefType,
1741 allocOp.getAlignmentAttr());
1742 }
1743 // Replace all uses of the old memref.
1744 if (failed(replaceAllMemRefUsesWith(oldMemRef, /*newMemRef=*/newAlloc,
1745 /*extraIndices=*/{},
1746 /*indexRemap=*/layoutMap,
1747 /*extraOperands=*/{},
1748 /*symbolOperands=*/symbolOperands,
1749 /*userFilterFn=*/nullptr,
1750 /*allowNonDereferencingOps=*/true))) {
1751 // If it failed (due to escapes for example), bail out.
1752 newAlloc.erase();
1753 return failure();
1754 }
1755 // Replace any uses of the original alloc op and erase it. All remaining uses
1756 // have to be dealloc's; RAMUW above would've failed otherwise.
1757 assert(llvm::all_of(oldMemRef.getUsers(), [&](Operation *op) {
1758 return hasSingleEffect<MemoryEffects::Free>(op, oldMemRef);
1759 }));
1760 oldMemRef.replaceAllUsesWith(newValue: newAlloc);
1761 allocOp.erase();
1762 return success();
1763}
1764
1765LogicalResult
1766mlir::affine::normalizeMemRef(memref::ReinterpretCastOp reinterpretCastOp) {
1767 MemRefType memrefType = reinterpretCastOp.getType();
1768 AffineMap oldLayoutMap = memrefType.getLayout().getAffineMap();
1769 Value oldMemRef = reinterpretCastOp.getResult();
1770
1771 // If `oldLayoutMap` is identity, `memrefType` is already normalized.
1772 if (oldLayoutMap.isIdentity())
1773 return success();
1774
1775 // Fetch a new memref type after normalizing the old memref to have an
1776 // identity map layout.
1777 MemRefType newMemRefType = normalizeMemRefType(memrefType);
1778 if (newMemRefType == memrefType)
1779 // `oldLayoutMap` couldn't be transformed to an identity map.
1780 return failure();
1781
1782 uint64_t newRank = newMemRefType.getRank();
1783 SmallVector<Value> mapOperands(oldLayoutMap.getNumDims() +
1784 oldLayoutMap.getNumSymbols());
1785 SmallVector<Value> oldStrides = reinterpretCastOp.getStrides();
1786 Location loc = reinterpretCastOp.getLoc();
1787 // As `newMemRefType` is normalized, it is unit strided.
1788 SmallVector<int64_t> newStaticStrides(newRank, 1);
1789 SmallVector<int64_t> newStaticOffsets(newRank, 0);
1790 ArrayRef<int64_t> oldShape = memrefType.getShape();
1791 ValueRange oldSizes = reinterpretCastOp.getSizes();
1792 unsigned idx = 0;
1793 OpBuilder b(reinterpretCastOp);
1794 // Collect the map operands which will be used to compute the new normalized
1795 // memref shape.
1796 for (unsigned i = 0, e = memrefType.getRank(); i < e; i++) {
1797 if (memrefType.isDynamicDim(idx: i))
1798 mapOperands[i] =
1799 arith::SubIOp::create(builder&: b, location: loc, result: oldSizes[0].getType(), lhs: oldSizes[idx++],
1800 rhs: arith::ConstantIndexOp::create(builder&: b, location: loc, value: 1));
1801 else
1802 mapOperands[i] = arith::ConstantIndexOp::create(builder&: b, location: loc, value: oldShape[i] - 1);
1803 }
1804 for (unsigned i = 0, e = oldStrides.size(); i < e; i++)
1805 mapOperands[memrefType.getRank() + i] = oldStrides[i];
1806 SmallVector<Value> newSizes;
1807 ArrayRef<int64_t> newShape = newMemRefType.getShape();
1808 // Compute size along all the dimensions of the new normalized memref.
1809 for (unsigned i = 0; i < newRank; i++) {
1810 if (!newMemRefType.isDynamicDim(idx: i))
1811 continue;
1812 newSizes.push_back(Elt: AffineApplyOp::create(
1813 builder&: b, location: loc,
1814 map: AffineMap::get(dimCount: oldLayoutMap.getNumDims(), symbolCount: oldLayoutMap.getNumSymbols(),
1815 result: oldLayoutMap.getResult(idx: i)),
1816 mapOperands));
1817 }
1818 for (auto &newSize : newSizes) {
1819 newSize = arith::AddIOp::create(builder&: b, location: loc, result: newSize.getType(), lhs: newSize,
1820 rhs: arith::ConstantIndexOp::create(builder&: b, location: loc, value: 1));
1821 }
1822 // Create the new reinterpret_cast op.
1823 auto newReinterpretCast = memref::ReinterpretCastOp::create(
1824 builder&: b, location: loc, result: newMemRefType, source: reinterpretCastOp.getSource(),
1825 /*offsets=*/ValueRange(), sizes: newSizes,
1826 /*strides=*/ValueRange(),
1827 /*static_offsets=*/newStaticOffsets,
1828 /*static_sizes=*/newShape,
1829 /*static_strides=*/newStaticStrides);
1830
1831 // Replace all uses of the old memref.
1832 if (failed(Result: replaceAllMemRefUsesWith(oldMemRef,
1833 /*newMemRef=*/newReinterpretCast,
1834 /*extraIndices=*/{},
1835 /*indexRemap=*/oldLayoutMap,
1836 /*extraOperands=*/{},
1837 /*symbolOperands=*/oldStrides,
1838 /*userFilterFn=*/nullptr,
1839 /*allowNonDereferencingOps=*/true))) {
1840 // If it failed (due to escapes for example), bail out.
1841 newReinterpretCast.erase();
1842 return failure();
1843 }
1844
1845 oldMemRef.replaceAllUsesWith(newValue: newReinterpretCast);
1846 reinterpretCastOp.erase();
1847 return success();
1848}
1849
1850template LogicalResult
1851mlir::affine::normalizeMemRef<memref::AllocaOp>(memref::AllocaOp op);
1852template LogicalResult
1853mlir::affine::normalizeMemRef<memref::AllocOp>(memref::AllocOp op);
1854
1855MemRefType mlir::affine::normalizeMemRefType(MemRefType memrefType) {
1856 unsigned rank = memrefType.getRank();
1857 if (rank == 0)
1858 return memrefType;
1859
1860 if (memrefType.getLayout().isIdentity()) {
1861 // Either no maps is associated with this memref or this memref has
1862 // a trivial (identity) map.
1863 return memrefType;
1864 }
1865 AffineMap layoutMap = memrefType.getLayout().getAffineMap();
1866 unsigned numSymbolicOperands = layoutMap.getNumSymbols();
1867
1868 // We don't do any checks for one-to-one'ness; we assume that it is
1869 // one-to-one.
1870
1871 // Normalize only static memrefs and dynamic memrefs with a tiled-layout map
1872 // for now.
1873 // TODO: Normalize the other types of dynamic memrefs.
1874 SmallVector<std::tuple<AffineExpr, unsigned, unsigned>> tileSizePos;
1875 (void)getTileSizePos(map: layoutMap, tileSizePos);
1876 if (memrefType.getNumDynamicDims() > 0 && tileSizePos.empty())
1877 return memrefType;
1878
1879 // We have a single map that is not an identity map. Create a new memref
1880 // with the right shape and an identity layout map.
1881 ArrayRef<int64_t> shape = memrefType.getShape();
1882 // FlatAffineValueConstraint may later on use symbolicOperands.
1883 FlatAffineValueConstraints fac(rank, numSymbolicOperands);
1884 SmallVector<unsigned, 4> memrefTypeDynDims;
1885 for (unsigned d = 0; d < rank; ++d) {
1886 // Use constraint system only in static dimensions.
1887 if (shape[d] > 0) {
1888 fac.addBound(type: BoundType::LB, pos: d, value: 0);
1889 fac.addBound(type: BoundType::UB, pos: d, value: shape[d] - 1);
1890 } else {
1891 memrefTypeDynDims.emplace_back(Args&: d);
1892 }
1893 }
1894 // We compose this map with the original index (logical) space to derive
1895 // the upper bounds for the new index space.
1896 unsigned newRank = layoutMap.getNumResults();
1897 if (failed(Result: fac.composeMatchingMap(other: layoutMap)))
1898 return memrefType;
1899 // TODO: Handle semi-affine maps.
1900 // Project out the old data dimensions.
1901 fac.projectOut(pos: newRank, num: fac.getNumVars() - newRank - fac.getNumLocalVars());
1902 SmallVector<int64_t, 4> newShape(newRank);
1903 MLIRContext *context = memrefType.getContext();
1904 for (unsigned d = 0; d < newRank; ++d) {
1905 // Check if this dimension is dynamic.
1906 if (isNormalizedMemRefDynamicDim(dim: d, layoutMap, inMemrefTypeDynDims&: memrefTypeDynDims)) {
1907 newShape[d] = ShapedType::kDynamic;
1908 continue;
1909 }
1910 // The lower bound for the shape is always zero.
1911 std::optional<int64_t> ubConst = fac.getConstantBound64(type: BoundType::UB, pos: d);
1912 // For a static memref and an affine map with no symbols, this is
1913 // always bounded. However, when we have symbols, we may not be able to
1914 // obtain a constant upper bound. Also, mapping to a negative space is
1915 // invalid for normalization.
1916 if (!ubConst.has_value() || *ubConst < 0) {
1917 LLVM_DEBUG(llvm::dbgs()
1918 << "can't normalize map due to unknown/invalid upper bound");
1919 return memrefType;
1920 }
1921 // If dimension of new memrefType is dynamic, the value is -1.
1922 newShape[d] = *ubConst + 1;
1923 }
1924
1925 // Create the new memref type after trivializing the old layout map.
1926 auto newMemRefType =
1927 MemRefType::Builder(memrefType)
1928 .setShape(newShape)
1929 .setLayout(AffineMapAttr::get(
1930 value: AffineMap::getMultiDimIdentityMap(numDims: newRank, context)));
1931 return newMemRefType;
1932}
1933
1934DivModValue mlir::affine::getDivMod(OpBuilder &b, Location loc, Value lhs,
1935 Value rhs) {
1936 DivModValue result;
1937 AffineExpr d0, d1;
1938 bindDims(ctx: b.getContext(), exprs&: d0, exprs&: d1);
1939 result.quotient =
1940 affine::makeComposedAffineApply(b, loc, e: d0.floorDiv(other: d1), operands: {lhs, rhs});
1941 result.remainder =
1942 affine::makeComposedAffineApply(b, loc, e: d0 % d1, operands: {lhs, rhs});
1943 return result;
1944}
1945
1946/// Create an affine map that computes `lhs` * `rhs`, composing in any other
1947/// affine maps.
1948static FailureOr<OpFoldResult> composedAffineMultiply(OpBuilder &b,
1949 Location loc,
1950 OpFoldResult lhs,
1951 OpFoldResult rhs) {
1952 AffineExpr s0, s1;
1953 bindSymbols(ctx: b.getContext(), exprs&: s0, exprs&: s1);
1954 return makeComposedFoldedAffineApply(b, loc, expr: s0 * s1, operands: {lhs, rhs});
1955}
1956
1957FailureOr<SmallVector<Value>>
1958mlir::affine::delinearizeIndex(OpBuilder &b, Location loc, Value linearIndex,
1959 ArrayRef<Value> basis, bool hasOuterBound) {
1960 if (hasOuterBound)
1961 basis = basis.drop_front();
1962
1963 // Note: the divisors are backwards due to the scan.
1964 SmallVector<Value> divisors;
1965 OpFoldResult basisProd = b.getIndexAttr(value: 1);
1966 for (OpFoldResult basisElem : llvm::reverse(C&: basis)) {
1967 FailureOr<OpFoldResult> nextProd =
1968 composedAffineMultiply(b, loc, lhs: basisElem, rhs: basisProd);
1969 if (failed(Result: nextProd))
1970 return failure();
1971 basisProd = *nextProd;
1972 divisors.push_back(Elt: getValueOrCreateConstantIndexOp(b, loc, ofr: basisProd));
1973 }
1974
1975 SmallVector<Value> results;
1976 results.reserve(N: divisors.size() + 1);
1977 Value residual = linearIndex;
1978 for (Value divisor : llvm::reverse(C&: divisors)) {
1979 DivModValue divMod = getDivMod(b, loc, lhs: residual, rhs: divisor);
1980 results.push_back(Elt: divMod.quotient);
1981 residual = divMod.remainder;
1982 }
1983 results.push_back(Elt: residual);
1984 return results;
1985}
1986
1987FailureOr<SmallVector<Value>>
1988mlir::affine::delinearizeIndex(OpBuilder &b, Location loc, Value linearIndex,
1989 ArrayRef<OpFoldResult> basis,
1990 bool hasOuterBound) {
1991 if (hasOuterBound)
1992 basis = basis.drop_front();
1993
1994 // Note: the divisors are backwards due to the scan.
1995 SmallVector<Value> divisors;
1996 OpFoldResult basisProd = b.getIndexAttr(value: 1);
1997 for (OpFoldResult basisElem : llvm::reverse(C&: basis)) {
1998 FailureOr<OpFoldResult> nextProd =
1999 composedAffineMultiply(b, loc, lhs: basisElem, rhs: basisProd);
2000 if (failed(Result: nextProd))
2001 return failure();
2002 basisProd = *nextProd;
2003 divisors.push_back(Elt: getValueOrCreateConstantIndexOp(b, loc, ofr: basisProd));
2004 }
2005
2006 SmallVector<Value> results;
2007 results.reserve(N: divisors.size() + 1);
2008 Value residual = linearIndex;
2009 for (Value divisor : llvm::reverse(C&: divisors)) {
2010 DivModValue divMod = getDivMod(b, loc, lhs: residual, rhs: divisor);
2011 results.push_back(Elt: divMod.quotient);
2012 residual = divMod.remainder;
2013 }
2014 results.push_back(Elt: residual);
2015 return results;
2016}
2017
2018OpFoldResult mlir::affine::linearizeIndex(ArrayRef<OpFoldResult> multiIndex,
2019 ArrayRef<OpFoldResult> basis,
2020 ImplicitLocOpBuilder &builder) {
2021 return linearizeIndex(builder, loc: builder.getLoc(), multiIndex, basis);
2022}
2023
2024OpFoldResult mlir::affine::linearizeIndex(OpBuilder &builder, Location loc,
2025 ArrayRef<OpFoldResult> multiIndex,
2026 ArrayRef<OpFoldResult> basis) {
2027 assert(multiIndex.size() == basis.size() ||
2028 multiIndex.size() == basis.size() + 1);
2029 SmallVector<AffineExpr> basisAffine;
2030
2031 // Add a fake initial size in order to make the later index linearization
2032 // computations line up if an outer bound is not provided.
2033 if (multiIndex.size() == basis.size() + 1)
2034 basisAffine.push_back(Elt: getAffineConstantExpr(constant: 1, context: builder.getContext()));
2035
2036 for (size_t i = 0; i < basis.size(); ++i) {
2037 basisAffine.push_back(Elt: getAffineSymbolExpr(position: i, context: builder.getContext()));
2038 }
2039
2040 SmallVector<AffineExpr> stridesAffine = computeStrides(sizes: basisAffine);
2041 SmallVector<OpFoldResult> strides;
2042 strides.reserve(N: stridesAffine.size());
2043 llvm::transform(Range&: stridesAffine, d_first: std::back_inserter(x&: strides),
2044 F: [&builder, &basis, loc](AffineExpr strideExpr) {
2045 return affine::makeComposedFoldedAffineApply(
2046 b&: builder, loc, expr: strideExpr, operands: basis);
2047 });
2048
2049 auto &&[linearIndexExpr, multiIndexAndStrides] = computeLinearIndex(
2050 sourceOffset: OpFoldResult(builder.getIndexAttr(value: 0)), strides, indices: multiIndex);
2051 return affine::makeComposedFoldedAffineApply(b&: builder, loc, expr: linearIndexExpr,
2052 operands: multiIndexAndStrides);
2053}
2054