[Interpreter] Reduce temporary register usage in generated bytecode.

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 b732f8b96fae8197abf145ffc3abe0af50df6e09..2a139e55e607e0c62a6d1dd44a4ffb0f26465c38 100644
--- a/src/interpreter/bytecode-array-builder.cc
+++ b/src/interpreter/bytecode-array-builder.cc
@@ -22,13 +22,12 @@ BytecodeArrayBuilder::BytecodeArrayBuilder(Isolate* isolate, Zone* zone)
       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_;
 }
 
 
@@ -40,7 +39,6 @@ void BytecodeArrayBuilder::set_parameter_count(int 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_;
 }
 
 
@@ -56,12 +54,35 @@ Register BytecodeArrayBuilder::last_context_register() const {
 }
 
 
+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);
 
@@ -600,6 +621,7 @@ void BytecodeArrayBuilder::EnsureReturn() {
   }
 }
 
+
 BytecodeArrayBuilder& BytecodeArrayBuilder::Call(Register callable,
                                                  Register receiver,
                                                  size_t arg_count) {
@@ -654,18 +676,72 @@ size_t BytecodeArrayBuilder::GetConstantPoolEntry(Handle<Object> object) {
 
 
 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;
+  }
 }
 
 
@@ -686,10 +762,12 @@ bool BytecodeArrayBuilder::OperandIsValid(Bytecode bytecode, int operand_index,
       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);
       }
     }
   }
@@ -873,20 +951,46 @@ bool BytecodeArrayBuilder::FitsInIdx16Operand(int value) {
 
 
 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() {
-  count_++;
-  last_register_index_ = builder_->BorrowTemporaryRegister();
-  return Register(last_register_index_);
+  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::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