Do not special case ref.null in `LUBFinder` (#5307)

Before we implemented bottom heap types, `ref.null` had to be annotated with
specific types. The `LUBFinder` utility ignored these types so that it could
find the best LUB from all considered non-null expressions, then go back and
update the type annotations on the nulls to match that LUB. Now that we have
bottom types, however, none of that is necessary, and in fact ignoring nulls can
miss possible refinements to bottom types.

Update and simplify `LUBFinder` so that it is a simple wrapper around the
underlying `Type::getLeastUpperBound` utility with no additional logic. Update
tests to account for the more powerful optimizations.

6 files changed, 101 insertions, 58 deletions

diff --git a/test/lit/passes/dae-gc-refine-params.wast b/test/lit/passes/dae-gc-refine-params.wast
index 53110efca..dc3c6879f 100644
--- a/test/lit/passes/dae-gc-refine-params.wast
+++ b/test/lit/passes/dae-gc-refine-params.wast
@@ -12,16 +12,20 @@
  ;; NOMNL:      (type ${i32} (struct_subtype (field i32) ${}))
  (type ${i32} (struct_subtype (field i32) ${}))
 
+ ;; CHECK:      (type ${i32_i64} (struct_subtype (field i32) (field i64) ${i32}))
+
+ ;; CHECK:      (type ${i32_f32} (struct_subtype (field i32) (field f32) ${i32}))
+
  ;; CHECK:      (type ${f64} (struct_subtype (field f64) ${}))
+ ;; NOMNL:      (type ${i32_i64} (struct_subtype (field i32) (field i64) ${i32}))
+
+ ;; NOMNL:      (type ${i32_f32} (struct_subtype (field i32) (field f32) ${i32}))
+
  ;; NOMNL:      (type ${f64} (struct_subtype (field f64) ${}))
  (type ${f64} (struct_subtype (field f64) ${}))
 
-;; CHECK:      (type ${i32_i64} (struct_subtype (field i32) (field i64) ${i32}))
-;; NOMNL:      (type ${i32_i64} (struct_subtype (field i32) (field i64) ${i32}))
 (type ${i32_i64} (struct_subtype (field i32) (field i64) ${i32}))
 
- ;; CHECK:      (type ${i32_f32} (struct_subtype (field i32) (field f32) ${i32}))
- ;; NOMNL:      (type ${i32_f32} (struct_subtype (field i32) (field f32) ${i32}))
  (type ${i32_f32} (struct_subtype (field i32) (field f32) ${i32}))
 
  ;; CHECK:      (func $call-various-params-no (type $none_=>_none)
@@ -583,34 +587,70 @@
  )
 
  ;; CHECK:      (func $get_null_{i32} (type $none_=>_ref?|${i32}|) (result (ref null ${i32}))
- ;; CHECK-NEXT:  (ref.null none)
+ ;; CHECK-NEXT:  (select (result (ref null ${i32}))
+ ;; CHECK-NEXT:   (ref.null none)
+ ;; CHECK-NEXT:   (struct.new_default ${i32})
+ ;; CHECK-NEXT:   (i32.const 0)
+ ;; CHECK-NEXT:  )
  ;; CHECK-NEXT: )
  ;; NOMNL:      (func $get_null_{i32} (type $none_=>_ref?|${i32}|) (result (ref null ${i32}))
- ;; NOMNL-NEXT:  (ref.null none)
+ ;; NOMNL-NEXT:  (select (result (ref null ${i32}))
+ ;; NOMNL-NEXT:   (ref.null none)
+ ;; NOMNL-NEXT:   (struct.new_default ${i32})
+ ;; NOMNL-NEXT:   (i32.const 0)
+ ;; NOMNL-NEXT:  )
  ;; NOMNL-NEXT: )
  (func $get_null_{i32} (result (ref null ${i32}))
   ;; Helper function that returns a null value of ${i32}. We use this instead of
   ;; a direct ref.null because those can be rewritten by LUBFinder.
-  (ref.null ${i32})
+  (select
+   (ref.null none)
+   (struct.new_default ${i32})
+   (i32.const 0)
+  )
  )
 
  ;; CHECK:      (func $get_null_{i32_i64} (type $none_=>_ref?|${i32_i64}|) (result (ref null ${i32_i64}))
- ;; CHECK-NEXT:  (ref.null none)
+ ;; CHECK-NEXT:  (select (result (ref null ${i32_i64}))
+ ;; CHECK-NEXT:   (ref.null none)
+ ;; CHECK-NEXT:   (struct.new_default ${i32_i64})
+ ;; CHECK-NEXT:   (i32.const 0)
+ ;; CHECK-NEXT:  )
  ;; CHECK-NEXT: )
  ;; NOMNL:      (func $get_null_{i32_i64} (type $none_=>_ref?|${i32_i64}|) (result (ref null ${i32_i64}))
- ;; NOMNL-NEXT:  (ref.null none)
+ ;; NOMNL-NEXT:  (select (result (ref null ${i32_i64}))
+ ;; NOMNL-NEXT:   (ref.null none)
+ ;; NOMNL-NEXT:   (struct.new_default ${i32_i64})
+ ;; NOMNL-NEXT:   (i32.const 0)
+ ;; NOMNL-NEXT:  )
  ;; NOMNL-NEXT: )
  (func $get_null_{i32_i64} (result (ref null ${i32_i64}))
-  (ref.null ${i32_i64})
+  (select
+   (ref.null none)
+   (struct.new_default ${i32_i64})
+   (i32.const 0)
+  )
  )
 
  ;; CHECK:      (func $get_null_{i32_f32} (type $none_=>_ref?|${i32_f32}|) (result (ref null ${i32_f32}))
- ;; CHECK-NEXT:  (ref.null none)
+ ;; CHECK-NEXT:  (select (result (ref null ${i32_f32}))
+ ;; CHECK-NEXT:   (ref.null none)
+ ;; CHECK-NEXT:   (struct.new_default ${i32_f32})
+ ;; CHECK-NEXT:   (i32.const 0)
+ ;; CHECK-NEXT:  )
  ;; CHECK-NEXT: )
  ;; NOMNL:      (func $get_null_{i32_f32} (type $none_=>_ref?|${i32_f32}|) (result (ref null ${i32_f32}))
- ;; NOMNL-NEXT:  (ref.null none)
+ ;; NOMNL-NEXT:  (select (result (ref null ${i32_f32}))
+ ;; NOMNL-NEXT:   (ref.null none)
+ ;; NOMNL-NEXT:   (struct.new_default ${i32_f32})
+ ;; NOMNL-NEXT:   (i32.const 0)
+ ;; NOMNL-NEXT:  )
  ;; NOMNL-NEXT: )
  (func $get_null_{i32_f32} (result (ref null ${i32_f32}))
-  (ref.null ${i32_f32})
+  (select
+   (ref.null none)
+   (struct.new_default ${i32_f32})
+   (i32.const 0)
+  )
  )
 )
