[Wasm GC] Fix precompute on GC data (#3810)

This fixes precomputation on GC after #3803 was too optimistic.

The issue is subtle. Precompute will repeatedly evaluate expressions and
propagate their values, flowing them around, and it ignores side effects
when doing so. For example:

(block
 ..side effect..
 (i32.const 1)
)
When we evaluate that we see there are side effects, but regardless of them
we know the value flowing out is 1. So we can propagate that value, if it is
assigned to a local and read elsewhere.

This is not valid for GC because struct.new and array.new have a "side
effect" that is noticeable in the result. Each time we call struct.new we get a
new struct with a new address, which ref.eq can distinguish. So when this
pass evaluates the same thing multiple times it will get a different result.

Also, we can't precompute a struct.get even if we know the struct, not unless
we know the reference has not escaped (where a call could modify it).

To avoid all that, do not precompute references, aside from the trivially safe ones
like nulls and function references (simple constants that are the same each time
we evaluate the expression emitting them).

precomputeExpression() had a minor bug which this fixes. It checked the type
of the expression to see if we can create a constant for it, but really it should
check the value - since (separate from this PR) we have no way to emit a
"constant" for a struct etc. Also that only matters if replaceExpression is true, that
is, if we are replacing with a constant; if we just want the value internally, we have
no limit on that.

Also add Literal support for comparing GC refs, which is used by ref.eq. Without
that tiny fix the tests here crash.

This adds a bunch of tests, many for corner cases that we don't handle (since
the PR makes us not propagate GC references). But they should be helpful
if/when we do, to avoid the mistakes in #3803

3 files changed, 487 insertions, 17 deletions

diff --git a/test/lit/passes/precompute-gc.wast b/test/lit/passes/precompute-gc.wast
index 9402aa068..0cd6d2c2c 100644
--- a/test/lit/passes/precompute-gc.wast
+++ b/test/lit/passes/precompute-gc.wast
@@ -1,8 +1,13 @@
 ;; NOTE: Assertions have been generated by update_lit_checks.py and should not be edited.
