AST Builder class, and use it to optimzie umoddi4 in asm2wasm

5 files changed, 231 insertions, 6 deletions

diff --git a/src/asm2wasm.h b/src/asm2wasm.h
index 1aca67eff..a3cbb95c7 100644
--- a/src/asm2wasm.h
+++ b/src/asm2wasm.h
@@ -29,6 +29,7 @@
 #include "asm_v_wasm.h"
 #include "pass.h"
 #include "ast_utils.h"
+#include "wasm-builder.h"
 
 namespace wasm {
 
@@ -206,6 +207,10 @@ private:
 
   IString tempDoublePtr; // imported name of tempDoublePtr
 
+  // possibly-minified names, detected via their exports
+  IString udivmoddi4;
+  IString getTempRet0;
+
   // function types. we fill in this information as we see
   // uses, in the first pass
 
@@ -664,6 +669,10 @@ void Asm2WasmBuilder::processAsm(Ref ast) {
           // asm.js memory growth provides this special non-asm function, which we don't need (we use grow_memory)
           assert(!wasm.checkFunction(value));
           continue;
+        } else if (key == UDIVMODDI4) {
+          udivmoddi4 = value;
+        } else if (key == GET_TEMP_RET0) {
+          getTempRet0 = value;
         }
         assert(wasm.checkFunction(value));
         auto export_ = allocator.alloc<Export>();
@@ -746,10 +755,108 @@ void Asm2WasmBuilder::processAsm(Ref ast) {
   }
 
   wasm.memory.exportName = MEMORY;
+
+  if (udivmoddi4.is()) {
+    // generate a wasm-optimized __udivmoddi4 method, which we can do much more efficiently in wasm
+    assert(getTempRet0.is());
+    // first, figure out which minified global is tempRet0
+    int tempRet0;
+    {
+      Expression* curr = wasm.getFunction(getTempRet0)->body;
+      if (curr->is<Block>()) curr = curr->cast<Block>()->list[0];
+      curr = curr->cast<Return>()->value;
+      auto* load = curr->cast<Load>();
+      auto* ptr = load->ptr->cast<Const>();
+      tempRet0 = ptr->value.geti32() + load->offset;
+    }
+    // udivmoddi4 receives xl, xh, yl, yl, r, and
+    //    if r then *r = x % y
+    //    returns x / y
+    auto* func = wasm.getFunction(udivmoddi4);
+    assert(!func->type.is());
+    Name xl = func->params[0].name,
+         xh = func->params[1].name,
+         yl = func->params[2].name,
+         yh = func->params[3].name,
+         r = func->params[4].name;
+    func->locals.clear();
+    Name x64("x64"), y64("y64");
+    func->locals.emplace_back(x64, i64);
+    func->locals.emplace_back(y64, i64);
+    Builder builder(wasm);
+    auto* body = allocator.alloc<Block>();
+    auto recreateI64 = [&](Name target, Name low, Name high) {
+      return builder.makeSetLocal(
+        target,
+        builder.makeBinary(
+          Or,
+          builder.makeUnary(
+            ExtendUInt32,
+            builder.makeGetLocal(low, i32)
+          ),
+          builder.makeBinary(
+            Shl,
+            builder.makeUnary(
+              ExtendUInt32,
+              builder.makeGetLocal(high, i32)
+            ),
+            builder.makeConst(Literal(int64_t(32)))
+          )
+        )
+      );
+    };
+    body->list.push_back(recreateI64(x64, xl, xh));
+    body->list.push_back(recreateI64(y64, yl, yh));
+    body->list.push_back(
+      builder.makeIf(
+        builder.makeGetLocal(r, i32),
+        builder.makeStore(
+          8, 0, 8,
+          builder.makeGetLocal(r, i32),
+          builder.makeBinary(
+            RemU,
+            builder.makeGetLocal(x64, i64),
+            builder.makeGetLocal(y64, i64)
+          )
+        )
+      )
+    );
+    body->list.push_back(
+      builder.makeSetLocal(
+        x64,
+        builder.makeBinary(
+          DivU,
+          builder.makeGetLocal(x64, i64),
+          builder.makeGetLocal(y64, i64)
+        )
+      )
+    );
+    body->list.push_back(
+      builder.makeStore(
+        4, 0, 4,
+        builder.makeConst(Literal(int32_t(tempRet0))),
+        builder.makeUnary(
+          WrapInt64,
+          builder.makeBinary(
+            ShrU,
+            builder.makeGetLocal(x64, i64),
+            builder.makeConst(Literal(int64_t(32)))
+          )
+        )
+      )
+    );
+    body->list.push_back(
+      builder.makeUnary(
+        WrapInt64,
+        builder.makeGetLocal(x64, i64)
+      )
+    );
+    func->body = body;
+  }
 }
 
 Function* Asm2WasmBuilder::processFunction(Ref ast) {
-  //if (ast[1] != IString("qta")) return nullptr;
+  auto name = ast[1]->getIString();
 
   if (debug) {
     std::cout << "\nfunc: " << ast[1]->getIString().str << '\n';
@@ -758,7 +865,7 @@ Function* Asm2WasmBuilder::processFunction(Ref ast) {
   }
 
   auto function = allocator.alloc<Function>();
-  function->name = ast[1]->getIString();
+  function->name = name;
   Ref params = ast[2];
   Ref body = ast[3];
 
@@ -1601,7 +1708,6 @@ Function* Asm2WasmBuilder::processFunction(Ref ast) {
   // cleanups/checks
   assert(breakStack.size() == 0 && continueStack.size() == 0);
   assert(parentLabel.isNull());
-
   return function;
 }
 
diff --git a/src/emscripten-optimizer/parser.cpp b/src/emscripten-optimizer/parser.cpp
index ce4737476..b8297fc29 100644
--- a/src/emscripten-optimizer/parser.cpp
+++ b/src/emscripten-optimizer/parser.cpp
@@ -48,7 +48,9 @@ IString TOPLEVEL("toplevel"),
         INF("inf"),
         NaN("nan"),
         TEMP_RET0("tempRet0"),
+        GET_TEMP_RET0("getTempRet0"),
         LLVM_CTTZ_I32("_llvm_cttz_i32"),
+        UDIVMODDI4("___udivmoddi4"),
         UNARY_PREFIX("unary-prefix"),
         UNARY_POSTFIX("unary-postfix"),
         MATH_FROUND("Math_fround"),
diff --git a/src/emscripten-optimizer/parser.h b/src/emscripten-optimizer/parser.h
index e10044fbc..367c831e2 100644
--- a/src/emscripten-optimizer/parser.h
+++ b/src/emscripten-optimizer/parser.h
@@ -63,7 +63,9 @@ extern IString TOPLEVEL,
                INF,
                NaN,
                TEMP_RET0,
+               GET_TEMP_RET0,
                LLVM_CTTZ_I32,
+               UDIVMODDI4,
                UNARY_PREFIX,
                UNARY_POSTFIX,
                MATH_FROUND,
diff --git a/src/wasm-builder.h b/src/wasm-builder.h
new file mode 100644
index 000000000..de3371274
--- /dev/null
+++ b/src/wasm-builder.h
@@ -0,0 +1,116 @@
+/*
+ * 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.
+ */
+
+#ifndef wasm_builder_h
+#define wasm_builder_h
+
+#include <wasm.h>
+
+namespace wasm {
+
+class Builder {
+  MixedArena &allocator;
+
+public:
+  Builder(AllocatingModule& wasm) : allocator(wasm.allocator) {}
+
+  // Nop TODO: add all the rest
+  // Block
+  If* makeIf(Expression* condition, Expression* ifTrue, Expression* ifFalse=nullptr) {
+    auto* ret = allocator.alloc<If>();
+    ret->condition = condition; ret->ifTrue = ifTrue; ret->ifFalse = ifFalse;
+    ret->finalize();
+    return ret;
+  }
+  // Loop
+  // Break
+  // Switch
+  // CallBase
+  // Call
+  // CallImport
+  // FunctionType
+  GetLocal* makeGetLocal(Name name, WasmType type) {
+    auto* ret = allocator.alloc<GetLocal>();
+    ret->name = name;
+    ret->type = type;
+    return ret;
+  }
+  SetLocal* makeSetLocal(Name name, Expression* value) {
+    auto* ret = allocator.alloc<SetLocal>();
+    ret->name = name;
+    ret->value = value;
+    ret->type = value->type;
+    return ret;
+  }
+  // Load
+  Store* makeStore(unsigned bytes, uint32_t offset, unsigned align, Expression *ptr, Expression *value) {
+    auto* ret = allocator.alloc<Store>();
+    ret->bytes = bytes; ret->offset = offset; ret->align = align; ret->ptr = ptr; ret->value = value;
+    ret->type = value->type;
+    return ret;
+  }
+  Const* makeConst(Literal value) {
+    auto* ret = allocator.alloc<Const>();
+    ret->value = value;
+    ret->type = value.type;
+    return ret;
+  }
+  Unary* makeUnary(UnaryOp op, Expression *value, WasmType type=none) {
+    auto* ret = allocator.alloc<Unary>();
+    ret->op = op; ret->value = value;
+    if (type != none) {
+      ret->type = type; // some opcodes have more than one type, user must provide it
+    } else {
+      switch (op) {
+        case Clz:
+        case Ctz:
+        case Popcnt:
+        case Neg:
+        case Abs:
+        case Ceil:
+        case Floor:
+        case Trunc:
+        case Nearest:
+        case Sqrt: ret->type = value->type; break;
+        case EqZ: ret->type = i32; break;
+        case ExtendSInt32: case ExtendUInt32: ret->type = i64; break;
+        case WrapInt64: ret->type = i32; break;
+        case PromoteFloat32: ret->type = f64; break;
+        case DemoteFloat64: ret->type = f32; break;
+        case TruncSFloat32: case TruncUFloat32: case TruncSFloat64: case TruncUFloat64: case ReinterpretFloat:
+        case ConvertSInt32: case ConvertUInt32: case ConvertSInt64: case ConvertUInt64: case ReinterpretInt: abort(); // user needs to say the type
+        default: abort();
+      }
+    }
+    return ret;
+  }
+  Binary* makeBinary(BinaryOp op, Expression *left, Expression *right) {
+    auto* ret = allocator.alloc<Binary>();
+    ret->op = op; ret->left = left; ret->right = right;
+    ret->finalize();
+    return ret;
+  }
+  // Select
+  // Return
+  // Host
+  // Unreachable
+
+};
+
+} // namespace wasm
+
+#endif // wasm_builder_h
+
diff --git a/src/wasm.h b/src/wasm.h
index 2fa117b91..a064a3431 100644
--- a/src/wasm.h
+++ b/src/wasm.h
@@ -975,10 +975,9 @@ public:
   UnaryOp op;
   Expression *value;
 
-  // the type is always the type of the operands,
-  // except for relationals
-
   bool isRelational() { return op == EqZ; }
+
+  // no finalize since some opcodes have more than one type, so user must set it anyhow
 };
 
 class Binary : public Expression {