1// Copyright 2015 the V8 project authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#include "src/interpreter/constant-array-builder.h"
6
7#include "src/isolate.h"
8#include "src/objects-inl.h"
9
10namespace v8 {
11namespace internal {
12namespace interpreter {
13
14ConstantArrayBuilder::ConstantArraySlice::ConstantArraySlice(
15    Zone* zone, size_t start_index, size_t capacity, OperandSize operand_size)
16    : start_index_(start_index),
17      capacity_(capacity),
18      reserved_(0),
19      operand_size_(operand_size),
20      constants_(zone) {}
21
22void ConstantArrayBuilder::ConstantArraySlice::Reserve() {
23  DCHECK_GT(available(), 0u);
24  reserved_++;
25  DCHECK_LE(reserved_, capacity() - constants_.size());
26}
27
28void ConstantArrayBuilder::ConstantArraySlice::Unreserve() {
29  DCHECK_GT(reserved_, 0u);
30  reserved_--;
31}
32
33size_t ConstantArrayBuilder::ConstantArraySlice::Allocate(
34    Handle<Object> object) {
35  DCHECK_GT(available(), 0u);
36  size_t index = constants_.size();
37  DCHECK_LT(index, capacity());
38  constants_.push_back(object);
39  return index + start_index();
40}
41
42Handle<Object> ConstantArrayBuilder::ConstantArraySlice::At(
43    size_t index) const {
44  DCHECK_GE(index, start_index());
45  DCHECK_LT(index, start_index() + size());
46  return constants_[index - start_index()];
47}
48
49STATIC_CONST_MEMBER_DEFINITION const size_t ConstantArrayBuilder::k8BitCapacity;
50STATIC_CONST_MEMBER_DEFINITION const size_t
51    ConstantArrayBuilder::k16BitCapacity;
52STATIC_CONST_MEMBER_DEFINITION const size_t
53    ConstantArrayBuilder::k32BitCapacity;
54
55ConstantArrayBuilder::ConstantArrayBuilder(Isolate* isolate, Zone* zone)
56    : isolate_(isolate), constants_map_(isolate->heap(), zone) {
57  idx_slice_[0] =
58      new (zone) ConstantArraySlice(zone, 0, k8BitCapacity, OperandSize::kByte);
59  idx_slice_[1] = new (zone) ConstantArraySlice(
60      zone, k8BitCapacity, k16BitCapacity, OperandSize::kShort);
61  idx_slice_[2] = new (zone) ConstantArraySlice(
62      zone, k8BitCapacity + k16BitCapacity, k32BitCapacity, OperandSize::kQuad);
63}
64
65size_t ConstantArrayBuilder::size() const {
66  size_t i = arraysize(idx_slice_);
67  while (i > 0) {
68    ConstantArraySlice* slice = idx_slice_[--i];
69    if (slice->size() > 0) {
70      return slice->start_index() + slice->size();
71    }
72  }
73  return idx_slice_[0]->size();
74}
75
76const ConstantArrayBuilder::ConstantArraySlice*
77ConstantArrayBuilder::IndexToSlice(size_t index) const {
78  for (const ConstantArraySlice* slice : idx_slice_) {
79    if (index <= slice->max_index()) {
80      return slice;
81    }
82  }
83  UNREACHABLE();
84  return nullptr;
85}
86
87Handle<Object> ConstantArrayBuilder::At(size_t index) const {
88  const ConstantArraySlice* slice = IndexToSlice(index);
89  if (index < slice->start_index() + slice->size()) {
90    return slice->At(index);
91  } else {
92    DCHECK_LT(index, slice->capacity());
93    return isolate_->factory()->the_hole_value();
94  }
95}
96
97Handle<FixedArray> ConstantArrayBuilder::ToFixedArray() {
98  Handle<FixedArray> fixed_array = isolate_->factory()->NewFixedArray(
99      static_cast<int>(size()), PretenureFlag::TENURED);
100  int array_index = 0;
101  for (const ConstantArraySlice* slice : idx_slice_) {
102    if (array_index == fixed_array->length()) {
103      break;
104    }
105    DCHECK(array_index == 0 ||
106           base::bits::IsPowerOfTwo32(static_cast<uint32_t>(array_index)));
107    // Copy objects from slice into array.
108    for (size_t i = 0; i < slice->size(); ++i) {
109      fixed_array->set(array_index++, *slice->At(slice->start_index() + i));
110    }
111    // Insert holes where reservations led to unused slots.
112    size_t padding =
113        std::min(static_cast<size_t>(fixed_array->length() - array_index),
114                 slice->capacity() - slice->size());
115    for (size_t i = 0; i < padding; i++) {
116      fixed_array->set(array_index++, *isolate_->factory()->the_hole_value());
117    }
118  }
119  DCHECK_EQ(array_index, fixed_array->length());
120  constants_map()->Clear();
121  return fixed_array;
122}
123
124size_t ConstantArrayBuilder::Insert(Handle<Object> object) {
125  index_t* entry = constants_map()->Find(object);
126  return (entry == nullptr) ? AllocateEntry(object) : *entry;
127}
128
129ConstantArrayBuilder::index_t ConstantArrayBuilder::AllocateEntry(
130    Handle<Object> object) {
131  DCHECK(!object->IsOddball());
132  index_t* entry = constants_map()->Get(object);
133  for (size_t i = 0; i < arraysize(idx_slice_); ++i) {
134    if (idx_slice_[i]->available() > 0) {
135      size_t index = idx_slice_[i]->Allocate(object);
136      *entry = static_cast<index_t>(index);
137      return *entry;
138      break;
139    }
140  }
141  UNREACHABLE();
142  return kMaxUInt32;
143}
144
145OperandSize ConstantArrayBuilder::CreateReservedEntry() {
146  for (size_t i = 0; i < arraysize(idx_slice_); ++i) {
147    if (idx_slice_[i]->available() > 0) {
148      idx_slice_[i]->Reserve();
149      return idx_slice_[i]->operand_size();
150    }
151  }
152  UNREACHABLE();
153  return OperandSize::kNone;
154}
155
156ConstantArrayBuilder::ConstantArraySlice*
157ConstantArrayBuilder::OperandSizeToSlice(OperandSize operand_size) const {
158  ConstantArraySlice* slice = nullptr;
159  switch (operand_size) {
160    case OperandSize::kNone:
161      UNREACHABLE();
162      break;
163    case OperandSize::kByte:
164      slice = idx_slice_[0];
165      break;
166    case OperandSize::kShort:
167      slice = idx_slice_[1];
168      break;
169    case OperandSize::kQuad:
170      slice = idx_slice_[2];
171      break;
172  }
173  DCHECK(slice->operand_size() == operand_size);
174  return slice;
175}
176
177size_t ConstantArrayBuilder::CommitReservedEntry(OperandSize operand_size,
178                                                 Handle<Object> object) {
179  DiscardReservedEntry(operand_size);
180  size_t index;
181  index_t* entry = constants_map()->Find(object);
182  if (nullptr == entry) {
183    index = AllocateEntry(object);
184  } else {
185    ConstantArraySlice* slice = OperandSizeToSlice(operand_size);
186    if (*entry > slice->max_index()) {
187      // The object is already in the constant array, but may have an
188      // index too big for the reserved operand_size. So, duplicate
189      // entry with the smaller operand size.
190      *entry = static_cast<index_t>(slice->Allocate(object));
191    }
192    index = *entry;
193  }
194  return index;
195}
196
197void ConstantArrayBuilder::DiscardReservedEntry(OperandSize operand_size) {
198  OperandSizeToSlice(operand_size)->Unreserve();
199}
200
201}  // namespace interpreter
202}  // namespace internal
203}  // namespace v8
204