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
24using namespace mlir;
25
26namespace {
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.
34static 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.
41static SmallVector<OpFoldResult> getRemainingSizes(RewriterBase &rewriter,
42 Location loc,
43 Value srcMemRef,
44 ValueRange indices) {
45 auto extractStridedMetadataOp =
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.
70static SmallVector<OpFoldResult>
71getIndexedAccessViewSizes(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 extractStridedMetadataOp =
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
125static 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
138static 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: ?>>
152struct 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.
197struct 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
250void memref::populateExtractAddressComputationsPatterns(
251 RewritePatternSet &patterns) {
252 patterns.add<IndexedAccessOpRewriter, TransferOpRewriter>(
253 arg: patterns.getContext());
254}
255