1//===----- FlattenMemRefs.cpp - MemRef ops flattener pass ----------------===//
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 file contains patterns for flattening an multi-rank memref-related
10// ops into 1-d memref ops.
11//
12//===----------------------------------------------------------------------===//
13
14#include "mlir/Dialect/Affine/IR/AffineOps.h"
15#include "mlir/Dialect/Arith/IR/Arith.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/Utils/IndexingUtils.h"
22#include "mlir/Dialect/Utils/StaticValueUtils.h"
23#include "mlir/Dialect/Vector/IR/VectorOps.h"
24#include "mlir/IR/Attributes.h"
25#include "mlir/IR/Builders.h"
26#include "mlir/IR/BuiltinTypes.h"
27#include "mlir/IR/OpDefinition.h"
28#include "mlir/IR/PatternMatch.h"
29#include "mlir/Transforms/GreedyPatternRewriteDriver.h"
30#include "llvm/ADT/STLExtras.h"
31#include <algorithm>
32
33namespace mlir {
34namespace memref {
35#define GEN_PASS_DEF_FLATTENMEMREFSPASS
36#include "mlir/Dialect/MemRef/Transforms/Passes.h.inc"
37} // namespace memref
38} // namespace mlir
39
40using namespace mlir;
41
42static Value getValueFromOpFoldResult(OpBuilder &rewriter, Location loc,
43 OpFoldResult in) {
44 if (Attribute offsetAttr = dyn_cast<Attribute>(Val&: in)) {
45 return arith::ConstantIndexOp::create(
46 builder&: rewriter, location: loc, value: cast<IntegerAttr>(Val&: offsetAttr).getInt());
47 }
48 return cast<Value>(Val&: in);
49}
50
51/// Returns a collapsed memref and the linearized index to access the element
52/// at the specified indices.
53static std::pair<Value, Value> getFlattenMemrefAndOffset(OpBuilder &rewriter,
54 Location loc,
55 Value source,
56 ValueRange indices) {
57 int64_t sourceOffset;
58 SmallVector<int64_t, 4> sourceStrides;
59 auto sourceType = cast<MemRefType>(Val: source.getType());
60 if (failed(Result: sourceType.getStridesAndOffset(strides&: sourceStrides, offset&: sourceOffset))) {
61 assert(false);
62 }
63
64 memref::ExtractStridedMetadataOp stridedMetadata =
65 memref::ExtractStridedMetadataOp::create(builder&: rewriter, location: loc, source);
66
67 auto typeBit = sourceType.getElementType().getIntOrFloatBitWidth();
68 OpFoldResult linearizedIndices;
69 memref::LinearizedMemRefInfo linearizedInfo;
70 std::tie(args&: linearizedInfo, args&: linearizedIndices) =
71 memref::getLinearizedMemRefOffsetAndSize(
72 builder&: rewriter, loc, srcBits: typeBit, dstBits: typeBit,
73 offset: stridedMetadata.getConstifiedMixedOffset(),
74 sizes: stridedMetadata.getConstifiedMixedSizes(),
75 strides: stridedMetadata.getConstifiedMixedStrides(),
76 indices: getAsOpFoldResult(values: indices));
77
78 return std::make_pair(
79 x: memref::ReinterpretCastOp::create(
80 builder&: rewriter, location: loc, source,
81 /*offset=*/linearizedInfo.linearizedOffset,
82 /*sizes=*/
83 ArrayRef<OpFoldResult>{linearizedInfo.linearizedSize},
84 /*strides=*/
85 ArrayRef<OpFoldResult>{rewriter.getIndexAttr(value: 1)}),
86 y: getValueFromOpFoldResult(rewriter, loc, in: linearizedIndices));
87}
88
89static bool needFlattening(Value val) {
90 auto type = cast<MemRefType>(Val: val.getType());
91 return type.getRank() > 1;
92}
93
94static bool checkLayout(Value val) {
95 auto type = cast<MemRefType>(Val: val.getType());
96 return type.getLayout().isIdentity() ||
97 isa<StridedLayoutAttr>(Val: type.getLayout());
98}
99
100namespace {
101static bool hasSupportedElementType(Value memref) {
102 auto type = cast<MemRefType>(Val: memref.getType());
103 return type.getElementType().isIntOrFloat();
104}
105
106/// Compute the type that will be used to linearize the memref.
107/// Used so we don't create IR like `getLinearizedMemRefOffsetAndSize` would.
108static FailureOr<MemRefType> getFlattenedMemRefType(MemRefType sourceType) {
109 int64_t sourceOffset;
110 SmallVector<int64_t> sourceStrides;
111 if (failed(Result: sourceType.getStridesAndOffset(strides&: sourceStrides, offset&: sourceOffset)))
112 return failure();
113
114 auto flatDimSize = SaturatedInteger::wrap(v: 0);
115 for (auto [size, stride] :
116 llvm::zip_equal(t: sourceType.getShape(), u&: sourceStrides)) {
117 auto dimSize =
118 SaturatedInteger::wrap(v: size) * SaturatedInteger::wrap(v: stride);
119 flatDimSize = flatDimSize.smax(other: dimSize);
120 if (flatDimSize.isSaturated())
121 break;
122 }
123
124 if (sourceType.getLayout().isIdentity())
125 return MemRefType::get(
126 shape: {flatDimSize.asInteger()}, elementType: sourceType.getElementType(),
127 layout: MemRefLayoutAttrInterface{}, memorySpace: sourceType.getMemorySpace());
128
129 return MemRefType::get(
130 shape: {flatDimSize.asInteger()}, elementType: sourceType.getElementType(),
131 layout: StridedLayoutAttr::get(context: sourceType.getContext(), offset: sourceOffset, strides: {1}),
132 memorySpace: sourceType.getMemorySpace());
133}
134
135/// Return whether `memref` has the basic properties needed for linearizing it
136/// into a 1-D reinterpret_cast.
137static LogicalResult checkFlattenableMemref(Operation *op, Value memref,
138 PatternRewriter &rewriter) {
139 if (!needFlattening(val: memref))
140 return rewriter.notifyMatchFailure(arg&: op, msg: "memref does not need flattening");
141 if (!checkLayout(val: memref))
142 return rewriter.notifyMatchFailure(arg&: op, msg: "unsupported memref layout");
143 if (!hasSupportedElementType(memref))
144 return rewriter.notifyMatchFailure(arg&: op, msg: "unsupported element type");
145 return success();
146}
147
148/// Wrapeer around checking if the last memref dimension is contiguous that
149/// provides nice failures message.
150static LogicalResult hasUnitTrailingStride(Operation *op,
151 TypedValue<MemRefType> memref,
152 PatternRewriter &rewriter) {
153 if (!memref.getType().areTrailingDimsContiguous(n: 1))
154 return rewriter.notifyMatchFailure(
155 arg&: op, msg: "cannot preserve non-unit trailing access stride");
156
157 return success();
158}
159
160static LogicalResult
161canLinearizeAccessedShape(memref::IndexedAccessOpInterface op,
162 TypedValue<MemRefType> memref,
163 PatternRewriter &rewriter) {
164 SmallVector<int64_t> accessedShape = op.getAccessedShape();
165 if (accessedShape.empty())
166 return success();
167 if (accessedShape.size() > 1)
168 return rewriter.notifyMatchFailure(
169 arg&: op, msg: "cannot preserve multi-dimensional accessed shape");
170
171 return hasUnitTrailingStride(op, memref, rewriter);
172}
173
174static LogicalResult canFlattenTransferOp(VectorTransferOpInterface op,
175 TypedValue<MemRefType> memref,
176 PatternRewriter &rewriter) {
177 // For vector.transfer_read/write, must make sure:
178 // 1. all accesses are inbounds,
179 // 2. has a minor identity permutation map, and
180 // 3. has at most one transfer dimension.
181 AffineMap permutationMap = op.getPermutationMap();
182 if (!permutationMap.isMinorIdentity())
183 return rewriter.notifyMatchFailure(
184 arg&: op, msg: "only identity or minor identity permutation map is supported");
185
186 if (op.hasOutOfBoundsDim())
187 return rewriter.notifyMatchFailure(arg&: op, msg: "only inbounds are supported");
188
189 if (op.getTransferRank() > 1)
190 return rewriter.notifyMatchFailure(
191 arg&: op, msg: "cannot flatten multi-dimensional vector transfer");
192
193 if (op.getTransferRank() > 0 &&
194 failed(Result: hasUnitTrailingStride(op, memref, rewriter)))
195 return failure();
196
197 return success();
198}
199
200// Pattern for memref::AllocOp and memref::AllocaOp.
201//
202// The "source" memref for these ops is the op's own result, so the generic
203// indexed access pattern cannot be used: getFlattenMemrefAndOffset would
204// insert ExtractStridedMetadataOp and ReinterpretCastOp that use op.result
205// before this op in the block. After replaceOpWithNewOp the original result is
206// RAUW'd to the new ReinterpretCastOp, leaving the earlier ops with forward
207// references (domination violations) caught by
208// MLIR_ENABLE_EXPENSIVE_PATTERN_API_CHECKS.
209//
210// Instead, sizes and strides are computed from the op's operands and type
211// (which all dominate the op), avoiding any reference to op.result until the
212// final replaceOpWithNewOp.
213template <typename AllocLikeOp>
214struct AllocLikeFlattenPattern final : public OpRewritePattern<AllocLikeOp> {
215 using Base = OpRewritePattern<AllocLikeOp>;
216 using Base::Base;
217
218 LogicalResult matchAndRewrite(AllocLikeOp op,
219 PatternRewriter &rewriter) const override {
220 if (!needFlattening(op.getMemref()) || !checkLayout(op.getMemref()))
221 return failure();
222
223 Location loc = op->getLoc();
224 auto memrefType = cast<MemRefType>(op.getType());
225 auto elemType = memrefType.getElementType();
226 if (!elemType.isIntOrFloat())
227 return failure();
228 unsigned elemBitWidth = elemType.getIntOrFloatBitWidth();
229
230 SmallVector<OpFoldResult> sizes = op.getMixedSizes();
231
232 int64_t staticOffset;
233 SmallVector<int64_t> staticStrides;
234 if (failed(memrefType.getStridesAndOffset(staticStrides, staticOffset)))
235 return failure();
236 if (staticOffset == ShapedType::kDynamic)
237 return rewriter.notifyMatchFailure(op, "dynamic offset not supported");
238 SmallVector<OpFoldResult> strides;
239 strides.reserve(N: staticStrides.size());
240 for (int64_t stride : staticStrides) {
241 if (stride == ShapedType::kDynamic)
242 return rewriter.notifyMatchFailure(op,
243 "dynamic stride cannot be computed");
244 strides.push_back(Elt: rewriter.getIndexAttr(value: stride));
245 }
246
247 // Compute the linearized flat extent from sizes and strides (no SSA ops
248 // referencing op.result are created here).
249 memref::LinearizedMemRefInfo linearizedInfo;
250 OpFoldResult linearizedOffset;
251 std::tie(args&: linearizedInfo, args&: linearizedOffset) =
252 memref::getLinearizedMemRefOffsetAndSize(
253 builder&: rewriter, loc, srcBits: elemBitWidth, dstBits: elemBitWidth, offset: rewriter.getIndexAttr(value: 0),
254 sizes, strides);
255 (void)linearizedOffset;
256
257 // The total allocation must cover [0, staticOffset + linearizedExtent).
258 // When the offset is non-zero, add it to the computed extent so that the
259 // buffer is large enough for elements accessed at positions
260 // [staticOffset, staticOffset + linearizedExtent).
261 OpFoldResult flatSizeOfr = linearizedInfo.linearizedSize;
262 if (staticOffset != 0) {
263 AffineExpr s0;
264 bindSymbols(ctx: rewriter.getContext(), exprs&: s0);
265 flatSizeOfr = affine::makeComposedFoldedAffineApply(
266 b&: rewriter, loc, expr: s0 + staticOffset, operands: {flatSizeOfr});
267 }
268
269 // Build the flat 1-D MemRefType. The linearized size may be static or
270 // dynamic (OpFoldResult of either IntegerAttr or a Value).
271 int64_t flatDimSize = ShapedType::kDynamic;
272 if (auto attr = dyn_cast<Attribute>(Val&: flatSizeOfr))
273 if (auto intAttr = dyn_cast<IntegerAttr>(Val&: attr))
274 flatDimSize = intAttr.getInt();
275
276 auto flatMemrefType =
277 MemRefType::get({flatDimSize}, memrefType.getElementType(),
278 StridedLayoutAttr::get(context: rewriter.getContext(), offset: 0, strides: {1}),
279 memrefType.getMemorySpace());
280
281 // Collect the flat dynamic-size operand (empty for fully-static case).
282 SmallVector<Value, 1> dynSizes;
283 if (flatDimSize == ShapedType::kDynamic)
284 dynSizes.push_back(Elt: getValueFromOpFoldResult(rewriter, loc, in: flatSizeOfr));
285
286 auto newOp = AllocLikeOp::create(rewriter, loc, flatMemrefType, dynSizes,
287 op.getAlignmentAttr());
288 rewriter.replaceOpWithNewOp<memref::ReinterpretCastOp>(
289 op, cast<MemRefType>(op.getType()), newOp,
290 rewriter.getIndexAttr(value: staticOffset), sizes, strides);
291 return success();
292 }
293};
294
295/// Pattern that flattens any IndexedAccessOpInterface op.
296struct IndexedAccessOpFlattenPattern final
297 : public OpInterfaceRewritePattern<memref::IndexedAccessOpInterface> {
298 using Base::Base;
299
300 LogicalResult matchAndRewrite(memref::IndexedAccessOpInterface op,
301 PatternRewriter &rewriter) const override {
302 TypedValue<MemRefType> memref = op.getAccessedMemref();
303 if (!memref)
304 return rewriter.notifyMatchFailure(arg&: op, msg: "not accessing a memref");
305 if (failed(Result: checkFlattenableMemref(op, memref, rewriter)))
306 return failure();
307 if (failed(Result: canLinearizeAccessedShape(op, memref, rewriter)))
308 return failure();
309
310 auto [flatMemref, offset] = getFlattenMemrefAndOffset(
311 rewriter, loc: op->getLoc(), source: memref, indices: op.getIndices());
312 std::optional<SmallVector<Value>> replacementValues =
313 op.updateMemrefAndIndices(rewriter, newMemref: flatMemref, newIndices: ValueRange{offset});
314 if (replacementValues)
315 rewriter.replaceOp(op, newValues: *replacementValues);
316 return success();
317 }
318};
319
320/// Flatten operations that use VectorTransferOpInterface. Transfer ops have
321/// permutation-map and in_bounds semantics that are separate from
322/// IndexedAccessOpInterface, so use updateStartingPosition directly.
323struct VectorTransferOpFlattenPattern final
324 : public OpInterfaceRewritePattern<VectorTransferOpInterface> {
325 using Base::Base;
326
327 LogicalResult matchAndRewrite(VectorTransferOpInterface op,
328 PatternRewriter &rewriter) const override {
329 auto memref = dyn_cast<TypedValue<MemRefType>>(Val: op.getBase());
330 if (!memref)
331 return rewriter.notifyMatchFailure(arg&: op, msg: "not accessing a memref");
332 if (failed(Result: checkFlattenableMemref(op, memref, rewriter)))
333 return failure();
334 if (failed(Result: canFlattenTransferOp(op, memref, rewriter)))
335 return failure();
336
337 FailureOr<MemRefType> flatMemrefType =
338 getFlattenedMemRefType(sourceType: memref.getType());
339 if (failed(Result: flatMemrefType))
340 return failure();
341 AffineMap newPermutationMap = AffineMap::getMinorIdentityMap(
342 /*dims=*/1, results: op.getTransferRank(), context: op.getContext());
343 if (failed(
344 Result: op.mayUpdateStartingPosition(newBaseType: *flatMemrefType, newPermutationMap)))
345 return rewriter.notifyMatchFailure(arg&: op,
346 msg: "failed op-specific preconditions");
347
348 auto [flatMemref, offset] = getFlattenMemrefAndOffset(
349 rewriter, loc: op->getLoc(), source: memref, indices: op.getIndices());
350 op.updateStartingPosition(rewriter, newBase: flatMemref, newIndices: ValueRange{offset},
351 newPermutationMap: AffineMapAttr::get(value: newPermutationMap));
352 return success();
353 }
354};
355
356/// Flatten the source and destination memref/index pairs of indexed memcpy-like
357/// operations such as memref.dma_start.
358struct FlattenedMemrefAccess {
359 Value memref;
360 Value index;
361};
362
363/// Flatten all IndexedMemCopyOpInterface operations.
364struct IndexedMemCopyOpFlattenPattern final
365 : public OpInterfaceRewritePattern<memref::IndexedMemCopyOpInterface> {
366 using Base::Base;
367
368 LogicalResult matchAndRewrite(memref::IndexedMemCopyOpInterface op,
369 PatternRewriter &rewriter) const override {
370 TypedValue<MemRefType> src = op.getSrc();
371 TypedValue<MemRefType> dst = op.getDst();
372 if (!src && !dst)
373 return rewriter.notifyMatchFailure(arg&: op, msg: "not copying between memrefs");
374
375 auto tryFlatten =
376 [&](TypedValue<MemRefType> memref,
377 ValueRange indices) -> std::optional<FlattenedMemrefAccess> {
378 if (!memref || !needFlattening(val: memref))
379 return std::nullopt;
380 if (failed(Result: checkFlattenableMemref(op, memref, rewriter)))
381 return std::nullopt;
382
383 auto [flatMemref, offset] =
384 getFlattenMemrefAndOffset(rewriter, loc: op->getLoc(), source: memref, indices);
385 return FlattenedMemrefAccess{.memref: flatMemref, .index: offset};
386 };
387
388 std::optional<FlattenedMemrefAccess> newSrc =
389 tryFlatten(src, op.getSrcIndices());
390 std::optional<FlattenedMemrefAccess> newDst =
391 tryFlatten(dst, op.getDstIndices());
392 if (!newSrc && !newDst)
393 return rewriter.notifyMatchFailure(
394 arg&: op, msg: "no source or destination memref needed flattening");
395
396 Value srcMemref = src;
397 ValueRange srcIndices = op.getSrcIndices();
398 if (newSrc) {
399 srcMemref = newSrc->memref;
400 srcIndices = ValueRange(newSrc->index);
401 }
402
403 Value dstMemref = dst;
404 ValueRange dstIndices = op.getDstIndices();
405 if (newDst) {
406 dstMemref = newDst->memref;
407 dstIndices = ValueRange(newDst->index);
408 }
409
410 op.setMemrefsAndIndices(rewriter, newSrc: srcMemref, newSrcIndices: srcIndices, newDst: dstMemref,
411 newDstIndices: dstIndices);
412 return success();
413 }
414};
415
416struct FlattenMemrefsPass
417 : public mlir::memref::impl::FlattenMemrefsPassBase<FlattenMemrefsPass> {
418 using Base::Base;
419
420 void getDependentDialects(DialectRegistry &registry) const override {
421 registry.insert<affine::AffineDialect, arith::ArithDialect,
422 memref::MemRefDialect>();
423 }
424
425 void runOnOperation() override {
426 RewritePatternSet patterns(&getContext());
427
428 memref::populateFlattenMemrefsPatterns(patterns);
429
430 if (failed(Result: applyPatternsGreedily(op: getOperation(), patterns: std::move(patterns))))
431 return signalPassFailure();
432 }
433};
434
435} // namespace
436
437void memref::populateFlattenMemrefsPatterns(RewritePatternSet &patterns) {
438 patterns.insert<IndexedAccessOpFlattenPattern, IndexedMemCopyOpFlattenPattern,
439 VectorTransferOpFlattenPattern,
440 AllocLikeFlattenPattern<memref::AllocOp>,
441 AllocLikeFlattenPattern<memref::AllocaOp>>(
442 arg: patterns.getContext());
443}
444