[turbofan] Sparse representation for state values

src/compiler/state-values-utils.cc

 // 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.
 
 #include "src/compiler/state-values-utils.h"
 
 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,
                 ZoneAllocationPolicy(zone())),
       working_space_(zone()),
       empty_state_values_(nullptr) {}
 
 
 // static
 bool StateValuesCache::AreKeysEqual(void* key1, void* key2) {
@@ skipping 19 matching lines @@
   }
   UNREACHABLE();
 }
 
 
 // static
 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;
     }
   }
   return true;
 }
 
 
 // static
 bool StateValuesCache::AreValueKeysEqual(StateValuesKey* key1,
                                          StateValuesKey* key2) {
   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;
     }
   }
   return true;
 }
 
 
 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_;
 }
 
 
 NodeVector* StateValuesCache::GetWorkingSpace(size_t level) {
   while (working_space_.size() <= level) {
     void* space = zone()->New(sizeof(NodeVector));
     working_space_.push_back(new (space)
                                  NodeVector(kMaxInputCount, nullptr, zone()));
   }
   return working_space_[level];
 }
 
 namespace {
 
 int StateValuesHashKey(Node** nodes, size_t count) {
   size_t hash = count;
   for (size_t i = 0; i < count; i++) {
     hash = hash * 23 + nodes[i]->id();
   }
   return static_cast<int>(hash & 0x7fffffff);
 }
 
 }  // 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()));
   DCHECK_NOT_NULL(lookup);
   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;
   } else {
     node = reinterpret_cast<Node*>(lookup->value);
   }
   return node;
 }
 
 
@@ skipping 25 matching lines @@
 Node* StateValuesCache::BuildTree(ValueArrayIterator* it, size_t max_height) {
   if (max_height == 0) {
     Node* node = it->node();
     it->Advance();
     return node;
   }
   DCHECK(!it->done());
 
   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 (count == 1) {
+
+  if (use_mask) {
+    DCHECK(idx < 32);
+    mask |= 1 << idx;
+  }
+
+  if (count == 1 && !use_mask) {
     return (*buffer)[0];
   } else {
-    return GetValuesNodeFromCache(&(buffer->front()), count);
+    return GetValuesNodeFromCache(&(buffer->front()), count,
+                                  use_mask ? mask : 0u);
   }
 }
 
 
 Node* StateValuesCache::GetNodeForValues(Node** values, size_t count) {
 #if DEBUG
   for (size_t i = 0; i < count; i++) {
     DCHECK_NE(values[i]->opcode(), IrOpcode::kStateValues);
     DCHECK_NE(values[i]->opcode(), IrOpcode::kTypedStateValues);
   }
 #endif
   if (count == 0) {
     return GetEmptyStateValues();
   }
   size_t height = 0;
   size_t max_nodes = 1;
   while (count > max_nodes) {
     height++;

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

I am guesisng this will get the tree height wrong because it does not take the
optimized_out constants into account. No?

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

Yes, this was my guess too. However, I think that this doesn't really matter,
because over-estimating the height of the tree will only over-allocate the
working space; the actual trees generated should (I think) be collapsed if they
are too tall by the if(count == 1) check in BuildTree.

     max_nodes *= kMaxInputCount;
   }
 
   ValueArrayIterator it(values, count);
 
   Node* tree = BuildTree(&it, height);
 
   // 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();
 }
 
 
 StateValuesAccess::iterator::StatePos* StateValuesAccess::iterator::Top() {
   DCHECK(current_depth_ >= 0);
   DCHECK(current_depth_ < kMaxInlineDepth);
   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;
 }
 
 
 void StateValuesAccess::iterator::Pop() {
   DCHECK(current_depth_ >= 0);
   current_depth_--;
 }
 
 
 bool StateValuesAccess::iterator::done() { return current_depth_ < 0; }
 
 
 void StateValuesAccess::iterator::Advance() {
-  // Advance the current index.
-  Top()->index++;
+  MoveToNextSibling();
+  EnsureValid();
+}
 
-  // Fix up the position to point to a valid node.
+void StateValuesAccess::iterator::MoveToNextSibling() {
+  int mask = Top()->mask;
+  if (mask == 0 || (mask & 0x1) == 1) {
+    Top()->index++;
+  }
+  Top()->mask >>= 1;
+}
+
+void StateValuesAccess::iterator::EnsureValid() {
   while (true) {
-    // TODO(jarin): Factor to a separate method.
+    uint32_t mask = Top()->mask;
+    int index = Top()->index;
     Node* node = Top()->node;
-    int index = Top()->index;
 
-    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);
+  }
 }
 
 
 MachineType StateValuesAccess::iterator::type() {
   Node* state = Top()->node;
   if (state->opcode() == IrOpcode::kStateValues) {
     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];
+    }
   }
 }
 
 
 bool StateValuesAccess::iterator::operator!=(iterator& other) {
   // We only allow comparison with end().
   CHECK(other.done());
   return !done();
 }
 
 
 StateValuesAccess::iterator& StateValuesAccess::iterator::operator++() {
   Advance();
   return *this;
 }
 
 
 StateValuesAccess::TypedNode StateValuesAccess::iterator::operator*() {
   return TypedNode(node(), type());
 }
 
 
 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();
+  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 {
-      count++;
+      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;
 }
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8