• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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