[turbofan] Initial version of the new LoadElimination.

src/compiler/load-elimination.cc

-// Copyright 2014 the V8 project authors. All rights reserved.
+// Copyright 2016 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "src/compiler/load-elimination.h"
 
-#include "src/compiler/graph.h"
+#include "src/compiler/js-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"
-#include "src/types.h"
 
 namespace v8 {
 namespace internal {
 namespace compiler {
 
-LoadElimination::~LoadElimination() {}
-
-Reduction LoadElimination::Reduce(Node* node) {
+#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::kLoadField:
-      return ReduceLoadField(node);
+    case IrOpcode::kCheckBounds:
+    case IrOpcode::kCheckNumber:
+    case IrOpcode::kCheckTaggedPointer:
+    case IrOpcode::kCheckTaggedSigned:
+    case IrOpcode::kFinishRegion:
+      return ActualValue(NodeProperties::GetValueInput(node, 0));
     default:
-      break;
-  }
-  return NoChange();
+      return node;
+  }
 }
 
-Reduction LoadElimination::ReduceLoadField(Node* node) {
-  DCHECK_EQ(IrOpcode::kLoadField, node->opcode());
-  FieldAccess const access = FieldAccessOf(node->op());
-  Node* object = NodeProperties::GetValueInput(node, 0);
-  for (Node* effect = NodeProperties::GetEffectInput(node);;
-       effect = NodeProperties::GetEffectInput(effect)) {
-    switch (effect->opcode()) {
-      case IrOpcode::kLoadField: {
-        FieldAccess const effect_access = FieldAccessOf(effect->op());
-        if (object == NodeProperties::GetValueInput(effect, 0) &&
-            access == effect_access && effect_access.type->Is(access.type)) {
-          Node* const value = effect;
-          ReplaceWithValue(node, value);
-          return Replace(value);
+enum Aliasing { kNoAlias, kMayAlias, kMustAlias };
+
+Aliasing QueryAlias(Node* a, Node* b) {
+  if (a == b) return kMustAlias;
+  if (b->opcode() == IrOpcode::kAllocate) {
+    switch (a->opcode()) {
+      case IrOpcode::kAllocate:
+      case IrOpcode::kHeapConstant:
+      case IrOpcode::kParameter:
+        return kNoAlias;
+      default:
+        break;
+    }
+  }
+  if (a->opcode() == IrOpcode::kAllocate) {
+    switch (b->opcode()) {
+      case IrOpcode::kHeapConstant:
+      case IrOpcode::kParameter:
+        return kNoAlias;
+      default:
+        break;
+    }
+  }
+  return kMayAlias;
+}
+
+bool MayAlias(Node* a, Node* b) { return QueryAlias(a, b) == kMayAlias; }

[Jarin, 2016/07/04 13:18:07]

How about QueryAlias(a, b) == kMayAlias || QueryAlias(a, b) == kMustAlias (or
QueryAlias(a, b) != kNoAlias)?

[Benedikt Meurer, 2016/07/05 11:29:09]

Done.

+
+bool MustAlias(Node* a, Node* b) { return QueryAlias(a, b) == kMustAlias; }
+
+class AbstractField final : public ZoneObject {

[Jarin, 2016/07/04 13:18:07]

Please explain in a comment what this is (+ the rest of the code).

[Benedikt Meurer, 2016/07/05 11:29:09]

Done.

+ 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));
+  }
+
+  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;
+  }
+  Node* Lookup(Node* object) const {
+    for (auto pair : info_for_node_) {
+      if (MustAlias(object, pair.first)) return pair.second;
+    }
+    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 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 copy;
+  }
+
+ private:
+  ZoneMap<Node*, Node*> info_for_node_;
+};
+
+class AbstractState final : public ZoneObject {
+ public:
+  AbstractState() {
+    for (size_t i = 0; i < kMaxTrackedFields; ++i) fields_[i] = nullptr;
+  }
+
+  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);
+      }
+    }
+    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;
+      }
+      DCHECK(this_field == 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;
+            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();
+          }
+          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);

[Jarin, 2016/07/04 13:18:07]

It is a shame that we cannot learn from control flow. If we could, this would
get rid of (at least some) map transitions.

