1//===- RankReductionPatterns.cpp - Patterns related to rank reductions ----===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9#include "mlir/Dialect/Affine/IR/AffineOps.h"
10#include "mlir/Dialect/Arith/Utils/Utils.h"
11#include "mlir/Dialect/Tensor/IR/Tensor.h"
12#include "mlir/Dialect/Tensor/Transforms/Transforms.h"
13#include "mlir/IR/PatternMatch.h"
14#include "mlir/IR/Value.h"
15#include "mlir/Interfaces/ValueBoundsOpInterface.h"
16#include "llvm/ADT/STLExtras.h"
17#include "llvm/Support/LogicalResult.h"
18
19using namespace mlir;
20using namespace mlir::tensor;
21
22namespace {
23/// Fold expand_shape(extract_slice) ops that cancel itself out.
24struct FoldExpandOfRankReducingExtract
25 : public OpRewritePattern<ExpandShapeOp> {
26 using OpRewritePattern<ExpandShapeOp>::OpRewritePattern;
27
28 LogicalResult matchAndRewrite(ExpandShapeOp expandShapeOp,
29 PatternRewriter &rewriter) const override {
30 RankedTensorType resultType = expandShapeOp.getResultType();
31 auto extractSliceOp =
32 expandShapeOp.getSrc().getDefiningOp<ExtractSliceOp>();
33 if (!extractSliceOp)
34 return failure();
35 RankedTensorType srcType = extractSliceOp.getSourceType();
36
37 // Only cases where the ExpandShapeOp can be folded away entirely are
38 // supported. Moreover, only simple cases where the resulting ExtractSliceOp
39 // has no rank-reduction anymore are supported at the moment.
40 RankedTensorType nonReducingExtractType = ExtractSliceOp::inferResultType(
41 sourceTensorType: srcType, staticSizes: extractSliceOp.getStaticSizes());
42 if (nonReducingExtractType != resultType)
43 return failure();
44
45 SmallVector<OpFoldResult> mixedOffsets = extractSliceOp.getMixedOffsets();
46 SmallVector<OpFoldResult> mixedSizes = extractSliceOp.getMixedSizes();
47 SmallVector<OpFoldResult> mixedStrides = extractSliceOp.getMixedStrides();
48 rewriter.replaceOpWithNewOp<tensor::ExtractSliceOp>(
49 op: expandShapeOp, args: extractSliceOp.getSource(), args&: mixedOffsets, args&: mixedSizes,
50 args&: mixedStrides);
51 return success();
52 }
53};
54
55/// Fold a full-slice rank-reducing extract_slice of an expand_shape back to
56/// the expand_shape source when the expanded and sliced dimensions match.
57struct FoldExtractSliceOfExpandShape : public OpRewritePattern<ExtractSliceOp> {
58 using OpRewritePattern<ExtractSliceOp>::OpRewritePattern;
59
60 LogicalResult matchAndRewrite(ExtractSliceOp sliceOp,
61 PatternRewriter &rewriter) const override {
62 auto expandOp = sliceOp.getSource().getDefiningOp<ExpandShapeOp>();
63 if (!expandOp)
64 return failure();
65
66 if (sliceOp.getType() != expandOp.getSrcType())
67 return rewriter.notifyMatchFailure(
68 arg&: sliceOp, msg: "slice result type does not match expand_shape source type");
69
70 SmallVector<OpFoldResult> mixedExpandedSizes =
71 expandOp.getMixedOutputShape();
72 if (mixedExpandedSizes.size() != sliceOp.getMixedSizes().size())
73 return rewriter.notifyMatchFailure(
74 arg&: sliceOp, msg: "expand_shape output rank does not match slice rank");
75
76 for (auto [offset, size, stride, expandedSize] :
77 llvm::zip_equal(t: sliceOp.getMixedOffsets(), u: sliceOp.getMixedSizes(),
78 args: sliceOp.getMixedStrides(), args&: mixedExpandedSizes)) {
79 if (getConstantIntValue(ofr: offset) != static_cast<int64_t>(0) ||
80 getConstantIntValue(ofr: stride) != static_cast<int64_t>(1))
81 return rewriter.notifyMatchFailure(
82 arg&: sliceOp, msg: "slice is not a zero-offset, unit-stride full slice");
83 if (size != expandedSize)
84 return rewriter.notifyMatchFailure(
85 arg&: sliceOp, msg: "slice size does not match expand_shape output size");
86 }
87
88 rewriter.replaceOp(op: sliceOp, newValues: expandOp.getSrc());
89 return success();
90 }
91};
92
93/// Fold collapse_shape which only removes static dimensions of size `1`
94/// into extract_slice.
95struct FoldUnPaddingCollapseIntoExtract
96 : public OpRewritePattern<tensor::CollapseShapeOp> {
97 using OpRewritePattern<tensor::CollapseShapeOp>::OpRewritePattern;
98
99 LogicalResult matchAndRewrite(tensor::CollapseShapeOp collapseShapeOp,
100 PatternRewriter &rewriter) const override {
101 auto extractSliceOp =
102 collapseShapeOp.getSrc().getDefiningOp<tensor::ExtractSliceOp>();
103 // Collapse cannot be folded away with multiple users of the extract slice
104 // and it is not necessarily beneficial to only convert the collapse into
105 // another extract slice.
106 if (!extractSliceOp || !extractSliceOp->hasOneUse())
107 return failure();
108
109 // Only fold away simple collapse where all removed dimensions have static
110 // size `1`.
111 SliceVerificationResult res = isRankReducedType(
112 originalType: collapseShapeOp.getSrcType(), candidateReducedType: collapseShapeOp.getResultType());
113 if (res != SliceVerificationResult::Success)
114 return rewriter.notifyMatchFailure(arg&: collapseShapeOp,
115 msg: "expected unpadding collapse");
116
117 Value unPaddedExtractSlice = tensor::ExtractSliceOp::create(
118 builder&: rewriter, location: extractSliceOp.getLoc(), resultType: collapseShapeOp.getResultType(),
119 source: extractSliceOp.getSource(), offsets: extractSliceOp.getMixedOffsets(),
120 sizes: extractSliceOp.getMixedSizes(), strides: extractSliceOp.getMixedStrides());
121 rewriter.replaceOp(op: collapseShapeOp, newValues: unPaddedExtractSlice);
122 return success();
123 }
124};
125
126/// Fold insert_slice(collapse_shape) ops that cancel itself out.
127template <typename OpTy>
128struct FoldInsertOfRankReducingInsert : public OpRewritePattern<OpTy> {
129 using OpRewritePattern<OpTy>::OpRewritePattern;
130
131 LogicalResult matchAndRewrite(OpTy insertSliceOp,
132 PatternRewriter &rewriter) const override {
133 auto collapseShapeOp =
134 insertSliceOp.getSource().template getDefiningOp<CollapseShapeOp>();
135 if (!collapseShapeOp)
136 return failure();
137 RankedTensorType srcType = collapseShapeOp.getSrcType();
138
139 // Only cases where the CollapseShapeOp can be folded away entirely are
140 // supported. Moreover, only simple cases where the resulting InsertSliceOp
141 // has no rank-reduction anymore are supported at the moment.
142 RankedTensorType nonReducingInsertType =
143 RankedTensorType::get(shape: insertSliceOp.getStaticSizes(),
144 elementType: insertSliceOp.getDestType().getElementType());
145 if (nonReducingInsertType != srcType)
146 return failure();
147
148 SmallVector<OpFoldResult> mixedOffsets = insertSliceOp.getMixedOffsets();
149 SmallVector<OpFoldResult> mixedSizes = insertSliceOp.getMixedSizes();
150 SmallVector<OpFoldResult> mixedStrides = insertSliceOp.getMixedStrides();
151 rewriter.replaceOpWithNewOp<OpTy>(insertSliceOp, collapseShapeOp.getSrc(),
152 insertSliceOp.getDest(), mixedOffsets,
153 mixedSizes, mixedStrides);
154 return success();
155 }
156};
157
158/// Fold expand_shape which only adds static dimensions of size `1`
159/// into insert_slice.
160template <typename OpTy>
161struct FoldPaddingExpandIntoInsert : public OpRewritePattern<OpTy> {
162 using OpRewritePattern<OpTy>::OpRewritePattern;
163
164 LogicalResult matchAndRewrite(OpTy insertSliceOp,
165 PatternRewriter &rewriter) const override {
166 auto expandShapeOp = insertSliceOp.getSource()
167 .template getDefiningOp<tensor::ExpandShapeOp>();
168 if (!expandShapeOp)
169 return failure();
170
171 // Only fold away simple expansion where all added dimensions have static
172 // size `1`.
173 SliceVerificationResult res = isRankReducedType(
174 expandShapeOp.getResultType(), expandShapeOp.getSrcType());
175 if (res != SliceVerificationResult::Success)
176 return rewriter.notifyMatchFailure(insertSliceOp,
177 "expected rank increasing expansion");
178
179 rewriter.modifyOpInPlace(insertSliceOp, [&]() {
180 insertSliceOp.getSourceMutable().assign(expandShapeOp.getSrc());
181 });
182 return success();
183 }
184};
185
186/// Pattern to bubble up a tensor.expand_shape op through a producer
187/// tensor.collapse_shape op that has non intersecting reassociations.
188struct BubbleUpExpandThroughParallelCollapse
189 : public OpRewritePattern<tensor::ExpandShapeOp> {
190 using OpRewritePattern<tensor::ExpandShapeOp>::OpRewritePattern;
191
192 LogicalResult matchAndRewrite(tensor::ExpandShapeOp expandOp,
193 PatternRewriter &rewriter) const override {
194 auto collapseOp =
195 expandOp.getSrc().getDefiningOp<tensor::CollapseShapeOp>();
196 if (!collapseOp)
197 return failure();
198 auto expandReInds = expandOp.getReassociationIndices();
199 auto collapseReInds = collapseOp.getReassociationIndices();
200
201 // Special case where the collapsed tensor to expand is a 0-D tensor,
202 // then the reassociation maps will be empty and not produce valid results.
203 if (expandReInds.size() == 0) {
204 return failure();
205 }
206
207 // Reshapes are parallel to each other (by construction the number of
208 // reassociations specified in the collapse and expand are the same), if at
209 // any position
210 // 1. either the reassociation indices are of the same size, or
211 // 2. either the reassociation in the collapse or the expand is of size 1.
212 ArrayRef<int64_t> staticSourceSize = collapseOp.getSrcType().getShape();
213 ArrayRef<int64_t> staticResultSize = expandOp.getStaticOutputShape();
214 for (auto [expandReassociation, collapseReassociation] :
215 llvm::zip_equal(t&: expandReInds, u&: collapseReInds)) {
216 if (collapseReassociation.size() == expandReassociation.size()) {
217 // Even if the reassociations are the same, the collapse/expand should
218 // result in the same dimensions. i.e 4x8x2 into 64 should be expanded
219 // into 4x8x2 again. In presense of dynamic dimensions one can only
220 // verify "equality" when there is only one dynamic dimension present,
221 // and all other static dimensions are equal.
222 ArrayRef<int64_t> collapsedStaticShapes = staticSourceSize.slice(
223 N: collapseReassociation.front(), M: collapseReassociation.size());
224 int64_t numCollapsedDynamic =
225 llvm::count_if(Range&: collapsedStaticShapes, P: ShapedType::isDynamic);
226 ArrayRef<int64_t> expandedStaticShapes = staticResultSize.slice(
227 N: expandReassociation.front(), M: expandReassociation.size());
228 int64_t numExpandedDynamic =
229 llvm::count_if(Range&: expandedStaticShapes, P: ShapedType::isDynamic);
230 if (numCollapsedDynamic > 1 || numExpandedDynamic > 1 ||
231 collapsedStaticShapes != expandedStaticShapes) {
232 return failure();
233 }
234 continue;
235 }
236 // If the reassociations are not same, one or the other needs to be of
237 // size one.
238 if (collapseReassociation.size() != 1 && expandReassociation.size() != 1)
239 return failure();
240 }
241
242 // Compute new reassociation indices and expanded/collaped shapes.
243 SmallVector<ReassociationIndices> newExpandReInds, newCollapseReInds;
244 Location loc = expandOp->getLoc();
245 SmallVector<OpFoldResult> sourceSizes =
246 tensor::getMixedSizes(builder&: rewriter, loc, value: collapseOp.getSrc());
247 SmallVector<OpFoldResult> resultSizes = expandOp.getMixedOutputShape();
248 SmallVector<OpFoldResult> newExpandSizes;
249
250 int64_t newExpandIndex = 0, newCollapseIndex = 0, sourceSizeIndex = 0,
251 resultSizeIndex = 0;
252
253 for (size_t idx = 0, idxEnd = collapseReInds.size(); idx < idxEnd; idx++) {
254 auto &collapseReassociation = collapseReInds[idx];
255 auto &expandReassociation = expandReInds[idx];
256
257 // Case 1. The reassociations are same in the collapse producer
258 // and expand consumer. In the swapped expand, each of the final
259 // dimensions are kept as is in the expand and the collapse. So,
260 // for every element in the `ReassocationIndices` vector add a new
261 // `ReassociationIndices` vector for the swapped expand and collapse
262 // (of size 1).
263 if (collapseReassociation.size() == expandReassociation.size()) {
264 for (size_t i = 0; i < collapseReassociation.size(); ++i) {
265 newCollapseReInds.push_back(Elt: {newCollapseIndex++});
266 newExpandReInds.push_back(Elt: {newExpandIndex++});
267 newExpandSizes.push_back(Elt: resultSizes[resultSizeIndex++]);
268 sourceSizeIndex++;
269 }
270 continue;
271 }
272
273 // Case 2. The `ReassociationIndices` in the collapse is of size > 1 (and
274 // in the expand is of size == 1). In this case, the original dimensions
275 // are preserved on expansion and collapsed subsequently.
276 if (collapseReassociation.size() != 1) {
277 ReassociationIndices newCollapseReassociation;
278 for (size_t i = 0; i < collapseReassociation.size(); ++i) {
279 newCollapseReassociation.push_back(Elt: newCollapseIndex++);
280 newExpandReInds.push_back(Elt: {newExpandIndex++});
281 newExpandSizes.push_back(Elt: sourceSizes[sourceSizeIndex++]);
282 }
283 resultSizeIndex++;
284 newCollapseReInds.push_back(Elt: newCollapseReassociation);
285 continue;
286 }
287
288 // Case 3. The `ReassociationIndices` in the expand is of size > 1 (and
289 // in the collapse is of size == 1). In this case, the expansion happens
290 // first and the expanded dimensions are preserved on collapse.
291 ReassociationIndices newExpandReassociation;
292 for (size_t i = 0; i < expandReassociation.size(); ++i) {
293 newExpandReassociation.push_back(Elt: newExpandIndex++);
294 newCollapseReInds.push_back(Elt: {newCollapseIndex++});
295 newExpandSizes.push_back(Elt: resultSizes[resultSizeIndex++]);
296 }
297 newExpandReInds.push_back(Elt: newExpandReassociation);
298 sourceSizeIndex++;
299 }
300
301 // Swap reshape order.
302 SmallVector<Value> dynamicSizes;
303 SmallVector<int64_t> staticSizes;
304 dispatchIndexOpFoldResults(ofrs: newExpandSizes, dynamicVec&: dynamicSizes, staticVec&: staticSizes);
305 auto expandResultType = expandOp.getResultType().clone(shape: staticSizes);
306 Value newCollapseSrc = collapseOp.getSrc();
307 // If the number of reassociation indices in the new `expand_shape` op
308 // matches the number of dimensions of the result, then the expand_shape
309 // is a no-op.
310 if (newExpandReInds.size() != newExpandSizes.size()) {
311 newCollapseSrc = tensor::ExpandShapeOp::create(
312 builder&: rewriter, location: loc, resultType: expandResultType, src: newCollapseSrc, reassociation: newExpandReInds,
313 outputShape: newExpandSizes);
314 }
315
316 // If the number of reassociation indices in the new `collapse_shape` op
317 // matches the number of dimensions of the source, then the collapse_shape
318 // is a no-op.
319 Value replacement = newCollapseSrc;
320 if (newCollapseReInds.size() != newExpandSizes.size()) {
321 replacement = tensor::CollapseShapeOp::create(
322 builder&: rewriter, location: loc, src: newCollapseSrc, reassociation: newCollapseReInds);
323 }
324 rewriter.replaceOp(op: expandOp, newValues: replacement);
325 return success();
326 }
327};
328
329/// Converts `tensor.extract_slice(tensor.expand_shape)` to
330/// `tensor.expand_shape(tensor.extract_slice)`.
331///
332/// For this transformation to be possible, the slice must be fully contiguous
333/// within each reassociation group of the expand_shape. A slice is defined as
334/// fully contiguous within a reassociation group if after flattening the
335/// reassociation group to a single 1D range, then the slice taken out of the
336/// group could be defined as a single contiguous subrange within that range.
337///
338/// Rank reducing slices are not supported.
339///
340/// Example:
341/// The transformation is possible because each reassociation group has a
342/// contiguous slice (i.e., [2x4->2x4], [2x8->1x5], [4x2x4->1x1x4]).
343/// ```
344/// BEFORE:
345/// %reshape = tensor.expand_shape %in [[0, 1], [2, 3], [4, 5, 6]]
346/// tensor<8x16x32xf32> to tensor<2x4x2x8x4x2x4xf32>
347/// %slice = tensor.extract_slice %reshape ...
348/// tensor<2x4x2x8x4x2x4xf32> to tensor<2x4x1x5x1x1x4xf32>
349///
350/// AFTER:
351/// %slice = tensor.extract_slice %in ...
352/// tensor<8x16x32xf32> to tensor<8x5x4xf32>
353/// %reshape = tensor.expand_shape %slice [[0, 1], [2, 3], [4, 5, 6]]
354/// tensor<8x5x4xf32> to tensor<2x4x1x5x1x1x4xf32>
355/// ```
356///
357/// Note - this pattern could be extended to be a swap pattern between
358/// `tensor.expand_shape` and `tensor.extract_slice`, but is currently
359/// implemented only as a bubble up pattern for `tensor.extract_slice`.
360struct BubbleUpExtractSliceThroughExpandShape
361 : public OpRewritePattern<tensor::ExtractSliceOp> {
362 using OpRewritePattern<tensor::ExtractSliceOp>::OpRewritePattern;
363
364 LogicalResult matchAndRewrite(tensor::ExtractSliceOp sliceOp,
365 PatternRewriter &rewriter) const override {
366 auto expandShapeOp =
367 sliceOp.getSource().getDefiningOp<tensor::ExpandShapeOp>();
368 if (!expandShapeOp) {
369 return rewriter.notifyMatchFailure(
370 arg&: sliceOp, msg: "tensor.extract_slice source not produced by expand_shape");
371 }
372 SmallVector<ReassociationIndices> reassociation =
373 expandShapeOp.getReassociationIndices();
374
375 SmallVector<OpFoldResult> offsets, sizes, strides;
376 if (failed(Result: getCollapsedExtractSliceInfo(b&: rewriter, sliceOp, reassociation,
377 collapsedOffsets&: offsets, collapsedSizes&: sizes, collapsedStrides&: strides)))
378 return failure();
379
380 // The shape of the result can be obtained from the sizes passed in.
381 SmallVector<OpFoldResult> expandedSizes = sliceOp.getMixedSizes();
382 RankedTensorType resultType = sliceOp.getResultType();
383
384 // Create a new ExtractSliceOp and ExpandShapeOp.
385 Location loc = sliceOp.getLoc();
386 Value newSliceOp = tensor::ExtractSliceOp::create(
387 builder&: rewriter, location: loc, source: expandShapeOp.getSrc(), offsets, sizes, strides);
388 rewriter.replaceOpWithNewOp<tensor::ExpandShapeOp>(
389 op: sliceOp, args&: resultType, args&: newSliceOp,
390 args: expandShapeOp.getReassociationIndices(), args&: expandedSizes);
391 return success();
392 }
393};
394
395/// Converts `tensor.extract_slice(tensor.collapse_shape)` to
396/// `tensor.collapse_shape(tensor.extract_slice)`.
397///
398/// For this transformation to be possible - after bubbling up, the extraction
399/// of the contiguous slice must be representable as a single slice obtained via
400/// tensor.extract_slice within each reassociation group of the src.
401///
402/// In case the size and offset extracted are static then this is possible if
403/// the following conditions are met within each reassociation group:
404/// Let T be a tensor of shape [A0, A1, ..., An] (these are the sizes of the
405/// dimensions in the reassociation group), and let S = [S0, S1, ..., Sn] be the
406/// shape of a desired slice. A slice of shape S can be extracted as a
407/// contiguous span of elements if and only if there exists an index k in {0, 1,
408/// ..., n} such that:
409/// S_i = 1 for all i < k (that is, all leading dimensions are singleton),
410/// 1 <= S_k <= A_k (that is, non trivial slicing occurs along exactly
411/// one dimension),
412/// S_i = A_i for all i > k (that is, all trailing dimensions are preserved
413/// in full).
414/// In other words, the slice shape S must be of the form:
415/// [ 1, 1, ..., 1, Sk, Ak + 1, Ak + 2, ...,An ]
416///
417/// In case the size and/or offset extracted are dynamic then this is possible
418/// only if there is single dimension in the reassociation group that has a size
419/// not equal to 1.
420/// In other words, the tensor shape must be of the form:
421/// [ 1, 1, ..., 1, A, 1, ...,1 ]
422/// Note - it might be possible to enable this pattern for more cases when the
423/// size/offset are dynamic via performing an analysis of the possible values
424/// that could be given to the size/offset.
425///
426/// Example:
427/// The transformation is possible because each reassociation group can be
428/// represented as a contiguous slice (i.e., [8x16->2x16], [1x7->1x?],
429/// [20->10]).
430/// ```
431/// BEFORE:
432/// %collapse = tensor.collapse_shape %src [[0, 1], [2, 3], [4]] ...
433/// tensor<8x16x1x7x20f32> to tensor<128x7x20xf32>
434/// %slice = tensor.extract_slice %slice [0, 0, 0][32, %size, 10][1, 1, 1]
435/// tensor<128x7x20xf32> to tensor<32x?x10xf32>
436///
437/// AFTER:
438/// %slice = tensor.extract_slice %src [0, 0, 0, 0, 0][2, 16, 1, %size, 10]
439// [1, 1, 1, 1, 1] : tensor<8x16x1x7x20f32> to tensor<2x16x1x?x10xf32>
440/// %collapse = tensor.collapse_shape %slice [[0, 1], [2, 3], [4]] ...
441/// tensor<2x16x1x?x10xf32> to tensor<32x?x10xf32>
442/// ```
443///
444/// Negative example:
445/// The transformation is not possible because we cannot use a single slice to
446/// represent the reassociation group [2x3x10->???]. If we would want the
447/// collapse to be after the extraction, we would need to extract multiple
448/// slices and concat them together.
449/// ```
450/// %collapse = tensor.collapse_shape %src [[0, 1, 2]] : tensor<2x3x10xf32> into
451/// tensor<60xf32> %extract = tensor.extract_slice %collapse[0][15][1] :
452/// tensor<60xf32> to tensor<15xf32>
453/// ```
454/// If we would want the collapse to be after the extraction, a possible
455/// alternate transformation could be to extract multiple slices and concat them
456/// together:
457/// ```
458/// %extract_1 = tensor.extract_slice %src[0, 0, 0][1, 1, 10] :
459/// tensor<2x3x10xf32> to tensor <1x1x10xf32>
460/// %extract_2 = tensor.extract_slice %src[0, 1, 0][1, 1, 5] :
461/// tensor<2x3x10xf32> to tensor <1x1x5xf32>
462/// %concat = tosa.concat %extract_1, %extract_2 {axis = 0 : i32} :
463/// (<1x1x10xf32>, <1x1x5xf32>) -> <1x1x15xf32>
464/// %collapse = tensor.collapse_shape %concat [[0, 1, 2]] : tensor<1x1x15xf32>
465/// to tensor<15xf32>
466/// ```
467/// But this is not the intended purpose of the transformation.
468struct BubbleUpExtractSliceThroughCollapseShape
469 : public OpRewritePattern<tensor::ExtractSliceOp> {
470 using OpRewritePattern<tensor::ExtractSliceOp>::OpRewritePattern;
471
472 LogicalResult matchAndRewrite(tensor::ExtractSliceOp sliceOp,
473 PatternRewriter &rewriter) const override {
474 auto collapseShapeOp =
475 sliceOp.getSource().getDefiningOp<tensor::CollapseShapeOp>();
476 if (!collapseShapeOp) {
477 return rewriter.notifyMatchFailure(
478 arg&: sliceOp,
479 msg: "tensor.extract_slice source not produced by tensor.collapse_shape");
480 }
481
482 SmallVector<OpFoldResult> offsets, sizes, strides;
483 if (failed(Result: getExpandedExtractSliceInfo(
484 b&: rewriter, sliceOp, reassociation: collapseShapeOp.getReassociationIndices(),
485 expandedValue: collapseShapeOp.getSrc(), expandedOffsets&: offsets, expandedSizes&: sizes, expandedStrides&: strides)))
486 return failure();
487
488 Value newSliceOp = tensor::ExtractSliceOp::create(
489 builder&: rewriter, location: collapseShapeOp->getLoc(), source: collapseShapeOp.getSrc(), offsets,
490 sizes, strides);
491 rewriter.replaceOpWithNewOp<tensor::CollapseShapeOp>(
492 op: sliceOp, args: sliceOp.getResultType(), args&: newSliceOp,
493 args: collapseShapeOp.getReassociationIndices());
494
495 return success();
496 }
497};
498
499} // namespace
500
501LogicalResult mlir::tensor::getCollapsedExtractSliceInfo(
502 OpBuilder &b, tensor::ExtractSliceOp sliceOp,
503 ArrayRef<ReassociationIndices> reassociation,
504 SmallVectorImpl<OpFoldResult> &collapsedOffsets,
505 SmallVectorImpl<OpFoldResult> &collapsedSizes,
506 SmallVectorImpl<OpFoldResult> &collapsedStrides) {
507 if (!sliceOp.hasUnitStride()) {
508 return failure();
509 }
510
511 SmallVector<OpFoldResult> offsets = sliceOp.getMixedOffsets();
512 SmallVector<OpFoldResult> sizes = sliceOp.getMixedSizes();
513
514 if (static_cast<size_t>(sliceOp.getResultType().getRank()) != sizes.size()) {
515 return failure();
516 }
517
518 auto isZeroOffsetAndFullSize = [&](OpFoldResult offset,
519 OpFoldResult sliceSize, int64_t inputDim) {
520 if (!isZeroInteger(v: offset))
521 return false;
522 ValueBoundsConstraintSet::Variable inputSize(sliceOp.getSource(), inputDim);
523 FailureOr<bool> maybeEqual =
524 ValueBoundsConstraintSet::areEqual(var1: sliceSize, var2: inputSize);
525 return llvm::succeeded(Result: maybeEqual) && maybeEqual.value();
526 };
527
528 // Check that the slice is contiguous within each reassociation group.
529 // The slice is contiguous only if after the first dimension where a non
530 // unit slice is taken, the slice size on all subsequent dimensions of the
531 // group is equal to the entire size of the dimension.
532 // Examples of contiguous slices:
533 // full sizes: [8, 8, 10] slice offsets: [0, 0, 0] slice sizes: [1, 1, 10]
534 // full sizes: [5, 10] slice offsets: [3, 0] slice sizes: [2, 10]
535 // Examples of non contiguous slices:
536 // full sizes: [8, 8, 10] slice offsets: [0, 0, 0] slice sizes: [1, 2, 5]
537 // full sizes: [5, 10] slice offsets: [0, 4] slice sizes: [2, 5]
538 for (const ReassociationIndices &indices : reassociation) {
539 int64_t i = 0;
540 int64_t e = indices.size();
541 // Find the first expanded dim after the first dim with non-unit extracted
542 // size.
543 for (; i < e; ++i) {
544 if (!isOneInteger(v: sizes[indices[i]])) {
545 // +1 to skip the first non-unit size dim.
546 i++;
547 break;
548 }
549 }
550
551 // Verify that all subsequent dimensions extract the full size of the
552 // source tensor.
553 for (; i < e; ++i) {
554 int64_t expandedDim = indices[i];
555 if (!isZeroOffsetAndFullSize(offsets[expandedDim], sizes[expandedDim],
556 expandedDim)) {
557 return failure();
558 }
559 }
560 }
561
562 // The tensor.extract_slice before applying the pattern works on the result
563 // of the tensor.expand_shape, so variables (i.e. inputs for ExtractSliceOp)
564 // referring to the state before applying the pattern are named with the
565 // prefix "expanded", and ones referring to the state after applying the
566 // pattern are named with the prefix "collapsed".
567 Location loc = sliceOp.getLoc();
568 SmallVector<OpFoldResult> expandedOffsets = sliceOp.getMixedOffsets();
569 SmallVector<OpFoldResult> expandedSizes = sliceOp.getMixedSizes();
570 SmallVector<OpFoldResult> expandedShape =
571 getMixedSizes(builder&: b, loc, value: sliceOp.getSource());
572
573 // Helper variables and function for accumulating the size values.
574 AffineExpr d0, d1;
575 bindDims(ctx: b.getContext(), exprs&: d0, exprs&: d1);
576 // Multiply two integers.
577 auto mul = [&](OpFoldResult v1, OpFoldResult v2) {
578 auto mulMap = AffineMap::get(dimCount: 2, symbolCount: 0, result: {d0 * d1});
579 return affine::makeComposedFoldedAffineApply(b, loc, map: mulMap, operands: {v1, v2});
580 };
581
582 // Compute new offsets, sizes, and strides for tensor.extract_slice.
583 // The new tensor.extract_slice will work on a tensor that has has a rank of
584 // ReassociationIndices.size(). In the loop a single offset, size, and
585 // stride value is computed per reassociation group.
586 for (const ReassociationIndices &indices : reassociation) {
587 // collapsedSize will hold the size of the single dim that represents the
588 // reassociation group in the non expanded tensor.
589 OpFoldResult collapsedSize = b.getIndexAttr(value: 1);
590 // The reassocGroupSizes and reassocGroupOffsets are used to create an
591 // affine.linearize_index op to linearize the single offset value required
592 // for this reassociation group.
593 SmallVector<OpFoldResult> reassocGroupSizes, reassocGroupOffsets;
594
595 for (long expandedDim : indices) {
596 // reassocGroupSizes and reassocGroupOffsets can be obtained directly
597 // from the expanded state, but the collapsed size requires calculation
598 // as it did not previously exist.
599 reassocGroupSizes.push_back(Elt: expandedShape[expandedDim]);
600 reassocGroupOffsets.push_back(Elt: expandedOffsets[expandedDim]);
601 collapsedSize = mul(collapsedSize, expandedSizes[expandedDim]);
602 }
603
604 SmallVector<Value> offsetVals =
605 llvm::map_to_vector(C&: reassocGroupOffsets, F: [&](OpFoldResult ofr) {
606 return getValueOrCreateConstantIndexOp(b, loc, ofr);
607 });
608 OpFoldResult collapsedOffset = affine::AffineLinearizeIndexOp::create(
609 builder&: b, location: loc, multi_index: offsetVals, basis: reassocGroupSizes,
610 /*disjoint=*/true)
611 .getResult();
612 collapsedOffsets.push_back(Elt: collapsedOffset);
613 collapsedSizes.push_back(Elt: collapsedSize);
614
615 // Only unit stride is supported.
616 collapsedStrides.push_back(Elt: b.getIndexAttr(value: 1));
617 }
618 return success();
619}
620
621// Checks if the `ofr` is a multiple of the `factor`.
622// Handles both static integer and dynamic values
623// where the value is the result of an affine.apply.
624static bool isMultipleOf(OpFoldResult ofr, int64_t factor) {
625 std::optional<int64_t> staticValue = getConstantIntValue(ofr);
626 if (staticValue.has_value())
627 return staticValue.value() % factor == 0;
628
629 Value value = dyn_cast<Value>(Val&: ofr);
630 if (!value)
631 return false;
632 auto applyOp = value.getDefiningOp<affine::AffineApplyOp>();
633 if (!applyOp)
634 return false;
635 AffineMap map = applyOp.getAffineMap();
636 SmallVector<Value> operands(applyOp.getOperands());
637 affine::fullyComposeAffineMapAndOperands(map: &map, operands: &operands);
638 map = simplifyAffineMap(map);
639 if (map.getNumResults() != 1)
640 return false;
641 return map.getResult(idx: 0).isMultipleOf(factor);
642}
643
644/// Given a `collapsedOffset` and `collapsedSize`, this function
645/// validates that the slice is representable as a contiguous slice
646/// in the `expandedShape` and computes the corresponding expanded sizes.
647/// Returns failure if the slice cannot be guaranteed to be contiguous.
648/// On success, populates `groupSizes` with the expanded sizes for each
649/// dimension in the reassociation group.
650static LogicalResult computeExpandedSliceInfoForReassocGroup(
651 OpBuilder &b, OpFoldResult collapsedSize, OpFoldResult collapsedOffset,
652 const ReassociationIndices &reassocIndices, ArrayRef<int64_t> expandedShape,
653 SmallVectorImpl<OpFoldResult> &groupSizes) {
654 assert(groupSizes.empty() && "Group sizes must be empty");
655 // The first case is when there's only one non-unit dimension in the
656 // reassociation group.
657 // When there's only one non-unit dimension, the slice is trivially
658 // contiguous - offset and size go directly on that dimension.
659 // This works for both dynamic size and dynamic offset.
660 int nonUnitSizeCount = llvm::count_if(
661 Range: reassocIndices, P: [&expandedShape](int64_t expandedShapeIdx) {
662 return expandedShape[expandedShapeIdx] != 1;
663 });
664 if (nonUnitSizeCount == 1) {
665 for (int64_t expandedShapeIdx : reassocIndices) {
666 if (expandedShape[expandedShapeIdx] != 1)
667 groupSizes.push_back(Elt: collapsedSize);
668 else
669 groupSizes.push_back(Elt: b.getIndexAttr(value: 1));
670 }
671 return success();
672 }
673
674 // Having dynamic extracted size requires additional complex
675 // analysis to guarantee contiguous slicing.
676 if (isa<Value>(Val: collapsedSize))
677 return failure();
678
679 std::optional<int64_t> staticSize = getConstantIntValue(ofr: collapsedSize);
680 assert(staticSize.has_value() && "Expected static size");
681
682 // The extracted size is only one element, offset may be static
683 // or dynamic, It's a trivial case where we always can guarantee
684 // contiguous slicing.
685 if (staticSize.value() == 1) {
686 for (size_t i = 0; i < reassocIndices.size(); ++i)
687 groupSizes.push_back(Elt: b.getIndexAttr(value: 1));
688
689 return success();
690 }
691
692 // Size is static and greater than 1, offset may be static or dynamic.
693 // Use traversal to find dimension k where slicing occurs.
694 // Verify that the slice can be represented as a contiguous slice of the
695 // src of the collapse_shape.
696 // Checking this is done on order of most internal dimensions first,
697 // so traversal is done in reverse order of the reassociation group.
698 // If the expected slice shape is [1, 1, ..., 1, Sk, Ak + 1, Ak + 2,
699 // ...,An] then we first find the size and offset for n...k+1 then for k
700 // and then for k-1...0.
701
702 // currentCollapsedsize is initialized with the original collapsed size
703 // and divided by the expanded shape size in each dimension as we go along
704 // the reassociation group. In essence we are spreading the original
705 // collapsed size over the various expanded slice dimensions.
706 // currentOffsetDivisor is initialized with 1 and multiplied by the expanded
707 // shape size in each dimension as we go along the reassociation group.
708 // These variables are used both to check the validity of the slice and to
709 // compute the expanded sizes and offsets.
710 assert(staticSize.value() > 1 && "Expected size to be greater than 1");
711 int64_t currentCollapsedsize = staticSize.value();
712 int64_t currentOffsetDivisor = 1;
713
714 ReassociationIndices reversedReassocIndices(reassocIndices.rbegin(),
715 reassocIndices.rend());
716 int64_t idx = 0;
717 int64_t reassocGroupSize = reassocIndices.size();
718
719 // First handle the trailing dimensions where the slice size should be
720 // equal to the tensor shape and the offset should be 0 (n...k+1).
721 for (; idx < reassocGroupSize; ++idx) {
722 int64_t expandedShapeSize = expandedShape[reversedReassocIndices[idx]];
723 if (expandedShapeSize == ShapedType::kDynamic)
724 return failure();
725
726 if (currentCollapsedsize < expandedShapeSize)
727 break;
728
729 // Check size divisibility.
730 if ((currentCollapsedsize % expandedShapeSize) != 0)
731 return failure();
732
733 // Check dynamic/static offset divisibility.
734 currentOffsetDivisor *= expandedShapeSize;
735 if (!isMultipleOf(ofr: collapsedOffset, factor: currentOffsetDivisor))
736 return failure();
737
738 // Trailing dims get full shape and zero offset.
739 groupSizes.push_back(Elt: b.getIndexAttr(value: expandedShapeSize));
740 currentCollapsedsize /= expandedShapeSize;
741 }
742
743 // Now handle the first dim where slicing occurs on (k).
744 if (idx < reassocGroupSize) {
745 int64_t expandedShapeSize = expandedShape[reversedReassocIndices[idx]];
746 std::optional<int64_t> staticOffset = getConstantIntValue(ofr: collapsedOffset);
747
748 if (staticOffset.has_value()) {
749 // Static offset: check that offset + size doesn't exceed dimension.
750 int64_t offsetInDim =
751 (staticOffset.value() / currentOffsetDivisor) % expandedShapeSize;
752 if ((currentCollapsedsize + offsetInDim) > expandedShapeSize)
753 return failure();
754 } else {
755 // If the offset is dynamic, We could have more restricted conditions
756 // to guarantee contiguous slicing.
757 // For example, we could require that the dimension is divisible by the
758 // slice size and the offset is a multiple of the slice size.
759 // For more complex cases, we could use valueBoundsInterface
760 // to check the validity of the range.
761 if ((expandedShapeSize % currentCollapsedsize) != 0)
762 return failure();
763 if (!isMultipleOf(ofr: collapsedOffset, factor: staticSize.value()))
764 return failure();
765 }
766 // Slicing dimension gets the remaining collapsed size.
767 groupSizes.push_back(Elt: b.getIndexAttr(value: currentCollapsedsize));
768 }
769
770 // Now handle the leading dimensions where the slice size is equal to 1
771 // (k-1...0).
772 // The size for these dimensions must be 1 because of how we constructed
773 // the slice size of the expanded shape. We spread the original collapsed
774 // size over the expanded shape sizes until we reached dimension k where
775 // the remaining size was smaller than the expanded shape size, and spread
776 // the remaining size on it. So, now we are left with only 1s.
777 for (idx++; idx < reassocGroupSize; ++idx)
778 groupSizes.push_back(Elt: b.getIndexAttr(value: 1));
779
780 // Sizes were built in reverse order, so reverse them.
781 groupSizes = llvm::to_vector(Range: llvm::reverse(C&: groupSizes));
782 return success();
783}
784
785LogicalResult mlir::tensor::getExpandedExtractSliceInfo(
786 OpBuilder &b, tensor::ExtractSliceOp sliceOp,
787 ArrayRef<ReassociationIndices> reassociation, Value expandedValue,
788 SmallVectorImpl<OpFoldResult> &expandedOffsets,
789 SmallVectorImpl<OpFoldResult> &expandedSizes,
790 SmallVectorImpl<OpFoldResult> &expandedStrides) {
791 if (!sliceOp.hasUnitStride()) {
792 return failure();
793 }
794
795 // The tensor.extract_slice before applying the pattern works on the result
796 // of the tensor.collapse_shape, so variables (i.e. inputs for
797 // ExtractSliceOp) referring to the state before applying the pattern are
798 // named with the prefix "collapsed", and ones referring to the state after
799 // applying the pattern are named with the prefix "expanded".
800 SmallVector<OpFoldResult> collapsedOffsets = sliceOp.getMixedOffsets();
801 SmallVector<OpFoldResult> collapsedSizes = sliceOp.getMixedSizes();
802 if (static_cast<size_t>(sliceOp.getResultType().getRank()) !=
803 collapsedSizes.size()) {
804 return failure();
805 }
806
807 // Compute new offsets, sizes, and strides for tensor.extract_slice.
808 // The new tensor.extract_slice will work on a tensor that has has a rank
809 // equal to the rank of the src of the collapse_shape. In each iteration of
810 // the loop, the offsets and sizes will be computed per reassociation group.
811 ArrayRef<int64_t> expandedShape =
812 cast<RankedTensorType>(Val: expandedValue.getType()).getShape();
813 SmallVector<SmallVector<OpFoldResult>> groupResults;
814 for (auto [collapsedSize, collapsedOffset, reassocIndices] :
815 llvm::zip_equal(t&: collapsedSizes, u&: collapsedOffsets, args&: reassociation)) {
816
817 SmallVector<OpFoldResult> groupSizes;
818 LogicalResult result = computeExpandedSliceInfoForReassocGroup(
819 b, collapsedSize, collapsedOffset, reassocIndices, expandedShape,
820 groupSizes);
821 if (failed(Result: result))
822 return failure();
823 groupResults.emplace_back(Args&: groupSizes);
824 }
825
826 expandedStrides.resize(N: expandedShape.size(), NV: b.getIndexAttr(value: 1));
827 for (auto [groupIdx, reassocIndices] : llvm::enumerate(First&: reassociation)) {
828 auto &sizes = groupResults[groupIdx];
829 expandedSizes.append(RHS: sizes);
830
831 SmallVector<OpFoldResult> basis;
832 for (int64_t expandedShapeIdx : reassocIndices)
833 basis.push_back(Elt: tensor::getMixedSize(builder&: b, loc: sliceOp.getLoc(), value: expandedValue,
834 dim: expandedShapeIdx));
835
836 OpFoldResult collapsedOffset = collapsedOffsets[groupIdx];
837 Value offsetVal =
838 getValueOrCreateConstantIndexOp(b, loc: sliceOp.getLoc(), ofr: collapsedOffset);
839 auto delinearizeOp = affine::AffineDelinearizeIndexOp::create(
840 builder&: b, location: sliceOp.getLoc(), linear_index: offsetVal, basis, /*hasOuterBound=*/true);
841 for (OpResult result : delinearizeOp.getResults())
842 expandedOffsets.push_back(Elt: result);
843 }
844 return success();
845}
846
847void mlir::tensor::populateReassociativeReshapeFoldingPatterns(
848 RewritePatternSet &patterns) {
849 patterns.add<FoldExpandOfRankReducingExtract, FoldExtractSliceOfExpandShape,
850 FoldUnPaddingCollapseIntoExtract,
851 FoldInsertOfRankReducingInsert<tensor::InsertSliceOp>,
852 FoldInsertOfRankReducingInsert<tensor::ParallelInsertSliceOp>,
853 FoldPaddingExpandIntoInsert<tensor::InsertSliceOp>,
854 FoldPaddingExpandIntoInsert<tensor::ParallelInsertSliceOp>>(
855 arg: patterns.getContext());
856}
857
858void mlir::tensor::populateBubbleUpExpandShapePatterns(
859 RewritePatternSet &patterns) {
860 patterns.add<BubbleUpExpandThroughParallelCollapse>(arg: patterns.getContext());
861}
862
863void mlir::tensor::populateBubbleUpExtractSliceOpPatterns(
864 RewritePatternSet &patterns) {
865 patterns.add<BubbleUpExtractSliceThroughExpandShape,
866 BubbleUpExtractSliceThroughCollapseShape>(arg: patterns.getContext());
867}
868