[turbofan] Track multiple maps for LoadElimination.

src/compiler/load-elimination.h

Index: src/compiler/load-elimination.h
diff --git a/src/compiler/load-elimination.h b/src/compiler/load-elimination.h
index 985e690bc4e24d71bf13255152d8b0885be6e8ac..d05f1c21d8dd82d441f635d35c09480e2495fb4c 100644
--- a/src/compiler/load-elimination.h
+++ b/src/compiler/load-elimination.h
@@ -6,9 +6,14 @@
 #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.
@@ -149,6 +154,49 @@ class LoadElimination final : public AdvancedReducer {
 
   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() {
@@ -160,6 +208,11 @@ class LoadElimination final : public AdvancedReducer {
     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,
@@ -181,6 +234,7 @@ class LoadElimination final : public AdvancedReducer {
     AbstractChecks const* checks_ = nullptr;
     AbstractElements const* elements_ = nullptr;
     AbstractField const* fields_[kMaxTrackedFields];
+    AbstractMaps const* maps_ = nullptr;
   };
 
   class AbstractStateForEffectNodes final : public ZoneObject {
@@ -219,6 +273,7 @@ class LoadElimination final : public AdvancedReducer {
 
   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(); }