1 // Copyright 2008 the V8 project authors. All rights reserved. 2 // Redistribution and use in source and binary forms, with or without 3 // modification, are permitted provided that the following conditions are 4 // met: 5 // 6 // * Redistributions of source code must retain the above copyright 7 // notice, this list of conditions and the following disclaimer. 8 // * Redistributions in binary form must reproduce the above 9 // copyright notice, this list of conditions and the following 10 // disclaimer in the documentation and/or other materials provided 11 // with the distribution. 12 // * Neither the name of Google Inc. nor the names of its 13 // contributors may be used to endorse or promote products derived 14 // from this software without specific prior written permission. 15 // 16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 17 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 18 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 19 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 20 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 21 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 22 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27 28 #ifndef V8_REGISTER_ALLOCATOR_H_ 29 #define V8_REGISTER_ALLOCATOR_H_ 30 31 #include "macro-assembler.h" 32 #include "number-info.h" 33 34 #if V8_TARGET_ARCH_IA32 35 #include "ia32/register-allocator-ia32.h" 36 #elif V8_TARGET_ARCH_X64 37 #include "x64/register-allocator-x64.h" 38 #elif V8_TARGET_ARCH_ARM 39 #include "arm/register-allocator-arm.h" 40 #elif V8_TARGET_ARCH_MIPS 41 #include "mips/register-allocator-mips.h" 42 #else 43 #error Unsupported target architecture. 44 #endif 45 46 namespace v8 { 47 namespace internal { 48 49 50 // ------------------------------------------------------------------------- 51 // Results 52 // 53 // Results encapsulate the compile-time values manipulated by the code 54 // generator. They can represent registers or constants. 55 56 class Result BASE_EMBEDDED { 57 public: 58 enum Type { 59 INVALID, 60 REGISTER, 61 CONSTANT 62 }; 63 64 // Construct an invalid result. 65 Result() { invalidate(); } 66 67 // Construct a register Result. 68 explicit Result(Register reg, NumberInfo::Type info = NumberInfo::kUnknown); 69 70 // Construct a Result whose value is a compile-time constant. 71 explicit Result(Handle<Object> value) { 72 value_ = TypeField::encode(CONSTANT) 73 | NumberInfoField::encode(NumberInfo::kUninitialized) 74 | DataField::encode(ConstantList()->length()); 75 ConstantList()->Add(value); 76 } 77 78 // The copy constructor and assignment operators could each create a new 79 // register reference. 80 inline Result(const Result& other); 81 82 inline Result& operator=(const Result& other); 83 84 inline ~Result(); 85 86 // Static indirection table for handles to constants. If a Result 87 // represents a constant, the data contains an index into this table 88 // of handles to the actual constants. 89 typedef ZoneList<Handle<Object> > ZoneObjectList; 90 91 static ZoneObjectList* ConstantList(); 92 93 // Clear the constants indirection table. 94 static void ClearConstantList() { 95 ConstantList()->Clear(); 96 } 97 98 inline void Unuse(); 99 100 Type type() const { return TypeField::decode(value_); } 101 102 void invalidate() { value_ = TypeField::encode(INVALID); } 103 104 NumberInfo::Type number_info(); 105 void set_number_info(NumberInfo::Type info); 106 bool is_number() { 107 return (number_info() & NumberInfo::kNumber) != 0; 108 } 109 bool is_smi() { return number_info() == NumberInfo::kSmi; } 110 bool is_heap_number() { return number_info() == NumberInfo::kHeapNumber; } 111 112 bool is_valid() const { return type() != INVALID; } 113 bool is_register() const { return type() == REGISTER; } 114 bool is_constant() const { return type() == CONSTANT; } 115 116 Register reg() const { 117 ASSERT(is_register()); 118 uint32_t reg = DataField::decode(value_); 119 Register result; 120 result.code_ = reg; 121 return result; 122 } 123 124 Handle<Object> handle() const { 125 ASSERT(type() == CONSTANT); 126 return ConstantList()->at(DataField::decode(value_)); 127 } 128 129 // Move this result to an arbitrary register. The register is not 130 // necessarily spilled from the frame or even singly-referenced outside 131 // it. 132 void ToRegister(); 133 134 // Move this result to a specified register. The register is spilled from 135 // the frame, and the register is singly-referenced (by this result) 136 // outside the frame. 137 void ToRegister(Register reg); 138 139 private: 140 uint32_t value_; 141 142 class TypeField: public BitField<Type, 0, 2> {}; 143 class NumberInfoField : public BitField<NumberInfo::Type, 2, 3> {}; 144 class DataField: public BitField<uint32_t, 5, 32 - 5> {}; 145 146 inline void CopyTo(Result* destination) const; 147 148 friend class CodeGeneratorScope; 149 }; 150 151 152 // ------------------------------------------------------------------------- 153 // Register file 154 // 155 // The register file tracks reference counts for the processor registers. 156 // It is used by both the register allocator and the virtual frame. 157 158 class RegisterFile BASE_EMBEDDED { 159 public: 160 RegisterFile() { Reset(); } 161 162 void Reset() { 163 for (int i = 0; i < kNumRegisters; i++) { 164 ref_counts_[i] = 0; 165 } 166 } 167 168 // Predicates and accessors for the reference counts. 169 bool is_used(int num) { 170 ASSERT(0 <= num && num < kNumRegisters); 171 return ref_counts_[num] > 0; 172 } 173 174 int count(int num) { 175 ASSERT(0 <= num && num < kNumRegisters); 176 return ref_counts_[num]; 177 } 178 179 // Record a use of a register by incrementing its reference count. 180 void Use(int num) { 181 ASSERT(0 <= num && num < kNumRegisters); 182 ref_counts_[num]++; 183 } 184 185 // Record that a register will no longer be used by decrementing its 186 // reference count. 187 void Unuse(int num) { 188 ASSERT(is_used(num)); 189 ref_counts_[num]--; 190 } 191 192 // Copy the reference counts from this register file to the other. 193 void CopyTo(RegisterFile* other) { 194 for (int i = 0; i < kNumRegisters; i++) { 195 other->ref_counts_[i] = ref_counts_[i]; 196 } 197 } 198 199 private: 200 static const int kNumRegisters = RegisterAllocatorConstants::kNumRegisters; 201 202 int ref_counts_[kNumRegisters]; 203 204 // Very fast inlined loop to find a free register. Used in 205 // RegisterAllocator::AllocateWithoutSpilling. Returns 206 // kInvalidRegister if no free register found. 207 int ScanForFreeRegister() { 208 for (int i = 0; i < RegisterAllocatorConstants::kNumRegisters; i++) { 209 if (!is_used(i)) return i; 210 } 211 return RegisterAllocatorConstants::kInvalidRegister; 212 } 213 214 friend class RegisterAllocator; 215 }; 216 217 218 // ------------------------------------------------------------------------- 219 // Register allocator 220 // 221 222 class RegisterAllocator BASE_EMBEDDED { 223 public: 224 static const int kNumRegisters = 225 RegisterAllocatorConstants::kNumRegisters; 226 static const int kInvalidRegister = 227 RegisterAllocatorConstants::kInvalidRegister; 228 229 explicit RegisterAllocator(CodeGenerator* cgen) : cgen_(cgen) {} 230 231 // True if the register is reserved by the code generator, false if it 232 // can be freely used by the allocator Defined in the 233 // platform-specific XXX-inl.h files.. 234 static inline bool IsReserved(Register reg); 235 236 // Convert between (unreserved) assembler registers and allocator 237 // numbers. Defined in the platform-specific XXX-inl.h files. 238 static inline int ToNumber(Register reg); 239 static inline Register ToRegister(int num); 240 241 // Predicates and accessors for the registers' reference counts. 242 bool is_used(int num) { return registers_.is_used(num); } 243 inline bool is_used(Register reg); 244 245 int count(int num) { return registers_.count(num); } 246 inline int count(Register reg); 247 248 // Explicitly record a reference to a register. 249 void Use(int num) { registers_.Use(num); } 250 inline void Use(Register reg); 251 252 // Explicitly record that a register will no longer be used. 253 void Unuse(int num) { registers_.Unuse(num); } 254 inline void Unuse(Register reg); 255 256 // Reset the register reference counts to free all non-reserved registers. 257 void Reset() { registers_.Reset(); } 258 259 // Initialize the register allocator for entry to a JS function. On 260 // entry, the (non-reserved) registers used by the JS calling 261 // convention are referenced and the other (non-reserved) registers 262 // are free. 263 inline void Initialize(); 264 265 // Allocate a free register and return a register result if possible or 266 // fail and return an invalid result. 267 Result Allocate(); 268 269 // Allocate a specific register if possible, spilling it from the 270 // current frame if necessary, or else fail and return an invalid 271 // result. 272 Result Allocate(Register target); 273 274 // Allocate a free register without spilling any from the current 275 // frame or fail and return an invalid result. 276 Result AllocateWithoutSpilling(); 277 278 // Allocate a free byte register without spilling any from the current 279 // frame or fail and return an invalid result. 280 Result AllocateByteRegisterWithoutSpilling(); 281 282 // Copy the internal state to a register file, to be restored later by 283 // RestoreFrom. 284 void SaveTo(RegisterFile* register_file) { 285 registers_.CopyTo(register_file); 286 } 287 288 // Restore the internal state. 289 void RestoreFrom(RegisterFile* register_file) { 290 register_file->CopyTo(®isters_); 291 } 292 293 private: 294 CodeGenerator* cgen_; 295 RegisterFile registers_; 296 }; 297 298 } } // namespace v8::internal 299 300 #endif // V8_REGISTER_ALLOCATOR_H_ 301