1//===- MemorySlotInterfacesImpl.cpp - Mem2Reg for MemRef 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// External-model-based implementation of Memory Slot Interfaces for MemRef Ops.
10//
11// This file implements memory slot interface models used by Mem2Reg to promote
12// a memref to a single vector SSA value. `PromotableMemOpInterface` handles
13// `memref.copy`. `PromotableAliaserInterface` exposes `memref.subview` aliases,
14// and `PromotableOpInterface` removes the subviews after promotion. Vector
15// transfer ops are handled by the models in the Vector dialect.
16//
17// A memory slot pairs a memref with the vector type used to represent its
18// contents. Promotion replaces accesses to the slot with uses and definitions
19// of that vector value. All uses, including those through subviews, must be
20// supported by the models.
21//
22// The accesses are rewritten as follows:
23//
24// * A `memref.copy` into the slot becomes a `vector.transfer_read` of the
25// source. A copy out of the slot becomes a `vector.transfer_write` to the
26// target. A copy between two slots is rewritten one slot at a time.
27//
28// * A same-rank, unit-stride `memref.subview` gets an alias slot that is
29// promoted together with the parent:
30//
31// - A static subview holds the corresponding sub-vector. Reads extract it
32// with `vector.extract_strided_slice`; writes update the parent with
33// `vector.insert_strided_slice`.
34//
35// - A dynamic subview holds the whole parent vector because vector shapes
36// must be static. `vector.create_mask` and `arith.select` restrict
37// accesses to the subview's extent. The subview must start at the
38// parent's origin.
39//
40// Copies and subviews require a statically shaped parent buffer. A dynamically
41// shaped buffer can instead promote to a 1-D scalable vector through
42// whole-buffer transfers, but copies and subviews are not supported.
43//
44// Unsupported accesses, such as dynamic subview offsets, rank reduction,
45// non-unit subview strides, or non-zero transfer indices, prevent promotion.
46//
47//===----------------------------------------------------------------------===//
48
49#include "mlir/Dialect/MemRef/Transforms/MemorySlotInterfacesImpl.h"
50
51#include "mlir/Dialect/Arith/Utils/Utils.h"
52#include "mlir/Dialect/MemRef/IR/MemRef.h"
53#include "mlir/Dialect/MemRef/IR/MemRefDialect.h"
54#include "mlir/Dialect/Vector/IR/VectorOps.h"
55#include "mlir/Dialect/Vector/Utils/VectorUtils.h"
56#include "mlir/Interfaces/MemorySlotInterfaces.h"
57
58using namespace mlir;
59using namespace mlir::memref;
60using namespace mlir::vector;
61
62//===----------------------------------------------------------------------===//
63// Utilities
64//===----------------------------------------------------------------------===//
65
66/// Checks the requirements shared by static and dynamic subview aliases: a
67/// parent with a static shape and a valid vector element type, no rank
68/// reduction, and unit slice strides.
69static bool isUnitStrideSliceOfStaticParent(memref::SubViewOp subView) {
70 MemRefType srcType = subView.getSourceType();
71 // vector requires a static parent shape.
72 if (!srcType.hasStaticShape())
73 return false;
74
75 // implementation limitation: vector.extract_strided_slice must have the same
76 // rank (static). Alternative vector.extract could be used but only drop
77 // leading dimensions.
78 if (srcType.getRank() != subView.getType().getRank())
79 return false;
80
81 // No straightforward mapping to vector code for non-unit stride slices.
82 if (!subView.hasUnitStride())
83 return false;
84
85 return VectorType::isValidElementType(t: srcType.getElementType());
86}
87
88/// Returns whether static `subView` can alias a slice of the parent vector
89/// using `vector.extract_strided_slice` and `vector.insert_strided_slice`.
90/// Requires static source and result shapes, constant offsets, unit strides,
91/// and no rank reduction.
92static bool isAliasableStaticShapeSubView(memref::SubViewOp subView) {
93 if (!subView.getType().hasStaticShape())
94 return false;
95
96 if (!isUnitStrideSliceOfStaticParent(subView))
97 return false;
98
99 // extract/insert_strided_slice requires all offsets to be constant.
100 return llvm::all_of(Range: subView.getMixedOffsets(), P: [](OpFoldResult offset) {
101 return getConstantIntValue(ofr: offset).has_value();
102 });
103}
104
105/// Returns whether dynamic `subView` can alias the whole parent vector. The
106/// alias uses the parent vector's shape because vector dimensions cannot be
107/// dynamic. Requires a static source shape, a dynamic result shape, zero
108/// offsets, unit strides, and no rank reduction.
109static bool isAliasableDynamicShapeSubView(memref::SubViewOp subView) {
110 if (subView.getType().hasStaticShape())
111 return false;
112
113 if (!isUnitStrideSliceOfStaticParent(subView))
114 return false;
115
116 /// TODO: Allow non-zero offsets by improving buildSubViewMask().
117 return subView.hasZeroOffset();
118}
119
120/// Returns the static offsets of `subView` within the parent vector for
121/// `vector.extract_strided_slice` and `vector.insert_strided_slice`.
122static SmallVector<int64_t> getStaticSubViewOffsets(memref::SubViewOp subView) {
123 SmallVector<int64_t> offsets;
124 for (OpFoldResult offset : subView.getMixedOffsets()) {
125 std::optional<int64_t> value = getConstantIntValue(ofr: offset);
126 assert(value && "expected a static offset");
127 offsets.push_back(Elt: *value);
128 }
129 return offsets;
130}
131
132/// The vector type covering `subView`'s whole parent buffer, which is the type
133/// the alias slot of a dynamically-shaped subview takes.
134static VectorType getWholeParentVectorType(memref::SubViewOp subView) {
135 auto parentType = cast<MemRefType>(Val: subView.getSource().getType());
136 assert(parentType.hasStaticShape() && "expected a statically-shaped parent");
137 return VectorType::get(shape: parentType.getShape(), elementType: parentType.getElementType());
138}
139
140/// Builds the mask of `subView`'s valid region: a `vector.create_mask` of the
141/// subview's sizes, in the shape of the whole parent that its alias holds.
142static Value buildSubViewMask(OpBuilder &builder, Location loc,
143 memref::SubViewOp subView) {
144 VectorType parentVecType = getWholeParentVectorType(subView);
145 SmallVector<Value> bounds =
146 getValueOrCreateConstantIndexOp(b&: builder, loc, valueOrAttrVec: subView.getMixedSizes());
147 return vector::CreateMaskOp::create(
148 builder, location: loc,
149 resultType0: VectorType::get(shape: parentVecType.getShape(), elementType: builder.getI1Type()), mask_dim_sizes: bounds);
150}
151
152//===----------------------------------------------------------------------===//
153// PromotableMemOpInterface model for memref.copy
154//===----------------------------------------------------------------------===//
155namespace {
156/// `PromotableMemOpInterface` model for `memref.copy`.
157///
158/// A copy into the slot becomes a `vector.transfer_read` of the source in
159/// `getStored`. A copy out of the slot becomes a `vector.transfer_write` of the
160/// reaching definition in `removeBlockingUses`.
161///
162/// A copy between two slots is rewritten one slot at a time, in either order.
163/// For dynamic subviews,
164/// `PromotableAliaserInterface::projectAliasValueToSlotValue` masks writes into
165/// the slot.
166struct CopyOpMemOpModel
167 : public PromotableMemOpInterface::ExternalModel<CopyOpMemOpModel,
168 memref::CopyOp> {
169 bool loadsFrom(Operation *op, const MemorySlot &slot) const {
170 return cast<memref::CopyOp>(Val: op).getSource() == slot.ptr;
171 }
172
173 bool storesTo(Operation *op, const MemorySlot &slot) const {
174 return cast<memref::CopyOp>(Val: op).getTarget() == slot.ptr;
175 }
176
177 // Promotion replaces the slot with a vector value, so a copy into the slot
178 // becomes the code producing that value: a read of the copy's source.
179 Value getStored(Operation *op, const MemorySlot &slot, OpBuilder &builder,
180 Value /*reachingDef*/, const DataLayout &dataLayout) const {
181 auto copyOp = cast<memref::CopyOp>(Val: op);
182 return vector::createReadOrMaskedRead(builder, loc: op->getLoc(),
183 source: copyOp.getSource(),
184 vecToReadTy: cast<VectorType>(Val: slot.valueType));
185 }
186
187 bool canUsesBeRemoved(Operation *op, const MemorySlot &slot,
188 const SmallPtrSetImpl<OpOperand *> &blockingUses,
189 SmallVectorImpl<OpOperand *> &newBlockingUses,
190 const DataLayout &dataLayout) const {
191 auto copyOp = cast<memref::CopyOp>(Val: op);
192 auto vecType = dyn_cast<VectorType>(Val: slot.valueType);
193 if (!vecType || vecType.isScalable())
194 return false;
195 bool srcIsSlot = copyOp.getSource() == slot.ptr;
196 bool dstIsSlot = copyOp.getTarget() == slot.ptr;
197 // Exactly one side must be this slot. A self-copy (both sides the slot) is
198 // not modeled here.
199 if (srcIsSlot == dstIsSlot)
200 return false;
201 // No further check: `memref.copy` requires both operands to have the same
202 // element type and runtime shape; a shape mismatch is undefined behavior.
203 return true;
204 }
205
206 // A copy out of the slot is a use of the slot's vector value: it becomes a
207 // `vector.transfer_write` of that value into the copy's target.
208 DeletionKind
209 removeBlockingUses(Operation *op, const MemorySlot &slot,
210 const SmallPtrSetImpl<OpOperand *> &blockingUses,
211 OpBuilder &builder, Value reachingDefinition,
212 const DataLayout &dataLayout) const {
213 auto copyOp = cast<memref::CopyOp>(Val: op);
214 if (copyOp.getSource() == slot.ptr)
215 vector::createWriteOrMaskedWrite(builder, loc: op->getLoc(),
216 vecToStore: reachingDefinition, dest: copyOp.getTarget());
217 return DeletionKind::Delete;
218 }
219};
220
221//===----------------------------------------------------------------------===//
222// PromotableOpInterface model for memref.subview
223//===----------------------------------------------------------------------===//
224
225/// `PromotableOpInterface` model for `memref.subview`. Works with the
226/// `PromotableAliaserInterface` model below to remove the subview once its
227/// result's uses have been promoted.
228struct SubViewOpPromotableModel
229 : public PromotableOpInterface::ExternalModel<SubViewOpPromotableModel,
230 memref::SubViewOp> {
231 bool canUsesBeRemoved(Operation *op,
232 const SmallPtrSetImpl<OpOperand *> &blockingUses,
233 SmallVectorImpl<OpOperand *> &newBlockingUses,
234 const DataLayout &dataLayout) const {
235 // Removing the subview requires removing all uses of its memref result.
236 for (OpOperand &use : op->getResult(idx: 0).getUses())
237 newBlockingUses.push_back(Elt: &use);
238 return true;
239 }
240
241 DeletionKind
242 removeBlockingUses(Operation *op,
243 const SmallPtrSetImpl<OpOperand *> &blockingUses,
244 OpBuilder &builder) const {
245 return DeletionKind::Delete;
246 }
247};
248
249//===----------------------------------------------------------------------===//
250// PromotableAliaserInterface model for memref.subview
251//===----------------------------------------------------------------------===//
252
253/// `PromotableAliaserInterface` model exposing a same-rank `memref.subview` as
254/// an alias of a vector slot.
255///
256/// `projectSlotValueToAliasValue` provides the alias value for loads and for a
257/// store's `getStored` hook. `projectAliasValueToSlotValue` merges the stored
258/// alias value back into the parent.
259///
260/// Static subviews use `vector.extract_strided_slice` and
261/// `vector.insert_strided_slice`. Dynamic subviews keep the whole parent
262/// vector: loads use it directly, and stores use `arith.select` with a mask of
263/// the subview's sizes to preserve the parent value outside the subview.
264struct SubViewOpAliasModel
265 : public PromotableAliaserInterface::ExternalModel<SubViewOpAliasModel,
266 memref::SubViewOp> {
267 void getPromotableSlotAliases(Operation *op,
268 OpOperand &aliasedSlotPointerOperand,
269 const MemorySlot &parentSlot,
270 SmallVectorImpl<MemorySlot> &newSlots) const {
271 auto subView = cast<memref::SubViewOp>(Val: op);
272 // Called once per operand holding the slot pointer; only the viewed source
273 // exposes an alias.
274 if (aliasedSlotPointerOperand.get() != subView.getSource())
275 return;
276
277 // The parent slot must promote to a vector. A scalar (single-element)
278 // parent slot cannot be sliced.
279 auto parentVecType = dyn_cast<VectorType>(Val: parentSlot.valueType);
280 if (!parentVecType)
281 return;
282
283 // A static slice aliases the sub-vector matching the subview's shape.
284 if (isAliasableStaticShapeSubView(subView)) {
285 auto resType = cast<MemRefType>(Val: subView.getResult().getType());
286 VectorType aliasVecType =
287 VectorType::get(shape: resType.getShape(), elementType: resType.getElementType());
288 newSlots.push_back(Elt: MemorySlot{.ptr: subView.getResult(), .valueType: aliasVecType});
289 }
290
291 // A dynamic slice aliases the whole parent value.
292 if (isAliasableDynamicShapeSubView(subView)) {
293 newSlots.push_back(Elt: MemorySlot{.ptr: subView.getResult(), .valueType: parentVecType});
294 }
295 }
296
297 Value projectSlotValueToAliasValue(Operation *op,
298 OpOperand & /*aliasedSlotPointerOperand*/,
299 const MemorySlot & /*parentSlot*/,
300 const MemorySlot &aliasSlot,
301 Value slotValue,
302 OpBuilder &builder) const {
303 auto subView = cast<memref::SubViewOp>(Val: op);
304 // Identity: the alias holds the whole parent value. Lanes past the
305 // subview's extent are expected to be masked off by the consuming read.
306 if (isAliasableDynamicShapeSubView(subView))
307 return slotValue;
308
309 SmallVector<int64_t> offsets = getStaticSubViewOffsets(subView);
310 auto aliasVecType = cast<VectorType>(Val: aliasSlot.valueType);
311 SmallVector<int64_t> strides(offsets.size(), 1);
312 return vector::ExtractStridedSliceOp::create(
313 builder, location: op->getLoc(), source: slotValue, offsets,
314 sizes: aliasVecType.getShape(), strides)
315 .getResult();
316 }
317
318 Value projectAliasValueToSlotValue(Operation *op,
319 OpOperand & /*aliasedSlotPointerOperand*/,
320 const MemorySlot & /*parentSlot*/,
321 const MemorySlot & /*aliasSlot*/,
322 Value aliasValue, Value reachingDef,
323 OpBuilder &builder) const {
324 auto subView = cast<memref::SubViewOp>(Val: op);
325 // Compose the stored value over the subview's extent only, leaving the rest
326 // of the parent value untouched.
327 if (isAliasableDynamicShapeSubView(subView)) {
328 Location loc = op->getLoc();
329 Value mask = buildSubViewMask(builder, loc, subView);
330 return arith::SelectOp::create(builder, location: loc, condition: mask, true_value: aliasValue,
331 false_value: reachingDef);
332 }
333
334 SmallVector<int64_t> offsets = getStaticSubViewOffsets(subView);
335 SmallVector<int64_t> strides(offsets.size(), 1);
336 return vector::InsertStridedSliceOp::create(
337 builder, location: op->getLoc(), valueToStore: aliasValue, dest: reachingDef, offsets, strides)
338 .getResult();
339 }
340};
341} // namespace
342
343//===----------------------------------------------------------------------===//
344// Register external models
345//===----------------------------------------------------------------------===//
346
347void mlir::memref::registerMemorySlotInterfacesExternalModels(
348 DialectRegistry &registry) {
349 registry.addExtension(extensionFn: +[](MLIRContext *ctx, memref::MemRefDialect *dialect) {
350 memref::SubViewOp::attachInterface<SubViewOpAliasModel>(context&: *ctx);
351 memref::SubViewOp::attachInterface<SubViewOpPromotableModel>(context&: *ctx);
352 memref::CopyOp::attachInterface<CopyOpMemOpModel>(context&: *ctx);
353 });
354}
355