[turbofan] Track multiple maps for 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 93c24a08e5cfd6af94a74e6f7e6e876ee601e3e7..5a6a886d6e51c9c9c49f2e6bd842ec19fb61439b 100644
--- a/src/compiler/load-elimination.cc
+++ b/src/compiler/load-elimination.cc
@@ -8,6 +8,8 @@
 #include "src/compiler/js-graph.h"
 #include "src/compiler/node-properties.h"
 #include "src/compiler/simplified-operator.h"
+#include "src/factory.h"
+#include "src/objects-inl.h"
 
 namespace v8 {
 namespace internal {
@@ -320,6 +322,39 @@ void LoadElimination::AbstractField::Print() const {
   }
 }
 
+ZoneHandleSet<Map> LoadElimination::AbstractMaps::Lookup(Node* object) const {
+  for (auto pair : info_for_node_) {
+    if (MustAlias(object, pair.first)) return pair.second;
+  }
+  return ZoneHandleSet<Map>();
+}
+
+LoadElimination::AbstractMaps const* LoadElimination::AbstractMaps::Kill(
+    Node* object, Zone* zone) const {
+  for (auto pair : this->info_for_node_) {
+    if (MayAlias(object, pair.first)) {
+      AbstractMaps* that = new (zone) AbstractMaps(zone);
+      for (auto pair : this->info_for_node_) {
+        if (!MayAlias(object, pair.first)) that->info_for_node_.insert(pair);
+      }
+      return that;
+    }
+  }
+  return this;
+}
+
+void LoadElimination::AbstractMaps::Print() const {
+  for (auto pair : info_for_node_) {
+    PrintF("    #%d:%s\n", pair.first->id(),
+           pair.first->op()->mnemonic());
+    OFStream os(stdout);
+    ZoneHandleSet<Map> const& maps = pair.second;
+    for (size_t i = 0; i < maps.size(); ++i) {
+      os << "     - " << Brief(*maps[i]) << "\n";
+    }
+  }
+}
+
 bool LoadElimination::AbstractState::Equals(AbstractState const* that) const {
   if (this->checks_) {
     if (!that->checks_ || !that->checks_->Equals(this->checks_)) {
@@ -344,6 +379,13 @@ bool LoadElimination::AbstractState::Equals(AbstractState const* that) const {
       return false;
     }
   }
+  if (this->maps_) {
+    if (!that->maps_ || !that->maps_->Equals(this->maps_)) {
+      return false;
+    }
+  } else if (that->maps_) {
+    return false;
+  }
   return true;
 }
 
@@ -372,6 +414,11 @@ void LoadElimination::AbstractState::Merge(AbstractState const* that,
       }
     }
   }
