Handle concrete values in CodeFolding (#7117)

CodeFolding previously only worked on blocks that did not produce
values. It worked on Ifs that produced values, but only by accident; the
logic for folding matching tails was not written to support tails
producing concrete values, but it happened to work for Ifs because
subsequent ReFinalize runs fixed all the incorrect types it produced.

Improve the power of the optimization by explicitly handling tails that
produce concrete values for both blocks and ifs. Now that the core logic
handles concrete values correctly, remove the unnecessary ReFinalize
run.

Also remove the separate optimization of Ifs with identical arms; this
optimization requires ReFinalize and is already performed by
OptimizeInstructions.

1 files changed, 457 insertions, 49 deletions

diff --git a/test/lit/passes/code-folding.wast b/test/lit/passes/code-folding.wast
index 358167481..007aa5909 100644
--- a/test/lit/passes/code-folding.wast
+++ b/test/lit/passes/code-folding.wast
@@ -1,18 +1,32 @@
 ;; NOTE: Assertions have been generated by update_lit_checks.py --all-items and should not be edited.
 ;; NOTE: This test was ported using port_passes_tests_to_lit.py and could be cleaned up.
 
-;; RUN: foreach %s %t wasm-opt -all --code-folding -S -o - | filecheck %s
+;; RUN: wasm-opt %s -all --code-folding -S -o - | filecheck %s
 
 (module
  ;; CHECK:      (type $0 (func))
 
  ;; CHECK:      (type $1 (func (result f32)))
 
+ ;; CHECK:      (type $2 (func (result i32)))
+
+ ;; CHECK:      (type $3 (func (result anyref)))
+
  ;; CHECK:      (type $13 (func (param f32)))
  (type $13 (func (param f32)))
  (table 282 282 funcref)
+ ;; CHECK:      (type $5 (func (param i32)))
+
+ ;; CHECK:      (global $global$0 (mut i32) (i32.const 10))
+
  ;; CHECK:      (memory $0 1 1)
  (memory $0 1 1)
+
+ ;; CHECK:      (memory $shared 1 1 shared)
+ (memory $shared 1 1 shared)
+
+ (global $global$0 (mut i32) (i32.const 10))
+
  ;; CHECK:      (table $0 282 282 funcref)
 
  ;; CHECK:      (func $0 (type $0)
@@ -22,7 +36,7 @@
  ;; CHECK-NEXT:    (then
  ;; CHECK-NEXT:     (block $label$3
  ;; CHECK-NEXT:      (call_indirect $0 (type $13)
- ;; CHECK-NEXT:       (block $label$4
+ ;; CHECK-NEXT:       (block $label$4 (result f32)
  ;; CHECK-NEXT:        (br $label$3)
  ;; CHECK-NEXT:       )
  ;; CHECK-NEXT:       (i32.const 105)
@@ -52,18 +66,15 @@
    )
   )
  )
+
  ;; CHECK:      (func $negative-zero (type $1) (result f32)
  ;; CHECK-NEXT:  (if (result f32)
  ;; CHECK-NEXT:   (i32.const 0)
  ;; CHECK-NEXT:   (then
- ;; CHECK-NEXT:    (block $label$0 (result f32)
- ;; CHECK-NEXT:     (f32.const 0)
- ;; CHECK-NEXT:    )
+ ;; CHECK-NEXT:    (f32.const 0)
  ;; CHECK-NEXT:   )
  ;; CHECK-NEXT:   (else
- ;; CHECK-NEXT:    (block $label$1 (result f32)
- ;; CHECK-NEXT:     (f32.const -0)
- ;; CHECK-NEXT:    )
+ ;; CHECK-NEXT:    (f32.const -0)
  ;; CHECK-NEXT:   )
  ;; CHECK-NEXT:  )
  ;; CHECK-NEXT: )
@@ -71,63 +82,173 @@
   (if (result f32)
    (i32.const 0)
    (then
-    (block $label$0 (result f32)
+    (block (result f32)
      (f32.const 0)
     )
    )
    (else
-    (block $label$1 (result f32)
+    (block (result f32)
      (f32.const -0)
     )
    )
   )
  )
+
  ;; CHECK:      (func $negative-zero-b (type $1) (result f32)
  ;; CHECK-NEXT:  (drop
  ;; CHECK-NEXT:   (i32.const 0)
  ;; CHECK-NEXT:  )
- ;; CHECK-NEXT:  (block $label$0 (result f32)
- ;; CHECK-NEXT:   (f32.const -0)
- ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT:  (f32.const -0)
  ;; CHECK-NEXT: )
  (func $negative-zero-b (result f32)
   (if (result f32)
    (i32.const 0)
    (then
-    (block $label$0 (result f32)
+    (block (result f32)
      (f32.const -0)
     )
    )
    (else
-    (block $label$1 (result f32)
+    (block (result f32)
      (f32.const -0)
     )
    )
   )
  )
- ;; CHECK:      (func $negative-zero-c (type $1) (result f32)
- ;; CHECK-NEXT:  (drop
+
+ ;; CHECK:      (func $positive-zero (type $1) (result f32)
+ ;; CHECK-NEXT:  (if (result f32)
  ;; CHECK-NEXT:   (i32.const 0)
+ ;; CHECK-NEXT:   (then
+ ;; CHECK-NEXT:    (f32.const 0)
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:   (else
+ ;; CHECK-NEXT:    (f32.const 0)
+ ;; CHECK-NEXT:   )
  ;; CHECK-NEXT:  )
- ;; CHECK-NEXT:  (block $label$0 (result f32)
- ;; CHECK-NEXT:   (f32.const 0)
+ ;; CHECK-NEXT: )
+ (func $positive-zero (result f32)
+  ;; This doesn't get optimized because we only look at Ifs with block arms.
+  ;; This simpler case will be optimized by OptimizeInstructions.
+  (if (result f32)
+   (i32.const 0)
+   (then
+    (f32.const 0)
+   )
+   (else
+    (f32.const 0)
+   )
+  )
+ )
+
+ ;; CHECK:      (func $positive-zero-names (type $1) (result f32)
+ ;; CHECK-NEXT:  (if (result f32)
+ ;; CHECK-NEXT:   (i32.const 0)
+ ;; CHECK-NEXT:   (then
+ ;; CHECK-NEXT:    (block $l1 (result f32)
+ ;; CHECK-NEXT:     (f32.const 0)
+ ;; CHECK-NEXT:    )
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:   (else
+ ;; CHECK-NEXT:    (block $l2 (result f32)
+ ;; CHECK-NEXT:     (f32.const 0)
+ ;; CHECK-NEXT:    )
+ ;; CHECK-NEXT:   )
  ;; CHECK-NEXT:  )
  ;; CHECK-NEXT: )
- (func $negative-zero-c (result f32)
+ (func $positive-zero-names (result f32)
+  ;; This one has block arms, but doesn't get optimized because the blocks have
+  ;; names.
   (if (result f32)
    (i32.const 0)
    (then
-    (block $label$0 (result f32)
+    (block $l1 (result f32)
      (f32.const 0)
     )
    )
    (else
-    (block $label$1 (result f32)
+    (block $l2 (result f32)
      (f32.const 0)
     )
    )
   )
  )
+
+ ;; CHECK:      (func $positive-zero-extra-a (type $1) (result f32)
+ ;; CHECK-NEXT:  (if
+ ;; CHECK-NEXT:   (i32.const 0)
+ ;; CHECK-NEXT:   (then
+ ;; CHECK-NEXT:    (nop)
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:   (else
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT:  (f32.const 0)
+ ;; CHECK-NEXT: )
+ (func $positive-zero-extra-a (result f32)
+  (if (result f32)
+   (i32.const 0)
+   (then
+    (nop)
+    (f32.const 0)
+   )
+   (else
+    (f32.const 0)
+   )
+  )
+ )
+
+ ;; CHECK:      (func $positive-zero-extra-b (type $1) (result f32)
+ ;; CHECK-NEXT:  (if
+ ;; CHECK-NEXT:   (i32.const 0)
+ ;; CHECK-NEXT:   (then
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:   (else
+ ;; CHECK-NEXT:    (nop)
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT:  (f32.const 0)
+ ;; CHECK-NEXT: )
+ (func $positive-zero-extra-b (result f32)
+  (if (result f32)
+   (i32.const 0)
+   (then
+    (f32.const 0)
+   )
+   (else
+    (nop)
+    (f32.const 0)
+   )
+  )
+ )
+
+ ;; CHECK:      (func $positive-zero-extra-c (type $1) (result f32)
+ ;; CHECK-NEXT:  (if
+ ;; CHECK-NEXT:   (i32.const 0)
+ ;; CHECK-NEXT:   (then
+ ;; CHECK-NEXT:    (nop)
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:   (else
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT:  (nop)
+ ;; CHECK-NEXT:  (f32.const 0)
+ ;; CHECK-NEXT: )
+ (func $positive-zero-extra-c (result f32)
+  (if (result f32)
+   (i32.const 0)
+   (then
+    (nop)
+    (nop)
+    (f32.const 0)
+   )
+   (else
+    (nop)
+    (f32.const 0)
+   )
+  )
+ )
+
  ;; CHECK:      (func $break-target-outside-of-return-merged-code (type $0)
  ;; CHECK-NEXT:  (block $label$A
  ;; CHECK-NEXT:   (if
@@ -202,6 +323,7 @@
    )
   )
  )
+
  ;; CHECK:      (func $break-target-inside-all-good (type $0)
  ;; CHECK-NEXT:  (block $folding-inner0
  ;; CHECK-NEXT:   (block $label$A
@@ -269,11 +391,12 @@
    )
   )
  )
+
  ;; CHECK:      (func $leave-inner-block-type (type $0)
  ;; CHECK-NEXT:  (block $label$1
  ;; CHECK-NEXT:   (drop
- ;; CHECK-NEXT:    (block $label$2
- ;; CHECK-NEXT:     (block
+ ;; CHECK-NEXT:    (block $label$2 (result i32)
+ ;; CHECK-NEXT:     (br_if $label$2
  ;; CHECK-NEXT:      (unreachable)
  ;; CHECK-NEXT:      (unreachable)
  ;; CHECK-NEXT:     )
@@ -304,54 +427,40 @@
    )
   )
  )
-)
-(module
- ;; CHECK:      (type $0 (func (result i32)))
 
- ;; CHECK:      (memory $0 1 1 shared)
- (memory $0 1 1 shared)
- ;; CHECK:      (export "func_2224" (func $0))
- (export "func_2224" (func $0))
- ;; CHECK:      (func $0 (type $0) (result i32)
+ ;; CHECK:      (func $atomic-load-different (type $2) (result i32)
  ;; CHECK-NEXT:  (local $var$0 i32)
  ;; CHECK-NEXT:  (if (result i32)
  ;; CHECK-NEXT:   (i32.const 0)
  ;; CHECK-NEXT:   (then
- ;; CHECK-NEXT:    (i32.load offset=22
+ ;; CHECK-NEXT:    (i32.load $shared offset=22
  ;; CHECK-NEXT:     (local.get $var$0)
  ;; CHECK-NEXT:    )
  ;; CHECK-NEXT:   )
  ;; CHECK-NEXT:   (else
- ;; CHECK-NEXT:    (i32.atomic.load offset=22
+ ;; CHECK-NEXT:    (i32.atomic.load $shared offset=22
  ;; CHECK-NEXT:     (local.get $var$0)
  ;; CHECK-NEXT:    )
  ;; CHECK-NEXT:   )
  ;; CHECK-NEXT:  )
  ;; CHECK-NEXT: )
- (func $0 (result i32)
+ (func $atomic-load-different (result i32)
   (local $var$0 i32)
   (if (result i32)
    (i32.const 0)
    (then
-    (i32.load offset=22
+    (i32.load $shared offset=22
      (local.get $var$0)
     )
    )
    (else
-    (i32.atomic.load offset=22
+    (i32.atomic.load $shared offset=22
      (local.get $var$0)
     )
    )
   )
  )
-)
-(module
- ;; CHECK:      (type $0 (func))
- (type $0 (func))
- ;; CHECK:      (type $1 (func (param i32)))
 
- ;; CHECK:      (global $global$0 (mut i32) (i32.const 10))
- (global $global$0 (mut i32) (i32.const 10))
  ;; CHECK:      (func $determinism (type $0)
  ;; CHECK-NEXT:  (block $folding-inner0
  ;; CHECK-NEXT:   (block
@@ -390,7 +499,7 @@
  ;; CHECK-NEXT:  )
  ;; CHECK-NEXT:  (unreachable)
  ;; CHECK-NEXT: )
- (func $determinism (; 0 ;) (type $0)
+ (func $determinism
   (block $label$1
    (br_if $label$1
     (i32.const 1)
@@ -439,7 +548,8 @@
   )
   (unreachable)
  )
- ;; CHECK:      (func $careful-of-the-switch (type $1) (param $0 i32)
+
+ ;; CHECK:      (func $careful-of-the-switch (type $5) (param $0 i32)
  ;; CHECK-NEXT:  (block $label$1
  ;; CHECK-NEXT:   (block $label$3
  ;; CHECK-NEXT:    (block $label$5
@@ -481,10 +591,243 @@
     (unreachable)
   )
  )
-)
 
-(module
- ;; CHECK:      (type $0 (func))
+ ;; CHECK:      (func $br-with-value (type $2) (result i32)
+ ;; CHECK-NEXT:  (block $l
+ ;; CHECK-NEXT:   (block
+ ;; CHECK-NEXT:    (br $l)
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:   (block
+ ;; CHECK-NEXT:    (br $l)
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:   (drop
+ ;; CHECK-NEXT:    (i32.const 1)
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT:  (i32.const 1)
+ ;; CHECK-NEXT: )
+ (func $br-with-value (result i32)
+  (block $l (result i32)
+   (block
+    (br $l
+     (i32.const 1)
+    )
+   )
+   (block
+    (br $l
+     (i32.const 1)
+    )
+   )
+   (i32.const 1)
+  )
+ )
+
+ ;; CHECK:      (func $br-and-fallthrough-with-value (type $2) (result i32)
+ ;; CHECK-NEXT:  (block $l
+ ;; CHECK-NEXT:   (drop
+ ;; CHECK-NEXT:    (block (result i32)
+ ;; CHECK-NEXT:     (br $l)
+ ;; CHECK-NEXT:    )
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:   (drop
+ ;; CHECK-NEXT:    (block (result i32)
+ ;; CHECK-NEXT:     (br $l)
+ ;; CHECK-NEXT:    )
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT:  (i32.const 1)
+ ;; CHECK-NEXT: )
+ (func $br-and-fallthrough-with-value (result i32)
+  (block $l (result i32)
+   (drop
+    (block (result i32)
+     (br $l
+      (i32.const 1)
+     )
+    )
+   )
+   (drop
+    (block (result i32)
+     (br $l
+      (i32.const 1)
+     )
+    )
+   )
+   (i32.const 1)
+  )
+ )
+
+ ;; CHECK:      (func $br-with-value-and-more (type $2) (result i32)
+ ;; CHECK-NEXT:  (block $l
+ ;; CHECK-NEXT:   (block
+ ;; CHECK-NEXT:    (br $l)
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:   (block
+ ;; CHECK-NEXT:    (nop)
+ ;; CHECK-NEXT:    (br $l)
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:   (nop)
+ ;; CHECK-NEXT:   (drop
+ ;; CHECK-NEXT:    (i32.const 1)
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT:  (nop)
+ ;; CHECK-NEXT:  (nop)
+ ;; CHECK-NEXT:  (i32.const 1)
+ ;; CHECK-NEXT: )
+ (func $br-with-value-and-more (result i32)
+  (block $l (result i32)
+   (block
+    (nop)
+    (nop)
+    (br $l
+     (i32.const 1)
+    )
+   )
+   (block
+    (nop)
+    (nop)
+    (nop)
+    (br $l
+     (i32.const 1)
+    )
+   )
+   (nop)
+   (i32.const 1)
+  )
+ )
+
+ ;; CHECK:      (func $br-and-fallthrough-with-value-and-more (type $2) (result i32)
+ ;; CHECK-NEXT:  (block $l
+ ;; CHECK-NEXT:   (drop
+ ;; CHECK-NEXT:    (block (result i32)
+ ;; CHECK-NEXT:     (nop)
+ ;; CHECK-NEXT:     (br $l)
+ ;; CHECK-NEXT:    )
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:   (drop
+ ;; CHECK-NEXT:    (block (result i32)
+ ;; CHECK-NEXT:     (nop)
+ ;; CHECK-NEXT:     (nop)
+ ;; CHECK-NEXT:     (br $l)
+ ;; CHECK-NEXT:    )
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT:  (nop)
+ ;; CHECK-NEXT:  (i32.const 1)
+ ;; CHECK-NEXT: )
+ (func $br-and-fallthrough-with-value-and-more (result i32)
+  (block $l (result i32)
+   (drop
+    (block (result i32)
+     (nop)
+     (nop)
+     (br $l
+      (i32.const 1)
+     )
+    )
+   )
+   (drop
+    (block (result i32)
+     (nop)
+     (nop)
+     (nop)
+     (br $l
+      (i32.const 1)
+     )
+    )
+   )
+   (nop)
+   (i32.const 1)
+  )
+ )
+
+ ;; CHECK:      (func $unreachable-if (type $0)
+ ;; CHECK-NEXT:  (drop
+ ;; CHECK-NEXT:   (unreachable)
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT:  (nop)
+ ;; CHECK-NEXT:  (drop
+ ;; CHECK-NEXT:   (i32.const 1)
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT: )
+ (func $unreachable-if
+  (if
+   (unreachable)
+   (then
+    (nop)
+    (drop
+     (i32.const 1)
+    )
+   )
+   (else
+    (nop)
+    (drop
+     (i32.const 1)
+    )
+   )
+  )
+ )
+
+ ;; CHECK:      (func $unreachable-if-suffix (type $0)
+ ;; CHECK-NEXT:  (if
+ ;; CHECK-NEXT:   (unreachable)
+ ;; CHECK-NEXT:   (then
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:   (else
+ ;; CHECK-NEXT:    (nop)
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT:  (drop
+ ;; CHECK-NEXT:   (i32.const 1)
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT: )
+ (func $unreachable-if-suffix
+  (if
+   (unreachable)
+   (then
+    (drop
+     (i32.const 1)
+    )
+   )
+   (else
+    (nop)
+    (drop
+     (i32.const 1)
+    )
+   )
+  )
+ )
+
+ ;; CHECK:      (func $unreachable-if-concrete-arms (type $0)
+ ;; CHECK-NEXT:  (drop
+ ;; CHECK-NEXT:   (block (result i32)
+ ;; CHECK-NEXT:    (if
+ ;; CHECK-NEXT:     (unreachable)
+ ;; CHECK-NEXT:     (then
+ ;; CHECK-NEXT:     )
+ ;; CHECK-NEXT:     (else
+ ;; CHECK-NEXT:      (nop)
+ ;; CHECK-NEXT:     )
+ ;; CHECK-NEXT:    )
+ ;; CHECK-NEXT:    (i32.const 1)
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT:  (unreachable)
+ ;; CHECK-NEXT: )
+ (func $unreachable-if-concrete-arms
+  (if (result i32)
+   (unreachable)
+   (then
+    (i32.const 1)
+   )
+   (else
+    (nop)
+    (i32.const 1)
+   )
+  )
+  (unreachable)
+ )
 
  ;; CHECK:      (func $br-on-null (type $0)
  ;; CHECK-NEXT:  (block $block
@@ -520,4 +863,69 @@
    (call $br-on-null)
   )
  )
+
+ ;; CHECK:      (func $refined-type (type $3) (result anyref)
+ ;; CHECK-NEXT:  (select (result anyref)
+ ;; CHECK-NEXT:   (if (result anyref)
+ ;; CHECK-NEXT:    (i32.const 0)
+ ;; CHECK-NEXT:    (then
+ ;; CHECK-NEXT:     (ref.null none)
+ ;; CHECK-NEXT:    )
+ ;; CHECK-NEXT:    (else
+ ;; CHECK-NEXT:     (ref.null none)
+ ;; CHECK-NEXT:    )
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:   (ref.null none)
+ ;; CHECK-NEXT:   (i32.const 0)
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT: )
+ (func $refined-type (result anyref)
+  (select (result anyref)
+   ;; If we fold the identical arms, the select will have a stale type.
+   (if (result anyref)
+    (i32.const 0)
+    (then
+     (ref.null none)
+    )
+    (else
+     (ref.null none)
+    )
+   )
+   (ref.null none)
+   (i32.const 0)
+  )
+ )
+
+ ;; CHECK:      (func $refined-type-blocks (type $3) (result anyref)
+ ;; CHECK-NEXT:  (select (result anyref)
+ ;; CHECK-NEXT:   (block (result anyref)
+ ;; CHECK-NEXT:    (drop
+ ;; CHECK-NEXT:     (i32.const 0)
+ ;; CHECK-NEXT:    )
+ ;; CHECK-NEXT:    (nop)
+ ;; CHECK-NEXT:    (ref.null none)
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:   (ref.null none)
+ ;; CHECK-NEXT:   (i32.const 0)
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT: )
+ (func $refined-type-blocks (result anyref)
+  (select (result anyref)
+   ;; Same, but now the arms are blocks, so they have the stale types (which is
+   ;; allowed) and the select is ok.
+   (if (result anyref)
+    (i32.const 0)
+    (then
+     (nop)
+     (ref.null none)
+    )
+    (else
+     (nop)
+     (ref.null none)
+    )
+   )
+   (ref.null none)
+   (i32.const 0)
+  )
+ )
 )