1//===- MemRefUtils.h - MemRef transformation utilities ----------*- 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// This header file defines prototypes for various transformation utilities for
10// the MemRefOps dialect. These are not passes by themselves but are used
11// either by passes, optimization sequences, or in turn by other transformation
12// utilities.
13//
14//===----------------------------------------------------------------------===//
15
16#ifndef MLIR_DIALECT_MEMREF_UTILS_MEMREFUTILS_H
17#define MLIR_DIALECT_MEMREF_UTILS_MEMREFUTILS_H
18
19#include "mlir/Dialect/MemRef/IR/MemRef.h"
20
21namespace mlir {
22
23class MemRefType;
24
25/// A value with a memref type.
26using MemrefValue = TypedValue<BaseMemRefType>;
27
28namespace memref {
29
30/// Returns true, if the memref type has static shapes and represents a
31/// contiguous chunk of memory.
32bool isStaticShapeAndContiguousRowMajor(MemRefType type);
33
34/// Controls how the per-dimension contribution to `linearizedSize` is divided
35/// by `dstBits / srcBits` when scaling down to the emulated type. The offset
36/// and intra-data offset are unaffected; they always use floor division and
37/// remainder respectively.
38/// - `Floor`: round each `stride * size / scaler` down. Suitable for indexing
39/// computations where a partial trailing byte is not included.
40/// - `Ceil`: round up, matching the result-shape size used by narrow-type
41/// memref type conversion (see `getLinearizedShape`). Use this when the
42/// caller needs the linearized size to cover all source elements, e.g. when
43/// building the size attribute of a converted `memref.reinterpret_cast`.
44enum class LinearizedDivKind { Floor, Ceil };
45
46/// For a `memref` with `offset`, `sizes` and `strides`, returns the
47/// offset, size, and potentially the size padded at the front to use for the
48/// linearized `memref`.
49/// - If the linearization is done for emulating load/stores of
50/// element type with bitwidth `srcBits` using element type with
51/// bitwidth `dstBits`, the linearized offset and size are
52/// scaled down by `dstBits`/`srcBits`.
53/// - If `indices` is provided, it represents the position in the
54/// original `memref` being accessed. The method then returns the
55/// index to use in the linearized `memref`. The linearized index
56/// is also scaled down by `dstBits`/`srcBits`. If `indices` is not provided
57/// 0, is returned for the linearized index.
58/// - If the size of the load/store is smaller than the linearized memref
59/// load/store, the memory region emulated is larger than the actual memory
60/// region needed. `intraDataOffset` returns the element offset of the data
61/// relevant at the beginning.
62/// - `sizeDivKind` selects floor vs ceil rounding for the `linearizedSize`
63/// contribution from each dimension (see `LinearizedDivKind`).
64struct LinearizedMemRefInfo {
65 OpFoldResult linearizedOffset;
66 OpFoldResult linearizedSize;
67 OpFoldResult intraDataOffset;
68};
69std::pair<LinearizedMemRefInfo, OpFoldResult> getLinearizedMemRefOffsetAndSize(
70 OpBuilder &builder, Location loc, int srcBits, int dstBits,
71 OpFoldResult offset, ArrayRef<OpFoldResult> sizes,
72 ArrayRef<OpFoldResult> strides, ArrayRef<OpFoldResult> indices = {},
73 LinearizedDivKind sizeDivKind = LinearizedDivKind::Floor);
74
75/// For a `memref` with `offset` and `sizes`, returns the
76/// offset and size to use for the linearized `memref`, assuming that
77/// the strides are computed from a row-major ordering of the sizes;
78/// - If the linearization is done for emulating load/stores of
79/// element type with bitwidth `srcBits` using element type with
80/// bitwidth `dstBits`, the linearized offset and size are
81/// scaled down by `dstBits`/`srcBits`.
82/// - `sizeDivKind` selects floor vs ceil rounding for the `linearizedSize`
83/// contribution from each dimension (see `LinearizedDivKind`).
84LinearizedMemRefInfo getLinearizedMemRefOffsetAndSize(
85 OpBuilder &builder, Location loc, int srcBits, int dstBits,
86 OpFoldResult offset, ArrayRef<OpFoldResult> sizes,
87 LinearizedDivKind sizeDivKind = LinearizedDivKind::Floor);
88
89/// Track temporary allocations that are never read from. If this is the case
90/// it means both the allocations and associated stores can be removed.
91void eraseDeadAllocAndStores(RewriterBase &rewriter, Operation *parentOp);
92
93/// Given a set of sizes, return the suffix product.
94///
95/// When applied to slicing, this is the calculation needed to derive the
96/// strides (i.e. the number of linear indices to skip along the (k-1) most
97/// minor dimensions to get the next k-slice).
98///
99/// This is the basis to linearize an n-D offset confined to `[0 ... sizes]`.
100///
101/// Assuming `sizes` is `[s0, .. sn]`, return the vector<Value>
102/// `[s1 * ... * sn, s2 * ... * sn, ..., sn, 1]`.
103///
104/// It is the caller's responsibility to provide valid OpFoldResult type values
105/// and construct valid IR in the end.
106///
107/// `sizes` elements are asserted to be non-negative.
108///
109/// Return an empty vector if `sizes` is empty.
110///
111/// The function emits an IR block which computes suffix product for provided
112/// sizes.
113SmallVector<OpFoldResult>
114computeSuffixProductIRBlock(Location loc, OpBuilder &builder,
115 ArrayRef<OpFoldResult> sizes);
116inline SmallVector<OpFoldResult>
117computeStridesIRBlock(Location loc, OpBuilder &builder,
118 ArrayRef<OpFoldResult> sizes) {
119 return computeSuffixProductIRBlock(loc, builder, sizes);
120}
121
122/// Walk up the source chain until an operation that changes/defines the view of
123/// memory is found (i.e. skip operations that alias the entire view).
124MemrefValue skipFullyAliasingOperations(MemrefValue source);
125
126/// Checks if two (memref) values are the same or statically known to alias
127/// the same region of memory.
128inline bool isSameViewOrTrivialAlias(MemrefValue a, MemrefValue b) {
129 return skipFullyAliasingOperations(source: a) == skipFullyAliasingOperations(source: b);
130}
131
132/// Walk up the source chain until we find an operation that is not a view of
133/// the source memref (i.e. implements ViewLikeOpInterface).
134MemrefValue skipViewLikeOps(MemrefValue source);
135
136/// Given the 'indices' of a load/store operation where the memref is a result
137/// of a expand_shape op, returns the indices w.r.t to the source memref of the
138/// expand_shape op into `sourceIndices`. For example
139///
140/// %0 = ... : memref<12x42xf32>
141/// %1 = memref.expand_shape %0 [[0, 1], [2]]
142/// : memref<12x42xf32> into memref<2x6x42xf32>
143/// %2 = load %1[%i1, %i2, %i3] : memref<2x6x42xf32
144///
145/// could be folded into
146///
147/// %2 = load %0[6 * i1 + i2, %i3] :
148/// memref<12x42xf32>
149///
150/// If `startsInbounds` is true, optimizations that rely on all indices being
151/// non-negative and less than the corresponding memref dimension may be
152/// performed.
153void resolveSourceIndicesExpandShape(Location loc, PatternRewriter &rewriter,
154 memref::ExpandShapeOp expandShapeOp,
155 ValueRange indices,
156 SmallVectorImpl<Value> &sourceIndices,
157 bool startsInbounds);
158
159/// Given the 'indices' of a load/store operation where the memref is a result
160/// of a collapse_shape op, returns the indices w.r.t to the source memref of
161/// the collapse_shape op, returing them into `sourceIndices`. For example
162///
163/// %0 = ... : memref<2x6x42xf32>
164/// %1 = memref.collapse_shape %0 [[0, 1], [2]]
165/// : memref<2x6x42xf32> into memref<12x42xf32>
166/// %2 = load %1[%i1, %i2] : memref<12x42xf32>
167///
168/// could be folded into
169///
170/// %2 = load %0[%i1 / 6, %i1 % 6, %i2] :
171/// memref<2x6x42xf32>
172///
173/// If `startsInbounds` is true, optimizations that rely on all indices being
174/// non-negative and less than the corresponding memref dimension may be
175/// performed.
176void resolveSourceIndicesCollapseShape(Location loc, PatternRewriter &rewriter,
177 memref::CollapseShapeOp collapseShapeOp,
178 ValueRange indices,
179 SmallVectorImpl<Value> &sourceIndices,
180 bool startsInbounds);
181
182/// Given the 'indices' of a load/store operation where the memref is a result
183/// of a rank-reducing full subview op, returns the indices w.r.t to the source
184/// memref of the memref.subview op. For example
185///
186/// %alias = memref.subview %src[0, 0, 0][1, 2, 2][1, 1, 1]: memref<1x2x2xf32>
187/// to memref<2x2xf32>
188/// %val = memref.load %alias[%i, %j] : memref<2x2xf32>
189///
190/// could be folded into
191///
192/// %val = memref.load %src[0, %i, %j] : memref<1x2x2xf32>
193LogicalResult resolveSourceIndicesRankReducingSubview(
194 Location loc, OpBuilder &b, memref::SubViewOp subViewOp, ValueRange indices,
195 SmallVectorImpl<Value> &sourceIndices);
196
197/// Returns true if any stride of `memRefTy` is statically known to be
198/// negative.
199bool hasNegativeStaticStride(MemRefType memRefTy);
200
201/// Return "true" when no other access nested in `scope` can alias `base`.
202///
203/// The underlying buffer is found by looking through the view ops defining
204/// `base`, and its transitive in-`scope` users are visited. A user conflicts
205/// unless it is effect-free, in `excludedOps`, or each of its memref operands
206/// that resolves to the buffer touches a slice disjoint from `base`'s static
207/// footprint (or, when `readsAreSafe`, is only read). `excludedOps` are left
208/// out of the analysis, typically because the caller intends to relocate them.
209bool hasNoAliasingAccessInScope(Value base, Operation *scope,
210 ArrayRef<Operation *> excludedOps = {},
211 bool readsAreSafe = false);
212
213} // namespace memref
214} // namespace mlir
215
216#endif // MLIR_DIALECT_MEMREF_UTILS_MEMREFUTILS_H
217