| 1 | //===- DecomposeLinalgOps.cpp - Pattern to break up Linalg ops ------------===// |
| 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/Linalg/Transforms/Transforms.h" |
| 10 | |
| 11 | #include "mlir/Dialect/Affine/IR/AffineOps.h" |
| 12 | #include "mlir/Dialect/Linalg/IR/Linalg.h" |
| 13 | #include "llvm/ADT/SmallVectorExtras.h" |
| 14 | #include <optional> |
| 15 | |
| 16 | using namespace mlir; |
| 17 | using namespace mlir::linalg; |
| 18 | |
| 19 | namespace { |
| 20 | |
| 21 | /// Pattern to decompose a GenericOp that has more than two statements |
| 22 | /// into one GenericOp with the first statement (i.e. peeled operation), and |
| 23 | /// a second GenericOp with the remaining statements (i.e. residual operations). |
| 24 | |
| 25 | /// - The result of the first GenericOp has the same shape as the iteration |
| 26 | /// space of the GenericOp. The body of the op yields as many values as the |
| 27 | /// original op plus all the results of the peeled operation. |
| 28 | /// - The second GenericOp has as many operands as the original operation plus |
| 29 | /// all the results of the first Generic Op. It has the same number of yields as |
| 30 | /// the original op. |
| 31 | /// - If the result of the peeled operation was yielded by the original |
| 32 | /// GenericOp the uses of the corresponding results will be replaced with the |
| 33 | /// result of the first GenericOp created. |
| 34 | /// |
| 35 | /// Example |
| 36 | /// |
| 37 | /// ```mlir |
| 38 | /// %result:2 = linalg.generic ... ins(%arg0, %arg1, %arg2 : ...) |
| 39 | /// outs(%init0, %init1 : ...) { |
| 40 | /// ^bb0(%b0: ... , %b1: ... , %b2: ... , %b3: ..., %b4: ...): |
| 41 | /// %0 = <s0> %b0, %b1 : ... |
| 42 | /// %1 = <s1> %0, %b2 : ... |
| 43 | /// linalg.yield %0, %1 : ... |
| 44 | /// } -> (..., ...) |
| 45 | /// return %result#0, %result#1 |
| 46 | /// ``` |
| 47 | /// |
| 48 | /// gets split into |
| 49 | /// |
| 50 | /// ```mlir |
| 51 | /// %init = tensor.empty ... |
| 52 | /// %op0:3 = linalg.generic ... ins(%arg0, %arg1, %arg2 : ...) |
| 53 | /// outs(%init0, %init1, %init : ...) |
| 54 | /// ^bb0(%b0: ... , %b1: ... , %b2: ... , %b3: ..., %b4: ..., %b5: ...): |
| 55 | /// %0 = <s0> %b0, %b1 : ... |
| 56 | /// linalg.yield %0, %..., %0 : ... |
| 57 | /// } -> (..., ..., ...) |
| 58 | /// %op1:2 = linalg.generic ... ins(%arg0, %arg1, %arg2, %op0#2 : ...) |
| 59 | /// outs(%init0, %init1 : ...) { |
| 60 | /// ^bb0(%b0: ... , %b1: ... , %b2: ... , %b3: ..., %b4: ..., %b5: ...): |
| 61 | /// %1 = <s1> %b3, %b2 : ... |
| 62 | /// linalg.yield %..., %1 : ... |
| 63 | /// } -> (..., ...) |
| 64 | /// return %op0#0, %op1#1 |
| 65 | /// ``` |
| 66 | /// |
| 67 | /// After canonicalization this is expected to be |
| 68 | /// |
| 69 | /// ```mlir |
| 70 | /// %init = tensor.empty ... |
| 71 | /// %op0 = linalg.generic ... ins(%arg0, %arg1, : ...) |
| 72 | /// outs(%init : ...) |
| 73 | /// ^bb0(%b0: ... , %b1: ... , %b2: ...): |
| 74 | /// %0 = <s0> %b0, %b1 : ... |
| 75 | /// linalg.yield %0 : ... |
| 76 | /// } -> ... |
| 77 | /// %op1 = linalg.generic ... ins(%arg2, %op0#2 : ...) |
| 78 | /// outs(%init1 : ...) { |
| 79 | /// ^bb0(%b0: ... , %b1: ... , %b2: ...): |
| 80 | /// %1 = <s1> %b1, %b0 : ... |
| 81 | /// linalg.yield %..., %1 : ... |
| 82 | /// } -> ... |
| 83 | /// return %op0, %op1 |
| 84 | /// ``` |
| 85 | struct DecomposeLinalgOp : public OpRewritePattern<GenericOp> { |
| 86 | using OpRewritePattern<GenericOp>::OpRewritePattern; |
| 87 | |
| 88 | LogicalResult matchAndRewrite(GenericOp genericOp, |
| 89 | PatternRewriter &rewriter) const override; |
| 90 | |
| 91 | private: |
| 92 | /// Helper method to create a generic op for the peeled scalar operation. The |
| 93 | /// created op has an empty region. |
| 94 | GenericOp createPeeledGenericOp(GenericOp genericOp, |
| 95 | PatternRewriter &rewriter) const; |
| 96 | |
| 97 | /// Helper method to create a generic op for the residual scalar operation. |
| 98 | /// The created op has the same region as the original op. |
| 99 | GenericOp createResidualGenericOp(GenericOp genericOp, |
| 100 | GenericOp peeledGenericOp, |
| 101 | PatternRewriter &rewriter) const; |
| 102 | }; |
| 103 | } // namespace |
| 104 | |
| 105 | /// Helper method to compute the range of a generic op. |
| 106 | static SmallVector<OpFoldResult> getGenericOpLoopRange(OpBuilder &b, |
| 107 | GenericOp op) { |
| 108 | OpBuilder::InsertionGuard g(b); |
| 109 | b.setInsertionPoint(op); |
| 110 | Location loc = op.getLoc(); |
| 111 | auto allShapesSizes = |
| 112 | cast<LinalgOp>(Val: op.getOperation()).createFlatListOfOperandDims(b, loc); |
| 113 | AffineMap map = op.getShapesToLoopsMap(); |
| 114 | IRRewriter rewriter(b); |
| 115 | return affine::makeComposedFoldedMultiResultAffineApply(b&: rewriter, loc, map, |
| 116 | operands: allShapesSizes); |
| 117 | } |
| 118 | |
| 119 | /// Get zero value for an element type. |
| 120 | static Value getZero(OpBuilder &b, Location loc, Type elementType) { |
| 121 | assert(elementType.isIntOrIndexOrFloat() && |
| 122 | "expected scalar type while computing zero value" ); |
| 123 | if (isa<IntegerType>(Val: elementType)) |
| 124 | return arith::ConstantIntOp::create(builder&: b, location: loc, type: elementType, value: 0); |
| 125 | if (elementType.isIndex()) |
| 126 | return arith::ConstantIndexOp::create(builder&: b, location: loc, value: 0); |
| 127 | // Assume float. |
| 128 | auto floatType = cast<FloatType>(Val&: elementType); |
| 129 | return arith::ConstantFloatOp::create( |
| 130 | builder&: b, location: loc, type: floatType, value: APFloat::getZero(Sem: floatType.getFloatSemantics())); |
| 131 | } |
| 132 | |
| 133 | GenericOp |
| 134 | DecomposeLinalgOp::createPeeledGenericOp(GenericOp genericOp, |
| 135 | PatternRewriter &rewriter) const { |
| 136 | Block *body = genericOp.getBody(); |
| 137 | Operation *peeledScalarOperation = &(*body->begin()); |
| 138 | SmallVector<AffineMap> peeledGenericOpIndexingMaps = |
| 139 | genericOp.getIndexingMapsArray(); |
| 140 | |
| 141 | /// Compute the loop ranges for operation. This is the shape of the result of |
| 142 | /// the generic op for the peeled operation. |
| 143 | Location loc = genericOp.getLoc(); |
| 144 | SmallVector<OpFoldResult> domain = getGenericOpLoopRange(b&: rewriter, op: genericOp); |
| 145 | SmallVector<Value> newInitValues; |
| 146 | SmallVector<Type> newResultTypes; |
| 147 | |
| 148 | // Add as many new results as the number of results of the peeled scalar op. |
| 149 | for (auto scalarOpResult : peeledScalarOperation->getResults()) { |
| 150 | // If the result is yielded by the original op, use the operand, indexing |
| 151 | // map and result type that correspond to the yielded value. |
| 152 | |
| 153 | std::optional<unsigned> resultNumber; |
| 154 | for (auto *user : scalarOpResult.getUsers()) { |
| 155 | if (auto yieldOp = dyn_cast<YieldOp>(Val: user)) { |
| 156 | // Find the first use of the `scalarOpResult` in the yield op. |
| 157 | for (OpOperand &yieldOperand : yieldOp->getOpOperands()) { |
| 158 | if (yieldOperand.get() == scalarOpResult) { |
| 159 | resultNumber = yieldOperand.getOperandNumber(); |
| 160 | break; |
| 161 | } |
| 162 | } |
| 163 | assert(resultNumber && "unable to find use of a value in its user" ); |
| 164 | break; |
| 165 | } |
| 166 | } |
| 167 | if (resultNumber) { |
| 168 | newInitValues.push_back( |
| 169 | Elt: genericOp.getDpsInitOperand(i: *resultNumber)->get()); |
| 170 | OpResult result = cast<OpResult>(Val: genericOp.getResult(i: *resultNumber)); |
| 171 | newResultTypes.push_back(Elt: result.getType()); |
| 172 | peeledGenericOpIndexingMaps.push_back( |
| 173 | Elt: genericOp.getIndexingMapMatchingResult(result)); |
| 174 | continue; |
| 175 | } |
| 176 | |
| 177 | // Fall back path, use an `init_tensor` and identity indexing map. |
| 178 | AffineMap indexingMap = rewriter.getMultiDimIdentityMap(rank: domain.size()); |
| 179 | Value emptyTensor = tensor::EmptyOp::create(builder&: rewriter, location: loc, sizes: domain, |
| 180 | elementType: scalarOpResult.getType()); |
| 181 | newInitValues.push_back(Elt: emptyTensor); |
| 182 | newResultTypes.push_back(Elt: emptyTensor.getType()); |
| 183 | peeledGenericOpIndexingMaps.push_back(Elt: indexingMap); |
| 184 | } |
| 185 | |
| 186 | /// Create the peeled generic op with an empty body. |
| 187 | SmallVector<Value> outsOperands = genericOp.getOutputs(); |
| 188 | outsOperands.append(in_start: newInitValues.begin(), in_end: newInitValues.end()); |
| 189 | SmallVector<Type> resultTypes = llvm::to_vector(Range: genericOp.getResultTypes()); |
| 190 | resultTypes.append(in_start: newResultTypes.begin(), in_end: newResultTypes.end()); |
| 191 | auto indexingMapAttr = |
| 192 | rewriter.getAffineMapArrayAttr(values: peeledGenericOpIndexingMaps); |
| 193 | return GenericOp::create( |
| 194 | builder&: rewriter, location: loc, resultTensorTypes: resultTypes, inputs: genericOp.getInputs(), outputs: outsOperands, |
| 195 | indexingMaps: indexingMapAttr, iteratorTypes: genericOp.getIteratorTypes(), /*doc=*/nullptr, |
| 196 | /*libraryCall=*/nullptr, odsArg7: [](OpBuilder, Location, ValueRange) {}); |
| 197 | } |
| 198 | |
| 199 | GenericOp |
| 200 | DecomposeLinalgOp::createResidualGenericOp(GenericOp genericOp, |
| 201 | GenericOp peeledGenericOp, |
| 202 | PatternRewriter &rewriter) const { |
| 203 | /// Append all results from the peeledGenericOps as `ins` operand for the |
| 204 | /// residual generic op. |
| 205 | SmallVector<Value> residualGenericOpOperands = genericOp.getInputs(); |
| 206 | unsigned origNumResults = genericOp.getNumResults(); |
| 207 | unsigned peeledGenericOpNumResults = peeledGenericOp.getNumResults(); |
| 208 | SmallVector<Value> ; |
| 209 | for (auto resultNum : |
| 210 | llvm::seq<unsigned>(Begin: origNumResults, End: peeledGenericOpNumResults)) |
| 211 | extraIns.push_back(Elt: peeledGenericOp->getResult(idx: resultNum)); |
| 212 | residualGenericOpOperands.append(RHS: extraIns); |
| 213 | |
| 214 | /// Add indexing maps for the newly added operands. Use the same map |
| 215 | /// as those used for the new results of the peeledGenericOp. |
| 216 | auto indexingMaps = llvm::map_to_vector( |
| 217 | C: genericOp.getDpsInputOperands(), F: [&](OpOperand *operand) { |
| 218 | return genericOp.getMatchingIndexingMap(opOperand: operand); |
| 219 | }); |
| 220 | for (auto resultNum : |
| 221 | llvm::seq<unsigned>(Begin: origNumResults, End: peeledGenericOpNumResults)) { |
| 222 | OpResult result = cast<OpResult>(Val: peeledGenericOp.getResult(i: resultNum)); |
| 223 | indexingMaps.push_back( |
| 224 | Elt: peeledGenericOp.getIndexingMapMatchingResult(result)); |
| 225 | } |
| 226 | for (OpOperand &outOperand : genericOp.getDpsInitsMutable()) |
| 227 | indexingMaps.push_back(Elt: genericOp.getMatchingIndexingMap(opOperand: &outOperand)); |
| 228 | |
| 229 | auto indexingMapAttr = rewriter.getAffineMapArrayAttr(values: indexingMaps); |
| 230 | return GenericOp::create( |
| 231 | builder&: rewriter, location: genericOp->getLoc(), resultTensorTypes: genericOp->getResultTypes(), |
| 232 | inputs: residualGenericOpOperands, outputs: genericOp.getOutputs(), indexingMaps: indexingMapAttr, |
| 233 | iteratorTypes: genericOp.getIteratorTypes(), /*doc=*/nullptr, /*libraryCall=*/nullptr, |
| 234 | odsArg7: [](OpBuilder, Location, ValueRange) {}); |
| 235 | } |
| 236 | |
| 237 | LogicalResult |
| 238 | DecomposeLinalgOp::matchAndRewrite(GenericOp genericOp, |
| 239 | PatternRewriter &rewriter) const { |
| 240 | /// For now only match on operations where the iterator types are all parallel |
| 241 | if (genericOp.getNumParallelLoops() != genericOp.getNumLoops()) { |
| 242 | return rewriter.notifyMatchFailure(arg&: genericOp, |
| 243 | msg: "unhandled decomposition of operation " |
| 244 | "with non-parallel iterator types" ); |
| 245 | } |
| 246 | // TODO: this could be generalized to handle `linalg.generic` with buffer |
| 247 | // operands too but requires allocation for intermediates. Punt on this for |
| 248 | // now. |
| 249 | if (!genericOp.hasPureTensorSemantics()) { |
| 250 | return rewriter.notifyMatchFailure( |
| 251 | arg&: genericOp, msg: "only operations with tensor semantics are handled" ); |
| 252 | } |
| 253 | |
| 254 | if (llvm::any_of(Range: genericOp.getDpsInitsMutable(), P: [&](OpOperand &outOperand) { |
| 255 | return !genericOp.getMatchingIndexingMap(opOperand: &outOperand).isPermutation(); |
| 256 | })) { |
| 257 | return rewriter.notifyMatchFailure( |
| 258 | arg&: genericOp, msg: "unhandled decomposition of generic op with out operand not " |
| 259 | "accessed using a permutation" ); |
| 260 | } |
| 261 | |
| 262 | /// If the op has only a single statement (apart from the yield), do nothing. |
| 263 | Block *body = genericOp.getBody(); |
| 264 | if (body->getOperations().size() <= 2) { |
| 265 | return rewriter.notifyMatchFailure(arg&: genericOp, |
| 266 | msg: "operation has less than 3 statements" ); |
| 267 | } |
| 268 | |
| 269 | /// The peeled statement is expected to produce at least one result. |
| 270 | if (body->getOperations().begin()->getNumResults() == 0) { |
| 271 | return rewriter.notifyMatchFailure( |
| 272 | arg: &(*body->getOperations().begin()), |
| 273 | msg: "peeled statement is expected to have at least one result" ); |
| 274 | } |
| 275 | |
| 276 | /// Check that the peeled statement has a scalar element type. |
| 277 | if (llvm::any_of(Range: body->getOperations().begin()->getResultTypes(), |
| 278 | P: [](Type t) { return !t.isIntOrIndexOrFloat(); })) { |
| 279 | return rewriter.notifyMatchFailure( |
| 280 | arg: &(*body->getOperations().begin()), |
| 281 | msg: "expected return type to be only int, index or float" ); |
| 282 | } |
| 283 | |
| 284 | GenericOp peeledGenericOp = createPeeledGenericOp(genericOp, rewriter); |
| 285 | GenericOp residualGenericOp = |
| 286 | createResidualGenericOp(genericOp, peeledGenericOp, rewriter); |
| 287 | |
| 288 | /// Move the first statement of the original operation into the body of the |
| 289 | /// generic op for the peeled operation. |
| 290 | Block *peeledGenericOpBody = peeledGenericOp.getBody(); |
| 291 | Block *residualGenericOpBody = residualGenericOp.getBody(); |
| 292 | assert(peeledGenericOpBody->empty() && residualGenericOpBody->empty() && |
| 293 | "expected split generic ops to have empty region" ); |
| 294 | peeledGenericOpBody->getOperations().splice( |
| 295 | where: peeledGenericOpBody->begin(), L2&: body->getOperations(), first: body->begin()); |
| 296 | residualGenericOpBody->getOperations().splice(where: residualGenericOpBody->begin(), |
| 297 | L2&: body->getOperations()); |
| 298 | |
| 299 | Operation *peeledScalarOperation = &(*peeledGenericOpBody->begin()); |
| 300 | auto *yieldOp = residualGenericOpBody->getTerminator(); |
| 301 | { |
| 302 | // Yield all the result of the peeled scalar operation. |
| 303 | OpBuilder::InsertionGuard g(rewriter); |
| 304 | rewriter.setInsertionPointToEnd(peeledGenericOpBody); |
| 305 | SmallVector<Value> yieldedVals; |
| 306 | for (auto origYield : yieldOp->getOperands()) { |
| 307 | if (origYield.getDefiningOp() == peeledScalarOperation) { |
| 308 | yieldedVals.push_back(Elt: origYield); |
| 309 | } else { |
| 310 | // Do not materialize any new ops inside of the decomposed LinalgOp, |
| 311 | // as that would trigger another application of the rewrite pattern |
| 312 | // (infinite loop). |
| 313 | OpBuilder::InsertionGuard g(rewriter); |
| 314 | rewriter.setInsertionPoint(peeledGenericOp); |
| 315 | yieldedVals.push_back( |
| 316 | Elt: getZero(b&: rewriter, loc: genericOp.getLoc(), elementType: origYield.getType())); |
| 317 | } |
| 318 | } |
| 319 | yieldedVals.append( |
| 320 | RHS: llvm::map_to_vector(C: peeledScalarOperation->getResults(), |
| 321 | F: [](OpResult opr) -> Value { return opr; })); |
| 322 | YieldOp::create(builder&: rewriter, location: genericOp.getLoc(), values: yieldedVals); |
| 323 | } |
| 324 | |
| 325 | /// In the split operations, replace block arguments uses that refer to |
| 326 | /// original operation to the block arguments of the newly created operation. |
| 327 | unsigned origNumInputs = genericOp.getNumDpsInputs(); |
| 328 | for (const auto &inputBlockArg : |
| 329 | llvm::enumerate(First: genericOp.getBody()->getArguments())) { |
| 330 | Value residualOpReplacementArg = |
| 331 | residualGenericOpBody->getArgument(i: inputBlockArg.index()); |
| 332 | rewriter.replaceUsesWithIf( |
| 333 | from: inputBlockArg.value(), to: residualOpReplacementArg, functor: [&](OpOperand &use) { |
| 334 | return use.getOwner()->getBlock() == residualGenericOpBody; |
| 335 | }); |
| 336 | |
| 337 | Value peeledOpReplacementArg = |
| 338 | peeledGenericOpBody->getArgument(i: inputBlockArg.index()); |
| 339 | rewriter.replaceUsesWithIf( |
| 340 | from: inputBlockArg.value(), to: peeledOpReplacementArg, functor: [&](OpOperand &use) { |
| 341 | return use.getOwner()->getBlock() == peeledGenericOpBody; |
| 342 | }); |
| 343 | } |
| 344 | |
| 345 | /// Before fixing up the residual operation, track what values are yielded. If |
| 346 | /// any of those are from the peeled scalar operation, the uses of the |
| 347 | /// corresponding result have to be remapped to result of the generic op for |
| 348 | /// the peeled operation. |
| 349 | SmallVector<Value> replacements; |
| 350 | for (const auto &yieldValue : llvm::enumerate(First: yieldOp->getOperands())) { |
| 351 | OpResult opr = dyn_cast<OpResult>(Val&: yieldValue.value()); |
| 352 | if (!opr || opr.getOwner() != peeledScalarOperation) |
| 353 | replacements.push_back(Elt: residualGenericOp.getResult(i: yieldValue.index())); |
| 354 | else |
| 355 | replacements.push_back(Elt: peeledGenericOp->getResult(idx: yieldValue.index())); |
| 356 | } |
| 357 | |
| 358 | /// Update all uses of the peeled scalar operation results in the residual op |
| 359 | /// to the newly added arguments. |
| 360 | { |
| 361 | SmallVector<Value> scalarReplacements; |
| 362 | unsigned peeledScalarOpNumResults = peeledScalarOperation->getNumResults(); |
| 363 | scalarReplacements.reserve(N: peeledScalarOpNumResults); |
| 364 | for (auto num : llvm::seq<unsigned>(Begin: 0, End: peeledScalarOpNumResults)) |
| 365 | scalarReplacements.push_back( |
| 366 | Elt: residualGenericOpBody->getArgument(i: num + origNumInputs)); |
| 367 | bool allUsesReplaced = false; |
| 368 | rewriter.replaceOpUsesWithinBlock(op: peeledScalarOperation, newValues: scalarReplacements, |
| 369 | block: residualGenericOpBody, allUsesReplaced: &allUsesReplaced); |
| 370 | assert(!allUsesReplaced && |
| 371 | "peeled scalar operation is erased when it wasnt expected to be" ); |
| 372 | } |
| 373 | |
| 374 | // Replace the original operation |
| 375 | rewriter.replaceOp(op: genericOp, newValues: replacements); |
| 376 | return success(); |
| 377 | } |
| 378 | |
| 379 | void mlir::linalg::populateDecomposeLinalgOpsPattern( |
| 380 | RewritePatternSet &patterns, bool removeDeadArgsAndResults) { |
| 381 | patterns.insert<DecomposeLinalgOp>(arg: patterns.getContext()); |
| 382 | // Add the patterns to clean up the dead operands and results. |
| 383 | if (removeDeadArgsAndResults) |
| 384 | populateEraseUnusedOperandsAndResultsPatterns(patterns); |
| 385 | } |
| 386 | |