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), |
| 17 | allocation_count_(0) {} |
| 18 | |
| 19 | Register TemporaryRegisterAllocator::first_temporary_register() const { |
| 20 | DCHECK(allocation_count() > 0); |
| 21 | return Register(allocation_base()); |
| 22 | } |
| 23 | |
| 24 | Register TemporaryRegisterAllocator::last_temporary_register() const { |
| 25 | DCHECK(allocation_count() > 0); |
| 26 | return Register(allocation_base() + allocation_count() - 1); |
| 27 | } |
| 28 | |
| 29 | int TemporaryRegisterAllocator::AllocateTemporaryRegister() { |
| 30 | allocation_count_ += 1; |
| 31 | return allocation_base() + allocation_count() - 1; |
| 32 | } |
| 33 | |
| 34 | int TemporaryRegisterAllocator::BorrowTemporaryRegister() { |
| 35 | if (free_temporaries_.empty()) { |
| 36 | return AllocateTemporaryRegister(); |
| 37 | } else { |
| 38 | auto pos = free_temporaries_.begin(); |
| 39 | int retval = *pos; |
| 40 | free_temporaries_.erase(pos); |
| 41 | return retval; |
| 42 | } |
| 43 | } |
| 44 | |
| 45 | int TemporaryRegisterAllocator::BorrowTemporaryRegisterNotInRange( |
| 46 | int start_index, int end_index) { |
| 47 | if (free_temporaries_.empty()) { |
| 48 | int next_allocation = allocation_base() + allocation_count(); |
| 49 | while (next_allocation >= start_index && next_allocation <= end_index) { |
| 50 | free_temporaries_.insert(AllocateTemporaryRegister()); |
| 51 | next_allocation += 1; |
| 52 | } |
| 53 | return AllocateTemporaryRegister(); |
| 54 | } |
| 55 | |
| 56 | ZoneSet<int>::iterator index = free_temporaries_.lower_bound(start_index); |
| 57 | if (index == free_temporaries_.begin()) { |
| 58 | // If start_index is the first free register, check for a register |
| 59 | // greater than end_index. |
| 60 | index = free_temporaries_.upper_bound(end_index); |
| 61 | if (index == free_temporaries_.end()) { |
| 62 | return AllocateTemporaryRegister(); |
| 63 | } |
| 64 | } else { |
| 65 | // If there is a free register < start_index |
| 66 | index--; |
| 67 | } |
| 68 | |
| 69 | int retval = *index; |
| 70 | free_temporaries_.erase(index); |
| 71 | return retval; |
| 72 | } |
| 73 | |
| 74 | int TemporaryRegisterAllocator::PrepareForConsecutiveTemporaryRegisters( |
| 75 | size_t count) { |
| 76 | if (count == 0) { |
| 77 | return -1; |
| 78 | } |
| 79 | |
| 80 | // TODO(oth): replace use of set<> here for free_temporaries with a |
| 81 | // more efficient structure. And/or partition into two searches - |
| 82 | // one before the translation window and one after. |
| 83 | |
| 84 | // A run will require at least |count| free temporaries. |
| 85 | while (free_temporaries_.size() < count) { |
| 86 | free_temporaries_.insert(AllocateTemporaryRegister()); |
| 87 | } |
| 88 | |
| 89 | // Search within existing temporaries for a run. |
| 90 | auto start = free_temporaries_.begin(); |
| 91 | size_t run_length = 0; |
| 92 | for (auto run_end = start; run_end != free_temporaries_.end(); run_end++) { |
| 93 | int expected = *start + static_cast<int>(run_length); |
| 94 | if (*run_end != expected) { |
| 95 | start = run_end; |
| 96 | run_length = 0; |
| 97 | } |
| 98 | Register reg_start(*start); |
| 99 | Register reg_expected(expected); |
| 100 | if (RegisterTranslator::DistanceToTranslationWindow(reg_start) > 0 && |
| 101 | RegisterTranslator::DistanceToTranslationWindow(reg_expected) <= 0) { |
| 102 | // Run straddles the lower edge of the translation window. Registers |
| 103 | // after the start of this boundary are displaced by the register |
| 104 | // translator to provide a hole for translation. Runs either side |
| 105 | // of the boundary are fine. |
| 106 | start = run_end; |
| 107 | run_length = 0; |
| 108 | } |
| 109 | if (++run_length == count) { |
| 110 | return *start; |
| 111 | } |
| 112 | } |
| 113 | |
| 114 | // Continue run if possible across existing last temporary. |
| 115 | if (allocation_count_ > 0 && (start == free_temporaries_.end() || |
| 116 | *start + static_cast<int>(run_length) != |
| 117 | last_temporary_register().index() + 1)) { |
| 118 | run_length = 0; |
| 119 | } |
| 120 | |
| 121 | // Pad temporaries if extended run would cross translation boundary. |
| 122 | Register reg_first(*start); |
| 123 | Register reg_last(*start + static_cast<int>(count) - 1); |
| 124 | DCHECK_GT(RegisterTranslator::DistanceToTranslationWindow(reg_first), |
| 125 | RegisterTranslator::DistanceToTranslationWindow(reg_last)); |
| 126 | while (RegisterTranslator::DistanceToTranslationWindow(reg_first) > 0 && |
| 127 | RegisterTranslator::DistanceToTranslationWindow(reg_last) <= 0) { |
| 128 | auto pos_insert_pair = |
| 129 | free_temporaries_.insert(AllocateTemporaryRegister()); |
| 130 | reg_first = Register(*pos_insert_pair.first); |
| 131 | reg_last = Register(reg_first.index() + static_cast<int>(count) - 1); |
| 132 | run_length = 0; |
| 133 | } |
| 134 | |
| 135 | // Ensure enough registers for run. |
| 136 | while (run_length++ < count) { |
| 137 | free_temporaries_.insert(AllocateTemporaryRegister()); |
| 138 | } |
| 139 | |
| 140 | int run_start = |
| 141 | last_temporary_register().index() - static_cast<int>(count) + 1; |
| 142 | DCHECK(RegisterTranslator::DistanceToTranslationWindow(Register(run_start)) <= |
| 143 | 0 || |
| 144 | RegisterTranslator::DistanceToTranslationWindow( |
| 145 | Register(run_start + static_cast<int>(count) - 1)) > 0); |
| 146 | return run_start; |
| 147 | } |
| 148 | |
| 149 | bool TemporaryRegisterAllocator::RegisterIsLive(Register reg) const { |
| 150 | if (allocation_count_ > 0) { |
| 151 | DCHECK(reg >= first_temporary_register() && |
| 152 | reg <= last_temporary_register()); |
| 153 | return free_temporaries_.find(reg.index()) == free_temporaries_.end(); |
| 154 | } else { |
| 155 | return false; |
| 156 | } |
| 157 | } |
| 158 | |
| 159 | void TemporaryRegisterAllocator::BorrowConsecutiveTemporaryRegister( |
| 160 | int reg_index) { |
| 161 | DCHECK(free_temporaries_.find(reg_index) != free_temporaries_.end()); |
| 162 | free_temporaries_.erase(reg_index); |
| 163 | } |
| 164 | |
| 165 | void TemporaryRegisterAllocator::ReturnTemporaryRegister(int reg_index) { |
| 166 | DCHECK(free_temporaries_.find(reg_index) == free_temporaries_.end()); |
| 167 | free_temporaries_.insert(reg_index); |
| 168 | } |
| 169 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 170 | BytecodeRegisterAllocator::BytecodeRegisterAllocator( |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 171 | Zone* zone, TemporaryRegisterAllocator* allocator) |
| 172 | : base_allocator_(allocator), |
| 173 | allocated_(zone), |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 174 | next_consecutive_register_(-1), |
| 175 | next_consecutive_count_(-1) {} |
| 176 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 177 | BytecodeRegisterAllocator::~BytecodeRegisterAllocator() { |
| 178 | for (auto i = allocated_.rbegin(); i != allocated_.rend(); i++) { |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 179 | base_allocator()->ReturnTemporaryRegister(*i); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 180 | } |
| 181 | allocated_.clear(); |
| 182 | } |
| 183 | |
| 184 | |
| 185 | Register BytecodeRegisterAllocator::NewRegister() { |
| 186 | int allocated = -1; |
| 187 | if (next_consecutive_count_ <= 0) { |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 188 | allocated = base_allocator()->BorrowTemporaryRegister(); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 189 | } else { |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 190 | allocated = base_allocator()->BorrowTemporaryRegisterNotInRange( |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 191 | next_consecutive_register_, |
| 192 | next_consecutive_register_ + next_consecutive_count_ - 1); |
| 193 | } |
| 194 | allocated_.push_back(allocated); |
| 195 | return Register(allocated); |
| 196 | } |
| 197 | |
| 198 | |
| 199 | bool BytecodeRegisterAllocator::RegisterIsAllocatedInThisScope( |
| 200 | Register reg) const { |
| 201 | for (auto i = allocated_.begin(); i != allocated_.end(); i++) { |
| 202 | if (*i == reg.index()) return true; |
| 203 | } |
| 204 | return false; |
| 205 | } |
| 206 | |
| 207 | |
| 208 | void BytecodeRegisterAllocator::PrepareForConsecutiveAllocations(size_t count) { |
| 209 | if (static_cast<int>(count) > next_consecutive_count_) { |
| 210 | next_consecutive_register_ = |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 211 | base_allocator()->PrepareForConsecutiveTemporaryRegisters(count); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 212 | next_consecutive_count_ = static_cast<int>(count); |
| 213 | } |
| 214 | } |
| 215 | |
| 216 | |
| 217 | Register BytecodeRegisterAllocator::NextConsecutiveRegister() { |
| 218 | DCHECK_GE(next_consecutive_register_, 0); |
| 219 | DCHECK_GT(next_consecutive_count_, 0); |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame^] | 220 | base_allocator()->BorrowConsecutiveTemporaryRegister( |
| 221 | next_consecutive_register_); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 222 | allocated_.push_back(next_consecutive_register_); |
| 223 | next_consecutive_count_--; |
| 224 | return Register(next_consecutive_register_++); |
| 225 | } |
| 226 | |
| 227 | } // namespace interpreter |
| 228 | } // namespace internal |
| 229 | } // namespace v8 |