Home | History | Annotate | Download | only in interpreter 
      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/ast/ast-value-factory.h"
     11 #include "src/ast/ast.h"
     12 #include "src/ast/scopes.h"
     13 #include "src/base/functional.h"
     14 #include "src/isolate.h"
     15 #include "src/objects-inl.h"
     16 
     17 namespace v8 {
     18 namespace internal {
     19 namespace interpreter {
     20 
     21 ConstantArrayBuilder::ConstantArraySlice::ConstantArraySlice(
     22     Zone* zone, size_t start_index, size_t capacity, OperandSize operand_size)
     23     : start_index_(start_index),
     24       capacity_(capacity),
     25       reserved_(0),
     26       operand_size_(operand_size),
     27       constants_(zone) {}
     28 
     29 void ConstantArrayBuilder::ConstantArraySlice::Reserve() {
     30   DCHECK_GT(available(), 0u);
     31   reserved_++;
     32   DCHECK_LE(reserved_, capacity() - constants_.size());
     33 }
     34 
     35 void ConstantArrayBuilder::ConstantArraySlice::Unreserve() {
     36   DCHECK_GT(reserved_, 0u);
     37   reserved_--;
     38 }
     39 
     40 size_t ConstantArrayBuilder::ConstantArraySlice::Allocate(
     41     ConstantArrayBuilder::Entry entry) {
     42   DCHECK_GT(available(), 0u);
     43   size_t index = constants_.size();
     44   DCHECK_LT(index, capacity());
     45   constants_.push_back(entry);
     46   return index + start_index();
     47 }
     48 
     49 ConstantArrayBuilder::Entry& ConstantArrayBuilder::ConstantArraySlice::At(
     50     size_t index) {
     51   DCHECK_GE(index, start_index());
     52   DCHECK_LT(index, start_index() + size());
     53   return constants_[index - start_index()];
     54 }
     55 
     56 const ConstantArrayBuilder::Entry& ConstantArrayBuilder::ConstantArraySlice::At(
     57     size_t index) const {
     58   DCHECK_GE(index, start_index());
     59   DCHECK_LT(index, start_index() + size());
     60   return constants_[index - start_index()];
     61 }
     62 
     63 #if DEBUG
     64 void ConstantArrayBuilder::ConstantArraySlice::CheckAllElementsAreUnique(
     65     Isolate* isolate) const {
     66   std::set<Object*> elements;
     67   for (const Entry& entry : constants_) {
     68     Handle<Object> handle = entry.ToHandle(isolate);
     69     if (elements.find(*handle) != elements.end()) {
     70       std::ostringstream os;
     71       os << "Duplicate constant found: " << Brief(*handle) << std::endl;
     72       // Print all the entries in the slice to help debug duplicates.
     73       size_t i = start_index();
     74       for (const Entry& prev_entry : constants_) {
     75         os << i++ << ": " << Brief(*prev_entry.ToHandle(isolate)) << std::endl;
     76       }
     77       FATAL(os.str().c_str());
     78     }
     79     elements.insert(*handle);
     80   }
     81 }
     82 #endif
     83 
     84 STATIC_CONST_MEMBER_DEFINITION const size_t ConstantArrayBuilder::k8BitCapacity;
     85 STATIC_CONST_MEMBER_DEFINITION const size_t
     86     ConstantArrayBuilder::k16BitCapacity;
     87 STATIC_CONST_MEMBER_DEFINITION const size_t
     88     ConstantArrayBuilder::k32BitCapacity;
     89 
     90 ConstantArrayBuilder::ConstantArrayBuilder(Zone* zone)
     91     : constants_map_(16, base::KeyEqualityMatcher<intptr_t>(),
     92                      ZoneAllocationPolicy(zone)),
     93       smi_map_(zone),
     94       smi_pairs_(zone),
     95 #define INIT_SINGLETON_ENTRY_FIELD(NAME, LOWER_NAME) LOWER_NAME##_(-1),
     96       SINGLETON_CONSTANT_ENTRY_TYPES(INIT_SINGLETON_ENTRY_FIELD)
     97 #undef INIT_SINGLETON_ENTRY_FIELD
     98           zone_(zone) {
     99   idx_slice_[0] =
    100       new (zone) ConstantArraySlice(zone, 0, k8BitCapacity, OperandSize::kByte);
    101   idx_slice_[1] = new (zone) ConstantArraySlice(
    102       zone, k8BitCapacity, k16BitCapacity, OperandSize::kShort);
    103   idx_slice_[2] = new (zone) ConstantArraySlice(
    104       zone, k8BitCapacity + k16BitCapacity, k32BitCapacity, OperandSize::kQuad);
    105 }
    106 
    107 size_t ConstantArrayBuilder::size() const {
    108   size_t i = arraysize(idx_slice_);
    109   while (i > 0) {
    110     ConstantArraySlice* slice = idx_slice_[--i];
    111     if (slice->size() > 0) {
    112       return slice->start_index() + slice->size();
    113     }
    114   }
    115   return idx_slice_[0]->size();
    116 }
    117 
    118 ConstantArrayBuilder::ConstantArraySlice* ConstantArrayBuilder::IndexToSlice(
    119     size_t index) const {
    120   for (ConstantArraySlice* slice : idx_slice_) {
    121     if (index <= slice->max_index()) {
    122       return slice;
    123     }
    124   }
    125   UNREACHABLE();
    126   return nullptr;
    127 }
    128 
    129 MaybeHandle<Object> ConstantArrayBuilder::At(size_t index,
    130                                              Isolate* isolate) const {
    131   const ConstantArraySlice* slice = IndexToSlice(index);
    132   DCHECK_LT(index, slice->capacity());
    133   if (index < slice->start_index() + slice->size()) {
    134     const Entry& entry = slice->At(index);
    135     if (!entry.IsDeferred()) return entry.ToHandle(isolate);
    136   }
    137   return MaybeHandle<Object>();
    138 }
    139 
    140 Handle<FixedArray> ConstantArrayBuilder::ToFixedArray(Isolate* isolate) {
    141   Handle<FixedArray> fixed_array = isolate->factory()->NewFixedArrayWithHoles(
    142       static_cast<int>(size()), PretenureFlag::TENURED);
    143   int array_index = 0;
    144   for (const ConstantArraySlice* slice : idx_slice_) {
    145     DCHECK_EQ(slice->reserved(), 0);
    146     DCHECK(array_index == 0 ||
    147            base::bits::IsPowerOfTwo32(static_cast<uint32_t>(array_index)));
    148 #if DEBUG
    149     // Different slices might contain the same element due to reservations, but
    150     // all elements within a slice should be unique. If this DCHECK fails, then
    151     // the AST nodes are not being internalized within a CanonicalHandleScope.
    152     slice->CheckAllElementsAreUnique(isolate);
    153 #endif
    154     // Copy objects from slice into array.
    155     for (size_t i = 0; i < slice->size(); ++i) {
    156       fixed_array->set(array_index++,
    157                        *slice->At(slice->start_index() + i).ToHandle(isolate));
    158     }
    159     // Leave holes where reservations led to unused slots.
    160     size_t padding = slice->capacity() - slice->size();
    161     if (static_cast<size_t>(fixed_array->length() - array_index) <= padding) {
    162       break;
    163     }
    164     array_index += padding;
    165   }
    166   DCHECK_GE(array_index, fixed_array->length());
    167   return fixed_array;
    168 }
    169 
    170 size_t ConstantArrayBuilder::Insert(Smi* smi) {
    171   auto entry = smi_map_.find(smi);
    172   if (entry == smi_map_.end()) {
    173     return AllocateReservedEntry(smi);
    174   }
    175   return entry->second;
    176 }
    177 
    178 size_t ConstantArrayBuilder::Insert(const AstRawString* raw_string) {
    179   return constants_map_
    180       .LookupOrInsert(reinterpret_cast<intptr_t>(raw_string),
    181                       raw_string->hash(),
    182                       [&]() { return AllocateIndex(Entry(raw_string)); },
    183                       ZoneAllocationPolicy(zone_))
    184       ->value;
    185 }
    186 
    187 size_t ConstantArrayBuilder::Insert(const AstValue* heap_number) {
    188   // This method only accepts heap numbers. Other types of ast value should
    189   // either be passed through as raw values (in the case of strings), use the
    190   // singleton Insert methods (in the case of symbols), or skip the constant
    191   // pool entirely and use bytecodes with immediate values (Smis, booleans,
    192   // undefined, etc.).
    193   DCHECK(heap_number->IsHeapNumber());
    194   return constants_map_
    195       .LookupOrInsert(reinterpret_cast<intptr_t>(heap_number),
    196                       static_cast<uint32_t>(base::hash_value(heap_number)),
    197                       [&]() { return AllocateIndex(Entry(heap_number)); },
    198                       ZoneAllocationPolicy(zone_))
    199       ->value;
    200 }
    201 
    202 size_t ConstantArrayBuilder::Insert(const Scope* scope) {
    203   return constants_map_
    204       .LookupOrInsert(reinterpret_cast<intptr_t>(scope),
    205                       static_cast<uint32_t>(base::hash_value(scope)),
    206                       [&]() { return AllocateIndex(Entry(scope)); },
    207                       ZoneAllocationPolicy(zone_))
    208       ->value;
    209 }
    210 
    211 #define INSERT_ENTRY(NAME, LOWER_NAME)              \
    212   size_t ConstantArrayBuilder::Insert##NAME() {     \
    213     if (LOWER_NAME##_ < 0) {                        \
    214       LOWER_NAME##_ = AllocateIndex(Entry::NAME()); \
    215     }                                               \
    216     return LOWER_NAME##_;                           \
    217   }
    218 SINGLETON_CONSTANT_ENTRY_TYPES(INSERT_ENTRY)
    219 #undef INSERT_ENTRY
    220 
    221 ConstantArrayBuilder::index_t ConstantArrayBuilder::AllocateIndex(
    222     ConstantArrayBuilder::Entry entry) {
    223   for (size_t i = 0; i < arraysize(idx_slice_); ++i) {
    224     if (idx_slice_[i]->available() > 0) {
    225       return static_cast<index_t>(idx_slice_[i]->Allocate(entry));
    226     }
    227   }
    228   UNREACHABLE();
    229   return kMaxUInt32;
    230 }
    231 
    232 ConstantArrayBuilder::ConstantArraySlice*
    233 ConstantArrayBuilder::OperandSizeToSlice(OperandSize operand_size) const {
    234   ConstantArraySlice* slice = nullptr;
    235   switch (operand_size) {
    236     case OperandSize::kNone:
    237       UNREACHABLE();
    238       break;
    239     case OperandSize::kByte:
    240       slice = idx_slice_[0];
    241       break;
    242     case OperandSize::kShort:
    243       slice = idx_slice_[1];
    244       break;
    245     case OperandSize::kQuad:
    246       slice = idx_slice_[2];
    247       break;
    248   }
    249   DCHECK(slice->operand_size() == operand_size);
    250   return slice;
    251 }
    252 
    253 size_t ConstantArrayBuilder::InsertDeferred() {
    254   return AllocateIndex(Entry::Deferred());
    255 }
    256 
    257 void ConstantArrayBuilder::SetDeferredAt(size_t index, Handle<Object> object) {
    258   ConstantArraySlice* slice = IndexToSlice(index);
    259   return slice->At(index).SetDeferred(object);
    260 }
    261 
    262 OperandSize ConstantArrayBuilder::CreateReservedEntry() {
    263   for (size_t i = 0; i < arraysize(idx_slice_); ++i) {
    264     if (idx_slice_[i]->available() > 0) {
    265       idx_slice_[i]->Reserve();
    266       return idx_slice_[i]->operand_size();
    267     }
    268   }
    269   UNREACHABLE();
    270   return OperandSize::kNone;
    271 }
    272 
    273 ConstantArrayBuilder::index_t ConstantArrayBuilder::AllocateReservedEntry(
    274     Smi* value) {
    275   index_t index = static_cast<index_t>(AllocateIndex(Entry(value)));
    276   smi_map_[value] = index;
    277   return index;
    278 }
    279 
    280 size_t ConstantArrayBuilder::CommitReservedEntry(OperandSize operand_size,
    281                                                  Smi* value) {
    282   DiscardReservedEntry(operand_size);
    283   size_t index;
    284   auto entry = smi_map_.find(value);
    285   if (entry == smi_map_.end()) {
    286     index = AllocateReservedEntry(value);
    287   } else {
    288     ConstantArraySlice* slice = OperandSizeToSlice(operand_size);
    289     index = entry->second;
    290     if (index > slice->max_index()) {
    291       // The object is already in the constant array, but may have an
    292       // index too big for the reserved operand_size. So, duplicate
    293       // entry with the smaller operand size.
    294       index = AllocateReservedEntry(value);
    295     }
    296     DCHECK_LE(index, slice->max_index());
    297   }
    298   return index;
    299 }
    300 
    301 void ConstantArrayBuilder::DiscardReservedEntry(OperandSize operand_size) {
    302   OperandSizeToSlice(operand_size)->Unreserve();
    303 }
    304 
    305 Handle<Object> ConstantArrayBuilder::Entry::ToHandle(Isolate* isolate) const {
    306   switch (tag_) {
    307     case Tag::kDeferred:
    308       // We shouldn't have any deferred entries by now.
    309       UNREACHABLE();
    310       return Handle<Object>::null();
    311     case Tag::kHandle:
    312       return handle_;
    313     case Tag::kSmi:
    314       return handle(smi_, isolate);
    315     case Tag::kRawString:
    316       return raw_string_->string();
    317     case Tag::kHeapNumber:
    318       DCHECK(heap_number_->IsHeapNumber());
    319       return heap_number_->value();
    320     case Tag::kScope:
    321       return scope_->scope_info();
    322 #define ENTRY_LOOKUP(Name, name) \
    323   case Tag::k##Name:             \
    324     return isolate->factory()->name();
    325       SINGLETON_CONSTANT_ENTRY_TYPES(ENTRY_LOOKUP);
    326 #undef ENTRY_LOOKUP
    327   }
    328   UNREACHABLE();
    329   return Handle<Object>::null();
    330 }
    331 
    332 }  // namespace interpreter
    333 }  // namespace internal
    334 }  // namespace v8
    335