// 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/instruction.h"
|
|
#include <iomanip>
|
|
#include "src/compiler/common-operator.h"
|
#include "src/compiler/graph.h"
|
#include "src/compiler/schedule.h"
|
#include "src/compiler/state-values-utils.h"
|
#include "src/source-position.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();
|
break;
|
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)) / kPointerSize + 1;
|
int other_index_hi = other_loc.index();
|
int other_index_lo =
|
other_index_hi - (1 << ElementSizeLog2Of(other_rep)) / kPointerSize + 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 RegisterConfiguration* config) const {
|
PrintableInstructionOperand wrapper;
|
wrapper.register_configuration_ = config;
|
wrapper.op_ = *this;
|
StdoutStream{} << wrapper << std::endl;
|
}
|
|
void InstructionOperand::Print() const { Print(GetRegConfig()); }
|
|
std::ostream& operator<<(std::ostream& os,
|
const PrintableInstructionOperand& printable) {
|
const InstructionOperand& op = printable.op_;
|
const RegisterConfiguration* conf = printable.register_configuration_;
|
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 << "(="
|
<< conf->GetGeneralRegisterName(
|
unalloc->fixed_register_index())
|
<< ")";
|
case UnallocatedOperand::FIXED_FP_REGISTER:
|
return os << "(="
|
<< conf->GetDoubleRegisterName(
|
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::EXPLICIT:
|
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()) {
|
os << "["
|
<< GetRegConfig()->GetGeneralOrSpecialRegisterName(
|
allocated.register_code())
|
<< "|R";
|
} else if (op.IsDoubleRegister()) {
|
os << "["
|
<< GetRegConfig()->GetDoubleRegisterName(allocated.register_code())
|
<< "|R";
|
} else if (op.IsFloatRegister()) {
|
os << "["
|
<< GetRegConfig()->GetFloatRegisterName(allocated.register_code())
|
<< "|R";
|
} else {
|
DCHECK(op.IsSimd128Register());
|
os << "["
|
<< GetRegConfig()->GetSimd128RegisterName(allocated.register_code())
|
<< "|R";
|
}
|
if (allocated.IsExplicit()) {
|
os << "|E";
|
}
|
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;
|
}
|
return os << "]";
|
}
|
case InstructionOperand::INVALID:
|
return os << "(x)";
|
}
|
UNREACHABLE();
|
}
|
|
void MoveOperands::Print(const RegisterConfiguration* config) const {
|
StdoutStream os;
|
PrintableInstructionOperand wrapper;
|
wrapper.register_configuration_ = config;
|
wrapper.op_ = destination();
|
os << wrapper << " = ";
|
wrapper.op_ = source();
|
os << wrapper << std::endl;
|
}
|
|
void MoveOperands::Print() const { Print(GetRegConfig()); }
|
|
std::ostream& operator<<(std::ostream& os,
|
const PrintableMoveOperands& printable) {
|
const MoveOperands& mo = *printable.move_operands_;
|
PrintableInstructionOperand printable_op = {printable.register_configuration_,
|
mo.destination()};
|
os << printable_op;
|
if (!mo.source().Equals(mo.destination())) {
|
printable_op.op_ = mo.source();
|
os << " = " << printable_op;
|
}
|
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());
|
}
|
|
ExplicitOperand::ExplicitOperand(LocationKind kind, MachineRepresentation rep,
|
int index)
|
: LocationOperand(EXPLICIT, kind, rep, index) {
|
DCHECK_IMPLIES(kind == REGISTER && !IsFloatingPoint(rep),
|
GetRegConfig()->IsAllocatableGeneralCode(index));
|
DCHECK_IMPLIES(kind == REGISTER && rep == MachineRepresentation::kFloat32,
|
GetRegConfig()->IsAllocatableFloatCode(index));
|
DCHECK_IMPLIES(kind == REGISTER && (rep == MachineRepresentation::kFloat64),
|
GetRegConfig()->IsAllocatableDoubleCode(index));
|
}
|
|
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;
|
}
|
|
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 RegisterConfiguration* config) const {
|
PrintableInstruction wrapper;
|
wrapper.instr_ = this;
|
wrapper.register_configuration_ = config;
|
StdoutStream{} << wrapper << std::endl;
|
}
|
|
void Instruction::Print() const { Print(GetRegConfig()); }
|
|
std::ostream& operator<<(std::ostream& os,
|
const PrintableParallelMove& printable) {
|
const ParallelMove& pm = *printable.parallel_move_;
|
bool first = true;
|
for (MoveOperands* move : pm) {
|
if (move->IsEliminated()) continue;
|
if (!first) os << " ";
|
first = false;
|
PrintableMoveOperands pmo = {printable.register_configuration_, move};
|
os << pmo;
|
}
|
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 << "{";
|
bool first = true;
|
PrintableInstructionOperand poi = {GetRegConfig(), InstructionOperand()};
|
for (const InstructionOperand& op : pm.reference_operands_) {
|
if (!first) {
|
os << ";";
|
} else {
|
first = false;
|
}
|
poi.op_ = op;
|
os << poi;
|
}
|
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 PrintableInstruction& printable) {
|
const Instruction& instr = *printable.instr_;
|
PrintableInstructionOperand printable_op = {printable.register_configuration_,
|
InstructionOperand()};
|
os << "gap ";
|
for (int i = Instruction::FIRST_GAP_POSITION;
|
i <= Instruction::LAST_GAP_POSITION; i++) {
|
os << "(";
|
if (instr.parallel_moves()[i] != nullptr) {
|
PrintableParallelMove ppm = {printable.register_configuration_,
|
instr.parallel_moves()[i]};
|
os << ppm;
|
}
|
os << ") ";
|
}
|
os << "\n ";
|
|
if (instr.OutputCount() > 1) os << "(";
|
for (size_t i = 0; i < instr.OutputCount(); i++) {
|
if (i > 0) os << ", ";
|
printable_op.op_ = *instr.OutputAt(i);
|
os << printable_op;
|
}
|
|
if (instr.OutputCount() > 1) os << ") = ";
|
if (instr.OutputCount() == 1) 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());
|
}
|
if (instr.InputCount() > 0) {
|
for (size_t i = 0; i < instr.InputCount(); i++) {
|
printable_op.op_ = *instr.InputAt(i);
|
os << " " << printable_op;
|
}
|
}
|
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_EQ(kHeapObject, type());
|
Handle<HeapObject> value(
|
bit_cast<HeapObject**>(static_cast<intptr_t>(value_)));
|
return value;
|
}
|
|
Handle<Code> Constant::ToCode() const {
|
DCHECK_EQ(kHeapObject, type());
|
Handle<Code> value(bit_cast<Code**>(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:
|
return os << Brief(*constant.ToHeapObject());
|
case Constant::kRpoNumber:
|
return os << "RPO" << constant.ToRpoNumber().ToInt();
|
}
|
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,
|
bool deferred, bool handler)
|
: successors_(zone),
|
predecessors_(zone),
|
phis_(zone),
|
ao_number_(rpo_number),
|
rpo_number_(rpo_number),
|
loop_header_(loop_header),
|
loop_end_(loop_end),
|
code_start_(-1),
|
code_end_(-1),
|
deferred_(deferred),
|
handler_(handler),
|
needs_frame_(false),
|
must_construct_frame_(false),
|
must_deconstruct_frame_(false) {}
|
|
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 = new (zone)
|
InstructionBlock(zone, GetRpo(block), GetRpo(block->loop_header()),
|
GetLoopEndRpo(block), 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));
|
}
|
return instr_block;
|
}
|
|
std::ostream& operator<<(std::ostream& os,
|
const PrintableInstructionBlock& printable_block) {
|
const InstructionBlock* block = printable_block.block_;
|
const RegisterConfiguration* config = printable_block.register_configuration_;
|
const InstructionSequence* code = printable_block.code_;
|
|
os << "B" << block->rpo_number();
|
os << ": AO#" << block->ao_number();
|
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()) {
|
PrintableInstructionOperand printable_op = {config, phi->output()};
|
os << " phi: " << printable_op << " =";
|
for (int input : phi->operands()) {
|
os << " v" << input;
|
}
|
os << std::endl;
|
}
|
|
PrintableInstruction printable_instr;
|
printable_instr.register_configuration_ = config;
|
for (int j = block->first_instruction_index();
|
j <= block->last_instruction_index(); j++) {
|
printable_instr.instr_ = code->InstructionAt(j);
|
os << " " << std::setw(5) << j << ": " << printable_instr << 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);
|
}
|
ComputeAssemblyOrder(blocks);
|
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(InstructionBlocks* blocks) {
|
int ao = 0;
|
for (InstructionBlock* const block : *blocks) {
|
if (!block->IsDeferred()) {
|
block->set_ao_number(RpoNumber::FromInt(ao++));
|
}
|
}
|
for (InstructionBlock* const block : *blocks) {
|
if (block->IsDeferred()) {
|
block->set_ao_number(RpoNumber::FromInt(ao++));
|
}
|
}
|
}
|
|
InstructionSequence::InstructionSequence(Isolate* isolate,
|
Zone* instruction_zone,
|
InstructionBlocks* instruction_blocks)
|
: isolate_(isolate),
|
zone_(instruction_zone),
|
instruction_blocks_(instruction_blocks),
|
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) {}
|
|
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 = new (zone()) 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:
|
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_ |= 1 << static_cast<int>(rep);
|
}
|
|
int InstructionSequence::AddDeoptimizationEntry(
|
FrameStateDescriptor* descriptor, DeoptimizeKind kind,
|
DeoptimizeReason reason, VectorSlotPair 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 RegisterConfiguration* config) const {
|
PrintableInstructionSequence wrapper;
|
wrapper.register_configuration_ = config;
|
wrapper.sequence_ = this;
|
StdoutStream{} << wrapper << std::endl;
|
}
|
|
void InstructionSequence::Print() const { Print(GetRegConfig()); }
|
|
void InstructionSequence::PrintBlock(const RegisterConfiguration* config,
|
int block_id) const {
|
RpoNumber rpo = RpoNumber::FromInt(block_id);
|
const InstructionBlock* block = InstructionBlockAt(rpo);
|
CHECK(block->rpo_number() == rpo);
|
PrintableInstructionBlock printable_block = {config, block, this};
|
StdoutStream{} << printable_block << std::endl;
|
}
|
|
void InstructionSequence::PrintBlock(int block_id) const {
|
PrintBlock(GetRegConfig(), block_id);
|
}
|
|
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;
|
}
|
|
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),
|
values_(zone),
|
shared_info_(shared_info),
|
outer_state_(outer_state) {}
|
|
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 PrintableInstructionSequence& printable) {
|
const InstructionSequence& code = *printable.sequence_;
|
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";
|
}
|
PrintableInstructionBlock printable_block = {
|
printable.register_configuration_, nullptr, printable.sequence_};
|
for (int i = 0; i < code.InstructionBlockCount(); i++) {
|
printable_block.block_ = code.InstructionBlockAt(RpoNumber::FromInt(i));
|
os << printable_block;
|
}
|
return os;
|
}
|
|
} // namespace compiler
|
} // namespace internal
|
} // namespace v8
|
