blob: bde3f7fe36f8a1e4e0975f6c3bba4799e56c1c87 [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/move-optimizer.h"
namespace v8 {
namespace internal {
namespace compiler {
namespace {
typedef std::pair<InstructionOperand, InstructionOperand> MoveKey;
struct MoveKeyCompare {
bool operator()(const MoveKey& a, const MoveKey& b) const {
if (a.first.EqualsCanonicalized(b.first)) {
return a.second.CompareCanonicalized(b.second);
}
return a.first.CompareCanonicalized(b.first);
}
};
struct OperandCompare {
bool operator()(const InstructionOperand& a,
const InstructionOperand& b) const {
return a.CompareCanonicalized(b);
}
};
typedef ZoneMap<MoveKey, unsigned, MoveKeyCompare> MoveMap;
typedef ZoneSet<InstructionOperand, CompareOperandModuloType> OperandSet;
bool GapsCanMoveOver(Instruction* instr, Zone* zone) {
if (instr->IsNop()) return true;
if (instr->ClobbersTemps() || instr->ClobbersRegisters() ||
instr->ClobbersDoubleRegisters()) {
return false;
}
if (instr->arch_opcode() != ArchOpcode::kArchNop) return false;
ZoneSet<InstructionOperand, OperandCompare> operands(zone);
for (size_t i = 0; i < instr->InputCount(); ++i) {
operands.insert(*instr->InputAt(i));
}
for (size_t i = 0; i < instr->OutputCount(); ++i) {
operands.insert(*instr->OutputAt(i));
}
for (size_t i = 0; i < instr->TempCount(); ++i) {
operands.insert(*instr->TempAt(i));
}
for (int i = Instruction::GapPosition::FIRST_GAP_POSITION;
i <= Instruction::GapPosition::LAST_GAP_POSITION; ++i) {
ParallelMove* moves = instr->parallel_moves()[i];
if (moves == nullptr) continue;
for (MoveOperands* move : *moves) {
if (operands.count(move->source()) > 0 ||
operands.count(move->destination()) > 0) {
return false;
}
}
}
return true;
}
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),
to_finalize_(local_zone),
local_vector_(local_zone) {}
void MoveOptimizer::Run() {
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 : to_finalize_) {
FinalizeMoves(gap);
}
}
void MoveOptimizer::CompressMoves(ParallelMove* left, ParallelMove* 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;
MoveOperands* to_eliminate = left->PrepareInsertAfter(move);
if (to_eliminate != nullptr) eliminated.push_back(to_eliminate);
}
// 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());
}
// Smash all consecutive moves into the left most move slot and accumulate them
// as much as possible across instructions.
void MoveOptimizer::CompressBlock(InstructionBlock* block) {
Instruction* prev_instr = nullptr;
for (int index = block->code_start(); index < block->code_end(); ++index) {
Instruction* instr = code()->instructions()[index];
int i = FindFirstNonEmptySlot(instr);
bool has_moves = i <= Instruction::LAST_GAP_POSITION;
if (i == Instruction::LAST_GAP_POSITION) {
std::swap(instr->parallel_moves()[Instruction::FIRST_GAP_POSITION],
instr->parallel_moves()[Instruction::LAST_GAP_POSITION]);
} else if (i == Instruction::FIRST_GAP_POSITION) {
CompressMoves(instr->parallel_moves()[Instruction::FIRST_GAP_POSITION],
instr->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 =
instr->parallel_moves()[Instruction::FIRST_GAP_POSITION];
ParallelMove* last =
instr->parallel_moves()[Instruction::LAST_GAP_POSITION];
USE(last);
DCHECK(!has_moves ||
(first != nullptr && (last == nullptr || last->empty())));
if (prev_instr != nullptr) {
if (has_moves) {
// Smash first into prev_instr, killing left.
ParallelMove* pred_moves = prev_instr->parallel_moves()[0];
CompressMoves(pred_moves, first);
}
// Slide prev_instr down so we always know where to look for it.
std::swap(prev_instr->parallel_moves()[0], instr->parallel_moves()[0]);
}
prev_instr = instr->parallel_moves()[0] == nullptr ? nullptr : instr;
if (GapsCanMoveOver(instr, local_zone())) continue;
if (prev_instr != nullptr) {
to_finalize_.push_back(prev_instr);
prev_instr = nullptr;
}
}
if (prev_instr != nullptr) {
to_finalize_.push_back(prev_instr);
}
}
const Instruction* MoveOptimizer::LastInstruction(
const InstructionBlock* block) const {
return code()->instructions()[block->last_instruction_index()];
}
void MoveOptimizer::OptimizeMerge(InstructionBlock* block) {
DCHECK(block->PredecessorCount() > 1);
// 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);
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 ZonePool 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 != move_map.size()) return;
// Find insertion point.
Instruction* instr = nullptr;
for (int i = block->first_instruction_index();
i <= block->last_instruction_index(); ++i) {
instr = code()->instructions()[i];
if (!GapsCanMoveOver(instr, local_zone()) || !instr->AreMovesRedundant())
break;
}
DCHECK_NOT_NULL(instr);
bool gap_initialized = true;
if (instr->parallel_moves()[0] == nullptr ||
instr->parallel_moves()[0]->empty()) {
to_finalize_.push_back(instr);
} else {
// 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);
USE(it);
DCHECK(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]);
}
}
namespace {
bool IsSlot(const InstructionOperand& op) {
return op.IsStackSlot() || op.IsDoubleStackSlot();
}
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());
// Find all the loads.
for (MoveOperands* move : *instr->parallel_moves()[0]) {
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