1//===- AffineOps.cpp - MLIR Affine Operations -----------------------------===//
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#include "mlir/Dialect/Affine/IR/AffineOps.h"
10#include "mlir/Dialect/Affine/IR/AffineValueMap.h"
11#include "mlir/Dialect/MemRef/IR/MemRef.h"
12#include "mlir/Dialect/UB/IR/UBOps.h"
13#include "mlir/Dialect/Utils/StaticValueUtils.h"
14#include "mlir/IR/AffineExpr.h"
15#include "mlir/IR/AffineExprVisitor.h"
16#include "mlir/IR/IRMapping.h"
17#include "mlir/IR/IntegerSet.h"
18#include "mlir/IR/Matchers.h"
19#include "mlir/IR/OpDefinition.h"
20#include "mlir/IR/PatternMatch.h"
21#include "mlir/IR/Value.h"
22#include "mlir/Interfaces/ShapedOpInterfaces.h"
23#include "mlir/Interfaces/ValueBoundsOpInterface.h"
24#include "mlir/Transforms/InliningUtils.h"
25#include "llvm/ADT/STLExtras.h"
26#include "llvm/ADT/SmallBitVector.h"
27#include "llvm/ADT/SmallVectorExtras.h"
28#include "llvm/ADT/TypeSwitch.h"
29#include "llvm/Support/DebugLog.h"
30#include "llvm/Support/LogicalResult.h"
31#include "llvm/Support/MathExtras.h"
32#include <numeric>
33#include <optional>
34
35using namespace mlir;
36using namespace mlir::affine;
37
38using llvm::divideCeilSigned;
39using llvm::divideFloorSigned;
40using llvm::mod;
41
42#define DEBUG_TYPE "affine-ops"
43
44#include "mlir/Dialect/Affine/IR/AffineOpsDialect.cpp.inc"
45
46/// A utility function to check if a value is defined at the top level of
47/// `region` or is an argument of `region`. A value of index type defined at the
48/// top level of a `AffineScope` region is always a valid symbol for all
49/// uses in that region.
50bool mlir::affine::isTopLevelValue(Value value, Region *region) {
51 if (auto arg = dyn_cast<BlockArgument>(Val&: value))
52 return arg.getParentRegion() == region;
53 return value.getDefiningOp()->getParentRegion() == region;
54}
55
56/// Checks if `value` known to be a legal affine dimension or symbol in `src`
57/// region remains legal if the operation that uses it is inlined into `dest`
58/// with the given value mapping. `legalityCheck` is either `isValidDim` or
59/// `isValidSymbol`, depending on the value being required to remain a valid
60/// dimension or symbol.
61static bool
62remainsLegalAfterInline(Value value, Region *src, Region *dest,
63 const IRMapping &mapping,
64 function_ref<bool(Value, Region *)> legalityCheck) {
65 // If the value is a valid dimension for any other reason than being
66 // a top-level value, it will remain valid: constants get inlined
67 // with the function, transitive affine applies also get inlined and
68 // will be checked themselves, etc.
69 if (!isTopLevelValue(value, region: src))
70 return true;
71
72 // If it's a top-level value because it's a block operand, i.e. a
73 // function argument, check whether the value replacing it after
74 // inlining is a valid dimension in the new region.
75 if (llvm::isa<BlockArgument>(Val: value))
76 return legalityCheck(mapping.lookup(from: value), dest);
77
78 // If it's a top-level value because it's defined in the region,
79 // it can only be inlined if the defining op is a constant or a
80 // `dim`, which can appear anywhere and be valid, since the defining
81 // op won't be top-level anymore after inlining.
82 Attribute operandCst;
83 bool isDimLikeOp = isa<ShapedDimOpInterface>(Val: value.getDefiningOp());
84 return matchPattern(op: value.getDefiningOp(), pattern: m_Constant(bind_value: &operandCst)) ||
85 isDimLikeOp;
86}
87
88/// Checks if all values known to be legal affine dimensions or symbols in `src`
89/// remain so if their respective users are inlined into `dest`.
90static bool
91remainsLegalAfterInline(ValueRange values, Region *src, Region *dest,
92 const IRMapping &mapping,
93 function_ref<bool(Value, Region *)> legalityCheck) {
94 return llvm::all_of(Range&: values, P: [&](Value v) {
95 return remainsLegalAfterInline(value: v, src, dest, mapping, legalityCheck);
96 });
97}
98
99/// Checks if an affine read or write operation remains legal after inlining
100/// from `src` to `dest`.
101template <typename OpTy>
102static bool remainsLegalAfterInline(OpTy op, Region *src, Region *dest,
103 const IRMapping &mapping) {
104 static_assert(llvm::is_one_of<OpTy, AffineReadOpInterface,
105 AffineWriteOpInterface>::value,
106 "only ops with affine read/write interface are supported");
107
108 AffineMap map = op.getAffineMap();
109 ValueRange dimOperands = op.getMapOperands().take_front(map.getNumDims());
110 ValueRange symbolOperands =
111 op.getMapOperands().take_back(map.getNumSymbols());
112 if (!remainsLegalAfterInline(
113 values: dimOperands, src, dest, mapping,
114 legalityCheck: static_cast<bool (*)(Value, Region *)>(isValidDim)))
115 return false;
116 if (!remainsLegalAfterInline(
117 values: symbolOperands, src, dest, mapping,
118 legalityCheck: static_cast<bool (*)(Value, Region *)>(isValidSymbol)))
119 return false;
120 return true;
121}
122
123/// Checks if an affine apply operation remains legal after inlining from `src`
124/// to `dest`.
125// Use "unused attribute" marker to silence clang-tidy warning stemming from
126// the inability to see through "llvm::TypeSwitch".
127template <>
128[[maybe_unused]] bool remainsLegalAfterInline(AffineApplyOp op, Region *src,
129 Region *dest,
130 const IRMapping &mapping) {
131 // If it's a valid dimension, we need to check that it remains so.
132 if (isValidDim(value: op.getResult(), region: src))
133 return remainsLegalAfterInline(
134 values: op.getMapOperands(), src, dest, mapping,
135 legalityCheck: static_cast<bool (*)(Value, Region *)>(isValidDim));
136
137 // Otherwise it must be a valid symbol, check that it remains so.
138 return remainsLegalAfterInline(
139 values: op.getMapOperands(), src, dest, mapping,
140 legalityCheck: static_cast<bool (*)(Value, Region *)>(isValidSymbol));
141}
142
143//===----------------------------------------------------------------------===//
144// AffineDialect Interfaces
145//===----------------------------------------------------------------------===//
146
147namespace {
148/// This class defines the interface for handling inlining with affine
149/// operations.
150struct AffineInlinerInterface : public DialectInlinerInterface {
151 using DialectInlinerInterface::DialectInlinerInterface;
152
153 //===--------------------------------------------------------------------===//
154 // Analysis Hooks
155 //===--------------------------------------------------------------------===//
156
157 /// Returns true if the given region 'src' can be inlined into the region
158 /// 'dest' that is attached to an operation registered to the current dialect.
159 /// 'wouldBeCloned' is set if the region is cloned into its new location
160 /// rather than moved, indicating there may be other users.
161 bool isLegalToInline(Region *dest, Region *src, bool wouldBeCloned,
162 IRMapping &valueMapping) const final {
163 // We can inline into affine loops and conditionals if this doesn't break
164 // affine value categorization rules.
165 Operation *destOp = dest->getParentOp();
166 if (!isa<AffineParallelOp, AffineForOp, AffineIfOp>(Val: destOp))
167 return false;
168
169 // Multi-block regions cannot be inlined into affine constructs, all of
170 // which require single-block regions.
171 if (!src->hasOneBlock())
172 return false;
173
174 // Side-effecting operations that the affine dialect cannot understand
175 // should not be inlined.
176 Block &srcBlock = src->front();
177 for (Operation &op : srcBlock) {
178 // Ops with no side effects are fine,
179 if (auto iface = dyn_cast<MemoryEffectOpInterface>(Val&: op)) {
180 if (iface.hasNoEffect())
181 continue;
182 }
183
184 // Assuming the inlined region is valid, we only need to check if the
185 // inlining would change it.
186 bool remainsValid =
187 llvm::TypeSwitch<Operation *, bool>(&op)
188 .Case<AffineApplyOp, AffineReadOpInterface,
189 AffineWriteOpInterface>(caseFn: [&](auto op) {
190 return remainsLegalAfterInline(op, src, dest, valueMapping);
191 })
192 .Default(defaultFn: [](Operation *) {
193 // Conservatively disallow inlining ops we cannot reason about.
194 return false;
195 });
196
197 if (!remainsValid)
198 return false;
199 }
200
201 return true;
202 }
203
204 /// Returns true if the given operation 'op', that is registered to this
205 /// dialect, can be inlined into the given region, false otherwise.
206 bool isLegalToInline(Operation *op, Region *region, bool wouldBeCloned,
207 IRMapping &valueMapping) const final {
208 // Always allow inlining affine operations into a region that is marked as
209 // affine scope, or into affine loops and conditionals. There are some edge
210 // cases when inlining *into* affine structures, but that is handled in the
211 // other 'isLegalToInline' hook above.
212 Operation *parentOp = region->getParentOp();
213 return parentOp->hasTrait<OpTrait::AffineScope>() ||
214 isa<AffineForOp, AffineParallelOp, AffineIfOp>(Val: parentOp);
215 }
216
217 /// Affine regions should be analyzed recursively.
218 bool shouldAnalyzeRecursively(Operation *op) const final { return true; }
219};
220} // namespace
221
222//===----------------------------------------------------------------------===//
223// AffineDialect
224//===----------------------------------------------------------------------===//
225
226void AffineDialect::initialize() {
227 addOperations<
228#define GET_OP_LIST
229#include "mlir/Dialect/Affine/IR/AffineOps.cpp.inc"
230 >();
231 addInterfaces<AffineInlinerInterface>();
232 declarePromisedInterfaces<ValueBoundsOpInterface, AffineApplyOp, AffineMaxOp,
233 AffineMinOp>();
234}
235
236/// Materialize a single constant operation from a given attribute value with
237/// the desired resultant type.
238Operation *AffineDialect::materializeConstant(OpBuilder &builder,
239 Attribute value, Type type,
240 Location loc) {
241 if (auto poison = dyn_cast<ub::PoisonAttr>(Val&: value))
242 return ub::PoisonOp::create(builder, location: loc, result: type, value: poison);
243 return arith::ConstantOp::materialize(builder, value, type, loc);
244}
245
246/// A utility function to check if a value is defined at the top level of an
247/// op with trait `AffineScope`. If the value is defined in an unlinked region,
248/// conservatively assume it is not top-level. A value of index type defined at
249/// the top level is always a valid symbol.
250bool mlir::affine::isTopLevelValue(Value value) {
251 if (auto arg = dyn_cast<BlockArgument>(Val&: value)) {
252 // The block owning the argument may be unlinked, e.g. when the surrounding
253 // region has not yet been attached to an Op, at which point the parent Op
254 // is null.
255 Operation *parentOp = arg.getOwner()->getParentOp();
256 return parentOp && parentOp->hasTrait<OpTrait::AffineScope>();
257 }
258 // The defining Op may live in an unlinked block so its parent Op may be null.
259 Operation *parentOp = value.getDefiningOp()->getParentOp();
260 return parentOp && parentOp->hasTrait<OpTrait::AffineScope>();
261}
262
263/// Returns the closest region enclosing `op` that is held by an operation with
264/// trait `AffineScope`; `nullptr` if there is no such region.
265Region *mlir::affine::getAffineScope(Operation *op) {
266 auto *curOp = op;
267 while (auto *parentOp = curOp->getParentOp()) {
268 if (parentOp->hasTrait<OpTrait::AffineScope>())
269 return curOp->getParentRegion();
270 curOp = parentOp;
271 }
272 return nullptr;
273}
274
275Region *mlir::affine::getAffineAnalysisScope(Operation *op) {
276 Operation *curOp = op;
277 while (auto *parentOp = curOp->getParentOp()) {
278 if (!isa<AffineForOp, AffineIfOp, AffineParallelOp>(Val: parentOp))
279 return curOp->getParentRegion();
280 curOp = parentOp;
281 }
282 return nullptr;
283}
284
285// A Value can be used as a dimension id iff it meets one of the following
286// conditions:
287// *) It is valid as a symbol.
288// *) It is an induction variable.
289// *) It is the result of affine apply operation with dimension id arguments.
290bool mlir::affine::isValidDim(Value value) {
291 // The value must be an index type.
292 if (!value.getType().isIndex())
293 return false;
294
295 if (auto *defOp = value.getDefiningOp())
296 return isValidDim(value, region: getAffineScope(op: defOp));
297
298 // This value has to be a block argument for an op that has the
299 // `AffineScope` trait or an induction var of an affine.for or
300 // affine.parallel.
301 if (isAffineInductionVar(val: value))
302 return true;
303 auto *parentOp = llvm::cast<BlockArgument>(Val&: value).getOwner()->getParentOp();
304 return parentOp && parentOp->hasTrait<OpTrait::AffineScope>();
305}
306
307// Value can be used as a dimension id iff it meets one of the following
308// conditions:
309// *) It is valid as a symbol.
310// *) It is an induction variable.
311// *) It is the result of an affine apply operation with dimension id operands.
312// *) It is the result of a more specialized index transformation (ex.
313// delinearize_index or linearize_index) with dimension id operands.
314bool mlir::affine::isValidDim(Value value, Region *region) {
315 // The value must be an index type.
316 if (!value.getType().isIndex())
317 return false;
318
319 // All valid symbols are okay.
320 if (isValidSymbol(value, region))
321 return true;
322
323 auto *op = value.getDefiningOp();
324 if (!op) {
325 // This value has to be an induction var for an affine.for or an
326 // affine.parallel.
327 return isAffineInductionVar(val: value);
328 }
329
330 // Affine apply operation is ok if all of its operands are ok.
331 if (auto applyOp = dyn_cast<AffineApplyOp>(Val: op))
332 return applyOp.isValidDim(region);
333 // delinearize_index and linearize_index are special forms of apply
334 // and so are valid dimensions if all their arguments are valid dimensions.
335 if (isa<AffineDelinearizeIndexOp, AffineLinearizeIndexOp>(Val: op))
336 return llvm::all_of(Range: op->getOperands(),
337 P: [&](Value arg) { return ::isValidDim(value: arg, region); });
338 // The dim op is okay if its operand memref/tensor is defined at the top
339 // level.
340 if (auto dimOp = dyn_cast<ShapedDimOpInterface>(Val: op))
341 return isTopLevelValue(value: dimOp.getShapedValue());
342 return false;
343}
344
345/// Returns true if the 'index' dimension of the `memref` defined by
346/// `memrefDefOp` is a statically shaped one or defined using a valid symbol
347/// for `region`.
348template <typename AnyMemRefDefOp>
349static bool isMemRefSizeValidSymbol(AnyMemRefDefOp memrefDefOp, unsigned index,
350 Region *region) {
351 MemRefType memRefType = memrefDefOp.getType();
352
353 // Dimension index is out of bounds.
354 if (index >= memRefType.getRank()) {
355 return false;
356 }
357
358 // Statically shaped.
359 if (!memRefType.isDynamicDim(idx: index))
360 return true;
361 // Get the position of the dimension among dynamic dimensions;
362 unsigned dynamicDimPos = memRefType.getDynamicDimIndex(index);
363 return isValidSymbol(*(memrefDefOp.getDynamicSizes().begin() + dynamicDimPos),
364 region);
365}
366
367/// Returns true if the result of the dim op is a valid symbol for `region`.
368static bool isDimOpValidSymbol(ShapedDimOpInterface dimOp, Region *region) {
369 // The dim op is okay if its source is defined at the top level.
370 if (isTopLevelValue(value: dimOp.getShapedValue()))
371 return true;
372
373 // Conservatively handle remaining BlockArguments as non-valid symbols.
374 // E.g. scf.for iterArgs.
375 if (llvm::isa<BlockArgument>(Val: dimOp.getShapedValue()))
376 return false;
377
378 // The dim op is also okay if its operand memref is a view/subview whose
379 // corresponding size is a valid symbol.
380 std::optional<int64_t> index = getConstantIntValue(ofr: dimOp.getDimension());
381
382 // Be conservative if we can't understand the dimension.
383 if (!index.has_value())
384 return false;
385
386 // Skip over all memref.cast ops (if any).
387 Operation *op = dimOp.getShapedValue().getDefiningOp();
388 while (auto castOp = dyn_cast<memref::CastOp>(Val: op)) {
389 // Bail on unranked memrefs.
390 if (isa<UnrankedMemRefType>(Val: castOp.getSource().getType()))
391 return false;
392 op = castOp.getSource().getDefiningOp();
393 if (!op)
394 return false;
395 }
396
397 int64_t i = index.value();
398 return TypeSwitch<Operation *, bool>(op)
399 .Case<memref::ViewOp, memref::SubViewOp, memref::AllocOp>(
400 caseFn: [&](auto op) { return isMemRefSizeValidSymbol(op, i, region); })
401 .Default(defaultFn: [](Operation *) { return false; });
402}
403
404// A value can be used as a symbol (at all its use sites) iff it meets one of
405// the following conditions:
406// *) It is a constant.
407// *) Its defining op or block arg appearance is immediately enclosed by an op
408// with `AffineScope` trait.
409// *) It is the result of an affine.apply operation with symbol operands.
410// *) It is a result of the dim op on a memref whose corresponding size is a
411// valid symbol.
412bool mlir::affine::isValidSymbol(Value value) {
413 if (!value)
414 return false;
415
416 // The value must be an index type.
417 if (!value.getType().isIndex())
418 return false;
419
420 // Check that the value is a top level value.
421 if (isTopLevelValue(value))
422 return true;
423
424 if (auto *defOp = value.getDefiningOp())
425 return isValidSymbol(value, region: getAffineScope(op: defOp));
426
427 return false;
428}
429
430/// A utility function to check if a value is defined at the top level of
431/// `region` or is an argument of `region` or is defined above the region.
432static bool isTopLevelValueOrAbove(Value value, Region *region) {
433 Region *parentRegion = value.getParentRegion();
434 do {
435 if (parentRegion == region)
436 return true;
437 Operation *regionOp = region->getParentOp();
438 if (regionOp->hasTrait<OpTrait::IsIsolatedFromAbove>())
439 break;
440 region = region->getParentOp()->getParentRegion();
441 } while (region);
442 return false;
443}
444
445/// A value can be used as a symbol for `region` iff it meets one of the
446/// following conditions:
447/// *) It is a constant.
448/// *) It is a result of a `Pure` operation whose operands are valid symbolic
449/// *) identifiers.
450/// *) It is a result of the dim op on a memref whose corresponding size is
451/// a valid symbol.
452/// *) It is defined at the top level of 'region' or is its argument.
453/// *) It dominates `region`'s parent op.
454/// If `region` is null, conservatively assume the symbol definition scope does
455/// not exist and only accept the values that would be symbols regardless of
456/// the surrounding region structure, i.e. the first three cases above.
457bool mlir::affine::isValidSymbol(Value value, Region *region) {
458 // The value must be an index type.
459 if (!value.getType().isIndex())
460 return false;
461
462 // A top-level value is a valid symbol.
463 if (region && isTopLevelValueOrAbove(value, region))
464 return true;
465
466 auto *defOp = value.getDefiningOp();
467 if (!defOp)
468 return false;
469
470 // Constant operation is ok.
471 Attribute operandCst;
472 if (matchPattern(op: defOp, pattern: m_Constant(bind_value: &operandCst)))
473 return true;
474
475 // `Pure` operation that whose operands are valid symbolic identifiers.
476 if (isPure(op: defOp) && llvm::all_of(Range: defOp->getOperands(), P: [&](Value operand) {
477 return affine::isValidSymbol(value: operand, region);
478 })) {
479 return true;
480 }
481
482 // Dim op results could be valid symbols at any level.
483 if (auto dimOp = dyn_cast<ShapedDimOpInterface>(Val: defOp))
484 return isDimOpValidSymbol(dimOp, region);
485
486 return false;
487}
488
489// Returns true if 'value' is a valid index to an affine operation (e.g.
490// affine.load, affine.store, affine.dma_start, affine.dma_wait) where
491// `region` provides the polyhedral symbol scope. Returns false otherwise.
492static bool isValidAffineIndexOperand(Value value, Region *region) {
493 return isValidDim(value, region) || isValidSymbol(value, region);
494}
495
496/// Prints dimension and symbol list.
497static void printDimAndSymbolList(Operation::operand_iterator begin,
498 Operation::operand_iterator end,
499 unsigned numDims, OpAsmPrinter &printer) {
500 OperandRange operands(begin, end);
501 printer << '(' << operands.take_front(n: numDims) << ')';
502 if (operands.size() > numDims)
503 printer << '[' << operands.drop_front(n: numDims) << ']';
504}
505
506/// Parses dimension and symbol list and returns true if parsing failed.
507ParseResult mlir::affine::parseDimAndSymbolList(
508 OpAsmParser &parser, SmallVectorImpl<Value> &operands, unsigned &numDims) {
509 SmallVector<OpAsmParser::UnresolvedOperand, 8> opInfos;
510 if (parser.parseOperandList(result&: opInfos, delimiter: OpAsmParser::Delimiter::Paren))
511 return failure();
512 // Store number of dimensions for validation by caller.
513 numDims = opInfos.size();
514
515 // Parse the optional symbol operands.
516 auto indexTy = parser.getBuilder().getIndexType();
517 return failure(IsFailure: parser.parseOperandList(
518 result&: opInfos, delimiter: OpAsmParser::Delimiter::OptionalSquare) ||
519 parser.resolveOperands(operands&: opInfos, type: indexTy, result&: operands));
520}
521
522/// Utility function to verify that a set of operands are valid dimension and
523/// symbol identifiers. The operands should be laid out such that the dimension
524/// operands are before the symbol operands. This function returns failure if
525/// there was an invalid operand. An operation is provided to emit any necessary
526/// errors.
527template <typename OpTy>
528static LogicalResult
529verifyDimAndSymbolIdentifiers(OpTy &op, Operation::operand_range operands,
530 unsigned numDims) {
531 unsigned opIt = 0;
532 for (auto operand : operands) {
533 if (opIt++ < numDims) {
534 if (!isValidDim(operand, getAffineScope(op)))
535 return op.emitOpError("operand cannot be used as a dimension id");
536 } else if (!isValidSymbol(operand, getAffineScope(op))) {
537 return op.emitOpError("operand cannot be used as a symbol");
538 }
539 }
540 return success();
541}
542
543//===----------------------------------------------------------------------===//
544// AffineApplyOp
545//===----------------------------------------------------------------------===//
546
547AffineValueMap AffineApplyOp::getAffineValueMap() {
548 return AffineValueMap(getAffineMap(), getOperands(), getResult());
549}
550
551ParseResult AffineApplyOp::parse(OpAsmParser &parser, OperationState &result) {
552 auto &builder = parser.getBuilder();
553 auto indexTy = builder.getIndexType();
554
555 AffineMapAttr mapAttr;
556 unsigned numDims;
557 if (parser.parseAttribute(result&: mapAttr, attrName: "map", attrs&: result.attributes) ||
558 parseDimAndSymbolList(parser, operands&: result.operands, numDims) ||
559 parser.parseOptionalAttrDict(result&: result.attributes))
560 return failure();
561 auto map = mapAttr.getValue();
562
563 if (map.getNumDims() != numDims ||
564 numDims + map.getNumSymbols() != result.operands.size()) {
565 return parser.emitError(loc: parser.getNameLoc(),
566 message: "dimension or symbol index mismatch");
567 }
568
569 result.types.append(NumInputs: map.getNumResults(), Elt: indexTy);
570 return success();
571}
572
573void AffineApplyOp::print(OpAsmPrinter &p) {
574 p << " " << getMapAttr();
575 printDimAndSymbolList(begin: operand_begin(), end: operand_end(),
576 numDims: getAffineMap().getNumDims(), printer&: p);
577 p.printOptionalAttrDict(attrs: (*this)->getDiscardableAttrDictionary().getValue());
578}
579
580LogicalResult AffineApplyOp::verify() {
581 // Check input and output dimensions match.
582 AffineMap affineMap = getMap();
583
584 // Verify that operand count matches affine map dimension and symbol count.
585 if (getNumOperands() != affineMap.getNumDims() + affineMap.getNumSymbols())
586 return emitOpError(
587 message: "operand count and affine map dimension and symbol count must match");
588
589 // Verify that the map only produces one result.
590 if (affineMap.getNumResults() != 1)
591 return emitOpError(message: "mapping must produce one value");
592
593 // Do not allow valid dims to be used in symbol positions. We do allow
594 // affine.apply to use operands for values that may neither qualify as affine
595 // dims or affine symbols due to usage outside of affine ops, analyses, etc.
596 Region *region = getAffineScope(op: *this);
597 for (Value operand : getMapOperands().drop_front(n: affineMap.getNumDims())) {
598 if (::isValidDim(value: operand, region) && !::isValidSymbol(value: operand, region))
599 return emitError(message: "dimensional operand cannot be used as a symbol");
600 }
601
602 return success();
603}
604
605// The result of the affine apply operation can be used as a dimension id if all
606// its operands are valid dimension ids.
607bool AffineApplyOp::isValidDim() {
608 return llvm::all_of(Range: getOperands(),
609 P: [](Value op) { return affine::isValidDim(value: op); });
610}
611
612// The result of the affine apply operation can be used as a dimension id if all
613// its operands are valid dimension ids with the parent operation of `region`
614// defining the polyhedral scope for symbols.
615bool AffineApplyOp::isValidDim(Region *region) {
616 return llvm::all_of(Range: getOperands(),
617 P: [&](Value op) { return ::isValidDim(value: op, region); });
618}
619
620// The result of the affine apply operation can be used as a symbol if all its
621// operands are symbols.
622bool AffineApplyOp::isValidSymbol() {
623 return llvm::all_of(Range: getOperands(),
624 P: [](Value op) { return affine::isValidSymbol(value: op); });
625}
626
627// The result of the affine apply operation can be used as a symbol in `region`
628// if all its operands are symbols in `region`.
629bool AffineApplyOp::isValidSymbol(Region *region) {
630 return llvm::all_of(Range: getOperands(), P: [&](Value operand) {
631 return affine::isValidSymbol(value: operand, region);
632 });
633}
634
635OpFoldResult AffineApplyOp::fold(FoldAdaptor adaptor) {
636 auto map = getAffineMap();
637
638 // Fold dims and symbols to existing values.
639 auto expr = map.getResult(idx: 0);
640 if (auto dim = dyn_cast<AffineDimExpr>(Val&: expr))
641 return getOperand(i: dim.getPosition());
642 if (auto sym = dyn_cast<AffineSymbolExpr>(Val&: expr))
643 return getOperand(i: map.getNumDims() + sym.getPosition());
644
645 // Otherwise, default to folding the map.
646 SmallVector<Attribute, 1> result;
647 bool hasPoison = false;
648 auto foldResult =
649 map.constantFold(operandConstants: adaptor.getMapOperands(), results&: result, hasPoison: &hasPoison);
650 if (hasPoison)
651 return ub::PoisonAttr::get(ctx: getContext());
652 if (failed(Result: foldResult))
653 return {};
654 return result[0];
655}
656
657/// Returns the largest known divisor of `e`. Exploits information from the
658/// values in `operands`.
659static int64_t getLargestKnownDivisor(AffineExpr e, ArrayRef<Value> operands) {
660 // This method isn't aware of `operands`.
661 int64_t div = e.getLargestKnownDivisor();
662
663 // We now make use of operands for the case `e` is a dim expression.
664 // TODO: More powerful simplification would have to modify
665 // getLargestKnownDivisor to take `operands` and exploit that information as
666 // well for dim/sym expressions, but in that case, getLargestKnownDivisor
667 // can't be part of the IR library but of the `Analysis` library. The IR
668 // library can only really depend on simple O(1) checks.
669 auto dimExpr = dyn_cast<AffineDimExpr>(Val&: e);
670 // If it's not a dim expr, `div` is the best we have.
671 if (!dimExpr)
672 return div;
673
674 // We simply exploit information from loop IVs.
675 // We don't need to use mlir::getLargestKnownDivisorOfValue since the other
676 // desired simplifications are expected to be part of other
677 // canonicalizations. Also, mlir::getLargestKnownDivisorOfValue is part of the
678 // LoopAnalysis library.
679 Value operand = operands[dimExpr.getPosition()];
680 int64_t operandDivisor = 1;
681 // TODO: With the right accessors, this can be extended to
682 // LoopLikeOpInterface.
683 if (AffineForOp forOp = getForInductionVarOwner(val: operand)) {
684 if (forOp.hasConstantLowerBound() && forOp.getConstantLowerBound() == 0) {
685 operandDivisor = forOp.getStepAsInt();
686 } else {
687 uint64_t lbLargestKnownDivisor =
688 forOp.getLowerBoundMap().getLargestKnownDivisorOfMapExprs();
689 operandDivisor = std::gcd(m: lbLargestKnownDivisor, n: forOp.getStepAsInt());
690 }
691 }
692 return operandDivisor;
693}
694
695/// Check if `e` is known to be: 0 <= `e` < `k`. Handles the simple cases of `e`
696/// being an affine dim expression or a constant.
697static bool isNonNegativeBoundedBy(AffineExpr e, ArrayRef<Value> operands,
698 int64_t k) {
699 if (auto constExpr = dyn_cast<AffineConstantExpr>(Val&: e)) {
700 int64_t constVal = constExpr.getValue();
701 return constVal >= 0 && constVal < k;
702 }
703 auto dimExpr = dyn_cast<AffineDimExpr>(Val&: e);
704 if (!dimExpr)
705 return false;
706 Value operand = operands[dimExpr.getPosition()];
707 // TODO: With the right accessors, this can be extended to
708 // LoopLikeOpInterface.
709 if (AffineForOp forOp = getForInductionVarOwner(val: operand)) {
710 if (forOp.hasConstantLowerBound() && forOp.getConstantLowerBound() >= 0 &&
711 forOp.hasConstantUpperBound() && forOp.getConstantUpperBound() <= k) {
712 return true;
713 }
714 }
715
716 // We don't consider other cases like `operand` being defined by a constant or
717 // an affine.apply op since such cases will already be handled by other
718 // patterns and propagation of loop IVs or constant would happen.
719 return false;
720}
721
722/// Check if expression `e` is of the form d*e_1 + e_2 where 0 <= e_2 < d.
723/// Set `div` to `d`, `quotientTimesDiv` to e_1 and `rem` to e_2 if the
724/// expression is in that form.
725static bool isQTimesDPlusR(AffineExpr e, ArrayRef<Value> operands, int64_t &div,
726 AffineExpr &quotientTimesDiv, AffineExpr &rem) {
727 auto bin = dyn_cast<AffineBinaryOpExpr>(Val&: e);
728 if (!bin || bin.getKind() != AffineExprKind::Add)
729 return false;
730
731 AffineExpr llhs = bin.getLHS();
732 AffineExpr rlhs = bin.getRHS();
733 div = getLargestKnownDivisor(e: llhs, operands);
734 if (isNonNegativeBoundedBy(e: rlhs, operands, k: div)) {
735 quotientTimesDiv = llhs;
736 rem = rlhs;
737 return true;
738 }
739 div = getLargestKnownDivisor(e: rlhs, operands);
740 if (isNonNegativeBoundedBy(e: llhs, operands, k: div)) {
741 quotientTimesDiv = rlhs;
742 rem = llhs;
743 return true;
744 }
745 return false;
746}
747
748/// Gets the constant lower bound on an `iv`.
749static std::optional<int64_t> getLowerBound(Value iv) {
750 AffineForOp forOp = getForInductionVarOwner(val: iv);
751 if (forOp && forOp.hasConstantLowerBound())
752 return forOp.getConstantLowerBound();
753 return std::nullopt;
754}
755
756/// Gets the constant upper bound on an affine.for `iv`.
757static std::optional<int64_t> getUpperBound(Value iv) {
758 AffineForOp forOp = getForInductionVarOwner(val: iv);
759 if (!forOp || !forOp.hasConstantUpperBound())
760 return std::nullopt;
761
762 // If its lower bound is also known, we can get a more precise bound
763 // whenever the step is not one.
764 if (forOp.hasConstantLowerBound()) {
765 return forOp.getConstantUpperBound() - 1 -
766 (forOp.getConstantUpperBound() - forOp.getConstantLowerBound() - 1) %
767 forOp.getStepAsInt();
768 }
769 return forOp.getConstantUpperBound() - 1;
770}
771
772/// Determine a constant upper bound for `expr` if one exists while exploiting
773/// values in `operands`. Note that the upper bound is an inclusive one. `expr`
774/// is guaranteed to be less than or equal to it.
775static std::optional<int64_t> getUpperBound(AffineExpr expr, unsigned numDims,
776 unsigned numSymbols,
777 ArrayRef<Value> operands) {
778 if (auto constExpr = dyn_cast<AffineConstantExpr>(Val&: expr))
779 return constExpr.getValue();
780
781 // Get the constant lower or upper bounds on the operands.
782 SmallVector<std::optional<int64_t>> constLowerBounds, constUpperBounds;
783 constLowerBounds.reserve(N: operands.size());
784 constUpperBounds.reserve(N: operands.size());
785 for (Value operand : operands) {
786 constLowerBounds.push_back(Elt: getLowerBound(iv: operand));
787 constUpperBounds.push_back(Elt: getUpperBound(iv: operand));
788 }
789
790 return getBoundForAffineExpr(expr, numDims, numSymbols, constLowerBounds,
791 constUpperBounds,
792 /*isUpper=*/true);
793}
794
795/// Determine a constant lower bound for `expr` if one exists while exploiting
796/// values in `operands`. Note that the upper bound is an inclusive one. `expr`
797/// is guaranteed to be less than or equal to it.
798static std::optional<int64_t> getLowerBound(AffineExpr expr, unsigned numDims,
799 unsigned numSymbols,
800 ArrayRef<Value> operands) {
801 if (auto constExpr = dyn_cast<AffineConstantExpr>(Val&: expr))
802 return constExpr.getValue();
803
804 // Get the constant lower or upper bounds on the operands.
805 SmallVector<std::optional<int64_t>> constLowerBounds, constUpperBounds;
806 constLowerBounds.reserve(N: operands.size());
807 constUpperBounds.reserve(N: operands.size());
808 for (Value operand : operands) {
809 constLowerBounds.push_back(Elt: getLowerBound(iv: operand));
810 constUpperBounds.push_back(Elt: getUpperBound(iv: operand));
811 }
812
813 return getBoundForAffineExpr(expr, numDims, numSymbols, constLowerBounds,
814 constUpperBounds,
815 /*isUpper=*/false);
816}
817
818/// Simplify `expr` while exploiting information from the values in `operands`.
819static void simplifyExprAndOperands(AffineExpr &expr, unsigned numDims,
820 unsigned numSymbols,
821 ArrayRef<Value> operands) {
822 // We do this only for certain floordiv/mod expressions.
823 auto binExpr = dyn_cast<AffineBinaryOpExpr>(Val&: expr);
824 if (!binExpr)
825 return;
826
827 // Simplify the child expressions first.
828 AffineExpr lhs = binExpr.getLHS();
829 AffineExpr rhs = binExpr.getRHS();
830 simplifyExprAndOperands(expr&: lhs, numDims, numSymbols, operands);
831 simplifyExprAndOperands(expr&: rhs, numDims, numSymbols, operands);
832 expr = getAffineBinaryOpExpr(kind: binExpr.getKind(), lhs, rhs);
833
834 binExpr = dyn_cast<AffineBinaryOpExpr>(Val&: expr);
835 if (!binExpr || (expr.getKind() != AffineExprKind::FloorDiv &&
836 expr.getKind() != AffineExprKind::CeilDiv &&
837 expr.getKind() != AffineExprKind::Mod)) {
838 return;
839 }
840
841 // The `lhs` and `rhs` may be different post construction of simplified expr.
842 lhs = binExpr.getLHS();
843 rhs = binExpr.getRHS();
844 auto rhsConst = dyn_cast<AffineConstantExpr>(Val&: rhs);
845 if (!rhsConst)
846 return;
847
848 int64_t rhsConstVal = rhsConst.getValue();
849 // Undefined exprsessions aren't touched; IR can still be valid with them.
850 if (rhsConstVal <= 0)
851 return;
852
853 // Exploit constant lower/upper bounds to simplify a floordiv or mod.
854 MLIRContext *context = expr.getContext();
855 std::optional<int64_t> lhsLbConst =
856 getLowerBound(expr: lhs, numDims, numSymbols, operands);
857 std::optional<int64_t> lhsUbConst =
858 getUpperBound(expr: lhs, numDims, numSymbols, operands);
859 if (lhsLbConst && lhsUbConst) {
860 int64_t lhsLbConstVal = *lhsLbConst;
861 int64_t lhsUbConstVal = *lhsUbConst;
862 // lhs floordiv c is a single value lhs is bounded in a range `c` that has
863 // the same quotient.
864 if (binExpr.getKind() == AffineExprKind::FloorDiv &&
865 divideFloorSigned(Numerator: lhsLbConstVal, Denominator: rhsConstVal) ==
866 divideFloorSigned(Numerator: lhsUbConstVal, Denominator: rhsConstVal)) {
867 expr = getAffineConstantExpr(
868 constant: divideFloorSigned(Numerator: lhsLbConstVal, Denominator: rhsConstVal), context);
869 return;
870 }
871 // lhs ceildiv c is a single value if the entire range has the same ceil
872 // quotient.
873 if (binExpr.getKind() == AffineExprKind::CeilDiv &&
874 divideCeilSigned(Numerator: lhsLbConstVal, Denominator: rhsConstVal) ==
875 divideCeilSigned(Numerator: lhsUbConstVal, Denominator: rhsConstVal)) {
876 expr = getAffineConstantExpr(constant: divideCeilSigned(Numerator: lhsLbConstVal, Denominator: rhsConstVal),
877 context);
878 return;
879 }
880 // lhs mod c is lhs if the entire range has quotient 0 w.r.t the rhs.
881 if (binExpr.getKind() == AffineExprKind::Mod && lhsLbConstVal >= 0 &&
882 lhsLbConstVal < rhsConstVal && lhsUbConstVal < rhsConstVal) {
883 expr = lhs;
884 return;
885 }
886 }
887
888 // Simplify expressions of the form e = (e_1 + e_2) floordiv c or (e_1 + e_2)
889 // mod c, where e_1 is a multiple of `k` and 0 <= e_2 < k. In such cases, if
890 // `c` % `k` == 0, (e_1 + e_2) floordiv c can be simplified to e_1 floordiv c.
891 // And when k % c == 0, (e_1 + e_2) mod c can be simplified to e_2 mod c.
892 AffineExpr quotientTimesDiv, rem;
893 int64_t divisor;
894 if (isQTimesDPlusR(e: lhs, operands, div&: divisor, quotientTimesDiv, rem)) {
895 if (rhsConstVal % divisor == 0 &&
896 binExpr.getKind() == AffineExprKind::FloorDiv) {
897 expr = quotientTimesDiv.floorDiv(other: rhsConst);
898 } else if (divisor % rhsConstVal == 0 &&
899 binExpr.getKind() == AffineExprKind::Mod) {
900 expr = rem % rhsConst;
901 }
902 return;
903 }
904
905 // Handle the simple case when the LHS expression can be either upper
906 // bounded or is a known multiple of RHS constant.
907 // lhs floordiv c -> 0 if 0 <= lhs < c,
908 // lhs mod c -> 0 if lhs % c = 0.
909 if ((isNonNegativeBoundedBy(e: lhs, operands, k: rhsConstVal) &&
910 binExpr.getKind() == AffineExprKind::FloorDiv) ||
911 (getLargestKnownDivisor(e: lhs, operands) % rhsConstVal == 0 &&
912 binExpr.getKind() == AffineExprKind::Mod)) {
913 expr = getAffineConstantExpr(constant: 0, context: expr.getContext());
914 }
915}
916
917/// Simplify the expressions in `map` while making use of lower or upper bounds
918/// of its operands. If `isMax` is true, the map is to be treated as a max of
919/// its result expressions, and min otherwise. Eg: min (d0, d1) -> (8, 4 * d0 +
920/// d1) can be simplified to (8) if the operands are respectively lower bounded
921/// by 2 and 0 (the second expression can't be lower than 8).
922static void simplifyMinOrMaxExprWithOperands(AffineMap &map,
923 ArrayRef<Value> operands,
924 bool isMax) {
925 // Can't simplify.
926 if (operands.empty())
927 return;
928
929 // Get the upper or lower bound on an affine.for op IV using its range.
930 // Get the constant lower or upper bounds on the operands.
931 SmallVector<std::optional<int64_t>> constLowerBounds, constUpperBounds;
932 constLowerBounds.reserve(N: operands.size());
933 constUpperBounds.reserve(N: operands.size());
934 for (Value operand : operands) {
935 constLowerBounds.push_back(Elt: getLowerBound(iv: operand));
936 constUpperBounds.push_back(Elt: getUpperBound(iv: operand));
937 }
938
939 // We will compute the lower and upper bounds on each of the expressions
940 // Then, we will check (depending on max or min) as to whether a specific
941 // bound is redundant by checking if its highest (in case of max) and its
942 // lowest (in the case of min) value is already lower than (or higher than)
943 // the lower bound (or upper bound in the case of min) of another bound.
944 SmallVector<std::optional<int64_t>, 4> lowerBounds, upperBounds;
945 lowerBounds.reserve(N: map.getNumResults());
946 upperBounds.reserve(N: map.getNumResults());
947 for (AffineExpr e : map.getResults()) {
948 if (auto constExpr = dyn_cast<AffineConstantExpr>(Val&: e)) {
949 lowerBounds.push_back(Elt: constExpr.getValue());
950 upperBounds.push_back(Elt: constExpr.getValue());
951 } else {
952 lowerBounds.push_back(
953 Elt: getBoundForAffineExpr(expr: e, numDims: map.getNumDims(), numSymbols: map.getNumSymbols(),
954 constLowerBounds, constUpperBounds,
955 /*isUpper=*/false));
956 upperBounds.push_back(
957 Elt: getBoundForAffineExpr(expr: e, numDims: map.getNumDims(), numSymbols: map.getNumSymbols(),
958 constLowerBounds, constUpperBounds,
959 /*isUpper=*/true));
960 }
961 }
962
963 // Collect expressions that are not redundant.
964 SmallVector<AffineExpr, 4> irredundantExprs;
965 for (auto exprEn : llvm::enumerate(First: map.getResults())) {
966 AffineExpr e = exprEn.value();
967 unsigned i = exprEn.index();
968 // Some expressions can be turned into constants.
969 if (lowerBounds[i] && upperBounds[i] && *lowerBounds[i] == *upperBounds[i])
970 e = getAffineConstantExpr(constant: *lowerBounds[i], context: e.getContext());
971
972 // Check if the expression is redundant.
973 if (isMax) {
974 if (!upperBounds[i]) {
975 irredundantExprs.push_back(Elt: e);
976 continue;
977 }
978 // If there exists another expression such that its lower bound is greater
979 // than this expression's upper bound, it's redundant.
980 if (!llvm::any_of(Range: llvm::enumerate(First&: lowerBounds), P: [&](const auto &en) {
981 auto otherLowerBound = en.value();
982 unsigned pos = en.index();
983 if (pos == i || !otherLowerBound)
984 return false;
985 if (*otherLowerBound > *upperBounds[i])
986 return true;
987 if (*otherLowerBound < *upperBounds[i])
988 return false;
989 // Equality case. When both expressions are considered redundant, we
990 // don't want to get both of them. We keep the one that appears
991 // first.
992 if (upperBounds[pos] && lowerBounds[i] &&
993 lowerBounds[i] == upperBounds[i] &&
994 otherLowerBound == *upperBounds[pos] && i < pos)
995 return false;
996 return true;
997 }))
998 irredundantExprs.push_back(Elt: e);
999 } else {
1000 if (!lowerBounds[i]) {
1001 irredundantExprs.push_back(Elt: e);
1002 continue;
1003 }
1004 // Likewise for the `min` case. Use the complement of the condition above.
1005 if (!llvm::any_of(Range: llvm::enumerate(First&: upperBounds), P: [&](const auto &en) {
1006 auto otherUpperBound = en.value();
1007 unsigned pos = en.index();
1008 if (pos == i || !otherUpperBound)
1009 return false;
1010 if (*otherUpperBound < *lowerBounds[i])
1011 return true;
1012 if (*otherUpperBound > *lowerBounds[i])
1013 return false;
1014 if (lowerBounds[pos] && upperBounds[i] &&
1015 lowerBounds[i] == upperBounds[i] &&
1016 otherUpperBound == lowerBounds[pos] && i < pos)
1017 return false;
1018 return true;
1019 }))
1020 irredundantExprs.push_back(Elt: e);
1021 }
1022 }
1023
1024 // Create the map without the redundant expressions.
1025 map = AffineMap::get(dimCount: map.getNumDims(), symbolCount: map.getNumSymbols(), results: irredundantExprs,
1026 context: map.getContext());
1027}
1028
1029/// Simplify the map while exploiting information on the values in `operands`.
1030// Use "unused attribute" marker to silence warning stemming from the inability
1031// to see through the template expansion.
1032[[maybe_unused]] static void simplifyMapWithOperands(AffineMap &map,
1033 ArrayRef<Value> operands) {
1034 assert(map.getNumInputs() == operands.size() && "invalid operands for map");
1035 SmallVector<AffineExpr> newResults;
1036 newResults.reserve(N: map.getNumResults());
1037 for (AffineExpr expr : map.getResults()) {
1038 simplifyExprAndOperands(expr, numDims: map.getNumDims(), numSymbols: map.getNumSymbols(),
1039 operands);
1040 newResults.push_back(Elt: expr);
1041 }
1042 map = AffineMap::get(dimCount: map.getNumDims(), symbolCount: map.getNumSymbols(), results: newResults,
1043 context: map.getContext());
1044}
1045
1046/// Assuming `dimOrSym` is a quantity in the apply op map `map` and defined by
1047/// `minOp = affine_min(x_1, ..., x_n)`. This function checks that:
1048/// `0 < affine_min(x_1, ..., x_n)` and proceeds with replacing the patterns:
1049/// ```
1050/// dimOrSym.ceildiv(x_k)
1051/// (dimOrSym + x_k - 1).floordiv(x_k)
1052/// ```
1053/// by `1` for all `k` in `1, ..., n`. This is possible because `x / x_k <= 1`.
1054///
1055///
1056/// Warning: ValueBoundsConstraintSet::computeConstantBound is needed to check
1057/// `minOp` is positive.
1058static LogicalResult replaceAffineMinBoundingBoxExpression(AffineMinOp minOp,
1059 AffineExpr dimOrSym,
1060 AffineMap *map,
1061 ValueRange dims,
1062 ValueRange syms) {
1063 LDBG() << "replaceAffineMinBoundingBoxExpression: `" << minOp << "`";
1064 AffineMap affineMinMap = minOp.getAffineMap();
1065
1066 // Check the value is positive.
1067 for (unsigned i = 0, e = affineMinMap.getNumResults(); i < e; ++i) {
1068 // Compare each expression in the minimum against 0.
1069 if (!ValueBoundsConstraintSet::compare(
1070 lhs: getAsIndexOpFoldResult(ctx: minOp.getContext(), val: 0),
1071 cmp: ValueBoundsConstraintSet::ComparisonOperator::LT,
1072 rhs: ValueBoundsConstraintSet::Variable(affineMinMap.getSliceMap(start: i, length: 1),
1073 minOp.getOperands())))
1074 return failure();
1075 }
1076
1077 /// Convert affine symbols and dimensions in minOp to symbols or dimensions in
1078 /// the apply op affine map.
1079 DenseMap<AffineExpr, AffineExpr> dimSymConversionTable;
1080 SmallVector<unsigned> unmappedDims, unmappedSyms;
1081 for (auto [i, dim] : llvm::enumerate(First: minOp.getDimOperands())) {
1082 auto it = llvm::find(Range&: dims, Val: dim);
1083 if (it == dims.end()) {
1084 unmappedDims.push_back(Elt: i);
1085 continue;
1086 }
1087 dimSymConversionTable[getAffineDimExpr(position: i, context: minOp.getContext())] =
1088 getAffineDimExpr(position: it.getIndex(), context: minOp.getContext());
1089 }
1090 for (auto [i, sym] : llvm::enumerate(First: minOp.getSymbolOperands())) {
1091 auto it = llvm::find(Range&: syms, Val: sym);
1092 if (it == syms.end()) {
1093 unmappedSyms.push_back(Elt: i);
1094 continue;
1095 }
1096 dimSymConversionTable[getAffineSymbolExpr(position: i, context: minOp.getContext())] =
1097 getAffineSymbolExpr(position: it.getIndex(), context: minOp.getContext());
1098 }
1099
1100 // Create the replacement map.
1101 DenseMap<AffineExpr, AffineExpr> repl;
1102 AffineExpr c1 = getAffineConstantExpr(constant: 1, context: minOp.getContext());
1103 for (AffineExpr expr : affineMinMap.getResults()) {
1104 // If we cannot express the result in terms of the apply map symbols and
1105 // sims then continue.
1106 if (llvm::any_of(Range&: unmappedDims,
1107 P: [&](unsigned i) { return expr.isFunctionOfDim(position: i); }) ||
1108 llvm::any_of(Range&: unmappedSyms,
1109 P: [&](unsigned i) { return expr.isFunctionOfSymbol(position: i); }))
1110 continue;
1111
1112 AffineExpr convertedExpr = expr.replace(map: dimSymConversionTable);
1113
1114 // dimOrSym.ceilDiv(expr) -> 1
1115 repl[dimOrSym.ceilDiv(other: convertedExpr)] = c1;
1116 // (dimOrSym + expr - 1).floorDiv(expr) -> 1
1117 repl[(dimOrSym + convertedExpr - 1).floorDiv(other: convertedExpr)] = c1;
1118 }
1119 AffineMap initialMap = *map;
1120 *map = initialMap.replace(map: repl, numResultDims: initialMap.getNumDims(),
1121 numResultSyms: initialMap.getNumSymbols());
1122 return success(IsSuccess: *map != initialMap);
1123}
1124
1125/// Recursively traverse `e`. If `e` or one of its sub-expressions has the form
1126/// e1 + e2 + ... + eK, where the e_i are a super(multi)set of `exprsToRemove`,
1127/// place a map between e and `newVal` + sum({e1, e2, .. eK} - exprsToRemove)
1128/// into `replacementsMap`. If no entries were added to `replacementsMap`,
1129/// nothing was found.
1130static void shortenAddChainsContainingAll(
1131 AffineExpr e, const llvm::SmallDenseSet<AffineExpr, 4> &exprsToRemove,
1132 AffineExpr newVal, DenseMap<AffineExpr, AffineExpr> &replacementsMap) {
1133 auto binOp = dyn_cast<AffineBinaryOpExpr>(Val&: e);
1134 if (!binOp)
1135 return;
1136 AffineExpr lhs = binOp.getLHS();
1137 AffineExpr rhs = binOp.getRHS();
1138 if (binOp.getKind() != AffineExprKind::Add) {
1139 shortenAddChainsContainingAll(e: lhs, exprsToRemove, newVal, replacementsMap);
1140 shortenAddChainsContainingAll(e: rhs, exprsToRemove, newVal, replacementsMap);
1141 return;
1142 }
1143 SmallVector<AffineExpr> toPreserve;
1144 llvm::SmallDenseSet<AffineExpr, 4> ourTracker(exprsToRemove);
1145 AffineExpr thisTerm = rhs;
1146 AffineExpr nextTerm = lhs;
1147
1148 while (thisTerm) {
1149 if (!ourTracker.erase(V: thisTerm)) {
1150 toPreserve.push_back(Elt: thisTerm);
1151 shortenAddChainsContainingAll(e: thisTerm, exprsToRemove, newVal,
1152 replacementsMap);
1153 }
1154 auto nextBinOp = dyn_cast_if_present<AffineBinaryOpExpr>(Val&: nextTerm);
1155 if (!nextBinOp || nextBinOp.getKind() != AffineExprKind::Add) {
1156 thisTerm = nextTerm;
1157 nextTerm = AffineExpr();
1158 } else {
1159 thisTerm = nextBinOp.getRHS();
1160 nextTerm = nextBinOp.getLHS();
1161 }
1162 }
1163 if (!ourTracker.empty())
1164 return;
1165 // We reverse the terms to be preserved here in order to preserve
1166 // associativity between them.
1167 AffineExpr newExpr = newVal;
1168 for (AffineExpr preserved : llvm::reverse(C&: toPreserve))
1169 newExpr = newExpr + preserved;
1170 replacementsMap.insert(KV: {e, newExpr});
1171}
1172
1173/// If this map contains of the expression `x_1 + x_1 * C_1 + ... x_n * C_N +
1174/// ...` (not necessarily in order) where the set of the `x_i` is the set of
1175/// outputs of an `affine.delinearize_index` whos inverse is that expression,
1176/// replace that expression with the input of that delinearize_index op.
1177///
1178/// `unitDimInput` is the input that was detected as the potential start to this
1179/// replacement chain - if it isn't the rightmost result of the delinearization,
1180/// this method fails. (This is intended to ensure we don't have redundant scans
1181/// over the same expression).
1182///
1183/// While this currently only handles delinearizations with a constant basis,
1184/// that isn't a fundamental limitation.
1185///
1186/// This is a utility function for `replaceDimOrSym` below.
1187static LogicalResult replaceAffineDelinearizeIndexInverseExpression(
1188 AffineDelinearizeIndexOp delinOp, Value resultToReplace, AffineMap *map,
1189 SmallVectorImpl<Value> &dims, SmallVectorImpl<Value> &syms) {
1190 if (!delinOp.getDynamicBasis().empty())
1191 return failure();
1192 if (resultToReplace != delinOp.getMultiIndex().back())
1193 return failure();
1194
1195 MLIRContext *ctx = delinOp.getContext();
1196 SmallVector<AffineExpr> resToExpr(delinOp.getNumResults(), AffineExpr());
1197 for (auto [pos, dim] : llvm::enumerate(First&: dims)) {
1198 auto asResult = dyn_cast_if_present<OpResult>(Val&: dim);
1199 if (!asResult)
1200 continue;
1201 if (asResult.getOwner() == delinOp.getOperation())
1202 resToExpr[asResult.getResultNumber()] = getAffineDimExpr(position: pos, context: ctx);
1203 }
1204 for (auto [pos, sym] : llvm::enumerate(First&: syms)) {
1205 auto asResult = dyn_cast_if_present<OpResult>(Val&: sym);
1206 if (!asResult)
1207 continue;
1208 if (asResult.getOwner() == delinOp.getOperation())
1209 resToExpr[asResult.getResultNumber()] = getAffineSymbolExpr(position: pos, context: ctx);
1210 }
1211 if (llvm::is_contained(Range&: resToExpr, Element: AffineExpr()))
1212 return failure();
1213
1214 bool isDimReplacement = llvm::all_of(Range&: resToExpr, P: llvm::IsaPred<AffineDimExpr>);
1215 int64_t stride = 1;
1216 llvm::SmallDenseSet<AffineExpr, 4> expectedExprs;
1217 // This isn't zip_equal since sometimes the delinearize basis is missing a
1218 // size for the first result.
1219 for (auto [binding, size] : llvm::zip(
1220 t: llvm::reverse(C&: resToExpr), u: llvm::reverse(C: delinOp.getStaticBasis()))) {
1221 expectedExprs.insert(V: binding * getAffineConstantExpr(constant: stride, context: ctx));
1222 stride *= size;
1223 }
1224 if (resToExpr.size() != delinOp.getStaticBasis().size())
1225 expectedExprs.insert(V: resToExpr[0] * stride);
1226
1227 DenseMap<AffineExpr, AffineExpr> replacements;
1228 AffineExpr delinInExpr = isDimReplacement
1229 ? getAffineDimExpr(position: dims.size(), context: ctx)
1230 : getAffineSymbolExpr(position: syms.size(), context: ctx);
1231
1232 for (AffineExpr e : map->getResults())
1233 shortenAddChainsContainingAll(e, exprsToRemove: expectedExprs, newVal: delinInExpr, replacementsMap&: replacements);
1234 if (replacements.empty())
1235 return failure();
1236
1237 AffineMap origMap = *map;
1238 if (isDimReplacement)
1239 dims.push_back(Elt: delinOp.getLinearIndex());
1240 else
1241 syms.push_back(Elt: delinOp.getLinearIndex());
1242 *map = origMap.replace(map: replacements, numResultDims: dims.size(), numResultSyms: syms.size());
1243
1244 // Blank out dead dimensions and symbols
1245 for (AffineExpr e : resToExpr) {
1246 if (auto d = dyn_cast<AffineDimExpr>(Val&: e)) {
1247 unsigned pos = d.getPosition();
1248 if (!map->isFunctionOfDim(position: pos))
1249 dims[pos] = nullptr;
1250 }
1251 if (auto s = dyn_cast<AffineSymbolExpr>(Val&: e)) {
1252 unsigned pos = s.getPosition();
1253 if (!map->isFunctionOfSymbol(position: pos))
1254 syms[pos] = nullptr;
1255 }
1256 }
1257 return success();
1258}
1259
1260/// Replace all occurrences of AffineExpr at position `pos` in `map` by the
1261/// defining AffineApplyOp expression and operands.
1262/// When `dimOrSymbolPosition < dims.size()`, AffineDimExpr@[pos] is replaced.
1263/// When `dimOrSymbolPosition >= dims.size()`,
1264/// AffineSymbolExpr@[pos - dims.size()] is replaced.
1265/// Mutate `map`,`dims` and `syms` in place as follows:
1266/// 1. `dims` and `syms` are only appended to.
1267/// 2. `map` dim and symbols are gradually shifted to higher positions.
1268/// 3. Old `dim` and `sym` entries are replaced by nullptr
1269/// This avoids the need for any bookkeeping.
1270/// If `replaceAffineMin` is set to true, additionally triggers more expensive
1271/// replacements involving affine_min operations.
1272static LogicalResult replaceDimOrSym(AffineMap *map,
1273 unsigned dimOrSymbolPosition,
1274 SmallVectorImpl<Value> &dims,
1275 SmallVectorImpl<Value> &syms,
1276 bool replaceAffineMin) {
1277 MLIRContext *ctx = map->getContext();
1278 bool isDimReplacement = (dimOrSymbolPosition < dims.size());
1279 unsigned pos = isDimReplacement ? dimOrSymbolPosition
1280 : dimOrSymbolPosition - dims.size();
1281 Value &v = isDimReplacement ? dims[pos] : syms[pos];
1282 if (!v)
1283 return failure();
1284
1285 if (auto minOp = v.getDefiningOp<AffineMinOp>(); minOp && replaceAffineMin) {
1286 AffineExpr dimOrSym = isDimReplacement ? getAffineDimExpr(position: pos, context: ctx)
1287 : getAffineSymbolExpr(position: pos, context: ctx);
1288 return replaceAffineMinBoundingBoxExpression(minOp, dimOrSym, map, dims,
1289 syms);
1290 }
1291
1292 if (auto delinOp = v.getDefiningOp<affine::AffineDelinearizeIndexOp>()) {
1293 return replaceAffineDelinearizeIndexInverseExpression(delinOp, resultToReplace: v, map, dims,
1294 syms);
1295 }
1296
1297 auto affineApply = v.getDefiningOp<AffineApplyOp>();
1298 if (!affineApply)
1299 return failure();
1300
1301 // At this point we will perform a replacement of `v`, set the entry in `dim`
1302 // or `sym` to nullptr immediately.
1303 v = nullptr;
1304
1305 // Compute the map, dims and symbols coming from the AffineApplyOp.
1306 AffineMap composeMap = affineApply.getAffineMap();
1307 assert(composeMap.getNumResults() == 1 && "affine.apply with >1 results");
1308 SmallVector<Value> composeOperands(affineApply.getMapOperands().begin(),
1309 affineApply.getMapOperands().end());
1310 // Canonicalize the map to promote dims to symbols when possible. This is to
1311 // avoid generating invalid maps.
1312 canonicalizeMapAndOperands(map: &composeMap, operands: &composeOperands);
1313 AffineExpr replacementExpr =
1314 composeMap.shiftDims(shift: dims.size()).shiftSymbols(shift: syms.size()).getResult(idx: 0);
1315 ValueRange composeDims =
1316 ArrayRef<Value>(composeOperands).take_front(N: composeMap.getNumDims());
1317 ValueRange composeSyms =
1318 ArrayRef<Value>(composeOperands).take_back(N: composeMap.getNumSymbols());
1319 AffineExpr toReplace = isDimReplacement ? getAffineDimExpr(position: pos, context: ctx)
1320 : getAffineSymbolExpr(position: pos, context: ctx);
1321
1322 // Append the dims and symbols where relevant and perform the replacement.
1323 dims.append(in_start: composeDims.begin(), in_end: composeDims.end());
1324 syms.append(in_start: composeSyms.begin(), in_end: composeSyms.end());
1325 *map = map->replace(expr: toReplace, replacement: replacementExpr, numResultDims: dims.size(), numResultSyms: syms.size());
1326
1327 return success();
1328}
1329
1330/// Iterate over `operands` and fold away all those produced by an AffineApplyOp
1331/// iteratively. Perform canonicalization of map and operands as well as
1332/// AffineMap simplification. `map` and `operands` are mutated in place.
1333static void composeAffineMapAndOperands(AffineMap *map,
1334 SmallVectorImpl<Value> *operands,
1335 bool composeAffineMin = false) {
1336 if (map->getNumResults() == 0) {
1337 canonicalizeMapAndOperands(map, operands);
1338 *map = simplifyAffineMap(map: *map);
1339 return;
1340 }
1341
1342 MLIRContext *ctx = map->getContext();
1343 SmallVector<Value, 4> dims(operands->begin(),
1344 operands->begin() + map->getNumDims());
1345 SmallVector<Value, 4> syms(operands->begin() + map->getNumDims(),
1346 operands->end());
1347
1348 // Iterate over dims and symbols coming from AffineApplyOp and replace until
1349 // exhaustion. This iteratively mutates `map`, `dims` and `syms`. Both `dims`
1350 // and `syms` can only increase by construction.
1351 // The implementation uses a `while` loop to support the case of symbols
1352 // that may be constructed from dims ;this may be overkill.
1353 while (true) {
1354 bool changed = false;
1355 for (unsigned pos = 0; pos != dims.size() + syms.size(); ++pos)
1356 if ((changed |=
1357 succeeded(Result: replaceDimOrSym(map, dimOrSymbolPosition: pos, dims, syms, replaceAffineMin: composeAffineMin))))
1358 break;
1359 if (!changed)
1360 break;
1361 }
1362
1363 // Clear operands so we can fill them anew.
1364 operands->clear();
1365
1366 // At this point we may have introduced null operands, prune them out before
1367 // canonicalizing map and operands.
1368 unsigned nDims = 0, nSyms = 0;
1369 SmallVector<AffineExpr, 4> dimReplacements, symReplacements;
1370 dimReplacements.reserve(N: dims.size());
1371 symReplacements.reserve(N: syms.size());
1372 for (auto *container : {&dims, &syms}) {
1373 bool isDim = (container == &dims);
1374 auto &repls = isDim ? dimReplacements : symReplacements;
1375 for (const auto &en : llvm::enumerate(First&: *container)) {
1376 Value v = en.value();
1377 if (!v) {
1378 assert(isDim ? !map->isFunctionOfDim(en.index())
1379 : !map->isFunctionOfSymbol(en.index()) &&
1380 "map is function of unexpected expr@pos");
1381 repls.push_back(Elt: getAffineConstantExpr(constant: 0, context: ctx));
1382 continue;
1383 }
1384 repls.push_back(Elt: isDim ? getAffineDimExpr(position: nDims++, context: ctx)
1385 : getAffineSymbolExpr(position: nSyms++, context: ctx));
1386 operands->push_back(Elt: v);
1387 }
1388 }
1389 *map = map->replaceDimsAndSymbols(dimReplacements, symReplacements, numResultDims: nDims,
1390 numResultSyms: nSyms);
1391
1392 // Canonicalize and simplify before returning.
1393 canonicalizeMapAndOperands(map, operands);
1394 *map = simplifyAffineMap(map: *map);
1395}
1396
1397void mlir::affine::fullyComposeAffineMapAndOperands(
1398 AffineMap *map, SmallVectorImpl<Value> *operands, bool composeAffineMin) {
1399 while (llvm::any_of(Range&: *operands, P: [](Value v) {
1400 return isa_and_nonnull<AffineApplyOp>(Val: v.getDefiningOp());
1401 })) {
1402 composeAffineMapAndOperands(map, operands, composeAffineMin);
1403 }
1404 // Additional trailing step for AffineMinOps in case no chains of AffineApply.
1405 if (composeAffineMin && llvm::any_of(Range&: *operands, P: [](Value v) {
1406 return isa_and_nonnull<AffineMinOp>(Val: v.getDefiningOp());
1407 })) {
1408 composeAffineMapAndOperands(map, operands, composeAffineMin);
1409 }
1410}
1411
1412AffineApplyOp
1413mlir::affine::makeComposedAffineApply(OpBuilder &b, Location loc, AffineMap map,
1414 ArrayRef<OpFoldResult> operands,
1415 bool composeAffineMin) {
1416 SmallVector<Value> valueOperands;
1417 map = foldAttributesIntoMap(b, map, operands, remainingValues&: valueOperands);
1418 composeAffineMapAndOperands(map: &map, operands: &valueOperands, composeAffineMin);
1419 assert(map);
1420 return AffineApplyOp::create(builder&: b, location: loc, map, mapOperands: valueOperands);
1421}
1422
1423AffineApplyOp
1424mlir::affine::makeComposedAffineApply(OpBuilder &b, Location loc, AffineExpr e,
1425 ArrayRef<OpFoldResult> operands,
1426 bool composeAffineMin) {
1427 return makeComposedAffineApply(
1428 b, loc,
1429 map: AffineMap::inferFromExprList(exprsList: ArrayRef<AffineExpr>{e}, context: b.getContext())
1430 .front(),
1431 operands, composeAffineMin);
1432}
1433
1434/// Composes the given affine map with the given list of operands, pulling in
1435/// the maps from any affine.apply operations that supply the operands.
1436static void composeMultiResultAffineMap(AffineMap &map,
1437 SmallVectorImpl<Value> &operands,
1438 bool composeAffineMin = false) {
1439 // Compose and canonicalize each expression in the map individually because
1440 // composition only applies to single-result maps, collecting potentially
1441 // duplicate operands in a single list with shifted dimensions and symbols.
1442 SmallVector<Value> dims, symbols;
1443 SmallVector<AffineExpr> exprs;
1444 for (unsigned i : llvm::seq<unsigned>(Begin: 0, End: map.getNumResults())) {
1445 SmallVector<Value> submapOperands(operands.begin(), operands.end());
1446 AffineMap submap = map.getSubMap(resultPos: {i});
1447 fullyComposeAffineMapAndOperands(map: &submap, operands: &submapOperands,
1448 composeAffineMin);
1449 canonicalizeMapAndOperands(map: &submap, operands: &submapOperands);
1450 unsigned numNewDims = submap.getNumDims();
1451 submap = submap.shiftDims(shift: dims.size()).shiftSymbols(shift: symbols.size());
1452 llvm::append_range(C&: dims,
1453 R: ArrayRef<Value>(submapOperands).take_front(N: numNewDims));
1454 llvm::append_range(C&: symbols,
1455 R: ArrayRef<Value>(submapOperands).drop_front(N: numNewDims));
1456 exprs.push_back(Elt: submap.getResult(idx: 0));
1457 }
1458
1459 // Canonicalize the map created from composed expressions to deduplicate the
1460 // dimension and symbol operands.
1461 operands = llvm::to_vector(Range: llvm::concat<Value>(Ranges&: dims, Ranges&: symbols));
1462 map = AffineMap::get(dimCount: dims.size(), symbolCount: symbols.size(), results: exprs, context: map.getContext());
1463 canonicalizeMapAndOperands(map: &map, operands: &operands);
1464}
1465
1466OpFoldResult mlir::affine::makeComposedFoldedAffineApply(
1467 OpBuilder &b, Location loc, AffineMap map, ArrayRef<OpFoldResult> operands,
1468 bool composeAffineMin) {
1469 assert(map.getNumResults() == 1 && "building affine.apply with !=1 result");
1470
1471 // Create new builder without a listener, so that no notification is
1472 // triggered if the op is folded.
1473 // TODO: OpBuilder::createOrFold should return OpFoldResults, then this
1474 // workaround is no longer needed.
1475 OpBuilder newBuilder(b.getContext());
1476 newBuilder.setInsertionPoint(block: b.getInsertionBlock(), insertPoint: b.getInsertionPoint());
1477
1478 // Create op.
1479 AffineApplyOp applyOp =
1480 makeComposedAffineApply(b&: newBuilder, loc, map, operands, composeAffineMin);
1481
1482 // Get constant operands.
1483 SmallVector<Attribute> constOperands(applyOp->getNumOperands());
1484 for (unsigned i = 0, e = constOperands.size(); i != e; ++i)
1485 matchPattern(value: applyOp->getOperand(idx: i), pattern: m_Constant(bind_value: &constOperands[i]));
1486
1487 // Try to fold the operation.
1488 SmallVector<OpFoldResult> foldResults;
1489 if (failed(Result: applyOp->fold(operands: constOperands, results&: foldResults)) ||
1490 foldResults.empty()) {
1491 if (OpBuilder::Listener *listener = b.getListener())
1492 listener->notifyOperationInserted(op: applyOp, /*previous=*/{});
1493 return applyOp.getResult();
1494 }
1495
1496 applyOp->erase();
1497 return llvm::getSingleElement(C&: foldResults);
1498}
1499
1500OpFoldResult mlir::affine::makeComposedFoldedAffineApply(
1501 OpBuilder &b, Location loc, AffineExpr expr,
1502 ArrayRef<OpFoldResult> operands, bool composeAffineMin) {
1503 return makeComposedFoldedAffineApply(
1504 b, loc,
1505 map: AffineMap::inferFromExprList(exprsList: ArrayRef<AffineExpr>{expr}, context: b.getContext())
1506 .front(),
1507 operands, composeAffineMin);
1508}
1509
1510SmallVector<OpFoldResult>
1511mlir::affine::makeComposedFoldedMultiResultAffineApply(
1512 OpBuilder &b, Location loc, AffineMap map, ArrayRef<OpFoldResult> operands,
1513 bool composeAffineMin) {
1514 return llvm::map_to_vector(
1515 C: llvm::seq<unsigned>(Begin: 0, End: map.getNumResults()), F: [&](unsigned i) {
1516 return makeComposedFoldedAffineApply(b, loc, map: map.getSubMap(resultPos: {i}),
1517 operands, composeAffineMin);
1518 });
1519}
1520
1521template <typename OpTy>
1522static OpTy makeComposedMinMax(OpBuilder &b, Location loc, AffineMap map,
1523 ArrayRef<OpFoldResult> operands) {
1524 SmallVector<Value> valueOperands;
1525 map = foldAttributesIntoMap(b, map, operands, remainingValues&: valueOperands);
1526 composeMultiResultAffineMap(map, operands&: valueOperands);
1527 return OpTy::create(b, loc, b.getIndexType(), map, valueOperands);
1528}
1529
1530AffineMinOp
1531mlir::affine::makeComposedAffineMin(OpBuilder &b, Location loc, AffineMap map,
1532 ArrayRef<OpFoldResult> operands) {
1533 return makeComposedMinMax<AffineMinOp>(b, loc, map, operands);
1534}
1535
1536template <typename OpTy>
1537static OpFoldResult makeComposedFoldedMinMax(OpBuilder &b, Location loc,
1538 AffineMap map,
1539 ArrayRef<OpFoldResult> operands) {
1540 // Create new builder without a listener, so that no notification is
1541 // triggered if the op is folded.
1542 // TODO: OpBuilder::createOrFold should return OpFoldResults, then this
1543 // workaround is no longer needed.
1544 OpBuilder newBuilder(b.getContext());
1545 newBuilder.setInsertionPoint(block: b.getInsertionBlock(), insertPoint: b.getInsertionPoint());
1546
1547 // Create op.
1548 auto minMaxOp = makeComposedMinMax<OpTy>(newBuilder, loc, map, operands);
1549
1550 // Get constant operands.
1551 SmallVector<Attribute> constOperands(minMaxOp->getNumOperands());
1552 for (unsigned i = 0, e = constOperands.size(); i != e; ++i)
1553 matchPattern(minMaxOp->getOperand(i), m_Constant(bind_value: &constOperands[i]));
1554
1555 // Try to fold the operation.
1556 SmallVector<OpFoldResult> foldResults;
1557 if (failed(minMaxOp->fold(constOperands, foldResults)) ||
1558 foldResults.empty()) {
1559 if (OpBuilder::Listener *listener = b.getListener())
1560 listener->notifyOperationInserted(op: minMaxOp, /*previous=*/{});
1561 return minMaxOp.getResult();
1562 }
1563
1564 minMaxOp->erase();
1565 return llvm::getSingleElement(C&: foldResults);
1566}
1567
1568OpFoldResult
1569mlir::affine::makeComposedFoldedAffineMin(OpBuilder &b, Location loc,
1570 AffineMap map,
1571 ArrayRef<OpFoldResult> operands) {
1572 return makeComposedFoldedMinMax<AffineMinOp>(b, loc, map, operands);
1573}
1574
1575OpFoldResult
1576mlir::affine::makeComposedFoldedAffineMax(OpBuilder &b, Location loc,
1577 AffineMap map,
1578 ArrayRef<OpFoldResult> operands) {
1579 return makeComposedFoldedMinMax<AffineMaxOp>(b, loc, map, operands);
1580}
1581
1582// A symbol may appear as a dim in affine.apply operations. This function
1583// canonicalizes dims that are valid symbols into actual symbols.
1584template <class MapOrSet>
1585static void canonicalizePromotedSymbols(MapOrSet *mapOrSet,
1586 SmallVectorImpl<Value> *operands) {
1587 if (!mapOrSet || operands->empty())
1588 return;
1589
1590 assert(mapOrSet->getNumInputs() == operands->size() &&
1591 "map/set inputs must match number of operands");
1592
1593 auto *context = mapOrSet->getContext();
1594 SmallVector<Value, 8> resultOperands;
1595 resultOperands.reserve(N: operands->size());
1596 SmallVector<Value, 8> remappedSymbols;
1597 remappedSymbols.reserve(N: operands->size());
1598 unsigned nextDim = 0;
1599 unsigned nextSym = 0;
1600 unsigned oldNumSyms = mapOrSet->getNumSymbols();
1601 SmallVector<AffineExpr, 8> dimRemapping(mapOrSet->getNumDims());
1602 for (unsigned i = 0, e = mapOrSet->getNumInputs(); i != e; ++i) {
1603 if (i < mapOrSet->getNumDims()) {
1604 if (isValidSymbol(value: (*operands)[i])) {
1605 // This is a valid symbol that appears as a dim, canonicalize it.
1606 dimRemapping[i] = getAffineSymbolExpr(oldNumSyms + nextSym++, context);
1607 remappedSymbols.push_back(Elt: (*operands)[i]);
1608 } else {
1609 dimRemapping[i] = getAffineDimExpr(nextDim++, context);
1610 resultOperands.push_back(Elt: (*operands)[i]);
1611 }
1612 } else {
1613 resultOperands.push_back(Elt: (*operands)[i]);
1614 }
1615 }
1616
1617 resultOperands.append(in_start: remappedSymbols.begin(), in_end: remappedSymbols.end());
1618 *operands = std::move(resultOperands);
1619 *mapOrSet = mapOrSet->replaceDimsAndSymbols(
1620 dimRemapping, /*symReplacements=*/{}, nextDim, oldNumSyms + nextSym);
1621
1622 assert(mapOrSet->getNumInputs() == operands->size() &&
1623 "map/set inputs must match number of operands");
1624}
1625
1626/// A valid affine dimension may appear as a symbol in affine.apply operations.
1627/// Given an application of `operands` to an affine map or integer set
1628/// `mapOrSet`, this function canonicalizes symbols of `mapOrSet` that are valid
1629/// dims, but not valid symbols into actual dims. Without such a legalization,
1630/// the affine.apply will be invalid. This method is the exact inverse of
1631/// canonicalizePromotedSymbols.
1632template <class MapOrSet>
1633static void legalizeDemotedDims(MapOrSet &mapOrSet,
1634 SmallVectorImpl<Value> &operands) {
1635 if (!mapOrSet || operands.empty())
1636 return;
1637
1638 unsigned numOperands = operands.size();
1639
1640 assert(mapOrSet.getNumInputs() == numOperands &&
1641 "map/set inputs must match number of operands");
1642
1643 auto *context = mapOrSet.getContext();
1644 SmallVector<Value, 8> resultOperands;
1645 resultOperands.reserve(N: numOperands);
1646 SmallVector<Value, 8> remappedDims;
1647 remappedDims.reserve(N: numOperands);
1648 SmallVector<Value, 8> symOperands;
1649 symOperands.reserve(N: mapOrSet.getNumSymbols());
1650 unsigned nextSym = 0;
1651 unsigned nextDim = 0;
1652 unsigned oldNumDims = mapOrSet.getNumDims();
1653 SmallVector<AffineExpr, 8> symRemapping(mapOrSet.getNumSymbols());
1654 resultOperands.assign(in_start: operands.begin(), in_end: operands.begin() + oldNumDims);
1655 for (unsigned i = oldNumDims, e = mapOrSet.getNumInputs(); i != e; ++i) {
1656 if (operands[i] && isValidDim(value: operands[i]) && !isValidSymbol(value: operands[i])) {
1657 // This is a valid dim that appears as a symbol, legalize it.
1658 symRemapping[i - oldNumDims] =
1659 getAffineDimExpr(oldNumDims + nextDim++, context);
1660 remappedDims.push_back(Elt: operands[i]);
1661 } else {
1662 symRemapping[i - oldNumDims] = getAffineSymbolExpr(nextSym++, context);
1663 symOperands.push_back(Elt: operands[i]);
1664 }
1665 }
1666
1667 append_range(C&: resultOperands, R&: remappedDims);
1668 append_range(C&: resultOperands, R&: symOperands);
1669 operands = std::move(resultOperands);
1670 mapOrSet = mapOrSet.replaceDimsAndSymbols(
1671 /*dimReplacements=*/{}, symRemapping, oldNumDims + nextDim, nextSym);
1672
1673 assert(mapOrSet.getNumInputs() == operands.size() &&
1674 "map/set inputs must match number of operands");
1675}
1676
1677// Works for either an affine map or an integer set.
1678template <class MapOrSet>
1679static void canonicalizeMapOrSetAndOperands(MapOrSet *mapOrSet,
1680 SmallVectorImpl<Value> *operands) {
1681 static_assert(llvm::is_one_of<MapOrSet, AffineMap, IntegerSet>::value,
1682 "Argument must be either of AffineMap or IntegerSet type");
1683
1684 if (!mapOrSet || operands->empty())
1685 return;
1686
1687 assert(mapOrSet->getNumInputs() == operands->size() &&
1688 "map/set inputs must match number of operands");
1689
1690 canonicalizePromotedSymbols<MapOrSet>(mapOrSet, operands);
1691 legalizeDemotedDims<MapOrSet>(*mapOrSet, *operands);
1692
1693 // Check to see what dims are used.
1694 llvm::SmallBitVector usedDims(mapOrSet->getNumDims());
1695 llvm::SmallBitVector usedSyms(mapOrSet->getNumSymbols());
1696 mapOrSet->walkExprs([&](AffineExpr expr) {
1697 if (auto dimExpr = dyn_cast<AffineDimExpr>(Val&: expr))
1698 usedDims[dimExpr.getPosition()] = true;
1699 else if (auto symExpr = dyn_cast<AffineSymbolExpr>(Val&: expr))
1700 usedSyms[symExpr.getPosition()] = true;
1701 });
1702
1703 auto *context = mapOrSet->getContext();
1704
1705 SmallVector<Value, 8> resultOperands;
1706 resultOperands.reserve(N: operands->size());
1707
1708 llvm::SmallDenseMap<Value, AffineExpr, 8> seenDims;
1709 SmallVector<AffineExpr, 8> dimRemapping(mapOrSet->getNumDims());
1710 unsigned nextDim = 0;
1711 for (unsigned i = 0, e = mapOrSet->getNumDims(); i != e; ++i) {
1712 if (usedDims[i]) {
1713 // Remap dim positions for duplicate operands.
1714 auto it = seenDims.find(Val: (*operands)[i]);
1715 if (it == seenDims.end()) {
1716 dimRemapping[i] = getAffineDimExpr(nextDim++, context);
1717 resultOperands.push_back(Elt: (*operands)[i]);
1718 seenDims.insert(KV: std::make_pair(x&: (*operands)[i], y&: dimRemapping[i]));
1719 } else {
1720 dimRemapping[i] = it->second;
1721 }
1722 }
1723 }
1724 llvm::SmallDenseMap<Value, AffineExpr, 8> seenSymbols;
1725 SmallVector<AffineExpr, 8> symRemapping(mapOrSet->getNumSymbols());
1726 unsigned nextSym = 0;
1727 for (unsigned i = 0, e = mapOrSet->getNumSymbols(); i != e; ++i) {
1728 if (!usedSyms[i])
1729 continue;
1730 // Handle constant operands (only needed for symbolic operands since
1731 // constant operands in dimensional positions would have already been
1732 // promoted to symbolic positions above).
1733 IntegerAttr operandCst;
1734 if (matchPattern((*operands)[i + mapOrSet->getNumDims()],
1735 m_Constant(bind_value: &operandCst))) {
1736 symRemapping[i] =
1737 getAffineConstantExpr(operandCst.getValue().getSExtValue(), context);
1738 continue;
1739 }
1740 // Remap symbol positions for duplicate operands.
1741 auto it = seenSymbols.find((*operands)[i + mapOrSet->getNumDims()]);
1742 if (it == seenSymbols.end()) {
1743 symRemapping[i] = getAffineSymbolExpr(nextSym++, context);
1744 resultOperands.push_back(Elt: (*operands)[i + mapOrSet->getNumDims()]);
1745 seenSymbols.insert(std::make_pair((*operands)[i + mapOrSet->getNumDims()],
1746 symRemapping[i]));
1747 } else {
1748 symRemapping[i] = it->second;
1749 }
1750 }
1751 *mapOrSet = mapOrSet->replaceDimsAndSymbols(dimRemapping, symRemapping,
1752 nextDim, nextSym);
1753 *operands = std::move(resultOperands);
1754}
1755
1756void mlir::affine::canonicalizeMapAndOperands(
1757 AffineMap *map, SmallVectorImpl<Value> *operands) {
1758 canonicalizeMapOrSetAndOperands<AffineMap>(mapOrSet: map, operands);
1759}
1760
1761void mlir::affine::canonicalizeSetAndOperands(
1762 IntegerSet *set, SmallVectorImpl<Value> *operands) {
1763 canonicalizeMapOrSetAndOperands<IntegerSet>(mapOrSet: set, operands);
1764}
1765
1766namespace {
1767/// Simplify AffineApply, AffineLoad, and AffineStore operations by composing
1768/// maps that supply results into them.
1769///
1770template <typename AffineOpTy>
1771struct SimplifyAffineOp : public OpRewritePattern<AffineOpTy> {
1772 using OpRewritePattern<AffineOpTy>::OpRewritePattern;
1773
1774 /// Replace the affine op with another instance of it with the supplied
1775 /// map and mapOperands.
1776 void replaceAffineOp(PatternRewriter &rewriter, AffineOpTy affineOp,
1777 AffineMap map, ArrayRef<Value> mapOperands) const;
1778
1779 LogicalResult matchAndRewrite(AffineOpTy affineOp,
1780 PatternRewriter &rewriter) const override {
1781 static_assert(
1782 llvm::is_one_of<AffineOpTy, AffineLoadOp, AffinePrefetchOp,
1783 AffineStoreOp, AffineApplyOp, AffineMinOp, AffineMaxOp,
1784 AffineVectorStoreOp, AffineVectorLoadOp>::value,
1785 "affine load/store/vectorstore/vectorload/apply/prefetch/min/max op "
1786 "expected");
1787 auto map = affineOp.getAffineMap();
1788 AffineMap oldMap = map;
1789 auto oldOperands = affineOp.getMapOperands();
1790 SmallVector<Value, 8> resultOperands(oldOperands);
1791 composeAffineMapAndOperands(&map, &resultOperands);
1792 canonicalizeMapAndOperands(&map, &resultOperands);
1793 simplifyMapWithOperands(map, resultOperands);
1794 if (map == oldMap && std::equal(oldOperands.begin(), oldOperands.end(),
1795 resultOperands.begin()))
1796 return failure();
1797
1798 replaceAffineOp(rewriter, affineOp, map, mapOperands: resultOperands);
1799 return success();
1800 }
1801};
1802
1803// Specialize the template to account for the different build signatures for
1804// affine load, store, and apply ops.
1805template <>
1806void SimplifyAffineOp<AffineLoadOp>::replaceAffineOp(
1807 PatternRewriter &rewriter, AffineLoadOp load, AffineMap map,
1808 ArrayRef<Value> mapOperands) const {
1809 rewriter.replaceOpWithNewOp<AffineLoadOp>(op: load, args: load.getMemRef(), args&: map,
1810 args&: mapOperands, args: load.getMaybeAlign());
1811}
1812template <>
1813void SimplifyAffineOp<AffinePrefetchOp>::replaceAffineOp(
1814 PatternRewriter &rewriter, AffinePrefetchOp prefetch, AffineMap map,
1815 ArrayRef<Value> mapOperands) const {
1816 rewriter.replaceOpWithNewOp<AffinePrefetchOp>(
1817 op: prefetch, args: prefetch.getMemref(), args&: map, args&: mapOperands, args: prefetch.getIsWrite(),
1818 args: prefetch.getLocalityHint(), args: prefetch.getIsDataCache());
1819}
1820template <>
1821void SimplifyAffineOp<AffineStoreOp>::replaceAffineOp(
1822 PatternRewriter &rewriter, AffineStoreOp store, AffineMap map,
1823 ArrayRef<Value> mapOperands) const {
1824 rewriter.replaceOpWithNewOp<AffineStoreOp>(
1825 op: store, args: store.getValueToStore(), args: store.getMemRef(), args&: map, args&: mapOperands,
1826 args: store.getMaybeAlign());
1827}
1828template <>
1829void SimplifyAffineOp<AffineVectorLoadOp>::replaceAffineOp(
1830 PatternRewriter &rewriter, AffineVectorLoadOp vectorload, AffineMap map,
1831 ArrayRef<Value> mapOperands) const {
1832 rewriter.replaceOpWithNewOp<AffineVectorLoadOp>(
1833 op: vectorload, args: vectorload.getVectorType(), args: vectorload.getMemRef(), args&: map,
1834 args&: mapOperands, args: vectorload.getMaybeAlign());
1835}
1836template <>
1837void SimplifyAffineOp<AffineVectorStoreOp>::replaceAffineOp(
1838 PatternRewriter &rewriter, AffineVectorStoreOp vectorstore, AffineMap map,
1839 ArrayRef<Value> mapOperands) const {
1840 rewriter.replaceOpWithNewOp<AffineVectorStoreOp>(
1841 op: vectorstore, args: vectorstore.getValueToStore(), args: vectorstore.getMemRef(), args&: map,
1842 args&: mapOperands, args: vectorstore.getMaybeAlign());
1843}
1844
1845// Generic version for ops that don't have extra operands.
1846template <typename AffineOpTy>
1847void SimplifyAffineOp<AffineOpTy>::replaceAffineOp(
1848 PatternRewriter &rewriter, AffineOpTy op, AffineMap map,
1849 ArrayRef<Value> mapOperands) const {
1850 rewriter.replaceOpWithNewOp<AffineOpTy>(op, map, mapOperands);
1851}
1852} // namespace
1853
1854void AffineApplyOp::getCanonicalizationPatterns(RewritePatternSet &results,
1855 MLIRContext *context) {
1856 results.add<SimplifyAffineOp<AffineApplyOp>>(arg&: context);
1857}
1858
1859//===----------------------------------------------------------------------===//
1860// AffineDmaStartOp
1861//===----------------------------------------------------------------------===//
1862
1863// TODO: Check that map operands are loop IVs or symbols.
1864void AffineDmaStartOp::build(OpBuilder &builder, OperationState &result,
1865 Value srcMemRef, AffineMap srcMap,
1866 ValueRange srcIndices, Value destMemRef,
1867 AffineMap dstMap, ValueRange destIndices,
1868 Value tagMemRef, AffineMap tagMap,
1869 ValueRange tagIndices, Value numElements,
1870 Value stride, Value elementsPerStride) {
1871 result.addOperands(newOperands: srcMemRef);
1872 result.addAttribute(name: getSrcMapAttrStrName(), attr: AffineMapAttr::get(value: srcMap));
1873 result.addOperands(newOperands: srcIndices);
1874 result.addOperands(newOperands: destMemRef);
1875 result.addAttribute(name: getDstMapAttrStrName(), attr: AffineMapAttr::get(value: dstMap));
1876 result.addOperands(newOperands: destIndices);
1877 result.addOperands(newOperands: tagMemRef);
1878 result.addAttribute(name: getTagMapAttrStrName(), attr: AffineMapAttr::get(value: tagMap));
1879 result.addOperands(newOperands: tagIndices);
1880 result.addOperands(newOperands: numElements);
1881 if (stride) {
1882 result.addOperands(newOperands: {stride, elementsPerStride});
1883 }
1884}
1885
1886void AffineDmaStartOp::print(OpAsmPrinter &p) {
1887 p << " " << getSrcMemRef() << '[';
1888 p.printAffineMapOfSSAIds(mapAttr: getSrcMapAttr(), operands: getSrcIndices());
1889 p << "], " << getDstMemRef() << '[';
1890 p.printAffineMapOfSSAIds(mapAttr: getDstMapAttr(), operands: getDstIndices());
1891 p << "], " << getTagMemRef() << '[';
1892 p.printAffineMapOfSSAIds(mapAttr: getTagMapAttr(), operands: getTagIndices());
1893 p << "], " << getNumElements();
1894 if (isStrided()) {
1895 p << ", " << getStride();
1896 p << ", " << getNumElementsPerStride();
1897 }
1898 p << " : " << getSrcMemRefType() << ", " << getDstMemRefType() << ", "
1899 << getTagMemRefType();
1900}
1901
1902// Parse AffineDmaStartOp.
1903// Ex:
1904// affine.dma_start %src[%i, %j], %dst[%k, %l], %tag[%index], %size,
1905// %stride, %num_elt_per_stride
1906// : memref<3076 x f32, 0>, memref<1024 x f32, 2>, memref<1 x i32>
1907//
1908ParseResult AffineDmaStartOp::parse(OpAsmParser &parser,
1909 OperationState &result) {
1910 OpAsmParser::UnresolvedOperand srcMemRefInfo;
1911 AffineMapAttr srcMapAttr;
1912 SmallVector<OpAsmParser::UnresolvedOperand, 4> srcMapOperands;
1913 OpAsmParser::UnresolvedOperand dstMemRefInfo;
1914 AffineMapAttr dstMapAttr;
1915 SmallVector<OpAsmParser::UnresolvedOperand, 4> dstMapOperands;
1916 OpAsmParser::UnresolvedOperand tagMemRefInfo;
1917 AffineMapAttr tagMapAttr;
1918 SmallVector<OpAsmParser::UnresolvedOperand, 4> tagMapOperands;
1919 OpAsmParser::UnresolvedOperand numElementsInfo;
1920 SmallVector<OpAsmParser::UnresolvedOperand, 2> strideInfo;
1921
1922 SmallVector<Type, 3> types;
1923 auto indexType = parser.getBuilder().getIndexType();
1924
1925 // Parse and resolve the following list of operands:
1926 // *) dst memref followed by its affine maps operands (in square brackets).
1927 // *) src memref followed by its affine map operands (in square brackets).
1928 // *) tag memref followed by its affine map operands (in square brackets).
1929 // *) number of elements transferred by DMA operation.
1930 if (parser.parseOperand(result&: srcMemRefInfo) ||
1931 parser.parseAffineMapOfSSAIds(operands&: srcMapOperands, map&: srcMapAttr,
1932 attrName: getSrcMapAttrStrName(),
1933 attrs&: result.attributes) ||
1934 parser.parseComma() || parser.parseOperand(result&: dstMemRefInfo) ||
1935 parser.parseAffineMapOfSSAIds(operands&: dstMapOperands, map&: dstMapAttr,
1936 attrName: getDstMapAttrStrName(),
1937 attrs&: result.attributes) ||
1938 parser.parseComma() || parser.parseOperand(result&: tagMemRefInfo) ||
1939 parser.parseAffineMapOfSSAIds(operands&: tagMapOperands, map&: tagMapAttr,
1940 attrName: getTagMapAttrStrName(),
1941 attrs&: result.attributes) ||
1942 parser.parseComma() || parser.parseOperand(result&: numElementsInfo))
1943 return failure();
1944
1945 // Parse optional stride and elements per stride.
1946 if (parser.parseTrailingOperandList(result&: strideInfo))
1947 return failure();
1948
1949 if (!strideInfo.empty() && strideInfo.size() != 2) {
1950 return parser.emitError(loc: parser.getNameLoc(),
1951 message: "expected two stride related operands");
1952 }
1953 bool isStrided = strideInfo.size() == 2;
1954
1955 if (parser.parseColonTypeList(result&: types))
1956 return failure();
1957
1958 if (types.size() != 3)
1959 return parser.emitError(loc: parser.getNameLoc(), message: "expected three types");
1960
1961 if (parser.resolveOperand(operand: srcMemRefInfo, type: types[0], result&: result.operands) ||
1962 parser.resolveOperands(operands&: srcMapOperands, type: indexType, result&: result.operands) ||
1963 parser.resolveOperand(operand: dstMemRefInfo, type: types[1], result&: result.operands) ||
1964 parser.resolveOperands(operands&: dstMapOperands, type: indexType, result&: result.operands) ||
1965 parser.resolveOperand(operand: tagMemRefInfo, type: types[2], result&: result.operands) ||
1966 parser.resolveOperands(operands&: tagMapOperands, type: indexType, result&: result.operands) ||
1967 parser.resolveOperand(operand: numElementsInfo, type: indexType, result&: result.operands))
1968 return failure();
1969
1970 if (isStrided) {
1971 if (parser.resolveOperands(operands&: strideInfo, type: indexType, result&: result.operands))
1972 return failure();
1973 }
1974
1975 // Check that src/dst/tag operand counts match their map.numInputs.
1976 if (srcMapOperands.size() != srcMapAttr.getValue().getNumInputs() ||
1977 dstMapOperands.size() != dstMapAttr.getValue().getNumInputs() ||
1978 tagMapOperands.size() != tagMapAttr.getValue().getNumInputs())
1979 return parser.emitError(loc: parser.getNameLoc(),
1980 message: "memref operand count not equal to map.numInputs");
1981 return success();
1982}
1983
1984LogicalResult AffineDmaStartOp::verify() {
1985 if (!llvm::isa<MemRefType>(Val: getOperand(i: getSrcMemRefOperandIndex()).getType()))
1986 return emitOpError(message: "expected DMA source to be of memref type");
1987 if (!llvm::isa<MemRefType>(Val: getOperand(i: getDstMemRefOperandIndex()).getType()))
1988 return emitOpError(message: "expected DMA destination to be of memref type");
1989 if (!llvm::isa<MemRefType>(Val: getOperand(i: getTagMemRefOperandIndex()).getType()))
1990 return emitOpError(message: "expected DMA tag to be of memref type");
1991
1992 unsigned numInputsAllMaps = getSrcMap().getNumInputs() +
1993 getDstMap().getNumInputs() +
1994 getTagMap().getNumInputs();
1995 if (getNumOperands() != numInputsAllMaps + 3 + 1 &&
1996 getNumOperands() != numInputsAllMaps + 3 + 1 + 2) {
1997 return emitOpError(message: "incorrect number of operands");
1998 }
1999
2000 Region *scope = getAffineScope(op: *this);
2001 for (auto idx : getSrcIndices()) {
2002 if (!idx.getType().isIndex())
2003 return emitOpError(message: "src index to dma_start must have 'index' type");
2004 if (!isValidAffineIndexOperand(value: idx, region: scope))
2005 return emitOpError(
2006 message: "src index must be a valid dimension or symbol identifier");
2007 }
2008 for (auto idx : getDstIndices()) {
2009 if (!idx.getType().isIndex())
2010 return emitOpError(message: "dst index to dma_start must have 'index' type");
2011 if (!isValidAffineIndexOperand(value: idx, region: scope))
2012 return emitOpError(
2013 message: "dst index must be a valid dimension or symbol identifier");
2014 }
2015 for (auto idx : getTagIndices()) {
2016 if (!idx.getType().isIndex())
2017 return emitOpError(message: "tag index to dma_start must have 'index' type");
2018 if (!isValidAffineIndexOperand(value: idx, region: scope))
2019 return emitOpError(
2020 message: "tag index must be a valid dimension or symbol identifier");
2021 }
2022 return success();
2023}
2024
2025LogicalResult AffineDmaStartOp::fold(FoldAdaptor adaptor,
2026 SmallVectorImpl<OpFoldResult> &results) {
2027 /// dma_start(memrefcast) -> dma_start
2028 return memref::foldMemRefCast(op: *this);
2029}
2030
2031void AffineDmaStartOp::getEffects(
2032 SmallVectorImpl<SideEffects::EffectInstance<MemoryEffects::Effect>>
2033 &effects) {
2034 effects.emplace_back(Args: MemoryEffects::Read::get(), Args: &getSrcMemRefMutable(),
2035 Args: SideEffects::DefaultResource::get());
2036 effects.emplace_back(Args: MemoryEffects::Write::get(), Args: &getDstMemRefMutable(),
2037 Args: SideEffects::DefaultResource::get());
2038 effects.emplace_back(Args: MemoryEffects::Read::get(), Args: &getTagMemRefMutable(),
2039 Args: SideEffects::DefaultResource::get());
2040}
2041
2042//===----------------------------------------------------------------------===//
2043// AffineDmaWaitOp
2044//===----------------------------------------------------------------------===//
2045
2046// TODO: Check that map operands are loop IVs or symbols.
2047void AffineDmaWaitOp::build(OpBuilder &builder, OperationState &result,
2048 Value tagMemRef, AffineMap tagMap,
2049 ValueRange tagIndices, Value numElements) {
2050 result.addOperands(newOperands: tagMemRef);
2051 result.addAttribute(name: getTagMapAttrStrName(), attr: AffineMapAttr::get(value: tagMap));
2052 result.addOperands(newOperands: tagIndices);
2053 result.addOperands(newOperands: numElements);
2054}
2055
2056void AffineDmaWaitOp::print(OpAsmPrinter &p) {
2057 p << " " << getTagMemRef() << '[';
2058 SmallVector<Value, 2> operands(getTagIndices());
2059 p.printAffineMapOfSSAIds(mapAttr: getTagMapAttr(), operands);
2060 p << "], ";
2061 p.printOperand(value: getNumElements());
2062 p << " : " << getTagMemRef().getType();
2063}
2064
2065// Parse AffineDmaWaitOp.
2066// Eg:
2067// affine.dma_wait %tag[%index], %num_elements
2068// : memref<1 x i32, (d0) -> (d0), 4>
2069//
2070ParseResult AffineDmaWaitOp::parse(OpAsmParser &parser,
2071 OperationState &result) {
2072 OpAsmParser::UnresolvedOperand tagMemRefInfo;
2073 AffineMapAttr tagMapAttr;
2074 SmallVector<OpAsmParser::UnresolvedOperand, 2> tagMapOperands;
2075 Type type;
2076 auto indexType = parser.getBuilder().getIndexType();
2077 OpAsmParser::UnresolvedOperand numElementsInfo;
2078
2079 // Parse tag memref, its map operands, and dma size.
2080 if (parser.parseOperand(result&: tagMemRefInfo) ||
2081 parser.parseAffineMapOfSSAIds(operands&: tagMapOperands, map&: tagMapAttr,
2082 attrName: getTagMapAttrStrName(),
2083 attrs&: result.attributes) ||
2084 parser.parseComma() || parser.parseOperand(result&: numElementsInfo) ||
2085 parser.parseColonType(result&: type) ||
2086 parser.resolveOperand(operand: tagMemRefInfo, type, result&: result.operands) ||
2087 parser.resolveOperands(operands&: tagMapOperands, type: indexType, result&: result.operands) ||
2088 parser.resolveOperand(operand: numElementsInfo, type: indexType, result&: result.operands))
2089 return failure();
2090
2091 if (!llvm::isa<MemRefType>(Val: type))
2092 return parser.emitError(loc: parser.getNameLoc(),
2093 message: "expected tag to be of memref type");
2094
2095 if (tagMapOperands.size() != tagMapAttr.getValue().getNumInputs())
2096 return parser.emitError(loc: parser.getNameLoc(),
2097 message: "tag memref operand count != to map.numInputs");
2098 return success();
2099}
2100
2101LogicalResult AffineDmaWaitOp::verify() {
2102 if (!llvm::isa<MemRefType>(Val: getOperand(i: 0).getType()))
2103 return emitOpError(message: "expected DMA tag to be of memref type");
2104 Region *scope = getAffineScope(op: *this);
2105 for (auto idx : getTagIndices()) {
2106 if (!idx.getType().isIndex())
2107 return emitOpError(message: "index to dma_wait must have 'index' type");
2108 if (!isValidAffineIndexOperand(value: idx, region: scope))
2109 return emitOpError(
2110 message: "index must be a valid dimension or symbol identifier");
2111 }
2112 return success();
2113}
2114
2115LogicalResult AffineDmaWaitOp::fold(FoldAdaptor adaptor,
2116 SmallVectorImpl<OpFoldResult> &results) {
2117 /// dma_wait(memrefcast) -> dma_wait
2118 return memref::foldMemRefCast(op: *this);
2119}
2120
2121void AffineDmaWaitOp::getEffects(
2122 SmallVectorImpl<SideEffects::EffectInstance<MemoryEffects::Effect>>
2123 &effects) {
2124 effects.emplace_back(Args: MemoryEffects::Read::get(), Args: &getTagMemRefMutable(),
2125 Args: SideEffects::DefaultResource::get());
2126}
2127
2128//===----------------------------------------------------------------------===//
2129// AffineForOp
2130//===----------------------------------------------------------------------===//
2131
2132/// 'bodyBuilder' is used to build the body of affine.for. If iterArgs and
2133/// bodyBuilder are empty/null, we include default terminator op.
2134void AffineForOp::build(OpBuilder &builder, OperationState &result,
2135 ValueRange lbOperands, AffineMap lbMap,
2136 ValueRange ubOperands, AffineMap ubMap, int64_t step,
2137 ValueRange iterArgs, BodyBuilderFn bodyBuilder) {
2138 assert(((!lbMap && lbOperands.empty()) ||
2139 lbOperands.size() == lbMap.getNumInputs()) &&
2140 "lower bound operand count does not match the affine map");
2141 assert(((!ubMap && ubOperands.empty()) ||
2142 ubOperands.size() == ubMap.getNumInputs()) &&
2143 "upper bound operand count does not match the affine map");
2144 assert(step > 0 && "step has to be a positive integer constant");
2145
2146 OpBuilder::InsertionGuard guard(builder);
2147
2148 // Set variadic segment sizes.
2149 result.addAttribute(
2150 name: getOperandSegmentSizeAttr(),
2151 attr: builder.getDenseI32ArrayAttr(values: {static_cast<int32_t>(lbOperands.size()),
2152 static_cast<int32_t>(ubOperands.size()),
2153 static_cast<int32_t>(iterArgs.size())}));
2154
2155 for (Value val : iterArgs)
2156 result.addTypes(newTypes: val.getType());
2157
2158 // Add an attribute for the step.
2159 result.addAttribute(name: getStepAttrName(name: result.name),
2160 attr: builder.getIntegerAttr(type: builder.getIndexType(), value: step));
2161
2162 // Add the lower bound.
2163 result.addAttribute(name: getLowerBoundMapAttrName(name: result.name),
2164 attr: AffineMapAttr::get(value: lbMap));
2165 result.addOperands(newOperands: lbOperands);
2166
2167 // Add the upper bound.
2168 result.addAttribute(name: getUpperBoundMapAttrName(name: result.name),
2169 attr: AffineMapAttr::get(value: ubMap));
2170 result.addOperands(newOperands: ubOperands);
2171
2172 result.addOperands(newOperands: iterArgs);
2173 // Create a region and a block for the body. The argument of the region is
2174 // the loop induction variable.
2175 Region *bodyRegion = result.addRegion();
2176 Block *bodyBlock = builder.createBlock(parent: bodyRegion);
2177 Value inductionVar =
2178 bodyBlock->addArgument(type: builder.getIndexType(), loc: result.location);
2179 for (Value val : iterArgs)
2180 bodyBlock->addArgument(type: val.getType(), loc: val.getLoc());
2181
2182 // Create the default terminator if the builder is not provided and if the
2183 // iteration arguments are not provided. Otherwise, leave this to the caller
2184 // because we don't know which values to return from the loop.
2185 if (iterArgs.empty() && !bodyBuilder) {
2186 ensureTerminator(region&: *bodyRegion, builder, loc: result.location);
2187 } else if (bodyBuilder) {
2188 OpBuilder::InsertionGuard guard(builder);
2189 builder.setInsertionPointToStart(bodyBlock);
2190 bodyBuilder(builder, result.location, inductionVar,
2191 bodyBlock->getArguments().drop_front());
2192 }
2193}
2194
2195void AffineForOp::build(OpBuilder &builder, OperationState &result, int64_t lb,
2196 int64_t ub, int64_t step, ValueRange iterArgs,
2197 BodyBuilderFn bodyBuilder) {
2198 auto lbMap = AffineMap::getConstantMap(val: lb, context: builder.getContext());
2199 auto ubMap = AffineMap::getConstantMap(val: ub, context: builder.getContext());
2200 return build(builder, result, lbOperands: {}, lbMap, ubOperands: {}, ubMap, step, iterArgs,
2201 bodyBuilder);
2202}
2203
2204LogicalResult AffineForOp::verify() {
2205 auto *body = getBody();
2206 if (body->getNumArguments() == 0 || !getInductionVar().getType().isIndex())
2207 return emitOpError(message: "expected body to have an index argument for the "
2208 "induction variable");
2209
2210 return success();
2211}
2212
2213LogicalResult AffineForOp::verifyRegions() {
2214 // Step must be a strictly positive integer.
2215 if (getStepAsInt() <= 0)
2216 return emitOpError(message: "expected step to be a positive integer, got ")
2217 << getStepAsInt();
2218
2219 // Verify that the bound operands are valid dimension/symbols.
2220 /// Lower bound.
2221 if (getLowerBoundMap().getNumInputs() > 0)
2222 if (failed(Result: verifyDimAndSymbolIdentifiers(op&: *this, operands: getLowerBoundOperands(),
2223 numDims: getLowerBoundMap().getNumDims())))
2224 return failure();
2225 /// Upper bound.
2226 if (getUpperBoundMap().getNumInputs() > 0)
2227 if (failed(Result: verifyDimAndSymbolIdentifiers(op&: *this, operands: getUpperBoundOperands(),
2228 numDims: getUpperBoundMap().getNumDims())))
2229 return failure();
2230 if (getLowerBoundMap().getNumResults() < 1)
2231 return emitOpError(message: "expected lower bound map to have at least one result");
2232 if (getUpperBoundMap().getNumResults() < 1)
2233 return emitOpError(message: "expected upper bound map to have at least one result");
2234
2235 unsigned opNumResults = getNumResults();
2236 if (opNumResults == 0)
2237 return success();
2238
2239 // If ForOp defines values, check that the number and types of the defined
2240 // values match ForOp initial iter operands and backedge basic block
2241 // arguments.
2242 if (getNumIterOperands() != opNumResults)
2243 return emitOpError(
2244 message: "mismatch between the number of loop-carried values and results");
2245 if (getNumRegionIterArgs() != opNumResults)
2246 return emitOpError(
2247 message: "mismatch between the number of basic block args and results");
2248
2249 return success();
2250}
2251
2252/// Parse a for operation loop bounds.
2253static ParseResult parseBound(bool isLower, OperationState &result,
2254 OpAsmParser &p) {
2255 // 'min' / 'max' prefixes are generally syntactic sugar, but are required if
2256 // the map has multiple results.
2257 bool failedToParsedMinMax =
2258 failed(Result: p.parseOptionalKeyword(keyword: isLower ? "max" : "min"));
2259
2260 auto &builder = p.getBuilder();
2261 auto boundAttrStrName =
2262 isLower ? AffineForOp::getLowerBoundMapAttrName(name: result.name)
2263 : AffineForOp::getUpperBoundMapAttrName(name: result.name);
2264
2265 // Parse ssa-id as identity map.
2266 SmallVector<OpAsmParser::UnresolvedOperand, 1> boundOpInfos;
2267 if (p.parseOperandList(result&: boundOpInfos))
2268 return failure();
2269
2270 if (!boundOpInfos.empty()) {
2271 // Check that only one operand was parsed.
2272 if (boundOpInfos.size() > 1)
2273 return p.emitError(loc: p.getNameLoc(),
2274 message: "expected only one loop bound operand");
2275
2276 // TODO: improve error message when SSA value is not of index type.
2277 // Currently it is 'use of value ... expects different type than prior uses'
2278 if (p.resolveOperand(operand: boundOpInfos.front(), type: builder.getIndexType(),
2279 result&: result.operands))
2280 return failure();
2281
2282 // Create an identity map using symbol id. This representation is optimized
2283 // for storage. Analysis passes may expand it into a multi-dimensional map
2284 // if desired.
2285 AffineMap map = builder.getSymbolIdentityMap();
2286 result.addAttribute(name: boundAttrStrName, attr: AffineMapAttr::get(value: map));
2287 return success();
2288 }
2289
2290 // Get the attribute location.
2291 SMLoc attrLoc = p.getCurrentLocation();
2292
2293 Attribute boundAttr;
2294 if (p.parseAttribute(result&: boundAttr, type: builder.getIndexType(), attrName: boundAttrStrName,
2295 attrs&: result.attributes))
2296 return failure();
2297
2298 // Parse full form - affine map followed by dim and symbol list.
2299 if (auto affineMapAttr = dyn_cast<AffineMapAttr>(Val&: boundAttr)) {
2300 unsigned currentNumOperands = result.operands.size();
2301 unsigned numDims;
2302 if (parseDimAndSymbolList(parser&: p, operands&: result.operands, numDims))
2303 return failure();
2304
2305 auto map = affineMapAttr.getValue();
2306 if (map.getNumDims() != numDims)
2307 return p.emitError(
2308 loc: p.getNameLoc(),
2309 message: "dim operand count and affine map dim count must match");
2310
2311 unsigned numDimAndSymbolOperands =
2312 result.operands.size() - currentNumOperands;
2313 if (numDims + map.getNumSymbols() != numDimAndSymbolOperands)
2314 return p.emitError(
2315 loc: p.getNameLoc(),
2316 message: "symbol operand count and affine map symbol count must match");
2317
2318 // If the map has multiple results, make sure that we parsed the min/max
2319 // prefix.
2320 if (map.getNumResults() > 1 && failedToParsedMinMax) {
2321 if (isLower) {
2322 return p.emitError(loc: attrLoc, message: "lower loop bound affine map with "
2323 "multiple results requires 'max' prefix");
2324 }
2325 return p.emitError(loc: attrLoc, message: "upper loop bound affine map with multiple "
2326 "results requires 'min' prefix");
2327 }
2328 return success();
2329 }
2330
2331 // Parse custom assembly form.
2332 if (auto integerAttr = dyn_cast<IntegerAttr>(Val&: boundAttr)) {
2333 result.attributes.pop_back();
2334 result.addAttribute(
2335 name: boundAttrStrName,
2336 attr: AffineMapAttr::get(value: builder.getConstantAffineMap(val: integerAttr.getInt())));
2337 return success();
2338 }
2339
2340 return p.emitError(
2341 loc: p.getNameLoc(),
2342 message: "expected valid affine map representation for loop bounds");
2343}
2344
2345ParseResult AffineForOp::parse(OpAsmParser &parser, OperationState &result) {
2346 auto &builder = parser.getBuilder();
2347 OpAsmParser::Argument inductionVariable;
2348 inductionVariable.type = builder.getIndexType();
2349 // Parse the induction variable followed by '='.
2350 if (parser.parseArgument(result&: inductionVariable) || parser.parseEqual())
2351 return failure();
2352
2353 // Parse loop bounds.
2354 int64_t numOperands = result.operands.size();
2355 if (parseBound(/*isLower=*/true, result, p&: parser))
2356 return failure();
2357 int64_t numLbOperands = result.operands.size() - numOperands;
2358 if (parser.parseKeyword(keyword: "to", msg: " between bounds"))
2359 return failure();
2360 numOperands = result.operands.size();
2361 if (parseBound(/*isLower=*/false, result, p&: parser))
2362 return failure();
2363 int64_t numUbOperands = result.operands.size() - numOperands;
2364
2365 // Parse the optional loop step, we default to 1 if one is not present.
2366 if (parser.parseOptionalKeyword(keyword: "step")) {
2367 result.addAttribute(
2368 name: getStepAttrName(name: result.name),
2369 attr: builder.getIntegerAttr(type: builder.getIndexType(), /*value=*/1));
2370 } else {
2371 SMLoc stepLoc = parser.getCurrentLocation();
2372 IntegerAttr stepAttr;
2373 if (parser.parseAttribute(result&: stepAttr, type: builder.getIndexType(),
2374 attrName: getStepAttrName(name: result.name).data(),
2375 attrs&: result.attributes))
2376 return failure();
2377
2378 if (!stepAttr.getValue().isStrictlyPositive())
2379 return parser.emitError(
2380 loc: stepLoc,
2381 message: "expected step to be representable as a positive signed integer");
2382 }
2383
2384 // Parse the optional initial iteration arguments.
2385 SmallVector<OpAsmParser::Argument, 4> regionArgs;
2386 SmallVector<OpAsmParser::UnresolvedOperand, 4> operands;
2387
2388 // Induction variable.
2389 regionArgs.push_back(Elt: inductionVariable);
2390
2391 if (succeeded(Result: parser.parseOptionalKeyword(keyword: "iter_args"))) {
2392 // Parse assignment list and results type list.
2393 if (parser.parseAssignmentList(lhs&: regionArgs, rhs&: operands) ||
2394 parser.parseArrowTypeList(result&: result.types))
2395 return failure();
2396 // Resolve input operands.
2397 for (auto argOperandType :
2398 llvm::zip(t: llvm::drop_begin(RangeOrContainer&: regionArgs), u&: operands, args&: result.types)) {
2399 Type type = std::get<2>(t&: argOperandType);
2400 std::get<0>(t&: argOperandType).type = type;
2401 if (parser.resolveOperand(operand: std::get<1>(t&: argOperandType), type,
2402 result&: result.operands))
2403 return failure();
2404 }
2405 }
2406
2407 result.addAttribute(
2408 name: getOperandSegmentSizeAttr(),
2409 attr: builder.getDenseI32ArrayAttr(values: {static_cast<int32_t>(numLbOperands),
2410 static_cast<int32_t>(numUbOperands),
2411 static_cast<int32_t>(operands.size())}));
2412
2413 // Parse the body region.
2414 Region *body = result.addRegion();
2415 if (regionArgs.size() != result.types.size() + 1)
2416 return parser.emitError(
2417 loc: parser.getNameLoc(),
2418 message: "mismatch between the number of loop-carried values and results");
2419 if (parser.parseRegion(region&: *body, arguments: regionArgs))
2420 return failure();
2421
2422 AffineForOp::ensureTerminator(region&: *body, builder, loc: result.location);
2423
2424 // Parse the optional attribute list.
2425 return parser.parseOptionalAttrDict(result&: result.attributes);
2426}
2427
2428static void printBound(AffineMapAttr boundMap,
2429 Operation::operand_range boundOperands,
2430 const char *prefix, OpAsmPrinter &p) {
2431 AffineMap map = boundMap.getValue();
2432
2433 // Check if this bound should be printed using custom assembly form.
2434 // The decision to restrict printing custom assembly form to trivial cases
2435 // comes from the will to roundtrip MLIR binary -> text -> binary in a
2436 // lossless way.
2437 // Therefore, custom assembly form parsing and printing is only supported for
2438 // zero-operand constant maps and single symbol operand identity maps.
2439 if (map.getNumResults() == 1) {
2440 AffineExpr expr = map.getResult(idx: 0);
2441
2442 // Print constant bound.
2443 if (map.getNumDims() == 0 && map.getNumSymbols() == 0) {
2444 if (auto constExpr = dyn_cast<AffineConstantExpr>(Val&: expr)) {
2445 p << constExpr.getValue();
2446 return;
2447 }
2448 }
2449
2450 // Print bound that consists of a single SSA symbol if the map is over a
2451 // single symbol.
2452 if (map.getNumDims() == 0 && map.getNumSymbols() == 1) {
2453 if (isa<AffineSymbolExpr>(Val: expr)) {
2454 p.printOperand(value: *boundOperands.begin());
2455 return;
2456 }
2457 }
2458 } else {
2459 // Map has multiple results. Print 'min' or 'max' prefix.
2460 p << prefix << ' ';
2461 }
2462
2463 // Print the map and its operands.
2464 p << boundMap;
2465 printDimAndSymbolList(begin: boundOperands.begin(), end: boundOperands.end(),
2466 numDims: map.getNumDims(), printer&: p);
2467}
2468
2469unsigned AffineForOp::getNumIterOperands() {
2470 AffineMap lbMap = getLowerBoundMapAttr().getValue();
2471 AffineMap ubMap = getUpperBoundMapAttr().getValue();
2472
2473 return getNumOperands() - lbMap.getNumInputs() - ubMap.getNumInputs();
2474}
2475
2476std::optional<MutableArrayRef<OpOperand>>
2477AffineForOp::getYieldedValuesMutable() {
2478 return cast<AffineYieldOp>(Val: getBody()->getTerminator()).getOperandsMutable();
2479}
2480
2481void AffineForOp::print(OpAsmPrinter &p) {
2482 p << ' ';
2483 p.printRegionArgument(arg: getBody()->getArgument(i: 0), /*argAttrs=*/{},
2484 /*omitType=*/true);
2485 p << " = ";
2486 printBound(boundMap: getLowerBoundMapAttr(), boundOperands: getLowerBoundOperands(), prefix: "max", p);
2487 p << " to ";
2488 printBound(boundMap: getUpperBoundMapAttr(), boundOperands: getUpperBoundOperands(), prefix: "min", p);
2489
2490 if (getStepAsInt() != 1)
2491 p << " step " << getStepAsInt();
2492
2493 bool printBlockTerminators = false;
2494 if (getNumIterOperands() > 0) {
2495 p << " iter_args(";
2496 auto regionArgs = getRegionIterArgs();
2497 auto operands = getInits();
2498
2499 llvm::interleaveComma(c: llvm::zip(t&: regionArgs, u&: operands), os&: p, each_fn: [&](auto it) {
2500 p << std::get<0>(it) << " = " << std::get<1>(it);
2501 });
2502 p << ") -> (" << getResultTypes() << ")";
2503 printBlockTerminators = true;
2504 }
2505
2506 p << ' ';
2507 p.printRegion(blocks&: getRegion(), /*printEntryBlockArgs=*/false,
2508 printBlockTerminators);
2509 p.printOptionalAttrDict(attrs: (*this)->getDiscardableAttrDictionary().getValue());
2510}
2511
2512/// Fold the constant bounds of a loop.
2513static LogicalResult foldLoopBounds(AffineForOp forOp) {
2514 auto foldLowerOrUpperBound = [&forOp](bool lower) {
2515 // Check to see if each of the operands is the result of a constant. If
2516 // so, get the value. If not, ignore it.
2517 SmallVector<Attribute, 8> operandConstants;
2518 auto boundOperands =
2519 lower ? forOp.getLowerBoundOperands() : forOp.getUpperBoundOperands();
2520 for (auto operand : boundOperands) {
2521 Attribute operandCst;
2522 matchPattern(value: operand, pattern: m_Constant(bind_value: &operandCst));
2523 operandConstants.push_back(Elt: operandCst);
2524 }
2525
2526 AffineMap boundMap =
2527 lower ? forOp.getLowerBoundMap() : forOp.getUpperBoundMap();
2528 assert(boundMap.getNumResults() >= 1 &&
2529 "bound maps should have at least one result");
2530 SmallVector<Attribute, 4> foldedResults;
2531 if (failed(Result: boundMap.constantFold(operandConstants, results&: foldedResults)))
2532 return failure();
2533
2534 // Compute the max or min as applicable over the results.
2535 assert(!foldedResults.empty() && "bounds should have at least one result");
2536 auto maxOrMin = llvm::cast<IntegerAttr>(Val&: foldedResults[0]).getValue();
2537 for (unsigned i = 1, e = foldedResults.size(); i < e; i++) {
2538 auto foldedResult = llvm::cast<IntegerAttr>(Val&: foldedResults[i]).getValue();
2539 maxOrMin = lower ? llvm::APIntOps::smax(A: maxOrMin, B: foldedResult)
2540 : llvm::APIntOps::smin(A: maxOrMin, B: foldedResult);
2541 }
2542 lower ? forOp.setConstantLowerBound(maxOrMin.getSExtValue())
2543 : forOp.setConstantUpperBound(maxOrMin.getSExtValue());
2544 return success();
2545 };
2546
2547 // Try to fold the lower bound.
2548 bool folded = false;
2549 if (!forOp.hasConstantLowerBound())
2550 folded |= succeeded(Result: foldLowerOrUpperBound(/*lower=*/true));
2551
2552 // Try to fold the upper bound.
2553 if (!forOp.hasConstantUpperBound())
2554 folded |= succeeded(Result: foldLowerOrUpperBound(/*lower=*/false));
2555 return success(IsSuccess: folded);
2556}
2557
2558/// Returns constant trip count in trivial cases.
2559static std::optional<uint64_t> getTrivialConstantTripCount(AffineForOp forOp) {
2560 int64_t step = forOp.getStepAsInt();
2561 if (!forOp.hasConstantBounds() || step <= 0)
2562 return std::nullopt;
2563 int64_t lb = forOp.getConstantLowerBound();
2564 int64_t ub = forOp.getConstantUpperBound();
2565 return ub - lb <= 0 ? 0 : (ub - lb + step - 1) / step;
2566}
2567
2568/// Fold the empty loop.
2569static SmallVector<OpFoldResult> AffineForEmptyLoopFolder(AffineForOp forOp) {
2570 if (!llvm::hasSingleElement(C&: *forOp.getBody()))
2571 return {};
2572 if (forOp.getNumResults() == 0)
2573 return {};
2574 std::optional<uint64_t> tripCount = getTrivialConstantTripCount(forOp);
2575 if (tripCount == 0) {
2576 // The initial values of the iteration arguments would be the op's
2577 // results.
2578 return forOp.getInits();
2579 }
2580 SmallVector<Value, 4> replacements;
2581 auto yieldOp = cast<AffineYieldOp>(Val: forOp.getBody()->getTerminator());
2582 auto iterArgs = forOp.getRegionIterArgs();
2583 bool hasValDefinedOutsideLoop = false;
2584 bool iterArgsNotInOrder = false;
2585 for (unsigned i = 0, e = yieldOp->getNumOperands(); i < e; ++i) {
2586 Value val = yieldOp.getOperand(i);
2587 BlockArgument *iterArgIt = llvm::find(Range&: iterArgs, Val: val);
2588 // TODO: It should be possible to perform a replacement by computing the
2589 // last value of the IV based on the bounds and the step.
2590 if (val == forOp.getInductionVar())
2591 return {};
2592 if (iterArgIt == iterArgs.end()) {
2593 // `val` is defined outside of the loop.
2594 assert(forOp.isDefinedOutsideOfLoop(val) &&
2595 "must be defined outside of the loop");
2596 hasValDefinedOutsideLoop = true;
2597 replacements.push_back(Elt: val);
2598 } else {
2599 unsigned pos = std::distance(first: iterArgs.begin(), last: iterArgIt);
2600 if (pos != i)
2601 iterArgsNotInOrder = true;
2602 replacements.push_back(Elt: forOp.getInits()[pos]);
2603 }
2604 }
2605 // Bail out when the trip count is unknown and the loop returns any value
2606 // defined outside of the loop or any iterArg out of order.
2607 if (!tripCount.has_value() &&
2608 (hasValDefinedOutsideLoop || iterArgsNotInOrder))
2609 return {};
2610 // Bail out when the loop iterates more than once and it returns any iterArg
2611 // out of order.
2612 if (tripCount.has_value() && tripCount.value() >= 2 && iterArgsNotInOrder)
2613 return {};
2614 return llvm::to_vector_of<OpFoldResult>(Range&: replacements);
2615}
2616
2617/// Canonicalize the bounds of the given loop.
2618static LogicalResult canonicalizeLoopBounds(AffineForOp forOp) {
2619 SmallVector<Value, 4> lbOperands(forOp.getLowerBoundOperands());
2620 SmallVector<Value, 4> ubOperands(forOp.getUpperBoundOperands());
2621
2622 auto lbMap = forOp.getLowerBoundMap();
2623 auto ubMap = forOp.getUpperBoundMap();
2624 auto prevLbMap = lbMap;
2625 auto prevUbMap = ubMap;
2626
2627 composeAffineMapAndOperands(map: &lbMap, operands: &lbOperands);
2628 canonicalizeMapAndOperands(map: &lbMap, operands: &lbOperands);
2629 simplifyMinOrMaxExprWithOperands(map&: lbMap, operands: lbOperands, /*isMax=*/true);
2630 simplifyMinOrMaxExprWithOperands(map&: ubMap, operands: ubOperands, /*isMax=*/false);
2631 lbMap = removeDuplicateExprs(map: lbMap);
2632
2633 composeAffineMapAndOperands(map: &ubMap, operands: &ubOperands);
2634 canonicalizeMapAndOperands(map: &ubMap, operands: &ubOperands);
2635 ubMap = removeDuplicateExprs(map: ubMap);
2636
2637 // Any canonicalization change always leads to updated map(s).
2638 if (lbMap == prevLbMap && ubMap == prevUbMap)
2639 return failure();
2640
2641 if (lbMap != prevLbMap)
2642 forOp.setLowerBound(operands: lbOperands, map: lbMap);
2643 if (ubMap != prevUbMap)
2644 forOp.setUpperBound(operands: ubOperands, map: ubMap);
2645 return success();
2646}
2647
2648/// Returns true if the affine.for has zero iterations in trivial cases.
2649static bool hasTrivialZeroTripCount(AffineForOp op) {
2650 return getTrivialConstantTripCount(forOp: op) == 0;
2651}
2652
2653LogicalResult AffineForOp::fold(FoldAdaptor adaptor,
2654 SmallVectorImpl<OpFoldResult> &results) {
2655 bool folded = succeeded(Result: foldLoopBounds(forOp: *this));
2656 folded |= succeeded(Result: canonicalizeLoopBounds(forOp: *this));
2657 if (hasTrivialZeroTripCount(op: *this) && getNumResults() != 0) {
2658 // The initial values of the loop-carried variables (iter_args) are the
2659 // results of the op. But this must be avoided for an affine.for op that
2660 // does not return any results. Since ops that do not return results cannot
2661 // be folded away, we would enter an infinite loop of folds on the same
2662 // affine.for op.
2663 results.assign(in_start: getInits().begin(), in_end: getInits().end());
2664 folded = true;
2665 }
2666 SmallVector<OpFoldResult> foldResults = AffineForEmptyLoopFolder(forOp: *this);
2667 if (!foldResults.empty()) {
2668 results.assign(RHS: foldResults);
2669 folded = true;
2670 }
2671 return success(IsSuccess: folded);
2672}
2673
2674OperandRange AffineForOp::getEntrySuccessorOperands(RegionSuccessor successor) {
2675 assert(
2676 (successor.isOperation() || successor.getSuccessor() == &getRegion()) &&
2677 "invalid region point");
2678
2679 // The initial operands map to the loop arguments after the induction
2680 // variable or are forwarded to the results when the trip count is zero.
2681 return getInits();
2682}
2683
2684void AffineForOp::getSuccessorRegions(
2685 RegionBranchPoint point, SmallVectorImpl<RegionSuccessor> &regions) {
2686 assert((point.isParent() ||
2687 point.getTerminatorPredecessorOrNull()->getParentRegion() ==
2688 &getRegion()) &&
2689 "expected loop region");
2690 // The loop may typically branch back to its body or to the parent operation.
2691 // If the predecessor is the parent op and the trip count is known to be at
2692 // least one, branch into the body using the iterator arguments. And in cases
2693 // we know the trip count is zero, it can only branch back to its parent.
2694 std::optional<uint64_t> tripCount = getTrivialConstantTripCount(forOp: *this);
2695 if (tripCount.has_value()) {
2696 if (!point.isParent()) {
2697 // From the loop body, if the trip count is one, we can only branch back
2698 // to the parent.
2699 if (tripCount == 1) {
2700 regions.push_back(Elt: RegionSuccessor(getOperation()));
2701 return;
2702 }
2703 if (tripCount == 0)
2704 return;
2705 } else {
2706 if (tripCount.value() > 0) {
2707 regions.push_back(Elt: RegionSuccessor(&getRegion()));
2708 return;
2709 }
2710 if (tripCount.value() == 0) {
2711 regions.push_back(Elt: RegionSuccessor(getOperation()));
2712 return;
2713 }
2714 }
2715 }
2716
2717 // In all other cases, the loop may branch back to itself or the parent
2718 // operation.
2719 regions.push_back(Elt: RegionSuccessor(&getRegion()));
2720 regions.push_back(Elt: RegionSuccessor(getOperation()));
2721}
2722
2723ValueRange AffineForOp::getSuccessorInputs(RegionSuccessor successor) {
2724 if (successor.isOperation())
2725 return getResults();
2726 return getRegionIterArgs();
2727}
2728
2729AffineBound AffineForOp::getLowerBound() {
2730 return AffineBound(*this, getLowerBoundOperands(), getLowerBoundMap());
2731}
2732
2733AffineBound AffineForOp::getUpperBound() {
2734 return AffineBound(*this, getUpperBoundOperands(), getUpperBoundMap());
2735}
2736
2737void AffineForOp::setLowerBound(ValueRange lbOperands, AffineMap map) {
2738 assert(lbOperands.size() == map.getNumInputs());
2739 assert(map.getNumResults() >= 1 && "bound map has at least one result");
2740 getLowerBoundOperandsMutable().assign(values: lbOperands);
2741 setLowerBoundMap(map);
2742}
2743
2744void AffineForOp::setUpperBound(ValueRange ubOperands, AffineMap map) {
2745 assert(ubOperands.size() == map.getNumInputs());
2746 assert(map.getNumResults() >= 1 && "bound map has at least one result");
2747 getUpperBoundOperandsMutable().assign(values: ubOperands);
2748 setUpperBoundMap(map);
2749}
2750
2751bool AffineForOp::hasConstantLowerBound() {
2752 return getLowerBoundMap().isSingleConstant();
2753}
2754
2755bool AffineForOp::hasConstantUpperBound() {
2756 return getUpperBoundMap().isSingleConstant();
2757}
2758
2759int64_t AffineForOp::getConstantLowerBound() {
2760 return getLowerBoundMap().getSingleConstantResult();
2761}
2762
2763int64_t AffineForOp::getConstantUpperBound() {
2764 return getUpperBoundMap().getSingleConstantResult();
2765}
2766
2767void AffineForOp::setConstantLowerBound(int64_t value) {
2768 setLowerBound(lbOperands: {}, map: AffineMap::getConstantMap(val: value, context: getContext()));
2769}
2770
2771void AffineForOp::setConstantUpperBound(int64_t value) {
2772 setUpperBound(ubOperands: {}, map: AffineMap::getConstantMap(val: value, context: getContext()));
2773}
2774
2775AffineForOp::operand_range AffineForOp::getControlOperands() {
2776 return {operand_begin(), operand_begin() + getLowerBoundOperands().size() +
2777 getUpperBoundOperands().size()};
2778}
2779
2780bool AffineForOp::matchingBoundOperandList() {
2781 auto lbMap = getLowerBoundMap();
2782 auto ubMap = getUpperBoundMap();
2783 if (lbMap.getNumDims() != ubMap.getNumDims() ||
2784 lbMap.getNumSymbols() != ubMap.getNumSymbols())
2785 return false;
2786
2787 unsigned numOperands = lbMap.getNumInputs();
2788 for (unsigned i = 0, e = lbMap.getNumInputs(); i < e; i++) {
2789 // Compare Value 's.
2790 if (getOperand(i) != getOperand(i: numOperands + i))
2791 return false;
2792 }
2793 return true;
2794}
2795
2796SmallVector<Region *> AffineForOp::getLoopRegions() { return {&getRegion()}; }
2797
2798std::optional<SmallVector<Value>> AffineForOp::getLoopInductionVars() {
2799 return SmallVector<Value>{getInductionVar()};
2800}
2801
2802std::optional<SmallVector<OpFoldResult>> AffineForOp::getLoopLowerBounds() {
2803 if (!hasConstantLowerBound())
2804 return std::nullopt;
2805 OpBuilder b(getContext());
2806 return SmallVector<OpFoldResult>{
2807 OpFoldResult(b.getI64IntegerAttr(value: getConstantLowerBound()))};
2808}
2809
2810std::optional<SmallVector<OpFoldResult>> AffineForOp::getLoopSteps() {
2811 OpBuilder b(getContext());
2812 return SmallVector<OpFoldResult>{
2813 OpFoldResult(b.getI64IntegerAttr(value: getStepAsInt()))};
2814}
2815
2816std::optional<SmallVector<OpFoldResult>> AffineForOp::getLoopUpperBounds() {
2817 if (!hasConstantUpperBound())
2818 return {};
2819 OpBuilder b(getContext());
2820 return SmallVector<OpFoldResult>{
2821 OpFoldResult(b.getI64IntegerAttr(value: getConstantUpperBound()))};
2822}
2823
2824std::optional<APInt> AffineForOp::getStaticTripCount() {
2825 int64_t step = getStepAsInt();
2826 if (step <= 0)
2827 return std::nullopt;
2828
2829 if (hasConstantBounds()) {
2830 int64_t lb = getConstantLowerBound();
2831 int64_t ub = getConstantUpperBound();
2832 int64_t loopSpan = ub - lb;
2833 if (loopSpan < 0)
2834 loopSpan = 0;
2835 return APInt(64, llvm::divideCeilSigned(Numerator: loopSpan, Denominator: step));
2836 }
2837
2838 auto lbMap = getLowerBoundMap();
2839 auto ubMap = getUpperBoundMap();
2840 if (lbMap.getNumResults() != 1)
2841 return std::nullopt;
2842
2843 // Difference of each upper bound expression from the single lower bound
2844 // expression (divided by the step) provides the expressions for the trip
2845 // count map.
2846 AffineValueMap ubValueMap(ubMap, getUpperBoundOperands());
2847 AffineValueMap lbValueMap(lbMap, getLowerBoundOperands());
2848
2849 AffineValueMap tripCountValueMap;
2850 AffineValueMap::cartesianProductDifference(a: ubValueMap, b: lbValueMap,
2851 res: &tripCountValueMap);
2852
2853 // Take the min if all trip counts are constant.
2854 std::optional<uint64_t> tripCount;
2855 for (unsigned i = 0, e = tripCountValueMap.getNumResults(); i < e; ++i) {
2856 AffineExpr expr = tripCountValueMap.getResult(i).ceilDiv(v: step);
2857 if (auto constExpr = llvm::dyn_cast<AffineConstantExpr>(Val&: expr)) {
2858 uint64_t value = std::max<int64_t>(a: constExpr.getValue(), b: 0);
2859 if (tripCount.has_value())
2860 tripCount = std::min(a: *tripCount, b: value);
2861 else
2862 tripCount = value;
2863 } else {
2864 return std::nullopt;
2865 }
2866 }
2867
2868 if (tripCount.has_value())
2869 return APInt(64, *tripCount);
2870
2871 return std::nullopt;
2872}
2873
2874FailureOr<LoopLikeOpInterface> AffineForOp::replaceWithAdditionalYields(
2875 RewriterBase &rewriter, ValueRange newInitOperands,
2876 bool replaceInitOperandUsesInLoop,
2877 const NewYieldValuesFn &newYieldValuesFn) {
2878 // Create a new loop before the existing one, with the extra operands.
2879 OpBuilder::InsertionGuard g(rewriter);
2880 rewriter.setInsertionPoint(getOperation());
2881 auto inits = llvm::to_vector(Range: getInits());
2882 inits.append(in_start: newInitOperands.begin(), in_end: newInitOperands.end());
2883 AffineForOp newLoop = AffineForOp::create(
2884 builder&: rewriter, location: getLoc(), lbOperands: getLowerBoundOperands(), lbMap: getLowerBoundMap(),
2885 ubOperands: getUpperBoundOperands(), ubMap: getUpperBoundMap(), step: getStepAsInt(), iterArgs: inits);
2886 // Existing operands, results, and region arguments retain their positions;
2887 // only new loop-carried values are appended.
2888 newLoop->setDiscardableAttrs(getOperation()->getDiscardableAttrDictionary());
2889
2890 // Generate the new yield values and append them to the scf.yield operation.
2891 auto yieldOp = cast<AffineYieldOp>(Val: getBody()->getTerminator());
2892 ArrayRef<BlockArgument> newIterArgs =
2893 newLoop.getBody()->getArguments().take_back(N: newInitOperands.size());
2894 {
2895 OpBuilder::InsertionGuard g(rewriter);
2896 rewriter.setInsertionPoint(yieldOp);
2897 SmallVector<Value> newYieldedValues =
2898 newYieldValuesFn(rewriter, getLoc(), newIterArgs);
2899 assert(newInitOperands.size() == newYieldedValues.size() &&
2900 "expected as many new yield values as new iter operands");
2901 rewriter.modifyOpInPlace(root: yieldOp, callable: [&]() {
2902 yieldOp.getOperandsMutable().append(values: newYieldedValues);
2903 });
2904 }
2905
2906 // Move the loop body to the new op.
2907 rewriter.mergeBlocks(source: getBody(), dest: newLoop.getBody(),
2908 argValues: newLoop.getBody()->getArguments().take_front(
2909 N: getBody()->getNumArguments()));
2910
2911 if (replaceInitOperandUsesInLoop) {
2912 // Replace all uses of `newInitOperands` with the corresponding basic block
2913 // arguments.
2914 for (auto it : llvm::zip(t&: newInitOperands, u&: newIterArgs)) {
2915 rewriter.replaceUsesWithIf(from: std::get<0>(t&: it), to: std::get<1>(t&: it),
2916 functor: [&](OpOperand &use) {
2917 Operation *user = use.getOwner();
2918 return newLoop->isProperAncestor(other: user);
2919 });
2920 }
2921 }
2922
2923 // Replace the old loop.
2924 rewriter.replaceOp(op: getOperation(),
2925 newValues: newLoop->getResults().take_front(n: getNumResults()));
2926 return cast<LoopLikeOpInterface>(Val: newLoop.getOperation());
2927}
2928
2929Speculation::Speculatability AffineForOp::getSpeculatability() {
2930 // `affine.for (I = Start; I < End; I += 1)` terminates for all values of
2931 // Start and End.
2932 //
2933 // For Step != 1, the loop may not terminate. We can add more smarts here if
2934 // needed.
2935 return getStepAsInt() == 1 ? Speculation::RecursivelySpeculatable
2936 : Speculation::NotSpeculatable;
2937}
2938
2939/// Returns true if the provided value is the induction variable of a
2940/// AffineForOp.
2941bool mlir::affine::isAffineForInductionVar(Value val) {
2942 return getForInductionVarOwner(val) != AffineForOp();
2943}
2944
2945bool mlir::affine::isAffineParallelInductionVar(Value val) {
2946 return getAffineParallelInductionVarOwner(val) != nullptr;
2947}
2948
2949bool mlir::affine::isAffineInductionVar(Value val) {
2950 return isAffineForInductionVar(val) || isAffineParallelInductionVar(val);
2951}
2952
2953AffineForOp mlir::affine::getForInductionVarOwner(Value val) {
2954 auto ivArg = dyn_cast<BlockArgument>(Val&: val);
2955 if (!ivArg || !ivArg.getOwner() || !ivArg.getOwner()->getParent())
2956 return AffineForOp();
2957 if (auto forOp =
2958 ivArg.getOwner()->getParent()->getParentOfType<AffineForOp>())
2959 // Check to make sure `val` is the induction variable, not an iter_arg.
2960 return forOp.getInductionVar() == val ? forOp : AffineForOp();
2961 return AffineForOp();
2962}
2963
2964AffineParallelOp mlir::affine::getAffineParallelInductionVarOwner(Value val) {
2965 auto ivArg = dyn_cast<BlockArgument>(Val&: val);
2966 if (!ivArg || !ivArg.getOwner())
2967 return nullptr;
2968 Operation *containingOp = ivArg.getOwner()->getParentOp();
2969 auto parallelOp = dyn_cast_if_present<AffineParallelOp>(Val: containingOp);
2970 if (parallelOp && llvm::is_contained(Range: parallelOp.getIVs(), Element: val))
2971 return parallelOp;
2972 return nullptr;
2973}
2974
2975/// Extracts the induction variables from a list of AffineForOps and returns
2976/// them.
2977void mlir::affine::extractForInductionVars(ArrayRef<AffineForOp> forInsts,
2978 SmallVectorImpl<Value> *ivs) {
2979 ivs->reserve(N: forInsts.size());
2980 for (auto forInst : forInsts)
2981 ivs->push_back(Elt: forInst.getInductionVar());
2982}
2983
2984void mlir::affine::extractInductionVars(ArrayRef<mlir::Operation *> affineOps,
2985 SmallVectorImpl<mlir::Value> &ivs) {
2986 ivs.reserve(N: affineOps.size());
2987 for (Operation *op : affineOps) {
2988 // Add constraints from forOp's bounds.
2989 if (auto forOp = dyn_cast<AffineForOp>(Val: op))
2990 ivs.push_back(Elt: forOp.getInductionVar());
2991 else if (auto parallelOp = dyn_cast<AffineParallelOp>(Val: op))
2992 for (size_t i = 0; i < parallelOp.getBody()->getNumArguments(); i++)
2993 ivs.push_back(Elt: parallelOp.getBody()->getArgument(i));
2994 }
2995}
2996
2997/// Builds an affine loop nest, using "loopCreatorFn" to create individual loop
2998/// operations.
2999template <typename BoundListTy, typename LoopCreatorTy>
3000static void buildAffineLoopNestImpl(
3001 OpBuilder &builder, Location loc, BoundListTy lbs, BoundListTy ubs,
3002 ArrayRef<int64_t> steps,
3003 function_ref<void(OpBuilder &, Location, ValueRange)> bodyBuilderFn,
3004 LoopCreatorTy &&loopCreatorFn) {
3005 assert(lbs.size() == ubs.size() && "Mismatch in number of arguments");
3006 assert(lbs.size() == steps.size() && "Mismatch in number of arguments");
3007
3008 // If there are no loops to be constructed, construct the body anyway.
3009 OpBuilder::InsertionGuard guard(builder);
3010 if (lbs.empty()) {
3011 if (bodyBuilderFn)
3012 bodyBuilderFn(builder, loc, ValueRange());
3013 return;
3014 }
3015
3016 // Create the loops iteratively and store the induction variables.
3017 SmallVector<Value, 4> ivs;
3018 ivs.reserve(N: lbs.size());
3019 for (unsigned i = 0, e = lbs.size(); i < e; ++i) {
3020 // Callback for creating the loop body, always creates the terminator.
3021 auto loopBody = [&](OpBuilder &nestedBuilder, Location nestedLoc, Value iv,
3022 ValueRange iterArgs) {
3023 ivs.push_back(Elt: iv);
3024 // In the innermost loop, call the body builder.
3025 if (i == e - 1 && bodyBuilderFn) {
3026 OpBuilder::InsertionGuard nestedGuard(nestedBuilder);
3027 bodyBuilderFn(nestedBuilder, nestedLoc, ivs);
3028 }
3029 AffineYieldOp::create(builder&: nestedBuilder, location: nestedLoc);
3030 };
3031
3032 // Delegate actual loop creation to the callback in order to dispatch
3033 // between constant- and variable-bound loops.
3034 auto loop = loopCreatorFn(builder, loc, lbs[i], ubs[i], steps[i], loopBody);
3035 builder.setInsertionPointToStart(loop.getBody());
3036 }
3037}
3038
3039/// Creates an affine loop from the bounds known to be constants.
3040static AffineForOp
3041buildAffineLoopFromConstants(OpBuilder &builder, Location loc, int64_t lb,
3042 int64_t ub, int64_t step,
3043 AffineForOp::BodyBuilderFn bodyBuilderFn) {
3044 return AffineForOp::create(builder, location: loc, lowerBound: lb, upperBound: ub, step,
3045 /*iterArgs=*/ValueRange(), bodyBuilder: bodyBuilderFn);
3046}
3047
3048/// Creates an affine loop from the bounds that may or may not be constants.
3049static AffineForOp
3050buildAffineLoopFromValues(OpBuilder &builder, Location loc, Value lb, Value ub,
3051 int64_t step,
3052 AffineForOp::BodyBuilderFn bodyBuilderFn) {
3053 std::optional<int64_t> lbConst = getConstantIntValue(ofr: lb);
3054 std::optional<int64_t> ubConst = getConstantIntValue(ofr: ub);
3055 if (lbConst && ubConst)
3056 return buildAffineLoopFromConstants(builder, loc, lb: lbConst.value(),
3057 ub: ubConst.value(), step, bodyBuilderFn);
3058 return AffineForOp::create(builder, location: loc, lbOperands: lb, lbMap: builder.getDimIdentityMap(), ubOperands: ub,
3059 ubMap: builder.getDimIdentityMap(), step,
3060 /*iterArgs=*/ValueRange(), bodyBuilder: bodyBuilderFn);
3061}
3062
3063void mlir::affine::buildAffineLoopNest(
3064 OpBuilder &builder, Location loc, ArrayRef<int64_t> lbs,
3065 ArrayRef<int64_t> ubs, ArrayRef<int64_t> steps,
3066 function_ref<void(OpBuilder &, Location, ValueRange)> bodyBuilderFn) {
3067 buildAffineLoopNestImpl(builder, loc, lbs, ubs, steps, bodyBuilderFn,
3068 loopCreatorFn&: buildAffineLoopFromConstants);
3069}
3070
3071void mlir::affine::buildAffineLoopNest(
3072 OpBuilder &builder, Location loc, ValueRange lbs, ValueRange ubs,
3073 ArrayRef<int64_t> steps,
3074 function_ref<void(OpBuilder &, Location, ValueRange)> bodyBuilderFn) {
3075 buildAffineLoopNestImpl(builder, loc, lbs, ubs, steps, bodyBuilderFn,
3076 loopCreatorFn&: buildAffineLoopFromValues);
3077}
3078
3079//===----------------------------------------------------------------------===//
3080// AffineIfOp
3081//===----------------------------------------------------------------------===//
3082
3083namespace {
3084/// Remove else blocks that have nothing other than a zero value yield.
3085struct SimplifyDeadElse : public OpRewritePattern<AffineIfOp> {
3086 using OpRewritePattern<AffineIfOp>::OpRewritePattern;
3087
3088 LogicalResult matchAndRewrite(AffineIfOp ifOp,
3089 PatternRewriter &rewriter) const override {
3090 if (ifOp.getElseRegion().empty() ||
3091 !llvm::hasSingleElement(C&: *ifOp.getElseBlock()) || ifOp.getNumResults())
3092 return failure();
3093
3094 rewriter.startOpModification(op: ifOp);
3095 rewriter.eraseBlock(block: ifOp.getElseBlock());
3096 rewriter.finalizeOpModification(op: ifOp);
3097 return success();
3098 }
3099};
3100
3101/// Removes affine.if cond if the condition is always true or false in certain
3102/// trivial cases. Promotes the then/else block in the parent operation block.
3103struct AlwaysTrueOrFalseIf : public OpRewritePattern<AffineIfOp> {
3104 using OpRewritePattern<AffineIfOp>::OpRewritePattern;
3105
3106 LogicalResult matchAndRewrite(AffineIfOp op,
3107 PatternRewriter &rewriter) const override {
3108
3109 auto isTriviallyFalse = [](IntegerSet iSet) {
3110 return iSet.isEmptyIntegerSet();
3111 };
3112
3113 auto isTriviallyTrue = [](IntegerSet iSet) {
3114 return (iSet.getNumEqualities() == 1 && iSet.getNumInequalities() == 0 &&
3115 iSet.getConstraint(idx: 0) == 0);
3116 };
3117
3118 IntegerSet affineIfConditions = op.getIntegerSet();
3119 Block *blockToMove;
3120 if (isTriviallyFalse(affineIfConditions)) {
3121 // The absence, or equivalently, the emptiness of the else region need not
3122 // be checked when affine.if is returning results because if an affine.if
3123 // operation is returning results, it always has a non-empty else region.
3124 if (op.getNumResults() == 0 && !op.hasElse()) {
3125 // If the else region is absent, or equivalently, empty, remove the
3126 // affine.if operation (which is not returning any results).
3127 rewriter.eraseOp(op);
3128 return success();
3129 }
3130 blockToMove = op.getElseBlock();
3131 } else if (isTriviallyTrue(affineIfConditions)) {
3132 blockToMove = op.getThenBlock();
3133 } else {
3134 return failure();
3135 }
3136 Operation *blockToMoveTerminator = blockToMove->getTerminator();
3137 // Promote the "blockToMove" block to the parent operation block between the
3138 // prologue and epilogue of "op".
3139 rewriter.inlineBlockBefore(source: blockToMove, op);
3140 // Replace the "op" operation with the operands of the
3141 // "blockToMoveTerminator" operation. Note that "blockToMoveTerminator" is
3142 // the affine.yield operation present in the "blockToMove" block. It has no
3143 // operands when affine.if is not returning results and therefore, in that
3144 // case, replaceOp just erases "op". When affine.if is not returning
3145 // results, the affine.yield operation can be omitted. It gets inserted
3146 // implicitly.
3147 rewriter.replaceOp(op, newValues: blockToMoveTerminator->getOperands());
3148 // Erase the "blockToMoveTerminator" operation since it is now in the parent
3149 // operation block, which already has its own terminator.
3150 rewriter.eraseOp(op: blockToMoveTerminator);
3151 return success();
3152 }
3153};
3154} // namespace
3155
3156/// AffineIfOp has two regions -- `then` and `else`. The flow of data should be
3157/// as follows: AffineIfOp -> `then`/`else` -> AffineIfOp
3158void AffineIfOp::getSuccessorRegions(
3159 RegionBranchPoint point, SmallVectorImpl<RegionSuccessor> &regions) {
3160 // If the predecessor is an AffineIfOp, then branching into both `then` and
3161 // `else` region is valid.
3162 if (point.isParent()) {
3163 regions.reserve(N: 2);
3164 regions.push_back(Elt: RegionSuccessor(&getThenRegion()));
3165 // If the "else" region is empty, branch bach into parent.
3166 if (getElseRegion().empty()) {
3167 regions.push_back(Elt: RegionSuccessor(getOperation()));
3168 } else {
3169 regions.push_back(Elt: RegionSuccessor(&getElseRegion()));
3170 }
3171 return;
3172 }
3173
3174 // If the predecessor is the `else`/`then` region, then branching into parent
3175 // op is valid.
3176 regions.push_back(Elt: RegionSuccessor(getOperation()));
3177}
3178
3179ValueRange AffineIfOp::getSuccessorInputs(RegionSuccessor successor) {
3180 if (successor.isOperation())
3181 return getResults();
3182 if (successor == &getThenRegion())
3183 return getThenRegion().getArguments();
3184 if (successor == &getElseRegion())
3185 return getElseRegion().getArguments();
3186 llvm_unreachable("invalid region successor");
3187}
3188
3189LogicalResult AffineIfOp::verify() {
3190 // Verify that we have a condition attribute.
3191 // FIXME: This should be specified in the arguments list in ODS.
3192 auto conditionAttr = getConditionAttr();
3193 if (!conditionAttr)
3194 return emitOpError(message: "requires an integer set attribute named 'condition'");
3195
3196 // Verify that there are enough operands for the condition.
3197 IntegerSet condition = conditionAttr.getValue();
3198 if (getNumOperands() != condition.getNumInputs())
3199 return emitOpError(message: "operand count and condition integer set dimension and "
3200 "symbol count must match");
3201
3202 // Verify that the operands are valid dimension/symbols.
3203 if (failed(Result: verifyDimAndSymbolIdentifiers(op&: *this, operands: getOperands(),
3204 numDims: condition.getNumDims())))
3205 return failure();
3206
3207 return success();
3208}
3209
3210ParseResult AffineIfOp::parse(OpAsmParser &parser, OperationState &result) {
3211 // Parse the condition attribute set.
3212 IntegerSetAttr conditionAttr;
3213 unsigned numDims;
3214 if (parser.parseAttribute(result&: conditionAttr,
3215 attrName: AffineIfOp::getConditionAttrStrName(),
3216 attrs&: result.attributes) ||
3217 parseDimAndSymbolList(parser, operands&: result.operands, numDims))
3218 return failure();
3219
3220 // Verify the condition operands.
3221 auto set = conditionAttr.getValue();
3222 if (set.getNumDims() != numDims)
3223 return parser.emitError(
3224 loc: parser.getNameLoc(),
3225 message: "dim operand count and integer set dim count must match");
3226 if (numDims + set.getNumSymbols() != result.operands.size())
3227 return parser.emitError(
3228 loc: parser.getNameLoc(),
3229 message: "symbol operand count and integer set symbol count must match");
3230
3231 if (parser.parseOptionalArrowTypeList(result&: result.types))
3232 return failure();
3233
3234 // Create the regions for 'then' and 'else'. The latter must be created even
3235 // if it remains empty for the validity of the operation.
3236 result.regions.reserve(N: 2);
3237 Region *thenRegion = result.addRegion();
3238 Region *elseRegion = result.addRegion();
3239
3240 // Parse the 'then' region.
3241 if (parser.parseRegion(region&: *thenRegion, arguments: {}, enableNameShadowing: {}))
3242 return failure();
3243 AffineIfOp::ensureTerminator(region&: *thenRegion, builder&: parser.getBuilder(),
3244 loc: result.location);
3245
3246 // If we find an 'else' keyword then parse the 'else' region.
3247 if (!parser.parseOptionalKeyword(keyword: "else")) {
3248 if (parser.parseRegion(region&: *elseRegion, arguments: {}, enableNameShadowing: {}))
3249 return failure();
3250 AffineIfOp::ensureTerminator(region&: *elseRegion, builder&: parser.getBuilder(),
3251 loc: result.location);
3252 }
3253
3254 // Parse the optional attribute list.
3255 if (parser.parseOptionalAttrDict(result&: result.attributes))
3256 return failure();
3257
3258 return success();
3259}
3260
3261void AffineIfOp::print(OpAsmPrinter &p) {
3262 auto conditionAttr = getConditionAttr();
3263 p << " " << conditionAttr;
3264 printDimAndSymbolList(begin: operand_begin(), end: operand_end(),
3265 numDims: conditionAttr.getValue().getNumDims(), printer&: p);
3266 p.printOptionalArrowTypeList(types: getResultTypes());
3267 p << ' ';
3268 p.printRegion(blocks&: getThenRegion(), /*printEntryBlockArgs=*/false,
3269 /*printBlockTerminators=*/getNumResults());
3270
3271 // Print the 'else' regions if it has any blocks.
3272 auto &elseRegion = this->getElseRegion();
3273 if (!elseRegion.empty()) {
3274 p << " else ";
3275 p.printRegion(blocks&: elseRegion,
3276 /*printEntryBlockArgs=*/false,
3277 /*printBlockTerminators=*/getNumResults());
3278 }
3279
3280 // Print the attribute list.
3281 p.printOptionalAttrDict(attrs: (*this)->getDiscardableAttrDictionary().getValue());
3282}
3283
3284IntegerSet AffineIfOp::getIntegerSet() { return getConditionAttr().getValue(); }
3285
3286void AffineIfOp::setIntegerSet(IntegerSet newSet) {
3287 setConditionAttr(IntegerSetAttr::get(value: newSet));
3288}
3289
3290void AffineIfOp::setConditional(IntegerSet set, ValueRange operands) {
3291 setIntegerSet(set);
3292 (*this)->setOperands(operands);
3293}
3294
3295void AffineIfOp::build(OpBuilder &builder, OperationState &result,
3296 TypeRange resultTypes, IntegerSet set, ValueRange args,
3297 bool withElseRegion) {
3298 assert(resultTypes.empty() || withElseRegion);
3299 OpBuilder::InsertionGuard guard(builder);
3300
3301 result.addTypes(newTypes&: resultTypes);
3302 result.addOperands(newOperands: args);
3303 result.addAttribute(name: getConditionAttrStrName(), attr: IntegerSetAttr::get(value: set));
3304
3305 Region *thenRegion = result.addRegion();
3306 builder.createBlock(parent: thenRegion);
3307 if (resultTypes.empty())
3308 AffineIfOp::ensureTerminator(region&: *thenRegion, builder, loc: result.location);
3309
3310 Region *elseRegion = result.addRegion();
3311 if (withElseRegion) {
3312 builder.createBlock(parent: elseRegion);
3313 if (resultTypes.empty())
3314 AffineIfOp::ensureTerminator(region&: *elseRegion, builder, loc: result.location);
3315 }
3316}
3317
3318void AffineIfOp::build(OpBuilder &builder, OperationState &result,
3319 IntegerSet set, ValueRange args, bool withElseRegion) {
3320 AffineIfOp::build(builder, result, /*resultTypes=*/{}, set, args,
3321 withElseRegion);
3322}
3323
3324/// Compose any affine.apply ops feeding into `operands` of the integer set
3325/// `set` by composing the maps of such affine.apply ops with the integer
3326/// set constraints.
3327static void composeSetAndOperands(IntegerSet &set,
3328 SmallVectorImpl<Value> &operands,
3329 bool composeAffineMin = false) {
3330 // We will simply reuse the API of the map composition by viewing the LHSs of
3331 // the equalities and inequalities of `set` as the affine exprs of an affine
3332 // map. Convert to equivalent map, compose, and convert back to set.
3333 auto map = AffineMap::get(dimCount: set.getNumDims(), symbolCount: set.getNumSymbols(),
3334 results: set.getConstraints(), context: set.getContext());
3335 // Check if any composition is possible.
3336 if (llvm::none_of(Range&: operands,
3337 P: [](Value v) { return v.getDefiningOp<AffineApplyOp>(); }))
3338 return;
3339
3340 composeAffineMapAndOperands(map: &map, operands: &operands, composeAffineMin);
3341 set = IntegerSet::get(dimCount: map.getNumDims(), symbolCount: map.getNumSymbols(), constraints: map.getResults(),
3342 eqFlags: set.getEqFlags());
3343}
3344
3345/// Canonicalize an affine if op's conditional (integer set + operands).
3346LogicalResult AffineIfOp::fold(FoldAdaptor, SmallVectorImpl<OpFoldResult> &) {
3347 auto set = getIntegerSet();
3348 SmallVector<Value, 4> operands(getOperands());
3349 composeSetAndOperands(set, operands);
3350 canonicalizeSetAndOperands(set: &set, operands: &operands);
3351
3352 // Check if the canonicalization or composition led to any change.
3353 if (getIntegerSet() == set && llvm::equal(LRange&: operands, RRange: getOperands()))
3354 return failure();
3355
3356 setConditional(set, operands);
3357 return success();
3358}
3359
3360void AffineIfOp::getCanonicalizationPatterns(RewritePatternSet &results,
3361 MLIRContext *context) {
3362 results.add<SimplifyDeadElse, AlwaysTrueOrFalseIf>(arg&: context);
3363}
3364
3365/// Adds the optional `alignment` attribute to `result`, if one is given.
3366static void addAlignmentAttr(OpBuilder &builder, OperationState &result,
3367 StringAttr attrName, llvm::MaybeAlign alignment) {
3368 if (alignment)
3369 result.addAttribute(name: attrName,
3370 attr: builder.getI64IntegerAttr(value: alignment->value()));
3371}
3372
3373//===----------------------------------------------------------------------===//
3374// AffineLoadOp
3375//===----------------------------------------------------------------------===//
3376
3377void AffineLoadOp::build(OpBuilder &builder, OperationState &result,
3378 AffineMap map, ValueRange operands,
3379 llvm::MaybeAlign alignment) {
3380 assert(operands.size() == 1 + map.getNumInputs() && "inconsistent operands");
3381 result.addOperands(newOperands: operands);
3382 if (map)
3383 result.addAttribute(name: getMapAttrStrName(), attr: AffineMapAttr::get(value: map));
3384 addAlignmentAttr(builder, result, attrName: getAlignmentAttrName(name: result.name),
3385 alignment);
3386 auto memrefType = llvm::cast<MemRefType>(Val: operands[0].getType());
3387 result.types.push_back(Elt: memrefType.getElementType());
3388}
3389
3390void AffineLoadOp::build(OpBuilder &builder, OperationState &result,
3391 Value memref, AffineMap map, ValueRange mapOperands,
3392 llvm::MaybeAlign alignment) {
3393 assert(map.getNumInputs() == mapOperands.size() && "inconsistent index info");
3394 result.addOperands(newOperands: memref);
3395 result.addOperands(newOperands: mapOperands);
3396 auto memrefType = llvm::cast<MemRefType>(Val: memref.getType());
3397 result.addAttribute(name: getMapAttrStrName(), attr: AffineMapAttr::get(value: map));
3398 addAlignmentAttr(builder, result, attrName: getAlignmentAttrName(name: result.name),
3399 alignment);
3400 result.types.push_back(Elt: memrefType.getElementType());
3401}
3402
3403void AffineLoadOp::build(OpBuilder &builder, OperationState &result,
3404 Value memref, ValueRange indices,
3405 llvm::MaybeAlign alignment) {
3406 auto memrefType = llvm::cast<MemRefType>(Val: memref.getType());
3407 int64_t rank = memrefType.getRank();
3408 // Create identity map for memrefs with at least one dimension or () -> ()
3409 // for zero-dimensional memrefs.
3410 auto map =
3411 rank ? builder.getMultiDimIdentityMap(rank) : builder.getEmptyAffineMap();
3412 build(builder, result, memref, map, mapOperands: indices, alignment);
3413}
3414
3415ParseResult AffineLoadOp::parse(OpAsmParser &parser, OperationState &result) {
3416 auto &builder = parser.getBuilder();
3417 auto indexTy = builder.getIndexType();
3418
3419 MemRefType type;
3420 OpAsmParser::UnresolvedOperand memrefInfo;
3421 AffineMapAttr mapAttr;
3422 SmallVector<OpAsmParser::UnresolvedOperand, 1> mapOperands;
3423 return failure(
3424 IsFailure: parser.parseOperand(result&: memrefInfo) ||
3425 parser.parseAffineMapOfSSAIds(operands&: mapOperands, map&: mapAttr,
3426 attrName: AffineLoadOp::getMapAttrStrName(),
3427 attrs&: result.attributes) ||
3428 parser.parseOptionalAttrDict(result&: result.attributes) ||
3429 parser.parseColonType(result&: type) ||
3430 parser.resolveOperand(operand: memrefInfo, type, result&: result.operands) ||
3431 parser.resolveOperands(operands&: mapOperands, type: indexTy, result&: result.operands) ||
3432 parser.addTypeToList(type: type.getElementType(), result&: result.types));
3433}
3434
3435void AffineLoadOp::print(OpAsmPrinter &p) {
3436 p << " " << getMemRef() << '[';
3437 if (AffineMapAttr mapAttr = getMapAttr())
3438 p.printAffineMapOfSSAIds(mapAttr, operands: getMapOperands());
3439 p << ']';
3440 SmallVector<NamedAttribute> attrs((*this)->getDiscardableAttrs());
3441 if (IntegerAttr alignment = getAlignmentAttr())
3442 attrs.emplace_back(Args: getAlignmentAttrName(), Args&: alignment);
3443 llvm::sort(C&: attrs);
3444 p.printOptionalAttrDict(attrs);
3445 p << " : " << getMemRefType();
3446}
3447
3448/// Verify common indexing invariants of affine.load, affine.store,
3449/// affine.vector_load and affine.vector_store.
3450template <typename AffineMemOpTy>
3451static LogicalResult
3452verifyMemoryOpIndexing(AffineMemOpTy op, AffineMapAttr mapAttr,
3453 Operation::operand_range mapOperands,
3454 MemRefType memrefType, unsigned numIndexOperands) {
3455 AffineMap map = mapAttr.getValue();
3456 if (map.getNumResults() != memrefType.getRank())
3457 return op->emitOpError("affine map num results must equal memref rank");
3458 if (map.getNumInputs() != numIndexOperands)
3459 return op->emitOpError("expects as many subscripts as affine map inputs");
3460
3461 for (auto idx : mapOperands) {
3462 if (!idx.getType().isIndex())
3463 return op->emitOpError("index to load must have 'index' type");
3464 }
3465 if (failed(verifyDimAndSymbolIdentifiers(op, mapOperands, map.getNumDims())))
3466 return failure();
3467
3468 return success();
3469}
3470
3471LogicalResult AffineLoadOp::verify() {
3472 auto memrefType = getMemRefType();
3473 if (getType() != memrefType.getElementType())
3474 return emitOpError(message: "result type must match element type of memref");
3475
3476 if (failed(Result: verifyMemoryOpIndexing(op: *this, mapAttr: getMapAttr(), mapOperands: getMapOperands(),
3477 memrefType,
3478 /*numIndexOperands=*/getNumOperands() - 1)))
3479 return failure();
3480
3481 return success();
3482}
3483
3484void AffineLoadOp::getCanonicalizationPatterns(RewritePatternSet &results,
3485 MLIRContext *context) {
3486 results.add<SimplifyAffineOp<AffineLoadOp>>(arg&: context);
3487}
3488
3489OpFoldResult AffineLoadOp::fold(FoldAdaptor adaptor) {
3490 /// load(memrefcast) -> load
3491 if (succeeded(Result: memref::foldMemRefCast(op: *this)))
3492 return getResult();
3493
3494 // Fold load from a global constant memref.
3495 auto getGlobalOp = getMemref().getDefiningOp<memref::GetGlobalOp>();
3496 if (!getGlobalOp)
3497 return {};
3498 // Get to the memref.global defining the symbol.
3499 auto global = SymbolTable::lookupNearestSymbolFrom<memref::GlobalOp>(
3500 from: getGlobalOp, symbol: getGlobalOp.getNameAttr());
3501 if (!global)
3502 return {};
3503
3504 // Check if the global memref is a constant.
3505 auto cstAttr =
3506 dyn_cast_or_null<DenseElementsAttr>(Val: global.getConstantInitValue());
3507 if (!cstAttr)
3508 return {};
3509 // If it's a splat constant, we can fold irrespective of indices.
3510 if (auto splatAttr = dyn_cast<SplatElementsAttr>(Val&: cstAttr))
3511 return splatAttr.getSplatValue<Attribute>();
3512 // Otherwise, we can fold only if we know the indices.
3513 if (!getAffineMap().isConstant())
3514 return {};
3515 auto indices =
3516 llvm::map_to_vector<4>(C: getAffineMap().getConstantResults(),
3517 F: [](int64_t v) -> uint64_t { return v; });
3518 ElementsAttr elementsAttr = cstAttr;
3519 if (!elementsAttr.isValidIndex(index: indices))
3520 return {};
3521 return elementsAttr.getValues<Attribute>()[indices];
3522}
3523
3524//===----------------------------------------------------------------------===//
3525// AffineStoreOp
3526//===----------------------------------------------------------------------===//
3527
3528void AffineStoreOp::build(OpBuilder &builder, OperationState &result,
3529 Value valueToStore, Value memref, AffineMap map,
3530 ValueRange mapOperands, llvm::MaybeAlign alignment) {
3531 assert(map.getNumInputs() == mapOperands.size() && "inconsistent index info");
3532 result.addOperands(newOperands: valueToStore);
3533 result.addOperands(newOperands: memref);
3534 result.addOperands(newOperands: mapOperands);
3535 result.getOrAddProperties<Properties>().map = AffineMapAttr::get(value: map);
3536 addAlignmentAttr(builder, result, attrName: getAlignmentAttrName(name: result.name),
3537 alignment);
3538}
3539
3540// Use identity map.
3541void AffineStoreOp::build(OpBuilder &builder, OperationState &result,
3542 Value valueToStore, Value memref, ValueRange indices,
3543 llvm::MaybeAlign alignment) {
3544 auto memrefType = llvm::cast<MemRefType>(Val: memref.getType());
3545 int64_t rank = memrefType.getRank();
3546 // Create identity map for memrefs with at least one dimension or () -> ()
3547 // for zero-dimensional memrefs.
3548 auto map =
3549 rank ? builder.getMultiDimIdentityMap(rank) : builder.getEmptyAffineMap();
3550 build(builder, result, valueToStore, memref, map, mapOperands: indices, alignment);
3551}
3552
3553ParseResult AffineStoreOp::parse(OpAsmParser &parser, OperationState &result) {
3554 auto indexTy = parser.getBuilder().getIndexType();
3555
3556 MemRefType type;
3557 OpAsmParser::UnresolvedOperand storeValueInfo;
3558 OpAsmParser::UnresolvedOperand memrefInfo;
3559 AffineMapAttr mapAttr;
3560 SmallVector<OpAsmParser::UnresolvedOperand, 1> mapOperands;
3561 return failure(IsFailure: parser.parseOperand(result&: storeValueInfo) || parser.parseComma() ||
3562 parser.parseOperand(result&: memrefInfo) ||
3563 parser.parseAffineMapOfSSAIds(
3564 operands&: mapOperands, map&: mapAttr, attrName: AffineStoreOp::getMapAttrStrName(),
3565 attrs&: result.attributes) ||
3566 parser.parseOptionalAttrDict(result&: result.attributes) ||
3567 parser.parseColonType(result&: type) ||
3568 parser.resolveOperand(operand: storeValueInfo, type: type.getElementType(),
3569 result&: result.operands) ||
3570 parser.resolveOperand(operand: memrefInfo, type, result&: result.operands) ||
3571 parser.resolveOperands(operands&: mapOperands, type: indexTy, result&: result.operands));
3572}
3573
3574void AffineStoreOp::print(OpAsmPrinter &p) {
3575 p << " " << getValueToStore();
3576 p << ", " << getMemRef() << '[';
3577 if (AffineMapAttr mapAttr = getMapAttr())
3578 p.printAffineMapOfSSAIds(mapAttr, operands: getMapOperands());
3579 p << ']';
3580 SmallVector<NamedAttribute> attrs((*this)->getDiscardableAttrs());
3581 if (IntegerAttr alignment = getAlignmentAttr())
3582 attrs.emplace_back(Args: getAlignmentAttrName(), Args&: alignment);
3583 llvm::sort(C&: attrs);
3584 p.printOptionalAttrDict(attrs);
3585 p << " : " << getMemRefType();
3586}
3587
3588LogicalResult AffineStoreOp::verify() {
3589 // The value to store must have the same type as memref element type.
3590 auto memrefType = getMemRefType();
3591 if (getValueToStore().getType() != memrefType.getElementType())
3592 return emitOpError(
3593 message: "value to store must have the same type as memref element type");
3594
3595 if (failed(Result: verifyMemoryOpIndexing(op: *this, mapAttr: getMapAttr(), mapOperands: getMapOperands(),
3596 memrefType,
3597 /*numIndexOperands=*/getNumOperands() - 2)))
3598 return failure();
3599
3600 return success();
3601}
3602
3603void AffineStoreOp::getCanonicalizationPatterns(RewritePatternSet &results,
3604 MLIRContext *context) {
3605 results.add<SimplifyAffineOp<AffineStoreOp>>(arg&: context);
3606}
3607
3608LogicalResult AffineStoreOp::fold(FoldAdaptor adaptor,
3609 SmallVectorImpl<OpFoldResult> &results) {
3610 /// store(memrefcast) -> store
3611 return memref::foldMemRefCast(op: *this, inner: getValueToStore());
3612}
3613
3614//===----------------------------------------------------------------------===//
3615// AffineMinMaxOpBase
3616//===----------------------------------------------------------------------===//
3617
3618template <typename T>
3619static LogicalResult verifyAffineMinMaxOp(T op) {
3620 // Verify that operand count matches affine map dimension and symbol count.
3621 if (op.getNumOperands() !=
3622 op.getMap().getNumDims() + op.getMap().getNumSymbols())
3623 return op.emitOpError(
3624 "operand count and affine map dimension and symbol count must match");
3625
3626 if (op.getMap().getNumResults() == 0)
3627 return op.emitOpError("affine map expect at least one result");
3628 return success();
3629}
3630
3631template <typename T>
3632static void printAffineMinMaxOp(OpAsmPrinter &p, T op) {
3633 p << ' ' << op.getMapAttr();
3634 auto operands = op.getOperands();
3635 unsigned numDims = op.getMap().getNumDims();
3636 p << '(' << operands.take_front(numDims) << ')';
3637
3638 if (operands.size() != numDims)
3639 p << '[' << operands.drop_front(numDims) << ']';
3640 p.printOptionalAttrDict(op->getDiscardableAttrDictionary().getValue());
3641}
3642
3643template <typename T>
3644static ParseResult parseAffineMinMaxOp(OpAsmParser &parser,
3645 OperationState &result) {
3646 auto &builder = parser.getBuilder();
3647 auto indexType = builder.getIndexType();
3648 SmallVector<OpAsmParser::UnresolvedOperand, 8> dimInfos;
3649 SmallVector<OpAsmParser::UnresolvedOperand, 8> symInfos;
3650 AffineMapAttr mapAttr;
3651 return failure(
3652 parser.parseAttribute(mapAttr, T::getMapAttrStrName(),
3653 result.attributes) ||
3654 parser.parseOperandList(result&: dimInfos, delimiter: OpAsmParser::Delimiter::Paren) ||
3655 parser.parseOperandList(result&: symInfos,
3656 delimiter: OpAsmParser::Delimiter::OptionalSquare) ||
3657 parser.parseOptionalAttrDict(result&: result.attributes) ||
3658 parser.resolveOperands(operands&: dimInfos, type: indexType, result&: result.operands) ||
3659 parser.resolveOperands(operands&: symInfos, type: indexType, result&: result.operands) ||
3660 parser.addTypeToList(type: indexType, result&: result.types));
3661}
3662
3663/// Fold an affine min or max operation with the given operands. The operand
3664/// list may contain nulls, which are interpreted as the operand not being a
3665/// constant.
3666template <typename T>
3667static OpFoldResult foldMinMaxOp(T op, ArrayRef<Attribute> operands) {
3668 static_assert(llvm::is_one_of<T, AffineMinOp, AffineMaxOp>::value,
3669 "expected affine min or max op");
3670
3671 // Fold the affine map.
3672 // TODO: Fold more cases:
3673 // min(some_affine, some_affine + constant, ...), etc.
3674 SmallVector<int64_t, 2> results;
3675 auto foldedMap = op.getMap().partialConstantFold(operands, &results);
3676
3677 if (foldedMap.getNumSymbols() == 1 && foldedMap.isSymbolIdentity())
3678 return op.getOperand(0);
3679
3680 // If some of the map results are not constant, try changing the map in-place.
3681 if (results.empty()) {
3682 // If the map is the same, report that folding did not happen.
3683 if (foldedMap == op.getMap())
3684 return {};
3685 op.setMapAttr(AffineMapAttr::get(value: foldedMap));
3686 return op.getResult();
3687 }
3688
3689 // Otherwise, completely fold the op into a constant.
3690 auto resultIt = std::is_same<T, AffineMinOp>::value
3691 ? llvm::min_element(Range&: results)
3692 : llvm::max_element(Range&: results);
3693 if (resultIt == results.end())
3694 return {};
3695 return IntegerAttr::get(IndexType::get(context: op.getContext()), *resultIt);
3696}
3697
3698/// Remove duplicated expressions in affine min/max ops.
3699template <typename T>
3700struct DeduplicateAffineMinMaxExpressions : public OpRewritePattern<T> {
3701 using OpRewritePattern<T>::OpRewritePattern;
3702
3703 LogicalResult matchAndRewrite(T affineOp,
3704 PatternRewriter &rewriter) const override {
3705 AffineMap oldMap = affineOp.getAffineMap();
3706
3707 SmallVector<AffineExpr, 4> newExprs;
3708 for (AffineExpr expr : oldMap.getResults()) {
3709 // This is a linear scan over newExprs, but it should be fine given that
3710 // we typically just have a few expressions per op.
3711 if (!llvm::is_contained(Range&: newExprs, Element: expr))
3712 newExprs.push_back(Elt: expr);
3713 }
3714
3715 if (newExprs.size() == oldMap.getNumResults())
3716 return failure();
3717
3718 auto newMap = AffineMap::get(dimCount: oldMap.getNumDims(), symbolCount: oldMap.getNumSymbols(),
3719 results: newExprs, context: rewriter.getContext());
3720 rewriter.replaceOpWithNewOp<T>(affineOp, newMap, affineOp.getMapOperands());
3721
3722 return success();
3723 }
3724};
3725
3726/// Merge an affine min/max op to its consumers if its consumer is also an
3727/// affine min/max op.
3728///
3729/// This pattern requires the producer affine min/max op is bound to a
3730/// dimension/symbol that is used as a standalone expression in the consumer
3731/// affine op's map.
3732///
3733/// For example, a pattern like the following:
3734///
3735/// %0 = affine.min affine_map<()[s0] -> (s0 + 16, s0 * 8)> ()[%sym1]
3736/// %1 = affine.min affine_map<(d0)[s0] -> (s0 + 4, d0)> (%0)[%sym2]
3737///
3738/// Can be turned into:
3739///
3740/// %1 = affine.min affine_map<
3741/// ()[s0, s1] -> (s0 + 4, s1 + 16, s1 * 8)> ()[%sym2, %sym1]
3742template <typename T>
3743struct MergeAffineMinMaxOp : public OpRewritePattern<T> {
3744 using OpRewritePattern<T>::OpRewritePattern;
3745
3746 LogicalResult matchAndRewrite(T affineOp,
3747 PatternRewriter &rewriter) const override {
3748 AffineMap oldMap = affineOp.getAffineMap();
3749 ValueRange dimOperands =
3750 affineOp.getMapOperands().take_front(oldMap.getNumDims());
3751 ValueRange symOperands =
3752 affineOp.getMapOperands().take_back(oldMap.getNumSymbols());
3753
3754 auto newDimOperands = llvm::to_vector<8>(Range&: dimOperands);
3755 auto newSymOperands = llvm::to_vector<8>(Range&: symOperands);
3756 SmallVector<AffineExpr, 4> newExprs;
3757 SmallVector<T, 4> producerOps;
3758
3759 // Go over each expression to see whether it's a single dimension/symbol
3760 // with the corresponding operand which is the result of another affine
3761 // min/max op. If So it can be merged into this affine op.
3762 for (AffineExpr expr : oldMap.getResults()) {
3763 if (auto symExpr = dyn_cast<AffineSymbolExpr>(Val&: expr)) {
3764 Value symValue = symOperands[symExpr.getPosition()];
3765 if (auto producerOp = symValue.getDefiningOp<T>()) {
3766 producerOps.push_back(producerOp);
3767 continue;
3768 }
3769 } else if (auto dimExpr = dyn_cast<AffineDimExpr>(Val&: expr)) {
3770 Value dimValue = dimOperands[dimExpr.getPosition()];
3771 if (auto producerOp = dimValue.getDefiningOp<T>()) {
3772 producerOps.push_back(producerOp);
3773 continue;
3774 }
3775 }
3776 // For the above cases we will remove the expression by merging the
3777 // producer affine min/max's affine expressions. Otherwise we need to
3778 // keep the existing expression.
3779 newExprs.push_back(Elt: expr);
3780 }
3781
3782 if (producerOps.empty())
3783 return failure();
3784
3785 unsigned numUsedDims = oldMap.getNumDims();
3786 unsigned numUsedSyms = oldMap.getNumSymbols();
3787
3788 // Now go over all producer affine ops and merge their expressions.
3789 for (T producerOp : producerOps) {
3790 AffineMap producerMap = producerOp.getAffineMap();
3791 unsigned numProducerDims = producerMap.getNumDims();
3792 unsigned numProducerSyms = producerMap.getNumSymbols();
3793
3794 // Collect all dimension/symbol values.
3795 ValueRange dimValues =
3796 producerOp.getMapOperands().take_front(numProducerDims);
3797 ValueRange symValues =
3798 producerOp.getMapOperands().take_back(numProducerSyms);
3799 newDimOperands.append(in_start: dimValues.begin(), in_end: dimValues.end());
3800 newSymOperands.append(in_start: symValues.begin(), in_end: symValues.end());
3801
3802 // For expressions we need to shift to avoid overlap.
3803 for (AffineExpr expr : producerMap.getResults()) {
3804 newExprs.push_back(Elt: expr.shiftDims(numDims: numProducerDims, shift: numUsedDims)
3805 .shiftSymbols(numSymbols: numProducerSyms, shift: numUsedSyms));
3806 }
3807
3808 numUsedDims += numProducerDims;
3809 numUsedSyms += numProducerSyms;
3810 }
3811
3812 auto newMap = AffineMap::get(dimCount: numUsedDims, symbolCount: numUsedSyms, results: newExprs,
3813 context: rewriter.getContext());
3814 auto newOperands =
3815 llvm::to_vector<8>(Range: llvm::concat<Value>(Ranges&: newDimOperands, Ranges&: newSymOperands));
3816 rewriter.replaceOpWithNewOp<T>(affineOp, newMap, newOperands);
3817
3818 return success();
3819 }
3820};
3821
3822/// Canonicalize the result expression order of an affine map and return success
3823/// if the order changed.
3824///
3825/// The function flattens the map's affine expressions to coefficient arrays and
3826/// sorts them in lexicographic order. A coefficient array contains a multiplier
3827/// for every dimension/symbol and a constant term. The canonicalization fails
3828/// if a result expression is not pure or if the flattening requires local
3829/// variables that, unlike dimensions and symbols, have no global order.
3830static LogicalResult canonicalizeMapExprAndTermOrder(AffineMap &map) {
3831 SmallVector<SmallVector<int64_t>> flattenedExprs;
3832 for (const AffineExpr &resultExpr : map.getResults()) {
3833 // Fail if the expression is not pure.
3834 if (!resultExpr.isPureAffine())
3835 return failure();
3836
3837 SimpleAffineExprFlattener flattener(map.getNumDims(), map.getNumSymbols());
3838 auto flattenResult = flattener.walkPostOrder(expr: resultExpr);
3839 if (failed(Result: flattenResult))
3840 return failure();
3841
3842 // Fail if the flattened expression has local variables.
3843 if (flattener.operandExprStack.back().size() !=
3844 map.getNumDims() + map.getNumSymbols() + 1)
3845 return failure();
3846
3847 flattenedExprs.emplace_back(Args: flattener.operandExprStack.back().begin(),
3848 Args: flattener.operandExprStack.back().end());
3849 }
3850
3851 // Fail if sorting is not necessary.
3852 if (llvm::is_sorted(Range&: flattenedExprs))
3853 return failure();
3854
3855 // Reorder the result expressions according to their flattened form.
3856 SmallVector<unsigned> resultPermutation =
3857 llvm::to_vector(Range: llvm::seq<unsigned>(Begin: 0, End: map.getNumResults()));
3858 llvm::sort(C&: resultPermutation, Comp: [&](unsigned lhs, unsigned rhs) {
3859 return flattenedExprs[lhs] < flattenedExprs[rhs];
3860 });
3861 SmallVector<AffineExpr> newExprs;
3862 for (unsigned idx : resultPermutation)
3863 newExprs.push_back(Elt: map.getResult(idx));
3864
3865 map = AffineMap::get(dimCount: map.getNumDims(), symbolCount: map.getNumSymbols(), results: newExprs,
3866 context: map.getContext());
3867 return success();
3868}
3869
3870/// Canonicalize the affine map result expression order of an affine min/max
3871/// operation.
3872///
3873/// The pattern calls `canonicalizeMapExprAndTermOrder` to order the result
3874/// expressions and replaces the operation if the order changed.
3875///
3876/// For example, the following operation:
3877///
3878/// %0 = affine.min affine_map<(d0, d1) -> (d0 + d1, d1 + 16, 32)> (%i0, %i1)
3879///
3880/// Turns into:
3881///
3882/// %0 = affine.min affine_map<(d0, d1) -> (32, d1 + 16, d0 + d1)> (%i0, %i1)
3883template <typename T>
3884struct CanonicalizeAffineMinMaxOpExprAndTermOrder : public OpRewritePattern<T> {
3885 using OpRewritePattern<T>::OpRewritePattern;
3886
3887 LogicalResult matchAndRewrite(T affineOp,
3888 PatternRewriter &rewriter) const override {
3889 AffineMap map = affineOp.getAffineMap();
3890 if (failed(Result: canonicalizeMapExprAndTermOrder(map)))
3891 return failure();
3892 rewriter.replaceOpWithNewOp<T>(affineOp, map, affineOp.getMapOperands());
3893 return success();
3894 }
3895};
3896
3897template <typename T>
3898struct CanonicalizeSingleResultAffineMinMaxOp : public OpRewritePattern<T> {
3899 using OpRewritePattern<T>::OpRewritePattern;
3900
3901 LogicalResult matchAndRewrite(T affineOp,
3902 PatternRewriter &rewriter) const override {
3903 if (affineOp.getMap().getNumResults() != 1)
3904 return failure();
3905 rewriter.replaceOpWithNewOp<AffineApplyOp>(affineOp, affineOp.getMap(),
3906 affineOp.getOperands());
3907 return success();
3908 }
3909};
3910
3911//===----------------------------------------------------------------------===//
3912// AffineMinOp
3913//===----------------------------------------------------------------------===//
3914//
3915// %0 = affine.min (d0) -> (1000, d0 + 512) (%i0)
3916//
3917
3918OpFoldResult AffineMinOp::fold(FoldAdaptor adaptor) {
3919 return foldMinMaxOp(op: *this, operands: adaptor.getOperands());
3920}
3921
3922void AffineMinOp::getCanonicalizationPatterns(RewritePatternSet &patterns,
3923 MLIRContext *context) {
3924 patterns.add<CanonicalizeSingleResultAffineMinMaxOp<AffineMinOp>,
3925 DeduplicateAffineMinMaxExpressions<AffineMinOp>,
3926 MergeAffineMinMaxOp<AffineMinOp>, SimplifyAffineOp<AffineMinOp>,
3927 CanonicalizeAffineMinMaxOpExprAndTermOrder<AffineMinOp>>(
3928 arg&: context);
3929}
3930
3931LogicalResult AffineMinOp::verify() { return verifyAffineMinMaxOp(op: *this); }
3932
3933ParseResult AffineMinOp::parse(OpAsmParser &parser, OperationState &result) {
3934 return parseAffineMinMaxOp<AffineMinOp>(parser, result);
3935}
3936
3937void AffineMinOp::print(OpAsmPrinter &p) { printAffineMinMaxOp(p, op: *this); }
3938
3939//===----------------------------------------------------------------------===//
3940// AffineMaxOp
3941//===----------------------------------------------------------------------===//
3942//
3943// %0 = affine.max (d0) -> (1000, d0 + 512) (%i0)
3944//
3945
3946OpFoldResult AffineMaxOp::fold(FoldAdaptor adaptor) {
3947 return foldMinMaxOp(op: *this, operands: adaptor.getOperands());
3948}
3949
3950void AffineMaxOp::getCanonicalizationPatterns(RewritePatternSet &patterns,
3951 MLIRContext *context) {
3952 patterns.add<CanonicalizeSingleResultAffineMinMaxOp<AffineMaxOp>,
3953 DeduplicateAffineMinMaxExpressions<AffineMaxOp>,
3954 MergeAffineMinMaxOp<AffineMaxOp>, SimplifyAffineOp<AffineMaxOp>,
3955 CanonicalizeAffineMinMaxOpExprAndTermOrder<AffineMaxOp>>(
3956 arg&: context);
3957}
3958
3959LogicalResult AffineMaxOp::verify() { return verifyAffineMinMaxOp(op: *this); }
3960
3961ParseResult AffineMaxOp::parse(OpAsmParser &parser, OperationState &result) {
3962 return parseAffineMinMaxOp<AffineMaxOp>(parser, result);
3963}
3964
3965void AffineMaxOp::print(OpAsmPrinter &p) { printAffineMinMaxOp(p, op: *this); }
3966
3967//===----------------------------------------------------------------------===//
3968// AffinePrefetchOp
3969//===----------------------------------------------------------------------===//
3970
3971//
3972// affine.prefetch %0[%i, %j + 5], read, locality<3>, data : memref<400x400xi32>
3973//
3974ParseResult AffinePrefetchOp::parse(OpAsmParser &parser,
3975 OperationState &result) {
3976 auto &builder = parser.getBuilder();
3977 auto indexTy = builder.getIndexType();
3978
3979 MemRefType type;
3980 OpAsmParser::UnresolvedOperand memrefInfo;
3981 IntegerAttr hintInfo;
3982 auto i32Type = parser.getBuilder().getIntegerType(width: 32);
3983 StringRef readOrWrite, cacheType;
3984
3985 AffineMapAttr mapAttr;
3986 SmallVector<OpAsmParser::UnresolvedOperand, 1> mapOperands;
3987 if (parser.parseOperand(result&: memrefInfo) ||
3988 parser.parseAffineMapOfSSAIds(operands&: mapOperands, map&: mapAttr,
3989 attrName: AffinePrefetchOp::getMapAttrStrName(),
3990 attrs&: result.attributes) ||
3991 parser.parseComma() || parser.parseKeyword(keyword: &readOrWrite) ||
3992 parser.parseComma() || parser.parseKeyword(keyword: "locality") ||
3993 parser.parseLess() ||
3994 parser.parseAttribute(result&: hintInfo, type: i32Type,
3995 attrName: AffinePrefetchOp::getLocalityHintAttrStrName(),
3996 attrs&: result.attributes) ||
3997 parser.parseGreater() || parser.parseComma() ||
3998 parser.parseKeyword(keyword: &cacheType) ||
3999 parser.parseOptionalAttrDict(result&: result.attributes) ||
4000 parser.parseColonType(result&: type) ||
4001 parser.resolveOperand(operand: memrefInfo, type, result&: result.operands) ||
4002 parser.resolveOperands(operands&: mapOperands, type: indexTy, result&: result.operands))
4003 return failure();
4004
4005 if (readOrWrite != "read" && readOrWrite != "write")
4006 return parser.emitError(loc: parser.getNameLoc(),
4007 message: "rw specifier has to be 'read' or 'write'");
4008 result.addAttribute(name: AffinePrefetchOp::getIsWriteAttrStrName(),
4009 attr: parser.getBuilder().getBoolAttr(value: readOrWrite == "write"));
4010
4011 if (cacheType != "data" && cacheType != "instr")
4012 return parser.emitError(loc: parser.getNameLoc(),
4013 message: "cache type has to be 'data' or 'instr'");
4014
4015 result.addAttribute(name: AffinePrefetchOp::getIsDataCacheAttrStrName(),
4016 attr: parser.getBuilder().getBoolAttr(value: cacheType == "data"));
4017
4018 return success();
4019}
4020
4021void AffinePrefetchOp::print(OpAsmPrinter &p) {
4022 p << " " << getMemref() << '[';
4023 AffineMapAttr mapAttr = getMapAttr();
4024 if (mapAttr)
4025 p.printAffineMapOfSSAIds(mapAttr, operands: getMapOperands());
4026 p << ']' << ", " << (getIsWrite() ? "write" : "read") << ", " << "locality<"
4027 << getLocalityHint() << ">, " << (getIsDataCache() ? "data" : "instr");
4028 p.printOptionalAttrDict(attrs: (*this)->getDiscardableAttrDictionary().getValue());
4029 p << " : " << getMemRefType();
4030}
4031
4032LogicalResult AffinePrefetchOp::verify() {
4033 auto mapAttr = getMapAttr();
4034 if (mapAttr) {
4035 AffineMap map = mapAttr.getValue();
4036 if (map.getNumResults() != getMemRefType().getRank())
4037 return emitOpError(message: "affine.prefetch affine map num results must equal"
4038 " memref rank");
4039 if (map.getNumInputs() + 1 != getNumOperands())
4040 return emitOpError(message: "too few operands");
4041 } else {
4042 if (getNumOperands() != 1)
4043 return emitOpError(message: "too few operands");
4044 }
4045
4046 Region *scope = getAffineScope(op: *this);
4047 for (auto idx : getMapOperands()) {
4048 if (!isValidAffineIndexOperand(value: idx, region: scope))
4049 return emitOpError(
4050 message: "index must be a valid dimension or symbol identifier");
4051 }
4052 return success();
4053}
4054
4055void AffinePrefetchOp::getCanonicalizationPatterns(RewritePatternSet &results,
4056 MLIRContext *context) {
4057 // prefetch(memrefcast) -> prefetch
4058 results.add<SimplifyAffineOp<AffinePrefetchOp>>(arg&: context);
4059}
4060
4061LogicalResult AffinePrefetchOp::fold(FoldAdaptor adaptor,
4062 SmallVectorImpl<OpFoldResult> &results) {
4063 /// prefetch(memrefcast) -> prefetch
4064 return memref::foldMemRefCast(op: *this);
4065}
4066
4067//===----------------------------------------------------------------------===//
4068// AffineParallelOp
4069//===----------------------------------------------------------------------===//
4070
4071void AffineParallelOp::build(OpBuilder &builder, OperationState &result,
4072 TypeRange resultTypes,
4073 ArrayRef<arith::AtomicRMWKind> reductions,
4074 ArrayRef<int64_t> ranges) {
4075 SmallVector<AffineMap> lbs(ranges.size(), builder.getConstantAffineMap(val: 0));
4076 auto ubs = llvm::map_to_vector<4>(C&: ranges, F: [&](int64_t value) {
4077 return builder.getConstantAffineMap(val: value);
4078 });
4079 SmallVector<int64_t> steps(ranges.size(), 1);
4080 build(odsBuilder&: builder, odsState&: result, resultTypes, reductions, lbMaps: lbs, /*lbArgs=*/{}, ubMaps: ubs,
4081 /*ubArgs=*/{}, steps);
4082}
4083
4084void AffineParallelOp::build(OpBuilder &builder, OperationState &result,
4085 TypeRange resultTypes,
4086 ArrayRef<arith::AtomicRMWKind> reductions,
4087 ArrayRef<AffineMap> lbMaps, ValueRange lbArgs,
4088 ArrayRef<AffineMap> ubMaps, ValueRange ubArgs,
4089 ArrayRef<int64_t> steps) {
4090 assert(llvm::all_of(lbMaps,
4091 [lbMaps](AffineMap m) {
4092 return m.getNumDims() == lbMaps[0].getNumDims() &&
4093 m.getNumSymbols() == lbMaps[0].getNumSymbols();
4094 }) &&
4095 "expected all lower bounds maps to have the same number of dimensions "
4096 "and symbols");
4097 assert(llvm::all_of(ubMaps,
4098 [ubMaps](AffineMap m) {
4099 return m.getNumDims() == ubMaps[0].getNumDims() &&
4100 m.getNumSymbols() == ubMaps[0].getNumSymbols();
4101 }) &&
4102 "expected all upper bounds maps to have the same number of dimensions "
4103 "and symbols");
4104 assert((lbMaps.empty() || lbMaps[0].getNumInputs() == lbArgs.size()) &&
4105 "expected lower bound maps to have as many inputs as lower bound "
4106 "operands");
4107 assert((ubMaps.empty() || ubMaps[0].getNumInputs() == ubArgs.size()) &&
4108 "expected upper bound maps to have as many inputs as upper bound "
4109 "operands");
4110
4111 OpBuilder::InsertionGuard guard(builder);
4112 result.addTypes(newTypes&: resultTypes);
4113
4114 // Convert the reductions to integer attributes.
4115 SmallVector<Attribute, 4> reductionAttrs;
4116 for (arith::AtomicRMWKind reduction : reductions)
4117 reductionAttrs.push_back(
4118 Elt: builder.getI64IntegerAttr(value: static_cast<int64_t>(reduction)));
4119 result.addAttribute(name: getReductionsAttrStrName(),
4120 attr: builder.getArrayAttr(value: reductionAttrs));
4121
4122 // Concatenates maps defined in the same input space (same dimensions and
4123 // symbols), assumes there is at least one map.
4124 auto concatMapsSameInput = [&builder](ArrayRef<AffineMap> maps,
4125 SmallVectorImpl<int32_t> &groups) {
4126 if (maps.empty())
4127 return AffineMap::get(context: builder.getContext());
4128 SmallVector<AffineExpr> exprs;
4129 groups.reserve(N: groups.size() + maps.size());
4130 exprs.reserve(N: maps.size());
4131 for (AffineMap m : maps) {
4132 llvm::append_range(C&: exprs, R: m.getResults());
4133 groups.push_back(Elt: m.getNumResults());
4134 }
4135 return AffineMap::get(dimCount: maps[0].getNumDims(), symbolCount: maps[0].getNumSymbols(), results: exprs,
4136 context: maps[0].getContext());
4137 };
4138
4139 // Set up the bounds.
4140 SmallVector<int32_t> lbGroups, ubGroups;
4141 AffineMap lbMap = concatMapsSameInput(lbMaps, lbGroups);
4142 AffineMap ubMap = concatMapsSameInput(ubMaps, ubGroups);
4143 result.addAttribute(name: getLowerBoundsMapAttrStrName(),
4144 attr: AffineMapAttr::get(value: lbMap));
4145 result.addAttribute(name: getLowerBoundsGroupsAttrStrName(),
4146 attr: builder.getI32TensorAttr(values: lbGroups));
4147 result.addAttribute(name: getUpperBoundsMapAttrStrName(),
4148 attr: AffineMapAttr::get(value: ubMap));
4149 result.addAttribute(name: getUpperBoundsGroupsAttrStrName(),
4150 attr: builder.getI32TensorAttr(values: ubGroups));
4151 result.addAttribute(name: getStepsAttrStrName(), attr: builder.getI64ArrayAttr(values: steps));
4152 result.addOperands(newOperands: lbArgs);
4153 result.addOperands(newOperands: ubArgs);
4154
4155 // Create a region and a block for the body.
4156 auto *bodyRegion = result.addRegion();
4157 Block *body = builder.createBlock(parent: bodyRegion);
4158
4159 // Add all the block arguments.
4160 for (unsigned i = 0, e = steps.size(); i < e; ++i)
4161 body->addArgument(type: IndexType::get(context: builder.getContext()), loc: result.location);
4162 if (resultTypes.empty())
4163 ensureTerminator(region&: *bodyRegion, builder, loc: result.location);
4164}
4165
4166SmallVector<Region *> AffineParallelOp::getLoopRegions() {
4167 return {&getRegion()};
4168}
4169
4170unsigned AffineParallelOp::getNumDims() { return getSteps().size(); }
4171
4172AffineParallelOp::operand_range AffineParallelOp::getLowerBoundsOperands() {
4173 return getOperands().take_front(n: getLowerBoundsMap().getNumInputs());
4174}
4175
4176AffineParallelOp::operand_range AffineParallelOp::getUpperBoundsOperands() {
4177 return getOperands().drop_front(n: getLowerBoundsMap().getNumInputs());
4178}
4179
4180AffineMap AffineParallelOp::getLowerBoundMap(unsigned pos) {
4181 auto values = getLowerBoundsGroups().getValues<int32_t>();
4182 unsigned start = 0;
4183 for (unsigned i = 0; i < pos; ++i)
4184 start += values[i];
4185 return getLowerBoundsMap().getSliceMap(start, length: values[pos]);
4186}
4187
4188AffineMap AffineParallelOp::getUpperBoundMap(unsigned pos) {
4189 auto values = getUpperBoundsGroups().getValues<int32_t>();
4190 unsigned start = 0;
4191 for (unsigned i = 0; i < pos; ++i)
4192 start += values[i];
4193 return getUpperBoundsMap().getSliceMap(start, length: values[pos]);
4194}
4195
4196AffineValueMap AffineParallelOp::getLowerBoundsValueMap() {
4197 return AffineValueMap(getLowerBoundsMap(), getLowerBoundsOperands());
4198}
4199
4200AffineValueMap AffineParallelOp::getUpperBoundsValueMap() {
4201 return AffineValueMap(getUpperBoundsMap(), getUpperBoundsOperands());
4202}
4203
4204std::optional<SmallVector<int64_t, 8>> AffineParallelOp::getConstantRanges() {
4205 if (hasMinMaxBounds())
4206 return std::nullopt;
4207
4208 // Try to convert all the ranges to constant expressions.
4209 SmallVector<int64_t, 8> out;
4210 AffineValueMap rangesValueMap;
4211 AffineValueMap::difference(a: getUpperBoundsValueMap(), b: getLowerBoundsValueMap(),
4212 res: &rangesValueMap);
4213 out.reserve(N: rangesValueMap.getNumResults());
4214 for (unsigned i = 0, e = rangesValueMap.getNumResults(); i < e; ++i) {
4215 auto expr = rangesValueMap.getResult(i);
4216 auto cst = dyn_cast<AffineConstantExpr>(Val&: expr);
4217 if (!cst)
4218 return std::nullopt;
4219 out.push_back(Elt: cst.getValue());
4220 }
4221 return out;
4222}
4223
4224Block *AffineParallelOp::getBody() { return &getRegion().front(); }
4225
4226OpBuilder AffineParallelOp::getBodyBuilder() {
4227 return OpBuilder(getBody(), std::prev(x: getBody()->end()));
4228}
4229
4230void AffineParallelOp::setLowerBounds(ValueRange lbOperands, AffineMap map) {
4231 assert(lbOperands.size() == map.getNumInputs() &&
4232 "operands to map must match number of inputs");
4233
4234 auto ubOperands = getUpperBoundsOperands();
4235
4236 SmallVector<Value, 4> newOperands(lbOperands);
4237 newOperands.append(in_start: ubOperands.begin(), in_end: ubOperands.end());
4238 (*this)->setOperands(newOperands);
4239
4240 setLowerBoundsMapAttr(AffineMapAttr::get(value: map));
4241}
4242
4243void AffineParallelOp::setUpperBounds(ValueRange ubOperands, AffineMap map) {
4244 assert(ubOperands.size() == map.getNumInputs() &&
4245 "operands to map must match number of inputs");
4246
4247 SmallVector<Value, 4> newOperands(getLowerBoundsOperands());
4248 newOperands.append(in_start: ubOperands.begin(), in_end: ubOperands.end());
4249 (*this)->setOperands(newOperands);
4250
4251 setUpperBoundsMapAttr(AffineMapAttr::get(value: map));
4252}
4253
4254void AffineParallelOp::setSteps(ArrayRef<int64_t> newSteps) {
4255 setStepsAttr(getBodyBuilder().getI64ArrayAttr(values: newSteps));
4256}
4257
4258// check whether resultType match op or not in affine.parallel
4259static bool isResultTypeMatchAtomicRMWKind(Type resultType,
4260 arith::AtomicRMWKind op) {
4261 switch (op) {
4262 case arith::AtomicRMWKind::addf:
4263 return isa<FloatType>(Val: resultType);
4264 case arith::AtomicRMWKind::addi:
4265 return isa<IntegerType>(Val: resultType);
4266 case arith::AtomicRMWKind::assign:
4267 return true;
4268 case arith::AtomicRMWKind::mulf:
4269 return isa<FloatType>(Val: resultType);
4270 case arith::AtomicRMWKind::muli:
4271 return isa<IntegerType>(Val: resultType);
4272 case arith::AtomicRMWKind::maximumf:
4273 case arith::AtomicRMWKind::maxnumf:
4274 case arith::AtomicRMWKind::minimumf:
4275 case arith::AtomicRMWKind::minnumf:
4276 return isa<FloatType>(Val: resultType);
4277 // The kind carries the signedness of the comparison; the integer is
4278 // signless (what arith's maxsi/minsi/maxui/minui, which the reduction
4279 // lowers to, operate on) or of that signedness.
4280 case arith::AtomicRMWKind::maxs:
4281 case arith::AtomicRMWKind::mins: {
4282 auto intType = dyn_cast<IntegerType>(Val&: resultType);
4283 return intType && !intType.isUnsigned();
4284 }
4285 case arith::AtomicRMWKind::maxu:
4286 case arith::AtomicRMWKind::minu: {
4287 auto intType = dyn_cast<IntegerType>(Val&: resultType);
4288 return intType && !intType.isSigned();
4289 }
4290 case arith::AtomicRMWKind::ori:
4291 case arith::AtomicRMWKind::andi:
4292 case arith::AtomicRMWKind::xori:
4293 return isa<IntegerType>(Val: resultType);
4294 }
4295 llvm_unreachable("Unhandled atomic rmw kind");
4296}
4297
4298LogicalResult AffineParallelOp::verify() {
4299 auto numDims = getNumDims();
4300 if (getLowerBoundsGroups().getNumElements() != numDims ||
4301 getUpperBoundsGroups().getNumElements() != numDims ||
4302 getSteps().size() != numDims || getBody()->getNumArguments() != numDims) {
4303 return emitOpError() << "the number of region arguments ("
4304 << getBody()->getNumArguments()
4305 << ") and the number of map groups for lower ("
4306 << getLowerBoundsGroups().getNumElements()
4307 << ") and upper bound ("
4308 << getUpperBoundsGroups().getNumElements()
4309 << "), and the number of steps (" << getSteps().size()
4310 << ") must all match";
4311 }
4312
4313 unsigned expectedNumLBResults = 0;
4314 for (APInt v : getLowerBoundsGroups()) {
4315 unsigned results = v.getZExtValue();
4316 if (results == 0)
4317 return emitOpError()
4318 << "expected lower bound map to have at least one result";
4319 expectedNumLBResults += results;
4320 }
4321 if (expectedNumLBResults != getLowerBoundsMap().getNumResults())
4322 return emitOpError() << "expected lower bounds map to have "
4323 << expectedNumLBResults << " results";
4324 unsigned expectedNumUBResults = 0;
4325 for (APInt v : getUpperBoundsGroups()) {
4326 unsigned results = v.getZExtValue();
4327 if (results == 0)
4328 return emitOpError()
4329 << "expected upper bound map to have at least one result";
4330 expectedNumUBResults += results;
4331 }
4332 if (expectedNumUBResults != getUpperBoundsMap().getNumResults())
4333 return emitOpError() << "expected upper bounds map to have "
4334 << expectedNumUBResults << " results";
4335
4336 if (getReductions().size() != getNumResults())
4337 return emitOpError(message: "a reduction must be specified for each output");
4338
4339 // Verify reduction ops are all valid and each result type matches reduction
4340 // ops
4341 for (auto it : llvm::enumerate(First: (getReductions()))) {
4342 Attribute attr = it.value();
4343 auto intAttr = dyn_cast<IntegerAttr>(Val&: attr);
4344 if (!intAttr || !arith::symbolizeAtomicRMWKind(intAttr.getInt()))
4345 return emitOpError(message: "invalid reduction attribute");
4346 auto kind = arith::symbolizeAtomicRMWKind(intAttr.getInt()).value();
4347 if (!isResultTypeMatchAtomicRMWKind(resultType: getResult(i: it.index()).getType(), op: kind))
4348 return emitOpError(message: "result type cannot match reduction attribute");
4349 }
4350
4351 // Verify that the bound operands are valid dimension/symbols.
4352 /// Lower bounds.
4353 if (failed(Result: verifyDimAndSymbolIdentifiers(op&: *this, operands: getLowerBoundsOperands(),
4354 numDims: getLowerBoundsMap().getNumDims())))
4355 return failure();
4356 /// Upper bounds.
4357 if (failed(Result: verifyDimAndSymbolIdentifiers(op&: *this, operands: getUpperBoundsOperands(),
4358 numDims: getUpperBoundsMap().getNumDims())))
4359 return failure();
4360 return success();
4361}
4362
4363LogicalResult AffineValueMap::canonicalize() {
4364 SmallVector<Value, 4> newOperands{operands};
4365 auto newMap = getAffineMap();
4366 composeAffineMapAndOperands(map: &newMap, operands: &newOperands);
4367 if (newMap == getAffineMap() && newOperands == operands)
4368 return failure();
4369 reset(map: newMap, operands: newOperands);
4370 return success();
4371}
4372
4373/// Canonicalize the bounds of the given loop.
4374static LogicalResult canonicalizeLoopBounds(AffineParallelOp op) {
4375 AffineValueMap lb = op.getLowerBoundsValueMap();
4376 bool lbCanonicalized = succeeded(Result: lb.canonicalize());
4377
4378 AffineValueMap ub = op.getUpperBoundsValueMap();
4379 bool ubCanonicalized = succeeded(Result: ub.canonicalize());
4380
4381 // Any canonicalization change always leads to updated map(s).
4382 if (!lbCanonicalized && !ubCanonicalized)
4383 return failure();
4384
4385 if (lbCanonicalized)
4386 op.setLowerBounds(lbOperands: lb.getOperands(), map: lb.getAffineMap());
4387 if (ubCanonicalized)
4388 op.setUpperBounds(ubOperands: ub.getOperands(), map: ub.getAffineMap());
4389
4390 return success();
4391}
4392
4393LogicalResult AffineParallelOp::fold(FoldAdaptor adaptor,
4394 SmallVectorImpl<OpFoldResult> &results) {
4395 return canonicalizeLoopBounds(op: *this);
4396}
4397
4398/// Prints a lower(upper) bound of an affine parallel loop with max(min)
4399/// conditions in it. `mapAttr` is a flat list of affine expressions and `group`
4400/// identifies which of the those expressions form max/min groups. `operands`
4401/// are the SSA values of dimensions and symbols and `keyword` is either "min"
4402/// or "max".
4403static void printMinMaxBound(OpAsmPrinter &p, AffineMapAttr mapAttr,
4404 DenseIntElementsAttr group, ValueRange operands,
4405 StringRef keyword) {
4406 AffineMap map = mapAttr.getValue();
4407 unsigned numDims = map.getNumDims();
4408 ValueRange dimOperands = operands.take_front(n: numDims);
4409 ValueRange symOperands = operands.drop_front(n: numDims);
4410 unsigned start = 0;
4411 for (llvm::APInt groupSize : group) {
4412 if (start != 0)
4413 p << ", ";
4414
4415 unsigned size = groupSize.getZExtValue();
4416 if (size == 1) {
4417 p.printAffineExprOfSSAIds(expr: map.getResult(idx: start), dimOperands, symOperands);
4418 ++start;
4419 } else {
4420 p << keyword << '(';
4421 AffineMap submap = map.getSliceMap(start, length: size);
4422 p.printAffineMapOfSSAIds(mapAttr: AffineMapAttr::get(value: submap), operands);
4423 p << ')';
4424 start += size;
4425 }
4426 }
4427}
4428
4429void AffineParallelOp::print(OpAsmPrinter &p) {
4430 p << " (" << getBody()->getArguments() << ") = (";
4431 printMinMaxBound(p, mapAttr: getLowerBoundsMapAttr(), group: getLowerBoundsGroupsAttr(),
4432 operands: getLowerBoundsOperands(), keyword: "max");
4433 p << ") to (";
4434 printMinMaxBound(p, mapAttr: getUpperBoundsMapAttr(), group: getUpperBoundsGroupsAttr(),
4435 operands: getUpperBoundsOperands(), keyword: "min");
4436 p << ')';
4437 SmallVector<int64_t, 8> steps = getSteps();
4438 bool elideSteps = llvm::all_of(Range&: steps, P: [](int64_t step) { return step == 1; });
4439 if (!elideSteps) {
4440 p << " step (";
4441 llvm::interleaveComma(c: steps, os&: p);
4442 p << ')';
4443 }
4444 if (getNumResults()) {
4445 p << " reduce (";
4446 llvm::interleaveComma(c: getReductions(), os&: p, each_fn: [&](auto &attr) {
4447 arith::AtomicRMWKind sym = *arith::symbolizeAtomicRMWKind(
4448 llvm::cast<IntegerAttr>(attr).getInt());
4449 p << "\"" << arith::stringifyAtomicRMWKind(sym) << "\"";
4450 });
4451 p << ") -> (" << getResultTypes() << ")";
4452 }
4453
4454 p << ' ';
4455 p.printRegion(blocks&: getRegion(), /*printEntryBlockArgs=*/false,
4456 /*printBlockTerminators=*/getNumResults());
4457 p.printOptionalAttrDict(attrs: (*this)->getDiscardableAttrDictionary().getValue());
4458}
4459
4460/// Given a list of lists of parsed operands, populates `uniqueOperands` with
4461/// unique operands. Also populates `replacements with affine expressions of
4462/// `kind` that can be used to update affine maps previously accepting a
4463/// `operands` to accept `uniqueOperands` instead.
4464static ParseResult deduplicateAndResolveOperands(
4465 OpAsmParser &parser,
4466 ArrayRef<SmallVector<OpAsmParser::UnresolvedOperand>> operands,
4467 SmallVectorImpl<Value> &uniqueOperands,
4468 SmallVectorImpl<AffineExpr> &replacements, AffineExprKind kind) {
4469 assert((kind == AffineExprKind::DimId || kind == AffineExprKind::SymbolId) &&
4470 "expected operands to be dim or symbol expression");
4471
4472 Type indexType = parser.getBuilder().getIndexType();
4473 for (const auto &list : operands) {
4474 SmallVector<Value> valueOperands;
4475 if (parser.resolveOperands(operands: list, type: indexType, result&: valueOperands))
4476 return failure();
4477 for (Value operand : valueOperands) {
4478 unsigned pos = std::distance(first: uniqueOperands.begin(),
4479 last: llvm::find(Range&: uniqueOperands, Val: operand));
4480 if (pos == uniqueOperands.size())
4481 uniqueOperands.push_back(Elt: operand);
4482 replacements.push_back(
4483 Elt: kind == AffineExprKind::DimId
4484 ? getAffineDimExpr(position: pos, context: parser.getContext())
4485 : getAffineSymbolExpr(position: pos, context: parser.getContext()));
4486 }
4487 }
4488 return success();
4489}
4490
4491namespace {
4492enum class MinMaxKind { Min, Max };
4493} // namespace
4494
4495/// Parses an affine map that can contain a min/max for groups of its results,
4496/// e.g., max(expr-1, expr-2), expr-3, max(expr-4, expr-5, expr-6). Populates
4497/// `result` attributes with the map (flat list of expressions) and the grouping
4498/// (list of integers that specify how many expressions to put into each
4499/// min/max) attributes. Deduplicates repeated operands.
4500///
4501/// parallel-bound ::= `(` parallel-group-list `)`
4502/// parallel-group-list ::= parallel-group (`,` parallel-group-list)?
4503/// parallel-group ::= simple-group | min-max-group
4504/// simple-group ::= expr-of-ssa-ids
4505/// min-max-group ::= ( `min` | `max` ) `(` expr-of-ssa-ids-list `)`
4506/// expr-of-ssa-ids-list ::= expr-of-ssa-ids (`,` expr-of-ssa-id-list)?
4507///
4508/// Examples:
4509/// (%0, min(%1 + %2, %3), %4, min(%5 floordiv 32, %6))
4510/// (%0, max(%1 - 2 * %2))
4511static ParseResult parseAffineMapWithMinMax(OpAsmParser &parser,
4512 OperationState &result,
4513 MinMaxKind kind) {
4514 // Using `const` not `constexpr` below to workaround a MSVC optimizer bug,
4515 // see: https://reviews.llvm.org/D134227#3821753
4516 const llvm::StringLiteral tmpAttrStrName = "__pseudo_bound_map";
4517
4518 StringRef mapName = kind == MinMaxKind::Min
4519 ? AffineParallelOp::getUpperBoundsMapAttrStrName()
4520 : AffineParallelOp::getLowerBoundsMapAttrStrName();
4521 StringRef groupsName =
4522 kind == MinMaxKind::Min
4523 ? AffineParallelOp::getUpperBoundsGroupsAttrStrName()
4524 : AffineParallelOp::getLowerBoundsGroupsAttrStrName();
4525
4526 if (failed(Result: parser.parseLParen()))
4527 return failure();
4528
4529 if (succeeded(Result: parser.parseOptionalRParen())) {
4530 result.addAttribute(
4531 name: mapName, attr: AffineMapAttr::get(value: parser.getBuilder().getEmptyAffineMap()));
4532 result.addAttribute(name: groupsName, attr: parser.getBuilder().getI32TensorAttr(values: {}));
4533 return success();
4534 }
4535
4536 SmallVector<AffineExpr> flatExprs;
4537 SmallVector<SmallVector<OpAsmParser::UnresolvedOperand>> flatDimOperands;
4538 SmallVector<SmallVector<OpAsmParser::UnresolvedOperand>> flatSymOperands;
4539 SmallVector<int32_t> numMapsPerGroup;
4540 SmallVector<OpAsmParser::UnresolvedOperand> mapOperands;
4541 auto parseOperands = [&]() {
4542 if (succeeded(Result: parser.parseOptionalKeyword(
4543 keyword: kind == MinMaxKind::Min ? "min" : "max"))) {
4544 mapOperands.clear();
4545 AffineMapAttr map;
4546 if (failed(Result: parser.parseAffineMapOfSSAIds(operands&: mapOperands, map, attrName: tmpAttrStrName,
4547 attrs&: result.attributes,
4548 delimiter: OpAsmParser::Delimiter::Paren)))
4549 return failure();
4550 result.attributes.erase(name: tmpAttrStrName);
4551 llvm::append_range(C&: flatExprs, R: map.getValue().getResults());
4552 auto operandsRef = llvm::ArrayRef(mapOperands);
4553 auto dimsRef = operandsRef.take_front(N: map.getValue().getNumDims());
4554 SmallVector<OpAsmParser::UnresolvedOperand> dims(dimsRef);
4555 auto symsRef = operandsRef.drop_front(N: map.getValue().getNumDims());
4556 SmallVector<OpAsmParser::UnresolvedOperand> syms(symsRef);
4557 flatDimOperands.append(NumInputs: map.getValue().getNumResults(), Elt: dims);
4558 flatSymOperands.append(NumInputs: map.getValue().getNumResults(), Elt: syms);
4559 numMapsPerGroup.push_back(Elt: map.getValue().getNumResults());
4560 } else {
4561 if (failed(Result: parser.parseAffineExprOfSSAIds(dimOperands&: flatDimOperands.emplace_back(),
4562 symbOperands&: flatSymOperands.emplace_back(),
4563 expr&: flatExprs.emplace_back())))
4564 return failure();
4565 numMapsPerGroup.push_back(Elt: 1);
4566 }
4567 return success();
4568 };
4569 if (parser.parseCommaSeparatedList(parseElementFn: parseOperands) || parser.parseRParen())
4570 return failure();
4571
4572 unsigned totalNumDims = 0;
4573 unsigned totalNumSyms = 0;
4574 for (unsigned i = 0, e = flatExprs.size(); i < e; ++i) {
4575 unsigned numDims = flatDimOperands[i].size();
4576 unsigned numSyms = flatSymOperands[i].size();
4577 flatExprs[i] = flatExprs[i]
4578 .shiftDims(numDims, shift: totalNumDims)
4579 .shiftSymbols(numSymbols: numSyms, shift: totalNumSyms);
4580 totalNumDims += numDims;
4581 totalNumSyms += numSyms;
4582 }
4583
4584 // Deduplicate map operands.
4585 SmallVector<Value> dimOperands, symOperands;
4586 SmallVector<AffineExpr> dimRplacements, symRepacements;
4587 if (deduplicateAndResolveOperands(parser, operands: flatDimOperands, uniqueOperands&: dimOperands,
4588 replacements&: dimRplacements, kind: AffineExprKind::DimId) ||
4589 deduplicateAndResolveOperands(parser, operands: flatSymOperands, uniqueOperands&: symOperands,
4590 replacements&: symRepacements, kind: AffineExprKind::SymbolId))
4591 return failure();
4592
4593 result.operands.append(in_start: dimOperands.begin(), in_end: dimOperands.end());
4594 result.operands.append(in_start: symOperands.begin(), in_end: symOperands.end());
4595
4596 Builder &builder = parser.getBuilder();
4597 auto flatMap = AffineMap::get(dimCount: totalNumDims, symbolCount: totalNumSyms, results: flatExprs,
4598 context: parser.getContext());
4599 flatMap = flatMap.replaceDimsAndSymbols(
4600 dimReplacements: dimRplacements, symReplacements: symRepacements, numResultDims: dimOperands.size(), numResultSyms: symOperands.size());
4601
4602 result.addAttribute(name: mapName, attr: AffineMapAttr::get(value: flatMap));
4603 result.addAttribute(name: groupsName, attr: builder.getI32TensorAttr(values: numMapsPerGroup));
4604 return success();
4605}
4606
4607//
4608// operation ::= `affine.parallel` `(` ssa-ids `)` `=` parallel-bound
4609// `to` parallel-bound steps? region attr-dict?
4610// steps ::= `steps` `(` integer-literals `)`
4611//
4612ParseResult AffineParallelOp::parse(OpAsmParser &parser,
4613 OperationState &result) {
4614 auto &builder = parser.getBuilder();
4615 auto indexType = builder.getIndexType();
4616 SmallVector<OpAsmParser::Argument, 4> ivs;
4617 if (parser.parseArgumentList(result&: ivs, delimiter: OpAsmParser::Delimiter::Paren) ||
4618 parser.parseEqual() ||
4619 parseAffineMapWithMinMax(parser, result, kind: MinMaxKind::Max) ||
4620 parser.parseKeyword(keyword: "to") ||
4621 parseAffineMapWithMinMax(parser, result, kind: MinMaxKind::Min))
4622 return failure();
4623
4624 AffineMapAttr stepsMapAttr;
4625 NamedAttrList stepsAttrs;
4626 SmallVector<OpAsmParser::UnresolvedOperand, 4> stepsMapOperands;
4627 if (failed(Result: parser.parseOptionalKeyword(keyword: "step"))) {
4628 SmallVector<int64_t, 4> steps(ivs.size(), 1);
4629 result.addAttribute(name: AffineParallelOp::getStepsAttrStrName(),
4630 attr: builder.getI64ArrayAttr(values: steps));
4631 } else {
4632 if (parser.parseAffineMapOfSSAIds(operands&: stepsMapOperands, map&: stepsMapAttr,
4633 attrName: AffineParallelOp::getStepsAttrStrName(),
4634 attrs&: stepsAttrs,
4635 delimiter: OpAsmParser::Delimiter::Paren))
4636 return failure();
4637
4638 // Convert steps from an AffineMap into an I64ArrayAttr.
4639 SmallVector<int64_t, 4> steps;
4640 auto stepsMap = stepsMapAttr.getValue();
4641 for (const auto &result : stepsMap.getResults()) {
4642 auto constExpr = dyn_cast<AffineConstantExpr>(Val: result);
4643 if (!constExpr)
4644 return parser.emitError(loc: parser.getNameLoc(),
4645 message: "steps must be constant integers");
4646 steps.push_back(Elt: constExpr.getValue());
4647 }
4648 result.addAttribute(name: AffineParallelOp::getStepsAttrStrName(),
4649 attr: builder.getI64ArrayAttr(values: steps));
4650 }
4651
4652 // Parse optional clause of the form: `reduce ("addf", "maxf")`, where the
4653 // quoted strings are a member of the enum AtomicRMWKind.
4654 SmallVector<Attribute, 4> reductions;
4655 if (succeeded(Result: parser.parseOptionalKeyword(keyword: "reduce"))) {
4656 if (parser.parseLParen())
4657 return failure();
4658 auto parseAttributes = [&]() -> ParseResult {
4659 // Parse a single quoted string via the attribute parsing, and then
4660 // verify it is a member of the enum and convert to it's integer
4661 // representation.
4662 StringAttr attrVal;
4663 NamedAttrList attrStorage;
4664 auto loc = parser.getCurrentLocation();
4665 if (parser.parseAttribute(result&: attrVal, type: builder.getNoneType(), attrName: "reduce",
4666 attrs&: attrStorage))
4667 return failure();
4668 std::optional<arith::AtomicRMWKind> reduction =
4669 arith::symbolizeAtomicRMWKind(attrVal.getValue());
4670 if (!reduction)
4671 return parser.emitError(loc, message: "invalid reduction value: ") << attrVal;
4672 reductions.push_back(
4673 Elt: builder.getI64IntegerAttr(value: static_cast<int64_t>(reduction.value())));
4674 // While we keep getting commas, keep parsing.
4675 return success();
4676 };
4677 if (parser.parseCommaSeparatedList(parseElementFn: parseAttributes) || parser.parseRParen())
4678 return failure();
4679 }
4680 result.addAttribute(name: AffineParallelOp::getReductionsAttrStrName(),
4681 attr: builder.getArrayAttr(value: reductions));
4682
4683 // Parse return types of reductions (if any)
4684 if (parser.parseOptionalArrowTypeList(result&: result.types))
4685 return failure();
4686
4687 // Now parse the body.
4688 Region *body = result.addRegion();
4689 for (auto &iv : ivs)
4690 iv.type = indexType;
4691 if (parser.parseRegion(region&: *body, arguments: ivs) ||
4692 parser.parseOptionalAttrDict(result&: result.attributes))
4693 return failure();
4694
4695 // Add a terminator if none was parsed.
4696 AffineParallelOp::ensureTerminator(region&: *body, builder, loc: result.location);
4697 return success();
4698}
4699
4700//===----------------------------------------------------------------------===//
4701// AffineYieldOp
4702//===----------------------------------------------------------------------===//
4703
4704LogicalResult AffineYieldOp::verify() {
4705 auto *parentOp = (*this)->getParentOp();
4706 auto results = parentOp->getResults();
4707 auto operands = getOperands();
4708
4709 if (!isa<AffineParallelOp, AffineIfOp, AffineForOp>(Val: parentOp))
4710 return emitOpError() << "only terminates affine.if/for/parallel regions";
4711 if (parentOp->getNumResults() != getNumOperands())
4712 return emitOpError() << "parent of yield must have same number of "
4713 "results as the yield operands";
4714 for (auto it : llvm::zip(t&: results, u&: operands)) {
4715 if (std::get<0>(t&: it).getType() != std::get<1>(t&: it).getType())
4716 return emitOpError() << "types mismatch between yield op and its parent";
4717 }
4718
4719 return success();
4720}
4721
4722//===----------------------------------------------------------------------===//
4723// AffineVectorLoadOp
4724//===----------------------------------------------------------------------===//
4725
4726void AffineVectorLoadOp::build(OpBuilder &builder, OperationState &result,
4727 VectorType resultType, AffineMap map,
4728 ValueRange operands,
4729 llvm::MaybeAlign alignment) {
4730 assert(operands.size() == 1 + map.getNumInputs() && "inconsistent operands");
4731 result.addOperands(newOperands: operands);
4732 if (map)
4733 result.addAttribute(name: getMapAttrStrName(), attr: AffineMapAttr::get(value: map));
4734 addAlignmentAttr(builder, result, attrName: getAlignmentAttrName(name: result.name),
4735 alignment);
4736 result.types.push_back(Elt: resultType);
4737}
4738
4739void AffineVectorLoadOp::build(OpBuilder &builder, OperationState &result,
4740 VectorType resultType, Value memref,
4741 AffineMap map, ValueRange mapOperands,
4742 llvm::MaybeAlign alignment) {
4743 assert(map.getNumInputs() == mapOperands.size() && "inconsistent index info");
4744 result.addOperands(newOperands: memref);
4745 result.addOperands(newOperands: mapOperands);
4746 result.addAttribute(name: getMapAttrStrName(), attr: AffineMapAttr::get(value: map));
4747 addAlignmentAttr(builder, result, attrName: getAlignmentAttrName(name: result.name),
4748 alignment);
4749 result.types.push_back(Elt: resultType);
4750}
4751
4752void AffineVectorLoadOp::build(OpBuilder &builder, OperationState &result,
4753 VectorType resultType, Value memref,
4754 ValueRange indices, llvm::MaybeAlign alignment) {
4755 auto memrefType = llvm::cast<MemRefType>(Val: memref.getType());
4756 int64_t rank = memrefType.getRank();
4757 // Create identity map for memrefs with at least one dimension or () -> ()
4758 // for zero-dimensional memrefs.
4759 auto map =
4760 rank ? builder.getMultiDimIdentityMap(rank) : builder.getEmptyAffineMap();
4761 build(builder, result, resultType, memref, map, mapOperands: indices, alignment);
4762}
4763
4764void AffineVectorLoadOp::getCanonicalizationPatterns(RewritePatternSet &results,
4765 MLIRContext *context) {
4766 results.add<SimplifyAffineOp<AffineVectorLoadOp>>(arg&: context);
4767}
4768
4769ParseResult AffineVectorLoadOp::parse(OpAsmParser &parser,
4770 OperationState &result) {
4771 auto &builder = parser.getBuilder();
4772 auto indexTy = builder.getIndexType();
4773
4774 MemRefType memrefType;
4775 VectorType resultType;
4776 OpAsmParser::UnresolvedOperand memrefInfo;
4777 AffineMapAttr mapAttr;
4778 SmallVector<OpAsmParser::UnresolvedOperand, 1> mapOperands;
4779 return failure(
4780 IsFailure: parser.parseOperand(result&: memrefInfo) ||
4781 parser.parseAffineMapOfSSAIds(operands&: mapOperands, map&: mapAttr,
4782 attrName: AffineVectorLoadOp::getMapAttrStrName(),
4783 attrs&: result.attributes) ||
4784 parser.parseOptionalAttrDict(result&: result.attributes) ||
4785 parser.parseColonType(result&: memrefType) || parser.parseComma() ||
4786 parser.parseType(result&: resultType) ||
4787 parser.resolveOperand(operand: memrefInfo, type: memrefType, result&: result.operands) ||
4788 parser.resolveOperands(operands&: mapOperands, type: indexTy, result&: result.operands) ||
4789 parser.addTypeToList(type: resultType, result&: result.types));
4790}
4791
4792void AffineVectorLoadOp::print(OpAsmPrinter &p) {
4793 p << " " << getMemRef() << '[';
4794 if (AffineMapAttr mapAttr = getMapAttr())
4795 p.printAffineMapOfSSAIds(mapAttr, operands: getMapOperands());
4796 p << ']';
4797 SmallVector<NamedAttribute> attrs((*this)->getDiscardableAttrs());
4798 if (IntegerAttr alignment = getAlignmentAttr())
4799 attrs.emplace_back(Args: getAlignmentAttrName(), Args&: alignment);
4800 llvm::sort(C&: attrs);
4801 p.printOptionalAttrDict(attrs);
4802 p << " : " << getMemRefType() << ", " << getType();
4803}
4804
4805/// Verify common invariants of affine.vector_load and affine.vector_store.
4806static LogicalResult verifyVectorMemoryOp(Operation *op, MemRefType memrefType,
4807 VectorType vectorType) {
4808 // Check that memref and vector element types match.
4809 if (memrefType.getElementType() != vectorType.getElementType())
4810 return op->emitOpError(
4811 message: "requires memref and vector types of the same elemental type");
4812 return success();
4813}
4814
4815LogicalResult AffineVectorLoadOp::verify() {
4816 MemRefType memrefType = getMemRefType();
4817 if (failed(Result: verifyMemoryOpIndexing(op: *this, mapAttr: getMapAttr(), mapOperands: getMapOperands(),
4818 memrefType,
4819 /*numIndexOperands=*/getNumOperands() - 1)))
4820 return failure();
4821
4822 if (failed(Result: verifyVectorMemoryOp(op: getOperation(), memrefType, vectorType: getVectorType())))
4823 return failure();
4824
4825 return success();
4826}
4827
4828//===----------------------------------------------------------------------===//
4829// AffineVectorStoreOp
4830//===----------------------------------------------------------------------===//
4831
4832void AffineVectorStoreOp::build(OpBuilder &builder, OperationState &result,
4833 Value valueToStore, Value memref, AffineMap map,
4834 ValueRange mapOperands,
4835 llvm::MaybeAlign alignment) {
4836 assert(map.getNumInputs() == mapOperands.size() && "inconsistent index info");
4837 result.addOperands(newOperands: valueToStore);
4838 result.addOperands(newOperands: memref);
4839 result.addOperands(newOperands: mapOperands);
4840 result.addAttribute(name: getMapAttrStrName(), attr: AffineMapAttr::get(value: map));
4841 addAlignmentAttr(builder, result, attrName: getAlignmentAttrName(name: result.name),
4842 alignment);
4843}
4844
4845// Use identity map.
4846void AffineVectorStoreOp::build(OpBuilder &builder, OperationState &result,
4847 Value valueToStore, Value memref,
4848 ValueRange indices,
4849 llvm::MaybeAlign alignment) {
4850 auto memrefType = llvm::cast<MemRefType>(Val: memref.getType());
4851 int64_t rank = memrefType.getRank();
4852 // Create identity map for memrefs with at least one dimension or () -> ()
4853 // for zero-dimensional memrefs.
4854 auto map =
4855 rank ? builder.getMultiDimIdentityMap(rank) : builder.getEmptyAffineMap();
4856 build(builder, result, valueToStore, memref, map, mapOperands: indices, alignment);
4857}
4858void AffineVectorStoreOp::getCanonicalizationPatterns(
4859 RewritePatternSet &results, MLIRContext *context) {
4860 results.add<SimplifyAffineOp<AffineVectorStoreOp>>(arg&: context);
4861}
4862
4863ParseResult AffineVectorStoreOp::parse(OpAsmParser &parser,
4864 OperationState &result) {
4865 auto indexTy = parser.getBuilder().getIndexType();
4866
4867 MemRefType memrefType;
4868 VectorType resultType;
4869 OpAsmParser::UnresolvedOperand storeValueInfo;
4870 OpAsmParser::UnresolvedOperand memrefInfo;
4871 AffineMapAttr mapAttr;
4872 SmallVector<OpAsmParser::UnresolvedOperand, 1> mapOperands;
4873 return failure(
4874 IsFailure: parser.parseOperand(result&: storeValueInfo) || parser.parseComma() ||
4875 parser.parseOperand(result&: memrefInfo) ||
4876 parser.parseAffineMapOfSSAIds(operands&: mapOperands, map&: mapAttr,
4877 attrName: AffineVectorStoreOp::getMapAttrStrName(),
4878 attrs&: result.attributes) ||
4879 parser.parseOptionalAttrDict(result&: result.attributes) ||
4880 parser.parseColonType(result&: memrefType) || parser.parseComma() ||
4881 parser.parseType(result&: resultType) ||
4882 parser.resolveOperand(operand: storeValueInfo, type: resultType, result&: result.operands) ||
4883 parser.resolveOperand(operand: memrefInfo, type: memrefType, result&: result.operands) ||
4884 parser.resolveOperands(operands&: mapOperands, type: indexTy, result&: result.operands));
4885}
4886
4887void AffineVectorStoreOp::print(OpAsmPrinter &p) {
4888 p << " " << getValueToStore();
4889 p << ", " << getMemRef() << '[';
4890 if (AffineMapAttr mapAttr = getMapAttr())
4891 p.printAffineMapOfSSAIds(mapAttr, operands: getMapOperands());
4892 p << ']';
4893 SmallVector<NamedAttribute> attrs((*this)->getDiscardableAttrs());
4894 if (IntegerAttr alignment = getAlignmentAttr())
4895 attrs.emplace_back(Args: getAlignmentAttrName(), Args&: alignment);
4896 llvm::sort(C&: attrs);
4897 p.printOptionalAttrDict(attrs);
4898 p << " : " << getMemRefType() << ", " << getValueToStore().getType();
4899}
4900
4901LogicalResult AffineVectorStoreOp::verify() {
4902 MemRefType memrefType = getMemRefType();
4903 if (failed(Result: verifyMemoryOpIndexing(op: *this, mapAttr: getMapAttr(), mapOperands: getMapOperands(),
4904 memrefType,
4905 /*numIndexOperands=*/getNumOperands() - 2)))
4906 return failure();
4907
4908 if (failed(Result: verifyVectorMemoryOp(op: *this, memrefType, vectorType: getVectorType())))
4909 return failure();
4910
4911 return success();
4912}
4913
4914//===----------------------------------------------------------------------===//
4915// DelinearizeIndexOp
4916//===----------------------------------------------------------------------===//
4917
4918void AffineDelinearizeIndexOp::build(OpBuilder &odsBuilder,
4919 OperationState &odsState,
4920 Value linearIndex, ValueRange dynamicBasis,
4921 ArrayRef<int64_t> staticBasis,
4922 bool hasOuterBound) {
4923 SmallVector<Type> returnTypes(hasOuterBound ? staticBasis.size()
4924 : staticBasis.size() + 1,
4925 linearIndex.getType());
4926 build(odsBuilder, odsState, multi_index: returnTypes, linear_index: linearIndex, dynamic_basis: dynamicBasis,
4927 static_basis: staticBasis);
4928}
4929
4930void AffineDelinearizeIndexOp::build(OpBuilder &odsBuilder,
4931 OperationState &odsState,
4932 Value linearIndex, ValueRange basis,
4933 bool hasOuterBound) {
4934 if (hasOuterBound && !basis.empty() && basis.front() == nullptr) {
4935 hasOuterBound = false;
4936 basis = basis.drop_front();
4937 }
4938 SmallVector<Value> dynamicBasis;
4939 SmallVector<int64_t> staticBasis;
4940 dispatchIndexOpFoldResults(ofrs: getAsOpFoldResult(values: basis), dynamicVec&: dynamicBasis,
4941 staticVec&: staticBasis);
4942 build(odsBuilder, odsState, linearIndex, dynamicBasis, staticBasis,
4943 hasOuterBound);
4944}
4945
4946void AffineDelinearizeIndexOp::build(OpBuilder &odsBuilder,
4947 OperationState &odsState,
4948 Value linearIndex,
4949 ArrayRef<OpFoldResult> basis,
4950 bool hasOuterBound) {
4951 if (hasOuterBound && !basis.empty() && basis.front() == OpFoldResult()) {
4952 hasOuterBound = false;
4953 basis = basis.drop_front();
4954 }
4955 SmallVector<Value> dynamicBasis;
4956 SmallVector<int64_t> staticBasis;
4957 dispatchIndexOpFoldResults(ofrs: basis, dynamicVec&: dynamicBasis, staticVec&: staticBasis);
4958 build(odsBuilder, odsState, linearIndex, dynamicBasis, staticBasis,
4959 hasOuterBound);
4960}
4961
4962void AffineDelinearizeIndexOp::build(OpBuilder &odsBuilder,
4963 OperationState &odsState,
4964 Value linearIndex, ArrayRef<int64_t> basis,
4965 bool hasOuterBound) {
4966 build(odsBuilder, odsState, linearIndex, dynamicBasis: ValueRange{}, staticBasis: basis, hasOuterBound);
4967}
4968
4969LogicalResult AffineDelinearizeIndexOp::verify() {
4970 ArrayRef<int64_t> staticBasis = getStaticBasis();
4971 if (getNumResults() != staticBasis.size() &&
4972 getNumResults() != staticBasis.size() + 1)
4973 return emitOpError(message: "should return an index for each basis element and up "
4974 "to one extra index");
4975
4976 auto dynamicMarkersCount = llvm::count_if(Range&: staticBasis, P: ShapedType::isDynamic);
4977 if (static_cast<size_t>(dynamicMarkersCount) != getDynamicBasis().size())
4978 return emitOpError(
4979 message: "mismatch between dynamic and static basis (kDynamic marker but no "
4980 "corresponding dynamic basis entry) -- this can only happen due to an "
4981 "incorrect fold/rewrite");
4982
4983 if (!llvm::all_of(Range&: staticBasis, P: [](int64_t v) {
4984 return v > 0 || ShapedType::isDynamic(dValue: v);
4985 }))
4986 return emitOpError(message: "no basis element may be statically non-positive");
4987
4988 return success();
4989}
4990
4991/// Given mixed basis of affine.delinearize_index/linearize_index replace
4992/// constant SSA values with the constant integer value and return the new
4993/// static basis. In case no such candidate for replacement exists, this utility
4994/// returns std::nullopt.
4995static std::optional<SmallVector<int64_t>>
4996foldCstValueToCstAttrBasis(ArrayRef<OpFoldResult> mixedBasis,
4997 MutableOperandRange mutableDynamicBasis,
4998 ArrayRef<Attribute> dynamicBasis) {
4999 uint64_t dynamicBasisIndex = 0;
5000 for (Attribute basis : dynamicBasis) {
5001 // Skip poison values: they don't have a concrete integer value, so erasing
5002 // them from the dynamic operands would create an inconsistency between
5003 // the static basis (which would still hold kDynamic) and the dynamic
5004 // operand list (which would be one element shorter).
5005 if (basis && isa<IntegerAttr>(Val: basis)) {
5006 mutableDynamicBasis.erase(subStart: dynamicBasisIndex);
5007 } else {
5008 ++dynamicBasisIndex;
5009 }
5010 }
5011
5012 // No constant SSA value exists.
5013 if (dynamicBasisIndex == dynamicBasis.size())
5014 return std::nullopt;
5015
5016 SmallVector<int64_t> staticBasis;
5017 for (OpFoldResult basis : mixedBasis) {
5018 std::optional<int64_t> basisVal = getConstantIntValue(ofr: basis);
5019 if (!basisVal)
5020 staticBasis.push_back(Elt: ShapedType::kDynamic);
5021 else
5022 staticBasis.push_back(Elt: *basisVal);
5023 }
5024
5025 return staticBasis;
5026}
5027
5028LogicalResult
5029AffineDelinearizeIndexOp::fold(FoldAdaptor adaptor,
5030 SmallVectorImpl<OpFoldResult> &result) {
5031 std::optional<SmallVector<int64_t>> maybeStaticBasis =
5032 foldCstValueToCstAttrBasis(mixedBasis: getMixedBasis(), mutableDynamicBasis: getDynamicBasisMutable(),
5033 dynamicBasis: adaptor.getDynamicBasis());
5034 if (maybeStaticBasis) {
5035 setStaticBasis(*maybeStaticBasis);
5036 return success();
5037 }
5038 // If we won't be doing any division or modulo (no basis or the one basis
5039 // element is purely advisory), simply return the input value.
5040 if (getNumResults() == 1) {
5041 result.push_back(Elt: getLinearIndex());
5042 return success();
5043 }
5044
5045 if (adaptor.getLinearIndex() == nullptr)
5046 return failure();
5047
5048 if (!adaptor.getDynamicBasis().empty())
5049 return failure();
5050
5051 int64_t highPart = cast<IntegerAttr>(Val: adaptor.getLinearIndex()).getInt();
5052 Type attrType = getLinearIndex().getType();
5053
5054 ArrayRef<int64_t> staticBasis = getStaticBasis();
5055 if (hasOuterBound())
5056 staticBasis = staticBasis.drop_front();
5057 for (int64_t modulus : llvm::reverse(C&: staticBasis)) {
5058 result.push_back(Elt: IntegerAttr::get(type: attrType, value: llvm::mod(Numerator: highPart, Denominator: modulus)));
5059 highPart = llvm::divideFloorSigned(Numerator: highPart, Denominator: modulus);
5060 }
5061 result.push_back(Elt: IntegerAttr::get(type: attrType, value: highPart));
5062 std::reverse(first: result.begin(), last: result.end());
5063 return success();
5064}
5065
5066SmallVector<OpFoldResult> AffineDelinearizeIndexOp::getEffectiveBasis() {
5067 OpBuilder builder(getContext());
5068 if (hasOuterBound()) {
5069 if (getStaticBasis().front() == ::mlir::ShapedType::kDynamic)
5070 return getMixedValues(staticValues: getStaticBasis().drop_front(),
5071 dynamicValues: getDynamicBasis().drop_front(), b&: builder);
5072
5073 return getMixedValues(staticValues: getStaticBasis().drop_front(), dynamicValues: getDynamicBasis(),
5074 b&: builder);
5075 }
5076
5077 return getMixedValues(staticValues: getStaticBasis(), dynamicValues: getDynamicBasis(), b&: builder);
5078}
5079
5080SmallVector<OpFoldResult> AffineDelinearizeIndexOp::getPaddedBasis() {
5081 SmallVector<OpFoldResult> ret = getMixedBasis();
5082 if (!hasOuterBound())
5083 ret.insert(I: ret.begin(), Elt: OpFoldResult());
5084 return ret;
5085}
5086
5087namespace {
5088// Drops delinearization indices that correspond to unit-extent basis
5089struct DropUnitExtentBasis
5090 : public OpRewritePattern<affine::AffineDelinearizeIndexOp> {
5091 using Base::Base;
5092
5093 LogicalResult matchAndRewrite(affine::AffineDelinearizeIndexOp delinearizeOp,
5094 PatternRewriter &rewriter) const override {
5095 SmallVector<Value> replacements(delinearizeOp->getNumResults(), nullptr);
5096 std::optional<Value> zero = std::nullopt;
5097 Location loc = delinearizeOp->getLoc();
5098 Type indexType = delinearizeOp.getLinearIndex().getType();
5099 auto getZero = [&]() -> Value {
5100 if (!zero)
5101 zero = arith::ConstantOp::create(builder&: rewriter, location: loc,
5102 value: rewriter.getZeroAttr(type: indexType));
5103 return zero.value();
5104 };
5105
5106 // Replace all indices corresponding to unit-extent basis with 0.
5107 // Remaining basis can be used to get a new `affine.delinearize_index` op.
5108 SmallVector<OpFoldResult> newBasis;
5109 for (auto [index, basis] :
5110 llvm::enumerate(First: delinearizeOp.getPaddedBasis())) {
5111 std::optional<int64_t> basisVal =
5112 basis ? getConstantIntValue(ofr: basis) : std::nullopt;
5113 if (basisVal == 1)
5114 replacements[index] = getZero();
5115 else
5116 newBasis.push_back(Elt: basis);
5117 }
5118
5119 if (newBasis.size() == delinearizeOp.getNumResults())
5120 return rewriter.notifyMatchFailure(arg&: delinearizeOp,
5121 msg: "no unit basis elements");
5122
5123 if (!newBasis.empty()) {
5124 // Will drop the leading nullptr from `basis` if there was no outer bound.
5125 auto newDelinearizeOp = affine::AffineDelinearizeIndexOp::create(
5126 builder&: rewriter, location: loc, linear_index: delinearizeOp.getLinearIndex(), basis: newBasis);
5127 int newIndex = 0;
5128 // Map back the new delinearized indices to the values they replace.
5129 for (auto &replacement : replacements) {
5130 if (replacement)
5131 continue;
5132 replacement = newDelinearizeOp->getResult(idx: newIndex++);
5133 }
5134 }
5135
5136 rewriter.replaceOp(op: delinearizeOp, newValues: replacements);
5137 return success();
5138 }
5139};
5140
5141/// If a `affine.delinearize_index`'s input is a `affine.linearize_index
5142/// disjoint` and the two operations end with the same basis elements,
5143/// cancel those parts of the operations out because they are inverses
5144/// of each other.
5145///
5146/// If the operations have the same basis, cancel them entirely.
5147///
5148/// The `disjoint` flag is needed on the `affine.linearize_index` because
5149/// otherwise, there is no guarantee that the inputs to the linearization are
5150/// in-bounds the way the outputs of the delinearization would be.
5151struct CancelDelinearizeOfLinearizeDisjointExactTail
5152 : public OpRewritePattern<affine::AffineDelinearizeIndexOp> {
5153 using Base::Base;
5154
5155 LogicalResult matchAndRewrite(affine::AffineDelinearizeIndexOp delinearizeOp,
5156 PatternRewriter &rewriter) const override {
5157 auto linearizeOp = delinearizeOp.getLinearIndex()
5158 .getDefiningOp<affine::AffineLinearizeIndexOp>();
5159 if (!linearizeOp)
5160 return rewriter.notifyMatchFailure(arg&: delinearizeOp,
5161 msg: "index doesn't come from linearize");
5162
5163 if (!linearizeOp.getDisjoint())
5164 return rewriter.notifyMatchFailure(arg&: linearizeOp, msg: "not disjoint");
5165
5166 ValueRange linearizeIns = linearizeOp.getMultiIndex();
5167 // Note: we use the full basis so we don't lose outer bounds later.
5168 SmallVector<OpFoldResult> linearizeBasis = linearizeOp.getMixedBasis();
5169 SmallVector<OpFoldResult> delinearizeBasis = delinearizeOp.getMixedBasis();
5170 size_t numMatches = 0;
5171 for (auto [linSize, delinSize] : llvm::zip(
5172 t: llvm::reverse(C&: linearizeBasis), u: llvm::reverse(C&: delinearizeBasis))) {
5173 if (linSize != delinSize)
5174 break;
5175 ++numMatches;
5176 }
5177
5178 if (numMatches == 0)
5179 return rewriter.notifyMatchFailure(
5180 arg&: delinearizeOp, msg: "final basis element doesn't match linearize");
5181
5182 // The easy case: everything lines up and the basis match sup completely.
5183 if (numMatches == linearizeBasis.size() &&
5184 numMatches == delinearizeBasis.size() &&
5185 linearizeIns.size() == delinearizeOp.getNumResults()) {
5186 rewriter.replaceOp(op: delinearizeOp, newValues: linearizeOp.getMultiIndex());
5187 return success();
5188 }
5189
5190 Value newLinearize = affine::AffineLinearizeIndexOp::create(
5191 builder&: rewriter, location: linearizeOp.getLoc(), multi_index: linearizeIns.drop_back(n: numMatches),
5192 basis: ArrayRef<OpFoldResult>{linearizeBasis}.drop_back(N: numMatches),
5193 disjoint: linearizeOp.getDisjoint());
5194 auto newDelinearize = affine::AffineDelinearizeIndexOp::create(
5195 builder&: rewriter, location: delinearizeOp.getLoc(), linear_index: newLinearize,
5196 basis: ArrayRef<OpFoldResult>{delinearizeBasis}.drop_back(N: numMatches),
5197 hasOuterBound: delinearizeOp.hasOuterBound());
5198 SmallVector<Value> mergedResults(newDelinearize.getResults());
5199 mergedResults.append(in_start: linearizeIns.take_back(n: numMatches).begin(),
5200 in_end: linearizeIns.take_back(n: numMatches).end());
5201 rewriter.replaceOp(op: delinearizeOp, newValues: mergedResults);
5202 return success();
5203 }
5204};
5205
5206/// If the input to a delinearization is a disjoint linearization, and the
5207/// last k > 1 components of the delinearization basis multiply to the
5208/// last component of the linearization basis, break the linearization and
5209/// delinearization into two parts, peeling off the last input to linearization.
5210/// The split does not apply when it would consume an entire outer-bounded
5211/// delinearization basis because earlier linearization inputs still contribute
5212/// to the first delinearized result.
5213///
5214/// For example:
5215/// %0 = affine.linearize_index [%z, %y, %x] by (3, 2, 32) : index
5216/// %1:4 = affine.delinearize_index %0 by (2, 3, 8, 4) : index, ...
5217/// becomes
5218/// %0 = affine.linearize_index [%z, %y] by (3, 2) : index
5219/// %1:2 = affine.delinearize_index %0 by (2, 3) : index
5220/// %2:2 = affine.delinearize_index %x by (8, 4) : index
5221/// where the original %1:4 is replaced by %1:2 ++ %2:2
5222struct SplitDelinearizeSpanningLastLinearizeArg final
5223 : OpRewritePattern<affine::AffineDelinearizeIndexOp> {
5224 using Base::Base;
5225
5226 LogicalResult matchAndRewrite(affine::AffineDelinearizeIndexOp delinearizeOp,
5227 PatternRewriter &rewriter) const override {
5228 auto linearizeOp = delinearizeOp.getLinearIndex()
5229 .getDefiningOp<affine::AffineLinearizeIndexOp>();
5230 if (!linearizeOp)
5231 return rewriter.notifyMatchFailure(arg&: delinearizeOp,
5232 msg: "index doesn't come from linearize");
5233
5234 if (!linearizeOp.getDisjoint())
5235 return rewriter.notifyMatchFailure(arg&: linearizeOp,
5236 msg: "linearize isn't disjoint");
5237
5238 // A linearize with no inputs has an empty basis and folds to a constant
5239 // zero; there is nothing to split, and reading its last basis element
5240 // below would be out of bounds.
5241 if (linearizeOp.getStaticBasis().empty())
5242 return rewriter.notifyMatchFailure(
5243 arg&: linearizeOp, msg: "linearize has no basis elements (no inputs)");
5244
5245 int64_t target = linearizeOp.getStaticBasis().back();
5246 if (ShapedType::isDynamic(dValue: target))
5247 return rewriter.notifyMatchFailure(
5248 arg&: linearizeOp, msg: "linearize ends with dynamic basis value");
5249
5250 int64_t sizeToSplit = 1;
5251 size_t elemsToSplit = 0;
5252 ArrayRef<int64_t> basis = delinearizeOp.getStaticBasis();
5253 for (int64_t basisElem : llvm::reverse(C&: basis)) {
5254 if (ShapedType::isDynamic(dValue: basisElem))
5255 return rewriter.notifyMatchFailure(
5256 arg&: delinearizeOp, msg: "dynamic basis element while scanning for split");
5257 sizeToSplit *= basisElem;
5258 elemsToSplit += 1;
5259
5260 if (sizeToSplit > target)
5261 return rewriter.notifyMatchFailure(arg&: delinearizeOp,
5262 msg: "overshot last argument size");
5263 if (sizeToSplit == target)
5264 break;
5265 }
5266
5267 if (sizeToSplit < target)
5268 return rewriter.notifyMatchFailure(
5269 arg&: delinearizeOp, msg: "product of known basis elements doesn't exceed last "
5270 "linearize argument");
5271
5272 if (elemsToSplit < 2)
5273 return rewriter.notifyMatchFailure(
5274 arg&: delinearizeOp,
5275 msg: "need at least two elements to form the basis product");
5276
5277 if (elemsToSplit == basis.size() && delinearizeOp.hasOuterBound())
5278 return rewriter.notifyMatchFailure(
5279 arg&: delinearizeOp, msg: "split would consume entire bounded basis");
5280
5281 Value linearizeWithoutBack = affine::AffineLinearizeIndexOp::create(
5282 builder&: rewriter, location: linearizeOp.getLoc(), linear_index: linearizeOp.getLinearIndex().getType(),
5283 multi_index: linearizeOp.getMultiIndex().drop_back(), dynamic_basis: linearizeOp.getDynamicBasis(),
5284 static_basis: linearizeOp.getStaticBasis().drop_back(), disjoint: linearizeOp.getDisjoint());
5285 auto delinearizeWithoutSplitPart = affine::AffineDelinearizeIndexOp::create(
5286 builder&: rewriter, location: delinearizeOp.getLoc(), linear_index: linearizeWithoutBack,
5287 dynamic_basis: delinearizeOp.getDynamicBasis(), static_basis: basis.drop_back(N: elemsToSplit),
5288 hasOuterBound: delinearizeOp.hasOuterBound());
5289 auto delinearizeBack = affine::AffineDelinearizeIndexOp::create(
5290 builder&: rewriter, location: delinearizeOp.getLoc(), linear_index: linearizeOp.getMultiIndex().back(),
5291 basis: basis.take_back(N: elemsToSplit), /*hasOuterBound=*/true);
5292 SmallVector<Value> results = llvm::to_vector(
5293 Range: llvm::concat<Value>(Ranges: delinearizeWithoutSplitPart.getResults(),
5294 Ranges: delinearizeBack.getResults()));
5295 rewriter.replaceOp(op: delinearizeOp, newValues: results);
5296
5297 return success();
5298 }
5299};
5300} // namespace
5301
5302void affine::AffineDelinearizeIndexOp::getCanonicalizationPatterns(
5303 RewritePatternSet &patterns, MLIRContext *context) {
5304 patterns
5305 .insert<CancelDelinearizeOfLinearizeDisjointExactTail,
5306 DropUnitExtentBasis, SplitDelinearizeSpanningLastLinearizeArg>(
5307 arg&: context);
5308}
5309
5310//===----------------------------------------------------------------------===//
5311// LinearizeIndexOp
5312//===----------------------------------------------------------------------===//
5313
5314/// Infer the index type from a set of multi-index values. Returns the common
5315/// type (index or vector<...xindex>), or IndexType if the set is empty.
5316static Type inferIndexType(MLIRContext *ctx, ValueRange multiIndex) {
5317 if (multiIndex.empty())
5318 return IndexType::get(context: ctx);
5319 return multiIndex.front().getType();
5320}
5321
5322void AffineLinearizeIndexOp::build(OpBuilder &odsBuilder,
5323 OperationState &odsState,
5324 ValueRange multiIndex, ValueRange basis,
5325 bool disjoint) {
5326 if (!basis.empty() && basis.front() == Value())
5327 basis = basis.drop_front();
5328 SmallVector<Value> dynamicBasis;
5329 SmallVector<int64_t> staticBasis;
5330 dispatchIndexOpFoldResults(ofrs: getAsOpFoldResult(values: basis), dynamicVec&: dynamicBasis,
5331 staticVec&: staticBasis);
5332 Type resultType = inferIndexType(ctx: odsBuilder.getContext(), multiIndex);
5333 build(odsBuilder, odsState, linear_index: resultType, multi_index: multiIndex, dynamic_basis: dynamicBasis, static_basis: staticBasis,
5334 disjoint);
5335}
5336
5337void AffineLinearizeIndexOp::build(OpBuilder &odsBuilder,
5338 OperationState &odsState,
5339 ValueRange multiIndex,
5340 ArrayRef<OpFoldResult> basis,
5341 bool disjoint) {
5342 if (!basis.empty() && basis.front() == OpFoldResult())
5343 basis = basis.drop_front();
5344 SmallVector<Value> dynamicBasis;
5345 SmallVector<int64_t> staticBasis;
5346 dispatchIndexOpFoldResults(ofrs: basis, dynamicVec&: dynamicBasis, staticVec&: staticBasis);
5347 Type resultType = inferIndexType(ctx: odsBuilder.getContext(), multiIndex);
5348 build(odsBuilder, odsState, linear_index: resultType, multi_index: multiIndex, dynamic_basis: dynamicBasis, static_basis: staticBasis,
5349 disjoint);
5350}
5351
5352void AffineLinearizeIndexOp::build(OpBuilder &odsBuilder,
5353 OperationState &odsState,
5354 ValueRange multiIndex,
5355 ArrayRef<int64_t> basis, bool disjoint) {
5356 Type resultType = inferIndexType(ctx: odsBuilder.getContext(), multiIndex);
5357 build(odsBuilder, odsState, linear_index: resultType, multi_index: multiIndex, dynamic_basis: ValueRange{}, static_basis: basis,
5358 disjoint);
5359}
5360
5361LogicalResult AffineLinearizeIndexOp::verify() {
5362 size_t numIndexes = getMultiIndex().size();
5363 size_t numBasisElems = getStaticBasis().size();
5364 if (numIndexes != numBasisElems && numIndexes != numBasisElems + 1)
5365 return emitOpError(message: "should be passed a basis element for each index except "
5366 "possibly the first");
5367
5368 auto dynamicMarkersCount =
5369 llvm::count_if(Range: getStaticBasis(), P: ShapedType::isDynamic);
5370 if (static_cast<size_t>(dynamicMarkersCount) != getDynamicBasis().size())
5371 return emitOpError(
5372 message: "mismatch between dynamic and static basis (kDynamic marker but no "
5373 "corresponding dynamic basis entry) -- this can only happen due to an "
5374 "incorrect fold/rewrite");
5375
5376 return success();
5377}
5378
5379OpFoldResult AffineLinearizeIndexOp::fold(FoldAdaptor adaptor) {
5380 std::optional<SmallVector<int64_t>> maybeStaticBasis =
5381 foldCstValueToCstAttrBasis(mixedBasis: getMixedBasis(), mutableDynamicBasis: getDynamicBasisMutable(),
5382 dynamicBasis: adaptor.getDynamicBasis());
5383 if (maybeStaticBasis) {
5384 setStaticBasis(*maybeStaticBasis);
5385 return getResult();
5386 }
5387 // No indices linearizes to zero.
5388 if (getMultiIndex().empty())
5389 return IntegerAttr::get(type: getResult().getType(), value: 0);
5390
5391 // One single index linearizes to itself.
5392 if (getMultiIndex().size() == 1)
5393 return getMultiIndex().front();
5394
5395 // Return nullptr if any multi-index attribute has not been folded to a
5396 // concrete integer (e.g. it is still a runtime value or has folded to a
5397 // non-integer attribute such as #ub.poison).
5398 if (llvm::any_of(Range: adaptor.getMultiIndex(), P: [](Attribute a) {
5399 return !isa_and_nonnull<IntegerAttr>(Val: a);
5400 }))
5401 return nullptr;
5402
5403 if (!adaptor.getDynamicBasis().empty())
5404 return nullptr;
5405
5406 int64_t result = 0;
5407 int64_t stride = 1;
5408 for (auto [length, indexAttr] :
5409 llvm::zip_first(t: llvm::reverse(C: getStaticBasis()),
5410 u: llvm::reverse(C: adaptor.getMultiIndex()))) {
5411 result = result + cast<IntegerAttr>(Val: indexAttr).getInt() * stride;
5412 stride = stride * length;
5413 }
5414 // Handle the index element with no basis element.
5415 if (!hasOuterBound())
5416 result =
5417 result +
5418 cast<IntegerAttr>(Val: adaptor.getMultiIndex().front()).getInt() * stride;
5419
5420 return IntegerAttr::get(type: getResult().getType(), value: result);
5421}
5422
5423SmallVector<OpFoldResult> AffineLinearizeIndexOp::getEffectiveBasis() {
5424 OpBuilder builder(getContext());
5425 if (hasOuterBound()) {
5426 if (getStaticBasis().front() == ::mlir::ShapedType::kDynamic)
5427 return getMixedValues(staticValues: getStaticBasis().drop_front(),
5428 dynamicValues: getDynamicBasis().drop_front(), b&: builder);
5429
5430 return getMixedValues(staticValues: getStaticBasis().drop_front(), dynamicValues: getDynamicBasis(),
5431 b&: builder);
5432 }
5433
5434 return getMixedValues(staticValues: getStaticBasis(), dynamicValues: getDynamicBasis(), b&: builder);
5435}
5436
5437SmallVector<OpFoldResult> AffineLinearizeIndexOp::getPaddedBasis() {
5438 SmallVector<OpFoldResult> ret = getMixedBasis();
5439 if (!hasOuterBound())
5440 ret.insert(I: ret.begin(), Elt: OpFoldResult());
5441 return ret;
5442}
5443
5444namespace {
5445/// Rewrite `affine.linearize_index disjoint [%...a, %x, %...b] by (%...c, 1,
5446/// %...d)` to `affine.linearize_index disjoint [%...a, %...b] by (%...c,
5447/// %...d)`.
5448
5449/// Note that `disjoint` is required here, because, without it, we could have
5450/// `affine.linearize_index [%...a, %c64, %...b] by (%...c, 1, %...d)`
5451/// is a valid operation where the `%c64` cannot be trivially dropped.
5452///
5453/// Alternatively, if `%x` in the above is a known constant 0, remove it even if
5454/// the operation isn't asserted to be `disjoint`.
5455struct DropLinearizeUnitComponentsIfDisjointOrZero final
5456 : OpRewritePattern<affine::AffineLinearizeIndexOp> {
5457 using Base::Base;
5458
5459 LogicalResult matchAndRewrite(affine::AffineLinearizeIndexOp op,
5460 PatternRewriter &rewriter) const override {
5461 ValueRange multiIndex = op.getMultiIndex();
5462 size_t numIndices = multiIndex.size();
5463 SmallVector<Value> newIndices;
5464 newIndices.reserve(N: numIndices);
5465 SmallVector<OpFoldResult> newBasis;
5466 newBasis.reserve(N: numIndices);
5467
5468 if (!op.hasOuterBound()) {
5469 newIndices.push_back(Elt: multiIndex.front());
5470 multiIndex = multiIndex.drop_front();
5471 }
5472
5473 SmallVector<OpFoldResult> basis = op.getMixedBasis();
5474 for (auto [index, basisElem] : llvm::zip_equal(t&: multiIndex, u&: basis)) {
5475 std::optional<int64_t> basisEntry = getConstantIntValue(ofr: basisElem);
5476 if (!basisEntry || *basisEntry != 1) {
5477 newIndices.push_back(Elt: index);
5478 newBasis.push_back(Elt: basisElem);
5479 continue;
5480 }
5481
5482 std::optional<int64_t> indexValue = getConstantIntValue(ofr: index);
5483 if (!op.getDisjoint() && (!indexValue || *indexValue != 0)) {
5484 newIndices.push_back(Elt: index);
5485 newBasis.push_back(Elt: basisElem);
5486 continue;
5487 }
5488 }
5489 if (newIndices.size() == numIndices)
5490 return rewriter.notifyMatchFailure(arg&: op,
5491 msg: "no unit basis entries to replace");
5492
5493 if (newIndices.empty()) {
5494 rewriter.replaceOpWithNewOp<arith::ConstantOp>(
5495 op, args: rewriter.getZeroAttr(type: op.getLinearIndex().getType()));
5496 return success();
5497 }
5498 rewriter.replaceOpWithNewOp<affine::AffineLinearizeIndexOp>(
5499 op, args&: newIndices, args&: newBasis, args: op.getDisjoint());
5500 return success();
5501 }
5502};
5503
5504OpFoldResult computeProduct(Location loc, OpBuilder &builder,
5505 ArrayRef<OpFoldResult> terms) {
5506 int64_t nDynamic = 0;
5507 SmallVector<Value> dynamicPart;
5508 AffineExpr result = builder.getAffineConstantExpr(constant: 1);
5509 for (OpFoldResult term : terms) {
5510 if (!term)
5511 return term;
5512 std::optional<int64_t> maybeConst = getConstantIntValue(ofr: term);
5513 if (maybeConst) {
5514 result = result * builder.getAffineConstantExpr(constant: *maybeConst);
5515 } else {
5516 dynamicPart.push_back(Elt: cast<Value>(Val&: term));
5517 result = result * builder.getAffineSymbolExpr(position: nDynamic++);
5518 }
5519 }
5520 if (auto constant = dyn_cast<AffineConstantExpr>(Val&: result))
5521 return getAsIndexOpFoldResult(ctx: builder.getContext(), val: constant.getValue());
5522 return AffineApplyOp::create(builder, location: loc, exprList: result, mapOperands: dynamicPart).getResult();
5523}
5524
5525/// If conseceutive outputs of a delinearize_index are linearized with the same
5526/// bounds, canonicalize away the redundant arithmetic.
5527///
5528/// That is, if we have
5529/// ```
5530/// %s:N = affine.delinearize_index %x into (...a, B1, B2, ... BK, ...b)
5531/// %t = affine.linearize_index [...c, %s#I, %s#(I + 1), ... %s#(I+K-1), ...d]
5532/// by (...e, B1, B2, ..., BK, ...f)
5533/// ```
5534///
5535/// We can rewrite this to
5536/// ```
5537/// B = B1 * B2 ... BK
5538/// %sMerged:(N-K+1) affine.delinearize_index %x into (...a, B, ...b)
5539/// %t = affine.linearize_index [...c, %s#I, ...d] by (...e, B, ...f)
5540/// ```
5541/// where we replace all results of %s unaffected by the change with results
5542/// from %sMerged.
5543///
5544/// As a special case, if all results of the delinearize are merged in this way
5545/// we can replace those usages with %x, thus cancelling the delinearization
5546/// entirely, as in
5547/// ```
5548/// %s:3 = affine.delinearize_index %x into (2, 4, 8)
5549/// %t = affine.linearize_index [%s#0, %s#1, %s#2, %c0] by (2, 4, 8, 16)
5550/// ```
5551/// becoming `%t = affine.linearize_index [%x, %c0] by (64, 16)`
5552struct CancelLinearizeOfDelinearizePortion final
5553 : OpRewritePattern<affine::AffineLinearizeIndexOp> {
5554 using Base::Base;
5555
5556private:
5557 // Struct representing a case where the cancellation pattern
5558 // applies. A `Match` means that `length` inputs to the linearize operation
5559 // starting at `linStart` can be cancelled with `length` outputs of
5560 // `delinearize`, starting from `delinStart`.
5561 struct Match {
5562 AffineDelinearizeIndexOp delinearize;
5563 unsigned linStart = 0;
5564 unsigned delinStart = 0;
5565 unsigned length = 0;
5566 };
5567
5568public:
5569 LogicalResult matchAndRewrite(affine::AffineLinearizeIndexOp linearizeOp,
5570 PatternRewriter &rewriter) const override {
5571 SmallVector<Match> matches;
5572
5573 const SmallVector<OpFoldResult> linBasis = linearizeOp.getPaddedBasis();
5574 ArrayRef<OpFoldResult> linBasisRef = linBasis;
5575
5576 ValueRange multiIndex = linearizeOp.getMultiIndex();
5577 unsigned numLinArgs = multiIndex.size();
5578 unsigned linArgIdx = 0;
5579 // We only want to replace one run from the same delinearize op per
5580 // pattern invocation lest we run into invalidation issues.
5581 llvm::SmallPtrSet<Operation *, 2> alreadyMatchedDelinearize;
5582 while (linArgIdx < numLinArgs) {
5583 auto asResult = dyn_cast<OpResult>(Val: multiIndex[linArgIdx]);
5584 if (!asResult) {
5585 linArgIdx++;
5586 continue;
5587 }
5588
5589 auto delinearizeOp =
5590 dyn_cast<AffineDelinearizeIndexOp>(Val: asResult.getOwner());
5591 if (!delinearizeOp) {
5592 linArgIdx++;
5593 continue;
5594 }
5595
5596 /// Result 0 of the delinearize and argument 0 of the linearize can
5597 /// leave their maximum value unspecified. However, even if this happens
5598 /// we can still sometimes start the match process. Specifically, if
5599 /// - The argument we're matching is result 0 and argument 0 (so the
5600 /// bounds don't matter). For example,
5601 ///
5602 /// %0:2 = affine.delinearize_index %x into (8) : index, index
5603 /// %1 = affine.linearize_index [%s#0, %s#1, ...] (8, ...)
5604 /// allows cancellation
5605 /// - The delinearization doesn't specify a bound, but the linearization
5606 /// is `disjoint`, which asserts that the bound on the linearization is
5607 /// correct.
5608 unsigned delinArgIdx = asResult.getResultNumber();
5609 SmallVector<OpFoldResult> delinBasis = delinearizeOp.getPaddedBasis();
5610 OpFoldResult firstDelinBound = delinBasis[delinArgIdx];
5611 OpFoldResult firstLinBound = linBasis[linArgIdx];
5612 bool boundsMatch = firstDelinBound == firstLinBound;
5613 bool bothAtFront = linArgIdx == 0 && delinArgIdx == 0;
5614 bool knownByDisjoint =
5615 linearizeOp.getDisjoint() && delinArgIdx == 0 && !firstDelinBound;
5616 if (!boundsMatch && !bothAtFront && !knownByDisjoint) {
5617 linArgIdx++;
5618 continue;
5619 }
5620
5621 unsigned j = 1;
5622 unsigned numDelinOuts = delinearizeOp.getNumResults();
5623 for (; j + linArgIdx < numLinArgs && j + delinArgIdx < numDelinOuts;
5624 ++j) {
5625 if (multiIndex[linArgIdx + j] !=
5626 delinearizeOp.getResult(i: delinArgIdx + j))
5627 break;
5628 if (linBasis[linArgIdx + j] != delinBasis[delinArgIdx + j])
5629 break;
5630 }
5631 // If there're multiple matches against the same delinearize_index,
5632 // only rewrite the first one we find to prevent invalidations. The next
5633 // ones will be taken care of by subsequent pattern invocations.
5634 if (j <= 1 || !alreadyMatchedDelinearize.insert(Ptr: delinearizeOp).second) {
5635 linArgIdx++;
5636 continue;
5637 }
5638 matches.push_back(Elt: Match{.delinearize: delinearizeOp, .linStart: linArgIdx, .delinStart: delinArgIdx, .length: j});
5639 linArgIdx += j;
5640 }
5641
5642 if (matches.empty())
5643 return rewriter.notifyMatchFailure(
5644 arg&: linearizeOp, msg: "no run of delinearize outputs to deal with");
5645
5646 // Record all the delinearize replacements so we can do them after creating
5647 // the new linearization operation, since the new operation might use
5648 // outputs of something we're replacing.
5649 SmallVector<SmallVector<Value>> delinearizeReplacements;
5650
5651 SmallVector<Value> newIndex;
5652 newIndex.reserve(N: numLinArgs);
5653 SmallVector<OpFoldResult> newBasis;
5654 newBasis.reserve(N: numLinArgs);
5655 unsigned prevMatchEnd = 0;
5656 for (Match m : matches) {
5657 unsigned gap = m.linStart - prevMatchEnd;
5658 llvm::append_range(C&: newIndex, R: multiIndex.slice(n: prevMatchEnd, m: gap));
5659 llvm::append_range(C&: newBasis, R: linBasisRef.slice(N: prevMatchEnd, M: gap));
5660 // Update here so we don't forget this during early continues
5661 prevMatchEnd = m.linStart + m.length;
5662
5663 PatternRewriter::InsertionGuard g(rewriter);
5664 rewriter.setInsertionPoint(m.delinearize);
5665
5666 ArrayRef<OpFoldResult> basisToMerge =
5667 linBasisRef.slice(N: m.linStart, M: m.length);
5668 // We use the slice from the linearize's basis above because of the
5669 // "bounds inferred from `disjoint`" case above.
5670 OpFoldResult newSize =
5671 computeProduct(loc: linearizeOp.getLoc(), builder&: rewriter, terms: basisToMerge);
5672
5673 // Trivial case where we can just skip past the delinearize all together
5674 if (m.length == m.delinearize.getNumResults()) {
5675 newIndex.push_back(Elt: m.delinearize.getLinearIndex());
5676 newBasis.push_back(Elt: newSize);
5677 // Pad out set of replacements so we don't do anything with this one.
5678 delinearizeReplacements.push_back(Elt: SmallVector<Value>());
5679 continue;
5680 }
5681
5682 SmallVector<Value> newDelinResults;
5683 SmallVector<OpFoldResult> newDelinBasis = m.delinearize.getPaddedBasis();
5684 newDelinBasis.erase(CS: newDelinBasis.begin() + m.delinStart,
5685 CE: newDelinBasis.begin() + m.delinStart + m.length);
5686 newDelinBasis.insert(I: newDelinBasis.begin() + m.delinStart, Elt: newSize);
5687 auto newDelinearize = AffineDelinearizeIndexOp::create(
5688 builder&: rewriter, location: m.delinearize.getLoc(), linear_index: m.delinearize.getLinearIndex(),
5689 basis: newDelinBasis);
5690
5691 // Since there may be other uses of the indices we just merged together,
5692 // create a residual affine.delinearize_index that delinearizes the
5693 // merged output into its component parts.
5694 Value combinedElem = newDelinearize.getResult(i: m.delinStart);
5695 auto residualDelinearize = AffineDelinearizeIndexOp::create(
5696 builder&: rewriter, location: m.delinearize.getLoc(), linear_index: combinedElem, basis: basisToMerge);
5697
5698 // Swap all the uses of the unaffected delinearize outputs to the new
5699 // delinearization so that the old code can be removed if this
5700 // linearize_index is the only user of the merged results.
5701 llvm::append_range(C&: newDelinResults,
5702 R: newDelinearize.getResults().take_front(n: m.delinStart));
5703 llvm::append_range(C&: newDelinResults, R: residualDelinearize.getResults());
5704 llvm::append_range(
5705 C&: newDelinResults,
5706 R: newDelinearize.getResults().drop_front(n: m.delinStart + 1));
5707
5708 delinearizeReplacements.push_back(Elt: newDelinResults);
5709 newIndex.push_back(Elt: combinedElem);
5710 newBasis.push_back(Elt: newSize);
5711 }
5712 llvm::append_range(C&: newIndex, R: multiIndex.drop_front(n: prevMatchEnd));
5713 llvm::append_range(C&: newBasis, R: linBasisRef.drop_front(N: prevMatchEnd));
5714 rewriter.replaceOpWithNewOp<AffineLinearizeIndexOp>(
5715 op: linearizeOp, args&: newIndex, args&: newBasis, args: linearizeOp.getDisjoint());
5716
5717 for (auto [m, newResults] :
5718 llvm::zip_equal(t&: matches, u&: delinearizeReplacements)) {
5719 if (newResults.empty())
5720 continue;
5721 rewriter.replaceOp(op: m.delinearize, newValues: newResults);
5722 }
5723
5724 return success();
5725 }
5726};
5727
5728/// Strip leading zero from affine.linearize_index.
5729///
5730/// `affine.linearize_index [%c0, ...a] by (%x, ...b)` can be rewritten
5731/// to `affine.linearize_index [...a] by (...b)` in all cases.
5732struct DropLinearizeLeadingZero final
5733 : OpRewritePattern<affine::AffineLinearizeIndexOp> {
5734 using Base::Base;
5735
5736 LogicalResult matchAndRewrite(affine::AffineLinearizeIndexOp op,
5737 PatternRewriter &rewriter) const override {
5738 Value leadingIdx = op.getMultiIndex().front();
5739 if (!matchPattern(value: leadingIdx, pattern: m_Zero()))
5740 return failure();
5741
5742 if (op.getMultiIndex().size() == 1) {
5743 rewriter.replaceOp(op, newValues: leadingIdx);
5744 return success();
5745 }
5746
5747 SmallVector<OpFoldResult> mixedBasis = op.getMixedBasis();
5748 ArrayRef<OpFoldResult> newMixedBasis = mixedBasis;
5749 if (op.hasOuterBound())
5750 newMixedBasis = newMixedBasis.drop_front();
5751
5752 rewriter.replaceOpWithNewOp<affine::AffineLinearizeIndexOp>(
5753 op, args: op.getMultiIndex().drop_front(), args&: newMixedBasis, args: op.getDisjoint());
5754 return success();
5755 }
5756};
5757} // namespace
5758
5759void affine::AffineLinearizeIndexOp::getCanonicalizationPatterns(
5760 RewritePatternSet &patterns, MLIRContext *context) {
5761 patterns.add<CancelLinearizeOfDelinearizePortion, DropLinearizeLeadingZero,
5762 DropLinearizeUnitComponentsIfDisjointOrZero>(arg&: context);
5763}
5764
5765//===----------------------------------------------------------------------===//
5766// TableGen'd op method definitions
5767//===----------------------------------------------------------------------===//
5768
5769#define GET_OP_CLASSES
5770#include "mlir/Dialect/Affine/IR/AffineOps.cpp.inc"
5771