Adds a J2CL specific pass that moves itable entries to vtables (#6888)

This allows to remove a reference field from all Java objects reducing
the per object memory and initialization overhead.

The pass is designed to run direclty on the J2CL output before other
optimizations since it relies on invariants that might get lost in
optimization. If the invariants don't hold the pass aborts.

4 files changed, 242 insertions, 0 deletions

diff --git a/test/lit/help/wasm-metadce.test b/test/lit/help/wasm-metadce.test
index 41a43bf1b..4ddf55203 100644
--- a/test/lit/help/wasm-metadce.test
+++ b/test/lit/help/wasm-metadce.test
@@ -248,6 +248,10 @@
 ;; CHECK-NEXT:
 ;; CHECK-NEXT:   --merge-blocks                                merges blocks to their parents
 ;; CHECK-NEXT:
+;; CHECK-NEXT:   --merge-j2cl-itables                          Merges itable structures into 
+;; CHECK-NEXT:                                                 vtables to make types more
+;; CHECK-NEXT:                                                 compact 
+;; CHECK-NEXT:
 ;; CHECK-NEXT:   --merge-locals                                merges locals when beneficial
 ;; CHECK-NEXT:
 ;; CHECK-NEXT:   --merge-similar-functions                     merges similar functions when
diff --git a/test/lit/help/wasm-opt.test b/test/lit/help/wasm-opt.test
index e5b30e304..f55798253 100644
--- a/test/lit/help/wasm-opt.test
+++ b/test/lit/help/wasm-opt.test
@@ -257,6 +257,10 @@
 ;; CHECK-NEXT:
 ;; CHECK-NEXT:   --merge-blocks                                merges blocks to their parents
 ;; CHECK-NEXT:
+;; CHECK-NEXT:   --merge-j2cl-itables                          Merges itable structures into 
+;; CHECK-NEXT:                                                 vtables to make types more
+;; CHECK-NEXT:                                                 compact
+;; CHECK-NEXT:
 ;; CHECK-NEXT:   --merge-locals                                merges locals when beneficial
 ;; CHECK-NEXT:
 ;; CHECK-NEXT:   --merge-similar-functions                     merges similar functions when
diff --git a/test/lit/help/wasm2js.test b/test/lit/help/wasm2js.test
index 2d933984e..39c4d5f5e 100644
--- a/test/lit/help/wasm2js.test
+++ b/test/lit/help/wasm2js.test
@@ -211,6 +211,10 @@
 ;; CHECK-NEXT:
 ;; CHECK-NEXT:   --merge-blocks                                merges blocks to their parents
 ;; CHECK-NEXT:
+;; CHECK-NEXT:   --merge-j2cl-itables                          Merges itable structures into 
+;; CHECK-NEXT:                                                 vtables to make types more
+;; CHECK-NEXT:                                                 compact
+;; CHECK-NEXT:
 ;; CHECK-NEXT:   --merge-locals                                merges locals when beneficial
 ;; CHECK-NEXT:
 ;; CHECK-NEXT:   --merge-similar-functions                     merges similar functions when
diff --git a/test/lit/passes/j2cl-merge-itables.wast b/test/lit/passes/j2cl-merge-itables.wast
new file mode 100644
index 000000000..f578eb65c
--- /dev/null
+++ b/test/lit/passes/j2cl-merge-itables.wast
@@ -0,0 +1,230 @@
+;; NOTE: Assertions have been generated by update_lit_checks.py --all-items and should not be edited.
+
+;; RUN: foreach %s %t wasm-opt --closed-world --merge-j2cl-itables -all -S -o - | filecheck %s
+
+;; Shared itable instance.
+(module
+  (rec
+    ;; CHECK:      (rec
+    ;; CHECK-NEXT:  (type $Object (sub (struct (field $vtable (ref $Object.vtable)) (field $itable (ref $Object.itable)))))
+    (type $Object (sub (struct
+      (field $vtable (ref $Object.vtable))
+      (field $itable (ref $Object.itable)))))
+
+    ;; CHECK:       (type $SubObject (sub $Object (struct (field $vtable (ref $SubObject.vtable)) (field $itable (ref $Object.itable)))))
+    (type $SubObject (sub $Object (struct
+      (field $vtable (ref $SubObject.vtable))
+      (field $itable (ref $Object.itable)))))
+
+    ;; CHECK:       (type $2 (func))
+
+    ;; CHECK:       (type $function (func))
+    (type $function (func))
+
+    ;; The $Object.itable field (a structref) will be added as a field to
+    ;; the beginning of this vtable.
+    ;; CHECK:       (type $Object.vtable (sub (struct (field structref))))
+    (type $Object.vtable (sub (struct)))
+
+    ;; The $Object.itable field (a structref) will be added as a field to
+    ;; the beginning of this vtable.
+    ;; CHECK:       (type $SubObject.vtable (sub $Object.vtable (struct (field structref) (field (ref $function)))))
+    (type $SubObject.vtable (sub $Object.vtable (struct
+      (field (ref $function)))))
+
+    ;; CHECK:       (type $Object.itable (struct (field structref)))
+    (type $Object.itable (struct
+	    (field (ref null struct))))
+  )
+
+  ;; CHECK:      (global $Object.itable (ref $Object.itable) (struct.new_default $Object.itable))
+  (global $Object.itable (ref $Object.itable)
+    (struct.new_default $Object.itable))
+
+  ;; CHECK:      (global $SubObject.itable (ref $Object.itable) (global.get $Object.itable))
+  (global $SubObject.itable (ref $Object.itable)
+    (global.get $Object.itable))  ;; uses shared empty itable instance.
+
+  ;; The initialization for the itable field (null struct) will be added to this
+  ;; vtable instance.
+  ;; CHECK:      (global $SubObject.vtable (ref $SubObject.vtable) (struct.new $SubObject.vtable
+  ;; CHECK-NEXT:  (ref.null none)
+  ;; CHECK-NEXT:  (ref.func $SubObject.f)
+  ;; CHECK-NEXT: ))
+  (global $SubObject.vtable (ref $SubObject.vtable)
+    (struct.new $SubObject.vtable (ref.func $SubObject.f)))
+
+
+  ;; The initialization for the itable field (null struct) will be added to this
+  ;; vtable instance.
+  ;; CHECK:      (global $Object.vtable (ref $Object.vtable) (struct.new $Object.vtable
+  ;; CHECK-NEXT:  (ref.null none)
+  ;; CHECK-NEXT: ))
+  (global $Object.vtable (ref $Object.vtable)
+    (struct.new $Object.vtable))
+
+  ;; CHECK:      (func $SubObject.f (type $function)
+  ;; CHECK-NEXT:  (nop)
+  ;; CHECK-NEXT: )
+  (func $SubObject.f
+    (type $function)
+  )
+
+  ;; CHECK:      (func $usages (type $2)
+  ;; CHECK-NEXT:  (local $o (ref null $SubObject))
+  ;; CHECK-NEXT:  (local.set $o
+  ;; CHECK-NEXT:   (struct.new $SubObject
+  ;; CHECK-NEXT:    (global.get $SubObject.vtable)
+  ;; CHECK-NEXT:    (global.get $SubObject.itable)
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (drop
+  ;; CHECK-NEXT:   (struct.get $SubObject.vtable 1
+  ;; CHECK-NEXT:    (struct.get $SubObject $vtable
+  ;; CHECK-NEXT:     (local.get $o)
+  ;; CHECK-NEXT:    )
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (drop
+  ;; CHECK-NEXT:   (struct.get $SubObject.vtable 0
+  ;; CHECK-NEXT:    (struct.get $SubObject $vtable
+  ;; CHECK-NEXT:     (local.get $o)
+  ;; CHECK-NEXT:    )
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT: )
+  (func $usages
+    (local $o (ref null $SubObject))
+    (local.set $o
+      (struct.new $SubObject
+        (global.get $SubObject.vtable)
+        (global.get $SubObject.itable)))
+    (drop
+      ;; The access to vtable field 0 is offset but the itable size and
+      ;; will be an access to field 1.
+      (struct.get $SubObject.vtable 0
+        (struct.get $SubObject $vtable
+          (local.get $o))))
+    (drop
+      ;; The access to itable field 0 will be rerouted to be an access to
+      ;; vtable field 0.
+      (struct.get $Object.itable 0
+        (struct.get $SubObject $itable
+          (local.get $o))))
+    )
+)
+
+;; Each type has its own itable.
+(module
+  (rec
+    ;; CHECK:      (rec
+    ;; CHECK-NEXT:  (type $Object (sub (struct (field $vtable (ref $Object.vtable)) (field $itable (ref $Object.itable)))))
+    (type $Object (sub (struct
+      (field $vtable (ref $Object.vtable))
+      (field $itable (ref $Object.itable)))))
+
+    ;; CHECK:       (type $SubObject (sub $Object (struct (field $vtable (ref $SubObject.vtable)) (field $itable (ref $SubObject.itable)))))
+    (type $SubObject (sub $Object (struct
+      (field $vtable (ref $SubObject.vtable))
+      (field $itable (ref $SubObject.itable)))))
+
+    ;; CHECK:       (type $2 (func))
+
+    ;; CHECK:       (type $function (func))
+    (type $function (func))
+
+    ;; CHECK:       (type $Object.itable (sub (struct (field structref))))
+    (type $Object.itable (sub (struct
+		  (field (ref null struct)))))
+
+    ;; CHECK:       (type $SubObject.itable (sub $Object.itable (struct (field structref))))
+    (type $SubObject.itable (sub $Object.itable
+      (struct (field (ref null struct)))))
+
+    ;; The $Object.itable field (a structref) will be added as a field to
+    ;; the beginning of this vtable.
+    ;; CHECK:       (type $Object.vtable (sub (struct (field structref))))
+    (type $Object.vtable (sub (struct)))
+
+    ;; The $SubObject.itable field (a structref) will be added as a field to
+    ;; the beginning of this vtable.
+    ;; CHECK:       (type $SubObject.vtable (sub $Object.vtable (struct (field structref) (field (ref $function)))))
+    (type $SubObject.vtable (sub $Object.vtable
+      (struct (field (ref $function)))))
+  )
+
+  ;; The initialization for the itable field (null struct) will be added to this
+  ;; vtable instance.
+  ;; CHECK:      (global $SubObject.vtable (ref $SubObject.vtable) (struct.new $SubObject.vtable
+  ;; CHECK-NEXT:  (ref.null none)
+  ;; CHECK-NEXT:  (ref.func $SubObject.f)
+  ;; CHECK-NEXT: ))
+  (global $SubObject.vtable (ref $SubObject.vtable)
+    (struct.new $SubObject.vtable (ref.func $SubObject.f)))
+
+  ;; CHECK:      (global $SubObject.itable (ref $SubObject.itable) (struct.new_default $SubObject.itable))
+  (global $SubObject.itable (ref $SubObject.itable)
+    (struct.new_default $SubObject.itable))
+
+  ;; The initialization for the itable field (null struct) will be added to this
+  ;; vtable instance.
+  ;; CHECK:      (global $Object.vtable (ref $Object.vtable) (struct.new $Object.vtable
+  ;; CHECK-NEXT:  (ref.null none)
+  ;; CHECK-NEXT: ))
+  (global $Object.vtable (ref $Object.vtable)
+    (struct.new $Object.vtable))
+
+  ;; CHECK:      (global $Object.itable (ref $Object.itable) (struct.new_default $Object.itable))
+  (global $Object.itable (ref $Object.itable)
+    (struct.new_default $Object.itable))
+
+  ;; CHECK:      (func $SubObject.f (type $function)
+  ;; CHECK-NEXT:  (nop)
+  ;; CHECK-NEXT: )
+  (func $SubObject.f
+    (type $function)
+  )
+
+  ;; CHECK:      (func $usages (type $2)
+  ;; CHECK-NEXT:  (local $o (ref null $SubObject))
+  ;; CHECK-NEXT:  (local.set $o
+  ;; CHECK-NEXT:   (struct.new $SubObject
+  ;; CHECK-NEXT:    (global.get $SubObject.vtable)
+  ;; CHECK-NEXT:    (global.get $SubObject.itable)
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (drop
+  ;; CHECK-NEXT:   (struct.get $SubObject.vtable 1
+  ;; CHECK-NEXT:    (struct.get $SubObject $vtable
+  ;; CHECK-NEXT:     (local.get $o)
+  ;; CHECK-NEXT:    )
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (drop
+  ;; CHECK-NEXT:   (struct.get $SubObject.vtable 0
+  ;; CHECK-NEXT:    (struct.get $SubObject $vtable
+  ;; CHECK-NEXT:     (local.get $o)
+  ;; CHECK-NEXT:    )
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT: )
+  (func $usages
+    (local $o (ref null $SubObject))
+    (local.set $o
+      (struct.new $SubObject
+        (global.get $SubObject.vtable)
+        (global.get $SubObject.itable)))
+    (drop
+      ;; The access to vtable field 0 is offset but the itable size and
+      ;; will be an access to field 1.
+      (struct.get $SubObject.vtable 0
+        (struct.get $SubObject $vtable
+          (local.get $o))))
+    (drop
+      ;; The access to itable field 0 will be rerouted to be an access to
+      ;; vtable field 0.
+      (struct.get $Object.itable 0
+        (struct.get $SubObject $itable
+          (local.get $o))))
+  )
+)