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