ffa822a184c85c4cc1153fef6bf3d7f0c0148457
[WebKit-https.git] / Source / JavaScriptCore / dfg / DFGRegisterBank.h
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
35 namespace 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.
70 template<class BankInfo>
71 class 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
78 public:
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 #ifndef NDEBUG
216     void dump()
217     {
218         // For each register, print the VirtualRegister 'name'.
219         for (uint32_t i =0; i < NUM_REGS; ++i) {
220             if (m_data[i].name.isValid())
221                 dataLogF("[%02d]", m_data[i].name.offset());
222             else
223                 dataLogF("[--]");
224         }
225         dataLogF("\n");
226     }
227 #endif
228
229     class iterator {
230     friend class RegisterBank<BankInfo>;
231     public:
232         VirtualRegister name() const
233         {
234             return m_bank->nameAtIndex(m_index);
235         }
236
237         bool isLocked() const
238         {
239             return m_bank->isLockedAtIndex(m_index);
240         }
241
242         void release() const
243         {
244             m_bank->releaseAtIndex(m_index);
245         }
246
247         RegID regID() const
248         {
249             return BankInfo::toRegister(m_index);
250         }
251
252 #ifndef NDEBUG
253         const char* debugName() const
254         {
255             return BankInfo::debugName(regID());
256         }
257 #endif
258
259         iterator& operator++()
260         {
261             ++m_index;
262             return *this;
263         }
264
265         bool operator!=(const iterator& other) const
266         {
267             ASSERT(m_bank == other.m_bank);
268             return m_index != other.m_index;
269         }
270
271         unsigned index() const
272         {
273             return m_index;
274         }
275
276     private:
277         iterator(RegisterBank<BankInfo>* bank, unsigned index)
278             : m_bank(bank)
279             , m_index(index)
280         {
281         }
282
283         RegisterBank<BankInfo>* m_bank;
284         unsigned m_index;
285     };
286
287     iterator begin()
288     {
289         return iterator(this, 0);
290     }
291
292     iterator end()
293     {
294         return iterator(this, NUM_REGS);
295     }
296
297 private:
298     bool isLockedAtIndex(unsigned index) const
299     {
300         ASSERT(index < NUM_REGS);
301         return m_data[index].lockCount;
302     }
303
304     VirtualRegister nameAtIndex(unsigned index) const
305     {
306         ASSERT(index < NUM_REGS);
307         return m_data[index].name;
308     }
309
310     void releaseAtIndex(unsigned index)
311     {
312         // 'index' must be a valid register.
313         ASSERT(index < NUM_REGS);
314         // 'index' should currently be named.
315         ASSERT(m_data[index].name.isValid());
316         // 'index' should currently have a valid spill order.
317         ASSERT(m_data[index].spillOrder != SpillHintInvalid);
318
319         m_data[index].name = VirtualRegister();
320         m_data[index].spillOrder = SpillHintInvalid;
321     }
322
323     // Used by 'allocate', above, to update inforamtion in the map.
324     RegID allocateInternal(uint32_t i, VirtualRegister &spillMe)
325     {
326         // 'i' must be a valid, unlocked register.
327         ASSERT(i < NUM_REGS && !m_data[i].lockCount);
328
329         // Return the VirtualRegister of the named value currently stored in
330         // the register being returned - or default VirtualRegister() if none.
331         spillMe = m_data[i].name;
332
333         // Clear any name/spillOrder currently associated with the register,
334         m_data[i] = MapEntry();
335         // Mark the register as locked (with a lock count of 1).
336         m_data[i].lockCount = 1;
337
338         return BankInfo::toRegister(i);
339     }
340
341     // === MapEntry ===
342     //
343     // This structure provides information for an individual machine register
344     // being managed by the RegisterBank. For each register we track a lock
345     // count, name and spillOrder hint.
346     struct MapEntry {
347         MapEntry()
348             : name(VirtualRegister())
349             , spillOrder(SpillHintInvalid)
350             , lockCount(0)
351         {
352         }
353
354         VirtualRegister name;
355         SpillHint spillOrder;
356         uint32_t lockCount;
357     };
358
359     // Holds the current status of all registers.
360     MapEntry m_data[NUM_REGS];
361 };
362
363 typedef RegisterBank<GPRInfo>::iterator gpr_iterator;
364 typedef RegisterBank<FPRInfo>::iterator fpr_iterator;
365
366 } } // namespace JSC::DFG
367
368 #endif
369 #endif