Implement better side effect tracking for load-to-load forwarding.

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 2758 matching lines @@
 
 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) {
+static intptr_t ComputeLoadOffsetInWords(Definition* defn) {
+  if (defn->IsLoadIndexed()) {
+    // We are assuming that LoadField is never used to load the first word.
+    return 0;
+  }
+
+  LoadFieldInstr* load_field = defn->AsLoadField();
+  if (load_field != NULL) {
+    const intptr_t idx = load_field->offset_in_bytes() / kWordSize;
+    ASSERT(idx > 0);
+    return idx;
+  }
+
+  UNREACHABLE();
+  return 0;
+}
+
+
+static bool IsInterferingStore(Instruction* instr,
+                               intptr_t* offset_in_words) {
+  if (instr->IsStoreIndexed()) {
+    // We are assuming that LoadField is never used to load the first word.
+    *offset_in_words = 0;
+    return true;
+  }
+
+  StoreInstanceFieldInstr* store_instance_field = instr->AsStoreInstanceField();
+  if (store_instance_field != NULL) {
+    ASSERT(store_instance_field->field().Offset() != 0);
+    *offset_in_words = store_instance_field->field().Offset() / kWordSize;
+    return true;
+  }
+
+  StoreVMFieldInstr* store_vm_field = instr->AsStoreVMField();
+  if (store_vm_field != NULL) {
+    ASSERT(store_vm_field->offset_in_bytes() != 0);
+    *offset_in_words = store_vm_field->offset_in_bytes() / kWordSize;
+    return true;
+  }
+
+  return false;
+}
+
+
+static intptr_t NumberLoadExpressions(
+    FlowGraph* graph,
+    GrowableArray<BitVector*>* kill_by_offs) {
   DirectChainedHashMap<PointerKeyValueTrait<Definition> > map;
   intptr_t expr_id = 0;
+
+  // Loads representing different expression ids will be collected and
+  // used to build per offset kill sets.
+  GrowableArray<Definition*> loads(10);
+
   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) || !IsLoadEliminationCandidate(defn)) {
         continue;
       }
       Definition* result = map.Lookup(defn);
       if (result == NULL) {
         map.Insert(defn);
         defn->set_expr_id(expr_id++);
+        loads.Add(defn);
       } else {
         defn->set_expr_id(result->expr_id());
       }
     }
   }
