Bug 962555 part 5 - IonMonkey: Move the RValueAllocation into an indexed buffer. r=h4writer
authorNicolas B. Pierron <nicolas.b.pierron@mozilla.com>
Tue, 18 Mar 2014 08:31:24 -0700
changeset 193712 69bc4df5ede5cc53ae5a4bcc8ffeac8b0dd3e616
parent 193711 20268ebc09583530e28b80b21bca9b6eb8907df7
child 193713 a883534432517e6bdcc105d4be86fcfb2b7a04c0
push id486
push userasasaki@mozilla.com
push dateMon, 14 Jul 2014 18:39:42 +0000
treeherdermozilla-release@d33428174ff1 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersh4writer
bugs962555
milestone31.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 962555 part 5 - IonMonkey: Move the RValueAllocation into an indexed buffer. r=h4writer
js/src/jit/Bailouts.cpp
js/src/jit/BaselineBailouts.cpp
js/src/jit/CodeGenerator.cpp
js/src/jit/CompactBuffer.h
js/src/jit/Ion.cpp
js/src/jit/IonCode.h
js/src/jit/IonFrames.cpp
js/src/jit/Snapshots.cpp
js/src/jit/Snapshots.h
js/src/jsapi-tests/testJitRValueAlloc.cpp
--- a/js/src/jit/Bailouts.cpp
+++ b/js/src/jit/Bailouts.cpp
@@ -32,18 +32,20 @@ using namespace js::jit;
 //
 // Currently, such cases should not happen because our only use case of the
 // IonFrameIterator within InlineFrameIterator is to read the frame content, or
 // to clone it to find the parent scripted frame.  Both use cases are fine and
 // should not cause any issue since the only potential issue is to read the
 // bailed out frame.
 
 SnapshotIterator::SnapshotIterator(const IonBailoutIterator &iter)
-  : SnapshotReader(iter.ionScript()->snapshots() + iter.snapshotOffset(),
-                   iter.ionScript()->snapshots() + iter.ionScript()->snapshotsSize()),
+  : SnapshotReader(iter.ionScript()->snapshots(),
+                   iter.snapshotOffset(),
+                   iter.ionScript()->snapshotsRVATableSize(),
+                   iter.ionScript()->snapshotsListSize()),
     fp_(iter.jsFrame()),
     machine_(iter.machineState()),
     ionScript_(iter.ionScript())
 {
 }
 
 void
 IonBailoutIterator::dump() const
--- a/js/src/jit/BaselineBailouts.cpp
+++ b/js/src/jit/BaselineBailouts.cpp
@@ -1270,17 +1270,17 @@ jit::BailoutIonToBaseline(JSContext *cx,
     IonSpew(IonSpew_BaselineBailouts, "Bailing to baseline %s:%u (IonScript=%p) (FrameType=%d)",
             iter.script()->filename(), iter.script()->lineno(), (void *) iter.ionScript(),
             (int) prevFrameType);
 
     if (excInfo)
         IonSpew(IonSpew_BaselineBailouts, "Resuming in catch or finally block");
 
     IonSpew(IonSpew_BaselineBailouts, "  Reading from snapshot offset %u size %u",
-            iter.snapshotOffset(), iter.ionScript()->snapshotsSize());
+            iter.snapshotOffset(), iter.ionScript()->snapshotsListSize());
 
     if (!excInfo)
         iter.ionScript()->incNumBailouts();
     iter.script()->updateBaselineOrIonRaw();
 
     // Allocate buffer to hold stack replacement data.
     BaselineStackBuilder builder(iter, 1024);
     if (!builder.init())
--- a/js/src/jit/CodeGenerator.cpp
+++ b/js/src/jit/CodeGenerator.cpp
@@ -6068,33 +6068,37 @@ CodeGenerator::generateAsmJS()
     // The only remaining work needed to compile this function is to patch the
     // switch-statement jump tables (the entries of the table need the absolute
     // address of the cases). These table entries are accmulated as CodeLabels
     // in the MacroAssembler's codeLabels_ list and processed all at once at in
     // the "static-link" phase of module compilation. It is critical that there
     // is nothing else to do after this point since the LifoAlloc memory
     // holding the MIR graph is about to be popped and reused. In particular,
     // every step in CodeGenerator::link must be a nop, as asserted here:
