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