[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"
 
+#include "src/bit-vector.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:

[Jarin, 2016/12/08 07:59:43]

This explanation should probably be in common-operator.h - somewhere close to
StateValues and TypedStateValues.

[Leszek Swirski, 2016/12/08 15:44:31]

Done.

+//
+//   * 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)

[Jarin (Google), 2016/12/07 15:16:44]

If really want to use such a complex encoding scheme, there should be a check in
StateValues constructor making sure that the number of live inputs corresponds
to the input count.

[Leszek Swirski, 2016/12/08 15:44:30]

Done.

+//
+// 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;
   }
+
+  DCHECK(node->opcode() == IrOpcode::kStateValues);
+  uint32_t node_mask = OpParameter<uint32_t>(node);

[Jarin (Google), 2016/12/07 15:16:44]

No OpParameter, please!

[Leszek Swirski, 2016/12/08 15:44:30]

Done.

+
+  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()));
+StateValuesCache::WorkingBuffer& StateValuesCache::GetWorkingSpace(
+    size_t level) {
+  if (working_space_.size() <= level) {
+    working_space_.resize(level + 1);
   }
   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();
+    hash = hash * 23 + (nodes[i] == nullptr ? 0 : 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;
 }
 
+Node* StateValuesCache::BuildTree(size_t& idx, Node** values, size_t count,
+                                  const BitVector* liveness, size_t level) {
+  WorkingBuffer& input_buffer = GetWorkingSpace(level);
+  size_t input_count = 0;
+  bool use_mask = false;
+  uint32_t mask = 0;
 
-class StateValuesCache::ValueArrayIterator {
- public:
-  ValueArrayIterator(Node** values, size_t count)
-      : values_(values), count_(count), current_(0) {}
+  if (level == 0) {
+    // Virtual inputs are the live inputs plus the implicit dead inputs, which
+    // are implied by the liveness mask.
+    size_t virtual_input_count = 0;
+    while (idx < count && input_count < kMaxInputCount &&
+           (!use_mask || virtual_input_count < 31)) {

[Jarin (Google), 2016/12/07 15:16:44]

Magic constants (31) defined at the top of the function, please.

[Leszek Swirski, 2016/12/08 15:44:31]

Done (moved into the new sparse input mask type).

+      DCHECK_LE(idx, static_cast<size_t>(INT_MAX));
+      if (liveness == nullptr || liveness->Contains(static_cast<int>(idx))) {
+        mask |= 1 << virtual_input_count;
+        input_buffer[input_count++] = values[idx];
+      } else {
+        use_mask = true;

[Jarin (Google), 2016/12/07 15:16:44]

What improvement do you see from special casing the all-live case? Is it worth
the extra complexity?

[Leszek Swirski, 2016/12/08 15:44:31]

I haven't measured it, but I've removed it since the iterator still has to make
the same checks regardless so I can't imagine it giving a performance benefit.

I had to keep nodes with (only) subtrees dense, so that I wouldn't have to
fiddle with setting the guard bit conditionally on whether the "dump remaining
nodes" path was taken. Conveniently, this simplified the single-input elision to
only trigger if we have a single StateValue input, and we can get rid of the
wrapper check in GetNodeForValues.

+      }
+      virtual_input_count++;
 
-  void Advance() {
-    if (!done()) {
-      current_++;
+      idx++;
+    }
+
+    if (use_mask) {
+      DCHECK(virtual_input_count < 32);
+      mask |= 1 << virtual_input_count;
+    } else {
+      mask = 0;
+    }
+  } else {
+    while (idx < count && input_count < kMaxInputCount) {
+      if (count - idx < kMaxInputCount - input_count) {
+        // If we have fewer values remaining than inputs remaining, dump the
+        // remaining values into this node.
+
+        // TODO(leszeks): We could optimise this further by counting remaining
+        // live nodes, though this gets complicated with the 31 bit limit on the
+        // mask.

[Jarin (Google), 2016/12/07 15:16:44]

Maybe the remove the comment, the complexity budget on this function is
exhausted.

[Leszek Swirski, 2016/12/08 15:44:30]

Kept the comment (shortened it a bit), after refactoring to simplify this
function.

+
+        // All previous inputs are live.
+        mask = ((1 << input_count) - 1);
+
+        // Add the remaining values as inputs.
+        size_t virtual_input_count = input_count;
+        while (idx < count) {
+          DCHECK_LE(input_count, kMaxInputCount);
+          DCHECK_LE(idx, static_cast<size_t>(INT_MAX));
+          DCHECK(!use_mask || virtual_input_count < 31);
+
+          if (liveness == nullptr ||
+              liveness->Contains(static_cast<int>(idx))) {

[Jarin (Google), 2016/12/07 15:16:44]

This looks very similar to the code above, perhaps it should be factored out?

[Leszek Swirski, 2016/12/08 15:44:30]

Done, I had a TODO for it at some point anyway.

+            mask |= 1 << virtual_input_count;
+            input_buffer[input_count++] = values[idx];
+          } else {
+            use_mask = true;
+          }
+          virtual_input_count++;
+
+          idx++;
+        }
+
+        if (use_mask) {
+          DCHECK(virtual_input_count < 32);
+          mask |= 1 << virtual_input_count;
+        } else {
+          mask = 0;
+        }
+      } else {
+        // Otherwise, add the values to a subtree and add that as an input.
+        Node* subtree = BuildTree(idx, values, count, liveness, level - 1);
+        input_buffer[input_count++] = subtree;
+      }
     }
   }
 
-  bool done() { return current_ >= count_; }
-
-  Node* node() {
-    DCHECK(!done());
-    return values_[current_];
-  }
-
- private:
-  Node** values_;
-  size_t count_;
-  size_t current_;
-};
-
-
-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++) {
-    if (it->done()) break;
-    (*buffer)[count] = BuildTree(it, max_height - 1);
-  }
-  if (count == 1) {
-    return (*buffer)[0];
+  if (input_count == 1 && !use_mask) {
+    // Elide the StateValue node if there is only one input.
+    return input_buffer[0];
   } else {
-    return GetValuesNodeFromCache(&(buffer->front()), count);
+    return GetValuesNodeFromCache(input_buffer.data(), input_count, mask);
   }
 }
 
-
-Node* StateValuesCache::GetNodeForValues(Node** values, size_t count) {
+Node* StateValuesCache::GetNodeForValues(Node** values, size_t count,
+                                         const BitVector* liveness) {
 #if DEBUG
   for (size_t i = 0; i < count; i++) {
-    DCHECK_NE(values[i]->opcode(), IrOpcode::kStateValues);
-    DCHECK_NE(values[i]->opcode(), IrOpcode::kTypedStateValues);
+    if (values[i] != nullptr) {
+      DCHECK_NE(values[i]->opcode(), IrOpcode::kStateValues);
+      DCHECK_NE(values[i]->opcode(), IrOpcode::kTypedStateValues);
+    }
+  }
+  if (liveness != nullptr) {
+    // Liveness can have extra bits for the stack or accumulator, which we
+    // ignore here.
+    DCHECK_LE(count, static_cast<size_t>(liveness->length()));
+
+    for (size_t i = 0; i < count; i++) {
+      if (liveness->Contains(static_cast<int>(i))) {
+        DCHECK_NOT_NULL(values[i]);
+      }
+    }
   }
 #endif
   if (count == 0) {
     return GetEmptyStateValues();
   }
+
+  // This is a worst-case tree height estimate, assuming that all values are
+  // live. We could get a better estimate by counting zeroes in the liveness
+  // vector, but there's no point -- any excess height in the tree will be
+  // collapsed by the single-input elision at the end of BuildTree.
   size_t height = 0;
-  size_t max_nodes = 1;
-  while (count > max_nodes) {
+  size_t max_inputs = kMaxInputCount;
+  while (count > max_inputs) {
     height++;
-    max_nodes *= kMaxInputCount;
+    max_inputs *= kMaxInputCount;
   }
 
-  ValueArrayIterator it(values, count);
-
-  Node* tree = BuildTree(&it, height);
+  size_t idx = 0;
+  Node* tree = BuildTree(idx, values, count, liveness, 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);
+  if (tree->opcode() != IrOpcode::kStateValues) {
+    tree = GetValuesNodeFromCache(&tree, 1, 0u);
   }
 
+#if DEBUG
+  {
+    DCHECK_EQ(count, StateValuesAccess(tree).size());
+    int i;
+    auto access = StateValuesAccess(tree);
+    auto it = access.begin();
+    auto itend = access.end();
+    for (i = 0; it != itend; ++it, ++i) {
+      if (liveness == nullptr || liveness->Contains(i)) {
+        DCHECK((*it).node == values[i]);
+      } else {
+        DCHECK((*it).node == nullptr);
+      }
+    }
+    DCHECK_EQ(static_cast<size_t>(i), count);
+  }
+#endif
+
   return tree;
 }
 
+namespace {
+
+uint32_t GetStateValueMask(Node* node) {

[Jarin (Google), 2016/12/07 15:16:44]

This should live somewhere in common-operator.h

[Leszek Swirski, 2016/12/08 15:44:30]

Done.

+  if (node->opcode() == IrOpcode::kStateValues) {
+    return OpParameter<uint32_t>(node);
+  } else {
+    DCHECK_EQ(node->opcode(), IrOpcode::kTypedStateValues);
+    return OpParameter<TypedStateValueInfo>(node).mask();
+  }
+}
+
+}  // namespace
 
 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;
+  stack_[current_depth_].mask = GetStateValueMask(node);
+
+  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) {

[Jarin (Google), 2016/12/07 15:16:44]

Nit: Why 0x1? On line 446, you say mask & 1. Perhaps you could do the same here
(and below).

Or actually, I see the pattern "mask != 0 && (mask & 0x1) == 0" and "mask == 0
|| (mask & 0x1) == 1" many times here, perhaps factor into a helper function?

[Leszek Swirski, 2016/12/08 15:44:31]

Completely refactored out into sparse input iterator.

+    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.

[Jarin (Google), 2016/12/07 15:16:44]

dead -> optimized_out here and elsewhere

[Leszek Swirski, 2016/12/08 15:44:30]

Done.

+      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;
+      Push(node->InputAt(index), GetStateValueMask(node->InputAt(index)));
+      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 = GetStateValueMask(node_);
+
+  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