1//===- EraseUnusedOperandsAndResults.cpp ----------------------------------===//
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/Linalg/IR/Linalg.h"
12
13using namespace mlir;
14using namespace mlir::linalg;
15
16/// Return `true` if the `result` of an operation `genericOp` is dead.
17static bool isResultValueDead(linalg::GenericOp genericOp, OpResult result) {
18 if (!result.use_empty())
19 return false;
20 // If out operand not used in payload, we can drop it.
21 OpOperand *outputOpOperand =
22 genericOp.getDpsInitOperand(i: result.getResultNumber());
23 if (!genericOp.payloadUsesValueFromOperand(opOperand: outputOpOperand))
24 return true;
25
26 // The out operand that is part of a payload can be dropped if
27 // these conditions are met:
28 // - Result from out operand is dead.
29 // - User of arg is yield.
30 // - outArg data is not being used by other outArgs.
31
32 // Check block arg and cycle from out operand has a single use.
33 BlockArgument outputArg =
34 genericOp.getRegionOutputArgs()[result.getResultNumber()];
35 if (!outputArg.hasOneUse())
36 return false;
37 Operation *argUserOp = *outputArg.user_begin();
38
39 // Check argUser has no other use.
40 if (!argUserOp->use_empty())
41 return false;
42
43 // Check that argUser is this op's own terminator. A nested op's
44 // `linalg.yield` also matches, but leaves the argument live inside that
45 // region.
46 auto yieldOp = dyn_cast<linalg::YieldOp>(Val: argUserOp);
47 if (!yieldOp || yieldOp != genericOp.getBody()->getTerminator())
48 return false;
49
50 // Check outArg data is not being used by other outArgs.
51 if (yieldOp.getOperand(i: result.getResultNumber()) != outputArg)
52 return false;
53
54 return true;
55}
56
57//===---------------------------------------------------------------------===//
58// Helper methods for operand deduplication and dead results elimination
59//===---------------------------------------------------------------------===//
60
61// Deduplicate input operands, and return the
62// - Mapping from operand position in the original op, to operand position in
63// the canonicalized op.
64// - The preserved input operands list (by reference).
65llvm::SmallDenseMap<unsigned, unsigned> static deduplicateInputOperands(
66 GenericOp genericOp, SmallVector<OpOperand *> &droppedOpOperands,
67 SmallVector<Value> &newInputOperands,
68 SmallVector<AffineMap> &newIndexingMaps) {
69 llvm::SmallDenseMap<unsigned, unsigned> origToNewPos;
70 llvm::SmallDenseMap<std::pair<Value, AffineMap>, unsigned> dedupedInputs;
71 for (const auto &en : llvm::enumerate(First: genericOp.getDpsInputOperands())) {
72 OpOperand *inputOpOperand = en.value();
73 // Check if operand is dead and if dropping the indexing map makes the
74 // loops to shape computation invalid.
75 if (!genericOp.payloadUsesValueFromOperand(opOperand: inputOpOperand)) {
76 // Add the current operands to the list of potentially droppable
77 // operands. If it cannot be dropped, this needs to be popped back.
78 droppedOpOperands.push_back(Elt: inputOpOperand);
79 if (genericOp.canOpOperandsBeDropped(droppedOperands: droppedOpOperands))
80 continue;
81 droppedOpOperands.pop_back();
82 }
83
84 // Check if this operand is a duplicate.
85 AffineMap indexingMap = genericOp.getMatchingIndexingMap(opOperand: inputOpOperand);
86 auto it =
87 dedupedInputs.find(Val: std::make_pair(x: inputOpOperand->get(), y&: indexingMap));
88 if (it != dedupedInputs.end()) {
89 origToNewPos[en.index()] = it->second;
90 droppedOpOperands.push_back(Elt: inputOpOperand);
91 continue;
92 }
93
94 // This is a preserved argument.
95 origToNewPos[en.index()] = newInputOperands.size();
96 dedupedInputs[{inputOpOperand->get(), indexingMap}] =
97 newInputOperands.size();
98 newInputOperands.push_back(Elt: inputOpOperand->get());
99 newIndexingMaps.push_back(Elt: indexingMap);
100 }
101 return origToNewPos;
102}
103
104// Deduplicate output operands, and return the
105// - Mapping from operand position in the original op, to operand position in
106// the canonicalized op.
107// - The preserved output operands list (by reference).
108llvm::SmallDenseMap<unsigned, unsigned> static deduplicateOutputOperands(
109 GenericOp genericOp, SmallVector<OpOperand *> &droppedOpOperands,
110 SmallVector<Value> &newOutputOperands,
111 SmallVector<AffineMap> &newIndexingMaps, bool removeOutputs) {
112 llvm::SmallDenseMap<unsigned, unsigned> origToNewPos;
113 llvm::SmallDenseMap<std::tuple<Value, AffineMap, Value>, unsigned>
114 dedupedOutpts;
115 // If the op doesn't have tensor semantics or outputs should not be removed,
116 // keep all the outputs as preserved.
117 if (!genericOp.hasPureTensorSemantics() || !removeOutputs) {
118 for (const auto &en : llvm::enumerate(First: genericOp.getDpsInitsMutable())) {
119 origToNewPos[en.index()] = newOutputOperands.size();
120 newOutputOperands.push_back(Elt: en.value().get());
121 newIndexingMaps.push_back(Elt: genericOp.getMatchingIndexingMap(opOperand: &en.value()));
122 }
123 return origToNewPos;
124 }
125 // Output argument can be dropped if the result has
126 // - no users, and
127 // - it is not used in the payload, and
128 // - the corresponding indexing maps are not needed for loop bound
129 // computation.
130 auto yieldOp = cast<YieldOp>(Val: genericOp.getBody()->getTerminator());
131 for (const auto &outputOpOperand :
132 llvm::enumerate(First: genericOp.getDpsInitsMutable())) {
133 OpResult result = genericOp.getTiedOpResult(opOperand: &outputOpOperand.value());
134 AffineMap indexingMap =
135 genericOp.getMatchingIndexingMap(opOperand: &outputOpOperand.value());
136 auto key = std::make_tuple(args: outputOpOperand.value().get(), args&: indexingMap,
137 args: yieldOp->getOperand(idx: outputOpOperand.index()));
138 if (isResultValueDead(genericOp, result)) {
139 // Check if the opoperand can be dropped without affecting loop
140 // bound computation. Add the operand to the list of dropped op
141 // operand for checking. If it cannot be dropped, need to pop the
142 // value back.
143 droppedOpOperands.push_back(Elt: &outputOpOperand.value());
144 if (genericOp.canOpOperandsBeDropped(droppedOperands: droppedOpOperands)) {
145 continue;
146 }
147 droppedOpOperands.pop_back();
148 }
149
150 if (!genericOp.payloadUsesValueFromOperand(opOperand: &outputOpOperand.value())) {
151 // The out operand can also be dropped if it is computed redundantly
152 // by another result, the conditions for that are
153 // - The same operand is used as the out operand
154 // - The same indexing map is used
155 // - The same yield value is used.
156 auto it = dedupedOutpts.find(Val: key);
157 if (it != dedupedOutpts.end()) {
158 origToNewPos[outputOpOperand.index()] = it->second;
159 droppedOpOperands.push_back(Elt: &outputOpOperand.value());
160 continue;
161 }
162 }
163
164 origToNewPos[outputOpOperand.index()] = newOutputOperands.size();
165 dedupedOutpts[key] = newOutputOperands.size();
166 newOutputOperands.push_back(Elt: outputOpOperand.value().get());
167 newIndexingMaps.push_back(
168 Elt: genericOp.getMatchingIndexingMap(opOperand: &outputOpOperand.value()));
169 }
170 return origToNewPos;
171}
172
173// Populate the body of the canonicalized operation.
174static void populateOpPayload(
175 GenericOp genericOp, GenericOp newOp,
176 const llvm::SmallDenseMap<unsigned, unsigned> &origInsToNewInsPos,
177 const llvm::SmallDenseMap<unsigned, unsigned> &origOutsToNewOutsPos,
178 RewriterBase &rewriter) {
179 // Merge the body of the original op with the new op.
180 Block *newOpBlock = &newOp.getRegion().front();
181 assert(newOpBlock->empty() && "expected new op to have an empty payload");
182 Block *origOpBlock = &genericOp.getRegion().front();
183 SmallVector<Value> replacements(origOpBlock->getNumArguments(), nullptr);
184
185 // Replace all arguments in the original op, with arguments from the
186 // canonicalized op.
187 auto updateReplacements =
188 [&](SmallVector<OpOperand *> &origOperands,
189 SmallVector<OpOperand *> &newOperands,
190 const llvm::SmallDenseMap<unsigned, unsigned> &map) {
191 for (const auto &origOperand : llvm::enumerate(First&: origOperands)) {
192 auto it = map.find(Val: origOperand.index());
193 if (it == map.end())
194 continue;
195 OpOperand *newOperand = newOperands[it->second];
196 replacements[origOperand.value()->getOperandNumber()] =
197 newOpBlock->getArgument(i: newOperand->getOperandNumber());
198 }
199 };
200
201 SmallVector<OpOperand *> origInputOperands = genericOp.getDpsInputOperands();
202 SmallVector<OpOperand *> newInputOperands = newOp.getDpsInputOperands();
203 updateReplacements(origInputOperands, newInputOperands, origInsToNewInsPos);
204
205 SmallVector<OpOperand *> origOutputOperands =
206 llvm::to_vector(Range: llvm::make_pointer_range(Range: genericOp.getDpsInitsMutable()));
207 SmallVector<OpOperand *> newOutputOperands =
208 llvm::to_vector(Range: llvm::make_pointer_range(Range: newOp.getDpsInitsMutable()));
209 updateReplacements(origOutputOperands, newOutputOperands,
210 origOutsToNewOutsPos);
211
212 // Drop the unused yield args.
213 if (newOp.getNumDpsInits() != genericOp.getNumDpsInits()) {
214 OpBuilder::InsertionGuard g(rewriter);
215 YieldOp origYieldOp = cast<YieldOp>(Val: origOpBlock->getTerminator());
216 rewriter.setInsertionPoint(origYieldOp);
217
218 SmallVector<Value> newYieldVals(newOp.getNumDpsInits(), nullptr);
219 for (const auto &yieldOpOperands :
220 llvm::enumerate(First: origYieldOp.getValues())) {
221 auto it = origOutsToNewOutsPos.find(Val: yieldOpOperands.index());
222 if (it == origOutsToNewOutsPos.end())
223 continue;
224 newYieldVals[it->second] = yieldOpOperands.value();
225 }
226 rewriter.replaceOpWithNewOp<YieldOp>(op: origYieldOp, args&: newYieldVals);
227 }
228
229 rewriter.mergeBlocks(source: origOpBlock, dest: newOpBlock, argValues: replacements);
230}
231
232FailureOr<linalg::GenericOp>
233mlir::linalg::deduplicateOperandsAndRemoveDeadResults(
234 RewriterBase &rewriter, linalg::GenericOp genericOp, bool removeOutputs) {
235 // Create a map from argument position in the original op to the argument
236 // position in the new op. If the argument is dropped it wont have an entry.
237 SmallVector<OpOperand *> droppedOpOperands;
238
239 // Information needed to build the new op.
240 SmallVector<Value> newInputOperands, newOutputOperands;
241 SmallVector<AffineMap> newIndexingMaps;
242
243 // Gather information about duplicate input operands.
244 llvm::SmallDenseMap<unsigned, unsigned> origInsToNewInsPos =
245 deduplicateInputOperands(genericOp, droppedOpOperands, newInputOperands,
246 newIndexingMaps);
247
248 // Gather information about the dropped outputs.
249 llvm::SmallDenseMap<unsigned, unsigned> origOutsToNewOutsPos =
250 deduplicateOutputOperands(genericOp, droppedOpOperands, newOutputOperands,
251 newIndexingMaps, removeOutputs);
252
253 // Check if there is any change to operands.
254 if (newInputOperands.size() + newOutputOperands.size() ==
255 genericOp->getNumOperands())
256 return genericOp;
257
258 // Create the new op with the body being empty.
259 Location loc = genericOp.getLoc();
260 SmallVector<Type> newResultTypes;
261 for (Value v : newOutputOperands)
262 if (isa<TensorType>(Val: v.getType()))
263 newResultTypes.push_back(Elt: v.getType());
264 auto newOp = GenericOp::create(
265 builder&: rewriter, location: loc, resultTensorTypes: newResultTypes, inputs: newInputOperands, outputs: newOutputOperands,
266 indexingMaps: rewriter.getAffineMapArrayAttr(values: newIndexingMaps),
267 iteratorTypes: genericOp.getIteratorTypes(), doc: genericOp.getDocAttr(),
268 libraryCall: genericOp.getLibraryCallAttr(),
269 odsArg7: [](OpBuilder & /*builder*/, Location /*loc*/, ValueRange /*args*/) {
270 return;
271 });
272 // Copy over unknown attributes. They might be load bearing for some flow.
273 ArrayRef<StringRef> odsAttrs = genericOp.getAttributeNames();
274 for (NamedAttribute kv : genericOp->getDiscardableAttrDictionary())
275 if (!llvm::is_contained(Range&: odsAttrs, Element: kv.getName().getValue()))
276 newOp->setDiscardableAttr(name: kv.getName(), value: kv.getValue());
277
278 // Fix up the payload of the canonicalized operation.
279 populateOpPayload(genericOp, newOp, origInsToNewInsPos, origOutsToNewOutsPos,
280 rewriter);
281
282 // Replace all live uses of the op.
283 SmallVector<Value> replacementsVals(genericOp->getNumResults(), nullptr);
284 for (const auto &result : llvm::enumerate(First: genericOp.getResults())) {
285 auto it = origOutsToNewOutsPos.find(Val: result.index());
286 if (it == origOutsToNewOutsPos.end())
287 continue;
288 replacementsVals[result.index()] = newOp.getResult(i: it->second);
289 }
290 rewriter.replaceOp(op: genericOp, newValues: replacementsVals);
291 return newOp;
292}
293
294namespace {
295
296struct DeduplicateAndRemoveDeadOperandsAndResults
297 : public OpRewritePattern<GenericOp> {
298 DeduplicateAndRemoveDeadOperandsAndResults(MLIRContext *ctx,
299 bool removeOutputs)
300 : OpRewritePattern<GenericOp>(ctx), removeOutputs(removeOutputs) {}
301
302 LogicalResult matchAndRewrite(GenericOp genericOp,
303 PatternRewriter &rewriter) const override {
304 FailureOr<GenericOp> newOp = deduplicateOperandsAndRemoveDeadResults(
305 rewriter, genericOp, removeOutputs);
306 if (failed(Result: newOp) || newOp.value() == genericOp) {
307 return rewriter.notifyMatchFailure(
308 arg&: genericOp, msg: "failed to dedup operands/remove dead results");
309 }
310 return success();
311 }
312
313private:
314 /// If unset, outputs are not modified by this pattern.
315 bool removeOutputs;
316};
317
318/// Remove unused cycles.
319/// We can remove unused cycle within a payload of generic region
320/// if these conditions are met:
321/// - Result from out operand is dead.
322/// - Block arg from out operand has a single use in the %cycle
323/// instruction.
324/// - Cycle has a single use and it is in yield.
325struct RemoveUnusedCycleInGenericOp : public OpRewritePattern<GenericOp> {
326 using OpRewritePattern<GenericOp>::OpRewritePattern;
327
328 LogicalResult matchAndRewrite(GenericOp genericOp,
329 PatternRewriter &rewriter) const override {
330
331 // If the op doesnt have tensor semantics, preserve the outputs as is.
332 if (!genericOp.hasPureTensorSemantics())
333 return failure();
334
335 bool hasRemovedCycles = false;
336 // Iterate over output operands and remove any unused cycles.
337 for (const auto &outputOpOperand :
338 llvm::enumerate(First: genericOp.getDpsInits())) {
339
340 // Check that result from out operand is dead.
341 Value result = genericOp.getResult(i: outputOpOperand.index());
342 if (!result.use_empty())
343 continue;
344
345 // Check that outputArg has one use in cycle.
346 BlockArgument outputArg =
347 genericOp.getRegionOutputArgs()[outputOpOperand.index()];
348 if (!outputArg.hasOneUse())
349 continue;
350
351 // Check cycle has at most one use.
352 Operation *cycleOp = *outputArg.user_begin();
353 if (!cycleOp->hasOneUse())
354 continue;
355
356 // Check that the cycleUser is a yield.
357 Operation *cycleUserOp = *cycleOp->user_begin();
358 if (!isa<linalg::YieldOp>(Val: cycleUserOp))
359 continue;
360
361 // Check that argIndex matches yieldIndex, else data is being used.
362 if (cycleUserOp->getOperand(idx: outputOpOperand.index()) !=
363 cycleOp->getResult(idx: 0))
364 continue;
365
366 // Directly replace the cycle with the blockArg such that
367 // Deduplicate pattern can eliminate it along with unused yield.
368 rewriter.replaceOp(op: cycleOp, newValues: outputArg);
369 rewriter.modifyOpInPlace(root: genericOp, callable: [] {});
370 hasRemovedCycles = true;
371 }
372
373 if (hasRemovedCycles) {
374 return success();
375 }
376
377 return failure();
378 }
379};
380
381/// Fold uses of duplicate inputs in the body of a linalg.generic. E.g.:
382/// ```
383/// linalg.generic ins(%a, %b, %a, %b) outs(%a)
384/// ^bb0(%in0, %in1, %in2, %in3, %out1)
385/// ```
386/// Assuming that all %a and %b have the same index map:
387/// * All uses of %in0 and %in2 are replaced with %out1
388/// * All uses of %in1 are replaced with %in3
389/// This pattern can enable additional canonicalizations: In the above example,
390/// %in0, %in1 and %in3 have no uses anymore and their corresponding operands
391/// can be folded away. This pattern does not modify uses of output block args.
392struct FoldDuplicateInputBbArgs : public OpRewritePattern<GenericOp> {
393 using OpRewritePattern<GenericOp>::OpRewritePattern;
394
395 LogicalResult matchAndRewrite(GenericOp genericOp,
396 PatternRewriter &rewriter) const override {
397 // Find replacement bbArgs for all input bbArg.
398 DenseMap<int, int> replacements;
399 for (int i = 0; i < genericOp.getNumDpsInputs(); ++i) {
400 // Skip bbArgs that have no uses.
401 if (genericOp.getBody()->getArgument(i).getUses().empty())
402 continue;
403 // Find replacement bbArg. This can be an input or an output bbArg.
404 for (int j = genericOp->getNumOperands() - 1; j > i; --j) {
405 if (genericOp->getOperand(idx: i) == genericOp->getOperand(idx: j) &&
406 genericOp.getIndexingMapsArray()[i] ==
407 genericOp.getIndexingMapsArray()[j]) {
408 replacements[i] = j;
409 break;
410 }
411 }
412 }
413
414 // Stop here if no replacements were found.
415 if (replacements.empty())
416 return failure();
417
418 // Rewrite the op.
419 rewriter.modifyOpInPlace(root: genericOp, callable: [&]() {
420 for (auto [before, after] : replacements) {
421 BlockArgument bbArg = genericOp.getBody()->getArgument(i: before);
422 BlockArgument replacement = genericOp.getBody()->getArgument(i: after);
423 rewriter.replaceAllUsesWith(from: bbArg, to: replacement);
424 }
425 });
426
427 return success();
428 }
429};
430
431} // namespace
432
433void mlir::linalg::populateEraseUnusedOperandsAndResultsPatterns(
434 RewritePatternSet &patterns) {
435 patterns.insert<DeduplicateAndRemoveDeadOperandsAndResults>(
436 arg: patterns.getContext(), /*removeOutputs=*/args: true);
437 patterns.insert<RemoveUnusedCycleInGenericOp>(arg: patterns.getContext());
438}
439
440void mlir::linalg::populateEraseUnnecessaryInputsPatterns(
441 RewritePatternSet &patterns) {
442 patterns.insert<DeduplicateAndRemoveDeadOperandsAndResults>(
443 arg: patterns.getContext(), /*removeOutputs=*/args: false);
444 patterns.insert<FoldDuplicateInputBbArgs>(arg: patterns.getContext());
445}
446