blob: 50e57bc5adf27a0ff58b94bb86e01b8577099607 [file] [log] [blame]
// 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/register-allocator-verifier.h"
#include "src/compiler/backend/instruction.h"
#include "src/utils/bit-vector.h"
#include "src/utils/ostreams.h"
namespace v8 {
namespace internal {
namespace compiler {
namespace {
size_t OperandCount(const Instruction* instr) {
return instr->InputCount() + instr->OutputCount() + instr->TempCount();
}
void VerifyEmptyGaps(const Instruction* instr) {
for (int i = Instruction::FIRST_GAP_POSITION;
i <= Instruction::LAST_GAP_POSITION; i++) {
Instruction::GapPosition inner_pos =
static_cast<Instruction::GapPosition>(i);
CHECK_NULL(instr->GetParallelMove(inner_pos));
}
}
void VerifyAllocatedGaps(const Instruction* instr, const char* caller_info) {
for (int i = Instruction::FIRST_GAP_POSITION;
i <= Instruction::LAST_GAP_POSITION; i++) {
Instruction::GapPosition inner_pos =
static_cast<Instruction::GapPosition>(i);
const ParallelMove* moves = instr->GetParallelMove(inner_pos);
if (moves == nullptr) continue;
for (const MoveOperands* move : *moves) {
if (move->IsRedundant()) continue;
CHECK_WITH_MSG(
move->source().IsAllocated() || move->source().IsConstant(),
caller_info);
CHECK_WITH_MSG(move->destination().IsAllocated(), caller_info);
}
}
}
} // namespace
RegisterAllocatorVerifier::RegisterAllocatorVerifier(
Zone* zone, const RegisterConfiguration* config,
const InstructionSequence* sequence, const Frame* frame)
: zone_(zone),
config_(config),
sequence_(sequence),
constraints_(zone),
assessments_(zone),
outstanding_assessments_(zone),
spill_slot_delta_(frame->GetTotalFrameSlotCount() -
frame->GetSpillSlotCount()) {
constraints_.reserve(sequence->instructions().size());
// TODO(dcarney): model unique constraints.
// Construct OperandConstraints for all InstructionOperands, eliminating
// kSameAsFirst along the way.
for (const Instruction* instr : sequence->instructions()) {
// All gaps should be totally unallocated at this point.
VerifyEmptyGaps(instr);
const size_t operand_count = OperandCount(instr);
OperandConstraint* op_constraints =
zone->NewArray<OperandConstraint>(operand_count);
size_t count = 0;
for (size_t i = 0; i < instr->InputCount(); ++i, ++count) {
BuildConstraint(instr->InputAt(i), &op_constraints[count]);
VerifyInput(op_constraints[count]);
}
for (size_t i = 0; i < instr->TempCount(); ++i, ++count) {
BuildConstraint(instr->TempAt(i), &op_constraints[count]);
VerifyTemp(op_constraints[count]);
}
for (size_t i = 0; i < instr->OutputCount(); ++i, ++count) {
BuildConstraint(instr->OutputAt(i), &op_constraints[count]);
if (op_constraints[count].type_ == kSameAsFirst) {
CHECK_LT(0, instr->InputCount());
op_constraints[count].type_ = op_constraints[0].type_;
op_constraints[count].value_ = op_constraints[0].value_;
}
VerifyOutput(op_constraints[count]);
}
InstructionConstraint instr_constraint = {instr, operand_count,
op_constraints};
constraints()->push_back(instr_constraint);
}
}
void RegisterAllocatorVerifier::VerifyInput(
const OperandConstraint& constraint) {
CHECK_NE(kSameAsFirst, constraint.type_);
if (constraint.type_ != kImmediate) {
CHECK_NE(InstructionOperand::kInvalidVirtualRegister,
constraint.virtual_register_);
}
}
void RegisterAllocatorVerifier::VerifyTemp(
const OperandConstraint& constraint) {
CHECK_NE(kSameAsFirst, constraint.type_);
CHECK_NE(kImmediate, constraint.type_);
CHECK_NE(kConstant, constraint.type_);
}
void RegisterAllocatorVerifier::VerifyOutput(
const OperandConstraint& constraint) {
CHECK_NE(kImmediate, constraint.type_);
CHECK_NE(InstructionOperand::kInvalidVirtualRegister,
constraint.virtual_register_);
}
void RegisterAllocatorVerifier::VerifyAssignment(const char* caller_info) {
caller_info_ = caller_info;
CHECK(sequence()->instructions().size() == constraints()->size());
auto instr_it = sequence()->begin();
for (const auto& instr_constraint : *constraints()) {
const Instruction* instr = instr_constraint.instruction_;
// All gaps should be totally allocated at this point.
VerifyAllocatedGaps(instr, caller_info_);
const size_t operand_count = instr_constraint.operand_constaints_size_;
const OperandConstraint* op_constraints =
instr_constraint.operand_constraints_;
CHECK_EQ(instr, *instr_it);
CHECK(operand_count == OperandCount(instr));
size_t count = 0;
for (size_t i = 0; i < instr->InputCount(); ++i, ++count) {
CheckConstraint(instr->InputAt(i), &op_constraints[count]);
}
for (size_t i = 0; i < instr->TempCount(); ++i, ++count) {
CheckConstraint(instr->TempAt(i), &op_constraints[count]);
}
for (size_t i = 0; i < instr->OutputCount(); ++i, ++count) {
CheckConstraint(instr->OutputAt(i), &op_constraints[count]);
}
++instr_it;
}
}
void RegisterAllocatorVerifier::BuildConstraint(const InstructionOperand* op,
OperandConstraint* constraint) {
constraint->value_ = kMinInt;
constraint->virtual_register_ = InstructionOperand::kInvalidVirtualRegister;
if (op->IsConstant()) {
constraint->type_ = kConstant;
constraint->value_ = ConstantOperand::cast(op)->virtual_register();
constraint->virtual_register_ = constraint->value_;
} else if (op->IsImmediate()) {
const ImmediateOperand* imm = ImmediateOperand::cast(op);
int value = imm->type() == ImmediateOperand::INLINE ? imm->inline_value()
: imm->indexed_value();
constraint->type_ = kImmediate;
constraint->value_ = value;
} else {
CHECK(op->IsUnallocated());
const UnallocatedOperand* unallocated = UnallocatedOperand::cast(op);
int vreg = unallocated->virtual_register();
constraint->virtual_register_ = vreg;
if (unallocated->basic_policy() == UnallocatedOperand::FIXED_SLOT) {
constraint->type_ = kFixedSlot;
constraint->value_ = unallocated->fixed_slot_index();
} else {
switch (unallocated->extended_policy()) {
case UnallocatedOperand::REGISTER_OR_SLOT:
case UnallocatedOperand::NONE:
if (sequence()->IsFP(vreg)) {
constraint->type_ = kRegisterOrSlotFP;
} else {
constraint->type_ = kRegisterOrSlot;
}
break;
case UnallocatedOperand::REGISTER_OR_SLOT_OR_CONSTANT:
DCHECK(!sequence()->IsFP(vreg));
constraint->type_ = kRegisterOrSlotOrConstant;
break;
case UnallocatedOperand::FIXED_REGISTER:
if (unallocated->HasSecondaryStorage()) {
constraint->type_ = kRegisterAndSlot;
constraint->spilled_slot_ = unallocated->GetSecondaryStorage();
} else {
constraint->type_ = kFixedRegister;
}
constraint->value_ = unallocated->fixed_register_index();
break;
case UnallocatedOperand::FIXED_FP_REGISTER:
constraint->type_ = kFixedFPRegister;
constraint->value_ = unallocated->fixed_register_index();
break;
case UnallocatedOperand::MUST_HAVE_REGISTER:
if (sequence()->IsFP(vreg)) {
constraint->type_ = kFPRegister;
} else {
constraint->type_ = kRegister;
}
break;
case UnallocatedOperand::MUST_HAVE_SLOT:
constraint->type_ = kSlot;
constraint->value_ =
ElementSizeLog2Of(sequence()->GetRepresentation(vreg));
break;
case UnallocatedOperand::SAME_AS_FIRST_INPUT:
constraint->type_ = kSameAsFirst;
break;
}
}
}
}
void RegisterAllocatorVerifier::CheckConstraint(
const InstructionOperand* op, const OperandConstraint* constraint) {
switch (constraint->type_) {
case kConstant:
CHECK_WITH_MSG(op->IsConstant(), caller_info_);
CHECK_EQ(ConstantOperand::cast(op)->virtual_register(),
constraint->value_);
return;
case kImmediate: {
CHECK_WITH_MSG(op->IsImmediate(), caller_info_);
const ImmediateOperand* imm = ImmediateOperand::cast(op);
int value = imm->type() == ImmediateOperand::INLINE
? imm->inline_value()
: imm->indexed_value();
CHECK_EQ(value, constraint->value_);
return;
}
case kRegister:
CHECK_WITH_MSG(op->IsRegister(), caller_info_);
return;
case kFPRegister:
CHECK_WITH_MSG(op->IsFPRegister(), caller_info_);
return;
case kFixedRegister:
case kRegisterAndSlot:
CHECK_WITH_MSG(op->IsRegister(), caller_info_);
CHECK_EQ(LocationOperand::cast(op)->register_code(), constraint->value_);
return;
case kFixedFPRegister:
CHECK_WITH_MSG(op->IsFPRegister(), caller_info_);
CHECK_EQ(LocationOperand::cast(op)->register_code(), constraint->value_);
return;
case kFixedSlot:
CHECK_WITH_MSG(op->IsStackSlot() || op->IsFPStackSlot(), caller_info_);
CHECK_EQ(LocationOperand::cast(op)->index(), constraint->value_);
return;
case kSlot:
CHECK_WITH_MSG(op->IsStackSlot() || op->IsFPStackSlot(), caller_info_);
CHECK_EQ(ElementSizeLog2Of(LocationOperand::cast(op)->representation()),
constraint->value_);
return;
case kRegisterOrSlot:
CHECK_WITH_MSG(op->IsRegister() || op->IsStackSlot(), caller_info_);
return;
case kRegisterOrSlotFP:
CHECK_WITH_MSG(op->IsFPRegister() || op->IsFPStackSlot(), caller_info_);
return;
case kRegisterOrSlotOrConstant:
CHECK_WITH_MSG(op->IsRegister() || op->IsStackSlot() || op->IsConstant(),
caller_info_);
return;
case kSameAsFirst:
CHECK_WITH_MSG(false, caller_info_);
return;
}
}
void BlockAssessments::PerformMoves(const Instruction* instruction) {
const ParallelMove* first =
instruction->GetParallelMove(Instruction::GapPosition::START);
PerformParallelMoves(first);
const ParallelMove* last =
instruction->GetParallelMove(Instruction::GapPosition::END);
PerformParallelMoves(last);
}
void BlockAssessments::PerformParallelMoves(const ParallelMove* moves) {
if (moves == nullptr) return;
CHECK(map_for_moves_.empty());
for (MoveOperands* move : *moves) {
if (move->IsEliminated() || move->IsRedundant()) continue;
auto it = map_.find(move->source());
// The RHS of a parallel move should have been already assessed.
CHECK(it != map_.end());
// The LHS of a parallel move should not have been assigned in this
// parallel move.
CHECK(map_for_moves_.find(move->destination()) == map_for_moves_.end());
// The RHS of a parallel move should not be a stale reference.
CHECK(!IsStaleReferenceStackSlot(move->source()));
// Copy the assessment to the destination.
map_for_moves_[move->destination()] = it->second;
}
for (auto pair : map_for_moves_) {
// Re-insert the existing key for the new assignment so that it has the
// correct representation (which is ignored by the canonicalizing map
// comparator).
InstructionOperand op = pair.first;
map_.erase(op);
map_.insert(pair);
// Destination is no longer a stale reference.
stale_ref_stack_slots().erase(op);
}
map_for_moves_.clear();
}
void BlockAssessments::DropRegisters() {
for (auto iterator = map().begin(), end = map().end(); iterator != end;) {
auto current = iterator;
++iterator;
InstructionOperand op = current->first;
if (op.IsAnyRegister()) map().erase(current);
}
}
void BlockAssessments::CheckReferenceMap(const ReferenceMap* reference_map) {
// First mark all existing reference stack spill slots as stale.
for (auto pair : map()) {
InstructionOperand op = pair.first;
if (op.IsStackSlot()) {
const LocationOperand* loc_op = LocationOperand::cast(&op);
// Only mark arguments that are spill slots as stale, the reference map
// doesn't track arguments or fixed stack slots, which are implicitly
// tracked by the GC.
if (CanBeTaggedOrCompressedPointer(loc_op->representation()) &&
loc_op->index() >= spill_slot_delta()) {
stale_ref_stack_slots().insert(op);
}
}
}
// Now remove any stack spill slots in the reference map from the list of
// stale slots.
for (auto ref_map_operand : reference_map->reference_operands()) {
if (ref_map_operand.IsStackSlot()) {
auto pair = map().find(ref_map_operand);
CHECK(pair != map().end());
stale_ref_stack_slots().erase(pair->first);
}
}
}
bool BlockAssessments::IsStaleReferenceStackSlot(InstructionOperand op) {
if (!op.IsStackSlot()) return false;
const LocationOperand* loc_op = LocationOperand::cast(&op);
return CanBeTaggedOrCompressedPointer(loc_op->representation()) &&
stale_ref_stack_slots().find(op) != stale_ref_stack_slots().end();
}
void BlockAssessments::Print() const {
StdoutStream os;
for (const auto pair : map()) {
const InstructionOperand op = pair.first;
const Assessment* assessment = pair.second;
// Use operator<< so we can write the assessment on the same
// line.
os << op << " : ";
if (assessment->kind() == AssessmentKind::Final) {
os << "v" << FinalAssessment::cast(assessment)->virtual_register();
} else {
os << "P";
}
if (stale_ref_stack_slots().find(op) != stale_ref_stack_slots().end()) {
os << " (stale reference)";
}
os << std::endl;
}
os << std::endl;
}
BlockAssessments* RegisterAllocatorVerifier::CreateForBlock(
const InstructionBlock* block) {
RpoNumber current_block_id = block->rpo_number();
BlockAssessments* ret =
zone()->New<BlockAssessments>(zone(), spill_slot_delta());
if (block->PredecessorCount() == 0) {
// TODO(mtrofin): the following check should hold, however, in certain
// unit tests it is invalidated by the last block. Investigate and
// normalize the CFG.
// CHECK_EQ(0, current_block_id.ToInt());
// The phi size test below is because we can, technically, have phi
// instructions with one argument. Some tests expose that, too.
} else if (block->PredecessorCount() == 1 && block->phis().size() == 0) {
const BlockAssessments* prev_block = assessments_[block->predecessors()[0]];
ret->CopyFrom(prev_block);
} else {
for (RpoNumber pred_id : block->predecessors()) {
// For every operand coming from any of the predecessors, create an
// Unfinalized assessment.
auto iterator = assessments_.find(pred_id);
if (iterator == assessments_.end()) {
// This block is the head of a loop, and this predecessor is the
// loopback
// arc.
// Validate this is a loop case, otherwise the CFG is malformed.
CHECK(pred_id >= current_block_id);
CHECK(block->IsLoopHeader());
continue;
}
const BlockAssessments* pred_assessments = iterator->second;
CHECK_NOT_NULL(pred_assessments);
for (auto pair : pred_assessments->map()) {
InstructionOperand operand = pair.first;
if (ret->map().find(operand) == ret->map().end()) {
ret->map().insert(std::make_pair(
operand, zone()->New<PendingAssessment>(zone(), block, operand)));
}
}
// Any references stack slots that became stale in predecessors will be
// stale here.
ret->stale_ref_stack_slots().insert(
pred_assessments->stale_ref_stack_slots().begin(),
pred_assessments->stale_ref_stack_slots().end());
}
}
return ret;
}
void RegisterAllocatorVerifier::ValidatePendingAssessment(
RpoNumber block_id, InstructionOperand op,
const BlockAssessments* current_assessments,
PendingAssessment* const assessment, int virtual_register) {
if (assessment->IsAliasOf(virtual_register)) return;
// When validating a pending assessment, it is possible some of the
// assessments for the original operand (the one where the assessment was
// created for first) are also pending. To avoid recursion, we use a work
// list. To deal with cycles, we keep a set of seen nodes.
Zone local_zone(zone()->allocator(), ZONE_NAME);
ZoneQueue<std::pair<const PendingAssessment*, int>> worklist(&local_zone);
ZoneSet<RpoNumber> seen(&local_zone);
worklist.push(std::make_pair(assessment, virtual_register));
seen.insert(block_id);
while (!worklist.empty()) {
auto work = worklist.front();
const PendingAssessment* current_assessment = work.first;
int current_virtual_register = work.second;
InstructionOperand current_operand = current_assessment->operand();
worklist.pop();
const InstructionBlock* origin = current_assessment->origin();
CHECK(origin->PredecessorCount() > 1 || origin->phis().size() > 0);
// Check if the virtual register is a phi first, instead of relying on
// the incoming assessments. In particular, this handles the case
// v1 = phi v0 v0, which structurally is identical to v0 having been
// defined at the top of a diamond, and arriving at the node joining the
// diamond's branches.
const PhiInstruction* phi = nullptr;
for (const PhiInstruction* candidate : origin->phis()) {
if (candidate->virtual_register() == current_virtual_register) {
phi = candidate;
break;
}
}
int op_index = 0;
for (RpoNumber pred : origin->predecessors()) {
int expected =
phi != nullptr ? phi->operands()[op_index] : current_virtual_register;
++op_index;
auto pred_assignment = assessments_.find(pred);
if (pred_assignment == assessments_.end()) {
CHECK(origin->IsLoopHeader());
auto todo_iter = outstanding_assessments_.find(pred);
DelayedAssessments* set = nullptr;
if (todo_iter == outstanding_assessments_.end()) {
set = zone()->New<DelayedAssessments>(zone());
outstanding_assessments_.insert(std::make_pair(pred, set));
} else {
set = todo_iter->second;
}
set->AddDelayedAssessment(current_operand, expected);
continue;
}
const BlockAssessments* pred_assessments = pred_assignment->second;
auto found_contribution = pred_assessments->map().find(current_operand);
CHECK(found_contribution != pred_assessments->map().end());
Assessment* contribution = found_contribution->second;
switch (contribution->kind()) {
case Final:
CHECK_EQ(FinalAssessment::cast(contribution)->virtual_register(),
expected);
break;
case Pending: {
// This happens if we have a diamond feeding into another one, and
// the inner one never being used - other than for carrying the value.
const PendingAssessment* next = PendingAssessment::cast(contribution);
if (seen.find(pred) == seen.end()) {
worklist.push({next, expected});
seen.insert(pred);
}
// Note that we do not want to finalize pending assessments at the
// beginning of a block - which is the information we'd have
// available here. This is because this operand may be reused to
// define duplicate phis.
break;
}
}
}
}
assessment->AddAlias(virtual_register);
}
void RegisterAllocatorVerifier::ValidateUse(
RpoNumber block_id, BlockAssessments* current_assessments,
InstructionOperand op, int virtual_register) {
auto iterator = current_assessments->map().find(op);
// We should have seen this operand before.
CHECK(iterator != current_assessments->map().end());
Assessment* assessment = iterator->second;
// The operand shouldn't be a stale reference stack slot.
CHECK(!current_assessments->IsStaleReferenceStackSlot(op));
switch (assessment->kind()) {
case Final:
CHECK_EQ(FinalAssessment::cast(assessment)->virtual_register(),
virtual_register);
break;
case Pending: {
PendingAssessment* pending = PendingAssessment::cast(assessment);
ValidatePendingAssessment(block_id, op, current_assessments, pending,
virtual_register);
break;
}
}
}
void RegisterAllocatorVerifier::VerifyGapMoves() {
CHECK(assessments_.empty());
CHECK(outstanding_assessments_.empty());
const size_t block_count = sequence()->instruction_blocks().size();
for (size_t block_index = 0; block_index < block_count; ++block_index) {
const InstructionBlock* block =
sequence()->instruction_blocks()[block_index];
BlockAssessments* block_assessments = CreateForBlock(block);
for (int instr_index = block->code_start(); instr_index < block->code_end();
++instr_index) {
const InstructionConstraint& instr_constraint = constraints_[instr_index];
const Instruction* instr = instr_constraint.instruction_;
block_assessments->PerformMoves(instr);
const OperandConstraint* op_constraints =
instr_constraint.operand_constraints_;
size_t count = 0;
for (size_t i = 0; i < instr->InputCount(); ++i, ++count) {
if (op_constraints[count].type_ == kImmediate) {
continue;
}
int virtual_register = op_constraints[count].virtual_register_;
InstructionOperand op = *instr->InputAt(i);
ValidateUse(block->rpo_number(), block_assessments, op,
virtual_register);
}
for (size_t i = 0; i < instr->TempCount(); ++i, ++count) {
block_assessments->Drop(*instr->TempAt(i));
}
if (instr->IsCall()) {
block_assessments->DropRegisters();
}
if (instr->HasReferenceMap()) {
block_assessments->CheckReferenceMap(instr->reference_map());
}
for (size_t i = 0; i < instr->OutputCount(); ++i, ++count) {
int virtual_register = op_constraints[count].virtual_register_;
block_assessments->AddDefinition(*instr->OutputAt(i), virtual_register);
if (op_constraints[count].type_ == kRegisterAndSlot) {
const AllocatedOperand* reg_op =
AllocatedOperand::cast(instr->OutputAt(i));
MachineRepresentation rep = reg_op->representation();
const AllocatedOperand* stack_op = AllocatedOperand::New(
zone(), LocationOperand::LocationKind::STACK_SLOT, rep,
op_constraints[i].spilled_slot_);
block_assessments->AddDefinition(*stack_op, virtual_register);
}
}
}
// Now commit the assessments for this block. If there are any delayed
// assessments, ValidatePendingAssessment should see this block, too.
assessments_[block->rpo_number()] = block_assessments;
auto todo_iter = outstanding_assessments_.find(block->rpo_number());
if (todo_iter == outstanding_assessments_.end()) continue;
DelayedAssessments* todo = todo_iter->second;
for (auto pair : todo->map()) {
InstructionOperand op = pair.first;
int vreg = pair.second;
auto found_op = block_assessments->map().find(op);
CHECK(found_op != block_assessments->map().end());
// This block is a jump back to the loop header, ensure that the op hasn't
// become a stale reference during the blocks in the loop.
CHECK(!block_assessments->IsStaleReferenceStackSlot(op));
switch (found_op->second->kind()) {
case Final:
CHECK_EQ(FinalAssessment::cast(found_op->second)->virtual_register(),
vreg);
break;
case Pending:
ValidatePendingAssessment(block->rpo_number(), op, block_assessments,
PendingAssessment::cast(found_op->second),
vreg);
break;
}
}
}
}
} // namespace compiler
} // namespace internal
} // namespace v8