[turbofan] Track multiple maps for LoadElimination.

src/compiler/load-elimination.cc

 // 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/common-operator.h"
 #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 {
 namespace compiler {
 
 namespace {
 
 enum Aliasing { kNoAlias, kMayAlias, kMustAlias };
 
 Aliasing QueryAlias(Node* a, Node* b) {
@@ skipping 292 matching lines @@
 }
 
 void LoadElimination::AbstractField::Print() const {
   for (auto pair : info_for_node_) {
     PrintF("    #%d:%s -> #%d:%s\n", pair.first->id(),
            pair.first->op()->mnemonic(), pair.second->id(),
            pair.second->op()->mnemonic());
   }
 }
 
+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_)) {
       return false;
     }
   } else if (that->checks_) {
     return false;
   }
   if (this->elements_) {
     if (!that->elements_ || !that->elements_->Equals(this->elements_)) {
       return false;
     }
   } 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;
     }
   }
+  if (this->maps_) {
+    if (!that->maps_ || !that->maps_->Equals(this->maps_)) {
+      return false;
+    }
+  } else if (that->maps_) {
+    return false;
+  }
   return true;
 }
 
 void LoadElimination::AbstractState::Merge(AbstractState const* that,
                                            Zone* zone) {
   // Merge the information we have about the checks.
   if (this->checks_) {
     this->checks_ =
         that->checks_ ? that->checks_->Merge(this->checks_, zone) : nullptr;
   }
 
   // Merge the information we have about the elements.
   if (this->elements_) {
     this->elements_ = that->elements_
                           ? that->elements_->Merge(this->elements_, zone)
                           : nullptr;
   }
 
   // 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;
       }
     }
   }
+
+  // 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 {
   return this->checks_ ? this->checks_->Lookup(node) : nullptr;
 }
 
 LoadElimination::AbstractState const* LoadElimination::AbstractState::AddCheck(
     Node* node, Zone* zone) const {
   AbstractState* that = new (zone) AbstractState(*this);
   if (that->checks_) {
     that->checks_ = that->checks_->Extend(node, zone);
   } else {
     that->checks_ = new (zone) AbstractChecks(node, zone);
   }
   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_) {
     return this->elements_->Lookup(object, index);
   }
   return nullptr;
 }
 
 LoadElimination::AbstractState const*
 LoadElimination::AbstractState::AddElement(Node* object, Node* index,
@@ skipping 52 matching lines @@
     return this_field->Lookup(object);
   }
   return nullptr;
 }
 
 void LoadElimination::AbstractState::Print() const {
   if (checks_) {
     PrintF("   checks:\n");
     checks_->Print();
   }
+  if (maps_) {
+    PrintF("   maps:\n");
+    maps_->Print();
+  }
   if (elements_) {
     PrintF("   elements:\n");
     elements_->Print();
   }
   for (size_t i = 0; i < arraysize(fields_); ++i) {
     if (AbstractField const* const field = fields_[i]) {
       PrintF("   field %zu:\n", i);
       field->Print();
     }
   }
@@ skipping 19 matching lines @@
   if (state == nullptr) return NoChange();
   if (Node* const check = state->LookupCheck(node)) {
     ReplaceWithValue(node, check, effect);
     return Replace(check);
   }
   state = state->AddCheck(node, zone());
   return UpdateState(node, state);
 }
 
 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);
 }
 
 Reduction LoadElimination::ReduceEnsureWritableFastElements(Node* node) {
   Node* const object = NodeProperties::GetValueInput(node, 0);
   Node* const elements = NodeProperties::GetValueInput(node, 1);
   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());
   // Add the new elements on {object}.
   state = state->AddField(object, FieldIndexOf(JSObject::kElementsOffset), node,
                           zone());
   return UpdateState(node, state);
 }
 
 Reduction LoadElimination::ReduceMaybeGrowFastElements(Node* node) {
   GrowFastElementsFlags flags = GrowFastElementsFlagsOf(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();
   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}.
     state =
         state->KillField(object, FieldIndexOf(JSArray::kLengthOffset), zone());
   }
   // Kill the previous elements on {object}.
   state =
       state->KillField(object, FieldIndexOf(JSObject::kElementsOffset), zone());
   // Add the new elements on {object}.
   state = state->AddField(object, FieldIndexOf(JSObject::kElementsOffset), node,
                           zone());
   return UpdateState(node, state);
 }
 
 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) {
       // The {object} already has the {target_map}, so this TransitionElements
       // {node} is fully redundant (independent of what {source_map} is).
       return Replace(effect);
     }
     state =
         state->KillField(object, FieldIndexOf(HeapObject::kMapOffset), zone());
     if (source_map == object_map) {
       state = state->AddField(object, FieldIndexOf(HeapObject::kMapOffset),
                               target_map, zone());
     }
   } else {
     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:
       break;
     case ElementsTransition::kSlowTransition:
       // Kill the elements as well.
       state = state->KillField(object, FieldIndexOf(JSObject::kElementsOffset),
                                zone());
       break;
   }
   return UpdateState(node, state);
 }
 
 Reduction LoadElimination::ReduceLoadField(Node* node) {
   FieldAccess const& access = FieldAccessOf(node->op());
   Node* const object = NodeProperties::GetValueInput(node, 0);
   Node* const effect = NodeProperties::GetEffectInput(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);
 }
 
 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);
+  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);
 }
 
 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);
   Node* const control = NodeProperties::GetControlInput(node);
   AbstractState const* state = node_states_.Get(effect);
@@ skipping 163 matching lines @@
             state = state->KillField(
                 object, FieldIndexOf(JSObject::kElementsOffset), zone());
             if (flags & GrowFastElementsFlag::kArrayObject) {
               state = state->KillField(
                   object, FieldIndexOf(JSArray::kLengthOffset), zone());
             }
             break;
           }
           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;
           }
           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());
@@ skipping 20 matching lines @@
     }
   }
   return state;
 }
 
 // static
 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
 int LoadElimination::FieldIndexOf(FieldAccess const& access) {
   MachineRepresentation rep = access.machine_type.representation();
   switch (rep) {
     case MachineRepresentation::kNone:
     case MachineRepresentation::kBit:
       UNREACHABLE();
       break;
@@ skipping 20 matching lines @@
   DCHECK_EQ(kTaggedBase, access.base_is_tagged);
   return FieldIndexOf(access.offset);
 }
 
 CommonOperatorBuilder* LoadElimination::common() const {
   return jsgraph()->common();
 }
 
 Graph* LoadElimination::graph() const { return jsgraph()->graph(); }
 
+Factory* LoadElimination::factory() const { return jsgraph()->factory(); }
+
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8