[wasm] Implement polymorphic checking, matching the reference interpreter.

src/wasm/function-body-decoder.cc

Index: src/wasm/function-body-decoder.cc
diff --git a/src/wasm/function-body-decoder.cc b/src/wasm/function-body-decoder.cc
index 7c755b1a06a36c8f8995bbffcc0a62450f1361d6..02a6290216135f6abf25b07d32219f25ccf3fad9 100644
--- a/src/wasm/function-body-decoder.cc
+++ b/src/wasm/function-body-decoder.cc
@@ -104,6 +104,7 @@ struct Control {
   SsaEnv* false_env;       // false environment (only for if).
   TryInfo* try_info;       // Information used for compiling try statements.
   int32_t previous_catch;  // The previous Control (on the stack) with a catch.
+  bool unreachable;        // The current block has been ended.
 
   // Values merged into the end of this control construct.
   MergeValues merge;
@@ -116,28 +117,28 @@ struct Control {
   // Named constructors.
   static Control Block(const byte* pc, size_t stack_depth, SsaEnv* end_env,
                        int32_t previous_catch) {
-    return {pc,      kControlBlock, stack_depth,    end_env,
-            nullptr, nullptr,       previous_catch, {0, {NO_VALUE}}};
+    return {pc,      kControlBlock,  stack_depth, end_env,        nullptr,
+            nullptr, previous_catch, false,       {0, {NO_VALUE}}};
   }
 
   static Control If(const byte* pc, size_t stack_depth, SsaEnv* end_env,
                     SsaEnv* false_env, int32_t previous_catch) {
-    return {pc,        kControlIf, stack_depth,    end_env,
-            false_env, nullptr,    previous_catch, {0, {NO_VALUE}}};
+    return {pc,      kControlIf,     stack_depth, end_env,        false_env,
+            nullptr, previous_catch, false,       {0, {NO_VALUE}}};
   }
 
   static Control Loop(const byte* pc, size_t stack_depth, SsaEnv* end_env,
                       int32_t previous_catch) {
-    return {pc,      kControlLoop, stack_depth,    end_env,
-            nullptr, nullptr,      previous_catch, {0, {NO_VALUE}}};
+    return {pc,      kControlLoop,   stack_depth, end_env,        nullptr,
+            nullptr, previous_catch, false,       {0, {NO_VALUE}}};
   }
 
   static Control Try(const byte* pc, size_t stack_depth, SsaEnv* end_env,
                      Zone* zone, SsaEnv* catch_env, int32_t previous_catch) {
     DCHECK_NOT_NULL(catch_env);
     TryInfo* try_info = new (zone) TryInfo(catch_env);
-    return {pc,      kControlTry, stack_depth,    end_env,
-            nullptr, try_info,    previous_catch, {0, {NO_VALUE}}};
+    return {pc,       kControlTry,    stack_depth, end_env,        nullptr,
+            try_info, previous_catch, false,       {0, {NO_VALUE}}};
   }
 };
 
@@ -708,7 +709,7 @@ class WasmFullDecoder : public WasmDecoder {
             // TODO(titzer): Throw should end control, but currently we build a
             // (reachable) runtime call instead of connecting it directly to
             // end.
-            //            EndControl();
+            //            EndControl(len);
             break;
           }
           case kExprTry: {
@@ -744,14 +745,14 @@ class WasmFullDecoder : public WasmDecoder {
               break;
             }
 
-            if (ssa_env_->go()) {
-              MergeValuesInto(c);
-            }
+            FallThruTo(c);
+            c->unreachable = false;
             stack_.resize(c->stack_depth);
 
             DCHECK_NOT_NULL(c->try_info);
             SsaEnv* catch_env = c->try_info->catch_env;
             c->try_info->catch_env = nullptr;
+            c->unreachable = false;
             SetEnv("catch:begin", catch_env);
             current_catch_ = c->previous_catch;
 
@@ -810,6 +811,7 @@ class WasmFullDecoder : public WasmDecoder {
               break;
             }
             FallThruTo(c);
+            c->unreachable = false;
             // Switch to environment for false branch.
             stack_.resize(c->stack_depth);
             SetEnv("if_else:false", c->false_env);
@@ -826,6 +828,7 @@ class WasmFullDecoder : public WasmDecoder {
             if (c->is_loop()) {
               // A loop just leaves the values on the stack.
               TypeCheckLoopFallThru(c);
+              if (c->unreachable) PushEndValues(c);
               PopControl();
               SetEnv("loop:end", ssa_env_);
               break;
@@ -834,7 +837,7 @@ class WasmFullDecoder : public WasmDecoder {
               if (c->false_env != nullptr) {
                 // End the true branch of a one-armed if.
                 Goto(c->false_env, c->end_env);
-                if (ssa_env_->go() && stack_.size() != c->stack_depth) {
+                if (!c->unreachable && stack_.size() != c->stack_depth) {
                   error("end of if expected empty stack");
                   stack_.resize(c->stack_depth);
                 }
@@ -856,18 +859,13 @@ class WasmFullDecoder : public WasmDecoder {
               }
             }
             FallThruTo(c);
+            c->unreachable = false;
             SetEnv(name, c->end_env);
 
             // Push the end values onto the stack.
-            stack_.resize(c->stack_depth);
-            if (c->merge.arity == 1) {
-              stack_.push_back(c->merge.vals.first);
-            } else {
-              for (unsigned i = 0; i < c->merge.arity; i++) {
-                stack_.push_back(c->merge.vals.array[i]);
-              }
-            }
+            PushEndValues(c);
 
+            DCHECK_EQ(c->stack_depth + c->merge.arity, stack_.size());
             if (control_.size() == 1) {
               // If at the last (implicit) control, check we are at end.
               if (pc_ + 1 != end_) {
@@ -878,8 +876,10 @@ class WasmFullDecoder : public WasmDecoder {
               if (ssa_env_->go()) {
                 // The result of the block is the return value.
                 TRACE("  @%-8d #xx:%-20s|", startrel(pc_), "(implicit) return");
-                DoReturn();
+                DoReturn(0);
                 TRACE("\n");
+              } else {
+                TypeCheckLoopFallThru(c);
               }
             }
             PopControl();
@@ -888,17 +888,8 @@ class WasmFullDecoder : public WasmDecoder {
           case kExprSelect: {
             Value cond = Pop(2, kWasmI32);
             Value fval = Pop();
-            Value tval = Pop();
-            if (tval.type == kWasmStmt || tval.type != fval.type) {
-              if (tval.type != kWasmEnd && fval.type != kWasmEnd) {
-                error("type mismatch in select");
-                break;
-              }
-            }
+            Value tval = Pop(0, fval.type);
             if (build()) {
-              DCHECK(tval.type != kWasmEnd);
-              DCHECK(fval.type != kWasmEnd);
-              DCHECK(cond.type != kWasmEnd);
               TFNode* controls[2];
               builder_->BranchNoHint(cond.node, &controls[0], &controls[1]);
               TFNode* merge = builder_->Merge(2, controls);
@@ -907,7 +898,7 @@ class WasmFullDecoder : public WasmDecoder {
               Push(tval.type, phi);
               ssa_env_->control = merge;
             } else {
-              Push(tval.type, nullptr);
+              Push(tval.type == kWasmVar ? fval.type : tval.type, nullptr);
             }
             break;
           }
@@ -917,7 +908,7 @@ class WasmFullDecoder : public WasmDecoder {
               BreakTo(operand.depth);
             }
             len = 1 + operand.length;
-            EndControl();
+            EndControl(len);
             break;
           }
           case kExprBrIf: {
@@ -978,16 +969,16 @@ class WasmFullDecoder : public WasmDecoder {
               ssa_env_ = break_env;
             }
             len = 1 + iterator.length();
-            EndControl();
+            EndControl(len);
             break;
           }
           case kExprReturn: {
-            DoReturn();
+            DoReturn(len);
             break;
           }
           case kExprUnreachable: {
             BUILD(Unreachable, position());
-            EndControl();
+            EndControl(len);
             break;
           }
           case kExprI32Const: {
@@ -1229,6 +1220,35 @@ class WasmFullDecoder : public WasmDecoder {
 
 #if DEBUG
       if (FLAG_trace_wasm_decoder) {
+        PrintF(" ");
+        for (size_t i = 0; i < control_.size(); ++i) {
+          Control* c = &control_[i];
+          enum ControlKind {
+            kControlIf,
+            kControlBlock,
+            kControlLoop,
+            kControlTry
+          };
+          switch (c->kind) {
+            case kControlIf:
+              PrintF("I");
+              break;
+            case kControlBlock:
+              PrintF("B");
+              break;
+            case kControlLoop:
+              PrintF("L");
+              break;
+            case kControlTry:
+              PrintF("T");
+              break;
+            default:
+              break;
+          }
+          PrintF("%u", c->merge.arity);
+          if (c->unreachable) PrintF("*");
+        }
+        PrintF(" | ");
         for (size_t i = 0; i < stack_.size(); ++i) {
           Value& val = stack_[i];
           WasmOpcode opcode = static_cast<WasmOpcode>(*val.pc);
@@ -1258,6 +1278,7 @@ class WasmFullDecoder : public WasmDecoder {
             default:
               break;
           }
+          if (val.node == nullptr) PrintF("?");
         }
         PrintF("\n");
       }
@@ -1267,13 +1288,11 @@ class WasmFullDecoder : public WasmDecoder {
     if (pc_ > end_ && ok()) error("Beyond end of code");
   }
 
-  void EndControl() {
+  void EndControl(int len) {
     ssa_env_->Kill(SsaEnv::kControlEnd);
-    if (control_.empty()) {
-      stack_.clear();
-    } else {
-      DCHECK_LE(control_.back().stack_depth, stack_.size());
+    if (!control_.empty()) {
       stack_.resize(control_.back().stack_depth);
+      control_.back().unreachable = true;
     }
   }
 
@@ -1423,7 +1442,7 @@ class WasmFullDecoder : public WasmDecoder {
 
   void BuildAtomicOperator(WasmOpcode opcode) { UNIMPLEMENTED(); }
 
-  void DoReturn() {
+  void DoReturn(int len) {
     int count = static_cast<int>(sig_->return_count());
     TFNode** buffer = nullptr;
     if (build()) buffer = builder_->Buffer(count);
@@ -1435,15 +1454,26 @@ class WasmFullDecoder : public WasmDecoder {
     }
 
     BUILD(Return, count, buffer);
-    EndControl();
+    EndControl(len);
   }
 
   void Push(ValueType type, TFNode* node) {
-    if (type != kWasmStmt && type != kWasmEnd) {
+    if (type != kWasmStmt) {
       stack_.push_back({pc_, node, type});
     }
   }
 
+  void PushEndValues(Control* c) {
+    stack_.resize(c->stack_depth);
+    if (c->merge.arity == 1) {
+      stack_.push_back(c->merge.vals.first);
+    } else {
+      for (unsigned i = 0; i < c->merge.arity; i++) {
+        stack_.push_back(c->merge.vals.array[i]);
+      }
+    }
+  }
+
   void PushReturns(FunctionSig* sig, TFNode** rets) {
     for (size_t i = 0; i < sig->return_count(); i++) {
       // When verifying only, then {rets} will be null, so push null.
@@ -1458,12 +1488,10 @@ class WasmFullDecoder : public WasmDecoder {
 
   Value Pop(int index, ValueType expected) {
     Value val = Pop();
-    if (val.type != expected) {
-      if (val.type != kWasmEnd) {
-        error(pc_, val.pc, "%s[%d] expected type %s, found %s of type %s",
-              SafeOpcodeNameAt(pc_), index, WasmOpcodes::TypeName(expected),
-              SafeOpcodeNameAt(val.pc), WasmOpcodes::TypeName(val.type));
-      }
+    if (val.type != expected && val.type != kWasmVar && expected != kWasmVar) {
+      error(pc_, val.pc, "%s[%d] expected type %s, found %s of type %s",
+            SafeOpcodeNameAt(pc_), index, WasmOpcodes::TypeName(expected),
+            SafeOpcodeNameAt(val.pc), WasmOpcodes::TypeName(val.type));
     }
     return val;
   }
@@ -1471,9 +1499,9 @@ class WasmFullDecoder : public WasmDecoder {
   Value Pop() {
     size_t limit = control_.empty() ? 0 : control_.back().stack_depth;
     if (stack_.size() <= limit) {
-      Value val = {pc_, nullptr, kWasmEnd};
-      if (ssa_env_->go()) {
-        // Popping past the current control start in reachable code.
+      // Popping past the current control start in reachable code.
+      Value val = {pc_, nullptr, kWasmVar};
+      if (!control_.back().unreachable) {
         error(pc_, pc_, "%s found empty stack", SafeOpcodeNameAt(pc_));
       }
       return val;
@@ -1490,17 +1518,17 @@ class WasmFullDecoder : public WasmDecoder {
   int startrel(const byte* ptr) { return static_cast<int>(ptr - start_); }
 
   void BreakTo(unsigned depth) {
-    if (!ssa_env_->go()) return;
     Control* c = &control_[control_.size() - depth - 1];
     if (c->is_loop()) {
       // This is the inner loop block, which does not have a value.
       Goto(ssa_env_, c->end_env);
     } else {
       // Merge the value(s) into the end of the block.
-      if (c->stack_depth + c->merge.arity > stack_.size()) {
+      size_t expected = c->stack_depth + c->merge.arity;
+      if (!c->unreachable && stack_.size() < expected) {
         error(
             pc_, pc_,
-            "expected at least %d values on the stack for br to @%d, found %d",
+            "expected at least %u values on the stack for br to @%d, found %d",
             c->merge.arity, startrel(c->pc),
             static_cast<int>(stack_.size() - c->stack_depth));
         return;
@@ -1510,37 +1538,36 @@ class WasmFullDecoder : public WasmDecoder {
   }
 
   void FallThruTo(Control* c) {
-    if (!ssa_env_->go()) return;
     // Merge the value(s) into the end of the block.
-    int arity = static_cast<int>(c->merge.arity);
-    if (c->stack_depth + arity != stack_.size()) {
-      error(pc_, pc_, "expected %d elements on the stack for fallthru to @%d",
-            arity, startrel(c->pc));
-      return;
-    }
-    MergeValuesInto(c);
+    size_t expected = c->stack_depth + c->merge.arity;
+    if (stack_.size() == expected) return MergeValuesInto(c);
+    if (c->unreachable && stack_.size() < expected) return MergeValuesInto(c);
+    error(pc_, pc_, "expected %u elements on the stack for fallthru to @%d",
+          c->merge.arity, startrel(c->pc));
   }
 
-  inline Value& GetMergeValueFromStack(Control* c, int i) {
+  inline Value& GetMergeValueFromStack(Control* c, size_t i) {
     return stack_[stack_.size() - c->merge.arity + i];
   }
 
   void TypeCheckLoopFallThru(Control* c) {
-    if (!ssa_env_->go()) return;
     // Fallthru must match arity exactly.
     int arity = static_cast<int>(c->merge.arity);
-    if (c->stack_depth + arity != stack_.size()) {
+    if (c->stack_depth + arity < stack_.size() ||
+        (!c->unreachable && c->stack_depth + arity != stack_.size())) {
       error(pc_, pc_, "expected %d elements on the stack for fallthru to @%d",
             arity, startrel(c->pc));
       return;
     }
     // Typecheck the values left on the stack.
-    for (unsigned i = 0; i < c->merge.arity; i++) {
+    size_t avail = stack_.size() - c->stack_depth;
+    for (size_t i = avail >= c->merge.arity ? 0 : c->merge.arity - avail;
+         i < c->merge.arity; i++) {
       Value& val = GetMergeValueFromStack(c, i);
       Value& old =
           c->merge.arity == 1 ? c->merge.vals.first : c->merge.vals.array[i];
       if (val.type != old.type) {
-        error(pc_, pc_, "type error in merge[%d] (expected %s, got %s)", i,
+        error(pc_, pc_, "type error in merge[%zu] (expected %s, got %s)", i,
               WasmOpcodes::TypeName(old.type), WasmOpcodes::TypeName(val.type));
         return;
       }
@@ -1550,23 +1577,25 @@ class WasmFullDecoder : public WasmDecoder {
   void MergeValuesInto(Control* c) {
     SsaEnv* target = c->end_env;
     bool first = target->state == SsaEnv::kUnreachable;
+    bool reachable = ssa_env_->go();
     Goto(ssa_env_, target);
 
-    for (unsigned i = 0; i < c->merge.arity; i++) {
+    size_t avail = stack_.size() - c->stack_depth;
+    for (size_t i = avail >= c->merge.arity ? 0 : c->merge.arity - avail;
+         i < c->merge.arity; i++) {
       Value& val = GetMergeValueFromStack(c, i);
       Value& old =
           c->merge.arity == 1 ? c->merge.vals.first : c->merge.vals.array[i];
-      if (val.type != old.type) {
-        error(pc_, pc_, "type error in merge[%d] (expected %s, got %s)", i,
+      if (val.type != old.type && val.type != kWasmVar) {
+        error(pc_, pc_, "type error in merge[%zu] (expected %s, got %s)", i,
               WasmOpcodes::TypeName(old.type), WasmOpcodes::TypeName(val.type));
         return;
       }
-      if (builder_) {
+      if (builder_ && reachable) {
+        DCHECK_NOT_NULL(val.node);
         old.node =
             first ? val.node : CreateOrMergeIntoPhi(old.type, target->control,
                                                     old.node, val.node);
-      } else {
-        old.node = nullptr;
       }
     }
   }
@@ -1591,13 +1620,13 @@ class WasmFullDecoder : public WasmDecoder {
             break;
         }
       }
-      PrintF("  env = %p, state = %c, reason = %s", static_cast<void*>(env),
+      PrintF("{set_env = %p, state = %c, reason = %s", static_cast<void*>(env),
              state, reason);
       if (env && env->control) {
         PrintF(", control = ");
         compiler::WasmGraphBuilder::PrintDebugName(env->control);
       }
-      PrintF("\n");
+      PrintF("}");
     }
 #endif
     ssa_env_ = env;