[Interpreter] Add support for jumps using constants with wide operands.

src/interpreter/bytecode-array-builder.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/interpreter/bytecode-array-builder.h"
 
 namespace v8 {
 namespace internal {
 namespace interpreter {
 
@@ skipping 34 matching lines @@
             array_builder_.bytecodes()->at(operand_offset));
       case OperandSize::kShort:
         uint16_t operand =
             (array_builder_.bytecodes()->at(operand_offset) << 8) +
             array_builder_.bytecodes()->at(operand_offset + 1);
         return static_cast<uint32_t>(operand);
     }
   }
 
   Handle<Object> GetConstantForIndexOperand(int operand_index) const {
-    return array_builder_.constants_.at(GetOperand(operand_index));
+    return array_builder_.constant_array_builder()->at(
+        GetOperand(operand_index));
   }
 
  private:
   const BytecodeArrayBuilder& array_builder_;
   size_t previous_bytecode_start_;
 
   DISALLOW_COPY_AND_ASSIGN(PreviousBytecodeHelper);
 };
 
 
 BytecodeArrayBuilder::BytecodeArrayBuilder(Isolate* isolate, Zone* zone)
     : isolate_(isolate),
       zone_(zone),
       bytecodes_(zone),
       bytecode_generated_(false),
+      constant_array_builder_(isolate, zone),
       last_block_end_(0),
       last_bytecode_start_(~0),
       exit_seen_in_block_(false),
       unbound_jumps_(0),
-      constants_map_(isolate->heap(), zone),
-      constants_(zone),
       parameter_count_(-1),
       local_register_count_(-1),
       context_register_count_(-1),
       temporary_register_count_(0),
       free_temporaries_(zone) {}
 
 
 BytecodeArrayBuilder::~BytecodeArrayBuilder() { DCHECK_EQ(0, unbound_jumps_); }
 
 
@@ skipping 50 matching lines @@
 
 
 bool BytecodeArrayBuilder::RegisterIsTemporary(Register reg) const {
   return temporary_register_count_ > 0 && first_temporary_register() <= reg &&
          reg <= last_temporary_register();
 }
 
 
 Handle<BytecodeArray> BytecodeArrayBuilder::ToBytecodeArray() {
   DCHECK_EQ(bytecode_generated_, false);
-
   EnsureReturn();
 
   int bytecode_size = static_cast<int>(bytecodes_.size());
   int register_count = fixed_register_count() + temporary_register_count_;
   int frame_size = register_count * kPointerSize;
-
   Factory* factory = isolate_->factory();
-  int constants_count = static_cast<int>(constants_.size());
   Handle<FixedArray> constant_pool =
-      factory->NewFixedArray(constants_count, TENURED);
-  for (int i = 0; i < constants_count; i++) {
-    constant_pool->set(i, *constants_[i]);
-  }
-
+      constant_array_builder()->ToFixedArray(factory, TENURED);
   Handle<BytecodeArray> output =
       factory->NewBytecodeArray(bytecode_size, &bytecodes_.front(), frame_size,
                                 parameter_count(), constant_pool);
   bytecode_generated_ = true;
   return output;
 }
 
 
 template <size_t N>
 void BytecodeArrayBuilder::Output(Bytecode bytecode, uint32_t(&operands)[N]) {
@@ skipping 579 matching lines @@
       return Bytecode::kJumpIfNullConstant;
     case Bytecode::kJumpIfUndefined:
       return Bytecode::kJumpIfUndefinedConstant;
     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);
-  int delta = static_cast<int>(jump_target - jump_location);
-
-  DCHECK(Bytecodes::IsJump(jump_bytecode));
-  DCHECK_EQ(Bytecodes::Size(jump_bytecode), 2);
-  DCHECK_NE(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()));
-    if (FitsInIdx8Operand(entry)) {
-      jump_bytecode = GetJumpWithConstantOperand(jump_bytecode);
-      *jump_location++ = Bytecodes::ToByte(jump_bytecode);
-      *jump_location = static_cast<uint8_t>(entry);
-    } else {
-      // TODO(oth): OutputJump should reserve a constant pool entry
-      // when jump is written. The reservation should be used here if
-      // needed, or cancelled if not. This is due to the patch needing
-      // to match the size of the code it's replacing. In future,
-      // there will probably be a jump with 32-bit operand for cases
-      // when constant pool is full, but that needs to be emitted in
-      // OutputJump too.
-      UNIMPLEMENTED();
-    }
+// static
+Bytecode BytecodeArrayBuilder::GetJumpWithConstantWideOperand(
+    Bytecode jump_bytecode) {
+  switch (jump_bytecode) {
+    case Bytecode::kJump:
+      return Bytecode::kJumpConstantWide;
+    case Bytecode::kJumpIfTrue:
+      return Bytecode::kJumpIfTrueConstantWide;
+    case Bytecode::kJumpIfFalse:
+      return Bytecode::kJumpIfFalseConstantWide;
+    case Bytecode::kJumpIfToBooleanTrue:
+      return Bytecode::kJumpIfToBooleanTrueConstantWide;
+    case Bytecode::kJumpIfToBooleanFalse:
+      return Bytecode::kJumpIfToBooleanFalseConstantWide;
+    case Bytecode::kJumpIfNull:
+      return Bytecode::kJumpIfNullConstantWide;
+    case Bytecode::kJumpIfUndefined:
+      return Bytecode::kJumpIfUndefinedConstantWide;
+    default:
+      UNREACHABLE();
+      return Bytecode::kJumpConstantWide;

[rmcilroy, 2016/01/04 17:05:48]

nit - return static_cast<Bytecode>(-1) (and above)

[oth, 2016/01/05 09:30:08]

Done.

   }
-  unbound_jumps_--;
 }
 
 
 // static
 Bytecode BytecodeArrayBuilder::GetJumpWithToBoolean(Bytecode jump_bytecode) {
   switch (jump_bytecode) {
     case Bytecode::kJump:
     case Bytecode::kJumpIfNull:
     case Bytecode::kJumpIfUndefined:
       return jump_bytecode;
     case Bytecode::kJumpIfTrue:
       return Bytecode::kJumpIfToBooleanTrue;
     case Bytecode::kJumpIfFalse:
       return Bytecode::kJumpIfToBooleanFalse;
     default:
       UNREACHABLE();
   }
   return static_cast<Bytecode>(-1);
 }
 
 
