Home | History | Annotate | Download | only in interpreter 
      1 // Copyright 2015 the V8 project authors. All rights reserved.
      2 // Use of this source code is governed by a BSD-style license that can be
      3 // found in the LICENSE file.
      4 
      5 #include "src/interpreter/bytecode-register-allocator.h"
      6 
      7 #include "src/interpreter/bytecode-array-builder.h"
      8 
      9 namespace v8 {
     10 namespace internal {
     11 namespace interpreter {
     12 
     13 TemporaryRegisterAllocator::TemporaryRegisterAllocator(Zone* zone,
     14                                                        int allocation_base)
     15     : free_temporaries_(zone),
     16       allocation_base_(allocation_base),
     17       allocation_count_(0),
     18       observer_(nullptr) {}
     19 
     20 Register TemporaryRegisterAllocator::first_temporary_register() const {
     21   DCHECK(allocation_count() > 0);
     22   return Register(allocation_base());
     23 }
     24 
     25 Register TemporaryRegisterAllocator::last_temporary_register() const {
     26   DCHECK(allocation_count() > 0);
     27   return Register(allocation_base() + allocation_count() - 1);
     28 }
     29 
     30 void TemporaryRegisterAllocator::set_observer(
     31     TemporaryRegisterObserver* observer) {
     32   DCHECK(observer_ == nullptr);
     33   observer_ = observer;
     34 }
     35 
     36 int TemporaryRegisterAllocator::AllocateTemporaryRegister() {
     37   allocation_count_ += 1;
     38   return allocation_base() + allocation_count() - 1;
     39 }
     40 
     41 int TemporaryRegisterAllocator::BorrowTemporaryRegister() {
     42   if (free_temporaries_.empty()) {
     43     return AllocateTemporaryRegister();
     44   } else {
     45     auto pos = free_temporaries_.begin();
     46     int retval = *pos;
     47     free_temporaries_.erase(pos);
     48     return retval;
     49   }
     50 }
     51 
     52 int TemporaryRegisterAllocator::BorrowTemporaryRegisterNotInRange(
     53     int start_index, int end_index) {
     54   if (free_temporaries_.empty()) {
     55     int next_allocation = allocation_base() + allocation_count();
     56     while (next_allocation >= start_index && next_allocation <= end_index) {
     57       free_temporaries_.insert(AllocateTemporaryRegister());
     58       next_allocation += 1;
     59     }
     60     return AllocateTemporaryRegister();
     61   }
     62 
     63   ZoneSet<int>::iterator index = free_temporaries_.lower_bound(start_index);
     64   if (index == free_temporaries_.begin()) {
     65     // If start_index is the first free register, check for a register
     66     // greater than end_index.
     67     index = free_temporaries_.upper_bound(end_index);
     68     if (index == free_temporaries_.end()) {
     69       return AllocateTemporaryRegister();
     70     }
     71   } else {
     72     // If there is a free register < start_index
     73     index--;
     74   }
     75 
     76   int retval = *index;
     77   free_temporaries_.erase(index);
     78   return retval;
     79 }
     80 
     81 int TemporaryRegisterAllocator::PrepareForConsecutiveTemporaryRegisters(
     82     size_t count) {
     83   if (count == 0) {
     84     return -1;
     85   }
     86 
     87   // TODO(oth): replace use of set<> here for free_temporaries with a
     88   // more efficient structure. And/or partition into two searches -
     89   // one before the translation window and one after.
     90 
     91   // A run will require at least |count| free temporaries.
     92   while (free_temporaries_.size() < count) {
     93     free_temporaries_.insert(AllocateTemporaryRegister());
     94   }
     95 
     96   // Search within existing temporaries for a run.
     97   auto start = free_temporaries_.begin();
     98   size_t run_length = 0;
     99   for (auto run_end = start; run_end != free_temporaries_.end(); run_end++) {
    100     int expected = *start + static_cast<int>(run_length);
    101     if (*run_end != expected) {
    102       start = run_end;
    103       run_length = 0;
    104     }
    105     if (++run_length == count) {
    106       return *start;
    107     }
    108   }
    109 
    110   // Continue run if possible across existing last temporary.
    111   if (allocation_count_ > 0 && (start == free_temporaries_.end() ||
    112                                 *start + static_cast<int>(run_length) !=
    113                                     last_temporary_register().index() + 1)) {
    114     run_length = 0;
    115   }
    116 
    117   // Pad temporaries if extended run would cross translation boundary.
    118   Register reg_first(*start);
    119   Register reg_last(*start + static_cast<int>(count) - 1);
    120 
    121   // Ensure enough registers for run.
    122   while (run_length++ < count) {
    123     free_temporaries_.insert(AllocateTemporaryRegister());
    124   }
    125 
    126   int run_start =
    127       last_temporary_register().index() - static_cast<int>(count) + 1;
    128   return run_start;
    129 }
    130 
    131 bool TemporaryRegisterAllocator::RegisterIsLive(Register reg) const {
    132   if (allocation_count_ > 0) {
    133     DCHECK(reg >= first_temporary_register() &&
    134            reg <= last_temporary_register());
    135     return free_temporaries_.find(reg.index()) == free_temporaries_.end();
    136   } else {
    137     return false;
    138   }
    139 }
    140 
    141 void TemporaryRegisterAllocator::BorrowConsecutiveTemporaryRegister(
    142     int reg_index) {
    143   DCHECK(free_temporaries_.find(reg_index) != free_temporaries_.end());
    144   free_temporaries_.erase(reg_index);
    145 }
    146 
    147 void TemporaryRegisterAllocator::ReturnTemporaryRegister(int reg_index) {
    148   DCHECK(free_temporaries_.find(reg_index) == free_temporaries_.end());
    149   free_temporaries_.insert(reg_index);
    150   if (observer_) {
    151     observer_->TemporaryRegisterFreeEvent(Register(reg_index));
    152   }
    153 }
    154 
    155 BytecodeRegisterAllocator::BytecodeRegisterAllocator(
    156     Zone* zone, TemporaryRegisterAllocator* allocator)
    157     : base_allocator_(allocator),
    158       allocated_(zone),
    159       next_consecutive_register_(-1),
    160       next_consecutive_count_(-1) {}
    161 
    162 BytecodeRegisterAllocator::~BytecodeRegisterAllocator() {
    163   for (auto i = allocated_.rbegin(); i != allocated_.rend(); i++) {
    164     base_allocator()->ReturnTemporaryRegister(*i);
    165   }
    166   allocated_.clear();
    167 }
    168 
    169 Register BytecodeRegisterAllocator::NewRegister() {
    170   int allocated = -1;
    171   if (next_consecutive_count_ <= 0) {
    172     allocated = base_allocator()->BorrowTemporaryRegister();
    173   } else {
    174     allocated = base_allocator()->BorrowTemporaryRegisterNotInRange(
    175         next_consecutive_register_,
    176         next_consecutive_register_ + next_consecutive_count_ - 1);
    177   }
    178   allocated_.push_back(allocated);
    179   return Register(allocated);
    180 }
    181 
    182 bool BytecodeRegisterAllocator::RegisterIsAllocatedInThisScope(
    183     Register reg) const {
    184   for (auto i = allocated_.begin(); i != allocated_.end(); i++) {
    185     if (*i == reg.index()) return true;
    186   }
    187   return false;
    188 }
    189 
    190 void BytecodeRegisterAllocator::PrepareForConsecutiveAllocations(size_t count) {
    191   if (static_cast<int>(count) > next_consecutive_count_) {
    192     next_consecutive_register_ =
    193         base_allocator()->PrepareForConsecutiveTemporaryRegisters(count);
    194     next_consecutive_count_ = static_cast<int>(count);
    195   }
    196 }
    197 
    198 Register BytecodeRegisterAllocator::NextConsecutiveRegister() {
    199   DCHECK_GE(next_consecutive_register_, 0);
    200   DCHECK_GT(next_consecutive_count_, 0);
    201   base_allocator()->BorrowConsecutiveTemporaryRegister(
    202       next_consecutive_register_);
    203   allocated_.push_back(next_consecutive_register_);
    204   next_consecutive_count_--;
    205   return Register(next_consecutive_register_++);
    206 }
    207 
    208 }  // namespace interpreter
    209 }  // namespace internal
    210 }  // namespace v8
    211