-    JS_ASSERT(snapshots_.size() == 0);
+    JS_ASSERT(snapshots_.listSize() == 0);
+    JS_ASSERT(snapshots_.RVATableSize() == 0);
     JS_ASSERT(bailouts_.empty());
     JS_ASSERT(graph.numConstants() == 0);
     JS_ASSERT(safepointIndices_.empty());
     JS_ASSERT(osiIndices_.empty());
     JS_ASSERT(cacheList_.empty());
     JS_ASSERT(safepoints_.size() == 0);
     return true;
 }
 
 bool
 CodeGenerator::generate()
 {
     IonSpew(IonSpew_Codegen, "# Emitting code for script %s:%d",
             gen->info().script()->filename(),
             gen->info().script()->lineno());
 
+    if (!snapshots_.init())
+        return false;
+
     if (!safepoints_.init(gen->alloc(), graph.totalSlotCount()))
         return false;
 
 #if JS_TRACE_LOGGING
     masm.tracelogStart(gen->info().script());
     masm.tracelogLog(TraceLogging::INFO_ENGINE_IONMONKEY);
 #endif
 
@@ -6187,17 +6191,18 @@ CodeGenerator::link(JSContext *cx, types
     // List of possible scripts that this graph may call. Currently this is
     // only tracked when compiling for parallel execution.
     CallTargetVector callTargets(alloc());
     if (executionMode == ParallelExecution)
         AddPossibleCallees(cx, graph.mir(), callTargets);
 
     IonScript *ionScript =
       IonScript::New(cx, recompileInfo,
-                     graph.totalSlotCount(), scriptFrameSize, snapshots_.size(),
+                     graph.totalSlotCount(), scriptFrameSize,
+                     snapshots_.listSize(), snapshots_.RVATableSize(),
                      bailouts_.length(), graph.numConstants(),
                      safepointIndices_.length(), osiIndices_.length(),
                      cacheList_.length(), runtimeData_.length(),
                      safepoints_.size(), callTargets.length(),
                      patchableBackedges_.length(), optimizationLevel);
     if (!ionScript) {
         recompileInfo.compilerOutput(cx->zone()->types)->invalidate();
         return false;
@@ -6296,17 +6301,17 @@ CodeGenerator::link(JSContext *cx, types
     if (safepoints_.size())
         ionScript->copySafepoints(&safepoints_);
 
     // for reconvering from an Ion Frame.
     if (bailouts_.length())
         ionScript->copyBailoutTable(&bailouts_[0]);
     if (osiIndices_.length())
         ionScript->copyOsiIndices(&osiIndices_[0], masm);
-    if (snapshots_.size())
+    if (snapshots_.listSize())
         ionScript->copySnapshots(&snapshots_);
     if (graph.numConstants())
         ionScript->copyConstants(graph.constantPool());
     if (callTargets.length() > 0)
         ionScript->copyCallTargetEntries(callTargets.begin());
     if (patchableBackedges_.length() > 0)
         ionScript->copyPatchableBackedges(cx, code, patchableBackedges_.begin());
 
--- a/js/src/jit/CompactBuffer.h
+++ b/js/src/jit/CompactBuffer.h
@@ -82,16 +82,22 @@ class CompactBufferReader
             return -result;
         return result;
     }
 
     bool more() const {
         JS_ASSERT(buffer_ <= end_);
         return buffer_ < end_;
     }
+
+    void seek(const uint8_t *start, uint32_t offset) {
+        buffer_ = start + offset;
+        MOZ_ASSERT(start < end_);
+        MOZ_ASSERT(buffer_ < end_);
+    }
 };
 
 class CompactBufferWriter
 {
     js::Vector<uint8_t, 32, SystemAllocPolicy> buffer_;
     bool enoughMemory_;
 
   public:
--- a/js/src/jit/Ion.cpp
+++ b/js/src/jit/Ion.cpp
@@ -742,51 +742,53 @@ IonScript::IonScript()
     safepointsSize_(0),
     frameSlots_(0),
     frameSize_(0),
     bailoutTable_(0),
     bailoutEntries_(0),
     osiIndexOffset_(0),
     osiIndexEntries_(0),
     snapshots_(0),
-    snapshotsSize_(0),
+    snapshotsListSize_(0),
+    snapshotsRVATableSize_(0),
     constantTable_(0),
     constantEntries_(0),
     callTargetList_(0),
     callTargetEntries_(0),
     backedgeList_(0),
     backedgeEntries_(0),
     refcount_(0),
     recompileInfo_(),
     osrPcMismatchCounter_(0),
     dependentAsmJSModules(nullptr)
 {
 }
 
 IonScript *
 IonScript::New(JSContext *cx, types::RecompileInfo recompileInfo,
-               uint32_t frameSlots, uint32_t frameSize, size_t snapshotsSize,
+               uint32_t frameSlots, uint32_t frameSize,
+               size_t snapshotsListSize, size_t snapshotsRVATableSize,
                size_t bailoutEntries, size_t constants, size_t safepointIndices,
                size_t osiIndices, size_t cacheEntries, size_t runtimeSize,
                size_t safepointsSize, size_t callTargetEntries, size_t backedgeEntries,
                OptimizationLevel optimizationLevel)
 {
     static const int DataAlignment = sizeof(void *);
 
-    if (snapshotsSize >= MAX_BUFFER_SIZE ||
+    if (snapshotsListSize >= MAX_BUFFER_SIZE ||
         (bailoutEntries >= MAX_BUFFER_SIZE / sizeof(uint32_t)))
     {
         js_ReportOutOfMemory(cx);
         return nullptr;
     }
 
     // This should not overflow on x86, because the memory is already allocated
     // *somewhere* and if their total overflowed there would be no memory left
     // at all.
-    size_t paddedSnapshotsSize = AlignBytes(snapshotsSize, DataAlignment);
+    size_t paddedSnapshotsSize = AlignBytes(snapshotsListSize + snapshotsRVATableSize, DataAlignment);
     size_t paddedBailoutSize = AlignBytes(bailoutEntries * sizeof(uint32_t), DataAlignment);
     size_t paddedConstantsSize = AlignBytes(constants * sizeof(Value), DataAlignment);
     size_t paddedSafepointIndicesSize = AlignBytes(safepointIndices * sizeof(SafepointIndex), DataAlignment);
     size_t paddedOsiIndicesSize = AlignBytes(osiIndices * sizeof(OsiIndex), DataAlignment);
     size_t paddedCacheEntriesSize = AlignBytes(cacheEntries * sizeof(uint32_t), DataAlignment);
     size_t paddedRuntimeSize = AlignBytes(runtimeSize, DataAlignment);
     size_t paddedSafepointSize = AlignBytes(safepointsSize, DataAlignment);
     size_t paddedCallTargetSize = AlignBytes(callTargetEntries * sizeof(JSScript *), DataAlignment);
@@ -830,17 +832,18 @@ IonScript::New(JSContext *cx, types::Rec
     script->bailoutEntries_ = bailoutEntries;
     offsetCursor += paddedBailoutSize;
 
     script->osiIndexOffset_ = offsetCursor;
     script->osiIndexEntries_ = osiIndices;
     offsetCursor += paddedOsiIndicesSize;
 
     script->snapshots_ = offsetCursor;
-    script->snapshotsSize_ = snapshotsSize;
+    script->snapshotsListSize_ = snapshotsListSize;
+    script->snapshotsRVATableSize_ = snapshotsRVATableSize;
     offsetCursor += paddedSnapshotsSize;
 
     script->constantTable_ = offsetCursor;
     script->constantEntries_ = constants;
     offsetCursor += paddedConstantsSize;
 
     script->callTargetList_ = offsetCursor;
     script->callTargetEntries_ = callTargetEntries;
@@ -884,18 +887,24 @@ IonScript::writeBarrierPre(Zone *zone, I
     if (zone->needsBarrier())
         ionScript->trace(zone->barrierTracer());
 #endif
 }
 
 void
 IonScript::copySnapshots(const SnapshotWriter *writer)
 {
-    JS_ASSERT(writer->size() == snapshotsSize_);
-    memcpy((uint8_t *)this + snapshots_, writer->buffer(), snapshotsSize_);
+    MOZ_ASSERT(writer->listSize() == snapshotsListSize_);
+    memcpy((uint8_t *)this + snapshots_,
+           writer->listBuffer(), snapshotsListSize_);
+
+    MOZ_ASSERT(snapshotsRVATableSize_);
+    MOZ_ASSERT(writer->RVATableSize() == snapshotsRVATableSize_);
+    memcpy((uint8_t *)this + snapshots_ + snapshotsListSize_,
+           writer->RVATableBuffer(), snapshotsRVATableSize_);
 }
 
 void
 IonScript::copySafepoints(const SafepointWriter *writer)
 {
     JS_ASSERT(writer->size() == safepointsSize_);
     memcpy((uint8_t *)this + safepointsStart_, writer->buffer(), safepointsSize_);
 }
--- a/js/src/jit/IonCode.h
+++ b/js/src/jit/IonCode.h
@@ -237,17 +237,18 @@ struct IonScript
     uint32_t bailoutEntries_;
 
     // Map OSI-point displacement to snapshot.
     uint32_t osiIndexOffset_;
     uint32_t osiIndexEntries_;
 
     // Offset from the start of the code buffer to its snapshot buffer.
     uint32_t snapshots_;
-    uint32_t snapshotsSize_;
+    uint32_t snapshotsListSize_;
+    uint32_t snapshotsRVATableSize_;
 
     // Constant table for constants stored in snapshots.
     uint32_t constantTable_;
     uint32_t constantEntries_;
 
     // List of scripts that we call.
     //
     // Currently this is only non-nullptr for parallel IonScripts.
@@ -332,18 +333,19 @@ struct IonScript
     void trace(JSTracer *trc);
 
   public:
     // Do not call directly, use IonScript::New. This is public for cx->new_.
     IonScript();
 
     static IonScript *New(JSContext *cx, types::RecompileInfo recompileInfo,
                           uint32_t frameLocals, uint32_t frameSize,
-                          size_t snapshotsSize, size_t snapshotEntries,
-                          size_t constants, size_t safepointIndexEntries, size_t osiIndexEntries,
+                          size_t snapshotsListSize, size_t snapshotsRVATableSize,
+                          size_t bailoutEntries, size_t constants,
+                          size_t safepointIndexEntries, size_t osiIndexEntries,
                           size_t cacheEntries, size_t runtimeSize, size_t safepointsSize,
                           size_t callTargetEntries, size_t backedgeEntries,
                           OptimizationLevel optimizationLevel);
     static void Trace(JSTracer *trc, IonScript *script);
     static void Destroy(FreeOp *fop, IonScript *script);
 
     static inline size_t offsetOfMethod() {
         return offsetof(IonScript, method_);
@@ -441,18 +443,21 @@ struct IonScript
         hasSPSInstrumentation_ = false;
     }
     bool hasSPSInstrumentation() const {
         return hasSPSInstrumentation_;
     }
     const uint8_t *snapshots() const {
         return reinterpret_cast<const uint8_t *>(this) + snapshots_;
     }
-    size_t snapshotsSize() const {
-        return snapshotsSize_;
+    size_t snapshotsListSize() const {
+        return snapshotsListSize_;
+    }
+    size_t snapshotsRVATableSize() const {
+        return snapshotsRVATableSize_;
     }
     const uint8_t *safepoints() const {
         return reinterpret_cast<const uint8_t *>(this) + safepointsStart_;
     }
     size_t safepointsSize() const {
         return safepointsSize_;
     }
     size_t callTargetEntries() const {
--- a/js/src/jit/IonFrames.cpp
+++ b/js/src/jit/IonFrames.cpp
@@ -1288,36 +1288,40 @@ OsiIndex::returnPointDisplacement() cons
     // In general, pointer arithmetic on code is bad, but in this case,
     // getting the return address from a call instruction, stepping over pools
     // would be wrong.
     return callPointDisplacement_ + Assembler::patchWrite_NearCallSize();
 }
 
 SnapshotIterator::SnapshotIterator(IonScript *ionScript, SnapshotOffset snapshotOffset,
                                    IonJSFrameLayout *fp, const MachineState &machine)
-  : SnapshotReader(ionScript->snapshots() + snapshotOffset,
-                   ionScript->snapshots() + ionScript->snapshotsSize()),
+  : SnapshotReader(ionScript->snapshots(),
+                   snapshotOffset,
+                   ionScript->snapshotsRVATableSize(),
+                   ionScript->snapshotsListSize()),
     fp_(fp),
     machine_(machine),
     ionScript_(ionScript)
 {
-    JS_ASSERT(snapshotOffset < ionScript->snapshotsSize());
+    JS_ASSERT(snapshotOffset < ionScript->snapshotsListSize());
 }
 
 SnapshotIterator::SnapshotIterator(const IonFrameIterator &iter)
-  : SnapshotReader(iter.ionScript()->snapshots() + iter.osiIndex()->snapshotOffset(),
-                   iter.ionScript()->snapshots() + iter.ionScript()->snapshotsSize()),
+  : SnapshotReader(iter.ionScript()->snapshots(),
+                   iter.osiIndex()->snapshotOffset(),
+                   iter.ionScript()->snapshotsRVATableSize(),
+                   iter.ionScript()->snapshotsListSize()),
     fp_(iter.jsFrame()),
     machine_(iter.machineState()),
     ionScript_(iter.ionScript())
 {
 }
 
 SnapshotIterator::SnapshotIterator()
-  : SnapshotReader(nullptr, nullptr),
+  : SnapshotReader(nullptr, 0, 0, 0),
     fp_(nullptr),
     ionScript_(nullptr)
 {
 }
 
 bool
 SnapshotIterator::hasRegister(const Location &loc)
 {
--- a/js/src/jit/Snapshots.cpp
+++ b/js/src/jit/Snapshots.cpp
@@ -309,16 +309,35 @@ RValueAllocation::write(CompactBufferWri
       }
       case INVALID: {
         MOZ_ASSUME_UNREACHABLE("not initialized");
         break;
       }
     }
 }
 
+HashNumber
+RValueAllocation::hash() const {
+    CompactBufferWriter writer;
+    write(writer);
+
+    // We should never oom because the compact buffer writer has 32 inlined
+    // bytes, and in the worse case scenario, only encode 11 bytes (= header
+    // + signed + signed).
+    MOZ_ASSERT(!writer.oom());
+    MOZ_ASSERT(writer.length() <= 11);
+
+    HashNumber res = 0;
+    for (size_t i = 0; i < writer.length(); i++) {
+        res = ((res << 8) | (res >> (sizeof(res) - 1)));
+        res ^= writer.buffer()[i];
+    }
+    return res;
+}
+
 void
 Location::dump(FILE *fp) const
 {
     if (isStackOffset())
         fprintf(fp, "stack %d", stackOffset());
     else
         fprintf(fp, "reg %s", reg().name());
 }
@@ -406,23 +425,26 @@ RValueAllocation::dump(FILE *fp) const
         break;
 
       case INVALID:
         fprintf(fp, "invalid");
         break;
     }
 }
 
-SnapshotReader::SnapshotReader(const uint8_t *buffer, const uint8_t *end)
-  : reader_(buffer, end),
+SnapshotReader::SnapshotReader(const uint8_t *snapshots, uint32_t offset,
+                               uint32_t RVATableSize, uint32_t listSize)
+  : reader_(snapshots + offset, snapshots + listSize),
+    allocReader_(snapshots + listSize, snapshots + listSize + RVATableSize),
+    allocTable_(snapshots + listSize),
     allocCount_(0),
     frameCount_(0),
     allocRead_(0)
 {
-    if (!buffer)
+    if (!snapshots)
         return;
     IonSpew(IonSpew_Snapshots, "Creating snapshot reader");
     readSnapshotHeader();
     nextFrame();
 }
 
 static const uint32_t BAILOUT_KIND_SHIFT = 0;
 static const uint32_t BAILOUT_KIND_MASK = (1 << BAILOUT_KIND_BITS) - 1;
@@ -476,23 +498,50 @@ SnapshotReader::spewBailingFrom() const
         fprintf(IonSpewFile, " [%u], LIR: ", mirId_);
         LInstruction::printName(IonSpewFile, LInstruction::Opcode(lirOpcode_));
         fprintf(IonSpewFile, " [%u]", lirId_);
         fprintf(IonSpewFile, "\n");
     }
 }
 #endif
 
+// Pad serialized RValueAllocations by a multiple of X bytes in the allocation
+// buffer.  By padding serialized value allocations, we are building an
+// indexable table of elements of X bytes, and thus we can safely divide any
+// offset within the buffer by X to obtain an index.
+//
+// By padding, we are loosing space within the allocation buffer, but we
+// multiple by X the number of indexes that we can store on one byte in each
+// snapshots.
+//
+// Some value allocations are taking more than X bytes to be encoded, in which
+// case we will pad to a multiple of X, and we are wasting indexes. The choice
+// of X should be balanced between the wasted padding of serialized value
+// allocation, and the saving made in snapshot indexes.
+static const size_t ALLOCATION_TABLE_ALIGNMENT = 2; /* bytes */
+
 RValueAllocation
 SnapshotReader::readAllocation()
 {
     JS_ASSERT(allocRead_ < allocCount_);
     IonSpew(IonSpew_Snapshots, "Reading slot %u", allocRead_);
     allocRead_++;
-    return RValueAllocation::read(reader_);
+
+    uint32_t offset = reader_.readUnsigned() * ALLOCATION_TABLE_ALIGNMENT;
+    allocReader_.seek(allocTable_, offset);
+    return RValueAllocation::read(allocReader_);
+}
+
+bool
+SnapshotWriter::init()
+{
+    // Based on the measurements made in Bug 962555 comment 20, this should be
+    // enough to prevent the reallocation of the hash table for at least half of
+    // the compilations.
+    return allocMap_.init(32);
 }
 
 SnapshotOffset
 SnapshotWriter::startSnapshot(uint32_t frameCount, BailoutKind kind, bool resumeAfter)
 {
     nframes_ = frameCount;
     framesWritten_ = 0;
 
@@ -544,29 +593,48 @@ SnapshotWriter::trackFrame(uint32_t pcOp
     writer_.writeUnsigned(pcOpcode);
     writer_.writeUnsigned(mirOpcode);
     writer_.writeUnsigned(mirId);
     writer_.writeUnsigned(lirOpcode);
     writer_.writeUnsigned(lirId);
 }
 #endif
 
-void
+bool
 SnapshotWriter::add(const RValueAllocation &alloc)
 {
+    MOZ_ASSERT(allocMap_.initialized());
+
+    uint32_t offset;
+    RValueAllocMap::AddPtr p = allocMap_.lookupForAdd(alloc);
+    if (!p) {
+        // Write 0x7f in all padding bytes.
+        while (allocWriter_.length() % ALLOCATION_TABLE_ALIGNMENT)
+            allocWriter_.writeByte(0x7f);
+
+        offset = allocWriter_.length();
+        JS_ASSERT(offset % ALLOCATION_TABLE_ALIGNMENT == 0);
+        alloc.write(allocWriter_);
+        if (!allocMap_.add(p, alloc, offset))
+            return false;
+    } else {
+        offset = p->value();
+    }
+
     if (IonSpewEnabled(IonSpew_Snapshots)) {
         IonSpewHeader(IonSpew_Snapshots);
-        fprintf(IonSpewFile, "    slot %u: ", allocWritten_);
+        fprintf(IonSpewFile, "    slot %u (%d): ", allocWritten_, offset);
         alloc.dump(IonSpewFile);
         fprintf(IonSpewFile, "\n");
     }
 
     allocWritten_++;
     JS_ASSERT(allocWritten_ <= nallocs_);
-    alloc.write(writer_);
+    writer_.writeUnsigned(offset / ALLOCATION_TABLE_ALIGNMENT);
+    return true;
 }
 
 void
 SnapshotWriter::endFrame()
 {
     // Check that the last write succeeded.
     JS_ASSERT(nallocs_ == allocWritten_);
     nallocs_ = allocWritten_ = 0;
--- a/js/src/jit/Snapshots.h
+++ b/js/src/jit/Snapshots.h
@@ -2,22 +2,25 @@
  * vim: set ts=8 sts=4 et sw=4 tw=99:
  * This Source Code Form is subject to the terms of the Mozilla Public
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 #ifndef jit_Snapshot_h
 #define jit_Snapshot_h
 
+#include "jsalloc.h"
 #include "jsbytecode.h"
 
 #include "jit/CompactBuffer.h"
 #include "jit/IonTypes.h"
 #include "jit/Registers.h"
 
+#include "js/HashTable.h"
+
 namespace js {
 namespace jit {
 
 class RValueAllocation;
 
 class Location
 {
     friend class RValueAllocation;
@@ -347,63 +350,95 @@ class RValueAllocation
 #endif
           case CONSTANT:
           case JS_INT32:
             return value_ == s.value_;
           default:
             return true;
         }
     }
+
+    HashNumber hash() const;
+
+    struct Hasher
+    {
+        typedef RValueAllocation Key;
+        typedef Key Lookup;
+        static HashNumber hash(const Lookup &v) {
+            return v.hash();
+        }
+        static bool match(const Key &k, const Lookup &l) {
+            return k == l;
+        }
+    };
 };
 
 // Collects snapshots in a contiguous buffer, which is copied into IonScript
 // memory after code generation.
 class SnapshotWriter
 {
     CompactBufferWriter writer_;
+    CompactBufferWriter allocWriter_;
+
+    // Map RValueAllocations to an offset in the allocWriter_ buffer.  This is
+    // useful as value allocations are repeated frequently.
+    typedef RValueAllocation RVA;
+    typedef HashMap<RVA, uint32_t, RVA::Hasher, SystemAllocPolicy> RValueAllocMap;
+    RValueAllocMap allocMap_;
 
     // These are only used to assert sanity.
     uint32_t nallocs_;
     uint32_t allocWritten_;
     uint32_t nframes_;
     uint32_t framesWritten_;
     SnapshotOffset lastStart_;
 
   public:
+    bool init();
+
     SnapshotOffset startSnapshot(uint32_t frameCount, BailoutKind kind, bool resumeAfter);
     void startFrame(JSFunction *fun, JSScript *script, jsbytecode *pc, uint32_t exprStack);
 #ifdef TRACK_SNAPSHOTS
     void trackFrame(uint32_t pcOpcode, uint32_t mirOpcode, uint32_t mirId,
                     uint32_t lirOpcode, uint32_t lirId);
 #endif
     void endFrame();
 
-    void add(const RValueAllocation &slot);
+    bool add(const RValueAllocation &slot);
 
     void endSnapshot();
 
     bool oom() const {
         return writer_.oom() || writer_.length() >= MAX_BUFFER_SIZE;
     }
 
-    size_t size() const {
+    size_t listSize() const {
         return writer_.length();
     }
-    const uint8_t *buffer() const {
+    const uint8_t *listBuffer() const {
         return writer_.buffer();
     }
+
+    size_t RVATableSize() const {
+        return allocWriter_.length();
+    }
+    const uint8_t *RVATableBuffer() const {
+        return allocWriter_.buffer();
+    }
 };
 
 // A snapshot reader reads the entries out of the compressed snapshot buffer in
 // a script. These entries describe the equivalent interpreter frames at a given
 // position in JIT code. Each entry is an Ion's value allocations, used to
 // recover the corresponding Value from an Ion frame.
 class SnapshotReader
 {
     CompactBufferReader reader_;
+    CompactBufferReader allocReader_;
+    const uint8_t* allocTable_;
 
     uint32_t pcOffset_;           // Offset from script->code.
     uint32_t allocCount_;         // Number of slots.
     uint32_t frameCount_;
     BailoutKind bailoutKind_;
     uint32_t framesRead_;         // Number of frame headers that have been read.
     uint32_t allocRead_;          // Number of slots that have been read.
     bool resumeAfter_;
@@ -420,17 +455,18 @@ class SnapshotReader
     void spewBailingFrom() const;
 #endif
 
   private:
     void readSnapshotHeader();
     void readFrameHeader();
 
   public:
-    SnapshotReader(const uint8_t *buffer, const uint8_t *end);
+    SnapshotReader(const uint8_t *snapshots, uint32_t offset,
+                   uint32_t RVATableSize, uint32_t listSize);
 
     uint32_t pcOffset() const {
         return pcOffset_;
     }
     uint32_t allocations() const {
         return allocCount_;
     }
     BailoutKind bailoutKind() const {
--- a/js/src/jsapi-tests/testJitRValueAlloc.cpp
+++ b/js/src/jsapi-tests/testJitRValueAlloc.cpp
@@ -16,16 +16,19 @@ using namespace js::jit;
 // be encoded and decoded correctly.  We iterate on all registers and on many
 // fake stack locations (Fibonacci).
 static RValueAllocation
 Read(const RValueAllocation &slot)
 {
     CompactBufferWriter writer;
     slot.write(writer);
 
+    // Call hash to run its assertions.
+    slot.hash();
+
     CompactBufferReader reader(writer);
     return RValueAllocation::read(reader);
 }
 
 BEGIN_TEST(testJitRValueAlloc_Double)
 {
     RValueAllocation s;
     for (uint32_t i = 0; i < FloatRegisters::Total; i++) {