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 |