summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/ir/lubs.h8
-rw-r--r--src/ir/type-updating.cpp3
-rw-r--r--src/passes/CMakeLists.txt3
-rw-r--r--src/passes/GlobalSubtyping.cpp272
-rw-r--r--src/passes/GlobalTypeOptimization.cpp2
-rw-r--r--src/passes/pass.cpp4
-rw-r--r--src/passes/passes.h3
7 files changed, 292 insertions, 3 deletions
diff --git a/src/ir/lubs.h b/src/ir/lubs.h
index b75932091..a45b62c52 100644
--- a/src/ir/lubs.h
+++ b/src/ir/lubs.h
@@ -39,6 +39,14 @@ struct LUBFinder {
// Returns the lub that we found.
Type get() { return lub; }
+
+ // Combines the information in another LUBFinder into this one, and returns
+ // whether we changed anything.
+ bool combine(const LUBFinder& other) {
+ auto old = lub;
+ note(other.lub);
+ return lub != old;
+ }
};
} // namespace wasm
diff --git a/src/ir/type-updating.cpp b/src/ir/type-updating.cpp
index cacdc9000..316dbd93f 100644
--- a/src/ir/type-updating.cpp
+++ b/src/ir/type-updating.cpp
@@ -26,6 +26,9 @@ GlobalTypeRewriter::GlobalTypeRewriter(Module& wasm) : wasm(wasm) {}
void GlobalTypeRewriter::update() {
ModuleUtils::collectHeapTypes(wasm, types, typeIndices);
+ if (types.empty()) {
+ return;
+ }
typeBuilder.grow(types.size());
// Create the temporary heap types.
diff --git a/src/passes/CMakeLists.txt b/src/passes/CMakeLists.txt
index 4ee7fe9d1..56f12dc17 100644
--- a/src/passes/CMakeLists.txt
+++ b/src/passes/CMakeLists.txt
@@ -30,6 +30,8 @@ set(passes_SOURCES
Flatten.cpp
FuncCastEmulation.cpp
GenerateDynCalls.cpp
+ GlobalSubtyping.cpp
+ GlobalTypeOptimization.cpp
Heap2Local.cpp
I64ToI32Lowering.cpp
Inlining.cpp
@@ -87,7 +89,6 @@ set(passes_SOURCES
SSAify.cpp
Untee.cpp
Vacuum.cpp
- GlobalTypeOptimization.cpp
${CMAKE_CURRENT_BINARY_DIR}/WasmIntrinsics.cpp
${passes_HEADERS}
)
diff --git a/src/passes/GlobalSubtyping.cpp b/src/passes/GlobalSubtyping.cpp
new file mode 100644
index 000000000..7cf963f0d
--- /dev/null
+++ b/src/passes/GlobalSubtyping.cpp
@@ -0,0 +1,272 @@
+/*
+ * Copyright 2021 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.
+ */
+
+//
+// Apply more specific subtypes to type fields where possible, where all the
+// writes to that field in the entire program allow doing so.
+//
+
+#include "ir/lubs.h"
+#include "ir/struct-utils.h"
+#include "ir/type-updating.h"
+#include "ir/utils.h"
+#include "pass.h"
+#include "support/unique_deferring_queue.h"
+#include "wasm-type.h"
+#include "wasm.h"
+
+namespace wasm {
+
+namespace {
+
+// We use a LUBFinder to track field info. A LUBFinder keeps track of the best
+// possible LUB so far. The only extra functionality we need here is whether
+// there is a default null value (which would force us to keep the type
+// nullable).
+struct FieldInfo : public LUBFinder {
+ bool nullDefault = false;
+
+ void noteNullDefault() { nullDefault = true; }
+
+ bool hasNullDefault() { return nullDefault; }
+
+ bool noted() { return LUBFinder::noted() || nullDefault; }
+
+ Type get() {
+ auto ret = LUBFinder::get();
+ if (nullDefault && !ret.isNullable()) {
+ ret = Type(ret.getHeapType(), Nullable);
+ }
+ return ret;
+ }
+
+ bool combine(const FieldInfo& other) {
+ auto old = nullDefault;
+ if (other.nullDefault) {
+ noteNullDefault();
+ }
+ return LUBFinder::combine(other) || nullDefault != old;
+ }
+
+ // Force the lub to a particular type.
+ void set(Type type) { lub = type; }
+
+ void dump(std::ostream& o) {
+ std::cout << "FieldInfo(" << lub << ", " << nullDefault << ")";
+ }
+};
+
+struct FieldInfoScanner
+ : public StructUtils::StructScanner<FieldInfo, FieldInfoScanner> {
+ Pass* create() override {
+ return new FieldInfoScanner(functionNewInfos, functionSetGetInfos);
+ }
+
+ FieldInfoScanner(
+ StructUtils::FunctionStructValuesMap<FieldInfo>& functionNewInfos,
+ StructUtils::FunctionStructValuesMap<FieldInfo>& functionSetGetInfos)
+ : StructUtils::StructScanner<FieldInfo, FieldInfoScanner>(
+ functionNewInfos, functionSetGetInfos) {}
+
+ void noteExpression(Expression* expr,
+ HeapType type,
+ Index index,
+ FieldInfo& info) {
+ info.note(expr);
+ }
+
+ void
+ noteDefault(Type fieldType, HeapType type, Index index, FieldInfo& info) {
+ // Default values do not affect what the heap type of a field can be turned
+ // into. Note them, however, as they force us to keep the type nullable.
+ if (fieldType.isRef()) {
+ info.noteNullDefault();
+ }
+ }
+
+ void noteCopy(HeapType type, Index index, FieldInfo& info) {
+ // Copies do not add any type requirements at all: the type will always be
+ // read and written to a place with the same type.
+ }
+
+ void noteRead(HeapType type, Index index, FieldInfo& info) {
+ // Nothing to do for a read, we just care about written values.
+ }
+};
+
+struct GlobalSubtyping : public Pass {
+ StructUtils::StructValuesMap<FieldInfo> finalInfos;
+
+ void run(PassRunner* runner, Module* module) override {
+ if (getTypeSystem() != TypeSystem::Nominal) {
+ Fatal() << "GlobalSubtyping requires nominal typing";
+ }
+
+ // Find and analyze struct operations inside each function.
+ StructUtils::FunctionStructValuesMap<FieldInfo> functionNewInfos(*module),
+ functionSetGetInfos(*module);
+ FieldInfoScanner scanner(functionNewInfos, functionSetGetInfos);
+ scanner.run(runner, module);
+ scanner.runOnModuleCode(runner, module);
+
+ // Combine the data from the functions.
+ StructUtils::StructValuesMap<FieldInfo> combinedNewInfos;
+ StructUtils::StructValuesMap<FieldInfo> combinedSetGetInfos;
+ functionNewInfos.combineInto(combinedNewInfos);
+ functionSetGetInfos.combineInto(combinedSetGetInfos);
+
+ // Propagate things written during new to supertypes, as they must also be
+ // able to contain that type. Propagate things written using set to subtypes
+ // as well, as the reference might be to a supertype if the field is present
+ // there.
+ StructUtils::TypeHierarchyPropagator<FieldInfo> propagator(*module);
+ propagator.propagateToSuperTypes(combinedNewInfos);
+ propagator.propagateToSuperAndSubTypes(combinedSetGetInfos);
+
+ // Combine everything together.
+ combinedNewInfos.combineInto(finalInfos);
+ combinedSetGetInfos.combineInto(finalInfos);
+
+ // While we do the following work, see if we have anything to optimize, so
+ // that we can avoid wasteful work later if not.
+ bool canOptimize = false;
+
+ // We have combined all the information we have about writes to the fields,
+ // but we still need to make sure that the new types makes sense. In
+ // particular, subtyping cares about things like mutability, and we also
+ // need to handle the case where we have no writes to a type but do have
+ // them to subtypes or supertypes; in all these cases, we must preserve
+ // that a field is always a subtype of the parent field. To do so, we go
+ // through all the types downward from supertypes to subtypes, ensuring the
+ // subtypes are suitable.
+ auto& subTypes = propagator.subTypes;
+ UniqueDeferredQueue<HeapType> work;
+ for (auto type : subTypes.types) {
+ if (type.isStruct() && !type.getSuperType()) {
+ work.push(type);
+ }
+ }
+ while (!work.empty()) {
+ auto type = work.pop();
+
+ // First, find fields that have nothing written to them at all, and set
+ // their value to their old type. We must pick some type for the field,
+ // and we have nothing better to go on. (If we have a super, and it does
+ // have writes, then we may further update this type later, see the
+ // isSubType check in the loop after this.)
+ auto& fields = type.getStruct().fields;
+ for (Index i = 0; i < fields.size(); i++) {
+ auto oldType = fields[i].type;
+ auto& info = finalInfos[type][i];
+ auto newType = info.get();
+ if (newType == Type::unreachable) {
+ info.set(oldType);
+ }
+ }
+
+ // Next ensure proper subtyping of this struct's fields versus its super.
+ if (auto super = type.getSuperType()) {
+ auto& superFields = super->getStruct().fields;
+ for (Index i = 0; i < superFields.size(); i++) {
+ auto newSuperType = finalInfos[*super][i].get();
+ auto& info = finalInfos[type][i];
+ auto newType = info.get();
+ if (!Type::isSubType(newType, newSuperType)) {
+ // To ensure we are a subtype of the super's field, simply copy that
+ // value, which is more specific than us.
+ //
+ // This situation cannot happen normally, but if a type is not used
+ // then it can. For example, imagine that $B and $C are subtypes of
+ // $A, and that $C is never created anywhere. A struct.new of $B
+ // propagates info to $A (forcing $A's type to take it into account
+ // and not be more specific than it), but that does not reach $C
+ // (struct.new propagates only up, not down; if it propagated down
+ // then we could never specialize a subtype more than its super). If
+ // $C had some value written to it then that value would force the
+ // LUB of $A to take it into account, but as here $C is never even
+ // created, that does not happen. And then if we update $A's type
+ // to something more specific than $C's old type, we end up with the
+ // problem that this code path fixes: we just need to get $C's type
+ // to be identical to its super so that validation works.
+ info.set(newSuperType);
+ } else if (fields[i].mutable_ == Mutable) {
+ // Mutable fields must have identical types, so we cannot
+ // specialize.
+ // TODO: Perhaps we should be using a new Field::isSubType() method
+ // here? This entire analysis might be done on fields, and not
+ // types, which would also handle more things added to fields
+ // in the future.
+ info.set(newSuperType);
+ }
+ }
+ }
+
+ // After all those decisions, see if we found anything to optimize.
+ if (!canOptimize) {
+ for (Index i = 0; i < fields.size(); i++) {
+ auto oldType = fields[i].type;
+ auto newType = finalInfos[type][i].get();
+ if (newType != oldType) {
+ canOptimize = true;
+ break;
+ }
+ }
+ }
+
+ for (auto subType : subTypes.getSubTypes(type)) {
+ work.push(subType);
+ }
+ }
+
+ if (canOptimize) {
+ updateTypes(*module, runner);
+ }
+ }
+
+ void updateTypes(Module& wasm, PassRunner* runner) {
+ class TypeRewriter : public GlobalTypeRewriter {
+ GlobalSubtyping& parent;
+
+ public:
+ TypeRewriter(Module& wasm, GlobalSubtyping& parent)
+ : GlobalTypeRewriter(wasm), parent(parent) {}
+
+ void modifyStruct(HeapType oldStructType, Struct& struct_) override {
+ const auto& oldFields = oldStructType.getStruct().fields;
+ auto& newFields = struct_.fields;
+
+ for (Index i = 0; i < newFields.size(); i++) {
+ auto oldType = oldFields[i].type;
+ if (!oldType.isRef()) {
+ continue;
+ }
+ auto newType = parent.finalInfos[oldStructType][i].get();
+ newFields[i].type = getTempType(newType);
+ }
+ }
+ };
+
+ TypeRewriter(wasm, *this).update();
+
+ ReFinalize().run(runner, &wasm);
+ }
+};
+
+} // anonymous namespace
+
+Pass* createGlobalSubtypingPass() { return new GlobalSubtyping(); }
+
+} // namespace wasm
diff --git a/src/passes/GlobalTypeOptimization.cpp b/src/passes/GlobalTypeOptimization.cpp
index 306faa3ca..0c919ddf0 100644
--- a/src/passes/GlobalTypeOptimization.cpp
+++ b/src/passes/GlobalTypeOptimization.cpp
@@ -216,7 +216,7 @@ struct GlobalTypeOptimization : public Pass {
TypeRewriter(Module& wasm, GlobalTypeOptimization& parent)
: GlobalTypeRewriter(wasm), parent(parent) {}
- virtual void modifyStruct(HeapType oldStructType, Struct& struct_) {
+ void modifyStruct(HeapType oldStructType, Struct& struct_) override {
auto& newFields = struct_.fields;
// Adjust immutability.
diff --git a/src/passes/pass.cpp b/src/passes/pass.cpp
index 3b0faa6c3..2c7199781 100644
--- a/src/passes/pass.cpp
+++ b/src/passes/pass.cpp
@@ -156,6 +156,9 @@ void PassRegistry::registerPasses() {
"generate-stack-ir", "generate Stack IR", createGenerateStackIRPass);
registerPass(
"gto", "globally optimize GC types", createGlobalTypeOptimizationPass);
+ registerPass("global-subtyping",
+ "apply more specific subtypes to type fields where possible",
+ createGlobalSubtypingPass);
registerPass(
"heap2local", "replace GC allocations with locals", createHeap2LocalPass);
registerPass(
@@ -524,6 +527,7 @@ void PassRunner::addDefaultGlobalOptimizationPrePasses() {
}
if (wasm->features.hasGC() && getTypeSystem() == TypeSystem::Nominal &&
options.optimizeLevel >= 2) {
+ addIfNoDWARFIssues("global-subtyping");
// Global type optimization can remove fields that are not needed, which can
// remove ref.funcs that were once assigned to vtables but are no longer
// needed, which can allow more code to be removed globally. After those,
diff --git a/src/passes/passes.h b/src/passes/passes.h
index a08e42f62..b9ba566d0 100644
--- a/src/passes/passes.h
+++ b/src/passes/passes.h
@@ -51,6 +51,8 @@ Pass* createFunctionMetricsPass();
Pass* createGenerateDynCallsPass();
Pass* createGenerateI64DynCallsPass();
Pass* createGenerateStackIRPass();
+Pass* createGlobalSubtypingPass();
+Pass* createGlobalTypeOptimizationPass();
Pass* createHeap2LocalPass();
Pass* createI64ToI32LoweringPass();
Pass* createInlineMainPass();
@@ -131,7 +133,6 @@ Pass* createTrapModeClamp();
Pass* createTrapModeJS();
Pass* createUnteePass();
Pass* createVacuumPass();
-Pass* createGlobalTypeOptimizationPass();
} // namespace wasm
generated by cgit v1.2.3 (git 2.39.1) at 2025-07-15 11:05:54 +0000