Skip liveness analysis if too many locals (#2560)

The analysis currently uses a dense matrix. If there are >65535
locals then the indexes don't fit in a 32-bit type like a wasm32
index, which led to overflows and incorrect behavior. To avoid
that, don't run passes with liveness analysis for now if they have
that many locals.

Note that skipping coalesce-locals (the main liveness-using
pass) is not that bad, as we run it more than once, and it's
likely that even if the first must be skipped, we can still run
the second (which is after simplify- and reorder-locals, which
can greatly reduce the local count).

Fixes #2559

3 files changed, 22 insertions, 0 deletions

diff --git a/src/cfg/liveness-traversal.h b/src/cfg/liveness-traversal.h
index d665c07af..6deab2fd6 100644
--- a/src/cfg/liveness-traversal.h
+++ b/src/cfg/liveness-traversal.h
@@ -171,10 +171,26 @@ struct LivenessWalker : public CFGWalker<SubType, VisitorType, Liveness> {
     return nullptr;
   }
 
+  // If there are too many locals, we cannot run currently as
+  // numLocals * numLocals might overflow. We may want to add an option for
+  // a sparse matrix at some point TODO
+  bool canRun(Function* func) {
+    Index numLocals = func->getNumLocals();
+    if (uint64_t(numLocals) * uint64_t(numLocals) <=
+        std::numeric_limits<Index>::max()) {
+      return true;
+    }
+    std::cerr << "warning: too many locals (" << numLocals
+              << ") to run liveness analysis in " << this->getFunction()->name
+              << '\n';
+    return false;
+  }
+
   // main entry point
 
   void doWalkFunction(Function* func) {
     numLocals = func->getNumLocals();
+    assert(canRun(func));
     copies.resize(numLocals * numLocals);
     std::fill(copies.begin(), copies.end(), 0);
     totalCopies.resize(numLocals);
diff --git a/src/passes/CoalesceLocals.cpp b/src/passes/CoalesceLocals.cpp
index 9bc635f80..232685001 100644
--- a/src/passes/CoalesceLocals.cpp
+++ b/src/passes/CoalesceLocals.cpp
@@ -92,6 +92,9 @@ struct CoalesceLocals
 };
 
 void CoalesceLocals::doWalkFunction(Function* func) {
+  if (!canRun(func)) {
+    return;
+  }
   super::doWalkFunction(func);
   // prioritize back edges
   increaseBackEdgePriorities();
diff --git a/src/passes/SpillPointers.cpp b/src/passes/SpillPointers.cpp
index 758ca3223..7458f5fbd 100644
--- a/src/passes/SpillPointers.cpp
+++ b/src/passes/SpillPointers.cpp
@@ -65,6 +65,9 @@ struct SpillPointers
   // main entry point
 
   void doWalkFunction(Function* func) {
+    if (!canRun(func)) {
+      return;
+    }
     super::doWalkFunction(func);
     spillPointers();
   }