diff options
| -rw-r--r-- | src/ir/struct-utils.h | 43 | ||||
| -rw-r--r-- | src/ir/type-updating.h | 3 | ||||
| -rw-r--r-- | src/passes/ConstantFieldPropagation.cpp | 6 | ||||
| -rw-r--r-- | src/passes/GlobalTypeOptimization.cpp | 275 | ||||
| -rw-r--r-- | src/passes/pass.cpp | 2 | ||||
| -rw-r--r-- | test/lit/passes/gto-mutability.wast | 201 | ||||
| -rw-r--r-- | test/lit/passes/gto-removals.wast | 389 |
7 files changed, 857 insertions, 62 deletions
diff --git a/src/ir/struct-utils.h b/src/ir/struct-utils.h index 442d990fb..5d0f5a9b8 100644 --- a/src/ir/struct-utils.h +++ b/src/ir/struct-utils.h @@ -119,17 +119,22 @@ struct FunctionStructValuesMap // // void noteCopy(HeapType type, Index index, T& info); // -// We track information from struct.new and struct.set separately, because in -// struct.new we know more about the type - we know the actual exact type being -// written to, and not just that it is of a subtype of the instruction's type, -// which helps later. +// * Note a read +// +// void noteRead(HeapType type, Index index, T& info); +// +// We track information from struct.new and struct.set/struct.get separately, +// because in struct.new we know more about the type - we know the actual exact +// type being written to, and not just that it is of a subtype of the +// instruction's type, which helps later. template<typename T, typename SubType> struct Scanner : public WalkerPass<PostWalker<Scanner<T, SubType>>> { bool isFunctionParallel() override { return true; } Scanner(FunctionStructValuesMap<T>& functionNewInfos, - FunctionStructValuesMap<T>& functionSetInfos) - : functionNewInfos(functionNewInfos), functionSetInfos(functionSetInfos) {} + FunctionStructValuesMap<T>& functionSetGetInfos) + : functionNewInfos(functionNewInfos), + functionSetGetInfos(functionSetGetInfos) {} void visitStructNew(StructNew* curr) { auto type = curr->type; @@ -158,11 +163,25 @@ struct Scanner : public WalkerPass<PostWalker<Scanner<T, SubType>>> { } // Note a write to this field of the struct. - noteExpressionOrCopy( - curr->value, - type.getHeapType(), - curr->index, - functionSetInfos[this->getFunction()][type.getHeapType()][curr->index]); + noteExpressionOrCopy(curr->value, + type.getHeapType(), + curr->index, + functionSetGetInfos[this->getFunction()] + [type.getHeapType()][curr->index]); + } + + void visitStructGet(StructGet* curr) { + auto type = curr->ref->type; + if (type == Type::unreachable) { + return; + } + + auto heapType = type.getHeapType(); + auto index = curr->index; + static_cast<SubType*>(this)->noteRead( + heapType, + index, + functionSetGetInfos[this->getFunction()][heapType][index]); } void @@ -186,7 +205,7 @@ struct Scanner : public WalkerPass<PostWalker<Scanner<T, SubType>>> { } FunctionStructValuesMap<T>& functionNewInfos; - FunctionStructValuesMap<T>& functionSetInfos; + FunctionStructValuesMap<T>& functionSetGetInfos; }; // Helper class to propagate information about fields to sub- and/or super- diff --git a/src/ir/type-updating.h b/src/ir/type-updating.h index 83c1e1aa1..d3be7c3ca 100644 --- a/src/ir/type-updating.h +++ b/src/ir/type-updating.h @@ -309,6 +309,8 @@ struct TypeUpdater // made while doing so. class GlobalTypeRewriter { public: + Module& wasm; + GlobalTypeRewriter(Module& wasm); virtual ~GlobalTypeRewriter() {} @@ -332,7 +334,6 @@ public: Type getTempType(Type type); private: - Module& wasm; TypeBuilder typeBuilder; // The list of old types. diff --git a/src/passes/ConstantFieldPropagation.cpp b/src/passes/ConstantFieldPropagation.cpp index 2fdd8333c..f6bad04b6 100644 --- a/src/passes/ConstantFieldPropagation.cpp +++ b/src/passes/ConstantFieldPropagation.cpp @@ -214,7 +214,7 @@ private: struct PCVScanner : public Scanner<PossibleConstantValues, PCVScanner> { Pass* create() override { - return new PCVScanner(functionNewInfos, functionSetInfos); + return new PCVScanner(functionNewInfos, functionSetGetInfos); } PCVScanner(FunctionStructValuesMap<PossibleConstantValues>& functionNewInfos, @@ -261,6 +261,10 @@ struct PCVScanner : public Scanner<PossibleConstantValues, PCVScanner> { // analysis (but this is already entering the realm of diminishing // returns). } + + void noteRead(HeapType type, Index index, PossibleConstantValues& info) { + // Reads do not interest us. + } }; struct ConstantFieldPropagation : public Pass { diff --git a/src/passes/GlobalTypeOptimization.cpp b/src/passes/GlobalTypeOptimization.cpp index 35b10bfff..442b7570a 100644 --- a/src/passes/GlobalTypeOptimization.cpp +++ b/src/passes/GlobalTypeOptimization.cpp @@ -19,11 +19,13 @@ // types defined in the module. // // * Immutability: If a field has no struct.set, it can become immutable. +// * Fields that are never read from can be removed entirely. // // TODO: Specialize field types. // TODO: Remove unused fields. // +#include "ir/effects.h" #include "ir/struct-utils.h" #include "ir/subtypes.h" #include "ir/type-updating.h" @@ -43,27 +45,34 @@ namespace { // Information about usage of a field. struct FieldInfo { bool hasWrite = false; + bool hasRead = false; void noteWrite() { hasWrite = true; } + void noteRead() { hasRead = true; } bool combine(const FieldInfo& other) { + bool changed = false; if (!hasWrite && other.hasWrite) { hasWrite = true; - return true; + changed = true; } - return false; + if (!hasRead && other.hasRead) { + hasRead = true; + changed = true; + } + return changed; } }; struct FieldInfoScanner : public Scanner<FieldInfo, FieldInfoScanner> { Pass* create() override { - return new FieldInfoScanner(functionNewInfos, functionSetInfos); + return new FieldInfoScanner(functionNewInfos, functionSetGetInfos); } FieldInfoScanner(FunctionStructValuesMap<FieldInfo>& functionNewInfos, - FunctionStructValuesMap<FieldInfo>& functionSetInfos) - : Scanner<FieldInfo, FieldInfoScanner>(functionNewInfos, functionSetInfos) { - } + FunctionStructValuesMap<FieldInfo>& functionSetGetInfos) + : Scanner<FieldInfo, FieldInfoScanner>(functionNewInfos, + functionSetGetInfos) {} void noteExpression(Expression* expr, HeapType type, @@ -80,9 +89,31 @@ struct FieldInfoScanner : public Scanner<FieldInfo, FieldInfoScanner> { void noteCopy(HeapType type, Index index, FieldInfo& info) { info.noteWrite(); } + + void noteRead(HeapType type, Index index, FieldInfo& info) { + info.noteRead(); + } }; struct GlobalTypeOptimization : public Pass { + StructValuesMap<FieldInfo> combinedSetGetInfos; + + // Maps types to a vector of booleans that indicate whether a field can + // become immutable. To avoid eager allocation of memory, the vectors are + // only resized when we actually have a true to place in them (which is + // rare). + std::unordered_map<HeapType, std::vector<bool>> canBecomeImmutable; + + // Maps each field to its new index after field removals. That is, this + // takes into account that fields before this one may have been removed, + // which would then reduce this field's index. If a field itself is removed, + // it has the special value |RemovedField|. This is always of the full size + // of the number of fields, unlike canBecomeImmutable which is lazily + // allocated, as if we remove one field that affects the indexes of all the + // others anyhow. + static const Index RemovedField = Index(-1); + std::unordered_map<HeapType, std::vector<Index>> indexesAfterRemovals; + void run(PassRunner* runner, Module* module) override { if (getTypeSystem() != TypeSystem::Nominal) { Fatal() << "GlobalTypeOptimization requires nominal typing"; @@ -90,50 +121,50 @@ struct GlobalTypeOptimization : public Pass { // Find and analyze struct operations inside each function. FunctionStructValuesMap<FieldInfo> functionNewInfos(*module), - functionSetInfos(*module); - FieldInfoScanner scanner(functionNewInfos, functionSetInfos); + functionSetGetInfos(*module); + FieldInfoScanner scanner(functionNewInfos, functionSetGetInfos); scanner.run(runner, module); scanner.runOnModuleCode(runner, module); // Combine the data from the functions. - StructValuesMap<FieldInfo> combinedNewInfos, combinedSetInfos; - functionSetInfos.combineInto(combinedSetInfos); + functionSetGetInfos.combineInto(combinedSetGetInfos); // TODO: combine newInfos as well, once we have a need for that (we will // when we do things like subtyping). - // Find which fields are immutable in all super- and sub-classes. To see - // that, propagate sets in both directions. This is necessary because we - // cannot have a supertype's field be immutable while a subtype's is not - - // they must match for us to preserve subtyping. + // Propagate information to super and subtypes on set/get infos: + // + // * For removing unread fields, we can only remove a field if it is never + // read in any sub or supertype, as such a read may alias any of those + // types (where the field is present). // - // Note that we do not need to care about types here: If the fields were - // mutable before, then they must have had identical types for them to be - // subtypes (as wasm only allows the type to differ if the fields are - // immutable). Note that by making more things immutable we therefore make - // it possible to apply more specific subtypes in subtype fields. + // * For immutability, this is necessary because we cannot have a + // supertype's field be immutable while a subtype's is not - they must + // match for us to preserve subtyping. + // + // Note that we do not need to care about types here: If the fields were + // mutable before, then they must have had identical types for them to be + // subtypes (as wasm only allows the type to differ if the fields are + // immutable). Note that by making more things immutable we therefore + // make it possible to apply more specific subtypes in subtype fields. TypeHierarchyPropagator<FieldInfo> propagator(*module); - propagator.propagateToSuperAndSubTypes(combinedSetInfos); - - // Maps types to a vector of booleans that indicate if we can turn the - // field immutable. To avoid eager allocation of memory, the vectors are - // only resized when we actually have a true to place in them (which is - // rare). - using CanBecomeImmutable = std::unordered_map<HeapType, std::vector<bool>>; - CanBecomeImmutable canBecomeImmutable; + propagator.propagateToSuperAndSubTypes(combinedSetGetInfos); + // Process the propagated info. for (auto type : propagator.subTypes.types) { if (!type.isStruct()) { continue; } - auto& fields = type.getStruct().fields; + auto& infos = combinedSetGetInfos[type]; + + // Process immutability. for (Index i = 0; i < fields.size(); i++) { if (fields[i].mutable_ == Immutable) { // Already immutable; nothing to do. continue; } - if (combinedSetInfos[type][i].hasWrite) { + if (infos[i].hasWrite) { // A set exists. continue; } @@ -143,33 +174,195 @@ struct GlobalTypeOptimization : public Pass { vec.resize(i + 1); vec[i] = true; } + + // Process removability. First, see if we can remove anything before we + // start to allocate info for that. + if (std::any_of(infos.begin(), infos.end(), [&](const FieldInfo& info) { + return !info.hasRead; + })) { + auto& indexesAfterRemoval = indexesAfterRemovals[type]; + indexesAfterRemoval.resize(fields.size()); + Index skip = 0; + for (Index i = 0; i < fields.size(); i++) { + if (infos[i].hasRead) { + indexesAfterRemoval[i] = i - skip; + } else { + indexesAfterRemoval[i] = RemovedField; + skip++; + } + } + } } - // The types are now generally correct, except for their internals, which we - // rewrite now. + // If we found fields that can be removed, remove them from instructions. + // (Note that we must do this first, while we still have the old heap types + // that we can identify, and only after this should we update all the types + // throughout the module.) + if (!indexesAfterRemovals.empty()) { + removeFieldsInInstructions(runner, *module); + } + + // Update the types in the entire module. + updateTypes(*module); + } + + void updateTypes(Module& wasm) { class TypeRewriter : public GlobalTypeRewriter { - CanBecomeImmutable& canBecomeImmutable; + GlobalTypeOptimization& parent; public: - TypeRewriter(Module& wasm, CanBecomeImmutable& canBecomeImmutable) - : GlobalTypeRewriter(wasm), canBecomeImmutable(canBecomeImmutable) {} + TypeRewriter(Module& wasm, GlobalTypeOptimization& parent) + : GlobalTypeRewriter(wasm), parent(parent) {} virtual void modifyStruct(HeapType oldStructType, Struct& struct_) { - if (!canBecomeImmutable.count(oldStructType)) { + auto& newFields = struct_.fields; + + // Adjust immutability. + auto immIter = parent.canBecomeImmutable.find(oldStructType); + if (immIter != parent.canBecomeImmutable.end()) { + auto& immutableVec = immIter->second; + for (Index i = 0; i < immutableVec.size(); i++) { + if (immutableVec[i]) { + newFields[i].mutable_ = Immutable; + } + } + } + + // Remove fields where we can. + auto remIter = parent.indexesAfterRemovals.find(oldStructType); + if (remIter != parent.indexesAfterRemovals.end()) { + auto& indexesAfterRemoval = remIter->second; + Index removed = 0; + for (Index i = 0; i < newFields.size(); i++) { + auto newIndex = indexesAfterRemoval[i]; + if (newIndex != RemovedField) { + newFields[newIndex] = newFields[i]; + } else { + removed++; + } + } + newFields.resize(newFields.size() - removed); + + // Update field names as well. The Type Rewriter cannot do this for + // us, as it does not know which old fields map to which new ones (it + // just keeps the names in sequence). + auto iter = wasm.typeNames.find(oldStructType); + if (iter != wasm.typeNames.end()) { + auto& nameInfo = iter->second; + + // Make a copy of the old ones to base ourselves off of as we do so. + auto oldFieldNames = nameInfo.fieldNames; + + // Clear the old names and write the new ones. + nameInfo.fieldNames.clear(); + for (Index i = 0; i < oldFieldNames.size(); i++) { + auto newIndex = indexesAfterRemoval[i]; + if (newIndex != RemovedField && oldFieldNames.count(i)) { + assert(oldFieldNames[i].is()); + nameInfo.fieldNames[newIndex] = oldFieldNames[i]; + } + } + } + } + } + }; + + TypeRewriter(wasm, *this).update(); + } + + // After updating the types to remove certain fields, we must also remove + // them from struct instructions. + void removeFieldsInInstructions(PassRunner* runner, Module& wasm) { + struct FieldRemover : public WalkerPass<PostWalker<FieldRemover>> { + bool isFunctionParallel() override { return true; } + + GlobalTypeOptimization& parent; + + FieldRemover(GlobalTypeOptimization& parent) : parent(parent) {} + + FieldRemover* create() override { return new FieldRemover(parent); } + + void visitStructNew(StructNew* curr) { + if (curr->type == Type::unreachable) { + return; + } + if (curr->isWithDefault()) { + // Nothing to do, a default was written and will no longer be. return; } - auto& newFields = struct_.fields; - auto& immutableVec = canBecomeImmutable[oldStructType]; - for (Index i = 0; i < immutableVec.size(); i++) { - if (immutableVec[i]) { - newFields[i].mutable_ = Immutable; + auto iter = parent.indexesAfterRemovals.find(curr->type.getHeapType()); + if (iter == parent.indexesAfterRemovals.end()) { + return; + } + auto& indexesAfterRemoval = iter->second; + + auto& operands = curr->operands; + assert(indexesAfterRemoval.size() == operands.size()); + + // Remove the unneeded operands. + Index removed = 0; + for (Index i = 0; i < operands.size(); i++) { + auto newIndex = indexesAfterRemoval[i]; + if (newIndex != RemovedField) { + assert(newIndex < operands.size()); + operands[newIndex] = operands[i]; + } else { + if (EffectAnalyzer(getPassOptions(), *getModule(), operands[i]) + .hasUnremovableSideEffects()) { + Fatal() << "TODO: handle side effects in field removal " + "(impossible in global locations?)"; + } + removed++; } } + operands.resize(operands.size() - removed); + } + + void visitStructSet(StructSet* curr) { + if (curr->ref->type == Type::unreachable) { + return; + } + + auto newIndex = getNewIndex(curr->ref->type.getHeapType(), curr->index); + if (newIndex != RemovedField) { + // Map to the new index. + curr->index = newIndex; + } else { + // This field was removed, so just emit drops of our children. + Builder builder(*getModule()); + replaceCurrent(builder.makeSequence(builder.makeDrop(curr->ref), + builder.makeDrop(curr->value))); + } + } + + void visitStructGet(StructGet* curr) { + if (curr->ref->type == Type::unreachable) { + return; + } + + auto newIndex = getNewIndex(curr->ref->type.getHeapType(), curr->index); + // We must not remove a field that is read from. + assert(newIndex != RemovedField); + curr->index = newIndex; + } + + Index getNewIndex(HeapType type, Index index) { + auto iter = parent.indexesAfterRemovals.find(type); + if (iter == parent.indexesAfterRemovals.end()) { + return index; + } + auto& indexesAfterRemoval = iter->second; + auto newIndex = indexesAfterRemoval[index]; + assert(newIndex < indexesAfterRemoval.size() || + newIndex == RemovedField); + return newIndex; } }; - TypeRewriter(*module, canBecomeImmutable).update(); + FieldRemover remover(*this); + remover.run(runner, &wasm); + remover.runOnModuleCode(runner, &wasm); } }; diff --git a/src/passes/pass.cpp b/src/passes/pass.cpp index 67087c328..fd31dada8 100644 --- a/src/passes/pass.cpp +++ b/src/passes/pass.cpp @@ -524,9 +524,9 @@ void PassRunner::addDefaultGlobalOptimizationPrePasses() { } if (wasm->features.hasGC() && getTypeSystem() == TypeSystem::Nominal && options.optimizeLevel >= 2) { + // TODO: investigate enabling --gto and --remove-module-elements before cfp addIfNoDWARFIssues("cfp"); } - // TODO: investigate enabling --gto } void PassRunner::addDefaultGlobalOptimizationPostPasses() { diff --git a/test/lit/passes/gto-mutability.wast b/test/lit/passes/gto-mutability.wast index 8610e0760..bd657bb90 100644 --- a/test/lit/passes/gto-mutability.wast +++ b/test/lit/passes/gto-mutability.wast @@ -15,6 +15,8 @@ ;; CHECK: (type $none_=>_ref?|$struct| (func_subtype (result (ref null $struct)) func)) + ;; CHECK: (type $none_=>_none (func_subtype func)) + ;; CHECK: (tag $tag (param (ref $struct))) (tag $tag (param (ref $struct))) @@ -114,6 +116,19 @@ ) (ref.null $struct) ) + + ;; CHECK: (func $field-keepalive + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (struct.get $struct 2 + ;; CHECK-NEXT: (ref.null $struct) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $field-keepalive + ;; --gto will remove fields that are not read from, so add reads to any + ;; that don't already have them. + (drop (struct.get $struct 2 (ref.null $struct))) + ) ) (module @@ -127,6 +142,8 @@ ;; CHECK: (type $ref|$A|_=>_none (func_subtype (param (ref $A)) func)) + ;; CHECK: (type $none_=>_none (func_subtype func)) + ;; CHECK: (func $func (param $x (ref $A)) ;; CHECK-NEXT: (struct.set $A 0 ;; CHECK-NEXT: (local.get $x) @@ -147,6 +164,35 @@ (i32.const 20) ) ) + + ;; CHECK: (func $field-keepalive + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (struct.get $A 0 + ;; CHECK-NEXT: (ref.null $A) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (struct.get $A 1 + ;; CHECK-NEXT: (ref.null $A) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (struct.get $B 0 + ;; CHECK-NEXT: (ref.null $B) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (struct.get $B 1 + ;; CHECK-NEXT: (ref.null $B) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $field-keepalive + (drop (struct.get $A 0 (ref.null $A))) + (drop (struct.get $A 1 (ref.null $A))) + (drop (struct.get $B 0 (ref.null $B))) + (drop (struct.get $B 1 (ref.null $B))) + ) ) (module @@ -160,6 +206,8 @@ ;; CHECK: (type $ref|$B|_=>_none (func_subtype (param (ref $B)) func)) + ;; CHECK: (type $none_=>_none (func_subtype func)) + ;; CHECK: (func $func (param $x (ref $B)) ;; CHECK-NEXT: (struct.set $B 0 ;; CHECK-NEXT: (local.get $x) @@ -180,6 +228,35 @@ (f64.const 3.14159) ) ) + + ;; CHECK: (func $field-keepalive + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (struct.get $A 0 + ;; CHECK-NEXT: (ref.null $A) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (struct.get $A 1 + ;; CHECK-NEXT: (ref.null $A) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (struct.get $B 0 + ;; CHECK-NEXT: (ref.null $B) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (struct.get $B 1 + ;; CHECK-NEXT: (ref.null $B) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $field-keepalive + (drop (struct.get $A 0 (ref.null $A))) + (drop (struct.get $A 1 (ref.null $A))) + (drop (struct.get $B 0 (ref.null $B))) + (drop (struct.get $B 1 (ref.null $B))) + ) ) (module @@ -193,6 +270,8 @@ ;; CHECK: (type $ref|$A|_ref|$B|_=>_none (func_subtype (param (ref $A) (ref $B)) func)) + ;; CHECK: (type $none_=>_none (func_subtype func)) + ;; CHECK: (func $func (param $x (ref $A)) (param $y (ref $B)) ;; CHECK-NEXT: (struct.set $A 0 ;; CHECK-NEXT: (local.get $x) @@ -213,6 +292,35 @@ (f64.const 3.14159) ) ) + + ;; CHECK: (func $field-keepalive + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (struct.get $A 0 + ;; CHECK-NEXT: (ref.null $A) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (struct.get $A 1 + ;; CHECK-NEXT: (ref.null $A) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (struct.get $B 0 + ;; CHECK-NEXT: (ref.null $B) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (struct.get $B 1 + ;; CHECK-NEXT: (ref.null $B) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $field-keepalive + (drop (struct.get $A 0 (ref.null $A))) + (drop (struct.get $A 1 (ref.null $A))) + (drop (struct.get $B 0 (ref.null $B))) + (drop (struct.get $B 1 (ref.null $B))) + ) ) (module @@ -225,6 +333,8 @@ ;; CHECK: (type $ref|$struct|_=>_none (func_subtype (param (ref $struct)) func)) + ;; CHECK: (type $none_=>_none (func_subtype func)) + ;; CHECK: (func $func (param $x (ref $struct)) ;; CHECK-NEXT: (struct.set $struct 2 ;; CHECK-NEXT: (local.get $x) @@ -237,19 +347,42 @@ (i32.const 1) ) ) + + ;; CHECK: (func $field-keepalive + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (struct.get $struct 0 + ;; CHECK-NEXT: (ref.null $struct) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (struct.get $struct 1 + ;; CHECK-NEXT: (ref.null $struct) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (struct.get $struct 2 + ;; CHECK-NEXT: (ref.null $struct) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $field-keepalive + (drop (struct.get $struct 0 (ref.null $struct))) + (drop (struct.get $struct 1 (ref.null $struct))) + (drop (struct.get $struct 2 (ref.null $struct))) + ) ) (module ;; Subtyping. Without a write in either supertype or subtype, we can ;; optimize the field to be immutable. - ;; CHECK: (type $none_=>_none (func_subtype func)) - ;; CHECK: (type $super (struct_subtype (field i32) data)) (type $super (struct (field (mut i32)))) ;; CHECK: (type $sub (struct_subtype (field i32) $super)) (type $sub (struct_subtype (field (mut i32)) $super)) + ;; CHECK: (type $none_=>_none (func_subtype func)) + ;; CHECK: (func $func ;; CHECK-NEXT: (drop ;; CHECK-NEXT: (struct.new $super @@ -275,6 +408,23 @@ ) ) ) + + ;; CHECK: (func $field-keepalive + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (struct.get $super 0 + ;; CHECK-NEXT: (ref.null $super) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (struct.get $sub 0 + ;; CHECK-NEXT: (ref.null $sub) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $field-keepalive + (drop (struct.get $super 0 (ref.null $super))) + (drop (struct.get $sub 0 (ref.null $sub))) + ) ) (module @@ -282,11 +432,13 @@ ;; CHECK: (type $super (struct_subtype (field (mut i32)) data)) (type $super (struct (field (mut i32)))) - ;; CHECK: (type $ref|$super|_=>_none (func_subtype (param (ref $super)) func)) - ;; CHECK: (type $sub (struct_subtype (field (mut i32)) $super)) (type $sub (struct_subtype (field (mut i32)) $super)) + ;; CHECK: (type $ref|$super|_=>_none (func_subtype (param (ref $super)) func)) + + ;; CHECK: (type $none_=>_none (func_subtype func)) + ;; CHECK: (func $func (param $x (ref $super)) ;; CHECK-NEXT: (drop ;; CHECK-NEXT: (struct.new $super @@ -320,19 +472,39 @@ (i32.const 2) ) ) + + ;; CHECK: (func $field-keepalive + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (struct.get $super 0 + ;; CHECK-NEXT: (ref.null $super) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (struct.get $sub 0 + ;; CHECK-NEXT: (ref.null $sub) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $field-keepalive + (drop (struct.get $super 0 (ref.null $super))) + (drop (struct.get $sub 0 (ref.null $sub))) + ) ) (module ;; As above, but add a write in the sub, which prevents optimization. - ;; CHECK: (type $sub (struct_subtype (field (mut i32)) $super)) - ;; CHECK: (type $ref|$sub|_=>_none (func_subtype (param (ref $sub)) func)) + ;; CHECK: (type $sub (struct_subtype (field (mut i32)) $super)) ;; CHECK: (type $super (struct_subtype (field (mut i32)) data)) (type $super (struct (field (mut i32)))) (type $sub (struct_subtype (field (mut i32)) $super)) + ;; CHECK: (type $ref|$sub|_=>_none (func_subtype (param (ref $sub)) func)) + + ;; CHECK: (type $none_=>_none (func_subtype func)) + ;; CHECK: (func $func (param $x (ref $sub)) ;; CHECK-NEXT: (struct.set $sub 0 ;; CHECK-NEXT: (local.get $x) @@ -345,4 +517,21 @@ (i32.const 2) ) ) + + ;; CHECK: (func $field-keepalive + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (struct.get $super 0 + ;; CHECK-NEXT: (ref.null $super) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (struct.get $sub 0 + ;; CHECK-NEXT: (ref.null $sub) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $field-keepalive + (drop (struct.get $super 0 (ref.null $super))) + (drop (struct.get $sub 0 (ref.null $sub))) + ) ) diff --git a/test/lit/passes/gto-removals.wast b/test/lit/passes/gto-removals.wast new file mode 100644 index 000000000..2247285ca --- /dev/null +++ b/test/lit/passes/gto-removals.wast @@ -0,0 +1,389 @@ +;; NOTE: Assertions have been generated by update_lit_checks.py --all-items and should not be edited. +;; RUN: foreach %s %t wasm-opt --nominal --gto -all -S -o - | filecheck %s +;; (remove-unused-names is added to test fallthrough values without a block +;; name getting in the way) + +(module + ;; A struct with a field that is never read or written, so it can be + ;; removed. + + ;; CHECK: (type $ref|$struct|_=>_none (func_subtype (param (ref $struct)) func)) + + ;; CHECK: (type $struct (struct_subtype data)) + (type $struct (struct_subtype (field (mut funcref)) data)) + + ;; CHECK: (func $func (param $x (ref $struct)) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: ) + (func $func (param $x (ref $struct)) + ) +) + +(module + ;; A write does not keep a field from being removed. + + ;; CHECK: (type $ref|$struct|_=>_none (func_subtype (param (ref $struct)) func)) + + ;; CHECK: (type $struct (struct_subtype data)) + (type $struct (struct_subtype (field (mut funcref)) data)) + + ;; CHECK: (func $func (param $x (ref $struct)) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (local.get $x) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (ref.null func) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $func (param $x (ref $struct)) + ;; The fields of this set will be dropped, as we do not need to perform + ;; the write. + (struct.set $struct 0 + (local.get $x) + (ref.null func) + ) + ) +) + +(module + ;; A new does not keep a field from being removed. + + ;; CHECK: (type $struct (struct_subtype data)) + (type $struct (struct_subtype (field (mut funcref)) data)) + + ;; CHECK: (type $ref|$struct|_=>_none (func_subtype (param (ref $struct)) func)) + + ;; CHECK: (func $func (param $x (ref $struct)) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (struct.new_default $struct) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $func (param $x (ref $struct)) + ;; The fields in this new will be removed. + (drop + (struct.new $struct + (ref.null func) + ) + ) + ) +) + +(module + ;; A new_default does not keep a field from being removed. + + ;; CHECK: (type $struct (struct_subtype data)) + (type $struct (struct_subtype (field (mut funcref)) data)) + + ;; CHECK: (type $ref|$struct|_=>_none (func_subtype (param (ref $struct)) func)) + + ;; CHECK: (func $func (param $x (ref $struct)) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (struct.new_default $struct) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $func (param $x (ref $struct)) + ;; The fields in this new will be removed. + (drop + (struct.new_default $struct + ) + ) + ) +) + +(module + ;; A read *does* keep a field from being removed. + + ;; CHECK: (type $struct (struct_subtype (field funcref) data)) + (type $struct (struct_subtype (field (mut funcref)) data)) + + ;; CHECK: (type $ref|$struct|_=>_none (func_subtype (param (ref $struct)) func)) + + ;; CHECK: (func $func (param $x (ref $struct)) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (struct.get $struct 0 + ;; CHECK-NEXT: (local.get $x) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $func (param $x (ref $struct)) + (drop + (struct.get $struct 0 + (local.get $x) + ) + ) + ) +) + +(module + ;; Different struct types with different situations: some fields are read, + ;; some written, and some both. (Note that this also tests the interaction + ;; of removing with the immutability inference that --gto does.) + + ;; A struct with all fields marked mutable. + ;; CHECK: (type $mut-struct (struct_subtype (field $r i32) (field $rw (mut i32)) (field $r-2 i32) (field $rw-2 (mut i32)) data)) + (type $mut-struct (struct_subtype (field $r (mut i32)) (field $w (mut i32)) (field $rw (mut i32)) (field $r-2 (mut i32)) (field $w-2 (mut i32)) (field $rw-2 (mut i32)) data)) + + ;; A similar struct but with all fields marked immutable, and the only + ;; writes are from during creation (so all fields are at least writeable). + ;; CHECK: (type $imm-struct (struct_subtype (field $rw i32) (field $rw-2 i32) data)) + (type $imm-struct (struct_subtype (field $w i32) (field $rw i32) (field $w-2 i32) (field $rw-2 i32) data)) + + ;; CHECK: (type $ref|$mut-struct|_=>_none (func_subtype (param (ref $mut-struct)) func)) + + ;; CHECK: (type $ref|$imm-struct|_=>_none (func_subtype (param (ref $imm-struct)) func)) + + ;; CHECK: (func $func-mut (param $x (ref $mut-struct)) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (struct.get $mut-struct $r + ;; CHECK-NEXT: (local.get $x) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (block + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (local.get $x) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (struct.set $mut-struct $rw + ;; CHECK-NEXT: (local.get $x) + ;; CHECK-NEXT: (i32.const 1) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (struct.get $mut-struct $rw + ;; CHECK-NEXT: (local.get $x) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (struct.get $mut-struct $r-2 + ;; CHECK-NEXT: (local.get $x) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (block + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (local.get $x) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (i32.const 2) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (struct.set $mut-struct $rw-2 + ;; CHECK-NEXT: (local.get $x) + ;; CHECK-NEXT: (i32.const 3) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (struct.get $mut-struct $rw-2 + ;; CHECK-NEXT: (local.get $x) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $func-mut (param $x (ref $mut-struct)) + ;; $r is only read + (drop + (struct.get $mut-struct $r + (local.get $x) + ) + ) + ;; $w is only written + (struct.set $mut-struct $w + (local.get $x) + (i32.const 0) + ) + ;; $rw is both + (struct.set $mut-struct $rw + (local.get $x) + (i32.const 1) + ) + (drop + (struct.get $mut-struct $rw + (local.get $x) + ) + ) + ;; The same, for the $*-2 fields + (drop + (struct.get $mut-struct $r-2 + (local.get $x) + ) + ) + (struct.set $mut-struct $w-2 + (local.get $x) + (i32.const 2) + ) + (struct.set $mut-struct $rw-2 + (local.get $x) + (i32.const 3) + ) + (drop + (struct.get $mut-struct $rw-2 + (local.get $x) + ) + ) + ) + + ;; CHECK: (func $func-imm (param $x (ref $imm-struct)) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (struct.new $imm-struct + ;; CHECK-NEXT: (i32.const 1) + ;; CHECK-NEXT: (i32.const 3) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (struct.get $imm-struct $rw + ;; CHECK-NEXT: (local.get $x) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (struct.get $imm-struct $rw-2 + ;; CHECK-NEXT: (local.get $x) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $func-imm (param $x (ref $imm-struct)) + ;; create an instance + (drop + (struct.new $imm-struct + (i32.const 0) + (i32.const 1) + (i32.const 2) + (i32.const 3) + ) + ) + ;; $rw and $rw-2 are also read + (drop + (struct.get $imm-struct $rw + (local.get $x) + ) + ) + (drop + (struct.get $imm-struct $rw-2 + (local.get $x) + ) + ) + ) +) + +(module + ;; A vtable-like structure created in a global location. Only some of the + ;; fields are accessed. + + ;; CHECK: (type $none_=>_none (func_subtype func)) + + ;; CHECK: (type $vtable (struct_subtype (field $v1 funcref) (field $v2 funcref) data)) + (type $vtable (struct_subtype (field $v0 funcref) (field $v1 funcref) (field $v2 funcref) (field $v3 funcref) (field $v4 funcref) data)) + + ;; CHECK: (global $vtable (ref $vtable) (struct.new $vtable + ;; CHECK-NEXT: (ref.func $func-1) + ;; CHECK-NEXT: (ref.func $func-2) + ;; CHECK-NEXT: )) + (global $vtable (ref $vtable) (struct.new $vtable + (ref.func $func-0) + (ref.func $func-1) + (ref.func $func-2) + (ref.func $func-3) + (ref.func $func-4) + )) + + ;; CHECK: (func $test + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (struct.get $vtable $v1 + ;; CHECK-NEXT: (global.get $vtable) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (struct.get $vtable $v2 + ;; CHECK-NEXT: (global.get $vtable) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $test + ;; To differ from previous tests, do not read the very first field. + (drop + (struct.get $vtable 1 + (global.get $vtable) + ) + ) + ;; To differ from previous tests, do reads in two adjacent fields. + (drop + (struct.get $vtable 2 + (global.get $vtable) + ) + ) + ;; To differ from previous tests, do not read the very last field, and the + ;; one before it. + ) + + ;; CHECK: (func $func-0 + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: ) + (func $func-0) + ;; CHECK: (func $func-1 + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: ) + (func $func-1) + ;; CHECK: (func $func-2 + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: ) + (func $func-2) + ;; CHECK: (func $func-3 + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: ) + (func $func-3) + ;; CHECK: (func $func-4 + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: ) + (func $func-4) +) + +(module + ;; Similar to the above, but with different types in each field, to verify + ;; that we emit valid code and are not confused by the names being right + ;; by coincidence. + + + ;; CHECK: (type $vtable (struct_subtype (field $v1 i64) (field $v2 f32) data)) + (type $vtable (struct_subtype (field $v0 i32) (field $v1 i64) (field $v2 f32) (field $v3 f64) (field $v4 anyref) data)) + + ;; CHECK: (type $none_=>_none (func_subtype func)) + + ;; CHECK: (global $vtable (ref $vtable) (struct.new $vtable + ;; CHECK-NEXT: (i64.const 1) + ;; CHECK-NEXT: (f32.const 2.200000047683716) + ;; CHECK-NEXT: )) + (global $vtable (ref $vtable) (struct.new $vtable + (i32.const 0) + (i64.const 1) + (f32.const 2.2) + (f64.const 3.3) + (ref.null data) + )) + + ;; CHECK: (func $test + ;; CHECK-NEXT: (local $i64 i64) + ;; CHECK-NEXT: (local $f32 f32) + ;; CHECK-NEXT: (local.set $i64 + ;; CHECK-NEXT: (struct.get $vtable $v1 + ;; CHECK-NEXT: (global.get $vtable) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (local.set $f32 + ;; CHECK-NEXT: (struct.get $vtable $v2 + ;; CHECK-NEXT: (global.get $vtable) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $test + (local $i64 i64) + (local $f32 f32) + (local.set $i64 + (struct.get $vtable 1 + (global.get $vtable) + ) + ) + (local.set $f32 + (struct.get $vtable 2 + (global.get $vtable) + ) + ) + ) +) |