Merge pull request #1019 from WebAssembly/fuzz

More fuzz bug fixes

5 files changed, 130 insertions, 37 deletions

diff --git a/src/cfg/Relooper.cpp b/src/cfg/Relooper.cpp
index 9fcc9c8be..b326d761d 100644
--- a/src/cfg/Relooper.cpp
+++ b/src/cfg/Relooper.cpp
@@ -328,7 +328,12 @@ wasm::Expression* Block::Render(RelooperBuilder& Builder, bool InLoop) {
         NextOuter->list.push_back(Outer);
         Outer->name = CurrName; // breaking on Outer leads to the content in NextOuter
         NextOuter->list.push_back(CurrContent);
-        NextOuter->list.push_back(Builder.makeBreak(SwitchLeave));
+        // if this is not a dead end, also need to break to the outside
+        // this is both an optimization, and avoids incorrectness as adding
+        // a brak in unreachable code can make a place look reachable that isn't
+        if (CurrContent->type != wasm::unreachable) {
+          NextOuter->list.push_back(Builder.makeBreak(SwitchLeave));
+        }
         // prepare for more nesting
         Outer = NextOuter;
       } else {
diff --git a/src/passes/ReReloop.cpp b/src/passes/ReReloop.cpp
index 6bdc0eb06..db2ec5698 100644
--- a/src/passes/ReReloop.cpp
+++ b/src/passes/ReReloop.cpp
@@ -28,6 +28,7 @@
 #include "wasm-traversal.h"
 #include "pass.h"
 #include "cfg/Relooper.h"
+#include "ast_utils.h"
 
 namespace wasm {
 
@@ -314,6 +315,8 @@ struct ReReloop : public Pass {
       CFG::RelooperBuilder builder(*module, temp);
       function->body = relooper.Render(builder);
     }
+    // TODO: should this be in the relooper itself?
+    ReFinalize().walk(function->body);
   }
 };
 
diff --git a/src/passes/Vacuum.cpp b/src/passes/Vacuum.cpp
index 1f820ec9d..4e47ad9a3 100644
--- a/src/passes/Vacuum.cpp
+++ b/src/passes/Vacuum.cpp
@@ -23,6 +23,7 @@
 #include <ast_utils.h>
 #include <wasm-builder.h>
 #include <ast/block-utils.h>
