1//===- InlinerPass.cpp - Pass to inline function calls --------------------===//
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 a basic inlining algorithm that operates bottom up over
10// the Strongly Connect Components(SCCs) of the CallGraph. This enables a more
11// incremental propagation of inlining decisions from the leafs to the roots of
12// the callgraph.
13//
14//===----------------------------------------------------------------------===//
15
16#include "mlir/Transforms/Passes.h"
17
18#include "mlir/Analysis/CallGraph.h"
19#include "mlir/Pass/PassManager.h"
20#include "mlir/Transforms/Inliner.h"
21#include "llvm/Support/DebugLog.h"
22
23namespace mlir {
24#define GEN_PASS_DEF_INLINERPASS
25#include "mlir/Transforms/Passes.h.inc"
26} // namespace mlir
27
28#define DEBUG_TYPE "inliner-pass"
29
30using namespace mlir;
31
32/// This function implements the inliner optimization pipeline.
33static void defaultInlinerOptPipeline(OpPassManager &pm) {
34 pm.addPass(pass: createCanonicalizerPass());
35}
36
37//===----------------------------------------------------------------------===//
38// InlinerPass
39//===----------------------------------------------------------------------===//
40
41namespace {
42class InlinerPass : public impl::InlinerPassBase<InlinerPass> {
43public:
44 using impl::InlinerPassBase<InlinerPass>::InlinerPassBase;
45 InlinerPass();
46 InlinerPass(const InlinerPass &) = default;
47 InlinerPass(std::function<void(OpPassManager &)> defaultPipeline);
48 InlinerPass(std::function<void(OpPassManager &)> defaultPipeline,
49 llvm::StringMap<OpPassManager> opPipelines);
50 void runOnOperation() override;
51
52 /// A callback provided to the inliner driver to execute
53 /// the specified pass pipeline on the given operation
54 /// within the context of the current inliner pass,
55 /// which is passed as the first argument.
56 /// runPipeline API is protected within the Pass class,
57 /// so this helper is required to call it from the foreign
58 /// inliner driver.
59 static LogicalResult runPipelineHelper(Pass &pass, OpPassManager &pipeline,
60 Operation *op) {
61 return mlir::cast<InlinerPass>(Val&: pass).runPipeline(pipeline, op);
62 }
63
64private:
65 /// Attempt to initialize the options of this pass from the given string.
66 /// Derived classes may override this method to hook into the point at which
67 /// options are initialized, but should generally always invoke this base
68 /// class variant.
69 LogicalResult initializeOptions(
70 StringRef options,
71 function_ref<LogicalResult(const Twine &)> errorHandler) override;
72
73 /// Inliner configuration parameters created from the pass options.
74 InlinerConfig config;
75};
76} // namespace
77
78InlinerPass::InlinerPass() : InlinerPass(defaultInlinerOptPipeline) {}
79
80InlinerPass::InlinerPass(
81 std::function<void(OpPassManager &)> defaultPipelineArg)
82 : InlinerPass(std::move(defaultPipelineArg),
83 llvm::StringMap<OpPassManager>{}) {}
84
85InlinerPass::InlinerPass(std::function<void(OpPassManager &)> defaultPipeline,
86 llvm::StringMap<OpPassManager> opPipelines)
87 : config(std::move(defaultPipeline), maxInliningIterations) {
88 if (opPipelines.empty())
89 return;
90
91 // Update the option for the op specific optimization pipelines.
92 for (auto &it : opPipelines)
93 opPipelineList.addValue(V: it.second);
94 config.setOpPipelines(std::move(opPipelines));
95}
96
97// Return true if the inlining ratio does not exceed the threshold.
98static bool isProfitableToInline(const Inliner::ResolvedCall &resolvedCall,
99 unsigned inliningThreshold) {
100 // Return early, ratio <= 0U will always be false.
101 if (inliningThreshold == 0U)
102 return false;
103 // Return early, ratio <= -1U will always be true.
104 if (inliningThreshold == -1U)
105 return true;
106
107 Region *callerRegion = resolvedCall.sourceNode->getCallableRegion();
108 Region *calleeRegion = resolvedCall.targetNode->getCallableRegion();
109
110 assert(calleeRegion && callerRegion && "unexpected external node");
111
112 auto countOps = [](Region *region) {
113 unsigned count = 0;
114 region->walk(callback: [&](Operation *) { ++count; });
115 return count;
116 };
117
118 unsigned callerOps = countOps(callerRegion);
119
120 // Always inline empty callees (if it is possible at all).
121 if (callerOps == 0)
122 return true;
123
124 unsigned ratio = countOps(calleeRegion) * 100 / callerOps;
125 LDBG() << "Callee / caller operation ratio (max: " << inliningThreshold
126 << "%): " << ratio << "%";
127 return ratio <= inliningThreshold;
128}
129
130void InlinerPass::runOnOperation() {
131 CallGraph &cg = getAnalysis<CallGraph>();
132
133 // The inliner should only be run on operations that define a symbol table,
134 // as the callgraph will need to resolve references.
135 Operation *op = getOperation();
136 if (!op->hasTrait<OpTrait::SymbolTable>()) {
137 op->emitOpError() << " was scheduled to run under the inliner, but does "
138 "not define a symbol table";
139 return signalPassFailure();
140 }
141
142 // By default, assume that any inlining is profitable.
143 auto profitabilityCb = [this](const Inliner::ResolvedCall &call) {
144 return isProfitableToInline(resolvedCall: call, inliningThreshold);
145 };
146
147 // Get an instance of the inliner.
148 Inliner inliner(op, cg, *this, getAnalysisManager(), runPipelineHelper,
149 config, profitabilityCb);
150
151 // Run the inlining.
152 if (failed(Result: inliner.doInlining()))
153 signalPassFailure();
154}
155
156LogicalResult InlinerPass::initializeOptions(
157 StringRef options,
158 function_ref<LogicalResult(const Twine &)> errorHandler) {
159 if (failed(Result: Pass::initializeOptions(options, errorHandler)))
160 return failure();
161
162 // Initialize the pipeline builder for operations without the dedicated
163 // optimization pipeline in opPipelineList to use the option string.
164 // TODO: Use a generic pass manager for the pre-inline pipeline, and remove
165 // this.
166 if (!defaultPipelineStr.empty()) {
167 std::string defaultPipelineCopy = defaultPipelineStr;
168 config.setDefaultPipeline([=](OpPassManager &pm) {
169 (void)parsePassPipeline(pipeline: defaultPipelineCopy, pm);
170 });
171 } else if (defaultPipelineStr.getNumOccurrences()) {
172 config.setDefaultPipeline(nullptr);
173 }
174
175 // Initialize the op specific pass pipelines.
176 llvm::StringMap<OpPassManager> pipelines;
177 for (OpPassManager pipeline : opPipelineList)
178 if (!pipeline.empty())
179 pipelines.try_emplace(Key: pipeline.getOpAnchorName(), Args&: pipeline);
180 config.setOpPipelines(std::move(pipelines));
181
182 config.setMaxInliningIterations(maxInliningIterations);
183
184 return success();
185}
186
187std::unique_ptr<Pass>
188mlir::createInlinerPass(llvm::StringMap<OpPassManager> opPipelines) {
189 return std::make_unique<InlinerPass>(args&: defaultInlinerOptPipeline,
190 args: std::move(opPipelines));
191}
192std::unique_ptr<Pass> mlir::createInlinerPass(
193 llvm::StringMap<OpPassManager> opPipelines,
194 std::function<void(OpPassManager &)> defaultPipelineBuilder) {
195 return std::make_unique<InlinerPass>(args: std::move(defaultPipelineBuilder),
196 args: std::move(opPipelines));
197}
198