+void BytecodeArrayBuilder::PatchJump(
+    const ZoneVector<uint8_t>::iterator& jump_target,
+    const ZoneVector<uint8_t>::iterator& jump_location) {
+  int delta = static_cast<int>(jump_target - jump_location);
+  Bytecode jump_bytecode = Bytecodes::FromByte(*jump_location);
+  auto operand_location = jump_location + 1;

[rmcilroy, 2016/01/04 17:05:48]

Don't use auto here (it's not immediately obvious what the type is).

[oth, 2016/01/05 09:30:08]

Done.

+  auto reservation_token =
+      static_cast<ConstantArrayBuilder::ReservationToken>(*operand_location);

[rmcilroy, 2016/01/04 17:05:48]

Could we wrap up this ReservationToken getter stuff in
ConstantArrayBuilder::GetToken(const ZoneVector<uint8_t>::iterator&
jump_location)

[oth, 2016/01/05 09:30:08]

Simplified the code path.

+  if (ConstantArrayBuilder::ReservationToken::kIdx8 == reservation_token) {

[rmcilroy, 2016/01/04 17:05:48]

nit - switch on ReservationToken type

[oth, 2016/01/05 09:30:08]

Done. Moved the switch bodies into separate functions.

+    DCHECK(Bytecodes::IsJumpImmediate(jump_bytecode));
+    if (FitsInImm8Operand(delta)) {
+      // The jump fits with the range of an Imm8 operand, so cancel
+      // the reservation and jump directly.
+      constant_array_builder()->DiscardReservedEntry(reservation_token);
+      *operand_location = static_cast<uint8_t>(delta);
+    } else {
+      // The jump does not fit in range of an Imm8 operand, so commit
+      // reservation and update the jump instruction and operand.
+      size_t entry = constant_array_builder()->CommitReservedEntry(
+          reservation_token, handle(Smi::FromInt(delta), isolate()));
+      DCHECK(FitsInIdx8Operand(entry));
+      jump_bytecode = GetJumpWithConstantOperand(jump_bytecode);
+      *jump_location = Bytecodes::ToByte(jump_bytecode);
+      *operand_location = static_cast<uint8_t>(entry);
+    }
+  } else {
+    // A reservation for an entry in the constant array with a 16-bit index.
+    DCHECK(ConstantArrayBuilder::ReservationToken::kIdx16 == reservation_token);
+    DCHECK(Bytecodes::IsJumpConstantWide(jump_bytecode));
+    size_t entry = constant_array_builder()->CommitReservedEntry(
+        reservation_token, handle(Smi::FromInt(delta), isolate()));
+    DCHECK(FitsInIdx16Operand(entry));
+    uint8_t operand_bytes[2];
+    WriteUnalignedUInt16(operand_bytes, static_cast<uint16_t>(entry));
+    *operand_location++ = operand_bytes[0];
+    *operand_location = operand_bytes[1];
+  }
+  unbound_jumps_--;
+}
+
+
 BytecodeArrayBuilder& BytecodeArrayBuilder::OutputJump(Bytecode jump_bytecode,
                                                        BytecodeLabel* label) {
   // Don't emit dead code.
   if (exit_seen_in_block_) return *this;
 
   // Check if the value in accumulator is boolean, if not choose an
   // appropriate JumpIfToBoolean bytecode.
   if (NeedToBooleanCast()) {
     jump_bytecode = GetJumpWithToBoolean(jump_bytecode);
   }
 
-  int delta;
   if (label->is_bound()) {
     // Label has been bound already so this is a backwards jump.
     CHECK_GE(bytecodes()->size(), label->offset());
     CHECK_LE(bytecodes()->size(), static_cast<size_t>(kMaxInt));
     size_t abs_delta = bytecodes()->size() - label->offset();
-    delta = -static_cast<int>(abs_delta);
+    int delta = -static_cast<int>(abs_delta);
+
+    if (FitsInImm8Operand(delta)) {
+      Output(jump_bytecode, static_cast<uint8_t>(delta));
+    } else {
+      size_t entry =
+          GetConstantPoolEntry(handle(Smi::FromInt(delta), isolate()));
+      if (FitsInIdx8Operand(entry)) {
+        Output(GetJumpWithConstantOperand(jump_bytecode),
+               static_cast<uint8_t>(entry));
+      } else if (FitsInIdx16Operand(entry)) {
+        Output(GetJumpWithConstantWideOperand(jump_bytecode),
+               static_cast<uint16_t>(entry));
+      } else {
+        UNREACHABLE();
+      }
+    }
   } 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());
