Const hoisting (#1176)

A pass that hoists repeating constants to a local, and replaces their uses with a get of that local. This can reduce binary size, but can also *increase* gzip size, so it's mostly for experimentation and not used by default.

1 files changed, 131 insertions, 0 deletions

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