Merge pull request #819 from WebAssembly/optimize-memory

Pack memory segments

12 files changed, 150 insertions, 5 deletions

diff --git a/auto_update_tests.py b/auto_update_tests.py
index 63590f6cc..f3671b5ce 100755
--- a/auto_update_tests.py
+++ b/auto_update_tests.py
@@ -25,6 +25,8 @@ for asm in sorted(os.listdir('test')):
           # test mem init importing
           open('a.mem', 'wb').write(asm)
           cmd += ['--mem-init=a.mem']
+          if asm[0] == 'e':
+            cmd += ['--mem-base=1024']
         if 'i64' in asm or 'wasm-only' in asm:
           cmd += ['--wasm-only']
         print '..', asm, wasm
diff --git a/check.py b/check.py
index df9633de8..67adea9ef 100755
--- a/check.py
+++ b/check.py
@@ -370,6 +370,8 @@ for asm in tests:
           # test mem init importing
           open('a.mem', 'wb').write(asm)
           cmd += ['--mem-init=a.mem']
+          if asm[0] == 'e':
+            cmd += ['--mem-base=1024']
         if 'i64' in asm or 'wasm-only' in asm:
           cmd += ['--wasm-only']
         wasm = os.path.join(options.binaryen_test, wasm)
diff --git a/src/passes/CMakeLists.txt b/src/passes/CMakeLists.txt
index b8a0a3986..e47a7d892 100644
--- a/src/passes/CMakeLists.txt
+++ b/src/passes/CMakeLists.txt
@@ -7,6 +7,7 @@ SET(passes_SOURCES
   ExtractFunction.cpp
   Inlining.cpp
   LegalizeJSInterface.cpp
+  MemoryPacking.cpp
   MergeBlocks.cpp
   Metrics.cpp
   NameManager.cpp
diff --git a/src/passes/MemoryPacking.cpp b/src/passes/MemoryPacking.cpp
new file mode 100644
index 000000000..1ba004886
--- /dev/null
+++ b/src/passes/MemoryPacking.cpp
@@ -0,0 +1,80 @@
+/*
+ * Copyright 2016 WebAssembly Community Group participants
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <wasm.h>
+#include <pass.h>
+#include <wasm-builder.h>
+
+namespace wasm {
+
+// Adding segments adds overhead, this is a rough estimate
+const Index OVERHEAD = 8;
+
+struct MemoryPacking : public Pass {
+  void run(PassRunner* runner, Module* module) override {
+    if (!module->memory.exists) return;
+    std::vector<Memory::Segment> packed;
+    for (auto& segment : module->memory.segments) {
+      // skip final zeros
+      while (segment.data.size() > 0 && segment.data.back() == 0) {
+        segment.data.pop_back();
+      }
+      // we can only handle a constant offset for splitting
+      if (auto* offset = segment.offset->dynCast<Const>()) {
+        // Find runs of zeros, and split
+        auto& data = segment.data;
+        auto base = offset->value.geti32();
+        Index start = 0;
+        // create new segments
+        while (start < data.size()) {
+          // skip initial zeros
+          while (start < data.size() && data[start] == 0) {
+            start++;
+          }
+          Index end = start; // end of data-containing part
+          Index next = end; // after zeros we can skip. preserves next >= end
+          while (next < data.size() && (next - end < OVERHEAD)) {
+            if (data[end] != 0) {
+              end++;
+              next = end; // we can try to skip zeros from here
+            } else {
+              // end is on a zero, we are looking to skip
+              if (data[next] != 0) {
+                end = next; // we must extend the segment, including some zeros
+              } else {
+                next++;
+              }
+            }
+          }
+          if (end != start) {
+            packed.emplace_back(Builder(*module).makeConst(Literal(int32_t(base + start))), &data[start], end - start);
+          }
+          start = next;
+        }
+      } else {
+        packed.push_back(segment);
+      }
+    }
+    module->memory.segments.swap(packed);
+  }
+};
+
+Pass *createMemoryPackingPass() {
+  return new MemoryPacking();
+}
+
+} // namespace wasm
+
diff --git a/src/passes/pass.cpp b/src/passes/pass.cpp
index c8704db89..c307fea46 100644
--- a/src/passes/pass.cpp
+++ b/src/passes/pass.cpp
@@ -71,6 +71,7 @@ void PassRegistry::registerPasses() {
   registerPass("extract-function", "leaves just one function (useful for debugging)", createExtractFunctionPass);
   registerPass("inlining", "inlines functions (currently only ones with a single use)", createInliningPass);
   registerPass("legalize-js-interface", "legalizes i64 types on the import/export boundary", createLegalizeJSInterfacePass);
+  registerPass("memory-packing", "packs memory into separate segments, skipping zeros", createMemoryPackingPass);
   registerPass("merge-blocks", "merges blocks to their parents", createMergeBlocksPass);
   registerPass("metrics", "reports metrics", createMetricsPass);
   registerPass("nm", "name list", createNameListPass);
@@ -100,6 +101,7 @@ void PassRunner::addDefaultOptimizationPasses() {
   addDefaultFunctionOptimizationPasses();
   add("duplicate-function-elimination"); // optimizations show more functions as duplicate
   add("remove-unused-functions");
+  add("memory-packing");
 }
 
 void PassRunner::addDefaultFunctionOptimizationPasses() {
@@ -127,6 +129,7 @@ void PassRunner::addDefaultFunctionOptimizationPasses() {
 void PassRunner::addDefaultGlobalOptimizationPasses() {
   add("duplicate-function-elimination");
   add("remove-unused-functions");
+  add("memory-packing");
 }
 
 void PassRunner::run() {
diff --git a/src/passes/passes.h b/src/passes/passes.h
index bb577f86a..c71831e73 100644
--- a/src/passes/passes.h
+++ b/src/passes/passes.h
@@ -32,8 +32,9 @@ Pass *createFullPrinterPass();
 Pass *createInliningPass();
 Pass *createLegalizeJSInterfacePass();
 Pass *createLowerIfElsePass();
-Pass *createMinifiedPrinterPass();
+Pass *createMemoryPackingPass();
 Pass *createMergeBlocksPass();
+Pass *createMinifiedPrinterPass();
 Pass *createMetricsPass();
 Pass *createNameListPass();
 Pass *createNameManagerPass();
diff --git a/src/tools/asm2wasm.cpp b/src/tools/asm2wasm.cpp
index def361066..c5590c5eb 100644
--- a/src/tools/asm2wasm.cpp
+++ b/src/tools/asm2wasm.cpp
@@ -51,6 +51,10 @@ int main(int argc, const char *argv[]) {
            [](Options *o, const std::string &argument) {
              o->extra["mem init"] = argument;
            })
+      .add("--mem-base", "-mb", "Set the location to write the memory initialization (--mem-init) file (GLOBAL_BASE in emscripten). If not provided, the memoryBase global import is used.", Options::Arguments::One,
+           [](Options *o, const std::string &argument) {
+             o->extra["mem base"] = argument;
+           })
       .add("--total-memory", "-m", "Total memory size", Options::Arguments::One,
            [](Options *o, const std::string &argument) {
              o->extra["total memory"] = argument;
@@ -104,7 +108,19 @@ int main(int argc, const char *argv[]) {
     auto filename = memInit->second.c_str();
     auto data(read_file<std::vector<char>>(filename, Flags::Binary, options.debug ? Flags::Debug : Flags::Release));
     // create the memory segment
-    wasm.memory.segments.emplace_back(Builder(wasm).makeGetGlobal(Name("memoryBase"), i32), data);
+    Expression* init;
+    const auto &memBase = options.extra.find("mem base");
+    if (memBase == options.extra.end()) {
+      init = Builder(wasm).makeGetGlobal(Name("memoryBase"), i32);
+    } else {
+      init = Builder(wasm).makeConst(Literal(int32_t(atoi(memBase->second.c_str()))));
+    }
+    wasm.memory.segments.emplace_back(init, data);
+    if (runOptimizationPasses) {
+      PassRunner runner(&wasm);
+      runner.add("memory-packing");
+      runner.run();
+    }
   }
 
   if (options.debug) std::cerr << "printing..." << std::endl;
diff --git a/test/emcc_O2_hello_world.fromasm b/test/emcc_O2_hello_world.fromasm
index 9646d4d62..70ff7a09e 100644
--- a/test/emcc_O2_hello_world.fromasm
+++ b/test/emcc_O2_hello_world.fromasm
@@ -33,7 +33,7 @@
   (import "env" "memoryBase" (global $memoryBase i32))
   (import "env" "tableBase" (global $tableBase i32))
   (elem (i32.const 0) $b0 $___stdio_close $b1 $b1 $___stdout_write $___stdio_seek $b1 $___stdio_write $b1 $b1 $b2 $b2 $b2 $b2 $_cleanup_418 $b2 $b2 $b2)
-  (data (get_global $memoryBase) "emcc_O2_hello_world.asm.js")
+  (data (i32.const 1024) "emcc_O2_hello_world.asm.js")
   (global $STACKTOP (mut i32) (get_global $STACKTOP$asm2wasm$import))
   (global $STACK_MAX (mut i32) (get_global $STACK_MAX$asm2wasm$import))
   (global $tempDoublePtr (mut i32) (get_global $tempDoublePtr$asm2wasm$import))
diff --git a/test/emcc_hello_world.fromasm b/test/emcc_hello_world.fromasm
index 01a30d8eb..043ad0d96 100644
--- a/test/emcc_hello_world.fromasm
+++ b/test/emcc_hello_world.fromasm
@@ -42,7 +42,7 @@
   (import "env" "memoryBase" (global $memoryBase i32))
   (import "env" "tableBase" (global $tableBase i32))
   (elem (i32.const 0) $b0 $___stdio_close $b1 $b1 $___stdout_write $___stdio_seek $___stdio_write $b1 $b1 $b1 $b2 $b2 $b2 $b2 $b2 $_cleanup $b2 $b2)
-  (data (get_global $memoryBase) "emcc_hello_world.asm.js")
+  (data (i32.const 1024) "emcc_hello_world.asm.js")
   (global $STACKTOP (mut i32) (get_global $STACKTOP$asm2wasm$import))
   (global $STACK_MAX (mut i32) (get_global $STACK_MAX$asm2wasm$import))
   (global $tempDoublePtr (mut i32) (get_global $tempDoublePtr$asm2wasm$import))
diff --git a/test/empty.fromasm b/test/empty.fromasm
index a8d289e29..a88b44007 100644
--- a/test/empty.fromasm
+++ b/test/empty.fromasm
@@ -3,5 +3,5 @@
   (import "env" "table" (table 0 0 anyfunc))
   (import "env" "memoryBase" (global $memoryBase i32))
   (import "env" "tableBase" (global $tableBase i32))
-  (data (get_global $memoryBase) "empty.asm.js")
+  (data (i32.const 1024) "empty.asm.js")
 )
diff --git a/test/passes/memory-packing.txt b/test/passes/memory-packing.txt
new file mode 100644
index 000000000..1f068180c
--- /dev/null
+++ b/test/passes/memory-packing.txt
@@ -0,0 +1,20 @@
+(module
+  (import "env" "memory" (memory $0 2048 2048))
+  (import "env" "memoryBase" (global $memoryBase i32))
+  (data (get_global $memoryBase) "waka this cannot be optimized\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00we don\'t know where it will go")
+  (data (i32.const 1024) "waka this CAN be optimized")
+  (data (i32.const 1107) "we DO know where it will go")
+  (data (i32.const 2057) "zeros before")
+  (data (i32.const 3000) "zeros after")
+  (data (i32.const 4000) "zeros\00in\00the\00middle")
+  (data (i32.const 4035) "nice skip here")
+  (data (i32.const 4066) "another\00but no")
+)
+(module
+  (import "env" "memory" (memory $0 2048 2048))
+  (import "env" "memoryBase" (global $memoryBase i32))
+)
+(module
+  (import "env" "memory" (memory $0 2048 2048))
+  (import "env" "memoryBase" (global $memoryBase i32))
+)
diff --git a/test/passes/memory-packing.wast b/test/passes/memory-packing.wast
new file mode 100644
index 000000000..eb343188e
--- /dev/null
+++ b/test/passes/memory-packing.wast
@@ -0,0 +1,20 @@
+(module
+  (import "env" "memory" (memory $0 2048 2048))
+  (import "env" "memoryBase" (global $memoryBase i32))
+  (data (get_global $memoryBase) "waka this cannot be optimized\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00we don't know where it will go")
+  (data (i32.const 1024) "waka this CAN be optimized\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00we DO know where it will go")
+  (data (i32.const 2000) "\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00zeros before")
+  (data (i32.const 3000) "zeros after\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00")
+  (data (i32.const 4000) "zeros\00in\00the\00middle\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00nice skip here\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00another\00but no")
+)
+(module
+  (import "env" "memory" (memory $0 2048 2048))
+  (import "env" "memoryBase" (global $memoryBase i32))
+  ;; nothing
+)
+(module
+  (import "env" "memory" (memory $0 2048 2048))
+  (import "env" "memoryBase" (global $memoryBase i32))
+  (data (i32.const 4066) "") ;; empty
+)
+