Precompute: Track reference identity (#4243)

Precompute will run the interpreter on struct.new etc. repeatedly,
as it keeps doing so while it propagates constant values around (if one
of the operands to the struct.new becomes constant, that could have
a noticeable effect). But creating new GC data means we lose track of
their identity, and so ref.eq would not work, and we disabled basically
all struct operations. This implements identity tracking so we can start
to optimize there, which is a step towards using it for immutable field
propagation.

To track identity, always store the data representing each struct.new
in the source using the same GCData structure. That keeps identity
consistent no matter how many times we execute.

3 files changed, 610 insertions, 179 deletions

diff --git a/src/passes/Precompute.cpp b/src/passes/Precompute.cpp
index 4209ffbe2..876b09acd 100644
--- a/src/passes/Precompute.cpp
+++ b/src/passes/Precompute.cpp
@@ -40,7 +40,33 @@
 
 namespace wasm {
 
-typedef std::unordered_map<LocalGet*, Literals> GetValues;
+using GetValues = std::unordered_map<LocalGet*, Literals>;
+
+// A map of values on the heap. This maps the expressions that create the
+// heap data (struct.new, array.new, etc.) to the data they are created with.
+// Each such expression gets its own GCData created for it. This allows
+// computing identity between locals referring to the same GCData, by seeing
+// if they point to the same thing.
+//
+// Note that a source expression may create different data each time it is
+// reached in a loop,
+//
+// (loop
+//  (if ..
+//   (local.set $x
+//    (struct.new ..
+//   )
+//  )
+//  ..compare $x to something..
+// )
+//
+// Just like in SSA form, this is not a problem because the loop entry must
+// have a merge, if a value entering the loop might be noticed. In SSA form
+// that means a phi is created, and identity is set there. In our
+// representation, the merge will cause a local.get of $x to have more
+// possible input values than that struct.new, which means we will not infer
+// a value for it, and not attempt to say anything about comparisons of $x.
+using HeapValues = std::unordered_map<Expression*, std::shared_ptr<GCData>>;
 
 // Precomputes an expression. Errors if we hit anything that can't be
 // precomputed. Inherits most of its functionality from
@@ -49,10 +75,14 @@ typedef std::unordered_map<LocalGet*, Literals> GetValues;
 class PrecomputingExpressionRunner
   : public ConstantExpressionRunner<PrecomputingExpressionRunner> {
 
+  using Super = ConstantExpressionRunner<PrecomputingExpressionRunner>;
+
   // Concrete values of gets computed during the pass, which the runner does not
   // know about since it only records values of sets it visits.
   GetValues& getValues;
 
+  HeapValues& heapValues;
+
   // Limit evaluation depth for 2 reasons: first, it is highly unlikely
   // that we can do anything useful to precompute a hugely nested expression
   // (we should succed at smaller parts of it first). Second, a low limit is
@@ -68,6 +98,7 @@ class PrecomputingExpressionRunner
 public:
   PrecomputingExpressionRunner(Module* module,
                                GetValues& getValues,
+                               HeapValues& heapValues,
                                bool replaceExpression)
     : ConstantExpressionRunner<PrecomputingExpressionRunner>(
         module,
@@ -75,7 +106,7 @@ public:
                           : FlagValues::DEFAULT,
         MAX_DEPTH,
         MAX_LOOP_ITERATIONS),
-      getValues(getValues) {}
+      getValues(getValues), heapValues(heapValues) {}
 
   Flow visitLocalGet(LocalGet* curr) {
     auto iter = getValues.find(curr);
@@ -89,16 +120,49 @@ public:
       PrecomputingExpressionRunner>::visitLocalGet(curr);
   }
 
-  // Heap data may be modified in ways we do not see. We would need escape
-  // analysis to avoid that risk. For now, disallow all heap operations.
-  // TODO: immutability might also be good enough
-  Flow visitStructNew(StructNew* curr) { return Flow(NONCONSTANT_FLOW); }
+  // TODO: Use immutability for values
+  Flow visitStructNew(StructNew* curr) {
+    auto flow = Super::visitStructNew(curr);
+    if (flow.breaking()) {
+      return flow;
+    }
+    return getHeapCreationFlow(flow, curr);
+  }
+  Flow visitStructSet(StructSet* curr) { return Flow(NONCONSTANT_FLOW); }
   Flow visitStructGet(StructGet* curr) { return Flow(NONCONSTANT_FLOW); }
-  Flow visitArrayNew(ArrayNew* curr) { return Flow(NONCONSTANT_FLOW); }
-  Flow visitArrayInit(ArrayInit* curr) { return Flow(NONCONSTANT_FLOW); }
+  Flow visitArrayNew(ArrayNew* curr) {
+    auto flow = Super::visitArrayNew(curr);
+    if (flow.breaking()) {
+      return flow;
+    }
+    return getHeapCreationFlow(flow, curr);
+  }
+  Flow visitArrayInit(ArrayInit* curr) {
+    auto flow = Super::visitArrayInit(curr);
+    if (flow.breaking()) {
+      return flow;
+    }
+    return getHeapCreationFlow(flow, curr);
+  }
+  Flow visitArraySet(ArraySet* curr) { return Flow(NONCONSTANT_FLOW); }
   Flow visitArrayGet(ArrayGet* curr) { return Flow(NONCONSTANT_FLOW); }
   Flow visitArrayLen(ArrayLen* curr) { return Flow(NONCONSTANT_FLOW); }
   Flow visitArrayCopy(ArrayCopy* curr) { return Flow(NONCONSTANT_FLOW); }
+
+  // Generates heap info for a heap-allocating expression.
+  template<typename T> Flow getHeapCreationFlow(Flow flow, T* curr) {
+    // We must return a literal that refers to the canonical location for this
+    // source expression, so that each time we compute a specific struct.new
+    // we get the same identity.
+    std::shared_ptr<GCData>& canonical = heapValues[curr];
+    std::shared_ptr<GCData> newGCData = flow.getSingleValue().getGCData();
+    if (!canonical) {
+      canonical = std::make_shared<GCData>(*newGCData);
+    } else {
+      *canonical = *newGCData;
+    }
+    return Literal(canonical, curr->type);
+  }
 };
 
 struct Precompute
@@ -113,6 +177,7 @@ struct Precompute
   Precompute(bool propagate) : propagate(propagate) {}
 
   GetValues getValues;
+  HeapValues heapValues;
 
   void doWalkFunction(Function* func) {
     // Walk the function and precompute things.
@@ -242,9 +307,9 @@ private:
   Flow precomputeExpression(Expression* curr, bool replaceExpression = true) {
     Flow flow;
     try {
-      flow =
-        PrecomputingExpressionRunner(getModule(), getValues, replaceExpression)
-          .visit(curr);
+      flow = PrecomputingExpressionRunner(
+               getModule(), getValues, heapValues, replaceExpression)
+               .visit(curr);
     } catch (PrecomputingExpressionRunner::NonconstantException&) {
       return Flow(NONCONSTANT_FLOW);
     }
@@ -308,10 +373,8 @@ private:
         // repeating side effects if those side effects are expressed *in the
         // value*. A case where that can happen is GC data (each struct.new
         // creates a new, unique struct, even if the data is equal), and so
-        // PrecomputingExpressionRunner will return a nonconstant flow for all
-        // GC heap operations. (We could also have used
-        // Properties::isGenerative here, but that would be less efficient to
-        // re-scan the entire expression.)
+        // PrecomputingExpressionRunner has special logic to make sure that
+        // reference identity is preserved properly.
         //
         // (Other side effects are fine; if an expression does a call and we
         // somehow know the entire expression precomputes to a 42, then we can
diff --git a/test/lit/passes/precompute-gc.wast b/test/lit/passes/precompute-gc.wast
index 44eff1c5f..c12e86635 100644
--- a/test/lit/passes/precompute-gc.wast
+++ b/test/lit/passes/precompute-gc.wast
@@ -5,19 +5,18 @@
 ;; RUN:   | filecheck %s
 
 (module
+ ;; CHECK:      (type $empty (struct ))
+
  ;; CHECK:      (type $struct (struct (field (mut i32))))
  (type $struct (struct (mut i32)))
- ;; CHECK:      (type $B (struct (field (mut f64))))
-
- ;; CHECK:      (type $func-return-i32 (func (result i32)))
-
- ;; CHECK:      (type $empty (struct ))
  (type $empty (struct))
 
  ;; two incompatible struct types
  (type $A (struct (field (mut f32))))
+ ;; CHECK:      (type $B (struct (field (mut f64))))
  (type $B (struct (field (mut f64))))
 
+ ;; CHECK:      (type $func-return-i32 (func (result i32)))
  (type $func-return-i32 (func (result i32)))
 
  ;; CHECK:      (import "fuzzing-support" "log-i32" (func $log (param i32)))
@@ -307,12 +306,9 @@
  ;; CHECK-NEXT:   (local.get $x)
  ;; CHECK-NEXT:  )
  ;; CHECK-NEXT:  (local.set $tempresult
- ;; CHECK-NEXT:   (ref.eq
- ;; CHECK-NEXT:    (local.get $x)
- ;; CHECK-NEXT:    (local.get $y)
- ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:   (i32.const 1)
  ;; CHECK-NEXT:  )
- ;; CHECK-NEXT:  (local.get $tempresult)
+ ;; CHECK-NEXT:  (i32.const 1)
  ;; CHECK-NEXT: )
  (func $new-ref-comparisons (result i32)
   (local $x (ref null $struct))
@@ -327,15 +323,15 @@
   (local.set $y
    (local.get $x)
   )
-  ;; assign the result, so that propagate calculates the ref.eq
+  ;; assign the result, so that propagate calculates the ref.eq. both $x and $y
+  ;; must refer to the same data, so we can precompute a 1 here.
   (local.set $tempresult
    (ref.eq
     (local.get $x)
     (local.get $y)
    )
   )
-  ;; this value could be precomputed in principle, however, we currently do not
-  ;; precompute GC references, and so nothing will be done.
+  ;; and that 1 is propagated to here.
   (local.get $tempresult)
  )
  ;; CHECK:      (func $propagate-equal (result i32)
@@ -351,7 +347,7 @@
  ;; CHECK-NEXT:    (local.get $tempref)
  ;; CHECK-NEXT:   )
  ;; CHECK-NEXT:  )
- ;; CHECK-NEXT:  (local.get $tempresult)
+ ;; CHECK-NEXT:  (i32.const 1)
  ;; CHECK-NEXT: )
  (func $propagate-equal (result i32)
   (local $tempresult i32)
@@ -368,43 +364,417 @@
     (local.get $tempref)
    )
   )
-  ;; this value could be precomputed in principle, however, we currently do not
-  ;; precompute GC references, and so nothing will be done.
+  ;; we can compute a 1 here as the ref.eq compares a struct to itself. note
+  ;; that the ref.eq itself cannot be precomputed away (as it has side effects).
   (local.get $tempresult)
  )
  ;; CHECK:      (func $propagate-unequal (result i32)
  ;; CHECK-NEXT:  (local $tempresult i32)
  ;; CHECK-NEXT:  (local $tempref (ref null $empty))
  ;; CHECK-NEXT:  (local.set $tempresult
+ ;; CHECK-NEXT:   (i32.const 0)
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT:  (i32.const 0)
+ ;; CHECK-NEXT: )
+ (func $propagate-unequal (result i32)
+  (local $tempresult i32)
+  (local $tempref (ref null $empty))
+  ;; assign the result, so that propagate calculates the ref.eq.
+  ;; the structs are different, so we will precompute a 0 here, and as creating
+  ;; heap data does not have side effects, we can in fact replace the ref.eq
+  ;; with that value
+  (local.set $tempresult
+   ;; allocate two different structs
+   (ref.eq
+    (struct.new_with_rtt $empty
+     (rtt.canon $empty)
+    )
+    (struct.new_with_rtt $empty
+     (rtt.canon $empty)
+    )
+   )
+  )
+  (local.get $tempresult)
+ )
+
+ ;; CHECK:      (func $propagate-uncertain-param (param $input (ref $empty)) (result i32)
+ ;; CHECK-NEXT:  (local $tempresult i32)
+ ;; CHECK-NEXT:  (local $tempref (ref null $empty))
+ ;; CHECK-NEXT:  (local.set $tempresult
  ;; CHECK-NEXT:   (ref.eq
  ;; CHECK-NEXT:    (struct.new_default_with_rtt $empty
  ;; CHECK-NEXT:     (rtt.canon $empty)
  ;; CHECK-NEXT:    )
+ ;; CHECK-NEXT:    (local.get $input)
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT:  (local.get $tempresult)
+ ;; CHECK-NEXT: )
+ (func $propagate-uncertain-param (param $input (ref $empty)) (result i32)
+  (local $tempresult i32)
+  (local $tempref (ref null $empty))
+  (local.set $tempresult
+   ;; allocate a struct and compare it to a param, which we know nothing about,
+   ;; so we can infer nothing here at all.
+   (ref.eq
+    (struct.new_with_rtt $empty
+     (rtt.canon $empty)
+    )
+    (local.get $input)
+   )
+  )
+  (local.get $tempresult)
+ )
+
+ ;; CHECK:      (func $propagate-different-params (param $input1 (ref $empty)) (param $input2 (ref $empty)) (result i32)
+ ;; CHECK-NEXT:  (local $tempresult i32)
+ ;; CHECK-NEXT:  (local.set $tempresult
+ ;; CHECK-NEXT:   (ref.eq
+ ;; CHECK-NEXT:    (local.get $input1)
+ ;; CHECK-NEXT:    (local.get $input2)
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT:  (local.get $tempresult)
+ ;; CHECK-NEXT: )
+ (func $propagate-different-params (param $input1 (ref $empty)) (param $input2 (ref $empty)) (result i32)
+  (local $tempresult i32)
+  (local.set $tempresult
+   ;; We cannot say anything about parameters - they might alias, or not.
+   (ref.eq
+    (local.get $input1)
+    (local.get $input2)
+   )
+  )
+  (local.get $tempresult)
+ )
+
+ ;; CHECK:      (func $propagate-same-param (param $input (ref $empty)) (result i32)
+ ;; CHECK-NEXT:  (local $tempresult i32)
+ ;; CHECK-NEXT:  (local.set $tempresult
+ ;; CHECK-NEXT:   (ref.eq
+ ;; CHECK-NEXT:    (local.get $input)
+ ;; CHECK-NEXT:    (local.get $input)
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT:  (local.get $tempresult)
+ ;; CHECK-NEXT: )
+ (func $propagate-same-param (param $input (ref $empty)) (result i32)
+  (local $tempresult i32)
+  (local.set $tempresult
+   ;; We could optimize this in principle, but atm do not.
+   ;; Note that optimize-instructions can handle patterns like this.
+   (ref.eq
+    (local.get $input)
+    (local.get $input)
+   )
+  )
+  (local.get $tempresult)
+ )
+
+ ;; CHECK:      (func $propagate-uncertain-local (result i32)
+ ;; CHECK-NEXT:  (local $tempresult i32)
+ ;; CHECK-NEXT:  (local $tempref (ref null $empty))
+ ;; CHECK-NEXT:  (local $stashedref (ref null $empty))
+ ;; CHECK-NEXT:  (local.set $tempref
+ ;; CHECK-NEXT:   (struct.new_default_with_rtt $empty
+ ;; CHECK-NEXT:    (rtt.canon $empty)
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT:  (local.set $stashedref
+ ;; CHECK-NEXT:   (local.get $tempref)
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT:  (if
+ ;; CHECK-NEXT:   (call $helper
+ ;; CHECK-NEXT:    (i32.const 0)
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:   (local.set $tempref
  ;; CHECK-NEXT:    (struct.new_default_with_rtt $empty
  ;; CHECK-NEXT:     (rtt.canon $empty)
  ;; CHECK-NEXT:    )
  ;; CHECK-NEXT:   )
  ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT:  (local.set $tempresult
+ ;; CHECK-NEXT:   (ref.eq
+ ;; CHECK-NEXT:    (local.get $tempref)
+ ;; CHECK-NEXT:    (local.get $stashedref)
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:  )
  ;; CHECK-NEXT:  (local.get $tempresult)
  ;; CHECK-NEXT: )
- (func $propagate-unequal (result i32)
+ (func $propagate-uncertain-local (result i32)
   (local $tempresult i32)
   (local $tempref (ref null $empty))
-  ;; assign the result, so that propagate calculates the ref.eq
+  (local $stashedref (ref null $empty))
+  (local.set $tempref
+   (struct.new_with_rtt $empty
+    (rtt.canon $empty)
+   )
+  )
+  (local.set $stashedref
+   (local.get $tempref)
+  )
+  ;; This if makes it impossible to know what value the ref.eq later should
+  ;; return.
+  (if
+   (call $helper
+    (i32.const 0)
+   )
+   (local.set $tempref
+    (struct.new_with_rtt $empty
+     (rtt.canon $empty)
+    )
+   )
+  )
   (local.set $tempresult
-   ;; allocate two different structs
    (ref.eq
+    (local.get $tempref)
+    (local.get $stashedref)
+   )
+  )
+  (local.get $tempresult)
+ )
+
+ ;; CHECK:      (func $propagate-uncertain-loop
+ ;; CHECK-NEXT:  (local $tempresult i32)
+ ;; CHECK-NEXT:  (local $tempref (ref null $empty))
+ ;; CHECK-NEXT:  (local $stashedref (ref null $empty))
+ ;; CHECK-NEXT:  (local.set $tempref
+ ;; CHECK-NEXT:   (struct.new_default_with_rtt $empty
+ ;; CHECK-NEXT:    (rtt.canon $empty)
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT:  (local.set $stashedref
+ ;; CHECK-NEXT:   (local.get $tempref)
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT:  (loop $loop
+ ;; CHECK-NEXT:   (local.set $tempresult
+ ;; CHECK-NEXT:    (ref.eq
+ ;; CHECK-NEXT:     (local.get $tempref)
+ ;; CHECK-NEXT:     (local.get $stashedref)
+ ;; CHECK-NEXT:    )
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:   (local.set $tempref
+ ;; CHECK-NEXT:    (struct.new_default_with_rtt $empty
+ ;; CHECK-NEXT:     (rtt.canon $empty)
+ ;; CHECK-NEXT:    )
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:   (br_if $loop
+ ;; CHECK-NEXT:    (call $helper
+ ;; CHECK-NEXT:     (local.get $tempresult)
+ ;; CHECK-NEXT:    )
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT: )
+ (func $propagate-uncertain-loop
+  (local $tempresult i32)
+  (local $tempref (ref null $empty))
+  (local $stashedref (ref null $empty))
+  (local.set $tempref
+   (struct.new_with_rtt $empty
+    (rtt.canon $empty)
+   )
+  )
+  (local.set $stashedref
+   (local.get $tempref)
+  )
+  (loop $loop
+   ;; Each iteration in this loop may see a different struct, so we cannot
+   ;; precompute the ref.eq here.
+   (local.set $tempresult
+    (ref.eq
+     (local.get $tempref)
+     (local.get $stashedref)
+    )
+   )
+   (local.set $tempref
     (struct.new_with_rtt $empty
      (rtt.canon $empty)
     )
+   )
+   (br_if $loop
+    (call $helper
+     (local.get $tempresult)
+    )
+   )
+  )
+ )
+
+ ;; CHECK:      (func $propagate-certain-loop
+ ;; CHECK-NEXT:  (local $tempresult i32)
+ ;; CHECK-NEXT:  (local $tempref (ref null $empty))
+ ;; CHECK-NEXT:  (local $stashedref (ref null $empty))
+ ;; CHECK-NEXT:  (local.set $tempref
+ ;; CHECK-NEXT:   (struct.new_default_with_rtt $empty
+ ;; CHECK-NEXT:    (rtt.canon $empty)
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT:  (local.set $stashedref
+ ;; CHECK-NEXT:   (local.get $tempref)
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT:  (loop $loop
+ ;; CHECK-NEXT:   (local.set $tempresult
+ ;; CHECK-NEXT:    (i32.const 1)
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:   (br_if $loop
+ ;; CHECK-NEXT:    (call $helper
+ ;; CHECK-NEXT:     (i32.const 1)
+ ;; CHECK-NEXT:    )
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT: )
+ (func $propagate-certain-loop
+  (local $tempresult i32)
+  (local $tempref (ref null $empty))
+  (local $stashedref (ref null $empty))
+  ;; As above, but remove the new in the loop, so that each loop iteration does
+  ;; in fact have the ref locals identical, and we can precompute a 1.
+  (local.set $tempref
+   (struct.new_with_rtt $empty
+    (rtt.canon $empty)
+   )
+  )
+  (local.set $stashedref
+   (local.get $tempref)
+  )
+  (loop $loop
+   (local.set $tempresult
+    (ref.eq
+     (local.get $tempref)
+     (local.get $stashedref)
+    )
+   )
+   (br_if $loop
+    (call $helper
+     (local.get $tempresult)
+    )
+   )
+  )
+ )
+
+ ;; CHECK:      (func $propagate-certain-loop-2
+ ;; CHECK-NEXT:  (local $tempresult i32)
+ ;; CHECK-NEXT:  (local $tempref (ref null $empty))
+ ;; CHECK-NEXT:  (local $stashedref (ref null $empty))
+ ;; CHECK-NEXT:  (loop $loop
+ ;; CHECK-NEXT:   (local.set $tempref
+ ;; CHECK-NEXT:    (struct.new_default_with_rtt $empty
+ ;; CHECK-NEXT:     (rtt.canon $empty)
+ ;; CHECK-NEXT:    )
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:   (local.set $stashedref
+ ;; CHECK-NEXT:    (local.get $tempref)
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:   (local.set $tempresult
+ ;; CHECK-NEXT:    (i32.const 1)
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:   (br_if $loop
+ ;; CHECK-NEXT:    (call $helper
+ ;; CHECK-NEXT:     (i32.const 1)
+ ;; CHECK-NEXT:    )
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT: )
+ (func $propagate-certain-loop-2
+  (local $tempresult i32)
+  (local $tempref (ref null $empty))
+  (local $stashedref (ref null $empty))
+  (loop $loop
+   ;; Another example of a loop where we can optimize. Here the new is inside
+   ;; the loop.
+   (local.set $tempref
     (struct.new_with_rtt $empty
      (rtt.canon $empty)
     )
    )
+   (local.set $stashedref
+    (local.get $tempref)
+   )
+   (local.set $tempresult
+    (ref.eq
+     (local.get $tempref)
+     (local.get $stashedref)
+    )
+   )
+   (br_if $loop
+    (call $helper
+     (local.get $tempresult)
+    )
+   )
+  )
+ )
+
+ ;; CHECK:      (func $propagate-possibly-certain-loop
+ ;; CHECK-NEXT:  (local $tempresult i32)
+ ;; CHECK-NEXT:  (local $tempref (ref null $empty))
+ ;; CHECK-NEXT:  (local $stashedref (ref null $empty))
+ ;; CHECK-NEXT:  (loop $loop
+ ;; CHECK-NEXT:   (if
+ ;; CHECK-NEXT:    (call $helper
+ ;; CHECK-NEXT:     (i32.const 0)
+ ;; CHECK-NEXT:    )
+ ;; CHECK-NEXT:    (local.set $tempref
+ ;; CHECK-NEXT:     (struct.new_default_with_rtt $empty
+ ;; CHECK-NEXT:      (rtt.canon $empty)
+ ;; CHECK-NEXT:     )
+ ;; CHECK-NEXT:    )
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:   (local.set $stashedref
+ ;; CHECK-NEXT:    (local.get $tempref)
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:   (local.set $tempresult
+ ;; CHECK-NEXT:    (ref.eq
+ ;; CHECK-NEXT:     (local.get $tempref)
+ ;; CHECK-NEXT:     (local.get $stashedref)
+ ;; CHECK-NEXT:    )
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:   (br_if $loop
+ ;; CHECK-NEXT:    (call $helper
+ ;; CHECK-NEXT:     (local.get $tempresult)
+ ;; CHECK-NEXT:    )
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT: )
+ (func $propagate-possibly-certain-loop
+  (local $tempresult i32)
+  (local $tempref (ref null $empty))
+  (local $stashedref (ref null $empty))
+  (loop $loop
+   ;; As above, but move the set of $stashedref below the if. That means that
+   ;; it must be identical to $tempref in each iteration. However, that is
+   ;; something we cannot infer atm (while SSA could), so we do not infer
+   ;; anything here for now.
+   (if
+    (call $helper
+     (i32.const 0)
+    )
+    (local.set $tempref
+     (struct.new_with_rtt $empty
+      (rtt.canon $empty)
+     )
+    )
+   )
+   (local.set $stashedref
+    (local.get $tempref)
+   )
+   (local.set $tempresult
+    (ref.eq
+     (local.get $tempref)
+     (local.get $stashedref)
+    )
+   )
+   (br_if $loop
+    (call $helper
+     (local.get $tempresult)
+    )
+   )
   )
-  ;; this value could be precomputed in principle, however, we currently do not
-  ;; precompute GC references, and so nothing will be done.
-  (local.get $tempresult)
+ )
+
+ ;; CHECK:      (func $helper (param $0 i32) (result i32)
+ ;; CHECK-NEXT:  (unreachable)
+ ;; CHECK-NEXT: )
+ (func $helper (param i32) (result i32)
+  (unreachable)
  )
 
  ;; CHECK:      (func $odd-cast-and-get
@@ -530,4 +900,130 @@
    (rtt.canon $struct)
   )
  )
+
+ ;; CHECK:      (func $br_on_cast-on-creation-rtt (result (ref $empty))
+ ;; CHECK-NEXT:  (block $label (result (ref $empty))
+ ;; CHECK-NEXT:   (drop
+ ;; CHECK-NEXT:    (br_on_cast $label
+ ;; CHECK-NEXT:     (struct.new_default_with_rtt $empty
+ ;; CHECK-NEXT:      (rtt.canon $empty)
+ ;; CHECK-NEXT:     )
+ ;; CHECK-NEXT:     (rtt.canon $empty)
+ ;; CHECK-NEXT:    )
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:   (unreachable)
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT: )
+ (func $br_on_cast-on-creation-rtt (result (ref $empty))
+  (block $label (result (ref $empty))
+   (drop
+    ;; The br_on_cast will read the GC data created from struct.new, which must
+    ;; emit it properly, including with an RTT which it will read from (since
+    ;; this instructions uses an RTT).
+    (br_on_cast $label
+     (struct.new_default_with_rtt $empty
+      (rtt.canon $empty)
+     )
+     (rtt.canon $empty)
+    )
+   )
+   (unreachable)
+  )
+ )
+
+ ;; CHECK:      (func $br_on_cast-on-creation-nortt (result (ref $empty))
+ ;; CHECK-NEXT:  (block $label (result (ref $empty))
+ ;; CHECK-NEXT:   (drop
+ ;; CHECK-NEXT:    (br_on_cast_static $label $empty
+ ;; CHECK-NEXT:     (struct.new_default $empty)
+ ;; CHECK-NEXT:    )
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:   (unreachable)
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT: )
+ (func $br_on_cast-on-creation-nortt (result (ref $empty))
+  (block $label (result (ref $empty))
+   (drop
+    ;; As above, but with no RTTs.
+    (br_on_cast_static $label $empty
+     (struct.new_default $empty)
+    )
+   )
+   (unreachable)
+  )
+ )
+
+ ;; CHECK:      (func $ref.is_null (param $param i32)
+ ;; CHECK-NEXT:  (local $ref (ref null $empty))
+ ;; CHECK-NEXT:  (local.set $ref
+ ;; CHECK-NEXT:   (struct.new_default $empty)
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT:  (drop
+ ;; CHECK-NEXT:   (call $helper
+ ;; CHECK-NEXT:    (i32.const 0)
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT:  (local.set $ref
+ ;; CHECK-NEXT:   (ref.null $empty)
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT:  (drop
+ ;; CHECK-NEXT:   (call $helper
+ ;; CHECK-NEXT:    (i32.const 1)
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT:  (if
+ ;; CHECK-NEXT:   (local.get $param)
+ ;; CHECK-NEXT:   (local.set $ref
+ ;; CHECK-NEXT:    (struct.new_default $empty)
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT:  (drop
+ ;; CHECK-NEXT:   (call $helper
+ ;; CHECK-NEXT:    (ref.is_null
+ ;; CHECK-NEXT:     (local.get $ref)
+ ;; CHECK-NEXT:    )
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT: )
+ (func $ref.is_null (param $param i32)
+  (local $ref (ref null $empty))
+  ;; Test ref.null on references, and also test that we can infer multiple
+  ;; assignments in the same function, without confusion between them.
+  (local.set $ref
+   (struct.new $empty)
+  )
+  (drop
+   (call $helper
+    ;; The reference here is definitely not null.
+    (ref.is_null
+     (local.get $ref)
+    )
+   )
+  )
+  (local.set $ref
+   (ref.null $empty)
+  )
+  (drop
+   (call $helper
+    ;; The reference here is definitely null.
+    (ref.is_null
+     (local.get $ref)
+    )
+   )
+  )
+  (if
+   (local.get $param)
+   (local.set $ref
+    (struct.new $empty)
+   )
+  )
+  (drop
+   (call $helper
+    ;; The reference here might be null.
+    (ref.is_null
+     (local.get $ref)
+    )
+   )
+  )
+ )
 )
diff --git a/test/passes/Oz_fuzz-exec_all-features.txt b/test/passes/Oz_fuzz-exec_all-features.txt
index 5730b7ad8..359cb83ed 100644
--- a/test/passes/Oz_fuzz-exec_all-features.txt
+++ b/test/passes/Oz_fuzz-exec_all-features.txt
@@ -85,10 +85,10 @@
 [fuzz-exec] calling static-br_on_cast_fail
 [LoggingExternalInterface logging -2]
 (module
- (type $struct (struct (field (mut i32))))
- (type $extendedstruct (struct (field (mut i32)) (field f64)))
  (type $void_func (func))
  (type $bytes (array (mut i8)))
+ (type $struct (struct (field (mut i32))))
+ (type $extendedstruct (struct (field (mut i32)) (field f64)))
  (type $i32_=>_none (func (param i32)))
  (type $anyref_=>_none (func (param anyref)))
  (type $int_func (func (result i32)))
@@ -183,7 +183,6 @@
   )
  )
  (func $2 (; has Stack IR ;)
-  (local $0 (ref null $extendedstruct))
   (call $log
    (i32.const 1)
   )
@@ -194,76 +193,22 @@
    (i32.const 0)
   )
   (call $log
-   (ref.test
-    (struct.new_default_with_rtt $struct
-     (rtt.canon $struct)
-    )
-    (rtt.canon $struct)
-   )
+   (i32.const 1)
   )
   (call $log
-   (ref.test
-    (struct.new_default_with_rtt $struct
-     (rtt.canon $struct)
-    )
-    (rtt.canon $extendedstruct)
-   )
+   (i32.const 0)
   )
   (call $log
-   (ref.test
-    (local.tee $0
-     (struct.new_default_with_rtt $extendedstruct
-      (rtt.sub $extendedstruct
-       (rtt.canon $struct)
-      )
-     )
-    )
-    (rtt.sub $extendedstruct
-     (rtt.canon $struct)
-    )
-   )
+   (i32.const 1)
   )
   (call $log
-   (ref.test
-    (local.get $0)
-    (rtt.canon $extendedstruct)
-   )
+   (i32.const 0)
   )
   (call $log
-   (ref.test
-    (local.get $0)
-    (rtt.canon $struct)
-   )
+   (i32.const 1)
   )
  )
  (func $3 (; has Stack IR ;)
-  (drop
-   (block $block (result (ref $struct))
-    (drop
-     (block $extendedblock (result (ref $extendedstruct))
-      (drop
-       (br_on_cast $block
-        (br_on_cast $extendedblock
-         (struct.new_default_with_rtt $struct
-          (rtt.canon $struct)
-         )
-         (rtt.canon $extendedstruct)
-        )
-        (rtt.canon $struct)
-       )
-      )
-      (call $log
-       (i32.const -1)
-      )
-      (return)
-     )
-    )
-    (call $log
-     (i32.const -2)
-    )
-    (return)
-   )
-  )
   (call $log
    (i32.const 3)
   )
@@ -295,28 +240,11 @@
   )
  )
  (func $5 (; has Stack IR ;)
-  (local $0 (ref null $extendedstruct))
-  (local.set $0
-   (struct.new_default_with_rtt $extendedstruct
-    (rtt.canon $extendedstruct)
-   )
+  (call $log
+   (i32.const 1)
   )
-  (drop
-   (block $any (result anyref)
-    (call $log
-     (i32.const 1)
-    )
-    (drop
-     (br_on_cast_fail $any
-      (local.get $0)
-      (rtt.canon $extendedstruct)
-     )
-    )
-    (call $log
-     (i32.const 999)
-    )
-    (ref.null any)
-   )
+  (call $log
+   (i32.const 999)
   )
  )
  (func $6 (; has Stack IR ;)
@@ -451,28 +379,10 @@
  )
  (func $25 (; has Stack IR ;)
   (call $log
-   (ref.test
-    (struct.new_default_with_rtt $extendedstruct
-     (rtt.sub $extendedstruct
-      (rtt.canon $struct)
-     )
-    )
-    (rtt.sub $extendedstruct
-     (rtt.canon $struct)
-    )
-   )
+   (i32.const 1)
   )
   (call $log
-   (ref.test
-    (struct.new_default_with_rtt $extendedstruct
-     (rtt.sub $extendedstruct
-      (rtt.canon $struct)
-     )
-    )
-    (rtt.fresh_sub $extendedstruct
-     (rtt.canon $struct)
-    )
-   )
+   (i32.const 0)
   )
   (global.set $rtt
    (rtt.fresh_sub $extendedstruct
@@ -539,56 +449,18 @@
    (i32.const 1)
   )
   (call $log
-   (ref.test_static $extendedstruct
-    (struct.new_default $struct)
-   )
+   (i32.const 0)
   )
   (call $log
    (i32.const 1)
   )
  )
  (func $29 (; has Stack IR ;)
-  (drop
-   (block $block (result (ref $struct))
-    (drop
-     (block $extendedblock (result (ref $extendedstruct))
-      (drop
-       (br_on_cast_static $block $struct
-        (br_on_cast_static $extendedblock $extendedstruct
-         (struct.new_default $struct)
-        )
-       )
-      )
-      (call $log
-       (i32.const -1)
-      )
-      (return)
-     )
-    )
-    (call $log
-     (i32.const -2)
-    )
-    (return)
-   )
-  )
   (call $log
    (i32.const 3)
   )
  )
  (func $30 (; has Stack IR ;)
-  (drop
-   (block $failblock (result (ref $struct))
-    (drop
-     (br_on_cast_static_fail $failblock $extendedstruct
-      (struct.new_default $struct)
-     )
-    )
-    (call $log
-     (i32.const -1)
-    )
-    (return)
-   )
-  )
   (call $log
    (i32.const -2)
   )