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_builder.h" | 5 #include "vm/flow_graph_builder.h" |
6 | 6 |
7 #include "vm/ast_printer.h" | 7 #include "vm/ast_printer.h" |
8 #include "vm/bit_vector.h" | 8 #include "vm/bit_vector.h" |
9 #include "vm/code_descriptors.h" | 9 #include "vm/code_descriptors.h" |
10 #include "vm/dart_entry.h" | 10 #include "vm/dart_entry.h" |
(...skipping 2268 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2279 const Function& function = parsed_function().function(); | 2279 const Function& function = parsed_function().function(); |
2280 TargetEntryInstr* normal_entry = new TargetEntryInstr(); | 2280 TargetEntryInstr* normal_entry = new TargetEntryInstr(); |
2281 graph_entry_ = new GraphEntryInstr(normal_entry); | 2281 graph_entry_ = new GraphEntryInstr(normal_entry); |
2282 EffectGraphVisitor for_effect(this, 0); | 2282 EffectGraphVisitor for_effect(this, 0); |
2283 parsed_function().node_sequence()->Visit(&for_effect); | 2283 parsed_function().node_sequence()->Visit(&for_effect); |
2284 AppendFragment(normal_entry, for_effect); | 2284 AppendFragment(normal_entry, for_effect); |
2285 // Check that the graph is properly terminated. | 2285 // Check that the graph is properly terminated. |
2286 ASSERT(!for_effect.is_open()); | 2286 ASSERT(!for_effect.is_open()); |
2287 GrowableArray<intptr_t> parent; | 2287 GrowableArray<intptr_t> parent; |
2288 GrowableArray<BitVector*> assigned_vars; | 2288 GrowableArray<BitVector*> assigned_vars; |
2289 intptr_t variable_count = parsed_function_.function().num_fixed_parameters() + | 2289 |
| 2290 const intptr_t fixed_parameter_count = |
| 2291 parsed_function_.function().num_fixed_parameters(); |
| 2292 const intptr_t variable_count = fixed_parameter_count + |
2290 parsed_function_.copied_parameter_count() + | 2293 parsed_function_.copied_parameter_count() + |
2291 parsed_function_.stack_local_count(); | 2294 parsed_function_.stack_local_count(); |
2292 // Perform a depth-first traversal of the graph to build preorder and | 2295 // Perform a depth-first traversal of the graph to build preorder and |
2293 // postorder block orders. | 2296 // postorder block orders. |
2294 graph_entry_->DiscoverBlocks(NULL, // Entry block predecessor. | 2297 graph_entry_->DiscoverBlocks(NULL, // Entry block predecessor. |
2295 &preorder_block_entries_, | 2298 &preorder_block_entries_, |
2296 &postorder_block_entries_, | 2299 &postorder_block_entries_, |
2297 &parent, | 2300 &parent, |
2298 &assigned_vars, | 2301 &assigned_vars, |
2299 variable_count); | 2302 variable_count, |
| 2303 fixed_parameter_count); |
2300 // Number blocks in reverse postorder. | 2304 // Number blocks in reverse postorder. |
2301 intptr_t block_count = postorder_block_entries_.length(); | 2305 intptr_t block_count = postorder_block_entries_.length(); |
2302 for (intptr_t i = 0; i < block_count; ++i) { | 2306 for (intptr_t i = 0; i < block_count; ++i) { |
2303 postorder_block_entries_[i]->set_block_id(block_count - i - 1); | 2307 postorder_block_entries_[i]->set_block_id(block_count - i - 1); |
2304 } | 2308 } |
2305 | 2309 |
2306 if (for_optimized) { | 2310 if (for_optimized) { |
2307 // Link instructions backwards for optimized compilation. | 2311 // Link instructions backwards for optimized compilation. |
2308 for (intptr_t i = 0; i < block_count; ++i) { | 2312 for (intptr_t i = 0; i < block_count; ++i) { |
2309 BlockEntryInstr* entry = postorder_block_entries_[i]; | 2313 BlockEntryInstr* entry = postorder_block_entries_[i]; |
(...skipping 225 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2535 // TODO(fschneider): Support copied parameters. | 2539 // TODO(fschneider): Support copied parameters. |
2536 if (parsed_function().copied_parameter_count() != 0) { | 2540 if (parsed_function().copied_parameter_count() != 0) { |
2537 Bailout("Copied parameter support in SSA"); | 2541 Bailout("Copied parameter support in SSA"); |
2538 } | 2542 } |
2539 ASSERT(var_count == (parsed_function().stack_local_count() + | 2543 ASSERT(var_count == (parsed_function().stack_local_count() + |
2540 parsed_function().function().num_fixed_parameters())); | 2544 parsed_function().function().num_fixed_parameters())); |
2541 | 2545 |
2542 // Initialize start environment. | 2546 // Initialize start environment. |
2543 GrowableArray<Value*> start_env(var_count); | 2547 GrowableArray<Value*> start_env(var_count); |
2544 intptr_t i = 0; | 2548 intptr_t i = 0; |
2545 for (; i < parsed_function().function().num_fixed_parameters(); ++i) { | 2549 const intptr_t fixed_parameter_count = |
| 2550 parsed_function().function().num_fixed_parameters(); |
| 2551 for (; i < fixed_parameter_count; ++i) { |
2546 ParameterInstr* param = new ParameterInstr(i); | 2552 ParameterInstr* param = new ParameterInstr(i); |
2547 param->set_ssa_temp_index(alloc_ssa_temp_index()); // New SSA temp. | 2553 param->set_ssa_temp_index(alloc_ssa_temp_index()); // New SSA temp. |
2548 start_env.Add(new UseVal(param)); | 2554 start_env.Add(new UseVal(param)); |
2549 } | 2555 } |
2550 | 2556 |
2551 // All locals are initialized with #null. | 2557 // All locals are initialized with #null. |
2552 Value* null_value = new ConstantVal(Object::ZoneHandle()); | 2558 Value* null_value = new ConstantVal(Object::ZoneHandle()); |
2553 for (; i < var_count; i++) { | 2559 for (; i < var_count; i++) { |
2554 start_env.Add(null_value); | 2560 start_env.Add(null_value); |
2555 } | 2561 } |
2556 graph_entry_->set_start_env(new Environment(start_env)); | 2562 graph_entry_->set_start_env( |
| 2563 new Environment(start_env, fixed_parameter_count)); |
2557 | 2564 |
2558 BlockEntryInstr* normal_entry = graph_entry_->SuccessorAt(0); | 2565 BlockEntryInstr* normal_entry = graph_entry_->SuccessorAt(0); |
2559 ASSERT(normal_entry != NULL); // Must have entry. | 2566 ASSERT(normal_entry != NULL); // Must have entry. |
2560 GrowableArray<Value*> env(var_count); | 2567 GrowableArray<Value*> env(var_count); |
2561 env.AddArray(start_env); | 2568 env.AddArray(start_env); |
2562 RenameRecursive(normal_entry, &env, var_count); | 2569 RenameRecursive(normal_entry, &env, var_count, fixed_parameter_count); |
2563 } | 2570 } |
2564 | 2571 |
2565 | 2572 |
2566 // Helper to a copy a value iff it is a UseVal. | 2573 // Helper to a copy a value iff it is a UseVal. |
2567 static Value* CopyValue(Value* value) { | 2574 static Value* CopyValue(Value* value) { |
2568 return value->IsUse() | 2575 return value->IsUse() |
2569 ? new UseVal(value->AsUse()->definition()) | 2576 ? new UseVal(value->AsUse()->definition()) |
2570 : value; | 2577 : value; |
2571 } | 2578 } |
2572 | 2579 |
2573 | 2580 |
2574 void FlowGraphBuilder::RenameRecursive(BlockEntryInstr* block_entry, | 2581 void FlowGraphBuilder::RenameRecursive(BlockEntryInstr* block_entry, |
2575 GrowableArray<Value*>* env, | 2582 GrowableArray<Value*>* env, |
2576 intptr_t var_count) { | 2583 intptr_t var_count, |
| 2584 intptr_t fixed_parameter_count) { |
2577 // 1. Process phis first. | 2585 // 1. Process phis first. |
2578 if (block_entry->IsJoinEntry()) { | 2586 if (block_entry->IsJoinEntry()) { |
2579 JoinEntryInstr* join = block_entry->AsJoinEntry(); | 2587 JoinEntryInstr* join = block_entry->AsJoinEntry(); |
2580 if (join->phis() != NULL) { | 2588 if (join->phis() != NULL) { |
2581 for (intptr_t i = 0; i < join->phis()->length(); ++i) { | 2589 for (intptr_t i = 0; i < join->phis()->length(); ++i) { |
2582 PhiInstr* phi = (*join->phis())[i]; | 2590 PhiInstr* phi = (*join->phis())[i]; |
2583 if (phi != NULL) { | 2591 if (phi != NULL) { |
2584 (*env)[i] = new UseVal(phi); | 2592 (*env)[i] = new UseVal(phi); |
2585 phi->set_ssa_temp_index(alloc_ssa_temp_index()); // New SSA temp. | 2593 phi->set_ssa_temp_index(alloc_ssa_temp_index()); // New SSA temp. |
2586 } | 2594 } |
2587 } | 2595 } |
2588 } | 2596 } |
2589 } | 2597 } |
2590 | 2598 |
2591 // 2. Process normal instructions. | 2599 // 2. Process normal instructions. |
2592 for (ForwardInstructionIterator it(block_entry); !it.Done(); it.Advance()) { | 2600 for (ForwardInstructionIterator it(block_entry); !it.Done(); it.Advance()) { |
2593 Instruction* current = it.Current(); | 2601 Instruction* current = it.Current(); |
2594 // Attach current environment to the instruction. | 2602 // Attach current environment to the instruction. |
2595 // TODO(fschneider): Currently each instruction gets a full copy of the | 2603 // TODO(fschneider): Currently each instruction gets a full copy of the |
2596 // environment. This should be optimized: Only instructions that can | 2604 // environment. This should be optimized: Only instructions that can |
2597 // deoptimize should have uses of the environment values. | 2605 // deoptimize should have uses of the environment values. |
2598 current->set_env(new Environment(*env)); | 2606 current->set_env(new Environment(*env, fixed_parameter_count)); |
2599 | 2607 |
2600 // 2a. Handle uses: | 2608 // 2a. Handle uses: |
2601 // Update expression stack environment for each use. | 2609 // Update expression stack environment for each use. |
2602 // For each use of a LoadLocal or StoreLocal: Replace it with the value | 2610 // For each use of a LoadLocal or StoreLocal: Replace it with the value |
2603 // from the environment. | 2611 // from the environment. |
2604 for (intptr_t i = 0; i < current->InputCount(); ++i) { | 2612 for (intptr_t i = 0; i < current->InputCount(); ++i) { |
2605 Value* v = current->InputAt(i); | 2613 Value* v = current->InputAt(i); |
2606 if (!v->IsUse()) continue; | 2614 if (!v->IsUse()) continue; |
2607 // Update expression stack. | 2615 // Update expression stack. |
2608 ASSERT(env->length() > var_count); | 2616 ASSERT(env->length() > var_count); |
2609 env->RemoveLast(); | 2617 env->RemoveLast(); |
2610 BindInstr* as_bind = v->AsUse()->definition()->AsBind(); | 2618 BindInstr* as_bind = v->AsUse()->definition()->AsBind(); |
2611 if ((as_bind != NULL) && as_bind->computation()->IsLoadLocal()) { | 2619 if ((as_bind != NULL) && as_bind->computation()->IsLoadLocal()) { |
2612 Computation* comp = as_bind->computation(); | 2620 Computation* comp = as_bind->computation(); |
2613 intptr_t index = comp->AsLoadLocal()->local().BitIndexIn(var_count); | 2621 intptr_t index = |
| 2622 comp->AsLoadLocal()->local().BitIndexIn(fixed_parameter_count); |
2614 current->SetInputAt(i, CopyValue((*env)[index])); | 2623 current->SetInputAt(i, CopyValue((*env)[index])); |
2615 } | 2624 } |
2616 if ((as_bind != NULL) && as_bind->computation()->IsStoreLocal()) { | 2625 if ((as_bind != NULL) && as_bind->computation()->IsStoreLocal()) { |
2617 // For each use of a StoreLocal: Replace it with the value from the | 2626 // For each use of a StoreLocal: Replace it with the value from the |
2618 // environment. | 2627 // environment. |
2619 Computation* comp = as_bind->computation(); | 2628 Computation* comp = as_bind->computation(); |
2620 intptr_t index = comp->AsStoreLocal()->local().BitIndexIn(var_count); | 2629 intptr_t index = |
| 2630 comp->AsStoreLocal()->local().BitIndexIn(fixed_parameter_count); |
2621 current->SetInputAt(i, CopyValue((*env)[index])); | 2631 current->SetInputAt(i, CopyValue((*env)[index])); |
2622 } | 2632 } |
2623 } | 2633 } |
2624 | 2634 |
2625 // 2b. Handle LoadLocal and StoreLocal. | 2635 // 2b. Handle LoadLocal and StoreLocal. |
2626 // For each LoadLocal: Remove it from the graph. | 2636 // For each LoadLocal: Remove it from the graph. |
2627 // For each StoreLocal: Remove it from the graph and update the environment. | 2637 // For each StoreLocal: Remove it from the graph and update the environment. |
2628 BindInstr* bind = current->AsBind(); | 2638 BindInstr* bind = current->AsBind(); |
2629 if (bind != NULL) { | 2639 if (bind != NULL) { |
2630 LoadLocalComp* load = bind->computation()->AsLoadLocal(); | 2640 LoadLocalComp* load = bind->computation()->AsLoadLocal(); |
2631 StoreLocalComp* store = bind->computation()->AsStoreLocal(); | 2641 StoreLocalComp* store = bind->computation()->AsStoreLocal(); |
2632 if ((load != NULL) || (store != NULL)) { | 2642 if ((load != NULL) || (store != NULL)) { |
2633 intptr_t index; | 2643 intptr_t index; |
2634 if (store != NULL) { | 2644 if (store != NULL) { |
2635 index = store->local().BitIndexIn(var_count); | 2645 index = store->local().BitIndexIn(fixed_parameter_count); |
2636 // Update renaming environment. | 2646 // Update renaming environment. |
2637 (*env)[index] = store->value(); | 2647 (*env)[index] = store->value(); |
2638 } else { | 2648 } else { |
2639 // The graph construction ensures we do not have an unused LoadLocal | 2649 // The graph construction ensures we do not have an unused LoadLocal |
2640 // computation. | 2650 // computation. |
2641 ASSERT(bind->is_used()); | 2651 ASSERT(bind->is_used()); |
2642 index = load->local().BitIndexIn(var_count); | 2652 index = load->local().BitIndexIn(fixed_parameter_count); |
2643 } | 2653 } |
2644 // Update expression stack and remove from graph. | 2654 // Update expression stack and remove from graph. |
2645 if (bind->is_used()) { | 2655 if (bind->is_used()) { |
2646 env->Add(CopyValue((*env)[index])); | 2656 env->Add(CopyValue((*env)[index])); |
2647 } | 2657 } |
2648 it.RemoveCurrentFromGraph(); | 2658 it.RemoveCurrentFromGraph(); |
2649 } else { | 2659 } else { |
2650 // Not a load or store. | 2660 // Not a load or store. |
2651 if (bind->is_used()) { | 2661 if (bind->is_used()) { |
2652 // Assign fresh SSA temporary and update expression stack. | 2662 // Assign fresh SSA temporary and update expression stack. |
2653 bind->set_ssa_temp_index(alloc_ssa_temp_index()); | 2663 bind->set_ssa_temp_index(alloc_ssa_temp_index()); |
2654 env->Add(new UseVal(bind)); | 2664 env->Add(new UseVal(bind)); |
2655 } | 2665 } |
2656 } | 2666 } |
2657 } | 2667 } |
2658 } | 2668 } |
2659 | 2669 |
2660 // 3. Process dominated blocks. | 2670 // 3. Process dominated blocks. |
2661 for (intptr_t i = 0; i < block_entry->dominated_blocks().length(); ++i) { | 2671 for (intptr_t i = 0; i < block_entry->dominated_blocks().length(); ++i) { |
2662 BlockEntryInstr* block = block_entry->dominated_blocks()[i]; | 2672 BlockEntryInstr* block = block_entry->dominated_blocks()[i]; |
2663 GrowableArray<Value*> new_env(env->length()); | 2673 GrowableArray<Value*> new_env(env->length()); |
2664 new_env.AddArray(*env); | 2674 new_env.AddArray(*env); |
2665 RenameRecursive(block, &new_env, var_count); | 2675 RenameRecursive(block, &new_env, var_count, fixed_parameter_count); |
2666 } | 2676 } |
2667 | 2677 |
2668 // 4. Process successor block. We have edge-split form, so that only blocks | 2678 // 4. Process successor block. We have edge-split form, so that only blocks |
2669 // with one successor can have a join block as successor. | 2679 // with one successor can have a join block as successor. |
2670 if ((block_entry->last_instruction()->SuccessorCount() == 1) && | 2680 if ((block_entry->last_instruction()->SuccessorCount() == 1) && |
2671 block_entry->last_instruction()->SuccessorAt(0)->IsJoinEntry()) { | 2681 block_entry->last_instruction()->SuccessorAt(0)->IsJoinEntry()) { |
2672 JoinEntryInstr* successor = | 2682 JoinEntryInstr* successor = |
2673 block_entry->last_instruction()->SuccessorAt(0)->AsJoinEntry(); | 2683 block_entry->last_instruction()->SuccessorAt(0)->AsJoinEntry(); |
2674 intptr_t pred_index = successor->IndexOfPredecessor(block_entry); | 2684 intptr_t pred_index = successor->IndexOfPredecessor(block_entry); |
2675 ASSERT(pred_index >= 0); | 2685 ASSERT(pred_index >= 0); |
(...skipping 20 matching lines...) Expand all Loading... |
2696 char* chars = reinterpret_cast<char*>( | 2706 char* chars = reinterpret_cast<char*>( |
2697 Isolate::Current()->current_zone()->Allocate(len)); | 2707 Isolate::Current()->current_zone()->Allocate(len)); |
2698 OS::SNPrint(chars, len, kFormat, function_name, reason); | 2708 OS::SNPrint(chars, len, kFormat, function_name, reason); |
2699 const Error& error = Error::Handle( | 2709 const Error& error = Error::Handle( |
2700 LanguageError::New(String::Handle(String::New(chars)))); | 2710 LanguageError::New(String::Handle(String::New(chars)))); |
2701 Isolate::Current()->long_jump_base()->Jump(1, error); | 2711 Isolate::Current()->long_jump_base()->Jump(1, error); |
2702 } | 2712 } |
2703 | 2713 |
2704 | 2714 |
2705 } // namespace dart | 2715 } // namespace dart |
OLD | NEW |