| 1 | //===- Transforms.cpp - Linalg transformations as patterns ----------------===// |
| 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 logic and helpers to expose Linalg transforms as rewrite |
| 10 | // patterns. |
| 11 | // |
| 12 | //===----------------------------------------------------------------------===// |
| 13 | |
| 14 | #include "mlir/Dialect/Linalg/Transforms/Transforms.h" |
| 15 | #include "mlir/Dialect/Affine/IR/AffineOps.h" |
| 16 | #include "mlir/Dialect/Arith/IR/Arith.h" |
| 17 | #include "mlir/Dialect/Func/IR/FuncOps.h" |
| 18 | #include "mlir/Dialect/Linalg/IR/Linalg.h" |
| 19 | #include "mlir/Dialect/Linalg/Utils/Utils.h" |
| 20 | #include "mlir/Dialect/SCF/Transforms/Transforms.h" |
| 21 | #include "mlir/Dialect/Tensor/IR/Tensor.h" |
| 22 | #include "mlir/Dialect/Tensor/IR/TensorTilingInterfaceImpl.h" |
| 23 | #include "mlir/Dialect/Tensor/Utils/Utils.h" |
| 24 | #include "mlir/Dialect/Utils/IndexingUtils.h" |
| 25 | #include "mlir/Dialect/Utils/StaticValueUtils.h" |
| 26 | #include "mlir/Dialect/Utils/StructuredOpsUtils.h" |
| 27 | #include "mlir/Dialect/Vector/IR/VectorOps.h" |
| 28 | #include "mlir/IR/AffineExpr.h" |
| 29 | #include "mlir/IR/BuiltinTypeInterfaces.h" |
| 30 | #include "mlir/IR/BuiltinTypes.h" |
| 31 | #include "mlir/Support/LLVM.h" |
| 32 | #include "llvm/ADT/SmallVectorExtras.h" |
| 33 | #include "llvm/ADT/TypeSwitch.h" |
| 34 | #include "llvm/Support/Debug.h" |
| 35 | #include "llvm/Support/DebugLog.h" |
| 36 | #include "llvm/Support/InterleavedRange.h" |
| 37 | #include "llvm/Support/raw_ostream.h" |
| 38 | #include <type_traits> |
| 39 | #include <utility> |
| 40 | |
| 41 | #define DEBUG_TYPE "linalg-transforms" |
| 42 | |
| 43 | using namespace mlir; |
| 44 | using namespace mlir::linalg; |
| 45 | |
| 46 | //===----------------------------------------------------------------------===// |
| 47 | // Transformations exposed as functional-style API calls. |
| 48 | //===----------------------------------------------------------------------===// |
| 49 | |
| 50 | //===----------------------------------------------------------------------===// |
| 51 | // peelLoop transformation. |
| 52 | //===----------------------------------------------------------------------===// |
| 53 | |
| 54 | /// Try to peel and canonicalize loop `op` and return the new result. |
| 55 | /// Also applies affine_min/max bounds simplification on the fly where relevant. |
| 56 | // TODO: Add support for scf.parallel and affine.for loops. |
| 57 | SmallVector<Value> mlir::linalg::peelLoop(RewriterBase &rewriter, |
| 58 | Operation *op) { |
| 59 | return llvm::TypeSwitch<Operation *, SmallVector<Value, 4>>(op) |
| 60 | .Case(caseFn: [&](scf::ForOp forOp) { |
| 61 | scf::ForOp partialIteration; |
| 62 | if (succeeded(Result: scf::peelForLoopAndSimplifyBounds(rewriter, forOp, |
| 63 | partialIteration))) |
| 64 | return partialIteration->getResults(); |
| 65 | assert(!partialIteration && "expected that loop was not peeled" ); |
| 66 | return forOp->getResults(); |
| 67 | }) |
| 68 | .Default(defaultFn: [&](Operation *op) { return op->getResults(); }); |
| 69 | } |
| 70 | |
| 71 | /// Peel 'loops' and applies affine_min/max bounds simplification on the fly |
| 72 | /// where relevant. |
| 73 | void mlir::linalg::peelLoops(RewriterBase &rewriter, |
| 74 | ArrayRef<scf::ForOp> loops) { |
| 75 | for (auto loopOp : loops) |
| 76 | peelLoop(rewriter, op: loopOp); |
| 77 | } |
| 78 | |
| 79 | //===----------------------------------------------------------------------===// |
| 80 | // pack transformation. |
| 81 | //===----------------------------------------------------------------------===// |
| 82 | |
| 83 | #ifndef NDEBUG |
| 84 | /// Return true if `map` has 0 or 1 result function of AffineDimExpr(dim). |
| 85 | static bool hasAtMostOneResultFunctionOfDim(AffineMap map, int64_t dim) { |
| 86 | bool found = false; |
| 87 | for (AffineExpr e : map.getResults()) { |
| 88 | if (!e.isFunctionOfDim(dim)) |
| 89 | continue; |
| 90 | if (found) |
| 91 | return false; |
| 92 | found = true; |
| 93 | } |
| 94 | return true; |
| 95 | } |
| 96 | #endif // NDEBUG |
| 97 | |
| 98 | static std::string stringifyReassocIndices(ReassociationIndicesRef ri) { |
| 99 | return llvm::interleaved(R: ri, Separator: ", " , /*Prefix=*/"|" , /*Suffix=*/"" ); |
| 100 | } |
| 101 | |
| 102 | /// Return the index of the first result of `map` that is a function of |
| 103 | /// AffineDimExpr(dim), std::nullopt otherwise. |
| 104 | static std::optional<int64_t> getFirstResultIndexFunctionOf(AffineMap map, |
| 105 | int64_t dim) { |
| 106 | for (int64_t i = 0, e = map.getNumResults(); i < e; ++i) { |
| 107 | AffineExpr expr = map.getResult(idx: i); |
| 108 | if (!expr.isFunctionOfDim(position: dim)) |
| 109 | continue; |
| 110 | return i; |
| 111 | } |
| 112 | return std::nullopt; |
| 113 | } |
| 114 | |
| 115 | /// Perform one step of packing of a LinalgOp's metadata along `dim` into the |
| 116 | /// `newDim` at `iteratorTypes.size()` by: |
| 117 | /// 1. Appending `iteratorTypes[newDim]`, equal to `iteratorTypes[dim]`. |
| 118 | /// 2. Appending a `newDim` to the domain of every indexing map. |
| 119 | /// 3. For each operand (i.e. for each map in `indexingMaps`), perform packing |
| 120 | /// by potentially adding a `newDim` result to `map`. |
| 121 | /// The preserved invariant is that `iteratorTypes.size()` is always equal to |
| 122 | /// `map.getNumDims()` for every map in `indexingMaps`. |
| 123 | /// |
| 124 | /// Update `indexingMaps` and `iteratorTypes` inplace as one step of the update. |
| 125 | /// Return a vector that records the optional packing for each operand. |
| 126 | /// Return failure if the packed indexing cannot be represented with a LinalgOp. |
| 127 | /// |
| 128 | /// Further details: |
| 129 | /// ================ |
| 130 | /// The current implementation of packing (i.e. data tiling) consists of |
| 131 | /// rewriting a linearized strip-mined form into a higher-dimensional access. |
| 132 | /// e.g. consider an access `A[I][f(j, k, l)]` and packing by 4; we rewrite |
| 133 | /// `I` into `4 * i + ii`, where `0 <= ii < 4`. |
| 134 | /// The access is further rewritten as `A[i][f(j, k, l)][ii]`. |
| 135 | /// |
| 136 | /// This rewrite into higher dimensional access is not possible for general |
| 137 | /// AffineExpr in Linalg atm, it is restricted to an AffineDimExpr: |
| 138 | /// e.g. consider an access `A[I + J][f(j, k, l)]` and packing by 4; we |
| 139 | /// rewrite `I + J` into `4 * i + ii + J`, where `0 <= ii < 4`. |
| 140 | /// The rewrite of the access would be a form not representable in Linalg: |
| 141 | /// `A[i + (ii + J) / 4][f(j, k, l)][(ii + J) % 4]`. |
| 142 | /// Note however that as `J` and `ii` iterate, the accesses do not have a |
| 143 | /// particular alignment, so packing does not achieve alignment in this case |
| 144 | /// |
| 145 | /// In the future, we may want to consider a mixed-form that allows some |
| 146 | /// alignment in the presence of multiple accesses: |
| 147 | /// `A[I][f(j, k, l)]` and `B[I + J][f(j, k, l)]` |
| 148 | /// And would rewrite accesses as: |
| 149 | /// `A[i][f(j, k, l)][ii]` and `B[4 * i + ii + J][f(j, k, l)]` |
| 150 | static FailureOr<SmallVector<std::optional<int64_t>>> |
| 151 | packLinalgMetadataOnce(SmallVectorImpl<AffineMap> &indexingMaps, |
| 152 | SmallVectorImpl<utils::IteratorType> &iteratorTypes, |
| 153 | int64_t dim) { |
| 154 | int64_t newDim = iteratorTypes.size(); |
| 155 | iteratorTypes.push_back(Elt: iteratorTypes[dim]); |
| 156 | |
| 157 | SmallVector<std::optional<int64_t>> packedDimPerIndexingMap( |
| 158 | indexingMaps.size(), std::nullopt); |
| 159 | SmallVector<AffineMap> newMaps; |
| 160 | for (int64_t operandIdx = 0, e = indexingMaps.size(); operandIdx < e; |
| 161 | ++operandIdx) { |
| 162 | AffineMap map = indexingMaps[operandIdx]; |
| 163 | |
| 164 | // Add the `newDim` to map whatever the case. |
| 165 | assert(map.getNumDims() == newDim && "num dims invariant violation" ); |
| 166 | map = map.shiftDims(shift: 1, offset: newDim); |
| 167 | |
| 168 | // Get the at-most-1 index of the result that is a function of `dim`. |
| 169 | // If we can find one, we insert `AffineDimExpr(newDim)` to the map, which |
| 170 | // logically chunks dimension `dim` into `K * dim + newDim`, where the |
| 171 | // packing factor `K` is specified separately. |
| 172 | assert(hasAtMostOneResultFunctionOfDim(map, dim) && |
| 173 | "num results invariant violation" ); |
| 174 | auto maybeOperandDimensionToPack = getFirstResultIndexFunctionOf(map, dim); |
| 175 | if (!maybeOperandDimensionToPack.has_value()) { |
| 176 | newMaps.push_back(Elt: map); |
| 177 | continue; |
| 178 | } |
| 179 | |
| 180 | // We can only pack AffineDimExpr atm. |
| 181 | if (!isa<AffineDimExpr>(Val: map.getResult(idx: maybeOperandDimensionToPack.value()))) |
| 182 | return failure(); |
| 183 | |
| 184 | // Add `newDim` to the results of the map. |
| 185 | map = map.insertResult(expr: Builder(map.getContext()).getAffineDimExpr(position: newDim), |
| 186 | pos: map.getNumResults()); |
| 187 | newMaps.push_back(Elt: map); |
| 188 | |
| 189 | // Record the that `operandIdx` is packed. |
| 190 | packedDimPerIndexingMap[operandIdx] = maybeOperandDimensionToPack; |
| 191 | } |
| 192 | indexingMaps = newMaps; |
| 193 | |
| 194 | return packedDimPerIndexingMap; |
| 195 | } |
| 196 | |
| 197 | namespace { |
| 198 | |
| 199 | /// Helper struct to encode packing along one dimension of a LinalgOp. |
| 200 | struct PackedOperandsDim { |
| 201 | OpFoldResult packedSize; |
| 202 | SmallVector<std::optional<int64_t>> packedDimForEachOperand; |
| 203 | }; |
| 204 | |
| 205 | /// Helper struct to encode packing along all dimensions of a LinalgOp. |
| 206 | struct PackedOperandsDimList { |
| 207 | void pushBack(PackedOperandsDim &&packedOperandsDims) { |
| 208 | spec.emplace_back(Args&: packedOperandsDims); |
| 209 | } |
| 210 | /// Return all the dims that have been packed for operand @ `operandPos`. |
| 211 | SmallVector<int64_t> extractPackedDimsForOperand(int64_t operandPos); |
| 212 | /// Return all the pack sizes by which an operand @ `operandPos` is packed. |
| 213 | SmallVector<OpFoldResult> extractPackSizesForOperand(int64_t operandPos); |
| 214 | |
| 215 | private: |
| 216 | SmallVector<PackedOperandsDim> spec; |
| 217 | }; |
| 218 | |
| 219 | } // namespace |
| 220 | |
| 221 | /// Rewrite index operations in a packed Linalg op to preserve their values in |
| 222 | /// the original iteration space. Packing loop dimension `d` by `tileSize` |
| 223 | /// splits its index into an outer and inner index, so the original index is |
| 224 | /// `outer * tileSize + inner`. |
| 225 | static void |
| 226 | remapPackedIndexOps(RewriterBase &rewriter, LinalgOp packedLinalgOp, |
| 227 | ArrayRef<OpFoldResult> packedSizes, |
| 228 | ArrayRef<std::optional<int64_t>> packedLoopToInnerLoop) { |
| 229 | if (!packedLinalgOp.hasIndexSemantics()) |
| 230 | return; |
| 231 | |
| 232 | SmallVector<IndexOp> indexOps = |
| 233 | llvm::to_vector(Range: packedLinalgOp.getBlock()->getOps<IndexOp>()); |
| 234 | for (IndexOp indexOp : indexOps) { |
| 235 | unsigned dim = indexOp.getDim(); |
| 236 | assert(dim < packedLoopToInnerLoop.size() && "invalid linalg.index dim" ); |
| 237 | std::optional<int64_t> innerDim = packedLoopToInnerLoop[dim]; |
| 238 | if (!innerDim) |
| 239 | continue; |
| 240 | |
| 241 | OpBuilder::InsertionGuard guard(rewriter); |
| 242 | rewriter.setInsertionPoint(indexOp); |
| 243 | Value outerIndex = |
| 244 | IndexOp::create(builder&: rewriter, location: indexOp.getLoc(), dim).getResult(); |
| 245 | Value innerIndex = |
| 246 | IndexOp::create(builder&: rewriter, location: indexOp.getLoc(), dim: *innerDim).getResult(); |
| 247 | |
| 248 | AffineExpr outer, inner, tileSize; |
| 249 | bindDims(ctx: rewriter.getContext(), exprs&: outer, exprs&: inner); |
| 250 | bindSymbols(ctx: rewriter.getContext(), exprs&: tileSize); |
| 251 | OpFoldResult originalIndex = affine::makeComposedFoldedAffineApply( |
| 252 | b&: rewriter, loc: indexOp.getLoc(), expr: outer * tileSize + inner, |
| 253 | operands: {outerIndex, innerIndex, packedSizes[dim]}); |
| 254 | rewriter.replaceOp(op: indexOp, newValues: getValueOrCreateConstantIndexOp( |
| 255 | b&: rewriter, loc: indexOp.getLoc(), ofr: originalIndex)); |
| 256 | } |
| 257 | } |
| 258 | |
| 259 | FailureOr<LowerPackResult> linalg::lowerPack(RewriterBase &rewriter, |
| 260 | linalg::PackOp packOp, |
| 261 | bool lowerPadLikeWithInsertSlice) { |
| 262 | // Pack/unpack memref transformations are unsupported. The memref forms |
| 263 | // are mainly for bufferization and scalar lowering. Other uses are not |
| 264 | // recommended, see #225650 for details. |
| 265 | if (!packOp.hasPureTensorSemantics()) |
| 266 | return failure(); |
| 267 | |
| 268 | auto packedTensorType = |
| 269 | cast<RankedTensorType>(Val: packOp->getResultTypes().front()); |
| 270 | |
| 271 | Location loc = packOp->getLoc(); |
| 272 | OpBuilder::InsertionGuard g(rewriter); |
| 273 | rewriter.setInsertionPoint(packOp); |
| 274 | |
| 275 | // 2. Compute the permutation vector to shuffle packed shape into the shape |
| 276 | // before any outer or inner permutations have been applied. |
| 277 | PackingMetadata packingMetadata; |
| 278 | SmallVector<int64_t> packedToStripMinedShapePerm = |
| 279 | getPackInverseDestPerm(packOp, metadata&: packingMetadata); |
| 280 | |
| 281 | // 3. Compute the stripMinedShape: this is the packed shape before any outer |
| 282 | // or inner permutations have been applied. |
| 283 | SmallVector<int64_t> stripMinedShape(packedTensorType.getShape()); |
| 284 | applyPermutationToVector(inVec&: stripMinedShape, permutation: packedToStripMinedShapePerm); |
| 285 | |
| 286 | // Also compute the mixed (static+dynamic) strip-mined sizes for the |
| 287 | // expand_shape output. This is needed to support dynamic inner tile sizes, |
| 288 | // since the shapes cannot be inferred automatically when multiple dynamic |
| 289 | // dims appear in a single reassociation group during ExpandShapeOp |
| 290 | // construction. |
| 291 | SmallVector<OpFoldResult> stripMinedMixedSizes = |
| 292 | tensor::getMixedSizes(builder&: rewriter, loc, value: packOp.getDest()); |
| 293 | applyPermutationToVector(inVec&: stripMinedMixedSizes, permutation: packedToStripMinedShapePerm); |
| 294 | |
| 295 | // 4. Pad the source of packOp to a shape we can expand into stripMinedShape. |
| 296 | SmallVector<OpFoldResult> lows(packOp.getSourceRank(), |
| 297 | rewriter.getIndexAttr(value: 0)); |
| 298 | SmallVector<OpFoldResult> highs(packOp.getSourceRank(), |
| 299 | rewriter.getIndexAttr(value: 0)); |
| 300 | for (auto [pos, innerSize] : |
| 301 | llvm::zip_equal(t: packOp.getInnerDimsPos(), u: packOp.getMixedTiles())) { |
| 302 | int outerPos = |
| 303 | packedToStripMinedShapePerm[packingMetadata.outerPositions[pos]]; |
| 304 | OpFoldResult origSize = |
| 305 | tensor::getMixedSize(builder&: rewriter, loc, value: packOp.getSource(), dim: pos); |
| 306 | OpFoldResult outerSize = |
| 307 | tensor::getMixedSize(builder&: rewriter, loc, value: packOp.getDest(), dim: outerPos); |
| 308 | AffineExpr s0, d0, d1; |
| 309 | bindDims(ctx: rewriter.getContext(), exprs&: d0, exprs&: d1); |
| 310 | bindSymbols(ctx: rewriter.getContext(), exprs&: s0); |
| 311 | auto map = AffineMap::get(/*dimCount=*/2, /*symbolCount=*/1, result: d0 * s0 - d1); |
| 312 | highs[pos] = affine::makeComposedFoldedAffineApply( |
| 313 | b&: rewriter, loc, map, operands: {outerSize, origSize, innerSize}); |
| 314 | } |
| 315 | RankedTensorType collapsed = tensor::CollapseShapeOp::inferCollapsedType( |
| 316 | type: RankedTensorType::Builder(packedTensorType).setShape(stripMinedShape), |
| 317 | reassociation: packingMetadata.reassociations); |
| 318 | Value paddingValue = packOp.getPaddingValue(); |
| 319 | if (!paddingValue) { |
| 320 | paddingValue = arith::ConstantOp::create( |
| 321 | builder&: rewriter, location: loc, value: rewriter.getZeroAttr(type: getElementTypeOrSelf(type: collapsed))); |
| 322 | } |
| 323 | auto padOp = |
| 324 | tensor::PadOp::create(builder&: rewriter, location: loc, resultType: collapsed, source: packOp.getSource(), low: lows, |
| 325 | high: highs, constantPadValue: paddingValue, /*nofold=*/false); |
| 326 | |
| 327 | LDBG() << "insertPositions: " |
| 328 | << llvm::interleaved(R: packingMetadata.insertPositions); |
| 329 | LDBG() << "outerPositions: " |
| 330 | << llvm::interleaved(R: packingMetadata.outerPositions); |
| 331 | LDBG() << "packedShape: " << llvm::interleaved(R: packedTensorType.getShape()); |
| 332 | LDBG() << "packedToStripMinedShapePerm: " |
| 333 | << llvm::interleaved(R: packedToStripMinedShapePerm); |
| 334 | LDBG() << "reassociations: " |
| 335 | << llvm::interleaved(R: llvm::map_range(C&: packingMetadata.reassociations, |
| 336 | F: stringifyReassocIndices)); |
| 337 | LDBG() << "stripMinedShape: " << llvm::interleaved(R: stripMinedShape); |
| 338 | LDBG() << "collapsed type: " << collapsed; |
| 339 | |
| 340 | if (lowerPadLikeWithInsertSlice && packOp.isLikePad()) { |
| 341 | // Pack ops which operate as simple pads may not produce legal |
| 342 | // tensor.insert_slice operations when the packed type does not rank reduce |
| 343 | // to the padded type. |
| 344 | SliceVerificationResult rankReduces = |
| 345 | isRankReducedType(originalType: packedTensorType, candidateReducedType: padOp.getResultType()); |
| 346 | |
| 347 | if (rankReduces == SliceVerificationResult::Success) { |
| 348 | // This pack is just a plain pad. |
| 349 | // Just insert the pad in the higher ranked tensor. |
| 350 | // Offsets. |
| 351 | SmallVector<OpFoldResult> zeros(packOp.getDestRank(), |
| 352 | rewriter.getIndexAttr(value: 0)); |
| 353 | // Strides. |
| 354 | SmallVector<OpFoldResult> ones(packOp.getDestRank(), |
| 355 | rewriter.getIndexAttr(value: 1)); |
| 356 | SmallVector<OpFoldResult> sizes = |
| 357 | tensor::getMixedSizes(builder&: rewriter, loc, value: packOp.getDest()); |
| 358 | |
| 359 | auto insertSliceOp = tensor::InsertSliceOp::create( |
| 360 | builder&: rewriter, location: loc, /*source=*/padOp, /*dest=*/packOp.getDest(), |
| 361 | /*offsets=*/zeros, sizes, /*strides=*/ones); |
| 362 | |
| 363 | LDBG() << "insert_slice op: " << insertSliceOp; |
| 364 | |
| 365 | rewriter.replaceOp(op: packOp, newValues: insertSliceOp->getResults()); |
| 366 | |
| 367 | return LowerPackResult{.padOp: padOp, /*reshapeOp=*/.expandShapeOp: nullptr, |
| 368 | /*transposeOp=*/nullptr}; |
| 369 | } |
| 370 | } |
| 371 | |
| 372 | // 5. Expand from the padded result to the stripMinedShape. |
| 373 | auto expandShapeResultType = |
| 374 | RankedTensorType::Builder(packedTensorType).setShape(stripMinedShape); |
| 375 | auto reshapeOp = tensor::ExpandShapeOp::create( |
| 376 | builder&: rewriter, location: loc, resultType: expandShapeResultType, src: padOp.getResult(), |
| 377 | reassociation: packingMetadata.reassociations, outputShape: stripMinedMixedSizes); |
| 378 | |
| 379 | // 6. Transpose stripMinedShape to packedShape. |
| 380 | SmallVector<int64_t> transpPerm = |
| 381 | invertPermutationVector(permutation: packedToStripMinedShapePerm); |
| 382 | auto transposeOp = linalg::TransposeOp::create( |
| 383 | builder&: rewriter, location: loc, input: reshapeOp.getResult(), init: packOp.getDest(), permutation: transpPerm); |
| 384 | |
| 385 | LDBG() << "reshape op: " << reshapeOp; |
| 386 | LDBG() << "transpPerm: " << llvm::interleaved(R: transpPerm); |
| 387 | LDBG() << "transpose op: " << transposeOp; |
| 388 | |
| 389 | // 7. Replace packOp by transposeOp. |
| 390 | rewriter.replaceOp(op: packOp, newValues: transposeOp->getResults()); |
| 391 | |
| 392 | return LowerPackResult{.padOp: padOp, .expandShapeOp: reshapeOp, .transposeOp: transposeOp}; |
| 393 | } |
| 394 | |
| 395 | FailureOr<LowerUnPackOpResult> |
| 396 | linalg::lowerUnPack(RewriterBase &rewriter, linalg::UnPackOp unPackOp, |
| 397 | bool ) { |
| 398 | // Pack/unpack memref transformations are unsupported. The memref forms |
| 399 | // are mainly for bufferization and scalar lowering. Other uses are not |
| 400 | // recommended, see #225650 for details. |
| 401 | if (!unPackOp.hasPureTensorSemantics()) |
| 402 | return failure(); |
| 403 | |
| 404 | Location loc = unPackOp->getLoc(); |
| 405 | OpBuilder::InsertionGuard g(rewriter); |
| 406 | rewriter.setInsertionPoint(unPackOp); |
| 407 | |
| 408 | auto packedTensorType = cast<RankedTensorType>(Val: unPackOp.getSourceType()); |
| 409 | int64_t packedRank = packedTensorType.getRank(); |
| 410 | |
| 411 | OpFoldResult zero = rewriter.getIndexAttr(value: 0), one = rewriter.getIndexAttr(value: 1); |
| 412 | auto destTensorType = cast<RankedTensorType>(Val: unPackOp.getDest().getType()); |
| 413 | if (lowerUnpadLikeWithExtractSlice && unPackOp.isLikeUnPad()) { |
| 414 | // This unpack is just a plain unpad. |
| 415 | // Just extract the slice from the higher ranked tensor. |
| 416 | ArrayRef<int64_t> destShape = destTensorType.getShape(); |
| 417 | // The inner dimensions stay the same as the destination tensor, but the |
| 418 | // outer ones are additional 1s. |
| 419 | SmallVector<OpFoldResult> sizes(packedRank - destShape.size(), one); |
| 420 | sizes.append(RHS: tensor::getMixedSizes(builder&: rewriter, loc, value: unPackOp.getDest())); |
| 421 | |
| 422 | auto = tensor::ExtractSliceOp::create( |
| 423 | builder&: rewriter, location: loc, resultType: destTensorType, source: unPackOp.getSource(), |
| 424 | offsets: SmallVector<OpFoldResult>(packedRank, zero), sizes, |
| 425 | strides: SmallVector<OpFoldResult>(packedRank, one)); |
| 426 | |
| 427 | rewriter.replaceOp(op: unPackOp, newValues: extractSliceOp->getResults()); |
| 428 | |
| 429 | return LowerUnPackOpResult{/*emptyOp=*/nullptr, /*transposeOp=*/nullptr, |
| 430 | /*reshapeOp=*/.collapseShapeOp: nullptr, .extractSliceOp: extractSliceOp, |
| 431 | /*copyOp=*/nullptr}; |
| 432 | } |
| 433 | |
| 434 | // 1. Compute the permutation vector to shuffle packed shape into the shape |
| 435 | // before any outer or inner permutations have been applied. |
| 436 | PackingMetadata packingMetadata; |
| 437 | SmallVector<int64_t> packedToStripMinedShapePerm = |
| 438 | getUnPackInverseSrcPerm(unPackOp, metadata&: packingMetadata); |
| 439 | |
| 440 | // 2. Compute the stripMinedShape: this is the packed shape without outer and |
| 441 | // inner permutations. |
| 442 | SmallVector<int64_t> stripMinedShape(packedTensorType.getShape()); |
| 443 | applyPermutationToVector(inVec&: stripMinedShape, permutation: packedToStripMinedShapePerm); |
| 444 | |
| 445 | // 3. Transpose packedShape to stripMinedShape. |
| 446 | RankedTensorType stripMinedTensorType = |
| 447 | RankedTensorType::Builder(packedTensorType).setShape(stripMinedShape); |
| 448 | RankedTensorType collapsedType = tensor::CollapseShapeOp::inferCollapsedType( |
| 449 | type: stripMinedTensorType, reassociation: packingMetadata.reassociations); |
| 450 | |
| 451 | // Get dynamic dims from input tensor based on packedToStripMinedShapePerm |
| 452 | // permutation. |
| 453 | SmallVector<OpFoldResult, 4> dims = |
| 454 | tensor::getMixedSizes(builder&: rewriter, loc, value: unPackOp.getSource()); |
| 455 | applyPermutationToVector(inVec&: dims, permutation: packedToStripMinedShapePerm); |
| 456 | auto emptyOp = tensor::EmptyOp::create(builder&: rewriter, location: loc, sizes: dims, |
| 457 | elementType: stripMinedTensorType.getElementType()); |
| 458 | auto transposeOp = |
| 459 | linalg::TransposeOp::create(builder&: rewriter, location: loc, input: unPackOp.getSource(), init: emptyOp, |
| 460 | permutation: packedToStripMinedShapePerm); |
| 461 | |
| 462 | LDBG() << "insertPositions: " |
| 463 | << llvm::interleaved(R: packingMetadata.insertPositions); |
| 464 | LDBG() << "packedShape: " << llvm::interleaved(R: packedTensorType.getShape()); |
| 465 | LDBG() << "packedToStripMinedShapePerm: " |
| 466 | << llvm::interleaved(R: packedToStripMinedShapePerm); |
| 467 | LDBG() << "reassociations: " |
| 468 | << llvm::interleaved(R: llvm::map_range(C&: packingMetadata.reassociations, |
| 469 | F: stringifyReassocIndices)); |
| 470 | LDBG() << "stripMinedShape: " << llvm::interleaved(R: stripMinedShape); |
| 471 | LDBG() << "collapsed type: " << collapsedType; |
| 472 | |
| 473 | // 4. Collapse from the stripMinedShape to the padded result. |
| 474 | auto reshapeOp = tensor::CollapseShapeOp::create( |
| 475 | builder&: rewriter, location: loc, resultType: collapsedType, src: transposeOp->getResult(idx: 0), |
| 476 | reassociation: packingMetadata.reassociations); |
| 477 | |
| 478 | // 5. ExtractSlice. |
| 479 | int64_t destRank = destTensorType.getRank(); |
| 480 | auto = tensor::ExtractSliceOp::create( |
| 481 | builder&: rewriter, location: loc, resultType: destTensorType, source: reshapeOp->getResult(idx: 0), |
| 482 | offsets: SmallVector<OpFoldResult>(destRank, zero), |
| 483 | sizes: tensor::getMixedSizes(builder&: rewriter, loc, value: unPackOp.getDest()), |
| 484 | strides: SmallVector<OpFoldResult>(destRank, one)); |
| 485 | |
| 486 | // 6. Inject a copy to preserve DPS. |
| 487 | auto copyOp = linalg::CopyOp::create( |
| 488 | builder&: rewriter, location: loc, inputs: extractSliceOp->getResult(idx: 0), outputs: unPackOp.getDest()); |
| 489 | |
| 490 | // 7. Replace unPackOp by copyOp. |
| 491 | rewriter.replaceOp(op: unPackOp, newValues: copyOp->getResults()); |
| 492 | |
| 493 | return LowerUnPackOpResult{.emptyOp: emptyOp, .transposeOp: transposeOp, .collapseShapeOp: reshapeOp, .extractSliceOp: extractSliceOp, |
| 494 | .copyOp: copyOp}; |
| 495 | } |
| 496 | |
| 497 | SmallVector<int64_t> |
| 498 | PackedOperandsDimList::extractPackedDimsForOperand(int64_t operandPos) { |
| 499 | SmallVector<int64_t> res; |
| 500 | for (auto &i : spec) { |
| 501 | if (!i.packedDimForEachOperand[operandPos].has_value()) |
| 502 | continue; |
| 503 | res.push_back(Elt: i.packedDimForEachOperand[operandPos].value()); |
| 504 | } |
| 505 | return res; |
| 506 | } |
| 507 | |
| 508 | SmallVector<OpFoldResult> |
| 509 | PackedOperandsDimList::extractPackSizesForOperand(int64_t operandPos) { |
| 510 | SmallVector<OpFoldResult> res; |
| 511 | for (auto &i : spec) { |
| 512 | if (!i.packedDimForEachOperand[operandPos].has_value()) |
| 513 | continue; |
| 514 | res.push_back(Elt: i.packedSize); |
| 515 | } |
| 516 | return res; |
| 517 | } |
| 518 | |
| 519 | /// Implement packing of a single LinalgOp by performing packing by |
| 520 | /// `packedSizes`. There must be one packedSizes entry per `linalgOp` iterator. |
| 521 | /// Return the packed Linalg op on success, failure otherwise. |
| 522 | FailureOr<PackResult> linalg::pack(RewriterBase &rewriter, |
| 523 | linalg::LinalgOp linalgOp, |
| 524 | ArrayRef<OpFoldResult> packedSizes) { |
| 525 | if (packedSizes.size() != linalgOp.getNumLoops()) { |
| 526 | return rewriter.notifyMatchFailure(arg&: linalgOp, |
| 527 | msg: "incorrect number of pack sizes" ); |
| 528 | } |
| 529 | if (!linalgOp.hasPureTensorSemantics()) { |
| 530 | return rewriter.notifyMatchFailure( |
| 531 | arg&: linalgOp, msg: "expects LinalgOp with pure tensor semantics" ); |
| 532 | } |
| 533 | |
| 534 | Location loc = linalgOp->getLoc(); |
| 535 | SmallVector<AffineMap> indexingMaps = linalgOp.getIndexingMapsArray(); |
| 536 | SmallVector<utils::IteratorType> iteratorTypes = |
| 537 | linalgOp.getIteratorTypesArray(); |
| 538 | LDBG() << "Start packing: " << linalgOp; |
| 539 | LDBG() << "maps: " << llvm::interleaved(R: indexingMaps); |
| 540 | LDBG() << "iterators: " << llvm::interleaved(R: iteratorTypes); |
| 541 | |
| 542 | SmallVector<linalg::PackOp> packOps; |
| 543 | SmallVector<linalg::UnPackOp> unPackOps; |
| 544 | // Step 1. Pack each dim of the LinalgOp metadata by packedSizes[i]. |
| 545 | PackedOperandsDimList listOfPackedOperandsDim; |
| 546 | SmallVector<std::optional<int64_t>> packedLoopToInnerLoop(packedSizes.size()); |
| 547 | for (int64_t i = 0, e = packedSizes.size(); i < e; ++i) { |
| 548 | std::optional<int64_t> maybeConstant = getConstantIntValue(ofr: packedSizes[i]); |
| 549 | // Skip tile sizes explicitly set to 0. |
| 550 | if (maybeConstant.has_value() && maybeConstant.value() == 0) |
| 551 | continue; |
| 552 | |
| 553 | PackedOperandsDim packedOperandsDims; |
| 554 | packedOperandsDims.packedSize = packedSizes[i]; |
| 555 | FailureOr<SmallVector<std::optional<int64_t>>> |
| 556 | maybePackedDimForEachOperand = |
| 557 | packLinalgMetadataOnce(indexingMaps, iteratorTypes, dim: i); |
| 558 | if (failed(Result: maybePackedDimForEachOperand)) |
| 559 | return failure(); |
| 560 | packedLoopToInnerLoop[i] = iteratorTypes.size() - 1; |
| 561 | packedOperandsDims.packedDimForEachOperand = *maybePackedDimForEachOperand; |
| 562 | |
| 563 | LDBG() << "++++ After pack size #" << i << ": " << packedSizes[i]; |
| 564 | LDBG() << "maps: " << llvm::interleaved(R: indexingMaps); |
| 565 | LDBG() << "iterators: " << llvm::interleaved(R: iteratorTypes); |
| 566 | LDBG() << "packedDimForEachOperand: " |
| 567 | << llvm::interleaved(R: packedOperandsDims.packedDimForEachOperand); |
| 568 | |
| 569 | listOfPackedOperandsDim.pushBack(packedOperandsDims: std::move(packedOperandsDims)); |
| 570 | } |
| 571 | |
| 572 | // Step 2. Propagate packing to all LinalgOp operands. |
| 573 | SmallVector<Value> inputsAndInits, results; |
| 574 | SmallVector<OpOperand *> initOperands = |
| 575 | llvm::to_vector(Range: llvm::make_pointer_range(Range: linalgOp.getDpsInitsMutable())); |
| 576 | SmallVector<OpOperand *> inputOperands = linalgOp.getDpsInputOperands(); |
| 577 | for (const auto &operandsList : {inputOperands, initOperands}) { |
| 578 | for (OpOperand *opOperand : operandsList) { |
| 579 | int64_t pos = opOperand->getOperandNumber(); |
| 580 | Value operand = opOperand->get(); |
| 581 | SmallVector<int64_t> innerPos = |
| 582 | listOfPackedOperandsDim.extractPackedDimsForOperand(operandPos: pos); |
| 583 | SmallVector<OpFoldResult> innerPackSizes = |
| 584 | listOfPackedOperandsDim.extractPackSizesForOperand(operandPos: pos); |
| 585 | LDBG() << "operand: " << operand; |
| 586 | LDBG() << "innerPos: " << llvm::interleaved(R: innerPos); |
| 587 | LDBG() << "innerPackSizes: " << llvm::interleaved(R: innerPackSizes); |
| 588 | if (innerPackSizes.empty()) { |
| 589 | inputsAndInits.push_back(Elt: operand); |
| 590 | continue; |
| 591 | } |
| 592 | Value dest = linalg::PackOp::createDestinationTensor( |
| 593 | b&: rewriter, loc, source: operand, innerTileSizes: innerPackSizes, innerDimsPos: innerPos, |
| 594 | /*outerDimsPerm=*/{}); |
| 595 | ShapedType operandType = cast<ShapedType>(Val: operand.getType()); |
| 596 | bool areConstantTiles = |
| 597 | llvm::all_of(Range&: innerPackSizes, P: [](OpFoldResult tile) { |
| 598 | return getConstantIntValue(ofr: tile).has_value(); |
| 599 | }); |
| 600 | if (areConstantTiles && operandType.hasStaticShape() && |
| 601 | !linalg::PackOp::requirePaddingValue( |
| 602 | inputShape: operandType.getShape(), innerDimsPos: innerPos, |
| 603 | outputShape: cast<ShapedType>(Val: dest.getType()).getShape(), outerDimsPerm: {}, |
| 604 | innerTiles: innerPackSizes)) { |
| 605 | packOps.push_back(Elt: linalg::PackOp::create(builder&: rewriter, location: loc, source: operand, dest, |
| 606 | innerDimsPos: innerPos, innerTiles: innerPackSizes)); |
| 607 | } else { |
| 608 | // TODO: value of the padding attribute should be determined by |
| 609 | // consumers. |
| 610 | auto zeroAttr = |
| 611 | rewriter.getZeroAttr(type: getElementTypeOrSelf(type: dest.getType())); |
| 612 | Value zero = arith::ConstantOp::create(builder&: rewriter, location: loc, value: zeroAttr); |
| 613 | packOps.push_back(Elt: linalg::PackOp::create( |
| 614 | builder&: rewriter, location: loc, source: operand, dest, innerDimsPos: innerPos, innerTiles: innerPackSizes, paddingValue: zero)); |
| 615 | } |
| 616 | inputsAndInits.push_back(Elt: packOps.back().getResult()); |
| 617 | } |
| 618 | } |
| 619 | |
| 620 | // Step 3. Build the packed op, use the type of `inits` as result types. |
| 621 | ValueRange inputs = |
| 622 | ValueRange{inputsAndInits}.take_front(n: linalgOp.getNumDpsInputs()); |
| 623 | ValueRange inits = |
| 624 | ValueRange{inputsAndInits}.take_back(n: linalgOp.getNumDpsInits()); |
| 625 | auto packedLinalgOp = |
| 626 | linalg::GenericOp::create(builder&: rewriter, location: linalgOp.getLoc(), resultTensorTypes: inits.getTypes(), |
| 627 | inputs, outputs: inits, indexingMaps, iteratorTypes); |
| 628 | packedLinalgOp.getRegion().takeBody(other&: linalgOp->getRegion(index: 0)); |
| 629 | remapPackedIndexOps(rewriter, packedLinalgOp, packedSizes, |
| 630 | packedLoopToInnerLoop); |
| 631 | |
| 632 | // Step 4. Propagate packing to all the op results. |
| 633 | for (OpResult result : packedLinalgOp->getResults()) { |
| 634 | int64_t resultNum = result.getResultNumber(); |
| 635 | linalg::PackOp maybePackedInit = |
| 636 | inits[resultNum].getDefiningOp<linalg::PackOp>(); |
| 637 | if (!maybePackedInit) { |
| 638 | results.push_back(Elt: result); |
| 639 | continue; |
| 640 | } |
| 641 | // Build the symmetrical UnPackOp to the existing PackOp. |
| 642 | unPackOps.push_back(Elt: linalg::UnPackOp::create( |
| 643 | builder&: rewriter, location: packedLinalgOp->getLoc(), source: result, dest: maybePackedInit.getSource(), |
| 644 | innerDimsPos: maybePackedInit.getInnerDimsPos(), innerTiles: maybePackedInit.getMixedTiles())); |
| 645 | results.push_back(Elt: unPackOps.back().getResult()); |
| 646 | } |
| 647 | |
| 648 | // Step 5. Replace `linalgOp`. |
| 649 | rewriter.replaceOp(op: linalgOp, newValues: results); |
| 650 | |
| 651 | // Return packedLinalgOp. |
| 652 | return PackResult{.packOps: packOps, |
| 653 | .packedLinalgOp: cast<linalg::LinalgOp>(Val: packedLinalgOp.getOperation()), |
| 654 | .unPackOps: unPackOps}; |
| 655 | } |
| 656 | |
| 657 | //===----------------------------------------------------------------------===// |
| 658 | // packTranspose transformation. |
| 659 | //===----------------------------------------------------------------------===// |
| 660 | |
| 661 | /// Return a copy of `tensorType` after permutation by `permutationVector`. |
| 662 | // Note: Should be a new method in of MemRef/RankedTensor/VectorType::Builder |
| 663 | // but this would introduce a dependence on Dialect in IR. |
| 664 | // TODO: Restructure. |
| 665 | static RankedTensorType permuteShape(RankedTensorType tensorType, |
| 666 | ArrayRef<int64_t> permutationVector) { |
| 667 | SmallVector<int64_t> shape(tensorType.getShape()); |
| 668 | applyPermutationToVector(inVec&: shape, permutation: permutationVector); |
| 669 | return RankedTensorType::Builder(tensorType).setShape(shape); |
| 670 | } |
| 671 | |
| 672 | /// Return a new GenericOp obtained by transposing opOperand by the permutation |
| 673 | /// vector: |
| 674 | /// - the corresponding indexing map is transposed by `permutation` |
| 675 | /// - the corresponding operand value is replaced by `transposedValue` |
| 676 | /// `linalgOp` is replaced by the return op in the process. |
| 677 | /// Asserts that `transposedValue` is of the proper transposed ShapedType. |
| 678 | static LinalgOp transposeOneLinalgOperandAndReplace( |
| 679 | RewriterBase &rewriter, LinalgOp linalgOp, OpOperand &opOperand, |
| 680 | ArrayRef<int64_t> permutation, Value transposedValue) { |
| 681 | // Sanity check the operand. |
| 682 | assert(linalgOp == opOperand.getOwner() && "linalg op must own the operand" ); |
| 683 | |
| 684 | // Sanity check of the expected transposed tensor type. |
| 685 | auto tensorType = permuteShape( |
| 686 | tensorType: cast<RankedTensorType>(Val: opOperand.get().getType()), permutationVector: permutation); |
| 687 | (void)tensorType; |
| 688 | assert(tensorType == transposedValue.getType() && |
| 689 | "expected tensor type mismatch" ); |
| 690 | |
| 691 | // Compute the transposed indexing map. |
| 692 | // Sigh unsigned pollution. |
| 693 | SmallVector<unsigned> tmpTransposition = |
| 694 | llvm::map_to_vector(C&: permutation, F: [](int64_t i) -> unsigned { return i; }); |
| 695 | AffineMap permutationMap = |
| 696 | AffineMap::getPermutationMap(permutation: tmpTransposition, context: rewriter.getContext()); |
| 697 | AffineMap transposedMap = |
| 698 | permutationMap.compose(map: linalgOp.getMatchingIndexingMap(opOperand: &opOperand)); |
| 699 | |
| 700 | // Set the transposed indexing map in the proper position. |
| 701 | SmallVector<AffineMap> indexingMaps = linalgOp.getIndexingMapsArray(); |
| 702 | indexingMaps[linalgOp.getIndexingMapIndex(opOperand: &opOperand)] = transposedMap; |
| 703 | // Set the transposedValue in the proper operand position. |
| 704 | SmallVector<Value> operands = linalgOp->getOperands(); |
| 705 | operands[opOperand.getOperandNumber()] = transposedValue; |
| 706 | |
| 707 | ValueRange operandsRef(operands); |
| 708 | auto transposedGenericOp = linalg::GenericOp::create( |
| 709 | builder&: rewriter, |
| 710 | /*location=*/linalgOp->getLoc(), |
| 711 | /*resultTensorTypes=*/ |
| 712 | operandsRef.drop_front(n: linalgOp.getNumDpsInputs()).getTypes(), |
| 713 | /*inputs=*/operandsRef.take_front(n: linalgOp.getNumDpsInputs()), |
| 714 | /*outputs=*/operandsRef.drop_front(n: linalgOp.getNumDpsInputs()), |
| 715 | /*indexingMaps=*/indexingMaps, |
| 716 | /*iteratorTypes=*/linalgOp.getIteratorTypesArray()); |
| 717 | transposedGenericOp.getRegion().takeBody(other&: linalgOp->getRegion(index: 0)); |
| 718 | rewriter.replaceOp(op: linalgOp, newValues: transposedGenericOp->getResults()); |
| 719 | |
| 720 | return cast<linalg::LinalgOp>(Val: transposedGenericOp.getOperation()); |
| 721 | } |
| 722 | |
| 723 | FailureOr<PackTransposeResult> |
| 724 | linalg::packTranspose(RewriterBase &rewriter, linalg::PackOp packOp, |
| 725 | linalg::LinalgOp linalgOp, linalg::UnPackOp maybeUnPackOp, |
| 726 | ArrayRef<int64_t> outerPerm, |
| 727 | ArrayRef<int64_t> innerPerm) { |
| 728 | Location loc = linalgOp.getLoc(); |
| 729 | |
| 730 | // Step 1. Transpose packOp. |
| 731 | rewriter.setInsertionPoint(packOp); |
| 732 | linalg::PackOp transposedPackOp = |
| 733 | packOp.createTransposedClone(b&: rewriter, loc, innerPermutation: innerPerm, outerPermutation: outerPerm); |
| 734 | |
| 735 | if (packOp.hasPureBufferSemantics() || !packOp.getResult().hasOneUse()) |
| 736 | return rewriter.notifyMatchFailure(arg&: linalgOp, msg: "expect single pack use" ); |
| 737 | |
| 738 | OpOperand &packUse = *packOp->getUses().begin(); |
| 739 | if (packUse.getOwner() != linalgOp) { |
| 740 | return rewriter.notifyMatchFailure( |
| 741 | arg&: linalgOp, msg: "not a single use by the LinalgOp target" ); |
| 742 | } |
| 743 | if (maybeUnPackOp && |
| 744 | (!linalgOp.isDpsInit(opOperand: &packUse) || |
| 745 | maybeUnPackOp.getSource() != linalgOp.getTiedOpResult(opOperand: &packUse))) { |
| 746 | return rewriter.notifyMatchFailure(arg&: linalgOp, |
| 747 | msg: "not produced by the LinalgOp target" ); |
| 748 | } |
| 749 | |
| 750 | // Step 2. Transpose linalgOp. |
| 751 | // transposedPackOp.getOuterDimsPerm() may be empty, in which case it is the |
| 752 | // identity. Don't rely on it. |
| 753 | int64_t numLeadingDims = packOp.getSourceRank(); |
| 754 | int64_t numTrailingDims = packOp.getInnerDimsPos().size(); |
| 755 | // Step 2.a. Compute the permutation on the whole operand. |
| 756 | // Leading part just reuse the outerPerm. |
| 757 | SmallVector<int64_t> permutation(outerPerm); |
| 758 | if (permutation.empty()) |
| 759 | llvm::append_range(C&: permutation, R: llvm::seq<int64_t>(Begin: 0, End: numLeadingDims)); |
| 760 | // Trailing part needs to reindex positions by `numLeadingDims`. |
| 761 | if (innerPerm.empty()) { |
| 762 | llvm::append_range( |
| 763 | C&: permutation, |
| 764 | R: llvm::seq<int64_t>(Begin: numLeadingDims, End: numLeadingDims + numTrailingDims)); |
| 765 | } else { |
| 766 | llvm::append_range(C&: permutation, |
| 767 | R: llvm::map_range(C&: innerPerm, F: [&](int64_t pos) { |
| 768 | return numLeadingDims + pos; |
| 769 | })); |
| 770 | } |
| 771 | if (!isPermutationVector(interchange: permutation)) |
| 772 | return rewriter.notifyMatchFailure(arg&: linalgOp, msg: "invalid permutation" ); |
| 773 | |
| 774 | // Step 2.b. Save the transposedPackUse operand number in case we need to |
| 775 | // get the tied OpResult after `linalgOp` has been replaced. |
| 776 | int64_t packUseOperandNumber = packUse.getOperandNumber(); |
| 777 | // Step 2.c. Actually perform the transposition. |
| 778 | rewriter.setInsertionPoint(linalgOp); |
| 779 | linalg::LinalgOp transposedLinalgOp = transposeOneLinalgOperandAndReplace( |
| 780 | rewriter, linalgOp, opOperand&: packUse, permutation, transposedValue: transposedPackOp.getResult()); |
| 781 | |
| 782 | // Step 3. Maybe transpose unPackOp. |
| 783 | linalg::UnPackOp transposedUnPackOp; |
| 784 | if (maybeUnPackOp) { |
| 785 | OpOperand &opOperand = |
| 786 | transposedLinalgOp->getOpOperand(idx: packUseOperandNumber); |
| 787 | OpResult transposedResult = transposedLinalgOp.getTiedOpResult(opOperand: &opOperand); |
| 788 | rewriter.setInsertionPoint(maybeUnPackOp); |
| 789 | transposedUnPackOp = maybeUnPackOp.createTransposedClone( |
| 790 | b&: rewriter, loc, transposedSource: transposedResult, innerPermutation: innerPerm, outerPermutation: outerPerm); |
| 791 | |
| 792 | rewriter.replaceOp(op: maybeUnPackOp, newValues: transposedUnPackOp->getResults()); |
| 793 | } |
| 794 | |
| 795 | // Step 4. Finally, replace packOp now that we don't need it anymore. |
| 796 | if (packOp.hasPureTensorSemantics()) |
| 797 | rewriter.replaceOp(op: packOp, newValues: transposedPackOp->getResults()); |
| 798 | else |
| 799 | rewriter.eraseOp(op: packOp); |
| 800 | |
| 801 | return PackTransposeResult{.transposedPackOp: transposedPackOp, .transposedLinalgOp: transposedLinalgOp, |
| 802 | .transposedUnPackOp: transposedUnPackOp}; |
| 803 | } |
| 804 | |
| 805 | //===----------------------------------------------------------------------===// |
| 806 | // packMatmulGreedily transformation. |
| 807 | //===----------------------------------------------------------------------===// |
| 808 | |
| 809 | /// Pack a LinalgOp by greedily inferring matmul dimensions (m, n, k) where m |
| 810 | /// and n are proper parallel dimensions and k is a proper reduction |
| 811 | /// dimension. Packing occurs by rewriting the op as a linalg.generic and |
| 812 | /// calling linalg::pack by `mnkPackedSizes`. The order of the packed |
| 813 | /// dimensions is customizable: the `mnkOrder` is a permutation of {0, 1, 2} |
| 814 | /// to reorder {m, n, k} into one of the 8 possible forms. The outer |
| 815 | /// dimensions of the operands are not permuted at this time, this is left for |
| 816 | /// future work. |
| 817 | FailureOr<PackResult> |
| 818 | linalg::packMatmulGreedily(RewriterBase &rewriter, LinalgOp linalgOp, |
| 819 | ArrayRef<OpFoldResult> mnkPackedSizes, |
| 820 | ArrayRef<int64_t> mnkPaddedSizesNextMultipleOf, |
| 821 | ArrayRef<int64_t> mnkOrder) { |
| 822 | assert(mnkPackedSizes.size() == 3 && "unexpected num of packing sizes" ); |
| 823 | assert((mnkPaddedSizesNextMultipleOf.empty() || |
| 824 | mnkPaddedSizesNextMultipleOf.size() == 3) && |
| 825 | "num of packing sizes next multiple should be empty or of size 3" ); |
| 826 | assert(mnkOrder.size() == 3 && "unexpected mnkOrder size" ); |
| 827 | assert(isPermutationVector(mnkOrder) && "expected a permutation" ); |
| 828 | |
| 829 | int64_t numLoops = linalgOp.getNumLoops(); |
| 830 | if (numLoops <= 2) { |
| 831 | LDBG() << "need 3+ loops to find a matmul to pack, got " << numLoops |
| 832 | << " in: " << linalgOp; |
| 833 | return rewriter.notifyMatchFailure( |
| 834 | arg&: linalgOp, msg: "need 3+ loops to find a matmul to pack" ); |
| 835 | } |
| 836 | |
| 837 | // Locally adjust the desired iterator position of mnk and packing sizes. |
| 838 | int64_t numPackedDims = mnkPackedSizes.size(); |
| 839 | SmallVector<int64_t> mmnnkkPos(numPackedDims); |
| 840 | for (int64_t i = 0, e = numPackedDims; i < e; ++i) |
| 841 | mmnnkkPos[i] = numLoops - numPackedDims + mnkOrder[i]; |
| 842 | SmallVector<OpFoldResult> packedSizes(numPackedDims); |
| 843 | for (int64_t i = 0, e = numPackedDims; i < e; ++i) |
| 844 | packedSizes[mnkOrder[i]] = mnkPackedSizes[i]; |
| 845 | SmallVector<int64_t> paddedSizesNextMultipleOf(numPackedDims); |
| 846 | for (int64_t i = 0, e = numPackedDims; i < e; ++i) { |
| 847 | paddedSizesNextMultipleOf[mnkOrder[i]] = |
| 848 | mnkPaddedSizesNextMultipleOf.empty() ? 0 |
| 849 | : mnkPaddedSizesNextMultipleOf[i]; |
| 850 | } |
| 851 | |
| 852 | // 1. Infer dims that are important for matmul. |
| 853 | FailureOr<ContractionDimensions> maybeDimensions = |
| 854 | inferContractionDims(linalgOp); |
| 855 | if (failed(Result: maybeDimensions)) { |
| 856 | LDBG() << "couldn't infer matmul iterators in: " << linalgOp; |
| 857 | return rewriter.notifyMatchFailure(arg&: linalgOp, |
| 858 | msg: "couldn't infer matmul iterators" ); |
| 859 | } |
| 860 | |
| 861 | // 2. Normalize linalgOp to an kmn-matmul-like with [red, par, par] most |
| 862 | // minor iterators. In cases with multiple options for m, n, k bias towards |
| 863 | // the most minor embedding. |
| 864 | // If we wanted a different normalization order, this is where it would have |
| 865 | // to plug a heuristic. |
| 866 | int64_t mPos = maybeDimensions->m.back(), nPos = maybeDimensions->n.back(), |
| 867 | kPos = maybeDimensions->k.back(); |
| 868 | LDBG() << "Start packing generic op greedily with (m@" << mPos << ", n@" |
| 869 | << nPos << ", k@" << kPos << "): " << linalgOp; |
| 870 | |
| 871 | // 2.a. Rewrite as a generic. |
| 872 | auto genericOp = dyn_cast<GenericOp>(Val: linalgOp.getOperation()); |
| 873 | if (!genericOp) { |
| 874 | FailureOr<LinalgOp> generalizeResult = |
| 875 | generalizeNamedOp(rewriter, linalgOp); |
| 876 | assert(succeeded(generalizeResult) && |
| 877 | isa<GenericOp>(generalizeResult->getOperation()) && |
| 878 | "unexpected failure generalizing op" ); |
| 879 | genericOp = cast<GenericOp>(Val: generalizeResult->getOperation()); |
| 880 | } |
| 881 | |
| 882 | // 2.b. Interchange to move the dimensions (k, m, n) as most-minor |
| 883 | // iterators. Note that this only normalized the iteration order and does |
| 884 | // not change the indexings of any operand. |
| 885 | SmallVector<int64_t> permutation = |
| 886 | computePermutationVector(permSize: numLoops, positions: {mPos, nPos, kPos}, desiredPositions: mmnnkkPos); |
| 887 | LDBG() << "perm: " << llvm::interleaved(R: permutation); |
| 888 | // Sign .. unsigned pollution. |
| 889 | SmallVector<unsigned> unsignedPerm(permutation.begin(), permutation.end()); |
| 890 | FailureOr<GenericOp> interchangeResult = |
| 891 | interchangeGenericOp(rewriter, genericOp, interchangeVector: unsignedPerm); |
| 892 | assert(succeeded(interchangeResult) && "unexpected failure interchanging op" ); |
| 893 | genericOp = *interchangeResult; |
| 894 | LDBG() << "Generalized Op to pack: " << genericOp; |
| 895 | |
| 896 | // At this point, the op iterators are normalized to {leading, k, m, n}. |
| 897 | // The layouts induced by packing will always be: |
| 898 | // - LHS{leading_lhs, kk, mm} |
| 899 | // - RHS{leading_rhs, kk, nn} |
| 900 | // - RES{leading_res, mm, nn} |
| 901 | // If we wanted to change the packed order, we would reorder (k, m, n) to |
| 902 | // something else above. |
| 903 | // |
| 904 | // Additional permutations of the outer dims of the operands (i.e. |
| 905 | // leading_lhs, leading_rhs and leading_res) could follow by computing the |
| 906 | // desired outerPerm for each operand. |
| 907 | // This is left for future work. |
| 908 | |
| 909 | // TODO: this creates too much IR, go use reifyResultShapes. |
| 910 | SmallVector<Range, 4> loopRanges = |
| 911 | cast<LinalgOp>(Val: genericOp.getOperation()) |
| 912 | .createLoopRanges(b&: rewriter, loc: genericOp.getLoc()); |
| 913 | |
| 914 | // Add leading zeros to match numLoops, we only pack the last 3 dimensions |
| 915 | // post interchange. |
| 916 | LDBG() << "paddedSizesNextMultipleOf: " |
| 917 | << llvm::interleaved(R: paddedSizesNextMultipleOf); |
| 918 | LDBG() << "loopRanges: " |
| 919 | << llvm::interleaved( |
| 920 | R: llvm::map_range(C&: loopRanges, F: [](Range r) { return r.size; })); |
| 921 | SmallVector<OpFoldResult> adjustedPackedSizes(numLoops - packedSizes.size(), |
| 922 | rewriter.getIndexAttr(value: 0)); |
| 923 | for (int64_t i = 0, e = numPackedDims; i < e; ++i) { |
| 924 | if (paddedSizesNextMultipleOf[i] == 0) { |
| 925 | adjustedPackedSizes.push_back(Elt: packedSizes[i]); |
| 926 | continue; |
| 927 | } |
| 928 | AffineExpr d0, s0; |
| 929 | bindDims(ctx: rewriter.getContext(), exprs&: d0); |
| 930 | bindSymbols(ctx: rewriter.getContext(), exprs&: s0); |
| 931 | adjustedPackedSizes.push_back(Elt: affine::makeComposedFoldedAffineApply( |
| 932 | b&: rewriter, loc: genericOp->getLoc(), expr: d0.ceilDiv(other: s0) * s0, |
| 933 | operands: {loopRanges[adjustedPackedSizes.size()].size, |
| 934 | rewriter.getIndexAttr(value: paddedSizesNextMultipleOf[i])})); |
| 935 | } |
| 936 | LDBG() << "adjustedPackedSizes: " << llvm::interleaved(R: adjustedPackedSizes); |
| 937 | |
| 938 | // TODO: If we wanted to give the genericOp a name after packing, after |
| 939 | // calling `pack` would be a good time. One would still need to check that |
| 940 | // `containsMostMinorMatmul(packingRes->packedLinalgOp)` is true, since we |
| 941 | // also allow degenerate matmul cases (i.e. matvec, dot). |
| 942 | return pack(rewriter, linalgOp: genericOp, packedSizes: adjustedPackedSizes); |
| 943 | } |
| 944 | |
| 945 | //===----------------------------------------------------------------------===// |
| 946 | // Transformations exposed as rewrite patterns. |
| 947 | //===----------------------------------------------------------------------===// |
| 948 | |
| 949 | LinalgTilingOptions & |
| 950 | mlir::linalg::LinalgTilingOptions::setTileSizes(ArrayRef<int64_t> ts) { |
| 951 | assert(!tileSizeComputationFunction && "tile sizes already set" ); |
| 952 | SmallVector<int64_t, 4> tileSizes(ts); |
| 953 | tileSizeComputationFunction = [tileSizes](OpBuilder &b, Operation *op) { |
| 954 | OpBuilder::InsertionGuard guard(b); |
| 955 | b.setInsertionPointToStart( |
| 956 | &op->getParentOfType<func::FuncOp>().getBody().front()); |
| 957 | return llvm::map_to_vector<4>(C: tileSizes, F: [&](int64_t s) { |
| 958 | Value v = arith::ConstantIndexOp::create(builder&: b, location: op->getLoc(), value: s); |
| 959 | return v; |
| 960 | }); |
| 961 | }; |
| 962 | return *this; |
| 963 | } |
| 964 | |
| 965 | LogicalResult mlir::linalg::CopyVectorizationPattern::matchAndRewrite( |
| 966 | memref::CopyOp copyOp, PatternRewriter &rewriter) const { |
| 967 | return vectorizeCopy(builder&: rewriter, copyOp); |
| 968 | } |
| 969 | |
| 970 | /// Filling `dest` using FillOp constant padding value if possible. |
| 971 | /// Otherwise, generate a tensor::GenerateOp. |
| 972 | Value DecomposePadOpPattern::createFillOrGenerateOp( |
| 973 | RewriterBase &rewriter, tensor::PadOp padOp, Value dest, |
| 974 | const SmallVector<Value> &dynSizes) const { |
| 975 | auto padValue = padOp.getConstantPaddingValue(); |
| 976 | if (padValue) { |
| 977 | // Move the padding value defined inside the PadOp block to outside. |
| 978 | if (padValue.getParentBlock() == &padOp.getRegion().front()) |
| 979 | rewriter.moveOpBefore(op: padValue.getDefiningOp(), existingOp: padOp); |
| 980 | return FillOp::create(builder&: rewriter, location: padOp.getLoc(), inputs: padValue, outputs: dest).result(); |
| 981 | } |
| 982 | |
| 983 | // Fill could not be optimized: Lower to tensor::GenerateOp with region. |
| 984 | auto generateOp = tensor::GenerateOp::create(builder&: rewriter, location: padOp.getLoc(), |
| 985 | result: padOp.getResultType(), dynamicExtents: dynSizes); |
| 986 | // Copy region to new op. |
| 987 | IRMapping bvm; |
| 988 | padOp.getRegion().cloneInto(dest: &generateOp.getRegion(), mapper&: bvm); |
| 989 | return generateOp; |
| 990 | } |
| 991 | |
| 992 | LogicalResult |
| 993 | DecomposePadOpPattern::matchAndRewrite(tensor::PadOp padOp, |
| 994 | PatternRewriter &rewriter) const { |
| 995 | // Given an OpFoldResult, return an index-typed value. |
| 996 | auto getIdxValue = [&](OpFoldResult ofr) { |
| 997 | if (auto val = llvm::dyn_cast_if_present<Value>(Val&: ofr)) |
| 998 | return val; |
| 999 | return arith::ConstantIndexOp::create( |
| 1000 | builder&: rewriter, location: padOp.getLoc(), |
| 1001 | value: cast<IntegerAttr>(Val: cast<Attribute>(Val&: ofr)).getInt()) |
| 1002 | .getResult(); |
| 1003 | }; |
| 1004 | |
| 1005 | auto resultType = padOp.getResultType(); |
| 1006 | // Compute size of EmptyOp. Any combination of static/dynamic is supported. |
| 1007 | SmallVector<Value> dynSizes; |
| 1008 | SmallVector<int64_t> staticSizes; |
| 1009 | for (unsigned dim = 0; dim < resultType.getRank(); ++dim) { |
| 1010 | if (resultType.isDynamicDim(idx: dim)) { |
| 1011 | auto srcSize = getIdxValue(tensor::getMixedSize(builder&: rewriter, loc: padOp.getLoc(), |
| 1012 | value: padOp.getSource(), dim)); |
| 1013 | // Add low and high padding value. |
| 1014 | auto plusLow = rewriter.createOrFold<arith::AddIOp>( |
| 1015 | location: padOp.getLoc(), args&: srcSize, args: getIdxValue(padOp.getMixedLowPad()[dim])); |
| 1016 | auto plusHigh = rewriter.createOrFold<arith::AddIOp>( |
| 1017 | location: padOp.getLoc(), args&: plusLow, args: getIdxValue(padOp.getMixedHighPad()[dim])); |
| 1018 | dynSizes.push_back(Elt: plusHigh); |
| 1019 | } |
| 1020 | staticSizes.push_back(Elt: resultType.getDimSize(idx: dim)); |
| 1021 | } |
| 1022 | |
| 1023 | // Init tensor and fill it with padding. |
| 1024 | Value emptyTensor = |
| 1025 | tensor::EmptyOp::create(builder&: rewriter, location: padOp.getLoc(), staticShape: staticSizes, |
| 1026 | elementType: resultType.getElementType(), dynamicSizes: dynSizes); |
| 1027 | Value fill = createFillOrGenerateOp(rewriter, padOp, dest: emptyTensor, dynSizes); |
| 1028 | |
| 1029 | // Generate a InsertSliceOp for copying the PadOp source. |
| 1030 | auto sourceType = padOp.getSourceType(); |
| 1031 | // Compute size of source of tensor::PadOp. |
| 1032 | SmallVector<OpFoldResult> srcSizes = |
| 1033 | tensor::getMixedSizes(builder&: rewriter, loc: padOp.getLoc(), value: padOp.getSource()); |
| 1034 | // Strides of InsertSliceOp are all 1. |
| 1035 | SmallVector<OpFoldResult> strides(sourceType.getRank(), |
| 1036 | rewriter.getIndexAttr(value: 1)); |
| 1037 | rewriter.replaceOpWithNewOp<tensor::InsertSliceOp>( |
| 1038 | op: padOp, args: padOp.getSource(), args&: fill, args: padOp.getMixedLowPad(), args&: srcSizes, |
| 1039 | args&: strides); |
| 1040 | |
| 1041 | return success(); |
| 1042 | } |
| 1043 | |
| 1044 | LogicalResult ExtractSliceOfPadTensorSwapPattern::matchAndRewrite( |
| 1045 | tensor::ExtractSliceOp sliceOp, PatternRewriter &rewriter) const { |
| 1046 | if (!sliceOp.hasUnitStride()) |
| 1047 | return failure(); |
| 1048 | |
| 1049 | auto padOp = sliceOp.getSource().getDefiningOp<tensor::PadOp>(); |
| 1050 | if (!padOp) |
| 1051 | return failure(); |
| 1052 | |
| 1053 | bool zeroSliceGuard = true; |
| 1054 | if (controlFn) { |
| 1055 | if (std::optional<bool> control = controlFn(sliceOp)) |
| 1056 | zeroSliceGuard = *control; |
| 1057 | else |
| 1058 | return failure(); |
| 1059 | } |
| 1060 | |
| 1061 | FailureOr<TilingResult> tilingResult = |
| 1062 | tensor::bubbleUpPadSlice(b&: rewriter, padOp, offsets: sliceOp.getMixedOffsets(), |
| 1063 | sizes: sliceOp.getMixedSizes(), generateZeroSliceGuard: zeroSliceGuard); |
| 1064 | if (failed(Result: tilingResult)) |
| 1065 | return failure(); |
| 1066 | |
| 1067 | RankedTensorType sourceType = sliceOp.getSourceType(); |
| 1068 | RankedTensorType resultType = sliceOp.getResultType(); |
| 1069 | |
| 1070 | // If the extract_slice is not rank-reduced, all shapes are static and the |
| 1071 | // data source is actually used. Rewrite into pad(extract_slice(x)). |
| 1072 | if (sourceType.getRank() == resultType.getRank()) { |
| 1073 | rewriter.replaceOp(op: sliceOp, newValues: tilingResult->tiledValues); |
| 1074 | return success(); |
| 1075 | } |
| 1076 | |
| 1077 | // Handle rank-reduced slice by creating another extract_slice op. |
| 1078 | Value rankReduced = tensor::createCanonicalRankReducingExtractSliceOp( |
| 1079 | b&: rewriter, loc: sliceOp.getLoc(), tensor: tilingResult->tiledValues[0], targetType: resultType); |
| 1080 | |
| 1081 | rewriter.replaceOp(op: sliceOp, newValues: rankReduced); |
| 1082 | return success(); |
| 1083 | } |
| 1084 | |
| 1085 | /// If padding value is set, returns a tensor.pad Op for the source tensor, |
| 1086 | /// with the output shape matching the output of `packOp`. Otherwise, returns |
| 1087 | /// the source directly. |
| 1088 | /// |
| 1089 | /// This method assumes that all outer dims for this pack Op are 1. |
| 1090 | static Value getPackOpSourceOrPaddedSource(OpBuilder &builder, |
| 1091 | linalg::PackOp packOp) { |
| 1092 | Value input = packOp.getSource(); |
| 1093 | // Pack/unpack memref transformations are unsupported. The memref forms |
| 1094 | // are mainly for bufferization and scalar lowering. Other uses are not |
| 1095 | // recommended, see #225650 for details. |
| 1096 | if (!packOp.hasPureTensorSemantics()) |
| 1097 | return input; |
| 1098 | |
| 1099 | if (!packOp.getPaddingValue()) { |
| 1100 | return input; |
| 1101 | } |
| 1102 | |
| 1103 | assert(llvm::all_of(packOp.getAllOuterDims(), |
| 1104 | [](int64_t val) { return val == 1; }) && |
| 1105 | "some outer dims are != 1" ); |
| 1106 | |
| 1107 | Location loc = packOp.getLoc(); |
| 1108 | ShapedType inputType = packOp.getSourceType(); |
| 1109 | int64_t inputRank = inputType.getRank(); |
| 1110 | |
| 1111 | DenseMap<int64_t, OpFoldResult> tileAndPosMapping = |
| 1112 | packOp.getDimAndTileMapping(); |
| 1113 | |
| 1114 | // The sizes of dynamic tiles |
| 1115 | SmallVector<Value> dynamicTileSizes; |
| 1116 | |
| 1117 | // Collect dims for the padded shape. |
| 1118 | SmallVector<int64_t> paddedShape; |
| 1119 | for (int64_t dimIdx = 0; dimIdx < inputRank; ++dimIdx) { |
| 1120 | // 1. Non-tiled outer dims. |
| 1121 | // These dims should be 1 and we simply preserve them. |
| 1122 | if (!tileAndPosMapping.count(Val: dimIdx)) { |
| 1123 | int64_t inputDimSize = inputType.getDimSize(idx: dimIdx); |
| 1124 | assert(inputDimSize == 1 && |
| 1125 | "with all outer dims == 1, this non-tiled input dim should be 1!" ); |
| 1126 | paddedShape.push_back(Elt: inputDimSize); |
| 1127 | continue; |
| 1128 | } |
| 1129 | |
| 1130 | // 2. Tiled outer dims |
| 1131 | // As all outer dims == 1, it is safe to use the tile size for the padded |
| 1132 | // shape. |
| 1133 | OpFoldResult tileSizeForDim = tileAndPosMapping.lookup(Val: dimIdx); |
| 1134 | |
| 1135 | // 2.1 Static tile sizes |
| 1136 | std::optional<int64_t> cstTileSize = getConstantIntValue(ofr: tileSizeForDim); |
| 1137 | if (cstTileSize.has_value()) { |
| 1138 | paddedShape.push_back(Elt: cstTileSize.value()); |
| 1139 | continue; |
| 1140 | } |
| 1141 | |
| 1142 | // 2.2 Dynamic tile sizes |
| 1143 | paddedShape.push_back(Elt: ShapedType::kDynamic); |
| 1144 | |
| 1145 | // Get the value that holds the dynamic size. |
| 1146 | dynamicTileSizes.push_back(Elt: llvm::dyn_cast<Value>(Val&: tileSizeForDim)); |
| 1147 | } |
| 1148 | auto resultType = |
| 1149 | RankedTensorType::get(shape: paddedShape, elementType: inputType.getElementType()); |
| 1150 | return tensor::createPadHighOp(resType: resultType, source: input, pad: packOp.getPaddingValue(), |
| 1151 | /*nofold=*/false, loc, builder, |
| 1152 | dynOutDims: dynamicTileSizes); |
| 1153 | } |
| 1154 | |
| 1155 | // Normalizes a permutation on a higher rank space to its actual size, e.g. |
| 1156 | // perm = [1, 4, 2] |
| 1157 | // becomes |
| 1158 | // norm = [0, 2, 1] |
| 1159 | static SmallVector<int64_t> |
| 1160 | getPackUnpackNormalizedPerm(int rank, ArrayRef<int64_t> perm) { |
| 1161 | constexpr int64_t kNonTiledMarker = -1; |
| 1162 | SmallVector<int64_t> vec(rank, kNonTiledMarker); |
| 1163 | for (auto [index, value] : llvm::enumerate(First&: perm)) |
| 1164 | vec[value] = index; |
| 1165 | SmallVector<int64_t> normalizedPerm = llvm::filter_to_vector( |
| 1166 | C&: vec, Pred: [&](int64_t v) { return v != kNonTiledMarker; }); |
| 1167 | // This inverts the permutation in addition to normalizing so invert back. |
| 1168 | return invertPermutationVector(permutation: normalizedPerm); |
| 1169 | } |
| 1170 | |
| 1171 | // Gets the normalized permutation implied by innerDimsPos and outerDimsPerm |
| 1172 | // assuming rank reduction of unit outer dims. |
| 1173 | static SmallVector<int64_t> |
| 1174 | getPackUnpackRankReducedPerm(ArrayRef<int64_t> shape, |
| 1175 | ArrayRef<int64_t> innerDimsPos, |
| 1176 | ArrayRef<int64_t> outerDimsPerm) { |
| 1177 | SmallVector<int64_t> rankReducedOuterDimsPerm; |
| 1178 | SmallVector<int64_t> outerDims; |
| 1179 | SmallVector<int64_t> innerDims; |
| 1180 | int64_t dim = 0; |
| 1181 | int64_t unpackedRank = shape.size(); |
| 1182 | for (auto i : llvm::seq<unsigned>(Begin: 0, End: unpackedRank)) { |
| 1183 | if (llvm::is_contained(Range&: innerDimsPos, Element: i)) { |
| 1184 | innerDims.push_back(Elt: dim++); |
| 1185 | continue; |
| 1186 | } |
| 1187 | if (shape[i] == 1) |
| 1188 | continue; |
| 1189 | outerDims.push_back(Elt: dim++); |
| 1190 | if (!outerDimsPerm.empty()) |
| 1191 | rankReducedOuterDimsPerm.push_back(Elt: outerDimsPerm[i]); |
| 1192 | } |
| 1193 | |
| 1194 | // Get the position of the inner dims after permutation. |
| 1195 | SmallVector<int64_t> innerPerm = |
| 1196 | getPackUnpackNormalizedPerm(rank: unpackedRank, perm: innerDimsPos); |
| 1197 | applyPermutationToVector<int64_t>(inVec&: innerDims, permutation: innerPerm); |
| 1198 | |
| 1199 | // Ditto for the outer dims. |
| 1200 | SmallVector<int64_t> perm = outerDims; |
| 1201 | |
| 1202 | rankReducedOuterDimsPerm = |
| 1203 | getPackUnpackNormalizedPerm(rank: unpackedRank, perm: rankReducedOuterDimsPerm); |
| 1204 | if (!rankReducedOuterDimsPerm.empty()) |
| 1205 | applyPermutationToVector<int64_t>(inVec&: perm, permutation: rankReducedOuterDimsPerm); |
| 1206 | |
| 1207 | // The tile always ends up as the inner most dims after packing. |
| 1208 | perm.append(RHS: innerDims); |
| 1209 | |
| 1210 | return perm; |
| 1211 | } |
| 1212 | |
| 1213 | LogicalResult DecomposeOuterUnitDimsPackOpPattern::matchAndRewrite( |
| 1214 | linalg::PackOp packOp, PatternRewriter &rewriter) const { |
| 1215 | // Pack/unpack memref transformations are unsupported. The memref forms |
| 1216 | // are mainly for bufferization and scalar lowering. Other uses are not |
| 1217 | // recommended, see #225650 for details. |
| 1218 | if (!packOp.hasPureTensorSemantics()) |
| 1219 | return failure(); |
| 1220 | |
| 1221 | if (llvm::any_of(Range: packOp.getTiledOuterDims(), |
| 1222 | P: [](int64_t dim) { return dim != 1; })) { |
| 1223 | return rewriter.notifyMatchFailure( |
| 1224 | arg&: packOp, msg: "not all outer dimensions of the result are 1s" ); |
| 1225 | } |
| 1226 | |
| 1227 | // When a padding value is set, getPackOpSourceOrPaddedSource only supports |
| 1228 | // the case where every outer dim (including un-tiled ones) is 1. Bail out |
| 1229 | // instead of hitting an assertion on a non-unit un-tiled outer dim. |
| 1230 | // FIXME: Handle this case by decomposing the padded pack instead of bailing |
| 1231 | // out; a non-unit un-tiled outer dim should be supported here. |
| 1232 | if (packOp.getPaddingValue() && |
| 1233 | llvm::any_of(Range: packOp.getAllOuterDims(), |
| 1234 | P: [](int64_t dim) { return dim != 1; })) { |
| 1235 | return rewriter.notifyMatchFailure( |
| 1236 | arg&: packOp, msg: "cannot decompose padded pack with a non-unit un-tiled outer " |
| 1237 | "dimension" ); |
| 1238 | } |
| 1239 | |
| 1240 | ArrayRef<int64_t> innerDimsPos = packOp.getInnerDimsPos(); |
| 1241 | auto outerDimsPerm = packOp.getOuterDimsPerm(); |
| 1242 | |
| 1243 | // Verify that there are no: |
| 1244 | // * non-unit + un-tiled-outer-dims, |
| 1245 | // that are permuted. Supporting such cases would require refining the logic |
| 1246 | // that generates the Transpose Op. |
| 1247 | if (!llvm::all_of(Range&: outerDimsPerm, P: [&innerDimsPos, &packOp](int64_t dim) { |
| 1248 | static int prev = 0; |
| 1249 | // Skip tiled dims - these can be permuted. |
| 1250 | if (llvm::is_contained(Range&: innerDimsPos, Element: dim)) |
| 1251 | return true; |
| 1252 | |
| 1253 | // Check whether this dim has been permuted. Permuting unit dims is fine |
| 1254 | // as that's effectively a no-op. |
| 1255 | if (dim < prev && (packOp.getResult().getType().getShape()[prev] != 1 || |
| 1256 | packOp.getResult().getType().getShape()[dim] != 1)) |
| 1257 | return false; |
| 1258 | |
| 1259 | prev = dim; |
| 1260 | return true; |
| 1261 | })) { |
| 1262 | return rewriter.notifyMatchFailure( |
| 1263 | arg&: packOp, msg: "At least one non-unit and un-tiled outer dim is permuted, " |
| 1264 | "this is not supported ATM!" ); |
| 1265 | } |
| 1266 | |
| 1267 | Location loc = packOp.getLoc(); |
| 1268 | |
| 1269 | int64_t srcRank = packOp.getSourceRank(); |
| 1270 | |
| 1271 | // 1. Get the input that is going to be packed. If the input requires padding, |
| 1272 | // add a padding operation and return that as the input. |
| 1273 | Value input = getPackOpSourceOrPaddedSource(builder&: rewriter, packOp); |
| 1274 | |
| 1275 | // 2. Transpose the input to match the inner tile order: |
| 1276 | // %init = tensor.empty() |
| 1277 | // %transposed_tile = linalg.transpose ins(%source_or_padded_source), |
| 1278 | // outs(%init) |
| 1279 | // Assumptions made: |
| 1280 | // - All tiled outer dims are 1 - the corresponding transposition order |
| 1281 | // doesn't matter, but requires all dim indices to be present. |
| 1282 | // - Un-tiled outer dims remain un-permuted. |
| 1283 | |
| 1284 | // 2.1 Get the permutation for linalg.transpose: |
| 1285 | // [ untiled-dims, inner-dims-pos ] |
| 1286 | // Note, this logic assumes that the untiled dims are not permuted. |
| 1287 | SmallVector<int64_t> srcPermForTranspose; |
| 1288 | for (int64_t i = 0; i < srcRank; i++) { |
| 1289 | // We assume the `k` dimensions of the inner dim position, where `k` is the |
| 1290 | // rank of the inner tiling, correspond to the last `k` indices of the |
| 1291 | // transpose permutation. This is done by adding the indices not contained |
| 1292 | // in the inner dimension position in order from 0 to `n`. Where n is the |
| 1293 | // rank of the source tensor. For example if we have a source tensor with |
| 1294 | // indices [0, 1, 2, 3] and inner dim position of [3, 0], the remaining |
| 1295 | // indices are [1, 2]. and the transpose will be [1, 2, 3, 0]. |
| 1296 | if (llvm::is_contained(Range&: innerDimsPos, Element: i)) |
| 1297 | continue; |
| 1298 | srcPermForTranspose.push_back(Elt: i); |
| 1299 | } |
| 1300 | srcPermForTranspose.append(in_start: innerDimsPos.begin(), in_end: innerDimsPos.end()); |
| 1301 | |
| 1302 | // 2.2 Create the init tensor for linalg.transpose with the correct shape: |
| 1303 | // [ untiled-dims, tiled-dims ] |
| 1304 | ShapedType inputTy = cast<ShapedType>(Val: input.getType()); |
| 1305 | SmallVector<OpFoldResult> shapeForEmptyOp; |
| 1306 | for (int64_t i = 0; i < srcRank; i++) { |
| 1307 | if (llvm::is_contained(Range&: innerDimsPos, Element: i)) { |
| 1308 | // The tiled dims are appended after this loop. |
| 1309 | continue; |
| 1310 | } |
| 1311 | if (inputTy.isStaticDim(idx: i)) |
| 1312 | shapeForEmptyOp.push_back(Elt: rewriter.getIndexAttr(value: inputTy.getShape()[i])); |
| 1313 | else |
| 1314 | shapeForEmptyOp.emplace_back( |
| 1315 | Args: tensor::DimOp::create(builder&: rewriter, location: loc, source: input, index: i).getResult()); |
| 1316 | } |
| 1317 | shapeForEmptyOp.append(RHS: packOp.getMixedTiles()); |
| 1318 | |
| 1319 | // getMixedTiles() may contain Values pointing to constant ops (as opposed to |
| 1320 | // constant attributes with the corresponding value). Replace those with |
| 1321 | // attributes. This is to match the behaviour in |
| 1322 | // `getPackOpSourceOrPaddedSource`, which replaces constant SSA values with |
| 1323 | // attributes. |
| 1324 | llvm::transform(Range&: shapeForEmptyOp, d_first: shapeForEmptyOp.begin(), |
| 1325 | F: [&](OpFoldResult ofr) { |
| 1326 | if (auto val = llvm::dyn_cast<Value>(Val&: ofr)) |
| 1327 | return getAsOpFoldResult(val); |
| 1328 | return ofr; |
| 1329 | }); |
| 1330 | |
| 1331 | LDBG() << "Pack permutation: " << packOp; |
| 1332 | LDBG() << "perm: " << llvm::interleaved(R: srcPermForTranspose); |
| 1333 | LDBG() << "Shape of empty tensor: " << llvm::interleaved(R: shapeForEmptyOp); |
| 1334 | |
| 1335 | Value empty = tensor::EmptyOp::create( |
| 1336 | builder&: rewriter, location: loc, sizes: shapeForEmptyOp, elementType: packOp.getSourceType().getElementType()); |
| 1337 | |
| 1338 | // 2.3 Create linalg.transpose |
| 1339 | auto transposedOp = linalg::TransposeOp::create(builder&: rewriter, location: loc, input, init: empty, |
| 1340 | permutation: srcPermForTranspose); |
| 1341 | |
| 1342 | // 3. Insert the inner tile into the destination tensor: |
| 1343 | // %inserted_tile = tensor.insert_slice(%transposed_tile) |
| 1344 | |
| 1345 | // Compute the sizes attribute: |
| 1346 | // [ outer-dims, tile-sizes ] |
| 1347 | // Note that the output from the transpose Op excludes the tiled outer dims. |
| 1348 | // However, given the assumption that: |
| 1349 | // * all tiled outer dims == 1, |
| 1350 | // we can just use a rank-expanding tensor.insert_slice. |
| 1351 | SmallVector<OpFoldResult> writeSizes; |
| 1352 | for (auto size : packOp.getAllOuterDims()) { |
| 1353 | writeSizes.push_back(Elt: rewriter.getIndexAttr(value: size)); |
| 1354 | } |
| 1355 | |
| 1356 | for (auto tileSize : packOp.getMixedTiles()) { |
| 1357 | auto [_, tileSizeOfr] = |
| 1358 | getSimplifiedOfrAndStaticSizePair(ofr: tileSize, b&: rewriter); |
| 1359 | writeSizes.push_back(Elt: tileSizeOfr); |
| 1360 | } |
| 1361 | |
| 1362 | auto insert = tensor::InsertSliceOp::create( |
| 1363 | builder&: rewriter, location: loc, source: transposedOp.getResult()[0], dest: packOp.getDest(), sizes: writeSizes); |
| 1364 | |
| 1365 | // 4. Replace tensor.packOp with tensor.insert_slice created above |
| 1366 | rewriter.replaceOp(op: packOp, newValues: insert.getResult()); |
| 1367 | |
| 1368 | return success(); |
| 1369 | } |
| 1370 | |
| 1371 | LogicalResult DecomposeOuterUnitDimsUnPackOpPattern::matchAndRewrite( |
| 1372 | linalg::UnPackOp unpackOp, PatternRewriter &rewriter) const { |
| 1373 | if (!unpackOp.hasPureTensorSemantics()) |
| 1374 | return failure(); |
| 1375 | |
| 1376 | int64_t destRank = unpackOp.getDestRank(); |
| 1377 | ArrayRef<int64_t> srcShape = unpackOp.getSourceType().getShape(); |
| 1378 | ArrayRef<int64_t> innerDimsPos = unpackOp.getInnerDimsPos(); |
| 1379 | if (llvm::any_of(Range: unpackOp.getTiledOuterDims(), |
| 1380 | P: [](int64_t dim) { return dim != 1; })) { |
| 1381 | return rewriter.notifyMatchFailure( |
| 1382 | arg&: unpackOp, |
| 1383 | msg: "require the tiled outer dimensions of the result are all 1s" ); |
| 1384 | } |
| 1385 | |
| 1386 | // 1. Use rank-reduced tensor.extract_slice op to extract the tile: |
| 1387 | // %extracted_tile = tensor.extract_slice(%unpack_op_input) |
| 1388 | Location loc = unpackOp.getLoc(); |
| 1389 | Value source = unpackOp.getSource(); |
| 1390 | DenseMap<int64_t, OpFoldResult> dimAndTileMapping = |
| 1391 | unpackOp.getDimAndTileMapping(); |
| 1392 | Attribute oneIdxAttr = rewriter.getIndexAttr(value: 1); |
| 1393 | |
| 1394 | // The shape for ExtractSliceOp. Note that this will consist of 3 blocks of |
| 1395 | // dims: |
| 1396 | // [ outer-untiled-dims, outer-tiled-dims, tile-sizes ] |
| 1397 | SmallVector<int64_t> ; |
| 1398 | // The sizes attribute for ExtractSliceOp. Due to rank-reducing (and |
| 1399 | // outer-tiled-dims being all 1), this will be |
| 1400 | // [ outer-untiled-dims, tile-sizes ] |
| 1401 | SmallVector<OpFoldResult> ; |
| 1402 | |
| 1403 | // Shape for EmptyOp that's used as the init value for TransposeOp below. |
| 1404 | // This should be: |
| 1405 | // [ outer-untiled-dims, tile-sizes ] |
| 1406 | // However, skip unit dims - TransposeOp (below) applies rank-reduced |
| 1407 | // permutation. |
| 1408 | SmallVector<OpFoldResult> shapeForEmptyOp; |
| 1409 | |
| 1410 | for (auto i : llvm::seq<unsigned>(Begin: 0, End: destRank)) { |
| 1411 | // Compute sizes attribute for ExtractSliceOp - outer-tiled-dims. |
| 1412 | // |
| 1413 | // As all outer tiled dims are 1, so the corresponding |
| 1414 | // slice size to read will also 1. As this will be rank-reducing "extract |
| 1415 | // slice" (i.e. the unit dims will be "collapsed"), there's no need to |
| 1416 | // update: |
| 1417 | // * the output shape for ExtractSliceOp, nor |
| 1418 | // * the shape for EmptyOp. |
| 1419 | if (dimAndTileMapping.count(Val: i)) { |
| 1420 | extractSliceSizes.push_back(Elt: oneIdxAttr); |
| 1421 | continue; |
| 1422 | } |
| 1423 | |
| 1424 | // Compute sizes attribute for ExtractSliceOp + EmptyOp - |
| 1425 | // outer-untiled-dims |
| 1426 | if (ShapedType::isDynamic(dValue: srcShape[i])) { |
| 1427 | OpFoldResult dynamicDim = |
| 1428 | tensor::DimOp::create(builder&: rewriter, location: loc, source, index: i).getResult(); |
| 1429 | extractSliceSizes.push_back(Elt: dynamicDim); |
| 1430 | shapeForEmptyOp.push_back(Elt: dynamicDim); |
| 1431 | } else { |
| 1432 | extractSliceSizes.push_back(Elt: rewriter.getIndexAttr(value: srcShape[i])); |
| 1433 | if (srcShape[i] != 1) |
| 1434 | shapeForEmptyOp.push_back(Elt: rewriter.getIndexAttr(value: srcShape[i])); |
| 1435 | } |
| 1436 | // Compute the output shape for ExtractSliceOp - outer-untiled-dims (take |
| 1437 | // into account rank-reducing) |
| 1438 | if (srcShape[i] != 1) { |
| 1439 | readShapeForExtractSlice.push_back(Elt: srcShape[i]); |
| 1440 | } |
| 1441 | } |
| 1442 | // Append the tile sizes to "sizes attribute" for ExtractSliceOp and the |
| 1443 | // shape for EmptyOp. |
| 1444 | auto mixedTiles = unpackOp.getMixedTiles(); |
| 1445 | extractSliceSizes.append(in_start: mixedTiles.begin(), in_end: mixedTiles.end()); |
| 1446 | shapeForEmptyOp.append(in_start: mixedTiles.begin(), in_end: mixedTiles.end()); |
| 1447 | |
| 1448 | // Explicitly create the type for extract_slice op because the inner tile |
| 1449 | // size could be 1. We want to represent the whole inner tile in this case. |
| 1450 | auto tileShape = srcShape.drop_front(N: destRank); |
| 1451 | // Append the inner tile shape to the permuted and rank-reduced outer shape. |
| 1452 | readShapeForExtractSlice.append(in_start: tileShape.begin(), in_end: tileShape.end()); |
| 1453 | Type elemType = unpackOp.getSourceType().getElementType(); |
| 1454 | auto readType = RankedTensorType::get(shape: readShapeForExtractSlice, elementType: elemType); |
| 1455 | Value innerTile = tensor::ExtractSliceOp::create( |
| 1456 | builder&: rewriter, location: loc, resultType: readType, source: unpackOp.getSource(), sizes: extractSliceSizes); |
| 1457 | |
| 1458 | // 2. Transpose the tile to match the outer corresponding tile order. |
| 1459 | SmallVector<int64_t> perm = getPackUnpackRankReducedPerm( |
| 1460 | shape: srcShape.take_front(N: destRank), innerDimsPos, outerDimsPerm: unpackOp.getOuterDimsPerm()); |
| 1461 | // Unpack is a transition out of packed space so we invert the permutation. |
| 1462 | perm = invertPermutationVector(permutation: perm); |
| 1463 | applyPermutationToVector<OpFoldResult>(inVec&: shapeForEmptyOp, permutation: perm); |
| 1464 | |
| 1465 | Value empty = |
| 1466 | tensor::EmptyOp::create(builder&: rewriter, location: loc, sizes: shapeForEmptyOp, elementType: elemType); |
| 1467 | auto transposedOp = |
| 1468 | linalg::TransposeOp::create(builder&: rewriter, location: loc, input: innerTile, init: empty, permutation: perm); |
| 1469 | |
| 1470 | // 3. Handle in-complete tiles if needed. It truncates trailing data from the |
| 1471 | // transposed tile. |
| 1472 | SmallVector<OpFoldResult> tileSizes; |
| 1473 | ArrayRef<int64_t> destShape = unpackOp.getDestType().getShape(); |
| 1474 | for (auto i : llvm::seq<unsigned>(Begin: 0, End: destRank)) { |
| 1475 | if (dimAndTileMapping.count(Val: i) || destShape[i] != 1) |
| 1476 | tileSizes.push_back( |
| 1477 | Elt: tensor::getMixedSize(builder&: rewriter, loc, value: unpackOp.getDest(), dim: i)); |
| 1478 | } |
| 1479 | |
| 1480 | auto partialTile = |
| 1481 | tensor::ExtractSliceOp::create(builder&: rewriter, location: loc, resultType: RankedTensorType(), |
| 1482 | source: transposedOp.getResult()[0], sizes: tileSizes); |
| 1483 | |
| 1484 | // 4. Insert the result to the destination tensor. |
| 1485 | SmallVector<OpFoldResult> writeSizes; |
| 1486 | for (int i = 0, idx = 0; i < destRank; ++i) { |
| 1487 | if (dimAndTileMapping.count(Val: i) || destShape[i] != 1) |
| 1488 | writeSizes.push_back(Elt: tileSizes[idx++]); |
| 1489 | else |
| 1490 | writeSizes.push_back(Elt: oneIdxAttr); |
| 1491 | } |
| 1492 | auto insert = tensor::InsertSliceOp::create(builder&: rewriter, location: loc, source: partialTile, |
| 1493 | dest: unpackOp.getDest(), sizes: writeSizes); |
| 1494 | rewriter.replaceOp(op: unpackOp, newValues: insert.getResult()); |
| 1495 | |
| 1496 | return success(); |
| 1497 | } |
| 1498 | |
| 1499 | //===----------------------------------------------------------------------===// |
| 1500 | // Generic DownscaleSizeOneWindowedConvolution |
| 1501 | //===----------------------------------------------------------------------===// |
| 1502 | // |
| 1503 | /// Returns the indices of affine map results that reference any of the given |
| 1504 | /// dimensions. |
| 1505 | static SmallVector<unsigned> |
| 1506 | getResultIndicesReferencingDims(AffineMap map, ArrayRef<unsigned> dims) { |
| 1507 | SmallVector<unsigned> resultIndices; |
| 1508 | for (unsigned dim : dims) { |
| 1509 | for (unsigned i = 0, e = map.getNumResults(); i < e; ++i) { |
| 1510 | AffineExpr expr = map.getResult(idx: i); |
| 1511 | if (expr.isFunctionOfDim(position: dim)) { |
| 1512 | resultIndices.push_back(Elt: i); |
| 1513 | break; |
| 1514 | } |
| 1515 | } |
| 1516 | } |
| 1517 | return resultIndices; |
| 1518 | } |
| 1519 | |
| 1520 | /// Helper to create a rank-reducing extract_slice that removes specific |
| 1521 | /// dimensions from a tensor. |
| 1522 | static Value (RewriterBase &rewriter, |
| 1523 | Location loc, Value tensor, |
| 1524 | ArrayRef<unsigned> dimsToRemove) { |
| 1525 | auto tensorType = cast<RankedTensorType>(Val: tensor.getType()); |
| 1526 | int64_t rank = tensorType.getRank(); |
| 1527 | |
| 1528 | // Compute new shape by removing the specified dimensions. |
| 1529 | SmallVector<int64_t> newShape; |
| 1530 | for (int64_t i = 0; i < rank; ++i) { |
| 1531 | if (!llvm::is_contained(Range&: dimsToRemove, Element: i)) |
| 1532 | newShape.push_back(Elt: tensorType.getDimSize(idx: i)); |
| 1533 | } |
| 1534 | |
| 1535 | auto newType = RankedTensorType::get(shape: newShape, elementType: tensorType.getElementType()); |
| 1536 | return tensor::createCanonicalRankReducingExtractSliceOp(b&: rewriter, loc, |
| 1537 | tensor, targetType: newType); |
| 1538 | } |
| 1539 | |
| 1540 | /// Drops specified dimensions from an AffineExpr and compresses remaining |
| 1541 | /// dimension indices. Returns std::nullopt if the expression only references |
| 1542 | /// the dropped dimensions. |
| 1543 | static std::optional<AffineExpr> |
| 1544 | dropDimsAndCompress(AffineExpr expr, ArrayRef<unsigned> dimsToDrop, |
| 1545 | unsigned newNumDims, MLIRContext *ctx) { |
| 1546 | // Check if expr only references dimensions to be dropped. |
| 1547 | bool onlyReferencesDroppedDims = true; |
| 1548 | for (unsigned d = 0; d < newNumDims + dimsToDrop.size(); ++d) { |
| 1549 | if (expr.isFunctionOfDim(position: d) && !llvm::is_contained(Range&: dimsToDrop, Element: d)) { |
| 1550 | onlyReferencesDroppedDims = false; |
| 1551 | break; |
| 1552 | } |
| 1553 | } |
| 1554 | if (onlyReferencesDroppedDims && llvm::any_of(Range&: dimsToDrop, P: [&](unsigned d) { |
| 1555 | return expr.isFunctionOfDim(position: d); |
| 1556 | })) |
| 1557 | return std::nullopt; |
| 1558 | |
| 1559 | // Replace dimensions: compute new index for each old dimension. |
| 1560 | // Dropped dimensions get mapped to constant 0, others get compressed. |
| 1561 | SmallVector<AffineExpr> dimReplacements; |
| 1562 | unsigned newDimIdx = 0; |
| 1563 | for (unsigned d = 0; d < newNumDims + dimsToDrop.size(); ++d) { |
| 1564 | if (llvm::is_contained(Range&: dimsToDrop, Element: d)) { |
| 1565 | dimReplacements.push_back(Elt: getAffineConstantExpr(constant: 0, context: ctx)); |
| 1566 | } else { |
| 1567 | dimReplacements.push_back(Elt: getAffineDimExpr(position: newDimIdx++, context: ctx)); |
| 1568 | } |
| 1569 | } |
| 1570 | |
| 1571 | return expr.replaceDims(dimReplacements); |
| 1572 | } |
| 1573 | |
| 1574 | FailureOr<LinalgOp> |
| 1575 | linalg::downscaleSizeOneWindowedConvolution(RewriterBase &rewriter, |
| 1576 | LinalgOp op) { |
| 1577 | auto maybeDims = inferConvolutionDims(linalgOp: op); |
| 1578 | if (failed(Result: maybeDims)) |
| 1579 | return failure(); |
| 1580 | |
| 1581 | // Currently supports only 2D convolutions. |
| 1582 | if (maybeDims->outputImage.size() != 2 || maybeDims->filterLoop.size() != 2) |
| 1583 | return failure(); |
| 1584 | |
| 1585 | if (op.hasPureBufferSemantics()) |
| 1586 | return failure(); |
| 1587 | |
| 1588 | // Get loop domain indices for spatial dimensions. |
| 1589 | unsigned outSpatial0 = maybeDims->outputImage[0]; |
| 1590 | unsigned outSpatial1 = maybeDims->outputImage[1]; |
| 1591 | unsigned filterSpatial0 = maybeDims->filterLoop[0]; |
| 1592 | unsigned filterSpatial1 = maybeDims->filterLoop[1]; |
| 1593 | |
| 1594 | // Get sizes from loop bounds. |
| 1595 | SmallVector<int64_t, 4> loopRanges = op.getStaticLoopRanges(); |
| 1596 | int64_t outSize0 = loopRanges[outSpatial0]; |
| 1597 | int64_t outSize1 = loopRanges[outSpatial1]; |
| 1598 | int64_t filterSize0 = loopRanges[filterSpatial0]; |
| 1599 | int64_t filterSize1 = loopRanges[filterSpatial1]; |
| 1600 | |
| 1601 | // Check if we can downscale by removing a spatial dimension. |
| 1602 | bool canRemoveSpatial0 = (filterSize0 == 1 && outSize0 == 1); |
| 1603 | bool canRemoveSpatial1 = (filterSize1 == 1 && outSize1 == 1); |
| 1604 | if (!canRemoveSpatial0 && !canRemoveSpatial1) |
| 1605 | return failure(); |
| 1606 | |
| 1607 | // Determine which loop dims to remove (output spatial + corresponding filter) |
| 1608 | // and sort for correct index compression when removing dimensions from affine |
| 1609 | // maps. |
| 1610 | SmallVector<unsigned> loopDimsToRemove; |
| 1611 | if (canRemoveSpatial0) { |
| 1612 | loopDimsToRemove.push_back(Elt: outSpatial0); |
| 1613 | loopDimsToRemove.push_back(Elt: filterSpatial0); |
| 1614 | } else { |
| 1615 | loopDimsToRemove.push_back(Elt: outSpatial1); |
| 1616 | loopDimsToRemove.push_back(Elt: filterSpatial1); |
| 1617 | } |
| 1618 | llvm::sort(C&: loopDimsToRemove); |
| 1619 | |
| 1620 | // Create new indexing maps with dimensions removed. |
| 1621 | SmallVector<AffineMap> newMaps; |
| 1622 | MLIRContext *ctx = op.getContext(); |
| 1623 | unsigned numDims = op.getNumLoops(); |
| 1624 | unsigned newNumDims = numDims - loopDimsToRemove.size(); |
| 1625 | for (AffineMap map : op.getIndexingMapsArray()) { |
| 1626 | SmallVector<AffineExpr> newResults; |
| 1627 | for (AffineExpr expr : map.getResults()) { |
| 1628 | auto newExpr = |
| 1629 | dropDimsAndCompress(expr, dimsToDrop: loopDimsToRemove, newNumDims, ctx); |
| 1630 | if (newExpr) |
| 1631 | newResults.push_back(Elt: *newExpr); |
| 1632 | } |
| 1633 | newMaps.push_back(Elt: AffineMap::get(dimCount: newNumDims, symbolCount: 0, results: newResults, context: ctx)); |
| 1634 | } |
| 1635 | |
| 1636 | // Create new iterator types. |
| 1637 | SmallVector<utils::IteratorType> newIterTypes; |
| 1638 | auto iterTypes = op.getIteratorTypesArray(); |
| 1639 | for (unsigned idx = 0; idx < iterTypes.size(); ++idx) { |
| 1640 | if (!llvm::is_contained(Range&: loopDimsToRemove, Element: idx)) |
| 1641 | newIterTypes.push_back(Elt: iterTypes[idx]); |
| 1642 | } |
| 1643 | |
| 1644 | // Rank-reduce operands using extract_slice. |
| 1645 | Location loc = op.getLoc(); |
| 1646 | SmallVector<Value> newInputs; |
| 1647 | for (OpOperand *input : op.getDpsInputOperands()) { |
| 1648 | AffineMap map = op.getMatchingIndexingMap(opOperand: input); |
| 1649 | SmallVector<unsigned> tensorDimsToRemove = |
| 1650 | getResultIndicesReferencingDims(map, dims: loopDimsToRemove); |
| 1651 | Value reduced = createRankReducingExtractSlice(rewriter, loc, tensor: input->get(), |
| 1652 | dimsToRemove: tensorDimsToRemove); |
| 1653 | newInputs.push_back(Elt: reduced); |
| 1654 | } |
| 1655 | |
| 1656 | OpOperand &output = *op.getDpsInitsMutable().begin(); |
| 1657 | AffineMap outputMap = op.getMatchingIndexingMap(opOperand: &output); |
| 1658 | SmallVector<unsigned> outputDimsToRemove = |
| 1659 | getResultIndicesReferencingDims(map: outputMap, dims: loopDimsToRemove); |
| 1660 | Value newOutput = createRankReducingExtractSlice(rewriter, loc, tensor: output.get(), |
| 1661 | dimsToRemove: outputDimsToRemove); |
| 1662 | |
| 1663 | // Create new linalg.generic with reduced dimensions. |
| 1664 | auto newOp = |
| 1665 | linalg::GenericOp::create(builder&: rewriter, location: loc, resultTensorTypes: TypeRange{newOutput.getType()}, |
| 1666 | inputs: newInputs, outputs: newOutput, indexingMaps: newMaps, iteratorTypes: newIterTypes); |
| 1667 | rewriter.inlineRegionBefore(region&: op->getRegion(index: 0), parent&: newOp.getRegion(), |
| 1668 | before: newOp.getRegion().begin()); |
| 1669 | |
| 1670 | // Try to specialize the generic back to a named op only if the input was |
| 1671 | // already a specialized (named) op. |
| 1672 | LinalgOp resultOp = newOp; |
| 1673 | if (!isa<GenericOp>(Val: op)) { |
| 1674 | FailureOr<LinalgOp> specializedOp = specializeGenericOp(rewriter, genericOp: newOp); |
| 1675 | if (succeeded(Result: specializedOp)) |
| 1676 | resultOp = *specializedOp; |
| 1677 | } |
| 1678 | |
| 1679 | // Insert result back into original shape. |
| 1680 | Value result = tensor::createCanonicalRankReducingInsertSliceOp( |
| 1681 | b&: rewriter, loc, tensor: resultOp->getResult(idx: 0), dest: output.get()); |
| 1682 | |
| 1683 | rewriter.replaceOp(op, newValues: result); |
| 1684 | return resultOp; |
| 1685 | } |
| 1686 | |
| 1687 | namespace { |
| 1688 | /// Pattern wrapper around `downscaleSizeOneWindowedConvolution`. |
| 1689 | struct DownscaleSizeOneWindowedConvolution final |
| 1690 | : public OpInterfaceRewritePattern<LinalgOp> { |
| 1691 | DownscaleSizeOneWindowedConvolution(MLIRContext *context, |
| 1692 | PatternBenefit benefit = 1) |
| 1693 | : OpInterfaceRewritePattern<LinalgOp>(context, benefit) {} |
| 1694 | |
| 1695 | LogicalResult matchAndRewrite(LinalgOp op, |
| 1696 | PatternRewriter &rewriter) const override { |
| 1697 | return linalg::downscaleSizeOneWindowedConvolution(rewriter, op); |
| 1698 | } |
| 1699 | }; |
| 1700 | } // namespace |
| 1701 | |
| 1702 | void linalg::populateDecomposeConvolutionPatterns(RewritePatternSet &patterns, |
| 1703 | PatternBenefit benefit) { |
| 1704 | patterns.add<DownscaleSizeOneWindowedConvolution>(arg: patterns.getContext(), |
| 1705 | args&: benefit); |
| 1706 | } |
| 1707 | |
| 1708 | void linalg::populateDecomposePackUnpackPatterns(RewritePatternSet &patterns) { |
| 1709 | patterns.add<DecomposeOuterUnitDimsPackOpPattern>(arg: patterns.getContext()); |
| 1710 | patterns.add<DecomposeOuterUnitDimsUnPackOpPattern>(arg: patterns.getContext()); |
| 1711 | } |
| 1712 | |
| 1713 | void linalg::populateDecomposePadPatterns(RewritePatternSet &patterns) { |
| 1714 | patterns.add<DecomposePadOpPattern>(arg: patterns.getContext()); |
| 1715 | } |
| 1716 | |