// 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/move-optimizer.h"
|
|
namespace v8 {
|
namespace internal {
|
namespace compiler {
|
|
namespace {
|
|
struct MoveKey {
|
InstructionOperand source;
|
InstructionOperand destination;
|
};
|
|
struct MoveKeyCompare {
|
bool operator()(const MoveKey& a, const MoveKey& b) const {
|
if (a.source.EqualsCanonicalized(b.source)) {
|
return a.destination.CompareCanonicalized(b.destination);
|
}
|
return a.source.CompareCanonicalized(b.source);
|
}
|
};
|
|
typedef ZoneMap<MoveKey, unsigned, MoveKeyCompare> MoveMap;
|
|
class OperandSet {
|
public:
|
explicit OperandSet(ZoneVector<InstructionOperand>* buffer)
|
: set_(buffer), fp_reps_(0) {
|
buffer->clear();
|
}
|
|
void InsertOp(const InstructionOperand& op) {
|
set_->push_back(op);
|
|
if (!kSimpleFPAliasing && op.IsFPRegister())
|
fp_reps_ |= RepBit(LocationOperand::cast(op).representation());
|
}
|
|
bool Contains(const InstructionOperand& op) const {
|
for (const InstructionOperand& elem : *set_) {
|
if (elem.EqualsCanonicalized(op)) return true;
|
}
|
return false;
|
}
|
|
bool ContainsOpOrAlias(const InstructionOperand& op) const {
|
if (Contains(op)) return true;
|
|
if (!kSimpleFPAliasing && op.IsFPRegister()) {
|
// Platforms where FP registers have complex aliasing need extra checks.
|
const LocationOperand& loc = LocationOperand::cast(op);
|
MachineRepresentation rep = loc.representation();
|
// If haven't encountered mixed rep FP registers, skip the extra checks.
|
if (!HasMixedFPReps(fp_reps_ | RepBit(rep))) return false;
|
|
// Check register against aliasing registers of other FP representations.
|
MachineRepresentation other_rep1, other_rep2;
|
switch (rep) {
|
case MachineRepresentation::kFloat32:
|
other_rep1 = MachineRepresentation::kFloat64;
|
other_rep2 = MachineRepresentation::kSimd128;
|
break;
|
case MachineRepresentation::kFloat64:
|
other_rep1 = MachineRepresentation::kFloat32;
|
other_rep2 = MachineRepresentation::kSimd128;
|
break;
|
case MachineRepresentation::kSimd128:
|
other_rep1 = MachineRepresentation::kFloat32;
|
other_rep2 = MachineRepresentation::kFloat64;
|
break;
|
default:
|
UNREACHABLE();
|
break;
|
}
|
const RegisterConfiguration* config = RegisterConfiguration::Default();
|
int base = -1;
|
int aliases =
|
config->GetAliases(rep, loc.register_code(), other_rep1, &base);
|
DCHECK(aliases > 0 || (aliases == 0 && base == -1));
|
while (aliases--) {
|
if (Contains(AllocatedOperand(LocationOperand::REGISTER, other_rep1,
|
base + aliases))) {
|
return true;
|
}
|
}
|
aliases = config->GetAliases(rep, loc.register_code(), other_rep2, &base);
|
DCHECK(aliases > 0 || (aliases == 0 && base == -1));
|
while (aliases--) {
|
if (Contains(AllocatedOperand(LocationOperand::REGISTER, other_rep2,
|
base + aliases))) {
|
return true;
|
}
|
}
|
}
|
return false;
|
}
|
|
private:
|
static int RepBit(MachineRepresentation rep) {
|
return 1 << static_cast<int>(rep);
|
}
|
|
static bool HasMixedFPReps(int reps) {
|
return reps && !base::bits::IsPowerOfTwo(reps);
|
}
|
|
ZoneVector<InstructionOperand>* set_;
|
int fp_reps_;
|
};
|
|
int FindFirstNonEmptySlot(const Instruction* instr) {
|
int i = Instruction::FIRST_GAP_POSITION;
|
for (; i <= Instruction::LAST_GAP_POSITION; i++) {
|
ParallelMove* moves = instr->parallel_moves()[i];
|
if (moves == nullptr) continue;
|
for (MoveOperands* move : *moves) {
|
if (!move->IsRedundant()) return i;
|
move->Eliminate();
|
}
|
moves->clear(); // Clear this redundant move.
|
}
|
return i;
|
}
|
|
} // namespace
|
|
MoveOptimizer::MoveOptimizer(Zone* local_zone, InstructionSequence* code)
|
: local_zone_(local_zone),
|
code_(code),
|
local_vector_(local_zone),
|
operand_buffer1(local_zone),
|
operand_buffer2(local_zone) {}
|
|
void MoveOptimizer::Run() {
|
for (Instruction* instruction : code()->instructions()) {
|
CompressGaps(instruction);
|
}
|
for (InstructionBlock* block : code()->instruction_blocks()) {
|
CompressBlock(block);
|
}
|
for (InstructionBlock* block : code()->instruction_blocks()) {
|
if (block->PredecessorCount() <= 1) continue;
|
if (!block->IsDeferred()) {
|
bool has_only_deferred = true;
|
for (RpoNumber& pred_id : block->predecessors()) {
|
if (!code()->InstructionBlockAt(pred_id)->IsDeferred()) {
|
has_only_deferred = false;
|
break;
|
}
|
}
|
// This would pull down common moves. If the moves occur in deferred
|
// blocks, and the closest common successor is not deferred, we lose the
|
// optimization of just spilling/filling in deferred blocks, when the
|
// current block is not deferred.
|
if (has_only_deferred) continue;
|
}
|
OptimizeMerge(block);
|
}
|
for (Instruction* gap : code()->instructions()) {
|
FinalizeMoves(gap);
|
}
|
}
|
|
void MoveOptimizer::RemoveClobberedDestinations(Instruction* instruction) {
|
if (instruction->IsCall()) return;
|
ParallelMove* moves = instruction->parallel_moves()[0];
|
if (moves == nullptr) return;
|
|
DCHECK(instruction->parallel_moves()[1] == nullptr ||
|
instruction->parallel_moves()[1]->empty());
|
|
OperandSet outputs(&operand_buffer1);
|
OperandSet inputs(&operand_buffer2);
|
|
// Outputs and temps are treated together as potentially clobbering a
|
// destination operand.
|
for (size_t i = 0; i < instruction->OutputCount(); ++i) {
|
outputs.InsertOp(*instruction->OutputAt(i));
|
}
|
for (size_t i = 0; i < instruction->TempCount(); ++i) {
|
outputs.InsertOp(*instruction->TempAt(i));
|
}
|
|
// Input operands block elisions.
|
for (size_t i = 0; i < instruction->InputCount(); ++i) {
|
inputs.InsertOp(*instruction->InputAt(i));
|
}
|
|
// Elide moves made redundant by the instruction.
|
for (MoveOperands* move : *moves) {
|
if (outputs.ContainsOpOrAlias(move->destination()) &&
|
!inputs.ContainsOpOrAlias(move->destination())) {
|
move->Eliminate();
|
}
|
}
|
|
// The ret instruction makes any assignment before it unnecessary, except for
|
// the one for its input.
|
if (instruction->IsRet() || instruction->IsTailCall()) {
|
for (MoveOperands* move : *moves) {
|
if (!inputs.ContainsOpOrAlias(move->destination())) {
|
move->Eliminate();
|
}
|
}
|
}
|
}
|
|
void MoveOptimizer::MigrateMoves(Instruction* to, Instruction* from) {
|
if (from->IsCall()) return;
|
|
ParallelMove* from_moves = from->parallel_moves()[0];
|
if (from_moves == nullptr || from_moves->empty()) return;
|
|
OperandSet dst_cant_be(&operand_buffer1);
|
OperandSet src_cant_be(&operand_buffer2);
|
|
// If an operand is an input to the instruction, we cannot move assignments
|
// where it appears on the LHS.
|
for (size_t i = 0; i < from->InputCount(); ++i) {
|
dst_cant_be.InsertOp(*from->InputAt(i));
|
}
|
// If an operand is output to the instruction, we cannot move assignments
|
// where it appears on the RHS, because we would lose its value before the
|
// instruction.
|
// Same for temp operands.
|
// The output can't appear on the LHS because we performed
|
// RemoveClobberedDestinations for the "from" instruction.
|
for (size_t i = 0; i < from->OutputCount(); ++i) {
|
src_cant_be.InsertOp(*from->OutputAt(i));
|
}
|
for (size_t i = 0; i < from->TempCount(); ++i) {
|
src_cant_be.InsertOp(*from->TempAt(i));
|
}
|
for (MoveOperands* move : *from_moves) {
|
if (move->IsRedundant()) continue;
|
// Assume dest has a value "V". If we have a "dest = y" move, then we can't
|
// move "z = dest", because z would become y rather than "V".
|
// We assume CompressMoves has happened before this, which means we don't
|
// have more than one assignment to dest.
|
src_cant_be.InsertOp(move->destination());
|
}
|
|
ZoneSet<MoveKey, MoveKeyCompare> move_candidates(local_zone());
|
// We start with all the moves that don't have conflicting source or
|
// destination operands are eligible for being moved down.
|
for (MoveOperands* move : *from_moves) {
|
if (move->IsRedundant()) continue;
|
if (!dst_cant_be.ContainsOpOrAlias(move->destination())) {
|
MoveKey key = {move->source(), move->destination()};
|
move_candidates.insert(key);
|
}
|
}
|
if (move_candidates.empty()) return;
|
|
// Stabilize the candidate set.
|
bool changed = false;
|
do {
|
changed = false;
|
for (auto iter = move_candidates.begin(); iter != move_candidates.end();) {
|
auto current = iter;
|
++iter;
|
InstructionOperand src = current->source;
|
if (src_cant_be.ContainsOpOrAlias(src)) {
|
src_cant_be.InsertOp(current->destination);
|
move_candidates.erase(current);
|
changed = true;
|
}
|
}
|
} while (changed);
|
|
ParallelMove to_move(local_zone());
|
for (MoveOperands* move : *from_moves) {
|
if (move->IsRedundant()) continue;
|
MoveKey key = {move->source(), move->destination()};
|
if (move_candidates.find(key) != move_candidates.end()) {
|
to_move.AddMove(move->source(), move->destination(), code_zone());
|
move->Eliminate();
|
}
|
}
|
if (to_move.empty()) return;
|
|
ParallelMove* dest =
|
to->GetOrCreateParallelMove(Instruction::GapPosition::START, code_zone());
|
|
CompressMoves(&to_move, dest);
|
DCHECK(dest->empty());
|
for (MoveOperands* m : to_move) {
|
dest->push_back(m);
|
}
|
}
|
|
void MoveOptimizer::CompressMoves(ParallelMove* left, MoveOpVector* right) {
|
if (right == nullptr) return;
|
|
MoveOpVector& eliminated = local_vector();
|
DCHECK(eliminated.empty());
|
|
if (!left->empty()) {
|
// Modify the right moves in place and collect moves that will be killed by
|
// merging the two gaps.
|
for (MoveOperands* move : *right) {
|
if (move->IsRedundant()) continue;
|
left->PrepareInsertAfter(move, &eliminated);
|
}
|
// Eliminate dead moves.
|
for (MoveOperands* to_eliminate : eliminated) {
|
to_eliminate->Eliminate();
|
}
|
eliminated.clear();
|
}
|
// Add all possibly modified moves from right side.
|
for (MoveOperands* move : *right) {
|
if (move->IsRedundant()) continue;
|
left->push_back(move);
|
}
|
// Nuke right.
|
right->clear();
|
DCHECK(eliminated.empty());
|
}
|
|
void MoveOptimizer::CompressGaps(Instruction* instruction) {
|
int i = FindFirstNonEmptySlot(instruction);
|
bool has_moves = i <= Instruction::LAST_GAP_POSITION;
|
USE(has_moves);
|
|
if (i == Instruction::LAST_GAP_POSITION) {
|
std::swap(instruction->parallel_moves()[Instruction::FIRST_GAP_POSITION],
|
instruction->parallel_moves()[Instruction::LAST_GAP_POSITION]);
|
} else if (i == Instruction::FIRST_GAP_POSITION) {
|
CompressMoves(
|
instruction->parallel_moves()[Instruction::FIRST_GAP_POSITION],
|
instruction->parallel_moves()[Instruction::LAST_GAP_POSITION]);
|
}
|
// We either have no moves, or, after swapping or compressing, we have
|
// all the moves in the first gap position, and none in the second/end gap
|
// position.
|
ParallelMove* first =
|
instruction->parallel_moves()[Instruction::FIRST_GAP_POSITION];
|
ParallelMove* last =
|
instruction->parallel_moves()[Instruction::LAST_GAP_POSITION];
|
USE(first);
|
USE(last);
|
|
DCHECK(!has_moves ||
|
(first != nullptr && (last == nullptr || last->empty())));
|
}
|
|
void MoveOptimizer::CompressBlock(InstructionBlock* block) {
|
int first_instr_index = block->first_instruction_index();
|
int last_instr_index = block->last_instruction_index();
|
|
// Start by removing gap assignments where the output of the subsequent
|
// instruction appears on LHS, as long as they are not needed by its input.
|
Instruction* prev_instr = code()->instructions()[first_instr_index];
|
RemoveClobberedDestinations(prev_instr);
|
|
for (int index = first_instr_index + 1; index <= last_instr_index; ++index) {
|
Instruction* instr = code()->instructions()[index];
|
// Migrate to the gap of prev_instr eligible moves from instr.
|
MigrateMoves(instr, prev_instr);
|
// Remove gap assignments clobbered by instr's output.
|
RemoveClobberedDestinations(instr);
|
prev_instr = instr;
|
}
|
}
|
|
|
const Instruction* MoveOptimizer::LastInstruction(
|
const InstructionBlock* block) const {
|
return code()->instructions()[block->last_instruction_index()];
|
}
|
|
|
void MoveOptimizer::OptimizeMerge(InstructionBlock* block) {
|
DCHECK_LT(1, block->PredecessorCount());
|
// Ensure that the last instruction in all incoming blocks don't contain
|
// things that would prevent moving gap moves across them.
|
for (RpoNumber& pred_index : block->predecessors()) {
|
const InstructionBlock* pred = code()->InstructionBlockAt(pred_index);
|
|
// If the predecessor has more than one successor, we shouldn't attempt to
|
// move down to this block (one of the successors) any of the gap moves,
|
// because their effect may be necessary to the other successors.
|
if (pred->SuccessorCount() > 1) return;
|
|
const Instruction* last_instr =
|
code()->instructions()[pred->last_instruction_index()];
|
if (last_instr->IsCall()) return;
|
if (last_instr->TempCount() != 0) return;
|
if (last_instr->OutputCount() != 0) return;
|
for (size_t i = 0; i < last_instr->InputCount(); ++i) {
|
const InstructionOperand* op = last_instr->InputAt(i);
|
if (!op->IsConstant() && !op->IsImmediate()) return;
|
}
|
}
|
// TODO(dcarney): pass a ZoneStats down for this?
|
MoveMap move_map(local_zone());
|
size_t correct_counts = 0;
|
// Accumulate set of shared moves.
|
for (RpoNumber& pred_index : block->predecessors()) {
|
const InstructionBlock* pred = code()->InstructionBlockAt(pred_index);
|
const Instruction* instr = LastInstruction(pred);
|
if (instr->parallel_moves()[0] == nullptr ||
|
instr->parallel_moves()[0]->empty()) {
|
return;
|
}
|
for (const MoveOperands* move : *instr->parallel_moves()[0]) {
|
if (move->IsRedundant()) continue;
|
InstructionOperand src = move->source();
|
InstructionOperand dst = move->destination();
|
MoveKey key = {src, dst};
|
auto res = move_map.insert(std::make_pair(key, 1));
|
if (!res.second) {
|
res.first->second++;
|
if (res.first->second == block->PredecessorCount()) {
|
correct_counts++;
|
}
|
}
|
}
|
}
|
if (move_map.empty() || correct_counts == 0) return;
|
|
// Find insertion point.
|
Instruction* instr = code()->instructions()[block->first_instruction_index()];
|
|
if (correct_counts != move_map.size()) {
|
// Moves that are unique to each predecessor won't be pushed to the common
|
// successor.
|
OperandSet conflicting_srcs(&operand_buffer1);
|
for (auto iter = move_map.begin(), end = move_map.end(); iter != end;) {
|
auto current = iter;
|
++iter;
|
if (current->second != block->PredecessorCount()) {
|
InstructionOperand dest = current->first.destination;
|
// Not all the moves in all the gaps are the same. Maybe some are. If
|
// there are such moves, we could move them, but the destination of the
|
// moves staying behind can't appear as a source of a common move,
|
// because the move staying behind will clobber this destination.
|
conflicting_srcs.InsertOp(dest);
|
move_map.erase(current);
|
}
|
}
|
|
bool changed = false;
|
do {
|
// If a common move can't be pushed to the common successor, then its
|
// destination also can't appear as source to any move being pushed.
|
changed = false;
|
for (auto iter = move_map.begin(), end = move_map.end(); iter != end;) {
|
auto current = iter;
|
++iter;
|
DCHECK_EQ(block->PredecessorCount(), current->second);
|
if (conflicting_srcs.ContainsOpOrAlias(current->first.source)) {
|
conflicting_srcs.InsertOp(current->first.destination);
|
move_map.erase(current);
|
changed = true;
|
}
|
}
|
} while (changed);
|
}
|
|
if (move_map.empty()) return;
|
|
DCHECK_NOT_NULL(instr);
|
bool gap_initialized = true;
|
if (instr->parallel_moves()[0] != nullptr &&
|
!instr->parallel_moves()[0]->empty()) {
|
// Will compress after insertion.
|
gap_initialized = false;
|
std::swap(instr->parallel_moves()[0], instr->parallel_moves()[1]);
|
}
|
ParallelMove* moves = instr->GetOrCreateParallelMove(
|
static_cast<Instruction::GapPosition>(0), code_zone());
|
// Delete relevant entries in predecessors and move everything to block.
|
bool first_iteration = true;
|
for (RpoNumber& pred_index : block->predecessors()) {
|
const InstructionBlock* pred = code()->InstructionBlockAt(pred_index);
|
for (MoveOperands* move : *LastInstruction(pred)->parallel_moves()[0]) {
|
if (move->IsRedundant()) continue;
|
MoveKey key = {move->source(), move->destination()};
|
auto it = move_map.find(key);
|
if (it != move_map.end()) {
|
if (first_iteration) {
|
moves->AddMove(move->source(), move->destination());
|
}
|
move->Eliminate();
|
}
|
}
|
first_iteration = false;
|
}
|
// Compress.
|
if (!gap_initialized) {
|
CompressMoves(instr->parallel_moves()[0], instr->parallel_moves()[1]);
|
}
|
CompressBlock(block);
|
}
|
|
|
namespace {
|
|
bool IsSlot(const InstructionOperand& op) {
|
return op.IsStackSlot() || op.IsFPStackSlot();
|
}
|
|
|
bool LoadCompare(const MoveOperands* a, const MoveOperands* b) {
|
if (!a->source().EqualsCanonicalized(b->source())) {
|
return a->source().CompareCanonicalized(b->source());
|
}
|
if (IsSlot(a->destination()) && !IsSlot(b->destination())) return false;
|
if (!IsSlot(a->destination()) && IsSlot(b->destination())) return true;
|
return a->destination().CompareCanonicalized(b->destination());
|
}
|
|
} // namespace
|
|
|
// Split multiple loads of the same constant or stack slot off into the second
|
// slot and keep remaining moves in the first slot.
|
void MoveOptimizer::FinalizeMoves(Instruction* instr) {
|
MoveOpVector& loads = local_vector();
|
DCHECK(loads.empty());
|
|
ParallelMove* parallel_moves = instr->parallel_moves()[0];
|
if (parallel_moves == nullptr) return;
|
// Find all the loads.
|
for (MoveOperands* move : *parallel_moves) {
|
if (move->IsRedundant()) continue;
|
if (move->source().IsConstant() || IsSlot(move->source())) {
|
loads.push_back(move);
|
}
|
}
|
if (loads.empty()) return;
|
// Group the loads by source, moving the preferred destination to the
|
// beginning of the group.
|
std::sort(loads.begin(), loads.end(), LoadCompare);
|
MoveOperands* group_begin = nullptr;
|
for (MoveOperands* load : loads) {
|
// New group.
|
if (group_begin == nullptr ||
|
!load->source().EqualsCanonicalized(group_begin->source())) {
|
group_begin = load;
|
continue;
|
}
|
// Nothing to be gained from splitting here.
|
if (IsSlot(group_begin->destination())) continue;
|
// Insert new move into slot 1.
|
ParallelMove* slot_1 = instr->GetOrCreateParallelMove(
|
static_cast<Instruction::GapPosition>(1), code_zone());
|
slot_1->AddMove(group_begin->destination(), load->destination());
|
load->Eliminate();
|
}
|
loads.clear();
|
}
|
|
} // namespace compiler
|
} // namespace internal
|
} // namespace v8
|
