DCE bugfix (#736)

* fix a dce bug where it is invalid to truncate a block if it leaves a final element with a bad type (wasm doesn't always allow removing unreachable code)

* add wast pass fuzzer

6 files changed, 243 insertions, 2 deletions

diff --git a/scripts/fuzz_passes_wast.py b/scripts/fuzz_passes_wast.py
new file mode 100644
index 000000000..5ec032de1
--- /dev/null
+++ b/scripts/fuzz_passes_wast.py
@@ -0,0 +1,136 @@
+#! /usr/bin/env python
+
+#   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.
+
+'''
+This fuzzes passes, by starting with a wast, then running
+random passes on the wast, and seeing if they break optimization
+or validation
+
+Usage: Provide the filename of the wast.
+'''
+
+import os
+import random
+import shutil
+import subprocess
+import sys
+
+PASSES = [
+    "duplicate-function-elimination",
+    "dce",
+    "remove-unused-brs",
+    "remove-unused-names",
+    "optimize-instructions",
+    "precompute",
+    "simplify-locals",
+    "vacuum",
+    "coalesce-locals",
+    "reorder-locals",
+    "merge-blocks",
+    "remove-unused-functions",
+]
+
+# main
+
+wast = sys.argv[1]
+print '>>> wast:', wast
+
+args = sys.argv[2:]
+
+
+def run():
+  try:
+    print 'run', ['bin/wasm-opt', wast]
+    subprocess.check_call(['bin/wasm-opt', wast])
+  except Exception, e:
+    print ">>> !!! ", e, " !!!"
+  return 'ok'
+
+original_wast = None
+
+try:
+  # get normal output
+
+  normal = run()
+  print '>>> normal output:\n', normal
+  assert normal, 'must be output'
+
+  # ensure we actually use the wast
+
+  original_wast = wast + '.original.wast'
+  shutil.move(wast, original_wast)
+
+  def apply_passes(passes):
+    wasm_opt = os.path.join('bin', 'wasm-opt')
+    subprocess.check_call([wasm_opt, original_wast] + passes + ['-o', wast],
+                          stderr=open('/dev/null'))
+
+  # loop, looking for failures
+
+  def simplify(passes):
+    # passes is known to fail, try to simplify down by removing
+    more = True
+    while more:
+      more = False
+      print '>>> trying to reduce:', ' '.join(passes),
+      print '  [' + str(len(passes)) + ']'
+      for i in range(len(passes)):
+        smaller = passes[:i] + passes[i + 1:]
+        print '>>>>>> try to reduce to:', ' '.join(smaller),
+        print '  [' + str(len(smaller)) + ']'
+        try:
+          apply_passes(smaller)
+          assert run() == normal
+        except:
+          # this failed too, so it's a good reduction
+          passes = smaller
+          print '>>> reduction successful'
+          more = True
+          break
+    print '>>> reduced to:', ' '.join(passes)
+
+  tested = set()
+
+  def pick_passes():
+    ret = []
+    while 1:
+      str_ret = str(ret)
+      if random.random() < 0.5 and str_ret not in tested:
+        tested.add(str_ret)
+        return ret
+      ret.append('--' + random.choice(PASSES))
+
+  counter = 0
+
+  while 1:
+    passes = pick_passes()
+    print '>>> [' + str(counter) + '] testing:', ' '.join(passes)
+    counter += 1
+    try:
+      apply_passes(passes)
+    except Exception, e:
+      print e
+      simplify(passes)
+      break
+    seen = run()
+    if seen != normal:
+      print '>>> bad output:\n', seen
+      simplify(passes)
+      break
+
+finally:
+  if original_wast:
+    shutil.move(original_wast, wast)
diff --git a/src/passes/DeadCodeElimination.cpp b/src/passes/DeadCodeElimination.cpp
index b30b8ffbd..c2799f13a 100644
--- a/src/passes/DeadCodeElimination.cpp
+++ b/src/passes/DeadCodeElimination.cpp
@@ -110,12 +110,23 @@ struct DeadCodeElimination : public WalkerPass<PostWalker<DeadCodeElimination, V
     Index i = self->blockStack.back();
     self->blockStack.back()++;
     if (!self->reachable) {
-      // control flow ended in the middle of the block
+      // control flow ended in the middle of the block, so we can truncate the rest.
       // note that we still visit the rest, so if we already truncated, do not lengthen.
       // note that it is ok that we visit the others even though the list was shortened;
       // our arena vectors leave things as they are when shrinking.
       if (block->list.size() > i + 1) {
-        block->list.resize(i + 1);
+        // but note that it is not legal to truncate a block if it leaves a bad last element,
+        // given the wasm type rules. For example, if the last element is a return, then
+        // the block doesn't care about it for type checking purposes, but if removing
+        // it would leave an element with type none as the last, that could be a problem,
+        // see https://github.com/WebAssembly/spec/issues/355
+        if (!(isConcreteWasmType(block->type) && block->list[i]->type == none)) {
+          block->list.resize(i + 1);
+          // note that we do *not* finalize here. it is incorrect to re-finalize a block
+          // after removing elements, as it may no longer have branches to it that would
+          // determine its type, so re-finalizing would just wipe out an existing type
+          // that it had.
+        }
       }
     }
   }
diff --git a/test/passes/dce.txt b/test/passes/dce.txt
index 443417744..96bc6b3b2 100644
--- a/test/passes/dce.txt
+++ b/test/passes/dce.txt
@@ -2,6 +2,8 @@
   (memory $0 10)
   (type $ii (func (param i32 i32)))
   (type $1 (func))
+  (type $2 (func (result i32)))
+  (type $3 (func (param i32) (result i32)))
   (table 1 1 anyfunc)
   (elem (i32.const 0) $call-me)
   (func $call-me (type $ii) (param $0 i32) (param $1 i32)
@@ -296,4 +298,34 @@
       (i32.const 2000)
     )
   )
