| 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 534 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 545 | 545 |
| 546 // 2a. Handle uses: | 546 // 2a. Handle uses: |
| 547 // Update expression stack environment for each use. | 547 // Update expression stack environment for each use. |
| 548 // For each use of a LoadLocal or StoreLocal: Replace it with the value | 548 // For each use of a LoadLocal or StoreLocal: Replace it with the value |
| 549 // from the environment. | 549 // from the environment. |
| 550 for (intptr_t i = current->InputCount() - 1; i >= 0; --i) { | 550 for (intptr_t i = current->InputCount() - 1; i >= 0; --i) { |
| 551 Value* v = current->InputAt(i); | 551 Value* v = current->InputAt(i); |
| 552 // Update expression stack. | 552 // Update expression stack. |
| 553 ASSERT(env->length() > variable_count()); | 553 ASSERT(env->length() > variable_count()); |
| 554 | 554 |
| 555 Definition* input_defn = env->Last(); | 555 Definition* reaching_defn = env->Last(); |
| 556 env->RemoveLast(); | 556 env->RemoveLast(); |
| 557 | 557 |
| 558 BindInstr* as_bind = v->definition()->AsBind(); | 558 Definition* input_defn = v->definition(); |
| 559 if ((as_bind != NULL) && | 559 if (input_defn->IsLoadLocal() || input_defn->IsStoreLocal()) { |
| 560 (as_bind->computation()->IsLoadLocal() || | |
| 561 as_bind->computation()->IsStoreLocal())) { | |
| 562 // Remove the load/store from the graph. | 560 // Remove the load/store from the graph. |
| 563 as_bind->RemoveFromGraph(); | 561 input_defn->RemoveFromGraph(); |
| 564 // Assert we are not referencing nulls in the initial environment. | 562 // Assert we are not referencing nulls in the initial environment. |
| 565 ASSERT(input_defn->ssa_temp_index() != -1); | 563 ASSERT(reaching_defn->ssa_temp_index() != -1); |
| 566 current->SetInputAt(i, new Value(input_defn)); | 564 current->SetInputAt(i, new Value(reaching_defn)); |
| 567 } | 565 } |
| 568 } | 566 } |
| 569 | 567 |
| 570 // Drop pushed arguments for calls. | 568 // Drop pushed arguments for calls. |
| 571 for (intptr_t j = 0; j < current->ArgumentCount(); j++) { | 569 for (intptr_t j = 0; j < current->ArgumentCount(); j++) { |
| 572 env->RemoveLast(); | 570 env->RemoveLast(); |
| 573 } | 571 } |
| 574 | 572 |
| 575 // 2b. Handle LoadLocal and StoreLocal. | 573 // 2b. Handle LoadLocal and StoreLocal. |
| 576 // For each LoadLocal: Remove it from the graph. | 574 // For each LoadLocal: Remove it from the graph. |
| 577 // For each StoreLocal: Remove it from the graph and update the environment. | 575 // For each StoreLocal: Remove it from the graph and update the environment. |
| 578 BindInstr* bind = current->AsBind(); | 576 Definition* definition = current->AsDefinition(); |
| 579 if (bind != NULL) { | 577 if (definition != NULL) { |
| 580 LoadLocalComp* load = bind->computation()->AsLoadLocal(); | 578 LoadLocalInstr* load = definition->AsLoadLocal(); |
| 581 StoreLocalComp* store = bind->computation()->AsStoreLocal(); | 579 StoreLocalInstr* store = definition->AsStoreLocal(); |
| 582 if ((load != NULL) || (store != NULL)) { | 580 if ((load != NULL) || (store != NULL)) { |
| 583 intptr_t index; | 581 intptr_t index; |
| 584 if (store != NULL) { | 582 if (store != NULL) { |
| 585 index = store->local().BitIndexIn(non_copied_parameter_count_); | 583 index = store->local().BitIndexIn(non_copied_parameter_count_); |
| 586 // Update renaming environment. | 584 // Update renaming environment. |
| 587 (*env)[index] = store->value()->definition(); | 585 (*env)[index] = store->value()->definition(); |
| 588 } else { | 586 } else { |
| 589 // The graph construction ensures we do not have an unused LoadLocal | 587 // The graph construction ensures we do not have an unused LoadLocal |
| 590 // computation. | 588 // computation. |
| 591 ASSERT(bind->is_used()); | 589 ASSERT(definition->is_used()); |
| 592 index = load->local().BitIndexIn(non_copied_parameter_count_); | 590 index = load->local().BitIndexIn(non_copied_parameter_count_); |
| 593 | 591 |
| 594 PhiInstr* phi = (*env)[index]->AsPhi(); | 592 PhiInstr* phi = (*env)[index]->AsPhi(); |
| 595 if ((phi != NULL) && !phi->is_alive()) { | 593 if ((phi != NULL) && !phi->is_alive()) { |
| 596 phi->mark_alive(); | 594 phi->mark_alive(); |
| 597 live_phis->Add(phi); | 595 live_phis->Add(phi); |
| 598 } | 596 } |
| 599 } | 597 } |
| 600 // Update expression stack or remove from graph. | 598 // Update expression stack or remove from graph. |
| 601 if (bind->is_used()) { | 599 if (definition->is_used()) { |
| 602 env->Add((*env)[index]); | 600 env->Add((*env)[index]); |
| 603 // We remove load/store instructions when we find their use in 2a. | 601 // We remove load/store instructions when we find their use in 2a. |
| 604 } else { | 602 } else { |
| 605 it.RemoveCurrentFromGraph(); | 603 it.RemoveCurrentFromGraph(); |
| 606 } | 604 } |
| 607 } else { | 605 } else { |
| 608 // Not a load or store. | 606 // Not a load or store. |
| 609 if (bind->is_used()) { | 607 if (definition->is_used()) { |
| 610 // Assign fresh SSA temporary and update expression stack. | 608 // Assign fresh SSA temporary and update expression stack. |
| 611 bind->set_ssa_temp_index(alloc_ssa_temp_index()); | 609 definition->set_ssa_temp_index(alloc_ssa_temp_index()); |
| 612 env->Add(bind); | 610 env->Add(definition); |
| 613 } | 611 } |
| 614 } | 612 } |
| 615 } | 613 } |
| 616 | 614 |
| 617 // 2c. Handle pushed argument. | 615 // 2c. Handle pushed argument. |
| 618 PushArgumentInstr* push = current->AsPushArgument(); | 616 PushArgumentInstr* push = current->AsPushArgument(); |
| 619 if (push != NULL) { | 617 if (push != NULL) { |
| 620 env->Add(push); | 618 env->Add(push); |
| 621 } | 619 } |
| 622 } | 620 } |
| (...skipping 71 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 694 | 692 |
| 695 | 693 |
| 696 // Inline a flow graph at a call site. | 694 // Inline a flow graph at a call site. |
| 697 // | 695 // |
| 698 // Assumes the callee graph was computed with BuildGraphForInlining and | 696 // Assumes the callee graph was computed with BuildGraphForInlining and |
| 699 // transformed to SSA with ComputeSSAForInlining, and that the use lists have | 697 // transformed to SSA with ComputeSSAForInlining, and that the use lists have |
| 700 // been correctly computed. | 698 // been correctly computed. |
| 701 // | 699 // |
| 702 // After inlining the caller graph will correctly have adjusted the pre/post | 700 // After inlining the caller graph will correctly have adjusted the pre/post |
| 703 // orders, the dominator tree and the use lists. | 701 // orders, the dominator tree and the use lists. |
| 704 void FlowGraph::InlineCall(BindInstr* caller_instr, | 702 void FlowGraph::InlineCall(StaticCallInstr* call, FlowGraph* callee_graph) { |
| 705 StaticCallComp* caller_comp, | |
| 706 FlowGraph* callee_graph) { | |
| 707 ASSERT(callee_graph->exits() != NULL); | 703 ASSERT(callee_graph->exits() != NULL); |
| 708 ASSERT(callee_graph->graph_entry()->SuccessorCount() == 1); | 704 ASSERT(callee_graph->graph_entry()->SuccessorCount() == 1); |
| 709 ASSERT(callee_graph->max_virtual_register_number() > | 705 ASSERT(callee_graph->max_virtual_register_number() > |
| 710 max_virtual_register_number()); | 706 max_virtual_register_number()); |
| 711 | 707 |
| 712 // TODO(zerny): Implement support for callee graphs with control flow. | 708 // TODO(zerny): Implement support for callee graphs with control flow. |
| 713 ASSERT(callee_graph->preorder().length() == 2); | 709 ASSERT(callee_graph->preorder().length() == 2); |
| 714 | 710 |
| 715 // Adjust the SSA temp index by the callee graph's index. | 711 // Adjust the SSA temp index by the callee graph's index. |
| 716 current_ssa_temp_index_ = callee_graph->max_virtual_register_number(); | 712 current_ssa_temp_index_ = callee_graph->max_virtual_register_number(); |
| 717 | 713 |
| 718 TargetEntryInstr* callee_entry = callee_graph->graph_entry()->normal_entry(); | 714 TargetEntryInstr* callee_entry = callee_graph->graph_entry()->normal_entry(); |
| 719 ZoneGrowableArray<ReturnInstr*>* callee_exits = callee_graph->exits(); | 715 ZoneGrowableArray<ReturnInstr*>* callee_exits = callee_graph->exits(); |
| 720 | 716 |
| 721 // 1. Insert the callee graph into the caller graph. | 717 // 1. Insert the callee graph into the caller graph. |
| 722 if (callee_exits->length() == 1) { | 718 if (callee_exits->length() == 1) { |
| 723 ReturnInstr* exit = (*callee_exits)[0]; | 719 ReturnInstr* exit = (*callee_exits)[0]; |
| 724 // TODO(zerny): Support one exit graph containing control flow. | 720 // TODO(zerny): Support one exit graph containing control flow. |
| 725 ASSERT(callee_entry == GetBlockEntry(exit)); | 721 ASSERT(callee_entry == GetBlockEntry(exit)); |
| 726 // For just one exit, replace the uses and remove the call from the graph. | 722 // For just one exit, replace the uses and remove the call from the graph. |
| 727 caller_instr->ReplaceUsesWith(exit->value()->definition()); | 723 call->ReplaceUsesWith(exit->value()->definition()); |
| 728 Link(caller_instr->previous(), callee_entry->next()); | 724 Link(call->previous(), callee_entry->next()); |
| 729 Link(exit->previous(), caller_instr->next()); | 725 Link(exit->previous(), call->next()); |
| 730 } else { | 726 } else { |
| 731 // TODO(zerny): Support multiple exits. | 727 // TODO(zerny): Support multiple exits. |
| 732 UNREACHABLE(); | 728 UNREACHABLE(); |
| 733 } | 729 } |
| 734 | 730 |
| 735 // TODO(zerny): Adjust pre/post orders. | 731 // TODO(zerny): Adjust pre/post orders. |
| 736 // TODO(zerny): Update dominator tree. | 732 // TODO(zerny): Update dominator tree. |
| 737 | 733 |
| 738 // Remove original arguments to the call. | 734 // Remove original arguments to the call. |
| 739 for (intptr_t i = 0; i < caller_comp->ArgumentCount(); ++i) { | 735 for (intptr_t i = 0; i < call->ArgumentCount(); ++i) { |
| 740 PushArgumentInstr* push = caller_comp->ArgumentAt(i); | 736 PushArgumentInstr* push = call->ArgumentAt(i); |
| 741 push->ReplaceUsesWith(push->value()->definition()); | 737 push->ReplaceUsesWith(push->value()->definition()); |
| 742 push->RemoveFromGraph(); | 738 push->RemoveFromGraph(); |
| 743 } | 739 } |
| 744 } | 740 } |
| 745 | 741 |
| 746 | 742 |
| 747 } // namespace dart | 743 } // namespace dart |
| OLD | NEW |