| 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 | |
| 34 | namespace mlir { |
| 35 | namespace memref { |
| 36 | #define GEN_PASS_DEF_FOLDMEMREFALIASOPSPASS |
| 37 | #include "mlir/Dialect/MemRef/Transforms/Passes.h.inc" |
| 38 | } // namespace memref |
| 39 | } // namespace mlir |
| 40 | |
| 41 | using 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. |
| 49 | static bool |
| 50 | hasTrivialReassociationSuffix(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 | |
| 61 | static 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 | |
| 74 | namespace { |
| 75 | /// Folds subview(subview(x)) to a single subview(x). |
| 76 | class SubViewOfSubViewFolder : public OpRewritePattern<memref::SubViewOp> { |
| 77 | public: |
| 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. |
| 103 | struct 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. |
| 117 | struct 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. |
| 133 | struct 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. |
| 146 | struct 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. |
| 157 | struct 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. |
| 168 | struct 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. |
| 182 | struct 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. |
| 197 | struct 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. |
| 209 | struct TransferOpOfCollapseShapeOpFolder final |
| 210 | : OpInterfaceRewritePattern<VectorTransferOpInterface> { |
| 211 | using Base::Base; |
| 212 | |
| 213 | LogicalResult matchAndRewrite(VectorTransferOpInterface op, |
| 214 | PatternRewriter &rewriter) const override; |
| 215 | }; |
| 216 | } // namespace |
| 217 | |
| 218 | LogicalResult |
| 219 | AccessOpOfSubViewOpFolder::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 | |
| 267 | LogicalResult 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 | |
| 308 | LogicalResult 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 | |
| 349 | LogicalResult 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 | |
| 384 | LogicalResult 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 | |
| 417 | LogicalResult 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 | |
| 452 | LogicalResult |
| 453 | TransferOpOfSubViewOpFolder::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 | |
| 499 | LogicalResult 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 | |
| 566 | LogicalResult 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 | |
| 619 | void 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 | |
| 633 | namespace { |
| 634 | |
| 635 | struct FoldMemRefAliasOpsPass final |
| 636 | : public memref::impl::FoldMemRefAliasOpsPassBase<FoldMemRefAliasOpsPass> { |
| 637 | void runOnOperation() override; |
| 638 | }; |
| 639 | |
| 640 | } // namespace |
| 641 | |
| 642 | void FoldMemRefAliasOpsPass::runOnOperation() { |
| 643 | RewritePatternSet patterns(&getContext()); |
| 644 | memref::populateFoldMemRefAliasOpPatterns(patterns); |
| 645 | (void)applyPatternsGreedily(op: getOperation(), patterns: std::move(patterns)); |
| 646 | } |
| 647 | |