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

Side by Side Diff: runtime/vm/flow_graph_optimizer.cc

Issue 10872035: Add a simple dominator based redundancy elimination. (Closed) Base URL: http://dart.googlecode.com/svn/branches/bleeding_edge/dart/
Patch Set: Created 8 years, 3 months 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 | « runtime/vm/flow_graph_optimizer.h ('k') | runtime/vm/hash_map.h » ('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_optimizer.h" 5 #include "vm/flow_graph_optimizer.h"
6 6
7 #include "vm/cha.h" 7 #include "vm/cha.h"
8 #include "vm/flow_graph_builder.h" 8 #include "vm/flow_graph_builder.h"
9 #include "vm/hash_map.h" 9 #include "vm/hash_map.h"
10 #include "vm/il_printer.h" 10 #include "vm/il_printer.h"
(...skipping 937 matching lines...) Expand 10 before | Expand all | Expand 10 after
948 LocationSummary* locs = it.Current()->locs(); 948 LocationSummary* locs = it.Current()->locs();
949 if ((locs != NULL) && locs->can_call()) { 949 if ((locs != NULL) && locs->can_call()) {
950 is_leaf_ = false; 950 is_leaf_ = false;
951 return; 951 return;
952 } 952 }
953 } 953 }
954 } 954 }
955 } 955 }
956 956
957 957
958 void LocalCSE::Optimize() { 958 void DominatorBasedCSE::Optimize(BlockEntryInstr* graph_entry) {
959 for (intptr_t i = 0; i < blocks_.length(); ++i) { 959 ASSERT(graph_entry->IsGraphEntry());
960 BlockEntryInstr* entry = blocks_[i]; 960 DirectChainedHashMap<BindInstr*> map;
961 DirectChainedHashMap<BindInstr*> map; 961 OptimizeRecursive(graph_entry, &map);
962 ASSERT(map.IsEmpty()); 962 }
963 for (ForwardInstructionIterator it(entry); !it.Done(); it.Advance()) { 963
964 BindInstr* instr = it.Current()->AsBind(); 964
965 if (instr == NULL || instr->computation()->HasSideEffect()) continue; 965 void DominatorBasedCSE::OptimizeRecursive(
966 BindInstr* result = map.Lookup(instr); 966 BlockEntryInstr* block,
967 if (result == NULL) { 967 DirectChainedHashMap<BindInstr*>* map) {
968 map.Insert(instr); 968 for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) {
969 continue; 969 BindInstr* instr = it.Current()->AsBind();
970 } 970 if (instr == NULL || instr->computation()->HasSideEffect()) continue;
971 // Replace current with lookup result. 971 BindInstr* result = map->Lookup(instr);
972 instr->ReplaceUsesWith(result); 972 if (result == NULL) {
973 it.RemoveCurrentFromGraph(); 973 map->Insert(instr);
974 if (FLAG_trace_optimization) { 974 continue;
975 OS::Print("Replacing v%d with v%d\n", 975 }
976 instr->ssa_temp_index(), 976 // Replace current with lookup result.
977 result->ssa_temp_index()); 977 instr->ReplaceUsesWith(result);
978 } 978 it.RemoveCurrentFromGraph();
979 if (FLAG_trace_optimization) {
980 OS::Print("Replacing v%d with v%d\n",
981 instr->ssa_temp_index(),
982 result->ssa_temp_index());
983 }
984 }
985
986 // Process children in the dominator tree recursively.
987 intptr_t num_children = block->dominated_blocks().length();
988 for (intptr_t i = 0; i < num_children; ++i) {
989 BlockEntryInstr* child = block->dominated_blocks()[i];
990 if (i < num_children - 1) {
Kevin Millikin (Google) 2012/08/23 13:12:39 There's an extra space here for some reason.
Florian Schneider 2012/08/23 13:17:50 Done.
991 DirectChainedHashMap<BindInstr*> child_map(*map); // Copy map.
992 OptimizeRecursive(child, &child_map);
993 } else {
994 OptimizeRecursive(child, map); // Reuse map for the last child.
979 } 995 }
980 } 996 }
981 } 997 }
982 998
983 999
984 } // namespace dart 1000 } // namespace dart
OLDNEW
« no previous file with comments | « runtime/vm/flow_graph_optimizer.h ('k') | runtime/vm/hash_map.h » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698