1//===- TensorTilingInterface.cpp - Tiling Interface models *- 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#include "mlir/Dialect/Tensor/IR/TensorTilingInterfaceImpl.h"
10#include "mlir/Dialect/Affine/IR/AffineOps.h"
11#include "mlir/Dialect/Affine/Utils.h"
12#include "mlir/Dialect/Arith/Utils/Utils.h"
13#include "mlir/Dialect/Linalg/Utils/Utils.h"
14#include "mlir/Dialect/SCF/IR/SCF.h"
15#include "mlir/Dialect/Tensor/IR/Tensor.h"
16#include "mlir/Interfaces/InferTypeOpInterface.h"
17#include "mlir/Interfaces/TilingInterface.h"
18
19using namespace mlir;
20using namespace mlir::tensor;
21
22namespace {
23
24struct PadOpTiling : public TilingInterface::ExternalModel<PadOpTiling, PadOp> {
25 using Base = TilingInterface::ExternalModel<PadOpTiling, PadOp>;
26 // Inherit the defaulted hint-bearing overloads; this op does not require the
27 // hint.
28 using Base::generateResultTileValue;
29 using Base::getTiledImplementation;
30
31 SmallVector<utils::IteratorType> getLoopIteratorTypes(Operation *op) const {
32 auto padOp = cast<PadOp>(Val: op);
33 SmallVector<utils::IteratorType> iteratorTypes(
34 padOp.getResultType().getRank(), utils::IteratorType::parallel);
35 return iteratorTypes;
36 }
37
38 SmallVector<Range> getIterationDomain(Operation *op, OpBuilder &b) const {
39 ReifiedRankedShapedTypeDims reifiedShapes;
40 (void)reifyResultShapes(b, op, reifiedReturnShapes&: reifiedShapes);
41 OpFoldResult zero = b.getIndexAttr(value: 0);
42 OpFoldResult one = b.getIndexAttr(value: 1);
43 // Initialize all the ranges to {zero, one, one}. All the `ub`s are
44 // overwritten.
45 SmallVector<Range> loopRanges(reifiedShapes[0].size(), {.offset: zero, .size: one, .stride: one});
46 for (const auto &ub : enumerate(First&: reifiedShapes[0]))
47 loopRanges[ub.index()].size = ub.value();
48 return loopRanges;
49 }
50
51 FailureOr<TilingResult>
52 getTiledImplementation(Operation *op, OpBuilder &b,
53 ArrayRef<OpFoldResult> offsets,
54 ArrayRef<OpFoldResult> sizes) const {
55 FailureOr<TilingResult> result =
56 tensor::bubbleUpPadSlice(b, padOp: cast<PadOp>(Val: op), offsets, sizes);
57 if (failed(Result: result))
58 return failure();
59 return result.value();
60 }
61
62 LogicalResult
63 getResultTilePosition(Operation *op, OpBuilder &b, unsigned resultNumber,
64 ArrayRef<OpFoldResult> offsets,
65 ArrayRef<OpFoldResult> sizes,
66 SmallVector<OpFoldResult> &resultOffsets,
67 SmallVector<OpFoldResult> &resultSizes) const {
68 resultOffsets.assign(in_start: offsets.begin(), in_end: offsets.end());
69 resultSizes.assign(in_start: sizes.begin(), in_end: sizes.end());
70 return success();
71 }
72
73 LogicalResult getIterationDomainTileFromResultTile(
74 Operation *op, OpBuilder &b, unsigned resultNumber,
75 ArrayRef<OpFoldResult> offsets, ArrayRef<OpFoldResult> sizes,
76 SmallVectorImpl<OpFoldResult> &iterDomainOffsets,
77 SmallVectorImpl<OpFoldResult> &iterDomainSizes) const {
78 iterDomainOffsets.assign(in_start: offsets.begin(), in_end: offsets.end());
79 iterDomainSizes.assign(in_start: sizes.begin(), in_end: sizes.end());
80 return success();
81 }
82
83 FailureOr<TilingResult>
84 generateResultTileValue(Operation *op, OpBuilder &b, unsigned resultNumber,
85 ArrayRef<OpFoldResult> offsets,
86 ArrayRef<OpFoldResult> sizes) const {
87 return getTiledImplementation(op, b, offsets, sizes);
88 }
89};
90
91} // namespace
92
93FailureOr<TilingResult> tensor::bubbleUpPadSlice(OpBuilder &b,
94 tensor::PadOp padOp,
95 ArrayRef<OpFoldResult> offsets,
96 ArrayRef<OpFoldResult> sizes,
97 bool generateZeroSliceGuard) {
98 // Only constant padding value supported.
99 Value padValue = padOp.getConstantPaddingValue();
100 if (!padValue)
101 return failure();
102
103 // Helper variables and functions for various arithmetic operations. These
104 // are used extensively for computing new offset/length and padding values.
105 Location loc = padOp->getLoc();
106 AffineExpr dim0, dim1;
107 bindDims(ctx: b.getContext(), exprs&: dim0, exprs&: dim1);
108 // Subtract two integers.
109 auto subMap = AffineMap::get(dimCount: 2, symbolCount: 0, result: {dim0 - dim1});
110 auto sub = [&](OpFoldResult v1, OpFoldResult v2) {
111 return affine::makeComposedFoldedAffineApply(b, loc, map: subMap, operands: {v1, v2});
112 };
113 // Take the minimum of two integers.
114 auto idMap = AffineMap::getMultiDimIdentityMap(numDims: 2, context: b.getContext());
115 auto min = [&](OpFoldResult v1, OpFoldResult v2) {
116 return affine::makeComposedFoldedAffineMin(b, loc, map: idMap, operands: {v1, v2});
117 };
118 // Take the maximum of two integers.
119 auto max = [&](OpFoldResult v1, OpFoldResult v2) {
120 return affine::makeComposedFoldedAffineMax(b, loc, map: idMap, operands: {v1, v2});
121 };
122 // Zero index-typed integer.
123 OpFoldResult zero = b.getIndexAttr(value: 0);
124
125 // Compute new offsets, lengths, low padding, high padding.
126 SmallVector<OpFoldResult> newOffsets, newLengths;
127 SmallVector<OpFoldResult> newLows, newHighs;
128 // Set to true if the original data source is not read at all.
129 bool hasZeroLen = false;
130 // Same as hasZeroLen, but for dynamic dimension sizes. This condition
131 // is true if the original data source turns out to be unused at runtime.
132 Value dynHasZeroLenCond;
133
134 int64_t rank = padOp.getSourceType().getRank();
135 // Only unit stride supported.
136 SmallVector<OpFoldResult> newStrides(rank, b.getIndexAttr(value: 1));
137 for (unsigned dim = 0; dim < rank; ++dim) {
138 auto low = padOp.getMixedLowPad()[dim];
139 bool hasLowPad = !isZeroInteger(v: low);
140 auto high = padOp.getMixedHighPad()[dim];
141 bool hasHighPad = !isZeroInteger(v: high);
142 auto offset = offsets[dim];
143 auto length = sizes[dim];
144 // If the dim has no padding, we dont need to calculate new values for that
145 // dim as the exisiting ones are correct even after the pattern.
146 if (!hasLowPad && !hasHighPad) {
147 newOffsets.push_back(Elt: offset);
148 newLengths.push_back(Elt: length);
149 newLows.push_back(Elt: low);
150 newHighs.push_back(Elt: high);
151 continue;
152 }
153
154 auto srcSize = tensor::getMixedSize(builder&: b, loc, value: padOp.getSource(), dim);
155
156 // The new amount of low padding is `low - offset`. Except for the case
157 // where none of the low padding is read. In that case, the new amount of
158 // low padding is zero.
159 //
160 // Optimization: If low = 0, then newLow = 0.
161 OpFoldResult newLow = hasLowPad ? max(zero, sub(low, offset)) : zero;
162 newLows.push_back(Elt: newLow);
163
164 // Start reading the data from position `offset - low`. Since the original
165 // read may have started in the low padding zone, this value could be
166 // negative. Therefore, start reading from:
167 //
168 // max(offset - low, 0)
169 //
170 // The original read could also have started in the high padding zone.
171 // In that case, set the offset to the end of source tensor. The new
172 // ExtractSliceOp length will be zero in that case. (Effectively reading
173 // no data from the source.)
174 //
175 // Optimization: If low = 0, then the formula can be simplified.
176 OpFoldResult newOffset = hasLowPad
177 ? min(max(sub(offset, low), zero), srcSize)
178 : min(offset, srcSize);
179 newOffsets.push_back(Elt: newOffset);
180
181 // The original ExtractSliceOp was reading until position `offset +
182 // length`. Therefore, the corresponding position within the source tensor
183 // is:
184 //
185 // offset + length - low
186 //
187 // In case the original ExtractSliceOp stopped reading within the low
188 // padding zone, this value can be negative. In that case, the end
189 // position of the read should be zero. (Similar to newOffset.)
190 //
191 // The original read could also have stopped in the high padding zone.
192 // In that case, set the end positition of the read should be the end of
193 // the source tensor. (Similar to newOffset.)
194 // srcSize - newOffset represents how much length we have available
195 // and length - newLow represents how much length we want at most.
196 // Note that there are many ways to order this indexing math to compute
197 // newLength, but we want to make sure that the final affine.min ops in the
198 // sequence are bounding the index to as small a value as possible. If
199 // ValueBoundsOpInterface is used, this calculation will get upper bounds
200 // from the affine.min ops, so we want to use the smallest known value to
201 // set the bound at the end of the computation sequence. In this case, the
202 // index will be upper bounded by length - newLow.
203 OpFoldResult newLength = min(sub(srcSize, newOffset), sub(length, newLow));
204 // Optimization: If low = 0, then newLow = 0. then newLength >= 0 assuming
205 // length >= 0.
206 if (hasLowPad)
207 newLength = max(newLength, zero);
208 newLengths.push_back(Elt: newLength);
209
210 // Check if newLength is zero. In that case, no SubTensorOp should be
211 // executed.
212 if (isZeroInteger(v: newLength)) {
213 hasZeroLen = true;
214 } else if (!hasZeroLen) {
215 Value check = arith::CmpIOp::create(
216 builder&: b, location: loc, predicate: arith::CmpIPredicate::eq,
217 lhs: getValueOrCreateConstantIndexOp(b, loc, ofr: newLength),
218 rhs: getValueOrCreateConstantIndexOp(b, loc, ofr: zero));
219 dynHasZeroLenCond =
220 dynHasZeroLenCond
221 ? arith::OrIOp::create(builder&: b, location: loc, lhs: check, rhs: dynHasZeroLenCond)
222 : check;
223 }
224
225 // The amount of high padding is simply the number of elements remaining,
226 // so that the result has the same length as the original ExtractSliceOp.
227 // As an optimization, if the original high padding is zero, then the new
228 // high padding must also be zero.
229 OpFoldResult newHigh =
230 hasHighPad ? sub(sub(length, newLength), newLow) : zero;
231 newHighs.push_back(Elt: newHigh);
232 }
233
234 // The shape of the result can be obtained from the sizes passed in.
235 SmallVector<Value> dynDims;
236 SmallVector<int64_t> shape;
237 dispatchIndexOpFoldResults(ofrs: sizes, dynamicVec&: dynDims, staticVec&: shape);
238 RankedTensorType resultType =
239 RankedTensorType::get(shape, elementType: padOp.getResultType().getElementType());
240
241 // Insert cast to ensure that types match. (May be folded away.)
242 auto castResult = [&](Value val) -> Value {
243 if (resultType == val.getType())
244 return val;
245 return tensor::CastOp::create(builder&: b, location: loc, dest: resultType, source: val);
246 };
247
248 // In cases where the original data source is unused: Emit a GenerateOp and
249 // do not generate a SliceOp. (The result shape of the SliceOp would
250 // have a dimension of size 0, the semantics of which is unclear.)
251 auto createGenerateOp = [&]() {
252 // Create GenerateOp.
253 auto generateOp = tensor::GenerateOp::create(
254 builder&: b, location: loc, resultTy: resultType, dynamicExtents: dynDims,
255 odsArg2: [&](OpBuilder &builder, Location gLoc, ValueRange indices) {
256 tensor::YieldOp::create(builder, location: gLoc, value: padValue);
257 });
258 return generateOp;
259 };
260
261 // Emit a SliceOp and a PadOp. Should not be used in cases where
262 // the result shape of the new SliceOp has a zero dimension.
263 auto createPadOfExtractSlice = [&]() {
264 // Create pad(extract_slice(x)).
265 auto newSliceOp = tensor::ExtractSliceOp::create(
266 builder&: b, location: loc, source: padOp.getSource(), offsets: newOffsets, sizes: newLengths, strides: newStrides);
267 auto newPadOp = PadOp::create(
268 builder&: b, location: loc, resultType: Type(), source: newSliceOp, low: newLows, high: newHighs,
269 /*nofold=*/padOp.getNofold(),
270 attrs: getPrunedAttributeList(op: padOp, elidedAttrs: PadOp::getAttributeNames()));
271
272 // Copy region to new PadOp.
273 IRMapping bvm;
274 padOp.getRegion().cloneInto(dest: &newPadOp.getRegion(), mapper&: bvm);
275
276 // Cast result and return.
277 return std::make_tuple(args&: newPadOp, args&: newSliceOp);
278 };
279
280 // Rewrite extract_slice(pad(x)) into a GenerateOp it is statically known that
281 // the original data source x is not used.
282 if (hasZeroLen) {
283 Operation *generateOp = createGenerateOp();
284 return TilingResult{.tiledOps: {generateOp},
285 .tiledValues: {castResult(generateOp->getResult(idx: 0))},
286 /*generatedSlices=*/{}};
287 }
288
289 // If there are dynamic dimensions: Generate an scf.if check to avoid
290 // creating SliceOps with result dimensions of size 0 at runtime.
291 if (generateZeroSliceGuard && dynHasZeroLenCond) {
292 Operation *thenOp;
293 Operation *elseOp;
294 Operation *sliceOp;
295 auto result = scf::IfOp::create(
296 builder&: b, location: loc, cond: dynHasZeroLenCond,
297 /*thenBuilder=*/
298 [&](OpBuilder &b, Location loc) {
299 thenOp = createGenerateOp();
300 scf::YieldOp::create(builder&: b, location: loc, results: castResult(thenOp->getResult(idx: 0)));
301 },
302 /*elseBuilder=*/
303 [&](OpBuilder &b, Location loc) {
304 std::tie(args&: elseOp, args&: sliceOp) = createPadOfExtractSlice();
305 scf::YieldOp::create(builder&: b, location: loc, results: castResult(elseOp->getResult(idx: 0)));
306 });
307 return TilingResult{
308 .tiledOps: {elseOp}, .tiledValues: SmallVector<Value>(result->getResults()), .generatedSlices: {sliceOp}};
309 }
310
311 auto [newPadOp, sliceOp] = createPadOfExtractSlice();
312 return TilingResult{
313 .tiledOps: {newPadOp}, .tiledValues: {castResult(newPadOp->getResult(idx: 0))}, .generatedSlices: {sliceOp}};
314}
315
316void mlir::tensor::registerTilingInterfaceExternalModels(
317 DialectRegistry &registry) {
318 registry.addExtension(extensionFn: +[](MLIRContext *ctx, TensorDialect *dialect) {
319 tensor::PadOp::attachInterface<PadOpTiling>(context&: *ctx);
320 });
321}
322