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/cha.h" | 8 #include "vm/cha.h" |
9 #include "vm/flow_graph_builder.h" | 9 #include "vm/flow_graph_builder.h" |
10 #include "vm/flow_graph_compiler.h" | 10 #include "vm/flow_graph_compiler.h" |
(...skipping 22 matching lines...) Expand all Loading... |
33 num_copied_params_(parsed_function.num_copied_params()), | 33 num_copied_params_(parsed_function.num_copied_params()), |
34 num_non_copied_params_(parsed_function.num_non_copied_params()), | 34 num_non_copied_params_(parsed_function.num_non_copied_params()), |
35 graph_entry_(graph_entry), | 35 graph_entry_(graph_entry), |
36 preorder_(), | 36 preorder_(), |
37 postorder_(), | 37 postorder_(), |
38 reverse_postorder_(), | 38 reverse_postorder_(), |
39 optimized_block_order_(), | 39 optimized_block_order_(), |
40 constant_null_(NULL), | 40 constant_null_(NULL), |
41 constant_dead_(NULL), | 41 constant_dead_(NULL), |
42 constant_empty_context_(NULL), | 42 constant_empty_context_(NULL), |
43 block_effects_(NULL), | |
44 licm_allowed_(true), | 43 licm_allowed_(true), |
45 loop_headers_(NULL), | 44 loop_headers_(NULL), |
46 loop_invariant_loads_(NULL), | 45 loop_invariant_loads_(NULL), |
47 deferred_prefixes_(parsed_function.deferred_prefixes()), | 46 deferred_prefixes_(parsed_function.deferred_prefixes()), |
48 await_token_positions_(NULL), | 47 await_token_positions_(NULL), |
49 captured_parameters_(new (zone()) BitVector(zone(), variable_count())), | 48 captured_parameters_(new (zone()) BitVector(zone(), variable_count())), |
50 inlining_id_(-1) { | 49 inlining_id_(-1) { |
51 DiscoverBlocks(); | 50 DiscoverBlocks(); |
52 } | 51 } |
53 | 52 |
(...skipping 178 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
232 } | 231 } |
233 | 232 |
234 ASSERT(postorder_.length() == preorder_.length()); | 233 ASSERT(postorder_.length() == preorder_.length()); |
235 | 234 |
236 // Create an array of blocks in reverse postorder. | 235 // Create an array of blocks in reverse postorder. |
237 intptr_t block_count = postorder_.length(); | 236 intptr_t block_count = postorder_.length(); |
238 for (intptr_t i = 0; i < block_count; ++i) { | 237 for (intptr_t i = 0; i < block_count; ++i) { |
239 reverse_postorder_.Add(postorder_[block_count - i - 1]); | 238 reverse_postorder_.Add(postorder_[block_count - i - 1]); |
240 } | 239 } |
241 | 240 |
242 // Block effects are using postorder numbering. Discard computed information. | |
243 block_effects_ = NULL; | |
244 loop_headers_ = NULL; | 241 loop_headers_ = NULL; |
245 loop_invariant_loads_ = NULL; | 242 loop_invariant_loads_ = NULL; |
246 } | 243 } |
247 | 244 |
248 void FlowGraph::MergeBlocks() { | 245 void FlowGraph::MergeBlocks() { |
249 bool changed = false; | 246 bool changed = false; |
250 BitVector* merged = new (zone()) BitVector(zone(), postorder().length()); | 247 BitVector* merged = new (zone()) BitVector(zone(), postorder().length()); |
251 for (BlockIterator block_it = reverse_postorder_iterator(); !block_it.Done(); | 248 for (BlockIterator block_it = reverse_postorder_iterator(); !block_it.Done(); |
252 block_it.Advance()) { | 249 block_it.Advance()) { |
253 BlockEntryInstr* block = block_it.Current(); | 250 BlockEntryInstr* block = block_it.Current(); |
(...skipping 1153 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1407 // Iterate each block, skipping the graph entry. | 1404 // Iterate each block, skipping the graph entry. |
1408 for (intptr_t i = 1; i < preorder_.length(); ++i) { | 1405 for (intptr_t i = 1; i < preorder_.length(); ++i) { |
1409 for (ForwardInstructionIterator it(preorder_[i]); !it.Done(); | 1406 for (ForwardInstructionIterator it(preorder_[i]); !it.Done(); |
1410 it.Advance()) { | 1407 it.Advance()) { |
1411 ++size; | 1408 ++size; |
1412 } | 1409 } |
1413 } | 1410 } |
1414 return size; | 1411 return size; |
1415 } | 1412 } |
1416 | 1413 |
1417 void FlowGraph::ComputeBlockEffects() { | |
1418 block_effects_ = new (zone()) BlockEffects(this); | |
1419 } | |
1420 | |
1421 BlockEffects::BlockEffects(FlowGraph* flow_graph) | |
1422 : available_at_(flow_graph->postorder().length()) { | |
1423 // We are tracking a single effect. | |
1424 ASSERT(EffectSet::kLastEffect == 1); | |
1425 Zone* zone = flow_graph->zone(); | |
1426 const intptr_t block_count = flow_graph->postorder().length(); | |
1427 | |
1428 // Set of blocks that contain side-effects. | |
1429 BitVector* kill = new (zone) BitVector(zone, block_count); | |
1430 | |
1431 // Per block available-after sets. Block A is available after the block B if | |
1432 // and only if A is either equal to B or A is available at B and B contains no | |
1433 // side-effects. Initially we consider all blocks available after all other | |
1434 // blocks. | |
1435 GrowableArray<BitVector*> available_after(block_count); | |
1436 | |
1437 // Discover all blocks with side-effects. | |
1438 for (BlockIterator it = flow_graph->postorder_iterator(); !it.Done(); | |
1439 it.Advance()) { | |
1440 available_at_.Add(NULL); | |
1441 available_after.Add(NULL); | |
1442 | |
1443 BlockEntryInstr* block = it.Current(); | |
1444 for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) { | |
1445 if (it.Current()->HasUnknownSideEffects()) { | |
1446 kill->Add(block->postorder_number()); | |
1447 break; | |
1448 } | |
1449 } | |
1450 } | |
1451 | |
1452 BitVector* temp = new (zone) BitVector(zone, block_count); | |
1453 | |
1454 // Recompute available-at based on predecessors' available-after until the fix | |
1455 // point is reached. | |
1456 bool changed; | |
1457 do { | |
1458 changed = false; | |
1459 | |
1460 for (BlockIterator it = flow_graph->reverse_postorder_iterator(); | |
1461 !it.Done(); it.Advance()) { | |
1462 BlockEntryInstr* block = it.Current(); | |
1463 const intptr_t block_num = block->postorder_number(); | |
1464 | |
1465 if (block->IsGraphEntry()) { | |
1466 temp->Clear(); // Nothing is live-in into graph entry. | |
1467 } else { | |
1468 // Available-at is an intersection of all predecessors' available-after | |
1469 // sets. | |
1470 temp->SetAll(); | |
1471 for (intptr_t i = 0; i < block->PredecessorCount(); i++) { | |
1472 const intptr_t pred = block->PredecessorAt(i)->postorder_number(); | |
1473 if (available_after[pred] != NULL) { | |
1474 temp->Intersect(available_after[pred]); | |
1475 } | |
1476 } | |
1477 } | |
1478 | |
1479 BitVector* current = available_at_[block_num]; | |
1480 if ((current == NULL) || !current->Equals(*temp)) { | |
1481 // Available-at changed: update it and recompute available-after. | |
1482 if (available_at_[block_num] == NULL) { | |
1483 current = available_at_[block_num] = | |
1484 new (zone) BitVector(zone, block_count); | |
1485 available_after[block_num] = new (zone) BitVector(zone, block_count); | |
1486 // Block is always available after itself. | |
1487 available_after[block_num]->Add(block_num); | |
1488 } | |
1489 current->CopyFrom(temp); | |
1490 if (!kill->Contains(block_num)) { | |
1491 available_after[block_num]->CopyFrom(temp); | |
1492 // Block is always available after itself. | |
1493 available_after[block_num]->Add(block_num); | |
1494 } | |
1495 changed = true; | |
1496 } | |
1497 } | |
1498 } while (changed); | |
1499 } | |
1500 | |
1501 bool BlockEffects::IsAvailableAt(Instruction* instr, | |
1502 BlockEntryInstr* block) const { | |
1503 ASSERT(instr->AllowsCSE()); | |
1504 ASSERT(instr->Dependencies().IsNone()); | |
1505 return true; // TODO(dartbug.com/30474): cleanup | |
1506 } | |
1507 | |
1508 bool BlockEffects::CanBeMovedTo(Instruction* instr, | |
1509 BlockEntryInstr* block) const { | |
1510 ASSERT(instr->AllowsCSE()); | |
1511 ASSERT(instr->Dependencies().IsNone()); | |
1512 return true; // TODO(dartbug.com/30474): cleanup | |
1513 } | |
1514 | |
1515 bool BlockEffects::IsSideEffectFreePath(BlockEntryInstr* from, | |
1516 BlockEntryInstr* to) const { | |
1517 return available_at_[to->postorder_number()]->Contains( | |
1518 from->postorder_number()); | |
1519 } | |
1520 | |
1521 // Quick access to the current zone. | 1414 // Quick access to the current zone. |
1522 #define Z (zone()) | 1415 #define Z (zone()) |
1523 | 1416 |
1524 void FlowGraph::ConvertUse(Value* use, Representation from_rep) { | 1417 void FlowGraph::ConvertUse(Value* use, Representation from_rep) { |
1525 const Representation to_rep = | 1418 const Representation to_rep = |
1526 use->instruction()->RequiredInputRepresentation(use->use_index()); | 1419 use->instruction()->RequiredInputRepresentation(use->use_index()); |
1527 if (from_rep == to_rep || to_rep == kNoRepresentation) { | 1420 if (from_rep == to_rep || to_rep == kNoRepresentation) { |
1528 return; | 1421 return; |
1529 } | 1422 } |
1530 InsertConversion(from_rep, to_rep, use, /*is_environment_use=*/false); | 1423 InsertConversion(from_rep, to_rep, use, /*is_environment_use=*/false); |
(...skipping 735 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2266 intptr_t index, | 2159 intptr_t index, |
2267 Representation rep, | 2160 Representation rep, |
2268 intptr_t cid) { | 2161 intptr_t cid) { |
2269 ExtractNthOutputInstr* extract = | 2162 ExtractNthOutputInstr* extract = |
2270 new (Z) ExtractNthOutputInstr(new (Z) Value(instr), index, rep, cid); | 2163 new (Z) ExtractNthOutputInstr(new (Z) Value(instr), index, rep, cid); |
2271 instr->ReplaceUsesWith(extract); | 2164 instr->ReplaceUsesWith(extract); |
2272 InsertAfter(instr, extract, NULL, FlowGraph::kValue); | 2165 InsertAfter(instr, extract, NULL, FlowGraph::kValue); |
2273 } | 2166 } |
2274 | 2167 |
2275 } // namespace dart | 2168 } // namespace dart |
OLD | NEW |