1//===- Inliner.cpp ---- SCC-based inliner ---------------------------------===//
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 Inliner that uses a basic inlining
10// algorithm that operates bottom up over the Strongly Connect Components(SCCs)
11// of the CallGraph. This enables a more incremental propagation of inlining
12// decisions from the leafs to the roots of the callgraph.
13//
14//===----------------------------------------------------------------------===//
15
16#include "mlir/Transforms/Inliner.h"
17#include "mlir/IR/Threading.h"
18#include "mlir/Interfaces/CallInterfaces.h"
19#include "mlir/Interfaces/SideEffectInterfaces.h"
20#include "mlir/Support/DebugStringHelper.h"
21#include "mlir/Transforms/InliningUtils.h"
22#include "llvm/ADT/DenseSet.h"
23#include "llvm/ADT/SCCIterator.h"
24#include "llvm/ADT/STLExtras.h"
25#include "llvm/Support/DebugLog.h"
26
27#define DEBUG_TYPE "inlining"
28
29using namespace mlir;
30
31using ResolvedCall = Inliner::ResolvedCall;
32
33//===----------------------------------------------------------------------===//
34// Symbol Use Tracking
35//===----------------------------------------------------------------------===//
36
37/// Walk all of the used symbol callgraph nodes referenced with the given op.
38static void walkReferencedSymbolNodes(
39 Operation *op, CallGraph &cg, SymbolTableCollection &symbolTable,
40 DenseMap<Attribute, CallGraphNode *> &resolvedRefs,
41 function_ref<void(CallGraphNode *, Operation *)> callback) {
42 auto symbolUses = SymbolTable::getSymbolUses(from: op);
43 assert(symbolUses && "expected uses to be valid");
44
45 Operation *symbolTableOp = op->getParentOp();
46 for (const SymbolTable::SymbolUse &use : *symbolUses) {
47 auto refIt = resolvedRefs.try_emplace(Key: use.getSymbolRef());
48 CallGraphNode *&node = refIt.first->second;
49
50 // If this is the first instance of this reference, try to resolve a
51 // callgraph node for it.
52 if (refIt.second) {
53 auto *symbolOp = symbolTable.lookupNearestSymbolFrom(from: symbolTableOp,
54 symbol: use.getSymbolRef());
55 auto callableOp = dyn_cast_or_null<CallableOpInterface>(Val: symbolOp);
56 if (!callableOp)
57 continue;
58 node = cg.lookupNode(region: callableOp.getCallableRegion());
59 }
60 if (node)
61 callback(node, use.getUser());
62 }
63}
64
65//===----------------------------------------------------------------------===//
66// CGUseList
67//===----------------------------------------------------------------------===//
68
69namespace {
70/// This struct tracks the uses of callgraph nodes that can be dropped when
71/// use_empty. It directly tracks and manages a use-list for all of the
72/// call-graph nodes. This is necessary because many callgraph nodes are
73/// referenced by SymbolRefAttr, which has no mechanism akin to the SSA `Use`
74/// class.
75struct CGUseList {
76 /// This struct tracks the uses of callgraph nodes within a specific
77 /// operation.
78 struct CGUser {
79 /// Any nodes referenced in the top-level attribute list of this user. We
80 /// use a set here because the number of references does not matter.
81 DenseSet<CallGraphNode *> topLevelUses;
82
83 /// Uses of nodes referenced by nested operations.
84 DenseMap<CallGraphNode *, int> innerUses;
85 };
86
87 CGUseList(Operation *op, CallGraph &cg, SymbolTableCollection &symbolTable);
88
89 /// Drop uses of nodes referred to by the given call operation that resides
90 /// within 'userNode'.
91 void dropCallUses(CallGraphNode *userNode, Operation *callOp, CallGraph &cg);
92
93 /// Remove the given node from the use list.
94 void eraseNode(CallGraphNode *node);
95
96 /// Returns true if the given callgraph node has no uses and can be pruned.
97 bool isDead(CallGraphNode *node) const;
98
99 /// Returns true if the given callgraph node has a single use and can be
100 /// discarded.
101 bool hasOneUseAndDiscardable(CallGraphNode *node) const;
102
103 /// Recompute the uses held by the given callgraph node.
104 void recomputeUses(CallGraphNode *node, CallGraph &cg);
105
106 /// Merge the uses of 'lhs' with the uses of the 'rhs' after inlining a copy
107 /// of 'lhs' into 'rhs'.
108 void mergeUsesAfterInlining(CallGraphNode *lhs, CallGraphNode *rhs);
109
110private:
111 /// Decrement the uses of discardable nodes referenced by the given user.
112 void decrementDiscardableUses(CGUser &uses);
113
114 /// A mapping between a discardable callgraph node (that is a symbol) and the
115 /// number of uses for this node.
116 DenseMap<CallGraphNode *, int> discardableSymNodeUses;
117
118 /// A mapping between a callgraph node and the symbol callgraph nodes that it
119 /// uses.
120 DenseMap<CallGraphNode *, CGUser> nodeUses;
121
122 /// A symbol table to use when resolving call lookups.
123 SymbolTableCollection &symbolTable;
124};
125} // namespace
126
127CGUseList::CGUseList(Operation *op, CallGraph &cg,
128 SymbolTableCollection &symbolTable)
129 : symbolTable(symbolTable) {
130 /// A set of callgraph nodes that are always known to be live during inlining.
131 DenseMap<Attribute, CallGraphNode *> alwaysLiveNodes;
132
133 // Walk each of the symbol tables looking for discardable callgraph nodes.
134 auto walkFn = [&](Operation *symbolTableOp, bool allUsesVisible) {
135 for (Operation &op : symbolTableOp->getRegion(index: 0).getOps()) {
136 // If this is a callgraph operation, check to see if it is discardable.
137 if (auto callable = dyn_cast<CallableOpInterface>(Val: &op)) {
138 if (auto *node = cg.lookupNode(region: callable.getCallableRegion())) {
139 SymbolOpInterface symbol = dyn_cast<SymbolOpInterface>(Val: &op);
140 if (symbol && (allUsesVisible || symbol.isPrivate()) &&
141 symbol.canDiscardOnUseEmpty()) {
142 discardableSymNodeUses.try_emplace(Key: node, Args: 0);
143 }
144 continue;
145 }
146 }
147 // Otherwise, check for any referenced nodes. These will be always-live.
148 walkReferencedSymbolNodes(op: &op, cg, symbolTable, resolvedRefs&: alwaysLiveNodes,
149 callback: [](CallGraphNode *, Operation *) {});
150 }
151 };
152 SymbolTable::walkSymbolTables(op, /*allSymUsesVisible=*/!op->getBlock(),
153 callback: walkFn);
154
155 // Drop the use information for any discardable nodes that are always live.
156 for (auto &it : alwaysLiveNodes)
157 discardableSymNodeUses.erase(Val: it.second);
158
159 // Compute the uses for each of the callable nodes in the graph.
160 for (CallGraphNode *node : cg)
161 recomputeUses(node, cg);
162}
163
164void CGUseList::dropCallUses(CallGraphNode *userNode, Operation *callOp,
165 CallGraph &cg) {
166 auto &userRefs = nodeUses[userNode].innerUses;
167 auto walkFn = [&](CallGraphNode *node, Operation *user) {
168 auto parentIt = userRefs.find(Val: node);
169 if (parentIt == userRefs.end())
170 return;
171 --parentIt->second;
172 --discardableSymNodeUses[node];
173 };
174 DenseMap<Attribute, CallGraphNode *> resolvedRefs;
175 walkReferencedSymbolNodes(op: callOp, cg, symbolTable, resolvedRefs, callback: walkFn);
176}
177
178void CGUseList::eraseNode(CallGraphNode *node) {
179 // Drop all child nodes.
180 for (auto &edge : *node)
181 if (edge.isChild())
182 eraseNode(node: edge.getTarget());
183
184 // Drop the uses held by this node and erase it.
185 auto useIt = nodeUses.find(Val: node);
186 assert(useIt != nodeUses.end() && "expected node to be valid");
187 decrementDiscardableUses(uses&: useIt->getSecond());
188 nodeUses.erase(I: useIt);
189 discardableSymNodeUses.erase(Val: node);
190}
191
192bool CGUseList::isDead(CallGraphNode *node) const {
193 // If the parent operation isn't a symbol, simply check normal SSA deadness.
194 Operation *nodeOp = node->getCallableRegion()->getParentOp();
195 if (!isa<SymbolOpInterface>(Val: nodeOp))
196 return isMemoryEffectFree(op: nodeOp) && nodeOp->use_empty();
197
198 // Otherwise, check the number of symbol uses.
199 auto symbolIt = discardableSymNodeUses.find(Val: node);
200 return symbolIt != discardableSymNodeUses.end() && symbolIt->second == 0;
201}
202
203bool CGUseList::hasOneUseAndDiscardable(CallGraphNode *node) const {
204 // If this isn't a symbol node, check for side-effects and SSA use count.
205 Operation *nodeOp = node->getCallableRegion()->getParentOp();
206 if (!isa<SymbolOpInterface>(Val: nodeOp))
207 return isMemoryEffectFree(op: nodeOp) && nodeOp->hasOneUse();
208
209 // Otherwise, check the number of symbol uses.
210 auto symbolIt = discardableSymNodeUses.find(Val: node);
211 return symbolIt != discardableSymNodeUses.end() && symbolIt->second == 1;
212}
213
214void CGUseList::recomputeUses(CallGraphNode *node, CallGraph &cg) {
215 Operation *parentOp = node->getCallableRegion()->getParentOp();
216 CGUser &uses = nodeUses[node];
217 decrementDiscardableUses(uses);
218
219 // Collect the new discardable uses within this node.
220 uses = CGUser();
221 DenseMap<Attribute, CallGraphNode *> resolvedRefs;
222 auto walkFn = [&](CallGraphNode *refNode, Operation *user) {
223 auto discardSymIt = discardableSymNodeUses.find(Val: refNode);
224 if (discardSymIt == discardableSymNodeUses.end())
225 return;
226
227 if (user != parentOp)
228 ++uses.innerUses[refNode];
229 else if (!uses.topLevelUses.insert(V: refNode).second)
230 return;
231 ++discardSymIt->second;
232 };
233 walkReferencedSymbolNodes(op: parentOp, cg, symbolTable, resolvedRefs, callback: walkFn);
234}
235
236void CGUseList::mergeUsesAfterInlining(CallGraphNode *lhs, CallGraphNode *rhs) {
237 auto &lhsUses = nodeUses[lhs], &rhsUses = nodeUses[rhs];
238 for (auto &useIt : lhsUses.innerUses) {
239 rhsUses.innerUses[useIt.first] += useIt.second;
240 discardableSymNodeUses[useIt.first] += useIt.second;
241 }
242}
243
244void CGUseList::decrementDiscardableUses(CGUser &uses) {
245 for (CallGraphNode *node : uses.topLevelUses)
246 --discardableSymNodeUses[node];
247 for (auto &it : uses.innerUses)
248 discardableSymNodeUses[it.first] -= it.second;
249}
250
251//===----------------------------------------------------------------------===//
252// CallGraph traversal
253//===----------------------------------------------------------------------===//
254
255namespace {
256/// This class represents a specific callgraph SCC.
257class CallGraphSCC {
258public:
259 CallGraphSCC(llvm::scc_iterator<const CallGraph *> &parentIterator)
260 : parentIterator(parentIterator) {}
261 /// Return a range over the nodes within this SCC.
262 std::vector<CallGraphNode *>::iterator begin() { return nodes.begin(); }
263 std::vector<CallGraphNode *>::iterator end() { return nodes.end(); }
264
265 /// Reset the nodes of this SCC with those provided.
266 void reset(const std::vector<CallGraphNode *> &newNodes) { nodes = newNodes; }
267
268 /// Remove the given node from this SCC.
269 void remove(CallGraphNode *node) {
270 auto it = llvm::find(Range&: nodes, Val: node);
271 if (it != nodes.end()) {
272 nodes.erase(position: it);
273 parentIterator.ReplaceNode(Old: node, New: nullptr);
274 }
275 }
276
277private:
278 std::vector<CallGraphNode *> nodes;
279 llvm::scc_iterator<const CallGraph *> &parentIterator;
280};
281} // namespace
282
283/// Run a given transformation over the SCCs of the callgraph in a bottom up
284/// traversal.
285static LogicalResult runTransformOnCGSCCs(
286 const CallGraph &cg,
287 function_ref<LogicalResult(CallGraphSCC &)> sccTransformer) {
288 llvm::scc_iterator<const CallGraph *> cgi = llvm::scc_begin(G: &cg);
289 CallGraphSCC currentSCC(cgi);
290 while (!cgi.isAtEnd()) {
291 // Copy the current SCC and increment so that the transformer can modify the
292 // SCC without invalidating our iterator.
293 currentSCC.reset(newNodes: *cgi);
294 ++cgi;
295 if (failed(Result: sccTransformer(currentSCC)))
296 return failure();
297 }
298 return success();
299}
300
301/// Collect all of the callable operations within the given range of blocks. If
302/// `traverseNestedCGNodes` is true, this will also collect call operations
303/// inside of nested callgraph nodes.
304static void collectCallOps(iterator_range<Region::iterator> blocks,
305 CallGraphNode *sourceNode, CallGraph &cg,
306 SymbolTableCollection &symbolTable,
307 SmallVectorImpl<ResolvedCall> &calls,
308 bool traverseNestedCGNodes) {
309 SmallVector<std::pair<Block *, CallGraphNode *>, 8> worklist;
310 auto addToWorklist = [&](CallGraphNode *node,
311 iterator_range<Region::iterator> blocks) {
312 for (Block &block : blocks)
313 worklist.emplace_back(Args: &block, Args&: node);
314 };
315
316 addToWorklist(sourceNode, blocks);
317 while (!worklist.empty()) {
318 Block *block;
319 std::tie(args&: block, args&: sourceNode) = worklist.pop_back_val();
320
321 for (Operation &op : *block) {
322 if (auto call = dyn_cast<CallOpInterface>(Val&: op)) {
323 // TODO: Support inlining nested call references.
324 CallInterfaceCallable callable = call.getCallableForCallee();
325 if (SymbolRefAttr symRef = dyn_cast<SymbolRefAttr>(Val&: callable)) {
326 if (!isa<FlatSymbolRefAttr>(Val: symRef))
327 continue;
328 }
329
330 CallGraphNode *targetNode = cg.resolveCallable(call, symbolTable);
331 if (!targetNode->isExternal())
332 calls.emplace_back(Args&: call, Args&: sourceNode, Args&: targetNode);
333 continue;
334 }
335
336 // If this is not a call, traverse the nested regions. If
337 // `traverseNestedCGNodes` is false, then don't traverse nested call graph
338 // regions.
339 for (auto &nestedRegion : op.getRegions()) {
340 CallGraphNode *nestedNode = cg.lookupNode(region: &nestedRegion);
341 if (traverseNestedCGNodes || !nestedNode)
342 addToWorklist(nestedNode ? nestedNode : sourceNode, nestedRegion);
343 }
344 }
345 }
346}
347
348//===----------------------------------------------------------------------===//
349// InlinerInterfaceImpl
350//===----------------------------------------------------------------------===//
351
352static std::string getNodeName(CallOpInterface op) {
353 if (llvm::dyn_cast_if_present<SymbolRefAttr>(Val: op.getCallableForCallee()))
354 return debugString(op);
355 return "_unnamed_callee_";
356}
357
358/// Return true if the specified `inlineHistoryID` indicates an inline history
359/// that already includes `node`.
360static bool inlineHistoryIncludes(
361 CallGraphNode *node, std::optional<size_t> inlineHistoryID,
362 MutableArrayRef<std::pair<CallGraphNode *, std::optional<size_t>>>
363 inlineHistory) {
364 while (inlineHistoryID.has_value()) {
365 assert(*inlineHistoryID < inlineHistory.size() &&
366 "Invalid inline history ID");
367 if (inlineHistory[*inlineHistoryID].first == node)
368 return true;
369 inlineHistoryID = inlineHistory[*inlineHistoryID].second;
370 }
371 return false;
372}
373
374namespace {
375/// This class provides a specialization of the main inlining interface.
376struct InlinerInterfaceImpl : public InlinerInterface {
377 InlinerInterfaceImpl(MLIRContext *context, CallGraph &cg,
378 SymbolTableCollection &symbolTable)
379 : InlinerInterface(context), cg(cg), symbolTable(symbolTable) {}
380
381 /// Process a set of blocks that have been inlined. This callback is invoked
382 /// *before* inlined terminator operations have been processed.
383 void
384 processInlinedBlocks(iterator_range<Region::iterator> inlinedBlocks) final {
385 // Find the closest callgraph node from the first block.
386 CallGraphNode *node;
387 Region *region = inlinedBlocks.begin()->getParent();
388 while (!(node = cg.lookupNode(region))) {
389 region = region->getParentRegion();
390 assert(region && "expected valid parent node");
391 }
392
393 collectCallOps(blocks: inlinedBlocks, sourceNode: node, cg, symbolTable, calls,
394 /*traverseNestedCGNodes=*/true);
395 }
396
397 /// Mark the given callgraph node for deletion.
398 void markForDeletion(CallGraphNode *node) { deadNodes.insert(Ptr: node); }
399
400 /// This method properly disposes of callables that became dead during
401 /// inlining. This should not be called while iterating over the SCCs.
402 void eraseDeadCallables() {
403 for (CallGraphNode *node : deadNodes)
404 node->getCallableRegion()->getParentOp()->erase();
405 }
406
407 /// The set of callables known to be dead.
408 SmallPtrSet<CallGraphNode *, 8> deadNodes;
409
410 /// The current set of call instructions to consider for inlining.
411 SmallVector<ResolvedCall, 8> calls;
412
413 /// The callgraph being operated on.
414 CallGraph &cg;
415
416 /// A symbol table to use when resolving call lookups.
417 SymbolTableCollection &symbolTable;
418};
419} // namespace
420
421namespace mlir {
422
423using CallGraphEdge = std::pair<CallGraphNode *, CallGraphNode *>;
424using BlockedEdges = DenseSet<CallGraphEdge>;
425
426class Inliner::Impl {
427public:
428 Impl(Inliner &inliner) : inliner(inliner) {}
429
430 /// Attempt to inline calls within the given scc, and run simplifications,
431 /// until a fixed point is reached. This allows for the inlining of newly
432 /// devirtualized calls. Returns failure if there was a fatal error during
433 /// inlining.
434 LogicalResult inlineSCC(InlinerInterfaceImpl &inlinerIface,
435 CGUseList &useList, CallGraphSCC &currentSCC,
436 MLIRContext *context);
437
438private:
439 /// Optimize the nodes within the given SCC with one of the held optimization
440 /// pass pipelines. `inlinedIntoSCC` indicates whether a previous iteration
441 /// already inlined into this SCC; the caller only repeats after a
442 /// successful inline, so a first round always passes false. Returns failure
443 /// if an error occurred during the optimization of the SCC, success
444 /// otherwise.
445 LogicalResult optimizeSCC(CallGraph &cg, CGUseList &useList,
446 CallGraphSCC &currentSCC, MLIRContext *context,
447 bool inlinedIntoSCC);
448
449 /// Optimize the nodes within the given SCC in parallel. Returns failure if an
450 /// error occurred during the optimization of the SCC, success otherwise.
451 LogicalResult optimizeSCCAsync(MutableArrayRef<CallGraphNode *> nodesToVisit,
452 MLIRContext *context);
453
454 /// Optimize the given callable node with one of the pass managers provided
455 /// with `pipelines`, or the generic pre-inline pipeline. Returns failure if
456 /// an error occurred during the optimization of the callable, success
457 /// otherwise.
458 LogicalResult optimizeCallable(CallGraphNode *node,
459 llvm::StringMap<OpPassManager> &pipelines);
460
461 /// Attempt to inline calls within the given scc. This function returns
462 /// success if any calls were inlined, failure otherwise.
463 LogicalResult inlineCallsInSCC(InlinerInterfaceImpl &inlinerIface,
464 CGUseList &useList, CallGraphSCC &currentSCC,
465 BlockedEdges &blockedEdges);
466
467 /// Returns true if the given call should be inlined.
468 bool shouldInline(ResolvedCall &resolvedCall);
469
470private:
471 Inliner &inliner;
472 llvm::SmallVector<llvm::StringMap<OpPassManager>> pipelines;
473};
474
475LogicalResult Inliner::Impl::inlineSCC(InlinerInterfaceImpl &inlinerIface,
476 CGUseList &useList,
477 CallGraphSCC &currentSCC,
478 MLIRContext *context) {
479 // Continuously simplify and inline until we either reach a fixed point, or
480 // hit the maximum iteration count. Simplifying early helps to refine the cost
481 // model, and in future iterations may devirtualize new calls.
482 unsigned iterationCount = 0;
483 // Optimization may replace calls, preventing exact provenance tracking.
484 // Conservatively retain proven recursive graph edges across iterations.
485 BlockedEdges blockedEdges;
486 do {
487 if (failed(Result: optimizeSCC(cg&: inlinerIface.cg, useList, currentSCC, context,
488 /*inlinedIntoSCC=*/iterationCount != 0)))
489 return failure();
490 if (failed(
491 Result: inlineCallsInSCC(inlinerIface, useList, currentSCC, blockedEdges)))
492 break;
493 } while (++iterationCount < inliner.config.getMaxInliningIterations());
494 return success();
495}
496
497LogicalResult Inliner::Impl::optimizeSCC(CallGraph &cg, CGUseList &useList,
498 CallGraphSCC &currentSCC,
499 MLIRContext *context,
500 bool inlinedIntoSCC) {
501 // With no pipeline configured and no successful inlining in this SCC yet,
502 // every node simplified below is unchanged since the use list was built:
503 // inlining only modifies callers in the SCC being processed, and nodes
504 // with nested children are excluded from simplification. Skip the no-op
505 // round.
506 if (!inlinedIntoSCC && inliner.config.getOpPipelines().empty() &&
507 !inliner.config.getDefaultPipeline())
508 return success();
509
510 // Collect the sets of nodes to simplify.
511 SmallVector<CallGraphNode *, 4> nodesToVisit;
512 for (auto *node : currentSCC) {
513 if (node->isExternal())
514 continue;
515
516 // Don't simplify nodes with children. Nodes with children require special
517 // handling as we may remove the node during simplification. In the future,
518 // we should be able to handle this case with proper node deletion tracking.
519 if (node->hasChildren())
520 continue;
521
522 // We also won't apply simplifications to nodes that can't have passes
523 // scheduled on them.
524 auto *region = node->getCallableRegion();
525 if (!region->getParentOp()->hasTrait<OpTrait::IsIsolatedFromAbove>())
526 continue;
527 nodesToVisit.push_back(Elt: node);
528 }
529 if (nodesToVisit.empty())
530 return success();
531
532 // Optimize each of the nodes within the SCC in parallel.
533 if (failed(Result: optimizeSCCAsync(nodesToVisit, context)))
534 return failure();
535
536 // Recompute the uses held by each of the nodes.
537 for (CallGraphNode *node : nodesToVisit)
538 useList.recomputeUses(node, cg);
539 return success();
540}
541
542LogicalResult
543Inliner::Impl::optimizeSCCAsync(MutableArrayRef<CallGraphNode *> nodesToVisit,
544 MLIRContext *ctx) {
545 // We must maintain a fixed pool of pass managers which is at least as large
546 // as the maximum parallelism of the failableParallelForEach below.
547 // Note: The number of pass managers here needs to remain constant
548 // to prevent issues with pass instrumentations that rely on having the same
549 // pass manager for the main thread.
550 size_t numThreads = ctx->getNumThreads();
551 const auto &opPipelines = inliner.config.getOpPipelines();
552 if (pipelines.size() < numThreads) {
553 pipelines.reserve(N: numThreads);
554 pipelines.resize(N: numThreads, NV: opPipelines);
555 }
556
557 // Ensure an analysis manager has been constructed for each of the nodes.
558 // This prevents thread races when running the nested pipelines.
559 for (CallGraphNode *node : nodesToVisit)
560 inliner.am.nest(op: node->getCallableRegion()->getParentOp());
561
562 // An atomic failure variable for the async executors.
563 std::vector<std::atomic<bool>> activePMs(pipelines.size());
564 llvm::fill(Range&: activePMs, Value: false);
565 return failableParallelForEach(context: ctx, range&: nodesToVisit, func: [&](CallGraphNode *node) {
566 // Find a pass manager for this operation.
567 auto it = llvm::find_if(Range&: activePMs, P: [](std::atomic<bool> &isActive) {
568 bool expectedInactive = false;
569 return isActive.compare_exchange_strong(i1&: expectedInactive, i2: true);
570 });
571 assert(it != activePMs.end() &&
572 "could not find inactive pass manager for thread");
573 unsigned pmIndex = it - activePMs.begin();
574
575 // Optimize this callable node.
576 LogicalResult result = optimizeCallable(node, pipelines&: pipelines[pmIndex]);
577
578 // Reset the active bit for this pass manager.
579 activePMs[pmIndex].store(i: false);
580 return result;
581 });
582}
583
584LogicalResult
585Inliner::Impl::optimizeCallable(CallGraphNode *node,
586 llvm::StringMap<OpPassManager> &pipelines) {
587 Operation *callable = node->getCallableRegion()->getParentOp();
588 StringRef opName = callable->getName().getStringRef();
589 auto pipelineIt = pipelines.find(Key: opName);
590 const auto &defaultPipeline = inliner.config.getDefaultPipeline();
591 if (pipelineIt == pipelines.end()) {
592 // If a pipeline didn't exist, use the generic pipeline if possible.
593 if (!defaultPipeline)
594 return success();
595
596 OpPassManager defaultPM(opName);
597 defaultPipeline(defaultPM);
598 pipelineIt = pipelines.try_emplace(Key: opName, Args: std::move(defaultPM)).first;
599 }
600 return inliner.runPipelineHelper(inliner.pass, pipelineIt->second, callable);
601}
602
603/// Attempt to inline calls within the given scc. This function returns
604/// success if any calls were inlined, failure otherwise.
605LogicalResult
606Inliner::Impl::inlineCallsInSCC(InlinerInterfaceImpl &inlinerIface,
607 CGUseList &useList, CallGraphSCC &currentSCC,
608 BlockedEdges &blockedEdges) {
609 CallGraph &cg = inlinerIface.cg;
610 auto &calls = inlinerIface.calls;
611
612 // A set of dead nodes to remove after inlining.
613 llvm::SmallSetVector<CallGraphNode *, 1> deadNodes;
614
615 // Collect all of the direct calls within the nodes of the current SCC. We
616 // don't traverse nested callgraph nodes, because they are handled separately
617 // likely within a different SCC.
618 for (CallGraphNode *node : currentSCC) {
619 if (node->isExternal())
620 continue;
621
622 // Don't collect calls if the node is already dead.
623 if (useList.isDead(node)) {
624 deadNodes.insert(X: node);
625 } else {
626 collectCallOps(blocks: *node->getCallableRegion(), sourceNode: node, cg,
627 symbolTable&: inlinerIface.symbolTable, calls,
628 /*traverseNestedCGNodes=*/false);
629 }
630 }
631
632 // When inlining a callee produces new call sites, remember that they came
633 // from the callee to avoid recursively inlining through a cycle.
634 using InlineHistoryT = std::optional<size_t>;
635 SmallVector<std::pair<CallGraphNode *, InlineHistoryT>, 8> inlineHistory;
636 std::vector<InlineHistoryT> callHistory(calls.size(), InlineHistoryT{});
637 BlockedEdges newlyBlockedEdges;
638
639 LLVM_DEBUG({
640 LDBG() << "* Inliner: Initial calls in SCC are: {";
641 for (unsigned I = 0, E = calls.size(); I < E; ++I)
642 LDBG() << " " << I << ". " << calls[I].call << ",";
643 LDBG() << "}";
644 });
645
646 // Try to inline each of the call operations. Don't cache the end iterator
647 // here as more calls may be added during inlining.
648 bool inlinedAnyCalls = false;
649 for (unsigned i = 0; i < calls.size(); ++i) {
650 if (deadNodes.contains(key: calls[i].sourceNode))
651 continue;
652 ResolvedCall it = calls[i];
653
654 InlineHistoryT inlineHistoryID = callHistory[i];
655 bool inHistory =
656 inlineHistoryIncludes(node: it.targetNode, inlineHistoryID, inlineHistory);
657 auto edge = std::make_pair(x&: it.sourceNode, y&: it.targetNode);
658 if (inHistory)
659 newlyBlockedEdges.insert(V: edge);
660 bool doInline =
661 !inHistory && !blockedEdges.contains(V: edge) && shouldInline(resolvedCall&: it);
662 CallOpInterface call = it.call;
663 LLVM_DEBUG({
664 if (doInline)
665 LDBG() << "* Inlining call: " << i << ". " << call;
666 else
667 LDBG() << "* Not inlining call: " << i << ". " << call;
668 });
669 if (!doInline)
670 continue;
671
672 unsigned prevSize = calls.size();
673 Region *targetRegion = it.targetNode->getCallableRegion();
674
675 // If this is the last call to the target node and the node is discardable,
676 // then inline it in-place and delete the node if successful.
677 bool inlineInPlace = useList.hasOneUseAndDiscardable(node: it.targetNode);
678
679 LogicalResult inlineResult =
680 inlineCall(interface&: inlinerIface, cloneCallback: inliner.config.getCloneCallback(), call,
681 callable: cast<CallableOpInterface>(Val: targetRegion->getParentOp()),
682 src: targetRegion, /*shouldCloneInlinedRegion=*/!inlineInPlace);
683 if (failed(Result: inlineResult)) {
684 LDBG() << "** Failed to inline";
685 continue;
686 }
687 inlinedAnyCalls = true;
688
689 // Record that the new callsites came from inlining the callee.
690 InlineHistoryT newInlineHistoryID{inlineHistory.size()};
691 inlineHistory.push_back(Elt: std::make_pair(x&: it.targetNode, y&: inlineHistoryID));
692
693 auto historyToString = [](InlineHistoryT h) {
694 return h.has_value() ? std::to_string(val: *h) : "root";
695 };
696 LDBG() << "* new inlineHistory entry: " << newInlineHistoryID << ". ["
697 << getNodeName(op: call) << ", " << historyToString(inlineHistoryID)
698 << "]";
699
700 for (unsigned k = prevSize; k != calls.size(); ++k) {
701 callHistory.push_back(x: newInlineHistoryID);
702 LDBG() << "* new call " << k << " {" << calls[k].call
703 << "}\n with historyID = " << newInlineHistoryID
704 << ", added due to inlining of\n call {" << call
705 << "}\n with historyID = " << historyToString(inlineHistoryID);
706 }
707
708 // If the inlining was successful, Merge the new uses into the source node.
709 useList.dropCallUses(userNode: it.sourceNode, callOp: call.getOperation(), cg);
710 useList.mergeUsesAfterInlining(lhs: it.targetNode, rhs: it.sourceNode);
711
712 // then erase the call.
713 call.erase();
714
715 // If we inlined in place, mark the node for deletion.
716 if (inlineInPlace) {
717 useList.eraseNode(node: it.targetNode);
718 deadNodes.insert(X: it.targetNode);
719 }
720 }
721
722 for (CallGraphNode *node : deadNodes) {
723 currentSCC.remove(node);
724 inlinerIface.markForDeletion(node);
725 }
726 // Delay blocking until the next iteration so independent calls on the same
727 // edge in the current worklist retain their inlining opportunities.
728 blockedEdges.insert(I: newlyBlockedEdges.begin(), E: newlyBlockedEdges.end());
729 calls.clear();
730 return success(IsSuccess: inlinedAnyCalls);
731}
732
733/// Returns true if the given call should be inlined.
734bool Inliner::Impl::shouldInline(ResolvedCall &resolvedCall) {
735 // Don't allow inlining terminator calls. We currently don't support this
736 // case.
737 if (resolvedCall.call->hasTrait<OpTrait::IsTerminator>())
738 return false;
739
740 // Don't allow inlining if the target is a self-recursive function.
741 // Don't allow inlining if the call graph is like A->B->A.
742 if (llvm::count_if(Range&: *resolvedCall.targetNode,
743 P: [&](CallGraphNode::Edge const &edge) -> bool {
744 return edge.getTarget() == resolvedCall.targetNode ||
745 edge.getTarget() == resolvedCall.sourceNode;
746 }) > 0)
747 return false;
748
749 // Don't allow inlining if the target is an ancestor of the call. This
750 // prevents inlining recursively.
751 Region *callableRegion = resolvedCall.targetNode->getCallableRegion();
752 if (callableRegion->isAncestor(other: resolvedCall.call->getParentRegion()))
753 return false;
754
755 // Don't allow inlining if the callee has multiple blocks (unstructured
756 // control flow) but we cannot be sure that the caller region supports that.
757 if (!inliner.config.getCanHandleMultipleBlocks()) {
758 bool calleeHasMultipleBlocks =
759 llvm::hasNItemsOrMore(C&: *callableRegion, /*N=*/2);
760 // If both parent ops have the same type, it is safe to inline. Otherwise,
761 // decide based on whether the op has the SingleBlock trait or not.
762 // Note: This check does currently not account for
763 // SizedRegion/MaxSizedRegion.
764 auto callerRegionSupportsMultipleBlocks = [&]() {
765 return callableRegion->getParentOp()->getName() ==
766 resolvedCall.call->getParentOp()->getName() ||
767 !resolvedCall.call->getParentOp()
768 ->mightHaveTrait<OpTrait::SingleBlock>();
769 };
770 if (calleeHasMultipleBlocks && !callerRegionSupportsMultipleBlocks())
771 return false;
772 }
773
774 if (!inliner.isProfitableToInline(resolvedCall))
775 return false;
776
777 // Otherwise, inline.
778 return true;
779}
780
781LogicalResult Inliner::doInlining() {
782 Impl impl(*this);
783 auto *context = op->getContext();
784 // Run the inline transform in post-order over the SCCs in the callgraph.
785 SymbolTableCollection symbolTable;
786 // FIXME: some clean-up can be done for the arguments
787 // of the Impl's methods, if the inlinerIface and useList
788 // become the states of the Impl.
789 InlinerInterfaceImpl inlinerIface(context, cg, symbolTable);
790 CGUseList useList(op, cg, symbolTable);
791 LogicalResult result = runTransformOnCGSCCs(cg, sccTransformer: [&](CallGraphSCC &scc) {
792 return impl.inlineSCC(inlinerIface, useList, currentSCC&: scc, context);
793 });
794 if (failed(Result: result))
795 return result;
796
797 // After inlining, make sure to erase any callables proven to be dead.
798 inlinerIface.eraseDeadCallables();
799 return success();
800}
801} // namespace mlir
802