| 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 | |
| 21 | namespace mlir { |
| 22 | namespace memref { |
| 23 | |
| 24 | bool 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 | |
| 56 | std::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 | |
| 121 | LinearizedMemRefInfo |
| 122 | getLinearizedMemRefOffsetAndSize(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. |
| 151 | static 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 | |
| 171 | void 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 | |
| 186 | static SmallVector<OpFoldResult> |
| 187 | computeSuffixProductIRBlockImpl(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 | |
| 201 | SmallVector<OpFoldResult> |
| 202 | computeSuffixProductIRBlock(Location loc, OpBuilder &builder, |
| 203 | ArrayRef<OpFoldResult> sizes) { |
| 204 | OpFoldResult unit = builder.getIndexAttr(value: 1); |
| 205 | return computeSuffixProductIRBlockImpl(loc, builder, sizes, unit); |
| 206 | } |
| 207 | |
| 208 | MemrefValue 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 | |
| 225 | MemrefValue 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 | |
| 238 | void 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 | |
| 264 | void 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 | |
| 307 | LogicalResult 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 | |
| 348 | bool 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 | |
| 355 | namespace { |
| 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. |
| 368 | struct { |
| 369 | Value ; |
| 370 | SmallVector<int64_t> ; |
| 371 | SmallVector<int64_t> ; |
| 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. |
| 382 | static std::optional<SubviewFootprint> (Value base) { |
| 383 | auto baseTy = dyn_cast<MemRefType>(Val: base.getType()); |
| 384 | if (!baseTy) |
| 385 | return std::nullopt; |
| 386 | SubviewFootprint ; |
| 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. |
| 419 | static bool (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 | |
| 435 | bool 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 | |