Reduce dynamic memory allocation in css jit.
[WebKit-https.git] / Source / WebCore / cssjit / RegisterAllocator.h
1 /*
2  * Copyright (C) 2013, 2014 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. AND ITS CONTRIBUTORS ``AS IS''
14  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
15  * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
17  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
18  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
19  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
20  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
21  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
22  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
23  * THE POSSIBILITY OF SUCH DAMAGE.
24  */
25
26 #ifndef RegisterAllocator_h
27 #define RegisterAllocator_h
28
29 #if ENABLE(CSS_SELECTOR_JIT)
30
31 #include <JavaScriptCore/MacroAssembler.h>
32 #include <wtf/Deque.h>
33 #include <wtf/Vector.h>
34
35 namespace WebCore {
36
37 #if CPU(ARM64)
38 static const JSC::MacroAssembler::RegisterID callerSavedRegisters[] = {
39     JSC::ARM64Registers::x0,
40     JSC::ARM64Registers::x1,
41     JSC::ARM64Registers::x2,
42     JSC::ARM64Registers::x3,
43     JSC::ARM64Registers::x4,
44     JSC::ARM64Registers::x5,
45     JSC::ARM64Registers::x6,
46     JSC::ARM64Registers::x7,
47     JSC::ARM64Registers::x8,
48     JSC::ARM64Registers::x9,
49     JSC::ARM64Registers::x10,
50     JSC::ARM64Registers::x11,
51     JSC::ARM64Registers::x12,
52     JSC::ARM64Registers::x13,
53     JSC::ARM64Registers::x14,
54 };
55 static const JSC::MacroAssembler::RegisterID calleeSavedRegisters[] = {
56     JSC::ARM64Registers::x19
57 };
58 static const JSC::MacroAssembler::RegisterID tempRegister = JSC::ARM64Registers::x15;
59 #elif CPU(ARM_THUMB2)
60 static const JSC::MacroAssembler::RegisterID callerSavedRegisters[] {
61     JSC::ARMRegisters::r0,
62     JSC::ARMRegisters::r1,
63     JSC::ARMRegisters::r2,
64     JSC::ARMRegisters::r3,
65     JSC::ARMRegisters::r9,
66 };
67 static const JSC::MacroAssembler::RegisterID calleeSavedRegisters[] = {
68     JSC::ARMRegisters::r4,
69     JSC::ARMRegisters::r5,
70     JSC::ARMRegisters::r7,
71     JSC::ARMRegisters::r8,
72     JSC::ARMRegisters::r10,
73     JSC::ARMRegisters::r11,
74 };
75 // r6 is also used as addressTempRegister in the macro assembler. It is saved in the prologue and restored in the epilogue.
76 static const JSC::MacroAssembler::RegisterID tempRegister = JSC::ARMRegisters::r6;
77 #elif CPU(X86_64)
78 static const JSC::MacroAssembler::RegisterID callerSavedRegisters[] = {
79     JSC::X86Registers::eax,
80     JSC::X86Registers::ecx,
81     JSC::X86Registers::edx,
82     JSC::X86Registers::esi,
83     JSC::X86Registers::edi,
84     JSC::X86Registers::r8,
85     JSC::X86Registers::r9,
86     JSC::X86Registers::r10,
87     JSC::X86Registers::r11
88 };
89 static const JSC::MacroAssembler::RegisterID calleeSavedRegisters[] = {
90     JSC::X86Registers::r12,
91     JSC::X86Registers::r13,
92     JSC::X86Registers::r14,
93     JSC::X86Registers::r15
94 };
95 #else
96 #error RegisterAllocator has no defined registers for the architecture.
97 #endif
98 static const unsigned calleeSavedRegisterCount = WTF_ARRAY_LENGTH(calleeSavedRegisters);
99 static const unsigned registerCount = calleeSavedRegisterCount + WTF_ARRAY_LENGTH(callerSavedRegisters);
100
101 class RegisterAllocator {
102 public:
103     RegisterAllocator();
104     ~RegisterAllocator();
105
106     unsigned availableRegisterCount() const { return m_registers.size(); }
107
108     JSC::MacroAssembler::RegisterID allocateRegister()
109     {
110         RELEASE_ASSERT(m_registers.size());
111         JSC::MacroAssembler::RegisterID registerID = m_registers.first();
112         m_registers.removeFirst();
113         ASSERT(!m_allocatedRegisters.contains(registerID));
114         m_allocatedRegisters.append(registerID);
115         return registerID;
116     }
117
118     void allocateRegister(JSC::MacroAssembler::RegisterID registerID)
119     {
120         for (auto it = m_registers.begin(); it != m_registers.end(); ++it) {
121             if (*it == registerID) {
122                 m_registers.remove(it);
123                 ASSERT(!m_allocatedRegisters.contains(registerID));
124                 m_allocatedRegisters.append(registerID);
125                 return;
126             }
127         }
128         RELEASE_ASSERT_NOT_REACHED();
129     }
130     
131     JSC::MacroAssembler::RegisterID allocateRegisterWithPreference(JSC::MacroAssembler::RegisterID preferredRegister)
132     {
133         for (auto it = m_registers.begin(); it != m_registers.end(); ++it) {
134             if (*it == preferredRegister) {
135                 m_registers.remove(it);
136                 ASSERT(!m_allocatedRegisters.contains(preferredRegister));
137                 m_allocatedRegisters.append(preferredRegister);
138                 return preferredRegister;
139             }
140         }
141         return allocateRegister();
142     }
143
144     void deallocateRegister(JSC::MacroAssembler::RegisterID registerID)
145     {
146         ASSERT(m_allocatedRegisters.contains(registerID));
147         // Most allocation/deallocation happen in stack-like order. In the common case, this
148         // just removes the last item.
149         m_allocatedRegisters.remove(m_allocatedRegisters.reverseFind(registerID));
150         for (auto unallocatedRegister : m_registers)
151             RELEASE_ASSERT(unallocatedRegister != registerID);
152         m_registers.append(registerID);
153     }
154
155     const Vector<JSC::MacroAssembler::RegisterID, calleeSavedRegisterCount>& reserveCalleeSavedRegisters(unsigned count)
156     {
157         RELEASE_ASSERT(count <= WTF_ARRAY_LENGTH(calleeSavedRegisters));
158         RELEASE_ASSERT(!m_reservedCalleeSavedRegisters.size());
159         for (unsigned i = 0; i < count; ++i) {
160             JSC::MacroAssembler::RegisterID registerId = calleeSavedRegisters[i];
161             m_reservedCalleeSavedRegisters.append(registerId);
162             m_registers.append(registerId);
163         }
164         return m_reservedCalleeSavedRegisters;
165     }
166
167     Vector<JSC::MacroAssembler::RegisterID, calleeSavedRegisterCount> restoreCalleeSavedRegisters()
168     {
169         Vector<JSC::MacroAssembler::RegisterID, calleeSavedRegisterCount> registers(m_reservedCalleeSavedRegisters);
170         m_reservedCalleeSavedRegisters.clear();
171         return registers;
172     }
173
174     const Vector<JSC::MacroAssembler::RegisterID, registerCount>& allocatedRegisters() const { return m_allocatedRegisters; }
175
176     static bool isValidRegister(JSC::MacroAssembler::RegisterID registerID)
177     {
178 #if CPU(ARM64)
179         return (registerID >= JSC::ARM64Registers::x0 && registerID <= JSC::ARM64Registers::x14)
180             || registerID == JSC::ARM64Registers::x19;
181 #elif CPU(ARM_THUMB2)
182         return registerID >= JSC::ARMRegisters::r0 && registerID <= JSC::ARMRegisters::r11 && registerID != JSC::ARMRegisters::r6;
183 #elif CPU(X86_64)
184         return (registerID >= JSC::X86Registers::eax && registerID <= JSC::X86Registers::edx)
185             || (registerID >= JSC::X86Registers::esi && registerID <= JSC::X86Registers::r15);
186 #else
187 #error RegisterAllocator does not define the valid register range for the current architecture.
188 #endif
189     }
190     
191     static bool isCallerSavedRegister(JSC::MacroAssembler::RegisterID registerID)
192     {
193         ASSERT(isValidRegister(registerID));
194 #if CPU(ARM64)
195         return registerID >= JSC::ARM64Registers::x0 && registerID <= JSC::ARM64Registers::x14;
196 #elif CPU(ARM_THUMB2)
197         return (registerID >= JSC::ARMRegisters::r0 && registerID <= JSC::ARMRegisters::r3)
198             || registerID == JSC::ARMRegisters::r9;
199 #elif CPU(X86_64)
200         return (registerID >= JSC::X86Registers::eax && registerID <= JSC::X86Registers::edx)
201             || (registerID >= JSC::X86Registers::esi && registerID <= JSC::X86Registers::r11);
202 #else
203 #error RegisterAllocator does not define the valid caller saved register range for the current architecture.
204 #endif
205     }
206
207 private:
208     Deque<JSC::MacroAssembler::RegisterID, registerCount> m_registers;
209     Vector<JSC::MacroAssembler::RegisterID, registerCount> m_allocatedRegisters;
210     Vector<JSC::MacroAssembler::RegisterID, calleeSavedRegisterCount> m_reservedCalleeSavedRegisters;
211 };
212
213 class LocalRegister {
214 public:
215     explicit LocalRegister(RegisterAllocator& allocator)
216         : m_allocator(allocator)
217         , m_register(allocator.allocateRegister())
218     {
219     }
220
221     ~LocalRegister()
222     {
223         m_allocator.deallocateRegister(m_register);
224     }
225
226     operator JSC::MacroAssembler::RegisterID() const
227     {
228         return m_register;
229     }
230
231 protected:
232     explicit LocalRegister(RegisterAllocator& allocator, JSC::MacroAssembler::RegisterID registerID)
233         : m_allocator(allocator)
234         , m_register(registerID)
235     {
236     }
237     RegisterAllocator& m_allocator;
238     JSC::MacroAssembler::RegisterID m_register;
239 };
240
241 class LocalRegisterWithPreference : public LocalRegister {
242 public:
243     explicit LocalRegisterWithPreference(RegisterAllocator& allocator, JSC::MacroAssembler::RegisterID preferredRegister)
244         : LocalRegister(allocator, allocator.allocateRegisterWithPreference(preferredRegister))
245     {
246     }
247 };
248     
249 inline RegisterAllocator::RegisterAllocator()
250 {
251     for (unsigned i = 0; i < WTF_ARRAY_LENGTH(callerSavedRegisters); ++i)
252         m_registers.append(callerSavedRegisters[i]);
253 }
254
255 inline RegisterAllocator::~RegisterAllocator()
256 {
257     RELEASE_ASSERT(m_reservedCalleeSavedRegisters.isEmpty());
258 }
259
260 } // namespace WebCore
261
262 #endif // ENABLE(CSS_SELECTOR_JIT)
263
264 #endif // RegisterAllocator_h
265