[Interpreter] Basic flow control.

src/interpreter/bytecode-array-builder.cc

Index: src/interpreter/bytecode-array-builder.cc
diff --git a/src/interpreter/bytecode-array-builder.cc b/src/interpreter/bytecode-array-builder.cc
index f3a1b1ea0803959990370da458ae10da87d8ec54..3ca8a49522aa85d62dd9a5d4d9c20d0c07703002 100644
--- a/src/interpreter/bytecode-array-builder.cc
+++ b/src/interpreter/bytecode-array-builder.cc
@@ -12,6 +12,8 @@ BytecodeArrayBuilder::BytecodeArrayBuilder(Isolate* isolate, Zone* zone)
     : isolate_(isolate),
       bytecodes_(zone),
       bytecode_generated_(false),
+      last_block_end_(0),
+      last_bytecode_start_(~0),
       constants_map_(isolate->heap(), zone),
       constants_(zone),
       parameter_count_(-1),
@@ -37,14 +39,6 @@ void BytecodeArrayBuilder::set_parameter_count(int number_of_parameters) {
 int BytecodeArrayBuilder::parameter_count() const { return parameter_count_; }
 
 
-bool BytecodeArrayBuilder::HasExplicitReturn() {
-  // TODO(rmcilroy): When we have control flow we should return false here if
-  // there is an outstanding jump target, even if the last bytecode is kReturn.
-  return !bytecodes_.empty() &&
-         bytecodes_.back() == Bytecodes::ToByte(Bytecode::kReturn);
-}
-
-
 Register BytecodeArrayBuilder::Parameter(int parameter_index) {
   DCHECK_GE(parameter_index, 0);
   DCHECK_LT(parameter_index, parameter_count_);
@@ -56,6 +50,7 @@ Handle<BytecodeArray> BytecodeArrayBuilder::ToBytecodeArray() {
   DCHECK_EQ(bytecode_generated_, false);
   DCHECK_GE(parameter_count_, 0);
   DCHECK_GE(local_register_count_, 0);
+  EnsureReturn();

[rmcilroy, 2015/09/23 14:00:28]

nit - newlines around this.

[oth, 2015/09/24 11:15:27]

Done.

   int bytecode_size = static_cast<int>(bytecodes_.size());
   int register_count = local_register_count_ + temporary_register_count_;
   int frame_size = register_count * kPointerSize;
@@ -76,9 +71,57 @@ Handle<BytecodeArray> BytecodeArrayBuilder::ToBytecodeArray() {
 }
 
 
-BytecodeArrayBuilder& BytecodeArrayBuilder::BinaryOperation(Token::Value binop,
+template <size_t N>
+void BytecodeArrayBuilder::Output(uint8_t(&bytes)[N]) {
+  DCHECK_EQ(Bytecodes::NumberOfOperands(Bytecodes::FromByte(bytes[0])), N - 1);
+  last_bytecode_start_ = bytecodes()->size();
+  for (int i = 1; i < static_cast<int>(N); i++) {
+    DCHECK(OperandIsValid(Bytecodes::FromByte(bytes[0]), i - 1, bytes[i]));
+  }
+  bytecodes()->insert(bytecodes()->end(), bytes, bytes + N);
+}
+
+
+void BytecodeArrayBuilder::Output(Bytecode bytecode, uint8_t operand0,
+                                  uint8_t operand1, uint8_t operand2) {
+  uint8_t bytes[] = {Bytecodes::ToByte(bytecode), operand0, operand1, operand2};
+  Output(bytes);

[rmcilroy, 2015/09/23 14:00:28]

personally I prefer the old-style returns (each of which just did the
push_back() themselves) - this avoided building a new array for each bytecode as
these do.

[oth, 2015/09/24 11:15:27]

The point is well made. This pattern occurs elsewhere in v8 and I think there's
a good case centralizing this:

1) Fewer calls to std::vector::push_back() and means fewer resize checks and
fewer resizes.
2) Common code is not repeated and potentially lost when next iteration is
cut-n-pasted or new functionality added, like the update of
last_bytecode_start_.
3) No fiddly handwritten hard-coded constants.

[rmcilroy, 2015/09/24 11:44:36]

Ok, you've convinced me :).

+}
+
+
+void BytecodeArrayBuilder::Output(Bytecode bytecode, uint8_t operand0,
+                                  uint8_t operand1) {
+  uint8_t bytes[] = {Bytecodes::ToByte(bytecode), operand0, operand1};
+  Output(bytes);
+}
+
+
+void BytecodeArrayBuilder::Output(Bytecode bytecode, uint8_t operand0) {
+  uint8_t bytes[] = {Bytecodes::ToByte(bytecode), operand0};
+  Output(bytes);
+}
+
+
+void BytecodeArrayBuilder::Output(Bytecode bytecode) {
+  uint8_t bytes[] = {Bytecodes::ToByte(bytecode)};
+  Output(bytes);
+}
+
+
+BytecodeArrayBuilder& BytecodeArrayBuilder::BinaryOperation(Token::Value op,
                                                             Register reg) {
-  Output(BytecodeForBinaryOperation(binop), reg.ToOperand());
+  Output(BytecodeForBinaryOperation(op), reg.ToOperand());
+  return *this;
+}
+
+
+BytecodeArrayBuilder& BytecodeArrayBuilder::CompareOperation(
+    Token::Value op, Register reg, LanguageMode language_mode) {
+  if (!is_sloppy(language_mode)) {
+    UNIMPLEMENTED();
+  }
+
+  Output(BytecodeForCompareOperation(op), reg.ToOperand());
   return *this;
 }
 
@@ -99,7 +142,7 @@ BytecodeArrayBuilder& BytecodeArrayBuilder::LoadLiteral(
 
 BytecodeArrayBuilder& BytecodeArrayBuilder::LoadLiteral(Handle<Object> object) {
   size_t entry = GetConstantPoolEntry(object);
-  if (FitsInByteOperand(entry)) {
+  if (FitsInIdxOperand(entry)) {
     Output(Bytecode::kLdaConstant, static_cast<uint8_t>(entry));
   } else {
     UNIMPLEMENTED();
@@ -158,7 +201,7 @@ BytecodeArrayBuilder& BytecodeArrayBuilder::LoadNamedProperty(
     UNIMPLEMENTED();
   }
 
-  if (FitsInByteOperand(feedback_slot)) {
+  if (FitsInIdxOperand(feedback_slot)) {
     Output(Bytecode::kLoadIC, object.ToOperand(),
            static_cast<uint8_t>(feedback_slot));
   } else {
@@ -174,7 +217,7 @@ BytecodeArrayBuilder& BytecodeArrayBuilder::LoadKeyedProperty(
     UNIMPLEMENTED();
   }
 
-  if (FitsInByteOperand(feedback_slot)) {
+  if (FitsInIdxOperand(feedback_slot)) {
     Output(Bytecode::kKeyedLoadIC, object.ToOperand(),
            static_cast<uint8_t>(feedback_slot));
   } else {
@@ -191,7 +234,7 @@ BytecodeArrayBuilder& BytecodeArrayBuilder::StoreNamedProperty(
     UNIMPLEMENTED();
   }
 
-  if (FitsInByteOperand(feedback_slot)) {
+  if (FitsInIdxOperand(feedback_slot)) {
     Output(Bytecode::kStoreIC, object.ToOperand(), name.ToOperand(),
            static_cast<uint8_t>(feedback_slot));
   } else {
@@ -208,7 +251,7 @@ BytecodeArrayBuilder& BytecodeArrayBuilder::StoreKeyedProperty(
     UNIMPLEMENTED();
   }
 
-  if (FitsInByteOperand(feedback_slot)) {
+  if (FitsInIdxOperand(feedback_slot)) {
     Output(Bytecode::kKeyedStoreIC, object.ToOperand(), key.ToOperand(),
            static_cast<uint8_t>(feedback_slot));
   } else {
@@ -218,16 +261,177 @@ BytecodeArrayBuilder& BytecodeArrayBuilder::StoreKeyedProperty(
 }
 
 
+BytecodeArrayBuilder& BytecodeArrayBuilder::CastAccumulatorToBoolean() {
+  if (LastBytecodeInSameBlock()) {
+    // If the previous bytecode puts a boolean in the accumulator
+    // there is no need to emit an instruction.
+    switch (Bytecodes::FromByte(bytecodes()->at(last_bytecode_start_))) {
+      case Bytecode::kCastToBoolean:
+        DCHECK(false);

[rmcilroy, 2015/09/23 14:00:28]

nit - just UNREACHABLE()

[oth, 2015/09/24 11:15:27]

Done.

+      case Bytecode::kLdaTrue:
+      case Bytecode::kLdaFalse:
+      case Bytecode::kTestEqual:
+      case Bytecode::kTestNotEqual:
+      case Bytecode::kTestEqualStrict:
+      case Bytecode::kTestNotEqualStrict:
+      case Bytecode::kTestLessThan:
+      case Bytecode::kTestLessThanEqual:
+      case Bytecode::kTestGreaterThan:
+      case Bytecode::kTestGreaterThanEqual:
+      case Bytecode::kTestInstanceOf:
+      case Bytecode::kTestIn:
+        break;
+      default:
+        Output(Bytecode::kCastToBoolean);
+    }
+  }
+  return *this;
+}
+
+
+BytecodeArrayBuilder& BytecodeArrayBuilder::Bind(BytecodeLabel* label) {
+  if (label->is_forward_target()) {
+    // An earlier jump instruction refers to this label. Update it's location.
+    PatchJump(bytecodes()->end(), bytecodes()->begin() + label->offset());
+    // Now treat as if the label will only be back referred to.
+  }
+  label->bind_to(bytecodes()->size());
+  return *this;
+}
+
+
+// static
+bool BytecodeArrayBuilder::IsJumpWithSmi8Operand(Bytecode jump_bytecode) {

[rmcilroy, 2015/09/23 14:00:28]

nit /s/Smi8/Imm8

[oth, 2015/09/24 11:15:27]

Done.

+  return jump_bytecode == Bytecode::kJump ||
+         jump_bytecode == Bytecode::kJumpIfTrue ||
+         jump_bytecode == Bytecode::kJumpIfFalse;
+}
+
+
+// static
+Bytecode BytecodeArrayBuilder::GetJumpWithConstantOperand(
+    Bytecode jump_bytecode) {
+  switch (jump_bytecode) {
+    case Bytecode::kJump:
+      return Bytecode::kJumpConstant;
+    case Bytecode::kJumpIfTrue:
+      return Bytecode::kJumpIfTrueConstant;
+    case Bytecode::kJumpIfFalse:
+      return Bytecode::kJumpIfFalseConstant;
+    default:
+      UNREACHABLE();
+      return Bytecode::kJumpConstant;
+  }
+}
+
+
+void BytecodeArrayBuilder::PatchJump(
+    const ZoneVector<uint8_t>::iterator& jump_target,
+    ZoneVector<uint8_t>::iterator jump_location) {
+  Bytecode jump_bytecode = Bytecodes::FromByte(*jump_location);
+  DCHECK(IsJumpWithSmi8Operand(jump_bytecode));
+  DCHECK_EQ(Bytecodes::Size(jump_bytecode), 2);
+  int delta = static_cast<int>(jump_target - jump_location);
+  DCHECK_GE(delta, 0);
+  if (FitsInImm8Operand(delta)) {
+    // Just update the operand
+    jump_location++;
+    *jump_location = static_cast<uint8_t>(delta);
+  } else {
+    // Update the jump type and operand
+    size_t entry = GetConstantPoolEntry(handle(Smi::FromInt(delta), isolate()));

[rmcilroy, 2015/09/23 14:00:28]

We will need to reserve the constant pool entry ahead of time (when the jump is
emitted) to ensure it the index will fit in a byte when we get to patch it. We
can do this in a followup CL, but please ad the TODO in the else block to remind
us.

[oth, 2015/09/24 11:15:27]

Done.

+    if (FitsInIdxOperand(entry)) {
+      *jump_location++ =
+          Bytecodes::ToByte(GetJumpWithConstantOperand(jump_bytecode));
+      *jump_location = static_cast<uint8_t>(entry);
+    } else {
+      UNIMPLEMENTED();
+    }
+  }
+}
+
+
+void BytecodeArrayBuilder::OutputJump(
+    Bytecode jump_bytecode, const ZoneVector<uint8_t>::iterator& jump_target) {
+  DCHECK(IsJumpWithSmi8Operand(jump_bytecode));
+
+  int delta = static_cast<int>(jump_target - bytecodes()->end());
+  if (FitsInImm8Operand(delta)) {
+    Output(jump_bytecode, static_cast<uint8_t>(delta));
+  } else {
+    size_t entry = GetConstantPoolEntry(handle(Smi::FromInt(delta), isolate()));
+    if (FitsInIdxOperand(entry)) {
+      Output(GetJumpWithConstantOperand(jump_bytecode),
+             static_cast<uint8_t>(entry));
+    } else {
+      UNIMPLEMENTED();
+    }
+  }
+}
+
+
+BytecodeArrayBuilder& BytecodeArrayBuilder::Jump(Bytecode jump_bytecode,
+                                                 BytecodeLabel* label) {
+  if (label->is_bound()) {
+    // Label has been bound already so this is a backwards jump.
+    OutputJump(jump_bytecode, bytecodes()->begin() + label->offset());
+  } else {
+    // Label has not yet been bound so this is a forward reference
+    // that will be patched when the label is bound.
+    label->set_referrer(bytecodes()->size());
+    OutputJump(jump_bytecode, bytecodes()->end());
+  }

[rmcilroy, 2015/09/23 14:00:28]

nit - could we fold OutputJump into this function - i.e.:

  int delta;
  if (label->is_bound()) {
    delta = bytecodes()->size() - label->offset();
  } else {
    label->set_referrer(bytecodes()->size());
    delta = 0;
  }
 
  if (FitsInImm8Operand(delta)) {  ...

[oth, 2015/09/24 11:15:27]

Done.

+  return *this;
+}
+
+
+BytecodeArrayBuilder& BytecodeArrayBuilder::Jump(BytecodeLabel* label) {
+  return Jump(Bytecode::kJump, label);
+}
+
+
+BytecodeArrayBuilder& BytecodeArrayBuilder::JumpIfTrue(BytecodeLabel* label) {
+  return Jump(Bytecode::kJumpIfTrue, label);
+}
+
+
+BytecodeArrayBuilder& BytecodeArrayBuilder::JumpIfFalse(BytecodeLabel* label) {
+  return Jump(Bytecode::kJumpIfFalse, label);
+}
+
+
 BytecodeArrayBuilder& BytecodeArrayBuilder::Return() {
   Output(Bytecode::kReturn);
   return *this;
 }
 
 
+BytecodeArrayBuilder& BytecodeArrayBuilder::EnterBlock() { return *this; }
+
+
+BytecodeArrayBuilder& BytecodeArrayBuilder::LeaveBlock() {
+  last_block_end_ = bytecodes()->size();
+  return *this;
+}
+
+
+void BytecodeArrayBuilder::EnsureReturn() {
+  size_t offset = last_block_end_;
+  while (offset < bytecodes()->size()) {

[rmcilroy, 2015/09/23 14:00:28]

As discussed offline, please add a TODO to avoid this while loop when we track
the blocks better.

[oth, 2015/09/24 11:15:27]

Switched to O(1) implementation.

+    Bytecode bytecode = Bytecodes::FromByte(bytecodes()->at(offset));
+    if (bytecode == Bytecode::kReturn) {
+      return;
+    }
+    offset += Bytecodes::Size(bytecode);
+  }
+  LoadUndefined();
+  Return();
+}
+
 BytecodeArrayBuilder& BytecodeArrayBuilder::Call(Register callable,
                                                  Register receiver,
                                                  size_t arg_count) {
-  if (FitsInByteOperand(arg_count)) {
+  if (FitsInIdxOperand(arg_count)) {
     Output(Bytecode::kCall, callable.ToOperand(), receiver.ToOperand(),
            static_cast<uint8_t>(arg_count));
   } else {
@@ -298,42 +502,9 @@ bool BytecodeArrayBuilder::OperandIsValid(Bytecode bytecode, int operand_index,
   return false;
 }
 
-
-void BytecodeArrayBuilder::Output(Bytecode bytecode, uint8_t operand0,
-                                  uint8_t operand1, uint8_t operand2) {
-  DCHECK_EQ(Bytecodes::NumberOfOperands(bytecode), 3);
-  DCHECK(OperandIsValid(bytecode, 0, operand0) &&
-         OperandIsValid(bytecode, 1, operand1) &&
-         OperandIsValid(bytecode, 2, operand2));
-  bytecodes_.push_back(Bytecodes::ToByte(bytecode));
-  bytecodes_.push_back(operand0);
-  bytecodes_.push_back(operand1);
-  bytecodes_.push_back(operand2);
-}
-
-
-void BytecodeArrayBuilder::Output(Bytecode bytecode, uint8_t operand0,
-                                  uint8_t operand1) {
-  DCHECK_EQ(Bytecodes::NumberOfOperands(bytecode), 2);
-  DCHECK(OperandIsValid(bytecode, 0, operand0) &&
-         OperandIsValid(bytecode, 1, operand1));
-  bytecodes_.push_back(Bytecodes::ToByte(bytecode));
-  bytecodes_.push_back(operand0);
-  bytecodes_.push_back(operand1);
-}
-
-
-void BytecodeArrayBuilder::Output(Bytecode bytecode, uint8_t operand0) {
-  DCHECK_EQ(Bytecodes::NumberOfOperands(bytecode), 1);
-  DCHECK(OperandIsValid(bytecode, 0, operand0));
-  bytecodes_.push_back(Bytecodes::ToByte(bytecode));
-  bytecodes_.push_back(operand0);
-}
-
-
-void BytecodeArrayBuilder::Output(Bytecode bytecode) {
-  DCHECK_EQ(Bytecodes::NumberOfOperands(bytecode), 0);
-  bytecodes_.push_back(Bytecodes::ToByte(bytecode));
+bool BytecodeArrayBuilder::LastBytecodeInSameBlock() const {
+  return last_bytecode_start_ < bytecodes()->size() &&
+         last_bytecode_start_ >= last_block_end_;
 }
 
 
@@ -351,24 +522,60 @@ Bytecode BytecodeArrayBuilder::BytecodeForBinaryOperation(Token::Value op) {
     case Token::Value::MOD:
       return Bytecode::kMod;
     default:
-      UNIMPLEMENTED();
+      UNREACHABLE();
       return static_cast<Bytecode>(-1);
   }
 }
 
 
 // static
-bool BytecodeArrayBuilder::FitsInByteOperand(int value) {
+Bytecode BytecodeArrayBuilder::BytecodeForCompareOperation(Token::Value op) {
+  switch (op) {
+    case Token::Value::EQ:
+      return Bytecode::kTestEqual;
+    case Token::Value::NE:
+      return Bytecode::kTestNotEqual;
+    case Token::Value::EQ_STRICT:
+      return Bytecode::kTestEqualStrict;
+    case Token::Value::NE_STRICT:
+      return Bytecode::kTestNotEqualStrict;
+    case Token::Value::LT:
+      return Bytecode::kTestLessThan;
+    case Token::Value::GT:
+      return Bytecode::kTestGreaterThan;
+    case Token::Value::LTE:
+      return Bytecode::kTestLessThanEqual;
+    case Token::Value::GTE:
+      return Bytecode::kTestGreaterThanEqual;
+    case Token::Value::INSTANCEOF:
+      return Bytecode::kTestInstanceOf;
+    case Token::Value::IN:
+      return Bytecode::kTestIn;
+    default:
+      UNREACHABLE();
+      return static_cast<Bytecode>(-1);
+  }
+}
+
+
+// static
+bool BytecodeArrayBuilder::FitsInIdxOperand(int value) {
   return 0 <= value && value <= 255;
 }
 
 
 // static
-bool BytecodeArrayBuilder::FitsInByteOperand(size_t value) {
+bool BytecodeArrayBuilder::FitsInIdxOperand(size_t value) {
   return value <= 255;
 }
 
 
+// static
+bool BytecodeArrayBuilder::FitsInImm8Operand(int value) {
+  return -128 <= value && value < 128;
+}
+
+
 TemporaryRegisterScope::TemporaryRegisterScope(BytecodeArrayBuilder* builder)
     : builder_(builder), count_(0), last_register_index_(-1) {}