Enable redundancy elimination for array loads.

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/bit_vector.h"
 #include "vm/cha.h"
 #include "vm/flow_graph_builder.h"
 #include "vm/flow_graph_compiler.h"
@@ skipping 2456 matching lines @@
             TryHoistCheckSmiThroughPhi(
                 &it, header, pre_header, current->AsCheckSmi());
           }
         }
       }
     }
   }
 }
 
 
+static bool IsLoadEliminationCandidate(Definition* def) {
+  // Immutable loads (not affected by side effects) are handled
+  // in the DominatorBasedCSE pass.
+  // TODO(fschneider): Extend to other load instructions.
+  return (def->IsLoadField() && def->AffectedBySideEffect())
+      || def->IsLoadIndexed();
+}
+
+
 static intptr_t NumberLoadExpressions(FlowGraph* graph) {
   DirectChainedHashMap<Definition*> map;
   intptr_t expr_id = 0;
   for (BlockIterator it = graph->reverse_postorder_iterator();
        !it.Done();
        it.Advance()) {
     BlockEntryInstr* block = it.Current();
     for (ForwardInstructionIterator instr_it(block);
          !instr_it.Done();
          instr_it.Advance()) {
       Definition* defn = instr_it.Current()->AsDefinition();
-      if ((defn == NULL) ||
-          !defn->IsLoadField() ||
-          !defn->AffectedBySideEffect()) {
-        // TODO(fschneider): Extend to other load instructions.
+      if ((defn == NULL) || !IsLoadEliminationCandidate(defn)) {
         continue;
       }
       Definition* result = map.Lookup(defn);
       if (result == NULL) {
         map.Insert(defn);
         defn->set_expr_id(expr_id++);
       } else {
         defn->set_expr_id(result->expr_id());
       }
     }
@@ skipping 24 matching lines @@
     intptr_t preorder_number = block->preorder_number();
     for (BackwardInstructionIterator instr_it(block);
          !instr_it.Done();
          instr_it.Advance()) {
       Instruction* instr = instr_it.Current();
       if (instr->HasSideEffect()) {
         avail_kill[preorder_number]->SetAll();
         break;
       }
       Definition* defn = instr_it.Current()->AsDefinition();
-      if ((defn == NULL) ||
-          !defn->IsLoadField() ||
-          !defn->AffectedBySideEffect()) {
-        // TODO(fschneider): Extend to other load instructions.
+      if ((defn == NULL) || !IsLoadEliminationCandidate(defn)) {
         continue;
       }
       avail_gen[preorder_number]->Add(defn->expr_id());
     }
     avail_out[preorder_number]->CopyFrom(avail_gen[preorder_number]);
   }
 
   BitVector* temp = new BitVector(avail_in[0]->length());
 
   bool changed = true;
@@ skipping 31 matching lines @@
       }
       if (!temp->Equals(*block_in)) {
         block_in->CopyFrom(temp);
         if (block_out->KillAndAdd(block_kill, block_gen)) changed = true;
       }
     }
   }
 }
 
 
