[turbofan] New GraphReducer based LoadElimination.

src/compiler/load-elimination.cc

Index: src/compiler/load-elimination.cc
diff --git a/src/compiler/load-elimination.cc b/src/compiler/load-elimination.cc
index 493c9cafd6c248973c14f7671874b9a90e4c5c32..f9e90ad09f73dc6bbbccd9b0dd9abf018b8fb87e 100644
--- a/src/compiler/load-elimination.cc
+++ b/src/compiler/load-elimination.cc
@@ -4,42 +4,15 @@
 
 #include "src/compiler/load-elimination.h"
 
-#include "src/compiler/graph.h"
-#include "src/compiler/node-marker.h"
 #include "src/compiler/node-properties.h"
-#include "src/compiler/node.h"
 #include "src/compiler/simplified-operator.h"
 
 namespace v8 {
 namespace internal {
 namespace compiler {
 
-#ifdef DEBUG
-#define TRACE(...)                                              \
-  do {                                                          \
-    if (FLAG_trace_turbo_load_elimination) PrintF(__VA_ARGS__); \
-  } while (false)
-#else
-#define TRACE(...)
-#endif
-
 namespace {
 
-const size_t kMaxTrackedFields = 16;
-
-Node* ActualValue(Node* node) {
-  switch (node->opcode()) {
-    case IrOpcode::kCheckBounds:
-    case IrOpcode::kCheckNumber:
-    case IrOpcode::kCheckTaggedPointer:
-    case IrOpcode::kCheckTaggedSigned:
-    case IrOpcode::kFinishRegion:
-      return ActualValue(NodeProperties::GetValueInput(node, 0));
-    default:
-      return node;
-  }
-}
-
 enum Aliasing { kNoAlias, kMayAlias, kMustAlias };
 
 Aliasing QueryAlias(Node* a, Node* b) {
@@ -50,6 +23,8 @@ Aliasing QueryAlias(Node* a, Node* b) {
       case IrOpcode::kHeapConstant:
       case IrOpcode::kParameter:
         return kNoAlias;
+      case IrOpcode::kFinishRegion:
+        return QueryAlias(a->InputAt(0), b);
       default:
         break;
     }
@@ -59,6 +34,8 @@ Aliasing QueryAlias(Node* a, Node* b) {
       case IrOpcode::kHeapConstant:
       case IrOpcode::kParameter:
         return kNoAlias;
+      case IrOpcode::kFinishRegion:
+        return QueryAlias(a, b->InputAt(0));
       default:
         break;
     }
@@ -70,373 +47,503 @@ bool MayAlias(Node* a, Node* b) { return QueryAlias(a, b) != kNoAlias; }
 
 bool MustAlias(Node* a, Node* b) { return QueryAlias(a, b) == kMustAlias; }
 
-// Abstract state to approximate the current state of a certain field along the
-// effect paths through the graph.
-class AbstractField final : public ZoneObject {
- public:
-  explicit AbstractField(Zone* zone) : info_for_node_(zone) {}
-  AbstractField(Node* object, Node* value, Zone* zone) : info_for_node_(zone) {
-    info_for_node_.insert(std::make_pair(object, value));
-  }
+}  // namespace
 
-  AbstractField const* Extend(Node* object, Node* value, Zone* zone) const {
-    AbstractField* that = new (zone) AbstractField(zone);
-    that->info_for_node_ = this->info_for_node_;
-    that->info_for_node_.insert(std::make_pair(object, value));
-    return that;
+Reduction LoadElimination::Reduce(Node* node) {
+  switch (node->opcode()) {
+    case IrOpcode::kLoadField:
+      return ReduceLoadField(node);
+    case IrOpcode::kStoreField:
+      return ReduceStoreField(node);
+    case IrOpcode::kLoadElement:
+      return ReduceLoadElement(node);
+    case IrOpcode::kStoreElement:
+      return ReduceStoreElement(node);
+    case IrOpcode::kEffectPhi:
+      return ReduceEffectPhi(node);
+    case IrOpcode::kDead:
+      break;
+    case IrOpcode::kStart:
+      return ReduceStart(node);
+    default:
+      return ReduceOtherNode(node);
   }
-  Node* Lookup(Node* object) const {
-    for (auto pair : info_for_node_) {
-      if (MustAlias(object, pair.first)) return pair.second;
+  return NoChange();
+}
+
+Node* LoadElimination::AbstractElements::Lookup(Node* object,
+                                                Node* index) const {
+  for (Element const element : elements_) {
+    if (element.object == nullptr) continue;
+    DCHECK_NOT_NULL(element.index);
+    DCHECK_NOT_NULL(element.value);
+    if (MustAlias(object, element.object) && MustAlias(index, element.index)) {
+      return element.value;
     }
-    return nullptr;
-  }
-  AbstractField const* Kill(Node* object, Zone* zone) const {
-    for (auto pair : this->info_for_node_) {
-      if (MayAlias(object, pair.first)) {
-        AbstractField* that = new (zone) AbstractField(zone);
-        for (auto pair : this->info_for_node_) {
-          if (!MayAlias(object, pair.first)) that->info_for_node_.insert(pair);
+  }
+  return nullptr;
+}
+
+LoadElimination::AbstractElements const*
+LoadElimination::AbstractElements::Kill(Node* object, Node* index,
+                                        Zone* zone) const {
+  for (Element const element : this->elements_) {
+    if (element.object == nullptr) continue;
+    if (MayAlias(object, element.object) && MayAlias(index, element.index)) {

[Jarin, 2016/07/25 11:22:27]

Please, remove the MayAlias for the index. This seems to work for now, but only
because MayAlias is dumb. If we made MayAlias a bit smarter (e.g., by doing
aliasing for heap constants), this could blow up.

[Benedikt Meurer, 2016/07/25 11:28:42]

Done.

+      AbstractElements* that = new (zone) AbstractElements(zone);
+      for (Element const element : this->elements_) {
+        if (element.object == nullptr) continue;
+        DCHECK_NOT_NULL(element.index);
+        DCHECK_NOT_NULL(element.value);
+        if (!MayAlias(object, element.object) ||
+            !MayAlias(index, element.index)) {
+          that->elements_[that->next_index_++] = element;
         }
-        return that;
-      }
-    }
-    return this;
-  }
-  bool Equals(AbstractField const* that) const {
-    return this == that || this->info_for_node_ == that->info_for_node_;
-  }
-  AbstractField const* Merge(AbstractField const* that, Zone* zone) const {
-    if (this->Equals(that)) return this;
-    AbstractField* copy = new (zone) AbstractField(zone);
-    for (auto this_it : this->info_for_node_) {
-      Node* this_object = this_it.first;
-      Node* this_value = this_it.second;
-      auto that_it = that->info_for_node_.find(this_object);
-      if (that_it != that->info_for_node_.end() &&
-          that_it->second == this_value) {
-        copy->info_for_node_.insert(this_it);
       }
+      return that;
     }
-    return copy;
-  }
-
- private:
-  ZoneMap<Node*, Node*> info_for_node_;
-};
-
-// Abstract state to track the state of all fields along the effect paths
-// through the graph.
-class AbstractState final : public ZoneObject {
- public:
-  AbstractState() {
-    for (size_t i = 0; i < kMaxTrackedFields; ++i) fields_[i] = nullptr;
   }
+  return this;
+}
 
-  AbstractState const* Extend(Node* object, size_t index, Node* value,
-                              Zone* zone) const {
-    AbstractState* that = new (zone) AbstractState(*this);
-    AbstractField const* that_field = that->fields_[index];
-    if (that_field) {
-      that_field = that_field->Extend(object, value, zone);
-    } else {
-      that_field = new (zone) AbstractField(object, value, zone);
-    }
-    that->fields_[index] = that_field;
-    return that;
-  }
-  AbstractState const* Kill(Node* object, size_t index, Zone* zone) const {
-    if (!this->fields_[index]) return this;
-    AbstractState* that = new (zone) AbstractState(*this);
-    that->fields_[index] = nullptr;
-    return that;
-  }
-  AbstractState const* Merge(AbstractState const* that, Zone* zone) const {
-    if (this->Equals(that)) return this;
-    AbstractState* copy = new (zone) AbstractState();
-    for (size_t i = 0; i < kMaxTrackedFields; ++i) {
-      AbstractField const* this_field = this->fields_[i];
-      AbstractField const* that_field = that->fields_[i];
-      if (this_field && that_field) {
-        copy->fields_[i] = this_field->Merge(that_field, zone);
+bool LoadElimination::AbstractElements::Equals(
+    AbstractElements const* that) const {
+  if (this == that) return true;
+  for (size_t i = 0; i < arraysize(elements_); ++i) {
+    Element this_element = this->elements_[i];
+    if (this_element.object == nullptr) continue;
+    for (size_t j = 0;; ++j) {
+      if (j == arraysize(elements_)) return false;
+      Element that_element = that->elements_[j];
+      if (this_element.object == that_element.object &&
+          this_element.index == that_element.index &&
+          this_element.value == that_element.value) {
+        break;
       }
     }
-    return copy;
-  }
-  Node* Lookup(Node* object, size_t index) const {
-    AbstractField const* this_field = this->fields_[index];
-    if (this_field) return this_field->Lookup(object);
-    return nullptr;
-  }
-  bool Equals(AbstractState const* that) const {
-    if (this == that) return true;
-    for (size_t i = 0; i < kMaxTrackedFields; ++i) {
-      AbstractField const* this_field = this->fields_[i];
-      AbstractField const* that_field = that->fields_[i];
-      if (this_field) {
-        if (!that_field || !this_field->Equals(that_field)) return false;
-      } else if (that_field) {
-        return false;
+  }
+  for (size_t i = 0; i < arraysize(elements_); ++i) {
+    Element that_element = that->elements_[i];
+    if (that_element.object == nullptr) continue;
+    for (size_t j = 0;; ++j) {
+      if (j == arraysize(elements_)) return false;
+      Element this_element = this->elements_[j];
+      if (that_element.object == this_element.object &&
+          that_element.index == this_element.index &&
+          that_element.value == this_element.value) {
+        break;
       }
-      DCHECK(this_field == that_field || this_field->Equals(that_field));
     }
-    return true;
-  }
-
- private:
-  AbstractField const* fields_[kMaxTrackedFields];
-};
-
-class LoadEliminationAnalysis final {
- public:
-  LoadEliminationAnalysis(Graph* graph, Zone* zone)
-      : candidates_(zone),
-        empty_state_(),
-        queue_(zone),
-        node_states_(graph->NodeCount(), zone) {}
-
-  void Run(Node* start) {
-    TRACE("--{Analysis phase}--\n");
-    UpdateState(start, empty_state());
-    while (!queue_.empty()) {
-      Node* const node = queue_.top();
-      queue_.pop();
-      VisitNode(node);
-    }
-    TRACE("--{Replacement phase}--\n");
-    ZoneMap<Node*, Node*> replacements(zone());
-    for (Node* const node : candidates_) {
-      switch (node->opcode()) {
-        case IrOpcode::kLoadField: {
-          FieldAccess const& access = FieldAccessOf(node->op());
-          Node* const object =
-              ActualValue(NodeProperties::GetValueInput(node, 0));
-          Node* const effect = NodeProperties::GetEffectInput(node);
-          AbstractState const* state = GetState(effect);
-          int field_index = FieldIndexOf(access);
-          DCHECK_LE(0, field_index);
-          if (Node* value = state->Lookup(object, field_index)) {
-            auto it = replacements.find(value);
-            if (it != replacements.end()) value = it->second;
-            Type* const value_type = NodeProperties::GetType(value);
-            if (value_type->Is(access.type)) {
-              replacements.insert(std::make_pair(node, value));
-              TRACE(" - Replacing redundant #%d:LoadField with #%d:%s\n",
-                    node->id(), value->id(), value->op()->mnemonic());
-              NodeProperties::ReplaceUses(node, value, effect);
-              node->Kill();
-            } else {
-              TRACE(
-                  " - Cannot replace redundant #%d:LoadField with #%d:%s,"
-                  " because types don't agree",
-                  node->id(), value->id(), value->op()->mnemonic());
-            }
-          }
-          break;
-        }
-        case IrOpcode::kStoreField: {
-          FieldAccess const& access = FieldAccessOf(node->op());
-          Node* const object =
-              ActualValue(NodeProperties::GetValueInput(node, 0));
-          Node* const value =
-              ActualValue(NodeProperties::GetValueInput(node, 1));
-          Node* const effect = NodeProperties::GetEffectInput(node);
-          AbstractState const* state = GetState(effect);
-          int field_index = FieldIndexOf(access);
-          DCHECK_LE(0, field_index);
-          if (value == state->Lookup(object, field_index)) {
-            TRACE(" - Killing redundant #%d:StoreField\n", node->id());
-            NodeProperties::ReplaceUses(node, value, effect);
-            node->Kill();
-          }
-          break;
-        }
-        default:
-          UNREACHABLE();
+  }
+  return true;
+}
+
+LoadElimination::AbstractElements const*
+LoadElimination::AbstractElements::Merge(AbstractElements const* that,
+                                         Zone* zone) const {
+  if (this->Equals(that)) return this;
+  AbstractElements* copy = new (zone) AbstractElements(zone);
+  for (Element const this_element : this->elements_) {
+    if (this_element.object == nullptr) continue;
+    for (Element const that_element : that->elements_) {
+      if (this_element.object == that_element.object &&
+          this_element.index == that_element.index &&
+          this_element.value == that_element.value) {
+        copy->elements_[copy->next_index_++] = this_element;
       }
     }
   }
+  return copy;
+}
 
- private:
-  void VisitNode(Node* node) {
-    TRACE(" - Visiting node #%d:%s\n", node->id(), node->op()->mnemonic());
-    switch (node->opcode()) {
-      case IrOpcode::kEffectPhi:
-        return VisitEffectPhi(node);
-      case IrOpcode::kLoadField:
-        return VisitLoadField(node);
-      case IrOpcode::kStoreElement:
-        return VisitStoreElement(node);
-      case IrOpcode::kStoreField:
-        return VisitStoreField(node);
-      case IrOpcode::kDeoptimize:
-      case IrOpcode::kReturn:
-      case IrOpcode::kTerminate:
-      case IrOpcode::kThrow:
-        break;
-      default:
-        return VisitOtherNode(node);
-    }
+Node* LoadElimination::AbstractField::Lookup(Node* object) const {
+  for (auto pair : info_for_node_) {
+    if (MustAlias(object, pair.first)) return pair.second;
   }
+  return nullptr;
+}
 
-  void VisitEffectPhi(Node* node) {
-    int const input_count = node->InputCount() - 1;
-    DCHECK_LT(0, input_count);
-    Node* const control = NodeProperties::GetControlInput(node);
-    Node* const effect0 = NodeProperties::GetEffectInput(node, 0);
-    AbstractState const* state = GetState(effect0);
-    if (state == nullptr) return;
-    if (control->opcode() == IrOpcode::kMerge) {
-      for (int i = 1; i < input_count; ++i) {
-        Node* const effecti = NodeProperties::GetEffectInput(node, i);
-        if (GetState(effecti) == nullptr) return;
+LoadElimination::AbstractField const* LoadElimination::AbstractField::Kill(
+    Node* object, Zone* zone) const {
+  for (auto pair : this->info_for_node_) {
+    if (MayAlias(object, pair.first)) {
+      AbstractField* that = new (zone) AbstractField(zone);
+      for (auto pair : this->info_for_node_) {
+        if (!MayAlias(object, pair.first)) that->info_for_node_.insert(pair);
       }
+      return that;
     }
-    for (int i = 1; i < input_count; ++i) {
-      Node* const effecti = NodeProperties::GetEffectInput(node, i);
-      if (AbstractState const* statei = GetState(effecti)) {
-        state = state->Merge(statei, zone());
-      }
+  }
+  return this;
+}
+
+bool LoadElimination::AbstractState::Equals(AbstractState const* that) const {
+  if (this->elements_) {
+    if (!that->elements_ || !that->elements_->Equals(this->elements_)) {
+      return false;
     }
-    UpdateState(node, state);
-  }
-
-  void VisitLoadField(Node* node) {
-    FieldAccess const& access = FieldAccessOf(node->op());
-    Node* const object = ActualValue(NodeProperties::GetValueInput(node, 0));
-    Node* const effect = NodeProperties::GetEffectInput(node);
-    AbstractState const* state = GetState(effect);
-    int field_index = FieldIndexOf(access);
-    if (field_index >= 0) {
-      Node* const value = state->Lookup(object, field_index);
-      if (!value) {
-        TRACE("   Node #%d:LoadField is not redundant\n", node->id());
-        state = state->Extend(object, field_index, node, zone());
-      } else if (!NodeProperties::GetType(value)->Is(access.type)) {
-        TRACE(
-            "   Node #%d:LoadField is redundant for #%d:%s, but"
-            " types don't agree\n",
-            node->id(), value->id(), value->op()->mnemonic());
-        state = state->Extend(object, field_index, node, zone());
-      } else if (value) {
-        TRACE("   Node #%d:LoadField is fully redundant for #%d:%s\n",
-              node->id(), value->id(), value->op()->mnemonic());
-        candidates_.insert(node);
-      }
-    } else {
-      TRACE("   Node #%d:LoadField is unsupported\n", node->id());
+  } else if (that->elements_) {
+    return false;
+  }
+  for (size_t i = 0u; i < arraysize(fields_); ++i) {
+    AbstractField const* this_field = this->fields_[i];
+    AbstractField const* that_field = that->fields_[i];
+    if (this_field) {
+      if (!that_field || !that_field->Equals(this_field)) return false;
+    } else if (that_field) {
+      return false;
     }
-    UpdateState(node, state);
-  }
-
-  void VisitStoreField(Node* node) {
-    FieldAccess const& access = FieldAccessOf(node->op());
-    Node* const object = ActualValue(NodeProperties::GetValueInput(node, 0));
-    Node* const new_value = NodeProperties::GetValueInput(node, 1);
-    Node* const effect = NodeProperties::GetEffectInput(node);
-    AbstractState const* state = GetState(effect);
-    int field_index = FieldIndexOf(access);
-    if (field_index >= 0) {
-      Node* const old_value = state->Lookup(object, field_index);
-      if (old_value == new_value) {
-        TRACE("  Node #%d:StoreField is fully redundant, storing #%d:%s\n",
-              node->id(), new_value->id(), new_value->op()->mnemonic());
-        candidates_.insert(node);
+  }
+  return true;
+}
+
+void LoadElimination::AbstractState::Merge(AbstractState const* that,
+                                           Zone* zone) {
+  // Merge the information we have about the elements.
+  if (this->elements_) {
+    this->elements_ = that->elements_
+                          ? that->elements_->Merge(this->elements_, zone)
+                          : that->elements_;
+  } else {
+    this->elements_ = that->elements_;
+  }
+
+  // Merge the information we have about the fields.
+  for (size_t i = 0; i < arraysize(fields_); ++i) {
+    if (this->fields_[i]) {
+      if (that->fields_[i]) {
+        this->fields_[i] = this->fields_[i]->Merge(that->fields_[i], zone);
+      } else {
+        this->fields_[i] = nullptr;
       }
-      TRACE("  Killing all potentially aliasing stores for %d on #%d:%s\n",
-            field_index, object->id(), object->op()->mnemonic());
-      state = state->Kill(object, field_index, zone());
-      TRACE("  Node #%d:StoreField provides #%d:%s for %d on #%d:%s\n",
-            node->id(), new_value->id(), new_value->op()->mnemonic(),
-            field_index, object->id(), object->op()->mnemonic());
-      state = state->Extend(object, field_index, new_value, zone());
-    } else {
-      TRACE("   Node #%d:StoreField is unsupported\n", node->id());
-      state = empty_state();
     }
-    UpdateState(node, state);
   }
+}
 
-  void VisitStoreElement(Node* node) {
-    Node* const effect = NodeProperties::GetEffectInput(node);
-    AbstractState const* state = GetState(effect);
-    UpdateState(node, state);
+Node* LoadElimination::AbstractState::LookupElement(Node* object,
+                                                    Node* index) const {
+  if (this->elements_) {
+    return this->elements_->Lookup(object, index);
   }
+  return nullptr;
+}
 
-  void VisitOtherNode(Node* node) {
-    DCHECK_EQ(1, node->op()->EffectInputCount());
-    DCHECK_EQ(1, node->op()->EffectOutputCount());
-    Node* const effect = NodeProperties::GetEffectInput(node);
-    AbstractState const* state = node->op()->HasProperty(Operator::kNoWrite)
-                                     ? GetState(effect)
-                                     : empty_state();
-    UpdateState(node, state);
+LoadElimination::AbstractState const*
+LoadElimination::AbstractState::AddElement(Node* object, Node* index,
+                                           Node* value, Zone* zone) const {
+  AbstractState* that = new (zone) AbstractState(*this);
+  if (that->elements_) {
+    that->elements_ = that->elements_->Extend(object, index, value, zone);
+  } else {
+    that->elements_ = new (zone) AbstractElements(object, index, value, zone);
   }
+  return that;
+}
 
-  int FieldIndexOf(FieldAccess const& access) const {
-    switch (access.machine_type.representation()) {
-      case MachineRepresentation::kNone:
-      case MachineRepresentation::kBit:
-        UNREACHABLE();
-        break;
-      case MachineRepresentation::kWord8:
-      case MachineRepresentation::kWord16:
-      case MachineRepresentation::kWord32:
-      case MachineRepresentation::kWord64:
-      case MachineRepresentation::kFloat32:
-        return -1;  // Currently untracked.
-      case MachineRepresentation::kFloat64:
-      case MachineRepresentation::kSimd128:
-      case MachineRepresentation::kTagged:
-        // TODO(bmeurer): Check that we never do overlapping load/stores of
-        // individual parts of Float64/Simd128 values.
-        break;
+LoadElimination::AbstractState const*
+LoadElimination::AbstractState::KillElement(Node* object, Node* index,
+                                            Zone* zone) const {
+  if (this->elements_) {
+    AbstractElements const* that_elements =
+        this->elements_->Kill(object, index, zone);
+    if (this->elements_ != that_elements) {
+      AbstractState* that = new (zone) AbstractState(*this);
+      that->elements_ = that_elements;
+      return that;
     }
-    DCHECK_EQ(kTaggedBase, access.base_is_tagged);
-    DCHECK_EQ(0, access.offset % kPointerSize);
-    int field_index = access.offset / kPointerSize;
-    if (field_index >= static_cast<int>(kMaxTrackedFields)) return -1;
-    return field_index;
   }
+  return this;
+}
 
-  AbstractState const* GetState(Node* node) const {
-    return node_states_[node->id()];
+LoadElimination::AbstractState const* LoadElimination::AbstractState::AddField(
+    Node* object, size_t index, Node* value, Zone* zone) const {
+  AbstractState* that = new (zone) AbstractState(*this);
+  if (that->fields_[index]) {
+    that->fields_[index] = that->fields_[index]->Extend(object, value, zone);
+  } else {
+    that->fields_[index] = new (zone) AbstractField(object, value, zone);
   }
-  void SetState(Node* node, AbstractState const* state) {
-    node_states_[node->id()] = state;
+  return that;
+}
+
+LoadElimination::AbstractState const* LoadElimination::AbstractState::KillField(
+    Node* object, size_t index, Zone* zone) const {
+  if (AbstractField const* this_field = this->fields_[index]) {
+    this_field = this_field->Kill(object, zone);
+    if (this->fields_[index] != this_field) {
+      AbstractState* that = new (zone) AbstractState(*this);
+      that->fields_[index] = this_field;
+      return that;
+    }
   }
+  return this;
+}
 
-  void UpdateState(Node* node, AbstractState const* new_state) {
-    AbstractState const* old_state = GetState(node);
-    if (old_state && old_state->Equals(new_state)) return;
-    SetState(node, new_state);
-    EnqueueUses(node);
+Node* LoadElimination::AbstractState::LookupField(Node* object,
+                                                  size_t index) const {
+  if (AbstractField const* this_field = this->fields_[index]) {
+    return this_field->Lookup(object);
   }
+  return nullptr;
+}
+
+LoadElimination::AbstractState const*
+LoadElimination::AbstractStateForEffectNodes::Get(Node* node) const {
+  size_t const id = node->id();
+  if (id < info_for_node_.size()) return info_for_node_[id];
+  return nullptr;
+}
+
+void LoadElimination::AbstractStateForEffectNodes::Set(
+    Node* node, AbstractState const* state) {
+  size_t const id = node->id();
+  if (id >= info_for_node_.size()) info_for_node_.resize(id + 1, nullptr);
+  info_for_node_[id] = state;
+}
 
-  void EnqueueUses(Node* node) {
-    for (Edge const edge : node->use_edges()) {
-      if (NodeProperties::IsEffectEdge(edge)) {
-        queue_.push(edge.from());
+Reduction LoadElimination::ReduceLoadField(Node* node) {
+  FieldAccess const& access = FieldAccessOf(node->op());
+  Node* const object = NodeProperties::GetValueInput(node, 0);
+  Node* const effect = NodeProperties::GetEffectInput(node);
+  AbstractState const* state = node_states_.Get(effect);
+  if (state == nullptr) return NoChange();
+  int field_index = FieldIndexOf(access);
+  if (field_index >= 0) {
+    if (Node* const replacement = state->LookupField(object, field_index)) {
+      // Make sure the {replacement} has at least as good type
+      // as the original {node}.
+      if (NodeProperties::GetType(replacement)
+              ->Is(NodeProperties::GetType(node))) {
+        ReplaceWithValue(node, replacement, effect);
+        DCHECK(!replacement->IsDead());
+        return Replace(replacement);
       }
     }
+    state = state->AddField(object, field_index, node, zone());
   }
+  return UpdateState(node, state);
+}
 
-  AbstractState const* empty_state() const { return &empty_state_; }
-  Zone* zone() const { return node_states_.get_allocator().zone(); }
+Reduction LoadElimination::ReduceStoreField(Node* node) {
+  FieldAccess const& access = FieldAccessOf(node->op());
+  Node* const object = NodeProperties::GetValueInput(node, 0);
+  Node* const new_value = NodeProperties::GetValueInput(node, 1);
+  Node* const effect = NodeProperties::GetEffectInput(node);
+  AbstractState const* state = node_states_.Get(effect);
+  if (state == nullptr) return NoChange();
+  int field_index = FieldIndexOf(access);
+  if (field_index >= 0) {
+    Node* const old_value = state->LookupField(object, field_index);
+    if (old_value == new_value) {
+      // This store is fully redundant.
+      return Replace(effect);
+    }
+    // Kill all potentially aliasing fields and record the new value.
+    state = state->KillField(object, field_index, zone());
+    state = state->AddField(object, field_index, new_value, zone());
+  } else {
+    // Unsupported StoreField operator.
+    state = empty_state();
+  }
+  return UpdateState(node, state);
+}
 
-  ZoneSet<Node*> candidates_;
-  AbstractState const empty_state_;
-  ZoneStack<Node*> queue_;
-  ZoneVector<AbstractState const*> node_states_;
+Reduction LoadElimination::ReduceLoadElement(Node* node) {
+  Node* const object = NodeProperties::GetValueInput(node, 0);
+  Node* const index = NodeProperties::GetValueInput(node, 1);
+  Node* const effect = NodeProperties::GetEffectInput(node);
+  AbstractState const* state = node_states_.Get(effect);
+  if (state == nullptr) return NoChange();
+  if (Node* const replacement = state->LookupElement(object, index)) {
+    // Make sure the {replacement} has at least as good type
+    // as the original {node}.
+    if (NodeProperties::GetType(replacement)
+            ->Is(NodeProperties::GetType(node))) {
+      ReplaceWithValue(node, replacement, effect);
+      DCHECK(!replacement->IsDead());
+      return Replace(replacement);
+    }
+  }
+  state = state->AddElement(object, index, node, zone());
+  return UpdateState(node, state);
+}
 
-  DISALLOW_COPY_AND_ASSIGN(LoadEliminationAnalysis);
-};
+Reduction LoadElimination::ReduceStoreElement(Node* node) {
+  ElementAccess const& access = ElementAccessOf(node->op());
+  Node* const object = NodeProperties::GetValueInput(node, 0);
+  Node* const index = NodeProperties::GetValueInput(node, 1);
+  Node* const new_value = NodeProperties::GetValueInput(node, 2);
+  Node* const effect = NodeProperties::GetEffectInput(node);
+  AbstractState const* state = node_states_.Get(effect);
+  if (state == nullptr) return NoChange();
+  Node* const old_value = state->LookupElement(object, index);
+  if (old_value == new_value) {
+    // This store is fully redundant.
+    return Replace(effect);
+  }
+  // Kill all potentially aliasing elements.
+  state = state->KillElement(object, index, zone());
+  // Only record the new value if the store doesn't have an implicit truncation.
+  switch (access.machine_type.representation()) {
+    case MachineRepresentation::kNone:
+    case MachineRepresentation::kBit:
+      UNREACHABLE();
+      break;
+    case MachineRepresentation::kWord8:
+    case MachineRepresentation::kWord16:
+    case MachineRepresentation::kWord32:
+    case MachineRepresentation::kWord64:
+    case MachineRepresentation::kFloat32:
+      // TODO(turbofan): Add support for doing the truncations.
+      break;
+    case MachineRepresentation::kFloat64:
+    case MachineRepresentation::kSimd128:
+    case MachineRepresentation::kTagged:
+      state = state->AddElement(object, index, new_value, zone());
+      break;
+  }
+  return UpdateState(node, state);
+}
 
-}  // namespace
+Reduction LoadElimination::ReduceEffectPhi(Node* node) {
+  Node* const effect0 = NodeProperties::GetEffectInput(node, 0);
+  Node* const control = NodeProperties::GetControlInput(node);
+  AbstractState const* state0 = node_states_.Get(effect0);
+  if (state0 == nullptr) return NoChange();
+  if (control->opcode() == IrOpcode::kLoop) {
+    // Here we rely on having only reducible loops:
+    // The loop entry edge always dominates the header, so we can just use
+    // the information from the loop entry edge.

[Jarin, 2016/07/25 11:22:27]

Replace the comment with one that makes sense :-)

[Benedikt Meurer, 2016/07/25 11:28:42]

Done.

+    AbstractState const* state = ComputeLoopState(node, state0);
+    return UpdateState(node, state);
+  }
+  DCHECK_EQ(IrOpcode::kMerge, control->opcode());
+
+  // Shortcut for the case when we do not know anything about some input.
+  int const input_count = node->op()->EffectInputCount();
+  for (int i = 1; i < input_count; ++i) {
+    Node* const effect = NodeProperties::GetEffectInput(node, i);
+    if (node_states_.Get(effect) == nullptr) return NoChange();
+  }
+
+  // Make a copy of the first input's state and merge with the state
+  // from other inputs.
+  AbstractState* state = new (zone()) AbstractState(*state0);
+  for (int i = 1; i < input_count; ++i) {
+    Node* const input = NodeProperties::GetEffectInput(node, i);
+    state->Merge(node_states_.Get(input), zone());
+  }
+  return UpdateState(node, state);
+}
+
+Reduction LoadElimination::ReduceStart(Node* node) {
+  return UpdateState(node, empty_state());
+}
+
+Reduction LoadElimination::ReduceOtherNode(Node* node) {
+  if (node->op()->EffectInputCount() == 1) {
+    if (node->op()->EffectOutputCount() == 1) {
+      Node* const effect = NodeProperties::GetEffectInput(node);
+      AbstractState const* state = node_states_.Get(effect);
+      // If we do not know anything about the predecessor, do not propagate
+      // just yet because we will have to recompute anyway once we compute
+      // the predecessor.
+      if (state == nullptr) return NoChange();
+      // Check if this {node} has some uncontrolled side effects.
+      if (!node->op()->HasProperty(Operator::kNoWrite)) {
+        state = empty_state();
+      }
+      return UpdateState(node, state);
+    } else {
+      // Effect terminators should be handled specially.
+      return NoChange();
+    }
+  }
+  DCHECK_EQ(0, node->op()->EffectInputCount());
+  DCHECK_EQ(0, node->op()->EffectOutputCount());
+  return NoChange();
+}
 
-void LoadElimination::Run() {
-  LoadEliminationAnalysis analysis(graph(), zone());
-  analysis.Run(graph()->start());
+Reduction LoadElimination::UpdateState(Node* node, AbstractState const* state) {
+  AbstractState const* original = node_states_.Get(node);
+  // Only signal that the {node} has Changed, if the information about {state}
+  // has changed wrt. the {original}.
+  if (state != original) {
+    if (original == nullptr || !state->Equals(original)) {
+      node_states_.Set(node, state);
+      return Changed(node);
+    }
+  }
+  return NoChange();
+}
+
+LoadElimination::AbstractState const* LoadElimination::ComputeLoopState(
+    Node* node, AbstractState const* state) const {
+  Node* const control = NodeProperties::GetControlInput(node);
+  ZoneQueue<Node*> queue(zone());
+  ZoneSet<Node*> visited(zone());
+  visited.insert(node);
+  for (int i = 1; i < control->InputCount(); ++i) {
+    queue.push(node->InputAt(i));
+  }
+  while (!queue.empty()) {
+    Node* const current = queue.front();
+    queue.pop();
+    if (visited.find(current) == visited.end()) {
+      visited.insert(current);
+      if (!current->op()->HasProperty(Operator::kNoWrite)) {
+        switch (current->opcode()) {
+          case IrOpcode::kStoreField: {
+            FieldAccess const& access = FieldAccessOf(current->op());
+            Node* const object = NodeProperties::GetValueInput(current, 0);
+            int field_index = FieldIndexOf(access);
+            if (field_index < 0) return empty_state();
+            state = state->KillField(object, field_index, zone());
+            break;
+          }
+          case IrOpcode::kStoreElement: {
+            Node* const object = NodeProperties::GetValueInput(current, 0);
+            Node* const index = NodeProperties::GetValueInput(current, 1);
+            state = state->KillElement(object, index, zone());
+            break;
+          }
+          default:
+            return empty_state();
+        }
+      }
+      for (int i = 0; i < current->op()->EffectInputCount(); ++i) {
+        queue.push(NodeProperties::GetEffectInput(current, i));
+      }
+    }
+  }
+  return state;
+}
+
+// static
+int LoadElimination::FieldIndexOf(FieldAccess const& access) {
+  switch (access.machine_type.representation()) {
+    case MachineRepresentation::kNone:
+    case MachineRepresentation::kBit:
+      UNREACHABLE();
+      break;
+    case MachineRepresentation::kWord8:
+    case MachineRepresentation::kWord16:
+    case MachineRepresentation::kWord32:
+    case MachineRepresentation::kWord64:
+    case MachineRepresentation::kFloat32:
+      return -1;  // Currently untracked.
+    case MachineRepresentation::kFloat64:
+    case MachineRepresentation::kSimd128:
+    case MachineRepresentation::kTagged:
+      // TODO(bmeurer): Check that we never do overlapping load/stores of
+      // individual parts of Float64/Simd128 values.
+      break;
+  }
+  DCHECK_EQ(kTaggedBase, access.base_is_tagged);
+  DCHECK_EQ(0, access.offset % kPointerSize);
+  int field_index = access.offset / kPointerSize;
+  if (field_index >= static_cast<int>(kMaxTrackedFields)) return -1;
+  return field_index;
 }
 
 }  // namespace compiler