[Interpreter] Reduce temporary register usage in generated bytecode.

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 {
 
 BytecodeArrayBuilder::BytecodeArrayBuilder(Isolate* isolate, Zone* zone)
     : isolate_(isolate),
       zone_(zone),
       bytecodes_(zone),
       bytecode_generated_(false),
       last_block_end_(0),
       last_bytecode_start_(~0),
       return_seen_in_block_(false),
       constants_map_(isolate->heap(), zone),
       constants_(zone),
       parameter_count_(-1),
       local_register_count_(-1),
       context_register_count_(-1),
       temporary_register_count_(0),
-      temporary_register_next_(0) {}
+      free_temporaries_(zone) {}
 
 
 void BytecodeArrayBuilder::set_locals_count(int number_of_locals) {
   local_register_count_ = number_of_locals;
   DCHECK_LE(context_register_count_, 0);
-  temporary_register_next_ = local_register_count_;
 }
 
 
 void BytecodeArrayBuilder::set_parameter_count(int number_of_parameters) {
   parameter_count_ = number_of_parameters;
 }
 
 
 void BytecodeArrayBuilder::set_context_count(int number_of_contexts) {
   context_register_count_ = number_of_contexts;
   DCHECK_GE(local_register_count_, 0);
-  temporary_register_next_ = local_register_count_ + context_register_count_;
 }
 
 
 Register BytecodeArrayBuilder::first_context_register() const {
   DCHECK_GT(context_register_count_, 0);
   return Register(local_register_count_);
 }
 
 
 Register BytecodeArrayBuilder::last_context_register() const {
   DCHECK_GT(context_register_count_, 0);
   return Register(local_register_count_ + context_register_count_ - 1);
 }
 
 
+Register BytecodeArrayBuilder::first_temporary_register() const {
+  DCHECK_GT(temporary_register_count_, 0);
+  return Register(fixed_register_count());
+}
+
+
+Register BytecodeArrayBuilder::last_temporary_register() const {
+  DCHECK_GT(temporary_register_count_, 0);
+  return Register(fixed_register_count() + temporary_register_count_ - 1);
+}
+
+
 Register BytecodeArrayBuilder::Parameter(int parameter_index) const {
   DCHECK_GE(parameter_index, 0);
   return Register::FromParameterIndex(parameter_index, parameter_count());
 }
 
 
+bool BytecodeArrayBuilder::RegisterIsParameterOrLocal(Register reg) const {
+  return reg.is_parameter() || reg.index() < locals_count();
+}
+
+
+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();
@@ skipping 518 matching lines @@
 }
 
 
 void BytecodeArrayBuilder::EnsureReturn() {
   if (!return_seen_in_block_) {
     LoadUndefined();
     Return();
   }
 }
 
