[turbofan] Sparse representation for state values

src/compiler/common-operator.h

Index: src/compiler/common-operator.h
diff --git a/src/compiler/common-operator.h b/src/compiler/common-operator.h
index b4685f005a6294ba177e69ae9bb231a608226851..e80304b99cc5e8bfc2059bb332a194bb603e32fc 100644
--- a/src/compiler/common-operator.h
+++ b/src/compiler/common-operator.h
@@ -22,6 +22,7 @@ class CallDescriptor;
 struct CommonOperatorGlobalCache;
 class Operator;
 class Type;
+class Node;
 
 // Prediction hint for branches.
 enum class BranchHint : uint8_t { kNone, kTrue, kFalse };
@@ -158,6 +159,122 @@ std::ostream& operator<<(std::ostream&, RelocatablePtrConstantInfo const&);
 
 size_t hash_value(RelocatablePtrConstantInfo const& p);
 
+// Used to define a sparse set of inputs. This can be used to efficiently encode
+// nodes that can have a lot of inputs, but where many inputs can have the same
+// value.
+//
+// The sparse input mask has a bitmask specifying if the node's inputs are
+// represented sparsely. If the bitmask value is 0, then the inputs are dense;
+// otherwise, they should be interpreted as follows:
+//
+//   * The bitmask represents which values are real, with 1 for real values
+//     and 0 for empty values.
+//   * The inputs to the node are the real 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 real or empty (and is not representative of a real input itself).
+//     This is used so that we don't have to additionally store a value count.
+//
+// So, for N 1s in the bitmask, there are N - 1 inputs into the node.

[Jarin, 2016/12/10 10:15:06]

Perhaps move lines 166-178 to the actual mask field (line 249) so that people
only read the text when interested in internals of the class.

[Leszek Swirski, 2016/12/13 14:35:16]

Good idea, done.

+class SparseInputMask final {
+ public:
+  typedef uint32_t BitMaskType;
+
+  // The mask representing a dense input set.
+  static const BitMaskType kDenseBitMask = 0x0;
+  // The bits representing the end of a sparse input set.
+  static const BitMaskType kEndMarker = 0x1;
+  // The mask for accessing a sparse input entry in the bitmask.
+  static const BitMaskType kEntryMask = 0x1;
+
+  // The number of bits in the mask, minus one for the end marker.
+  static const int kMaxSparseInputs = (sizeof(BitMaskType) * kBitsPerByte - 1);
+
+  // An iterator over a node's sparse inputs.
+  class InputIterator final {
+   public:
+    InputIterator() {}
+    InputIterator(BitMaskType bit_mask, Node* parent);
+
+    Node* parent() const { return parent_; }
+    int real_index() const { return real_index_; }
+
+    // Advance the iterator to the next sparse input. Only valid if the iterator
+    // has not reached the end.
+    void Advance();
+
+    // Get the current sparse input's real node value. Only valid if the
+    // current sparse input is real.
+    Node* GetReal() const;
+
+    // Get the current sparse input, returning either a real input node if
+    // the current sparse input is real, or the given {empty_value} if the
+    // current sparse input is empty.
+    Node* Get(Node* empty_value) const {
+      return IsReal() ? GetReal() : empty_value;
+    }
+
+    // True if the current sparse input is a real input node.
+    bool IsReal() const;
+
+    // True if the current sparse input is an empty value.
+    bool IsEmpty() const { return !IsReal(); }
+
+    // True if the iterator has reached the end of the sparse inputs.
+    bool IsEnd() const;
+
+   private:
+    BitMaskType bit_mask_;
+    Node* parent_;
+    int real_index_;
+  };
+
+  explicit SparseInputMask(BitMaskType bit_mask) : bit_mask_(bit_mask) {}
+
+  // Provides a SparseInputMask representing a dense input set.
+  static SparseInputMask Dense() { return SparseInputMask(kDenseBitMask); }
+
+  BitMaskType mask() const { return bit_mask_; }
+
+  bool IsDense() const { return bit_mask_ == SparseInputMask::kDenseBitMask; }
+
+  // Counts how many real values are in the sparse array. Only valid for
+  // non-dense masks.
+  int CountReal() const;
+
+  // Returns an iterator over the sparse inputs of {node}.
+  InputIterator IterateOverInputs(Node* node);
+
+ private:
+  BitMaskType bit_mask_;
+};
+
+bool operator==(SparseInputMask const& lhs, SparseInputMask const& rhs);
+bool operator!=(SparseInputMask const& lhs, SparseInputMask const& rhs);
+
+class TypedStateValueInfo final {
+ public:
+  TypedStateValueInfo(ZoneVector<MachineType> const* machine_types,
+                      SparseInputMask sparse_input_mask)
+      : machine_types_(machine_types), sparse_input_mask_(sparse_input_mask) {}
+
+  ZoneVector<MachineType> const* machine_types() const {
+    return machine_types_;
+  }
+  SparseInputMask sparse_input_mask() const { return sparse_input_mask_; }
+
+ private:
+  ZoneVector<MachineType> const* machine_types_;
+  SparseInputMask sparse_input_mask_;
+};
+
+bool operator==(TypedStateValueInfo const& lhs, TypedStateValueInfo const& rhs);
+bool operator!=(TypedStateValueInfo const& lhs, TypedStateValueInfo const& rhs);
+
+std::ostream& operator<<(std::ostream&, TypedStateValueInfo const&);
+
+size_t hash_value(TypedStateValueInfo const& p);
+
 // Used to mark a region (as identified by BeginRegion/FinishRegion) as either
 // JavaScript-observable or not (i.e. allocations are not JavaScript observable
 // themselves, but transitioning stores are).
@@ -181,6 +298,8 @@ size_t hash_value(OsrGuardType type);
 std::ostream& operator<<(std::ostream&, OsrGuardType);
 OsrGuardType OsrGuardTypeOf(Operator const*);
 
+SparseInputMask SparseInputMaskOf(Operator const*);
+
 ZoneVector<MachineType> const* MachineTypesOf(Operator const*)
     WARN_UNUSED_RESULT;
 
@@ -243,8 +362,9 @@ class V8_EXPORT_PRIVATE CommonOperatorBuilder final
   const Operator* Checkpoint();
   const Operator* BeginRegion(RegionObservability);
   const Operator* FinishRegion();
-  const Operator* StateValues(int arguments);
-  const Operator* TypedStateValues(const ZoneVector<MachineType>* types);
+  const Operator* StateValues(int arguments, SparseInputMask bitmask);
+  const Operator* TypedStateValues(const ZoneVector<MachineType>* types,
+                                   SparseInputMask bitmask);
   const Operator* ObjectState(int pointer_slots);
   const Operator* TypedObjectState(const ZoneVector<MachineType>* types);
   const Operator* FrameState(BailoutId bailout_id,