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/safepoint-table.h"
6
7#include "src/assembler-inl.h"
8#include "src/deoptimizer.h"
9#include "src/disasm.h"
10#include "src/frames-inl.h"
11#include "src/macro-assembler.h"
12#include "src/ostreams.h"
13
14namespace v8 {
15namespace internal {
16
17
18bool SafepointEntry::HasRegisters() const {
19 DCHECK(is_valid());
20 DCHECK(IsAligned(kNumSafepointRegisters, kBitsPerByte));
21 const int num_reg_bytes = kNumSafepointRegisters >> kBitsPerByteLog2;
22 for (int i = 0; i < num_reg_bytes; i++) {
23 if (bits_[i] != SafepointTable::kNoRegisters) return true;
24 }
25 return false;
26}
27
28
29bool SafepointEntry::HasRegisterAt(int reg_index) const {
30 DCHECK(is_valid());
31 DCHECK(reg_index >= 0 && reg_index < kNumSafepointRegisters);
32 int byte_index = reg_index >> kBitsPerByteLog2;
33 int bit_index = reg_index & (kBitsPerByte - 1);
34 return (bits_[byte_index] & (1 << bit_index)) != 0;
35}
36
37SafepointTable::SafepointTable(Address instruction_start,
38 size_t safepoint_table_offset,
39 uint32_t stack_slots, bool has_deopt)
40 : instruction_start_(instruction_start),
41 stack_slots_(stack_slots),
42 has_deopt_(has_deopt) {
43 Address header = instruction_start_ + safepoint_table_offset;
44 length_ = Memory<uint32_t>(header + kLengthOffset);
45 entry_size_ = Memory<uint32_t>(header + kEntrySizeOffset);
46 pc_and_deoptimization_indexes_ = header + kHeaderSize;
47 entries_ = pc_and_deoptimization_indexes_ + (length_ * kFixedEntrySize);
48 DCHECK_GT(entry_size_, 0);
49 STATIC_ASSERT(SafepointEntry::DeoptimizationIndexField::kMax ==
50 Safepoint::kNoDeoptimizationIndex);
51}
52
53SafepointTable::SafepointTable(Code code)
54 : SafepointTable(code->InstructionStart(), code->safepoint_table_offset(),
55 code->stack_slots(), true) {}
56
57unsigned SafepointTable::find_return_pc(unsigned pc_offset) {
58 for (unsigned i = 0; i < length(); i++) {
59 if (GetTrampolinePcOffset(i) == static_cast<int>(pc_offset)) {
60 return GetPcOffset(i);
61 } else if (GetPcOffset(i) == pc_offset) {
62 return pc_offset;
63 }
64 }
65 UNREACHABLE();
66 return 0;
67}
68
69SafepointEntry SafepointTable::FindEntry(Address pc) const {
70 unsigned pc_offset = static_cast<unsigned>(pc - instruction_start_);
71 // We use kMaxUInt32 as sentinel value, so check that we don't hit that.
72 DCHECK_NE(kMaxUInt32, pc_offset);
73 unsigned len = length();
74 CHECK_GT(len, 0);
75 // If pc == kMaxUInt32, then this entry covers all call sites in the function.
76 if (len == 1 && GetPcOffset(0) == kMaxUInt32) return GetEntry(0);
77 for (unsigned i = 0; i < len; i++) {
78 // TODO(kasperl): Replace the linear search with binary search.
79 if (GetPcOffset(i) == pc_offset ||
80 (has_deopt_ &&
81 GetTrampolinePcOffset(i) == static_cast<int>(pc_offset))) {
82 return GetEntry(i);
83 }
84 }
85 UNREACHABLE();
86 return SafepointEntry();
87}
88
89
90void SafepointTable::PrintEntry(unsigned index,
91 std::ostream& os) const { // NOLINT
92 disasm::NameConverter converter;
93 SafepointEntry entry = GetEntry(index);
94 uint8_t* bits = entry.bits();
95
96 // Print the stack slot bits.
97 if (entry_size_ > 0) {
98 DCHECK(IsAligned(kNumSafepointRegisters, kBitsPerByte));
99 const int first = kNumSafepointRegisters >> kBitsPerByteLog2;
100 int last = entry_size_ - 1;
101 for (int i = first; i < last; i++) PrintBits(os, bits[i], kBitsPerByte);
102 int last_bits = stack_slots_ - ((last - first) * kBitsPerByte);
103 PrintBits(os, bits[last], last_bits);
104
105 // Print the registers (if any).
106 if (!entry.HasRegisters()) return;
107 for (int j = 0; j < kNumSafepointRegisters; j++) {
108 if (entry.HasRegisterAt(j)) {
109 os << " | " << converter.NameOfCPURegister(j);
110 }
111 }
112 }
113}
114
115
116void SafepointTable::PrintBits(std::ostream& os, // NOLINT
117 uint8_t byte, int digits) {
118 DCHECK(digits >= 0 && digits <= kBitsPerByte);
119 for (int i = 0; i < digits; i++) {
120 os << (((byte & (1 << i)) == 0) ? "0" : "1");
121 }
122}
123
124void Safepoint::DefinePointerRegister(Register reg) {
125 registers_->push_back(reg.code());
126}
127
128
129Safepoint SafepointTableBuilder::DefineSafepoint(
130 Assembler* assembler,
131 Safepoint::Kind kind,
132 Safepoint::DeoptMode deopt_mode) {
133 deoptimization_info_.push_back(
134 DeoptimizationInfo(zone_, assembler->pc_offset(), kind));
135 if (deopt_mode == Safepoint::kNoLazyDeopt) {
136 last_lazy_safepoint_ = deoptimization_info_.size();
137 }
138 DeoptimizationInfo& new_info = deoptimization_info_.back();
139 return Safepoint(new_info.indexes, new_info.registers);
140}
141
142void SafepointTableBuilder::RecordLazyDeoptimizationIndex(int index) {
143 for (auto it = deoptimization_info_.Find(last_lazy_safepoint_);
144 it != deoptimization_info_.end(); it++, last_lazy_safepoint_++) {
145 it->deopt_index = index;
146 }
147}
148
149unsigned SafepointTableBuilder::GetCodeOffset() const {
150 DCHECK(emitted_);
151 return offset_;
152}
153
154int SafepointTableBuilder::UpdateDeoptimizationInfo(int pc, int trampoline,
155 int start) {
156 int index = start;
157 for (auto it = deoptimization_info_.Find(start);
158 it != deoptimization_info_.end(); it++, index++) {
159 if (static_cast<int>(it->pc) == pc) {
160 it->trampoline = trampoline;
161 return index;
162 }
163 }
164 UNREACHABLE();
165}
166
167void SafepointTableBuilder::Emit(Assembler* assembler, int bits_per_entry) {
168 RemoveDuplicates();
169
170 // Make sure the safepoint table is properly aligned. Pad with nops.
171 assembler->Align(kIntSize);
172 assembler->RecordComment(";;; Safepoint table.");
173 offset_ = assembler->pc_offset();
174
175 // Take the register bits into account.
176 bits_per_entry += kNumSafepointRegisters;
177
178 // Compute the number of bytes per safepoint entry.
179 int bytes_per_entry =
180 RoundUp(bits_per_entry, kBitsPerByte) >> kBitsPerByteLog2;
181
182 // Emit the table header.
183 STATIC_ASSERT(SafepointTable::kLengthOffset == 0 * kIntSize);
184 STATIC_ASSERT(SafepointTable::kEntrySizeOffset == 1 * kIntSize);
185 STATIC_ASSERT(SafepointTable::kHeaderSize == 2 * kIntSize);
186 int length = static_cast<int>(deoptimization_info_.size());
187 assembler->dd(length);
188 assembler->dd(bytes_per_entry);
189
190 // Emit sorted table of pc offsets together with additional info (i.e. the
191 // deoptimization index or arguments count) and trampoline offsets.
192 STATIC_ASSERT(SafepointTable::kPcOffset == 0 * kIntSize);
193 STATIC_ASSERT(SafepointTable::kEncodedInfoOffset == 1 * kIntSize);
194 STATIC_ASSERT(SafepointTable::kTrampolinePcOffset == 2 * kIntSize);
195 STATIC_ASSERT(SafepointTable::kFixedEntrySize == 3 * kIntSize);
196 for (const DeoptimizationInfo& info : deoptimization_info_) {
197 assembler->dd(info.pc);
198 assembler->dd(EncodeExceptPC(info));
199 assembler->dd(info.trampoline);
200 }
201
202 // Emit table of bitmaps.
203 ZoneVector<uint8_t> bits(bytes_per_entry, 0, zone_);
204 for (const DeoptimizationInfo& info : deoptimization_info_) {
205 ZoneChunkList<int>* indexes = info.indexes;
206 ZoneChunkList<int>* registers = info.registers;
207 std::fill(bits.begin(), bits.end(), 0);
208
209 // Run through the registers (if any).
210 DCHECK(IsAligned(kNumSafepointRegisters, kBitsPerByte));
211 if (registers == nullptr) {
212 const int num_reg_bytes = kNumSafepointRegisters >> kBitsPerByteLog2;
213 for (int j = 0; j < num_reg_bytes; j++) {
214 bits[j] = SafepointTable::kNoRegisters;
215 }
216 } else {
217 for (int index : *registers) {
218 DCHECK(index >= 0 && index < kNumSafepointRegisters);
219 int byte_index = index >> kBitsPerByteLog2;
220 int bit_index = index & (kBitsPerByte - 1);
221 bits[byte_index] |= (1 << bit_index);
222 }
223 }
224
225 // Run through the indexes and build a bitmap.
226 for (int idx : *indexes) {
227 int index = bits_per_entry - 1 - idx;
228 int byte_index = index >> kBitsPerByteLog2;
229 int bit_index = index & (kBitsPerByte - 1);
230 bits[byte_index] |= (1U << bit_index);
231 }
232
233 // Emit the bitmap for the current entry.
234 for (int k = 0; k < bytes_per_entry; k++) {
235 assembler->db(bits[k]);
236 }
237 }
238 emitted_ = true;
239}
240
241uint32_t SafepointTableBuilder::EncodeExceptPC(const DeoptimizationInfo& info) {
242 return SafepointEntry::DeoptimizationIndexField::encode(info.deopt_index) |
243 SafepointEntry::SaveDoublesField::encode(info.has_doubles);
244}
245
246void SafepointTableBuilder::RemoveDuplicates() {
247 // If the table contains more than one entry, and all entries are identical
248 // (except for the pc), replace the whole table by a single entry with pc =
249 // kMaxUInt32. This especially compacts the table for wasm code without tagged
250 // pointers and without deoptimization info.
251
252 if (deoptimization_info_.size() < 2) return;
253
254 // Check that all entries (1, size] are identical to entry 0.
255 const DeoptimizationInfo& first_info = deoptimization_info_.front();
256 for (auto it = deoptimization_info_.Find(1); it != deoptimization_info_.end();
257 it++) {
258 if (!IsIdenticalExceptForPc(first_info, *it)) return;
259 }
260
261 // If we get here, all entries were identical. Rewind the list to just one
262 // entry, and set the pc to kMaxUInt32.
263 deoptimization_info_.Rewind(1);
264 deoptimization_info_.front().pc = kMaxUInt32;
265}
266
267bool SafepointTableBuilder::IsIdenticalExceptForPc(
268 const DeoptimizationInfo& info1, const DeoptimizationInfo& info2) const {
269 if (info1.has_doubles != info2.has_doubles) return false;
270 if (info1.deopt_index != info2.deopt_index) return false;
271
272 ZoneChunkList<int>* indexes1 = info1.indexes;
273 ZoneChunkList<int>* indexes2 = info2.indexes;
274 if (indexes1->size() != indexes2->size()) return false;
275 if (!std::equal(indexes1->begin(), indexes1->end(), indexes2->begin())) {
276 return false;
277 }
278
279 ZoneChunkList<int>* registers1 = info1.registers;
280 ZoneChunkList<int>* registers2 = info2.registers;
281 if (registers1) {
282 if (!registers2) return false;
283 if (registers1->size() != registers2->size()) return false;
284 if (!std::equal(registers1->begin(), registers1->end(),
285 registers2->begin())) {
286 return false;
287 }
288 } else if (registers2) {
289 return false;
290 }
291
292 return true;
293}
294
295} // namespace internal
296} // namespace v8
297