summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/passes/CMakeLists.txt1
-rw-r--r--src/passes/Inlining.cpp207
-rw-r--r--src/passes/pass.cpp1
-rw-r--r--src/passes/passes.h1
-rw-r--r--src/wasm-builder.h4
5 files changed, 214 insertions, 0 deletions
diff --git a/src/passes/CMakeLists.txt b/src/passes/CMakeLists.txt
index d15365a57..b8a0a3986 100644
--- a/src/passes/CMakeLists.txt
+++ b/src/passes/CMakeLists.txt
@@ -5,6 +5,7 @@ SET(passes_SOURCES
DeadCodeElimination.cpp
DuplicateFunctionElimination.cpp
ExtractFunction.cpp
+ Inlining.cpp
LegalizeJSInterface.cpp
MergeBlocks.cpp
Metrics.cpp
diff --git a/src/passes/Inlining.cpp b/src/passes/Inlining.cpp
new file mode 100644
index 000000000..9496b532c
--- /dev/null
+++ b/src/passes/Inlining.cpp
@@ -0,0 +1,207 @@
+/*
+ * Copyright 2016 WebAssembly Community Group participants
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+//
+// Inlining.
+//
+// For now, this does a conservative inlining of all functions that have
+// exactly one use. That should not increase code size, and may have
+// speed benefits.
+//
+
+#include <wasm.h>
+#include <pass.h>
+#include <wasm-builder.h>
+#include <parsing.h>
+
+namespace wasm {
+
+struct FunctionUseCounter : public WalkerPass<PostWalker<FunctionUseCounter, Visitor<FunctionUseCounter>>> {
+ bool isFunctionParallel() override { return true; }
+
+ FunctionUseCounter(std::map<Name, Index>* output) : output(output) {}
+
+ FunctionUseCounter* create() override {
+ return new FunctionUseCounter(output);
+ }
+
+ void visitCall(Call *curr) {
+ (*output)[curr->target]++;
+ }
+
+private:
+ std::map<Name, Index>* output;
+};
+
+struct Action {
+ Call* call;
+ Block* block; // the replacement for the call, into which we should inline
+ Function* contents;
+
+ Action(Call* call, Block* block, Function* contents) : call(call), block(block), contents(contents) {}
+};
+
+struct InliningState {
+ std::set<Name> canInline;
+ std::map<Name, std::vector<Action>> actionsForFunction; // function name => actions that can be performed in it
+};
+
+struct Planner : public WalkerPass<PostWalker<Planner, Visitor<Planner>>> {
+ bool isFunctionParallel() override { return true; }
+
+ Planner(InliningState* state) : state(state) {}
+
+ Planner* create() override {
+ return new Planner(state);
+ }
+
+ void visitCall(Call *curr) {
+ if (state->canInline.count(curr->target)) {
+ auto* block = Builder(*getModule()).makeBlock();
+ block->type = curr->type;
+ replaceCurrent(block);
+ state->actionsForFunction[getFunction()->name].emplace_back(curr, block, getModule()->getFunction(curr->target));
+ }
+ }
+
+ void doWalkFunction(Function* func) {
+ // we shouldn't inline into us if we are to be inlined
+ // ourselves - that has the risk of cycles
+ if (state->canInline.count(func->name) == 0) {
+ walk(func->body);
+ }
+ }
+
+private:
+ InliningState* state;
+};
+
+// Core inlining logic. Modifies the outside function (adding locals as
+// needed), and returns the inlined code.
+// Since we only inline once, and do not need the function afterwards, we
+// can just reuse all the nodes and even avoid copying.
+static Expression* doInlining(Module* module, Function* into, Action& action) {
+ Builder builder(*module);
+ auto* block = action.block;
+ block->name = Name(std::string("__inlined_func$") + action.contents->name.str);
+ block->type = action.contents->result;
+ // set up a locals mapping
+ struct Updater : public PostWalker<Updater, Visitor<Updater>> {
+ std::map<Index, Index> localMapping;
+ Name returnName;
+ Builder* builder;
+
+ void visitReturn(Return* curr) {
+ replaceCurrent(builder->makeBreak(returnName, curr->value));
+ }
+ void visitGetLocal(GetLocal* curr) {
+ curr->index = localMapping[curr->index];
+ }
+ void visitSetLocal(SetLocal* curr) {
+ curr->index = localMapping[curr->index];
+ }
+ } updater;
+ updater.returnName = block->name;
+ updater.builder = &builder;
+ for (Index i = 0; i < action.contents->getNumLocals(); i++) {
+ updater.localMapping[i] = builder.addVar(into, action.contents->getLocalType(i));
+ }
+ // assign the operands into the params
+ for (Index i = 0; i < action.contents->params.size(); i++) {
+ block->list.push_back(builder.makeSetLocal(updater.localMapping[i], action.call->operands[i]));
+ }
+ // update the inlined contents
+ updater.walk(action.contents->body);
+ block->list.push_back(action.contents->body);
+ action.contents->body = builder.makeUnreachable(); // not strictly needed, since it's going away
+ return block;
+}
+
+struct Inlining : public Pass {
+ void run(PassRunner* runner, Module* module) override {
+ // keep going while we inline, to handle nesting. TODO: optimize
+ while (iteration(runner, module)) {}
+ }
+
+ bool iteration(PassRunner* runner, Module* module) {
+ // Count uses
+ std::map<Name, Index> uses;
+ // fill in uses, as we operate on it in parallel (each function to its own entry)
+ for (auto& func : module->functions) {
+ uses[func->name] = 0;
+ }
+ {
+ PassRunner runner(module);
+ runner.add<FunctionUseCounter>(&uses);
+ runner.run();
+ }
+ for (auto& ex : module->exports) {
+ if (ex->kind == ExternalKind::Function) {
+ uses[ex->value] = 2; // too many, so we ignore it
+ }
+ }
+ for (auto& segment : module->table.segments) {
+ for (auto name : segment.data) {
+ uses[name]++;
+ }
+ }
+ // decide which to inline
+ InliningState state;
+ for (auto iter : uses) {
+ if (iter.second == 1) {
+ state.canInline.insert(iter.first);
+ }
+ }
+ // fill in actionsForFunction, as we operate on it in parallel (each function to its own entry)
+ for (auto& func : module->functions) {
+ state.actionsForFunction[func->name];
+ }
+ // find and plan inlinings
+ {
+ PassRunner runner(module);
+ runner.add<Planner>(&state);
+ runner.run();
+ }
+ // perform inlinings
+ std::set<Name> inlined;
+ std::set<Function*> inlinedInto;
+ for (auto& func : module->functions) {
+ for (auto& action : state.actionsForFunction[func->name]) {
+ doInlining(module, func.get(), action);
+ inlined.insert(action.contents->name);
+ inlinedInto.insert(func.get());
+ }
+ }
+ // anything we inlined into may now have non-unique label names, fix it up
+ for (auto func : inlinedInto) {
+ wasm::UniqueNameMapper::uniquify(func->body);
+ }
+ // remove functions that we managed to inline, their one use is gone
+ auto& funcs = module->functions;
+ funcs.erase(std::remove_if(funcs.begin(), funcs.end(), [&inlined](const std::unique_ptr<Function>& curr) {
+ return inlined.count(curr->name) > 0;
+ }), funcs.end());
+ // return whether we did any work
+ return inlined.size() > 0;
+ }
+};
+
+Pass *createInliningPass() {
+ return new Inlining();
+}
+
+} // namespace wasm
+
diff --git a/src/passes/pass.cpp b/src/passes/pass.cpp
index f88e6675d..c8704db89 100644
--- a/src/passes/pass.cpp
+++ b/src/passes/pass.cpp
@@ -69,6 +69,7 @@ void PassRegistry::registerPasses() {
registerPass("dce", "removes unreachable code", createDeadCodeEliminationPass);
registerPass("duplicate-function-elimination", "removes duplicate functions", createDuplicateFunctionEliminationPass);
registerPass("extract-function", "leaves just one function (useful for debugging)", createExtractFunctionPass);
+ registerPass("inlining", "inlines functions (currently only ones with a single use)", createInliningPass);
registerPass("legalize-js-interface", "legalizes i64 types on the import/export boundary", createLegalizeJSInterfacePass);
registerPass("merge-blocks", "merges blocks to their parents", createMergeBlocksPass);
registerPass("metrics", "reports metrics", createMetricsPass);
diff --git a/src/passes/passes.h b/src/passes/passes.h
index 828512aba..bb577f86a 100644
--- a/src/passes/passes.h
+++ b/src/passes/passes.h
@@ -29,6 +29,7 @@ Pass *createDeadCodeEliminationPass();
Pass *createDuplicateFunctionEliminationPass();
Pass *createExtractFunctionPass();
Pass *createFullPrinterPass();
+Pass *createInliningPass();
Pass *createLegalizeJSInterfacePass();
Pass *createLowerIfElsePass();
Pass *createMinifiedPrinterPass();
diff --git a/src/wasm-builder.h b/src/wasm-builder.h
index a8c7bc4d1..4f3a80091 100644
--- a/src/wasm-builder.h
+++ b/src/wasm-builder.h
@@ -269,6 +269,10 @@ public:
return index;
}
+ static Index addVar(Function* func, WasmType type) {
+ return addVar(func, Name(), type);
+ }
+
static void clearLocals(Function* func) {
func->params.clear();
func->vars.clear();
generated by cgit v1.2.3 (git 2.39.1) at 2025-08-07 06:43:22 +0000