Semi-SSA improvements (#1965)

This adds an ssa-nomerge pass, which like ssa creates new local indexes for each set, but it does not alter indexes that have merges (in practice adding indexes to merges can lead to more copies in the end.)

This also stops adding a new local index for a set that is already in "ssa form", that is, has only one set (aside from the zero initialization which wasm mandates, but for an "ssa form" index, that must not be used).

This then enables ssa-nomerge in -O3 and -Os. This doesn't help much on well-optimized code like from the wasm backend (but it does sometimes - 0.5% code size improvement on Box2D), but on AssemblyScript for example it can remove a copy in the n-body benchmark as can be seen in the test updates here.

1 files changed, 51 insertions, 6 deletions

diff --git a/src/passes/SSAify.cpp b/src/passes/SSAify.cpp
index 9e6ff2de2..1ed3b976f 100644
--- a/src/passes/SSAify.cpp
+++ b/src/passes/SSAify.cpp
@@ -27,6 +27,26 @@
 // TODO: consider adding a "proper" phi node to the AST, that passes
 //       can utilize
 //
+// There is also a "no-merge" variant of this pass. That will ignore
+// sets leading to merges, that is, it only creates new SSA indexes
+// for sets whose gets have just that set, e.g.
+//
+//  x = ..
+//  f(x, x)
+//  x = ..
+//  g(x, x)
+// =>
+//  x = ..
+//  f(x, x)
+//  x' = ..
+//  g(x', x')
+//
+// This "untangles" local indexes in a way that helps other passes,
+// while not creating copies with overlapping lifetimes that can
+// lead to a code size increase. In particular, the new variables
+// added by ssa-nomerge can be easily removed by the coalesce-locals
+// pass.
+//
 
 #include <iterator>
 
@@ -49,7 +69,11 @@ static SetLocal IMPOSSIBLE_SET;
 struct SSAify : public Pass {
   bool isFunctionParallel() override { return true; }
 
-  Pass* create() override { return new SSAify; }
+  Pass* create() override { return new SSAify(allowMerges); }
+
+  SSAify(bool allowMerges) : allowMerges(allowMerges) {}
+
+  bool allowMerges;
 
   Module* module;
   Function* func;
@@ -59,21 +83,37 @@ struct SSAify : public Pass {
     module = module_;
     func = func_;
     LocalGraph graph(func);
+    graph.computeInfluences();
+    graph.computeSSAIndexes();
     // create new local indexes, one for each set
-    createNewIndexes();
+    createNewIndexes(graph);
     // we now know the sets for each get, and can compute get indexes and handle phis
     computeGetsAndPhis(graph);
     // add prepends to function
     addPrepends();
   }
 
-  void createNewIndexes() {
+  void createNewIndexes(LocalGraph& graph) {
     FindAll<SetLocal> sets(func->body);
     for (auto* set : sets.list) {
-      set->index = addLocal(func->getLocalType(set->index));
+      // Indexes already in SSA form do not need to be modified - there is already
+      // just one set for that index. Otherwise, use a new index, unless merges
+      // are disallowed.
+      if (!graph.isSSA(set->index) && (allowMerges || !hasMerges(set, graph))) {
+        set->index = addLocal(func->getLocalType(set->index));
+      }
     }
   }
 
+  bool hasMerges(SetLocal* set, LocalGraph& graph) {
+    for (auto* get : graph.setInfluences[set]) {
+      if (graph.getSetses[get].size() > 1) {
+        return true;
+      }
+    }
+    return false;
+  }
+
   void computeGetsAndPhis(LocalGraph& graph) {
     FindAll<GetLocal> gets(func->body);
     for (auto* get : gets.list) {
@@ -97,6 +137,7 @@ struct SSAify : public Pass {
         }
         continue;
       }
+      if (!allowMerges) continue;
       // more than 1 set, need a phi: a new local written to at each of the sets
       auto new_ = addLocal(get->type);
       auto old = get->index;
@@ -154,8 +195,12 @@ struct SSAify : public Pass {
   }
 };
 
-Pass *createSSAifyPass() {
-  return new SSAify();
+Pass* createSSAifyPass() {
+  return new SSAify(true);
+}
+
+Pass* createSSAifyNoMergePass() {
+  return new SSAify(false);
 }
 
 } // namespace wasm