| // 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" |
| #include "test/unittests/compiler/instruction-sequence-unittest.h" |
| |
| namespace v8 { |
| namespace internal { |
| namespace compiler { |
| |
| class MoveOptimizerTest : public InstructionSequenceTest { |
| public: |
| Instruction* LastInstruction() { return sequence()->instructions().back(); } |
| |
| void AddMove(Instruction* instr, TestOperand from, TestOperand to, |
| Instruction::GapPosition pos = Instruction::START) { |
| auto parallel_move = instr->GetOrCreateParallelMove(pos, zone()); |
| parallel_move->AddMove(ConvertMoveArg(from), ConvertMoveArg(to)); |
| } |
| |
| int NonRedundantSize(ParallelMove* moves) { |
| int i = 0; |
| for (auto move : *moves) { |
| if (move->IsRedundant()) continue; |
| i++; |
| } |
| return i; |
| } |
| |
| bool Contains(ParallelMove* moves, TestOperand from_op, TestOperand to_op) { |
| auto from = ConvertMoveArg(from_op); |
| auto to = ConvertMoveArg(to_op); |
| for (auto move : *moves) { |
| if (move->IsRedundant()) continue; |
| if (move->source().Equals(from) && move->destination().Equals(to)) { |
| return true; |
| } |
| } |
| return false; |
| } |
| |
| // TODO(dcarney): add a verifier. |
| void Optimize() { |
| WireBlocks(); |
| if (FLAG_trace_turbo) { |
| OFStream os(stdout); |
| PrintableInstructionSequence printable = {config(), sequence()}; |
| os << "----- Instruction sequence before move optimization -----\n" |
| << printable; |
| } |
| MoveOptimizer move_optimizer(zone(), sequence()); |
| move_optimizer.Run(); |
| if (FLAG_trace_turbo) { |
| OFStream os(stdout); |
| PrintableInstructionSequence printable = {config(), sequence()}; |
| os << "----- Instruction sequence after move optimization -----\n" |
| << printable; |
| } |
| } |
| |
| private: |
| InstructionOperand ConvertMoveArg(TestOperand op) { |
| CHECK_EQ(kNoValue, op.vreg_.value_); |
| CHECK_NE(kNoValue, op.value_); |
| switch (op.type_) { |
| case kConstant: |
| return ConstantOperand(op.value_); |
| case kFixedSlot: |
| return AllocatedOperand(LocationOperand::STACK_SLOT, |
| MachineRepresentation::kWord32, op.value_); |
| case kFixedRegister: |
| CHECK(0 <= op.value_ && op.value_ < num_general_registers()); |
| return AllocatedOperand(LocationOperand::REGISTER, |
| MachineRepresentation::kWord32, op.value_); |
| case kExplicit: |
| CHECK(0 <= op.value_ && op.value_ < num_general_registers()); |
| return ExplicitOperand(LocationOperand::REGISTER, |
| MachineRepresentation::kWord32, op.value_); |
| default: |
| break; |
| } |
| CHECK(false); |
| return InstructionOperand(); |
| } |
| }; |
| |
| |
| TEST_F(MoveOptimizerTest, RemovesRedundant) { |
| StartBlock(); |
| auto first_instr = EmitNop(); |
| AddMove(first_instr, Reg(0), Reg(1)); |
| auto last_instr = EmitNop(); |
| AddMove(last_instr, Reg(1), Reg(0)); |
| EndBlock(Last()); |
| |
| Optimize(); |
| |
| CHECK_EQ(0, NonRedundantSize(first_instr->parallel_moves()[0])); |
| auto move = last_instr->parallel_moves()[0]; |
| CHECK_EQ(1, NonRedundantSize(move)); |
| CHECK(Contains(move, Reg(0), Reg(1))); |
| } |
| |
| |
| TEST_F(MoveOptimizerTest, RemovesRedundantExplicit) { |
| int first_reg_index = |
| RegisterConfiguration::ArchDefault(RegisterConfiguration::TURBOFAN) |
| ->GetAllocatableGeneralCode(0); |
| int second_reg_index = |
| RegisterConfiguration::ArchDefault(RegisterConfiguration::TURBOFAN) |
| ->GetAllocatableGeneralCode(1); |
| |
| StartBlock(); |
| auto first_instr = EmitNop(); |
| AddMove(first_instr, Reg(first_reg_index), ExplicitReg(second_reg_index)); |
| auto last_instr = EmitNop(); |
| AddMove(last_instr, Reg(second_reg_index), Reg(first_reg_index)); |
| EndBlock(Last()); |
| |
| Optimize(); |
| |
| CHECK_EQ(0, NonRedundantSize(first_instr->parallel_moves()[0])); |
| auto move = last_instr->parallel_moves()[0]; |
| CHECK_EQ(1, NonRedundantSize(move)); |
| CHECK(Contains(move, Reg(first_reg_index), ExplicitReg(second_reg_index))); |
| } |
| |
| |
| TEST_F(MoveOptimizerTest, SplitsConstants) { |
| StartBlock(); |
| EndBlock(Last()); |
| |
| auto gap = LastInstruction(); |
| AddMove(gap, Const(1), Slot(0)); |
| AddMove(gap, Const(1), Slot(1)); |
| AddMove(gap, Const(1), Reg(0)); |
| AddMove(gap, Const(1), Slot(2)); |
| |
| Optimize(); |
| |
| auto move = gap->parallel_moves()[0]; |
| CHECK_EQ(1, NonRedundantSize(move)); |
| CHECK(Contains(move, Const(1), Reg(0))); |
| |
| move = gap->parallel_moves()[1]; |
| CHECK_EQ(3, NonRedundantSize(move)); |
| CHECK(Contains(move, Reg(0), Slot(0))); |
| CHECK(Contains(move, Reg(0), Slot(1))); |
| CHECK(Contains(move, Reg(0), Slot(2))); |
| } |
| |
| |
| TEST_F(MoveOptimizerTest, SimpleMerge) { |
| StartBlock(); |
| EndBlock(Branch(Imm(), 1, 2)); |
| |
| StartBlock(); |
| EndBlock(Jump(2)); |
| AddMove(LastInstruction(), Reg(0), Reg(1)); |
| |
| StartBlock(); |
| EndBlock(Jump(1)); |
| AddMove(LastInstruction(), Reg(0), Reg(1)); |
| |
| StartBlock(); |
| EndBlock(Last()); |
| |
| auto last = LastInstruction(); |
| |
| Optimize(); |
| |
| auto move = last->parallel_moves()[0]; |
| CHECK_EQ(1, NonRedundantSize(move)); |
| CHECK(Contains(move, Reg(0), Reg(1))); |
| } |
| |
| |
| TEST_F(MoveOptimizerTest, SimpleMergeCycle) { |
| StartBlock(); |
| EndBlock(Branch(Imm(), 1, 2)); |
| |
| StartBlock(); |
| EndBlock(Jump(2)); |
| auto gap_0 = LastInstruction(); |
| AddMove(gap_0, Reg(0), Reg(1)); |
| AddMove(LastInstruction(), Reg(1), Reg(0)); |
| |
| StartBlock(); |
| EndBlock(Jump(1)); |
| auto gap_1 = LastInstruction(); |
| AddMove(gap_1, Reg(0), Reg(1)); |
| AddMove(gap_1, Reg(1), Reg(0)); |
| |
| StartBlock(); |
| EndBlock(Last()); |
| |
| auto last = LastInstruction(); |
| |
| Optimize(); |
| |
| CHECK(gap_0->AreMovesRedundant()); |
| CHECK(gap_1->AreMovesRedundant()); |
| auto move = last->parallel_moves()[0]; |
| CHECK_EQ(2, NonRedundantSize(move)); |
| CHECK(Contains(move, Reg(0), Reg(1))); |
| CHECK(Contains(move, Reg(1), Reg(0))); |
| } |
| |
| |
| TEST_F(MoveOptimizerTest, GapsCanMoveOverInstruction) { |
| StartBlock(); |
| int const_index = 1; |
| DefineConstant(const_index); |
| Instruction* ctant_def = LastInstruction(); |
| AddMove(ctant_def, Reg(1), Reg(0)); |
| |
| Instruction* last = EmitNop(); |
| AddMove(last, Const(const_index), Reg(0)); |
| AddMove(last, Reg(0), Reg(1)); |
| EndBlock(Last()); |
| Optimize(); |
| |
| ParallelMove* inst1_start = |
| ctant_def->GetParallelMove(Instruction::GapPosition::START); |
| ParallelMove* inst1_end = |
| ctant_def->GetParallelMove(Instruction::GapPosition::END); |
| ParallelMove* last_start = |
| last->GetParallelMove(Instruction::GapPosition::START); |
| CHECK(inst1_start == nullptr || inst1_start->size() == 0); |
| CHECK(inst1_end == nullptr || inst1_end->size() == 0); |
| CHECK(last_start->size() == 2); |
| int redundants = 0; |
| int assignment = 0; |
| for (MoveOperands* move : *last_start) { |
| if (move->IsRedundant()) { |
| ++redundants; |
| } else { |
| ++assignment; |
| CHECK(move->destination().IsRegister()); |
| CHECK(move->source().IsConstant()); |
| } |
| } |
| CHECK_EQ(1, redundants); |
| CHECK_EQ(1, assignment); |
| } |
| |
| |
| } // namespace compiler |
| } // namespace internal |
| } // namespace v8 |