| 1 | //===- Utils.cpp - Utilities to support the Func dialect ------------------===// |
| 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 | // This file implements utilities for the Func dialect. |
| 10 | // |
| 11 | //===----------------------------------------------------------------------===// |
| 12 | |
| 13 | #include "mlir/Dialect/Func/Utils/Utils.h" |
| 14 | #include "mlir/Dialect/Func/IR/FuncOps.h" |
| 15 | #include "mlir/IR/IRMapping.h" |
| 16 | #include "mlir/IR/PatternMatch.h" |
| 17 | #include "llvm/ADT/STLExtras.h" |
| 18 | #include "llvm/ADT/SmallVector.h" |
| 19 | #include "llvm/Support/DebugLog.h" |
| 20 | |
| 21 | #define DEBUG_TYPE "func-utils" |
| 22 | |
| 23 | using namespace mlir; |
| 24 | |
| 25 | /// This method creates an inverse mapping of the provided map `oldToNew`. |
| 26 | /// Given an array where `oldIdxToNewIdx[i] = j` means old index `i` maps |
| 27 | /// to new index `j`, |
| 28 | /// This method returns a vector where `result[j]` contains all old indices |
| 29 | /// that map to new index `j`. |
| 30 | /// |
| 31 | /// Example: |
| 32 | /// ``` |
| 33 | /// oldIdxToNewIdx = [0, 1, 2, 2, 3] |
| 34 | /// getInverseMapping(oldIdxToNewIdx) = [[0], [1], [2, 3], [4]] |
| 35 | /// ``` |
| 36 | /// |
| 37 | static llvm::SmallVector<llvm::SmallVector<int>> |
| 38 | getInverseMapping(ArrayRef<int> oldIdxToNewIdx) { |
| 39 | int numOfNewIdxs = 0; |
| 40 | if (!oldIdxToNewIdx.empty()) |
| 41 | numOfNewIdxs = 1 + *llvm::max_element(Range&: oldIdxToNewIdx); |
| 42 | llvm::SmallVector<llvm::SmallVector<int>> newToOldIdxs(numOfNewIdxs); |
| 43 | for (auto [oldIdx, newIdx] : llvm::enumerate(First&: oldIdxToNewIdx)) |
| 44 | newToOldIdxs[newIdx].push_back(Elt: oldIdx); |
| 45 | return newToOldIdxs; |
| 46 | } |
| 47 | |
| 48 | /// This method returns a new vector of elements that are mapped from the |
| 49 | /// `origElements` based on the `newIdxToOldIdxs` mapping. This function assumes |
| 50 | /// that the `newIdxToOldIdxs` mapping is valid, i.e. for each new index, there |
| 51 | /// is at least one old index that maps to it. Also, It assumes that mapping to |
| 52 | /// the same old index has the same element in the `origElements` vector. |
| 53 | template <typename Element> |
| 54 | static SmallVector<Element> getMappedElements( |
| 55 | ArrayRef<Element> origElements, |
| 56 | const llvm::SmallVector<llvm::SmallVector<int>> &newIdxToOldIdxs) { |
| 57 | SmallVector<Element> newElements; |
| 58 | for (const auto &oldIdxs : newIdxToOldIdxs) { |
| 59 | assert(llvm::all_of(oldIdxs, |
| 60 | [&origElements](int idx) -> bool { |
| 61 | return idx >= 0 && |
| 62 | static_cast<size_t>(idx) < origElements.size(); |
| 63 | }) && |
| 64 | "idx must be less than the number of elements in the original " |
| 65 | "elements" ); |
| 66 | assert(!oldIdxs.empty() && "oldIdx must not be empty" ); |
| 67 | Element origTypeToCheck = origElements[oldIdxs.front()]; |
| 68 | assert(llvm::all_of(oldIdxs, |
| 69 | [&](int idx) -> bool { |
| 70 | return origElements[idx] == origTypeToCheck; |
| 71 | }) && |
| 72 | "all oldIdxs must be equal" ); |
| 73 | newElements.push_back(origTypeToCheck); |
| 74 | } |
| 75 | return newElements; |
| 76 | } |
| 77 | |
| 78 | FailureOr<func::FuncOp> |
| 79 | func::replaceFuncWithNewMapping(RewriterBase &rewriter, func::FuncOp funcOp, |
| 80 | ArrayRef<int> oldArgIdxToNewArgIdx, |
| 81 | ArrayRef<int> oldResIdxToNewResIdx) { |
| 82 | // Generate an empty new function operation with the same name as the |
| 83 | // original. |
| 84 | assert(funcOp.getNumArguments() == oldArgIdxToNewArgIdx.size() && |
| 85 | "oldArgIdxToNewArgIdx must match the number of arguments in the " |
| 86 | "function" ); |
| 87 | assert( |
| 88 | funcOp.getNumResults() == oldResIdxToNewResIdx.size() && |
| 89 | "oldResIdxToNewResIdx must match the number of results in the function" ); |
| 90 | |
| 91 | if (!funcOp.getBody().hasOneBlock()) |
| 92 | return rewriter.notifyMatchFailure( |
| 93 | arg&: funcOp, msg: "expected function to have exactly one block" ); |
| 94 | |
| 95 | // We may have some duplicate arguments in the old function, i.e. |
| 96 | // in the mapping `newArgIdxToOldArgIdxs` for some new argument index |
| 97 | // there may be multiple old argument indices. |
| 98 | llvm::SmallVector<llvm::SmallVector<int>> newArgIdxToOldArgIdxs = |
| 99 | getInverseMapping(oldIdxToNewIdx: oldArgIdxToNewArgIdx); |
| 100 | SmallVector<Type> newInputTypes = getMappedElements( |
| 101 | origElements: funcOp.getFunctionType().getInputs(), newIdxToOldIdxs: newArgIdxToOldArgIdxs); |
| 102 | |
| 103 | SmallVector<Location> locs; |
| 104 | for (const auto &oldArgIdxs : newArgIdxToOldArgIdxs) |
| 105 | locs.push_back(Elt: funcOp.getArgument(idx: oldArgIdxs.front()).getLoc()); |
| 106 | |
| 107 | llvm::SmallVector<llvm::SmallVector<int>> newResToOldResIdxs = |
| 108 | getInverseMapping(oldIdxToNewIdx: oldResIdxToNewResIdx); |
| 109 | SmallVector<Type> newOutputTypes = getMappedElements( |
| 110 | origElements: funcOp.getFunctionType().getResults(), newIdxToOldIdxs: newResToOldResIdxs); |
| 111 | |
| 112 | rewriter.setInsertionPoint(funcOp); |
| 113 | auto newFuncOp = func::FuncOp::create( |
| 114 | builder&: rewriter, location: funcOp.getLoc(), name: funcOp.getName(), |
| 115 | type: rewriter.getFunctionType(inputs: newInputTypes, results: newOutputTypes)); |
| 116 | |
| 117 | Region &newRegion = newFuncOp.getBody(); |
| 118 | rewriter.createBlock(parent: &newRegion, insertPt: newRegion.begin(), argTypes: newInputTypes, locs); |
| 119 | newFuncOp.setVisibility(funcOp.getVisibility()); |
| 120 | |
| 121 | // Map the arguments of the original function to the new function in |
| 122 | // the new order and adjust the attributes accordingly. |
| 123 | IRMapping operandMapper; |
| 124 | SmallVector<DictionaryAttr> argAttrs, resultAttrs; |
| 125 | funcOp.getAllArgAttrs(result&: argAttrs); |
| 126 | for (auto [oldArgIdx, newArgIdx] : llvm::enumerate(First&: oldArgIdxToNewArgIdx)) |
| 127 | operandMapper.map(from: funcOp.getArgument(idx: oldArgIdx), |
| 128 | to: newFuncOp.getArgument(idx: newArgIdx)); |
| 129 | for (auto [newArgIdx, oldArgIdx] : llvm::enumerate(First&: newArgIdxToOldArgIdxs)) |
| 130 | newFuncOp.setArgAttrs(index: newArgIdx, attributes: argAttrs[oldArgIdx.front()]); |
| 131 | |
| 132 | funcOp.getAllResultAttrs(result&: resultAttrs); |
| 133 | for (auto [newResIdx, oldResIdx] : llvm::enumerate(First&: newResToOldResIdxs)) |
| 134 | newFuncOp.setResultAttrs(index: newResIdx, attributes: resultAttrs[oldResIdx.front()]); |
| 135 | |
| 136 | // Clone the operations from the original function to the new function. |
| 137 | rewriter.setInsertionPointToStart(&newFuncOp.getBody().front()); |
| 138 | for (Operation &op : funcOp.getOps()) |
| 139 | rewriter.clone(op, mapper&: operandMapper); |
| 140 | |
| 141 | // Handle the return operation. |
| 142 | auto returnOp = cast<func::ReturnOp>( |
| 143 | Val: newFuncOp.getFunctionBody().begin()->getTerminator()); |
| 144 | SmallVector<Value> newReturnValues; |
| 145 | for (const auto &oldResIdxs : newResToOldResIdxs) |
| 146 | newReturnValues.push_back(Elt: returnOp.getOperand(i: oldResIdxs.front())); |
| 147 | |
| 148 | rewriter.setInsertionPoint(returnOp); |
| 149 | func::ReturnOp::create(builder&: rewriter, location: newFuncOp.getLoc(), operands: newReturnValues); |
| 150 | rewriter.eraseOp(op: returnOp); |
| 151 | |
| 152 | rewriter.eraseOp(op: funcOp); |
| 153 | |
| 154 | return newFuncOp; |
| 155 | } |
| 156 | |
| 157 | func::CallOp |
| 158 | func::replaceCallOpWithNewMapping(RewriterBase &rewriter, func::CallOp callOp, |
| 159 | ArrayRef<int> oldArgIdxToNewArgIdx, |
| 160 | ArrayRef<int> oldResIdxToNewResIdx) { |
| 161 | assert(callOp.getNumOperands() == oldArgIdxToNewArgIdx.size() && |
| 162 | "oldArgIdxToNewArgIdx must match the number of operands in the call " |
| 163 | "operation" ); |
| 164 | assert(callOp.getNumResults() == oldResIdxToNewResIdx.size() && |
| 165 | "oldResIdxToNewResIdx must match the number of results in the call " |
| 166 | "operation" ); |
| 167 | |
| 168 | SmallVector<Value> origOperands = callOp.getOperands(); |
| 169 | SmallVector<llvm::SmallVector<int>> newArgIdxToOldArgIdxs = |
| 170 | getInverseMapping(oldIdxToNewIdx: oldArgIdxToNewArgIdx); |
| 171 | SmallVector<Value> newOperandsValues = |
| 172 | getMappedElements<Value>(origElements: origOperands, newIdxToOldIdxs: newArgIdxToOldArgIdxs); |
| 173 | SmallVector<llvm::SmallVector<int>> newResToOldResIdxs = |
| 174 | getInverseMapping(oldIdxToNewIdx: oldResIdxToNewResIdx); |
| 175 | SmallVector<Type> origResultTypes = llvm::to_vector(Range: callOp.getResultTypes()); |
| 176 | SmallVector<Type> newResultTypes = |
| 177 | getMappedElements<Type>(origElements: origResultTypes, newIdxToOldIdxs: newResToOldResIdxs); |
| 178 | |
| 179 | // Replace the kernel call operation with a new one that has the |
| 180 | // mapped arguments. |
| 181 | rewriter.setInsertionPoint(callOp); |
| 182 | auto newCallOp = |
| 183 | func::CallOp::create(builder&: rewriter, location: callOp.getLoc(), callee: callOp.getCallee(), |
| 184 | results: newResultTypes, operands: newOperandsValues); |
| 185 | newCallOp.setNoInlineAttr(callOp.getNoInlineAttr()); |
| 186 | for (auto &&[oldResIdx, newResIdx] : llvm::enumerate(First&: oldResIdxToNewResIdx)) |
| 187 | rewriter.replaceAllUsesWith(from: callOp.getResult(i: oldResIdx), |
| 188 | to: newCallOp.getResult(i: newResIdx)); |
| 189 | rewriter.eraseOp(op: callOp); |
| 190 | |
| 191 | return newCallOp; |
| 192 | } |
| 193 | |
| 194 | FailureOr<std::pair<func::FuncOp, func::CallOp>> |
| 195 | func::deduplicateArgsOfFuncOp(RewriterBase &rewriter, func::FuncOp funcOp, |
| 196 | ModuleOp moduleOp) { |
| 197 | SmallVector<func::CallOp> callOps; |
| 198 | auto traversalResult = moduleOp.walk(callback: [&](func::CallOp callOp) { |
| 199 | if (callOp.getCallee() == funcOp.getSymName()) { |
| 200 | if (!callOps.empty()) |
| 201 | // Only support one callOp for now |
| 202 | return WalkResult::interrupt(); |
| 203 | callOps.push_back(Elt: callOp); |
| 204 | } |
| 205 | return WalkResult::advance(); |
| 206 | }); |
| 207 | |
| 208 | if (traversalResult.wasInterrupted()) { |
| 209 | LDBG() << "function " << funcOp.getName() << " has more than one callOp" ; |
| 210 | return failure(); |
| 211 | } |
| 212 | |
| 213 | if (callOps.empty()) { |
| 214 | LDBG() << "function " << funcOp.getName() << " does not have any callOp" ; |
| 215 | return failure(); |
| 216 | } |
| 217 | |
| 218 | func::CallOp callOp = callOps.front(); |
| 219 | |
| 220 | // Create mapping for arguments (deduplicate operands) |
| 221 | SmallVector<int> oldArgIdxToNewArgIdx(callOp.getNumOperands()); |
| 222 | llvm::DenseMap<Value, int> valueToNewArgIdx; |
| 223 | for (auto [operandIdx, operand] : llvm::enumerate(First: callOp.getOperands())) { |
| 224 | auto [iterator, inserted] = valueToNewArgIdx.insert( |
| 225 | KV: {operand, static_cast<int>(valueToNewArgIdx.size())}); |
| 226 | // Reduce the duplicate operands and maintain the original order. |
| 227 | oldArgIdxToNewArgIdx[operandIdx] = iterator->second; |
| 228 | } |
| 229 | |
| 230 | bool hasDuplicateOperands = |
| 231 | valueToNewArgIdx.size() != callOp.getNumOperands(); |
| 232 | if (!hasDuplicateOperands) { |
| 233 | LDBG() << "function " << funcOp.getName() |
| 234 | << " does not have duplicate operands" ; |
| 235 | return failure(); |
| 236 | } |
| 237 | |
| 238 | // Create identity mapping for results (no deduplication needed) |
| 239 | SmallVector<int> oldResIdxToNewResIdx(callOp.getNumResults()); |
| 240 | for (int resultIdx : llvm::seq<int>(Begin: 0, End: callOp.getNumResults())) |
| 241 | oldResIdxToNewResIdx[resultIdx] = resultIdx; |
| 242 | |
| 243 | // Apply the transformation to create new function and call operations |
| 244 | FailureOr<func::FuncOp> newFuncOpOrFailure = replaceFuncWithNewMapping( |
| 245 | rewriter, funcOp, oldArgIdxToNewArgIdx, oldResIdxToNewResIdx); |
| 246 | if (failed(Result: newFuncOpOrFailure)) { |
| 247 | LDBG() << "failed to replace function signature with name " |
| 248 | << funcOp.getName() << " with new order" ; |
| 249 | return failure(); |
| 250 | } |
| 251 | |
| 252 | func::CallOp newCallOp = replaceCallOpWithNewMapping( |
| 253 | rewriter, callOp, oldArgIdxToNewArgIdx, oldResIdxToNewResIdx); |
| 254 | |
| 255 | return std::make_pair(x&: *newFuncOpOrFailure, y&: newCallOp); |
| 256 | } |
| 257 | |
| 258 | FailureOr<func::FuncOp> |
| 259 | func::lookupFnDecl(SymbolOpInterface symTable, StringRef name, |
| 260 | FunctionType funcT, SymbolTableCollection *symbolTables) { |
| 261 | FuncOp func; |
| 262 | if (symbolTables) { |
| 263 | func = symbolTables->lookupSymbolIn<FuncOp>( |
| 264 | symbolTableOp: symTable, name: StringAttr::get(context: symTable->getContext(), bytes: name)); |
| 265 | } else { |
| 266 | func = llvm::dyn_cast_or_null<FuncOp>( |
| 267 | Val: SymbolTable::lookupSymbolIn(op: symTable, symbol: name)); |
| 268 | } |
| 269 | |
| 270 | if (!func) |
| 271 | return func; |
| 272 | |
| 273 | mlir::FunctionType foundFuncT = func.getFunctionType(); |
| 274 | // Assert the signature of the found function is same as expected |
| 275 | if (funcT != foundFuncT) { |
| 276 | return func.emitError(message: "matched function '" ) |
| 277 | << name << "' but with different type: " << foundFuncT |
| 278 | << " (expected " << funcT << ")" ; |
| 279 | } |
| 280 | return func; |
| 281 | } |
| 282 | |
| 283 | func::FuncOp func::createFnDecl(OpBuilder &b, SymbolOpInterface symTable, |
| 284 | StringRef name, FunctionType funcT, |
| 285 | bool setPrivate, |
| 286 | SymbolTableCollection *symbolTables) { |
| 287 | OpBuilder::InsertionGuard g(b); |
| 288 | assert(!symTable->getRegion(0).empty() && "expected non-empty region" ); |
| 289 | b.setInsertionPointToStart(&symTable->getRegion(index: 0).front()); |
| 290 | func::FuncOp funcOp = |
| 291 | func::FuncOp::create(builder&: b, location: symTable->getLoc(), name, type: funcT); |
| 292 | if (setPrivate) |
| 293 | funcOp.setPrivate(); |
| 294 | if (symbolTables) { |
| 295 | SymbolTable &symbolTable = symbolTables->getSymbolTable(op: symTable); |
| 296 | symbolTable.insert(symbol: funcOp, insertPt: symTable->getRegion(index: 0).front().begin()); |
| 297 | } |
| 298 | return funcOp; |
| 299 | } |
| 300 | |
| 301 | FailureOr<func::FuncOp> |
| 302 | func::lookupOrCreateFnDecl(OpBuilder &b, SymbolOpInterface symTable, |
| 303 | StringRef funcName, TypeRange paramTypes, |
| 304 | SymbolTableCollection *symbolTables, |
| 305 | Type resultType) { |
| 306 | if (!resultType) |
| 307 | resultType = IntegerType::get(context: symTable->getContext(), width: 64); |
| 308 | auto funcT = FunctionType::get(context: b.getContext(), inputs: paramTypes, results: {resultType}); |
| 309 | FailureOr<func::FuncOp> func = |
| 310 | lookupFnDecl(symTable, name: funcName, funcT, symbolTables); |
| 311 | // Failed due to type mismatch. |
| 312 | if (failed(Result: func)) |
| 313 | return func; |
| 314 | // Successfully matched existing decl. |
| 315 | if (*func) |
| 316 | return *func; |
| 317 | |
| 318 | return createFnDecl(b, symTable, name: funcName, funcT, |
| 319 | /*setPrivate=*/true, symbolTables); |
| 320 | } |
| 321 | |