1//===- TilingInterfaceImpl.cpp - Implementation of TilingInterface -------===//
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/Linalg/Transforms/TilingInterfaceImpl.h"
10
11#include "mlir/Analysis/SliceAnalysis.h"
12#include "mlir/Dialect/Affine/IR/AffineOps.h"
13#include "mlir/Dialect/Affine/Utils.h"
14#include "mlir/Dialect/Arith/IR/Arith.h"
15#include "mlir/Dialect/Arith/Utils/Utils.h"
16#include "mlir/Dialect/Linalg/IR/Linalg.h"
17#include "mlir/Dialect/Linalg/Utils/Utils.h"
18#include "mlir/Dialect/MemRef/IR/MemRef.h"
19#include "mlir/Dialect/SCF/IR/SCF.h"
20#include "mlir/Dialect/Tensor/IR/Tensor.h"
21#include "mlir/Dialect/Utils/IndexingUtils.h"
22#include "mlir/Dialect/Utils/StaticValueUtils.h"
23#include "mlir/Dialect/Utils/StructuredOpsUtils.h"
24#include "mlir/IR/BuiltinTypeInterfaces.h"
25#include "mlir/Interfaces/TilingInterface.h"
26#include "mlir/Interfaces/ValueBoundsOpInterface.h"
27#include "llvm/ADT/SmallVectorExtras.h"
28#include "llvm/Support/Debug.h"
29#include <optional>
30
31#define DEBUG_TYPE "linalg-tiling-interface-impl"
32
33using namespace mlir;
34using namespace mlir::linalg;
35
36//===----------------------------------------------------------------------===//
37// Utility methods for implementation of Tiling Interface for Linalg ops
38//===----------------------------------------------------------------------===//
39
40/// Return the SSA values that represent the data point accessed using a given
41/// `indexingMap` for a given point in the iteration space represented by `ivs`.
42static SmallVector<Value> getIndicesForAccess(OpBuilder &b, Location loc,
43 AffineMap indexingMap,
44 ValueRange ivs) {
45 SmallVector<Value> indices;
46 indices.reserve(N: indexingMap.getNumResults());
47 for (auto result : indexingMap.getResults()) {
48 AffineMap m = AffineMap::get(dimCount: indexingMap.getNumDims(),
49 symbolCount: indexingMap.getNumSymbols(), result);
50 Value v = affine::AffineApplyOp::create(builder&: b, location: loc, map: m, mapOperands: ivs);
51 indices.push_back(Elt: v);
52 }
53 return indices;
54}
55
56/// Method to inline the payload of a `linalgOp` given the iteration space
57/// point and values for the arguments of the payload.
58static LogicalResult inlinePayload(OpBuilder &b, LinalgOp linalgOp,
59 ValueRange ivs, ValueRange argValues) {
60 Block *body = linalgOp.getBlock();
61 IRMapping map;
62 map.map(from: body->getArguments(), to&: argValues);
63 for (auto &op : body->without_terminator()) {
64 if (auto indexOp = dyn_cast<IndexOp>(Val: &op)) {
65 map.map(from: indexOp.getResult(), to: ivs[indexOp.getDim()]);
66 continue;
67 }
68 b.clone(op, mapper&: map);
69 }
70
71 Operation *terminator = body->getTerminator();
72 Location loc = terminator->getLoc();
73 for (const auto &operand : llvm::enumerate(First: terminator->getOperands())) {
74 Value toStore = map.lookupOrDefault(from: operand.value());
75 OpOperand *storeInto = linalgOp.getDpsInitOperand(i: operand.index());
76 auto indices = getIndicesForAccess(
77 b, loc, indexingMap: linalgOp.getMatchingIndexingMap(opOperand: storeInto), ivs);
78 memref::StoreOp::create(builder&: b, location: loc, valueToStore: toStore,
79 memref: linalgOp.getDpsInitOperand(i: operand.index())->get(),
80 indices);
81 }
82 return success();
83}
84
85/// Verify that tiling can be applied in presence of semi-affine maps.
86static LogicalResult
87validateTilingSemiAffineMaps(LinalgOp linalgOp, ArrayRef<OpFoldResult> sizes) {
88 // Precompute each dimension's constant tile-size upper bound once.
89 // A failed entry marks a dynamic tile with no static bound.
90 SmallVector<FailureOr<int64_t>> tileSizeBounds =
91 llvm::map_to_vector(C&: sizes, F: [](OpFoldResult size) {
92 return ValueBoundsConstraintSet::computeConstantBound(
93 type: presburger::BoundType::UB, var: size,
94 /*stopCondition=*/nullptr, options: ValueBoundsOptions{/*closedUB=*/true});
95 });
96 SmallVector<int64_t> loopRanges = linalgOp.getStaticLoopRanges();
97
98 // Dynamic tiles or dynamic loop ranges are conservatively treated as tiled.
99 SmallVector<bool> tiledDims(loopRanges.size(), false);
100 for (auto [pos, tileSize] : llvm::enumerate(First&: tileSizeBounds)) {
101 if (failed(Result: tileSize)) {
102 tiledDims[pos] = true;
103 continue;
104 }
105 if (*tileSize == 0)
106 continue;
107 tiledDims[pos] =
108 ShapedType::isDynamic(dValue: loopRanges[pos]) || *tileSize < loopRanges[pos];
109 }
110
111 for (AffineMap map : linalgOp.getIndexingMapsArray()) {
112 for (AffineExpr result : map.getResults()) {
113 WalkResult status = result.walk(callback: [&](AffineExpr expr) -> WalkResult {
114 auto binExpr = dyn_cast<AffineBinaryOpExpr>(Val&: expr);
115 if (!binExpr)
116 return WalkResult::advance();
117 AffineExprKind kind = binExpr.getKind();
118 if (kind != AffineExprKind::Mod && kind != AffineExprKind::FloorDiv &&
119 kind != AffineExprKind::CeilDiv)
120 return WalkResult::advance();
121
122 // Skip if the semi-affine expression does not involve any tiled
123 // dimension: an untiled dimension keeps its full extent in every tile,
124 // so re-applying the map on the slice is exact.
125 bool involvesTiledDim = expr.walk(callback: [&](AffineExpr e) -> WalkResult {
126 auto dim = dyn_cast<AffineDimExpr>(Val&: e);
127 if (dim && tiledDims[dim.getPosition()])
128 return WalkResult::interrupt();
129 return WalkResult::advance();
130 })
131 .wasInterrupted();
132 if (!involvesTiledDim)
133 return WalkResult::advance();
134
135 // Allow only `d OP C` map where `d` is a dimension and `C` is a
136 // constant. A compound LHS (e.g. `(d0 + d1)`, `(d0 * 2)`, a nested
137 // semi-affine expression) or a non-constant step is not provably safe,
138 // so reject it.
139 auto dimExpr = dyn_cast<AffineDimExpr>(Val: binExpr.getLHS());
140 auto stepExpr = dyn_cast<AffineConstantExpr>(Val: binExpr.getRHS());
141 if (!dimExpr || !stepExpr || stepExpr.getValue() <= 0) {
142 linalgOp.emitOpError()
143 << "tiling is not supported for the semi-affine indexing map: "
144 "only a single iteration dimension divided by a positive "
145 "constant step can be tiled over a tiled dimension";
146 return WalkResult::interrupt();
147 }
148
149 // Tiles are spaced by the full tile size, so tile origins are its
150 // multiples (0, tileSize, 2*tileSize, ...).
151 // A tile's indices are `origin + d'`, with `origin` the tile's start
152 // and `0 <= d' < tileSize`. A trailing partial tile is a full tile
153 // truncated at the same origin, spanning a subset of the same `d'`, so
154 // full-tile validity implies partial-tile validity and validating the
155 // upper-bound tile size suffices.
156 unsigned dimPos = dimExpr.getPosition();
157 FailureOr<int64_t> tileSize = tileSizeBounds[dimPos];
158
159 // Dynamic tile sizes are assumed to be valid.
160 // Unit tile is always valid.
161 if (failed(Result: tileSize) || *tileSize == 1)
162 return WalkResult::advance();
163
164 // Tiled op reuses the same map on a slice whose base offset is
165 // `m(origin) - m(0)`, so it is correct only when
166 // `m(origin + d') == (m(origin) - m(0)) + m(d')` for every `d'`.
167 // Slice origins are tile-size multiples, so this reduces to a relation
168 // between the tile size and the step `C`:
169 // - `floordiv`/`mod` are locally affine within a step window (floordiv
170 // is constant, mod is linear), so they compose when the origin is
171 // step-aligned (`C | tileSize`) or the whole tile fits in one window
172 // (`tileSize | C`);
173 // - `ceildiv` jumps at `k * C + 1` instead of `k * C`, so a
174 // non-step-aligned origin already straddles the jump. It composes
175 // only from a step-aligned origin, i.e. `C | tileSize`.
176 int64_t step = stepExpr.getValue();
177 bool isCeil = kind == AffineExprKind::CeilDiv;
178 bool safe = *tileSize % step == 0 || (!isCeil && step % *tileSize == 0);
179 if (!safe) {
180 linalgOp.emitOpError()
181 << "tiling is not supported for the semi-affine indexing map: "
182 "tile size "
183 << *tileSize << " for dimension d" << dimPos
184 << (isCeil ? " must be a multiple of the step "
185 : " must divide or be divisible by the step ")
186 << step;
187 return WalkResult::interrupt();
188 }
189 return WalkResult::advance();
190 });
191 if (status.wasInterrupted())
192 return failure();
193 }
194 }
195 return success();
196}
197
198//===----------------------------------------------------------------------===//
199// External Model for implementing `TilingInterface` for `LinalgOp`s.
200//===----------------------------------------------------------------------===//
201
202namespace {
203/// Operation-independent implementation shared by the external models for
204/// LinalgOps. External models are used for now until `TilingInterface` is
205/// on-par with the current Linalg tiling and fusion patterns. It may then be
206/// possible to move this into the op definitions, though there are advantages
207/// to leaving it as an external model.
208struct LinalgOpTilingInterfaceImpl {
209 /// Return the iteration domain range.
210 SmallVector<Range> getIterationDomain(Operation *op, OpBuilder &b) const {
211 OpBuilder::InsertionGuard g(b);
212 b.setInsertionPoint(op);
213 Location loc = op->getLoc();
214 LinalgOp linalgOp = cast<LinalgOp>(Val: op);
215 SmallVector<OpFoldResult> allShapesSizes =
216 linalgOp.createFlatListOfOperandDims(b, loc);
217 AffineMap map = linalgOp.getShapesToLoopsMap();
218
219 return llvm::map_to_vector(C: map.getResults(), F: [&](AffineExpr loopExpr) {
220 OpFoldResult ofr = affine::makeComposedFoldedAffineApply(b, loc, expr: loopExpr,
221 operands: allShapesSizes);
222 return Range{.offset: b.getIndexAttr(value: 0), .size: ofr, .stride: b.getIndexAttr(value: 1)};
223 });
224 }
225
226 /// Instantiate the tiled implementation of the operation.
227 FailureOr<TilingResult>
228 getTiledImplementation(Operation *op, OpBuilder &b,
229 ArrayRef<OpFoldResult> offsets,
230 ArrayRef<OpFoldResult> sizes) const {
231 // Leave the `sizeBounds` value empty. That is only needed when the `sizes`
232 // specified could lead to out of bounds accesses.
233 Location loc = op->getLoc();
234 LinalgOp linalgOp = cast<LinalgOp>(Val: op);
235 // In case of a semi-affine expression, generalized tracking of tiles would
236 // require a per-tile-position shift that cannot be expressed by the
237 // symbol-free indexing maps.
238 // Thus, tiling is allowed only when the semi-affine maps can be proven safe
239 // for the current tiling configuration. Otherwise, tiling can end up
240 // producing incorrect results.
241 if (failed(Result: validateTilingSemiAffineMaps(linalgOp, sizes)))
242 return failure();
243 SmallVector<Value> valuesToTile = linalgOp->getOperands();
244 SmallVector<Value> tiledOperands = makeTiledShapes(
245 builder&: b, loc, linalgOp, valuesToTile, ivs: offsets, tileSizes: sizes, sizeBounds: {}, omitPartialTileCheck: true);
246 SmallVector<Operation *> generatedSlices = llvm::map_to_vector(
247 C: llvm::make_filter_range(
248 Range&: tiledOperands,
249 Pred: [](Value v) -> bool {
250 return isa_and_nonnull<tensor::ExtractSliceOp, memref::SubViewOp>(
251 Val: v.getDefiningOp());
252 }),
253 F: [](Value v) -> Operation * { return v.getDefiningOp(); });
254
255 SmallVector<Type> resultTensorTypes =
256 getTensorOutputTypes(op: linalgOp, operands: tiledOperands);
257
258 Operation *tiledOp = clone(b, op: linalgOp, newResultTypes: resultTensorTypes, newOperands: tiledOperands);
259 offsetIndices(b, linalgOp: cast<LinalgOp>(Val: tiledOp), offests: offsets);
260
261 return TilingResult{
262 .tiledOps: {tiledOp}, .tiledValues: SmallVector<Value>(tiledOp->getResults()), .generatedSlices: generatedSlices};
263 }
264
265 /// Utility to fetch the offsets and sizes when applied as per the indexing
266 /// map of the linalg op. This helps in fusing the linalg op as a consumer of
267 /// a given slice op.
268 static LogicalResult
269 getMappedOffsetAndSize(LinalgOp linalgOp, OpBuilder &b,
270 ArrayRef<AffineMap> indexingMaps,
271 ArrayRef<SmallVector<OpFoldResult>> allOffsets,
272 ArrayRef<SmallVector<OpFoldResult>> allSizes,
273 SmallVectorImpl<OpFoldResult> &mappedOffsetsVec,
274 SmallVectorImpl<OpFoldResult> &mappedSizesVec) {
275 DenseMap<unsigned, OpFoldResult> mappedOffsets, mappedSizes;
276
277 for (auto [indexingMap, offsets, sizes] :
278 llvm::zip_equal(t&: indexingMaps, u&: allOffsets, args&: allSizes)) {
279 for (auto [resultExpr, offset, size] :
280 llvm::zip_equal(t: indexingMap.getResults(), u: offsets, args: sizes)) {
281 auto dimExpr = dyn_cast<AffineDimExpr>(Val: resultExpr);
282 if (!dimExpr)
283 return failure();
284 unsigned position = dimExpr.getPosition();
285 auto it = mappedOffsets.find(Val: position);
286 if (it != mappedOffsets.end()) {
287 OpFoldResult seenOffset = it->second;
288 OpFoldResult seenSize = mappedSizes.lookup(Val: position);
289 if (seenOffset != offset || seenSize != size) {
290 LLVM_DEBUG({
291 llvm::dbgs() << "inconsistent iteration space mapping from "
292 "offsets/sizes of operands/results";
293 });
294 return failure();
295 }
296 } else {
297 mappedOffsets[position] = offset;
298 mappedSizes[position] = size;
299 }
300 }
301 }
302
303 // Aggregate from the given operand offsets and sizes, or default to
304 // iteration space values.
305 SmallVector<Range> iterationDomain =
306 cast<TilingInterface>(Val: linalgOp.getOperation()).getIterationDomain(b);
307 mappedOffsetsVec.resize(N: iterationDomain.size());
308 mappedSizesVec.resize(N: iterationDomain.size());
309 for (auto [index, domain] : llvm::enumerate(First&: iterationDomain)) {
310 auto it = mappedOffsets.find(Val: index);
311 if (it != mappedOffsets.end()) {
312 mappedOffsetsVec[index] = it->second;
313 mappedSizesVec[index] = mappedSizes.lookup(Val: index);
314 continue;
315 }
316 mappedOffsetsVec[index] = domain.offset;
317 mappedSizesVec[index] = domain.size;
318 }
319 return success();
320 }
321
322 /// Method to return the position of the result tile computed by the tiled
323 /// operation.
324 LogicalResult getIterationDomainTileFromOperandTiles(
325 Operation *op, OpBuilder &b, ArrayRef<unsigned> operandNumbers,
326 ArrayRef<SmallVector<OpFoldResult>> allOffsets,
327 ArrayRef<SmallVector<OpFoldResult>> allSizes,
328 SmallVectorImpl<OpFoldResult> &iterDomainOffsets,
329 SmallVectorImpl<OpFoldResult> &iterDomainSizes) const {
330 auto linalgOp = cast<LinalgOp>(Val: op);
331
332 SmallVector<AffineMap> indexingMaps =
333 llvm::map_to_vector(C&: operandNumbers, F: [&](unsigned operandNumber) {
334 OpOperand &opOperand = linalgOp->getOpOperand(idx: operandNumber);
335 return linalgOp.getMatchingIndexingMap(opOperand: &opOperand);
336 });
337 if (failed(Result: getMappedOffsetAndSize(linalgOp, b, indexingMaps, allOffsets,
338 allSizes, mappedOffsetsVec&: iterDomainOffsets,
339 mappedSizesVec&: iterDomainSizes))) {
340 return failure();
341 }
342 return success();
343 }
344
345 /// Return the details of the output tile generated by the tiled
346 /// implementation.
347 LogicalResult
348 getResultTilePosition(Operation *op, OpBuilder &b, unsigned resultNumber,
349 ArrayRef<OpFoldResult> offsets,
350 ArrayRef<OpFoldResult> sizes,
351 SmallVector<OpFoldResult> &resultOffsets,
352 SmallVector<OpFoldResult> &resultSizes) const {
353 Location loc = op->getLoc();
354 LinalgOp linalgOp = cast<LinalgOp>(Val: op);
355
356 AffineExpr d0;
357 bindDims(ctx: b.getContext(), exprs&: d0);
358 SmallVector<OpFoldResult> subShapeSizes =
359 llvm::map_to_vector(C&: sizes, F: [&](OpFoldResult ofr) {
360 return affine::makeComposedFoldedAffineApply(b, loc, expr: d0 - 1, operands: ofr);
361 });
362
363 OpOperand *outOperand = linalgOp.getDpsInitOperand(i: resultNumber);
364 SliceParameters sliceParams = computeSliceParameters(
365 builder&: b, loc, valueToTile: outOperand->get(), tileSizes: sizes,
366 map: linalgOp.getMatchingIndexingMap(opOperand: outOperand), lbs: offsets,
367 /*ubs*/ {}, subShapeSizes, omitPartialTileCheck: true);
368 resultOffsets = sliceParams.offsets;
369 resultSizes = sliceParams.sizes;
370 return success();
371 }
372
373 LogicalResult getIterationDomainTileFromResultTile(
374 Operation *op, OpBuilder &b, unsigned resultNumber,
375 ArrayRef<OpFoldResult> offsets, ArrayRef<OpFoldResult> sizes,
376 SmallVectorImpl<OpFoldResult> &iterDomainOffsets,
377 SmallVectorImpl<OpFoldResult> &iterDomainSizes) const {
378 auto linalgOp = cast<LinalgOp>(Val: op);
379
380 // Check that the indexing map used for the output is a projected
381 // permutation. This could be relaxed with a more general approach that can
382 // map the offsets and sizes from the result to iteration space tiles
383 // (filling in full extent for dimensions not used to access the result).
384 AffineMap indexingMap =
385 linalgOp.getIndexingMapMatchingResult(result: op->getResult(idx: resultNumber));
386 if (!indexingMap.isProjectedPermutation()) {
387 return op->emitOpError(
388 message: "unhandled tiled implementation generation when result is not "
389 "accessed using a permuted projection");
390 }
391
392 SmallVector<OpFoldResult> allOffsets = llvm::to_vector(Range&: offsets);
393 SmallVector<OpFoldResult> allSizes = llvm::to_vector(Range&: sizes);
394 auto status =
395 getMappedOffsetAndSize(linalgOp, b, indexingMaps: indexingMap, allOffsets: {allOffsets},
396 allSizes: {allSizes}, mappedOffsetsVec&: iterDomainOffsets, mappedSizesVec&: iterDomainSizes);
397 (void)status;
398 assert(succeeded(status) && "unexpected error in offset calculation");
399 return success();
400 }
401
402 FailureOr<TilingResult>
403 generateResultTileValue(Operation *op, OpBuilder &b, unsigned resultNumber,
404 ArrayRef<OpFoldResult> offsets,
405 ArrayRef<OpFoldResult> sizes) const {
406 SmallVector<OpFoldResult> mappedOffsets, mappedSizes;
407 if (failed(Result: getIterationDomainTileFromResultTile(
408 op, b, resultNumber, offsets, sizes, iterDomainOffsets&: mappedOffsets, iterDomainSizes&: mappedSizes))) {
409 return failure();
410 }
411 auto tilingInterfaceOp = cast<TilingInterface>(Val: op);
412 FailureOr<TilingResult> tilingResult =
413 tilingInterfaceOp.getTiledImplementation(b, offsets: mappedOffsets, sizes: mappedSizes);
414
415 if (failed(Result: tilingResult))
416 return failure();
417
418 if (tilingResult->tiledOps.size() != 1)
419 return op->emitOpError(message: "failed to generate tiled implementation");
420
421 return TilingResult{
422 .tiledOps: tilingResult->tiledOps,
423 .tiledValues: SmallVector<Value>{tilingResult->tiledValues[resultNumber]},
424 .generatedSlices: tilingResult->generatedSlices};
425 }
426
427 /// Method to generate the tiled implementation of an operation from the tile
428 /// of the operand.
429 FailureOr<TilingResult> getTiledImplementationFromOperandTiles(
430 Operation *op, OpBuilder &b, ArrayRef<unsigned> operandNumbers,
431 ArrayRef<SmallVector<OpFoldResult>> allOffsets,
432 ArrayRef<SmallVector<OpFoldResult>> allSizes) const {
433 SmallVector<OpFoldResult> mappedOffsets, mappedSizes;
434 if (failed(Result: getIterationDomainTileFromOperandTiles(
435 op, b, operandNumbers, allOffsets, allSizes, iterDomainOffsets&: mappedOffsets,
436 iterDomainSizes&: mappedSizes))) {
437 return failure();
438 }
439 return getTiledImplementation(op, b, offsets: mappedOffsets, sizes: mappedSizes);
440 }
441
442 LogicalResult generateScalarImplementation(Operation *op, OpBuilder &builder,
443 Location loc,
444 ValueRange ivs) const {
445 auto linalgOp = cast<LinalgOp>(Val: op);
446 if (!linalgOp.hasPureBufferSemantics())
447 return op->emitOpError(message: "expected operation to have buffer semantics");
448
449 SmallVector<Value> indexedValues;
450 indexedValues.reserve(N: linalgOp->getNumOperands());
451 Location linalgOpLoc = op->getLoc();
452 /// Load the data corresponding to the block arguments that
453 /// represent input operands.
454 for (OpOperand &operand : linalgOp->getOpOperands()) {
455 if (!linalgOp.payloadUsesValueFromOperand(opOperand: &operand)) {
456 indexedValues.push_back(Elt: nullptr);
457 continue;
458 }
459 if (linalgOp.isScalar(opOperand: &operand)) {
460 indexedValues.push_back(Elt: operand.get());
461 continue;
462 }
463 SmallVector<Value> indices = getIndicesForAccess(
464 b&: builder, loc: linalgOpLoc, indexingMap: linalgOp.getMatchingIndexingMap(opOperand: &operand), ivs);
465 Value load =
466 memref::LoadOp::create(builder, location: linalgOpLoc, memref: operand.get(), indices);
467 indexedValues.push_back(Elt: load);
468 }
469
470 /// Inline the op payload and store the result.
471 return inlinePayload(b&: builder, linalgOp, ivs, argValues: indexedValues);
472 }
473
474 bool isOpFusableWithConsumerSlice(Operation *op, unsigned resultNumber,
475 ArrayRef<OpFoldResult> offsets,
476 ArrayRef<OpFoldResult> sizes) const {
477 // The verifier gives all the necessary requirements for consumer fusion.
478 return true;
479 }
480
481 bool isOpFusableWithProducerSlices(
482 Operation *op, ArrayRef<unsigned> operandNumbers,
483 ArrayRef<SmallVector<OpFoldResult>> allOffsets,
484 ArrayRef<SmallVector<OpFoldResult>> allSizes) const {
485
486 auto linalgOp = cast<LinalgOp>(Val: op);
487 SmallVector<AffineMap> indexingMaps =
488 llvm::map_to_vector(C&: operandNumbers, F: [&](unsigned operandNumber) {
489 OpOperand &opOperand = linalgOp->getOpOperand(idx: operandNumber);
490 return linalgOp.getMatchingIndexingMap(opOperand: &opOperand);
491 });
492 // Check that offsets/sizes are consistent across all operands.
493 OpBuilder b(op);
494 SmallVector<OpFoldResult> mappedOffsets, mappedSizes;
495 return succeeded(Result: getMappedOffsetAndSize(linalgOp, b, indexingMaps,
496 allOffsets, allSizes, mappedOffsetsVec&: mappedOffsets,
497 mappedSizesVec&: mappedSizes));
498 }
499};
500
501template <typename LinalgOpTy>
502struct LinalgOpTilingInterfaceModel
503 : public TilingInterface::ExternalModel<
504 LinalgOpTilingInterfaceModel<LinalgOpTy>, LinalgOpTy>,
505 public LinalgOpTilingInterfaceImpl {
506 using ExternalModel =
507 TilingInterface::ExternalModel<LinalgOpTilingInterfaceModel<LinalgOpTy>,
508 LinalgOpTy>;
509
510 using LinalgOpTilingInterfaceImpl::generateScalarImplementation;
511 using LinalgOpTilingInterfaceImpl::getIterationDomain;
512 using LinalgOpTilingInterfaceImpl::getIterationDomainTileFromResultTile;
513 using LinalgOpTilingInterfaceImpl::getResultTilePosition;
514 using LinalgOpTilingInterfaceImpl::isOpFusableWithConsumerSlice;
515 using LinalgOpTilingInterfaceImpl::isOpFusableWithProducerSlices;
516
517 /// Return the loop iterator type without a dynamic LinalgOp interface lookup.
518 SmallVector<utils::IteratorType> getLoopIteratorTypes(Operation *op) const {
519 return cast<LinalgOpTy>(op).getIteratorTypesArray();
520 }
521
522 // Preserve the hint-bearing ExternalModel defaults while routing the
523 // no-hint overloads through the shared implementation.
524 using ExternalModel::generateResultTileValue;
525 FailureOr<TilingResult>
526 generateResultTileValue(Operation *op, OpBuilder &b, unsigned resultNumber,
527 ArrayRef<OpFoldResult> offsets,
528 ArrayRef<OpFoldResult> sizes) const {
529 return LinalgOpTilingInterfaceImpl::generateResultTileValue(
530 op, b, resultNumber, offsets, sizes);
531 }
532
533 using ExternalModel::getIterationDomainTileFromOperandTiles;
534 LogicalResult getIterationDomainTileFromOperandTiles(
535 Operation *op, OpBuilder &b, ArrayRef<unsigned> operandNumbers,
536 ArrayRef<SmallVector<OpFoldResult>> allOffsets,
537 ArrayRef<SmallVector<OpFoldResult>> allSizes,
538 SmallVectorImpl<OpFoldResult> &iterDomainOffsets,
539 SmallVectorImpl<OpFoldResult> &iterDomainSizes) const {
540 return LinalgOpTilingInterfaceImpl::getIterationDomainTileFromOperandTiles(
541 op, b, operandNumbers, allOffsets, allSizes, iterDomainOffsets,
542 iterDomainSizes);
543 }
544
545 using ExternalModel::getTiledImplementation;
546 FailureOr<TilingResult>
547 getTiledImplementation(Operation *op, OpBuilder &b,
548 ArrayRef<OpFoldResult> offsets,
549 ArrayRef<OpFoldResult> sizes) const {
550 return LinalgOpTilingInterfaceImpl::getTiledImplementation(op, b, offsets,
551 sizes);
552 }
553
554 using ExternalModel::getTiledImplementationFromOperandTiles;
555 FailureOr<TilingResult> getTiledImplementationFromOperandTiles(
556 Operation *op, OpBuilder &b, ArrayRef<unsigned> operandNumbers,
557 ArrayRef<SmallVector<OpFoldResult>> allOffsets,
558 ArrayRef<SmallVector<OpFoldResult>> allSizes) const {
559 return LinalgOpTilingInterfaceImpl::getTiledImplementationFromOperandTiles(
560 op, b, operandNumbers, allOffsets, allSizes);
561 }
562};
563
564//===----------------------------------------------------------------------===//
565// External Model for implementing `PartialReductionInterface` for `LinalgOp`s.
566//===----------------------------------------------------------------------===//
567
568/// In a given set vector, get the position of a particular element.
569std::optional<int> getPositionIn(const llvm::SetVector<unsigned> &reductionDims,
570 unsigned value) {
571 for (auto [index, reductionDim] : llvm::enumerate(First: reductionDims)) {
572 if (reductionDim == value) {
573 return index;
574 }
575 }
576 return std::nullopt;
577}
578
579/// Return an AffineMaps to use for the `outs` operands of the linalg op
580/// generated for partial results. The new AffineMap is the AffineMap of the
581/// untiled op with reduction dimensions appended at end in order in which they
582/// were specified during tiling.
583static SmallVector<AffineMap>
584getPartialResultAffineMaps(LinalgOp linalgOp,
585 const SetVector<unsigned> &reductionDims) {
586 auto partialReductionMaps = llvm::map_to_vector(
587 C: linalgOp.getDpsInitsMutable(), F: [&](OpOperand &opOperand) {
588 AffineMap map = linalgOp.getMatchingIndexingMap(opOperand: &opOperand);
589 for (auto redPos : reductionDims) {
590 map =
591 map.insertResult(expr: getAffineDimExpr(position: redPos, context: linalgOp.getContext()),
592 pos: map.getNumResults());
593 }
594 return map;
595 });
596 return partialReductionMaps;
597}
598
599struct InitSliceInfo {
600 SmallVector<int64_t> resultShape;
601 SmallVector<OpFoldResult> offsets;
602 SmallVector<OpFoldResult> sizes;
603 SmallVector<OpFoldResult> strides;
604};
605
606/// Return the result shape, offsets, sizes and strides of the slice of the
607/// `initValue` to use as the destination of the partial reduction op generated
608/// with outer reduction strategy.
609static InitSliceInfo getInitSliceInfoForOuterReduction(
610 MLIRContext *context, ArrayRef<OpFoldResult> offsets,
611 ArrayRef<OpFoldResult> sizes, const SetVector<unsigned> &reductionDims,
612 ArrayRef<OpFoldResult> splitReductionIvs, AffineMap partialReductionMap,
613 ArrayRef<OpFoldResult> initOperandShape) {
614 int64_t initRank = partialReductionMap.getNumResults();
615 SmallVector<OpFoldResult> initOffsets, initSizes;
616 Attribute zero = IntegerAttr::get(type: IndexType::get(context), value: 0);
617 Attribute one = IntegerAttr::get(type: IndexType::get(context), value: 1);
618 SmallVector<OpFoldResult> initStrides(initRank, one);
619 for (auto [resultIdx, dimExpr] :
620 llvm::enumerate(First: partialReductionMap.getResults())) {
621 if (isa<AffineConstantExpr>(Val: dimExpr)) {
622 // A constant index in the output map accesses a fixed position; keep
623 // the full output dimension to match the original output operand shape.
624 initOffsets.push_back(Elt: zero);
625 initSizes.push_back(Elt: initOperandShape[resultIdx]);
626 continue;
627 }
628 unsigned dim = cast<AffineDimExpr>(Val: dimExpr).getPosition();
629 if (reductionDims.contains(key: dim)) {
630 initOffsets.push_back(Elt: zero);
631 } else {
632 initOffsets.push_back(Elt: offsets[dim]);
633 }
634 initSizes.push_back(Elt: sizes[dim]);
635 }
636 SmallVector<int64_t> resultShape;
637 std::tie(args&: resultShape, args: std::ignore) = decomposeMixedValues(mixedValues: initSizes);
638 return {.resultShape: resultShape, .offsets: initOffsets, .sizes: initSizes, .strides: initStrides};
639}
640
641/// Return the result shape, offsets, sizes and strides of the slice of the
642/// `initValue` to use as destination of the partial reduction op generated with
643/// outer parallel strategy.
644static InitSliceInfo getInitSliceInfoForOuterParallel(
645 MLIRContext *context, ArrayRef<OpFoldResult> offsets,
646 ArrayRef<OpFoldResult> sizes, const SetVector<unsigned> &reductionDims,
647 ArrayRef<OpFoldResult> splitReductionIvs, AffineMap partialReductionMap,
648 ArrayRef<OpFoldResult> initOperandShape) {
649 int64_t initRank = partialReductionMap.getNumResults();
650 SmallVector<OpFoldResult> initOffsets, initSizes;
651 Attribute zero = IntegerAttr::get(type: IndexType::get(context), value: 0);
652 Attribute one = IntegerAttr::get(type: IndexType::get(context), value: 1);
653 SmallVector<OpFoldResult> initStrides(initRank, one);
654 SmallVector<OpFoldResult> resultShape;
655 for (auto [resultIdx, dimExpr] :
656 llvm::enumerate(First: partialReductionMap.getResults())) {
657 if (isa<AffineConstantExpr>(Val: dimExpr)) {
658 // A constant index accesses a fixed position; keep the full output
659 // dimension to match the original output operand shape.
660 initOffsets.push_back(Elt: zero);
661 initSizes.push_back(Elt: initOperandShape[resultIdx]);
662 resultShape.push_back(Elt: initOperandShape[resultIdx]);
663 continue;
664 }
665 unsigned dim = cast<AffineDimExpr>(Val: dimExpr).getPosition();
666 if (std::optional<unsigned> dimPos = getPositionIn(reductionDims, value: dim)) {
667 initOffsets.push_back(Elt: splitReductionIvs[dimPos.value()]);
668 initSizes.push_back(Elt: one);
669 } else {
670 initOffsets.push_back(Elt: offsets[dim]);
671 initSizes.push_back(Elt: sizes[dim]);
672 resultShape.push_back(Elt: sizes[dim]);
673 }
674 }
675 SmallVector<int64_t> staticShapes;
676 std::tie(args&: staticShapes, args: std::ignore) = decomposeMixedValues(mixedValues: resultShape);
677 return {.resultShape: staticShapes, .offsets: initOffsets, .sizes: initSizes, .strides: initStrides};
678}
679
680/// Return the result shape, offsets, sizes and strides of the slice of the
681/// `initValue` to use as destination of the partial reduction op.
682static InitSliceInfo getInitSliceInfo(MLIRContext *context,
683 ReductionTilingStrategy strategy,
684 ArrayRef<OpFoldResult> offsets,
685 ArrayRef<OpFoldResult> sizes,
686 const SetVector<unsigned> &reductionDims,
687 ArrayRef<OpFoldResult> splitReductionIvs,
688 AffineMap partialReductionMap,
689 ArrayRef<OpFoldResult> initOperandShape) {
690 if (strategy == ReductionTilingStrategy::PartialReductionOuterReduction) {
691 return getInitSliceInfoForOuterReduction(
692 context, offsets, sizes, reductionDims, splitReductionIvs,
693 partialReductionMap, initOperandShape);
694 }
695 assert(strategy == ReductionTilingStrategy::PartialReductionOuterParallel &&
696 "unexpected ReductionTilingStrategy");
697 return getInitSliceInfoForOuterParallel(
698 context, offsets, sizes, reductionDims, splitReductionIvs,
699 partialReductionMap, initOperandShape);
700}
701
702/// Operation-independent implementation shared by the
703/// PartialReductionInterface external models for LinalgOps.
704struct LinalgOpPartialReductionInterfaceImpl {
705 FailureOr<SmallVector<Value>> generateInitialTensorForPartialReduction(
706 Operation *op, OpBuilder &b, Location loc, ArrayRef<OpFoldResult> sizes,
707 const SetVector<unsigned> &reductionDims) const {
708 auto linalgOp = cast<LinalgOp>(Val: op);
709
710 OpBuilder::InsertionGuard guard(b);
711 if (linalgOp.hasPureBufferSemantics())
712 return op->emitOpError(message: "expected operation to have tensor semantics");
713
714 SmallVector<AffineMap> partialResultMaps =
715 getPartialResultAffineMaps(linalgOp, reductionDims);
716
717 SmallVector<Value> inits;
718 for (auto [initIdx, result, partialMap] :
719 llvm::enumerate(First: linalgOp->getResults(), Rest&: partialResultMaps)) {
720 SmallVector<Operation *, 4> combinerOps;
721 if (!matchReduction(iterCarriedArgs: linalgOp.getRegionOutputArgs(), redPos: initIdx,
722 combinerOps) ||
723 combinerOps.size() != 1)
724 return op->emitOpError(message: "Failed to anaysis the reduction operation.");
725
726 Operation *reductionOp = combinerOps[0];
727 std::optional<TypedAttr> identity = arith::getNeutralElement(op: reductionOp);
728 if (!identity.has_value())
729 return op->emitOpError(
730 message: "Failed to get an identity value for the reduction operation.");
731
732 // Append the new partial result dimensions.
733 SmallVector<OpFoldResult> partialResultShape;
734 Value initValue = linalgOp.getDpsInits()[initIdx];
735 SmallVector<OpFoldResult> initShape =
736 tensor::getMixedSizes(builder&: b, loc, value: initValue);
737 for (auto [resultIdx, dimExpr] :
738 llvm::enumerate(First: partialMap.getResults())) {
739 if (isa<AffineConstantExpr>(Val: dimExpr)) {
740 // A constant index in the output map accesses a fixed position; use
741 // the actual output dimension size (not a hardcoded 1).
742 partialResultShape.push_back(Elt: initShape[resultIdx]);
743 continue;
744 }
745 auto dim = cast<AffineDimExpr>(Val: dimExpr);
746 partialResultShape.push_back(Elt: sizes[dim.getPosition()]);
747 }
748
749 Type elType = getElementTypeOrSelf(type: result.getType());
750 Value emptyTensor =
751 tensor::EmptyOp::create(builder&: b, location: loc, sizes: partialResultShape, elementType: elType);
752 Value constantOp = arith::ConstantOp::create(builder&: b, location: loc, value: *identity);
753 auto identityTensor =
754 linalg::FillOp::create(builder&: b, location: loc, inputs: constantOp, outputs: emptyTensor);
755 inits.push_back(Elt: identityTensor.getResult(i: 0));
756 }
757
758 return inits;
759 }
760
761 FailureOr<TilingResult>
762 tileToPartialReduction(Operation *op, OpBuilder &b, Location loc,
763 ReductionTilingStrategy tilingStrategy,
764 ValueRange init, ArrayRef<OpFoldResult> offsets,
765 ArrayRef<OpFoldResult> sizes,
766 const SetVector<unsigned> &reductionDims,
767 ArrayRef<OpFoldResult> splitReductionIvs) const {
768 OpBuilder::InsertionGuard guard(b);
769 auto linalgOp = cast<LinalgOp>(Val: op);
770
771 SmallVector<AffineMap> partialReductionMaps =
772 getPartialResultAffineMaps(linalgOp, reductionDims);
773
774 // Step 1. Extend init maps to have reduction dimension dims, since we
775 // are converting them to parallel dimensions.
776 SmallVector<AffineMap> newInitMaps;
777 if (tilingStrategy ==
778 ReductionTilingStrategy::PartialReductionOuterReduction) {
779 newInitMaps = llvm::to_vector(Range&: partialReductionMaps);
780 } else {
781 newInitMaps = llvm::map_to_vector(
782 C: linalgOp.getDpsInitsMutable(), F: [&](OpOperand &opOperand) {
783 return linalgOp.getMatchingIndexingMap(opOperand: &opOperand);
784 });
785 }
786
787 // Step 2a: Extract a slice of the input operands.
788 SmallVector<Value> tiledInputs = makeTiledShapes(
789 builder&: b, loc, linalgOp, valuesToTile: linalgOp.getDpsInputs(), ivs: offsets, tileSizes: sizes, sizeBounds: {}, omitPartialTileCheck: true);
790 SmallVector<Operation *> generatedSlices = llvm::map_to_vector(
791 C: llvm::make_filter_range(
792 Range&: tiledInputs, Pred: [](Value v) -> bool { return v.getDefiningOp(); }),
793 F: [](Value v) -> Operation * { return v.getDefiningOp(); });
794
795 // Step 2b: Extract a slice of the init operands.
796 SmallVector<Value, 1> tiledInits;
797 for (auto [partialReductionMap, valueToTile, initOperandValue] :
798 llvm::zip_equal(t&: partialReductionMaps, u&: init, args: linalgOp.getDpsInits())) {
799 // Compute the actual shape of the original init operand for handling
800 // constant expressions in the partial reduction map.
801 SmallVector<OpFoldResult> initOperandShape =
802 tensor::getMixedSizes(builder&: b, loc, value: initOperandValue);
803 InitSliceInfo sliceInfo = getInitSliceInfo(
804 context: b.getContext(), strategy: tilingStrategy, offsets, sizes, reductionDims,
805 splitReductionIvs, partialReductionMap, initOperandShape);
806 auto valueToTileType = cast<RankedTensorType>(Val: valueToTile.getType());
807 RankedTensorType sliceResultType = RankedTensorType::get(
808 shape: sliceInfo.resultShape, elementType: valueToTileType.getElementType(),
809 encoding: valueToTileType.getEncoding());
810 auto sliceOp = tensor::ExtractSliceOp::create(
811 builder&: b, location: loc, resultType: sliceResultType, source: valueToTile, offsets: sliceInfo.offsets,
812 sizes: sliceInfo.sizes, strides: sliceInfo.strides);
813 tiledInits.push_back(Elt: sliceOp.getResult());
814 generatedSlices.push_back(Elt: sliceOp);
815 }
816
817 // Update the indexing maps.
818 SmallVector<AffineMap> newMaps = linalgOp.getIndexingMapsArray();
819 for (auto [initOperand, newInitMap] :
820 llvm::zip_equal(t: linalgOp.getDpsInitsMutable(), u&: newInitMaps)) {
821 int mapIdx = linalgOp.getIndexingMapIndex(opOperand: &initOperand);
822 newMaps[mapIdx] = newInitMap;
823 }
824
825 // Step 3. Change the reduction dim iterator types.
826 SmallVector<utils::IteratorType> newIteratorTypes =
827 linalgOp.getIteratorTypesArray();
828 if (tilingStrategy ==
829 ReductionTilingStrategy::PartialReductionOuterReduction) {
830 for (int dim : reductionDims)
831 newIteratorTypes[dim] = utils::IteratorType::parallel;
832 }
833
834 // Step 4. Create the new generic op.
835 Operation *partialReductionOp;
836 auto resultTypes = ValueRange(tiledInits).getTypes();
837 if (tilingStrategy ==
838 ReductionTilingStrategy::PartialReductionOuterReduction) {
839 auto genericOp = GenericOp::create(builder&: b, location: loc, resultTensorTypes: resultTypes, inputs: tiledInputs,
840 outputs: tiledInits, indexingMaps: newMaps, iteratorTypes: newIteratorTypes);
841 IRMapping mapping;
842 op->getRegion(index: 0).cloneInto(dest: &genericOp.getRegion(),
843 destPos: genericOp.getRegion().begin(), mapper&: mapping);
844 offsetIndices(b, linalgOp: genericOp, offests: offsets);
845 partialReductionOp = genericOp.getOperation();
846 } else {
847 SmallVector<Value> operands = std::move(tiledInputs);
848 llvm::append_range(C&: operands, R&: tiledInits);
849 partialReductionOp = mlir::clone(b, op, newResultTypes: resultTypes, newOperands: operands);
850 offsetIndices(b, linalgOp: cast<LinalgOp>(Val: partialReductionOp), offests: offsets);
851 }
852 return TilingResult{
853 .tiledOps: {partialReductionOp},
854 .tiledValues: llvm::map_to_vector(C: partialReductionOp->getResults(),
855 F: [](OpResult r) -> Value { return r; }),
856 .generatedSlices: generatedSlices};
857 }
858
859 FailureOr<MergeResult>
860 mergeReductions(Operation *op, OpBuilder &b, Location loc,
861 ValueRange partialReduce,
862 const SetVector<unsigned> &reductionDims) const {
863 auto linalgOp = cast<LinalgOp>(Val: op);
864 SmallVector<AffineMap> partialReductionMaps =
865 getPartialResultAffineMaps(linalgOp, reductionDims);
866
867 // Permute the reduction dims as permuted by the partial result map.
868 SmallVector<Operation *> mergeOperations;
869 SmallVector<Value> replacements;
870 for (auto [idx, init, partialResult, partialMap] : llvm::enumerate(
871 First: linalgOp.getDpsInits(), Rest&: partialReduce, Rest&: partialReductionMaps)) {
872 unsigned initIdx = idx;
873 // linalg.reduce's iteration space is the tiled result's iteration space
874 // (and not the tiled operation's iteration space). To account for this,
875 // permute the reduction dimensions based on the partial result map of the
876 // tiled result.
877 SmallVector<int64_t> partialReductionDims;
878 for (auto [resultNum, dimExpr] :
879 llvm::enumerate(First: partialMap.getResults())) {
880 if (isa<AffineConstantExpr>(Val: dimExpr))
881 continue; // Constant dims are never reduction dims.
882 unsigned dim = cast<AffineDimExpr>(Val: dimExpr).getPosition();
883 if (llvm::is_contained(Range: reductionDims, Element: dim)) {
884 partialReductionDims.push_back(Elt: resultNum);
885 }
886 }
887
888 auto reduction = linalg::ReduceOp::create(
889 builder&: b, location: loc, inputs: partialResult, inits: init, dimensions: partialReductionDims,
890 odsArg3: [&linalgOp, &initIdx](OpBuilder &b, Location loc, ValueRange inputs) {
891 // Get the combiner op.
892 SmallVector<Operation *, 4> combinerOps;
893 matchReduction(iterCarriedArgs: linalgOp.getRegionOutputArgs(), redPos: initIdx,
894 combinerOps);
895 Operation *clonedReductionOp = b.clone(op&: *combinerOps[0]);
896 // Combine the input at idx and output at numInits + idx.
897 clonedReductionOp->setOperand(idx: 0, value: inputs[0]);
898 clonedReductionOp->setOperand(idx: 1, value: inputs[1]);
899 linalg::YieldOp::create(builder&: b, location: loc, values: clonedReductionOp->getResult(idx: 0));
900 });
901
902 mergeOperations.push_back(Elt: reduction);
903 replacements.push_back(Elt: reduction->getResult(idx: 0));
904 }
905
906 return MergeResult{.mergeOps: mergeOperations, .replacements: replacements};
907 }
908
909 LogicalResult getPartialResultTilePosition(
910 Operation *op, OpBuilder &b, unsigned resultNumber,
911 ReductionTilingStrategy tilingStrategy, ArrayRef<OpFoldResult> offsets,
912 ArrayRef<OpFoldResult> sizes, const SetVector<unsigned> &reductionDims,
913 ArrayRef<OpFoldResult> splitReductionIvs,
914 SmallVector<OpFoldResult> &resultOffsets,
915 SmallVector<OpFoldResult> &resultSizes) const {
916 auto linalgOp = cast<LinalgOp>(Val: op);
917 SmallVector<AffineMap> partialReductionMaps =
918 getPartialResultAffineMaps(linalgOp, reductionDims);
919 // Compute the actual shape of the init operand for handling constant
920 // expressions in the partial reduction map.
921 Value initOperandValue = linalgOp.getDpsInits()[resultNumber];
922 Location loc = op->getLoc();
923 SmallVector<OpFoldResult> initOperandShape =
924 tensor::getMixedSizes(builder&: b, loc, value: initOperandValue);
925 InitSliceInfo sliceInfo =
926 getInitSliceInfo(context: b.getContext(), strategy: tilingStrategy, offsets, sizes,
927 reductionDims, splitReductionIvs,
928 partialReductionMap: partialReductionMaps[resultNumber], initOperandShape);
929 std::swap(LHS&: resultOffsets, RHS&: sliceInfo.offsets);
930 std::swap(LHS&: resultSizes, RHS&: sliceInfo.sizes);
931
932 return success();
933 }
934};
935
936template <typename LinalgOpTy>
937struct LinalgOpPartialReductionInterfaceModel
938 : public PartialReductionOpInterface::ExternalModel<
939 LinalgOpPartialReductionInterfaceModel<LinalgOpTy>, LinalgOpTy>,
940 public LinalgOpPartialReductionInterfaceImpl {
941 using LinalgOpPartialReductionInterfaceImpl::
942 generateInitialTensorForPartialReduction;
943 using LinalgOpPartialReductionInterfaceImpl::getPartialResultTilePosition;
944 using LinalgOpPartialReductionInterfaceImpl::mergeReductions;
945 using LinalgOpPartialReductionInterfaceImpl::tileToPartialReduction;
946};
947
948template <typename OpTy>
949static SmallVector<Range> getPackUnPackIterationDomain(OpTy op,
950 OpBuilder &builder) {
951 static_assert(llvm::is_one_of<OpTy, PackOp, UnPackOp>::value,
952 "applies to only pack or unpack operations");
953 OpBuilder::InsertionGuard g(builder);
954 int64_t rank = (std::is_same<OpTy, PackOp>::value) ? op.getSourceRank()
955 : op.getDestRank();
956 OpFoldResult zero = builder.getIndexAttr(value: 0);
957 OpFoldResult one = builder.getIndexAttr(value: 1);
958 ReifiedRankedShapedTypeDims resultShape;
959 (void)op.reifyResultShapes(builder, resultShape);
960 SmallVector<Range> loopBounds(rank);
961 for (auto dim : llvm::seq<int64_t>(Begin: 0, End: rank)) {
962 loopBounds[dim].offset = zero;
963 loopBounds[dim].stride = one;
964 loopBounds[dim].size = resultShape[0][dim];
965 }
966 return loopBounds;
967}
968
969static void applyPermToRange(SmallVector<OpFoldResult> &offsets,
970 SmallVector<OpFoldResult> &sizes,
971 ArrayRef<int64_t> permutation) {
972 if (permutation.empty())
973 return;
974 applyPermutationToVector<OpFoldResult>(inVec&: offsets, permutation);
975 applyPermutationToVector<OpFoldResult>(inVec&: sizes, permutation);
976}
977
978/// Compute the permutation vector to interchange `elements` such that the
979/// elements at positions in `dimsPos` are moved to the positions `[0, ...,
980/// dimsPos.size())` in order.
981static SmallVector<int64_t>
982computeInterchangeFromDimPos(ArrayRef<int64_t> dimsPos, int64_t rank) {
983 SmallVector<int64_t> interchangeVector;
984 interchangeVector.reserve(N: dimsPos.size());
985 // First map dims and their position. For example, dims_pos = [2, 0] will map
986 // to:
987 // [
988 // [ key: 2, value: 0]
989 // [ key: 0, value: 1]
990 // ]
991 // where key is the idx in dims_pos while value its position in dims_pos.
992 DenseMap<int64_t, int64_t> dimsAndPosMapping;
993 for (int64_t dimsIdx = 0, end = dimsPos.size(); dimsIdx < end; dimsIdx++)
994 dimsAndPosMapping[dimsPos[dimsIdx]] = dimsIdx;
995
996 // Scan the position in order and insert the value in the map
997 // to compute the interchange vector.
998 for (int64_t dimsIdx = 0; dimsIdx < rank; dimsIdx++) {
999 if (dimsAndPosMapping.count(Val: dimsIdx))
1000 interchangeVector.push_back(Elt: dimsAndPosMapping[dimsIdx]);
1001 }
1002 return interchangeVector;
1003}
1004
1005/// Permute the elements of `vec` starting at position `offset` according to
1006/// `interchangeVector`. The permutation maps position `i` in the permuted range
1007/// to position `interchangeVector[i]` in the original range. Elements before
1008/// `offset` are unchanged.
1009///
1010/// Example: interchange([a, b, c, d, e], [2, 0, 1], offset=2)
1011/// returns [a, b, e, c, d] (permutes the suffix [c, d, e])
1012///
1013/// Note: This is similar to `applyPermutationToVector` but supports an offset
1014/// for permuting a suffix of the vector. It is only used for pack/unpack scalar
1015/// implementation where we need to permute inner tile dimensions which are
1016/// stored at the end of the index vector.
1017template <typename T>
1018static SmallVector<T> interchange(ArrayRef<T> elements,
1019 ArrayRef<int64_t> interchangeVector,
1020 int offset = 0) {
1021 SmallVector<T> vec = llvm::to_vector(elements);
1022 for (auto [idx, val] : llvm::enumerate(First&: interchangeVector))
1023 vec[idx + offset] = elements[val + offset];
1024 return vec;
1025}
1026
1027/// Generate the body of the innermost loop of the scalar implementation
1028/// of `pack` operation.
1029static void generatePackOpScalarImplementationBody(PackOp packOp,
1030 OpBuilder &builder,
1031 Location loc,
1032 ValueRange ivs) {
1033 // Note: `ivs` are already in the correct order, possibly interchanged based
1034 // on `dims_pos`. However, connecting the loops with the access patterns is
1035 // difficult - What is the relation between the position of the tile loop and
1036 // the point loop? However, if we interchange `ivs` once more to go to the
1037 // canonical blocking format: ABCabc, this connection becomes trivial: Each
1038 // point loop is pointLoopsOffset + inputRank away from the tiled loop.
1039 ArrayRef<int64_t> dimsToInnerBlock = packOp.getInnerDimsPos();
1040 ArrayRef<int64_t> dimsToOuterBlock = packOp.getOuterDimsPerm();
1041
1042 SmallVector<Value> interchangedIvs = ivs;
1043 SmallVector<int64_t> interchangeVector =
1044 computeInterchangeFromDimPos(dimsPos: dimsToInnerBlock, rank: packOp.getSourceRank());
1045 interchangedIvs = interchange<Value>(elements: interchangedIvs, interchangeVector,
1046 /*offset=*/packOp.getSourceRank());
1047 if (!dimsToOuterBlock.empty()) {
1048 interchangeVector =
1049 computeInterchangeFromDimPos(dimsPos: dimsToOuterBlock, rank: packOp.getSourceRank());
1050 interchangedIvs =
1051 interchange<Value>(elements: interchangedIvs, interchangeVector, /*offset=*/0);
1052 }
1053 DenseMap<int64_t, OpFoldResult> dimAndTileMapping =
1054 packOp.getDimAndTileMapping();
1055 SmallVector<OpFoldResult> sourceIndices;
1056 size_t pointLoopsOffset = 0;
1057 int64_t sourceRank = packOp.getSourceRank();
1058 for (auto dim : llvm::seq<int64_t>(Begin: 0, End: sourceRank)) {
1059 if (dimAndTileMapping.contains(Val: dim)) {
1060 AffineExpr i, j, tile;
1061 bindDims(ctx: builder.getContext(), exprs&: i, exprs&: j);
1062 bindSymbols(ctx: builder.getContext(), exprs&: tile);
1063 OpFoldResult sourceIndex = affine::makeComposedFoldedAffineApply(
1064 b&: builder, loc, expr: i * tile + j,
1065 operands: ArrayRef<OpFoldResult>{
1066 interchangedIvs[dim],
1067 interchangedIvs[pointLoopsOffset + packOp.getSourceRank()],
1068 dimAndTileMapping[dim]});
1069 sourceIndices.push_back(Elt: sourceIndex);
1070 ++pointLoopsOffset;
1071 } else {
1072 sourceIndices.push_back(Elt: interchangedIvs[dim]);
1073 }
1074 }
1075
1076 auto createLoad = [&]() -> Value {
1077 return memref::LoadOp::create(
1078 builder, location: loc, memref: packOp.getSource(),
1079 indices: getValueOrCreateConstantIndexOp(b&: builder, loc, valueOrAttrVec: sourceIndices));
1080 };
1081 Value scalar;
1082 if (auto paddingValue = packOp.getPaddingValue()) {
1083 ArithBuilder arithBuilder(builder, loc);
1084 Value isInBounds;
1085 for (auto dim : llvm::seq<int64_t>(Begin: 0, End: sourceRank)) {
1086 Value idx =
1087 getValueOrCreateConstantIndexOp(b&: builder, loc, ofr: sourceIndices[dim]);
1088 Value cond = arithBuilder.slt(
1089 lhs: idx, rhs: createOrFoldDimOp(b&: builder, loc, val: packOp.getSource(), dim));
1090 isInBounds = dim == 0 ? cond : arithBuilder._and(lhs: isInBounds, rhs: cond);
1091 }
1092 scalar = scf::IfOp::create(
1093 builder, location: loc, cond: isInBounds, /*thenBuilder=*/
1094 [&](OpBuilder &b, Location l) {
1095 scf::YieldOp::create(builder&: b, location: l, results: createLoad());
1096 },
1097 /*elseBuilder=*/
1098 [&](OpBuilder &b, Location l) {
1099 scf::YieldOp::create(builder&: b, location: l, results: paddingValue);
1100 })
1101 .getResult(i: 0);
1102 } else {
1103 scalar = createLoad();
1104 }
1105
1106 memref::StoreOp::create(builder, location: loc, valueToStore: scalar, memref: packOp.getDest(), indices: ivs);
1107}
1108
1109struct PackOpTiling
1110 : public TilingInterface::ExternalModel<PackOpTiling, linalg::PackOp> {
1111 using Base = TilingInterface::ExternalModel<PackOpTiling, linalg::PackOp>;
1112 using Base::getTiledImplementation;
1113
1114 SmallVector<utils::IteratorType> getLoopIteratorTypes(Operation *op) const {
1115 // Note that here we only consider untiled dimensions and outer tiled data
1116 // dimensions, the inner tiled data dimensions are materialized when
1117 // building the body of the operation.
1118 auto packOp = cast<PackOp>(Val: op);
1119 SmallVector<utils::IteratorType> iteratorTypes(
1120 packOp.getSourceRank(), utils::IteratorType::parallel);
1121 return iteratorTypes;
1122 }
1123
1124 SmallVector<Range> getIterationDomain(Operation *op, OpBuilder &b) const {
1125 return getPackUnPackIterationDomain<PackOp>(op: cast<PackOp>(Val: op), builder&: b);
1126 }
1127
1128 FailureOr<TilingResult>
1129 getTiledImplementation(Operation *op, OpBuilder &b,
1130 ArrayRef<OpFoldResult> offsets,
1131 ArrayRef<OpFoldResult> sizes) const {
1132 auto packOp = cast<PackOp>(Val: op);
1133 // Pack/unpack transformations on memrefs are currently unsupported.
1134 // The memref forms are mainly used for bufferization and scalar
1135 // lowering. Other uses are not recommended without strong motivation.
1136 // See #225650 for details.
1137 if (!packOp.hasPureTensorSemantics())
1138 return failure();
1139
1140 Location loc = packOp.getLoc();
1141
1142 // The tiling is applied on interchanged dimensions. We have to undo the
1143 // interchange to map sizes and offsets to the original input.
1144 int64_t inputRank = packOp.getSourceRank();
1145 SmallVector<OpFoldResult> origOffsets(offsets);
1146 SmallVector<OpFoldResult> origSizes(sizes);
1147 applyPermToRange(offsets&: origOffsets, sizes&: origSizes,
1148 permutation: invertPermutationVector(permutation: packOp.getOuterDimsPerm()));
1149
1150 DenseMap<int64_t, OpFoldResult> dimAndTileMapping =
1151 packOp.getDimAndTileMapping();
1152 SmallVector<OpFoldResult> srcDimValues =
1153 tensor::getMixedSizes(builder&: b, loc, value: packOp.getSource());
1154 SmallVector<OpFoldResult> inputIndices, inputSizes;
1155 for (auto dim : llvm::seq<int64_t>(Begin: 0, End: inputRank)) {
1156 using AV = affine::AffineValueExpr;
1157 affine::AffineBuilder ab(b, loc);
1158 AffineExpr dim0, dim1, sym;
1159 bindDims(ctx: b.getContext(), exprs&: dim0, exprs&: dim1);
1160 bindSymbols(ctx: b.getContext(), exprs&: sym);
1161 if (dimAndTileMapping.count(Val: dim)) {
1162 // If the data dimension is tiled, the i-th index is the product of
1163 // offset_i and tile_i, and the i-th size is the product of sizes_i and
1164 // tile_i.
1165 auto avOffset = AV(dim0).bind(v: origOffsets[dim]);
1166 auto avSize = AV(dim0).bind(v: origSizes[dim]);
1167 auto avTileSize = AV(sym).bind(v: dimAndTileMapping[dim]);
1168 inputIndices.push_back(Elt: ab.mul(lhs: avOffset, rhs: avTileSize));
1169 inputSizes.push_back(Elt: ab.mul(lhs: avSize, rhs: avTileSize));
1170 } else {
1171 inputIndices.push_back(Elt: origOffsets[dim]);
1172 inputSizes.push_back(Elt: origSizes[dim]);
1173 }
1174
1175 // Limit the size of the input operand for incomplete tiles.
1176 if (packOp.getPaddingValue()) {
1177 OpFoldResult dimSize = srcDimValues[dim];
1178 auto avDimSize = AV(dim0).bind(v: dimSize);
1179 auto avInputIdx = AV(dim1).bind(v: inputIndices.back());
1180 inputSizes.back() =
1181 ab.min(vals: {inputSizes.back(), ab.sub(lhs: avDimSize, rhs: avInputIdx)});
1182 }
1183 }
1184
1185 auto oneAttr = b.getI64IntegerAttr(value: 1);
1186 SmallVector<OpFoldResult> strides(inputRank, oneAttr);
1187
1188 SmallVector<Value> tiledOperands;
1189 auto sourceSlice = tensor::ExtractSliceOp::create(
1190 builder&: b, location: loc, source: packOp.getSource(), offsets: inputIndices, sizes: inputSizes, strides);
1191 tiledOperands.push_back(Elt: sourceSlice);
1192
1193 SmallVector<OpFoldResult> outputOffsets, outputSizes;
1194 if (failed(Result: getResultTilePosition(op, b, resultNumber: 0, offsets, sizes, resultOffsets&: outputOffsets,
1195 resultSizes&: outputSizes)))
1196 return {};
1197
1198 strides.append(NumInputs: packOp.getDestRank() - inputRank, Elt: oneAttr);
1199 auto outSlice = tensor::ExtractSliceOp::create(
1200 builder&: b, location: loc, source: packOp.getDest(), offsets: outputOffsets, sizes: outputSizes, strides);
1201 tiledOperands.push_back(Elt: outSlice);
1202
1203 if (auto val = packOp.getPaddingValue())
1204 tiledOperands.push_back(Elt: val);
1205 for (auto tile : packOp.getInnerTiles())
1206 tiledOperands.push_back(Elt: tile);
1207
1208 PackOp tiledPackOp =
1209 PackOp::create(builder&: b, location: loc, resultTypes: TypeRange{outSlice.getType()}, operands: tiledOperands,
1210 properties: packOp.getProperties(),
1211 discardableAttributes: packOp->getDiscardableAttrDictionary().getValue());
1212
1213 return TilingResult{
1214 .tiledOps: {tiledPackOp},
1215 .tiledValues: SmallVector<Value>(tiledPackOp->getResults()),
1216 .generatedSlices: llvm::to_vector(Range: ArrayRef<Operation *>{sourceSlice, outSlice})};
1217 }
1218
1219 LogicalResult
1220 getResultTilePosition(Operation *op, OpBuilder &b, unsigned resultNumber,
1221 ArrayRef<OpFoldResult> offsets,
1222 ArrayRef<OpFoldResult> sizes,
1223 SmallVector<OpFoldResult> &resultOffsets,
1224 SmallVector<OpFoldResult> &resultSizes) const {
1225 // The iteration domain is over outer dimensions of packed layout. In this
1226 // context, the outer dimensions of `resultOffsets` are `offsets`. The
1227 // inner dimensions of `resultOffsets` are zeros because tiling is not
1228 // applied to them.
1229 auto packOp = cast<PackOp>(Val: op);
1230 int64_t inputRank = packOp.getSourceRank();
1231 int64_t outputRank = packOp.getDestRank();
1232 auto zeroAttr = b.getI64IntegerAttr(value: 0);
1233 resultOffsets.assign(in_start: offsets.begin(), in_end: offsets.end());
1234 resultOffsets.append(NumInputs: outputRank - inputRank, Elt: zeroAttr);
1235
1236 ReifiedRankedShapedTypeDims outputShape;
1237 (void)reifyResultShapes(b, op: packOp, reifiedReturnShapes&: outputShape);
1238 resultSizes.assign(in_start: sizes.begin(), in_end: sizes.end());
1239 for (auto dataTileDim : llvm::seq<unsigned>(Begin: inputRank, End: outputRank))
1240 resultSizes.push_back(Elt: outputShape[0][dataTileDim]);
1241
1242 return success();
1243 }
1244
1245 FailureOr<TilingResult>
1246 generateResultTileValue(Operation *op, OpBuilder &b, unsigned resultNumber,
1247 ArrayRef<OpFoldResult> offsets,
1248 ArrayRef<OpFoldResult> sizes) const {
1249 return generateResultTileValue(op, b, resultNumber, offsets, sizes,
1250 /*innerTileAlignments=*/{});
1251 }
1252
1253 FailureOr<TilingResult> generateResultTileValue(
1254 Operation *op, OpBuilder &b, unsigned resultNumber,
1255 ArrayRef<OpFoldResult> offsets, ArrayRef<OpFoldResult> sizes,
1256 ArrayRef<InnerTileAlignment> innerTileAlignments) const {
1257 auto packOp = cast<PackOp>(Val: op);
1258 int64_t numTiles = packOp.getInnerDimsPos().size();
1259
1260 // linalg.pack op is fusible (as a producer) only if full inner tiles are
1261 // iterated or inner dims are not tiled. Otherwise, it will generate a
1262 // sequence of non-trivial ops (for partial tiles).
1263 for (auto offset : offsets.take_back(N: numTiles))
1264 if (!isZeroInteger(v: offset))
1265 return failure();
1266
1267 // Each requested inner-dim size must cover a full inner tile. A caller may
1268 // instead assert this via an `Equal` alignment hint. The hint is indexed by
1269 // source dim, matching the consumer-fusion path.
1270 ArrayRef<int64_t> innerDimsPos = packOp.getInnerDimsPos();
1271 SmallVector<OpFoldResult> mixedTiles = packOp.getMixedTiles();
1272 ArrayRef<OpFoldResult> innerSizes = sizes.take_back(N: numTiles);
1273 for (auto [i, pos] : llvm::enumerate(First&: innerDimsPos)) {
1274 InnerTileAlignment alignment =
1275 pos < static_cast<int64_t>(innerTileAlignments.size())
1276 ? innerTileAlignments[pos]
1277 : InnerTileAlignment::Unknown;
1278 if (alignment != InnerTileAlignment::Equal &&
1279 !isEqualConstantIntOrValue(ofr1: mixedTiles[i], ofr2: innerSizes[i]))
1280 return failure();
1281 }
1282
1283 FailureOr<TilingResult> tilingResult = getTiledImplementation(
1284 op, b, offsets: offsets.drop_back(N: numTiles), sizes: sizes.drop_back(N: numTiles));
1285 if (failed(Result: tilingResult))
1286 return failure();
1287 return tilingResult.value();
1288 }
1289
1290 LogicalResult generateScalarImplementation(Operation *op, OpBuilder &builder,
1291 Location loc,
1292 ValueRange ivs) const {
1293 auto packOp = cast<PackOp>(Val: op);
1294 assert(packOp.hasPureBufferSemantics() &&
1295 "expected operation to have buffer semantics");
1296 OpBuilder::InsertionGuard g(builder);
1297 // The `ivs` already represent the position into the output for the non
1298 // data-tile dimensions.
1299 SmallVector<Value> ivVec(ivs);
1300
1301 // Get output shape - for memrefs, get dimensions from dest directly.
1302 SmallVector<OpFoldResult> outputShape;
1303 Value dest = packOp.getDest();
1304 for (auto dim : llvm::seq<int64_t>(Begin: 0, End: packOp.getDestRank()))
1305 outputShape.push_back(Elt: createOrFoldDimOp(b&: builder, loc, val: dest, dim));
1306
1307 // Generate the loops that iterate over the data tile.
1308 Value zero = arith::ConstantIndexOp::create(builder, location: loc, value: 0);
1309 Value one = arith::ConstantIndexOp::create(builder, location: loc, value: 1);
1310
1311 // All loops except the innermost are simple loops that just iterate
1312 // over the tile dimensions.
1313 for (auto dataTileDim : llvm::seq<unsigned>(Begin: packOp.getSourceRank(),
1314 End: packOp.getDestRank() - 1)) {
1315 Value ub = getValueOrCreateConstantIndexOp(b&: builder, loc,
1316 ofr: outputShape[dataTileDim]);
1317 scf::ForOp loop = scf::ForOp::create(builder, location: loc, lowerBound: zero, upperBound: ub, step: one);
1318 builder.setInsertionPointToStart(loop.getBody());
1319 ivVec.push_back(Elt: loop.getInductionVar());
1320 }
1321 // The body of the innermost loops does the actual data movement.
1322 scf::ForOp::create(
1323 builder, location: loc, lowerBound: zero,
1324 upperBound: getValueOrCreateConstantIndexOp(b&: builder, loc, ofr: outputShape.back()), step: one,
1325 initArgs: ValueRange{},
1326 odsArg4: [&](OpBuilder &bodyBuilder, Location bodyLoc, Value iv,
1327 ValueRange regionIterArgs) {
1328 ivVec.push_back(Elt: iv);
1329 generatePackOpScalarImplementationBody(packOp, builder&: bodyBuilder, loc: bodyLoc,
1330 ivs: ivVec);
1331 scf::YieldOp::create(builder&: bodyBuilder, location: bodyLoc);
1332 });
1333 return success();
1334 }
1335
1336 LogicalResult getIterationDomainTileFromOperandTiles(
1337 Operation *op, OpBuilder &b, ArrayRef<unsigned> operandNumbers,
1338 ArrayRef<SmallVector<OpFoldResult>> allOffsets,
1339 ArrayRef<SmallVector<OpFoldResult>> allSizes,
1340 SmallVectorImpl<OpFoldResult> &resultOffsets,
1341 SmallVectorImpl<OpFoldResult> &resultSizes) const {
1342 return getIterationDomainTileFromOperandTiles(
1343 op, b, operandNumbers, allOffsets, allSizes, resultOffsets, resultSizes,
1344 /*innerTileAlignments=*/{});
1345 }
1346
1347 /// Method to return the position of iteration domain tile computed by the
1348 /// tiled operation. In current `linalg.pack` context, the `resultOffsets` and
1349 /// `resultSizes` only cover outer dimensions.
1350 LogicalResult getIterationDomainTileFromOperandTiles(
1351 Operation *op, OpBuilder &b, ArrayRef<unsigned> operandNumbers,
1352 ArrayRef<SmallVector<OpFoldResult>> allOffsets,
1353 ArrayRef<SmallVector<OpFoldResult>> allSizes,
1354 SmallVectorImpl<OpFoldResult> &resultOffsets,
1355 SmallVectorImpl<OpFoldResult> &resultSizes,
1356 ArrayRef<InnerTileAlignment> innerTileAlignments) const {
1357 if (operandNumbers.size() != 1 || operandNumbers[0] != 0) {
1358 LLVM_DEBUG(
1359 { llvm::dbgs() << "unsupported operands for consumer fusion"; });
1360 return failure();
1361 }
1362
1363 ArrayRef<OpFoldResult> offsets(allOffsets[0]);
1364 ArrayRef<OpFoldResult> sizes(allSizes[0]);
1365 auto packOp = cast<PackOp>(Val: op);
1366 Location loc = packOp.getLoc();
1367 SmallVector<OpFoldResult> outerDimOffsets, outerDimSizes;
1368 DenseMap<int64_t, OpFoldResult> dimAndTileMapping =
1369 packOp.getDimAndTileMapping();
1370 SmallVector<int64_t> outerShapeWithoutTranspose(
1371 packOp.getDestType().getShape().take_front(N: packOp.getSourceRank()));
1372 if (!packOp.getOuterDimsPerm().empty()) {
1373 applyPermutationToVector(
1374 inVec&: outerShapeWithoutTranspose,
1375 permutation: invertPermutationVector(permutation: packOp.getOuterDimsPerm()));
1376 }
1377 for (auto dim : llvm::seq<int64_t>(Size: packOp.getSourceRank())) {
1378 if (dimAndTileMapping.count(Val: dim)) {
1379 FailureOr<int64_t> cstTileSize =
1380 ValueBoundsConstraintSet::computeConstantBound(
1381 type: presburger::BoundType::UB, var: sizes[dim],
1382 /*stopCondition=*/nullptr,
1383 options: ValueBoundsOptions{/*closedUB=*/true});
1384 std::optional<int64_t> cstInnerSize =
1385 getConstantIntValue(ofr: dimAndTileMapping[dim]);
1386
1387 // A caller-supplied alignment hint (see InnerTileAlignment) asserts
1388 // that this packed dimension is tiled and how its loop tile size
1389 // relates to the pack op inner tile size.
1390 InnerTileAlignment innerTileAlignment =
1391 dim < static_cast<int64_t>(innerTileAlignments.size())
1392 ? innerTileAlignments[dim]
1393 : InnerTileAlignment::Unknown;
1394
1395 // If a dimension is not tiled, it is always valid to fuse the pack op,
1396 // even if the op has padding semantics. Because it always generates a
1397 // full slice along the dimension. The tile sizes are for unpacked
1398 // domain, i.e., `srcDimSize`, so `tileSize < srcDimSize` means that the
1399 // dimension is tiled.
1400 // TODO: It could be untiled if the `srcDimSize` is dynamic. It is a
1401 // hard check to determine if a dimension is tiled or not.
1402 // A non-`Unknown` hint also means the caller asserts the dimension is
1403 // tiled: `cstTileSize` is an upper bound, so a scalable/`min`-shaped
1404 // tile (whose bound equals `srcDimSize`) would otherwise be mistaken
1405 // for untiled and bypass the hint below.
1406 int64_t srcDimSize = packOp.getSourceType().getDimSize(idx: dim);
1407 int64_t destDimSize = outerShapeWithoutTranspose[dim];
1408 bool isTiled = innerTileAlignment != InnerTileAlignment::Unknown ||
1409 failed(Result: cstTileSize) ||
1410 ShapedType::isDynamic(dValue: srcDimSize) ||
1411 cstTileSize.value() < srcDimSize;
1412 if (!isTiled) {
1413 outerDimOffsets.push_back(Elt: offsets[dim]);
1414 if (ShapedType::isStatic(dValue: destDimSize)) {
1415 outerDimSizes.push_back(Elt: b.getIndexAttr(value: destDimSize));
1416 } else {
1417 outerDimSizes.push_back(
1418 Elt: b.createOrFold<tensor::DimOp>(location: loc, args: packOp.getDest(), args&: dim));
1419 }
1420 continue;
1421 }
1422
1423 // Currently fusing `packOp` as consumer only expects perfect tiling
1424 // scenario because even if without padding semantic, the `packOp` may
1425 // also yield incomplete tiles. E.g. tensor<30xf32> -> tensor<5x6xf32>,
1426 // where the `tileSize` from operand of `packOp` is 5, which is not
1427 // exactly divided by `innerTile`(=6) of `packOp`. As the result:
1428 // 1. the first slice is extracted from (0) to (4) and inserted into
1429 // (0,0)~(0,4) at first row.
1430 // 2. the second slice is extracted from (5) to (9) and SHOULD BE
1431 // respectively inserted into two rows with different length, including
1432 // first row: (0,5) and second row (1,0)~(1,3). It is hard to coordinate
1433 // them, thus adding below constraint to bypass them temporarily. In
1434 // another word, we can only support tiling with consumer if the tile
1435 // size for the producer is a multiple of the inner tile size for the
1436 // packed dimensions at this moment.
1437
1438 // The caller may assert how this packed dimension's loop tile size
1439 // relates to the inner tile size via `innerTileAlignments` (see
1440 // InnerTileAlignment). The hint is the source of truth and is honored
1441 // when present. When both sizes are also statically known we assert the
1442 // hint agrees with them (a contradicting hint is a caller bug). When
1443 // the hint is `Unknown`, fall back to requiring a statically-provable
1444 // multiple.
1445 bool assumeInnerTileSizesMatchTiles =
1446 innerTileAlignment == InnerTileAlignment::Equal;
1447 bool staticallyDecidable =
1448 !failed(Result: cstTileSize) && cstInnerSize.has_value();
1449 if (innerTileAlignment == InnerTileAlignment::Unknown) {
1450 if (!staticallyDecidable || *cstTileSize % *cstInnerSize != 0)
1451 return failure();
1452 } else if (staticallyDecidable) {
1453 assert(*cstTileSize % *cstInnerSize == 0 &&
1454 "InnerTileAlignment hint contradicts statically known tile "
1455 "sizes");
1456 assert((innerTileAlignment != InnerTileAlignment::Equal ||
1457 *cstTileSize == *cstInnerSize) &&
1458 "InnerTileAlignment::Equal contradicts statically known tile "
1459 "sizes");
1460 }
1461
1462 using AV = affine::AffineValueExpr;
1463 affine::AffineBuilder ab(b, loc);
1464 AffineExpr dim0, sym;
1465 bindDims(ctx: b.getContext(), exprs&: dim0);
1466 bindSymbols(ctx: b.getContext(), exprs&: sym);
1467 auto avOffset = AV(dim0).bind(v: offsets[dim]);
1468 auto avSize = AV(dim0).bind(v: sizes[dim]);
1469 auto avTileSize = AV(sym).bind(v: dimAndTileMapping[dim]);
1470 outerDimOffsets.push_back(Elt: ab.floor(lhs: avOffset, rhs: avTileSize));
1471 // If the tile size equals the inner tile size, the outer dims are
1472 // always 1.
1473 outerDimSizes.push_back(Elt: assumeInnerTileSizesMatchTiles
1474 ? b.getIndexAttr(value: 1)
1475 : ab.ceil(lhs: avSize, rhs: avTileSize));
1476 } else {
1477 outerDimOffsets.push_back(Elt: offsets[dim]);
1478 outerDimSizes.push_back(Elt: sizes[dim]);
1479 }
1480 }
1481 applyPermToRange(offsets&: outerDimOffsets, sizes&: outerDimSizes, permutation: packOp.getOuterDimsPerm());
1482 resultOffsets = outerDimOffsets;
1483 resultSizes = outerDimSizes;
1484 return success();
1485 }
1486
1487 FailureOr<TilingResult> getTiledImplementationFromOperandTiles(
1488 Operation *op, OpBuilder &b, ArrayRef<unsigned> operandNumbers,
1489 ArrayRef<SmallVector<OpFoldResult>> allOffsets,
1490 ArrayRef<SmallVector<OpFoldResult>> allSizes) const {
1491 return getTiledImplementationFromOperandTiles(op, b, operandNumbers,
1492 allOffsets, allSizes,
1493 /*innerTileAlignments=*/{});
1494 }
1495
1496 /// Method to return the tiled implementation of linalg.pack as a consumer.
1497 FailureOr<TilingResult> getTiledImplementationFromOperandTiles(
1498 Operation *op, OpBuilder &b, ArrayRef<unsigned> operandNumbers,
1499 ArrayRef<SmallVector<OpFoldResult>> allOffsets,
1500 ArrayRef<SmallVector<OpFoldResult>> allSizes,
1501 ArrayRef<InnerTileAlignment> innerTileAlignments) const {
1502 if (operandNumbers.size() != 1 || operandNumbers[0] != 0) {
1503 LLVM_DEBUG({ llvm::dbgs() << "unhandled operands for consumer fusion"; });
1504 return failure();
1505 }
1506
1507 ArrayRef<OpFoldResult> offsets(allOffsets[0]);
1508 ArrayRef<OpFoldResult> sizes(allSizes[0]);
1509
1510 auto packOp = cast<PackOp>(Val: op);
1511 // Pack/unpack transformations on memrefs are currently unsupported.
1512 // The memref forms are mainly used for bufferization and scalar
1513 // lowering. Other uses are not recommended without strong motivation.
1514 // See #225650 for details.
1515 if (!packOp.hasPureTensorSemantics())
1516 return failure();
1517
1518 Location loc = packOp.getLoc();
1519
1520 int64_t inputRank = packOp.getSourceRank();
1521 auto oneAttr = b.getI64IntegerAttr(value: 1);
1522 SmallVector<OpFoldResult> strides(inputRank, oneAttr);
1523
1524 SmallVector<Value> tiledOperands;
1525 auto sourceSlice = tensor::ExtractSliceOp::create(
1526 builder&: b, location: loc, source: packOp.getSource(), offsets, sizes, strides);
1527 tiledOperands.push_back(Elt: sourceSlice);
1528
1529 SmallVector<OpFoldResult> outerDimOffsets, outerDimSizes;
1530 if (failed(Result: getIterationDomainTileFromOperandTiles(
1531 op, b, operandNumbers, allOffsets, allSizes, resultOffsets&: outerDimOffsets,
1532 resultSizes&: outerDimSizes, innerTileAlignments)))
1533 return failure();
1534
1535 SmallVector<OpFoldResult> outputOffsets, outputSizes;
1536 if (failed(Result: getResultTilePosition(op, b, resultNumber: 0, offsets: outerDimOffsets, sizes: outerDimSizes,
1537 resultOffsets&: outputOffsets, resultSizes&: outputSizes)))
1538 return failure();
1539
1540 strides.append(NumInputs: packOp.getDestRank() - inputRank, Elt: oneAttr);
1541 auto outSlice = tensor::ExtractSliceOp::create(
1542 builder&: b, location: loc, source: packOp.getDest(), offsets: outputOffsets, sizes: outputSizes, strides);
1543 tiledOperands.push_back(Elt: outSlice);
1544
1545 if (auto val = packOp.getPaddingValue())
1546 tiledOperands.push_back(Elt: val);
1547 for (auto tile : packOp.getInnerTiles())
1548 tiledOperands.push_back(Elt: tile);
1549
1550 PackOp tiledPackOp =
1551 PackOp::create(builder&: b, location: loc, resultTypes: TypeRange{outSlice.getType()}, operands: tiledOperands,
1552 properties: packOp.getProperties(),
1553 discardableAttributes: packOp->getDiscardableAttrDictionary().getValue());
1554
1555 return TilingResult{
1556 .tiledOps: {tiledPackOp},
1557 .tiledValues: SmallVector<Value>(tiledPackOp->getResults()),
1558 .generatedSlices: llvm::to_vector(Range: ArrayRef<Operation *>{sourceSlice, outSlice})};
1559 }
1560};
1561
1562struct UnpackTileDimInfo {
1563 bool isAlignedToInnerTileSize;
1564 OpFoldResult sourceOffset;
1565 OpFoldResult sourceSize;
1566 OpFoldResult resultOffset;
1567 OpFoldResult destExpandedSize;
1568};
1569
1570/// Returns the needed information for tiling unpack op on `tileDim` with given
1571/// `tileOffset` and `tileSize`. For more details, see the comment of the
1572/// `getTiledImplementation`.
1573static UnpackTileDimInfo
1574getUnpackTileDimInfo(OpBuilder &b, UnPackOp unpackOp, int64_t tileDim,
1575 OpFoldResult tileOffset, OpFoldResult tileSize,
1576 InnerTileAlignment innerTileAlignment) {
1577 UnpackTileDimInfo info;
1578 Attribute zeroAttr = b.getIndexAttr(value: 0);
1579 Attribute oneAttr = b.getIndexAttr(value: 1);
1580 DenseMap<int64_t, OpFoldResult> dimAndTileMapping =
1581 unpackOp.getDimAndTileMapping();
1582 // The dimension is not one of packed data dimension.
1583 if (!dimAndTileMapping.count(Val: tileDim)) {
1584 info.isAlignedToInnerTileSize = true;
1585 info.sourceOffset = tileOffset;
1586 info.sourceSize = tileSize;
1587 info.resultOffset = zeroAttr;
1588 info.destExpandedSize = tileSize;
1589 return info;
1590 }
1591
1592 Location loc = unpackOp.getLoc();
1593 using AV = affine::AffineValueExpr;
1594 affine::AffineBuilder ab(b, loc);
1595 AffineExpr dim0, dim1, sym0;
1596 bindDims(ctx: b.getContext(), exprs&: dim0, exprs&: dim1);
1597 bindSymbols(ctx: b.getContext(), exprs&: sym0);
1598
1599 OpFoldResult innerTileSize = dimAndTileMapping[tileDim];
1600
1601 info.isAlignedToInnerTileSize = false;
1602 FailureOr<int64_t> cstSize = ValueBoundsConstraintSet::computeConstantBound(
1603 type: presburger::BoundType::UB, var: tileSize,
1604 /*stopCondition=*/nullptr, options: ValueBoundsOptions{/*closedUB=*/true});
1605 std::optional<int64_t> cstInnerSize = getConstantIntValue(ofr: innerTileSize);
1606 // The caller may assert how this dimension's loop tile size relates to the
1607 // op's inner tile size via `innerTileAlignment` (see InnerTileAlignment). The
1608 // hint is the source of truth and is honored when present: `Equal`/`Multiple`
1609 // both mean the tile is aligned to (a multiple of) the inner tile, and
1610 // `Equal` additionally collapses the source slice to a single inner tile.
1611 // When both sizes are also statically known we assert the hint agrees with
1612 // them (a contradicting hint is a caller bug). When `Unknown`, fall back to
1613 // the static upper-bound path below.
1614 bool assumeInnerTileSizesMatchTiles =
1615 innerTileAlignment == InnerTileAlignment::Equal;
1616 bool staticallyDecidable = !failed(Result: cstSize) && cstInnerSize.has_value();
1617 if (innerTileAlignment != InnerTileAlignment::Unknown) {
1618 info.isAlignedToInnerTileSize = true;
1619 if (staticallyDecidable) {
1620 assert(*cstSize % *cstInnerSize == 0 &&
1621 "InnerTileAlignment hint contradicts statically known tile sizes");
1622 assert((innerTileAlignment != InnerTileAlignment::Equal ||
1623 *cstSize == *cstInnerSize) &&
1624 "InnerTileAlignment::Equal contradicts statically known tile "
1625 "sizes");
1626 }
1627 }
1628 if (info.isAlignedToInnerTileSize || (!failed(Result: cstSize) && cstInnerSize)) {
1629 if (!info.isAlignedToInnerTileSize && *cstSize % *cstInnerSize == 0)
1630 info.isAlignedToInnerTileSize = true;
1631
1632 // If the tiling size equals to the inner tiling size, the outer dims are
1633 // always 1.
1634 if (assumeInnerTileSizesMatchTiles ||
1635 (cstInnerSize && !failed(Result: cstSize) && *cstInnerSize == *cstSize)) {
1636 auto lhs = AV(dim0).bind(v: tileOffset);
1637 auto rhs = AV(dim1).bind(v: innerTileSize);
1638 info.sourceOffset = ab.floor(lhs, rhs);
1639 info.sourceSize = oneAttr;
1640 info.resultOffset = zeroAttr;
1641 info.destExpandedSize = tileSize;
1642 return info;
1643 }
1644 }
1645
1646 if (info.isAlignedToInnerTileSize) {
1647 info.sourceOffset =
1648 ab.floor(lhs: AV(dim0).bind(v: tileOffset), rhs: AV(dim1).bind(v: innerTileSize));
1649 info.resultOffset = zeroAttr;
1650 info.destExpandedSize = tileSize;
1651
1652 // The ceilDiv is needed here because there could be incomplete tile even
1653 // it is perfect tiling cases. E.g.,
1654 // %0 = unpack tensor<33x2xf32> into tensor<64xf32>
1655 // If the tiling size is 32, there will be 3 tiles. Two of them have
1656 // size=32; one of them have size=2. The size is represented using
1657 // affine_min op; we need ceilDiv.
1658 info.sourceSize =
1659 ab.ceil(lhs: AV(dim0).bind(v: tileSize), rhs: AV(dim1).bind(v: innerTileSize));
1660 return info;
1661 }
1662
1663 affine::DivModValue firstCoord = affine::getDivMod(
1664 b, loc, lhs: getValueOrCreateConstantIndexOp(b, loc, ofr: tileOffset),
1665 rhs: getValueOrCreateConstantIndexOp(b, loc, ofr: innerTileSize));
1666 OpFoldResult tileExclusiveBound =
1667 ab.add(lhs: AV(dim0).bind(v: tileOffset), rhs: AV(dim1).bind(v: tileSize));
1668 affine::DivModValue lastCoord = affine::getDivMod(
1669 b, loc,
1670 lhs: getValueOrCreateConstantIndexOp(
1671 b, loc,
1672 ofr: ab.sub(lhs: AV(dim0).bind(v: tileExclusiveBound), rhs: AV(dim1).bind(v: oneAttr))),
1673 rhs: getValueOrCreateConstantIndexOp(b, loc, ofr: innerTileSize));
1674
1675 OpFoldResult lengthMinusOne = ab.sub(lhs: AV(dim0).bind(v: lastCoord.quotient),
1676 rhs: AV(dim1).bind(v: firstCoord.quotient));
1677 info.sourceSize =
1678 ab.add(lhs: AV(dim0).bind(v: lengthMinusOne), rhs: AV(dim1).bind(v: oneAttr));
1679 info.sourceOffset = firstCoord.quotient;
1680 info.resultOffset = firstCoord.remainder;
1681 // Do not create an Affine ops for expanded size because the affine op is too
1682 // complicated which would trigger an issue in affine ops simplification.
1683 info.destExpandedSize = b.createOrFold<arith::MulIOp>(
1684 location: loc, args: getValueOrCreateConstantIndexOp(b, loc, ofr: info.sourceSize),
1685 args: getValueOrCreateConstantIndexOp(b, loc, ofr: innerTileSize));
1686 return info;
1687}
1688
1689struct UnPackOpTiling
1690 : public TilingInterface::ExternalModel<UnPackOpTiling, linalg::UnPackOp> {
1691 using Base = TilingInterface::ExternalModel<UnPackOpTiling, linalg::UnPackOp>;
1692 using Base::getIterationDomainTileFromOperandTiles;
1693
1694 SmallVector<utils::IteratorType> getLoopIteratorTypes(Operation *op) const {
1695 auto unpackOp = cast<UnPackOp>(Val: op);
1696 SmallVector<utils::IteratorType> iteratorTypes(
1697 unpackOp.getDestRank(), utils::IteratorType::parallel);
1698 return iteratorTypes;
1699 }
1700
1701 SmallVector<Range> getIterationDomain(Operation *op, OpBuilder &b) const {
1702 return getPackUnPackIterationDomain<UnPackOp>(op: cast<UnPackOp>(Val: op), builder&: b);
1703 }
1704
1705 /// There are two cases in tiling unpack ops. If the tiling size is aligned to
1706 /// the inner tile size, the corresponding tiles of source are all complete.
1707 /// Otherwise, there are in-complete tiles. We will need to expand the slice
1708 /// of source for getting complete tiles. The tiled unpack op unpacks more
1709 /// data from source, so We'll need an extract_slice op to shift and truncate
1710 /// the output.
1711 /// Take Nn_to_N as an example. Say that N=32, n=8, and tiling_size=15. The
1712 /// coordinates of second tile (i.e., result[15..31]) are
1713 /// [(1, 7), (2, 0,), (2, 1) ... (3, 6), (3, 7)]. The first row and the last
1714 /// row are incomplete tiles. To represent the unpack op, we have to complete
1715 /// the rows. I.e., the input coordinates would start with (1, 0); end with
1716 /// (3, 7). In this context, the tiled unpack produces a (3 * n) elements
1717 /// because there are 3 rows in total. Follow by a tensor.extract_slice op, we
1718 /// can get the actual result.
1719 FailureOr<TilingResult>
1720 getTiledImplementation(Operation *op, OpBuilder &b,
1721 ArrayRef<OpFoldResult> offsets,
1722 ArrayRef<OpFoldResult> sizes) const {
1723 return getTiledImplementation(op, b, offsets, sizes,
1724 /*innerTileAlignments=*/{});
1725 }
1726
1727 FailureOr<TilingResult> getTiledImplementation(
1728 Operation *op, OpBuilder &b, ArrayRef<OpFoldResult> offsets,
1729 ArrayRef<OpFoldResult> sizes,
1730 ArrayRef<InnerTileAlignment> innerTileAlignments) const {
1731 auto unpackOp = cast<UnPackOp>(Val: op);
1732 // Pack/unpack transformations on memrefs are currently unsupported.
1733 // The memref forms are mainly used for bufferization and scalar
1734 // lowering. Other uses are not recommended without strong motivation.
1735 // See #225650 for details.
1736 if (!unpackOp.hasPureTensorSemantics())
1737 return failure();
1738
1739 int64_t srcRank = unpackOp.getSourceRank();
1740 int64_t destRank = unpackOp.getDestRank();
1741 int64_t numInnerTiles = srcRank - destRank;
1742 Location loc = unpackOp.getLoc();
1743
1744 // The perfect tiling case indicates that the tiling sizes are multiple of
1745 // inner_tile_size. In this context, no extra data is needed when
1746 // representing the tiled unpack op.
1747 bool isPerfectTilingCase = true;
1748 Attribute oneAttr = b.getIndexAttr(value: 1);
1749 SmallVector<OpFoldResult> sliceSrcStrides(destRank, oneAttr);
1750 SmallVector<OpFoldResult> sliceSrcIndices, sliceSrcSizes;
1751 SmallVector<OpFoldResult> destExpandedSizes, resultOffsetsFromDest;
1752 for (auto dim : llvm::seq<int64_t>(Begin: 0, End: destRank)) {
1753 UnpackTileDimInfo info = getUnpackTileDimInfo(
1754 b, unpackOp, tileDim: dim, tileOffset: offsets[dim], tileSize: sizes[dim],
1755 innerTileAlignment: dim < static_cast<int64_t>(innerTileAlignments.size())
1756 ? innerTileAlignments[dim]
1757 : InnerTileAlignment::Unknown);
1758 if (!info.isAlignedToInnerTileSize)
1759 isPerfectTilingCase = false;
1760 sliceSrcIndices.push_back(Elt: info.sourceOffset);
1761 sliceSrcSizes.push_back(Elt: info.sourceSize);
1762 destExpandedSizes.push_back(Elt: info.destExpandedSize);
1763 resultOffsetsFromDest.push_back(Elt: info.resultOffset);
1764 }
1765
1766 // The tiling is applied on destination dimensions. We have to apply the
1767 // interchange on source dimensions if outer_dims_perm is set.
1768 applyPermToRange(offsets&: sliceSrcIndices, sizes&: sliceSrcSizes,
1769 permutation: unpackOp.getOuterDimsPerm());
1770 Attribute zeroAttr = b.getIndexAttr(value: 0);
1771 sliceSrcIndices.append(NumInputs: numInnerTiles, Elt: zeroAttr);
1772 sliceSrcSizes.append(RHS: unpackOp.getMixedTiles());
1773 sliceSrcStrides.append(NumInputs: numInnerTiles, Elt: oneAttr);
1774 SmallVector<Operation *> generatedSlices;
1775 tensor::ExtractSliceOp sliceSource = tensor::ExtractSliceOp::create(
1776 builder&: b, location: loc, source: unpackOp.getSource(), offsets: sliceSrcIndices, sizes: sliceSrcSizes,
1777 strides: sliceSrcStrides);
1778 generatedSlices.push_back(Elt: sliceSource);
1779
1780 SmallVector<OpFoldResult> destStrides(destRank, oneAttr);
1781 Value sliceDest;
1782 if (isPerfectTilingCase) {
1783 auto destSliceOp = tensor::ExtractSliceOp::create(
1784 builder&: b, location: loc, source: unpackOp.getDest(), offsets, sizes, strides: destStrides);
1785 sliceDest = destSliceOp;
1786 generatedSlices.push_back(Elt: destSliceOp);
1787 } else {
1788 sliceDest = tensor::EmptyOp::create(
1789 builder&: b, location: loc, sizes: destExpandedSizes, elementType: unpackOp.getDestType().getElementType());
1790 }
1791
1792 SmallVector<Value> tiledOperands = {sliceSource.getResult(), sliceDest};
1793 for (auto tile : unpackOp.getInnerTiles())
1794 tiledOperands.push_back(Elt: tile);
1795
1796 UnPackOp tiledUnpackOp =
1797 UnPackOp::create(builder&: b, location: loc, resultTypes: TypeRange{sliceDest.getType()}, operands: tiledOperands,
1798 properties: unpackOp.getProperties(),
1799 discardableAttributes: unpackOp->getDiscardableAttrDictionary().getValue());
1800
1801 if (isPerfectTilingCase)
1802 return TilingResult{.tiledOps: {tiledUnpackOp},
1803 .tiledValues: SmallVector<Value>(tiledUnpackOp->getResults()),
1804 .generatedSlices: generatedSlices};
1805
1806 auto extractSlice = tensor::ExtractSliceOp::create(
1807 builder&: b, location: loc, source: tiledUnpackOp->getResult(idx: 0), offsets: resultOffsetsFromDest, sizes,
1808 strides: destStrides);
1809 return TilingResult{
1810 .tiledOps: {tiledUnpackOp}, .tiledValues: {extractSlice.getResult()}, .generatedSlices: generatedSlices};
1811 }
1812
1813 LogicalResult
1814 getResultTilePosition(Operation *op, OpBuilder &b, unsigned resultNumber,
1815 ArrayRef<OpFoldResult> offsets,
1816 ArrayRef<OpFoldResult> sizes,
1817 SmallVector<OpFoldResult> &resultOffsets,
1818 SmallVector<OpFoldResult> &resultSizes) const {
1819 resultOffsets = llvm::to_vector(Range&: offsets);
1820 resultSizes = llvm::to_vector(Range&: sizes);
1821 return success();
1822 }
1823
1824 FailureOr<TilingResult>
1825 generateResultTileValue(Operation *op, OpBuilder &b, unsigned resultNumber,
1826 ArrayRef<OpFoldResult> offsets,
1827 ArrayRef<OpFoldResult> sizes) const {
1828 return generateResultTileValue(op, b, resultNumber, offsets, sizes,
1829 /*innerTileAlignments=*/{});
1830 }
1831
1832 FailureOr<TilingResult> generateResultTileValue(
1833 Operation *op, OpBuilder &b, unsigned resultNumber,
1834 ArrayRef<OpFoldResult> offsets, ArrayRef<OpFoldResult> sizes,
1835 ArrayRef<InnerTileAlignment> innerTileAlignments) const {
1836 FailureOr<TilingResult> tilingResult =
1837 getTiledImplementation(op, b, offsets, sizes, innerTileAlignments);
1838 if (failed(Result: tilingResult))
1839 return failure();
1840 return tilingResult.value();
1841 }
1842
1843 LogicalResult generateScalarImplementation(Operation *op, OpBuilder &builder,
1844 Location loc,
1845 ValueRange ivs) const {
1846 auto unpackOp = cast<UnPackOp>(Val: op);
1847 assert(unpackOp.hasPureBufferSemantics() &&
1848 "expected operation to have buffer semantics");
1849 assert(ivs.size() == unpackOp.getDestRank() &&
1850 "number of ivs must match the rank of the output tensor");
1851 OpBuilder::InsertionGuard g(builder);
1852
1853 DenseMap<int64_t, OpFoldResult> dimAndTileMapping =
1854 unpackOp.getDimAndTileMapping();
1855 // Untiled loops and tile loops induction variables.
1856 SmallVector<Value> inputIvs;
1857 // Point loops induction variables.
1858 SmallVector<Value> inputIvsPointLoops;
1859 inputIvs.reserve(N: unpackOp.getDestRank());
1860 inputIvsPointLoops.reserve(N: dimAndTileMapping.size());
1861 for (auto dim : llvm::seq<int64_t>(Begin: 0, End: unpackOp.getDestRank())) {
1862 if (dimAndTileMapping.count(Val: dim)) {
1863 affine::DivModValue divMod =
1864 affine::getDivMod(b&: builder, loc, lhs: ivs[dim],
1865 rhs: getValueOrCreateConstantIndexOp(
1866 b&: builder, loc, ofr: dimAndTileMapping[dim]));
1867 inputIvsPointLoops.push_back(Elt: divMod.remainder);
1868 inputIvs.push_back(Elt: divMod.quotient);
1869 } else {
1870 inputIvs.push_back(Elt: ivs[dim]);
1871 }
1872 }
1873
1874 // TODO: (lorenzo) simplify the logic a bit. There is `ivs`,
1875 // `inputIvsPointLoops` and `inputIvs`.
1876 assert(inputIvsPointLoops.size() + inputIvs.size() ==
1877 unpackOp.getSourceRank() &&
1878 "expect same number of induction variables equals to input rank");
1879 // Interchange the point loops induction variables based on `inner_dim_pos`.
1880 ArrayRef<int64_t> innerDims = unpackOp.getInnerDimsPos();
1881 SmallVector<int64_t> interchangeVector =
1882 computeInterchangeFromDimPos(dimsPos: innerDims, rank: unpackOp.getDestRank());
1883 SmallVector<Value> interchangedInputIvsPointLoops = inputIvsPointLoops;
1884 interchangedInputIvsPointLoops = interchange<Value>(
1885 elements: interchangedInputIvsPointLoops, interchangeVector, /*offset=*/0);
1886 // Interchange the tiled loops induction variables based on
1887 // `outer_dims_perm`.
1888 ArrayRef<int64_t> outerDims = unpackOp.getOuterDimsPerm();
1889 if (!outerDims.empty())
1890 inputIvs = interchange<Value>(elements: inputIvs, interchangeVector: outerDims, /*offset=*/0);
1891
1892 llvm::append_range(C&: inputIvs, R&: interchangedInputIvsPointLoops);
1893 Value scalar =
1894 memref::LoadOp::create(builder, location: loc, memref: unpackOp.getSource(), indices: inputIvs);
1895 memref::StoreOp::create(builder, location: loc, valueToStore: scalar, memref: unpackOp.getDest(), indices: ivs);
1896 return success();
1897 }
1898
1899 /// Method to return the position of iteration domain tile computed by the
1900 /// tiled operation.
1901 LogicalResult getIterationDomainTileFromOperandTiles(
1902 Operation *op, OpBuilder &b, ArrayRef<unsigned> operandNumbers,
1903 ArrayRef<SmallVector<OpFoldResult>> allOffsets,
1904 ArrayRef<SmallVector<OpFoldResult>> allSizes,
1905 SmallVectorImpl<OpFoldResult> &resultOffsets,
1906 SmallVectorImpl<OpFoldResult> &resultSizes) const {
1907 if (operandNumbers.size() != 1) {
1908 LLVM_DEBUG({ llvm::dbgs() << "unable to handle multiple operands"; });
1909 return failure();
1910 }
1911 auto unPackOp = cast<UnPackOp>(Val: op);
1912 unsigned operandNumber = operandNumbers[0];
1913 ArrayRef<OpFoldResult> offsets(allOffsets[0]);
1914 ArrayRef<OpFoldResult> sizes(allSizes[0]);
1915
1916 // If the operand tile is the dest, then no adjustment is needed.
1917 if (operandNumber == unPackOp.getDestMutable().getOperandNumber()) {
1918 resultOffsets = llvm::to_vector(Range&: offsets);
1919 resultSizes = llvm::to_vector(Range&: sizes);
1920 return success();
1921 }
1922 Location loc = unPackOp.getLoc();
1923
1924 int64_t numTiles = unPackOp.getInnerDimsPos().size();
1925 auto destOffsets = offsets.drop_back(N: numTiles);
1926 auto destSizes = sizes.drop_back(N: numTiles);
1927 // The tiling is applied on interchanged dimensions. We have to undo the
1928 // interchange to map sizes and offsets to the original input.
1929 int64_t outputRank = unPackOp.getDestRank();
1930 ReifiedRankedShapedTypeDims reifiedReturnShapes;
1931 if (failed(Result: reifyResultShapes(b, op: unPackOp, reifiedReturnShapes)))
1932 return failure();
1933 SmallVector<OpFoldResult> outputMixedSizes = reifiedReturnShapes.front();
1934 SmallVector<OpFoldResult> origOffsets(destOffsets);
1935 SmallVector<OpFoldResult> origSizes(destSizes);
1936 applyPermToRange(offsets&: origOffsets, sizes&: origSizes,
1937 permutation: invertPermutationVector(permutation: unPackOp.getOuterDimsPerm()));
1938
1939 DenseMap<int64_t, OpFoldResult> dimAndTileMapping =
1940 unPackOp.getDimAndTileMapping();
1941
1942 for (auto dim : llvm::seq<int64_t>(Begin: 0, End: outputRank)) {
1943 using AV = affine::AffineValueExpr;
1944 affine::AffineBuilder ab(b, loc);
1945 AffineExpr dim0, dim1, sym0;
1946 bindDims(ctx: b.getContext(), exprs&: dim0, exprs&: dim1);
1947 bindSymbols(ctx: b.getContext(), exprs&: sym0);
1948 if (dimAndTileMapping.count(Val: dim)) {
1949 // If the data dimension is tiled, the i-th index is the product of
1950 // offset_i and tile_i, and the i-th size is the product of sizes_i and
1951 // tile_i. The sizes must be clamped to the sizes of the unpack result.
1952 auto avOffset = AV(dim0).bind(v: origOffsets[dim]);
1953 auto avSize = AV(dim0).bind(v: origSizes[dim]);
1954 auto avTileSize = AV(sym0).bind(v: dimAndTileMapping[dim]);
1955 auto avResultSize = AV(dim0).bind(v: outputMixedSizes[dim]);
1956 resultOffsets.push_back(Elt: ab.mul(lhs: avOffset, rhs: avTileSize));
1957 auto avResultOffset = AV(dim1).bind(v: resultOffsets.back());
1958 resultSizes.push_back(Elt: ab.min(vals: {ab.mul(lhs: avSize, rhs: avTileSize),
1959 ab.sub(lhs: avResultSize, rhs: avResultOffset)}));
1960 } else {
1961 resultOffsets.push_back(Elt: origOffsets[dim]);
1962 resultSizes.push_back(Elt: origSizes[dim]);
1963 }
1964 }
1965 return success();
1966 }
1967
1968 FailureOr<TilingResult> getTiledImplementationFromOperandTiles(
1969 Operation *op, OpBuilder &b, ArrayRef<unsigned> operandNumbers,
1970 ArrayRef<SmallVector<OpFoldResult>> allOffsets,
1971 ArrayRef<SmallVector<OpFoldResult>> allSizes) const {
1972 return getTiledImplementationFromOperandTiles(op, b, operandNumbers,
1973 allOffsets, allSizes,
1974 /*innerTileAlignments=*/{});
1975 }
1976
1977 /// Method to return the tiled implementation of linalg.unpack as a consumer.
1978 FailureOr<TilingResult> getTiledImplementationFromOperandTiles(
1979 Operation *op, OpBuilder &b, ArrayRef<unsigned> operandNumbers,
1980 ArrayRef<SmallVector<OpFoldResult>> allOffsets,
1981 ArrayRef<SmallVector<OpFoldResult>> allSizes,
1982 ArrayRef<InnerTileAlignment> innerTileAlignments) const {
1983 if (operandNumbers.size() != 1 || operandNumbers[0] != 0) {
1984 LLVM_DEBUG({ llvm::dbgs() << "unhandled operands for consumer fusion"; });
1985 return failure();
1986 }
1987 auto unPackOp = cast<UnPackOp>(Val: op);
1988 // Pack/unpack transformations on memrefs are currently unsupported.
1989 // The memref forms are mainly used for bufferization and scalar
1990 // lowering. Other uses are not recommended without strong motivation.
1991 // See #225650 for details.
1992 if (!unPackOp.hasPureTensorSemantics())
1993 return failure();
1994
1995 ArrayRef<OpFoldResult> offsets(allOffsets[0]);
1996 ArrayRef<OpFoldResult> sizes(allSizes[0]);
1997
1998 // linalg.unpack op is fusible (as a consumer) only if the inner dims are
1999 // not tiled, i.e. each inner-dim loop tile size equals the inner tile size.
2000 // The caller may assert this per inner dim via InnerTileAlignment::Equal;
2001 // otherwise we require a statically-provable equality.
2002 int64_t numTiles = unPackOp.getInnerDimsPos().size();
2003 ArrayRef<int64_t> innerDimsPos = unPackOp.getInnerDimsPos();
2004 SmallVector<OpFoldResult> mixedTiles = unPackOp.getMixedTiles();
2005 ArrayRef<OpFoldResult> innerSizes = sizes.take_back(N: numTiles);
2006 for (int64_t i = 0; i < numTiles; ++i) {
2007 // `innerTileAlignments` is indexed by the unpack iteration domain (the
2008 // dest dims); the i-th inner tile lives on dest dim `innerDimsPos[i]`.
2009 int64_t destDim = innerDimsPos[i];
2010 bool hintedEqual =
2011 destDim < static_cast<int64_t>(innerTileAlignments.size()) &&
2012 innerTileAlignments[destDim] == InnerTileAlignment::Equal;
2013 // The hint is the source of truth: honor a caller `Equal` assertion. When
2014 // both sizes are also statically known, assert the hint agrees with them
2015 // (a contradicting hint is a caller bug) rather than silently ignoring
2016 // it. Without an `Equal` hint, require a statically-provable equality
2017 // (the inner dim must not be tiled).
2018 if (hintedEqual) {
2019 assert((!getConstantIntValue(mixedTiles[i]) ||
2020 !getConstantIntValue(innerSizes[i]) ||
2021 isEqualConstantIntOrValue(mixedTiles[i], innerSizes[i])) &&
2022 "InnerTileAlignment::Equal contradicts statically known tile "
2023 "sizes");
2024 continue;
2025 }
2026 if (isEqualConstantIntOrValue(ofr1: mixedTiles[i], ofr2: innerSizes[i]))
2027 continue;
2028 return failure();
2029 }
2030
2031 Location loc = unPackOp.getLoc();
2032
2033 // Fetch offset/size for creating the slice of the dest operand of
2034 // unpack op.
2035 SmallVector<OpFoldResult> outputOffsets, outputSizes;
2036 if (failed(Result: getIterationDomainTileFromOperandTiles(
2037 op, b, operandNumbers, allOffsets, allSizes, resultOffsets&: outputOffsets,
2038 resultSizes&: outputSizes)))
2039 return failure();
2040
2041 auto oneAttr = b.getI64IntegerAttr(value: 1);
2042 int64_t outputRank = unPackOp.getDestRank();
2043 SmallVector<OpFoldResult> strides(outputRank, oneAttr);
2044
2045 SmallVector<Value> tiledOperands;
2046 // Create slice of the dest operand.
2047 auto extractDestSlice = tensor::ExtractSliceOp::create(
2048 builder&: b, location: loc, source: unPackOp.getDest(), offsets: outputOffsets, sizes: outputSizes, strides);
2049 tiledOperands.push_back(Elt: extractDestSlice);
2050
2051 strides.append(NumInputs: unPackOp.getSourceRank() - outputRank, Elt: oneAttr);
2052 // Create slice of the source operand.
2053 auto extractSourceSlice = tensor::ExtractSliceOp::create(
2054 builder&: b, location: loc, source: unPackOp.getSource(), offsets, sizes, strides);
2055 tiledOperands.insert(I: tiledOperands.begin(), Elt: extractSourceSlice);
2056 for (auto tile : unPackOp.getInnerTiles())
2057 tiledOperands.push_back(Elt: tile);
2058
2059 // Create tiled unpack op.
2060 UnPackOp tiledUnPackOp =
2061 UnPackOp::create(builder&: b, location: loc, resultTypes: TypeRange{extractDestSlice.getType()},
2062 operands: tiledOperands, properties: unPackOp.getProperties(),
2063 discardableAttributes: unPackOp->getDiscardableAttrDictionary().getValue());
2064
2065 return TilingResult{.tiledOps: {tiledUnPackOp},
2066 .tiledValues: SmallVector<Value>(tiledUnPackOp->getResults()),
2067 .generatedSlices: llvm::to_vector(Range: ArrayRef<Operation *>{
2068 extractSourceSlice, extractDestSlice})};
2069 }
2070};
2071
2072} // namespace
2073
2074template <typename OpType>
2075static void registerOne(MLIRContext *ctx) {
2076 OpType::template attachInterface<LinalgOpTilingInterfaceModel<OpType>>(*ctx);
2077 OpType::template attachInterface<
2078 LinalgOpPartialReductionInterfaceModel<OpType>>(*ctx);
2079}
2080
2081/// Variadic helper function.
2082template <typename... OpTypes>
2083static void registerAll(MLIRContext *ctx) {
2084 (registerOne<OpTypes>(ctx), ...);
2085}
2086
2087#define GET_OP_LIST
2088
2089void mlir::linalg::registerTilingInterfaceExternalModels(
2090 DialectRegistry &registry) {
2091 registry.addExtension(extensionFn: +[](MLIRContext *ctx, linalg::LinalgDialect *dialect) {
2092 registerOne<linalg::GenericOp>(ctx);
2093 linalg::PackOp::attachInterface<PackOpTiling>(context&: *ctx);
2094 linalg::UnPackOp::attachInterface<UnPackOpTiling>(context&: *ctx);
2095 registerAll<
2096#include "mlir/Dialect/Linalg/IR/LinalgStructuredOps.cpp.inc"
2097 >(ctx);
2098 });
2099}
2100
2101void mlir::linalg::registerTilingInterfaceExternalModelsForPackUnPackOps(
2102 DialectRegistry &registry) {
2103 registry.addExtension(extensionFn: +[](MLIRContext *ctx, LinalgDialect *dialect) {
2104 linalg::PackOp::attachInterface<PackOpTiling>(context&: *ctx);
2105 linalg::UnPackOp::attachInterface<UnPackOpTiling>(context&: *ctx);
2106 });
2107}
2108