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