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 |