| 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" | |
| 12 | 11 |
| 13 namespace dart { | 12 namespace dart { |
| 14 | 13 |
| 15 FlowGraph::FlowGraph(const FlowGraphBuilder& builder, | 14 FlowGraph::FlowGraph(const FlowGraphBuilder& builder, |
| 16 GraphEntryInstr* graph_entry) | 15 GraphEntryInstr* graph_entry) |
| 17 : parent_(), | 16 : parent_(), |
| 18 assigned_vars_(), | 17 assigned_vars_(), |
| 19 current_ssa_temp_index_(0), | 18 current_ssa_temp_index_(0), |
| 20 parsed_function_(builder.parsed_function()), | 19 parsed_function_(builder.parsed_function()), |
| 21 copied_parameter_count_(builder.copied_parameter_count()), | 20 copied_parameter_count_(builder.copied_parameter_count()), |
| 22 non_copied_parameter_count_(builder.non_copied_parameter_count()), | 21 non_copied_parameter_count_(builder.non_copied_parameter_count()), |
| 23 stack_local_count_(builder.stack_local_count()), | 22 stack_local_count_(builder.stack_local_count()), |
| 24 graph_entry_(graph_entry), | 23 graph_entry_(graph_entry), |
| 25 preorder_(), | 24 preorder_(), |
| 26 postorder_(), | 25 postorder_(), |
| 27 reverse_postorder_(), | 26 reverse_postorder_() { |
| 28 exits_(NULL) { | |
| 29 DiscoverBlocks(); | 27 DiscoverBlocks(); |
| 30 } | 28 } |
| 31 | 29 |
| 32 | 30 |
| 33 void FlowGraph::DiscoverBlocks() { | 31 void FlowGraph::DiscoverBlocks() { |
| 34 // Initialize state. | 32 // Initialize state. |
| 35 preorder_.TruncateTo(0); | 33 preorder_.TruncateTo(0); |
| 36 postorder_.TruncateTo(0); | 34 postorder_.TruncateTo(0); |
| 37 reverse_postorder_.TruncateTo(0); | 35 reverse_postorder_.TruncateTo(0); |
| 38 parent_.TruncateTo(0); | 36 parent_.TruncateTo(0); |
| (...skipping 248 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 287 } | 285 } |
| 288 | 286 |
| 289 | 287 |
| 290 void FlowGraph::ComputeUseLists() { | 288 void FlowGraph::ComputeUseLists() { |
| 291 DEBUG_ASSERT(ResetUseLists()); | 289 DEBUG_ASSERT(ResetUseLists()); |
| 292 ComputeUseListsRecursive(graph_entry_); | 290 ComputeUseListsRecursive(graph_entry_); |
| 293 DEBUG_ASSERT(ValidateUseLists()); | 291 DEBUG_ASSERT(ValidateUseLists()); |
| 294 } | 292 } |
| 295 | 293 |
| 296 | 294 |
| 297 void FlowGraph::ComputeSSA(intptr_t next_virtual_register_number) { | 295 void FlowGraph::ComputeSSA() { |
| 298 current_ssa_temp_index_ = next_virtual_register_number; | |
| 299 GrowableArray<BitVector*> dominance_frontier; | 296 GrowableArray<BitVector*> dominance_frontier; |
| 300 ComputeDominators(&preorder_, &parent_, &dominance_frontier); | 297 ComputeDominators(&preorder_, &parent_, &dominance_frontier); |
| 301 InsertPhis(preorder_, assigned_vars_, dominance_frontier); | 298 InsertPhis(preorder_, assigned_vars_, dominance_frontier); |
| 302 GrowableArray<PhiInstr*> live_phis; | 299 GrowableArray<PhiInstr*> live_phis; |
| 303 // Rename uses to reference inserted phis where appropriate. | 300 // Rename uses to reference inserted phis where appropriate. |
| 304 // Collect phis that reach a non-environment use. | 301 // Collect phis that reach a non-environment use. |
| 305 Rename(&live_phis); | 302 Rename(&live_phis); |
| 306 // Propagate alive mark transitively from alive phis. | 303 // Propagate alive mark transitively from alive phis. |
| 307 MarkLivePhis(&live_phis); | 304 MarkLivePhis(&live_phis); |
| 308 } | 305 } |
| (...skipping 367 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 676 const char* function_name = parsed_function_.function().ToCString(); | 673 const char* function_name = parsed_function_.function().ToCString(); |
| 677 intptr_t len = OS::SNPrint(NULL, 0, kFormat, function_name, reason) + 1; | 674 intptr_t len = OS::SNPrint(NULL, 0, kFormat, function_name, reason) + 1; |
| 678 char* chars = Isolate::Current()->current_zone()->Alloc<char>(len); | 675 char* chars = Isolate::Current()->current_zone()->Alloc<char>(len); |
| 679 OS::SNPrint(chars, len, kFormat, function_name, reason); | 676 OS::SNPrint(chars, len, kFormat, function_name, reason); |
| 680 const Error& error = Error::Handle( | 677 const Error& error = Error::Handle( |
| 681 LanguageError::New(String::Handle(String::New(chars)))); | 678 LanguageError::New(String::Handle(String::New(chars)))); |
| 682 Isolate::Current()->long_jump_base()->Jump(1, error); | 679 Isolate::Current()->long_jump_base()->Jump(1, error); |
| 683 } | 680 } |
| 684 | 681 |
| 685 | 682 |
| 686 // Helper to get the block-entry of an instruction. | |
| 687 static BlockEntryInstr* GetBlockEntry(Instruction* instr) { | |
| 688 while (!instr->IsBlockEntry()) instr = instr->previous(); | |
| 689 return instr->AsBlockEntry(); | |
| 690 } | |
| 691 | |
| 692 | |
| 693 // Helper to link two instructions in the graph. | |
| 694 static void Link(Instruction* prev, Instruction* next) { | |
| 695 ASSERT(prev != next); | |
| 696 prev->set_next(next); | |
| 697 next->set_previous(prev); | |
| 698 } | |
| 699 | |
| 700 | |
| 701 // Inline a flow graph at a call site. | |
| 702 // | |
| 703 // Assumes the callee graph was computed with BuildGraphForInlining and | |
| 704 // transformed to SSA with ComputeSSAForInlining, and that the use lists have | |
| 705 // been correctly computed. | |
| 706 // | |
| 707 // After inlining the caller graph will correctly have adjusted the pre/post | |
| 708 // orders, the dominator tree and the use lists. | |
| 709 void FlowGraph::InlineCall(BindInstr* caller_instr, | |
| 710 StaticCallComp* caller_comp, | |
| 711 FlowGraph* callee_graph) { | |
| 712 ASSERT(callee_graph->exits() != NULL); | |
| 713 ASSERT(callee_graph->graph_entry()->SuccessorCount() == 1); | |
| 714 ASSERT(callee_graph->max_virtual_register_number() > | |
| 715 max_virtual_register_number()); | |
| 716 | |
| 717 // TODO(zerny): Implement support for callee graphs with control flow. | |
| 718 ASSERT(callee_graph->preorder().length() == 2); | |
| 719 | |
| 720 // Adjust the SSA temp index by the callee graph's index. | |
| 721 current_ssa_temp_index_ = callee_graph->max_virtual_register_number(); | |
| 722 | |
| 723 TargetEntryInstr* callee_entry = callee_graph->graph_entry()->normal_entry(); | |
| 724 ZoneGrowableArray<ReturnInstr*>* callee_exits = callee_graph->exits(); | |
| 725 | |
| 726 // 1. Insert the callee graph into the caller graph. | |
| 727 if (callee_exits->length() == 1) { | |
| 728 ReturnInstr* exit = (*callee_exits)[0]; | |
| 729 // TODO(zerny): Support one exit graph containing control flow. | |
| 730 ASSERT(callee_entry == GetBlockEntry(exit)); | |
| 731 // For just one exit, replace the uses and remove the call from the graph. | |
| 732 caller_instr->ReplaceUsesWith(exit->value()->AsUse()->definition()); | |
| 733 Link(caller_instr->previous(), callee_entry->next()); | |
| 734 Link(exit->previous(), caller_instr->next()); | |
| 735 } else { | |
| 736 // TODO(zerny): Support multiple exits. | |
| 737 UNREACHABLE(); | |
| 738 } | |
| 739 | |
| 740 // TODO(zerny): Adjust pre/post orders. | |
| 741 // TODO(zerny): Update dominator tree. | |
| 742 | |
| 743 // Remove original arguments to the call. | |
| 744 for (intptr_t i = 0; i < caller_comp->ArgumentCount(); ++i) { | |
| 745 PushArgumentInstr* push = caller_comp->ArgumentAt(i); | |
| 746 push->ReplaceUsesWith(push->value()->AsUse()->definition()); | |
| 747 push->RemoveFromGraph(); | |
| 748 } | |
| 749 } | |
| 750 | |
| 751 | |
| 752 } // namespace dart | 683 } // namespace dart |
| OLD | NEW |