| 1 | //===- Utils.cpp - Utils related to the transform dialect -------*- C++ -*-===// |
| 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/Transform/IR/Utils.h" |
| 10 | #include "mlir/Analysis/CallGraph.h" |
| 11 | #include "mlir/Dialect/Transform/IR/TransformDialect.h" |
| 12 | #include "mlir/IR/Verifier.h" |
| 13 | #include "mlir/Interfaces/CallInterfaces.h" |
| 14 | #include "mlir/Interfaces/FunctionInterfaces.h" |
| 15 | #include "mlir/Transforms/InliningUtils.h" |
| 16 | #include "llvm/ADT/SCCIterator.h" |
| 17 | #include "llvm/Support/Debug.h" |
| 18 | #include "llvm/Support/DebugLog.h" |
| 19 | |
| 20 | using namespace mlir; |
| 21 | |
| 22 | #define DEBUG_TYPE "transform-dialect-utils" |
| 23 | #define DBGS() (llvm::dbgs() << "[" DEBUG_TYPE << "]: ") |
| 24 | |
| 25 | /// Return whether `func1` can be merged into `func2`. For that to work |
| 26 | /// `func1` has to be a declaration (aka has to be external) and `func2` |
| 27 | /// either has to be a declaration as well, or it has to be public (otherwise, |
| 28 | /// it wouldn't be visible by `func1`). |
| 29 | static bool canMergeInto(FunctionOpInterface func1, FunctionOpInterface func2) { |
| 30 | return func1.isExternal() && (func2.isPublic() || func2.isExternal()); |
| 31 | } |
| 32 | |
| 33 | /// Merge `func1` into `func2`. The two ops must be inside the same parent op |
| 34 | /// and mergable according to `canMergeInto`. The function erases `func1` such |
| 35 | /// that only `func2` exists when the function returns. |
| 36 | static LogicalResult mergeInto(FunctionOpInterface func1, |
| 37 | FunctionOpInterface func2) { |
| 38 | assert(canMergeInto(func1, func2)); |
| 39 | assert(func1->getParentOp() == func2->getParentOp() && |
| 40 | "expected func1 and func2 to be in the same parent op" ); |
| 41 | |
| 42 | // Check that function signatures match. |
| 43 | if (func1.getFunctionType() != func2.getFunctionType()) { |
| 44 | return func1.emitError() |
| 45 | << "external definition has a mismatching signature (" |
| 46 | << func2.getFunctionType() << ")" ; |
| 47 | } |
| 48 | |
| 49 | // Check and merge argument attributes. |
| 50 | MLIRContext *context = func1->getContext(); |
| 51 | auto *td = context->getLoadedDialect<transform::TransformDialect>(); |
| 52 | StringAttr consumedName = td->getConsumedAttrName(); |
| 53 | StringAttr readOnlyName = td->getReadOnlyAttrName(); |
| 54 | for (unsigned i = 0, e = func1.getNumArguments(); i < e; ++i) { |
| 55 | bool isExternalConsumed = func2.getArgAttr(index: i, name: consumedName) != nullptr; |
| 56 | bool isExternalReadonly = func2.getArgAttr(index: i, name: readOnlyName) != nullptr; |
| 57 | bool isConsumed = func1.getArgAttr(index: i, name: consumedName) != nullptr; |
| 58 | bool isReadonly = func1.getArgAttr(index: i, name: readOnlyName) != nullptr; |
| 59 | if (!isExternalConsumed && !isExternalReadonly) { |
| 60 | if (isConsumed) |
| 61 | func2.setArgAttr(index: i, name: consumedName, value: UnitAttr::get(context)); |
| 62 | else if (isReadonly) |
| 63 | func2.setArgAttr(index: i, name: readOnlyName, value: UnitAttr::get(context)); |
| 64 | continue; |
| 65 | } |
| 66 | |
| 67 | if ((isExternalConsumed && !isConsumed) || |
| 68 | (isExternalReadonly && !isReadonly)) { |
| 69 | return func1.emitError() |
| 70 | << "external definition has mismatching consumption " |
| 71 | "annotations for argument #" |
| 72 | << i; |
| 73 | } |
| 74 | } |
| 75 | |
| 76 | // `func1` is the external one, so we can remove it. |
| 77 | assert(func1.isExternal()); |
| 78 | func1->erase(); |
| 79 | |
| 80 | return success(); |
| 81 | } |
| 82 | |
| 83 | LogicalResult transform::detail::verifyNoRecursionInCallGraph(Operation *root) { |
| 84 | const mlir::CallGraph callgraph(root); |
| 85 | for (auto scc = llvm::scc_begin(G: &callgraph); !scc.isAtEnd(); ++scc) { |
| 86 | if (!scc.hasCycle()) |
| 87 | continue; |
| 88 | |
| 89 | // Need to check this here additionally because this verification may run |
| 90 | // before we check the nested operations. |
| 91 | if ((*scc->begin())->isExternal()) |
| 92 | return root->emitOpError() << "contains a call to an external " |
| 93 | "operation, which is not allowed" ; |
| 94 | |
| 95 | Operation *first = (*scc->begin())->getCallableRegion()->getParentOp(); |
| 96 | InFlightDiagnostic diag = emitError(loc: first->getLoc()) |
| 97 | << "recursion not allowed in named sequences" ; |
| 98 | for (auto it = std::next(x: scc->begin()); it != scc->end(); ++it) { |
| 99 | // Need to check this here additionally because this verification may |
| 100 | // run before we check the nested operations. |
| 101 | if ((*it)->isExternal()) { |
| 102 | return root->emitOpError() << "contains a call to an external " |
| 103 | "operation, which is not allowed" ; |
| 104 | } |
| 105 | |
| 106 | Operation *current = (*it)->getCallableRegion()->getParentOp(); |
| 107 | diag.attachNote(noteLoc: current->getLoc()) << "operation on recursion stack" ; |
| 108 | } |
| 109 | return diag; |
| 110 | } |
| 111 | return success(); |
| 112 | } |
| 113 | |
| 114 | LogicalResult |
| 115 | transform::detail::mergeSymbolsInto(Operation *target, |
| 116 | OwningOpRef<Operation *> other) { |
| 117 | assert(target->hasTrait<OpTrait::SymbolTable>() && |
| 118 | "requires target to implement the 'SymbolTable' trait" ); |
| 119 | assert(other->hasTrait<OpTrait::SymbolTable>() && |
| 120 | "requires target to implement the 'SymbolTable' trait" ); |
| 121 | |
| 122 | SymbolTable targetSymbolTable(target); |
| 123 | SymbolTable otherSymbolTable(*other); |
| 124 | |
| 125 | // Step 1: |
| 126 | // |
| 127 | // Rename private symbols in both ops in order to resolve conflicts that can |
| 128 | // be resolved that way. |
| 129 | LDBG() << "renaming private symbols to resolve conflicts:" ; |
| 130 | // TODO: Do we *actually* need to test in both directions? |
| 131 | for (auto &&[symbolTable, otherSymbolTable] : llvm::zip( |
| 132 | t: SmallVector<SymbolTable *, 2>{&targetSymbolTable, &otherSymbolTable}, |
| 133 | u: SmallVector<SymbolTable *, 2>{&otherSymbolTable, |
| 134 | &targetSymbolTable})) { |
| 135 | Operation *symbolTableOp = symbolTable->getOp(); |
| 136 | for (Operation &op : symbolTableOp->getRegion(index: 0).front()) { |
| 137 | auto symbolOp = dyn_cast<SymbolOpInterface>(Val&: op); |
| 138 | if (!symbolOp) |
| 139 | continue; |
| 140 | StringAttr name = symbolOp.getNameAttr(); |
| 141 | LDBG() << " found @" << name.getValue(); |
| 142 | |
| 143 | // Check if there is a colliding op in the other module. |
| 144 | auto collidingOp = |
| 145 | cast_or_null<SymbolOpInterface>(Val: otherSymbolTable->lookup(name)); |
| 146 | if (!collidingOp) |
| 147 | continue; |
| 148 | |
| 149 | LDBG() << " collision found for @" << name.getValue(); |
| 150 | |
| 151 | // Collisions are fine if both ops are functions and can be merged. |
| 152 | if (auto funcOp = dyn_cast<FunctionOpInterface>(Val&: op), |
| 153 | collidingFuncOp = |
| 154 | dyn_cast<FunctionOpInterface>(Val: collidingOp.getOperation()); |
| 155 | funcOp && collidingFuncOp) { |
| 156 | if (canMergeInto(func1: funcOp, func2: collidingFuncOp) || |
| 157 | canMergeInto(func1: collidingFuncOp, func2: funcOp)) { |
| 158 | LDBG() << " but both ops are functions and will be merged" ; |
| 159 | continue; |
| 160 | } |
| 161 | |
| 162 | // If they can't be merged, proceed like any other collision. |
| 163 | LDBG() << " and both ops are function definitions" ; |
| 164 | } |
| 165 | |
| 166 | // Collision can be resolved by renaming if one of the ops is private. |
| 167 | auto renameToUnique = |
| 168 | [&](SymbolOpInterface op, SymbolOpInterface otherOp, |
| 169 | SymbolTable &symbolTable, |
| 170 | SymbolTable &otherSymbolTable) -> LogicalResult { |
| 171 | LDBG() << ", renaming" ; |
| 172 | FailureOr<StringAttr> maybeNewName = |
| 173 | symbolTable.renameToUnique(op, others: {&otherSymbolTable}); |
| 174 | if (failed(Result: maybeNewName)) { |
| 175 | InFlightDiagnostic diag = op->emitError(message: "failed to rename symbol" ); |
| 176 | diag.attachNote(noteLoc: otherOp->getLoc()) |
| 177 | << "attempted renaming due to collision with this op" ; |
| 178 | return diag; |
| 179 | } |
| 180 | LDBG() << " renamed to @" << maybeNewName->getValue(); |
| 181 | return success(); |
| 182 | }; |
| 183 | |
| 184 | if (symbolOp.isPrivate()) { |
| 185 | if (failed(Result: renameToUnique(symbolOp, collidingOp, *symbolTable, |
| 186 | *otherSymbolTable))) |
| 187 | return failure(); |
| 188 | continue; |
| 189 | } |
| 190 | if (collidingOp.isPrivate()) { |
| 191 | if (failed(Result: renameToUnique(collidingOp, symbolOp, *otherSymbolTable, |
| 192 | *symbolTable))) |
| 193 | return failure(); |
| 194 | continue; |
| 195 | } |
| 196 | LDBG() << ", emitting error" ; |
| 197 | InFlightDiagnostic diag = symbolOp.emitError() |
| 198 | << "doubly defined symbol @" << name.getValue(); |
| 199 | diag.attachNote(noteLoc: collidingOp->getLoc()) << "previously defined here" ; |
| 200 | return diag; |
| 201 | } |
| 202 | } |
| 203 | |
| 204 | // We only modified symbols above, so there is no need to verify everything |
| 205 | // again, just the symbol table. |
| 206 | for (auto *op : SmallVector<Operation *>{target, *other}) { |
| 207 | if (failed(Result: mlir::detail::verifySymbolTable(op))) |
| 208 | return op->emitError() |
| 209 | << "failed to verify symbol table after symbol renaming" ; |
| 210 | } |
| 211 | |
| 212 | // Step 2: |
| 213 | // |
| 214 | // Move all ops from `other` into target and merge public symbols. |
| 215 | LDBG() << "moving all symbols into target" ; |
| 216 | SmallVector<SymbolOpInterface> processedSymbols; |
| 217 | for (Operation &op : other->getRegion(index: 0).front()) { |
| 218 | if (auto symbol = dyn_cast<SymbolOpInterface>(Val&: op)) |
| 219 | processedSymbols.push_back(Elt: symbol); |
| 220 | } |
| 221 | |
| 222 | for (SymbolOpInterface &op : processedSymbols) { |
| 223 | // Remember potentially colliding op in the target module. |
| 224 | auto collidingOp = cast_or_null<SymbolOpInterface>( |
| 225 | Val: targetSymbolTable.lookup(name: op.getNameAttr())); |
| 226 | |
| 227 | // Move op even if we get a collision. |
| 228 | LDBG() << " moving @" << op.getName(); |
| 229 | op->moveBefore(block: &target->getRegion(index: 0).front(), |
| 230 | iterator: target->getRegion(index: 0).front().end()); |
| 231 | |
| 232 | // If there is no collision, we are done -- keep the target symbol |
| 233 | // table in sync with the moved op so that subsequent lookups (and the |
| 234 | // post-merge validation below) remain efficient. |
| 235 | if (!collidingOp) { |
| 236 | LDBG() << " without collision" ; |
| 237 | targetSymbolTable.insert(symbol: op); |
| 238 | continue; |
| 239 | } |
| 240 | |
| 241 | // The two colliding ops must both be functions because we have already |
| 242 | // emitted errors otherwise earlier. |
| 243 | auto funcOp = cast<FunctionOpInterface>(Val: op.getOperation()); |
| 244 | auto collidingFuncOp = |
| 245 | cast<FunctionOpInterface>(Val: collidingOp.getOperation()); |
| 246 | |
| 247 | // Both ops are in the target module now and can be treated |
| 248 | // symmetrically, so w.l.o.g. we can reduce to merging `funcOp` into |
| 249 | // `collidingFuncOp`. |
| 250 | if (!canMergeInto(func1: funcOp, func2: collidingFuncOp)) { |
| 251 | std::swap(a&: funcOp, b&: collidingFuncOp); |
| 252 | } |
| 253 | assert(canMergeInto(funcOp, collidingFuncOp)); |
| 254 | |
| 255 | LDBG() << " with collision, trying to keep op at " |
| 256 | << collidingFuncOp.getLoc() << ":\n" |
| 257 | << collidingFuncOp; |
| 258 | |
| 259 | // Update symbol table. This works with or without the previous `swap`. |
| 260 | targetSymbolTable.remove(op: funcOp); |
| 261 | targetSymbolTable.insert(symbol: collidingFuncOp); |
| 262 | assert(targetSymbolTable.lookup(funcOp.getName()) == collidingFuncOp); |
| 263 | |
| 264 | // Do the actual merging. |
| 265 | if (failed(Result: mergeInto(func1: funcOp, func2: collidingFuncOp))) |
| 266 | return failure(); |
| 267 | |
| 268 | // After merging, only collidingFuncOp exists, update the list to reflect |
| 269 | // this. |
| 270 | op = collidingFuncOp; |
| 271 | } |
| 272 | |
| 273 | // Symbol merging only moves callable ops between symbol tables; it does not |
| 274 | // alter the bodies that were already valid in the source modules. The only |
| 275 | // invariants that may newly be violated after merging are: |
| 276 | // 1. a call now refers to a callee whose body is structurally not legal to |
| 277 | // inline at the call site (caught by the transform dialect's |
| 278 | // `DialectInlinerInterface` implementation), or |
| 279 | // 2. the merged call graph contains a recursive cycle, which is forbidden |
| 280 | // for `transform.named_sequence` callables (caught by the shared |
| 281 | // `verifyNoRecursionInCallGraph` helper). |
| 282 | // Use the inliner interface methods directly (without running the inlining |
| 283 | // pass) to validate (1), and reuse the dialect's call-graph verifier for |
| 284 | // (2). The call graph builder requires call/callable ops to be well-formed, |
| 285 | // so pre-verify them here without recursing into their bodies. |
| 286 | WalkResult preVerify = target->walk(callback: [](Operation *nested) { |
| 287 | if (!isa<CallableOpInterface, CallOpInterface>(Val: nested)) |
| 288 | return WalkResult::advance(); |
| 289 | if (failed(Result: mlir::verify(op: nested, /*verifyRecursively=*/false))) |
| 290 | return WalkResult::interrupt(); |
| 291 | return WalkResult::advance(); |
| 292 | }); |
| 293 | if (preVerify.wasInterrupted()) |
| 294 | return failure(); |
| 295 | |
| 296 | InlinerInterface inliner(target->getContext()); |
| 297 | WalkResult inlineCheck = target->walk(callback: [&](CallOpInterface call) { |
| 298 | Operation *callable = nullptr; |
| 299 | CallInterfaceCallable callee = call.getCallableForCallee(); |
| 300 | if (auto symRef = dyn_cast<SymbolRefAttr>(Val&: callee)) { |
| 301 | // Fall back to full resolution for nested symbols, the table is |
| 302 | // one-level only. |
| 303 | if (isa<FlatSymbolRefAttr>(Val: symRef)) |
| 304 | callable = targetSymbolTable.lookup(name: symRef.getLeafReference()); |
| 305 | else |
| 306 | callable = SymbolTable::lookupNearestSymbolFrom(from: call, symbol: symRef); |
| 307 | } else if (auto value = dyn_cast<Value>(Val&: callee)) { |
| 308 | callable = value.getDefiningOp(); |
| 309 | } |
| 310 | |
| 311 | if (!callable) |
| 312 | return WalkResult::advance(); |
| 313 | |
| 314 | // Only check symbols that we actually moved. |
| 315 | if (!llvm::is_contained(Range&: processedSymbols, Element: callable)) |
| 316 | return WalkResult::advance(); |
| 317 | if (!inliner.isLegalToInline(call, callable, /*wouldBeCloned=*/false)) { |
| 318 | InFlightDiagnostic diag = |
| 319 | call->emitError() |
| 320 | << "merged call is not legal to inline into its caller" ; |
| 321 | diag.attachNote(noteLoc: callable->getLoc()) << "callee defined here" ; |
| 322 | return WalkResult::interrupt(); |
| 323 | } |
| 324 | return WalkResult::advance(); |
| 325 | }); |
| 326 | if (inlineCheck.wasInterrupted()) |
| 327 | return failure(); |
| 328 | |
| 329 | LDBG() << "done merging ops" ; |
| 330 | return verifyNoRecursionInCallGraph(root: target); |
| 331 | } |
| 332 | |