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 26596362 : 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 63936518 : void set_materialized(bool materialized) { materialized_ = materialized; }
68 : bool allocated() const { return allocated_; }
69 47527068 : void set_allocated(bool allocated) { allocated_ = allocated; }
70 : void set_equivalence_id(uint32_t equivalence_id) {
71 32354732 : 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 31895605 : 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 : RegisterInfo* info) {
94 : DCHECK_NE(kInvalidEquivalenceId, info->equivalence_id());
95 : // Fix old list
96 32354732 : next_->prev_ = prev_;
97 32354732 : prev_->next_ = next_;
98 : // Add to new list.
99 32354732 : next_ = info->next_;
100 32354732 : prev_ = info;
101 32354732 : prev_->next_ = this;
102 32354732 : 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 47654521 : next_->prev_ = prev_;
110 47654521 : prev_->next_ = next_;
111 47654521 : next_ = prev_ = this;
112 47654521 : equivalence_id_ = equivalence_id;
113 47654521 : 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 : RegisterInfo* info) const {
137 0 : return equivalence_id() == info->equivalence_id();
138 : }
139 :
140 : BytecodeRegisterOptimizer::RegisterInfo*
141 0 : BytecodeRegisterOptimizer::RegisterInfo::GetAllocatedEquivalent() {
142 : RegisterInfo* visitor = this;
143 : do {
144 0 : if (visitor->allocated()) {
145 : return visitor;
146 : }
147 0 : visitor = visitor->next_;
148 0 : } while (visitor != this);
149 :
150 : return nullptr;
151 : }
152 :
153 : BytecodeRegisterOptimizer::RegisterInfo*
154 0 : BytecodeRegisterOptimizer::RegisterInfo::GetMaterializedEquivalent() {
155 : RegisterInfo* visitor = this;
156 : do {
157 17993618 : if (visitor->materialized()) {
158 : return visitor;
159 : }
160 9361230 : visitor = visitor->next_;
161 9361230 : } while (visitor != this);
162 :
163 : return nullptr;
164 : }
165 :
166 : BytecodeRegisterOptimizer::RegisterInfo*
167 0 : BytecodeRegisterOptimizer::RegisterInfo::GetMaterializedEquivalentOtherThan(
168 : Register reg) {
169 : RegisterInfo* visitor = this;
170 : do {
171 9374048 : if (visitor->materialized() && visitor->register_value() != reg) {
172 : return visitor;
173 : }
174 5013493 : visitor = visitor->next_;
175 5013493 : } while (visitor != this);
176 :
177 : return nullptr;
178 : }
179 :
180 : BytecodeRegisterOptimizer::RegisterInfo*
181 70412372 : BytecodeRegisterOptimizer::RegisterInfo::GetEquivalentToMaterialize() {
182 : DCHECK(this->materialized());
183 70412372 : RegisterInfo* visitor = this->next_;
184 : RegisterInfo* best_info = nullptr;
185 112955830 : while (visitor != this) {
186 26095499 : if (visitor->materialized()) {
187 : return nullptr;
188 : }
189 42543458 : if (visitor->allocated() &&
190 163895 : (best_info == nullptr ||
191 : visitor->register_value() < best_info->register_value())) {
192 : best_info = visitor;
193 : }
194 21271729 : 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 5779403 : RegisterInfo* visitor = this->next_;
204 14690610 : while (visitor != this) {
205 8911207 : if (visitor->register_value() >= temporary_base) {
206 : visitor->set_materialized(false);
207 : }
208 8911207 : visitor = visitor->next_;
209 : }
210 0 : }
211 :
212 : BytecodeRegisterOptimizer::RegisterInfo*
213 0 : BytecodeRegisterOptimizer::RegisterInfo::GetEquivalent() {
214 17465822 : return next_;
215 : }
216 :
217 2138304 : 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 2138306 : 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 6414931 : zone_(zone) {
230 2138321 : 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 4276642 : -Register::FromParameterIndex(0, parameter_count).index();
238 :
239 : // Initialize register map for parameters, locals, and the
240 : // accumulator.
241 4276642 : register_info_table_.resize(register_info_table_offset_ +
242 2138321 : static_cast<size_t>(temporary_base_.index()));
243 41008348 : for (size_t i = 0; i < register_info_table_.size(); ++i) {
244 : register_info_table_[i] = new (zone) RegisterInfo(
245 19434995 : RegisterFromRegisterInfoTableIndex(i), NextEquivalenceId(), true, true);
246 : DCHECK_EQ(register_info_table_[i]->register_value().index(),
247 : RegisterFromRegisterInfoTableIndex(i).index());
248 : }
249 2138339 : accumulator_info_ = GetRegisterInfo(accumulator_);
250 : DCHECK(accumulator_info_->register_value() == accumulator_);
251 2138339 : }
252 :
253 0 : void BytecodeRegisterOptimizer::PushToRegistersNeedingFlush(RegisterInfo* reg) {
254 32354788 : if (!reg->needs_flush()) {
255 : reg->set_needs_flush(true);
256 14412686 : 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 6577446 : void BytecodeRegisterOptimizer::Flush() {
274 6577446 : if (!flush_required_) {
275 : return;
276 : }
277 :
278 : // Materialize all live registers and break equivalences.
279 18458453 : for (RegisterInfo* reg_info : registers_needing_flushed_) {
280 14278505 : if (!reg_info->needs_flush()) continue;
281 : reg_info->set_needs_flush(false);
282 :
283 : RegisterInfo* materialized = reg_info->materialized()
284 : ? reg_info
285 13500688 : : reg_info->GetMaterializedEquivalent();
286 :
287 13500688 : 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 17465822 : while ((equivalent = materialized->GetEquivalent()) != materialized) {
293 3982207 : if (equivalent->allocated() && !equivalent->materialized()) {
294 645643 : 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 4179948 : registers_needing_flushed_.clear();
307 : DCHECK(EnsureAllRegistersAreFlushed());
308 :
309 4179945 : flush_required_ = false;
310 : }
311 :
312 25571451 : 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 25571451 : if (input == accumulator_) {
319 20374927 : bytecode_writer_->EmitStar(output);
320 5196524 : } else if (output == accumulator_) {
321 3816891 : bytecode_writer_->EmitLdar(input);
322 : } else {
323 1379633 : bytecode_writer_->EmitMov(input, output);
324 : }
325 25570861 : if (output != accumulator_) {
326 43507904 : max_register_index_ = std::max(max_register_index_, output.index());
327 : }
328 : output_info->set_materialized(true);
329 25570861 : }
330 :
331 70412449 : void BytecodeRegisterOptimizer::CreateMaterializedEquivalent(
332 : RegisterInfo* info) {
333 : DCHECK(info->materialized());
334 70412449 : RegisterInfo* unmaterialized = info->GetEquivalentToMaterialize();
335 70412686 : if (unmaterialized) {
336 17930474 : OutputRegisterTransfer(info, unmaterialized);
337 : }
338 70412274 : }
339 :
340 : BytecodeRegisterOptimizer::RegisterInfo*
341 0 : BytecodeRegisterOptimizer::GetMaterializedEquivalent(RegisterInfo* info) {
342 0 : return info->materialized() ? info : info->GetMaterializedEquivalent();
343 : }
344 :
345 : BytecodeRegisterOptimizer::RegisterInfo*
346 4365091 : BytecodeRegisterOptimizer::GetMaterializedEquivalentNotAccumulator(
347 : RegisterInfo* info) {
348 4365091 : if (info->materialized()) {
349 : return info;
350 : }
351 :
352 : RegisterInfo* result = info->GetMaterializedEquivalentOtherThan(accumulator_);
353 4365096 : if (result == nullptr) {
354 4549 : Materialize(info);
355 : result = info;
356 : }
357 : DCHECK(result->register_value() != accumulator_);
358 : return result;
359 : }
360 :
361 25109885 : void BytecodeRegisterOptimizer::Materialize(RegisterInfo* info) {
362 25109885 : if (!info->materialized()) {
363 : RegisterInfo* materialized = info->GetMaterializedEquivalent();
364 : DCHECK_NOT_NULL(materialized);
365 4460149 : OutputRegisterTransfer(materialized, info);
366 : }
367 25109909 : }
368 :
369 32354788 : 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 32354732 : flush_required_ = true;
377 32354732 : }
378 :
379 34039237 : 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 68078474 : if (in_same_equivalence_set &&
386 1718 : (!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 32354471 : if (output_info->materialized()) {
393 31834520 : CreateMaterializedEquivalent(output_info);
394 : }
395 :
396 : // Add |output_info| to new equivalence set.
397 32355492 : if (!in_same_equivalence_set) {
398 32354818 : AddToEquivalenceSet(input_info, output_info);
399 : }
400 :
401 32355109 : 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 2535295 : OutputRegisterTransfer(materialized_info, output_info);
406 : }
407 :
408 : bool input_is_observable = RegisterIsObservable(input_info->register_value());
409 32355124 : 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 40453984 : void BytecodeRegisterOptimizer::PrepareOutputRegister(Register reg) {
417 : RegisterInfo* reg_info = GetRegisterInfo(reg);
418 40453984 : if (reg_info->materialized()) {
419 38586621 : CreateMaterializedEquivalent(reg_info);
420 : }
421 : reg_info->MoveToNewEquivalenceSet(NextEquivalenceId(), true);
422 : max_register_index_ =
423 80907416 : std::max(max_register_index_, reg_info->register_value().index());
424 40453708 : }
425 :
426 33265 : void BytecodeRegisterOptimizer::PrepareOutputRegisterList(
427 : RegisterList reg_list) {
428 : int start_index = reg_list.first_register().index();
429 322573 : for (int i = 0; i < reg_list.register_count(); ++i) {
430 144654 : Register current(start_index + i);
431 144654 : PrepareOutputRegister(current);
432 : }
433 33265 : }
434 :
435 16764641 : Register BytecodeRegisterOptimizer::GetInputRegister(Register reg) {
436 : RegisterInfo* reg_info = GetRegisterInfo(reg);
437 16764641 : if (reg_info->materialized()) {
438 12399553 : return reg;
439 : } else {
440 : RegisterInfo* equivalent_info =
441 4365088 : GetMaterializedEquivalentNotAccumulator(reg_info);
442 : return equivalent_info->register_value();
443 : }
444 : }
445 :
446 2892865 : RegisterList BytecodeRegisterOptimizer::GetInputRegisterList(
447 : RegisterList reg_list) {
448 2892865 : if (reg_list.register_count() == 1) {
449 : // If there is only a single register, treat it as a normal input register.
450 703655 : Register reg(GetInputRegister(reg_list.first_register()));
451 703660 : return RegisterList(reg);
452 : } else {
453 : int start_index = reg_list.first_register().index();
454 17888232 : for (int i = 0; i < reg_list.register_count(); ++i) {
455 7849498 : Register current(start_index + i);
456 : RegisterInfo* input_info = GetRegisterInfo(current);
457 7849498 : Materialize(input_info);
458 : }
459 2189223 : return reg_list;
460 : }
461 : }
462 :
463 6704105 : void BytecodeRegisterOptimizer::GrowRegisterMap(Register reg) {
464 : DCHECK(RegisterIsTemporary(reg));
465 : size_t index = GetRegisterInfoTableIndex(reg);
466 6704105 : if (index >= register_info_table_.size()) {
467 6347651 : size_t new_size = index + 1;
468 : size_t old_size = register_info_table_.size();
469 6347651 : register_info_table_.resize(new_size);
470 20670432 : for (size_t i = old_size; i < new_size; ++i) {
471 : register_info_table_[i] =
472 : new (zone()) RegisterInfo(RegisterFromRegisterInfoTableIndex(i),
473 7161367 : NextEquivalenceId(), true, false);
474 : }
475 : }
476 6704115 : }
477 :
478 23764462 : void BytecodeRegisterOptimizer::AllocateRegister(RegisterInfo* info) {
479 : info->set_allocated(true);
480 23764462 : if (!info->materialized()) {
481 : info->MoveToNewEquivalenceSet(NextEquivalenceId(), true);
482 : }
483 23764462 : }
484 :
485 21830430 : void BytecodeRegisterOptimizer::RegisterAllocateEvent(Register reg) {
486 21830430 : AllocateRegister(GetOrCreateRegisterInfo(reg));
487 21830389 : }
488 :
489 699033 : void BytecodeRegisterOptimizer::RegisterListAllocateEvent(
490 : RegisterList reg_list) {
491 699033 : if (reg_list.register_count() != 0) {
492 : int first_index = reg_list.first_register().index();
493 1398078 : GrowRegisterMap(Register(first_index + reg_list.register_count() - 1));
494 4567818 : for (int i = 0; i < reg_list.register_count(); i++) {
495 3868810 : AllocateRegister(GetRegisterInfo(Register(first_index + i)));
496 : }
497 : }
498 699023 : }
499 :
500 81385987 : void BytecodeRegisterOptimizer::RegisterListFreeEvent(RegisterList reg_list) {
501 : int first_index = reg_list.first_register().index();
502 128911199 : for (int i = 0; i < reg_list.register_count(); i++) {
503 23762606 : GetRegisterInfo(Register(first_index + i))->set_allocated(false);
504 : }
505 81385987 : }
506 :
507 : } // namespace interpreter
508 : } // namespace internal
509 122036 : } // namespace v8
|
