| 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 | |
| 18 | namespace mlir { |
| 19 | namespace tensor { |
| 20 | #define GEN_PASS_DEF_SCALARIZESINGLEELEMENTTENSORRETURNPASS |
| 21 | #include "mlir/Dialect/Tensor/Transforms/Passes.h.inc" |
| 22 | } // namespace tensor |
| 23 | } // namespace mlir |
| 24 | |
| 25 | using namespace mlir; |
| 26 | |
| 27 | namespace { |
| 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`. |
| 32 | enum 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. |
| 50 | struct 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. |
| 58 | static FailureOr<ScalarizableFunctionInfo> |
| 59 | getScalarizableFunctionInfoIfEligible(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 | |
| 86 | struct 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. |
| 100 | static ScalarizationState |
| 101 | computeScalarizationState(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. |
| 155 | static 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. |
| 172 | static 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 | /// } |
| 262 | static LogicalResult |
| 263 | ScalarizeSingleElementTensorReturns(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 | |
| 286 | struct 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 | |