| 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" |
| 11 #include "vm/growable_array.h" | 11 #include "vm/growable_array.h" |
| 12 | 12 |
| 13 namespace dart { | 13 namespace dart { |
| 14 | 14 |
| 15 DECLARE_FLAG(bool, trace_optimization); | 15 DECLARE_FLAG(bool, trace_optimization); |
| 16 | 16 |
| 17 FlowGraph::FlowGraph(const FlowGraphBuilder& builder, | 17 FlowGraph::FlowGraph(const FlowGraphBuilder& builder, |
| 18 GraphEntryInstr* graph_entry) | 18 GraphEntryInstr* graph_entry) |
| 19 : parent_(), | 19 : parent_(), |
| 20 assigned_vars_(), | 20 assigned_vars_(), |
| 21 current_ssa_temp_index_(0), | 21 current_ssa_temp_index_(0), |
| 22 parsed_function_(builder.parsed_function()), | 22 parsed_function_(builder.parsed_function()), |
| 23 copied_parameter_count_(builder.copied_parameter_count()), | 23 num_copied_params_(builder.num_copied_params()), |
| 24 non_copied_parameter_count_(builder.non_copied_parameter_count()), | 24 num_non_copied_params_(builder.num_non_copied_params()), |
| 25 stack_local_count_(builder.stack_local_count()), | 25 num_stack_locals_(builder.num_stack_locals()), |
| 26 graph_entry_(graph_entry), | 26 graph_entry_(graph_entry), |
| 27 preorder_(), | 27 preorder_(), |
| 28 postorder_(), | 28 postorder_(), |
| 29 reverse_postorder_(), | 29 reverse_postorder_(), |
| 30 exits_(NULL) { | 30 exits_(NULL) { |
| 31 DiscoverBlocks(); | 31 DiscoverBlocks(); |
| 32 } | 32 } |
| 33 | 33 |
| 34 | 34 |
| 35 void FlowGraph::DiscoverBlocks() { | 35 void FlowGraph::DiscoverBlocks() { |
| 36 // Initialize state. | 36 // Initialize state. |
| 37 preorder_.TruncateTo(0); | 37 preorder_.TruncateTo(0); |
| 38 postorder_.TruncateTo(0); | 38 postorder_.TruncateTo(0); |
| 39 reverse_postorder_.TruncateTo(0); | 39 reverse_postorder_.TruncateTo(0); |
| 40 parent_.TruncateTo(0); | 40 parent_.TruncateTo(0); |
| 41 assigned_vars_.TruncateTo(0); | 41 assigned_vars_.TruncateTo(0); |
| 42 // Perform a depth-first traversal of the graph to build preorder and | 42 // Perform a depth-first traversal of the graph to build preorder and |
| 43 // postorder block orders. | 43 // postorder block orders. |
| 44 graph_entry_->DiscoverBlocks(NULL, // Entry block predecessor. | 44 graph_entry_->DiscoverBlocks(NULL, // Entry block predecessor. |
| 45 &preorder_, | 45 &preorder_, |
| 46 &postorder_, | 46 &postorder_, |
| 47 &parent_, | 47 &parent_, |
| 48 &assigned_vars_, | 48 &assigned_vars_, |
| 49 variable_count(), | 49 variable_count(), |
| 50 non_copied_parameter_count()); | 50 num_non_copied_params()); |
| 51 // Number blocks in reverse postorder. | 51 // Number blocks in reverse postorder. |
| 52 intptr_t block_count = postorder_.length(); | 52 intptr_t block_count = postorder_.length(); |
| 53 for (intptr_t i = 0; i < block_count; ++i) { | 53 for (intptr_t i = 0; i < block_count; ++i) { |
| 54 postorder_[i]->set_block_id(block_count - i - 1); | 54 postorder_[i]->set_block_id(block_count - i - 1); |
| 55 reverse_postorder_.Add(postorder_[block_count - i - 1]); | 55 reverse_postorder_.Add(postorder_[block_count - i - 1]); |
| 56 } | 56 } |
| 57 // Link instructions backwards for optimized compilation. | 57 // Link instructions backwards for optimized compilation. |
| 58 // TODO(zerny): The builder should do this at construction time. | 58 // TODO(zerny): The builder should do this at construction time. |
| 59 for (intptr_t i = 0; i < block_count; ++i) { | 59 for (intptr_t i = 0; i < block_count; ++i) { |
| 60 BlockEntryInstr* entry = postorder_[i]; | 60 BlockEntryInstr* entry = postorder_[i]; |
| (...skipping 442 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 503 param->set_ssa_temp_index(alloc_ssa_temp_index()); // New SSA temp. | 503 param->set_ssa_temp_index(alloc_ssa_temp_index()); // New SSA temp. |
| 504 start_env.Add(param); | 504 start_env.Add(param); |
| 505 } | 505 } |
| 506 | 506 |
| 507 // All locals are initialized with #null. Use the global definition, uses | 507 // All locals are initialized with #null. Use the global definition, uses |
| 508 // will be created in the Environment constructor. | 508 // will be created in the Environment constructor. |
| 509 while (start_env.length() < variable_count()) { | 509 while (start_env.length() < variable_count()) { |
| 510 start_env.Add(graph_entry_->constant_null()); | 510 start_env.Add(graph_entry_->constant_null()); |
| 511 } | 511 } |
| 512 graph_entry_->set_start_env( | 512 graph_entry_->set_start_env( |
| 513 new Environment(start_env, non_copied_parameter_count_)); | 513 new Environment(start_env, num_non_copied_params_)); |
| 514 | 514 |
| 515 BlockEntryInstr* normal_entry = graph_entry_->SuccessorAt(0); | 515 BlockEntryInstr* normal_entry = graph_entry_->SuccessorAt(0); |
| 516 ASSERT(normal_entry != NULL); // Must have entry. | 516 ASSERT(normal_entry != NULL); // Must have entry. |
| 517 GrowableArray<Definition*> env(variable_count()); | 517 GrowableArray<Definition*> env(variable_count()); |
| 518 env.AddArray(start_env); | 518 env.AddArray(start_env); |
| 519 RenameRecursive(normal_entry, &env, live_phis); | 519 RenameRecursive(normal_entry, &env, live_phis); |
| 520 } | 520 } |
| 521 | 521 |
| 522 | 522 |
| 523 void FlowGraph::RenameRecursive(BlockEntryInstr* block_entry, | 523 void FlowGraph::RenameRecursive(BlockEntryInstr* block_entry, |
| (...skipping 12 matching lines...) Expand all Loading... |
| 536 } | 536 } |
| 537 } | 537 } |
| 538 } | 538 } |
| 539 | 539 |
| 540 // 2. Process normal instructions. | 540 // 2. Process normal instructions. |
| 541 for (ForwardInstructionIterator it(block_entry); !it.Done(); it.Advance()) { | 541 for (ForwardInstructionIterator it(block_entry); !it.Done(); it.Advance()) { |
| 542 Instruction* current = it.Current(); | 542 Instruction* current = it.Current(); |
| 543 // Attach current environment to the instruction. First, each instruction | 543 // Attach current environment to the instruction. First, each instruction |
| 544 // gets a full copy of the environment. Later we optimize this by | 544 // gets a full copy of the environment. Later we optimize this by |
| 545 // eliminating unnecessary environments. | 545 // eliminating unnecessary environments. |
| 546 current->set_env(new Environment(*env, non_copied_parameter_count_)); | 546 current->set_env(new Environment(*env, num_non_copied_params_)); |
| 547 | 547 |
| 548 // 2a. Handle uses: | 548 // 2a. Handle uses: |
| 549 // Update expression stack environment for each use. | 549 // Update expression stack environment for each use. |
| 550 // For each use of a LoadLocal or StoreLocal: Replace it with the value | 550 // For each use of a LoadLocal or StoreLocal: Replace it with the value |
| 551 // from the environment. | 551 // from the environment. |
| 552 for (intptr_t i = current->InputCount() - 1; i >= 0; --i) { | 552 for (intptr_t i = current->InputCount() - 1; i >= 0; --i) { |
| 553 Value* v = current->InputAt(i); | 553 Value* v = current->InputAt(i); |
| 554 // Update expression stack. | 554 // Update expression stack. |
| 555 ASSERT(env->length() > variable_count()); | 555 ASSERT(env->length() > variable_count()); |
| 556 | 556 |
| (...skipping 18 matching lines...) Expand all Loading... |
| 575 // 2b. Handle LoadLocal and StoreLocal. | 575 // 2b. Handle LoadLocal and StoreLocal. |
| 576 // For each LoadLocal: Remove it from the graph. | 576 // For each LoadLocal: Remove it from the graph. |
| 577 // For each StoreLocal: Remove it from the graph and update the environment. | 577 // For each StoreLocal: Remove it from the graph and update the environment. |
| 578 Definition* definition = current->AsDefinition(); | 578 Definition* definition = current->AsDefinition(); |
| 579 if (definition != NULL) { | 579 if (definition != NULL) { |
| 580 LoadLocalInstr* load = definition->AsLoadLocal(); | 580 LoadLocalInstr* load = definition->AsLoadLocal(); |
| 581 StoreLocalInstr* store = definition->AsStoreLocal(); | 581 StoreLocalInstr* store = definition->AsStoreLocal(); |
| 582 if ((load != NULL) || (store != NULL)) { | 582 if ((load != NULL) || (store != NULL)) { |
| 583 intptr_t index; | 583 intptr_t index; |
| 584 if (store != NULL) { | 584 if (store != NULL) { |
| 585 index = store->local().BitIndexIn(non_copied_parameter_count_); | 585 index = store->local().BitIndexIn(num_non_copied_params_); |
| 586 // Update renaming environment. | 586 // Update renaming environment. |
| 587 (*env)[index] = store->value()->definition(); | 587 (*env)[index] = store->value()->definition(); |
| 588 } else { | 588 } else { |
| 589 // The graph construction ensures we do not have an unused LoadLocal | 589 // The graph construction ensures we do not have an unused LoadLocal |
| 590 // computation. | 590 // computation. |
| 591 ASSERT(definition->is_used()); | 591 ASSERT(definition->is_used()); |
| 592 index = load->local().BitIndexIn(non_copied_parameter_count_); | 592 index = load->local().BitIndexIn(num_non_copied_params_); |
| 593 | 593 |
| 594 PhiInstr* phi = (*env)[index]->AsPhi(); | 594 PhiInstr* phi = (*env)[index]->AsPhi(); |
| 595 if ((phi != NULL) && !phi->is_alive()) { | 595 if ((phi != NULL) && !phi->is_alive()) { |
| 596 phi->mark_alive(); | 596 phi->mark_alive(); |
| 597 live_phis->Add(phi); | 597 live_phis->Add(phi); |
| 598 } | 598 } |
| 599 } | 599 } |
| 600 // Update expression stack or remove from graph. | 600 // Update expression stack or remove from graph. |
| 601 if (definition->is_used()) { | 601 if (definition->is_used()) { |
| 602 env->Add((*env)[index]); | 602 env->Add((*env)[index]); |
| (...skipping 189 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 792 // Remove original arguments to the call. | 792 // Remove original arguments to the call. |
| 793 for (intptr_t i = 0; i < call->ArgumentCount(); ++i) { | 793 for (intptr_t i = 0; i < call->ArgumentCount(); ++i) { |
| 794 PushArgumentInstr* push = call->ArgumentAt(i); | 794 PushArgumentInstr* push = call->ArgumentAt(i); |
| 795 push->ReplaceUsesWith(push->value()->definition()); | 795 push->ReplaceUsesWith(push->value()->definition()); |
| 796 push->RemoveFromGraph(); | 796 push->RemoveFromGraph(); |
| 797 } | 797 } |
| 798 } | 798 } |
| 799 | 799 |
| 800 | 800 |
| 801 } // namespace dart | 801 } // namespace dart |
| OLD | NEW |