| 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 | |
| 19 | using namespace mlir; |
| 20 | using namespace mlir::tensor; |
| 21 | |
| 22 | namespace { |
| 23 | |
| 24 | struct 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 | |
| 93 | FailureOr<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 = [&]() { |
| 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 | |
| 316 | void mlir::tensor::registerTilingInterfaceExternalModels( |
| 317 | DialectRegistry ®istry) { |
| 318 | registry.addExtension(extensionFn: +[](MLIRContext *ctx, TensorDialect *dialect) { |
| 319 | tensor::PadOp::attachInterface<PadOpTiling>(context&: *ctx); |
| 320 | }); |
| 321 | } |
| 322 | |