Implement bottom heap types (#5115)

These types, `none`, `nofunc`, and `noextern` are uninhabited, so references to
them can only possibly be null. To simplify the IR and increase type precision,
introduce new invariants that all `ref.null` instructions must be typed with one
of these new bottom types and that `Literals` have a bottom type iff they
represent null values. These new invariants requires several additional changes.

First, it is now possible that the `ref` or `target` child of a `StructGet`,
`StructSet`, `ArrayGet`, `ArraySet`, or `CallRef` instruction has a bottom
reference type, so it is not possible to determine what heap type annotation to
emit in the binary or text formats. (The bottom types are not valid type
annotations since they do not have indices in the type section.)

To fix that problem, update the printer and binary emitter to emit unreachables
instead of the instruction with undetermined type annotation. This is a valid
transformation because the only possible value that could flow into those
instructions in that case is null, and all of those instructions trap on nulls.

That fix uncovered a latent bug in the binary parser in which new unreachables
within unreachable code were handled incorrectly. This bug was not previously
found by the fuzzer because we generally stop emitting code once we encounter an
instruction with type `unreachable`. Now, however, it is possible to emit an
`unreachable` for instructions that do not have type `unreachable` (but are
known to trap at runtime), so we will continue emitting code. See the new
test/lit/parse-double-unreachable.wast for details.

Update other miscellaneous code that creates `RefNull` expressions and null
`Literals` to maintain the new invariants as well.

7 files changed, 60 insertions, 60 deletions

diff --git a/test/passes/Oz_fuzz-exec_all-features.txt b/test/passes/Oz_fuzz-exec_all-features.txt
index b3c8b936a..e19110848 100644
--- a/test/passes/Oz_fuzz-exec_all-features.txt
+++ b/test/passes/Oz_fuzz-exec_all-features.txt
@@ -173,7 +173,7 @@
    (struct.new_default $struct)
   )
   (drop
-   (block $any (result anyref)
+   (block $any (result (ref null $struct))
     (call $log
      (i32.const 1)
     )
@@ -185,7 +185,7 @@
     (call $log
      (i32.const 999)
     )
-    (ref.null any)
+    (ref.null none)
    )
   )
  )
diff --git a/test/passes/precompute_all-features.txt b/test/passes/precompute_all-features.txt
index 1fbea9d64..ea582d8d4 100644
--- a/test/passes/precompute_all-features.txt
+++ b/test/passes/precompute_all-features.txt
@@ -254,7 +254,7 @@
   (i32.const 1)
  )
  (func $reftype-test (result externref)
-  (ref.null extern)
+  (ref.null noextern)
  )
  (func $dummy
   (nop)
@@ -276,22 +276,22 @@
    )
   )
   (drop
-   (block $l2 (result externref)
+   (block $l2 (result nullexternref)
     (drop
      (block $l3
       (global.set $global-mut
        (i32.const 1)
       )
       (br $l2
-       (ref.null extern)
+       (ref.null noextern)
       )
      )
     )
-    (ref.null extern)
+    (ref.null noextern)
    )
   )
   (drop
-   (block $l4 (result funcref)
+   (block $l4 (result (ref null $none_=>_none))
     (drop
      (block $l5
       (global.set $global-mut
@@ -302,7 +302,7 @@
       )
      )
     )
-    (ref.null func)
+    (ref.null nofunc)
    )
   )
  )
diff --git a/test/passes/remove-unused-brs_all-features.txt b/test/passes/remove-unused-brs_all-features.txt
index c340519f8..ab3ead0f4 100644
--- a/test/passes/remove-unused-brs_all-features.txt
+++ b/test/passes/remove-unused-brs_all-features.txt
@@ -18,7 +18,7 @@
      (i32.const 1)
     )
    )
