| 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.h" | 10 #include "vm/flow_graph.h" |
| (...skipping 83 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 94 postorder_.Last()->AsGraphEntry()->constant_null(); | 94 postorder_.Last()->AsGraphEntry()->constant_null(); |
| 95 for (intptr_t i = 0; i < block_order_.length(); ++i) { | 95 for (intptr_t i = 0; i < block_order_.length(); ++i) { |
| 96 BlockEntryInstr* block = block_order_[i]; | 96 BlockEntryInstr* block = block_order_[i]; |
| 97 if (block->IsJoinEntry()) block->AsJoinEntry()->RemoveDeadPhis(); | 97 if (block->IsJoinEntry()) block->AsJoinEntry()->RemoveDeadPhis(); |
| 98 for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) { | 98 for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) { |
| 99 Instruction* current = it.Current(); | 99 Instruction* current = it.Current(); |
| 100 if (current->CanDeoptimize()) { | 100 if (current->CanDeoptimize()) { |
| 101 ASSERT(current->env() != NULL); | 101 ASSERT(current->env() != NULL); |
| 102 GrowableArray<Value*>* values = current->env()->values_ptr(); | 102 GrowableArray<Value*>* values = current->env()->values_ptr(); |
| 103 for (intptr_t i = 0; i < values->length(); i++) { | 103 for (intptr_t i = 0; i < values->length(); i++) { |
| 104 UseVal* use = (*values)[i]->AsUse(); | 104 Value* use = (*values)[i]; |
| 105 if (use == NULL) continue; | |
| 106 | |
| 107 Definition* def = use->definition(); | 105 Definition* def = use->definition(); |
| 108 PushArgumentInstr* push_argument = def->AsPushArgument(); | 106 PushArgumentInstr* push_argument = def->AsPushArgument(); |
| 109 if ((push_argument != NULL) && push_argument->WasEliminated()) { | 107 if ((push_argument != NULL) && push_argument->WasEliminated()) { |
| 110 (*values)[i] = push_argument->value()->CopyValue(); | 108 (*values)[i] = push_argument->value()->Copy(); |
| 111 continue; | 109 continue; |
| 112 } | 110 } |
| 113 | 111 |
| 114 PhiInstr* phi = def->AsPhi(); | 112 PhiInstr* phi = def->AsPhi(); |
| 115 if ((phi != NULL) && !phi->is_alive()) { | 113 if ((phi != NULL) && !phi->is_alive()) { |
| 116 (*values)[i] = new UseVal(constant_null); | 114 (*values)[i] = new Value(constant_null); |
| 117 continue; | 115 continue; |
| 118 } | 116 } |
| 119 } | 117 } |
| 120 } else { | 118 } else { |
| 121 current->set_env(NULL); | 119 current->set_env(NULL); |
| 122 } | 120 } |
| 123 } | 121 } |
| 124 } | 122 } |
| 125 } | 123 } |
| 126 | 124 |
| (...skipping 13 matching lines...) Expand all Loading... |
| 140 // Handle definitions. | 138 // Handle definitions. |
| 141 Definition* current_def = current->AsDefinition(); | 139 Definition* current_def = current->AsDefinition(); |
| 142 if ((current_def != NULL) && current_def->HasSSATemp()) { | 140 if ((current_def != NULL) && current_def->HasSSATemp()) { |
| 143 kill->Add(current_def->ssa_temp_index()); | 141 kill->Add(current_def->ssa_temp_index()); |
| 144 live_in->Remove(current_def->ssa_temp_index()); | 142 live_in->Remove(current_def->ssa_temp_index()); |
| 145 } | 143 } |
| 146 | 144 |
| 147 // Handle uses. | 145 // Handle uses. |
| 148 for (intptr_t j = 0; j < current->InputCount(); j++) { | 146 for (intptr_t j = 0; j < current->InputCount(); j++) { |
| 149 Value* input = current->InputAt(j); | 147 Value* input = current->InputAt(j); |
| 150 if (input->IsUse()) { | 148 const intptr_t use = input->definition()->ssa_temp_index(); |
| 151 const intptr_t use = input->AsUse()->definition()->ssa_temp_index(); | 149 live_in->Add(use); |
| 152 live_in->Add(use); | |
| 153 } | |
| 154 } | 150 } |
| 155 | 151 |
| 156 // Add uses from the deoptimization environment. | 152 // Add uses from the deoptimization environment. |
| 157 if (current->env() != NULL) { | 153 if (current->env() != NULL) { |
| 158 const GrowableArray<Value*>& values = current->env()->values(); | 154 const GrowableArray<Value*>& values = current->env()->values(); |
| 159 for (intptr_t j = 0; j < values.length(); j++) { | 155 for (intptr_t j = 0; j < values.length(); j++) { |
| 160 UseVal* use_val = values[j]->AsUse(); | 156 Value* value = values[j]; |
| 161 if ((use_val != NULL) && !use_val->definition()->IsPushArgument()) { | 157 if (!value->definition()->IsPushArgument()) { |
| 162 live_in->Add(use_val->definition()->ssa_temp_index()); | 158 live_in->Add(value->definition()->ssa_temp_index()); |
| 163 } | 159 } |
| 164 } | 160 } |
| 165 } | 161 } |
| 166 } | 162 } |
| 167 | 163 |
| 168 // Handle phis. | 164 // Handle phis. |
| 169 if (block->IsJoinEntry()) { | 165 if (block->IsJoinEntry()) { |
| 170 JoinEntryInstr* join = block->AsJoinEntry(); | 166 JoinEntryInstr* join = block->AsJoinEntry(); |
| 171 if (join->phis() != NULL) { | 167 if (join->phis() != NULL) { |
| 172 for (intptr_t j = 0; j < join->phis()->length(); j++) { | 168 for (intptr_t j = 0; j < join->phis()->length(); j++) { |
| 173 PhiInstr* phi = (*join->phis())[j]; | 169 PhiInstr* phi = (*join->phis())[j]; |
| 174 if (phi == NULL) continue; | 170 if (phi == NULL) continue; |
| 175 | 171 |
| 176 kill->Add(phi->ssa_temp_index()); | 172 kill->Add(phi->ssa_temp_index()); |
| 177 live_in->Remove(phi->ssa_temp_index()); | 173 live_in->Remove(phi->ssa_temp_index()); |
| 178 | 174 |
| 179 // If phi-operand is not defined by a predecessor it must be marked | 175 // If phi-operand is not defined by a predecessor it must be marked |
| 180 // live-in for a predecessor. | 176 // live-in for a predecessor. |
| 181 for (intptr_t k = 0; k < phi->InputCount(); k++) { | 177 for (intptr_t k = 0; k < phi->InputCount(); k++) { |
| 182 Value* val = phi->InputAt(k); | 178 Value* val = phi->InputAt(k); |
| 183 if (val->IsUse()) { | 179 BlockEntryInstr* pred = block->PredecessorAt(k); |
| 184 BlockEntryInstr* pred = block->PredecessorAt(k); | 180 const intptr_t use = val->definition()->ssa_temp_index(); |
| 185 const intptr_t use = val->AsUse()->definition()->ssa_temp_index(); | 181 if (!kill_[pred->postorder_number()]->Contains(use)) { |
| 186 if (!kill_[pred->postorder_number()]->Contains(use)) { | 182 live_in_[pred->postorder_number()]->Add(use); |
| 187 live_in_[pred->postorder_number()]->Add(use); | |
| 188 } | |
| 189 } | 183 } |
| 190 } | 184 } |
| 191 } | 185 } |
| 192 } | 186 } |
| 193 } | 187 } |
| 194 } | 188 } |
| 195 | 189 |
| 196 // Process incoming parameters. | 190 // Process incoming parameters. |
| 197 GraphEntryInstr* graph_entry = postorder_.Last()->AsGraphEntry(); | 191 GraphEntryInstr* graph_entry = postorder_.Last()->AsGraphEntry(); |
| 198 for (intptr_t i = 0; i < graph_entry->start_env()->values().length(); i++) { | 192 for (intptr_t i = 0; i < graph_entry->start_env()->values().length(); i++) { |
| 199 Value* val = graph_entry->start_env()->values()[i]; | 193 Value* val = graph_entry->start_env()->values()[i]; |
| 200 if (val->IsUse()) { | 194 intptr_t vreg = val->definition()->ssa_temp_index(); |
| 201 intptr_t vreg = val->AsUse()->definition()->ssa_temp_index(); | 195 kill_[graph_entry->postorder_number()]->Add(vreg); |
| 202 kill_[graph_entry->postorder_number()]->Add(vreg); | 196 live_in_[graph_entry->postorder_number()]->Remove(vreg); |
| 203 live_in_[graph_entry->postorder_number()]->Remove(vreg); | |
| 204 } | |
| 205 } | 197 } |
| 206 | 198 |
| 207 // Process global constants. | 199 // Process global constants. |
| 208 intptr_t vreg = graph_entry->constant_null()->ssa_temp_index(); | 200 intptr_t vreg = graph_entry->constant_null()->ssa_temp_index(); |
| 209 kill_[graph_entry->postorder_number()]->Add(vreg); | 201 kill_[graph_entry->postorder_number()]->Add(vreg); |
| 210 live_in_[graph_entry->postorder_number()]->Remove(vreg); | 202 live_in_[graph_entry->postorder_number()]->Remove(vreg); |
| 211 | 203 |
| 212 // Update initial live_in sets to match live_out sets. Has to be | 204 // Update initial live_in sets to match live_out sets. Has to be |
| 213 // done in a separate path because of backwards branches. | 205 // done in a separate path because of backwards branches. |
| 214 for (intptr_t i = 0; i < block_count; i++) { | 206 for (intptr_t i = 0; i < block_count; i++) { |
| (...skipping 311 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 526 } | 518 } |
| 527 | 519 |
| 528 ConnectIncomingPhiMoves(block); | 520 ConnectIncomingPhiMoves(block); |
| 529 } | 521 } |
| 530 | 522 |
| 531 // Process incoming parameters. Do this after all other instructions so | 523 // Process incoming parameters. Do this after all other instructions so |
| 532 // that safepoints for all calls have already been found. | 524 // that safepoints for all calls have already been found. |
| 533 GraphEntryInstr* graph_entry = postorder_.Last()->AsGraphEntry(); | 525 GraphEntryInstr* graph_entry = postorder_.Last()->AsGraphEntry(); |
| 534 for (intptr_t i = 0; i < graph_entry->start_env()->values().length(); i++) { | 526 for (intptr_t i = 0; i < graph_entry->start_env()->values().length(); i++) { |
| 535 Value* val = graph_entry->start_env()->values()[i]; | 527 Value* val = graph_entry->start_env()->values()[i]; |
| 536 ASSERT(val->IsUse()); | 528 ParameterInstr* param = val->definition()->AsParameter(); |
| 537 ParameterInstr* param = val->AsUse()->definition()->AsParameter(); | |
| 538 if (param == NULL) continue; | 529 if (param == NULL) continue; |
| 539 | 530 |
| 540 // Handle the parameters specially. They are spilled on entry. | 531 // Handle the parameters specially. They are spilled on entry. |
| 541 LiveRange* range = GetLiveRange(param->ssa_temp_index()); | 532 LiveRange* range = GetLiveRange(param->ssa_temp_index()); |
| 542 range->AddUseInterval(graph_entry->start_pos(), graph_entry->end_pos()); | 533 range->AddUseInterval(graph_entry->start_pos(), graph_entry->end_pos()); |
| 543 range->DefineAt(graph_entry->start_pos()); | 534 range->DefineAt(graph_entry->start_pos()); |
| 544 | 535 |
| 545 // Assert that copied and non-copied parameters are mutually exclusive. | 536 // Assert that copied and non-copied parameters are mutually exclusive. |
| 546 // This might change in the future and, if so, the index will be wrong. | 537 // This might change in the future and, if so, the index will be wrong. |
| 547 ASSERT(flow_graph_.copied_parameter_count() == 0 || | 538 ASSERT(flow_graph_.copied_parameter_count() == 0 || |
| (...skipping 95 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 643 | 634 |
| 644 // Record the corresponding phi input use for each phi. | 635 // Record the corresponding phi input use for each phi. |
| 645 ZoneGrowableArray<PhiInstr*>* phis = join->phis(); | 636 ZoneGrowableArray<PhiInstr*>* phis = join->phis(); |
| 646 intptr_t move_idx = 0; | 637 intptr_t move_idx = 0; |
| 647 for (intptr_t phi_idx = 0; phi_idx < phis->length(); phi_idx++) { | 638 for (intptr_t phi_idx = 0; phi_idx < phis->length(); phi_idx++) { |
| 648 PhiInstr* phi = (*phis)[phi_idx]; | 639 PhiInstr* phi = (*phis)[phi_idx]; |
| 649 if (phi == NULL) continue; | 640 if (phi == NULL) continue; |
| 650 | 641 |
| 651 Value* val = phi->InputAt(pred_idx); | 642 Value* val = phi->InputAt(pred_idx); |
| 652 MoveOperands* move = parallel_move->MoveOperandsAt(move_idx); | 643 MoveOperands* move = parallel_move->MoveOperandsAt(move_idx); |
| 653 ASSERT(val->IsUse()); | |
| 654 // Expected shape of live ranges: | 644 // Expected shape of live ranges: |
| 655 // | 645 // |
| 656 // g g' | 646 // g g' |
| 657 // value --* | 647 // value --* |
| 658 // | 648 // |
| 659 | 649 |
| 660 LiveRange* range = | 650 LiveRange* range = GetLiveRange(val->definition()->ssa_temp_index()); |
| 661 GetLiveRange(val->AsUse()->definition()->ssa_temp_index()); | |
| 662 | 651 |
| 663 range->AddUseInterval(block->start_pos(), pos); | 652 range->AddUseInterval(block->start_pos(), pos); |
| 664 range->AddHintedUse(pos, move->src_slot(), move->dest_slot()); | 653 range->AddHintedUse(pos, move->src_slot(), move->dest_slot()); |
| 665 | 654 |
| 666 move->set_src(Location::PrefersRegister()); | 655 move->set_src(Location::PrefersRegister()); |
| 667 move_idx++; | 656 move_idx++; |
| 668 } | 657 } |
| 669 | 658 |
| 670 // Begin backward iteration with the instruction before the parallel | 659 // Begin backward iteration with the instruction before the parallel |
| 671 // move. | 660 // move. |
| (...skipping 70 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 742 if (values.length() == 0) return; | 731 if (values.length() == 0) return; |
| 743 | 732 |
| 744 const intptr_t block_start_pos = block->start_pos(); | 733 const intptr_t block_start_pos = block->start_pos(); |
| 745 const intptr_t use_pos = current->lifetime_position() + 1; | 734 const intptr_t use_pos = current->lifetime_position() + 1; |
| 746 | 735 |
| 747 Location* locations = | 736 Location* locations = |
| 748 Isolate::Current()->current_zone()->Alloc<Location>(values.length()); | 737 Isolate::Current()->current_zone()->Alloc<Location>(values.length()); |
| 749 | 738 |
| 750 for (intptr_t i = 0; i < values.length(); ++i) { | 739 for (intptr_t i = 0; i < values.length(); ++i) { |
| 751 Value* value = values[i]; | 740 Value* value = values[i]; |
| 752 ASSERT(value->IsUse()); | |
| 753 locations[i] = Location::Any(); | 741 locations[i] = Location::Any(); |
| 754 Definition* def = value->AsUse()->definition(); | 742 Definition* def = value->definition(); |
| 755 | 743 |
| 756 if (def->IsPushArgument()) { | 744 if (def->IsPushArgument()) { |
| 757 // Frame size is unknown until after allocation. | 745 // Frame size is unknown until after allocation. |
| 758 locations[i] = Location::NoLocation(); | 746 locations[i] = Location::NoLocation(); |
| 759 continue; | 747 continue; |
| 760 } | 748 } |
| 761 | 749 |
| 762 const intptr_t vreg = def->ssa_temp_index(); | 750 const intptr_t vreg = def->ssa_temp_index(); |
| 763 LiveRange* range = GetLiveRange(vreg); | 751 LiveRange* range = GetLiveRange(vreg); |
| 764 range->AddUseInterval(block_start_pos, use_pos); | 752 range->AddUseInterval(block_start_pos, use_pos); |
| (...skipping 49 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 814 // Add uses from the deoptimization environment. | 802 // Add uses from the deoptimization environment. |
| 815 if (current->env() != NULL) ProcessEnvironmentUses(block, current); | 803 if (current->env() != NULL) ProcessEnvironmentUses(block, current); |
| 816 | 804 |
| 817 // Process inputs. | 805 // Process inputs. |
| 818 // Skip the first input if output is specified with kSameAsFirstInput policy, | 806 // Skip the first input if output is specified with kSameAsFirstInput policy, |
| 819 // they will be processed together at the very end. | 807 // they will be processed together at the very end. |
| 820 for (intptr_t j = output_same_as_first_input ? 1 : 0; | 808 for (intptr_t j = output_same_as_first_input ? 1 : 0; |
| 821 j < current->InputCount(); | 809 j < current->InputCount(); |
| 822 j++) { | 810 j++) { |
| 823 Value* input = current->InputAt(j); | 811 Value* input = current->InputAt(j); |
| 824 ASSERT(input->IsUse()); // Can not be a constant currently. | 812 const intptr_t vreg = input->definition()->ssa_temp_index(); |
| 825 const intptr_t vreg = input->AsUse()->definition()->ssa_temp_index(); | |
| 826 LiveRange* range = GetLiveRange(vreg); | 813 LiveRange* range = GetLiveRange(vreg); |
| 827 | 814 |
| 828 Location* in_ref = locs->in_slot(j); | 815 Location* in_ref = locs->in_slot(j); |
| 829 | 816 |
| 830 if (in_ref->IsMachineRegister()) { | 817 if (in_ref->IsMachineRegister()) { |
| 831 // Input is expected in a fixed register. Expected shape of | 818 // Input is expected in a fixed register. Expected shape of |
| 832 // live ranges: | 819 // live ranges: |
| 833 // | 820 // |
| 834 // j' i i' | 821 // j' i i' |
| 835 // value --* | 822 // value --* |
| (...skipping 138 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 974 locs->in(0).Equals(Location::RequiresXmmRegister())); | 961 locs->in(0).Equals(Location::RequiresXmmRegister())); |
| 975 | 962 |
| 976 // Create move that will copy value between input and output. | 963 // Create move that will copy value between input and output. |
| 977 locs->set_out(Location::RequiresRegister()); | 964 locs->set_out(Location::RequiresRegister()); |
| 978 MoveOperands* move = AddMoveAt(pos, | 965 MoveOperands* move = AddMoveAt(pos, |
| 979 Location::RequiresRegister(), | 966 Location::RequiresRegister(), |
| 980 Location::Any()); | 967 Location::Any()); |
| 981 | 968 |
| 982 // Add uses to the live range of the input. | 969 // Add uses to the live range of the input. |
| 983 Value* input = current->InputAt(0); | 970 Value* input = current->InputAt(0); |
| 984 ASSERT(input->IsUse()); // Can not be a constant currently. | 971 LiveRange* input_range = |
| 985 LiveRange* input_range = GetLiveRange( | 972 GetLiveRange(input->definition()->ssa_temp_index()); |
| 986 input->AsUse()->definition()->ssa_temp_index()); | |
| 987 input_range->AddUseInterval(block->start_pos(), pos); | 973 input_range->AddUseInterval(block->start_pos(), pos); |
| 988 input_range->AddUse(pos, move->src_slot()); | 974 input_range->AddUse(pos, move->src_slot()); |
| 989 | 975 |
| 990 // Shorten output live range to the point of definition and add both input | 976 // Shorten output live range to the point of definition and add both input |
| 991 // and output uses slots to be filled by allocator. | 977 // and output uses slots to be filled by allocator. |
| 992 range->DefineAt(pos); | 978 range->DefineAt(pos); |
| 993 range->AddHintedUse(pos, out, move->src_slot()); | 979 range->AddHintedUse(pos, out, move->src_slot()); |
| 994 range->AddUse(pos, move->dest_slot()); | 980 range->AddUse(pos, move->dest_slot()); |
| 995 range->AddUse(pos, locs->in_slot(0)); | 981 range->AddUse(pos, locs->in_slot(0)); |
| 996 } else { | 982 } else { |
| (...skipping 1159 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 2156 OS::Print("-- [after ssa allocator] ir [%s] -------------\n", | 2142 OS::Print("-- [after ssa allocator] ir [%s] -------------\n", |
| 2157 function.ToFullyQualifiedCString()); | 2143 function.ToFullyQualifiedCString()); |
| 2158 FlowGraphPrinter printer(flow_graph_, true); | 2144 FlowGraphPrinter printer(flow_graph_, true); |
| 2159 printer.PrintBlocks(); | 2145 printer.PrintBlocks(); |
| 2160 OS::Print("----------------------------------------------\n"); | 2146 OS::Print("----------------------------------------------\n"); |
| 2161 } | 2147 } |
| 2162 } | 2148 } |
| 2163 | 2149 |
| 2164 | 2150 |
| 2165 } // namespace dart | 2151 } // namespace dart |
| OLD | NEW |