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

src/wasm/function-body-decoder.cc

 // Copyright 2015 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "src/signature.h"
 
 #include "src/bit-vector.h"
 #include "src/flags.h"
 #include "src/handles.h"
 #include "src/zone/zone-containers.h"
@@ skipping 86 matching lines @@
 
 // An entry on the control stack (i.e. if, block, loop).
 struct Control {
   const byte* pc;
   ControlKind kind;
   size_t stack_depth;      // stack height at the beginning of the construct.
   SsaEnv* end_env;         // end environment for the construct.
   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;
 
   inline bool is_if() const { return kind == kControlIf; }
   inline bool is_block() const { return kind == kControlBlock; }
   inline bool is_loop() const { return kind == kControlLoop; }
   inline bool is_try() const { return kind == kControlTry; }
 
   // 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}}};
   }
 };
 
 // Macros that build nodes only if there is a graph and the current SSA
 // environment is reachable from start. This avoids problems with malformed
 // TF graphs when decoding inputs that have unreachable code.
 #define BUILD(func, ...) \
   (build() ? CheckForException(builder_->func(__VA_ARGS__)) : nullptr)
 #define BUILD0(func) (build() ? CheckForException(builder_->func()) : nullptr)
 
@@ skipping 550 matching lines @@
             len = 1 + operand.length;
             break;
           }
           case kExprThrow: {
             CHECK_PROTOTYPE_OPCODE(wasm_eh_prototype);
             Value value = Pop(0, kWasmI32);
             BUILD(Throw, value.node);
             // 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: {
             CHECK_PROTOTYPE_OPCODE(wasm_eh_prototype);
             BlockTypeOperand operand(this, pc_);
             SsaEnv* outer_env = ssa_env_;
             SsaEnv* try_env = Steal(outer_env);
             SsaEnv* catch_env = UnreachableEnv();
             PushTry(outer_env, catch_env);
             SetEnv("try_catch:start", try_env);
@@ skipping 15 matching lines @@
             if (!c->is_try()) {
               error("catch does not match any try");
               break;
             }
 
             if (c->try_info->catch_env == nullptr) {
               error(pc_, "catch already present for try with catch");
               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;

[rossberg, 2017/02/02 13:01:27]

Why is this set to false twice?

[titzer, 2017/02/02 18:50:19]

Done.

             SetEnv("catch:begin", catch_env);
             current_catch_ = c->previous_catch;
 
             if (Validate(pc_, operand)) {
               if (ssa_env_->locals) {
                 TFNode* exception_as_i32 =
                     BUILD(Catch, c->try_info->exception, position());
                 ssa_env_->locals[operand.index] = exception_as_i32;
               }
             }
@@ skipping 38 matching lines @@
             Control* c = &control_.back();
             if (!c->is_if()) {
               error(pc_, c->pc, "else does not match an if");
               break;
             }
             if (c->false_env == nullptr) {
               error(pc_, c->pc, "else already present for if");
               break;
             }
             FallThruTo(c);
+            c->unreachable = false;

[rossberg, 2017/02/02 13:01:27]

This pattern occurs several times, could this be moved into FallThruTo?

[titzer, 2017/02/02 18:50:19]

Done.

             // Switch to environment for false branch.
             stack_.resize(c->stack_depth);
             SetEnv("if_else:false", c->false_env);
             c->false_env = nullptr;  // record that an else is already seen
             break;
           }
           case kExprEnd: {
             if (control_.empty()) {
               error("end does not match any if, try, or block");
               return;
             }
             const char* name = "block:end";
             Control* c = &control_.back();
             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;
             }
             if (c->is_if()) {
               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);
                 }
                 if (c->merge.arity > 0) {
                   error("non-void one-armed if");
                 }
                 name = "if:merge";
               } else {
                 // End the false branch of a two-armed if.
                 name = "if_else:merge";
               }
             } else if (c->is_try()) {
               name = "try:end";
 
               // validate that catch was seen.
               if (c->try_info->catch_env != nullptr) {
                 error(pc_, "missing catch in try");
                 break;
               }
             }
             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);

[rossberg, 2017/02/02 13:01:27]

Nit: calling the function might make the preceding comment redundant.

[titzer, 2017/02/02 18:50:19]

Done.

 
+            DCHECK_EQ(c->stack_depth + c->merge.arity, stack_.size());

[rossberg, 2017/02/02 13:01:27]

Maybe move this assertion into PushEndValues?

[titzer, 2017/02/02 18:50:19]

Done.

             if (control_.size() == 1) {
               // If at the last (implicit) control, check we are at end.
               if (pc_ + 1 != end_) {
                 error(pc_, pc_ + 1, "trailing code after function end");
                 break;
               }
               last_end_found_ = true;
               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);

[rossberg, 2017/02/02 13:01:27]

Nit: might make sense to remove the "Loop" from the name of this function.

[titzer, 2017/02/02 18:50:19]

