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