Home | History | Annotate | Download | only in src 
      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 
     18 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 
     29 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 
     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 
     53 SafepointTable::SafepointTable(Code* code)
     54     : SafepointTable(code->InstructionStart(), code->safepoint_table_offset(),
     55                      code->stack_slots(), true) {}
     56 
     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 
     69 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 
     90 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 
    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 
    124 void Safepoint::DefinePointerRegister(Register reg) {
    125   registers_->push_back(reg.code());
    126 }
    127 
    128 
    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 
    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 
    151 unsigned SafepointTableBuilder::GetCodeOffset() const {
    152   DCHECK(emitted_);
    153   return offset_;
    154 }
    155 
    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 
    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 
    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 
    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 
    262 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