| 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 457 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 468 for (intptr_t var_index = 0; var_index < variable_count(); ++var_index) { | 468 for (intptr_t var_index = 0; var_index < variable_count(); ++var_index) { |
| 469 // Add to the worklist each block containing an assignment. | 469 // Add to the worklist each block containing an assignment. |
| 470 for (intptr_t block_index = 0; block_index < block_count; ++block_index) { | 470 for (intptr_t block_index = 0; block_index < block_count; ++block_index) { |
| 471 if (assigned_vars[block_index]->Contains(var_index)) { | 471 if (assigned_vars[block_index]->Contains(var_index)) { |
| 472 work[block_index] = var_index; | 472 work[block_index] = var_index; |
| 473 worklist.Add(preorder[block_index]); | 473 worklist.Add(preorder[block_index]); |
| 474 } | 474 } |
| 475 } | 475 } |
| 476 | 476 |
| 477 while (!worklist.is_empty()) { | 477 while (!worklist.is_empty()) { |
| 478 BlockEntryInstr* current = worklist.Last(); | 478 BlockEntryInstr* current = worklist.RemoveLast(); |
| 479 worklist.RemoveLast(); | |
| 480 // Ensure a phi for each block in the dominance frontier of current. | 479 // Ensure a phi for each block in the dominance frontier of current. |
| 481 for (BitVector::Iterator it(dom_frontier[current->preorder_number()]); | 480 for (BitVector::Iterator it(dom_frontier[current->preorder_number()]); |
| 482 !it.Done(); | 481 !it.Done(); |
| 483 it.Advance()) { | 482 it.Advance()) { |
| 484 int index = it.Current(); | 483 int index = it.Current(); |
| 485 if (has_already[index] < var_index) { | 484 if (has_already[index] < var_index) { |
| 486 BlockEntryInstr* block = preorder[index]; | 485 BlockEntryInstr* block = preorder[index]; |
| 487 ASSERT(block->IsJoinEntry()); | 486 ASSERT(block->IsJoinEntry()); |
| 488 block->AsJoinEntry()->InsertPhi(var_index, variable_count()); | 487 block->AsJoinEntry()->InsertPhi(var_index, variable_count()); |
| 489 has_already[index] = var_index; | 488 has_already[index] = var_index; |
| (...skipping 87 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 577 | 576 |
| 578 // 2a. Handle uses: | 577 // 2a. Handle uses: |
| 579 // Update expression stack environment for each use. | 578 // Update expression stack environment for each use. |
| 580 // For each use of a LoadLocal or StoreLocal: Replace it with the value | 579 // For each use of a LoadLocal or StoreLocal: Replace it with the value |
| 581 // from the environment. | 580 // from the environment. |
| 582 for (intptr_t i = current->InputCount() - 1; i >= 0; --i) { | 581 for (intptr_t i = current->InputCount() - 1; i >= 0; --i) { |
| 583 Value* v = current->InputAt(i); | 582 Value* v = current->InputAt(i); |
| 584 // Update expression stack. | 583 // Update expression stack. |
| 585 ASSERT(env->length() > variable_count()); | 584 ASSERT(env->length() > variable_count()); |
| 586 | 585 |
| 587 Definition* reaching_defn = env->Last(); | 586 Definition* reaching_defn = env->RemoveLast(); |
| 588 env->RemoveLast(); | |
| 589 | 587 |
| 590 Definition* input_defn = v->definition(); | 588 Definition* input_defn = v->definition(); |
| 591 if (input_defn->IsLoadLocal() || input_defn->IsStoreLocal()) { | 589 if (input_defn->IsLoadLocal() || input_defn->IsStoreLocal()) { |
| 592 // Remove the load/store from the graph. | 590 // Remove the load/store from the graph. |
| 593 input_defn->RemoveFromGraph(); | 591 input_defn->RemoveFromGraph(); |
| 594 // Assert we are not referencing nulls in the initial environment. | 592 // Assert we are not referencing nulls in the initial environment. |
| 595 ASSERT(reaching_defn->ssa_temp_index() != -1); | 593 ASSERT(reaching_defn->ssa_temp_index() != -1); |
| 596 current->SetInputAt(i, new Value(reaching_defn)); | 594 current->SetInputAt(i, new Value(reaching_defn)); |
| 597 } | 595 } |
| 598 } | 596 } |
| (...skipping 76 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 675 phi->SetInputAt(pred_index, new Value((*env)[i])); | 673 phi->SetInputAt(pred_index, new Value((*env)[i])); |
| 676 } | 674 } |
| 677 } | 675 } |
| 678 } | 676 } |
| 679 } | 677 } |
| 680 } | 678 } |
| 681 | 679 |
| 682 | 680 |
| 683 void FlowGraph::MarkLivePhis(GrowableArray<PhiInstr*>* live_phis) { | 681 void FlowGraph::MarkLivePhis(GrowableArray<PhiInstr*>* live_phis) { |
| 684 while (!live_phis->is_empty()) { | 682 while (!live_phis->is_empty()) { |
| 685 PhiInstr* phi = live_phis->Last(); | 683 PhiInstr* phi = live_phis->RemoveLast(); |
| 686 live_phis->RemoveLast(); | |
| 687 for (intptr_t i = 0; i < phi->InputCount(); i++) { | 684 for (intptr_t i = 0; i < phi->InputCount(); i++) { |
| 688 Value* val = phi->InputAt(i); | 685 Value* val = phi->InputAt(i); |
| 689 PhiInstr* used_phi = val->definition()->AsPhi(); | 686 PhiInstr* used_phi = val->definition()->AsPhi(); |
| 690 if ((used_phi != NULL) && !used_phi->is_alive()) { | 687 if ((used_phi != NULL) && !used_phi->is_alive()) { |
| 691 used_phi->mark_alive(); | 688 used_phi->mark_alive(); |
| 692 live_phis->Add(used_phi); | 689 live_phis->Add(used_phi); |
| 693 } | 690 } |
| 694 } | 691 } |
| 695 } | 692 } |
| 696 } | 693 } |
| 697 | 694 |
| 698 | 695 |
| 699 // Find the natural loop for the back edge m->n and attach loop information | 696 // Find the natural loop for the back edge m->n and attach loop information |
| 700 // to block n (loop header). The algorithm is described in "Advanced Compiler | 697 // to block n (loop header). The algorithm is described in "Advanced Compiler |
| 701 // Design & Implementation" (Muchnick) p192. | 698 // Design & Implementation" (Muchnick) p192. |
| 702 static void FindLoop(BlockEntryInstr* m, | 699 static void FindLoop(BlockEntryInstr* m, |
| 703 BlockEntryInstr* n, | 700 BlockEntryInstr* n, |
| 704 intptr_t num_blocks) { | 701 intptr_t num_blocks) { |
| 705 GrowableArray<BlockEntryInstr*> stack; | 702 GrowableArray<BlockEntryInstr*> stack; |
| 706 BitVector* loop = new BitVector(num_blocks); | 703 BitVector* loop = new BitVector(num_blocks); |
| 707 | 704 |
| 708 loop->Add(n->preorder_number()); | 705 loop->Add(n->preorder_number()); |
| 709 if (n != m) { | 706 if (n != m) { |
| 710 loop->Add(m->preorder_number()); | 707 loop->Add(m->preorder_number()); |
| 711 stack.Add(m); | 708 stack.Add(m); |
| 712 } | 709 } |
| 713 | 710 |
| 714 while (!stack.is_empty()) { | 711 while (!stack.is_empty()) { |
| 715 BlockEntryInstr* p = stack.Last(); | 712 BlockEntryInstr* p = stack.RemoveLast(); |
| 716 stack.RemoveLast(); | |
| 717 for (intptr_t i = 0; i < p->PredecessorCount(); ++i) { | 713 for (intptr_t i = 0; i < p->PredecessorCount(); ++i) { |
| 718 BlockEntryInstr* q = p->PredecessorAt(i); | 714 BlockEntryInstr* q = p->PredecessorAt(i); |
| 719 if (!loop->Contains(q->preorder_number())) { | 715 if (!loop->Contains(q->preorder_number())) { |
| 720 loop->Add(q->preorder_number()); | 716 loop->Add(q->preorder_number()); |
| 721 stack.Add(q); | 717 stack.Add(q); |
| 722 } | 718 } |
| 723 } | 719 } |
| 724 } | 720 } |
| 725 n->set_loop_info(loop); | 721 n->set_loop_info(loop); |
| 726 if (FLAG_trace_optimization) { | 722 if (FLAG_trace_optimization) { |
| (...skipping 281 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1008 !it.Done(); | 1004 !it.Done(); |
| 1009 it.Advance()) { | 1005 it.Advance()) { |
| 1010 ++size; | 1006 ++size; |
| 1011 } | 1007 } |
| 1012 } | 1008 } |
| 1013 return size; | 1009 return size; |
| 1014 } | 1010 } |
| 1015 | 1011 |
| 1016 | 1012 |
| 1017 } // namespace dart | 1013 } // namespace dart |
| OLD | NEW |