Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(11)

Side by Side Diff: runtime/vm/flow_graph_allocator.cc

Issue 10891025: Eliminate class UseVal. (Closed) Base URL: https://dart.googlecode.com/svn/branches/bleeding_edge/dart
Patch Set: Created 8 years, 3 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch | Annotate | Revision Log
OLDNEW
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
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
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
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
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
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
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
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
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
OLDNEW

Powered by Google App Engine
This is Rietveld 408576698