Move register allocation unittests and constrain owners

test/unittests/compiler/regalloc/register-allocator-unittest.cc

 // 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/pipeline.h"
 #include "test/unittests/compiler/instruction-sequence-unittest.h"
 
 namespace v8 {
 namespace internal {
 namespace compiler {
 
-
 namespace {
 
 // We can't just use the size of the moves collection, because of
 // redundant moves which need to be discounted.
 int GetMoveCount(const ParallelMove& moves) {
   int move_count = 0;
   for (auto move : moves) {
     if (move->IsEliminated() || move->IsRedundant()) continue;
     ++move_count;
   }
   return move_count;
 }
 
-
 bool AreOperandsOfSameType(
     const AllocatedOperand& op,
     const InstructionSequenceTest::TestOperand& test_op) {
   bool test_op_is_reg =
       (test_op.type_ ==
            InstructionSequenceTest::TestOperandType::kFixedRegister ||
        test_op.type_ == InstructionSequenceTest::TestOperandType::kRegister);
 
   return (op.IsRegister() && test_op_is_reg) ||
          (op.IsStackSlot() && !test_op_is_reg);
 }
 
-
 bool AllocatedOperandMatches(
     const AllocatedOperand& op,
     const InstructionSequenceTest::TestOperand& test_op) {
   return AreOperandsOfSameType(op, test_op) &&
          ((op.IsRegister() ? op.GetRegister().code() : op.index()) ==
               test_op.value_ ||
           test_op.value_ == InstructionSequenceTest::kNoValue);
 }
 
-
 int GetParallelMoveCount(int instr_index, Instruction::GapPosition gap_pos,
                          const InstructionSequence* sequence) {
   const ParallelMove* moves =
       sequence->InstructionAt(instr_index)->GetParallelMove(gap_pos);
   if (moves == nullptr) return 0;
   return GetMoveCount(*moves);
 }
 
-
 bool IsParallelMovePresent(int instr_index, Instruction::GapPosition gap_pos,
                            const InstructionSequence* sequence,
                            const InstructionSequenceTest::TestOperand& src,
                            const InstructionSequenceTest::TestOperand& dest) {
   const ParallelMove* moves =
       sequence->InstructionAt(instr_index)->GetParallelMove(gap_pos);
   EXPECT_NE(nullptr, moves);
 
   bool found_match = false;
   for (auto move : *moves) {
     if (move->IsEliminated() || move->IsRedundant()) continue;
     if (AllocatedOperandMatches(AllocatedOperand::cast(move->source()), src) &&
         AllocatedOperandMatches(AllocatedOperand::cast(move->destination()),
                                 dest)) {
       found_match = true;
       break;
     }
   }
   return found_match;
 }
 
 }  // namespace
 
-
 class RegisterAllocatorTest : public InstructionSequenceTest {
  public:
   void Allocate() {
     WireBlocks();
     Pipeline::AllocateRegistersForTesting(config(), sequence(), true);
   }
 };
 
-
 TEST_F(RegisterAllocatorTest, CanAllocateThreeRegisters) {
   // return p0 + p1;
   StartBlock();
   auto a_reg = Parameter();
   auto b_reg = Parameter();
   auto c_reg = EmitOI(Reg(1), Reg(a_reg, 1), Reg(b_reg, 0));
   Return(c_reg);
   EndBlock(Last());
 
   Allocate();
@@ skipping 27 matching lines @@
     auto ipp = EmitOI(Same(), Reg(phi), Use(DefineConstant()));
     SetInput(phi, 1, ipp);
     EndBlock(Jump(0));
 
     EndLoop();
   }
 
   Allocate();
 }
 
-
 TEST_F(RegisterAllocatorTest, SimpleBranch) {
   // return i ? K1 : K2
   StartBlock();
   auto i = DefineConstant();
   EndBlock(Branch(Reg(i), 1, 2));
 
   StartBlock();
   Return(DefineConstant());
   EndBlock(Last());
 
   StartBlock();
   Return(DefineConstant());
   EndBlock(Last());
 
   Allocate();
 }
 
-
 TEST_F(RegisterAllocatorTest, SimpleDiamond) {
   // return p0 ? p0 : p0
   StartBlock();
   auto param = Parameter();
   EndBlock(Branch(Reg(param), 1, 2));
 
   StartBlock();
   EndBlock(Jump(2));
 
   StartBlock();
   EndBlock(Jump(1));
 
   StartBlock();
   Return(param);
   EndBlock();
 
   Allocate();
 }
 
-
 TEST_F(RegisterAllocatorTest, SimpleDiamondPhi) {
   // return i ? K1 : K2
   StartBlock();
   EndBlock(Branch(Reg(DefineConstant()), 1, 2));
 
   StartBlock();
   auto t_val = DefineConstant();
   EndBlock(Jump(2));
 
   StartBlock();
   auto f_val = DefineConstant();
   EndBlock(Jump(1));
 
   StartBlock();
   Return(Reg(Phi(t_val, f_val)));
   EndBlock();
 
   Allocate();
 }
 
-
 TEST_F(RegisterAllocatorTest, DiamondManyPhis) {
   const int kPhis = kDefaultNRegs * 2;
 
   StartBlock();
   EndBlock(Branch(Reg(DefineConstant()), 1, 2));
 
   StartBlock();
   VReg t_vals[kPhis];
   for (int i = 0; i < kPhis; ++i) {
     t_vals[i] = DefineConstant();
@@ skipping 11 matching lines @@
   TestOperand merged[kPhis];
   for (int i = 0; i < kPhis; ++i) {
     merged[i] = Use(Phi(t_vals[i], f_vals[i]));
   }
   Return(EmitCall(Slot(-1), kPhis, merged));
   EndBlock();
 
   Allocate();
 }
 
-
 TEST_F(RegisterAllocatorTest, DoubleDiamondManyRedundantPhis) {
   const int kPhis = kDefaultNRegs * 2;
 
   // First diamond.
   StartBlock();
   VReg vals[kPhis];
   for (int i = 0; i < kPhis; ++i) {
     vals[i] = Parameter(Slot(-1 - i));
   }
   EndBlock(Branch(Reg(DefineConstant()), 1, 2));
@@ skipping 18 matching lines @@
   TestOperand merged[kPhis];
   for (int i = 0; i < kPhis; ++i) {
     merged[i] = Use(Phi(vals[i], vals[i]));
   }
   Return(EmitCall(Reg(0), kPhis, merged));
   EndBlock();
 
   Allocate();
 }
 
-
 TEST_F(RegisterAllocatorTest, RegressionPhisNeedTooManyRegisters) {
   const size_t kNumRegs = 3;
   const size_t kParams = kNumRegs + 1;
   // Override number of registers.
   SetNumRegs(kNumRegs, kNumRegs);
 
   StartBlock();
   auto constant = DefineConstant();
   VReg parameters[kParams];
   for (size_t i = 0; i < arraysize(parameters); ++i) {
@@ skipping 28 matching lines @@
     EndLoop();
   }
 
   StartBlock();
   Return(DefineConstant());
   EndBlock();
 
   Allocate();
 }
 
-
 TEST_F(RegisterAllocatorTest, SpillPhi) {
   StartBlock();
   EndBlock(Branch(Imm(), 1, 2));
 
   StartBlock();
   auto left = Define(Reg(0));
   EndBlock(Jump(2));
 
   StartBlock();
   auto right = Define(Reg(0));
   EndBlock();
 
   StartBlock();
   auto phi = Phi(left, right);
   EmitCall(Slot(-1));
   Return(Reg(phi));
   EndBlock();
 
   Allocate();
 }
 
-
 TEST_F(RegisterAllocatorTest, MoveLotsOfConstants) {
   StartBlock();
   VReg constants[kDefaultNRegs];
   for (size_t i = 0; i < arraysize(constants); ++i) {
     constants[i] = DefineConstant();
   }
   TestOperand call_ops[kDefaultNRegs * 2];
   for (int i = 0; i < kDefaultNRegs; ++i) {
     call_ops[i] = Reg(constants[i], i);
   }
   for (int i = 0; i < kDefaultNRegs; ++i) {
     call_ops[i + kDefaultNRegs] = Slot(constants[i], i);
   }
   EmitCall(Slot(-1), arraysize(call_ops), call_ops);
   EndBlock(Last());
 
   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<int>(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, SplitBeforeInstruction2) {
   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<int>(i)));
   }
 
   // values[0] and [1] will be split in the second half of this instruction.
   EmitOOI(Reg(0), Reg(1), Reg(p_0, 0), Reg(p_1, 1));
   EmitI(Reg(values[0]), Reg(values[1]));
   EndBlock(Last());
 
   Allocate();
 }
 
-
 TEST_F(RegisterAllocatorTest, NestedDiamondPhiMerge) {
   // Outer diamond.
   StartBlock();
   EndBlock(Branch(Imm(), 1, 5));
 
   // Diamond 1
   StartBlock();
   EndBlock(Branch(Imm(), 1, 2));
 
   StartBlock();
@@ skipping 26 matching lines @@
 
   // 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();
@@ skipping 26 matching lines @@
 
   // Outer diamond merge.
   StartBlock();
   auto phi = Phi(l_phi, r_phi);
   Return(Reg(phi));
   EndBlock();
 
   Allocate();
 }
 
-
 TEST_F(RegisterAllocatorTest, RegressionSplitBeforeAndMove) {
   StartBlock();
 
   // Fill registers.
   VReg values[kDefaultNRegs];
   for (size_t i = 0; i < arraysize(values); ++i) {
     if (i == 0 || i == 1) continue;  // Leave a hole for c_1 to take.
     values[i] = Define(Reg(static_cast<int>(i)));
   }
 
   auto c_0 = DefineConstant();
   auto c_1 = DefineConstant();
 
   EmitOI(Reg(1), Reg(c_0, 0), UniqueReg(c_1));
 
   // Use previous values to force c_1 to split before the previous instruction.
   for (size_t i = 0; i < arraysize(values); ++i) {
     if (i == 0 || i == 1) continue;
     EmitI(Reg(values[i], static_cast<int>(i)));
   }
 
   EndBlock(Last());
 
   Allocate();
 }
 
-
 TEST_F(RegisterAllocatorTest, RegressionSpillTwice) {
   StartBlock();
   auto p_0 = Parameter(Reg(1));
   EmitCall(Slot(-2), Unique(p_0), Reg(p_0, 1));
   EndBlock(Last());
 
   Allocate();
 }
 
-
 TEST_F(RegisterAllocatorTest, RegressionLoadConstantBeforeSpill) {
   StartBlock();
   // Fill registers.
   VReg values[kDefaultNRegs];
   for (size_t i = arraysize(values); i > 0; --i) {
     values[i - 1] = Define(Reg(static_cast<int>(i - 1)));
   }
   auto c = DefineConstant();
   auto to_spill = Define(Reg());
   EndBlock(Jump(1));
@@ skipping 14 matching lines @@
 
   StartBlock();
   // Force c to split within to_spill's definition.
   EmitI(Reg(c));
   EmitI(Reg(to_spill));
   EndBlock(Last());
 
   Allocate();
 }
 
-
 TEST_F(RegisterAllocatorTest, DiamondWithCallFirstBlock) {
   StartBlock();
   auto x = EmitOI(Reg(0));
   EndBlock(Branch(Reg(x), 1, 2));
 
   StartBlock();
   EmitCall(Slot(-1));
   auto occupy = EmitOI(Reg(0));
   EndBlock(Jump(2));
 
   StartBlock();
   EndBlock(FallThrough());
 
   StartBlock();
   Use(occupy);
   Return(Reg(x));
   EndBlock();
   Allocate();
 }
 
-
 TEST_F(RegisterAllocatorTest, DiamondWithCallSecondBlock) {
   StartBlock();
   auto x = EmitOI(Reg(0));
   EndBlock(Branch(Reg(x), 1, 2));
 
   StartBlock();
   EndBlock(Jump(2));
 
   StartBlock();
   EmitCall(Slot(-1));
   auto occupy = EmitOI(Reg(0));
   EndBlock(FallThrough());
 
   StartBlock();
   Use(occupy);
   Return(Reg(x));
   EndBlock();
   Allocate();
 }
 
-
 TEST_F(RegisterAllocatorTest, SingleDeferredBlockSpill) {
   StartBlock();  // B0
   auto var = EmitOI(Reg(0));
   EndBlock(Branch(Reg(var), 1, 2));
 
   StartBlock();  // B1
   EndBlock(Jump(2));
 
   StartBlock(true);  // B2
   EmitCall(Slot(-1), Slot(var));
@@ skipping 18 matching lines @@
 
   // We should have no parallel moves at the "expect_no_moves" position.
   EXPECT_EQ(
       0, GetParallelMoveCount(expect_no_moves, Instruction::START, sequence()));
 
   // The spill should be performed at the position expect_spill_move.
   EXPECT_TRUE(IsParallelMovePresent(expect_spill_move, Instruction::START,
                                     sequence(), Reg(0), Slot(0)));
 }
 
-
 TEST_F(RegisterAllocatorTest, MultipleDeferredBlockSpills) {
   if (!FLAG_turbo_preprocess_ranges) return;
 
   StartBlock();  // B0
   auto var1 = EmitOI(Reg(0));
   auto var2 = EmitOI(Reg(1));
   auto var3 = EmitOI(Reg(2));
   EndBlock(Branch(Reg(var1, 0), 1, 2));
 
   StartBlock(true);  // B1
@@ skipping 30 matching lines @@
   EXPECT_TRUE(IsParallelMovePresent(call_in_b1, Instruction::START, sequence(),
                                     Reg(var3_reg), Slot(var3_slot)));
   EXPECT_TRUE(IsParallelMovePresent(end_of_b1, Instruction::START, sequence(),
                                     Slot(var3_slot), Reg()));
 
   EXPECT_TRUE(IsParallelMovePresent(call_in_b2, Instruction::START, sequence(),
                                     Reg(var3_reg), Slot(var3_slot)));
   EXPECT_TRUE(IsParallelMovePresent(end_of_b2, Instruction::START, sequence(),
                                     Slot(var3_slot), Reg()));
 
-
   EXPECT_EQ(0,
             GetParallelMoveCount(start_of_b3, Instruction::START, sequence()));
 }
 
-
 namespace {
 
 enum class ParameterType { kFixedSlot, kSlot, kRegister, kFixedRegister };
 
 const ParameterType kParameterTypes[] = {
     ParameterType::kFixedSlot, ParameterType::kSlot, ParameterType::kRegister,
     ParameterType::kFixedRegister};
 
 class SlotConstraintTest : public RegisterAllocatorTest,
                            public ::testing::WithParamInterface<
                                ::testing::tuple<ParameterType, int>> {
  public:
   static const int kMaxVariant = 5;
 
  protected:
   ParameterType parameter_type() const {
     return ::testing::get<0>(B::GetParam());
   }
   int variant() const { return ::testing::get<1>(B::GetParam()); }
 
  private:
   typedef ::testing::WithParamInterface<::testing::tuple<ParameterType, int>> B;
 };
 
 }  // namespace
 
-
 #if GTEST_HAS_COMBINE
 
 TEST_P(SlotConstraintTest, SlotConstraint) {
   StartBlock();
   VReg p_0;
   switch (parameter_type()) {
     case ParameterType::kFixedSlot:
       p_0 = Parameter(Slot(-1));
       break;
     case ParameterType::kSlot:
@@ skipping 26 matching lines @@
       break;
     default:
       UNREACHABLE();
       break;
   }
   EndBlock(Last());
 
   Allocate();
 }
 
-
 INSTANTIATE_TEST_CASE_P(
     RegisterAllocatorTest, SlotConstraintTest,
     ::testing::Combine(::testing::ValuesIn(kParameterTypes),
                        ::testing::Range(0, SlotConstraintTest::kMaxVariant)));
 
 #endif  // GTEST_HAS_COMBINE
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8