[Wasm GC] Support non-nullable locals in the "1a" form (#4959)

An overview of this is in the README in the diff here (conveniently, it is near the
top of the diff). Basically, we fix up nn locals after each pass, by default. This keeps
things easy to reason about - what validates is what is valid wasm - but there are
some minor nuances as mentioned there, in particular, we ignore nameless blocks
(which are commonly added by various passes; ignoring them means we can keep
more locals non-nullable).

The key addition here is LocalStructuralDominance which checks which local
indexes have the "structural dominance" property of 1a, that is, that each get has
a set in its block or an outer block that precedes it. I optimized that function quite
a lot to reduce the overhead of running that logic after each pass. The overhead
is something like 2% on J2Wasm and 0% on Dart (0%, because in this mode we
shrink code size, so there is less work actually, and it balances out).

Since we run fixups after each pass, this PR removes logic to manually call the
fixup code from various places we used to call it (like eh-utils and various passes).

Various passes are now marked as requiresNonNullableLocalFixups => false.
That lets us skip running the fixups after them, which we normally do automatically.
This helps avoid overhead. Most passes still need the fixups, though - any pass
that adds a local, or a named block, or moves code around, likely does.

This removes a hack in SimplifyLocals that is no longer needed. Before we
worked to avoid moving a set into a try, as it might not validate. Now, we just do it
and let fixups happen automatically if they need to: in the common code they
probably don't, so the extra complexity seems not worth it.

Also removes a hack from StackIR. That hack tried to avoid roundtrip adding a
nondefaultable local. But we have the logic to fix that up now, and opts will
likely keep it non-nullable as well.

Various tests end up updated here because now a local can be non-nullable -
previous fixups are no longer needed.

Note that this doesn't remove the gc-nn-locals feature. That has been useful for
testing, and may still be useful in the future - it basically just allows nn locals in
all positions (that can't read the null default value at the entry). We can consider
removing it separately.

Fixes #4824

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");
+          }
         }
       }
     }