-static void OptimizeLoads(
+static bool OptimizeLoads(
     BlockEntryInstr* block,
     GrowableArray<Definition*>* definitions,
     const GrowableArray<BitVector*>& avail_in) {
   // TODO(fschneider): Factor out code shared with the existing CSE pass.
 
   // Delete loads that are killed (not available) at the entry.
   intptr_t pre_num = block->preorder_number();
   ASSERT(avail_in[pre_num]->length() == definitions->length());
   for (intptr_t i = 0; i < avail_in[pre_num]->length(); i++) {
     if (!avail_in[pre_num]->Contains(i)) {
       (*definitions)[i] = NULL;
     }
   }
 
+  bool changed = false;
   for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) {
     Instruction* instr = it.Current();
     if (instr->HasSideEffect()) {
       // Handle local side effects by clearing current definitions.
       for (intptr_t i = 0; i < definitions->length(); i++) {
         (*definitions)[i] = NULL;
       }
       continue;
     }
     Definition* defn = instr->AsDefinition();
-    if ((defn == NULL) ||
-        !defn->IsLoadField() ||
-        !defn->AffectedBySideEffect()) {
-      // Immutable loads are handled in normal CSE.
-      // TODO(fschneider): Extend to other load instructions.
+    if ((defn == NULL) || !IsLoadEliminationCandidate(defn)) {
       continue;
     }
     Definition* result = (*definitions)[defn->expr_id()];
     if (result == NULL) {
       (*definitions)[defn->expr_id()] = defn;
       continue;
     }
 
     // Replace current with lookup result.
     defn->ReplaceUsesWith(result);
     it.RemoveCurrentFromGraph();
+    changed = true;
     if (FLAG_trace_optimization) {
       OS::Print("Replacing load v%"Pd" with v%"Pd"\n",
                 defn->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) {
       GrowableArray<Definition*> child_defs(definitions->length());
       child_defs.AddArray(*definitions);
-      OptimizeLoads(child, &child_defs, avail_in);
+      changed = OptimizeLoads(child, &child_defs, avail_in) || changed;
     } else {
-      OptimizeLoads(child, definitions, avail_in);
+      changed = OptimizeLoads(child, definitions, avail_in) || changed;
     }
   }
+  return changed;
 }
 
 
-void DominatorBasedCSE::Optimize(FlowGraph* graph) {
+bool DominatorBasedCSE::Optimize(FlowGraph* graph) {
+  bool changed = false;
   if (FLAG_load_cse) {
     intptr_t max_expr_id = NumberLoadExpressions(graph);
     if (max_expr_id > 0) {
       intptr_t num_blocks = graph->preorder().length();
       GrowableArray<BitVector*> avail_in(num_blocks);
       for (intptr_t i = 0; i < num_blocks; i++) {
         avail_in.Add(new BitVector(max_expr_id));
       }
 
       ComputeAvailableLoads(graph, max_expr_id, avail_in);
 
       GrowableArray<Definition*> definitions(max_expr_id);
       for (intptr_t j = 0; j < max_expr_id ; j++) {
         definitions.Add(NULL);
       }
-
-      OptimizeLoads(graph->graph_entry(), &definitions, avail_in);
+      changed = OptimizeLoads(graph->graph_entry(), &definitions, avail_in);
     }
   }
 
   DirectChainedHashMap<Instruction*> map;
-  OptimizeRecursive(graph->graph_entry(), &map);
+  changed = OptimizeRecursive(graph->graph_entry(), &map) || changed;
+
+  return changed;
 }
 
 
-void DominatorBasedCSE::OptimizeRecursive(
+bool DominatorBasedCSE::OptimizeRecursive(
     BlockEntryInstr* block,
     DirectChainedHashMap<Instruction*>* map) {
+  bool changed = false;
   for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) {
     Instruction* current = it.Current();
     if (current->AffectedBySideEffect()) continue;
     Instruction* replacement = map->Lookup(current);
     if (replacement == NULL) {
       map->Insert(current);
       continue;
     }
     // Replace current with lookup result.
     ReplaceCurrentInstruction(&it, current, replacement);
+    changed = true;
   }
 
   // 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<Instruction*> child_map(*map);  // Copy map.
-      OptimizeRecursive(child, &child_map);
+      changed = OptimizeRecursive(child, &child_map) || changed;
     } else {
-      OptimizeRecursive(child, map);  // Reuse map for the last child.
+      // Reuse map for the last child.
+      changed = OptimizeRecursive(child, map) || changed;
     }
   }
+  return changed;
 }
 
 
 ConstantPropagator::ConstantPropagator(
     FlowGraph* graph,
     const GrowableArray<BlockEntryInstr*>& ignored)
     : FlowGraphVisitor(ignored),
       graph_(graph),
       unknown_(Object::ZoneHandle(Object::transition_sentinel())),
       non_constant_(Object::ZoneHandle(Object::sentinel())),
@@ skipping 747 matching lines @@
 
   if (FLAG_trace_constant_propagation) {
     OS::Print("\n==== After constant propagation ====\n");
     FlowGraphPrinter printer(*graph_);
     printer.PrintBlocks();
   }
 }
 
 
 }  // namespace dart