Lift the restriction in liveness-traversal.h that supported max 65535 locals in a function. (#4567)

* Lift the restriction in liveness-traversal.h that supported max 65535 locals in a function.

* Lint

* Fix typo

* Fix static

* Lint

* Lint

* Lint

* Add needed canRun function

* lint

* Use either a sparse or a dense matrix for tracking liveness copies, depending on the locals count.

* Lint

* Fix lint

* Lint

* Implement sparse_square_matrix class and use that as a backing.

* Lint

* Lint

* Lint #includes

* Lint

* Lint includes

* Remove unnecessary code

* Fix canonical accesses to copies matrix

* Lint

* Add missing variable update

* Remove canRun() function

* Address review

* Update expected test results

* Update test name

* Add asserts to sparse_square_matrix set and get functions that they are not out of bound.

* Lint includes

* Update test expectation

* Use .clear() + .resize() to reset totalCopies vector

5 files changed, 56 insertions, 1 deletions

diff --git a/test/example/sparse_square_matrix.cpp b/test/example/sparse_square_matrix.cpp
new file mode 100644
index 000000000..ad1f71ade
--- /dev/null
+++ b/test/example/sparse_square_matrix.cpp
@@ -0,0 +1,54 @@
+#include <iostream>
+
+#include "support/sparse_square_matrix.h"
+
+int main() {
+  sparse_square_matrix<uint32_t> m;
+
+  // New matrix should initialize to 0x0 size.
+  assert(m.width() == 0);
+
+  // Recreating should resize the matrix.
+  m.recreate(100);
+  assert(m.width() == 100);
+
+  // Small matrices should use dense storage.
+  assert(m.usingDenseStorage());
+
+  // Setting and getting element values in dense storage should work.
+  for (int y = 0; y < 100; ++y)
+    for (int x = 0; x < 100; ++x)
+      m.set(y, x, y * 100 + x);
+  for (int y = 0; y < 100; ++y)
+    for (int x = 0; x < 100; ++x)
+      assert(m.get(y, x) == y * 100 + x);
+
+  // Recreating should clear the matrix elements to zero,
+  // even if recreating to same size as before.
+  assert(m.width() == 100);
+  m.recreate(100);
+  for (int y = 0; y < 100; ++y)
+    for (int x = 0; x < 100; ++x)
+      assert(m.get(y, x) == 0);
+
+  // Large matrices should use sparse storage.
+  m.recreate(m.DenseLimit);
+  assert(!m.usingDenseStorage());
+
+  // Setting and getting element values in sparse storage should work.
+  for (int y = 0; y < m.DenseLimit; y += 128)
+    for (int x = 0; x < m.DenseLimit; x += 128)
+      m.set(y, x, y * m.DenseLimit + x);
+  for (int y = 0; y < m.DenseLimit; y += 128)
+    for (int x = 0; x < m.DenseLimit; x += 128)
+      assert(m.get(y, x) == y * m.DenseLimit + x);
+
+  // Recreating matrix in sparse mode should reset values in sparse
+  // storage to zero.
+  m.recreate(m.DenseLimit + 1);
+  for (int y = 0; y < m.width(); y += 128)
+    for (int x = 0; x < m.width(); x += 128)
+      assert(m.get(y, x) == 0);
+
+  std::cout << "ok.\n";
+}
diff --git a/test/example/sparse_square_matrix.txt b/test/example/sparse_square_matrix.txt
new file mode 100644
index 000000000..90b5016ef
--- /dev/null
+++ b/test/example/sparse_square_matrix.txt
@@ -0,0 +1 @@
+ok.
diff --git a/test/passes/too_much_for_liveness.bin.txt b/test/passes/65536_locals_for_liveness.bin.txt
index 793f9578c..0fc7f873a 100644
--- a/test/passes/too_much_for_liveness.bin.txt
+++ b/test/passes/65536_locals_for_liveness.bin.txt
@@ -19,7 +19,7 @@ total
  [tables]       : 0       
  [tags]         : 0       
  [total]        : 4       
- [vars]         : 65536   
+ [vars]         : 1         -65535
  Block          : 1       
  Const          : 1       
  LocalGet       : 1       
diff --git a/test/passes/too_much_for_liveness.passes b/test/passes/65536_locals_for_liveness.passes
index 719d0bbcd..719d0bbcd 100644
--- a/test/passes/too_much_for_liveness.passes
+++ b/test/passes/65536_locals_for_liveness.passes
diff --git a/test/passes/too_much_for_liveness.wasm b/test/passes/65536_locals_for_liveness.wasm
index 88929243d..88929243d 100644
--- a/test/passes/too_much_for_liveness.wasm
+++ b/test/passes/65536_locals_for_liveness.wasm