2 * Copyright (C) 2011 Apple Inc. All rights reserved.
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
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.
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.
26 #ifndef DFGRegisterBank_h
27 #define DFGRegisterBank_h
31 #include <dfg/DFGNode.h>
33 namespace JSC { namespace DFG {
35 // === RegisterBank ===
37 // This class is used to implement the GPR and FPR register banks.
38 // All registers have two pieces of state associated with them:
39 // a lock count (used to indicate this register is already in use
40 // in code generation of the current node, and cannot be spilled or
41 // allocated as a temporary), and VirtualRegister 'name', recording
42 // which value (if any) a machine register currently holds.
43 // Either or both of these pieces of information may be valid for a
44 // given register. A register may be:
46 // - unlocked, and unnamed: Available for allocation.
47 // - locked, but unnamed: Already allocated as a temporary or
48 // result for the current node.
49 // - unlocked, but named: Contains the result of a prior operation,
50 // not yet in use for this node,
51 // - locked, but named: Contains the result of a prior operation,
52 // already allocated as a operand to the
55 // For every named register we also record a hint value indicating
56 // the order in which registers should be selected to be spilled;
57 // registers that can be more cheaply spilled and/or filled should
60 // Locking register is a strong retention mechanism; a locked register
61 // will never be reallocated (this is used to ensure the operands to
62 // the current node are in registers). Naming, conversely, in a weak
63 // retention mechanism - allocating a register may force a named value
66 // All named values must be given a hint that is greater than Min and
68 template<class BankInfo>
70 typedef typename BankInfo::RegisterType RegID;
71 static const size_t NUM_REGS = BankInfo::numberOfRegisters;
73 typedef uint32_t SpillHint;
74 static const SpillHint SpillHintInvalid = 0xffffffff;
78 : m_lastAllocated(NUM_REGS - 1)
82 // Attempt to allocate a register - this function finds an unlocked
83 // register, locks it, and returns it. If none can be found, this
84 // returns -1 (InvalidGPRReg or InvalidFPRReg).
87 VirtualRegister ignored;
89 for (uint32_t i = m_lastAllocated + 1; i < NUM_REGS; ++i) {
90 if (!m_data[i].lockCount && m_data[i].name == InvalidVirtualRegister)
91 return allocateInternal(i, ignored);
93 // Loop over the remaining entries.
94 for (uint32_t i = 0; i <= m_lastAllocated; ++i) {
95 if (!m_data[i].lockCount && m_data[i].name == InvalidVirtualRegister)
96 return allocateInternal(i, ignored);
102 // Allocate a register - this function finds an unlocked register,
103 // locks it, and returns it. If any named registers exist, one
104 // of these should be selected to be allocated. If all unlocked
105 // registers are named, then one of the named registers will need
106 // to be spilled. In this case the register selected to be spilled
107 // will be one of the registers that has the lowest 'spillOrder'
108 // cost associated with it.
110 // This method select the register to be allocated, and calls the
111 // private 'allocateInternal' method to update internal data
112 // structures accordingly.
113 RegID allocate(VirtualRegister &spillMe)
115 uint32_t currentLowest = NUM_REGS;
116 SpillHint currentSpillOrder = SpillHintInvalid;
118 // Scan through all register, starting at the last allocated & looping around.
119 ASSERT(m_lastAllocated < NUM_REGS);
121 // This loop is broken into two halves, looping from the last allocated
122 // register (the register returned last time this method was called) to
123 // the maximum register value, then from 0 to the last allocated.
124 // This implements a simple round-robin like approach to try to reduce
125 // thrash, and minimize time spent scanning locked registers in allocation.
126 // If a unlocked and unnamed register is found return it immediately.
127 // Otherwise, find the first unlocked register with the lowest spillOrder.
128 for (uint32_t i = m_lastAllocated + 1; i < NUM_REGS; ++i) {
129 // (1) If the current register is locked, it is not a candidate.
130 if (m_data[i].lockCount)
132 // (2) If the current register's spill order is 0, pick this! – unassigned registers have spill order 0.
133 SpillHint spillOrder = m_data[i].spillOrder;
134 if (spillOrder == SpillHintInvalid)
135 return allocateInternal(i, spillMe);
136 // If this register is better (has a lower spill order value) than any prior
137 // candidate, then record it.
138 if (spillOrder < currentSpillOrder) {
139 currentSpillOrder = spillOrder;
143 // Loop over the remaining entries.
144 for (uint32_t i = 0; i <= m_lastAllocated; ++i) {
145 if (m_data[i].lockCount)
147 SpillHint spillOrder = m_data[i].spillOrder;
148 if (spillOrder == SpillHintInvalid)
149 return allocateInternal(i, spillMe);
150 if (spillOrder < currentSpillOrder) {
151 currentSpillOrder = spillOrder;
156 // Deadlock check - this could only occur is all registers are locked!
157 ASSERT(currentLowest != NUM_REGS && currentSpillOrder != SpillHintInvalid);
158 // There were no available registers; currentLowest will need to be spilled.
159 return allocateInternal(currentLowest, spillMe);
162 // Allocates the given register, even if this will force a spill.
163 VirtualRegister allocateSpecific(RegID reg)
165 unsigned index = BankInfo::toIndex(reg);
167 ++m_data[index].lockCount;
168 VirtualRegister name = nameAtIndex(index);
169 if (name != InvalidVirtualRegister)
170 releaseAtIndex(index);
175 // retain/release - these methods are used to associate/disassociate names
176 // with values in registers. retain should only be called on locked registers.
177 void retain(RegID reg, VirtualRegister name, SpillHint spillOrder)
179 unsigned index = BankInfo::toIndex(reg);
181 // SpillHint must be valid.
182 ASSERT(spillOrder != SpillHintInvalid);
183 // 'index' must be a valid, locked register.
184 ASSERT(index < NUM_REGS);
185 ASSERT(m_data[index].lockCount);
186 // 'index' should not currently be named, the new name must be valid.
187 ASSERT(m_data[index].name == InvalidVirtualRegister);
188 ASSERT(name != InvalidVirtualRegister);
189 // 'index' should not currently have a spillOrder.
190 ASSERT(m_data[index].spillOrder == SpillHintInvalid);
192 m_data[index].name = name;
193 m_data[index].spillOrder = spillOrder;
195 void release(RegID reg)
197 releaseAtIndex(BankInfo::toIndex(reg));
200 // lock/unlock register, ensures that they are not spilled.
203 unsigned index = BankInfo::toIndex(reg);
205 ASSERT(index < NUM_REGS);
206 ++m_data[index].lockCount;
207 ASSERT(m_data[index].lockCount);
209 void unlock(RegID reg)
211 unsigned index = BankInfo::toIndex(reg);
213 ASSERT(index < NUM_REGS);
214 ASSERT(m_data[index].lockCount);
215 --m_data[index].lockCount;
217 bool isLocked(RegID reg) const
219 return isLockedAtIndex(BankInfo::toIndex(reg));
222 // Get the name (VirtualRegister) associated with the
223 // given register (or InvalidVirtualRegister for none).
224 VirtualRegister name(RegID reg) const
226 return nameAtIndex(BankInfo::toIndex(reg));
232 // For each register, print the VirtualRegister 'name'.
233 for (uint32_t i =0; i < NUM_REGS; ++i) {
234 if (m_data[i].name != InvalidVirtualRegister)
235 fprintf(stderr, "[%02d]", m_data[i].name);
237 fprintf(stderr, "[--]");
239 fprintf(stderr, "\n");
244 friend class RegisterBank<BankInfo>;
246 VirtualRegister name() const
248 return m_bank->nameAtIndex(m_index);
251 bool isLocked() const
253 return m_bank->isLockedAtIndex(m_index);
258 m_bank->releaseAtIndex(m_index);
263 return BankInfo::toRegister(m_index);
267 const char* debugName() const
269 return BankInfo::debugName(regID());
273 iterator& operator++()
279 bool operator!=(const iterator& other) const
281 ASSERT(m_bank == other.m_bank);
282 return m_index != other.m_index;
285 unsigned index() const
291 iterator(RegisterBank<BankInfo>* bank, unsigned index)
297 RegisterBank<BankInfo>* m_bank;
303 return iterator(this, 0);
308 return iterator(this, NUM_REGS);
312 bool isLockedAtIndex(unsigned index) const
314 ASSERT(index < NUM_REGS);
315 return m_data[index].lockCount;
318 VirtualRegister nameAtIndex(unsigned index) const
320 ASSERT(index < NUM_REGS);
321 return m_data[index].name;
324 void releaseAtIndex(unsigned index)
326 // 'index' must be a valid register.
327 ASSERT(index < NUM_REGS);
328 // 'index' should currently be named.
329 ASSERT(m_data[index].name != InvalidVirtualRegister);
330 // 'index' should currently have a valid spill order.
331 ASSERT(m_data[index].spillOrder != SpillHintInvalid);
333 m_data[index].name = InvalidVirtualRegister;
334 m_data[index].spillOrder = SpillHintInvalid;
337 // Used by 'allocate', above, to update inforamtion in the map.
338 RegID allocateInternal(uint32_t i, VirtualRegister &spillMe)
340 // 'i' must be a valid, unlocked register.
341 ASSERT(i < NUM_REGS && !m_data[i].lockCount);
343 // Return the VirtualRegister of the named value currently stored in
344 // the register being returned - or InvalidVirtualRegister if none.
345 spillMe = m_data[i].name;
347 // Clear any name/spillOrder currently associated with the register,
348 m_data[i] = MapEntry();
349 // Mark the register as locked (with a lock count of 1).
350 m_data[i].lockCount = 1;
353 return BankInfo::toRegister(i);
358 // This structure provides information for an individual machine register
359 // being managed by the RegisterBank. For each register we track a lock
360 // count, name and spillOrder hint.
363 : name(InvalidVirtualRegister)
364 , spillOrder(SpillHintInvalid)
369 VirtualRegister name;
370 SpillHint spillOrder;
374 // Holds the current status of all registers.
375 MapEntry m_data[NUM_REGS];
376 // Used to to implement a simple round-robin like allocation scheme.
377 uint32_t m_lastAllocated;
380 } } // namespace JSC::DFG