+
+  // Merge the information we have about the maps.
+  if (this->maps_) {
+    this->maps_ = that->maps_ ? that->maps_->Merge(this->maps_, zone) : nullptr;
+  }
 }
 
 Node* LoadElimination::AbstractState::LookupCheck(Node* node) const {
@@ -389,6 +436,38 @@ LoadElimination::AbstractState const* LoadElimination::AbstractState::AddCheck(
   return that;
 }
 
+ZoneHandleSet<Map> LoadElimination::AbstractState::LookupMaps(
+    Node* object) const {
+  if (this->maps_) {
+    return this->maps_->Lookup(object);
+  }
+  return ZoneHandleSet<Map>();
+}
+
+LoadElimination::AbstractState const* LoadElimination::AbstractState::AddMaps(
+    Node* object, ZoneHandleSet<Map> maps, Zone* zone) const {
+  AbstractState* that = new (zone) AbstractState(*this);
+  if (that->maps_) {
+    that->maps_ = that->maps_->Extend(object, maps, zone);
+  } else {
+    that->maps_ = new (zone) AbstractMaps(object, maps, zone);
+  }
+  return that;
+}
+
+LoadElimination::AbstractState const* LoadElimination::AbstractState::KillMaps(
+    Node* object, Zone* zone) const {
+  if (this->maps_) {
+    AbstractMaps const* that_maps = this->maps_->Kill(object, zone);
+    if (this->maps_ != that_maps) {
+      AbstractState* that = new (zone) AbstractState(*this);
+      that->maps_ = that_maps;
+      return that;
+    }
+  }
+  return this;
+}
+
 Node* LoadElimination::AbstractState::LookupElement(Node* object,
                                                     Node* index) const {
   if (this->elements_) {
@@ -461,6 +540,10 @@ void LoadElimination::AbstractState::Print() const {
     PrintF("   checks:\n");
     checks_->Print();
   }
+  if (maps_) {
+    PrintF("   maps:\n");
+    maps_->Print();
+  }
   if (elements_) {
     PrintF("   elements:\n");
     elements_->Print();
@@ -500,23 +583,16 @@ Reduction LoadElimination::ReduceArrayBufferWasNeutered(Node* node) {
 }
 
 Reduction LoadElimination::ReduceCheckMaps(Node* node) {
+  ZoneHandleSet<Map> const maps = CheckMapsParametersOf(node->op()).maps();
   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 const map_input_count = node->op()->ValueInputCount() - 1;
-  if (Node* const object_map =
-          state->LookupField(object, FieldIndexOf(HeapObject::kMapOffset))) {
-    for (int i = 0; i < map_input_count; ++i) {
-      Node* map = NodeProperties::GetValueInput(node, 1 + i);
-      if (map == object_map) return Replace(effect);
-    }
-  }
-  if (map_input_count == 1) {
-    Node* const map0 = NodeProperties::GetValueInput(node, 1);
-    state = state->AddField(object, FieldIndexOf(HeapObject::kMapOffset), map0,
-                            zone());
-  }
+  ZoneHandleSet<Map> object_maps = state->LookupMaps(object);
+  if (object_maps.contains(maps)) return Replace(effect);

[Jarin, 2016/11/16 14:54:41]

Still confused.

If I have MapCheck(m1, m2); MapCheck(m1); this would insert (m1, m2) to the
maps; then when processing MapCheck(m1), the check (m1, m2).contains(m1) would
pass, so we would remove MapCheck(m1), no? That would seem wrong.

[Benedikt Meurer, 2016/12/21 08:36:49]

Done.

+  // TODO(intersect)
+  state = state->KillMaps(object, zone());
+  state = state->AddMaps(object, maps, zone());
   return UpdateState(node, state);
 }
 
@@ -526,18 +602,15 @@ Reduction LoadElimination::ReduceEnsureWritableFastElements(Node* node) {
   Node* const effect = NodeProperties::GetEffectInput(node);
   AbstractState const* state = node_states_.Get(effect);
   if (state == nullptr) return NoChange();
-  Node* fixed_array_map = jsgraph()->FixedArrayMapConstant();
-  if (Node* const elements_map =
-          state->LookupField(elements, FieldIndexOf(HeapObject::kMapOffset))) {
     // Check if the {elements} already have the fixed array map.
-    if (elements_map == fixed_array_map) {
-      ReplaceWithValue(node, elements, effect);
-      return Replace(elements);
-    }
+  ZoneHandleSet<Map> elements_maps = state->LookupMaps(elements);
+  ZoneHandleSet<Map> fixed_array_map(factory()->fixed_array_map());
+  if (elements_maps == fixed_array_map) {
+    ReplaceWithValue(node, elements, effect);
+    return Replace(elements);
   }
   // We know that the resulting elements have the fixed array map.
-  state = state->AddField(node, FieldIndexOf(HeapObject::kMapOffset),
-                          fixed_array_map, zone());
+  state = state->AddMaps(node, fixed_array_map, zone());
   // Kill the previous elements on {object}.
   state =
       state->KillField(object, FieldIndexOf(JSObject::kElementsOffset), zone());
@@ -555,14 +628,12 @@ Reduction LoadElimination::ReduceMaybeGrowFastElements(Node* node) {
   if (state == nullptr) return NoChange();
   if (flags & GrowFastElementsFlag::kDoubleElements) {
     // We know that the resulting elements have the fixed double array map.
-    Node* fixed_double_array_map = jsgraph()->FixedDoubleArrayMapConstant();
-    state = state->AddField(node, FieldIndexOf(HeapObject::kMapOffset),
-                            fixed_double_array_map, zone());
+    state = state->AddMaps(
+        node, ZoneHandleSet<Map>(factory()->fixed_double_array_map()), zone());
   } else {
     // We know that the resulting elements have the fixed array map.
-    Node* fixed_array_map = jsgraph()->FixedArrayMapConstant();
-    state = state->AddField(node, FieldIndexOf(HeapObject::kMapOffset),
-                            fixed_array_map, zone());
+    state = state->AddMaps(
+        node, ZoneHandleSet<Map>(factory()->fixed_array_map()), zone());
   }
   if (flags & GrowFastElementsFlag::kArrayObject) {
     // Kill the previous Array::length on {object}.
@@ -580,11 +651,14 @@ Reduction LoadElimination::ReduceMaybeGrowFastElements(Node* node) {
 
 Reduction LoadElimination::ReduceTransitionElementsKind(Node* node) {
   Node* const object = NodeProperties::GetValueInput(node, 0);
-  Node* const source_map = NodeProperties::GetValueInput(node, 1);
-  Node* const target_map = NodeProperties::GetValueInput(node, 2);
+  // Node* const source_map = NodeProperties::GetValueInput(node, 1);
+  // Node* const target_map = NodeProperties::GetValueInput(node, 2);
   Node* const effect = NodeProperties::GetEffectInput(node);
   AbstractState const* state = node_states_.Get(effect);
   if (state == nullptr) return NoChange();
+  // TODO(bmeurer): Put the map constants onto the operator.
+  // ZoneHandleSet<Map> object_maps = state->LookupMaps(object);
+#if 0
   if (Node* const object_map =
           state->LookupField(object, FieldIndexOf(HeapObject::kMapOffset))) {
     if (target_map == object_map) {
@@ -602,6 +676,9 @@ Reduction LoadElimination::ReduceTransitionElementsKind(Node* node) {
     state =
         state->KillField(object, FieldIndexOf(HeapObject::kMapOffset), zone());
   }
+#else
+  state = state->KillMaps(object, zone());
+#endif
   ElementsTransition transition = ElementsTransitionOf(node->op());
   switch (transition) {
     case ElementsTransition::kFastTransition:
@@ -622,23 +699,34 @@ Reduction LoadElimination::ReduceLoadField(Node* node) {
   Node* const control = NodeProperties::GetControlInput(node);
   AbstractState const* state = node_states_.Get(effect);
   if (state == nullptr) return NoChange();
-  int field_index = FieldIndexOf(access);
-  if (field_index >= 0) {
-    if (Node* replacement = state->LookupField(object, field_index)) {
-      // Make sure we don't resurrect dead {replacement} nodes.
-      if (!replacement->IsDead()) {
-        // We might need to guard the {replacement} if the type of the
-        // {node} is more precise than the type of the {replacement}.
-        Type* const node_type = NodeProperties::GetType(node);
-        if (!NodeProperties::GetType(replacement)->Is(node_type)) {
-          replacement = graph()->NewNode(common()->TypeGuard(node_type),
-                                         replacement, control);
+  if (access.offset == HeapObject::kMapOffset) {
+    DCHECK_EQ(kTaggedBase, access.base_is_tagged);
+    DCHECK(IsAnyTagged(access.machine_type.representation()));
+    ZoneHandleSet<Map> object_maps = state->LookupMaps(object);
+    if (object_maps.size() == 1) {
+      Node* value = jsgraph()->HeapConstant(object_maps[0]);
+      ReplaceWithValue(node, value, effect);
+      return Replace(value);
+    }
+  } else {
+    int field_index = FieldIndexOf(access);
+    if (field_index >= 0) {
+      if (Node* replacement = state->LookupField(object, field_index)) {
+        // Make sure we don't resurrect dead {replacement} nodes.
+        if (!replacement->IsDead()) {
+          // We might need to guard the {replacement} if the type of the
+          // {node} is more precise than the type of the {replacement}.
+          Type* const node_type = NodeProperties::GetType(node);
+          if (!NodeProperties::GetType(replacement)->Is(node_type)) {
+            replacement = graph()->NewNode(common()->TypeGuard(node_type),
+                                           replacement, control);
+          }
+          ReplaceWithValue(node, replacement, effect);
+          return Replace(replacement);
         }
-        ReplaceWithValue(node, replacement, effect);
-        return Replace(replacement);
       }
+      state = state->AddField(object, field_index, node, zone());
     }
-    state = state->AddField(object, field_index, node, zone());
   }
   return UpdateState(node, state);
 }
@@ -650,19 +738,33 @@ Reduction LoadElimination::ReduceStoreField(Node* node) {
   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);
+  if (access.offset == HeapObject::kMapOffset) {
+    DCHECK_EQ(kTaggedBase, access.base_is_tagged);
+    DCHECK(IsAnyTagged(access.machine_type.representation()));
+    // Kill all potential knowledge about the {object}s map.
+    state = state->KillMaps(object, zone());
+    Type* const new_value_type = NodeProperties::GetType(new_value);
+    if (new_value_type->IsConstant()) {
+      // Record the new {object} map information.
+      ZoneHandleSet<Map> object_maps(
+          Handle<Map>::cast(new_value_type->AsConstant()->Value()));
+      state = state->AddMaps(object, object_maps, zone());
     }
-    // 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();
+    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);
 }
@@ -846,8 +948,7 @@ LoadElimination::AbstractState const* LoadElimination::ComputeLoopState(
           }
           case IrOpcode::kTransitionElementsKind: {
             Node* const object = NodeProperties::GetValueInput(current, 0);
-            state = state->KillField(
-                object, FieldIndexOf(HeapObject::kMapOffset), zone());
+            state = state->KillMaps(object, zone());
             state = state->KillField(
                 object, FieldIndexOf(JSObject::kElementsOffset), zone());
             break;
@@ -888,7 +989,8 @@ int LoadElimination::FieldIndexOf(int offset) {
   DCHECK_EQ(0, offset % kPointerSize);
   int field_index = offset / kPointerSize;
   if (field_index >= static_cast<int>(kMaxTrackedFields)) return -1;
-  return field_index;
+  DCHECK_LT(0, field_index);
+  return field_index - 1;
 }
 
 // static
@@ -929,6 +1031,8 @@ CommonOperatorBuilder* LoadElimination::common() const {
 
 Graph* LoadElimination::graph() const { return jsgraph()->graph(); }
 
+Factory* LoadElimination::factory() const { return jsgraph()->factory(); }
+
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8