| 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 1045 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1056 instr_it.RemoveCurrentFromGraph(); | 1056 instr_it.RemoveCurrentFromGraph(); |
| 1057 } | 1057 } |
| 1058 } | 1058 } |
| 1059 } | 1059 } |
| 1060 } | 1060 } |
| 1061 | 1061 |
| 1062 | 1062 |
| 1063 // Find the natural loop for the back edge m->n and attach loop information | 1063 // Find the natural loop for the back edge m->n and attach loop information |
| 1064 // to block n (loop header). The algorithm is described in "Advanced Compiler | 1064 // to block n (loop header). The algorithm is described in "Advanced Compiler |
| 1065 // Design & Implementation" (Muchnick) p192. | 1065 // Design & Implementation" (Muchnick) p192. |
| 1066 BitVector* FlowGraph::FindLoop(BlockEntryInstr* m, BlockEntryInstr* n) { | 1066 BitVector* FlowGraph::FindLoop(BlockEntryInstr* m, BlockEntryInstr* n) const { |
| 1067 GrowableArray<BlockEntryInstr*> stack; | 1067 GrowableArray<BlockEntryInstr*> stack; |
| 1068 BitVector* loop = new(isolate()) BitVector(preorder_.length()); | 1068 BitVector* loop = new(isolate()) BitVector(preorder_.length()); |
| 1069 | 1069 |
| 1070 loop->Add(n->preorder_number()); | 1070 loop->Add(n->preorder_number()); |
| 1071 if (n != m) { | 1071 if (n != m) { |
| 1072 loop->Add(m->preorder_number()); | 1072 loop->Add(m->preorder_number()); |
| 1073 stack.Add(m); | 1073 stack.Add(m); |
| 1074 } | 1074 } |
| 1075 | 1075 |
| 1076 while (!stack.is_empty()) { | 1076 while (!stack.is_empty()) { |
| 1077 BlockEntryInstr* p = stack.RemoveLast(); | 1077 BlockEntryInstr* p = stack.RemoveLast(); |
| 1078 for (intptr_t i = 0; i < p->PredecessorCount(); ++i) { | 1078 for (intptr_t i = 0; i < p->PredecessorCount(); ++i) { |
| 1079 BlockEntryInstr* q = p->PredecessorAt(i); | 1079 BlockEntryInstr* q = p->PredecessorAt(i); |
| 1080 if (!loop->Contains(q->preorder_number())) { | 1080 if (!loop->Contains(q->preorder_number())) { |
| 1081 loop->Add(q->preorder_number()); | 1081 loop->Add(q->preorder_number()); |
| 1082 stack.Add(q); | 1082 stack.Add(q); |
| 1083 } | 1083 } |
| 1084 } | 1084 } |
| 1085 } | 1085 } |
| 1086 return loop; | 1086 return loop; |
| 1087 } | 1087 } |
| 1088 | 1088 |
| 1089 | 1089 |
| 1090 ZoneGrowableArray<BlockEntryInstr*>* FlowGraph::ComputeLoops() { | 1090 ZoneGrowableArray<BlockEntryInstr*>* FlowGraph::ComputeLoops() const { |
| 1091 ZoneGrowableArray<BlockEntryInstr*>* loop_headers = | 1091 ZoneGrowableArray<BlockEntryInstr*>* loop_headers = |
| 1092 new(isolate()) ZoneGrowableArray<BlockEntryInstr*>(); | 1092 new(isolate()) ZoneGrowableArray<BlockEntryInstr*>(); |
| 1093 | 1093 |
| 1094 for (BlockIterator it = postorder_iterator(); | 1094 for (BlockIterator it = postorder_iterator(); |
| 1095 !it.Done(); | 1095 !it.Done(); |
| 1096 it.Advance()) { | 1096 it.Advance()) { |
| 1097 BlockEntryInstr* block = it.Current(); | 1097 BlockEntryInstr* block = it.Current(); |
| 1098 for (intptr_t i = 0; i < block->PredecessorCount(); ++i) { | 1098 for (intptr_t i = 0; i < block->PredecessorCount(); ++i) { |
| 1099 BlockEntryInstr* pred = block->PredecessorAt(i); | 1099 BlockEntryInstr* pred = block->PredecessorAt(i); |
| 1100 if (block->Dominates(pred)) { | 1100 if (block->Dominates(pred)) { |
| (...skipping 20 matching lines...) Expand all Loading... |
| 1121 } | 1121 } |
| 1122 } | 1122 } |
| 1123 if (FLAG_trace_optimization) { | 1123 if (FLAG_trace_optimization) { |
| 1124 for (intptr_t i = 0; i < loop_headers->length(); ++i) { | 1124 for (intptr_t i = 0; i < loop_headers->length(); ++i) { |
| 1125 BlockEntryInstr* header = (*loop_headers)[i]; | 1125 BlockEntryInstr* header = (*loop_headers)[i]; |
| 1126 OS::Print("Loop header B%" Pd "\n", header->block_id()); | 1126 OS::Print("Loop header B%" Pd "\n", header->block_id()); |
| 1127 for (BitVector::Iterator it(header->loop_info()); | 1127 for (BitVector::Iterator it(header->loop_info()); |
| 1128 !it.Done(); | 1128 !it.Done(); |
| 1129 it.Advance()) { | 1129 it.Advance()) { |
| 1130 OS::Print(" B%" Pd "\n", preorder_[it.Current()]->block_id()); | 1130 OS::Print(" B%" Pd "\n", preorder_[it.Current()]->block_id()); |
| 1131 } | 1131 } |
| 1132 } | 1132 } |
| 1133 } | 1133 } |
| 1134 return loop_headers; | 1134 return loop_headers; |
| 1135 } | 1135 } |
| 1136 | 1136 |
| 1137 | 1137 |
| 1138 intptr_t FlowGraph::InstructionCount() const { | 1138 intptr_t FlowGraph::InstructionCount() const { |
| 1139 intptr_t size = 0; | 1139 intptr_t size = 0; |
| 1140 // Iterate each block, skipping the graph entry. | 1140 // Iterate each block, skipping the graph entry. |
| 1141 for (intptr_t i = 1; i < preorder_.length(); ++i) { | 1141 for (intptr_t i = 1; i < preorder_.length(); ++i) { |
| (...skipping 112 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1254 } | 1254 } |
| 1255 | 1255 |
| 1256 | 1256 |
| 1257 bool BlockEffects::IsSideEffectFreePath(BlockEntryInstr* from, | 1257 bool BlockEffects::IsSideEffectFreePath(BlockEntryInstr* from, |
| 1258 BlockEntryInstr* to) const { | 1258 BlockEntryInstr* to) const { |
| 1259 return available_at_[to->postorder_number()]->Contains( | 1259 return available_at_[to->postorder_number()]->Contains( |
| 1260 from->postorder_number()); | 1260 from->postorder_number()); |
| 1261 } | 1261 } |
| 1262 | 1262 |
| 1263 } // namespace dart | 1263 } // namespace dart |
| OLD | NEW |