[turbofan] Sparse representation for state values

src/compiler/state-values-utils.cc

Index: src/compiler/state-values-utils.cc
diff --git a/src/compiler/state-values-utils.cc b/src/compiler/state-values-utils.cc
index e8310d7d56ed95cb4ebaaa75b86ed56379ea9940..25a7d45072e5efb2b4bb09bfa6a18374cdd66c6c 100644
--- a/src/compiler/state-values-utils.cc
+++ b/src/compiler/state-values-utils.cc
@@ -8,6 +8,19 @@ namespace v8 {
 namespace internal {
 namespace compiler {
 
+// A (Typed)StateValues node's has a bitmask specifying if its inputs are
+// represented sparsely. If the bitmask value is 0, then the inputs are not
+// sparse; otherwise, they should be interpreted as follows:
+//
+//   * The bitmask represents which values are live, with 1 for live values
+//     and 0 for dead (optimized out) values.
+//   * The inputs to the node are the live values, in the order of the 1s from
+//     least- to most-significant
+//   * The top bit of the bitmask is a guard indicating the end of the values,
+//     whether live or dead (and is not representative of a live node)
+//
+// So, for N 1s in the bitmask, there are N - 1 inputs into the node.
+
 StateValuesCache::StateValuesCache(JSGraph* js_graph)
     : js_graph_(js_graph),
       hash_map_(AreKeysEqual, ZoneHashMap::kDefaultHashMapCapacity,
@@ -47,6 +60,20 @@ bool StateValuesCache::IsKeysEqualToNode(StateValuesKey* key, Node* node) {
   if (key->count != static_cast<size_t>(node->InputCount())) {
     return false;
   }
+
+  uint32_t node_mask;
+  if (node->opcode() == IrOpcode::kStateValues) {
+    node_mask = OpParameter<uint32_t>(node);
+  } else if (node->opcode() == IrOpcode::kTypedStateValues) {

[Jarin, 2016/11/16 15:32:42]

Does the TypedStateValues actually ever get here?

[Leszek Swirski, 2016/11/17 09:23:04]

Good point, probably not.

+    node_mask = OpParameter<std::pair<const void*, uint32_t>>(node).second;
+  } else {
+    return false;
+  }
+
+  if (node_mask != key->mask) {
+    return false;
+  }
+
   for (size_t i = 0; i < key->count; i++) {
     if (key->values[i] != node->InputAt(static_cast<int>(i))) {
       return false;
@@ -62,6 +89,9 @@ bool StateValuesCache::AreValueKeysEqual(StateValuesKey* key1,
   if (key1->count != key2->count) {
     return false;
   }
+  if (key1->mask != key2->mask) {
+    return false;
+  }
   for (size_t i = 0; i < key1->count; i++) {
     if (key1->values[i] != key2->values[i]) {
       return false;
@@ -73,7 +103,7 @@ bool StateValuesCache::AreValueKeysEqual(StateValuesKey* key1,
 
 Node* StateValuesCache::GetEmptyStateValues() {
   if (empty_state_values_ == nullptr) {
-    empty_state_values_ = graph()->NewNode(common()->StateValues(0));
+    empty_state_values_ = graph()->NewNode(common()->StateValues(0, 0u));
   }
   return empty_state_values_;
 }
@@ -100,9 +130,9 @@ int StateValuesHashKey(Node** nodes, size_t count) {
 
 }  // namespace
 
-
-Node* StateValuesCache::GetValuesNodeFromCache(Node** nodes, size_t count) {
-  StateValuesKey key(count, nodes);
+Node* StateValuesCache::GetValuesNodeFromCache(Node** nodes, size_t count,
+                                               uint32_t mask) {
+  StateValuesKey key(count, mask, nodes);
   int hash = StateValuesHashKey(nodes, count);
   ZoneHashMap::Entry* lookup =
       hash_map_.LookupOrInsert(&key, hash, ZoneAllocationPolicy(zone()));
@@ -110,8 +140,8 @@ Node* StateValuesCache::GetValuesNodeFromCache(Node** nodes, size_t count) {
   Node* node;
   if (lookup->value == nullptr) {
     int input_count = static_cast<int>(count);
-    node = graph()->NewNode(common()->StateValues(input_count), input_count,
-                            nodes);
+    node = graph()->NewNode(common()->StateValues(input_count, mask),
+                            input_count, nodes);
     NodeKey* new_key = new (zone()->New(sizeof(NodeKey))) NodeKey(node);
     lookup->key = new_key;
     lookup->value = node;
@@ -157,14 +187,34 @@ Node* StateValuesCache::BuildTree(ValueArrayIterator* it, size_t max_height) {
 
   NodeVector* buffer = GetWorkingSpace(max_height);
   size_t count = 0;
-  for (; count < kMaxInputCount; count++) {
+  size_t idx = 0;
+  uint32_t mask = 0;
+  bool use_mask = false;
+  while (count < kMaxInputCount && (!use_mask || idx < 31)) {
     if (it->done()) break;
-    (*buffer)[count] = BuildTree(it, max_height - 1);
+
+    Node* subtree = BuildTree(it, max_height - 1);
+    if (subtree == js_graph_->OptimizedOutConstant() && idx < 31) {
+      use_mask = true;
+      idx++;
+    } else {
+      mask |= 1 << idx;
+      (*buffer)[count] = subtree;
+      idx++;
+      count++;
+    }
+  }
+
+  if (use_mask) {
+    DCHECK(idx < 32);
+    mask |= 1 << idx;
   }
-  if (count == 1) {
+
+  if (count == 1 && !use_mask) {
     return (*buffer)[0];
   } else {
-    return GetValuesNodeFromCache(&(buffer->front()), count);
+    return GetValuesNodeFromCache(&(buffer->front()), count,
+                                  use_mask ? mask : 0u);
   }
 }
 
@@ -193,19 +243,44 @@ Node* StateValuesCache::GetNodeForValues(Node** values, size_t count) {
   // If the 'tree' is a single node, equip it with a StateValues wrapper.
   if (tree->opcode() != IrOpcode::kStateValues &&
       tree->opcode() != IrOpcode::kTypedStateValues) {
-    tree = GetValuesNodeFromCache(&tree, 1);
+    tree = GetValuesNodeFromCache(&tree, 1, 0u);
+  }
+
+#if DEBUG
+  {
+    DCHECK_EQ(count, StateValuesAccess(tree).size());
+    size_t i = 0;
+    auto access = StateValuesAccess(tree);
+    auto it = access.begin();
+    auto itend = access.end();
+    for (; it != itend; ++it) {
+      DCHECK(values[i] == (*it).node ||
+             values[i] == js_graph_->OptimizedOutConstant() &&
+                 (*it).node == nullptr);
+      ++i;
+    }
+    DCHECK_EQ(i, count);
   }
+#endif
 
   return tree;
 }
 
 
 StateValuesAccess::iterator::iterator(Node* node) : current_depth_(0) {
-  // A hacky way initialize - just set the index before the node we want
-  // to process and then advance to it.
   stack_[current_depth_].node = node;
-  stack_[current_depth_].index = -1;
-  Advance();
+  stack_[current_depth_].index = 0;
+
+  uint32_t input_mask;
+  if (node->opcode() == IrOpcode::kStateValues) {
+    input_mask = OpParameter<uint32_t>(node);
+  } else {
+    DCHECK_EQ(node->opcode(), IrOpcode::kTypedStateValues);
+    input_mask = OpParameter<std::pair<const void*, uint32_t>>(node).second;
+  }
+  stack_[current_depth_].mask = input_mask;
+
+  EnsureValid();
 }
 
 
@@ -215,11 +290,11 @@ StateValuesAccess::iterator::StatePos* StateValuesAccess::iterator::Top() {
   return &(stack_[current_depth_]);
 }
 
-
-void StateValuesAccess::iterator::Push(Node* node) {
+void StateValuesAccess::iterator::Push(Node* node, uint32_t mask) {
   current_depth_++;
   CHECK(current_depth_ < kMaxInlineDepth);
   stack_[current_depth_].node = node;
+  stack_[current_depth_].mask = mask;
   stack_[current_depth_].index = 0;
 }
 
@@ -234,37 +309,71 @@ bool StateValuesAccess::iterator::done() { return current_depth_ < 0; }
 
 
 void StateValuesAccess::iterator::Advance() {
-  // Advance the current index.
-  Top()->index++;
+  MoveToNextSibling();
+  EnsureValid();
+}
+
+void StateValuesAccess::iterator::MoveToNextSibling() {
+  int mask = Top()->mask;
+  if (mask == 0 || (mask & 0x1) == 1) {
+    Top()->index++;
+  }
+  Top()->mask >>= 1;
+}
 
-  // Fix up the position to point to a valid node.
+void StateValuesAccess::iterator::EnsureValid() {
   while (true) {
-    // TODO(jarin): Factor to a separate method.
-    Node* node = Top()->node;
+    uint32_t mask = Top()->mask;
     int index = Top()->index;
+    Node* node = Top()->node;
 
-    if (index >= node->InputCount()) {
-      // Pop stack and move to the next sibling.
+    if (mask != 0 && (mask & 0x1) == 0) {
+      // We are on a valid (dead) node.
+      return;
+    }
+
+    if (mask == 1 || (mask == 0 && index >= node->InputCount())) {
+      // We have hit the guard bit or exhausted our inputs. Pop the stack and
+      // move to the next sibling.
       Pop();
       if (done()) {
         // Stack is exhausted, we have reached the end.
         return;
       }
-      Top()->index++;
-    } else if (node->InputAt(index)->opcode() == IrOpcode::kStateValues ||
-               node->InputAt(index)->opcode() == IrOpcode::kTypedStateValues) {
+      MoveToNextSibling();
+      continue;
+    }
+
+    // At this point the value is known to be live and within our input nodes.
+    Node* value_node = node->InputAt(Top()->index);
+
+    if (value_node->opcode() == IrOpcode::kStateValues ||
+        value_node->opcode() == IrOpcode::kTypedStateValues) {
       // Nested state, we need to push to the stack.
-      Push(node->InputAt(index));
-    } else {
-      // We are on a valid node, we can stop the iteration.
-      return;
+      uint32_t input_mask;
+      if (node->InputAt(index)->opcode() == IrOpcode::kStateValues) {
+        input_mask = OpParameter<uint32_t>(node->InputAt(index));
+      } else {
+        input_mask =
+            OpParameter<std::pair<const void*, uint32_t>>(node->InputAt(index))
+                .second;
+      }
+      Push(node->InputAt(index), input_mask);
+      continue;
     }
+
+    // We are on a valid node, we can stop the iteration.
+    return;
   }
 }
 
 
 Node* StateValuesAccess::iterator::node() {
-  return Top()->node->InputAt(Top()->index);
+  if (Top()->mask != 0 && (Top()->mask & 0x1) == 0) {
+    return nullptr;
+  } else {
+    return Top()->node->InputAt(Top()->index);
+  }
 }
 
 
@@ -274,8 +383,13 @@ MachineType StateValuesAccess::iterator::type() {
     return MachineType::AnyTagged();
   } else {
     DCHECK_EQ(IrOpcode::kTypedStateValues, state->opcode());
-    ZoneVector<MachineType> const* types = MachineTypesOf(state->op());
-    return (*types)[Top()->index];
+
+    if (Top()->mask != 0 && (Top()->mask & 0x1) == 0) {
+      return MachineType::None();
+    } else {
+      ZoneVector<MachineType> const* types = MachineTypesOf(state->op());
+      return (*types)[Top()->index];
+    }
   }
 }
 
@@ -300,14 +414,29 @@ StateValuesAccess::TypedNode StateValuesAccess::iterator::operator*() {
 
 size_t StateValuesAccess::size() {
   size_t count = 0;
-  for (int i = 0; i < node_->InputCount(); i++) {
-    if (node_->InputAt(i)->opcode() == IrOpcode::kStateValues ||
-        node_->InputAt(i)->opcode() == IrOpcode::kTypedStateValues) {
-      count += StateValuesAccess(node_->InputAt(i)).size();
-    } else {
+  uint32_t mask = 0;
+  if (node_->opcode() == IrOpcode::kStateValues) {
+    mask = OpParameter<uint32_t>(node_);
+  } else if (node_->opcode() == IrOpcode::kTypedStateValues) {
+    mask = OpParameter<std::pair<const void*, uint32_t>>(node_).second;
+  }
+
+  int i = 0;
+  while ((mask == 0 && i < node_->InputCount()) || (mask != 0 && mask != 1)) {
+    if (mask != 0 && (mask & 1) == 0) {
       count++;
+    } else {
+      if (node_->InputAt(i)->opcode() == IrOpcode::kStateValues ||
+          node_->InputAt(i)->opcode() == IrOpcode::kTypedStateValues) {
+        count += StateValuesAccess(node_->InputAt(i)).size();
+      } else {
+        count++;
+      }
+      i++;
     }
+    mask >>= 1;
   }
+
   return count;
 }