[Wasm GC] [ctor-eval] Evaluate and serialize GC data (#4491)

This ended up simpler than I thought. We can simply emit global and
local data as we go, creating globals as necessary to contain GC data,
and referring to them using global.get later. That will ensure that
data identity works (things referring to the same object in the interpreter
will refer to the same object when the wasm is loaded). In more detail,
each live GC item is created in a "defining global", a global that is
immutable and of the precise type of that data. Then we just read from
that location in any place that wants to refer to that data. That is,
something like

function foo() {
  var x = Bar(10);
  var y = Bar(20);
  var z = x;
  z.value++; // first object now contains 11
  ...
}

will be evalled into something like

var define$0 = Bar(11); // note the ++ has taken effect here
var define$1 = Bar(20);

function foo() {
  var x = define$0;
  var y = define$1;
  var z = define$0;
  ...
}

This PR should handle everything but "cycles", that is, GC data that at
runtime ends up forming a loop. Leaving that for later work (not sure
how urgent it is to fix).

9 files changed, 264 insertions, 0 deletions

diff --git a/test/ctor-eval/gc-2.wast b/test/ctor-eval/gc-2.wast
new file mode 100644
index 000000000..fed45abac
--- /dev/null
+++ b/test/ctor-eval/gc-2.wast
@@ -0,0 +1,54 @@
+(module
+  (type $struct (struct_subtype (field i32) data))
+
+  (import "import" "import" (func $import (param anyref)))
+
+  ;; This struct is created in an immutable global, but it has the wrong type.
+  ;; We will create a new defining global for it that has the proper type, and
+  ;; read from it here. (This is necessary as when the global is used elsewhere
+  ;; we want to get the right type from the global.get.)
+  (global $global1 (ref any)
+    (struct.new $struct
+      (i32.const 1337)
+    )
+  )
+
+  ;; Test reordering of globals. This global will be written a value that is
+  ;; actually defined after it. To handle that, we must create it earlier than
+  ;; this global.
+  (global $global2 (mut (ref null $struct))
+    (ref.null $struct)
+  )
+
+  ;; This global is perfect to be a defining global (immutable, right type), but
+  ;; because of an earlier use, we will end up defining it earlier on, and
+  ;; reading it here.
+  (global $global3 (ref $struct)
+    (struct.new $struct
+      (i32.const 9999)
+    )
+  )
+
+  (func "test1"
+    (global.set $global2
+      (global.get $global3)
+    )
+  )
+
+  (func "keepalive" (result i32)
+    (select
+      (struct.get $struct 0
+        (ref.cast_static $struct
+          (global.get $global1)
+        )
+      )
+      (struct.get $struct 0
+        (global.get $global2)
+      )
+      (struct.get $struct 0
+        (global.get $global3)
+      )
+    )
+  )
+)
+
diff --git a/test/ctor-eval/gc-2.wast.ctors b/test/ctor-eval/gc-2.wast.ctors
new file mode 100644
index 000000000..a5bce3fd2
--- /dev/null
+++ b/test/ctor-eval/gc-2.wast.ctors
@@ -0,0 +1 @@
+test1
diff --git a/test/ctor-eval/gc-2.wast.out b/test/ctor-eval/gc-2.wast.out
new file mode 100644
index 000000000..ce30a27e7
--- /dev/null
+++ b/test/ctor-eval/gc-2.wast.out
@@ -0,0 +1,29 @@
+(module
+ (type $struct (struct (field i32)))
+ (type $none_=>_i32 (func (result i32)))
+ (global $ctor-eval$global (ref $struct) (struct.new $struct
+  (i32.const 1337)
+ ))
+ (global $global1 (ref any) (global.get $ctor-eval$global))
+ (global $ctor-eval$global_0 (ref $struct) (struct.new $struct
+  (i32.const 9999)
+ ))
+ (global $global2 (mut (ref null $struct)) (global.get $ctor-eval$global_0))
+ (global $global3 (ref $struct) (global.get $ctor-eval$global_0))
+ (export "keepalive" (func $1))
+ (func $1 (result i32)
+  (select
+   (struct.get $struct 0
+    (ref.cast_static $struct
+     (global.get $global1)
+    )
+   )
+   (struct.get $struct 0
+    (global.get $global2)
+   )
+   (struct.get $struct 0
+    (global.get $global3)
+   )
+  )
+ )
+)
diff --git a/test/ctor-eval/gc-array.wast b/test/ctor-eval/gc-array.wast
new file mode 100644
index 000000000..8f6731821
--- /dev/null
+++ b/test/ctor-eval/gc-array.wast
@@ -0,0 +1,45 @@
+(module
+  (type $array (array (mut i32)))
+
+  (import "import" "import" (func $import (param anyref)))
+
+  ;; This global will remain as it is.
+  (global $global1 (ref $array)
+    (array.init_static $array
+      (i32.const 10)
+      (i32.const 20)
+      (i32.const 30)
+      (i32.const 40)
+    )
+  )
+
+  (global $global2 (ref $array)
+    (array.init_static $array
+      (i32.const 42)
+      ;; This location will be written with a new value, 1337
+      (i32.const 0)
+    )
+  )
+
+  (func "test1"
+    (array.set $array
+      (global.get $global2)
+      (i32.const 1)
+      (i32.const 1337)
+    )
+  )
+
+  (func "keepalive" (result i32)
+    (i32.add
+      (array.get $array
+        (global.get $global1)
+        (i32.const 0)
+      )
+      (array.get $array
+        (global.get $global2)
+        (i32.const 0)
+      )
+    )
+  )
+)
+
diff --git a/test/ctor-eval/gc-array.wast.ctors b/test/ctor-eval/gc-array.wast.ctors
new file mode 100644
index 000000000..a5bce3fd2
--- /dev/null
+++ b/test/ctor-eval/gc-array.wast.ctors
@@ -0,0 +1 @@
+test1
diff --git a/test/ctor-eval/gc-array.wast.out b/test/ctor-eval/gc-array.wast.out
new file mode 100644
index 000000000..d78eba852
--- /dev/null
+++ b/test/ctor-eval/gc-array.wast.out
@@ -0,0 +1,27 @@
+(module
+ (type $array (array (mut i32)))
+ (type $none_=>_i32 (func (result i32)))
+ (global $global1 (ref $array) (array.init_static $array
+  (i32.const 10)
+  (i32.const 20)
+  (i32.const 30)
+  (i32.const 40)
+ ))
+ (global $global2 (ref $array) (array.init_static $array
+  (i32.const 42)
+  (i32.const 1337)
+ ))
+ (export "keepalive" (func $1))
+ (func $1 (result i32)
+  (i32.add
+   (array.get $array
+    (global.get $global1)
+    (i32.const 0)
+   )
+   (array.get $array
+    (global.get $global2)
+    (i32.const 0)
+   )
+  )
+ )
+)
diff --git a/test/ctor-eval/gc.wast b/test/ctor-eval/gc.wast
new file mode 100644
index 000000000..0449b6140
--- /dev/null
+++ b/test/ctor-eval/gc.wast
@@ -0,0 +1,65 @@
+(module
+  (type $struct (struct_subtype (field i32) data))
+
+  (import "import" "import" (func $import (param anyref)))
+
+  ;; Create a GC object in a global. We can keep the struct.new here even after
+  ;; evalling (we should not create an extra, unneeded global, and read from
+  ;; that).
+  (global $global1 (ref $struct)
+    (struct.new $struct
+      (i32.const 1337)
+    )
+  )
+
+  ;; After evalling we should see this refer to a struct with contents 42, and
+  ;; not 41, which is overridden, see "test1". We also should not see any code
+  ;; that creates an object with 41, as that is no longer live.
+  ;;
+  ;; Note that we will not simply do a struct.new in this global, as it is
+  ;; mutable, and we only use immutable globals as defining globals for values,
+  ;; so a new (immutable) global will appear, and we will read from it.
+  (global $global2 (mut (ref null $struct)) (ref.null $struct))
+
+  (func "test1"
+    ;; Leave the first local as null, which we should handle properly (we will
+    ;; end up emitting nothing and still using the default null value).
+    (local $temp1 (ref null $struct))
+    (local $temp2 (ref null $struct))
+
+    (global.set $global2
+      (struct.new $struct
+        (i32.const 41)
+      )
+    )
+    (global.set $global2
+      (struct.new $struct
+        (i32.const 42)
+      )
+    )
+
+    ;; Write a value to this local. A struct with value 99 will be created in a
+    ;; global, and referred to here.
+    (local.set $temp2
+      (struct.new $struct
+        (i32.const 99)
+      )
+    )
+
+    ;; Stop evalling here at the import.
+    (call $import (local.get $temp1))
+    (call $import (local.get $temp2))
+  )
+
+  (func "keepalive" (result i32)
+    (i32.add
+      (struct.get $struct 0
+        (global.get $global1)
+      )
+      (struct.get $struct 0
+        (global.get $global2)
+      )
+    )
+  )
+)
+
diff --git a/test/ctor-eval/gc.wast.ctors b/test/ctor-eval/gc.wast.ctors
new file mode 100644
index 000000000..a5bce3fd2
--- /dev/null
+++ b/test/ctor-eval/gc.wast.ctors
@@ -0,0 +1 @@
+test1
diff --git a/test/ctor-eval/gc.wast.out b/test/ctor-eval/gc.wast.out
new file mode 100644
index 000000000..b926b5ad4
--- /dev/null
+++ b/test/ctor-eval/gc.wast.out
@@ -0,0 +1,41 @@
+(module
+ (type $struct (struct (field i32)))
+ (type $anyref_=>_none (func (param anyref)))
+ (type $none_=>_i32 (func (result i32)))
+ (type $none_=>_none (func))
+ (import "import" "import" (func $import (param anyref)))
+ (global $global1 (ref $struct) (struct.new $struct
+  (i32.const 1337)
+ ))
+ (global $ctor-eval$global (ref $struct) (struct.new $struct
+  (i32.const 42)
+ ))
+ (global $global2 (mut (ref null $struct)) (global.get $ctor-eval$global))
+ (global $ctor-eval$global_0 (ref $struct) (struct.new $struct
+  (i32.const 99)
+ ))
+ (export "test1" (func $0_0))
+ (export "keepalive" (func $1))
+ (func $1 (result i32)
+  (i32.add
+   (struct.get $struct 0
+    (global.get $global1)
+   )
+   (struct.get $struct 0
+    (global.get $global2)
+   )
+  )
+ )
+ (func $0_0
+  (local $0 (ref null $struct))
+  (local.set $0
+   (global.get $ctor-eval$global_0)
+  )
+  (call $import
+   (ref.null $struct)
+  )
+  (call $import
+   (local.get $0)
+  )
+ )
+)