[interpreter] Preparation for 32-bit operands.

src/interpreter/constant-array-builder.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/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,
-                                                             size_t start_index,
-                                                             size_t capacity)
+ConstantArrayBuilder::ConstantArraySlice::ConstantArraySlice(
+    Zone* zone, size_t start_index, size_t capacity, OperandSize operand_size)
     : start_index_(start_index),
       capacity_(capacity),
       reserved_(0),
+      operand_size_(operand_size),
       constants_(zone) {}
 
-
 void ConstantArrayBuilder::ConstantArraySlice::Reserve() {
   DCHECK_GT(available(), 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(available(), 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 {
+  DCHECK_GE(index, start_index());
+  DCHECK_LT(index, start_index() + size());
   return constants_[index - start_index()];
 }
 
-
-STATIC_CONST_MEMBER_DEFINITION const size_t ConstantArrayBuilder::kMaxCapacity;
-STATIC_CONST_MEMBER_DEFINITION const size_t ConstantArrayBuilder::kLowCapacity;
-
+STATIC_CONST_MEMBER_DEFINITION const size_t ConstantArrayBuilder::k8BitCapacity;
+STATIC_CONST_MEMBER_DEFINITION const size_t
+    ConstantArrayBuilder::k16BitCapacity;
+STATIC_CONST_MEMBER_DEFINITION const size_t
+    ConstantArrayBuilder::k32BitCapacity;
 
 ConstantArrayBuilder::ConstantArrayBuilder(Isolate* isolate, Zone* zone)
-    : isolate_(isolate),
-      idx8_slice_(zone, 0, kLowCapacity),
-      idx16_slice_(zone, kLowCapacity, kHighCapacity),
-      constants_map_(isolate->heap(), zone) {
-  STATIC_ASSERT(kMaxCapacity == static_cast<size_t>(kMaxUInt16 + 1));
-  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);
+    : isolate_(isolate), constants_map_(isolate->heap(), zone) {
+  idx_slice_[0] =
+      new (zone) ConstantArraySlice(zone, 0, k8BitCapacity, OperandSize::kByte);
+  idx_slice_[1] = new (zone) ConstantArraySlice(
+      zone, k8BitCapacity, k16BitCapacity, OperandSize::kShort);
 }
 
-
 size_t ConstantArrayBuilder::size() const {
-  if (idx16_slice_.size() > 0) {
-    return idx16_slice_.start_index() + idx16_slice_.size();
-  } else {
-    return idx8_slice_.size();
+  size_t i = arraysize(idx_slice_);
+  while (i > 0) {
+    ConstantArraySlice* slice = idx_slice_[--i];
+    if (slice->size() > 0) {
+      return slice->start_index() + slice->size();
+    }
   }
+  return idx_slice_[0]->size();
 }
 
+ConstantArrayBuilder::ConstantArraySlice* ConstantArrayBuilder::IndexToSlice(

[rmcilroy, 2016/02/25 13:26:06]

This seems a bit overkill to me. I'd prefer just to do the following in
ConstantArrayBuilder::At:

for (size_t i = 0; i < arraysize(idx_slice_); ++i) {
  if (index <= idx_slice_[i]->max_index()) {
    return idx_slice_[i]->At(index);
  }
}

WDYT?

[oth, 2016/02/25 15:40:15]

Compensated in ToFixedArray to avoid 2-3x penalty for wider constant pools.

+    size_t index) const {
+  DCHECK_LE(index, kMaxUInt32);
+  static const int kLog2Table[] = {0, 1, 2, 2};
+  int clz = base::bits::CountLeadingZeros32(static_cast<uint32_t>(index | 1));
+  int byte_index = (31 - clz) >> 3;
+  return idx_slice_[kLog2Table[byte_index]];
+}
 
 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);
+  ConstantArraySlice* slice = IndexToSlice(index);
+  if (index < slice->start_index() + slice->size()) {
+    return slice->At(index);
   } else {
     return isolate_->factory()->the_hole_value();
   }
 }
 
 Handle<FixedArray> ConstantArrayBuilder::ToFixedArray() {
   Handle<FixedArray> fixed_array = isolate_->factory()->NewFixedArray(
       static_cast<int>(size()), PretenureFlag::TENURED);
   for (int i = 0; i < fixed_array->length(); i++) {
     fixed_array->set(i, *At(static_cast<size_t>(i)));
   }
   constants_map()->Clear();
   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;

[rmcilroy, 2016/02/25 13:26:06]

nit - move this into the for loop now

[oth, 2016/02/25 15:40:15]

Done.

   index_t* entry = constants_map()->Get(object);
-  if (idx8_slice_.available() > 0) {
-    index = idx8_slice_.Allocate(object);
-  } else {
-    index = idx16_slice_.Allocate(object);
+  for (size_t i = 0; i < arraysize(idx_slice_); ++i) {
+    if (idx_slice_[i]->available() > 0) {
+      index = idx_slice_[i]->Allocate(object);
+      *entry = static_cast<index_t>(index);
+      return *entry;
+      break;
+    }
   }
-  CHECK_LT(index, kMaxCapacity);
-  *entry = static_cast<index_t>(index);
-  return *entry;
+  UNREACHABLE();
+  return kMaxUInt32;
 }
 
-
 OperandSize ConstantArrayBuilder::CreateReservedEntry() {
-  if (idx8_slice_.available() > 0) {
-    idx8_slice_.Reserve();
-    return OperandSize::kByte;
-  } else if (idx16_slice_.available() > 0) {
-    idx16_slice_.Reserve();
-    return OperandSize::kShort;
-  } else {
-    UNREACHABLE();
-    return OperandSize::kNone;
+  for (size_t i = 0; i < arraysize(idx_slice_); ++i) {
+    if (idx_slice_[i]->available() > 0) {
+      idx_slice_[i]->Reserve();
+      return idx_slice_[i]->operand_size();
+    }
   }
+  UNREACHABLE();
+  return OperandSize::kNone;
 }
 
-
 size_t ConstantArrayBuilder::CommitReservedEntry(OperandSize operand_size,
                                                  Handle<Object> object) {
   DiscardReservedEntry(operand_size);
   size_t index;
   index_t* entry = constants_map()->Find(object);
   if (nullptr == entry) {
     index = AllocateEntry(object);
   } else {
-    if (operand_size == OperandSize::kByte &&
-        *entry >= idx8_slice_.capacity()) {
-      // 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));
+    // The object is already in the constant array, but may have an

[rmcilroy, 2016/02/25 13:26:06]

Could you pull the check for entry in a larger operand size out into a seperate
if, i.e.:

if (*entry > idx_slice_[operand_size]->slice->max_index()) {
  // The object...
  for ....
}

[oth, 2016/02/25 15:40:15]

Done.

+    // index too big for the reserved operand_size. So, duplicate
+    // entry with the smaller operand size.
+    for (size_t i = arraysize(idx_slice_); i > 0; --i) {
+      ConstantArraySlice* slice = idx_slice_[i - 1];
+      if (operand_size == slice->operand_size() &&
+          *entry > slice->max_index()) {
+        *entry = static_cast<index_t>(slice->Allocate(object));
+        break;
+      }
     }
     index = *entry;
   }
-  DCHECK(operand_size == OperandSize::kShort || index < idx8_slice_.capacity());
-  DCHECK_LT(index, kMaxCapacity);
   return index;
 }
 
-
 void ConstantArrayBuilder::DiscardReservedEntry(OperandSize operand_size) {
-  switch (operand_size) {
-    case OperandSize::kByte:
-      idx8_slice_.Unreserve();
+  for (size_t i = 0; i < arraysize(idx_slice_); ++i) {
+    if (operand_size == idx_slice_[i]->operand_size()) {

[rmcilroy, 2016/02/25 13:26:06]

Could you make idx_slice_ indexable by operand_size (or have a function which
returns the index for a given operand size? Then you wouldn't need a for loop
here, and I think it would be cleaner.

[oth, 2016/02/25 15:40:15]

There is existing code already assumes the enum values of match the actual size.

+      idx_slice_[i]->Unreserve();
       return;
-    case OperandSize::kShort:
-      idx16_slice_.Unreserve();
-      return;
-    default:
-      UNREACHABLE();
+    }
   }
+  UNREACHABLE();
 }
 
 }  // namespace interpreter
 }  // namespace internal
 }  // namespace v8