[GC] Fully implement RTT semantics (#3441)

This adds info to RTT literals so that they can represent the chain of
rtt.canon/sub commands that generated them, and it adds an internal
RTT for each GC allocation (array or struct).

The approach taken is to simply store the full chain of rtt.sub types
that led to each literal. This is not efficient, but it is simple and seems
sufficient for the semantics described in the GC MVP doc - specifically,
only the types matter, in that repeated executions of rtt.canon/sub
on the same inputs yield equal outputs.

This PR fixes a bunch of minor issues regarding that, enough to allow testing
of the optimization and execution of ref.test/cast.

2 files changed, 172 insertions, 0 deletions

diff --git a/test/passes/Oz_fuzz-exec_all-features.txt b/test/passes/Oz_fuzz-exec_all-features.txt
index 0663a3351..ed235ed21 100644
--- a/test/passes/Oz_fuzz-exec_all-features.txt
+++ b/test/passes/Oz_fuzz-exec_all-features.txt
@@ -9,14 +9,25 @@
 [LoggingExternalInterface logging 128]
 [LoggingExternalInterface logging -128]
 [LoggingExternalInterface logging 42]
+[fuzz-exec] calling rtts
+[LoggingExternalInterface logging 1]
+[LoggingExternalInterface logging 0]
+[LoggingExternalInterface logging 0]
+[LoggingExternalInterface logging 1]
+[LoggingExternalInterface logging 0]
+[LoggingExternalInterface logging 1]
+[LoggingExternalInterface logging 0]
+[LoggingExternalInterface logging 1]
 (module
  (type ${i32} (struct (field i32)))
+ (type ${i32_f64} (struct (field i32) (field f64)))
  (type $none_=>_none (func))
  (type $[mut:i8] (array (mut i8)))
  (type $i32_=>_none (func (param i32)))
  (import "fuzzing-support" "log-i32" (func $log (param i32)))
  (export "structs" (func $0))
  (export "arrays" (func $1))
+ (export "rtts" (func $2))
  (func $0 (; has Stack IR ;)
   (local $0 (ref null ${i32}))
   (call $log
@@ -95,6 +106,84 @@
    )
   )
  )
+ (func $2 (; has Stack IR ;)
+  (local $0 (rtt ${i32}))
+  (local $1 (rtt ${i32_f64}))
+  (local $2 (rtt ${i32_f64}))
+  (local $3 anyref)
+  (local.set $1
+   (rtt.sub ${i32_f64}
+    (local.tee $0
+     (rtt.canon ${i32})
+    )
+   )
+  )
+  (local.set $2
+   (rtt.canon ${i32_f64})
+  )
+  (call $log
+   (ref.is_null
+    (ref.cast ${i32}
+     (ref.null ${i32})
+     (local.get $0)
+    )
+   )
+  )
+  (call $log
+   (ref.test ${i32}
+    (ref.null ${i32})
+    (local.get $0)
+   )
+  )
+  (call $log
+   (ref.test ${i32}
+    (array.new_with_rtt $[mut:i8]
+     (rtt.canon $[mut:i8])
+     (i32.const 10)
+     (i32.const 20)
+    )
+    (local.get $0)
+   )
+  )
+  (call $log
+   (ref.test ${i32}
+    (struct.new_default_with_rtt ${i32}
+     (local.get $0)
+    )
+    (local.get $0)
+   )
+  )
+  (call $log
+   (ref.test ${i32_f64}
+    (struct.new_default_with_rtt ${i32}
+     (local.get $0)
+    )
+    (local.get $2)
+   )
+  )
+  (call $log
+   (ref.test ${i32_f64}
+    (local.tee $3
+     (struct.new_default_with_rtt ${i32_f64}
+      (local.get $1)
+     )
+    )
+    (local.get $1)
+   )
+  )
+  (call $log
+   (ref.test ${i32_f64}
+    (local.get $3)
+    (local.get $2)
+   )
+  )
+  (call $log
+   (ref.test ${i32}
+    (local.get $3)
+    (local.get $0)
+   )
+  )
+ )
 )
 [fuzz-exec] calling structs
 [LoggingExternalInterface logging 0]
@@ -107,3 +196,12 @@
 [LoggingExternalInterface logging 128]
 [LoggingExternalInterface logging -128]
 [LoggingExternalInterface logging 42]
+[fuzz-exec] calling rtts
+[LoggingExternalInterface logging 1]
+[LoggingExternalInterface logging 0]
+[LoggingExternalInterface logging 0]
+[LoggingExternalInterface logging 1]
+[LoggingExternalInterface logging 0]
+[LoggingExternalInterface logging 1]
+[LoggingExternalInterface logging 0]
+[LoggingExternalInterface logging 1]
diff --git a/test/passes/Oz_fuzz-exec_all-features.wast b/test/passes/Oz_fuzz-exec_all-features.wast
index d32ee0c19..e12ddeed0 100644
--- a/test/passes/Oz_fuzz-exec_all-features.wast
+++ b/test/passes/Oz_fuzz-exec_all-features.wast
@@ -1,5 +1,6 @@
 (module
  (type $struct (struct i32))
+ (type $extendedstruct (struct i32 f64))
  (type $bytes (array (mut i8)))
  (import "fuzzing-support" "log-i32" (func $log (param i32)))
  (func "structs"
@@ -67,4 +68,77 @@
    (array.get_s $bytes (local.get $x) (i32.const 20))
   )
  )
+ (func "rtts"
+  (local $x (rtt $struct))
+  (local $y (rtt $extendedstruct))
+  (local $z (rtt $extendedstruct))
+  (local $any anyref)
+  (local.set $x (rtt.canon $struct))
+  (local.set $y (rtt.sub $extendedstruct (local.get $x)))
+  (local.set $z (rtt.canon $extendedstruct))
+  ;; Casting null returns null.
+  (call $log (ref.is_null
+   (ref.cast $struct (ref.null $struct) (local.get $x))
+  ))
+  ;; Testing null returns 0.
+  (call $log
+   (ref.test $struct (ref.null $struct) (local.get $x))
+  )
+  ;; Testing something completely wrong (struct vs array) returns 0.
+  (call $log
+   (ref.test $struct
+    (array.new_with_rtt $bytes
+     (rtt.canon $bytes)
+     (i32.const 10)
+     (i32.const 20)
+    )
+    (local.get $x)
+   )
+  )
+  ;; Testing a thing with the same RTT returns 1.
+  (call $log
+   (ref.test $struct
+    (struct.new_default_with_rtt $struct
+     (local.get $x)
+    )
+    (local.get $x)
+   )
+  )
+  ;; A bad downcast returns 0: we create a struct, which is not a extendedstruct.
+  (call $log
+   (ref.test $extendedstruct
+    (struct.new_default_with_rtt $struct
+     (local.get $x)
+    )
+    (local.get $z)
+   )
+  )
+  ;; Create a extendedstruct with RTT y, and upcast statically to anyref.
+  (local.set $any
+   (struct.new_default_with_rtt $extendedstruct
+    (local.get $y)
+   )
+  )
+  ;; Casting to y, the exact same RTT, works.
+  (call $log
+   (ref.test $extendedstruct
+    (local.get $any)
+    (local.get $y)
+   )
+  )
+  ;; Casting to z, another RTT of the same data type, fails.
+  (call $log
+   (ref.test $extendedstruct
+    (local.get $any)
+    (local.get $z)
+   )
+  )
+  ;; Casting to x, the parent of y, works.
+  (call $log
+   (ref.test $struct
+    (local.get $any)
+    (local.get $x)
+   )
+  )
+ )
 )