Merge pull request #1123 from WebAssembly/fuzz-2

Yet more fuzz fixes

17 files changed, 407 insertions, 66 deletions

diff --git a/src/passes/MergeBlocks.cpp b/src/passes/MergeBlocks.cpp
index 7c086a920..619d7b5a5 100644
--- a/src/passes/MergeBlocks.cpp
+++ b/src/passes/MergeBlocks.cpp
@@ -154,6 +154,15 @@ struct BreakValueDropper : public ControlFlowWalker<BreakValueDropper> {
   }
 };
 
+static bool hasUnreachableChild(Block* block) {
+  for (auto* test : block->list) {
+    if (test->type == unreachable) {
+      return true;
+    }
+  }
+  return false;
+}
+
 // core block optimizer routine
 static void optimizeBlock(Block* curr, Module* module, PassOptions& passOptions) {
   bool more = true;
@@ -168,6 +177,11 @@ static void optimizeBlock(Block* curr, Module* module, PassOptions& passOptions)
         if (drop) {
           child = drop->value->dynCast<Block>();
           if (child) {
+            if (hasUnreachableChild(child)) {
+              // don't move around unreachable code, as it can change types
+              // dce should have been run anyhow
+              continue;
+            }
             if (child->name.is()) {
               Expression* expression = child;
               // check if it's ok to remove the value from all breaks to us
@@ -200,15 +214,6 @@ static void optimizeBlock(Block* curr, Module* module, PassOptions& passOptions)
       }
       if (!child) continue;
       if (child->name.is()) continue; // named blocks can have breaks to them (and certainly do, if we ran RemoveUnusedNames and RemoveUnusedBrs)
-      if (child->type == unreachable) {
-        // an unreachable block can have a concrete final element (which is never reached)
-        if (!child->list.empty()) {
-          if (isConcreteWasmType(child->list.back()->type)) {
-            // just remove it
-            child->list.pop_back();
-          }
-        }
-      }
       ExpressionList merged(module->allocator);
       for (size_t j = 0; j < i; j++) {
         merged.push_back(curr->list[j]);
@@ -219,6 +224,16 @@ static void optimizeBlock(Block* curr, Module* module, PassOptions& passOptions)
       for (size_t j = i + 1; j < curr->list.size(); j++) {
         merged.push_back(curr->list[j]);
       }
+      // if we merged a concrete element in the middle, drop it
+      if (!merged.empty()) {
+        auto* last = merged.back();
+        for (auto*& item : merged) {
+          if (item != last && isConcreteWasmType(item->type)) {
+            Builder builder(*module);
+            item = builder.makeDrop(item);
+          }
+        }
+      }
       curr->list.swap(merged);
       more = true;
       changed = true;
@@ -241,6 +256,23 @@ struct MergeBlocks : public WalkerPass<PostWalker<MergeBlocks>> {
     optimizeBlock(curr, getModule(), getPassOptions());
   }
 
+  // given
+  // (curr
+  //  (block=child
+  //   (..more..)
+  //   (back)
+  //  )
+  //  (..other..children..)
+  // )
+  // if child is a block, we can move this around to
+  // (block
+  //  (..more..)
+  //  (curr
+  //   (back)
+  //   (..other..children..)
+  //  )
+  // )
+  // at which point the block is on the outside and potentially mergeable with an outer block
   Block* optimize(Expression* curr, Expression*& child, Block* outer = nullptr, Expression** dependency1 = nullptr, Expression** dependency2 = nullptr) {
     if (!child) return outer;
     if ((dependency1 && *dependency1) || (dependency2 && *dependency2)) {
@@ -251,18 +283,29 @@ struct MergeBlocks : public WalkerPass<PostWalker<MergeBlocks>> {
     }
     if (auto* block = child->dynCast<Block>()) {
       if (!block->name.is() && block->list.size() >= 2) {
-        child = block->list.back();
-        // we modified child (which is a reference to a pointer), which modifies curr, which might change its type
-        // (e.g. (drop (block (result i32) .. (unreachable)))
-        // the child was a block of i32, and is being replaced with an unreachable, so the
-        // parent will likely need to be unreachable too
-        auto oldType = curr->type;
-        ReFinalize().walk(curr);
+        // if we move around unreachable code, type changes could occur. avoid that, as
+        // anyhow it means we should have run dce before getting here
+        if (curr->type == none && hasUnreachableChild(block)) {
+          // moving the block to the outside would replace a none with an unreachable
+          return outer;
+        }
+        auto* back = block->list.back();
+        if (back->type == unreachable) {
+          // curr is not reachable, dce could remove it; don't try anything fancy
+          // here
+          return outer;
+        }
+        // we are going to replace the block with the final element, so they should
+        // be identically typed
+        if (block->type != back->type) {
+          return outer;
+        }
+        child = back;
         if (outer == nullptr) {
           // reuse the block, move it out
           block->list.back() = curr;
           // we want the block outside to have the same type as curr had
-          block->finalize(oldType);
+          block->finalize(curr->type);
           replaceCurrent(block);
           return block;
         } else {
diff --git a/src/passes/RemoveUnusedBrs.cpp b/src/passes/RemoveUnusedBrs.cpp
index 9fed3e4a5..8994c7fe2 100644
--- a/src/passes/RemoveUnusedBrs.cpp
+++ b/src/passes/RemoveUnusedBrs.cpp
@@ -481,7 +481,9 @@ struct RemoveUnusedBrs : public WalkerPass<PostWalker<RemoveUnusedBrs>> {
           // format. We need to flip the condition, which at worst adds 1.
           if (curr->name.is()) {
             auto* br = list[0]->dynCast<Break>();
-            if (br && br->condition && br->name == curr->name) {
+            // we seek a regular br_if; if the type is unreachable that means it is not
+            // actually taken, so ignore
+            if (br && br->condition && br->name == curr->name && br->type != unreachable) {
               assert(!br->value); // can't, it would be dropped or last in the block
               if (BranchUtils::BranchSeeker::countNamed(curr, curr->name) == 1) {
                 // no other breaks to that name, so we can do this
diff --git a/src/passes/RemoveUnusedNames.cpp b/src/passes/RemoveUnusedNames.cpp
index 39bf068df..e5aaf5509 100644
--- a/src/passes/RemoveUnusedNames.cpp
+++ b/src/passes/RemoveUnusedNames.cpp
@@ -57,7 +57,7 @@ struct RemoveUnusedNames : public WalkerPass<PostWalker<RemoveUnusedNames>> {
   void visitBlock(Block *curr) {
     if (curr->name.is() && curr->list.size() == 1) {
       auto* child = curr->list[0]->dynCast<Block>();
-      if (child && child->name.is()) {
+      if (child && child->name.is() && child->type == curr->type) {
         // we have just one child, this block, so breaking out of it goes to the same place as breaking out of us, we just need one name (and block)
         auto& branches = branchesSeen[curr->name];
         for (auto* branch : branches) {
diff --git a/src/wasm-binary.h b/src/wasm-binary.h
index ca3d69989..9c468b0ea 100644
--- a/src/wasm-binary.h
+++ b/src/wasm-binary.h
@@ -861,6 +861,7 @@ public:
   int depth = 0; // only for debugging
 
   BinaryConsts::ASTNodes readExpression(Expression*& curr);
+  void pushBlockElements(Block* curr, size_t start, size_t end);
   void visitBlock(Block *curr);
   Expression* getMaybeBlock(WasmType type);
   Expression* getBlock(WasmType type);
diff --git a/src/wasm/wasm-binary.cpp b/src/wasm/wasm-binary.cpp
index 47bcc8ba5..63dddbdd6 100644
--- a/src/wasm/wasm-binary.cpp
+++ b/src/wasm/wasm-binary.cpp
@@ -583,6 +583,11 @@ void WasmBinaryWriter::recursePossibleBlockContents(Expression* curr) {
   for (auto* child : block->list) {
     recurse(child);
   }
+  if (block->type == unreachable && block->list.back()->type != unreachable) {
+    // similar to in visitBlock, here we could skip emitting the block itself,
+    // but must still end the 'block' (the contents, really) with an unreachable
+    o << int8_t(BinaryConsts::Unreachable);
+  }
 }
 
 void WasmBinaryWriter::visitIf(If *curr) {
@@ -2073,6 +2078,20 @@ BinaryConsts::ASTNodes WasmBinaryBuilder::readExpression(Expression*& curr) {
   return BinaryConsts::ASTNodes(code);
 }
 
+void WasmBinaryBuilder::pushBlockElements(Block* curr, size_t start, size_t end) {
+  for (size_t i = start; i < end; i++) {
+    auto* item = expressionStack[i];
+    curr->list.push_back(item);
+    if (i < end - 1) {
+      // stacky&unreachable code may introduce elements that need to be dropped in non-final positions
+      if (isConcreteWasmType(item->type)) {
+        curr->list.back() = Builder(wasm).makeDrop(curr->list.back());
+      }
+    }
+  }
+  expressionStack.resize(start);
+}
+
 void WasmBinaryBuilder::visitBlock(Block *curr) {
   if (debug) std::cerr << "zz node: Block" << std::endl;
   // special-case Block and de-recurse nested blocks in their first position, as that is
@@ -2108,18 +2127,7 @@ void WasmBinaryBuilder::visitBlock(Block *curr) {
     if (end < start) {
       throw ParseException("block cannot pop from outside");
     }
-    for (size_t i = start; i < end; i++) {
-      if (debug) std::cerr << "  " << size_t(expressionStack[i]) << "\n zz Block element " << curr->list.size() << std::endl;
-      auto* item = expressionStack[i];
-      curr->list.push_back(item);
-      if (i < end - 1) {
-        // stacky&unreachable code may introduce elements that need to be dropped in non-final positions
-        if (isConcreteWasmType(item->type)) {
-          curr->list.back() = Builder(wasm).makeDrop(curr->list.back());
-        }
-      }
-    }
-    expressionStack.resize(start);
+    pushBlockElements(curr, start, end);
     curr->finalize(curr->type);
     breakStack.pop_back();
   }
@@ -2136,11 +2144,8 @@ Expression* WasmBinaryBuilder::getMaybeBlock(WasmType type) {
     throw ParseException("block cannot pop from outside");
   }
   auto* block = allocator.alloc<Block>();
-  for (size_t i = start; i < end; i++) {
-    block->list.push_back(expressionStack[i]);
-  }
+  pushBlockElements(block, start, end);
   block->finalize(type);
-  expressionStack.resize(start);
   return block;
 }
 
diff --git a/test/passes/merge-blocks.txt b/test/passes/merge-blocks.txt
index b972a6421..f9ca7c3c1 100644
--- a/test/passes/merge-blocks.txt
+++ b/test/passes/merge-blocks.txt
@@ -14,12 +14,11 @@
  )
  (func $drop-block-br (type $0)
   (block $block
-   (block $x
-    (drop
-     (i32.const 1)
-    )
-    (br $x)
-    (drop
+   (drop
+    (block $x (result i32)
+     (br $x
+      (i32.const 1)
+     )
      (i32.const 0)
     )
    )
@@ -95,8 +94,8 @@
  (func $drop-block-squared-iloop (type $0)
   (drop
    (block $label$0 (result i32)
-    (block $label$1
-     (drop
+    (drop
+     (block $label$1
       (loop $label$2
        (br $label$2)
       )
@@ -124,4 +123,15 @@
    )
   )
  )
+ (func $loop-block-drop-block-return (type $0)
+  (loop $label$4
+   (block $label$5
+    (drop
+     (block $label$6 (result i32)
+      (return)
+     )
+    )
+   )
+  )
+ )
 )
diff --git a/test/passes/merge-blocks.wast b/test/passes/merge-blocks.wast
index 81b70d1b5..d73612735 100644
--- a/test/passes/merge-blocks.wast
+++ b/test/passes/merge-blocks.wast
@@ -101,5 +101,16 @@
     )
    )
   )
+  (func $loop-block-drop-block-return
+   (loop $label$4
+    (block $label$5
+     (drop
+      (block $label$6 (result i32)
+       (return)
+      )
+     )
+    )
+   )
+  )
 )
 
diff --git a/test/passes/remove-unused-brs.txt b/test/passes/remove-unused-brs.txt
index 355f8a531..fe0c59fca 100644
--- a/test/passes/remove-unused-brs.txt
+++ b/test/passes/remove-unused-brs.txt
@@ -1048,4 +1048,15 @@
    )
   )
  )
+ (func $untaken-br_if-then-if (type $1)
+  (block $label$0
+   (br_if $label$0
+    (unreachable)
+   )
+   (if
+    (i32.const 0)
+    (nop)
+   )
+  )
+ )
 )
diff --git a/test/passes/remove-unused-brs.wast b/test/passes/remove-unused-brs.wast
index e7c221fa4..996b05264 100644
--- a/test/passes/remove-unused-brs.wast
+++ b/test/passes/remove-unused-brs.wast
@@ -932,5 +932,16 @@
     )
    )
   )
+  (func $untaken-br_if-then-if
+   (block $label$0
+    (br_if $label$0
+     (unreachable)
+    )
+    (if
+     (i32.const 0)
+     (nop)
+    )
+   )
+  )
 )
 
diff --git a/test/passes/remove-unused-names.txt b/test/passes/remove-unused-names.txt
index 91b8b8981..894e07165 100644
--- a/test/passes/remove-unused-names.txt
+++ b/test/passes/remove-unused-names.txt
@@ -1,6 +1,7 @@
 (module
  (type $0 (func (param i32) (result i32)))
  (type $1 (func))
+ (type $2 (func (result i32)))
  (memory $0 256 256)
  (func $b0 (type $0) (param $i1 i32) (result i32)
   (i32.const 0)
@@ -63,4 +64,20 @@
    )
   )
  )
+ (func $merge-typed-with-unreachable-child (type $2) (result i32)
+  (local $0 f32)
+  (block $label$0 (result i32)
+   (block $label$1
+    (br_if $label$1
+     (i32.const 0)
+     (br_if $label$0
+      (i32.const 0)
+      (br $label$0
+       (i32.const 0)
+      )
+     )
+    )
+   )
+  )
+ )
 )
diff --git a/test/passes/remove-unused-names.wast b/test/passes/remove-unused-names.wast
index 0f8fe4dcc..dc882cf4c 100644
--- a/test/passes/remove-unused-names.wast
+++ b/test/passes/remove-unused-names.wast
@@ -77,4 +77,20 @@
       )
     )
   )
+  (func $merge-typed-with-unreachable-child (result i32)
+   (local $0 f32)
+   (block $label$0 (result i32)
+    (block $label$1
+     (br_if $label$1
+      (i32.const 0)
+      (br_if $label$0
+       (i32.const 0)
+       (br $label$0
+        (i32.const 0)
+       )
+      )
+     )
+    )
+   )
+  )
 )
diff --git a/test/passes/remove-unused-names_merge-blocks.txt b/test/passes/remove-unused-names_merge-blocks.txt
index 6bd9d348e..19f03c662 100644
--- a/test/passes/remove-unused-names_merge-blocks.txt
+++ b/test/passes/remove-unused-names_merge-blocks.txt
@@ -166,11 +166,13 @@
     (i32.const 20)
    )
   )
-  (drop
-   (i32.const 10)
-  )
   (return
-   (unreachable)
+   (block
+    (drop
+     (i32.const 10)
+    )
+    (unreachable)
+   )
   )
  )
  (func $binary (type $3)
@@ -297,14 +299,16 @@
     )
    )
   )
-  (unreachable)
-  (drop
-   (i32.const 20)
-  )
   (drop
-   (i32.add
-    (i32.const 10)
-    (i32.const 30)
+   (block (result i32)
+    (unreachable)
+    (drop
+     (i32.const 20)
+    )
+    (i32.add
+     (i32.const 10)
+     (i32.const 30)
+    )
    )
   )
  )
@@ -460,7 +464,7 @@
   (drop
    (select
     (i32.const 20)
-    (block
+    (block (result i32)
      (unreachable)
      (i32.const 40)
     )
@@ -478,7 +482,7 @@
   (drop
    (select
     (i32.const 20)
-    (block
+    (block (result i32)
      (drop
       (i32.const 30)
      )
@@ -502,7 +506,7 @@
    (select
     (i32.const 20)
     (i32.const 40)
-    (block
+    (block (result i32)
      (unreachable)
      (i32.const 60)
     )
@@ -518,7 +522,7 @@
    (select
     (i32.const 20)
     (i32.const 40)
-    (block
+    (block (result i32)
      (drop
       (i32.const 50)
      )
@@ -639,7 +643,7 @@
   )
   (call $call-ii
    (i32.const 20)
-   (block
+   (block (result i32)
     (unreachable)
     (i32.const 30)
    )
@@ -649,7 +653,7 @@
   )
   (call $call-ii
    (i32.const 20)
-   (block
+   (block (result i32)
     (drop
      (i32.const 30)
     )
@@ -826,12 +830,14 @@
  )
  (func $return-different-type (type $4) (result i32)
   (drop
-   (i32.const 2)
-  )
-  (drop
    (f64.abs
-    (return
-     (i32.const 1)
+    (block
+     (drop
+      (i32.const 2)
+     )
+     (return
+      (i32.const 1)
+     )
     )
    )
   )
@@ -840,12 +846,86 @@
  (func $drop-unreachable (type $4) (result i32)
   (local $0 i32)
   (drop
-   (unreachable)
+   (block (result i32)
+    (unreachable)
+   )
   )
   (unreachable)
  )
  (func $concrete_finale_in_unreachable (type $5) (result f64)
   (unreachable)
+  (drop
+   (f64.const 6.322092475576799e-96)
+  )
   (f64.const -1)
  )
+ (func $dont-move-unreachable (type $3)
+  (loop $label$0
+   (drop
+    (block (result i32)
+     (br $label$0)
+     (i32.const 1)
+    )
+   )
+  )
+ )
+ (func $dont-move-unreachable-last (type $3)
+  (loop $label$0
+   (drop
+    (block (result i32)
+     (call $dont-move-unreachable-last)
+     (br $label$0)
+    )
+   )
+  )
+ )
+ (func $move-around-unreachable-in-middle (type $3)
+  (loop $label$0
+   (nop)
+   (drop
+    (block $label$3 (result i32)
+     (drop
+      (br_if $label$3
+       (br $label$0)
+       (i32.const 0)
+      )
+     )
+     (i32.const 1)
+    )
+   )
+  )
+ )
+ (func $drop-unreachable-block-with-concrete-final (type $3)
+  (drop
+   (block
+    (drop
+     (block
+      (drop
+       (return)
+      )
+     )
+    )
+    (i32.const -452)
+   )
+  )
+ )
+ (func $merging-with-unreachable-in-middle (type $4) (result i32)
+  (return
+   (i32.const 21536)
+  )
+  (block $label$15
+   (br $label$15)
+  )
+  (i32.const 19299)
+ )
+ (func $remove-br-after-unreachable (type $3)
+  (block $label$9
+   (drop
+    (block
+     (return)
+     (br $label$9)
+    )
+   )
+  )
+ )
 )
diff --git a/test/passes/remove-unused-names_merge-blocks.wast b/test/passes/remove-unused-names_merge-blocks.wast
index c249a34dd..6f6dd92b9 100644
--- a/test/passes/remove-unused-names_merge-blocks.wast
+++ b/test/passes/remove-unused-names_merge-blocks.wast
@@ -1014,4 +1014,84 @@
    (f64.const -1)
   )
  )
+ (func $dont-move-unreachable
+  (loop $label$0
+   (drop
+    (block $label$3 (result i32)
+     (br $label$0)
+     (i32.const 1)
+    )
+   )
+  )
+ )
+ (func $dont-move-unreachable-last
+  (loop $label$0
+   (drop
+    (block $label$3 (result i32)
+     (call $dont-move-unreachable-last)
+     (br $label$0)
+    )
+   )
+  )
+ )
+ (func $move-around-unreachable-in-middle
+  (loop $label$0
+   (drop
+    (block $label$2 (result i32)
+     (block $block2
+      (nop)
+     )
+     (block $label$3 (result i32)
+      (drop
+       (br_if $label$3
+        (br $label$0)
+        (i32.const 0)
+       )
+      )
+      (i32.const 1)
+     )
+    )
+   )
+  )
+ )
+ (func $drop-unreachable-block-with-concrete-final
+  (drop
+   (block
+    (drop
+     (block
+      (drop
+       (return)
+      )
+     )
+    )
+    (i32.const -452)
+   )
+  )
+ )
+ (func $merging-with-unreachable-in-middle (result i32)
+  (block $label$1 (result i32)
+   (block
+    (return
+     (i32.const 21536)
+    )
+    (block $label$15
+     (br $label$15)
+    )
+    (i32.const 19299)
+   )
+  )
+ )
+ (func $remove-br-after-unreachable
+  (block $label$9
+   (drop
+    (block
+     (block
+      (return)
+      (br $label$9) ;; removing this leads to the block becoming unreachable
+     )
+    )
+   )
+  )
+ )
 )
+
diff --git a/test/unit.wast b/test/unit.wast
index c1a945264..a429675de 100644
--- a/test/unit.wast
+++ b/test/unit.wast
@@ -537,4 +537,16 @@
     (if (i32.const 1) (nop) (unreachable))
     (if (i32.const 1) (unreachable) (unreachable))
   )
+  (func $unreachable-if-arm
+    (if
+      (i32.const 1)
+      (block
+        (nop)
+      )
+      (block
+        (unreachable)
+        (i32.const 1) ;; ends in a concrete, after an unreachable
+      )
+    )
+  )
 )
diff --git a/test/unit.wast.from-wast b/test/unit.wast.from-wast
index bb66845af..7fb82d69d 100644
--- a/test/unit.wast.from-wast
+++ b/test/unit.wast.from-wast
@@ -602,4 +602,16 @@
    (unreachable)
   )
  )
+ (func $unreachable-if-arm (type $FUNCSIG$v)
+  (if
+   (i32.const 1)
+   (block $block
+    (nop)
+   )
+   (block $block12
+    (unreachable)
+    (i32.const 1)
+   )
+  )
+ )
 )
diff --git a/test/unit.wast.fromBinary b/test/unit.wast.fromBinary
index 78ae640b1..8bb80bcca 100644
--- a/test/unit.wast.fromBinary
+++ b/test/unit.wast.fromBinary
@@ -646,5 +646,20 @@
   )
   (unreachable)
  )
+ (func $unreachable-if-arm (type $1)
+  (if
+   (i32.const 1)
+   (block $label$0
+    (nop)
+   )
+   (block $label$1
+    (unreachable)
+    (drop
+     (i32.const 1)
+    )
+    (unreachable)
+   )
+  )
+ )
 )
 
diff --git a/test/unit.wast.fromBinary.noDebugInfo b/test/unit.wast.fromBinary.noDebugInfo
index 3c24886f5..09da9a15b 100644
--- a/test/unit.wast.fromBinary.noDebugInfo
+++ b/test/unit.wast.fromBinary.noDebugInfo
@@ -646,5 +646,20 @@
   )
   (unreachable)
  )
+ (func $36 (type $1)
+  (if
+   (i32.const 1)
+   (block $label$0
+    (nop)
+   )
+   (block $label$1
+    (unreachable)
+    (drop
+     (i32.const 1)
+    )
+    (unreachable)
+   )
+  )
+ )
 )