[turbofan] Track multiple maps for LoadElimination.

src/compiler/load-elimination.h

 // 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.
 
 #ifndef V8_COMPILER_LOAD_ELIMINATION_H_
 #define V8_COMPILER_LOAD_ELIMINATION_H_
 
 #include "src/compiler/graph-reducer.h"
+#include "src/zone/zone-handle-set.h"
 
 namespace v8 {
 namespace internal {
+
+// Forward declarations.
+class Factory;
+
 namespace compiler {
 
 // Foward declarations.
 class CommonOperatorBuilder;
 struct FieldAccess;
 class Graph;
 class JSGraph;
 
 class LoadElimination final : public AdvancedReducer {
  public:
@@ skipping 120 matching lines @@
     }
 
     void Print() const;
 
    private:
     ZoneMap<Node*, Node*> info_for_node_;
   };
 
   static size_t const kMaxTrackedFields = 32;
 
+  // Abstract state to approximate the current map of an object along the
+  // effect paths through the graph.
+  class AbstractMaps final : public ZoneObject {
+   public:
+    explicit AbstractMaps(Zone* zone) : info_for_node_(zone) {}
+    AbstractMaps(Node* object, ZoneHandleSet<Map> maps, Zone* zone)
+        : info_for_node_(zone) {
+      info_for_node_.insert(std::make_pair(object, maps));
+    }
+
+    AbstractMaps const* Extend(Node* object, ZoneHandleSet<Map> maps,
+                               Zone* zone) const {
+      AbstractMaps* that = new (zone) AbstractMaps(zone);
+      that->info_for_node_ = this->info_for_node_;
+      that->info_for_node_.insert(std::make_pair(object, maps));
+      return that;
+    }
+    ZoneHandleSet<Map> Lookup(Node* object) const;
+    AbstractMaps const* Kill(Node* object, Zone* zone) const;
+    bool Equals(AbstractMaps const* that) const {
+      return this == that || this->info_for_node_ == that->info_for_node_;
+    }
+    AbstractMaps const* Merge(AbstractMaps const* that, Zone* zone) const {
+      if (this->Equals(that)) return this;
+      AbstractMaps* copy = new (zone) AbstractMaps(zone);
+      for (auto this_it : this->info_for_node_) {
+        Node* this_object = this_it.first;
+        ZoneHandleSet<Map> this_maps = 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_maps) {
+          copy->info_for_node_.insert(this_it);
+        }
+      }
+      return copy;
+    }
+
+    void Print() const;
+
+   private:
+    ZoneMap<Node*, ZoneHandleSet<Map>> info_for_node_;

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

I am super confused about what these sets mean. I would expect that if an object
o has a map-set m, then o's map must be in m.

However, what does empty map-set mean? Since we return empty set for unknown
nodes, does it mean we do not know anything. How do we distinguish from an
impossible set, e.g., if we we mapcheck m1 and then m2? 

+  };
+
   class AbstractState final : public ZoneObject {
    public:
     AbstractState() {
       for (size_t i = 0; i < arraysize(fields_); ++i) {
         fields_[i] = nullptr;
       }
     }
 
     bool Equals(AbstractState const* that) const;
     void Merge(AbstractState const* that, Zone* zone);
 
+    AbstractState const* AddMaps(Node* object, ZoneHandleSet<Map> maps,
+                                 Zone* zone) const;
+    AbstractState const* KillMaps(Node* object, Zone* zone) const;
+    ZoneHandleSet<Map> LookupMaps(Node* object) const;
+
     AbstractState const* AddField(Node* object, size_t index, Node* value,
                                   Zone* zone) const;
     AbstractState const* KillField(Node* object, size_t index,
                                    Zone* zone) const;
     Node* LookupField(Node* object, size_t index) const;
 
     AbstractState const* AddElement(Node* object, Node* index, Node* value,
                                     Zone* zone) const;
     AbstractState const* KillElement(Node* object, Node* index,
                                      Zone* zone) const;
     Node* LookupElement(Node* object, Node* index) const;
 
     AbstractState const* AddCheck(Node* node, Zone* zone) const;
     Node* LookupCheck(Node* node) const;
 
     void Print() const;
 
    private:
     AbstractChecks const* checks_ = nullptr;
     AbstractElements const* elements_ = nullptr;
     AbstractField const* fields_[kMaxTrackedFields];
+    AbstractMaps const* maps_ = nullptr;
   };
 
   class AbstractStateForEffectNodes final : public ZoneObject {
    public:
     explicit AbstractStateForEffectNodes(Zone* zone) : info_for_node_(zone) {}
     AbstractState const* Get(Node* node) const;
     void Set(Node* node, AbstractState const* state);
 
     Zone* zone() const { return info_for_node_.get_allocator().zone(); }
 
@@ skipping 18 matching lines @@
   Reduction UpdateState(Node* node, AbstractState const* state);
 
   AbstractState const* ComputeLoopState(Node* node,
                                         AbstractState const* state) const;
 
   static int FieldIndexOf(int offset);
   static int FieldIndexOf(FieldAccess const& access);
 
   CommonOperatorBuilder* common() const;
   AbstractState const* empty_state() const { return &empty_state_; }
+  Factory* factory() const;
   Graph* graph() const;
   JSGraph* jsgraph() const { return jsgraph_; }
   Zone* zone() const { return node_states_.zone(); }
 
   AbstractState const empty_state_;
   AbstractStateForEffectNodes node_states_;
   JSGraph* const jsgraph_;
 
   DISALLOW_COPY_AND_ASSIGN(LoadElimination);
 };
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8
 
 #endif  // V8_COMPILER_LOAD_ELIMINATION_H_