Implement store 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 2811 matching lines @@
   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 Definition* GetStoredValue(Instruction* instr) {
+  if (instr->IsStoreIndexed()) {
+    return instr->AsStoreIndexed()->value()->definition();
+  }
+
+  StoreInstanceFieldInstr* store_instance_field = instr->AsStoreInstanceField();
+  if (store_instance_field != NULL) {
+    return store_instance_field->value()->definition();
+  }
+
+  StoreVMFieldInstr* store_vm_field = instr->AsStoreVMField();
+  if (store_vm_field != NULL) {
+    return store_vm_field->value()->definition();
+  }
+
+  UNREACHABLE();  // Should only be called for supported store instructions.
+  return NULL;
+}
+
+
+// KeyValueTrait used for numbering of loads. Allows to lookup loads
+// corresponding to stores.
+class LoadKeyValueTrait {
+ public:
+  typedef Definition* Value;
+  typedef Definition* Key;
+  typedef Definition* Pair;
+
+  static Key KeyOf(Pair kv) {
+    return kv;
+  }
+
+  static Value ValueOf(Pair kv) {
+    return kv;
+  }
+
+  static inline intptr_t Hashcode(Key key) {
+    intptr_t object = 0;
+    intptr_t location = 0;
+
+    if (key->IsLoadIndexed()) {
+      LoadIndexedInstr* load_indexed = key->AsLoadIndexed();
+      object = load_indexed->array()->definition()->ssa_temp_index();
+      location = load_indexed->index()->definition()->ssa_temp_index();
+    } else if (key->IsStoreIndexed()) {
+      StoreIndexedInstr* store_indexed = key->AsStoreIndexed();
+      object = store_indexed->array()->definition()->ssa_temp_index();
+      location = store_indexed->index()->definition()->ssa_temp_index();
+    } else if (key->IsLoadField()) {
+      LoadFieldInstr* load_field = key->AsLoadField();
+      object = load_field->value()->definition()->ssa_temp_index();
+      location = load_field->offset_in_bytes();
+    } else if (key->IsStoreInstanceField()) {
+      StoreInstanceFieldInstr* store_field = key->AsStoreInstanceField();
+      object = store_field->instance()->definition()->ssa_temp_index();
+      location = store_field->field().Offset();
+    } else if (key->IsStoreVMField()) {
+      StoreVMFieldInstr* store_field = key->AsStoreVMField();
+      object = store_field->dest()->definition()->ssa_temp_index();
+      location = store_field->offset_in_bytes();
+    }
+
+    return object * 31 + location;
+  }
+
+  static inline bool IsKeyEqual(Pair kv, Key key) {
+    if (kv->Equals(key)) return true;
+
+    if (kv->IsLoadIndexed()) {
+      if (key->IsStoreIndexed()) {
+        LoadIndexedInstr* load_indexed = kv->AsLoadIndexed();
+        StoreIndexedInstr* store_indexed = key->AsStoreIndexed();
+        return load_indexed->array()->Equals(store_indexed->array()) &&
+               load_indexed->index()->Equals(store_indexed->index());
+      }
+      return false;
+    }
+
+    ASSERT(kv->IsLoadField());
+    LoadFieldInstr* load_field = kv->AsLoadField();
+    if (key->IsStoreVMField()) {
+      StoreVMFieldInstr* store_field = key->AsStoreVMField();
+      return load_field->value()->Equals(store_field->dest()) &&
+             (load_field->offset_in_bytes() == store_field->offset_in_bytes());
+    } else if (key->IsStoreInstanceField()) {
+      StoreInstanceFieldInstr* store_field = key->AsStoreInstanceField();
+      return load_field->value()->Equals(store_field->instance()) &&
+             (load_field->offset_in_bytes() == store_field->field().Offset());
+    }
+
+    return false;
+  }
+};
+
+
 static intptr_t NumberLoadExpressions(
     FlowGraph* graph,
+    DirectChainedHashMap<LoadKeyValueTrait>* map,
     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);
