OLD | NEW |
1 // Copyright 2012 the V8 project authors. All rights reserved. | 1 // Copyright 2012 the V8 project authors. All rights reserved. |
2 // Redistribution and use in source and binary forms, with or without | 2 // Redistribution and use in source and binary forms, with or without |
3 // modification, are permitted provided that the following conditions are | 3 // modification, are permitted provided that the following conditions are |
4 // met: | 4 // met: |
5 // | 5 // |
6 // * Redistributions of source code must retain the above copyright | 6 // * Redistributions of source code must retain the above copyright |
7 // notice, this list of conditions and the following disclaimer. | 7 // notice, this list of conditions and the following disclaimer. |
8 // * Redistributions in binary form must reproduce the above | 8 // * Redistributions in binary form must reproduce the above |
9 // copyright notice, this list of conditions and the following | 9 // copyright notice, this list of conditions and the following |
10 // disclaimer in the documentation and/or other materials provided | 10 // disclaimer in the documentation and/or other materials provided |
(...skipping 525 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
536 AdvanceLastProcessedMarker(a, advance_last_processed_up_to); | 536 AdvanceLastProcessedMarker(a, advance_last_processed_up_to); |
537 } else { | 537 } else { |
538 b = b->next(); | 538 b = b->next(); |
539 } | 539 } |
540 } | 540 } |
541 return LifetimePosition::Invalid(); | 541 return LifetimePosition::Invalid(); |
542 } | 542 } |
543 | 543 |
544 | 544 |
545 LAllocator::LAllocator(int num_values, HGraph* graph) | 545 LAllocator::LAllocator(int num_values, HGraph* graph) |
546 : zone_(graph->zone()), | 546 : zone_(graph->isolate()), |
547 chunk_(NULL), | 547 chunk_(NULL), |
548 live_in_sets_(graph->blocks()->length(), zone_), | 548 live_in_sets_(graph->blocks()->length(), zone()), |
549 live_ranges_(num_values * 2, zone_), | 549 live_ranges_(num_values * 2, zone()), |
550 fixed_live_ranges_(NULL), | 550 fixed_live_ranges_(NULL), |
551 fixed_double_live_ranges_(NULL), | 551 fixed_double_live_ranges_(NULL), |
552 unhandled_live_ranges_(num_values * 2, zone_), | 552 unhandled_live_ranges_(num_values * 2, zone()), |
553 active_live_ranges_(8, zone_), | 553 active_live_ranges_(8, zone()), |
554 inactive_live_ranges_(8, zone_), | 554 inactive_live_ranges_(8, zone()), |
555 reusable_slots_(8, zone_), | 555 reusable_slots_(8, zone()), |
556 next_virtual_register_(num_values), | 556 next_virtual_register_(num_values), |
557 first_artificial_register_(num_values), | 557 first_artificial_register_(num_values), |
558 mode_(GENERAL_REGISTERS), | 558 mode_(GENERAL_REGISTERS), |
559 num_registers_(-1), | 559 num_registers_(-1), |
560 graph_(graph), | 560 graph_(graph), |
561 has_osr_entry_(false), | 561 has_osr_entry_(false), |
562 allocation_ok_(true) { } | 562 allocation_ok_(true) { } |
563 | 563 |
564 | 564 |
565 void LAllocator::InitializeLivenessAnalysis() { | 565 void LAllocator::InitializeLivenessAnalysis() { |
566 // Initialize the live_in sets for each block to NULL. | 566 // Initialize the live_in sets for each block to NULL. |
567 int block_count = graph_->blocks()->length(); | 567 int block_count = graph_->blocks()->length(); |
568 live_in_sets_.Initialize(block_count, zone()); | 568 live_in_sets_.Initialize(block_count, zone()); |
569 live_in_sets_.AddBlock(NULL, block_count, zone()); | 569 live_in_sets_.AddBlock(NULL, block_count, zone()); |
570 } | 570 } |
571 | 571 |
572 | 572 |
573 BitVector* LAllocator::ComputeLiveOut(HBasicBlock* block) { | 573 BitVector* LAllocator::ComputeLiveOut(HBasicBlock* block) { |
574 // Compute live out for the given block, except not including backward | 574 // Compute live out for the given block, except not including backward |
575 // successor edges. | 575 // successor edges. |
576 BitVector* live_out = new(zone_) BitVector(next_virtual_register_, zone_); | 576 BitVector* live_out = new(zone()) BitVector(next_virtual_register_, zone()); |
577 | 577 |
578 // Process all successor blocks. | 578 // Process all successor blocks. |
579 for (HSuccessorIterator it(block->end()); !it.Done(); it.Advance()) { | 579 for (HSuccessorIterator it(block->end()); !it.Done(); it.Advance()) { |
580 // Add values live on entry to the successor. Note the successor's | 580 // Add values live on entry to the successor. Note the successor's |
581 // live_in will not be computed yet for backwards edges. | 581 // live_in will not be computed yet for backwards edges. |
582 HBasicBlock* successor = it.Current(); | 582 HBasicBlock* successor = it.Current(); |
583 BitVector* live_in = live_in_sets_[successor->block_id()]; | 583 BitVector* live_in = live_in_sets_[successor->block_id()]; |
584 if (live_in != NULL) live_out->Union(*live_in); | 584 if (live_in != NULL) live_out->Union(*live_in); |
585 | 585 |
586 // All phi input operands corresponding to this successor edge are live | 586 // All phi input operands corresponding to this successor edge are live |
(...skipping 17 matching lines...) Expand all Loading... |
604 // Add an interval that includes the entire block to the live range for | 604 // Add an interval that includes the entire block to the live range for |
605 // each live_out value. | 605 // each live_out value. |
606 LifetimePosition start = LifetimePosition::FromInstructionIndex( | 606 LifetimePosition start = LifetimePosition::FromInstructionIndex( |
607 block->first_instruction_index()); | 607 block->first_instruction_index()); |
608 LifetimePosition end = LifetimePosition::FromInstructionIndex( | 608 LifetimePosition end = LifetimePosition::FromInstructionIndex( |
609 block->last_instruction_index()).NextInstruction(); | 609 block->last_instruction_index()).NextInstruction(); |
610 BitVector::Iterator iterator(live_out); | 610 BitVector::Iterator iterator(live_out); |
611 while (!iterator.Done()) { | 611 while (!iterator.Done()) { |
612 int operand_index = iterator.Current(); | 612 int operand_index = iterator.Current(); |
613 LiveRange* range = LiveRangeFor(operand_index); | 613 LiveRange* range = LiveRangeFor(operand_index); |
614 range->AddUseInterval(start, end, zone_); | 614 range->AddUseInterval(start, end, zone()); |
615 iterator.Advance(); | 615 iterator.Advance(); |
616 } | 616 } |
617 } | 617 } |
618 | 618 |
619 | 619 |
620 int LAllocator::FixedDoubleLiveRangeID(int index) { | 620 int LAllocator::FixedDoubleLiveRangeID(int index) { |
621 return -index - 1 - Register::kMaxNumAllocatableRegisters; | 621 return -index - 1 - Register::kMaxNumAllocatableRegisters; |
622 } | 622 } |
623 | 623 |
624 | 624 |
(...skipping 10 matching lines...) Expand all Loading... |
635 } else if (operand->HasFixedDoubleRegisterPolicy()) { | 635 } else if (operand->HasFixedDoubleRegisterPolicy()) { |
636 int reg_index = operand->fixed_register_index(); | 636 int reg_index = operand->fixed_register_index(); |
637 operand->ConvertTo(LOperand::DOUBLE_REGISTER, reg_index); | 637 operand->ConvertTo(LOperand::DOUBLE_REGISTER, reg_index); |
638 } else { | 638 } else { |
639 UNREACHABLE(); | 639 UNREACHABLE(); |
640 } | 640 } |
641 if (is_tagged) { | 641 if (is_tagged) { |
642 TraceAlloc("Fixed reg is tagged at %d\n", pos); | 642 TraceAlloc("Fixed reg is tagged at %d\n", pos); |
643 LInstruction* instr = InstructionAt(pos); | 643 LInstruction* instr = InstructionAt(pos); |
644 if (instr->HasPointerMap()) { | 644 if (instr->HasPointerMap()) { |
645 instr->pointer_map()->RecordPointer(operand, zone()); | 645 instr->pointer_map()->RecordPointer(operand, chunk()->zone()); |
646 } | 646 } |
647 } | 647 } |
648 return operand; | 648 return operand; |
649 } | 649 } |
650 | 650 |
651 | 651 |
652 LiveRange* LAllocator::FixedLiveRangeFor(int index) { | 652 LiveRange* LAllocator::FixedLiveRangeFor(int index) { |
653 ASSERT(index < Register::kMaxNumAllocatableRegisters); | 653 ASSERT(index < Register::kMaxNumAllocatableRegisters); |
654 LiveRange* result = fixed_live_ranges_[index]; | 654 LiveRange* result = fixed_live_ranges_[index]; |
655 if (result == NULL) { | 655 if (result == NULL) { |
656 result = new(zone_) LiveRange(FixedLiveRangeID(index), zone_); | 656 result = new(zone()) LiveRange(FixedLiveRangeID(index), chunk()->zone()); |
657 ASSERT(result->IsFixed()); | 657 ASSERT(result->IsFixed()); |
658 SetLiveRangeAssignedRegister(result, index, GENERAL_REGISTERS, zone_); | 658 SetLiveRangeAssignedRegister(result, index, GENERAL_REGISTERS); |
659 fixed_live_ranges_[index] = result; | 659 fixed_live_ranges_[index] = result; |
660 } | 660 } |
661 return result; | 661 return result; |
662 } | 662 } |
663 | 663 |
664 | 664 |
665 LiveRange* LAllocator::FixedDoubleLiveRangeFor(int index) { | 665 LiveRange* LAllocator::FixedDoubleLiveRangeFor(int index) { |
666 ASSERT(index < DoubleRegister::NumAllocatableRegisters()); | 666 ASSERT(index < DoubleRegister::NumAllocatableRegisters()); |
667 LiveRange* result = fixed_double_live_ranges_[index]; | 667 LiveRange* result = fixed_double_live_ranges_[index]; |
668 if (result == NULL) { | 668 if (result == NULL) { |
669 result = new(zone_) LiveRange(FixedDoubleLiveRangeID(index), zone_); | 669 result = new(zone()) LiveRange(FixedDoubleLiveRangeID(index), |
| 670 chunk()->zone()); |
670 ASSERT(result->IsFixed()); | 671 ASSERT(result->IsFixed()); |
671 SetLiveRangeAssignedRegister(result, index, DOUBLE_REGISTERS, zone_); | 672 SetLiveRangeAssignedRegister(result, index, DOUBLE_REGISTERS); |
672 fixed_double_live_ranges_[index] = result; | 673 fixed_double_live_ranges_[index] = result; |
673 } | 674 } |
674 return result; | 675 return result; |
675 } | 676 } |
676 | 677 |
677 | 678 |
678 LiveRange* LAllocator::LiveRangeFor(int index) { | 679 LiveRange* LAllocator::LiveRangeFor(int index) { |
679 if (index >= live_ranges_.length()) { | 680 if (index >= live_ranges_.length()) { |
680 live_ranges_.AddBlock(NULL, index - live_ranges_.length() + 1, zone()); | 681 live_ranges_.AddBlock(NULL, index - live_ranges_.length() + 1, zone()); |
681 } | 682 } |
682 LiveRange* result = live_ranges_[index]; | 683 LiveRange* result = live_ranges_[index]; |
683 if (result == NULL) { | 684 if (result == NULL) { |
684 result = new(zone_) LiveRange(index, zone_); | 685 result = new(zone()) LiveRange(index, chunk()->zone()); |
685 live_ranges_[index] = result; | 686 live_ranges_[index] = result; |
686 } | 687 } |
687 return result; | 688 return result; |
688 } | 689 } |
689 | 690 |
690 | 691 |
691 LGap* LAllocator::GetLastGap(HBasicBlock* block) { | 692 LGap* LAllocator::GetLastGap(HBasicBlock* block) { |
692 int last_instruction = block->last_instruction_index(); | 693 int last_instruction = block->last_instruction_index(); |
693 int index = chunk_->NearestGapPos(last_instruction); | 694 int index = chunk_->NearestGapPos(last_instruction); |
694 return GapAt(index); | 695 return GapAt(index); |
(...skipping 25 matching lines...) Expand all Loading... |
720 | 721 |
721 | 722 |
722 void LAllocator::Define(LifetimePosition position, | 723 void LAllocator::Define(LifetimePosition position, |
723 LOperand* operand, | 724 LOperand* operand, |
724 LOperand* hint) { | 725 LOperand* hint) { |
725 LiveRange* range = LiveRangeFor(operand); | 726 LiveRange* range = LiveRangeFor(operand); |
726 if (range == NULL) return; | 727 if (range == NULL) return; |
727 | 728 |
728 if (range->IsEmpty() || range->Start().Value() > position.Value()) { | 729 if (range->IsEmpty() || range->Start().Value() > position.Value()) { |
729 // Can happen if there is a definition without use. | 730 // Can happen if there is a definition without use. |
730 range->AddUseInterval(position, position.NextInstruction(), zone_); | 731 range->AddUseInterval(position, position.NextInstruction(), zone()); |
731 range->AddUsePosition(position.NextInstruction(), NULL, NULL, zone_); | 732 range->AddUsePosition(position.NextInstruction(), NULL, NULL, zone()); |
732 } else { | 733 } else { |
733 range->ShortenTo(position); | 734 range->ShortenTo(position); |
734 } | 735 } |
735 | 736 |
736 if (operand->IsUnallocated()) { | 737 if (operand->IsUnallocated()) { |
737 LUnallocated* unalloc_operand = LUnallocated::cast(operand); | 738 LUnallocated* unalloc_operand = LUnallocated::cast(operand); |
738 range->AddUsePosition(position, unalloc_operand, hint, zone_); | 739 range->AddUsePosition(position, unalloc_operand, hint, zone()); |
739 } | 740 } |
740 } | 741 } |
741 | 742 |
742 | 743 |
743 void LAllocator::Use(LifetimePosition block_start, | 744 void LAllocator::Use(LifetimePosition block_start, |
744 LifetimePosition position, | 745 LifetimePosition position, |
745 LOperand* operand, | 746 LOperand* operand, |
746 LOperand* hint) { | 747 LOperand* hint) { |
747 LiveRange* range = LiveRangeFor(operand); | 748 LiveRange* range = LiveRangeFor(operand); |
748 if (range == NULL) return; | 749 if (range == NULL) return; |
749 if (operand->IsUnallocated()) { | 750 if (operand->IsUnallocated()) { |
750 LUnallocated* unalloc_operand = LUnallocated::cast(operand); | 751 LUnallocated* unalloc_operand = LUnallocated::cast(operand); |
751 range->AddUsePosition(position, unalloc_operand, hint, zone_); | 752 range->AddUsePosition(position, unalloc_operand, hint, zone()); |
752 } | 753 } |
753 range->AddUseInterval(block_start, position, zone_); | 754 range->AddUseInterval(block_start, position, zone()); |
754 } | 755 } |
755 | 756 |
756 | 757 |
757 void LAllocator::AddConstraintsGapMove(int index, | 758 void LAllocator::AddConstraintsGapMove(int index, |
758 LOperand* from, | 759 LOperand* from, |
759 LOperand* to) { | 760 LOperand* to) { |
760 LGap* gap = GapAt(index); | 761 LGap* gap = GapAt(index); |
761 LParallelMove* move = gap->GetOrCreateParallelMove(LGap::START, zone()); | 762 LParallelMove* move = gap->GetOrCreateParallelMove(LGap::START, |
| 763 chunk()->zone()); |
762 if (from->IsUnallocated()) { | 764 if (from->IsUnallocated()) { |
763 const ZoneList<LMoveOperands>* move_operands = move->move_operands(); | 765 const ZoneList<LMoveOperands>* move_operands = move->move_operands(); |
764 for (int i = 0; i < move_operands->length(); ++i) { | 766 for (int i = 0; i < move_operands->length(); ++i) { |
765 LMoveOperands cur = move_operands->at(i); | 767 LMoveOperands cur = move_operands->at(i); |
766 LOperand* cur_to = cur.destination(); | 768 LOperand* cur_to = cur.destination(); |
767 if (cur_to->IsUnallocated()) { | 769 if (cur_to->IsUnallocated()) { |
768 if (LUnallocated::cast(cur_to)->virtual_register() == | 770 if (LUnallocated::cast(cur_to)->virtual_register() == |
769 LUnallocated::cast(from)->virtual_register()) { | 771 LUnallocated::cast(from)->virtual_register()) { |
770 move->AddMove(cur.source(), to, zone()); | 772 move->AddMove(cur.source(), to, chunk()->zone()); |
771 return; | 773 return; |
772 } | 774 } |
773 } | 775 } |
774 } | 776 } |
775 } | 777 } |
776 move->AddMove(from, to, zone()); | 778 move->AddMove(from, to, chunk()->zone()); |
777 } | 779 } |
778 | 780 |
779 | 781 |
780 void LAllocator::MeetRegisterConstraints(HBasicBlock* block) { | 782 void LAllocator::MeetRegisterConstraints(HBasicBlock* block) { |
781 int start = block->first_instruction_index(); | 783 int start = block->first_instruction_index(); |
782 int end = block->last_instruction_index(); | 784 int end = block->last_instruction_index(); |
783 if (start == -1) return; | 785 if (start == -1) return; |
784 for (int i = start; i <= end; ++i) { | 786 for (int i = start; i <= end; ++i) { |
785 if (IsGapAt(i)) { | 787 if (IsGapAt(i)) { |
786 LInstruction* instr = NULL; | 788 LInstruction* instr = NULL; |
(...skipping 19 matching lines...) Expand all Loading... |
806 } | 808 } |
807 } | 809 } |
808 } | 810 } |
809 | 811 |
810 // Handle fixed output operand. | 812 // Handle fixed output operand. |
811 if (first != NULL && first->Output() != NULL) { | 813 if (first != NULL && first->Output() != NULL) { |
812 LUnallocated* first_output = LUnallocated::cast(first->Output()); | 814 LUnallocated* first_output = LUnallocated::cast(first->Output()); |
813 LiveRange* range = LiveRangeFor(first_output->virtual_register()); | 815 LiveRange* range = LiveRangeFor(first_output->virtual_register()); |
814 bool assigned = false; | 816 bool assigned = false; |
815 if (first_output->HasFixedPolicy()) { | 817 if (first_output->HasFixedPolicy()) { |
816 LUnallocated* output_copy = first_output->CopyUnconstrained(zone()); | 818 LUnallocated* output_copy = first_output->CopyUnconstrained( |
| 819 chunk()->zone()); |
817 bool is_tagged = HasTaggedValue(first_output->virtual_register()); | 820 bool is_tagged = HasTaggedValue(first_output->virtual_register()); |
818 AllocateFixed(first_output, gap_index, is_tagged); | 821 AllocateFixed(first_output, gap_index, is_tagged); |
819 | 822 |
820 // This value is produced on the stack, we never need to spill it. | 823 // This value is produced on the stack, we never need to spill it. |
821 if (first_output->IsStackSlot()) { | 824 if (first_output->IsStackSlot()) { |
822 range->SetSpillOperand(first_output); | 825 range->SetSpillOperand(first_output); |
823 range->SetSpillStartIndex(gap_index - 1); | 826 range->SetSpillStartIndex(gap_index - 1); |
824 assigned = true; | 827 assigned = true; |
825 } | 828 } |
826 chunk_->AddGapMove(gap_index, first_output, output_copy); | 829 chunk_->AddGapMove(gap_index, first_output, output_copy); |
827 } | 830 } |
828 | 831 |
829 if (!assigned) { | 832 if (!assigned) { |
830 range->SetSpillStartIndex(gap_index); | 833 range->SetSpillStartIndex(gap_index); |
831 | 834 |
832 // This move to spill operand is not a real use. Liveness analysis | 835 // This move to spill operand is not a real use. Liveness analysis |
833 // and splitting of live ranges do not account for it. | 836 // and splitting of live ranges do not account for it. |
834 // Thus it should be inserted to a lifetime position corresponding to | 837 // Thus it should be inserted to a lifetime position corresponding to |
835 // the instruction end. | 838 // the instruction end. |
836 LGap* gap = GapAt(gap_index); | 839 LGap* gap = GapAt(gap_index); |
837 LParallelMove* move = gap->GetOrCreateParallelMove(LGap::BEFORE, zone()); | 840 LParallelMove* move = gap->GetOrCreateParallelMove(LGap::BEFORE, |
838 move->AddMove(first_output, range->GetSpillOperand(), zone()); | 841 chunk()->zone()); |
| 842 move->AddMove(first_output, range->GetSpillOperand(), |
| 843 chunk()->zone()); |
839 } | 844 } |
840 } | 845 } |
841 | 846 |
842 // Handle fixed input operands of second instruction. | 847 // Handle fixed input operands of second instruction. |
843 if (second != NULL) { | 848 if (second != NULL) { |
844 for (UseIterator it(second); !it.Done(); it.Advance()) { | 849 for (UseIterator it(second); !it.Done(); it.Advance()) { |
845 LUnallocated* cur_input = LUnallocated::cast(it.Current()); | 850 LUnallocated* cur_input = LUnallocated::cast(it.Current()); |
846 if (cur_input->HasFixedPolicy()) { | 851 if (cur_input->HasFixedPolicy()) { |
847 LUnallocated* input_copy = cur_input->CopyUnconstrained(zone()); | 852 LUnallocated* input_copy = cur_input->CopyUnconstrained( |
| 853 chunk()->zone()); |
848 bool is_tagged = HasTaggedValue(cur_input->virtual_register()); | 854 bool is_tagged = HasTaggedValue(cur_input->virtual_register()); |
849 AllocateFixed(cur_input, gap_index + 1, is_tagged); | 855 AllocateFixed(cur_input, gap_index + 1, is_tagged); |
850 AddConstraintsGapMove(gap_index, input_copy, cur_input); | 856 AddConstraintsGapMove(gap_index, input_copy, cur_input); |
851 } else if (cur_input->HasWritableRegisterPolicy()) { | 857 } else if (cur_input->HasWritableRegisterPolicy()) { |
852 // The live range of writable input registers always goes until the end | 858 // The live range of writable input registers always goes until the end |
853 // of the instruction. | 859 // of the instruction. |
854 ASSERT(!cur_input->IsUsedAtStart()); | 860 ASSERT(!cur_input->IsUsedAtStart()); |
855 | 861 |
856 LUnallocated* input_copy = cur_input->CopyUnconstrained(zone()); | 862 LUnallocated* input_copy = cur_input->CopyUnconstrained( |
| 863 chunk()->zone()); |
857 int vreg = GetVirtualRegister(); | 864 int vreg = GetVirtualRegister(); |
858 if (!AllocationOk()) return; | 865 if (!AllocationOk()) return; |
859 cur_input->set_virtual_register(vreg); | 866 cur_input->set_virtual_register(vreg); |
860 | 867 |
861 if (RequiredRegisterKind(input_copy->virtual_register()) == | 868 if (RequiredRegisterKind(input_copy->virtual_register()) == |
862 DOUBLE_REGISTERS) { | 869 DOUBLE_REGISTERS) { |
863 double_artificial_registers_.Add( | 870 double_artificial_registers_.Add( |
864 cur_input->virtual_register() - first_artificial_register_, | 871 cur_input->virtual_register() - first_artificial_register_, |
865 zone_); | 872 zone()); |
866 } | 873 } |
867 | 874 |
868 AddConstraintsGapMove(gap_index, input_copy, cur_input); | 875 AddConstraintsGapMove(gap_index, input_copy, cur_input); |
869 } | 876 } |
870 } | 877 } |
871 } | 878 } |
872 | 879 |
873 // Handle "output same as input" for second instruction. | 880 // Handle "output same as input" for second instruction. |
874 if (second != NULL && second->Output() != NULL) { | 881 if (second != NULL && second->Output() != NULL) { |
875 LUnallocated* second_output = LUnallocated::cast(second->Output()); | 882 LUnallocated* second_output = LUnallocated::cast(second->Output()); |
876 if (second_output->HasSameAsInputPolicy()) { | 883 if (second_output->HasSameAsInputPolicy()) { |
877 LUnallocated* cur_input = LUnallocated::cast(second->FirstInput()); | 884 LUnallocated* cur_input = LUnallocated::cast(second->FirstInput()); |
878 int output_vreg = second_output->virtual_register(); | 885 int output_vreg = second_output->virtual_register(); |
879 int input_vreg = cur_input->virtual_register(); | 886 int input_vreg = cur_input->virtual_register(); |
880 | 887 |
881 LUnallocated* input_copy = cur_input->CopyUnconstrained(zone()); | 888 LUnallocated* input_copy = cur_input->CopyUnconstrained( |
| 889 chunk()->zone()); |
882 cur_input->set_virtual_register(second_output->virtual_register()); | 890 cur_input->set_virtual_register(second_output->virtual_register()); |
883 AddConstraintsGapMove(gap_index, input_copy, cur_input); | 891 AddConstraintsGapMove(gap_index, input_copy, cur_input); |
884 | 892 |
885 if (HasTaggedValue(input_vreg) && !HasTaggedValue(output_vreg)) { | 893 if (HasTaggedValue(input_vreg) && !HasTaggedValue(output_vreg)) { |
886 int index = gap_index + 1; | 894 int index = gap_index + 1; |
887 LInstruction* instr = InstructionAt(index); | 895 LInstruction* instr = InstructionAt(index); |
888 if (instr->HasPointerMap()) { | 896 if (instr->HasPointerMap()) { |
889 instr->pointer_map()->RecordPointer(input_copy, zone()); | 897 instr->pointer_map()->RecordPointer(input_copy, chunk()->zone()); |
890 } | 898 } |
891 } else if (!HasTaggedValue(input_vreg) && HasTaggedValue(output_vreg)) { | 899 } else if (!HasTaggedValue(input_vreg) && HasTaggedValue(output_vreg)) { |
892 // The input is assumed to immediately have a tagged representation, | 900 // The input is assumed to immediately have a tagged representation, |
893 // before the pointer map can be used. I.e. the pointer map at the | 901 // before the pointer map can be used. I.e. the pointer map at the |
894 // instruction will include the output operand (whose value at the | 902 // instruction will include the output operand (whose value at the |
895 // beginning of the instruction is equal to the input operand). If | 903 // beginning of the instruction is equal to the input operand). If |
896 // this is not desired, then the pointer map at this instruction needs | 904 // this is not desired, then the pointer map at this instruction needs |
897 // to be adjusted manually. | 905 // to be adjusted manually. |
898 } | 906 } |
899 } | 907 } |
900 } | 908 } |
901 } | 909 } |
902 | 910 |
903 | 911 |
904 void LAllocator::ProcessInstructions(HBasicBlock* block, BitVector* live) { | 912 void LAllocator::ProcessInstructions(HBasicBlock* block, BitVector* live) { |
905 int block_start = block->first_instruction_index(); | 913 int block_start = block->first_instruction_index(); |
906 int index = block->last_instruction_index(); | 914 int index = block->last_instruction_index(); |
907 | 915 |
908 LifetimePosition block_start_position = | 916 LifetimePosition block_start_position = |
909 LifetimePosition::FromInstructionIndex(block_start); | 917 LifetimePosition::FromInstructionIndex(block_start); |
910 | 918 |
911 while (index >= block_start) { | 919 while (index >= block_start) { |
912 LifetimePosition curr_position = | 920 LifetimePosition curr_position = |
913 LifetimePosition::FromInstructionIndex(index); | 921 LifetimePosition::FromInstructionIndex(index); |
914 | 922 |
915 if (IsGapAt(index)) { | 923 if (IsGapAt(index)) { |
916 // We have a gap at this position. | 924 // We have a gap at this position. |
917 LGap* gap = GapAt(index); | 925 LGap* gap = GapAt(index); |
918 LParallelMove* move = gap->GetOrCreateParallelMove(LGap::START, zone()); | 926 LParallelMove* move = gap->GetOrCreateParallelMove(LGap::START, |
| 927 chunk()->zone()); |
919 const ZoneList<LMoveOperands>* move_operands = move->move_operands(); | 928 const ZoneList<LMoveOperands>* move_operands = move->move_operands(); |
920 for (int i = 0; i < move_operands->length(); ++i) { | 929 for (int i = 0; i < move_operands->length(); ++i) { |
921 LMoveOperands* cur = &move_operands->at(i); | 930 LMoveOperands* cur = &move_operands->at(i); |
922 if (cur->IsIgnored()) continue; | 931 if (cur->IsIgnored()) continue; |
923 LOperand* from = cur->source(); | 932 LOperand* from = cur->source(); |
924 LOperand* to = cur->destination(); | 933 LOperand* to = cur->destination(); |
925 HPhi* phi = LookupPhi(to); | 934 HPhi* phi = LookupPhi(to); |
926 LOperand* hint = to; | 935 LOperand* hint = to; |
927 if (phi != NULL) { | 936 if (phi != NULL) { |
928 // This is a phi resolving move. | 937 // This is a phi resolving move. |
(...skipping 31 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
960 Define(curr_position, output, NULL); | 969 Define(curr_position, output, NULL); |
961 } | 970 } |
962 | 971 |
963 if (instr->ClobbersRegisters()) { | 972 if (instr->ClobbersRegisters()) { |
964 for (int i = 0; i < Register::kMaxNumAllocatableRegisters; ++i) { | 973 for (int i = 0; i < Register::kMaxNumAllocatableRegisters; ++i) { |
965 if (output == NULL || !output->IsRegister() || | 974 if (output == NULL || !output->IsRegister() || |
966 output->index() != i) { | 975 output->index() != i) { |
967 LiveRange* range = FixedLiveRangeFor(i); | 976 LiveRange* range = FixedLiveRangeFor(i); |
968 range->AddUseInterval(curr_position, | 977 range->AddUseInterval(curr_position, |
969 curr_position.InstructionEnd(), | 978 curr_position.InstructionEnd(), |
970 zone_); | 979 zone()); |
971 } | 980 } |
972 } | 981 } |
973 } | 982 } |
974 | 983 |
975 if (instr->ClobbersDoubleRegisters()) { | 984 if (instr->ClobbersDoubleRegisters()) { |
976 for (int i = 0; i < DoubleRegister::NumAllocatableRegisters(); ++i) { | 985 for (int i = 0; i < DoubleRegister::NumAllocatableRegisters(); ++i) { |
977 if (output == NULL || !output->IsDoubleRegister() || | 986 if (output == NULL || !output->IsDoubleRegister() || |
978 output->index() != i) { | 987 output->index() != i) { |
979 LiveRange* range = FixedDoubleLiveRangeFor(i); | 988 LiveRange* range = FixedDoubleLiveRangeFor(i); |
980 range->AddUseInterval(curr_position, | 989 range->AddUseInterval(curr_position, |
981 curr_position.InstructionEnd(), | 990 curr_position.InstructionEnd(), |
982 zone_); | 991 zone()); |
983 } | 992 } |
984 } | 993 } |
985 } | 994 } |
986 | 995 |
987 for (UseIterator it(instr); !it.Done(); it.Advance()) { | 996 for (UseIterator it(instr); !it.Done(); it.Advance()) { |
988 LOperand* input = it.Current(); | 997 LOperand* input = it.Current(); |
989 | 998 |
990 LifetimePosition use_pos; | 999 LifetimePosition use_pos; |
991 if (input->IsUnallocated() && | 1000 if (input->IsUnallocated() && |
992 LUnallocated::cast(input)->IsUsedAtStart()) { | 1001 LUnallocated::cast(input)->IsUsedAtStart()) { |
(...skipping 27 matching lines...) Expand all Loading... |
1020 | 1029 |
1021 index = index - 1; | 1030 index = index - 1; |
1022 } | 1031 } |
1023 } | 1032 } |
1024 | 1033 |
1025 | 1034 |
1026 void LAllocator::ResolvePhis(HBasicBlock* block) { | 1035 void LAllocator::ResolvePhis(HBasicBlock* block) { |
1027 const ZoneList<HPhi*>* phis = block->phis(); | 1036 const ZoneList<HPhi*>* phis = block->phis(); |
1028 for (int i = 0; i < phis->length(); ++i) { | 1037 for (int i = 0; i < phis->length(); ++i) { |
1029 HPhi* phi = phis->at(i); | 1038 HPhi* phi = phis->at(i); |
1030 LUnallocated* phi_operand = new(zone_) LUnallocated(LUnallocated::NONE); | 1039 LUnallocated* phi_operand = |
| 1040 new(chunk()->zone()) LUnallocated(LUnallocated::NONE); |
1031 phi_operand->set_virtual_register(phi->id()); | 1041 phi_operand->set_virtual_register(phi->id()); |
1032 for (int j = 0; j < phi->OperandCount(); ++j) { | 1042 for (int j = 0; j < phi->OperandCount(); ++j) { |
1033 HValue* op = phi->OperandAt(j); | 1043 HValue* op = phi->OperandAt(j); |
1034 LOperand* operand = NULL; | 1044 LOperand* operand = NULL; |
1035 if (op->IsConstant() && op->EmitAtUses()) { | 1045 if (op->IsConstant() && op->EmitAtUses()) { |
1036 HConstant* constant = HConstant::cast(op); | 1046 HConstant* constant = HConstant::cast(op); |
1037 operand = chunk_->DefineConstantOperand(constant); | 1047 operand = chunk_->DefineConstantOperand(constant); |
1038 } else { | 1048 } else { |
1039 ASSERT(!op->EmitAtUses()); | 1049 ASSERT(!op->EmitAtUses()); |
1040 LUnallocated* unalloc = new(zone_) LUnallocated(LUnallocated::ANY); | 1050 LUnallocated* unalloc = |
| 1051 new(chunk()->zone()) LUnallocated(LUnallocated::ANY); |
1041 unalloc->set_virtual_register(op->id()); | 1052 unalloc->set_virtual_register(op->id()); |
1042 operand = unalloc; | 1053 operand = unalloc; |
1043 } | 1054 } |
1044 HBasicBlock* cur_block = block->predecessors()->at(j); | 1055 HBasicBlock* cur_block = block->predecessors()->at(j); |
1045 // The gap move must be added without any special processing as in | 1056 // The gap move must be added without any special processing as in |
1046 // the AddConstraintsGapMove. | 1057 // the AddConstraintsGapMove. |
1047 chunk_->AddGapMove(cur_block->last_instruction_index() - 1, | 1058 chunk_->AddGapMove(cur_block->last_instruction_index() - 1, |
1048 operand, | 1059 operand, |
1049 phi_operand); | 1060 phi_operand); |
1050 | 1061 |
1051 // We are going to insert a move before the branch instruction. | 1062 // We are going to insert a move before the branch instruction. |
1052 // Some branch instructions (e.g. loops' back edges) | 1063 // Some branch instructions (e.g. loops' back edges) |
1053 // can potentially cause a GC so they have a pointer map. | 1064 // can potentially cause a GC so they have a pointer map. |
1054 // By inserting a move we essentially create a copy of a | 1065 // By inserting a move we essentially create a copy of a |
1055 // value which is invisible to PopulatePointerMaps(), because we store | 1066 // value which is invisible to PopulatePointerMaps(), because we store |
1056 // it into a location different from the operand of a live range | 1067 // it into a location different from the operand of a live range |
1057 // covering a branch instruction. | 1068 // covering a branch instruction. |
1058 // Thus we need to manually record a pointer. | 1069 // Thus we need to manually record a pointer. |
1059 LInstruction* branch = | 1070 LInstruction* branch = |
1060 InstructionAt(cur_block->last_instruction_index()); | 1071 InstructionAt(cur_block->last_instruction_index()); |
1061 if (branch->HasPointerMap()) { | 1072 if (branch->HasPointerMap()) { |
1062 if (phi->representation().IsTagged() && !phi->type().IsSmi()) { | 1073 if (phi->representation().IsTagged() && !phi->type().IsSmi()) { |
1063 branch->pointer_map()->RecordPointer(phi_operand, zone()); | 1074 branch->pointer_map()->RecordPointer(phi_operand, chunk()->zone()); |
1064 } else if (!phi->representation().IsDouble()) { | 1075 } else if (!phi->representation().IsDouble()) { |
1065 branch->pointer_map()->RecordUntagged(phi_operand, zone()); | 1076 branch->pointer_map()->RecordUntagged(phi_operand, chunk()->zone()); |
1066 } | 1077 } |
1067 } | 1078 } |
1068 } | 1079 } |
1069 | 1080 |
1070 LiveRange* live_range = LiveRangeFor(phi->id()); | 1081 LiveRange* live_range = LiveRangeFor(phi->id()); |
1071 LLabel* label = chunk_->GetLabel(phi->block()->block_id()); | 1082 LLabel* label = chunk_->GetLabel(phi->block()->block_id()); |
1072 label->GetOrCreateParallelMove(LGap::START, zone())-> | 1083 label->GetOrCreateParallelMove(LGap::START, chunk()->zone())-> |
1073 AddMove(phi_operand, live_range->GetSpillOperand(), zone()); | 1084 AddMove(phi_operand, live_range->GetSpillOperand(), chunk()->zone()); |
1074 live_range->SetSpillStartIndex(phi->block()->first_instruction_index()); | 1085 live_range->SetSpillStartIndex(phi->block()->first_instruction_index()); |
1075 } | 1086 } |
1076 } | 1087 } |
1077 | 1088 |
1078 | 1089 |
1079 bool LAllocator::Allocate(LChunk* chunk) { | 1090 bool LAllocator::Allocate(LChunk* chunk) { |
1080 ASSERT(chunk_ == NULL); | 1091 ASSERT(chunk_ == NULL); |
1081 chunk_ = static_cast<LPlatformChunk*>(chunk); | 1092 chunk_ = static_cast<LPlatformChunk*>(chunk); |
1082 assigned_registers_ = | 1093 assigned_registers_ = |
1083 new(zone()) BitVector(Register::NumAllocatableRegisters(), zone()); | 1094 new(chunk->zone()) BitVector(Register::NumAllocatableRegisters(), |
1084 assigned_registers_->Clear(); | 1095 chunk->zone()); |
1085 assigned_double_registers_ = | 1096 assigned_double_registers_ = |
1086 new(zone()) BitVector(DoubleRegister::NumAllocatableRegisters(), | 1097 new(chunk->zone()) BitVector(DoubleRegister::NumAllocatableRegisters(), |
1087 zone()); | 1098 chunk->zone()); |
1088 assigned_double_registers_->Clear(); | |
1089 MeetRegisterConstraints(); | 1099 MeetRegisterConstraints(); |
1090 if (!AllocationOk()) return false; | 1100 if (!AllocationOk()) return false; |
1091 ResolvePhis(); | 1101 ResolvePhis(); |
1092 BuildLiveRanges(); | 1102 BuildLiveRanges(); |
1093 AllocateGeneralRegisters(); | 1103 AllocateGeneralRegisters(); |
1094 if (!AllocationOk()) return false; | 1104 if (!AllocationOk()) return false; |
1095 AllocateDoubleRegisters(); | 1105 AllocateDoubleRegisters(); |
1096 if (!AllocationOk()) return false; | 1106 if (!AllocationOk()) return false; |
1097 PopulatePointerMaps(); | 1107 PopulatePointerMaps(); |
1098 ConnectRanges(); | 1108 ConnectRanges(); |
(...skipping 44 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1143 if (cur_range->CanCover(pred_end)) { | 1153 if (cur_range->CanCover(pred_end)) { |
1144 ASSERT(pred_cover == NULL); | 1154 ASSERT(pred_cover == NULL); |
1145 pred_cover = cur_range; | 1155 pred_cover = cur_range; |
1146 } | 1156 } |
1147 cur_range = cur_range->next(); | 1157 cur_range = cur_range->next(); |
1148 } | 1158 } |
1149 | 1159 |
1150 if (cur_cover->IsSpilled()) return; | 1160 if (cur_cover->IsSpilled()) return; |
1151 ASSERT(pred_cover != NULL && cur_cover != NULL); | 1161 ASSERT(pred_cover != NULL && cur_cover != NULL); |
1152 if (pred_cover != cur_cover) { | 1162 if (pred_cover != cur_cover) { |
1153 LOperand* pred_op = pred_cover->CreateAssignedOperand(zone_); | 1163 LOperand* pred_op = pred_cover->CreateAssignedOperand(chunk()->zone()); |
1154 LOperand* cur_op = cur_cover->CreateAssignedOperand(zone_); | 1164 LOperand* cur_op = cur_cover->CreateAssignedOperand(chunk()->zone()); |
1155 if (!pred_op->Equals(cur_op)) { | 1165 if (!pred_op->Equals(cur_op)) { |
1156 LGap* gap = NULL; | 1166 LGap* gap = NULL; |
1157 if (block->predecessors()->length() == 1) { | 1167 if (block->predecessors()->length() == 1) { |
1158 gap = GapAt(block->first_instruction_index()); | 1168 gap = GapAt(block->first_instruction_index()); |
1159 } else { | 1169 } else { |
1160 ASSERT(pred->end()->SecondSuccessor() == NULL); | 1170 ASSERT(pred->end()->SecondSuccessor() == NULL); |
1161 gap = GetLastGap(pred); | 1171 gap = GetLastGap(pred); |
1162 | 1172 |
1163 // We are going to insert a move before the branch instruction. | 1173 // We are going to insert a move before the branch instruction. |
1164 // Some branch instructions (e.g. loops' back edges) | 1174 // Some branch instructions (e.g. loops' back edges) |
1165 // can potentially cause a GC so they have a pointer map. | 1175 // can potentially cause a GC so they have a pointer map. |
1166 // By inserting a move we essentially create a copy of a | 1176 // By inserting a move we essentially create a copy of a |
1167 // value which is invisible to PopulatePointerMaps(), because we store | 1177 // value which is invisible to PopulatePointerMaps(), because we store |
1168 // it into a location different from the operand of a live range | 1178 // it into a location different from the operand of a live range |
1169 // covering a branch instruction. | 1179 // covering a branch instruction. |
1170 // Thus we need to manually record a pointer. | 1180 // Thus we need to manually record a pointer. |
1171 LInstruction* branch = InstructionAt(pred->last_instruction_index()); | 1181 LInstruction* branch = InstructionAt(pred->last_instruction_index()); |
1172 if (branch->HasPointerMap()) { | 1182 if (branch->HasPointerMap()) { |
1173 if (HasTaggedValue(range->id())) { | 1183 if (HasTaggedValue(range->id())) { |
1174 branch->pointer_map()->RecordPointer(cur_op, zone()); | 1184 branch->pointer_map()->RecordPointer(cur_op, chunk()->zone()); |
1175 } else if (!cur_op->IsDoubleStackSlot() && | 1185 } else if (!cur_op->IsDoubleStackSlot() && |
1176 !cur_op->IsDoubleRegister()) { | 1186 !cur_op->IsDoubleRegister()) { |
1177 branch->pointer_map()->RemovePointer(cur_op); | 1187 branch->pointer_map()->RemovePointer(cur_op); |
1178 } | 1188 } |
1179 } | 1189 } |
1180 } | 1190 } |
1181 gap->GetOrCreateParallelMove( | 1191 gap->GetOrCreateParallelMove( |
1182 LGap::START, zone())->AddMove(pred_op, cur_op, zone()); | 1192 LGap::START, chunk()->zone())->AddMove(pred_op, cur_op, |
| 1193 chunk()->zone()); |
1183 } | 1194 } |
1184 } | 1195 } |
1185 } | 1196 } |
1186 | 1197 |
1187 | 1198 |
1188 LParallelMove* LAllocator::GetConnectingParallelMove(LifetimePosition pos) { | 1199 LParallelMove* LAllocator::GetConnectingParallelMove(LifetimePosition pos) { |
1189 int index = pos.InstructionIndex(); | 1200 int index = pos.InstructionIndex(); |
1190 if (IsGapAt(index)) { | 1201 if (IsGapAt(index)) { |
1191 LGap* gap = GapAt(index); | 1202 LGap* gap = GapAt(index); |
1192 return gap->GetOrCreateParallelMove( | 1203 return gap->GetOrCreateParallelMove( |
1193 pos.IsInstructionStart() ? LGap::START : LGap::END, zone()); | 1204 pos.IsInstructionStart() ? LGap::START : LGap::END, chunk()->zone()); |
1194 } | 1205 } |
1195 int gap_pos = pos.IsInstructionStart() ? (index - 1) : (index + 1); | 1206 int gap_pos = pos.IsInstructionStart() ? (index - 1) : (index + 1); |
1196 return GapAt(gap_pos)->GetOrCreateParallelMove( | 1207 return GapAt(gap_pos)->GetOrCreateParallelMove( |
1197 (gap_pos < index) ? LGap::AFTER : LGap::BEFORE, zone()); | 1208 (gap_pos < index) ? LGap::AFTER : LGap::BEFORE, chunk()->zone()); |
1198 } | 1209 } |
1199 | 1210 |
1200 | 1211 |
1201 HBasicBlock* LAllocator::GetBlock(LifetimePosition pos) { | 1212 HBasicBlock* LAllocator::GetBlock(LifetimePosition pos) { |
1202 LGap* gap = GapAt(chunk_->NearestGapPos(pos.InstructionIndex())); | 1213 LGap* gap = GapAt(chunk_->NearestGapPos(pos.InstructionIndex())); |
1203 return gap->block(); | 1214 return gap->block(); |
1204 } | 1215 } |
1205 | 1216 |
1206 | 1217 |
1207 void LAllocator::ConnectRanges() { | 1218 void LAllocator::ConnectRanges() { |
1208 LAllocatorPhase phase("L_Connect ranges", this); | 1219 LAllocatorPhase phase("L_Connect ranges", this); |
1209 for (int i = 0; i < live_ranges()->length(); ++i) { | 1220 for (int i = 0; i < live_ranges()->length(); ++i) { |
1210 LiveRange* first_range = live_ranges()->at(i); | 1221 LiveRange* first_range = live_ranges()->at(i); |
1211 if (first_range == NULL || first_range->parent() != NULL) continue; | 1222 if (first_range == NULL || first_range->parent() != NULL) continue; |
1212 | 1223 |
1213 LiveRange* second_range = first_range->next(); | 1224 LiveRange* second_range = first_range->next(); |
1214 while (second_range != NULL) { | 1225 while (second_range != NULL) { |
1215 LifetimePosition pos = second_range->Start(); | 1226 LifetimePosition pos = second_range->Start(); |
1216 | 1227 |
1217 if (!second_range->IsSpilled()) { | 1228 if (!second_range->IsSpilled()) { |
1218 // Add gap move if the two live ranges touch and there is no block | 1229 // Add gap move if the two live ranges touch and there is no block |
1219 // boundary. | 1230 // boundary. |
1220 if (first_range->End().Value() == pos.Value()) { | 1231 if (first_range->End().Value() == pos.Value()) { |
1221 bool should_insert = true; | 1232 bool should_insert = true; |
1222 if (IsBlockBoundary(pos)) { | 1233 if (IsBlockBoundary(pos)) { |
1223 should_insert = CanEagerlyResolveControlFlow(GetBlock(pos)); | 1234 should_insert = CanEagerlyResolveControlFlow(GetBlock(pos)); |
1224 } | 1235 } |
1225 if (should_insert) { | 1236 if (should_insert) { |
1226 LParallelMove* move = GetConnectingParallelMove(pos); | 1237 LParallelMove* move = GetConnectingParallelMove(pos); |
1227 LOperand* prev_operand = first_range->CreateAssignedOperand(zone_); | 1238 LOperand* prev_operand = first_range->CreateAssignedOperand( |
1228 LOperand* cur_operand = second_range->CreateAssignedOperand(zone_); | 1239 chunk()->zone()); |
1229 move->AddMove(prev_operand, cur_operand, zone()); | 1240 LOperand* cur_operand = second_range->CreateAssignedOperand( |
| 1241 chunk()->zone()); |
| 1242 move->AddMove(prev_operand, cur_operand, |
| 1243 chunk()->zone()); |
1230 } | 1244 } |
1231 } | 1245 } |
1232 } | 1246 } |
1233 | 1247 |
1234 first_range = second_range; | 1248 first_range = second_range; |
1235 second_range = second_range->next(); | 1249 second_range = second_range->next(); |
1236 } | 1250 } |
1237 } | 1251 } |
1238 } | 1252 } |
1239 | 1253 |
(...skipping 44 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1284 const ZoneList<HPhi*>* phis = block->phis(); | 1298 const ZoneList<HPhi*>* phis = block->phis(); |
1285 for (int i = 0; i < phis->length(); ++i) { | 1299 for (int i = 0; i < phis->length(); ++i) { |
1286 // The live range interval already ends at the first instruction of the | 1300 // The live range interval already ends at the first instruction of the |
1287 // block. | 1301 // block. |
1288 HPhi* phi = phis->at(i); | 1302 HPhi* phi = phis->at(i); |
1289 live->Remove(phi->id()); | 1303 live->Remove(phi->id()); |
1290 | 1304 |
1291 LOperand* hint = NULL; | 1305 LOperand* hint = NULL; |
1292 LOperand* phi_operand = NULL; | 1306 LOperand* phi_operand = NULL; |
1293 LGap* gap = GetLastGap(phi->block()->predecessors()->at(0)); | 1307 LGap* gap = GetLastGap(phi->block()->predecessors()->at(0)); |
1294 LParallelMove* move = gap->GetOrCreateParallelMove(LGap::START, zone()); | 1308 LParallelMove* move = gap->GetOrCreateParallelMove(LGap::START, |
| 1309 chunk()->zone()); |
1295 for (int j = 0; j < move->move_operands()->length(); ++j) { | 1310 for (int j = 0; j < move->move_operands()->length(); ++j) { |
1296 LOperand* to = move->move_operands()->at(j).destination(); | 1311 LOperand* to = move->move_operands()->at(j).destination(); |
1297 if (to->IsUnallocated() && | 1312 if (to->IsUnallocated() && |
1298 LUnallocated::cast(to)->virtual_register() == phi->id()) { | 1313 LUnallocated::cast(to)->virtual_register() == phi->id()) { |
1299 hint = move->move_operands()->at(j).source(); | 1314 hint = move->move_operands()->at(j).source(); |
1300 phi_operand = to; | 1315 phi_operand = to; |
1301 break; | 1316 break; |
1302 } | 1317 } |
1303 } | 1318 } |
1304 ASSERT(hint != NULL); | 1319 ASSERT(hint != NULL); |
(...skipping 16 matching lines...) Expand all Loading... |
1321 // header. | 1336 // header. |
1322 HBasicBlock* back_edge = block->loop_information()->GetLastBackEdge(); | 1337 HBasicBlock* back_edge = block->loop_information()->GetLastBackEdge(); |
1323 BitVector::Iterator iterator(live); | 1338 BitVector::Iterator iterator(live); |
1324 LifetimePosition start = LifetimePosition::FromInstructionIndex( | 1339 LifetimePosition start = LifetimePosition::FromInstructionIndex( |
1325 block->first_instruction_index()); | 1340 block->first_instruction_index()); |
1326 LifetimePosition end = LifetimePosition::FromInstructionIndex( | 1341 LifetimePosition end = LifetimePosition::FromInstructionIndex( |
1327 back_edge->last_instruction_index()).NextInstruction(); | 1342 back_edge->last_instruction_index()).NextInstruction(); |
1328 while (!iterator.Done()) { | 1343 while (!iterator.Done()) { |
1329 int operand_index = iterator.Current(); | 1344 int operand_index = iterator.Current(); |
1330 LiveRange* range = LiveRangeFor(operand_index); | 1345 LiveRange* range = LiveRangeFor(operand_index); |
1331 range->EnsureInterval(start, end, zone_); | 1346 range->EnsureInterval(start, end, zone()); |
1332 iterator.Advance(); | 1347 iterator.Advance(); |
1333 } | 1348 } |
1334 | 1349 |
1335 for (int i = block->block_id() + 1; i <= back_edge->block_id(); ++i) { | 1350 for (int i = block->block_id() + 1; i <= back_edge->block_id(); ++i) { |
1336 live_in_sets_[i]->Union(*live); | 1351 live_in_sets_[i]->Union(*live); |
1337 } | 1352 } |
1338 } | 1353 } |
1339 | 1354 |
1340 #ifdef DEBUG | 1355 #ifdef DEBUG |
1341 if (block_id == 0) { | 1356 if (block_id == 0) { |
(...skipping 100 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1442 cur = cur->next(); | 1457 cur = cur->next(); |
1443 } | 1458 } |
1444 if (cur == NULL) continue; | 1459 if (cur == NULL) continue; |
1445 | 1460 |
1446 // Check if the live range is spilled and the safe point is after | 1461 // Check if the live range is spilled and the safe point is after |
1447 // the spill position. | 1462 // the spill position. |
1448 if (range->HasAllocatedSpillOperand() && | 1463 if (range->HasAllocatedSpillOperand() && |
1449 safe_point >= range->spill_start_index()) { | 1464 safe_point >= range->spill_start_index()) { |
1450 TraceAlloc("Pointer for range %d (spilled at %d) at safe point %d\n", | 1465 TraceAlloc("Pointer for range %d (spilled at %d) at safe point %d\n", |
1451 range->id(), range->spill_start_index(), safe_point); | 1466 range->id(), range->spill_start_index(), safe_point); |
1452 map->RecordPointer(range->GetSpillOperand(), zone()); | 1467 map->RecordPointer(range->GetSpillOperand(), chunk()->zone()); |
1453 } | 1468 } |
1454 | 1469 |
1455 if (!cur->IsSpilled()) { | 1470 if (!cur->IsSpilled()) { |
1456 TraceAlloc("Pointer in register for range %d (start at %d) " | 1471 TraceAlloc("Pointer in register for range %d (start at %d) " |
1457 "at safe point %d\n", | 1472 "at safe point %d\n", |
1458 cur->id(), cur->Start().Value(), safe_point); | 1473 cur->id(), cur->Start().Value(), safe_point); |
1459 LOperand* operand = cur->CreateAssignedOperand(zone_); | 1474 LOperand* operand = cur->CreateAssignedOperand(chunk()->zone()); |
1460 ASSERT(!operand->IsStackSlot()); | 1475 ASSERT(!operand->IsStackSlot()); |
1461 map->RecordPointer(operand, zone()); | 1476 map->RecordPointer(operand, chunk()->zone()); |
1462 } | 1477 } |
1463 } | 1478 } |
1464 } | 1479 } |
1465 } | 1480 } |
1466 | 1481 |
1467 | 1482 |
1468 void LAllocator::AllocateGeneralRegisters() { | 1483 void LAllocator::AllocateGeneralRegisters() { |
1469 LAllocatorPhase phase("L_Allocate general registers", this); | 1484 LAllocatorPhase phase("L_Allocate general registers", this); |
1470 num_registers_ = Register::NumAllocatableRegisters(); | 1485 num_registers_ = Register::NumAllocatableRegisters(); |
1471 AllocateRegisters(); | 1486 AllocateRegisters(); |
(...skipping 320 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1792 RegisterName(register_index), | 1807 RegisterName(register_index), |
1793 free_until_pos[register_index].Value(), | 1808 free_until_pos[register_index].Value(), |
1794 current->id(), | 1809 current->id(), |
1795 current->End().Value()); | 1810 current->End().Value()); |
1796 | 1811 |
1797 // The desired register is free until the end of the current live range. | 1812 // The desired register is free until the end of the current live range. |
1798 if (free_until_pos[register_index].Value() >= current->End().Value()) { | 1813 if (free_until_pos[register_index].Value() >= current->End().Value()) { |
1799 TraceAlloc("Assigning preferred reg %s to live range %d\n", | 1814 TraceAlloc("Assigning preferred reg %s to live range %d\n", |
1800 RegisterName(register_index), | 1815 RegisterName(register_index), |
1801 current->id()); | 1816 current->id()); |
1802 SetLiveRangeAssignedRegister(current, register_index, mode_, zone_); | 1817 SetLiveRangeAssignedRegister(current, register_index, mode_); |
1803 return true; | 1818 return true; |
1804 } | 1819 } |
1805 } | 1820 } |
1806 | 1821 |
1807 // Find the register which stays free for the longest time. | 1822 // Find the register which stays free for the longest time. |
1808 int reg = 0; | 1823 int reg = 0; |
1809 for (int i = 1; i < RegisterCount(); ++i) { | 1824 for (int i = 1; i < RegisterCount(); ++i) { |
1810 if (free_until_pos[i].Value() > free_until_pos[reg].Value()) { | 1825 if (free_until_pos[i].Value() > free_until_pos[reg].Value()) { |
1811 reg = i; | 1826 reg = i; |
1812 } | 1827 } |
(...skipping 14 matching lines...) Expand all Loading... |
1827 AddToUnhandledSorted(tail); | 1842 AddToUnhandledSorted(tail); |
1828 } | 1843 } |
1829 | 1844 |
1830 | 1845 |
1831 // Register reg is available at the range start and is free until | 1846 // Register reg is available at the range start and is free until |
1832 // the range end. | 1847 // the range end. |
1833 ASSERT(pos.Value() >= current->End().Value()); | 1848 ASSERT(pos.Value() >= current->End().Value()); |
1834 TraceAlloc("Assigning free reg %s to live range %d\n", | 1849 TraceAlloc("Assigning free reg %s to live range %d\n", |
1835 RegisterName(reg), | 1850 RegisterName(reg), |
1836 current->id()); | 1851 current->id()); |
1837 SetLiveRangeAssignedRegister(current, reg, mode_, zone_); | 1852 SetLiveRangeAssignedRegister(current, reg, mode_); |
1838 | 1853 |
1839 return true; | 1854 return true; |
1840 } | 1855 } |
1841 | 1856 |
1842 | 1857 |
1843 void LAllocator::AllocateBlockedReg(LiveRange* current) { | 1858 void LAllocator::AllocateBlockedReg(LiveRange* current) { |
1844 UsePosition* register_use = current->NextRegisterPosition(current->Start()); | 1859 UsePosition* register_use = current->NextRegisterPosition(current->Start()); |
1845 if (register_use == NULL) { | 1860 if (register_use == NULL) { |
1846 // There is no use in the current live range that requires a register. | 1861 // There is no use in the current live range that requires a register. |
1847 // We can just spill it. | 1862 // We can just spill it. |
(...skipping 64 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1912 block_pos[reg].InstructionStart()); | 1927 block_pos[reg].InstructionStart()); |
1913 if (!AllocationOk()) return; | 1928 if (!AllocationOk()) return; |
1914 AddToUnhandledSorted(tail); | 1929 AddToUnhandledSorted(tail); |
1915 } | 1930 } |
1916 | 1931 |
1917 // Register reg is not blocked for the whole range. | 1932 // Register reg is not blocked for the whole range. |
1918 ASSERT(block_pos[reg].Value() >= current->End().Value()); | 1933 ASSERT(block_pos[reg].Value() >= current->End().Value()); |
1919 TraceAlloc("Assigning blocked reg %s to live range %d\n", | 1934 TraceAlloc("Assigning blocked reg %s to live range %d\n", |
1920 RegisterName(reg), | 1935 RegisterName(reg), |
1921 current->id()); | 1936 current->id()); |
1922 SetLiveRangeAssignedRegister(current, reg, mode_, zone_); | 1937 SetLiveRangeAssignedRegister(current, reg, mode_); |
1923 | 1938 |
1924 // This register was not free. Thus we need to find and spill | 1939 // This register was not free. Thus we need to find and spill |
1925 // parts of active and inactive live regions that use the same register | 1940 // parts of active and inactive live regions that use the same register |
1926 // at the same lifetime positions as current. | 1941 // at the same lifetime positions as current. |
1927 SplitAndSpillIntersecting(current); | 1942 SplitAndSpillIntersecting(current); |
1928 } | 1943 } |
1929 | 1944 |
1930 | 1945 |
1931 LifetimePosition LAllocator::FindOptimalSpillingPos(LiveRange* range, | 1946 LifetimePosition LAllocator::FindOptimalSpillingPos(LiveRange* range, |
1932 LifetimePosition pos) { | 1947 LifetimePosition pos) { |
(...skipping 91 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2024 if (pos.Value() <= range->Start().Value()) return range; | 2039 if (pos.Value() <= range->Start().Value()) return range; |
2025 | 2040 |
2026 // We can't properly connect liveranges if split occured at the end | 2041 // We can't properly connect liveranges if split occured at the end |
2027 // of control instruction. | 2042 // of control instruction. |
2028 ASSERT(pos.IsInstructionStart() || | 2043 ASSERT(pos.IsInstructionStart() || |
2029 !chunk_->instructions()->at(pos.InstructionIndex())->IsControl()); | 2044 !chunk_->instructions()->at(pos.InstructionIndex())->IsControl()); |
2030 | 2045 |
2031 int vreg = GetVirtualRegister(); | 2046 int vreg = GetVirtualRegister(); |
2032 if (!AllocationOk()) return NULL; | 2047 if (!AllocationOk()) return NULL; |
2033 LiveRange* result = LiveRangeFor(vreg); | 2048 LiveRange* result = LiveRangeFor(vreg); |
2034 range->SplitAt(pos, result, zone_); | 2049 range->SplitAt(pos, result, zone()); |
2035 return result; | 2050 return result; |
2036 } | 2051 } |
2037 | 2052 |
2038 | 2053 |
2039 LiveRange* LAllocator::SplitBetween(LiveRange* range, | 2054 LiveRange* LAllocator::SplitBetween(LiveRange* range, |
2040 LifetimePosition start, | 2055 LifetimePosition start, |
2041 LifetimePosition end) { | 2056 LifetimePosition end) { |
2042 ASSERT(!range->IsFixed()); | 2057 ASSERT(!range->IsFixed()); |
2043 TraceAlloc("Splitting live range %d in position between [%d, %d]\n", | 2058 TraceAlloc("Splitting live range %d in position between [%d, %d]\n", |
2044 range->id(), | 2059 range->id(), |
(...skipping 87 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2132 void LAllocator::Spill(LiveRange* range) { | 2147 void LAllocator::Spill(LiveRange* range) { |
2133 ASSERT(!range->IsSpilled()); | 2148 ASSERT(!range->IsSpilled()); |
2134 TraceAlloc("Spilling live range %d\n", range->id()); | 2149 TraceAlloc("Spilling live range %d\n", range->id()); |
2135 LiveRange* first = range->TopLevel(); | 2150 LiveRange* first = range->TopLevel(); |
2136 | 2151 |
2137 if (!first->HasAllocatedSpillOperand()) { | 2152 if (!first->HasAllocatedSpillOperand()) { |
2138 LOperand* op = TryReuseSpillSlot(range); | 2153 LOperand* op = TryReuseSpillSlot(range); |
2139 if (op == NULL) op = chunk_->GetNextSpillSlot(mode_ == DOUBLE_REGISTERS); | 2154 if (op == NULL) op = chunk_->GetNextSpillSlot(mode_ == DOUBLE_REGISTERS); |
2140 first->SetSpillOperand(op); | 2155 first->SetSpillOperand(op); |
2141 } | 2156 } |
2142 range->MakeSpilled(zone_); | 2157 range->MakeSpilled(chunk()->zone()); |
2143 } | 2158 } |
2144 | 2159 |
2145 | 2160 |
2146 int LAllocator::RegisterCount() const { | 2161 int LAllocator::RegisterCount() const { |
2147 return num_registers_; | 2162 return num_registers_; |
2148 } | 2163 } |
2149 | 2164 |
2150 | 2165 |
2151 #ifdef DEBUG | 2166 #ifdef DEBUG |
2152 | 2167 |
2153 | 2168 |
2154 void LAllocator::Verify() const { | 2169 void LAllocator::Verify() const { |
2155 for (int i = 0; i < live_ranges()->length(); ++i) { | 2170 for (int i = 0; i < live_ranges()->length(); ++i) { |
2156 LiveRange* current = live_ranges()->at(i); | 2171 LiveRange* current = live_ranges()->at(i); |
2157 if (current != NULL) current->Verify(); | 2172 if (current != NULL) current->Verify(); |
2158 } | 2173 } |
2159 } | 2174 } |
2160 | 2175 |
2161 | 2176 |
2162 #endif | 2177 #endif |
2163 | 2178 |
2164 | 2179 |
| 2180 LAllocatorPhase::LAllocatorPhase(const char* name, LAllocator* allocator) |
| 2181 : CompilationPhase(name, allocator->graph()->info()), |
| 2182 allocator_(allocator) { |
| 2183 if (FLAG_hydrogen_stats) { |
| 2184 allocator_zone_start_allocation_size_ = |
| 2185 allocator->zone()->allocation_size(); |
| 2186 } |
| 2187 } |
| 2188 |
| 2189 |
2165 LAllocatorPhase::~LAllocatorPhase() { | 2190 LAllocatorPhase::~LAllocatorPhase() { |
| 2191 if (FLAG_hydrogen_stats) { |
| 2192 unsigned size = allocator_->zone()->allocation_size() - |
| 2193 allocator_zone_start_allocation_size_; |
| 2194 isolate()->GetHStatistics()->SaveTiming(name(), 0, size); |
| 2195 } |
| 2196 |
2166 if (ShouldProduceTraceOutput()) { | 2197 if (ShouldProduceTraceOutput()) { |
2167 isolate()->GetHTracer()->TraceLithium(name(), allocator_->chunk()); | 2198 isolate()->GetHTracer()->TraceLithium(name(), allocator_->chunk()); |
2168 isolate()->GetHTracer()->TraceLiveRanges(name(), allocator_); | 2199 isolate()->GetHTracer()->TraceLiveRanges(name(), allocator_); |
2169 } | 2200 } |
2170 | 2201 |
2171 #ifdef DEBUG | 2202 #ifdef DEBUG |
2172 if (allocator_ != NULL) allocator_->Verify(); | 2203 if (allocator_ != NULL) allocator_->Verify(); |
2173 #endif | 2204 #endif |
2174 } | 2205 } |
2175 | 2206 |
2176 | 2207 |
2177 } } // namespace v8::internal | 2208 } } // namespace v8::internal |
OLD | NEW |