OLD | NEW |
1 // Copyright (c) 2013, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2013, 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 84 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
95 blocked_cpu_registers_[PP] = true; | 95 blocked_cpu_registers_[PP] = true; |
96 } | 96 } |
97 blocked_cpu_registers_[SPREG] = true; | 97 blocked_cpu_registers_[SPREG] = true; |
98 blocked_cpu_registers_[FPREG] = true; | 98 blocked_cpu_registers_[FPREG] = true; |
99 | 99 |
100 // FpuTMP is used as scratch by optimized code and parallel move resolver. | 100 // FpuTMP is used as scratch by optimized code and parallel move resolver. |
101 blocked_fpu_registers_[FpuTMP] = true; | 101 blocked_fpu_registers_[FpuTMP] = true; |
102 } | 102 } |
103 | 103 |
104 | 104 |
105 // Remove environments from the instructions which can't deoptimize. | |
106 void FlowGraphAllocator::EliminateEnvironments() { | |
107 for (intptr_t i = 0; i < block_order_.length(); ++i) { | |
108 BlockEntryInstr* block = block_order_[i]; | |
109 for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) { | |
110 Instruction* current = it.Current(); | |
111 if (!current->CanDeoptimize()) current->RemoveEnvironment(); | |
112 } | |
113 } | |
114 } | |
115 | |
116 | |
117 void SSALivenessAnalysis::ComputeInitialSets() { | 105 void SSALivenessAnalysis::ComputeInitialSets() { |
118 const intptr_t block_count = postorder_.length(); | 106 const intptr_t block_count = postorder_.length(); |
119 for (intptr_t i = 0; i < block_count; i++) { | 107 for (intptr_t i = 0; i < block_count; i++) { |
120 BlockEntryInstr* block = postorder_[i]; | 108 BlockEntryInstr* block = postorder_[i]; |
121 | 109 |
122 BitVector* kill = kill_[i]; | 110 BitVector* kill = kill_[i]; |
123 BitVector* live_in = live_in_[i]; | 111 BitVector* live_in = live_in_[i]; |
124 | 112 |
125 // Iterate backwards starting at the last instruction. | 113 // Iterate backwards starting at the last instruction. |
126 for (BackwardInstructionIterator it(block); !it.Done(); it.Advance()) { | 114 for (BackwardInstructionIterator it(block); !it.Done(); it.Advance()) { |
(...skipping 18 matching lines...) Expand all Loading... |
145 | 133 |
146 live_in->Add(use); | 134 live_in->Add(use); |
147 } | 135 } |
148 | 136 |
149 // Add non-argument uses from the deoptimization environment (pushed | 137 // Add non-argument uses from the deoptimization environment (pushed |
150 // arguments are not allocated by the register allocator). | 138 // arguments are not allocated by the register allocator). |
151 if (current->env() != NULL) { | 139 if (current->env() != NULL) { |
152 for (Environment::DeepIterator env_it(current->env()); | 140 for (Environment::DeepIterator env_it(current->env()); |
153 !env_it.Done(); | 141 !env_it.Done(); |
154 env_it.Advance()) { | 142 env_it.Advance()) { |
155 Value* value = env_it.CurrentValue(); | 143 Definition* defn = env_it.CurrentValue()->definition(); |
156 if (!value->definition()->IsPushArgument() && | 144 if (defn->IsMaterializeObject()) { |
157 !value->BindsToConstant()) { | 145 // MaterializeObject instruction is not in the graph. |
158 live_in->Add(value->definition()->ssa_temp_index()); | 146 // Treat its inputs as part of the environment. |
| 147 for (intptr_t i = 0; i < defn->InputCount(); i++) { |
| 148 if (!defn->InputAt(i)->BindsToConstant()) { |
| 149 live_in->Add(defn->InputAt(i)->definition()->ssa_temp_index()); |
| 150 } |
| 151 } |
| 152 } else if (!defn->IsPushArgument() && !defn->IsConstant()) { |
| 153 live_in->Add(defn->ssa_temp_index()); |
159 } | 154 } |
160 } | 155 } |
161 } | 156 } |
162 } | 157 } |
163 | 158 |
164 // Handle phis. | 159 // Handle phis. |
165 if (block->IsJoinEntry()) { | 160 if (block->IsJoinEntry()) { |
166 JoinEntryInstr* join = block->AsJoinEntry(); | 161 JoinEntryInstr* join = block->AsJoinEntry(); |
167 for (PhiIterator it(join); !it.Done(); it.Advance()) { | 162 for (PhiIterator it(join); !it.Done(); it.Advance()) { |
168 PhiInstr* phi = it.Current(); | 163 PhiInstr* phi = it.Current(); |
(...skipping 566 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
735 locations[i] = Location::NoLocation(); | 730 locations[i] = Location::NoLocation(); |
736 continue; | 731 continue; |
737 } | 732 } |
738 | 733 |
739 ConstantInstr* constant = def->AsConstant(); | 734 ConstantInstr* constant = def->AsConstant(); |
740 if (constant != NULL) { | 735 if (constant != NULL) { |
741 locations[i] = Location::Constant(constant->value()); | 736 locations[i] = Location::Constant(constant->value()); |
742 continue; | 737 continue; |
743 } | 738 } |
744 | 739 |
| 740 MaterializeObjectInstr* mat = def->AsMaterializeObject(); |
| 741 if (mat != NULL) { |
| 742 // MaterializeObject itself produces no value. But its uses |
| 743 // are treated as part of the environment: allocated locations |
| 744 // will be used when building deoptimization data. |
| 745 locations[i] = Location::NoLocation(); |
| 746 ProcessMaterializationUses(block, block_start_pos, use_pos, mat); |
| 747 continue; |
| 748 } |
| 749 |
745 const intptr_t vreg = def->ssa_temp_index(); | 750 const intptr_t vreg = def->ssa_temp_index(); |
746 LiveRange* range = GetLiveRange(vreg); | 751 LiveRange* range = GetLiveRange(vreg); |
747 range->AddUseInterval(block_start_pos, use_pos); | 752 range->AddUseInterval(block_start_pos, use_pos); |
748 range->AddUse(use_pos, &locations[i]); | 753 range->AddUse(use_pos, &locations[i]); |
749 } | 754 } |
750 | 755 |
751 env->set_locations(locations); | 756 env->set_locations(locations); |
752 env = env->outer(); | 757 env = env->outer(); |
753 } | 758 } |
754 } | 759 } |
755 | 760 |
756 | 761 |
| 762 void FlowGraphAllocator::ProcessMaterializationUses( |
| 763 BlockEntryInstr* block, |
| 764 const intptr_t block_start_pos, |
| 765 const intptr_t use_pos, |
| 766 MaterializeObjectInstr* mat) { |
| 767 // Materialization can occur several times in the same environment. |
| 768 // Check if we already processed this one. |
| 769 if (mat->locations() != NULL) { |
| 770 return; // Already processed. |
| 771 } |
| 772 |
| 773 // Initialize location for every input of the MaterializeObject instruction. |
| 774 Location* locations = |
| 775 Isolate::Current()->current_zone()->Alloc<Location>(mat->InputCount()); |
| 776 |
| 777 for (intptr_t i = 0; i < mat->InputCount(); ++i) { |
| 778 Definition* def = mat->InputAt(i)->definition(); |
| 779 |
| 780 ConstantInstr* constant = def->AsConstant(); |
| 781 if (constant != NULL) { |
| 782 locations[i] = Location::Constant(constant->value()); |
| 783 continue; |
| 784 } |
| 785 |
| 786 locations[i] = Location::Any(); |
| 787 |
| 788 const intptr_t vreg = def->ssa_temp_index(); |
| 789 LiveRange* range = GetLiveRange(vreg); |
| 790 range->AddUseInterval(block_start_pos, use_pos); |
| 791 range->AddUse(use_pos, &locations[i]); |
| 792 } |
| 793 |
| 794 mat->set_locations(locations); |
| 795 } |
| 796 |
| 797 |
757 // Create and update live ranges corresponding to instruction's inputs, | 798 // Create and update live ranges corresponding to instruction's inputs, |
758 // temporaries and output. | 799 // temporaries and output. |
759 void FlowGraphAllocator::ProcessOneInstruction(BlockEntryInstr* block, | 800 void FlowGraphAllocator::ProcessOneInstruction(BlockEntryInstr* block, |
760 Instruction* current, | 801 Instruction* current, |
761 BitVector* interference_set) { | 802 BitVector* interference_set) { |
762 LocationSummary* locs = current->locs(); | 803 LocationSummary* locs = current->locs(); |
763 | 804 |
764 Definition* def = current->AsDefinition(); | 805 Definition* def = current->AsDefinition(); |
765 if ((def != NULL) && (def->AsConstant() != NULL)) { | 806 if ((def != NULL) && (def->AsConstant() != NULL)) { |
766 LiveRange* range = (def->ssa_temp_index() != -1) ? | 807 LiveRange* range = (def->ssa_temp_index() != -1) ? |
(...skipping 1661 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2428 value_representations_[def->ssa_temp_index()] = def->representation(); | 2469 value_representations_[def->ssa_temp_index()] = def->representation(); |
2429 } | 2470 } |
2430 } | 2471 } |
2431 } | 2472 } |
2432 } | 2473 } |
2433 | 2474 |
2434 | 2475 |
2435 void FlowGraphAllocator::AllocateRegisters() { | 2476 void FlowGraphAllocator::AllocateRegisters() { |
2436 CollectRepresentations(); | 2477 CollectRepresentations(); |
2437 | 2478 |
2438 EliminateEnvironments(); | |
2439 | |
2440 liveness_.Analyze(); | 2479 liveness_.Analyze(); |
2441 | 2480 |
2442 NumberInstructions(); | 2481 NumberInstructions(); |
2443 | 2482 |
2444 DiscoverLoops(); | 2483 DiscoverLoops(); |
2445 | 2484 |
2446 BuildLiveRanges(); | 2485 BuildLiveRanges(); |
2447 | 2486 |
2448 if (FLAG_print_ssa_liveness) { | 2487 if (FLAG_print_ssa_liveness) { |
2449 liveness_.Dump(); | 2488 liveness_.Dump(); |
(...skipping 50 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2500 OS::Print("-- [after ssa allocator] ir [%s] -------------\n", | 2539 OS::Print("-- [after ssa allocator] ir [%s] -------------\n", |
2501 function.ToFullyQualifiedCString()); | 2540 function.ToFullyQualifiedCString()); |
2502 FlowGraphPrinter printer(flow_graph_, true); | 2541 FlowGraphPrinter printer(flow_graph_, true); |
2503 printer.PrintBlocks(); | 2542 printer.PrintBlocks(); |
2504 OS::Print("----------------------------------------------\n"); | 2543 OS::Print("----------------------------------------------\n"); |
2505 } | 2544 } |
2506 } | 2545 } |
2507 | 2546 |
2508 | 2547 |
2509 } // namespace dart | 2548 } // namespace dart |
OLD | NEW |