[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),
+      temporary_register_count_(0) {}
 
 
 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 {
+  // OTH: TODO review or context?

[rmcilroy, 2015/10/19 12:56:21]

I don't think we need to worry about contexts since these registers are never
directly returned as results. Maybe add a DCHECK in RegisterResultScope that the
result register is RegisterIsParameterOrLocal() or is a temporary register to
enforce this?

[oth, 2015/10/20 15:28:51]

Agree. Now have a RegisterIsTemporary() as an additional check. Not sure we need
anything extra for contexts for now.

+  return reg.is_parameter() || reg.index() < local_register_count_;

[rmcilroy, 2015/10/19 12:56:21]

use local_register_count() instead.

[oth, 2015/10/20 15:28:51]

Done.

+}
+
+
 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;
+  int retval;
+  if (free_temporaries_.empty()) {
+    temporary_register_count_ += 1;
+    retval = last_temporary_register().index();
+  } else {
+    retval = free_temporaries_.back();
+    free_temporaries_.pop_back();
+    for (size_t i = 0; i < free_temporaries_.size(); i++) {

[rmcilroy, 2015/10/19 12:56:21]

Only do this loop if #DEBUG.

[oth, 2015/10/20 15:28:52]

Re-implemented with ZoneSet.

+      DCHECK(free_temporaries_[i] != retval);
+    }
   }
-  return temporary_reg_index;
+  return retval;
 }
 
 
 void BytecodeArrayBuilder::ReturnTemporaryRegister(int reg_index) {
-  DCHECK_EQ(reg_index, temporary_register_next_ - 1);
-  temporary_register_next_ = reg_index;
+  for (size_t i = 0; i < free_temporaries_.size(); i++) {

[rmcilroy, 2015/10/19 12:56:22]

ditto

[oth, 2015/10/20 15:28:52]

Re-implemented with ZoneSet.

+    DCHECK(free_temporaries_[i] != reg_index);
+  }
+  free_temporaries_.push_back(reg_index);
 }
 
 
