Fix emitting of unreachable block/if/loop (#911)

* an unreachable block is one with an unreachable child, plus no breaks

* document new difference between binaryen IR and wasm

* fix relooper missing finalize

* add a bunch of tests

* don't assume that test/*.wast files print to themselves exactly; print to from.wast. this allows wast tests with comments in them

* emit unreachable blocks as (block .. unreachable) unreachable

* if without else and unreachable ifTrue is still not unreachable, it should be none

* update wasm.js

* cleanups

* empty blocks have none type

4 files changed, 69 insertions, 10 deletions

diff --git a/src/cfg/Relooper.cpp b/src/cfg/Relooper.cpp
index d412c7b31..f6250b888 100644
--- a/src/cfg/Relooper.cpp
+++ b/src/cfg/Relooper.cpp
@@ -90,6 +90,7 @@ static wasm::Expression* HandleFollowupMultiples(wasm::Expression* Ret, Shape* P
       }
     }
   }
+  Curr->finalize();
   return Curr;
 }
 
diff --git a/src/wasm-validator.h b/src/wasm-validator.h
index 28e575ca4..dacba39c3 100644
--- a/src/wasm-validator.h
+++ b/src/wasm-validator.h
@@ -128,7 +128,9 @@ public:
       }
     }
     if (!isConcreteWasmType(curr->type) && curr->list.size() > 0) {
-      shouldBeFalse(isConcreteWasmType(curr->list.back()->type), curr, "block with no value cannot have a last element with a value");
+      if (isConcreteWasmType(curr->list.back()->type)) {
+        shouldBeTrue(curr->type == unreachable, curr, "block with no value and a last element with a value must be unreachable");
+      }
     }
   }
 
@@ -155,6 +157,9 @@ public:
     shouldBeTrue(curr->condition->type == unreachable || curr->condition->type == i32 || curr->condition->type == i64, curr, "if condition must be valid");
     if (!curr->ifFalse) {
       shouldBeFalse(isConcreteWasmType(curr->ifTrue->type), curr, "if without else must not return a value in body");
+      if (curr->condition->type != unreachable) {
+        shouldBeEqual(curr->type, none, curr, "if without else and reachable condition must be none");
+      }
     }
   }
 
diff --git a/src/wasm/wasm-binary.cpp b/src/wasm/wasm-binary.cpp
index 6b5878904..456e4505e 100644
--- a/src/wasm/wasm-binary.cpp
+++ b/src/wasm/wasm-binary.cpp
@@ -461,24 +461,39 @@ void WasmBinaryWriter::recurse(Expression*& curr) {
   if (debug) std::cerr << "zz recurse from " << depth-- << " at " << o.size() << std::endl;
 }
 