-    delta = 0;
     unbound_jumps_++;
+    auto token = constant_array_builder()->CreateReservedEntry();

[rmcilroy, 2016/01/04 17:05:48]

don't use auto here (not immediately clear what the type is).

[oth, 2016/01/05 09:30:08]

Done.

+    switch (token) {

[rmcilroy, 2016/01/04 17:05:48]

Please add a comment mentioning what you are doing here (storing the token in
the operand).

[oth, 2016/01/05 09:30:08]

Removed. The token was supposed to be symbolic - make a reservation, get a
token, cash it in. However, there are only two token values and on reflection I
don't think it serves any practical purpose.

+      case ConstantArrayBuilder::ReservationToken::kIdx8: {
+        Output(jump_bytecode, static_cast<uint8_t>(token));
+        break;
+      }
+      case ConstantArrayBuilder::ReservationToken::kIdx16: {
+        uint16_t target = static_cast<uint16_t>(token);
+        target |= target << 8;

[rmcilroy, 2016/01/04 17:05:48]

nit - I assume this is for big endian support? Please add a comment

[oth, 2016/01/05 09:30:08]

Yes. No longer exists.

+        Output(GetJumpWithConstantWideOperand(jump_bytecode), target);
+        break;
+      }
+    }
   }
 
-  if (FitsInImm8Operand(delta)) {
-    Output(jump_bytecode, static_cast<uint8_t>(delta));
-  } else {
-    size_t entry = GetConstantPoolEntry(handle(Smi::FromInt(delta), isolate()));
-    if (FitsInIdx8Operand(entry)) {
-      Output(GetJumpWithConstantOperand(jump_bytecode),
-             static_cast<uint8_t>(entry));
-    } else {
-      UNIMPLEMENTED();
-    }
-  }
   LeaveBasicBlock();
   return *this;
 }
 
 
 BytecodeArrayBuilder& BytecodeArrayBuilder::Jump(BytecodeLabel* label) {
   return OutputJump(Bytecode::kJump, label);
 }
 
 
@@ skipping 143 matching lines @@
 }
 
 
 BytecodeArrayBuilder& BytecodeArrayBuilder::DeleteLookupSlot() {
   Output(Bytecode::kDeleteLookupSlot);
   return *this;
 }
 
 
 size_t BytecodeArrayBuilder::GetConstantPoolEntry(Handle<Object> object) {
-  // These constants shouldn't be added to the constant pool, the should use
-  // specialzed bytecodes instead.
-  DCHECK(!object.is_identical_to(isolate_->factory()->undefined_value()));
-  DCHECK(!object.is_identical_to(isolate_->factory()->null_value()));
-  DCHECK(!object.is_identical_to(isolate_->factory()->the_hole_value()));
-  DCHECK(!object.is_identical_to(isolate_->factory()->true_value()));
-  DCHECK(!object.is_identical_to(isolate_->factory()->false_value()));
-
-  size_t* entry = constants_map_.Find(object);
-  if (!entry) {
-    entry = constants_map_.Get(object);
-    *entry = constants_.size();
-    constants_.push_back(object);
-  }
-  DCHECK(constants_[*entry].is_identical_to(object));
-  return *entry;
+  return constant_array_builder()->Insert(object);
 }
 
 
 int BytecodeArrayBuilder::BorrowTemporaryRegister() {
   if (free_temporaries_.empty()) {
     temporary_register_count_ += 1;
     return last_temporary_register().index();
   } else {
     auto pos = free_temporaries_.begin();
     int retval = *pos;
@@ skipping 502 matching lines @@
   DCHECK_GT(next_consecutive_count_, 0);
   builder_->BorrowConsecutiveTemporaryRegister(next_consecutive_register_);
   allocated_.push_back(next_consecutive_register_);
   next_consecutive_count_--;
   return Register(next_consecutive_register_++);
 }
 
 }  // namespace interpreter
 }  // namespace internal
 }  // namespace v8