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 | } |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 98 | if (++run_length == count) { |
| 99 | return *start; |
| 100 | } |
| 101 | } |
| 102 | |
| 103 | // Continue run if possible across existing last temporary. |
| 104 | if (allocation_count_ > 0 && (start == free_temporaries_.end() || |
| 105 | *start + static_cast<int>(run_length) != |
| 106 | last_temporary_register().index() + 1)) { |
| 107 | run_length = 0; |
| 108 | } |
| 109 | |
| 110 | // Pad temporaries if extended run would cross translation boundary. |
| 111 | Register reg_first(*start); |
| 112 | Register reg_last(*start + static_cast<int>(count) - 1); |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 113 | |
| 114 | // Ensure enough registers for run. |
| 115 | while (run_length++ < count) { |
| 116 | free_temporaries_.insert(AllocateTemporaryRegister()); |
| 117 | } |
| 118 | |
| 119 | int run_start = |
| 120 | last_temporary_register().index() - static_cast<int>(count) + 1; |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 121 | return run_start; |
| 122 | } |
| 123 | |
| 124 | bool TemporaryRegisterAllocator::RegisterIsLive(Register reg) const { |
| 125 | if (allocation_count_ > 0) { |
| 126 | DCHECK(reg >= first_temporary_register() && |
| 127 | reg <= last_temporary_register()); |
| 128 | return free_temporaries_.find(reg.index()) == free_temporaries_.end(); |
| 129 | } else { |
| 130 | return false; |
| 131 | } |
| 132 | } |
| 133 | |
| 134 | void TemporaryRegisterAllocator::BorrowConsecutiveTemporaryRegister( |
| 135 | int reg_index) { |
| 136 | DCHECK(free_temporaries_.find(reg_index) != free_temporaries_.end()); |
| 137 | free_temporaries_.erase(reg_index); |
| 138 | } |
| 139 | |
| 140 | void TemporaryRegisterAllocator::ReturnTemporaryRegister(int reg_index) { |
| 141 | DCHECK(free_temporaries_.find(reg_index) == free_temporaries_.end()); |
| 142 | free_temporaries_.insert(reg_index); |
| 143 | } |
| 144 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 145 | BytecodeRegisterAllocator::BytecodeRegisterAllocator( |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 146 | Zone* zone, TemporaryRegisterAllocator* allocator) |
| 147 | : base_allocator_(allocator), |
| 148 | allocated_(zone), |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 149 | next_consecutive_register_(-1), |
| 150 | next_consecutive_count_(-1) {} |
| 151 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 152 | BytecodeRegisterAllocator::~BytecodeRegisterAllocator() { |
| 153 | for (auto i = allocated_.rbegin(); i != allocated_.rend(); i++) { |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 154 | base_allocator()->ReturnTemporaryRegister(*i); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 155 | } |
| 156 | allocated_.clear(); |
| 157 | } |
| 158 | |
| 159 | |
| 160 | Register BytecodeRegisterAllocator::NewRegister() { |
| 161 | int allocated = -1; |
| 162 | if (next_consecutive_count_ <= 0) { |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 163 | allocated = base_allocator()->BorrowTemporaryRegister(); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 164 | } else { |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 165 | allocated = base_allocator()->BorrowTemporaryRegisterNotInRange( |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 166 | next_consecutive_register_, |
| 167 | next_consecutive_register_ + next_consecutive_count_ - 1); |
| 168 | } |
| 169 | allocated_.push_back(allocated); |
| 170 | return Register(allocated); |
| 171 | } |
| 172 | |
| 173 | |
| 174 | bool BytecodeRegisterAllocator::RegisterIsAllocatedInThisScope( |
| 175 | Register reg) const { |
| 176 | for (auto i = allocated_.begin(); i != allocated_.end(); i++) { |
| 177 | if (*i == reg.index()) return true; |
| 178 | } |
| 179 | return false; |
| 180 | } |
| 181 | |
| 182 | |
| 183 | void BytecodeRegisterAllocator::PrepareForConsecutiveAllocations(size_t count) { |
| 184 | if (static_cast<int>(count) > next_consecutive_count_) { |
| 185 | next_consecutive_register_ = |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 186 | base_allocator()->PrepareForConsecutiveTemporaryRegisters(count); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 187 | next_consecutive_count_ = static_cast<int>(count); |
| 188 | } |
| 189 | } |
| 190 | |
| 191 | |
| 192 | Register BytecodeRegisterAllocator::NextConsecutiveRegister() { |
| 193 | DCHECK_GE(next_consecutive_register_, 0); |
| 194 | DCHECK_GT(next_consecutive_count_, 0); |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 195 | base_allocator()->BorrowConsecutiveTemporaryRegister( |
| 196 | next_consecutive_register_); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 197 | allocated_.push_back(next_consecutive_register_); |
| 198 | next_consecutive_count_--; |
| 199 | return Register(next_consecutive_register_++); |
| 200 | } |
| 201 | |
| 202 | } // namespace interpreter |
| 203 | } // namespace internal |
| 204 | } // namespace v8 |