Precompute: Only run a single LocalGraph iteration (#4184)

Precompute has a mode in which it propagates results from local.sets to
local.gets. That constructs a LocalGraph which is a non-trivial amount of
work. We used to run multiple iterations of this, but investigation shows that
such opportunities are extremely rare, as doing just a single propagation
iteration has no effect on the entire emscripten benchmark suite, nor on
j2cl output. Furthermore, we run this pass twice in the normal pipeline (once
early, once late) so even if there are such opportunities they may be
optimized already. And, --converge is a way to get additional iterations of
all passes if a user wants that, so it makes sense not to costly work for more
iterations automatically.

In effect, 99.99% of the time before this pass we would create the LocalGraph
twice: once the first time, then a second time only to see that we can't
actually optimize anything further. This PR makes us only create it once, which
makes precompute-propagate 10% faster on j2cl and even faster on other things
like poppler (33%) and LLVM (29%).

See the change in the test suite for an example of a case that does require
more than one iteration to be optimized. Note that even there, we only manage
to get benefit from a second iteration by doing something that overlaps with
another pass (optimizing out an if with condition 0), which shows even more
how unnecessary the extra work was.

See #4165

1 files changed, 24 insertions, 19 deletions

diff --git a/src/passes/Precompute.cpp b/src/passes/Precompute.cpp
index 980fb17bd..4209ffbe2 100644
--- a/src/passes/Precompute.cpp
+++ b/src/passes/Precompute.cpp
@@ -114,24 +114,27 @@ struct Precompute
 
   GetValues getValues;
 
-  bool worked;
-
   void doWalkFunction(Function* func) {
-    // if propagating, we may need multiple rounds: each propagation can
-    // lead to the main walk removing code, which might open up more
-    // propagation opportunities
-    do {
-      getValues.clear();
-      // with extra effort, we can utilize the get-set graph to precompute
-      // things that use locals that are known to be constant. otherwise,
-      // we just look at what is immediately before us
-      if (propagate) {
-        optimizeLocals(func);
-      }
-      // do the main walk over everything
-      worked = false;
+    // Walk the function and precompute things.
+    super::doWalkFunction(func);
+    if (!propagate) {
+      return;
+    }
+    // When propagating, we can utilize the graph of local operations to
+    // precompute the values from a local.set to a local.get. This populates
+    // getValues which is then used by a subsequent walk that applies those
+    // values.
+    bool propagated = propagateLocals(func);
+    if (propagated) {
+      // We found constants to propagate and entered them in getValues. Do
+      // another walk to apply them and perhaps other optimizations that are
+      // unlocked.
       super::doWalkFunction(func);
-    } while (propagate && worked);
+    }
+    // Note that in principle even more cycles could find further work here, in
+    // very rare cases. To avoid constructing a LocalGraph again just for that
+    // unlikely chance, we leave such things for later runs of this pass and for
+    // --converge.
   }
 
   template<typename T> void reuseConstantNode(T* curr, Flow flow) {
@@ -223,7 +226,6 @@ struct Precompute
     // this was precomputed
     if (flow.values.isConcrete()) {
       replaceCurrent(flow.getConstExpression(*getModule()));
-      worked = true;
     } else {
       ExpressionManipulator::nop(curr);
     }
@@ -273,7 +275,8 @@ private:
   }
 
   // Propagates values around. Returns whether we propagated.
-  void optimizeLocals(Function* func) {
+  bool propagateLocals(Function* func) {
+    bool propagated = false;
     // using the graph of get-set interactions, do a constant-propagation type
     // operation: note which sets are assigned locals, then see if that lets us
     // compute other sets as locals (since some of the gets they read may be
@@ -390,9 +393,11 @@ private:
           for (auto* set : localGraph.getInfluences[get]) {
             work.push(set);
           }
+          propagated = true;
         }
       }
     }
+    return propagated;
   }
 
   bool canEmitConstantFor(const Literals& values) {
@@ -421,7 +426,7 @@ private:
     }
     // All other reference types cannot be precomputed. Even an immutable GC
     // reference is not currently something this pass can handle, as it will
-    // evaluate and reevaluate code multiple times in e.g. optimizeLocals, see
+    // evaluate and reevaluate code multiple times in e.g. propagateLocals, see
     // the comment above.
     if (type.isRef()) {
       return false;