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
15using namespace mlir;
16
17// Determine whether the value is defined to be zero.
18static 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///
59struct 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
156void 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