-   (ref.null $struct)
+   (ref.null none)
   )
  )
  (func $test-prefinalize (result f64)
@@ -136,59 +136,59 @@
  )
  (func $br_on-to-flow
   (drop
-   (block $data (result dataref)
+   (block $data (result nullref)
     (drop
      (ref.func $br_on-to-flow)
     )
-    (ref.null data)
+    (ref.null none)
    )
   )
   (drop
-   (block $datab (result dataref)
+   (block $datab (result nullref)
     (drop
      (i31.new
       (i32.const 1337)
      )
     )
-    (ref.null data)
+    (ref.null none)
    )
   )
   (drop
-   (block $func (result funcref)
+   (block $func (result nullfuncref)
     (drop
      (array.new_default $vector
       (i32.const 2)
      )
     )
-    (ref.null func)
+    (ref.null nofunc)
    )
   )
   (drop
-   (block $funcb (result funcref)
+   (block $funcb (result nullfuncref)
     (drop
      (i31.new
       (i32.const 1337)
      )
     )
-    (ref.null func)
+    (ref.null nofunc)
    )
   )
   (drop
-   (block $i31 (result i31ref)
+   (block $i31 (result nullref)
     (drop
      (array.new_default $vector
       (i32.const 2)
      )
     )
-    (ref.null i31)
+    (ref.null none)
    )
   )
   (drop
-   (block $i31b (result i31ref)
+   (block $i31b (result nullref)
     (drop
      (ref.func $br_on-to-flow)
     )
-    (ref.null i31)
+    (ref.null none)
    )
   )
  )
diff --git a/test/passes/simplify-globals_all-features.txt b/test/passes/simplify-globals_all-features.txt
index ace056aac..d94ac55d3 100644
--- a/test/passes/simplify-globals_all-features.txt
+++ b/test/passes/simplify-globals_all-features.txt
@@ -215,7 +215,7 @@
  (type $none_=>_none (func))
  (import "env" "global-1" (global $g1 externref))
  (global $g2 externref (global.get $g1))
- (global $g3 externref (ref.null extern))
+ (global $g3 externref (ref.null noextern))
  (func $test1
   (drop
    (global.get $g1)
@@ -226,7 +226,7 @@
  )
  (func $test2
   (drop
-   (ref.null extern)
+   (ref.null noextern)
   )
  )
 )
diff --git a/test/passes/simplify-globals_all-features_fuzz-exec.txt b/test/passes/simplify-globals_all-features_fuzz-exec.txt
index d38d06704..f4e2df478 100644
--- a/test/passes/simplify-globals_all-features_fuzz-exec.txt
+++ b/test/passes/simplify-globals_all-features_fuzz-exec.txt
@@ -3,7 +3,7 @@
 (module
  (type $f32_i31ref_i64_f64_funcref_=>_none (func (param f32 i31ref i64 f64 funcref)))
  (type $none_=>_funcref (func (result funcref)))
- (global $global$0 (mut funcref) (ref.null func))
+ (global $global$0 (mut funcref) (ref.null nofunc))
  (elem declare func $0)
  (export "export" (func $1))
  (func $0 (param $0 f32) (param $1 i31ref) (param $2 i64) (param $3 f64) (param $4 funcref)
diff --git a/test/passes/strip-target-features_roundtrip_print-features_all-features.txt b/test/passes/strip-target-features_roundtrip_print-features_all-features.txt
index b460f8801..8e2d73001 100644
--- a/test/passes/strip-target-features_roundtrip_print-features_all-features.txt
+++ b/test/passes/strip-target-features_roundtrip_print-features_all-features.txt
@@ -19,7 +19,7 @@
  (func $foo (result v128 externref)
   (tuple.make
    (v128.const i32x4 0x00000000 0x00000000 0x00000000 0x00000000)
-   (ref.null extern)
+   (ref.null noextern)
   )
  )
  (func $bar (result v128 externref)
diff --git a/test/passes/translate-to-fuzz_all-features_metrics_noprint.txt b/test/passes/translate-to-fuzz_all-features_metrics_noprint.txt
index 927c07bca..e984e8be5 100644
--- a/test/passes/translate-to-fuzz_all-features_metrics_noprint.txt
+++ b/test/passes/translate-to-fuzz_all-features_metrics_noprint.txt
@@ -1,45 +1,45 @@
 total
- [exports]      : 14      
- [funcs]        : 19      
+ [exports]      : 7       
+ [funcs]        : 7       
  [globals]      : 6       
  [imports]      : 5       
  [memories]     : 1       
  [memory-data]  : 22      
- [table-data]   : 12      
+ [table-data]   : 8       
  [tables]       : 1       
  [tags]         : 2       
- [total]        : 771     
- [vars]         : 27      
- ArrayInit      : 1       
- AtomicCmpxchg  : 1       
- AtomicFence    : 1       
+ [total]        : 433     
+ [vars]         : 6       
  AtomicRMW      : 1       
- Binary         : 82      
- Block          : 105     
- Break          : 19      
- Call           : 23      
- CallIndirect   : 3       
- CallRef        : 2       
- Const          : 145     
- DataDrop       : 1       
- Drop           : 7       
- GlobalGet      : 65      
- GlobalSet      : 31      
- I31New         : 3       
- If             : 35      
- Load           : 21      
- LocalGet       : 48      
- LocalSet       : 26      
- Loop           : 12      
- Nop            : 16      
- RefEq          : 1       
- RefFunc        : 17      
- RefNull        : 4       
- Return         : 35      
+ Binary         : 56      
+ Block          : 36      
+ Break          : 4       
+ Call           : 22      
+ CallRef        : 8       
+ Const          : 113     
+ Drop           : 5       
+ GlobalGet      : 24      
+ GlobalSet      : 11      
+ I31Get         : 2       
+ I31New         : 7       
+ If             : 14      
+ Load           : 17      
+ LocalGet       : 24      
+ LocalSet       : 17      
+ Loop           : 4       
+ MemoryFill     : 1       
+ Nop            : 1       
+ RefEq          : 2       
+ RefFunc        : 18      
+ RefIs          : 1       
+ RefNull        : 2       
+ Return         : 12      
  SIMDExtract    : 1       
- Select         : 1       
- Store          : 6       
+ SIMDLoad       : 1       
+ Select         : 7       
+ Store          : 2       
  StructNew      : 1       
- TupleExtract   : 2       
- TupleMake      : 8       
- Unary          : 47      
+ Switch         : 1       
+ TupleMake      : 2       
+ Unary          : 13      
+ Unreachable    : 3