Merge pull request #435 from WebAssembly/more-relooper

Add optimization to C API, and with that, more relooper tests

14 files changed, 295 insertions, 15 deletions

diff --git a/CMakeLists.txt b/CMakeLists.txt
index 4877a118b..461f092ad 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -95,10 +95,22 @@ SET(binaryen_c_SOURCES
   src/binaryen-c.cpp
   src/cfg/Relooper.cpp
   src/pass.cpp
+  src/passes/LowerIfElse.cpp
+  src/passes/MergeBlocks.cpp
+  src/passes/NameManager.cpp
+  src/passes/OptimizeInstructions.cpp
+  src/passes/PostEmscripten.cpp
   src/passes/Print.cpp
+  src/passes/RemoveImports.cpp
+  src/passes/RemoveUnusedBrs.cpp
+  src/passes/RemoveUnusedNames.cpp
+  src/passes/SimplifyLocals.cpp
+  src/passes/ReorderLocals.cpp
+  src/passes/Vacuum.cpp
+  src/passes/Metrics.cpp
   src/wasm.cpp
 )
-ADD_LIBRARY(binaryen-c STATIC ${binaryen_c_SOURCES})
+ADD_LIBRARY(binaryen-c SHARED ${binaryen_c_SOURCES})
 
 SET(binaryen-shell_SOURCES
   src/binaryen-shell.cpp
diff --git a/auto_update_tests.py b/auto_update_tests.py
index bd9e5f695..7162bd8fd 100755
--- a/auto_update_tests.py
+++ b/auto_update_tests.py
@@ -2,6 +2,8 @@
 
 import os, sys, subprocess, difflib
 
+os.environ['LD_LIBRARY_PATH'] = 'lib' # find our dynamic libraries
+
 print '[ processing and updating testcases... ]\n'
 
 for asm in sorted(os.listdir('test')):
diff --git a/check.py b/check.py
index 25e7e905c..b02ce14ce 100755
--- a/check.py
+++ b/check.py
@@ -49,6 +49,7 @@ WATERFALL_BUILD_DIR = os.path.join(BASE_DIR, 'wasm-install')
 BIN_DIR = os.path.abspath(os.path.join(WATERFALL_BUILD_DIR, 'wasm-install', 'bin'))
 
 os.environ['BINARYEN'] = os.getcwd()
+os.environ['LD_LIBRARY_PATH'] = 'lib' # find our dynamic libraries
 
 def fetch_waterfall():
   rev = open(os.path.join('test', 'revision')).read().strip()
diff --git a/src/asm2wasm.h b/src/asm2wasm.h
index fa35211a4..0f4852250 100644
--- a/src/asm2wasm.h
+++ b/src/asm2wasm.h
@@ -1725,12 +1725,12 @@ Function* Asm2WasmBuilder::processFunction(Ref ast) {
 }
 
 void Asm2WasmBuilder::optimize() {
-  PassRunner passRunner(&allocator);
+  PassRunner passRunner(&wasm);
   passRunner.addDefaultOptimizationPasses();
   if (maxGlobal < 1024) {
     passRunner.add("post-emscripten");
   }
-  passRunner.run(&wasm);
+  passRunner.run();
 }
 
 } // namespace wasm
diff --git a/src/binaryen-c.cpp b/src/binaryen-c.cpp
index b2c695ec0..bbafdf49d 100644
--- a/src/binaryen-c.cpp
+++ b/src/binaryen-c.cpp
@@ -19,6 +19,7 @@
 //===============================
 
 #include "binaryen-c.h"
+#include "pass.h"
 #include "wasm.h"
 #include "wasm-builder.h"
 #include "wasm-printing.h"
@@ -384,6 +385,13 @@ void BinaryenModulePrint(BinaryenModuleRef module) {
   WasmPrinter::printModule((Module*)module);
 }
 
+void BinaryenModuleOptimize(BinaryenModuleRef module) {
+  Module* wasm = (Module*)module;
+  PassRunner passRunner(wasm);
+  passRunner.addDefaultOptimizationPasses();
+  passRunner.run();
+}
+
 //
 // ========== CFG / Relooper ==========
 //
diff --git a/src/binaryen-c.h b/src/binaryen-c.h
index 2dbf27076..2e0a7b996 100644
--- a/src/binaryen-c.h
+++ b/src/binaryen-c.h
@@ -266,6 +266,9 @@ void BinaryenSetStart(BinaryenModuleRef module, const char* name);
 // Print a module to stdout.
 void BinaryenModulePrint(BinaryenModuleRef module);
 
