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 |