[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..5bb53601b8fdce840360a9fb84a3daf62a6a26ff
--- /dev/null
+++ b/src/interpreter/constant-array-builder.cc
@@ -0,0 +1,146 @@
+// 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 {
+
+STATIC_CONST_MEMBER_DEFINITION const size_t ConstantArrayBuilder::kMaxCapacity;
+STATIC_CONST_MEMBER_DEFINITION const size_t ConstantArrayBuilder::kLowCapacity;
+
+
+ConstantArrayBuilder::ConstantArrayBuilder(Isolate* isolate, Zone* zone)
+    : isolate_(isolate),
+      constants_map_(isolate->heap(), zone),
+      constants_(zone),
+      allocated_low_(0),
+      reserved_low_(0),
+      reserved_high_(0) {}
+
+
+Handle<FixedArray> ConstantArrayBuilder::ToFixedArray(
+    Factory* factory, PretenureFlag pretenure) const {
+  Handle<FixedArray> fixed_array =
+      factory->NewFixedArray(static_cast<int>(constants_.size()), pretenure);
+  for (int i = 0; i < fixed_array->length(); i++) {
+    fixed_array->set(i, *constants_.at(i));
+  }
+  return fixed_array;
+}
+
+
+size_t ConstantArrayBuilder::Insert(Handle<Object> object) {
+  index_t* entry = constants_map_.Find(object);
+  return (entry == nullptr) ? AllocateEntry(object) : *entry;
+}
+
+
+void ConstantArrayBuilder::EnsureCapacity(size_t minimum_pool_size) {
+  DCHECK_GE(minimum_pool_size, allocated_low_);
+  if (constants_.size() < minimum_pool_size) {
+    constants_.insert(constants_.end(), minimum_pool_size - constants_.size(),
+                      isolate()->factory()->the_hole_value());
+  }
+}
+
+
+ConstantArrayBuilder::index_t ConstantArrayBuilder::AllocateEntry(
+    Handle<Object> object) {
+  DCHECK(!object->IsOddball());
+  DCHECK_LE(allocated_and_reserved_low(), kLowCapacity);
+  index_t* entry = constants_map_.Get(object);
+  if (allocated_and_reserved_low() < kLowCapacity) {
+    EnsureCapacity(allocated_low_ + 1);

[mythria, 2015/12/24 15:53:44]

I might have missed something, but would the following work here?
constants_.push_back(object); 
allocated_low_++; 

[oth, 2015/12/27 08:42:34]

Consider the case where a reservation has been made in the low range
and a subsequent allocation goes into the high range. The constants
array has a gap for the reserved entries and must be big enough for the
entries in the high range too. Then code discards a low reservation
and subsequently allocates. The new entry needs to be inserted into
the hole in the low entries. If it's pushed back it'll be at the end of the
high entries.

I am thinking this code might be easier to reasonable about if there were an
internal ConstantsArrayRange class that held a portion of the constants_ array
and reservations for the low and high ranges. There'd be less special casing.

+    DCHECK(constants_[allocated_low_].is_identical_to(
+        isolate()->factory()->the_hole_value()));
+    constants_[allocated_low_] = object;
+    *entry = allocated_low_++;
+  } else {
+    if (allocated_and_reserved_low() == kLowCapacity) {
+      EnsureCapacity(kLowCapacity);
+    }
+    constants_.push_back(object);
+    DCHECK_LE(constants_.size() - 1, std::numeric_limits<index_t>::max());
+    *entry = static_cast<index_t>(constants_.size() - 1);
+    DCHECK_GT(constants_.size(), kLowCapacity);
+    DCHECK_LE(constants_.size(), kMaxCapacity);
+  }
+  DCHECK_LE(allocated_and_reserved_low(), kLowCapacity);
+  DCHECK_LE(reserved_high_ + constants_.size(), kMaxCapacity);
+  DCHECK(constants_[*entry]->SameValue(*object));
+  return *entry;
+}
+
+
+ConstantArrayBuilder::ReservationToken
+ConstantArrayBuilder::CreateReservedEntry() {
+  if (allocated_and_reserved_low() < kLowCapacity) {
+    reserved_low_++;
+    return ReservationToken::kIdx8;
+  } else {
+    reserved_high_++;
+    DCHECK_LE(reserved_high_ + constants_.size(), kMaxCapacity);
+    return ReservationToken::kIdx16;
+  }
+}
+
+
+size_t ConstantArrayBuilder::CommitReservedEntry(ReservationToken token,
+                                                 Handle<Object> object) {
+  DCHECK(token == ReservationToken::kIdx16 || reserved_low_ > 0);
+  DiscardReservedEntry(token);
+  size_t index;
+  index_t* entry = constants_map_.Find(object);
+  if (nullptr == entry) {
+    index = AllocateEntry(object);
+  } else {
+    if (token == ReservationToken::kIdx8 && *entry >= kLowCapacity) {
+      // The object is already in the constant array, but has an index
+      // outside the low range so we need to create a duplicate entry
+      // in the low range to satisfy the commitment.

[mythria, 2015/12/24 15:53:44]

Do we need constants_[allocated_low_] = object; here?

[oth, 2015/12/27 08:42:34]

Yes.

+      *entry = allocated_low_++;
+      DCHECK_LE(allocated_and_reserved_low(), kLowCapacity);
+    }
+    index = *entry;
+  }
+  DCHECK(token == ReservationToken::kIdx16 || index < kLowCapacity);
+  return index;
+}
+
+
+void ConstantArrayBuilder::DiscardReservedEntry(ReservationToken token) {
+  if (token == ReservationToken::kIdx8) {
+    DCHECK_GT(reserved_low_, 0);
+    reserved_low_--;
+    if (reserved_low_ != 0 && constants_.size() == kLowCapacity) {
+      constants_.resize(allocated_low_);
+    }
+  } else {
+    DCHECK(token == ReservationToken::kIdx16);
+    DCHECK_GT(reserved_high_, 0);
+    reserved_high_--;
+  }
+}
+
+
+// static
+size_t ConstantArrayBuilder::SizeOfReservedArrayIndex(ReservationToken token) {
+  switch (token) {
+    case ReservationToken::kIdx8:
+      return 1;
+    case ReservationToken::kIdx16:
+      return 2;
+  }
+  UNREACHABLE();
+  return 0;
+}
+
+}  // namespace interpreter
+}  // namespace internal
+}  // namespace v8