Line data Source code
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:
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 26260246 : 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 :
65 : Register register_value() const { return register_; }
66 : bool materialized() const { return materialized_; }
67 62609386 : void set_materialized(bool materialized) { materialized_ = materialized; }
68 : bool allocated() const { return allocated_; }
69 46442605 : void set_allocated(bool allocated) { allocated_ = allocated; }
70 : void set_equivalence_id(uint32_t equivalence_id) {
71 31602938 : equivalence_id_ = equivalence_id;
72 : }
73 : uint32_t equivalence_id() const { return equivalence_id_; }
74 : // Indicates if a register should be processed when calling Flush().
75 : bool needs_flush() const { return needs_flush_; }
76 31329178 : 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 :
92 0 : void BytecodeRegisterOptimizer::RegisterInfo::AddToEquivalenceSetOf(
93 31602938 : RegisterInfo* info) {
94 : DCHECK_NE(kInvalidEquivalenceId, info->equivalence_id());
95 : // Fix old list
96 31602938 : next_->prev_ = prev_;
97 31602938 : prev_->next_ = next_;
98 : // Add to new list.
99 31602938 : next_ = info->next_;
100 31602938 : prev_ = info;
101 31602938 : prev_->next_ = this;
102 31602938 : next_->prev_ = this;
103 : set_equivalence_id(info->equivalence_id());
104 : set_materialized(false);
105 0 : }
106 :
107 0 : void BytecodeRegisterOptimizer::RegisterInfo::MoveToNewEquivalenceSet(
108 : uint32_t equivalence_id, bool materialized) {
109 46602858 : next_->prev_ = prev_;
110 46602858 : prev_->next_ = next_;
111 46602858 : next_ = prev_ = this;
112 46602858 : equivalence_id_ = equivalence_id;
113 46602858 : materialized_ = materialized;
114 0 : }
115 :
116 0 : bool BytecodeRegisterOptimizer::RegisterInfo::IsOnlyMemberOfEquivalenceSet()
117 : const {
118 0 : return this->next_ == this;
119 : }
120 :
121 0 : bool BytecodeRegisterOptimizer::RegisterInfo::
122 : IsOnlyMaterializedMemberOfEquivalenceSet() const {
123 : DCHECK(materialized());
124 :
125 0 : const RegisterInfo* visitor = this->next_;
126 0 : while (visitor != this) {
127 0 : if (visitor->materialized()) {
128 : return false;
129 : }
130 0 : visitor = visitor->next_;
131 : }
132 : return true;
133 : }
134 :
135 0 : bool BytecodeRegisterOptimizer::RegisterInfo::IsInSameEquivalenceSet(
136 33252234 : RegisterInfo* info) const {
137 33252234 : return equivalence_id() == info->equivalence_id();
138 : }
139 :
140 : BytecodeRegisterOptimizer::RegisterInfo*
141 0 : BytecodeRegisterOptimizer::RegisterInfo::GetAllocatedEquivalent() {
142 0 : RegisterInfo* visitor = this;
143 0 : do {
144 0 : if (visitor->allocated()) {
145 : return visitor;
146 : }
147 0 : visitor = visitor->next_;
148 : } while (visitor != this);
149 :
150 : return nullptr;
151 : }
152 :
153 : BytecodeRegisterOptimizer::RegisterInfo*
154 0 : BytecodeRegisterOptimizer::RegisterInfo::GetMaterializedEquivalent() {
155 17743696 : RegisterInfo* visitor = this;
156 9249718 : do {
157 17743696 : if (visitor->materialized()) {
158 : return visitor;
159 : }
160 9249718 : visitor = visitor->next_;
161 : } while (visitor != this);
162 :
163 : return nullptr;
164 : }
165 :
166 : BytecodeRegisterOptimizer::RegisterInfo*
167 0 : BytecodeRegisterOptimizer::RegisterInfo::GetMaterializedEquivalentOtherThan(
168 : Register reg) {
169 9110370 : RegisterInfo* visitor = this;
170 4879084 : do {
171 9110370 : if (visitor->materialized() && visitor->register_value() != reg) {
172 : return visitor;
173 : }
174 4879084 : visitor = visitor->next_;
175 : } while (visitor != this);
176 :
177 : return nullptr;
178 : }
179 :
180 : BytecodeRegisterOptimizer::RegisterInfo*
181 68871329 : BytecodeRegisterOptimizer::RegisterInfo::GetEquivalentToMaterialize() {
182 : DCHECK(this->materialized());
183 115320532 : RegisterInfo* visitor = this->next_;
184 : RegisterInfo* best_info = nullptr;
185 158586401 : while (visitor != this) {
186 25605460 : if (visitor->materialized()) {
187 : return nullptr;
188 : }
189 41687486 : if (visitor->allocated() &&
190 162455 : (best_info == nullptr ||
191 : visitor->register_value() < best_info->register_value())) {
192 : best_info = visitor;
193 : }
194 20843743 : visitor = visitor->next_;
195 : }
196 : return best_info;
197 : }
198 :
199 0 : void BytecodeRegisterOptimizer::RegisterInfo::MarkTemporariesAsUnmaterialized(
200 : Register temporary_base) {
201 : DCHECK(this->register_value() < temporary_base);
202 : DCHECK(this->materialized());
203 5649171 : RegisterInfo* visitor = this->next_;
204 14408374 : while (visitor != this) {
205 8759203 : if (visitor->register_value() >= temporary_base) {
206 : visitor->set_materialized(false);
207 : }
208 8759203 : visitor = visitor->next_;
209 : }
210 0 : }
211 :
212 : BytecodeRegisterOptimizer::RegisterInfo*
213 0 : BytecodeRegisterOptimizer::RegisterInfo::GetEquivalent() {
214 17152766 : return next_;
215 : }
216 :
217 2106751 : BytecodeRegisterOptimizer::BytecodeRegisterOptimizer(
218 : Zone* zone, BytecodeRegisterAllocator* register_allocator,
219 : int fixed_registers_count, int parameter_count,
220 19166099 : BytecodeWriter* bytecode_writer)
221 : : accumulator_(Register::virtual_accumulator()),
222 : temporary_base_(fixed_registers_count),
223 2106752 : 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 6320270 : zone_(zone) {
230 2106767 : 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 4213534 : -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 44652490 : static_cast<size_t>(temporary_base_.index()));
243 42545744 : for (size_t i = 0; i < register_info_table_.size(); ++i) {
244 : register_info_table_[i] = new (zone) RegisterInfo(
245 38332183 : RegisterFromRegisterInfoTableIndex(i), NextEquivalenceId(), true, true);
246 : DCHECK_EQ(register_info_table_[i]->register_value().index(),
247 : RegisterFromRegisterInfoTableIndex(i).index());
248 : }
249 2106773 : accumulator_info_ = GetRegisterInfo(accumulator_);
250 : DCHECK(accumulator_info_->register_value() == accumulator_);
251 2106773 : }
252 :
253 0 : void BytecodeRegisterOptimizer::PushToRegistersNeedingFlush(RegisterInfo* reg) {
254 31602990 : if (!reg->needs_flush()) {
255 : reg->set_needs_flush(true);
256 14157293 : registers_needing_flushed_.push_back(reg);
257 : }
258 0 : }
259 :
260 0 : bool BytecodeRegisterOptimizer::EnsureAllRegistersAreFlushed() const {
261 0 : for (RegisterInfo* reg_info : register_info_table_) {
262 0 : if (reg_info->needs_flush()) {
263 : return false;
264 0 : } else if (!reg_info->IsOnlyMemberOfEquivalenceSet()) {
265 : return false;
266 0 : } else if (reg_info->allocated() && !reg_info->materialized()) {
267 : return false;
268 : }
269 : }
270 : return true;
271 : }
272 :
273 6937716 : void BytecodeRegisterOptimizer::Flush() {
274 6937716 : if (!flush_required_) {
275 6937812 : return;
276 : }
277 :
278 : // Materialize all live registers and break equivalences.
279 45427535 : for (RegisterInfo* reg_info : registers_needing_flushed_) {
280 14029601 : if (!reg_info->needs_flush()) continue;
281 : reg_info->set_needs_flush(false);
282 :
283 : RegisterInfo* materialized = reg_info->materialized()
284 : ? reg_info
285 13269501 : : reg_info->GetMaterializedEquivalent();
286 :
287 13269501 : 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 6459912 : RegisterInfo* equivalent;
292 17152766 : while ((equivalent = materialized->GetEquivalent()) != materialized) {
293 6459912 : if (equivalent->allocated() && !equivalent->materialized()) {
294 635794 : OutputRegisterTransfer(materialized, equivalent);
295 : }
296 3902377 : 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 19119 : reg_info->MoveToNewEquivalenceSet(NextEquivalenceId(), false);
303 : }
304 : }
305 :
306 4098832 : registers_needing_flushed_.clear();
307 : DCHECK(EnsureAllRegistersAreFlushed());
308 :
309 4098864 : flush_required_ = false;
310 : }
311 :
312 25062520 : 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 25062520 : if (input == accumulator_) {
319 19942120 : bytecode_writer_->EmitStar(output);
320 5120400 : } else if (output == accumulator_) {
321 3776842 : bytecode_writer_->EmitLdar(input);
322 : } else {
323 1343558 : bytecode_writer_->EmitMov(input, output);
324 : }
325 25059824 : if (output != accumulator_) {
326 42565864 : max_register_index_ = std::max(max_register_index_, output.index());
327 : }
328 : output_info->set_materialized(true);
329 25059824 : }
330 :
331 68871144 : void BytecodeRegisterOptimizer::CreateMaterializedEquivalent(
332 : RegisterInfo* info) {
333 : DCHECK(info->materialized());
334 68871144 : RegisterInfo* unmaterialized = info->GetEquivalentToMaterialize();
335 68872035 : if (unmaterialized) {
336 17519531 : OutputRegisterTransfer(info, unmaterialized);
337 : }
338 68869660 : }
339 :
340 : BytecodeRegisterOptimizer::RegisterInfo*
341 0 : BytecodeRegisterOptimizer::GetMaterializedEquivalent(RegisterInfo* info) {
342 0 : return info->materialized() ? info : info->GetMaterializedEquivalent();
343 : }
344 :
345 : BytecodeRegisterOptimizer::RegisterInfo*
346 4235802 : BytecodeRegisterOptimizer::GetMaterializedEquivalentNotAccumulator(
347 4235802 : RegisterInfo* info) {
348 4235802 : if (info->materialized()) {
349 : return info;
350 : }
351 :
352 : RegisterInfo* result = info->GetMaterializedEquivalentOtherThan(accumulator_);
353 4235808 : if (result == nullptr) {
354 4522 : Materialize(info);
355 : result = info;
356 : }
357 : DCHECK(result->register_value() != accumulator_);
358 4235816 : return result;
359 : }
360 :
361 24541017 : void BytecodeRegisterOptimizer::Materialize(RegisterInfo* info) {
362 24541017 : if (!info->materialized()) {
363 : RegisterInfo* materialized = info->GetMaterializedEquivalent();
364 : DCHECK_NOT_NULL(materialized);
365 4405703 : OutputRegisterTransfer(materialized, info);
366 : }
367 24541078 : }
368 :
369 31602990 : 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 31602938 : flush_required_ = true;
377 31602938 : }
378 :
379 33252234 : void BytecodeRegisterOptimizer::RegisterTransfer(RegisterInfo* input_info,
380 31604966 : 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 66504468 : if (in_same_equivalence_set &&
386 1713 : (!output_is_observable || output_info->materialized())) {
387 33253855 : return; // Nothing more to do.
388 : }
389 :
390 : // Materialize an alternate in the equivalence set that
391 : // |output_info| is leaving.
392 31603253 : if (output_info->materialized()) {
393 31098984 : CreateMaterializedEquivalent(output_info);
394 : }
395 :
396 : // Add |output_info| to new equivalence set.
397 31604293 : if (!in_same_equivalence_set) {
398 31603158 : AddToEquivalenceSet(input_info, output_info);
399 : }
400 :
401 31604828 : 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 2501594 : OutputRegisterTransfer(materialized_info, output_info);
406 : }
407 :
408 : bool input_is_observable = RegisterIsObservable(input_info->register_value());
409 31604874 : 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 :
416 39552602 : void BytecodeRegisterOptimizer::PrepareOutputRegister(Register reg) {
417 39552602 : RegisterInfo* reg_info = GetRegisterInfo(reg);
418 39552602 : if (reg_info->materialized()) {
419 37795030 : CreateMaterializedEquivalent(reg_info);
420 : }
421 39550945 : reg_info->MoveToNewEquivalenceSet(NextEquivalenceId(), true);
422 : max_register_index_ =
423 79102794 : std::max(max_register_index_, reg_info->register_value().index());
424 39551397 : }
425 :
426 32891 : void BytecodeRegisterOptimizer::PrepareOutputRegisterList(
427 : RegisterList reg_list) {
428 : int start_index = reg_list.first_register().index();
429 175778 : for (int i = 0; i < reg_list.register_count(); ++i) {
430 142888 : Register current(start_index + i);
431 142888 : PrepareOutputRegister(current);
432 : }
433 32890 : }
434 :
435 16315666 : Register BytecodeRegisterOptimizer::GetInputRegister(Register reg) {
436 16315666 : RegisterInfo* reg_info = GetRegisterInfo(reg);
437 16315666 : if (reg_info->materialized()) {
438 12079861 : return reg;
439 : } else {
440 : RegisterInfo* equivalent_info =
441 4235805 : GetMaterializedEquivalentNotAccumulator(reg_info);
442 : return equivalent_info->register_value();
443 : }
444 : }
445 :
446 2810139 : RegisterList BytecodeRegisterOptimizer::GetInputRegisterList(
447 : RegisterList reg_list) {
448 2810139 : if (reg_list.register_count() == 1) {
449 : // If there is only a single register, treat it as a normal input register.
450 683363 : Register reg(GetInputRegister(reg_list.first_register()));
451 683357 : return RegisterList(reg);
452 : } else {
453 : int start_index = reg_list.first_register().index();
454 9821394 : for (int i = 0; i < reg_list.register_count(); ++i) {
455 7694582 : Register current(start_index + i);
456 : RegisterInfo* input_info = GetRegisterInfo(current);
457 7694582 : Materialize(input_info);
458 : }
459 2126812 : return reg_list;
460 : }
461 : }
462 :
463 20803278 : void BytecodeRegisterOptimizer::GrowRegisterMap(Register reg) {
464 : DCHECK(RegisterIsTemporary(reg));
465 : size_t index = GetRegisterInfoTableIndex(reg);
466 20323798 : if (index >= register_info_table_.size()) {
467 6285919 : size_t new_size = index + 1;
468 : size_t old_size = register_info_table_.size();
469 6285919 : register_info_table_.resize(new_size);
470 13380146 : for (size_t i = old_size; i < new_size; ++i) {
471 : register_info_table_[i] =
472 : new (zone()) RegisterInfo(RegisterFromRegisterInfoTableIndex(i),
473 14188381 : NextEquivalenceId(), true, false);
474 : }
475 : }
476 6614826 : }
477 :
478 46440880 : void BytecodeRegisterOptimizer::AllocateRegister(RegisterInfo* info) {
479 : info->set_allocated(true);
480 23220440 : if (!info->materialized()) {
481 3129942 : info->MoveToNewEquivalenceSet(NextEquivalenceId(), true);
482 : }
483 23220436 : }
484 :
485 21353451 : void BytecodeRegisterOptimizer::RegisterAllocateEvent(Register reg) {
486 21353451 : AllocateRegister(GetOrCreateRegisterInfo(reg));
487 21353258 : }
488 :
489 667104 : void BytecodeRegisterOptimizer::RegisterListAllocateEvent(
490 : RegisterList reg_list) {
491 667104 : if (reg_list.register_count() != 0) {
492 : int first_index = reg_list.first_register().index();
493 1334226 : GrowRegisterMap(Register(first_index + reg_list.register_count() - 1));
494 2535169 : for (int i = 0; i < reg_list.register_count(); i++) {
495 3736094 : AllocateRegister(GetRegisterInfo(Register(first_index + i)));
496 : }
497 : }
498 667113 : }
499 :
500 79671649 : void BytecodeRegisterOptimizer::RegisterListFreeEvent(RegisterList reg_list) {
501 : int first_index = reg_list.first_register().index();
502 102893814 : for (int i = 0; i < reg_list.register_count(); i++) {
503 23222165 : GetRegisterInfo(Register(first_index + i))->set_allocated(false);
504 : }
505 79671649 : }
506 :
507 : } // namespace interpreter
508 : } // namespace internal
509 178779 : } // namespace v8
|
