OLD | NEW |
1 // Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file |
2 // for details. All rights reserved. Use of this source code is governed by a | 2 // for details. All rights reserved. Use of this source code is governed by a |
3 // BSD-style license that can be found in the LICENSE file. | 3 // BSD-style license that can be found in the LICENSE file. |
4 | 4 |
5 #include "vm/flow_graph_allocator.h" | 5 #include "vm/flow_graph_allocator.h" |
6 | 6 |
7 #include "vm/bit_vector.h" | 7 #include "vm/bit_vector.h" |
8 #include "vm/intermediate_language.h" | 8 #include "vm/intermediate_language.h" |
9 #include "vm/il_printer.h" | 9 #include "vm/il_printer.h" |
10 #include "vm/flow_graph_builder.h" | 10 #include "vm/flow_graph_builder.h" |
(...skipping 82 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
93 for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) { | 93 for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) { |
94 Instruction* current = it.Current(); | 94 Instruction* current = it.Current(); |
95 if (current->CanDeoptimize()) { | 95 if (current->CanDeoptimize()) { |
96 ASSERT(current->env() != NULL); | 96 ASSERT(current->env() != NULL); |
97 GrowableArray<Value*>* values = current->env()->values_ptr(); | 97 GrowableArray<Value*>* values = current->env()->values_ptr(); |
98 | 98 |
99 for (intptr_t i = 0; i < values->length(); i++) { | 99 for (intptr_t i = 0; i < values->length(); i++) { |
100 UseVal* use = (*values)[i]->AsUse(); | 100 UseVal* use = (*values)[i]->AsUse(); |
101 if (use == NULL) continue; | 101 if (use == NULL) continue; |
102 | 102 |
103 PhiInstr* phi = use->definition()->AsPhi(); | 103 Definition* def = use->definition(); |
104 if (phi == NULL) continue; | |
105 | 104 |
106 if (!phi->is_alive()) (*values)[i] = null_value; | 105 PushArgumentInstr* push_argument = def->AsPushArgument(); |
| 106 if ((push_argument != NULL) && push_argument->WasEliminated()) { |
| 107 (*values)[i] = push_argument->value(); |
| 108 continue; |
| 109 } |
| 110 |
| 111 PhiInstr* phi = def->AsPhi(); |
| 112 if ((phi != NULL) && !phi->is_alive()) { |
| 113 (*values)[i] = null_value; |
| 114 continue; |
| 115 } |
107 } | 116 } |
108 } else { | 117 } else { |
109 current->set_env(NULL); | 118 current->set_env(NULL); |
110 } | 119 } |
111 } | 120 } |
112 } | 121 } |
113 } | 122 } |
114 | 123 |
115 | 124 |
116 void FlowGraphAllocator::ComputeInitialSets() { | 125 void FlowGraphAllocator::ComputeInitialSets() { |
(...skipping 21 matching lines...) Expand all Loading... |
138 if (input->IsUse()) { | 147 if (input->IsUse()) { |
139 const intptr_t use = input->AsUse()->definition()->ssa_temp_index(); | 148 const intptr_t use = input->AsUse()->definition()->ssa_temp_index(); |
140 live_in->Add(use); | 149 live_in->Add(use); |
141 } | 150 } |
142 } | 151 } |
143 | 152 |
144 // Add uses from the deoptimization environment. | 153 // Add uses from the deoptimization environment. |
145 if (current->env() != NULL) { | 154 if (current->env() != NULL) { |
146 const GrowableArray<Value*>& values = current->env()->values(); | 155 const GrowableArray<Value*>& values = current->env()->values(); |
147 for (intptr_t j = 0; j < values.length(); j++) { | 156 for (intptr_t j = 0; j < values.length(); j++) { |
148 Value* val = values[j]; | 157 UseVal* use_val = values[j]->AsUse(); |
149 if (val->IsUse()) { | 158 if ((use_val != NULL) && !use_val->definition()->IsPushArgument()) { |
150 const intptr_t use = val->AsUse()->definition()->ssa_temp_index(); | 159 live_in->Add(use_val->definition()->ssa_temp_index()); |
151 live_in->Add(use); | |
152 } | 160 } |
153 } | 161 } |
154 } | 162 } |
155 } | 163 } |
156 | 164 |
157 // Handle phis. | 165 // Handle phis. |
158 if (block->IsJoinEntry()) { | 166 if (block->IsJoinEntry()) { |
159 JoinEntryInstr* join = block->AsJoinEntry(); | 167 JoinEntryInstr* join = block->AsJoinEntry(); |
160 if (join->phis() != NULL) { | 168 if (join->phis() != NULL) { |
161 for (intptr_t j = 0; j < join->phis()->length(); j++) { | 169 for (intptr_t j = 0; j < join->phis()->length(); j++) { |
(...skipping 487 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
649 // All phi resolution moves are connected. Phi's live range is | 657 // All phi resolution moves are connected. Phi's live range is |
650 // complete. | 658 // complete. |
651 AddToUnallocated(range); | 659 AddToUnallocated(range); |
652 | 660 |
653 move_idx++; | 661 move_idx++; |
654 } | 662 } |
655 } | 663 } |
656 } | 664 } |
657 | 665 |
658 | 666 |
| 667 void FlowGraphAllocator::ProcessEnvironmentUses(BlockEntryInstr* block, |
| 668 Instruction* current) { |
| 669 ASSERT(current->env() != NULL); |
| 670 |
| 671 Environment* env = current->env(); |
| 672 |
| 673 // Any value mentioned in the deoptimization environment should survive |
| 674 // until the end of instruction but it does not need to be in the register. |
| 675 // Expected shape of live range: |
| 676 // |
| 677 // i i' |
| 678 // value -----* |
| 679 // |
| 680 |
| 681 const GrowableArray<Value*>& values = env->values(); |
| 682 if (values.length() == 0) return; |
| 683 |
| 684 const intptr_t block_start_pos = block->start_pos(); |
| 685 const intptr_t use_pos = current->lifetime_position() + 1; |
| 686 |
| 687 Location* locations = |
| 688 Isolate::Current()->current_zone()->Alloc<Location>(values.length()); |
| 689 |
| 690 for (intptr_t i = 0; i < values.length(); ++i) { |
| 691 Value* value = values[i]; |
| 692 if (value->IsUse()) { |
| 693 locations[i] = Location::Any(); |
| 694 Definition* def = value->AsUse()->definition(); |
| 695 |
| 696 if (def->IsPushArgument()) { |
| 697 // Frame size is unknown until after allocation. |
| 698 locations[i] = Location::NoLocation(); |
| 699 continue; |
| 700 } |
| 701 |
| 702 const intptr_t vreg = def->ssa_temp_index(); |
| 703 LiveRange* range = GetLiveRange(vreg); |
| 704 range->AddUseInterval(block_start_pos, use_pos); |
| 705 range->AddUse(use_pos, &locations[i]); |
| 706 } else { |
| 707 ASSERT(value->IsConstant()); |
| 708 locations[i] = Location::NoLocation(); |
| 709 } |
| 710 } |
| 711 |
| 712 env->set_locations(locations); |
| 713 } |
| 714 |
| 715 |
659 // Create and update live ranges corresponding to instruction's inputs, | 716 // Create and update live ranges corresponding to instruction's inputs, |
660 // temporaries and output. | 717 // temporaries and output. |
661 void FlowGraphAllocator::ProcessOneInstruction(BlockEntryInstr* block, | 718 void FlowGraphAllocator::ProcessOneInstruction(BlockEntryInstr* block, |
662 Instruction* current) { | 719 Instruction* current) { |
663 const intptr_t pos = current->lifetime_position(); | 720 const intptr_t pos = current->lifetime_position(); |
664 ASSERT(IsInstructionStartPosition(pos)); | 721 ASSERT(IsInstructionStartPosition(pos)); |
665 | 722 |
666 LocationSummary* locs = current->locs(); | 723 LocationSummary* locs = current->locs(); |
667 | 724 |
668 // TODO(vegorov): number of inputs must match number of input locations. | 725 // TODO(vegorov): number of inputs must match number of input locations. |
669 if (locs->input_count() != current->InputCount()) { | 726 if (locs->input_count() != current->InputCount()) { |
670 builder_->Bailout("ssa allocator: number of input locations mismatch"); | 727 builder_->Bailout("ssa allocator: number of input locations mismatch"); |
671 } | 728 } |
672 | 729 |
673 // Normalize same-as-first-input output if input is specified as | 730 // Normalize same-as-first-input output if input is specified as |
674 // fixed register. | 731 // fixed register. |
675 if (locs->out().IsUnallocated() && | 732 if (locs->out().IsUnallocated() && |
676 (locs->out().policy() == Location::kSameAsFirstInput) && | 733 (locs->out().policy() == Location::kSameAsFirstInput) && |
677 (locs->in(0).IsRegister())) { | 734 (locs->in(0).IsRegister())) { |
678 locs->set_out(locs->in(0)); | 735 locs->set_out(locs->in(0)); |
679 } | 736 } |
680 | 737 |
681 const bool output_same_as_first_input = | 738 const bool output_same_as_first_input = |
682 locs->out().IsUnallocated() && | 739 locs->out().IsUnallocated() && |
683 (locs->out().policy() == Location::kSameAsFirstInput); | 740 (locs->out().policy() == Location::kSameAsFirstInput); |
684 | 741 |
685 // Add uses from the deoptimization environment. | 742 // Add uses from the deoptimization environment. |
686 Environment* env = current->env(); | 743 if (current->env() != NULL) ProcessEnvironmentUses(block, current); |
687 if (env != NULL) { | |
688 env->InitializeLocations(this, block->start_pos(), pos + 1); | |
689 } | |
690 | 744 |
691 // Process inputs. | 745 // Process inputs. |
692 // Skip the first input if output is specified with kSameAsFirstInput policy, | 746 // Skip the first input if output is specified with kSameAsFirstInput policy, |
693 // they will be processed together at the very end. | 747 // they will be processed together at the very end. |
694 for (intptr_t j = output_same_as_first_input ? 1 : 0; | 748 for (intptr_t j = output_same_as_first_input ? 1 : 0; |
695 j < current->InputCount(); | 749 j < current->InputCount(); |
696 j++) { | 750 j++) { |
697 Value* input = current->InputAt(j); | 751 Value* input = current->InputAt(j); |
698 ASSERT(input->IsUse()); // Can not be a constant currently. | 752 ASSERT(input->IsUse()); // Can not be a constant currently. |
699 const intptr_t vreg = input->AsUse()->definition()->ssa_temp_index(); | 753 const intptr_t vreg = input->AsUse()->definition()->ssa_temp_index(); |
(...skipping 1187 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1887 OS::Print("-- [after ssa allocator] ir [%s] -------------\n", | 1941 OS::Print("-- [after ssa allocator] ir [%s] -------------\n", |
1888 function.ToFullyQualifiedCString()); | 1942 function.ToFullyQualifiedCString()); |
1889 FlowGraphPrinter printer(Function::Handle(), block_order_, true); | 1943 FlowGraphPrinter printer(Function::Handle(), block_order_, true); |
1890 printer.PrintBlocks(); | 1944 printer.PrintBlocks(); |
1891 OS::Print("----------------------------------------------\n"); | 1945 OS::Print("----------------------------------------------\n"); |
1892 } | 1946 } |
1893 } | 1947 } |
1894 | 1948 |
1895 | 1949 |
1896 } // namespace dart | 1950 } // namespace dart |
OLD | NEW |