Merge pull request #341 from WebAssembly/opts

More optimization goodies

7 files changed, 69 insertions, 40 deletions

diff --git a/src/asm2wasm.h b/src/asm2wasm.h
index a5a76b396..307f7a38e 100644
--- a/src/asm2wasm.h
+++ b/src/asm2wasm.h
@@ -1713,13 +1713,7 @@ Function* Asm2WasmBuilder::processFunction(Ref ast) {
 
 void Asm2WasmBuilder::optimize() {
   PassRunner passRunner(&allocator);
-  passRunner.add("remove-unused-brs");
-  passRunner.add("remove-unused-names");
-  passRunner.add("merge-blocks");
-  passRunner.add("optimize-instructions");
-  passRunner.add("simplify-locals");
-  passRunner.add("reorder-locals");
-  passRunner.add("vacuum");
+  passRunner.addDefaultOptimizationPasses();
   if (maxGlobal < 1024) {
     passRunner.add("post-emscripten");
   }
diff --git a/src/binaryen-shell.cpp b/src/binaryen-shell.cpp
index dd0f0eeca..84b81963b 100644
--- a/src/binaryen-shell.cpp
+++ b/src/binaryen-shell.cpp
@@ -174,12 +174,6 @@ int main(int argc, const char* argv[]) {
   Name entry;
   std::vector<std::string> passes;
 
-  static const char* default_passes[] = {"remove-unused-brs",
-                                         "remove-unused-names", "merge-blocks",
-                                         "optimize-instructions",
-                                         "simplify-locals", "reorder-locals",
-                                         "vacuum"};
-
   Options options("binaryen-shell", "Execute .wast files");
   options
       .add("--output", "-o", "Output file (stdout if not specified)",
@@ -195,7 +189,7 @@ int main(int argc, const char* argv[]) {
       .add("", "-O", "execute default optimization passes",
            Options::Arguments::Zero,
            [&passes](Options*, const std::string&) {
-             for (const auto* p : default_passes) passes.push_back(p);
+             passes.push_back("O");
            })
       .add_positional("INFILE", Options::Arguments::One,
                       [](Options* o, const std::string& argument) {
@@ -234,7 +228,11 @@ int main(int argc, const char* argv[]) {
         if (options.debug) std::cerr << "running passes...\n";
         PassRunner passRunner(&moreModuleAllocations);
         for (auto& passName : passes) {
-          passRunner.add(passName);
+          if (passName == "O") {
+            passRunner.addDefaultOptimizationPasses();
+          } else {
+            passRunner.add(passName);
+          }
         }
         passRunner.run(&wasm);
       }
diff --git a/src/pass.cpp b/src/pass.cpp
index 432979413..a85643efa 100644
--- a/src/pass.cpp
+++ b/src/pass.cpp
@@ -53,6 +53,16 @@ std::string PassRegistry::getPassDescription(std::string name) {
 
 // PassRunner
 
+void PassRunner::addDefaultOptimizationPasses() {
+  add("remove-unused-brs");
+  add("remove-unused-names");
+  add("merge-blocks");
+  add("optimize-instructions");
+  add("simplify-locals");
+  add("reorder-locals");
+  add("vacuum");
+}
+
 void PassRunner::run(Module* module) {
   for (auto pass : passes) {
     currPass = pass;
diff --git a/src/pass.h b/src/pass.h
index f1f99e3aa..503c164f9 100644
--- a/src/pass.h
+++ b/src/pass.h
@@ -88,6 +88,10 @@ struct PassRunner {
     passes.push_back(new P(arg));
   }
 
+  // Adds the default set of optimization passes; this is
+  // what -O does.
+  void addDefaultOptimizationPasses();
+
   void run(Module* module);
 
   // Get the last pass that was already executed of a certain type.
diff --git a/src/passes/ReorderLocals.cpp b/src/passes/ReorderLocals.cpp
index e378408b6..7f64c00f3 100644
--- a/src/passes/ReorderLocals.cpp
+++ b/src/passes/ReorderLocals.cpp
@@ -31,12 +31,17 @@ struct ReorderLocals : public WalkerPass<PostWalker<ReorderLocals>> {
   std::map<Name, uint32_t> counts;
 
   void visitFunction(Function *curr) {
-    sort(curr->locals.begin(), curr->locals.end(), [this](NameType a, NameType b) -> bool {
+    auto& locals = curr->locals;
+    sort(locals.begin(), locals.end(), [this](NameType a, NameType b) -> bool {
       if (this->counts[a.name] == this->counts[b.name]) {
         return strcmp(a.name.str, b.name.str) > 0;
       }
       return this->counts[a.name] > this->counts[b.name];
     });
+    // drop completely unused locals
+    while (locals.size() > 0 && counts[locals.back().name] == 0) {
+      locals.pop_back();
+    }
     counts.clear();
   }
 
diff --git a/src/passes/SimplifyLocals.cpp b/src/passes/SimplifyLocals.cpp
index 77e4f788a..408fea7ab 100644
--- a/src/passes/SimplifyLocals.cpp
+++ b/src/passes/SimplifyLocals.cpp
@@ -20,6 +20,10 @@
 // This "sinks" set_locals, pushing them to the next get_local where possible,
 // and removing the set if there are no gets remaining (the latter is
 // particularly useful in ssa mode, but not only).
+//
+// After this pass, some locals may be completely unused. reorder-locals
+// can get rid of those (the operation is trivial there after it sorts by use
+// frequency).
 
 #include <wasm.h>
 #include <wasm-traversal.h>
@@ -41,6 +45,8 @@ struct SimplifyLocals : public WalkerPass<LinearExecutionWalker<SimplifyLocals>>
   // locals in current linear execution trace, which we try to sink
   std::map<Name, SinkableInfo> sinkables;
 
+  bool sunk;
+
   // name => # of get_locals for it
   std::map<Name, int> numGetLocals;
 
@@ -60,6 +66,7 @@ struct SimplifyLocals : public WalkerPass<LinearExecutionWalker<SimplifyLocals>>
       *found->second.item = curr;
       ExpressionManipulator::nop(curr);
       sinkables.erase(found);
+      sunk = true;
     } else {
       numGetLocals[curr->name]++;
     }
@@ -150,31 +157,42 @@ struct SimplifyLocals : public WalkerPass<LinearExecutionWalker<SimplifyLocals>>
     self->pushTask(visitPre, currp);
   }
 
-  void visitFunction(Function *curr) {
-    // after optimizing a function, we can see if we have set_locals
-    // for a local with no remaining gets, in which case, we can
-    // remove the set.
-    std::vector<SetLocal*> optimizables;
-    for (auto pair : setLocalOrigins) {
-      SetLocal* curr = pair.first;
-      if (numGetLocals[curr->name] == 0) {
-        // no gets, can remove the set and leave just the value
-        optimizables.push_back(curr);
+  void startWalk(Function *func) {
+    // multiple passes may be required per function, consider this:
+    //    x = load
+    //    y = store
+    //    c(x, y)
+    // the load cannot cross the store, but y can be sunk, after which so can x
+    do {
+      sunk = false;
+      // main operation
+      walk(func->body);
+      // after optimizing a function, we can see if we have set_locals
+      // for a local with no remaining gets, in which case, we can
+      // remove the set.
+      std::vector<SetLocal*> optimizables;
+      for (auto pair : setLocalOrigins) {
+        SetLocal* curr = pair.first;
+        if (numGetLocals[curr->name] == 0) {
+          // no gets, can remove the set and leave just the value
+          optimizables.push_back(curr);
+        }
       }
-    }
-    for (auto* curr : optimizables) {
-      Expression** origin = setLocalOrigins[curr];
-      *origin = curr->value;
-      // nested set_values need to be handled properly.
-      // consider (set_local x (set_local y (..)), where both can be
-      // reduced to their values, and we might do it in either
-      // order.
-      if (curr->value->is<SetLocal>()) {
-        setLocalOrigins[curr->value->cast<SetLocal>()] = origin;
+      for (auto* curr : optimizables) {
+        Expression** origin = setLocalOrigins[curr];
+        *origin = curr->value;
+        // nested set_values need to be handled properly.
+        // consider (set_local x (set_local y (..)), where both can be
+        // reduced to their values, and we might do it in either
+        // order.
+        if (curr->value->is<SetLocal>()) {
+          setLocalOrigins[curr->value->cast<SetLocal>()] = origin;
+        }
       }
-    }
-    numGetLocals.clear();
-    setLocalOrigins.clear();
+      // clean up
+      numGetLocals.clear();
+      setLocalOrigins.clear();
+    } while (sunk);
   }
 };
 
diff --git a/src/wasm-traversal.h b/src/wasm-traversal.h
index c8de5d886..efbe12586 100644
--- a/src/wasm-traversal.h
+++ b/src/wasm-traversal.h
@@ -141,7 +141,7 @@ struct Walker : public Visitor<SubType> {
       self->visitExport(curr);
     }
     for (auto curr : module->functions) {
-      startWalk(curr);
+      self->startWalk(curr);
       self->visitFunction(curr);
     }
     self->visitTable(&module->table);