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#include "src/codegen/safepoint-table.h"
6
7#include <iomanip>
8
9#include "src/codegen/assembler-inl.h"
10#include "src/codegen/macro-assembler.h"
11#include "src/deoptimizer/deoptimizer.h"
12#include "src/diagnostics/disasm.h"
13#include "src/execution/frames-inl.h"
14#include "src/utils/ostreams.h"
15
16#if V8_ENABLE_WEBASSEMBLY
17#include "src/wasm/wasm-code-manager.h"
18#endif  // V8_ENABLE_WEBASSEMBLY
19
20namespace v8 {
21namespace internal {
22
23SafepointTable::SafepointTable(Isolate* isolate, Address pc, Code code)
24    : SafepointTable(code.InstructionStart(isolate, pc),
25                     code.SafepointTableAddress()) {}
26
27#if V8_ENABLE_WEBASSEMBLY
28SafepointTable::SafepointTable(const wasm::WasmCode* code)
29    : SafepointTable(
30          code->instruction_start(),
31          code->instruction_start() + code->safepoint_table_offset()) {}
32#endif  // V8_ENABLE_WEBASSEMBLY
33
34SafepointTable::SafepointTable(Address instruction_start,
35                               Address safepoint_table_address)
36    : instruction_start_(instruction_start),
37      safepoint_table_address_(safepoint_table_address),
38      length_(base::Memory<int>(safepoint_table_address + kLengthOffset)),
39      entry_configuration_(base::Memory<uint32_t>(safepoint_table_address +
40                                                  kEntryConfigurationOffset)) {}
41
42int SafepointTable::find_return_pc(int pc_offset) {
43  for (int i = 0; i < length(); i++) {
44    SafepointEntry entry = GetEntry(i);
45    if (entry.trampoline_pc() == pc_offset || entry.pc() == pc_offset) {
46      return entry.pc();
47    }
48  }
49  UNREACHABLE();
50}
51
52SafepointEntry SafepointTable::FindEntry(Address pc) const {
53  int pc_offset = static_cast<int>(pc - instruction_start_);
54
55  // Check if the PC is pointing at a trampoline.
56  if (has_deopt_data()) {
57    int candidate = -1;
58    for (int i = 0; i < length_; ++i) {
59      int trampoline_pc = GetEntry(i).trampoline_pc();
60      if (trampoline_pc != -1 && trampoline_pc <= pc_offset) candidate = i;
61      if (trampoline_pc > pc_offset) break;
62    }
63    if (candidate != -1) return GetEntry(candidate);
64  }
65
66  for (int i = 0; i < length_; ++i) {
67    SafepointEntry entry = GetEntry(i);
68    if (i == length_ - 1 || GetEntry(i + 1).pc() > pc_offset) {
69      DCHECK_LE(entry.pc(), pc_offset);
70      return entry;
71    }
72  }
73  UNREACHABLE();
74}
75
76void SafepointTable::Print(std::ostream& os) const {
77  os << "Safepoints (entries = " << length_ << ", byte size = " << byte_size()
78     << ")\n";
79
80  for (int index = 0; index < length_; index++) {
81    SafepointEntry entry = GetEntry(index);
82    os << reinterpret_cast<const void*>(instruction_start_ + entry.pc()) << " "
83       << std::setw(6) << std::hex << entry.pc() << std::dec;
84
85    if (!entry.tagged_slots().empty()) {
86      os << "  slots (sp->fp): ";
87      for (uint8_t bits : entry.tagged_slots()) {
88        for (int bit = 0; bit < kBitsPerByte; ++bit) {
89          os << ((bits >> bit) & 1);
90        }
91      }
92    }
93
94    if (entry.tagged_register_indexes() != 0) {
95      os << "  registers: ";
96      uint32_t register_bits = entry.tagged_register_indexes();
97      int bits = 32 - base::bits::CountLeadingZeros32(register_bits);
98      for (int j = bits - 1; j >= 0; --j) {
99        os << ((register_bits >> j) & 1);
100      }
101    }
102
103    if (entry.has_deoptimization_index()) {
104      os << "  deopt " << std::setw(6) << entry.deoptimization_index()
105         << " trampoline: " << std::setw(6) << std::hex
106         << entry.trampoline_pc();
107    }
108    os << "\n";
109  }
110}
111
112SafepointTableBuilder::Safepoint SafepointTableBuilder::DefineSafepoint(
113    Assembler* assembler) {
114  entries_.push_back(EntryBuilder(zone_, assembler->pc_offset_for_safepoint()));
115  return SafepointTableBuilder::Safepoint(&entries_.back(), this);
116}
117
118int SafepointTableBuilder::UpdateDeoptimizationInfo(int pc, int trampoline,
119                                                    int start,
120                                                    int deopt_index) {
121  DCHECK_NE(SafepointEntry::kNoTrampolinePC, trampoline);
122  DCHECK_NE(SafepointEntry::kNoDeoptIndex, deopt_index);
123  auto it = entries_.Find(start);
124  DCHECK(std::any_of(it, entries_.end(),
125                     [pc](auto& entry) { return entry.pc == pc; }));
126  int index = start;
127  while (it->pc != pc) ++it, ++index;
128  it->trampoline = trampoline;
129  it->deopt_index = deopt_index;
130  return index;
131}
132
133void SafepointTableBuilder::Emit(Assembler* assembler, int tagged_slots_size) {
134  DCHECK_LT(max_stack_index_, tagged_slots_size);
135
136#ifdef DEBUG
137  int last_pc = -1;
138  int last_trampoline = -1;
139  for (const EntryBuilder& entry : entries_) {
140    // Entries are ordered by PC.
141    DCHECK_LT(last_pc, entry.pc);
142    last_pc = entry.pc;
143    // Trampoline PCs are increasing, and larger than regular PCs.
144    if (entry.trampoline != SafepointEntry::kNoTrampolinePC) {
145      DCHECK_LT(last_trampoline, entry.trampoline);
146      DCHECK_LT(entries_.back().pc, entry.trampoline);
147      last_trampoline = entry.trampoline;
148    }
149    // An entry either has trampoline and deopt index, or none of the two.
150    DCHECK_EQ(entry.trampoline == SafepointEntry::kNoTrampolinePC,
151              entry.deopt_index == SafepointEntry::kNoDeoptIndex);
152  }
153#endif  // DEBUG
154
155  RemoveDuplicates();
156
157  // The encoding is compacted by translating stack slot indices s.t. they
158  // start at 0. See also below.
159  tagged_slots_size -= min_stack_index();
160
161#if V8_TARGET_ARCH_ARM || V8_TARGET_ARCH_ARM64
162  // We cannot emit a const pool within the safepoint table.
163  Assembler::BlockConstPoolScope block_const_pool(assembler);
164#endif
165
166  // Make sure the safepoint table is properly aligned. Pad with nops.
167  assembler->Align(Code::kMetadataAlignment);
168  assembler->RecordComment(";;; Safepoint table.");
169  safepoint_table_offset_ = assembler->pc_offset();
170
171  // Compute the required sizes of the fields.
172  int used_register_indexes = 0;
173  STATIC_ASSERT(SafepointEntry::kNoTrampolinePC == -1);
174  int max_pc = SafepointEntry::kNoTrampolinePC;
175  STATIC_ASSERT(SafepointEntry::kNoDeoptIndex == -1);
176  int max_deopt_index = SafepointEntry::kNoDeoptIndex;
177  for (const EntryBuilder& entry : entries_) {
178    used_register_indexes |= entry.register_indexes;
179    max_pc = std::max(max_pc, std::max(entry.pc, entry.trampoline));
180    max_deopt_index = std::max(max_deopt_index, entry.deopt_index);
181  }
182
183  // Derive the bytes and bools for the entry configuration from the values.
184  auto value_to_bytes = [](int value) {
185    DCHECK_LE(0, value);
186    if (value == 0) return 0;
187    if (value <= 0xff) return 1;
188    if (value <= 0xffff) return 2;
189    if (value <= 0xffffff) return 3;
190    return 4;
191  };
192  bool has_deopt_data = max_deopt_index != -1;
193  int register_indexes_size = value_to_bytes(used_register_indexes);
194  // Add 1 so all values (including kNoDeoptIndex and kNoTrampolinePC) are
195  // non-negative.
196  STATIC_ASSERT(SafepointEntry::kNoDeoptIndex == -1);
197  STATIC_ASSERT(SafepointEntry::kNoTrampolinePC == -1);
198  int pc_size = value_to_bytes(max_pc + 1);
199  int deopt_index_size = value_to_bytes(max_deopt_index + 1);
200  int tagged_slots_bytes =
201      (tagged_slots_size + kBitsPerByte - 1) / kBitsPerByte;
202
203  // Add a CHECK to ensure we never overflow the space in the bitfield, even for
204  // huge functions which might not be covered by tests.
205  CHECK(SafepointTable::RegisterIndexesSizeField::is_valid(
206            register_indexes_size) &&
207        SafepointTable::PcSizeField::is_valid(pc_size) &&
208        SafepointTable::DeoptIndexSizeField::is_valid(deopt_index_size) &&
209        SafepointTable::TaggedSlotsBytesField::is_valid(tagged_slots_bytes));
210
211  uint32_t entry_configuration =
212      SafepointTable::HasDeoptDataField::encode(has_deopt_data) |
213      SafepointTable::RegisterIndexesSizeField::encode(register_indexes_size) |
214      SafepointTable::PcSizeField::encode(pc_size) |
215      SafepointTable::DeoptIndexSizeField::encode(deopt_index_size) |
216      SafepointTable::TaggedSlotsBytesField::encode(tagged_slots_bytes);
217
218  // Emit the table header.
219  STATIC_ASSERT(SafepointTable::kLengthOffset == 0 * kIntSize);
220  STATIC_ASSERT(SafepointTable::kEntryConfigurationOffset == 1 * kIntSize);
221  STATIC_ASSERT(SafepointTable::kHeaderSize == 2 * kIntSize);
222  int length = static_cast<int>(entries_.size());
223  assembler->dd(length);
224  assembler->dd(entry_configuration);
225
226  auto emit_bytes = [assembler](int value, int bytes) {
227    DCHECK_LE(0, value);
228    for (; bytes > 0; --bytes, value >>= 8) assembler->db(value);
229    DCHECK_EQ(0, value);
230  };
231  // Emit entries, sorted by pc offsets.
232  for (const EntryBuilder& entry : entries_) {
233    emit_bytes(entry.pc, pc_size);
234    if (has_deopt_data) {
235      // Add 1 so all values (including kNoDeoptIndex and kNoTrampolinePC) are
236      // non-negative.
237      STATIC_ASSERT(SafepointEntry::kNoDeoptIndex == -1);
238      STATIC_ASSERT(SafepointEntry::kNoTrampolinePC == -1);
239      emit_bytes(entry.deopt_index + 1, deopt_index_size);
240      emit_bytes(entry.trampoline + 1, pc_size);
241    }
242    emit_bytes(entry.register_indexes, register_indexes_size);
243  }
244
245  // Emit bitmaps of tagged stack slots. Note the slot list is reversed in the
246  // encoding.
247  // TODO(jgruber): Avoid building a reversed copy of the bit vector.
248  ZoneVector<uint8_t> bits(tagged_slots_bytes, 0, zone_);
249  for (const EntryBuilder& entry : entries_) {
250    std::fill(bits.begin(), bits.end(), 0);
251
252    // Run through the indexes and build a bitmap.
253    for (int idx : *entry.stack_indexes) {
254      // The encoding is compacted by translating stack slot indices s.t. they
255      // start at 0. See also above.
256      const int adjusted_idx = idx - min_stack_index();
257      DCHECK_GT(tagged_slots_size, adjusted_idx);
258      int index = tagged_slots_size - 1 - adjusted_idx;
259      int byte_index = index >> kBitsPerByteLog2;
260      int bit_index = index & (kBitsPerByte - 1);
261      bits[byte_index] |= (1u << bit_index);
262    }
263
264    // Emit the bitmap for the current entry.
265    for (uint8_t byte : bits) assembler->db(byte);
266  }
267}
268
269void SafepointTableBuilder::RemoveDuplicates() {
270  // Remove any duplicate entries, i.e. succeeding entries that are identical
271  // except for the PC. During lookup, we will find the first entry whose PC is
272  // not larger than the PC at hand, and find the first non-duplicate.
273
274  if (entries_.size() < 2) return;
275
276  auto is_identical_except_for_pc = [](const EntryBuilder& entry1,
277                                       const EntryBuilder& entry2) {
278    if (entry1.deopt_index != entry2.deopt_index) return false;
279    DCHECK_EQ(entry1.trampoline, entry2.trampoline);
280    return entry1.register_indexes == entry2.register_indexes &&
281           entry1.stack_indexes->Equals(*entry2.stack_indexes);
282  };
283
284  auto remaining_it = entries_.begin();
285  size_t remaining = 0;
286
287  for (auto it = entries_.begin(), end = entries_.end(); it != end;
288       ++remaining_it, ++remaining) {
289    if (remaining_it != it) *remaining_it = *it;
290    // Merge identical entries.
291    do {
292      ++it;
293    } while (it != end && is_identical_except_for_pc(*it, *remaining_it));
294  }
295
296  entries_.Rewind(remaining);
297}
298
299}  // namespace internal
300}  // namespace v8
301