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
14 namespace v8 {
15 namespace internal {
16
17
HasRegisters() const18 bool 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
HasRegisterAt(int reg_index) const29 bool 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
SafepointTable(Address instruction_start,size_t safepoint_table_offset,uint32_t stack_slots,bool has_deopt)37 SafepointTable::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
SafepointTable(Code * code)53 SafepointTable::SafepointTable(Code* code)
54 : SafepointTable(code->InstructionStart(), code->safepoint_table_offset(),
55 code->stack_slots(), true) {}
56
find_return_pc(unsigned pc_offset)57 unsigned 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
FindEntry(Address pc) const69 SafepointEntry 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
PrintEntry(unsigned index,std::ostream & os) const90 void 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
PrintBits(std::ostream & os,uint8_t byte,int digits)116 void 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
DefinePointerRegister(Register reg)124 void Safepoint::DefinePointerRegister(Register reg) {
125 registers_->push_back(reg.code());
126 }
127
128
DefineSafepoint(Assembler * assembler,Safepoint::Kind kind,int arguments,Safepoint::DeoptMode deopt_mode)129 Safepoint SafepointTableBuilder::DefineSafepoint(
130 Assembler* assembler,
131 Safepoint::Kind kind,
132 int arguments,
133 Safepoint::DeoptMode deopt_mode) {
134 DCHECK_GE(arguments, 0);
135 deoptimization_info_.push_back(
136 DeoptimizationInfo(zone_, assembler->pc_offset(), arguments, kind));
137 if (deopt_mode == Safepoint::kNoLazyDeopt) {
138 last_lazy_safepoint_ = deoptimization_info_.size();
139 }
140 DeoptimizationInfo& new_info = deoptimization_info_.back();
141 return Safepoint(new_info.indexes, new_info.registers);
142 }
143
RecordLazyDeoptimizationIndex(int index)144 void SafepointTableBuilder::RecordLazyDeoptimizationIndex(int index) {
145 for (auto it = deoptimization_info_.Find(last_lazy_safepoint_);
146 it != deoptimization_info_.end(); it++, last_lazy_safepoint_++) {
147 it->deopt_index = index;
148 }
149 }
150
GetCodeOffset() const151 unsigned SafepointTableBuilder::GetCodeOffset() const {
152 DCHECK(emitted_);
153 return offset_;
154 }
155
UpdateDeoptimizationInfo(int pc,int trampoline,int start)156 int SafepointTableBuilder::UpdateDeoptimizationInfo(int pc, int trampoline,
157 int start) {
158 int index = start;
159 for (auto it = deoptimization_info_.Find(start);
160 it != deoptimization_info_.end(); it++, index++) {
161 if (static_cast<int>(it->pc) == pc) {
162 it->trampoline = trampoline;
163 return index;
164 }
165 }
166 UNREACHABLE();
167 }
168
Emit(Assembler * assembler,int bits_per_entry)169 void SafepointTableBuilder::Emit(Assembler* assembler, int bits_per_entry) {
170 RemoveDuplicates();
171
172 // Make sure the safepoint table is properly aligned. Pad with nops.
173 assembler->Align(kIntSize);
174 assembler->RecordComment(";;; Safepoint table.");
175 offset_ = assembler->pc_offset();
176
177 // Take the register bits into account.
178 bits_per_entry += kNumSafepointRegisters;
179
180 // Compute the number of bytes per safepoint entry.
181 int bytes_per_entry =
182 RoundUp(bits_per_entry, kBitsPerByte) >> kBitsPerByteLog2;
183
184 // Emit the table header.
185 int length = static_cast<int>(deoptimization_info_.size());
186 assembler->dd(length);
187 assembler->dd(bytes_per_entry);
188
189 // Emit sorted table of pc offsets together with deoptimization indexes.
190 for (const DeoptimizationInfo& info : deoptimization_info_) {
191 assembler->dd(info.pc);
192 assembler->dd(EncodeExceptPC(info));
193 assembler->dd(info.trampoline);
194 }
195
196 // Emit table of bitmaps.
197 ZoneVector<uint8_t> bits(bytes_per_entry, 0, zone_);
198 for (const DeoptimizationInfo& info : deoptimization_info_) {
199 ZoneChunkList<int>* indexes = info.indexes;
200 ZoneChunkList<int>* registers = info.registers;
201 std::fill(bits.begin(), bits.end(), 0);
202
203 // Run through the registers (if any).
204 DCHECK(IsAligned(kNumSafepointRegisters, kBitsPerByte));
205 if (registers == nullptr) {
206 const int num_reg_bytes = kNumSafepointRegisters >> kBitsPerByteLog2;
207 for (int j = 0; j < num_reg_bytes; j++) {
208 bits[j] = SafepointTable::kNoRegisters;
209 }
210 } else {
211 for (int index : *registers) {
212 DCHECK(index >= 0 && index < kNumSafepointRegisters);
213 int byte_index = index >> kBitsPerByteLog2;
214 int bit_index = index & (kBitsPerByte - 1);
215 bits[byte_index] |= (1 << bit_index);
216 }
217 }
218
219 // Run through the indexes and build a bitmap.
220 for (int idx : *indexes) {
221 int index = bits_per_entry - 1 - idx;
222 int byte_index = index >> kBitsPerByteLog2;
223 int bit_index = index & (kBitsPerByte - 1);
224 bits[byte_index] |= (1U << bit_index);
225 }
226
227 // Emit the bitmap for the current entry.
228 for (int k = 0; k < bytes_per_entry; k++) {
229 assembler->db(bits[k]);
230 }
231 }
232 emitted_ = true;
233 }
234
EncodeExceptPC(const DeoptimizationInfo & info)235 uint32_t SafepointTableBuilder::EncodeExceptPC(const DeoptimizationInfo& info) {
236 return SafepointEntry::DeoptimizationIndexField::encode(info.deopt_index) |
237 SafepointEntry::ArgumentsField::encode(info.arguments) |
238 SafepointEntry::SaveDoublesField::encode(info.has_doubles);
239 }
240
RemoveDuplicates()241 void SafepointTableBuilder::RemoveDuplicates() {
242 // If the table contains more than one entry, and all entries are identical
243 // (except for the pc), replace the whole table by a single entry with pc =
244 // kMaxUInt32. This especially compacts the table for wasm code without tagged
245 // pointers and without deoptimization info.
246
247 if (deoptimization_info_.size() < 2) return;
248
249 // Check that all entries (1, size] are identical to entry 0.
250 const DeoptimizationInfo& first_info = deoptimization_info_.front();
251 for (auto it = deoptimization_info_.Find(1); it != deoptimization_info_.end();
252 it++) {
253 if (!IsIdenticalExceptForPc(first_info, *it)) return;
254 }
255
256 // If we get here, all entries were identical. Rewind the list to just one
257 // entry, and set the pc to kMaxUInt32.
258 deoptimization_info_.Rewind(1);
259 deoptimization_info_.front().pc = kMaxUInt32;
260 }
261
IsIdenticalExceptForPc(const DeoptimizationInfo & info1,const DeoptimizationInfo & info2) const262 bool SafepointTableBuilder::IsIdenticalExceptForPc(
263 const DeoptimizationInfo& info1, const DeoptimizationInfo& info2) const {
264 if (info1.arguments != info2.arguments) return false;
265 if (info1.has_doubles != info2.has_doubles) return false;
266
267 if (info1.deopt_index != info2.deopt_index) return false;
268
269 ZoneChunkList<int>* indexes1 = info1.indexes;
270 ZoneChunkList<int>* indexes2 = info2.indexes;
271 if (indexes1->size() != indexes2->size()) return false;
272 if (!std::equal(indexes1->begin(), indexes1->end(), indexes2->begin())) {
273 return false;
274 }
275
276 ZoneChunkList<int>* registers1 = info1.registers;
277 ZoneChunkList<int>* registers2 = info2.registers;
278 if (registers1) {
279 if (!registers2) return false;
280 if (registers1->size() != registers2->size()) return false;
281 if (!std::equal(registers1->begin(), registers1->end(),
282 registers2->begin())) {
283 return false;
284 }
285 } else if (registers2) {
286 return false;
287 }
288
289 return true;
290 }
291
292 } // namespace internal
293 } // namespace v8
294