| 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/zone-containers.h" | 9 #include "src/zone-containers.h" |
| 10 | 10 |
| (...skipping 192 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 203 typedef BitField8<UsePositionType, 0, 2> TypeField; | 203 typedef BitField8<UsePositionType, 0, 2> TypeField; |
| 204 typedef BitField8<bool, 2, 1> RegisterBeneficialField; | 204 typedef BitField8<bool, 2, 1> RegisterBeneficialField; |
| 205 uint8_t flags_; | 205 uint8_t flags_; |
| 206 | 206 |
| 207 DISALLOW_COPY_AND_ASSIGN(UsePosition); | 207 DISALLOW_COPY_AND_ASSIGN(UsePosition); |
| 208 }; | 208 }; |
| 209 | 209 |
| 210 class SpillRange; | 210 class SpillRange; |
| 211 | 211 |
| 212 | 212 |
| 213 // TODO(dcarney): remove this cache. | |
| 214 class InstructionOperandCache FINAL : public ZoneObject { | |
| 215 public: | |
| 216 InstructionOperandCache(); | |
| 217 | |
| 218 RegisterOperand* GetRegisterOperand(int index) { | |
| 219 DCHECK(index >= 0 && | |
| 220 index < static_cast<int>(arraysize(general_register_operands_))); | |
| 221 return RegisterOperand::cast(&general_register_operands_[index]); | |
| 222 } | |
| 223 DoubleRegisterOperand* GetDoubleRegisterOperand(int index) { | |
| 224 DCHECK(index >= 0 && | |
| 225 index < static_cast<int>(arraysize(double_register_operands_))); | |
| 226 return DoubleRegisterOperand::cast(&double_register_operands_[index]); | |
| 227 } | |
| 228 | |
| 229 private: | |
| 230 InstructionOperand | |
| 231 general_register_operands_[RegisterConfiguration::kMaxGeneralRegisters]; | |
| 232 InstructionOperand | |
| 233 double_register_operands_[RegisterConfiguration::kMaxDoubleRegisters]; | |
| 234 | |
| 235 DISALLOW_COPY_AND_ASSIGN(InstructionOperandCache); | |
| 236 }; | |
| 237 | |
| 238 | |
| 239 // Representation of SSA values' live ranges as a collection of (continuous) | 213 // Representation of SSA values' live ranges as a collection of (continuous) |
| 240 // intervals over the instruction ordering. | 214 // intervals over the instruction ordering. |
| 241 class LiveRange FINAL : public ZoneObject { | 215 class LiveRange FINAL : public ZoneObject { |
| 242 public: | 216 public: |
| 243 static const int kInvalidAssignment = 0x7fffffff; | 217 static const int kInvalidAssignment = 0x7fffffff; |
| 244 | 218 |
| 245 LiveRange(int id, Zone* zone); | 219 LiveRange(int id, Zone* zone); |
| 246 | 220 |
| 247 UseInterval* first_interval() const { return first_interval_; } | 221 UseInterval* first_interval() const { return first_interval_; } |
| 248 UsePosition* first_pos() const { return first_pos_; } | 222 UsePosition* first_pos() const { return first_pos_; } |
| 249 LiveRange* parent() const { return parent_; } | 223 LiveRange* parent() const { return parent_; } |
| 250 LiveRange* TopLevel() { return (parent_ == nullptr) ? this : parent_; } | 224 LiveRange* TopLevel() { return (parent_ == nullptr) ? this : parent_; } |
| 251 const LiveRange* TopLevel() const { | 225 const LiveRange* TopLevel() const { |
| 252 return (parent_ == nullptr) ? this : parent_; | 226 return (parent_ == nullptr) ? this : parent_; |
| 253 } | 227 } |
| 254 LiveRange* next() const { return next_; } | 228 LiveRange* next() const { return next_; } |
| 255 bool IsChild() const { return parent() != nullptr; } | 229 bool IsChild() const { return parent() != nullptr; } |
| 256 int id() const { return id_; } | 230 int id() const { return id_; } |
| 257 bool IsFixed() const { return id_ < 0; } | 231 bool IsFixed() const { return id_ < 0; } |
| 258 bool IsEmpty() const { return first_interval() == nullptr; } | 232 bool IsEmpty() const { return first_interval() == nullptr; } |
| 259 // TODO(dcarney): remove this. | |
| 260 InstructionOperand* GetAssignedOperand(InstructionOperandCache* cache) const; | |
| 261 InstructionOperand GetAssignedOperand() const; | 233 InstructionOperand GetAssignedOperand() const; |
| 262 int assigned_register() const { return assigned_register_; } | 234 int assigned_register() const { return assigned_register_; } |
| 263 int spill_start_index() const { return spill_start_index_; } | 235 int spill_start_index() const { return spill_start_index_; } |
| 264 void set_assigned_register(int reg, InstructionOperandCache* cache); | 236 void set_assigned_register(int reg); |
| 265 void MakeSpilled(); | 237 void MakeSpilled(); |
| 266 bool is_phi() const { return is_phi_; } | 238 bool is_phi() const { return is_phi_; } |
| 267 void set_is_phi(bool is_phi) { is_phi_ = is_phi; } | 239 void set_is_phi(bool is_phi) { is_phi_ = is_phi; } |
| 268 bool is_non_loop_phi() const { return is_non_loop_phi_; } | 240 bool is_non_loop_phi() const { return is_non_loop_phi_; } |
| 269 void set_is_non_loop_phi(bool is_non_loop_phi) { | 241 void set_is_non_loop_phi(bool is_non_loop_phi) { |
| 270 is_non_loop_phi_ = is_non_loop_phi; | 242 is_non_loop_phi_ = is_non_loop_phi; |
| 271 } | 243 } |
| 272 bool has_slot_use() const { return has_slot_use_; } | 244 bool has_slot_use() const { return has_slot_use_; } |
| 273 void set_has_slot_use(bool has_slot_use) { has_slot_use_ = has_slot_use; } | 245 void set_has_slot_use(bool has_slot_use) { has_slot_use_ = has_slot_use; } |
| 274 | 246 |
| (...skipping 95 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 370 | 342 |
| 371 #ifdef DEBUG | 343 #ifdef DEBUG |
| 372 // True if target overlaps an existing interval. | 344 // True if target overlaps an existing interval. |
| 373 bool HasOverlap(UseInterval* target) const; | 345 bool HasOverlap(UseInterval* target) const; |
| 374 void Verify() const; | 346 void Verify() const; |
| 375 #endif | 347 #endif |
| 376 | 348 |
| 377 private: | 349 private: |
| 378 struct SpillAtDefinitionList; | 350 struct SpillAtDefinitionList; |
| 379 | 351 |
| 380 void ConvertUsesToOperand(InstructionOperand* op, | 352 void ConvertUsesToOperand(const InstructionOperand& op, |
| 381 InstructionOperand* spill_op); | 353 InstructionOperand* spill_op); |
| 382 UseInterval* FirstSearchIntervalForPosition(LifetimePosition position) const; | 354 UseInterval* FirstSearchIntervalForPosition(LifetimePosition position) const; |
| 383 void AdvanceLastProcessedMarker(UseInterval* to_start_of, | 355 void AdvanceLastProcessedMarker(UseInterval* to_start_of, |
| 384 LifetimePosition but_not_past) const; | 356 LifetimePosition but_not_past) const; |
| 385 | 357 |
| 386 // TODO(dcarney): pack this structure better. | 358 // TODO(dcarney): pack this structure better. |
| 387 int id_; | 359 int id_; |
| 388 bool spilled_ : 1; | 360 bool spilled_ : 1; |
| 389 bool has_slot_use_ : 1; // Relevant only for parent. | 361 bool has_slot_use_ : 1; // Relevant only for parent. |
| 390 bool is_phi_ : 1; | 362 bool is_phi_ : 1; |
| (...skipping 229 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 620 LiveRange* LiveRangeFor(int index); | 592 LiveRange* LiveRangeFor(int index); |
| 621 Instruction* GetLastInstruction(const InstructionBlock* block); | 593 Instruction* GetLastInstruction(const InstructionBlock* block); |
| 622 | 594 |
| 623 const char* RegisterName(int allocation_index); | 595 const char* RegisterName(int allocation_index); |
| 624 | 596 |
| 625 Instruction* InstructionAt(int index) { return code()->InstructionAt(index); } | 597 Instruction* InstructionAt(int index) { return code()->InstructionAt(index); } |
| 626 | 598 |
| 627 Frame* frame() const { return frame_; } | 599 Frame* frame() const { return frame_; } |
| 628 const char* debug_name() const { return debug_name_; } | 600 const char* debug_name() const { return debug_name_; } |
| 629 const RegisterConfiguration* config() const { return config_; } | 601 const RegisterConfiguration* config() const { return config_; } |
| 630 InstructionOperandCache* operand_cache() const { return operand_cache_; } | |
| 631 ZoneVector<LiveRange*>& live_ranges() { return live_ranges_; } | 602 ZoneVector<LiveRange*>& live_ranges() { return live_ranges_; } |
| 632 ZoneVector<LiveRange*>& fixed_live_ranges() { return fixed_live_ranges_; } | 603 ZoneVector<LiveRange*>& fixed_live_ranges() { return fixed_live_ranges_; } |
| 633 ZoneVector<LiveRange*>& fixed_double_live_ranges() { | 604 ZoneVector<LiveRange*>& fixed_double_live_ranges() { |
| 634 return fixed_double_live_ranges_; | 605 return fixed_double_live_ranges_; |
| 635 } | 606 } |
| 636 ZoneVector<LiveRange*>& unhandled_live_ranges() { | 607 ZoneVector<LiveRange*>& unhandled_live_ranges() { |
| 637 return unhandled_live_ranges_; | 608 return unhandled_live_ranges_; |
| 638 } | 609 } |
| 639 ZoneVector<LiveRange*>& active_live_ranges() { return active_live_ranges_; } | 610 ZoneVector<LiveRange*>& active_live_ranges() { return active_live_ranges_; } |
| 640 ZoneVector<LiveRange*>& inactive_live_ranges() { | 611 ZoneVector<LiveRange*>& inactive_live_ranges() { |
| 641 return inactive_live_ranges_; | 612 return inactive_live_ranges_; |
| 642 } | 613 } |
| 643 ZoneVector<SpillRange*>& spill_ranges() { return spill_ranges_; } | 614 ZoneVector<SpillRange*>& spill_ranges() { return spill_ranges_; } |
| 644 | 615 |
| 645 struct PhiMapValue { | 616 struct PhiMapValue { |
| 646 PhiMapValue(PhiInstruction* phi, const InstructionBlock* block) | 617 PhiMapValue(PhiInstruction* phi, const InstructionBlock* block) |
| 647 : phi(phi), block(block) {} | 618 : phi(phi), block(block) {} |
| 648 PhiInstruction* const phi; | 619 PhiInstruction* const phi; |
| 649 const InstructionBlock* const block; | 620 const InstructionBlock* const block; |
| 650 }; | 621 }; |
| 651 typedef ZoneMap<int, PhiMapValue> PhiMap; | 622 typedef ZoneMap<int, PhiMapValue> PhiMap; |
| 652 | 623 |
| 653 Zone* const local_zone_; | 624 Zone* const local_zone_; |
| 654 Frame* const frame_; | 625 Frame* const frame_; |
| 655 InstructionSequence* const code_; | 626 InstructionSequence* const code_; |
| 656 const char* const debug_name_; | 627 const char* const debug_name_; |
| 657 | 628 |
| 658 const RegisterConfiguration* config_; | 629 const RegisterConfiguration* config_; |
| 659 InstructionOperandCache* const operand_cache_; | |
| 660 PhiMap phi_map_; | 630 PhiMap phi_map_; |
| 661 | 631 |
| 662 // During liveness analysis keep a mapping from block id to live_in sets | 632 // During liveness analysis keep a mapping from block id to live_in sets |
| 663 // for blocks already analyzed. | 633 // for blocks already analyzed. |
| 664 ZoneVector<BitVector*> live_in_sets_; | 634 ZoneVector<BitVector*> live_in_sets_; |
| 665 | 635 |
| 666 // Liveness analysis results. | 636 // Liveness analysis results. |
| 667 ZoneVector<LiveRange*> live_ranges_; | 637 ZoneVector<LiveRange*> live_ranges_; |
| 668 | 638 |
| 669 // Lists of live ranges | 639 // Lists of live ranges |
| (...skipping 15 matching lines...) Expand all Loading... |
| 685 #endif | 655 #endif |
| 686 | 656 |
| 687 DISALLOW_COPY_AND_ASSIGN(RegisterAllocator); | 657 DISALLOW_COPY_AND_ASSIGN(RegisterAllocator); |
| 688 }; | 658 }; |
| 689 | 659 |
| 690 } // namespace compiler | 660 } // namespace compiler |
| 691 } // namespace internal | 661 } // namespace internal |
| 692 } // namespace v8 | 662 } // namespace v8 |
| 693 | 663 |
| 694 #endif // V8_REGISTER_ALLOCATOR_H_ | 664 #endif // V8_REGISTER_ALLOCATOR_H_ |
| OLD | NEW |