Validate finalization (#1014)

* validate that types are properly finalized, when in pass-debug mode (BINARYEN_PASS_DEBUG env var): check after each pass is run that the type of each node is equal to the proper type (when finalizing it, i.e., fully recomputing the type).

* fix many fuzz bugs found by that.

* in particular, fix dce bugs with type changes not being fully updated during code removal. add a new TypeUpdater helper class that lets a pass update types efficiently, by the helper tracking deps between blocks and branches etc., and updating/propagating type changes only as necessary.

1 files changed, 50 insertions, 7 deletions

diff --git a/src/wasm-validator.h b/src/wasm-validator.h
index b657b67a6..66375790c 100644
--- a/src/wasm-validator.h
+++ b/src/wasm-validator.h
@@ -42,6 +42,7 @@
 #include "support/colors.h"
 #include "wasm.h"
 #include "wasm-printing.h"
+#include "ast_utils.h"
 
 namespace wasm {
 
@@ -68,7 +69,7 @@ struct WasmValidator : public PostWalker<WasmValidator> {
 
   void noteLabelName(Name name) {
     if (!name.is()) return;
-    shouldBeTrue(labelNames.find(name) == labelNames.end(), name, "names in Binaren IR must be unique - IR generators must ensure that");
+    shouldBeTrue(labelNames.find(name) == labelNames.end(), name, "names in Binaryen IR must be unique - IR generators must ensure that");
     labelNames.insert(name);
   }
 
@@ -76,7 +77,13 @@ public:
   bool validate(Module& module, bool validateWeb_ = false, bool validateGlobally_ = true) {
     validateWeb = validateWeb_;
     validateGlobally = validateGlobally_;
+    // wasm logic validation
     walkModule(&module);
+    // validate additional internal IR details when in pass-debug mode
+    if (PassRunner::getPassDebug()) {
+      validateBinaryenIR(module);
+    }
+    // print if an error occurred
     if (!valid) {
       WasmPrinter::printModule(&module, std::cerr);
     }
@@ -222,16 +229,23 @@ public:
     }
   }
   void visitBreak(Break *curr) {
-    noteBreak(curr->name, curr->value, curr);
+    // note breaks (that are actually taken)
+    if ((!curr->value     || curr->value->type     != unreachable) &&
+        (!curr->condition || curr->condition->type != unreachable)) {
+      noteBreak(curr->name, curr->value, curr);
+    }
     if (curr->condition) {
       shouldBeTrue(curr->condition->type == unreachable || curr->condition->type == i32, curr, "break condition must be i32");
     }
   }
   void visitSwitch(Switch *curr) {
-    for (auto& target : curr->targets) {
-      noteBreak(target, curr->value, curr);
+    // note breaks (that are actually taken)
+    if (curr->condition->type != unreachable && (!curr->value || curr->value->type != unreachable)) {
+      for (auto& target : curr->targets) {
+        noteBreak(target, curr->value, curr);
+      }
+      noteBreak(curr->default_, curr->value, curr);
     }
-    noteBreak(curr->default_, curr->value, curr);
     shouldBeTrue(curr->condition->type == unreachable || curr->condition->type == i32, curr, "br_table condition must be i32");
   }
   void visitCall(Call *curr) {
@@ -612,8 +626,6 @@ public:
     PostWalker<WasmValidator>::doWalkFunction(func);
   }
 
-private:
-
   // helpers
 
   std::ostream& fail() {
@@ -718,6 +730,37 @@ private:
       default: {}
     }
   }
+
+  void validateBinaryenIR(Module& wasm) {
+    struct BinaryenIRValidator : public PostWalker<BinaryenIRValidator, UnifiedExpressionVisitor<BinaryenIRValidator>> {
+      WasmValidator& parent;
+
+      BinaryenIRValidator(WasmValidator& parent) : parent(parent) {}
+
+      void visitExpression(Expression* curr) {
+        // check if a node type is 'stale', i.e., we forgot to finalize() the node.
+        auto oldType = curr->type;
+        ReFinalizeNode().visit(curr);
+        auto newType = curr->type;
+        if (newType != oldType) {
+          // We accept concrete => undefined,
+          // e.g.
+          //
+          //  (drop (block i32 (unreachable)))
+          //
+          // The block has an added type, not derived from the ast itself, so it is
+          // ok for it to be either i32 or unreachable.
+          if (!(isConcreteWasmType(oldType) && newType == unreachable)) {
+            parent.fail() << "stale type found in " << getFunction()->name << " on " << curr << "\n(marked as " << printWasmType(oldType) << ", should be " << printWasmType(newType) << ")\n";
+            parent.valid = false;
+          }
+          curr->type = oldType;
+        }
+      }
+    };
+    BinaryenIRValidator binaryenIRValidator(*this);
+    binaryenIRValidator.walkModule(&wasm);
+  }
 };
 
 } // namespace wasm