Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(56)

Side by Side Diff: src/interpreter/bytecode-register-allocator.cc

Issue 1651133002: [interpreter] Move temporary register allocator into own file. (Closed) Base URL: https://chromium.googlesource.com/v8/v8.git@master
Patch Set: ASAN fix. Created 4 years, 10 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
OLDNEW
1 // Copyright 2015 the V8 project authors. All rights reserved. 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 2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file. 3 // found in the LICENSE file.
4 4
5 #include "src/interpreter/bytecode-register-allocator.h" 5 #include "src/interpreter/bytecode-register-allocator.h"
6 6
7 #include "src/interpreter/bytecode-array-builder.h" 7 #include "src/interpreter/bytecode-array-builder.h"
8 8
9 namespace v8 { 9 namespace v8 {
10 namespace internal { 10 namespace internal {
11 namespace interpreter { 11 namespace interpreter {
12 12
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 =
57 free_temporaries_.lower_bound(start_index);
58 if (index == free_temporaries_.begin()) {
59 // If start_index is the first free register, check for a register
60 // greater than end_index.
61 index = free_temporaries_.upper_bound(end_index);
62 if (index == free_temporaries_.end()) {
63 return AllocateTemporaryRegister();
64 }
65 } else {
66 // If there is a free register < start_index
67 index--;
68 }
69
70 int retval = *index;
71 free_temporaries_.erase(index);
72 return retval;
73 }
74
75 int TemporaryRegisterAllocator::PrepareForConsecutiveTemporaryRegisters(
76 size_t count) {
77 if (count == 0) {
78 return -1;
79 }
80
81 // TODO(oth): replace use of set<> here for free_temporaries with a
82 // more efficient structure. And/or partition into two searches -
83 // one before the translation window and one after.
84
85 // A run will require at least |count| free temporaries.
86 while (free_temporaries_.size() < count) {
87 free_temporaries_.insert(AllocateTemporaryRegister());
88 }
89
90 // Search within existing temporaries for a run.
91 auto start = free_temporaries_.begin();
92 size_t run_length = 0;
93 for (auto run_end = start; run_end != free_temporaries_.end(); run_end++) {
94 int expected = *start + static_cast<int>(run_length);
95 if (*run_end != expected) {
96 start = run_end;
97 run_length = 0;
98 }
99 Register reg_start(*start);
100 Register reg_expected(expected);
101 if (RegisterTranslator::DistanceToTranslationWindow(reg_start) > 0 &&
102 RegisterTranslator::DistanceToTranslationWindow(reg_expected) <= 0) {
103 // Run straddles the lower edge of the translation window. Registers
104 // after the start of this boundary are displaced by the register
105 // translator to provide a hole for translation. Runs either side
106 // of the boundary are fine.
107 start = run_end;
108 run_length = 0;
109 }
110 if (++run_length == count) {
111 return *start;
112 }
113 }
114
115 // Continue run if possible across existing last temporary.
116 if (allocation_count_ > 0 && (start == free_temporaries_.end() ||
117 *start + static_cast<int>(run_length) !=
118 last_temporary_register().index() + 1)) {
119 run_length = 0;
120 }
121
122 // Pad temporaries if extended run would cross translation boundary.
123 Register reg_first(*start);
124 Register reg_last(*start + static_cast<int>(count) - 1);
125 DCHECK_GT(RegisterTranslator::DistanceToTranslationWindow(reg_first),
126 RegisterTranslator::DistanceToTranslationWindow(reg_last));
127 while (RegisterTranslator::DistanceToTranslationWindow(reg_first) > 0 &&
128 RegisterTranslator::DistanceToTranslationWindow(reg_last) <= 0) {
129 auto pos_insert_pair =
130 free_temporaries_.insert(AllocateTemporaryRegister());
131 reg_first = Register(*pos_insert_pair.first);
132 reg_last = Register(reg_first.index() + static_cast<int>(count) - 1);
133 run_length = 0;
134 }
135
136 // Ensure enough registers for run.
137 while (run_length++ < count) {
138 free_temporaries_.insert(AllocateTemporaryRegister());
139 }
140
141 int run_start =
142 last_temporary_register().index() - static_cast<int>(count) + 1;
143 DCHECK(RegisterTranslator::DistanceToTranslationWindow(Register(run_start)) <=
144 0 ||
145 RegisterTranslator::DistanceToTranslationWindow(
146 Register(run_start + static_cast<int>(count) - 1)) > 0);
147 return run_start;
148 }
149
150 bool TemporaryRegisterAllocator::RegisterIsLive(Register reg) const {
151 if (allocation_count_ > 0) {
152 DCHECK(reg >= first_temporary_register() &&
153 reg <= last_temporary_register());
154 return free_temporaries_.find(reg.index()) == free_temporaries_.end();
155 } else {
156 return false;
157 }
158 }
159
160 void TemporaryRegisterAllocator::BorrowConsecutiveTemporaryRegister(
161 int reg_index) {
162 DCHECK(free_temporaries_.find(reg_index) != free_temporaries_.end());
163 free_temporaries_.erase(reg_index);
164 }
165
166 void TemporaryRegisterAllocator::ReturnTemporaryRegister(int reg_index) {
167 DCHECK(free_temporaries_.find(reg_index) == free_temporaries_.end());
168 free_temporaries_.insert(reg_index);
169 }
170
13 BytecodeRegisterAllocator::BytecodeRegisterAllocator( 171 BytecodeRegisterAllocator::BytecodeRegisterAllocator(
14 BytecodeArrayBuilder* builder) 172 Zone* zone, TemporaryRegisterAllocator* allocator)
15 : builder_(builder), 173 : base_allocator_(allocator),
16 allocated_(builder->zone()), 174 allocated_(zone),
17 next_consecutive_register_(-1), 175 next_consecutive_register_(-1),
18 next_consecutive_count_(-1) {} 176 next_consecutive_count_(-1) {}
19 177
20
21 BytecodeRegisterAllocator::~BytecodeRegisterAllocator() { 178 BytecodeRegisterAllocator::~BytecodeRegisterAllocator() {
22 for (auto i = allocated_.rbegin(); i != allocated_.rend(); i++) { 179 for (auto i = allocated_.rbegin(); i != allocated_.rend(); i++) {
23 builder_->ReturnTemporaryRegister(*i); 180 base_allocator()->ReturnTemporaryRegister(*i);
24 } 181 }
25 allocated_.clear(); 182 allocated_.clear();
26 } 183 }
27 184
28 185
29 Register BytecodeRegisterAllocator::NewRegister() { 186 Register BytecodeRegisterAllocator::NewRegister() {
30 int allocated = -1; 187 int allocated = -1;
31 if (next_consecutive_count_ <= 0) { 188 if (next_consecutive_count_ <= 0) {
32 allocated = builder_->BorrowTemporaryRegister(); 189 allocated = base_allocator()->BorrowTemporaryRegister();
33 } else { 190 } else {
34 allocated = builder_->BorrowTemporaryRegisterNotInRange( 191 allocated = base_allocator()->BorrowTemporaryRegisterNotInRange(
35 next_consecutive_register_, 192 next_consecutive_register_,
36 next_consecutive_register_ + next_consecutive_count_ - 1); 193 next_consecutive_register_ + next_consecutive_count_ - 1);
37 } 194 }
38 allocated_.push_back(allocated); 195 allocated_.push_back(allocated);
39 return Register(allocated); 196 return Register(allocated);
40 } 197 }
41 198
42 199
43 bool BytecodeRegisterAllocator::RegisterIsAllocatedInThisScope( 200 bool BytecodeRegisterAllocator::RegisterIsAllocatedInThisScope(
44 Register reg) const { 201 Register reg) const {
45 for (auto i = allocated_.begin(); i != allocated_.end(); i++) { 202 for (auto i = allocated_.begin(); i != allocated_.end(); i++) {
46 if (*i == reg.index()) return true; 203 if (*i == reg.index()) return true;
47 } 204 }
48 return false; 205 return false;
49 } 206 }
50 207
51 208
52 void BytecodeRegisterAllocator::PrepareForConsecutiveAllocations(size_t count) { 209 void BytecodeRegisterAllocator::PrepareForConsecutiveAllocations(size_t count) {
53 if (static_cast<int>(count) > next_consecutive_count_) { 210 if (static_cast<int>(count) > next_consecutive_count_) {
54 next_consecutive_register_ = 211 next_consecutive_register_ =
55 builder_->PrepareForConsecutiveTemporaryRegisters(count); 212 base_allocator()->PrepareForConsecutiveTemporaryRegisters(count);
56 next_consecutive_count_ = static_cast<int>(count); 213 next_consecutive_count_ = static_cast<int>(count);
57 } 214 }
58 } 215 }
59 216
60 217
61 Register BytecodeRegisterAllocator::NextConsecutiveRegister() { 218 Register BytecodeRegisterAllocator::NextConsecutiveRegister() {
62 DCHECK_GE(next_consecutive_register_, 0); 219 DCHECK_GE(next_consecutive_register_, 0);
63 DCHECK_GT(next_consecutive_count_, 0); 220 DCHECK_GT(next_consecutive_count_, 0);
64 builder_->BorrowConsecutiveTemporaryRegister(next_consecutive_register_); 221 base_allocator()->BorrowConsecutiveTemporaryRegister(
222 next_consecutive_register_);
65 allocated_.push_back(next_consecutive_register_); 223 allocated_.push_back(next_consecutive_register_);
66 next_consecutive_count_--; 224 next_consecutive_count_--;
67 return Register(next_consecutive_register_++); 225 return Register(next_consecutive_register_++);
68 } 226 }
69 227
70 } // namespace interpreter 228 } // namespace interpreter
71 } // namespace internal 229 } // namespace internal
72 } // namespace v8 230 } // namespace v8
OLDNEW

Powered by Google App Engine
This is Rietveld 408576698