Implement global load elimination based on flow engine.

src/hydrogen-load-elimination.cc

Index: src/hydrogen-load-elimination.cc
diff --git a/src/hydrogen-load-elimination.cc b/src/hydrogen-load-elimination.cc
index 6d01ae573be81d1dd2e86444cfa88af0a9091762..f33ebe2fabcb61aed1429792618e745e58de73ce 100644
--- a/src/hydrogen-load-elimination.cc
+++ b/src/hydrogen-load-elimination.cc
@@ -28,10 +28,14 @@
 #include "hydrogen-alias-analysis.h"
 #include "hydrogen-load-elimination.h"
 #include "hydrogen-instructions.h"
+#include "hydrogen-flow-engine.h"
 
 namespace v8 {
 namespace internal {
 
+#define GLOBAL true
+#define TRACE(x) if (FLAG_trace_load_elimination) PrintF x
+
 static const int kMaxTrackedFields = 16;
 static const int kMaxTrackedObjects = 5;
 
@@ -42,17 +46,145 @@ class HFieldApproximation : public ZoneObject {
   HLoadNamedField* last_load_;
   HValue* last_value_;
   HFieldApproximation* next_;
+
+  // Recursively copy the entire linked list of field approximations.
+  HFieldApproximation* Copy(Zone* zone) {
+    if (this == NULL) return NULL;
+    HFieldApproximation* copy = new(zone) HFieldApproximation();
+    copy->object_ = this->object_;
+    copy->last_load_ = this->last_load_;
+    copy->last_value_ = this->last_value_;
+    copy->next_ = this->next_->Copy(zone);
+    return copy;
+  }
 };
 
 
 // The main datastructure used during load/store elimination. Each in-object
 // field is tracked separately. For each field, store a list of known field
 // values for known objects.
-class HLoadEliminationTable BASE_EMBEDDED {
+class HLoadEliminationTable : public ZoneObject {
  public:
   HLoadEliminationTable(Zone* zone, HAliasAnalyzer* aliasing)
     : zone_(zone), fields_(kMaxTrackedFields, zone), aliasing_(aliasing) { }
 
+  // The main processing of instructions.
+  HLoadEliminationTable* Process(HInstruction* instr, Zone* zone) {
+    switch (instr->opcode()) {
+      case HValue::kLoadNamedField: {
+        HLoadNamedField* l = HLoadNamedField::cast(instr);
+        TRACE((" process L%d field %d (o%d)\n",
+               instr->id(),
+               FieldOf(l->access()),
+               l->object()->ActualValue()->id()));
+        HValue* result = load(l);
+        if (result != instr) {
+          // The load can be replaced with a previous load or a value.
+          TRACE(("  replace L%d -> v%d\n", instr->id(), result->id()));
+          instr->DeleteAndReplaceWith(result);
+        }
+        break;
+      }
+      case HValue::kStoreNamedField: {
+        HStoreNamedField* s = HStoreNamedField::cast(instr);
+        TRACE((" process S%d field %d (o%d) = v%d\n",
+               instr->id(),
+               FieldOf(s->access()),
+               s->object()->ActualValue()->id(),
+               s->value()->id()));
+        HValue* result = store(s);
+        if (result == NULL) {
+          // The store is redundant. Remove it.
+          TRACE(("  remove S%d\n", instr->id()));
+          instr->DeleteAndReplaceWith(NULL);
+        }
+        break;
+      }
+      default: {
+        if (instr->CheckGVNFlag(kChangesInobjectFields)) {
+          TRACE((" kill-all i%d\n", instr->id()));
+          Kill();
+          break;
+        }
+        if (instr->CheckGVNFlag(kChangesMaps)) {
+          TRACE((" kill-maps i%d\n", instr->id()));
+          KillOffset(JSObject::kMapOffset);
+        }
+        if (instr->CheckGVNFlag(kChangesElementsKind)) {
+          TRACE((" kill-elements-kind i%d\n", instr->id()));
+          KillOffset(JSObject::kMapOffset);
+          KillOffset(JSObject::kElementsOffset);
+        }
+        if (instr->CheckGVNFlag(kChangesElementsPointer)) {
+          TRACE((" kill-elements i%d\n", instr->id()));
+          KillOffset(JSObject::kElementsOffset);
+        }
+        if (instr->CheckGVNFlag(kChangesOsrEntries)) {
+          TRACE((" kill-osr i%d\n", instr->id()));
+          Kill();
+        }
+      }
+      // Improvements possible:
+      // - learn from HCheckMaps for field 0
+      // - remove unobservable stores (write-after-write)
+      // - track cells
+      // - track globals
+      // - track roots
+    }
+    return this;
+  }
+
+  // Support for global analysis with HFlowEngine: Copy state to sucessor block.
+  HLoadEliminationTable* Copy(HBasicBlock* succ, Zone* zone) {
+    HLoadEliminationTable* copy =
+        new(zone) HLoadEliminationTable(zone, aliasing_);
+    copy->EnsureFields(fields_.length());
+    for (int i = 0; i < fields_.length(); i++) {
+      copy->fields_[i] = fields_[i]->Copy(zone);
+    }
+    if (FLAG_trace_load_elimination) {
+      TRACE((" copy-to B%d\n", succ->block_id()));
+      copy->Print();
+    }
+    return copy;
+  }
+
+  // Support for global analysis with HFlowEngine: Merge this state with
+  // the other incoming state.
+  HLoadEliminationTable* Merge(HBasicBlock* succ,
+      HLoadEliminationTable* that, Zone* zone) {
+    if (that->fields_.length() < fields_.length()) {
+      // Drop fields not in the other table.
+      fields_.Rewind(that->fields_.length());
+    }
+    for (int i = 0; i < fields_.length(); i++) {
+      // Merge the field approximations for like fields.
+      HFieldApproximation* approx = fields_[i];
+      HFieldApproximation* prev = NULL;
+      while (approx != NULL) {
+        // TODO(titzer): Merging is O(N * M); sort?
+        HFieldApproximation* other = that->Find(approx->object_, i);
+        if (other == NULL || !Equal(approx->last_value_, other->last_value_)) {
+          // Kill an entry that doesn't agree with the other value.
+          if (prev != NULL) {
+            prev->next_ = approx->next_;
+          } else {
+            fields_[i] = approx->next_;
+          }
+          approx = approx->next_;
+          continue;
+        }
+        prev = approx;
+        approx = approx->next_;
+      }
+    }
+    return this;
+  }
+
+  friend class HLoadEliminationEffects;  // Calls Kill() and others.
+  friend class HLoadEliminationPhase;
+
+ private:
   // Process a load instruction, updating internal table state. If a previous
   // load or store for this object and field exists, return the new value with
   // which the load should be replaced. Otherwise, return {instr}.
@@ -118,28 +250,17 @@ class HLoadEliminationTable BASE_EMBEDDED {
     }
   }
 
-  // Compute the field index for the given object access; -1 if not tracked.
-  int FieldOf(HObjectAccess access) {
-    // Only track kMaxTrackedFields in-object fields.
-    if (!access.IsInobject()) return -1;
-    return FieldOf(access.offset());
-  }
-
-  // Print this table to stdout.
-  void Print() {
-    for (int i = 0; i < fields_.length(); i++) {
-      PrintF("  field %d: ", i);
-      for (HFieldApproximation* a = fields_[i]; a != NULL; a = a->next_) {
-        PrintF("[o%d =", a->object_->id());
-        if (a->last_load_ != NULL) PrintF(" L%d", a->last_load_->id());
-        if (a->last_value_ != NULL) PrintF(" v%d", a->last_value_->id());
-        PrintF("] ");
-      }
-      PrintF("\n");
+  // Find an entry for the given object and field pair.
+  HFieldApproximation* Find(HValue* object, int field) {
+    // Search for a field approximation for this object.
+    HFieldApproximation* approx = fields_[field];
+    while (approx != NULL) {
+      if (aliasing_->MustAlias(object, approx->object_)) return approx;
+      approx = approx->next_;
     }
+    return NULL;
   }
 
- private:
   // Find or create an entry for the given object and field pair.
   HFieldApproximation* FindOrCreate(HValue* object, int field) {
     EnsureFields(field + 1);
@@ -218,110 +339,143 @@ class HLoadEliminationTable BASE_EMBEDDED {
     return approx;
   }
 
-  // Ensure internal storage for the given number of fields.
-  void EnsureFields(int num_fields) {
-    while (fields_.length() < num_fields) fields_.Add(NULL, zone_);
+  // Compute the field index for the given object access; -1 if not tracked.
+  int FieldOf(HObjectAccess access) {
+    return access.IsInobject() ? FieldOf(access.offset()) : -1;
   }
 
-  // Compute the field index for the given in-object offset.
+  // Compute the field index for the given in-object offset; -1 if not tracked.
   int FieldOf(int offset) {
     if (offset >= kMaxTrackedFields * kPointerSize) return -1;
     ASSERT((offset % kPointerSize) == 0);  // Assume aligned accesses.
     return offset / kPointerSize;
   }
 
+  // Ensure internal storage for the given number of fields.
+  void EnsureFields(int num_fields) {
+    if (fields_.length() < num_fields) {
+      fields_.AddBlock(NULL, num_fields - fields_.length(), zone_);
+    }
+  }
+
+  // Print this table to stdout.
+  void Print() {
+    for (int i = 0; i < fields_.length(); i++) {
+      PrintF("  field %d: ", i);
+      for (HFieldApproximation* a = fields_[i]; a != NULL; a = a->next_) {
+        PrintF("[o%d =", a->object_->id());
+        if (a->last_load_ != NULL) PrintF(" L%d", a->last_load_->id());
+        if (a->last_value_ != NULL) PrintF(" v%d", a->last_value_->id());
+        PrintF("] ");
+      }
+      PrintF("\n");
+    }
+  }
+
   Zone* zone_;
   ZoneList<HFieldApproximation*> fields_;
   HAliasAnalyzer* aliasing_;
 };
 
 
-void HLoadEliminationPhase::Run() {
-  for (int i = 0; i < graph()->blocks()->length(); i++) {
-    HBasicBlock* block = graph()->blocks()->at(i);
-    EliminateLoads(block);
+// Support for HFlowEngine: collect store effects within loops.
+class HLoadEliminationEffects : public ZoneObject {
+ public:
+  explicit HLoadEliminationEffects(Zone* zone)
+    : zone_(zone),
+      maps_stored_(false),
+      fields_stored_(false),
+      elements_stored_(false),
+      stores_(5, zone) { }
+
+  inline bool Disabled() {
+    return false;  // Effects are _not_ disabled.
   }
-}
-
-
-// For code de-uglification.
-#define TRACE(x) if (FLAG_trace_load_elimination) PrintF x
-
-
-// Eliminate loads and stores local to a block.
-void HLoadEliminationPhase::EliminateLoads(HBasicBlock* block) {
-  HAliasAnalyzer aliasing;
-  HLoadEliminationTable table(zone(), &aliasing);
-
-  TRACE(("-- load-elim B%d -------------------------------------------------\n",
-         block->block_id()));
-
-  for (HInstructionIterator it(block); !it.Done(); it.Advance()) {
-    bool changed = false;
-    HInstruction* instr = it.Current();
 
+  // Process a possibly side-effecting instruction.
+  void Process(HInstruction* instr, Zone* zone) {
     switch (instr->opcode()) {
-      case HValue::kLoadNamedField: {
-        HLoadNamedField* load = HLoadNamedField::cast(instr);
-        TRACE((" process L%d field %d (o%d)\n",
-               instr->id(),
-               table.FieldOf(load->access()),
-               load->object()->ActualValue()->id()));
-        HValue* result = table.load(load);
-        if (result != instr) {
-          // The load can be replaced with a previous load or a value.
-          TRACE(("  replace L%d -> v%d\n", instr->id(), result->id()));
-          instr->DeleteAndReplaceWith(result);
-        }
-        changed = true;
-        break;
-      }
       case HValue::kStoreNamedField: {
-        HStoreNamedField* store = HStoreNamedField::cast(instr);
-        TRACE((" process S%d field %d (o%d) = v%d\n",
-               instr->id(),
-               table.FieldOf(store->access()),
-               store->object()->ActualValue()->id(),
-               store->value()->id()));
-        HValue* result = table.store(store);
-        if (result == NULL) {
-          // The store is redundant. Remove it.
-          TRACE(("  remove S%d\n", instr->id()));
-          instr->DeleteAndReplaceWith(NULL);
-        }
-        changed = true;
+        stores_.Add(HStoreNamedField::cast(instr), zone_);
         break;
       }
+      case HValue::kOsrEntry: {
+        // Kill everything. Loads must not be hoisted past the OSR entry.
+        maps_stored_ = true;
+        fields_stored_ = true;
+        elements_stored_ = true;
+      }
       default: {
-        if (instr->CheckGVNFlag(kChangesInobjectFields)) {
-          TRACE((" kill-all i%d\n", instr->id()));
-          table.Kill();
-          continue;
-        }
-        if (instr->CheckGVNFlag(kChangesMaps)) {
-          TRACE((" kill-maps i%d\n", instr->id()));
-          table.KillOffset(JSObject::kMapOffset);
-        }
-        if (instr->CheckGVNFlag(kChangesElementsKind)) {
-          TRACE((" kill-elements-kind i%d\n", instr->id()));
-          table.KillOffset(JSObject::kMapOffset);
-          table.KillOffset(JSObject::kElementsOffset);
-        }
-        if (instr->CheckGVNFlag(kChangesElementsPointer)) {
-          TRACE((" kill-elements i%d\n", instr->id()));
-          table.KillOffset(JSObject::kElementsOffset);
-        }
+        fields_stored_ |= instr->CheckGVNFlag(kChangesInobjectFields);
+        maps_stored_ |= instr->CheckGVNFlag(kChangesMaps);
+        maps_stored_ |= instr->CheckGVNFlag(kChangesElementsKind);
+        elements_stored_ |= instr->CheckGVNFlag(kChangesElementsKind);
+        elements_stored_ |= instr->CheckGVNFlag(kChangesElementsPointer);
       }
-    // Improvements possible:
-    // - learn from HCheckMaps for field 0
-    // - remove unobservable stores (write-after-write)
     }
+  }
 
-    if (changed && FLAG_trace_load_elimination) {
-      table.Print();
+  // Apply these effects to the given load elimination table.
+  void Apply(HLoadEliminationTable* table) {
+    if (fields_stored_) {
+      table->Kill();
+      return;
+    }
+    if (maps_stored_) {
+      table->KillOffset(JSObject::kMapOffset);
+    }
+    if (elements_stored_) {
+      table->KillOffset(JSObject::kElementsOffset);
+    }
+
+    // Kill non-agreeing fields for each store contained in these effects.
+    for (int i = 0; i < stores_.length(); i++) {
+      HStoreNamedField* s = stores_[i];
+      int field = table->FieldOf(s->access());
+      if (field >= 0) {
+        table->KillFieldInternal(s->object()->ActualValue(), field, s->value());
+      }
+    }
+  }
+
+  // Union these effects with the other effects.
+  void Union(HLoadEliminationEffects* that, Zone* zone) {
+    maps_stored_ |= that->maps_stored_;
+    fields_stored_ |= that->fields_stored_;
+    elements_stored_ |= that->elements_stored_;
+    for (int i = 0; i < that->stores_.length(); i++) {
+      stores_.Add(that->stores_[i], zone);
     }
   }
-}
 
+ private:
+  Zone* zone_;
+  bool maps_stored_ : 1;
+  bool fields_stored_ : 1;
+  bool elements_stored_ : 1;
+  ZoneList<HStoreNamedField*> stores_;
+};
+
+
+// The main routine of the analysis phase. Use the HFlowEngine for either a
+// local or a global analysis.
+void HLoadEliminationPhase::Run() {
+  HFlowEngine<HLoadEliminationTable, HLoadEliminationEffects>
+    engine(graph(), zone());
+  HAliasAnalyzer aliasing;
+  HLoadEliminationTable* table =
+      new(zone()) HLoadEliminationTable(zone(), &aliasing);
+
+  if (GLOBAL) {
+    // Perform a global analysis.
+    engine.AnalyzeDominatedBlocks(graph()->blocks()->at(0), table);
+  } else {
+    // Perform only local analysis.
+    for (int i = 0; i < graph()->blocks()->length(); i++) {
+      table->Kill();
+      engine.AnalyzeOneBlock(graph()->blocks()->at(i), table);
+    }
+  }
+}
 
 } }  // namespace v8::internal