+
 BytecodeArrayBuilder& BytecodeArrayBuilder::Call(Register callable,
                                                  Register receiver,
                                                  size_t arg_count) {
   if (FitsInIdx8Operand(arg_count)) {
     Output(Bytecode::kCall, callable.ToOperand(), receiver.ToOperand(),
            static_cast<uint8_t>(arg_count));
   } else {
     UNIMPLEMENTED();
   }
   return *this;
@@ skipping 34 matching lines @@
     entry = constants_map_.Get(object);
     *entry = constants_.size();
     constants_.push_back(object);
   }
   DCHECK(constants_[*entry].is_identical_to(object));
   return *entry;
 }
 
 
 int BytecodeArrayBuilder::BorrowTemporaryRegister() {
-  int temporary_reg_index = temporary_register_next_++;
-  int count = temporary_register_next_ - fixed_register_count();
-  if (count > temporary_register_count_) {
-    temporary_register_count_ = count;
+  if (free_temporaries_.empty()) {
+    temporary_register_count_ += 1;
+    return last_temporary_register().index();
+  } else {
+    auto pos = free_temporaries_.begin();
+    int retval = *pos;
+    free_temporaries_.erase(pos);
+    return retval;
   }
-  return temporary_reg_index;
+}
+
+
+void BytecodeArrayBuilder::BorrowConsecutiveTemporaryRegister(int reg_index) {
+  free_temporaries_.erase(reg_index);

[rmcilroy, 2015/10/20 16:39:20]

Could you DCHECK that the value is in free_temporaries_ before it is erased.

[oth, 2015/10/20 20:58:42]

Done.

 }
 
 
 void BytecodeArrayBuilder::ReturnTemporaryRegister(int reg_index) {
-  DCHECK_EQ(reg_index, temporary_register_next_ - 1);
-  temporary_register_next_ = reg_index;
+  DCHECK(free_temporaries_.find(reg_index) == free_temporaries_.end());
+  free_temporaries_.insert(reg_index);
 }
 
 
+int BytecodeArrayBuilder::PrepareForConsecutiveTemporaryRegisters(
+    size_t count) {
+  if (count == 0) {
+    return -1;
+  }
+
+  // Search within existing temporaries for a run.
+  auto start = free_temporaries_.begin();
+  int run_length = 0;
+  for (auto run_end = start; run_end != free_temporaries_.end(); run_end++) {
+    if (*run_end != *start + run_length) {
+      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 + run_length != last_temporary_register().index() + 1)) {
+    run_length = 0;
+  }
+
+  // Ensure enough registers for run.
+  while (run_length++ < count) {
+    temporary_register_count_++;
+    free_temporaries_.insert(last_temporary_register().index());
+  }
+  return last_temporary_register().index() - static_cast<int>(count) + 1;
+}
+
+
+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;
     case OperandType::kIdx16:
       return static_cast<uint16_t>(operand_value) == operand_value;
     case OperandType::kCount8:
     case OperandType::kImm8:
     case OperandType::kIdx8:
       return static_cast<uint8_t>(operand_value) == operand_value;
     case OperandType::kReg8: {
       Register reg = Register::FromOperand(static_cast<uint8_t>(operand_value));
       if (reg.is_function_context() || reg.is_function_closure()) {
         return true;
       } else if (reg.is_parameter()) {
-        int parameter_index = reg.ToParameterIndex(parameter_count());
-        return parameter_index >= 0 && parameter_index < parameter_count();
+        int parameter_index = reg.ToParameterIndex(parameter_count_);
+        return parameter_index >= 0 && parameter_index < parameter_count_;
+      } else if (reg.index() < fixed_register_count()) {
+        return true;
       } else {
-        return (reg.index() >= 0 && reg.index() < temporary_register_next_);
+        return TemporaryRegisterIsLive(reg);
       }
     }
   }
   UNREACHABLE();
   return false;
 }
 
 bool BytecodeArrayBuilder::LastBytecodeInSameBlock() const {
   return last_bytecode_start_ < bytecodes()->size() &&
          last_bytecode_start_ >= last_block_end_;
@@ skipping 163 matching lines @@
 }
 
 
 // static
 bool BytecodeArrayBuilder::FitsInIdx16Operand(int value) {
   return kMinUInt16 <= value && value <= kMaxUInt16;
 }
 
 
 TemporaryRegisterScope::TemporaryRegisterScope(BytecodeArrayBuilder* builder)
-    : builder_(builder), count_(0), last_register_index_(-1) {}
+    : builder_(builder),
+      allocated_(builder->zone()),
+      next_consecutive_register_(-1),
+      next_consecutive_count_(-1) {
+  // TODO(oth): Deprecate TemporaryRegisterScope use. Should be using
+  // result scopes as far as possible.

[rmcilroy, 2015/10/20 16:39:20]

nit - move TODO to TemporaryRegisterScope declaration in header.

[oth, 2015/10/20 20:58:42]

Done.

+}
 
 
 TemporaryRegisterScope::~TemporaryRegisterScope() {
-  while (count_-- != 0) {
-    builder_->ReturnTemporaryRegister(last_register_index_--);
+  for (auto i = allocated_.rbegin(); i != allocated_.rend(); i++) {
+    builder_->ReturnTemporaryRegister(*i);
+  }
+  allocated_.clear();
+}
+
+
+Register TemporaryRegisterScope::NewRegister() {
+  int allocated = builder_->BorrowTemporaryRegister();
+  allocated_.push_back(allocated);
+  return Register(allocated);
+}
+
+
+void TemporaryRegisterScope::PrepareForConsecutiveAllocations(size_t count) {
+  if (static_cast<int>(count) > next_consecutive_count_) {
+    next_consecutive_register_ =
+        builder_->PrepareForConsecutiveTemporaryRegisters(count);
+    next_consecutive_count_ = static_cast<int>(count);
   }
 }
 
 
-Register TemporaryRegisterScope::NewRegister() {
-  count_++;
-  last_register_index_ = builder_->BorrowTemporaryRegister();
-  return Register(last_register_index_);
+Register TemporaryRegisterScope::NextConsecutiveRegister() {
+  DCHECK_GE(next_consecutive_register_, 0);
+  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