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/longjump.h" | 10 #include "vm/longjump.h" |
(...skipping 504 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
515 } | 515 } |
516 | 516 |
517 // 2. Compute the immediate dominators as the nearest common ancestor of | 517 // 2. Compute the immediate dominators as the nearest common ancestor of |
518 // spanning tree parent and semidominator, for all blocks except the entry. | 518 // spanning tree parent and semidominator, for all blocks except the entry. |
519 for (intptr_t block_index = 1; block_index < size; ++block_index) { | 519 for (intptr_t block_index = 1; block_index < size; ++block_index) { |
520 intptr_t dom_index = idom[block_index]; | 520 intptr_t dom_index = idom[block_index]; |
521 while (dom_index > semi[block_index]) { | 521 while (dom_index > semi[block_index]) { |
522 dom_index = idom[dom_index]; | 522 dom_index = idom[dom_index]; |
523 } | 523 } |
524 idom[block_index] = dom_index; | 524 idom[block_index] = dom_index; |
525 preorder_[block_index]->set_dominator(preorder_[dom_index]); | |
526 preorder_[dom_index]->AddDominatedBlock(preorder_[block_index]); | 525 preorder_[dom_index]->AddDominatedBlock(preorder_[block_index]); |
527 } | 526 } |
528 | 527 |
529 // 3. Now compute the dominance frontier for all blocks. This is | 528 // 3. Now compute the dominance frontier for all blocks. This is |
530 // algorithm in "A Simple, Fast Dominance Algorithm" (Figure 5), which is | 529 // algorithm in "A Simple, Fast Dominance Algorithm" (Figure 5), which is |
531 // attributed to a paper by Ferrante et al. There is no bookkeeping | 530 // attributed to a paper by Ferrante et al. There is no bookkeeping |
532 // required to avoid adding a block twice to the same block's dominance | 531 // required to avoid adding a block twice to the same block's dominance |
533 // frontier because we use a set to represent the dominance frontier. | 532 // frontier because we use a set to represent the dominance frontier. |
534 for (intptr_t block_index = 0; block_index < size; ++block_index) { | 533 for (intptr_t block_index = 0; block_index < size; ++block_index) { |
535 BlockEntryInstr* block = preorder_[block_index]; | 534 BlockEntryInstr* block = preorder_[block_index]; |
(...skipping 304 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
840 } | 839 } |
841 } | 840 } |
842 | 841 |
843 for (BlockIterator it(postorder_iterator()); !it.Done(); it.Advance()) { | 842 for (BlockIterator it(postorder_iterator()); !it.Done(); it.Advance()) { |
844 JoinEntryInstr* join = it.Current()->AsJoinEntry(); | 843 JoinEntryInstr* join = it.Current()->AsJoinEntry(); |
845 if (join != NULL) join->RemoveDeadPhis(constant_null()); | 844 if (join != NULL) join->RemoveDeadPhis(constant_null()); |
846 } | 845 } |
847 } | 846 } |
848 | 847 |
849 | 848 |
| 849 void FlowGraph::RemoveRedefinitions() { |
| 850 // Remove redefinition instructions inserted to inhibit hoisting. |
| 851 for (BlockIterator block_it = reverse_postorder_iterator(); |
| 852 !block_it.Done(); |
| 853 block_it.Advance()) { |
| 854 for (ForwardInstructionIterator instr_it(block_it.Current()); |
| 855 !instr_it.Done(); |
| 856 instr_it.Advance()) { |
| 857 RedefinitionInstr* redefinition = instr_it.Current()->AsRedefinition(); |
| 858 if (redefinition != NULL) { |
| 859 Definition* original; |
| 860 do { |
| 861 original = redefinition->value()->definition(); |
| 862 } while (original->IsRedefinition()); |
| 863 redefinition->ReplaceUsesWith(original); |
| 864 instr_it.RemoveCurrentFromGraph(); |
| 865 } |
| 866 } |
| 867 } |
| 868 } |
| 869 |
| 870 |
850 // Find the natural loop for the back edge m->n and attach loop information | 871 // Find the natural loop for the back edge m->n and attach loop information |
851 // to block n (loop header). The algorithm is described in "Advanced Compiler | 872 // to block n (loop header). The algorithm is described in "Advanced Compiler |
852 // Design & Implementation" (Muchnick) p192. | 873 // Design & Implementation" (Muchnick) p192. |
853 static void FindLoop(BlockEntryInstr* m, | 874 static void FindLoop(BlockEntryInstr* m, |
854 BlockEntryInstr* n, | 875 BlockEntryInstr* n, |
855 intptr_t num_blocks) { | 876 intptr_t num_blocks) { |
856 GrowableArray<BlockEntryInstr*> stack; | 877 GrowableArray<BlockEntryInstr*> stack; |
857 BitVector* loop = new BitVector(num_blocks); | 878 BitVector* loop = new BitVector(num_blocks); |
858 | 879 |
859 loop->Add(n->preorder_number()); | 880 loop->Add(n->preorder_number()); |
(...skipping 171 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1031 } | 1052 } |
1032 | 1053 |
1033 | 1054 |
1034 bool BlockEffects::IsSideEffectFreePath(BlockEntryInstr* from, | 1055 bool BlockEffects::IsSideEffectFreePath(BlockEntryInstr* from, |
1035 BlockEntryInstr* to) const { | 1056 BlockEntryInstr* to) const { |
1036 return available_at_[to->postorder_number()]->Contains( | 1057 return available_at_[to->postorder_number()]->Contains( |
1037 from->postorder_number()); | 1058 from->postorder_number()); |
1038 } | 1059 } |
1039 | 1060 |
1040 } // namespace dart | 1061 } // namespace dart |
OLD | NEW |