diff options
Diffstat (limited to 'deps/v8/src/compiler/move-optimizer.cc')
| -rw-r--r-- | deps/v8/src/compiler/move-optimizer.cc | 205 |
1 files changed, 205 insertions, 0 deletions
diff --git a/deps/v8/src/compiler/move-optimizer.cc b/deps/v8/src/compiler/move-optimizer.cc new file mode 100644 index 0000000000..330f32f65d --- /dev/null +++ b/deps/v8/src/compiler/move-optimizer.cc @@ -0,0 +1,205 @@ +// 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 { + +MoveOptimizer::MoveOptimizer(Zone* local_zone, InstructionSequence* code) + : local_zone_(local_zone), + code_(code), + temp_vector_0_(local_zone), + temp_vector_1_(local_zone) {} + + +void MoveOptimizer::Run() { + // First smash all consecutive moves into the left most move slot. + for (auto* block : code()->instruction_blocks()) { + GapInstruction* prev_gap = nullptr; + for (int index = block->code_start(); index < block->code_end(); ++index) { + auto instr = code()->instructions()[index]; + if (!instr->IsGapMoves()) { + if (instr->IsSourcePosition() || instr->IsNop()) continue; + FinalizeMoves(&temp_vector_0_, &temp_vector_1_, prev_gap); + prev_gap = nullptr; + continue; + } + auto gap = GapInstruction::cast(instr); + // Find first non-empty slot. + int i = GapInstruction::FIRST_INNER_POSITION; + for (; i <= GapInstruction::LAST_INNER_POSITION; i++) { + auto move = gap->parallel_moves()[i]; + if (move == nullptr) continue; + auto move_ops = move->move_operands(); + auto op = move_ops->begin(); + for (; op != move_ops->end(); ++op) { + if (!op->IsRedundant()) break; + } + if (op == move_ops->end()) { + move_ops->Rewind(0); // Clear this redundant move. + } else { + break; // Found index of first non-redundant move. + } + } + // Nothing to do here. + if (i == GapInstruction::LAST_INNER_POSITION + 1) { + if (prev_gap != nullptr) { + // Slide prev_gap down so we always know where to look for it. + std::swap(prev_gap->parallel_moves()[0], gap->parallel_moves()[0]); + prev_gap = gap; + } + continue; + } + // Move the first non-empty gap to position 0. + std::swap(gap->parallel_moves()[0], gap->parallel_moves()[i]); + auto left = gap->parallel_moves()[0]; + // Compress everything into position 0. + for (++i; i <= GapInstruction::LAST_INNER_POSITION; ++i) { + auto move = gap->parallel_moves()[i]; + if (move == nullptr) continue; + CompressMoves(&temp_vector_0_, left, move); + } + if (prev_gap != nullptr) { + // Smash left into prev_gap, killing left. + auto pred_moves = prev_gap->parallel_moves()[0]; + CompressMoves(&temp_vector_0_, pred_moves, left); + std::swap(prev_gap->parallel_moves()[0], gap->parallel_moves()[0]); + } + prev_gap = gap; + } + FinalizeMoves(&temp_vector_0_, &temp_vector_1_, prev_gap); + } +} + + +static MoveOperands* PrepareInsertAfter(ParallelMove* left, MoveOperands* move, + Zone* zone) { + auto move_ops = left->move_operands(); + MoveOperands* replacement = nullptr; + MoveOperands* to_eliminate = nullptr; + for (auto curr = move_ops->begin(); curr != move_ops->end(); ++curr) { + if (curr->IsEliminated()) continue; + if (curr->destination()->Equals(move->source())) { + DCHECK_EQ(nullptr, replacement); + replacement = curr; + if (to_eliminate != nullptr) break; + } else if (curr->destination()->Equals(move->destination())) { + DCHECK_EQ(nullptr, to_eliminate); + to_eliminate = curr; + if (replacement != nullptr) break; + } + } + DCHECK(!(replacement == to_eliminate && replacement != nullptr)); + if (replacement != nullptr) { + auto new_source = new (zone) InstructionOperand( + replacement->source()->kind(), replacement->source()->index()); + move->set_source(new_source); + } + return to_eliminate; +} + + +void MoveOptimizer::CompressMoves(MoveOpVector* eliminated, ParallelMove* left, + ParallelMove* right) { + DCHECK(eliminated->empty()); + auto move_ops = right->move_operands(); + // Modify the right moves in place and collect moves that will be killed by + // merging the two gaps. + for (auto op = move_ops->begin(); op != move_ops->end(); ++op) { + if (op->IsRedundant()) continue; + MoveOperands* to_eliminate = PrepareInsertAfter(left, op, code_zone()); + if (to_eliminate != nullptr) { + eliminated->push_back(to_eliminate); + } + } + // Eliminate dead moves. Must happen before insertion of new moves as the + // contents of eliminated are pointers into a list. + for (auto to_eliminate : *eliminated) { + to_eliminate->Eliminate(); + } + eliminated->clear(); + // Add all possibly modified moves from right side. + for (auto op = move_ops->begin(); op != move_ops->end(); ++op) { + if (op->IsRedundant()) continue; + left->move_operands()->Add(*op, code_zone()); + } + // Nuke right. + move_ops->Rewind(0); +} + + +void MoveOptimizer::FinalizeMoves(MoveOpVector* loads, MoveOpVector* new_moves, + GapInstruction* gap) { + DCHECK(loads->empty()); + DCHECK(new_moves->empty()); + if (gap == nullptr) return; + // Split multiple loads of the same constant or stack slot off into the second + // slot and keep remaining moves in the first slot. + auto move_ops = gap->parallel_moves()[0]->move_operands(); + for (auto move = move_ops->begin(); move != move_ops->end(); ++move) { + if (move->IsRedundant()) { + move->Eliminate(); + continue; + } + if (!(move->source()->IsConstant() || move->source()->IsStackSlot() || + move->source()->IsDoubleStackSlot())) + continue; + // Search for existing move to this slot. + MoveOperands* found = nullptr; + for (auto load : *loads) { + if (load->source()->Equals(move->source())) { + found = load; + break; + } + } + // Not found so insert. + if (found == nullptr) { + loads->push_back(move); + // Replace source with copy for later use. + auto dest = move->destination(); + move->set_destination(new (code_zone()) + InstructionOperand(dest->kind(), dest->index())); + continue; + } + if ((found->destination()->IsStackSlot() || + found->destination()->IsDoubleStackSlot()) && + !(move->destination()->IsStackSlot() || + move->destination()->IsDoubleStackSlot())) { + // Found a better source for this load. Smash it in place to affect other + // loads that have already been split. + InstructionOperand::Kind found_kind = found->destination()->kind(); + int found_index = found->destination()->index(); + auto next_dest = + new (code_zone()) InstructionOperand(found_kind, found_index); + auto dest = move->destination(); + found->destination()->ConvertTo(dest->kind(), dest->index()); + move->set_destination(next_dest); + } + // move from load destination. + move->set_source(found->destination()); + new_moves->push_back(move); + } + loads->clear(); + if (new_moves->empty()) return; + // Insert all new moves into slot 1. + auto slot_1 = gap->GetOrCreateParallelMove( + static_cast<GapInstruction::InnerPosition>(1), code_zone()); + DCHECK(slot_1->move_operands()->is_empty()); + slot_1->move_operands()->AddBlock(MoveOperands(nullptr, nullptr), + static_cast<int>(new_moves->size()), + code_zone()); + auto it = slot_1->move_operands()->begin(); + for (auto new_move : *new_moves) { + std::swap(*new_move, *it); + ++it; + } + DCHECK_EQ(it, slot_1->move_operands()->end()); + new_moves->clear(); +} + +} // namespace compiler +} // namespace internal +} // namespace v8 |