| 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 180 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 191 LiveRange* next() const { return next_; } | 191 LiveRange* next() const { return next_; } |
| 192 bool IsChild() const { return parent() != NULL; } | 192 bool IsChild() const { return parent() != NULL; } |
| 193 int id() const { return id_; } | 193 int id() const { return id_; } |
| 194 bool IsFixed() const { return id_ < 0; } | 194 bool IsFixed() const { return id_ < 0; } |
| 195 bool IsEmpty() const { return first_interval() == NULL; } | 195 bool IsEmpty() const { return first_interval() == NULL; } |
| 196 InstructionOperand* CreateAssignedOperand(Zone* zone) const; | 196 InstructionOperand* CreateAssignedOperand(Zone* zone) const; |
| 197 int assigned_register() const { return assigned_register_; } | 197 int assigned_register() const { return assigned_register_; } |
| 198 int spill_start_index() const { return spill_start_index_; } | 198 int spill_start_index() const { return spill_start_index_; } |
| 199 void set_assigned_register(int reg, Zone* zone); | 199 void set_assigned_register(int reg, Zone* zone); |
| 200 void MakeSpilled(Zone* zone); | 200 void MakeSpilled(Zone* zone); |
| 201 bool is_phi() const { return is_phi_; } |
| 202 void set_is_phi(bool is_phi) { is_phi_ = is_phi; } |
| 203 bool is_non_loop_phi() const { return is_non_loop_phi_; } |
| 204 void set_is_non_loop_phi(bool is_non_loop_phi) { |
| 205 is_non_loop_phi_ = is_non_loop_phi; |
| 206 } |
| 201 | 207 |
| 202 // Returns use position in this live range that follows both start | 208 // Returns use position in this live range that follows both start |
| 203 // and last processed use position. | 209 // and last processed use position. |
| 204 // Modifies internal state of live range! | 210 // Modifies internal state of live range! |
| 205 UsePosition* NextUsePosition(LifetimePosition start); | 211 UsePosition* NextUsePosition(LifetimePosition start); |
| 206 | 212 |
| 207 // Returns use position for which register is required in this live | 213 // Returns use position for which register is required in this live |
| 208 // range and which follows both start and last processed use position | 214 // range and which follows both start and last processed use position |
| 209 // Modifies internal state of live range! | 215 // Modifies internal state of live range! |
| 210 UsePosition* NextRegisterPosition(LifetimePosition start); | 216 UsePosition* NextRegisterPosition(LifetimePosition start); |
| (...skipping 77 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 288 | 294 |
| 289 private: | 295 private: |
| 290 void ConvertOperands(Zone* zone); | 296 void ConvertOperands(Zone* zone); |
| 291 void ConvertUsesToOperand(InstructionOperand* op); | 297 void ConvertUsesToOperand(InstructionOperand* op); |
| 292 UseInterval* FirstSearchIntervalForPosition(LifetimePosition position) const; | 298 UseInterval* FirstSearchIntervalForPosition(LifetimePosition position) const; |
| 293 void AdvanceLastProcessedMarker(UseInterval* to_start_of, | 299 void AdvanceLastProcessedMarker(UseInterval* to_start_of, |
| 294 LifetimePosition but_not_past) const; | 300 LifetimePosition but_not_past) const; |
| 295 | 301 |
| 296 int id_; | 302 int id_; |
| 297 bool spilled_; | 303 bool spilled_; |
| 304 bool is_phi_; |
| 305 bool is_non_loop_phi_; |
| 298 RegisterKind kind_; | 306 RegisterKind kind_; |
| 299 int assigned_register_; | 307 int assigned_register_; |
| 300 UseInterval* last_interval_; | 308 UseInterval* last_interval_; |
| 301 UseInterval* first_interval_; | 309 UseInterval* first_interval_; |
| 302 UsePosition* first_pos_; | 310 UsePosition* first_pos_; |
| 303 LiveRange* parent_; | 311 LiveRange* parent_; |
| 304 LiveRange* next_; | 312 LiveRange* next_; |
| 305 // This is used as a cache, it doesn't affect correctness. | 313 // This is used as a cache, it doesn't affect correctness. |
| 306 mutable UseInterval* current_interval_; | 314 mutable UseInterval* current_interval_; |
| 307 UsePosition* last_processed_use_; | 315 UsePosition* last_processed_use_; |
| (...skipping 48 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 356 const ZoneVector<LiveRange*>& fixed_double_live_ranges() const { | 364 const ZoneVector<LiveRange*>& fixed_double_live_ranges() const { |
| 357 return fixed_double_live_ranges_; | 365 return fixed_double_live_ranges_; |
| 358 } | 366 } |
| 359 InstructionSequence* code() const { return code_; } | 367 InstructionSequence* code() const { return code_; } |
| 360 // This zone is for datastructures only needed during register allocation. | 368 // This zone is for datastructures only needed during register allocation. |
| 361 Zone* local_zone() const { return local_zone_; } | 369 Zone* local_zone() const { return local_zone_; } |
| 362 | 370 |
| 363 // Phase 1 : insert moves to account for fixed register operands. | 371 // Phase 1 : insert moves to account for fixed register operands. |
| 364 void MeetRegisterConstraints(); | 372 void MeetRegisterConstraints(); |
| 365 | 373 |
| 366 // Phase 2: compute liveness of all virtual register. | 374 // Phase 2: deconstruct SSA by inserting moves in successors and the headers |
| 375 // of blocks containing phis. |
| 376 void ResolvePhis(); |
| 377 |
| 378 // Phase 3: compute liveness of all virtual register. |
| 367 void BuildLiveRanges(); | 379 void BuildLiveRanges(); |
| 368 bool ExistsUseWithoutDefinition(); | 380 bool ExistsUseWithoutDefinition(); |
| 369 | 381 |
| 370 // Phase 3: compute register assignments. | 382 // Phase 4: compute register assignments. |
| 371 void AllocateGeneralRegisters(); | 383 void AllocateGeneralRegisters(); |
| 372 void AllocateDoubleRegisters(); | 384 void AllocateDoubleRegisters(); |
| 373 | 385 |
| 374 // Phase 4: reassign spill splots for maximal reuse. | 386 // Phase 5: reassign spill splots for maximal reuse. |
| 375 void ReuseSpillSlots(); | 387 void ReuseSpillSlots(); |
| 376 | 388 |
| 377 // Phase 5: compute values for pointer maps. | 389 // Phase 6: compute values for pointer maps. |
| 378 void PopulatePointerMaps(); // TODO(titzer): rename to PopulateReferenceMaps. | 390 void PopulatePointerMaps(); // TODO(titzer): rename to PopulateReferenceMaps. |
| 379 | 391 |
| 380 // Phase 6: reconnect split ranges with moves. | 392 // Phase 7: reconnect split ranges with moves. |
| 381 void ConnectRanges(); | 393 void ConnectRanges(); |
| 382 | 394 |
| 383 // Phase 7: insert moves to connect ranges across basic blocks. | 395 // Phase 8: insert moves to connect ranges across basic blocks. |
| 384 void ResolveControlFlow(); | 396 void ResolveControlFlow(); |
| 385 | 397 |
| 386 private: | 398 private: |
| 387 int GetVirtualRegister() { | 399 int GetVirtualRegister() { |
| 388 int vreg = code()->NextVirtualRegister(); | 400 int vreg = code()->NextVirtualRegister(); |
| 389 if (vreg >= UnallocatedOperand::kMaxVirtualRegisters) { | 401 if (vreg >= UnallocatedOperand::kMaxVirtualRegisters) { |
| 390 allocation_ok_ = false; | 402 allocation_ok_ = false; |
| 391 // Maintain the invariant that we return something below the maximum. | 403 // Maintain the invariant that we return something below the maximum. |
| 392 return 0; | 404 return 0; |
| 393 } | 405 } |
| (...skipping 27 matching lines...) Expand all Loading... |
| 421 BitVector* ComputeLiveOut(const InstructionBlock* block); | 433 BitVector* ComputeLiveOut(const InstructionBlock* block); |
| 422 void AddInitialIntervals(const InstructionBlock* block, BitVector* live_out); | 434 void AddInitialIntervals(const InstructionBlock* block, BitVector* live_out); |
| 423 bool IsOutputRegisterOf(Instruction* instr, int index); | 435 bool IsOutputRegisterOf(Instruction* instr, int index); |
| 424 bool IsOutputDoubleRegisterOf(Instruction* instr, int index); | 436 bool IsOutputDoubleRegisterOf(Instruction* instr, int index); |
| 425 void ProcessInstructions(const InstructionBlock* block, BitVector* live); | 437 void ProcessInstructions(const InstructionBlock* block, BitVector* live); |
| 426 void MeetRegisterConstraints(const InstructionBlock* block); | 438 void MeetRegisterConstraints(const InstructionBlock* block); |
| 427 void MeetConstraintsBetween(Instruction* first, Instruction* second, | 439 void MeetConstraintsBetween(Instruction* first, Instruction* second, |
| 428 int gap_index); | 440 int gap_index); |
| 429 void MeetRegisterConstraintsForLastInstructionInBlock( | 441 void MeetRegisterConstraintsForLastInstructionInBlock( |
| 430 const InstructionBlock* block); | 442 const InstructionBlock* block); |
| 431 void ProcessPhis(const InstructionBlock* block); | 443 void ResolvePhis(const InstructionBlock* block); |
| 432 | 444 |
| 433 // Helper methods for building intervals. | 445 // Helper methods for building intervals. |
| 434 InstructionOperand* AllocateFixed(UnallocatedOperand* operand, int pos, | 446 InstructionOperand* AllocateFixed(UnallocatedOperand* operand, int pos, |
| 435 bool is_tagged); | 447 bool is_tagged); |
| 436 LiveRange* LiveRangeFor(InstructionOperand* operand); | 448 LiveRange* LiveRangeFor(InstructionOperand* operand); |
| 437 void Define(LifetimePosition position, InstructionOperand* operand, | 449 void Define(LifetimePosition position, InstructionOperand* operand, |
| 438 InstructionOperand* hint); | 450 InstructionOperand* hint); |
| 439 void Use(LifetimePosition block_start, LifetimePosition position, | 451 void Use(LifetimePosition block_start, LifetimePosition position, |
| 440 InstructionOperand* operand, InstructionOperand* hint); | 452 InstructionOperand* operand, InstructionOperand* hint); |
| 441 void AddConstraintsGapMove(int index, InstructionOperand* from, | 453 void AddConstraintsGapMove(int index, InstructionOperand* from, |
| (...skipping 129 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 571 #endif | 583 #endif |
| 572 | 584 |
| 573 DISALLOW_COPY_AND_ASSIGN(RegisterAllocator); | 585 DISALLOW_COPY_AND_ASSIGN(RegisterAllocator); |
| 574 }; | 586 }; |
| 575 | 587 |
| 576 } | 588 } |
| 577 } | 589 } |
| 578 } // namespace v8::internal::compiler | 590 } // namespace v8::internal::compiler |
| 579 | 591 |
| 580 #endif // V8_REGISTER_ALLOCATOR_H_ | 592 #endif // V8_REGISTER_ALLOCATOR_H_ |
| OLD | NEW |