| 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 762 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 773 // If the successor is a target, update its predecessor. | 773 // If the successor is a target, update its predecessor. |
| 774 TargetEntryInstr* target = last->SuccessorAt(sidx)->AsTargetEntry(); | 774 TargetEntryInstr* target = last->SuccessorAt(sidx)->AsTargetEntry(); |
| 775 if (target != NULL) { | 775 if (target != NULL) { |
| 776 target->predecessor_ = new_block; | 776 target->predecessor_ = new_block; |
| 777 continue; | 777 continue; |
| 778 } | 778 } |
| 779 // If the successor is a join, update each predecessor and the phis. | 779 // If the successor is a join, update each predecessor and the phis. |
| 780 JoinEntryInstr* join = last->SuccessorAt(sidx)->AsJoinEntry(); | 780 JoinEntryInstr* join = last->SuccessorAt(sidx)->AsJoinEntry(); |
| 781 ASSERT(join != NULL); | 781 ASSERT(join != NULL); |
| 782 // Find the old predecessor index. | 782 // Find the old predecessor index. |
| 783 const intptr_t old_index = join->IndexOfPredecessor(old_block); | 783 intptr_t old_index = join->IndexOfPredecessor(old_block); |
| 784 const intptr_t pred_count = join->PredecessorCount(); | 784 intptr_t pred_count = join->PredecessorCount(); |
| 785 ASSERT(old_index >= 0); | 785 ASSERT(old_index >= 0); |
| 786 ASSERT(old_index < pred_count); | 786 ASSERT(old_index < pred_count); |
| 787 // Find the new predecessor index while reordering the predecessors. | 787 // Find the new predecessor index while reordering the predecessors. |
| 788 const intptr_t new_id = new_block->block_id(); | 788 intptr_t new_id = new_block->block_id(); |
| 789 intptr_t new_index = old_index; | 789 intptr_t new_index = old_index; |
| 790 // The predecessors are sorted by block id in ascending order. This is done | |
| 791 // in JoinEntryInstr::AddPredecessor and in InlineCall. | |
| 792 if (old_block->block_id() < new_id) { | 790 if (old_block->block_id() < new_id) { |
| 793 // Search upwards, bubbling down intermediate predecessors. | 791 // Search upwards, bubbling down intermediate predecessors. |
| 794 for (; new_index < pred_count - 1; ++new_index) { | 792 for (; new_index < pred_count - 1; ++new_index) { |
| 795 ASSERT(join->predecessors_[new_index]->block_id() < | |
| 796 join->predecessors_[new_index + 1]->block_id()); | |
| 797 if (join->predecessors_[new_index + 1]->block_id() > new_id) break; | 793 if (join->predecessors_[new_index + 1]->block_id() > new_id) break; |
| 798 join->predecessors_[new_index] = join->predecessors_[new_index + 1]; | 794 join->predecessors_[new_index] = join->predecessors_[new_index + 1]; |
| 799 } | 795 } |
| 800 } else { | 796 } else { |
| 801 // Search downwards, bubbling up intermediate predecessors. | 797 // Search downwards, bubbling up intermediate predecessors. |
| 802 for (; new_index > 0; --new_index) { | 798 for (; new_index > 0; --new_index) { |
| 803 ASSERT(join->predecessors_[new_index - 1]->block_id() < | |
| 804 join->predecessors_[new_index]->block_id()); | |
| 805 if (join->predecessors_[new_index - 1]->block_id() < new_id) break; | 799 if (join->predecessors_[new_index - 1]->block_id() < new_id) break; |
| 806 join->predecessors_[new_index] = join->predecessors_[new_index - 1]; | 800 join->predecessors_[new_index] = join->predecessors_[new_index - 1]; |
| 807 } | 801 } |
| 808 } | 802 } |
| 809 join->predecessors_[new_index] = new_block; | 803 join->predecessors_[new_index] = new_block; |
| 810 // If the new and old predecessor index match there is nothing to update. | 804 // If the new and old predecessor index match there is nothing to update. |
| 811 if ((join->phis() == NULL) || (old_index == new_index)) return; | 805 if ((join->phis() == NULL) || (old_index == new_index)) return; |
| 812 // Otherwise, reorder the predecessor uses in each phi. | 806 // Otherwise, reorder the predecessor uses in each phi. |
| 813 for (intptr_t i = 0; i < join->phis()->length(); ++i) { | 807 for (intptr_t i = 0; i < join->phis()->length(); ++i) { |
| 814 PhiInstr* phi = (*join->phis())[i]; | 808 PhiInstr* phi = (*join->phis())[i]; |
| (...skipping 170 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 985 ReplacePredecessor(callee_entry, caller_entry); | 979 ReplacePredecessor(callee_entry, caller_entry); |
| 986 // Update the last instruction pointers on each exit (ie, to the new goto). | 980 // Update the last instruction pointers on each exit (ie, to the new goto). |
| 987 for (intptr_t i = 0; i < exits.length(); ++i) { | 981 for (intptr_t i = 0; i < exits.length(); ++i) { |
| 988 exits[i]->set_last_instruction( | 982 exits[i]->set_last_instruction( |
| 989 exits[i]->last_instruction()->previous()->next()); | 983 exits[i]->last_instruction()->previous()->next()); |
| 990 } | 984 } |
| 991 // Mark that the dominator tree is invalid. | 985 // Mark that the dominator tree is invalid. |
| 992 // TODO(zerny): Compute the dominator frontier locally. | 986 // TODO(zerny): Compute the dominator frontier locally. |
| 993 invalid_dominator_tree_ = true; | 987 invalid_dominator_tree_ = true; |
| 994 } | 988 } |
| 995 | |
| 996 // Remove push arguments of the call. | |
| 997 for (intptr_t i = 0; i < call->ArgumentCount(); ++i) { | |
| 998 PushArgumentInstr* push = call->ArgumentAt(i); | |
| 999 push->ReplaceUsesWith(push->value()->definition()); | |
| 1000 push->RemoveFromGraph(); | |
| 1001 } | |
| 1002 | |
| 1003 // Replace remaining constants with uses by constants in the caller's | |
| 1004 // initial definitions. | |
| 1005 GrowableArray<Definition*>* defns = | |
| 1006 callee_graph->graph_entry()->initial_definitions(); | |
| 1007 for (intptr_t i = 0; i < defns->length(); ++i) { | |
| 1008 ConstantInstr* constant = (*defns)[i]->AsConstant(); | |
| 1009 if (constant != NULL && | |
| 1010 ((constant->input_use_list() != NULL) || | |
| 1011 (constant->env_use_list() != NULL))) { | |
| 1012 constant->ReplaceUsesWith( | |
| 1013 AddConstantToInitialDefinitions(constant->value())); | |
| 1014 } | |
| 1015 } | |
| 1016 } | 989 } |
| 1017 | 990 |
| 1018 | 991 |
| 1019 void FlowGraph::RepairGraphAfterInlining() { | 992 void FlowGraph::RepairGraphAfterInlining() { |
| 1020 DiscoverBlocks(); | 993 DiscoverBlocks(); |
| 1021 if (invalid_dominator_tree_) { | 994 if (invalid_dominator_tree_) { |
| 1022 GrowableArray<BitVector*> dominance_frontier; | 995 GrowableArray<BitVector*> dominance_frontier; |
| 1023 ComputeDominators(&dominance_frontier); | 996 ComputeDominators(&dominance_frontier); |
| 1024 } | 997 } |
| 1025 } | 998 } |
| 1026 | 999 |
| 1027 | 1000 |
| 1028 intptr_t FlowGraph::InstructionCount() const { | 1001 intptr_t FlowGraph::InstructionCount() const { |
| 1029 intptr_t size = 0; | 1002 intptr_t size = 0; |
| 1030 // Iterate each block, skipping the graph entry. | 1003 // Iterate each block, skipping the graph entry. |
| 1031 for (intptr_t i = 1; i < preorder_.length(); ++i) { | 1004 for (intptr_t i = 1; i < preorder_.length(); ++i) { |
| 1032 for (ForwardInstructionIterator it(preorder_[i]); | 1005 for (ForwardInstructionIterator it(preorder_[i]); |
| 1033 !it.Done(); | 1006 !it.Done(); |
| 1034 it.Advance()) { | 1007 it.Advance()) { |
| 1035 ++size; | 1008 ++size; |
| 1036 } | 1009 } |
| 1037 } | 1010 } |
| 1038 return size; | 1011 return size; |
| 1039 } | 1012 } |
| 1040 | 1013 |
| 1041 | 1014 |
| 1042 } // namespace dart | 1015 } // namespace dart |
| OLD | NEW |