[turbofan] Sparse representation for state values

test/unittests/compiler/state-values-utils-unittest.cc

 // Copyright 2014 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/state-values-utils.h"
+#include "src/bit-vector.h"
 #include "test/unittests/compiler/graph-unittest.h"
 #include "test/unittests/compiler/node-test-utils.h"
 #include "test/unittests/test-utils.h"
 #include "testing/gmock/include/gmock/gmock.h"
 
 namespace v8 {
 namespace internal {
 namespace compiler {
 
 class StateValuesIteratorTest : public GraphTest {
  public:
   StateValuesIteratorTest() : GraphTest(3) {}
 
   Node* StateValuesFromVector(NodeVector* nodes) {
     int count = static_cast<int>(nodes->size());
-    return graph()->NewNode(common()->StateValues(count), count,
+    return graph()->NewNode(common()->StateValues(count, 0u), count,
                             count == 0 ? nullptr : &(nodes->front()));
   }
 };
 
 
 TEST_F(StateValuesIteratorTest, SimpleIteration) {
   NodeVector inputs(zone());
   const int count = 10;
   for (int i = 0; i < count; i++) {
     inputs.push_back(Int32Constant(i));
@@ skipping 68 matching lines @@
 
     // Generate the input vector.
     NodeVector inputs(zone());
     for (int i = 0; i < count; i++) {
       inputs.push_back(Int32Constant(i));
     }
 
     // Build the tree.
     StateValuesCache builder(&jsgraph);
     Node* values_node = builder.GetNodeForValues(
-        inputs.size() == 0 ? nullptr : &(inputs.front()), inputs.size());
+        inputs.size() == 0 ? nullptr : &(inputs.front()), inputs.size(),
+        nullptr);
 
     // Check the tree contents with vector.
     int i = 0;
     for (StateValuesAccess::TypedNode node : StateValuesAccess(values_node)) {
       EXPECT_THAT(node.node, IsInt32Constant(i));
       i++;
     }
     EXPECT_EQ(inputs.size(), static_cast<size_t>(i));
   }
 }
 
+TEST_F(StateValuesIteratorTest, TreeFromVectorWithLiveness) {
+  int sizes[] = {0, 1, 2, 100, 5000, 30000};
+  TRACED_FOREACH(int, count, sizes) {
+    JSOperatorBuilder javascript(zone());
+    MachineOperatorBuilder machine(zone());
+    JSGraph jsgraph(isolate(), graph(), common(), &javascript, nullptr,
+                    &machine);
+
+    // Generate the input vector.
+    NodeVector inputs(zone());
+    for (int i = 0; i < count; i++) {
+      inputs.push_back(Int32Constant(i));
+    }
+    // Generate the input liveness.
+    BitVector liveness(count, zone());
+    for (int i = 0; i < count; i++) {
+      if (i % 3 == 0) {
+        liveness.Add(i);
+      }
+    }
+
+    // Build the tree.
+    StateValuesCache builder(&jsgraph);
+    Node* values_node = builder.GetNodeForValues(
+        inputs.size() == 0 ? nullptr : &(inputs.front()), inputs.size(),
+        &liveness);
+
+    // Check the tree contents with vector.
+    int i = 0;
+    for (StateValuesAccess::TypedNode node : StateValuesAccess(values_node)) {
+      if (liveness.Contains(i)) {
+        EXPECT_THAT(node.node, IsInt32Constant(i));
+      } else {
+        EXPECT_EQ(node.node, nullptr);
+      }
+      i++;
+    }
+    EXPECT_EQ(inputs.size(), static_cast<size_t>(i));
+  }
+}
 
 TEST_F(StateValuesIteratorTest, BuildTreeIdentical) {
   int sizes[] = {0, 1, 2, 100, 5000, 30000};
   TRACED_FOREACH(int, count, sizes) {
     JSOperatorBuilder javascript(zone());
     MachineOperatorBuilder machine(zone());
     JSGraph jsgraph(isolate(), graph(), common(), &javascript, nullptr,
                     &machine);
 
     // Generate the input vector.
     NodeVector inputs(zone());
     for (int i = 0; i < count; i++) {
       inputs.push_back(Int32Constant(i));
     }
 
     // Build two trees from the same data.
     StateValuesCache builder(&jsgraph);
     Node* node1 = builder.GetNodeForValues(
-        inputs.size() == 0 ? nullptr : &(inputs.front()), inputs.size());
+        inputs.size() == 0 ? nullptr : &(inputs.front()), inputs.size(),
+        nullptr);
     Node* node2 = builder.GetNodeForValues(
-        inputs.size() == 0 ? nullptr : &(inputs.front()), inputs.size());
+        inputs.size() == 0 ? nullptr : &(inputs.front()), inputs.size(),
+        nullptr);
 
     // The trees should be equal since the data was the same.
     EXPECT_EQ(node1, node2);
+  }
+}
+
+TEST_F(StateValuesIteratorTest, BuildTreeWithLivenessIdentical) {
+  int sizes[] = {0, 1, 2, 100, 5000, 30000};
+  TRACED_FOREACH(int, count, sizes) {
+    JSOperatorBuilder javascript(zone());
+    MachineOperatorBuilder machine(zone());
+    JSGraph jsgraph(isolate(), graph(), common(), &javascript, nullptr,
+                    &machine);
+
+    // Generate the input vector.
+    NodeVector inputs(zone());
+    for (int i = 0; i < count; i++) {
+      inputs.push_back(Int32Constant(i));
+    }
+    // Generate the input liveness.
+    BitVector liveness(count, zone());
+    for (int i = 0; i < count; i++) {
+      if (i % 3 == 0) {
+        liveness.Add(i);
+      }
+    }
+
+    // Build two trees from the same data.
+    StateValuesCache builder(&jsgraph);
+    Node* node1 = builder.GetNodeForValues(
+        inputs.size() == 0 ? nullptr : &(inputs.front()), inputs.size(),
+        &liveness);
+    Node* node2 = builder.GetNodeForValues(
+        inputs.size() == 0 ? nullptr : &(inputs.front()), inputs.size(),
+        &liveness);
+
+    // The trees should be equal since the data was the same.
+    EXPECT_EQ(node1, node2);
   }
 }
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8