Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(155)

Side by Side Diff: vm/flow_graph.cc

Issue 11348026: - GrowableArray::RemoveLast returns the value being removed (Closed) Base URL: http://dart.googlecode.com/svn/branches/bleeding_edge/dart/runtime/
Patch Set: Created 8 years, 1 month ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch | Annotate | Revision Log
« no previous file with comments | « no previous file | vm/flow_graph_allocator.cc » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
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
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
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
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
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
OLDNEW
« no previous file with comments | « no previous file | vm/flow_graph_allocator.cc » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698