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