+      Definition* result = map->Lookup(defn);
       if (result == NULL) {
-        map.Insert(defn);
+        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;
 }
 
 
 class LoadOptimizer : public ValueObject {
  public:
   LoadOptimizer(FlowGraph* graph,
                 intptr_t max_expr_id,
+                DirectChainedHashMap<LoadKeyValueTrait>* map,
                 const GrowableArray<BitVector*>& kill_by_offset)
       : graph_(graph),
+        map_(map),
         max_expr_id_(max_expr_id),
         kill_by_offset_(kill_by_offset),
         in_(graph_->preorder().length()),
         out_(graph_->preorder().length()),
         gen_(graph_->preorder().length()),
         kill_(graph_->preorder().length()),
         exposed_values_(graph_->preorder().length()),
         out_values_(graph_->preorder().length()),
         phis_(5),
         worklist_(5),
@@ skipping 45 matching lines @@
         intptr_t offset_in_words = 0;
         if (IsInterferingStore(instr, &offset_in_words)) {
           // Interfering stores kill only loads from the same offset.
           if ((offset_in_words < kill_by_offset_.length()) &&
               (kill_by_offset_[offset_in_words] != NULL)) {
             kill->AddAll(kill_by_offset_[offset_in_words]);
             // There is no need to clear out_values when clearing GEN set
             // because only those values that are in the GEN set
             // will ever be used.
             gen->RemoveAll(kill_by_offset_[offset_in_words]);
+
+            Definition* load = map_->Lookup(instr->AsDefinition());
+            if (load != NULL) {
+              // Store has a corresponding numbered load. Try forwarding
+              // stored value to it.
+              gen->Add(load->expr_id());
+              if (out_values == NULL) out_values = CreateBlockOutValues();
+              (*out_values)[load->expr_id()] = GetStoredValue(instr);
+            }
           }
           ASSERT(instr->IsDefinition() &&
                  !IsLoadEliminationCandidate(instr->AsDefinition()));
           continue;
         }
 
         // Other instructions with side effects kill all loads.
         if (instr->HasSideEffect()) {
           kill->SetAll();
           // There is no need to clear out_values when clearing GEN set
@@ skipping 302 matching lines @@
   ZoneGrowableArray<Definition*>* CreateBlockOutValues() {
     ZoneGrowableArray<Definition*>* out =
         new ZoneGrowableArray<Definition*>(max_expr_id_);
     for (intptr_t i = 0; i < max_expr_id_; i++) {
       out->Add(NULL);
     }
     return out;
   }
 
   FlowGraph* graph_;
+  DirectChainedHashMap<LoadKeyValueTrait>* map_;
   const intptr_t max_expr_id_;
 
   // Mapping between field offsets in words and expression ids of loads from
   // that offset.
   const GrowableArray<BitVector*>& kill_by_offset_;
 
   // Per block sets of expression ids for loads that are: incoming (available
   // on the entry), outgoing (available on the exit), generated and killed.
   GrowableArray<BitVector*> in_;
   GrowableArray<BitVector*> out_;
@@ skipping 17 matching lines @@
   BitVector* in_worklist_;
 
   DISALLOW_COPY_AND_ASSIGN(LoadOptimizer);
 };
 
 
 bool DominatorBasedCSE::Optimize(FlowGraph* graph) {
   bool changed = false;
   if (FLAG_load_cse) {
     GrowableArray<BitVector*> kill_by_offs(10);
-    const intptr_t max_expr_id = NumberLoadExpressions(graph, &kill_by_offs);
+    DirectChainedHashMap<LoadKeyValueTrait> map;
+    const intptr_t max_expr_id =
+        NumberLoadExpressions(graph, &map, &kill_by_offs);
     if (max_expr_id > 0) {
-      LoadOptimizer load_optimizer(graph, max_expr_id, kill_by_offs);
+      LoadOptimizer load_optimizer(graph, max_expr_id, &map, kill_by_offs);
       load_optimizer.Optimize();
     }
   }
 
   DirectChainedHashMap<PointerKeyValueTrait<Instruction> > map;
   changed = OptimizeRecursive(graph->graph_entry(), &map) || changed;
 
   return changed;
 }
 
@@ skipping 834 matching lines @@
 
   if (FLAG_trace_constant_propagation) {
     OS::Print("\n==== After constant propagation ====\n");
     FlowGraphPrinter printer(*graph_);
     printer.PrintBlocks();
   }
 }
 
 
 }  // namespace dart