| 1 | //===- ExtractAddressCmoputations.cpp - Extract address computations -----===// |
| 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 rewrites memory access operations with offsets into |
| 10 | /// accesses through a subview and without any offset on the access operation |
| 11 | /// itself. |
| 12 | // |
| 13 | //===----------------------------------------------------------------------===// |
| 14 | |
| 15 | #include "mlir/Dialect/Affine/IR/AffineOps.h" |
| 16 | #include "mlir/Dialect/Arith/IR/Arith.h" |
| 17 | #include "mlir/Dialect/MemRef/IR/MemRef.h" |
| 18 | #include "mlir/Dialect/MemRef/IR/MemoryAccessOpInterfaces.h" |
| 19 | #include "mlir/Dialect/MemRef/Transforms/Transforms.h" |
| 20 | #include "mlir/Dialect/Utils/StaticValueUtils.h" |
| 21 | #include "mlir/Dialect/Vector/IR/VectorOps.h" |
| 22 | #include "mlir/IR/PatternMatch.h" |
| 23 | |
| 24 | using namespace mlir; |
| 25 | |
| 26 | namespace { |
| 27 | |
| 28 | //===----------------------------------------------------------------------===// |
| 29 | // Helper functions for the `access base[off0...]` |
| 30 | // => `access (subview base[off0...])[0...]` pattern. |
| 31 | //===----------------------------------------------------------------------===// |
| 32 | |
| 33 | /// Returns true if every index is zero. |
| 34 | static bool hasAllZeroIndices(ValueRange indices) { |
| 35 | return llvm::all_of(Range: getAsOpFoldResult(values: indices), P: isZeroInteger); |
| 36 | } |
| 37 | |
| 38 | /// Get the remaining size in each dimension - that is, the size of the memref |
| 39 | /// dimension minus the index. Used to preserve in_bounds behavior for |
| 40 | /// transfer_read/write. |
| 41 | static SmallVector<OpFoldResult> getRemainingSizes(RewriterBase &rewriter, |
| 42 | Location loc, |
| 43 | Value srcMemRef, |
| 44 | ValueRange indices) { |
| 45 | auto = |
| 46 | memref::ExtractStridedMetadataOp::create(builder&: rewriter, location: loc, source: srcMemRef); |
| 47 | SmallVector<OpFoldResult> srcSizes = |
| 48 | extractStridedMetadataOp.getConstifiedMixedSizes(); |
| 49 | SmallVector<OpFoldResult> mixedIndices = getAsOpFoldResult(values: indices); |
| 50 | SmallVector<OpFoldResult> finalSizes; |
| 51 | |
| 52 | AffineExpr s0 = rewriter.getAffineSymbolExpr(position: 0); |
| 53 | AffineExpr s1 = rewriter.getAffineSymbolExpr(position: 1); |
| 54 | |
| 55 | for (auto [srcSize, index] : llvm::zip_equal(t&: srcSizes, u&: mixedIndices)) { |
| 56 | finalSizes.push_back(Elt: affine::makeComposedFoldedAffineApply( |
| 57 | b&: rewriter, loc, expr: s0 - s1, operands: {srcSize, index})); |
| 58 | } |
| 59 | return finalSizes; |
| 60 | } |
| 61 | |
| 62 | /// Get the sizes needed to create a valid subview for an indexed access. |
| 63 | /// The trailing dimensions are sized using the accessed shape, taking |
| 64 | /// the minimum of that shape's size and what's available along the relevant |
| 65 | /// memref dimension as a dynamic value if the memref is dynamically shaped |
| 66 | /// (so as to avoid subviews that exceed the bounds of the relevant memref |
| 67 | /// dimension). If the operation accesses a dynamic number of elements along |
| 68 | /// the dimension, the size of the subview will always be the remaining element |
| 69 | /// count along the dimension. |
| 70 | static SmallVector<OpFoldResult> |
| 71 | getIndexedAccessViewSizes(RewriterBase &rewriter, |
| 72 | memref::IndexedAccessOpInterface op) { |
| 73 | TypedValue<MemRefType> srcMemRef = op.getAccessedMemref(); |
| 74 | assert(srcMemRef && "expected indexed access with a memref" ); |
| 75 | |
| 76 | MemRefType srcType = srcMemRef.getType(); |
| 77 | int64_t srcRank = srcType.getRank(); |
| 78 | SmallVector<int64_t> accessedShape = op.getAccessedShape(); |
| 79 | int64_t accessedRank = static_cast<int64_t>(accessedShape.size()); |
| 80 | assert(accessedRank <= srcRank && |
| 81 | "can't access more dimensions than a memref has" ); |
| 82 | |
| 83 | SmallVector<OpFoldResult> indices = getAsOpFoldResult(values: op.getIndices()); |
| 84 | int64_t firstAccessedDim = srcRank - accessedRank; |
| 85 | |
| 86 | Location loc = op.getLoc(); |
| 87 | SmallVector<OpFoldResult> viewSizes(srcRank, rewriter.getIndexAttr(value: 1)); |
| 88 | SmallVector<OpFoldResult> srcSizes; |
| 89 | AffineExpr s0 = rewriter.getAffineSymbolExpr(position: 0); |
| 90 | AffineExpr s1 = rewriter.getAffineSymbolExpr(position: 1); |
| 91 | AffineExpr cst = rewriter.getAffineSymbolExpr(position: 2); |
| 92 | |
| 93 | auto ensureSrcSizes = [&]() { |
| 94 | if (srcSizes.empty()) { |
| 95 | auto = |
| 96 | memref::ExtractStridedMetadataOp::create(builder&: rewriter, location: loc, source: srcMemRef); |
| 97 | srcSizes = extractStridedMetadataOp.getConstifiedMixedSizes(); |
| 98 | } |
| 99 | }; |
| 100 | |
| 101 | for (int64_t accessedDim : llvm::seq<int64_t>(Begin: 0, End: accessedRank)) { |
| 102 | int64_t accessedSize = accessedShape[accessedDim]; |
| 103 | int64_t dim = firstAccessedDim + accessedDim; |
| 104 | if (!ShapedType::isDynamic(dValue: accessedSize)) { |
| 105 | int64_t srcDimSize = srcType.getDimSize(idx: dim); |
| 106 | if (!ShapedType::isDynamic(dValue: srcDimSize) || accessedSize == 1) { |
| 107 | viewSizes[dim] = rewriter.getIndexAttr(value: accessedSize); |
| 108 | continue; |
| 109 | } |
| 110 | ensureSrcSizes(); |
| 111 | viewSizes[dim] = affine::makeComposedFoldedAffineMin( |
| 112 | b&: rewriter, loc, |
| 113 | map: AffineMap::get(/*dimCount=*/0, /*symbolCount=*/3, results: {s0 - s1, cst}, |
| 114 | context: rewriter.getContext()), |
| 115 | operands: {srcSizes[dim], indices[dim], rewriter.getIndexAttr(value: accessedSize)}); |
| 116 | } else { |
| 117 | ensureSrcSizes(); |
| 118 | viewSizes[dim] = affine::makeComposedFoldedAffineApply( |
| 119 | b&: rewriter, loc, expr: s0 - s1, operands: {srcSizes[dim], indices[dim]}); |
| 120 | } |
| 121 | } |
| 122 | return viewSizes; |
| 123 | } |
| 124 | |
| 125 | static memref::SubViewOp createSubviewForAccess(RewriterBase &rewriter, |
| 126 | Location loc, Value srcMemRef, |
| 127 | ValueRange indices, |
| 128 | ArrayRef<OpFoldResult> sizes) { |
| 129 | int64_t rank = cast<MemRefType>(Val: srcMemRef.getType()).getRank(); |
| 130 | SmallVector<OpFoldResult> mixedIndices = getAsOpFoldResult(values: indices); |
| 131 | SmallVector<OpFoldResult> ones(rank, rewriter.getIndexAttr(value: 1)); |
| 132 | |
| 133 | return memref::SubViewOp::create(builder&: rewriter, location: loc, /*source=*/srcMemRef, |
| 134 | /*offsets=*/mixedIndices, |
| 135 | /*sizes=*/sizes, /*strides=*/ones); |
| 136 | } |
| 137 | |
| 138 | static SmallVector<Value> getZeroIndices(RewriterBase &rewriter, Location loc, |
| 139 | int64_t rank) { |
| 140 | if (rank == 0) |
| 141 | return {}; |
| 142 | Value zero = arith::ConstantIndexOp::create(builder&: rewriter, location: loc, value: 0); |
| 143 | return SmallVector<Value>(rank, zero); |
| 144 | } |
| 145 | |
| 146 | /// Rewrite an indexed access op so that all its indices are zeros. |
| 147 | /// E.g., %res = indexed_access %base[%off0]...[%offN] |
| 148 | /// => |
| 149 | /// %new_base = subview %base[%off0,.., %offN][1,..,1][1,..,1] |
| 150 | /// %res = indexed_access %new_base[0,..,0] : |
| 151 | /// memref<1x..x1xTy, strided<[1,..,1], offset: ?>> |
| 152 | struct IndexedAccessOpRewriter final |
| 153 | : OpInterfaceRewritePattern<memref::IndexedAccessOpInterface> { |
| 154 | using Base::Base; |
| 155 | |
| 156 | LogicalResult matchAndRewrite(memref::IndexedAccessOpInterface op, |
| 157 | PatternRewriter &rewriter) const override { |
| 158 | TypedValue<MemRefType> srcMemRef = op.getAccessedMemref(); |
| 159 | if (!srcMemRef) |
| 160 | return rewriter.notifyMatchFailure(arg&: op, msg: "source is not a memref" ); |
| 161 | |
| 162 | int64_t rank = srcMemRef.getType().getRank(); |
| 163 | if (rank == 0) |
| 164 | return rewriter.notifyMatchFailure(arg&: op, |
| 165 | msg: "0-D accesses don't need rewriting" ); |
| 166 | |
| 167 | if (static_cast<int64_t>(op.getAccessedShape().size()) > rank) |
| 168 | return rewriter.notifyMatchFailure( |
| 169 | arg&: op, msg: "can't access more dimensions than a memref has" ); |
| 170 | |
| 171 | if (!op.hasInboundsIndices()) |
| 172 | return rewriter.notifyMatchFailure(arg&: op, msg: "indices may be out of bounds" ); |
| 173 | |
| 174 | // If the access already has only zeros as indices there is nothing |
| 175 | // to do. |
| 176 | if (hasAllZeroIndices(indices: op.getIndices())) |
| 177 | return rewriter.notifyMatchFailure( |
| 178 | arg&: op, msg: "no computation to extract: offsets are 0s" ); |
| 179 | |
| 180 | SmallVector<OpFoldResult> subviewSizes = |
| 181 | getIndexedAccessViewSizes(rewriter, op); |
| 182 | |
| 183 | Location loc = op.getLoc(); |
| 184 | auto subview = createSubviewForAccess(rewriter, loc, srcMemRef, |
| 185 | indices: op.getIndices(), sizes: subviewSizes); |
| 186 | SmallVector<Value> zeros = getZeroIndices(rewriter, loc, rank); |
| 187 | |
| 188 | std::optional<SmallVector<Value>> newValues = |
| 189 | op.updateMemrefAndIndices(rewriter, newMemref: subview.getResult(), newIndices: zeros); |
| 190 | if (newValues) |
| 191 | rewriter.replaceOp(op, newValues: *newValues); |
| 192 | return success(); |
| 193 | } |
| 194 | }; |
| 195 | |
| 196 | /// Rewrite a vector transfer op so that all its indices are zeros. |
| 197 | struct TransferOpRewriter final |
| 198 | : OpInterfaceRewritePattern<VectorTransferOpInterface> { |
| 199 | using Base::Base; |
| 200 | |
| 201 | LogicalResult matchAndRewrite(VectorTransferOpInterface op, |
| 202 | PatternRewriter &rewriter) const override { |
| 203 | Value srcMemRef = op.getBase(); |
| 204 | auto srcType = dyn_cast<MemRefType>(Val: srcMemRef.getType()); |
| 205 | if (!srcType) |
| 206 | return rewriter.notifyMatchFailure(arg&: op, msg: "source is not a memref" ); |
| 207 | |
| 208 | int64_t rank = srcType.getRank(); |
| 209 | |
| 210 | if (rank == 0) |
| 211 | return rewriter.notifyMatchFailure(arg&: op, |
| 212 | msg: "0-D accesses don't need rewriting" ); |
| 213 | |
| 214 | if (hasAllZeroIndices(indices: op.getIndices())) |
| 215 | return rewriter.notifyMatchFailure( |
| 216 | arg&: op, msg: "no computation to extract: offsets are 0s" ); |
| 217 | |
| 218 | Location loc = op.getLoc(); |
| 219 | SmallVector<OpFoldResult> offsets = getAsOpFoldResult(values: op.getIndices()); |
| 220 | SmallVector<OpFoldResult> strides(rank, rewriter.getIndexAttr(value: 1)); |
| 221 | // Approximate sizes needed so we can test the general case of the |
| 222 | // replacement we're planning to do - this can be tightened up later when |
| 223 | // this pattern is extended to reason about in_bounds, which dimensions are |
| 224 | // accessed, etc. |
| 225 | SmallVector<OpFoldResult> approximateSizes( |
| 226 | rank, rewriter.getIndexAttr(value: ShapedType::kDynamic)); |
| 227 | MemRefType subviewType = memref::SubViewOp::inferResultType( |
| 228 | sourceMemRefType: srcType, staticOffsets: offsets, staticSizes: approximateSizes, staticStrides: strides); |
| 229 | if (!subviewType) |
| 230 | return rewriter.notifyMatchFailure(arg&: op, msg: "failed to infer subview type" ); |
| 231 | |
| 232 | AffineMap permutationMap = op.getPermutationMap(); |
| 233 | if (failed(Result: op.mayUpdateStartingPosition(newBaseType: subviewType, newPermutationMap: permutationMap))) |
| 234 | return rewriter.notifyMatchFailure(arg&: op, |
| 235 | msg: "failed op-specific preconditions" ); |
| 236 | |
| 237 | SmallVector<OpFoldResult> sizes = |
| 238 | getRemainingSizes(rewriter, loc, srcMemRef, indices: op.getIndices()); |
| 239 | auto subview = createSubviewForAccess(rewriter, loc, srcMemRef, |
| 240 | indices: op.getIndices(), sizes); |
| 241 | SmallVector<Value> zeros = getZeroIndices(rewriter, loc, rank); |
| 242 | |
| 243 | op.updateStartingPosition(rewriter, newBase: subview.getResult(), newIndices: zeros, |
| 244 | newPermutationMap: AffineMapAttr::get(value: permutationMap)); |
| 245 | return success(); |
| 246 | } |
| 247 | }; |
| 248 | } // namespace |
| 249 | |
| 250 | void memref::( |
| 251 | RewritePatternSet &patterns) { |
| 252 | patterns.add<IndexedAccessOpRewriter, TransferOpRewriter>( |
| 253 | arg: patterns.getContext()); |
| 254 | } |
| 255 | |