37cbb24fe2f2cbb348edc4701397fd891430f501
[WebKit-https.git] / Source / JavaScriptCore / jit / CompactJITCodeMap.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  *
8  * 1.  Redistributions of source code must retain the above copyright
9  *     notice, this list of conditions and the following disclaimer.
10  * 2.  Redistributions in binary form must reproduce the above copyright
11  *     notice, this list of conditions and the following disclaimer in the
12  *     documentation and/or other materials provided with the distribution.
13  * 3.  Neither the name of Apple Inc. ("Apple") nor the names of
14  *     its contributors may be used to endorse or promote products derived
15  *     from this software without specific prior written permission.
16  *
17  * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
18  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
19  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
20  * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
21  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
22  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
23  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
24  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27  */
28
29 #ifndef CompactJITCodeMap_h
30 #define CompactJITCodeMap_h
31
32 #include <wtf/Assertions.h>
33 #include <wtf/FastMalloc.h>
34 #include <wtf/FastMalloc.h>
35 #include <wtf/OwnPtr.h>
36 #include <wtf/PassOwnPtr.h>
37 #include <wtf/Vector.h>
38
39 namespace JSC {
40
41 // Gives you a compressed map between between bytecode indices and machine code
42 // entry points. The compression simply tries to use either 1, 2, or 4 bytes for
43 // any given offset. The largest offset that can be stored is 2^30.
44
45 // Example use:
46 //
47 // CompactJITCodeMap::Encoder encoder(map);
48 // encoder.append(a, b);
49 // encoder.append(c, d); // preconditions: c >= a, d >= b
50 // OwnPtr<CompactJITCodeMap> map = encoder.finish();
51 //
52 // At some later time:
53 //
54 // Vector<BytecodeAndMachineOffset> decoded;
55 // map->decode(decoded);
56
57 struct BytecodeAndMachineOffset {
58     BytecodeAndMachineOffset() { }
59     
60     BytecodeAndMachineOffset(unsigned bytecodeIndex, unsigned machineCodeOffset)
61         : m_bytecodeIndex(bytecodeIndex)
62         , m_machineCodeOffset(machineCodeOffset)
63     {
64     }
65     
66     unsigned m_bytecodeIndex;
67     unsigned m_machineCodeOffset;
68     
69     static inline unsigned getBytecodeIndex(BytecodeAndMachineOffset* mapping)
70     {
71         return mapping->m_bytecodeIndex;
72     }
73     
74     static inline unsigned getMachineCodeOffset(BytecodeAndMachineOffset* mapping)
75     {
76         return mapping->m_machineCodeOffset;
77     }
78 };
79
80 class CompactJITCodeMap {
81     WTF_MAKE_FAST_ALLOCATED;
82 public:
83     ~CompactJITCodeMap()
84     {
85         if (m_buffer)
86             fastFree(m_buffer);
87     }
88     
89     unsigned numberOfEntries() const
90     {
91         return m_numberOfEntries;
92     }
93     
94     void decode(Vector<BytecodeAndMachineOffset>& result) const;
95     
96 private:
97     CompactJITCodeMap(uint8_t* buffer, unsigned size, unsigned numberOfEntries)
98         : m_buffer(buffer)
99 #if !ASSERT_DISABLED
100         , m_size(size)
101 #endif
102         , m_numberOfEntries(numberOfEntries)
103     {
104         UNUSED_PARAM(size);
105     }
106     
107     uint8_t at(unsigned index) const
108     {
109         ASSERT(index < m_size);
110         return m_buffer[index];
111     }
112     
113     unsigned decodeNumber(unsigned& index) const
114     {
115         uint8_t headValue = at(index++);
116         if (!(headValue & 128))
117             return headValue;
118         if (!(headValue & 64))
119             return (static_cast<unsigned>(headValue & ~128) << 8) | at(index++);
120         unsigned second = at(index++);
121         unsigned third  = at(index++);
122         unsigned fourth = at(index++);
123         return (static_cast<unsigned>(headValue & ~(128 + 64)) << 24) | (second << 16) | (third << 8) | fourth;
124     }
125     
126     uint8_t* m_buffer;
127 #if !ASSERT_DISABLED
128     unsigned m_size;
129 #endif
130     unsigned m_numberOfEntries;
131     
132 public:
133     class Encoder {
134         WTF_MAKE_NONCOPYABLE(Encoder);
135     public:
136         Encoder();
137         ~Encoder();
138         
139         void ensureCapacityFor(unsigned numberOfEntriesToAdd);
140         void append(unsigned bytecodeIndex, unsigned machineCodeOffset);
141         PassOwnPtr<CompactJITCodeMap> finish();
142         
143     private:
144         void appendByte(uint8_t value);
145         void encodeNumber(uint32_t value);
146     
147         uint8_t* m_buffer;
148         unsigned m_size;
149         unsigned m_capacity;
150         unsigned m_numberOfEntries;
151         
152         unsigned m_previousBytecodeIndex;
153         unsigned m_previousMachineCodeOffset;
154     };
155     
156     class Decoder {
157         WTF_MAKE_NONCOPYABLE(Decoder);
158     public:
159         Decoder(const CompactJITCodeMap*);
160         
161         unsigned numberOfEntriesRemaining() const;
162         void read(unsigned& bytecodeIndex, unsigned& machineCodeOffset);
163         
164     private:
165         const CompactJITCodeMap* m_jitCodeMap;
166         unsigned m_previousBytecodeIndex;
167         unsigned m_previousMachineCodeOffset;
168         unsigned m_numberOfEntriesRemaining;
169         unsigned m_bufferIndex;
170     };
171
172 private:
173     friend class Encoder;
174     friend class Decoder;
175 };
176
177 inline void CompactJITCodeMap::decode(Vector<BytecodeAndMachineOffset>& result) const
178 {
179     Decoder decoder(this);
180     result.resize(decoder.numberOfEntriesRemaining());
181     for (unsigned i = 0; i < result.size(); ++i)
182         decoder.read(result[i].m_bytecodeIndex, result[i].m_machineCodeOffset);
183     
184     ASSERT(!decoder.numberOfEntriesRemaining());
185 }
186
187 inline CompactJITCodeMap::Encoder::Encoder()
188     : m_buffer(0)
189     , m_size(0)
190     , m_capacity(0)
191     , m_numberOfEntries(0)
192     , m_previousBytecodeIndex(0)
193     , m_previousMachineCodeOffset(0)
194 {
195 }
196
197 inline CompactJITCodeMap::Encoder::~Encoder()
198 {
199     if (m_buffer)
200         fastFree(m_buffer);
201 }
202         
203 inline void CompactJITCodeMap::Encoder::append(unsigned bytecodeIndex, unsigned machineCodeOffset)
204 {
205     ASSERT(bytecodeIndex >= m_previousBytecodeIndex);
206     ASSERT(machineCodeOffset >= m_previousMachineCodeOffset);
207     ensureCapacityFor(1);
208     encodeNumber(bytecodeIndex - m_previousBytecodeIndex);
209     encodeNumber(machineCodeOffset - m_previousMachineCodeOffset);
210     m_previousBytecodeIndex = bytecodeIndex;
211     m_previousMachineCodeOffset = machineCodeOffset;
212     m_numberOfEntries++;
213 }
214
215 inline PassOwnPtr<CompactJITCodeMap> CompactJITCodeMap::Encoder::finish()
216 {
217     m_capacity = m_size;
218     m_buffer = static_cast<uint8_t*>(fastRealloc(m_buffer, m_capacity));
219     OwnPtr<CompactJITCodeMap> result = adoptPtr(new CompactJITCodeMap(m_buffer, m_size, m_numberOfEntries));
220     m_buffer = 0;
221     m_size = 0;
222     m_capacity = 0;
223     m_numberOfEntries = 0;
224     m_previousBytecodeIndex = 0;
225     m_previousMachineCodeOffset = 0;
226     return result.release();
227 }
228         
229 inline void CompactJITCodeMap::Encoder::appendByte(uint8_t value)
230 {
231     ASSERT(m_size + 1 <= m_capacity);
232     m_buffer[m_size++] = value;
233 }
234     
235 inline void CompactJITCodeMap::Encoder::encodeNumber(uint32_t value)
236 {
237     ASSERT(m_size + 4 <= m_capacity);
238     ASSERT(value < (1 << 30));
239     if (value <= 127) {
240         uint8_t headValue = static_cast<uint8_t>(value);
241         ASSERT(!(headValue & 128));
242         appendByte(headValue);
243     } else if (value <= 16383) {
244         uint8_t headValue = static_cast<uint8_t>(value >> 8);
245         ASSERT(!(headValue & 128));
246         ASSERT(!(headValue & 64));
247         appendByte(headValue | 128);
248         appendByte(static_cast<uint8_t>(value));
249     } else {
250         uint8_t headValue = static_cast<uint8_t>(value >> 24);
251         ASSERT(!(headValue & 128));
252         ASSERT(!(headValue & 64));
253         appendByte(headValue | 128 | 64);
254         appendByte(static_cast<uint8_t>(value >> 16));
255         appendByte(static_cast<uint8_t>(value >> 8));
256         appendByte(static_cast<uint8_t>(value));
257     }
258 }
259
260 inline void CompactJITCodeMap::Encoder::ensureCapacityFor(unsigned numberOfEntriesToAdd)
261 {
262     unsigned capacityNeeded = m_size + numberOfEntriesToAdd * 2 * 4;
263     if (capacityNeeded > m_capacity) {
264         m_capacity = capacityNeeded * 2;
265         m_buffer = static_cast<uint8_t*>(fastRealloc(m_buffer, m_capacity));
266     }
267 }
268
269 inline CompactJITCodeMap::Decoder::Decoder(const CompactJITCodeMap* jitCodeMap)
270     : m_jitCodeMap(jitCodeMap)
271     , m_previousBytecodeIndex(0)
272     , m_previousMachineCodeOffset(0)
273     , m_numberOfEntriesRemaining(jitCodeMap->m_numberOfEntries)
274     , m_bufferIndex(0)
275 {
276 }
277
278 inline unsigned CompactJITCodeMap::Decoder::numberOfEntriesRemaining() const
279 {
280     ASSERT(m_numberOfEntriesRemaining || m_bufferIndex == m_jitCodeMap->m_size);
281     return m_numberOfEntriesRemaining;
282 }
283
284 inline void CompactJITCodeMap::Decoder::read(unsigned& bytecodeIndex, unsigned& machineCodeOffset)
285 {
286     ASSERT(numberOfEntriesRemaining());
287     
288     m_previousBytecodeIndex += m_jitCodeMap->decodeNumber(m_bufferIndex);
289     m_previousMachineCodeOffset += m_jitCodeMap->decodeNumber(m_bufferIndex);
290     bytecodeIndex = m_previousBytecodeIndex;
291     machineCodeOffset = m_previousMachineCodeOffset;
292     m_numberOfEntriesRemaining--;
293 }
294
295 } // namespace JSC
296
297 #endif // CompactJITCodeMap_h