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, NestedDiamondPhiMerge) {
 305   // Outer diamond.
 306   StartBlock();
 307   EndBlock(Branch(Imm(), 1, 5));
 308
 309   // Diamond 1
 310   StartBlock();
 311   EndBlock(Branch(Imm(), 1, 2));
 312
 313   StartBlock();
 314   auto ll = Define(Reg());
 315   EndBlock(Jump(2));
 316
 317   StartBlock();
 318   auto lr = Define(Reg());
 319   EndBlock();
 320
 321   StartBlock();
 322   auto l_phi = Phi(ll, lr);
 323   EndBlock(Jump(5));
 324
 325   // Diamond 2
 326   StartBlock();
 327   EndBlock(Branch(Imm(), 1, 2));
 328
 329   StartBlock();
 330   auto rl = Define(Reg());
 331   EndBlock(Jump(2));
 332
 333   StartBlock();
 334   auto rr = Define(Reg());
 335   EndBlock();
 336
 337   StartBlock();
 338   auto r_phi = Phi(rl, rr);
 339   EndBlock();
 340
 341   // Outer diamond merge.
 342   StartBlock();
 343   auto phi = Phi(l_phi, r_phi);
 344   Return(Reg(phi));
 345   EndBlock();
 346
 347   Allocate();
 348 }
 349
 350
 351 TEST_F(RegisterAllocatorTest, NestedDiamondPhiMergeDifferent) {
 352   // Outer diamond.
 353   StartBlock();
 354   EndBlock(Branch(Imm(), 1, 5));
 355
 356   // Diamond 1
 357   StartBlock();
 358   EndBlock(Branch(Imm(), 1, 2));
 359
 360   StartBlock();
 361   auto ll = Define(Reg(0));
 362   EndBlock(Jump(2));
 363
 364   StartBlock();
 365   auto lr = Define(Reg(1));
 366   EndBlock();
 367
 368   StartBlock();
 369   auto l_phi = Phi(ll, lr);
 370   EndBlock(Jump(5));
 371
 372   // Diamond 2
 373   StartBlock();
 374   EndBlock(Branch(Imm(), 1, 2));
 375
 376   StartBlock();
 377   auto rl = Define(Reg(2));
 378   EndBlock(Jump(2));
 379
 380   StartBlock();
 381   auto rr = Define(Reg(3));
 382   EndBlock();
 383
 384   StartBlock();
 385   auto r_phi = Phi(rl, rr);
 386   EndBlock();
 387
 388   // Outer diamond merge.
 389   StartBlock();
 390   auto phi = Phi(l_phi, r_phi);
 391   Return(Reg(phi));
 392   EndBlock();
 393
 394   Allocate();
 395 }
 396
 397
 398 TEST_F(RegisterAllocatorTest, RegressionSplitBeforeAndMove) {
 399   StartBlock();
 400
 401   // Fill registers.
 402   VReg values[kDefaultNRegs];
 403   for (size_t i = 0; i < arraysize(values); ++i) {
 404     if (i == 0 || i == 1) continue;  // Leave a hole for c_1 to take.
 405     values[i] = Define(Reg(static_cast<int>(i)));
 406   }
 407
 408   auto c_0 = DefineConstant();
 409   auto c_1 = DefineConstant();
 410
 411   EmitOI(Reg(1), Reg(c_0, 0), UniqueReg(c_1));
 412
 413   // Use previous values to force c_1 to split before the previous instruction.
 414   for (size_t i = 0; i < arraysize(values); ++i) {
 415     if (i == 0 || i == 1) continue;
 416     EmitI(Reg(values[i], static_cast<int>(i)));
 417   }
 418
 419   EndBlock(Last());
 420
 421   Allocate();
 422 }
 423
 424
 425 TEST_F(RegisterAllocatorTest, RegressionSpillTwice) {
 426   StartBlock();
 427   auto p_0 = Parameter(Reg(1));
 428   EmitCall(Slot(-2), Unique(p_0), Reg(p_0, 1));
 429   EndBlock(Last());
 430
 431   Allocate();
 432 }
 433
 434
 435 TEST_F(RegisterAllocatorTest, RegressionLoadConstantBeforeSpill) {
 436   StartBlock();
 437   // Fill registers.
 438   VReg values[kDefaultNRegs];
 439   for (size_t i = arraysize(values); i > 0; --i) {
 440     values[i - 1] = Define(Reg(static_cast<int>(i - 1)));
 441   }
 442   auto c = DefineConstant();
 443   auto to_spill = Define(Reg());
 444   EndBlock(Jump(1));
 445
 446   {
 447     StartLoop(1);
 448
 449     StartBlock();
 450     // Create a use for c in second half of prev block's last gap
 451     Phi(c);
 452     for (size_t i = arraysize(values); i > 0; --i) {
 453       Phi(values[i - 1]);
 454     }
 455     EndBlock(Jump(1));
 456
 457     EndLoop();
 458   }
 459
 460   StartBlock();
 461   // Force c to split within to_spill's definition.
 462   EmitI(Reg(c));
 463   EmitI(Reg(to_spill));
 464   EndBlock(Last());
 465
 466   Allocate();
 467 }
 468
 469 }  // namespace compiler
 470 }  // namespace internal
 471 }  // namespace v8