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