constant-array-builder.cc 13.8 KB
Newer Older
1 2 3 4 5 6
// 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"

7
#include <cmath>
8
#include <functional>
9 10
#include <set>

11 12 13 14
#include "src/ast/ast-value-factory.h"
#include "src/ast/ast.h"
#include "src/ast/scopes.h"
#include "src/base/functional.h"
15
#include "src/execution/isolate.h"
16
#include "src/heap/local-factory-inl.h"
17
#include "src/objects/objects-inl.h"
18 19 20 21 22

namespace v8 {
namespace internal {
namespace interpreter {

23 24
ConstantArrayBuilder::ConstantArraySlice::ConstantArraySlice(
    Zone* zone, size_t start_index, size_t capacity, OperandSize operand_size)
25 26 27
    : start_index_(start_index),
      capacity_(capacity),
      reserved_(0),
28
      operand_size_(operand_size),
29 30 31 32 33 34 35 36 37 38 39 40 41 42
      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(
43 44
    ConstantArrayBuilder::Entry entry, size_t count) {
  DCHECK_GE(available(), count);
45 46
  size_t index = constants_.size();
  DCHECK_LT(index, capacity());
47 48 49
  for (size_t i = 0; i < count; ++i) {
    constants_.push_back(entry);
  }
50 51 52
  return index + start_index();
}

53 54
ConstantArrayBuilder::Entry& ConstantArrayBuilder::ConstantArraySlice::At(
    size_t index) {
55 56
  DCHECK_GE(index, start_index());
  DCHECK_LT(index, start_index() + size());
57 58 59
  return constants_[index - start_index()];
}

60 61
const ConstantArrayBuilder::Entry& ConstantArrayBuilder::ConstantArraySlice::At(
    size_t index) const {
62 63
  DCHECK_GE(index, start_index());
  DCHECK_LT(index, start_index() + size());
64
  return constants_[index - start_index()];
65 66
}

67
#if DEBUG
68
template <typename LocalIsolate>
69
void ConstantArrayBuilder::ConstantArraySlice::CheckAllElementsAreUnique(
70
    LocalIsolate* isolate) const {
71
  std::set<Smi> smis;
72 73 74 75
  std::set<double> heap_numbers;
  std::set<const AstRawString*> strings;
  std::set<const char*> bigints;
  std::set<const Scope*> scopes;
76
  std::set<Object, Object::Comparer> deferred_objects;
77
  for (const Entry& entry : constants_) {
78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95
    bool duplicate = false;
    switch (entry.tag_) {
      case Entry::Tag::kSmi:
        duplicate = !smis.insert(entry.smi_).second;
        break;
      case Entry::Tag::kHeapNumber:
        duplicate = !heap_numbers.insert(entry.heap_number_).second;
        break;
      case Entry::Tag::kRawString:
        duplicate = !strings.insert(entry.raw_string_).second;
        break;
      case Entry::Tag::kBigInt:
        duplicate = !bigints.insert(entry.bigint_.c_str()).second;
        break;
      case Entry::Tag::kScope:
        duplicate = !scopes.insert(entry.scope_).second;
        break;
      case Entry::Tag::kHandle:
96
        duplicate = !deferred_objects.insert(*entry.handle_).second;
97 98 99 100 101 102 103 104 105 106 107 108 109 110 111
        break;
      case Entry::Tag::kDeferred:
        UNREACHABLE();  // Should be kHandle at this point.
      case Entry::Tag::kJumpTableSmi:
      case Entry::Tag::kUninitializedJumpTableSmi:
        // TODO(leszeks): Ignore jump tables because they have to be contiguous,
        // so they can contain duplicates.
        break;
#define CASE_TAG(NAME, ...) case Entry::Tag::k##NAME:
        SINGLETON_CONSTANT_ENTRY_TYPES(CASE_TAG)
#undef CASE_TAG
        // Singletons are non-duplicated by definition.
        break;
    }
    if (duplicate) {
112
      std::ostringstream os;
113 114
      os << "Duplicate constant found: " << Brief(*entry.ToHandle(isolate))
         << std::endl;
115 116 117 118 119
      // Print all the entries in the slice to help debug duplicates.
      size_t i = start_index();
      for (const Entry& prev_entry : constants_) {
        os << i++ << ": " << Brief(*prev_entry.ToHandle(isolate)) << std::endl;
      }
120
      FATAL("%s", os.str().c_str());
121
    }
122 123
  }
}
124
#endif
125

126 127 128 129 130
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;
131

132 133
ConstantArrayBuilder::ConstantArrayBuilder(Zone* zone)
    : constants_map_(16, base::KeyEqualityMatcher<intptr_t>(),
134
                     ZoneAllocationPolicy(zone)),
135
      smi_map_(zone),
136
      smi_pairs_(zone),
137
      heap_number_map_(zone) {
138
  idx_slice_[0] =
139 140
      zone->New<ConstantArraySlice>(zone, 0, k8BitCapacity, OperandSize::kByte);
  idx_slice_[1] = zone->New<ConstantArraySlice>(
141
      zone, k8BitCapacity, k16BitCapacity, OperandSize::kShort);
142
  idx_slice_[2] = zone->New<ConstantArraySlice>(
143
      zone, k8BitCapacity + k16BitCapacity, k32BitCapacity, OperandSize::kQuad);
144 145 146
}

size_t ConstantArrayBuilder::size() const {
147 148 149 150 151 152
  size_t i = arraysize(idx_slice_);
  while (i > 0) {
    ConstantArraySlice* slice = idx_slice_[--i];
    if (slice->size() > 0) {
      return slice->start_index() + slice->size();
    }
153
  }
154
  return idx_slice_[0]->size();
155 156
}

157 158 159
ConstantArrayBuilder::ConstantArraySlice* ConstantArrayBuilder::IndexToSlice(
    size_t index) const {
  for (ConstantArraySlice* slice : idx_slice_) {
160 161 162 163 164 165
    if (index <= slice->max_index()) {
      return slice;
    }
  }
  UNREACHABLE();
}
166

167 168 169
template <typename LocalIsolate>
MaybeHandle<Object> ConstantArrayBuilder::At(size_t index,
                                             LocalIsolate* isolate) const {
170
  const ConstantArraySlice* slice = IndexToSlice(index);
171
  DCHECK_LT(index, slice->capacity());
172
  if (index < slice->start_index() + slice->size()) {
173 174
    const Entry& entry = slice->At(index);
    if (!entry.IsDeferred()) return entry.ToHandle(isolate);
175
  }
176
  return MaybeHandle<Object>();
177 178
}

179 180 181 182
template EXPORT_TEMPLATE_DEFINE(V8_EXPORT_PRIVATE)
    MaybeHandle<Object> ConstantArrayBuilder::At(size_t index,
                                                 Isolate* isolate) const;
template EXPORT_TEMPLATE_DEFINE(V8_EXPORT_PRIVATE)
183 184
    MaybeHandle<Object> ConstantArrayBuilder::At(size_t index,
                                                 LocalIsolate* isolate) const;
185

186 187 188 189
template <typename LocalIsolate>
Handle<FixedArray> ConstantArrayBuilder::ToFixedArray(LocalIsolate* isolate) {
  Handle<FixedArray> fixed_array = isolate->factory()->NewFixedArrayWithHoles(
      static_cast<int>(size()), AllocationType::kOld);
190 191
  int array_index = 0;
  for (const ConstantArraySlice* slice : idx_slice_) {
192
    DCHECK_EQ(slice->reserved(), 0);
193
    DCHECK(array_index == 0 ||
194
           base::bits::IsPowerOfTwo(static_cast<uint32_t>(array_index)));
195
#if DEBUG
196
    // Different slices might contain the same element due to reservations, but
197
    // all elements within a slice should be unique.
198
    slice->CheckAllElementsAreUnique(isolate);
199
#endif
200 201
    // Copy objects from slice into array.
    for (size_t i = 0; i < slice->size(); ++i) {
202
      Handle<Object> value =
203 204
          slice->At(slice->start_index() + i).ToHandle(isolate);
      fixed_array->set(array_index++, *value);
205
    }
206 207 208 209
    // Leave holes where reservations led to unused slots.
    size_t padding = slice->capacity() - slice->size();
    if (static_cast<size_t>(fixed_array->length() - array_index) <= padding) {
      break;
210
    }
211
    array_index += padding;
212
  }
213
  DCHECK_GE(array_index, fixed_array->length());
214 215 216
  return fixed_array;
}

217 218 219
template EXPORT_TEMPLATE_DEFINE(V8_EXPORT_PRIVATE)
    Handle<FixedArray> ConstantArrayBuilder::ToFixedArray(Isolate* isolate);
template EXPORT_TEMPLATE_DEFINE(V8_EXPORT_PRIVATE)
220
    Handle<FixedArray> ConstantArrayBuilder::ToFixedArray(
221
        LocalIsolate* isolate);
222

223
size_t ConstantArrayBuilder::Insert(Smi smi) {
224 225 226 227 228 229 230
  auto entry = smi_map_.find(smi);
  if (entry == smi_map_.end()) {
    return AllocateReservedEntry(smi);
  }
  return entry->second;
}

231 232 233 234 235 236 237 238 239 240 241
size_t ConstantArrayBuilder::Insert(double number) {
  if (std::isnan(number)) return InsertNaN();
  auto entry = heap_number_map_.find(number);
  if (entry == heap_number_map_.end()) {
    index_t index = static_cast<index_t>(AllocateIndex(Entry(number)));
    heap_number_map_[number] = index;
    return index;
  }
  return entry->second;
}

242
size_t ConstantArrayBuilder::Insert(const AstRawString* raw_string) {
243
  return constants_map_
244
      .LookupOrInsert(reinterpret_cast<intptr_t>(raw_string),
245
                      raw_string->Hash(),
246
                      [&]() { return AllocateIndex(Entry(raw_string)); })
247
      ->value;
248 249
}

250
size_t ConstantArrayBuilder::Insert(AstBigInt bigint) {
251
  return constants_map_
252 253
      .LookupOrInsert(reinterpret_cast<intptr_t>(bigint.c_str()),
                      static_cast<uint32_t>(base::hash_value(bigint.c_str())),
254
                      [&]() { return AllocateIndex(Entry(bigint)); })
255 256 257 258 259 260 261
      ->value;
}

size_t ConstantArrayBuilder::Insert(const Scope* scope) {
  return constants_map_
      .LookupOrInsert(reinterpret_cast<intptr_t>(scope),
                      static_cast<uint32_t>(base::hash_value(scope)),
262
                      [&]() { return AllocateIndex(Entry(scope)); })
263 264 265 266 267 268 269 270 271 272 273 274 275
      ->value;
}

#define INSERT_ENTRY(NAME, LOWER_NAME)              \
  size_t ConstantArrayBuilder::Insert##NAME() {     \
    if (LOWER_NAME##_ < 0) {                        \
      LOWER_NAME##_ = AllocateIndex(Entry::NAME()); \
    }                                               \
    return LOWER_NAME##_;                           \
  }
SINGLETON_CONSTANT_ENTRY_TYPES(INSERT_ENTRY)
#undef INSERT_ENTRY

276
ConstantArrayBuilder::index_t ConstantArrayBuilder::AllocateIndex(
277
    ConstantArrayBuilder::Entry entry) {
278 279 280 281 282
  return AllocateIndexArray(entry, 1);
}

ConstantArrayBuilder::index_t ConstantArrayBuilder::AllocateIndexArray(
    ConstantArrayBuilder::Entry entry, size_t count) {
283
  for (size_t i = 0; i < arraysize(idx_slice_); ++i) {
284 285
    if (idx_slice_[i]->available() >= count) {
      return static_cast<index_t>(idx_slice_[i]->Allocate(entry, count));
286
    }
287
  }
288
  UNREACHABLE();
289 290
}

291 292 293 294 295 296 297 298 299 300 301 302
ConstantArrayBuilder::ConstantArraySlice*
ConstantArrayBuilder::OperandSizeToSlice(OperandSize operand_size) const {
  ConstantArraySlice* slice = nullptr;
  switch (operand_size) {
    case OperandSize::kNone:
      UNREACHABLE();
    case OperandSize::kByte:
      slice = idx_slice_[0];
      break;
    case OperandSize::kShort:
      slice = idx_slice_[1];
      break;
303 304 305
    case OperandSize::kQuad:
      slice = idx_slice_[2];
      break;
306 307 308 309
  }
  DCHECK(slice->operand_size() == operand_size);
  return slice;
}
310

311 312
size_t ConstantArrayBuilder::InsertDeferred() {
  return AllocateIndex(Entry::Deferred());
313 314
}

315 316 317 318
size_t ConstantArrayBuilder::InsertJumpTable(size_t size) {
  return AllocateIndexArray(Entry::UninitializedJumpTableSmi(), size);
}

319
void ConstantArrayBuilder::SetDeferredAt(size_t index, Handle<Object> object) {
320
  ConstantArraySlice* slice = IndexToSlice(index);
321
  return slice->At(index).SetDeferred(object);
322 323
}

324
void ConstantArrayBuilder::SetJumpTableSmi(size_t index, Smi smi) {
325 326 327 328 329 330 331 332
  ConstantArraySlice* slice = IndexToSlice(index);
  // Allow others to reuse these Smis, but insert using emplace to avoid
  // overwriting existing values in the Smi map (which may have a smaller
  // operand size).
  smi_map_.emplace(smi, static_cast<index_t>(index));
  return slice->At(index).SetJumpTableSmi(smi);
}

333 334 335 336 337 338 339 340 341 342
OperandSize ConstantArrayBuilder::CreateReservedEntry() {
  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();
}

343
ConstantArrayBuilder::index_t ConstantArrayBuilder::AllocateReservedEntry(
344
    Smi value) {
345
  index_t index = static_cast<index_t>(AllocateIndex(Entry(value)));
346 347 348 349
  smi_map_[value] = index;
  return index;
}

350
size_t ConstantArrayBuilder::CommitReservedEntry(OperandSize operand_size,
351
                                                 Smi value) {
352 353
  DiscardReservedEntry(operand_size);
  size_t index;
354 355 356
  auto entry = smi_map_.find(value);
  if (entry == smi_map_.end()) {
    index = AllocateReservedEntry(value);
357
  } else {
358
    ConstantArraySlice* slice = OperandSizeToSlice(operand_size);
359 360
    index = entry->second;
    if (index > slice->max_index()) {
361 362 363
      // The object is already in the constant array, but may have an
      // index too big for the reserved operand_size. So, duplicate
      // entry with the smaller operand size.
364
      index = AllocateReservedEntry(value);
365
    }
366
    DCHECK_LE(index, slice->max_index());
367 368 369 370 371
  }
  return index;
}

void ConstantArrayBuilder::DiscardReservedEntry(OperandSize operand_size) {
372
  OperandSizeToSlice(operand_size)->Unreserve();
373 374
}

375 376 377
template <typename LocalIsolate>
Handle<Object> ConstantArrayBuilder::Entry::ToHandle(
    LocalIsolate* isolate) const {
378 379 380 381 382 383 384
  switch (tag_) {
    case Tag::kDeferred:
      // We shouldn't have any deferred entries by now.
      UNREACHABLE();
    case Tag::kHandle:
      return handle_;
    case Tag::kSmi:
385
    case Tag::kJumpTableSmi:
386
      return handle(smi_, isolate);
387 388 389
    case Tag::kUninitializedJumpTableSmi:
      // TODO(leszeks): There's probably a better value we could use here.
      return isolate->factory()->the_hole_value();
390
    case Tag::kRawString:
391
      return raw_string_->string();
392
    case Tag::kHeapNumber:
393 394
      return isolate->factory()->template NewNumber<AllocationType::kOld>(
          heap_number_);
395
    case Tag::kBigInt:
396 397
      // This should never fail: the parser will never create a BigInt
      // literal that cannot be allocated.
398
      return BigIntLiteral(isolate, bigint_.c_str()).ToHandleChecked();
399 400
    case Tag::kScope:
      return scope_->scope_info();
401 402 403 404 405
#define ENTRY_LOOKUP(Name, name) \
  case Tag::k##Name:             \
    return isolate->factory()->name();
      SINGLETON_CONSTANT_ENTRY_TYPES(ENTRY_LOOKUP);
#undef ENTRY_LOOKUP
406 407 408 409
  }
  UNREACHABLE();
}

410 411
template Handle<Object> ConstantArrayBuilder::Entry::ToHandle(
    Isolate* isolate) const;
412
template Handle<Object> ConstantArrayBuilder::Entry::ToHandle(
413
    LocalIsolate* isolate) const;
414

415 416 417
}  // namespace interpreter
}  // namespace internal
}  // namespace v8