+  (func $typed-block-none-then-unreachable (type $2) (result i32)
+    (block $top-typed i32
+      (block $switch$0
+        (return
+          (i32.const 0)
+        )
+      )
+      (unreachable)
+    )
+  )
+  (func $typed-block-remove-br-changes-type (type $3) (param $$$0 i32) (result i32)
+    (block $switch$7
+      (block $switch-default$10
+        (block $switch-case$9
+          (block $switch-case$8
+            (br_table $switch-case$9 $switch-case$8 $switch-default$10
+              (i32.const -1)
+            )
+          )
+        )
+        (return
+          (get_local $$$0)
+        )
+      )
+      (return
+        (get_local $$$0)
+      )
+    )
+    (unreachable)
+  )
 )
diff --git a/test/passes/dce.wast b/test/passes/dce.wast
index af85945b4..fe8cb73f9 100644
--- a/test/passes/dce.wast
+++ b/test/passes/dce.wast
@@ -393,4 +393,40 @@
       (i32.const 2000)
     )
   )
+  (func $typed-block-none-then-unreachable (result i32)
+    (block $top-typed i32
+      (block $switch$0 ;; this looks like it can be broken to, so it gets type 'none'
+        (return
+          (i32.const 0)
+        )
+        (br $switch$0) ;; this is not reachable, so dce cleans it up, changing $switch$0's type
+      )
+      (return ;; and this is cleaned up as well, leaving $top-typed in need of a type change
+        (i32.const 1)
+      )
+    )
+  )
+  (func $typed-block-remove-br-changes-type (param $$$0 i32) (result i32)
+    (block $switch$7
+      (block $switch-default$10
+        (block $switch-case$9
+          (block $switch-case$8
+            (br_table $switch-case$9 $switch-case$8 $switch-default$10
+              (i32.const -1)
+            )
+          )
+        )
+        (return
+          (get_local $$$0)
+        )
+        (br $switch$7)
+      )
+      (return
+        (get_local $$$0)
+      )
+    )
+    (return
+      (i32.const 0)
+    )
+  )
 )
diff --git a/test/passes/dce_vacuum.txt b/test/passes/dce_vacuum.txt
new file mode 100644
index 000000000..876eb3c34
--- /dev/null
+++ b/test/passes/dce_vacuum.txt
@@ -0,0 +1,12 @@
+(module
+  (memory $0 0)
+  (type $0 (func (result i32)))
+  (func $__Z12serveroptionPc (type $0) (result i32)
+    (block $switch$0
+      (return
+        (i32.const 0)
+      )
+    )
+    (unreachable)
+  )
+)
diff --git a/test/passes/dce_vacuum.wast b/test/passes/dce_vacuum.wast
new file mode 100644
index 000000000..a7e43db23
--- /dev/null
+++ b/test/passes/dce_vacuum.wast
@@ -0,0 +1,14 @@
+(module
+  (func $__Z12serveroptionPc (result i32)
+    (block $switch$0
+      (return
+        (i32.const 0)
+      )
+      (br $switch$0)
+    )
+    (return
+      (i32.const 0)
+    )
+  )
+)
+