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