diff options
Diffstat (limited to 'src')
45 files changed, 622 insertions, 192 deletions
diff --git a/src/ir/CMakeLists.txt b/src/ir/CMakeLists.txt index e3315565b..2dadb743f 100644 --- a/src/ir/CMakeLists.txt +++ b/src/ir/CMakeLists.txt @@ -12,6 +12,7 @@ set(ir_SOURCES possible-contents.cpp properties.cpp LocalGraph.cpp + LocalStructuralDominance.cpp ReFinalize.cpp stack-utils.cpp table-utils.cpp diff --git a/src/ir/LocalStructuralDominance.cpp b/src/ir/LocalStructuralDominance.cpp new file mode 100644 index 000000000..cfb75e006 --- /dev/null +++ b/src/ir/LocalStructuralDominance.cpp @@ -0,0 +1,230 @@ +/* + * 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. + */ + +#include "ir/iteration.h" +#include "ir/local-structural-dominance.h" +#include "support/small_vector.h" + +namespace wasm { + +LocalStructuralDominance::LocalStructuralDominance(Function* func, + Module& wasm, + Mode mode) { + if (!wasm.features.hasReferenceTypes()) { + // No references, so nothing to look at. + return; + } + + bool hasRefVar = false; + for (auto var : func->vars) { + if (var.isRef()) { + hasRefVar = true; + break; + } + } + if (!hasRefVar) { + return; + } + + if (mode == NonNullableOnly) { + bool hasNonNullableVar = false; + for (auto var : func->vars) { + // Check if we have any non-nullable vars at all. + if (var.isNonNullable()) { + hasNonNullableVar = true; + break; + } + } + if (!hasNonNullableVar) { + return; + } + } + + struct Scanner : public PostWalker<Scanner> { + std::set<Index>& nonDominatingIndices; + + // The locals that have been set, and so at the current time, they + // structurally dominate. + std::vector<bool> localsSet; + + Scanner(Function* func, Mode mode, std::set<Index>& nonDominatingIndices) + : nonDominatingIndices(nonDominatingIndices) { + localsSet.resize(func->getNumLocals()); + + // Parameters always dominate. + for (Index i = 0; i < func->getNumParams(); i++) { + localsSet[i] = true; + } + + for (Index i = func->getNumParams(); i < func->getNumLocals(); i++) { + auto type = func->getLocalType(i); + // Mark locals we don't need to care about as "set". We never do any + // work for such a local. + if (!type.isRef() || (mode == NonNullableOnly && type.isNullable())) { + localsSet[i] = true; + } + } + + // Note that we do not need to start a scope for the function body. + // Logically there is a scope there, but there is no code after it, so + // there is nothing to clean up when that scope exits, so we may as well + // not even create a scope. Just start walking the body now. + walk(func->body); + } + + using Locals = SmallVector<Index, 5>; + + // When we exit a control flow scope, we must undo the locals that it set. + std::vector<Locals> cleanupStack; + + static void doBeginScope(Scanner* self, Expression** currp) { + self->cleanupStack.emplace_back(); + } + + static void doEndScope(Scanner* self, Expression** currp) { + for (auto index : self->cleanupStack.back()) { + assert(self->localsSet[index]); + self->localsSet[index] = false; + } + self->cleanupStack.pop_back(); + } + + static void doLocalSet(Scanner* self, Expression** currp) { + auto index = (*currp)->cast<LocalSet>()->index; + if (!self->localsSet[index]) { + // This local is now set until the end of this scope. + self->localsSet[index] = true; + // If we are not in the topmost scope, note this for later cleanup. + if (!self->cleanupStack.empty()) { + self->cleanupStack.back().push_back(index); + } + } + } + + static void scan(Scanner* self, Expression** currp) { + // Use a loop to avoid recursing on the last child - we can just go + // straight into a loop iteration for it. + while (1) { + Expression* curr = *currp; + + switch (curr->_id) { + case Expression::Id::InvalidId: + WASM_UNREACHABLE("bad id"); + + // local.get can just be visited immediately, as it has no children. + case Expression::Id::LocalGetId: { + auto index = curr->cast<LocalGet>()->index; + if (!self->localsSet[index]) { + self->nonDominatingIndices.insert(index); + } + return; + } + case Expression::Id::LocalSetId: { + auto* set = curr->cast<LocalSet>(); + if (!self->localsSet[set->index]) { + self->pushTask(doLocalSet, currp); + } + // Immediately continue in the loop. + currp = &set->value; + continue; + } + + // Control flow structures. + case Expression::Id::BlockId: { + auto* block = curr->cast<Block>(); + // Blocks with no name are never emitted in the binary format, so do + // not create a scope for them. + if (block->name.is()) { + self->pushTask(Scanner::doEndScope, currp); + } + auto& list = block->list; + for (int i = int(list.size()) - 1; i >= 0; i--) { + self->pushTask(Scanner::scan, &list[i]); + } + if (block->name.is()) { + // Just call the task immediately. + doBeginScope(self, currp); + } + return; + } + case Expression::Id::IfId: { + if (curr->cast<If>()->ifFalse) { + self->pushTask(Scanner::doEndScope, currp); + self->maybePushTask(Scanner::scan, &curr->cast<If>()->ifFalse); + self->pushTask(Scanner::doBeginScope, currp); + } + self->pushTask(Scanner::doEndScope, currp); + self->pushTask(Scanner::scan, &curr->cast<If>()->ifTrue); + self->pushTask(Scanner::doBeginScope, currp); + // Immediately continue in the loop. + currp = &curr->cast<If>()->condition; + continue; + } + case Expression::Id::LoopId: { + self->pushTask(Scanner::doEndScope, currp); + // Just call the task immediately. + doBeginScope(self, currp); + // Immediately continue in the loop. + currp = &curr->cast<Loop>()->body; + continue; + } + case Expression::Id::TryId: { + auto& list = curr->cast<Try>()->catchBodies; + for (int i = int(list.size()) - 1; i >= 0; i--) { + self->pushTask(Scanner::doEndScope, currp); + self->pushTask(Scanner::scan, &list[i]); + self->pushTask(Scanner::doBeginScope, currp); + } + self->pushTask(Scanner::doEndScope, currp); + // Just call the task immediately. + doBeginScope(self, currp); + // Immediately continue in the loop. + currp = &curr->cast<Try>()->body; + continue; + } + + default: { + // Control flow structures have been handled. This is an expression, + // which we scan normally. + assert(!Properties::isControlFlowStructure(curr)); + PostWalker<Scanner>::scan(self, currp); + return; + } + } + } + } + + // Only local.set needs to be visited. + void pushTask(TaskFunc func, Expression** currp) { + // Visits to anything but a set can be ignored, so only very specific + // tasks need to actually be pushed here. In particular, we don't want to + // push tasks to call doVisit* when those callbacks do nothing. + if (func == scan || func == doLocalSet || func == doBeginScope || + func == doEndScope) { + PostWalker<Scanner>::pushTask(func, currp); + } + } + void maybePushTask(TaskFunc func, Expression** currp) { + if (*currp) { + pushTask(func, currp); + } + } + }; + + Scanner(func, mode, nonDominatingIndices); +} + +} // namespace wasm diff --git a/src/ir/eh-utils.cpp b/src/ir/eh-utils.cpp index fe33b09c2..f9cd2d940 100644 --- a/src/ir/eh-utils.cpp +++ b/src/ir/eh-utils.cpp @@ -17,7 +17,6 @@ #include "ir/eh-utils.h" #include "ir/branch-utils.h" #include "ir/find_all.h" -#include "ir/type-updating.h" namespace wasm { @@ -157,9 +156,6 @@ void handleBlockNestedPops(Function* func, Module& wasm) { for (auto* try_ : trys.list) { handleBlockNestedPop(try_, func, wasm); } - // Pops we handled can be of non-defaultable types, so we may have created - // non-nullable type locals. Fix them. - TypeUpdating::handleNonDefaultableLocals(func, wasm); } Pop* findPop(Expression* expr) { diff --git a/src/ir/iteration.h b/src/ir/iteration.h index e897c51a5..a2c9ceef6 100644 --- a/src/ir/iteration.h +++ b/src/ir/iteration.h @@ -76,6 +76,7 @@ template<class Specific> class AbstractChildIterator { public: // The vector of children in the order emitted by wasm-delegations-fields // (which is in reverse execution order). + // TODO: rename this "reverseChildren"? SmallVector<Expression**, 4> children; AbstractChildIterator(Expression* parent) { diff --git a/src/ir/linear-execution.h b/src/ir/linear-execution.h index 99b3a2a22..c88d0e444 100644 --- a/src/ir/linear-execution.h +++ b/src/ir/linear-execution.h @@ -49,7 +49,7 @@ struct LinearExecutionWalker : public PostWalker<SubType, VisitorType> { switch (curr->_id) { case Expression::Id::InvalidId: - abort(); + WASM_UNREACHABLE("bad id"); case Expression::Id::BlockId: { self->pushTask(SubType::doVisitBlock, currp); if (curr->cast<Block>()->name.is()) { diff --git a/src/ir/local-structural-dominance.h b/src/ir/local-structural-dominance.h new file mode 100644 index 000000000..e0cc2f329 --- /dev/null +++ b/src/ir/local-structural-dominance.h @@ -0,0 +1,94 @@ +/* + * 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. + */ + +#ifndef wasm_ir_local_structural_dominance_h +#define wasm_ir_local_structural_dominance_h + +#include "wasm.h" + +namespace wasm { + +// +// This class is useful for the handling of non-nullable locals that is in the +// wasm spec: a local.get validates if it is structurally dominated by a set. +// That dominance proves the get cannot access the default null value, and, +// nicely, it can be validated in linear time. (Historically, this was called +// "1a" during spec discussions.) +// +// Concretely, this class finds which local indexes lack the structural +// dominance property. It only looks at reference types and not anything else. +// It can look at both nullable and non-nullable references, though, as it can +// be used to validate non-nullable ones, and also to check if a nullable one +// could become non-nullable and still validate. +// +// The property of "structural dominance" means that the set dominates the gets +// using wasm's structured control flow constructs, like this: +// +// (block $A +// (local.set $x ..) +// (local.get $x) ;; use in the same scope. +// (block $B +// (local.get $x) ;; use in an inner scope. +// ) +// ) +// +// That set structurally dominates both of those gets. However, in this example +// it does not: +// +// (block $A +// (local.set $x ..) +// ) +// (local.get $x) ;; use in an outer scope. +// +// This is a little similar to breaks: (br $foo) can only go to a label $foo +// that is in scope. +// +// Note that this property must hold on the final wasm binary, while we are +// checking it on Binaryen IR. The property will carry over, however: when +// lowering to wasm we may remove some Block nodes, but removing nodes cannot +// break validation. +// +// In fact, since Blocks without names are not emitted in the binary format (we +// never need them, since nothing can branch to them, so we just emit their +// contents), we can ignore them here. That means that this will validate, which +// is identical to the last example but the block has no name: +// +// (block ;; no name here +// (local.set $x ..) +// ) +// (local.get $x) +// +// It is useful to ignore such blocks here, as various passes emit them +// temporarily. +// +struct LocalStructuralDominance { + // We always look at non-nullable locals, but can be configured to ignore + // or process nullable ones. + enum Mode { + All, + NonNullableOnly, + }; + + LocalStructuralDominance(Function* func, Module& wasm, Mode mode = All); + + // Local indexes for whom a local.get exists that is not structurally + // dominated. + std::set<Index> nonDominatingIndices; +}; + +} // namespace wasm + +#endif // wasm_ir_local_structural_dominance_h diff --git a/src/ir/type-updating.cpp b/src/ir/type-updating.cpp index 5452613bb..6d5848c83 100644 --- a/src/ir/type-updating.cpp +++ b/src/ir/type-updating.cpp @@ -16,6 +16,7 @@ #include "type-updating.h" #include "find_all.h" +#include "ir/local-structural-dominance.h" #include "ir/module-utils.h" #include "ir/utils.h" #include "wasm-type.h" @@ -268,8 +269,12 @@ bool canHandleAsLocal(Type type) { } void handleNonDefaultableLocals(Function* func, Module& wasm) { - // Check if this is an issue. if (wasm.features.hasGCNNLocals()) { + // We have nothing to fix up: all locals are allowed. + return; + } + if (!wasm.features.hasReferenceTypes()) { + // No references, so no non-nullable ones at all. return; } bool hasNonNullable = false; @@ -280,6 +285,26 @@ void handleNonDefaultableLocals(Function* func, Module& wasm) { } } if (!hasNonNullable) { + // No non-nullable types exist in practice. + return; + } + + // Non-nullable locals exist, which we may need to fix up. See if they + // validate as they are, that is, if they fall within the validation rules of + // the wasm spec. We do not need to modify such locals. + LocalStructuralDominance info( + func, wasm, LocalStructuralDominance::NonNullableOnly); + std::unordered_set<Index> badIndexes; + for (auto index : info.nonDominatingIndices) { + badIndexes.insert(index); + + // LocalStructuralDominance should have only looked at non-nullable indexes + // since we told it to ignore nullable ones. Also, params always dominate + // and should not appear here. + assert(func->getLocalType(index).isNonNullable()); + assert(!func->isParam(index)); + } + if (badIndexes.empty()) { return; } @@ -287,11 +312,9 @@ void handleNonDefaultableLocals(Function* func, Module& wasm) { Builder builder(wasm); for (auto** getp : FindAllPointers<LocalGet>(func->body).list) { auto* get = (*getp)->cast<LocalGet>(); - if (!func->isVar(get->index)) { - // We do not need to process params, which can legally be non-nullable. - continue; + if (badIndexes.count(get->index)) { + *getp = fixLocalGet(get, wasm); } - *getp = fixLocalGet(get, wasm); } // Update tees, whose type must match the local (if the wasm spec changes for @@ -307,8 +330,8 @@ void handleNonDefaultableLocals(Function* func, Module& wasm) { if (!set->isTee() || set->type == Type::unreachable) { continue; } - auto type = func->getLocalType(set->index); - if (type.isNonNullable()) { + if (badIndexes.count(set->index)) { + auto type = func->getLocalType(set->index); set->type = Type(type.getHeapType(), Nullable); *setp = builder.makeRefAs(RefAsNonNull, set); } @@ -316,12 +339,14 @@ void handleNonDefaultableLocals(Function* func, Module& wasm) { // Rewrite the types of the function's vars (which we can do now, after we // are done using them to know which local.gets etc to fix). - for (auto& type : func->vars) { - type = getValidLocalType(type, wasm.features); + for (auto index : badIndexes) { + func->vars[index - func->getNumParams()] = + getValidLocalType(func->getLocalType(index), wasm.features); } } Type getValidLocalType(Type type, FeatureSet features) { + // TODO: this should handle tuples with a non-nullable item assert(canHandleAsLocal(type)); if (type.isNonNullable() && !features.hasGCNNLocals()) { type = Type(type.getHeapType(), Nullable); diff --git a/src/ir/utils.h b/src/ir/utils.h index cad4a78aa..b7cd65e19 100644 --- a/src/ir/utils.h +++ b/src/ir/utils.h @@ -119,6 +119,10 @@ struct ReFinalize : public WalkerPass<PostWalker<ReFinalize, OverriddenVisitor<ReFinalize>>> { bool isFunctionParallel() override { return true; } + // Re-running finalize() does not change the types of locals, so validation is + // preserved. + bool requiresNonNullableLocalFixups() override { return false; } + Pass* create() override { return new ReFinalize; } ReFinalize() { name = "refinalize"; } diff --git a/src/pass.h b/src/pass.h index 924d608b9..6769c91ee 100644 --- a/src/pass.h +++ b/src/pass.h @@ -386,6 +386,15 @@ public: // for. This is used to issue a proper warning about that. virtual bool invalidatesDWARF() { return false; } + // Whether this pass modifies Binaryen IR in ways that may require fixups for + // non-nullable locals to validate according to the wasm spec. If the pass + // adds locals not in that form, or moves code around in ways that might break + // that validation, this must return true. In that case the pass runner will + // automatically run the necessary fixups afterwards. + // + // For more details see the LocalStructuralDominance class. + virtual bool requiresNonNullableLocalFixups() { return true; } + std::string name; protected: diff --git a/src/passes/CoalesceLocals.cpp b/src/passes/CoalesceLocals.cpp index ba9b87527..edf142039 100644 --- a/src/passes/CoalesceLocals.cpp +++ b/src/passes/CoalesceLocals.cpp @@ -526,7 +526,25 @@ void CoalesceLocals::applyIndices(std::vector<Index>& indices, continue; } } - // remove ineffective actions + + // Remove ineffective actions, that is, dead stores. + // + // Note that this may have downsides for non-nullable locals: + // + // x = whatever; // dead set for validation + // if (..) { + // x = value1; + // } else { + // x = value2; + // } + // + // The dead set ensures validation, at the cost of extra code size and + // slower speed in some tiers (the optimizing tier, at least, will + // remove such dead sets anyhow). In theory keeping such a dead set may + // be worthwhile, as it may save code size (by keeping the local + // non-nullable and avoiding ref.as_non_nulls later). But the tradeoff + // here isn't clear, so do the simple thing for now and remove all dead + // sets. if (!action.effective) { // value may have no side effects, further optimizations can eliminate // it diff --git a/src/passes/CodePushing.cpp b/src/passes/CodePushing.cpp index 29a3ae743..682f025c8 100644 --- a/src/passes/CodePushing.cpp +++ b/src/passes/CodePushing.cpp @@ -234,6 +234,11 @@ private: struct CodePushing : public WalkerPass<PostWalker<CodePushing>> { bool isFunctionParallel() override { return true; } + // This pass moves code forward in blocks, but a local.set would not be moved + // after a local.get with the same index (effects prevent breaking things that + // way), so validation will be preserved. + bool requiresNonNullableLocalFixups() override { return false; } + Pass* create() override { return new CodePushing; } LocalAnalyzer analyzer; diff --git a/src/passes/ConstantFieldPropagation.cpp b/src/passes/ConstantFieldPropagation.cpp index d2b08ea30..0ec889e36 100644 --- a/src/passes/ConstantFieldPropagation.cpp +++ b/src/passes/ConstantFieldPropagation.cpp @@ -52,6 +52,9 @@ using PCVFunctionStructValuesMap = struct FunctionOptimizer : public WalkerPass<PostWalker<FunctionOptimizer>> { bool isFunctionParallel() override { return true; } + // Only modifies struct.get operations. + bool requiresNonNullableLocalFixups() override { return false; } + Pass* create() override { return new FunctionOptimizer(infos); } FunctionOptimizer(PCVStructValuesMap& infos) : infos(infos) {} @@ -175,6 +178,9 @@ struct PCVScanner }; struct ConstantFieldPropagation : public Pass { + // Only modifies struct.get operations. + bool requiresNonNullableLocalFixups() override { return false; } + void run(PassRunner* runner, Module* module) override { if (!module->features.hasGC()) { return; diff --git a/src/passes/DeadCodeElimination.cpp b/src/passes/DeadCodeElimination.cpp index c30da5428..caafb755d 100644 --- a/src/passes/DeadCodeElimination.cpp +++ b/src/passes/DeadCodeElimination.cpp @@ -44,6 +44,10 @@ struct DeadCodeElimination UnifiedExpressionVisitor<DeadCodeElimination>>> { bool isFunctionParallel() override { return true; } + // This pass removes dead code, which can only help validation (a dead + // local.get might have prevented validation). + bool requiresNonNullableLocalFixups() override { return false; } + Pass* create() override { return new DeadCodeElimination; } // as we remove code, we must keep the types of other nodes valid diff --git a/src/passes/Directize.cpp b/src/passes/Directize.cpp index ba5280d65..af020aca6 100644 --- a/src/passes/Directize.cpp +++ b/src/passes/Directize.cpp @@ -34,7 +34,6 @@ #include "call-utils.h" #include "ir/table-utils.h" -#include "ir/type-updating.h" #include "ir/utils.h" #include "pass.h" #include "wasm-builder.h" @@ -107,7 +106,6 @@ struct FunctionDirectizer : public WalkerPass<PostWalker<FunctionDirectizer>> { WalkerPass<PostWalker<FunctionDirectizer>>::doWalkFunction(func); if (changedTypes) { ReFinalize().walkFunctionInModule(func, getModule()); - TypeUpdating::handleNonDefaultableLocals(func, *getModule()); } } diff --git a/src/passes/DuplicateFunctionElimination.cpp b/src/passes/DuplicateFunctionElimination.cpp index 2e8c83cdd..2ebdca4ba 100644 --- a/src/passes/DuplicateFunctionElimination.cpp +++ b/src/passes/DuplicateFunctionElimination.cpp @@ -34,6 +34,9 @@ struct DuplicateFunctionElimination : public Pass { // FIXME Merge DWARF info bool invalidatesDWARF() override { return true; } + // This pass merges functions but does not alter their contents. + bool requiresNonNullableLocalFixups() override { return false; } + void run(PassRunner* runner, Module* module) override { // Multiple iterations may be necessary: A and B may be identical only after // we see the functions C1 and C2 that they call are in fact identical. diff --git a/src/passes/DuplicateImportElimination.cpp b/src/passes/DuplicateImportElimination.cpp index faf2bb776..1a0319e3a 100644 --- a/src/passes/DuplicateImportElimination.cpp +++ b/src/passes/DuplicateImportElimination.cpp @@ -28,6 +28,9 @@ namespace wasm { struct DuplicateImportElimination : public Pass { + // This pass does not alter function contents. + bool requiresNonNullableLocalFixups() override { return false; } + void run(PassRunner* runner, Module* module) override { ImportInfo imports(*module); std::map<Name, Name> replacements; diff --git a/src/passes/Flatten.cpp b/src/passes/Flatten.cpp index be43e57f2..771183d2c 100644 --- a/src/passes/Flatten.cpp +++ b/src/passes/Flatten.cpp @@ -44,7 +44,6 @@ #include <ir/eh-utils.h> #include <ir/flat.h> #include <ir/properties.h> -#include <ir/type-updating.h> #include <ir/utils.h> #include <pass.h> #include <wasm-builder.h> @@ -368,17 +367,6 @@ struct Flatten } // the body may have preludes curr->body = getPreludesWithExpression(originalBody, curr->body); - // New locals we added may be non-nullable. - TypeUpdating::handleNonDefaultableLocals(curr, *getModule()); - // We cannot handle non-nullable tuples currently, see the comment at the - // top of the file. - for (auto type : curr->vars) { - if (!type.isDefaultable()) { - Fatal() << "Flatten was forced to add a local of a type it cannot " - "handle yet: " - << type; - } - } // Flatten can generate blocks within 'catch', making pops invalid. Fix them // up. diff --git a/src/passes/GlobalRefining.cpp b/src/passes/GlobalRefining.cpp index 6f2f19842..626fbaeb5 100644 --- a/src/passes/GlobalRefining.cpp +++ b/src/passes/GlobalRefining.cpp @@ -31,6 +31,9 @@ namespace wasm { namespace { struct GlobalRefining : public Pass { + // Only modifies globals and global.get operations. + bool requiresNonNullableLocalFixups() override { return false; } + void run(PassRunner* runner, Module* module) override { if (!module->features.hasGC()) { return; @@ -102,6 +105,9 @@ struct GlobalRefining : public Pass { struct GetUpdater : public WalkerPass<PostWalker<GetUpdater>> { bool isFunctionParallel() override { return true; } + // Only modifies global.get operations. + bool requiresNonNullableLocalFixups() override { return false; } + GlobalRefining& parent; Module& wasm; diff --git a/src/passes/GlobalStructInference.cpp b/src/passes/GlobalStructInference.cpp index b2717b850..e2b3fa0c9 100644 --- a/src/passes/GlobalStructInference.cpp +++ b/src/passes/GlobalStructInference.cpp @@ -57,6 +57,9 @@ namespace wasm { namespace { struct GlobalStructInference : public Pass { + // Only modifies struct.get operations. + bool requiresNonNullableLocalFixups() override { return false; } + // Maps optimizable struct types to the globals whose init is a struct.new of // them. If a global is not present here, it cannot be optimized. std::unordered_map<HeapType, std::vector<Name>> typeGlobals; diff --git a/src/passes/GlobalTypeOptimization.cpp b/src/passes/GlobalTypeOptimization.cpp index 2c0799874..dad54d116 100644 --- a/src/passes/GlobalTypeOptimization.cpp +++ b/src/passes/GlobalTypeOptimization.cpp @@ -366,7 +366,6 @@ struct GlobalTypeOptimization : public Pass { block->list.push_back(curr); block->finalize(curr->type); replaceCurrent(block); - addedLocals = true; } // Remove the unneeded operands. @@ -405,7 +404,6 @@ struct GlobalTypeOptimization : public Pass { getPassOptions()); replaceCurrent( builder.makeDrop(builder.makeRefAs(RefAsNonNull, flipped))); - addedLocals = true; } } @@ -420,15 +418,7 @@ struct GlobalTypeOptimization : public Pass { curr->index = newIndex; } - void visitFunction(Function* curr) { - if (addedLocals) { - TypeUpdating::handleNonDefaultableLocals(curr, *getModule()); - } - } - private: - bool addedLocals = false; - Index getNewIndex(HeapType type, Index index) { auto iter = parent.indexesAfterRemovals.find(type); if (iter == parent.indexesAfterRemovals.end()) { diff --git a/src/passes/Heap2Local.cpp b/src/passes/Heap2Local.cpp index 86235b001..104a5bbcd 100644 --- a/src/passes/Heap2Local.cpp +++ b/src/passes/Heap2Local.cpp @@ -181,8 +181,6 @@ struct Heap2LocalOptimizer { Parents parents; BranchUtils::BranchTargets branchTargets; - bool optimized = false; - Heap2LocalOptimizer(Function* func, Module* module, const PassOptions& passOptions) @@ -203,9 +201,7 @@ struct Heap2LocalOptimizer { continue; } - if (convertToLocals(allocation)) { - optimized = true; - } + convertToLocals(allocation); } } @@ -473,7 +469,7 @@ struct Heap2LocalOptimizer { // Analyze an allocation to see if we can convert it from a heap allocation to // locals. - bool convertToLocals(StructNew* allocation) { + void convertToLocals(StructNew* allocation) { Rewriter rewriter(allocation, func, module); // A queue of flows from children to parents. When something is in the queue @@ -502,13 +498,13 @@ struct Heap2LocalOptimizer { // different call to this function and use a different queue (any overlap // between calls would prove non-exclusivity). if (!seen.emplace(parent).second) { - return false; + return; } switch (getParentChildInteraction(parent, child)) { case ParentChildInteraction::Escapes: { // If the parent may let us escape then we are done. - return false; + return; } case ParentChildInteraction::FullyConsumes: { // If the parent consumes us without letting us escape then all is @@ -524,7 +520,7 @@ struct Heap2LocalOptimizer { case ParentChildInteraction::Mixes: { // Our allocation is not used exclusively via the parent, as other // values are mixed with it. Give up. - return false; + return; } } @@ -558,13 +554,11 @@ struct Heap2LocalOptimizer { // We finished the loop over the flows. Do the final checks. if (!getsAreExclusiveToSets(rewriter.sets)) { - return false; + return; } // We can do it, hurray! rewriter.applyOptimization(); - - return true; } ParentChildInteraction getParentChildInteraction(Expression* parent, @@ -750,9 +744,7 @@ struct Heap2Local : public WalkerPass<PostWalker<Heap2Local>> { // vacuum, in particular, to optimize such nested allocations. // TODO Consider running multiple iterations here, and running vacuum in // between them. - if (Heap2LocalOptimizer(func, getModule(), getPassOptions()).optimized) { - TypeUpdating::handleNonDefaultableLocals(func, *getModule()); - } + Heap2LocalOptimizer(func, getModule(), getPassOptions()); } }; diff --git a/src/passes/LocalCSE.cpp b/src/passes/LocalCSE.cpp index 4728f189a..e777241a4 100644 --- a/src/passes/LocalCSE.cpp +++ b/src/passes/LocalCSE.cpp @@ -549,8 +549,6 @@ struct LocalCSE : public WalkerPass<PostWalker<LocalCSE>> { Applier applier(requestInfos); applier.walkFunctionInModule(func, getModule()); - - TypeUpdating::handleNonDefaultableLocals(func, *getModule()); } }; diff --git a/src/passes/LocalSubtyping.cpp b/src/passes/LocalSubtyping.cpp index b6e94b771..31e689075 100644 --- a/src/passes/LocalSubtyping.cpp +++ b/src/passes/LocalSubtyping.cpp @@ -25,6 +25,7 @@ #include <ir/find_all.h> #include <ir/linear-execution.h> #include <ir/local-graph.h> +#include <ir/local-structural-dominance.h> #include <ir/lubs.h> #include <ir/utils.h> #include <pass.h> @@ -36,6 +37,10 @@ namespace wasm { struct LocalSubtyping : public WalkerPass<PostWalker<LocalSubtyping>> { bool isFunctionParallel() override { return true; } + // This pass carefully avoids breaking validation by only refining a local's + // type to be non-nullable if it would validate. + bool requiresNonNullableLocalFixups() override { return false; } + Pass* create() override { return new LocalSubtyping(); } void doWalkFunction(Function* func) { @@ -68,24 +73,30 @@ struct LocalSubtyping : public WalkerPass<PostWalker<LocalSubtyping>> { } } - // Find which vars use the default value, if we allow non-nullable locals. - // - // If that feature is not enabled, then we can safely assume that the - // default is never used - the default would be a null value, and the type - // of the null does not really matter as all nulls compare equally, so we do - // not need to worry. - std::unordered_set<Index> usesDefault; + // Find which vars can be non-nullable. + std::unordered_set<Index> cannotBeNonNullable; if (getModule()->features.hasGCNNLocals()) { + // If the feature is enabled then the only constraint is being able to + // read the default value - if it is readable, the local cannot become + // non-nullable. for (auto& [get, sets] : localGraph.getSetses) { auto index = get->index; if (func->isVar(index) && std::any_of(sets.begin(), sets.end(), [&](LocalSet* set) { return set == nullptr; })) { - usesDefault.insert(index); + cannotBeNonNullable.insert(index); } } + } else { + // Without GCNNLocals, validation rules follow the spec rules: all gets + // must be dominated structurally by sets, for the local to be non- + // nullable. + LocalStructuralDominance info(func, *getModule()); + for (auto index : info.nonDominatingIndices) { + cannotBeNonNullable.insert(index); + } } auto varBase = func->getVarIndexBase(); @@ -136,10 +147,7 @@ struct LocalSubtyping : public WalkerPass<PostWalker<LocalSubtyping>> { // Remove non-nullability if we disallow that in locals. if (newType.isNonNullable()) { - // As mentioned earlier, even if we allow non-nullability, there may - // be a problem if the default value - a null - is used. In that case, - // remove non-nullability as well. - if (!getModule()->features.hasGCNNLocals() || usesDefault.count(i)) { + if (cannotBeNonNullable.count(i)) { newType = Type(newType.getHeapType(), Nullable); } } else if (!newType.isDefaultable()) { diff --git a/src/passes/MemoryPacking.cpp b/src/passes/MemoryPacking.cpp index cd4a6698d..0f2cf6f14 100644 --- a/src/passes/MemoryPacking.cpp +++ b/src/passes/MemoryPacking.cpp @@ -95,6 +95,10 @@ makeGtShiftedMemorySize(Builder& builder, Module& module, MemoryInit* curr) { } // anonymous namespace struct MemoryPacking : public Pass { + // This pass operates on linear memory, and does not affect reference locals. + // TODO: don't run at all if the module has no memories + bool requiresNonNullableLocalFixups() override { return false; } + void run(PassRunner* runner, Module* module) override; bool canOptimize(std::vector<std::unique_ptr<Memory>>& memories, std::vector<std::unique_ptr<DataSegment>>& dataSegments, @@ -377,6 +381,10 @@ void MemoryPacking::calculateRanges(const std::unique_ptr<DataSegment>& segment, void MemoryPacking::optimizeBulkMemoryOps(PassRunner* runner, Module* module) { struct Optimizer : WalkerPass<PostWalker<Optimizer>> { bool isFunctionParallel() override { return true; } + + // This operates on linear memory, and does not affect reference locals. + bool requiresNonNullableLocalFixups() override { return false; } + Pass* create() override { return new Optimizer; } bool needsRefinalizing; @@ -777,6 +785,9 @@ void MemoryPacking::replaceBulkMemoryOps(PassRunner* runner, struct Replacer : WalkerPass<PostWalker<Replacer>> { bool isFunctionParallel() override { return true; } + // This operates on linear memory, and does not affect reference locals. + bool requiresNonNullableLocalFixups() override { return false; } + Replacements& replacements; Replacer(Replacements& replacements) : replacements(replacements){}; diff --git a/src/passes/MinifyImportsAndExports.cpp b/src/passes/MinifyImportsAndExports.cpp index 02675e49b..3e919c799 100644 --- a/src/passes/MinifyImportsAndExports.cpp +++ b/src/passes/MinifyImportsAndExports.cpp @@ -46,6 +46,9 @@ namespace wasm { struct MinifyImportsAndExports : public Pass { + // This operates on import/export names only. + bool requiresNonNullableLocalFixups() override { return false; } + bool minifyExports, minifyModules; public: diff --git a/src/passes/NameTypes.cpp b/src/passes/NameTypes.cpp index b855e4c0d..3ad35fa1d 100644 --- a/src/passes/NameTypes.cpp +++ b/src/passes/NameTypes.cpp @@ -28,6 +28,8 @@ namespace wasm { static const size_t NameLenLimit = 20; struct NameTypes : public Pass { + bool requiresNonNullableLocalFixups() override { return false; } + void run(PassRunner* runner, Module* module) override { // Find all the types. std::vector<HeapType> types = ModuleUtils::collectHeapTypes(*module); diff --git a/src/passes/OptimizeAddedConstants.cpp b/src/passes/OptimizeAddedConstants.cpp index 0af23c1cc..8256169c1 100644 --- a/src/passes/OptimizeAddedConstants.cpp +++ b/src/passes/OptimizeAddedConstants.cpp @@ -242,6 +242,9 @@ struct OptimizeAddedConstants UnifiedExpressionVisitor<OptimizeAddedConstants>>> { bool isFunctionParallel() override { return true; } + // This pass operates on linear memory, and does not affect reference locals. + bool requiresNonNullableLocalFixups() override { return false; } + bool propagate; OptimizeAddedConstants(bool propagate) : propagate(propagate) {} diff --git a/src/passes/OptimizeInstructions.cpp b/src/passes/OptimizeInstructions.cpp index 9379d8588..42d92751f 100644 --- a/src/passes/OptimizeInstructions.cpp +++ b/src/passes/OptimizeInstructions.cpp @@ -238,9 +238,6 @@ struct OptimizeInstructions optimizer.walkFunction(func); } - // Some patterns create locals (like when we use getResultOfFirst), which we - // may need to fix up. - TypeUpdating::handleNonDefaultableLocals(func, *getModule()); // Some patterns create blocks that can interfere 'catch' and 'pop', nesting // the 'pop' into a block making it invalid. EHUtils::handleBlockNestedPops(func, *getModule()); diff --git a/src/passes/RemoveUnusedModuleElements.cpp b/src/passes/RemoveUnusedModuleElements.cpp index 1b1174745..139f6f655 100644 --- a/src/passes/RemoveUnusedModuleElements.cpp +++ b/src/passes/RemoveUnusedModuleElements.cpp @@ -230,6 +230,10 @@ struct ReachabilityAnalyzer : public PostWalker<ReachabilityAnalyzer> { }; struct RemoveUnusedModuleElements : public Pass { + // This pass only removes module elements, it never modifies function + // contents. + bool requiresNonNullableLocalFixups() override { return false; } + bool rootAllFunctions; RemoveUnusedModuleElements(bool rootAllFunctions) diff --git a/src/passes/RemoveUnusedNames.cpp b/src/passes/RemoveUnusedNames.cpp index a08cb5eda..4c74245f0 100644 --- a/src/passes/RemoveUnusedNames.cpp +++ b/src/passes/RemoveUnusedNames.cpp @@ -31,6 +31,10 @@ struct RemoveUnusedNames UnifiedExpressionVisitor<RemoveUnusedNames>>> { bool isFunctionParallel() override { return true; } + // This pass only removes names, which can only help validation (as blocks + // without names are ignored, see the README section on non-nullable locals). + bool requiresNonNullableLocalFixups() override { return false; } + Pass* create() override { return new RemoveUnusedNames; } // We maintain a list of branches that we saw in children, then when we reach diff --git a/src/passes/ReorderFunctions.cpp b/src/passes/ReorderFunctions.cpp index 7d2e7fb53..6f87e74a6 100644 --- a/src/passes/ReorderFunctions.cpp +++ b/src/passes/ReorderFunctions.cpp @@ -57,6 +57,9 @@ private: }; struct ReorderFunctions : public Pass { + // Only reorders functions, does not change their contents. + bool requiresNonNullableLocalFixups() override { return false; } + void run(PassRunner* runner, Module* module) override { NameCountMap counts; // fill in info, as we operate on it in parallel (each function to its own diff --git a/src/passes/ReorderLocals.cpp b/src/passes/ReorderLocals.cpp index 7b2de0d70..ce06afd68 100644 --- a/src/passes/ReorderLocals.cpp +++ b/src/passes/ReorderLocals.cpp @@ -32,6 +32,9 @@ namespace wasm { struct ReorderLocals : public WalkerPass<PostWalker<ReorderLocals>> { bool isFunctionParallel() override { return true; } + // Sorting and removing unused locals cannot affect validation. + bool requiresNonNullableLocalFixups() override { return false; } + Pass* create() override { return new ReorderLocals; } // local index => times it is used diff --git a/src/passes/SSAify.cpp b/src/passes/SSAify.cpp index 07867b32d..089def301 100644 --- a/src/passes/SSAify.cpp +++ b/src/passes/SSAify.cpp @@ -53,7 +53,6 @@ #include "ir/find_all.h" #include "ir/literal-utils.h" #include "ir/local-graph.h" -#include "ir/type-updating.h" #include "pass.h" #include "support/permutations.h" #include "wasm-builder.h" @@ -99,8 +98,6 @@ struct SSAify : public Pass { computeGetsAndPhis(graph); // add prepends to function addPrepends(); - // Handle non-nullability in new locals we added. - TypeUpdating::handleNonDefaultableLocals(func, *module); } void createNewIndexes(LocalGraph& graph) { @@ -140,10 +137,14 @@ struct SSAify : public Pass { // no set, assign param or zero if (func->isParam(get->index)) { // leave it, it's fine - } else { + } else if (LiteralUtils::canMakeZero(get->type)) { // zero it out (*graph.locations[get]) = LiteralUtils::makeZero(get->type, *module); + } else { + // No zero exists here, so this is a nondefaultable type. The + // default won't be used anyhow, so this value does not really + // matter and we have nothing to do. } } continue; diff --git a/src/passes/SetGlobals.cpp b/src/passes/SetGlobals.cpp index 8a147665c..4109eb69b 100644 --- a/src/passes/SetGlobals.cpp +++ b/src/passes/SetGlobals.cpp @@ -25,6 +25,9 @@ namespace wasm { struct SetGlobals : public Pass { + // Only modifies globals. + bool requiresNonNullableLocalFixups() override { return false; } + void run(PassRunner* runner, Module* module) override { Name input = runner->options.getArgument( "set-globals", diff --git a/src/passes/SignatureRefining.cpp b/src/passes/SignatureRefining.cpp index 11df83f4d..d00626fca 100644 --- a/src/passes/SignatureRefining.cpp +++ b/src/passes/SignatureRefining.cpp @@ -41,6 +41,9 @@ namespace wasm { namespace { struct SignatureRefining : public Pass { + // Only changes heap types and parameter types (but not locals). + bool requiresNonNullableLocalFixups() override { return false; } + // Maps each heap type to the possible refinement of the types in their // signatures. We will fill this during analysis and then use it while doing // an update of the types. If a type has no improvement that we can find, it @@ -241,6 +244,10 @@ struct SignatureRefining : public Pass { struct CodeUpdater : public WalkerPass<PostWalker<CodeUpdater>> { bool isFunctionParallel() override { return true; } + // Updating parameter types cannot affect validation (only updating var + // types types might). + bool requiresNonNullableLocalFixups() override { return false; } + SignatureRefining& parent; Module& wasm; diff --git a/src/passes/SimplifyLocals.cpp b/src/passes/SimplifyLocals.cpp index ee9e43b0b..6250b1321 100644 --- a/src/passes/SimplifyLocals.cpp +++ b/src/passes/SimplifyLocals.cpp @@ -331,50 +331,6 @@ struct SimplifyLocals invalidated.push_back(index); continue; } - - // Non-nullable local.sets cannot be moved into a try, as that may - // change dominance from the perspective of the spec - // - // (local.set $x X) - // (try - // .. - // (Y - // (local.get $x)) - // (catch - // (Z - // (local.get $x))) - // - // => - // - // (try - // .. - // (Y - // (local.tee $x X)) - // (catch - // (Z - // (local.get $x))) - // - // After sinking the set, the tee does not dominate the get in the - // catch, at least not in the simple way the spec defines it, see - // https://github.com/WebAssembly/function-references/issues/44#issuecomment-1083146887 - // We have more refined information about control flow and dominance - // than the spec, and so we would see if ".." can throw or not (only if - // it can throw is there a branch to the catch, which can change - // dominance). To stay compliant with the spec, however, we must not - // move code regardless of whether ".." can throw - we must simply keep - // the set outside of the try. - // - // The problem described can also occur on the *value* and not the set - // itself. For example, |X| above could be a local.set of a non-nullable - // local. For that reason we must scan it all. - if (self->getModule()->features.hasGCNNLocals()) { - for (auto* set : FindAll<LocalSet>(*info.item).list) { - if (self->getFunction()->getLocalType(set->index).isNonNullable()) { - invalidated.push_back(index); - break; - } - } - } } for (auto index : invalidated) { self->sinkables.erase(index); @@ -804,7 +760,48 @@ struct SimplifyLocals if (sinkables.empty()) { return; } + + // Check if the type makes sense. A non-nullable local might be dangerous + // here, as creating new local.gets for such locals is risky: + // + // (func $silly + // (local $x (ref $T)) + // (if + // (condition) + // (local.set $x ..) + // ) + // ) + // + // That local is silly as the write is never read. If we optimize it and add + // a local.get, however, then we'd no longer validate (as no set would + // dominate that new get in the if's else arm). Fixups would add a + // ref.as_non_null around the local.get, which will then trap at runtime: + // + // (func $silly + // (local $x (ref null $T)) + // (local.set $x + // (if + // (condition) + // (..) + // (ref.as_non_null + // (local.get $x) + // ) + // ) + // ) + // ) + // + // In other words, local.get is not necessarily free of effects if the local + // is non-nullable - it must have been set already. We could check that + // here, but running that linear-time check may not be worth it as this + // optimization is fairly minor, so just skip the non-nullable case. + // + // TODO investigate more Index goodIndex = sinkables.begin()->first; + auto localType = this->getFunction()->getLocalType(goodIndex); + if (localType.isNonNullable()) { + return; + } + // Ensure we have a place to write the return values for, if not, we // need another cycle. auto* ifTrueBlock = iff->ifTrue->dynCast<Block>(); @@ -813,6 +810,9 @@ struct SimplifyLocals ifsToEnlarge.push_back(iff); return; } + + // We can optimize! + // Update the ifTrue side. Builder builder(*this->getModule()); auto** item = sinkables.at(goodIndex).item; @@ -822,8 +822,7 @@ struct SimplifyLocals ifTrueBlock->finalize(); assert(ifTrueBlock->type != Type::none); // Update the ifFalse side. - iff->ifFalse = builder.makeLocalGet( - set->index, this->getFunction()->getLocalType(set->index)); + iff->ifFalse = builder.makeLocalGet(set->index, localType); iff->finalize(); // update type // Update the get count. getCounter.num[set->index]++; diff --git a/src/passes/StackCheck.cpp b/src/passes/StackCheck.cpp index fd7ed6c0f..11ab1fe4e 100644 --- a/src/passes/StackCheck.cpp +++ b/src/passes/StackCheck.cpp @@ -67,6 +67,9 @@ struct EnforceStackLimits : public WalkerPass<PostWalker<EnforceStackLimits>> { bool isFunctionParallel() override { return true; } + // Only affects linear memory operations. + bool requiresNonNullableLocalFixups() override { return false; } + Pass* create() override { return new EnforceStackLimits( stackPointer, stackBase, stackLimit, builder, handler); diff --git a/src/passes/StackIR.cpp b/src/passes/StackIR.cpp index 84e19428d..e896af0f5 100644 --- a/src/passes/StackIR.cpp +++ b/src/passes/StackIR.cpp @@ -69,41 +69,7 @@ public: if (passOptions.optimizeLevel >= 3 || passOptions.shrinkLevel >= 1) { local2Stack(); } - // Removing unneeded blocks is dangerous with GC, as if we do this: - // - // (call - // (struct.new) - // (block - // (nop) - // (i32) - // ) - // ) - // === remove inner block ==> - // (call - // (struct.new) - // (nop) - // (i32) - // ) - // - // Then we end up with a nop that forces us to emit this during load: - // - // (call - // (block - // (local.set - // (struct.new) - // ) - // (nop) - // (local.get) - // ) - // (i32) - // ) - // - // However, that is not valid as an non-nullable reference cannot be set to - // a local. TODO: double check that this is still true now that we don't - // have RTTs. - if (!features.hasGC()) { - removeUnneededBlocks(); - } + removeUnneededBlocks(); dce(); } diff --git a/src/passes/Strip.cpp b/src/passes/Strip.cpp index 6377d2367..7c9f61061 100644 --- a/src/passes/Strip.cpp +++ b/src/passes/Strip.cpp @@ -28,6 +28,8 @@ namespace wasm { struct Strip : public Pass { + bool requiresNonNullableLocalFixups() override { return false; } + // A function that returns true if the method should be removed. typedef std::function<bool(UserSection&)> Decider; Decider decider; diff --git a/src/passes/StripTargetFeatures.cpp b/src/passes/StripTargetFeatures.cpp index cb5e51f08..878004a98 100644 --- a/src/passes/StripTargetFeatures.cpp +++ b/src/passes/StripTargetFeatures.cpp @@ -19,6 +19,8 @@ namespace wasm { struct StripTargetFeatures : public Pass { + bool requiresNonNullableLocalFixups() override { return false; } + bool isStripped = false; StripTargetFeatures(bool isStripped) : isStripped(isStripped) {} void run(PassRunner* runner, Module* module) override { diff --git a/src/passes/TypeRefining.cpp b/src/passes/TypeRefining.cpp index ac95d01fe..3d3f981db 100644 --- a/src/passes/TypeRefining.cpp +++ b/src/passes/TypeRefining.cpp @@ -93,6 +93,9 @@ struct FieldInfoScanner }; struct TypeRefining : public Pass { + // Only affects GC type declarations and struct.gets. + bool requiresNonNullableLocalFixups() override { return false; } + StructUtils::StructValuesMap<FieldInfo> finalInfos; void run(PassRunner* runner, Module* module) override { @@ -235,6 +238,9 @@ struct TypeRefining : public Pass { struct ReadUpdater : public WalkerPass<PostWalker<ReadUpdater>> { bool isFunctionParallel() override { return true; } + // Only affects struct.gets. + bool requiresNonNullableLocalFixups() override { return false; } + TypeRefining& parent; ReadUpdater(TypeRefining& parent) : parent(parent) {} diff --git a/src/passes/pass.cpp b/src/passes/pass.cpp index 570cd8610..f55f5018e 100644 --- a/src/passes/pass.cpp +++ b/src/passes/pass.cpp @@ -23,6 +23,7 @@ #include "ir/hashed.h" #include "ir/module-utils.h" +#include "ir/type-updating.h" #include "pass.h" #include "passes/passes.h" #include "support/colors.h" @@ -936,16 +937,29 @@ void PassRunner::runPassOnFunction(Pass* pass, Function* func) { } void PassRunner::handleAfterEffects(Pass* pass, Function* func) { - if (pass->modifiesBinaryenIR()) { - // If Binaryen IR is modified, Stack IR must be cleared - it would - // be out of sync in a potentially dangerous way. - if (func) { - func->stackIR.reset(nullptr); - } else { - for (auto& func : wasm->functions) { - func->stackIR.reset(nullptr); - } + if (!pass->modifiesBinaryenIR()) { + return; + } + + // Binaryen IR is modified, so we may have work here. + + if (!func) { + // If no function is provided, then this is not a function-parallel pass, + // and it may have operated on any of the functions in theory, so run on + // them all. + assert(!pass->isFunctionParallel()); + for (auto& func : wasm->functions) { + handleAfterEffects(pass, func.get()); } + return; + } + + // If Binaryen IR is modified, Stack IR must be cleared - it would + // be out of sync in a potentially dangerous way. + func->stackIR.reset(nullptr); + + if (pass->requiresNonNullableLocalFixups()) { + TypeUpdating::handleNonDefaultableLocals(func, *wasm); } } diff --git a/src/tools/fuzzing.h b/src/tools/fuzzing.h index 47d55cfef..aff2a0aa3 100644 --- a/src/tools/fuzzing.h +++ b/src/tools/fuzzing.h @@ -76,8 +76,9 @@ public: void build(); -private: Module& wasm; + +private: Builder builder; Random random; diff --git a/src/tools/fuzzing/fuzzing.cpp b/src/tools/fuzzing/fuzzing.cpp index 828f80693..0f59bb635 100644 --- a/src/tools/fuzzing/fuzzing.cpp +++ b/src/tools/fuzzing/fuzzing.cpp @@ -15,6 +15,7 @@ */ #include "tools/fuzzing.h" +#include "ir/type-updating.h" #include "tools/fuzzing/heap-types.h" #include "tools/fuzzing/parameters.h" @@ -461,6 +462,9 @@ TranslateToFuzzReader::FunctionCreationContext::~FunctionCreationContext() { assert(breakableStack.empty()); assert(hangStack.empty()); parent.funcContext = nullptr; + + // We must ensure non-nullable locals validate. + TypeUpdating::handleNonDefaultableLocals(func, parent.wasm); } Expression* TranslateToFuzzReader::makeHangLimitCheck() { diff --git a/src/wasm/wasm-validator.cpp b/src/wasm/wasm-validator.cpp index 75cbcf53a..c1a8eea7f 100644 --- a/src/wasm/wasm-validator.cpp +++ b/src/wasm/wasm-validator.cpp @@ -24,6 +24,7 @@ #include "ir/global-utils.h" #include "ir/intrinsics.h" #include "ir/local-graph.h" +#include "ir/local-structural-dominance.h" #include "ir/module-utils.h" #include "ir/stack-utils.h" #include "ir/utils.h" @@ -2761,8 +2762,6 @@ void FunctionValidator::visitFunction(Function* curr) { } for (const auto& var : curr->vars) { features |= var.getFeatures(); - bool valid = getModule()->features.hasGCNNLocals() || var.isDefaultable(); - shouldBeTrue(valid, var, "vars must be defaultable"); } shouldBeTrue(features <= getModule()->features, curr->name, @@ -2796,32 +2795,43 @@ void FunctionValidator::visitFunction(Function* curr) { shouldBeTrue(seen.insert(name).second, name, "local names must be unique"); } - if (getModule()->features.hasGCNNLocals()) { - // If we have non-nullable locals, verify that no local.get can read a null - // default value. - // TODO: this can be fairly slow due to the LocalGraph. writing more code to - // do a more specific analysis (we don't need to know all sets, just - // if there is a set of a null default value that is read) could be a - // lot faster. - bool hasNNLocals = false; - for (const auto& var : curr->vars) { - if (var.isNonNullable()) { - hasNNLocals = true; - break; + if (getModule()->features.hasGC()) { + // If we have non-nullable locals, verify that local.get are valid. + if (!getModule()->features.hasGCNNLocals()) { + // Without the special GCNNLocals feature, we implement the spec rules, + // that is, a set allows gets until the end of the block. + LocalStructuralDominance info(curr, *getModule()); + for (auto index : info.nonDominatingIndices) { + shouldBeTrue(!curr->getLocalType(index).isNonNullable(), + index, + "non-nullable local's sets must dominate gets"); } - } - if (hasNNLocals) { - LocalGraph graph(curr); - for (auto& [get, sets] : graph.getSetses) { - auto index = get->index; - // It is always ok to read nullable locals, and it is always ok to read - // params even if they are non-nullable. - if (!curr->getLocalType(index).isNonNullable() || - curr->isParam(index)) { - continue; + } else { + // With the special GCNNLocals feature, we allow gets anywhere, so long as + // we can prove they cannot read the null value. (TODO: remove this once + // the spec is stable). + // + // This is slow, so only do it if we find such locals exist at all. + bool hasNNLocals = false; + for (const auto& var : curr->vars) { + if (!var.isDefaultable()) { + hasNNLocals = true; + break; } - for (auto* set : sets) { - shouldBeTrue(!!set, index, "non-nullable local must not read null"); + } + if (hasNNLocals) { + LocalGraph graph(curr); + for (auto& [get, sets] : graph.getSetses) { + auto index = get->index; + // It is always ok to read nullable locals, and it is always ok to + // read params even if they are non-nullable. + if (curr->getLocalType(index).isDefaultable() || + curr->isParam(index)) { + continue; + } + for (auto* set : sets) { + shouldBeTrue(!!set, index, "non-nullable local must not read null"); + } } } } |