-;; RUN: wasm-opt %s --remove-unused-names --precompute-propagate -all -S -o - \
+;; RUN: wasm-opt %s --remove-unused-names --precompute-propagate --fuzz-exec -all -S -o - \
 ;; RUN:   | filecheck %s
 
 (module
+ (type $struct (struct (mut i32)))
+ (type $empty (struct))
+
+ (import "fuzzing-support" "log-i32" (func $log (param i32)))
+
  ;; CHECK:      (func $test-fallthrough (result i32)
  ;; CHECK-NEXT:  (local $x funcref)
  ;; CHECK-NEXT:  (local.set $x
@@ -34,4 +39,356 @@
    (local.get $x)
   )
  )
+
+ ;; CHECK:      (func $load-from-struct
+ ;; CHECK-NEXT:  (local $x (ref null $struct))
+ ;; CHECK-NEXT:  (local.set $x
+ ;; CHECK-NEXT:   (struct.new_with_rtt $struct
+ ;; CHECK-NEXT:    (i32.const 1)
+ ;; CHECK-NEXT:    (rtt.canon $struct)
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT:  (call $log
+ ;; CHECK-NEXT:   (struct.get $struct 0
+ ;; CHECK-NEXT:    (local.get $x)
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT:  (local.set $x
+ ;; CHECK-NEXT:   (struct.new_with_rtt $struct
+ ;; CHECK-NEXT:    (i32.const 2)
+ ;; CHECK-NEXT:    (rtt.canon $struct)
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT:  (call $log
+ ;; CHECK-NEXT:   (struct.get $struct 0
+ ;; CHECK-NEXT:    (local.get $x)
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT:  (struct.set $struct 0
+ ;; CHECK-NEXT:   (local.get $x)
+ ;; CHECK-NEXT:   (i32.const 3)
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT:  (call $log
+ ;; CHECK-NEXT:   (struct.get $struct 0
+ ;; CHECK-NEXT:    (local.get $x)
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT: )
+ (func $load-from-struct
+  (local $x (ref null $struct))
+  (local.set $x
+   (struct.new_with_rtt $struct
+    (i32.const 1)
+    (rtt.canon $struct)
+   )
+  )
+  ;; we don't precompute these, as we don't know if the GC data was modified
+  ;; elsewhere (we'd need immutability or escape analysis)
+  (call $log
+   (struct.get $struct 0 (local.get $x))
+  )
+  ;; Assign a new struct
+  (local.set $x
+   (struct.new_with_rtt $struct
+    (i32.const 2)
+    (rtt.canon $struct)
+   )
+  )
+  (call $log
+   (struct.get $struct 0 (local.get $x))
+  )
+  ;; Assign a new value
+  (struct.set $struct 0
+   (local.get $x)
+   (i32.const 3)
+  )
+  (call $log
+   (struct.get $struct 0 (local.get $x))
+  )
+ )
+ ;; CHECK:      (func $load-from-struct-bad-merge (param $i i32)
+ ;; CHECK-NEXT:  (local $x (ref null $struct))
+ ;; CHECK-NEXT:  (if
+ ;; CHECK-NEXT:   (local.get $i)
+ ;; CHECK-NEXT:   (local.set $x
+ ;; CHECK-NEXT:    (struct.new_with_rtt $struct
+ ;; CHECK-NEXT:     (i32.const 1)
+ ;; CHECK-NEXT:     (rtt.canon $struct)
+ ;; CHECK-NEXT:    )
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:   (local.set $x
+ ;; CHECK-NEXT:    (struct.new_with_rtt $struct
+ ;; CHECK-NEXT:     (i32.const 2)
+ ;; CHECK-NEXT:     (rtt.canon $struct)
+ ;; CHECK-NEXT:    )
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT:  (call $log
+ ;; CHECK-NEXT:   (struct.get $struct 0
+ ;; CHECK-NEXT:    (local.get $x)
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT: )
+ (func $load-from-struct-bad-merge (param $i i32)
+  (local $x (ref null $struct))
+  ;; a merge of two different $x values cannot be precomputed
+  (if
+   (local.get $i)
+   (local.set $x
+    (struct.new_with_rtt $struct
+     (i32.const 1)
+     (rtt.canon $struct)
+    )
+   )
+   (local.set $x
+    (struct.new_with_rtt $struct
+     (i32.const 2)
+     (rtt.canon $struct)
+    )
+   )
+  )
+  (call $log
+   (struct.get $struct 0 (local.get $x))
+  )
+ )
+ ;; CHECK:      (func $modify-gc-heap (param $x (ref null $struct))
+ ;; CHECK-NEXT:  (struct.set $struct 0
+ ;; CHECK-NEXT:   (local.get $x)
+ ;; CHECK-NEXT:   (i32.add
+ ;; CHECK-NEXT:    (struct.get $struct 0
+ ;; CHECK-NEXT:     (local.get $x)
+ ;; CHECK-NEXT:    )
+ ;; CHECK-NEXT:    (i32.const 1)
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT: )
+ (func $modify-gc-heap (param $x (ref null $struct))
+  (struct.set $struct 0
+   (local.get $x)
+   (i32.add
+    (struct.get $struct 0
+     (local.get $x)
+    )
+    (i32.const 1)
+   )
+  )
+ )
+ ;; --fuzz-exec verifies the output of this function, checking that the change
+ ;; makde in modify-gc-heap is not ignored
+ ;; CHECK:      (func $load-from-struct-bad-escape
+ ;; CHECK-NEXT:  (local $x (ref null $struct))
+ ;; CHECK-NEXT:  (local.set $x
+ ;; CHECK-NEXT:   (struct.new_with_rtt $struct
+ ;; CHECK-NEXT:    (i32.const 1)
+ ;; CHECK-NEXT:    (rtt.canon $struct)
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT:  (call $modify-gc-heap
+ ;; CHECK-NEXT:   (local.get $x)
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT:  (call $log
+ ;; CHECK-NEXT:   (struct.get $struct 0
+ ;; CHECK-NEXT:    (local.get $x)
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT: )
+ (func $load-from-struct-bad-escape (export "test")
+  (local $x (ref null $struct))
+  (local.set $x
+   (struct.new_with_rtt $struct
+    (i32.const 1)
+    (rtt.canon $struct)
+   )
+  )
+  (call $modify-gc-heap
+   (local.get $x)
+  )
+  (call $log
+   (struct.get $struct 0 (local.get $x))
+  )
+ )
+ ;; CHECK:      (func $load-from-struct-bad-arrive (param $x (ref null $struct))
+ ;; CHECK-NEXT:  (call $log
+ ;; CHECK-NEXT:   (struct.get $struct 0
+ ;; CHECK-NEXT:    (local.get $x)
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT: )
+ (func $load-from-struct-bad-arrive (param $x (ref null $struct))
+  ;; a parameter cannot be precomputed
+  (call $log
+   (struct.get $struct 0 (local.get $x))
+  )
+ )
+ ;; CHECK:      (func $ref-comparisons (param $x (ref null $struct)) (param $y (ref null $struct))
+ ;; CHECK-NEXT:  (local $z (ref null $struct))
+ ;; CHECK-NEXT:  (local $w (ref null $struct))
+ ;; CHECK-NEXT:  (call $log
+ ;; CHECK-NEXT:   (ref.eq
+ ;; CHECK-NEXT:    (local.get $x)
+ ;; CHECK-NEXT:    (local.get $y)
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT:  (call $log
+ ;; CHECK-NEXT:   (ref.eq
+ ;; CHECK-NEXT:    (local.get $x)
+ ;; CHECK-NEXT:    (ref.null $struct)
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT:  (call $log
+ ;; CHECK-NEXT:   (ref.eq
+ ;; CHECK-NEXT:    (local.get $x)
+ ;; CHECK-NEXT:    (ref.null $struct)
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT:  (call $log
+ ;; CHECK-NEXT:   (i32.const 1)
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT: )
+ (func $ref-comparisons
+  (param $x (ref null $struct))
+  (param $y (ref null $struct))
+  (local $z (ref null $struct))
+  (local $w (ref null $struct))
+  ;; incoming parameters are unknown
+  (call $log
+   (ref.eq
+    (local.get $x)
+    (local.get $y)
+   )
+  )
+  (call $log
+   (ref.eq
+    (local.get $x)
+    ;; locals are ref.null which are known, and will be propagated
+    (local.get $z)
+   )
+  )
+  (call $log
+   (ref.eq
+    (local.get $x)
+    (local.get $w)
+   )
+  )
+  ;; null-initialized locals are known and can be compared
+  (call $log
+   (ref.eq
+    (local.get $z)
+    (local.get $w)
+   )
+  )
+ )
+ ;; CHECK:      (func $new-ref-comparisons (result i32)
+ ;; CHECK-NEXT:  (local $x (ref null $struct))
+ ;; CHECK-NEXT:  (local $y (ref null $struct))
+ ;; CHECK-NEXT:  (local $tempresult i32)
+ ;; CHECK-NEXT:  (local.set $x
+ ;; CHECK-NEXT:   (struct.new_with_rtt $struct
+ ;; CHECK-NEXT:    (i32.const 1)
+ ;; CHECK-NEXT:    (rtt.canon $struct)
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT:  (local.set $y
+ ;; 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:  )
+ ;; CHECK-NEXT:  (local.get $tempresult)
+ ;; CHECK-NEXT: )
+ (func $new-ref-comparisons (result i32)
+  (local $x (ref null $struct))
+  (local $y (ref null $struct))
+  (local $tempresult i32)
+  (local.set $x
+   (struct.new_with_rtt $struct
+    (i32.const 1)
+    (rtt.canon $struct)
+   )
+  )
+  (local.set $y
+   (local.get $x)
+  )
+  ;; assign the result, so that propagate calculates the ref.eq
+  (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.
+  (local.get $tempresult)
+ )
+ ;; CHECK:      (func $propagate-equal (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:    (local.tee $tempref
+ ;; CHECK-NEXT:     (struct.new_default_with_rtt $empty
+ ;; CHECK-NEXT:      (rtt.canon $empty)
+ ;; CHECK-NEXT:     )
+ ;; CHECK-NEXT:    )
+ ;; CHECK-NEXT:    (local.get $tempref)
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT:  (local.get $tempresult)
+ ;; CHECK-NEXT: )
+ (func $propagate-equal (result i32)
+  (local $tempresult i32)
+  (local $tempref (ref null $empty))
+  ;; assign the result, so that propagate calculates the ref.eq
+  (local.set $tempresult
+   (ref.eq
+    ;; allocate one struct
+    (local.tee $tempref
+     (struct.new_with_rtt $empty
+      (rtt.canon $empty)
+     )
+    )
+    (local.get $tempref)
+   )
+  )
+  ;; 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 $propagate-unequal (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:    (struct.new_default_with_rtt $empty
+ ;; CHECK-NEXT:     (rtt.canon $empty)
+ ;; CHECK-NEXT:    )
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT:  (local.get $tempresult)
+ ;; 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
+  (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)
+    )
+   )
+  )
+  ;; this value could be precomputed in principle, however, we currently do not
+  ;; precompute GC references, and so nothing will be done.
+  (local.get $tempresult)
+ )
 )
diff --git a/test/passes/Oz_fuzz-exec_all-features.txt b/test/passes/Oz_fuzz-exec_all-features.txt
index b7c7688b5..618fa2333 100644
--- a/test/passes/Oz_fuzz-exec_all-features.txt
+++ b/test/passes/Oz_fuzz-exec_all-features.txt
@@ -35,11 +35,13 @@
 [fuzz-exec] calling array-alloc-failure
 [host limit allocation failure]
 (module
+ (type $struct (struct (field (mut i32))))
  (type $void_func (func))
+ (type $extendedstruct (struct (field (mut i32)) (field f64)))
+ (type $bytes (array (mut i8)))
  (type $i32_=>_none (func (param i32)))
  (type $anyref_=>_none (func (param anyref)))
  (type $int_func (func (result i32)))
- (type $struct (struct (field (mut i32))))
  (import "fuzzing-support" "log-i32" (func $log (param i32)))
  (elem declare func $a-void-func)
  (export "structs" (func $0))
@@ -51,37 +53,85 @@
  (export "rtt-and-cast-on-func" (func $8))
  (export "array-alloc-failure" (func $9))
  (func $0 (; has Stack IR ;)
+  (local $0 (ref null $struct))
   (call $log
-   (i32.const 0)
+   (struct.get $struct 0
+    (local.tee $0
+     (struct.new_default_with_rtt $struct
+      (rtt.canon $struct)
+     )
+    )
+   )
   )
-  (call $log
+  (struct.set $struct 0
+   (local.get $0)
    (i32.const 42)
   )
   (call $log
+   (struct.get $struct 0
+    (local.get $0)
+   )
+  )
+  (struct.set $struct 0
+   (local.get $0)
    (i32.const 100)
   )
   (call $log
-   (i32.const 100)
+   (struct.get $struct 0
+    (local.get $0)
+   )
+  )
+  (call $log
+   (struct.get $struct 0
+    (local.get $0)
+   )
   )
  )
  (func $1 (; has Stack IR ;)
+  (local $0 (ref null $bytes))
   (call $log
-   (i32.const 50)
+   (array.len $bytes
+    (local.tee $0
+     (array.new_with_rtt $bytes
+      (i32.const 42)
+      (i32.const 50)
+      (rtt.canon $bytes)
+     )
+    )
+   )
   )
   (call $log
-   (i32.const 42)
+   (array.get_u $bytes
+    (local.get $0)
+    (i32.const 10)
+   )
   )
-  (call $log
+  (array.set $bytes
+   (local.get $0)
+   (i32.const 10)
    (i32.const 128)
   )
   (call $log
-   (i32.const -128)
+   (array.get_u $bytes
+    (local.get $0)
+    (i32.const 10)
+   )
   )
   (call $log
-   (i32.const 42)
+   (array.get_s $bytes
+    (local.get $0)
+    (i32.const 10)
+   )
+  )
+  (call $log
+   (array.get_s $bytes
+    (local.get $0)
+    (i32.const 20)
+   )
   )
  )
  (func $2 (; has Stack IR ;)
+  (local $0 anyref)
   (call $log
    (i32.const 1)
   )
@@ -89,25 +139,86 @@
    (i32.const 0)
   )
   (call $log
-   (i32.const 0)
+   (ref.test
+    (array.new_with_rtt $bytes
+     (i32.const 20)
+     (i32.const 10)
+     (rtt.canon $bytes)
+    )
+    (rtt.canon $struct)
+   )
   )
   (call $log
-   (i32.const 1)
+   (ref.test
+    (struct.new_default_with_rtt $struct
+     (rtt.canon $struct)
+    )
+    (rtt.canon $struct)
+   )
   )
   (call $log
-   (i32.const 0)
+   (ref.test
+    (struct.new_default_with_rtt $struct
+     (rtt.canon $struct)
+    )
+    (rtt.canon $extendedstruct)
+   )
   )
   (call $log
-   (i32.const 1)
+   (ref.test
+    (local.tee $0
+     (struct.new_default_with_rtt $extendedstruct
+      (rtt.sub $extendedstruct
+       (rtt.canon $struct)
+      )
+     )
+    )
+    (rtt.sub $extendedstruct
+     (rtt.canon $struct)
+    )
+   )
   )
   (call $log
-   (i32.const 0)
+   (ref.test
+    (local.get $0)
+    (rtt.canon $extendedstruct)
+   )
   )
   (call $log
-   (i32.const 1)
+   (ref.test
+    (local.get $0)
+    (rtt.canon $struct)
+   )
   )
  )
  (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)
   )
diff --git a/test/passes/Oz_fuzz-exec_all-features.wast b/test/passes/Oz_fuzz-exec_all-features.wast
index c88133c3a..87f2e24e3 100644
--- a/test/passes/Oz_fuzz-exec_all-features.wast
+++ b/test/passes/Oz_fuzz-exec_all-features.wast
@@ -17,7 +17,9 @@
    )
   )
   ;; The value is initialized to 0
-  ;; Note: -Oz will optimize all these to constants thanks to Precompute
+  ;; Note: We cannot optimize these to constants without either immutability or
+  ;; some kind of escape analysis (to verify that the GC data referred to is not
+  ;; written to elsewhere).
   (call $log
    (struct.get $struct 0 (local.get $x))
   )