Merge pull request #329 from WebAssembly/opts

Begin an AST Builder helper class, and more asm2wasm opts

7 files changed, 314 insertions, 33 deletions

diff --git a/src/asm2wasm.h b/src/asm2wasm.h
index 910134024..72a8b9048 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 {
 
@@ -132,6 +133,8 @@ class Asm2WasmBuilder {
 
   MixedArena &allocator;
 
+  Builder builder;
+
   // globals
 
   unsigned nextGlobal; // next place to put a global
@@ -202,8 +205,14 @@ private:
   IString Math_ceil;
   IString Math_sqrt;
 
+  IString llvm_cttz_i32;
+
   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
 
@@ -260,6 +269,7 @@ public:
  Asm2WasmBuilder(AllocatingModule& wasm, bool memoryGrowth, bool debug, bool imprecise)
      : wasm(wasm),
        allocator(wasm.allocator),
+       builder(wasm),
        nextGlobal(8),
        maxGlobal(1000),
        memoryGrowth(memoryGrowth),
@@ -486,10 +496,15 @@ void Asm2WasmBuilder::processAsm(Ref ast) {
       assert(module[0] == NAME);
       moduleName = module[1]->getIString();
       if (moduleName == ENV) {
-        if (imported[2] == TEMP_DOUBLE_PTR) {
+        auto base = imported[2]->getIString();
+        if (base == TEMP_DOUBLE_PTR) {
           assert(tempDoublePtr.isNull());
           tempDoublePtr = name;
           // we don't return here, as we can only optimize out some uses of tDP. So it remains imported
+        } else if (base == LLVM_CTTZ_I32) {
+          assert(llvm_cttz_i32.isNull());
+          llvm_cttz_i32 = name;
+          return;
         }
       }
     }
@@ -657,6 +672,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>();
@@ -739,10 +758,107 @@ void Asm2WasmBuilder::processAsm(Ref ast) {
   }
 
   wasm.memory.exportName = MEMORY;
+
+  if (udivmoddi4.is() && getTempRet0.is()) {
+    // generate a wasm-optimized __udivmoddi4 method, which we can do much more efficiently in wasm
+    // we can only do this if we know getTempRet0 as well since we use it to figure out which minified global is tempRet0
+    // (getTempRet0 might be an import, if this is a shared module, so we can't optimize that case)
+    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);
+    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';
@@ -751,7 +867,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];
 
@@ -1092,10 +1208,10 @@ Function* Asm2WasmBuilder::processFunction(Ref ast) {
           ret->type = WasmType::i32;
           return ret;
         }
-        if (name == Math_clz32) {
+        if (name == Math_clz32 || name == llvm_cttz_i32) {
           assert(ast[2]->size() == 1);
           auto ret = allocator.alloc<Unary>();
-          ret->op = Clz;
+          ret->op = name == Math_clz32 ? Clz : Ctz;
           ret->value = process(ast[2][0]);
           ret->type = WasmType::i32;
           return ret;
@@ -1279,9 +1395,8 @@ Function* Asm2WasmBuilder::processFunction(Ref ast) {
         Break *breakOut = allocator.alloc<Break>();
         breakOut->name = out;
         If *condition = allocator.alloc<If>();
-        condition->condition = process(ast[1]);
-        condition->ifTrue = allocator.alloc<Nop>();
-        condition->ifFalse = breakOut;
+        condition->condition = builder.makeUnary(EqZ, process(ast[1]));
+        condition->ifTrue = breakOut;
         auto body = allocator.alloc<Block>();
         body->list.push_back(condition);
         body->list.push_back(process(ast[2]));
@@ -1377,9 +1492,8 @@ Function* Asm2WasmBuilder::processFunction(Ref ast) {
       Break *breakOut = allocator.alloc<Break>();
       breakOut->name = out;
       If *condition = allocator.alloc<If>();
-      condition->condition = process(fcond);
-      condition->ifTrue = allocator.alloc<Nop>();
-      condition->ifFalse = breakOut;
+      condition->condition = builder.makeUnary(EqZ, process(fcond));
+      condition->ifTrue = breakOut;
       auto body = allocator.alloc<Block>();
       body->list.push_back(condition);
       body->list.push_back(process(fbody));
@@ -1594,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 7005dc4b4..b8297fc29 100644
--- a/src/emscripten-optimizer/parser.cpp
+++ b/src/emscripten-optimizer/parser.cpp
@@ -48,6 +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 da3e6f5c7..367c831e2 100644
--- a/src/emscripten-optimizer/parser.h
+++ b/src/emscripten-optimizer/parser.h
@@ -63,6 +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/passes/OptimizeInstructions.cpp b/src/passes/OptimizeInstructions.cpp
index 638977353..de342b43f 100644
--- a/src/passes/OptimizeInstructions.cpp
+++ b/src/passes/OptimizeInstructions.cpp
@@ -36,6 +36,28 @@ struct OptimizeInstructions : public WalkerPass<WasmWalker<OptimizeInstructions>
       }
     }
   }
+  void visitUnary(Unary* curr) {
+    if (curr->op == EqZ) {
+      // fold comparisons that flow into an EqZ
+      auto* child = curr->value->dyn_cast<Binary>();
+      if (child && (child->type == i32 || child->type == i64)) {
+        switch (child->op) {
+          case Eq:  child->op = Ne; break;
+          case Ne:  child->op = Eq; break;
+          case LtS: child->op = GeS; break;
+          case LtU: child->op = GeU; break;
+          case LeS: child->op = GtS; break;
+          case LeU: child->op = GtU; break;
+          case GtS: child->op = LeS; break;
+          case GtU: child->op = LeU; break;
+          case GeS: child->op = LtS; break;
+          case GeU: child->op = LtU; break;
+          default: return;
+        }
+        replaceCurrent(child);
+      }
+    }
+  }
 };
 
 static RegisterPass<OptimizeInstructions> registerPass("optimize-instructions", "optimizes instruction combinations");
diff --git a/src/passes/Print.cpp b/src/passes/Print.cpp
index 056b61939..8e3d503b8 100644
--- a/src/passes/Print.cpp
+++ b/src/passes/Print.cpp
@@ -26,17 +26,27 @@ namespace wasm {
 
 struct PrintSExpression : public WasmVisitor<PrintSExpression, void> {
   std::ostream& o;
-  unsigned indent;
+  unsigned indent = 0;
+
   bool minify;
   const char *maybeSpace;
   const char *maybeNewLine;
 
-  PrintSExpression(std::ostream& o, bool minify = false)
-    : o(o), indent(0), minify(minify) {
+  bool fullAST = false; // whether to not elide nodes in output when possible
+                        // (like implicit blocks)
+
+  PrintSExpression(std::ostream& o) : o(o) {
+    setMinify(false);
+  }
+
+  void setMinify(bool minify_) {
+    minify = minify_;
     maybeSpace = minify ? "" : " ";
     maybeNewLine = minify ? "" : "\n";
   }
 
+  void setFullAST(bool fullAST_) { fullAST = fullAST_; }
+
   void incIndent() {
     if (minify) return;
     o << '\n';
@@ -95,13 +105,13 @@ struct PrintSExpression : public WasmVisitor<PrintSExpression, void> {
     incIndent();
     printFullLine(curr->condition);
     // ifTrue and False have implict blocks, avoid printing them if possible
-    if (curr->ifTrue->is<Block>() && curr->ifTrue->dyn_cast<Block>()->name.isNull() && curr->ifTrue->dyn_cast<Block>()->list.size() == 1) {
+    if (!fullAST && curr->ifTrue->is<Block>() && curr->ifTrue->dyn_cast<Block>()->name.isNull() && curr->ifTrue->dyn_cast<Block>()->list.size() == 1) {
       printFullLine(curr->ifTrue->dyn_cast<Block>()->list.back());
     } else {
       printFullLine(curr->ifTrue);
     }
     if (curr->ifFalse) {
-      if (curr->ifFalse->is<Block>() && curr->ifFalse->dyn_cast<Block>()->name.isNull() && curr->ifFalse->dyn_cast<Block>()->list.size() == 1) {
+      if (!fullAST && curr->ifFalse->is<Block>() && curr->ifFalse->dyn_cast<Block>()->name.isNull() && curr->ifFalse->dyn_cast<Block>()->list.size() == 1) {
         printFullLine(curr->ifFalse->dyn_cast<Block>()->list.back());
       } else {
         printFullLine(curr->ifFalse);
@@ -120,7 +130,7 @@ struct PrintSExpression : public WasmVisitor<PrintSExpression, void> {
     }
     incIndent();
     auto block = curr->body->dyn_cast<Block>();
-    if (block && block->name.isNull()) {
+    if (!fullAST && block && block->name.isNull()) {
       // wasm spec has loops containing children directly, while our ast
       // has a single child for simplicity. print out the optimal form.
       for (auto expression : block->list) {
@@ -435,7 +445,7 @@ struct PrintSExpression : public WasmVisitor<PrintSExpression, void> {
     }
     // It is ok to emit a block here, as a function can directly contain a list, even if our
     // ast avoids that for simplicity. We can just do that optimization here..
-    if (curr->body->is<Block>() && curr->body->cast<Block>()->name.isNull()) {
+    if (!fullAST && curr->body->is<Block>() && curr->body->cast<Block>()->name.isNull()) {
       Block* block = curr->body->cast<Block>();
       for (auto item : block->list) {
         printFullLine(item);
@@ -526,8 +536,6 @@ struct PrintSExpression : public WasmVisitor<PrintSExpression, void> {
   }
 };
 
-// Pass entry point. Eventually this will direct printing to one of various options.
-
 void Printer::run(PassRunner* runner, Module* module) {
   PrintSExpression print(o);
   print.visitModule(module);
@@ -536,26 +544,42 @@ void Printer::run(PassRunner* runner, Module* module) {
 static RegisterPass<Printer> registerPass("print", "print in s-expression format");
 
 // Prints out a minified module
+
 class MinifiedPrinter : public Printer {
   public:
   MinifiedPrinter() : Printer() {}
   MinifiedPrinter(std::ostream& o) : Printer(o) {}
 
-  void run(PassRunner* runner, Module* module) override;
+  void run(PassRunner* runner, Module* module) override {
+    PrintSExpression print(o);
+    print.setMinify(true);
+    print.visitModule(module);
+  }
 };
 
-void MinifiedPrinter::run(PassRunner* runner, Module* module) {
-  PrintSExpression print(o, true);
-  print.visitModule(module);
-}
+static RegisterPass<MinifiedPrinter> registerMinifyPass("print-minified", "print in minified s-expression format");
 
+// Prints out a module withough elision, i.e., the full ast
 
-static RegisterPass<MinifiedPrinter> registerMinifyPass("print-minified", "print in minified s-expression format");
+class FullPrinter : public Printer {
+  public:
+  FullPrinter() : Printer() {}
+  FullPrinter(std::ostream& o) : Printer(o) {}
+
+  void run(PassRunner* runner, Module* module) override {
+    PrintSExpression print(o);
+    print.setFullAST(true);
+    print.visitModule(module);
+  }
+};
+
+static RegisterPass<FullPrinter> registerFullASTPass("print-full", "print in full s-expression format");
 
 // Print individual expressions
 
 std::ostream& WasmPrinter::printExpression(Expression* expression, std::ostream& o, bool minify) {
-  PrintSExpression print(o, minify);
+  PrintSExpression print(o);
+  print.setMinify(minify);
   print.visit(expression);
   return o;
 }
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 f985e9b59..c9494d4d6 100644
--- a/src/wasm.h
+++ b/src/wasm.h
@@ -742,7 +742,8 @@ public:
     ReturnId,
     HostId,
     NopId,
-    UnreachableId
+    UnreachableId,
+    NumExpressionIds
   };
   Id _id;
 
@@ -827,7 +828,7 @@ public:
   Expression *condition, *ifTrue, *ifFalse;
 
   void finalize() {
-    if (condition) {
+    if (ifFalse) {
       type = getReachableWasmType(ifTrue->type, ifFalse->type);
     }
   }
@@ -975,10 +976,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 {