Reland "Add a simple dominator based redundancy elimination" and fix a register allocation bug.

runtime/vm/flow_graph_optimizer.cc

 // Copyright (c) 2012, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 #include "vm/flow_graph_optimizer.h"
 
 #include "vm/cha.h"
 #include "vm/flow_graph_builder.h"
 #include "vm/hash_map.h"
 #include "vm/il_printer.h"
@@ skipping 937 matching lines @@
       LocationSummary* locs = it.Current()->locs();
       if ((locs != NULL) && locs->can_call()) {
         is_leaf_ = false;
         return;
       }
     }
   }
 }
 
 
-void LocalCSE::Optimize() {
-  for (intptr_t i = 0; i < blocks_.length(); ++i) {
-    BlockEntryInstr* entry = blocks_[i];
-    DirectChainedHashMap<BindInstr*> map;
-    ASSERT(map.IsEmpty());
-    for (ForwardInstructionIterator it(entry); !it.Done(); it.Advance()) {
-      BindInstr* instr = it.Current()->AsBind();
-      if (instr == NULL || instr->computation()->HasSideEffect()) continue;
-      BindInstr* result = map.Lookup(instr);
-      if (result == NULL) {
-        map.Insert(instr);
-        continue;
-      }
-      // Replace current with lookup result.
-      instr->ReplaceUsesWith(result);
-      it.RemoveCurrentFromGraph();
-      if (FLAG_trace_optimization) {
-        OS::Print("Replacing v%d with v%d\n",
-                  instr->ssa_temp_index(),
-                  result->ssa_temp_index());
-      }
+void DominatorBasedCSE::Optimize(BlockEntryInstr* graph_entry) {
+  ASSERT(graph_entry->IsGraphEntry());
+  DirectChainedHashMap<BindInstr*> map;
+  OptimizeRecursive(graph_entry, &map);
+}
+
+
+void DominatorBasedCSE::OptimizeRecursive(
+    BlockEntryInstr* block,
+    DirectChainedHashMap<BindInstr*>* map) {
+  for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) {
+    BindInstr* instr = it.Current()->AsBind();
+    if (instr == NULL || instr->computation()->HasSideEffect()) continue;
+    BindInstr* result = map->Lookup(instr);
+    if (result == NULL) {
+      map->Insert(instr);
+      continue;
+    }
+    // Replace current with lookup result.
+    instr->ReplaceUsesWith(result);
+    it.RemoveCurrentFromGraph();
+    if (FLAG_trace_optimization) {
+      OS::Print("Replacing v%d with v%d\n",
+                instr->ssa_temp_index(),
+                result->ssa_temp_index());
+    }
+  }
+
+  // Process children in the dominator tree recursively.
+  intptr_t num_children = block->dominated_blocks().length();
+  for (intptr_t i = 0; i < num_children; ++i) {
+    BlockEntryInstr* child = block->dominated_blocks()[i];
+    if (i  < num_children - 1) {
+      DirectChainedHashMap<BindInstr*> child_map(*map);  // Copy map.
+      OptimizeRecursive(child, &child_map);
+    } else {
+      OptimizeRecursive(child, map);  // Reuse map for the last child.
     }
   }
 }
 
 
 }  // namespace dart