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 #ifndef V8_INTERPRETER_CONSTANT_ARRAY_BUILDER_H_ 6 #define V8_INTERPRETER_CONSTANT_ARRAY_BUILDER_H_ 7 8 #include "src/ast/ast-value-factory.h" 9 #include "src/common/globals.h" 10 #include "src/handles/handles.h" 11 #include "src/interpreter/bytecodes.h" 12 #include "src/objects/smi.h" 13 #include "src/utils/identity-map.h" 14 #include "src/zone/zone-containers.h" 15 16 namespace v8 { 17 namespace internal { 18 19 class Isolate; 20 class AstRawString; 21 class AstValue; 22 23 namespace interpreter { 24 25 // Constant array entries that represent singletons. 26 #define SINGLETON_CONSTANT_ENTRY_TYPES(V) \ 27 V(AsyncIteratorSymbol, async_iterator_symbol) \ 28 V(ClassFieldsSymbol, class_fields_symbol) \ 29 V(EmptyObjectBoilerplateDescription, empty_object_boilerplate_description) \ 30 V(EmptyArrayBoilerplateDescription, empty_array_boilerplate_description) \ 31 V(EmptyFixedArray, empty_fixed_array) \ 32 V(HomeObjectSymbol, home_object_symbol) \ 33 V(IteratorSymbol, iterator_symbol) \ 34 V(InterpreterTrampolineSymbol, interpreter_trampoline_symbol) \ 35 V(NaN, nan_value) 36 37 // A helper class for constructing constant arrays for the 38 // interpreter. Each instance of this class is intended to be used to 39 // generate exactly one FixedArray of constants via the ToFixedArray 40 // method. 41 class V8_EXPORT_PRIVATE ConstantArrayBuilder final { 42 public: 43 // Capacity of the 8-bit operand slice. 44 static const size_t k8BitCapacity = 1u << kBitsPerByte; 45 46 // Capacity of the 16-bit operand slice. 47 static const size_t k16BitCapacity = (1u << 2 * kBitsPerByte) - k8BitCapacity; 48 49 // Capacity of the 32-bit operand slice. 50 static const size_t k32BitCapacity = 51 kMaxUInt32 - k16BitCapacity - k8BitCapacity + 1; 52 53 explicit ConstantArrayBuilder(Zone* zone); 54 55 // Generate a fixed array of constant handles based on inserted objects. 56 template <typename LocalIsolate> 57 EXPORT_TEMPLATE_DECLARE(V8_EXPORT_PRIVATE) 58 Handle<FixedArray> ToFixedArray(LocalIsolate* isolate); 59 60 // Returns the object, as a handle in |isolate|, that is in the constant pool 61 // array at index |index|. Returns null if there is no handle at this index. 62 // Only expected to be used in tests. 63 template <typename LocalIsolate> 64 EXPORT_TEMPLATE_DECLARE(V8_EXPORT_PRIVATE) 65 MaybeHandle<Object> At(size_t index, LocalIsolate* isolate) const; 66 67 // Returns the number of elements in the array. 68 size_t size() const; 69 70 // Insert an object into the constants array if it is not already present. 71 // Returns the array index associated with the object. 72 size_t Insert(Smi smi); 73 size_t Insert(double number); 74 size_t Insert(const AstRawString* raw_string); 75 size_t Insert(AstBigInt bigint); 76 size_t Insert(const Scope* scope); 77 #define INSERT_ENTRY(NAME, ...) size_t Insert##NAME(); 78 SINGLETON_CONSTANT_ENTRY_TYPES(INSERT_ENTRY) 79 #undef INSERT_ENTRY 80 81 // Inserts an empty entry and returns the array index associated with the 82 // reservation. The entry's handle value can be inserted by calling 83 // SetDeferredAt(). 84 size_t InsertDeferred(); 85 86 // Inserts |size| consecutive empty entries and returns the array index 87 // associated with the first reservation. Each entry's Smi value can be 88 // inserted by calling SetJumpTableSmi(). 89 size_t InsertJumpTable(size_t size); 90 91 // Sets the deferred value at |index| to |object|. 92 void SetDeferredAt(size_t index, Handle<Object> object); 93 94 // Sets the jump table entry at |index| to |smi|. Note that |index| is the 95 // constant pool index, not the switch case value. 96 void SetJumpTableSmi(size_t index, Smi smi); 97 98 // Creates a reserved entry in the constant pool and returns 99 // the size of the operand that'll be required to hold the entry 100 // when committed. 101 OperandSize CreateReservedEntry(); 102 103 // Commit reserved entry and returns the constant pool index for the 104 // SMI value. 105 size_t CommitReservedEntry(OperandSize operand_size, Smi value); 106 107 // Discards constant pool reservation. 108 void DiscardReservedEntry(OperandSize operand_size); 109 110 private: 111 using index_t = uint32_t; 112 113 struct ConstantArraySlice; 114 115 class Entry { 116 private: 117 enum class Tag : uint8_t; 118 119 public: Entry(Smi smi)120 explicit Entry(Smi smi) : smi_(smi), tag_(Tag::kSmi) {} Entry(double heap_number)121 explicit Entry(double heap_number) 122 : heap_number_(heap_number), tag_(Tag::kHeapNumber) {} Entry(const AstRawString * raw_string)123 explicit Entry(const AstRawString* raw_string) 124 : raw_string_(raw_string), tag_(Tag::kRawString) {} Entry(AstBigInt bigint)125 explicit Entry(AstBigInt bigint) : bigint_(bigint), tag_(Tag::kBigInt) {} Entry(const Scope * scope)126 explicit Entry(const Scope* scope) : scope_(scope), tag_(Tag::kScope) {} 127 128 #define CONSTRUCT_ENTRY(NAME, LOWER_NAME) \ 129 static Entry NAME() { return Entry(Tag::k##NAME); } SINGLETON_CONSTANT_ENTRY_TYPES(CONSTRUCT_ENTRY)130 SINGLETON_CONSTANT_ENTRY_TYPES(CONSTRUCT_ENTRY) 131 #undef CONSTRUCT_ENTRY 132 133 static Entry Deferred() { return Entry(Tag::kDeferred); } 134 UninitializedJumpTableSmi()135 static Entry UninitializedJumpTableSmi() { 136 return Entry(Tag::kUninitializedJumpTableSmi); 137 } 138 IsDeferred()139 bool IsDeferred() const { return tag_ == Tag::kDeferred; } 140 IsJumpTableEntry()141 bool IsJumpTableEntry() const { 142 return tag_ == Tag::kUninitializedJumpTableSmi || 143 tag_ == Tag::kJumpTableSmi; 144 } 145 SetDeferred(Handle<Object> handle)146 void SetDeferred(Handle<Object> handle) { 147 DCHECK_EQ(tag_, Tag::kDeferred); 148 tag_ = Tag::kHandle; 149 handle_ = handle; 150 } 151 SetJumpTableSmi(Smi smi)152 void SetJumpTableSmi(Smi smi) { 153 DCHECK_EQ(tag_, Tag::kUninitializedJumpTableSmi); 154 tag_ = Tag::kJumpTableSmi; 155 smi_ = smi; 156 } 157 158 template <typename LocalIsolate> 159 Handle<Object> ToHandle(LocalIsolate* isolate) const; 160 161 private: Entry(Tag tag)162 explicit Entry(Tag tag) : tag_(tag) {} 163 164 union { 165 Handle<Object> handle_; 166 Smi smi_; 167 double heap_number_; 168 const AstRawString* raw_string_; 169 AstBigInt bigint_; 170 const Scope* scope_; 171 }; 172 173 enum class Tag : uint8_t { 174 kDeferred, 175 kHandle, 176 kSmi, 177 kRawString, 178 kHeapNumber, 179 kBigInt, 180 kScope, 181 kUninitializedJumpTableSmi, 182 kJumpTableSmi, 183 #define ENTRY_TAG(NAME, ...) k##NAME, 184 SINGLETON_CONSTANT_ENTRY_TYPES(ENTRY_TAG) 185 #undef ENTRY_TAG 186 } tag_; 187 188 #if DEBUG 189 // Required by CheckAllElementsAreUnique(). 190 friend struct ConstantArraySlice; 191 #endif 192 }; 193 194 index_t AllocateIndex(Entry constant_entry); 195 index_t AllocateIndexArray(Entry constant_entry, size_t size); 196 index_t AllocateReservedEntry(Smi value); 197 198 struct ConstantArraySlice final : public ZoneObject { 199 ConstantArraySlice(Zone* zone, size_t start_index, size_t capacity, 200 OperandSize operand_size); 201 ConstantArraySlice(const ConstantArraySlice&) = delete; 202 ConstantArraySlice& operator=(const ConstantArraySlice&) = delete; 203 204 void Reserve(); 205 void Unreserve(); 206 size_t Allocate(Entry entry, size_t count = 1); 207 Entry& At(size_t index); 208 const Entry& At(size_t index) const; 209 210 #if DEBUG 211 template <typename LocalIsolate> 212 void CheckAllElementsAreUnique(LocalIsolate* isolate) const; 213 #endif 214 availablefinal215 inline size_t available() const { return capacity() - reserved() - size(); } reservedfinal216 inline size_t reserved() const { return reserved_; } capacityfinal217 inline size_t capacity() const { return capacity_; } sizefinal218 inline size_t size() const { return constants_.size(); } start_indexfinal219 inline size_t start_index() const { return start_index_; } max_indexfinal220 inline size_t max_index() const { return start_index_ + capacity() - 1; } operand_sizefinal221 inline OperandSize operand_size() const { return operand_size_; } 222 223 private: 224 const size_t start_index_; 225 const size_t capacity_; 226 size_t reserved_; 227 OperandSize operand_size_; 228 ZoneVector<Entry> constants_; 229 }; 230 231 ConstantArraySlice* IndexToSlice(size_t index) const; 232 ConstantArraySlice* OperandSizeToSlice(OperandSize operand_size) const; 233 234 ConstantArraySlice* idx_slice_[3]; 235 base::TemplateHashMapImpl<intptr_t, index_t, 236 base::KeyEqualityMatcher<intptr_t>, 237 ZoneAllocationPolicy> 238 constants_map_; 239 ZoneMap<Smi, index_t> smi_map_; 240 ZoneVector<std::pair<Smi, index_t>> smi_pairs_; 241 ZoneMap<double, index_t> heap_number_map_; 242 243 #define SINGLETON_ENTRY_FIELD(NAME, LOWER_NAME) int LOWER_NAME##_ = -1; 244 SINGLETON_CONSTANT_ENTRY_TYPES(SINGLETON_ENTRY_FIELD) 245 #undef SINGLETON_ENTRY_FIELD 246 }; 247 248 } // namespace interpreter 249 } // namespace internal 250 } // namespace v8 251 252 #endif // V8_INTERPRETER_CONSTANT_ARRAY_BUILDER_H_ 253