1 // Copyright 2016 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-optimizer.h"
6
7 namespace v8 {
8 namespace internal {
9 namespace interpreter {
10
11 const uint32_t BytecodeRegisterOptimizer::kInvalidEquivalenceId = kMaxUInt32;
12
13 // A class for tracking the state of a register. This class tracks
14 // which equivalence set a register is a member of and also whether a
15 // register is materialized in the bytecode stream.
16 class BytecodeRegisterOptimizer::RegisterInfo final : public ZoneObject {
17 public:
RegisterInfo(Register reg,uint32_t equivalence_id,bool materialized,bool allocated)18 RegisterInfo(Register reg, uint32_t equivalence_id, bool materialized,
19 bool allocated)
20 : register_(reg),
21 equivalence_id_(equivalence_id),
22 materialized_(materialized),
23 allocated_(allocated),
24 needs_flush_(false),
25 next_(this),
26 prev_(this) {}
27
28 void AddToEquivalenceSetOf(RegisterInfo* info);
29 void MoveToNewEquivalenceSet(uint32_t equivalence_id, bool materialized);
30 bool IsOnlyMemberOfEquivalenceSet() const;
31 bool IsOnlyMaterializedMemberOfEquivalenceSet() const;
32 bool IsInSameEquivalenceSet(RegisterInfo* info) const;
33
34 // Get a member of the register's equivalence set that is allocated.
35 // Returns itself if allocated, and nullptr if there is no unallocated
36 // equivalent register.
37 RegisterInfo* GetAllocatedEquivalent();
38
39 // Get a member of this register's equivalence set that is
40 // materialized. The materialized equivalent will be this register
41 // if it is materialized. Returns nullptr if no materialized
42 // equivalent exists.
43 RegisterInfo* GetMaterializedEquivalent();
44
45 // Get a member of this register's equivalence set that is
46 // materialized and not register |reg|. The materialized equivalent
47 // will be this register if it is materialized. Returns nullptr if
48 // no materialized equivalent exists.
49 RegisterInfo* GetMaterializedEquivalentOtherThan(Register reg);
50
51 // Get a member of this register's equivalence set that is intended
52 // to be materialized in place of this register (which is currently
53 // materialized). The best candidate is deemed to be the register
54 // with the lowest index as this permits temporary registers to be
55 // removed from the bytecode stream. Returns nullptr if no candidate
56 // exists.
57 RegisterInfo* GetEquivalentToMaterialize();
58
59 // Marks all temporary registers of the equivalence set as unmaterialized.
60 void MarkTemporariesAsUnmaterialized(Register temporary_base);
61
62 // Get an equivalent register. Returns this if none exists.
63 RegisterInfo* GetEquivalent();
64
register_value() const65 Register register_value() const { return register_; }
materialized() const66 bool materialized() const { return materialized_; }
set_materialized(bool materialized)67 void set_materialized(bool materialized) { materialized_ = materialized; }
allocated() const68 bool allocated() const { return allocated_; }
set_allocated(bool allocated)69 void set_allocated(bool allocated) { allocated_ = allocated; }
set_equivalence_id(uint32_t equivalence_id)70 void set_equivalence_id(uint32_t equivalence_id) {
71 equivalence_id_ = equivalence_id;
72 }
equivalence_id() const73 uint32_t equivalence_id() const { return equivalence_id_; }
74 // Indicates if a register should be processed when calling Flush().
needs_flush() const75 bool needs_flush() const { return needs_flush_; }
set_needs_flush(bool needs_flush)76 void set_needs_flush(bool needs_flush) { needs_flush_ = needs_flush; }
77
78 private:
79 Register register_;
80 uint32_t equivalence_id_;
81 bool materialized_;
82 bool allocated_;
83 bool needs_flush_;
84
85 // Equivalence set pointers.
86 RegisterInfo* next_;
87 RegisterInfo* prev_;
88
89 DISALLOW_COPY_AND_ASSIGN(RegisterInfo);
90 };
91
AddToEquivalenceSetOf(RegisterInfo * info)92 void BytecodeRegisterOptimizer::RegisterInfo::AddToEquivalenceSetOf(
93 RegisterInfo* info) {
94 DCHECK_NE(kInvalidEquivalenceId, info->equivalence_id());
95 // Fix old list
96 next_->prev_ = prev_;
97 prev_->next_ = next_;
98 // Add to new list.
99 next_ = info->next_;
100 prev_ = info;
101 prev_->next_ = this;
102 next_->prev_ = this;
103 set_equivalence_id(info->equivalence_id());
104 set_materialized(false);
105 }
106
MoveToNewEquivalenceSet(uint32_t equivalence_id,bool materialized)107 void BytecodeRegisterOptimizer::RegisterInfo::MoveToNewEquivalenceSet(
108 uint32_t equivalence_id, bool materialized) {
109 next_->prev_ = prev_;
110 prev_->next_ = next_;
111 next_ = prev_ = this;
112 equivalence_id_ = equivalence_id;
113 materialized_ = materialized;
114 }
115
IsOnlyMemberOfEquivalenceSet() const116 bool BytecodeRegisterOptimizer::RegisterInfo::IsOnlyMemberOfEquivalenceSet()
117 const {
118 return this->next_ == this;
119 }
120
121 bool BytecodeRegisterOptimizer::RegisterInfo::
IsOnlyMaterializedMemberOfEquivalenceSet() const122 IsOnlyMaterializedMemberOfEquivalenceSet() const {
123 DCHECK(materialized());
124
125 const RegisterInfo* visitor = this->next_;
126 while (visitor != this) {
127 if (visitor->materialized()) {
128 return false;
129 }
130 visitor = visitor->next_;
131 }
132 return true;
133 }
134
IsInSameEquivalenceSet(RegisterInfo * info) const135 bool BytecodeRegisterOptimizer::RegisterInfo::IsInSameEquivalenceSet(
136 RegisterInfo* info) const {
137 return equivalence_id() == info->equivalence_id();
138 }
139
140 BytecodeRegisterOptimizer::RegisterInfo*
GetAllocatedEquivalent()141 BytecodeRegisterOptimizer::RegisterInfo::GetAllocatedEquivalent() {
142 RegisterInfo* visitor = this;
143 do {
144 if (visitor->allocated()) {
145 return visitor;
146 }
147 visitor = visitor->next_;
148 } while (visitor != this);
149
150 return nullptr;
151 }
152
153 BytecodeRegisterOptimizer::RegisterInfo*
GetMaterializedEquivalent()154 BytecodeRegisterOptimizer::RegisterInfo::GetMaterializedEquivalent() {
155 RegisterInfo* visitor = this;
156 do {
157 if (visitor->materialized()) {
158 return visitor;
159 }
160 visitor = visitor->next_;
161 } while (visitor != this);
162
163 return nullptr;
164 }
165
166 BytecodeRegisterOptimizer::RegisterInfo*
GetMaterializedEquivalentOtherThan(Register reg)167 BytecodeRegisterOptimizer::RegisterInfo::GetMaterializedEquivalentOtherThan(
168 Register reg) {
169 RegisterInfo* visitor = this;
170 do {
171 if (visitor->materialized() && visitor->register_value() != reg) {
172 return visitor;
173 }
174 visitor = visitor->next_;
175 } while (visitor != this);
176
177 return nullptr;
178 }
179
180 BytecodeRegisterOptimizer::RegisterInfo*
GetEquivalentToMaterialize()181 BytecodeRegisterOptimizer::RegisterInfo::GetEquivalentToMaterialize() {
182 DCHECK(this->materialized());
183 RegisterInfo* visitor = this->next_;
184 RegisterInfo* best_info = nullptr;
185 while (visitor != this) {
186 if (visitor->materialized()) {
187 return nullptr;
188 }
189 if (visitor->allocated() &&
190 (best_info == nullptr ||
191 visitor->register_value() < best_info->register_value())) {
192 best_info = visitor;
193 }
194 visitor = visitor->next_;
195 }
196 return best_info;
197 }
198
MarkTemporariesAsUnmaterialized(Register temporary_base)199 void BytecodeRegisterOptimizer::RegisterInfo::MarkTemporariesAsUnmaterialized(
200 Register temporary_base) {
201 DCHECK(this->register_value() < temporary_base);
202 DCHECK(this->materialized());
203 RegisterInfo* visitor = this->next_;
204 while (visitor != this) {
205 if (visitor->register_value() >= temporary_base) {
206 visitor->set_materialized(false);
207 }
208 visitor = visitor->next_;
209 }
210 }
211
212 BytecodeRegisterOptimizer::RegisterInfo*
GetEquivalent()213 BytecodeRegisterOptimizer::RegisterInfo::GetEquivalent() {
214 return next_;
215 }
216
BytecodeRegisterOptimizer(Zone * zone,BytecodeRegisterAllocator * register_allocator,int fixed_registers_count,int parameter_count,BytecodeWriter * bytecode_writer)217 BytecodeRegisterOptimizer::BytecodeRegisterOptimizer(
218 Zone* zone, BytecodeRegisterAllocator* register_allocator,
219 int fixed_registers_count, int parameter_count,
220 BytecodeWriter* bytecode_writer)
221 : accumulator_(Register::virtual_accumulator()),
222 temporary_base_(fixed_registers_count),
223 max_register_index_(fixed_registers_count - 1),
224 register_info_table_(zone),
225 registers_needing_flushed_(zone),
226 equivalence_id_(0),
227 bytecode_writer_(bytecode_writer),
228 flush_required_(false),
229 zone_(zone) {
230 register_allocator->set_observer(this);
231
232 // Calculate offset so register index values can be mapped into
233 // a vector of register metadata.
234 // There is at least one parameter, which is the JS receiver.
235 DCHECK_NE(parameter_count, 0);
236 register_info_table_offset_ =
237 -Register::FromParameterIndex(0, parameter_count).index();
238
239 // Initialize register map for parameters, locals, and the
240 // accumulator.
241 register_info_table_.resize(register_info_table_offset_ +
242 static_cast<size_t>(temporary_base_.index()));
243 for (size_t i = 0; i < register_info_table_.size(); ++i) {
244 register_info_table_[i] = new (zone) RegisterInfo(
245 RegisterFromRegisterInfoTableIndex(i), NextEquivalenceId(), true, true);
246 DCHECK_EQ(register_info_table_[i]->register_value().index(),
247 RegisterFromRegisterInfoTableIndex(i).index());
248 }
249 accumulator_info_ = GetRegisterInfo(accumulator_);
250 DCHECK(accumulator_info_->register_value() == accumulator_);
251 }
252
PushToRegistersNeedingFlush(RegisterInfo * reg)253 void BytecodeRegisterOptimizer::PushToRegistersNeedingFlush(RegisterInfo* reg) {
254 if (!reg->needs_flush()) {
255 reg->set_needs_flush(true);
256 registers_needing_flushed_.push_back(reg);
257 }
258 }
259
EnsureAllRegistersAreFlushed() const260 bool BytecodeRegisterOptimizer::EnsureAllRegistersAreFlushed() const {
261 for (RegisterInfo* reg_info : register_info_table_) {
262 if (reg_info->needs_flush()) {
263 return false;
264 } else if (!reg_info->IsOnlyMemberOfEquivalenceSet()) {
265 return false;
266 } else if (reg_info->allocated() && !reg_info->materialized()) {
267 return false;
268 }
269 }
270 return true;
271 }
272
Flush()273 void BytecodeRegisterOptimizer::Flush() {
274 if (!flush_required_) {
275 return;
276 }
277
278 // Materialize all live registers and break equivalences.
279 for (RegisterInfo* reg_info : registers_needing_flushed_) {
280 if (!reg_info->needs_flush()) continue;
281 reg_info->set_needs_flush(false);
282
283 RegisterInfo* materialized = reg_info->materialized()
284 ? reg_info
285 : reg_info->GetMaterializedEquivalent();
286
287 if (materialized != nullptr) {
288 // Walk equivalents of materialized registers, materializing
289 // each equivalent register as necessary and placing in their
290 // own equivalence set.
291 RegisterInfo* equivalent;
292 while ((equivalent = materialized->GetEquivalent()) != materialized) {
293 if (equivalent->allocated() && !equivalent->materialized()) {
294 OutputRegisterTransfer(materialized, equivalent);
295 }
296 equivalent->MoveToNewEquivalenceSet(NextEquivalenceId(), true);
297 equivalent->set_needs_flush(false);
298 }
299 } else {
300 // Equivalernce class containing only unallocated registers.
301 DCHECK_NULL(reg_info->GetAllocatedEquivalent());
302 reg_info->MoveToNewEquivalenceSet(NextEquivalenceId(), false);
303 }
304 }
305
306 registers_needing_flushed_.clear();
307 DCHECK(EnsureAllRegistersAreFlushed());
308
309 flush_required_ = false;
310 }
311
OutputRegisterTransfer(RegisterInfo * input_info,RegisterInfo * output_info)312 void BytecodeRegisterOptimizer::OutputRegisterTransfer(
313 RegisterInfo* input_info, RegisterInfo* output_info) {
314 Register input = input_info->register_value();
315 Register output = output_info->register_value();
316 DCHECK_NE(input.index(), output.index());
317
318 if (input == accumulator_) {
319 bytecode_writer_->EmitStar(output);
320 } else if (output == accumulator_) {
321 bytecode_writer_->EmitLdar(input);
322 } else {
323 bytecode_writer_->EmitMov(input, output);
324 }
325 if (output != accumulator_) {
326 max_register_index_ = std::max(max_register_index_, output.index());
327 }
328 output_info->set_materialized(true);
329 }
330
CreateMaterializedEquivalent(RegisterInfo * info)331 void BytecodeRegisterOptimizer::CreateMaterializedEquivalent(
332 RegisterInfo* info) {
333 DCHECK(info->materialized());
334 RegisterInfo* unmaterialized = info->GetEquivalentToMaterialize();
335 if (unmaterialized) {
336 OutputRegisterTransfer(info, unmaterialized);
337 }
338 }
339
340 BytecodeRegisterOptimizer::RegisterInfo*
GetMaterializedEquivalent(RegisterInfo * info)341 BytecodeRegisterOptimizer::GetMaterializedEquivalent(RegisterInfo* info) {
342 return info->materialized() ? info : info->GetMaterializedEquivalent();
343 }
344
345 BytecodeRegisterOptimizer::RegisterInfo*
GetMaterializedEquivalentNotAccumulator(RegisterInfo * info)346 BytecodeRegisterOptimizer::GetMaterializedEquivalentNotAccumulator(
347 RegisterInfo* info) {
348 if (info->materialized()) {
349 return info;
350 }
351
352 RegisterInfo* result = info->GetMaterializedEquivalentOtherThan(accumulator_);
353 if (result == nullptr) {
354 Materialize(info);
355 result = info;
356 }
357 DCHECK(result->register_value() != accumulator_);
358 return result;
359 }
360
Materialize(RegisterInfo * info)361 void BytecodeRegisterOptimizer::Materialize(RegisterInfo* info) {
362 if (!info->materialized()) {
363 RegisterInfo* materialized = info->GetMaterializedEquivalent();
364 DCHECK_NOT_NULL(materialized);
365 OutputRegisterTransfer(materialized, info);
366 }
367 }
368
AddToEquivalenceSet(RegisterInfo * set_member,RegisterInfo * non_set_member)369 void BytecodeRegisterOptimizer::AddToEquivalenceSet(
370 RegisterInfo* set_member, RegisterInfo* non_set_member) {
371 // Equivalence class is now of size >= 2, so we make sure it will be flushed.
372 PushToRegistersNeedingFlush(non_set_member);
373 non_set_member->AddToEquivalenceSetOf(set_member);
374 // Flushing is only required when two or more registers are placed
375 // in the same equivalence set.
376 flush_required_ = true;
377 }
378
RegisterTransfer(RegisterInfo * input_info,RegisterInfo * output_info)379 void BytecodeRegisterOptimizer::RegisterTransfer(RegisterInfo* input_info,
380 RegisterInfo* output_info) {
381 bool output_is_observable =
382 RegisterIsObservable(output_info->register_value());
383 bool in_same_equivalence_set =
384 output_info->IsInSameEquivalenceSet(input_info);
385 if (in_same_equivalence_set &&
386 (!output_is_observable || output_info->materialized())) {
387 return; // Nothing more to do.
388 }
389
390 // Materialize an alternate in the equivalence set that
391 // |output_info| is leaving.
392 if (output_info->materialized()) {
393 CreateMaterializedEquivalent(output_info);
394 }
395
396 // Add |output_info| to new equivalence set.
397 if (!in_same_equivalence_set) {
398 AddToEquivalenceSet(input_info, output_info);
399 }
400
401 if (output_is_observable) {
402 // Force store to be emitted when register is observable.
403 output_info->set_materialized(false);
404 RegisterInfo* materialized_info = input_info->GetMaterializedEquivalent();
405 OutputRegisterTransfer(materialized_info, output_info);
406 }
407
408 bool input_is_observable = RegisterIsObservable(input_info->register_value());
409 if (input_is_observable) {
410 // If input is observable by the debugger, mark all other temporaries
411 // registers as unmaterialized so that this register is used in preference.
412 input_info->MarkTemporariesAsUnmaterialized(temporary_base_);
413 }
414 }
415
PrepareOutputRegister(Register reg)416 void BytecodeRegisterOptimizer::PrepareOutputRegister(Register reg) {
417 RegisterInfo* reg_info = GetRegisterInfo(reg);
418 if (reg_info->materialized()) {
419 CreateMaterializedEquivalent(reg_info);
420 }
421 reg_info->MoveToNewEquivalenceSet(NextEquivalenceId(), true);
422 max_register_index_ =
423 std::max(max_register_index_, reg_info->register_value().index());
424 }
425
PrepareOutputRegisterList(RegisterList reg_list)426 void BytecodeRegisterOptimizer::PrepareOutputRegisterList(
427 RegisterList reg_list) {
428 int start_index = reg_list.first_register().index();
429 for (int i = 0; i < reg_list.register_count(); ++i) {
430 Register current(start_index + i);
431 PrepareOutputRegister(current);
432 }
433 }
434
GetInputRegister(Register reg)435 Register BytecodeRegisterOptimizer::GetInputRegister(Register reg) {
436 RegisterInfo* reg_info = GetRegisterInfo(reg);
437 if (reg_info->materialized()) {
438 return reg;
439 } else {
440 RegisterInfo* equivalent_info =
441 GetMaterializedEquivalentNotAccumulator(reg_info);
442 return equivalent_info->register_value();
443 }
444 }
445
GetInputRegisterList(RegisterList reg_list)446 RegisterList BytecodeRegisterOptimizer::GetInputRegisterList(
447 RegisterList reg_list) {
448 if (reg_list.register_count() == 1) {
449 // If there is only a single register, treat it as a normal input register.
450 Register reg(GetInputRegister(reg_list.first_register()));
451 return RegisterList(reg);
452 } else {
453 int start_index = reg_list.first_register().index();
454 for (int i = 0; i < reg_list.register_count(); ++i) {
455 Register current(start_index + i);
456 RegisterInfo* input_info = GetRegisterInfo(current);
457 Materialize(input_info);
458 }
459 return reg_list;
460 }
461 }
462
GrowRegisterMap(Register reg)463 void BytecodeRegisterOptimizer::GrowRegisterMap(Register reg) {
464 DCHECK(RegisterIsTemporary(reg));
465 size_t index = GetRegisterInfoTableIndex(reg);
466 if (index >= register_info_table_.size()) {
467 size_t new_size = index + 1;
468 size_t old_size = register_info_table_.size();
469 register_info_table_.resize(new_size);
470 for (size_t i = old_size; i < new_size; ++i) {
471 register_info_table_[i] =
472 new (zone()) RegisterInfo(RegisterFromRegisterInfoTableIndex(i),
473 NextEquivalenceId(), true, false);
474 }
475 }
476 }
477
AllocateRegister(RegisterInfo * info)478 void BytecodeRegisterOptimizer::AllocateRegister(RegisterInfo* info) {
479 info->set_allocated(true);
480 if (!info->materialized()) {
481 info->MoveToNewEquivalenceSet(NextEquivalenceId(), true);
482 }
483 }
484
RegisterAllocateEvent(Register reg)485 void BytecodeRegisterOptimizer::RegisterAllocateEvent(Register reg) {
486 AllocateRegister(GetOrCreateRegisterInfo(reg));
487 }
488
RegisterListAllocateEvent(RegisterList reg_list)489 void BytecodeRegisterOptimizer::RegisterListAllocateEvent(
490 RegisterList reg_list) {
491 if (reg_list.register_count() != 0) {
492 int first_index = reg_list.first_register().index();
493 GrowRegisterMap(Register(first_index + reg_list.register_count() - 1));
494 for (int i = 0; i < reg_list.register_count(); i++) {
495 AllocateRegister(GetRegisterInfo(Register(first_index + i)));
496 }
497 }
498 }
499
RegisterListFreeEvent(RegisterList reg_list)500 void BytecodeRegisterOptimizer::RegisterListFreeEvent(RegisterList reg_list) {
501 int first_index = reg_list.first_register().index();
502 for (int i = 0; i < reg_list.register_count(); i++) {
503 GetRegisterInfo(Register(first_index + i))->set_allocated(false);
504 }
505 }
506
507 } // namespace interpreter
508 } // namespace internal
509 } // namespace v8
510