| 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 937 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 948 instr_it.RemoveCurrentFromGraph(); | 948 instr_it.RemoveCurrentFromGraph(); |
| 949 } | 949 } |
| 950 } | 950 } |
| 951 } | 951 } |
| 952 } | 952 } |
| 953 | 953 |
| 954 | 954 |
| 955 // Find the natural loop for the back edge m->n and attach loop information | 955 // Find the natural loop for the back edge m->n and attach loop information |
| 956 // to block n (loop header). The algorithm is described in "Advanced Compiler | 956 // to block n (loop header). The algorithm is described in "Advanced Compiler |
| 957 // Design & Implementation" (Muchnick) p192. | 957 // Design & Implementation" (Muchnick) p192. |
| 958 static void FindLoop(BlockEntryInstr* m, | 958 void FlowGraph::FindLoop(BlockEntryInstr* m, BlockEntryInstr* n) { |
| 959 BlockEntryInstr* n, | |
| 960 intptr_t num_blocks) { | |
| 961 GrowableArray<BlockEntryInstr*> stack; | 959 GrowableArray<BlockEntryInstr*> stack; |
| 962 BitVector* loop = new BitVector(num_blocks); | 960 BitVector* loop = new BitVector(preorder_.length()); |
| 963 | 961 |
| 964 loop->Add(n->preorder_number()); | 962 loop->Add(n->preorder_number()); |
| 965 if (n != m) { | 963 if (n != m) { |
| 966 loop->Add(m->preorder_number()); | 964 loop->Add(m->preorder_number()); |
| 967 stack.Add(m); | 965 stack.Add(m); |
| 968 } | 966 } |
| 969 | 967 |
| 970 while (!stack.is_empty()) { | 968 while (!stack.is_empty()) { |
| 971 BlockEntryInstr* p = stack.RemoveLast(); | 969 BlockEntryInstr* p = stack.RemoveLast(); |
| 972 for (intptr_t i = 0; i < p->PredecessorCount(); ++i) { | 970 for (intptr_t i = 0; i < p->PredecessorCount(); ++i) { |
| 973 BlockEntryInstr* q = p->PredecessorAt(i); | 971 BlockEntryInstr* q = p->PredecessorAt(i); |
| 974 if (!loop->Contains(q->preorder_number())) { | 972 if (!loop->Contains(q->preorder_number())) { |
| 975 loop->Add(q->preorder_number()); | 973 loop->Add(q->preorder_number()); |
| 976 stack.Add(q); | 974 stack.Add(q); |
| 977 } | 975 } |
| 978 } | 976 } |
| 979 } | 977 } |
| 980 n->set_loop_info(loop); | 978 n->set_loop_info(loop); |
| 981 if (FLAG_trace_optimization) { | 979 if (FLAG_trace_optimization) { |
| 982 for (BitVector::Iterator it(loop); !it.Done(); it.Advance()) { | 980 for (BitVector::Iterator it(loop); !it.Done(); it.Advance()) { |
| 983 OS::Print(" B%"Pd"\n", it.Current()); | 981 OS::Print(" B%"Pd"\n", preorder_[it.Current()]->block_id()); |
| 984 } | 982 } |
| 985 } | 983 } |
| 986 } | 984 } |
| 987 | 985 |
| 988 | 986 |
| 989 ZoneGrowableArray<BlockEntryInstr*>* FlowGraph::ComputeLoops() { | 987 ZoneGrowableArray<BlockEntryInstr*>* FlowGraph::ComputeLoops() { |
| 990 ZoneGrowableArray<BlockEntryInstr*>* loop_headers = | 988 ZoneGrowableArray<BlockEntryInstr*>* loop_headers = |
| 991 new ZoneGrowableArray<BlockEntryInstr*>(); | 989 new ZoneGrowableArray<BlockEntryInstr*>(); |
| 992 | 990 |
| 993 for (BlockIterator it = postorder_iterator(); | 991 for (BlockIterator it = postorder_iterator(); |
| 994 !it.Done(); | 992 !it.Done(); |
| 995 it.Advance()) { | 993 it.Advance()) { |
| 996 BlockEntryInstr* block = it.Current(); | 994 BlockEntryInstr* block = it.Current(); |
| 997 for (intptr_t i = 0; i < block->PredecessorCount(); ++i) { | 995 for (intptr_t i = 0; i < block->PredecessorCount(); ++i) { |
| 998 BlockEntryInstr* pred = block->PredecessorAt(i); | 996 BlockEntryInstr* pred = block->PredecessorAt(i); |
| 999 if (block->Dominates(pred)) { | 997 if (block->Dominates(pred)) { |
| 1000 if (FLAG_trace_optimization) { | 998 if (FLAG_trace_optimization) { |
| 1001 OS::Print("Back edge B%"Pd" -> B%"Pd"\n", pred->block_id(), | 999 OS::Print("Back edge B%"Pd" -> B%"Pd"\n", pred->block_id(), |
| 1002 block->block_id()); | 1000 block->block_id()); |
| 1003 } | 1001 } |
| 1004 FindLoop(pred, block, preorder_.length()); | 1002 FindLoop(pred, block); |
| 1005 loop_headers->Add(block); | 1003 loop_headers->Add(block); |
| 1006 } | 1004 } |
| 1007 } | 1005 } |
| 1008 } | 1006 } |
| 1009 | 1007 |
| 1010 return loop_headers; | 1008 return loop_headers; |
| 1011 } | 1009 } |
| 1012 | 1010 |
| 1013 | 1011 |
| 1014 void FlowGraph::Bailout(const char* reason) const { | 1012 void FlowGraph::Bailout(const char* reason) const { |
| (...skipping 125 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1140 } | 1138 } |
| 1141 | 1139 |
| 1142 | 1140 |
| 1143 bool BlockEffects::IsSideEffectFreePath(BlockEntryInstr* from, | 1141 bool BlockEffects::IsSideEffectFreePath(BlockEntryInstr* from, |
| 1144 BlockEntryInstr* to) const { | 1142 BlockEntryInstr* to) const { |
| 1145 return available_at_[to->postorder_number()]->Contains( | 1143 return available_at_[to->postorder_number()]->Contains( |
| 1146 from->postorder_number()); | 1144 from->postorder_number()); |
| 1147 } | 1145 } |
| 1148 | 1146 |
| 1149 } // namespace dart | 1147 } // namespace dart |
| OLD | NEW |