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
16using namespace mlir;
17using namespace mlir::linalg;
18
19namespace {
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/// ```
85struct DecomposeLinalgOp : public OpRewritePattern<GenericOp> {
86 using OpRewritePattern<GenericOp>::OpRewritePattern;
87
88 LogicalResult matchAndRewrite(GenericOp genericOp,
89 PatternRewriter &rewriter) const override;
90
91private:
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.
106static 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.
120static 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
133GenericOp
134DecomposeLinalgOp::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
199GenericOp
200DecomposeLinalgOp::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> extraIns;
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
237LogicalResult
238DecomposeLinalgOp::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
379void 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