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
7namespace v8 {
8namespace internal {
9namespace interpreter {
10
11const 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.
16class BytecodeRegisterOptimizer::RegisterInfo final : public ZoneObject {
17 public:
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  RegisterInfo(const RegisterInfo&) = delete;
28  RegisterInfo& operator=(const RegisterInfo&) = delete;
29
30  void AddToEquivalenceSetOf(RegisterInfo* info);
31  void MoveToNewEquivalenceSet(uint32_t equivalence_id, bool materialized);
32  bool IsOnlyMemberOfEquivalenceSet() const;
33  bool IsOnlyMaterializedMemberOfEquivalenceSet() const;
34  bool IsInSameEquivalenceSet(RegisterInfo* info) const;
35
36  // Get a member of the register's equivalence set that is allocated.
37  // Returns itself if allocated, and nullptr if there is no unallocated
38  // equivalent register.
39  RegisterInfo* GetAllocatedEquivalent();
40
41  // Get a member of this register's equivalence set that is
42  // materialized. The materialized equivalent will be this register
43  // if it is materialized. Returns nullptr if no materialized
44  // equivalent exists.
45  RegisterInfo* GetMaterializedEquivalent();
46
47  // Get a member of this register's equivalence set that is
48  // materialized and not register |reg|. The materialized equivalent
49  // will be this register if it is materialized. Returns nullptr if
50  // no materialized equivalent exists.
51  RegisterInfo* GetMaterializedEquivalentOtherThan(Register reg);
52
53  // Get a member of this register's equivalence set that is intended
54  // to be materialized in place of this register (which is currently
55  // materialized). The best candidate is deemed to be the register
56  // with the lowest index as this permits temporary registers to be
57  // removed from the bytecode stream. Returns nullptr if no candidate
58  // exists.
59  RegisterInfo* GetEquivalentToMaterialize();
60
61  // Marks all temporary registers of the equivalence set as unmaterialized.
62  void MarkTemporariesAsUnmaterialized(Register temporary_base);
63
64  // Get an equivalent register. Returns this if none exists.
65  RegisterInfo* GetEquivalent();
66
67  Register register_value() const { return register_; }
68  bool materialized() const { return materialized_; }
69  void set_materialized(bool materialized) { materialized_ = materialized; }
70  bool allocated() const { return allocated_; }
71  void set_allocated(bool allocated) { allocated_ = allocated; }
72  void set_equivalence_id(uint32_t equivalence_id) {
73    equivalence_id_ = equivalence_id;
74  }
75  uint32_t equivalence_id() const { return equivalence_id_; }
76  // Indicates if a register should be processed when calling Flush().
77  bool needs_flush() const { return needs_flush_; }
78  void set_needs_flush(bool needs_flush) { needs_flush_ = needs_flush; }
79
80 private:
81  Register register_;
82  uint32_t equivalence_id_;
83  bool materialized_;
84  bool allocated_;
85  bool needs_flush_;
86
87  // Equivalence set pointers.
88  RegisterInfo* next_;
89  RegisterInfo* prev_;
90};
91
92void 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
107void 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
116bool BytecodeRegisterOptimizer::RegisterInfo::IsOnlyMemberOfEquivalenceSet()
117    const {
118  return this->next_ == this;
119}
120
121bool BytecodeRegisterOptimizer::RegisterInfo::
122    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
135bool BytecodeRegisterOptimizer::RegisterInfo::IsInSameEquivalenceSet(
136    RegisterInfo* info) const {
137  return equivalence_id() == info->equivalence_id();
138}
139
140BytecodeRegisterOptimizer::RegisterInfo*
141BytecodeRegisterOptimizer::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
153BytecodeRegisterOptimizer::RegisterInfo*
154BytecodeRegisterOptimizer::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
166BytecodeRegisterOptimizer::RegisterInfo*
167BytecodeRegisterOptimizer::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
180BytecodeRegisterOptimizer::RegisterInfo*
181BytecodeRegisterOptimizer::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
199void 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
212BytecodeRegisterOptimizer::RegisterInfo*
213BytecodeRegisterOptimizer::RegisterInfo::GetEquivalent() {
214  return next_;
215}
216
217BytecodeRegisterOptimizer::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  int first_slot_index = parameter_count - 1;
237  register_info_table_offset_ =
238      -Register::FromParameterIndex(first_slot_index).index();
239
240  // Initialize register map for parameters, locals, and the
241  // accumulator.
242  register_info_table_.resize(register_info_table_offset_ +
243                              static_cast<size_t>(temporary_base_.index()));
244  for (size_t i = 0; i < register_info_table_.size(); ++i) {
245    register_info_table_[i] = zone->New<RegisterInfo>(
246        RegisterFromRegisterInfoTableIndex(i), NextEquivalenceId(), true, true);
247    DCHECK_EQ(register_info_table_[i]->register_value().index(),
248              RegisterFromRegisterInfoTableIndex(i).index());
249  }
250  accumulator_info_ = GetRegisterInfo(accumulator_);
251  DCHECK(accumulator_info_->register_value() == accumulator_);
252}
253
254void BytecodeRegisterOptimizer::PushToRegistersNeedingFlush(RegisterInfo* reg) {
255  if (!reg->needs_flush()) {
256    reg->set_needs_flush(true);
257    registers_needing_flushed_.push_back(reg);
258  }
259}
260
261bool BytecodeRegisterOptimizer::EnsureAllRegistersAreFlushed() const {
262  for (RegisterInfo* reg_info : register_info_table_) {
263    if (reg_info->needs_flush()) {
264      return false;
265    } else if (!reg_info->IsOnlyMemberOfEquivalenceSet()) {
266      return false;
267    } else if (reg_info->allocated() && !reg_info->materialized()) {
268      return false;
269    }
270  }
271  return true;
272}
273
274void BytecodeRegisterOptimizer::Flush() {
275  if (!flush_required_) {
276    return;
277  }
278
279  // Materialize all live registers and break equivalences.
280  for (RegisterInfo* reg_info : registers_needing_flushed_) {
281    if (!reg_info->needs_flush()) continue;
282    reg_info->set_needs_flush(false);
283
284    RegisterInfo* materialized = reg_info->materialized()
285                                     ? reg_info
286                                     : reg_info->GetMaterializedEquivalent();
287
288    if (materialized != nullptr) {
289      // Walk equivalents of materialized registers, materializing
290      // each equivalent register as necessary and placing in their
291      // own equivalence set.
292      RegisterInfo* equivalent;
293      while ((equivalent = materialized->GetEquivalent()) != materialized) {
294        if (equivalent->allocated() && !equivalent->materialized()) {
295          OutputRegisterTransfer(materialized, equivalent);
296        }
297        equivalent->MoveToNewEquivalenceSet(NextEquivalenceId(), true);
298        equivalent->set_needs_flush(false);
299      }
300    } else {
301      // Equivalernce class containing only unallocated registers.
302      DCHECK_NULL(reg_info->GetAllocatedEquivalent());
303      reg_info->MoveToNewEquivalenceSet(NextEquivalenceId(), false);
304    }
305  }
306
307  registers_needing_flushed_.clear();
308  DCHECK(EnsureAllRegistersAreFlushed());
309
310  flush_required_ = false;
311}
312
313void BytecodeRegisterOptimizer::OutputRegisterTransfer(
314    RegisterInfo* input_info, RegisterInfo* output_info) {
315  Register input = input_info->register_value();
316  Register output = output_info->register_value();
317  DCHECK_NE(input.index(), output.index());
318
319  if (input == accumulator_) {
320    bytecode_writer_->EmitStar(output);
321  } else if (output == accumulator_) {
322    bytecode_writer_->EmitLdar(input);
323  } else {
324    bytecode_writer_->EmitMov(input, output);
325  }
326  if (output != accumulator_) {
327    max_register_index_ = std::max(max_register_index_, output.index());
328  }
329  output_info->set_materialized(true);
330}
331
332void BytecodeRegisterOptimizer::CreateMaterializedEquivalent(
333    RegisterInfo* info) {
334  DCHECK(info->materialized());
335  RegisterInfo* unmaterialized = info->GetEquivalentToMaterialize();
336  if (unmaterialized) {
337    OutputRegisterTransfer(info, unmaterialized);
338  }
339}
340
341BytecodeRegisterOptimizer::RegisterInfo*
342BytecodeRegisterOptimizer::GetMaterializedEquivalent(RegisterInfo* info) {
343  return info->materialized() ? info : info->GetMaterializedEquivalent();
344}
345
346BytecodeRegisterOptimizer::RegisterInfo*
347BytecodeRegisterOptimizer::GetMaterializedEquivalentNotAccumulator(
348    RegisterInfo* info) {
349  if (info->materialized()) {
350    return info;
351  }
352
353  RegisterInfo* result = info->GetMaterializedEquivalentOtherThan(accumulator_);
354  if (result == nullptr) {
355    Materialize(info);
356    result = info;
357  }
358  DCHECK(result->register_value() != accumulator_);
359  return result;
360}
361
362void BytecodeRegisterOptimizer::Materialize(RegisterInfo* info) {
363  if (!info->materialized()) {
364    RegisterInfo* materialized = info->GetMaterializedEquivalent();
365    DCHECK_NOT_NULL(materialized);
366    OutputRegisterTransfer(materialized, info);
367  }
368}
369
370void BytecodeRegisterOptimizer::AddToEquivalenceSet(
371    RegisterInfo* set_member, RegisterInfo* non_set_member) {
372  // Equivalence class is now of size >= 2, so we make sure it will be flushed.
373  PushToRegistersNeedingFlush(non_set_member);
374  non_set_member->AddToEquivalenceSetOf(set_member);
375  // Flushing is only required when two or more registers are placed
376  // in the same equivalence set.
377  flush_required_ = true;
378}
379
380void BytecodeRegisterOptimizer::RegisterTransfer(RegisterInfo* input_info,
381                                                 RegisterInfo* output_info) {
382  bool output_is_observable =
383      RegisterIsObservable(output_info->register_value());
384  bool in_same_equivalence_set =
385      output_info->IsInSameEquivalenceSet(input_info);
386  if (in_same_equivalence_set &&
387      (!output_is_observable || output_info->materialized())) {
388    return;  // Nothing more to do.
389  }
390
391  // Materialize an alternate in the equivalence set that
392  // |output_info| is leaving.
393  if (output_info->materialized()) {
394    CreateMaterializedEquivalent(output_info);
395  }
396
397  // Add |output_info| to new equivalence set.
398  if (!in_same_equivalence_set) {
399    AddToEquivalenceSet(input_info, output_info);
400  }
401
402  if (output_is_observable) {
403    // Force store to be emitted when register is observable.
404    output_info->set_materialized(false);
405    RegisterInfo* materialized_info = input_info->GetMaterializedEquivalent();
406    OutputRegisterTransfer(materialized_info, output_info);
407  }
408
409  bool input_is_observable = RegisterIsObservable(input_info->register_value());
410  if (input_is_observable) {
411    // If input is observable by the debugger, mark all other temporaries
412    // registers as unmaterialized so that this register is used in preference.
413    input_info->MarkTemporariesAsUnmaterialized(temporary_base_);
414  }
415}
416
417void BytecodeRegisterOptimizer::PrepareOutputRegister(Register reg) {
418  RegisterInfo* reg_info = GetRegisterInfo(reg);
419  if (reg_info->materialized()) {
420    CreateMaterializedEquivalent(reg_info);
421  }
422  reg_info->MoveToNewEquivalenceSet(NextEquivalenceId(), true);
423  max_register_index_ =
424      std::max(max_register_index_, reg_info->register_value().index());
425}
426
427void BytecodeRegisterOptimizer::PrepareOutputRegisterList(
428    RegisterList reg_list) {
429  int start_index = reg_list.first_register().index();
430  for (int i = 0; i < reg_list.register_count(); ++i) {
431    Register current(start_index + i);
432    PrepareOutputRegister(current);
433  }
434}
435
436Register BytecodeRegisterOptimizer::GetInputRegister(Register reg) {
437  RegisterInfo* reg_info = GetRegisterInfo(reg);
438  if (reg_info->materialized()) {
439    return reg;
440  } else {
441    RegisterInfo* equivalent_info =
442        GetMaterializedEquivalentNotAccumulator(reg_info);
443    return equivalent_info->register_value();
444  }
445}
446
447RegisterList BytecodeRegisterOptimizer::GetInputRegisterList(
448    RegisterList reg_list) {
449  if (reg_list.register_count() == 1) {
450    // If there is only a single register, treat it as a normal input register.
451    Register reg(GetInputRegister(reg_list.first_register()));
452    return RegisterList(reg);
453  } else {
454    int start_index = reg_list.first_register().index();
455    for (int i = 0; i < reg_list.register_count(); ++i) {
456      Register current(start_index + i);
457      RegisterInfo* input_info = GetRegisterInfo(current);
458      Materialize(input_info);
459    }
460    return reg_list;
461  }
462}
463
464void BytecodeRegisterOptimizer::GrowRegisterMap(Register reg) {
465  DCHECK(RegisterIsTemporary(reg));
466  size_t index = GetRegisterInfoTableIndex(reg);
467  if (index >= register_info_table_.size()) {
468    size_t new_size = index + 1;
469    size_t old_size = register_info_table_.size();
470    register_info_table_.resize(new_size);
471    for (size_t i = old_size; i < new_size; ++i) {
472      register_info_table_[i] =
473          zone()->New<RegisterInfo>(RegisterFromRegisterInfoTableIndex(i),
474                                    NextEquivalenceId(), true, false);
475    }
476  }
477}
478
479void BytecodeRegisterOptimizer::AllocateRegister(RegisterInfo* info) {
480  info->set_allocated(true);
481  if (!info->materialized()) {
482    info->MoveToNewEquivalenceSet(NextEquivalenceId(), true);
483  }
484}
485
486void BytecodeRegisterOptimizer::RegisterAllocateEvent(Register reg) {
487  AllocateRegister(GetOrCreateRegisterInfo(reg));
488}
489
490void BytecodeRegisterOptimizer::RegisterListAllocateEvent(
491    RegisterList reg_list) {
492  if (reg_list.register_count() != 0) {
493    int first_index = reg_list.first_register().index();
494    GrowRegisterMap(Register(first_index + reg_list.register_count() - 1));
495    for (int i = 0; i < reg_list.register_count(); i++) {
496      AllocateRegister(GetRegisterInfo(Register(first_index + i)));
497    }
498  }
499}
500
501void BytecodeRegisterOptimizer::RegisterListFreeEvent(RegisterList reg_list) {
502  int first_index = reg_list.first_register().index();
503  for (int i = 0; i < reg_list.register_count(); i++) {
504    GetRegisterInfo(Register(first_index + i))->set_allocated(false);
505  }
506}
507
508}  // namespace interpreter
509}  // namespace internal
510}  // namespace v8
511