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
16namespace v8 {
17namespace internal {
18
19class Isolate;
20class AstRawString;
21class AstValue;
22
23namespace 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.
40class 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:
119    explicit Entry(Smi smi) : smi_(smi), tag_(Tag::kSmi) {}
120    explicit Entry(double heap_number)
121        : heap_number_(heap_number), tag_(Tag::kHeapNumber) {}
122    explicit Entry(const AstRawString* raw_string)
123        : raw_string_(raw_string), tag_(Tag::kRawString) {}
124    explicit Entry(AstBigInt bigint) : bigint_(bigint), tag_(Tag::kBigInt) {}
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); }
129    SINGLETON_CONSTANT_ENTRY_TYPES(CONSTRUCT_ENTRY)
130#undef CONSTRUCT_ENTRY
131
132    static Entry Deferred() { return Entry(Tag::kDeferred); }
133
134    static Entry UninitializedJumpTableSmi() {
135      return Entry(Tag::kUninitializedJumpTableSmi);
136    }
137
138    bool IsDeferred() const { return tag_ == Tag::kDeferred; }
139
140    bool IsJumpTableEntry() const {
141      return tag_ == Tag::kUninitializedJumpTableSmi ||
142             tag_ == Tag::kJumpTableSmi;
143    }
144
145    void SetDeferred(Handle<Object> handle) {
146      DCHECK_EQ(tag_, Tag::kDeferred);
147      tag_ = Tag::kHandle;
148      handle_ = handle;
149    }
150
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:
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
214    inline size_t available() const { return capacity() - reserved() - size(); }
215    inline size_t reserved() const { return reserved_; }
216    inline size_t capacity() const { return capacity_; }
217    inline size_t size() const { return constants_.size(); }
218    inline size_t start_index() const { return start_index_; }
219    inline size_t max_index() const { return start_index_ + capacity() - 1; }
220    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