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
20using 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`).
29static 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.
36static 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
83LogicalResult 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
114LogicalResult
115transform::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