From 5d398d5c9305272b971322d728c4628b38c5669c Mon Sep 17 00:00:00 2001 From: Alon Zakai Date: Mon, 15 Nov 2021 16:41:53 -0800 Subject: [NFC] HeapRefining => TypeRefining (#4332) --- src/passes/CMakeLists.txt | 2 +- src/passes/HeapRefining.cpp | 272 -------------------------------------------- src/passes/TypeRefining.cpp | 272 ++++++++++++++++++++++++++++++++++++++++++++ src/passes/pass.cpp | 6 +- src/passes/passes.h | 2 +- 5 files changed, 277 insertions(+), 277 deletions(-) delete mode 100644 src/passes/HeapRefining.cpp create mode 100644 src/passes/TypeRefining.cpp (limited to 'src') diff --git a/src/passes/CMakeLists.txt b/src/passes/CMakeLists.txt index b3a7db4c9..25c9cb6b3 100644 --- a/src/passes/CMakeLists.txt +++ b/src/passes/CMakeLists.txt @@ -32,7 +32,6 @@ set(passes_SOURCES GenerateDynCalls.cpp GlobalTypeOptimization.cpp Heap2Local.cpp - HeapRefining.cpp I64ToI32Lowering.cpp Inlining.cpp InstrumentLocals.cpp @@ -81,6 +80,7 @@ set(passes_SOURCES ReorderFunctions.cpp ReReloop.cpp TrapMode.cpp + TypeRefining.cpp SafeHeap.cpp SimplifyGlobals.cpp SimplifyLocals.cpp diff --git a/src/passes/HeapRefining.cpp b/src/passes/HeapRefining.cpp deleted file mode 100644 index 54d6f5103..000000000 --- a/src/passes/HeapRefining.cpp +++ /dev/null @@ -1,272 +0,0 @@ -/* - * 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 { - Pass* create() override { - return new FieldInfoScanner(functionNewInfos, functionSetGetInfos); - } - - FieldInfoScanner( - StructUtils::FunctionStructValuesMap& functionNewInfos, - StructUtils::FunctionStructValuesMap& functionSetGetInfos) - : StructUtils::StructScanner( - 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 HeapRefining : public Pass { - StructUtils::StructValuesMap finalInfos; - - void run(PassRunner* runner, Module* module) override { - if (getTypeSystem() != TypeSystem::Nominal) { - Fatal() << "HeapRefining requires nominal typing"; - } - - // Find and analyze struct operations inside each function. - StructUtils::FunctionStructValuesMap functionNewInfos(*module), - functionSetGetInfos(*module); - FieldInfoScanner scanner(functionNewInfos, functionSetGetInfos); - scanner.run(runner, module); - scanner.runOnModuleCode(runner, module); - - // Combine the data from the functions. - StructUtils::StructValuesMap combinedNewInfos; - StructUtils::StructValuesMap 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 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 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 { - HeapRefining& parent; - - public: - TypeRewriter(Module& wasm, HeapRefining& 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* createHeapRefiningPass() { return new HeapRefining(); } - -} // namespace wasm diff --git a/src/passes/TypeRefining.cpp b/src/passes/TypeRefining.cpp new file mode 100644 index 000000000..33e382bc5 --- /dev/null +++ b/src/passes/TypeRefining.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 { + Pass* create() override { + return new FieldInfoScanner(functionNewInfos, functionSetGetInfos); + } + + FieldInfoScanner( + StructUtils::FunctionStructValuesMap& functionNewInfos, + StructUtils::FunctionStructValuesMap& functionSetGetInfos) + : StructUtils::StructScanner( + 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 TypeRefining : public Pass { + StructUtils::StructValuesMap finalInfos; + + void run(PassRunner* runner, Module* module) override { + if (getTypeSystem() != TypeSystem::Nominal) { + Fatal() << "TypeRefining requires nominal typing"; + } + + // Find and analyze struct operations inside each function. + StructUtils::FunctionStructValuesMap functionNewInfos(*module), + functionSetGetInfos(*module); + FieldInfoScanner scanner(functionNewInfos, functionSetGetInfos); + scanner.run(runner, module); + scanner.runOnModuleCode(runner, module); + + // Combine the data from the functions. + StructUtils::StructValuesMap combinedNewInfos; + StructUtils::StructValuesMap 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 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 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 { + TypeRefining& parent; + + public: + TypeRewriter(Module& wasm, TypeRefining& 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* createTypeRefiningPass() { return new TypeRefining(); } + +} // namespace wasm diff --git a/src/passes/pass.cpp b/src/passes/pass.cpp index 118b2e6ae..49615d81b 100644 --- a/src/passes/pass.cpp +++ b/src/passes/pass.cpp @@ -156,9 +156,9 @@ void PassRegistry::registerPasses() { "generate-stack-ir", "generate Stack IR", createGenerateStackIRPass); registerPass( "gto", "globally optimize GC types", createGlobalTypeOptimizationPass); - registerPass("heap-refining", + registerPass("type-refining", "apply more specific subtypes to type fields where possible", - createHeapRefiningPass); + createTypeRefiningPass); registerPass( "heap2local", "replace GC allocations with locals", createHeap2LocalPass); registerPass( @@ -527,7 +527,7 @@ void PassRunner::addDefaultGlobalOptimizationPrePasses() { } if (wasm->features.hasGC() && getTypeSystem() == TypeSystem::Nominal && options.optimizeLevel >= 2) { - addIfNoDWARFIssues("heap-refining"); + addIfNoDWARFIssues("type-refining"); // 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 365a68ad7..e8e8ecc78 100644 --- a/src/passes/passes.h +++ b/src/passes/passes.h @@ -53,7 +53,6 @@ Pass* createGenerateI64DynCallsPass(); Pass* createGenerateStackIRPass(); Pass* createGlobalTypeOptimizationPass(); Pass* createHeap2LocalPass(); -Pass* createHeapRefiningPass(); Pass* createI64ToI32LoweringPass(); Pass* createInlineMainPass(); Pass* createInliningPass(); @@ -131,6 +130,7 @@ Pass* createSSAifyPass(); Pass* createSSAifyNoMergePass(); Pass* createTrapModeClamp(); Pass* createTrapModeJS(); +Pass* createTypeRefiningPass(); Pass* createUnteePass(); Pass* createVacuumPass(); -- cgit v1.2.3