diff --git a/test/lit/passes/dae-gc.wast b/test/lit/passes/dae-gc.wast
index 8e55e6ec8..2f023b075 100644
--- a/test/lit/passes/dae-gc.wast
+++ b/test/lit/passes/dae-gc.wast
@@ -157,7 +157,7 @@
  )
 
  ;; CHECK:      (func $bar (type $i31ref_=>_none) (param $0 i31ref)
- ;; CHECK-NEXT:  (local $1 anyref)
+ ;; CHECK-NEXT:  (local $1 nullref)
  ;; CHECK-NEXT:  (local.set $1
  ;; CHECK-NEXT:   (ref.null none)
  ;; CHECK-NEXT:  )
@@ -171,7 +171,7 @@
  ;; CHECK-NEXT:  )
  ;; CHECK-NEXT: )
  ;; NOMNL:      (func $bar (type $i31ref_=>_none) (param $0 i31ref)
- ;; NOMNL-NEXT:  (local $1 anyref)
+ ;; NOMNL-NEXT:  (local $1 nullref)
  ;; NOMNL-NEXT:  (local.set $1
  ;; NOMNL-NEXT:   (ref.null none)
  ;; NOMNL-NEXT:  )
diff --git a/test/lit/passes/global-refining.wast b/test/lit/passes/global-refining.wast
index 2aa803285..06af50bf1 100644
--- a/test/lit/passes/global-refining.wast
+++ b/test/lit/passes/global-refining.wast
@@ -2,14 +2,13 @@
 ;; RUN: foreach %s %t wasm-opt --nominal --global-refining -all -S -o - | filecheck %s
 
 (module
-  ;; Globals with no assignments aside from their initial values. The first is
-  ;; a null, so we have nothing concrete to improve with (though we could use
-  ;; the type of the null perhaps, TODO). The second is a ref.func which lets
-  ;; us refine.
+  ;; Globals with no assignments aside from their initial values. The first is a
+  ;; null, so we can optimize to a nullfuncref. The second is a ref.func which
+  ;; lets us refine to the specific function type.
   ;; CHECK:      (type $foo_t (func))
   (type $foo_t (func))
 
-  ;; CHECK:      (global $func-null-init (mut funcref) (ref.null nofunc))
+  ;; CHECK:      (global $func-null-init (mut nullfuncref) (ref.null nofunc))
   (global $func-null-init (mut funcref) (ref.null $foo_t))
   ;; CHECK:      (global $func-func-init (mut (ref $foo_t)) (ref.func $foo))
   (global $func-func-init (mut funcref) (ref.func $foo))
@@ -26,7 +25,7 @@
   ;; CHECK:      (type $foo_t (func))
   (type $foo_t (func))
 
-  ;; CHECK:      (global $func-null-init (mut funcref) (ref.null nofunc))
+  ;; CHECK:      (global $func-null-init (mut nullfuncref) (ref.null nofunc))
   (global $func-null-init (mut funcref) (ref.null $foo_t))
   ;; CHECK:      (global $func-func-init (mut (ref null $foo_t)) (ref.func $foo))
   (global $func-func-init (mut funcref) (ref.func $foo))
diff --git a/test/lit/passes/signature-refining.wast b/test/lit/passes/signature-refining.wast
index f254a2f63..a17032789 100644
--- a/test/lit/passes/signature-refining.wast
+++ b/test/lit/passes/signature-refining.wast
@@ -508,8 +508,8 @@
   (type $sig-can-refine (func_subtype (result anyref) func))
 
   ;; Also a single function, but no refinement is possible.
-  ;; CHECK:      (type $sig-cannot-refine (func (result anyref)))
-  (type $sig-cannot-refine (func_subtype (result anyref) func))
+  ;; CHECK:      (type $sig-cannot-refine (func (result (ref func))))
+  (type $sig-cannot-refine (func_subtype (result (ref func)) func))
 
   ;; The single function never returns, so no refinement is possible.
   ;; CHECK:      (type $sig-unreachable (func (result anyref)))
@@ -517,7 +517,7 @@
 
   ;; CHECK:      (type $none_=>_none (func))
 
-  ;; CHECK:      (elem declare func $func-can-refine)
+  ;; CHECK:      (elem declare func $func-can-refine $func-cannot-refine)
 
   ;; CHECK:      (func $func-can-refine (type $sig-can-refine) (result (ref $struct))
   ;; CHECK-NEXT:  (struct.new_default $struct)
@@ -526,11 +526,19 @@
     (struct.new $struct)
   )
 
-  ;; CHECK:      (func $func-cannot-refine (type $sig-cannot-refine) (result anyref)
-  ;; CHECK-NEXT:  (ref.null none)
+  ;; CHECK:      (func $func-cannot-refine (type $sig-cannot-refine) (result (ref func))
+  ;; CHECK-NEXT:  (select (result (ref func))
+  ;; CHECK-NEXT:   (ref.func $func-can-refine)
+  ;; CHECK-NEXT:   (ref.func $func-cannot-refine)
+  ;; CHECK-NEXT:   (i32.const 0)
+  ;; CHECK-NEXT:  )
   ;; CHECK-NEXT: )
-  (func $func-cannot-refine (type $sig-cannot-refine) (result anyref)
-    (ref.null any)
+  (func $func-cannot-refine (type $sig-cannot-refine) (result (ref func))
+    (select
+      (ref.func $func-can-refine)
+      (ref.func $func-cannot-refine)
+      (i32.const 0)
+    )
   )
 
   ;; CHECK:      (func $func-unreachable (type $sig-unreachable) (result anyref)
diff --git a/test/lit/passes/type-refining-isorecursive.wast b/test/lit/passes/type-refining-isorecursive.wast
index 3ede5146c..216462b07 100644
--- a/test/lit/passes/type-refining-isorecursive.wast
+++ b/test/lit/passes/type-refining-isorecursive.wast
@@ -5,12 +5,12 @@
  ;; The types should be refined to a set of three mutually recursive types.
 
  ;; CHECK:      (rec
- ;; CHECK-NEXT:  (type $0 (struct (field anyref) (field (ref $1))))
- (type $0 (struct_subtype (ref null any) anyref data))
- ;; CHECK:       (type $1 (struct (field eqref) (field (ref $2))))
- (type $1 (struct_subtype (ref null eq) anyref data))
- ;; CHECK:       (type $2 (struct (field i31ref) (field (ref $0))))
- (type $2 (struct_subtype (ref null i31) anyref data))
+ ;; CHECK-NEXT:  (type $0 (struct (field nullref) (field (ref $1))))
+ (type $0 (struct_subtype nullref anyref data))
+ ;; CHECK:       (type $1 (struct (field nullfuncref) (field (ref $2))))
+ (type $1 (struct_subtype nullfuncref anyref data))
+ ;; CHECK:       (type $2 (struct (field nullexternref) (field (ref $0))))
+ (type $2 (struct_subtype nullexternref anyref data))
 
  ;; CHECK:       (type $ref|$0|_ref|$1|_ref|$2|_=>_none (func (param (ref $0) (ref $1) (ref $2))))
 
@@ -23,13 +23,13 @@
  ;; CHECK-NEXT:  )
  ;; CHECK-NEXT:  (drop
  ;; CHECK-NEXT:   (struct.new $1
- ;; CHECK-NEXT:    (ref.null none)
+ ;; CHECK-NEXT:    (ref.null nofunc)
  ;; CHECK-NEXT:    (local.get $z)
  ;; CHECK-NEXT:   )
  ;; CHECK-NEXT:  )
  ;; CHECK-NEXT:  (drop
  ;; CHECK-NEXT:   (struct.new $2
- ;; CHECK-NEXT:    (ref.null none)
+ ;; CHECK-NEXT:    (ref.null noextern)
  ;; CHECK-NEXT:    (local.get $x)
  ;; CHECK-NEXT:   )
  ;; CHECK-NEXT:  )
@@ -37,19 +37,19 @@
  (func $foo (param $x (ref $0)) (param $y (ref $1)) (param $z (ref $2))
   (drop
    (struct.new $0
-    (ref.null any)
+    (ref.null none)
     (local.get $y)
    )
   )
   (drop
    (struct.new $1
-    (ref.null eq)
+    (ref.null nofunc)
     (local.get $z)
    )
   )
   (drop
    (struct.new $2
-    (ref.null i31)
+    (ref.null noextern)
     (local.get $x)
    )
   )
@@ -65,12 +65,12 @@
  ;; CHECK-NEXT:  (type $all (struct (field i32) (field (ref $0)) (field (ref $1)) (field (ref $2))))
  (type $all (struct_subtype i32 anyref anyref anyref data))
 
- ;; CHECK:       (type $0 (struct (field anyref) (field (ref null $all)) (field (ref $0))))
- (type $0 (struct_subtype (ref null any) anyref anyref data))
- ;; CHECK:       (type $1 (struct_subtype (field eqref) (field (ref null $all)) (field (ref $0)) $0))
- (type $1 (struct_subtype (ref null eq) anyref anyref $0))
- ;; CHECK:       (type $2 (struct_subtype (field i31ref) (field (ref null $all)) (field (ref $0)) $1))
- (type $2 (struct_subtype (ref null i31) anyref anyref $1))
+ ;; CHECK:       (type $0 (struct (field (ref null $all)) (field (ref $0))))
+ (type $0 (struct_subtype anyref anyref data))
+ ;; CHECK:       (type $1 (struct_subtype (field (ref null $all)) (field (ref $0)) $0))
+ (type $1 (struct_subtype anyref anyref $0))
+ ;; CHECK:       (type $2 (struct_subtype (field (ref null $all)) (field (ref $0)) $1))
+ (type $2 (struct_subtype anyref anyref $1))
 
  ;; CHECK:       (type $ref|$0|_ref|$1|_ref|$2|_=>_none (func (param (ref $0) (ref $1) (ref $2))))
 
@@ -86,21 +86,18 @@
  ;; CHECK-NEXT:  )
  ;; CHECK-NEXT:  (drop
  ;; CHECK-NEXT:   (struct.new $0
- ;; CHECK-NEXT:    (ref.null none)
  ;; CHECK-NEXT:    (local.get $all)
  ;; CHECK-NEXT:    (local.get $y)
  ;; CHECK-NEXT:   )
  ;; CHECK-NEXT:  )
  ;; CHECK-NEXT:  (drop
  ;; CHECK-NEXT:   (struct.new $1
- ;; CHECK-NEXT:    (ref.null none)
  ;; CHECK-NEXT:    (local.get $all)
  ;; CHECK-NEXT:    (local.get $z)
  ;; CHECK-NEXT:   )
  ;; CHECK-NEXT:  )
  ;; CHECK-NEXT:  (drop
  ;; CHECK-NEXT:   (struct.new $2
- ;; CHECK-NEXT:    (ref.null none)
  ;; CHECK-NEXT:    (local.get $all)
  ;; CHECK-NEXT:    (local.get $x)
  ;; CHECK-NEXT:   )
@@ -118,21 +115,18 @@
   )
   (drop
    (struct.new $0
-    (ref.null any)
     (local.get $all)
     (local.get $y)
    )
   )
   (drop
    (struct.new $1
-    (ref.null eq)
     (local.get $all)
     (local.get $z)
    )
   )
   (drop
    (struct.new $2
-    (ref.null i31)
     (local.get $all)
     (local.get $x)
    )
diff --git a/test/lit/passes/type-refining.wast b/test/lit/passes/type-refining.wast
index 082f16bfb..f6d7ec7b2 100644
--- a/test/lit/passes/type-refining.wast
+++ b/test/lit/passes/type-refining.wast
@@ -5,15 +5,17 @@
   ;; A struct with three fields. The first will have no writes, the second one
   ;; write of the same type, and the last a write of a subtype, which will allow
   ;; us to specialize that one.
-  ;; CHECK:      (type $struct (struct (field (mut anyref)) (field (mut anyref)) (field (mut (ref i31)))))
-  (type $struct (struct_subtype (field (mut anyref)) (field (mut anyref)) (field (mut anyref)) data))
+  ;; CHECK:      (type $struct (struct (field (mut anyref)) (field (mut (ref i31))) (field (mut (ref i31)))))
+  (type $struct (struct_subtype (field (mut anyref)) (field (mut (ref i31))) (field (mut anyref)) data))
 
   ;; CHECK:      (type $ref|$struct|_=>_none (func (param (ref $struct))))
 
   ;; CHECK:      (func $work (type $ref|$struct|_=>_none) (param $struct (ref $struct))
   ;; CHECK-NEXT:  (struct.set $struct 1
   ;; CHECK-NEXT:   (local.get $struct)
-  ;; CHECK-NEXT:   (ref.null none)
+  ;; CHECK-NEXT:   (i31.new
+  ;; CHECK-NEXT:    (i32.const 0)
+  ;; CHECK-NEXT:   )
   ;; CHECK-NEXT:  )
   ;; CHECK-NEXT:  (struct.set $struct 2
   ;; CHECK-NEXT:   (local.get $struct)
@@ -30,7 +32,7 @@
   (func $work (param $struct (ref $struct))
     (struct.set $struct 1
       (local.get $struct)
-      (ref.null any)
+      (i31.new (i32.const 0))
     )
     (struct.set $struct 2
       (local.get $struct)
@@ -655,7 +657,7 @@
 )
 
 (module
-  ;; CHECK:      (type $struct (struct (field (mut dataref))))
+  ;; CHECK:      (type $struct (struct (field (mut nullref))))
   (type $struct (struct_subtype (field (mut (ref null data))) data))
 
   ;; CHECK:      (type $ref|$struct|_=>_none (func (param (ref $struct))))
@@ -666,8 +668,8 @@
   ;; CHECK-NEXT:  )
   ;; CHECK-NEXT: )
   (func $work (param $struct (ref $struct))
-    ;; The only write to this struct is of a null default value. There is
-    ;; nothing to optimize here.
+    ;; The only write to this struct is of a null default value, so we can
+    ;; optimize to nullref.
     (drop
       (struct.new_default $struct)
     )