[Interpreter] Add support for jumps using constants with wide operands.

src/interpreter/constant-array-builder.cc

Index: src/interpreter/constant-array-builder.cc
diff --git a/src/interpreter/constant-array-builder.cc b/src/interpreter/constant-array-builder.cc
new file mode 100644
index 0000000000000000000000000000000000000000..18fbfd609c44ffe36f5d4be5f2d625bb2cc11cfa
--- /dev/null
+++ b/src/interpreter/constant-array-builder.cc
@@ -0,0 +1,193 @@
+// 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/interpreter/constant-array-builder.h"
+
+#include "src/isolate.h"
+#include "src/objects-inl.h"
+
+namespace v8 {
+namespace internal {
+namespace interpreter {
+
+ConstantArrayBuilder::ConstantArraySlice::ConstantArraySlice(Zone* zone,
+                                                             int width)

[rmcilroy, 2016/01/04 17:05:48]

The width thing is a bit complex - I think it would be simpler just to have a
start_index and end_index, WDYT ?

[oth, 2016/01/05 09:30:08]

Yes, this shouldn't have been left in.

+    : width_(width), reserved_(0), constants_(zone) {}
+
+
+size_t ConstantArrayBuilder::ConstantArraySlice::reserved() const {
+  return reserved_;
+}
+
+
+size_t ConstantArrayBuilder::ConstantArraySlice::size() const {
+  return constants_.size();
+}
+
+
+size_t ConstantArrayBuilder::ConstantArraySlice::free() const {

[rmcilroy, 2016/01/04 17:05:48]

free is a bit of an overloaded name. How about remaining().

[oth, 2016/01/05 09:30:08]

Glass half-full? available() :-)

[rmcilroy, 2016/01/05 13:46:10]

SGTM :).

+  return capacity() - reserved_ - constants_.size();
+}
+
+
+size_t ConstantArrayBuilder::ConstantArraySlice::start_index() const {
+  size_t shift = 8u * (width_ - 1u);
+  return (static_cast<size_t>(1) << shift) & ~0xffu;
+}
+
+
+size_t ConstantArrayBuilder::ConstantArraySlice::capacity() const {
+  size_t shift = 8u * width_;
+  return (static_cast<size_t>(1) << shift) - start_index();
+}
+
+
+void ConstantArrayBuilder::ConstantArraySlice::reserve() {
+  DCHECK_GT(free(), 0u);
+  reserved_++;
+  DCHECK_LE(reserved_, capacity() - constants_.size());
+}
+
+
+void ConstantArrayBuilder::ConstantArraySlice::unreserve() {
+  DCHECK_GT(reserved_, 0u);
+  reserved_--;
+}
+
+
+size_t ConstantArrayBuilder::ConstantArraySlice::allocate(
+    Handle<Object> object) {
+  DCHECK_GT(free(), 0u);
+  size_t index = constants_.size();
+  DCHECK_LT(index, capacity());
+  constants_.push_back(object);
+  return index + start_index();
+}
+
+
+Handle<Object> ConstantArrayBuilder::ConstantArraySlice::at(
+    size_t index) const {
+  return constants_[index - start_index()];
+}
+
+
+STATIC_CONST_MEMBER_DEFINITION const size_t ConstantArrayBuilder::kMaxCapacity;
+STATIC_CONST_MEMBER_DEFINITION const size_t ConstantArrayBuilder::kLowCapacity;

[rmcilroy, 2016/01/04 17:05:48]

Do you need these? I didn't think you needed them unless you took the address of
the static const?

[oth, 2016/01/05 09:30:08]

Yes, both external linkage and taking the constant's address requires these. The
unittests for ConstantArrayBuilder use this.

+
+
+ConstantArrayBuilder::ConstantArrayBuilder(Isolate* isolate, Zone* zone)
+    : isolate_(isolate),
+      idx8_slice_(zone, 1),
+      idx16_slice_(zone, 2),
+      constants_map_(isolate->heap(), zone) {
+  DCHECK_EQ(idx8_slice_.start_index(), 0u);
+  DCHECK_EQ(idx8_slice_.capacity(), kLowCapacity);
+  DCHECK_EQ(idx16_slice_.start_index(), kLowCapacity);
+  DCHECK_EQ(idx16_slice_.capacity(), kMaxCapacity - kLowCapacity);
+}
+
+
+size_t ConstantArrayBuilder::size() const {
+  if (idx16_slice_.size() > 0) {
+    return idx16_slice_.start_index() + idx16_slice_.size();
+  } else {
+    return idx8_slice_.size();
+  }
+}
+
+
+Handle<Object> ConstantArrayBuilder::at(size_t index) const {
+  if (index >= idx16_slice_.start_index()) {
+    return idx16_slice_.at(index);
+  } else if (index < idx8_slice_.size()) {
+    return idx8_slice_.at(index);
+  } else {
+    return isolate_->factory()->the_hole_value();
+  }
+}
+
+
+Handle<FixedArray> ConstantArrayBuilder::ToFixedArray(
+    Factory* factory, PretenureFlag pretenure) const {
+  Handle<FixedArray> fixed_array =
+      factory->NewFixedArray(static_cast<int>(size()), pretenure);
+  for (int i = 0; i < fixed_array->length(); i++) {
+    fixed_array->set(i, *at(static_cast<size_t>(i)));
+  }
+  return fixed_array;
+}
+
+
+size_t ConstantArrayBuilder::Insert(Handle<Object> object) {
+  index_t* entry = constants_map_.Find(object);
+  return (entry == nullptr) ? AllocateEntry(object) : *entry;
+}
+
+
+ConstantArrayBuilder::index_t ConstantArrayBuilder::AllocateEntry(
+    Handle<Object> object) {
+  DCHECK(!object->IsOddball());
+  size_t index;
+  index_t* entry = constants_map_.Get(object);
+  if (idx8_slice_.free() > 0) {
+    index = idx8_slice_.allocate(object);
+    DCHECK_LT(index, idx8_slice_.capacity());
+  } else {
+    index = idx16_slice_.allocate(object);
+    DCHECK_LT(index, idx8_slice_.capacity() + idx16_slice_.capacity());
+  }
+  *entry = static_cast<index_t>(index);
+  return *entry;
+}
+
+
+ConstantArrayBuilder::ReservationToken
+ConstantArrayBuilder::CreateReservedEntry() {
+  if (idx8_slice_.free() > 0) {
+    idx8_slice_.reserve();
+    return ReservationToken::kIdx8;
+  } else {
+    idx16_slice_.reserve();
+    return ReservationToken::kIdx16;
+  }
+}
+
+
+size_t ConstantArrayBuilder::CommitReservedEntry(ReservationToken token,
+                                                 Handle<Object> object) {
+  DiscardReservedEntry(token);
+  size_t index;
+  index_t* entry = constants_map_.Find(object);
+  if (nullptr == entry) {
+    index = AllocateEntry(object);
+  } else {
+    if (token == ReservationToken::kIdx8 && *entry >= idx8_slice_.capacity()) {

[rmcilroy, 2016/01/04 17:05:48]

Could the opposite happen (token == kIdx16 but we got an entry in kIdx8)? I
suppose this doesn't matter if it does since the wide variant will still work?

[oth, 2016/01/05 09:30:08]

If the opposite happens it doesn't matter. The bytecode stream has space for a
2-byte operand. The emitted bytecode will be for a 2-byte operand and it get's
appropriately zero padded. Any subsequent duplicate object additions will get
the 1-byte operand index.

+      // The object is already in the constant array, but has an index
+      // outside the range of an idx8 operand so we need to create a
+      // duplicate entry in the idx8 operand range to satisfy the
+      // commitment.
+      *entry = static_cast<index_t>(idx8_slice_.allocate(object));
+    }
+    index = *entry;
+  }
+  DCHECK(token == ReservationToken::kIdx16 || index < idx8_slice_.capacity());
+  DCHECK_LT(index, kMaxCapacity);
+  return index;
+}
+
+
+void ConstantArrayBuilder::DiscardReservedEntry(ReservationToken token) {
+  switch (token) {
+    case ReservationToken::kIdx8:
+      idx8_slice_.unreserve();
+      return;
+    case ReservationToken::kIdx16:
+      idx16_slice_.unreserve();
+      return;
+  }
+}
+
+}  // namespace interpreter
+}  // namespace internal
+}  // namespace v8