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 #ifndef V8_REGISTER_ALLOCATOR_H_ | 5 #ifndef V8_REGISTER_ALLOCATOR_H_ |
6 #define V8_REGISTER_ALLOCATOR_H_ | 6 #define V8_REGISTER_ALLOCATOR_H_ |
7 | 7 |
8 #include "src/compiler/instruction.h" | 8 #include "src/compiler/instruction.h" |
9 #include "src/ostreams.h" | 9 #include "src/ostreams.h" |
10 #include "src/register-configuration.h" | 10 #include "src/register-configuration.h" |
(...skipping 660 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
671 std::ostream& operator<<(std::ostream& os, | 671 std::ostream& operator<<(std::ostream& os, |
672 const PrintableLiveRange& printable_range); | 672 const PrintableLiveRange& printable_range); |
673 | 673 |
674 | 674 |
675 class SpillRange final : public ZoneObject { | 675 class SpillRange final : public ZoneObject { |
676 public: | 676 public: |
677 static const int kUnassignedSlot = -1; | 677 static const int kUnassignedSlot = -1; |
678 SpillRange(TopLevelLiveRange* range, Zone* zone); | 678 SpillRange(TopLevelLiveRange* range, Zone* zone); |
679 | 679 |
680 UseInterval* interval() const { return use_interval_; } | 680 UseInterval* interval() const { return use_interval_; } |
681 // Currently, only 4 or 8 byte slots are supported. | 681 |
682 int ByteWidth() const; | |
683 bool IsEmpty() const { return live_ranges_.empty(); } | 682 bool IsEmpty() const { return live_ranges_.empty(); } |
684 bool TryMerge(SpillRange* other); | 683 bool TryMerge(SpillRange* other); |
685 bool HasSlot() const { return assigned_slot_ != kUnassignedSlot; } | 684 bool HasSlot() const { return assigned_slot_ != kUnassignedSlot; } |
686 | 685 |
687 void set_assigned_slot(int index) { | 686 void set_assigned_slot(int index) { |
688 DCHECK_EQ(kUnassignedSlot, assigned_slot_); | 687 DCHECK_EQ(kUnassignedSlot, assigned_slot_); |
689 assigned_slot_ = index; | 688 assigned_slot_ = index; |
690 } | 689 } |
691 int assigned_slot() { | 690 int assigned_slot() { |
692 DCHECK_NE(kUnassignedSlot, assigned_slot_); | 691 DCHECK_NE(kUnassignedSlot, assigned_slot_); |
(...skipping 68 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
761 const ZoneVector<TopLevelLiveRange*>& live_ranges() const { | 760 const ZoneVector<TopLevelLiveRange*>& live_ranges() const { |
762 return live_ranges_; | 761 return live_ranges_; |
763 } | 762 } |
764 ZoneVector<TopLevelLiveRange*>& live_ranges() { return live_ranges_; } | 763 ZoneVector<TopLevelLiveRange*>& live_ranges() { return live_ranges_; } |
765 const ZoneVector<TopLevelLiveRange*>& fixed_live_ranges() const { | 764 const ZoneVector<TopLevelLiveRange*>& fixed_live_ranges() const { |
766 return fixed_live_ranges_; | 765 return fixed_live_ranges_; |
767 } | 766 } |
768 ZoneVector<TopLevelLiveRange*>& fixed_live_ranges() { | 767 ZoneVector<TopLevelLiveRange*>& fixed_live_ranges() { |
769 return fixed_live_ranges_; | 768 return fixed_live_ranges_; |
770 } | 769 } |
| 770 ZoneVector<TopLevelLiveRange*>& fixed_float_live_ranges() { |
| 771 return fixed_float_live_ranges_; |
| 772 } |
| 773 const ZoneVector<TopLevelLiveRange*>& fixed_float_live_ranges() const { |
| 774 return fixed_float_live_ranges_; |
| 775 } |
771 ZoneVector<TopLevelLiveRange*>& fixed_double_live_ranges() { | 776 ZoneVector<TopLevelLiveRange*>& fixed_double_live_ranges() { |
772 return fixed_double_live_ranges_; | 777 return fixed_double_live_ranges_; |
773 } | 778 } |
774 const ZoneVector<TopLevelLiveRange*>& fixed_double_live_ranges() const { | 779 const ZoneVector<TopLevelLiveRange*>& fixed_double_live_ranges() const { |
775 return fixed_double_live_ranges_; | 780 return fixed_double_live_ranges_; |
776 } | 781 } |
777 ZoneVector<BitVector*>& live_in_sets() { return live_in_sets_; } | 782 ZoneVector<BitVector*>& live_in_sets() { return live_in_sets_; } |
778 ZoneVector<BitVector*>& live_out_sets() { return live_out_sets_; } | 783 ZoneVector<BitVector*>& live_out_sets() { return live_out_sets_; } |
779 ZoneVector<SpillRange*>& spill_ranges() { return spill_ranges_; } | 784 ZoneVector<SpillRange*>& spill_ranges() { return spill_ranges_; } |
780 DelayedReferences& delayed_references() { return delayed_references_; } | 785 DelayedReferences& delayed_references() { return delayed_references_; } |
781 InstructionSequence* code() const { return code_; } | 786 InstructionSequence* code() const { return code_; } |
782 // This zone is for datastructures only needed during register allocation | 787 // This zone is for data structures only needed during register allocation |
783 // phases. | 788 // phases. |
784 Zone* allocation_zone() const { return allocation_zone_; } | 789 Zone* allocation_zone() const { return allocation_zone_; } |
785 // This zone is for InstructionOperands and moves that live beyond register | 790 // This zone is for InstructionOperands and moves that live beyond register |
786 // allocation. | 791 // allocation. |
787 Zone* code_zone() const { return code()->zone(); } | 792 Zone* code_zone() const { return code()->zone(); } |
788 Frame* frame() const { return frame_; } | 793 Frame* frame() const { return frame_; } |
789 const char* debug_name() const { return debug_name_; } | 794 const char* debug_name() const { return debug_name_; } |
790 const RegisterConfiguration* config() const { return config_; } | 795 const RegisterConfiguration* config() const { return config_; } |
791 | 796 |
792 MachineRepresentation RepresentationFor(int virtual_register); | 797 MachineRepresentation RepresentationFor(int virtual_register); |
(...skipping 10 matching lines...) Expand all Loading... |
803 const InstructionOperand& from, | 808 const InstructionOperand& from, |
804 const InstructionOperand& to); | 809 const InstructionOperand& to); |
805 | 810 |
806 bool IsReference(TopLevelLiveRange* top_range) const { | 811 bool IsReference(TopLevelLiveRange* top_range) const { |
807 return code()->IsReference(top_range->vreg()); | 812 return code()->IsReference(top_range->vreg()); |
808 } | 813 } |
809 | 814 |
810 bool ExistsUseWithoutDefinition(); | 815 bool ExistsUseWithoutDefinition(); |
811 bool RangesDefinedInDeferredStayInDeferred(); | 816 bool RangesDefinedInDeferredStayInDeferred(); |
812 | 817 |
813 void MarkAllocated(RegisterKind kind, int index); | 818 void MarkAllocated(MachineRepresentation rep, int index); |
814 | 819 |
815 PhiMapValue* InitializePhiMap(const InstructionBlock* block, | 820 PhiMapValue* InitializePhiMap(const InstructionBlock* block, |
816 PhiInstruction* phi); | 821 PhiInstruction* phi); |
817 PhiMapValue* GetPhiMapValueFor(TopLevelLiveRange* top_range); | 822 PhiMapValue* GetPhiMapValueFor(TopLevelLiveRange* top_range); |
818 PhiMapValue* GetPhiMapValueFor(int virtual_register); | 823 PhiMapValue* GetPhiMapValueFor(int virtual_register); |
819 bool IsBlockBoundary(LifetimePosition pos) const; | 824 bool IsBlockBoundary(LifetimePosition pos) const; |
820 | 825 |
821 RangesWithPreassignedSlots& preassigned_slot_ranges() { | 826 RangesWithPreassignedSlots& preassigned_slot_ranges() { |
822 return preassigned_slot_ranges_; | 827 return preassigned_slot_ranges_; |
823 } | 828 } |
824 | 829 |
825 private: | 830 private: |
826 int GetNextLiveRangeId(); | 831 int GetNextLiveRangeId(); |
827 | 832 |
828 Zone* const allocation_zone_; | 833 Zone* const allocation_zone_; |
829 Frame* const frame_; | 834 Frame* const frame_; |
830 InstructionSequence* const code_; | 835 InstructionSequence* const code_; |
831 const char* const debug_name_; | 836 const char* const debug_name_; |
832 const RegisterConfiguration* const config_; | 837 const RegisterConfiguration* const config_; |
833 PhiMap phi_map_; | 838 PhiMap phi_map_; |
834 ZoneVector<BitVector*> live_in_sets_; | 839 ZoneVector<BitVector*> live_in_sets_; |
835 ZoneVector<BitVector*> live_out_sets_; | 840 ZoneVector<BitVector*> live_out_sets_; |
836 ZoneVector<TopLevelLiveRange*> live_ranges_; | 841 ZoneVector<TopLevelLiveRange*> live_ranges_; |
837 ZoneVector<TopLevelLiveRange*> fixed_live_ranges_; | 842 ZoneVector<TopLevelLiveRange*> fixed_live_ranges_; |
| 843 ZoneVector<TopLevelLiveRange*> fixed_float_live_ranges_; |
838 ZoneVector<TopLevelLiveRange*> fixed_double_live_ranges_; | 844 ZoneVector<TopLevelLiveRange*> fixed_double_live_ranges_; |
839 ZoneVector<SpillRange*> spill_ranges_; | 845 ZoneVector<SpillRange*> spill_ranges_; |
840 DelayedReferences delayed_references_; | 846 DelayedReferences delayed_references_; |
841 BitVector* assigned_registers_; | 847 BitVector* assigned_registers_; |
842 BitVector* assigned_double_registers_; | 848 BitVector* assigned_double_registers_; |
843 int virtual_register_count_; | 849 int virtual_register_count_; |
844 RangesWithPreassignedSlots preassigned_slot_ranges_; | 850 RangesWithPreassignedSlots preassigned_slot_ranges_; |
845 | 851 |
846 DISALLOW_COPY_AND_ASSIGN(RegisterAllocationData); | 852 DISALLOW_COPY_AND_ASSIGN(RegisterAllocationData); |
847 }; | 853 }; |
(...skipping 56 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
904 const TopLevelLiveRange* range) const; | 910 const TopLevelLiveRange* range) const; |
905 bool NextIntervalStartsInDifferentBlocks(const UseInterval* interval) const; | 911 bool NextIntervalStartsInDifferentBlocks(const UseInterval* interval) const; |
906 | 912 |
907 // Liveness analysis support. | 913 // Liveness analysis support. |
908 void AddInitialIntervals(const InstructionBlock* block, BitVector* live_out); | 914 void AddInitialIntervals(const InstructionBlock* block, BitVector* live_out); |
909 void ProcessInstructions(const InstructionBlock* block, BitVector* live); | 915 void ProcessInstructions(const InstructionBlock* block, BitVector* live); |
910 void ProcessPhis(const InstructionBlock* block, BitVector* live); | 916 void ProcessPhis(const InstructionBlock* block, BitVector* live); |
911 void ProcessLoopHeader(const InstructionBlock* block, BitVector* live); | 917 void ProcessLoopHeader(const InstructionBlock* block, BitVector* live); |
912 | 918 |
913 static int FixedLiveRangeID(int index) { return -index - 1; } | 919 static int FixedLiveRangeID(int index) { return -index - 1; } |
914 int FixedDoubleLiveRangeID(int index); | 920 int FixedFPLiveRangeID(int index, MachineRepresentation rep); |
915 TopLevelLiveRange* FixedLiveRangeFor(int index); | 921 TopLevelLiveRange* FixedLiveRangeFor(int index); |
916 TopLevelLiveRange* FixedDoubleLiveRangeFor(int index); | 922 TopLevelLiveRange* FixedFPLiveRangeFor(int index, MachineRepresentation rep); |
917 | 923 |
918 void MapPhiHint(InstructionOperand* operand, UsePosition* use_pos); | 924 void MapPhiHint(InstructionOperand* operand, UsePosition* use_pos); |
919 void ResolvePhiHint(InstructionOperand* operand, UsePosition* use_pos); | 925 void ResolvePhiHint(InstructionOperand* operand, UsePosition* use_pos); |
920 | 926 |
921 UsePosition* NewUsePosition(LifetimePosition pos, InstructionOperand* operand, | 927 UsePosition* NewUsePosition(LifetimePosition pos, InstructionOperand* operand, |
922 void* hint, UsePositionHintType hint_type); | 928 void* hint, UsePositionHintType hint_type); |
923 UsePosition* NewUsePosition(LifetimePosition pos) { | 929 UsePosition* NewUsePosition(LifetimePosition pos) { |
924 return NewUsePosition(pos, nullptr, nullptr, UsePositionHintType::kNone); | 930 return NewUsePosition(pos, nullptr, nullptr, UsePositionHintType::kNone); |
925 } | 931 } |
926 TopLevelLiveRange* LiveRangeFor(InstructionOperand* operand); | 932 TopLevelLiveRange* LiveRangeFor(InstructionOperand* operand); |
(...skipping 13 matching lines...) Expand all Loading... |
940 | 946 |
941 RegisterAllocationData* const data_; | 947 RegisterAllocationData* const data_; |
942 ZoneMap<InstructionOperand*, UsePosition*> phi_hints_; | 948 ZoneMap<InstructionOperand*, UsePosition*> phi_hints_; |
943 | 949 |
944 DISALLOW_COPY_AND_ASSIGN(LiveRangeBuilder); | 950 DISALLOW_COPY_AND_ASSIGN(LiveRangeBuilder); |
945 }; | 951 }; |
946 | 952 |
947 | 953 |
948 class RegisterAllocator : public ZoneObject { | 954 class RegisterAllocator : public ZoneObject { |
949 public: | 955 public: |
950 explicit RegisterAllocator(RegisterAllocationData* data, RegisterKind kind); | 956 RegisterAllocator(RegisterAllocationData* data, RegisterKind kind); |
951 | 957 |
952 protected: | 958 protected: |
953 RegisterAllocationData* data() const { return data_; } | 959 RegisterAllocationData* data() const { return data_; } |
954 InstructionSequence* code() const { return data()->code(); } | 960 InstructionSequence* code() const { return data()->code(); } |
955 RegisterKind mode() const { return mode_; } | 961 RegisterKind mode() const { return mode_; } |
956 int num_registers() const { return num_registers_; } | 962 int num_registers() const { return num_registers_; } |
957 int num_allocatable_registers() const { return num_allocatable_registers_; } | 963 int num_allocatable_registers() const { return num_allocatable_registers_; } |
958 int allocatable_register_code(int allocatable_index) const { | 964 const int* allocatable_register_codes() const { |
959 return allocatable_register_codes_[allocatable_index]; | 965 return allocatable_register_codes_; |
960 } | 966 } |
| 967 // Returns true if registers do not combine to form larger registers, i.e. |
| 968 // no complex aliasing detection is required. This is always true for the |
| 969 // general register pass, and true for the FP register pass except for arm |
| 970 // and mips archs. |
| 971 bool no_combining() const { return no_combining_; } |
961 | 972 |
962 // TODO(mtrofin): explain why splitting in gap START is always OK. | 973 // TODO(mtrofin): explain why splitting in gap START is always OK. |
963 LifetimePosition GetSplitPositionForInstruction(const LiveRange* range, | 974 LifetimePosition GetSplitPositionForInstruction(const LiveRange* range, |
964 int instruction_index); | 975 int instruction_index); |
965 | 976 |
966 Zone* allocation_zone() const { return data()->allocation_zone(); } | 977 Zone* allocation_zone() const { return data()->allocation_zone(); } |
967 | 978 |
968 // Find the optimal split for ranges defined by a memory operand, e.g. | 979 // Find the optimal split for ranges defined by a memory operand, e.g. |
969 // constants or function parameters passed on the stack. | 980 // constants or function parameters passed on the stack. |
970 void SplitAndSpillRangesDefinedByMemoryOperand(bool operands_only); | 981 void SplitAndSpillRangesDefinedByMemoryOperand(bool operands_only); |
(...skipping 31 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1002 const ZoneVector<TopLevelLiveRange*>& GetFixedRegisters() const; | 1013 const ZoneVector<TopLevelLiveRange*>& GetFixedRegisters() const; |
1003 const char* RegisterName(int allocation_index) const; | 1014 const char* RegisterName(int allocation_index) const; |
1004 | 1015 |
1005 private: | 1016 private: |
1006 RegisterAllocationData* const data_; | 1017 RegisterAllocationData* const data_; |
1007 const RegisterKind mode_; | 1018 const RegisterKind mode_; |
1008 const int num_registers_; | 1019 const int num_registers_; |
1009 int num_allocatable_registers_; | 1020 int num_allocatable_registers_; |
1010 const int* allocatable_register_codes_; | 1021 const int* allocatable_register_codes_; |
1011 | 1022 |
| 1023 private: |
| 1024 bool no_combining_; |
| 1025 |
1012 DISALLOW_COPY_AND_ASSIGN(RegisterAllocator); | 1026 DISALLOW_COPY_AND_ASSIGN(RegisterAllocator); |
1013 }; | 1027 }; |
1014 | 1028 |
1015 | 1029 |
1016 class LinearScanAllocator final : public RegisterAllocator { | 1030 class LinearScanAllocator final : public RegisterAllocator { |
1017 public: | 1031 public: |
1018 LinearScanAllocator(RegisterAllocationData* data, RegisterKind kind, | 1032 LinearScanAllocator(RegisterAllocationData* data, RegisterKind kind, |
1019 Zone* local_zone); | 1033 Zone* local_zone); |
1020 | 1034 |
1021 // Phase 4: compute register assignments. | 1035 // Phase 4: compute register assignments. |
(...skipping 145 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1167 RegisterAllocationData* const data_; | 1181 RegisterAllocationData* const data_; |
1168 | 1182 |
1169 DISALLOW_COPY_AND_ASSIGN(LiveRangeConnector); | 1183 DISALLOW_COPY_AND_ASSIGN(LiveRangeConnector); |
1170 }; | 1184 }; |
1171 | 1185 |
1172 } // namespace compiler | 1186 } // namespace compiler |
1173 } // namespace internal | 1187 } // namespace internal |
1174 } // namespace v8 | 1188 } // namespace v8 |
1175 | 1189 |
1176 #endif // V8_REGISTER_ALLOCATOR_H_ | 1190 #endif // V8_REGISTER_ALLOCATOR_H_ |
OLD | NEW |