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
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 Computer, 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.
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.
29 #ifndef CompactJITCodeMap_h
30 #define CompactJITCodeMap_h
32 #include <wtf/Assertions.h>
33 #include <wtf/FastAllocBase.h>
34 #include <wtf/FastMalloc.h>
35 #include <wtf/OwnPtr.h>
36 #include <wtf/PassOwnPtr.h>
37 #include <wtf/UnusedParam.h>
38 #include <wtf/Vector.h>
42 // Gives you a compressed map between between bytecode indices and machine code
43 // entry points. The compression simply tries to use either 1, 2, or 4 bytes for
44 // any given offset. The largest offset that can be stored is 2^30.
48 // CompactJITCodeMap::Encoder encoder(map);
49 // encoder.append(a, b);
50 // encoder.append(c, d); // preconditions: c >= a, d >= b
51 // OwnPtr<CompactJITCodeMap> map = encoder.finish();
53 // At some later time:
55 // Vector<BytecodeAndMachineOffset> decoded;
56 // map->decode(decoded);
58 struct BytecodeAndMachineOffset {
59 BytecodeAndMachineOffset() { }
61 BytecodeAndMachineOffset(unsigned bytecodeIndex, unsigned machineCodeOffset)
62 : m_bytecodeIndex(bytecodeIndex)
63 , m_machineCodeOffset(machineCodeOffset)
67 unsigned m_bytecodeIndex;
68 unsigned m_machineCodeOffset;
70 static inline unsigned getBytecodeIndex(BytecodeAndMachineOffset* mapping)
72 return mapping->m_bytecodeIndex;
75 static inline unsigned getMachineCodeOffset(BytecodeAndMachineOffset* mapping)
77 return mapping->m_machineCodeOffset;
81 class CompactJITCodeMap {
82 WTF_MAKE_FAST_ALLOCATED;
90 unsigned numberOfEntries() const
92 return m_numberOfEntries;
95 void decode(Vector<BytecodeAndMachineOffset>& result) const;
98 CompactJITCodeMap(uint8_t* buffer, unsigned size, unsigned numberOfEntries)
103 , m_numberOfEntries(numberOfEntries)
108 uint8_t at(unsigned index) const
110 ASSERT(index < m_size);
111 return m_buffer[index];
114 unsigned decodeNumber(unsigned& index) const
116 uint8_t headValue = at(index++);
117 if (!(headValue & 128))
119 if (!(headValue & 64))
120 return (static_cast<unsigned>(headValue & ~128) << 8) | at(index++);
121 unsigned second = at(index++);
122 unsigned third = at(index++);
123 unsigned fourth = at(index++);
124 return (static_cast<unsigned>(headValue & ~(128 + 64)) << 24) | (second << 16) | (third << 8) | fourth;
131 unsigned m_numberOfEntries;
135 WTF_MAKE_NONCOPYABLE(Encoder);
140 void ensureCapacityFor(unsigned numberOfEntriesToAdd);
141 void append(unsigned bytecodeIndex, unsigned machineCodeOffset);
142 PassOwnPtr<CompactJITCodeMap> finish();
145 void appendByte(uint8_t value);
146 void encodeNumber(uint32_t value);
151 unsigned m_numberOfEntries;
153 unsigned m_previousBytecodeIndex;
154 unsigned m_previousMachineCodeOffset;
158 WTF_MAKE_NONCOPYABLE(Decoder);
160 Decoder(const CompactJITCodeMap*);
162 unsigned numberOfEntriesRemaining() const;
163 void read(unsigned& bytecodeIndex, unsigned& machineCodeOffset);
166 const CompactJITCodeMap* m_jitCodeMap;
167 unsigned m_previousBytecodeIndex;
168 unsigned m_previousMachineCodeOffset;
169 unsigned m_numberOfEntriesRemaining;
170 unsigned m_bufferIndex;
174 friend class Encoder;
175 friend class Decoder;
178 inline void CompactJITCodeMap::decode(Vector<BytecodeAndMachineOffset>& result) const
180 Decoder decoder(this);
181 result.resize(decoder.numberOfEntriesRemaining());
182 for (unsigned i = 0; i < result.size(); ++i)
183 decoder.read(result[i].m_bytecodeIndex, result[i].m_machineCodeOffset);
185 ASSERT(!decoder.numberOfEntriesRemaining());
188 inline CompactJITCodeMap::Encoder::Encoder()
192 , m_numberOfEntries(0)
193 , m_previousBytecodeIndex(0)
194 , m_previousMachineCodeOffset(0)
198 inline CompactJITCodeMap::Encoder::~Encoder()
204 inline void CompactJITCodeMap::Encoder::append(unsigned bytecodeIndex, unsigned machineCodeOffset)
206 ASSERT(bytecodeIndex >= m_previousBytecodeIndex);
207 ASSERT(machineCodeOffset >= m_previousMachineCodeOffset);
208 ensureCapacityFor(1);
209 encodeNumber(bytecodeIndex - m_previousBytecodeIndex);
210 encodeNumber(machineCodeOffset - m_previousMachineCodeOffset);
211 m_previousBytecodeIndex = bytecodeIndex;
212 m_previousMachineCodeOffset = machineCodeOffset;
216 inline PassOwnPtr<CompactJITCodeMap> CompactJITCodeMap::Encoder::finish()
219 m_buffer = static_cast<uint8_t*>(fastRealloc(m_buffer, m_capacity));
220 OwnPtr<CompactJITCodeMap> result = adoptPtr(new CompactJITCodeMap(m_buffer, m_size, m_numberOfEntries));
224 m_numberOfEntries = 0;
225 m_previousBytecodeIndex = 0;
226 m_previousMachineCodeOffset = 0;
227 return result.release();
230 inline void CompactJITCodeMap::Encoder::appendByte(uint8_t value)
232 ASSERT(m_size + 1 <= m_capacity);
233 m_buffer[m_size++] = value;
236 inline void CompactJITCodeMap::Encoder::encodeNumber(uint32_t value)
238 ASSERT(m_size + 4 <= m_capacity);
239 ASSERT(value < (1 << 30));
241 uint8_t headValue = static_cast<uint8_t>(value);
242 ASSERT(!(headValue & 128));
243 appendByte(headValue);
244 } else if (value <= 16383) {
245 uint8_t headValue = static_cast<uint8_t>(value >> 8);
246 ASSERT(!(headValue & 128));
247 ASSERT(!(headValue & 64));
248 appendByte(headValue | 128);
249 appendByte(static_cast<uint8_t>(value));
251 uint8_t headValue = static_cast<uint8_t>(value >> 24);
252 ASSERT(!(headValue & 128));
253 ASSERT(!(headValue & 64));
254 appendByte(headValue | 128 | 64);
255 appendByte(static_cast<uint8_t>(value >> 16));
256 appendByte(static_cast<uint8_t>(value >> 8));
257 appendByte(static_cast<uint8_t>(value));
261 inline void CompactJITCodeMap::Encoder::ensureCapacityFor(unsigned numberOfEntriesToAdd)
263 unsigned capacityNeeded = m_size + numberOfEntriesToAdd * 2 * 4;
264 if (capacityNeeded > m_capacity) {
265 m_capacity = capacityNeeded * 2;
266 m_buffer = static_cast<uint8_t*>(fastRealloc(m_buffer, m_capacity));
270 inline CompactJITCodeMap::Decoder::Decoder(const CompactJITCodeMap* jitCodeMap)
271 : m_jitCodeMap(jitCodeMap)
272 , m_previousBytecodeIndex(0)
273 , m_previousMachineCodeOffset(0)
274 , m_numberOfEntriesRemaining(jitCodeMap->m_numberOfEntries)
279 inline unsigned CompactJITCodeMap::Decoder::numberOfEntriesRemaining() const
281 ASSERT(m_numberOfEntriesRemaining || m_bufferIndex == m_jitCodeMap->m_size);
282 return m_numberOfEntriesRemaining;
285 inline void CompactJITCodeMap::Decoder::read(unsigned& bytecodeIndex, unsigned& machineCodeOffset)
287 ASSERT(numberOfEntriesRemaining());
289 m_previousBytecodeIndex += m_jitCodeMap->decodeNumber(m_bufferIndex);
290 m_previousMachineCodeOffset += m_jitCodeMap->decodeNumber(m_bufferIndex);
291 bytecodeIndex = m_previousBytecodeIndex;
292 machineCodeOffset = m_previousMachineCodeOffset;
293 m_numberOfEntriesRemaining--;
298 #endif // CompactJITCodeMap_h