summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/ir/type-updating.cpp4
-rw-r--r--src/ir/type-updating.h1
-rw-r--r--src/passes/CMakeLists.txt1
-rw-r--r--src/passes/TypeMerging.cpp267
-rw-r--r--src/passes/TypeSSA.cpp2
-rw-r--r--src/passes/pass.cpp3
-rw-r--r--src/passes/passes.h1
7 files changed, 279 insertions, 0 deletions
diff --git a/src/ir/type-updating.cpp b/src/ir/type-updating.cpp
index 47931baad..31c110738 100644
--- a/src/ir/type-updating.cpp
+++ b/src/ir/type-updating.cpp
@@ -266,6 +266,10 @@ Type GlobalTypeRewriter::getTempType(Type type) {
WASM_UNREACHABLE("bad type");
}
+Type GlobalTypeRewriter::getTempTupleType(Tuple tuple) {
+ return typeBuilder.getTempTupleType(tuple);
+}
+
namespace TypeUpdating {
bool canHandleAsLocal(Type type) {
diff --git a/src/ir/type-updating.h b/src/ir/type-updating.h
index 8da84ceb6..12e0b8b57 100644
--- a/src/ir/type-updating.h
+++ b/src/ir/type-updating.h
@@ -360,6 +360,7 @@ public:
// so that they can use a proper temp type of the TypeBuilder while modifying
// things.
Type getTempType(Type type);
+ Type getTempTupleType(Tuple tuple);
using SignatureUpdates = std::unordered_map<HeapType, Signature>;
diff --git a/src/passes/CMakeLists.txt b/src/passes/CMakeLists.txt
index ea06bebb1..e97f5e388 100644
--- a/src/passes/CMakeLists.txt
+++ b/src/passes/CMakeLists.txt
@@ -100,6 +100,7 @@ set(passes_SOURCES
ReReloop.cpp
TrapMode.cpp
TypeRefining.cpp
+ TypeMerging.cpp
TypeSSA.cpp
SafeHeap.cpp
SimplifyGlobals.cpp
diff --git a/src/passes/TypeMerging.cpp b/src/passes/TypeMerging.cpp
new file mode 100644
index 000000000..94a198adf
--- /dev/null
+++ b/src/passes/TypeMerging.cpp
@@ -0,0 +1,267 @@
+/*
+ * Copyright 2022 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.
+ */
+
+//
+// Merge unneeded types: types that are not needed for validation, and have no
+// detectable runtime effect. Completely unused types are removed anyhow during
+// binary writing, so this handles the case of used types that can be merged
+// into others. Specifically we merge a type into its super, which is possible
+// when it has no extra fields, no refined fields, and no casts.
+//
+// Note that such "redundant" types may help the optimizer, so merging them can
+// have a negative effect later. For that reason this may be best run near the
+// very end of the optimization pipeline, when nothing else is expected to do
+// type-based optimizations later. However, you also do not want to merge at the
+// very end, as e.g. type merging may open up function merging opportunities.
+// One possible sequence:
+//
+// --type-ssa -Os --type-merging -Os
+//
+// That is, running TypeSSA early makes sense, as it provides more type info.
+// Then we hope the optimizer benefits from that, and after that we merge types
+// and then optimize a final time. You can experiment with more optimization
+// passes in between.
+//
+
+#include "ir/module-utils.h"
+#include "ir/type-updating.h"
+#include "pass.h"
+#include "support/small_set.h"
+#include "wasm-builder.h"
+#include "wasm.h"
+
+namespace wasm {
+
+namespace {
+
+// We need to find all the types that have references to them, such as casts,
+// as such types must be preserved - even if they are identical to other types,
+// they are nominally distinguishable.
+
+// Most functions do no casts, or perhaps cast |this| and perhaps a few others.
+using ReferredTypes = SmallUnorderedSet<HeapType, 5>;
+
+struct CastFinder
+ : public PostWalker<CastFinder, UnifiedExpressionVisitor<CastFinder>> {
+ ReferredTypes referredTypes;
+
+ void visitExpression(Expression* curr) {
+ // Find all references to a heap type.
+
+#define DELEGATE_ID curr->_id
+
+#define DELEGATE_START(id) [[maybe_unused]] auto* cast = curr->cast<id>();
+
+#define DELEGATE_FIELD_HEAPTYPE(id, field) referredTypes.insert(cast->field);
+
+#define DELEGATE_FIELD_CHILD(id, field)
+#define DELEGATE_FIELD_OPTIONAL_CHILD(id, field)
+#define DELEGATE_FIELD_INT(id, field)
+#define DELEGATE_FIELD_INT_ARRAY(id, field)
+#define DELEGATE_FIELD_LITERAL(id, field)
+#define DELEGATE_FIELD_NAME(id, field)
+#define DELEGATE_FIELD_NAME_VECTOR(id, field)
+#define DELEGATE_FIELD_SCOPE_NAME_DEF(id, field)
+#define DELEGATE_FIELD_SCOPE_NAME_USE(id, field)
+#define DELEGATE_FIELD_SCOPE_NAME_USE_VECTOR(id, field)
+#define DELEGATE_FIELD_TYPE(id, field)
+#define DELEGATE_FIELD_ADDRESS(id, field)
+#define DELEGATE_FIELD_CHILD_VECTOR(id, field)
+
+#include "wasm-delegations-fields.def"
+ }
+};
+
+struct TypeMerging : public Pass {
+ // Only modifies types.
+ bool requiresNonNullableLocalFixups() override { return false; }
+
+ Module* module;
+
+ // The types we can merge. We map each such type to merge with the type we
+ // want to merge it with.
+ using TypeUpdates = std::unordered_map<HeapType, HeapType>;
+ TypeUpdates merges;
+
+ void run(Module* module_) override {
+ module = module_;
+
+ if (!module->features.hasGC()) {
+ return;
+ }
+
+ // First, find all the cast types.
+
+ ModuleUtils::ParallelFunctionAnalysis<ReferredTypes> analysis(
+ *module, [&](Function* func, ReferredTypes& referredTypes) {
+ if (func->imported()) {
+ return;
+ }
+
+ CastFinder finder;
+ finder.walk(func->body);
+ referredTypes = std::move(finder.referredTypes);
+ });
+
+ // Also find cast types in the module scope (not possible in the current
+ // spec, but do it to be future-proof).
+ CastFinder moduleFinder;
+ moduleFinder.walkModuleCode(module);
+
+ // Accumulate all the referredTypes.
+ auto& allReferredTypes = moduleFinder.referredTypes;
+ for (auto& [k, referredTypes] : analysis.map) {
+ for (auto type : referredTypes) {
+ allReferredTypes.insert(type);
+ }
+ }
+
+ // Find all the heap types.
+ std::vector<HeapType> types = ModuleUtils::collectHeapTypes(*module);
+
+ // TODO: There may be more opportunities after this loop. Imagine that we
+ // decide to merge A and B into C, and there are types X and Y that
+ // contain a nested reference to A and B respectively, then after A
+ // and B become identical so do X and Y. The recursive case is not
+ // trivial, however, and needs more thought.
+ for (auto type : types) {
+ if (allReferredTypes.count(type)) {
+ // This has a cast, so it is distinguishable nominally.
+ continue;
+ }
+
+ auto super = type.getSuperType();
+ if (!super) {
+ // This has no supertype, so there is nothing to merge it into.
+ continue;
+ }
+
+ // TODO: arrays
+ if (!type.isStruct()) {
+ continue;
+ }
+
+ auto& fields = type.getStruct().fields;
+ auto& superFields = super->getStruct().fields;
+ if (fields != superFields) {
+ // This adds a field, or refines one, so it differs from the super, and
+ // we cannot merge it with the super.
+ continue;
+ }
+
+ // We can merge! This is identical structurally to the super, and also not
+ // distinguishable nominally.
+ merges[type] = *super;
+ }
+
+ if (merges.empty()) {
+ return;
+ }
+
+ // We found things to optimize! Rewrite types in the module to apply those
+ // changes.
+
+ // First, close over the map, so if X can be merged into Y and Y into Z then
+ // we map X into Z.
+ for (auto type : types) {
+ if (!merges.count(type)) {
+ continue;
+ }
+
+ auto newType = merges[type];
+ while (merges.count(newType)) {
+ newType = merges[newType];
+ }
+ // Apply the findings to all intermediate types as well, to avoid
+ // duplicate work in later iterations. That is, all the types we saw in
+ // the above loop will all get merged into newType.
+ auto curr = type;
+ while (1) {
+ auto iter = merges.find(curr);
+ if (iter == merges.end()) {
+ break;
+ }
+ auto& currMerge = iter->second;
+ curr = currMerge;
+ currMerge = newType;
+ }
+ }
+
+ // Apply the merges.
+
+ class TypeInternalsUpdater : public GlobalTypeRewriter {
+ const TypeUpdates& merges;
+
+ std::unordered_map<HeapType, Signature> newSignatures;
+
+ public:
+ TypeInternalsUpdater(Module& wasm, const TypeUpdates& merges)
+ : GlobalTypeRewriter(wasm), merges(merges) {
+
+ // Map the types of expressions (curr->type, etc.) to their merged
+ // types.
+ mapTypes(merges);
+
+ // Update the internals of types (struct fields, signatures, etc.) to
+ // refer to the merged types.
+ update();
+ }
+
+ Type getNewType(Type type) {
+ if (!type.isRef()) {
+ return type;
+ }
+ auto heapType = type.getHeapType();
+ auto iter = merges.find(heapType);
+ if (iter != merges.end()) {
+ return getTempType(Type(iter->second, type.getNullability()));
+ }
+ return getTempType(type);
+ }
+
+ void modifyStruct(HeapType oldType, Struct& struct_) override {
+ auto& oldFields = oldType.getStruct().fields;
+ for (Index i = 0; i < oldFields.size(); i++) {
+ auto& oldField = oldFields[i];
+ auto& newField = struct_.fields[i];
+ newField.type = getNewType(oldField.type);
+ }
+ }
+ void modifyArray(HeapType oldType, Array& array) override {
+ array.element.type = getNewType(oldType.getArray().element.type);
+ }
+ void modifySignature(HeapType oldSignatureType, Signature& sig) override {
+ auto getUpdatedTypeList = [&](Type type) {
+ std::vector<Type> vec;
+ for (auto t : type) {
+ vec.push_back(getNewType(t));
+ }
+ return getTempTupleType(vec);
+ };
+
+ auto oldSig = oldSignatureType.getSignature();
+ sig.params = getUpdatedTypeList(oldSig.params);
+ sig.results = getUpdatedTypeList(oldSig.results);
+ }
+ } rewriter(*module, merges);
+ }
+};
+
+} // anonymous namespace
+
+Pass* createTypeMergingPass() { return new TypeMerging(); }
+
+} // namespace wasm
diff --git a/src/passes/TypeSSA.cpp b/src/passes/TypeSSA.cpp
index e25795cdc..17f166a9e 100644
--- a/src/passes/TypeSSA.cpp
+++ b/src/passes/TypeSSA.cpp
@@ -44,6 +44,8 @@
// then we do nothing atm. We could create a phi there, but in general that
// would require multiple inheritance. TODO think more on that
//
+// This pass works well with TypeMerging. See notes there for more.
+//
#include "ir/find_all.h"
#include "ir/module-utils.h"
diff --git a/src/passes/pass.cpp b/src/passes/pass.cpp
index b97d182c6..d7f2a310f 100644
--- a/src/passes/pass.cpp
+++ b/src/passes/pass.cpp
@@ -461,6 +461,9 @@ void PassRegistry::registerPasses() {
registerPass("trap-mode-js",
"replace trapping operations with js semantics",
createTrapModeJS);
+ registerPass("type-merging",
+ "merge types to their supertypes where possible",
+ createTypeMergingPass);
registerPass("type-ssa",
"create new nominal types to help other optimizations",
createTypeSSAPass);
diff --git a/src/passes/passes.h b/src/passes/passes.h
index 126dc5f12..1543ae794 100644
--- a/src/passes/passes.h
+++ b/src/passes/passes.h
@@ -148,6 +148,7 @@ Pass* createSSAifyNoMergePass();
Pass* createTrapModeClamp();
Pass* createTrapModeJS();
Pass* createTypeRefiningPass();
+Pass* createTypeMergingPass();
Pass* createTypeSSAPass();
Pass* createUnteePass();
Pass* createVacuumPass();