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 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
register_value() const59 Register register_value() const { return register_; }
materialized() const60 bool materialized() const { return materialized_; }
set_materialized(bool materialized)61 void set_materialized(bool materialized) { materialized_ = materialized; }
allocated() const62 bool allocated() const { return allocated_; }
set_allocated(bool allocated)63 void set_allocated(bool allocated) { allocated_ = allocated; }
set_equivalence_id(uint32_t equivalence_id)64 void set_equivalence_id(uint32_t equivalence_id) {
65 equivalence_id_ = equivalence_id;
66 }
equivalence_id() const67 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
AddToEquivalenceSetOf(RegisterInfo * info)82 void 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
MoveToNewEquivalenceSet(uint32_t equivalence_id,bool materialized)97 void 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
IsOnlyMemberOfEquivalenceSet() const106 bool BytecodeRegisterOptimizer::RegisterInfo::IsOnlyMemberOfEquivalenceSet()
107 const {
108 return this->next_ == this;
109 }
110
111 bool BytecodeRegisterOptimizer::RegisterInfo::
IsOnlyMaterializedMemberOfEquivalenceSet() const112 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
IsInSameEquivalenceSet(RegisterInfo * info) const125 bool BytecodeRegisterOptimizer::RegisterInfo::IsInSameEquivalenceSet(
126 RegisterInfo* info) const {
127 return equivalence_id() == info->equivalence_id();
128 }
129
130 BytecodeRegisterOptimizer::RegisterInfo*
GetMaterializedEquivalent()131 BytecodeRegisterOptimizer::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
143 BytecodeRegisterOptimizer::RegisterInfo*
GetMaterializedEquivalentOtherThan(Register reg)144 BytecodeRegisterOptimizer::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
157 BytecodeRegisterOptimizer::RegisterInfo*
GetEquivalentToMaterialize()158 BytecodeRegisterOptimizer::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
MarkTemporariesAsUnmaterialized(Register temporary_base)176 void 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
189 BytecodeRegisterOptimizer::RegisterInfo*
GetEquivalent()190 BytecodeRegisterOptimizer::RegisterInfo::GetEquivalent() {
191 return next_;
192 }
193
BytecodeRegisterOptimizer(Zone * zone,BytecodeRegisterAllocator * register_allocator,int fixed_registers_count,int parameter_count,BytecodePipelineStage * next_stage)194 BytecodeRegisterOptimizer::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
Flush()233 void 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
OutputRegisterTransfer(RegisterInfo * input_info,RegisterInfo * output_info,BytecodeSourceInfo source_info)259 void 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
CreateMaterializedEquivalent(RegisterInfo * info)286 void BytecodeRegisterOptimizer::CreateMaterializedEquivalent(
287 RegisterInfo* info) {
288 DCHECK(info->materialized());
289 RegisterInfo* unmaterialized = info->GetEquivalentToMaterialize();
290 if (unmaterialized) {
291 OutputRegisterTransfer(info, unmaterialized);
292 }
293 }
294
295 BytecodeRegisterOptimizer::RegisterInfo*
GetMaterializedEquivalent(RegisterInfo * info)296 BytecodeRegisterOptimizer::GetMaterializedEquivalent(RegisterInfo* info) {
297 return info->materialized() ? info : info->GetMaterializedEquivalent();
298 }
299
300 BytecodeRegisterOptimizer::RegisterInfo*
GetMaterializedEquivalentNotAccumulator(RegisterInfo * info)301 BytecodeRegisterOptimizer::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
Materialize(RegisterInfo * info)316 void BytecodeRegisterOptimizer::Materialize(RegisterInfo* info) {
317 if (!info->materialized()) {
318 RegisterInfo* materialized = info->GetMaterializedEquivalent();
319 OutputRegisterTransfer(materialized, info);
320 }
321 }
322
AddToEquivalenceSet(RegisterInfo * set_member,RegisterInfo * non_set_member)323 void 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
RegisterTransfer(RegisterInfo * input_info,RegisterInfo * output_info,BytecodeSourceInfo source_info)331 void 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
EmitNopForSourceInfo(BytecodeSourceInfo source_info) const365 void 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
PrepareOutputRegister(Register reg)372 void 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
PrepareOutputRegisterList(RegisterList reg_list)382 void 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
GetInputRegister(Register reg)391 Register 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
GetInputRegisterList(RegisterList reg_list)402 RegisterList 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
GrowRegisterMap(Register reg)419 void 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
RegisterAllocateEvent(Register reg)434 void BytecodeRegisterOptimizer::RegisterAllocateEvent(Register reg) {
435 GetOrCreateRegisterInfo(reg)->set_allocated(true);
436 }
437
RegisterListAllocateEvent(RegisterList reg_list)438 void 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
RegisterListFreeEvent(RegisterList reg_list)449 void 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