From 3595176565a0b7ebbfc3bacd06109b528d5efa33 Mon Sep 17 00:00:00 2001 From: dcarney Date: Fri, 12 Dec 2014 03:15:13 -0800 Subject: [PATCH] [turbofan] improve register allocator testing framework R=bmeurer@chromium.org BUG= Review URL: https://codereview.chromium.org/800493002 Cr-Commit-Position: refs/heads/master@{#25794} --- src/compiler/pipeline.cc | 4 +- src/flag-definitions.h | 2 + .../compiler/instruction-sequence-unittest.cc | 71 ++++++++---- .../compiler/instruction-sequence-unittest.h | 25 +++- .../compiler/register-allocator-unittest.cc | 126 ++++++++++++++++++++- 5 files changed, 195 insertions(+), 33 deletions(-) diff --git a/src/compiler/pipeline.cc b/src/compiler/pipeline.cc index 2407d0d..4ca289c 100644 --- a/src/compiler/pipeline.cc +++ b/src/compiler/pipeline.cc @@ -1049,7 +1049,9 @@ void Pipeline::AllocateRegisters(const RegisterConfiguration* config, Run(); Run(); Run(); - Run(); + if (FLAG_turbo_move_optimization) { + Run(); + } if (FLAG_trace_turbo_graph) { OFStream os(stdout); diff --git a/src/flag-definitions.h b/src/flag-definitions.h index 3038c13..2efe08c 100644 --- a/src/flag-definitions.h +++ b/src/flag-definitions.h @@ -406,6 +406,8 @@ DEFINE_BOOL(turbo_reuse_spill_slots, false, "reuse spill slots in TurboFan") // TODO(dcarney): this is just for experimentation, remove when default. DEFINE_BOOL(turbo_delay_ssa_decon, false, "delay ssa deconstruction in TurboFan register allocator") +// TODO(dcarney): this is just for debugging, remove eventually. +DEFINE_BOOL(turbo_move_optimization, true, "optimize gap moves in TurboFan") DEFINE_BOOL(turbo_jt, true, "enable jump threading") DEFINE_INT(typed_array_max_size_in_heap, 64, diff --git a/test/unittests/compiler/instruction-sequence-unittest.cc b/test/unittests/compiler/instruction-sequence-unittest.cc index 05d3d0a..6f1ac94 100644 --- a/test/unittests/compiler/instruction-sequence-unittest.cc +++ b/test/unittests/compiler/instruction-sequence-unittest.cc @@ -184,30 +184,46 @@ InstructionSequenceTest::VReg InstructionSequenceTest::DefineConstant( int InstructionSequenceTest::EmitNop() { return Emit(NewIndex(), kArchNop); } -int InstructionSequenceTest::EmitI(TestOperand input_op_0) { - InstructionOperand* inputs[1]{ConvertInputOp(input_op_0)}; - return Emit(NewIndex(), kArchNop, 0, nullptr, 1, inputs); +static size_t CountInputs(size_t size, + InstructionSequenceTest::TestOperand* inputs) { + size_t i = 0; + for (; i < size; ++i) { + if (inputs[i].type_ == InstructionSequenceTest::kInvalid) break; + } + return i; +} + + +int InstructionSequenceTest::EmitI(size_t input_size, TestOperand* inputs) { + InstructionOperand** mapped_inputs = ConvertInputs(input_size, inputs); + return Emit(NewIndex(), kArchNop, 0, nullptr, input_size, mapped_inputs); +} + + +int InstructionSequenceTest::EmitI(TestOperand input_op_0, + TestOperand input_op_1, + TestOperand input_op_2, + TestOperand input_op_3) { + TestOperand inputs[] = {input_op_0, input_op_1, input_op_2, input_op_3}; + return EmitI(CountInputs(arraysize(inputs), inputs), inputs); } InstructionSequenceTest::VReg InstructionSequenceTest::EmitOI( - TestOperand output_op, TestOperand input_op_0) { + TestOperand output_op, size_t input_size, TestOperand* inputs) { VReg output_vreg = NewReg(); InstructionOperand* outputs[1]{ConvertOutputOp(output_vreg, output_op)}; - InstructionOperand* inputs[1]{ConvertInputOp(input_op_0)}; - Emit(output_vreg.value_, kArchNop, 1, outputs, 1, inputs); + InstructionOperand** mapped_inputs = ConvertInputs(input_size, inputs); + Emit(output_vreg.value_, kArchNop, 1, outputs, input_size, mapped_inputs); return output_vreg; } -InstructionSequenceTest::VReg InstructionSequenceTest::EmitOII( - TestOperand output_op, TestOperand input_op_0, TestOperand input_op_1) { - VReg output_vreg = NewReg(); - InstructionOperand* outputs[1]{ConvertOutputOp(output_vreg, output_op)}; - InstructionOperand* inputs[2]{ConvertInputOp(input_op_0), - ConvertInputOp(input_op_1)}; - Emit(output_vreg.value_, kArchNop, 1, outputs, 2, inputs); - return output_vreg; +InstructionSequenceTest::VReg InstructionSequenceTest::EmitOI( + TestOperand output_op, TestOperand input_op_0, TestOperand input_op_1, + TestOperand input_op_2, TestOperand input_op_3) { + TestOperand inputs[] = {input_op_0, input_op_1, input_op_2, input_op_3}; + return EmitOI(output_op, CountInputs(arraysize(inputs), inputs), inputs); } @@ -216,11 +232,7 @@ InstructionSequenceTest::VReg InstructionSequenceTest::EmitCall( VReg output_vreg = NewReg(); InstructionOperand* outputs[1]{ConvertOutputOp(output_vreg, output_op)}; CHECK(UnallocatedOperand::cast(outputs[0])->HasFixedPolicy()); - InstructionOperand** mapped_inputs = - zone()->NewArray(static_cast(input_size)); - for (size_t i = 0; i < input_size; ++i) { - mapped_inputs[i] = ConvertInputOp(inputs[i]); - } + InstructionOperand** mapped_inputs = ConvertInputs(input_size, inputs); Emit(output_vreg.value_, kArchCallCodeObject, 1, outputs, input_size, mapped_inputs, 0, nullptr, true); return output_vreg; @@ -231,11 +243,7 @@ InstructionSequenceTest::VReg InstructionSequenceTest::EmitCall( TestOperand output_op, TestOperand input_op_0, TestOperand input_op_1, TestOperand input_op_2, TestOperand input_op_3) { TestOperand inputs[] = {input_op_0, input_op_1, input_op_2, input_op_3}; - size_t size = 0; - for (; size < arraysize(inputs); ++size) { - if (inputs[size].type_ == kInvalid) break; - } - return EmitCall(output_op, size, inputs); + return EmitCall(output_op, CountInputs(arraysize(inputs), inputs), inputs); } @@ -315,6 +323,17 @@ InstructionOperand* InstructionSequenceTest::Unallocated( } +InstructionOperand** InstructionSequenceTest::ConvertInputs( + size_t input_size, TestOperand* inputs) { + InstructionOperand** mapped_inputs = + zone()->NewArray(static_cast(input_size)); + for (size_t i = 0; i < input_size; ++i) { + mapped_inputs[i] = ConvertInputOp(inputs[i]); + } + return mapped_inputs; +} + + InstructionOperand* InstructionSequenceTest::ConvertInputOp(TestOperand op) { if (op.type_ == kImmediate) { CHECK_EQ(op.vreg_.value_, kNoValue); @@ -325,6 +344,10 @@ InstructionOperand* InstructionSequenceTest::ConvertInputOp(TestOperand op) { case kNone: return Unallocated(op, UnallocatedOperand::NONE, UnallocatedOperand::USED_AT_START); + case kUnique: + return Unallocated(op, UnallocatedOperand::NONE); + case kUniqueRegister: + return Unallocated(op, UnallocatedOperand::MUST_HAVE_REGISTER); case kRegister: return Unallocated(op, UnallocatedOperand::MUST_HAVE_REGISTER, UnallocatedOperand::USED_AT_START); diff --git a/test/unittests/compiler/instruction-sequence-unittest.h b/test/unittests/compiler/instruction-sequence-unittest.h index 5258951..ce0a5b4 100644 --- a/test/unittests/compiler/instruction-sequence-unittest.h +++ b/test/unittests/compiler/instruction-sequence-unittest.h @@ -36,7 +36,9 @@ class InstructionSequenceTest : public TestWithZone { kFixedSlot, kImmediate, kNone, - kConstant + kConstant, + kUnique, + kUniqueRegister }; struct TestOperand { @@ -78,6 +80,12 @@ class InstructionSequenceTest : public TestWithZone { static TestOperand Use() { return Use(VReg()); } + static TestOperand Unique(VReg vreg) { return TestOperand(kUnique, vreg); } + + static TestOperand UniqueReg(VReg vreg) { + return TestOperand(kUniqueRegister, vreg); + } + enum BlockCompletionType { kBlockEnd, kFallThrough, kBranch, kJump }; struct BlockCompletion { @@ -134,10 +142,16 @@ class InstructionSequenceTest : public TestWithZone { VReg DefineConstant(int32_t imm = 0); int EmitNop(); - int EmitI(TestOperand input_op_0); - VReg EmitOI(TestOperand output_op, TestOperand input_op_0); - VReg EmitOII(TestOperand output_op, TestOperand input_op_0, - TestOperand input_op_1); + int EmitI(size_t input_size, TestOperand* inputs); + int EmitI(TestOperand input_op_0 = TestOperand(), + TestOperand input_op_1 = TestOperand(), + TestOperand input_op_2 = TestOperand(), + TestOperand input_op_3 = TestOperand()); + VReg EmitOI(TestOperand output_op, size_t input_size, TestOperand* inputs); + VReg EmitOI(TestOperand output_op, TestOperand input_op_0 = TestOperand(), + TestOperand input_op_1 = TestOperand(), + TestOperand input_op_2 = TestOperand(), + TestOperand input_op_3 = TestOperand()); VReg EmitCall(TestOperand output_op, size_t input_size, TestOperand* inputs); VReg EmitCall(TestOperand output_op, TestOperand input_op_0 = TestOperand(), TestOperand input_op_1 = TestOperand(), @@ -181,6 +195,7 @@ class InstructionSequenceTest : public TestWithZone { InstructionOperand* Unallocated(TestOperand op, UnallocatedOperand::BasicPolicy policy, int index); + InstructionOperand** ConvertInputs(size_t input_size, TestOperand* inputs); InstructionOperand* ConvertInputOp(TestOperand op); InstructionOperand* ConvertOutputOp(VReg vreg, TestOperand op); InstructionBlock* NewBlock(); diff --git a/test/unittests/compiler/register-allocator-unittest.cc b/test/unittests/compiler/register-allocator-unittest.cc index 44d4fef..8c90b4c 100644 --- a/test/unittests/compiler/register-allocator-unittest.cc +++ b/test/unittests/compiler/register-allocator-unittest.cc @@ -23,7 +23,7 @@ TEST_F(RegisterAllocatorTest, CanAllocateThreeRegisters) { StartBlock(); auto a_reg = Parameter(); auto b_reg = Parameter(); - auto c_reg = EmitOII(Reg(1), Reg(a_reg, 1), Reg(b_reg, 0)); + auto c_reg = EmitOI(Reg(1), Reg(a_reg, 1), Reg(b_reg, 0)); Return(c_reg); EndBlock(Last()); @@ -43,7 +43,7 @@ TEST_F(RegisterAllocatorTest, SimpleLoop) { StartBlock(); auto phi = Phi(i_reg); - auto ipp = EmitOII(Same(), Reg(phi), Use(DefineConstant())); + auto ipp = EmitOI(Same(), Reg(phi), Use(DefineConstant())); Extend(phi, ipp); EndBlock(Jump(0)); @@ -212,7 +212,7 @@ TEST_F(RegisterAllocatorTest, RegressionPhisNeedTooManyRegisters) { // Perform some computations. // something like phi[i] += const for (size_t i = 0; i < arraysize(parameters); ++i) { - auto result = EmitOII(Same(), Reg(phis[i]), Use(constant)); + auto result = EmitOI(Same(), Reg(phis[i]), Use(constant)); Extend(phis[i], result); } @@ -274,6 +274,126 @@ TEST_F(RegisterAllocatorTest, MoveLotsOfConstants) { Allocate(); } + +TEST_F(RegisterAllocatorTest, SplitBeforeInstruction) { + const int kNumRegs = 6; + SetNumRegs(kNumRegs, kNumRegs); + + StartBlock(); + + // Stack parameters/spilled values. + auto p_0 = Define(Slot(-1)); + auto p_1 = Define(Slot(-2)); + + // Fill registers. + VReg values[kNumRegs]; + for (size_t i = 0; i < arraysize(values); ++i) { + values[i] = Define(Reg(static_cast(i))); + } + + // values[0] will be split in the second half of this instruction. + // Models Intel mod instructions. + EmitOI(Reg(0), Reg(p_0, 1), UniqueReg(p_1)); + EmitI(Reg(values[0], 0)); + EndBlock(Last()); + + Allocate(); +} + + +TEST_F(RegisterAllocatorTest, NestedDiamondPhiMerge) { + // Outer diamond. + StartBlock(); + EndBlock(Branch(Imm(), 1, 5)); + + // Diamond 1 + StartBlock(); + EndBlock(Branch(Imm(), 1, 2)); + + StartBlock(); + auto ll = Define(Reg()); + EndBlock(Jump(2)); + + StartBlock(); + auto lr = Define(Reg()); + EndBlock(); + + StartBlock(); + auto l_phi = Phi(ll, lr); + EndBlock(Jump(5)); + + // Diamond 2 + StartBlock(); + EndBlock(Branch(Imm(), 1, 2)); + + StartBlock(); + auto rl = Define(Reg()); + EndBlock(Jump(2)); + + StartBlock(); + auto rr = Define(Reg()); + EndBlock(); + + StartBlock(); + auto r_phi = Phi(rl, rr); + EndBlock(); + + // Outer diamond merge. + StartBlock(); + auto phi = Phi(l_phi, r_phi); + Return(Reg(phi)); + EndBlock(); + + Allocate(); +} + + +TEST_F(RegisterAllocatorTest, NestedDiamondPhiMergeDifferent) { + // Outer diamond. + StartBlock(); + EndBlock(Branch(Imm(), 1, 5)); + + // Diamond 1 + StartBlock(); + EndBlock(Branch(Imm(), 1, 2)); + + StartBlock(); + auto ll = Define(Reg(0)); + EndBlock(Jump(2)); + + StartBlock(); + auto lr = Define(Reg(1)); + EndBlock(); + + StartBlock(); + auto l_phi = Phi(ll, lr); + EndBlock(Jump(5)); + + // Diamond 2 + StartBlock(); + EndBlock(Branch(Imm(), 1, 2)); + + StartBlock(); + auto rl = Define(Reg(2)); + EndBlock(Jump(2)); + + StartBlock(); + auto rr = Define(Reg(3)); + EndBlock(); + + StartBlock(); + auto r_phi = Phi(rl, rr); + EndBlock(); + + // Outer diamond merge. + StartBlock(); + auto phi = Phi(l_phi, r_phi); + Return(Reg(phi)); + EndBlock(); + + Allocate(); +} + } // namespace compiler } // namespace internal } // namespace v8 -- 2.7.4