+
+  // Build per offset kill sets. Any store interferes only with loads from
+  // the same offset.
+  for (intptr_t i = 0; i < loads.length(); i++) {
+    Definition* defn = loads[i];
+
+    const intptr_t offset_in_words = ComputeLoadOffsetInWords(defn);
+    while (kill_by_offs->length() <= offset_in_words) {
+      kill_by_offs->Add(NULL);
+    }
+    if ((*kill_by_offs)[offset_in_words] == NULL) {
+      (*kill_by_offs)[offset_in_words] = new BitVector(expr_id);
+    }
+    (*kill_by_offs)[offset_in_words]->Add(defn->expr_id());
+  }
+
+
   return expr_id;
 }
 
 
 static void ComputeAvailableLoads(
     FlowGraph* graph,
     intptr_t max_expr_id,
-    const GrowableArray<BitVector*>& avail_in) {
+    const GrowableArray<BitVector*>& avail_in,
+    const GrowableArray<BitVector*>& kill_by_offs) {
   // Initialize gen-, kill-, out-sets.
   intptr_t num_blocks = graph->preorder().length();
   GrowableArray<BitVector*> avail_out(num_blocks);
   GrowableArray<BitVector*> avail_gen(num_blocks);
   GrowableArray<BitVector*> avail_kill(num_blocks);
   for (intptr_t i = 0; i < num_blocks; i++) {
     avail_out.Add(new BitVector(max_expr_id));
     avail_gen.Add(new BitVector(max_expr_id));
     avail_kill.Add(new BitVector(max_expr_id));
   }
 
   for (BlockIterator block_it = graph->reverse_postorder_iterator();
        !block_it.Done();
        block_it.Advance()) {
     BlockEntryInstr* block = block_it.Current();
     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()) {
+
+      intptr_t offset_in_words = 0;
+      if (IsInterferingStore(instr, &offset_in_words)) {
+        if ((offset_in_words < kill_by_offs.length()) &&
+            (kill_by_offs[offset_in_words] != NULL)) {
+          avail_kill[preorder_number]->AddAll(kill_by_offs[offset_in_words]);
+        }
+      } else if (instr->HasSideEffect()) {
         avail_kill[preorder_number]->SetAll();
         break;
       }
       Definition* defn = instr_it.Current()->AsDefinition();
       if ((defn == NULL) || !IsLoadEliminationCandidate(defn)) {
         continue;
       }
-      avail_gen[preorder_number]->Add(defn->expr_id());
+
+      const intptr_t expr_id = defn->expr_id();
+      if (!avail_kill[preorder_number]->Contains(expr_id)) {
+        avail_gen[preorder_number]->Add(expr_id);
+      }
     }
     avail_out[preorder_number]->CopyFrom(avail_gen[preorder_number]);
   }
 
   BitVector* temp = new BitVector(avail_in[0]->length());
 
   bool changed = true;
   while (changed) {
     changed = false;
 
@@ skipping 31 matching lines @@
         if (block_out->KillAndAdd(block_kill, block_gen)) changed = true;
       }
     }
   }
 }
 
 
 static bool OptimizeLoads(
     BlockEntryInstr* block,
     GrowableArray<Definition*>* definitions,
-    const GrowableArray<BitVector*>& avail_in) {
+    const GrowableArray<BitVector*>& avail_in,
+    const GrowableArray<BitVector*>& kill_by_offs) {
   // 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()) {
+
+    intptr_t offset_in_words = 0;
+    if (IsInterferingStore(instr, &offset_in_words)) {
+      if ((offset_in_words < kill_by_offs.length()) &&
+          (kill_by_offs[offset_in_words] != NULL)) {
+        for (BitVector::Iterator it(kill_by_offs[offset_in_words]);
+             !it.Done();
+             it.Advance()) {
+          (*definitions)[it.Current()] = NULL;
+        }
+      }

[Florian Schneider, 2012/11/29 13:42:48]

Maybe continue already here since IsInterferingStore implies 
IsLoadEliminatationCandidate(instr).

ASSERT(!IsLoadEliminationCandidate(instr))
continue;

+    } else 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) || !IsLoadEliminationCandidate(defn)) {
       continue;
     }
@@ skipping 14 matching lines @@
     }
   }
 
   // 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);
-      changed = OptimizeLoads(child, &child_defs, avail_in) || changed;
+      changed = OptimizeLoads(child, &child_defs, avail_in, kill_by_offs) ||
+                changed;
     } else {
-      changed = OptimizeLoads(child, definitions, avail_in) || changed;
+      changed = OptimizeLoads(child, definitions, avail_in, kill_by_offs) ||
+                changed;
     }
   }
   return changed;
 }
 
 
 bool DominatorBasedCSE::Optimize(FlowGraph* graph) {
   bool changed = false;
   if (FLAG_load_cse) {
-    intptr_t max_expr_id = NumberLoadExpressions(graph);
+    GrowableArray<BitVector*> kill_by_offs(10);
+    intptr_t max_expr_id = NumberLoadExpressions(graph, &kill_by_offs);
     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);
+      ComputeAvailableLoads(graph, max_expr_id, avail_in, kill_by_offs);
 
       GrowableArray<Definition*> definitions(max_expr_id);
       for (intptr_t j = 0; j < max_expr_id ; j++) {
         definitions.Add(NULL);
       }
-      changed = OptimizeLoads(graph->graph_entry(), &definitions, avail_in);
+      changed = OptimizeLoads(
+          graph->graph_entry(), &definitions, avail_in, kill_by_offs);
     }
   }
 
   DirectChainedHashMap<PointerKeyValueTrait<Instruction> > map;
   changed = OptimizeRecursive(graph->graph_entry(), &map) || changed;
 
   return changed;
 }
 
 
@@ skipping 824 matching lines @@
 
   if (FLAG_trace_constant_propagation) {
     OS::Print("\n==== After constant propagation ====\n");
     FlowGraphPrinter printer(*graph_);
     printer.PrintBlocks();
   }
 }
 
 
 }  // namespace dart