| 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 | |
| 33 | using 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. |
| 42 | static 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. |
| 55 | template <typename CallableT> |
| 56 | static 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. |
| 72 | static 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`. |
| 94 | static 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 | |
| 120 | SmallVector<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 | |
| 163 | Value memref::AllocaOp::getDefaultValue(const MemorySlot &slot, |
| 164 | OpBuilder &builder) { |
| 165 | return ub::PoisonOp::create(builder, location: getLoc(), result: slot.valueType); |
| 166 | } |
| 167 | |
| 168 | std::optional<PromotableAllocationOpInterface> |
| 169 | memref::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 | //===----------------------------------------------------------------------===// |
| 181 | void memref::AllocaOp::handleBlockArgument(const MemorySlot &slot, |
| 182 | BlockArgument argument, |
| 183 | OpBuilder &builder) {} |
| 184 | |
| 185 | SmallVector<DestructurableMemorySlot> |
| 186 | memref::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 | |
| 201 | DenseMap<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 | |
| 222 | std::optional<DestructurableAllocationOpInterface> |
| 223 | memref::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 | //===----------------------------------------------------------------------===// |
| 233 | bool memref::LoadOp::loadsFrom(const MemorySlot &slot) { |
| 234 | return getMemRef() == slot.ptr; |
| 235 | } |
| 236 | |
| 237 | bool memref::LoadOp::storesTo(const MemorySlot &slot) { return false; } |
| 238 | |
| 239 | Value 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 | |
| 245 | bool 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 | |
| 256 | DeletionKind 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 | //===----------------------------------------------------------------------===// |
| 269 | bool 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 | |
| 283 | DeletionKind 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 | |
| 295 | bool memref::StoreOp::loadsFrom(const MemorySlot &slot) { return false; } |
| 296 | |
| 297 | bool memref::StoreOp::storesTo(const MemorySlot &slot) { |
| 298 | return getMemRef() == slot.ptr; |
| 299 | } |
| 300 | |
| 301 | Value 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 | //===----------------------------------------------------------------------===// |
| 310 | bool 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 | |
| 321 | DeletionKind 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 | //===----------------------------------------------------------------------===// |
| 331 | bool 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 | |
| 345 | DeletionKind 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 | |
| 361 | namespace { |
| 362 | struct 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 | //===----------------------------------------------------------------------===// |
| 409 | void mlir::memref::registerDestructurableTypeInterfaceExternalModels( |
| 410 | DialectRegistry ®istry) { |
| 411 | registry.addExtension(extensionFn: +[](MLIRContext *ctx, BuiltinDialect *dialect) { |
| 412 | MemRefType::attachInterface<MemRefDestructurableTypeExternalModel>(context&: *ctx); |
| 413 | }); |
| 414 | } |
| 415 | |