[turbofan] Sparse representation for state values

src/compiler/state-values-utils.h

Index: src/compiler/state-values-utils.h
diff --git a/src/compiler/state-values-utils.h b/src/compiler/state-values-utils.h
index 14b1b9e59963755c2b0e543becb3c46f3220e994..d5e84d208c33c3b1c2f64e7a93df5acb9aa1be26 100644
--- a/src/compiler/state-values-utils.h
+++ b/src/compiler/state-values-utils.h
@@ -5,12 +5,16 @@
 #ifndef V8_COMPILER_STATE_VALUES_UTILS_H_
 #define V8_COMPILER_STATE_VALUES_UTILS_H_
 
+#include <array>
+#include "src/compiler/common-operator.h"
 #include "src/compiler/js-graph.h"
 #include "src/globals.h"
 
 namespace v8 {
 namespace internal {
 
+class BitVector;
+
 namespace compiler {
 
 class Graph;
@@ -19,10 +23,12 @@ class V8_EXPORT_PRIVATE StateValuesCache {
  public:
   explicit StateValuesCache(JSGraph* js_graph);
 
-  Node* GetNodeForValues(Node** values, size_t count);
+  Node* GetNodeForValues(Node** values, size_t count,
+                         const BitVector* liveness = nullptr);
 
  private:
   static const size_t kMaxInputCount = 8;
+  typedef std::array<Node*, kMaxInputCount> WorkingBuffer;
 
   struct NodeKey {
     Node* node;
@@ -33,22 +39,34 @@ class V8_EXPORT_PRIVATE StateValuesCache {
   struct StateValuesKey : public NodeKey {
     // ValueArray - array of nodes ({node} has to be nullptr).
     size_t count;
+    SparseInputMask mask;
     Node** values;
 
-    StateValuesKey(size_t count, Node** values)
-        : NodeKey(nullptr), count(count), values(values) {}
+    StateValuesKey(size_t count, SparseInputMask 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);
+  // Fills {node_buffer}, starting from {node_count}, with {values}, starting
+  // at {values_idx}, sparsely encoding according to {liveness}. {node_count} is
+  // updated with the new number of inputs in {node_buffer}, and a bitmask of
+  // the sparse encoding is returned.
+  SparseInputMask::BitMaskType FillBufferWithValues(WorkingBuffer* node_buffer,
+                                                    size_t* node_count,
+                                                    size_t* values_idx,
+                                                    Node** values, size_t count,
+                                                    const BitVector* liveness);
+
+  Node* BuildTree(size_t* values_idx, Node** values, size_t count,
+                  const BitVector* liveness, size_t level);
+
+  WorkingBuffer* GetWorkingSpace(size_t level);
   Node* GetEmptyStateValues();
-  Node* GetValuesNodeFromCache(Node** nodes, size_t count);
+  Node* GetValuesNodeFromCache(Node** nodes, size_t count,
+                               SparseInputMask mask);
 
   Graph* graph() { return js_graph_->graph(); }
   CommonOperatorBuilder* common() { return js_graph_->common(); }
@@ -57,7 +75,7 @@ class V8_EXPORT_PRIVATE StateValuesCache {
 
   JSGraph* js_graph_;
   CustomMatcherZoneHashMap hash_map_;
-  ZoneVector<NodeVector*> working_space_;  // One working space per level.
+  ZoneVector<WorkingBuffer> working_space_;  // One working space per level.
   Node* empty_state_values_;
 };
 
@@ -86,21 +104,14 @@ class V8_EXPORT_PRIVATE StateValuesAccess {
     MachineType type();
     bool done();
     void Advance();
+    void EnsureValid();
 
-    struct StatePos {
-      Node* node;
-      int index;
-
-      explicit StatePos(Node* node) : node(node), index(0) {}
-      StatePos() {}
-    };
-
-    StatePos* Top();
+    SparseInputMask::InputIterator* Top();
     void Push(Node* node);
     void Pop();
 
     static const int kMaxInlineDepth = 8;
-    StatePos stack_[kMaxInlineDepth];
+    SparseInputMask::InputIterator stack_[kMaxInlineDepth];
     int current_depth_;
   };