1//===- Vectorization.cpp - Implementation of linalg Vectorization ---------===//
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 the linalg dialect Vectorization transformations.
10//
11//===----------------------------------------------------------------------===//
12#include "mlir/Dialect/Affine/Utils.h"
13
14#include "mlir/Analysis/SliceAnalysis.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/IR/LinalgInterfaces.h"
20#include "mlir/Dialect/Linalg/Transforms/Transforms.h"
21#include "mlir/Dialect/Linalg/Utils/Utils.h"
22#include "mlir/Dialect/Tensor/IR/Tensor.h"
23#include "mlir/Dialect/Utils/IndexingUtils.h"
24#include "mlir/Dialect/Utils/StructuredOpsUtils.h"
25#include "mlir/Dialect/Vector/IR/VectorOps.h"
26#include "mlir/Dialect/Vector/Interfaces/MaskableOpInterface.h"
27#include "mlir/Dialect/Vector/Utils/VectorUtils.h"
28#include "mlir/IR/AffineExpr.h"
29#include "mlir/IR/AffineMap.h"
30#include "mlir/IR/Builders.h"
31#include "mlir/IR/BuiltinTypeInterfaces.h"
32#include "mlir/IR/BuiltinTypes.h"
33#include "mlir/IR/OpDefinition.h"
34#include "mlir/IR/PatternMatch.h"
35#include "mlir/IR/Value.h"
36#include "mlir/Support/LLVM.h"
37#include "mlir/Transforms/RegionUtils.h"
38#include "llvm/ADT/STLExtras.h"
39#include "llvm/ADT/Sequence.h"
40#include "llvm/ADT/SmallPtrSet.h"
41#include "llvm/ADT/SmallVector.h"
42#include "llvm/ADT/SmallVectorExtras.h"
43#include "llvm/ADT/TypeSwitch.h"
44#include "llvm/Support/DebugLog.h"
45#include "llvm/Support/InterleavedRange.h"
46#include "llvm/Support/MathExtras.h"
47#include "llvm/Support/raw_ostream.h"
48#include <optional>
49
50using namespace mlir;
51using namespace mlir::linalg;
52
53#define DEBUG_TYPE "linalg-vectorization"
54
55/// Try to vectorize `convOp` as a convolution.
56static FailureOr<Operation *>
57vectorizeConvolution(RewriterBase &rewriter, LinalgOp convOp,
58 ArrayRef<int64_t> inputVecSizes = {},
59 ArrayRef<bool> inputVecScalableFlags = {},
60 bool flatten1DDepthwiseConv = false);
61
62/// Vectorize tensor::InsertSliceOp with:
63/// * vector::TransferReadOp + vector::TransferWriteOp
64/// The vector sizes are either:
65/// * user-provided in `inputVectorSizes`, or
66/// * inferred from the static dims in the input and output tensors.
67/// Bails out if:
68/// * vector sizes are not user-provided, and
69/// * at least one dim is dynamic (in both the input and output tensors),
70/// or if the strides are not 1.
71///
72/// Before:
73/// !t_in_type = tensor<1x2x3xf32>
74/// !t_out_type = tensor<9x8x7x1x2x3xf32>
75/// !v_type = vector<1x2x3xf32>
76/// %inserted_slice = tensor.insert_slice %src into %dest ... : !t_in_type
77/// into !t_out_type
78/// After:
79/// %read = vector.transfer_read %src[...], %pad ... : !t_in_type, !v_type
80/// %write = vector.transfer_write %read, %dest ... : !v_type, !t_out_type
81static LogicalResult
82vectorizeAsInsertSliceOp(RewriterBase &rewriter, tensor::InsertSliceOp sliceOp,
83 ArrayRef<int64_t> inputVectorSizes,
84 SmallVectorImpl<Value> &newResults);
85
86/// Returns the effective Pad value for the input op, provided it's a scalar.
87///
88/// Many Ops exhibit pad-like behaviour, but this isn't always explicit. If
89/// this Op performs padding, retrieve the padding value provided that it's
90/// a scalar and static/fixed for all the padded values. Returns an empty value
91/// otherwise.
92static Value getStaticPadVal(Operation *op);
93
94/// Helper function to extract the input slices after filter is unrolled along
95/// kw.
96static SmallVector<Value>
97extractConvInputSlices(RewriterBase &rewriter, Location loc, Value input,
98 int64_t nSize, int64_t wSize, int64_t cSize,
99 int64_t kwSize, int strideW, int dilationW,
100 int64_t wSizeStep, bool isSingleChanneled) {
101 SmallVector<Value> result;
102 if (isSingleChanneled) {
103 // Extract input slice of size {wSizeStep} @ [w + kw] for non-channeled
104 // convolution.
105 SmallVector<int64_t> sizes = {wSizeStep};
106 SmallVector<int64_t> strides = {1};
107 for (int64_t kw = 0; kw < kwSize; ++kw) {
108 for (int64_t w = 0; w < wSize; w += wSizeStep) {
109 result.push_back(Elt: vector::ExtractStridedSliceOp::create(
110 builder&: rewriter, location: loc, source: input, /*offsets=*/ArrayRef<int64_t>{w + kw}, sizes,
111 strides));
112 }
113 }
114 } else {
115 // Extract lhs slice of size {n, wSizeStep, c} @ [0, sw * w + dw * kw, 0]
116 // for channeled convolution.
117 SmallVector<int64_t> sizes = {nSize, wSizeStep, cSize};
118 SmallVector<int64_t> strides = {1, 1, 1};
119 for (int64_t kw = 0; kw < kwSize; ++kw) {
120 for (int64_t w = 0; w < wSize; w += wSizeStep) {
121 result.push_back(Elt: vector::ExtractStridedSliceOp::create(
122 builder&: rewriter, location: loc, source: input,
123 /*offsets=*/ArrayRef<int64_t>{0, w * strideW + kw * dilationW, 0},
124 sizes, strides));
125 }
126 }
127 }
128 return result;
129}
130
131/// Helper function to extract the filter slices after filter is unrolled along
132/// kw.
133static SmallVector<Value> extractConvFilterSlices(RewriterBase &rewriter,
134 Location loc, Value filter,
135 int64_t kwSize) {
136 SmallVector<Value> result;
137 // Extract rhs slice of size [{c, f} for channeled convolutions and {1} for
138 // non-chanelled convolution] @ [kw].
139 for (int64_t kw = 0; kw < kwSize; ++kw) {
140 result.push_back(Elt: vector::ExtractOp::create(
141 builder&: rewriter, location: loc, source: filter, /*offsets=*/position: ArrayRef<int64_t>{kw}));
142 }
143 return result;
144}
145
146/// Helper function to extract the result slices after filter is unrolled along
147/// kw.
148static SmallVector<Value>
149extractConvResultSlices(RewriterBase &rewriter, Location loc, Value res,
150 int64_t nSize, int64_t wSize, int64_t fSize,
151 int64_t wSizeStep, bool isSingleChanneled) {
152 SmallVector<Value> result;
153 if (isSingleChanneled) {
154 // Extract res slice: {wSizeStep} @ [w] for non-channeled convolution.
155 SmallVector<int64_t> sizes = {wSizeStep};
156 SmallVector<int64_t> strides = {1};
157 for (int64_t w = 0; w < wSize; w += wSizeStep) {
158 result.push_back(Elt: vector::ExtractStridedSliceOp::create(
159 builder&: rewriter, location: loc, source: res, /*offsets=*/ArrayRef<int64_t>{w}, sizes,
160 strides));
161 }
162 } else {
163 // Extract res slice: {n, wSizeStep, f} @ [0, w, 0] for channeled
164 // convolution.
165 SmallVector<int64_t> sizes = {nSize, wSizeStep, fSize};
166 SmallVector<int64_t> strides = {1, 1, 1};
167 for (int64_t w = 0; w < wSize; w += wSizeStep) {
168 result.push_back(Elt: vector::ExtractStridedSliceOp::create(
169 builder&: rewriter, location: loc, source: res, /*offsets=*/ArrayRef<int64_t>{0, w, 0}, sizes,
170 strides));
171 }
172 }
173 return result;
174}
175
176/// Helper function to insert the computed result slices.
177static Value insertConvResultSlices(RewriterBase &rewriter, Location loc,
178 Value res, int64_t wSize, int64_t wSizeStep,
179 SmallVectorImpl<Value> &resVals,
180 bool isSingleChanneled) {
181
182 if (isSingleChanneled) {
183 // Write back res slice: {wSizeStep} @ [w] for non-channeled convolution.
184 // This does not depend on kw.
185 SmallVector<int64_t> strides = {1};
186 for (int64_t w = 0; w < wSize; w += wSizeStep) {
187 res = vector::InsertStridedSliceOp::create(
188 builder&: rewriter, location: loc, valueToStore: resVals[w], dest: res, /*offsets=*/ArrayRef<int64_t>{w},
189 strides);
190 }
191 } else {
192 // Write back res slice: {n, wSizeStep, f} @ [0, w, 0] for channeled
193 // convolution. This does not depend on kw.
194 SmallVector<int64_t> strides = {1, 1, 1};
195 for (int64_t w = 0; w < wSize; w += wSizeStep) {
196 res = vector::InsertStridedSliceOp::create(
197 builder&: rewriter, location: loc, valueToStore: resVals[w], dest: res,
198 /*offsets=*/ArrayRef<int64_t>{0, w, 0}, strides);
199 }
200 }
201 return res;
202}
203
204/// Contains the vectorization state and related methods used across the
205/// vectorization process of a given operation.
206struct VectorizationState {
207 VectorizationState(RewriterBase &rewriter) : rewriterGuard(rewriter) {}
208
209 /// Initializes the vectorization state, including the computation of the
210 /// canonical vector shape for vectorization.
211 LogicalResult initState(RewriterBase &rewriter, LinalgOp linalgOp,
212 ArrayRef<int64_t> inputVectorSizes,
213 ArrayRef<bool> inputScalableVecDims,
214 bool assumeDynamicDimsMatchVecSizes = false);
215
216 /// Returns the canonical vector shape used to vectorize the iteration space.
217 ArrayRef<int64_t> getCanonicalVecShape() const { return canonicalVecShape; }
218
219 /// Returns the vector dimensions that are scalable in the canonical vector
220 /// shape.
221 ArrayRef<bool> getScalableVecDims() const { return scalableVecDims; }
222
223 /// Returns a vector type of the provided `elementType` with the canonical
224 /// vector shape and the corresponding fixed/scalable dimensions bit. If
225 /// `dimPermutation` is provided, the canonical vector dimensions are permuted
226 /// accordingly.
227 VectorType getCanonicalVecType(
228 Type elementType,
229 std::optional<AffineMap> dimPermutation = std::nullopt) const {
230 SmallVector<int64_t> vectorShape;
231 SmallVector<bool> scalableDims;
232 if (dimPermutation.has_value()) {
233 vectorShape =
234 applyPermutationMap<int64_t>(map: *dimPermutation, source: canonicalVecShape);
235 scalableDims =
236 applyPermutationMap<bool>(map: *dimPermutation, source: scalableVecDims);
237 } else {
238 vectorShape.append(in_start: canonicalVecShape.begin(), in_end: canonicalVecShape.end());
239 scalableDims.append(in_start: scalableVecDims.begin(), in_end: scalableVecDims.end());
240 }
241
242 return VectorType::get(shape: vectorShape, elementType, scalableDims);
243 }
244
245 /// Masks an operation with the canonical vector mask if the operation needs
246 /// masking. Returns the masked operation or the original operation if masking
247 /// is not needed. If provided, the canonical mask for this operation is
248 /// permuted using `maybeIndexingMap`.
249 Operation *
250 maskOperation(RewriterBase &rewriter, Operation *opToMask, LinalgOp linalgOp,
251 std::optional<AffineMap> maybeIndexingMap = std::nullopt);
252
253 /// Create or retrieve an existing mask value for the canonical vector
254 /// iteration space. If `maybeMaskingMap` the mask is permuted using that
255 /// permutation map. If a new mask is created, it will be cached for future
256 /// users. Returns a null value if no mask is needed.
257 Value
258 getOrCreateMaskFor(RewriterBase &rewriter, LinalgOp linalgOp,
259 std::optional<AffineMap> maybeMaskingMap = std::nullopt);
260
261private:
262 /// Initializes the iteration space static sizes using the Linalg op
263 /// information. This may become more complicated in the future.
264 void initIterSpaceStaticSizes(LinalgOp linalgOp) {
265 iterSpaceStaticSizes.append(RHS: linalgOp.getStaticLoopRanges());
266 }
267
268 /// Generates 'arith.constant' and 'tensor/memref.dim' operations for
269 /// all the static and dynamic dimensions of the iteration space to be
270 /// vectorized and store them in `iterSpaceValueSizes`.
271 LogicalResult precomputeIterSpaceValueSizes(RewriterBase &rewriter,
272 LinalgOp linalgOp);
273
274 /// Check whether this permutation map can be used for masking. At the
275 /// moment we only make sure that there are no broadcast dimensions, but this
276 /// might change if indexing maps evolve.
277 bool isValidMaskingMap(AffineMap maskingMap) {
278 return maskingMap.getBroadcastDims().empty();
279 }
280
281 /// Turn the input indexing map into a valid masking map.
282 ///
283 /// The input indexing map may contain "zero" results, e.g.:
284 /// (d0, d1, d2, d3) -> (d2, d1, d0, 0)
285 /// Applying such maps to canonical vector shapes like this one:
286 /// (1, 16, 16, 4)
287 /// would yield an invalid vector shape like this:
288 /// (16, 16, 1, 0)
289 /// Instead, drop the broadcasting dims that make no sense for masking perm.
290 /// maps:
291 /// (d0, d1, d2, d3) -> (d2, d1, d0)
292 /// This way, the corresponding vector/mask type will be:
293 /// vector<16x16x1xty>
294 /// rather than this invalid Vector type:
295 /// vector<16x16x1x0xty>
296 AffineMap getMaskingMapFromIndexingMap(AffineMap &indexingMap) {
297 return indexingMap.dropZeroResults();
298 }
299
300 // Holds the compile-time static sizes of the iteration space to vectorize.
301 // Dynamic dimensions are represented using ShapedType::kDynamic.
302 SmallVector<int64_t> iterSpaceStaticSizes;
303
304 /// Holds the value sizes of the iteration space to vectorize. Static
305 /// dimensions are represented by 'arith.constant' and dynamic
306 /// dimensions by 'tensor/memref.dim'.
307 SmallVector<Value> iterSpaceValueSizes;
308
309 /// Holds the canonical vector shape used to vectorize the iteration space.
310 SmallVector<int64_t> canonicalVecShape;
311
312 /// Holds the vector dimensions that are scalable in the canonical vector
313 /// shape.
314 SmallVector<bool> scalableVecDims;
315
316 /// Holds the active masks for permutations of the canonical vector iteration
317 /// space.
318 DenseMap<AffineMap, Value> activeMaskCache;
319
320 /// Global vectorization guard for the incoming rewriter. It's initialized
321 /// when the vectorization state is initialized.
322 OpBuilder::InsertionGuard rewriterGuard;
323
324 /// Do all dynamic dims match the corresponding vector sizes?
325 ///
326 /// When a dynamic tensor/memref dimension matches the corresponding vector
327 /// dimension, masking can be safely skipped, despite the presence of dynamic
328 /// shapes. Use this flag with care and only for cases where you are
329 /// confident the assumption holds.
330 bool assumeDynamicDimsMatchVecSizes = false;
331};
332
333LogicalResult
334VectorizationState::precomputeIterSpaceValueSizes(RewriterBase &rewriter,
335 LinalgOp linalgOp) {
336 // TODO: Support 0-d vectors.
337 for (int vecDim = 0, end = canonicalVecShape.size(); vecDim < end; ++vecDim) {
338 if (ShapedType::isStatic(dValue: iterSpaceStaticSizes[vecDim])) {
339 // Create constant index op for static dimensions.
340 iterSpaceValueSizes.push_back(Elt: arith::ConstantIndexOp::create(
341 builder&: rewriter, location: linalgOp.getLoc(), value: iterSpaceStaticSizes[vecDim]));
342 continue;
343 }
344
345 // Find an operand defined on this dimension of the iteration space to
346 // extract the runtime dimension size.
347 Value operand;
348 unsigned operandDimPos;
349 if (failed(Result: linalgOp.mapIterationSpaceDimToOperandDim(dimPos: vecDim, operand,
350 operandDimPos)))
351 return failure();
352
353 Value dynamicDim =
354 linalgOp.hasPureTensorSemantics()
355 ? (Value)tensor::DimOp::create(builder&: rewriter, location: linalgOp.getLoc(), source: operand,
356 index: operandDimPos)
357 : (Value)memref::DimOp::create(builder&: rewriter, location: linalgOp.getLoc(), source: operand,
358 index: operandDimPos);
359 iterSpaceValueSizes.push_back(Elt: dynamicDim);
360 }
361
362 return success();
363}
364
365/// Initializes the vectorization state, including the computation of the
366/// canonical vector shape for vectorization.
367// TODO: Move this to the constructor when we can remove the failure cases.
368LogicalResult VectorizationState::initState(RewriterBase &rewriter,
369 LinalgOp linalgOp,
370 ArrayRef<int64_t> inputVectorSizes,
371 ArrayRef<bool> inputScalableVecDims,
372 bool assumeDimsMatchVec) {
373 assumeDynamicDimsMatchVecSizes = assumeDimsMatchVec;
374 // Initialize the insertion point.
375 rewriter.setInsertionPoint(linalgOp);
376
377 if (!inputVectorSizes.empty()) {
378 // Get the canonical vector shape from the input vector sizes provided. This
379 // path should be taken to vectorize code with dynamic shapes and when using
380 // vector sizes greater than the iteration space sizes.
381 canonicalVecShape.append(in_start: inputVectorSizes.begin(), in_end: inputVectorSizes.end());
382 scalableVecDims.append(in_start: inputScalableVecDims.begin(),
383 in_end: inputScalableVecDims.end());
384 } else {
385 // Compute the canonical vector shape from the operation shape. If there are
386 // dynamic shapes, the operation won't be vectorized. We assume all the
387 // vector dimensions are fixed.
388 canonicalVecShape = linalgOp.getStaticLoopRanges();
389 scalableVecDims.append(NumInputs: linalgOp.getNumLoops(), Elt: false);
390 }
391
392 LDBG() << "Canonical vector shape: " << llvm::interleaved(R: canonicalVecShape);
393 LDBG() << "Scalable vector dims: " << llvm::interleaved(R: scalableVecDims);
394
395 if (ShapedType::isDynamicShape(dSizes: canonicalVecShape))
396 return failure();
397
398 // Initialize iteration space static sizes.
399 initIterSpaceStaticSizes(linalgOp);
400
401 // Generate 'arith.constant' and 'tensor/memref.dim' operations for
402 // all the static and dynamic dimensions of the iteration space, needed to
403 // compute a mask during vectorization.
404 if (failed(Result: precomputeIterSpaceValueSizes(rewriter, linalgOp)))
405 return failure();
406
407 return success();
408}
409
410Value VectorizationState::getOrCreateMaskFor(
411 RewriterBase &rewriter, LinalgOp linalgOp,
412 std::optional<AffineMap> maybeMaskingMap) {
413
414 assert((!maybeMaskingMap || isValidMaskingMap(*maybeMaskingMap)) &&
415 "Ill-formed masking map.");
416
417 // If no masking map was provided, use an identity map with the loop dims.
418 assert((!maybeMaskingMap || *maybeMaskingMap) &&
419 "Unexpected null mask permutation map");
420 AffineMap maskingMap =
421 maybeMaskingMap ? *maybeMaskingMap
422 : AffineMap::getMultiDimIdentityMap(
423 numDims: linalgOp.getNumLoops(), context: rewriter.getContext());
424
425 LDBG() << "Masking map: " << maskingMap;
426
427 // Return the active mask for the masking map of this operation if it was
428 // already created.
429 auto activeMaskIt = activeMaskCache.find(Val: maskingMap);
430 if (activeMaskIt != activeMaskCache.end()) {
431 Value mask = activeMaskIt->second;
432 LDBG() << "Reusing mask: " << mask;
433 return mask;
434 }
435
436 // Compute permuted projection of the iteration space to be masked and the
437 // corresponding mask shape. If the resulting iteration space dimensions are
438 // static and identical to the mask shape, masking is not needed for this
439 // operation.
440 // TODO: Improve this check. Only projected permutation indexing maps are
441 // supported.
442 SmallVector<int64_t> permutedStaticSizes =
443 applyPermutationMap<int64_t>(map: maskingMap, source: iterSpaceStaticSizes);
444 auto maskType = getCanonicalVecType(elementType: rewriter.getI1Type(), dimPermutation: maskingMap);
445 auto maskShape = maskType.getShape();
446
447 LDBG() << "Mask shape: " << llvm::interleaved(R: maskShape);
448
449 if (permutedStaticSizes == maskShape) {
450 LDBG() << "Masking is not needed for masking map: " << maskingMap;
451 activeMaskCache[maskingMap] = Value();
452 return Value();
453 }
454
455 if (assumeDynamicDimsMatchVecSizes) {
456 // While for _dynamic_ dim sizes we can _assume_ that the corresponding
457 // vector sizes match, we still need to check the _static_ dim sizes. Only
458 // then we can be 100% sure that masking is not required.
459 if (llvm::all_of(Range: llvm::zip(t&: permutedStaticSizes, u: maskType.getShape()),
460 P: [](auto it) {
461 return std::get<0>(it) == ShapedType::kDynamic
462 ? true
463 : std::get<0>(it) == std::get<1>(it);
464 })) {
465 LDBG()
466 << "Dynamic + static dimensions match vector sizes, masking is not "
467 "required.";
468 activeMaskCache[maskingMap] = Value();
469 return Value();
470 }
471 }
472
473 // Permute the iteration space value sizes to compute the mask upper bounds.
474 SmallVector<Value> upperBounds =
475 applyPermutationMap(map: maskingMap, source: ArrayRef<Value>(iterSpaceValueSizes));
476 assert(!maskShape.empty() && !upperBounds.empty() &&
477 "Masked 0-d vectors are not supported yet");
478
479 // Create the mask based on the dimension values.
480 Value mask = vector::CreateMaskOp::create(builder&: rewriter, location: linalgOp.getLoc(),
481 resultType0: maskType, mask_dim_sizes: upperBounds);
482 LDBG() << "Creating new mask: " << mask;
483 activeMaskCache[maskingMap] = mask;
484 return mask;
485}
486
487Operation *
488VectorizationState::maskOperation(RewriterBase &rewriter, Operation *opToMask,
489 LinalgOp linalgOp,
490 std::optional<AffineMap> maybeIndexingMap) {
491 LDBG() << "Trying to mask: " << *opToMask;
492
493 // No mask is needed if the operation is not maskable.
494 auto maskableOp = dyn_cast<vector::MaskableOpInterface>(Val: opToMask);
495 if (!maskableOp) {
496 LDBG() << "Operation is not maskable";
497 return opToMask;
498 }
499 assert(!maskableOp.isMasked() &&
500 "Masking an operation that is already masked");
501
502 std::optional<AffineMap> maybeMaskingMap = std::nullopt;
503 if (maybeIndexingMap)
504 maybeMaskingMap = getMaskingMapFromIndexingMap(indexingMap&: *maybeIndexingMap);
505
506 // Create or retrieve mask for this operation.
507 Value mask = getOrCreateMaskFor(rewriter, linalgOp, maybeMaskingMap);
508
509 if (!mask) {
510 LDBG() << "No mask required";
511 if (assumeDynamicDimsMatchVecSizes) {
512 llvm::TypeSwitch<Operation *>(opToMask)
513 .Case<vector::TransferReadOp, vector::TransferWriteOp>(
514 caseFn: [&](auto xferOp) {
515 // For vector.transfer_read and vector.transfer_write, there is
516 // also the `in-bounds` attribute that has to be set explicitly
517 // to true. Otherwise, "out-of-bounds" access will be assumed
518 // and masks will be generated while lowering these.
519 LDBG() << "Assuming dynamic dimensions match vector sizes and "
520 "setting their in-bounds to true!";
521 SmallVector<bool> inBoundsMap = xferOp.getInBoundsValues();
522 ShapedType xferType = xferOp.getShapedType();
523 AffineMap permMap = xferOp.getPermutationMap();
524 // Only set the in-bounds values to true for dynamic dims.
525 // Different mechanisms will set these accordingly for the
526 // static dims.
527 for (unsigned i = 0; i < xferOp.getTransferRank(); i++) {
528 auto dimExpr = dyn_cast<AffineDimExpr>(Val: permMap.getResult(idx: i));
529 // Skip broadcast dimensions.
530 if (!dimExpr)
531 continue;
532 unsigned pos = dimExpr.getPosition();
533 if (xferType.isDynamicDim(idx: pos))
534 inBoundsMap[i] = true;
535 }
536 rewriter.modifyOpInPlace(xferOp, [&]() {
537 xferOp.setInBoundsAttr(
538 rewriter.getBoolArrayAttr(values: inBoundsMap));
539 });
540 })
541 .Default(defaultFn: [](Operation *op) {
542 // No-op if the operation is not an xfer read or write.
543 });
544 }
545 return opToMask;
546 }
547
548 // Wrap the operation with a new `vector.mask` and update D-U chain.
549 assert(opToMask && "Expected a valid operation to mask");
550 auto maskOp = cast<vector::MaskOp>(
551 Val: mlir::vector::maskOperation(builder&: rewriter, maskableOp: opToMask, mask));
552 Operation *maskOpTerminator = &maskOp.getMaskRegion().front().back();
553
554 for (auto [resIdx, resVal] : llvm::enumerate(First: opToMask->getResults()))
555 rewriter.replaceAllUsesExcept(from: resVal, to: maskOp.getResult(i: resIdx),
556 exceptedUser: maskOpTerminator);
557
558 LDBG() << "Masked operation: " << *maskOp;
559 return maskOp;
560}
561
562/// Given an indexing `map` coming from a LinalgOp indexing, restricted to a
563/// projectedPermutation, compress the unused dimensions to serve as a
564/// permutation_map for a vector transfer operation.
565/// For example, given a linalg op such as:
566///
567/// ```
568/// %0 = linalg.generic {
569/// indexing_maps = affine_map<(d0, d1, d2, d3, d4) -> (d4, d0, d2)>,
570/// indexing_maps = affine_map<(d0, d1, d2, d3, d4) -> (d1, d3)>
571/// }
572/// ins(%0 : tensor<2x3x4xf32>)
573/// outs(%1 : tensor<5x6xf32>)
574/// ```
575///
576/// the iteration domain size of the linalg op is 3x5x4x6x2. The first affine
577/// map is reindexed to `affine_map<(d0, d1, d2) -> (d2, d0, d1)>`, the second
578/// affine map is reindexed to `affine_map<(d0, d1) -> (d0, d1)>`.
579static AffineMap reindexIndexingMap(AffineMap map) {
580 assert(map.isProjectedPermutation(/*allowZeroInResults=*/true) &&
581 "expected projected permutation");
582 auto res = compressUnusedDims(map);
583 assert(res.getNumDims() ==
584 (res.getNumResults() - res.getNumOfZeroResults()) &&
585 "expected reindexed map with same number of dims and results");
586 return res;
587}
588
589/// Helper enum to represent conv1d input traversal order.
590enum class Conv1DOpOrder {
591 W, // Corresponds to non-channeled 1D convolution operation.
592 Ncw, // Corresponds to operation that traverses the input in (n, c, w) order.
593 Nwc // Corresponds to operation that traverses the input in (n, w, c) order.
594};
595
596/// Helper data structure to represent the result of vectorization for a single
597/// operation. In certain specific cases, like terminators, we do not want to
598/// propagate.
599enum VectorizationHookStatus {
600 /// Op failed to vectorize.
601 Failure = 0,
602 /// Op vectorized and custom function took care of replacement logic
603 NoReplace,
604 /// Op vectorized into a new Op whose results will replace original Op's
605 /// results.
606 NewOp
607 // TODO: support values if Op vectorized to Many-Ops whose results we need to
608 // aggregate for replacement.
609};
610/// VectorizationHookResult contains the vectorized op returned from a
611/// CustomVectorizationHook. This is an internal implementation detail of
612/// linalg vectorization, not to be confused with VectorizationResult.
613struct VectorizationHookResult {
614 /// Return status from vectorizing the current op.
615 enum VectorizationHookStatus status = VectorizationHookStatus::Failure;
616 /// New vectorized operation to replace the current op.
617 /// Replacement behavior is specified by `status`.
618 Operation *newOp;
619};
620
621std::optional<vector::CombiningKind>
622mlir::linalg::getCombinerOpKind(Operation *combinerOp) {
623 using ::mlir::vector::CombiningKind;
624
625 if (!combinerOp)
626 return std::nullopt;
627 return llvm::TypeSwitch<Operation *, std::optional<CombiningKind>>(combinerOp)
628 .Case<arith::AddIOp, arith::AddFOp>(
629 caseFn: [&](auto op) { return CombiningKind::ADD; })
630 .Case(caseFn: [&](arith::AndIOp op) { return CombiningKind::AND; })
631 .Case(caseFn: [&](arith::MaxSIOp op) { return CombiningKind::MAXSI; })
632 .Case(caseFn: [&](arith::MaxUIOp op) { return CombiningKind::MAXUI; })
633 .Case(caseFn: [&](arith::MaximumFOp op) { return CombiningKind::MAXIMUMF; })
634 .Case(caseFn: [&](arith::MaxNumFOp op) { return CombiningKind::MAXNUMF; })
635 .Case(caseFn: [&](arith::MaximumNumFOp op) { return CombiningKind::MAXIMUMNUMF; })
636 .Case(caseFn: [&](arith::MinSIOp op) { return CombiningKind::MINSI; })
637 .Case(caseFn: [&](arith::MinUIOp op) { return CombiningKind::MINUI; })
638 .Case(caseFn: [&](arith::MinimumFOp op) { return CombiningKind::MINIMUMF; })
639 .Case(caseFn: [&](arith::MinNumFOp op) { return CombiningKind::MINNUMF; })
640 .Case(caseFn: [&](arith::MinimumNumFOp op) { return CombiningKind::MINIMUMNUMF; })
641 .Case<arith::MulIOp, arith::MulFOp>(
642 caseFn: [&](auto op) { return CombiningKind::MUL; })
643 .Case(caseFn: [&](arith::OrIOp op) { return CombiningKind::OR; })
644 .Case(caseFn: [&](arith::XOrIOp op) { return CombiningKind::XOR; })
645 .Default(std::nullopt);
646}
647
648/// Check whether `outputOperand` is a reduction with a single combiner
649/// operation. Return the combiner operation of the reduction. Return
650/// nullptr otherwise. Multiple reduction operations would impose an
651/// ordering between reduction dimensions and is currently unsupported in
652/// Linalg. This limitation is motivated by the fact that e.g. min(max(X)) !=
653/// max(min(X))
654// TODO: use in LinalgOp verification, there is a circular dependency atm.
655static Operation *matchLinalgReduction(OpOperand *outputOperand) {
656 auto linalgOp = cast<LinalgOp>(Val: outputOperand->getOwner());
657 unsigned outputPos =
658 outputOperand->getOperandNumber() - linalgOp.getNumDpsInputs();
659 // Only single combiner operations are supported for now.
660 SmallVector<Operation *, 4> combinerOps;
661 if (!matchReduction(iterCarriedArgs: linalgOp.getRegionOutputArgs(), redPos: outputPos, combinerOps) ||
662 combinerOps.size() != 1)
663 return nullptr;
664
665 // Return the combiner operation.
666 return combinerOps[0];
667}
668
669/// Broadcast `value` to a vector of `shape` if possible. Return value
670/// otherwise.
671static Value broadcastIfNeeded(OpBuilder &b, Value value, Type dstType) {
672 auto dstVecType = dyn_cast<VectorType>(Val&: dstType);
673 // If no shape to broadcast to, just return `value`.
674 if (dstVecType.getRank() == 0)
675 return value;
676 if (vector::isBroadcastableTo(srcType: value.getType(), dstVectorType: dstVecType) !=
677 vector::BroadcastableToResult::Success)
678 return value;
679 Location loc = b.getInsertionPoint()->getLoc();
680 return b.createOrFold<vector::BroadcastOp>(location: loc, args&: dstVecType, args&: value);
681}
682
683/// Create MultiDimReductionOp to compute the reduction for `reductionOp`. This
684/// assumes that `reductionOp` has two operands and one of them is the reduction
685/// initial value.buildMultiDimReduce
686// Note: this is a true builder that notifies the OpBuilder listener.
687// TODO: Consider moving as a static helper on the ReduceOp.
688static Operation *buildMultiDimReduce(OpBuilder &b, Operation *reduceOp,
689 Value valueToReduce, Value acc,
690 ArrayRef<bool> dimsToMask) {
691 auto maybeKind = getCombinerOpKind(combinerOp: reduceOp);
692 assert(maybeKind && "Failed precondition: could not get reduction kind");
693 // Keep the combiner's fast-math flags on the reduction.
694 arith::FastMathFlags fastMathFlags = arith::FastMathFlags::none;
695 if (auto fmfOp = dyn_cast<arith::ArithFastMathInterface>(Val: reduceOp))
696 fastMathFlags = fmfOp.getFastMathFlagsAttr().getValue();
697 return vector::MultiDimReductionOp::create(builder&: b, location: reduceOp->getLoc(),
698 source: valueToReduce, acc, reductionMask: dimsToMask,
699 kind: *maybeKind, fastMathFlags);
700}
701
702static SmallVector<bool> getDimsToReduce(LinalgOp linalgOp) {
703 return llvm::map_to_vector(C: linalgOp.getIteratorTypesArray(),
704 F&: isReductionIterator);
705}
706
707/// Check if `op` is a linalg.reduce or a linalg.generic that has at least one
708/// reduction iterator.
709static bool hasReductionIterator(LinalgOp &op) {
710 return isa<linalg::ReduceOp>(Val: op) ||
711 (isa<linalg::GenericOp>(Val: op) &&
712 llvm::any_of(Range: op.getIteratorTypesArray(), P: isReductionIterator));
713}
714
715/// Build a vector.transfer_write of `value` into `outputOperand` at indices set
716/// to all `0`; where `outputOperand` is an output operand of the LinalgOp
717/// currently being vectorized. If `dest` has null rank, build an memref.store.
718/// Return the produced value or null if no value is produced.
719// Note: this is a true builder that notifies the OpBuilder listener.
720// TODO: Consider moving as a static helper on the ReduceOp.
721static Value buildVectorWrite(RewriterBase &rewriter, Value value,
722 OpOperand *outputOperand,
723 VectorizationState &state) {
724 Location loc = value.getLoc();
725 auto linalgOp = cast<LinalgOp>(Val: outputOperand->getOwner());
726 AffineMap opOperandMap = linalgOp.getMatchingIndexingMap(opOperand: outputOperand);
727
728 // Compute the vector type of the value to store. This type should be an
729 // identity or projection of the canonical vector type without any permutation
730 // applied, given that any permutation in a transfer write happens as part of
731 // the write itself.
732 AffineMap vectorTypeMap = AffineMap::getFilteredIdentityMap(
733 ctx: opOperandMap.getContext(), numDims: opOperandMap.getNumInputs(),
734 keepDimFilter: [&](AffineDimExpr dimExpr) -> bool {
735 return llvm::is_contained(Range: opOperandMap.getResults(), Element: dimExpr);
736 });
737 auto vectorType = state.getCanonicalVecType(
738 elementType: getElementTypeOrSelf(type: outputOperand->get().getType()), dimPermutation: vectorTypeMap);
739
740 SmallVector<Value> indices(linalgOp.getRank(opOperand: outputOperand),
741 arith::ConstantIndexOp::create(builder&: rewriter, location: loc, value: 0));
742
743 Operation *write;
744 if (vectorType.getRank() > 0) {
745 AffineMap writeMap = inversePermutation(map: reindexIndexingMap(map: opOperandMap));
746 value = broadcastIfNeeded(b&: rewriter, value, dstType: vectorType);
747 assert(value.getType() == vectorType && "Incorrect type");
748 write = vector::TransferWriteOp::create(
749 builder&: rewriter, location: loc, vector: value, dest: outputOperand->get(), indices, permutationMap: writeMap);
750 } else {
751 // 0-d case is still special: do not invert the reindexing writeMap.
752 if (!isa<VectorType>(Val: value.getType()))
753 value = vector::BroadcastOp::create(builder&: rewriter, location: loc, result: vectorType, source: value);
754 assert(value.getType() == vectorType && "Incorrect type");
755 write = vector::TransferWriteOp::create(builder&: rewriter, location: loc, vector: value,
756 dest: outputOperand->get(), indices);
757 }
758
759 write = state.maskOperation(rewriter, opToMask: write, linalgOp, maybeIndexingMap: opOperandMap);
760
761 // If masked, set in-bounds to true. Masking guarantees that the access will
762 // be in-bounds.
763 if (auto maskOp = dyn_cast<vector::MaskingOpInterface>(Val: write)) {
764 auto maskedWriteOp = cast<vector::TransferWriteOp>(Val: maskOp.getMaskableOp());
765 SmallVector<bool> inBounds(maskedWriteOp.getVectorType().getRank(), true);
766 maskedWriteOp.setInBoundsAttr(rewriter.getBoolArrayAttr(values: inBounds));
767 }
768
769 LDBG() << "vectorized op: " << *write;
770 if (!write->getResults().empty())
771 return write->getResult(idx: 0);
772 return Value();
773}
774
775// Custom vectorization precondition function type. This is intented to be used
776// with CustomVectorizationHook. Returns success if the corresponding custom
777// hook can vectorize the op.
778using CustomVectorizationPrecondition =
779 std::function<LogicalResult(Operation *, bool)>;
780
781// Custom vectorization function type. Produce a vector form of Operation*
782// assuming all its vectorized operands are already in the IRMapping.
783// Return nullptr if the Operation cannot be vectorized.
784using CustomVectorizationHook =
785 std::function<VectorizationHookResult(Operation *, const IRMapping &)>;
786
787/// Helper function to vectorize the terminator of a `linalgOp`. New result
788/// vector values are appended to `newResults`. Return
789/// VectorizationHookStatus::NoReplace to signal the vectorization algorithm
790/// that it should not try to map produced operations and instead return the
791/// results using the `newResults` vector making them available to the
792/// vectorization algorithm for RAUW. This function is meant to be used as a
793/// CustomVectorizationHook.
794static VectorizationHookResult
795vectorizeLinalgYield(RewriterBase &rewriter, Operation *op,
796 const IRMapping &bvm, VectorizationState &state,
797 LinalgOp linalgOp, SmallVectorImpl<Value> &newResults) {
798 auto yieldOp = dyn_cast<linalg::YieldOp>(Val: op);
799 if (!yieldOp)
800 return VectorizationHookResult{.status: VectorizationHookStatus::Failure, .newOp: nullptr};
801 for (const auto &output : llvm::enumerate(First: yieldOp.getValues())) {
802 // TODO: Scan for an opportunity for reuse.
803 // TODO: use a map.
804 Value vectorValue = bvm.lookup(from: output.value());
805 Value newResult =
806 buildVectorWrite(rewriter, value: vectorValue,
807 outputOperand: linalgOp.getDpsInitOperand(i: output.index()), state);
808 if (newResult)
809 newResults.push_back(Elt: newResult);
810 }
811
812 return VectorizationHookResult{.status: VectorizationHookStatus::NoReplace, .newOp: nullptr};
813}
814
815/// Helper function to vectorize the index operations of a `linalgOp`. Return
816/// VectorizationHookStatus::NewOp to signal the vectorization algorithm that it
817/// should map the produced operations. This function is meant to be used as a
818/// CustomVectorizationHook.
819static VectorizationHookResult vectorizeLinalgIndex(RewriterBase &rewriter,
820 VectorizationState &state,
821 Operation *op,
822 LinalgOp linalgOp) {
823 IndexOp indexOp = dyn_cast<linalg::IndexOp>(Val: op);
824 if (!indexOp)
825 return VectorizationHookResult{.status: VectorizationHookStatus::Failure, .newOp: nullptr};
826 auto loc = indexOp.getLoc();
827 // Compute the static loop sizes of the index op.
828 ArrayRef<int64_t> targetShape = state.getCanonicalVecShape();
829 auto dim = indexOp.getDim();
830 // Compute a one-dimensional index vector for the index op dimension.
831 auto indexVectorType =
832 VectorType::get(shape: {targetShape[dim]}, elementType: rewriter.getIndexType(),
833 scalableDims: state.getScalableVecDims()[dim]);
834 auto indexSteps = vector::StepOp::create(builder&: rewriter, location: loc, result: indexVectorType);
835 // Return the one-dimensional index vector if it lives in the trailing
836 // dimension of the iteration space since the vectorization algorithm in this
837 // case can handle the broadcast.
838 if (dim == targetShape.size() - 1)
839 return VectorizationHookResult{.status: VectorizationHookStatus::NewOp, .newOp: indexSteps};
840 // Otherwise permute the targetShape to move the index dimension last,
841 // broadcast the one-dimensional index vector to the permuted shape, and
842 // finally transpose the broadcasted index vector to undo the permutation.
843 auto permPattern =
844 llvm::to_vector(Range: llvm::seq<unsigned>(Begin: 0, End: targetShape.size()));
845 std::swap(a&: permPattern[dim], b&: permPattern.back());
846 auto permMap =
847 AffineMap::getPermutationMap(permutation: permPattern, context: linalgOp.getContext());
848
849 auto broadCastOp = vector::BroadcastOp::create(
850 builder&: rewriter, location: loc,
851 result: state.getCanonicalVecType(elementType: rewriter.getIndexType(), dimPermutation: permMap), source: indexSteps);
852 SmallVector<int64_t> transposition =
853 llvm::to_vector<16>(Range: llvm::seq<int64_t>(Begin: 0, End: linalgOp.getNumLoops()));
854 std::swap(a&: transposition.back(), b&: transposition[dim]);
855 auto transposeOp =
856 vector::TransposeOp::create(builder&: rewriter, location: loc, vector: broadCastOp, permutation: transposition);
857 return VectorizationHookResult{.status: VectorizationHookStatus::NewOp, .newOp: transposeOp};
858}
859
860/// Helper function to check if the tensor.extract can be vectorized by the
861/// custom hook vectorizeTensorExtract.
862static LogicalResult
863tensorExtractVectorizationPrecondition(Operation *op, bool vectorizeNDExtract) {
864 tensor::ExtractOp extractOp = dyn_cast<tensor::ExtractOp>(Val: op);
865 if (!extractOp)
866 return failure();
867
868 if (extractOp.getIndices().size() != 1 && !vectorizeNDExtract)
869 return failure();
870
871 // Check the index type, but only for non 0-d tensors (for which we do need
872 // access indices).
873 if (not extractOp.getIndices().empty()) {
874 if (!VectorType::isValidElementType(t: extractOp.getIndices()[0].getType()))
875 return failure();
876 }
877
878 if (!llvm::all_of(Range: extractOp->getResultTypes(),
879 P: VectorType::isValidElementType)) {
880 return failure();
881 }
882
883 return success();
884}
885
886/// Calculates the offsets (`$index_vec`) for `vector.gather` operations
887/// generated from `tensor.extract`. The offset is calculated as follows
888/// (example using scalar values):
889///
890/// offset = extractOp.indices[0]
891/// for (i = 1; i < numIndices; i++)
892/// offset = extractOp.dimSize[i] * offset + extractOp.indices[i];
893///
894/// For tensor<45 x 80 x 15 x f32> and index [1, 2, 3], this leads to:
895/// offset = ( ( 1 ) * 80 + 2 ) * 15 + 3
896static Value calculateGatherOffset(RewriterBase &rewriter,
897 VectorizationState &state,
898 tensor::ExtractOp extractOp,
899 const IRMapping &bvm) {
900 // The vector of indices for GatherOp should be shaped as the output vector.
901 auto indexVecType = state.getCanonicalVecType(elementType: rewriter.getIndexType());
902 auto loc = extractOp.getLoc();
903
904 Value offset = broadcastIfNeeded(
905 b&: rewriter, value: bvm.lookup(from: extractOp.getIndices()[0]), dstType: indexVecType);
906
907 const size_t numIndices = extractOp.getIndices().size();
908 for (size_t i = 1; i < numIndices; i++) {
909 Value dimIdx = arith::ConstantIndexOp::create(builder&: rewriter, location: loc, value: i);
910
911 auto dimSize = broadcastIfNeeded(
912 b&: rewriter,
913 value: tensor::DimOp::create(builder&: rewriter, location: loc, source: extractOp.getTensor(), index: dimIdx),
914 dstType: indexVecType);
915
916 offset = arith::MulIOp::create(builder&: rewriter, location: loc, lhs: offset, rhs: dimSize);
917
918 auto extractOpIndex = broadcastIfNeeded(
919 b&: rewriter, value: bvm.lookup(from: extractOp.getIndices()[i]), dstType: indexVecType);
920
921 offset = arith::AddIOp::create(builder&: rewriter, location: loc, lhs: extractOpIndex, rhs: offset);
922 }
923
924 return offset;
925}
926
927enum VectorMemoryAccessKind { ScalarBroadcast, Contiguous, Gather };
928
929/// Find the index of the trailing non-unit dim in linalgOp. This hook is used
930/// when checking whether `tensor.extract` Op (within a `linalg.generic` Op)
931/// represents a contiguous load operation.
932///
933/// Note that when calling this hook, it is assumed that the output vector is
934/// effectively 1D. Other cases (i.e. reading n-D vectors) should've been
935/// labelled as a gather load before entering this method.
936///
937/// Following on from the above, it is assumed that:
938/// * for statically shaped loops, when no masks are used, only one dim is !=
939/// 1 (that's what the shape of the output vector is based on).
940/// * for dynamically shaped loops, there might be more non-unit dims
941/// as the output vector type is user-specified.
942///
943/// TODO: Statically shaped loops + vector masking
944static uint64_t getTrailingNonUnitLoopDimIdx(LinalgOp linalgOp) {
945 SmallVector<int64_t> loopRanges = linalgOp.getStaticLoopRanges();
946 assert(
947 (linalgOp.hasDynamicShape() ||
948 llvm::count_if(loopRanges, [](int64_t dim) { return dim != 1; }) == 1) &&
949 "For statically shaped Linalg Ops, only one "
950 "non-unit loop dim is expected");
951 assert(!loopRanges.empty() && "Empty loops, nothing to analyse.");
952
953 size_t idx = loopRanges.size() - 1;
954 for (; idx != 0; idx--)
955 if (loopRanges[idx] != 1)
956 break;
957
958 return idx;
959}
960
961/// Checks whether `val` can be used for calculating a loop invariant index.
962static bool isLoopInvariantIdx(LinalgOp &linalgOp, Value &val,
963 VectorType resType) {
964
965 assert(((llvm::count_if(resType.getShape(),
966 [](int64_t dimSize) { return dimSize > 1; }) == 1)) &&
967 "n-D vectors are not yet supported");
968
969 auto *block = linalgOp.getBlock();
970
971 // A shared DAG has exponentially many paths; a revisit adds nothing.
972 SmallPtrSet<Operation *, 8> visited;
973 SmallVector<Value> worklist{val};
974
975 while (!worklist.empty()) {
976 Value v = worklist.pop_back_val();
977
978 // Blocks outside _this_ linalg.generic are effectively loop invariant.
979 // However, analysing block arguments for _this_ linalg.generic Op is a bit
980 // tricky. Just bail out in the latter case.
981 // TODO: We could try analysing the corresponding affine map here.
982 if (isa<BlockArgument>(Val: v)) {
983 if (llvm::is_contained(Range: block->getArguments(), Element: v))
984 return false;
985 continue;
986 }
987
988 Operation *defOp = v.getDefiningOp();
989 assert(defOp && "This is neither a block argument nor an operation result");
990
991 // IndexOp is loop invariant as long as its result remains constant across
992 // iterations. Note that for dynamic shapes, the corresponding dim will also
993 // be conservatively treated as != 1.
994 if (auto indexOp = dyn_cast<linalg::IndexOp>(Val: defOp)) {
995 if (linalgOp.getStaticLoopRanges()[indexOp.getDim()] != 1)
996 return false;
997 continue;
998 }
999
1000 auto *ancestor = block->findAncestorOpInBlock(op&: *defOp);
1001
1002 // Values define outside `linalgOp` are loop invariant.
1003 if (!ancestor)
1004 continue;
1005
1006 // Values defined inside `linalgOp`, which are constant, are loop invariant.
1007 if (isa<arith::ConstantOp>(Val: ancestor))
1008 continue;
1009
1010 if (visited.insert(Ptr: ancestor).second)
1011 llvm::append_range(C&: worklist, R: ancestor->getOperands());
1012 }
1013
1014 return true;
1015}
1016
1017/// Check whether `val` could be used for calculating the trailing index for a
1018/// contiguous load operation.
1019///
1020/// There are currently 3 types of values that are allowed here:
1021/// 1. loop-invariant values,
1022/// 2. values that increment by 1 with every loop iteration,
1023/// 3. results of basic arithmetic operations (linear and continuous)
1024/// involving 1., 2. and 3.
1025/// This method returns True if indeed only such values are used in calculating
1026/// `val.`
1027///
1028/// Additionally, the trailing index for a contiguous load operation should
1029/// increment by 1 with every loop iteration, i.e. be based on:
1030/// * `linalg.index <dim>` ,
1031/// where <dim> is the trailing non-unit dim of the iteration space (this way,
1032/// `linalg.index <dim>` increments by 1 with every loop iteration).
1033/// `foundIndexOp` is updated to `true` when such Op is found.
1034static bool isContiguousLoadIdx(LinalgOp &linalgOp, Value &val,
1035 bool &foundIndexOp, VectorType resType) {
1036
1037 assert(((llvm::count_if(resType.getShape(),
1038 [](int64_t dimSize) { return dimSize > 1; }) == 1)) &&
1039 "n-D vectors are not yet supported");
1040
1041 // Blocks outside _this_ linalg.generic are effectively loop invariant.
1042 // However, analysing block arguments for _this_ linalg.generic Op is a bit
1043 // tricky. Just bail out in the latter case.
1044 // TODO: We could try analysing the corresponding affine map here.
1045 auto *block = linalgOp.getBlock();
1046 if (isa<BlockArgument>(Val: val))
1047 return !llvm::is_contained(Range: block->getArguments(), Element: val);
1048
1049 Operation *defOp = val.getDefiningOp();
1050 assert(defOp && "This is neither a block argument nor an operation result");
1051
1052 if (auto indexOp = dyn_cast<linalg::IndexOp>(Val: defOp)) {
1053 auto loopDimThatIncrementsByOne = getTrailingNonUnitLoopDimIdx(linalgOp);
1054
1055 foundIndexOp = (indexOp.getDim() == loopDimThatIncrementsByOne);
1056 return true;
1057 }
1058
1059 auto *ancestor = block->findAncestorOpInBlock(op&: *defOp);
1060
1061 if (!ancestor)
1062 return false;
1063
1064 // Conservatively reject Ops that could lead to indices with stride other
1065 // than 1.
1066 if (!isa<arith::AddIOp, arith::ConstantOp, linalg::IndexOp>(Val: ancestor))
1067 return false;
1068
1069 bool result = false;
1070 for (auto op : ancestor->getOperands())
1071 result |= isContiguousLoadIdx(linalgOp, val&: op, foundIndexOp, resType);
1072
1073 return result;
1074}
1075
1076/// Infer the memory access pattern for the input ExtractOp
1077///
1078/// Based on the ExtratOp result shape and the access indices, decides whether
1079/// this Op corresponds to a contiguous load (including a broadcast of a scalar)
1080/// or a gather load. When analysing the ExtractOp indices (to identify
1081/// contiguous laods), this method looks for "loop" invariant indices (e.g.
1082/// block arguments) and indices that change linearly (e.g. via `linalg.index`
1083/// Op).
1084///
1085/// Note that it is always safe to use gather load operations for contiguous
1086/// loads (albeit slow), but not vice-versa. When in doubt, bail out and assume
1087/// that `extractOp` is a gather load.
1088static VectorMemoryAccessKind
1089getTensorExtractMemoryAccessPattern(tensor::ExtractOp extractOp,
1090 LinalgOp &linalgOp, VectorType resType) {
1091
1092 auto inputShape = cast<ShapedType>(Val: extractOp.getTensor().getType());
1093
1094 // 0. Is this a 0-D vector? If yes then this is a scalar broadcast.
1095 if (inputShape.getShape().empty())
1096 return VectorMemoryAccessKind::ScalarBroadcast;
1097
1098 // 0a. Is the result a 0-D vector? If yes, there are no iteration dimensions
1099 // so the tensor.extract is a single scalar load regardless of the index.
1100 if (resType.getRank() == 0)
1101 return VectorMemoryAccessKind::ScalarBroadcast;
1102
1103 // True for vectors that are effectively 1D, e.g. `vector<1x4x1xi32>`, false
1104 // otherwise.
1105 bool isOutput1DVector =
1106 (llvm::count_if(Range: resType.getShape(),
1107 P: [](int64_t dimSize) { return dimSize > 1; }) == 1);
1108 // 1. Assume that it's a gather load when reading non-1D vector.
1109 if (!isOutput1DVector)
1110 return VectorMemoryAccessKind::Gather;
1111
1112 bool leadingIdxsLoopInvariant = true;
1113
1114 // 2. Analyze the leading indices of `extractOp`.
1115 // Look at the way each index is calculated and decide whether it is suitable
1116 // for a contiguous load, i.e. whether it's loop invariant. If not, it's a
1117 // gather load.
1118 auto indices = extractOp.getIndices();
1119 auto leadIndices = indices.drop_back(n: 1);
1120
1121 for (auto [i, indexVal] : llvm::enumerate(First&: leadIndices)) {
1122 if (inputShape.getShape()[i] == 1)
1123 continue;
1124
1125 leadingIdxsLoopInvariant &= isLoopInvariantIdx(linalgOp, val&: indexVal, resType);
1126 }
1127
1128 if (!leadingIdxsLoopInvariant) {
1129 LDBG() << "Found gather load: " << extractOp;
1130 return VectorMemoryAccessKind::Gather;
1131 }
1132
1133 // 3. Analyze the trailing index for `extractOp`.
1134 // At this point we know that the leading indices are loop invariant. This
1135 // means that is potentially a scalar or a contiguous load. We can decide
1136 // based on the trailing idx.
1137 auto extractOpTrailingIdx = indices.back();
1138
1139 // 3a. Scalar broadcast load
1140 // If the trailing index is loop invariant then this is a scalar load.
1141 if (leadingIdxsLoopInvariant &&
1142 isLoopInvariantIdx(linalgOp, val&: extractOpTrailingIdx, resType)) {
1143 LDBG() << "Found scalar broadcast load: " << extractOp;
1144
1145 return VectorMemoryAccessKind::ScalarBroadcast;
1146 }
1147
1148 // 3b. Contiguous loads
1149 // The trailing `extractOp` index should increment with every loop iteration.
1150 // This effectively means that it must be based on the trailing loop index.
1151 // This is what the following bool captures.
1152 bool foundIndexOp = false;
1153 bool isContiguousLoad = isContiguousLoadIdx(linalgOp, val&: extractOpTrailingIdx,
1154 foundIndexOp, resType);
1155 // TODO: Support generating contiguous loads for column vectors - that will
1156 // require adding a permutation map to tranfer_read Ops.
1157 bool isRowVector = resType.getShape().back() != 1;
1158 isContiguousLoad &= (foundIndexOp && isRowVector);
1159
1160 if (isContiguousLoad) {
1161 LDBG() << "Found contigous load: " << extractOp;
1162 return VectorMemoryAccessKind::Contiguous;
1163 }
1164
1165 // 4. Fallback case - gather load.
1166 LDBG() << "Found gather load: " << extractOp;
1167 return VectorMemoryAccessKind::Gather;
1168}
1169
1170/// Helper function to vectorize the tensor.extract operations. Returns
1171/// VectorizationHookStatus::NewOp to signal the vectorization algorithm that it
1172/// should map the produced operations. This function is meant to be used as a
1173/// CustomVectorizationHook.
1174static VectorizationHookResult
1175vectorizeTensorExtract(RewriterBase &rewriter, VectorizationState &state,
1176 Operation *op, LinalgOp linalgOp, const IRMapping &bvm) {
1177 tensor::ExtractOp extractOp = dyn_cast<tensor::ExtractOp>(Val: op);
1178 if (!extractOp)
1179 return VectorizationHookResult{.status: VectorizationHookStatus::Failure, .newOp: nullptr};
1180 auto loc = extractOp.getLoc();
1181
1182 // Compute the static loop sizes of the extract op.
1183 auto resultType = state.getCanonicalVecType(elementType: extractOp.getResult().getType());
1184 auto maskConstantOp = arith::ConstantOp::create(
1185 builder&: rewriter, location: loc,
1186 value: DenseIntElementsAttr::get(type: state.getCanonicalVecType(elementType: rewriter.getI1Type()),
1187 /*value=*/arg: true));
1188 auto passThruConstantOp = arith::ConstantOp::create(
1189 builder&: rewriter, location: loc, value: rewriter.getZeroAttr(type: resultType));
1190
1191 // Base indices are currently set to 0. We will need to re-visit if more
1192 // generic scenarios are to be supported.
1193 SmallVector<Value> baseIndices(
1194 extractOp.getIndices().size(),
1195 arith::ConstantIndexOp::create(builder&: rewriter, location: loc, value: 0));
1196
1197 VectorMemoryAccessKind memAccessKind =
1198 getTensorExtractMemoryAccessPattern(extractOp, linalgOp, resType: resultType);
1199
1200 // 1. Handle gather access
1201 if (memAccessKind == VectorMemoryAccessKind::Gather) {
1202 Value offset = calculateGatherOffset(rewriter, state, extractOp, bvm);
1203
1204 // vector.gather is not maskable, so the iteration space mask (if any) is
1205 // passed as its mask operand.
1206 Value mask = state.getOrCreateMaskFor(rewriter, linalgOp);
1207 if (!mask)
1208 mask = maskConstantOp;
1209
1210 // Generate the gather load
1211 Operation *gatherOp = vector::GatherOp::create(
1212 builder&: rewriter, location: loc, resultType, base: extractOp.getTensor(), indices: baseIndices, index_vec: offset,
1213 mask, passthrough: passThruConstantOp);
1214
1215 LDBG() << "Vectorised as gather load: " << extractOp;
1216 return VectorizationHookResult{.status: VectorizationHookStatus::NewOp, .newOp: gatherOp};
1217 }
1218
1219 // 2. Handle:
1220 // a. scalar loads + broadcast,
1221 // b. contiguous loads.
1222 // Both cases use vector.transfer_read.
1223
1224 // Collect indices for `vector.transfer_read`. At this point, the indices will
1225 // either be scalars or would have been broadcast to vectors matching the
1226 // result type. For indices that are vectors, there are two options:
1227 // * for non-trailing indices, all elements are identical (contiguous
1228 // loads are identified by looking for non-trailing indices that are
1229 // invariant with respect to the corresponding linalg.generic), or
1230 // * for trailing indices, the index vector will contain values with stride
1231 // one, but for `vector.transfer_read` only the first (i.e. 0th) index is
1232 // needed.
1233 // This means that
1234 // * for scalar indices - just re-use it,
1235 // * for vector indices (e.g. `vector<1x1x4xindex>`) - extract the bottom
1236 // (0th) element and use that.
1237 SmallVector<Value> transferReadIdxs;
1238 for (size_t i = 0; i < extractOp.getIndices().size(); i++) {
1239 Value idx = bvm.lookup(from: extractOp.getIndices()[i]);
1240 if (idx.getType().isIndex()) {
1241 transferReadIdxs.push_back(Elt: idx);
1242 continue;
1243 }
1244
1245 auto indexAs1dVector = vector::ShapeCastOp::create(
1246 builder&: rewriter, location: loc,
1247 result: VectorType::get(shape: resultType.getShape().back(), elementType: rewriter.getIndexType(),
1248 scalableDims: resultType.getScalableDims().back()),
1249 source: idx);
1250 transferReadIdxs.push_back(
1251 Elt: vector::ExtractOp::create(builder&: rewriter, location: loc, source: indexAs1dVector, position: 0));
1252 }
1253
1254 // `tensor.extract_element` is always in-bounds, hence the following holds.
1255 auto dstRank = resultType.getRank();
1256 auto srcRank = extractOp.getTensor().getType().getRank();
1257 SmallVector<bool> inBounds(dstRank, true);
1258
1259 // 2a. Handle scalar broadcast access.
1260 if (memAccessKind == VectorMemoryAccessKind::ScalarBroadcast) {
1261 MLIRContext *ctx = rewriter.getContext();
1262 SmallVector<AffineExpr> exprs(dstRank, getAffineConstantExpr(constant: 0, context: ctx));
1263 auto permutationMap = AffineMap::get(dimCount: srcRank, symbolCount: 0, results: exprs, context: ctx);
1264
1265 auto transferReadOp = vector::TransferReadOp::create(
1266 builder&: rewriter, location: loc, vectorType: resultType, source: extractOp.getTensor(), indices: transferReadIdxs,
1267 /*padding=*/std::nullopt, permutationMap, inBounds);
1268
1269 Operation *readOrMaskedReadOp = transferReadOp;
1270 if (dstRank > 0) {
1271 // Mask this broadcasting xfer_read here rather than relying on the
1272 // generic path (the generic path assumes identity masking map, which
1273 // wouldn't be valid here).
1274 SmallVector<int64_t> readMaskShape = {1};
1275 auto readMaskType = VectorType::get(shape: readMaskShape, elementType: rewriter.getI1Type());
1276 auto allTrue = vector::ConstantMaskOp::create(
1277 builder&: rewriter, location: loc, type: readMaskType, kind: vector::ConstantMaskKind::AllTrue);
1278 readOrMaskedReadOp =
1279 mlir::vector::maskOperation(builder&: rewriter, maskableOp: transferReadOp, mask: allTrue);
1280 }
1281
1282 LDBG() << "Vectorised as scalar broadcast load: " << extractOp;
1283 return VectorizationHookResult{.status: VectorizationHookStatus::NewOp,
1284 .newOp: readOrMaskedReadOp};
1285 }
1286
1287 // 2b. Handle contiguous access.
1288 auto permutationMap = AffineMap::getMinorIdentityMap(
1289 dims: srcRank, results: std::min(a: dstRank, b: srcRank), context: rewriter.getContext());
1290
1291 int32_t rankDiff = dstRank - srcRank;
1292 // When dstRank > srcRank, broadcast the source tensor to the unitary leading
1293 // dims so that the ranks match. This is done by extending the map with 0s.
1294 // For example, for dstRank = 3, srcRank = 2, the following map created
1295 // above:
1296 // (d0, d1) --> (d0, d1)
1297 // is extended as:
1298 // (d0, d1) --> (0, d0, d1)
1299 while (rankDiff > 0) {
1300 permutationMap = permutationMap.insertResult(
1301 expr: mlir::getAffineConstantExpr(constant: 0, context: rewriter.getContext()), pos: 0);
1302 rankDiff--;
1303 }
1304
1305 auto transferReadOp = vector::TransferReadOp::create(
1306 builder&: rewriter, location: loc, vectorType: resultType, source: extractOp.getTensor(), indices: transferReadIdxs,
1307 /*padding=*/std::nullopt, permutationMap, inBounds);
1308
1309 // Mask this contiguous xfer_read here rather than relying on the generic
1310 // path (the generic path assumes an identity masking map over all the loop
1311 // dims, which wouldn't be valid here). A contiguous load only reads the
1312 // trailing `min(dstRank, srcRank)` dims of the iteration space - the leading
1313 // dims are broadcast via `permutationMap` above - so its inferred mask is
1314 // rank-reduced. Build a masking map that projects the iteration space onto
1315 // exactly those trailing dims so the created mask matches the xfer_read.
1316 int64_t numReadDims = std::min(a: dstRank, b: srcRank);
1317 auto maskingMap = AffineMap::getMinorIdentityMap(
1318 dims: linalgOp.getNumLoops(), results: numReadDims, context: rewriter.getContext());
1319 Operation *maskedReadOp =
1320 state.maskOperation(rewriter, opToMask: transferReadOp, linalgOp, maybeIndexingMap: maskingMap);
1321
1322 LDBG() << "Vectorised as contiguous load: " << extractOp;
1323 return VectorizationHookResult{.status: VectorizationHookStatus::NewOp, .newOp: maskedReadOp};
1324}
1325
1326/// Emit reduction operations if the shapes of the value to reduce is different
1327/// that the result shape.
1328// Note: this is a true builder that notifies the OpBuilder listener.
1329// TODO: Consider moving as a static helper on the ReduceOp.
1330static Operation *reduceIfNeeded(OpBuilder &b, LinalgOp linalgOp, Operation *op,
1331 Value reduceValue, Value initialValue,
1332 const IRMapping &bvm) {
1333 Value reduceVec = bvm.lookup(from: reduceValue);
1334 Value outputVec = bvm.lookup(from: initialValue);
1335 auto reduceType = dyn_cast<VectorType>(Val: reduceVec.getType());
1336 auto outputType = dyn_cast<VectorType>(Val: outputVec.getType());
1337 // Reduce only if needed as the value may already have been reduce for
1338 // contraction vectorization.
1339 if (!reduceType ||
1340 (outputType && reduceType.getShape() == outputType.getShape()))
1341 return nullptr;
1342 SmallVector<bool> dimsToMask = getDimsToReduce(linalgOp);
1343 return buildMultiDimReduce(b, reduceOp: op, valueToReduce: reduceVec, acc: outputVec, dimsToMask);
1344}
1345
1346/// Generic vectorization for a single operation `op`, given already vectorized
1347/// operands carried by `bvm`. Vectorization occurs as follows:
1348/// 1. Try to apply any of the `customVectorizationHooks` and return its
1349/// result on success.
1350/// 2. Clone any constant in the current scope without vectorization: each
1351/// consumer of the constant will later determine the shape to which the
1352/// constant needs to be broadcast to.
1353/// 3. Fail on any remaining non `ElementwiseMappable` op. It is the purpose
1354/// of the `customVectorizationHooks` to cover such cases.
1355/// 4. Clone `op` in vector form to a vector of shape prescribed by the first
1356/// operand of maximal rank. Other operands have smaller rank and are
1357/// broadcast accordingly. It is assumed this broadcast is always legal,
1358/// otherwise, it means one of the `customVectorizationHooks` is incorrect.
1359///
1360/// This function assumes all operands of `op` have been vectorized and are in
1361/// the `bvm` mapping. As a consequence, this function is meant to be called on
1362/// a topologically-sorted list of ops.
1363/// This function does not update `bvm` but returns a VectorizationHookStatus
1364/// that instructs the caller what `bvm` update needs to occur.
1365static VectorizationHookResult
1366vectorizeOneOp(RewriterBase &rewriter, VectorizationState &state,
1367 LinalgOp linalgOp, Operation *op, const IRMapping &bvm,
1368 ArrayRef<CustomVectorizationHook> customVectorizationHooks) {
1369 LDBG() << "vectorize op " << *op;
1370
1371 // 1. Try to apply any CustomVectorizationHook.
1372 if (!customVectorizationHooks.empty()) {
1373 for (auto &customFunc : customVectorizationHooks) {
1374 VectorizationHookResult result = customFunc(op, bvm);
1375 if (result.status == VectorizationHookStatus::Failure)
1376 continue;
1377 return result;
1378 }
1379 }
1380
1381 // 2. Constant ops don't get vectorized but rather broadcasted at their users.
1382 // Clone so that the constant is not confined to the linalgOp block .
1383 if (isa<arith::ConstantOp, func::ConstantOp>(Val: op))
1384 return VectorizationHookResult{.status: VectorizationHookStatus::NewOp,
1385 .newOp: rewriter.clone(op&: *op)};
1386
1387 // 3. Only ElementwiseMappable are allowed in the generic vectorization.
1388 if (!OpTrait::hasElementwiseMappableTraits(op))
1389 return VectorizationHookResult{.status: VectorizationHookStatus::Failure, .newOp: nullptr};
1390
1391 // 4 . Check if the operation is a reduction.
1392 SmallVector<std::pair<Value, Value>> reductionOperands;
1393 for (Value operand : op->getOperands()) {
1394 auto blockArg = dyn_cast<BlockArgument>(Val&: operand);
1395 if (!blockArg || blockArg.getOwner() != linalgOp.getBlock() ||
1396 blockArg.getArgNumber() < linalgOp.getNumDpsInputs())
1397 continue;
1398 SmallVector<Operation *> reductionOps;
1399 Value reduceValue = matchReduction(
1400 iterCarriedArgs: linalgOp.getRegionOutputArgs(),
1401 redPos: blockArg.getArgNumber() - linalgOp.getNumDpsInputs(), combinerOps&: reductionOps);
1402 if (!reduceValue)
1403 continue;
1404 reductionOperands.push_back(Elt: std::make_pair(x&: reduceValue, y&: operand));
1405 }
1406 if (!reductionOperands.empty()) {
1407 assert(reductionOperands.size() == 1);
1408 Operation *reduceOp =
1409 reduceIfNeeded(b&: rewriter, linalgOp, op, reduceValue: reductionOperands[0].first,
1410 initialValue: reductionOperands[0].second, bvm);
1411 if (reduceOp)
1412 return VectorizationHookResult{.status: VectorizationHookStatus::NewOp, .newOp: reduceOp};
1413 }
1414
1415 // 5. Generic vectorization path for ElementwiseMappable ops.
1416 // a. Get the first max ranked shape.
1417 VectorType firstMaxRankedType;
1418 for (Value operand : op->getOperands()) {
1419 auto vecOperand = bvm.lookup(from: operand);
1420 assert(vecOperand && "Vector operand couldn't be found");
1421
1422 auto vecType = dyn_cast<VectorType>(Val: vecOperand.getType());
1423 if (vecType && (!firstMaxRankedType ||
1424 firstMaxRankedType.getRank() < vecType.getRank()))
1425 firstMaxRankedType = vecType;
1426 }
1427 // b. Broadcast each op if needed.
1428 SmallVector<Value> vecOperands;
1429 for (Value scalarOperand : op->getOperands()) {
1430 Value vecOperand = bvm.lookup(from: scalarOperand);
1431 assert(vecOperand && "Vector operand couldn't be found");
1432
1433 if (firstMaxRankedType) {
1434 auto vecType = VectorType::get(shape: firstMaxRankedType.getShape(),
1435 elementType: getElementTypeOrSelf(type: vecOperand.getType()),
1436 scalableDims: firstMaxRankedType.getScalableDims());
1437 vecOperands.push_back(Elt: broadcastIfNeeded(b&: rewriter, value: vecOperand, dstType: vecType));
1438 } else {
1439 vecOperands.push_back(Elt: vecOperand);
1440 }
1441 }
1442 // c. for elementwise, the result is the vector with the firstMaxRankedShape
1443 SmallVector<Type> resultTypes;
1444 for (Type resultType : op->getResultTypes()) {
1445 resultTypes.push_back(
1446 Elt: firstMaxRankedType
1447 ? VectorType::get(shape: firstMaxRankedType.getShape(), elementType: resultType,
1448 scalableDims: firstMaxRankedType.getScalableDims())
1449 : resultType);
1450 }
1451 // d. Build and return the new op.
1452 Operation *newOp = Operation::create(
1453 location: op->getLoc(), name: op->getName(), resultTypes, operands: vecOperands,
1454 attributes: op->getDiscardableAttrDictionary(), properties: op->getPropertiesStorage(),
1455 /*successors=*/{}, /*numRegions=*/0);
1456 return VectorizationHookResult{.status: VectorizationHookStatus::NewOp,
1457 .newOp: rewriter.insert(op: newOp)};
1458}
1459
1460/// Generic vectorization function that rewrites the body of a `linalgOp` into
1461/// vector form. Generic vectorization proceeds as follows:
1462/// 1. Verify the `linalgOp` has one non-empty region.
1463/// 2. Values defined above the region are mapped to themselves and will be
1464/// broadcasted on a per-need basis by their consumers.
1465/// 3. Each region argument is vectorized into a vector.transfer_read (or 0-d
1466/// load).
1467/// TODO: Reuse opportunities for RAR dependencies.
1468/// 4a. Register CustomVectorizationHook for YieldOp to capture the results.
1469/// 4rewriter. Register CustomVectorizationHook for IndexOp to access the
1470/// iteration indices.
1471/// 5. Iteratively call vectorizeOneOp on the region operations.
1472///
1473/// When `broadcastToMaximalCommonShape` is set to true, eager broadcasting is
1474/// performed to the maximal common vector size implied by the `linalgOp`
1475/// iteration space. This eager broadcasting is introduced in the
1476/// permutation_map of the vector.transfer_read operations. The eager
1477/// broadcasting makes it trivial to determine where broadcast, transposes and
1478/// reductions should occur, without any bookkeeping. The tradeoff is that, in
1479/// the absence of good canonicalizations, the amount of work increases.
1480/// This is not deemed a problem as we expect canonicalizations and foldings to
1481/// aggressively clean up the useless work.
1482static LogicalResult
1483vectorizeAsLinalgGeneric(RewriterBase &rewriter, VectorizationState &state,
1484 LinalgOp linalgOp,
1485 SmallVectorImpl<Value> &newResults) {
1486 LDBG() << "Vectorizing operation as linalg generic/n";
1487 Block *block = linalgOp.getBlock();
1488
1489 // 2. Values defined above the region can only be broadcast for now. Make them
1490 // map to themselves.
1491 IRMapping bvm;
1492 SetVector<Value> valuesSet;
1493 mlir::getUsedValuesDefinedAbove(regions: linalgOp->getRegion(index: 0), values&: valuesSet);
1494 bvm.map(from: valuesSet.getArrayRef(), to: valuesSet.getArrayRef());
1495
1496 if (linalgOp.getNumDpsInits() == 0)
1497 return failure();
1498
1499 // 3. Turn all BBArgs into vector.transfer_read / load.
1500 Location loc = linalgOp.getLoc();
1501 Value zero = arith::ConstantIndexOp::create(builder&: rewriter, location: loc, value: 0);
1502 for (OpOperand *opOperand : linalgOp.getOpOperandsMatchingBBargs()) {
1503 BlockArgument bbarg = linalgOp.getMatchingBlockArgument(opOperand);
1504 if (linalgOp.isScalar(opOperand)) {
1505 bvm.map(from: bbarg, to: opOperand->get());
1506 continue;
1507 }
1508
1509 // 3.a. Convert the indexing map for this input/output to a transfer read
1510 // permutation map and masking map.
1511 AffineMap indexingMap = linalgOp.getMatchingIndexingMap(opOperand);
1512
1513 AffineMap readMap;
1514 VectorType readType;
1515 Type elemType = getElementTypeOrSelf(val: opOperand->get());
1516 if (linalgOp.isDpsInput(opOperand)) {
1517 // 3.a.i. For input reads we use the canonical vector shape.
1518 readMap = inverseAndBroadcastProjectedPermutation(map: indexingMap);
1519 readType = state.getCanonicalVecType(elementType: elemType);
1520 } else {
1521 // 3.a.ii. For output reads (iteration-carried dependence, e.g.,
1522 // reductions), the vector shape is computed by mapping the canonical
1523 // vector shape to the output domain and back to the canonical domain.
1524 readMap = inversePermutation(map: reindexIndexingMap(map: indexingMap));
1525 readType =
1526 state.getCanonicalVecType(elementType: elemType, dimPermutation: readMap.compose(map: indexingMap));
1527 }
1528
1529 SmallVector<Value> indices(linalgOp.getShape(opOperand).size(), zero);
1530
1531 Operation *read = vector::TransferReadOp::create(
1532 builder&: rewriter, location: loc, vectorType: readType, source: opOperand->get(), indices,
1533 /*padding=*/std::nullopt, permutationMap: readMap);
1534 read = state.maskOperation(rewriter, opToMask: read, linalgOp, maybeIndexingMap: indexingMap);
1535 Value readValue = read->getResult(idx: 0);
1536
1537 // 3.b. If masked, set in-bounds to true. Masking guarantees that the access
1538 // will be in-bounds.
1539 if (auto maskOp = dyn_cast<vector::MaskingOpInterface>(Val: read)) {
1540 SmallVector<bool> inBounds(readType.getRank(), true);
1541 cast<vector::TransferReadOp>(Val: maskOp.getMaskableOp())
1542 .setInBoundsAttr(rewriter.getBoolArrayAttr(values: inBounds));
1543 }
1544
1545 // 3.c. Not all ops support 0-d vectors, extract the scalar for now.
1546 // TODO: remove this.
1547 if (readType.getRank() == 0)
1548 readValue = vector::ExtractOp::create(builder&: rewriter, location: loc, source: readValue,
1549 position: ArrayRef<int64_t>());
1550
1551 LDBG() << "New vectorized bbarg(" << bbarg.getArgNumber()
1552 << "): " << readValue;
1553 bvm.map(from: bbarg, to: readValue);
1554 bvm.map(from: opOperand->get(), to: readValue);
1555 }
1556
1557 SmallVector<CustomVectorizationHook> hooks;
1558 // 4a. Register CustomVectorizationHook for yieldOp.
1559 CustomVectorizationHook vectorizeYield =
1560 [&](Operation *op, const IRMapping &bvm) -> VectorizationHookResult {
1561 return vectorizeLinalgYield(rewriter, op, bvm, state, linalgOp, newResults);
1562 };
1563 hooks.push_back(Elt: vectorizeYield);
1564
1565 // 4b. Register CustomVectorizationHook for indexOp.
1566 CustomVectorizationHook vectorizeIndex =
1567 [&](Operation *op, const IRMapping &bvm) -> VectorizationHookResult {
1568 return vectorizeLinalgIndex(rewriter, state, op, linalgOp);
1569 };
1570 hooks.push_back(Elt: vectorizeIndex);
1571
1572 // 4c. Register CustomVectorizationHook for extractOp.
1573 CustomVectorizationHook vectorizeExtract =
1574 [&](Operation *op, const IRMapping &bvm) -> VectorizationHookResult {
1575 return vectorizeTensorExtract(rewriter, state, op, linalgOp, bvm);
1576 };
1577 hooks.push_back(Elt: vectorizeExtract);
1578
1579 // 5. Iteratively call `vectorizeOneOp` to each op in the slice.
1580 for (Operation &op : block->getOperations()) {
1581 VectorizationHookResult result =
1582 vectorizeOneOp(rewriter, state, linalgOp, op: &op, bvm, customVectorizationHooks: hooks);
1583 if (result.status == VectorizationHookStatus::Failure) {
1584 LDBG() << "failed to vectorize: " << op;
1585 return failure();
1586 }
1587 if (result.status == VectorizationHookStatus::NewOp) {
1588 Operation *maybeMaskedOp =
1589 state.maskOperation(rewriter, opToMask: result.newOp, linalgOp);
1590 LDBG() << "New vector op: " << *maybeMaskedOp;
1591 bvm.map(from: op.getResults(), to: maybeMaskedOp->getResults());
1592 }
1593 }
1594
1595 return success();
1596}
1597
1598/// Given the re-associations, "collapses" the input Vector type
1599///
1600/// This is similar to CollapseShapeOp::inferCollapsedType with two notable
1601/// differences:
1602/// * We can safely assume that there are no dynamic sizes.
1603/// * Scalable flags are updated alongside regular dims.
1604///
1605/// When collapsing scalable flags, conservatively avoids cases with two
1606/// scalable dims. We could re-visit this in the future.
1607///
1608/// EXAMPLE:
1609/// type = vector<4x16x[8]x16xf32>
1610/// reassociation = [(d0, d1, d2, d3) -> (d0, d1),
1611/// (d0, d1, d2, d3) -> (d2, d3)]
1612/// Result:
1613/// vector<64x[128]xf32>
1614static VectorType getCollapsedVecType(VectorType type,
1615 ArrayRef<AffineMap> reassociation) {
1616 assert(type.getNumScalableDims() < 2 &&
1617 "Collapsing more than 1 scalable dim is not supported ATM");
1618
1619 // Use the fact that reassociation is valid to simplify the logic: only use
1620 // each map's rank.
1621 assert(isReassociationValid(reassociation) && "invalid reassociation");
1622
1623 auto shape = type.getShape();
1624 auto scalableFlags = type.getScalableDims();
1625 SmallVector<int64_t> newShape;
1626 SmallVector<bool> newScalableFlags;
1627
1628 unsigned currentDim = 0;
1629 for (AffineMap m : reassociation) {
1630 unsigned dim = m.getNumResults();
1631 int64_t size = 1;
1632 bool flag = false;
1633 for (unsigned d = 0; d < dim; ++d) {
1634 size *= shape[currentDim + d];
1635 flag |= scalableFlags[currentDim + d];
1636 }
1637 newShape.push_back(Elt: size);
1638 newScalableFlags.push_back(Elt: flag);
1639 currentDim += dim;
1640 }
1641
1642 return VectorType::get(shape: newShape, elementType: type.getElementType(), scalableDims: newScalableFlags);
1643}
1644
1645/// Vectorize `linalg.pack` as:
1646/// * xfer_read -> shape_cast -> transpose -> xfer_write
1647///
1648/// The input-vector-sizes specify the _write_ vector sizes (i.e. the vector
1649/// sizes for the xfer_write operation). This is sufficient to infer the other
1650/// vector sizes required here.
1651///
1652/// If the vector sizes are not provided:
1653/// * the vector sizes are determined from the destination tensor static shape.
1654///
1655/// EXAMPLE (no vector sizes):
1656/// ```
1657/// %pack = tensor.pack %src
1658/// inner_dims_pos = [2, 1]
1659/// inner_tiles = [16, 2]
1660/// into %dst : tensor<32x8x16xf32> -> tensor<32x4x1x16x2xf32>
1661/// ``
1662/// is vectorizes as:
1663/// ```
1664/// %read = vector.transfer_read %src
1665/// : tensor<32x7x16xf32>, vector<32x8x16xf32>
1666/// %sc = vector.shape_cast %read
1667/// : vector<32x8x16xf32> to vector<32x4x2x1x16xf32>
1668/// %tr = vector.transpose %sc, [0, 1, 3, 4, 2]
1669/// : vector<32x4x2x1x16xf32> to vector<32x4x1x16x2xf32>
1670/// %write = vector.transfer_write %tr into %dest
1671/// : vector<32x4x1x16x2xf32>, tensor<32x4x1x16x2xf32>
1672/// ```
1673static LogicalResult
1674vectorizeAsTensorPackOp(RewriterBase &rewriter, linalg::PackOp packOp,
1675 ArrayRef<int64_t> inputVectorSizes,
1676 SmallVectorImpl<Value> &newResults) {
1677 if (!inputVectorSizes.empty()) {
1678 assert(inputVectorSizes.size() == packOp.getDestRank() &&
1679 "Invalid number of input vector sizes!");
1680 }
1681
1682 // TODO: Introduce a parent class that will handle the insertion point update.
1683 OpBuilder::InsertionGuard g(rewriter);
1684 rewriter.setInsertionPoint(packOp);
1685
1686 Location loc = packOp.getLoc();
1687 std::optional<Value> padValue = packOp.getPaddingValue()
1688 ? std::optional(packOp.getPaddingValue())
1689 : std::nullopt;
1690
1691 SmallVector<int64_t> destShape =
1692 SmallVector<int64_t>(packOp.getDestType().getShape());
1693
1694 // This is just a convenience alias to clearly communicate that the input
1695 // vector sizes determine the _write_ sizes.
1696 ArrayRef<int64_t> &writeVectorSizes = inputVectorSizes;
1697
1698 // In the absence of input-vector-sizes, use the _static_ input tensor shape.
1699 if (writeVectorSizes.empty()) {
1700 if (ShapedType::isDynamicShape(dSizes: destShape))
1701 return rewriter.notifyMatchFailure(arg&: packOp,
1702 msg: "unable to infer vector sizes");
1703
1704 writeVectorSizes = destShape;
1705 }
1706
1707 // Compute pre-transpose-write-vector-type, i.e. the write vector type
1708 // _before_ the transposition (i.e. before dimension permutation). This is
1709 // done by inverting the permutation/transposition that's part of the Pack
1710 // operation. This type is required to:
1711 // 1) compute the read vector type for masked-read below, and
1712 // 2) generate shape-cast Op below that expands the read vector type.
1713 PackingMetadata packMetadata;
1714 SmallVector<int64_t> preTransposeWriteVecSizses(writeVectorSizes);
1715 auto destInvPermutation = getPackInverseDestPerm(packOp, metadata&: packMetadata);
1716 applyPermutationToVector(inVec&: preTransposeWriteVecSizses, permutation: destInvPermutation);
1717 auto preTransposeWriteVecType =
1718 VectorType::get(shape: preTransposeWriteVecSizses,
1719 elementType: packOp.getResult().getType().getElementType());
1720
1721 // Compute vector type for the _read_ opeartion. This is simply
1722 // pre-transpose-write-vector-type with the dimensions collapsed
1723 // as per the Pack operation.
1724 VectorType readVecType = getCollapsedVecType(
1725 type: preTransposeWriteVecType,
1726 reassociation: getSymbolLessAffineMaps(reassociation: convertReassociationIndicesToExprs(
1727 context: rewriter.getContext(), reassociationIndices: packMetadata.reassociations)));
1728
1729 // Create masked TransferReadOp.
1730 auto maskedRead = vector::createReadOrMaskedRead(
1731 builder&: rewriter, loc, source: packOp.getSource(), vecToReadTy: readVecType, padValue);
1732
1733 // Create ShapeCastOp.
1734 auto shapeCastOp = vector::ShapeCastOp::create(
1735 builder&: rewriter, location: loc, result: preTransposeWriteVecType, source: maskedRead);
1736
1737 // Create TransposeOp.
1738 auto destPermutation = invertPermutationVector(permutation: destInvPermutation);
1739 auto transposeOp = vector::TransposeOp::create(
1740 builder&: rewriter, location: loc, vector: shapeCastOp.getResult(), permutation: destPermutation);
1741
1742 // Create TransferWriteOp.
1743 Operation *write = vector::createWriteOrMaskedWrite(
1744 builder&: rewriter, loc, vecToStore: transposeOp.getResult(), dest: packOp.getDest());
1745 newResults.push_back(Elt: write->getResult(idx: 0));
1746 return success();
1747}
1748
1749/// Vectorize `linalg.unpack` as:
1750/// * xfer_read -> vector.transpose -> vector.shape_cast -> xfer_write
1751///
1752/// The input-vector-sizes specify the _read_ vector sizes (i.e. the vector
1753/// sizes for the xfer_read operation). This is sufficient to infer the other
1754/// vector sizes required here.
1755///
1756/// If the vector sizes are not provided:
1757/// * the vector sizes are determined from the input tensor static shape.
1758///
1759/// EXAMPLE (no vector sizes):
1760/// ```
1761/// %unpack = linalg.unpack %src
1762/// inner_dims_pos = [0, 1]
1763/// inner_tiles = [8, 8]
1764/// into %dest : tensor<1x1x8x8xf32> -> tensor<8x8xf32>
1765/// ```
1766/// is vectorized as:
1767/// ```
1768/// %read = vector.transfer_read %src
1769/// : tensor<1x1x8x8xf32>, vector<1x1x8x8xf32>
1770/// %tr = vector.transpose %read, [0, 2, 1, 3]
1771/// : vector<1x1x8x8xf32> to vector<1x8x1x8xf32>
1772/// %sc = vector.shape_cast %tr
1773/// : vector<1x8x1x8xf32> to vector<8x8xf32>
1774/// %vector = vector.transfer_write %sc into %dest
1775/// : vector<8x8xf32>, tensor<8x8xf32>
1776/// ```
1777static LogicalResult
1778vectorizeAsTensorUnpackOp(RewriterBase &rewriter, linalg::UnPackOp unpackOp,
1779 ArrayRef<int64_t> inputVectorSizes,
1780 ArrayRef<bool> inputScalableVecDims,
1781 SmallVectorImpl<Value> &newResults) {
1782 if (!inputVectorSizes.empty()) {
1783 assert(inputVectorSizes.size() == unpackOp.getSourceRank() &&
1784 "Invalid number of input vector sizes!");
1785 assert(inputVectorSizes.size() == inputScalableVecDims.size() &&
1786 "Incompatible number of vector sizes and vector scalable flags!");
1787 }
1788
1789 // TODO: Introduce a parent class that will handle the insertion point update.
1790 OpBuilder::InsertionGuard g(rewriter);
1791 rewriter.setInsertionPoint(unpackOp);
1792
1793 ShapedType unpackTensorType = unpackOp.getSourceType();
1794
1795 ArrayRef<int64_t> sourceShape = unpackTensorType.getShape();
1796
1797 Location loc = unpackOp->getLoc();
1798
1799 // Obtain vector sizes for the read operation.
1800 SmallVector<int64_t> readVectorSizes(inputVectorSizes);
1801 SmallVector<bool> readScalableVectorFlags(inputScalableVecDims);
1802
1803 // In the absence of input-vector-sizes, use the _static_ input tensor shape.
1804 if (inputVectorSizes.empty()) {
1805 if (ShapedType::isDynamicShape(dSizes: sourceShape))
1806 return rewriter.notifyMatchFailure(arg&: unpackOp,
1807 msg: "Unable to infer vector sizes!");
1808
1809 readVectorSizes.assign(in_start: sourceShape.begin(), in_end: sourceShape.end());
1810 }
1811
1812 // -- Generate the read operation --
1813 VectorType readVecType =
1814 VectorType::get(shape: readVectorSizes, elementType: unpackTensorType.getElementType(),
1815 scalableDims: readScalableVectorFlags);
1816 Value readResult = vector::createReadOrMaskedRead(
1817 builder&: rewriter, loc, source: unpackOp.getSource(), vecToReadTy: readVecType, padValue: std::nullopt);
1818
1819 // -- Generate the transpose operation --
1820 PackingMetadata packMetadata;
1821 SmallVector<int64_t> lastDimToInsertPosPerm =
1822 getUnPackInverseSrcPerm(unpackOp, metadata&: packMetadata);
1823 vector::TransposeOp transposeOp = vector::TransposeOp::create(
1824 builder&: rewriter, location: loc, vector: readResult, permutation: lastDimToInsertPosPerm);
1825
1826 // -- Generate the shape_cast operation --
1827 VectorType collapsedVecType = getCollapsedVecType(
1828 type: transposeOp.getType(),
1829 reassociation: getSymbolLessAffineMaps(reassociation: convertReassociationIndicesToExprs(
1830 context: rewriter.getContext(), reassociationIndices: packMetadata.reassociations)));
1831 vector::ShapeCastOp shapeCastOp = vector::ShapeCastOp::create(
1832 builder&: rewriter, location: loc, result: collapsedVecType, source: transposeOp->getResult(idx: 0));
1833
1834 // -- Generate the write operation --
1835 Operation *write = vector::createWriteOrMaskedWrite(
1836 builder&: rewriter, loc, vecToStore: shapeCastOp.getResult(), dest: unpackOp.getDest());
1837
1838 newResults.push_back(Elt: write->getResult(idx: 0));
1839 return success();
1840}
1841
1842/// Vectorize a `padOp` with (1) static result type, (2) constant padding value
1843/// and (3) all-zero lowPad to
1844/// `transfer_write_in_bounds(transfer_read_masked(pad_source, pad_value))`.
1845static LogicalResult
1846vectorizeAsTensorPadOp(RewriterBase &rewriter, tensor::PadOp padOp,
1847 ArrayRef<int64_t> inputVectorSizes,
1848 SmallVectorImpl<Value> &newResults) {
1849 auto padValue = padOp.getConstantPaddingValue();
1850 Location loc = padOp.getLoc();
1851
1852 // TODO: Introduce a parent class that will handle the insertion point update.
1853 OpBuilder::InsertionGuard g(rewriter);
1854 rewriter.setInsertionPoint(padOp);
1855
1856 ReifiedRankedShapedTypeDims reifiedReturnShapes;
1857 LogicalResult status =
1858 cast<ReifyRankedShapedTypeOpInterface>(Val: padOp.getOperation())
1859 .reifyResultShapes(builder&: rewriter, reifiedReturnShapes);
1860 (void)status; // prevent unused variable warning on non-assert builds
1861 assert(succeeded(status) && "failed to reify result shapes");
1862 auto readType = VectorType::get(shape: inputVectorSizes, elementType: padValue.getType());
1863 auto maskedRead = vector::createReadOrMaskedRead(
1864 builder&: rewriter, loc, source: padOp.getSource(), vecToReadTy: readType, padValue,
1865 /*useInBoundsInsteadOfMasking=*/false);
1866
1867 // Create Xfer write Op
1868 Value dest = tensor::EmptyOp::create(builder&: rewriter, location: loc, sizes: reifiedReturnShapes[0],
1869 elementType: padOp.getResultType().getElementType());
1870 Operation *write =
1871 vector::createWriteOrMaskedWrite(builder&: rewriter, loc, vecToStore: maskedRead, dest);
1872 newResults.push_back(Elt: write->getResult(idx: 0));
1873 return success();
1874}
1875
1876// TODO: probably need some extra checks for reduction followed by consumer
1877// ops that may not commute (e.g. linear reduction + non-linear instructions).
1878static LogicalResult reductionPreconditions(LinalgOp op) {
1879 if (llvm::none_of(Range: op.getIteratorTypesArray(), P: isReductionIterator)) {
1880 LDBG() << "reduction precondition failed: no reduction iterator";
1881 return failure();
1882 }
1883 for (OpOperand &opOperand : op.getDpsInitsMutable()) {
1884 AffineMap indexingMap = op.getMatchingIndexingMap(opOperand: &opOperand);
1885 if (indexingMap.isPermutation())
1886 continue;
1887
1888 Operation *reduceOp = matchLinalgReduction(outputOperand: &opOperand);
1889 if (!reduceOp || !getCombinerOpKind(combinerOp: reduceOp)) {
1890 LDBG() << "reduction precondition failed: reduction detection failed";
1891 return failure();
1892 }
1893 }
1894 return success();
1895}
1896
1897static LogicalResult
1898vectorizeDynamicConvOpPrecondition(linalg::LinalgOp conv,
1899 bool flatten1DDepthwiseConv) {
1900 if (flatten1DDepthwiseConv) {
1901 LDBG() << "Vectorization of flattened convs with dynamic shapes is not "
1902 "supported";
1903 return failure();
1904 }
1905
1906 if (!isaConvolutionOpOfType<linalg::DepthwiseConv1DNwcWcOp>(op: conv)) {
1907 LDBG() << "Not a 1D depth-wise WC conv, dynamic shapes are not supported";
1908 return failure();
1909 }
1910
1911 // Support dynamic shapes in 1D depthwise convolution, but only in the
1912 // _channel_ dimension.
1913 Value lhs = conv.getDpsInputOperand(i: 0)->get();
1914 ArrayRef<int64_t> lhsShape = cast<ShapedType>(Val: lhs.getType()).getShape();
1915 auto shapeWithoutCh = lhsShape.drop_back(N: 1);
1916 if (ShapedType::isDynamicShape(dSizes: shapeWithoutCh)) {
1917 LDBG() << "Dynamically-shaped op vectorization precondition failed: only "
1918 "channel dim can be dynamic";
1919 return failure();
1920 }
1921
1922 return success();
1923}
1924
1925static LogicalResult
1926vectorizeDynamicLinalgOpPrecondition(linalg::LinalgOp op,
1927 bool flatten1DDepthwiseConv) {
1928 if (isaConvolutionOpInterface(linalgOp: op))
1929 return vectorizeDynamicConvOpPrecondition(conv: op, flatten1DDepthwiseConv);
1930
1931 if (hasReductionIterator(op))
1932 return reductionPreconditions(op);
1933
1934 // TODO: Masking only supports dynamic element-wise ops, linalg.generic ops,
1935 // linalg.copy ops and ops that implement ContractionOpInterface for now.
1936 if (!isElementwise(op) &&
1937 !isa<linalg::GenericOp, linalg::CopyOp, linalg::ContractionOpInterface>(
1938 Val: op.getOperation()))
1939 return failure();
1940
1941 LDBG() << "Dynamically-shaped op meets vectorization pre-conditions";
1942 return success();
1943}
1944
1945//// This hook considers two cases:
1946/// (1) If the input-vector-sizes are empty, then the vector sizes will be
1947/// infered. This is only possible when all shapes are static.
1948/// (2) If the input-vector-sizes are non-empty (i.e. user provided), then
1949/// carry out basic sanity-checking.
1950static LogicalResult
1951vectorizeUnPackOpPrecondition(linalg::UnPackOp unpackOp,
1952 ArrayRef<int64_t> inputVectorSizes) {
1953 // Pack/unpack memref transformations are unsupported. The memref forms
1954 // are mainly for bufferization and scalar lowering. Other uses are not
1955 // recommended, see #225650 for details.
1956 if (!unpackOp.hasPureTensorSemantics())
1957 return failure();
1958
1959 // If there are no input vector sizes and all shapes are static, there is
1960 // nothing left to check.
1961 if (inputVectorSizes.empty() && unpackOp.getDestType().hasStaticShape() &&
1962 unpackOp.getSourceType().hasStaticShape())
1963 return success();
1964
1965 // The number of input vector sizes must be equal to:
1966 // * read-vector-rank
1967 if (!inputVectorSizes.empty() &&
1968 (inputVectorSizes.size() != unpackOp.getSourceRank())) {
1969 LDBG() << "Incorrect number of input vector sizes";
1970 return failure();
1971 }
1972
1973 // Check the vector sizes for the read operation.
1974 if (failed(Result: vector::isValidMaskedInputVector(
1975 shape: unpackOp.getSourceType().getShape(), inputVectorSizes))) {
1976 LDBG() << "Invalid vector sizes for the read operation";
1977 return failure();
1978 }
1979
1980 return success();
1981}
1982
1983static LogicalResult
1984vectorizeInsertSliceOpPrecondition(tensor::InsertSliceOp sliceOp,
1985 ArrayRef<int64_t> inputVectorSizes) {
1986
1987 TypedValue<RankedTensorType> source = sliceOp.getSource();
1988 auto sourceType = source.getType();
1989 if (!VectorType::isValidElementType(t: sourceType.getElementType()))
1990 return failure();
1991
1992 // The write is a vector.transfer_write at the slice offsets, which cannot
1993 // express a stride.
1994 if (!sliceOp.hasUnitStride()) {
1995 LDBG() << "Only unit strides are supported";
1996 return failure();
1997 }
1998
1999 // Get the pad value.
2000 // TransferReadOp (which is used to vectorize InsertSliceOp), requires a
2001 // scalar padding value. Note that:
2002 // * for in-bounds accesses,
2003 // the value is actually irrelevant. There are 2 cases in which xfer.read
2004 // accesses are known to be in-bounds:
2005 // 1. The source shape is static (output vector sizes would be based on
2006 // the source shape and hence all memory accesses would be in-bounds),
2007 // 2. Masking is used, i.e. the output vector sizes are user-provided. In
2008 // this case it is safe to assume that all memory accesses are in-bounds.
2009 //
2010 // When the value is not known and not needed, use 0. Otherwise, bail out.
2011 Value padValue = getStaticPadVal(op: sliceOp);
2012 bool isOutOfBoundsRead =
2013 !sourceType.hasStaticShape() && inputVectorSizes.empty();
2014
2015 if (!padValue && isOutOfBoundsRead) {
2016 LDBG() << "Failed to get a pad value for out-of-bounds read access";
2017 return failure();
2018 }
2019 return success();
2020}
2021
2022/// Vectorize a named linalg contraction op into:
2023/// vector::TransferReadOp - Reads vectors from the operands
2024/// vector::ContractionOp - Performs contraction
2025/// vector::TransferWriteOp - Write the result vector back to the
2026/// destination
2027/// The operands shapes are preserved and loaded directly into vectors.
2028/// Any further permutations or numerical casting remain within contraction op.
2029static LogicalResult
2030vectorizeAsLinalgContraction(RewriterBase &rewriter, VectorizationState &state,
2031 LinalgOp linalgOp,
2032 SmallVectorImpl<Value> &newResults) {
2033 Location loc = linalgOp.getLoc();
2034 MLIRContext *ctx = linalgOp.getContext();
2035
2036 // For simplicity, contraction vectorization is limited to linalg named ops.
2037 // Generic op is ignored as not every arbitrary contraction body can be
2038 // expressed by a vector.contract.
2039 if (!isa<ContractionOpInterface>(Val: linalgOp.getOperation()))
2040 return failure();
2041
2042 OpOperand *outOperand = linalgOp.getDpsInitOperand(i: 0);
2043 Operation *reduceOp = matchLinalgReduction(outputOperand: outOperand);
2044 auto maybeKind = getCombinerOpKind(combinerOp: reduceOp);
2045 if (!maybeKind) {
2046 LDBG() << "Failed to determine contraction combining kind.";
2047 return failure();
2048 }
2049
2050 // Check that all dimensions are present in the input operands.
2051 // Arbitrary broadcasts are not supported by the vector contraction.
2052 // Broadcasts are expected to be decomposed before vectorization.
2053 AffineMap lhsMap = linalgOp.getIndexingMapsArray()[0];
2054 AffineMap rhsMap = linalgOp.getIndexingMapsArray()[1];
2055 if (getUnusedDimsBitVector(maps: {lhsMap, rhsMap}).any()) {
2056 LDBG() << "Contractions with broadcasts are not supported.";
2057 return failure();
2058 }
2059
2060 // Load operands.
2061 SmallVector<Value> vecOperands;
2062 for (OpOperand &opOperand : linalgOp->getOpOperands()) {
2063 // The operand vector shape is computed by mapping the canonical vector
2064 // shape to the operand's domain. Further permutations are left as a part of
2065 // the contraction.
2066 AffineMap indexingMap = linalgOp.getMatchingIndexingMap(opOperand: &opOperand);
2067 AffineMap readMap = AffineMap::getMultiDimIdentityMap(
2068 numDims: indexingMap.getNumResults(), context: rewriter.getContext());
2069 Type elemType = getElementTypeOrSelf(val: opOperand.get());
2070 VectorType readType =
2071 state.getCanonicalVecType(elementType: elemType, dimPermutation: readMap.compose(map: indexingMap));
2072
2073 Value read = mlir::vector::createReadOrMaskedRead(
2074 builder&: rewriter, loc, source: opOperand.get(), vecToReadTy: readType,
2075 /*padding=*/padValue: arith::getZeroConstant(builder&: rewriter, loc, type: elemType),
2076 /*useInBoundsInsteadOfMasking=*/false);
2077 vecOperands.push_back(Elt: read);
2078 }
2079
2080 // Preserve the contraction's cast semantics when converting operands to the
2081 // integer accumulator type. vector.contract provides an implicit signed
2082 // integer promotion; the cases below materialize explicit casts as needed.
2083 auto castAttr = linalgOp->getAttrOfType<TypeFnAttr>(name: "cast");
2084 bool hasUnsignedCast =
2085 castAttr && castAttr.getValue() == TypeFn::cast_unsigned;
2086 auto accType = dyn_cast<VectorType>(Val: vecOperands[2].getType());
2087 auto accElementType =
2088 accType ? dyn_cast<IntegerType>(Val: accType.getElementType()) : nullptr;
2089 if (accElementType && accElementType.isSignless()) {
2090 for (Value &operand : MutableArrayRef(vecOperands).take_front(N: 2)) {
2091 auto operandType = cast<VectorType>(Val: operand.getType());
2092 Type operandElementType = operandType.getElementType();
2093 VectorType castType = operandType.clone(elementType: accElementType);
2094
2095 if (isa<FloatType>(Val: operandElementType)) {
2096 operand =
2097 hasUnsignedCast
2098 ? arith::FPToUIOp::create(builder&: rewriter, location: loc, out: castType, in: operand)
2099 .getResult()
2100 : arith::FPToSIOp::create(builder&: rewriter, location: loc, out: castType, in: operand)
2101 .getResult();
2102 continue;
2103 }
2104
2105 auto operandIntegerType = dyn_cast<IntegerType>(Val&: operandElementType);
2106 if (!operandIntegerType || !operandIntegerType.isSignless())
2107 continue;
2108 if (operandIntegerType.getWidth() >= accElementType.getWidth())
2109 continue;
2110 if (!hasUnsignedCast)
2111 continue;
2112
2113 // vector.contract implicitly sign-extends integer operands. Unsigned
2114 // promotion therefore requires an explicit zero extension.
2115 operand = arith::ExtUIOp::create(builder&: rewriter, location: loc, out: castType, in: operand);
2116 }
2117 }
2118
2119 // Remap iterators from linalg to vector.
2120 SmallVector<Attribute> iterAttrs;
2121 auto iterators = linalgOp.getIteratorTypesArray();
2122 for (utils::IteratorType iter : iterators) {
2123 auto vecIter = iter == utils::IteratorType::parallel
2124 ? vector::IteratorType::parallel
2125 : vector::IteratorType::reduction;
2126 iterAttrs.push_back(Elt: vector::IteratorTypeAttr::get(context: ctx, value: vecIter));
2127 }
2128
2129 // Create contraction.
2130 Operation *contractOp = vector::ContractionOp::create(
2131 builder&: rewriter, location: loc, /*lhs=*/vecOperands[0],
2132 /*rhs=*/vecOperands[1], /*acc=*/vecOperands[2],
2133 indexingMaps: linalgOp.getIndexingMaps(), iteratorTypes: rewriter.getArrayAttr(value: iterAttrs), kind: *maybeKind);
2134 contractOp = state.maskOperation(rewriter, opToMask: contractOp, linalgOp);
2135
2136 // Store result.
2137 Operation *write = vector::createWriteOrMaskedWrite(
2138 builder&: rewriter, loc, vecToStore: contractOp->getResult(idx: 0), dest: outOperand->get());
2139
2140 // Finalize.
2141 if (!write->getResults().empty())
2142 newResults.push_back(Elt: write->getResult(idx: 0));
2143
2144 return success();
2145}
2146
2147namespace {
2148enum class ConvOperationKind { Conv, Pool };
2149} // namespace
2150
2151static bool isCastOfBlockArgument(Operation *op) {
2152 return isa<CastOpInterface>(Val: op) && op->getNumOperands() == 1 &&
2153 isa<BlockArgument>(Val: op->getOperand(idx: 0));
2154}
2155
2156// Returns the ConvOperationKind of the op using reduceOp of the generic
2157// payload. If it is neither a convolution nor a pooling, it returns
2158// std::nullopt.
2159//
2160// If (region has 2 ops (reduction + yield) or 3 ops (extension + reduction
2161// + yield) and rhs is not used) then it is the body of a pooling
2162// If conv, check for single `mul` predecessor. The `mul` operands must be
2163// block arguments or extension of block arguments.
2164// Otherwise, check for one or zero `ext` predecessor. The `ext` operands
2165// must be block arguments or extension of block arguments.
2166static std::optional<ConvOperationKind>
2167getConvOperationKind(Operation *reduceOp) {
2168 int numBlockArguments =
2169 llvm::count_if(Range: reduceOp->getOperands(), P: llvm::IsaPred<BlockArgument>);
2170
2171 switch (numBlockArguments) {
2172 case 1: {
2173 // Will be convolution if feeder is a MulOp.
2174 // A strength reduced version of MulOp for i1 type is AndOp which is also
2175 // supported. Otherwise, it can be pooling. This strength reduction logic
2176 // is in `buildBinaryFn` helper in the Linalg dialect.
2177 auto feedValIt = llvm::find_if_not(Range: reduceOp->getOperands(),
2178 P: llvm::IsaPred<BlockArgument>);
2179 assert(feedValIt != reduceOp->operand_end() &&
2180 "Expected a non-block argument operand");
2181 Operation *feedOp = (*feedValIt).getDefiningOp();
2182 if (isCastOfBlockArgument(op: feedOp)) {
2183 return ConvOperationKind::Pool;
2184 }
2185
2186 if (!((isa<arith::MulIOp, arith::MulFOp>(Val: feedOp) ||
2187 (isa<arith::AndIOp>(Val: feedOp) &&
2188 feedOp->getResultTypes()[0].isInteger(width: 1))) &&
2189 llvm::all_of(Range: feedOp->getOperands(), P: [](Value v) {
2190 if (isa<BlockArgument>(Val: v))
2191 return true;
2192 if (Operation *op = v.getDefiningOp())
2193 return isCastOfBlockArgument(op);
2194 return false;
2195 }))) {
2196 return std::nullopt;
2197 }
2198
2199 return ConvOperationKind::Conv;
2200 }
2201 case 2:
2202 // Must be pooling
2203 return ConvOperationKind::Pool;
2204 default:
2205 return std::nullopt;
2206 }
2207}
2208
2209static bool isSupportedPoolKind(vector::CombiningKind kind) {
2210 switch (kind) {
2211 case vector::CombiningKind::ADD:
2212 case vector::CombiningKind::MAXNUMF:
2213 case vector::CombiningKind::MAXIMUMF:
2214 case vector::CombiningKind::MAXIMUMNUMF:
2215 case vector::CombiningKind::MAXSI:
2216 case vector::CombiningKind::MAXUI:
2217 case vector::CombiningKind::MINNUMF:
2218 case vector::CombiningKind::MINIMUMF:
2219 case vector::CombiningKind::MINIMUMNUMF:
2220 case vector::CombiningKind::MINSI:
2221 case vector::CombiningKind::MINUI:
2222 return true;
2223 default:
2224 return false;
2225 }
2226}
2227
2228static LogicalResult vectorizeConvOpPrecondition(linalg::LinalgOp convOp) {
2229 auto getOperandType = [&](auto operand) {
2230 return dyn_cast<ShapedType>((operand->get()).getType());
2231 };
2232 ShapedType lhsShapedType = getOperandType(convOp.getDpsInputOperand(i: 0));
2233 ShapedType rhsShapedType = getOperandType(convOp.getDpsInputOperand(i: 1));
2234 ShapedType resShapedType = getOperandType(convOp.getDpsInitOperand(i: 0));
2235 // (LHS has dimension NCW/NWC and RES has dimension NFW/NCW/NWF/NWC) OR
2236 // (non-channeled convolution -> LHS and RHS both have single dimensions).
2237 // Note that this also ensures 2D and 3D convolutions are rejected.
2238 if ((lhsShapedType.getRank() != 3 || resShapedType.getRank() != 3) &&
2239 (lhsShapedType.getRank() != 1 || resShapedType.getRank() != 1))
2240 return failure();
2241
2242 Operation *reduceOp = matchLinalgReduction(outputOperand: convOp.getDpsInitOperand(i: 0));
2243 if (!reduceOp)
2244 return failure();
2245
2246 auto maybeOper = getConvOperationKind(reduceOp);
2247 if (!maybeOper.has_value())
2248 return failure();
2249
2250 auto maybeKind = getCombinerOpKind(combinerOp: reduceOp);
2251 // Typically convolution will have a `Add` CombiningKind but for i1 type it
2252 // can get strength reduced to `OR` which is also supported. This strength
2253 // reduction logic is in `buildBinaryFn` helper in the Linalg dialect.
2254 if (!maybeKind || ((*maybeKind != vector::CombiningKind::ADD &&
2255 *maybeKind != vector::CombiningKind::OR) &&
2256 (*maybeOper != ConvOperationKind::Pool ||
2257 !isSupportedPoolKind(kind: *maybeKind)))) {
2258 return failure();
2259 }
2260
2261 auto rhsRank = rhsShapedType.getRank();
2262 if (*maybeOper == ConvOperationKind::Pool) {
2263 if (rhsRank != 1)
2264 return failure();
2265 } else {
2266 if (rhsRank != 1 && rhsRank != 2 && rhsRank != 3)
2267 return failure();
2268 }
2269
2270 return success();
2271}
2272
2273static LogicalResult vectorizeLinalgOpPrecondition(
2274 LinalgOp linalgOp, ArrayRef<int64_t> inputVectorSizes,
2275 bool vectorizeNDExtract, bool flatten1DDepthwiseConv) {
2276 // tensor with dimension of 0 cannot be vectorized.
2277 if (llvm::any_of(Range: linalgOp->getOpOperands(), P: [&](OpOperand &operand) {
2278 return llvm::is_contained(Range: linalgOp.getShape(opOperand: &operand), Element: 0);
2279 }))
2280 return failure();
2281 // Check API contract for input vector sizes.
2282 if (!inputVectorSizes.empty() &&
2283 failed(Result: vector::isValidMaskedInputVector(shape: linalgOp.getStaticLoopRanges(),
2284 inputVectorSizes)))
2285 return failure();
2286
2287 if (linalgOp.hasDynamicShape() && failed(Result: vectorizeDynamicLinalgOpPrecondition(
2288 op: linalgOp, flatten1DDepthwiseConv))) {
2289 LDBG() << "Dynamically-shaped op failed vectorization pre-conditions";
2290 return failure();
2291 }
2292
2293 SmallVector<CustomVectorizationPrecondition> customPreconditions;
2294
2295 // Register CustomVectorizationPrecondition for extractOp.
2296 customPreconditions.push_back(Elt: tensorExtractVectorizationPrecondition);
2297
2298 // All types in the body should be a supported element type for VectorType.
2299 for (Operation &innerOp : linalgOp->getRegion(index: 0).front()) {
2300 // Check if any custom hook can vectorize the inner op.
2301 if (llvm::any_of(
2302 Range&: customPreconditions,
2303 P: [&](const CustomVectorizationPrecondition &customPrecondition) {
2304 return succeeded(
2305 Result: customPrecondition(&innerOp, vectorizeNDExtract));
2306 })) {
2307 continue;
2308 }
2309 if (!llvm::all_of(Range: innerOp.getOperandTypes(),
2310 P: VectorType::isValidElementType)) {
2311 return failure();
2312 }
2313 if (!llvm::all_of(Range: innerOp.getResultTypes(),
2314 P: VectorType::isValidElementType)) {
2315 return failure();
2316 }
2317 }
2318 if (isElementwise(op: linalgOp))
2319 return success();
2320
2321 // Check for both named as well as generic convolution ops.
2322 if (isaConvolutionOpInterface(linalgOp))
2323 return vectorizeConvOpPrecondition(convOp: linalgOp);
2324
2325 // TODO: the common vector shape is equal to the static loop sizes only when
2326 // all indexing maps are projected permutations. For convs and stencils the
2327 // logic will need to evolve.
2328 if (!allIndexingsAreProjectedPermutation(op: linalgOp)) {
2329 LDBG() << "precondition failed: not projected permutations";
2330 return failure();
2331 }
2332 if (failed(Result: reductionPreconditions(op: linalgOp))) {
2333 LDBG() << "precondition failed: reduction preconditions";
2334 return failure();
2335 }
2336 return success();
2337}
2338
2339static LogicalResult
2340vectorizePackOpPrecondition(linalg::PackOp packOp,
2341 ArrayRef<int64_t> inputVectorSizes) {
2342 // Pack/unpack memref transformations are unsupported. The memref forms
2343 // are mainly for bufferization and scalar lowering. Other uses are not
2344 // recommended, see #225650 for details.
2345 if (!packOp.hasPureTensorSemantics())
2346 return failure();
2347
2348 auto padValue = packOp.getPaddingValue();
2349 Attribute cstAttr;
2350 // TODO: Relax this condiiton
2351 if (padValue && !matchPattern(value: padValue, pattern: m_Constant(bind_value: &cstAttr))) {
2352 LDBG() << "pad value is not constant: " << packOp;
2353 return failure();
2354 }
2355
2356 ArrayRef<int64_t> resultTensorShape = packOp.getDestType().getShape();
2357 bool satisfyEmptyCond = true;
2358 if (inputVectorSizes.empty()) {
2359 if (!packOp.getDestType().hasStaticShape() ||
2360 !packOp.getSourceType().hasStaticShape())
2361 satisfyEmptyCond = false;
2362 }
2363
2364 if (!satisfyEmptyCond &&
2365 failed(Result: vector::isValidMaskedInputVector(
2366 shape: resultTensorShape.take_front(N: packOp.getSourceRank()),
2367 inputVectorSizes)))
2368 return failure();
2369
2370 if (llvm::any_of(Range: packOp.getInnerTiles(), P: [](OpFoldResult v) {
2371 return !getConstantIntValue(ofr: v).has_value();
2372 })) {
2373 LDBG() << "inner_tiles must be constant: " << packOp;
2374 return failure();
2375 }
2376
2377 return success();
2378}
2379
2380static LogicalResult
2381vectorizePadOpPrecondition(tensor::PadOp padOp,
2382 ArrayRef<int64_t> inputVectorSizes) {
2383 auto padValue = padOp.getConstantPaddingValue();
2384 if (!padValue) {
2385 LDBG() << "pad value is not constant: " << padOp;
2386 return failure();
2387 }
2388
2389 ArrayRef<int64_t> resultTensorShape = padOp.getResultType().getShape();
2390 if (failed(Result: vector::isValidMaskedInputVector(shape: resultTensorShape,
2391 inputVectorSizes)))
2392 return failure();
2393
2394 // Padding with non-zero low pad values is not supported, unless the
2395 // corresponding result dim is 1 as this would require shifting the results to
2396 // the right for the low padded dims by the required amount of low padding.
2397 // However, we do support low padding if the dims being low padded have result
2398 // sizes of 1. The reason is when we have a low pad on a unit result dim, the
2399 // input size of that dimension will be dynamically zero (as the sum of the
2400 // low pad and input dim size has to be one) and hence we will create a zero
2401 // mask as the lowering logic just makes the mask one for the input dim size -
2402 // which is zero here. Hence we will load the pad value which is what we want
2403 // in this case. If the low pad is dynamically zero then the lowering is
2404 // correct as well as no shifts are necessary.
2405 if (llvm::any_of(Range: llvm::enumerate(First: padOp.getMixedLowPad()),
2406 P: [&](const auto &en) {
2407 OpFoldResult padValue = en.value();
2408 unsigned pos = en.index();
2409 std::optional<int64_t> pad = getConstantIntValue(ofr: padValue);
2410 return (!pad.has_value() || pad.value() != 0) &&
2411 resultTensorShape[pos] != 1;
2412 })) {
2413 LDBG() << "low pad must all be zero for all non unit dims: " << padOp;
2414 return failure();
2415 }
2416
2417 return success();
2418}
2419
2420/// Preconditions for scalable vectors.
2421///
2422/// For Ops implementing the LinalgOp interface, this is quite restrictive - it
2423/// models the fact that in practice we would only make selected dimensions
2424/// scalable. For other Ops (e.g. `linalg.unpack`), this will succeed
2425/// unconditionally - we are yet to identify meaningful conditions.
2426static LogicalResult
2427vectorizeScalableVectorPrecondition(Operation *op,
2428 ArrayRef<int64_t> inputVectorSizes,
2429 ArrayRef<bool> inputScalableVecDims) {
2430 assert(inputVectorSizes.size() == inputScalableVecDims.size() &&
2431 "Number of input vector sizes and scalable dims doesn't match");
2432
2433 size_t numOfScalableDims =
2434 llvm::count_if(Range&: inputScalableVecDims, P: [](bool flag) { return flag; });
2435
2436 if (numOfScalableDims == 0)
2437 return success();
2438
2439 auto linalgOp = dyn_cast<LinalgOp>(Val: op);
2440
2441 // Cond 1: Reject Ops that don't implement the LinalgOp interface, with the
2442 // exception of UnpackOp for which there is a dedicated hook.
2443 if (!linalgOp) {
2444 return success(IsSuccess: isa<linalg::UnPackOp>(Val: op));
2445 }
2446
2447 // Cond 2: There's been no need for more than 2 scalable dims so far
2448 if (numOfScalableDims > 2)
2449 return failure();
2450
2451 // Cond 3: Look at the configuration in `inputScalableVecDims` and verify that
2452 // it matches one of the supported cases:
2453 // 1. Exactly 1 dim is scalable and that's the _last_ non-unit parallel dim
2454 // (*).
2455 // 2. Exactly 2 dims are scalable and those are the _last two adjacent_
2456 // parallel dims.
2457 // 3. Exactly 1 reduction dim is scalable and that's the last (innermost)
2458 // dim.
2459 // The 2nd restriction above means that only Matmul-like Ops are supported
2460 // when 2 dims are scalable, e.g. :
2461 // * iterators = [parallel, parallel, reduction]
2462 // * scalable flags = [true, true, false]
2463 //
2464 // (*) Non-unit dims get folded away in practice.
2465 // TODO: Relax these conditions as good motivating examples are identified.
2466
2467 // Find the first scalable flag.
2468 bool seenNonUnitParallel = false;
2469 auto iterators = linalgOp.getIteratorTypesArray();
2470 SmallVector<bool> scalableFlags(inputScalableVecDims);
2471 int64_t idx = scalableFlags.size() - 1;
2472 while (!scalableFlags[idx]) {
2473 bool isNonUnitDim = (inputVectorSizes[idx] != 1);
2474 seenNonUnitParallel |=
2475 (iterators[idx] == utils::IteratorType::parallel && isNonUnitDim);
2476
2477 iterators.pop_back();
2478 scalableFlags.pop_back();
2479 --idx;
2480 }
2481
2482 // Analyze the iterator corresponding to the first scalable dim.
2483 switch (iterators.back()) {
2484 case utils::IteratorType::reduction: {
2485 // Check 3. above is met.
2486 if (iterators.size() != inputVectorSizes.size()) {
2487 LDBG() << "Non-trailing reduction dim requested for scalable "
2488 "vectorization";
2489 return failure();
2490 }
2491 if (isa<linalg::MatmulOp>(Val: op)) {
2492 LDBG()
2493 << "Scalable vectorization of the reduction dim in Matmul-like ops "
2494 "is not supported";
2495 return failure();
2496 }
2497 break;
2498 }
2499 case utils::IteratorType::parallel: {
2500 // Check 1. and 2. above are met.
2501 if (seenNonUnitParallel) {
2502 LDBG() << "Inner parallel dim not requested for scalable "
2503 "vectorization";
2504 return failure();
2505 }
2506 break;
2507 }
2508 }
2509
2510 // If present, check the 2nd scalable dim. ATM, only Matmul-like Ops are
2511 // supported for which expect the folowing config:
2512 // * iterators = [parallel, parallel, reduction]
2513 // * scalable flags = [true, true, false]
2514 if (numOfScalableDims == 2) {
2515 // Disallow below case which breaks 3. above:
2516 // * iterators = [..., parallel, reduction]
2517 // * scalable flags = [..., true, true]
2518 if (iterators.back() == utils::IteratorType::reduction) {
2519 LDBG() << "Higher dim than the trailing reduction dim requested for "
2520 "scalable "
2521 "vectorizatio";
2522 return failure();
2523 }
2524 scalableFlags.pop_back();
2525 iterators.pop_back();
2526
2527 if (!scalableFlags.back() ||
2528 (iterators.back() != utils::IteratorType::parallel))
2529 return failure();
2530 }
2531
2532 // Cond 4: Only the following ops are supported in the
2533 // presence of scalable vectors
2534 return success(
2535 IsSuccess: isElementwise(op: linalgOp) || isa<linalg::MatmulOp>(Val: op) ||
2536 isa<linalg::BatchMatmulOp>(Val: op) ||
2537 isaConvolutionOpOfType<linalg::DepthwiseConv1DNwcWcOp>(op: linalgOp) ||
2538 isa<linalg::MatvecOp>(Val: op) || isa<linalg::Mmt4DOp>(Val: op) ||
2539 isa<linalg::BatchMmt4DOp>(Val: op) || hasReductionIterator(op&: linalgOp));
2540}
2541
2542LogicalResult mlir::linalg::vectorizeOpPrecondition(
2543 Operation *op, ArrayRef<int64_t> inputVectorSizes,
2544 ArrayRef<bool> inputScalableVecDims, bool vectorizeNDExtract,
2545 bool flatten1DDepthwiseConv) {
2546
2547 if (!hasVectorizationImpl(op))
2548 return failure();
2549
2550 if (failed(Result: vectorizeScalableVectorPrecondition(op, inputVectorSizes,
2551 inputScalableVecDims)))
2552 return failure();
2553
2554 return TypeSwitch<Operation *, LogicalResult>(op)
2555 .Case(caseFn: [&](linalg::LinalgOp linalgOp) {
2556 return vectorizeLinalgOpPrecondition(linalgOp, inputVectorSizes,
2557 vectorizeNDExtract,
2558 flatten1DDepthwiseConv);
2559 })
2560 .Case(caseFn: [&](tensor::PadOp padOp) {
2561 return vectorizePadOpPrecondition(padOp, inputVectorSizes);
2562 })
2563 .Case(caseFn: [&](linalg::PackOp packOp) {
2564 return vectorizePackOpPrecondition(packOp, inputVectorSizes);
2565 })
2566 .Case(caseFn: [&](linalg::UnPackOp unpackOp) {
2567 return vectorizeUnPackOpPrecondition(unpackOp, inputVectorSizes);
2568 })
2569 .Case(caseFn: [&](tensor::InsertSliceOp sliceOp) {
2570 return vectorizeInsertSliceOpPrecondition(sliceOp, inputVectorSizes);
2571 })
2572 .Default(defaultResult: failure());
2573}
2574
2575/// Converts affine.apply Ops to arithmetic operations.
2576static void convertAffineApply(RewriterBase &rewriter, LinalgOp linalgOp) {
2577 OpBuilder::InsertionGuard g(rewriter);
2578 auto toReplace = linalgOp.getBlock()->getOps<affine::AffineApplyOp>();
2579
2580 for (auto op : make_early_inc_range(Range&: toReplace)) {
2581 rewriter.setInsertionPoint(op);
2582 auto expanded = affine::expandAffineExpr(
2583 builder&: rewriter, loc: op->getLoc(), expr: op.getAffineMap().getResult(idx: 0),
2584 dimValues: op.getOperands().take_front(n: op.getAffineMap().getNumDims()),
2585 symbolValues: op.getOperands().take_back(n: op.getAffineMap().getNumSymbols()));
2586 rewriter.replaceOp(op, newValues: expanded);
2587 }
2588}
2589
2590bool mlir::linalg::hasVectorizationImpl(Operation *op) {
2591 return isa<linalg::LinalgOp, tensor::PadOp, linalg::PackOp, linalg::UnPackOp,
2592 tensor::InsertSliceOp>(Val: op);
2593}
2594
2595FailureOr<VectorizationResult> mlir::linalg::vectorize(
2596 RewriterBase &rewriter, Operation *op, ArrayRef<int64_t> inputVectorSizes,
2597 ArrayRef<bool> inputScalableVecDims, bool vectorizeNDExtract,
2598 bool flatten1DDepthwiseConv, bool assumeDynamicDimsMatchVecSizes,
2599 bool createNamedContraction) {
2600 LDBG() << "Attempting to vectorize: " << *op;
2601 LDBG() << "Input vector sizes: " << llvm::interleaved(R: inputVectorSizes);
2602 LDBG() << "Input scalable vector dims: "
2603 << llvm::interleaved(R: inputScalableVecDims);
2604
2605 if (failed(Result: vectorizeOpPrecondition(op, inputVectorSizes, inputScalableVecDims,
2606 vectorizeNDExtract,
2607 flatten1DDepthwiseConv))) {
2608 LDBG() << "Vectorization pre-conditions failed";
2609 return failure();
2610 }
2611
2612 // Initialize vectorization state.
2613 VectorizationState state(rewriter);
2614 if (auto linalgOp = dyn_cast<linalg::LinalgOp>(Val: op)) {
2615 if (failed(Result: state.initState(rewriter, linalgOp, inputVectorSizes,
2616 inputScalableVecDims,
2617 assumeDimsMatchVec: assumeDynamicDimsMatchVecSizes))) {
2618 LDBG() << "Vectorization state couldn't be initialized";
2619 return failure();
2620 }
2621 }
2622
2623 SmallVector<Value> results;
2624 auto vectorizeResult =
2625 TypeSwitch<Operation *, LogicalResult>(op)
2626 .Case(caseFn: [&](linalg::LinalgOp linalgOp) {
2627 // Check for both named as well as generic convolution ops.
2628 if (isaConvolutionOpInterface(linalgOp)) {
2629 FailureOr<Operation *> convOr = vectorizeConvolution(
2630 rewriter, convOp: linalgOp, inputVecSizes: inputVectorSizes, inputVecScalableFlags: inputScalableVecDims,
2631 flatten1DDepthwiseConv);
2632 if (succeeded(Result: convOr)) {
2633 llvm::append_range(C&: results, R: (*convOr)->getResults());
2634 return success();
2635 }
2636
2637 LDBG() << "Unsupported convolution can't be vectorized.";
2638 return failure();
2639 }
2640
2641 if (createNamedContraction &&
2642 isa<ContractionOpInterface>(Val: linalgOp.getOperation()))
2643 return vectorizeAsLinalgContraction(rewriter, state, linalgOp,
2644 newResults&: results);
2645
2646 LDBG()
2647 << "Vectorize generic by broadcasting to the canonical vector "
2648 "shape";
2649
2650 // Pre-process before proceeding.
2651 convertAffineApply(rewriter, linalgOp);
2652
2653 // TODO: 'vectorize' takes in a 'RewriterBase' which is up-casted
2654 // to 'OpBuilder' when it is passed over to some methods like
2655 // 'vectorizeAsLinalgGeneric'. This is highly problematic: if we
2656 // erase an op within these methods, the actual rewriter won't be
2657 // notified and we will end up with read-after-free issues!
2658 return vectorizeAsLinalgGeneric(rewriter, state, linalgOp, newResults&: results);
2659 })
2660 .Case(caseFn: [&](tensor::PadOp padOp) {
2661 return vectorizeAsTensorPadOp(rewriter, padOp, inputVectorSizes,
2662 newResults&: results);
2663 })
2664 .Case(caseFn: [&](linalg::PackOp packOp) {
2665 return vectorizeAsTensorPackOp(rewriter, packOp, inputVectorSizes,
2666 newResults&: results);
2667 })
2668 .Case(caseFn: [&](linalg::UnPackOp unpackOp) {
2669 return vectorizeAsTensorUnpackOp(rewriter, unpackOp,
2670 inputVectorSizes,
2671 inputScalableVecDims, newResults&: results);
2672 })
2673 .Case(caseFn: [&](tensor::InsertSliceOp sliceOp) {
2674 return vectorizeAsInsertSliceOp(rewriter, sliceOp, inputVectorSizes,
2675 newResults&: results);
2676 })
2677 .Default(defaultResult: failure());
2678
2679 if (failed(Result: vectorizeResult)) {
2680 LDBG() << "Vectorization failed";
2681 return failure();
2682 }
2683
2684 return VectorizationResult{.replacements: results};
2685}
2686
2687LogicalResult mlir::linalg::vectorizeCopy(RewriterBase &rewriter,
2688 memref::CopyOp copyOp) {
2689 auto srcType = cast<MemRefType>(Val: copyOp.getSource().getType());
2690 auto dstType = cast<MemRefType>(Val: copyOp.getTarget().getType());
2691 if (!srcType.hasStaticShape() || !dstType.hasStaticShape())
2692 return failure();
2693
2694 auto srcElementType = getElementTypeOrSelf(type: srcType);
2695 auto dstElementType = getElementTypeOrSelf(type: dstType);
2696 if (!VectorType::isValidElementType(t: srcElementType) ||
2697 !VectorType::isValidElementType(t: dstElementType))
2698 return failure();
2699
2700 auto readType = VectorType::get(shape: srcType.getShape(), elementType: srcElementType);
2701 auto writeType = VectorType::get(shape: dstType.getShape(), elementType: dstElementType);
2702
2703 Location loc = copyOp->getLoc();
2704 Value zero = arith::ConstantIndexOp::create(builder&: rewriter, location: loc, value: 0);
2705 SmallVector<Value> indices(srcType.getRank(), zero);
2706
2707 Value readValue = vector::TransferReadOp::create(
2708 builder&: rewriter, location: loc, vectorType: readType, source: copyOp.getSource(), indices,
2709 /*padding=*/std::nullopt,
2710 permutationMap: rewriter.getMultiDimIdentityMap(rank: srcType.getRank()));
2711 if (cast<VectorType>(Val: readValue.getType()).getRank() == 0) {
2712 readValue = vector::ExtractOp::create(builder&: rewriter, location: loc, source: readValue,
2713 position: ArrayRef<int64_t>());
2714 readValue =
2715 vector::BroadcastOp::create(builder&: rewriter, location: loc, result: writeType, source: readValue);
2716 }
2717 Operation *writeValue = vector::TransferWriteOp::create(
2718 builder&: rewriter, location: loc, vector: readValue, dest: copyOp.getTarget(), indices,
2719 permutationMap: rewriter.getMultiDimIdentityMap(rank: srcType.getRank()));
2720 rewriter.replaceOp(op: copyOp, newValues: writeValue->getResults());
2721 return success();
2722}
2723
2724//----------------------------------------------------------------------------//
2725// Misc. vectorization patterns.
2726//----------------------------------------------------------------------------//
2727/// Base pattern for rewriting tensor::PadOps whose result is consumed by a
2728/// given operation type OpTy.
2729template <typename OpTy>
2730struct VectorizePadOpUserPattern : public OpRewritePattern<tensor::PadOp> {
2731 using OpRewritePattern<tensor::PadOp>::OpRewritePattern;
2732
2733 LogicalResult matchAndRewrite(tensor::PadOp padOp,
2734 PatternRewriter &rewriter) const final {
2735 bool changed = false;
2736 // Insert users in vector, because some users may be replaced/removed.
2737 for (auto *user : llvm::to_vector<4>(Range: padOp->getUsers()))
2738 if (auto op = dyn_cast<OpTy>(user))
2739 changed |= rewriteUser(rewriter, padOp, op).succeeded();
2740 return success(IsSuccess: changed);
2741 }
2742
2743protected:
2744 virtual LogicalResult rewriteUser(PatternRewriter &rewriter,
2745 tensor::PadOp padOp, OpTy op) const = 0;
2746};
2747
2748/// Rewrite use of tensor::PadOp result in TransferReadOp. E.g.:
2749/// ```
2750/// %0 = tensor.pad %src ... : tensor<?x?xf32> to tensor<17x5xf32>
2751/// %r = vector.transfer_read %0[%c0, %c0], %cst
2752/// {in_bounds = [true, true]} : tensor<17x5xf32>, vector<17x5xf32>
2753/// ```
2754/// is rewritten to:
2755/// ```
2756/// %r = vector.transfer_read %src[%c0, %c0], %padding
2757/// {in_bounds = [true, true]}
2758/// : tensor<?x?xf32>, vector<17x5xf32>
2759/// ```
2760/// Note: By restricting this pattern to in-bounds TransferReadOps, we can be
2761/// sure that the original padding value %cst was never used.
2762///
2763/// This rewrite is possible if:
2764/// - `xferOp` has no out-of-bounds dims or mask.
2765/// - Low padding is static 0.
2766/// - Single, scalar padding value.
2767struct PadOpVectorizationWithTransferReadPattern
2768 : public VectorizePadOpUserPattern<vector::TransferReadOp> {
2769 using VectorizePadOpUserPattern<
2770 vector::TransferReadOp>::VectorizePadOpUserPattern;
2771
2772 LogicalResult rewriteUser(PatternRewriter &rewriter, tensor::PadOp padOp,
2773 vector::TransferReadOp xferOp) const override {
2774 // Low padding must be static 0.
2775 if (!padOp.hasZeroLowPad())
2776 return failure();
2777 // Pad value must be a constant.
2778 auto padValue = padOp.getConstantPaddingValue();
2779 if (!padValue)
2780 return failure();
2781 // Padding value of existing `xferOp` is unused.
2782 if (xferOp.hasOutOfBoundsDim() || xferOp.getMask())
2783 return failure();
2784
2785 rewriter.modifyOpInPlace(root: xferOp, callable: [&]() {
2786 SmallVector<bool> inBounds(xferOp.getVectorType().getRank(), false);
2787 xferOp->setInherentAttr(name: xferOp.getInBoundsAttrName(),
2788 value: rewriter.getBoolArrayAttr(values: inBounds));
2789 xferOp.getBaseMutable().assign(value: padOp.getSource());
2790 xferOp.getPaddingMutable().assign(value: padValue);
2791 });
2792
2793 return success();
2794 }
2795};
2796
2797/// Rewrite use of tensor::PadOp result in TransferWriteOp.
2798/// This pattern rewrites TransferWriteOps that write to a padded tensor
2799/// value, where the same amount of padding is immediately removed again after
2800/// the write. In such cases, the TransferWriteOp can write to the non-padded
2801/// tensor value and apply out-of-bounds masking. E.g.:
2802/// ```
2803/// %0 = tensor.extract_slice ...[...] [%s0, %s1] [1, 1]
2804/// : tensor<...> to tensor<?x?xf32>
2805/// %1 = tensor.pad %0 ... : tensor<?x?xf32> to tensor<17x5xf32>
2806/// %2 = vector.transfer_write %vec, %1[...]
2807/// : vector<17x5xf32>, tensor<17x5xf32>
2808/// %r = tensor.extract_slice %2[0, 0] [%s0, %s1] [1, 1]
2809/// : tensor<17x5xf32> to tensor<?x?xf32>
2810/// ```
2811/// is rewritten to:
2812/// ```
2813/// %0 = tensor.extract_slice ...[...] [%s0, %s1] [1, 1]
2814/// : tensor<...> to tensor<?x?xf32>
2815/// %r = vector.transfer_write %vec, %0[...] : vector<17x5xf32>,
2816/// tensor<?x?xf32>
2817/// ```
2818/// Note: It is important that the ExtractSliceOp %r resizes the result of the
2819/// TransferWriteOp to the same size as the input of the TensorPadOp (or an
2820/// even smaller size). Otherwise, %r's new (dynamic) dimensions would differ
2821/// from %r's old dimensions.
2822///
2823/// This rewrite is possible if:
2824/// - Low padding is static 0.
2825/// - `xferOp` has exactly one use, which is an ExtractSliceOp. This
2826/// ExtractSliceOp trims the same amount of padding that was added
2827/// beforehand.
2828/// - Single, scalar padding value.
2829struct PadOpVectorizationWithTransferWritePattern
2830 : public VectorizePadOpUserPattern<vector::TransferWriteOp> {
2831 using VectorizePadOpUserPattern<
2832 vector::TransferWriteOp>::VectorizePadOpUserPattern;
2833
2834 LogicalResult rewriteUser(PatternRewriter &rewriter, tensor::PadOp padOp,
2835 vector::TransferWriteOp xferOp) const override {
2836 // TODO: support 0-d corner case.
2837 if (xferOp.getTransferRank() == 0)
2838 return failure();
2839
2840 // Low padding must be static 0.
2841 if (!padOp.hasZeroLowPad())
2842 return failure();
2843 // Pad value must be a constant.
2844 auto padValue = padOp.getConstantPaddingValue();
2845 if (!padValue)
2846 return failure();
2847 // TransferWriteOp result must be directly consumed by an ExtractSliceOp.
2848 if (!xferOp->hasOneUse())
2849 return failure();
2850 auto trimPadding = dyn_cast<tensor::ExtractSliceOp>(Val: *xferOp->user_begin());
2851 if (!trimPadding)
2852 return failure();
2853 // Only static zero offsets supported when trimming padding.
2854 if (!trimPadding.hasZeroOffset())
2855 return failure();
2856 // trimPadding must remove the amount of padding that was added earlier.
2857 if (!hasSameTensorSize(beforePadding: padOp.getSource(), afterTrimming: trimPadding))
2858 return failure();
2859
2860 // Insert the new TransferWriteOp at position of the old TransferWriteOp.
2861 rewriter.setInsertionPoint(xferOp);
2862
2863 SmallVector<bool> inBounds(xferOp.getVectorType().getRank(), false);
2864 auto newXferOp = rewriter.replaceOpWithNewOp<vector::TransferWriteOp>(
2865 op: xferOp, args: padOp.getSource().getType(), args: xferOp.getVector(),
2866 args: padOp.getSource(), args: xferOp.getIndices(), args: xferOp.getPermutationMapAttr(),
2867 args: xferOp.getMask(), args: rewriter.getBoolArrayAttr(values: inBounds));
2868 rewriter.replaceOp(op: trimPadding, newValues: newXferOp->getResult(idx: 0));
2869
2870 return success();
2871 }
2872
2873 /// Check if `beforePadding` and `afterTrimming` have the same tensor size,
2874 /// i.e., same dimensions.
2875 ///
2876 /// Dimensions may be static, dynamic or mix of both. In case of dynamic
2877 /// dimensions, this function tries to infer the (static) tensor size by
2878 /// looking at the defining op and utilizing op-specific knowledge.
2879 ///
2880 /// This is a conservative analysis. In case equal tensor sizes cannot be
2881 /// proven statically, this analysis returns `false` even though the tensor
2882 /// sizes may turn out to be equal at runtime.
2883 bool hasSameTensorSize(Value beforePadding,
2884 tensor::ExtractSliceOp afterTrimming) const {
2885 // If the input to tensor::PadOp is a CastOp, try with both CastOp
2886 // result and CastOp operand.
2887 if (auto castOp = beforePadding.getDefiningOp<tensor::CastOp>())
2888 if (hasSameTensorSize(beforePadding: castOp.getSource(), afterTrimming))
2889 return true;
2890
2891 auto t1 = dyn_cast<RankedTensorType>(Val: beforePadding.getType());
2892 auto t2 = dyn_cast<RankedTensorType>(Val: afterTrimming.getType());
2893 // Only RankedTensorType supported.
2894 if (!t1 || !t2)
2895 return false;
2896 // Rank of both values must be the same.
2897 if (t1.getRank() != t2.getRank())
2898 return false;
2899
2900 // All static dimensions must be the same. Mixed cases (e.g., dimension
2901 // static in `t1` but dynamic in `t2`) are not supported.
2902 for (unsigned i = 0; i < t1.getRank(); ++i) {
2903 if (t1.isDynamicDim(idx: i) != t2.isDynamicDim(idx: i))
2904 return false;
2905 if (!t1.isDynamicDim(idx: i) && t1.getDimSize(idx: i) != t2.getDimSize(idx: i))
2906 return false;
2907 }
2908
2909 // Nothing more to check if all dimensions are static.
2910 if (t1.getNumDynamicDims() == 0)
2911 return true;
2912
2913 // All dynamic sizes must be the same. The only supported case at the
2914 // moment is when `beforePadding` is an ExtractSliceOp (or a cast
2915 // thereof).
2916
2917 // Apart from CastOp, only ExtractSliceOp is supported.
2918 auto beforeSlice = beforePadding.getDefiningOp<tensor::ExtractSliceOp>();
2919 if (!beforeSlice)
2920 return false;
2921
2922 assert(static_cast<size_t>(t1.getRank()) ==
2923 beforeSlice.getMixedSizes().size());
2924 assert(static_cast<size_t>(t2.getRank()) ==
2925 afterTrimming.getMixedSizes().size());
2926
2927 for (unsigned i = 0; i < t1.getRank(); ++i) {
2928 // Skip static dimensions.
2929 if (!t1.isDynamicDim(idx: i))
2930 continue;
2931 auto size1 = beforeSlice.getMixedSizes()[i];
2932 auto size2 = afterTrimming.getMixedSizes()[i];
2933
2934 // Case 1: Same value or same constant int.
2935 if (isEqualConstantIntOrValue(ofr1: size1, ofr2: size2))
2936 continue;
2937
2938 // Other cases: Take a deeper look at defining ops of values.
2939 auto v1 = llvm::dyn_cast_if_present<Value>(Val&: size1);
2940 auto v2 = llvm::dyn_cast_if_present<Value>(Val&: size2);
2941 if (!v1 || !v2)
2942 return false;
2943
2944 // Case 2: Both values are identical AffineMinOps. (Should not happen if
2945 // CSE is run.)
2946 auto minOp1 = v1.getDefiningOp<affine::AffineMinOp>();
2947 auto minOp2 = v2.getDefiningOp<affine::AffineMinOp>();
2948 if (minOp1 && minOp2 && minOp1.getAffineMap() == minOp2.getAffineMap() &&
2949 minOp1.getOperands() == minOp2.getOperands())
2950 continue;
2951
2952 // Add additional cases as needed.
2953 }
2954
2955 // All tests passed.
2956 return true;
2957 }
2958};
2959
2960/// Returns the effective Pad value for the input op, provided it's a scalar.
2961///
2962/// Many Ops exhibit pad-like behaviour, but this isn't always explicit. If
2963/// this Op performs padding, retrieve the padding value provided that it's
2964/// a scalar and static/fixed for all the padded values. Returns an empty value
2965/// otherwise.
2966///
2967/// TODO: This is used twice (when checking vectorization pre-conditions and
2968/// when vectorizing). Cache results instead of re-running.
2969static Value getStaticPadVal(Operation *op) {
2970 if (!op)
2971 return {};
2972
2973 // 1. vector.broadcast (f32 -> vector <...xf32>) - return the value that's
2974 // being broadcast, provided that it's a scalar.
2975 if (auto bcast = llvm::dyn_cast<vector::BroadcastOp>(Val: op)) {
2976 auto source = bcast.getSource();
2977 if (llvm::dyn_cast<VectorType>(Val: source.getType()))
2978 return {};
2979
2980 return source;
2981 }
2982
2983 // 2. linalg.fill - use the scalar input value that used to fill the output
2984 // tensor.
2985 if (auto fill = llvm::dyn_cast<linalg::FillOp>(Val: op)) {
2986 return fill.getInputs()[0];
2987 }
2988
2989 // 3. tensor.generateOp - can't guarantee the value is fixed without
2990 // analysing, bail out.
2991 if (auto generate = llvm::dyn_cast<tensor::GenerateOp>(Val: op)) {
2992 return {};
2993 }
2994
2995 // 4. vector.transfer_write - inspect the input vector that's written from. If
2996 // if contains a single value that has been broadcast (e.g. via
2997 // vector.broadcast), extract it, fail otherwise.
2998 if (auto xferWrite = llvm::dyn_cast<vector::TransferWriteOp>(Val: op))
2999 return getStaticPadVal(op: xferWrite.getVector().getDefiningOp());
3000
3001 // 5. tensor.insert_slice - inspect the destination tensor. If it's larger
3002 // than the input tensor, then, provided it's constant, we'll extract the
3003 // value that was used to generate it (via e.g. linalg.fill), fail otherwise.
3004 // TODO: Clarify the semantics when the input tensor is larger than the
3005 // destination.
3006 if (auto slice = llvm::dyn_cast<tensor::InsertSliceOp>(Val: op))
3007 return getStaticPadVal(op: slice.getDest().getDefiningOp());
3008
3009 return {};
3010}
3011
3012static LogicalResult
3013vectorizeAsInsertSliceOp(RewriterBase &rewriter, tensor::InsertSliceOp sliceOp,
3014 ArrayRef<int64_t> inputVectorSizes,
3015 SmallVectorImpl<Value> &newResults) {
3016 // TODO: Introduce a parent class that will handle the insertion point update.
3017 OpBuilder::InsertionGuard g(rewriter);
3018 rewriter.setInsertionPoint(sliceOp);
3019
3020 TypedValue<RankedTensorType> source = sliceOp.getSource();
3021 auto sourceType = source.getType();
3022 auto resultType = sliceOp.getResultType();
3023
3024 Value padValue = getStaticPadVal(op: sliceOp);
3025
3026 if (!padValue) {
3027 auto elemType = sourceType.getElementType();
3028 padValue = arith::ConstantOp::create(builder&: rewriter, location: sliceOp.getLoc(), result: elemType,
3029 value: rewriter.getZeroAttr(type: elemType));
3030 }
3031
3032 // 2. Get the vector shape
3033 // Map each source dim to its corresponding (non-dropped) result dim: for a
3034 // rank-reducing slice, dropped dims need not be the trailing ones.
3035 llvm::SmallBitVector droppedDims = sliceOp.getDroppedDims();
3036 SmallVector<int64_t> resultDimsForSourceDims;
3037 resultDimsForSourceDims.reserve(N: sourceType.getRank());
3038 for (int64_t resultDim = 0, end = resultType.getRank(); resultDim < end;
3039 ++resultDim)
3040 if (!droppedDims[resultDim])
3041 resultDimsForSourceDims.push_back(Elt: resultDim);
3042 assert(resultDimsForSourceDims.size() ==
3043 static_cast<size_t>(sourceType.getRank()) &&
3044 "expected one non-dropped result dim per source dim");
3045
3046 SmallVector<int64_t> vecShape;
3047 for (int64_t i = 0, end = sourceType.getRank(); i < end; ++i) {
3048 if (!inputVectorSizes.empty()) {
3049 vecShape.push_back(Elt: inputVectorSizes[i]);
3050 } else if (!sourceType.isDynamicDim(idx: i)) {
3051 vecShape.push_back(Elt: sourceType.getDimSize(idx: i));
3052 } else if (!resultType.isDynamicDim(idx: resultDimsForSourceDims[i])) {
3053 // Source shape is not statically known, but result shape is.
3054 // Vectorize with size of result shape. This may be larger than the
3055 // source size.
3056 vecShape.push_back(Elt: resultType.getDimSize(idx: resultDimsForSourceDims[i]));
3057 } else {
3058 // Neither source nor result dim of padOp is static. Cannot vectorize
3059 // the copy.
3060 return failure();
3061 }
3062 }
3063 auto vecType = VectorType::get(shape: vecShape, elementType: sourceType.getElementType());
3064
3065 // 3. Generate TransferReadOp + TransferWriteOp
3066 auto loc = sliceOp.getLoc();
3067
3068 // Create read
3069 SmallVector<Value> readIndices(
3070 vecType.getRank(), arith::ConstantIndexOp::create(builder&: rewriter, location: loc, value: 0));
3071 Value read = mlir::vector::createReadOrMaskedRead(
3072 builder&: rewriter, loc, source, vecToReadTy: vecType, padValue,
3073 /*useInBoundsInsteadOfMasking=*/inputVectorSizes.empty());
3074
3075 // Create write
3076 auto writeIndices =
3077 getValueOrCreateConstantIndexOp(b&: rewriter, loc, valueOrAttrVec: sliceOp.getMixedOffsets());
3078 // For a rank-reducing slice the vector need not cover the trailing result
3079 // dims, so state which result dim each vector dim writes to.
3080 AffineMap writeMap;
3081 if (sourceType.getRank() != resultType.getRank()) {
3082 SmallVector<AffineExpr> exprs;
3083 for (int64_t resultDim : resultDimsForSourceDims)
3084 exprs.push_back(Elt: rewriter.getAffineDimExpr(position: resultDim));
3085 writeMap = AffineMap::get(dimCount: resultType.getRank(), /*symbolCount=*/0, results: exprs,
3086 context: rewriter.getContext());
3087 }
3088
3089 Operation *write = vector::createWriteOrMaskedWrite(
3090 builder&: rewriter, loc, vecToStore: read, dest: sliceOp.getDest(), writeIndices,
3091 useInBoundsInsteadOfMasking: inputVectorSizes.empty(), permutationMap: writeMap);
3092
3093 // 4. Finalize
3094 newResults.push_back(Elt: write->getResult(idx: 0));
3095
3096 return success();
3097}
3098
3099/// Rewrite use of tensor::PadOp result in InsertSliceOp. E.g.:
3100/// ```
3101/// %0 = tensor.pad %src ... : tensor<?x?xf32> to tensor<17x5xf32>
3102/// %r = tensor.insert_slice %0
3103/// into %dest[%a, %b, 0, 0] [1, 1, 17, 5] [1, 1, 1, 1]
3104/// : tensor<17x5xf32> into tensor<?x?x17x5xf32>
3105/// ```
3106/// is rewritten to:
3107/// ```
3108/// %0 = vector.transfer_read %src[%c0, %c0], %padding
3109/// : tensor<?x?xf32>, vector<17x5xf32>
3110/// %r = vector.transfer_write %0, %dest[%a, %b, %c0, %c0]
3111/// {in_bounds = [true, true]} : vector<17x5xf32>, tensor<?x?x17x5xf32>
3112/// ```
3113///
3114/// This rewrite is possible if:
3115/// - Low padding is static 0.
3116/// - `padOp` result shape is static.
3117/// - The entire padded tensor is inserted.
3118/// (Implies that sizes of `insertOp` are all static.)
3119/// - Only unit strides in `insertOp`.
3120/// - Single, scalar padding value.
3121/// - `padOp` result not used as destination.
3122struct PadOpVectorizationWithInsertSlicePattern
3123 : public VectorizePadOpUserPattern<tensor::InsertSliceOp> {
3124 using VectorizePadOpUserPattern<
3125 tensor::InsertSliceOp>::VectorizePadOpUserPattern;
3126
3127 LogicalResult rewriteUser(PatternRewriter &rewriter, tensor::PadOp padOp,
3128 tensor::InsertSliceOp insertOp) const override {
3129 // Low padding must be static 0.
3130 if (!padOp.hasZeroLowPad())
3131 return failure();
3132 // Only unit stride supported.
3133 if (!insertOp.hasUnitStride())
3134 return failure();
3135 // Pad value must be a constant.
3136 auto padValue = padOp.getConstantPaddingValue();
3137 if (!padValue)
3138 return failure();
3139 // Dynamic shapes not supported.
3140 if (!cast<ShapedType>(Val: padOp.getResult().getType()).hasStaticShape())
3141 return failure();
3142 // Pad result not used as destination.
3143 if (insertOp.getDest() == padOp.getResult())
3144 return failure();
3145
3146 auto vecType = VectorType::get(shape: padOp.getType().getShape(),
3147 elementType: padOp.getType().getElementType());
3148 unsigned vecRank = vecType.getRank();
3149 unsigned tensorRank = insertOp.getType().getRank();
3150
3151 // Check if sizes match: Insert the entire tensor into most minor dims.
3152 // (No permutations allowed.)
3153 SmallVector<int64_t> expectedSizes(tensorRank - vecRank, 1);
3154 expectedSizes.append(in_start: vecType.getShape().begin(), in_end: vecType.getShape().end());
3155 if (!llvm::all_of(
3156 Range: llvm::zip(t: insertOp.getMixedSizes(), u&: expectedSizes), P: [](auto it) {
3157 return getConstantIntValue(std::get<0>(it)) == std::get<1>(it);
3158 }))
3159 return failure();
3160
3161 // Insert the TransferReadOp and TransferWriteOp at the position of the
3162 // InsertSliceOp.
3163 rewriter.setInsertionPoint(insertOp);
3164
3165 // Generate TransferReadOp: Read entire source tensor and add high
3166 // padding.
3167 SmallVector<Value> readIndices(
3168 vecRank, arith::ConstantIndexOp::create(builder&: rewriter, location: padOp.getLoc(), value: 0));
3169 auto read = vector::TransferReadOp::create(builder&: rewriter, location: padOp.getLoc(),
3170 vectorType: vecType, source: padOp.getSource(),
3171 indices: readIndices, padding: padValue);
3172
3173 // Generate TransferWriteOp: Write to InsertSliceOp's dest tensor at
3174 // specified offsets. Write is fully in-bounds because a InsertSliceOp's
3175 // source must fit into the destination at the specified offsets.
3176 auto writeIndices = getValueOrCreateConstantIndexOp(
3177 b&: rewriter, loc: padOp.getLoc(), valueOrAttrVec: insertOp.getMixedOffsets());
3178 SmallVector<bool> inBounds(vecRank, true);
3179 rewriter.replaceOpWithNewOp<vector::TransferWriteOp>(
3180 op: insertOp, args&: read, args: insertOp.getDest(), args&: writeIndices,
3181 args: ArrayRef<bool>{inBounds});
3182
3183 return success();
3184 }
3185};
3186
3187void mlir::linalg::populatePadOpVectorizationPatterns(
3188 RewritePatternSet &patterns, PatternBenefit baseBenefit) {
3189 patterns.add<PadOpVectorizationWithTransferReadPattern,
3190 PadOpVectorizationWithTransferWritePattern,
3191 PadOpVectorizationWithInsertSlicePattern>(
3192 arg: patterns.getContext(), args: baseBenefit.getBenefit() + 1);
3193}
3194
3195//----------------------------------------------------------------------------//
3196// Forwarding patterns
3197//----------------------------------------------------------------------------//
3198
3199/// Check whether there is any interleaved use of any `values` between
3200/// `firstOp` and `secondOp`. Conservatively return `true` if any op or value
3201/// is in a different block.
3202static bool mayExistInterleavedUses(Operation *firstOp, Operation *secondOp,
3203 ValueRange values) {
3204 if (firstOp->getBlock() != secondOp->getBlock() ||
3205 !firstOp->isBeforeInBlock(other: secondOp)) {
3206 LDBG() << "interleavedUses precondition failed, firstOp: " << *firstOp
3207 << ", second op: " << *secondOp;
3208 return true;
3209 }
3210 for (auto v : values) {
3211 for (auto &u : v.getUses()) {
3212 Operation *owner = u.getOwner();
3213 if (owner == firstOp || owner == secondOp)
3214 continue;
3215 // TODO: this is too conservative, use dominance info in the future.
3216 if (owner->getBlock() == firstOp->getBlock() &&
3217 (owner->isBeforeInBlock(other: firstOp) || secondOp->isBeforeInBlock(other: owner)))
3218 continue;
3219 LDBG() << " found interleaved op " << *owner << ", firstOp: " << *firstOp
3220 << ", second op: " << *secondOp;
3221 return true;
3222 }
3223 }
3224 return false;
3225}
3226
3227/// Return the unique subview use of `v` if it is indeed unique, null
3228/// otherwise.
3229static memref::SubViewOp getSubViewUseIfUnique(Value v) {
3230 memref::SubViewOp subViewOp;
3231 for (auto &u : v.getUses()) {
3232 if (auto newSubViewOp = dyn_cast<memref::SubViewOp>(Val: u.getOwner())) {
3233 if (subViewOp)
3234 return memref::SubViewOp();
3235 subViewOp = newSubViewOp;
3236 }
3237 }
3238 return subViewOp;
3239}
3240
3241/// TODO: use interfaces, side-effects and aliasing analysis as appropriate,
3242/// when available.
3243LogicalResult LinalgCopyVTRForwardingPattern::matchAndRewrite(
3244 vector::TransferReadOp xferOp, PatternRewriter &rewriter) const {
3245
3246 // TODO: support mask.
3247 if (xferOp.getMask())
3248 return rewriter.notifyMatchFailure(arg&: xferOp, msg: "unsupported mask");
3249
3250 // Transfer into `view`.
3251 Value viewOrAlloc = xferOp.getBase();
3252 if (!viewOrAlloc.getDefiningOp<memref::ViewOp>() &&
3253 !viewOrAlloc.getDefiningOp<memref::AllocOp>())
3254 return rewriter.notifyMatchFailure(arg&: xferOp, msg: "source not a view or alloc");
3255
3256 // Ensure there is exactly one subview of `viewOrAlloc` defining `subView`.
3257 memref::SubViewOp subViewOp = getSubViewUseIfUnique(v: viewOrAlloc);
3258 if (!subViewOp)
3259 return rewriter.notifyMatchFailure(arg&: xferOp, msg: "no subview found");
3260 Value subView = subViewOp.getResult();
3261
3262 // Find the copy into `subView` without interleaved uses.
3263 memref::CopyOp copyOp;
3264 for (auto &u : subView.getUses()) {
3265 if (auto newCopyOp = dyn_cast<memref::CopyOp>(Val: u.getOwner())) {
3266 assert(isa<MemRefType>(newCopyOp.getTarget().getType()));
3267 if (newCopyOp.getTarget() != subView)
3268 continue;
3269 if (mayExistInterleavedUses(firstOp: newCopyOp, secondOp: xferOp, values: {viewOrAlloc, subView}))
3270 continue;
3271 copyOp = newCopyOp;
3272 break;
3273 }
3274 }
3275 if (!copyOp)
3276 return rewriter.notifyMatchFailure(arg&: xferOp, msg: "no copy found");
3277
3278 // Find the fill into `viewOrAlloc` without interleaved uses before the
3279 // copy.
3280 FillOp maybeFillOp;
3281 for (auto &u : viewOrAlloc.getUses()) {
3282 if (auto newFillOp = dyn_cast<FillOp>(Val: u.getOwner())) {
3283 assert(isa<MemRefType>(newFillOp.output().getType()));
3284 if (newFillOp.output() != viewOrAlloc)
3285 continue;
3286 if (mayExistInterleavedUses(firstOp: newFillOp, secondOp: copyOp, values: {viewOrAlloc, subView}))
3287 continue;
3288 maybeFillOp = newFillOp;
3289 break;
3290 }
3291 }
3292 // Ensure padding matches.
3293 if (maybeFillOp && xferOp.getPadding() != maybeFillOp.value())
3294 return rewriter.notifyMatchFailure(arg&: xferOp,
3295 msg: "padding value does not match fill");
3296
3297 // `in` is the subview that memref.copy reads. Replace it.
3298 Value in = copyOp.getSource();
3299
3300 // memref.copy + linalg.fill can be used to create a padded local buffer.
3301 // The `masked` attribute is only valid on this padded buffer.
3302 // When forwarding to vector.transfer_read, the attribute must be reset
3303 // conservatively.
3304 auto vectorType = xferOp.getVectorType();
3305 Value res = vector::TransferReadOp::create(
3306 builder&: rewriter, location: xferOp.getLoc(), result: vectorType, base: in, indices: xferOp.getIndices(),
3307 permutation_map: xferOp.getPermutationMapAttr(), padding: xferOp.getPadding(), mask: xferOp.getMask(),
3308 in_bounds: rewriter.getBoolArrayAttr(
3309 values: SmallVector<bool>(vectorType.getRank(), false)));
3310
3311 if (maybeFillOp)
3312 rewriter.eraseOp(op: maybeFillOp);
3313 rewriter.eraseOp(op: copyOp);
3314 rewriter.replaceOp(op: xferOp, newValues: res);
3315
3316 return success();
3317}
3318
3319/// TODO: use interfaces, side-effects and aliasing analysis as appropriate,
3320/// when available.
3321LogicalResult LinalgCopyVTWForwardingPattern::matchAndRewrite(
3322 vector::TransferWriteOp xferOp, PatternRewriter &rewriter) const {
3323 // TODO: support mask.
3324 if (xferOp.getMask())
3325 return rewriter.notifyMatchFailure(arg&: xferOp, msg: "unsupported mask");
3326
3327 // Transfer into `viewOrAlloc`.
3328 Value viewOrAlloc = xferOp.getBase();
3329 if (!viewOrAlloc.getDefiningOp<memref::ViewOp>() &&
3330 !viewOrAlloc.getDefiningOp<memref::AllocOp>())
3331 return rewriter.notifyMatchFailure(arg&: xferOp, msg: "source not a view or alloc");
3332
3333 // Ensure there is exactly one subview of `viewOrAlloc` defining `subView`.
3334 memref::SubViewOp subViewOp = getSubViewUseIfUnique(v: viewOrAlloc);
3335 if (!subViewOp)
3336 return rewriter.notifyMatchFailure(arg&: xferOp, msg: "no subview found");
3337 Value subView = subViewOp.getResult();
3338
3339 // Find the copy from `subView` without interleaved uses.
3340 memref::CopyOp copyOp;
3341 for (auto &u : subViewOp.getResult().getUses()) {
3342 if (auto newCopyOp = dyn_cast<memref::CopyOp>(Val: u.getOwner())) {
3343 if (newCopyOp.getSource() != subView)
3344 continue;
3345 if (mayExistInterleavedUses(firstOp: xferOp, secondOp: newCopyOp, values: {viewOrAlloc, subView}))
3346 continue;
3347 copyOp = newCopyOp;
3348 break;
3349 }
3350 }
3351 if (!copyOp)
3352 return rewriter.notifyMatchFailure(arg&: xferOp, msg: "no copy found");
3353
3354 // `out` is the subview copied into that we replace.
3355 assert(isa<MemRefType>(copyOp.getTarget().getType()));
3356 Value out = copyOp.getTarget();
3357
3358 // Forward vector.transfer into copy.
3359 // memref.copy + linalg.fill can be used to create a padded local buffer.
3360 // The `masked` attribute is only valid on this padded buffer.
3361 // When forwarding to vector.transfer_write, the attribute must be reset
3362 // conservatively.
3363 auto vector = xferOp.getVector();
3364 vector::TransferWriteOp::create(
3365 builder&: rewriter, location: xferOp.getLoc(), vector, dest: out, indices: xferOp.getIndices(),
3366 permutationMapAttr: xferOp.getPermutationMapAttr(), mask: xferOp.getMask(),
3367 inBoundsAttr: rewriter.getBoolArrayAttr(values: SmallVector<bool>(
3368 dyn_cast<VectorType>(Val: vector.getType()).getRank(), false)));
3369
3370 rewriter.eraseOp(op: copyOp);
3371 rewriter.eraseOp(op: xferOp);
3372
3373 return success();
3374}
3375
3376//===----------------------------------------------------------------------===//
3377// Convolution vectorization patterns
3378//===----------------------------------------------------------------------===//
3379
3380template <int N>
3381static void bindShapeDims(ShapedType shapedType) {}
3382
3383template <int N, typename IntTy, typename... IntTy2>
3384static void bindShapeDims(ShapedType shapedType, IntTy &val, IntTy2 &...vals) {
3385 val = shapedType.getShape()[N];
3386 bindShapeDims<N + 1, IntTy2 &...>(shapedType, vals...);
3387}
3388
3389/// Bind a pack of int& to the leading dimensions of shapedType.getShape().
3390template <typename... IntTy>
3391static void bindShapeDims(ShapedType shapedType, IntTy &...vals) {
3392 bindShapeDims<0>(shapedType, vals...);
3393}
3394
3395/// Match 1D convolution or pooling operations and return their dilations and
3396/// strides. Returns std::nullopt for unrecognized ops.
3397static std::optional<DilationsAndStrides> match1DConvPoolOp(LinalgOp op) {
3398#define MATCH_1D_CONV_POOL_OP(ConvOpTy) \
3399 if (auto convParams = matchConvolutionOpOfType<ConvOpTy>(op)) \
3400 return convParams;
3401
3402 // 1D Convolution ops.
3403 MATCH_1D_CONV_POOL_OP(linalg::Conv1DOp);
3404 MATCH_1D_CONV_POOL_OP(linalg::Conv1DNwcWcfOp);
3405 MATCH_1D_CONV_POOL_OP(linalg::Conv1DNcwFcwOp);
3406 // Depthwise 1D Convolution ops.
3407 // Note: Only NWC layout without channel multiplier is supported.
3408 // DepthwiseConv1DNcwCwOp (NCW) and DepthwiseConv1DNwcWcmOp (with multiplier)
3409 // are not supported.
3410 MATCH_1D_CONV_POOL_OP(linalg::DepthwiseConv1DNwcWcOp);
3411 // 1D Pooling ops (NWC layout).
3412 MATCH_1D_CONV_POOL_OP(linalg::PoolingNwcSumOp);
3413 MATCH_1D_CONV_POOL_OP(linalg::PoolingNwcMaxOp);
3414 MATCH_1D_CONV_POOL_OP(linalg::PoolingNwcMaxUnsignedOp);
3415 MATCH_1D_CONV_POOL_OP(linalg::PoolingNwcMinOp);
3416 MATCH_1D_CONV_POOL_OP(linalg::PoolingNwcMinUnsignedOp);
3417 // 1D Pooling ops (NCW layout).
3418 MATCH_1D_CONV_POOL_OP(linalg::PoolingNcwSumOp);
3419 MATCH_1D_CONV_POOL_OP(linalg::PoolingNcwMaxOp);
3420
3421#undef MATCH_1D_CONV_POOL_OP
3422
3423 return std::nullopt;
3424}
3425
3426namespace {
3427/// Generate a vector implementation for either:
3428/// ```
3429/// Op def: ( w, kw )
3430/// Iters: ({Par(), Red()})
3431/// Layout: {{w + kw}, {kw}, {w}}
3432/// ```
3433/// kw is unrolled.
3434///
3435/// or
3436///
3437/// ```
3438/// Op def: ( n, w, c, kw, f )
3439/// Iters: ({Par(), Par(), Par(), Red(), Red()})
3440/// Layout: {{n, strideW * w + dilationW * kw, c}, {kw, c, f}, {n, w, f}}
3441/// ```
3442/// kw is unrolled, w is unrolled iff dilationW > 1.
3443///
3444/// or
3445///
3446/// ```
3447/// Op def: ( n, c, w, f, kw )
3448/// Iters: ({Par(), Par(), Par(), Red(), Red()})
3449/// Layout: {{n, c, strideW * w + dilationW * kw}, {f, c, kw}, {n, f, w}}
3450/// ```
3451/// kw is unrolled, w is unrolled iff dilationW > 1.
3452///
3453/// or
3454///
3455/// ```
3456/// Op def: ( n, w, c, kw )
3457/// Iters: ({Par(), Par(), Par(), Red()})
3458/// Layout: {{n, strideW * w + dilationW * kw, c}, {kw, c}, {n, w, c}}
3459/// ```
3460/// kw is unrolled, w is unrolled iff dilationW > 1.
3461struct Conv1DGenerator
3462 : public StructuredGenerator<LinalgOp, utils::IteratorType> {
3463 /// Factory method to create a Conv1DGenerator. Returns failure if the
3464 /// operation doesn't have valid strides/dilations.
3465 static FailureOr<Conv1DGenerator> create(RewriterBase &rewriter,
3466 LinalgOp linalgOp) {
3467 // Try to match a 1D conv/pool op using matchConvolutionOpOfType. This
3468 // works for both named ops and generic ops that match their semantics.
3469 std::optional<DilationsAndStrides> convParams = match1DConvPoolOp(op: linalgOp);
3470 if (!convParams)
3471 return failure();
3472
3473 int strideW = static_cast<int>(convParams->strides.front());
3474 int dilationW = static_cast<int>(convParams->dilations.front());
3475 return Conv1DGenerator(rewriter, linalgOp, strideW, dilationW);
3476 }
3477
3478private:
3479 Conv1DGenerator(RewriterBase &rewriter, LinalgOp linalgOp, int strideW,
3480 int dilationW)
3481 : StructuredGenerator<LinalgOp, utils::IteratorType>(rewriter, linalgOp),
3482 strideW(strideW), dilationW(dilationW) {
3483
3484 lhsShaped = linalgOp.getDpsInputOperand(i: 0)->get();
3485 rhsShaped = linalgOp.getDpsInputOperand(i: 1)->get();
3486 resShaped = linalgOp.getDpsInitOperand(i: 0)->get();
3487 lhsShapedType = dyn_cast<ShapedType>(Val: lhsShaped.getType());
3488 rhsShapedType = dyn_cast<ShapedType>(Val: rhsShaped.getType());
3489 resShapedType = dyn_cast<ShapedType>(Val: resShaped.getType());
3490
3491 Operation *reduceOp = matchLinalgReduction(outputOperand: linalgOp.getDpsInitOperand(i: 0));
3492 redOp = reduceOp->getName().getIdentifier();
3493
3494 setConvOperationKind(reduceOp);
3495
3496 auto maybeKind = getCombinerOpKind(combinerOp: reduceOp);
3497 reductionKind = maybeKind.value();
3498 }
3499
3500public:
3501 /// Generate a vector implementation for:
3502 /// ```
3503 /// Op def: ( w, kw )
3504 /// Iters: ({Par(), Red()})
3505 /// Layout: {{w + kw}, {kw}, {w}}
3506 /// ```
3507 /// kw is always unrolled.
3508 ///
3509 /// or
3510 ///
3511 /// ```
3512 /// Op def: ( n, w, c, kw, f )
3513 /// Iters: ({Par(), Par(), Par(), Red(), Red()})
3514 /// Layout: {{n, strideW * w + dilationW * kw, c}, {kw, c, f}, {n, w, f}}
3515 /// ```
3516 /// kw is always unrolled.
3517 /// TODO: w (resp. kw) is unrolled when the strideW ( resp. dilationW) is
3518 /// > 1.
3519 FailureOr<Operation *> conv(Conv1DOpOrder conv1DOpOrder) {
3520 int64_t nSize, wSize, cSize, kwSize, fSize;
3521 SmallVector<int64_t, 3> lhsShape, rhsShape, resShape;
3522 bool isSingleChanneled = (conv1DOpOrder == Conv1DOpOrder::W);
3523 switch (conv1DOpOrder) {
3524 case Conv1DOpOrder::W:
3525 // Initialize unused dimensions
3526 nSize = fSize = cSize = 0;
3527 // out{W}
3528 bindShapeDims(shapedType: resShapedType, vals&: wSize);
3529 // kernel{kw}
3530 bindShapeDims(shapedType: rhsShapedType, vals&: kwSize);
3531 lhsShape = {// iw = ow + kw - 1
3532 // (i.e. 16 convolved with 3 -> 14)
3533 (wSize + kwSize - 1)};
3534 rhsShape = {kwSize};
3535 resShape = {wSize};
3536 break;
3537 case Conv1DOpOrder::Nwc:
3538 // out{n, w, f}
3539 bindShapeDims(shapedType: resShapedType, vals&: nSize, vals&: wSize, vals&: fSize);
3540 switch (oper) {
3541 case ConvOperationKind::Conv:
3542 // kernel{kw, c, f}
3543 bindShapeDims(shapedType: rhsShapedType, vals&: kwSize, vals&: cSize);
3544 break;
3545 case ConvOperationKind::Pool:
3546 // kernel{kw}
3547 bindShapeDims(shapedType: rhsShapedType, vals&: kwSize);
3548 cSize = fSize;
3549 break;
3550 }
3551 lhsShape = {nSize,
3552 // iw = ow * sw + kw * dw - 1
3553 // (i.e. 16 convolved with 3 (@stride 1 dilation 1) -> 14)
3554 // Perform the proper inclusive -> exclusive -> inclusive.
3555 ((wSize - 1) * strideW + 1) + ((kwSize - 1) * dilationW + 1) -
3556 1,
3557 cSize};
3558 switch (oper) {
3559 case ConvOperationKind::Conv:
3560 rhsShape = {kwSize, cSize, fSize};
3561 break;
3562 case ConvOperationKind::Pool:
3563 rhsShape = {kwSize};
3564 break;
3565 }
3566 resShape = {nSize, wSize, fSize};
3567 break;
3568 case Conv1DOpOrder::Ncw:
3569 // out{n, f, w}
3570 bindShapeDims(shapedType: resShapedType, vals&: nSize, vals&: fSize, vals&: wSize);
3571 switch (oper) {
3572 case ConvOperationKind::Conv:
3573 // kernel{f, c, kw}
3574 bindShapeDims(shapedType: rhsShapedType, vals&: fSize, vals&: cSize, vals&: kwSize);
3575 break;
3576 case ConvOperationKind::Pool:
3577 // kernel{kw}
3578 bindShapeDims(shapedType: rhsShapedType, vals&: kwSize);
3579 cSize = fSize;
3580 break;
3581 }
3582 lhsShape = {nSize, cSize,
3583 // iw = ow * sw + kw * dw - 1
3584 // (i.e. 16 convolved with 3 (@stride 1 dilation 1) -> 14)
3585 // Perform the proper inclusive -> exclusive -> inclusive.
3586 ((wSize - 1) * strideW + 1) + ((kwSize - 1) * dilationW + 1) -
3587 1};
3588 switch (oper) {
3589 case ConvOperationKind::Conv:
3590 rhsShape = {fSize, cSize, kwSize};
3591 break;
3592 case ConvOperationKind::Pool:
3593 rhsShape = {kwSize};
3594 break;
3595 }
3596 resShape = {nSize, fSize, wSize};
3597 break;
3598 }
3599
3600 vector::TransferWriteOp write;
3601 Value zero = arith::ConstantIndexOp::create(builder&: rewriter, location: loc, value: 0);
3602
3603 // w is unrolled (i.e. wSizeStep == 1) iff strideW > 1.
3604 // When strideW == 1, we can batch the contiguous loads and avoid
3605 // unrolling
3606 int64_t wSizeStep = strideW == 1 ? wSize : 1;
3607
3608 Type lhsEltType = lhsShapedType.getElementType();
3609 Type rhsEltType = rhsShapedType.getElementType();
3610 Type resEltType = resShapedType.getElementType();
3611 auto lhsType = VectorType::get(shape: lhsShape, elementType: lhsEltType);
3612 auto rhsType = VectorType::get(shape: rhsShape, elementType: rhsEltType);
3613 auto resType = VectorType::get(shape: resShape, elementType: resEltType);
3614 // Zero padding with the corresponding dimensions for lhs, rhs and res.
3615 SmallVector<Value> lhsPadding(lhsShape.size(), zero);
3616 SmallVector<Value> rhsPadding(rhsShape.size(), zero);
3617 SmallVector<Value> resPadding(resShape.size(), zero);
3618
3619 // Read the whole lhs, rhs and res in one shot (with zero padding).
3620 Value lhs = vector::TransferReadOp::create(
3621 builder&: rewriter, location: loc, vectorType: lhsType, source: lhsShaped, indices: lhsPadding,
3622 /*padding=*/arith::getZeroConstant(builder&: rewriter, loc, type: lhsEltType));
3623 // This is needed only for Conv.
3624 Value rhs = nullptr;
3625 if (oper == ConvOperationKind::Conv)
3626 rhs = vector::TransferReadOp::create(
3627 builder&: rewriter, location: loc, vectorType: rhsType, source: rhsShaped, indices: rhsPadding,
3628 /*padding=*/arith::getZeroConstant(builder&: rewriter, loc, type: rhsEltType));
3629 Value res = vector::TransferReadOp::create(
3630 builder&: rewriter, location: loc, vectorType: resType, source: resShaped, indices: resPadding,
3631 /*padding=*/arith::getZeroConstant(builder&: rewriter, loc, type: resEltType));
3632
3633 // The base vectorization case for channeled convolution is input:
3634 // {n,w,c}, weight: {kw,c,f}, output: {n,w,f}. To reuse the base pattern
3635 // vectorization case, we do pre transpose on input, weight, and output.
3636 switch (conv1DOpOrder) {
3637 case Conv1DOpOrder::W:
3638 case Conv1DOpOrder::Nwc:
3639 // Base case, so no transposes necessary.
3640 break;
3641 case Conv1DOpOrder::Ncw: {
3642 // To match base vectorization case, we pre-transpose current case.
3643 // ncw -> nwc
3644 static constexpr std::array<int64_t, 3> permLhs = {0, 2, 1};
3645 lhs = vector::TransposeOp::create(builder&: rewriter, location: loc, vector: lhs, permutation: permLhs);
3646 // fcw -> wcf
3647 static constexpr std::array<int64_t, 3> permRhs = {2, 1, 0};
3648
3649 // This is needed only for Conv.
3650 if (oper == ConvOperationKind::Conv)
3651 rhs = vector::TransposeOp::create(builder&: rewriter, location: loc, vector: rhs, permutation: permRhs);
3652 // nfw -> nwf
3653 static constexpr std::array<int64_t, 3> permRes = {0, 2, 1};
3654 res = vector::TransposeOp::create(builder&: rewriter, location: loc, vector: res, permutation: permRes);
3655 break;
3656 }
3657 }
3658
3659 //===------------------------------------------------------------------===//
3660 // Begin vector-only rewrite part
3661 //===------------------------------------------------------------------===//
3662 // Unroll along kw and read slices of lhs and rhs.
3663 SmallVector<Value> lhsVals, rhsVals, resVals;
3664 lhsVals = extractConvInputSlices(rewriter, loc, input: lhs, nSize, wSize, cSize,
3665 kwSize, strideW, dilationW, wSizeStep,
3666 isSingleChanneled);
3667 // Do not do for pooling.
3668 if (oper == ConvOperationKind::Conv)
3669 rhsVals = extractConvFilterSlices(rewriter, loc, filter: rhs, kwSize);
3670 resVals = extractConvResultSlices(rewriter, loc, res, nSize, wSize, fSize,
3671 wSizeStep, isSingleChanneled);
3672
3673 auto linearIndex = [&](int64_t kw, int64_t w) {
3674 return kw * (wSize / wSizeStep) + w;
3675 };
3676
3677 // Compute contraction: O{n, w, f} += I{n, sw * w + dw * kw, c} * F{c, f}
3678 // or perform outerproduct for non-channeled convolution or perform simple
3679 // arith operation for pooling
3680 for (int64_t kw = 0; kw < kwSize; ++kw) {
3681 for (int64_t w = 0; w < wSize; w += wSizeStep) {
3682 switch (oper) {
3683 case ConvOperationKind::Conv:
3684 if (isSingleChanneled) {
3685 resVals[w] = conv1dSliceAsOuterProduct(rewriter, loc,
3686 lhs: lhsVals[linearIndex(kw, w)],
3687 rhs: rhsVals[kw], res: resVals[w]);
3688 } else {
3689 resVals[w] = conv1dSliceAsContraction(rewriter, loc,
3690 lhs: lhsVals[linearIndex(kw, w)],
3691 rhs: rhsVals[kw], res: resVals[w]);
3692 }
3693 break;
3694 case ConvOperationKind::Pool:
3695 resVals[w] = pool1dSlice(rewriter, loc, lhs: lhsVals[linearIndex(kw, w)],
3696 res: resVals[w]);
3697 break;
3698 }
3699 }
3700 }
3701
3702 res = insertConvResultSlices(rewriter, loc, res, wSize, wSizeStep, resVals,
3703 isSingleChanneled);
3704 //===------------------------------------------------------------------===//
3705 // End vector-only rewrite part
3706 //===------------------------------------------------------------------===//
3707
3708 // The base vectorization case for channeled convolution is output:
3709 // {n,w,f} To reuse the result from base pattern vectorization case, we
3710 // post transpose the base case result.
3711 switch (conv1DOpOrder) {
3712 case Conv1DOpOrder::W:
3713 case Conv1DOpOrder::Nwc:
3714 // Base case, so no transposes necessary.
3715 break;
3716 case Conv1DOpOrder::Ncw: {
3717 // nwf -> nfw
3718 static constexpr std::array<int64_t, 3> perm = {0, 2, 1};
3719 res = vector::TransposeOp::create(builder&: rewriter, location: loc, vector: res, permutation: perm);
3720 break;
3721 }
3722 }
3723
3724 return vector::TransferWriteOp::create(builder&: rewriter, location: loc, vector: res, dest: resShaped,
3725 indices: resPadding)
3726 .getOperation();
3727 }
3728
3729 // Promote `val` to the element type of `ty` using `castOp`.
3730 Value promote(RewriterBase &rewriter, Location loc, Value val, Type ty,
3731 Operation *castOp) {
3732 const Type dstElementType = getElementTypeOrSelf(type: ty);
3733 if (getElementTypeOrSelf(type: val.getType()) == dstElementType)
3734 return val;
3735
3736 assert(castOp && "expected a payload cast for promoted operand");
3737
3738 // Handle both shaped as well as scalar types.
3739 Type dstType;
3740 if (auto shapedType = dyn_cast<ShapedType>(Val: val.getType()))
3741 dstType = shapedType.cloneWith(shape: std::nullopt, elementType: dstElementType);
3742 else
3743 dstType = dstElementType;
3744
3745 OperationState state(loc, castOp->getName().getIdentifier(), val, dstType,
3746 castOp->getDiscardableAttrDictionary().getValue());
3747 state.propertiesAttr = castOp->getPropertiesAsAttribute();
3748 return rewriter.create(state)->getResult(idx: 0);
3749 }
3750
3751 // Create a contraction: lhs{n, w, c} * rhs{c, f} -> res{n, w, f}
3752 Value conv1dSliceAsContraction(RewriterBase &rewriter, Location loc,
3753 Value lhs, Value rhs, Value res) {
3754 vector::IteratorType par = vector::IteratorType::parallel;
3755 vector::IteratorType red = vector::IteratorType::reduction;
3756 AffineExpr n, w, f, c;
3757 bindDims(ctx, exprs&: n, exprs&: w, exprs&: f, exprs&: c);
3758 lhs = promote(rewriter, loc, val: lhs, ty: res.getType(), castOp: lhsCastOp);
3759 rhs = promote(rewriter, loc, val: rhs, ty: res.getType(), castOp: rhsCastOp);
3760 auto contrationOp = vector::ContractionOp::create(
3761 builder&: rewriter, location: loc, lhs, rhs, acc: res,
3762 /*indexingMaps=*/indexingExprs: MapList{{n, w, c}, {c, f}, {n, w, f}},
3763 /*iteratorTypes=*/ArrayRef<vector::IteratorType>{par, par, par, red});
3764 contrationOp.setKind(reductionKind);
3765 return contrationOp;
3766 }
3767
3768 // Create an outerproduct: lhs{w} * rhs{1} -> res{w} for single channel
3769 // convolution.
3770 Value conv1dSliceAsOuterProduct(RewriterBase &rewriter, Location loc,
3771 Value lhs, Value rhs, Value res) {
3772 lhs = promote(rewriter, loc, val: lhs, ty: res.getType(), castOp: lhsCastOp);
3773 rhs = promote(rewriter, loc, val: rhs, ty: res.getType(), castOp: rhsCastOp);
3774 return vector::OuterProductOp::create(builder&: rewriter, location: loc, resultType0: res.getType(), lhs,
3775 rhs, acc: res, kind: vector::CombiningKind::ADD);
3776 }
3777
3778 // Create a reduction: lhs{n, w, c} -> res{n, w, c}
3779 Value pool1dSlice(RewriterBase &rewriter, Location loc, Value lhs,
3780 Value res) {
3781 if (isPoolExt)
3782 lhs = rewriter.create(loc, opName: poolExtOp, operands: lhs, types: res.getType())->getResult(idx: 0);
3783 return rewriter
3784 .create(loc, opName: redOp, operands: ArrayRef<Value>{lhs, res}, types: res.getType())
3785 ->getResult(idx: 0);
3786 }
3787
3788 /// Generate a vector implementation for:
3789 /// ```
3790 /// Op def: ( n, w, c, kw)
3791 /// Iters: ({Par(), Par(), Par(), Red()})
3792 /// Layout: {{n, strideW * w + dilationW * kw, c}, {kw, c}, {n, w, c}}
3793 /// ```
3794 /// kw is always unrolled.
3795 /// TODO: w (resp. kw) is unrolled when the strideW ( resp. dilationW) is
3796 /// > 1.
3797 FailureOr<Operation *> depthwiseConv(uint64_t channelDimVecSize,
3798 bool channelDimScalableFlag,
3799 bool flatten) {
3800 bool scalableChDim = false;
3801 bool useMasking = false;
3802 int64_t nSize, wSize, cSize, kwSize;
3803 // kernel{kw, c}
3804 bindShapeDims(shapedType: rhsShapedType, vals&: kwSize, vals&: cSize);
3805 if (ShapedType::isDynamic(dValue: cSize)) {
3806 assert(channelDimVecSize != 0 && "Channel dim vec size must be > 0");
3807 cSize = channelDimVecSize;
3808 // Scalable vectors are only used when both conditions are met:
3809 // 1. channel dim is dynamic
3810 // 2. channelDimScalableFlag is set
3811 scalableChDim = channelDimScalableFlag;
3812 useMasking = true;
3813 }
3814
3815 assert(!(useMasking && flatten) &&
3816 "Unsupported flattened conv with dynamic shapes");
3817
3818 // out{n, w, c}
3819 bindShapeDims(shapedType: resShapedType, vals&: nSize, vals&: wSize);
3820
3821 vector::TransferWriteOp write;
3822 Value zero = arith::ConstantIndexOp::create(builder&: rewriter, location: loc, value: 0);
3823
3824 // w is unrolled (i.e. wSizeStep == 1) iff strideW > 1.
3825 // When strideW == 1, we can batch the contiguous loads and avoid
3826 // unrolling
3827 int64_t wSizeStep = strideW == 1 ? wSize : 1;
3828
3829 Type lhsEltType = lhsShapedType.getElementType();
3830 Type rhsEltType = rhsShapedType.getElementType();
3831 Type resEltType = resShapedType.getElementType();
3832 VectorType lhsType = VectorType::get(
3833 shape: {nSize,
3834 // iw = ow * sw + kw * dw - 1
3835 // (i.e. 16 convolved with 3 (@stride 1 dilation 1) -> 14)
3836 ((wSize - 1) * strideW + 1) + ((kwSize - 1) * dilationW + 1) - 1,
3837 cSize},
3838 elementType: lhsEltType, /*scalableDims=*/{false, false, scalableChDim});
3839 VectorType rhsType =
3840 VectorType::get(shape: {kwSize, cSize}, elementType: rhsEltType,
3841 /*scalableDims=*/{false, scalableChDim});
3842 VectorType resType =
3843 VectorType::get(shape: {nSize, wSize, cSize}, elementType: resEltType,
3844 /*scalableDims=*/{false, false, scalableChDim});
3845
3846 // Masks the input xfer Op along the channel dim, iff the corresponding
3847 // scalable flag is set.
3848 auto maybeMaskXferOp = [&](ArrayRef<int64_t> maskShape,
3849 ArrayRef<bool> scalableDims,
3850 Operation *opToMask) {
3851 if (!useMasking)
3852 return opToMask;
3853 auto maskType =
3854 VectorType::get(shape: maskShape, elementType: rewriter.getI1Type(), scalableDims);
3855
3856 SmallVector<bool> inBounds(maskShape.size(), true);
3857 auto xferOp = cast<VectorTransferOpInterface>(Val: opToMask);
3858 xferOp->setInherentAttr(
3859 name: rewriter.getStringAttr(bytes: xferOp.getInBoundsAttrName()),
3860 value: rewriter.getBoolArrayAttr(values: inBounds));
3861
3862 SmallVector<OpFoldResult> mixedDims = vector::getMixedSizesXfer(
3863 hasTensorSemantics: cast<LinalgOp>(Val: op).hasPureTensorSemantics(), xfer: opToMask, rewriter);
3864
3865 Value maskOp =
3866 vector::CreateMaskOp::create(builder&: rewriter, location: loc, type: maskType, mixedOperands: mixedDims);
3867
3868 return mlir::vector::maskOperation(builder&: rewriter, maskableOp: opToMask, mask: maskOp);
3869 };
3870
3871 // Read lhs slice of size {n, w * strideW + kw * dilationW, c} @ [0, 0,
3872 // 0].
3873 Value lhs = vector::TransferReadOp::create(
3874 builder&: rewriter, location: loc, vectorType: lhsType, source: lhsShaped, indices: ValueRange{zero, zero, zero},
3875 /*padding=*/arith::getZeroConstant(builder&: rewriter, loc, type: lhsEltType));
3876 auto *maybeMaskedLhs = maybeMaskXferOp(
3877 lhsType.getShape(), lhsType.getScalableDims(), lhs.getDefiningOp());
3878
3879 // Read rhs slice of size {kw, c} @ [0, 0].
3880 Value rhs = vector::TransferReadOp::create(
3881 builder&: rewriter, location: loc, vectorType: rhsType, source: rhsShaped, indices: ValueRange{zero, zero},
3882 /*padding=*/arith::getZeroConstant(builder&: rewriter, loc, type: rhsEltType));
3883 auto *maybeMaskedRhs = maybeMaskXferOp(
3884 rhsType.getShape(), rhsType.getScalableDims(), rhs.getDefiningOp());
3885
3886 // Read res slice of size {n, w, c} @ [0, 0, 0].
3887 Value res = vector::TransferReadOp::create(
3888 builder&: rewriter, location: loc, vectorType: resType, source: resShaped, indices: ValueRange{zero, zero, zero},
3889 /*padding=*/arith::getZeroConstant(builder&: rewriter, loc, type: resEltType));
3890 auto *maybeMaskedRes = maybeMaskXferOp(
3891 resType.getShape(), resType.getScalableDims(), res.getDefiningOp());
3892
3893 //===------------------------------------------------------------------===//
3894 // Begin vector-only rewrite part
3895 //===------------------------------------------------------------------===//
3896 // Unroll along kw and read slices of lhs and rhs.
3897 SmallVector<Value> lhsVals, rhsVals, resVals;
3898 SmallVector<int64_t> inOutSliceSizes = {nSize, wSizeStep, cSize};
3899 SmallVector<int64_t> inOutStrides = {1, 1, 1};
3900
3901 // Extract lhs slice of size {n, wSizeStep, c}
3902 // @ [0, sw * w + dw * kw, 0].
3903 for (int64_t kw = 0; kw < kwSize; ++kw) {
3904 for (int64_t w = 0; w < wSize; w += wSizeStep) {
3905 lhsVals.push_back(Elt: vector::ExtractStridedSliceOp::create(
3906 builder&: rewriter, location: loc, source: maybeMaskedLhs->getResult(idx: 0),
3907 /*offsets=*/ArrayRef<int64_t>{0, w * strideW + kw * dilationW, 0},
3908 sizes: inOutSliceSizes, strides: inOutStrides));
3909 }
3910 }
3911 // Extract rhs slice of size {c} @ [kw].
3912 for (int64_t kw = 0; kw < kwSize; ++kw) {
3913 rhsVals.push_back(
3914 Elt: vector::ExtractOp::create(builder&: rewriter, location: loc, source: maybeMaskedRhs->getResult(idx: 0),
3915 /*offsets=*/position: ArrayRef<int64_t>{kw}));
3916 }
3917 // Extract res slice: {n, wSizeStep, c} @ [0, w, 0].
3918 for (int64_t w = 0; w < wSize; w += wSizeStep) {
3919 resVals.push_back(Elt: vector::ExtractStridedSliceOp::create(
3920 builder&: rewriter, location: loc, source: maybeMaskedRes->getResult(idx: 0),
3921 /*offsets=*/ArrayRef<int64_t>{0, w, 0}, sizes: inOutSliceSizes,
3922 strides: inOutStrides));
3923 }
3924
3925 auto linearIndex = [&](int64_t kw, int64_t w) {
3926 return kw * (wSize / wSizeStep) + w;
3927 };
3928
3929 // Note - the scalable flags are ignored as flattening combined with
3930 // scalable vectorization is not supported.
3931 SmallVector<int64_t> inOutFlattenSliceSizes = {nSize, wSizeStep * cSize};
3932 auto lhsTypeAfterFlattening =
3933 VectorType::get(shape: inOutFlattenSliceSizes, elementType: lhsEltType);
3934 auto resTypeAfterFlattening =
3935 VectorType::get(shape: inOutFlattenSliceSizes, elementType: resEltType);
3936
3937 // Compute contraction: O{n, w, c} += I{n, sw * w + dw * kw, c} * F{c}
3938 for (int64_t kw = 0; kw < kwSize; ++kw) {
3939 for (int64_t w = 0; w < wSize; w += wSizeStep) {
3940 Value lhsVal = lhsVals[linearIndex(kw, w)];
3941 Value resVal = resVals[w];
3942 if (flatten) {
3943 // Flatten the input and output vectors (collapse the channel
3944 // dimension)
3945 lhsVal =
3946 vector::ShapeCastOp::create(builder&: rewriter, location: loc, result: lhsTypeAfterFlattening,
3947 source: lhsVals[linearIndex(kw, w)]);
3948 resVal = vector::ShapeCastOp::create(
3949 builder&: rewriter, location: loc, result: resTypeAfterFlattening, source: resVals[w]);
3950 }
3951 resVals[w] = depthwiseConv1dSliceAsMulAcc(rewriter, loc, lhs: lhsVal,
3952 rhs: rhsVals[kw], res: resVal, flatten);
3953 if (flatten) {
3954 // Un-flatten the output vector (restore the channel dimension)
3955 resVals[w] = vector::ShapeCastOp::create(
3956 builder&: rewriter, location: loc, result: VectorType::get(shape: inOutSliceSizes, elementType: resEltType),
3957 source: resVals[w]);
3958 }
3959 }
3960 }
3961
3962 // Its possible we failed to create the Fma.
3963 if (!llvm::all_of(Range&: resVals, P: [](Value v) { return v; })) {
3964 // Manually revert (in reverse order) to avoid leaving a bad IR state.
3965 for (auto &collection :
3966 {resVals, rhsVals, lhsVals, {res, rhs, lhs, zero}})
3967 for (Value v : collection)
3968 rewriter.eraseOp(op: v.getDefiningOp());
3969 return rewriter.notifyMatchFailure(arg&: op, msg: "failed to create FMA");
3970 }
3971
3972 // Write back res slice: {n, wSizeStep, c} @ [0, w, 0].
3973 // This does not depend on kw.
3974 for (int64_t w = 0; w < wSize; w += wSizeStep) {
3975 maybeMaskedRes = vector::InsertStridedSliceOp::create(
3976 builder&: rewriter, location: loc, valueToStore: resVals[w], dest: maybeMaskedRes->getResult(idx: 0),
3977 /*offsets=*/ArrayRef<int64_t>{0, w, 0},
3978 /*strides=*/ArrayRef<int64_t>{1, 1, 1});
3979 }
3980 //===------------------------------------------------------------------===//
3981 // End vector-only rewrite part
3982 //===------------------------------------------------------------------===//
3983
3984 // Write back res slice of size {n, w, c} @ [0, 0, 0].
3985 Operation *resOut = vector::TransferWriteOp::create(
3986 builder&: rewriter, location: loc, vector: maybeMaskedRes->getResult(idx: 0), dest: resShaped,
3987 indices: ValueRange{zero, zero, zero});
3988 return maybeMaskXferOp(resType.getShape(), resType.getScalableDims(),
3989 resOut);
3990 }
3991
3992 /// Lower:
3993 /// * lhs{n, w, c} * rhs{c} -> res{n, w, c} (flatten = false)
3994 /// * lhs{n, w * c} * rhs{c} -> res{n, w * c} (flatten = true)
3995 /// to MulAcc.
3996 Value depthwiseConv1dSliceAsMulAcc(RewriterBase &rewriter, Location loc,
3997 Value lhs, Value rhs, Value res,
3998 bool flatten) {
3999 auto rhsTy = cast<ShapedType>(Val: rhs.getType());
4000 auto resTy = cast<ShapedType>(Val: res.getType());
4001
4002 // TODO(suderman): Change this to use a vector.ima intrinsic.
4003 lhs = promote(rewriter, loc, val: lhs, ty: resTy, castOp: lhsCastOp);
4004
4005 if (flatten) {
4006 // NOTE: This following logic won't work for scalable vectors. For this
4007 // reason, "flattening" is not supported when shapes are dynamic (this
4008 // should be captured by one of the pre-conditions).
4009
4010 // There are two options for handling the filter:
4011 // * shape_cast(broadcast(filter))
4012 // * broadcast(shuffle(filter))
4013 // Opt for the option without shape_cast to simplify the codegen.
4014 auto rhsSize = cast<VectorType>(Val: rhs.getType()).getShape()[0];
4015 auto resSize = cast<VectorType>(Val: res.getType()).getShape()[1];
4016
4017 SmallVector<int64_t, 16> indices;
4018 for (int i = 0; i < resSize / rhsSize; ++i) {
4019 for (int j = 0; j < rhsSize; ++j)
4020 indices.push_back(Elt: j);
4021 }
4022
4023 rhs = vector::ShuffleOp::create(builder&: rewriter, location: loc, v1: rhs, v2: rhs, mask: indices);
4024 }
4025 // Broadcast the filter to match the output vector
4026 rhs = vector::BroadcastOp::create(builder&: rewriter, location: loc,
4027 result: resTy.clone(elementType: rhsTy.getElementType()), source: rhs);
4028
4029 rhs = promote(rewriter, loc, val: rhs, ty: resTy, castOp: rhsCastOp);
4030
4031 if (!lhs || !rhs)
4032 return nullptr;
4033
4034 if (isa<FloatType>(Val: resTy.getElementType()))
4035 return vector::FMAOp::create(builder&: rewriter, location: loc, lhs, rhs, acc: res);
4036
4037 auto mul = arith::MulIOp::create(builder&: rewriter, location: loc, lhs, rhs);
4038 return arith::AddIOp::create(builder&: rewriter, location: loc, lhs: mul, rhs: res);
4039 }
4040
4041 /// Entry point for non-channeled convolution:
4042 /// {{w + kw}, {kw}, {w}}
4043 FailureOr<Operation *> generateNonChanneledConv() {
4044 AffineExpr w, kw;
4045 bindDims(ctx, exprs&: w, exprs&: kw);
4046 if (!iters(its: {Par(), Red()}))
4047 return rewriter.notifyMatchFailure(arg&: op,
4048 msg: "failed to match conv::W 1-par 1-red");
4049
4050 // No transposition needed.
4051 if (layout(l: {/*lhsIndex*/ {w + kw},
4052 /*rhsIndex*/ {kw},
4053 /*resIndex*/ {w}}))
4054 return conv(conv1DOpOrder: Conv1DOpOrder::W);
4055
4056 return rewriter.notifyMatchFailure(arg&: op, msg: "not a conv::W layout");
4057 }
4058
4059 /// Entry point that transposes into the common form:
4060 /// {{n, strideW * w + dilationW * kw, c}, {kw, c, f}, {n, w, f}}
4061 FailureOr<Operation *> generateNwcConv() {
4062 AffineExpr n, w, f, kw, c;
4063 bindDims(ctx, exprs&: n, exprs&: w, exprs&: f, exprs&: kw, exprs&: c);
4064 if (!iters(its: {Par(), Par(), Par(), Red(), Red()}))
4065 return rewriter.notifyMatchFailure(
4066 arg&: op, msg: "failed to match conv::Nwc 3-par 2-red");
4067
4068 // No transposition needed.
4069 if (layout(l: {/*lhsIndex*/ {n, strideW * w + dilationW * kw, c},
4070 /*rhsIndex*/ {kw, c, f},
4071 /*resIndex*/ {n, w, f}}))
4072 return conv(conv1DOpOrder: Conv1DOpOrder::Nwc);
4073
4074 return rewriter.notifyMatchFailure(arg&: op, msg: "not a conv::Nwc layout");
4075 }
4076
4077 /// Entry point that transposes into the common form:
4078 /// {{n, c, strideW * w + dilationW * kw}, {f, c, kw}, {n, f, w}}
4079 FailureOr<Operation *> generateNcwConv() {
4080 AffineExpr n, w, f, kw, c;
4081 bindDims(ctx, exprs&: n, exprs&: f, exprs&: w, exprs&: c, exprs&: kw);
4082 if (!iters(its: {Par(), Par(), Par(), Red(), Red()}))
4083 return rewriter.notifyMatchFailure(
4084 arg&: op, msg: "failed to match conv::Ncw 3-par 2-red");
4085
4086 if (layout(l: {/*lhsIndex*/ {n, c, strideW * w + dilationW * kw},
4087 /*rhsIndex*/ {f, c, kw},
4088 /*resIndex*/ {n, f, w}}))
4089 return conv(conv1DOpOrder: Conv1DOpOrder::Ncw);
4090
4091 return rewriter.notifyMatchFailure(arg&: op, msg: "not a conv::Ncw layout");
4092 }
4093
4094 /// Entry point that transposes into the common form:
4095 /// {{n, strideW * w + dilationW * kw, c}, {kw}, {n, w, c}} for pooling
4096 FailureOr<Operation *> generateNwcPooling() {
4097 AffineExpr n, w, c, kw;
4098 bindDims(ctx, exprs&: n, exprs&: w, exprs&: c, exprs&: kw);
4099 if (!iters(its: {Par(), Par(), Par(), Red()}))
4100 return rewriter.notifyMatchFailure(arg&: op,
4101 msg: "failed to match pooling 3-par 1-red");
4102
4103 // No transposition needed.
4104 if (layout(l: {/*lhsIndex*/ {n, strideW * w + dilationW * kw, c},
4105 /*rhsIndex*/ {kw},
4106 /*resIndex*/ {n, w, c}}))
4107 return conv(conv1DOpOrder: Conv1DOpOrder::Nwc);
4108
4109 return rewriter.notifyMatchFailure(arg&: op, msg: "not a pooling::Nwc layout");
4110 }
4111
4112 /// Entry point that transposes into the common form:
4113 /// {{n, c, strideW * w + dilationW * kw}, {kw}, {n, c, w}} for pooling
4114 FailureOr<Operation *> generateNcwPooling() {
4115 AffineExpr n, w, c, kw;
4116 bindDims(ctx, exprs&: n, exprs&: c, exprs&: w, exprs&: kw);
4117 if (!iters(its: {Par(), Par(), Par(), Red()}))
4118 return rewriter.notifyMatchFailure(arg&: op,
4119 msg: "failed to match pooling 3-par 1-red");
4120
4121 if (layout(l: {/*lhsIndex*/ {n, c, strideW * w + dilationW * kw},
4122 /*rhsIndex*/ {kw},
4123 /*resIndex*/ {n, c, w}}))
4124 return conv(conv1DOpOrder: Conv1DOpOrder::Ncw);
4125
4126 return rewriter.notifyMatchFailure(arg&: op, msg: "not a pooling::Ncw layout");
4127 }
4128
4129 /// Entry point that transposes into the common form:
4130 /// {{n, strideW * w + dilationW * kw, c}, {kw, c}, {n, w, c}}
4131 FailureOr<Operation *> generateDilatedConv(uint64_t vecChDimSize = 0,
4132 bool vecChDimScalableFlag = false,
4133 bool flatten = false) {
4134 AffineExpr n, w, c, kw;
4135 bindDims(ctx, exprs&: n, exprs&: w, exprs&: c, exprs&: kw);
4136 if (!iters(its: {Par(), Par(), Par(), Red()}))
4137 return rewriter.notifyMatchFailure(
4138 arg&: op, msg: "failed to match depthwise::Nwc conv 3-par 1-red");
4139
4140 // No transposition needed.
4141 if (layout(l: {/*lhsIndex*/ {n, strideW * w + dilationW * kw, c},
4142 /*rhsIndex*/ {kw, c},
4143 /*resIndex*/ {n, w, c}}))
4144 return depthwiseConv(channelDimVecSize: vecChDimSize, channelDimScalableFlag: vecChDimScalableFlag, flatten);
4145
4146 return rewriter.notifyMatchFailure(arg&: op, msg: "not a depthwise::Nwc layout");
4147 }
4148
4149private:
4150 ConvOperationKind oper = ConvOperationKind::Conv;
4151 StringAttr redOp;
4152 StringAttr poolExtOp;
4153 bool isPoolExt = false;
4154 // Casts used to widen the convolution payload's lhs and rhs. These are null
4155 // only when the corresponding operand already has the accumulator type.
4156 Operation *lhsCastOp = nullptr;
4157 Operation *rhsCastOp = nullptr;
4158 int strideW, dilationW;
4159 Value lhsShaped, rhsShaped, resShaped;
4160 ShapedType lhsShapedType, rhsShapedType, resShapedType;
4161 vector::CombiningKind reductionKind;
4162
4163 // Sets oper, poolExtOp, isPoolExt and the conv operand casts for valid
4164 // conv/pooling ops.
4165 void setConvOperationKind(Operation *reduceOp) {
4166 int numBlockArguments =
4167 llvm::count_if(Range: reduceOp->getOperands(), P: llvm::IsaPred<BlockArgument>);
4168 if (numBlockArguments == 1) {
4169 // Will be convolution if feeder is a MulOp.
4170 // A strength reduced version of MulOp for i1 type is AndOp which is also
4171 // supported. Otherwise, it can be pooling. This strength reduction logic
4172 // is in `buildBinaryFn` helper in the Linalg dialect.
4173 auto feedValIt = llvm::find_if_not(Range: reduceOp->getOperands(),
4174 P: llvm::IsaPred<BlockArgument>);
4175 Operation *feedOp = (*feedValIt).getDefiningOp();
4176 if (isCastOfBlockArgument(op: feedOp)) {
4177 oper = ConvOperationKind::Pool;
4178 isPoolExt = true;
4179 poolExtOp = feedOp->getName().getIdentifier();
4180 return;
4181 }
4182 oper = ConvOperationKind::Conv;
4183 setConvCastOps(feedOp);
4184 return;
4185 }
4186 // numBlockArugments == 2 and this is a pooling op.
4187 oper = ConvOperationKind::Pool;
4188 isPoolExt = false;
4189 }
4190
4191 // Record the casts applied to the input and filter.
4192 void setConvCastOps(Operation *feedOp) {
4193 lhsCastOp = feedOp->getOperand(idx: 0).getDefiningOp();
4194 rhsCastOp = feedOp->getOperand(idx: 1).getDefiningOp();
4195 }
4196};
4197} // namespace
4198
4199/// Helper function to vectorize a LinalgOp with convolution semantics.
4200// TODO: extend the generic vectorization to support windows and drop this.
4201static FailureOr<Operation *> vectorizeConvolution(
4202 RewriterBase &rewriter, LinalgOp op, ArrayRef<int64_t> inputVecSizes,
4203 ArrayRef<bool> inputScalableVecDims, bool flatten1DDepthwiseConv) {
4204 FailureOr<Conv1DGenerator> conv1dGen = Conv1DGenerator::create(rewriter, linalgOp: op);
4205 if (failed(Result: conv1dGen))
4206 return failure();
4207 auto res = conv1dGen->generateNonChanneledConv();
4208 if (succeeded(Result: res))
4209 return res;
4210 res = conv1dGen->generateNwcConv();
4211 if (succeeded(Result: res))
4212 return res;
4213 res = conv1dGen->generateNcwConv();
4214 if (succeeded(Result: res))
4215 return res;
4216 res = conv1dGen->generateNwcPooling();
4217 if (succeeded(Result: res))
4218 return res;
4219 res = conv1dGen->generateNcwPooling();
4220 if (succeeded(Result: res))
4221 return res;
4222
4223 // Only depthwise 1D NWC convs are left - these can be vectorized using masks
4224 // and scalable vectors. Note that ATM the only dim that can be dynamic (i.e.
4225 // masked/scalable) is the channel dim (i.e. the trailing dim).
4226 uint64_t vecChDimSize = ShapedType::kDynamic;
4227 bool vecChDimScalableFlag = false;
4228 if (!inputVecSizes.empty()) {
4229 // Only use the input vector size corresponding to the channel dim. Other
4230 // vector dims will be inferred from the Ops.
4231 assert((isaConvolutionOpOfType<linalg::DepthwiseConv1DNwcWcOp>(op) ||
4232 isaConvolutionOpOfType<linalg::DepthwiseConv1DNcwCwOp>(op)) &&
4233 "Not a 1D depthwise conv!");
4234 size_t chDimIdx = 0;
4235 if (isaConvolutionOpOfType<linalg::DepthwiseConv1DNwcWcOp>(op))
4236 chDimIdx = 2;
4237 if (isaConvolutionOpOfType<linalg::DepthwiseConv1DNcwCwOp>(op))
4238 chDimIdx = 1;
4239
4240 vecChDimSize = inputVecSizes[chDimIdx];
4241 vecChDimScalableFlag = inputScalableVecDims[chDimIdx];
4242 }
4243 return conv1dGen->generateDilatedConv(vecChDimSize, vecChDimScalableFlag,
4244 flatten: flatten1DDepthwiseConv);
4245}
4246
4247struct VectorizeConvolution : public OpInterfaceRewritePattern<LinalgOp> {
4248 using Base::Base;
4249
4250 LogicalResult matchAndRewrite(LinalgOp op,
4251 PatternRewriter &rewriter) const override {
4252 FailureOr<Operation *> resultOrFail = vectorizeConvolution(rewriter, op);
4253 if (failed(Result: resultOrFail))
4254 return failure();
4255 Operation *newOp = *resultOrFail;
4256 if (newOp->getNumResults() == 0) {
4257 rewriter.eraseOp(op: op.getOperation());
4258 return success();
4259 }
4260 assert(newOp->getNumResults() == 1 && "expected single result");
4261 rewriter.replaceOp(op: op.getOperation(), newValues: newOp->getResult(idx: 0));
4262 return success();
4263 }
4264};
4265
4266void mlir::linalg::populateConvolutionVectorizationPatterns(
4267 RewritePatternSet &patterns, PatternBenefit benefit) {
4268 patterns.add<VectorizeConvolution>(arg: patterns.getContext(), args&: benefit);
4269}
4270