Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 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 | |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 13 | TemporaryRegisterAllocator::TemporaryRegisterAllocator(Zone* zone, |
| 14 | int allocation_base) |
| 15 | : free_temporaries_(zone), |
| 16 | allocation_base_(allocation_base), |
Ben Murdoch | 61f157c | 2016-09-16 13:49:30 +0100 | [diff] [blame] | 17 | allocation_count_(0), |
| 18 | observer_(nullptr) {} |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 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 | |
Ben Murdoch | 61f157c | 2016-09-16 13:49:30 +0100 | [diff] [blame] | 30 | void TemporaryRegisterAllocator::set_observer( |
| 31 | TemporaryRegisterObserver* observer) { |
| 32 | DCHECK(observer_ == nullptr); |
| 33 | observer_ = observer; |
| 34 | } |
| 35 | |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 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 | } |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 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); |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 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; |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 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); |
Ben Murdoch | 61f157c | 2016-09-16 13:49:30 +0100 | [diff] [blame] | 150 | if (observer_) { |
| 151 | observer_->TemporaryRegisterFreeEvent(Register(reg_index)); |
| 152 | } |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 153 | } |
| 154 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 155 | BytecodeRegisterAllocator::BytecodeRegisterAllocator( |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 156 | Zone* zone, TemporaryRegisterAllocator* allocator) |
| 157 | : base_allocator_(allocator), |
| 158 | allocated_(zone), |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 159 | next_consecutive_register_(-1), |
| 160 | next_consecutive_count_(-1) {} |
| 161 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 162 | BytecodeRegisterAllocator::~BytecodeRegisterAllocator() { |
| 163 | for (auto i = allocated_.rbegin(); i != allocated_.rend(); i++) { |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 164 | base_allocator()->ReturnTemporaryRegister(*i); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 165 | } |
| 166 | allocated_.clear(); |
| 167 | } |
| 168 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 169 | Register BytecodeRegisterAllocator::NewRegister() { |
| 170 | int allocated = -1; |
| 171 | if (next_consecutive_count_ <= 0) { |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 172 | allocated = base_allocator()->BorrowTemporaryRegister(); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 173 | } else { |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 174 | allocated = base_allocator()->BorrowTemporaryRegisterNotInRange( |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 175 | next_consecutive_register_, |
| 176 | next_consecutive_register_ + next_consecutive_count_ - 1); |
| 177 | } |
| 178 | allocated_.push_back(allocated); |
| 179 | return Register(allocated); |
| 180 | } |
| 181 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 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 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 190 | void BytecodeRegisterAllocator::PrepareForConsecutiveAllocations(size_t count) { |
| 191 | if (static_cast<int>(count) > next_consecutive_count_) { |
| 192 | next_consecutive_register_ = |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 193 | base_allocator()->PrepareForConsecutiveTemporaryRegisters(count); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 194 | next_consecutive_count_ = static_cast<int>(count); |
| 195 | } |
| 196 | } |
| 197 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 198 | Register BytecodeRegisterAllocator::NextConsecutiveRegister() { |
| 199 | DCHECK_GE(next_consecutive_register_, 0); |
| 200 | DCHECK_GT(next_consecutive_count_, 0); |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 201 | base_allocator()->BorrowConsecutiveTemporaryRegister( |
| 202 | next_consecutive_register_); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 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 |