| 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.h" | 5 #include "vm/flow_graph.h" |
| 6 | 6 |
| 7 #include "vm/bit_vector.h" | 7 #include "vm/bit_vector.h" |
| 8 #include "vm/flow_graph_builder.h" | 8 #include "vm/flow_graph_builder.h" |
| 9 #include "vm/intermediate_language.h" | 9 #include "vm/intermediate_language.h" |
| 10 #include "vm/growable_array.h" | 10 #include "vm/growable_array.h" |
| (...skipping 320 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 331 changed = true; | 331 changed = true; |
| 332 } | 332 } |
| 333 } | 333 } |
| 334 } while (changed); | 334 } while (changed); |
| 335 } | 335 } |
| 336 | 336 |
| 337 | 337 |
| 338 void LivenessAnalysis::Analyze() { | 338 void LivenessAnalysis::Analyze() { |
| 339 const intptr_t block_count = postorder_.length(); | 339 const intptr_t block_count = postorder_.length(); |
| 340 for (intptr_t i = 0; i < block_count; i++) { | 340 for (intptr_t i = 0; i < block_count; i++) { |
| 341 live_out_.Add(new(isolate()) BitVector(variable_count_)); | 341 live_out_.Add(new(isolate()) BitVector(isolate(), variable_count_)); |
| 342 kill_.Add(new(isolate()) BitVector(variable_count_)); | 342 kill_.Add(new(isolate()) BitVector(isolate(), variable_count_)); |
| 343 live_in_.Add(new(isolate()) BitVector(variable_count_)); | 343 live_in_.Add(new(isolate()) BitVector(isolate(), variable_count_)); |
| 344 } | 344 } |
| 345 | 345 |
| 346 ComputeInitialSets(); | 346 ComputeInitialSets(); |
| 347 ComputeLiveInAndLiveOutSets(); | 347 ComputeLiveInAndLiveOutSets(); |
| 348 } | 348 } |
| 349 | 349 |
| 350 | 350 |
| 351 static void PrintBitVector(const char* tag, BitVector* v) { | 351 static void PrintBitVector(const char* tag, BitVector* v) { |
| 352 OS::Print("%s:", tag); | 352 OS::Print("%s:", tag); |
| 353 for (BitVector::Iterator it(v); !it.Done(); it.Advance()) { | 353 for (BitVector::Iterator it(v); !it.Done(); it.Advance()) { |
| (...skipping 90 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 444 | 444 |
| 445 const FlowGraph* flow_graph_; | 445 const FlowGraph* flow_graph_; |
| 446 const intptr_t num_non_copied_params_; | 446 const intptr_t num_non_copied_params_; |
| 447 GrowableArray<BitVector*> assigned_vars_; | 447 GrowableArray<BitVector*> assigned_vars_; |
| 448 }; | 448 }; |
| 449 | 449 |
| 450 | 450 |
| 451 void VariableLivenessAnalysis::ComputeInitialSets() { | 451 void VariableLivenessAnalysis::ComputeInitialSets() { |
| 452 const intptr_t block_count = postorder_.length(); | 452 const intptr_t block_count = postorder_.length(); |
| 453 | 453 |
| 454 BitVector* last_loads = new(isolate()) BitVector(variable_count_); | 454 BitVector* last_loads = new(isolate()) BitVector(isolate(), variable_count_); |
| 455 for (intptr_t i = 0; i < block_count; i++) { | 455 for (intptr_t i = 0; i < block_count; i++) { |
| 456 BlockEntryInstr* block = postorder_[i]; | 456 BlockEntryInstr* block = postorder_[i]; |
| 457 | 457 |
| 458 BitVector* kill = kill_[i]; | 458 BitVector* kill = kill_[i]; |
| 459 BitVector* live_in = live_in_[i]; | 459 BitVector* live_in = live_in_[i]; |
| 460 last_loads->Clear(); | 460 last_loads->Clear(); |
| 461 | 461 |
| 462 // There is an implicit use (load-local) of every local variable at each | 462 // There is an implicit use (load-local) of every local variable at each |
| 463 // call inside a try{} block and every call has an implicit control-flow | 463 // call inside a try{} block and every call has an implicit control-flow |
| 464 // to the catch entry. As an approximation we mark all locals as live | 464 // to the catch entry. As an approximation we mark all locals as live |
| (...skipping 103 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 568 // Use a link-eval data structure with path compression. Implement path | 568 // Use a link-eval data structure with path compression. Implement path |
| 569 // compression in place by mutating the parent array. Each block has a | 569 // compression in place by mutating the parent array. Each block has a |
| 570 // label, which is the minimum block number on the compressed path. | 570 // label, which is the minimum block number on the compressed path. |
| 571 | 571 |
| 572 // Initialize idom, semi, and label used by SEMI-NCA. Initialize the | 572 // Initialize idom, semi, and label used by SEMI-NCA. Initialize the |
| 573 // dominance frontier output array. | 573 // dominance frontier output array. |
| 574 for (intptr_t i = 0; i < size; ++i) { | 574 for (intptr_t i = 0; i < size; ++i) { |
| 575 idom.Add(parent_[i]); | 575 idom.Add(parent_[i]); |
| 576 semi.Add(i); | 576 semi.Add(i); |
| 577 label.Add(i); | 577 label.Add(i); |
| 578 dominance_frontier->Add(new(isolate()) BitVector(size)); | 578 dominance_frontier->Add(new(isolate()) BitVector(isolate(), size)); |
| 579 } | 579 } |
| 580 | 580 |
| 581 // Loop over the blocks in reverse preorder (not including the graph | 581 // Loop over the blocks in reverse preorder (not including the graph |
| 582 // entry). Clear the dominated blocks in the graph entry in case | 582 // entry). Clear the dominated blocks in the graph entry in case |
| 583 // ComputeDominators is used to recompute them. | 583 // ComputeDominators is used to recompute them. |
| 584 preorder_[0]->ClearDominatedBlocks(); | 584 preorder_[0]->ClearDominatedBlocks(); |
| 585 for (intptr_t block_index = size - 1; block_index >= 1; --block_index) { | 585 for (intptr_t block_index = size - 1; block_index >= 1; --block_index) { |
| 586 // Loop over the predecessors. | 586 // Loop over the predecessors. |
| 587 BlockEntryInstr* block = preorder_[block_index]; | 587 BlockEntryInstr* block = preorder_[block_index]; |
| 588 // Clear the immediately dominated blocks in case ComputeDominators is | 588 // Clear the immediately dominated blocks in case ComputeDominators is |
| (...skipping 470 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1059 } | 1059 } |
| 1060 } | 1060 } |
| 1061 } | 1061 } |
| 1062 | 1062 |
| 1063 | 1063 |
| 1064 // Find the natural loop for the back edge m->n and attach loop information | 1064 // Find the natural loop for the back edge m->n and attach loop information |
| 1065 // to block n (loop header). The algorithm is described in "Advanced Compiler | 1065 // to block n (loop header). The algorithm is described in "Advanced Compiler |
| 1066 // Design & Implementation" (Muchnick) p192. | 1066 // Design & Implementation" (Muchnick) p192. |
| 1067 BitVector* FlowGraph::FindLoop(BlockEntryInstr* m, BlockEntryInstr* n) const { | 1067 BitVector* FlowGraph::FindLoop(BlockEntryInstr* m, BlockEntryInstr* n) const { |
| 1068 GrowableArray<BlockEntryInstr*> stack; | 1068 GrowableArray<BlockEntryInstr*> stack; |
| 1069 BitVector* loop = new(isolate()) BitVector(preorder_.length()); | 1069 BitVector* loop = new(isolate()) BitVector(isolate(), preorder_.length()); |
| 1070 | 1070 |
| 1071 loop->Add(n->preorder_number()); | 1071 loop->Add(n->preorder_number()); |
| 1072 if (n != m) { | 1072 if (n != m) { |
| 1073 loop->Add(m->preorder_number()); | 1073 loop->Add(m->preorder_number()); |
| 1074 stack.Add(m); | 1074 stack.Add(m); |
| 1075 } | 1075 } |
| 1076 | 1076 |
| 1077 while (!stack.is_empty()) { | 1077 while (!stack.is_empty()) { |
| 1078 BlockEntryInstr* p = stack.RemoveLast(); | 1078 BlockEntryInstr* p = stack.RemoveLast(); |
| 1079 for (intptr_t i = 0; i < p->PredecessorCount(); ++i) { | 1079 for (intptr_t i = 0; i < p->PredecessorCount(); ++i) { |
| (...skipping 76 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1156 | 1156 |
| 1157 | 1157 |
| 1158 BlockEffects::BlockEffects(FlowGraph* flow_graph) | 1158 BlockEffects::BlockEffects(FlowGraph* flow_graph) |
| 1159 : available_at_(flow_graph->postorder().length()) { | 1159 : available_at_(flow_graph->postorder().length()) { |
| 1160 // We are tracking a single effect. | 1160 // We are tracking a single effect. |
| 1161 ASSERT(EffectSet::kLastEffect == 1); | 1161 ASSERT(EffectSet::kLastEffect == 1); |
| 1162 Isolate* isolate = flow_graph->isolate(); | 1162 Isolate* isolate = flow_graph->isolate(); |
| 1163 const intptr_t block_count = flow_graph->postorder().length(); | 1163 const intptr_t block_count = flow_graph->postorder().length(); |
| 1164 | 1164 |
| 1165 // Set of blocks that contain side-effects. | 1165 // Set of blocks that contain side-effects. |
| 1166 BitVector* kill = new(isolate) BitVector(block_count); | 1166 BitVector* kill = new(isolate) BitVector(isolate, block_count); |
| 1167 | 1167 |
| 1168 // Per block available-after sets. Block A is available after the block B if | 1168 // Per block available-after sets. Block A is available after the block B if |
| 1169 // and only if A is either equal to B or A is available at B and B contains no | 1169 // and only if A is either equal to B or A is available at B and B contains no |
| 1170 // side-effects. Initially we consider all blocks available after all other | 1170 // side-effects. Initially we consider all blocks available after all other |
| 1171 // blocks. | 1171 // blocks. |
| 1172 GrowableArray<BitVector*> available_after(block_count); | 1172 GrowableArray<BitVector*> available_after(block_count); |
| 1173 | 1173 |
| 1174 // Discover all blocks with side-effects. | 1174 // Discover all blocks with side-effects. |
| 1175 for (BlockIterator it = flow_graph->postorder_iterator(); | 1175 for (BlockIterator it = flow_graph->postorder_iterator(); |
| 1176 !it.Done(); | 1176 !it.Done(); |
| 1177 it.Advance()) { | 1177 it.Advance()) { |
| 1178 available_at_.Add(NULL); | 1178 available_at_.Add(NULL); |
| 1179 available_after.Add(NULL); | 1179 available_after.Add(NULL); |
| 1180 | 1180 |
| 1181 BlockEntryInstr* block = it.Current(); | 1181 BlockEntryInstr* block = it.Current(); |
| 1182 for (ForwardInstructionIterator it(block); | 1182 for (ForwardInstructionIterator it(block); |
| 1183 !it.Done(); | 1183 !it.Done(); |
| 1184 it.Advance()) { | 1184 it.Advance()) { |
| 1185 if (!it.Current()->Effects().IsNone()) { | 1185 if (!it.Current()->Effects().IsNone()) { |
| 1186 kill->Add(block->postorder_number()); | 1186 kill->Add(block->postorder_number()); |
| 1187 break; | 1187 break; |
| 1188 } | 1188 } |
| 1189 } | 1189 } |
| 1190 } | 1190 } |
| 1191 | 1191 |
| 1192 BitVector* temp = new(isolate) BitVector(block_count); | 1192 BitVector* temp = new(isolate) BitVector(isolate, block_count); |
| 1193 | 1193 |
| 1194 // Recompute available-at based on predecessors' available-after until the fix | 1194 // Recompute available-at based on predecessors' available-after until the fix |
| 1195 // point is reached. | 1195 // point is reached. |
| 1196 bool changed; | 1196 bool changed; |
| 1197 do { | 1197 do { |
| 1198 changed = false; | 1198 changed = false; |
| 1199 | 1199 |
| 1200 for (BlockIterator it = flow_graph->reverse_postorder_iterator(); | 1200 for (BlockIterator it = flow_graph->reverse_postorder_iterator(); |
| 1201 !it.Done(); | 1201 !it.Done(); |
| 1202 it.Advance()) { | 1202 it.Advance()) { |
| (...skipping 12 matching lines...) Expand all Loading... |
| 1215 temp->Intersect(available_after[pred]); | 1215 temp->Intersect(available_after[pred]); |
| 1216 } | 1216 } |
| 1217 } | 1217 } |
| 1218 } | 1218 } |
| 1219 | 1219 |
| 1220 BitVector* current = available_at_[block_num]; | 1220 BitVector* current = available_at_[block_num]; |
| 1221 if ((current == NULL) || !current->Equals(*temp)) { | 1221 if ((current == NULL) || !current->Equals(*temp)) { |
| 1222 // Available-at changed: update it and recompute available-after. | 1222 // Available-at changed: update it and recompute available-after. |
| 1223 if (available_at_[block_num] == NULL) { | 1223 if (available_at_[block_num] == NULL) { |
| 1224 current = available_at_[block_num] = | 1224 current = available_at_[block_num] = |
| 1225 new(isolate) BitVector(block_count); | 1225 new(isolate) BitVector(isolate, block_count); |
| 1226 available_after[block_num] = | 1226 available_after[block_num] = |
| 1227 new(isolate) BitVector(block_count); | 1227 new(isolate) BitVector(isolate, block_count); |
| 1228 // Block is always available after itself. | 1228 // Block is always available after itself. |
| 1229 available_after[block_num]->Add(block_num); | 1229 available_after[block_num]->Add(block_num); |
| 1230 } | 1230 } |
| 1231 current->CopyFrom(temp); | 1231 current->CopyFrom(temp); |
| 1232 if (!kill->Contains(block_num)) { | 1232 if (!kill->Contains(block_num)) { |
| 1233 available_after[block_num]->CopyFrom(temp); | 1233 available_after[block_num]->CopyFrom(temp); |
| 1234 // Block is always available after itself. | 1234 // Block is always available after itself. |
| 1235 available_after[block_num]->Add(block_num); | 1235 available_after[block_num]->Add(block_num); |
| 1236 } | 1236 } |
| 1237 changed = true; | 1237 changed = true; |
| (...skipping 17 matching lines...) Expand all Loading... |
| 1255 } | 1255 } |
| 1256 | 1256 |
| 1257 | 1257 |
| 1258 bool BlockEffects::IsSideEffectFreePath(BlockEntryInstr* from, | 1258 bool BlockEffects::IsSideEffectFreePath(BlockEntryInstr* from, |
| 1259 BlockEntryInstr* to) const { | 1259 BlockEntryInstr* to) const { |
| 1260 return available_at_[to->postorder_number()]->Contains( | 1260 return available_at_[to->postorder_number()]->Contains( |
| 1261 from->postorder_number()); | 1261 from->postorder_number()); |
| 1262 } | 1262 } |
| 1263 | 1263 |
| 1264 } // namespace dart | 1264 } // namespace dart |
| OLD | NEW |