5 files changed, 135 insertions, 1 deletions
diff --git a/src/passes/CMakeLists.txt b/src/passes/CMakeLists.txt
index edbf945cf..6870259c4 100644
--- a/src/passes/CMakeLists.txt
+++ b/src/passes/CMakeLists.txt
@@ -3,6 +3,7 @@ SET(passes_SOURCES
   CoalesceLocals.cpp
   CodePushing.cpp
   CodeFolding.cpp
+  ConstHoisting.cpp
   DeadCodeElimination.cpp
   DuplicateFunctionElimination.cpp
   ExtractFunction.cpp
diff --git a/src/passes/ConstHoisting.cpp b/src/passes/ConstHoisting.cpp
new file mode 100644
index 000000000..bddc0b5c5
--- /dev/null
+++ b/src/passes/ConstHoisting.cpp
@@ -0,0 +1,131 @@
+/*
+ * Copyright 2017 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.
+ */
+
+//
+// Hoists repeated constants to a local. A get_local takes 2 bytes
+// in most cases, and if a const is larger than that, it may be
+// better to store it to a local, then get it from that local.
+//
+// WARNING: this often shrinks code size, but can *increase* gzip
+//          size. apparently having the constants in their proper
+//          places lets them be compressed better, across
+//          functions, etc.
+//
+
+#include <map>
+
+#include <wasm.h>
+#include <pass.h>
+#include <wasm-binary.h>
+#include <wasm-builder.h>
+
+namespace wasm {
+
+// with fewer uses than this, it is never beneficial to hoist
+static const Index MIN_USES = 2;
+
+struct ConstHoisting : public WalkerPass<PostWalker<ConstHoisting>> {
+  bool isFunctionParallel() override { return true; }
+
+  Pass* create() override { return new ConstHoisting; }
+
+  std::map<Literal, std::vector<Expression**>> uses;
+
+  void visitConst(Const* curr) {
+    uses[curr->value].push_back(getCurrentPointer());
+  }
+
+  void visitFunction(Function* curr) {
+    std::vector<Expression*> prelude;
+    for (auto& pair : uses) {
+      auto value = pair.first;
+      auto& vec = pair.second;
+      auto num = vec.size();
+      if (worthHoisting(value, num)) {
+        prelude.push_back(hoist(vec));
+      }
+    }
+    if (!prelude.empty()) {
+      Builder builder(*getModule());
+      // merge-blocks can optimize this into a single block later in most cases
+      curr->body = builder.makeSequence(
+        builder.makeBlock(prelude),
+        curr->body
+      );
+    }
+  }
+
+private:
+  bool worthHoisting(Literal value, Index num) {
+    if (num < MIN_USES) return false;
+    // measure the size of the constant
+    Index size;
+    switch (value.type) {
+      case i32: {
+        size = getWrittenSize(S32LEB(value.geti32()));
+        break;
+      }
+      case i64: {
+        size = getWrittenSize(S64LEB(value.geti64()));
+        break;
+      }
+      case f32:
+      case f64: {
+        size = getWasmTypeSize(value.type);
+        break;
+      }
+      default: WASM_UNREACHABLE();
+    }
+    // compute the benefit, of replacing the uses with
+    // one use + a set and then a get for each use
+    // doing the algebra, the criterion here is when
+    //   size > 2(1+num)/(num-1)
+    // or
+    //   num > (size+2)/(size-2)
+    auto before = num * size;
+    auto after = size + 2 /* set_local */ + (2 /* get_local */ * num);
+    return after < before;
+  }
+
+  template<typename T>
+  Index getWrittenSize(const T& thing) {
+    BufferWithRandomAccess buffer;
+    buffer << thing;
+    return buffer.size();
+  }
+
+  // replace all the uses with gets, for a local set at the top. returns
+  // the set.
+  Expression* hoist(std::vector<Expression**>& vec) {
+    auto type = (*(vec[0]))->type;
+    Builder builder(*getModule());
+    auto temp = builder.addVar(getFunction(), type);
+    auto* ret = builder.makeSetLocal(
+      temp,
+      *(vec[0])
+    );
+    for (auto item : vec) {
+      *item = builder.makeGetLocal(temp, type);
+    }
+    return ret;
+  }
+};
+
+Pass *createConstHoistingPass() {
+  return new ConstHoisting();
+}
+
+} // namespace wasm
diff --git a/src/passes/DuplicateFunctionElimination.cpp b/src/passes/DuplicateFunctionElimination.cpp
index 5d55c7318..a96bd8fdf 100644
--- a/src/passes/DuplicateFunctionElimination.cpp
+++ b/src/passes/DuplicateFunctionElimination.cpp
@@ -56,7 +56,7 @@ private:
     digest = rehash(digest, hash);
   }
   void hash64(uint64_t hash) {
-    digest = rehash(rehash(digest, hash >> 32), uint32_t(hash));
+    digest = rehash(rehash(digest, uint32_t(hash >> 32)), uint32_t(hash));
   };
 };
 
diff --git a/src/passes/pass.cpp b/src/passes/pass.cpp
index 728fe2371..4ec454a50 100644
--- a/src/passes/pass.cpp
+++ b/src/passes/pass.cpp
@@ -68,6 +68,7 @@ void PassRegistry::registerPasses() {
   registerPass("coalesce-locals-learning", "reduce # of locals by coalescing and learning", createCoalesceLocalsWithLearningPass);
   registerPass("code-pushing", "push code forward, potentially making it not always execute", createCodePushingPass);
   registerPass("code-folding", "fold code, merging duplicates", createCodeFoldingPass);
+  registerPass("const-hoisting", "hoist repeated constants to a local", createConstHoistingPass);
   registerPass("dce", "removes unreachable code", createDeadCodeEliminationPass);
   registerPass("duplicate-function-elimination", "removes duplicate functions", createDuplicateFunctionEliminationPass);
   registerPass("extract-function", "leaves just one function (useful for debugging)", createExtractFunctionPass);
diff --git a/src/passes/passes.h b/src/passes/passes.h
index b1a6cb5c6..4e039f4bf 100644
--- a/src/passes/passes.h
+++ b/src/passes/passes.h
@@ -26,6 +26,7 @@ Pass *createCoalesceLocalsPass();
 Pass *createCoalesceLocalsWithLearningPass();
 Pass *createCodeFoldingPass();
 Pass *createCodePushingPass();
+Pass *createConstHoistingPass();
 Pass *createDeadCodeEliminationPass();
 Pass *createDuplicateFunctionEliminationPass();
 Pass *createExtractFunctionPass();