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        next_(this),
25        prev_(this) {}
26
27  void AddToEquivalenceSetOf(RegisterInfo* info);
28  void MoveToNewEquivalenceSet(uint32_t equivalence_id, bool materialized);
29  bool IsOnlyMemberOfEquivalenceSet() const;
30  bool IsOnlyMaterializedMemberOfEquivalenceSet() const;
31  bool IsInSameEquivalenceSet(RegisterInfo* info) const;
32
33  // Get a member of this register's equivalence set that is
34  // materialized. The materialized equivalent will be this register
35  // if it is materialized. Returns nullptr if no materialized
36  // equivalent exists.
37  RegisterInfo* GetMaterializedEquivalent();
38
39  // Get a member of this register's equivalence set that is
40  // materialized and not register |reg|. The materialized equivalent
41  // will be this register if it is materialized. Returns nullptr if
42  // no materialized equivalent exists.
43  RegisterInfo* GetMaterializedEquivalentOtherThan(Register reg);
44
45  // Get a member of this register's equivalence set that is intended
46  // to be materialized in place of this register (which is currently
47  // materialized). The best candidate is deemed to be the register
48  // with the lowest index as this permits temporary registers to be
49  // removed from the bytecode stream. Returns nullptr if no candidate
50  // exists.
51  RegisterInfo* GetEquivalentToMaterialize();
52
53  // Marks all temporary registers of the equivalence set as unmaterialized.
54  void MarkTemporariesAsUnmaterialized(Register temporary_base);
55
56  // Get an equivalent register. Returns this if none exists.
57  RegisterInfo* GetEquivalent();
58
59  Register register_value() const { return register_; }
60  bool materialized() const { return materialized_; }
61  void set_materialized(bool materialized) { materialized_ = materialized; }
62  bool allocated() const { return allocated_; }
63  void set_allocated(bool allocated) { allocated_ = allocated; }
64  void set_equivalence_id(uint32_t equivalence_id) {
65    equivalence_id_ = equivalence_id;
66  }
67  uint32_t equivalence_id() const { return equivalence_id_; }
68
69 private:
70  Register register_;
71  uint32_t equivalence_id_;
72  bool materialized_;
73  bool allocated_;
74
75  // Equivalence set pointers.
76  RegisterInfo* next_;
77  RegisterInfo* prev_;
78
79  DISALLOW_COPY_AND_ASSIGN(RegisterInfo);
80};
81
82void BytecodeRegisterOptimizer::RegisterInfo::AddToEquivalenceSetOf(
83    RegisterInfo* info) {
84  DCHECK_NE(kInvalidEquivalenceId, info->equivalence_id());
85  // Fix old list
86  next_->prev_ = prev_;
87  prev_->next_ = next_;
88  // Add to new list.
89  next_ = info->next_;
90  prev_ = info;
91  prev_->next_ = this;
92  next_->prev_ = this;
93  set_equivalence_id(info->equivalence_id());
94  set_materialized(false);
95}
96
97void BytecodeRegisterOptimizer::RegisterInfo::MoveToNewEquivalenceSet(
98    uint32_t equivalence_id, bool materialized) {
99  next_->prev_ = prev_;
100  prev_->next_ = next_;
101  next_ = prev_ = this;
102  equivalence_id_ = equivalence_id;
103  materialized_ = materialized;
104}
105
106bool BytecodeRegisterOptimizer::RegisterInfo::IsOnlyMemberOfEquivalenceSet()
107    const {
108  return this->next_ == this;
109}
110
111bool BytecodeRegisterOptimizer::RegisterInfo::
112    IsOnlyMaterializedMemberOfEquivalenceSet() const {
113  DCHECK(materialized());
114
115  const RegisterInfo* visitor = this->next_;
116  while (visitor != this) {
117    if (visitor->materialized()) {
118      return false;
119    }
120    visitor = visitor->next_;
121  }
122  return true;
123}
124
125bool BytecodeRegisterOptimizer::RegisterInfo::IsInSameEquivalenceSet(
126    RegisterInfo* info) const {
127  return equivalence_id() == info->equivalence_id();
128}
129
130BytecodeRegisterOptimizer::RegisterInfo*
131BytecodeRegisterOptimizer::RegisterInfo::GetMaterializedEquivalent() {
132  RegisterInfo* visitor = this;
133  do {
134    if (visitor->materialized()) {
135      return visitor;
136    }
137    visitor = visitor->next_;
138  } while (visitor != this);
139
140  return nullptr;
141}
142
143BytecodeRegisterOptimizer::RegisterInfo*
144BytecodeRegisterOptimizer::RegisterInfo::GetMaterializedEquivalentOtherThan(
145    Register reg) {
146  RegisterInfo* visitor = this;
147  do {
148    if (visitor->materialized() && visitor->register_value() != reg) {
149      return visitor;
150    }
151    visitor = visitor->next_;
152  } while (visitor != this);
153
154  return nullptr;
155}
156
157BytecodeRegisterOptimizer::RegisterInfo*
158BytecodeRegisterOptimizer::RegisterInfo::GetEquivalentToMaterialize() {
159  DCHECK(this->materialized());
160  RegisterInfo* visitor = this->next_;
161  RegisterInfo* best_info = nullptr;
162  while (visitor != this) {
163    if (visitor->materialized()) {
164      return nullptr;
165    }
166    if (visitor->allocated() &&
167        (best_info == nullptr ||
168         visitor->register_value() < best_info->register_value())) {
169      best_info = visitor;
170    }
171    visitor = visitor->next_;
172  }
173  return best_info;
174}
175
176void BytecodeRegisterOptimizer::RegisterInfo::MarkTemporariesAsUnmaterialized(
177    Register temporary_base) {
178  DCHECK(this->register_value() < temporary_base);
179  DCHECK(this->materialized());
180  RegisterInfo* visitor = this->next_;
181  while (visitor != this) {
182    if (visitor->register_value() >= temporary_base) {
183      visitor->set_materialized(false);
184    }
185    visitor = visitor->next_;
186  }
187}
188
189BytecodeRegisterOptimizer::RegisterInfo*
190BytecodeRegisterOptimizer::RegisterInfo::GetEquivalent() {
191  return next_;
192}
193
194BytecodeRegisterOptimizer::BytecodeRegisterOptimizer(
195    Zone* zone, BytecodeRegisterAllocator* register_allocator,
196    int fixed_registers_count, int parameter_count,
197    BytecodePipelineStage* next_stage)
198    : accumulator_(Register::virtual_accumulator()),
199      temporary_base_(fixed_registers_count),
200      max_register_index_(fixed_registers_count - 1),
201      register_info_table_(zone),
202      equivalence_id_(0),
203      next_stage_(next_stage),
204      flush_required_(false),
205      zone_(zone) {
206  register_allocator->set_observer(this);
207
208  // Calculate offset so register index values can be mapped into
209  // a vector of register metadata.
210  if (parameter_count != 0) {
211    register_info_table_offset_ =
212        -Register::FromParameterIndex(0, parameter_count).index();
213  } else {
214    // TODO(oth): This path shouldn't be necessary in bytecode generated
215    // from Javascript, but a set of tests do not include the JS receiver.
216    register_info_table_offset_ = -accumulator_.index();
217  }
218
219  // Initialize register map for parameters, locals, and the
220  // accumulator.
221  register_info_table_.resize(register_info_table_offset_ +
222                              static_cast<size_t>(temporary_base_.index()));
223  for (size_t i = 0; i < register_info_table_.size(); ++i) {
224    register_info_table_[i] = new (zone) RegisterInfo(
225        RegisterFromRegisterInfoTableIndex(i), NextEquivalenceId(), true, true);
226    DCHECK_EQ(register_info_table_[i]->register_value().index(),
227              RegisterFromRegisterInfoTableIndex(i).index());
228  }
229  accumulator_info_ = GetRegisterInfo(accumulator_);
230  DCHECK(accumulator_info_->register_value() == accumulator_);
231}
232
233void BytecodeRegisterOptimizer::Flush() {
234  if (!flush_required_) {
235    return;
236  }
237
238  // Materialize all live registers and break equivalences.
239  size_t count = register_info_table_.size();
240  for (size_t i = 0; i < count; ++i) {
241    RegisterInfo* reg_info = register_info_table_[i];
242    if (reg_info->materialized()) {
243      // Walk equivalents of materialized registers, materializing
244      // each equivalent register as necessary and placing in their
245      // own equivalence set.
246      RegisterInfo* equivalent;
247      while ((equivalent = reg_info->GetEquivalent()) != reg_info) {
248        if (equivalent->allocated() && !equivalent->materialized()) {
249          OutputRegisterTransfer(reg_info, equivalent);
250        }
251        equivalent->MoveToNewEquivalenceSet(NextEquivalenceId(), true);
252      }
253    }
254  }
255
256  flush_required_ = false;
257}
258
259void BytecodeRegisterOptimizer::OutputRegisterTransfer(
260    RegisterInfo* input_info, RegisterInfo* output_info,
261    BytecodeSourceInfo source_info) {
262  Register input = input_info->register_value();
263  Register output = output_info->register_value();
264  DCHECK_NE(input.index(), output.index());
265
266  if (input == accumulator_) {
267    uint32_t operand = static_cast<uint32_t>(output.ToOperand());
268    BytecodeNode node = BytecodeNode::Star(source_info, operand);
269    next_stage_->Write(&node);
270  } else if (output == accumulator_) {
271    uint32_t operand = static_cast<uint32_t>(input.ToOperand());
272    BytecodeNode node = BytecodeNode::Ldar(source_info, operand);
273    next_stage_->Write(&node);
274  } else {
275    uint32_t operand0 = static_cast<uint32_t>(input.ToOperand());
276    uint32_t operand1 = static_cast<uint32_t>(output.ToOperand());
277    BytecodeNode node = BytecodeNode::Mov(source_info, operand0, operand1);
278    next_stage_->Write(&node);
279  }
280  if (output != accumulator_) {
281    max_register_index_ = std::max(max_register_index_, output.index());
282  }
283  output_info->set_materialized(true);
284}
285
286void BytecodeRegisterOptimizer::CreateMaterializedEquivalent(
287    RegisterInfo* info) {
288  DCHECK(info->materialized());
289  RegisterInfo* unmaterialized = info->GetEquivalentToMaterialize();
290  if (unmaterialized) {
291    OutputRegisterTransfer(info, unmaterialized);
292  }
293}
294
295BytecodeRegisterOptimizer::RegisterInfo*
296BytecodeRegisterOptimizer::GetMaterializedEquivalent(RegisterInfo* info) {
297  return info->materialized() ? info : info->GetMaterializedEquivalent();
298}
299
300BytecodeRegisterOptimizer::RegisterInfo*
301BytecodeRegisterOptimizer::GetMaterializedEquivalentNotAccumulator(
302    RegisterInfo* info) {
303  if (info->materialized()) {
304    return info;
305  }
306
307  RegisterInfo* result = info->GetMaterializedEquivalentOtherThan(accumulator_);
308  if (result == nullptr) {
309    Materialize(info);
310    result = info;
311  }
312  DCHECK(result->register_value() != accumulator_);
313  return result;
314}
315
316void BytecodeRegisterOptimizer::Materialize(RegisterInfo* info) {
317  if (!info->materialized()) {
318    RegisterInfo* materialized = info->GetMaterializedEquivalent();
319    OutputRegisterTransfer(materialized, info);
320  }
321}
322
323void BytecodeRegisterOptimizer::AddToEquivalenceSet(
324    RegisterInfo* set_member, RegisterInfo* non_set_member) {
325  non_set_member->AddToEquivalenceSetOf(set_member);
326  // Flushing is only required when two or more registers are placed
327  // in the same equivalence set.
328  flush_required_ = true;
329}
330
331void BytecodeRegisterOptimizer::RegisterTransfer(
332    RegisterInfo* input_info, RegisterInfo* output_info,
333    BytecodeSourceInfo source_info) {
334  // Materialize an alternate in the equivalence set that
335  // |output_info| is leaving.
336  if (output_info->materialized()) {
337    CreateMaterializedEquivalent(output_info);
338  }
339
340  // Add |output_info| to new equivalence set.
341  if (!output_info->IsInSameEquivalenceSet(input_info)) {
342    AddToEquivalenceSet(input_info, output_info);
343  }
344
345  bool output_is_observable =
346      RegisterIsObservable(output_info->register_value());
347  if (output_is_observable) {
348    // Force store to be emitted when register is observable.
349    output_info->set_materialized(false);
350    RegisterInfo* materialized_info = input_info->GetMaterializedEquivalent();
351    OutputRegisterTransfer(materialized_info, output_info, source_info);
352  } else if (source_info.is_valid()) {
353    // Emit a placeholder nop to maintain source position info.
354    EmitNopForSourceInfo(source_info);
355  }
356
357  bool input_is_observable = RegisterIsObservable(input_info->register_value());
358  if (input_is_observable) {
359    // If input is observable by the debugger, mark all other temporaries
360    // registers as unmaterialized so that this register is used in preference.
361    input_info->MarkTemporariesAsUnmaterialized(temporary_base_);
362  }
363}
364
365void BytecodeRegisterOptimizer::EmitNopForSourceInfo(
366    BytecodeSourceInfo source_info) const {
367  DCHECK(source_info.is_valid());
368  BytecodeNode nop = BytecodeNode::Nop(source_info);
369  next_stage_->Write(&nop);
370}
371
372void BytecodeRegisterOptimizer::PrepareOutputRegister(Register reg) {
373  RegisterInfo* reg_info = GetRegisterInfo(reg);
374  if (reg_info->materialized()) {
375    CreateMaterializedEquivalent(reg_info);
376  }
377  reg_info->MoveToNewEquivalenceSet(NextEquivalenceId(), true);
378  max_register_index_ =
379      std::max(max_register_index_, reg_info->register_value().index());
380}
381
382void BytecodeRegisterOptimizer::PrepareOutputRegisterList(
383    RegisterList reg_list) {
384  int start_index = reg_list.first_register().index();
385  for (int i = 0; i < reg_list.register_count(); ++i) {
386    Register current(start_index + i);
387    PrepareOutputRegister(current);
388  }
389}
390
391Register BytecodeRegisterOptimizer::GetInputRegister(Register reg) {
392  RegisterInfo* reg_info = GetRegisterInfo(reg);
393  if (reg_info->materialized()) {
394    return reg;
395  } else {
396    RegisterInfo* equivalent_info =
397        GetMaterializedEquivalentNotAccumulator(reg_info);
398    return equivalent_info->register_value();
399  }
400}
401
402RegisterList BytecodeRegisterOptimizer::GetInputRegisterList(
403    RegisterList reg_list) {
404  if (reg_list.register_count() == 1) {
405    // If there is only a single register, treat it as a normal input register.
406    Register reg(GetInputRegister(reg_list.first_register()));
407    return RegisterList(reg.index(), 1);
408  } else {
409    int start_index = reg_list.first_register().index();
410    for (int i = 0; i < reg_list.register_count(); ++i) {
411      Register current(start_index + i);
412      RegisterInfo* input_info = GetRegisterInfo(current);
413      Materialize(input_info);
414    }
415    return reg_list;
416  }
417}
418
419void BytecodeRegisterOptimizer::GrowRegisterMap(Register reg) {
420  DCHECK(RegisterIsTemporary(reg));
421  size_t index = GetRegisterInfoTableIndex(reg);
422  if (index >= register_info_table_.size()) {
423    size_t new_size = index + 1;
424    size_t old_size = register_info_table_.size();
425    register_info_table_.resize(new_size);
426    for (size_t i = old_size; i < new_size; ++i) {
427      register_info_table_[i] =
428          new (zone()) RegisterInfo(RegisterFromRegisterInfoTableIndex(i),
429                                    NextEquivalenceId(), false, false);
430    }
431  }
432}
433
434void BytecodeRegisterOptimizer::RegisterAllocateEvent(Register reg) {
435  GetOrCreateRegisterInfo(reg)->set_allocated(true);
436}
437
438void BytecodeRegisterOptimizer::RegisterListAllocateEvent(
439    RegisterList reg_list) {
440  if (reg_list.register_count() != 0) {
441    int first_index = reg_list.first_register().index();
442    GrowRegisterMap(Register(first_index + reg_list.register_count() - 1));
443    for (int i = 0; i < reg_list.register_count(); i++) {
444      GetRegisterInfo(Register(first_index + i))->set_allocated(true);
445    }
446  }
447}
448
449void BytecodeRegisterOptimizer::RegisterListFreeEvent(RegisterList reg_list) {
450  int first_index = reg_list.first_register().index();
451  for (int i = 0; i < reg_list.register_count(); i++) {
452    GetRegisterInfo(Register(first_index + i))->set_allocated(false);
453  }
454}
455
456}  // namespace interpreter
457}  // namespace internal
458}  // namespace v8
459