| // Copyright 2014 the V8 project authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. |
| |
| #include "src/compiler/backend/instruction.h" |
| |
| #include <cstddef> |
| #include <iomanip> |
| |
| #include "src/codegen/interface-descriptors.h" |
| #include "src/codegen/register-configuration.h" |
| #include "src/codegen/source-position.h" |
| #include "src/compiler/common-operator.h" |
| #include "src/compiler/graph.h" |
| #include "src/compiler/node.h" |
| #include "src/compiler/schedule.h" |
| #include "src/execution/frames.h" |
| #include "src/utils/ostreams.h" |
| |
| namespace v8 { |
| namespace internal { |
| namespace compiler { |
| |
| const RegisterConfiguration* (*GetRegConfig)() = RegisterConfiguration::Default; |
| |
| FlagsCondition CommuteFlagsCondition(FlagsCondition condition) { |
| switch (condition) { |
| case kSignedLessThan: |
| return kSignedGreaterThan; |
| case kSignedGreaterThanOrEqual: |
| return kSignedLessThanOrEqual; |
| case kSignedLessThanOrEqual: |
| return kSignedGreaterThanOrEqual; |
| case kSignedGreaterThan: |
| return kSignedLessThan; |
| case kUnsignedLessThan: |
| return kUnsignedGreaterThan; |
| case kUnsignedGreaterThanOrEqual: |
| return kUnsignedLessThanOrEqual; |
| case kUnsignedLessThanOrEqual: |
| return kUnsignedGreaterThanOrEqual; |
| case kUnsignedGreaterThan: |
| return kUnsignedLessThan; |
| case kFloatLessThanOrUnordered: |
| return kFloatGreaterThanOrUnordered; |
| case kFloatGreaterThanOrEqual: |
| return kFloatLessThanOrEqual; |
| case kFloatLessThanOrEqual: |
| return kFloatGreaterThanOrEqual; |
| case kFloatGreaterThanOrUnordered: |
| return kFloatLessThanOrUnordered; |
| case kFloatLessThan: |
| return kFloatGreaterThan; |
| case kFloatGreaterThanOrEqualOrUnordered: |
| return kFloatLessThanOrEqualOrUnordered; |
| case kFloatLessThanOrEqualOrUnordered: |
| return kFloatGreaterThanOrEqualOrUnordered; |
| case kFloatGreaterThan: |
| return kFloatLessThan; |
| case kPositiveOrZero: |
| case kNegative: |
| UNREACHABLE(); |
| case kEqual: |
| case kNotEqual: |
| case kOverflow: |
| case kNotOverflow: |
| case kUnorderedEqual: |
| case kUnorderedNotEqual: |
| return condition; |
| } |
| UNREACHABLE(); |
| } |
| |
| bool InstructionOperand::InterferesWith(const InstructionOperand& other) const { |
| if (kSimpleFPAliasing || !this->IsFPLocationOperand() || |
| !other.IsFPLocationOperand()) |
| return EqualsCanonicalized(other); |
| // Aliasing is complex and both operands are fp locations. |
| const LocationOperand& loc = *LocationOperand::cast(this); |
| const LocationOperand& other_loc = LocationOperand::cast(other); |
| LocationOperand::LocationKind kind = loc.location_kind(); |
| LocationOperand::LocationKind other_kind = other_loc.location_kind(); |
| if (kind != other_kind) return false; |
| MachineRepresentation rep = loc.representation(); |
| MachineRepresentation other_rep = other_loc.representation(); |
| if (rep == other_rep) return EqualsCanonicalized(other); |
| if (kind == LocationOperand::REGISTER) { |
| // FP register-register interference. |
| return GetRegConfig()->AreAliases(rep, loc.register_code(), other_rep, |
| other_loc.register_code()); |
| } else { |
| // FP slot-slot interference. Slots of different FP reps can alias because |
| // the gap resolver may break a move into 2 or 4 equivalent smaller moves. |
| DCHECK_EQ(LocationOperand::STACK_SLOT, kind); |
| int index_hi = loc.index(); |
| int index_lo = |
| index_hi - (1 << ElementSizeLog2Of(rep)) / kSystemPointerSize + 1; |
| int other_index_hi = other_loc.index(); |
| int other_index_lo = |
| other_index_hi - |
| (1 << ElementSizeLog2Of(other_rep)) / kSystemPointerSize + 1; |
| return other_index_hi >= index_lo && index_hi >= other_index_lo; |
| } |
| return false; |
| } |
| |
| bool LocationOperand::IsCompatible(LocationOperand* op) { |
| if (IsRegister() || IsStackSlot()) { |
| return op->IsRegister() || op->IsStackSlot(); |
| } else if (kSimpleFPAliasing) { |
| // A backend may choose to generate the same instruction sequence regardless |
| // of the FP representation. As a result, we can relax the compatibility and |
| // allow a Double to be moved in a Float for example. However, this is only |
| // allowed if registers do not overlap. |
| return (IsFPRegister() || IsFPStackSlot()) && |
| (op->IsFPRegister() || op->IsFPStackSlot()); |
| } else if (IsFloatRegister() || IsFloatStackSlot()) { |
| return op->IsFloatRegister() || op->IsFloatStackSlot(); |
| } else if (IsDoubleRegister() || IsDoubleStackSlot()) { |
| return op->IsDoubleRegister() || op->IsDoubleStackSlot(); |
| } else { |
| return (IsSimd128Register() || IsSimd128StackSlot()) && |
| (op->IsSimd128Register() || op->IsSimd128StackSlot()); |
| } |
| } |
| |
| void InstructionOperand::Print() const { StdoutStream{} << *this << std::endl; } |
| |
| std::ostream& operator<<(std::ostream& os, const InstructionOperand& op) { |
| switch (op.kind()) { |
| case InstructionOperand::UNALLOCATED: { |
| const UnallocatedOperand* unalloc = UnallocatedOperand::cast(&op); |
| os << "v" << unalloc->virtual_register(); |
| if (unalloc->basic_policy() == UnallocatedOperand::FIXED_SLOT) { |
| return os << "(=" << unalloc->fixed_slot_index() << "S)"; |
| } |
| switch (unalloc->extended_policy()) { |
| case UnallocatedOperand::NONE: |
| return os; |
| case UnallocatedOperand::FIXED_REGISTER: |
| return os << "(=" |
| << Register::from_code(unalloc->fixed_register_index()) |
| << ")"; |
| case UnallocatedOperand::FIXED_FP_REGISTER: |
| return os << "(=" |
| << DoubleRegister::from_code( |
| unalloc->fixed_register_index()) |
| << ")"; |
| case UnallocatedOperand::MUST_HAVE_REGISTER: |
| return os << "(R)"; |
| case UnallocatedOperand::MUST_HAVE_SLOT: |
| return os << "(S)"; |
| case UnallocatedOperand::SAME_AS_FIRST_INPUT: |
| return os << "(1)"; |
| case UnallocatedOperand::REGISTER_OR_SLOT: |
| return os << "(-)"; |
| case UnallocatedOperand::REGISTER_OR_SLOT_OR_CONSTANT: |
| return os << "(*)"; |
| } |
| } |
| case InstructionOperand::CONSTANT: |
| return os << "[constant:" << ConstantOperand::cast(op).virtual_register() |
| << "]"; |
| case InstructionOperand::IMMEDIATE: { |
| ImmediateOperand imm = ImmediateOperand::cast(op); |
| switch (imm.type()) { |
| case ImmediateOperand::INLINE: |
| return os << "#" << imm.inline_value(); |
| case ImmediateOperand::INDEXED: |
| return os << "[immediate:" << imm.indexed_value() << "]"; |
| } |
| } |
| case InstructionOperand::PENDING: |
| return os << "[pending: " << PendingOperand::cast(op).next() << "]"; |
| case InstructionOperand::ALLOCATED: { |
| LocationOperand allocated = LocationOperand::cast(op); |
| if (op.IsStackSlot()) { |
| os << "[stack:" << allocated.index(); |
| } else if (op.IsFPStackSlot()) { |
| os << "[fp_stack:" << allocated.index(); |
| } else if (op.IsRegister()) { |
| const char* name = |
| allocated.register_code() < Register::kNumRegisters |
| ? RegisterName(Register::from_code(allocated.register_code())) |
| : Register::GetSpecialRegisterName(allocated.register_code()); |
| os << "[" << name << "|R"; |
| } else if (op.IsDoubleRegister()) { |
| os << "[" << DoubleRegister::from_code(allocated.register_code()) |
| << "|R"; |
| } else if (op.IsFloatRegister()) { |
| os << "[" << FloatRegister::from_code(allocated.register_code()) |
| << "|R"; |
| } else { |
| DCHECK(op.IsSimd128Register()); |
| os << "[" << Simd128Register::from_code(allocated.register_code()) |
| << "|R"; |
| } |
| switch (allocated.representation()) { |
| case MachineRepresentation::kNone: |
| os << "|-"; |
| break; |
| case MachineRepresentation::kBit: |
| os << "|b"; |
| break; |
| case MachineRepresentation::kWord8: |
| os << "|w8"; |
| break; |
| case MachineRepresentation::kWord16: |
| os << "|w16"; |
| break; |
| case MachineRepresentation::kWord32: |
| os << "|w32"; |
| break; |
| case MachineRepresentation::kWord64: |
| os << "|w64"; |
| break; |
| case MachineRepresentation::kFloat32: |
| os << "|f32"; |
| break; |
| case MachineRepresentation::kFloat64: |
| os << "|f64"; |
| break; |
| case MachineRepresentation::kSimd128: |
| os << "|s128"; |
| break; |
| case MachineRepresentation::kTaggedSigned: |
| os << "|ts"; |
| break; |
| case MachineRepresentation::kTaggedPointer: |
| os << "|tp"; |
| break; |
| case MachineRepresentation::kTagged: |
| os << "|t"; |
| break; |
| case MachineRepresentation::kCompressedPointer: |
| os << "|cp"; |
| break; |
| case MachineRepresentation::kCompressed: |
| os << "|c"; |
| break; |
| } |
| return os << "]"; |
| } |
| case InstructionOperand::INVALID: |
| return os << "(x)"; |
| } |
| UNREACHABLE(); |
| } |
| |
| void MoveOperands::Print() const { |
| StdoutStream{} << destination() << " = " << source() << std::endl; |
| } |
| |
| std::ostream& operator<<(std::ostream& os, const MoveOperands& mo) { |
| os << mo.destination(); |
| if (!mo.source().Equals(mo.destination())) { |
| os << " = " << mo.source(); |
| } |
| return os << ";"; |
| } |
| |
| bool ParallelMove::IsRedundant() const { |
| for (MoveOperands* move : *this) { |
| if (!move->IsRedundant()) return false; |
| } |
| return true; |
| } |
| |
| void ParallelMove::PrepareInsertAfter( |
| MoveOperands* move, ZoneVector<MoveOperands*>* to_eliminate) const { |
| bool no_aliasing = |
| kSimpleFPAliasing || !move->destination().IsFPLocationOperand(); |
| MoveOperands* replacement = nullptr; |
| MoveOperands* eliminated = nullptr; |
| for (MoveOperands* curr : *this) { |
| if (curr->IsEliminated()) continue; |
| if (curr->destination().EqualsCanonicalized(move->source())) { |
| // We must replace move's source with curr's destination in order to |
| // insert it into this ParallelMove. |
| DCHECK(!replacement); |
| replacement = curr; |
| if (no_aliasing && eliminated != nullptr) break; |
| } else if (curr->destination().InterferesWith(move->destination())) { |
| // We can eliminate curr, since move overwrites at least a part of its |
| // destination, implying its value is no longer live. |
| eliminated = curr; |
| to_eliminate->push_back(curr); |
| if (no_aliasing && replacement != nullptr) break; |
| } |
| } |
| if (replacement != nullptr) move->set_source(replacement->source()); |
| } |
| |
| Instruction::Instruction(InstructionCode opcode) |
| : opcode_(opcode), |
| bit_field_(OutputCountField::encode(0) | InputCountField::encode(0) | |
| TempCountField::encode(0) | IsCallField::encode(false)), |
| reference_map_(nullptr), |
| block_(nullptr) { |
| parallel_moves_[0] = nullptr; |
| parallel_moves_[1] = nullptr; |
| |
| // PendingOperands are required to be 8 byte aligned. |
| STATIC_ASSERT(offsetof(Instruction, operands_) % 8 == 0); |
| } |
| |
| Instruction::Instruction(InstructionCode opcode, size_t output_count, |
| InstructionOperand* outputs, size_t input_count, |
| InstructionOperand* inputs, size_t temp_count, |
| InstructionOperand* temps) |
| : opcode_(opcode), |
| bit_field_(OutputCountField::encode(output_count) | |
| InputCountField::encode(input_count) | |
| TempCountField::encode(temp_count) | |
| IsCallField::encode(false)), |
| reference_map_(nullptr), |
| block_(nullptr) { |
| parallel_moves_[0] = nullptr; |
| parallel_moves_[1] = nullptr; |
| size_t offset = 0; |
| for (size_t i = 0; i < output_count; ++i) { |
| DCHECK(!outputs[i].IsInvalid()); |
| operands_[offset++] = outputs[i]; |
| } |
| for (size_t i = 0; i < input_count; ++i) { |
| DCHECK(!inputs[i].IsInvalid()); |
| operands_[offset++] = inputs[i]; |
| } |
| for (size_t i = 0; i < temp_count; ++i) { |
| DCHECK(!temps[i].IsInvalid()); |
| operands_[offset++] = temps[i]; |
| } |
| } |
| |
| bool Instruction::AreMovesRedundant() const { |
| for (int i = Instruction::FIRST_GAP_POSITION; |
| i <= Instruction::LAST_GAP_POSITION; i++) { |
| if (parallel_moves_[i] != nullptr && !parallel_moves_[i]->IsRedundant()) { |
| return false; |
| } |
| } |
| return true; |
| } |
| |
| void Instruction::Print() const { StdoutStream{} << *this << std::endl; } |
| |
| std::ostream& operator<<(std::ostream& os, const ParallelMove& pm) { |
| const char* space = ""; |
| for (MoveOperands* move : pm) { |
| if (move->IsEliminated()) continue; |
| os << space << *move; |
| space = " "; |
| } |
| return os; |
| } |
| |
| void ReferenceMap::RecordReference(const AllocatedOperand& op) { |
| // Do not record arguments as pointers. |
| if (op.IsStackSlot() && LocationOperand::cast(op).index() < 0) return; |
| DCHECK(!op.IsFPRegister() && !op.IsFPStackSlot()); |
| reference_operands_.push_back(op); |
| } |
| |
| std::ostream& operator<<(std::ostream& os, const ReferenceMap& pm) { |
| os << "{"; |
| const char* separator = ""; |
| for (const InstructionOperand& op : pm.reference_operands_) { |
| os << separator << op; |
| separator = ";"; |
| } |
| return os << "}"; |
| } |
| |
| std::ostream& operator<<(std::ostream& os, const ArchOpcode& ao) { |
| switch (ao) { |
| #define CASE(Name) \ |
| case k##Name: \ |
| return os << #Name; |
| ARCH_OPCODE_LIST(CASE) |
| #undef CASE |
| } |
| UNREACHABLE(); |
| } |
| |
| std::ostream& operator<<(std::ostream& os, const AddressingMode& am) { |
| switch (am) { |
| case kMode_None: |
| return os; |
| #define CASE(Name) \ |
| case kMode_##Name: \ |
| return os << #Name; |
| TARGET_ADDRESSING_MODE_LIST(CASE) |
| #undef CASE |
| } |
| UNREACHABLE(); |
| } |
| |
| std::ostream& operator<<(std::ostream& os, const FlagsMode& fm) { |
| switch (fm) { |
| case kFlags_none: |
| return os; |
| case kFlags_branch: |
| return os << "branch"; |
| case kFlags_branch_and_poison: |
| return os << "branch_and_poison"; |
| case kFlags_deoptimize: |
| return os << "deoptimize"; |
| case kFlags_deoptimize_and_poison: |
| return os << "deoptimize_and_poison"; |
| case kFlags_set: |
| return os << "set"; |
| case kFlags_trap: |
| return os << "trap"; |
| } |
| UNREACHABLE(); |
| } |
| |
| std::ostream& operator<<(std::ostream& os, const FlagsCondition& fc) { |
| switch (fc) { |
| case kEqual: |
| return os << "equal"; |
| case kNotEqual: |
| return os << "not equal"; |
| case kSignedLessThan: |
| return os << "signed less than"; |
| case kSignedGreaterThanOrEqual: |
| return os << "signed greater than or equal"; |
| case kSignedLessThanOrEqual: |
| return os << "signed less than or equal"; |
| case kSignedGreaterThan: |
| return os << "signed greater than"; |
| case kUnsignedLessThan: |
| return os << "unsigned less than"; |
| case kUnsignedGreaterThanOrEqual: |
| return os << "unsigned greater than or equal"; |
| case kUnsignedLessThanOrEqual: |
| return os << "unsigned less than or equal"; |
| case kUnsignedGreaterThan: |
| return os << "unsigned greater than"; |
| case kFloatLessThanOrUnordered: |
| return os << "less than or unordered (FP)"; |
| case kFloatGreaterThanOrEqual: |
| return os << "greater than or equal (FP)"; |
| case kFloatLessThanOrEqual: |
| return os << "less than or equal (FP)"; |
| case kFloatGreaterThanOrUnordered: |
| return os << "greater than or unordered (FP)"; |
| case kFloatLessThan: |
| return os << "less than (FP)"; |
| case kFloatGreaterThanOrEqualOrUnordered: |
| return os << "greater than, equal or unordered (FP)"; |
| case kFloatLessThanOrEqualOrUnordered: |
| return os << "less than, equal or unordered (FP)"; |
| case kFloatGreaterThan: |
| return os << "greater than (FP)"; |
| case kUnorderedEqual: |
| return os << "unordered equal"; |
| case kUnorderedNotEqual: |
| return os << "unordered not equal"; |
| case kOverflow: |
| return os << "overflow"; |
| case kNotOverflow: |
| return os << "not overflow"; |
| case kPositiveOrZero: |
| return os << "positive or zero"; |
| case kNegative: |
| return os << "negative"; |
| } |
| UNREACHABLE(); |
| } |
| |
| std::ostream& operator<<(std::ostream& os, const Instruction& instr) { |
| os << "gap "; |
| for (int i = Instruction::FIRST_GAP_POSITION; |
| i <= Instruction::LAST_GAP_POSITION; i++) { |
| os << "("; |
| if (instr.parallel_moves()[i] != nullptr) { |
| os << *instr.parallel_moves()[i]; |
| } |
| os << ") "; |
| } |
| os << "\n "; |
| |
| if (instr.OutputCount() == 1) { |
| os << *instr.OutputAt(0) << " = "; |
| } else if (instr.OutputCount() > 1) { |
| os << "(" << *instr.OutputAt(0); |
| for (size_t i = 1; i < instr.OutputCount(); i++) { |
| os << ", " << *instr.OutputAt(i); |
| } |
| os << ") = "; |
| } |
| |
| os << ArchOpcodeField::decode(instr.opcode()); |
| AddressingMode am = AddressingModeField::decode(instr.opcode()); |
| if (am != kMode_None) { |
| os << " : " << AddressingModeField::decode(instr.opcode()); |
| } |
| FlagsMode fm = FlagsModeField::decode(instr.opcode()); |
| if (fm != kFlags_none) { |
| os << " && " << fm << " if " << FlagsConditionField::decode(instr.opcode()); |
| } |
| for (size_t i = 0; i < instr.InputCount(); i++) { |
| os << " " << *instr.InputAt(i); |
| } |
| return os; |
| } |
| |
| Constant::Constant(int32_t v) : type_(kInt32), value_(v) {} |
| |
| Constant::Constant(RelocatablePtrConstantInfo info) { |
| if (info.type() == RelocatablePtrConstantInfo::kInt32) { |
| type_ = kInt32; |
| } else if (info.type() == RelocatablePtrConstantInfo::kInt64) { |
| type_ = kInt64; |
| } else { |
| UNREACHABLE(); |
| } |
| value_ = info.value(); |
| rmode_ = info.rmode(); |
| } |
| |
| Handle<HeapObject> Constant::ToHeapObject() const { |
| DCHECK(kHeapObject == type() || kCompressedHeapObject == type()); |
| Handle<HeapObject> value( |
| reinterpret_cast<Address*>(static_cast<intptr_t>(value_))); |
| return value; |
| } |
| |
| Handle<Code> Constant::ToCode() const { |
| DCHECK_EQ(kHeapObject, type()); |
| Handle<Code> value(reinterpret_cast<Address*>(static_cast<intptr_t>(value_))); |
| return value; |
| } |
| |
| const StringConstantBase* Constant::ToDelayedStringConstant() const { |
| DCHECK_EQ(kDelayedStringConstant, type()); |
| const StringConstantBase* value = |
| bit_cast<StringConstantBase*>(static_cast<intptr_t>(value_)); |
| return value; |
| } |
| |
| std::ostream& operator<<(std::ostream& os, const Constant& constant) { |
| switch (constant.type()) { |
| case Constant::kInt32: |
| return os << constant.ToInt32(); |
| case Constant::kInt64: |
| return os << constant.ToInt64() << "l"; |
| case Constant::kFloat32: |
| return os << constant.ToFloat32() << "f"; |
| case Constant::kFloat64: |
| return os << constant.ToFloat64().value(); |
| case Constant::kExternalReference: |
| return os << constant.ToExternalReference().address(); |
| case Constant::kHeapObject: // Fall through. |
| case Constant::kCompressedHeapObject: |
| return os << Brief(*constant.ToHeapObject()); |
| case Constant::kRpoNumber: |
| return os << "RPO" << constant.ToRpoNumber().ToInt(); |
| case Constant::kDelayedStringConstant: |
| return os << "DelayedStringConstant: " |
| << constant.ToDelayedStringConstant(); |
| } |
| UNREACHABLE(); |
| } |
| |
| PhiInstruction::PhiInstruction(Zone* zone, int virtual_register, |
| size_t input_count) |
| : virtual_register_(virtual_register), |
| output_(UnallocatedOperand(UnallocatedOperand::NONE, virtual_register)), |
| operands_(input_count, InstructionOperand::kInvalidVirtualRegister, |
| zone) {} |
| |
| void PhiInstruction::SetInput(size_t offset, int virtual_register) { |
| DCHECK_EQ(InstructionOperand::kInvalidVirtualRegister, operands_[offset]); |
| operands_[offset] = virtual_register; |
| } |
| |
| void PhiInstruction::RenameInput(size_t offset, int virtual_register) { |
| DCHECK_NE(InstructionOperand::kInvalidVirtualRegister, operands_[offset]); |
| operands_[offset] = virtual_register; |
| } |
| |
| InstructionBlock::InstructionBlock(Zone* zone, RpoNumber rpo_number, |
| RpoNumber loop_header, RpoNumber loop_end, |
| RpoNumber dominator, bool deferred, |
| bool handler) |
| : successors_(zone), |
| predecessors_(zone), |
| phis_(zone), |
| ao_number_(RpoNumber::Invalid()), |
| rpo_number_(rpo_number), |
| loop_header_(loop_header), |
| loop_end_(loop_end), |
| dominator_(dominator), |
| deferred_(deferred), |
| handler_(handler) {} |
| |
| size_t InstructionBlock::PredecessorIndexOf(RpoNumber rpo_number) const { |
| size_t j = 0; |
| for (InstructionBlock::Predecessors::const_iterator i = predecessors_.begin(); |
| i != predecessors_.end(); ++i, ++j) { |
| if (*i == rpo_number) break; |
| } |
| return j; |
| } |
| |
| static RpoNumber GetRpo(const BasicBlock* block) { |
| if (block == nullptr) return RpoNumber::Invalid(); |
| return RpoNumber::FromInt(block->rpo_number()); |
| } |
| |
| static RpoNumber GetLoopEndRpo(const BasicBlock* block) { |
| if (!block->IsLoopHeader()) return RpoNumber::Invalid(); |
| return RpoNumber::FromInt(block->loop_end()->rpo_number()); |
| } |
| |
| static InstructionBlock* InstructionBlockFor(Zone* zone, |
| const BasicBlock* block) { |
| bool is_handler = |
| !block->empty() && block->front()->opcode() == IrOpcode::kIfException; |
| InstructionBlock* instr_block = zone->New<InstructionBlock>( |
| zone, GetRpo(block), GetRpo(block->loop_header()), GetLoopEndRpo(block), |
| GetRpo(block->dominator()), block->deferred(), is_handler); |
| // Map successors and precessors |
| instr_block->successors().reserve(block->SuccessorCount()); |
| for (BasicBlock* successor : block->successors()) { |
| instr_block->successors().push_back(GetRpo(successor)); |
| } |
| instr_block->predecessors().reserve(block->PredecessorCount()); |
| for (BasicBlock* predecessor : block->predecessors()) { |
| instr_block->predecessors().push_back(GetRpo(predecessor)); |
| } |
| if (block->PredecessorCount() == 1 && |
| block->predecessors()[0]->control() == BasicBlock::Control::kSwitch) { |
| instr_block->set_switch_target(true); |
| } |
| return instr_block; |
| } |
| |
| std::ostream& operator<<(std::ostream& os, |
| const PrintableInstructionBlock& printable_block) { |
| const InstructionBlock* block = printable_block.block_; |
| const InstructionSequence* code = printable_block.code_; |
| |
| os << "B" << block->rpo_number(); |
| if (block->ao_number().IsValid()) { |
| os << ": AO#" << block->ao_number(); |
| } else { |
| os << ": AO#?"; |
| } |
| if (block->IsDeferred()) os << " (deferred)"; |
| if (!block->needs_frame()) os << " (no frame)"; |
| if (block->must_construct_frame()) os << " (construct frame)"; |
| if (block->must_deconstruct_frame()) os << " (deconstruct frame)"; |
| if (block->IsLoopHeader()) { |
| os << " loop blocks: [" << block->rpo_number() << ", " << block->loop_end() |
| << ")"; |
| } |
| os << " instructions: [" << block->code_start() << ", " << block->code_end() |
| << ")" << std::endl |
| << " predecessors:"; |
| |
| for (RpoNumber pred : block->predecessors()) { |
| os << " B" << pred.ToInt(); |
| } |
| os << std::endl; |
| |
| for (const PhiInstruction* phi : block->phis()) { |
| os << " phi: " << phi->output() << " ="; |
| for (int input : phi->operands()) { |
| os << " v" << input; |
| } |
| os << std::endl; |
| } |
| |
| for (int j = block->first_instruction_index(); |
| j <= block->last_instruction_index(); j++) { |
| os << " " << std::setw(5) << j << ": " << *code->InstructionAt(j) |
| << std::endl; |
| } |
| |
| os << " successors:"; |
| for (RpoNumber succ : block->successors()) { |
| os << " B" << succ.ToInt(); |
| } |
| os << std::endl; |
| return os; |
| } |
| |
| InstructionBlocks* InstructionSequence::InstructionBlocksFor( |
| Zone* zone, const Schedule* schedule) { |
| InstructionBlocks* blocks = zone->NewArray<InstructionBlocks>(1); |
| new (blocks) InstructionBlocks( |
| static_cast<int>(schedule->rpo_order()->size()), nullptr, zone); |
| size_t rpo_number = 0; |
| for (BasicBlockVector::const_iterator it = schedule->rpo_order()->begin(); |
| it != schedule->rpo_order()->end(); ++it, ++rpo_number) { |
| DCHECK(!(*blocks)[rpo_number]); |
| DCHECK(GetRpo(*it).ToSize() == rpo_number); |
| (*blocks)[rpo_number] = InstructionBlockFor(zone, *it); |
| } |
| return blocks; |
| } |
| |
| void InstructionSequence::ValidateEdgeSplitForm() const { |
| // Validate blocks are in edge-split form: no block with multiple successors |
| // has an edge to a block (== a successor) with more than one predecessors. |
| for (const InstructionBlock* block : instruction_blocks()) { |
| if (block->SuccessorCount() > 1) { |
| for (const RpoNumber& successor_id : block->successors()) { |
| const InstructionBlock* successor = InstructionBlockAt(successor_id); |
| // Expect precisely one predecessor: "block". |
| CHECK(successor->PredecessorCount() == 1 && |
| successor->predecessors()[0] == block->rpo_number()); |
| } |
| } |
| } |
| } |
| |
| void InstructionSequence::ValidateDeferredBlockExitPaths() const { |
| // A deferred block with more than one successor must have all its successors |
| // deferred. |
| for (const InstructionBlock* block : instruction_blocks()) { |
| if (!block->IsDeferred() || block->SuccessorCount() <= 1) continue; |
| for (RpoNumber successor_id : block->successors()) { |
| CHECK(InstructionBlockAt(successor_id)->IsDeferred()); |
| } |
| } |
| } |
| |
| void InstructionSequence::ValidateDeferredBlockEntryPaths() const { |
| // If a deferred block has multiple predecessors, they have to |
| // all be deferred. Otherwise, we can run into a situation where a range |
| // that spills only in deferred blocks inserts its spill in the block, but |
| // other ranges need moves inserted by ResolveControlFlow in the predecessors, |
| // which may clobber the register of this range. |
| for (const InstructionBlock* block : instruction_blocks()) { |
| if (!block->IsDeferred() || block->PredecessorCount() <= 1) continue; |
| for (RpoNumber predecessor_id : block->predecessors()) { |
| CHECK(InstructionBlockAt(predecessor_id)->IsDeferred()); |
| } |
| } |
| } |
| |
| void InstructionSequence::ValidateSSA() const { |
| // TODO(mtrofin): We could use a local zone here instead. |
| BitVector definitions(VirtualRegisterCount(), zone()); |
| for (const Instruction* instruction : *this) { |
| for (size_t i = 0; i < instruction->OutputCount(); ++i) { |
| const InstructionOperand* output = instruction->OutputAt(i); |
| int vreg = (output->IsConstant()) |
| ? ConstantOperand::cast(output)->virtual_register() |
| : UnallocatedOperand::cast(output)->virtual_register(); |
| CHECK(!definitions.Contains(vreg)); |
| definitions.Add(vreg); |
| } |
| } |
| } |
| |
| void InstructionSequence::ComputeAssemblyOrder() { |
| int ao = 0; |
| RpoNumber invalid = RpoNumber::Invalid(); |
| |
| ao_blocks_ = zone()->NewArray<InstructionBlocks>(1); |
| new (ao_blocks_) InstructionBlocks(zone()); |
| ao_blocks_->reserve(instruction_blocks_->size()); |
| |
| // Place non-deferred blocks. |
| for (InstructionBlock* const block : *instruction_blocks_) { |
| DCHECK_NOT_NULL(block); |
| if (block->IsDeferred()) continue; // skip deferred blocks. |
| if (block->ao_number() != invalid) continue; // loop rotated. |
| if (block->IsLoopHeader()) { |
| bool header_align = true; |
| if (FLAG_turbo_loop_rotation) { |
| // Perform loop rotation for non-deferred loops. |
| InstructionBlock* loop_end = |
| instruction_blocks_->at(block->loop_end().ToSize() - 1); |
| if (loop_end->SuccessorCount() == 1 && /* ends with goto */ |
| loop_end != block /* not a degenerate infinite loop */) { |
| // If the last block has an unconditional jump back to the header, |
| // then move it to be in front of the header in the assembly order. |
| DCHECK_EQ(block->rpo_number(), loop_end->successors()[0]); |
| loop_end->set_ao_number(RpoNumber::FromInt(ao++)); |
| ao_blocks_->push_back(loop_end); |
| // This block will be the new machine-level loop header, so align |
| // this block instead of the loop header block. |
| loop_end->set_alignment(true); |
| header_align = false; |
| } |
| } |
| block->set_alignment(header_align); |
| } |
| if (block->loop_header().IsValid() && block->IsSwitchTarget()) { |
| block->set_alignment(true); |
| } |
| block->set_ao_number(RpoNumber::FromInt(ao++)); |
| ao_blocks_->push_back(block); |
| } |
| // Add all leftover (deferred) blocks. |
| for (InstructionBlock* const block : *instruction_blocks_) { |
| if (block->ao_number() == invalid) { |
| block->set_ao_number(RpoNumber::FromInt(ao++)); |
| ao_blocks_->push_back(block); |
| } |
| } |
| DCHECK_EQ(instruction_blocks_->size(), ao); |
| } |
| |
| void InstructionSequence::RecomputeAssemblyOrderForTesting() { |
| RpoNumber invalid = RpoNumber::Invalid(); |
| for (InstructionBlock* block : *instruction_blocks_) { |
| block->set_ao_number(invalid); |
| } |
| ComputeAssemblyOrder(); |
| } |
| |
| InstructionSequence::InstructionSequence(Isolate* isolate, |
| Zone* instruction_zone, |
| InstructionBlocks* instruction_blocks) |
| : isolate_(isolate), |
| zone_(instruction_zone), |
| instruction_blocks_(instruction_blocks), |
| ao_blocks_(nullptr), |
| source_positions_(zone()), |
| constants_(ConstantMap::key_compare(), |
| ConstantMap::allocator_type(zone())), |
| immediates_(zone()), |
| instructions_(zone()), |
| next_virtual_register_(0), |
| reference_maps_(zone()), |
| representations_(zone()), |
| representation_mask_(0), |
| deoptimization_entries_(zone()), |
| current_block_(nullptr) { |
| ComputeAssemblyOrder(); |
| } |
| |
| int InstructionSequence::NextVirtualRegister() { |
| int virtual_register = next_virtual_register_++; |
| CHECK_NE(virtual_register, InstructionOperand::kInvalidVirtualRegister); |
| return virtual_register; |
| } |
| |
| Instruction* InstructionSequence::GetBlockStart(RpoNumber rpo) const { |
| const InstructionBlock* block = InstructionBlockAt(rpo); |
| return InstructionAt(block->code_start()); |
| } |
| |
| void InstructionSequence::StartBlock(RpoNumber rpo) { |
| DCHECK_NULL(current_block_); |
| current_block_ = InstructionBlockAt(rpo); |
| int code_start = static_cast<int>(instructions_.size()); |
| current_block_->set_code_start(code_start); |
| } |
| |
| void InstructionSequence::EndBlock(RpoNumber rpo) { |
| int end = static_cast<int>(instructions_.size()); |
| DCHECK_EQ(current_block_->rpo_number(), rpo); |
| CHECK(current_block_->code_start() >= 0 && |
| current_block_->code_start() < end); |
| current_block_->set_code_end(end); |
| current_block_ = nullptr; |
| } |
| |
| int InstructionSequence::AddInstruction(Instruction* instr) { |
| DCHECK_NOT_NULL(current_block_); |
| int index = static_cast<int>(instructions_.size()); |
| instr->set_block(current_block_); |
| instructions_.push_back(instr); |
| if (instr->NeedsReferenceMap()) { |
| DCHECK_NULL(instr->reference_map()); |
| ReferenceMap* reference_map = zone()->New<ReferenceMap>(zone()); |
| reference_map->set_instruction_position(index); |
| instr->set_reference_map(reference_map); |
| reference_maps_.push_back(reference_map); |
| } |
| return index; |
| } |
| |
| InstructionBlock* InstructionSequence::GetInstructionBlock( |
| int instruction_index) const { |
| return instructions()[instruction_index]->block(); |
| } |
| |
| static MachineRepresentation FilterRepresentation(MachineRepresentation rep) { |
| switch (rep) { |
| case MachineRepresentation::kBit: |
| case MachineRepresentation::kWord8: |
| case MachineRepresentation::kWord16: |
| return InstructionSequence::DefaultRepresentation(); |
| case MachineRepresentation::kWord32: |
| case MachineRepresentation::kWord64: |
| case MachineRepresentation::kTaggedSigned: |
| case MachineRepresentation::kTaggedPointer: |
| case MachineRepresentation::kTagged: |
| case MachineRepresentation::kFloat32: |
| case MachineRepresentation::kFloat64: |
| case MachineRepresentation::kSimd128: |
| case MachineRepresentation::kCompressedPointer: |
| case MachineRepresentation::kCompressed: |
| return rep; |
| case MachineRepresentation::kNone: |
| break; |
| } |
| |
| UNREACHABLE(); |
| } |
| |
| MachineRepresentation InstructionSequence::GetRepresentation( |
| int virtual_register) const { |
| DCHECK_LE(0, virtual_register); |
| DCHECK_LT(virtual_register, VirtualRegisterCount()); |
| if (virtual_register >= static_cast<int>(representations_.size())) { |
| return DefaultRepresentation(); |
| } |
| return representations_[virtual_register]; |
| } |
| |
| void InstructionSequence::MarkAsRepresentation(MachineRepresentation rep, |
| int virtual_register) { |
| DCHECK_LE(0, virtual_register); |
| DCHECK_LT(virtual_register, VirtualRegisterCount()); |
| if (virtual_register >= static_cast<int>(representations_.size())) { |
| representations_.resize(VirtualRegisterCount(), DefaultRepresentation()); |
| } |
| rep = FilterRepresentation(rep); |
| DCHECK_IMPLIES(representations_[virtual_register] != rep, |
| representations_[virtual_register] == DefaultRepresentation()); |
| representations_[virtual_register] = rep; |
| representation_mask_ |= RepresentationBit(rep); |
| } |
| |
| int InstructionSequence::AddDeoptimizationEntry( |
| FrameStateDescriptor* descriptor, DeoptimizeKind kind, |
| DeoptimizeReason reason, FeedbackSource const& feedback) { |
| int deoptimization_id = static_cast<int>(deoptimization_entries_.size()); |
| deoptimization_entries_.push_back( |
| DeoptimizationEntry(descriptor, kind, reason, feedback)); |
| return deoptimization_id; |
| } |
| |
| DeoptimizationEntry const& InstructionSequence::GetDeoptimizationEntry( |
| int state_id) { |
| return deoptimization_entries_[state_id]; |
| } |
| |
| RpoNumber InstructionSequence::InputRpo(Instruction* instr, size_t index) { |
| InstructionOperand* operand = instr->InputAt(index); |
| Constant constant = |
| operand->IsImmediate() |
| ? GetImmediate(ImmediateOperand::cast(operand)) |
| : GetConstant(ConstantOperand::cast(operand)->virtual_register()); |
| return constant.ToRpoNumber(); |
| } |
| |
| bool InstructionSequence::GetSourcePosition(const Instruction* instr, |
| SourcePosition* result) const { |
| auto it = source_positions_.find(instr); |
| if (it == source_positions_.end()) return false; |
| *result = it->second; |
| return true; |
| } |
| |
| void InstructionSequence::SetSourcePosition(const Instruction* instr, |
| SourcePosition value) { |
| source_positions_.insert(std::make_pair(instr, value)); |
| } |
| |
| void InstructionSequence::Print() const { |
| StdoutStream{} << *this << std::endl; |
| } |
| |
| void InstructionSequence::PrintBlock(int block_id) const { |
| RpoNumber rpo = RpoNumber::FromInt(block_id); |
| const InstructionBlock* block = InstructionBlockAt(rpo); |
| CHECK(block->rpo_number() == rpo); |
| StdoutStream{} << PrintableInstructionBlock{block, this} << std::endl; |
| } |
| |
| const RegisterConfiguration* |
| InstructionSequence::registerConfigurationForTesting_ = nullptr; |
| |
| const RegisterConfiguration* |
| InstructionSequence::RegisterConfigurationForTesting() { |
| DCHECK_NOT_NULL(registerConfigurationForTesting_); |
| return registerConfigurationForTesting_; |
| } |
| |
| void InstructionSequence::SetRegisterConfigurationForTesting( |
| const RegisterConfiguration* regConfig) { |
| registerConfigurationForTesting_ = regConfig; |
| GetRegConfig = InstructionSequence::RegisterConfigurationForTesting; |
| } |
| |
| namespace { |
| |
| size_t GetConservativeFrameSizeInBytes(FrameStateType type, |
| size_t parameters_count, |
| size_t locals_count, |
| BailoutId bailout_id) { |
| switch (type) { |
| case FrameStateType::kInterpretedFunction: { |
| auto info = InterpretedFrameInfo::Conservative( |
| static_cast<int>(parameters_count), static_cast<int>(locals_count)); |
| return info.frame_size_in_bytes(); |
| } |
| case FrameStateType::kArgumentsAdaptor: { |
| auto info = ArgumentsAdaptorFrameInfo::Conservative( |
| static_cast<int>(parameters_count)); |
| return info.frame_size_in_bytes(); |
| } |
| case FrameStateType::kConstructStub: { |
| auto info = ConstructStubFrameInfo::Conservative( |
| static_cast<int>(parameters_count)); |
| return info.frame_size_in_bytes(); |
| } |
| case FrameStateType::kBuiltinContinuation: |
| case FrameStateType::kJavaScriptBuiltinContinuation: |
| case FrameStateType::kJavaScriptBuiltinContinuationWithCatch: { |
| const RegisterConfiguration* config = RegisterConfiguration::Default(); |
| auto info = BuiltinContinuationFrameInfo::Conservative( |
| static_cast<int>(parameters_count), |
| Builtins::CallInterfaceDescriptorFor( |
| Builtins::GetBuiltinFromBailoutId(bailout_id)), |
| config); |
| return info.frame_size_in_bytes(); |
| } |
| } |
| UNREACHABLE(); |
| } |
| |
| size_t GetTotalConservativeFrameSizeInBytes(FrameStateType type, |
| size_t parameters_count, |
| size_t locals_count, |
| BailoutId bailout_id, |
| FrameStateDescriptor* outer_state) { |
| size_t outer_total_conservative_frame_size_in_bytes = |
| (outer_state == nullptr) |
| ? 0 |
| : outer_state->total_conservative_frame_size_in_bytes(); |
| return GetConservativeFrameSizeInBytes(type, parameters_count, locals_count, |
| bailout_id) + |
| outer_total_conservative_frame_size_in_bytes; |
| } |
| |
| } // namespace |
| |
| FrameStateDescriptor::FrameStateDescriptor( |
| Zone* zone, FrameStateType type, BailoutId bailout_id, |
| OutputFrameStateCombine state_combine, size_t parameters_count, |
| size_t locals_count, size_t stack_count, |
| MaybeHandle<SharedFunctionInfo> shared_info, |
| FrameStateDescriptor* outer_state) |
| : type_(type), |
| bailout_id_(bailout_id), |
| frame_state_combine_(state_combine), |
| parameters_count_(parameters_count), |
| locals_count_(locals_count), |
| stack_count_(stack_count), |
| total_conservative_frame_size_in_bytes_( |
| GetTotalConservativeFrameSizeInBytes( |
| type, parameters_count, locals_count, bailout_id, outer_state)), |
| values_(zone), |
| shared_info_(shared_info), |
| outer_state_(outer_state) {} |
| |
| size_t FrameStateDescriptor::GetHeight() const { |
| switch (type()) { |
| case FrameStateType::kInterpretedFunction: |
| return locals_count(); // The accumulator is *not* included. |
| case FrameStateType::kBuiltinContinuation: |
| // Custom, non-JS calling convention (that does not have a notion of |
| // a receiver or context). |
| return parameters_count(); |
| case FrameStateType::kArgumentsAdaptor: |
| case FrameStateType::kConstructStub: |
| case FrameStateType::kJavaScriptBuiltinContinuation: |
| case FrameStateType::kJavaScriptBuiltinContinuationWithCatch: |
| // JS linkage. The parameters count |
| // - includes the receiver (input 1 in CreateArtificialFrameState, and |
| // passed as part of stack parameters to |
| // CreateJavaScriptBuiltinContinuationFrameState), and |
| // - does *not* include the context. |
| return parameters_count(); |
| } |
| UNREACHABLE(); |
| } |
| |
| size_t FrameStateDescriptor::GetSize() const { |
| return 1 + parameters_count() + locals_count() + stack_count() + |
| (HasContext() ? 1 : 0); |
| } |
| |
| size_t FrameStateDescriptor::GetTotalSize() const { |
| size_t total_size = 0; |
| for (const FrameStateDescriptor* iter = this; iter != nullptr; |
| iter = iter->outer_state_) { |
| total_size += iter->GetSize(); |
| } |
| return total_size; |
| } |
| |
| size_t FrameStateDescriptor::GetFrameCount() const { |
| size_t count = 0; |
| for (const FrameStateDescriptor* iter = this; iter != nullptr; |
| iter = iter->outer_state_) { |
| ++count; |
| } |
| return count; |
| } |
| |
| size_t FrameStateDescriptor::GetJSFrameCount() const { |
| size_t count = 0; |
| for (const FrameStateDescriptor* iter = this; iter != nullptr; |
| iter = iter->outer_state_) { |
| if (FrameStateFunctionInfo::IsJSFunctionType(iter->type_)) { |
| ++count; |
| } |
| } |
| return count; |
| } |
| |
| std::ostream& operator<<(std::ostream& os, const RpoNumber& rpo) { |
| return os << rpo.ToSize(); |
| } |
| |
| std::ostream& operator<<(std::ostream& os, const InstructionSequence& code) { |
| for (size_t i = 0; i < code.immediates_.size(); ++i) { |
| Constant constant = code.immediates_[i]; |
| os << "IMM#" << i << ": " << constant << "\n"; |
| } |
| int i = 0; |
| for (ConstantMap::const_iterator it = code.constants_.begin(); |
| it != code.constants_.end(); ++i, ++it) { |
| os << "CST#" << i << ": v" << it->first << " = " << it->second << "\n"; |
| } |
| for (int i = 0; i < code.InstructionBlockCount(); i++) { |
| auto* block = code.InstructionBlockAt(RpoNumber::FromInt(i)); |
| os << PrintableInstructionBlock{block, &code}; |
| } |
| return os; |
| } |
| |
| } // namespace compiler |
| } // namespace internal |
| } // namespace v8 |