+static void CheckConsecutiveRun(ZoneVector<int>* v, size_t count) {

[rmcilroy, 2015/10/19 12:56:21]

This code should only be run if #DEBUG - just make it IsConsecutiveRun with a
bool return value and call DCHECK(IsConsecutiveRun(...)) below.

[oth, 2015/10/20 15:28:52]

Method removed.

+  DCHECK_GE(v->size(), count);
+  auto current = v->rbegin();
+  while (count-- > 1) {

[rmcilroy, 2015/10/19 12:56:21]

for loop instead?

[oth, 2015/10/20 15:28:52]

Ack.

+    auto successor = current + 1;
+    DCHECK_EQ(*successor, *current + 1);
+    current = successor;
+  }
+}
+
+
+void BytecodeArrayBuilder::PrepareForConsecutiveTemporaryRegisters(
+    size_t count) {
+  // TODO(oth): this is a placeholder. There should have a better
+  // allocator that avoids sorting, e.g. bitmap allocator with hint to
+  // next cell in a consecutive sequence, or something similar.
+
+  if (count == 0) {
+    return;
+  }
+
+  size_t run = 0;
+  std::sort(free_temporaries_.begin(), free_temporaries_.end());

[rmcilroy, 2015/10/19 12:56:21]

How about we just keep free_temporaries sorted rather than doing the sort here?
E.g., std::set will keep it sorted (and is also more semantically correct since
there shouldn't be duplicate free registers).

[oth, 2015/10/20 15:28:52]

Yes, it's become a bit overwhelming in it's current form. Switched to using a
set. The code is much cleaner and produces the same output.

As part of this the TemporaryRegisterScope now has a NextConsecutiveRegister
method that should be called after PrepareForConsecutiveAllocations. And there's
counter and cursor for maintaining the necessary state.

+
+  // First check for a run in the existing elements

[rmcilroy, 2015/10/19 12:56:22]

How often do we end up (in the current test code) getting a run of free
registers in the middle of the free_temporaries? Would it be simpler to just
maintain the free-list sorted using a set (as above) and only try and abutt the
consecutive temporaries at the end of the free list, completing with new
temporaries as necessary?

[oth, 2015/10/20 15:28:52]

IIRC it only occurs in VisitObjectLiterals which is quite painful. See what you
think of the revised allocator - it still does this, but is much cleaner and
easier to follow (hopefully).

+  if (free_temporaries_.size() >= count) {
+    size_t run_start = 0;
+    int last_temporary = free_temporaries_[0] - 1;
+    for (size_t i = 0; i < free_temporaries_.size(); i++) {
+      if (free_temporaries_[i] == last_temporary + 1) {
+        if (i - run_start + 1 == count) {
+          std::rotate(free_temporaries_.begin(),
+                      free_temporaries_.begin() + i + 1,
+                      free_temporaries_.end());
+          std::reverse(free_temporaries_.rbegin(),
+                       free_temporaries_.rbegin() + count);
+          CheckConsecutiveRun(&free_temporaries_, count);
+          return;
+        }
+      } else {
+        run_start = i;
+      }
+      last_temporary = free_temporaries_[i];
+    }
+  }
+
+  // Next check if a run can be formed abutting the end of the
+  // free list.
+  if (!free_temporaries_.empty()) {
+    auto start = free_temporaries_.rbegin();
+    int last_index = last_temporary_register().index() + 1;
+    while (run < count && start != free_temporaries_.rend() &&
+           *start == last_index - 1) {
+      last_index = *start;
+      start++;
+      run++;
+    }
+  }
+
+  // Complete run with new temporaries as necessary.
+  while (run < count) {
+    // Push back enough temporaries to ensure consecutive allocations.
+    temporary_register_count_ += 1;
+    int index = last_temporary_register().index();
+    free_temporaries_.push_back(index);
+    run++;
+  }
+
+  // Finally, reverse end of free list to give consecutive order as
+  // registers are popped off.
+  auto lhs = free_temporaries_.rbegin();
+  auto rhs = lhs + count;
+  std::reverse(lhs, rhs);
+  CheckConsecutiveRun(&free_temporaries_, count);
+}
+
+
+bool BytecodeArrayBuilder::TemporaryRegisterIsLive(Register reg) const {
+  if (temporary_register_count_ > 0) {
+    for (size_t i = 0; i < free_temporaries_.size(); i++) {
+      if (free_temporaries_[i] == reg.index()) {
+        return false;
+      }
+    }
+    return reg <= last_temporary_register();
+  } 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() < local_register_count_) {

[rmcilroy, 2015/10/19 12:56:21]

I don't think this check is necessary given the check below. If it is, then use
local_register_count()

[oth, 2015/10/20 15:28:52]

Yes, agree. Removed.

+        return true;
+      } else if (reg.index() <
+                 local_register_count_ + context_register_count_) {

[rmcilroy, 2015/10/19 12:56:22]

reg.index() < fixed_register_count()

[oth, 2015/10/20 15:28:52]

Done.

+        // context_register_count_ may be -1 if not initialized.

[rmcilroy, 2015/10/19 12:56:21]

This comment should no longer be true - if you spot somewhere that
context_register_count_ is -1 let me know.

[oth, 2015/10/20 15:28:52]

Acknowledged. Removed comment.

+        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()) {}
 
 
 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) {

[rmcilroy, 2015/10/19 12:56:21]

As discussed offline - we should be moving towards a model where all register
allocations have to happen through the ResultScope (and TemporaryRegisterScope
becomes private and a friend of ResultScope), then we could have a DCHECK that
after PrepareForConsecutiveAllocations, the result scope only calls
NewConsecutiveRegister() and fails if something tries to call NewRegister() on
that scope (at least until the Consecutive allocations are no longer needed. As
I mentioned, I'm fine with this as-is for now, but let's add a TODO.

[oth, 2015/10/20 15:28:51]

Added a TODO in the constructor for TemporaryRegisterScope.

+  builder_->PrepareForConsecutiveTemporaryRegisters(count);
 }
 
 }  // namespace interpreter
 }  // namespace internal
 }  // namespace v8