Done.

               }
             }
             PopControl();
             break;
           }
           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);
               TFNode* vals[2] = {tval.node, fval.node};
               TFNode* phi = builder_->Phi(tval.type, 2, vals, merge);
               Push(tval.type, phi);
               ssa_env_->control = merge;
             } else {
-              Push(tval.type, nullptr);
+              Push(tval.type == kWasmVar ? fval.type : tval.type, nullptr);
             }
             break;
           }
           case kExprBr: {
             BreakDepthOperand operand(this, pc_);
             if (Validate(pc_, operand, control_)) {
               BreakTo(operand.depth);
             }
             len = 1 + operand.length;
-            EndControl();
+            EndControl(len);
             break;
           }
           case kExprBrIf: {
             BreakDepthOperand operand(this, pc_);
             Value cond = Pop(0, kWasmI32);
             if (ok() && Validate(pc_, operand, control_)) {
               SsaEnv* fenv = ssa_env_;
               SsaEnv* tenv = Split(fenv);
               fenv->SetNotMerged();
               BUILD(BranchNoHint, cond.node, &tenv->control, &fenv->control);
@@ skipping 40 matching lines @@
                 if (target >= control_.size()) {
                   error(pos, "improper branch in br_table");
                   break;
                 }
                 BreakTo(target);
               }
               // br_table ends the control flow like br.
               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: {
             ImmI32Operand operand(this, pc_);
             Push(kWasmI32, BUILD(Int32Constant, operand.value));
             len = 1 + operand.length;
             break;
           }
           case kExprI64Const: {
             ImmI64Operand operand(this, pc_);
@@ skipping 221 matching lines @@
             } else {
               error("Invalid opcode");
               return;
             }
           }
         }
       }
 
 #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);
           if (WasmOpcodes::IsPrefixOpcode(opcode)) {
             opcode = static_cast<WasmOpcode>(opcode << 8 | *(val.pc + 1));
           }
           PrintF(" %c@%d:%s", WasmOpcodes::ShortNameOf(val.type),
                  static_cast<int>(val.pc - start_),
                  WasmOpcodes::OpcodeName(opcode));
           switch (opcode) {
             case kExprI32Const: {
               ImmI32Operand operand(this, val.pc);
               PrintF("[%d]", operand.value);
               break;
             }
             case kExprGetLocal: {
               LocalIndexOperand operand(this, val.pc);
               PrintF("[%u]", operand.index);
               break;
             }
             case kExprSetLocal:  // fallthru
             case kExprTeeLocal: {
               LocalIndexOperand operand(this, val.pc);
               PrintF("[%u]", operand.index);
               break;
             }
             default:
               break;
           }
+          if (val.node == nullptr) PrintF("?");
         }
         PrintF("\n");
       }
 #endif
       pc_ += len;
     }  // end decode loop
     if (pc_ > end_ && ok()) error("Beyond end of code");
   }
 
-  void EndControl() {
+  void EndControl(int len) {

[rossberg, 2017/02/02 13:01:27]

The parameter seems to be unused.

[titzer, 2017/02/02 18:50:19]

Done.
A holdover from the disallowing-unreachable patch.

     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;
     }
   }
 
   void SetBlockType(Control* c, BlockTypeOperand& operand) {
     c->merge.arity = operand.arity;
     if (c->merge.arity == 1) {
       c->merge.vals.first = {pc_, nullptr, operand.read_entry(0)};
     } else if (c->merge.arity > 1) {
       c->merge.vals.array = zone_->NewArray<Value>(c->merge.arity);
       for (unsigned i = 0; i < c->merge.arity; i++) {
@@ skipping 129 matching lines @@
         } else {
           error("invalid simd opcode");
         }
       }
     }
     return len;
   }
 
   void BuildAtomicOperator(WasmOpcode opcode) { UNIMPLEMENTED(); }
 
-  void DoReturn() {
+  void DoReturn(int len) {

[rossberg, 2017/02/02 13:01:27]

And transitively, this one, too.

[titzer, 2017/02/02 18:50:19]

Done.

     int count = static_cast<int>(sig_->return_count());
     TFNode** buffer = nullptr;
     if (build()) buffer = builder_->Buffer(count);
 
     // Pop return values off the stack in reverse order.
     for (int i = count - 1; i >= 0; i--) {
       Value val = Pop(i, sig_->GetReturn(i));
       if (buffer) buffer[i] = val.node;
     }
 
     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.
       Push(sig->GetReturn(i), rets ? rets[i] : nullptr);
     }
   }
 
   const char* SafeOpcodeNameAt(const byte* pc) {
     if (pc >= end_) return "<end>";
     return WasmOpcodes::OpcodeName(static_cast<WasmOpcode>(*pc));
   }
 
   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;
   }
 
   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;
     }
     Value val = stack_.back();
     stack_.pop_back();
     return val;
   }
 
   int baserel(const byte* ptr) {
     return base_ ? static_cast<int>(ptr - base_) : 0;
   }
 
   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;
       }
       MergeValuesInto(c);
     }
   }
 
   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;
       }
     }
   }
 
   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;
       }
     }
   }
 
   void SetEnv(const char* reason, SsaEnv* env) {
 #if DEBUG
     if (FLAG_trace_wasm_decoder) {
       char state = 'X';
       if (env) {
         switch (env->state) {
           case SsaEnv::kReached:
             state = 'R';
             break;
           case SsaEnv::kUnreachable:
             state = 'U';
             break;
           case SsaEnv::kMerged:
             state = 'M';
             break;
           case SsaEnv::kControlEnd:
             state = 'E';
             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;
     if (builder_) {
       builder_->set_control_ptr(&env->control);
       builder_->set_effect_ptr(&env->effect);
     }
   }
 
   TFNode* CheckForException(TFNode* node) {
@@ skipping 441 matching lines @@
 BitVector* AnalyzeLoopAssignmentForTesting(Zone* zone, size_t num_locals,
                                            const byte* start, const byte* end) {
   Decoder decoder(start, end);
   return WasmDecoder::AnalyzeLoopAssignment(&decoder, start,
                                             static_cast<int>(num_locals), zone);
 }
 
 }  // namespace wasm
 }  // namespace internal
 }  // namespace v8