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 322 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
333 | 333 |
334 // Add a new interval or a new use position to this live range. | 334 // Add a new interval or a new use position to this live range. |
335 void EnsureInterval(LifetimePosition start, LifetimePosition end, Zone* zone); | 335 void EnsureInterval(LifetimePosition start, LifetimePosition end, Zone* zone); |
336 void AddUseInterval(LifetimePosition start, LifetimePosition end, Zone* zone); | 336 void AddUseInterval(LifetimePosition start, LifetimePosition end, Zone* zone); |
337 void AddUsePosition(LifetimePosition pos, InstructionOperand* operand, | 337 void AddUsePosition(LifetimePosition pos, InstructionOperand* operand, |
338 InstructionOperand* hint, Zone* zone); | 338 InstructionOperand* hint, Zone* zone); |
339 | 339 |
340 // Shorten the most recently added interval by setting a new start. | 340 // Shorten the most recently added interval by setting a new start. |
341 void ShortenTo(LifetimePosition start); | 341 void ShortenTo(LifetimePosition start); |
342 | 342 |
343 #ifdef DEBUG | |
344 // True if target overlaps an existing interval. | 343 // True if target overlaps an existing interval. |
345 bool HasOverlap(UseInterval* target) const; | 344 bool HasOverlap(UseInterval* target) const; |
346 void Verify() const; | 345 void Verify() const; |
347 #endif | 346 |
| 347 void ConvertUsesToOperand(const InstructionOperand& op, |
| 348 InstructionOperand* spill_op); |
| 349 |
| 350 void set_kind(RegisterKind kind) { kind_ = kind; } |
348 | 351 |
349 private: | 352 private: |
350 struct SpillAtDefinitionList; | 353 struct SpillAtDefinitionList; |
351 | 354 |
352 void ConvertUsesToOperand(const InstructionOperand& op, | |
353 InstructionOperand* spill_op); | |
354 UseInterval* FirstSearchIntervalForPosition(LifetimePosition position) const; | 355 UseInterval* FirstSearchIntervalForPosition(LifetimePosition position) const; |
355 void AdvanceLastProcessedMarker(UseInterval* to_start_of, | 356 void AdvanceLastProcessedMarker(UseInterval* to_start_of, |
356 LifetimePosition but_not_past) const; | 357 LifetimePosition but_not_past) const; |
357 | 358 |
358 // TODO(dcarney): pack this structure better. | 359 // TODO(dcarney): pack this structure better. |
359 int id_; | 360 int id_; |
360 bool spilled_ : 1; | 361 bool spilled_ : 1; |
361 bool has_slot_use_ : 1; // Relevant only for parent. | 362 bool has_slot_use_ : 1; // Relevant only for parent. |
362 bool is_phi_ : 1; | 363 bool is_phi_ : 1; |
363 bool is_non_loop_phi_ : 1; | 364 bool is_non_loop_phi_ : 1; |
(...skipping 10 matching lines...) Expand all Loading... |
374 // This is used as a cache, it's invalid outside of BuildLiveRanges. | 375 // This is used as a cache, it's invalid outside of BuildLiveRanges. |
375 InstructionOperand* current_hint_operand_; | 376 InstructionOperand* current_hint_operand_; |
376 int spill_start_index_; | 377 int spill_start_index_; |
377 SpillType spill_type_; | 378 SpillType spill_type_; |
378 union { | 379 union { |
379 InstructionOperand* spill_operand_; | 380 InstructionOperand* spill_operand_; |
380 SpillRange* spill_range_; | 381 SpillRange* spill_range_; |
381 }; | 382 }; |
382 SpillAtDefinitionList* spills_at_definition_; | 383 SpillAtDefinitionList* spills_at_definition_; |
383 | 384 |
384 friend class RegisterAllocator; // Assigns to kind_. | |
385 | |
386 DISALLOW_COPY_AND_ASSIGN(LiveRange); | 385 DISALLOW_COPY_AND_ASSIGN(LiveRange); |
387 }; | 386 }; |
388 | 387 |
389 | 388 |
390 class SpillRange final : public ZoneObject { | 389 class SpillRange final : public ZoneObject { |
391 public: | 390 public: |
392 SpillRange(LiveRange* range, Zone* zone); | 391 SpillRange(LiveRange* range, Zone* zone); |
393 | 392 |
394 UseInterval* interval() const { return use_interval_; } | 393 UseInterval* interval() const { return use_interval_; } |
395 RegisterKind Kind() const { return live_ranges_[0]->Kind(); } | 394 RegisterKind Kind() const { return live_ranges_[0]->Kind(); } |
396 bool IsEmpty() const { return live_ranges_.empty(); } | 395 bool IsEmpty() const { return live_ranges_.empty(); } |
397 bool TryMerge(SpillRange* other); | 396 bool TryMerge(SpillRange* other); |
398 void SetOperand(AllocatedOperand* op); | 397 void SetOperand(AllocatedOperand* op); |
399 | 398 |
400 private: | 399 private: |
401 LifetimePosition End() const { return end_position_; } | 400 LifetimePosition End() const { return end_position_; } |
402 ZoneVector<LiveRange*>& live_ranges() { return live_ranges_; } | 401 ZoneVector<LiveRange*>& live_ranges() { return live_ranges_; } |
403 bool IsIntersectingWith(SpillRange* other) const; | 402 bool IsIntersectingWith(SpillRange* other) const; |
404 // Merge intervals, making sure the use intervals are sorted | 403 // Merge intervals, making sure the use intervals are sorted |
405 void MergeDisjointIntervals(UseInterval* other); | 404 void MergeDisjointIntervals(UseInterval* other); |
406 | 405 |
407 ZoneVector<LiveRange*> live_ranges_; | 406 ZoneVector<LiveRange*> live_ranges_; |
408 UseInterval* use_interval_; | 407 UseInterval* use_interval_; |
409 LifetimePosition end_position_; | 408 LifetimePosition end_position_; |
410 | 409 |
411 DISALLOW_COPY_AND_ASSIGN(SpillRange); | 410 DISALLOW_COPY_AND_ASSIGN(SpillRange); |
412 }; | 411 }; |
413 | 412 |
414 | 413 |
415 class RegisterAllocator final : public ZoneObject { | 414 class RegisterAllocationData final : public ZoneObject { |
416 public: | 415 public: |
417 explicit RegisterAllocator(const RegisterConfiguration* config, | 416 class PhiMapValue : public ZoneObject { |
418 Zone* local_zone, Frame* frame, | 417 public: |
419 InstructionSequence* code, | 418 PhiMapValue(PhiInstruction* phi, const InstructionBlock* block, Zone* zone) |
420 const char* debug_name = nullptr); | 419 : phi(phi), block(block), incoming_moves(zone) { |
| 420 incoming_moves.reserve(phi->operands().size()); |
| 421 } |
| 422 PhiInstruction* const phi; |
| 423 const InstructionBlock* const block; |
| 424 ZoneVector<MoveOperands*> incoming_moves; |
| 425 }; |
| 426 typedef ZoneMap<int, PhiMapValue*> PhiMap; |
| 427 |
| 428 RegisterAllocationData(const RegisterConfiguration* config, |
| 429 Zone* allocation_zone, Frame* frame, |
| 430 InstructionSequence* code, |
| 431 const char* debug_name = nullptr); |
421 | 432 |
422 const ZoneVector<LiveRange*>& live_ranges() const { return live_ranges_; } | 433 const ZoneVector<LiveRange*>& live_ranges() const { return live_ranges_; } |
| 434 ZoneVector<LiveRange*>& live_ranges() { return live_ranges_; } |
423 const ZoneVector<LiveRange*>& fixed_live_ranges() const { | 435 const ZoneVector<LiveRange*>& fixed_live_ranges() const { |
424 return fixed_live_ranges_; | 436 return fixed_live_ranges_; |
425 } | 437 } |
| 438 ZoneVector<LiveRange*>& fixed_live_ranges() { return fixed_live_ranges_; } |
| 439 ZoneVector<LiveRange*>& fixed_double_live_ranges() { |
| 440 return fixed_double_live_ranges_; |
| 441 } |
426 const ZoneVector<LiveRange*>& fixed_double_live_ranges() const { | 442 const ZoneVector<LiveRange*>& fixed_double_live_ranges() const { |
427 return fixed_double_live_ranges_; | 443 return fixed_double_live_ranges_; |
428 } | 444 } |
| 445 const ZoneVector<BitVector*>& live_in_sets() const { return live_in_sets_; } |
| 446 ZoneVector<BitVector*>& live_in_sets() { return live_in_sets_; } |
| 447 ZoneVector<SpillRange*>& spill_ranges() { return spill_ranges_; } |
| 448 const ZoneVector<SpillRange*>& spill_ranges() const { return spill_ranges_; } |
429 InstructionSequence* code() const { return code_; } | 449 InstructionSequence* code() const { return code_; } |
430 // This zone is for datastructures only needed during register allocation. | 450 // This zone is for datastructures only needed during register allocation |
431 Zone* local_zone() const { return local_zone_; } | 451 // phases. |
| 452 Zone* allocation_zone() const { return allocation_zone_; } |
| 453 // This zone is for InstructionOperands and moves that live beyond register |
| 454 // allocation. |
| 455 Zone* code_zone() const { return code()->zone(); } |
| 456 const PhiMap& phi_map() const { return phi_map_; } |
| 457 PhiMap& phi_map() { return phi_map_; } |
| 458 Frame* frame() const { return frame_; } |
| 459 const char* debug_name() const { return debug_name_; } |
| 460 const RegisterConfiguration* config() const { return config_; } |
| 461 |
| 462 void SetLiveRangeAssignedRegister(LiveRange* range, int reg); |
| 463 LiveRange* LiveRangeFor(int index); |
| 464 Instruction* InstructionAt(int index) { return code()->InstructionAt(index); } |
| 465 |
| 466 void AssignPhiInput(LiveRange* range, const InstructionOperand& assignment); |
| 467 SpillRange* AssignSpillRangeToLiveRange(LiveRange* range); |
| 468 |
| 469 MoveOperands* AddGapMove(int index, Instruction::GapPosition position, |
| 470 const InstructionOperand& from, |
| 471 const InstructionOperand& to); |
| 472 |
| 473 bool IsBlockBoundary(LifetimePosition pos) { |
| 474 return pos.IsFullStart() && |
| 475 code() |
| 476 ->GetInstructionBlock(pos.ToInstructionIndex()) |
| 477 ->code_start() == pos.ToInstructionIndex(); |
| 478 } |
| 479 |
| 480 const InstructionBlock* GetInstructionBlock(LifetimePosition pos) const { |
| 481 return code()->GetInstructionBlock(pos.ToInstructionIndex()); |
| 482 } |
| 483 |
| 484 bool IsReference(int virtual_register) const { |
| 485 return code()->IsReference(virtual_register); |
| 486 } |
| 487 |
| 488 bool ExistsUseWithoutDefinition(); |
| 489 |
| 490 // Creates a new live range. |
| 491 LiveRange* NewLiveRange(int index); |
| 492 |
| 493 private: |
| 494 Zone* const allocation_zone_; |
| 495 Frame* const frame_; |
| 496 InstructionSequence* const code_; |
| 497 const char* const debug_name_; |
| 498 const RegisterConfiguration* const config_; |
| 499 PhiMap phi_map_; |
| 500 ZoneVector<BitVector*> live_in_sets_; |
| 501 ZoneVector<LiveRange*> live_ranges_; |
| 502 ZoneVector<LiveRange*> fixed_live_ranges_; |
| 503 ZoneVector<LiveRange*> fixed_double_live_ranges_; |
| 504 ZoneVector<SpillRange*> spill_ranges_; |
| 505 BitVector* assigned_registers_; |
| 506 BitVector* assigned_double_registers_; |
| 507 |
| 508 DISALLOW_COPY_AND_ASSIGN(RegisterAllocationData); |
| 509 }; |
| 510 |
| 511 |
| 512 class LiveRangeBuilder final : public ZoneObject { |
| 513 public: |
| 514 explicit LiveRangeBuilder(RegisterAllocationData* data); |
432 | 515 |
433 // Phase 1 : insert moves to account for fixed register operands. | 516 // Phase 1 : insert moves to account for fixed register operands. |
434 void MeetRegisterConstraints(); | 517 void MeetRegisterConstraints(); |
435 | 518 |
436 // Phase 2: deconstruct SSA by inserting moves in successors and the headers | 519 // Phase 2: deconstruct SSA by inserting moves in successors and the headers |
437 // of blocks containing phis. | 520 // of blocks containing phis. |
438 void ResolvePhis(); | 521 void ResolvePhis(); |
439 | 522 |
440 // Phase 3: compute liveness of all virtual register. | 523 // Phase 3: compute liveness of all virtual register. |
441 void BuildLiveRanges(); | 524 void BuildLiveRanges(); |
442 bool ExistsUseWithoutDefinition(); | |
443 | |
444 // Phase 4: compute register assignments. | |
445 void AllocateGeneralRegisters(); | |
446 void AllocateDoubleRegisters(); | |
447 | |
448 // Phase 5: assign spill splots. | |
449 void AssignSpillSlots(); | |
450 | |
451 // Phase 6: commit assignment. | |
452 void CommitAssignment(); | |
453 | |
454 // Phase 7: compute values for pointer maps. | |
455 void PopulateReferenceMaps(); | |
456 | |
457 // Phase 8: reconnect split ranges with moves. | |
458 void ConnectRanges(); | |
459 | |
460 // Phase 9: insert moves to connect ranges across basic blocks. | |
461 void ResolveControlFlow(); | |
462 | 525 |
463 private: | 526 private: |
464 int GetVirtualRegister() { return code()->NextVirtualRegister(); } | 527 RegisterAllocationData* data() const { return data_; } |
| 528 InstructionSequence* code() const { return data()->code(); } |
| 529 Zone* allocation_zone() const { return data()->allocation_zone(); } |
| 530 Zone* code_zone() const { return code()->zone(); } |
| 531 const RegisterConfiguration* config() const { return data()->config(); } |
| 532 ZoneVector<BitVector*>& live_in_sets() const { |
| 533 return data()->live_in_sets(); |
| 534 } |
| 535 ZoneVector<LiveRange*>& live_ranges() { return data()->live_ranges(); } |
| 536 ZoneVector<LiveRange*>& fixed_live_ranges() { |
| 537 return data()->fixed_live_ranges(); |
| 538 } |
| 539 ZoneVector<LiveRange*>& fixed_double_live_ranges() { |
| 540 return data()->fixed_double_live_ranges(); |
| 541 } |
| 542 ZoneVector<SpillRange*>& spill_ranges() { return data()->spill_ranges(); } |
| 543 RegisterAllocationData::PhiMap& phi_map() { return data()->phi_map(); } |
465 | 544 |
466 // Checks whether the value of a given virtual register is a reference. | 545 Instruction* InstructionAt(int index) { return code()->InstructionAt(index); } |
467 // TODO(titzer): rename this to IsReference. | 546 bool IsReference(int virtual_register) const { |
468 bool HasTaggedValue(int virtual_register) const; | 547 return data()->IsReference(virtual_register); |
| 548 } |
469 | 549 |
470 // Returns the register kind required by the given virtual register. | |
471 RegisterKind RequiredRegisterKind(int virtual_register) const; | |
472 | |
473 // Creates a new live range. | |
474 LiveRange* NewLiveRange(int index); | |
475 | |
476 // This zone is for InstructionOperands and moves that live beyond register | |
477 // allocation. | |
478 Zone* code_zone() const { return code()->zone(); } | |
479 | |
480 BitVector* assigned_registers() { return assigned_registers_; } | |
481 BitVector* assigned_double_registers() { return assigned_double_registers_; } | |
482 | |
483 #ifdef DEBUG | |
484 void Verify() const; | 550 void Verify() const; |
485 #endif | |
486 | |
487 void AllocateRegisters(); | |
488 bool CanEagerlyResolveControlFlow(const InstructionBlock* block) const; | |
489 bool SafePointsAreInOrder() const; | |
490 | 551 |
491 // Liveness analysis support. | 552 // Liveness analysis support. |
492 BitVector* ComputeLiveOut(const InstructionBlock* block); | 553 BitVector* ComputeLiveOut(const InstructionBlock* block); |
493 void AddInitialIntervals(const InstructionBlock* block, BitVector* live_out); | 554 void AddInitialIntervals(const InstructionBlock* block, BitVector* live_out); |
494 bool IsOutputRegisterOf(Instruction* instr, int index); | 555 bool IsOutputRegisterOf(Instruction* instr, int index); |
495 bool IsOutputDoubleRegisterOf(Instruction* instr, int index); | 556 bool IsOutputDoubleRegisterOf(Instruction* instr, int index); |
496 void ProcessInstructions(const InstructionBlock* block, BitVector* live); | 557 void ProcessInstructions(const InstructionBlock* block, BitVector* live); |
497 void MeetRegisterConstraints(const InstructionBlock* block); | 558 void MeetRegisterConstraints(const InstructionBlock* block); |
498 void MeetConstraintsBefore(int index); | 559 void MeetConstraintsBefore(int index); |
499 void MeetConstraintsAfter(int index); | 560 void MeetConstraintsAfter(int index); |
500 void MeetRegisterConstraintsForLastInstructionInBlock( | 561 void MeetRegisterConstraintsForLastInstructionInBlock( |
501 const InstructionBlock* block); | 562 const InstructionBlock* block); |
502 void ResolvePhis(const InstructionBlock* block); | 563 void ResolvePhis(const InstructionBlock* block); |
503 | 564 |
| 565 LiveRange* LiveRangeFor(int index) { return data()->LiveRangeFor(index); } |
| 566 static int FixedLiveRangeID(int index) { return -index - 1; } |
| 567 int FixedDoubleLiveRangeID(int index); |
| 568 LiveRange* FixedLiveRangeFor(int index); |
| 569 LiveRange* FixedDoubleLiveRangeFor(int index); |
| 570 Instruction* GetLastInstruction(const InstructionBlock* block); |
| 571 |
| 572 // Returns the register kind required by the given virtual register. |
| 573 RegisterKind RequiredRegisterKind(int virtual_register) const; |
| 574 |
504 // Helper methods for building intervals. | 575 // Helper methods for building intervals. |
505 InstructionOperand* AllocateFixed(UnallocatedOperand* operand, int pos, | 576 InstructionOperand* AllocateFixed(UnallocatedOperand* operand, int pos, |
506 bool is_tagged); | 577 bool is_tagged); |
507 LiveRange* LiveRangeFor(InstructionOperand* operand); | 578 LiveRange* LiveRangeFor(InstructionOperand* operand); |
508 void Define(LifetimePosition position, InstructionOperand* operand, | 579 void Define(LifetimePosition position, InstructionOperand* operand, |
509 InstructionOperand* hint); | 580 InstructionOperand* hint); |
510 void Use(LifetimePosition block_start, LifetimePosition position, | 581 void Use(LifetimePosition block_start, LifetimePosition position, |
511 InstructionOperand* operand, InstructionOperand* hint); | 582 InstructionOperand* operand, InstructionOperand* hint); |
512 MoveOperands* AddGapMove(int index, Instruction::GapPosition position, | 583 |
513 const InstructionOperand& from, | 584 RegisterAllocationData* const data_; |
514 const InstructionOperand& to); | 585 |
| 586 DISALLOW_COPY_AND_ASSIGN(LiveRangeBuilder); |
| 587 }; |
| 588 |
| 589 |
| 590 class LinearScanAllocator final : public ZoneObject { |
| 591 public: |
| 592 explicit LinearScanAllocator(RegisterAllocationData* data, RegisterKind kind); |
| 593 |
| 594 // Phase 4: compute register assignments. |
| 595 void AllocateRegisters(); |
| 596 |
| 597 private: |
| 598 RegisterAllocationData* data() const { return data_; } |
| 599 InstructionSequence* code() const { return data()->code(); } |
| 600 Zone* allocation_zone() const { return data()->allocation_zone(); } |
| 601 Zone* code_zone() const { return code()->zone(); } |
| 602 const RegisterConfiguration* config() const { return data()->config(); } |
| 603 |
| 604 Instruction* InstructionAt(int index) { return code()->InstructionAt(index); } |
| 605 |
| 606 int GetVirtualRegister() { return code()->NextVirtualRegister(); } |
| 607 |
| 608 bool IsReference(int virtual_register) const { |
| 609 return data()->IsReference(virtual_register); |
| 610 } |
| 611 |
| 612 LiveRange* LiveRangeFor(int index) { return data()->LiveRangeFor(index); } |
515 | 613 |
516 // Helper methods for updating the life range lists. | 614 // Helper methods for updating the life range lists. |
517 void AddToActive(LiveRange* range); | 615 void AddToActive(LiveRange* range); |
518 void AddToInactive(LiveRange* range); | 616 void AddToInactive(LiveRange* range); |
519 void AddToUnhandledSorted(LiveRange* range); | 617 void AddToUnhandledSorted(LiveRange* range); |
520 void AddToUnhandledUnsorted(LiveRange* range); | 618 void AddToUnhandledUnsorted(LiveRange* range); |
521 void SortUnhandled(); | 619 void SortUnhandled(); |
522 bool UnhandledIsSorted(); | 620 bool UnhandledIsSorted(); |
523 void ActiveToHandled(LiveRange* range); | 621 void ActiveToHandled(LiveRange* range); |
524 void ActiveToInactive(LiveRange* range); | 622 void ActiveToInactive(LiveRange* range); |
525 void InactiveToHandled(LiveRange* range); | 623 void InactiveToHandled(LiveRange* range); |
526 void InactiveToActive(LiveRange* range); | 624 void InactiveToActive(LiveRange* range); |
527 | 625 |
528 // Helper methods for allocating registers. | 626 // Helper methods for allocating registers. |
529 bool TryReuseSpillForPhi(LiveRange* range); | 627 bool TryReuseSpillForPhi(LiveRange* range); |
530 bool TryAllocateFreeReg(LiveRange* range); | 628 bool TryAllocateFreeReg(LiveRange* range); |
531 void AllocateBlockedReg(LiveRange* range); | 629 void AllocateBlockedReg(LiveRange* range); |
532 SpillRange* AssignSpillRangeToLiveRange(LiveRange* range); | |
533 | 630 |
534 // Live range splitting helpers. | 631 // Live range splitting helpers. |
535 | 632 |
536 // Split the given range at the given position. | 633 // Split the given range at the given position. |
537 // If range starts at or after the given position then the | 634 // If range starts at or after the given position then the |
538 // original range is returned. | 635 // original range is returned. |
539 // Otherwise returns the live range that starts at pos and contains | 636 // Otherwise returns the live range that starts at pos and contains |
540 // all uses from the original range that follow pos. Uses at pos will | 637 // all uses from the original range that follow pos. Uses at pos will |
541 // still be owned by the original range after splitting. | 638 // still be owned by the original range after splitting. |
542 LiveRange* SplitRangeAt(LiveRange* range, LifetimePosition pos); | 639 LiveRange* SplitRangeAt(LiveRange* range, LifetimePosition pos); |
(...skipping 21 matching lines...) Expand all Loading... |
564 LifetimePosition until, LifetimePosition end); | 661 LifetimePosition until, LifetimePosition end); |
565 | 662 |
566 void SplitAndSpillIntersecting(LiveRange* range); | 663 void SplitAndSpillIntersecting(LiveRange* range); |
567 | 664 |
568 // If we are trying to spill a range inside the loop try to | 665 // If we are trying to spill a range inside the loop try to |
569 // hoist spill position out to the point just before the loop. | 666 // hoist spill position out to the point just before the loop. |
570 LifetimePosition FindOptimalSpillingPos(LiveRange* range, | 667 LifetimePosition FindOptimalSpillingPos(LiveRange* range, |
571 LifetimePosition pos); | 668 LifetimePosition pos); |
572 | 669 |
573 void Spill(LiveRange* range); | 670 void Spill(LiveRange* range); |
574 bool IsBlockBoundary(LifetimePosition pos); | |
575 | |
576 // Helper methods for resolving control flow. | |
577 void ResolveControlFlow(const InstructionBlock* block, | |
578 const InstructionOperand& cur_op, | |
579 const InstructionBlock* pred, | |
580 const InstructionOperand& pred_op); | |
581 | |
582 void SetLiveRangeAssignedRegister(LiveRange* range, int reg); | |
583 | 671 |
584 // Return the block which contains give lifetime position. | 672 // Return the block which contains give lifetime position. |
585 const InstructionBlock* GetInstructionBlock(LifetimePosition pos); | 673 const InstructionBlock* GetInstructionBlock(LifetimePosition pos) const { |
| 674 return data()->GetInstructionBlock(pos); |
| 675 } |
| 676 |
| 677 void SetLiveRangeAssignedRegister(LiveRange* range, int reg) { |
| 678 data()->SetLiveRangeAssignedRegister(range, reg); |
| 679 } |
586 | 680 |
587 // Helper methods for the fixed registers. | 681 // Helper methods for the fixed registers. |
588 int RegisterCount() const; | 682 int RegisterCount() const { return num_registers_; } |
589 static int FixedLiveRangeID(int index) { return -index - 1; } | |
590 int FixedDoubleLiveRangeID(int index); | |
591 LiveRange* FixedLiveRangeFor(int index); | |
592 LiveRange* FixedDoubleLiveRangeFor(int index); | |
593 LiveRange* LiveRangeFor(int index); | |
594 Instruction* GetLastInstruction(const InstructionBlock* block); | |
595 | |
596 const char* RegisterName(int allocation_index); | 683 const char* RegisterName(int allocation_index); |
597 | 684 |
598 Instruction* InstructionAt(int index) { return code()->InstructionAt(index); } | 685 ZoneVector<LiveRange*>& live_ranges() { return data()->live_ranges(); } |
599 void AssignPhiInput(LiveRange* range, const InstructionOperand& assignment); | 686 ZoneVector<LiveRange*>& fixed_live_ranges() { |
600 | 687 return data()->fixed_live_ranges(); |
601 Frame* frame() const { return frame_; } | 688 } |
602 const char* debug_name() const { return debug_name_; } | |
603 const RegisterConfiguration* config() const { return config_; } | |
604 ZoneVector<LiveRange*>& live_ranges() { return live_ranges_; } | |
605 ZoneVector<LiveRange*>& fixed_live_ranges() { return fixed_live_ranges_; } | |
606 ZoneVector<LiveRange*>& fixed_double_live_ranges() { | 689 ZoneVector<LiveRange*>& fixed_double_live_ranges() { |
607 return fixed_double_live_ranges_; | 690 return data()->fixed_double_live_ranges(); |
608 } | 691 } |
609 ZoneVector<LiveRange*>& unhandled_live_ranges() { | 692 ZoneVector<LiveRange*>& unhandled_live_ranges() { |
610 return unhandled_live_ranges_; | 693 return unhandled_live_ranges_; |
611 } | 694 } |
612 ZoneVector<LiveRange*>& active_live_ranges() { return active_live_ranges_; } | 695 ZoneVector<LiveRange*>& active_live_ranges() { return active_live_ranges_; } |
613 ZoneVector<LiveRange*>& inactive_live_ranges() { | 696 ZoneVector<LiveRange*>& inactive_live_ranges() { |
614 return inactive_live_ranges_; | 697 return inactive_live_ranges_; |
615 } | 698 } |
616 ZoneVector<SpillRange*>& spill_ranges() { return spill_ranges_; } | 699 ZoneVector<SpillRange*>& spill_ranges() { return data()->spill_ranges(); } |
| 700 RegisterAllocationData::PhiMap& phi_map() { return data()->phi_map(); } |
617 | 701 |
618 class PhiMapValue : public ZoneObject { | 702 RegisterAllocationData* const data_; |
619 public: | 703 const RegisterKind mode_; |
620 PhiMapValue(PhiInstruction* phi, const InstructionBlock* block, Zone* zone) | 704 const int num_registers_; |
621 : phi(phi), block(block), incoming_moves(zone) { | |
622 incoming_moves.reserve(phi->operands().size()); | |
623 } | |
624 PhiInstruction* const phi; | |
625 const InstructionBlock* const block; | |
626 ZoneVector<MoveOperands*> incoming_moves; | |
627 }; | |
628 typedef ZoneMap<int, PhiMapValue*> PhiMap; | |
629 | 705 |
630 Zone* const local_zone_; | |
631 Frame* const frame_; | |
632 InstructionSequence* const code_; | |
633 const char* const debug_name_; | |
634 | |
635 const RegisterConfiguration* config_; | |
636 PhiMap phi_map_; | |
637 | |
638 // During liveness analysis keep a mapping from block id to live_in sets | |
639 // for blocks already analyzed. | |
640 ZoneVector<BitVector*> live_in_sets_; | |
641 | |
642 // Liveness analysis results. | |
643 ZoneVector<LiveRange*> live_ranges_; | |
644 | |
645 // Lists of live ranges | |
646 ZoneVector<LiveRange*> fixed_live_ranges_; | |
647 ZoneVector<LiveRange*> fixed_double_live_ranges_; | |
648 ZoneVector<LiveRange*> unhandled_live_ranges_; | 706 ZoneVector<LiveRange*> unhandled_live_ranges_; |
649 ZoneVector<LiveRange*> active_live_ranges_; | 707 ZoneVector<LiveRange*> active_live_ranges_; |
650 ZoneVector<LiveRange*> inactive_live_ranges_; | 708 ZoneVector<LiveRange*> inactive_live_ranges_; |
651 ZoneVector<SpillRange*> spill_ranges_; | |
652 | |
653 RegisterKind mode_; | |
654 int num_registers_; | |
655 | |
656 BitVector* assigned_registers_; | |
657 BitVector* assigned_double_registers_; | |
658 | 709 |
659 #ifdef DEBUG | 710 #ifdef DEBUG |
660 LifetimePosition allocation_finger_; | 711 LifetimePosition allocation_finger_; |
661 #endif | 712 #endif |
662 | 713 |
663 DISALLOW_COPY_AND_ASSIGN(RegisterAllocator); | 714 DISALLOW_COPY_AND_ASSIGN(LinearScanAllocator); |
| 715 }; |
| 716 |
| 717 |
| 718 class OperandAssigner final : public ZoneObject { |
| 719 public: |
| 720 explicit OperandAssigner(RegisterAllocationData* data); |
| 721 |
| 722 // Phase 5: assign spill splots. |
| 723 void AssignSpillSlots(); |
| 724 |
| 725 // Phase 6: commit assignment. |
| 726 void CommitAssignment(); |
| 727 |
| 728 private: |
| 729 RegisterAllocationData* data() const { return data_; } |
| 730 |
| 731 RegisterAllocationData* const data_; |
| 732 |
| 733 DISALLOW_COPY_AND_ASSIGN(OperandAssigner); |
| 734 }; |
| 735 |
| 736 |
| 737 class ReferenceMapPopulator final : public ZoneObject { |
| 738 public: |
| 739 explicit ReferenceMapPopulator(RegisterAllocationData* data); |
| 740 |
| 741 // Phase 7: compute values for pointer maps. |
| 742 void PopulateReferenceMaps(); |
| 743 |
| 744 private: |
| 745 bool SafePointsAreInOrder() const; |
| 746 |
| 747 bool IsReference(int virtual_register) const { |
| 748 return data()->IsReference(virtual_register); |
| 749 } |
| 750 |
| 751 RegisterAllocationData* data() const { return data_; } |
| 752 |
| 753 RegisterAllocationData* const data_; |
| 754 |
| 755 DISALLOW_COPY_AND_ASSIGN(ReferenceMapPopulator); |
| 756 }; |
| 757 |
| 758 |
| 759 class LiveRangeConnector final : public ZoneObject { |
| 760 public: |
| 761 explicit LiveRangeConnector(RegisterAllocationData* data); |
| 762 |
| 763 // Phase 8: reconnect split ranges with moves. |
| 764 void ConnectRanges(Zone* temp_zone); |
| 765 |
| 766 // Phase 9: insert moves to connect ranges across basic blocks. |
| 767 void ResolveControlFlow(); |
| 768 |
| 769 private: |
| 770 const InstructionBlock* GetInstructionBlock(LifetimePosition pos) const { |
| 771 return data()->GetInstructionBlock(pos); |
| 772 } |
| 773 bool CanEagerlyResolveControlFlow(const InstructionBlock* block) const; |
| 774 void ResolveControlFlow(const InstructionBlock* block, |
| 775 const InstructionOperand& cur_op, |
| 776 const InstructionBlock* pred, |
| 777 const InstructionOperand& pred_op); |
| 778 InstructionSequence* code() const { return data()->code(); } |
| 779 Zone* code_zone() const { return code()->zone(); } |
| 780 RegisterAllocationData* data() const { return data_; } |
| 781 |
| 782 RegisterAllocationData* const data_; |
| 783 |
| 784 DISALLOW_COPY_AND_ASSIGN(LiveRangeConnector); |
664 }; | 785 }; |
665 | 786 |
666 } // namespace compiler | 787 } // namespace compiler |
667 } // namespace internal | 788 } // namespace internal |
668 } // namespace v8 | 789 } // namespace v8 |
669 | 790 |
670 #endif // V8_REGISTER_ALLOCATOR_H_ | 791 #endif // V8_REGISTER_ALLOCATOR_H_ |
OLD | NEW |