Home | History | Annotate | Download | only in interpreter 
      1 // Copyright 2016 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/interpreter/bytecode-register-optimizer.h"
      6 
      7 namespace v8 {
      8 namespace internal {
      9 namespace interpreter {
     10 
     11 const uint32_t BytecodeRegisterOptimizer::kInvalidEquivalenceId = kMaxUInt32;
     12 
     13 // A class for tracking the state of a register. This class tracks
     14 // which equivalence set a register is a member of and also whether a
     15 // register is materialized in the bytecode stream.
     16 class BytecodeRegisterOptimizer::RegisterInfo final : public ZoneObject {
     17  public:
     18   RegisterInfo(Register reg, uint32_t equivalence_id, bool materialized,
     19                bool allocated)
     20       : register_(reg),
     21         equivalence_id_(equivalence_id),
     22         materialized_(materialized),
     23         allocated_(allocated),
     24         next_(this),
     25         prev_(this) {}
     26 
     27   void AddToEquivalenceSetOf(RegisterInfo* info);
     28   void MoveToNewEquivalenceSet(uint32_t equivalence_id, bool materialized);
     29   bool IsOnlyMemberOfEquivalenceSet() const;
     30   bool IsOnlyMaterializedMemberOfEquivalenceSet() const;
     31   bool IsInSameEquivalenceSet(RegisterInfo* info) const;
     32 
     33   // Get a member of this register's equivalence set that is
     34   // materialized. The materialized equivalent will be this register
     35   // if it is materialized. Returns nullptr if no materialized
     36   // equivalent exists.
     37   RegisterInfo* GetMaterializedEquivalent();
     38 
     39   // Get a member of this register's equivalence set that is
     40   // materialized and not register |reg|. The materialized equivalent
     41   // will be this register if it is materialized. Returns nullptr if
     42   // no materialized equivalent exists.
     43   RegisterInfo* GetMaterializedEquivalentOtherThan(Register reg);
     44 
     45   // Get a member of this register's equivalence set that is intended
     46   // to be materialized in place of this register (which is currently
     47   // materialized). The best candidate is deemed to be the register
     48   // with the lowest index as this permits temporary registers to be
     49   // removed from the bytecode stream. Returns nullptr if no candidate
     50   // exists.
     51   RegisterInfo* GetEquivalentToMaterialize();
     52 
     53   // Marks all temporary registers of the equivalence set as unmaterialized.
     54   void MarkTemporariesAsUnmaterialized(Register temporary_base);
     55 
     56   // Get an equivalent register. Returns this if none exists.
     57   RegisterInfo* GetEquivalent();
     58 
     59   Register register_value() const { return register_; }
     60   bool materialized() const { return materialized_; }
     61   void set_materialized(bool materialized) { materialized_ = materialized; }
     62   bool allocated() const { return allocated_; }
     63   void set_allocated(bool allocated) { allocated_ = allocated; }
     64   void set_equivalence_id(uint32_t equivalence_id) {
     65     equivalence_id_ = equivalence_id;
     66   }
     67   uint32_t equivalence_id() const { return equivalence_id_; }
     68 
     69  private:
     70   Register register_;
     71   uint32_t equivalence_id_;
     72   bool materialized_;
     73   bool allocated_;
     74 
     75   // Equivalence set pointers.
     76   RegisterInfo* next_;
     77   RegisterInfo* prev_;
     78 
     79   DISALLOW_COPY_AND_ASSIGN(RegisterInfo);
     80 };
     81 
     82 void BytecodeRegisterOptimizer::RegisterInfo::AddToEquivalenceSetOf(
     83     RegisterInfo* info) {
     84   DCHECK_NE(kInvalidEquivalenceId, info->equivalence_id());
     85   // Fix old list
     86   next_->prev_ = prev_;
     87   prev_->next_ = next_;
     88   // Add to new list.
     89   next_ = info->next_;
     90   prev_ = info;
     91   prev_->next_ = this;
     92   next_->prev_ = this;
     93   set_equivalence_id(info->equivalence_id());
     94   set_materialized(false);
     95 }
     96 
     97 void BytecodeRegisterOptimizer::RegisterInfo::MoveToNewEquivalenceSet(
     98     uint32_t equivalence_id, bool materialized) {
     99   next_->prev_ = prev_;
    100   prev_->next_ = next_;
    101   next_ = prev_ = this;
    102   equivalence_id_ = equivalence_id;
    103   materialized_ = materialized;
    104 }
    105 
    106 bool BytecodeRegisterOptimizer::RegisterInfo::IsOnlyMemberOfEquivalenceSet()
    107     const {
    108   return this->next_ == this;
    109 }
    110 
    111 bool BytecodeRegisterOptimizer::RegisterInfo::
    112     IsOnlyMaterializedMemberOfEquivalenceSet() const {
    113   DCHECK(materialized());
    114 
    115   const RegisterInfo* visitor = this->next_;
    116   while (visitor != this) {
    117     if (visitor->materialized()) {
    118       return false;
    119     }
    120     visitor = visitor->next_;
    121   }
    122   return true;
    123 }
    124 
    125 bool BytecodeRegisterOptimizer::RegisterInfo::IsInSameEquivalenceSet(
    126     RegisterInfo* info) const {
    127   return equivalence_id() == info->equivalence_id();
    128 }
    129 
    130 BytecodeRegisterOptimizer::RegisterInfo*
    131 BytecodeRegisterOptimizer::RegisterInfo::GetMaterializedEquivalent() {
    132   RegisterInfo* visitor = this;
    133   do {
    134     if (visitor->materialized()) {
    135       return visitor;
    136     }
    137     visitor = visitor->next_;
    138   } while (visitor != this);
    139 
    140   return nullptr;
    141 }
    142 
    143 BytecodeRegisterOptimizer::RegisterInfo*
    144 BytecodeRegisterOptimizer::RegisterInfo::GetMaterializedEquivalentOtherThan(
    145     Register reg) {
    146   RegisterInfo* visitor = this;
    147   do {
    148     if (visitor->materialized() && visitor->register_value() != reg) {
    149       return visitor;
    150     }
    151     visitor = visitor->next_;
    152   } while (visitor != this);
    153 
    154   return nullptr;
    155 }
    156 
    157 BytecodeRegisterOptimizer::RegisterInfo*
    158 BytecodeRegisterOptimizer::RegisterInfo::GetEquivalentToMaterialize() {
    159   DCHECK(this->materialized());
    160   RegisterInfo* visitor = this->next_;
    161   RegisterInfo* best_info = nullptr;
    162   while (visitor != this) {
    163     if (visitor->materialized()) {
    164       return nullptr;
    165     }
    166     if (visitor->allocated() &&
    167         (best_info == nullptr ||
    168          visitor->register_value() < best_info->register_value())) {
    169       best_info = visitor;
    170     }
    171     visitor = visitor->next_;
    172   }
    173   return best_info;
    174 }
    175 
    176 void BytecodeRegisterOptimizer::RegisterInfo::MarkTemporariesAsUnmaterialized(
    177     Register temporary_base) {
    178   DCHECK(this->register_value() < temporary_base);
    179   DCHECK(this->materialized());
    180   RegisterInfo* visitor = this->next_;
    181   while (visitor != this) {
    182     if (visitor->register_value() >= temporary_base) {
    183       visitor->set_materialized(false);
    184     }
    185     visitor = visitor->next_;
    186   }
    187 }
    188 
    189 BytecodeRegisterOptimizer::RegisterInfo*
    190 BytecodeRegisterOptimizer::RegisterInfo::GetEquivalent() {
    191   return next_;
    192 }
    193 
    194 BytecodeRegisterOptimizer::BytecodeRegisterOptimizer(
    195     Zone* zone, BytecodeRegisterAllocator* register_allocator,
    196     int fixed_registers_count, int parameter_count,
    197     BytecodePipelineStage* next_stage)
    198     : accumulator_(Register::virtual_accumulator()),
    199       temporary_base_(fixed_registers_count),
    200       max_register_index_(fixed_registers_count - 1),
    201       register_info_table_(zone),
    202       equivalence_id_(0),
    203       next_stage_(next_stage),
    204       flush_required_(false),
    205       zone_(zone) {
    206   register_allocator->set_observer(this);
    207 
    208   // Calculate offset so register index values can be mapped into
    209   // a vector of register metadata.
    210   if (parameter_count != 0) {
    211     register_info_table_offset_ =
    212         -Register::FromParameterIndex(0, parameter_count).index();
    213   } else {
    214     // TODO(oth): This path shouldn't be necessary in bytecode generated
    215     // from Javascript, but a set of tests do not include the JS receiver.
    216     register_info_table_offset_ = -accumulator_.index();
    217   }
    218 
    219   // Initialize register map for parameters, locals, and the
    220   // accumulator.
    221   register_info_table_.resize(register_info_table_offset_ +
    222                               static_cast<size_t>(temporary_base_.index()));
    223   for (size_t i = 0; i < register_info_table_.size(); ++i) {
    224     register_info_table_[i] = new (zone) RegisterInfo(
    225         RegisterFromRegisterInfoTableIndex(i), NextEquivalenceId(), true, true);
    226     DCHECK_EQ(register_info_table_[i]->register_value().index(),
    227               RegisterFromRegisterInfoTableIndex(i).index());
    228   }
    229   accumulator_info_ = GetRegisterInfo(accumulator_);
    230   DCHECK(accumulator_info_->register_value() == accumulator_);
    231 }
    232 
    233 void BytecodeRegisterOptimizer::Flush() {
    234   if (!flush_required_) {
    235     return;
    236   }
    237 
    238   // Materialize all live registers and break equivalences.
    239   size_t count = register_info_table_.size();
    240   for (size_t i = 0; i < count; ++i) {
    241     RegisterInfo* reg_info = register_info_table_[i];
    242     if (reg_info->materialized()) {
    243       // Walk equivalents of materialized registers, materializing
    244       // each equivalent register as necessary and placing in their
    245       // own equivalence set.
    246       RegisterInfo* equivalent;
    247       while ((equivalent = reg_info->GetEquivalent()) != reg_info) {
    248         if (equivalent->allocated() && !equivalent->materialized()) {
    249           OutputRegisterTransfer(reg_info, equivalent);
    250         }
    251         equivalent->MoveToNewEquivalenceSet(NextEquivalenceId(), true);
    252       }
    253     }
    254   }
    255 
    256   flush_required_ = false;
    257 }
    258 
    259 void BytecodeRegisterOptimizer::OutputRegisterTransfer(
    260     RegisterInfo* input_info, RegisterInfo* output_info,
    261     BytecodeSourceInfo source_info) {
    262   Register input = input_info->register_value();
    263   Register output = output_info->register_value();
    264   DCHECK_NE(input.index(), output.index());
    265 
    266   if (input == accumulator_) {
    267     uint32_t operand = static_cast<uint32_t>(output.ToOperand());
    268     BytecodeNode node = BytecodeNode::Star(source_info, operand);
    269     next_stage_->Write(&node);
    270   } else if (output == accumulator_) {
    271     uint32_t operand = static_cast<uint32_t>(input.ToOperand());
    272     BytecodeNode node = BytecodeNode::Ldar(source_info, operand);
    273     next_stage_->Write(&node);
    274   } else {
    275     uint32_t operand0 = static_cast<uint32_t>(input.ToOperand());
    276     uint32_t operand1 = static_cast<uint32_t>(output.ToOperand());
    277     BytecodeNode node = BytecodeNode::Mov(source_info, operand0, operand1);
    278     next_stage_->Write(&node);
    279   }
    280   if (output != accumulator_) {
    281     max_register_index_ = std::max(max_register_index_, output.index());
    282   }
    283   output_info->set_materialized(true);
    284 }
    285 
    286 void BytecodeRegisterOptimizer::CreateMaterializedEquivalent(
    287     RegisterInfo* info) {
    288   DCHECK(info->materialized());
    289   RegisterInfo* unmaterialized = info->GetEquivalentToMaterialize();
    290   if (unmaterialized) {
    291     OutputRegisterTransfer(info, unmaterialized);
    292   }
    293 }
    294 
    295 BytecodeRegisterOptimizer::RegisterInfo*
    296 BytecodeRegisterOptimizer::GetMaterializedEquivalent(RegisterInfo* info) {
    297   return info->materialized() ? info : info->GetMaterializedEquivalent();
    298 }
    299 
    300 BytecodeRegisterOptimizer::RegisterInfo*
    301 BytecodeRegisterOptimizer::GetMaterializedEquivalentNotAccumulator(
    302     RegisterInfo* info) {
    303   if (info->materialized()) {
    304     return info;
    305   }
    306 
    307   RegisterInfo* result = info->GetMaterializedEquivalentOtherThan(accumulator_);
    308   if (result == nullptr) {
    309     Materialize(info);
    310     result = info;
    311   }
    312   DCHECK(result->register_value() != accumulator_);
    313   return result;
    314 }
    315 
    316 void BytecodeRegisterOptimizer::Materialize(RegisterInfo* info) {
    317   if (!info->materialized()) {
    318     RegisterInfo* materialized = info->GetMaterializedEquivalent();
    319     OutputRegisterTransfer(materialized, info);
    320   }
    321 }
    322 
    323 void BytecodeRegisterOptimizer::AddToEquivalenceSet(
    324     RegisterInfo* set_member, RegisterInfo* non_set_member) {
    325   non_set_member->AddToEquivalenceSetOf(set_member);
    326   // Flushing is only required when two or more registers are placed
    327   // in the same equivalence set.
    328   flush_required_ = true;
    329 }
    330 
    331 void BytecodeRegisterOptimizer::RegisterTransfer(
    332     RegisterInfo* input_info, RegisterInfo* output_info,
    333     BytecodeSourceInfo source_info) {
    334   // Materialize an alternate in the equivalence set that
    335   // |output_info| is leaving.
    336   if (output_info->materialized()) {
    337     CreateMaterializedEquivalent(output_info);
    338   }
    339 
    340   // Add |output_info| to new equivalence set.
    341   if (!output_info->IsInSameEquivalenceSet(input_info)) {
    342     AddToEquivalenceSet(input_info, output_info);
    343   }
    344 
    345   bool output_is_observable =
    346       RegisterIsObservable(output_info->register_value());
    347   if (output_is_observable) {
    348     // Force store to be emitted when register is observable.
    349     output_info->set_materialized(false);
    350     RegisterInfo* materialized_info = input_info->GetMaterializedEquivalent();
    351     OutputRegisterTransfer(materialized_info, output_info, source_info);
    352   } else if (source_info.is_valid()) {
    353     // Emit a placeholder nop to maintain source position info.
    354     EmitNopForSourceInfo(source_info);
    355   }
    356 
    357   bool input_is_observable = RegisterIsObservable(input_info->register_value());
    358   if (input_is_observable) {
    359     // If input is observable by the debugger, mark all other temporaries
    360     // registers as unmaterialized so that this register is used in preference.
    361     input_info->MarkTemporariesAsUnmaterialized(temporary_base_);
    362   }
    363 }
    364 
    365 void BytecodeRegisterOptimizer::EmitNopForSourceInfo(
    366     BytecodeSourceInfo source_info) const {
    367   DCHECK(source_info.is_valid());
    368   BytecodeNode nop = BytecodeNode::Nop(source_info);
    369   next_stage_->Write(&nop);
    370 }
    371 
    372 void BytecodeRegisterOptimizer::PrepareOutputRegister(Register reg) {
    373   RegisterInfo* reg_info = GetRegisterInfo(reg);
    374   if (reg_info->materialized()) {
    375     CreateMaterializedEquivalent(reg_info);
    376   }
    377   reg_info->MoveToNewEquivalenceSet(NextEquivalenceId(), true);
    378   max_register_index_ =
    379       std::max(max_register_index_, reg_info->register_value().index());
    380 }
    381 
    382 void BytecodeRegisterOptimizer::PrepareOutputRegisterList(
    383     RegisterList reg_list) {
    384   int start_index = reg_list.first_register().index();
    385   for (int i = 0; i < reg_list.register_count(); ++i) {
    386     Register current(start_index + i);
    387     PrepareOutputRegister(current);
    388   }
    389 }
    390 
    391 Register BytecodeRegisterOptimizer::GetInputRegister(Register reg) {
    392   RegisterInfo* reg_info = GetRegisterInfo(reg);
    393   if (reg_info->materialized()) {
    394     return reg;
    395   } else {
    396     RegisterInfo* equivalent_info =
    397         GetMaterializedEquivalentNotAccumulator(reg_info);
    398     return equivalent_info->register_value();
    399   }
    400 }
    401 
    402 RegisterList BytecodeRegisterOptimizer::GetInputRegisterList(
    403     RegisterList reg_list) {
    404   if (reg_list.register_count() == 1) {
    405     // If there is only a single register, treat it as a normal input register.
    406     Register reg(GetInputRegister(reg_list.first_register()));
    407     return RegisterList(reg.index(), 1);
    408   } else {
    409     int start_index = reg_list.first_register().index();
    410     for (int i = 0; i < reg_list.register_count(); ++i) {
    411       Register current(start_index + i);
    412       RegisterInfo* input_info = GetRegisterInfo(current);
    413       Materialize(input_info);
    414     }
    415     return reg_list;
    416   }
    417 }
    418 
    419 void BytecodeRegisterOptimizer::GrowRegisterMap(Register reg) {
    420   DCHECK(RegisterIsTemporary(reg));
    421   size_t index = GetRegisterInfoTableIndex(reg);
    422   if (index >= register_info_table_.size()) {
    423     size_t new_size = index + 1;
    424     size_t old_size = register_info_table_.size();
    425     register_info_table_.resize(new_size);
    426     for (size_t i = old_size; i < new_size; ++i) {
    427       register_info_table_[i] =
    428           new (zone()) RegisterInfo(RegisterFromRegisterInfoTableIndex(i),
    429                                     NextEquivalenceId(), false, false);
    430     }
    431   }
    432 }
    433 
    434 void BytecodeRegisterOptimizer::RegisterAllocateEvent(Register reg) {
    435   GetOrCreateRegisterInfo(reg)->set_allocated(true);
    436 }
    437 
    438 void BytecodeRegisterOptimizer::RegisterListAllocateEvent(
    439     RegisterList reg_list) {
    440   if (reg_list.register_count() != 0) {
    441     int first_index = reg_list.first_register().index();
    442     GrowRegisterMap(Register(first_index + reg_list.register_count() - 1));
    443     for (int i = 0; i < reg_list.register_count(); i++) {
    444       GetRegisterInfo(Register(first_index + i))->set_allocated(true);
    445     }
    446   }
    447 }
    448 
    449 void BytecodeRegisterOptimizer::RegisterListFreeEvent(RegisterList reg_list) {
    450   int first_index = reg_list.first_register().index();
    451   for (int i = 0; i < reg_list.register_count(); i++) {
    452     GetRegisterInfo(Register(first_index + i))->set_allocated(false);
    453   }
    454 }
    455 
    456 }  // namespace interpreter
    457 }  // namespace internal
    458 }  // namespace v8
    459