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
TemporaryRegisterAllocator(Zone * zone,int allocation_base)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
first_temporary_register() const20 Register TemporaryRegisterAllocator::first_temporary_register() const {
21 DCHECK(allocation_count() > 0);
22 return Register(allocation_base());
23 }
24
last_temporary_register() const25 Register TemporaryRegisterAllocator::last_temporary_register() const {
26 DCHECK(allocation_count() > 0);
27 return Register(allocation_base() + allocation_count() - 1);
28 }
29
set_observer(TemporaryRegisterObserver * observer)30 void TemporaryRegisterAllocator::set_observer(
31 TemporaryRegisterObserver* observer) {
32 DCHECK(observer_ == nullptr);
33 observer_ = observer;
34 }
35
AllocateTemporaryRegister()36 int TemporaryRegisterAllocator::AllocateTemporaryRegister() {
37 allocation_count_ += 1;
38 return allocation_base() + allocation_count() - 1;
39 }
40
BorrowTemporaryRegister()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
BorrowTemporaryRegisterNotInRange(int start_index,int end_index)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
PrepareForConsecutiveTemporaryRegisters(size_t count)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
RegisterIsLive(Register reg) const131 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
BorrowConsecutiveTemporaryRegister(int reg_index)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
ReturnTemporaryRegister(int reg_index)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
BytecodeRegisterAllocator(Zone * zone,TemporaryRegisterAllocator * allocator)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
~BytecodeRegisterAllocator()162 BytecodeRegisterAllocator::~BytecodeRegisterAllocator() {
163 for (auto i = allocated_.rbegin(); i != allocated_.rend(); i++) {
164 base_allocator()->ReturnTemporaryRegister(*i);
165 }
166 allocated_.clear();
167 }
168
NewRegister()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
RegisterIsAllocatedInThisScope(Register reg) const182 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
PrepareForConsecutiveAllocations(size_t count)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
NextConsecutiveRegister()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