1//===- FoldMemRefAliasOps.cpp - Fold memref alias ops ---------------------===//
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 transformation pass folds loading/storing from/to subview ops into
10// loading/storing from/to the original memref.
11//
12//===----------------------------------------------------------------------===//
13
14#include "mlir/Dialect/Affine/ViewLikeInterfaceUtils.h"
15#include "mlir/Dialect/Arith/Utils/Utils.h"
16#include "mlir/Dialect/MemRef/IR/MemRef.h"
17#include "mlir/Dialect/MemRef/IR/MemoryAccessOpInterfaces.h"
18#include "mlir/Dialect/MemRef/Transforms/Passes.h"
19#include "mlir/Dialect/MemRef/Transforms/Transforms.h"
20#include "mlir/Dialect/MemRef/Utils/MemRefUtils.h"
21#include "mlir/Dialect/Vector/IR/VectorOps.h"
22#include "mlir/IR/AffineExpr.h"
23#include "mlir/IR/AffineMap.h"
24#include "mlir/IR/PatternMatch.h"
25#include "mlir/Transforms/GreedyPatternRewriteDriver.h"
26#include "llvm/ADT/STLExtras.h"
27#include "llvm/ADT/SmallBitVector.h"
28#include "llvm/Support/Debug.h"
29#include <cstdint>
30
31#define DEBUG_TYPE "fold-memref-alias-ops"
32#define DBGS() (llvm::dbgs() << "[" DEBUG_TYPE "]: ")
33
34namespace mlir {
35namespace memref {
36#define GEN_PASS_DEF_FOLDMEMREFALIASOPSPASS
37#include "mlir/Dialect/MemRef/Transforms/Passes.h.inc"
38} // namespace memref
39} // namespace mlir
40
41using namespace mlir;
42
43//===----------------------------------------------------------------------===//
44// Utility functions
45//===----------------------------------------------------------------------===//
46
47/// Deterimine if the last N indices of `reassocitaion` are trivial - that is,
48/// check if they all contain exactly one dimension to collape/expand into.
49static bool
50hasTrivialReassociationSuffix(ArrayRef<ReassociationIndices> reassocs,
51 int64_t n) {
52 if (n <= 0)
53 return true;
54 if (n > static_cast<int64_t>(reassocs.size()))
55 return false;
56 return llvm::all_of(
57 Range: reassocs.take_back(N: n),
58 P: [&](const ReassociationIndices &indices) { return indices.size() == 1; });
59}
60
61static bool hasTrailingUnitStrides(memref::SubViewOp subview, int64_t n) {
62 if (n <= 0)
63 return true;
64 ArrayRef<int64_t> strides = subview.getStaticStrides();
65 if (n > static_cast<int64_t>(strides.size()))
66 return false;
67 return llvm::all_of(Range: strides.take_back(N: n), P: [](int64_t s) { return s == 1; });
68}
69
70//===----------------------------------------------------------------------===//
71// Patterns
72//===----------------------------------------------------------------------===//
73
74namespace {
75/// Folds subview(subview(x)) to a single subview(x).
76class SubViewOfSubViewFolder : public OpRewritePattern<memref::SubViewOp> {
77public:
78 using OpRewritePattern<memref::SubViewOp>::OpRewritePattern;
79
80 LogicalResult matchAndRewrite(memref::SubViewOp subView,
81 PatternRewriter &rewriter) const override {
82 auto srcSubView = subView.getSource().getDefiningOp<memref::SubViewOp>();
83 if (!srcSubView)
84 return failure();
85
86 SmallVector<OpFoldResult> newOffsets, newSizes, newStrides;
87 if (failed(Result: affine::mergeOffsetsSizesAndStrides(
88 builder&: rewriter, loc: subView.getLoc(), producer: srcSubView, consumer: subView,
89 droppedProducerDims: srcSubView.getDroppedDims(), combinedOffsets&: newOffsets, combinedSizes&: newSizes, combinedStrides&: newStrides)))
90 return failure();
91
92 // Replace original op.
93 rewriter.replaceOpWithNewOp<memref::SubViewOp>(
94 op: subView, args: subView.getType(), args: srcSubView.getSource(), args&: newOffsets,
95 args&: newSizes, args&: newStrides);
96 return success();
97 }
98};
99
100/// Merges subview operations with load/store like operations unless such a
101/// merger would cause the strides between dimensions accessed by that operaton
102/// to change.
103struct AccessOpOfSubViewOpFolder final
104 : OpInterfaceRewritePattern<memref::IndexedAccessOpInterface> {
105 using Base::Base;
106
107 LogicalResult matchAndRewrite(memref::IndexedAccessOpInterface op,
108 PatternRewriter &rewriter) const override;
109};
110
111/// Merge a memref.expand_shape operation with an operation that accesses a
112/// memref by index unless that operation accesss more than one dimension of
113/// memory and any dimension other than the outermost dimension accessed this
114/// way would be merged. This prevents issuses from arising with, say, a
115/// vector.load of a 4x2 vector having the two trailing dimensions of the access
116/// get merged.
117struct AccessOpOfExpandShapeOpFolder final
118 : OpInterfaceRewritePattern<memref::IndexedAccessOpInterface> {
119 using Base::Base;
120
121 LogicalResult matchAndRewrite(memref::IndexedAccessOpInterface op,
122 PatternRewriter &rewriter) const override;
123};
124
125/// Merges an operation that accesses a memref by index with a
126/// memref.collapse_shape, unless this would break apart a dimension other than
127/// the outermost one that an operation accesses. This prevents, for example,
128/// transforming a load of a 3x8 vector from a 6x8 memref into a load
129/// from a 3x4x2 memref (as this would require special handling and could lead
130/// to invalid IR if that higher-dimensional memref comes from a subview) but
131/// does permit turning a load of a length-8 vector from a 3x8 memref into a
132/// load from a 3x2x8 one.
133struct AccessOpOfCollapseShapeOpFolder final
134 : OpInterfaceRewritePattern<memref::IndexedAccessOpInterface> {
135 using Base::Base;
136
137 LogicalResult matchAndRewrite(memref::IndexedAccessOpInterface op,
138 PatternRewriter &rewriter) const override;
139};
140
141/// Merges memref.subview operations present on the source or destination
142/// operands of indexed memory copy operations (DMA operations) into those
143/// operations. This is perfromed unconditionally, since folding in a subview
144/// cannot change the starting position of the copy, which is what the
145/// memref/index pair represent in DMA operations.
146struct IndexedMemCopyOpOfSubViewOpFolder final
147 : OpInterfaceRewritePattern<memref::IndexedMemCopyOpInterface> {
148 using Base::Base;
149
150 LogicalResult matchAndRewrite(memref::IndexedMemCopyOpInterface op,
151 PatternRewriter &rewriter) const override;
152};
153
154/// Merges memref.expand_shape operations that are present on the source or
155/// destination of an indexed memory copy/DMA into the memref/index arguments of
156/// that DMA. As with subviews, this can be done unconditionally.
157struct IndexedMemCopyOpOfExpandShapeOpFolder final
158 : OpInterfaceRewritePattern<memref::IndexedMemCopyOpInterface> {
159 using Base::Base;
160
161 LogicalResult matchAndRewrite(memref::IndexedMemCopyOpInterface op,
162 PatternRewriter &rewriter) const override;
163};
164
165/// Merges memref.collapse_shape operations that are present on the source or
166/// destination of an indexed memory copy/DMA into the memref/index arguments of
167/// that DMA. As with subviews, this can be done unconditionally.
168struct IndexedMemCopyOpOfCollapseShapeOpFolder final
169 : OpInterfaceRewritePattern<memref::IndexedMemCopyOpInterface> {
170 using Base::Base;
171
172 LogicalResult matchAndRewrite(memref::IndexedMemCopyOpInterface op,
173 PatternRewriter &rewriter) const override;
174};
175
176/// Merges memref.subview ops on the base argument to vector transfer operations
177/// into the base and indices of that transfer if:
178/// - The subview has unit strides on transfer dimensions
179/// - All the transfer dimensions are in-bounds
180/// This will correctly update said permutation map to account for dropped
181/// dimensions in rank-reducing subviews.
182struct TransferOpOfSubViewOpFolder final
183 : OpInterfaceRewritePattern<VectorTransferOpInterface> {
184 using Base::Base;
185
186 LogicalResult matchAndRewrite(VectorTransferOpInterface op,
187 PatternRewriter &rewriter) const override;
188};
189
190/// Merges memref.expand_shape ops that create the base of a vector transfer
191/// operation into the base and indices of that transfer. Does not act when the
192/// a dimension is potentially out of bounds, if one of the transfer dimensions
193/// would need to be strided because of the collapse, or if it would merge two
194/// dimensions that are both transfer dimensions.
195/// TODO: become more sophisticated about length-1 dimensions that are the
196/// result of an expansion becoming broadcasts.
197struct TransferOpOfExpandShapeOpFolder final
198 : OpInterfaceRewritePattern<VectorTransferOpInterface> {
199 using Base::Base;
200
201 LogicalResult matchAndRewrite(VectorTransferOpInterface op,
202 PatternRewriter &rewriter) const override;
203};
204
205/// Merges memref.collapse_shape ops that create the base of a vector transfer
206/// operation into the base and indices of that transfer. Does not act when the
207/// permutation map is not trivial, a dimension could be performing out of
208/// bounds reads, or if it would break apart a transfer dimension.
209struct TransferOpOfCollapseShapeOpFolder final
210 : OpInterfaceRewritePattern<VectorTransferOpInterface> {
211 using Base::Base;
212
213 LogicalResult matchAndRewrite(VectorTransferOpInterface op,
214 PatternRewriter &rewriter) const override;
215};
216} // namespace
217
218LogicalResult
219AccessOpOfSubViewOpFolder::matchAndRewrite(memref::IndexedAccessOpInterface op,
220 PatternRewriter &rewriter) const {
221 TypedValue<MemRefType> accessedMemref = op.getAccessedMemref();
222 if (!accessedMemref)
223 return rewriter.notifyMatchFailure(arg&: op, msg: "not accessing a memref");
224
225 auto subview = accessedMemref.getDefiningOp<memref::SubViewOp>();
226 if (!subview)
227 return rewriter.notifyMatchFailure(arg&: op, msg: "not accessing a subview");
228
229 SmallVector<int64_t> accessedShape = op.getAccessedShape();
230 // Note the subtle difference between accessedShape = {1} and accessedShape =
231 // {} here. The former prevents us from folding in a subview that doesn't
232 // have a unit stride on the final dimension, while the latter does not (since
233 // it indexes scalar accesses).
234 int64_t accessedDims = accessedShape.size();
235 if (!hasTrailingUnitStrides(subview, n: accessedDims))
236 return rewriter.notifyMatchFailure(
237 arg&: op, msg: "non-unit stride on accessed dimensions");
238
239 llvm::SmallBitVector droppedDims = subview.getDroppedDims();
240 int64_t sourceRank = subview.getSourceType().getRank();
241
242 // Ignore outermost access dimension - we only care about dropped dimensions
243 // between the accessed op's results, as those could break the accessing op's
244 // semantics.
245 int64_t secondAccessedDim = sourceRank - (accessedDims - 1);
246 if (secondAccessedDim < sourceRank) {
247 for (int64_t d : llvm::seq(Begin: secondAccessedDim, End: sourceRank)) {
248 if (droppedDims.test(Idx: d))
249 return rewriter.notifyMatchFailure(
250 arg&: op, msg: "reintroducing dropped dimension " + Twine(d) +
251 " would break access op semantics");
252 }
253 }
254
255 SmallVector<Value> sourceIndices;
256 affine::resolveIndicesIntoOpWithOffsetsAndStrides(
257 rewriter, loc: op.getLoc(), mixedSourceOffsets: subview.getMixedOffsets(),
258 mixedSourceStrides: subview.getMixedStrides(), rankReducedDims: droppedDims, consumerIndices: op.getIndices(), resolvedIndices&: sourceIndices);
259
260 std::optional<SmallVector<Value>> newValues =
261 op.updateMemrefAndIndices(rewriter, newMemref: subview.getSource(), newIndices: sourceIndices);
262 if (newValues)
263 rewriter.replaceOp(op, newValues: *newValues);
264 return success();
265}
266
267LogicalResult AccessOpOfExpandShapeOpFolder::matchAndRewrite(
268 memref::IndexedAccessOpInterface op, PatternRewriter &rewriter) const {
269 TypedValue<MemRefType> accessedMemref = op.getAccessedMemref();
270 if (!accessedMemref)
271 return rewriter.notifyMatchFailure(arg&: op, msg: "not accessing a memref");
272
273 auto expand = accessedMemref.getDefiningOp<memref::ExpandShapeOp>();
274 if (!expand)
275 return rewriter.notifyMatchFailure(arg&: op, msg: "not accessing an expand_shape");
276
277 SmallVector<int64_t> rawAccessedShape = op.getAccessedShape();
278 ArrayRef<int64_t> accessedShape = rawAccessedShape;
279 if (expand.getSrcType().getRank() <
280 static_cast<int64_t>(accessedShape.size()))
281 return rewriter.notifyMatchFailure(
282 arg&: op, msg: "expand_shape source rank is too small for the accessed shape");
283
284 // Cut off the leading dimension, since we don't care about modifying its
285 // strides.
286 if (!accessedShape.empty())
287 accessedShape = accessedShape.drop_front();
288
289 SmallVector<ReassociationIndices, 4> reassocs =
290 expand.getReassociationIndices();
291 if (!hasTrivialReassociationSuffix(reassocs, n: accessedShape.size()))
292 return rewriter.notifyMatchFailure(
293 arg&: op,
294 msg: "expand_shape folding would merge semantically important dimensions");
295
296 SmallVector<Value> sourceIndices;
297 memref::resolveSourceIndicesExpandShape(loc: op.getLoc(), rewriter, expandShapeOp: expand,
298 indices: op.getIndices(), sourceIndices,
299 startsInbounds: op.hasInboundsIndices());
300
301 std::optional<SmallVector<Value>> newValues = op.updateMemrefAndIndices(
302 rewriter, newMemref: expand.getViewSource(), newIndices: sourceIndices);
303 if (newValues)
304 rewriter.replaceOp(op, newValues: *newValues);
305 return success();
306}
307
308LogicalResult AccessOpOfCollapseShapeOpFolder::matchAndRewrite(
309 memref::IndexedAccessOpInterface op, PatternRewriter &rewriter) const {
310 TypedValue<MemRefType> accessedMemref = op.getAccessedMemref();
311 if (!accessedMemref)
312 return rewriter.notifyMatchFailure(arg&: op, msg: "not accessing a memref");
313
314 auto collapse = accessedMemref.getDefiningOp<memref::CollapseShapeOp>();
315 if (!collapse)
316 return rewriter.notifyMatchFailure(arg&: op, msg: "not accessing a collapse_shape");
317
318 SmallVector<int64_t> rawAccessedShape = op.getAccessedShape();
319 ArrayRef<int64_t> accessedShape = rawAccessedShape;
320 if (collapse.getSrcType().getRank() <
321 static_cast<int64_t>(accessedShape.size()))
322 return rewriter.notifyMatchFailure(
323 arg&: op, msg: "collapse_shape source rank is too small for the accessed shape");
324
325 // Cut off the leading dimension, since we don't care about its strides being
326 // modified and we know that the dimensions within its reassociation group, if
327 // it's non-trivial, must be contiguous.
328 if (!accessedShape.empty())
329 accessedShape = accessedShape.drop_front();
330
331 SmallVector<ReassociationIndices, 4> reassocs =
332 collapse.getReassociationIndices();
333 if (!hasTrivialReassociationSuffix(reassocs, n: accessedShape.size()))
334 return rewriter.notifyMatchFailure(arg&: op, msg: "collapse_shape folding would merge "
335 "semantically important dimensions");
336
337 SmallVector<Value> sourceIndices;
338 memref::resolveSourceIndicesCollapseShape(loc: op.getLoc(), rewriter, collapseShapeOp: collapse,
339 indices: op.getIndices(), sourceIndices,
340 startsInbounds: op.hasInboundsIndices());
341
342 std::optional<SmallVector<Value>> newValues = op.updateMemrefAndIndices(
343 rewriter, newMemref: collapse.getViewSource(), newIndices: sourceIndices);
344 if (newValues)
345 rewriter.replaceOp(op, newValues: *newValues);
346 return success();
347}
348
349LogicalResult IndexedMemCopyOpOfSubViewOpFolder::matchAndRewrite(
350 memref::IndexedMemCopyOpInterface op, PatternRewriter &rewriter) const {
351 TypedValue<MemRefType> src = op.getSrc();
352 TypedValue<MemRefType> dst = op.getDst();
353 auto srcSubview = src ? src.getDefiningOp<memref::SubViewOp>() : nullptr;
354 auto dstSubview = dst ? dst.getDefiningOp<memref::SubViewOp>() : nullptr;
355 if (!srcSubview && !dstSubview)
356 return rewriter.notifyMatchFailure(
357 arg&: op, msg: "no subviews found on indexed copy inputs");
358
359 Value newSrc = src;
360 SmallVector<Value> newSrcIndices = llvm::to_vector(Range: op.getSrcIndices());
361 Value newDst = dst;
362 SmallVector<Value> newDstIndices = llvm::to_vector(Range: op.getDstIndices());
363 if (srcSubview) {
364 newSrc = srcSubview.getSource();
365 newSrcIndices.clear();
366 affine::resolveIndicesIntoOpWithOffsetsAndStrides(
367 rewriter, loc: op.getLoc(), mixedSourceOffsets: srcSubview.getMixedOffsets(),
368 mixedSourceStrides: srcSubview.getMixedStrides(), rankReducedDims: srcSubview.getDroppedDims(),
369 consumerIndices: op.getSrcIndices(), resolvedIndices&: newSrcIndices);
370 }
371 if (dstSubview) {
372 newDst = dstSubview.getSource();
373 newDstIndices.clear();
374 affine::resolveIndicesIntoOpWithOffsetsAndStrides(
375 rewriter, loc: op.getLoc(), mixedSourceOffsets: dstSubview.getMixedOffsets(),
376 mixedSourceStrides: dstSubview.getMixedStrides(), rankReducedDims: dstSubview.getDroppedDims(),
377 consumerIndices: op.getDstIndices(), resolvedIndices&: newDstIndices);
378 }
379 op.setMemrefsAndIndices(rewriter, newSrc, newSrcIndices, newDst,
380 newDstIndices);
381 return success();
382}
383
384LogicalResult IndexedMemCopyOpOfExpandShapeOpFolder::matchAndRewrite(
385 memref::IndexedMemCopyOpInterface op, PatternRewriter &rewriter) const {
386 TypedValue<MemRefType> src = op.getSrc();
387 TypedValue<MemRefType> dst = op.getDst();
388 auto srcExpand = src ? src.getDefiningOp<memref::ExpandShapeOp>() : nullptr;
389 auto dstExpand = dst ? dst.getDefiningOp<memref::ExpandShapeOp>() : nullptr;
390 if (!srcExpand && !dstExpand)
391 return rewriter.notifyMatchFailure(
392 arg&: op, msg: "no expand_shapes found on indexed copy inputs");
393
394 Value newSrc = src;
395 SmallVector<Value> newSrcIndices = llvm::to_vector(Range: op.getSrcIndices());
396 Value newDst = dst;
397 SmallVector<Value> newDstIndices = llvm::to_vector(Range: op.getDstIndices());
398 if (srcExpand) {
399 newSrc = srcExpand.getViewSource();
400 newSrcIndices.clear();
401 memref::resolveSourceIndicesExpandShape(loc: op.getLoc(), rewriter, expandShapeOp: srcExpand,
402 indices: op.getSrcIndices(), sourceIndices&: newSrcIndices,
403 startsInbounds: op.hasInboundsSrcIndices());
404 }
405 if (dstExpand) {
406 newDst = dstExpand.getViewSource();
407 newDstIndices.clear();
408 memref::resolveSourceIndicesExpandShape(loc: op.getLoc(), rewriter, expandShapeOp: dstExpand,
409 indices: op.getDstIndices(), sourceIndices&: newDstIndices,
410 startsInbounds: op.hasInboundsDstIndices());
411 }
412 op.setMemrefsAndIndices(rewriter, newSrc, newSrcIndices, newDst,
413 newDstIndices);
414 return success();
415}
416
417LogicalResult IndexedMemCopyOpOfCollapseShapeOpFolder::matchAndRewrite(
418 memref::IndexedMemCopyOpInterface op, PatternRewriter &rewriter) const {
419 TypedValue<MemRefType> src = op.getSrc();
420 TypedValue<MemRefType> dst = op.getDst();
421 auto srcCollapse =
422 src ? src.getDefiningOp<memref::CollapseShapeOp>() : nullptr;
423 auto dstCollapse =
424 dst ? dst.getDefiningOp<memref::CollapseShapeOp>() : nullptr;
425 if (!srcCollapse && !dstCollapse)
426 return rewriter.notifyMatchFailure(
427 arg&: op, msg: "no collapse_shapes found on indexed copy inputs");
428
429 Value newSrc = src;
430 SmallVector<Value> newSrcIndices = llvm::to_vector(Range: op.getSrcIndices());
431 Value newDst = dst;
432 SmallVector<Value> newDstIndices = llvm::to_vector(Range: op.getDstIndices());
433 if (srcCollapse) {
434 newSrc = srcCollapse.getViewSource();
435 newSrcIndices.clear();
436 memref::resolveSourceIndicesCollapseShape(
437 loc: op.getLoc(), rewriter, collapseShapeOp: srcCollapse, indices: op.getSrcIndices(), sourceIndices&: newSrcIndices,
438 startsInbounds: op.hasInboundsSrcIndices());
439 }
440 if (dstCollapse) {
441 newDst = dstCollapse.getViewSource();
442 newDstIndices.clear();
443 memref::resolveSourceIndicesCollapseShape(
444 loc: op.getLoc(), rewriter, collapseShapeOp: dstCollapse, indices: op.getDstIndices(), sourceIndices&: newDstIndices,
445 startsInbounds: op.hasInboundsDstIndices());
446 }
447 op.setMemrefsAndIndices(rewriter, newSrc, newSrcIndices, newDst,
448 newDstIndices);
449 return success();
450}
451
452LogicalResult
453TransferOpOfSubViewOpFolder::matchAndRewrite(VectorTransferOpInterface op,
454 PatternRewriter &rewriter) const {
455 auto subview = op.getBase().getDefiningOp<memref::SubViewOp>();
456 if (!subview)
457 return rewriter.notifyMatchFailure(arg&: op, msg: "not accessing a subview");
458
459 AffineMap perm = op.getPermutationMap();
460 // Note: no identity permutation check here, since subview folding can handle
461 // complex permutations because it doesn't merge or split any individual
462 // dimension.
463 if (op.hasOutOfBoundsDim())
464 return rewriter.notifyMatchFailure(arg&: op, msg: "out of bounds dimension");
465 VectorType vecTy = op.getVectorType();
466 // Because we know the permutation map is a minor identity, we know that the
467 // last N dimensions must have unit stride, where N is the vector rank.
468 if (!hasTrailingUnitStrides(subview, n: vecTy.getRank()))
469 return rewriter.notifyMatchFailure(arg&: subview, msg: "non-unit stride within last " +
470 Twine(vecTy.getRank()) +
471 " dimensions");
472
473 AffineMap newPerm = expandDimsToRank(map: perm, rank: subview.getSourceType().getRank(),
474 projectedDimensions: subview.getDroppedDims());
475
476 if (failed(Result: op.mayUpdateStartingPosition(newBaseType: subview.getSourceType(), newPermutationMap: newPerm)))
477 return rewriter.notifyMatchFailure(arg&: subview,
478 msg: "failed op-specific preconditions");
479
480 // The region of a `vector.mask` can only hold the masked op, so create the
481 // new indices above it.
482 // TODO: Move this into a `MaskableOpInterfaceRewritePattern` (an interface
483 // version of `MaskableOpRewritePattern` that supports in-place updates) once
484 // it exists.
485 auto maskableOp = cast<vector::MaskableOpInterface>(Val: op.getOperation());
486 OpBuilder::InsertionGuard guard(rewriter);
487 if (maskableOp.isMasked())
488 rewriter.setInsertionPoint(maskableOp.getMaskingOp());
489 SmallVector<Value> newIndices;
490 affine::resolveIndicesIntoOpWithOffsetsAndStrides(
491 rewriter, loc: op.getLoc(), mixedSourceOffsets: subview.getMixedOffsets(),
492 mixedSourceStrides: subview.getMixedStrides(), rankReducedDims: subview.getDroppedDims(), consumerIndices: op.getIndices(),
493 resolvedIndices&: newIndices);
494 op.updateStartingPosition(rewriter, newBase: subview.getSource(), newIndices,
495 newPermutationMap: AffineMapAttr::get(value: newPerm));
496 return success();
497}
498
499LogicalResult TransferOpOfExpandShapeOpFolder::matchAndRewrite(
500 VectorTransferOpInterface op, PatternRewriter &rewriter) const {
501 auto expand = op.getBase().getDefiningOp<memref::ExpandShapeOp>();
502 if (!expand)
503 return rewriter.notifyMatchFailure(arg&: op, msg: "not accessing an expand_shape");
504
505 if (op.hasOutOfBoundsDim())
506 return rewriter.notifyMatchFailure(arg&: op, msg: "out of bounds dimension");
507
508 int64_t srcRank = expand.getSrc().getType().getRank();
509 int64_t vecRank = op.getVectorType().getRank();
510 if (srcRank < vecRank)
511 return rewriter.notifyMatchFailure(arg&: op,
512 msg: "source rank is less than vector rank");
513
514 llvm::SmallDenseMap<int64_t, int64_t, 8> unstridedResDimToSrcDim;
515 for (auto [srcIdx, reassoc] :
516 llvm::enumerate(First: expand.getReassociationIndices())) {
517 unstridedResDimToSrcDim.insert(KV: {reassoc.back(), srcIdx});
518 }
519 // If every dimension of the expanded shape that appears in the permutation
520 // map is also present in the final entry of the expansions (meaning that
521 // collapsing in more values won't cause us to need to stride the index), we
522 // can fold in the expansion. (This doesn't currently account for expanding
523 // length X to X by 1, but it could in the future).
524 AffineMap permMap = op.getPermutationMap();
525 SmallVector<AffineExpr> newPermMapResults;
526 newPermMapResults.reserve(N: permMap.getNumResults());
527 for (AffineExpr permRes : permMap.getResults()) {
528 auto resDim = dyn_cast<AffineDimExpr>(Val&: permRes);
529 if (!resDim)
530 return rewriter.notifyMatchFailure(
531 arg&: op, msg: "has non-dim entry in permutation map");
532 auto dimInSrc = unstridedResDimToSrcDim.find(Val: resDim.getPosition());
533 if (dimInSrc == unstridedResDimToSrcDim.end())
534 return rewriter.notifyMatchFailure(arg&: op,
535 msg: "permutation map result would be made "
536 "strided by expand_shape folding");
537 newPermMapResults.push_back(Elt: rewriter.getAffineDimExpr(position: dimInSrc->second));
538 }
539
540 auto newPerm = AffineMap::get(dimCount: srcRank, symbolCount: 0, results: newPermMapResults, context: op.getContext());
541
542 if (failed(Result: op.mayUpdateStartingPosition(newBaseType: expand.getSrc().getType(), newPermutationMap: newPerm)))
543 return rewriter.notifyMatchFailure(arg&: op, msg: "failed op-specific preconditions");
544
545 // The region of a `vector.mask` can only hold the masked op, so create the
546 // new indices above it.
547 // TODO: Move this into a `MaskableOpInterfaceRewritePattern` (an interface
548 // version of `MaskableOpRewritePattern` that supports in-place updates) once
549 // it exists.
550 auto maskableOp = cast<vector::MaskableOpInterface>(Val: op.getOperation());
551 OpBuilder::InsertionGuard guard(rewriter);
552 if (maskableOp.isMasked())
553 rewriter.setInsertionPoint(maskableOp.getMaskingOp());
554 SmallVector<Value> newIndices;
555 // We can use a disjoint linearization if we aren't masking, because then all
556 // indicators show that the start position will be in bounds.
557 memref::resolveSourceIndicesExpandShape(
558 loc: op.getLoc(), rewriter, expandShapeOp: expand, indices: op.getIndices(), sourceIndices&: newIndices,
559 /*startsInbounds=*/!op.getMask() && !maskableOp.isMasked());
560
561 op.updateStartingPosition(rewriter, newBase: expand.getViewSource(), newIndices,
562 newPermutationMap: AffineMapAttr::get(value: newPerm));
563 return success();
564}
565
566LogicalResult TransferOpOfCollapseShapeOpFolder::matchAndRewrite(
567 VectorTransferOpInterface op, PatternRewriter &rewriter) const {
568 auto collapse = op.getBase().getDefiningOp<memref::CollapseShapeOp>();
569 if (!collapse)
570 return rewriter.notifyMatchFailure(arg&: op, msg: "not accessing a collapse_shape");
571
572 if (!op.getPermutationMap().isMinorIdentity())
573 return rewriter.notifyMatchFailure(arg&: op,
574 msg: "non-minor identity permutation map");
575
576 if (op.hasOutOfBoundsDim())
577 return rewriter.notifyMatchFailure(arg&: op, msg: "out of bounds dimension");
578
579 int64_t srcRank = collapse.getSrc().getType().getRank();
580 int64_t vecRank = op.getVectorType().getRank();
581 if (srcRank < vecRank)
582 return rewriter.notifyMatchFailure(arg&: op,
583 msg: "source rank is less than vector rank");
584
585 // Note: no - 1 on the rank here. While we could treat the collapse of [1, 1,
586 // N] into N as a special case, that is left as future work for those who need
587 // such a pattern.
588 SmallVector<ReassociationIndices> reassocs =
589 collapse.getReassociationIndices();
590 if (!hasTrivialReassociationSuffix(reassocs, n: vecRank))
591 return rewriter.notifyMatchFailure(
592 arg&: op, msg: "collapse_shape folding would split a transfer dimension");
593
594 AffineMap newPerm =
595 AffineMap::getMinorIdentityMap(dims: srcRank, results: vecRank, context: op.getContext());
596 if (failed(
597 Result: op.mayUpdateStartingPosition(newBaseType: collapse.getSrc().getType(), newPermutationMap: newPerm)))
598 return rewriter.notifyMatchFailure(arg&: op, msg: "failed op-specific preconditions");
599
600 // The region of a `vector.mask` can only hold the masked op, so create the
601 // new indices above it.
602 // TODO: Move this into a `MaskableOpInterfaceRewritePattern` (an interface
603 // version of `MaskableOpRewritePattern` that supports in-place updates) once
604 // it exists.
605 auto maskableOp = cast<vector::MaskableOpInterface>(Val: op.getOperation());
606 OpBuilder::InsertionGuard guard(rewriter);
607 if (maskableOp.isMasked())
608 rewriter.setInsertionPoint(maskableOp.getMaskingOp());
609 SmallVector<Value> newIndices;
610 memref::resolveSourceIndicesCollapseShape(
611 loc: op.getLoc(), rewriter, collapseShapeOp: collapse, indices: op.getIndices(), sourceIndices&: newIndices,
612 /*startsInbounds=*/!op.getMask() && !maskableOp.isMasked());
613
614 op.updateStartingPosition(rewriter, newBase: collapse.getViewSource(), newIndices,
615 newPermutationMap: AffineMapAttr::get(value: newPerm));
616 return success();
617}
618
619void memref::populateFoldMemRefAliasOpPatterns(RewritePatternSet &patterns) {
620 patterns
621 .add<AccessOpOfSubViewOpFolder, AccessOpOfExpandShapeOpFolder,
622 AccessOpOfCollapseShapeOpFolder, IndexedMemCopyOpOfSubViewOpFolder,
623 IndexedMemCopyOpOfExpandShapeOpFolder,
624 IndexedMemCopyOpOfCollapseShapeOpFolder, TransferOpOfSubViewOpFolder,
625 TransferOpOfExpandShapeOpFolder, TransferOpOfCollapseShapeOpFolder,
626 SubViewOfSubViewFolder>(arg: patterns.getContext());
627}
628
629//===----------------------------------------------------------------------===//
630// Pass registration
631//===----------------------------------------------------------------------===//
632
633namespace {
634
635struct FoldMemRefAliasOpsPass final
636 : public memref::impl::FoldMemRefAliasOpsPassBase<FoldMemRefAliasOpsPass> {
637 void runOnOperation() override;
638};
639
640} // namespace
641
642void FoldMemRefAliasOpsPass::runOnOperation() {
643 RewritePatternSet patterns(&getContext());
644 memref::populateFoldMemRefAliasOpPatterns(patterns);
645 (void)applyPatternsGreedily(op: getOperation(), patterns: std::move(patterns));
646}
647