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