| 1 | //===- FoldAddIntoDest.cpp ---------------------------------------*- C++-*-===// |
| 2 | // |
| 3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| 4 | // See https://llvm.org/LICENSE.txt for license information. |
| 5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| 6 | // |
| 7 | //===----------------------------------------------------------------------===// |
| 8 | |
| 9 | #include "mlir/Dialect/Linalg/IR/Linalg.h" |
| 10 | #include "mlir/Dialect/Linalg/IR/LinalgInterfaces.h" |
| 11 | #include "mlir/Dialect/Linalg/Transforms/Transforms.h" |
| 12 | #include "mlir/IR/Dominance.h" |
| 13 | #include "mlir/Interfaces/DestinationStyleOpInterface.h" |
| 14 | |
| 15 | using namespace mlir; |
| 16 | |
| 17 | // Determine whether the value is defined to be zero. |
| 18 | static bool isDefinedAsZero(Value val) { |
| 19 | if (!val) |
| 20 | return false; |
| 21 | |
| 22 | // Check whether val is a constant scalar / vector splat / tensor splat float |
| 23 | // or integer zero. |
| 24 | if (isZeroIntegerOrFloat(v: val)) |
| 25 | return true; |
| 26 | |
| 27 | auto *defOp = val.getDefiningOp(); |
| 28 | if (!defOp) |
| 29 | return false; |
| 30 | |
| 31 | return TypeSwitch<Operation *, bool>(defOp) |
| 32 | .Case<linalg::FillOp, linalg::CopyOp>(caseFn: [&](auto op) { |
| 33 | return op.getInputs().size() == 1 && isDefinedAsZero(op.getInputs()[0]); |
| 34 | }) |
| 35 | .Default(defaultFn: [&](auto) { return false; }); |
| 36 | } |
| 37 | |
| 38 | /// Replace a linalg.elementwise kind=add with one operand the single user of a |
| 39 | /// contraction, which has a zero-filled, "identity-mapped" destination and is |
| 40 | /// dominated by the `other` operand, by the contraction with `other` as its |
| 41 | /// dest. |
| 42 | /// |
| 43 | /// As an example, the following pseudo-code will be rewritten |
| 44 | /// %cst = arith.constant 0.000000e+00 |
| 45 | /// %empty = tensor.empty() |
| 46 | /// %zeroed = linalg.fill ins(%cst : f32) outs(%empty : !type) -> !type |
| 47 | /// %C = linalg.matmul ins(%A, %B) outs(%zeroed) |
| 48 | /// %empty2 = tensor.empty() |
| 49 | /// %zeroed2 = linalg.fill ins(%cst : f32) outs(%empty2 : !type) -> !type |
| 50 | /// %F = linalg.matmul ins(%D, %E) outs(%zeroed2) |
| 51 | /// %out = linalg.elementwise kind=add ins(%C, %F) outs(%empty) |
| 52 | /// to: |
| 53 | /// %cst = arith.constant 0.000000e+00 |
| 54 | /// %empty = tensor.empty() |
| 55 | /// %zeroed = linalg.fill ins(%cst : f32) outs(%empty : !type) -> !type |
| 56 | /// %C = linalg.matmul ins(%A, %B) outs(%zeroed) |
| 57 | /// %out = linalg.matmul ins(%D, %E) outs(%C) |
| 58 | /// |
| 59 | struct FoldAddIntoDest final : public OpRewritePattern<linalg::ElementwiseOp> { |
| 60 | using OpRewritePattern<linalg::ElementwiseOp>::OpRewritePattern; |
| 61 | |
| 62 | LogicalResult matchAndRewrite(linalg::ElementwiseOp addOp, |
| 63 | PatternRewriter &rewriter) const override { |
| 64 | // Pattern only applies on a binary elementwise add. |
| 65 | if (addOp.getKind() != linalg::ElementwiseKind::add) |
| 66 | return failure(); |
| 67 | |
| 68 | // For now, pattern only applies on tensor types (memref support is TODO). |
| 69 | if (!addOp.hasPureTensorSemantics()) |
| 70 | return failure(); |
| 71 | |
| 72 | Value dominatingOperand = nullptr; |
| 73 | linalg::LinalgOp dominatedOp = nullptr; |
| 74 | { // We will forget about which operand was left or right after this block. |
| 75 | Value lhs = addOp.getInputs()[0]; |
| 76 | Value rhs = addOp.getInputs()[1]; |
| 77 | |
| 78 | // Can only put one of addOp's operands in the dest/out arg of the other's |
| 79 | // defining op based on suitable dominance. |
| 80 | // TODO: Can be generalized to move ops around as long as that still |
| 81 | // respects use-def chains and doesn't affect side-effects. |
| 82 | if (auto rhsOp = rhs.getDefiningOp<linalg::LinalgOp>()) { |
| 83 | DominanceInfo domInfo(rhsOp); |
| 84 | if (domInfo.properlyDominates(a: lhs, b: rhsOp)) { |
| 85 | dominatingOperand = lhs; |
| 86 | dominatedOp = rhsOp; |
| 87 | } |
| 88 | } |
| 89 | if (auto lhsOp = lhs.getDefiningOp<linalg::LinalgOp>()) { |
| 90 | DominanceInfo domInfo(lhsOp); |
| 91 | if (domInfo.properlyDominates(a: rhs, b: lhsOp)) { |
| 92 | dominatingOperand = rhs; |
| 93 | dominatedOp = lhsOp; |
| 94 | } |
| 95 | } |
| 96 | if (!dominatingOperand || !dominatedOp) |
| 97 | return failure(); |
| 98 | // NB: As the elementwise add's generalisation ignores the out argument in |
| 99 | // its region there is no need to perform checks on addOp's out |
| 100 | // argument. |
| 101 | } |
| 102 | |
| 103 | // When dominated op is a contraction we know it accumulates on its out arg. |
| 104 | // E.g., AddOp is not a contraction and hence ignores its out arg's value. |
| 105 | // TODO: Generalize check to also pass in case of other LinalgOps that |
| 106 | // accumulate on their out arg but are not (binary) contraction ops. |
| 107 | auto dominatedDestOp = |
| 108 | dyn_cast<DestinationStyleOpInterface>(Val: (Operation *)dominatedOp); |
| 109 | if (dominatedOp->getNumResults() != 1 || |
| 110 | !linalg::isaContractionOpInterface(linalgOp: dominatedOp) || |
| 111 | (!dominatedDestOp || dominatedDestOp.getNumDpsInits() != 1)) |
| 112 | return rewriter.notifyMatchFailure( |
| 113 | arg&: dominatedOp, msg: "expected dominated op to be single-result " |
| 114 | "destination-passing contraction" ); |
| 115 | |
| 116 | // To change the contraction's result, `addOp` must be its only user. |
| 117 | if (!dominatedOp->getResult(idx: 0).hasOneUse()) |
| 118 | return rewriter.notifyMatchFailure( |
| 119 | arg&: dominatedOp, |
| 120 | msg: "expected elementwise add to be single user of contraction's result" ); |
| 121 | |
| 122 | // As `dominatedOp` was already accumulating on its out argument, it is only |
| 123 | // safe to no longer use its current out arg when it is the additive ident. |
| 124 | auto *destOperand = dominatedDestOp.getDpsInitOperand(i: 0); |
| 125 | if (!isDefinedAsZero(val: destOperand->get())) |
| 126 | return rewriter.notifyMatchFailure( |
| 127 | arg&: dominatedOp, msg: "expected dominated op's dest to be additive zero" ); |
| 128 | // TODO: If the other op is a contraction and has additive ident as dest, we |
| 129 | // can swap the dests and achieve the proper sum, given suitable dominance. |
| 130 | |
| 131 | // As an operand to `addOp`, `dominatingOperand` has an identity affine_map. |
| 132 | // Hence, we can only substitute `dominatingOperand` for the dest of the |
| 133 | // contraction when dest's indexing_map corresponds to an identity map |
| 134 | // w.r.t. just the dimensions of dest, i.e. is an ordered projection. |
| 135 | SmallVector<AffineMap> indexMaps = dominatedOp.getIndexingMapsArray(); |
| 136 | int prevDimPos = -1; |
| 137 | for (auto expr : indexMaps[destOperand->getOperandNumber()].getResults()) { |
| 138 | auto dim = dyn_cast<AffineDimExpr>(Val&: expr); |
| 139 | if (!dim || prevDimPos > static_cast<int>(dim.getPosition())) |
| 140 | return rewriter.notifyMatchFailure( |
| 141 | arg&: dominatedOp, msg: "expected index_map for contraction's dest to be an " |
| 142 | "ordered projection" ); |
| 143 | prevDimPos = dim.getPosition(); |
| 144 | } |
| 145 | |
| 146 | // Replace the additive-ident, i.e. zero, out arg of the dominated op by the |
| 147 | // dominating summand. This makes the dominated op's result the sum of both |
| 148 | // of addOp's arguments - therefore we replace addOp and it uses by it. |
| 149 | rewriter.modifyOpInPlace( |
| 150 | root: dominatedOp, callable: [&]() { dominatedOp->setOperand(idx: 2, value: dominatingOperand); }); |
| 151 | rewriter.replaceAllOpUsesWith(from: addOp, to: dominatedOp->getResult(idx: 0)); |
| 152 | return success(); |
| 153 | } |
| 154 | }; |
| 155 | |
| 156 | void linalg::populateFoldAddIntoDestPatterns(RewritePatternSet &patterns) { |
| 157 | // Replace linalg.add when destination passing suffices for achieving the sum. |
| 158 | patterns.add<FoldAddIntoDest>(arg: patterns.getContext()); |
| 159 | } |
| 160 | |