Implement global load elimination based on flow engine.

src/hydrogen-load-elimination.cc

 // Copyright 2013 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 10 matching lines @@
 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 
 #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;
 
 // An element in the field approximation list.
 class HFieldApproximation : public ZoneObject {
  public:  // Just a data blob.
   HValue* object_;
   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}.
   HValue* load(HLoadNamedField* instr) {
     int field = FieldOf(instr->access());
     if (field < 0) return instr;
 
     HValue* object = instr->object()->ActualValue();
     HFieldApproximation* approx = FindOrCreate(object, field);
 
@@ skipping 45 matching lines @@
   }
 
   // Kill all entries matching the given offset.
   void KillOffset(int offset) {
     int field = FieldOf(offset);
     if (field >= 0 && field < fields_.length()) {
       fields_[field] = NULL;
     }
   }
 
-  // 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());
+  // 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;
   }
 
-  // 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");
-    }
-  }
-
- private:
   // Find or create an entry for the given object and field pair.
   HFieldApproximation* FindOrCreate(HValue* object, int field) {
     EnsureFields(field + 1);
 
     // Search for a field approximation for this object.
     HFieldApproximation* approx = fields_[field];
     int count = 0;
     while (approx != NULL) {
       if (aliasing_->MustAlias(object, approx->object_)) return approx;
       count++;
@@ skipping 58 matching lines @@
 
     HFieldApproximation* prev = NULL;
     while (approx->next_ != NULL) {
       prev = approx;
       approx = approx->next_;
     }
     if (prev != NULL) prev->next_ = NULL;
     return approx;
   }
 
+  // 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; -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) {
-    while (fields_.length() < num_fields) fields_.Add(NULL, zone_);
+    if (fields_.length() < num_fields) {
+      fields_.AddBlock(NULL, num_fields - fields_.length(), zone_);
+    }
   }
 
-  // Compute the field index for the given in-object offset.
-  int FieldOf(int offset) {
-    if (offset >= kMaxTrackedFields * kPointerSize) return -1;
-    ASSERT((offset % kPointerSize) == 0);  // Assume aligned accesses.
-    return offset / kPointerSize;
+  // 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.
   }
-}
+
+  // Process a possibly side-effecting instruction.
+  void Process(HInstruction* instr, Zone* zone) {
+    switch (instr->opcode()) {
+      case HValue::kStoreNamedField: {
+        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: {
+        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);
+      }
+    }
+  }
+
+  // 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_;
+};
 
 
-// For code de-uglification.
-#define TRACE(x) if (FLAG_trace_load_elimination) PrintF x
+// 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);
 
-
-// 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();
-
-    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;
-        break;
-      }
-      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);
-        }
-      }
-    // Improvements possible:
-    // - learn from HCheckMaps for field 0
-    // - remove unobservable stores (write-after-write)
-    }
-
-    if (changed && FLAG_trace_load_elimination) {
-      table.Print();
+  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