1//===- ScalarizeFunctionResult.cpp - Scalarize tensor returns ---------===//
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/Arith/IR/Arith.h"
10#include "mlir/Dialect/Func/IR/FuncOps.h"
11#include "mlir/Dialect/Tensor/IR/Tensor.h"
12#include "mlir/Dialect/Tensor/Transforms/Passes.h"
13#include "mlir/IR/BuiltinOps.h"
14#include "mlir/IR/PatternMatch.h"
15#include "mlir/IR/SymbolTable.h"
16#include "llvm/ADT/DenseMap.h"
17
18namespace mlir {
19namespace tensor {
20#define GEN_PASS_DEF_SCALARIZESINGLEELEMENTTENSORRETURNPASS
21#include "mlir/Dialect/Tensor/Transforms/Passes.h.inc"
22} // namespace tensor
23} // namespace mlir
24
25using namespace mlir;
26
27namespace {
28
29// Analysis state used by the memoized DFS below. It classifies whether a
30// candidate private function can be scalarized. The rewrite only consumes the
31// functions classified as `rewritable`.
32enum class ScalarizationState {
33 // No DFS classification has been computed for this function yet.
34 unknown,
35 // The function is currently on the recursive DFS stack. Re-entering this
36 // state means a cycle was found, which this pass conservatively blocks.
37 visiting,
38 // A symbol user or a candidate caller blocks the rewrite.
39 blocked,
40 // The function is locally eligible and all transitive users considered by
41 // this pass can be updated consistently.
42 rewritable
43};
44
45// Info analyzed to decide scalarizing a locally eligible function: a private
46// definition with exactly one statically-shaped ranked tensor result containing
47// one element. Functions not meeting these criteria are not represented here,
48// although they may still appear in the broader module analysis as callers or
49// blockers.
50struct ScalarizableFunctionInfo {
51 RankedTensorType tensorType;
52 SmallVector<func::ReturnOp> returnOps;
53};
54
55// Returns per-function scalarization info when this function is locally
56// eligible, i.e. it is a private definition with one statically-shaped ranked
57// tensor result containing exactly one element.
58static FailureOr<ScalarizableFunctionInfo>
59getScalarizableFunctionInfoIfEligible(func::FuncOp func) {
60 if (func.isDeclaration() || !func.isPrivate())
61 return failure();
62
63 FunctionType functionType = func.getFunctionType();
64 if (functionType.getNumResults() != 1)
65 return failure();
66
67 auto tensorType = dyn_cast<RankedTensorType>(Val: functionType.getResult(i: 0));
68 if (!tensorType || !tensorType.hasStaticShape() ||
69 tensorType.getNumElements() != 1)
70 return failure();
71
72 ScalarizableFunctionInfo sfi{.tensorType: tensorType, .returnOps: {}};
73 for (Block &block : func.getBody()) {
74 auto returnOp = dyn_cast<func::ReturnOp>(Val: block.getTerminator());
75 if (returnOp)
76 sfi.returnOps.push_back(Elt: returnOp);
77 }
78
79 // While FuncOp is guaranteed to contain terminator ops, there is no guarantee
80 // that it will contain ReturnOp(s). Hence the check.
81 if (sfi.returnOps.empty())
82 return failure();
83 return sfi;
84}
85
86struct ScalarizationAnalysis {
87 explicit ScalarizationAnalysis(SymbolUserMap &userMap) : userMap(userMap) {}
88
89 SymbolUserMap &userMap;
90 DenseMap<func::FuncOp, ScalarizableFunctionInfo> candidateInfos;
91 DenseMap<func::FuncOp, SmallVector<func::CallOp>> callUsers;
92 DenseMap<func::FuncOp, ScalarizationState> states;
93 // DFS completion order for rewritable functions. The rewrite phase walks
94 // this list in reverse so callees are rewritten before candidate callers.
95 SmallVector<func::FuncOp> rewriteOrder;
96};
97
98// Classifies a locally eligible candidate using memoized DFS through candidate
99// callers. Local eligibility must be cached for the entire module first.
100static ScalarizationState
101computeScalarizationState(func::FuncOp func, ScalarizationAnalysis &analysis) {
102 auto [it, inserted] =
103 analysis.states.try_emplace(Key: func, Args: ScalarizationState::unknown);
104 if (!inserted) {
105 // Conservatively reject recursive cycles instead of reasoning about SCCs.
106 if (it->second == ScalarizationState::visiting)
107 return ScalarizationState::blocked;
108 return it->second;
109 }
110
111 // Starting from one locally-eligible private function, walk its symbol users
112 // upward through private callers. Memoization avoids re-traversing the same
113 // subgraph from the outer linear scan, and early blocking truncates the DFS
114 // when an unsupported symbol user or a blocked candidate caller is found.
115 // Non-candidate callers, including public functions, stop recursion without
116 // blocking callsite adaptation.
117 auto setBlocked = [&] {
118 analysis.states[func] = ScalarizationState::blocked;
119 return ScalarizationState::blocked;
120 };
121 auto setRewritable = [&] {
122 analysis.states[func] = ScalarizationState::rewritable;
123 analysis.rewriteOrder.push_back(Elt: func);
124 return ScalarizationState::rewritable;
125 };
126
127 analysis.states[func] = ScalarizationState::visiting;
128
129 SmallVector<func::CallOp> directCallUsers;
130 for (Operation *user : analysis.userMap.getUsers(symbol: func.getOperation())) {
131 auto directCall = dyn_cast<func::CallOp>(Val: user);
132 // Non-call symbol uses, such as func.constant, prevent updating all users
133 // consistently, so the current function stays blocked.
134 if (!directCall)
135 return setBlocked();
136 directCallUsers.push_back(Elt: directCall);
137
138 func::FuncOp caller = directCall->getParentOfType<func::FuncOp>();
139 // Cache every direct call, but recurse only into candidate callers. Other
140 // callers, including public functions, keep their signatures and existing
141 // tensor uses through reboxing. Calls outside any func.func stop here too.
142 if (!caller || !analysis.candidateInfos.contains(Val: caller))
143 continue;
144
145 if (computeScalarizationState(func: caller, analysis) !=
146 ScalarizationState::rewritable)
147 return setBlocked();
148 }
149
150 analysis.callUsers.try_emplace(Key: func, Args: std::move(directCallUsers));
151 return setRewritable();
152}
153
154// Builds the module-level analysis state used by the rewrite phase.
155static void computeScalarizationAnalysis(ModuleOp module,
156 ScalarizationAnalysis &analysis) {
157 // Cache local eligibility for all direct functions before starting DFS.
158 for (func::FuncOp func : module.getOps<func::FuncOp>()) {
159 FailureOr<ScalarizableFunctionInfo> sfi =
160 getScalarizableFunctionInfoIfEligible(func);
161 if (succeeded(Result: sfi))
162 analysis.candidateInfos.try_emplace(Key: func, Args: std::move(*sfi));
163 }
164 // Then run the memoized DFS for candidate roots.
165 for (func::FuncOp func : module.getOps<func::FuncOp>())
166 if (analysis.candidateInfos.contains(Val: func))
167 (void)computeScalarizationState(func, analysis);
168}
169
170// Rewrites one function that has already been proven rewritable and updates
171// the direct call users cached before any IR mutation started.
172static void rewriteScalarizableFunction(func::FuncOp func,
173 const ScalarizableFunctionInfo &sfi,
174 ArrayRef<func::CallOp> directCalls,
175 RewriterBase &rewriter) {
176 OpBuilder::InsertionGuard guard(rewriter);
177 // Scalarize the unique element before each return.
178 RankedTensorType tensorType = sfi.tensorType;
179 SmallVector<Value> zeroIndices;
180 if (tensorType.getRank() != 0) {
181 rewriter.setInsertionPointToStart(&func.getBody().front());
182 Value zero = arith::ConstantIndexOp::create(builder&: rewriter, location: func.getLoc(), value: 0);
183 zeroIndices.assign(NumElts: tensorType.getRank(), Elt: zero);
184 }
185
186 Type scalarType = tensorType.getElementType();
187 for (func::ReturnOp funcReturn : sfi.returnOps) {
188 assert(funcReturn.getNumOperands() == 1 &&
189 "func.return must have exactly one operand");
190 assert(funcReturn.getOperand(0).getType() == tensorType &&
191 "func.return operand type must match the function result type");
192 rewriter.setInsertionPoint(funcReturn);
193 Value scalar = rewriter.createOrFold<tensor::ExtractOp>(
194 location: funcReturn.getLoc(), args: funcReturn.getOperand(i: 0), args&: zeroIndices);
195 rewriter.replaceOpWithNewOp<func::ReturnOp>(op: funcReturn, args&: scalar);
196 }
197
198 FunctionType functionType = func.getFunctionType();
199 // Update the function type:
200 // This is a 1-result to 1-result type replacement, so the existing result
201 // attribute dictionary remains attached to result #0 without reordering,
202 // hence the rewrite is done directly without function_interface methods.
203 func.setType(FunctionType::get(context: func.getContext(), inputs: functionType.getInputs(),
204 results: TypeRange{scalarType}));
205 // Fix direct call users that were recorded during analysis.
206 for (func::CallOp directCall : directCalls) {
207 rewriter.setInsertionPoint(directCall);
208 func::CallOp newDirectCall = func::CallOp::create(
209 builder&: rewriter, location: directCall.getLoc(), callee: func, operands: directCall.getOperands());
210 newDirectCall->setDiscardableAttrs(
211 directCall->getDiscardableAttrDictionary());
212
213 if (!directCall.getResult(i: 0).use_empty()) {
214 Value wrappedResult = tensor::FromElementsOp::create(
215 builder&: rewriter, location: directCall.getLoc(), result: tensorType,
216 elements: ValueRange{newDirectCall.getResult(i: 0)});
217 rewriter.replaceOp(op: directCall, newValues: wrappedResult);
218 } else {
219 rewriter.eraseOp(op: directCall);
220 }
221 }
222}
223
224/// Drives the complete module-level transform: analyze the original module,
225/// determine which private functions can be scalarized safely, then
226/// rewrite only that precomputed set.
227///
228/// BEFORE (both callee and private caller rewritten)
229/// private callee(x : tensor<1xT>) -> tensor<1xT> { return x }
230/// private caller(x : tensor<1xT>) -> tensor<1xT> {
231/// y = call callee(x)
232/// return y
233/// }
234///
235/// AFTER
236/// private callee(x : tensor<1xT>) -> T {
237/// return tensor.extract x[0]
238/// }
239/// private caller(x : tensor<1xT>) -> T {
240/// y = call callee(x)
241/// return y
242/// }
243///
244/// BEFORE (callee rewritten, unchanged private caller reboxes)
245/// private callee(x : tensor<1xT>) -> tensor<1xT> { return x }
246/// private caller(x : tensor<1xT>, z : tensor<1xT>) -> tensor<1xT> {
247/// y = call callee(x)
248/// r = tensor_op(y, z)
249/// return r
250/// }
251///
252/// AFTER
253/// private callee(x : tensor<1xT>) -> T {
254/// return tensor.extract x[0]
255/// }
256/// private caller(x : tensor<1xT>, z : tensor<1xT>) -> tensor<1xT> {
257/// y = call callee(x)
258/// y_boxed = tensor.from_elements y
259/// r = tensor_op(y_boxed, z)
260/// return r
261/// }
262static LogicalResult
263ScalarizeSingleElementTensorReturns(ModuleOp module, RewriterBase &rewriter) {
264 // The transform depends on module-scoped `SymbolUserMap` state and on a
265 // precomputed DFS result, so it runs as a direct module analysis + rewrite
266 // instead of exposing a pattern-testing / transform-dialect pattern path.
267 SymbolTableCollection symbolTable;
268 // Take a snapshot of symbol users for the original module. This is safe
269 // because it is consulted only during `computeScalarizationAnalysis`, before
270 // rewriting starts, and this pass invocation has exclusive access to the
271 // current module.
272 SymbolUserMap userMap(symbolTable, module);
273 ScalarizationAnalysis analysis(userMap);
274 computeScalarizationAnalysis(module, analysis);
275
276 for (func::FuncOp func : llvm::reverse(C&: analysis.rewriteOrder)) {
277 const ScalarizableFunctionInfo &sfi =
278 analysis.candidateInfos.find(Val: func)->second;
279 ArrayRef<func::CallOp> directCalls = analysis.callUsers.find(Val: func)->second;
280 rewriteScalarizableFunction(func, sfi, directCalls, rewriter);
281 }
282
283 return success();
284}
285
286struct ScalarizeSingleElementTensorReturnPass
287 : public tensor::impl::ScalarizeSingleElementTensorReturnPassBase<
288 ScalarizeSingleElementTensorReturnPass> {
289 using Base::Base;
290
291 void runOnOperation() override {
292 IRRewriter rewriter(&getContext());
293 if (failed(Result: ScalarizeSingleElementTensorReturns(module: getOperation(), rewriter)))
294 signalPassFailure();
295 }
296};
297
298} // namespace
299