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 2534 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2545 DCHECK(!range->spilled()); | 2545 DCHECK(!range->spilled()); |
2546 TopLevelLiveRange* first = range->TopLevel(); | 2546 TopLevelLiveRange* first = range->TopLevel(); |
2547 TRACE("Spilling live range %d:%d\n", first->vreg(), range->relative_id()); | 2547 TRACE("Spilling live range %d:%d\n", first->vreg(), range->relative_id()); |
2548 | 2548 |
2549 if (first->HasNoSpillType()) { | 2549 if (first->HasNoSpillType()) { |
2550 data()->AssignSpillRangeToLiveRange(first); | 2550 data()->AssignSpillRangeToLiveRange(first); |
2551 } | 2551 } |
2552 range->Spill(); | 2552 range->Spill(); |
2553 } | 2553 } |
2554 | 2554 |
2555 const char* RegisterAllocator::RegisterName(MachineRepresentation rep, | 2555 |
2556 int code) const { | 2556 const ZoneVector<TopLevelLiveRange*>& RegisterAllocator::GetFixedRegisters() |
2557 switch (rep) { | 2557 const { |
2558 case MachineRepresentation::kFloat32: | 2558 return mode() == FP_REGISTERS ? data()->fixed_double_live_ranges() |
2559 return data()->config()->GetFloatRegisterName(code); | 2559 : data()->fixed_live_ranges(); |
2560 case MachineRepresentation::kFloat64: | |
2561 return data()->config()->GetDoubleRegisterName(code); | |
2562 default: | |
2563 break; | |
2564 } | |
2565 return data()->config()->GetGeneralRegisterName(code); | |
2566 } | 2560 } |
2567 | 2561 |
2568 | 2562 |
| 2563 const char* RegisterAllocator::RegisterName(int register_code) const { |
| 2564 if (mode() == GENERAL_REGISTERS) { |
| 2565 return data()->config()->GetGeneralRegisterName(register_code); |
| 2566 } else { |
| 2567 return data()->config()->GetDoubleRegisterName(register_code); |
| 2568 } |
| 2569 } |
| 2570 |
| 2571 |
2569 LinearScanAllocator::LinearScanAllocator(RegisterAllocationData* data, | 2572 LinearScanAllocator::LinearScanAllocator(RegisterAllocationData* data, |
2570 RegisterKind kind, Zone* local_zone) | 2573 RegisterKind kind, Zone* local_zone) |
2571 : RegisterAllocator(data, kind), | 2574 : RegisterAllocator(data, kind), |
2572 unhandled_live_ranges_(local_zone), | 2575 unhandled_live_ranges_(local_zone), |
2573 active_live_ranges_(local_zone), | 2576 active_live_ranges_(local_zone), |
2574 inactive_live_ranges_(local_zone) { | 2577 inactive_live_ranges_(local_zone) { |
2575 unhandled_live_ranges().reserve( | 2578 unhandled_live_ranges().reserve( |
2576 static_cast<size_t>(code()->VirtualRegisterCount() * 2)); | 2579 static_cast<size_t>(code()->VirtualRegisterCount() * 2)); |
2577 active_live_ranges().reserve(8); | 2580 active_live_ranges().reserve(8); |
2578 inactive_live_ranges().reserve(8); | 2581 inactive_live_ranges().reserve(8); |
(...skipping 17 matching lines...) Expand all Loading... |
2596 for (LiveRange* to_add = range; to_add != nullptr; | 2599 for (LiveRange* to_add = range; to_add != nullptr; |
2597 to_add = to_add->next()) { | 2600 to_add = to_add->next()) { |
2598 if (!to_add->spilled()) { | 2601 if (!to_add->spilled()) { |
2599 AddToUnhandledUnsorted(to_add); | 2602 AddToUnhandledUnsorted(to_add); |
2600 } | 2603 } |
2601 } | 2604 } |
2602 } | 2605 } |
2603 SortUnhandled(); | 2606 SortUnhandled(); |
2604 DCHECK(UnhandledIsSorted()); | 2607 DCHECK(UnhandledIsSorted()); |
2605 | 2608 |
2606 if (mode() == GENERAL_REGISTERS) { | 2609 auto& fixed_ranges = GetFixedRegisters(); |
2607 for (TopLevelLiveRange* current : data()->fixed_live_ranges()) { | 2610 for (TopLevelLiveRange* current : fixed_ranges) { |
2608 if (current != nullptr) AddToInactive(current); | 2611 if (current != nullptr) { |
2609 } | 2612 DCHECK_EQ(mode(), current->kind()); |
2610 } else { | 2613 AddToInactive(current); |
2611 DCHECK(mode() == FP_REGISTERS); | |
2612 for (TopLevelLiveRange* current : data()->fixed_double_live_ranges()) { | |
2613 if (current != nullptr) AddToInactive(current); | |
2614 } | 2614 } |
2615 } | 2615 } |
2616 | 2616 |
2617 while (!unhandled_live_ranges().empty()) { | 2617 while (!unhandled_live_ranges().empty()) { |
2618 DCHECK(UnhandledIsSorted()); | 2618 DCHECK(UnhandledIsSorted()); |
2619 LiveRange* current = unhandled_live_ranges().back(); | 2619 LiveRange* current = unhandled_live_ranges().back(); |
2620 unhandled_live_ranges().pop_back(); | 2620 unhandled_live_ranges().pop_back(); |
2621 DCHECK(UnhandledIsSorted()); | 2621 DCHECK(UnhandledIsSorted()); |
2622 LifetimePosition position = current->Start(); | 2622 LifetimePosition position = current->Start(); |
2623 #ifdef DEBUG | 2623 #ifdef DEBUG |
(...skipping 147 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2771 | 2771 |
2772 void LinearScanAllocator::InactiveToActive(LiveRange* range) { | 2772 void LinearScanAllocator::InactiveToActive(LiveRange* range) { |
2773 RemoveElement(&inactive_live_ranges(), range); | 2773 RemoveElement(&inactive_live_ranges(), range); |
2774 active_live_ranges().push_back(range); | 2774 active_live_ranges().push_back(range); |
2775 TRACE("Moving live range %d:%d from inactive to active\n", | 2775 TRACE("Moving live range %d:%d from inactive to active\n", |
2776 range->TopLevel()->vreg(), range->relative_id()); | 2776 range->TopLevel()->vreg(), range->relative_id()); |
2777 } | 2777 } |
2778 | 2778 |
2779 | 2779 |
2780 bool LinearScanAllocator::TryAllocateFreeReg(LiveRange* current) { | 2780 bool LinearScanAllocator::TryAllocateFreeReg(LiveRange* current) { |
2781 MachineRepresentation rep = current->representation(); | |
2782 LifetimePosition free_until_pos[RegisterConfiguration::kMaxFPRegisters]; | 2781 LifetimePosition free_until_pos[RegisterConfiguration::kMaxFPRegisters]; |
2783 | 2782 |
2784 for (int i = 0; i < num_registers(); i++) { | 2783 for (int i = 0; i < num_registers(); i++) { |
2785 free_until_pos[i] = LifetimePosition::MaxPosition(); | 2784 free_until_pos[i] = LifetimePosition::MaxPosition(); |
2786 } | 2785 } |
2787 | 2786 |
2788 for (LiveRange* cur_active : active_live_ranges()) { | 2787 for (LiveRange* cur_active : active_live_ranges()) { |
2789 int cur_reg = cur_active->assigned_register(); | 2788 free_until_pos[cur_active->assigned_register()] = |
2790 free_until_pos[cur_reg] = LifetimePosition::GapFromInstructionIndex(0); | 2789 LifetimePosition::GapFromInstructionIndex(0); |
2791 TRACE("Register %s is free until pos %d (1)\n", | 2790 TRACE("Register %s is free until pos %d (1)\n", |
2792 RegisterName(cur_active->representation(), cur_reg), | 2791 RegisterName(cur_active->assigned_register()), |
2793 LifetimePosition::GapFromInstructionIndex(0).value()); | 2792 LifetimePosition::GapFromInstructionIndex(0).value()); |
2794 } | 2793 } |
2795 | 2794 |
2796 for (LiveRange* cur_inactive : inactive_live_ranges()) { | 2795 for (LiveRange* cur_inactive : inactive_live_ranges()) { |
2797 DCHECK(cur_inactive->End() > current->Start()); | 2796 DCHECK(cur_inactive->End() > current->Start()); |
2798 LifetimePosition next_intersection = | 2797 LifetimePosition next_intersection = |
2799 cur_inactive->FirstIntersection(current); | 2798 cur_inactive->FirstIntersection(current); |
2800 if (!next_intersection.IsValid()) continue; | 2799 if (!next_intersection.IsValid()) continue; |
2801 int cur_reg = cur_inactive->assigned_register(); | 2800 int cur_reg = cur_inactive->assigned_register(); |
2802 free_until_pos[cur_reg] = Min(free_until_pos[cur_reg], next_intersection); | 2801 free_until_pos[cur_reg] = Min(free_until_pos[cur_reg], next_intersection); |
2803 TRACE("Register %s is free until pos %d (2)\n", | 2802 TRACE("Register %s is free until pos %d (2)\n", RegisterName(cur_reg), |
2804 RegisterName(cur_inactive->representation(), cur_reg), | |
2805 Min(free_until_pos[cur_reg], next_intersection).value()); | 2803 Min(free_until_pos[cur_reg], next_intersection).value()); |
2806 } | 2804 } |
2807 | 2805 |
2808 int hint_register; | 2806 int hint_register; |
2809 if (current->FirstHintPosition(&hint_register) != nullptr) { | 2807 if (current->FirstHintPosition(&hint_register) != nullptr) { |
2810 TRACE( | 2808 TRACE( |
2811 "Found reg hint %s (free until [%d) for live range %d:%d (end %d[).\n", | 2809 "Found reg hint %s (free until [%d) for live range %d:%d (end %d[).\n", |
2812 RegisterName(rep, hint_register), free_until_pos[hint_register].value(), | 2810 RegisterName(hint_register), free_until_pos[hint_register].value(), |
2813 current->TopLevel()->vreg(), current->relative_id(), | 2811 current->TopLevel()->vreg(), current->relative_id(), |
2814 current->End().value()); | 2812 current->End().value()); |
2815 | 2813 |
2816 // The desired register is free until the end of the current live range. | 2814 // The desired register is free until the end of the current live range. |
2817 if (free_until_pos[hint_register] >= current->End()) { | 2815 if (free_until_pos[hint_register] >= current->End()) { |
2818 TRACE("Assigning preferred reg %s to live range %d:%d\n", | 2816 TRACE("Assigning preferred reg %s to live range %d:%d\n", |
2819 RegisterName(rep, hint_register), current->TopLevel()->vreg(), | 2817 RegisterName(hint_register), current->TopLevel()->vreg(), |
2820 current->relative_id()); | 2818 current->relative_id()); |
2821 SetLiveRangeAssignedRegister(current, hint_register); | 2819 SetLiveRangeAssignedRegister(current, hint_register); |
2822 return true; | 2820 return true; |
2823 } | 2821 } |
2824 } | 2822 } |
2825 | 2823 |
2826 // Find the register which stays free for the longest time. | 2824 // Find the register which stays free for the longest time. |
2827 int reg = allocatable_register_code(0); | 2825 int reg = allocatable_register_code(0); |
2828 for (int i = 1; i < num_allocatable_registers(); ++i) { | 2826 for (int i = 1; i < num_allocatable_registers(); ++i) { |
2829 int code = allocatable_register_code(i); | 2827 int code = allocatable_register_code(i); |
(...skipping 12 matching lines...) Expand all Loading... |
2842 if (pos < current->End()) { | 2840 if (pos < current->End()) { |
2843 // Register reg is available at the range start but becomes blocked before | 2841 // Register reg is available at the range start but becomes blocked before |
2844 // the range end. Split current at position where it becomes blocked. | 2842 // the range end. Split current at position where it becomes blocked. |
2845 LiveRange* tail = SplitRangeAt(current, pos); | 2843 LiveRange* tail = SplitRangeAt(current, pos); |
2846 AddToUnhandledSorted(tail); | 2844 AddToUnhandledSorted(tail); |
2847 } | 2845 } |
2848 | 2846 |
2849 // Register reg is available at the range start and is free until | 2847 // Register reg is available at the range start and is free until |
2850 // the range end. | 2848 // the range end. |
2851 DCHECK(pos >= current->End()); | 2849 DCHECK(pos >= current->End()); |
2852 TRACE("Assigning free reg %s to live range %d:%d\n", RegisterName(rep, reg), | 2850 TRACE("Assigning free reg %s to live range %d:%d\n", RegisterName(reg), |
2853 current->TopLevel()->vreg(), current->relative_id()); | 2851 current->TopLevel()->vreg(), current->relative_id()); |
2854 SetLiveRangeAssignedRegister(current, reg); | 2852 SetLiveRangeAssignedRegister(current, reg); |
2855 | 2853 |
2856 return true; | 2854 return true; |
2857 } | 2855 } |
2858 | 2856 |
2859 | 2857 |
2860 void LinearScanAllocator::AllocateBlockedReg(LiveRange* current) { | 2858 void LinearScanAllocator::AllocateBlockedReg(LiveRange* current) { |
2861 UsePosition* register_use = current->NextRegisterPosition(current->Start()); | 2859 UsePosition* register_use = current->NextRegisterPosition(current->Start()); |
2862 if (register_use == nullptr) { | 2860 if (register_use == nullptr) { |
(...skipping 64 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2927 if (block_pos[reg] < current->End()) { | 2925 if (block_pos[reg] < current->End()) { |
2928 // Register becomes blocked before the current range end. Split before that | 2926 // Register becomes blocked before the current range end. Split before that |
2929 // position. | 2927 // position. |
2930 LiveRange* tail = | 2928 LiveRange* tail = |
2931 SplitBetween(current, current->Start(), block_pos[reg].Start()); | 2929 SplitBetween(current, current->Start(), block_pos[reg].Start()); |
2932 AddToUnhandledSorted(tail); | 2930 AddToUnhandledSorted(tail); |
2933 } | 2931 } |
2934 | 2932 |
2935 // Register reg is not blocked for the whole range. | 2933 // Register reg is not blocked for the whole range. |
2936 DCHECK(block_pos[reg] >= current->End()); | 2934 DCHECK(block_pos[reg] >= current->End()); |
2937 TRACE("Assigning blocked reg %s to live range %d:%d\n", | 2935 TRACE("Assigning blocked reg %s to live range %d:%d\n", RegisterName(reg), |
2938 RegisterName(current->representation(), reg), | |
2939 current->TopLevel()->vreg(), current->relative_id()); | 2936 current->TopLevel()->vreg(), current->relative_id()); |
2940 SetLiveRangeAssignedRegister(current, reg); | 2937 SetLiveRangeAssignedRegister(current, reg); |
2941 | 2938 |
2942 // This register was not free. Thus we need to find and spill | 2939 // This register was not free. Thus we need to find and spill |
2943 // parts of active and inactive live regions that use the same register | 2940 // parts of active and inactive live regions that use the same register |
2944 // at the same lifetime positions as current. | 2941 // at the same lifetime positions as current. |
2945 SplitAndSpillIntersecting(current); | 2942 SplitAndSpillIntersecting(current); |
2946 } | 2943 } |
2947 | 2944 |
2948 | 2945 |
(...skipping 686 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
3635 } | 3632 } |
3636 } | 3633 } |
3637 } | 3634 } |
3638 } | 3635 } |
3639 } | 3636 } |
3640 | 3637 |
3641 | 3638 |
3642 } // namespace compiler | 3639 } // namespace compiler |
3643 } // namespace internal | 3640 } // namespace internal |
3644 } // namespace v8 | 3641 } // namespace v8 |
OLD | NEW |