+static bool brokenTo(Block* block) {
+  return block->name.is() && BreakSeeker::has(block, block->name);
+}
+
 void WasmBinaryWriter::visitBlock(Block *curr) {
   if (debug) std::cerr << "zz node: Block" << std::endl;
   o << int8_t(BinaryConsts::Block);
   o << binaryWasmType(curr->type != unreachable ? curr->type : none);
   breakStack.push_back(curr->name);
-  size_t i = 0;
+  Index i = 0;
   for (auto* child : curr->list) {
     if (debug) std::cerr << "  " << size_t(curr) << "\n zz Block element " << i++ << std::endl;
     recurse(child);
   }
   breakStack.pop_back();
+  if (curr->type == unreachable) {
+    // an unreachable block is one that cannot be exited. We cannot encode this directly
+    // in wasm, where blocks must be none,i32,i64,f32,f64. Since the block cannot be
+    // exited, we can emit an unreachable at the end, and that will always be valid,
+    // and then the block is ok as a none
+    o << int8_t(BinaryConsts::Unreachable);
+  }
   o << int8_t(BinaryConsts::End);
+  if (curr->type == unreachable) {
+    // and emit an unreachable *outside* the block too, so later things can pop anything
+    o << int8_t(BinaryConsts::Unreachable);
+  }
 }
 
 // emits a node, but if it is a block with no name, emit a list of its contents
 void WasmBinaryWriter::recursePossibleBlockContents(Expression* curr) {
   auto* block = curr->dynCast<Block>();
-  if (!block || (block->name.is() && BreakSeeker::has(curr, block->name))) {
+  if (!block || brokenTo(block)) {
     recurse(curr);
     return;
   }
@@ -489,6 +504,18 @@ void WasmBinaryWriter::recursePossibleBlockContents(Expression* curr) {
 
 void WasmBinaryWriter::visitIf(If *curr) {
   if (debug) std::cerr << "zz node: If" << std::endl;
+  if (curr->type == unreachable && curr->ifFalse) {
+    if (curr->condition->type == unreachable) {
+      // this if-else is unreachable because of the condition, i.e., the condition
+      // does not exit. So don't emit the if, but do consume the condition
+      recurse(curr->condition);
+      o << int8_t(BinaryConsts::Unreachable);
+      return;
+    }
+    // an unreachable if-else (with reachable condition) is one where both sides do not fall through.
+    // wasm does not allow this to be emitted directly, so we must do something more. we could do
+    // better, but for now we emit an extra unreachable instruction after the if, so it is not consumed itself
+  }
   recurse(curr->condition);
   o << int8_t(BinaryConsts::If);
   o << binaryWasmType(curr->type != unreachable ? curr->type : none);
@@ -502,6 +529,11 @@ void WasmBinaryWriter::visitIf(If *curr) {
     breakStack.pop_back();
   }
   o << int8_t(BinaryConsts::End);
+  if (curr->type == unreachable) {
+    // see explanation above - we emitted an if without a return type, so it must not be consumed
+    assert(curr->ifFalse); // otherwise, if without else, that is unreachable, must have an unreachable condition, which was handled earlier
+    o << int8_t(BinaryConsts::Unreachable);
+  }
 }
 void WasmBinaryWriter::visitLoop(Loop *curr) {
   if (debug) std::cerr << "zz node: Loop" << std::endl;
@@ -511,6 +543,10 @@ void WasmBinaryWriter::visitLoop(Loop *curr) {
   recursePossibleBlockContents(curr->body);
   breakStack.pop_back();
   o << int8_t(BinaryConsts::End);
+  if (curr->type == unreachable) {
+    // we emitted a loop without a return type, so it must not be consumed
+    o << int8_t(BinaryConsts::Unreachable);
+  }
 }
 
 int32_t WasmBinaryWriter::getBreakIndex(Name name) { // -1 if not found
diff --git a/src/wasm/wasm.cpp b/src/wasm/wasm.cpp
index cf58949de..c80d10c83 100644
--- a/src/wasm/wasm.cpp
+++ b/src/wasm/wasm.cpp
@@ -133,14 +133,30 @@ static WasmType mergeTypes(std::vector<WasmType>& types) {
   return type;
 }
 
+// a block is unreachable if one of its elements is unreachable,
+// and there are no branches to it
+static void handleUnreachable(Block* block) {
+  if (block->type == unreachable) return; // nothing to do
+  for (auto* child : block->list) {
+    if (child->type == unreachable) {
+      // there is an unreachable child, so we are unreachable, unless we have a break
+      BreakSeeker seeker(block->name);
+      Expression* expr = block;
+      seeker.walk(expr);
+      if (!seeker.found) {
+        block->type = unreachable;
+      } else {
+        block->type = seeker.valueType;
+      }
+      return;
+    }
+  }
+}
+
 void Block::finalize(WasmType type_) {
   type = type_;
   if (type == none && list.size() > 0) {
-    if (list.back()->type == unreachable) {
-      if (!BreakSeeker::has(this, name)) {
-        type = unreachable; // the last element is unreachable, and this block truly cannot be exited, so it is unreachable itself
-      }
-    }
+    handleUnreachable(this);
   }
 }
 
@@ -150,18 +166,19 @@ void Block::finalize() {
     if (list.size() > 0) {
       type = list.back()->type;
     } else {
-      type = unreachable;
+      type = none;
     }
     return;
   }
 
   TypeSeeker seeker(this, this->name);
   type = mergeTypes(seeker.types);
+  handleUnreachable(this);
 }
 
 void If::finalize(WasmType type_) {
   type = type_;
-  if (type == none && (condition->type == unreachable || (ifTrue->type == unreachable && (!ifFalse || ifFalse->type == unreachable)))) {
+  if (type == none && (condition->type == unreachable || (ifFalse && ifTrue->type && ifFalse->type == unreachable))) {
     type = unreachable;
   }
 }