1//===- MemRefUtils.cpp - Utilities to support the MemRef dialect ----------===//
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 implements utilities for the MemRef dialect.
10//
11//===----------------------------------------------------------------------===//
12
13#include "mlir/Dialect/MemRef/Utils/MemRefUtils.h"
14#include "mlir/Dialect/Affine/IR/AffineOps.h"
15#include "mlir/Dialect/Arith/Utils/Utils.h"
16#include "mlir/Dialect/MemRef/IR/MemRef.h"
17#include "mlir/Interfaces/SideEffectInterfaces.h"
18#include "mlir/Interfaces/ViewLikeInterface.h"
19#include "llvm/ADT/STLExtras.h"
20
21namespace mlir {
22namespace memref {
23
24bool isStaticShapeAndContiguousRowMajor(MemRefType type) {
25 if (!type.hasStaticShape())
26 return false;
27
28 int64_t rank = type.getRank();
29 if (rank == 0)
30 return true;
31
32 SmallVector<int64_t> strides;
33 int64_t offset;
34 if (failed(Result: type.getStridesAndOffset(strides, offset)))
35 return false;
36
37 // MemRef is contiguous if outer dimensions are size-1 and inner
38 // dimensions have unit strides.
39 int64_t runningStride = 1;
40 int64_t curDim = rank - 1;
41 // Finds all inner dimensions with unit strides.
42 while (curDim >= 0 && strides[curDim] == runningStride) {
43 runningStride *= type.getDimSize(idx: curDim);
44 --curDim;
45 }
46
47 // Check if other dimensions are size-1.
48 while (curDim >= 0 && type.getDimSize(idx: curDim) == 1) {
49 --curDim;
50 }
51
52 // All dims are unit-strided or size-1.
53 return curDim < 0;
54}
55
56std::pair<LinearizedMemRefInfo, OpFoldResult> getLinearizedMemRefOffsetAndSize(
57 OpBuilder &builder, Location loc, int srcBits, int dstBits,
58 OpFoldResult offset, ArrayRef<OpFoldResult> sizes,
59 ArrayRef<OpFoldResult> strides, ArrayRef<OpFoldResult> indices,
60 LinearizedDivKind sizeDivKind) {
61 unsigned sourceRank = sizes.size();
62 assert(sizes.size() == strides.size() &&
63 "expected as many sizes as strides for a memref");
64 SmallVector<OpFoldResult> indicesVec = llvm::to_vector(Range&: indices);
65 if (indices.empty())
66 indicesVec.resize(N: sourceRank, NV: builder.getIndexAttr(value: 0));
67 assert(indicesVec.size() == strides.size() &&
68 "expected as many indices as rank of memref");
69
70 // Create the affine symbols and values for linearization.
71 SmallVector<AffineExpr> symbols(2 * sourceRank);
72 bindSymbolsList(ctx: builder.getContext(), exprs: MutableArrayRef{symbols});
73 AffineExpr addMulMap = builder.getAffineConstantExpr(constant: 0);
74
75 SmallVector<OpFoldResult> offsetValues(2 * sourceRank);
76
77 for (unsigned i = 0; i < sourceRank; ++i) {
78 unsigned offsetIdx = 2 * i;
79 addMulMap = addMulMap + symbols[offsetIdx] * symbols[offsetIdx + 1];
80 offsetValues[offsetIdx] = indicesVec[i];
81 offsetValues[offsetIdx + 1] = strides[i];
82 }
83 // Adjust linearizedIndices and size by the scale factor (dstBits / srcBits).
84 int64_t scaler = dstBits / srcBits;
85 OpFoldResult linearizedIndices = affine::makeComposedFoldedAffineApply(
86 b&: builder, loc, expr: addMulMap.floorDiv(v: scaler), operands: offsetValues);
87
88 size_t symbolIndex = 0;
89 SmallVector<OpFoldResult> values;
90 SmallVector<AffineExpr> productExpressions;
91 for (unsigned i = 0; i < sourceRank; ++i) {
92 AffineExpr strideExpr = symbols[symbolIndex++];
93 values.push_back(Elt: strides[i]);
94 AffineExpr sizeExpr = symbols[symbolIndex++];
95 values.push_back(Elt: sizes[i]);
96
97 AffineExpr product = strideExpr * sizeExpr;
98 productExpressions.push_back(Elt: sizeDivKind == LinearizedDivKind::Ceil
99 ? product.ceilDiv(v: scaler)
100 : product.floorDiv(v: scaler));
101 }
102 AffineMap maxMap = AffineMap::get(
103 /*dimCount=*/0, /*symbolCount=*/symbolIndex, results: productExpressions,
104 context: builder.getContext());
105 OpFoldResult linearizedSize =
106 affine::makeComposedFoldedAffineMax(b&: builder, loc, map: maxMap, operands: values);
107
108 // Adjust baseOffset by the scale factor (dstBits / srcBits).
109 AffineExpr s0;
110 bindSymbols(ctx: builder.getContext(), exprs&: s0);
111 OpFoldResult adjustBaseOffset = affine::makeComposedFoldedAffineApply(
112 b&: builder, loc, expr: s0.floorDiv(v: scaler), operands: {offset});
113
114 OpFoldResult intraVectorOffset = affine::makeComposedFoldedAffineApply(
115 b&: builder, loc, expr: addMulMap % scaler, operands: offsetValues);
116
117 return {{.linearizedOffset: adjustBaseOffset, .linearizedSize: linearizedSize, .intraDataOffset: intraVectorOffset},
118 linearizedIndices};
119}
120
121LinearizedMemRefInfo
122getLinearizedMemRefOffsetAndSize(OpBuilder &builder, Location loc, int srcBits,
123 int dstBits, OpFoldResult offset,
124 ArrayRef<OpFoldResult> sizes,
125 LinearizedDivKind sizeDivKind) {
126 SmallVector<OpFoldResult> strides(sizes.size());
127 if (!sizes.empty()) {
128 strides.back() = builder.getIndexAttr(value: 1);
129 AffineExpr s0, s1;
130 bindSymbols(ctx: builder.getContext(), exprs&: s0, exprs&: s1);
131 for (int64_t index = static_cast<int64_t>(sizes.size()) - 1; index > 0;
132 --index) {
133 strides[index - 1] = affine::makeComposedFoldedAffineApply(
134 b&: builder, loc, expr: s0 * s1,
135 operands: ArrayRef<OpFoldResult>{strides[index], sizes[index]});
136 }
137 }
138
139 LinearizedMemRefInfo linearizedMemRefInfo;
140 std::tie(args&: linearizedMemRefInfo, args: std::ignore) =
141 getLinearizedMemRefOffsetAndSize(builder, loc, srcBits, dstBits, offset,
142 sizes, strides, /*indices=*/{},
143 sizeDivKind);
144 return linearizedMemRefInfo;
145}
146
147/// Returns true if all the uses of op are not read/load.
148/// There can be view-like-op users as long as all its users are also
149/// StoreOp/transfer_write. If return true it also fills out the uses, if it
150/// returns false uses is unchanged.
151static bool resultIsNotRead(Operation *op, std::vector<Operation *> &uses) {
152 std::vector<Operation *> opUses;
153 for (OpOperand &use : op->getUses()) {
154 Operation *useOp = use.getOwner();
155 // Use escaped the scope
156 if (useOp->mightHaveTrait<OpTrait::IsTerminator>())
157 return false;
158 if (isa<memref::DeallocOp>(Val: useOp) ||
159 (useOp->getNumResults() == 0 && useOp->getNumRegions() == 0 &&
160 !mlir::mightHaveEffect<MemoryEffects::Read>(op: useOp)) ||
161 (isa<ViewLikeOpInterface>(Val: useOp) && resultIsNotRead(op: useOp, uses&: opUses))) {
162 opUses.push_back(x: useOp);
163 continue;
164 }
165 return false;
166 }
167 llvm::append_range(C&: uses, R&: opUses);
168 return true;
169}
170
171void eraseDeadAllocAndStores(RewriterBase &rewriter, Operation *parentOp) {
172 std::vector<Operation *> opToErase;
173 parentOp->walk(callback: [&](Operation *op) {
174 std::vector<Operation *> candidates;
175 if (isa<memref::AllocOp, memref::AllocaOp>(Val: op) &&
176 resultIsNotRead(op, uses&: candidates)) {
177 llvm::append_range(C&: opToErase, R&: candidates);
178 opToErase.push_back(x: op);
179 }
180 });
181
182 for (Operation *op : opToErase)
183 rewriter.eraseOp(op);
184}
185
186static SmallVector<OpFoldResult>
187computeSuffixProductIRBlockImpl(Location loc, OpBuilder &builder,
188 ArrayRef<OpFoldResult> sizes,
189 OpFoldResult unit) {
190 SmallVector<OpFoldResult> strides(sizes.size(), unit);
191 AffineExpr s0, s1;
192 bindSymbols(ctx: builder.getContext(), exprs&: s0, exprs&: s1);
193
194 for (int64_t r = static_cast<int64_t>(strides.size()) - 1; r > 0; --r) {
195 strides[r - 1] = affine::makeComposedFoldedAffineApply(
196 b&: builder, loc, expr: s0 * s1, operands: {strides[r], sizes[r]});
197 }
198 return strides;
199}
200
201SmallVector<OpFoldResult>
202computeSuffixProductIRBlock(Location loc, OpBuilder &builder,
203 ArrayRef<OpFoldResult> sizes) {
204 OpFoldResult unit = builder.getIndexAttr(value: 1);
205 return computeSuffixProductIRBlockImpl(loc, builder, sizes, unit);
206}
207
208MemrefValue skipFullyAliasingOperations(MemrefValue source) {
209 while (auto *op = source.getDefiningOp()) {
210 if (auto subViewOp = dyn_cast<memref::SubViewOp>(Val: op);
211 subViewOp && subViewOp.hasZeroOffset() && subViewOp.hasUnitStride()) {
212 // A `memref.subview` with an all zero offset, and all unit strides, still
213 // points to the same memory.
214 source = cast<MemrefValue>(Val: subViewOp.getSource());
215 } else if (auto castOp = dyn_cast<memref::CastOp>(Val: op)) {
216 // A `memref.cast` still points to the same memory.
217 source = castOp.getSource();
218 } else {
219 return source;
220 }
221 }
222 return source;
223}
224
225MemrefValue skipViewLikeOps(MemrefValue source) {
226 while (auto *op = source.getDefiningOp()) {
227 if (auto viewLike = dyn_cast<ViewLikeOpInterface>(Val: op)) {
228 if (source == viewLike.getViewDest()) {
229 source = cast<MemrefValue>(Val: viewLike.getViewSource());
230 continue;
231 }
232 }
233 return source;
234 }
235 return source;
236}
237
238void resolveSourceIndicesExpandShape(Location loc, PatternRewriter &rewriter,
239 memref::ExpandShapeOp expandShapeOp,
240 ValueRange indices,
241 SmallVectorImpl<Value> &sourceIndices,
242 bool startsInbounds) {
243 SmallVector<OpFoldResult> destShape = expandShapeOp.getMixedOutputShape();
244
245 // Traverse all reassociation groups to determine the appropriate indices
246 // corresponding to each one of them post op folding.
247 for (ArrayRef<int64_t> group : expandShapeOp.getReassociationIndices()) {
248 assert(!group.empty() && "association indices groups cannot be empty");
249 int64_t groupSize = group.size();
250 if (groupSize == 1) {
251 sourceIndices.push_back(Elt: indices[group[0]]);
252 continue;
253 }
254 SmallVector<OpFoldResult> groupBasis =
255 llvm::map_to_vector(C&: group, F: [&](int64_t d) { return destShape[d]; });
256 SmallVector<Value> groupIndices =
257 llvm::map_to_vector(C&: group, F: [&](int64_t d) { return indices[d]; });
258 Value collapsedIndex = affine::AffineLinearizeIndexOp::create(
259 builder&: rewriter, location: loc, multi_index: groupIndices, basis: groupBasis, /*disjoint=*/startsInbounds);
260 sourceIndices.push_back(Elt: collapsedIndex);
261 }
262}
263
264void resolveSourceIndicesCollapseShape(Location loc, PatternRewriter &rewriter,
265 memref::CollapseShapeOp collapseShapeOp,
266 ValueRange indices,
267 SmallVectorImpl<Value> &sourceIndices,
268 bool startsInbounds) {
269 // Note: collapse_shape requires a strided memref, we can do this.
270 auto metadata = memref::ExtractStridedMetadataOp::create(
271 builder&: rewriter, location: loc, source: collapseShapeOp.getSrc());
272 SmallVector<OpFoldResult> sourceSizes = metadata.getConstifiedMixedSizes();
273 for (auto [index, group] :
274 llvm::zip(t&: indices, u: collapseShapeOp.getReassociationIndices())) {
275 assert(!group.empty() && "association indices groups cannot be empty");
276 int64_t groupSize = group.size();
277
278 if (groupSize == 1) {
279 sourceIndices.push_back(Elt: index);
280 continue;
281 }
282
283 // If we don't know that this value is in-bounds, the largest return value
284 // of the delinearization may exceed `sourceSizes[d]`, so we drop that first
285 // group entry in order to maintain soundness.
286 auto trimmedGroup =
287 ArrayRef<int64_t>(group).drop_front(N: startsInbounds ? 0 : 1);
288 SmallVector<OpFoldResult> basis = llvm::map_to_vector(
289 C&: trimmedGroup, F: [&](int64_t d) { return sourceSizes[d]; });
290 auto delinearize = affine::AffineDelinearizeIndexOp::create(
291 builder&: rewriter, location: loc, linear_index: index, basis, /*hasOuterBound=*/startsInbounds);
292 llvm::append_range(C&: sourceIndices, R: delinearize.getResults());
293 }
294 if (collapseShapeOp.getReassociationIndices().empty()) {
295 auto zeroAffineMap = rewriter.getConstantAffineMap(val: 0);
296 int64_t srcRank =
297 cast<MemRefType>(Val: collapseShapeOp.getViewSource().getType()).getRank();
298 OpFoldResult ofr = affine::makeComposedFoldedAffineApply(
299 b&: rewriter, loc, map: zeroAffineMap, operands: ArrayRef<OpFoldResult>{});
300 for (int64_t i = 0; i < srcRank; i++) {
301 sourceIndices.push_back(
302 Elt: getValueOrCreateConstantIndexOp(b&: rewriter, loc, ofr));
303 }
304 }
305}
306
307LogicalResult resolveSourceIndicesRankReducingSubview(
308 Location loc, OpBuilder &b, memref::SubViewOp subViewOp, ValueRange indices,
309 SmallVectorImpl<Value> &sourceIndices) {
310 if (!subViewOp.hasZeroOffset() || !subViewOp.hasUnitStride())
311 return failure();
312
313 MemRefType srcType = subViewOp.getSourceType();
314 MemRefType resType = subViewOp.getType();
315 unsigned srcRank = srcType.getRank();
316 unsigned resRank = resType.getRank();
317 if (srcRank <= resRank || indices.size() != resRank)
318 return failure();
319
320 auto droppedDims = subViewOp.getDroppedDims();
321 if (droppedDims.none() || droppedDims.count() != srcRank - resRank)
322 return failure();
323
324 auto mixedSizes = subViewOp.getMixedSizes();
325 if (mixedSizes.size() != srcRank)
326 return failure();
327
328 unsigned resultDim = 0;
329 for (unsigned sourceDim = 0; sourceDim < srcRank; ++sourceDim) {
330 if (droppedDims.test(Idx: sourceDim)) {
331 auto sizeCst = getConstantIntValue(ofr: mixedSizes[sourceDim]);
332 if (!sizeCst || *sizeCst != 1)
333 return failure();
334 sourceIndices.push_back(
335 Elt: getValueOrCreateConstantIndexOp(b, loc, ofr: b.getIndexAttr(value: 0)));
336 continue;
337 }
338 if (resultDim >= indices.size())
339 return failure();
340 sourceIndices.push_back(Elt: indices[resultDim++]);
341 }
342 if (resultDim != indices.size())
343 return failure();
344
345 return success();
346}
347
348bool hasNegativeStaticStride(MemRefType memRefTy) {
349 auto [strides, offset] = memRefTy.getStridesAndOffset();
350 return llvm::any_of(Range&: strides, P: [](int64_t stride) {
351 return ShapedType::isStatic(dValue: stride) && stride < 0;
352 });
353}
354
355namespace {
356// TODO: This footprint modelling and its logic overlap with
357// `SubsetOpInterface`, which is unfortunately tensor-only today; if it gains
358// memref support, look into unifying with it to improve code reuse.
359//
360/// Footprint of a memref value relative to a `root` memref reached through a
361/// chain of rank-preserving `memref.subview` ops whose `strides` operand is all
362/// ones (so each result index steps one source element in every dimension): per
363/// `root` dimension, the `[offset, offset + size)` interval the value covers (a
364/// `size` may be dynamic). The root is the underlying buffer if the whole chain
365/// composes, otherwise the result of the first subview (walking toward the
366/// root) that cannot be composed. Two footprints are therefore comparable only
367/// when they resolve to the *same* root value.
368struct SubviewFootprint {
369 Value root;
370 SmallVector<int64_t> offsets;
371 SmallVector<int64_t> sizes;
372};
373} // namespace
374
375/// Resolve `base` through a `memref.subview` chain to a footprint, or
376/// `std::nullopt` if it cannot be modelled. Composition stops at the first
377/// subview with a dynamic offset, a `strides` operand other than all ones, or a
378/// rank reduction; that subview's own result becomes the footprint root. This
379/// keeps two slices that share a common (possibly dynamically-offset) base
380/// comparable through their static offsets relative to that base. Sizes may be
381/// dynamic: such dimensions simply cannot be used to prove disjointness.
382static std::optional<SubviewFootprint> resolveSubviewFootprint(Value base) {
383 auto baseTy = dyn_cast<MemRefType>(Val: base.getType());
384 if (!baseTy)
385 return std::nullopt;
386 SubviewFootprint footprint;
387 // Size is fixed by `base` itself; offset accumulates the static offsets of
388 // the composable subviews walked toward the root.
389 footprint.offsets.assign(NumElts: baseTy.getRank(), Elt: 0);
390 footprint.sizes.assign(in_start: baseTy.getShape().begin(), in_end: baseTy.getShape().end());
391
392 Value cur = base;
393 while (auto sv = cur.getDefiningOp<SubViewOp>()) {
394 ArrayRef<int64_t> staticOffsets = sv.getStaticOffsets();
395 ArrayRef<int64_t> staticStrides = sv.getStaticStrides();
396 // Rank-reducing subviews, or those with a dynamic offset or a `strides`
397 // operand other than all ones, cannot be composed: stop here and use `sv`'s
398 // result as the root.
399 if (sv.getSourceType().getRank() != sv.getType().getRank() ||
400 llvm::any_of(Range&: staticOffsets, P: ShapedType::isDynamic) ||
401 llvm::any_of(Range&: staticStrides, P: [](int64_t s) { return s != 1; }))
402 break;
403 for (unsigned d = 0, e = staticOffsets.size(); d < e; ++d)
404 footprint.offsets[d] += staticOffsets[d];
405 cur = sv.getSource();
406 }
407 // The root must be a genuine buffer or a `memref.subview` result, not another
408 // kind of view (collapse/expand/reshape) whose coordinate remapping would
409 // invalidate the per-dimension offset bookkeeping.
410 if (auto *def = cur.getDefiningOp())
411 if (isa<ViewLikeOpInterface>(Val: def) && !isa<SubViewOp>(Val: def))
412 return std::nullopt;
413 footprint.root = cur;
414 return footprint;
415}
416
417/// True if two footprints provably cover disjoint memory: they must share the
418/// same root and be separated along at least one statically-sized dimension.
419static bool areFootprintDisjoint(const SubviewFootprint &a,
420 const SubviewFootprint &b) {
421 if (a.root != b.root)
422 return false;
423 for (unsigned d = 0, e = a.offsets.size(); d < e; ++d) {
424 // A dimension can prove disjointness only when both extents are static.
425 if (ShapedType::isDynamic(dValue: a.sizes[d]) || ShapedType::isDynamic(dValue: b.sizes[d]))
426 continue;
427 int64_t aHi = a.offsets[d] + a.sizes[d];
428 int64_t bHi = b.offsets[d] + b.sizes[d];
429 if (aHi <= b.offsets[d] || bHi <= a.offsets[d])
430 return true;
431 }
432 return false;
433}
434
435bool hasNoAliasingAccessInScope(Value base, Operation *scope,
436 ArrayRef<Operation *> excludedOps,
437 bool readsAreSafe) {
438 auto baseMemref = dyn_cast<MemrefValue>(Val&: base);
439 if (!baseMemref)
440 return false;
441 Value rootBuffer = skipViewLikeOps(source: baseMemref);
442 // Footprint of `base`, if modellable; enables the disjointness escape.
443 std::optional<SubviewFootprint> baseFp = resolveSubviewFootprint(base);
444
445 // Visit the transitive users of the root buffer, following views.
446 SmallVector<Operation *> worklist(rootBuffer.getUsers().begin(),
447 rootBuffer.getUsers().end());
448 SmallPtrSet<Operation *, 8> processed;
449 while (!worklist.empty()) {
450 Operation *user = worklist.pop_back_val();
451 if (!processed.insert(Ptr: user).second)
452 continue;
453 // Views do not access memory; follow them to their own users.
454 if (auto viewLike = dyn_cast<ViewLikeOpInterface>(Val: user)) {
455 Value viewDest = viewLike.getViewDest();
456 worklist.append(in_start: viewDest.getUsers().begin(), in_end: viewDest.getUsers().end());
457 continue;
458 }
459 if (isMemoryEffectFree(op: user) || llvm::is_contained(Range&: excludedOps, Element: user))
460 continue;
461 if (!scope->isAncestor(other: user))
462 continue;
463 // In-`scope`, memory-effecting op: each of its operands that resolves to
464 // the root buffer conflicts unless it is a provably-disjoint slice or (when
465 // allowed) is only read.
466 for (Value operand : user->getOperands()) {
467 auto slice = dyn_cast<MemrefValue>(Val&: operand);
468 if (!slice || skipViewLikeOps(source: slice) != rootBuffer)
469 continue;
470 if (baseFp) {
471 std::optional<SubviewFootprint> sliceFp =
472 resolveSubviewFootprint(base: slice);
473 if (sliceFp && areFootprintDisjoint(a: *baseFp, b: *sliceFp))
474 continue;
475 }
476 if (readsAreSafe && isa<MemoryEffectOpInterface>(Val: user) &&
477 !hasEffect<MemoryEffects::Write>(op: user, value: slice))
478 continue;
479 return false;
480 }
481 }
482 return true;
483}
484
485} // namespace memref
486} // namespace mlir
487