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/Vector.h>
  36
  37 namespace JSC {
  38
  39 // Gives you a compressed map between between bytecode indices and machine code
  40 // entry points. The compression simply tries to use either 1, 2, or 4 bytes for
  41 // any given offset. The largest offset that can be stored is 2^30.
  42
  43 // Example use:
  44 //
  45 // CompactJITCodeMap::Encoder encoder(map);
  46 // encoder.append(a, b);
  47 // encoder.append(c, d); // preconditions: c >= a, d >= b
  48 // auto map = encoder.finish();
  49 //
  50 // At some later time:
  51 //
  52 // Vector<BytecodeAndMachineOffset> decoded;
  53 // map->decode(decoded);
  54
  55 struct BytecodeAndMachineOffset {
  56     BytecodeAndMachineOffset() { }
  57
  58     BytecodeAndMachineOffset(unsigned bytecodeIndex, unsigned machineCodeOffset)
  59         : m_bytecodeIndex(bytecodeIndex)
  60         , m_machineCodeOffset(machineCodeOffset)
  61     {
  62     }
  63
  64     unsigned m_bytecodeIndex;
  65     unsigned m_machineCodeOffset;
  66
  67     static inline unsigned getBytecodeIndex(BytecodeAndMachineOffset* mapping)
  68     {
  69         return mapping->m_bytecodeIndex;
  70     }
  71
  72     static inline unsigned getMachineCodeOffset(BytecodeAndMachineOffset* mapping)
  73     {
  74         return mapping->m_machineCodeOffset;
  75     }
  76 };
  77
  78 class CompactJITCodeMap {
  79     WTF_MAKE_FAST_ALLOCATED;
  80 public:
  81     CompactJITCodeMap(uint8_t* buffer, unsigned size, unsigned numberOfEntries)
  82         : m_buffer(buffer)
  83 #if !ASSERT_DISABLED
  84         , m_size(size)
  85 #endif
  86         , m_numberOfEntries(numberOfEntries)
  87     {
  88         UNUSED_PARAM(size);
  89     }
  90
  91     ~CompactJITCodeMap()
  92     {
  93         if (m_buffer)
  94             fastFree(m_buffer);
  95     }
  96
  97     unsigned numberOfEntries() const
  98     {
  99         return m_numberOfEntries;
 100     }
 101
 102     void decode(Vector<BytecodeAndMachineOffset>& result) const;
 103
 104 private:
 105     uint8_t at(unsigned index) const
 106     {
 107         ASSERT(index < m_size);
 108         return m_buffer[index];
 109     }
 110
 111     unsigned decodeNumber(unsigned& index) const
 112     {
 113         uint8_t headValue = at(index++);
 114         if (!(headValue & 128))
 115             return headValue;
 116         if (!(headValue & 64))
 117             return (static_cast<unsigned>(headValue & ~128) << 8) | at(index++);
 118         unsigned second = at(index++);
 119         unsigned third  = at(index++);
 120         unsigned fourth = at(index++);
 121         return (static_cast<unsigned>(headValue & ~(128 + 64)) << 24) | (second << 16) | (third << 8) | fourth;
 122     }
 123
 124     uint8_t* m_buffer;
 125 #if !ASSERT_DISABLED
 126     unsigned m_size;
 127 #endif
 128     unsigned m_numberOfEntries;
 129
 130 public:
 131     class Encoder {
 132         WTF_MAKE_NONCOPYABLE(Encoder);
 133     public:
 134         Encoder();
 135         ~Encoder();
 136
 137         void ensureCapacityFor(unsigned numberOfEntriesToAdd);
 138         void append(unsigned bytecodeIndex, unsigned machineCodeOffset);
 139         std::unique_ptr<CompactJITCodeMap> finish();
 140
 141     private:
 142         void appendByte(uint8_t value);
 143         void encodeNumber(uint32_t value);
 144
 145         uint8_t* m_buffer;
 146         unsigned m_size;
 147         unsigned m_capacity;
 148         unsigned m_numberOfEntries;
 149
 150         unsigned m_previousBytecodeIndex;
 151         unsigned m_previousMachineCodeOffset;
 152     };
 153
 154     class Decoder {
 155         WTF_MAKE_NONCOPYABLE(Decoder);
 156     public:
 157         Decoder(const CompactJITCodeMap*);
 158
 159         unsigned numberOfEntriesRemaining() const;
 160         void read(unsigned& bytecodeIndex, unsigned& machineCodeOffset);
 161
 162     private:
 163         const CompactJITCodeMap* m_jitCodeMap;
 164         unsigned m_previousBytecodeIndex;
 165         unsigned m_previousMachineCodeOffset;
 166         unsigned m_numberOfEntriesRemaining;
 167         unsigned m_bufferIndex;
 168     };
 169
 170 private:
 171     friend class Encoder;
 172     friend class Decoder;
 173 };
 174
 175 inline void CompactJITCodeMap::decode(Vector<BytecodeAndMachineOffset>& result) const
 176 {
 177     Decoder decoder(this);
 178     result.resize(decoder.numberOfEntriesRemaining());
 179     for (unsigned i = 0; i < result.size(); ++i)
 180         decoder.read(result[i].m_bytecodeIndex, result[i].m_machineCodeOffset);
 181
 182     ASSERT(!decoder.numberOfEntriesRemaining());
 183 }
 184
 185 inline CompactJITCodeMap::Encoder::Encoder()
 186     : m_buffer(0)
 187     , m_size(0)
 188     , m_capacity(0)
 189     , m_numberOfEntries(0)
 190     , m_previousBytecodeIndex(0)
 191     , m_previousMachineCodeOffset(0)
 192 {
 193 }
 194
 195 inline CompactJITCodeMap::Encoder::~Encoder()
 196 {
 197     if (m_buffer)
 198         fastFree(m_buffer);
 199 }
 200
 201 inline void CompactJITCodeMap::Encoder::append(unsigned bytecodeIndex, unsigned machineCodeOffset)
 202 {
 203     ASSERT(bytecodeIndex >= m_previousBytecodeIndex);
 204     ASSERT(machineCodeOffset >= m_previousMachineCodeOffset);
 205     ensureCapacityFor(1);
 206     encodeNumber(bytecodeIndex - m_previousBytecodeIndex);
 207     encodeNumber(machineCodeOffset - m_previousMachineCodeOffset);
 208     m_previousBytecodeIndex = bytecodeIndex;
 209     m_previousMachineCodeOffset = machineCodeOffset;
 210     m_numberOfEntries++;
 211 }
 212
 213 inline std::unique_ptr<CompactJITCodeMap> CompactJITCodeMap::Encoder::finish()
 214 {
 215     m_capacity = m_size;
 216     m_buffer = static_cast<uint8_t*>(fastRealloc(m_buffer, m_capacity));
 217     auto result = std::make_unique<CompactJITCodeMap>(m_buffer, m_size, m_numberOfEntries);
 218     m_buffer = 0;
 219     m_size = 0;
 220     m_capacity = 0;
 221     m_numberOfEntries = 0;
 222     m_previousBytecodeIndex = 0;
 223     m_previousMachineCodeOffset = 0;
 224     return result;
 225 }
 226
 227 inline void CompactJITCodeMap::Encoder::appendByte(uint8_t value)
 228 {
 229     ASSERT(m_size + 1 <= m_capacity);
 230     m_buffer[m_size++] = value;
 231 }
 232
 233 inline void CompactJITCodeMap::Encoder::encodeNumber(uint32_t value)
 234 {
 235     ASSERT(m_size + 4 <= m_capacity);
 236     ASSERT(value < (1 << 30));
 237     if (value <= 127) {
 238         uint8_t headValue = static_cast<uint8_t>(value);
 239         ASSERT(!(headValue & 128));
 240         appendByte(headValue);
 241     } else if (value <= 16383) {
 242         uint8_t headValue = static_cast<uint8_t>(value >> 8);
 243         ASSERT(!(headValue & 128));
 244         ASSERT(!(headValue & 64));
 245         appendByte(headValue | 128);
 246         appendByte(static_cast<uint8_t>(value));
 247     } else {
 248         uint8_t headValue = static_cast<uint8_t>(value >> 24);
 249         ASSERT(!(headValue & 128));
 250         ASSERT(!(headValue & 64));
 251         appendByte(headValue | 128 | 64);
 252         appendByte(static_cast<uint8_t>(value >> 16));
 253         appendByte(static_cast<uint8_t>(value >> 8));
 254         appendByte(static_cast<uint8_t>(value));
 255     }
 256 }
 257
 258 inline void CompactJITCodeMap::Encoder::ensureCapacityFor(unsigned numberOfEntriesToAdd)
 259 {
 260     unsigned capacityNeeded = m_size + numberOfEntriesToAdd * 2 * 4;
 261     if (capacityNeeded > m_capacity) {
 262         m_capacity = capacityNeeded * 2;
 263         m_buffer = static_cast<uint8_t*>(fastRealloc(m_buffer, m_capacity));
 264     }
 265 }
 266
 267 inline CompactJITCodeMap::Decoder::Decoder(const CompactJITCodeMap* jitCodeMap)
 268     : m_jitCodeMap(jitCodeMap)
 269     , m_previousBytecodeIndex(0)
 270     , m_previousMachineCodeOffset(0)
 271     , m_numberOfEntriesRemaining(jitCodeMap->m_numberOfEntries)
 272     , m_bufferIndex(0)
 273 {
 274 }
 275
 276 inline unsigned CompactJITCodeMap::Decoder::numberOfEntriesRemaining() const
 277 {
 278     ASSERT(m_numberOfEntriesRemaining || m_bufferIndex == m_jitCodeMap->m_size);
 279     return m_numberOfEntriesRemaining;
 280 }
 281
 282 inline void CompactJITCodeMap::Decoder::read(unsigned& bytecodeIndex, unsigned& machineCodeOffset)
 283 {
 284     ASSERT(numberOfEntriesRemaining());
 285
 286     m_previousBytecodeIndex += m_jitCodeMap->decodeNumber(m_bufferIndex);
 287     m_previousMachineCodeOffset += m_jitCodeMap->decodeNumber(m_bufferIndex);
 288     bytecodeIndex = m_previousBytecodeIndex;
 289     machineCodeOffset = m_previousMachineCodeOffset;
 290     m_numberOfEntriesRemaining--;
 291 }
 292
 293 } // namespace JSC
 294
 295 #endif // CompactJITCodeMap_h