| 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 | 
|---|