+// Run the standard optimization passes on the module.
+void BinaryenModuleOptimize(BinaryenModuleRef module);
+
 //
 // ========== CFG / Relooper ==========
 //
diff --git a/src/binaryen-shell.cpp b/src/binaryen-shell.cpp
index f988379c4..8c0390d15 100644
--- a/src/binaryen-shell.cpp
+++ b/src/binaryen-shell.cpp
@@ -223,7 +223,7 @@ int main(int argc, const char* argv[]) {
 
       if (passes.size() > 0) {
         if (options.debug) std::cerr << "running passes...\n";
-        PassRunner passRunner(&moreModuleAllocations);
+        PassRunner passRunner(&wasm);
         if (options.debug) passRunner.setDebug(true);
         for (auto& passName : passes) {
           if (passName == "O") {
@@ -232,7 +232,7 @@ int main(int argc, const char* argv[]) {
             passRunner.add(passName);
           }
         }
-        passRunner.run(&wasm);
+        passRunner.run();
       }
 
       run_asserts(&i, &checked, &wasm, &root, &builder, entry);
diff --git a/src/pass.cpp b/src/pass.cpp
index 5c4f510f8..e4cc35554 100644
--- a/src/pass.cpp
+++ b/src/pass.cpp
@@ -68,7 +68,7 @@ void PassRunner::addDefaultOptimizationPasses() {
   add("optimize-instructions");
 }
 
-void PassRunner::run(Module* module) {
+void PassRunner::run() {
   std::chrono::high_resolution_clock::time_point beforeEverything;
   size_t padding = 0;
   if (debug) {
@@ -88,7 +88,7 @@ void PassRunner::run(Module* module) {
       }
       before = std::chrono::high_resolution_clock::now();
     }
-    pass->run(this, module);
+    pass->run(this, wasm);
     if (debug) {
       auto after = std::chrono::high_resolution_clock::now();
       std::chrono::duration<double> diff = after - before;
diff --git a/src/pass.h b/src/pass.h
index 85aec624f..bfbcb26d8 100644
--- a/src/pass.h
+++ b/src/pass.h
@@ -22,6 +22,7 @@
 #include "wasm.h"
 #include "wasm-traversal.h"
 #include "mixed_arena.h"
+#include "support/utilities.h"
 
 namespace wasm {
 
@@ -66,18 +67,19 @@ struct RegisterPass {
 // Runs a set of passes, in order
 //
 struct PassRunner {
+  Module* wasm;
   MixedArena* allocator;
   std::vector<Pass*> passes;
   Pass* currPass;
   bool debug = false;
 
-  PassRunner(MixedArena* allocator) : allocator(allocator) {}
+  PassRunner(Module* wasm) : wasm(wasm), allocator(&wasm->allocator) {}
 
   void setDebug(bool debug_) { debug = debug_; }
 
   void add(std::string passName) {
     auto pass = PassRegistry::get()->createPass(passName);
-    assert(pass);
+    if (!pass) Fatal() << "Could not find pass: " << passName << "\n";
     passes.push_back(pass);
   }
 
@@ -95,7 +97,7 @@ struct PassRunner {
   // what -O does.
   void addDefaultOptimizationPasses();
 
-  void run(Module* module);
+  void run();
 
   // Get the last pass that was already executed of a certain type.
   template<class P>
diff --git a/src/passes/ReorderLocals.cpp b/src/passes/ReorderLocals.cpp
index 1a3fbf09a..0e626e0a2 100644
--- a/src/passes/ReorderLocals.cpp
+++ b/src/passes/ReorderLocals.cpp
@@ -106,8 +106,11 @@ struct ReorderLocals : public WalkerPass<PostWalker<ReorderLocals, Visitor<Reord
     curr->localNames.resize(newToOld.size());
     curr->localIndices.clear();
     for (size_t i = 0; i < newToOld.size(); i++) {
-      curr->localNames[i] = oldLocalNames[newToOld[i]];
-      curr->localIndices[oldLocalNames[newToOld[i]]] = i;
+      if (newToOld[i] < oldLocalNames.size()) {
+        auto old = oldLocalNames[newToOld[i]];
+        curr->localNames[i] = old;
+        curr->localIndices[old] = i;
+      }
     }
   }
 
diff --git a/src/support/archive.cpp b/src/support/archive.cpp
index 3879f72a7..c0351bc05 100644
--- a/src/support/archive.cpp
+++ b/src/support/archive.cpp
@@ -211,7 +211,7 @@ static uint32_t read32be(const uint8_t* buf) {
 
 void Archive::dump() const {
   printf("Archive data %p len %lu, firstRegularData %p\n", data.data(),
-         data.size(), firstRegularData);
+         (long unsigned)data.size(), firstRegularData);
   printf("Symbol table %p, len %u\n", symbolTable.data, symbolTable.len);
   printf("string table %p, len %u\n", stringTable.data, stringTable.len);
   const uint8_t* buf = symbolTable.data;
diff --git a/src/wasm-printing.h b/src/wasm-printing.h
index 2fab99938..d1f1c42a5 100644
--- a/src/wasm-printing.h
+++ b/src/wasm-printing.h
@@ -26,9 +26,9 @@ namespace wasm {
 
 struct WasmPrinter {
   static std::ostream& printModule(Module* module, std::ostream& o) {
-    PassRunner passRunner(nullptr);
+    PassRunner passRunner(module);
     passRunner.add<Printer>(o);
-    passRunner.run(module);
+    passRunner.run();
     return o;
   }
 
diff --git a/test/example/c-api-kitchen-sink.c b/test/example/c-api-kitchen-sink.c
index 28fd901a4..b7b938c55 100644
--- a/test/example/c-api-kitchen-sink.c
+++ b/test/example/c-api-kitchen-sink.c
@@ -332,8 +332,35 @@ void test_relooper() {
     BinaryenExpressionRef body = RelooperRenderAndDispose(relooper, block0, 0, module);
     BinaryenFunctionRef sinker = BinaryenAddFunction(module, "loop-tail", v, localTypes, 1, body);
   }
+  { // nontrivial loop + phi to head
+    RelooperRef relooper = RelooperCreate();
+    RelooperBlockRef block0 = RelooperAddBlock(relooper, makeInt32(module, 0));
+    RelooperBlockRef block1 = RelooperAddBlock(relooper, makeInt32(module, 1));
+    RelooperBlockRef block2 = RelooperAddBlock(relooper, makeInt32(module, 2));
+    RelooperBlockRef block3 = RelooperAddBlock(relooper, makeInt32(module, 3));
+    RelooperBlockRef block4 = RelooperAddBlock(relooper, makeInt32(module, 4));
+    RelooperBlockRef block5 = RelooperAddBlock(relooper, makeInt32(module, 5));
+    RelooperBlockRef block6 = RelooperAddBlock(relooper, makeInt32(module, 6));
+    RelooperAddBranch(block0, block1, NULL, makeInt32(module, 10));
+    RelooperAddBranch(block1, block2, makeInt32(module, -2), NULL);
+    RelooperAddBranch(block1, block6, NULL, makeInt32(module, 20));
+    RelooperAddBranch(block2, block3, makeInt32(module, -6), NULL);
+    RelooperAddBranch(block2, block1, NULL, makeInt32(module, 30));
+    RelooperAddBranch(block3, block4, makeInt32(module, -10), NULL);
+    RelooperAddBranch(block3, block5, NULL, NULL);
+    RelooperAddBranch(block4, block5, NULL, NULL);
+    RelooperAddBranch(block5, block6, NULL, makeInt32(module, 40));
+    BinaryenExpressionRef body = RelooperRenderAndDispose(relooper, block0, 0, module);
+    BinaryenFunctionRef sinker = BinaryenAddFunction(module, "nontrivial-loop-plus-phi-to-head", v, localTypes, 1, body);
+  }
 
+  printf("raw:\n");
   BinaryenModulePrint(module);
+
+  printf("optimized:\n");
+  BinaryenModuleOptimize(module);
+  BinaryenModulePrint(module);
+
   BinaryenModuleDispose(module);
 }
 
diff --git a/test/example/c-api-kitchen-sink.txt b/test/example/c-api-kitchen-sink.txt
index 734038a74..71b937219 100644
--- a/test/example/c-api-kitchen-sink.txt
+++ b/test/example/c-api-kitchen-sink.txt
@@ -346,6 +346,7 @@ BinaryenFloat64: 4
     )
   )
 )
+raw:
 (module
   (memory 0)
   (type $v (func))
@@ -532,4 +533,225 @@ BinaryenFloat64: 4
       (i32.const 2)
     )
   )
+  (func $nontrivial-loop-plus-phi-to-head (type $v)
+    (local $0 i32)
+    (block
+      (i32.const 0)
+      (block
+        (i32.const 10)
+      )
+    )
+    (block
+      (loop $shape$1$break $shape$1$continue
+        (block
+          (i32.const 1)
+          (if
+            (i32.eqz
+              (i32.const -2)
+            )
+            (block
+              (i32.const 20)
+              (br $shape$1$break)
+            )
+          )
+        )
+        (block
+          (i32.const 2)
+          (if
+            (i32.const -6)
+            (block
+              (set_local $0
+                (i32.const 4)
+              )
+              (br $shape$1$break)
+            )
+            (block
+              (i32.const 30)
+              (br $shape$1$continue)
+            )
+          )
+        )
+      )
+      (block
+        (block $shape$4$break
+          (if
+            (i32.eq
+              (get_local $0)
+              (i32.const 4)
+            )
+            (block
+              (block
+                (i32.const 3)
+                (block $shape$6$break
+                  (if
+                    (i32.const -10)
+                    (block
+                      (i32.const 4)
+                      (block
+                        (br $shape$6$break)
+                      )
+                    )
+                  )
+                )
+              )
+              (block
+                (i32.const 5)
+                (block
+                  (i32.const 40)
+                  (br $shape$4$break)
+                )
+              )
+            )
+          )
+        )
+        (block
+          (i32.const 6)
+        )
+      )
+    )
+  )
+)
+optimized:
+(module
+  (memory 0)
+  (type $v (func))
+  (func $just-one-block (type $v)
+    (i32.const 1337)
+  )
+  (func $two-blocks (type $v)
+    (i32.const 0)
+    (i32.const 1)
+  )
+  (func $two-blocks-plus-code (type $v)
+    (i32.const 0)
+    (i32.const 77)
+    (i32.const 1)
+  )
+  (func $loop (type $v)
+    (loop $shape$0$break $shape$0$continue
+      (i32.const 0)
+      (i32.const 1)
+      (br $shape$0$continue)
+    )
+  )
+  (func $loop-plus-code (type $v)
+    (loop $shape$0$break $shape$0$continue
+      (i32.const 0)
+      (i32.const 33)
+      (i32.const 1)
+      (i32.const -66)
+      (br $shape$0$continue)
+    )
+  )
+  (func $split (type $v)
+    (i32.const 0)
+    (select
+      (i32.const 1)
+      (i32.const 2)
+      (i32.const 55)
+    )
+  )
+  (func $split-plus-code (type $v)
+    (i32.const 0)
+    (select
+      (block
+        (i32.const 10)
+        (i32.const 1)
+      )
+      (block
+        (i32.const 20)
+        (i32.const 2)
+      )
+      (i32.const 55)
+    )
+  )
+  (func $if (type $v)
+    (i32.const 0)
+    (if
+      (i32.const 55)
+      (i32.const 1)
+    )
+    (i32.const 2)
+  )
+  (func $if-plus-code (type $v)
+    (i32.const 0)
+    (select
+      (block
+        (i32.const -1)
+        (i32.const 1)
+        (i32.const -3)
+      )
+      (i32.const -2)
+      (i32.const 55)
+    )
+    (i32.const 2)
+  )
+  (func $if-else (type $v)
+    (i32.const 0)
+    (select
+      (i32.const 1)
+      (i32.const 2)
+      (i32.const 55)
+    )
+    (i32.const 3)
+  )
+  (func $loop-tail (type $v)
+    (loop $shape$0$break $shape$0$continue
+      (i32.const 0)
+      (i32.const 1)
+      (if
+        (i32.const 10)
+        (br $shape$0$continue)
+        (br $shape$0$break)
+      )
+    )
+    (i32.const 2)
+  )
+  (func $nontrivial-loop-plus-phi-to-head (type $v)
+    (local $0 i32)
+    (i32.const 0)
+    (i32.const 10)
+    (loop $shape$1$break $shape$1$continue
+      (i32.const 1)
+      (if
+        (i32.eqz
+          (i32.const -2)
+        )
+        (block
+          (i32.const 20)
+          (br $shape$1$break)
+        )
+      )
+      (i32.const 2)
+      (if
+        (i32.const -6)
+        (block
+          (set_local $0
+            (i32.const 4)
+          )
+          (br $shape$1$break)
+        )
+        (block
+          (i32.const 30)
+          (br $shape$1$continue)
+        )
+      )
+    )
+    (if
+      (i32.eq
+        (get_local $0)
+        (i32.const 4)
+      )
+      (block
+        (i32.const 3)
+        (if
+          (i32.const -10)
+          (i32.const 4)
+        )
+        (i32.const 5)
+        (i32.const 40)
+      )
+    )
+    (i32.const 6)
+  )
 )