OLD | NEW |
1 // Copyright 2014 the V8 project authors. All rights reserved. | 1 // Copyright 2014 the V8 project authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #include "src/base/adapters.h" | 5 #include "src/base/adapters.h" |
6 #include "src/compiler/linkage.h" | 6 #include "src/compiler/linkage.h" |
7 #include "src/compiler/register-allocator.h" | 7 #include "src/compiler/register-allocator.h" |
8 #include "src/string-stream.h" | 8 #include "src/string-stream.h" |
9 | 9 |
10 namespace v8 { | 10 namespace v8 { |
(...skipping 198 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
209 SpillAtDefinitionList* next) | 209 SpillAtDefinitionList* next) |
210 : gap_index(gap_index), operand(operand), next(next) {} | 210 : gap_index(gap_index), operand(operand), next(next) {} |
211 const int gap_index; | 211 const int gap_index; |
212 InstructionOperand* const operand; | 212 InstructionOperand* const operand; |
213 SpillAtDefinitionList* const next; | 213 SpillAtDefinitionList* const next; |
214 }; | 214 }; |
215 | 215 |
216 | 216 |
217 LiveRange::LiveRange(int id) | 217 LiveRange::LiveRange(int id) |
218 : id_(id), | 218 : id_(id), |
219 spilled_(false), | 219 spill_start_index_(kMaxInt), |
220 has_slot_use_(false), | 220 bits_(0), |
221 is_phi_(false), | |
222 is_non_loop_phi_(false), | |
223 kind_(UNALLOCATED_REGISTERS), | |
224 assigned_register_(kUnassignedRegister), | |
225 last_interval_(nullptr), | 221 last_interval_(nullptr), |
226 first_interval_(nullptr), | 222 first_interval_(nullptr), |
227 first_pos_(nullptr), | 223 first_pos_(nullptr), |
228 parent_(nullptr), | 224 parent_(nullptr), |
229 next_(nullptr), | 225 next_(nullptr), |
| 226 spill_operand_(nullptr), |
| 227 spills_at_definition_(nullptr), |
230 current_interval_(nullptr), | 228 current_interval_(nullptr), |
231 last_processed_use_(nullptr), | 229 last_processed_use_(nullptr), |
232 current_hint_position_(nullptr), | 230 current_hint_position_(nullptr) { |
233 spill_start_index_(kMaxInt), | 231 bits_ = SpillTypeField::encode(SpillType::kNoSpillType) | |
234 spill_type_(SpillType::kNoSpillType), | 232 AssignedRegisterField::encode(kUnassignedRegister); |
235 spill_operand_(nullptr), | 233 } |
236 spills_at_definition_(nullptr) {} | |
237 | 234 |
238 | 235 |
239 void LiveRange::Verify() const { | 236 void LiveRange::Verify() const { |
240 // Walk the positions, verifying that each is in an interval. | 237 // Walk the positions, verifying that each is in an interval. |
241 auto interval = first_interval_; | 238 auto interval = first_interval_; |
242 for (auto pos = first_pos_; pos != nullptr; pos = pos->next()) { | 239 for (auto pos = first_pos_; pos != nullptr; pos = pos->next()) { |
243 CHECK(Start() <= pos->pos()); | 240 CHECK(Start() <= pos->pos()); |
244 CHECK(pos->pos() <= End()); | 241 CHECK(pos->pos() <= End()); |
245 CHECK(interval != nullptr); | 242 CHECK(interval != nullptr); |
246 while (!interval->Contains(pos->pos()) && interval->end() != pos->pos()) { | 243 while (!interval->Contains(pos->pos()) && interval->end() != pos->pos()) { |
247 interval = interval->next(); | 244 interval = interval->next(); |
248 CHECK(interval != nullptr); | 245 CHECK(interval != nullptr); |
249 } | 246 } |
250 } | 247 } |
251 } | 248 } |
252 | 249 |
253 | 250 |
254 void LiveRange::set_assigned_register(int reg) { | 251 void LiveRange::set_assigned_register(int reg) { |
255 DCHECK(!HasRegisterAssigned() && !IsSpilled()); | 252 DCHECK(!HasRegisterAssigned() && !spilled()); |
256 assigned_register_ = reg; | 253 bits_ = AssignedRegisterField::update(bits_, reg); |
257 } | 254 } |
258 | 255 |
259 | 256 |
260 void LiveRange::UnsetAssignedRegister() { | 257 void LiveRange::UnsetAssignedRegister() { |
261 DCHECK(HasRegisterAssigned() && !IsSpilled()); | 258 DCHECK(HasRegisterAssigned() && !spilled()); |
262 assigned_register_ = kUnassignedRegister; | 259 bits_ = AssignedRegisterField::update(bits_, kUnassignedRegister); |
263 } | 260 } |
264 | 261 |
265 | 262 |
266 void LiveRange::MakeSpilled() { | 263 void LiveRange::Spill() { |
267 DCHECK(!IsSpilled()); | 264 DCHECK(!spilled()); |
268 DCHECK(!TopLevel()->HasNoSpillType()); | 265 DCHECK(!TopLevel()->HasNoSpillType()); |
269 spilled_ = true; | 266 set_spilled(true); |
270 assigned_register_ = kUnassignedRegister; | 267 bits_ = AssignedRegisterField::update(bits_, kUnassignedRegister); |
271 } | 268 } |
272 | 269 |
273 | 270 |
274 void LiveRange::SpillAtDefinition(Zone* zone, int gap_index, | 271 void LiveRange::SpillAtDefinition(Zone* zone, int gap_index, |
275 InstructionOperand* operand) { | 272 InstructionOperand* operand) { |
276 DCHECK(HasNoSpillType()); | 273 DCHECK(HasNoSpillType()); |
277 spills_at_definition_ = new (zone) | 274 spills_at_definition_ = new (zone) |
278 SpillAtDefinitionList(gap_index, operand, spills_at_definition_); | 275 SpillAtDefinitionList(gap_index, operand, spills_at_definition_); |
279 } | 276 } |
280 | 277 |
(...skipping 31 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
312 for (auto pos = first_pos_; pos != nullptr; pos = pos->next()) { | 309 for (auto pos = first_pos_; pos != nullptr; pos = pos->next()) { |
313 if (pos->HintRegister(register_index)) return pos; | 310 if (pos->HintRegister(register_index)) return pos; |
314 } | 311 } |
315 return nullptr; | 312 return nullptr; |
316 } | 313 } |
317 | 314 |
318 | 315 |
319 void LiveRange::SetSpillOperand(InstructionOperand* operand) { | 316 void LiveRange::SetSpillOperand(InstructionOperand* operand) { |
320 DCHECK(HasNoSpillType()); | 317 DCHECK(HasNoSpillType()); |
321 DCHECK(!operand->IsUnallocated() && !operand->IsImmediate()); | 318 DCHECK(!operand->IsUnallocated() && !operand->IsImmediate()); |
322 spill_type_ = SpillType::kSpillOperand; | 319 set_spill_type(SpillType::kSpillOperand); |
323 spill_operand_ = operand; | 320 spill_operand_ = operand; |
324 } | 321 } |
325 | 322 |
326 | 323 |
327 void LiveRange::SetSpillRange(SpillRange* spill_range) { | 324 void LiveRange::SetSpillRange(SpillRange* spill_range) { |
328 DCHECK(HasNoSpillType() || HasSpillRange()); | 325 DCHECK(HasNoSpillType() || HasSpillRange()); |
329 DCHECK(spill_range); | 326 DCHECK(spill_range); |
330 spill_type_ = SpillType::kSpillRange; | 327 set_spill_type(SpillType::kSpillRange); |
331 spill_range_ = spill_range; | 328 spill_range_ = spill_range; |
332 } | 329 } |
333 | 330 |
334 | 331 |
335 void LiveRange::CommitSpillOperand(AllocatedOperand* operand) { | 332 void LiveRange::CommitSpillOperand(AllocatedOperand* operand) { |
336 DCHECK(HasSpillRange()); | 333 DCHECK(HasSpillRange()); |
337 DCHECK(!IsChild()); | 334 DCHECK(!IsChild()); |
338 spill_type_ = SpillType::kSpillOperand; | 335 set_spill_type(SpillType::kSpillOperand); |
339 spill_operand_ = operand; | 336 spill_operand_ = operand; |
340 } | 337 } |
341 | 338 |
342 | 339 |
343 UsePosition* LiveRange::NextUsePosition(LifetimePosition start) const { | 340 UsePosition* LiveRange::NextUsePosition(LifetimePosition start) const { |
344 UsePosition* use_pos = last_processed_use_; | 341 UsePosition* use_pos = last_processed_use_; |
345 if (use_pos == nullptr || use_pos->pos() > start) { | 342 if (use_pos == nullptr || use_pos->pos() > start) { |
346 use_pos = first_pos(); | 343 use_pos = first_pos(); |
347 } | 344 } |
348 while (use_pos != nullptr && use_pos->pos() < start) { | 345 while (use_pos != nullptr && use_pos->pos() < start) { |
(...skipping 39 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
388 // We cannot spill a live range that has a use requiring a register | 385 // We cannot spill a live range that has a use requiring a register |
389 // at the current or the immediate next position. | 386 // at the current or the immediate next position. |
390 auto use_pos = NextRegisterPosition(pos); | 387 auto use_pos = NextRegisterPosition(pos); |
391 if (use_pos == nullptr) return true; | 388 if (use_pos == nullptr) return true; |
392 return use_pos->pos() > pos.NextStart().End(); | 389 return use_pos->pos() > pos.NextStart().End(); |
393 } | 390 } |
394 | 391 |
395 | 392 |
396 InstructionOperand LiveRange::GetAssignedOperand() const { | 393 InstructionOperand LiveRange::GetAssignedOperand() const { |
397 if (HasRegisterAssigned()) { | 394 if (HasRegisterAssigned()) { |
398 DCHECK(!IsSpilled()); | 395 DCHECK(!spilled()); |
399 switch (Kind()) { | 396 switch (kind()) { |
400 case GENERAL_REGISTERS: | 397 case GENERAL_REGISTERS: |
401 return RegisterOperand(assigned_register()); | 398 return RegisterOperand(assigned_register()); |
402 case DOUBLE_REGISTERS: | 399 case DOUBLE_REGISTERS: |
403 return DoubleRegisterOperand(assigned_register()); | 400 return DoubleRegisterOperand(assigned_register()); |
404 default: | 401 default: |
405 UNREACHABLE(); | 402 UNREACHABLE(); |
406 } | 403 } |
407 } | 404 } |
408 DCHECK(IsSpilled()); | 405 DCHECK(spilled()); |
409 DCHECK(!HasRegisterAssigned()); | 406 DCHECK(!HasRegisterAssigned()); |
410 auto op = TopLevel()->GetSpillOperand(); | 407 auto op = TopLevel()->GetSpillOperand(); |
411 DCHECK(!op->IsUnallocated()); | 408 DCHECK(!op->IsUnallocated()); |
412 return *op; | 409 return *op; |
413 } | 410 } |
414 | 411 |
415 | 412 |
416 UseInterval* LiveRange::FirstSearchIntervalForPosition( | 413 UseInterval* LiveRange::FirstSearchIntervalForPosition( |
417 LifetimePosition position) const { | 414 LifetimePosition position) const { |
418 if (current_interval_ == nullptr) return first_interval_; | 415 if (current_interval_ == nullptr) return first_interval_; |
(...skipping 43 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
462 } | 459 } |
463 auto next = current->next(); | 460 auto next = current->next(); |
464 if (next->start() >= position) { | 461 if (next->start() >= position) { |
465 split_at_start = (next->start() == position); | 462 split_at_start = (next->start() == position); |
466 after = next; | 463 after = next; |
467 current->set_next(nullptr); | 464 current->set_next(nullptr); |
468 break; | 465 break; |
469 } | 466 } |
470 current = next; | 467 current = next; |
471 } | 468 } |
| 469 DCHECK(nullptr != after); |
472 | 470 |
473 // Partition original use intervals to the two live ranges. | 471 // Partition original use intervals to the two live ranges. |
474 auto before = current; | 472 auto before = current; |
475 result->last_interval_ = | 473 result->last_interval_ = |
476 (last_interval_ == before) | 474 (last_interval_ == before) |
477 ? after // Only interval in the range after split. | 475 ? after // Only interval in the range after split. |
478 : last_interval_; // Last interval of the original range. | 476 : last_interval_; // Last interval of the original range. |
479 result->first_interval_ = after; | 477 result->first_interval_ = after; |
480 last_interval_ = before; | 478 last_interval_ = before; |
481 | 479 |
(...skipping 25 matching lines...) Expand all Loading... |
507 result->first_pos_ = use_after; | 505 result->first_pos_ = use_after; |
508 | 506 |
509 // Discard cached iteration state. It might be pointing | 507 // Discard cached iteration state. It might be pointing |
510 // to the use that no longer belongs to this live range. | 508 // to the use that no longer belongs to this live range. |
511 last_processed_use_ = nullptr; | 509 last_processed_use_ = nullptr; |
512 current_interval_ = nullptr; | 510 current_interval_ = nullptr; |
513 | 511 |
514 // Link the new live range in the chain before any of the other | 512 // Link the new live range in the chain before any of the other |
515 // ranges linked from the range before the split. | 513 // ranges linked from the range before the split. |
516 result->parent_ = (parent_ == nullptr) ? this : parent_; | 514 result->parent_ = (parent_ == nullptr) ? this : parent_; |
517 result->kind_ = result->parent_->kind_; | 515 result->set_kind(result->parent_->kind()); |
518 result->next_ = next_; | 516 result->next_ = next_; |
519 next_ = result; | 517 next_ = result; |
520 | 518 |
521 #ifdef DEBUG | 519 #ifdef DEBUG |
522 Verify(); | 520 Verify(); |
523 result->Verify(); | 521 result->Verify(); |
524 #endif | 522 #endif |
525 } | 523 } |
526 | 524 |
527 | 525 |
(...skipping 230 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
758 if (this->use_interval_ == nullptr || other->use_interval_ == nullptr || | 756 if (this->use_interval_ == nullptr || other->use_interval_ == nullptr || |
759 this->End() <= other->use_interval_->start() || | 757 this->End() <= other->use_interval_->start() || |
760 other->End() <= this->use_interval_->start()) { | 758 other->End() <= this->use_interval_->start()) { |
761 return false; | 759 return false; |
762 } | 760 } |
763 return AreUseIntervalsIntersecting(use_interval_, other->use_interval_); | 761 return AreUseIntervalsIntersecting(use_interval_, other->use_interval_); |
764 } | 762 } |
765 | 763 |
766 | 764 |
767 bool SpillRange::TryMerge(SpillRange* other) { | 765 bool SpillRange::TryMerge(SpillRange* other) { |
768 if (Kind() != other->Kind() || IsIntersectingWith(other)) return false; | 766 if (kind() != other->kind() || IsIntersectingWith(other)) return false; |
769 | 767 |
770 auto max = LifetimePosition::MaxPosition(); | 768 auto max = LifetimePosition::MaxPosition(); |
771 if (End() < other->End() && other->End() != max) { | 769 if (End() < other->End() && other->End() != max) { |
772 end_position_ = other->End(); | 770 end_position_ = other->End(); |
773 } | 771 } |
774 other->end_position_ = max; | 772 other->end_position_ = max; |
775 | 773 |
776 MergeDisjointIntervals(other->use_interval_); | 774 MergeDisjointIntervals(other->use_interval_); |
777 other->use_interval_ = nullptr; | 775 other->use_interval_ = nullptr; |
778 | 776 |
(...skipping 952 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1731 | 1729 |
1732 // Try hoisting out to an outer loop. | 1730 // Try hoisting out to an outer loop. |
1733 loop_header = GetContainingLoop(code(), loop_header); | 1731 loop_header = GetContainingLoop(code(), loop_header); |
1734 } | 1732 } |
1735 | 1733 |
1736 return pos; | 1734 return pos; |
1737 } | 1735 } |
1738 | 1736 |
1739 | 1737 |
1740 void RegisterAllocator::Spill(LiveRange* range) { | 1738 void RegisterAllocator::Spill(LiveRange* range) { |
1741 DCHECK(!range->IsSpilled()); | 1739 DCHECK(!range->spilled()); |
1742 TRACE("Spilling live range %d\n", range->id()); | 1740 TRACE("Spilling live range %d\n", range->id()); |
1743 auto first = range->TopLevel(); | 1741 auto first = range->TopLevel(); |
1744 if (first->HasNoSpillType()) { | 1742 if (first->HasNoSpillType()) { |
1745 data()->AssignSpillRangeToLiveRange(first); | 1743 data()->AssignSpillRangeToLiveRange(first); |
1746 } | 1744 } |
1747 range->MakeSpilled(); | 1745 range->Spill(); |
1748 } | 1746 } |
1749 | 1747 |
1750 | 1748 |
1751 LinearScanAllocator::LinearScanAllocator(RegisterAllocationData* data, | 1749 LinearScanAllocator::LinearScanAllocator(RegisterAllocationData* data, |
1752 RegisterKind kind, Zone* local_zone) | 1750 RegisterKind kind, Zone* local_zone) |
1753 : RegisterAllocator(data, kind), | 1751 : RegisterAllocator(data, kind), |
1754 unhandled_live_ranges_(local_zone), | 1752 unhandled_live_ranges_(local_zone), |
1755 active_live_ranges_(local_zone), | 1753 active_live_ranges_(local_zone), |
1756 inactive_live_ranges_(local_zone) { | 1754 inactive_live_ranges_(local_zone) { |
1757 unhandled_live_ranges().reserve( | 1755 unhandled_live_ranges().reserve( |
1758 static_cast<size_t>(code()->VirtualRegisterCount() * 2)); | 1756 static_cast<size_t>(code()->VirtualRegisterCount() * 2)); |
1759 active_live_ranges().reserve(8); | 1757 active_live_ranges().reserve(8); |
1760 inactive_live_ranges().reserve(8); | 1758 inactive_live_ranges().reserve(8); |
1761 // TryAllocateFreeReg and AllocateBlockedReg assume this | 1759 // TryAllocateFreeReg and AllocateBlockedReg assume this |
1762 // when allocating local arrays. | 1760 // when allocating local arrays. |
1763 DCHECK(RegisterConfiguration::kMaxDoubleRegisters >= | 1761 DCHECK(RegisterConfiguration::kMaxDoubleRegisters >= |
1764 this->data()->config()->num_general_registers()); | 1762 this->data()->config()->num_general_registers()); |
1765 } | 1763 } |
1766 | 1764 |
1767 | 1765 |
1768 void LinearScanAllocator::AllocateRegisters() { | 1766 void LinearScanAllocator::AllocateRegisters() { |
1769 DCHECK(unhandled_live_ranges().empty()); | 1767 DCHECK(unhandled_live_ranges().empty()); |
1770 DCHECK(active_live_ranges().empty()); | 1768 DCHECK(active_live_ranges().empty()); |
1771 DCHECK(inactive_live_ranges().empty()); | 1769 DCHECK(inactive_live_ranges().empty()); |
1772 | 1770 |
1773 for (auto range : data()->live_ranges()) { | 1771 for (auto range : data()->live_ranges()) { |
1774 if (range == nullptr) continue; | 1772 if (range == nullptr) continue; |
1775 if (range->Kind() == mode()) { | 1773 if (range->kind() == mode()) { |
1776 AddToUnhandledUnsorted(range); | 1774 AddToUnhandledUnsorted(range); |
1777 } | 1775 } |
1778 } | 1776 } |
1779 SortUnhandled(); | 1777 SortUnhandled(); |
1780 DCHECK(UnhandledIsSorted()); | 1778 DCHECK(UnhandledIsSorted()); |
1781 | 1779 |
1782 auto& fixed_ranges = GetFixedRegisters(data(), mode()); | 1780 auto& fixed_ranges = GetFixedRegisters(data(), mode()); |
1783 for (auto current : fixed_ranges) { | 1781 for (auto current : fixed_ranges) { |
1784 if (current != nullptr) { | 1782 if (current != nullptr) { |
1785 DCHECK_EQ(mode(), current->Kind()); | 1783 DCHECK_EQ(mode(), current->kind()); |
1786 AddToInactive(current); | 1784 AddToInactive(current); |
1787 } | 1785 } |
1788 } | 1786 } |
1789 | 1787 |
1790 while (!unhandled_live_ranges().empty()) { | 1788 while (!unhandled_live_ranges().empty()) { |
1791 DCHECK(UnhandledIsSorted()); | 1789 DCHECK(UnhandledIsSorted()); |
1792 auto current = unhandled_live_ranges().back(); | 1790 auto current = unhandled_live_ranges().back(); |
1793 unhandled_live_ranges().pop_back(); | 1791 unhandled_live_ranges().pop_back(); |
1794 DCHECK(UnhandledIsSorted()); | 1792 DCHECK(UnhandledIsSorted()); |
1795 auto position = current->Start(); | 1793 auto position = current->Start(); |
(...skipping 40 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1836 auto cur_inactive = inactive_live_ranges()[i]; | 1834 auto cur_inactive = inactive_live_ranges()[i]; |
1837 if (cur_inactive->End() <= position) { | 1835 if (cur_inactive->End() <= position) { |
1838 InactiveToHandled(cur_inactive); | 1836 InactiveToHandled(cur_inactive); |
1839 --i; // Live range was removed from the list of inactive live ranges. | 1837 --i; // Live range was removed from the list of inactive live ranges. |
1840 } else if (cur_inactive->Covers(position)) { | 1838 } else if (cur_inactive->Covers(position)) { |
1841 InactiveToActive(cur_inactive); | 1839 InactiveToActive(cur_inactive); |
1842 --i; // Live range was removed from the list of inactive live ranges. | 1840 --i; // Live range was removed from the list of inactive live ranges. |
1843 } | 1841 } |
1844 } | 1842 } |
1845 | 1843 |
1846 DCHECK(!current->HasRegisterAssigned() && !current->IsSpilled()); | 1844 DCHECK(!current->HasRegisterAssigned() && !current->spilled()); |
1847 | 1845 |
1848 bool result = TryAllocateFreeReg(current); | 1846 bool result = TryAllocateFreeReg(current); |
1849 if (!result) AllocateBlockedReg(current); | 1847 if (!result) AllocateBlockedReg(current); |
1850 if (current->HasRegisterAssigned()) { | 1848 if (current->HasRegisterAssigned()) { |
1851 AddToActive(current); | 1849 AddToActive(current); |
1852 } | 1850 } |
1853 } | 1851 } |
1854 } | 1852 } |
1855 | 1853 |
1856 | 1854 |
1857 const char* LinearScanAllocator::RegisterName(int allocation_index) const { | 1855 const char* LinearScanAllocator::RegisterName(int allocation_index) const { |
1858 if (mode() == GENERAL_REGISTERS) { | 1856 if (mode() == GENERAL_REGISTERS) { |
1859 return data()->config()->general_register_name(allocation_index); | 1857 return data()->config()->general_register_name(allocation_index); |
1860 } else { | 1858 } else { |
1861 return data()->config()->double_register_name(allocation_index); | 1859 return data()->config()->double_register_name(allocation_index); |
1862 } | 1860 } |
1863 } | 1861 } |
1864 | 1862 |
1865 | 1863 |
1866 void LinearScanAllocator::SetLiveRangeAssignedRegister(LiveRange* range, | 1864 void LinearScanAllocator::SetLiveRangeAssignedRegister(LiveRange* range, |
1867 int reg) { | 1865 int reg) { |
1868 data()->MarkAllocated(range->Kind(), reg); | 1866 data()->MarkAllocated(range->kind(), reg); |
1869 range->set_assigned_register(reg); | 1867 range->set_assigned_register(reg); |
1870 range->SetUseHints(reg); | 1868 range->SetUseHints(reg); |
1871 if (range->is_phi()) { | 1869 if (range->is_phi()) { |
1872 data()->GetPhiMapValueFor(range->id())->set_assigned_register(reg); | 1870 data()->GetPhiMapValueFor(range->id())->set_assigned_register(reg); |
1873 } | 1871 } |
1874 } | 1872 } |
1875 | 1873 |
1876 | 1874 |
1877 void LinearScanAllocator::AddToActive(LiveRange* range) { | 1875 void LinearScanAllocator::AddToActive(LiveRange* range) { |
1878 TRACE("Add live range %d to active\n", range->id()); | 1876 TRACE("Add live range %d to active\n", range->id()); |
1879 active_live_ranges().push_back(range); | 1877 active_live_ranges().push_back(range); |
1880 } | 1878 } |
1881 | 1879 |
1882 | 1880 |
1883 void LinearScanAllocator::AddToInactive(LiveRange* range) { | 1881 void LinearScanAllocator::AddToInactive(LiveRange* range) { |
1884 TRACE("Add live range %d to inactive\n", range->id()); | 1882 TRACE("Add live range %d to inactive\n", range->id()); |
1885 inactive_live_ranges().push_back(range); | 1883 inactive_live_ranges().push_back(range); |
1886 } | 1884 } |
1887 | 1885 |
1888 | 1886 |
1889 void LinearScanAllocator::AddToUnhandledSorted(LiveRange* range) { | 1887 void LinearScanAllocator::AddToUnhandledSorted(LiveRange* range) { |
1890 if (range == nullptr || range->IsEmpty()) return; | 1888 if (range == nullptr || range->IsEmpty()) return; |
1891 DCHECK(!range->HasRegisterAssigned() && !range->IsSpilled()); | 1889 DCHECK(!range->HasRegisterAssigned() && !range->spilled()); |
1892 DCHECK(allocation_finger_ <= range->Start()); | 1890 DCHECK(allocation_finger_ <= range->Start()); |
1893 for (int i = static_cast<int>(unhandled_live_ranges().size() - 1); i >= 0; | 1891 for (int i = static_cast<int>(unhandled_live_ranges().size() - 1); i >= 0; |
1894 --i) { | 1892 --i) { |
1895 auto cur_range = unhandled_live_ranges().at(i); | 1893 auto cur_range = unhandled_live_ranges().at(i); |
1896 if (!range->ShouldBeAllocatedBefore(cur_range)) continue; | 1894 if (!range->ShouldBeAllocatedBefore(cur_range)) continue; |
1897 TRACE("Add live range %d to unhandled at %d\n", range->id(), i + 1); | 1895 TRACE("Add live range %d to unhandled at %d\n", range->id(), i + 1); |
1898 auto it = unhandled_live_ranges().begin() + (i + 1); | 1896 auto it = unhandled_live_ranges().begin() + (i + 1); |
1899 unhandled_live_ranges().insert(it, range); | 1897 unhandled_live_ranges().insert(it, range); |
1900 DCHECK(UnhandledIsSorted()); | 1898 DCHECK(UnhandledIsSorted()); |
1901 return; | 1899 return; |
1902 } | 1900 } |
1903 TRACE("Add live range %d to unhandled at start\n", range->id()); | 1901 TRACE("Add live range %d to unhandled at start\n", range->id()); |
1904 unhandled_live_ranges().insert(unhandled_live_ranges().begin(), range); | 1902 unhandled_live_ranges().insert(unhandled_live_ranges().begin(), range); |
1905 DCHECK(UnhandledIsSorted()); | 1903 DCHECK(UnhandledIsSorted()); |
1906 } | 1904 } |
1907 | 1905 |
1908 | 1906 |
1909 void LinearScanAllocator::AddToUnhandledUnsorted(LiveRange* range) { | 1907 void LinearScanAllocator::AddToUnhandledUnsorted(LiveRange* range) { |
1910 if (range == nullptr || range->IsEmpty()) return; | 1908 if (range == nullptr || range->IsEmpty()) return; |
1911 DCHECK(!range->HasRegisterAssigned() && !range->IsSpilled()); | 1909 DCHECK(!range->HasRegisterAssigned() && !range->spilled()); |
1912 TRACE("Add live range %d to unhandled unsorted at end\n", range->id()); | 1910 TRACE("Add live range %d to unhandled unsorted at end\n", range->id()); |
1913 unhandled_live_ranges().push_back(range); | 1911 unhandled_live_ranges().push_back(range); |
1914 } | 1912 } |
1915 | 1913 |
1916 | 1914 |
1917 static bool UnhandledSortHelper(LiveRange* a, LiveRange* b) { | 1915 static bool UnhandledSortHelper(LiveRange* a, LiveRange* b) { |
1918 DCHECK(!a->ShouldBeAllocatedBefore(b) || !b->ShouldBeAllocatedBefore(a)); | 1916 DCHECK(!a->ShouldBeAllocatedBefore(b) || !b->ShouldBeAllocatedBefore(a)); |
1919 if (a->ShouldBeAllocatedBefore(b)) return false; | 1917 if (a->ShouldBeAllocatedBefore(b)) return false; |
1920 if (b->ShouldBeAllocatedBefore(a)) return true; | 1918 if (b->ShouldBeAllocatedBefore(a)) return true; |
1921 return a->id() < b->id(); | 1919 return a->id() < b->id(); |
(...skipping 257 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2179 for (size_t i = 0; i < phi->operands().size(); i++) { | 2177 for (size_t i = 0; i < phi->operands().size(); i++) { |
2180 int op = phi->operands()[i]; | 2178 int op = phi->operands()[i]; |
2181 LiveRange* op_range = LiveRangeFor(op); | 2179 LiveRange* op_range = LiveRangeFor(op); |
2182 if (!op_range->HasSpillRange()) continue; | 2180 if (!op_range->HasSpillRange()) continue; |
2183 auto pred = code()->InstructionBlockAt(block->predecessors()[i]); | 2181 auto pred = code()->InstructionBlockAt(block->predecessors()[i]); |
2184 auto pred_end = LifetimePosition::InstructionFromInstructionIndex( | 2182 auto pred_end = LifetimePosition::InstructionFromInstructionIndex( |
2185 pred->last_instruction_index()); | 2183 pred->last_instruction_index()); |
2186 while (op_range != nullptr && !op_range->CanCover(pred_end)) { | 2184 while (op_range != nullptr && !op_range->CanCover(pred_end)) { |
2187 op_range = op_range->next(); | 2185 op_range = op_range->next(); |
2188 } | 2186 } |
2189 if (op_range != nullptr && op_range->IsSpilled()) { | 2187 if (op_range != nullptr && op_range->spilled()) { |
2190 spilled_count++; | 2188 spilled_count++; |
2191 if (first_op == nullptr) { | 2189 if (first_op == nullptr) { |
2192 first_op = op_range->TopLevel(); | 2190 first_op = op_range->TopLevel(); |
2193 } | 2191 } |
2194 } | 2192 } |
2195 } | 2193 } |
2196 | 2194 |
2197 // Only continue if more than half of the operands are spilled. | 2195 // Only continue if more than half of the operands are spilled. |
2198 if (spilled_count * 2 <= phi->operands().size()) { | 2196 if (spilled_count * 2 <= phi->operands().size()) { |
2199 return false; | 2197 return false; |
(...skipping 353 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2553 } | 2551 } |
2554 return false; | 2552 return false; |
2555 // TODO(mtrofin): Do we need this? | 2553 // TODO(mtrofin): Do we need this? |
2556 // return (TryReuseSpillForPhi(range)); | 2554 // return (TryReuseSpillForPhi(range)); |
2557 } | 2555 } |
2558 | 2556 |
2559 | 2557 |
2560 void GreedyAllocator::AllocateRegisters() { | 2558 void GreedyAllocator::AllocateRegisters() { |
2561 for (auto range : data()->live_ranges()) { | 2559 for (auto range : data()->live_ranges()) { |
2562 if (range == nullptr) continue; | 2560 if (range == nullptr) continue; |
2563 if (range->Kind() == mode()) { | 2561 if (range->kind() == mode()) { |
2564 DCHECK(!range->HasRegisterAssigned() && !range->IsSpilled()); | 2562 DCHECK(!range->HasRegisterAssigned() && !range->spilled()); |
2565 TRACE("Enqueueing live range %d to priority queue \n", range->id()); | 2563 TRACE("Enqueueing live range %d to priority queue \n", range->id()); |
2566 Enqueue(range); | 2564 Enqueue(range); |
2567 } | 2565 } |
2568 } | 2566 } |
2569 | 2567 |
2570 allocations_.resize(num_registers()); | 2568 allocations_.resize(num_registers()); |
2571 auto* zone = data()->allocation_zone(); | 2569 auto* zone = data()->allocation_zone(); |
2572 for (int i = 0; i < num_registers(); i++) { | 2570 for (int i = 0; i < num_registers(); i++) { |
2573 allocations_[i] = new (zone) CoallescedLiveRanges(zone); | 2571 allocations_[i] = new (zone) CoallescedLiveRanges(zone); |
2574 } | 2572 } |
2575 | 2573 |
2576 for (auto* current : GetFixedRegisters(data(), mode())) { | 2574 for (auto* current : GetFixedRegisters(data(), mode())) { |
2577 if (current != nullptr) { | 2575 if (current != nullptr) { |
2578 DCHECK_EQ(mode(), current->Kind()); | 2576 DCHECK_EQ(mode(), current->kind()); |
2579 int reg_nr = current->assigned_register(); | 2577 int reg_nr = current->assigned_register(); |
2580 bool inserted = allocations_[reg_nr]->Insert(current); | 2578 bool inserted = allocations_[reg_nr]->Insert(current); |
2581 CHECK(inserted); | 2579 CHECK(inserted); |
2582 } | 2580 } |
2583 } | 2581 } |
2584 | 2582 |
2585 while (!queue_.empty()) { | 2583 while (!queue_.empty()) { |
2586 auto current_pair = queue_.top(); | 2584 auto current_pair = queue_.top(); |
2587 queue_.pop(); | 2585 queue_.pop(); |
2588 auto current = current_pair.second; | 2586 auto current = current_pair.second; |
(...skipping 58 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2647 auto other = spill_ranges[j]; | 2645 auto other = spill_ranges[j]; |
2648 if (!other->IsEmpty()) { | 2646 if (!other->IsEmpty()) { |
2649 range->TryMerge(other); | 2647 range->TryMerge(other); |
2650 } | 2648 } |
2651 } | 2649 } |
2652 } | 2650 } |
2653 // Allocate slots for the merged spill ranges. | 2651 // Allocate slots for the merged spill ranges. |
2654 for (auto range : spill_ranges) { | 2652 for (auto range : spill_ranges) { |
2655 if (range->IsEmpty()) continue; | 2653 if (range->IsEmpty()) continue; |
2656 // Allocate a new operand referring to the spill slot. | 2654 // Allocate a new operand referring to the spill slot. |
2657 auto kind = range->Kind(); | 2655 auto kind = range->kind(); |
2658 int index = data()->frame()->AllocateSpillSlot(kind == DOUBLE_REGISTERS); | 2656 int index = data()->frame()->AllocateSpillSlot(kind == DOUBLE_REGISTERS); |
2659 auto op_kind = kind == DOUBLE_REGISTERS | 2657 auto op_kind = kind == DOUBLE_REGISTERS |
2660 ? AllocatedOperand::DOUBLE_STACK_SLOT | 2658 ? AllocatedOperand::DOUBLE_STACK_SLOT |
2661 : AllocatedOperand::STACK_SLOT; | 2659 : AllocatedOperand::STACK_SLOT; |
2662 auto op = AllocatedOperand::New(data()->code_zone(), op_kind, index); | 2660 auto op = AllocatedOperand::New(data()->code_zone(), op_kind, index); |
2663 range->SetOperand(op); | 2661 range->SetOperand(op); |
2664 } | 2662 } |
2665 } | 2663 } |
2666 | 2664 |
2667 | 2665 |
(...skipping 91 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2759 // Check if the live range is spilled and the safe point is after | 2757 // Check if the live range is spilled and the safe point is after |
2760 // the spill position. | 2758 // the spill position. |
2761 if (range->HasSpillOperand() && | 2759 if (range->HasSpillOperand() && |
2762 safe_point >= range->spill_start_index() && | 2760 safe_point >= range->spill_start_index() && |
2763 !range->GetSpillOperand()->IsConstant()) { | 2761 !range->GetSpillOperand()->IsConstant()) { |
2764 TRACE("Pointer for range %d (spilled at %d) at safe point %d\n", | 2762 TRACE("Pointer for range %d (spilled at %d) at safe point %d\n", |
2765 range->id(), range->spill_start_index(), safe_point); | 2763 range->id(), range->spill_start_index(), safe_point); |
2766 map->RecordReference(*range->GetSpillOperand()); | 2764 map->RecordReference(*range->GetSpillOperand()); |
2767 } | 2765 } |
2768 | 2766 |
2769 if (!cur->IsSpilled()) { | 2767 if (!cur->spilled()) { |
2770 TRACE( | 2768 TRACE( |
2771 "Pointer in register for range %d (start at %d) " | 2769 "Pointer in register for range %d (start at %d) " |
2772 "at safe point %d\n", | 2770 "at safe point %d\n", |
2773 cur->id(), cur->Start().value(), safe_point); | 2771 cur->id(), cur->Start().value(), safe_point); |
2774 auto operand = cur->GetAssignedOperand(); | 2772 auto operand = cur->GetAssignedOperand(); |
2775 DCHECK(!operand.IsStackSlot()); | 2773 DCHECK(!operand.IsStackSlot()); |
2776 map->RecordReference(operand); | 2774 map->RecordReference(operand); |
2777 } | 2775 } |
2778 } | 2776 } |
2779 } | 2777 } |
(...skipping 153 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2933 if (CanEagerlyResolveControlFlow(block)) continue; | 2931 if (CanEagerlyResolveControlFlow(block)) continue; |
2934 auto live = live_in_sets[block->rpo_number().ToInt()]; | 2932 auto live = live_in_sets[block->rpo_number().ToInt()]; |
2935 BitVector::Iterator iterator(live); | 2933 BitVector::Iterator iterator(live); |
2936 while (!iterator.Done()) { | 2934 while (!iterator.Done()) { |
2937 auto* array = finder.ArrayFor(iterator.Current()); | 2935 auto* array = finder.ArrayFor(iterator.Current()); |
2938 for (auto pred : block->predecessors()) { | 2936 for (auto pred : block->predecessors()) { |
2939 FindResult result; | 2937 FindResult result; |
2940 const auto* pred_block = code()->InstructionBlockAt(pred); | 2938 const auto* pred_block = code()->InstructionBlockAt(pred); |
2941 array->Find(block, pred_block, &result); | 2939 array->Find(block, pred_block, &result); |
2942 if (result.cur_cover_ == result.pred_cover_ || | 2940 if (result.cur_cover_ == result.pred_cover_ || |
2943 result.cur_cover_->IsSpilled()) | 2941 result.cur_cover_->spilled()) |
2944 continue; | 2942 continue; |
2945 auto pred_op = result.pred_cover_->GetAssignedOperand(); | 2943 auto pred_op = result.pred_cover_->GetAssignedOperand(); |
2946 auto cur_op = result.cur_cover_->GetAssignedOperand(); | 2944 auto cur_op = result.cur_cover_->GetAssignedOperand(); |
2947 if (pred_op == cur_op) continue; | 2945 if (pred_op == cur_op) continue; |
2948 ResolveControlFlow(block, cur_op, pred_block, pred_op); | 2946 ResolveControlFlow(block, cur_op, pred_block, pred_op); |
2949 } | 2947 } |
2950 iterator.Advance(); | 2948 iterator.Advance(); |
2951 } | 2949 } |
2952 } | 2950 } |
2953 } | 2951 } |
(...skipping 24 matching lines...) Expand all Loading... |
2978 void LiveRangeConnector::ConnectRanges(Zone* local_zone) { | 2976 void LiveRangeConnector::ConnectRanges(Zone* local_zone) { |
2979 ZoneMap<std::pair<ParallelMove*, InstructionOperand>, InstructionOperand> | 2977 ZoneMap<std::pair<ParallelMove*, InstructionOperand>, InstructionOperand> |
2980 delayed_insertion_map(local_zone); | 2978 delayed_insertion_map(local_zone); |
2981 for (auto first_range : data()->live_ranges()) { | 2979 for (auto first_range : data()->live_ranges()) { |
2982 if (first_range == nullptr || first_range->IsChild()) continue; | 2980 if (first_range == nullptr || first_range->IsChild()) continue; |
2983 for (auto second_range = first_range->next(); second_range != nullptr; | 2981 for (auto second_range = first_range->next(); second_range != nullptr; |
2984 first_range = second_range, second_range = second_range->next()) { | 2982 first_range = second_range, second_range = second_range->next()) { |
2985 auto pos = second_range->Start(); | 2983 auto pos = second_range->Start(); |
2986 // Add gap move if the two live ranges touch and there is no block | 2984 // Add gap move if the two live ranges touch and there is no block |
2987 // boundary. | 2985 // boundary. |
2988 if (second_range->IsSpilled()) continue; | 2986 if (second_range->spilled()) continue; |
2989 if (first_range->End() != pos) continue; | 2987 if (first_range->End() != pos) continue; |
2990 if (IsBlockBoundary(code(), pos) && | 2988 if (IsBlockBoundary(code(), pos) && |
2991 !CanEagerlyResolveControlFlow(GetInstructionBlock(code(), pos))) { | 2989 !CanEagerlyResolveControlFlow(GetInstructionBlock(code(), pos))) { |
2992 continue; | 2990 continue; |
2993 } | 2991 } |
2994 auto prev_operand = first_range->GetAssignedOperand(); | 2992 auto prev_operand = first_range->GetAssignedOperand(); |
2995 auto cur_operand = second_range->GetAssignedOperand(); | 2993 auto cur_operand = second_range->GetAssignedOperand(); |
2996 if (prev_operand == cur_operand) continue; | 2994 if (prev_operand == cur_operand) continue; |
2997 bool delay_insertion = false; | 2995 bool delay_insertion = false; |
2998 Instruction::GapPosition gap_pos; | 2996 Instruction::GapPosition gap_pos; |
(...skipping 46 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
3045 auto eliminate = moves->PrepareInsertAfter(move); | 3043 auto eliminate = moves->PrepareInsertAfter(move); |
3046 to_insert.push_back(move); | 3044 to_insert.push_back(move); |
3047 if (eliminate != nullptr) to_eliminate.push_back(eliminate); | 3045 if (eliminate != nullptr) to_eliminate.push_back(eliminate); |
3048 } | 3046 } |
3049 } | 3047 } |
3050 | 3048 |
3051 | 3049 |
3052 } // namespace compiler | 3050 } // namespace compiler |
3053 } // namespace internal | 3051 } // namespace internal |
3054 } // namespace v8 | 3052 } // namespace v8 |
OLD | NEW |