[interpreter] Wide register support.

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 {
 
-class BytecodeArrayBuilder::PreviousBytecodeHelper {
+class BytecodeArrayBuilder::PreviousBytecodeHelper BASE_EMBEDDED {
  public:
   explicit PreviousBytecodeHelper(const BytecodeArrayBuilder& array_builder)
       : array_builder_(array_builder),
         previous_bytecode_start_(array_builder_.last_bytecode_start_) {
     // This helper is expected to be instantiated only when the last bytecode is
     // in the same basic block.
     DCHECK(array_builder_.LastBytecodeInSameBlock());
   }
 
   // Returns the previous bytecode in the same basic block.
   MUST_USE_RESULT Bytecode GetBytecode() const {
     DCHECK_EQ(array_builder_.last_bytecode_start_, previous_bytecode_start_);
     return Bytecodes::FromByte(
         array_builder_.bytecodes()->at(previous_bytecode_start_));
   }
 
   // Returns the operand at operand_index for the previous bytecode in the
   // same basic block.
   MUST_USE_RESULT uint32_t GetOperand(int operand_index) const {
     DCHECK_EQ(array_builder_.last_bytecode_start_, previous_bytecode_start_);
     Bytecode bytecode = GetBytecode();
     DCHECK_GE(operand_index, 0);
     DCHECK_LT(operand_index, Bytecodes::NumberOfOperands(bytecode));
     size_t operand_offset =
         previous_bytecode_start_ +
         Bytecodes::GetOperandOffset(bytecode, operand_index);
     OperandSize size = Bytecodes::GetOperandSize(bytecode, operand_index);
     switch (size) {
-      default:
       case OperandSize::kNone:
         UNREACHABLE();
+        break;
       case OperandSize::kByte:
         return static_cast<uint32_t>(
             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);
     }
+    return 0;
   }
 
   Handle<Object> GetConstantForIndexOperand(int operand_index) const {
     return array_builder_.constant_array_builder()->At(
         GetOperand(operand_index));
   }
 
  private:
   const BytecodeArrayBuilder& array_builder_;
   size_t previous_bytecode_start_;
@@ skipping 10 matching lines @@
       constant_array_builder_(isolate, zone),
       handler_table_builder_(isolate, zone),
       last_block_end_(0),
       last_bytecode_start_(~0),
       exit_seen_in_block_(false),
       unbound_jumps_(0),
       parameter_count_(-1),
       local_register_count_(-1),
       context_register_count_(-1),
       temporary_register_count_(0),
-      free_temporaries_(zone) {}
+      free_temporaries_(zone),
+      register_translator_(this) {}
 
 
 BytecodeArrayBuilder::~BytecodeArrayBuilder() { DCHECK_EQ(0, unbound_jumps_); }
 
 
 void BytecodeArrayBuilder::set_locals_count(int number_of_locals) {
   local_register_count_ = number_of_locals;
   DCHECK_LE(context_register_count_, 0);
 }
 
@@ skipping 48 matching lines @@
   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 register_count =
+      fixed_and_temporary_register_count() + translation_register_count();
   int frame_size = register_count * kPointerSize;
   Handle<FixedArray> constant_pool = constant_array_builder()->ToFixedArray();
   Handle<FixedArray> handler_table = handler_table_builder()->ToHandlerTable();
   Handle<BytecodeArray> output = isolate_->factory()->NewBytecodeArray(
       bytecode_size, &bytecodes_.front(), frame_size, parameter_count(),
       constant_pool);
   output->set_handler_table(*handler_table);
   bytecode_generated_ = true;
   return output;
 }
 
 
 template <size_t N>
 void BytecodeArrayBuilder::Output(Bytecode bytecode, uint32_t(&operands)[N]) {
   // Don't output dead code.
   if (exit_seen_in_block_) return;
 
-  DCHECK_EQ(Bytecodes::NumberOfOperands(bytecode), static_cast<int>(N));
+  int operand_count = static_cast<int>(N);
+  DCHECK_EQ(Bytecodes::NumberOfOperands(bytecode), operand_count);
+
+  int register_operand_count = Bytecodes::NumberOfRegisterOperands(bytecode);
+  if (register_operand_count > 0) {
+    register_translator()->TranslateInputRegisters(bytecode, operands,
+                                                   operand_count);
+  }
+
   last_bytecode_start_ = bytecodes()->size();
   bytecodes()->push_back(Bytecodes::ToByte(bytecode));
-  for (int i = 0; i < static_cast<int>(N); i++) {
+  for (int i = 0; i < operand_count; i++) {
     DCHECK(OperandIsValid(bytecode, i, operands[i]));
     switch (Bytecodes::GetOperandSize(bytecode, i)) {
       case OperandSize::kNone:
         UNREACHABLE();
+        break;
       case OperandSize::kByte:
         bytecodes()->push_back(static_cast<uint8_t>(operands[i]));
         break;
       case OperandSize::kShort: {
         uint8_t operand_bytes[2];
         WriteUnalignedUInt16(operand_bytes, operands[i]);
         bytecodes()->insert(bytecodes()->end(), operand_bytes,
                             operand_bytes + 2);
         break;
       }
     }
   }
+
+  if (register_operand_count > 0) {
+    register_translator()->TranslateOutputRegisters();
+  }
 }
 
 
 void BytecodeArrayBuilder::Output(Bytecode bytecode, uint32_t operand0,
                                   uint32_t operand1, uint32_t operand2,
                                   uint32_t operand3) {
   uint32_t operands[] = {operand0, operand1, operand2, operand3};
   Output(bytecode, operands);
 }
 
@@ skipping 155 matching lines @@
   if (!IsRegisterInAccumulator(reg)) {
     Output(Bytecode::kStar, reg.ToRawOperand());
   }
   return *this;
 }
 
 
 BytecodeArrayBuilder& BytecodeArrayBuilder::MoveRegister(Register from,
                                                          Register to) {
   DCHECK(from != to);
-  if (FitsInReg8Operand(to) && FitsInReg8Operand(from)) {
+  if (FitsInReg8Operand(from) && FitsInReg8Operand(to)) {
+    DCHECK(RegisterIsValid(from, OperandType::kReg8) &&
+           RegisterIsValid(to, OperandType::kReg8));

[rmcilroy, 2016/01/26 11:01:45]

Are these DCHECKs needed any longer, since they will be checked in
OperandIsValid?

[oth, 2016/01/26 13:39:56]

Done.

     Output(Bytecode::kMov, from.ToRawOperand(), to.ToRawOperand());
-  } else if (FitsInReg16Operand(to) && FitsInReg16Operand(from)) {
+  } else if (FitsInReg16Operand(from) && FitsInReg16Operand(to)) {
+    DCHECK(RegisterIsValid(from, OperandType::kReg16) &&
+           RegisterIsValid(to, OperandType::kReg16));
     Output(Bytecode::kMovWide, from.ToRawOperand(), to.ToRawOperand());
   } else {
     UNIMPLEMENTED();
   }
   return *this;
 }
 
 
+void BytecodeArrayBuilder::MoveRegisterUntranslated(Register from,
+                                                    Register to) {
+  // Move bytecodes modify the stack. Checking validity is essential.

[rmcilroy, 2016/01/26 11:01:45]

nit- "Move bytecodes modify the stack, so it is essential that we check the
validity of the operation to ensure we don't corrupt the stack." or similar

[oth, 2016/01/26 13:39:57]

Done.

+  if (FitsInReg8OperandUntranslated(from)) {
+    CHECK(RegisterIsValid(from, OperandType::kReg8) &&
+          RegisterIsValid(to, OperandType::kReg16));
+  } else if (FitsInReg8OperandUntranslated(to)) {
+    CHECK(RegisterIsValid(from, OperandType::kReg16) &&
+          RegisterIsValid(to, OperandType::kReg8));
+  } else {
+    UNIMPLEMENTED();
+  }
+  Output(Bytecode::kMovWide, from.ToRawOperand(), to.ToRawOperand());
+}
+
+
+bool BytecodeArrayBuilder::RegisterOperandIsMovable(Bytecode bytecode,
+                                                    int operand_index) {
+  // By design, we only support moving individual registers. There
+  // should be wide variants of such bytecodes instead to avoid the
+  // need for a large translation window.
+  OperandType operand_type = Bytecodes::GetOperandType(bytecode, operand_index);
+  if (operand_type == OperandType::kReg8 ||
+      operand_type == OperandType::kReg16) {
+    if (operand_index == Bytecodes::NumberOfOperands(bytecode) - 1) {
+      return true;
+    }
+    OperandType next_operand_type =
+        Bytecodes::GetOperandType(bytecode, operand_index + 1);
+    return (next_operand_type != OperandType::kRegCount8 &&
+            next_operand_type != OperandType::kRegCount16);
+  } else {
+    // TODO(oth): In the next CL in the series, this is possible:
+    // DCHECK(Bytecodes::IsRegisterOperand(bytecode, operand_index));

[rmcilroy, 2016/01/26 11:01:45]

Could we do this bytecode right at the top of the function (and avoid the else
branch, just return false at the end of function)?

[oth, 2016/01/26 13:39:56]

Re-ordered. Test not necessary here, comment removed.

+    return false;
+  }
+}
+
 BytecodeArrayBuilder& BytecodeArrayBuilder::LoadGlobal(
     const Handle<String> name, int feedback_slot, LanguageMode language_mode,
     TypeofMode typeof_mode) {
   // TODO(rmcilroy): Potentially store language and typeof information in an
   // operand rather than having extra bytecodes.
   Bytecode bytecode = BytecodeForLoadGlobal(language_mode, typeof_mode);
   size_t name_index = GetConstantPoolEntry(name);
   if (FitsInIdx8Operand(name_index) && FitsInIdx8Operand(feedback_slot)) {
     Output(bytecode, static_cast<uint8_t>(name_index),
            static_cast<uint8_t>(feedback_slot));
@@ skipping 691 matching lines @@
 }
 
 
 BytecodeArrayBuilder& BytecodeArrayBuilder::New(Register constructor,
                                                 Register first_arg,
                                                 size_t arg_count) {
   if (!first_arg.is_valid()) {
     DCHECK_EQ(0u, arg_count);
     first_arg = Register(0);
   }
-
   if (FitsInReg8Operand(constructor) && FitsInReg8Operand(first_arg) &&
       FitsInIdx8Operand(arg_count)) {
     Output(Bytecode::kNew, constructor.ToRawOperand(), first_arg.ToRawOperand(),
            static_cast<uint8_t>(arg_count));
   } else if (FitsInReg16Operand(constructor) && FitsInReg16Operand(first_arg) &&
              FitsInIdx16Operand(arg_count)) {
     Output(Bytecode::kNewWide, constructor.ToRawOperand(),
            first_arg.ToRawOperand(), static_cast<uint16_t>(arg_count));
   } else {
     UNIMPLEMENTED();
@@ skipping 77 matching lines @@
   Output(Bytecode::kDeleteLookupSlot);
   return *this;
 }
 
 
 size_t BytecodeArrayBuilder::GetConstantPoolEntry(Handle<Object> object) {
   return constant_array_builder()->Insert(object);
 }
 
 
+void BytecodeArrayBuilder::ForgeTemporaryRegister() {
+  temporary_register_count_++;
+}
+
+
 int BytecodeArrayBuilder::BorrowTemporaryRegister() {
   if (free_temporaries_.empty()) {
-    temporary_register_count_ += 1;
+    ForgeTemporaryRegister();
     return last_temporary_register().index();
   } else {
     auto pos = free_temporaries_.begin();
     int retval = *pos;
     free_temporaries_.erase(pos);
     return retval;
   }
 }
 
 
 int BytecodeArrayBuilder::BorrowTemporaryRegisterNotInRange(int start_index,
                                                             int end_index) {
   auto index = free_temporaries_.lower_bound(start_index);
   if (index == free_temporaries_.begin()) {
     // If start_index is the first free register, check for a register
     // greater than end_index.
     index = free_temporaries_.upper_bound(end_index);
     if (index == free_temporaries_.end()) {
-      temporary_register_count_ += 1;
+      ForgeTemporaryRegister();
       return last_temporary_register().index();
     }
   } else {
     // If there is a free register < start_index
     index--;
   }
 
   int retval = *index;
   free_temporaries_.erase(index);
   return retval;
@@ skipping 11 matching lines @@
   free_temporaries_.insert(reg_index);
 }
 
 
 int BytecodeArrayBuilder::PrepareForConsecutiveTemporaryRegisters(
     size_t count) {
   if (count == 0) {
     return -1;
   }
 
+  // TODO(oth): replace use of set<> here for free_temporaries with a
+  // more efficient structure. And/or partition into two searches -
+  // one before the translation window and one after.
+
+  // A run will require at least |count| free temporaries.
+  while (free_temporaries_.size() < count) {
+    ForgeTemporaryRegister();
+    free_temporaries_.insert(last_temporary_register().index());
+  }
+
   // Search within existing temporaries for a run.
   auto start = free_temporaries_.begin();
   size_t run_length = 0;
   for (auto run_end = start; run_end != free_temporaries_.end(); run_end++) {
-    if (*run_end != *start + static_cast<int>(run_length)) {
+    int expected = *start + static_cast<int>(run_length);
+    if (*run_end != expected) {
       start = run_end;
       run_length = 0;
     }
+    Register reg_start(*start);
+    Register reg_expected(expected);
+    if (RegisterTranslator::DistanceToTranslationWindow(reg_start) > 0 &&
+        RegisterTranslator::DistanceToTranslationWindow(reg_expected) <= 0) {
+      // Run straddles the lower edge of the translation window. Registers
+      // after the start of this boundary are displaced by the register
+      // translator to provide a hole for translation. Runs either side
+      // of the boundary are fine.
+      start = run_end;
+      run_length = 0;
+    }
     if (++run_length == count) {
       return *start;
     }
   }
 
   // Continue run if possible across existing last temporary.
   if (temporary_register_count_ > 0 &&
       (start == free_temporaries_.end() ||
        *start + static_cast<int>(run_length) !=
            last_temporary_register().index() + 1)) {
     run_length = 0;
   }
 
+  // Pad temporaries if extended run would cross translation boundary.
+  Register reg_first(*start);
+  Register reg_last(*start + static_cast<int>(count) - 1);
+  DCHECK_GT(RegisterTranslator::DistanceToTranslationWindow(reg_first),
+            RegisterTranslator::DistanceToTranslationWindow(reg_last));
+  while (RegisterTranslator::DistanceToTranslationWindow(reg_first) > 0 &&
+         RegisterTranslator::DistanceToTranslationWindow(reg_last) <= 0) {
+    ForgeTemporaryRegister();
+    free_temporaries_.insert(last_temporary_register().index());
+    start = --free_temporaries_.end();
+    reg_first = Register(*start);
+    reg_last = Register(*start + static_cast<int>(count) - 1);
+    run_length = 0;
+  }
+
   // Ensure enough registers for run.
   while (run_length++ < count) {
-    temporary_register_count_++;
+    ForgeTemporaryRegister();
     free_temporaries_.insert(last_temporary_register().index());
   }
-  return last_temporary_register().index() - static_cast<int>(count) + 1;
+
+  int run_start =
+      last_temporary_register().index() - static_cast<int>(count) + 1;
+  DCHECK(RegisterTranslator::DistanceToTranslationWindow(Register(run_start)) <=
+             0 ||
+         RegisterTranslator::DistanceToTranslationWindow(
+             Register(run_start + static_cast<int>(count) - 1)) > 0);
+  return run_start;
 }
 
 
 bool BytecodeArrayBuilder::TemporaryRegisterIsLive(Register reg) const {
   if (temporary_register_count_ > 0) {
     DCHECK(reg.index() >= first_temporary_register().index() &&
            reg.index() <= last_temporary_register().index());
     return free_temporaries_.find(reg.index()) == free_temporaries_.end();
   } else {
     return false;
   }
 }
 
 
 bool BytecodeArrayBuilder::OperandIsValid(Bytecode bytecode, int operand_index,
                                           uint32_t operand_value) const {
   OperandType operand_type = Bytecodes::GetOperandType(bytecode, operand_index);
   switch (operand_type) {
     case OperandType::kNone:
       return false;

[rmcilroy, 2016/01/26 11:01:45]

The DCHECK below looks like dead code?

[oth, 2016/01/26 13:39:57]

Done. Rebase or re-org snafu. Looks like it once belonged in a case below.

-    case OperandType::kRegCount16:
+      DCHECK(operand_index != 0);

[rmcilroy, 2016/01/26 11:01:45]

Dead code?

[oth, 2016/01/26 13:39:56]

Assuming this is flagging the same dead code as the previous comment.

[rmcilroy, 2016/01/26 14:08:07]

Yes it was. Weirdly the tool told me it failed to create this comment multiple
times, so I created the one above :).

+    case OperandType::kRegCount16: {
+      // Expect kRegCount16 is part of a range previous operand is a
+      // valid operand to start a range.
+      if (operand_index > 0) {

[rmcilroy, 2016/01/26 11:01:45]

Just DCHECK operand_index > 0 here (and below) ? 

[oth, 2016/01/26 13:39:57]

Leaving as-is. This method should be consistent and return true or false for all
validity conditions. It's use is wrapped by a DCHECK.

[rmcilroy, 2016/01/26 14:08:07]

Acknowledged.

+        OperandType previous_operand_type =
+            Bytecodes::GetOperandType(bytecode, operand_index - 1);
+        return ((previous_operand_type == OperandType::kMaybeReg16 ||
+                 previous_operand_type == OperandType::kReg16) &&
+                static_cast<uint16_t>(operand_value) == operand_value);
+      } else {
+        return false;
+      }
+    }
+    case OperandType::kRegCount8: {
+      // Expect kRegCount8 is part of a range previous operand is a
+      // valid operand to start a range.
+      if (operand_index > 0) {
+        OperandType previous_operand_type =
+            Bytecodes::GetOperandType(bytecode, operand_index - 1);
+        return ((previous_operand_type == OperandType::kMaybeReg8 ||
+                 previous_operand_type == OperandType::kReg8 ||
+                 previous_operand_type == OperandType::kMaybeReg16 ||
+                 previous_operand_type == OperandType::kReg16) &&

[rmcilroy, 2016/01/26 11:01:45]

Should the kReg16 be valid here? Maybe kRegCount8 should only be valid with
kReg8 ?

[oth, 2016/01/26 13:39:56]

Removed kReg16.

CallRuntimeWide and CallRuntimeForPairWide have MaybeReg16 and a RegCount8.

+                static_cast<uint8_t>(operand_value) == operand_value);
+      } else {
+        return false;
+      }
+    }
     case OperandType::kIdx16:
       return static_cast<uint16_t>(operand_value) == operand_value;
-    case OperandType::kRegCount8:
     case OperandType::kImm8:
     case OperandType::kIdx8:
       return static_cast<uint8_t>(operand_value) == operand_value;
     case OperandType::kMaybeReg8:
       if (operand_value == 0) {
         return true;
       }
     // Fall-through to kReg8 case.
     case OperandType::kReg8:
       return RegisterIsValid(Register::FromRawOperand(operand_value),
@@ skipping 24 matching lines @@
       return RegisterIsValid(reg, operand_type);
     }
   }
   UNREACHABLE();
   return false;
 }
 
 
 bool BytecodeArrayBuilder::RegisterIsValid(Register reg,
                                            OperandType reg_type) const {
+  if (!reg.is_valid()) {
+    return false;
+  }
+
   switch (Bytecodes::SizeOfOperand(reg_type)) {
     case OperandSize::kByte:
-      if (!FitsInReg8Operand(reg)) { return false; }
+      if (!FitsInReg8OperandUntranslated(reg)) {
+        return false;
+      }
       break;
     case OperandSize::kShort:
-      if (!FitsInReg16Operand(reg)) { return false; }
+      if (!FitsInReg16OperandUntranslated(reg)) {
+        return false;
+      }
       break;
     case OperandSize::kNone:
       UNREACHABLE();
       return false;
   }
 
   if (reg.is_current_context() || reg.is_function_closure() ||
       reg.is_new_target()) {
     return true;
   } else if (reg.is_parameter()) {
-    int parameter_index = reg.ToParameterIndex(parameter_count_);
-    return parameter_index >= 0 && parameter_index < parameter_count_;
-  } else if (reg.index() < fixed_register_count()) {
-    return true;
+    int parameter_index = reg.ToParameterIndex(parameter_count());
+    return parameter_index >= 0 && parameter_index < parameter_count();
+  } else if (RegisterTranslator::InTranslationWindow(reg)) {
+    return translation_register_count() > 0;
   } else {
-    return TemporaryRegisterIsLive(reg);
+    reg = RegisterTranslator::UntranslateRegister(reg);
+    if (reg.index() < fixed_register_count()) {
+      return true;
+    } else {
+      return TemporaryRegisterIsLive(reg);
+    }
   }
 }
 
 
 bool BytecodeArrayBuilder::LastBytecodeInSameBlock() const {
   return last_bytecode_start_ < bytecodes()->size() &&
          last_bytecode_start_ >= last_block_end_;
 }
 
 
 bool BytecodeArrayBuilder::IsRegisterInAccumulator(Register reg) {
   if (LastBytecodeInSameBlock()) {
     PreviousBytecodeHelper previous_bytecode(*this);
     Bytecode bytecode = previous_bytecode.GetBytecode();
-    if ((bytecode == Bytecode::kLdar || bytecode == Bytecode::kStar) &&
-        (reg == Register::FromOperand(previous_bytecode.GetOperand(0)))) {
-      return true;
+    if (bytecode == Bytecode::kLdar || bytecode == Bytecode::kStar) {
+      Register previous_reg =
+          Register::FromOperand(previous_bytecode.GetOperand(0));
+      return previous_reg == reg;
     }
   }
   return false;
 }
 
 
 // static
 Bytecode BytecodeArrayBuilder::BytecodeForBinaryOperation(Token::Value op) {
   switch (op) {
     case Token::Value::ADD:
@@ skipping 292 matching lines @@
 
 
 // static
 bool BytecodeArrayBuilder::FitsInIdx16Operand(size_t value) {
   return value <= static_cast<size_t>(kMaxUInt16);
 }
 
 
 // static
 bool BytecodeArrayBuilder::FitsInReg8Operand(Register value) {
-  return kMinInt8 <= value.index() && value.index() <= kMaxInt8;
+  return RegisterTranslator::FitsInReg8Operand(value);
+}
+
+
+// static
+bool BytecodeArrayBuilder::FitsInReg8OperandUntranslated(Register value) {
+  return value.is_byte_operand();
 }
 
 
 // static
 bool BytecodeArrayBuilder::FitsInReg16Operand(Register value) {
-  return kMinInt16 <= value.index() && value.index() <= kMaxInt16;
+  return RegisterTranslator::FitsInReg16Operand(value);
+}
+
+
+// static
+bool BytecodeArrayBuilder::FitsInReg16OperandUntranslated(Register value) {
+  return value.is_short_operand();
 }
 
 }  // namespace interpreter
 }  // namespace internal
 }  // namespace v8