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