1// Copyright 2011 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_CODEGEN_SAFEPOINT_TABLE_H_
6#define V8_CODEGEN_SAFEPOINT_TABLE_H_
7
8#include "src/base/bit-field.h"
9#include "src/base/iterator.h"
10#include "src/base/memory.h"
11#include "src/common/assert-scope.h"
12#include "src/utils/allocation.h"
13#include "src/utils/bit-vector.h"
14#include "src/utils/utils.h"
15#include "src/zone/zone-chunk-list.h"
16#include "src/zone/zone.h"
17
18namespace v8 {
19namespace internal {
20
21namespace wasm {
22class WasmCode;
23}  // namespace wasm
24
25class SafepointEntry {
26 public:
27  static constexpr int kNoDeoptIndex = -1;
28  static constexpr int kNoTrampolinePC = -1;
29
30  SafepointEntry() = default;
31
32  SafepointEntry(int pc, int deopt_index, uint32_t tagged_register_indexes,
33                 base::Vector<uint8_t> tagged_slots, int trampoline_pc)
34      : pc_(pc),
35        deopt_index_(deopt_index),
36        tagged_register_indexes_(tagged_register_indexes),
37        tagged_slots_(tagged_slots),
38        trampoline_pc_(trampoline_pc) {
39    DCHECK(is_initialized());
40  }
41
42  bool is_initialized() const { return tagged_slots_.begin() != nullptr; }
43
44  bool operator==(const SafepointEntry& other) const {
45    return pc_ == other.pc_ && deopt_index_ == other.deopt_index_ &&
46           tagged_register_indexes_ == other.tagged_register_indexes_ &&
47           tagged_slots_ == other.tagged_slots_ &&
48           trampoline_pc_ == other.trampoline_pc_;
49  }
50
51  void Reset() {
52    *this = SafepointEntry{};
53    DCHECK(!is_initialized());
54  }
55
56  int pc() const { return pc_; }
57
58  int trampoline_pc() const { return trampoline_pc_; }
59
60  bool has_deoptimization_index() const {
61    DCHECK(is_initialized());
62    return deopt_index_ != kNoDeoptIndex;
63  }
64
65  int deoptimization_index() const {
66    DCHECK(is_initialized() && has_deoptimization_index());
67    return deopt_index_;
68  }
69
70  uint32_t tagged_register_indexes() const {
71    DCHECK(is_initialized());
72    return tagged_register_indexes_;
73  }
74
75  base::Vector<const uint8_t> tagged_slots() const {
76    DCHECK(is_initialized());
77    return tagged_slots_;
78  }
79
80 private:
81  int pc_ = -1;
82  int deopt_index_ = kNoDeoptIndex;
83  uint32_t tagged_register_indexes_ = 0;
84  base::Vector<uint8_t> tagged_slots_;
85  int trampoline_pc_ = kNoTrampolinePC;
86};
87
88// A wrapper class for accessing the safepoint table embedded into the Code
89// object.
90class SafepointTable {
91 public:
92  // The isolate and pc arguments are used for figuring out whether pc
93  // belongs to the embedded or un-embedded code blob.
94  explicit SafepointTable(Isolate* isolate, Address pc, Code code);
95#if V8_ENABLE_WEBASSEMBLY
96  explicit SafepointTable(const wasm::WasmCode* code);
97#endif  // V8_ENABLE_WEBASSEMBLY
98
99  SafepointTable(const SafepointTable&) = delete;
100  SafepointTable& operator=(const SafepointTable&) = delete;
101
102  int length() const { return length_; }
103
104  int byte_size() const {
105    return kHeaderSize + length_ * (entry_size() + tagged_slots_bytes());
106  }
107
108  int find_return_pc(int pc_offset);
109
110  SafepointEntry GetEntry(int index) const {
111    DCHECK_GT(length_, index);
112    Address entry_ptr =
113        safepoint_table_address_ + kHeaderSize + index * entry_size();
114
115    int pc = read_bytes(&entry_ptr, pc_size());
116    int deopt_index = SafepointEntry::kNoDeoptIndex;
117    int trampoline_pc = SafepointEntry::kNoTrampolinePC;
118    if (has_deopt_data()) {
119      STATIC_ASSERT(SafepointEntry::kNoDeoptIndex == -1);
120      STATIC_ASSERT(SafepointEntry::kNoTrampolinePC == -1);
121      // `-1` to restore the original value, see also
122      // SafepointTableBuilder::Emit.
123      deopt_index = read_bytes(&entry_ptr, deopt_index_size()) - 1;
124      trampoline_pc = read_bytes(&entry_ptr, pc_size()) - 1;
125      DCHECK(deopt_index >= 0 || deopt_index == SafepointEntry::kNoDeoptIndex);
126      DCHECK(trampoline_pc >= 0 ||
127             trampoline_pc == SafepointEntry::kNoTrampolinePC);
128    }
129    int tagged_register_indexes =
130        read_bytes(&entry_ptr, register_indexes_size());
131
132    // Entry bits start after the the vector of entries (thus the pc offset of
133    // the non-existing entry after the last one).
134    uint8_t* tagged_slots_start = reinterpret_cast<uint8_t*>(
135        safepoint_table_address_ + kHeaderSize + length_ * entry_size());
136    base::Vector<uint8_t> tagged_slots(
137        tagged_slots_start + index * tagged_slots_bytes(),
138        tagged_slots_bytes());
139
140    return SafepointEntry(pc, deopt_index, tagged_register_indexes,
141                          tagged_slots, trampoline_pc);
142  }
143
144  // Returns the entry for the given pc.
145  SafepointEntry FindEntry(Address pc) const;
146
147  void Print(std::ostream&) const;
148
149 private:
150  // Layout information.
151  static constexpr int kLengthOffset = 0;
152  static constexpr int kEntryConfigurationOffset = kLengthOffset + kIntSize;
153  static constexpr int kHeaderSize = kEntryConfigurationOffset + kUInt32Size;
154
155  using HasDeoptDataField = base::BitField<bool, 0, 1>;
156  using RegisterIndexesSizeField = HasDeoptDataField::Next<int, 3>;
157  using PcSizeField = RegisterIndexesSizeField::Next<int, 3>;
158  using DeoptIndexSizeField = PcSizeField::Next<int, 3>;
159  // In 22 bits, we can encode up to 4M bytes, corresponding to 32M frame slots,
160  // which is 128MB on 32-bit and 256MB on 64-bit systems. The stack size is
161  // limited to a bit below 1MB anyway (see FLAG_stack_size).
162  using TaggedSlotsBytesField = DeoptIndexSizeField::Next<int, 22>;
163
164  SafepointTable(Address instruction_start, Address safepoint_table_address);
165
166  int entry_size() const {
167    int deopt_data_size = has_deopt_data() ? pc_size() + deopt_index_size() : 0;
168    return pc_size() + deopt_data_size + register_indexes_size();
169  }
170
171  int tagged_slots_bytes() const {
172    return TaggedSlotsBytesField::decode(entry_configuration_);
173  }
174  bool has_deopt_data() const {
175    return HasDeoptDataField::decode(entry_configuration_);
176  }
177  int pc_size() const { return PcSizeField::decode(entry_configuration_); }
178  int deopt_index_size() const {
179    return DeoptIndexSizeField::decode(entry_configuration_);
180  }
181  int register_indexes_size() const {
182    return RegisterIndexesSizeField::decode(entry_configuration_);
183  }
184
185  static int read_bytes(Address* ptr, int bytes) {
186    uint32_t result = 0;
187    for (int b = 0; b < bytes; ++b, ++*ptr) {
188      result |= uint32_t{*reinterpret_cast<uint8_t*>(*ptr)} << (8 * b);
189    }
190    return static_cast<int>(result);
191  }
192
193  DISALLOW_GARBAGE_COLLECTION(no_gc_)
194
195  const Address instruction_start_;
196
197  // Safepoint table layout.
198  const Address safepoint_table_address_;
199  const int length_;
200  const uint32_t entry_configuration_;
201
202  friend class SafepointTableBuilder;
203  friend class SafepointEntry;
204};
205
206class SafepointTableBuilder {
207 private:
208  struct EntryBuilder {
209    int pc;
210    int deopt_index = SafepointEntry::kNoDeoptIndex;
211    int trampoline = SafepointEntry::kNoTrampolinePC;
212    GrowableBitVector* stack_indexes;
213    uint32_t register_indexes = 0;
214    EntryBuilder(Zone* zone, int pc)
215        : pc(pc), stack_indexes(zone->New<GrowableBitVector>()) {}
216  };
217
218 public:
219  explicit SafepointTableBuilder(Zone* zone) : entries_(zone), zone_(zone) {}
220
221  SafepointTableBuilder(const SafepointTableBuilder&) = delete;
222  SafepointTableBuilder& operator=(const SafepointTableBuilder&) = delete;
223
224  bool emitted() const {
225    return safepoint_table_offset_ != kNoSafepointTableOffset;
226  }
227
228  int safepoint_table_offset() const {
229    DCHECK(emitted());
230    return safepoint_table_offset_;
231  }
232
233  class Safepoint {
234   public:
235    void DefineTaggedStackSlot(int index) {
236      // Note it is only valid to specify stack slots here that are *not* in
237      // the fixed part of the frame (e.g. argc, target, context, stored rbp,
238      // return address). Frame iteration handles the fixed part of the frame
239      // with custom code, see CommonFrame::IterateCompiledFrame.
240      entry_->stack_indexes->Add(index, table_->zone_);
241      table_->UpdateMinMaxStackIndex(index);
242    }
243
244    void DefineTaggedRegister(int reg_code) {
245      DCHECK_LT(reg_code,
246                kBitsPerByte * sizeof(EntryBuilder::register_indexes));
247      entry_->register_indexes |= 1u << reg_code;
248    }
249
250   private:
251    friend class SafepointTableBuilder;
252    Safepoint(EntryBuilder* entry, SafepointTableBuilder* table)
253        : entry_(entry), table_(table) {}
254    EntryBuilder* const entry_;
255    SafepointTableBuilder* const table_;
256  };
257
258  // Define a new safepoint for the current position in the body.
259  Safepoint DefineSafepoint(Assembler* assembler);
260
261  // Emit the safepoint table after the body. The number of bits per
262  // entry must be enough to hold all the pointer indexes.
263  V8_EXPORT_PRIVATE void Emit(Assembler* assembler, int bits_per_entry);
264
265  // Find the Deoptimization Info with pc offset {pc} and update its
266  // trampoline field. Calling this function ensures that the safepoint
267  // table contains the trampoline PC {trampoline} that replaced the
268  // return PC {pc} on the stack.
269  int UpdateDeoptimizationInfo(int pc, int trampoline, int start,
270                               int deopt_index);
271
272 private:
273  // Remove consecutive identical entries.
274  void RemoveDuplicates();
275
276  void UpdateMinMaxStackIndex(int index) {
277#ifdef DEBUG
278    max_stack_index_ = std::max(max_stack_index_, index);
279#endif  // DEBUG
280    min_stack_index_ = std::min(min_stack_index_, index);
281  }
282
283  int min_stack_index() const {
284    return min_stack_index_ == std::numeric_limits<int>::max()
285               ? 0
286               : min_stack_index_;
287  }
288
289  static constexpr int kNoSafepointTableOffset = -1;
290
291  // Tracks the min/max stack slot index over all entries. We need the minimum
292  // index when encoding the actual table since we shift all unused lower
293  // indices out of the encoding. Tracking the indices during safepoint
294  // construction means we don't have to iterate again later.
295#ifdef DEBUG
296  int max_stack_index_ = 0;
297#endif  // DEBUG
298  int min_stack_index_ = std::numeric_limits<int>::max();
299
300  ZoneChunkList<EntryBuilder> entries_;
301  int safepoint_table_offset_ = kNoSafepointTableOffset;
302  Zone* const zone_;
303};
304
305}  // namespace internal
306}  // namespace v8
307
308#endif  // V8_CODEGEN_SAFEPOINT_TABLE_H_
309