1 // Copyright 2014 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/compiler/instruction.h" 6 7 #include <iomanip> 8 9 #include "src/compiler/common-operator.h" 10 #include "src/compiler/graph.h" 11 #include "src/compiler/schedule.h" 12 #include "src/compiler/state-values-utils.h" 13 #include "src/source-position.h" 14 15 namespace v8 { 16 namespace internal { 17 namespace compiler { 18 19 const RegisterConfiguration* (*GetRegConfig)() = RegisterConfiguration::Default; 20 21 FlagsCondition CommuteFlagsCondition(FlagsCondition condition) { 22 switch (condition) { 23 case kSignedLessThan: 24 return kSignedGreaterThan; 25 case kSignedGreaterThanOrEqual: 26 return kSignedLessThanOrEqual; 27 case kSignedLessThanOrEqual: 28 return kSignedGreaterThanOrEqual; 29 case kSignedGreaterThan: 30 return kSignedLessThan; 31 case kUnsignedLessThan: 32 return kUnsignedGreaterThan; 33 case kUnsignedGreaterThanOrEqual: 34 return kUnsignedLessThanOrEqual; 35 case kUnsignedLessThanOrEqual: 36 return kUnsignedGreaterThanOrEqual; 37 case kUnsignedGreaterThan: 38 return kUnsignedLessThan; 39 case kFloatLessThanOrUnordered: 40 return kFloatGreaterThanOrUnordered; 41 case kFloatGreaterThanOrEqual: 42 return kFloatLessThanOrEqual; 43 case kFloatLessThanOrEqual: 44 return kFloatGreaterThanOrEqual; 45 case kFloatGreaterThanOrUnordered: 46 return kFloatLessThanOrUnordered; 47 case kFloatLessThan: 48 return kFloatGreaterThan; 49 case kFloatGreaterThanOrEqualOrUnordered: 50 return kFloatLessThanOrEqualOrUnordered; 51 case kFloatLessThanOrEqualOrUnordered: 52 return kFloatGreaterThanOrEqualOrUnordered; 53 case kFloatGreaterThan: 54 return kFloatLessThan; 55 case kPositiveOrZero: 56 case kNegative: 57 UNREACHABLE(); 58 break; 59 case kEqual: 60 case kNotEqual: 61 case kOverflow: 62 case kNotOverflow: 63 case kUnorderedEqual: 64 case kUnorderedNotEqual: 65 return condition; 66 } 67 UNREACHABLE(); 68 } 69 70 bool InstructionOperand::InterferesWith(const InstructionOperand& other) const { 71 if (kSimpleFPAliasing || !this->IsFPLocationOperand() || 72 !other.IsFPLocationOperand()) 73 return EqualsCanonicalized(other); 74 // Aliasing is complex and both operands are fp locations. 75 const LocationOperand& loc = *LocationOperand::cast(this); 76 const LocationOperand& other_loc = LocationOperand::cast(other); 77 LocationOperand::LocationKind kind = loc.location_kind(); 78 LocationOperand::LocationKind other_kind = other_loc.location_kind(); 79 if (kind != other_kind) return false; 80 MachineRepresentation rep = loc.representation(); 81 MachineRepresentation other_rep = other_loc.representation(); 82 if (rep == other_rep) return EqualsCanonicalized(other); 83 if (kind == LocationOperand::REGISTER) { 84 // FP register-register interference. 85 return GetRegConfig()->AreAliases(rep, loc.register_code(), other_rep, 86 other_loc.register_code()); 87 } else { 88 // FP slot-slot interference. Slots of different FP reps can alias because 89 // the gap resolver may break a move into 2 or 4 equivalent smaller moves. 90 DCHECK_EQ(LocationOperand::STACK_SLOT, kind); 91 int index_hi = loc.index(); 92 int index_lo = index_hi - (1 << ElementSizeLog2Of(rep)) / kPointerSize + 1; 93 int other_index_hi = other_loc.index(); 94 int other_index_lo = 95 other_index_hi - (1 << ElementSizeLog2Of(other_rep)) / kPointerSize + 1; 96 return other_index_hi >= index_lo && index_hi >= other_index_lo; 97 } 98 return false; 99 } 100 101 bool LocationOperand::IsCompatible(LocationOperand* op) { 102 if (IsRegister() || IsStackSlot()) { 103 return op->IsRegister() || op->IsStackSlot(); 104 } else if (kSimpleFPAliasing) { 105 // A backend may choose to generate the same instruction sequence regardless 106 // of the FP representation. As a result, we can relax the compatibility and 107 // allow a Double to be moved in a Float for example. However, this is only 108 // allowed if registers do not overlap. 109 return (IsFPRegister() || IsFPStackSlot()) && 110 (op->IsFPRegister() || op->IsFPStackSlot()); 111 } else if (IsFloatRegister() || IsFloatStackSlot()) { 112 return op->IsFloatRegister() || op->IsFloatStackSlot(); 113 } else if (IsDoubleRegister() || IsDoubleStackSlot()) { 114 return op->IsDoubleRegister() || op->IsDoubleStackSlot(); 115 } else { 116 return (IsSimd128Register() || IsSimd128StackSlot()) && 117 (op->IsSimd128Register() || op->IsSimd128StackSlot()); 118 } 119 } 120 121 void InstructionOperand::Print(const RegisterConfiguration* config) const { 122 PrintableInstructionOperand wrapper; 123 wrapper.register_configuration_ = config; 124 wrapper.op_ = *this; 125 StdoutStream{} << wrapper << std::endl; 126 } 127 128 void InstructionOperand::Print() const { Print(GetRegConfig()); } 129 130 std::ostream& operator<<(std::ostream& os, 131 const PrintableInstructionOperand& printable) { 132 const InstructionOperand& op = printable.op_; 133 const RegisterConfiguration* conf = printable.register_configuration_; 134 switch (op.kind()) { 135 case InstructionOperand::UNALLOCATED: { 136 const UnallocatedOperand* unalloc = UnallocatedOperand::cast(&op); 137 os << "v" << unalloc->virtual_register(); 138 if (unalloc->basic_policy() == UnallocatedOperand::FIXED_SLOT) { 139 return os << "(=" << unalloc->fixed_slot_index() << "S)"; 140 } 141 switch (unalloc->extended_policy()) { 142 case UnallocatedOperand::NONE: 143 return os; 144 case UnallocatedOperand::FIXED_REGISTER: 145 return os << "(=" 146 << conf->GetGeneralRegisterName( 147 unalloc->fixed_register_index()) 148 << ")"; 149 case UnallocatedOperand::FIXED_FP_REGISTER: 150 return os << "(=" 151 << conf->GetDoubleRegisterName( 152 unalloc->fixed_register_index()) 153 << ")"; 154 case UnallocatedOperand::MUST_HAVE_REGISTER: 155 return os << "(R)"; 156 case UnallocatedOperand::MUST_HAVE_SLOT: 157 return os << "(S)"; 158 case UnallocatedOperand::SAME_AS_FIRST_INPUT: 159 return os << "(1)"; 160 case UnallocatedOperand::REGISTER_OR_SLOT: 161 return os << "(-)"; 162 case UnallocatedOperand::REGISTER_OR_SLOT_OR_CONSTANT: 163 return os << "(*)"; 164 } 165 } 166 case InstructionOperand::CONSTANT: 167 return os << "[constant:" << ConstantOperand::cast(op).virtual_register() 168 << "]"; 169 case InstructionOperand::IMMEDIATE: { 170 ImmediateOperand imm = ImmediateOperand::cast(op); 171 switch (imm.type()) { 172 case ImmediateOperand::INLINE: 173 return os << "#" << imm.inline_value(); 174 case ImmediateOperand::INDEXED: 175 return os << "[immediate:" << imm.indexed_value() << "]"; 176 } 177 } 178 case InstructionOperand::EXPLICIT: 179 case InstructionOperand::ALLOCATED: { 180 LocationOperand allocated = LocationOperand::cast(op); 181 if (op.IsStackSlot()) { 182 os << "[stack:" << allocated.index(); 183 } else if (op.IsFPStackSlot()) { 184 os << "[fp_stack:" << allocated.index(); 185 } else if (op.IsRegister()) { 186 os << "[" 187 << GetRegConfig()->GetGeneralOrSpecialRegisterName( 188 allocated.register_code()) 189 << "|R"; 190 } else if (op.IsDoubleRegister()) { 191 os << "[" 192 << GetRegConfig()->GetDoubleRegisterName(allocated.register_code()) 193 << "|R"; 194 } else if (op.IsFloatRegister()) { 195 os << "[" 196 << GetRegConfig()->GetFloatRegisterName(allocated.register_code()) 197 << "|R"; 198 } else { 199 DCHECK(op.IsSimd128Register()); 200 os << "[" 201 << GetRegConfig()->GetSimd128RegisterName(allocated.register_code()) 202 << "|R"; 203 } 204 if (allocated.IsExplicit()) { 205 os << "|E"; 206 } 207 switch (allocated.representation()) { 208 case MachineRepresentation::kNone: 209 os << "|-"; 210 break; 211 case MachineRepresentation::kBit: 212 os << "|b"; 213 break; 214 case MachineRepresentation::kWord8: 215 os << "|w8"; 216 break; 217 case MachineRepresentation::kWord16: 218 os << "|w16"; 219 break; 220 case MachineRepresentation::kWord32: 221 os << "|w32"; 222 break; 223 case MachineRepresentation::kWord64: 224 os << "|w64"; 225 break; 226 case MachineRepresentation::kFloat32: 227 os << "|f32"; 228 break; 229 case MachineRepresentation::kFloat64: 230 os << "|f64"; 231 break; 232 case MachineRepresentation::kSimd128: 233 os << "|s128"; 234 break; 235 case MachineRepresentation::kTaggedSigned: 236 os << "|ts"; 237 break; 238 case MachineRepresentation::kTaggedPointer: 239 os << "|tp"; 240 break; 241 case MachineRepresentation::kTagged: 242 os << "|t"; 243 break; 244 } 245 return os << "]"; 246 } 247 case InstructionOperand::INVALID: 248 return os << "(x)"; 249 } 250 UNREACHABLE(); 251 } 252 253 void MoveOperands::Print(const RegisterConfiguration* config) const { 254 StdoutStream os; 255 PrintableInstructionOperand wrapper; 256 wrapper.register_configuration_ = config; 257 wrapper.op_ = destination(); 258 os << wrapper << " = "; 259 wrapper.op_ = source(); 260 os << wrapper << std::endl; 261 } 262 263 void MoveOperands::Print() const { Print(GetRegConfig()); } 264 265 std::ostream& operator<<(std::ostream& os, 266 const PrintableMoveOperands& printable) { 267 const MoveOperands& mo = *printable.move_operands_; 268 PrintableInstructionOperand printable_op = {printable.register_configuration_, 269 mo.destination()}; 270 os << printable_op; 271 if (!mo.source().Equals(mo.destination())) { 272 printable_op.op_ = mo.source(); 273 os << " = " << printable_op; 274 } 275 return os << ";"; 276 } 277 278 279 bool ParallelMove::IsRedundant() const { 280 for (MoveOperands* move : *this) { 281 if (!move->IsRedundant()) return false; 282 } 283 return true; 284 } 285 286 void ParallelMove::PrepareInsertAfter( 287 MoveOperands* move, ZoneVector<MoveOperands*>* to_eliminate) const { 288 bool no_aliasing = 289 kSimpleFPAliasing || !move->destination().IsFPLocationOperand(); 290 MoveOperands* replacement = nullptr; 291 MoveOperands* eliminated = nullptr; 292 for (MoveOperands* curr : *this) { 293 if (curr->IsEliminated()) continue; 294 if (curr->destination().EqualsCanonicalized(move->source())) { 295 // We must replace move's source with curr's destination in order to 296 // insert it into this ParallelMove. 297 DCHECK(!replacement); 298 replacement = curr; 299 if (no_aliasing && eliminated != nullptr) break; 300 } else if (curr->destination().InterferesWith(move->destination())) { 301 // We can eliminate curr, since move overwrites at least a part of its 302 // destination, implying its value is no longer live. 303 eliminated = curr; 304 to_eliminate->push_back(curr); 305 if (no_aliasing && replacement != nullptr) break; 306 } 307 } 308 if (replacement != nullptr) move->set_source(replacement->source()); 309 } 310 311 ExplicitOperand::ExplicitOperand(LocationKind kind, MachineRepresentation rep, 312 int index) 313 : LocationOperand(EXPLICIT, kind, rep, index) { 314 DCHECK_IMPLIES(kind == REGISTER && !IsFloatingPoint(rep), 315 GetRegConfig()->IsAllocatableGeneralCode(index)); 316 DCHECK_IMPLIES(kind == REGISTER && rep == MachineRepresentation::kFloat32, 317 GetRegConfig()->IsAllocatableFloatCode(index)); 318 DCHECK_IMPLIES(kind == REGISTER && (rep == MachineRepresentation::kFloat64), 319 GetRegConfig()->IsAllocatableDoubleCode(index)); 320 } 321 322 Instruction::Instruction(InstructionCode opcode) 323 : opcode_(opcode), 324 bit_field_(OutputCountField::encode(0) | InputCountField::encode(0) | 325 TempCountField::encode(0) | IsCallField::encode(false)), 326 reference_map_(nullptr), 327 block_(nullptr) { 328 parallel_moves_[0] = nullptr; 329 parallel_moves_[1] = nullptr; 330 } 331 332 Instruction::Instruction(InstructionCode opcode, size_t output_count, 333 InstructionOperand* outputs, size_t input_count, 334 InstructionOperand* inputs, size_t temp_count, 335 InstructionOperand* temps) 336 : opcode_(opcode), 337 bit_field_(OutputCountField::encode(output_count) | 338 InputCountField::encode(input_count) | 339 TempCountField::encode(temp_count) | 340 IsCallField::encode(false)), 341 reference_map_(nullptr), 342 block_(nullptr) { 343 parallel_moves_[0] = nullptr; 344 parallel_moves_[1] = nullptr; 345 size_t offset = 0; 346 for (size_t i = 0; i < output_count; ++i) { 347 DCHECK(!outputs[i].IsInvalid()); 348 operands_[offset++] = outputs[i]; 349 } 350 for (size_t i = 0; i < input_count; ++i) { 351 DCHECK(!inputs[i].IsInvalid()); 352 operands_[offset++] = inputs[i]; 353 } 354 for (size_t i = 0; i < temp_count; ++i) { 355 DCHECK(!temps[i].IsInvalid()); 356 operands_[offset++] = temps[i]; 357 } 358 } 359 360 361 bool Instruction::AreMovesRedundant() const { 362 for (int i = Instruction::FIRST_GAP_POSITION; 363 i <= Instruction::LAST_GAP_POSITION; i++) { 364 if (parallel_moves_[i] != nullptr && !parallel_moves_[i]->IsRedundant()) { 365 return false; 366 } 367 } 368 return true; 369 } 370 371 void Instruction::Print(const RegisterConfiguration* config) const { 372 PrintableInstruction wrapper; 373 wrapper.instr_ = this; 374 wrapper.register_configuration_ = config; 375 StdoutStream{} << wrapper << std::endl; 376 } 377 378 void Instruction::Print() const { Print(GetRegConfig()); } 379 380 std::ostream& operator<<(std::ostream& os, 381 const PrintableParallelMove& printable) { 382 const ParallelMove& pm = *printable.parallel_move_; 383 bool first = true; 384 for (MoveOperands* move : pm) { 385 if (move->IsEliminated()) continue; 386 if (!first) os << " "; 387 first = false; 388 PrintableMoveOperands pmo = {printable.register_configuration_, move}; 389 os << pmo; 390 } 391 return os; 392 } 393 394 395 void ReferenceMap::RecordReference(const AllocatedOperand& op) { 396 // Do not record arguments as pointers. 397 if (op.IsStackSlot() && LocationOperand::cast(op).index() < 0) return; 398 DCHECK(!op.IsFPRegister() && !op.IsFPStackSlot()); 399 reference_operands_.push_back(op); 400 } 401 402 403 std::ostream& operator<<(std::ostream& os, const ReferenceMap& pm) { 404 os << "{"; 405 bool first = true; 406 PrintableInstructionOperand poi = {GetRegConfig(), InstructionOperand()}; 407 for (const InstructionOperand& op : pm.reference_operands_) { 408 if (!first) { 409 os << ";"; 410 } else { 411 first = false; 412 } 413 poi.op_ = op; 414 os << poi; 415 } 416 return os << "}"; 417 } 418 419 420 std::ostream& operator<<(std::ostream& os, const ArchOpcode& ao) { 421 switch (ao) { 422 #define CASE(Name) \ 423 case k##Name: \ 424 return os << #Name; 425 ARCH_OPCODE_LIST(CASE) 426 #undef CASE 427 } 428 UNREACHABLE(); 429 } 430 431 432 std::ostream& operator<<(std::ostream& os, const AddressingMode& am) { 433 switch (am) { 434 case kMode_None: 435 return os; 436 #define CASE(Name) \ 437 case kMode_##Name: \ 438 return os << #Name; 439 TARGET_ADDRESSING_MODE_LIST(CASE) 440 #undef CASE 441 } 442 UNREACHABLE(); 443 } 444 445 446 std::ostream& operator<<(std::ostream& os, const FlagsMode& fm) { 447 switch (fm) { 448 case kFlags_none: 449 return os; 450 case kFlags_branch: 451 return os << "branch"; 452 case kFlags_branch_and_poison: 453 return os << "branch_and_poison"; 454 case kFlags_deoptimize: 455 return os << "deoptimize"; 456 case kFlags_deoptimize_and_poison: 457 return os << "deoptimize_and_poison"; 458 case kFlags_set: 459 return os << "set"; 460 case kFlags_trap: 461 return os << "trap"; 462 } 463 UNREACHABLE(); 464 } 465 466 467 std::ostream& operator<<(std::ostream& os, const FlagsCondition& fc) { 468 switch (fc) { 469 case kEqual: 470 return os << "equal"; 471 case kNotEqual: 472 return os << "not equal"; 473 case kSignedLessThan: 474 return os << "signed less than"; 475 case kSignedGreaterThanOrEqual: 476 return os << "signed greater than or equal"; 477 case kSignedLessThanOrEqual: 478 return os << "signed less than or equal"; 479 case kSignedGreaterThan: 480 return os << "signed greater than"; 481 case kUnsignedLessThan: 482 return os << "unsigned less than"; 483 case kUnsignedGreaterThanOrEqual: 484 return os << "unsigned greater than or equal"; 485 case kUnsignedLessThanOrEqual: 486 return os << "unsigned less than or equal"; 487 case kUnsignedGreaterThan: 488 return os << "unsigned greater than"; 489 case kFloatLessThanOrUnordered: 490 return os << "less than or unordered (FP)"; 491 case kFloatGreaterThanOrEqual: 492 return os << "greater than or equal (FP)"; 493 case kFloatLessThanOrEqual: 494 return os << "less than or equal (FP)"; 495 case kFloatGreaterThanOrUnordered: 496 return os << "greater than or unordered (FP)"; 497 case kFloatLessThan: 498 return os << "less than (FP)"; 499 case kFloatGreaterThanOrEqualOrUnordered: 500 return os << "greater than, equal or unordered (FP)"; 501 case kFloatLessThanOrEqualOrUnordered: 502 return os << "less than, equal or unordered (FP)"; 503 case kFloatGreaterThan: 504 return os << "greater than (FP)"; 505 case kUnorderedEqual: 506 return os << "unordered equal"; 507 case kUnorderedNotEqual: 508 return os << "unordered not equal"; 509 case kOverflow: 510 return os << "overflow"; 511 case kNotOverflow: 512 return os << "not overflow"; 513 case kPositiveOrZero: 514 return os << "positive or zero"; 515 case kNegative: 516 return os << "negative"; 517 } 518 UNREACHABLE(); 519 } 520 521 522 std::ostream& operator<<(std::ostream& os, 523 const PrintableInstruction& printable) { 524 const Instruction& instr = *printable.instr_; 525 PrintableInstructionOperand printable_op = {printable.register_configuration_, 526 InstructionOperand()}; 527 os << "gap "; 528 for (int i = Instruction::FIRST_GAP_POSITION; 529 i <= Instruction::LAST_GAP_POSITION; i++) { 530 os << "("; 531 if (instr.parallel_moves()[i] != nullptr) { 532 PrintableParallelMove ppm = {printable.register_configuration_, 533 instr.parallel_moves()[i]}; 534 os << ppm; 535 } 536 os << ") "; 537 } 538 os << "\n "; 539 540 if (instr.OutputCount() > 1) os << "("; 541 for (size_t i = 0; i < instr.OutputCount(); i++) { 542 if (i > 0) os << ", "; 543 printable_op.op_ = *instr.OutputAt(i); 544 os << printable_op; 545 } 546 547 if (instr.OutputCount() > 1) os << ") = "; 548 if (instr.OutputCount() == 1) os << " = "; 549 550 os << ArchOpcodeField::decode(instr.opcode()); 551 AddressingMode am = AddressingModeField::decode(instr.opcode()); 552 if (am != kMode_None) { 553 os << " : " << AddressingModeField::decode(instr.opcode()); 554 } 555 FlagsMode fm = FlagsModeField::decode(instr.opcode()); 556 if (fm != kFlags_none) { 557 os << " && " << fm << " if " << FlagsConditionField::decode(instr.opcode()); 558 } 559 if (instr.InputCount() > 0) { 560 for (size_t i = 0; i < instr.InputCount(); i++) { 561 printable_op.op_ = *instr.InputAt(i); 562 os << " " << printable_op; 563 } 564 } 565 return os; 566 } 567 568 569 Constant::Constant(int32_t v) : type_(kInt32), value_(v) {} 570 571 Constant::Constant(RelocatablePtrConstantInfo info) { 572 if (info.type() == RelocatablePtrConstantInfo::kInt32) { 573 type_ = kInt32; 574 } else if (info.type() == RelocatablePtrConstantInfo::kInt64) { 575 type_ = kInt64; 576 } else { 577 UNREACHABLE(); 578 } 579 value_ = info.value(); 580 rmode_ = info.rmode(); 581 } 582 583 Handle<HeapObject> Constant::ToHeapObject() const { 584 DCHECK_EQ(kHeapObject, type()); 585 Handle<HeapObject> value( 586 bit_cast<HeapObject**>(static_cast<intptr_t>(value_))); 587 return value; 588 } 589 590 Handle<Code> Constant::ToCode() const { 591 DCHECK_EQ(kHeapObject, type()); 592 Handle<Code> value(bit_cast<Code**>(static_cast<intptr_t>(value_))); 593 return value; 594 } 595 596 std::ostream& operator<<(std::ostream& os, const Constant& constant) { 597 switch (constant.type()) { 598 case Constant::kInt32: 599 return os << constant.ToInt32(); 600 case Constant::kInt64: 601 return os << constant.ToInt64() << "l"; 602 case Constant::kFloat32: 603 return os << constant.ToFloat32() << "f"; 604 case Constant::kFloat64: 605 return os << constant.ToFloat64().value(); 606 case Constant::kExternalReference: 607 return os << constant.ToExternalReference().address(); 608 case Constant::kHeapObject: 609 return os << Brief(*constant.ToHeapObject()); 610 case Constant::kRpoNumber: 611 return os << "RPO" << constant.ToRpoNumber().ToInt(); 612 } 613 UNREACHABLE(); 614 } 615 616 617 PhiInstruction::PhiInstruction(Zone* zone, int virtual_register, 618 size_t input_count) 619 : virtual_register_(virtual_register), 620 output_(UnallocatedOperand(UnallocatedOperand::NONE, virtual_register)), 621 operands_(input_count, InstructionOperand::kInvalidVirtualRegister, 622 zone) {} 623 624 625 void PhiInstruction::SetInput(size_t offset, int virtual_register) { 626 DCHECK_EQ(InstructionOperand::kInvalidVirtualRegister, operands_[offset]); 627 operands_[offset] = virtual_register; 628 } 629 630 void PhiInstruction::RenameInput(size_t offset, int virtual_register) { 631 DCHECK_NE(InstructionOperand::kInvalidVirtualRegister, operands_[offset]); 632 operands_[offset] = virtual_register; 633 } 634 635 InstructionBlock::InstructionBlock(Zone* zone, RpoNumber rpo_number, 636 RpoNumber loop_header, RpoNumber loop_end, 637 bool deferred, bool handler) 638 : successors_(zone), 639 predecessors_(zone), 640 phis_(zone), 641 ao_number_(rpo_number), 642 rpo_number_(rpo_number), 643 loop_header_(loop_header), 644 loop_end_(loop_end), 645 code_start_(-1), 646 code_end_(-1), 647 deferred_(deferred), 648 handler_(handler), 649 needs_frame_(false), 650 must_construct_frame_(false), 651 must_deconstruct_frame_(false) {} 652 653 size_t InstructionBlock::PredecessorIndexOf(RpoNumber rpo_number) const { 654 size_t j = 0; 655 for (InstructionBlock::Predecessors::const_iterator i = predecessors_.begin(); 656 i != predecessors_.end(); ++i, ++j) { 657 if (*i == rpo_number) break; 658 } 659 return j; 660 } 661 662 663 static RpoNumber GetRpo(const BasicBlock* block) { 664 if (block == nullptr) return RpoNumber::Invalid(); 665 return RpoNumber::FromInt(block->rpo_number()); 666 } 667 668 669 static RpoNumber GetLoopEndRpo(const BasicBlock* block) { 670 if (!block->IsLoopHeader()) return RpoNumber::Invalid(); 671 return RpoNumber::FromInt(block->loop_end()->rpo_number()); 672 } 673 674 675 static InstructionBlock* InstructionBlockFor(Zone* zone, 676 const BasicBlock* block) { 677 bool is_handler = 678 !block->empty() && block->front()->opcode() == IrOpcode::kIfException; 679 InstructionBlock* instr_block = new (zone) 680 InstructionBlock(zone, GetRpo(block), GetRpo(block->loop_header()), 681 GetLoopEndRpo(block), block->deferred(), is_handler); 682 // Map successors and precessors 683 instr_block->successors().reserve(block->SuccessorCount()); 684 for (BasicBlock* successor : block->successors()) { 685 instr_block->successors().push_back(GetRpo(successor)); 686 } 687 instr_block->predecessors().reserve(block->PredecessorCount()); 688 for (BasicBlock* predecessor : block->predecessors()) { 689 instr_block->predecessors().push_back(GetRpo(predecessor)); 690 } 691 return instr_block; 692 } 693 694 std::ostream& operator<<(std::ostream& os, 695 const PrintableInstructionBlock& printable_block) { 696 const InstructionBlock* block = printable_block.block_; 697 const RegisterConfiguration* config = printable_block.register_configuration_; 698 const InstructionSequence* code = printable_block.code_; 699 700 os << "B" << block->rpo_number(); 701 os << ": AO#" << block->ao_number(); 702 if (block->IsDeferred()) os << " (deferred)"; 703 if (!block->needs_frame()) os << " (no frame)"; 704 if (block->must_construct_frame()) os << " (construct frame)"; 705 if (block->must_deconstruct_frame()) os << " (deconstruct frame)"; 706 if (block->IsLoopHeader()) { 707 os << " loop blocks: [" << block->rpo_number() << ", " << block->loop_end() 708 << ")"; 709 } 710 os << " instructions: [" << block->code_start() << ", " << block->code_end() 711 << ")" << std::endl 712 << " predecessors:"; 713 714 for (RpoNumber pred : block->predecessors()) { 715 os << " B" << pred.ToInt(); 716 } 717 os << std::endl; 718 719 for (const PhiInstruction* phi : block->phis()) { 720 PrintableInstructionOperand printable_op = {config, phi->output()}; 721 os << " phi: " << printable_op << " ="; 722 for (int input : phi->operands()) { 723 os << " v" << input; 724 } 725 os << std::endl; 726 } 727 728 PrintableInstruction printable_instr; 729 printable_instr.register_configuration_ = config; 730 for (int j = block->first_instruction_index(); 731 j <= block->last_instruction_index(); j++) { 732 printable_instr.instr_ = code->InstructionAt(j); 733 os << " " << std::setw(5) << j << ": " << printable_instr << std::endl; 734 } 735 736 os << " successors:"; 737 for (RpoNumber succ : block->successors()) { 738 os << " B" << succ.ToInt(); 739 } 740 os << std::endl; 741 return os; 742 } 743 744 InstructionBlocks* InstructionSequence::InstructionBlocksFor( 745 Zone* zone, const Schedule* schedule) { 746 InstructionBlocks* blocks = zone->NewArray<InstructionBlocks>(1); 747 new (blocks) InstructionBlocks( 748 static_cast<int>(schedule->rpo_order()->size()), nullptr, zone); 749 size_t rpo_number = 0; 750 for (BasicBlockVector::const_iterator it = schedule->rpo_order()->begin(); 751 it != schedule->rpo_order()->end(); ++it, ++rpo_number) { 752 DCHECK(!(*blocks)[rpo_number]); 753 DCHECK(GetRpo(*it).ToSize() == rpo_number); 754 (*blocks)[rpo_number] = InstructionBlockFor(zone, *it); 755 } 756 ComputeAssemblyOrder(blocks); 757 return blocks; 758 } 759 760 void InstructionSequence::ValidateEdgeSplitForm() const { 761 // Validate blocks are in edge-split form: no block with multiple successors 762 // has an edge to a block (== a successor) with more than one predecessors. 763 for (const InstructionBlock* block : instruction_blocks()) { 764 if (block->SuccessorCount() > 1) { 765 for (const RpoNumber& successor_id : block->successors()) { 766 const InstructionBlock* successor = InstructionBlockAt(successor_id); 767 // Expect precisely one predecessor: "block". 768 CHECK(successor->PredecessorCount() == 1 && 769 successor->predecessors()[0] == block->rpo_number()); 770 } 771 } 772 } 773 } 774 775 void InstructionSequence::ValidateDeferredBlockExitPaths() const { 776 // A deferred block with more than one successor must have all its successors 777 // deferred. 778 for (const InstructionBlock* block : instruction_blocks()) { 779 if (!block->IsDeferred() || block->SuccessorCount() <= 1) continue; 780 for (RpoNumber successor_id : block->successors()) { 781 CHECK(InstructionBlockAt(successor_id)->IsDeferred()); 782 } 783 } 784 } 785 786 void InstructionSequence::ValidateDeferredBlockEntryPaths() const { 787 // If a deferred block has multiple predecessors, they have to 788 // all be deferred. Otherwise, we can run into a situation where a range 789 // that spills only in deferred blocks inserts its spill in the block, but 790 // other ranges need moves inserted by ResolveControlFlow in the predecessors, 791 // which may clobber the register of this range. 792 for (const InstructionBlock* block : instruction_blocks()) { 793 if (!block->IsDeferred() || block->PredecessorCount() <= 1) continue; 794 for (RpoNumber predecessor_id : block->predecessors()) { 795 CHECK(InstructionBlockAt(predecessor_id)->IsDeferred()); 796 } 797 } 798 } 799 800 void InstructionSequence::ValidateSSA() const { 801 // TODO(mtrofin): We could use a local zone here instead. 802 BitVector definitions(VirtualRegisterCount(), zone()); 803 for (const Instruction* instruction : *this) { 804 for (size_t i = 0; i < instruction->OutputCount(); ++i) { 805 const InstructionOperand* output = instruction->OutputAt(i); 806 int vreg = (output->IsConstant()) 807 ? ConstantOperand::cast(output)->virtual_register() 808 : UnallocatedOperand::cast(output)->virtual_register(); 809 CHECK(!definitions.Contains(vreg)); 810 definitions.Add(vreg); 811 } 812 } 813 } 814 815 void InstructionSequence::ComputeAssemblyOrder(InstructionBlocks* blocks) { 816 int ao = 0; 817 for (InstructionBlock* const block : *blocks) { 818 if (!block->IsDeferred()) { 819 block->set_ao_number(RpoNumber::FromInt(ao++)); 820 } 821 } 822 for (InstructionBlock* const block : *blocks) { 823 if (block->IsDeferred()) { 824 block->set_ao_number(RpoNumber::FromInt(ao++)); 825 } 826 } 827 } 828 829 InstructionSequence::InstructionSequence(Isolate* isolate, 830 Zone* instruction_zone, 831 InstructionBlocks* instruction_blocks) 832 : isolate_(isolate), 833 zone_(instruction_zone), 834 instruction_blocks_(instruction_blocks), 835 source_positions_(zone()), 836 constants_(ConstantMap::key_compare(), 837 ConstantMap::allocator_type(zone())), 838 immediates_(zone()), 839 instructions_(zone()), 840 next_virtual_register_(0), 841 reference_maps_(zone()), 842 representations_(zone()), 843 representation_mask_(0), 844 deoptimization_entries_(zone()), 845 current_block_(nullptr) {} 846 847 int InstructionSequence::NextVirtualRegister() { 848 int virtual_register = next_virtual_register_++; 849 CHECK_NE(virtual_register, InstructionOperand::kInvalidVirtualRegister); 850 return virtual_register; 851 } 852 853 854 Instruction* InstructionSequence::GetBlockStart(RpoNumber rpo) const { 855 const InstructionBlock* block = InstructionBlockAt(rpo); 856 return InstructionAt(block->code_start()); 857 } 858 859 860 void InstructionSequence::StartBlock(RpoNumber rpo) { 861 DCHECK_NULL(current_block_); 862 current_block_ = InstructionBlockAt(rpo); 863 int code_start = static_cast<int>(instructions_.size()); 864 current_block_->set_code_start(code_start); 865 } 866 867 868 void InstructionSequence::EndBlock(RpoNumber rpo) { 869 int end = static_cast<int>(instructions_.size()); 870 DCHECK_EQ(current_block_->rpo_number(), rpo); 871 CHECK(current_block_->code_start() >= 0 && 872 current_block_->code_start() < end); 873 current_block_->set_code_end(end); 874 current_block_ = nullptr; 875 } 876 877 878 int InstructionSequence::AddInstruction(Instruction* instr) { 879 DCHECK_NOT_NULL(current_block_); 880 int index = static_cast<int>(instructions_.size()); 881 instr->set_block(current_block_); 882 instructions_.push_back(instr); 883 if (instr->NeedsReferenceMap()) { 884 DCHECK_NULL(instr->reference_map()); 885 ReferenceMap* reference_map = new (zone()) ReferenceMap(zone()); 886 reference_map->set_instruction_position(index); 887 instr->set_reference_map(reference_map); 888 reference_maps_.push_back(reference_map); 889 } 890 return index; 891 } 892 893 894 InstructionBlock* InstructionSequence::GetInstructionBlock( 895 int instruction_index) const { 896 return instructions()[instruction_index]->block(); 897 } 898 899 900 static MachineRepresentation FilterRepresentation(MachineRepresentation rep) { 901 switch (rep) { 902 case MachineRepresentation::kBit: 903 case MachineRepresentation::kWord8: 904 case MachineRepresentation::kWord16: 905 return InstructionSequence::DefaultRepresentation(); 906 case MachineRepresentation::kWord32: 907 case MachineRepresentation::kWord64: 908 case MachineRepresentation::kTaggedSigned: 909 case MachineRepresentation::kTaggedPointer: 910 case MachineRepresentation::kTagged: 911 case MachineRepresentation::kFloat32: 912 case MachineRepresentation::kFloat64: 913 case MachineRepresentation::kSimd128: 914 return rep; 915 case MachineRepresentation::kNone: 916 break; 917 } 918 919 UNREACHABLE(); 920 } 921 922 923 MachineRepresentation InstructionSequence::GetRepresentation( 924 int virtual_register) const { 925 DCHECK_LE(0, virtual_register); 926 DCHECK_LT(virtual_register, VirtualRegisterCount()); 927 if (virtual_register >= static_cast<int>(representations_.size())) { 928 return DefaultRepresentation(); 929 } 930 return representations_[virtual_register]; 931 } 932 933 934 void InstructionSequence::MarkAsRepresentation(MachineRepresentation rep, 935 int virtual_register) { 936 DCHECK_LE(0, virtual_register); 937 DCHECK_LT(virtual_register, VirtualRegisterCount()); 938 if (virtual_register >= static_cast<int>(representations_.size())) { 939 representations_.resize(VirtualRegisterCount(), DefaultRepresentation()); 940 } 941 rep = FilterRepresentation(rep); 942 DCHECK_IMPLIES(representations_[virtual_register] != rep, 943 representations_[virtual_register] == DefaultRepresentation()); 944 representations_[virtual_register] = rep; 945 representation_mask_ |= 1 << static_cast<int>(rep); 946 } 947 948 int InstructionSequence::AddDeoptimizationEntry( 949 FrameStateDescriptor* descriptor, DeoptimizeKind kind, 950 DeoptimizeReason reason, VectorSlotPair const& feedback) { 951 int deoptimization_id = static_cast<int>(deoptimization_entries_.size()); 952 deoptimization_entries_.push_back( 953 DeoptimizationEntry(descriptor, kind, reason, feedback)); 954 return deoptimization_id; 955 } 956 957 DeoptimizationEntry const& InstructionSequence::GetDeoptimizationEntry( 958 int state_id) { 959 return deoptimization_entries_[state_id]; 960 } 961 962 963 RpoNumber InstructionSequence::InputRpo(Instruction* instr, size_t index) { 964 InstructionOperand* operand = instr->InputAt(index); 965 Constant constant = 966 operand->IsImmediate() 967 ? GetImmediate(ImmediateOperand::cast(operand)) 968 : GetConstant(ConstantOperand::cast(operand)->virtual_register()); 969 return constant.ToRpoNumber(); 970 } 971 972 973 bool InstructionSequence::GetSourcePosition(const Instruction* instr, 974 SourcePosition* result) const { 975 auto it = source_positions_.find(instr); 976 if (it == source_positions_.end()) return false; 977 *result = it->second; 978 return true; 979 } 980 981 982 void InstructionSequence::SetSourcePosition(const Instruction* instr, 983 SourcePosition value) { 984 source_positions_.insert(std::make_pair(instr, value)); 985 } 986 987 void InstructionSequence::Print(const RegisterConfiguration* config) const { 988 PrintableInstructionSequence wrapper; 989 wrapper.register_configuration_ = config; 990 wrapper.sequence_ = this; 991 StdoutStream{} << wrapper << std::endl; 992 } 993 994 void InstructionSequence::Print() const { Print(GetRegConfig()); } 995 996 void InstructionSequence::PrintBlock(const RegisterConfiguration* config, 997 int block_id) const { 998 RpoNumber rpo = RpoNumber::FromInt(block_id); 999 const InstructionBlock* block = InstructionBlockAt(rpo); 1000 CHECK(block->rpo_number() == rpo); 1001 PrintableInstructionBlock printable_block = {config, block, this}; 1002 StdoutStream{} << printable_block << std::endl; 1003 } 1004 1005 void InstructionSequence::PrintBlock(int block_id) const { 1006 PrintBlock(GetRegConfig(), block_id); 1007 } 1008 1009 const RegisterConfiguration* 1010 InstructionSequence::registerConfigurationForTesting_ = nullptr; 1011 1012 const RegisterConfiguration* 1013 InstructionSequence::RegisterConfigurationForTesting() { 1014 DCHECK_NOT_NULL(registerConfigurationForTesting_); 1015 return registerConfigurationForTesting_; 1016 } 1017 1018 void InstructionSequence::SetRegisterConfigurationForTesting( 1019 const RegisterConfiguration* regConfig) { 1020 registerConfigurationForTesting_ = regConfig; 1021 GetRegConfig = InstructionSequence::RegisterConfigurationForTesting; 1022 } 1023 1024 FrameStateDescriptor::FrameStateDescriptor( 1025 Zone* zone, FrameStateType type, BailoutId bailout_id, 1026 OutputFrameStateCombine state_combine, size_t parameters_count, 1027 size_t locals_count, size_t stack_count, 1028 MaybeHandle<SharedFunctionInfo> shared_info, 1029 FrameStateDescriptor* outer_state) 1030 : type_(type), 1031 bailout_id_(bailout_id), 1032 frame_state_combine_(state_combine), 1033 parameters_count_(parameters_count), 1034 locals_count_(locals_count), 1035 stack_count_(stack_count), 1036 values_(zone), 1037 shared_info_(shared_info), 1038 outer_state_(outer_state) {} 1039 1040 size_t FrameStateDescriptor::GetSize() const { 1041 return 1 + parameters_count() + locals_count() + stack_count() + 1042 (HasContext() ? 1 : 0); 1043 } 1044 1045 1046 size_t FrameStateDescriptor::GetTotalSize() const { 1047 size_t total_size = 0; 1048 for (const FrameStateDescriptor* iter = this; iter != nullptr; 1049 iter = iter->outer_state_) { 1050 total_size += iter->GetSize(); 1051 } 1052 return total_size; 1053 } 1054 1055 1056 size_t FrameStateDescriptor::GetFrameCount() const { 1057 size_t count = 0; 1058 for (const FrameStateDescriptor* iter = this; iter != nullptr; 1059 iter = iter->outer_state_) { 1060 ++count; 1061 } 1062 return count; 1063 } 1064 1065 1066 size_t FrameStateDescriptor::GetJSFrameCount() const { 1067 size_t count = 0; 1068 for (const FrameStateDescriptor* iter = this; iter != nullptr; 1069 iter = iter->outer_state_) { 1070 if (FrameStateFunctionInfo::IsJSFunctionType(iter->type_)) { 1071 ++count; 1072 } 1073 } 1074 return count; 1075 } 1076 1077 1078 std::ostream& operator<<(std::ostream& os, const RpoNumber& rpo) { 1079 return os << rpo.ToSize(); 1080 } 1081 1082 1083 std::ostream& operator<<(std::ostream& os, 1084 const PrintableInstructionSequence& printable) { 1085 const InstructionSequence& code = *printable.sequence_; 1086 for (size_t i = 0; i < code.immediates_.size(); ++i) { 1087 Constant constant = code.immediates_[i]; 1088 os << "IMM#" << i << ": " << constant << "\n"; 1089 } 1090 int i = 0; 1091 for (ConstantMap::const_iterator it = code.constants_.begin(); 1092 it != code.constants_.end(); ++i, ++it) { 1093 os << "CST#" << i << ": v" << it->first << " = " << it->second << "\n"; 1094 } 1095 PrintableInstructionBlock printable_block = { 1096 printable.register_configuration_, nullptr, printable.sequence_}; 1097 for (int i = 0; i < code.InstructionBlockCount(); i++) { 1098 printable_block.block_ = code.InstructionBlockAt(RpoNumber::FromInt(i)); 1099 os << printable_block; 1100 } 1101 return os; 1102 } 1103 1104 } // namespace compiler 1105 } // namespace internal 1106 } // namespace v8 1107