1//===- EmptyTensorElimination.cpp - tensor.empty op elimination -----------===//
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/Bufferization/Transforms/Passes.h"
10
11#include "mlir/Dialect/Bufferization/IR/BufferizableOpInterface.h"
12#include "mlir/Dialect/Bufferization/IR/BufferizationDialect.h"
13#include "mlir/Dialect/Bufferization/Transforms/OneShotAnalysis.h"
14#include "mlir/Dialect/Bufferization/Transforms/OneShotModuleBufferize.h"
15#include "mlir/Dialect/Bufferization/Transforms/Transforms.h"
16#include "mlir/Dialect/Tensor/IR/Tensor.h"
17#include "mlir/IR/Dominance.h"
18#include "mlir/Interfaces/SubsetOpInterface.h"
19#include "mlir/Transforms/RegionUtils.h"
20
21namespace mlir {
22namespace bufferization {
23#define GEN_PASS_DEF_EMPTYTENSORELIMINATIONPASS
24#include "mlir/Dialect/Bufferization/Transforms/Passes.h.inc"
25} // namespace bufferization
26} // namespace mlir
27
28using namespace mlir;
29using namespace mlir::bufferization;
30
31/// Return true if all `neededValues` are in scope at the given
32/// `insertionPoint`.
33static bool
34neededValuesDominateInsertionPoint(const DominanceInfo &domInfo,
35 Operation *insertionPoint,
36 const SmallVector<Value> &neededValues) {
37 for (Value val : neededValues) {
38 if (auto bbArg = dyn_cast<BlockArgument>(Val&: val)) {
39 Block *owner = bbArg.getOwner();
40 if (!owner->findAncestorOpInBlock(op&: *insertionPoint))
41 return false;
42 } else {
43 auto opResult = cast<OpResult>(Val&: val);
44 if (!domInfo.properlyDominates(a: opResult.getOwner(), b: insertionPoint))
45 return false;
46 }
47 }
48 return true;
49}
50
51/// Find a valid insertion point for a replacement of `emptyTensorOp`'s
52/// use of `user` operation, assuming that the replacement may use any
53/// value from `neededValues`.
54static Operation *
55findValidInsertionPoint(Operation *emptyTensorOp, Operation *user,
56 const SmallVector<Value> &neededValues) {
57 DominanceInfo domInfo;
58 Operation *candidateInsertionPoint = emptyTensorOp;
59
60 // Gather all possible insertion points: the location of
61 // `candidateInsertionPoint` and right after the definition of each value in
62 // `neededValues`.
63 SmallVector<Operation *> insertionPointCandidates;
64 insertionPointCandidates.push_back(Elt: candidateInsertionPoint);
65 for (Value val : neededValues) {
66 // Note: The anchor op is using all of `neededValues`, so:
67 // * in case of a block argument: There must be at least one op in the block
68 // (the anchor op or one of its parents).
69 // * in case of an OpResult: There must be at least one op right after the
70 // defining op (the anchor op or one of its
71 // parents).
72 if (auto bbArg = dyn_cast<BlockArgument>(Val&: val)) {
73 insertionPointCandidates.push_back(
74 Elt: &bbArg.getOwner()->getOperations().front());
75 } else {
76 insertionPointCandidates.push_back(Elt: val.getDefiningOp()->getNextNode());
77 }
78 }
79
80 // Select first matching insertion point.
81 for (Operation *insertionPoint : insertionPointCandidates) {
82 // Check if all needed values are in scope.
83 if (!neededValuesDominateInsertionPoint(domInfo, insertionPoint,
84 neededValues))
85 continue;
86 // Check if the insertion point is before the use to be replaced.
87 if (!domInfo.dominates(a: insertionPoint, b: user))
88 continue;
89 return insertionPoint;
90 }
91
92 // No suitable insertion point was found.
93 return nullptr;
94}
95
96Value mlir::bufferization::buildSubsetExtraction(RewriterBase &rewriter,
97 SubsetInsertionOpInterface op,
98 tensor::EmptyOp emptyTensorOp,
99 Operation *user) {
100
101 mlir::OpBuilder::InsertionGuard guard(rewriter);
102 // All values that are needed to create the replacement op.
103 SmallVector<Value> neededValues = op.getValuesNeededToBuildSubsetExtraction();
104 // Find a suitable insertion point. If no suitable insertion point
105 // for the replacement can be found, return an empty value to skip
106 // this replacement.
107 Operation *insertionPoint =
108 findValidInsertionPoint(emptyTensorOp, user, neededValues);
109 if (!insertionPoint) {
110 // If no already suitable insertion point was found, attempt to move all
111 // needed values before the user.
112 if (failed(Result: moveValueDefinitions(rewriter, values: neededValues, insertionPoint: user)))
113 return {};
114 insertionPoint = user;
115 }
116
117 rewriter.setInsertionPoint(insertionPoint);
118 Value replacement =
119 op.buildSubsetExtraction(builder&: rewriter, loc: emptyTensorOp->getLoc());
120 return replacement;
121}
122
123LogicalResult mlir::bufferization::eliminateEmptyTensors(
124 RewriterBase &rewriter, Operation *op, OneShotAnalysisState &state,
125 ControlBuildSubsetExtractionFn subsetsExtractionFn) {
126 OpBuilder::InsertionGuard g(rewriter);
127 llvm::DenseSet<OpOperand *> visitedOpOperands;
128 op->walk(callback: [&](SubsetInsertionOpInterface op) {
129 visitedOpOperands.clear();
130 OpOperand &source = op.getSourceOperand();
131 // Skip operands that do not bufferize inplace. "tensor.empty" could still
132 // be replaced, but the transformation may not be beneficial.
133 if (!state.isInPlace(opOperand&: source))
134 return WalkResult::skip();
135
136 // Find tensor.empty ops on the reverse SSA use-def chain. Only follow
137 // equivalent tensors. I.e., stop when there are ops such as extract_slice
138 // on the path.
139 TraversalConfig config;
140 config.followEquivalentOnly = true;
141 config.alwaysIncludeLeaves = false;
142 // Replace only if the types match or are static <-> dynamic casts. We do
143 // not support slices or reshapes.
144 // TODO: This could be extended to support IR such as:
145 // %0 = tensor.empty() : tensor<128xf32>
146 // %1 = "some_op"(%0) : (tensor<128xf32>) -> (tensor<128xf32>)
147 // %2 = tensor.expand_shape %1 ...
148 // %3 = tensor.insert_slice %2 into ...
149 config.followSameTypeOrCastsOnly = true;
150 SetVector<Value> emptyTensors = state.findValueInReverseUseDefChain(
151 opOperand: &source, /*condition=*/
152 [&](Value val) { return val.getDefiningOp<tensor::EmptyOp>(); }, config,
153 visitedOpOperands: &visitedOpOperands);
154
155 for (Value v : emptyTensors) {
156 auto emptyTensorOp = v.getDefiningOp<tensor::EmptyOp>();
157 assert(emptyTensorOp && "expected tensor.empty op");
158 // Find all the uses that are in the reverse use-def chain and whose
159 // immediate defining op is the tensor.empty op.
160 SmallVector<OpOperand *> usesForReplacement;
161 for (OpOperand *opOperand : visitedOpOperands) {
162 if (opOperand->get() == v)
163 usesForReplacement.push_back(Elt: opOperand);
164 }
165
166 assert(!usesForReplacement.empty() && "could not find any use");
167 for (OpOperand *useToBeReplaced : usesForReplacement) {
168 Operation *user = useToBeReplaced->getOwner();
169
170 auto replacement =
171 subsetsExtractionFn(rewriter, op, emptyTensorOp, user);
172 if (!replacement)
173 continue;
174 if (emptyTensorOp == replacement.getDefiningOp())
175 continue;
176 if (replacement.getType() != v.getType()) {
177 if (cast<ShapedType>(Val: replacement.getType()).getElementType() !=
178 cast<ShapedType>(Val: v.getType()).getElementType())
179 continue;
180 rewriter.setInsertionPointAfterValue(replacement);
181 replacement = tensor::CastOp::create(builder&: rewriter, location: v.getLoc(),
182 dest: v.getType(), source: replacement);
183 }
184 // Replace the specific use of the tensor::EmptyOp.
185 rewriter.modifyOpInPlace(root: user, callable: [&]() {
186 user->setOperand(idx: useToBeReplaced->getOperandNumber(), value: replacement);
187 });
188 state.resetCache();
189 }
190 }
191
192 return WalkResult::advance();
193 });
194
195 return success();
196}
197
198namespace {
199struct EmptyTensorElimination
200 : public bufferization::impl::EmptyTensorEliminationPassBase<
201 EmptyTensorElimination> {
202 using Base::Base;
203
204 void runOnOperation() override;
205
206 void getDependentDialects(DialectRegistry &registry) const override {
207 registry
208 .insert<bufferization::BufferizationDialect, tensor::TensorDialect>();
209 }
210};
211} // namespace
212
213LogicalResult mlir::bufferization::eliminateEmptyTensors(RewriterBase &rewriter,
214 Operation *op) {
215 auto moduleOp = dyn_cast<ModuleOp>(Val: op);
216 OneShotBufferizationOptions options;
217 options.allowReturnAllocsFromLoops = true;
218 if (moduleOp)
219 options.bufferizeFunctionBoundaries = true;
220 OneShotAnalysisState state(op, options);
221 if (moduleOp) {
222 // Module analysis takes into account function boundaries.
223 if (failed(Result: analyzeModuleOp(moduleOp, state)))
224 return failure();
225 } else {
226 // Regular One-Shot Bufferize ignores func.func block arguments, func.call,
227 // func.return.
228 if (failed(Result: analyzeOp(op, state)))
229 return failure();
230 }
231
232 return bufferization::eliminateEmptyTensors(rewriter, op, state);
233}
234
235void EmptyTensorElimination::runOnOperation() {
236 IRRewriter rewriter(getOperation()->getContext());
237 if (failed(Result: bufferization::eliminateEmptyTensors(rewriter, op: getOperation())))
238 signalPassFailure();
239}
240