Home | History | Annotate | Download | only in interpreter 
      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/v8.h"
      6 
      7 #include "src/interpreter/bytecode-array-builder.h"
      8 #include "src/interpreter/bytecode-register-allocator.h"
      9 #include "test/unittests/test-utils.h"
     10 
     11 namespace v8 {
     12 namespace internal {
     13 namespace interpreter {
     14 
     15 class TemporaryRegisterAllocatorTest : public TestWithIsolateAndZone {
     16  public:
     17   TemporaryRegisterAllocatorTest() : allocator_(zone(), 0) {}
     18   ~TemporaryRegisterAllocatorTest() override {}
     19   TemporaryRegisterAllocator* allocator() { return &allocator_; }
     20 
     21  private:
     22   TemporaryRegisterAllocator allocator_;
     23 };
     24 
     25 TEST_F(TemporaryRegisterAllocatorTest, FirstAllocation) {
     26   CHECK_EQ(allocator()->allocation_count(), 0);
     27   int reg0_index = allocator()->BorrowTemporaryRegister();
     28   CHECK_EQ(reg0_index, 0);
     29   CHECK_EQ(allocator()->allocation_count(), 1);
     30   CHECK(allocator()->RegisterIsLive(Register(reg0_index)));
     31   allocator()->ReturnTemporaryRegister(reg0_index);
     32   CHECK(!allocator()->RegisterIsLive(Register(reg0_index)));
     33   CHECK_EQ(allocator()->allocation_count(), 1);
     34   CHECK(allocator()->first_temporary_register() == Register(0));
     35   CHECK(allocator()->last_temporary_register() == Register(0));
     36 }
     37 
     38 TEST_F(TemporaryRegisterAllocatorTest, SimpleAllocations) {
     39   for (int i = 0; i < 13; i++) {
     40     int reg_index = allocator()->BorrowTemporaryRegister();
     41     CHECK_EQ(reg_index, i);
     42     CHECK_EQ(allocator()->allocation_count(), i + 1);
     43   }
     44   for (int i = 0; i < 13; i++) {
     45     CHECK(allocator()->RegisterIsLive(Register(i)));
     46     allocator()->ReturnTemporaryRegister(i);
     47     CHECK(!allocator()->RegisterIsLive(Register(i)));
     48     int reg_index = allocator()->BorrowTemporaryRegister();
     49     CHECK_EQ(reg_index, i);
     50     CHECK_EQ(allocator()->allocation_count(), 13);
     51   }
     52   for (int i = 0; i < 13; i++) {
     53     CHECK(allocator()->RegisterIsLive(Register(i)));
     54     allocator()->ReturnTemporaryRegister(i);
     55     CHECK(!allocator()->RegisterIsLive(Register(i)));
     56   }
     57 }
     58 
     59 TEST_F(TemporaryRegisterAllocatorTest, SimpleRangeAllocation) {
     60   static const int kRunLength = 7;
     61   int start = allocator()->PrepareForConsecutiveTemporaryRegisters(kRunLength);
     62   CHECK(!allocator()->RegisterIsLive(Register(start)));
     63   for (int i = 0; i < kRunLength; i++) {
     64     CHECK(!allocator()->RegisterIsLive(Register(start + i)));
     65     allocator()->BorrowConsecutiveTemporaryRegister(start + i);
     66     CHECK(allocator()->RegisterIsLive(Register(start + i)));
     67   }
     68 }
     69 
     70 TEST_F(TemporaryRegisterAllocatorTest, RangeAllocationAbuttingFree) {
     71   static const int kFreeCount = 3;
     72   static const int kRunLength = 6;
     73 
     74   for (int i = 0; i < kFreeCount; i++) {
     75     int to_free = allocator()->BorrowTemporaryRegister();
     76     CHECK_EQ(to_free, i);
     77   }
     78   for (int i = 0; i < kFreeCount; i++) {
     79     allocator()->ReturnTemporaryRegister(i);
     80   }
     81 
     82   int start = allocator()->PrepareForConsecutiveTemporaryRegisters(kRunLength);
     83   CHECK(!allocator()->RegisterIsLive(Register(start)));
     84   for (int i = 0; i < kRunLength; i++) {
     85     CHECK(!allocator()->RegisterIsLive(Register(start + i)));
     86     allocator()->BorrowConsecutiveTemporaryRegister(start + i);
     87     CHECK(allocator()->RegisterIsLive(Register(start + i)));
     88   }
     89 }
     90 
     91 TEST_F(TemporaryRegisterAllocatorTest, RangeAllocationAbuttingHole) {
     92   static const int kPreAllocatedCount = 7;
     93   static const int kPreAllocatedFreeCount = 6;
     94   static const int kRunLength = 8;
     95 
     96   for (int i = 0; i < kPreAllocatedCount; i++) {
     97     int to_free = allocator()->BorrowTemporaryRegister();
     98     CHECK_EQ(to_free, i);
     99   }
    100   for (int i = 0; i < kPreAllocatedFreeCount; i++) {
    101     allocator()->ReturnTemporaryRegister(i);
    102   }
    103   int start = allocator()->PrepareForConsecutiveTemporaryRegisters(kRunLength);
    104   CHECK(!allocator()->RegisterIsLive(Register(start)));
    105   CHECK_EQ(start, kPreAllocatedCount);
    106   for (int i = 0; i < kRunLength; i++) {
    107     CHECK(!allocator()->RegisterIsLive(Register(start + i)));
    108     allocator()->BorrowConsecutiveTemporaryRegister(start + i);
    109     CHECK(allocator()->RegisterIsLive(Register(start + i)));
    110   }
    111 }
    112 
    113 TEST_F(TemporaryRegisterAllocatorTest, RangeAllocationAvailableInTemporaries) {
    114   static const int kNotRunLength = 13;
    115   static const int kRunLength = 8;
    116 
    117   // Allocate big batch
    118   for (int i = 0; i < kNotRunLength * 2 + kRunLength; i++) {
    119     int allocated = allocator()->BorrowTemporaryRegister();
    120     CHECK_EQ(allocated, i);
    121   }
    122   // Free every other register either side of target.
    123   for (int i = 0; i < kNotRunLength; i++) {
    124     if ((i & 2) == 1) {
    125       allocator()->ReturnTemporaryRegister(i);
    126       allocator()->ReturnTemporaryRegister(kNotRunLength + kRunLength + i);
    127     }
    128   }
    129   // Free all registers for target.
    130   for (int i = kNotRunLength; i < kNotRunLength + kRunLength; i++) {
    131     allocator()->ReturnTemporaryRegister(i);
    132   }
    133 
    134   int start = allocator()->PrepareForConsecutiveTemporaryRegisters(kRunLength);
    135   CHECK_EQ(start, kNotRunLength);
    136   for (int i = 0; i < kRunLength; i++) {
    137     CHECK(!allocator()->RegisterIsLive(Register(start + i)));
    138     allocator()->BorrowConsecutiveTemporaryRegister(start + i);
    139     CHECK(allocator()->RegisterIsLive(Register(start + i)));
    140   }
    141 }
    142 
    143 TEST_F(TemporaryRegisterAllocatorTest, NotInRange) {
    144   for (int i = 0; i < 10; i++) {
    145     int reg = allocator()->BorrowTemporaryRegisterNotInRange(2, 5);
    146     CHECK(reg == i || (reg > 2 && reg == i + 4));
    147   }
    148   for (int i = 0; i < 10; i++) {
    149     if (i < 2) {
    150       allocator()->ReturnTemporaryRegister(i);
    151     } else {
    152       allocator()->ReturnTemporaryRegister(i + 4);
    153     }
    154   }
    155   int reg0 = allocator()->BorrowTemporaryRegisterNotInRange(0, 3);
    156   CHECK_EQ(reg0, 4);
    157   int reg1 = allocator()->BorrowTemporaryRegisterNotInRange(3, 10);
    158   CHECK_EQ(reg1, 2);
    159   int reg2 = allocator()->BorrowTemporaryRegisterNotInRange(2, 6);
    160   CHECK_EQ(reg2, 1);
    161   allocator()->ReturnTemporaryRegister(reg0);
    162   allocator()->ReturnTemporaryRegister(reg1);
    163   allocator()->ReturnTemporaryRegister(reg2);
    164 }
    165 
    166 class BytecodeRegisterAllocatorTest : public TestWithIsolateAndZone {
    167  public:
    168   BytecodeRegisterAllocatorTest() {}
    169   ~BytecodeRegisterAllocatorTest() override {}
    170 };
    171 
    172 TEST_F(BytecodeRegisterAllocatorTest, TemporariesRecycled) {
    173   BytecodeArrayBuilder builder(isolate(), zone(), 0, 0, 0);
    174 
    175   int first;
    176   {
    177     BytecodeRegisterAllocator allocator(zone(),
    178                                         builder.temporary_register_allocator());
    179     first = allocator.NewRegister().index();
    180     allocator.NewRegister();
    181     allocator.NewRegister();
    182     allocator.NewRegister();
    183   }
    184 
    185   int second;
    186   {
    187     BytecodeRegisterAllocator allocator(zone(),
    188                                         builder.temporary_register_allocator());
    189     second = allocator.NewRegister().index();
    190   }
    191 
    192   CHECK_EQ(first, second);
    193 }
    194 
    195 TEST_F(BytecodeRegisterAllocatorTest, ConsecutiveRegisters) {
    196   BytecodeArrayBuilder builder(isolate(), zone(), 0, 0, 0);
    197   BytecodeRegisterAllocator allocator(zone(),
    198                                       builder.temporary_register_allocator());
    199   allocator.PrepareForConsecutiveAllocations(4);
    200   Register reg0 = allocator.NextConsecutiveRegister();
    201   Register other = allocator.NewRegister();
    202   Register reg1 = allocator.NextConsecutiveRegister();
    203   Register reg2 = allocator.NextConsecutiveRegister();
    204   Register reg3 = allocator.NextConsecutiveRegister();
    205   USE(other);
    206 
    207   CHECK(Register::AreContiguous(reg0, reg1, reg2, reg3));
    208 }
    209 
    210 }  // namespace interpreter
    211 }  // namespace internal
    212 }  // namespace v8
    213