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

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

Issue 587873003: Pass isolate to BitVector constructor. (Closed) Base URL: http://dart.googlecode.com/svn/branches/bleeding_edge/dart/
Patch Set: Created 6 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
« no previous file with comments | « runtime/vm/bit_vector_test.cc ('k') | runtime/vm/flow_graph_allocator.cc » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
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.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
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
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
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
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
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
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
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
OLDNEW
« no previous file with comments | « runtime/vm/bit_vector_test.cc ('k') | runtime/vm/flow_graph_allocator.cc » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698