| 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/intermediate_language.h" | 5 #include "vm/intermediate_language.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/object.h" | 9 #include "vm/object.h" |
| 9 #include "vm/os.h" | 10 #include "vm/os.h" |
| 10 #include "vm/scopes.h" | 11 #include "vm/scopes.h" |
| 11 | 12 |
| 12 namespace dart { | 13 namespace dart { |
| 13 | 14 |
| 14 // ==== Support for visiting flow graphs. | 15 // ==== Support for visiting flow graphs. |
| 15 #define DEFINE_ACCEPT(ShortName, ClassName) \ | 16 #define DEFINE_ACCEPT(ShortName, ClassName) \ |
| 16 void ClassName::Accept(FlowGraphVisitor* visitor) { \ | 17 void ClassName::Accept(FlowGraphVisitor* visitor) { \ |
| 17 visitor->Visit##ShortName(this); \ | 18 visitor->Visit##ShortName(this); \ |
| (...skipping 145 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 163 | 164 |
| 164 | 165 |
| 165 void BindInstr::RecordAssignedVars(BitVector* assigned_vars) { | 166 void BindInstr::RecordAssignedVars(BitVector* assigned_vars) { |
| 166 computation()->RecordAssignedVars(assigned_vars); | 167 computation()->RecordAssignedVars(assigned_vars); |
| 167 } | 168 } |
| 168 | 169 |
| 169 | 170 |
| 170 // ==== Postorder graph traversal. | 171 // ==== Postorder graph traversal. |
| 171 void GraphEntryInstr::DiscoverBlocks( | 172 void GraphEntryInstr::DiscoverBlocks( |
| 172 BlockEntryInstr* current_block, | 173 BlockEntryInstr* current_block, |
| 173 GrowableArray<BlockEntryInstr*>* preorder, | 174 FlowGraphBuilder* builder, |
| 174 GrowableArray<BlockEntryInstr*>* postorder, | |
| 175 GrowableArray<intptr_t>* parent, | 175 GrowableArray<intptr_t>* parent, |
| 176 GrowableArray<BitVector*>* assigned_vars, | 176 GrowableArray<BitVector*>* assigned_vars, |
| 177 intptr_t variable_count) { | 177 intptr_t variable_count) { |
| 178 GrowableArray<BlockEntryInstr*>* preorder = |
| 179 builder->preorder_block_entries(); |
| 180 GrowableArray<BlockEntryInstr*>* postorder = |
| 181 builder->postorder_block_entries(); |
| 178 // We only visit this block once, first of all blocks. | 182 // We only visit this block once, first of all blocks. |
| 179 ASSERT(preorder_number() == -1); | 183 ASSERT(preorder_number() == -1); |
| 180 ASSERT(current_block == NULL); | 184 ASSERT(current_block == NULL); |
| 181 ASSERT(preorder->is_empty()); | 185 ASSERT(preorder->is_empty()); |
| 182 ASSERT(postorder->is_empty()); | 186 ASSERT(postorder->is_empty()); |
| 183 ASSERT(parent->is_empty()); | 187 ASSERT(parent->is_empty()); |
| 184 | 188 |
| 185 // This node has no parent, indicated by -1. The preorder number is 0. | 189 // This node has no parent, indicated by -1. The preorder number is 0. |
| 186 parent->Add(-1); | 190 parent->Add(-1); |
| 187 set_preorder_number(0); | 191 set_preorder_number(0); |
| 188 preorder->Add(this); | 192 preorder->Add(this); |
| 189 BitVector* vars = | 193 BitVector* vars = |
| 190 (variable_count == 0) ? NULL : new BitVector(variable_count); | 194 (variable_count == 0) ? NULL : new BitVector(variable_count); |
| 191 assigned_vars->Add(vars); | 195 assigned_vars->Add(vars); |
| 192 | 196 |
| 193 // Iteratively traverse all successors. In the unoptimized code, we will | 197 // Iteratively traverse all successors. In the unoptimized code, we will |
| 194 // enter the function at the first successor in reverse postorder, so we | 198 // enter the function at the first successor in reverse postorder, so we |
| 195 // must visit the normal entry last. | 199 // must visit the normal entry last. |
| 196 for (intptr_t i = catch_entries_.length() - 1; i >= 0; --i) { | 200 for (intptr_t i = catch_entries_.length() - 1; i >= 0; --i) { |
| 197 catch_entries_[i]->DiscoverBlocks(this, preorder, postorder, parent, | 201 catch_entries_[i]->DiscoverBlocks( |
| 198 assigned_vars, variable_count); | 202 this, builder, parent, assigned_vars, variable_count); |
| 199 } | 203 } |
| 200 normal_entry_->DiscoverBlocks(this, preorder, postorder, parent, | 204 normal_entry_->DiscoverBlocks( |
| 201 assigned_vars, variable_count); | 205 this, builder, parent, assigned_vars, variable_count); |
| 202 | 206 |
| 203 // Assign postorder number. | 207 // Assign postorder number. |
| 204 set_postorder_number(postorder->length()); | 208 set_postorder_number(postorder->length()); |
| 205 postorder->Add(this); | 209 postorder->Add(this); |
| 206 } | 210 } |
| 207 | 211 |
| 208 | 212 |
| 209 // Base class implementation used for JoinEntry and TargetEntry. | 213 // Base class implementation used for JoinEntry and TargetEntry. |
| 210 void BlockEntryInstr::DiscoverBlocks( | 214 void BlockEntryInstr::DiscoverBlocks( |
| 211 BlockEntryInstr* current_block, | 215 BlockEntryInstr* current_block, |
| 212 GrowableArray<BlockEntryInstr*>* preorder, | 216 FlowGraphBuilder* builder, |
| 213 GrowableArray<BlockEntryInstr*>* postorder, | |
| 214 GrowableArray<intptr_t>* parent, | 217 GrowableArray<intptr_t>* parent, |
| 215 GrowableArray<BitVector*>* assigned_vars, | 218 GrowableArray<BitVector*>* assigned_vars, |
| 216 intptr_t variable_count) { | 219 intptr_t variable_count) { |
| 220 GrowableArray<BlockEntryInstr*>* preorder = |
| 221 builder->preorder_block_entries(); |
| 222 GrowableArray<BlockEntryInstr*>* postorder = |
| 223 builder->postorder_block_entries(); |
| 217 // We have already visited the graph entry, so we can assume current_block | 224 // We have already visited the graph entry, so we can assume current_block |
| 218 // is non-null and preorder array is non-empty. | 225 // is non-null and preorder array is non-empty. |
| 219 ASSERT(current_block != NULL); | 226 ASSERT(current_block != NULL); |
| 220 ASSERT(!preorder->is_empty()); | 227 ASSERT(!preorder->is_empty()); |
| 221 | 228 |
| 222 // 1. Record control-flow-graph basic-block predecessors. | 229 // 1. Record control-flow-graph basic-block predecessors. |
| 223 AddPredecessor(current_block); | 230 AddPredecessor(current_block); |
| 224 | 231 |
| 225 // 2. If the block has already been reached by the traversal, we are | 232 // 2. If the block has already been reached by the traversal, we are |
| 226 // done. Blocks with a single predecessor cannot have been reached | 233 // done. Blocks with a single predecessor cannot have been reached |
| (...skipping 24 matching lines...) Expand all Loading... |
| 251 if (next->IsBlockEntry()) { | 258 if (next->IsBlockEntry()) { |
| 252 set_last_instruction(this); | 259 set_last_instruction(this); |
| 253 } else { | 260 } else { |
| 254 while ((next != NULL) && !next->IsBlockEntry() && !next->IsBranch()) { | 261 while ((next != NULL) && !next->IsBlockEntry() && !next->IsBranch()) { |
| 255 if (vars != NULL) next->RecordAssignedVars(vars); | 262 if (vars != NULL) next->RecordAssignedVars(vars); |
| 256 set_last_instruction(next); | 263 set_last_instruction(next); |
| 257 next = next->StraightLineSuccessor(); | 264 next = next->StraightLineSuccessor(); |
| 258 } | 265 } |
| 259 } | 266 } |
| 260 if (next != NULL) { | 267 if (next != NULL) { |
| 261 next->DiscoverBlocks(this, preorder, postorder, parent, assigned_vars, | 268 next->DiscoverBlocks(this, builder, parent, assigned_vars, variable_count); |
| 262 variable_count); | |
| 263 } | 269 } |
| 264 | 270 |
| 265 // 6. Assign postorder number and add the block entry to the list. | 271 // 6. Assign postorder number and add the block entry to the list. |
| 266 set_postorder_number(postorder->length()); | 272 set_postorder_number(postorder->length()); |
| 267 postorder->Add(this); | 273 postorder->Add(this); |
| 268 } | 274 } |
| 269 | 275 |
| 270 | 276 |
| 271 void BranchInstr::DiscoverBlocks( | 277 void BranchInstr::DiscoverBlocks( |
| 272 BlockEntryInstr* current_block, | 278 BlockEntryInstr* current_block, |
| 273 GrowableArray<BlockEntryInstr*>* preorder, | 279 FlowGraphBuilder* builder, |
| 274 GrowableArray<BlockEntryInstr*>* postorder, | |
| 275 GrowableArray<intptr_t>* parent, | 280 GrowableArray<intptr_t>* parent, |
| 276 GrowableArray<BitVector*>* assigned_vars, | 281 GrowableArray<BitVector*>* assigned_vars, |
| 277 intptr_t variable_count) { | 282 intptr_t variable_count) { |
| 278 current_block->set_last_instruction(this); | 283 current_block->set_last_instruction(this); |
| 279 // Visit the false successor before the true successor so they appear in | 284 // Visit the false successor before the true successor so they appear in |
| 280 // true/false order in reverse postorder used as the block ordering in the | 285 // true/false order in reverse postorder used as the block ordering in the |
| 281 // nonoptimizing compiler. | 286 // nonoptimizing compiler. |
| 282 ASSERT(true_successor_ != NULL); | 287 ASSERT(true_successor_ != NULL); |
| 283 ASSERT(false_successor_ != NULL); | 288 ASSERT(false_successor_ != NULL); |
| 284 false_successor_->DiscoverBlocks(current_block, preorder, postorder, parent, | 289 false_successor_->DiscoverBlocks( |
| 285 assigned_vars, variable_count); | 290 current_block, builder, parent, assigned_vars, variable_count); |
| 286 true_successor_->DiscoverBlocks(current_block, preorder, postorder, parent, | 291 true_successor_->DiscoverBlocks( |
| 287 assigned_vars, variable_count); | 292 current_block, builder, parent, assigned_vars, variable_count); |
| 288 } | 293 } |
| 289 | 294 |
| 290 | 295 |
| 291 } // namespace dart | 296 } // namespace dart |
| OLD | NEW |