CoalesceLocals: Use ValueNumbering (#4355)

This removes the old hardcoded value numbering in that pass and makes
it use the new code that was split into helper code. The immediate benefit
of this is to make the code aware of identical constants: if two locals have
the same constant then they do not interfere. Future improvements to
numbering will also automatically help here.

This changes some constants in existing tests so that they keep testing
what they were testing before, and adds new tests for the new benefit here.

This implements a proposed TODO from #4314

3 files changed, 171 insertions, 32 deletions

diff --git a/test/lit/passes/coalesce-locals-learning.wast b/test/lit/passes/coalesce-locals-learning.wast
index 6e896ae9d..d51a41276 100644
--- a/test/lit/passes/coalesce-locals-learning.wast
+++ b/test/lit/passes/coalesce-locals-learning.wast
@@ -57,7 +57,7 @@
   ;; CHECK-NEXT:   (i32.const 0)
   ;; CHECK-NEXT:  )
   ;; CHECK-NEXT:  (local.set $1
-  ;; CHECK-NEXT:   (i32.const 0)
+  ;; CHECK-NEXT:   (i32.const 1)
   ;; CHECK-NEXT:  )
   ;; CHECK-NEXT:  (drop
   ;; CHECK-NEXT:   (local.get $0)
@@ -73,7 +73,7 @@
       (i32.const 0)
     )
     (local.set $y
-      (i32.const 0)
+      (i32.const 1)
     )
     (drop
       (local.get $x)
@@ -190,7 +190,7 @@
   ;; CHECK-NEXT:  )
   ;; CHECK-NEXT:  (block $block0
   ;; CHECK-NEXT:   (local.set $1
-  ;; CHECK-NEXT:    (i32.const 0)
+  ;; CHECK-NEXT:    (i32.const 1)
   ;; CHECK-NEXT:   )
   ;; CHECK-NEXT:  )
   ;; CHECK-NEXT:  (drop
@@ -208,7 +208,7 @@
     )
     (block $block0
       (local.set $y
-        (i32.const 0)
+        (i32.const 1)
       )
     )
     (drop
@@ -269,7 +269,7 @@
   ;; CHECK-NEXT:  )
   ;; CHECK-NEXT:  (block $block
   ;; CHECK-NEXT:   (local.set $1
-  ;; CHECK-NEXT:    (i32.const 0)
+  ;; CHECK-NEXT:    (i32.const 1)
   ;; CHECK-NEXT:   )
   ;; CHECK-NEXT:   (drop
   ;; CHECK-NEXT:    (local.get $1)
@@ -288,7 +288,7 @@
     )
     (block $block
       (local.set $y
-        (i32.const 0)
+        (i32.const 1)
       )
       (drop
         (local.get $y)
@@ -582,7 +582,7 @@
   ;; CHECK-NEXT:  (local $0 i32)
   ;; CHECK-NEXT:  (local $1 i32)
   ;; CHECK-NEXT:  (local.set $0
-  ;; CHECK-NEXT:   (i32.const 0)
+  ;; CHECK-NEXT:   (i32.const 1)
   ;; CHECK-NEXT:  )
   ;; CHECK-NEXT:  (if
   ;; CHECK-NEXT:   (i32.const 0)
@@ -600,7 +600,7 @@
     (local $x i32)
     (local $y i32)
     (local.set $x
-      (i32.const 0)
+      (i32.const 1)
     )
     (if
       (i32.const 0)
@@ -619,7 +619,7 @@
   ;; CHECK-NEXT:  (local $1 i32)
   ;; CHECK-NEXT:  (if
   ;; CHECK-NEXT:   (local.tee $0
-  ;; CHECK-NEXT:    (i32.const 0)
+  ;; CHECK-NEXT:    (i32.const 1)
   ;; CHECK-NEXT:   )
   ;; CHECK-NEXT:   (block $block1
   ;; CHECK-NEXT:    (drop
@@ -636,7 +636,7 @@
     (local $y i32)
     (if
       (local.tee $x
-        (i32.const 0)
+        (i32.const 1)
       )
       (block $block1
         (drop
diff --git a/test/lit/passes/coalesce-locals.wast b/test/lit/passes/coalesce-locals.wast
index 7846929bc..2cd5948bc 100644
--- a/test/lit/passes/coalesce-locals.wast
+++ b/test/lit/passes/coalesce-locals.wast
@@ -74,7 +74,7 @@
   ;; CHECK-NEXT:   (i32.const 0)
   ;; CHECK-NEXT:  )
   ;; CHECK-NEXT:  (local.set $1
-  ;; CHECK-NEXT:   (i32.const 0)
+  ;; CHECK-NEXT:   (i32.const 1)
   ;; CHECK-NEXT:  )
   ;; CHECK-NEXT:  (drop
   ;; CHECK-NEXT:   (local.get $0)
@@ -90,7 +90,7 @@
       (i32.const 0)
     )
     (local.set $y
-      (i32.const 0)
+      (i32.const 1)
     )
     (drop
       (local.get $x)
@@ -207,7 +207,7 @@
   ;; CHECK-NEXT:  )
   ;; CHECK-NEXT:  (block $block0
   ;; CHECK-NEXT:   (local.set $1
-  ;; CHECK-NEXT:    (i32.const 0)
+  ;; CHECK-NEXT:    (i32.const 1)
   ;; CHECK-NEXT:   )
   ;; CHECK-NEXT:  )
   ;; CHECK-NEXT:  (drop
@@ -225,7 +225,7 @@
     )
     (block $block0
       (local.set $y
-        (i32.const 0)
+        (i32.const 1)
       )
     )
     (drop
@@ -286,7 +286,7 @@
   ;; CHECK-NEXT:  )
   ;; CHECK-NEXT:  (block $block
   ;; CHECK-NEXT:   (local.set $1
-  ;; CHECK-NEXT:    (i32.const 0)
+  ;; CHECK-NEXT:    (i32.const 1)
   ;; CHECK-NEXT:   )
   ;; CHECK-NEXT:   (drop
   ;; CHECK-NEXT:    (local.get $1)
@@ -305,7 +305,7 @@
     )
     (block $block
       (local.set $y
-        (i32.const 0)
+        (i32.const 1)
       )
       (drop
         (local.get $y)
@@ -599,7 +599,7 @@
   ;; CHECK-NEXT:  (local $0 i32)
   ;; CHECK-NEXT:  (local $1 i32)
   ;; CHECK-NEXT:  (local.set $0
-  ;; CHECK-NEXT:   (i32.const 0)
+  ;; CHECK-NEXT:   (i32.const 1)
   ;; CHECK-NEXT:  )
   ;; CHECK-NEXT:  (if
   ;; CHECK-NEXT:   (i32.const 0)
@@ -617,7 +617,7 @@
     (local $x i32)
     (local $y i32)
     (local.set $x
-      (i32.const 0)
+      (i32.const 1)
     )
     (if
       (i32.const 0)
@@ -636,7 +636,7 @@
   ;; CHECK-NEXT:  (local $1 i32)
   ;; CHECK-NEXT:  (if
   ;; CHECK-NEXT:   (local.tee $0
-  ;; CHECK-NEXT:    (i32.const 0)
+  ;; CHECK-NEXT:    (i32.const 1)
   ;; CHECK-NEXT:   )
   ;; CHECK-NEXT:   (block $block1
   ;; CHECK-NEXT:    (drop
@@ -653,7 +653,7 @@
     (local $y i32)
     (if
       (local.tee $x
-        (i32.const 0)
+        (i32.const 1)
       )
       (block $block1
         (drop
@@ -2921,4 +2921,146 @@
    )
    (local.get $1)
   )
+
+  ;; CHECK:      (func $equal-constants-zeroinit
+  ;; CHECK-NEXT:  (local $0 i32)
+  ;; CHECK-NEXT:  (drop
+  ;; CHECK-NEXT:   (local.get $0)
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (drop
+  ;; CHECK-NEXT:   (local.get $0)
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT: )
+  (func $equal-constants-zeroinit
+    (local $x i32)
+    (local $y i32)
+    ;; $x and $y both have the zero init value, which is identical, and they do
+    ;; not interfere.
+    (drop
+      (local.get $x)
+    )
+    (drop
+      (local.get $y)
+    )
+  )
+
+  ;; CHECK:      (func $equal-constants
+  ;; CHECK-NEXT:  (local $0 i32)
+  ;; CHECK-NEXT:  (local.set $0
+  ;; CHECK-NEXT:   (i32.const 0)
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (drop
+  ;; CHECK-NEXT:   (local.get $0)
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (drop
+  ;; CHECK-NEXT:   (local.get $0)
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT: )
+  (func $equal-constants
+    (local $x i32)
+    (local $y i32)
+    ;; $x is written the same value as $y, so they do not interfere.
+    (local.set $x
+      (i32.const 0)
+    )
+    (drop
+      (local.get $x)
+    )
+    (drop
+      (local.get $y)
+    )
+  )
+
+  ;; CHECK:      (func $different-constants
+  ;; CHECK-NEXT:  (local $0 i32)
+  ;; CHECK-NEXT:  (local $1 i32)
+  ;; CHECK-NEXT:  (local.set $0
+  ;; CHECK-NEXT:   (i32.const 1)
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (drop
+  ;; CHECK-NEXT:   (local.get $0)
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (drop
+  ;; CHECK-NEXT:   (local.get $1)
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT: )
+  (func $different-constants
+    (local $x i32)
+    (local $y i32)
+    ;; $x is written a different value, so they do interfere.
+    (local.set $x
+      (i32.const 1)
+    )
+    (drop
+      (local.get $x)
+    )
+    (drop
+      (local.get $y)
+    )
+  )
+
+  ;; CHECK:      (func $equal-constants-nonzero
+  ;; CHECK-NEXT:  (local $0 i32)
+  ;; CHECK-NEXT:  (local.set $0
+  ;; CHECK-NEXT:   (i32.const 42)
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (local.set $0
+  ;; CHECK-NEXT:   (i32.const 42)
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (drop
+  ;; CHECK-NEXT:   (local.get $0)
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (drop
+  ;; CHECK-NEXT:   (local.get $0)
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT: )
+  (func $equal-constants-nonzero
+    (local $x i32)
+    (local $y i32)
+    (local.set $x
+      (i32.const 42)
+    )
+    (local.set $y
+      (i32.const 42)
+    )
+    (drop
+      (local.get $x)
+    )
+    (drop
+      (local.get $y)
+    )
+  )
+
+  ;; CHECK:      (func $different-constants-nonzero
+  ;; CHECK-NEXT:  (local $0 i32)
+  ;; CHECK-NEXT:  (local $1 i32)
+  ;; CHECK-NEXT:  (local.set $0
+  ;; CHECK-NEXT:   (i32.const 42)
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (local.set $1
+  ;; CHECK-NEXT:   (i32.const 1337)
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (drop
+  ;; CHECK-NEXT:   (local.get $0)
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (drop
+  ;; CHECK-NEXT:   (local.get $1)
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT: )
+  (func $different-constants-nonzero
+    (local $x i32)
+    (local $y i32)
+    (local.set $x
+      (i32.const 42)
+    )
+    (local.set $y
+      (i32.const 1337)
+    )
+    (drop
+      (local.get $x)
+    )
+    (drop
+      (local.get $y)
+    )
+  )
 )
diff --git a/test/wasm2js/br_table_temp.2asm.js.opt b/test/wasm2js/br_table_temp.2asm.js.opt
index b4198a4dc..5c7d88a16 100644
--- a/test/wasm2js/br_table_temp.2asm.js.opt
+++ b/test/wasm2js/br_table_temp.2asm.js.opt
@@ -12555,15 +12555,14 @@ function asmFunc(env) {
  
  function $60($0) {
   $0 = $0 | 0;
-  var $1 = 0, $2 = 0;
+  var $1 = 0;
   $1 = 16;
-  $2 = 16;
   block : {
    switch ($0 | 0) {
    case 0:
-    $2 = 18;
+    $1 = 18;
    case 1:
-    $1 = $2 + 1 | 0;
+    $1 = $1 + 1 | 0;
     break;
    default:
     break block;
@@ -12574,15 +12573,14 @@ function asmFunc(env) {
  
  function $61($0) {
   $0 = $0 | 0;
-  var $1 = 0, $2 = 0;
+  var $1 = 0;
   $1 = 8;
-  $2 = 8;
   block : {
    switch ($0 | 0) {
    default:
-    $2 = 16;
+    $1 = 16;
    case 1:
-    $1 = $2 + 1 | 0;
+    $1 = $1 + 1 | 0;
     break;
    case 0:
     break block;
@@ -12593,15 +12591,14 @@ function asmFunc(env) {
  
  function $62($0) {
   $0 = $0 | 0;
-  var $1 = 0, $2 = 0;
+  var $1 = 0;
   $1 = 8;
-  $2 = 8;
   block : {
    switch ($0 | 0) {
    case 0:
-    $2 = 16;
+    $1 = 16;
    case 1:
-    $1 = $2 + 1 | 0;
+    $1 = $1 + 1 | 0;
     break;
    default:
     break block;