1//===- VectorUnrollDistribute.cpp - patterns to do vector unrolling -------===//
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 patterns to do vector unrolling and vector distribution.
10//
11//===----------------------------------------------------------------------===//
12
13#include "mlir/Dialect/Affine/IR/AffineOps.h"
14#include "mlir/Dialect/Utils/IndexingUtils.h"
15#include "mlir/Dialect/Vector/Transforms/LoweringPatterns.h"
16#include "mlir/Dialect/Vector/Transforms/VectorTransforms.h"
17#include "mlir/Dialect/Vector/Utils/VectorUtils.h"
18#include "mlir/Interfaces/VectorInterfaces.h"
19#include "llvm/ADT/MapVector.h"
20#include "llvm/ADT/STLExtras.h"
21#include "llvm/Support/DebugLog.h"
22#include "llvm/Support/InterleavedRange.h"
23#include <optional>
24
25#define DEBUG_TYPE "vector-unroll"
26
27using namespace mlir;
28using namespace mlir::vector;
29
30SmallVector<Value> mlir::vector::sliceTransferIndices(
31 ArrayRef<int64_t> elementOffsets, ArrayRef<Value> indices,
32 AffineMap permutationMap, Location loc, OpBuilder &builder) {
33 MLIRContext *ctx = builder.getContext();
34 auto isBroadcast = [](AffineExpr expr) {
35 if (auto constExpr = dyn_cast<AffineConstantExpr>(Val&: expr))
36 return constExpr.getValue() == 0;
37 return false;
38 };
39 // Compute 'sliceIndices' by adding 'sliceOffsets[i]' to 'indices[i]'.
40 SmallVector<Value> slicedIndices(indices);
41 for (const auto &dim : llvm::enumerate(First: permutationMap.getResults())) {
42 int64_t elementOffset = elementOffsets[dim.index()];
43 if (isBroadcast(dim.value()) || elementOffset == 0)
44 continue;
45 unsigned pos = cast<AffineDimExpr>(Val: dim.value()).getPosition();
46 auto expr = getAffineDimExpr(position: 0, context: builder.getContext()) +
47 getAffineConstantExpr(constant: elementOffset, context: ctx);
48 auto map = AffineMap::get(/*dimCount=*/1, /*symbolCount=*/0, result: expr);
49 slicedIndices[pos] =
50 affine::AffineApplyOp::create(builder, location: loc, map, mapOperands: indices[pos]);
51 }
52 return slicedIndices;
53}
54
55// Compute the new indices by adding `offsets` to `originalIndices`.
56// If m < n (m = offsets.size(), n = originalIndices.size()),
57// then only the trailing m values in `originalIndices` are updated.
58static SmallVector<Value> sliceLoadStoreIndices(PatternRewriter &rewriter,
59 Location loc,
60 OperandRange originalIndices,
61 ArrayRef<int64_t> offsets) {
62 assert(offsets.size() <= originalIndices.size() &&
63 "Offsets should not exceed the number of original indices");
64 SmallVector<Value> indices(originalIndices);
65
66 auto start = indices.size() - offsets.size();
67 for (auto [i, offset] : llvm::enumerate(First&: offsets)) {
68 if (offset != 0) {
69 indices[start + i] = arith::AddIOp::create(
70 builder&: rewriter, location: loc, lhs: originalIndices[start + i],
71 rhs: arith::ConstantIndexOp::create(builder&: rewriter, location: loc, value: offset));
72 }
73 }
74 return indices;
75}
76
77// Clones `op` into a new operations that takes `operands` and returns
78// `resultTypes`.
79static Operation *cloneOpWithOperandsAndTypes(OpBuilder &builder, Location loc,
80 Operation *op,
81 ArrayRef<Value> operands,
82 ArrayRef<Type> resultTypes) {
83 OperationState state(loc, op->getName(), operands, resultTypes,
84 op->getDiscardableAttrDictionary().getValue());
85 state.propertiesAttr = op->getPropertiesAsAttribute();
86 return builder.create(state);
87}
88
89/// Return the target shape for unrolling for the given op, provided through its
90/// VectorUnrollOpInterface object, `iface`. Return std::nullopt if the op
91/// shouldn't be or cannot be unrolled. Ops masked by an enclosing vector.mask
92/// are rejected unless `allowMasked` is set, which only patterns that slice the
93/// mask for each unrolled op may do.
94///
95/// ATM, target shape can be specified two-fold:
96/// 1. Via `VectorUnrollOpInterface` (see `getDefaultUnrollTargetShape`).
97/// 2. Via `UnrollVectorOptions` (see `nativeShape`).
98///
99/// Input from a "user" always takes precedence, i.e. 1. is used iff 2. (used
100/// for "user" input) is not available.
101static std::optional<SmallVector<int64_t>>
102getTargetShape(const vector::UnrollVectorOptions &options,
103 VectorUnrollOpInterface &iface, bool allowMasked = false) {
104 auto op = iface.getOperation();
105
106 if (options.filterConstraint && failed(Result: options.filterConstraint(op))) {
107 LDBG() << "--no filter constraint -> BAIL";
108 return std::nullopt;
109 }
110
111 LDBG() << "Get unroll shape for op " << op->getName().getStringRef();
112 auto tS = iface.getDefaultUnrollTargetShape();
113
114 // Unrolling a masked op would put several ops inside its vector.mask region,
115 // and the enclosing mask would not be sliced to match them.
116 auto maskableOp = dyn_cast<vector::MaskableOpInterface>(Val: op);
117 if (!allowMasked && maskableOp && maskableOp.isMasked()) {
118 LDBG() << "--op is masked -> BAIL";
119 return std::nullopt;
120 }
121 auto maybeUnrollShape = iface.getIterationShapeToUnroll();
122 if (!maybeUnrollShape) {
123 LDBG() << "--could not get shape of op " << *op << " -> BAIL";
124 return std::nullopt;
125 }
126 LDBG() << "--vector op shape: " << llvm::interleaved(R: *maybeUnrollShape);
127
128 std::optional<SmallVector<int64_t>> targetShape =
129 options.nativeShape ? options.nativeShape(op) : tS;
130 if (!targetShape) {
131 LDBG() << "--no unrolling target shape defined " << *op << "-> SKIP";
132 return std::nullopt;
133 }
134 LDBG() << "--target shape: " << llvm::interleaved(R: *targetShape);
135
136 auto maybeShapeRatio = computeShapeRatio(shape: *maybeUnrollShape, subShape: *targetShape);
137 if (!maybeShapeRatio) {
138 LDBG() << "--could not compute integral shape ratio -> BAIL";
139 return std::nullopt;
140 }
141 if (llvm::all_of(Range&: *maybeShapeRatio, P: [](int64_t v) { return v == 1; })) {
142 LDBG() << "--no unrolling needed -> SKIP";
143 return std::nullopt;
144 }
145 LDBG() << "--found an integral shape ratio to unroll to -> SUCCESS";
146 return targetShape;
147}
148
149static SmallVector<int64_t>
150getUnrollOrder(unsigned numLoops, Operation *op,
151 const vector::UnrollVectorOptions &options) {
152 SmallVector<int64_t> loopOrder =
153 llvm::to_vector(Range: llvm::seq<int64_t>(Begin: 0, End: static_cast<int64_t>(numLoops)));
154 if (options.traversalOrderCallback != nullptr) {
155 std::optional<SmallVector<int64_t>> order =
156 options.traversalOrderCallback(op);
157 if (order) {
158 loopOrder = std::move(*order);
159 }
160 }
161 return loopOrder;
162}
163
164/// Fail if `xferOp`, masked by an enclosing vector.mask, is masked in a way
165/// that the transfer unrolling patterns do not support yet.
166template <typename TransferOpTy>
167static LogicalResult
168checkSupportedMaskedTransferUnrolling(TransferOpTy xferOp,
169 PatternRewriter &rewriter) {
170 // Extra dimensions from a vector element type are not represented in the
171 // transfer's mask.
172 if (xferOp.getVectorType().getRank() != xferOp.getTransferRank())
173 return rewriter.notifyMatchFailure(
174 xferOp, "masked transfer with a vector element type");
175 // With a minor identity map and a scalar element type, the mask has the same
176 // shape as the vector, so each tile of the vector has the tile of the mask at
177 // the same offsets.
178 if (!xferOp.getPermutationMap().isMinorIdentity())
179 return rewriter.notifyMatchFailure(
180 xferOp, "masked transfer with a non-minor-identity map");
181 if (xferOp.getVectorType().isScalable())
182 return rewriter.notifyMatchFailure(xferOp, "masked scalable transfer");
183 return success();
184}
185
186/// Wrap `tiledXferOp`, the new transfer for one tile, in a vector.mask with the
187/// tile of `maskingOp`'s mask (and passthru, if any) at `offsets` with shape
188/// `sizes`. `maskingOp` is the vector.mask around the original transfer;
189/// `tiledXferOp` is created outside of it. Return `tiledXferOp` itself if
190/// `maskingOp` is null.
191static Operation *maskTile(PatternRewriter &rewriter, Location loc,
192 Operation *tiledXferOp,
193 vector::MaskingOpInterface maskingOp,
194 ArrayRef<int64_t> offsets, ArrayRef<int64_t> sizes,
195 ArrayRef<int64_t> strides) {
196 if (!maskingOp)
197 return tiledXferOp;
198 Value mask = rewriter.createOrFold<vector::ExtractStridedSliceOp>(
199 location: loc, args: maskingOp.getMask(), args&: offsets, args&: sizes, args&: strides);
200 Value passthru;
201 if (maskingOp.hasPassthru())
202 passthru = rewriter.createOrFold<vector::ExtractStridedSliceOp>(
203 location: loc, args: maskingOp.getPassthru(), args&: offsets, args&: sizes, args&: strides);
204 return vector::maskOperation(builder&: rewriter, maskableOp: tiledXferOp, mask, passthru);
205}
206
207namespace {
208struct UnrollTransferReadPattern
209 : public vector::MaskableOpRewritePattern<vector::TransferReadOp> {
210 UnrollTransferReadPattern(MLIRContext *context,
211 const vector::UnrollVectorOptions &options,
212 PatternBenefit benefit = 1)
213 : MaskableOpRewritePattern<vector::TransferReadOp>(context, benefit),
214 options(options) {}
215
216 FailureOr<Value>
217 matchAndRewriteMaskableOp(vector::TransferReadOp readOp,
218 vector::MaskingOpInterface maskingOp,
219 PatternRewriter &rewriter) const override {
220 // TODO: support 0-d corner case.
221 if (readOp.getTransferRank() == 0)
222 return failure();
223 if (readOp.getMask())
224 return failure();
225 // A read masked by an enclosing vector.mask is unrolled into one
226 // vector.mask per tile, each with its tile of the mask.
227 if (maskingOp &&
228 failed(Result: checkSupportedMaskedTransferUnrolling(xferOp: readOp, rewriter)))
229 return failure();
230 // TODO: This is shared between all Unroll patterns - merge.
231 auto iface = dyn_cast<VectorUnrollOpInterface>(Val: readOp.getOperation());
232 auto targetShape = getTargetShape(options, iface, /*allowMasked=*/true);
233 if (!targetShape)
234 return failure();
235 auto sourceVectorType = readOp.getVectorType();
236 SmallVector<int64_t> strides(targetShape->size(), 1);
237 Location loc = readOp.getLoc();
238 ArrayRef<int64_t> originalSize = sourceVectorType.getShape();
239 // Bail-out if rank(source) != rank(target). The rewrite reuses the original
240 // permutation_map and in_bounds attributes, which must match the sliced
241 // vector rank. If needed, we can relax this later.
242 if (originalSize.size() != targetShape->size())
243 return rewriter.notifyMatchFailure(
244 arg&: readOp,
245 msg: "expected source input vector rank to match target shape rank");
246
247 // Prepare the result vector;
248 Value result =
249 arith::ConstantOp::create(builder&: rewriter, location: loc, result: sourceVectorType,
250 value: rewriter.getZeroAttr(type: sourceVectorType));
251 auto targetType =
252 VectorType::get(shape: *targetShape, elementType: sourceVectorType.getElementType());
253 SmallVector<Value> originalIndices(readOp.getIndices().begin(),
254 readOp.getIndices().end());
255 SmallVector<int64_t> loopOrder =
256 getUnrollOrder(numLoops: originalSize.size(), op: readOp, options);
257 for (SmallVector<int64_t> elementOffsets :
258 StaticTileOffsetRange(originalSize, *targetShape, loopOrder)) {
259 SmallVector<Value> indices =
260 sliceTransferIndices(elementOffsets, indices: originalIndices,
261 permutationMap: readOp.getPermutationMap(), loc, builder&: rewriter);
262 Operation *slicedRead = vector::TransferReadOp::create(
263 builder&: rewriter, location: loc, result: targetType, base: readOp.getBase(), indices,
264 permutation_map: readOp.getPermutationMapAttr(), padding: readOp.getPadding(), mask: readOp.getMask(),
265 in_bounds: readOp.getInBoundsAttr());
266 slicedRead = maskTile(rewriter, loc, tiledXferOp: slicedRead, maskingOp,
267 offsets: elementOffsets, sizes: *targetShape, strides);
268
269 result = rewriter.createOrFold<vector::InsertStridedSliceOp>(
270 location: loc, args: slicedRead->getResult(idx: 0), args&: result, args&: elementOffsets, args&: strides);
271 }
272 return result;
273 }
274
275private:
276 vector::UnrollVectorOptions options;
277};
278
279struct UnrollTransferWritePattern
280 : public vector::MaskableOpRewritePattern<vector::TransferWriteOp> {
281 UnrollTransferWritePattern(MLIRContext *context,
282 const vector::UnrollVectorOptions &options,
283 PatternBenefit benefit = 1)
284 : MaskableOpRewritePattern<vector::TransferWriteOp>(context, benefit),
285 options(options) {}
286
287 FailureOr<Value>
288 matchAndRewriteMaskableOp(vector::TransferWriteOp writeOp,
289 vector::MaskingOpInterface maskingOp,
290 PatternRewriter &rewriter) const override {
291 // TODO: support 0-d corner case.
292 if (writeOp.getTransferRank() == 0)
293 return failure();
294
295 if (writeOp.getMask())
296 return failure();
297 // A write masked by an enclosing vector.mask is unrolled into one
298 // vector.mask per tile, each with its tile of the mask.
299 if (maskingOp &&
300 failed(Result: checkSupportedMaskedTransferUnrolling(xferOp: writeOp, rewriter)))
301 return failure();
302 // TODO: This is shared between all Unroll patterns - merge.
303 auto iface = dyn_cast<VectorUnrollOpInterface>(Val: writeOp.getOperation());
304 auto targetShape = getTargetShape(options, iface, /*allowMasked=*/true);
305 if (!targetShape)
306 return failure();
307 auto sourceVectorType = writeOp.getVectorType();
308 SmallVector<int64_t> strides(targetShape->size(), 1);
309 Location loc = writeOp.getLoc();
310 ArrayRef<int64_t> originalSize = sourceVectorType.getShape();
311 // Bail-out if rank(source) != rank(target). The main limitation here is the
312 // fact that `ExtractStridedSlice` requires the rank for the input and
313 // output to match. If needed, we can relax this later.
314 if (originalSize.size() != targetShape->size())
315 return rewriter.notifyMatchFailure(
316 arg&: writeOp,
317 msg: "expected source input vector rank to match target shape rank");
318
319 SmallVector<Value> originalIndices(writeOp.getIndices().begin(),
320 writeOp.getIndices().end());
321 SmallVector<int64_t> loopOrder =
322 getUnrollOrder(numLoops: originalSize.size(), op: writeOp, options);
323 Value resultTensor;
324 for (SmallVector<int64_t> elementOffsets :
325 StaticTileOffsetRange(originalSize, *targetShape, loopOrder)) {
326 Value slicedVector = rewriter.createOrFold<vector::ExtractStridedSliceOp>(
327 location: loc, args: writeOp.getVector(), args&: elementOffsets, args&: *targetShape, args&: strides);
328 SmallVector<Value> indices =
329 sliceTransferIndices(elementOffsets, indices: originalIndices,
330 permutationMap: writeOp.getPermutationMap(), loc, builder&: rewriter);
331 Operation *slicedWrite = vector::TransferWriteOp::create(
332 builder&: rewriter, location: loc, vector: slicedVector,
333 dest: resultTensor ? resultTensor : writeOp.getBase(), indices,
334 permutationMapAttr: writeOp.getPermutationMapAttr(), inBoundsAttr: writeOp.getInBoundsAttr());
335 slicedWrite = maskTile(rewriter, loc, tiledXferOp: slicedWrite, maskingOp,
336 offsets: elementOffsets, sizes: *targetShape, strides);
337 // For the tensor case update the destination for the next transfer write.
338 if (!slicedWrite->getResults().empty())
339 resultTensor = slicedWrite->getResult(idx: 0);
340 }
341 // A write to a memref has no result to replace.
342 return resultTensor;
343 }
344
345private:
346 vector::UnrollVectorOptions options;
347};
348
349struct OffsetMapInfo {
350 static unsigned getHashValue(const SmallVector<int64_t> &v) {
351 return static_cast<unsigned>(llvm::hash_combine_range(R: v));
352 }
353
354 static bool isEqual(const SmallVector<int64_t> &lhs,
355 const SmallVector<int64_t> &rhs) {
356 return lhs == rhs;
357 }
358};
359
360struct UnrollContractionPattern
361 : public OpRewritePattern<vector::ContractionOp> {
362 UnrollContractionPattern(MLIRContext *context,
363 const vector::UnrollVectorOptions &options,
364 PatternBenefit benefit = 1)
365 : OpRewritePattern<vector::ContractionOp>(context, benefit),
366 options(options) {}
367
368 LogicalResult matchAndRewrite(vector::ContractionOp contractOp,
369 PatternRewriter &rewriter) const override {
370 // TODO: This is shared between all Unroll patterns - merge.
371 auto iface = dyn_cast<VectorUnrollOpInterface>(Val: contractOp.getOperation());
372 auto targetShape = getTargetShape(options, iface);
373 if (!targetShape)
374 return failure();
375 auto dstVecType = cast<VectorType>(Val: contractOp.getResultType());
376 SmallVector<int64_t> originalSize = *contractOp.getIterationShapeToUnroll();
377
378 Location loc = contractOp.getLoc();
379 unsigned accIndex = vector::ContractionOp::getAccOperandIndex();
380 AffineMap dstAffineMap = contractOp.getIndexingMapsArray()[accIndex];
381 llvm::MapVector<
382 SmallVector<int64_t>, Value,
383 llvm::DenseMap<SmallVector<int64_t>, unsigned, OffsetMapInfo>>
384 accCache;
385
386 SmallVector<int64_t> loopOrder = getUnrollOrder(
387 numLoops: contractOp.getIteratorTypes().size(), op: contractOp, options);
388
389 for (SmallVector<int64_t> offsets :
390 StaticTileOffsetRange(originalSize, *targetShape, loopOrder)) {
391 SmallVector<Value> slicesOperands(contractOp.getNumOperands());
392
393 // Helper to compute the new shape of each operand and extract the slice.
394 auto extractOperand = [&](unsigned index, Value operand,
395 AffineMap permutationMap,
396 ArrayRef<int64_t> operandOffets) {
397 SmallVector<int64_t> operandShape = applyPermutationMap(
398 map: permutationMap, source: ArrayRef<int64_t>(*targetShape));
399 SmallVector<int64_t> operandStrides(operandOffets.size(), 1);
400 slicesOperands[index] =
401 rewriter.createOrFold<vector::ExtractStridedSliceOp>(
402 location: loc, args&: operand, args&: operandOffets, args&: operandShape, args&: operandStrides);
403 };
404
405 // Extract the new lhs operand.
406 AffineMap lhsPermutationMap = contractOp.getIndexingMapsArray()[0];
407 SmallVector<int64_t> lhsOffets =
408 applyPermutationMap(map: lhsPermutationMap, source: ArrayRef<int64_t>(offsets));
409 extractOperand(0, contractOp.getLhs(), lhsPermutationMap, lhsOffets);
410
411 // Extract the new rhs operand.
412 AffineMap rhsPermutationMap = contractOp.getIndexingMapsArray()[1];
413 SmallVector<int64_t> rhsOffets =
414 applyPermutationMap(map: rhsPermutationMap, source: ArrayRef<int64_t>(offsets));
415 extractOperand(1, contractOp.getRhs(), rhsPermutationMap, rhsOffets);
416
417 AffineMap accPermutationMap = contractOp.getIndexingMapsArray()[2];
418 SmallVector<int64_t> accOffets =
419 applyPermutationMap(map: accPermutationMap, source: ArrayRef<int64_t>(offsets));
420 // If a version of the accumulator has already been computed, use it
421 // otherwise extract the first version from the original operand.
422 auto *accIt = accCache.find(Key: accOffets);
423 if (accIt != accCache.end())
424 slicesOperands[2] = accIt->second;
425 else
426 extractOperand(2, contractOp.getAcc(), accPermutationMap, accOffets);
427
428 SmallVector<int64_t> dstShape =
429 applyPermutationMap(map: dstAffineMap, source: ArrayRef<int64_t>(*targetShape));
430 auto targetType = VectorType::get(shape: dstShape, elementType: dstVecType.getElementType());
431 Operation *newOp = cloneOpWithOperandsAndTypes(
432 builder&: rewriter, loc, op: contractOp, operands: slicesOperands, resultTypes: targetType);
433
434 SmallVector<int64_t> dstOffets =
435 applyPermutationMap(map: dstAffineMap, source: ArrayRef<int64_t>(offsets));
436 // Save the accumulated value untill all the loops are unrolled since
437 // reduction loop keep updating the accumulator.
438 accCache[dstOffets] = newOp->getResult(idx: 0);
439 }
440 // Assemble back the accumulator into a single vector.
441 Value result = arith::ConstantOp::create(builder&: rewriter, location: loc, result: dstVecType,
442 value: rewriter.getZeroAttr(type: dstVecType));
443 for (const auto &it : accCache) {
444 SmallVector<int64_t> dstStrides(it.first.size(), 1);
445 result = rewriter.createOrFold<vector::InsertStridedSliceOp>(
446 location: loc, args: it.second, args&: result, args: it.first, args&: dstStrides);
447 }
448 rewriter.replaceOp(op: contractOp, newValues: result);
449 return success();
450 }
451
452private:
453 vector::UnrollVectorOptions options;
454};
455
456struct UnrollMultiReductionPattern
457 : public OpRewritePattern<vector::MultiDimReductionOp> {
458 UnrollMultiReductionPattern(MLIRContext *context,
459 const vector::UnrollVectorOptions &options,
460 PatternBenefit benefit = 1)
461 : OpRewritePattern<vector::MultiDimReductionOp>(context, benefit),
462 options(options) {}
463
464 LogicalResult matchAndRewrite(vector::MultiDimReductionOp reductionOp,
465 PatternRewriter &rewriter) const override {
466
467 // TODO: This is shared between all Unroll patterns - merge.
468 auto iface = dyn_cast<VectorUnrollOpInterface>(Val: reductionOp.getOperation());
469 std::optional<SmallVector<int64_t>> targetShape =
470 getTargetShape(options, iface);
471 if (!targetShape)
472 return failure();
473 SmallVector<int64_t> originalSize =
474 *reductionOp.getIterationShapeToUnroll();
475 Location loc = reductionOp.getLoc();
476 auto resultType = reductionOp->getResult(idx: 0).getType();
477
478 // A target shape with fewer dimensions than the source vector applies to
479 // its trailing dimensions. Add leading unit dimensions so that it can be
480 // used to slice the source and to index its dimensions.
481 SmallVector<int64_t> adjustedTargetShape(originalSize.size(), 1);
482 llvm::copy(Range&: *targetShape, Out: adjustedTargetShape.end() - targetShape->size());
483
484 // Handle scalar result case: all dimensions are reduced.
485 // Each source tile is reduced to a scalar, and partial results are
486 // chained through the accumulator operand.
487 if (resultType.isIntOrFloat()) {
488 Value accumulator = reductionOp.getAcc();
489 for (SmallVector<int64_t> offsets :
490 StaticTileOffsetRange(originalSize, adjustedTargetShape)) {
491 SmallVector<int64_t> operandStrides(offsets.size(), 1);
492 Value slicedOperand =
493 rewriter.createOrFold<vector::ExtractStridedSliceOp>(
494 location: loc, args: reductionOp.getSource(), args&: offsets, args&: adjustedTargetShape,
495 args&: operandStrides);
496 Operation *newOp = cloneOpWithOperandsAndTypes(
497 builder&: rewriter, loc, op: reductionOp, operands: {slicedOperand, accumulator},
498 resultTypes: resultType);
499 accumulator = newOp->getResult(idx: 0);
500 }
501 rewriter.replaceOp(op: reductionOp, newValues: accumulator);
502 return success();
503 }
504
505 // Vector result case.
506 llvm::MapVector<
507 SmallVector<int64_t>, Value,
508 llvm::DenseMap<SmallVector<int64_t>, unsigned, OffsetMapInfo>>
509 accCache;
510
511 // Stride of the ratios, this gives us the offsets of sliceCount in a basis
512 // of multiples of the targetShape.
513 for (SmallVector<int64_t> offsets :
514 StaticTileOffsetRange(originalSize, adjustedTargetShape)) {
515 SmallVector<Value> operands;
516 SmallVector<int64_t> operandStrides(offsets.size(), 1);
517 Value slicedOperand =
518 rewriter.createOrFold<vector::ExtractStridedSliceOp>(
519 location: loc, args: reductionOp.getSource(), args&: offsets, args&: adjustedTargetShape,
520 args&: operandStrides);
521 operands.push_back(Elt: slicedOperand);
522 SmallVector<int64_t> dstShape;
523 SmallVector<int64_t> destOffset;
524 for (size_t i : llvm::seq(Begin: size_t(0), End: adjustedTargetShape.size())) {
525 if (!reductionOp.isReducedDim(d: i)) {
526 destOffset.push_back(Elt: offsets[i]);
527 dstShape.push_back(Elt: adjustedTargetShape[i]);
528 }
529 }
530 Value acc;
531 SmallVector<int64_t> accStrides(destOffset.size(), 1);
532 // If a version of the accumulator has already been computed, use it
533 // otherwise extract the first version from the original operand.
534 auto *accIt = accCache.find(Key: destOffset);
535 if (accIt != accCache.end())
536 acc = accIt->second;
537 else
538 acc = rewriter.createOrFold<vector::ExtractStridedSliceOp>(
539 location: loc, args: reductionOp.getAcc(), args&: destOffset, args&: dstShape, args&: accStrides);
540 operands.push_back(Elt: acc);
541 auto targetType = VectorType::get(
542 shape: dstShape, elementType: reductionOp.getSourceVectorType().getElementType());
543 Operation *newOp = cloneOpWithOperandsAndTypes(builder&: rewriter, loc, op: reductionOp,
544 operands, resultTypes: targetType);
545 Value result = newOp->getResult(idx: 0);
546 accCache[destOffset] = result;
547 }
548 // Assemble back the accumulator into a single vector.
549 Value result = arith::ConstantOp::create(
550 builder&: rewriter, location: loc, result: reductionOp.getDestType(),
551 value: rewriter.getZeroAttr(type: reductionOp.getDestType()));
552 for (const auto &it : accCache) {
553 SmallVector<int64_t> dstStrides(it.first.size(), 1);
554 result = rewriter.createOrFold<vector::InsertStridedSliceOp>(
555 location: loc, args: it.second, args&: result, args: it.first, args&: dstStrides);
556 }
557 rewriter.replaceOp(op: reductionOp, newValues: result);
558 return success();
559 }
560
561private:
562 vector::UnrollVectorOptions options;
563};
564
565struct UnrollElementwisePattern : public RewritePattern {
566 UnrollElementwisePattern(MLIRContext *context,
567 const vector::UnrollVectorOptions &options,
568 PatternBenefit benefit = 1)
569 : RewritePattern(MatchAnyOpTypeTag(), benefit, context),
570 options(options) {}
571
572 LogicalResult matchAndRewrite(Operation *op,
573 PatternRewriter &rewriter) const override {
574 if (!OpTrait::hasElementwiseMappableTraits(op) || op->getNumResults() != 1)
575 return failure();
576 // TODO: This is shared between all Unroll patterns - merge.
577 auto iface = dyn_cast<VectorUnrollOpInterface>(Val: op);
578 if (!iface)
579 return rewriter.notifyMatchFailure(arg&: op, msg: "Not an unrollable elem-wise Op!");
580 auto targetShape = getTargetShape(options, iface);
581 if (!targetShape)
582 return failure();
583 int64_t targetShapeRank = targetShape->size();
584 auto dstVecType = cast<VectorType>(Val: op->getResult(idx: 0).getType());
585 SmallVector<int64_t> originalSize = *iface.getIterationShapeToUnroll();
586 int64_t originalShapeRank = originalSize.size();
587
588 Location loc = op->getLoc();
589
590 // Handle rank mismatch by adding leading unit dimensions to targetShape
591 SmallVector<int64_t> adjustedTargetShape(originalShapeRank);
592 int64_t rankDiff = originalShapeRank - targetShapeRank;
593 std::fill(first: adjustedTargetShape.begin(),
594 last: adjustedTargetShape.begin() + rankDiff, value: 1);
595 std::copy(first: targetShape->begin(), last: targetShape->end(),
596 result: adjustedTargetShape.begin() + rankDiff);
597
598 int64_t adjustedTargetShapeRank = adjustedTargetShape.size();
599 // Prepare the result vector.
600 Value result = arith::ConstantOp::create(builder&: rewriter, location: loc, result: dstVecType,
601 value: rewriter.getZeroAttr(type: dstVecType));
602 SmallVector<int64_t> strides(adjustedTargetShapeRank, 1);
603 VectorType unrolledVecType =
604 VectorType::get(shape: *targetShape, elementType: dstVecType.getElementType());
605
606 // Create the unrolled computation.
607 for (SmallVector<int64_t> offsets :
608 StaticTileOffsetRange(originalSize, adjustedTargetShape)) {
609 SmallVector<Value> extractOperands;
610 for (OpOperand &operand : op->getOpOperands()) {
611 auto vecType = dyn_cast<VectorType>(Val: operand.get().getType());
612 if (!vecType) {
613 extractOperands.push_back(Elt: operand.get());
614 continue;
615 }
616 Value extracted = rewriter.createOrFold<vector::ExtractStridedSliceOp>(
617 location: loc, args: operand.get(), args&: offsets, args&: adjustedTargetShape, args&: strides);
618
619 // Reshape to remove leading unit dims if needed
620 if (adjustedTargetShapeRank > targetShapeRank) {
621 extracted = rewriter.createOrFold<vector::ShapeCastOp>(
622 location: loc, args: VectorType::get(shape: *targetShape, elementType: vecType.getElementType()),
623 args&: extracted);
624 }
625 extractOperands.push_back(Elt: extracted);
626 }
627
628 Operation *newOp = cloneOpWithOperandsAndTypes(
629 builder&: rewriter, loc, op, operands: extractOperands, resultTypes: unrolledVecType);
630
631 Value computeResult = newOp->getResult(idx: 0);
632
633 // Use strides sized to targetShape for proper insertion
634 SmallVector<int64_t> insertStrides =
635 (adjustedTargetShapeRank > targetShapeRank)
636 ? SmallVector<int64_t>(targetShapeRank, 1)
637 : strides;
638
639 result = rewriter.createOrFold<vector::InsertStridedSliceOp>(
640 location: loc, args&: computeResult, args&: result, args&: offsets, args&: insertStrides);
641 }
642 rewriter.replaceOp(op, newValues: result);
643 return success();
644 }
645
646private:
647 vector::UnrollVectorOptions options;
648};
649
650struct UnrollReductionPattern : public OpRewritePattern<vector::ReductionOp> {
651 UnrollReductionPattern(MLIRContext *context,
652 const vector::UnrollVectorOptions &options,
653 PatternBenefit benefit = 1)
654 : OpRewritePattern<vector::ReductionOp>(context, benefit),
655 options(options) {}
656
657 LogicalResult matchAndRewrite(vector::ReductionOp reductionOp,
658 PatternRewriter &rewriter) const override {
659 // TODO: This is shared between all Unroll patterns - merge.
660 auto iface = cast<VectorUnrollOpInterface>(Val&: *reductionOp);
661 std::optional<SmallVector<int64_t>> targetShape =
662 getTargetShape(options, iface);
663 if (!targetShape)
664 return failure();
665 SmallVector<int64_t> originalSize =
666 *reductionOp.getIterationShapeToUnroll();
667
668 // Create unrolled vector reduction.
669 Location loc = reductionOp.getLoc();
670 Value accumulator = nullptr;
671 for (SmallVector<int64_t> offsets :
672 StaticTileOffsetRange(originalSize, *targetShape)) {
673 SmallVector<int64_t> strides(offsets.size(), 1);
674 Value slicedOperand =
675 rewriter.createOrFold<vector::ExtractStridedSliceOp>(
676 location: loc, args: reductionOp.getVector(), args&: offsets, args&: *targetShape, args&: strides);
677 Operation *newOp = cloneOpWithOperandsAndTypes(
678 builder&: rewriter, loc, op: reductionOp, operands: slicedOperand, resultTypes: reductionOp.getType());
679 Value result = newOp->getResult(idx: 0);
680
681 if (!accumulator) {
682 // This is the first reduction.
683 accumulator = result;
684 } else {
685 // On subsequent reduction, combine with the accumulator.
686 accumulator = makeArithReduction(b&: rewriter, loc, kind: reductionOp.getKind(),
687 v1: accumulator, acc: result);
688 }
689 }
690
691 rewriter.replaceOp(op: reductionOp, newValues: accumulator);
692 return success();
693 }
694
695private:
696 const vector::UnrollVectorOptions options;
697};
698
699struct UnrollTransposePattern : public OpRewritePattern<vector::TransposeOp> {
700 UnrollTransposePattern(MLIRContext *context,
701 const vector::UnrollVectorOptions &options,
702 PatternBenefit benefit = 1)
703 : OpRewritePattern<vector::TransposeOp>(context, benefit),
704 options(options) {}
705
706 LogicalResult matchAndRewrite(vector::TransposeOp transposeOp,
707 PatternRewriter &rewriter) const override {
708 if (transposeOp.getResultVectorType().getRank() == 0)
709 return failure();
710 // TODO: This is shared between all Unroll patterns - merge.
711 auto iface = cast<VectorUnrollOpInterface>(Val&: *transposeOp);
712 auto targetShape = getTargetShape(options, iface);
713 if (!targetShape)
714 return failure();
715 auto originalVectorType = transposeOp.getResultVectorType();
716 SmallVector<int64_t> strides(targetShape->size(), 1);
717 Location loc = transposeOp.getLoc();
718 ArrayRef<int64_t> originalSize = originalVectorType.getShape();
719
720 // Prepare the result vector;
721 Value result =
722 arith::ConstantOp::create(builder&: rewriter, location: loc, result: originalVectorType,
723 value: rewriter.getZeroAttr(type: originalVectorType));
724 ArrayRef<int64_t> permutation = transposeOp.getPermutation();
725
726 // Unroll the computation.
727 for (SmallVector<int64_t> elementOffsets :
728 StaticTileOffsetRange(originalSize, *targetShape)) {
729 SmallVector<int64_t> permutedOffsets(elementOffsets.size());
730 SmallVector<int64_t> permutedShape(elementOffsets.size());
731 // Compute the source offsets and shape.
732 for (auto indices : llvm::enumerate(First&: permutation)) {
733 permutedOffsets[indices.value()] = elementOffsets[indices.index()];
734 permutedShape[indices.value()] = (*targetShape)[indices.index()];
735 }
736 Value slicedOperand =
737 rewriter.createOrFold<vector::ExtractStridedSliceOp>(
738 location: loc, args: transposeOp.getVector(), args&: permutedOffsets, args&: permutedShape,
739 args&: strides);
740 Value transposedSlice = rewriter.createOrFold<vector::TransposeOp>(
741 location: loc, args&: slicedOperand, args&: permutation);
742 result = rewriter.createOrFold<vector::InsertStridedSliceOp>(
743 location: loc, args&: transposedSlice, args&: result, args&: elementOffsets, args&: strides);
744 }
745 rewriter.replaceOp(op: transposeOp, newValues: result);
746 return success();
747 }
748
749private:
750 vector::UnrollVectorOptions options;
751};
752
753struct UnrollGatherPattern : public OpRewritePattern<vector::GatherOp> {
754 UnrollGatherPattern(MLIRContext *context,
755 const vector::UnrollVectorOptions &options,
756 PatternBenefit benefit = 1)
757 : OpRewritePattern<vector::GatherOp>(context, benefit), options(options) {
758 }
759
760 LogicalResult matchAndRewrite(vector::GatherOp gatherOp,
761 PatternRewriter &rewriter) const override {
762 VectorType sourceVectorType = gatherOp.getVectorType();
763 if (sourceVectorType.getRank() == 0)
764 return failure();
765 // TODO: This is shared between all Unroll patterns - merge.
766 auto iface = cast<VectorUnrollOpInterface>(Val&: *gatherOp);
767 auto targetShape = getTargetShape(options, iface);
768 if (!targetShape)
769 return failure();
770 SmallVector<int64_t> strides(targetShape->size(), 1);
771 Location loc = gatherOp.getLoc();
772 ArrayRef<int64_t> originalSize = gatherOp.getVectorType().getShape();
773
774 // Prepare the result vector;
775 Value result =
776 arith::ConstantOp::create(builder&: rewriter, location: loc, result: sourceVectorType,
777 value: rewriter.getZeroAttr(type: sourceVectorType));
778 auto targetType =
779 VectorType::get(shape: *targetShape, elementType: sourceVectorType.getElementType());
780
781 SmallVector<int64_t> loopOrder =
782 getUnrollOrder(numLoops: originalSize.size(), op: gatherOp, options);
783 for (SmallVector<int64_t> elementOffsets :
784 StaticTileOffsetRange(originalSize, *targetShape, loopOrder)) {
785 // To get the unrolled gather, extract the same slice based on the
786 // decomposed shape from each of the index, mask, and pass-through
787 // vectors.
788 Value indexSubVec = rewriter.createOrFold<vector::ExtractStridedSliceOp>(
789 location: loc, args: gatherOp.getIndices(), args&: elementOffsets, args&: *targetShape, args&: strides);
790 Value maskSubVec = rewriter.createOrFold<vector::ExtractStridedSliceOp>(
791 location: loc, args: gatherOp.getMask(), args&: elementOffsets, args&: *targetShape, args&: strides);
792 Value passThruSubVec =
793 rewriter.createOrFold<vector::ExtractStridedSliceOp>(
794 location: loc, args: gatherOp.getPassThru(), args&: elementOffsets, args&: *targetShape,
795 args&: strides);
796 auto slicedGather = vector::GatherOp::create(
797 builder&: rewriter, location: loc, resultType: targetType, base: gatherOp.getBase(), indices: gatherOp.getOffsets(),
798 index_vec: indexSubVec, mask: maskSubVec, passthrough: passThruSubVec);
799
800 result = rewriter.createOrFold<vector::InsertStridedSliceOp>(
801 location: loc, args&: slicedGather, args&: result, args&: elementOffsets, args&: strides);
802 }
803 rewriter.replaceOp(op: gatherOp, newValues: result);
804 return success();
805 }
806
807private:
808 vector::UnrollVectorOptions options;
809};
810
811struct UnrollLoadPattern : public OpRewritePattern<vector::LoadOp> {
812 UnrollLoadPattern(MLIRContext *context,
813 const vector::UnrollVectorOptions &options,
814 PatternBenefit benefit = 1)
815 : OpRewritePattern<vector::LoadOp>(context, benefit), options(options) {}
816
817 LogicalResult matchAndRewrite(vector::LoadOp loadOp,
818 PatternRewriter &rewriter) const override {
819 VectorType vecType = loadOp.getVectorType();
820
821 // TODO: This is shared between all Unroll patterns - merge.
822 auto iface = cast<VectorUnrollOpInterface>(Val&: *loadOp);
823 auto targetShape = getTargetShape(options, iface);
824 if (!targetShape)
825 return failure();
826
827 Location loc = loadOp.getLoc();
828 ArrayRef<int64_t> originalShape = vecType.getShape();
829 SmallVector<int64_t> strides(targetShape->size(), 1);
830
831 Value result = arith::ConstantOp::create(builder&: rewriter, location: loc, result: vecType,
832 value: rewriter.getZeroAttr(type: vecType));
833
834 SmallVector<int64_t> loopOrder =
835 getUnrollOrder(numLoops: originalShape.size(), op: loadOp, options);
836
837 auto targetVecType =
838 VectorType::get(shape: *targetShape, elementType: vecType.getElementType());
839
840 for (SmallVector<int64_t> offsets :
841 StaticTileOffsetRange(originalShape, *targetShape, loopOrder)) {
842 SmallVector<Value> indices =
843 sliceLoadStoreIndices(rewriter, loc, originalIndices: loadOp.getIndices(), offsets);
844 Value slicedLoad = vector::LoadOp::create(builder&: rewriter, location: loc, resultType: targetVecType,
845 base: loadOp.getBase(), indices);
846 result = rewriter.createOrFold<vector::InsertStridedSliceOp>(
847 location: loc, args&: slicedLoad, args&: result, args&: offsets, args&: strides);
848 }
849 rewriter.replaceOp(op: loadOp, newValues: result);
850 return success();
851 }
852
853private:
854 vector::UnrollVectorOptions options;
855};
856
857struct UnrollStorePattern : public OpRewritePattern<vector::StoreOp> {
858 UnrollStorePattern(MLIRContext *context,
859 const vector::UnrollVectorOptions &options,
860 PatternBenefit benefit = 1)
861 : OpRewritePattern<vector::StoreOp>(context, benefit), options(options) {}
862
863 LogicalResult matchAndRewrite(vector::StoreOp storeOp,
864 PatternRewriter &rewriter) const override {
865 VectorType vecType = storeOp.getVectorType();
866
867 // TODO: This is shared between all Unroll patterns - merge.
868 auto iface = cast<VectorUnrollOpInterface>(Val&: *storeOp);
869 auto targetShape = getTargetShape(options, iface);
870 if (!targetShape)
871 return failure();
872
873 Location loc = storeOp.getLoc();
874 ArrayRef<int64_t> originalShape = vecType.getShape();
875 SmallVector<int64_t> strides(targetShape->size(), 1);
876
877 Value base = storeOp.getBase();
878 Value vector = storeOp.getValueToStore();
879
880 SmallVector<int64_t> loopOrder =
881 getUnrollOrder(numLoops: originalShape.size(), op: storeOp, options);
882
883 for (SmallVector<int64_t> offsets :
884 StaticTileOffsetRange(originalShape, *targetShape, loopOrder)) {
885 SmallVector<Value> indices =
886 sliceLoadStoreIndices(rewriter, loc, originalIndices: storeOp.getIndices(), offsets);
887 Value slice = rewriter.createOrFold<vector::ExtractStridedSliceOp>(
888 location: loc, args&: vector, args&: offsets, args&: *targetShape, args&: strides);
889 vector::StoreOp::create(builder&: rewriter, location: loc, valueToStore: slice, base, indices);
890 }
891 rewriter.eraseOp(op: storeOp);
892 return success();
893 }
894
895private:
896 vector::UnrollVectorOptions options;
897};
898
899struct UnrollBroadcastPattern : public OpRewritePattern<vector::BroadcastOp> {
900 UnrollBroadcastPattern(MLIRContext *context,
901 const vector::UnrollVectorOptions &options,
902 PatternBenefit benefit = 1)
903 : OpRewritePattern<vector::BroadcastOp>(context, benefit),
904 options(options) {}
905
906 LogicalResult matchAndRewrite(vector::BroadcastOp broadcastOp,
907 PatternRewriter &rewriter) const override {
908 // TODO: This is shared between all Unroll patterns - merge.
909 auto iface = cast<VectorUnrollOpInterface>(Val&: *broadcastOp);
910 auto targetShape = getTargetShape(options, iface);
911 if (!targetShape)
912 return failure();
913
914 Location loc = broadcastOp.getLoc();
915 VectorType srcType = dyn_cast<VectorType>(Val: broadcastOp.getSourceType());
916 VectorType resType = broadcastOp.getResultVectorType();
917
918 SmallVector<int64_t> originalShape =
919 *broadcastOp.getIterationShapeToUnroll();
920 // Pad the target shape with leading unit dimensions when the broadcast
921 // result has a higher rank than the native shape.
922 SmallVector<int64_t> adjustedTargetShape(originalShape.size(), 1);
923 llvm::copy(Range&: *targetShape, Out: adjustedTargetShape.end() - targetShape->size());
924
925 VectorType targetType =
926 resType.cloneWith(shape: adjustedTargetShape, elementType: resType.getElementType());
927 Value result = arith::ConstantOp::create(builder&: rewriter, location: loc, result: resType,
928 value: rewriter.getZeroAttr(type: resType));
929
930 SmallVector<int64_t> strides(originalShape.size(), 1);
931
932 for (SmallVector<int64_t> offsets :
933 StaticTileOffsetRange(originalShape, adjustedTargetShape)) {
934 Value newSrc;
935 if (!srcType) {
936 // Scalar to vector broadcast.
937 newSrc = broadcastOp.getSource();
938 } else {
939 // Vector to vector broadcast.
940 int64_t rank = srcType.getRank();
941 SmallVector<int64_t> srcOffsets(offsets.end() - rank, offsets.end());
942 SmallVector<int64_t> srcShape(adjustedTargetShape.end() - rank,
943 adjustedTargetShape.end());
944 SmallVector<int64_t> srcStrides(strides.end() - rank, strides.end());
945 // adjust the offset and shape for src if the corresponding dim is 1.
946 for (int64_t i = 0; i < rank; ++i) {
947 if (srcType.getDimSize(idx: i) == 1) {
948 srcOffsets[i] = 0;
949 srcShape[i] = 1;
950 }
951 }
952 newSrc = rewriter.createOrFold<vector::ExtractStridedSliceOp>(
953 location: loc, args: broadcastOp.getSource(), args&: srcOffsets, args&: srcShape, args&: srcStrides);
954 }
955
956 Operation *newOp = cloneOpWithOperandsAndTypes(builder&: rewriter, loc, op: broadcastOp,
957 operands: newSrc, resultTypes: targetType);
958
959 result = rewriter.createOrFold<vector::InsertStridedSliceOp>(
960 location: loc, args: newOp->getResult(idx: 0), args&: result, args&: offsets, args&: strides);
961 }
962
963 rewriter.replaceOp(op: broadcastOp, newValues: result);
964 return success();
965 }
966
967private:
968 vector::UnrollVectorOptions options;
969};
970
971/// Unrolls 2 or more dimensional `vector.to_elements` ops by unrolling the
972/// outermost dimension of the operand. For example:
973///
974/// ```
975/// %0:4 = vector.to_elements %v : vector<2x2xf32>
976///
977/// ==>
978///
979/// %v0 = vector.extract %v[0] : vector<2x2xf32> from vector<2x2x2xf32>
980/// %v1 = vector.extract %v[1] : vector<2x2xf32> from vector<2x2x2xf32>
981/// %0:4 = vector.to_elements %v0 : vector<2x2xf32>
982/// %1:4 = vector.to_elements %v1 : vector<2x2xf32>
983/// ```
984///
985/// When this pattern is applied until a fixed-point is reached,
986/// this will produce a sequence of 1-d from_elements
987/// ops.
988struct UnrollToElements final : public OpRewritePattern<vector::ToElementsOp> {
989 UnrollToElements(MLIRContext *context,
990 const vector::UnrollVectorOptions &options,
991 PatternBenefit benefit = 1)
992 : OpRewritePattern<vector::ToElementsOp>(context, benefit),
993 options(options) {}
994
995 LogicalResult matchAndRewrite(vector::ToElementsOp op,
996 PatternRewriter &rewriter) const override {
997
998 TypedValue<VectorType> source = op.getSource();
999 FailureOr<SmallVector<Value>> result =
1000 vector::unrollVectorValue(source, rewriter);
1001 if (failed(Result: result)) {
1002 return failure();
1003 }
1004 SmallVector<Value> vectors = *result;
1005
1006 SmallVector<Value> results;
1007 for (Value vector : vectors) {
1008 auto subElements =
1009 vector::ToElementsOp::create(builder&: rewriter, location: op.getLoc(), source: vector);
1010 llvm::append_range(C&: results, R: subElements.getResults());
1011 }
1012 rewriter.replaceOp(op, newValues: results);
1013 return success();
1014 }
1015
1016private:
1017 vector::UnrollVectorOptions options;
1018};
1019
1020/// This pattern unrolls `vector.step` operations according to the provided
1021/// target unroll shape. It decomposes a large step vector into smaller step
1022/// vectors (segments) and assembles the result by inserting each computed
1023/// segment into the appropriate offset of the original vector.
1024///
1025/// The pattern does not support scalable vectors and will fail to match them.
1026///
1027/// For each segment, it adds the base step vector and the segment's offset,
1028/// then inserts the result into the output vector at the corresponding
1029/// position.
1030///
1031/// Example:
1032/// Given a step operation:
1033/// %0 = vector.step : vector<8xindex>
1034///
1035/// and a target unroll shape of <4>, the pattern produces:
1036///
1037/// %base = vector.step : vector<4xindex>
1038/// %zero = arith.constant dense<0> : vector<8xindex>
1039/// %result0 = vector.insert_strided_slice %base, %zero
1040/// {offsets = [0], strides = [1]} : vector<4xindex> into vector<8xindex>
1041/// %offset = arith.constant dense<4> : vector<4xindex>
1042/// %segment1 = arith.addi %base, %offset : vector<4xindex>
1043/// %result1 = vector.insert_strided_slice %segment1, %result0
1044/// {offsets = [4], strides = [1]} : vector<4xindex> into vector<8xindex>
1045///
1046struct UnrollStepPattern : public OpRewritePattern<vector::StepOp> {
1047 UnrollStepPattern(MLIRContext *context,
1048 const vector::UnrollVectorOptions &options,
1049 PatternBenefit benefit = 1)
1050 : OpRewritePattern<vector::StepOp>(context, benefit), options(options) {}
1051
1052 LogicalResult matchAndRewrite(vector::StepOp stepOp,
1053 PatternRewriter &rewriter) const override {
1054 // TODO: This is shared between all Unroll patterns - merge.
1055 auto iface = cast<VectorUnrollOpInterface>(Val&: *stepOp);
1056 std::optional<SmallVector<int64_t>> targetShape =
1057 getTargetShape(options, iface);
1058 if (!targetShape)
1059 return failure();
1060
1061 VectorType vecType = stepOp.getType();
1062 if (vecType.isScalable()) {
1063 // Scalable vectors are not supported by this pattern.
1064 return failure();
1065 }
1066 int64_t originalSize = vecType.getShape()[0];
1067 Location loc = stepOp.getLoc();
1068 SmallVector<int64_t> strides(1, 1);
1069
1070 Value result = arith::ConstantOp::create(builder&: rewriter, location: loc, result: vecType,
1071 value: rewriter.getZeroAttr(type: vecType));
1072
1073 auto targetVecType =
1074 VectorType::get(shape: *targetShape, elementType: vecType.getElementType());
1075 Value baseStep = vector::StepOp::create(builder&: rewriter, location: loc, result: targetVecType);
1076 for (const SmallVector<int64_t> &offsets :
1077 StaticTileOffsetRange({originalSize}, *targetShape)) {
1078 Value bcastOffset = arith::ConstantOp::create(
1079 builder&: rewriter, location: loc, result: targetVecType,
1080 value: DenseElementsAttr::get(
1081 type: targetVecType,
1082 values: IntegerAttr::get(type: targetVecType.getElementType(), value: offsets[0])));
1083 Value tileStep =
1084 arith::AddIOp::create(builder&: rewriter, location: loc, lhs: baseStep, rhs: bcastOffset);
1085
1086 result = rewriter.createOrFold<vector::InsertStridedSliceOp>(
1087 location: loc, args&: tileStep, args&: result, args: offsets, args&: strides);
1088 }
1089 rewriter.replaceOp(op: stepOp, newValues: result);
1090 return success();
1091 }
1092
1093private:
1094 vector::UnrollVectorOptions options;
1095};
1096
1097/// Unrolls 2 or more dimensional `vector.from_elements` ops by unrolling the
1098/// outermost dimension. For example:
1099/// ```
1100/// %v = vector.from_elements %e0, %e1, %e2, %e3, %e4, %e5 : vector<2x3xf32>
1101///
1102/// ==>
1103///
1104/// %0 = ub.poison : vector<2x3xf32>
1105/// %v0 = vector.from_elements %e0, %e1, %e2 : vector<3xf32>
1106/// %1 = vector.insert %v0, %0 [0] : vector<3xf32> into vector<2x3xf32>
1107/// %v1 = vector.from_elements %e3, %e4, %e5 : vector<3xf32>
1108/// %v = vector.insert %v1, %1 [1] : vector<3xf32> into vector<2x3xf32>
1109/// ```
1110///
1111/// When this pattern is applied until a fixed-point is reached,
1112/// this will produce a sequence of 1-d from_elements
1113/// ops.
1114struct UnrollFromElements : OpRewritePattern<vector::FromElementsOp> {
1115 UnrollFromElements(MLIRContext *context,
1116 const vector::UnrollVectorOptions &options,
1117 PatternBenefit benefit = 1)
1118 : OpRewritePattern<vector::FromElementsOp>(context, benefit),
1119 options(options) {}
1120
1121 LogicalResult matchAndRewrite(vector::FromElementsOp op,
1122 PatternRewriter &rewriter) const override {
1123 ValueRange allElements = op.getElements();
1124
1125 auto unrollFromElementsFn = [&](PatternRewriter &rewriter, Location loc,
1126 VectorType subTy, int64_t index) {
1127 size_t subTyNumElements = subTy.getNumElements();
1128 assert((index + 1) * subTyNumElements <= allElements.size() &&
1129 "out of bounds");
1130 ValueRange subElements =
1131 allElements.slice(n: index * subTyNumElements, m: subTyNumElements);
1132 return vector::FromElementsOp::create(builder&: rewriter, location: loc, result: subTy, elements: subElements);
1133 };
1134
1135 return unrollVectorOp(op, rewriter, unrollFn: unrollFromElementsFn);
1136 }
1137
1138private:
1139 vector::UnrollVectorOptions options;
1140};
1141
1142/// This pattern unrolls `vector.create_mask` operations into smaller mask
1143/// operations based on the target unroll shape. Each unrolled slice computes
1144/// its local mask size in each dimension (d) as:
1145/// min(max(originalMaskSize[d] - offset[d], 0), unrolledDimSize[d]).
1146/// Example:
1147/// Given a create_mask operation:
1148/// %0 = vector.create_mask %c6, %c10 : vector<8x16xi1> // mask first 6x10
1149/// elements
1150///
1151/// and a target unroll shape of <4x8>, the pattern produces:
1152///
1153/// %false = arith.constant dense<false> : vector<8x16xi1>
1154///
1155/// Slice [0,0]:
1156/// mask size = min(max(6-0, 0), 4) x min(max(10-0, 0), 8) = 4x8
1157/// %mask00 = vector.create_mask %c4, %c8 : vector<4x8xi1>
1158/// %r0 = vector.insert_strided_slice %mask00, %false [0, 0], [1, 1]
1159/// : vector<4x8xi1> into vector<8x16xi1>
1160/// Slice [0,8]:
1161/// mask size = min(max(6-0, 0), 4) x min(max(10-8, 0), 8) = 4x2
1162/// %mask01 = vector.create_mask %c4, %c2 : vector<4x8xi1>
1163/// %r1 = vector.insert_strided_slice %mask01, %r0 [0, 8], [1, 1]
1164/// : vector<4x8xi1> into vector<8x16xi1>
1165/// Slice [4,0]:
1166/// mask size = min(max(6-4, 0), 4) x min(max(10-0, 0), 8) = 2x8
1167/// %mask10 = vector.create_mask %c2, %c8 : vector<4x8xi1>
1168/// %r2 = vector.insert_strided_slice %mask10, %r1 [4, 0], [1, 1]
1169/// : vector<4x8xi1> into vector<8x16xi1>
1170/// Slice [4,8]:
1171/// mask size = min(max(6-4, 0), 4) x min(max(10-8, 0), 8) = 2x2
1172/// %mask11 = vector.create_mask %c2, %c2 : vector<4x8xi1>
1173/// %result = vector.insert_strided_slice %mask11, %r2 [4, 8], [1, 1]
1174/// : vector<4x8xi1> into vector<8x16xi1>
1175struct UnrollCreateMaskPattern : public OpRewritePattern<vector::CreateMaskOp> {
1176 UnrollCreateMaskPattern(MLIRContext *context,
1177 const vector::UnrollVectorOptions &options,
1178 PatternBenefit benefit = 1)
1179 : OpRewritePattern<vector::CreateMaskOp>(context, benefit),
1180 options(options) {}
1181
1182 LogicalResult matchAndRewrite(vector::CreateMaskOp createMaskOp,
1183 PatternRewriter &rewriter) const override {
1184 // TODO: This is shared between all Unroll patterns - merge.
1185 auto iface = cast<VectorUnrollOpInterface>(Val&: *createMaskOp);
1186 auto targetShape = getTargetShape(options, iface);
1187 if (!targetShape)
1188 return failure();
1189
1190 VectorType resultType = createMaskOp.getVectorType();
1191 SmallVector<int64_t> originalSize =
1192 *createMaskOp.getIterationShapeToUnroll();
1193 Location loc = createMaskOp.getLoc();
1194
1195 // `targetShape` may have a smaller rank than the op - pad with leading unit
1196 // dims.
1197 SmallVector<int64_t> adjustedTargetShape(originalSize.size(), 1);
1198 llvm::copy(Range&: *targetShape, Out: adjustedTargetShape.end() - targetShape->size());
1199
1200 Value result = arith::ConstantOp::create(builder&: rewriter, location: loc, result: resultType,
1201 value: rewriter.getZeroAttr(type: resultType));
1202 VectorType targetVectorType =
1203 VectorType::get(shape: adjustedTargetShape, elementType: rewriter.getI1Type());
1204 SmallVector<int64_t> strides(adjustedTargetShape.size(), 1);
1205
1206 // In each dimension (d), each unrolled vector computes its mask size as:
1207 // min(max(originalMaskOperands[d] - offset[d], 0), unrolledDimSize[d]).
1208 for (SmallVector<int64_t> offsets :
1209 StaticTileOffsetRange(originalSize, adjustedTargetShape)) {
1210 SmallVector<Value> unrolledOperands;
1211
1212 for (auto [i, originalMaskOperand] :
1213 llvm::enumerate(First: createMaskOp.getOperands())) {
1214 Value offsetVal =
1215 arith::ConstantIndexOp::create(builder&: rewriter, location: loc, value: offsets[i]);
1216 Value adjustedMaskSize = rewriter.createOrFold<arith::SubIOp>(
1217 location: loc, args&: originalMaskOperand, args&: offsetVal);
1218 Value zero = arith::ConstantIndexOp::create(builder&: rewriter, location: loc, value: 0);
1219 Value unrolledDimSize = arith::ConstantIndexOp::create(
1220 builder&: rewriter, location: loc, value: adjustedTargetShape[i]);
1221 Value nonNegative =
1222 rewriter.createOrFold<arith::MaxSIOp>(location: loc, args&: adjustedMaskSize, args&: zero);
1223 Value unrolledOperand = rewriter.createOrFold<arith::MinSIOp>(
1224 location: loc, args&: nonNegative, args&: unrolledDimSize);
1225 unrolledOperands.push_back(Elt: unrolledOperand);
1226 }
1227
1228 auto unrolledMask = rewriter.createOrFold<vector::CreateMaskOp>(
1229 location: loc, args&: targetVectorType, args&: unrolledOperands);
1230 result = rewriter.createOrFold<vector::InsertStridedSliceOp>(
1231 location: loc, args&: unrolledMask, args&: result, args&: offsets, args&: strides);
1232 }
1233 rewriter.replaceOp(op: createMaskOp, newValues: result);
1234 return success();
1235 }
1236
1237private:
1238 vector::UnrollVectorOptions options;
1239};
1240
1241/// This pattern unrolls `vector.constant_mask` operations into smaller mask
1242/// operations based on the target unroll shape. Each unrolled slice computes
1243/// whether its elements should be masked based on the original mask dimensions
1244/// and the slice's offset position.
1245///
1246/// Example:
1247/// Given a constant_mask operation:
1248/// %0 = vector.constant_mask [6, 10] : vector<8x16xi1>
1249///
1250/// and a target unroll shape of <4x8>, the pattern produces:
1251///
1252/// %false = arith.constant dense<false> : vector<8x16xi1>
1253///
1254/// Slice [0,0]: elements [0:4, 0:8] - fully within [6, 10] bounds
1255/// %mask00 = vector.constant_mask [4, 8] : vector<4x8xi1>
1256/// %r0 = vector.insert_strided_slice %mask00, %false [0, 0], [1, 1]
1257/// : vector<4x8xi1> into vector<8x16xi1>
1258///
1259/// Slice [0,8]: elements [0:4, 8:16] - partially within bounds
1260/// %mask01 = vector.constant_mask [4, 2] : vector<4x8xi1>
1261/// %r1 = vector.insert_strided_slice %mask01, %r0 [0, 8], [1, 1]
1262/// : vector<4x8xi1> into vector<8x16xi1>
1263///
1264/// Slice [4,0]: elements [4:8, 0:8] - partially within bounds
1265/// %mask10 = vector.constant_mask [2, 8] : vector<4x8xi1>
1266/// %r2 = vector.insert_strided_slice %mask10, %r1 [4, 0], [1, 1]
1267/// : vector<4x8xi1> into vector<8x16xi1>
1268///
1269/// Slice [4,8]: elements [4:8, 8:16] - partially within bounds
1270/// %mask11 = vector.constant_mask [2, 2] : vector<4x8xi1>
1271/// %result = vector.insert_strided_slice %mask11, %r2 [4, 8], [1, 1]
1272/// : vector<4x8xi1> into vector<8x16xi1>
1273struct UnrollConstantMaskPattern
1274 : public OpRewritePattern<vector::ConstantMaskOp> {
1275 UnrollConstantMaskPattern(MLIRContext *context,
1276 const vector::UnrollVectorOptions &options,
1277 PatternBenefit benefit = 1)
1278 : OpRewritePattern<vector::ConstantMaskOp>(context, benefit),
1279 options(options) {}
1280
1281 LogicalResult matchAndRewrite(vector::ConstantMaskOp constantMaskOp,
1282 PatternRewriter &rewriter) const override {
1283 // TODO: This is shared between all Unroll patterns - merge.
1284 auto iface = cast<VectorUnrollOpInterface>(Val&: *constantMaskOp);
1285 auto targetShape = getTargetShape(options, iface);
1286 if (!targetShape)
1287 return failure();
1288
1289 VectorType resultType = constantMaskOp.getVectorType();
1290 SmallVector<int64_t> originalSize =
1291 *constantMaskOp.getIterationShapeToUnroll();
1292 Location loc = constantMaskOp.getLoc();
1293
1294 // `targetShape` may have a smaller rank than the op - pad with leading unit
1295 // dims.
1296 SmallVector<int64_t> adjustedTargetShape(originalSize.size(), 1);
1297 llvm::copy(Range&: *targetShape, Out: adjustedTargetShape.end() - targetShape->size());
1298
1299 Value result = arith::ConstantOp::create(builder&: rewriter, location: loc, result: resultType,
1300 value: rewriter.getZeroAttr(type: resultType));
1301 VectorType targetVectorType =
1302 VectorType::get(shape: adjustedTargetShape, elementType: rewriter.getI1Type());
1303 SmallVector<int64_t> strides(adjustedTargetShape.size(), 1);
1304
1305 // In each dimension (d), each unrolled vector computes its mask size as:
1306 // min(max(originalMaskDim[d] - offset[d], 0), unrolledDimSize[d]).
1307 for (const SmallVector<int64_t> &offsets :
1308 StaticTileOffsetRange(originalSize, adjustedTargetShape)) {
1309 SmallVector<int64_t> unrolledMaskDims;
1310
1311 for (auto [i, originalMaskDim] :
1312 llvm::enumerate(First: constantMaskOp.getMaskDimSizes())) {
1313 // Calculate how many elements in this dimension should be masked
1314 // for this particular slice
1315 int64_t adjustedMaskSize =
1316 std::max(a: originalMaskDim - offsets[i], b: static_cast<int64_t>(0));
1317 int64_t unrolledMaskDim =
1318 std::min(a: adjustedMaskSize, b: adjustedTargetShape[i]);
1319 unrolledMaskDims.push_back(Elt: unrolledMaskDim);
1320 }
1321
1322 // If any of 'unrolledMaskDims' is zero, then the mask is effectively ALL
1323 // FALSE and we can set all dims to zero (masked region is a conjunction
1324 // of mask dim intervals).
1325 if (llvm::is_contained(Range&: unrolledMaskDims, Element: 0))
1326 unrolledMaskDims.assign(NumElts: unrolledMaskDims.size(), Elt: 0);
1327
1328 auto unrolledMask = rewriter.createOrFold<vector::ConstantMaskOp>(
1329 location: loc, args&: targetVectorType, args&: unrolledMaskDims);
1330 result = rewriter.createOrFold<vector::InsertStridedSliceOp>(
1331 location: loc, args&: unrolledMask, args&: result, args: offsets, args&: strides);
1332 }
1333 rewriter.replaceOp(op: constantMaskOp, newValues: result);
1334 return success();
1335 }
1336
1337private:
1338 vector::UnrollVectorOptions options;
1339};
1340
1341/// Checks whether extractShape is a contiguous slice of shape.
1342/// For extractShape to be contiguous in shape:
1343/// 1) All but the leading dimension of extractShape and shape must match
1344/// exactly. 2) The total number of elements in shape must be evenly divisible
1345/// by
1346/// the total number of elements in extractShape.
1347/// Examples:
1348/// isContiguous([4, 4], [8, 4]) == true
1349/// isContiguous([2, 4], [8, 4]) == true
1350/// isContiguous([2, 2], [8, 4]) == false
1351/// Removes leading unit dimensions to handle cases like:
1352/// isContiguous([1, 16], [1, 32]) == true
1353static bool isContiguous(ArrayRef<int64_t> extractShape,
1354 ArrayRef<int64_t> shape) {
1355
1356 if (extractShape.empty() || shape.empty() ||
1357 extractShape.size() > shape.size())
1358 return false;
1359
1360 while (extractShape.size() > 1 && extractShape.front() == 1)
1361 extractShape = extractShape.drop_front();
1362
1363 while (shape.size() > 1 && shape.front() == 1) {
1364 shape = shape.drop_front();
1365 }
1366
1367 size_t rankDiff = shape.size() - extractShape.size();
1368 if (!llvm::equal(LRange: extractShape.drop_front(), RRange: shape.drop_front(N: rankDiff + 1)))
1369 return false;
1370
1371 int64_t extractElements = ShapedType::getNumElements(shape: extractShape);
1372 int64_t shapeElements = ShapedType::getNumElements(shape);
1373 return shapeElements % extractElements == 0;
1374}
1375
1376/// Determines what shape to use with `vector.extract_strided_slice` to extract
1377/// a contiguous memory region from a source vector. The extraction must be
1378/// contiguous and contain exactly the specified number of elements. If such an
1379/// extraction shape cannot be determined, returns std::nullopt.
1380/// EXAMPLE 1:
1381/// sourceShape = [16], targetElements = 8
1382/// Working right-to-left:
1383/// - Take min(8, 16) = 8 from only dim → extractShape = [8],
1384/// remaining = 8/8 = 1
1385/// Result: [8]
1386///
1387/// EXAMPLE 2:
1388/// sourceShape = [4, 4], targetElements = 8
1389/// Working right-to-left:
1390/// - Take min(8, 4) = 4 from last dim → extractShape = [4],
1391/// remaining = 8/4 = 2
1392/// - Take min(2, 4) = 2 from first dim → extractShape = [2, 4],
1393/// remaining = 2/2 = 1
1394/// Result: [2, 4]
1395static std::optional<SmallVector<int64_t>>
1396calculateSourceExtractShape(ArrayRef<int64_t> sourceShape,
1397 int64_t targetElements) {
1398 SmallVector<int64_t> extractShape;
1399 int64_t remainingElements = targetElements;
1400
1401 // Build extract shape from innermost dimension outward to ensure contiguity.
1402 for (int i = sourceShape.size() - 1; i >= 0 && remainingElements > 1; --i) {
1403 int64_t takeFromDim = std::min(a: remainingElements, b: sourceShape[i]);
1404 extractShape.insert(I: extractShape.begin(), Elt: takeFromDim);
1405
1406 if (remainingElements % takeFromDim != 0)
1407 return std::nullopt; // Not evenly divisible.
1408 remainingElements /= takeFromDim;
1409 }
1410
1411 // Fill remaining dimensions with 1.
1412 while (extractShape.size() < sourceShape.size())
1413 extractShape.insert(I: extractShape.begin(), Elt: 1);
1414
1415 if (ShapedType::getNumElements(shape: extractShape) != targetElements)
1416 return std::nullopt;
1417
1418 return extractShape;
1419}
1420
1421// Convert result offsets to source offsets via linear position.
1422static SmallVector<int64_t>
1423calculateSourceOffsets(ArrayRef<int64_t> resultOffsets,
1424 ArrayRef<int64_t> sourceShape,
1425 ArrayRef<int64_t> resultShape) {
1426 // Convert result offsets to linear position.
1427 int64_t linearIndex = linearize(offsets: resultOffsets, basis: computeStrides(sizes: resultShape));
1428 // Convert linear position to source offsets.
1429 return delinearize(linearIndex, strides: computeStrides(sizes: sourceShape));
1430}
1431
1432/// A maximal aligned range of source dims [srcBegin, srcEnd) and result dims
1433/// [resBegin, resEnd) of a `vector.shape_cast` that hold equal element counts.
1434struct ShapeCastReassociationGroup {
1435 int64_t srcBegin, srcEnd;
1436 int64_t resBegin, resEnd;
1437};
1438
1439/// Splits a shape_cast from `sourceShape` to `resultShape` into reassociation
1440/// groups (trailing unit dims absorbed). Returns nullopt if shapes misalign.
1441/// E.g. [8, 32, 32] -> [256, 32] ==> {[0,2)->[0,1)}, {[2,3)->[1,2)}
1442static std::optional<SmallVector<ShapeCastReassociationGroup>>
1443computeShapeCastGroups(ArrayRef<int64_t> sourceShape,
1444 ArrayRef<int64_t> resultShape) {
1445 SmallVector<ShapeCastReassociationGroup> groups;
1446 int64_t si = 0, ri = 0;
1447 int64_t srcRank = sourceShape.size(), resRank = resultShape.size();
1448 while (si < srcRank && ri < resRank) {
1449 int64_t srcBegin = si, resBegin = ri;
1450 int64_t srcProd = sourceShape[si++];
1451 int64_t resProd = resultShape[ri++];
1452 // Grow the smaller side until both groups span the same element count.
1453 while (srcProd != resProd) {
1454 if (srcProd < resProd) {
1455 if (si >= srcRank)
1456 return std::nullopt;
1457 srcProd *= sourceShape[si++];
1458 } else {
1459 if (ri >= resRank)
1460 return std::nullopt;
1461 resProd *= resultShape[ri++];
1462 }
1463 }
1464 // Absorb trailing unit dimensions into the current group.
1465 while (si < srcRank && sourceShape[si] == 1)
1466 ++si;
1467 while (ri < resRank && resultShape[ri] == 1)
1468 ++ri;
1469 groups.push_back(Elt: {.srcBegin: srcBegin, .srcEnd: si, .resBegin: resBegin, .resEnd: ri});
1470 }
1471 if (si != srcRank || ri != resRank)
1472 return std::nullopt;
1473 return groups;
1474}
1475
1476/// This pattern unrolls `vector.shape_cast` operations according to the
1477/// provided target unroll shape. It unrolls a large shape cast into smaller
1478/// shape casts by extracting contiguous slices from the source vector, casting
1479/// each slice to the target shape, and assembling the result by inserting each
1480/// computed segment into the appropriate offset of the result vector.
1481///
1482/// The target tile need only be contiguous within each reassociation group of
1483/// the cast (not in the whole result vector), so that each extracted slice
1484/// remains a valid vector. The unrolling proceeds as:
1485/// vector.extract_strided_slice -> vector.shape_cast (on the slice) ->
1486/// vector.insert_strided_slice.
1487///
1488/// NOTE: This replaces a NOP `vector.shape_cast` with strided slices. Per-group
1489/// contiguity keeps those slices contiguous, so they are expected to lower to a
1490/// NOP too. Targets where strided slices do not lower to a NOP should not use
1491/// this pattern, or should pick a tile that avoids introducing such slices.
1492///
1493/// Example (single group):
1494/// Given a shape cast operation:
1495/// %0 = vector.shape_cast %src : vector<8x2xf32> to vector<4x4xf32>
1496///
1497/// and a target unroll shape of <2x4>, the pattern produces:
1498///
1499/// %zero = arith.constant dense<0.0> : vector<4x4xf32>
1500/// %s0 = vector.extract_strided_slice %src [0, 0], [4, 2], [1, 1]
1501/// : vector<8x2xf32> to vector<4x2xf32>
1502/// %sc0 = vector.shape_cast %s0 : vector<4x2xf32> to vector<2x4xf32>
1503/// %i0 = vector.insert_strided_slice %sc0, %zero [0, 0], [1, 1]
1504/// : vector<2x4xf32> into vector<4x4xf32>
1505/// %s1 = vector.extract_strided_slice %src [4, 0], [4, 2], [1, 1]
1506/// : vector<8x2xf32> to vector<4x2xf32>
1507/// %sc1 = vector.shape_cast %s1 : vector<4x2xf32> to vector<2x4xf32>
1508/// %i1 = vector.insert_strided_slice %sc1, %i0 [2, 0], [1, 1]
1509/// : vector<2x4xf32> into vector<4x4xf32>
1510///
1511/// Example (multiple groups): with target tile <8x1x4>, the tile is strided in
1512/// the result <8x1x32> but contiguous per group (8|32 -> 8x1|32), so the
1513/// matching strided box <8x4> is extracted from the source:
1514/// %0 = vector.shape_cast %src : vector<8x32xf32> to vector<8x1x32xf32>
1515///
1516/// %s0 = vector.extract_strided_slice %src [0, 0], [8, 4], [1, 1]
1517/// : vector<8x32xf32> to vector<8x4xf32>
1518/// %sc0 = vector.shape_cast %s0 : vector<8x4xf32> to vector<8x1x4xf32>
1519/// %i0 = vector.insert_strided_slice %sc0, %zero [0, 0, 0], [1, 1, 1]
1520/// : vector<8x1x4xf32> into vector<8x1x32xf32>
1521/// // ... repeat for the remaining slices.
1522///
1523struct UnrollShapeCastPattern : public OpRewritePattern<vector::ShapeCastOp> {
1524 UnrollShapeCastPattern(MLIRContext *context,
1525 const vector::UnrollVectorOptions &options,
1526 PatternBenefit benefit = 1)
1527 : OpRewritePattern<vector::ShapeCastOp>(context, benefit),
1528 options(options) {}
1529
1530 LogicalResult matchAndRewrite(vector::ShapeCastOp shapeCastOp,
1531 PatternRewriter &rewriter) const override {
1532 // TODO: This is shared between all Unroll patterns - merge.
1533 auto iface = cast<VectorUnrollOpInterface>(Val&: *shapeCastOp);
1534 auto targetShape = getTargetShape(options, iface);
1535 if (!targetShape)
1536 return failure();
1537
1538 VectorType sourceType = shapeCastOp.getSourceVectorType();
1539 VectorType resultType = shapeCastOp.getResultVectorType();
1540 ArrayRef<int64_t> sourceShape = sourceType.getShape();
1541 ArrayRef<int64_t> resultShape = resultType.getShape();
1542
1543 // The cast factors into reassociation groups; the target tile only needs to
1544 // be contiguous within each group, not in the whole result vector.
1545 std::optional<SmallVector<ShapeCastReassociationGroup>> groups =
1546 computeShapeCastGroups(sourceShape, resultShape);
1547 if (!groups)
1548 return rewriter.notifyMatchFailure(
1549 arg&: shapeCastOp, msg: "cannot align source and result reassociation groups");
1550
1551 // The tile is right-aligned against the result; left-pad with 1s so it can
1552 // be indexed per group.
1553 SmallVector<int64_t> paddedTarget(resultShape.size(), 1);
1554 llvm::copy(Range&: *targetShape,
1555 Out: paddedTarget.end() - static_cast<int64_t>(targetShape->size()));
1556
1557 // Validate per-group contiguity and build the source extract shape.
1558 SmallVector<int64_t> extractShapeStorage;
1559 for (const ShapeCastReassociationGroup &g : *groups) {
1560 ArrayRef<int64_t> resSub =
1561 resultShape.slice(N: g.resBegin, M: g.resEnd - g.resBegin);
1562 ArrayRef<int64_t> tgtSub = ArrayRef<int64_t>(paddedTarget)
1563 .slice(N: g.resBegin, M: g.resEnd - g.resBegin);
1564 if (!isContiguous(extractShape: tgtSub, shape: resSub))
1565 return rewriter.notifyMatchFailure(
1566 arg&: shapeCastOp, msg: "target shape is not contiguous within a "
1567 "reassociation group of the result vector shape");
1568
1569 ArrayRef<int64_t> srcSub =
1570 sourceShape.slice(N: g.srcBegin, M: g.srcEnd - g.srcBegin);
1571 int64_t groupTargetElements = ShapedType::getNumElements(shape: tgtSub);
1572 std::optional<SmallVector<int64_t>> groupExtract =
1573 calculateSourceExtractShape(sourceShape: srcSub, targetElements: groupTargetElements);
1574 if (!groupExtract)
1575 return rewriter.notifyMatchFailure(
1576 arg&: shapeCastOp, msg: "cannot extract the target number of elements "
1577 "contiguously from a source reassociation group");
1578 extractShapeStorage.append(in_start: groupExtract->begin(), in_end: groupExtract->end());
1579 }
1580 ArrayRef<int64_t> extractShape = extractShapeStorage;
1581
1582 Location loc = shapeCastOp.getLoc();
1583
1584 // Create result vector initialized to zero.
1585 Value result = arith::ConstantOp::create(builder&: rewriter, location: loc, result: resultType,
1586 value: rewriter.getZeroAttr(type: resultType));
1587
1588 VectorType targetType =
1589 VectorType::get(shape: *targetShape, elementType: sourceType.getElementType());
1590
1591 SmallVector<int64_t> extractStrides(extractShape.size(), 1);
1592 SmallVector<int64_t> insertStrides(targetShape->size(), 1);
1593
1594 for (SmallVector<int64_t> resultOffsets :
1595 StaticTileOffsetRange(resultShape, *targetShape)) {
1596 SmallVector<int64_t> sourceOffsets =
1597 calculateSourceOffsets(resultOffsets, sourceShape, resultShape);
1598 Value sourceChunk = rewriter.createOrFold<vector::ExtractStridedSliceOp>(
1599 location: loc, args: shapeCastOp.getSource(), args&: sourceOffsets, args&: extractShape,
1600 args&: extractStrides);
1601 Value targetChunk = rewriter.createOrFold<vector::ShapeCastOp>(
1602 location: loc, args&: targetType, args&: sourceChunk);
1603 result = rewriter.createOrFold<vector::InsertStridedSliceOp>(
1604 location: loc, args&: targetChunk, args&: result, args&: resultOffsets, args&: insertStrides);
1605 }
1606
1607 rewriter.replaceOp(op: shapeCastOp, newValues: result);
1608 return success();
1609 }
1610
1611private:
1612 vector::UnrollVectorOptions options;
1613};
1614
1615// Unroll vector::BitCastOp into smaller slice-based bitcast operations.
1616// Decomposes the result vector into target shape chunks and bitcasts
1617// corresponding source slices, accounting for element bitwidth ratios.
1618/// Example:
1619/// Given a bitcast Op:
1620///
1621/// vector.bitcast %src : vector<4x8xf32>
1622///
1623/// and a target unroll shape of <2x4>, the pattern produces:
1624///
1625/// %slice_0 = vector.extract_strided_slice %lhs[0, 0] : vector<2x4xf32>
1626/// %slice_0 = vector.bitcast %slice_0 : vector<2x4xf32>
1627/// %result = vector.insert_strided_slice %slice_0, %init[0, 0]
1628/// // ... repeat for remaining slices
1629struct UnrollBitCastPattern : public OpRewritePattern<vector::BitCastOp> {
1630 UnrollBitCastPattern(MLIRContext *context,
1631 const vector::UnrollVectorOptions &options,
1632 PatternBenefit benefit = 1)
1633 : OpRewritePattern<vector::BitCastOp>(context, benefit),
1634 options(options) {}
1635
1636 LogicalResult matchAndRewrite(vector::BitCastOp bitCastOp,
1637 PatternRewriter &rewriter) const override {
1638 // TODO: This is shared between all Unroll patterns - merge.
1639 auto iface = cast<VectorUnrollOpInterface>(Val&: *bitCastOp);
1640 auto targetShape = getTargetShape(options, iface);
1641 if (!targetShape)
1642 return rewriter.notifyMatchFailure(arg&: bitCastOp,
1643 msg: "failed to get target shape");
1644
1645 VectorType sourceType = bitCastOp.getSourceVectorType();
1646 VectorType resultType = bitCastOp.getResultVectorType();
1647 ArrayRef<int64_t> resultShape = resultType.getShape();
1648 Location loc = bitCastOp.getLoc();
1649
1650 if (targetShape->size() != resultShape.size())
1651 return rewriter.notifyMatchFailure(
1652 arg&: bitCastOp, msg: "target shape rank must match result rank");
1653
1654 unsigned sourceElementBits = sourceType.getElementTypeBitWidth();
1655 unsigned resultElementBits = resultType.getElementTypeBitWidth();
1656
1657 SmallVector<int64_t> sourceSliceShape(targetShape->begin(),
1658 targetShape->end());
1659 int64_t lastDim = sourceSliceShape.size() - 1;
1660
1661 sourceSliceShape[lastDim] =
1662 ((*targetShape)[lastDim] * resultElementBits) / sourceElementBits;
1663
1664 Value result = arith::ConstantOp::create(builder&: rewriter, location: loc, result: resultType,
1665 value: rewriter.getZeroAttr(type: resultType));
1666 SmallVector<int64_t> resultStrides(targetShape->size(), 1);
1667 SmallVector<int64_t> sourceStrides(sourceSliceShape.size(), 1);
1668
1669 VectorType targetType =
1670 VectorType::get(shape: *targetShape, elementType: resultType.getElementType());
1671
1672 for (SmallVector<int64_t> resultOffsets :
1673 StaticTileOffsetRange(resultShape, *targetShape)) {
1674 SmallVector<int64_t> sourceOffsets = resultOffsets;
1675 sourceOffsets[lastDim] =
1676 (resultOffsets[lastDim] * resultElementBits) / sourceElementBits;
1677
1678 Value sourceSlice = rewriter.createOrFold<vector::ExtractStridedSliceOp>(
1679 location: loc, args: bitCastOp.getSource(), args&: sourceOffsets, args&: sourceSliceShape,
1680 args&: sourceStrides);
1681 Value bitcastSlice = rewriter.createOrFold<vector::BitCastOp>(
1682 location: loc, args&: targetType, args&: sourceSlice);
1683 result = rewriter.createOrFold<vector::InsertStridedSliceOp>(
1684 location: loc, args&: bitcastSlice, args&: result, args&: resultOffsets, args&: resultStrides);
1685 }
1686
1687 rewriter.replaceOp(op: bitCastOp, newValues: result);
1688 return success();
1689 }
1690
1691private:
1692 vector::UnrollVectorOptions options;
1693};
1694
1695/// Pattern to unroll vector.interleave into smaller slice-sized operations.
1696/// Decomposes a large interleave into slices by extracting slices from both
1697/// input vectors, interleaving them, and inserting back into the result.
1698///
1699/// Example:
1700/// Given an interleave Op:
1701///
1702/// vector.interleave %lhs, %rhs : vector<4x8xf32>
1703///
1704/// and a target unroll shape of <2x4>, the pattern produces:
1705///
1706/// %slice_lhs_0 = vector.extract_strided_slice %lhs[0, 0] : vector<2x2xf32>
1707/// %slice_rhs_0 = vector.extract_strided_slice %rhs[0, 0] : vector<2x2xf32>
1708/// %slice_0 = vector.interleave %slice_lhs_0, %slice_rhs_0
1709/// : vector<2x4xf32>
1710/// %result = vector.insert_strided_slice %slice_0, %init[0, 0]
1711/// // ... repeat for remaining slices
1712struct UnrollInterleavePattern : public OpRewritePattern<vector::InterleaveOp> {
1713 UnrollInterleavePattern(MLIRContext *context,
1714 const vector::UnrollVectorOptions &options,
1715 PatternBenefit benefit = 1)
1716 : OpRewritePattern<vector::InterleaveOp>(context, benefit),
1717 options(options) {}
1718
1719 LogicalResult matchAndRewrite(vector::InterleaveOp interleaveOp,
1720 PatternRewriter &rewriter) const override {
1721 // TODO: This is shared between all Unroll patterns - merge.
1722 auto iface = cast<VectorUnrollOpInterface>(Val&: *interleaveOp);
1723 auto targetShape = getTargetShape(options, iface);
1724 if (!targetShape)
1725 return rewriter.notifyMatchFailure(arg&: interleaveOp,
1726 msg: "failed to get target shape");
1727
1728 VectorType resultType = interleaveOp.getResultVectorType();
1729 ArrayRef<int64_t> resultShape = resultType.getShape();
1730 Location loc = interleaveOp.getLoc();
1731
1732 if (targetShape->size() != resultShape.size())
1733 return rewriter.notifyMatchFailure(
1734 arg&: interleaveOp, msg: "target shape rank must match result rank");
1735
1736 SmallVector<int64_t> sourceSliceShape(targetShape->begin(),
1737 targetShape->end());
1738 int64_t lastDim = sourceSliceShape.size() - 1;
1739 sourceSliceShape[lastDim] = (*targetShape)[lastDim] / 2;
1740
1741 Value result = arith::ConstantOp::create(builder&: rewriter, location: loc, result: resultType,
1742 value: rewriter.getZeroAttr(type: resultType));
1743 SmallVector<int64_t> resultStrides(targetShape->size(), 1);
1744 SmallVector<int64_t> sourceStrides(sourceSliceShape.size(), 1);
1745
1746 VectorType targetType =
1747 VectorType::get(shape: *targetShape, elementType: resultType.getElementType());
1748
1749 for (SmallVector<int64_t> resultOffsets :
1750 StaticTileOffsetRange(resultShape, *targetShape)) {
1751 SmallVector<int64_t> sourceOffsets = resultOffsets;
1752 sourceOffsets[lastDim] = resultOffsets[lastDim] / 2;
1753
1754 Value lhsSlice = rewriter.createOrFold<vector::ExtractStridedSliceOp>(
1755 location: loc, args: interleaveOp.getLhs(), args&: sourceOffsets, args&: sourceSliceShape,
1756 args&: sourceStrides);
1757 Value rhsSlice = rewriter.createOrFold<vector::ExtractStridedSliceOp>(
1758 location: loc, args: interleaveOp.getRhs(), args&: sourceOffsets, args&: sourceSliceShape,
1759 args&: sourceStrides);
1760 Value interleaveSlice = rewriter.createOrFold<vector::InterleaveOp>(
1761 location: loc, args&: targetType, args&: lhsSlice, args&: rhsSlice);
1762 result = rewriter.createOrFold<vector::InsertStridedSliceOp>(
1763 location: loc, args&: interleaveSlice, args&: result, args&: resultOffsets, args&: resultStrides);
1764 }
1765
1766 rewriter.replaceOp(op: interleaveOp, newValues: result);
1767 return success();
1768 }
1769
1770private:
1771 vector::UnrollVectorOptions options;
1772};
1773
1774/// Pattern to unroll vector.deinterleave into smaller slice-sized operations.
1775/// Decomposes a large deinterleave (which splits a vector into even/odd halves)
1776/// by extracting source slices, deinterleaving them, and inserting into two
1777/// result vectors.
1778///
1779/// Example:
1780/// Given a deinterleave Op:
1781///
1782/// vector.deinterleave %src : vector<4x8xf32>
1783///
1784/// and a target unroll shape of <2x4>, the pattern produces:
1785///
1786/// %slice_0 = vector.extract_strided_slice %src[0, 0] : vector<2x4xf32>
1787/// %slice_lhs_0, %slice_rhs_0 = vector.deinterleave %slice_0 :
1788/// vector<2x4xf32> %result1 = vector.insert_strided_slice %slice_lhs_0,
1789/// %init1[0, 0] %result2 = vector.insert_strided_slice %slice_rhs_0,
1790/// %init2[0, 0]
1791/// // ... repeat for remaining slices
1792struct UnrollDeinterleavePattern
1793 : public OpRewritePattern<vector::DeinterleaveOp> {
1794 UnrollDeinterleavePattern(MLIRContext *context,
1795 const vector::UnrollVectorOptions &options,
1796 PatternBenefit benefit = 1)
1797 : OpRewritePattern<vector::DeinterleaveOp>(context, benefit),
1798 options(options) {}
1799
1800 LogicalResult matchAndRewrite(vector::DeinterleaveOp deinterleaveOp,
1801 PatternRewriter &rewriter) const override {
1802 // TODO: This is shared between all Unroll patterns - merge.
1803 auto iface = cast<VectorUnrollOpInterface>(Val&: *deinterleaveOp);
1804 auto targetShape = getTargetShape(options, iface);
1805 if (!targetShape)
1806 return rewriter.notifyMatchFailure(arg&: deinterleaveOp,
1807 msg: "failed to get target shape");
1808
1809 VectorType resultType = deinterleaveOp.getResultVectorType();
1810 ArrayRef<int64_t> resultShape = resultType.getShape();
1811 Location loc = deinterleaveOp.getLoc();
1812
1813 if (targetShape->size() != resultShape.size())
1814 return rewriter.notifyMatchFailure(
1815 arg&: deinterleaveOp, msg: "target shape rank must match result rank");
1816
1817 SmallVector<int64_t> sourceSliceShape(targetShape->begin(),
1818 targetShape->end());
1819 int64_t lastDim = sourceSliceShape.size() - 1;
1820 sourceSliceShape[lastDim] = (*targetShape)[lastDim] * 2;
1821
1822 Value resultOdd = arith::ConstantOp::create(
1823 builder&: rewriter, location: loc, result: resultType, value: rewriter.getZeroAttr(type: resultType));
1824 Value resultEven = arith::ConstantOp::create(
1825 builder&: rewriter, location: loc, result: resultType, value: rewriter.getZeroAttr(type: resultType));
1826 SmallVector<int64_t> resultStrides(targetShape->size(), 1);
1827 SmallVector<int64_t> sourceStrides(sourceSliceShape.size(), 1);
1828
1829 for (SmallVector<int64_t> resultOffsets :
1830 StaticTileOffsetRange(resultShape, *targetShape)) {
1831 SmallVector<int64_t> sourceOffsets = resultOffsets;
1832 sourceOffsets[lastDim] = resultOffsets[lastDim] * 2;
1833
1834 Value sourceSlice = rewriter.createOrFold<vector::ExtractStridedSliceOp>(
1835 location: loc, args: deinterleaveOp.getSource(), args&: sourceOffsets, args&: sourceSliceShape,
1836 args&: sourceStrides);
1837
1838 auto deinterleaveSlice =
1839 vector::DeinterleaveOp::create(builder&: rewriter, location: loc, source: sourceSlice);
1840
1841 resultOdd = rewriter.createOrFold<vector::InsertStridedSliceOp>(
1842 location: loc, args: deinterleaveSlice.getResultEven(), args&: resultOdd, args&: resultOffsets,
1843 args&: resultStrides);
1844 resultEven = rewriter.createOrFold<vector::InsertStridedSliceOp>(
1845 location: loc, args: deinterleaveSlice.getResultOdd(), args&: resultEven, args&: resultOffsets,
1846 args&: resultStrides);
1847 }
1848
1849 rewriter.replaceOp(op: deinterleaveOp, newValues: ValueRange{resultOdd, resultEven});
1850 return success();
1851 }
1852
1853private:
1854 vector::UnrollVectorOptions options;
1855};
1856} // namespace
1857
1858void mlir::vector::populateVectorUnrollPatterns(
1859 RewritePatternSet &patterns, const UnrollVectorOptions &options,
1860 PatternBenefit benefit) {
1861 patterns.add<UnrollTransferReadPattern, UnrollTransferWritePattern,
1862 UnrollContractionPattern, UnrollElementwisePattern,
1863 UnrollReductionPattern, UnrollMultiReductionPattern,
1864 UnrollTransposePattern, UnrollGatherPattern, UnrollLoadPattern,
1865 UnrollStorePattern, UnrollBroadcastPattern, UnrollFromElements,
1866 UnrollToElements, UnrollStepPattern, UnrollShapeCastPattern,
1867 UnrollCreateMaskPattern, UnrollConstantMaskPattern,
1868 UnrollBitCastPattern, UnrollInterleavePattern,
1869 UnrollDeinterleavePattern>(arg: patterns.getContext(), args: options,
1870 args&: benefit);
1871}
1872
1873void mlir::vector::populateVectorContractUnrollPatterns(
1874 RewritePatternSet &patterns, const UnrollVectorOptions &options,
1875 PatternBenefit benefit) {
1876 patterns.add<UnrollContractionPattern>(arg: patterns.getContext(), args: options,
1877 args&: benefit);
1878}
1879
1880void mlir::vector::populateVectorToElementsUnrollPatterns(
1881 RewritePatternSet &patterns, PatternBenefit benefit) {
1882 patterns.add<UnrollToElements>(arg: patterns.getContext(), args: UnrollVectorOptions(),
1883 args&: benefit);
1884}
1885
1886void mlir::vector::populateVectorFromElementsUnrollPatterns(
1887 RewritePatternSet &patterns, PatternBenefit benefit) {
1888 patterns.add<UnrollFromElements>(arg: patterns.getContext(), args: UnrollVectorOptions(),
1889 args&: benefit);
1890}
1891