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 : next_(this),
25 29585244 : 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 60962501 : void set_materialized(bool materialized) { materialized_ = materialized; }
62 : bool allocated() const { return allocated_; }
63 42112371 : void set_allocated(bool allocated) { allocated_ = allocated; }
64 : void set_equivalence_id(uint32_t equivalence_id) {
65 31904317 : 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 :
82 0 : void BytecodeRegisterOptimizer::RegisterInfo::AddToEquivalenceSetOf(
83 31904317 : RegisterInfo* info) {
84 : DCHECK_NE(kInvalidEquivalenceId, info->equivalence_id());
85 : // Fix old list
86 31904317 : next_->prev_ = prev_;
87 31904317 : prev_->next_ = next_;
88 : // Add to new list.
89 31904317 : next_ = info->next_;
90 31904317 : prev_ = info;
91 31904317 : prev_->next_ = this;
92 31904317 : next_->prev_ = this;
93 : set_equivalence_id(info->equivalence_id());
94 : set_materialized(false);
95 0 : }
96 :
97 0 : void BytecodeRegisterOptimizer::RegisterInfo::MoveToNewEquivalenceSet(
98 : uint32_t equivalence_id, bool materialized) {
99 39554291 : next_->prev_ = prev_;
100 39554291 : prev_->next_ = next_;
101 39554291 : next_ = prev_ = this;
102 39554291 : equivalence_id_ = equivalence_id;
103 39554291 : materialized_ = materialized;
104 0 : }
105 :
106 0 : bool BytecodeRegisterOptimizer::RegisterInfo::IsOnlyMemberOfEquivalenceSet()
107 : const {
108 0 : return this->next_ == this;
109 : }
110 :
111 0 : bool BytecodeRegisterOptimizer::RegisterInfo::
112 : IsOnlyMaterializedMemberOfEquivalenceSet() const {
113 : DCHECK(materialized());
114 :
115 0 : const RegisterInfo* visitor = this->next_;
116 0 : while (visitor != this) {
117 0 : if (visitor->materialized()) {
118 : return false;
119 : }
120 0 : visitor = visitor->next_;
121 : }
122 : return true;
123 : }
124 :
125 0 : bool BytecodeRegisterOptimizer::RegisterInfo::IsInSameEquivalenceSet(
126 34246841 : RegisterInfo* info) const {
127 0 : return equivalence_id() == info->equivalence_id();
128 : }
129 :
130 : BytecodeRegisterOptimizer::RegisterInfo*
131 0 : BytecodeRegisterOptimizer::RegisterInfo::GetMaterializedEquivalent() {
132 11806666 : RegisterInfo* visitor = this;
133 4433055 : do {
134 11806666 : if (visitor->materialized()) {
135 : return visitor;
136 : }
137 4433055 : visitor = visitor->next_;
138 : } while (visitor != this);
139 :
140 : return nullptr;
141 : }
142 :
143 : BytecodeRegisterOptimizer::RegisterInfo*
144 0 : BytecodeRegisterOptimizer::RegisterInfo::GetMaterializedEquivalentOtherThan(
145 : Register reg) {
146 8207717 : RegisterInfo* visitor = this;
147 4160833 : do {
148 8207717 : if (visitor->materialized() && visitor->register_value() != reg) {
149 : return visitor;
150 : }
151 4160833 : visitor = visitor->next_;
152 : } while (visitor != this);
153 :
154 : return nullptr;
155 : }
156 :
157 : BytecodeRegisterOptimizer::RegisterInfo*
158 54338260 : BytecodeRegisterOptimizer::RegisterInfo::GetEquivalentToMaterialize() {
159 : DCHECK(this->materialized());
160 94060026 : RegisterInfo* visitor = this->next_;
161 : RegisterInfo* best_info = nullptr;
162 125638587 : while (visitor != this) {
163 22759699 : if (visitor->materialized()) {
164 : return nullptr;
165 : }
166 33924134 : if (visitor->allocated() &&
167 164605 : (best_info == nullptr ||
168 : visitor->register_value() < best_info->register_value())) {
169 : best_info = visitor;
170 : }
171 16962067 : visitor = visitor->next_;
172 : }
173 : return best_info;
174 : }
175 :
176 0 : void BytecodeRegisterOptimizer::RegisterInfo::MarkTemporariesAsUnmaterialized(
177 : Register temporary_base) {
178 : DCHECK(this->register_value() < temporary_base);
179 : DCHECK(this->materialized());
180 8017778 : RegisterInfo* visitor = this->next_;
181 16876164 : while (visitor != this) {
182 8858386 : if (visitor->register_value() >= temporary_base) {
183 : visitor->set_materialized(false);
184 : }
185 8858386 : visitor = visitor->next_;
186 : }
187 0 : }
188 :
189 : BytecodeRegisterOptimizer::RegisterInfo*
190 0 : BytecodeRegisterOptimizer::RegisterInfo::GetEquivalent() {
191 1603972505 : return next_;
192 : }
193 :
194 2104165 : BytecodeRegisterOptimizer::BytecodeRegisterOptimizer(
195 : Zone* zone, BytecodeRegisterAllocator* register_allocator,
196 : int fixed_registers_count, int parameter_count,
197 22140082 : BytecodeWriter* bytecode_writer)
198 : : accumulator_(Register::virtual_accumulator()),
199 : temporary_base_(fixed_registers_count),
200 2104165 : max_register_index_(fixed_registers_count - 1),
201 : register_info_table_(zone),
202 : equivalence_id_(0),
203 : bytecode_writer_(bytecode_writer),
204 : flush_required_(false),
205 6312495 : zone_(zone) {
206 2104165 : register_allocator->set_observer(this);
207 :
208 : // Calculate offset so register index values can be mapped into
209 : // a vector of register metadata.
210 2104165 : if (parameter_count != 0) {
211 : register_info_table_offset_ =
212 4177929 : -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 15200 : 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 50592659 : static_cast<size_t>(temporary_base_.index()));
223 48488512 : for (size_t i = 0; i < register_info_table_.size(); ++i) {
224 : register_info_table_[i] = new (zone) RegisterInfo(
225 44280157 : RegisterFromRegisterInfoTableIndex(i), NextEquivalenceId(), true, true);
226 : DCHECK_EQ(register_info_table_[i]->register_value().index(),
227 : RegisterFromRegisterInfoTableIndex(i).index());
228 : }
229 2104174 : accumulator_info_ = GetRegisterInfo(accumulator_);
230 : DCHECK(accumulator_info_->register_value() == accumulator_);
231 2104174 : }
232 :
233 9963180 : void BytecodeRegisterOptimizer::Flush() {
234 9963180 : if (!flush_required_) {
235 9963173 : return;
236 : }
237 :
238 : // Materialize all live registers and break equivalences.
239 1604042611 : size_t count = register_info_table_.size();
240 1604042604 : for (size_t i = 0; i < count; ++i) {
241 1598354857 : RegisterInfo* reg_info = register_info_table_[i];
242 1598354857 : 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 8945912 : RegisterInfo* equivalent;
247 1603972505 : while ((equivalent = reg_info->GetEquivalent()) != reg_info) {
248 8945912 : if (equivalent->allocated() && !equivalent->materialized()) {
249 693279 : OutputRegisterTransfer(reg_info, equivalent);
250 : }
251 6042198 : equivalent->MoveToNewEquivalenceSet(NextEquivalenceId(), true);
252 : }
253 : }
254 : }
255 :
256 5687747 : flush_required_ = false;
257 : }
258 :
259 24471645 : void BytecodeRegisterOptimizer::OutputRegisterTransfer(
260 : RegisterInfo* input_info, RegisterInfo* output_info) {
261 : Register input = input_info->register_value();
262 : Register output = output_info->register_value();
263 : DCHECK_NE(input.index(), output.index());
264 :
265 24471645 : if (input == accumulator_) {
266 19578329 : bytecode_writer_->EmitStar(output);
267 4893316 : } else if (output == accumulator_) {
268 2726163 : bytecode_writer_->EmitLdar(input);
269 : } else {
270 2167153 : bytecode_writer_->EmitMov(input, output);
271 : }
272 24471640 : if (output != accumulator_) {
273 43490952 : max_register_index_ = std::max(max_register_index_, output.index());
274 : }
275 : output_info->set_materialized(true);
276 24471640 : }
277 :
278 54338258 : void BytecodeRegisterOptimizer::CreateMaterializedEquivalent(
279 : RegisterInfo* info) {
280 : DCHECK(info->materialized());
281 54338258 : RegisterInfo* unmaterialized = info->GetEquivalentToMaterialize();
282 54338276 : if (unmaterialized) {
283 16404762 : OutputRegisterTransfer(info, unmaterialized);
284 : }
285 54338278 : }
286 :
287 : BytecodeRegisterOptimizer::RegisterInfo*
288 0 : BytecodeRegisterOptimizer::GetMaterializedEquivalent(RegisterInfo* info) {
289 0 : return info->materialized() ? info : info->GetMaterializedEquivalent();
290 : }
291 :
292 : BytecodeRegisterOptimizer::RegisterInfo*
293 4049638 : BytecodeRegisterOptimizer::GetMaterializedEquivalentNotAccumulator(
294 4049638 : RegisterInfo* info) {
295 4049638 : if (info->materialized()) {
296 : return info;
297 : }
298 :
299 : RegisterInfo* result = info->GetMaterializedEquivalentOtherThan(accumulator_);
300 4049638 : if (result == nullptr) {
301 2754 : Materialize(info);
302 : result = info;
303 : }
304 : DCHECK(result->register_value() != accumulator_);
305 4049638 : return result;
306 : }
307 :
308 21343537 : void BytecodeRegisterOptimizer::Materialize(RegisterInfo* info) {
309 21343537 : if (!info->materialized()) {
310 : RegisterInfo* materialized = info->GetMaterializedEquivalent();
311 3820335 : OutputRegisterTransfer(materialized, info);
312 : }
313 21343538 : }
314 :
315 0 : void BytecodeRegisterOptimizer::AddToEquivalenceSet(
316 : RegisterInfo* set_member, RegisterInfo* non_set_member) {
317 : non_set_member->AddToEquivalenceSetOf(set_member);
318 : // Flushing is only required when two or more registers are placed
319 : // in the same equivalence set.
320 31904317 : flush_required_ = true;
321 0 : }
322 :
323 34246744 : void BytecodeRegisterOptimizer::RegisterTransfer(RegisterInfo* input_info,
324 34246744 : RegisterInfo* output_info) {
325 : // Materialize an alternate in the equivalence set that
326 : // |output_info| is leaving.
327 34246744 : if (output_info->materialized()) {
328 24201395 : CreateMaterializedEquivalent(output_info);
329 : }
330 :
331 : // Add |output_info| to new equivalence set.
332 34246841 : if (!output_info->IsInSameEquivalenceSet(input_info)) {
333 : AddToEquivalenceSet(input_info, output_info);
334 : }
335 :
336 : bool output_is_observable =
337 : RegisterIsObservable(output_info->register_value());
338 34246841 : if (output_is_observable) {
339 : // Force store to be emitted when register is observable.
340 : output_info->set_materialized(false);
341 : RegisterInfo* materialized_info = input_info->GetMaterializedEquivalent();
342 3553276 : OutputRegisterTransfer(materialized_info, output_info);
343 : }
344 :
345 : bool input_is_observable = RegisterIsObservable(input_info->register_value());
346 34246842 : if (input_is_observable) {
347 : // If input is observable by the debugger, mark all other temporaries
348 : // registers as unmaterialized so that this register is used in preference.
349 : input_info->MarkTemporariesAsUnmaterialized(temporary_base_);
350 : }
351 34246842 : }
352 :
353 33512119 : void BytecodeRegisterOptimizer::PrepareOutputRegister(Register reg) {
354 33512119 : RegisterInfo* reg_info = GetRegisterInfo(reg);
355 33512119 : if (reg_info->materialized()) {
356 30137101 : CreateMaterializedEquivalent(reg_info);
357 : }
358 33512099 : reg_info->MoveToNewEquivalenceSet(NextEquivalenceId(), true);
359 : max_register_index_ =
360 67024200 : std::max(max_register_index_, reg_info->register_value().index());
361 33512100 : }
362 :
363 8536 : void BytecodeRegisterOptimizer::PrepareOutputRegisterList(
364 : RegisterList reg_list) {
365 : int start_index = reg_list.first_register().index();
366 31381 : for (int i = 0; i < reg_list.register_count(); ++i) {
367 22845 : Register current(start_index + i);
368 22845 : PrepareOutputRegister(current);
369 : }
370 8536 : }
371 :
372 16609728 : Register BytecodeRegisterOptimizer::GetInputRegister(Register reg) {
373 16609728 : RegisterInfo* reg_info = GetRegisterInfo(reg);
374 16609728 : if (reg_info->materialized()) {
375 12560090 : return reg;
376 : } else {
377 : RegisterInfo* equivalent_info =
378 4049638 : GetMaterializedEquivalentNotAccumulator(reg_info);
379 : return equivalent_info->register_value();
380 : }
381 : }
382 :
383 2380621 : RegisterList BytecodeRegisterOptimizer::GetInputRegisterList(
384 : RegisterList reg_list) {
385 2380621 : if (reg_list.register_count() == 1) {
386 : // If there is only a single register, treat it as a normal input register.
387 1093131 : Register reg(GetInputRegister(reg_list.first_register()));
388 1093131 : return RegisterList(reg.index(), 1);
389 : } else {
390 : int start_index = reg_list.first_register().index();
391 7949614 : for (int i = 0; i < reg_list.register_count(); ++i) {
392 6662120 : Register current(start_index + i);
393 : RegisterInfo* input_info = GetRegisterInfo(current);
394 6662120 : Materialize(input_info);
395 : }
396 1287494 : return reg_list;
397 : }
398 : }
399 :
400 21491103 : void BytecodeRegisterOptimizer::GrowRegisterMap(Register reg) {
401 : DCHECK(RegisterIsTemporary(reg));
402 : size_t index = GetRegisterInfoTableIndex(reg);
403 20646689 : if (index >= register_info_table_.size()) {
404 6514657 : size_t new_size = index + 1;
405 : size_t old_size = register_info_table_.size();
406 6514657 : register_info_table_.resize(new_size);
407 13959834 : for (size_t i = old_size; i < new_size; ++i) {
408 : register_info_table_[i] =
409 : new (zone()) RegisterInfo(RegisterFromRegisterInfoTableIndex(i),
410 14890341 : NextEquivalenceId(), false, false);
411 : }
412 : }
413 6600765 : }
414 :
415 19437928 : void BytecodeRegisterOptimizer::RegisterAllocateEvent(Register reg) {
416 19437928 : GetOrCreateRegisterInfo(reg)->set_allocated(true);
417 19437937 : }
418 :
419 413292 : void BytecodeRegisterOptimizer::RegisterListAllocateEvent(
420 : RegisterList reg_list) {
421 413292 : if (reg_list.register_count() != 0) {
422 : int first_index = reg_list.first_register().index();
423 826584 : GrowRegisterMap(Register(first_index + reg_list.register_count() - 1));
424 2033814 : for (int i = 0; i < reg_list.register_count(); i++) {
425 1620522 : GetRegisterInfo(Register(first_index + i))->set_allocated(true);
426 : }
427 : }
428 413292 : }
429 :
430 74661012 : void BytecodeRegisterOptimizer::RegisterListFreeEvent(RegisterList reg_list) {
431 : int first_index = reg_list.first_register().index();
432 95714924 : for (int i = 0; i < reg_list.register_count(); i++) {
433 21053912 : GetRegisterInfo(Register(first_index + i))->set_allocated(false);
434 : }
435 74661012 : }
436 :
437 : } // namespace interpreter
438 : } // namespace internal
439 : } // namespace v8
|
