The Tor Browser / file revision

 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-

  * 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_shared_IonAssemblerBufferWithConstantPools_h

 #define jit_shared_IonAssemblerBufferWithConstantPools_h

 #include "mozilla/DebugOnly.h"

 #include "assembler/wtf/SegmentedVector.h"

 #include "jit/IonSpewer.h"

 #include "jit/shared/IonAssemblerBuffer.h"

 namespace js {

 namespace jit {

 typedef Vector<BufferOffset, 512, OldIonAllocPolicy> LoadOffsets;

 struct Pool

   : public OldIonAllocPolicy

 {

     const int maxOffset;

     const int immSize;

     const int instSize;

     const int bias;

   private:

     const int alignment;

   public:

     const bool isBackref;

     const bool canDedup;

     // "other" is the backwards half of this pool, it is held in another pool structure

     Pool *other;

     uint8_t *poolData;

     uint32_t numEntries;

     uint32_t buffSize;

     LoadOffsets loadOffsets;

     // When filling pools where the the size of an immediate is larger

     // than the size of an instruction, we find we're in a case where the distance between the

     // next instruction and the next pool slot is increasing!

     // Moreover, If we want to do fancy things like deduplicate pool entries at

     // dump time, we may not know the location in a pool (and thus the limiting load)

     // until very late.

     // Lastly, it may be beneficial to interleave the pools.  I have absolutely no idea

     // how that will work, but my suspicions are that it will be difficult.

     BufferOffset limitingUser;

     int limitingUsee;

     Pool(int maxOffset_, int immSize_, int instSize_, int bias_, int alignment_, LifoAlloc &LifoAlloc_,

          bool isBackref_ = false, bool canDedup_ = false, Pool *other_ = nullptr)

         : maxOffset(maxOffset_), immSize(immSize_), instSize(instSize_),

           bias(bias_), alignment(alignment_),

           isBackref(isBackref_), canDedup(canDedup_), other(other_),

           poolData(static_cast<uint8_t *>(LifoAlloc_.alloc(8*immSize))), numEntries(0),

           buffSize(8), loadOffsets(), limitingUser(), limitingUsee(INT_MIN)

     {

     }

     static const int garbage=0xa5a5a5a5;

     Pool() : maxOffset(garbage), immSize(garbage), instSize(garbage), bias(garbage),

              alignment(garbage), isBackref(garbage), canDedup(garbage), other((Pool*)garbage)

     {

     }

     // Sometimes, when we are adding large values to a pool, the limiting use may change.

     // Handle this case.  nextInst is the address of the

     void updateLimiter(BufferOffset nextInst) {

         int oldRange, newRange;

         if (isBackref) {

             // common expressions that are not subtracted: the location of the pool, ...

             oldRange = limitingUser.getOffset() - ((numEntries - limitingUsee) * immSize);

             newRange = nextInst.getOffset();

         } else {

             oldRange = (limitingUsee * immSize) - limitingUser.getOffset();

             newRange = (numEntries * immSize) - nextInst.getOffset();

         }

         if (!limitingUser.assigned() || newRange > oldRange) {

             // We have a new largest range!

             limitingUser = nextInst;

             limitingUsee = numEntries;

         }

     }

     // checkFull is called before any modifications have been made.

     // It is "if we were to add this instruction and pool entry,

     // would we be in an invalid state?".  If it is true, then it is in fact

     // time for a "pool dump".

     // poolOffset is the distance from the end of the current section to the end of the pool.

     //            For the last section of the pool, this will be the size of the footer

     //            For the first section of the pool, it will be the size of every other

     //            section and the footer

     // codeOffset is the instruction-distance from the pool to the beginning of the buffer.

     //            Since codeOffset only includes instructions, the number is the same for

     //            the beginning and end of the pool.

     // instOffset is the offset from the beginning of the buffer to the instruction that

     //            is about to be placed.

     bool checkFullBackref(int poolOffset, int codeOffset) {

         if (!limitingUser.assigned())

             return false;

         signed int distance =

             limitingUser.getOffset() + bias

             - codeOffset + poolOffset +

             (numEntries - limitingUsee + 1) * immSize;

         if (distance >= maxOffset)

             return true;

         return false;

     }

     // checkFull answers the question "If a pool were placed at poolOffset, would

     // any reference into the pool be out of range?". It is meant to be used as instructions

     // and elements are inserted, to determine if a saved perforation point needs to be used.

     bool checkFull(int poolOffset) {

         // Inserting an instruction into the stream can

         // push any of the pools out of range.

         // Similarly, inserting into a pool can push the pool entry out of range

         JS_ASSERT(!isBackref);

         // Not full if there aren't any uses.

         if (!limitingUser.assigned()) {

             return false;

         }

         // We're considered "full" when:

         // bias + abs(poolOffset + limitingeUsee * numEntries - limitingUser) + sizeof(other_pools) >= maxOffset

         if (poolOffset + limitingUsee * immSize - (limitingUser.getOffset() + bias) >= maxOffset) {

             return true;

         }

         return false;

     }

     // By the time this function is called, we'd damn well better know that this is going to succeed.

     uint32_t insertEntry(uint8_t *data, BufferOffset off, LifoAlloc &LifoAlloc_) {

         if (numEntries == buffSize) {

             buffSize <<= 1;

             uint8_t *tmp = static_cast<uint8_t*>(LifoAlloc_.alloc(immSize * buffSize));

             memcpy(tmp, poolData,  immSize * numEntries);

             if (poolData == nullptr) {

                 buffSize = 0;

                 return -1;

             }

             poolData = tmp;

         }

         memcpy(&poolData[numEntries * immSize], data, immSize);

         loadOffsets.append(off.getOffset());

         return numEntries++;

     }

     bool reset(LifoAlloc &a) {

         numEntries = 0;

         buffSize = 8;

         poolData = static_cast<uint8_t*>(a.alloc(buffSize * immSize));

         if (poolData == nullptr)

             return false;

         void *otherSpace = a.alloc(sizeof(Pool));

         if (otherSpace == nullptr)

             return false;

         other = new (otherSpace) Pool(other->maxOffset, other->immSize, other->instSize,

                                       other->bias, other->alignment, a, other->isBackref,

                                       other->canDedup);

         new (&loadOffsets) LoadOffsets;

         limitingUser = BufferOffset();

         limitingUsee = -1;

         return true;

     }

     // WARNING: This will not always align values. It will only

     // align to the requirement of the pool. If the pool is empty,

     // there is nothing to be aligned, so it will not perform any alignment

     uint8_t* align(uint8_t *ptr) {

         return (uint8_t*)align((uint32_t)ptr);

     }

     uint32_t align(uint32_t ptr) {

         if (numEntries == 0)

             return ptr;

         return (ptr + alignment-1) & ~(alignment-1);

     }

     uint32_t forceAlign(uint32_t ptr) {

         return (ptr + alignment-1) & ~(alignment-1);

     }

     bool isAligned(uint32_t ptr) {

         return ptr == align(ptr);

     }

     int getAlignment() {

         return alignment;

     }

     uint32_t addPoolSize(uint32_t start) {

         start = align(start);

         start += immSize * numEntries;

         return start;

     }

     uint8_t *addPoolSize(uint8_t *start) {

         start = align(start);

         start += immSize * numEntries;

         return start;

     }

     uint32_t getPoolSize() {

         return immSize * numEntries;

     }

 };

 template <int SliceSize, int InstBaseSize>

 struct BufferSliceTail : public BufferSlice<SliceSize> {

     Pool *data;

     mozilla::Array<uint8_t, (SliceSize + (InstBaseSize * 8 - 1)) / (InstBaseSize * 8)> isBranch;

     bool isNatural : 1;

     BufferSliceTail *getNext() {

         return (BufferSliceTail *)this->next;

     }

     BufferSliceTail() : data(nullptr), isNatural(true) {

         memset(&isBranch[0], 0, sizeof(isBranch));

     }

     void markNextAsBranch() {

         int idx = this->nodeSize / InstBaseSize;

         isBranch[idx >> 3] |= 1 << (idx & 0x7);

     }

     bool isNextBranch() {

         unsigned int size = this->nodeSize;

         if (size >= SliceSize)

             return false;

         int idx = size / InstBaseSize;

         return (isBranch[idx >> 3] >> (idx & 0x7)) & 1;

     }

 };

 #if 0

 static int getId() {

     if (MaybeGetIonContext())

         return MaybeGetIonContext()->getNextAssemblerId();

     return NULL_ID;

 }

 #endif

 static inline void spewEntry(uint8_t *ptr, int length) {

 #if IS_LITTLE_ENDIAN

     for (int idx = 0; idx < length; idx++) {

         IonSpewCont(IonSpew_Pools, "%02x", ptr[length - idx - 1]);

         if (((idx & 3) == 3) && (idx + 1 != length))

             IonSpewCont(IonSpew_Pools, "_");

     }

 #else

     for (int idx = 0; idx < length; idx++) {

         IonSpewCont(IonSpew_Pools, "%02x", ptr[idx]);

         if (((idx & 3) == 3) && (idx + 1 != length))

             IonSpewCont(IonSpew_Pools, "_");

     }

 #endif

 }

 // NOTE: Adding in the ability to retroactively insert a pool has consequences!

 // Most notably, Labels stop working.  Normally, we create a label, later bind it.

 // when the label is bound, We back-patch all previous references to the label with

 // the correct offset. However, since a pool may be retroactively inserted, we don't

 // actually know what the final offset is going to be until much later. This will

 // happen (in some instances) after the pools have been finalized. Attempting to compute

 // the correct offsets for branches as the pools are finalized is quite infeasible.

 // Instead, I write *just* the number of instructions that will be jumped over, then

 // when we go to copy the instructions into the executable buffer, fix up all of the

 // offsets to include the pools. Since we have about 32 megabytes worth of offset,

 // I am not very worried about the pools moving it out of range.

 // Now, How exactly do we generate these? The first step is to identify which

 // instructions are actually branches that need to be fixed up.  A single bit

 // per instruction should be enough to determine which ones are branches, but

 // we have no guarantee that all instructions are the same size, so the start of

 // each branch instruction will be marked with a bit (1 bit per byte).

 // then we neet to call up to the assembler to determine what the offset of the branch

 // is. The offset will be the number of instructions that are being skipped over

 // along with any processor bias. We then need to calculate the offset, including pools

 // and write that value into the buffer.  At this point, we can write it into the

 // executable buffer, or the AssemblerBuffer, and copy the data over later.

 // Previously, This was all handled by the assembler, since the location

 // and size of pools were always known as soon as its location had been reached.

 // A class for indexing into constant pools.

 // Each time a pool entry is added, one of these is generated.

 // This can be supplied to read and write that entry after the fact.

 // And it can be used to get the address of the entry once the buffer

 // has been finalized, and an executable copy allocated.

 template <int SliceSize, int InstBaseSize, class Inst, class Asm, int poolKindBits>

 struct AssemblerBufferWithConstantPool : public AssemblerBuffer<SliceSize, Inst> {

   private:

     mozilla::Array<int, 1 << poolKindBits> entryCount;

     static const int offsetBits = 32 - poolKindBits;

   public:

     class PoolEntry {

         template <int ss, int ibs, class i, class a, int pkb>

         friend struct AssemblerBufferWithConstantPool;

         uint32_t offset_ : offsetBits;

         uint32_t kind_ : poolKindBits;

         PoolEntry(int offset, int kind) : offset_(offset), kind_(kind) {

         }

       public:

         uint32_t encode() {

             uint32_t ret;

             memcpy(&ret, this, sizeof(uint32_t));

             return ret;

         }

         PoolEntry(uint32_t bits) : offset_(((1u << offsetBits) - 1) & bits),

                                  kind_(bits >> offsetBits) {

         }

         PoolEntry() : offset_((1u << offsetBits) - 1), kind_((1u << poolKindBits) - 1) {

         }

         uint32_t poolKind() const {

             return kind_;

         }

         uint32_t offset() const {

             return offset_;

         }

     };

   private:

     typedef BufferSliceTail<SliceSize, InstBaseSize> BufferSlice;

     typedef AssemblerBuffer<SliceSize, Inst> Parent;

     // The size of a guard instruction

     const int guardSize;

     // The size of the header that is put at the beginning of a full pool

     const int headerSize;

     // The size of a footer that is put in a pool after it is full.

     const int footerSize;

     // the number of sub-pools that we can allocate into.

     static const int numPoolKinds = 1 << poolKindBits;

     Pool *pools;

     // The buffer should be aligned to this address.

     const int instBufferAlign;

     // the number of times we've dumped the pool.

     int numDumps;

     struct PoolInfo {

         int offset; // the number of instructions before the start of the pool

         int size;   // the size of the pool, including padding

         int finalPos; // the end of the buffer, in bytes from the beginning of the buffer

         BufferSlice *slice;

     };

     PoolInfo *poolInfo;

     // we need to keep track of how large the pools are, so we can allocate

     // enough space for them later.  This should include any amount of padding

     // necessary to keep the pools aligned.

     int poolSize;

     // The Assembler should set this to true if it does not want us to dump a pool here

     int canNotPlacePool;

     // Are we filling up the forwards or backwards pools?

     bool inBackref;

     // Cache the last place we saw an opportunity to dump the pool

     BufferOffset perforation;

     BufferSlice *perforatedNode;

   public:

     int id;

   private:

     static const int logBasePoolInfo = 3;

     BufferSlice ** getHead() {

         return (BufferSlice**)&this->head;

     }

     BufferSlice ** getTail() {

         return (BufferSlice**)&this->tail;

     }

     virtual BufferSlice *newSlice(LifoAlloc &a) {

         BufferSlice *tmp = static_cast<BufferSlice*>(a.alloc(sizeof(BufferSlice)));

         if (!tmp) {

             this->m_oom = true;

             return nullptr;

         }

         new (tmp) BufferSlice;

         return tmp;

     }

   public:

     AssemblerBufferWithConstantPool(int guardSize_, int headerSize_, int footerSize_, Pool *pools_, int instBufferAlign_)

         : guardSize(guardSize_), headerSize(headerSize_),

           footerSize(footerSize_),

           pools(pools_),

           instBufferAlign(instBufferAlign_), numDumps(0),

           poolInfo(nullptr),

           poolSize(0), canNotPlacePool(0), inBackref(false),

           perforatedNode(nullptr), id(-1)

     {

         for (int idx = 0; idx < numPoolKinds; idx++) {

             entryCount[idx] = 0;

         }

     }

     // We need to wait until an AutoIonContextAlloc is created by the

     // IonMacroAssembler, before allocating any space.

     void initWithAllocator() {

         poolInfo = static_cast<PoolInfo*>(this->LifoAlloc_.alloc(sizeof(PoolInfo) * (1 << logBasePoolInfo)));

     }

     const PoolInfo & getInfo(int x) const {

         static const PoolInfo nil = {0,0,0};

         if (x < 0 || x >= numDumps)

             return nil;

         return poolInfo[x];

     }

     void executableCopy(uint8_t *dest_) {

         if (this->oom())

             return;

         // TODO: only do this when the pool actually has a value in it

         flushPool();

         for (int idx = 0; idx < numPoolKinds; idx++) {

             JS_ASSERT(pools[idx].numEntries == 0 && pools[idx].other->numEntries == 0);

         }

         typedef mozilla::Array<uint8_t, InstBaseSize> Chunk;

         mozilla::DebugOnly<Chunk *> start = (Chunk*)dest_;

         Chunk *dest = (Chunk*)(((uint32_t)dest_ + instBufferAlign - 1) & ~(instBufferAlign -1));

         int curIndex = 0;

         int curInstOffset = 0;

         JS_ASSERT(start == dest);

         for (BufferSlice * cur = *getHead(); cur != nullptr; cur = cur->getNext()) {

             Chunk *src = (Chunk*)&cur->instructions;

             for (unsigned int idx = 0; idx <cur->size()/InstBaseSize;

                  idx++, curInstOffset += InstBaseSize) {

                 // Is the current instruction a branch?

                 if (cur->isBranch[idx >> 3] & (1<<(idx&7))) {

                     // It's a branch.  fix up the branchiness!

                     patchBranch((Inst*)&src[idx], curIndex, BufferOffset(curInstOffset));

                 }

                 memcpy(&dest[idx], &src[idx], sizeof(Chunk));

             }

             dest+=cur->size()/InstBaseSize;

             if (cur->data != nullptr) {

                 // have the repatcher move on to the next pool

                 curIndex ++;

                 // loop over all of the pools, copying them into place.

                 uint8_t *poolDest = (uint8_t*)dest;

                 Asm::writePoolHeader(poolDest, cur->data, cur->isNatural);

                 poolDest += headerSize;

                 for (int idx = 0; idx < numPoolKinds; idx++) {

                     Pool *curPool = &cur->data[idx];

                     // align the pool.

                     poolDest = curPool->align(poolDest);

                     memcpy(poolDest, curPool->poolData, curPool->immSize * curPool->numEntries);

                     poolDest += curPool->immSize * curPool->numEntries;

                 }

                 // now go over the whole list backwards, and copy in the reverse portions

                 for (int idx = numPoolKinds-1; idx >= 0; idx--) {

                     Pool *curPool = cur->data[idx].other;

                     // align the pool.

                     poolDest = curPool->align(poolDest);

                     memcpy(poolDest, curPool->poolData, curPool->immSize * curPool->numEntries);

                     poolDest += curPool->immSize * curPool->numEntries;

                 }

                 // write a footer in place

                 Asm::writePoolFooter(poolDest, cur->data, cur->isNatural);

                 poolDest += footerSize;

                 // at this point, poolDest had better still be aligned to a chunk boundary.

                 dest = (Chunk*) poolDest;

             }

         }

     }

     BufferOffset insertEntry(uint32_t instSize, uint8_t *inst, Pool *p, uint8_t *data, PoolEntry *pe = nullptr) {

         if (this->oom() && !this->bail())

             return BufferOffset();

         int token;

         if (p != nullptr) {

             int poolId = p - pools;

             const char sigil = inBackref ? 'B' : 'F';

             IonSpew(IonSpew_Pools, "[%d]{%c} Inserting entry into pool %d", id, sigil, poolId);

             IonSpewStart(IonSpew_Pools, "[%d] data is: 0x", id);

             spewEntry(data, p->immSize);

             IonSpewFin(IonSpew_Pools);

         }

         // insert the pool value

         if (inBackref)

             token = insertEntryBackwards(instSize, inst, p, data);

         else

             token = insertEntryForwards(instSize, inst, p, data);

         // now to get an instruction to write

         PoolEntry retPE;

         if (p != nullptr) {

             if (this->oom())

                 return BufferOffset();

             int poolId = p - pools;

             IonSpew(IonSpew_Pools, "[%d] Entry has token %d, offset ~%d", id, token, size());

             Asm::insertTokenIntoTag(instSize, inst, token);

             JS_ASSERT(poolId < (1 << poolKindBits));

             JS_ASSERT(poolId >= 0);

             // Figure out the offset within like-kinded pool entries

             retPE = PoolEntry(entryCount[poolId], poolId);

             entryCount[poolId]++;

         }

         // Now inst is a valid thing to insert into the instruction stream

         if (pe != nullptr)

             *pe = retPE;

         return this->putBlob(instSize, inst);

     }

     uint32_t insertEntryBackwards(uint32_t instSize, uint8_t *inst, Pool *p, uint8_t *data) {

         // unlike the forward case, inserting an instruction without inserting

         // anything into a pool after a pool has been placed, we don't affect

         // anything relevant, so we can skip this check entirely!

         if (p == nullptr)

             return INT_MIN;

         // TODO: calculating offsets for the alignment requirements is *hard*

         // Instead, assume that we always add the maximum.

         int poolOffset = footerSize;

         Pool *cur, *tmp;

         // NOTE: we want to process the pools from last to first.

         // Since the last pool is pools[0].other, and the first pool

         // is pools[numPoolKinds-1], we actually want to process this

         // forwards.

         for (cur = pools; cur < &pools[numPoolKinds]; cur++) {

             // fetch the pool for the backwards half.

             tmp = cur->other;

             if (p == cur)

                 tmp->updateLimiter(this->nextOffset());

             if (tmp->checkFullBackref(poolOffset, perforation.getOffset())) {

                 // uh-oh, the backwards pool is full.  Time to finalize it, and

                 // switch to a new forward pool.

                 if (p != nullptr)

                     IonSpew(IonSpew_Pools, "[%d]Inserting pool entry caused a spill", id);

                 else

                     IonSpew(IonSpew_Pools, "[%d]Inserting instruction(%d) caused a spill", id, size());

                 this->finishPool();

                 if (this->oom())

                     return uint32_t(-1);

                 return this->insertEntryForwards(instSize, inst, p, data);

             }

             // when moving back to front, calculating the alignment is hard, just be

             // conservative with it.

             poolOffset += tmp->immSize * tmp->numEntries + tmp->getAlignment();

             if (p == tmp) {

                 poolOffset += tmp->immSize;

             }

         }

         return p->numEntries + p->other->insertEntry(data, this->nextOffset(), this->LifoAlloc_);

     }

     // Simultaneously insert an instSized instruction into the stream,

     // and an entry into the pool.  There are many things that can happen.

     // 1) the insertion goes as planned

     // 2) inserting an instruction pushes a previous pool-reference out of range, forcing a dump

     // 2a) there isn't a reasonable save point in the instruction stream. We need to save room for

     //     a guard instruction to branch over the pool.

     int insertEntryForwards(uint32_t instSize, uint8_t *inst, Pool *p, uint8_t *data) {

         // Advance the "current offset" by an inst, so everyone knows what their offset should be.

         uint32_t nextOffset = this->size() + instSize;

         uint32_t poolOffset = nextOffset;

         Pool *tmp;

         // If we need a guard instruction, reserve space for that.

         if (!perforatedNode)

             poolOffset += guardSize;

         // Also, take into account the size of the header that will be placed *after*

         // the guard instruction

         poolOffset += headerSize;

         // Perform the necessary range checks.

         for (tmp = pools; tmp < &pools[numPoolKinds]; tmp++) {

             // The pool may wish for a particular alignment, Let's give it one.

             JS_ASSERT((tmp->getAlignment() & (tmp->getAlignment() - 1)) == 0);

             // The pool only needs said alignment *if* there are any entries in the pool

             // WARNING: the pool needs said alignment if there are going to be entries in

             // the pool after this entry has been inserted

             if (p == tmp)

                 poolOffset = tmp->forceAlign(poolOffset);

             else

                 poolOffset = tmp->align(poolOffset);

             // If we're at the pool we want to insert into, find a new limiter

             // before we do the range check.

             if (p == tmp) {

                 p->updateLimiter(BufferOffset(nextOffset));

             }

             if (tmp->checkFull(poolOffset)) {

                 // uh-oh. DUMP DUMP DUMP

                 if (p != nullptr)

                     IonSpew(IonSpew_Pools, "[%d] Inserting pool entry caused a spill", id);

                 else

                     IonSpew(IonSpew_Pools, "[%d] Inserting instruction(%d) caused a spill", id, size());

                 this->dumpPool();

                 return this->insertEntryBackwards(instSize, inst, p, data);

             }

             // include the size of this pool in the running total

             if (p == tmp) {

                 nextOffset += tmp->immSize;

             }

             nextOffset += tmp->immSize * tmp->numEntries;

         }

         if (p == nullptr) {

             return INT_MIN;

         }

         return p->insertEntry(data, this->nextOffset(), this->LifoAlloc_);

     }

     BufferOffset putInt(uint32_t value) {

         return insertEntry(sizeof(uint32_t) / sizeof(uint8_t), (uint8_t*)&value, nullptr, nullptr);

     }

     // Mark the current section as an area where we can

     // later go to dump a pool

     void perforate() {

         // If we're filling the backrefrences, we don't want to start looking for a new dumpsite.

         if (inBackref)

             return;

         if (canNotPlacePool)

             return;

         // If there is nothing in the pool, then it is strictly disadvantageous

         // to attempt to place a pool here

         bool empty = true;

         for (int i = 0; i < numPoolKinds; i++) {

             if (pools[i].numEntries != 0) {

                 empty = false;

                 break;

             }

         }

         if (empty)

             return;

         perforatedNode = *getTail();

         perforation = this->nextOffset();

         Parent::perforate();

         IonSpew(IonSpew_Pools, "[%d] Adding a perforation at offset %d", id, perforation.getOffset());

     }

     // After a pool is finished, no more elements may be added to it. During this phase, we

     // will know the exact offsets to the pool entries, and those values should be written into

     // the given instructions.

     PoolInfo getPoolData() const {

         int prevOffset = getInfo(numDumps-1).offset;

         int prevEnd = getInfo(numDumps-1).finalPos;

         // calculate the offset of the start of this pool;

         int perfOffset = perforation.assigned() ?

             perforation.getOffset() :

             this->nextOffset().getOffset() + this->guardSize;

         int initOffset = prevEnd + (perfOffset - prevOffset);

         int finOffset = initOffset;

         bool poolIsEmpty = true;

         for (int poolIdx = 0; poolIdx < numPoolKinds; poolIdx++) {

             if (pools[poolIdx].numEntries != 0) {

                 poolIsEmpty = false;

                 break;

             }

             if (pools[poolIdx].other != nullptr && pools[poolIdx].other->numEntries != 0) {

                 poolIsEmpty = false;

                 break;

             }

         }

         if (!poolIsEmpty) {

             finOffset += headerSize;

             for (int poolIdx = 0; poolIdx < numPoolKinds; poolIdx++) {

                 finOffset=pools[poolIdx].align(finOffset);

                 finOffset+=pools[poolIdx].numEntries * pools[poolIdx].immSize;

             }

             // And compute the necessary adjustments for the second half of the pool.

             for (int poolIdx = numPoolKinds-1; poolIdx >= 0; poolIdx--) {

                 finOffset=pools[poolIdx].other->align(finOffset);

                 finOffset+=pools[poolIdx].other->numEntries * pools[poolIdx].other->immSize;

             }

             finOffset += footerSize;

         }

         PoolInfo ret;

         ret.offset = perfOffset;

         ret.size = finOffset - initOffset;

         ret.finalPos = finOffset;

         ret.slice = perforatedNode;

         return ret;

     }

     void finishPool() {

         // This function should only be called while the backwards half of the pool

         // is being filled in. The backwards half of the pool is always in a state

         // where it is sane. Everything that needs to be done here is for "sanity's sake".

         // The per-buffer pools need to be reset, and we need to record the size of the pool.

         IonSpew(IonSpew_Pools, "[%d] Finishing pool %d", id, numDumps);

         JS_ASSERT(inBackref);

         PoolInfo newPoolInfo = getPoolData();

         if (newPoolInfo.size == 0) {

             // The code below also creates a new pool, but that is not necessary, since

             // the pools have not been modified at all.

             new (&perforation) BufferOffset();

             perforatedNode = nullptr;

             inBackref = false;

             IonSpew(IonSpew_Pools, "[%d] Aborting because the pool is empty", id);

             // Bail out early, since we don't want to even pretend these pools exist.

             return;

         }

         JS_ASSERT(perforatedNode != nullptr);

         if (numDumps >= (1<<logBasePoolInfo) && (numDumps & (numDumps-1)) == 0) {

             // need to resize.

             PoolInfo *tmp = static_cast<PoolInfo*>(this->LifoAlloc_.alloc(sizeof(PoolInfo) * numDumps * 2));

             if (tmp == nullptr) {

                 this->fail_oom();

                 return;

             }

             memcpy(tmp, poolInfo, sizeof(PoolInfo) * numDumps);

             poolInfo = tmp;

         }

         // In order to figure out how to fix up the loads for the second half of the pool

         // we need to find where the bits of the pool that have been implemented end.

         int poolOffset = perforation.getOffset();

         int magicAlign = getInfo(numDumps-1).finalPos - getInfo(numDumps-1).offset;

         poolOffset += magicAlign;

         poolOffset += headerSize;

         for (int poolIdx = 0; poolIdx < numPoolKinds; poolIdx++) {

             poolOffset=pools[poolIdx].align(poolOffset);

             poolOffset+=pools[poolIdx].numEntries * pools[poolIdx].immSize;

         }

         mozilla::Array<LoadOffsets, 1 << poolKindBits> outcasts;

         mozilla::Array<uint8_t *, 1 << poolKindBits> outcastEntries;

         // All of the pool loads referred to by this code are going to

         // need fixing up here.

         int skippedBytes = 0;

         for (int poolIdx = numPoolKinds-1; poolIdx >= 0; poolIdx--) {

             Pool *p =  pools[poolIdx].other;

             JS_ASSERT(p != nullptr);

             unsigned int idx = p->numEntries-1;

             // Allocate space for tracking information that needs to be propagated to the next pool

             // as well as space for quickly updating the pool entries in the current pool to remove

             // the entries that don't actually fit.  I probably should change this over to a vector

             outcastEntries[poolIdx] = new uint8_t[p->getPoolSize()];

             bool *preservedEntries = new bool[p->numEntries];

             // Hacks on top of Hacks!

             // the patching code takes in the address of the instruction to be patched,

             // and the "address" of the element in the pool that we want to load.

             // However, since the code isn't actually in an array, we need to lie about

             // the address that the pool is in. Furthermore, since the offsets are

             // technically from the beginning of the FORWARD reference section, we have

             // to lie to ourselves about where this pool starts in order to make sure

             // the distance into the pool is interpreted correctly.

             // There is a more elegant way to fix this that will need to be implemented

             // eventually. We will want to provide the fixup function with a method to

             // convert from a 'token' into a pool offset.

             poolOffset = p->align(poolOffset);

             int numSkips = 0;

             int fakePoolOffset = poolOffset - pools[poolIdx].numEntries * pools[poolIdx].immSize;

             for (BufferOffset *iter = p->loadOffsets.end()-1;

                  iter != p->loadOffsets.begin()-1; --iter, --idx)

             {

                 IonSpew(IonSpew_Pools, "[%d] Linking entry %d in pool %d", id, idx+ pools[poolIdx].numEntries, poolIdx);

                 JS_ASSERT(iter->getOffset() >= perforation.getOffset());

                 // Everything here is known, we can safely do the necessary substitutions

                 Inst * inst = this->getInst(*iter);

                 // Manually compute the offset, including a possible bias.

                 // Also take into account the whole size of the pool that is being placed.

                 int codeOffset = fakePoolOffset - iter->getOffset() - newPoolInfo.size + numSkips * p->immSize - skippedBytes;

                 // That is, patchConstantPoolLoad wants to be handed the address of the

                 // pool entry that is being loaded.  We need to do a non-trivial amount

                 // of math here, since the pool that we've made does not actually reside there

                 // in memory.

                 IonSpew(IonSpew_Pools, "[%d] Fixing offset to %d", id, codeOffset - magicAlign);

                 if (!Asm::patchConstantPoolLoad(inst, (uint8_t*)inst + codeOffset - magicAlign)) {

                     // NOTE: if removing this entry happens to change the alignment of the next

                     // block, chances are you will have a bad time.

                     // ADDENDUM: this CANNOT happen on ARM, because the only elements that

                     // fall into this case are doubles loaded via vfp, but they will also be

                     // the last pool, which means it cannot affect the alignment of any other

                     // Sub Pools.

                     IonSpew(IonSpew_Pools, "[%d]***Offset was still out of range!***", id, codeOffset - magicAlign);

                     IonSpew(IonSpew_Pools, "[%d] Too complicated; bailingp", id);

                     this->fail_bail();

                     // only free up to the current offset

                     for (int pi = poolIdx; pi < numPoolKinds; pi++)

                         delete[] outcastEntries[pi];

                     delete[] preservedEntries;

                     return;

                 } else {

                     preservedEntries[idx] = true;

                 }

             }

             // remove the elements of the pool that should not be there (YAY, MEMCPY)

             unsigned int idxDest = 0;

             // If no elements were skipped, no expensive copy is necessary.

             if (numSkips != 0) {

                 for (idx = 0; idx < p->numEntries; idx++) {

                     if (preservedEntries[idx]) {

                         if (idx != idxDest) {

                             memcpy(&p->poolData[idxDest * p->immSize],

                                    &p->poolData[idx * p->immSize],

                                    p->immSize);

                         }

                         idxDest++;

                     }

                 }

                 p->numEntries -= numSkips;

             }

             poolOffset += p->numEntries * p->immSize;

             delete[] preservedEntries;

             preservedEntries = nullptr;

         }

         // bind the current pool to the perforation point.

         Pool **tmp = &perforatedNode->data;

         *tmp = static_cast<Pool*>(this->LifoAlloc_.alloc(sizeof(Pool) * numPoolKinds));

         if (tmp == nullptr) {

             this->fail_oom();

             for (int pi = 0; pi < numPoolKinds; pi++)

                 delete[] outcastEntries[pi];

             return;

         }

         // The above operations may have changed the size of pools!

         // recalibrate the size of the pool.

         newPoolInfo = getPoolData();

         poolInfo[numDumps] = newPoolInfo;

         poolSize += poolInfo[numDumps].size;

         numDumps++;

         memcpy(*tmp, pools, sizeof(Pool) * numPoolKinds);

         // reset everything to the state that it was in when we started

         for (int poolIdx = 0; poolIdx < numPoolKinds; poolIdx++) {

             if (!pools[poolIdx].reset(this->LifoAlloc_)) {

                 this->fail_oom();

                 for (int pi = 0; pi < numPoolKinds; pi++)

                     delete[] outcastEntries[pi];

                 return;

             }

         }

         new (&perforation) BufferOffset();

         perforatedNode = nullptr;

         inBackref = false;

         // Now that the backwards pool has been emptied, and a new forward pool

         // has been allocated, it is time to populate the new forward pool with

         // any entries that couldn't fit in the backwards pool.

         for (int poolIdx = 0; poolIdx < numPoolKinds; poolIdx++) {

             // Technically, the innermost pool will never have this issue, but it is easier

             // to just handle this case.

             // Since the pool entry was filled back-to-front, and in the next buffer, the elements

             // should be front-to-back, this insertion also needs to proceed backwards

             int idx = outcasts[poolIdx].length();

             for (BufferOffset *iter = outcasts[poolIdx].end()-1;

                  iter != outcasts[poolIdx].begin()-1;

                  --iter, --idx) {

                 pools[poolIdx].updateLimiter(*iter);

                 Inst *inst = this->getInst(*iter);

                 Asm::insertTokenIntoTag(pools[poolIdx].instSize, (uint8_t*)inst, outcasts[poolIdx].end()-1-iter);

                 pools[poolIdx].insertEntry(&outcastEntries[poolIdx][idx*pools[poolIdx].immSize], *iter, this->LifoAlloc_);

             }

             delete[] outcastEntries[poolIdx];

         }

         // this (*2) is not technically kosher, but I want to get this bug fixed.

         // It should actually be guardSize + the size of the instruction that we're attempting

         // to insert. Unfortunately that vaue is never passed in.  On ARM, these instructions

         // are always 4 bytes, so guardSize is legit to use.

         poolOffset = this->size() + guardSize * 2;

         poolOffset += headerSize;

         for (int poolIdx = 0; poolIdx < numPoolKinds; poolIdx++) {

             // There can still be an awkward situation where the element that triggered the

             // initial dump didn't fit into the pool backwards, and now, still does not fit into

             // this pool.  Now it is necessary to go and dump this pool (note: this is almost

             // certainly being called from dumpPool()).

             poolOffset = pools[poolIdx].align(poolOffset);

             if (pools[poolIdx].checkFull(poolOffset)) {

                 // ONCE AGAIN, UH-OH, TIME TO BAIL

                 dumpPool();

                 break;

             }

             poolOffset += pools[poolIdx].getPoolSize();

         }

     }

     void dumpPool() {

         JS_ASSERT(!inBackref);

         IonSpew(IonSpew_Pools, "[%d] Attempting to dump the pool", id);

         PoolInfo newPoolInfo = getPoolData();

         if (newPoolInfo.size == 0) {

             // If there is no data in the pool being dumped, don't dump anything.

             inBackref = true;

             IonSpew(IonSpew_Pools, "[%d]Abort, no pool data", id);

             return;

         }

         IonSpew(IonSpew_Pools, "[%d] Dumping %d bytes", id, newPoolInfo.size);

         if (!perforation.assigned()) {

             IonSpew(IonSpew_Pools, "[%d] No Perforation point selected, generating a new one", id);

             // There isn't a perforation here, we need to dump the pool with a guard.

             BufferOffset branch = this->nextOffset();

             bool shouldMarkAsBranch = this->isNextBranch();

             this->markNextAsBranch();

             this->putBlob(guardSize, nullptr);

             BufferOffset afterPool = this->nextOffset();

             Asm::writePoolGuard(branch, this->getInst(branch), afterPool);

             markGuard();

             perforatedNode->isNatural = false;

             if (shouldMarkAsBranch)

                 this->markNextAsBranch();

         }

         // We have a perforation.  Time to cut the instruction stream, patch in the pool

         // and possibly re-arrange the pool to accomodate its new location.

         int poolOffset = perforation.getOffset();

         int magicAlign =  getInfo(numDumps-1).finalPos - getInfo(numDumps-1).offset;

         poolOffset += magicAlign;

         poolOffset += headerSize;

         for (int poolIdx = 0; poolIdx < numPoolKinds; poolIdx++) {

             mozilla::DebugOnly<bool> beforePool = true;

             Pool *p = &pools[poolIdx];

             // Any entries that happened to be after the place we put our pool will need to be

             // switched from the forward-referenced pool to the backward-refrenced pool.

             int idx = 0;

             for (BufferOffset *iter = p->loadOffsets.begin();

                  iter != p->loadOffsets.end(); ++iter, ++idx)

             {

                 if (iter->getOffset() >= perforation.getOffset()) {

                     IonSpew(IonSpew_Pools, "[%d] Pushing entry %d in pool %d into the backwards section.", id, idx, poolIdx);

                     // insert this into the rear part of the pool.

                     int offset = idx * p->immSize;

                     p->other->insertEntry(&p->poolData[offset], BufferOffset(*iter), this->LifoAlloc_);

                     // update the limiting entry for this pool.

                     p->other->updateLimiter(*iter);

                     // Update the current pool to report fewer entries.  They are now in the

                     // backwards section.

                     p->numEntries--;

                     beforePool = false;

                 } else {

                     JS_ASSERT(beforePool);

                     // align the pool offset to the alignment of this pool

                     // it already only aligns when the pool has data in it, but we want to not

                     // align when all entries will end up in the backwards half of the pool

                     poolOffset = p->align(poolOffset);

                     IonSpew(IonSpew_Pools, "[%d] Entry %d in pool %d is before the pool.", id, idx, poolIdx);

                     // Everything here is known, we can safely do the necessary substitutions

                     Inst * inst = this->getInst(*iter);

                     // We need to manually compute the offset, including a possible bias.

                     int codeOffset = poolOffset - iter->getOffset();

                     // That is, patchConstantPoolLoad wants to be handed the address of the

                     // pool entry that is being loaded.  We need to do a non-trivial amount

                     // of math here, since the pool that we've made does not actually reside there

                     // in memory.

                     IonSpew(IonSpew_Pools, "[%d] Fixing offset to %d", id, codeOffset - magicAlign);

                     Asm::patchConstantPoolLoad(inst, (uint8_t*)inst + codeOffset - magicAlign);

                 }

             }

             // Some number of entries have been positively identified as being

             // in this section of the pool. Before processing the next pool,

             // update the offset from the beginning of the buffer

             poolOffset += p->numEntries * p->immSize;

         }

         poolOffset = footerSize;

         inBackref = true;

         for (int poolIdx = numPoolKinds-1; poolIdx >= 0; poolIdx--) {

             Pool *tmp = pools[poolIdx].other;

             if (tmp->checkFullBackref(poolOffset, perforation.getOffset())) {

                 // GNAAAH.  While we rotated elements into the back half, one of them filled up

                 // Now,  dumping the back half is necessary...

                 finishPool();

                 break;

             }

         }

     }

     void flushPool() {

         if (this->oom())

             return;

         IonSpew(IonSpew_Pools, "[%d] Requesting a pool flush", id);

         if (!inBackref)

             dumpPool();

         finishPool();

     }

     void patchBranch(Inst *i, int curpool, BufferOffset branch) {

         const Inst *ci = i;

         ptrdiff_t offset = Asm::getBranchOffset(ci);

         // If the offset is 0, then there is nothing to do.

         if (offset == 0)

             return;

         int destOffset = branch.getOffset() + offset;

         if (offset > 0) {

             while (curpool < numDumps && poolInfo[curpool].offset <= destOffset) {

                 offset += poolInfo[curpool].size;

                 curpool++;

             }

         } else {

             // Ignore the pool that comes next, since this is a backwards branch

             curpool--;

             while (curpool >= 0 && poolInfo[curpool].offset > destOffset) {

                 offset -= poolInfo[curpool].size;

                 curpool--;

             }

             // Can't assert anything here, since the first pool may be after the target.

         }

         Asm::retargetNearBranch(i, offset, false);

     }

     // Mark the next instruction as a valid guard.  This means we can place a pool here.

     void markGuard() {

         // If we are in a no pool zone then there is no point in dogearing

         // this branch as a place to go back to

         if (canNotPlacePool)

             return;

         // There is no point in trying to grab a new slot if we've already

         // found one and are in the process of filling it in.

         if (inBackref)

             return;

         perforate();

     }

     void enterNoPool() {

         if (!canNotPlacePool && !perforation.assigned()) {

             // Embarassing mode: The Assembler requests the start of a no pool section

             // and there have been no valid places that a pool could be dumped thusfar.

             // If a pool were to fill up before this no-pool section ends, we need to go back

             // in the stream and enter a pool guard after the fact.  This is feasable, but

             // for now, it is easier to just allocate a junk instruction, default it to a nop, and

             // finally, if the pool *is* needed, patch the nop to  apool guard.

             // What the assembler requests:

             // #request no-pool zone

             // push pc

             // blx r12

             // #end no-pool zone

             // however, if we would need to insert a pool, and there is no perforation point...

             // so, actual generated code:

             // b next; <= perforation point

             // next:

             // #beginning of no pool zone

             // push pc

             // blx r12

             BufferOffset branch = this->nextOffset();

             this->markNextAsBranch();

             this->putBlob(guardSize, nullptr);

             BufferOffset afterPool = this->nextOffset();

             Asm::writePoolGuard(branch, this->getInst(branch), afterPool);

             markGuard();

             if (perforatedNode != nullptr)

                 perforatedNode->isNatural = false;

         }

         canNotPlacePool++;

     }

     void leaveNoPool() {

         canNotPlacePool--;

     }

     int size() const {

         return uncheckedSize();

     }

     Pool *getPool(int idx) {

         return &pools[idx];

     }

     void markNextAsBranch() {

         // If the previous thing inserted was the last instruction of

         // the node, then whoops, we want to mark the first instruction of

         // the next node.

         this->ensureSpace(InstBaseSize);

         JS_ASSERT(*this->getTail() != nullptr);

         (*this->getTail())->markNextAsBranch();

     }

     bool isNextBranch() {

         JS_ASSERT(*this->getTail() != nullptr);

         return (*this->getTail())->isNextBranch();

     }

     int uncheckedSize() const {

         PoolInfo pi = getPoolData();

         int codeEnd = this->nextOffset().getOffset();

         return (codeEnd - pi.offset) + pi.finalPos;

     }

     ptrdiff_t curDumpsite;

     void resetCounter() {

         curDumpsite = 0;

     }

     ptrdiff_t poolSizeBefore(ptrdiff_t offset) const {

         int cur = 0;

         while(cur < numDumps && poolInfo[cur].offset <= offset)

             cur++;

         // poolInfo[curDumpsite] is now larger than the offset

         // either this is the first one, or the previous is the last one we care about

         if (cur == 0)

             return 0;

         return poolInfo[cur-1].finalPos - poolInfo[cur-1].offset;

     }

   private:

     void getPEPool(PoolEntry pe, Pool **retP, int32_t * retOffset, int32_t *poolNum) const {

         int poolKind = pe.poolKind();

         Pool *p = nullptr;

         uint32_t offset = pe.offset() * pools[poolKind].immSize;

         int idx;

         for (idx = 0; idx < numDumps; idx++) {

             p = &poolInfo[idx].slice->data[poolKind];

             if (p->getPoolSize() > offset)

                 break;

             offset -= p->getPoolSize();

             p = p->other;

             if (p->getPoolSize() > offset)

                 break;

             offset -= p->getPoolSize();

             p = nullptr;

         }

         if (poolNum != nullptr)

             *poolNum = idx;

         // If this offset is contained in any finished pool, forward or backwards, p now

         // points to that pool, if it is not in any pool (should be in the currently building pool)

         // then p is nullptr.

         if (p == nullptr) {

             p = &pools[poolKind];

             if (offset >= p->getPoolSize()) {

                 p = p->other;

                 offset -= p->getPoolSize();

             }

         }

         JS_ASSERT(p != nullptr);

         JS_ASSERT(offset < p->getPoolSize());

         *retP = p;

         *retOffset = offset;

     }

     uint8_t *getPoolEntry(PoolEntry pe) {

         Pool *p;

         int32_t offset;

         getPEPool(pe, &p, &offset, nullptr);

         return &p->poolData[offset];

     }

     size_t getPoolEntrySize(PoolEntry pe) {

         int idx = pe.poolKind();

         return pools[idx].immSize;

     }

   public:

     uint32_t poolEntryOffset(PoolEntry pe) const {

         Pool *realPool;

         // offset is in bytes, not entries.

         int32_t offset;

         int32_t poolNum;

         getPEPool(pe, &realPool, &offset, &poolNum);

         PoolInfo *pi = &poolInfo[poolNum];

         Pool *poolGroup = pi->slice->data;

         uint32_t start = pi->finalPos - pi->size + headerSize;

         /// The order of the pools is:

         // A B C C_Rev B_Rev A_Rev, so in the initial pass,

         // go through the pools forwards, and in the second pass

         // go through them in reverse order.

         for (int idx = 0; idx < numPoolKinds; idx++) {

             if (&poolGroup[idx] == realPool) {

                 return start + offset;

             }

             start = poolGroup[idx].addPoolSize(start);

         }

         for (int idx = numPoolKinds-1; idx >= 0; idx--) {

             if (poolGroup[idx].other == realPool) {

                 return start + offset;

             }

             start = poolGroup[idx].other->addPoolSize(start);

         }

         MOZ_ASSUME_UNREACHABLE("Entry is not in a pool");

     }

     void writePoolEntry(PoolEntry pe, uint8_t *buff) {

         size_t size = getPoolEntrySize(pe);

         uint8_t *entry = getPoolEntry(pe);

         memcpy(entry, buff, size);

     }

     void readPoolEntry(PoolEntry pe, uint8_t *buff) {

         size_t size = getPoolEntrySize(pe);

         uint8_t *entry = getPoolEntry(pe);

         memcpy(buff, entry, size);

     }

 };

 } // ion

 } // js

 #endif /* jit_shared_IonAssemblerBufferWithConstantPools_h */