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

4 files changed, 191 insertions, 46 deletions

diff --git a/src/passes/CoalesceLocals.cpp b/src/passes/CoalesceLocals.cpp
index f9ded9c92..42296b5bf 100644
--- a/src/passes/CoalesceLocals.cpp
+++ b/src/passes/CoalesceLocals.cpp
@@ -30,6 +30,7 @@
 #include <unordered_set>
 
 #include "cfg/liveness-traversal.h"
+#include "ir/numbering.h"
 #include "ir/utils.h"
 #include "pass.h"
 #include "support/learning.h"
@@ -155,6 +156,10 @@ void CoalesceLocals::calculateInterferences() {
   // loop.
   std::vector<Index> values(numLocals);
 
+  ValueNumbering valueNumbering;
+
+  auto* func = getFunction();
+
   for (auto& curr : basicBlocks) {
     if (liveBlocks.count(curr.get()) == 0) {
       continue; // ignore dead blocks
@@ -196,21 +201,22 @@ void CoalesceLocals::calculateInterferences() {
     // around through copies between sets we can see when sets are guaranteed to
     // be equal.
 
-    // Give all default values the same value ID, regardless of their type. This
-    // is valid since we only coalesce locals of the same type anyhow.
-    auto zeroInit = 0;
-    Index nextValue = 1;
-
     if (curr.get() == entry) {
       // Each parameter is assumed to have a different value on entry.
-      for (Index i = 0; i < getFunction()->getNumParams(); i++) {
-        values[i] = nextValue++;
+      for (Index i = 0; i < func->getNumParams(); i++) {
+        values[i] = valueNumbering.getUniqueValue();
       }
 
-      for (Index i = getFunction()->getNumParams();
-           i < getFunction()->getNumLocals();
-           i++) {
-        values[i] = zeroInit;
+      for (Index i = func->getNumParams(); i < func->getNumLocals(); i++) {
+        auto type = func->getLocalType(i);
+        if (type.isNonNullable()) {
+          // A non-nullable value cannot be used anyhow, but we must give it
+          // some value. A unique one seems least likely to result in surprise
+          // during debugging.
+          values[i] = valueNumbering.getUniqueValue();
+        } else {
+          values[i] = valueNumbering.getValue(Literal::makeZeros(type));
+        }
       }
     } else {
       // In any block but the entry, assume that each live local might have a
@@ -218,7 +224,7 @@ void CoalesceLocals::calculateInterferences() {
       // TODO: Propagating value IDs across blocks could identify more copies,
       //       however, it would also be nonlinear.
       for (auto index : curr->contents.start) {
-        values[index] = nextValue++;
+        values[index] = valueNumbering.getUniqueValue();
       }
     }
 
@@ -246,8 +252,8 @@ void CoalesceLocals::calculateInterferences() {
         assert(i > 0 && set->value == *actions[i - 1].origin);
         newValue = values[actions[i - 1].index];
       } else {
-        // This is not a copy; assign a new unique value.
-        newValue = nextValue++;
+        // This is not a copy.
+        newValue = valueNumbering.getValue(set->value);
       }
       values[index] = newValue;
 
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;