[Benedikt Meurer, 2016/07/05 11:29:09]

Yeah... compiler hall of shame.

+          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();
+      }
+    }
+  }
+
+ 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;
-      }
-      case IrOpcode::kStoreField: {
-        if (access == FieldAccessOf(effect->op())) {
-          if (object == NodeProperties::GetValueInput(effect, 0)) {
-            Node* const value = NodeProperties::GetValueInput(effect, 1);
-            Type* value_type = NodeProperties::GetType(value);
-            Type* node_type = NodeProperties::GetType(node);
-            // Make sure the replacement's type is a subtype of the node's
-            // type. Otherwise we could confuse optimizations that were
-            // based on the original type.
-            if (value_type->Is(node_type)) {
-              ReplaceWithValue(node, value);
-              return Replace(value);
-            } else {
-              // This LoadField has stronger guarantees than the stored value
-              // can give us, which suggests that we are probably in unreachable
-              // code, guarded by some Check, so don't bother trying to optimize
-              // this LoadField {node}.
-              return NoChange();
-            }
-          }
-          // TODO(turbofan): Alias analysis to the rescue?
-          return NoChange();
-        }
-        break;
-      }
-      case IrOpcode::kBeginRegion:
-      case IrOpcode::kStoreBuffer:
-      case IrOpcode::kStoreElement: {
-        // These can never interfere with field loads.
-        break;
-      }
-      case IrOpcode::kFinishRegion: {
-        // "Look through" FinishRegion nodes to make LoadElimination capable
-        // of looking into atomic regions.
-        if (object == effect) object = NodeProperties::GetValueInput(effect, 0);
-        break;
-      }
-      case IrOpcode::kAllocate: {
-        // Allocations don't interfere with field loads. In case we see the
-        // actual allocation for the {object} we can abort.
-        if (object == effect) return NoChange();
-        break;
-      }
-      default: {
-        if (!effect->op()->HasProperty(Operator::kNoWrite) ||
-            effect->op()->EffectInputCount() != 1) {
-          return NoChange();
-        }
-        break;
-      }
-    }
-  }
-  UNREACHABLE();
-  return NoChange();
+      default:
+        return VisitOtherNode(node);
+    }
+  }
+
+  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;
+      }
+    }
+    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());
+      }
+    }
+    UpdateState(node, state);
+  }
+
+  int FieldIndexOf(FieldAccess const& access) const {
+    if (access.offset % kPointerSize != 0) return -1;
+    int field_index = access.offset / kPointerSize;
+    if (field_index >= static_cast<int>(kMaxTrackedFields)) return -1;
+    return field_index;
+  }
+  AbstractState const* GetState(Node* node) const {
+    return node_states_[node->id()];
+  }
+  void SetState(Node* node, AbstractState const* state) {
+    node_states_[node->id()] = 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);

[Jarin, 2016/07/04 13:18:07]

Should not we also check the size? Either we only handle kPointerSize (and
ignore smaller sizes when loading + dcheck the store size is not bigger) or we
record the access size in the state (and handle the different size
appropriately).

Similarly in the store case.

[Benedikt Meurer, 2016/07/05 11:29:09]

Done.

+    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);
+      }
+    }
+    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);
+      }
+      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 misaligned\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);
+  }
+
+  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);
+  }
+
+  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);
+  }
+
+  void EnqueueUses(Node* node) {
+    for (Edge const edge : node->use_edges()) {
+      if (NodeProperties::IsEffectEdge(edge)) {
+        queue_.push(edge.from());
+      }
+    }
+  }
+
+  AbstractState const* empty_state() const { return &empty_state_; }
+  Zone* zone() const { return node_states_.get_allocator().zone(); }
+
+  ZoneSet<Node*> candidates_;
+  AbstractState const empty_state_;
+  ZoneStack<Node*> queue_;
+  ZoneVector<AbstractState const*> node_states_;
+
+  DISALLOW_COPY_AND_ASSIGN(LoadEliminationAnalysis);
+};
+
+}  // namespace
+
+void LoadElimination::Run() {
+  LoadEliminationAnalysis analysis(graph(), zone());
+  analysis.Run(graph()->start());
 }
 
+Graph* LoadElimination::graph() const { return jsgraph()->graph(); }
+
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8