1/* 2 * Copyright (C) 2011 Apple Inc. All rights reserved. 3 * 4 * Redistribution and use in source and binary forms, with or without 5 * modification, are permitted provided that the following conditions 6 * are met: 7 * 1. Redistributions of source code must retain the above copyright 8 * notice, this list of conditions and the following disclaimer. 9 * 2. Redistributions in binary form must reproduce the above copyright 10 * notice, this list of conditions and the following disclaimer in the 11 * documentation and/or other materials provided with the distribution. 12 * 13 * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY 14 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR 17 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 18 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 19 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 20 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY 21 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 23 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 24 */ 25 26#ifndef DFGRegisterBank_h 27#define DFGRegisterBank_h 28 29#if ENABLE(DFG_JIT) 30 31#include "DFGCommon.h" 32#include "FPRInfo.h" 33#include "GPRInfo.h" 34 35namespace JSC { namespace DFG { 36 37// === RegisterBank === 38// 39// This class is used to implement the GPR and FPR register banks. 40// All registers have two pieces of state associated with them: 41// a lock count (used to indicate this register is already in use 42// in code generation of the current node, and cannot be spilled or 43// allocated as a temporary), and VirtualRegister 'name', recording 44// which value (if any) a machine register currently holds. 45// Either or both of these pieces of information may be valid for a 46// given register. A register may be: 47// 48// - unlocked, and unnamed: Available for allocation. 49// - locked, but unnamed: Already allocated as a temporary or 50// result for the current node. 51// - unlocked, but named: Contains the result of a prior operation, 52// not yet in use for this node, 53// - locked, but named: Contains the result of a prior operation, 54// already allocated as a operand to the 55// current operation. 56// 57// For every named register we also record a hint value indicating 58// the order in which registers should be selected to be spilled; 59// registers that can be more cheaply spilled and/or filled should 60// be selected first. 61// 62// Locking register is a strong retention mechanism; a locked register 63// will never be reallocated (this is used to ensure the operands to 64// the current node are in registers). Naming, conversely, in a weak 65// retention mechanism - allocating a register may force a named value 66// to be spilled. 67// 68// All named values must be given a hint that is greater than Min and 69// less than Max. 70template<class BankInfo> 71class RegisterBank { 72 typedef typename BankInfo::RegisterType RegID; 73 static const size_t NUM_REGS = BankInfo::numberOfRegisters; 74 75 typedef uint32_t SpillHint; 76 static const SpillHint SpillHintInvalid = 0xffffffff; 77 78public: 79 RegisterBank() 80 { 81 } 82 83 // Attempt to allocate a register - this function finds an unlocked 84 // register, locks it, and returns it. If none can be found, this 85 // returns -1 (InvalidGPRReg or InvalidFPRReg). 86 RegID tryAllocate() 87 { 88 VirtualRegister ignored = VirtualRegister(); 89 90 for (uint32_t i = 0; i < NUM_REGS; ++i) { 91 if (!m_data[i].lockCount && !m_data[i].name.isValid()) 92 return allocateInternal(i, ignored); 93 } 94 95 return (RegID)-1; 96 } 97 98 // Allocate a register - this function finds an unlocked register, 99 // locks it, and returns it. If any named registers exist, one 100 // of these should be selected to be allocated. If all unlocked 101 // registers are named, then one of the named registers will need 102 // to be spilled. In this case the register selected to be spilled 103 // will be one of the registers that has the lowest 'spillOrder' 104 // cost associated with it. 105 // 106 // This method select the register to be allocated, and calls the 107 // private 'allocateInternal' method to update internal data 108 // structures accordingly. 109 RegID allocate(VirtualRegister &spillMe) 110 { 111 uint32_t currentLowest = NUM_REGS; 112 SpillHint currentSpillOrder = SpillHintInvalid; 113 114 // This loop is broken into two halves, looping from the last allocated 115 // register (the register returned last time this method was called) to 116 // the maximum register value, then from 0 to the last allocated. 117 // This implements a simple round-robin like approach to try to reduce 118 // thrash, and minimize time spent scanning locked registers in allocation. 119 // If a unlocked and unnamed register is found return it immediately. 120 // Otherwise, find the first unlocked register with the lowest spillOrder. 121 for (uint32_t i = 0 ; i < NUM_REGS; ++i) { 122 // (1) If the current register is locked, it is not a candidate. 123 if (m_data[i].lockCount) 124 continue; 125 // (2) If the current register's spill order is 0, pick this! – unassigned registers have spill order 0. 126 SpillHint spillOrder = m_data[i].spillOrder; 127 if (spillOrder == SpillHintInvalid) 128 return allocateInternal(i, spillMe); 129 // If this register is better (has a lower spill order value) than any prior 130 // candidate, then record it. 131 if (spillOrder < currentSpillOrder) { 132 currentSpillOrder = spillOrder; 133 currentLowest = i; 134 } 135 } 136 137 // Deadlock check - this could only occur is all registers are locked! 138 ASSERT(currentLowest != NUM_REGS && currentSpillOrder != SpillHintInvalid); 139 // There were no available registers; currentLowest will need to be spilled. 140 return allocateInternal(currentLowest, spillMe); 141 } 142 143 // Allocates the given register, even if this will force a spill. 144 VirtualRegister allocateSpecific(RegID reg) 145 { 146 unsigned index = BankInfo::toIndex(reg); 147 148 ++m_data[index].lockCount; 149 VirtualRegister name = nameAtIndex(index); 150 if (name.isValid()) 151 releaseAtIndex(index); 152 153 return name; 154 } 155 156 // retain/release - these methods are used to associate/disassociate names 157 // with values in registers. retain should only be called on locked registers. 158 void retain(RegID reg, VirtualRegister name, SpillHint spillOrder) 159 { 160 unsigned index = BankInfo::toIndex(reg); 161 162 // SpillHint must be valid. 163 ASSERT(spillOrder != SpillHintInvalid); 164 // 'index' must be a valid, locked register. 165 ASSERT(index < NUM_REGS); 166 ASSERT(m_data[index].lockCount); 167 // 'index' should not currently be named, the new name must be valid. 168 ASSERT(!m_data[index].name.isValid()); 169 ASSERT(name.isValid()); 170 // 'index' should not currently have a spillOrder. 171 ASSERT(m_data[index].spillOrder == SpillHintInvalid); 172 173 m_data[index].name = name; 174 m_data[index].spillOrder = spillOrder; 175 } 176 void release(RegID reg) 177 { 178 releaseAtIndex(BankInfo::toIndex(reg)); 179 } 180 181 // lock/unlock register, ensures that they are not spilled. 182 void lock(RegID reg) 183 { 184 unsigned index = BankInfo::toIndex(reg); 185 186 ASSERT(index < NUM_REGS); 187 ++m_data[index].lockCount; 188 ASSERT(m_data[index].lockCount); 189 } 190 void unlock(RegID reg) 191 { 192 unsigned index = BankInfo::toIndex(reg); 193 194 ASSERT(index < NUM_REGS); 195 ASSERT(m_data[index].lockCount); 196 --m_data[index].lockCount; 197 } 198 bool isLocked(RegID reg) const 199 { 200 return isLockedAtIndex(BankInfo::toIndex(reg)); 201 } 202 203 // Get the name (VirtualRegister) associated with the 204 // given register (or default VirtualRegister() for none). 205 VirtualRegister name(RegID reg) const 206 { 207 return nameAtIndex(BankInfo::toIndex(reg)); 208 } 209 210 bool isInUse(RegID reg) const 211 { 212 return isLocked(reg) || name(reg).isValid(); 213 } 214 215 void dump() 216 { 217 // For each register, print the VirtualRegister 'name'. 218 for (uint32_t i =0; i < NUM_REGS; ++i) { 219 if (m_data[i].name.isValid()) 220 dataLogF("[%02d]", m_data[i].name.offset()); 221 else 222 dataLogF("[--]"); 223 } 224 dataLogF("\n"); 225 } 226 227 class iterator { 228 friend class RegisterBank<BankInfo>; 229 public: 230 VirtualRegister name() const 231 { 232 return m_bank->nameAtIndex(m_index); 233 } 234 235 bool isLocked() const 236 { 237 return m_bank->isLockedAtIndex(m_index); 238 } 239 240 void release() const 241 { 242 m_bank->releaseAtIndex(m_index); 243 } 244 245 RegID regID() const 246 { 247 return BankInfo::toRegister(m_index); 248 } 249 250#ifndef NDEBUG 251 const char* debugName() const 252 { 253 return BankInfo::debugName(regID()); 254 } 255#endif 256 257 iterator& operator++() 258 { 259 ++m_index; 260 return *this; 261 } 262 263 bool operator!=(const iterator& other) const 264 { 265 ASSERT(m_bank == other.m_bank); 266 return m_index != other.m_index; 267 } 268 269 unsigned index() const 270 { 271 return m_index; 272 } 273 274 private: 275 iterator(RegisterBank<BankInfo>* bank, unsigned index) 276 : m_bank(bank) 277 , m_index(index) 278 { 279 } 280 281 RegisterBank<BankInfo>* m_bank; 282 unsigned m_index; 283 }; 284 285 iterator begin() 286 { 287 return iterator(this, 0); 288 } 289 290 iterator end() 291 { 292 return iterator(this, NUM_REGS); 293 } 294 295private: 296 bool isLockedAtIndex(unsigned index) const 297 { 298 ASSERT(index < NUM_REGS); 299 return m_data[index].lockCount; 300 } 301 302 VirtualRegister nameAtIndex(unsigned index) const 303 { 304 ASSERT(index < NUM_REGS); 305 return m_data[index].name; 306 } 307 308 void releaseAtIndex(unsigned index) 309 { 310 // 'index' must be a valid register. 311 ASSERT(index < NUM_REGS); 312 // 'index' should currently be named. 313 ASSERT(m_data[index].name.isValid()); 314 // 'index' should currently have a valid spill order. 315 ASSERT(m_data[index].spillOrder != SpillHintInvalid); 316 317 m_data[index].name = VirtualRegister(); 318 m_data[index].spillOrder = SpillHintInvalid; 319 } 320 321 // Used by 'allocate', above, to update inforamtion in the map. 322 RegID allocateInternal(uint32_t i, VirtualRegister &spillMe) 323 { 324 // 'i' must be a valid, unlocked register. 325 ASSERT(i < NUM_REGS && !m_data[i].lockCount); 326 327 // Return the VirtualRegister of the named value currently stored in 328 // the register being returned - or default VirtualRegister() if none. 329 spillMe = m_data[i].name; 330 331 // Clear any name/spillOrder currently associated with the register, 332 m_data[i] = MapEntry(); 333 // Mark the register as locked (with a lock count of 1). 334 m_data[i].lockCount = 1; 335 336 return BankInfo::toRegister(i); 337 } 338 339 // === MapEntry === 340 // 341 // This structure provides information for an individual machine register 342 // being managed by the RegisterBank. For each register we track a lock 343 // count, name and spillOrder hint. 344 struct MapEntry { 345 MapEntry() 346 : name(VirtualRegister()) 347 , spillOrder(SpillHintInvalid) 348 , lockCount(0) 349 { 350 } 351 352 VirtualRegister name; 353 SpillHint spillOrder; 354 uint32_t lockCount; 355 }; 356 357 // Holds the current status of all registers. 358 MapEntry m_data[NUM_REGS]; 359}; 360 361typedef RegisterBank<GPRInfo>::iterator gpr_iterator; 362typedef RegisterBank<FPRInfo>::iterator fpr_iterator; 363 364} } // namespace JSC::DFG 365 366#endif 367#endif 368