[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);
   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 574 matching lines @@
     case Bytecode::kJumpIfToBooleanTrue:
       return Bytecode::kJumpIfToBooleanTrueConstant;
     case Bytecode::kJumpIfToBooleanFalse:
       return Bytecode::kJumpIfToBooleanFalseConstant;
     case Bytecode::kJumpIfNull:
       return Bytecode::kJumpIfNullConstant;
     case Bytecode::kJumpIfUndefined:
       return Bytecode::kJumpIfUndefinedConstant;
     default:
       UNREACHABLE();
-      return Bytecode::kJumpConstant;
+      return static_cast<Bytecode>(-1);
   }
 }
 
 
-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 static_cast<Bytecode>(-1);
   }
-  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::PatchIndirectJumpWith8BitOperand(
+    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);
+  ZoneVector<uint8_t>::iterator operand_location = jump_location + 1;
+  if (FitsInImm8Operand(delta)) {
+    // The jump fits within the range of an Imm8 operand, so cancel
+    // the reservation and jump directly.
+    constant_array_builder()->DiscardReservedEntry(OperandSize::kByte);

[rmcilroy, 2016/01/05 13:46:10]

Could you add a DCHECK that the bytecode is the expected non-constant pool type
jump.

[oth, 2016/01/05 18:31:59]

Done + added DCHECK that the operand is zero in both the 8-bit and 16-bit patch
routines.

+    *operand_location = static_cast<uint8_t>(delta);
+  } else {
+    // The jump does not fit within the range of an Imm8 operand, so
+    // commit reservation putting the offset into the constant pool,
+    // and update the jump instruction and operand.
+    size_t entry = constant_array_builder()->CommitReservedEntry(
+        OperandSize::kByte, 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);
+  }
+}
+
+
+void BytecodeArrayBuilder::PatchIndirectJumpWith16BitOperand(
+    const ZoneVector<uint8_t>::iterator& jump_target,
+    const ZoneVector<uint8_t>::iterator& jump_location) {
+  DCHECK(Bytecodes::IsJumpConstantWide(Bytecodes::FromByte(*jump_location)));
+  int delta = static_cast<int>(jump_target - jump_location);
+  ZoneVector<uint8_t>::iterator operand_location = jump_location + 1;
+  size_t entry = constant_array_builder()->CommitReservedEntry(
+      OperandSize::kShort, 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];
+}
+
+
+void BytecodeArrayBuilder::PatchJump(
+    const ZoneVector<uint8_t>::iterator& jump_target,
+    const ZoneVector<uint8_t>::iterator& jump_location) {
+  Bytecode jump_bytecode = Bytecodes::FromByte(*jump_location);

[rmcilroy, 2016/01/05 13:46:10]

nit - you could calculate delta here and pass it to the PatchIndirect..
functions instead of jump_target.

[oth, 2016/01/05 18:31:59]

Done.

+  DCHECK(Bytecodes::IsJump(jump_bytecode));
+  switch (Bytecodes::GetOperandSize(jump_bytecode, 0)) {
+    case OperandSize::kByte:
+      PatchIndirectJumpWith8BitOperand(jump_target, jump_location);
+      break;
+    case OperandSize::kShort:
+      PatchIndirectJumpWith16BitOperand(jump_target, jump_location);
+      break;
+    case OperandSize::kNone:
+      UNREACHABLE();
+  }
+  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.
+    // The label has not yet been bound so this is a forward reference
+    // that will be patched when the label is bound. We create a
+    // reservation in the constant pool so the jump can be patched
+    // when the label is bound. The reservation means the maximum size
+    // of the operand for the constant is known and the jump can
+    // be emitted into the bytecode stream with space for the operand.
     label->set_referrer(bytecodes()->size());
-    delta = 0;
     unbound_jumps_++;
-  }
-
-  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();
+    OperandSize reserved_operand_size =
+        constant_array_builder()->CreateReservedEntry();
+    switch (reserved_operand_size) {
+      case OperandSize::kByte:
+        Output(jump_bytecode, 0);
+        break;
+      case OperandSize::kShort:
+        Output(GetJumpWithConstantWideOperand(jump_bytecode), 0);
+        break;
+      case OperandSize::kNone:
+        UNREACHABLE();
     }
   }
   LeaveBasicBlock();
   return *this;
 }
 
 
 BytecodeArrayBuilder& BytecodeArrayBuilder::Jump(BytecodeLabel* label) {
   return OutputJump(Bytecode::kJump, label);
 }
@@ skipping 145 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