+#include <ast/type-updating.h>
 
 namespace wasm {
 
@@ -31,7 +32,20 @@ struct Vacuum : public WalkerPass<PostWalker<Vacuum>> {
 
   Pass* create() override { return new Vacuum; }
 
-  bool needRefinalize = false;
+  TypeUpdater typeUpdater;
+
+  Expression* replaceCurrent(Expression* expression) {
+    auto* old = getCurrent();
+    WalkerPass<PostWalker<Vacuum>>::replaceCurrent(expression);
+    // also update the type updater
+    typeUpdater.noteReplacement(old, expression);
+    return expression;
+  }
+
+  void doWalkFunction(Function* func) {
+    typeUpdater.walk(func->body);
+    walk(func->body);
+  }
 
   // returns nullptr if curr is dead, curr if it must stay as is, or another node if it can be replaced
   Expression* optimize(Expression* curr, bool resultUsed) {
@@ -143,40 +157,39 @@ struct Vacuum : public WalkerPass<PostWalker<Vacuum>> {
     int skip = 0;
     auto& list = curr->list;
     size_t size = list.size();
-    bool needResize = false;
     for (size_t z = 0; z < size; z++) {
-      auto* optimized = optimize(list[z], z == size - 1 && isConcreteWasmType(curr->type));
+      auto* child = list[z];
+      auto* optimized = optimize(child, z == size - 1 && isConcreteWasmType(curr->type));
       if (!optimized) {
+        typeUpdater.noteRecursiveRemoval(child);
         skip++;
-        needResize = true;
       } else {
-        if (optimized != list[z]) {
+        if (optimized != child) {
+          typeUpdater.noteReplacement(child, optimized);
           list[z] = optimized;
         }
         if (skip > 0) {
           list[z - skip] = list[z];
+          list[z] = nullptr;
         }
-        // if this is an unconditional br, the rest is dead code
-        Break* br = list[z - skip]->dynCast<Break>();
-        Switch* sw = list[z - skip]->dynCast<Switch>();
-        if ((br && !br->condition) || sw) {
-          auto* last = list.back();
-          list.resize(z - skip + 1);
-          // if we removed the last one, and it was a return value, it must be returned
-          if (list.back() != last && isConcreteWasmType(last->type)) {
-            list.push_back(last);
+        // if this is unreachable, the rest is dead code
+        if (list[z - skip]->type == unreachable && z < size - 1) {
+          for (Index i = z - skip + 1; i < list.size(); i++) {
+            auto* remove = list[i];
+            if (remove) {
+              typeUpdater.noteRecursiveRemoval(remove);
+            }
           }
-          needResize = false;
-          needRefinalize = true;
+          list.resize(z - skip + 1);
+          typeUpdater.maybeUpdateTypeToUnreachable(curr);
+          skip = 0; // nothing more to do on the list
           break;
         }
       }
     }
-    if (needResize) {
+    if (skip > 0) {
       list.resize(size - skip);
-      // resizing means we drop elements, which may include breaks, which may
-      // render blocks unreachable now
-      needRefinalize = true;
+      typeUpdater.maybeUpdateTypeToUnreachable(curr);
     }
     // the block may now be a trivial one that we can get rid of and just leave its contents
     replaceCurrent(BlockUtils::simplifyToContents(curr, this));
@@ -198,13 +211,6 @@ struct Vacuum : public WalkerPass<PostWalker<Vacuum>> {
         }
       }
       replaceCurrent(child);
-      if (curr->type != child->type) {
-        // e.g., if (1) unreachable is none => unreachable
-        // or if i32 (1) unreachable else 10 is i32 => unreachable
-        // in which cases we must update our parents.
-        // we must do this now, so that our parents see valid data
-        ReFinalize().walk(getFunction()->body);
-      }
       return;
     }
     if (curr->ifFalse) {
@@ -307,9 +313,6 @@ struct Vacuum : public WalkerPass<PostWalker<Vacuum>> {
   }
 
   void visitFunction(Function* curr) {
-    if (needRefinalize) {
-      ReFinalize().walk(curr->body);
-    }
     auto* optimized = optimize(curr->body, curr->result != none);
     if (optimized) {
       curr->body = optimized;
diff --git a/src/tools/wasm-opt.cpp b/src/tools/wasm-opt.cpp
index bf79cb31d..468f3ce93 100644
--- a/src/tools/wasm-opt.cpp
+++ b/src/tools/wasm-opt.cpp
@@ -28,9 +28,64 @@
 #include "wasm-s-parser.h"
 #include "wasm-validator.h"
 #include "wasm-io.h"
+#include "wasm-interpreter.h"
+#include "shell-interface.h"
 
 using namespace wasm;
 
+// gets execution results from a wasm module. this is useful for fuzzing
+//
+// we can only get results when there are no imports. we then call each method
+// that has a result, with some values
+struct ExecutionResults {
+  std::map<Name, Literal> results;
+
+  void get(Module& wasm) {
+    if (wasm.imports.size() > 0) {
+      std::cout << "[fuzz-exec] imports, so quitting\n";
+      return;
+    }
+    for (auto& func : wasm.functions) {
+      if (func->result != none) {
+        // this is good
+        results[func->name] = run(func.get(), wasm);
+      }
+    }
+    std::cout << "[fuzz-exec] " << results.size() << " results noted\n";
+  }
+
+  bool operator==(ExecutionResults& other) {
+    for (auto& iter : results) {
+      auto name = iter.first;
+      if (other.results.find(name) != other.results.end()) {
+        if (results[name] != other.results[name]) {
+          return false;
+        }
+      }
+    }
+    return true;
+  }
+
+  bool operator!=(ExecutionResults& other) {
+    return !((*this) == other);
+  }
+
+  Literal run(Function* func, Module& wasm) {
+    ShellExternalInterface interface;
+    ModuleInstance instance(wasm, &interface);
+    LiteralList arguments;
+    for (WasmType param : func->params) {
+      // zeros in arguments TODO: more?
+      arguments.push_back(Literal(param));
+    }
+    try {
+      return instance.callFunctionInternal(func->name, arguments);
+    } catch (const TrapException&) {
+      return Literal();
+    }
+  }
+};
+
 //
 // main
 //
@@ -42,6 +97,7 @@ int main(int argc, const char* argv[]) {
   PassOptions passOptions;
   bool emitBinary = true;
   bool debugInfo = false;
+  bool fuzzExec = false;
 
   Options options("wasm-opt", "Optimize .wast files");
   options
@@ -58,6 +114,9 @@ int main(int argc, const char* argv[]) {
       .add("--debuginfo", "-g", "Emit names section and debug info",
            Options::Arguments::Zero,
            [&](Options *o, const std::string &arguments) { debugInfo = true; })
+      .add("--fuzz-exec", "-fe", "Execute functions before and after optimization, helping fuzzing find bugs",
+           Options::Arguments::Zero,
+           [&](Options *o, const std::string &arguments) { fuzzExec = true; })
       .add_positional("INFILE", Options::Arguments::One,
                       [](Options* o, const std::string& argument) {
                         o->extra["infile"] = argument;
@@ -99,6 +158,11 @@ int main(int argc, const char* argv[]) {
     Fatal() << "error in validating input";
   }
 
+  ExecutionResults results;
+  if (fuzzExec) {
+    results.get(wasm);
+  }
+
   if (passes.size() > 0) {
     if (options.debug) std::cerr << "running passes...\n";
     PassRunner passRunner(&wasm, passOptions);
@@ -114,6 +178,15 @@ int main(int argc, const char* argv[]) {
     assert(WasmValidator().validate(wasm));
   }
 
+  if (fuzzExec) {
+    ExecutionResults optimizedResults;
+    optimizedResults.get(wasm);
+    if (optimizedResults != results) {
+      Fatal() << "[fuzz-exec] optimization passes changed execution results";
+    }
+    std::cout << "[fuzz-exec] results match\n";
+  }
+
   if (options.extra.count("output") > 0) {
     if (options.debug) std::cerr << "writing..." << std::endl;
     ModuleWriter writer;
diff --git a/src/wasm-validator.h b/src/wasm-validator.h
index 699e5910a..aa404099e 100644
--- a/src/wasm-validator.h
+++ b/src/wasm-validator.h
@@ -408,17 +408,26 @@ public:
     switch (curr->op) {
       case ClzInt32:
       case CtzInt32:
-      case PopcntInt32:
+      case PopcntInt32: {
+        shouldBeEqual(curr->value->type, i32, curr, "i32 unary value type must be correct");
+        break;
+      }
+      case ClzInt64:
+      case CtzInt64:
+      case PopcntInt64: {
+        shouldBeEqual(curr->value->type, i64, curr, "i64 unary value type must be correct");
+        break;
+      }
       case NegFloat32:
       case AbsFloat32:
       case CeilFloat32:
       case FloorFloat32:
       case TruncFloat32:
       case NearestFloat32:
-      case SqrtFloat32:
-      case ClzInt64:
-      case CtzInt64:
-      case PopcntInt64:
+      case SqrtFloat32: {
+        shouldBeEqual(curr->value->type, f32, curr, "f32 unary value type must be correct");
+        break;
+      }
       case NegFloat64:
       case AbsFloat64:
       case CeilFloat64:
@@ -426,7 +435,7 @@ public:
       case TruncFloat64:
       case NearestFloat64:
       case SqrtFloat64: {
-        shouldBeEqual(curr->value->type, curr->type, curr, "non-conversion unaries must return the same type");
+        shouldBeEqual(curr->value->type, f64, curr, "f64 unary value type must be correct");
         break;
       }
       case EqZInt32: {