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 <functional>
8#include <set>
9
10#include "src/isolate.h"
11#include "src/objects-inl.h"
12
13namespace v8 {
14namespace internal {
15namespace interpreter {
16
17ConstantArrayBuilder::ConstantArraySlice::ConstantArraySlice(
18    Zone* zone, size_t start_index, size_t capacity, OperandSize operand_size)
19    : start_index_(start_index),
20      capacity_(capacity),
21      reserved_(0),
22      operand_size_(operand_size),
23      constants_(zone) {}
24
25void ConstantArrayBuilder::ConstantArraySlice::Reserve() {
26  DCHECK_GT(available(), 0u);
27  reserved_++;
28  DCHECK_LE(reserved_, capacity() - constants_.size());
29}
30
31void ConstantArrayBuilder::ConstantArraySlice::Unreserve() {
32  DCHECK_GT(reserved_, 0u);
33  reserved_--;
34}
35
36size_t ConstantArrayBuilder::ConstantArraySlice::Allocate(
37    Handle<Object> object) {
38  DCHECK_GT(available(), 0u);
39  size_t index = constants_.size();
40  DCHECK_LT(index, capacity());
41  constants_.push_back(object);
42  return index + start_index();
43}
44
45Handle<Object> ConstantArrayBuilder::ConstantArraySlice::At(
46    size_t index) const {
47  DCHECK_GE(index, start_index());
48  DCHECK_LT(index, start_index() + size());
49  return constants_[index - start_index()];
50}
51
52void ConstantArrayBuilder::ConstantArraySlice::InsertAt(size_t index,
53                                                        Handle<Object> object) {
54  DCHECK_GE(index, start_index());
55  DCHECK_LT(index, start_index() + size());
56  constants_[index - start_index()] = object;
57}
58
59bool ConstantArrayBuilder::ConstantArraySlice::AllElementsAreUnique() const {
60  std::set<Object*> elements;
61  for (auto constant : constants_) {
62    if (elements.find(*constant) != elements.end()) return false;
63    elements.insert(*constant);
64  }
65  return true;
66}
67
68STATIC_CONST_MEMBER_DEFINITION const size_t ConstantArrayBuilder::k8BitCapacity;
69STATIC_CONST_MEMBER_DEFINITION const size_t
70    ConstantArrayBuilder::k16BitCapacity;
71STATIC_CONST_MEMBER_DEFINITION const size_t
72    ConstantArrayBuilder::k32BitCapacity;
73
74ConstantArrayBuilder::ConstantArrayBuilder(Zone* zone,
75                                           Handle<Object> the_hole_value)
76    : constants_map_(16, base::KeyEqualityMatcher<Address>(),
77                     ZoneAllocationPolicy(zone)),
78      smi_map_(zone),
79      smi_pairs_(zone),
80      zone_(zone),
81      the_hole_value_(the_hole_value) {
82  idx_slice_[0] =
83      new (zone) ConstantArraySlice(zone, 0, k8BitCapacity, OperandSize::kByte);
84  idx_slice_[1] = new (zone) ConstantArraySlice(
85      zone, k8BitCapacity, k16BitCapacity, OperandSize::kShort);
86  idx_slice_[2] = new (zone) ConstantArraySlice(
87      zone, k8BitCapacity + k16BitCapacity, k32BitCapacity, OperandSize::kQuad);
88}
89
90size_t ConstantArrayBuilder::size() const {
91  size_t i = arraysize(idx_slice_);
92  while (i > 0) {
93    ConstantArraySlice* slice = idx_slice_[--i];
94    if (slice->size() > 0) {
95      return slice->start_index() + slice->size();
96    }
97  }
98  return idx_slice_[0]->size();
99}
100
101ConstantArrayBuilder::ConstantArraySlice* ConstantArrayBuilder::IndexToSlice(
102    size_t index) const {
103  for (ConstantArraySlice* slice : idx_slice_) {
104    if (index <= slice->max_index()) {
105      return slice;
106    }
107  }
108  UNREACHABLE();
109  return nullptr;
110}
111
112Handle<Object> ConstantArrayBuilder::At(size_t index) const {
113  const ConstantArraySlice* slice = IndexToSlice(index);
114  if (index < slice->start_index() + slice->size()) {
115    return slice->At(index);
116  } else {
117    DCHECK_LT(index, slice->capacity());
118    return the_hole_value();
119  }
120}
121
122Handle<FixedArray> ConstantArrayBuilder::ToFixedArray(Isolate* isolate) {
123  // First insert reserved SMI values.
124  for (auto reserved_smi : smi_pairs_) {
125    InsertAllocatedEntry(reserved_smi.second,
126                         handle(reserved_smi.first, isolate));
127  }
128
129  Handle<FixedArray> fixed_array = isolate->factory()->NewFixedArray(
130      static_cast<int>(size()), PretenureFlag::TENURED);
131  int array_index = 0;
132  for (const ConstantArraySlice* slice : idx_slice_) {
133    if (array_index == fixed_array->length()) {
134      break;
135    }
136    DCHECK(array_index == 0 ||
137           base::bits::IsPowerOfTwo32(static_cast<uint32_t>(array_index)));
138    // Different slices might contain the same element due to reservations, but
139    // all elements within a slice should be unique. If this DCHECK fails, then
140    // the AST nodes are not being internalized within a CanonicalHandleScope.
141    DCHECK(slice->AllElementsAreUnique());
142    // Copy objects from slice into array.
143    for (size_t i = 0; i < slice->size(); ++i) {
144      fixed_array->set(array_index++, *slice->At(slice->start_index() + i));
145    }
146    // Insert holes where reservations led to unused slots.
147    size_t padding =
148        std::min(static_cast<size_t>(fixed_array->length() - array_index),
149                 slice->capacity() - slice->size());
150    for (size_t i = 0; i < padding; i++) {
151      fixed_array->set(array_index++, *the_hole_value());
152    }
153  }
154  DCHECK_EQ(array_index, fixed_array->length());
155  return fixed_array;
156}
157
158size_t ConstantArrayBuilder::Insert(Handle<Object> object) {
159  return constants_map_
160      .LookupOrInsert(object.address(), ObjectHash(object.address()),
161                      [&]() { return AllocateIndex(object); },
162                      ZoneAllocationPolicy(zone_))
163      ->value;
164}
165
166ConstantArrayBuilder::index_t ConstantArrayBuilder::AllocateIndex(
167    Handle<Object> object) {
168  for (size_t i = 0; i < arraysize(idx_slice_); ++i) {
169    if (idx_slice_[i]->available() > 0) {
170      return static_cast<index_t>(idx_slice_[i]->Allocate(object));
171    }
172  }
173  UNREACHABLE();
174  return kMaxUInt32;
175}
176
177ConstantArrayBuilder::ConstantArraySlice*
178ConstantArrayBuilder::OperandSizeToSlice(OperandSize operand_size) const {
179  ConstantArraySlice* slice = nullptr;
180  switch (operand_size) {
181    case OperandSize::kNone:
182      UNREACHABLE();
183      break;
184    case OperandSize::kByte:
185      slice = idx_slice_[0];
186      break;
187    case OperandSize::kShort:
188      slice = idx_slice_[1];
189      break;
190    case OperandSize::kQuad:
191      slice = idx_slice_[2];
192      break;
193  }
194  DCHECK(slice->operand_size() == operand_size);
195  return slice;
196}
197
198size_t ConstantArrayBuilder::AllocateEntry() {
199  return AllocateIndex(the_hole_value());
200}
201
202void ConstantArrayBuilder::InsertAllocatedEntry(size_t index,
203                                                Handle<Object> object) {
204  DCHECK_EQ(the_hole_value().address(), At(index).address());
205  ConstantArraySlice* slice = IndexToSlice(index);
206  slice->InsertAt(index, object);
207}
208
209OperandSize ConstantArrayBuilder::CreateReservedEntry() {
210  for (size_t i = 0; i < arraysize(idx_slice_); ++i) {
211    if (idx_slice_[i]->available() > 0) {
212      idx_slice_[i]->Reserve();
213      return idx_slice_[i]->operand_size();
214    }
215  }
216  UNREACHABLE();
217  return OperandSize::kNone;
218}
219
220ConstantArrayBuilder::index_t ConstantArrayBuilder::AllocateReservedEntry(
221    Smi* value) {
222  index_t index = static_cast<index_t>(AllocateEntry());
223  smi_map_[value] = index;
224  smi_pairs_.push_back(std::make_pair(value, index));
225  return index;
226}
227
228size_t ConstantArrayBuilder::CommitReservedEntry(OperandSize operand_size,
229                                                 Smi* value) {
230  DiscardReservedEntry(operand_size);
231  size_t index;
232  auto entry = smi_map_.find(value);
233  if (entry == smi_map_.end()) {
234    index = AllocateReservedEntry(value);
235  } else {
236    ConstantArraySlice* slice = OperandSizeToSlice(operand_size);
237    index = entry->second;
238    if (index > slice->max_index()) {
239      // The object is already in the constant array, but may have an
240      // index too big for the reserved operand_size. So, duplicate
241      // entry with the smaller operand size.
242      index = AllocateReservedEntry(value);
243    }
244    DCHECK_LE(index, slice->max_index());
245  }
246  return index;
247}
248
249void ConstantArrayBuilder::DiscardReservedEntry(OperandSize operand_size) {
250  OperandSizeToSlice(operand_size)->Unreserve();
251}
252
253}  // namespace interpreter
254}  // namespace internal
255}  // namespace v8
256