deps/v8/test/unittests/compiler/register-allocator-unittest.cc

   1 // Copyright 2014 the V8 project authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include "src/compiler/pipeline.h"
   6 #include "test/unittests/compiler/instruction-sequence-unittest.h"
   7
   8 namespace v8 {
   9 namespace internal {
  10 namespace compiler {
  11
  12 class RegisterAllocatorTest : public InstructionSequenceTest {
  13  public:
  14   void Allocate() {
  15     WireBlocks();
  16     Pipeline::AllocateRegistersForTesting(config(), sequence(), true);
  17   }
  18 };
  19
  20
  21 TEST_F(RegisterAllocatorTest, CanAllocateThreeRegisters) {
  22   // return p0 + p1;
  23   StartBlock();
  24   auto a_reg = Parameter();
  25   auto b_reg = Parameter();
  26   auto c_reg = EmitOI(Reg(1), Reg(a_reg, 1), Reg(b_reg, 0));
  27   Return(c_reg);
  28   EndBlock(Last());
  29
  30   Allocate();
  31 }
  32
  33
  34 TEST_F(RegisterAllocatorTest, SimpleLoop) {
  35   // i = K;
  36   // while(true) { i++ }
  37   StartBlock();
  38   auto i_reg = DefineConstant();
  39   EndBlock();
  40
  41   {
  42     StartLoop(1);
  43
  44     StartBlock();
  45     auto phi = Phi(i_reg, 2);
  46     auto ipp = EmitOI(Same(), Reg(phi), Use(DefineConstant()));
  47     SetInput(phi, 1, ipp);
  48     EndBlock(Jump(0));
  49
  50     EndLoop();
  51   }
  52
  53   Allocate();
  54 }
  55
  56
  57 TEST_F(RegisterAllocatorTest, SimpleBranch) {
  58   // return i ? K1 : K2
  59   StartBlock();
  60   auto i = DefineConstant();
  61   EndBlock(Branch(Reg(i), 1, 2));
  62
  63   StartBlock();
  64   Return(DefineConstant());
  65   EndBlock(Last());
  66
  67   StartBlock();
  68   Return(DefineConstant());
  69   EndBlock(Last());
  70
  71   Allocate();
  72 }
  73
  74
  75 TEST_F(RegisterAllocatorTest, SimpleDiamond) {
  76   // return p0 ? p0 : p0
  77   StartBlock();
  78   auto param = Parameter();
  79   EndBlock(Branch(Reg(param), 1, 2));
  80
  81   StartBlock();
  82   EndBlock(Jump(2));
  83
  84   StartBlock();
  85   EndBlock(Jump(1));
  86
  87   StartBlock();
  88   Return(param);
  89   EndBlock();
  90
  91   Allocate();
  92 }
  93
  94
  95 TEST_F(RegisterAllocatorTest, SimpleDiamondPhi) {
  96   // return i ? K1 : K2
  97   StartBlock();
  98   EndBlock(Branch(Reg(DefineConstant()), 1, 2));
  99
 100   StartBlock();
 101   auto t_val = DefineConstant();
 102   EndBlock(Jump(2));
 103
 104   StartBlock();
 105   auto f_val = DefineConstant();
 106   EndBlock(Jump(1));
 107
 108   StartBlock();
 109   Return(Reg(Phi(t_val, f_val)));
 110   EndBlock();
 111
 112   Allocate();
 113 }
 114
 115
 116 TEST_F(RegisterAllocatorTest, DiamondManyPhis) {
 117   const int kPhis = kDefaultNRegs * 2;
 118
 119   StartBlock();
 120   EndBlock(Branch(Reg(DefineConstant()), 1, 2));
 121
 122   StartBlock();
 123   VReg t_vals[kPhis];
 124   for (int i = 0; i < kPhis; ++i) {
 125     t_vals[i] = DefineConstant();
 126   }
 127   EndBlock(Jump(2));
 128
 129   StartBlock();
 130   VReg f_vals[kPhis];
 131   for (int i = 0; i < kPhis; ++i) {
 132     f_vals[i] = DefineConstant();
 133   }
 134   EndBlock(Jump(1));
 135
 136   StartBlock();
 137   TestOperand merged[kPhis];
 138   for (int i = 0; i < kPhis; ++i) {
 139     merged[i] = Use(Phi(t_vals[i], f_vals[i]));
 140   }
 141   Return(EmitCall(Slot(-1), kPhis, merged));
 142   EndBlock();
 143
 144   Allocate();
 145 }
 146
 147
 148 TEST_F(RegisterAllocatorTest, DoubleDiamondManyRedundantPhis) {
 149   const int kPhis = kDefaultNRegs * 2;
 150
 151   // First diamond.
 152   StartBlock();
 153   VReg vals[kPhis];
 154   for (int i = 0; i < kPhis; ++i) {
 155     vals[i] = Parameter(Slot(-1 - i));
 156   }
 157   EndBlock(Branch(Reg(DefineConstant()), 1, 2));
 158
 159   StartBlock();
 160   EndBlock(Jump(2));
 161
 162   StartBlock();
 163   EndBlock(Jump(1));
 164
 165   // Second diamond.
 166   StartBlock();
 167   EndBlock(Branch(Reg(DefineConstant()), 1, 2));
 168
 169   StartBlock();
 170   EndBlock(Jump(2));
 171
 172   StartBlock();
 173   EndBlock(Jump(1));
 174
 175   StartBlock();
 176   TestOperand merged[kPhis];
 177   for (int i = 0; i < kPhis; ++i) {
 178     merged[i] = Use(Phi(vals[i], vals[i]));
 179   }
 180   Return(EmitCall(Reg(0), kPhis, merged));
 181   EndBlock();
 182
 183   Allocate();
 184 }
 185
 186
 187 TEST_F(RegisterAllocatorTest, RegressionPhisNeedTooManyRegisters) {
 188   const size_t kNumRegs = 3;
 189   const size_t kParams = kNumRegs + 1;
 190   // Override number of registers.
 191   SetNumRegs(kNumRegs, kNumRegs);
 192
 193   StartBlock();
 194   auto constant = DefineConstant();
 195   VReg parameters[kParams];
 196   for (size_t i = 0; i < arraysize(parameters); ++i) {
 197     parameters[i] = DefineConstant();
 198   }
 199   EndBlock();
 200
 201   PhiInstruction* phis[kParams];
 202   {
 203     StartLoop(2);
 204
 205     // Loop header.
 206     StartBlock();
 207
 208     for (size_t i = 0; i < arraysize(parameters); ++i) {
 209       phis[i] = Phi(parameters[i], 2);
 210     }
 211
 212     // Perform some computations.
 213     // something like phi[i] += const
 214     for (size_t i = 0; i < arraysize(parameters); ++i) {
 215       auto result = EmitOI(Same(), Reg(phis[i]), Use(constant));
 216       SetInput(phis[i], 1, result);
 217     }
 218
 219     EndBlock(Branch(Reg(DefineConstant()), 1, 2));
 220
 221     // Jump back to loop header.
 222     StartBlock();
 223     EndBlock(Jump(-1));
 224
 225     EndLoop();
 226   }
 227
 228   StartBlock();
 229   Return(DefineConstant());
 230   EndBlock();
 231
 232   Allocate();
 233 }
 234
 235
 236 TEST_F(RegisterAllocatorTest, SpillPhi) {
 237   StartBlock();
 238   EndBlock(Branch(Imm(), 1, 2));
 239
 240   StartBlock();
 241   auto left = Define(Reg(0));
 242   EndBlock(Jump(2));
 243
 244   StartBlock();
 245   auto right = Define(Reg(0));
 246   EndBlock();
 247
 248   StartBlock();
 249   auto phi = Phi(left, right);
 250   EmitCall(Slot(-1));
 251   Return(Reg(phi));
 252   EndBlock();
 253
 254   Allocate();
 255 }
 256
 257
 258 TEST_F(RegisterAllocatorTest, MoveLotsOfConstants) {
 259   StartBlock();
 260   VReg constants[kDefaultNRegs];
 261   for (size_t i = 0; i < arraysize(constants); ++i) {
 262     constants[i] = DefineConstant();
 263   }
 264   TestOperand call_ops[kDefaultNRegs * 2];
 265   for (int i = 0; i < kDefaultNRegs; ++i) {
 266     call_ops[i] = Reg(constants[i], i);
 267   }
 268   for (int i = 0; i < kDefaultNRegs; ++i) {
 269     call_ops[i + kDefaultNRegs] = Slot(constants[i], i);
 270   }
 271   EmitCall(Slot(-1), arraysize(call_ops), call_ops);
 272   EndBlock(Last());
 273
 274   Allocate();
 275 }
 276
 277
 278 TEST_F(RegisterAllocatorTest, SplitBeforeInstruction) {
 279   const int kNumRegs = 6;
 280   SetNumRegs(kNumRegs, kNumRegs);
 281
 282   StartBlock();
 283
 284   // Stack parameters/spilled values.
 285   auto p_0 = Define(Slot(-1));
 286   auto p_1 = Define(Slot(-2));
 287
 288   // Fill registers.
 289   VReg values[kNumRegs];
 290   for (size_t i = 0; i < arraysize(values); ++i) {
 291     values[i] = Define(Reg(static_cast<int>(i)));
 292   }
 293
 294   // values[0] will be split in the second half of this instruction.
 295   // Models Intel mod instructions.
 296   EmitOI(Reg(0), Reg(p_0, 1), UniqueReg(p_1));
 297   EmitI(Reg(values[0], 0));
 298   EndBlock(Last());
 299
 300   Allocate();
 301 }
 302
 303
 304 TEST_F(RegisterAllocatorTest, SplitBeforeInstruction2) {
 305   const int kNumRegs = 6;
 306   SetNumRegs(kNumRegs, kNumRegs);
 307
 308   StartBlock();
 309
 310   // Stack parameters/spilled values.
 311   auto p_0 = Define(Slot(-1));
 312   auto p_1 = Define(Slot(-2));
 313
 314   // Fill registers.
 315   VReg values[kNumRegs];
 316   for (size_t i = 0; i < arraysize(values); ++i) {
 317     values[i] = Define(Reg(static_cast<int>(i)));
 318   }
 319
 320   // values[0] and [1] will be split in the second half of this instruction.
 321   EmitOOI(Reg(0), Reg(1), Reg(p_0, 0), Reg(p_1, 1));
 322   EmitI(Reg(values[0]), Reg(values[1]));
 323   EndBlock(Last());
 324
 325   Allocate();
 326 }
 327
 328
 329 TEST_F(RegisterAllocatorTest, NestedDiamondPhiMerge) {
 330   // Outer diamond.
 331   StartBlock();
 332   EndBlock(Branch(Imm(), 1, 5));
 333
 334   // Diamond 1
 335   StartBlock();
 336   EndBlock(Branch(Imm(), 1, 2));
 337
 338   StartBlock();
 339   auto ll = Define(Reg());
 340   EndBlock(Jump(2));
 341
 342   StartBlock();
 343   auto lr = Define(Reg());
 344   EndBlock();
 345
 346   StartBlock();
 347   auto l_phi = Phi(ll, lr);
 348   EndBlock(Jump(5));
 349
 350   // Diamond 2
 351   StartBlock();
 352   EndBlock(Branch(Imm(), 1, 2));
 353
 354   StartBlock();
 355   auto rl = Define(Reg());
 356   EndBlock(Jump(2));
 357
 358   StartBlock();
 359   auto rr = Define(Reg());
 360   EndBlock();
 361
 362   StartBlock();
 363   auto r_phi = Phi(rl, rr);
 364   EndBlock();
 365
 366   // Outer diamond merge.
 367   StartBlock();
 368   auto phi = Phi(l_phi, r_phi);
 369   Return(Reg(phi));
 370   EndBlock();
 371
 372   Allocate();
 373 }
 374
 375
 376 TEST_F(RegisterAllocatorTest, NestedDiamondPhiMergeDifferent) {
 377   // Outer diamond.
 378   StartBlock();
 379   EndBlock(Branch(Imm(), 1, 5));
 380
 381   // Diamond 1
 382   StartBlock();
 383   EndBlock(Branch(Imm(), 1, 2));
 384
 385   StartBlock();
 386   auto ll = Define(Reg(0));
 387   EndBlock(Jump(2));
 388
 389   StartBlock();
 390   auto lr = Define(Reg(1));
 391   EndBlock();
 392
 393   StartBlock();
 394   auto l_phi = Phi(ll, lr);
 395   EndBlock(Jump(5));
 396
 397   // Diamond 2
 398   StartBlock();
 399   EndBlock(Branch(Imm(), 1, 2));
 400
 401   StartBlock();
 402   auto rl = Define(Reg(2));
 403   EndBlock(Jump(2));
 404
 405   StartBlock();
 406   auto rr = Define(Reg(3));
 407   EndBlock();
 408
 409   StartBlock();
 410   auto r_phi = Phi(rl, rr);
 411   EndBlock();
 412
 413   // Outer diamond merge.
 414   StartBlock();
 415   auto phi = Phi(l_phi, r_phi);
 416   Return(Reg(phi));
 417   EndBlock();
 418
 419   Allocate();
 420 }
 421
 422
 423 TEST_F(RegisterAllocatorTest, RegressionSplitBeforeAndMove) {
 424   StartBlock();
 425
 426   // Fill registers.
 427   VReg values[kDefaultNRegs];
 428   for (size_t i = 0; i < arraysize(values); ++i) {
 429     if (i == 0 || i == 1) continue;  // Leave a hole for c_1 to take.
 430     values[i] = Define(Reg(static_cast<int>(i)));
 431   }
 432
 433   auto c_0 = DefineConstant();
 434   auto c_1 = DefineConstant();
 435
 436   EmitOI(Reg(1), Reg(c_0, 0), UniqueReg(c_1));
 437
 438   // Use previous values to force c_1 to split before the previous instruction.
 439   for (size_t i = 0; i < arraysize(values); ++i) {
 440     if (i == 0 || i == 1) continue;
 441     EmitI(Reg(values[i], static_cast<int>(i)));
 442   }
 443
 444   EndBlock(Last());
 445
 446   Allocate();
 447 }
 448
 449
 450 TEST_F(RegisterAllocatorTest, RegressionSpillTwice) {
 451   StartBlock();
 452   auto p_0 = Parameter(Reg(1));
 453   EmitCall(Slot(-2), Unique(p_0), Reg(p_0, 1));
 454   EndBlock(Last());
 455
 456   Allocate();
 457 }
 458
 459
 460 TEST_F(RegisterAllocatorTest, RegressionLoadConstantBeforeSpill) {
 461   StartBlock();
 462   // Fill registers.
 463   VReg values[kDefaultNRegs];
 464   for (size_t i = arraysize(values); i > 0; --i) {
 465     values[i - 1] = Define(Reg(static_cast<int>(i - 1)));
 466   }
 467   auto c = DefineConstant();
 468   auto to_spill = Define(Reg());
 469   EndBlock(Jump(1));
 470
 471   {
 472     StartLoop(1);
 473
 474     StartBlock();
 475     // Create a use for c in second half of prev block's last gap
 476     Phi(c);
 477     for (size_t i = arraysize(values); i > 0; --i) {
 478       Phi(values[i - 1]);
 479     }
 480     EndBlock(Jump(1));
 481
 482     EndLoop();
 483   }
 484
 485   StartBlock();
 486   // Force c to split within to_spill's definition.
 487   EmitI(Reg(c));
 488   EmitI(Reg(to_spill));
 489   EndBlock(Last());
 490
 491   Allocate();
 492 }
 493
 494
 495 namespace {
 496
 497 enum class ParameterType { kFixedSlot, kSlot, kRegister, kFixedRegister };
 498
 499 const ParameterType kParameterTypes[] = {
 500     ParameterType::kFixedSlot, ParameterType::kSlot, ParameterType::kRegister,
 501     ParameterType::kFixedRegister};
 502
 503 class SlotConstraintTest : public RegisterAllocatorTest,
 504                            public ::testing::WithParamInterface<
 505                                ::testing::tuple<ParameterType, int>> {
 506  public:
 507   static const int kMaxVariant = 5;
 508
 509  protected:
 510   ParameterType parameter_type() const {
 511     return ::testing::get<0>(B::GetParam());
 512   }
 513   int variant() const { return ::testing::get<1>(B::GetParam()); }
 514
 515  private:
 516   typedef ::testing::WithParamInterface<::testing::tuple<ParameterType, int>> B;
 517 };
 518 }
 519
 520
 521 #if GTEST_HAS_COMBINE
 522
 523 TEST_P(SlotConstraintTest, SlotConstraint) {
 524   StartBlock();
 525   VReg p_0;
 526   switch (parameter_type()) {
 527     case ParameterType::kFixedSlot:
 528       p_0 = Parameter(Slot(-1));
 529       break;
 530     case ParameterType::kSlot:
 531       p_0 = Parameter(Slot(-1));
 532       break;
 533     case ParameterType::kRegister:
 534       p_0 = Parameter(Reg());
 535       break;
 536     case ParameterType::kFixedRegister:
 537       p_0 = Parameter(Reg(1));
 538       break;
 539   }
 540   switch (variant()) {
 541     case 0:
 542       EmitI(Slot(p_0), Reg(p_0));
 543       break;
 544     case 1:
 545       EmitI(Slot(p_0));
 546       break;
 547     case 2:
 548       EmitI(Reg(p_0));
 549       EmitI(Slot(p_0));
 550       break;
 551     case 3:
 552       EmitI(Slot(p_0));
 553       EmitI(Reg(p_0));
 554       break;
 555     case 4:
 556       EmitI(Slot(p_0, -1), Slot(p_0), Reg(p_0), Reg(p_0, 1));
 557       break;
 558     default:
 559       UNREACHABLE();
 560       break;
 561   }
 562   EndBlock(Last());
 563
 564   Allocate();
 565 }
 566
 567
 568 INSTANTIATE_TEST_CASE_P(
 569     RegisterAllocatorTest, SlotConstraintTest,
 570     ::testing::Combine(::testing::ValuesIn(kParameterTypes),
 571                        ::testing::Range(0, SlotConstraintTest::kMaxVariant)));
 572
 573 #endif  // GTEST_HAS_COMBINE
 574
 575 }  // namespace compiler
 576 }  // namespace internal
 577 }  // namespace v8