Merge pull request #231 from WebAssembly/spec-updates

Spec updates

12 files changed, 113 insertions, 324 deletions

diff --git a/src/asm2wasm.h b/src/asm2wasm.h
index be11344b2..aa59faa2d 100644
--- a/src/asm2wasm.h
+++ b/src/asm2wasm.h
@@ -1404,7 +1404,7 @@ Function* Asm2WasmBuilder::processFunction(Ref ast) {
       ret->finalize();
       return ret;
     } else if (what == SWITCH) {
-      IString name;
+      IString name; // for breaking out of the entire switch
       if (!parentLabel.isNull()) {
         name = getBreakLabelName(parentLabel);
         parentLabel = IString();
@@ -1412,10 +1412,11 @@ Function* Asm2WasmBuilder::processFunction(Ref ast) {
         name = getNextId("switch");
       }
       breakStack.push_back(name);
-      auto ret = allocator.alloc<Switch>();
-      ret->name = name;
-      ret->value = process(ast[1]);
-      assert(ret->value->type == i32);
+
+      auto br = allocator.alloc<Switch>();
+      br->condition = process(ast[1]);
+      assert(br->condition->type == i32);
+
       Ref cases = ast[2];
       bool seen = false;
       int min = 0; // the lowest index we see; we will offset to it
@@ -1435,18 +1436,23 @@ Function* Asm2WasmBuilder::processFunction(Ref ast) {
       }
       Binary* offsetor = allocator.alloc<Binary>();
       offsetor->op = BinaryOp::Sub;
-      offsetor->left = ret->value;
+      offsetor->left = br->condition;
       offsetor->right = allocator.alloc<Const>()->set(Literal(min));
       offsetor->type = i32;
-      ret->value = offsetor;
+      br->condition = offsetor;
+
+      auto top = allocator.alloc<Block>();
+      top->list.push_back(br);
+      top->finalize();
+
       for (unsigned i = 0; i < cases->size(); i++) {
         Ref curr = cases[i];
         Ref condition = curr[0];
         Ref body = curr[1];
-        Switch::Case case_;
-        case_.body = processStatements(body, 0);
+        auto case_ = processStatements(body, 0);
+        Name name;
         if (condition->isNull()) {
-          case_.name = ret->default_ = getNextId("switch-default");
+          name = br->default_ = getNextId("switch-default");
         } else {
           assert(condition[0] == NUM || condition[0] == UNARY_PREFIX);
           int32_t index = getLiteral(condition).geti32();
@@ -1454,26 +1460,35 @@ Function* Asm2WasmBuilder::processFunction(Ref ast) {
           index -= min;
           assert(index >= 0);
           size_t index_s = index;
-          case_.name = getNextId("switch-case");
-          if (ret->targets.size() <= index_s) {
-            ret->targets.resize(index_s+1);
+          name = getNextId("switch-case");
+          if (br->targets.size() <= index_s) {
+            br->targets.resize(index_s+1);
           }
-          ret->targets[index_s] = case_.name;
+          br->targets[index_s] = name;
         }
-        ret->cases.push_back(case_);
+        auto next = allocator.alloc<Block>();
+        top->name = name;
+        next->list.push_back(top);
+        next->list.push_back(case_);
+        next->finalize();
+        top = next;
       }
+
       // ensure a default
-      if (ret->default_.isNull()) {
-        Switch::Case defaultCase;
-        defaultCase.name = ret->default_ = getNextId("switch-default");
-        defaultCase.body = allocator.alloc<Nop>(); // ok if others fall through to this
-        ret->cases.push_back(defaultCase);
+      if (br->default_.isNull()) {
+        br->default_ = getNextId("switch-default");
       }
-      for (size_t i = 0; i < ret->targets.size(); i++) {
-        if (ret->targets[i].isNull()) ret->targets[i] = ret->default_;
+      for (size_t i = 0; i < br->targets.size(); i++) {
+        if (br->targets[i].isNull()) br->targets[i] = br->default_;
       }
-      // finalize
+      top->name = br->default_;
+
       breakStack.pop_back();
+
+      // Create a topmost block for breaking out of the entire switch
+      auto ret = allocator.alloc<Block>();
+      ret->name = name;
+      ret->list.push_back(top);
       return ret;
     }
     abort_on("confusing expression", ast);
@@ -1519,39 +1534,6 @@ Function* Asm2WasmBuilder::processFunction(Ref ast) {
 }
 
 void Asm2WasmBuilder::optimize() {
-  // Optimization passes. Note: no effort is made to free nodes that are no longer held on to.
-
-  struct BlockBreakOptimizer : public WasmWalker<BlockBreakOptimizer> {
-    void visitBlock(Block *curr) {
-      // if the block ends in a break on this very block, then just put the value there
-      Break *last = curr->list[curr->list.size()-1]->dyn_cast<Break>();
-      if (last && last->value && last->name == curr->name) {
-        curr->list[curr->list.size()-1] = last->value;
-      }
-      if (curr->list.size() > 1) return; // no hope to remove the block
-      // just one element; maybe we can return just the element
-      if (curr->name.isNull()) {
-        replaceCurrent(curr->list[0]); // cannot break into it
-        return;
-      }
-      // we might be broken to, but maybe there isn't a break (and we may have removed it, leading to this)
-      // look for any breaks to this block
-      BreakSeeker breakSeeker(curr->name);
-      Expression *child = curr->list[0];
-      breakSeeker.walk(child);
-      if (breakSeeker.found == 0) {
-        replaceCurrent(child); // no breaks to here, so eliminate the block
-      }
-    }
-  };
-
-  BlockBreakOptimizer blockBreakOptimizer;
-  for (auto pair : wasm.functionsMap) {
-    blockBreakOptimizer.startWalk(pair.second);
-  }
-
-  // Standard passes
-
   PassRunner passRunner(&allocator);
   passRunner.add("remove-unused-brs");
   passRunner.add("remove-unused-names");
diff --git a/src/passes/LowerCase.cpp b/src/passes/LowerCase.cpp
deleted file mode 100644
index c0ab8d235..000000000
--- a/src/passes/LowerCase.cpp
+++ /dev/null
@@ -1,105 +0,0 @@
-/*
- * 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.
- */
-
-//
-// Lowers switch cases out into blocks,
-//
-/*
-    (tableswitch $switch$0
-      (i32.sub
-        (get_local $x)
-        (i32.const 1)
-      )
-      (table (case $switch-case$1) (case $switch-case$2)) (case $switch-default$3)
-      (case $switch-case$1
-        (return
-          (i32.const 1)
-        )
-      )
-      (case $switch-case$2
-        (return
-          (i32.const 2)
-        )
-      )
-      (case $switch-default$3
-        (nop)
-      )
-    )
-
-  into
-
-    (block $forswitch$switch$0
-      (block $switch-case$3
-        (block $switch-case$2
-          (block $switch-case$1
-            (tableswitch $switch$0
-              (i32.sub
-                (get_local $x)
-                (i32.const 1)
-              )
-              (table (br $switch-case$1) (br $switch-case$2)) (br $switch-default$3)
-            )
-          )
-          (return
-            (i32.const 1)
-          )
-        )
-        (return
-          (i32.const 2)
-        )
-      )
-      (nop)
-    )
-*/
-
-
-#include <memory>
-
-#include <wasm.h>
-#include <pass.h>
-
-namespace wasm {
-
-struct LowerCase : public WalkerPass<WasmWalker<LowerCase, void>> {
-  MixedArena* allocator;
-
-  void prepare(PassRunner* runner, Module *module) override {
-    allocator = runner->allocator;
-  }
-
-  void visitSwitch(Switch *curr) {
-    if (curr->cases.size() == 0) return;
-    auto top = allocator->alloc<Block>();
-    top->list.push_back(curr);
-    top->finalize();
-    for (auto& c : curr->cases) {
-      top->name = c.name;
-      auto next = allocator->alloc<Block>();
-      next->list.push_back(top);
-      next->list.push_back(c.body);
-      next->finalize();
-      top = next;
-    }
-    curr->cases.clear();
-    top->name = curr->name;
-    curr->name = Name();
-    replaceCurrent(top);
-  }
-};
-
-static RegisterPass<LowerCase> registerPass("lower-case", "lowers cases into blocks");
-
-} // namespace wasm
diff --git a/src/passes/NameManager.cpp b/src/passes/NameManager.cpp
index 8ed29c478..8519d70eb 100644
--- a/src/passes/NameManager.cpp
+++ b/src/passes/NameManager.cpp
@@ -44,7 +44,6 @@ void NameManager::visitBreak(Break* curr) {
   names.insert(curr->name);
 }
 void NameManager::visitSwitch(Switch* curr) {
-  names.insert(curr->name);
   names.insert(curr->default_);
   for (auto& target : curr->targets) {
     names.insert(target);
diff --git a/src/passes/Print.cpp b/src/passes/Print.cpp
index e8e917a6e..91c4040f6 100644
--- a/src/passes/Print.cpp
+++ b/src/passes/Print.cpp
@@ -125,29 +125,16 @@ struct PrintSExpression : public WasmVisitor<PrintSExpression, void> {
     decIndent();
   }
   void visitSwitch(Switch *curr) {
-    printOpening(o, "tableswitch ");
-    if (curr->name.is()) o << curr->name;
-    incIndent();
-    printFullLine(curr->value);
-    doIndent(o, indent) << "(table";
-    std::set<Name> caseNames;
-    for (auto& c : curr->cases) {
-      caseNames.insert(c.name);
-    }
+    printOpening(o, "br_table");
     for (auto& t : curr->targets) {
-      o << maybeSpace << "(" << (caseNames.count(t) == 0 ? "br" : "case") << " " << (t.is() ? t : curr->default_) << ")";
+      o << " " << t;
     }
-    o << ")";
-    if (curr->default_.is()) o << " (" << (caseNames.count(curr->default_) == 0 ? "br" : "case") << " " << curr->default_ << ")";
-    o << maybeNewLine;
-    for (auto& c : curr->cases) {
-      doIndent(o, indent);
-      printMinorOpening(o, "case ") << c.name;
-      incIndent();
-      printFullLine(c.body);
-      decIndent();
-      o << maybeNewLine;
+    o << " " << curr->default_;
+    incIndent();
+    if (curr->value) {
+      printFullLine(curr->value);
     }
+    printFullLine(curr->condition);
     decIndent();
   }
 
diff --git a/src/passes/RemoveUnusedNames.cpp b/src/passes/RemoveUnusedNames.cpp
index 6929aa671..a8beaa15e 100644
--- a/src/passes/RemoveUnusedNames.cpp
+++ b/src/passes/RemoveUnusedNames.cpp
@@ -38,6 +38,13 @@ struct RemoveUnusedNames : public WalkerPass<WasmWalker<RemoveUnusedNames>> {
     }
   }
 
+  void visitSwitch(Switch *curr) {
+    for (auto name : curr->targets) {
+      branchesSeen.insert(name);
+    }
+    branchesSeen.insert(curr->default_);
+  }
+
   void visitFunction(Function *curr) {
     branchesSeen.clear();
   }
diff --git a/src/s2wasm.h b/src/s2wasm.h
index 2de6cd60f..16b1125e8 100644
--- a/src/s2wasm.h
+++ b/src/s2wasm.h
@@ -993,7 +993,7 @@ class S2WasmBuilder {
         addToBlock(curr);
       } else if (match("tableswitch")) {
         auto curr = allocator.alloc<Switch>();
-        curr->value = getInput();
+        curr->condition = getInput();
         skipComma();
         curr->default_ = getBranchLabel(getInt());
         while (skipComma()) {
diff --git a/src/wasm-binary.h b/src/wasm-binary.h
index 993b4522d..8a03ca843 100644
--- a/src/wasm-binary.h
+++ b/src/wasm-binary.h
@@ -677,26 +677,17 @@ public:
   }
   void visitSwitch(Switch *curr) {
     if (debug) std::cerr << "zz node: Switch" << std::endl;
-    o << int8_t(BinaryConsts::TableSwitch) << int16_t(curr->cases.size())
-                                           << int16_t(curr->targets.size() + 1);
-    for (size_t i = 0; i < curr->cases.size(); i++) {
-      breakStack.push_back(curr->cases[i].name);
-    }
-    breakStack.push_back(curr->name);
+    o << int8_t(BinaryConsts::TableSwitch) << int16_t(curr->targets.size() + 1) << int8_t(curr->value != nullptr);
     for (auto target : curr->targets) {
       o << (int16_t)getBreakIndex(target);
     }
     o << (int16_t)getBreakIndex(curr->default_);
-    recurse(curr->value);
+    recurse(curr->condition);
     o << int8_t(BinaryConsts::EndMarker);
-    for (auto& c : curr->cases) {
-      recurse(c.body);
+    if (curr->value) {
+      recurse(curr->value);
       o << int8_t(BinaryConsts::EndMarker);
     }
-    breakStack.pop_back(); // name
-    for (size_t i = 0; i < curr->cases.size(); i++) {
-      breakStack.pop_back(); // case
-    }
   }
   void visitCall(Call *curr) {
     if (debug) std::cerr << "zz node: Call" << std::endl;
@@ -1400,29 +1391,17 @@ public:
   }
   void visitSwitch(Switch *curr) {
     if (debug) std::cerr << "zz node: Switch" << std::endl;
-    auto numCases = getInt16();
     auto numTargets = getInt16();
-    for (auto i = 0; i < numCases; i++) {
-      Switch::Case c;
-      c.name = getNextLabel();
-      curr->cases.push_back(c);
-      breakStack.push_back(c.name);
-    }
-    curr->name = getNextLabel();
-    breakStack.push_back(curr->name);
+    auto hasValue = getInt8();
     for (auto i = 0; i < numTargets - 1; i++) {
       curr->targets.push_back(getBreakName(getInt16()));
     }
     curr->default_ = getBreakName(getInt16());
     processExpressions();
-    curr->value = popExpression();
-    for (auto i = 0; i < numCases; i++) {
+    curr->condition = popExpression();
+    if (hasValue) {
       processExpressions();
-      curr->cases[i].body = popExpression();
-    }
-    breakStack.pop_back(); // name
-    for (size_t i = 0; i < curr->cases.size(); i++) {
-      breakStack.pop_back(); // case
+      curr->value = popExpression();
     }
   }
   void visitCall(Call *curr, Name target) {
diff --git a/src/wasm-interpreter.h b/src/wasm-interpreter.h
index a7405e948..223a9e1a5 100644
--- a/src/wasm-interpreter.h
+++ b/src/wasm-interpreter.h
@@ -256,40 +256,24 @@ private:
       }
       Flow visitSwitch(Switch *curr) {
         NOTE_ENTER("Switch");
-        Flow flow = visit(curr->value);
-        if (flow.breaking()) {
-          flow.clearIf(curr->name);
-          return flow;
-        }
+        Flow flow = visit(curr->condition);
+        if (flow.breaking()) return flow;
         NOTE_EVAL1(flow.value);
         int64_t index = flow.value.getInteger();
+
+        if (curr->value) {
+          flow = visit(curr->value);
+          if (flow.breaking()) return flow;
+          NOTE_EVAL1(flow.value);
+        } else {
+          flow = Flow();
+        }
+
         Name target = curr->default_;
         if (index >= 0 && (size_t)index < curr->targets.size()) {
           target = curr->targets[index];
         }
-        // This is obviously very inefficient. This should be a cached data structure
-        std::map<Name, size_t> caseMap; // name => index in cases
-        for (size_t i = 0; i < curr->cases.size(); i++) {
-          caseMap[curr->cases[i].name] = i;
-        }
-        auto iter = caseMap.find(target);
-        if (iter == caseMap.end()) {
-          // not in the cases, so this is a break
-          Flow flow(target);
-          flow.clearIf(curr->name);
-          return flow;
-        }
-        size_t caseIndex = iter->second;
-        assert(caseIndex < curr->cases.size());
-        while (caseIndex < curr->cases.size()) {
-          Switch::Case& c = curr->cases[caseIndex];
-          flow = visit(c.body);
-          if (flow.breaking()) {
-            flow.clearIf(curr->name);
-            break;
-          }
-          caseIndex++;
-        }
+        flow.breakTo = target;
         return flow;
       }
 
diff --git a/src/wasm-s-parser.h b/src/wasm-s-parser.h
index f3a28fd1a..1cd614c1d 100644
--- a/src/wasm-s-parser.h
+++ b/src/wasm-s-parser.h
@@ -558,7 +558,10 @@ public:
       switch (str[0]) {
         case 'b': {
           if (str[1] == 'l') return makeBlock(s);
-          if (str[1] == 'r') return makeBreak(s);
+          if (str[1] == 'r') {
+            if (str[2] == '_' && str[3] == 't') return makeBreakTable(s);
+            return makeBreak(s);
+          }
           abort_on(str);
         }
         case 'c': {
@@ -612,7 +615,6 @@ public:
           abort_on(str);
         }
         case 't': {
-          if (str[1] == 'a') return makeSwitch(s); // aka tableswitch
           if (str[1] == 'h') return makeThenOrElse(s);
           abort_on(str);
         }
@@ -948,43 +950,27 @@ private:
     return ret;
   }
 
-  Expression* makeReturn(Element& s) {
-    auto ret = allocator.alloc<Return>();
-    if (s.size() >= 2) {
-      ret->value = parseExpression(s[1]);
-    }
-    return ret;
-  }
-
-  Expression* makeSwitch(Element& s) {
+  Expression* makeBreakTable(Element& s) {
     auto ret = allocator.alloc<Switch>();
     size_t i = 1;
-    if (s[i]->isStr()) {
-      ret->name = s[i]->str();
-      i++;
-    } else {
-      ret->name = getPrefixedName("switch");
+    while (!s[i]->isList()) {
+      ret->targets.push_back(getLabel(*s[i++]));
     }
-    labelStack.push_back(ret->name);
-    ret->value =  parseExpression(s[i]);
-    i++;
-    Element& table = *s[i];
-    i++;
-    for (size_t j = 1; j < table.size(); j++) {
-      Element& curr = *table[j];
-      ret->targets.push_back(getLabel(*curr[1]));
+    ret->default_ = ret->targets.back();
+    ret->targets.pop_back();
+    ret->condition = parseExpression(s[i++]);
+    if (i < s.size()) {
+      ret->value = ret->condition;
+      ret->condition = parseExpression(s[i++]);
     }
-    Element& curr = *s[i];
-    ret->default_ = getLabel(*curr[1]);
-    i++;
-    for (; i < s.size(); i++) {
-      Element& curr = *s[i];
-      assert(curr[0]->str() == CASE);
-      if (curr.size() < 2) onError();
-      ret->cases.emplace_back(curr[1]->str(), makeMaybeBlock(curr, 2, curr.size()));
+    return ret;
+  }
+
+  Expression* makeReturn(Element& s) {
+    auto ret = allocator.alloc<Return>();
+    if (s.size() >= 2) {
+      ret->value = parseExpression(s[1]);
     }
-    ret->type = ret->cases.size() > 0 ? ret->cases[0].body->type : none;
-    labelStack.pop_back();
     return ret;
   }
 
diff --git a/src/wasm-validator.h b/src/wasm-validator.h
index 04493bb5b..2918c918d 100644
--- a/src/wasm-validator.h
+++ b/src/wasm-validator.h
@@ -76,16 +76,6 @@ public:
     validateAlignment(curr->align);
   }
   void visitSwitch(Switch *curr) {
-    std::set<Name> inTable;
-    for (auto target : curr->targets) {
-      if (target.is()) {
-        inTable.insert(target);
-      }
-    }
-    for (auto& c : curr->cases) {
-      shouldBeFalse(c.name.is() && inTable.find(c.name) == inTable.end());
-    }
-    shouldBeFalse(curr->default_.is() && inTable.find(curr->default_) == inTable.end());
   }
   void visitUnary(Unary *curr) {
     shouldBeTrue(curr->value->type == curr->type);
diff --git a/src/wasm.h b/src/wasm.h
index ba9d7de3d..6cbe93e3b 100644
--- a/src/wasm.h
+++ b/src/wasm.h
@@ -842,20 +842,14 @@ public:
 
 class Switch : public Expression {
 public:
-  Switch() : Expression(SwitchId) {}
-
-  struct Case {
-    Name name;
-    Expression *body;
-    Case() {}
-    Case(Name name, Expression *body) : name(name), body(body) {}
-  };
+  Switch() : Expression(SwitchId), condition(nullptr), value(nullptr) {
+    type = unreachable;
+  }
 
-  Name name;
-  Expression *value;
   std::vector<Name> targets;
   Name default_;
-  std::vector<Case> cases;
+  Expression *condition;
+  Expression *value;
 };
 
 class CallBase : public Expression {
@@ -1288,10 +1282,8 @@ struct ChildWalker : public WasmWalkerBase<ChildWalker<ParentType>> {
     parent.walk(curr->value);
   }
   void visitSwitch(Switch *curr) {
-    parent.walk(curr->value);
-    for (auto& case_ : curr->cases) {
-      parent.walk(case_.body);
-    }
+    parent.walk(curr->condition);
+    if (curr->value) parent.walk(curr->value);
   }
   void visitCall(Call *curr) {
     ExpressionList& list = curr->operands;
diff --git a/src/wasm2asm.h b/src/wasm2asm.h
index d8ac6376e..310ba4224 100644
--- a/src/wasm2asm.h
+++ b/src/wasm2asm.h
@@ -652,36 +652,24 @@ Ref Wasm2AsmBuilder::processFunctionBody(Expression* curr, IString result) {
     }
     Expression *defaultBody = nullptr; // default must be last in asm.js
     Ref visitSwitch(Switch *curr) {
-      Ref ret = ValueBuilder::makeLabel(fromName(curr->name), ValueBuilder::makeBlock());
-      Ref value;
-      if (isStatement(curr->value)) {
+      assert(!curr->value);
+      Ref ret = ValueBuilder::makeBlock();
+      Ref condition;
+      if (isStatement(curr->condition)) {
         ScopedTemp temp(i32, parent);
-        flattenAppend(ret[2], visit(curr->value, temp));
-        value = temp.getAstName();
+        flattenAppend(ret[2], visit(curr->condition, temp));
+        condition = temp.getAstName();
       } else {
-        value = visit(curr->value, EXPRESSION_RESULT);
+        condition = visit(curr->condition, EXPRESSION_RESULT);
       }
-      Ref theSwitch = ValueBuilder::makeSwitch(value);
+      Ref theSwitch = ValueBuilder::makeSwitch(condition);
       ret[2][1]->push_back(theSwitch);
-      for (auto& c : curr->cases) {
-        if (c.name == curr->default_) {
-          defaultBody = c.body;
-          continue;
-        }
-        bool added = false;
-        for (size_t i = 0; i < curr->targets.size(); i++) {
-          if (curr->targets[i] == c.name) {
-            ValueBuilder::appendCaseToSwitch(theSwitch, ValueBuilder::makeNum(i));
-            added = true;
-          }
-        }
-        assert(added);
-        ValueBuilder::appendCodeToSwitch(theSwitch, blockify(visit(c.body, NO_RESULT)), false);
-      }
-      if (defaultBody) {
-        ValueBuilder::appendDefaultToSwitch(theSwitch);
-        ValueBuilder::appendCodeToSwitch(theSwitch, blockify(visit(defaultBody, NO_RESULT)), false);
+      for (size_t i = 0; i < curr->targets.size(); i++) {
+        ValueBuilder::appendCaseToSwitch(theSwitch, ValueBuilder::makeNum(i));
+        ValueBuilder::appendCodeToSwitch(theSwitch, blockify(ValueBuilder::makeBreak(fromName(curr->targets[i]))), false);
       }
+      ValueBuilder::appendDefaultToSwitch(theSwitch);
+      ValueBuilder::appendCodeToSwitch(theSwitch, blockify(ValueBuilder::makeBreak(fromName(curr->default_))), false);
       return ret;
     }