1//===- Transforms.cpp - Linalg transformations as patterns ----------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file implements logic and helpers to expose Linalg transforms as rewrite
10// patterns.
11//
12//===----------------------------------------------------------------------===//
13
14#include "mlir/Dialect/Linalg/Transforms/Transforms.h"
15#include "mlir/Dialect/Affine/IR/AffineOps.h"
16#include "mlir/Dialect/Arith/IR/Arith.h"
17#include "mlir/Dialect/Func/IR/FuncOps.h"
18#include "mlir/Dialect/Linalg/IR/Linalg.h"
19#include "mlir/Dialect/Linalg/Utils/Utils.h"
20#include "mlir/Dialect/SCF/Transforms/Transforms.h"
21#include "mlir/Dialect/Tensor/IR/Tensor.h"
22#include "mlir/Dialect/Tensor/IR/TensorTilingInterfaceImpl.h"
23#include "mlir/Dialect/Tensor/Utils/Utils.h"
24#include "mlir/Dialect/Utils/IndexingUtils.h"
25#include "mlir/Dialect/Utils/StaticValueUtils.h"
26#include "mlir/Dialect/Utils/StructuredOpsUtils.h"
27#include "mlir/Dialect/Vector/IR/VectorOps.h"
28#include "mlir/IR/AffineExpr.h"
29#include "mlir/IR/BuiltinTypeInterfaces.h"
30#include "mlir/IR/BuiltinTypes.h"
31#include "mlir/Support/LLVM.h"
32#include "llvm/ADT/SmallVectorExtras.h"
33#include "llvm/ADT/TypeSwitch.h"
34#include "llvm/Support/Debug.h"
35#include "llvm/Support/DebugLog.h"
36#include "llvm/Support/InterleavedRange.h"
37#include "llvm/Support/raw_ostream.h"
38#include <type_traits>
39#include <utility>
40
41#define DEBUG_TYPE "linalg-transforms"
42
43using namespace mlir;
44using namespace mlir::linalg;
45
46//===----------------------------------------------------------------------===//
47// Transformations exposed as functional-style API calls.
48//===----------------------------------------------------------------------===//
49
50//===----------------------------------------------------------------------===//
51// peelLoop transformation.
52//===----------------------------------------------------------------------===//
53
54/// Try to peel and canonicalize loop `op` and return the new result.
55/// Also applies affine_min/max bounds simplification on the fly where relevant.
56// TODO: Add support for scf.parallel and affine.for loops.
57SmallVector<Value> mlir::linalg::peelLoop(RewriterBase &rewriter,
58 Operation *op) {
59 return llvm::TypeSwitch<Operation *, SmallVector<Value, 4>>(op)
60 .Case(caseFn: [&](scf::ForOp forOp) {
61 scf::ForOp partialIteration;
62 if (succeeded(Result: scf::peelForLoopAndSimplifyBounds(rewriter, forOp,
63 partialIteration)))
64 return partialIteration->getResults();
65 assert(!partialIteration && "expected that loop was not peeled");
66 return forOp->getResults();
67 })
68 .Default(defaultFn: [&](Operation *op) { return op->getResults(); });
69}
70
71/// Peel 'loops' and applies affine_min/max bounds simplification on the fly
72/// where relevant.
73void mlir::linalg::peelLoops(RewriterBase &rewriter,
74 ArrayRef<scf::ForOp> loops) {
75 for (auto loopOp : loops)
76 peelLoop(rewriter, op: loopOp);
77}
78
79//===----------------------------------------------------------------------===//
80// pack transformation.
81//===----------------------------------------------------------------------===//
82
83#ifndef NDEBUG
84/// Return true if `map` has 0 or 1 result function of AffineDimExpr(dim).
85static bool hasAtMostOneResultFunctionOfDim(AffineMap map, int64_t dim) {
86 bool found = false;
87 for (AffineExpr e : map.getResults()) {
88 if (!e.isFunctionOfDim(dim))
89 continue;
90 if (found)
91 return false;
92 found = true;
93 }
94 return true;
95}
96#endif // NDEBUG
97
98static std::string stringifyReassocIndices(ReassociationIndicesRef ri) {
99 return llvm::interleaved(R: ri, Separator: ", ", /*Prefix=*/"|", /*Suffix=*/"");
100}
101
102/// Return the index of the first result of `map` that is a function of
103/// AffineDimExpr(dim), std::nullopt otherwise.
104static std::optional<int64_t> getFirstResultIndexFunctionOf(AffineMap map,
105 int64_t dim) {
106 for (int64_t i = 0, e = map.getNumResults(); i < e; ++i) {
107 AffineExpr expr = map.getResult(idx: i);
108 if (!expr.isFunctionOfDim(position: dim))
109 continue;
110 return i;
111 }
112 return std::nullopt;
113}
114
115/// Perform one step of packing of a LinalgOp's metadata along `dim` into the
116/// `newDim` at `iteratorTypes.size()` by:
117/// 1. Appending `iteratorTypes[newDim]`, equal to `iteratorTypes[dim]`.
118/// 2. Appending a `newDim` to the domain of every indexing map.
119/// 3. For each operand (i.e. for each map in `indexingMaps`), perform packing
120/// by potentially adding a `newDim` result to `map`.
121/// The preserved invariant is that `iteratorTypes.size()` is always equal to
122/// `map.getNumDims()` for every map in `indexingMaps`.
123///
124/// Update `indexingMaps` and `iteratorTypes` inplace as one step of the update.
125/// Return a vector that records the optional packing for each operand.
126/// Return failure if the packed indexing cannot be represented with a LinalgOp.
127///
128/// Further details:
129/// ================
130/// The current implementation of packing (i.e. data tiling) consists of
131/// rewriting a linearized strip-mined form into a higher-dimensional access.
132/// e.g. consider an access `A[I][f(j, k, l)]` and packing by 4; we rewrite
133/// `I` into `4 * i + ii`, where `0 <= ii < 4`.
134/// The access is further rewritten as `A[i][f(j, k, l)][ii]`.
135///
136/// This rewrite into higher dimensional access is not possible for general
137/// AffineExpr in Linalg atm, it is restricted to an AffineDimExpr:
138/// e.g. consider an access `A[I + J][f(j, k, l)]` and packing by 4; we
139/// rewrite `I + J` into `4 * i + ii + J`, where `0 <= ii < 4`.
140/// The rewrite of the access would be a form not representable in Linalg:
141/// `A[i + (ii + J) / 4][f(j, k, l)][(ii + J) % 4]`.
142/// Note however that as `J` and `ii` iterate, the accesses do not have a
143/// particular alignment, so packing does not achieve alignment in this case
144///
145/// In the future, we may want to consider a mixed-form that allows some
146/// alignment in the presence of multiple accesses:
147/// `A[I][f(j, k, l)]` and `B[I + J][f(j, k, l)]`
148/// And would rewrite accesses as:
149/// `A[i][f(j, k, l)][ii]` and `B[4 * i + ii + J][f(j, k, l)]`
150static FailureOr<SmallVector<std::optional<int64_t>>>
151packLinalgMetadataOnce(SmallVectorImpl<AffineMap> &indexingMaps,
152 SmallVectorImpl<utils::IteratorType> &iteratorTypes,
153 int64_t dim) {
154 int64_t newDim = iteratorTypes.size();
155 iteratorTypes.push_back(Elt: iteratorTypes[dim]);
156
157 SmallVector<std::optional<int64_t>> packedDimPerIndexingMap(
158 indexingMaps.size(), std::nullopt);
159 SmallVector<AffineMap> newMaps;
160 for (int64_t operandIdx = 0, e = indexingMaps.size(); operandIdx < e;
161 ++operandIdx) {
162 AffineMap map = indexingMaps[operandIdx];
163
164 // Add the `newDim` to map whatever the case.
165 assert(map.getNumDims() == newDim && "num dims invariant violation");
166 map = map.shiftDims(shift: 1, offset: newDim);
167
168 // Get the at-most-1 index of the result that is a function of `dim`.
169 // If we can find one, we insert `AffineDimExpr(newDim)` to the map, which
170 // logically chunks dimension `dim` into `K * dim + newDim`, where the
171 // packing factor `K` is specified separately.
172 assert(hasAtMostOneResultFunctionOfDim(map, dim) &&
173 "num results invariant violation");
174 auto maybeOperandDimensionToPack = getFirstResultIndexFunctionOf(map, dim);
175 if (!maybeOperandDimensionToPack.has_value()) {
176 newMaps.push_back(Elt: map);
177 continue;
178 }
179
180 // We can only pack AffineDimExpr atm.
181 if (!isa<AffineDimExpr>(Val: map.getResult(idx: maybeOperandDimensionToPack.value())))
182 return failure();
183
184 // Add `newDim` to the results of the map.
185 map = map.insertResult(expr: Builder(map.getContext()).getAffineDimExpr(position: newDim),
186 pos: map.getNumResults());
187 newMaps.push_back(Elt: map);
188
189 // Record the that `operandIdx` is packed.
190 packedDimPerIndexingMap[operandIdx] = maybeOperandDimensionToPack;
191 }
192 indexingMaps = newMaps;
193
194 return packedDimPerIndexingMap;
195}
196
197namespace {
198
199/// Helper struct to encode packing along one dimension of a LinalgOp.
200struct PackedOperandsDim {
201 OpFoldResult packedSize;
202 SmallVector<std::optional<int64_t>> packedDimForEachOperand;
203};
204
205/// Helper struct to encode packing along all dimensions of a LinalgOp.
206struct PackedOperandsDimList {
207 void pushBack(PackedOperandsDim &&packedOperandsDims) {
208 spec.emplace_back(Args&: packedOperandsDims);
209 }
210 /// Return all the dims that have been packed for operand @ `operandPos`.
211 SmallVector<int64_t> extractPackedDimsForOperand(int64_t operandPos);
212 /// Return all the pack sizes by which an operand @ `operandPos` is packed.
213 SmallVector<OpFoldResult> extractPackSizesForOperand(int64_t operandPos);
214
215private:
216 SmallVector<PackedOperandsDim> spec;
217};
218
219} // namespace
220
221/// Rewrite index operations in a packed Linalg op to preserve their values in
222/// the original iteration space. Packing loop dimension `d` by `tileSize`
223/// splits its index into an outer and inner index, so the original index is
224/// `outer * tileSize + inner`.
225static void
226remapPackedIndexOps(RewriterBase &rewriter, LinalgOp packedLinalgOp,
227 ArrayRef<OpFoldResult> packedSizes,
228 ArrayRef<std::optional<int64_t>> packedLoopToInnerLoop) {
229 if (!packedLinalgOp.hasIndexSemantics())
230 return;
231
232 SmallVector<IndexOp> indexOps =
233 llvm::to_vector(Range: packedLinalgOp.getBlock()->getOps<IndexOp>());
234 for (IndexOp indexOp : indexOps) {
235 unsigned dim = indexOp.getDim();
236 assert(dim < packedLoopToInnerLoop.size() && "invalid linalg.index dim");
237 std::optional<int64_t> innerDim = packedLoopToInnerLoop[dim];
238 if (!innerDim)
239 continue;
240
241 OpBuilder::InsertionGuard guard(rewriter);
242 rewriter.setInsertionPoint(indexOp);
243 Value outerIndex =
244 IndexOp::create(builder&: rewriter, location: indexOp.getLoc(), dim).getResult();
245 Value innerIndex =
246 IndexOp::create(builder&: rewriter, location: indexOp.getLoc(), dim: *innerDim).getResult();
247
248 AffineExpr outer, inner, tileSize;
249 bindDims(ctx: rewriter.getContext(), exprs&: outer, exprs&: inner);
250 bindSymbols(ctx: rewriter.getContext(), exprs&: tileSize);
251 OpFoldResult originalIndex = affine::makeComposedFoldedAffineApply(
252 b&: rewriter, loc: indexOp.getLoc(), expr: outer * tileSize + inner,
253 operands: {outerIndex, innerIndex, packedSizes[dim]});
254 rewriter.replaceOp(op: indexOp, newValues: getValueOrCreateConstantIndexOp(
255 b&: rewriter, loc: indexOp.getLoc(), ofr: originalIndex));
256 }
257}
258
259FailureOr<LowerPackResult> linalg::lowerPack(RewriterBase &rewriter,
260 linalg::PackOp packOp,
261 bool lowerPadLikeWithInsertSlice) {
262 // Pack/unpack memref transformations are unsupported. The memref forms
263 // are mainly for bufferization and scalar lowering. Other uses are not
264 // recommended, see #225650 for details.
265 if (!packOp.hasPureTensorSemantics())
266 return failure();
267
268 auto packedTensorType =
269 cast<RankedTensorType>(Val: packOp->getResultTypes().front());
270
271 Location loc = packOp->getLoc();
272 OpBuilder::InsertionGuard g(rewriter);
273 rewriter.setInsertionPoint(packOp);
274
275 // 2. Compute the permutation vector to shuffle packed shape into the shape
276 // before any outer or inner permutations have been applied.
277 PackingMetadata packingMetadata;
278 SmallVector<int64_t> packedToStripMinedShapePerm =
279 getPackInverseDestPerm(packOp, metadata&: packingMetadata);
280
281 // 3. Compute the stripMinedShape: this is the packed shape before any outer
282 // or inner permutations have been applied.
283 SmallVector<int64_t> stripMinedShape(packedTensorType.getShape());
284 applyPermutationToVector(inVec&: stripMinedShape, permutation: packedToStripMinedShapePerm);
285
286 // Also compute the mixed (static+dynamic) strip-mined sizes for the
287 // expand_shape output. This is needed to support dynamic inner tile sizes,
288 // since the shapes cannot be inferred automatically when multiple dynamic
289 // dims appear in a single reassociation group during ExpandShapeOp
290 // construction.
291 SmallVector<OpFoldResult> stripMinedMixedSizes =
292 tensor::getMixedSizes(builder&: rewriter, loc, value: packOp.getDest());
293 applyPermutationToVector(inVec&: stripMinedMixedSizes, permutation: packedToStripMinedShapePerm);
294
295 // 4. Pad the source of packOp to a shape we can expand into stripMinedShape.
296 SmallVector<OpFoldResult> lows(packOp.getSourceRank(),
297 rewriter.getIndexAttr(value: 0));
298 SmallVector<OpFoldResult> highs(packOp.getSourceRank(),
299 rewriter.getIndexAttr(value: 0));
300 for (auto [pos, innerSize] :
301 llvm::zip_equal(t: packOp.getInnerDimsPos(), u: packOp.getMixedTiles())) {
302 int outerPos =
303 packedToStripMinedShapePerm[packingMetadata.outerPositions[pos]];
304 OpFoldResult origSize =
305 tensor::getMixedSize(builder&: rewriter, loc, value: packOp.getSource(), dim: pos);
306 OpFoldResult outerSize =
307 tensor::getMixedSize(builder&: rewriter, loc, value: packOp.getDest(), dim: outerPos);
308 AffineExpr s0, d0, d1;
309 bindDims(ctx: rewriter.getContext(), exprs&: d0, exprs&: d1);
310 bindSymbols(ctx: rewriter.getContext(), exprs&: s0);
311 auto map = AffineMap::get(/*dimCount=*/2, /*symbolCount=*/1, result: d0 * s0 - d1);
312 highs[pos] = affine::makeComposedFoldedAffineApply(
313 b&: rewriter, loc, map, operands: {outerSize, origSize, innerSize});
314 }
315 RankedTensorType collapsed = tensor::CollapseShapeOp::inferCollapsedType(
316 type: RankedTensorType::Builder(packedTensorType).setShape(stripMinedShape),
317 reassociation: packingMetadata.reassociations);
318 Value paddingValue = packOp.getPaddingValue();
319 if (!paddingValue) {
320 paddingValue = arith::ConstantOp::create(
321 builder&: rewriter, location: loc, value: rewriter.getZeroAttr(type: getElementTypeOrSelf(type: collapsed)));
322 }
323 auto padOp =
324 tensor::PadOp::create(builder&: rewriter, location: loc, resultType: collapsed, source: packOp.getSource(), low: lows,
325 high: highs, constantPadValue: paddingValue, /*nofold=*/false);
326
327 LDBG() << "insertPositions: "
328 << llvm::interleaved(R: packingMetadata.insertPositions);
329 LDBG() << "outerPositions: "
330 << llvm::interleaved(R: packingMetadata.outerPositions);
331 LDBG() << "packedShape: " << llvm::interleaved(R: packedTensorType.getShape());
332 LDBG() << "packedToStripMinedShapePerm: "
333 << llvm::interleaved(R: packedToStripMinedShapePerm);
334 LDBG() << "reassociations: "
335 << llvm::interleaved(R: llvm::map_range(C&: packingMetadata.reassociations,
336 F: stringifyReassocIndices));
337 LDBG() << "stripMinedShape: " << llvm::interleaved(R: stripMinedShape);
338 LDBG() << "collapsed type: " << collapsed;
339
340 if (lowerPadLikeWithInsertSlice && packOp.isLikePad()) {
341 // Pack ops which operate as simple pads may not produce legal
342 // tensor.insert_slice operations when the packed type does not rank reduce
343 // to the padded type.
344 SliceVerificationResult rankReduces =
345 isRankReducedType(originalType: packedTensorType, candidateReducedType: padOp.getResultType());
346
347 if (rankReduces == SliceVerificationResult::Success) {
348 // This pack is just a plain pad.
349 // Just insert the pad in the higher ranked tensor.
350 // Offsets.
351 SmallVector<OpFoldResult> zeros(packOp.getDestRank(),
352 rewriter.getIndexAttr(value: 0));
353 // Strides.
354 SmallVector<OpFoldResult> ones(packOp.getDestRank(),
355 rewriter.getIndexAttr(value: 1));
356 SmallVector<OpFoldResult> sizes =
357 tensor::getMixedSizes(builder&: rewriter, loc, value: packOp.getDest());
358
359 auto insertSliceOp = tensor::InsertSliceOp::create(
360 builder&: rewriter, location: loc, /*source=*/padOp, /*dest=*/packOp.getDest(),
361 /*offsets=*/zeros, sizes, /*strides=*/ones);
362
363 LDBG() << "insert_slice op: " << insertSliceOp;
364
365 rewriter.replaceOp(op: packOp, newValues: insertSliceOp->getResults());
366
367 return LowerPackResult{.padOp: padOp, /*reshapeOp=*/.expandShapeOp: nullptr,
368 /*transposeOp=*/nullptr};
369 }
370 }
371
372 // 5. Expand from the padded result to the stripMinedShape.
373 auto expandShapeResultType =
374 RankedTensorType::Builder(packedTensorType).setShape(stripMinedShape);
375 auto reshapeOp = tensor::ExpandShapeOp::create(
376 builder&: rewriter, location: loc, resultType: expandShapeResultType, src: padOp.getResult(),
377 reassociation: packingMetadata.reassociations, outputShape: stripMinedMixedSizes);
378
379 // 6. Transpose stripMinedShape to packedShape.
380 SmallVector<int64_t> transpPerm =
381 invertPermutationVector(permutation: packedToStripMinedShapePerm);
382 auto transposeOp = linalg::TransposeOp::create(
383 builder&: rewriter, location: loc, input: reshapeOp.getResult(), init: packOp.getDest(), permutation: transpPerm);
384
385 LDBG() << "reshape op: " << reshapeOp;
386 LDBG() << "transpPerm: " << llvm::interleaved(R: transpPerm);
387 LDBG() << "transpose op: " << transposeOp;
388
389 // 7. Replace packOp by transposeOp.
390 rewriter.replaceOp(op: packOp, newValues: transposeOp->getResults());
391
392 return LowerPackResult{.padOp: padOp, .expandShapeOp: reshapeOp, .transposeOp: transposeOp};
393}
394
395FailureOr<LowerUnPackOpResult>
396linalg::lowerUnPack(RewriterBase &rewriter, linalg::UnPackOp unPackOp,
397 bool lowerUnpadLikeWithExtractSlice) {
398 // Pack/unpack memref transformations are unsupported. The memref forms
399 // are mainly for bufferization and scalar lowering. Other uses are not
400 // recommended, see #225650 for details.
401 if (!unPackOp.hasPureTensorSemantics())
402 return failure();
403
404 Location loc = unPackOp->getLoc();
405 OpBuilder::InsertionGuard g(rewriter);
406 rewriter.setInsertionPoint(unPackOp);
407
408 auto packedTensorType = cast<RankedTensorType>(Val: unPackOp.getSourceType());
409 int64_t packedRank = packedTensorType.getRank();
410
411 OpFoldResult zero = rewriter.getIndexAttr(value: 0), one = rewriter.getIndexAttr(value: 1);
412 auto destTensorType = cast<RankedTensorType>(Val: unPackOp.getDest().getType());
413 if (lowerUnpadLikeWithExtractSlice && unPackOp.isLikeUnPad()) {
414 // This unpack is just a plain unpad.
415 // Just extract the slice from the higher ranked tensor.
416 ArrayRef<int64_t> destShape = destTensorType.getShape();
417 // The inner dimensions stay the same as the destination tensor, but the
418 // outer ones are additional 1s.
419 SmallVector<OpFoldResult> sizes(packedRank - destShape.size(), one);
420 sizes.append(RHS: tensor::getMixedSizes(builder&: rewriter, loc, value: unPackOp.getDest()));
421
422 auto extractSliceOp = tensor::ExtractSliceOp::create(
423 builder&: rewriter, location: loc, resultType: destTensorType, source: unPackOp.getSource(),
424 offsets: SmallVector<OpFoldResult>(packedRank, zero), sizes,
425 strides: SmallVector<OpFoldResult>(packedRank, one));
426
427 rewriter.replaceOp(op: unPackOp, newValues: extractSliceOp->getResults());
428
429 return LowerUnPackOpResult{/*emptyOp=*/nullptr, /*transposeOp=*/nullptr,
430 /*reshapeOp=*/.collapseShapeOp: nullptr, .extractSliceOp: extractSliceOp,
431 /*copyOp=*/nullptr};
432 }
433
434 // 1. Compute the permutation vector to shuffle packed shape into the shape
435 // before any outer or inner permutations have been applied.
436 PackingMetadata packingMetadata;
437 SmallVector<int64_t> packedToStripMinedShapePerm =
438 getUnPackInverseSrcPerm(unPackOp, metadata&: packingMetadata);
439
440 // 2. Compute the stripMinedShape: this is the packed shape without outer and
441 // inner permutations.
442 SmallVector<int64_t> stripMinedShape(packedTensorType.getShape());
443 applyPermutationToVector(inVec&: stripMinedShape, permutation: packedToStripMinedShapePerm);
444
445 // 3. Transpose packedShape to stripMinedShape.
446 RankedTensorType stripMinedTensorType =
447 RankedTensorType::Builder(packedTensorType).setShape(stripMinedShape);
448 RankedTensorType collapsedType = tensor::CollapseShapeOp::inferCollapsedType(
449 type: stripMinedTensorType, reassociation: packingMetadata.reassociations);
450
451 // Get dynamic dims from input tensor based on packedToStripMinedShapePerm
452 // permutation.
453 SmallVector<OpFoldResult, 4> dims =
454 tensor::getMixedSizes(builder&: rewriter, loc, value: unPackOp.getSource());
455 applyPermutationToVector(inVec&: dims, permutation: packedToStripMinedShapePerm);
456 auto emptyOp = tensor::EmptyOp::create(builder&: rewriter, location: loc, sizes: dims,
457 elementType: stripMinedTensorType.getElementType());
458 auto transposeOp =
459 linalg::TransposeOp::create(builder&: rewriter, location: loc, input: unPackOp.getSource(), init: emptyOp,
460 permutation: packedToStripMinedShapePerm);
461
462 LDBG() << "insertPositions: "
463 << llvm::interleaved(R: packingMetadata.insertPositions);
464 LDBG() << "packedShape: " << llvm::interleaved(R: packedTensorType.getShape());
465 LDBG() << "packedToStripMinedShapePerm: "
466 << llvm::interleaved(R: packedToStripMinedShapePerm);
467 LDBG() << "reassociations: "
468 << llvm::interleaved(R: llvm::map_range(C&: packingMetadata.reassociations,
469 F: stringifyReassocIndices));
470 LDBG() << "stripMinedShape: " << llvm::interleaved(R: stripMinedShape);
471 LDBG() << "collapsed type: " << collapsedType;
472
473 // 4. Collapse from the stripMinedShape to the padded result.
474 auto reshapeOp = tensor::CollapseShapeOp::create(
475 builder&: rewriter, location: loc, resultType: collapsedType, src: transposeOp->getResult(idx: 0),
476 reassociation: packingMetadata.reassociations);
477
478 // 5. ExtractSlice.
479 int64_t destRank = destTensorType.getRank();
480 auto extractSliceOp = tensor::ExtractSliceOp::create(
481 builder&: rewriter, location: loc, resultType: destTensorType, source: reshapeOp->getResult(idx: 0),
482 offsets: SmallVector<OpFoldResult>(destRank, zero),
483 sizes: tensor::getMixedSizes(builder&: rewriter, loc, value: unPackOp.getDest()),
484 strides: SmallVector<OpFoldResult>(destRank, one));
485
486 // 6. Inject a copy to preserve DPS.
487 auto copyOp = linalg::CopyOp::create(
488 builder&: rewriter, location: loc, inputs: extractSliceOp->getResult(idx: 0), outputs: unPackOp.getDest());
489
490 // 7. Replace unPackOp by copyOp.
491 rewriter.replaceOp(op: unPackOp, newValues: copyOp->getResults());
492
493 return LowerUnPackOpResult{.emptyOp: emptyOp, .transposeOp: transposeOp, .collapseShapeOp: reshapeOp, .extractSliceOp: extractSliceOp,
494 .copyOp: copyOp};
495}
496
497SmallVector<int64_t>
498PackedOperandsDimList::extractPackedDimsForOperand(int64_t operandPos) {
499 SmallVector<int64_t> res;
500 for (auto &i : spec) {
501 if (!i.packedDimForEachOperand[operandPos].has_value())
502 continue;
503 res.push_back(Elt: i.packedDimForEachOperand[operandPos].value());
504 }
505 return res;
506}
507
508SmallVector<OpFoldResult>
509PackedOperandsDimList::extractPackSizesForOperand(int64_t operandPos) {
510 SmallVector<OpFoldResult> res;
511 for (auto &i : spec) {
512 if (!i.packedDimForEachOperand[operandPos].has_value())
513 continue;
514 res.push_back(Elt: i.packedSize);
515 }
516 return res;
517}
518
519/// Implement packing of a single LinalgOp by performing packing by
520/// `packedSizes`. There must be one packedSizes entry per `linalgOp` iterator.
521/// Return the packed Linalg op on success, failure otherwise.
522FailureOr<PackResult> linalg::pack(RewriterBase &rewriter,
523 linalg::LinalgOp linalgOp,
524 ArrayRef<OpFoldResult> packedSizes) {
525 if (packedSizes.size() != linalgOp.getNumLoops()) {
526 return rewriter.notifyMatchFailure(arg&: linalgOp,
527 msg: "incorrect number of pack sizes");
528 }
529 if (!linalgOp.hasPureTensorSemantics()) {
530 return rewriter.notifyMatchFailure(
531 arg&: linalgOp, msg: "expects LinalgOp with pure tensor semantics");
532 }
533
534 Location loc = linalgOp->getLoc();
535 SmallVector<AffineMap> indexingMaps = linalgOp.getIndexingMapsArray();
536 SmallVector<utils::IteratorType> iteratorTypes =
537 linalgOp.getIteratorTypesArray();
538 LDBG() << "Start packing: " << linalgOp;
539 LDBG() << "maps: " << llvm::interleaved(R: indexingMaps);
540 LDBG() << "iterators: " << llvm::interleaved(R: iteratorTypes);
541
542 SmallVector<linalg::PackOp> packOps;
543 SmallVector<linalg::UnPackOp> unPackOps;
544 // Step 1. Pack each dim of the LinalgOp metadata by packedSizes[i].
545 PackedOperandsDimList listOfPackedOperandsDim;
546 SmallVector<std::optional<int64_t>> packedLoopToInnerLoop(packedSizes.size());
547 for (int64_t i = 0, e = packedSizes.size(); i < e; ++i) {
548 std::optional<int64_t> maybeConstant = getConstantIntValue(ofr: packedSizes[i]);
549 // Skip tile sizes explicitly set to 0.
550 if (maybeConstant.has_value() && maybeConstant.value() == 0)
551 continue;
552
553 PackedOperandsDim packedOperandsDims;
554 packedOperandsDims.packedSize = packedSizes[i];
555 FailureOr<SmallVector<std::optional<int64_t>>>
556 maybePackedDimForEachOperand =
557 packLinalgMetadataOnce(indexingMaps, iteratorTypes, dim: i);
558 if (failed(Result: maybePackedDimForEachOperand))
559 return failure();
560 packedLoopToInnerLoop[i] = iteratorTypes.size() - 1;
561 packedOperandsDims.packedDimForEachOperand = *maybePackedDimForEachOperand;
562
563 LDBG() << "++++ After pack size #" << i << ": " << packedSizes[i];
564 LDBG() << "maps: " << llvm::interleaved(R: indexingMaps);
565 LDBG() << "iterators: " << llvm::interleaved(R: iteratorTypes);
566 LDBG() << "packedDimForEachOperand: "
567 << llvm::interleaved(R: packedOperandsDims.packedDimForEachOperand);
568
569 listOfPackedOperandsDim.pushBack(packedOperandsDims: std::move(packedOperandsDims));
570 }
571
572 // Step 2. Propagate packing to all LinalgOp operands.
573 SmallVector<Value> inputsAndInits, results;
574 SmallVector<OpOperand *> initOperands =
575 llvm::to_vector(Range: llvm::make_pointer_range(Range: linalgOp.getDpsInitsMutable()));
576 SmallVector<OpOperand *> inputOperands = linalgOp.getDpsInputOperands();
577 for (const auto &operandsList : {inputOperands, initOperands}) {
578 for (OpOperand *opOperand : operandsList) {
579 int64_t pos = opOperand->getOperandNumber();
580 Value operand = opOperand->get();
581 SmallVector<int64_t> innerPos =
582 listOfPackedOperandsDim.extractPackedDimsForOperand(operandPos: pos);
583 SmallVector<OpFoldResult> innerPackSizes =
584 listOfPackedOperandsDim.extractPackSizesForOperand(operandPos: pos);
585 LDBG() << "operand: " << operand;
586 LDBG() << "innerPos: " << llvm::interleaved(R: innerPos);
587 LDBG() << "innerPackSizes: " << llvm::interleaved(R: innerPackSizes);
588 if (innerPackSizes.empty()) {
589 inputsAndInits.push_back(Elt: operand);
590 continue;
591 }
592 Value dest = linalg::PackOp::createDestinationTensor(
593 b&: rewriter, loc, source: operand, innerTileSizes: innerPackSizes, innerDimsPos: innerPos,
594 /*outerDimsPerm=*/{});
595 ShapedType operandType = cast<ShapedType>(Val: operand.getType());
596 bool areConstantTiles =
597 llvm::all_of(Range&: innerPackSizes, P: [](OpFoldResult tile) {
598 return getConstantIntValue(ofr: tile).has_value();
599 });
600 if (areConstantTiles && operandType.hasStaticShape() &&
601 !linalg::PackOp::requirePaddingValue(
602 inputShape: operandType.getShape(), innerDimsPos: innerPos,
603 outputShape: cast<ShapedType>(Val: dest.getType()).getShape(), outerDimsPerm: {},
604 innerTiles: innerPackSizes)) {
605 packOps.push_back(Elt: linalg::PackOp::create(builder&: rewriter, location: loc, source: operand, dest,
606 innerDimsPos: innerPos, innerTiles: innerPackSizes));
607 } else {
608 // TODO: value of the padding attribute should be determined by
609 // consumers.
610 auto zeroAttr =
611 rewriter.getZeroAttr(type: getElementTypeOrSelf(type: dest.getType()));
612 Value zero = arith::ConstantOp::create(builder&: rewriter, location: loc, value: zeroAttr);
613 packOps.push_back(Elt: linalg::PackOp::create(
614 builder&: rewriter, location: loc, source: operand, dest, innerDimsPos: innerPos, innerTiles: innerPackSizes, paddingValue: zero));
615 }
616 inputsAndInits.push_back(Elt: packOps.back().getResult());
617 }
618 }
619
620 // Step 3. Build the packed op, use the type of `inits` as result types.
621 ValueRange inputs =
622 ValueRange{inputsAndInits}.take_front(n: linalgOp.getNumDpsInputs());
623 ValueRange inits =
624 ValueRange{inputsAndInits}.take_back(n: linalgOp.getNumDpsInits());
625 auto packedLinalgOp =
626 linalg::GenericOp::create(builder&: rewriter, location: linalgOp.getLoc(), resultTensorTypes: inits.getTypes(),
627 inputs, outputs: inits, indexingMaps, iteratorTypes);
628 packedLinalgOp.getRegion().takeBody(other&: linalgOp->getRegion(index: 0));
629 remapPackedIndexOps(rewriter, packedLinalgOp, packedSizes,
630 packedLoopToInnerLoop);
631
632 // Step 4. Propagate packing to all the op results.
633 for (OpResult result : packedLinalgOp->getResults()) {
634 int64_t resultNum = result.getResultNumber();
635 linalg::PackOp maybePackedInit =
636 inits[resultNum].getDefiningOp<linalg::PackOp>();
637 if (!maybePackedInit) {
638 results.push_back(Elt: result);
639 continue;
640 }
641 // Build the symmetrical UnPackOp to the existing PackOp.
642 unPackOps.push_back(Elt: linalg::UnPackOp::create(
643 builder&: rewriter, location: packedLinalgOp->getLoc(), source: result, dest: maybePackedInit.getSource(),
644 innerDimsPos: maybePackedInit.getInnerDimsPos(), innerTiles: maybePackedInit.getMixedTiles()));
645 results.push_back(Elt: unPackOps.back().getResult());
646 }
647
648 // Step 5. Replace `linalgOp`.
649 rewriter.replaceOp(op: linalgOp, newValues: results);
650
651 // Return packedLinalgOp.
652 return PackResult{.packOps: packOps,
653 .packedLinalgOp: cast<linalg::LinalgOp>(Val: packedLinalgOp.getOperation()),
654 .unPackOps: unPackOps};
655}
656
657//===----------------------------------------------------------------------===//
658// packTranspose transformation.
659//===----------------------------------------------------------------------===//
660
661/// Return a copy of `tensorType` after permutation by `permutationVector`.
662// Note: Should be a new method in of MemRef/RankedTensor/VectorType::Builder
663// but this would introduce a dependence on Dialect in IR.
664// TODO: Restructure.
665static RankedTensorType permuteShape(RankedTensorType tensorType,
666 ArrayRef<int64_t> permutationVector) {
667 SmallVector<int64_t> shape(tensorType.getShape());
668 applyPermutationToVector(inVec&: shape, permutation: permutationVector);
669 return RankedTensorType::Builder(tensorType).setShape(shape);
670}
671
672/// Return a new GenericOp obtained by transposing opOperand by the permutation
673/// vector:
674/// - the corresponding indexing map is transposed by `permutation`
675/// - the corresponding operand value is replaced by `transposedValue`
676/// `linalgOp` is replaced by the return op in the process.
677/// Asserts that `transposedValue` is of the proper transposed ShapedType.
678static LinalgOp transposeOneLinalgOperandAndReplace(
679 RewriterBase &rewriter, LinalgOp linalgOp, OpOperand &opOperand,
680 ArrayRef<int64_t> permutation, Value transposedValue) {
681 // Sanity check the operand.
682 assert(linalgOp == opOperand.getOwner() && "linalg op must own the operand");
683
684 // Sanity check of the expected transposed tensor type.
685 auto tensorType = permuteShape(
686 tensorType: cast<RankedTensorType>(Val: opOperand.get().getType()), permutationVector: permutation);
687 (void)tensorType;
688 assert(tensorType == transposedValue.getType() &&
689 "expected tensor type mismatch");
690
691 // Compute the transposed indexing map.
692 // Sigh unsigned pollution.
693 SmallVector<unsigned> tmpTransposition =
694 llvm::map_to_vector(C&: permutation, F: [](int64_t i) -> unsigned { return i; });
695 AffineMap permutationMap =
696 AffineMap::getPermutationMap(permutation: tmpTransposition, context: rewriter.getContext());
697 AffineMap transposedMap =
698 permutationMap.compose(map: linalgOp.getMatchingIndexingMap(opOperand: &opOperand));
699
700 // Set the transposed indexing map in the proper position.
701 SmallVector<AffineMap> indexingMaps = linalgOp.getIndexingMapsArray();
702 indexingMaps[linalgOp.getIndexingMapIndex(opOperand: &opOperand)] = transposedMap;
703 // Set the transposedValue in the proper operand position.
704 SmallVector<Value> operands = linalgOp->getOperands();
705 operands[opOperand.getOperandNumber()] = transposedValue;
706
707 ValueRange operandsRef(operands);
708 auto transposedGenericOp = linalg::GenericOp::create(
709 builder&: rewriter,
710 /*location=*/linalgOp->getLoc(),
711 /*resultTensorTypes=*/
712 operandsRef.drop_front(n: linalgOp.getNumDpsInputs()).getTypes(),
713 /*inputs=*/operandsRef.take_front(n: linalgOp.getNumDpsInputs()),
714 /*outputs=*/operandsRef.drop_front(n: linalgOp.getNumDpsInputs()),
715 /*indexingMaps=*/indexingMaps,
716 /*iteratorTypes=*/linalgOp.getIteratorTypesArray());
717 transposedGenericOp.getRegion().takeBody(other&: linalgOp->getRegion(index: 0));
718 rewriter.replaceOp(op: linalgOp, newValues: transposedGenericOp->getResults());
719
720 return cast<linalg::LinalgOp>(Val: transposedGenericOp.getOperation());
721}
722
723FailureOr<PackTransposeResult>
724linalg::packTranspose(RewriterBase &rewriter, linalg::PackOp packOp,
725 linalg::LinalgOp linalgOp, linalg::UnPackOp maybeUnPackOp,
726 ArrayRef<int64_t> outerPerm,
727 ArrayRef<int64_t> innerPerm) {
728 Location loc = linalgOp.getLoc();
729
730 // Step 1. Transpose packOp.
731 rewriter.setInsertionPoint(packOp);
732 linalg::PackOp transposedPackOp =
733 packOp.createTransposedClone(b&: rewriter, loc, innerPermutation: innerPerm, outerPermutation: outerPerm);
734
735 if (packOp.hasPureBufferSemantics() || !packOp.getResult().hasOneUse())
736 return rewriter.notifyMatchFailure(arg&: linalgOp, msg: "expect single pack use");
737
738 OpOperand &packUse = *packOp->getUses().begin();
739 if (packUse.getOwner() != linalgOp) {
740 return rewriter.notifyMatchFailure(
741 arg&: linalgOp, msg: "not a single use by the LinalgOp target");
742 }
743 if (maybeUnPackOp &&
744 (!linalgOp.isDpsInit(opOperand: &packUse) ||
745 maybeUnPackOp.getSource() != linalgOp.getTiedOpResult(opOperand: &packUse))) {
746 return rewriter.notifyMatchFailure(arg&: linalgOp,
747 msg: "not produced by the LinalgOp target");
748 }
749
750 // Step 2. Transpose linalgOp.
751 // transposedPackOp.getOuterDimsPerm() may be empty, in which case it is the
752 // identity. Don't rely on it.
753 int64_t numLeadingDims = packOp.getSourceRank();
754 int64_t numTrailingDims = packOp.getInnerDimsPos().size();
755 // Step 2.a. Compute the permutation on the whole operand.
756 // Leading part just reuse the outerPerm.
757 SmallVector<int64_t> permutation(outerPerm);
758 if (permutation.empty())
759 llvm::append_range(C&: permutation, R: llvm::seq<int64_t>(Begin: 0, End: numLeadingDims));
760 // Trailing part needs to reindex positions by `numLeadingDims`.
761 if (innerPerm.empty()) {
762 llvm::append_range(
763 C&: permutation,
764 R: llvm::seq<int64_t>(Begin: numLeadingDims, End: numLeadingDims + numTrailingDims));
765 } else {
766 llvm::append_range(C&: permutation,
767 R: llvm::map_range(C&: innerPerm, F: [&](int64_t pos) {
768 return numLeadingDims + pos;
769 }));
770 }
771 if (!isPermutationVector(interchange: permutation))
772 return rewriter.notifyMatchFailure(arg&: linalgOp, msg: "invalid permutation");
773
774 // Step 2.b. Save the transposedPackUse operand number in case we need to
775 // get the tied OpResult after `linalgOp` has been replaced.
776 int64_t packUseOperandNumber = packUse.getOperandNumber();
777 // Step 2.c. Actually perform the transposition.
778 rewriter.setInsertionPoint(linalgOp);
779 linalg::LinalgOp transposedLinalgOp = transposeOneLinalgOperandAndReplace(
780 rewriter, linalgOp, opOperand&: packUse, permutation, transposedValue: transposedPackOp.getResult());
781
782 // Step 3. Maybe transpose unPackOp.
783 linalg::UnPackOp transposedUnPackOp;
784 if (maybeUnPackOp) {
785 OpOperand &opOperand =
786 transposedLinalgOp->getOpOperand(idx: packUseOperandNumber);
787 OpResult transposedResult = transposedLinalgOp.getTiedOpResult(opOperand: &opOperand);
788 rewriter.setInsertionPoint(maybeUnPackOp);
789 transposedUnPackOp = maybeUnPackOp.createTransposedClone(
790 b&: rewriter, loc, transposedSource: transposedResult, innerPermutation: innerPerm, outerPermutation: outerPerm);
791
792 rewriter.replaceOp(op: maybeUnPackOp, newValues: transposedUnPackOp->getResults());
793 }
794
795 // Step 4. Finally, replace packOp now that we don't need it anymore.
796 if (packOp.hasPureTensorSemantics())
797 rewriter.replaceOp(op: packOp, newValues: transposedPackOp->getResults());
798 else
799 rewriter.eraseOp(op: packOp);
800
801 return PackTransposeResult{.transposedPackOp: transposedPackOp, .transposedLinalgOp: transposedLinalgOp,
802 .transposedUnPackOp: transposedUnPackOp};
803}
804
805//===----------------------------------------------------------------------===//
806// packMatmulGreedily transformation.
807//===----------------------------------------------------------------------===//
808
809/// Pack a LinalgOp by greedily inferring matmul dimensions (m, n, k) where m
810/// and n are proper parallel dimensions and k is a proper reduction
811/// dimension. Packing occurs by rewriting the op as a linalg.generic and
812/// calling linalg::pack by `mnkPackedSizes`. The order of the packed
813/// dimensions is customizable: the `mnkOrder` is a permutation of {0, 1, 2}
814/// to reorder {m, n, k} into one of the 8 possible forms. The outer
815/// dimensions of the operands are not permuted at this time, this is left for
816/// future work.
817FailureOr<PackResult>
818linalg::packMatmulGreedily(RewriterBase &rewriter, LinalgOp linalgOp,
819 ArrayRef<OpFoldResult> mnkPackedSizes,
820 ArrayRef<int64_t> mnkPaddedSizesNextMultipleOf,
821 ArrayRef<int64_t> mnkOrder) {
822 assert(mnkPackedSizes.size() == 3 && "unexpected num of packing sizes");
823 assert((mnkPaddedSizesNextMultipleOf.empty() ||
824 mnkPaddedSizesNextMultipleOf.size() == 3) &&
825 "num of packing sizes next multiple should be empty or of size 3");
826 assert(mnkOrder.size() == 3 && "unexpected mnkOrder size");
827 assert(isPermutationVector(mnkOrder) && "expected a permutation");
828
829 int64_t numLoops = linalgOp.getNumLoops();
830 if (numLoops <= 2) {
831 LDBG() << "need 3+ loops to find a matmul to pack, got " << numLoops
832 << " in: " << linalgOp;
833 return rewriter.notifyMatchFailure(
834 arg&: linalgOp, msg: "need 3+ loops to find a matmul to pack");
835 }
836
837 // Locally adjust the desired iterator position of mnk and packing sizes.
838 int64_t numPackedDims = mnkPackedSizes.size();
839 SmallVector<int64_t> mmnnkkPos(numPackedDims);
840 for (int64_t i = 0, e = numPackedDims; i < e; ++i)
841 mmnnkkPos[i] = numLoops - numPackedDims + mnkOrder[i];
842 SmallVector<OpFoldResult> packedSizes(numPackedDims);
843 for (int64_t i = 0, e = numPackedDims; i < e; ++i)
844 packedSizes[mnkOrder[i]] = mnkPackedSizes[i];
845 SmallVector<int64_t> paddedSizesNextMultipleOf(numPackedDims);
846 for (int64_t i = 0, e = numPackedDims; i < e; ++i) {
847 paddedSizesNextMultipleOf[mnkOrder[i]] =
848 mnkPaddedSizesNextMultipleOf.empty() ? 0
849 : mnkPaddedSizesNextMultipleOf[i];
850 }
851
852 // 1. Infer dims that are important for matmul.
853 FailureOr<ContractionDimensions> maybeDimensions =
854 inferContractionDims(linalgOp);
855 if (failed(Result: maybeDimensions)) {
856 LDBG() << "couldn't infer matmul iterators in: " << linalgOp;
857 return rewriter.notifyMatchFailure(arg&: linalgOp,
858 msg: "couldn't infer matmul iterators");
859 }
860
861 // 2. Normalize linalgOp to an kmn-matmul-like with [red, par, par] most
862 // minor iterators. In cases with multiple options for m, n, k bias towards
863 // the most minor embedding.
864 // If we wanted a different normalization order, this is where it would have
865 // to plug a heuristic.
866 int64_t mPos = maybeDimensions->m.back(), nPos = maybeDimensions->n.back(),
867 kPos = maybeDimensions->k.back();
868 LDBG() << "Start packing generic op greedily with (m@" << mPos << ", n@"
869 << nPos << ", k@" << kPos << "): " << linalgOp;
870
871 // 2.a. Rewrite as a generic.
872 auto genericOp = dyn_cast<GenericOp>(Val: linalgOp.getOperation());
873 if (!genericOp) {
874 FailureOr<LinalgOp> generalizeResult =
875 generalizeNamedOp(rewriter, linalgOp);
876 assert(succeeded(generalizeResult) &&
877 isa<GenericOp>(generalizeResult->getOperation()) &&
878 "unexpected failure generalizing op");
879 genericOp = cast<GenericOp>(Val: generalizeResult->getOperation());
880 }
881
882 // 2.b. Interchange to move the dimensions (k, m, n) as most-minor
883 // iterators. Note that this only normalized the iteration order and does
884 // not change the indexings of any operand.
885 SmallVector<int64_t> permutation =
886 computePermutationVector(permSize: numLoops, positions: {mPos, nPos, kPos}, desiredPositions: mmnnkkPos);
887 LDBG() << "perm: " << llvm::interleaved(R: permutation);
888 // Sign .. unsigned pollution.
889 SmallVector<unsigned> unsignedPerm(permutation.begin(), permutation.end());
890 FailureOr<GenericOp> interchangeResult =
891 interchangeGenericOp(rewriter, genericOp, interchangeVector: unsignedPerm);
892 assert(succeeded(interchangeResult) && "unexpected failure interchanging op");
893 genericOp = *interchangeResult;
894 LDBG() << "Generalized Op to pack: " << genericOp;
895
896 // At this point, the op iterators are normalized to {leading, k, m, n}.
897 // The layouts induced by packing will always be:
898 // - LHS{leading_lhs, kk, mm}
899 // - RHS{leading_rhs, kk, nn}
900 // - RES{leading_res, mm, nn}
901 // If we wanted to change the packed order, we would reorder (k, m, n) to
902 // something else above.
903 //
904 // Additional permutations of the outer dims of the operands (i.e.
905 // leading_lhs, leading_rhs and leading_res) could follow by computing the
906 // desired outerPerm for each operand.
907 // This is left for future work.
908
909 // TODO: this creates too much IR, go use reifyResultShapes.
910 SmallVector<Range, 4> loopRanges =
911 cast<LinalgOp>(Val: genericOp.getOperation())
912 .createLoopRanges(b&: rewriter, loc: genericOp.getLoc());
913
914 // Add leading zeros to match numLoops, we only pack the last 3 dimensions
915 // post interchange.
916 LDBG() << "paddedSizesNextMultipleOf: "
917 << llvm::interleaved(R: paddedSizesNextMultipleOf);
918 LDBG() << "loopRanges: "
919 << llvm::interleaved(
920 R: llvm::map_range(C&: loopRanges, F: [](Range r) { return r.size; }));
921 SmallVector<OpFoldResult> adjustedPackedSizes(numLoops - packedSizes.size(),
922 rewriter.getIndexAttr(value: 0));
923 for (int64_t i = 0, e = numPackedDims; i < e; ++i) {
924 if (paddedSizesNextMultipleOf[i] == 0) {
925 adjustedPackedSizes.push_back(Elt: packedSizes[i]);
926 continue;
927 }
928 AffineExpr d0, s0;
929 bindDims(ctx: rewriter.getContext(), exprs&: d0);
930 bindSymbols(ctx: rewriter.getContext(), exprs&: s0);
931 adjustedPackedSizes.push_back(Elt: affine::makeComposedFoldedAffineApply(
932 b&: rewriter, loc: genericOp->getLoc(), expr: d0.ceilDiv(other: s0) * s0,
933 operands: {loopRanges[adjustedPackedSizes.size()].size,
934 rewriter.getIndexAttr(value: paddedSizesNextMultipleOf[i])}));
935 }
936 LDBG() << "adjustedPackedSizes: " << llvm::interleaved(R: adjustedPackedSizes);
937
938 // TODO: If we wanted to give the genericOp a name after packing, after
939 // calling `pack` would be a good time. One would still need to check that
940 // `containsMostMinorMatmul(packingRes->packedLinalgOp)` is true, since we
941 // also allow degenerate matmul cases (i.e. matvec, dot).
942 return pack(rewriter, linalgOp: genericOp, packedSizes: adjustedPackedSizes);
943}
944
945//===----------------------------------------------------------------------===//
946// Transformations exposed as rewrite patterns.
947//===----------------------------------------------------------------------===//
948
949LinalgTilingOptions &
950mlir::linalg::LinalgTilingOptions::setTileSizes(ArrayRef<int64_t> ts) {
951 assert(!tileSizeComputationFunction && "tile sizes already set");
952 SmallVector<int64_t, 4> tileSizes(ts);
953 tileSizeComputationFunction = [tileSizes](OpBuilder &b, Operation *op) {
954 OpBuilder::InsertionGuard guard(b);
955 b.setInsertionPointToStart(
956 &op->getParentOfType<func::FuncOp>().getBody().front());
957 return llvm::map_to_vector<4>(C: tileSizes, F: [&](int64_t s) {
958 Value v = arith::ConstantIndexOp::create(builder&: b, location: op->getLoc(), value: s);
959 return v;
960 });
961 };
962 return *this;
963}
964
965LogicalResult mlir::linalg::CopyVectorizationPattern::matchAndRewrite(
966 memref::CopyOp copyOp, PatternRewriter &rewriter) const {
967 return vectorizeCopy(builder&: rewriter, copyOp);
968}
969
970/// Filling `dest` using FillOp constant padding value if possible.
971/// Otherwise, generate a tensor::GenerateOp.
972Value DecomposePadOpPattern::createFillOrGenerateOp(
973 RewriterBase &rewriter, tensor::PadOp padOp, Value dest,
974 const SmallVector<Value> &dynSizes) const {
975 auto padValue = padOp.getConstantPaddingValue();
976 if (padValue) {
977 // Move the padding value defined inside the PadOp block to outside.
978 if (padValue.getParentBlock() == &padOp.getRegion().front())
979 rewriter.moveOpBefore(op: padValue.getDefiningOp(), existingOp: padOp);
980 return FillOp::create(builder&: rewriter, location: padOp.getLoc(), inputs: padValue, outputs: dest).result();
981 }
982
983 // Fill could not be optimized: Lower to tensor::GenerateOp with region.
984 auto generateOp = tensor::GenerateOp::create(builder&: rewriter, location: padOp.getLoc(),
985 result: padOp.getResultType(), dynamicExtents: dynSizes);
986 // Copy region to new op.
987 IRMapping bvm;
988 padOp.getRegion().cloneInto(dest: &generateOp.getRegion(), mapper&: bvm);
989 return generateOp;
990}
991
992LogicalResult
993DecomposePadOpPattern::matchAndRewrite(tensor::PadOp padOp,
994 PatternRewriter &rewriter) const {
995 // Given an OpFoldResult, return an index-typed value.
996 auto getIdxValue = [&](OpFoldResult ofr) {
997 if (auto val = llvm::dyn_cast_if_present<Value>(Val&: ofr))
998 return val;
999 return arith::ConstantIndexOp::create(
1000 builder&: rewriter, location: padOp.getLoc(),
1001 value: cast<IntegerAttr>(Val: cast<Attribute>(Val&: ofr)).getInt())
1002 .getResult();
1003 };
1004
1005 auto resultType = padOp.getResultType();
1006 // Compute size of EmptyOp. Any combination of static/dynamic is supported.
1007 SmallVector<Value> dynSizes;
1008 SmallVector<int64_t> staticSizes;
1009 for (unsigned dim = 0; dim < resultType.getRank(); ++dim) {
1010 if (resultType.isDynamicDim(idx: dim)) {
1011 auto srcSize = getIdxValue(tensor::getMixedSize(builder&: rewriter, loc: padOp.getLoc(),
1012 value: padOp.getSource(), dim));
1013 // Add low and high padding value.
1014 auto plusLow = rewriter.createOrFold<arith::AddIOp>(
1015 location: padOp.getLoc(), args&: srcSize, args: getIdxValue(padOp.getMixedLowPad()[dim]));
1016 auto plusHigh = rewriter.createOrFold<arith::AddIOp>(
1017 location: padOp.getLoc(), args&: plusLow, args: getIdxValue(padOp.getMixedHighPad()[dim]));
1018 dynSizes.push_back(Elt: plusHigh);
1019 }
1020 staticSizes.push_back(Elt: resultType.getDimSize(idx: dim));
1021 }
1022
1023 // Init tensor and fill it with padding.
1024 Value emptyTensor =
1025 tensor::EmptyOp::create(builder&: rewriter, location: padOp.getLoc(), staticShape: staticSizes,
1026 elementType: resultType.getElementType(), dynamicSizes: dynSizes);
1027 Value fill = createFillOrGenerateOp(rewriter, padOp, dest: emptyTensor, dynSizes);
1028
1029 // Generate a InsertSliceOp for copying the PadOp source.
1030 auto sourceType = padOp.getSourceType();
1031 // Compute size of source of tensor::PadOp.
1032 SmallVector<OpFoldResult> srcSizes =
1033 tensor::getMixedSizes(builder&: rewriter, loc: padOp.getLoc(), value: padOp.getSource());
1034 // Strides of InsertSliceOp are all 1.
1035 SmallVector<OpFoldResult> strides(sourceType.getRank(),
1036 rewriter.getIndexAttr(value: 1));
1037 rewriter.replaceOpWithNewOp<tensor::InsertSliceOp>(
1038 op: padOp, args: padOp.getSource(), args&: fill, args: padOp.getMixedLowPad(), args&: srcSizes,
1039 args&: strides);
1040
1041 return success();
1042}
1043
1044LogicalResult ExtractSliceOfPadTensorSwapPattern::matchAndRewrite(
1045 tensor::ExtractSliceOp sliceOp, PatternRewriter &rewriter) const {
1046 if (!sliceOp.hasUnitStride())
1047 return failure();
1048
1049 auto padOp = sliceOp.getSource().getDefiningOp<tensor::PadOp>();
1050 if (!padOp)
1051 return failure();
1052
1053 bool zeroSliceGuard = true;
1054 if (controlFn) {
1055 if (std::optional<bool> control = controlFn(sliceOp))
1056 zeroSliceGuard = *control;
1057 else
1058 return failure();
1059 }
1060
1061 FailureOr<TilingResult> tilingResult =
1062 tensor::bubbleUpPadSlice(b&: rewriter, padOp, offsets: sliceOp.getMixedOffsets(),
1063 sizes: sliceOp.getMixedSizes(), generateZeroSliceGuard: zeroSliceGuard);
1064 if (failed(Result: tilingResult))
1065 return failure();
1066
1067 RankedTensorType sourceType = sliceOp.getSourceType();
1068 RankedTensorType resultType = sliceOp.getResultType();
1069
1070 // If the extract_slice is not rank-reduced, all shapes are static and the
1071 // data source is actually used. Rewrite into pad(extract_slice(x)).
1072 if (sourceType.getRank() == resultType.getRank()) {
1073 rewriter.replaceOp(op: sliceOp, newValues: tilingResult->tiledValues);
1074 return success();
1075 }
1076
1077 // Handle rank-reduced slice by creating another extract_slice op.
1078 Value rankReduced = tensor::createCanonicalRankReducingExtractSliceOp(
1079 b&: rewriter, loc: sliceOp.getLoc(), tensor: tilingResult->tiledValues[0], targetType: resultType);
1080
1081 rewriter.replaceOp(op: sliceOp, newValues: rankReduced);
1082 return success();
1083}
1084
1085/// If padding value is set, returns a tensor.pad Op for the source tensor,
1086/// with the output shape matching the output of `packOp`. Otherwise, returns
1087/// the source directly.
1088///
1089/// This method assumes that all outer dims for this pack Op are 1.
1090static Value getPackOpSourceOrPaddedSource(OpBuilder &builder,
1091 linalg::PackOp packOp) {
1092 Value input = packOp.getSource();
1093 // Pack/unpack memref transformations are unsupported. The memref forms
1094 // are mainly for bufferization and scalar lowering. Other uses are not
1095 // recommended, see #225650 for details.
1096 if (!packOp.hasPureTensorSemantics())
1097 return input;
1098
1099 if (!packOp.getPaddingValue()) {
1100 return input;
1101 }
1102
1103 assert(llvm::all_of(packOp.getAllOuterDims(),
1104 [](int64_t val) { return val == 1; }) &&
1105 "some outer dims are != 1");
1106
1107 Location loc = packOp.getLoc();
1108 ShapedType inputType = packOp.getSourceType();
1109 int64_t inputRank = inputType.getRank();
1110
1111 DenseMap<int64_t, OpFoldResult> tileAndPosMapping =
1112 packOp.getDimAndTileMapping();
1113
1114 // The sizes of dynamic tiles
1115 SmallVector<Value> dynamicTileSizes;
1116
1117 // Collect dims for the padded shape.
1118 SmallVector<int64_t> paddedShape;
1119 for (int64_t dimIdx = 0; dimIdx < inputRank; ++dimIdx) {
1120 // 1. Non-tiled outer dims.
1121 // These dims should be 1 and we simply preserve them.
1122 if (!tileAndPosMapping.count(Val: dimIdx)) {
1123 int64_t inputDimSize = inputType.getDimSize(idx: dimIdx);
1124 assert(inputDimSize == 1 &&
1125 "with all outer dims == 1, this non-tiled input dim should be 1!");
1126 paddedShape.push_back(Elt: inputDimSize);
1127 continue;
1128 }
1129
1130 // 2. Tiled outer dims
1131 // As all outer dims == 1, it is safe to use the tile size for the padded
1132 // shape.
1133 OpFoldResult tileSizeForDim = tileAndPosMapping.lookup(Val: dimIdx);
1134
1135 // 2.1 Static tile sizes
1136 std::optional<int64_t> cstTileSize = getConstantIntValue(ofr: tileSizeForDim);
1137 if (cstTileSize.has_value()) {
1138 paddedShape.push_back(Elt: cstTileSize.value());
1139 continue;
1140 }
1141
1142 // 2.2 Dynamic tile sizes
1143 paddedShape.push_back(Elt: ShapedType::kDynamic);
1144
1145 // Get the value that holds the dynamic size.
1146 dynamicTileSizes.push_back(Elt: llvm::dyn_cast<Value>(Val&: tileSizeForDim));
1147 }
1148 auto resultType =
1149 RankedTensorType::get(shape: paddedShape, elementType: inputType.getElementType());
1150 return tensor::createPadHighOp(resType: resultType, source: input, pad: packOp.getPaddingValue(),
1151 /*nofold=*/false, loc, builder,
1152 dynOutDims: dynamicTileSizes);
1153}
1154
1155// Normalizes a permutation on a higher rank space to its actual size, e.g.
1156// perm = [1, 4, 2]
1157// becomes
1158// norm = [0, 2, 1]
1159static SmallVector<int64_t>
1160getPackUnpackNormalizedPerm(int rank, ArrayRef<int64_t> perm) {
1161 constexpr int64_t kNonTiledMarker = -1;
1162 SmallVector<int64_t> vec(rank, kNonTiledMarker);
1163 for (auto [index, value] : llvm::enumerate(First&: perm))
1164 vec[value] = index;
1165 SmallVector<int64_t> normalizedPerm = llvm::filter_to_vector(
1166 C&: vec, Pred: [&](int64_t v) { return v != kNonTiledMarker; });
1167 // This inverts the permutation in addition to normalizing so invert back.
1168 return invertPermutationVector(permutation: normalizedPerm);
1169}
1170
1171// Gets the normalized permutation implied by innerDimsPos and outerDimsPerm
1172// assuming rank reduction of unit outer dims.
1173static SmallVector<int64_t>
1174getPackUnpackRankReducedPerm(ArrayRef<int64_t> shape,
1175 ArrayRef<int64_t> innerDimsPos,
1176 ArrayRef<int64_t> outerDimsPerm) {
1177 SmallVector<int64_t> rankReducedOuterDimsPerm;
1178 SmallVector<int64_t> outerDims;
1179 SmallVector<int64_t> innerDims;
1180 int64_t dim = 0;
1181 int64_t unpackedRank = shape.size();
1182 for (auto i : llvm::seq<unsigned>(Begin: 0, End: unpackedRank)) {
1183 if (llvm::is_contained(Range&: innerDimsPos, Element: i)) {
1184 innerDims.push_back(Elt: dim++);
1185 continue;
1186 }
1187 if (shape[i] == 1)
1188 continue;
1189 outerDims.push_back(Elt: dim++);
1190 if (!outerDimsPerm.empty())
1191 rankReducedOuterDimsPerm.push_back(Elt: outerDimsPerm[i]);
1192 }
1193
1194 // Get the position of the inner dims after permutation.
1195 SmallVector<int64_t> innerPerm =
1196 getPackUnpackNormalizedPerm(rank: unpackedRank, perm: innerDimsPos);
1197 applyPermutationToVector<int64_t>(inVec&: innerDims, permutation: innerPerm);
1198
1199 // Ditto for the outer dims.
1200 SmallVector<int64_t> perm = outerDims;
1201
1202 rankReducedOuterDimsPerm =
1203 getPackUnpackNormalizedPerm(rank: unpackedRank, perm: rankReducedOuterDimsPerm);
1204 if (!rankReducedOuterDimsPerm.empty())
1205 applyPermutationToVector<int64_t>(inVec&: perm, permutation: rankReducedOuterDimsPerm);
1206
1207 // The tile always ends up as the inner most dims after packing.
1208 perm.append(RHS: innerDims);
1209
1210 return perm;
1211}
1212
1213LogicalResult DecomposeOuterUnitDimsPackOpPattern::matchAndRewrite(
1214 linalg::PackOp packOp, PatternRewriter &rewriter) const {
1215 // Pack/unpack memref transformations are unsupported. The memref forms
1216 // are mainly for bufferization and scalar lowering. Other uses are not
1217 // recommended, see #225650 for details.
1218 if (!packOp.hasPureTensorSemantics())
1219 return failure();
1220
1221 if (llvm::any_of(Range: packOp.getTiledOuterDims(),
1222 P: [](int64_t dim) { return dim != 1; })) {
1223 return rewriter.notifyMatchFailure(
1224 arg&: packOp, msg: "not all outer dimensions of the result are 1s");
1225 }
1226
1227 // When a padding value is set, getPackOpSourceOrPaddedSource only supports
1228 // the case where every outer dim (including un-tiled ones) is 1. Bail out
1229 // instead of hitting an assertion on a non-unit un-tiled outer dim.
1230 // FIXME: Handle this case by decomposing the padded pack instead of bailing
1231 // out; a non-unit un-tiled outer dim should be supported here.
1232 if (packOp.getPaddingValue() &&
1233 llvm::any_of(Range: packOp.getAllOuterDims(),
1234 P: [](int64_t dim) { return dim != 1; })) {
1235 return rewriter.notifyMatchFailure(
1236 arg&: packOp, msg: "cannot decompose padded pack with a non-unit un-tiled outer "
1237 "dimension");
1238 }
1239
1240 ArrayRef<int64_t> innerDimsPos = packOp.getInnerDimsPos();
1241 auto outerDimsPerm = packOp.getOuterDimsPerm();
1242
1243 // Verify that there are no:
1244 // * non-unit + un-tiled-outer-dims,
1245 // that are permuted. Supporting such cases would require refining the logic
1246 // that generates the Transpose Op.
1247 if (!llvm::all_of(Range&: outerDimsPerm, P: [&innerDimsPos, &packOp](int64_t dim) {
1248 static int prev = 0;
1249 // Skip tiled dims - these can be permuted.
1250 if (llvm::is_contained(Range&: innerDimsPos, Element: dim))
1251 return true;
1252
1253 // Check whether this dim has been permuted. Permuting unit dims is fine
1254 // as that's effectively a no-op.
1255 if (dim < prev && (packOp.getResult().getType().getShape()[prev] != 1 ||
1256 packOp.getResult().getType().getShape()[dim] != 1))
1257 return false;
1258
1259 prev = dim;
1260 return true;
1261 })) {
1262 return rewriter.notifyMatchFailure(
1263 arg&: packOp, msg: "At least one non-unit and un-tiled outer dim is permuted, "
1264 "this is not supported ATM!");
1265 }
1266
1267 Location loc = packOp.getLoc();
1268
1269 int64_t srcRank = packOp.getSourceRank();
1270
1271 // 1. Get the input that is going to be packed. If the input requires padding,
1272 // add a padding operation and return that as the input.
1273 Value input = getPackOpSourceOrPaddedSource(builder&: rewriter, packOp);
1274
1275 // 2. Transpose the input to match the inner tile order:
1276 // %init = tensor.empty()
1277 // %transposed_tile = linalg.transpose ins(%source_or_padded_source),
1278 // outs(%init)
1279 // Assumptions made:
1280 // - All tiled outer dims are 1 - the corresponding transposition order
1281 // doesn't matter, but requires all dim indices to be present.
1282 // - Un-tiled outer dims remain un-permuted.
1283
1284 // 2.1 Get the permutation for linalg.transpose:
1285 // [ untiled-dims, inner-dims-pos ]
1286 // Note, this logic assumes that the untiled dims are not permuted.
1287 SmallVector<int64_t> srcPermForTranspose;
1288 for (int64_t i = 0; i < srcRank; i++) {
1289 // We assume the `k` dimensions of the inner dim position, where `k` is the
1290 // rank of the inner tiling, correspond to the last `k` indices of the
1291 // transpose permutation. This is done by adding the indices not contained
1292 // in the inner dimension position in order from 0 to `n`. Where n is the
1293 // rank of the source tensor. For example if we have a source tensor with
1294 // indices [0, 1, 2, 3] and inner dim position of [3, 0], the remaining
1295 // indices are [1, 2]. and the transpose will be [1, 2, 3, 0].
1296 if (llvm::is_contained(Range&: innerDimsPos, Element: i))
1297 continue;
1298 srcPermForTranspose.push_back(Elt: i);
1299 }
1300 srcPermForTranspose.append(in_start: innerDimsPos.begin(), in_end: innerDimsPos.end());
1301
1302 // 2.2 Create the init tensor for linalg.transpose with the correct shape:
1303 // [ untiled-dims, tiled-dims ]
1304 ShapedType inputTy = cast<ShapedType>(Val: input.getType());
1305 SmallVector<OpFoldResult> shapeForEmptyOp;
1306 for (int64_t i = 0; i < srcRank; i++) {
1307 if (llvm::is_contained(Range&: innerDimsPos, Element: i)) {
1308 // The tiled dims are appended after this loop.
1309 continue;
1310 }
1311 if (inputTy.isStaticDim(idx: i))
1312 shapeForEmptyOp.push_back(Elt: rewriter.getIndexAttr(value: inputTy.getShape()[i]));
1313 else
1314 shapeForEmptyOp.emplace_back(
1315 Args: tensor::DimOp::create(builder&: rewriter, location: loc, source: input, index: i).getResult());
1316 }
1317 shapeForEmptyOp.append(RHS: packOp.getMixedTiles());
1318
1319 // getMixedTiles() may contain Values pointing to constant ops (as opposed to
1320 // constant attributes with the corresponding value). Replace those with
1321 // attributes. This is to match the behaviour in
1322 // `getPackOpSourceOrPaddedSource`, which replaces constant SSA values with
1323 // attributes.
1324 llvm::transform(Range&: shapeForEmptyOp, d_first: shapeForEmptyOp.begin(),
1325 F: [&](OpFoldResult ofr) {
1326 if (auto val = llvm::dyn_cast<Value>(Val&: ofr))
1327 return getAsOpFoldResult(val);
1328 return ofr;
1329 });
1330
1331 LDBG() << "Pack permutation: " << packOp;
1332 LDBG() << "perm: " << llvm::interleaved(R: srcPermForTranspose);
1333 LDBG() << "Shape of empty tensor: " << llvm::interleaved(R: shapeForEmptyOp);
1334
1335 Value empty = tensor::EmptyOp::create(
1336 builder&: rewriter, location: loc, sizes: shapeForEmptyOp, elementType: packOp.getSourceType().getElementType());
1337
1338 // 2.3 Create linalg.transpose
1339 auto transposedOp = linalg::TransposeOp::create(builder&: rewriter, location: loc, input, init: empty,
1340 permutation: srcPermForTranspose);
1341
1342 // 3. Insert the inner tile into the destination tensor:
1343 // %inserted_tile = tensor.insert_slice(%transposed_tile)
1344
1345 // Compute the sizes attribute:
1346 // [ outer-dims, tile-sizes ]
1347 // Note that the output from the transpose Op excludes the tiled outer dims.
1348 // However, given the assumption that:
1349 // * all tiled outer dims == 1,
1350 // we can just use a rank-expanding tensor.insert_slice.
1351 SmallVector<OpFoldResult> writeSizes;
1352 for (auto size : packOp.getAllOuterDims()) {
1353 writeSizes.push_back(Elt: rewriter.getIndexAttr(value: size));
1354 }
1355
1356 for (auto tileSize : packOp.getMixedTiles()) {
1357 auto [_, tileSizeOfr] =
1358 getSimplifiedOfrAndStaticSizePair(ofr: tileSize, b&: rewriter);
1359 writeSizes.push_back(Elt: tileSizeOfr);
1360 }
1361
1362 auto insert = tensor::InsertSliceOp::create(
1363 builder&: rewriter, location: loc, source: transposedOp.getResult()[0], dest: packOp.getDest(), sizes: writeSizes);
1364
1365 // 4. Replace tensor.packOp with tensor.insert_slice created above
1366 rewriter.replaceOp(op: packOp, newValues: insert.getResult());
1367
1368 return success();
1369}
1370
1371LogicalResult DecomposeOuterUnitDimsUnPackOpPattern::matchAndRewrite(
1372 linalg::UnPackOp unpackOp, PatternRewriter &rewriter) const {
1373 if (!unpackOp.hasPureTensorSemantics())
1374 return failure();
1375
1376 int64_t destRank = unpackOp.getDestRank();
1377 ArrayRef<int64_t> srcShape = unpackOp.getSourceType().getShape();
1378 ArrayRef<int64_t> innerDimsPos = unpackOp.getInnerDimsPos();
1379 if (llvm::any_of(Range: unpackOp.getTiledOuterDims(),
1380 P: [](int64_t dim) { return dim != 1; })) {
1381 return rewriter.notifyMatchFailure(
1382 arg&: unpackOp,
1383 msg: "require the tiled outer dimensions of the result are all 1s");
1384 }
1385
1386 // 1. Use rank-reduced tensor.extract_slice op to extract the tile:
1387 // %extracted_tile = tensor.extract_slice(%unpack_op_input)
1388 Location loc = unpackOp.getLoc();
1389 Value source = unpackOp.getSource();
1390 DenseMap<int64_t, OpFoldResult> dimAndTileMapping =
1391 unpackOp.getDimAndTileMapping();
1392 Attribute oneIdxAttr = rewriter.getIndexAttr(value: 1);
1393
1394 // The shape for ExtractSliceOp. Note that this will consist of 3 blocks of
1395 // dims:
1396 // [ outer-untiled-dims, outer-tiled-dims, tile-sizes ]
1397 SmallVector<int64_t> readShapeForExtractSlice;
1398 // The sizes attribute for ExtractSliceOp. Due to rank-reducing (and
1399 // outer-tiled-dims being all 1), this will be
1400 // [ outer-untiled-dims, tile-sizes ]
1401 SmallVector<OpFoldResult> extractSliceSizes;
1402
1403 // Shape for EmptyOp that's used as the init value for TransposeOp below.
1404 // This should be:
1405 // [ outer-untiled-dims, tile-sizes ]
1406 // However, skip unit dims - TransposeOp (below) applies rank-reduced
1407 // permutation.
1408 SmallVector<OpFoldResult> shapeForEmptyOp;
1409
1410 for (auto i : llvm::seq<unsigned>(Begin: 0, End: destRank)) {
1411 // Compute sizes attribute for ExtractSliceOp - outer-tiled-dims.
1412 //
1413 // As all outer tiled dims are 1, so the corresponding
1414 // slice size to read will also 1. As this will be rank-reducing "extract
1415 // slice" (i.e. the unit dims will be "collapsed"), there's no need to
1416 // update:
1417 // * the output shape for ExtractSliceOp, nor
1418 // * the shape for EmptyOp.
1419 if (dimAndTileMapping.count(Val: i)) {
1420 extractSliceSizes.push_back(Elt: oneIdxAttr);
1421 continue;
1422 }
1423
1424 // Compute sizes attribute for ExtractSliceOp + EmptyOp -
1425 // outer-untiled-dims
1426 if (ShapedType::isDynamic(dValue: srcShape[i])) {
1427 OpFoldResult dynamicDim =
1428 tensor::DimOp::create(builder&: rewriter, location: loc, source, index: i).getResult();
1429 extractSliceSizes.push_back(Elt: dynamicDim);
1430 shapeForEmptyOp.push_back(Elt: dynamicDim);
1431 } else {
1432 extractSliceSizes.push_back(Elt: rewriter.getIndexAttr(value: srcShape[i]));
1433 if (srcShape[i] != 1)
1434 shapeForEmptyOp.push_back(Elt: rewriter.getIndexAttr(value: srcShape[i]));
1435 }
1436 // Compute the output shape for ExtractSliceOp - outer-untiled-dims (take
1437 // into account rank-reducing)
1438 if (srcShape[i] != 1) {
1439 readShapeForExtractSlice.push_back(Elt: srcShape[i]);
1440 }
1441 }
1442 // Append the tile sizes to "sizes attribute" for ExtractSliceOp and the
1443 // shape for EmptyOp.
1444 auto mixedTiles = unpackOp.getMixedTiles();
1445 extractSliceSizes.append(in_start: mixedTiles.begin(), in_end: mixedTiles.end());
1446 shapeForEmptyOp.append(in_start: mixedTiles.begin(), in_end: mixedTiles.end());
1447
1448 // Explicitly create the type for extract_slice op because the inner tile
1449 // size could be 1. We want to represent the whole inner tile in this case.
1450 auto tileShape = srcShape.drop_front(N: destRank);
1451 // Append the inner tile shape to the permuted and rank-reduced outer shape.
1452 readShapeForExtractSlice.append(in_start: tileShape.begin(), in_end: tileShape.end());
1453 Type elemType = unpackOp.getSourceType().getElementType();
1454 auto readType = RankedTensorType::get(shape: readShapeForExtractSlice, elementType: elemType);
1455 Value innerTile = tensor::ExtractSliceOp::create(
1456 builder&: rewriter, location: loc, resultType: readType, source: unpackOp.getSource(), sizes: extractSliceSizes);
1457
1458 // 2. Transpose the tile to match the outer corresponding tile order.
1459 SmallVector<int64_t> perm = getPackUnpackRankReducedPerm(
1460 shape: srcShape.take_front(N: destRank), innerDimsPos, outerDimsPerm: unpackOp.getOuterDimsPerm());
1461 // Unpack is a transition out of packed space so we invert the permutation.
1462 perm = invertPermutationVector(permutation: perm);
1463 applyPermutationToVector<OpFoldResult>(inVec&: shapeForEmptyOp, permutation: perm);
1464
1465 Value empty =
1466 tensor::EmptyOp::create(builder&: rewriter, location: loc, sizes: shapeForEmptyOp, elementType: elemType);
1467 auto transposedOp =
1468 linalg::TransposeOp::create(builder&: rewriter, location: loc, input: innerTile, init: empty, permutation: perm);
1469
1470 // 3. Handle in-complete tiles if needed. It truncates trailing data from the
1471 // transposed tile.
1472 SmallVector<OpFoldResult> tileSizes;
1473 ArrayRef<int64_t> destShape = unpackOp.getDestType().getShape();
1474 for (auto i : llvm::seq<unsigned>(Begin: 0, End: destRank)) {
1475 if (dimAndTileMapping.count(Val: i) || destShape[i] != 1)
1476 tileSizes.push_back(
1477 Elt: tensor::getMixedSize(builder&: rewriter, loc, value: unpackOp.getDest(), dim: i));
1478 }
1479
1480 auto partialTile =
1481 tensor::ExtractSliceOp::create(builder&: rewriter, location: loc, resultType: RankedTensorType(),
1482 source: transposedOp.getResult()[0], sizes: tileSizes);
1483
1484 // 4. Insert the result to the destination tensor.
1485 SmallVector<OpFoldResult> writeSizes;
1486 for (int i = 0, idx = 0; i < destRank; ++i) {
1487 if (dimAndTileMapping.count(Val: i) || destShape[i] != 1)
1488 writeSizes.push_back(Elt: tileSizes[idx++]);
1489 else
1490 writeSizes.push_back(Elt: oneIdxAttr);
1491 }
1492 auto insert = tensor::InsertSliceOp::create(builder&: rewriter, location: loc, source: partialTile,
1493 dest: unpackOp.getDest(), sizes: writeSizes);
1494 rewriter.replaceOp(op: unpackOp, newValues: insert.getResult());
1495
1496 return success();
1497}
1498
1499//===----------------------------------------------------------------------===//
1500// Generic DownscaleSizeOneWindowedConvolution
1501//===----------------------------------------------------------------------===//
1502//
1503/// Returns the indices of affine map results that reference any of the given
1504/// dimensions.
1505static SmallVector<unsigned>
1506getResultIndicesReferencingDims(AffineMap map, ArrayRef<unsigned> dims) {
1507 SmallVector<unsigned> resultIndices;
1508 for (unsigned dim : dims) {
1509 for (unsigned i = 0, e = map.getNumResults(); i < e; ++i) {
1510 AffineExpr expr = map.getResult(idx: i);
1511 if (expr.isFunctionOfDim(position: dim)) {
1512 resultIndices.push_back(Elt: i);
1513 break;
1514 }
1515 }
1516 }
1517 return resultIndices;
1518}
1519
1520/// Helper to create a rank-reducing extract_slice that removes specific
1521/// dimensions from a tensor.
1522static Value createRankReducingExtractSlice(RewriterBase &rewriter,
1523 Location loc, Value tensor,
1524 ArrayRef<unsigned> dimsToRemove) {
1525 auto tensorType = cast<RankedTensorType>(Val: tensor.getType());
1526 int64_t rank = tensorType.getRank();
1527
1528 // Compute new shape by removing the specified dimensions.
1529 SmallVector<int64_t> newShape;
1530 for (int64_t i = 0; i < rank; ++i) {
1531 if (!llvm::is_contained(Range&: dimsToRemove, Element: i))
1532 newShape.push_back(Elt: tensorType.getDimSize(idx: i));
1533 }
1534
1535 auto newType = RankedTensorType::get(shape: newShape, elementType: tensorType.getElementType());
1536 return tensor::createCanonicalRankReducingExtractSliceOp(b&: rewriter, loc,
1537 tensor, targetType: newType);
1538}
1539
1540/// Drops specified dimensions from an AffineExpr and compresses remaining
1541/// dimension indices. Returns std::nullopt if the expression only references
1542/// the dropped dimensions.
1543static std::optional<AffineExpr>
1544dropDimsAndCompress(AffineExpr expr, ArrayRef<unsigned> dimsToDrop,
1545 unsigned newNumDims, MLIRContext *ctx) {
1546 // Check if expr only references dimensions to be dropped.
1547 bool onlyReferencesDroppedDims = true;
1548 for (unsigned d = 0; d < newNumDims + dimsToDrop.size(); ++d) {
1549 if (expr.isFunctionOfDim(position: d) && !llvm::is_contained(Range&: dimsToDrop, Element: d)) {
1550 onlyReferencesDroppedDims = false;
1551 break;
1552 }
1553 }
1554 if (onlyReferencesDroppedDims && llvm::any_of(Range&: dimsToDrop, P: [&](unsigned d) {
1555 return expr.isFunctionOfDim(position: d);
1556 }))
1557 return std::nullopt;
1558
1559 // Replace dimensions: compute new index for each old dimension.
1560 // Dropped dimensions get mapped to constant 0, others get compressed.
1561 SmallVector<AffineExpr> dimReplacements;
1562 unsigned newDimIdx = 0;
1563 for (unsigned d = 0; d < newNumDims + dimsToDrop.size(); ++d) {
1564 if (llvm::is_contained(Range&: dimsToDrop, Element: d)) {
1565 dimReplacements.push_back(Elt: getAffineConstantExpr(constant: 0, context: ctx));
1566 } else {
1567 dimReplacements.push_back(Elt: getAffineDimExpr(position: newDimIdx++, context: ctx));
1568 }
1569 }
1570
1571 return expr.replaceDims(dimReplacements);
1572}
1573
1574FailureOr<LinalgOp>
1575linalg::downscaleSizeOneWindowedConvolution(RewriterBase &rewriter,
1576 LinalgOp op) {
1577 auto maybeDims = inferConvolutionDims(linalgOp: op);
1578 if (failed(Result: maybeDims))
1579 return failure();
1580
1581 // Currently supports only 2D convolutions.
1582 if (maybeDims->outputImage.size() != 2 || maybeDims->filterLoop.size() != 2)
1583 return failure();
1584
1585 if (op.hasPureBufferSemantics())
1586 return failure();
1587
1588 // Get loop domain indices for spatial dimensions.
1589 unsigned outSpatial0 = maybeDims->outputImage[0];
1590 unsigned outSpatial1 = maybeDims->outputImage[1];
1591 unsigned filterSpatial0 = maybeDims->filterLoop[0];
1592 unsigned filterSpatial1 = maybeDims->filterLoop[1];
1593
1594 // Get sizes from loop bounds.
1595 SmallVector<int64_t, 4> loopRanges = op.getStaticLoopRanges();
1596 int64_t outSize0 = loopRanges[outSpatial0];
1597 int64_t outSize1 = loopRanges[outSpatial1];
1598 int64_t filterSize0 = loopRanges[filterSpatial0];
1599 int64_t filterSize1 = loopRanges[filterSpatial1];
1600
1601 // Check if we can downscale by removing a spatial dimension.
1602 bool canRemoveSpatial0 = (filterSize0 == 1 && outSize0 == 1);
1603 bool canRemoveSpatial1 = (filterSize1 == 1 && outSize1 == 1);
1604 if (!canRemoveSpatial0 && !canRemoveSpatial1)
1605 return failure();
1606
1607 // Determine which loop dims to remove (output spatial + corresponding filter)
1608 // and sort for correct index compression when removing dimensions from affine
1609 // maps.
1610 SmallVector<unsigned> loopDimsToRemove;
1611 if (canRemoveSpatial0) {
1612 loopDimsToRemove.push_back(Elt: outSpatial0);
1613 loopDimsToRemove.push_back(Elt: filterSpatial0);
1614 } else {
1615 loopDimsToRemove.push_back(Elt: outSpatial1);
1616 loopDimsToRemove.push_back(Elt: filterSpatial1);
1617 }
1618 llvm::sort(C&: loopDimsToRemove);
1619
1620 // Create new indexing maps with dimensions removed.
1621 SmallVector<AffineMap> newMaps;
1622 MLIRContext *ctx = op.getContext();
1623 unsigned numDims = op.getNumLoops();
1624 unsigned newNumDims = numDims - loopDimsToRemove.size();
1625 for (AffineMap map : op.getIndexingMapsArray()) {
1626 SmallVector<AffineExpr> newResults;
1627 for (AffineExpr expr : map.getResults()) {
1628 auto newExpr =
1629 dropDimsAndCompress(expr, dimsToDrop: loopDimsToRemove, newNumDims, ctx);
1630 if (newExpr)
1631 newResults.push_back(Elt: *newExpr);
1632 }
1633 newMaps.push_back(Elt: AffineMap::get(dimCount: newNumDims, symbolCount: 0, results: newResults, context: ctx));
1634 }
1635
1636 // Create new iterator types.
1637 SmallVector<utils::IteratorType> newIterTypes;
1638 auto iterTypes = op.getIteratorTypesArray();
1639 for (unsigned idx = 0; idx < iterTypes.size(); ++idx) {
1640 if (!llvm::is_contained(Range&: loopDimsToRemove, Element: idx))
1641 newIterTypes.push_back(Elt: iterTypes[idx]);
1642 }
1643
1644 // Rank-reduce operands using extract_slice.
1645 Location loc = op.getLoc();
1646 SmallVector<Value> newInputs;
1647 for (OpOperand *input : op.getDpsInputOperands()) {
1648 AffineMap map = op.getMatchingIndexingMap(opOperand: input);
1649 SmallVector<unsigned> tensorDimsToRemove =
1650 getResultIndicesReferencingDims(map, dims: loopDimsToRemove);
1651 Value reduced = createRankReducingExtractSlice(rewriter, loc, tensor: input->get(),
1652 dimsToRemove: tensorDimsToRemove);
1653 newInputs.push_back(Elt: reduced);
1654 }
1655
1656 OpOperand &output = *op.getDpsInitsMutable().begin();
1657 AffineMap outputMap = op.getMatchingIndexingMap(opOperand: &output);
1658 SmallVector<unsigned> outputDimsToRemove =
1659 getResultIndicesReferencingDims(map: outputMap, dims: loopDimsToRemove);
1660 Value newOutput = createRankReducingExtractSlice(rewriter, loc, tensor: output.get(),
1661 dimsToRemove: outputDimsToRemove);
1662
1663 // Create new linalg.generic with reduced dimensions.
1664 auto newOp =
1665 linalg::GenericOp::create(builder&: rewriter, location: loc, resultTensorTypes: TypeRange{newOutput.getType()},
1666 inputs: newInputs, outputs: newOutput, indexingMaps: newMaps, iteratorTypes: newIterTypes);
1667 rewriter.inlineRegionBefore(region&: op->getRegion(index: 0), parent&: newOp.getRegion(),
1668 before: newOp.getRegion().begin());
1669
1670 // Try to specialize the generic back to a named op only if the input was
1671 // already a specialized (named) op.
1672 LinalgOp resultOp = newOp;
1673 if (!isa<GenericOp>(Val: op)) {
1674 FailureOr<LinalgOp> specializedOp = specializeGenericOp(rewriter, genericOp: newOp);
1675 if (succeeded(Result: specializedOp))
1676 resultOp = *specializedOp;
1677 }
1678
1679 // Insert result back into original shape.
1680 Value result = tensor::createCanonicalRankReducingInsertSliceOp(
1681 b&: rewriter, loc, tensor: resultOp->getResult(idx: 0), dest: output.get());
1682
1683 rewriter.replaceOp(op, newValues: result);
1684 return resultOp;
1685}
1686
1687namespace {
1688/// Pattern wrapper around `downscaleSizeOneWindowedConvolution`.
1689struct DownscaleSizeOneWindowedConvolution final
1690 : public OpInterfaceRewritePattern<LinalgOp> {
1691 DownscaleSizeOneWindowedConvolution(MLIRContext *context,
1692 PatternBenefit benefit = 1)
1693 : OpInterfaceRewritePattern<LinalgOp>(context, benefit) {}
1694
1695 LogicalResult matchAndRewrite(LinalgOp op,
1696 PatternRewriter &rewriter) const override {
1697 return linalg::downscaleSizeOneWindowedConvolution(rewriter, op);
1698 }
1699};
1700} // namespace
1701
1702void linalg::populateDecomposeConvolutionPatterns(RewritePatternSet &patterns,
1703 PatternBenefit benefit) {
1704 patterns.add<DownscaleSizeOneWindowedConvolution>(arg: patterns.getContext(),
1705 args&: benefit);
1706}
1707
1708void linalg::populateDecomposePackUnpackPatterns(RewritePatternSet &patterns) {
1709 patterns.add<DecomposeOuterUnitDimsPackOpPattern>(arg: patterns.getContext());
1710 patterns.add<DecomposeOuterUnitDimsUnPackOpPattern>(arg: patterns.getContext());
1711}
1712
1713void linalg::populateDecomposePadPatterns(RewritePatternSet &patterns) {
1714 patterns.add<DecomposePadOpPattern>(arg: patterns.getContext());
1715}
1716