[turbofan] Sparse representation for state values

src/compiler/state-values-utils.h

 // Copyright 2015 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_STATE_VALUES_UTILS_H_
 #define V8_COMPILER_STATE_VALUES_UTILS_H_
 
 #include "src/compiler/js-graph.h"
 #include "src/globals.h"
 
@@ skipping 15 matching lines @@
 
   struct NodeKey {
     Node* node;
 
     explicit NodeKey(Node* node) : node(node) {}
   };
 
   struct StateValuesKey : public NodeKey {
     // ValueArray - array of nodes ({node} has to be nullptr).
     size_t count;
+    uint32_t mask;
     Node** values;
 
-    StateValuesKey(size_t count, Node** values)
-        : NodeKey(nullptr), count(count), values(values) {}
+    StateValuesKey(size_t count, uint32_t mask, Node** values)
+        : NodeKey(nullptr), count(count), mask(mask), values(values) {}
   };
 
   class ValueArrayIterator;
 
   static bool AreKeysEqual(void* key1, void* key2);
   static bool IsKeysEqualToNode(StateValuesKey* key, Node* node);
   static bool AreValueKeysEqual(StateValuesKey* key1, StateValuesKey* key2);
 
   Node* BuildTree(ValueArrayIterator* it, size_t max_height);
   NodeVector* GetWorkingSpace(size_t level);
   Node* GetEmptyStateValues();
-  Node* GetValuesNodeFromCache(Node** nodes, size_t count);
+  Node* GetValuesNodeFromCache(Node** nodes, size_t count, uint32_t mask);
 
   Graph* graph() { return js_graph_->graph(); }
   CommonOperatorBuilder* common() { return js_graph_->common(); }
 
   Zone* zone() { return graph()->zone(); }
 
   JSGraph* js_graph_;
   CustomMatcherZoneHashMap hash_map_;
   ZoneVector<NodeVector*> working_space_;  // One working space per level.
   Node* empty_state_values_;
@@ skipping 17 matching lines @@
    private:
     friend class StateValuesAccess;
 
     iterator() : current_depth_(-1) {}
     explicit iterator(Node* node);
 
     Node* node();
     MachineType type();
     bool done();
     void Advance();
+    void MoveToNextSibling();
+    void EnsureValid();
 
     struct StatePos {
       Node* node;
+      uint32_t mask;
       int index;
-
-      explicit StatePos(Node* node) : node(node), index(0) {}
-      StatePos() {}
     };
 
     StatePos* Top();
-    void Push(Node* node);
+    void Push(Node* node, uint32_t mask);
     void Pop();
 
     static const int kMaxInlineDepth = 8;
     StatePos stack_[kMaxInlineDepth];
     int current_depth_;
   };
 
   explicit StateValuesAccess(Node* node) : node_(node) {}
 
   size_t size();
   iterator begin() { return iterator(node_); }
   iterator end() { return iterator(); }
 
  private:
   Node* node_;
 };
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8
 
 #endif  // V8_COMPILER_STATE_VALUES_UTILS_H_