1//===- MemorySlotInterfacesImpl.cpp - Memory Slot Interfaces ----*- C++ -*-===//
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// Implementation of Memory Slot Interfaces for MemRef Ops.
10//
11// This file also implements DestructurableTypeInterface for MemRefType that is
12// required for some of the interfaces implemented here. This particular
13// interface is added as an external model - otherwise we would need to add it
14// to the MemRef builtin type and make the builtin dialect depend on
15// `DestructurableTypeInterface`.
16//
17//===----------------------------------------------------------------------===//
18
19#include "mlir/Dialect/MemRef/IR/MemorySlotInterfacesImpl.h"
20#include "mlir/Dialect/Arith/IR/Arith.h"
21#include "mlir/Dialect/MemRef/IR/MemRef.h"
22#include "mlir/Dialect/UB/IR/UBOps.h"
23#include "mlir/Dialect/Utils/StaticValueUtils.h"
24#include "mlir/IR/BuiltinDialect.h"
25#include "mlir/IR/BuiltinTypes.h"
26#include "mlir/IR/Matchers.h"
27#include "mlir/IR/Value.h"
28#include "mlir/Interfaces/MemorySlotInterfaces.h"
29#include "llvm/ADT/ArrayRef.h"
30#include "llvm/ADT/TypeSwitch.h"
31#include "llvm/Support/ErrorHandling.h"
32
33using namespace mlir;
34
35//===----------------------------------------------------------------------===//
36// Utilities
37//===----------------------------------------------------------------------===//
38
39/// Walks over the indices of the elements of a tensor of a given `shape` by
40/// updating `index` in place to the next index. This returns failure if the
41/// provided index was the last index.
42static LogicalResult nextIndex(ArrayRef<int64_t> shape,
43 MutableArrayRef<int64_t> index) {
44 for (size_t i = 0; i < shape.size(); ++i) {
45 index[i]++;
46 if (index[i] < shape[i])
47 return success();
48 index[i] = 0;
49 }
50 return failure();
51}
52
53/// Calls `walker` for each index within a tensor of a given `shape`, providing
54/// the index as an array attribute of the coordinates.
55template <typename CallableT>
56static void walkIndicesAsAttr(MLIRContext *ctx, ArrayRef<int64_t> shape,
57 CallableT &&walker) {
58 Type indexType = IndexType::get(context: ctx);
59 SmallVector<int64_t> shapeIter(shape.size(), 0);
60 do {
61 SmallVector<Attribute> indexAsAttr;
62 for (int64_t dim : shapeIter)
63 indexAsAttr.push_back(Elt: IntegerAttr::get(type: indexType, value: dim));
64 walker(ArrayAttr::get(context: ctx, value: indexAsAttr));
65 } while (succeeded(Result: nextIndex(shape, index: shapeIter)));
66}
67
68/// Returns the index of a memref in attribute form, given its indices. Returns
69/// a null pointer if whether the indices form a valid index for the provided
70/// MemRefType cannot be computed. The indices must come from a valid memref
71/// StoreOp or LoadOp.
72static Attribute getAttributeIndexFromIndexOperands(MLIRContext *ctx,
73 ValueRange indices,
74 MemRefType memrefType) {
75 SmallVector<Attribute> index;
76 for (auto [coord, dimSize] : llvm::zip(t&: indices, u: memrefType.getShape())) {
77 IntegerAttr coordAttr;
78 if (!matchPattern(value: coord, pattern: m_Constant<IntegerAttr>(bind_value: &coordAttr)))
79 return {};
80 // MemRefType shape dimensions are always positive (checked by verifier).
81 std::optional<uint64_t> coordInt = coordAttr.getValue().tryZExtValue();
82 if (!coordInt || coordInt.value() >= static_cast<uint64_t>(dimSize))
83 return {};
84 index.push_back(Elt: coordAttr);
85 }
86 return ArrayAttr::get(context: ctx, value: index);
87}
88
89//===----------------------------------------------------------------------===//
90// AllocaOp: PromotableAllocationOpInterface
91//===----------------------------------------------------------------------===//
92/// Returns the scalable vector width a `vscale`-sized memref maps to: the
93/// factor C when `size` is a known multiple of `vscale`.
94static std::optional<int64_t> matchVScaleMultiple(Value size) {
95 Operation *defOp = size.getDefiningOp();
96 if (!defOp)
97 return std::nullopt;
98
99 auto isVScale = [](Value v) {
100 Operation *op = v.getDefiningOp();
101 // Matched by name to avoid a MemRef -> Vector circular dependency, as in
102 // arith::MulIOp::getAsmResultNames.
103 return op && op->getName().getStringRef() == "vector.vscale";
104 };
105
106 // Bare `vector.vscale` == vscale * 1.
107 if (isVScale(size))
108 return 1;
109
110 // `vscale * C` or `C * vscale` (multiplication is commutative).
111 if (auto mul = dyn_cast<arith::MulIOp>(Val: defOp)) {
112 if (isVScale(mul.getLhs()))
113 return getConstantIntValue(ofr: mul.getRhs());
114 if (isVScale(mul.getRhs()))
115 return getConstantIntValue(ofr: mul.getLhs());
116 }
117 return std::nullopt;
118}
119
120SmallVector<MemorySlot> memref::AllocaOp::getPromotableSlots() {
121 MemRefType type = getType();
122
123 // A single-element memref is promoted to a scalar SSA value.
124 if (type.hasStaticShape()) {
125 std::optional<int64_t> numElements =
126 ShapedType::tryGetNumElements(shape: type.getShape());
127 // Element count overflow: not promotable.
128 if (!numElements)
129 return {};
130 if (*numElements == 1)
131 return {MemorySlot{.ptr: getResult(), .valueType: type.getElementType()}};
132 }
133
134 // A multi-element memref can be promoted to a single vector SSA value when it
135 // is only ever accessed as a whole buffer (e.g. through whole-buffer
136 // `vector.transfer_read`/`vector.transfer_write`).
137 if (VectorType::isValidElementType(t: type.getElementType())) {
138 // Vector types require strictly positive extents, so a memref with a zero
139 // extent has nothing to promote.
140 if (llvm::is_contained(Range: type.getShape(), Element: 0))
141 return {};
142
143 // Static shape: a fixed-size vector of the same extents.
144 if (type.hasStaticShape())
145 return {MemorySlot{.ptr: getResult(), .valueType: VectorType::get(shape: type.getShape(),
146 elementType: type.getElementType())}};
147
148 // A 1-D memref whose single dynamic extent is `vector.vscale * N` maps to a
149 // scalable `vector<[N]x...>` slot, for a strictly positive multiple `N`.
150 if (type.getRank() == 1 && type.isDynamicDim(idx: 0)) {
151 if (std::optional<int64_t> multiple =
152 matchVScaleMultiple(size: getDynamicSizes()[0]);
153 multiple && *multiple > 0)
154 return {MemorySlot{.ptr: getResult(),
155 .valueType: VectorType::get(shape: {*multiple}, elementType: type.getElementType(),
156 /*scalableDims=*/{true})}};
157 }
158 }
159
160 return {};
161}
162
163Value memref::AllocaOp::getDefaultValue(const MemorySlot &slot,
164 OpBuilder &builder) {
165 return ub::PoisonOp::create(builder, location: getLoc(), result: slot.valueType);
166}
167
168std::optional<PromotableAllocationOpInterface>
169memref::AllocaOp::handlePromotionComplete(const MemorySlot &slot,
170 Value defaultValue,
171 OpBuilder &builder) {
172 if (defaultValue && defaultValue.use_empty())
173 defaultValue.getDefiningOp()->erase();
174 this->erase();
175 return std::nullopt;
176}
177
178//===----------------------------------------------------------------------===//
179// AllocaOp: DestructurableAllocationOpInterface
180//===----------------------------------------------------------------------===//
181void memref::AllocaOp::handleBlockArgument(const MemorySlot &slot,
182 BlockArgument argument,
183 OpBuilder &builder) {}
184
185SmallVector<DestructurableMemorySlot>
186memref::AllocaOp::getDestructurableSlots() {
187 MemRefType memrefType = getType();
188 auto destructurable = llvm::dyn_cast<DestructurableTypeInterface>(Val&: memrefType);
189 if (!destructurable)
190 return {};
191
192 std::optional<DenseMap<Attribute, Type>> destructuredType =
193 destructurable.getSubelementIndexMap();
194 if (!destructuredType)
195 return {};
196
197 return {
198 DestructurableMemorySlot{{.ptr: getMemref(), .valueType: memrefType}, .subelementTypes: *destructuredType}};
199}
200
201DenseMap<Attribute, MemorySlot> memref::AllocaOp::destructure(
202 const DestructurableMemorySlot &slot,
203 const SmallPtrSetImpl<Attribute> &usedIndices, OpBuilder &builder,
204 SmallVectorImpl<DestructurableAllocationOpInterface> &newAllocators) {
205 builder.setInsertionPointAfter(*this);
206
207 DenseMap<Attribute, MemorySlot> slotMap;
208
209 auto memrefType = llvm::cast<DestructurableTypeInterface>(Val: getType());
210 for (Attribute usedIndex : usedIndices) {
211 Type elemType = memrefType.getTypeAtIndex(index: usedIndex);
212 MemRefType elemPtr = MemRefType::get(shape: {}, elementType: elemType);
213 auto subAlloca = memref::AllocaOp::create(builder, location: getLoc(), memrefType: elemPtr);
214 newAllocators.push_back(Elt: subAlloca);
215 slotMap.try_emplace<MemorySlot>(Key: usedIndex,
216 Args: {.ptr: subAlloca.getResult(), .valueType: elemType});
217 }
218
219 return slotMap;
220}
221
222std::optional<DestructurableAllocationOpInterface>
223memref::AllocaOp::handleDestructuringComplete(
224 const DestructurableMemorySlot &slot, OpBuilder &builder) {
225 assert(slot.ptr == getResult());
226 this->erase();
227 return std::nullopt;
228}
229
230//===----------------------------------------------------------------------===//
231// LoadOp: PromotableMemOpInterface
232//===----------------------------------------------------------------------===//
233bool memref::LoadOp::loadsFrom(const MemorySlot &slot) {
234 return getMemRef() == slot.ptr;
235}
236
237bool memref::LoadOp::storesTo(const MemorySlot &slot) { return false; }
238
239Value memref::LoadOp::getStored(const MemorySlot &slot, OpBuilder &builder,
240 Value reachingDef,
241 const DataLayout &dataLayout) {
242 llvm_unreachable("getStored should not be called on LoadOp");
243}
244
245bool memref::LoadOp::canUsesBeRemoved(
246 const MemorySlot &slot, const SmallPtrSetImpl<OpOperand *> &blockingUses,
247 SmallVectorImpl<OpOperand *> &newBlockingUses,
248 const DataLayout &dataLayout) {
249 if (blockingUses.size() != 1)
250 return false;
251 Value blockingUse = (*blockingUses.begin())->get();
252 return blockingUse == slot.ptr && getMemRef() == slot.ptr &&
253 getResult().getType() == slot.valueType;
254}
255
256DeletionKind memref::LoadOp::removeBlockingUses(
257 const MemorySlot &slot, const SmallPtrSetImpl<OpOperand *> &blockingUses,
258 OpBuilder &builder, Value reachingDefinition,
259 const DataLayout &dataLayout) {
260 // `canUsesBeRemoved` checked this blocking use must be the loaded slot
261 // pointer.
262 getResult().replaceAllUsesWith(newValue: reachingDefinition);
263 return DeletionKind::Delete;
264}
265
266//===----------------------------------------------------------------------===//
267// LoadOp: DestructurableAccessorOpInterface
268//===----------------------------------------------------------------------===//
269bool memref::LoadOp::canRewire(const DestructurableMemorySlot &slot,
270 SmallPtrSetImpl<Attribute> &usedIndices,
271 SmallVectorImpl<MemorySlot> &mustBeSafelyUsed,
272 const DataLayout &dataLayout) {
273 if (slot.ptr != getMemRef())
274 return false;
275 Attribute index = getAttributeIndexFromIndexOperands(
276 ctx: getContext(), indices: getIndices(), memrefType: getMemRefType());
277 if (!index)
278 return false;
279 usedIndices.insert(Ptr: index);
280 return true;
281}
282
283DeletionKind memref::LoadOp::rewire(const DestructurableMemorySlot &slot,
284 DenseMap<Attribute, MemorySlot> &subslots,
285 OpBuilder &builder,
286 const DataLayout &dataLayout) {
287 Attribute index = getAttributeIndexFromIndexOperands(
288 ctx: getContext(), indices: getIndices(), memrefType: getMemRefType());
289 const MemorySlot &memorySlot = subslots.at(Val: index);
290 setMemRef(memorySlot.ptr);
291 getIndicesMutable().clear();
292 return DeletionKind::Keep;
293}
294
295bool memref::StoreOp::loadsFrom(const MemorySlot &slot) { return false; }
296
297bool memref::StoreOp::storesTo(const MemorySlot &slot) {
298 return getMemRef() == slot.ptr;
299}
300
301Value memref::StoreOp::getStored(const MemorySlot &slot, OpBuilder &builder,
302 Value reachingDef,
303 const DataLayout &dataLayout) {
304 return getValue();
305}
306
307//===----------------------------------------------------------------------===//
308// StoreOp: PromotableMemOpInterface
309//===----------------------------------------------------------------------===//
310bool memref::StoreOp::canUsesBeRemoved(
311 const MemorySlot &slot, const SmallPtrSetImpl<OpOperand *> &blockingUses,
312 SmallVectorImpl<OpOperand *> &newBlockingUses,
313 const DataLayout &dataLayout) {
314 if (blockingUses.size() != 1)
315 return false;
316 Value blockingUse = (*blockingUses.begin())->get();
317 return blockingUse == slot.ptr && getMemRef() == slot.ptr &&
318 getValue() != slot.ptr && getValue().getType() == slot.valueType;
319}
320
321DeletionKind memref::StoreOp::removeBlockingUses(
322 const MemorySlot &slot, const SmallPtrSetImpl<OpOperand *> &blockingUses,
323 OpBuilder &builder, Value reachingDefinition,
324 const DataLayout &dataLayout) {
325 return DeletionKind::Delete;
326}
327
328//===----------------------------------------------------------------------===//
329// StoreOp: DestructurableAccessorOpInterface
330//===----------------------------------------------------------------------===//
331bool memref::StoreOp::canRewire(const DestructurableMemorySlot &slot,
332 SmallPtrSetImpl<Attribute> &usedIndices,
333 SmallVectorImpl<MemorySlot> &mustBeSafelyUsed,
334 const DataLayout &dataLayout) {
335 if (slot.ptr != getMemRef() || getValue() == slot.ptr)
336 return false;
337 Attribute index = getAttributeIndexFromIndexOperands(
338 ctx: getContext(), indices: getIndices(), memrefType: getMemRefType());
339 if (!index || !slot.subelementTypes.contains(Val: index))
340 return false;
341 usedIndices.insert(Ptr: index);
342 return true;
343}
344
345DeletionKind memref::StoreOp::rewire(const DestructurableMemorySlot &slot,
346 DenseMap<Attribute, MemorySlot> &subslots,
347 OpBuilder &builder,
348 const DataLayout &dataLayout) {
349 Attribute index = getAttributeIndexFromIndexOperands(
350 ctx: getContext(), indices: getIndices(), memrefType: getMemRefType());
351 const MemorySlot &memorySlot = subslots.at(Val: index);
352 setMemRef(memorySlot.ptr);
353 getIndicesMutable().clear();
354 return DeletionKind::Keep;
355}
356
357//===----------------------------------------------------------------------===//
358// MemRefType: DestructurableTypeInterface
359//===----------------------------------------------------------------------===//
360
361namespace {
362struct MemRefDestructurableTypeExternalModel
363 : public DestructurableTypeInterface::ExternalModel<
364 MemRefDestructurableTypeExternalModel, MemRefType> {
365 std::optional<DenseMap<Attribute, Type>>
366 getSubelementIndexMap(Type type) const {
367 auto memrefType = llvm::cast<MemRefType>(Val&: type);
368 constexpr int64_t maxMemrefSizeForDestructuring = 16;
369 if (!memrefType.hasStaticShape())
370 return {};
371 std::optional<int64_t> numElements =
372 ShapedType::tryGetNumElements(shape: memrefType.getShape());
373 if (!numElements || *numElements > maxMemrefSizeForDestructuring ||
374 *numElements == 1)
375 return {};
376
377 DenseMap<Attribute, Type> destructured;
378 walkIndicesAsAttr(
379 ctx: memrefType.getContext(), shape: memrefType.getShape(), walker: [&](Attribute index) {
380 destructured.insert(KV: {index, memrefType.getElementType()});
381 });
382
383 return destructured;
384 }
385
386 Type getTypeAtIndex(Type type, Attribute index) const {
387 auto memrefType = llvm::cast<MemRefType>(Val&: type);
388 auto coordArrAttr = llvm::dyn_cast<ArrayAttr>(Val&: index);
389 if (!coordArrAttr || coordArrAttr.size() != memrefType.getShape().size())
390 return {};
391
392 Type indexType = IndexType::get(context: memrefType.getContext());
393 for (const auto &[coordAttr, dimSize] :
394 llvm::zip(t&: coordArrAttr, u: memrefType.getShape())) {
395 auto coord = llvm::dyn_cast<IntegerAttr>(Val: coordAttr);
396 if (!coord || coord.getType() != indexType || coord.getInt() < 0 ||
397 coord.getInt() >= dimSize)
398 return {};
399 }
400
401 return memrefType.getElementType();
402 }
403};
404} // namespace
405
406//===----------------------------------------------------------------------===//
407// Register MemRefDestructurableTypeExternalModel
408//===----------------------------------------------------------------------===//
409void mlir::memref::registerDestructurableTypeInterfaceExternalModels(
410 DialectRegistry &registry) {
411 registry.addExtension(extensionFn: +[](MLIRContext *ctx, BuiltinDialect *dialect) {
412 MemRefType::attachInterface<MemRefDestructurableTypeExternalModel>(context&: *ctx);
413 });
414}
415