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 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.
  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/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>
  39
  40 namespace JSC {
  41
  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.
  45
  46 // Example use:
  47 //
  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();
  52 //
  53 // At some later time:
  54 //
  55 // Vector<BytecodeAndMachineOffset> decoded;
  56 // map->decode(decoded);
  57
  58 struct BytecodeAndMachineOffset {
  59     BytecodeAndMachineOffset() { }
  60
  61     BytecodeAndMachineOffset(unsigned bytecodeIndex, unsigned machineCodeOffset)
  62         : m_bytecodeIndex(bytecodeIndex)
  63         , m_machineCodeOffset(machineCodeOffset)
  64     {
  65     }
  66
  67     unsigned m_bytecodeIndex;
  68     unsigned m_machineCodeOffset;
  69
  70     static inline unsigned getBytecodeIndex(BytecodeAndMachineOffset* mapping)
  71     {
  72         return mapping->m_bytecodeIndex;
  73     }
  74
  75     static inline unsigned getMachineCodeOffset(BytecodeAndMachineOffset* mapping)
  76     {
  77         return mapping->m_machineCodeOffset;
  78     }
  79 };
  80
  81 class CompactJITCodeMap {
  82     WTF_MAKE_FAST_ALLOCATED;
  83 public:
  84     ~CompactJITCodeMap()
  85     {
  86         if (m_buffer)
  87             fastFree(m_buffer);
  88     }
  89
  90     unsigned numberOfEntries() const
  91     {
  92         return m_numberOfEntries;
  93     }
  94
  95     void decode(Vector<BytecodeAndMachineOffset>& result) const;
  96
  97 private:
  98     CompactJITCodeMap(uint8_t* buffer, unsigned size, unsigned numberOfEntries)
  99         : m_buffer(buffer)
 100 #if !ASSERT_DISABLED
 101         , m_size(size)
 102 #endif
 103         , m_numberOfEntries(numberOfEntries)
 104     {
 105         UNUSED_PARAM(size);
 106     }
 107
 108     uint8_t at(unsigned index) const
 109     {
 110         ASSERT(index < m_size);
 111         return m_buffer[index];
 112     }
 113
 114     unsigned decodeNumber(unsigned& index) const
 115     {
 116         uint8_t headValue = at(index++);
 117         if (!(headValue & 128))
 118             return headValue;
 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;
 125     }
 126
 127     uint8_t* m_buffer;
 128 #if !ASSERT_DISABLED
 129     unsigned m_size;
 130 #endif
 131     unsigned m_numberOfEntries;
 132
 133 public:
 134     class Encoder {
 135         WTF_MAKE_NONCOPYABLE(Encoder);
 136     public:
 137         Encoder();
 138         ~Encoder();
 139
 140         void ensureCapacityFor(unsigned numberOfEntriesToAdd);
 141         void append(unsigned bytecodeIndex, unsigned machineCodeOffset);
 142         PassOwnPtr<CompactJITCodeMap> finish();
 143
 144     private:
 145         void appendByte(uint8_t value);
 146         void encodeNumber(uint32_t value);
 147
 148         uint8_t* m_buffer;
 149         unsigned m_size;
 150         unsigned m_capacity;
 151         unsigned m_numberOfEntries;
 152
 153         unsigned m_previousBytecodeIndex;
 154         unsigned m_previousMachineCodeOffset;
 155     };
 156
 157     class Decoder {
 158         WTF_MAKE_NONCOPYABLE(Decoder);
 159     public:
 160         Decoder(const CompactJITCodeMap*);
 161
 162         unsigned numberOfEntriesRemaining() const;
 163         void read(unsigned& bytecodeIndex, unsigned& machineCodeOffset);
 164
 165     private:
 166         const CompactJITCodeMap* m_jitCodeMap;
 167         unsigned m_previousBytecodeIndex;
 168         unsigned m_previousMachineCodeOffset;
 169         unsigned m_numberOfEntriesRemaining;
 170         unsigned m_bufferIndex;
 171     };
 172
 173 private:
 174     friend class Encoder;
 175     friend class Decoder;
 176 };
 177
 178 inline void CompactJITCodeMap::decode(Vector<BytecodeAndMachineOffset>& result) const
 179 {
 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);
 184
 185     ASSERT(!decoder.numberOfEntriesRemaining());
 186 }
 187
 188 inline CompactJITCodeMap::Encoder::Encoder()
 189     : m_buffer(0)
 190     , m_size(0)
 191     , m_capacity(0)
 192     , m_numberOfEntries(0)
 193     , m_previousBytecodeIndex(0)
 194     , m_previousMachineCodeOffset(0)
 195 {
 196 }
 197
 198 inline CompactJITCodeMap::Encoder::~Encoder()
 199 {
 200     if (m_buffer)
 201         fastFree(m_buffer);
 202 }
 203
 204 inline void CompactJITCodeMap::Encoder::append(unsigned bytecodeIndex, unsigned machineCodeOffset)
 205 {
 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;
 213     m_numberOfEntries++;
 214 }
 215
 216 inline PassOwnPtr<CompactJITCodeMap> CompactJITCodeMap::Encoder::finish()
 217 {
 218     m_capacity = m_size;
 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));
 221     m_buffer = 0;
 222     m_size = 0;
 223     m_capacity = 0;
 224     m_numberOfEntries = 0;
 225     m_previousBytecodeIndex = 0;
 226     m_previousMachineCodeOffset = 0;
 227     return result.release();
 228 }
 229
 230 inline void CompactJITCodeMap::Encoder::appendByte(uint8_t value)
 231 {
 232     ASSERT(m_size + 1 <= m_capacity);
 233     m_buffer[m_size++] = value;
 234 }
 235
 236 inline void CompactJITCodeMap::Encoder::encodeNumber(uint32_t value)
 237 {
 238     ASSERT(m_size + 4 <= m_capacity);
 239     ASSERT(value < (1 << 30));
 240     if (value <= 127) {
 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));
 250     } else {
 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));
 258     }
 259 }
 260
 261 inline void CompactJITCodeMap::Encoder::ensureCapacityFor(unsigned numberOfEntriesToAdd)
 262 {
 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));
 267     }
 268 }
 269
 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)
 275     , m_bufferIndex(0)
 276 {
 277 }
 278
 279 inline unsigned CompactJITCodeMap::Decoder::numberOfEntriesRemaining() const
 280 {
 281     ASSERT(m_numberOfEntriesRemaining || m_bufferIndex == m_jitCodeMap->m_size);
 282     return m_numberOfEntriesRemaining;
 283 }
 284
 285 inline void CompactJITCodeMap::Decoder::read(unsigned& bytecodeIndex, unsigned& machineCodeOffset)
 286 {
 287     ASSERT(numberOfEntriesRemaining());
 288
 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--;
 294 }
 295
 296 } // namespace JSC
 297
 298 #endif // CompactJITCodeMap_h