diff -r 000000000000 -r 6474c204b198 js/src/jit/LinearScan.cpp --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/js/src/jit/LinearScan.cpp Wed Dec 31 06:09:35 2014 +0100 @@ -0,0 +1,1444 @@ +/* -*- 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/. */ + +#include "jit/LinearScan.h" + +#include "mozilla/DebugOnly.h" + +#include "jit/BitSet.h" +#include "jit/IonSpewer.h" + +using namespace js; +using namespace js::jit; + +using mozilla::DebugOnly; + +/* + * Merge virtual register intervals into the UnhandledQueue, taking advantage + * of their nearly-sorted ordering. + */ +void +LinearScanAllocator::enqueueVirtualRegisterIntervals() +{ + // Cursor into the unhandled queue, iterating through start positions. + IntervalReverseIterator curr = unhandled.rbegin(); + + // Start position is non-monotonically increasing by virtual register number. + for (size_t i = 1; i < graph.numVirtualRegisters(); i++) { + LiveInterval *live = vregs[i].getInterval(0); + if (live->numRanges() > 0) { + setIntervalRequirement(live); + + // Iterate backward until the next highest class of start position. + for (; curr != unhandled.rend(); curr++) { + if (curr->start() > live->start()) + break; + } + + // Insert forward from the current position, thereby + // sorting by priority within the start class. + unhandled.enqueueForward(*curr, live); + } + } +} + +/* + * This function performs a preliminary allocation on the already-computed + * live intervals, storing the result in the allocation field of the intervals + * themselves. + * + * The algorithm is based on the one published in: + * + * Wimmer, Christian, and Hanspeter Mössenböck. "Optimized Interval Splitting + * in a Linear Scan Register Allocator." Proceedings of the First + * ACM/USENIX Conference on Virtual Execution Environments. Chicago, IL, + * USA, ACM. 2005. PDF. + * + * The algorithm proceeds over each interval in order of their start position. + * If a free register is available, the register that is free for the largest + * portion of the current interval is allocated. Otherwise, the interval + * with the farthest-away next use is spilled to make room for this one. In all + * cases, intervals which conflict either with other intervals or with + * use or definition constraints are split at the point of conflict to be + * assigned a compatible allocation later. + */ +bool +LinearScanAllocator::allocateRegisters() +{ + // The unhandled queue currently contains only spill intervals, in sorted + // order. Intervals for virtual registers exist in sorted order based on + // start position by vreg ID, but may have priorities that require them to + // be reordered when adding to the unhandled queue. + enqueueVirtualRegisterIntervals(); + unhandled.assertSorted(); + + // Add fixed intervals with ranges to fixed. + for (size_t i = 0; i < AnyRegister::Total; i++) { + if (fixedIntervals[i]->numRanges() > 0) + fixed.pushBack(fixedIntervals[i]); + } + + // Iterate through all intervals in ascending start order. + CodePosition prevPosition = CodePosition::MIN; + while ((current = unhandled.dequeue()) != nullptr) { + JS_ASSERT(current->getAllocation()->isUse()); + JS_ASSERT(current->numRanges() > 0); + + if (mir->shouldCancel("LSRA Allocate Registers (main loop)")) + return false; + + CodePosition position = current->start(); + const Requirement *req = current->requirement(); + const Requirement *hint = current->hint(); + + IonSpew(IonSpew_RegAlloc, "Processing %d = [%u, %u] (pri=%d)", + current->hasVreg() ? current->vreg() : 0, current->start().pos(), + current->end().pos(), current->requirement()->priority()); + + // Shift active intervals to the inactive or handled sets as appropriate + if (position != prevPosition) { + JS_ASSERT(position > prevPosition); + prevPosition = position; + + for (IntervalIterator i(active.begin()); i != active.end(); ) { + LiveInterval *it = *i; + JS_ASSERT(it->numRanges() > 0); + + if (it->end() <= position) { + i = active.removeAt(i); + finishInterval(it); + } else if (!it->covers(position)) { + i = active.removeAt(i); + inactive.pushBack(it); + } else { + i++; + } + } + + // Shift inactive intervals to the active or handled sets as appropriate + for (IntervalIterator i(inactive.begin()); i != inactive.end(); ) { + LiveInterval *it = *i; + JS_ASSERT(it->numRanges() > 0); + + if (it->end() <= position) { + i = inactive.removeAt(i); + finishInterval(it); + } else if (it->covers(position)) { + i = inactive.removeAt(i); + active.pushBack(it); + } else { + i++; + } + } + } + + // Sanity check all intervals in all sets + validateIntervals(); + + // If the interval has a hard requirement, grant it. + if (req->kind() == Requirement::FIXED) { + JS_ASSERT(!req->allocation().isRegister()); + if (!assign(req->allocation())) + return false; + continue; + } + + // If we don't really need this in a register, don't allocate one + if (req->kind() != Requirement::REGISTER && hint->kind() == Requirement::NONE) { + IonSpew(IonSpew_RegAlloc, " Eagerly spilling virtual register %d", + current->hasVreg() ? current->vreg() : 0); + if (!spill()) + return false; + continue; + } + + // Try to allocate a free register + IonSpew(IonSpew_RegAlloc, " Attempting free register allocation"); + CodePosition bestFreeUntil; + AnyRegister::Code bestCode = findBestFreeRegister(&bestFreeUntil); + if (bestCode != AnyRegister::Invalid) { + AnyRegister best = AnyRegister::FromCode(bestCode); + IonSpew(IonSpew_RegAlloc, " Decided best register was %s", best.name()); + + // Split when the register is next needed if necessary + if (bestFreeUntil < current->end()) { + if (!splitInterval(current, bestFreeUntil)) + return false; + } + if (!assign(LAllocation(best))) + return false; + + continue; + } + + IonSpew(IonSpew_RegAlloc, " Attempting blocked register allocation"); + + // If we absolutely need a register or our next use is closer than the + // selected blocking register then we spill the blocker. Otherwise, we + // spill the current interval. + CodePosition bestNextUsed; + bestCode = findBestBlockedRegister(&bestNextUsed); + if (bestCode != AnyRegister::Invalid && + (req->kind() == Requirement::REGISTER || hint->pos() < bestNextUsed)) + { + AnyRegister best = AnyRegister::FromCode(bestCode); + IonSpew(IonSpew_RegAlloc, " Decided best register was %s", best.name()); + + if (!splitBlockingIntervals(LAllocation(best))) + return false; + if (!assign(LAllocation(best))) + return false; + + continue; + } + + IonSpew(IonSpew_RegAlloc, " No registers available to spill"); + JS_ASSERT(req->kind() == Requirement::NONE); + + if (!spill()) + return false; + } + + validateAllocations(); + validateVirtualRegisters(); + + return true; +} + +/* + * This function iterates over control flow edges in the function and resolves + * conflicts wherein two predecessors of a block have different allocations + * for a virtual register than the block itself. It also turns phis into moves. + * + * The algorithm is based on the one published in "Linear Scan Register + * Allocation on SSA Form" by C. Wimmer et al., for which the full citation + * appears above. + */ +bool +LinearScanAllocator::resolveControlFlow() +{ + for (size_t i = 0; i < graph.numBlocks(); i++) { + if (mir->shouldCancel("LSRA Resolve Control Flow (main loop)")) + return false; + + LBlock *successor = graph.getBlock(i); + MBasicBlock *mSuccessor = successor->mir(); + if (mSuccessor->numPredecessors() < 1) + continue; + + // Resolve phis to moves + for (size_t j = 0; j < successor->numPhis(); j++) { + LPhi *phi = successor->getPhi(j); + JS_ASSERT(phi->numDefs() == 1); + LDefinition *def = phi->getDef(0); + LinearScanVirtualRegister *vreg = &vregs[def]; + LiveInterval *to = vreg->intervalFor(inputOf(successor->firstId())); + JS_ASSERT(to); + + for (size_t k = 0; k < mSuccessor->numPredecessors(); k++) { + LBlock *predecessor = mSuccessor->getPredecessor(k)->lir(); + JS_ASSERT(predecessor->mir()->numSuccessors() == 1); + + LAllocation *input = phi->getOperand(predecessor->mir()->positionInPhiSuccessor()); + LiveInterval *from = vregs[input].intervalFor(outputOf(predecessor->lastId())); + JS_ASSERT(from); + + if (!moveAtExit(predecessor, from, to, def->type())) + return false; + } + + if (vreg->mustSpillAtDefinition() && !to->isSpill()) { + // Make sure this phi is spilled at the loop header. + LMoveGroup *moves = successor->getEntryMoveGroup(alloc()); + if (!moves->add(to->getAllocation(), vregs[to->vreg()].canonicalSpill(), + def->type())) + return false; + } + } + + // Resolve split intervals with moves + BitSet *live = liveIn[mSuccessor->id()]; + + for (BitSet::Iterator liveRegId(*live); liveRegId; liveRegId++) { + LinearScanVirtualRegister *vreg = &vregs[*liveRegId]; + LiveInterval *to = vreg->intervalFor(inputOf(successor->firstId())); + JS_ASSERT(to); + + for (size_t j = 0; j < mSuccessor->numPredecessors(); j++) { + LBlock *predecessor = mSuccessor->getPredecessor(j)->lir(); + LiveInterval *from = vregs[*liveRegId].intervalFor(outputOf(predecessor->lastId())); + JS_ASSERT(from); + + if (*from->getAllocation() == *to->getAllocation()) + continue; + + // If this value is spilled at its definition, other stores + // are redundant. + if (vreg->mustSpillAtDefinition() && to->getAllocation()->isStackSlot()) { + JS_ASSERT(vreg->canonicalSpill()); + JS_ASSERT(*vreg->canonicalSpill() == *to->getAllocation()); + continue; + } + + if (mSuccessor->numPredecessors() > 1) { + JS_ASSERT(predecessor->mir()->numSuccessors() == 1); + if (!moveAtExit(predecessor, from, to, vreg->type())) + return false; + } else { + if (!moveAtEntry(successor, from, to, vreg->type())) + return false; + } + } + } + } + + return true; +} + +bool +LinearScanAllocator::moveInputAlloc(CodePosition pos, LAllocation *from, LAllocation *to, + LDefinition::Type type) +{ + if (*from == *to) + return true; + LMoveGroup *moves = getInputMoveGroup(pos); + return moves->add(from, to, type); +} + +static inline void +SetOsiPointUses(LiveInterval *interval, CodePosition defEnd, const LAllocation &allocation) +{ + // Moves are inserted after OsiPoint instructions. This function sets + // any OsiPoint uses of this interval to the allocation of the value + // before the move. + + JS_ASSERT(interval->index() == 0); + + for (UsePositionIterator usePos(interval->usesBegin()); + usePos != interval->usesEnd(); + usePos++) + { + if (usePos->pos > defEnd) + break; + *static_cast(usePos->use) = allocation; + } +} + +/* + * This function takes the allocations assigned to the live intervals and + * erases all virtual registers in the function with the allocations + * corresponding to the appropriate interval. + */ +bool +LinearScanAllocator::reifyAllocations() +{ + // Iterate over each interval, ensuring that definitions are visited before uses. + for (size_t j = 1; j < graph.numVirtualRegisters(); j++) { + LinearScanVirtualRegister *reg = &vregs[j]; + if (mir->shouldCancel("LSRA Reification (main loop)")) + return false; + + for (size_t k = 0; k < reg->numIntervals(); k++) { + LiveInterval *interval = reg->getInterval(k); + JS_ASSERT(reg == &vregs[interval->vreg()]); + if (!interval->numRanges()) + continue; + + UsePositionIterator usePos(interval->usesBegin()); + for (; usePos != interval->usesEnd(); usePos++) { + if (usePos->use->isFixedRegister()) { + LiveInterval *to = fixedIntervals[GetFixedRegister(reg->def(), usePos->use).code()]; + + *static_cast(usePos->use) = *to->getAllocation(); + if (!moveInput(usePos->pos, interval, to, reg->type())) + return false; + } else { + JS_ASSERT(UseCompatibleWith(usePos->use, *interval->getAllocation())); + *static_cast(usePos->use) = *interval->getAllocation(); + } + } + + // Erase the def of this interval if it's the first one + if (interval->index() == 0) + { + LDefinition *def = reg->def(); + LAllocation *spillFrom; + + // Insert the moves after any OsiPoint or Nop instructions + // following this one. See minimalDefEnd for more info. + CodePosition defEnd = minimalDefEnd(reg->ins()); + + if (def->policy() == LDefinition::PRESET && def->output()->isRegister()) { + AnyRegister fixedReg = def->output()->toRegister(); + LiveInterval *from = fixedIntervals[fixedReg.code()]; + + // If we insert the move after an OsiPoint that uses this vreg, + // it should use the fixed register instead. + SetOsiPointUses(interval, defEnd, LAllocation(fixedReg)); + + if (!moveAfter(defEnd, from, interval, def->type())) + return false; + spillFrom = from->getAllocation(); + } else { + if (def->policy() == LDefinition::MUST_REUSE_INPUT) { + LAllocation *inputAlloc = reg->ins()->getOperand(def->getReusedInput()); + LAllocation *origAlloc = LAllocation::New(alloc(), *inputAlloc); + + JS_ASSERT(!inputAlloc->isUse()); + + *inputAlloc = *interval->getAllocation(); + if (!moveInputAlloc(inputOf(reg->ins()), origAlloc, inputAlloc, def->type())) + return false; + } + + JS_ASSERT(DefinitionCompatibleWith(reg->ins(), def, *interval->getAllocation())); + def->setOutput(*interval->getAllocation()); + + spillFrom = interval->getAllocation(); + } + + if (reg->ins()->recoversInput()) { + LSnapshot *snapshot = reg->ins()->snapshot(); + for (size_t i = 0; i < snapshot->numEntries(); i++) { + LAllocation *entry = snapshot->getEntry(i); + if (entry->isUse() && entry->toUse()->policy() == LUse::RECOVERED_INPUT) + *entry = *def->output(); + } + } + + if (reg->mustSpillAtDefinition() && !reg->ins()->isPhi() && + (*reg->canonicalSpill() != *spillFrom)) + { + // If we move the spill after an OsiPoint, the OsiPoint should + // use the original location instead. + SetOsiPointUses(interval, defEnd, *spillFrom); + + // Insert a spill after this instruction (or after any OsiPoint + // or Nop instructions). Note that we explicitly ignore phis, + // which should have been handled in resolveControlFlow(). + LMoveGroup *moves = getMoveGroupAfter(defEnd); + if (!moves->add(spillFrom, reg->canonicalSpill(), def->type())) + return false; + } + } + else if (interval->start() > inputOf(insData[interval->start()].block()->firstId()) && + (!reg->canonicalSpill() || + (reg->canonicalSpill() == interval->getAllocation() && + !reg->mustSpillAtDefinition()) || + *reg->canonicalSpill() != *interval->getAllocation())) + { + // If this virtual register has no canonical spill location, this + // is the first spill to that location, or this is a move to somewhere + // completely different, we have to emit a move for this interval. + // Don't do this if the interval starts at the first instruction of the + // block; this case should have been handled by resolveControlFlow(). + // + // If the interval starts at the output half of an instruction, we have to + // emit the move *after* this instruction, to prevent clobbering an input + // register. + LiveInterval *prevInterval = reg->getInterval(interval->index() - 1); + CodePosition start = interval->start(); + InstructionData *data = &insData[start]; + + JS_ASSERT(start == inputOf(data->ins()) || start == outputOf(data->ins())); + + if (start.subpos() == CodePosition::INPUT) { + if (!moveInput(inputOf(data->ins()), prevInterval, interval, reg->type())) + return false; + } else { + if (!moveAfter(outputOf(data->ins()), prevInterval, interval, reg->type())) + return false; + } + + // Mark this interval's spill position, if needed. + if (reg->canonicalSpill() == interval->getAllocation() && + !reg->mustSpillAtDefinition()) + { + reg->setSpillPosition(interval->start()); + } + } + + addLiveRegistersForInterval(reg, interval); + }} // Iteration over virtual register intervals. + + // Set the graph overall stack height + graph.setLocalSlotCount(stackSlotAllocator.stackHeight()); + + return true; +} + +inline bool +LinearScanAllocator::isSpilledAt(LiveInterval *interval, CodePosition pos) +{ + LinearScanVirtualRegister *reg = &vregs[interval->vreg()]; + if (!reg->canonicalSpill() || !reg->canonicalSpill()->isStackSlot()) + return false; + + if (reg->mustSpillAtDefinition()) { + JS_ASSERT(reg->spillPosition() <= pos); + return true; + } + + return interval->getAllocation() == reg->canonicalSpill(); +} + +bool +LinearScanAllocator::populateSafepoints() +{ + size_t firstSafepoint = 0; + + for (uint32_t i = 0; i < vregs.numVirtualRegisters(); i++) { + LinearScanVirtualRegister *reg = &vregs[i]; + + if (!reg->def() || (!IsTraceable(reg) && !IsSlotsOrElements(reg) && !IsNunbox(reg))) + continue; + + firstSafepoint = findFirstSafepoint(reg->getInterval(0), firstSafepoint); + if (firstSafepoint >= graph.numSafepoints()) + break; + + // Find the furthest endpoint. + size_t lastInterval = reg->numIntervals() - 1; + CodePosition end = reg->getInterval(lastInterval)->end(); + + for (size_t j = firstSafepoint; j < graph.numSafepoints(); j++) { + LInstruction *ins = graph.getSafepoint(j); + + // Stop processing safepoints if we know we're out of this virtual + // register's range. + if (end < inputOf(ins)) + break; + + // Include temps but not instruction outputs. Also make sure MUST_REUSE_INPUT + // is not used with gcthings or nunboxes, or we would have to add the input reg + // to this safepoint. + if (ins == reg->ins() && !reg->isTemp()) { + DebugOnly def = reg->def(); + JS_ASSERT_IF(def->policy() == LDefinition::MUST_REUSE_INPUT, + def->type() == LDefinition::GENERAL || + def->type() == LDefinition::INT32 || + def->type() == LDefinition::FLOAT32 || + def->type() == LDefinition::DOUBLE); + continue; + } + + LSafepoint *safepoint = ins->safepoint(); + + if (IsSlotsOrElements(reg)) { + LiveInterval *interval = reg->intervalFor(inputOf(ins)); + if (!interval) + continue; + + LAllocation *a = interval->getAllocation(); + if (a->isGeneralReg() && !ins->isCall()) + safepoint->addSlotsOrElementsRegister(a->toGeneralReg()->reg()); + + if (isSpilledAt(interval, inputOf(ins))) { + if (!safepoint->addSlotsOrElementsSlot(reg->canonicalSpillSlot())) + return false; + } + } else if (!IsNunbox(reg)) { + JS_ASSERT(IsTraceable(reg)); + + LiveInterval *interval = reg->intervalFor(inputOf(ins)); + if (!interval) + continue; + + LAllocation *a = interval->getAllocation(); + if (a->isGeneralReg() && !ins->isCall()) { +#ifdef JS_PUNBOX64 + if (reg->type() == LDefinition::BOX) { + safepoint->addValueRegister(a->toGeneralReg()->reg()); + } else +#endif + { + safepoint->addGcRegister(a->toGeneralReg()->reg()); + } + } + + if (isSpilledAt(interval, inputOf(ins))) { +#ifdef JS_PUNBOX64 + if (reg->type() == LDefinition::BOX) { + if (!safepoint->addValueSlot(reg->canonicalSpillSlot())) + return false; + } else +#endif + { + if (!safepoint->addGcSlot(reg->canonicalSpillSlot())) + return false; + } + } +#ifdef JS_NUNBOX32 + } else { + LinearScanVirtualRegister *other = otherHalfOfNunbox(reg); + LinearScanVirtualRegister *type = (reg->type() == LDefinition::TYPE) ? reg : other; + LinearScanVirtualRegister *payload = (reg->type() == LDefinition::PAYLOAD) ? reg : other; + LiveInterval *typeInterval = type->intervalFor(inputOf(ins)); + LiveInterval *payloadInterval = payload->intervalFor(inputOf(ins)); + + if (!typeInterval && !payloadInterval) + continue; + + LAllocation *typeAlloc = typeInterval->getAllocation(); + LAllocation *payloadAlloc = payloadInterval->getAllocation(); + + // If the payload is an argument, we'll scan that explicitly as + // part of the frame. It is therefore safe to not add any + // safepoint entry, as long as the vreg does not have a stack + // slot as canonical spill slot. + if (payloadAlloc->isArgument() && + (!payload->canonicalSpill() || payload->canonicalSpill() == payloadAlloc)) + { + continue; + } + + if (isSpilledAt(typeInterval, inputOf(ins)) && + isSpilledAt(payloadInterval, inputOf(ins))) + { + // These two components of the Value are spilled + // contiguously, so simply keep track of the base slot. + uint32_t payloadSlot = payload->canonicalSpillSlot(); + uint32_t slot = BaseOfNunboxSlot(LDefinition::PAYLOAD, payloadSlot); + if (!safepoint->addValueSlot(slot)) + return false; + } + + if (!ins->isCall() && + (!isSpilledAt(typeInterval, inputOf(ins)) || payloadAlloc->isGeneralReg())) + { + // Either the payload is on the stack but the type is + // in a register, or the payload is in a register. In + // both cases, we don't have a contiguous spill so we + // add a torn entry. + if (!safepoint->addNunboxParts(*typeAlloc, *payloadAlloc)) + return false; + + // If the nunbox is stored in multiple places, we need to + // trace all of them to allow the GC to relocate objects. + if (payloadAlloc->isGeneralReg() && isSpilledAt(payloadInterval, inputOf(ins))) { + if (!safepoint->addNunboxParts(*typeAlloc, *payload->canonicalSpill())) + return false; + } + } +#endif + } + } + +#ifdef JS_NUNBOX32 + if (IsNunbox(reg)) { + // Skip past the next half of this nunbox so we don't track the + // same slot twice. + JS_ASSERT(&vregs[reg->def()->virtualRegister() + 1] == otherHalfOfNunbox(reg)); + i++; + } +#endif + } + + return true; +} + +/* + * Split the given interval at the given position, and add the created + * interval to the unhandled queue. + */ +bool +LinearScanAllocator::splitInterval(LiveInterval *interval, CodePosition pos) +{ + // Make sure we're actually splitting this interval, not some other + // interval in the same virtual register. + JS_ASSERT(interval->start() < pos && pos < interval->end()); + + LinearScanVirtualRegister *reg = &vregs[interval->vreg()]; + + // "Bogus" intervals cannot be split. + JS_ASSERT(reg); + + // Do the split. + LiveInterval *newInterval = LiveInterval::New(alloc(), interval->vreg(), interval->index() + 1); + if (!interval->splitFrom(pos, newInterval)) + return false; + + JS_ASSERT(interval->numRanges() > 0); + JS_ASSERT(newInterval->numRanges() > 0); + + if (!reg->addInterval(newInterval)) + return false; + + IonSpew(IonSpew_RegAlloc, " Split interval to %u = [%u, %u]/[%u, %u]", + interval->vreg(), interval->start().pos(), + interval->end().pos(), newInterval->start().pos(), + newInterval->end().pos()); + + // We always want to enqueue the resulting split. We always split + // forward, and we never want to handle something forward of our + // current position. + setIntervalRequirement(newInterval); + + // splitInterval() is usually called to split the node that has just been + // popped from the unhandled queue. Therefore the split will likely be + // closer to the lower start positions in the queue. + unhandled.enqueueBackward(newInterval); + + return true; +} + +bool +LinearScanAllocator::splitBlockingIntervals(LAllocation allocation) +{ + JS_ASSERT(allocation.isRegister()); + + // Split current before the next fixed use. + LiveInterval *fixed = fixedIntervals[allocation.toRegister().code()]; + if (fixed->numRanges() > 0) { + CodePosition fixedPos = current->intersect(fixed); + if (fixedPos != CodePosition::MIN) { + JS_ASSERT(fixedPos > current->start()); + JS_ASSERT(fixedPos < current->end()); + if (!splitInterval(current, fixedPos)) + return false; + } + } + + // Split the blocking interval if it exists. + for (IntervalIterator i(active.begin()); i != active.end(); i++) { + if (i->getAllocation()->isRegister() && *i->getAllocation() == allocation) { + IonSpew(IonSpew_RegAlloc, " Splitting active interval %u = [%u, %u]", + vregs[i->vreg()].ins()->id(), i->start().pos(), i->end().pos()); + + JS_ASSERT(i->start() != current->start()); + JS_ASSERT(i->covers(current->start())); + JS_ASSERT(i->start() != current->start()); + + if (!splitInterval(*i, current->start())) + return false; + + LiveInterval *it = *i; + active.removeAt(i); + finishInterval(it); + break; + } + } + + // Split any inactive intervals at the next live point. + for (IntervalIterator i(inactive.begin()); i != inactive.end(); ) { + if (i->getAllocation()->isRegister() && *i->getAllocation() == allocation) { + IonSpew(IonSpew_RegAlloc, " Splitting inactive interval %u = [%u, %u]", + vregs[i->vreg()].ins()->id(), i->start().pos(), i->end().pos()); + + LiveInterval *it = *i; + CodePosition nextActive = it->nextCoveredAfter(current->start()); + JS_ASSERT(nextActive != CodePosition::MIN); + + if (!splitInterval(it, nextActive)) + return false; + + i = inactive.removeAt(i); + finishInterval(it); + } else { + i++; + } + } + + return true; +} + +/* + * Assign the current interval the given allocation, splitting conflicting + * intervals as necessary to make the allocation stick. + */ +bool +LinearScanAllocator::assign(LAllocation allocation) +{ + if (allocation.isRegister()) + IonSpew(IonSpew_RegAlloc, "Assigning register %s", allocation.toRegister().name()); + current->setAllocation(allocation); + + // Split this interval at the next incompatible one + LinearScanVirtualRegister *reg = &vregs[current->vreg()]; + if (reg) { + CodePosition splitPos = current->firstIncompatibleUse(allocation); + if (splitPos != CodePosition::MAX) { + // Split before the incompatible use. This ensures the use position is + // part of the second half of the interval and guarantees we never split + // at the end (zero-length intervals are invalid). + splitPos = splitPos.previous(); + JS_ASSERT (splitPos < current->end()); + if (!splitInterval(current, splitPos)) + return false; + } + } + + bool useAsCanonicalSpillSlot = allocation.isMemory(); + // Only canonically spill argument values when frame arguments are not + // modified in the body. + if (mir->modifiesFrameArguments()) + useAsCanonicalSpillSlot = allocation.isStackSlot(); + + if (reg && useAsCanonicalSpillSlot) { + if (reg->canonicalSpill()) { + JS_ASSERT(allocation == *reg->canonicalSpill()); + + // This interval is spilled more than once, so just always spill + // it at its definition. + reg->setSpillAtDefinition(outputOf(reg->ins())); + } else { + reg->setCanonicalSpill(current->getAllocation()); + + // If this spill is inside a loop, and the definition is outside + // the loop, instead move the spill to outside the loop. + InstructionData *other = &insData[current->start()]; + uint32_t loopDepthAtDef = reg->block()->mir()->loopDepth(); + uint32_t loopDepthAtSpill = other->block()->mir()->loopDepth(); + if (loopDepthAtSpill > loopDepthAtDef) + reg->setSpillAtDefinition(outputOf(reg->ins())); + } + } + + active.pushBack(current); + + return true; +} + +uint32_t +LinearScanAllocator::allocateSlotFor(const LiveInterval *interval) +{ + LinearScanVirtualRegister *reg = &vregs[interval->vreg()]; + + SlotList *freed; + if (reg->type() == LDefinition::DOUBLE) + freed = &finishedDoubleSlots_; +#if JS_BITS_PER_WORD == 64 + else if (reg->type() == LDefinition::GENERAL || + reg->type() == LDefinition::OBJECT || + reg->type() == LDefinition::SLOTS) + freed = &finishedDoubleSlots_; +#endif +#ifdef JS_PUNBOX64 + else if (reg->type() == LDefinition::BOX) + freed = &finishedDoubleSlots_; +#endif +#ifdef JS_NUNBOX32 + else if (IsNunbox(reg)) + freed = &finishedNunboxSlots_; +#endif + else + freed = &finishedSlots_; + + if (!freed->empty()) { + LiveInterval *maybeDead = freed->back(); + if (maybeDead->end() < reg->getInterval(0)->start()) { + // This spill slot is dead before the start of the interval trying + // to reuse the slot, so reuse is safe. Otherwise, we could + // encounter a situation where a stack slot is allocated and freed + // inside a loop, but the same allocation is then used to hold a + // loop-carried value. + // + // Note that we don't reuse the dead slot if its interval ends right + // before the current interval, to avoid conflicting slot -> reg and + // reg -> slot moves in the same movegroup. + freed->popBack(); + LinearScanVirtualRegister *dead = &vregs[maybeDead->vreg()]; +#ifdef JS_NUNBOX32 + if (IsNunbox(dead)) + return BaseOfNunboxSlot(dead->type(), dead->canonicalSpillSlot()); +#endif + return dead->canonicalSpillSlot(); + } + } + + return stackSlotAllocator.allocateSlot(reg->type()); +} + +bool +LinearScanAllocator::spill() +{ + IonSpew(IonSpew_RegAlloc, " Decided to spill current interval"); + + // We can't spill bogus intervals + JS_ASSERT(current->hasVreg()); + + LinearScanVirtualRegister *reg = &vregs[current->vreg()]; + + if (reg->canonicalSpill()) { + IonSpew(IonSpew_RegAlloc, " Allocating canonical spill location"); + + return assign(*reg->canonicalSpill()); + } + + uint32_t stackSlot; +#if defined JS_NUNBOX32 + if (IsNunbox(reg)) { + LinearScanVirtualRegister *other = otherHalfOfNunbox(reg); + + if (other->canonicalSpill()) { + // The other half of this nunbox already has a spill slot. To + // ensure the Value is spilled contiguously, use the other half (it + // was allocated double-wide). + JS_ASSERT(other->canonicalSpill()->isStackSlot()); + stackSlot = BaseOfNunboxSlot(other->type(), other->canonicalSpillSlot()); + } else { + // No canonical spill location exists for this nunbox yet. Allocate + // one. + stackSlot = allocateSlotFor(current); + } + stackSlot -= OffsetOfNunboxSlot(reg->type()); + } else +#endif + { + stackSlot = allocateSlotFor(current); + } + JS_ASSERT(stackSlot <= stackSlotAllocator.stackHeight()); + + return assign(LStackSlot(stackSlot)); +} + +void +LinearScanAllocator::freeAllocation(LiveInterval *interval, LAllocation *alloc) +{ + LinearScanVirtualRegister *mine = &vregs[interval->vreg()]; + if (!IsNunbox(mine)) { + if (alloc->isStackSlot()) { + if (mine->type() == LDefinition::DOUBLE) + finishedDoubleSlots_.append(interval); +#if JS_BITS_PER_WORD == 64 + else if (mine->type() == LDefinition::GENERAL || + mine->type() == LDefinition::OBJECT || + mine->type() == LDefinition::SLOTS) + finishedDoubleSlots_.append(interval); +#endif +#ifdef JS_PUNBOX64 + else if (mine->type() == LDefinition::BOX) + finishedDoubleSlots_.append(interval); +#endif + else + finishedSlots_.append(interval); + } + return; + } + +#ifdef JS_NUNBOX32 + // Special handling for nunboxes. We can only free the stack slot once we + // know both intervals have been finished. + LinearScanVirtualRegister *other = otherHalfOfNunbox(mine); + if (other->finished()) { + if (!mine->canonicalSpill() && !other->canonicalSpill()) + return; + + JS_ASSERT_IF(mine->canonicalSpill() && other->canonicalSpill(), + mine->canonicalSpill()->isStackSlot() == other->canonicalSpill()->isStackSlot()); + + LinearScanVirtualRegister *candidate = mine->canonicalSpill() ? mine : other; + if (!candidate->canonicalSpill()->isStackSlot()) + return; + + finishedNunboxSlots_.append(candidate->lastInterval()); + } +#endif +} + +void +LinearScanAllocator::finishInterval(LiveInterval *interval) +{ + LAllocation *alloc = interval->getAllocation(); + JS_ASSERT(!alloc->isUse()); + + // Toss out the bogus interval now that it's run its course + if (!interval->hasVreg()) + return; + + LinearScanVirtualRegister *reg = &vregs[interval->vreg()]; + + // All spills should be equal to the canonical spill location. + JS_ASSERT_IF(alloc->isStackSlot(), *alloc == *reg->canonicalSpill()); + + bool lastInterval = interval->index() == (reg->numIntervals() - 1); + if (lastInterval) { + freeAllocation(interval, alloc); + reg->setFinished(); + } + + handled.pushBack(interval); +} + +/* + * This function locates a register which may be assigned by the register + * and is not assigned to any active interval. The register which is free + * for the longest period of time is then returned. + */ +AnyRegister::Code +LinearScanAllocator::findBestFreeRegister(CodePosition *freeUntil) +{ + IonSpew(IonSpew_RegAlloc, " Computing freeUntilPos"); + + // Compute free-until positions for all registers + CodePosition freeUntilPos[AnyRegister::Total]; + bool needFloat = vregs[current->vreg()].isFloatReg(); + for (RegisterSet regs(allRegisters_); !regs.empty(needFloat); ) { + AnyRegister reg = regs.takeAny(needFloat); + freeUntilPos[reg.code()] = CodePosition::MAX; + } + for (IntervalIterator i(active.begin()); i != active.end(); i++) { + LAllocation *alloc = i->getAllocation(); + if (alloc->isRegister(needFloat)) { + AnyRegister reg = alloc->toRegister(); + IonSpew(IonSpew_RegAlloc, " Register %s not free", reg.name()); + freeUntilPos[reg.code()] = CodePosition::MIN; + } + } + for (IntervalIterator i(inactive.begin()); i != inactive.end(); i++) { + LAllocation *alloc = i->getAllocation(); + if (alloc->isRegister(needFloat)) { + AnyRegister reg = alloc->toRegister(); + CodePosition pos = current->intersect(*i); + if (pos != CodePosition::MIN && pos < freeUntilPos[reg.code()]) { + freeUntilPos[reg.code()] = pos; + IonSpew(IonSpew_RegAlloc, " Register %s free until %u", reg.name(), pos.pos()); + } + } + } + + CodePosition fixedPos = fixedIntervalsUnion->intersect(current); + if (fixedPos != CodePosition::MIN) { + for (IntervalIterator i(fixed.begin()); i != fixed.end(); i++) { + AnyRegister reg = i->getAllocation()->toRegister(); + if (freeUntilPos[reg.code()] != CodePosition::MIN) { + CodePosition pos = current->intersect(*i); + if (pos != CodePosition::MIN && pos < freeUntilPos[reg.code()]) { + freeUntilPos[reg.code()] = (pos == current->start()) ? CodePosition::MIN : pos; + IonSpew(IonSpew_RegAlloc, " Register %s free until %u", reg.name(), pos.pos()); + } + } + } + } + + AnyRegister::Code bestCode = AnyRegister::Invalid; + if (current->index()) { + // As an optimization, use the allocation from the previous interval if + // it is available. + LiveInterval *previous = vregs[current->vreg()].getInterval(current->index() - 1); + LAllocation *alloc = previous->getAllocation(); + if (alloc->isRegister(needFloat)) { + AnyRegister prevReg = alloc->toRegister(); + if (freeUntilPos[prevReg.code()] != CodePosition::MIN) + bestCode = prevReg.code(); + } + } + + // Assign the register suggested by the hint if it's free. + const Requirement *hint = current->hint(); + if (hint->kind() == Requirement::FIXED && hint->allocation().isRegister()) { + AnyRegister hintReg = hint->allocation().toRegister(); + if (freeUntilPos[hintReg.code()] > hint->pos()) + bestCode = hintReg.code(); + } else if (hint->kind() == Requirement::SAME_AS_OTHER) { + LiveInterval *other = vregs[hint->virtualRegister()].intervalFor(hint->pos()); + if (other && other->getAllocation()->isRegister()) { + AnyRegister hintReg = other->getAllocation()->toRegister(); + if (freeUntilPos[hintReg.code()] > hint->pos()) + bestCode = hintReg.code(); + } + } + + if (bestCode == AnyRegister::Invalid) { + // If all else fails, search freeUntilPos for largest value + for (uint32_t i = 0; i < AnyRegister::Total; i++) { + if (freeUntilPos[i] == CodePosition::MIN) + continue; + if (bestCode == AnyRegister::Invalid || freeUntilPos[i] > freeUntilPos[bestCode]) + bestCode = AnyRegister::Code(i); + } + } + + if (bestCode != AnyRegister::Invalid) + *freeUntil = freeUntilPos[bestCode]; + return bestCode; +} + +/* + * This function locates a register which is assigned to an active interval, + * and returns the one with the furthest away next use. As a side effect, + * the nextUsePos array is updated with the next use position of all active + * intervals for use elsewhere in the algorithm. + */ +AnyRegister::Code +LinearScanAllocator::findBestBlockedRegister(CodePosition *nextUsed) +{ + IonSpew(IonSpew_RegAlloc, " Computing nextUsePos"); + + // Compute next-used positions for all registers + CodePosition nextUsePos[AnyRegister::Total]; + bool needFloat = vregs[current->vreg()].isFloatReg(); + for (RegisterSet regs(allRegisters_); !regs.empty(needFloat); ) { + AnyRegister reg = regs.takeAny(needFloat); + nextUsePos[reg.code()] = CodePosition::MAX; + } + for (IntervalIterator i(active.begin()); i != active.end(); i++) { + LAllocation *alloc = i->getAllocation(); + if (alloc->isRegister(needFloat)) { + AnyRegister reg = alloc->toRegister(); + if (i->start() == current->start()) { + nextUsePos[reg.code()] = CodePosition::MIN; + IonSpew(IonSpew_RegAlloc, " Disqualifying %s due to recency", reg.name()); + } else if (nextUsePos[reg.code()] != CodePosition::MIN) { + nextUsePos[reg.code()] = i->nextUsePosAfter(current->start()); + IonSpew(IonSpew_RegAlloc, " Register %s next used %u", reg.name(), + nextUsePos[reg.code()].pos()); + } + } + } + for (IntervalIterator i(inactive.begin()); i != inactive.end(); i++) { + LAllocation *alloc = i->getAllocation(); + if (alloc->isRegister(needFloat)) { + AnyRegister reg = alloc->toRegister(); + CodePosition pos = i->nextUsePosAfter(current->start()); + if (pos < nextUsePos[reg.code()]) { + nextUsePos[reg.code()] = pos; + IonSpew(IonSpew_RegAlloc, " Register %s next used %u", reg.name(), pos.pos()); + } + } + } + + CodePosition fixedPos = fixedIntervalsUnion->intersect(current); + if (fixedPos != CodePosition::MIN) { + for (IntervalIterator i(fixed.begin()); i != fixed.end(); i++) { + AnyRegister reg = i->getAllocation()->toRegister(); + if (nextUsePos[reg.code()] != CodePosition::MIN) { + CodePosition pos = i->intersect(current); + if (pos != CodePosition::MIN && pos < nextUsePos[reg.code()]) { + nextUsePos[reg.code()] = (pos == current->start()) ? CodePosition::MIN : pos; + IonSpew(IonSpew_RegAlloc, " Register %s next used %u (fixed)", reg.name(), pos.pos()); + } + } + } + } + + // Search nextUsePos for largest value + AnyRegister::Code bestCode = AnyRegister::Invalid; + for (size_t i = 0; i < AnyRegister::Total; i++) { + if (nextUsePos[i] == CodePosition::MIN) + continue; + if (bestCode == AnyRegister::Invalid || nextUsePos[i] > nextUsePos[bestCode]) + bestCode = AnyRegister::Code(i); + } + + if (bestCode != AnyRegister::Invalid) + *nextUsed = nextUsePos[bestCode]; + return bestCode; +} + +/* + * Two intervals can coexist if any of the following conditions is met: + * + * - The intervals do not intersect. + * - The intervals have different allocations. + * - The intervals have the same allocation, but the allocation may be + * shared. + * + * Intuitively, it is a bug if any allocated intervals exist which can not + * coexist. + */ +bool +LinearScanAllocator::canCoexist(LiveInterval *a, LiveInterval *b) +{ + LAllocation *aa = a->getAllocation(); + LAllocation *ba = b->getAllocation(); + if (aa->isRegister() && ba->isRegister() && aa->toRegister() == ba->toRegister()) + return a->intersect(b) == CodePosition::MIN; + return true; +} + +#ifdef DEBUG +/* + * Ensure intervals appear in exactly the appropriate one of {active,inactive, + * handled}, and that active and inactive intervals do not conflict. Handled + * intervals are checked for conflicts in validateAllocations for performance + * reasons. + */ +void +LinearScanAllocator::validateIntervals() +{ + if (!js_JitOptions.checkGraphConsistency) + return; + + for (IntervalIterator i(active.begin()); i != active.end(); i++) { + JS_ASSERT(i->numRanges() > 0); + JS_ASSERT(i->covers(current->start())); + + for (IntervalIterator j(active.begin()); j != i; j++) + JS_ASSERT(canCoexist(*i, *j)); + } + + for (IntervalIterator i(inactive.begin()); i != inactive.end(); i++) { + JS_ASSERT(i->numRanges() > 0); + JS_ASSERT(i->end() >= current->start()); + JS_ASSERT(!i->covers(current->start())); + + for (IntervalIterator j(active.begin()); j != active.end(); j++) { + JS_ASSERT(*i != *j); + JS_ASSERT(canCoexist(*i, *j)); + } + for (IntervalIterator j(inactive.begin()); j != i; j++) + JS_ASSERT(canCoexist(*i, *j)); + } + + for (IntervalIterator i(handled.begin()); i != handled.end(); i++) { + JS_ASSERT(!i->getAllocation()->isUse()); + JS_ASSERT(i->numRanges() > 0); + if (i->getAllocation()->isRegister()) { + JS_ASSERT(i->end() <= current->start()); + JS_ASSERT(!i->covers(current->start())); + } + + for (IntervalIterator j(active.begin()); j != active.end(); j++) + JS_ASSERT(*i != *j); + for (IntervalIterator j(inactive.begin()); j != inactive.end(); j++) + JS_ASSERT(*i != *j); + } +} + +/* + * This function performs a nice, expensive check that all intervals + * in the function can coexist with every other interval. + */ +void +LinearScanAllocator::validateAllocations() +{ + if (!js_JitOptions.checkGraphConsistency) + return; + + for (IntervalIterator i(handled.begin()); i != handled.end(); i++) { + for (IntervalIterator j(handled.begin()); j != i; j++) { + JS_ASSERT(*i != *j); + JS_ASSERT(canCoexist(*i, *j)); + } + LinearScanVirtualRegister *reg = &vregs[i->vreg()]; + bool found = false; + for (size_t j = 0; j < reg->numIntervals(); j++) { + if (reg->getInterval(j) == *i) { + JS_ASSERT(j == i->index()); + found = true; + break; + } + } + JS_ASSERT(found); + } +} + +#endif // DEBUG + +bool +LinearScanAllocator::go() +{ + IonSpew(IonSpew_RegAlloc, "Beginning register allocation"); + + IonSpew(IonSpew_RegAlloc, "Beginning liveness analysis"); + if (!buildLivenessInfo()) + return false; + IonSpew(IonSpew_RegAlloc, "Liveness analysis complete"); + + if (mir->shouldCancel("LSRA Liveness")) + return false; + + IonSpew(IonSpew_RegAlloc, "Beginning preliminary register allocation"); + if (!allocateRegisters()) + return false; + IonSpew(IonSpew_RegAlloc, "Preliminary register allocation complete"); + + if (mir->shouldCancel("LSRA Preliminary Regalloc")) + return false; + + IonSpew(IonSpew_RegAlloc, "Beginning control flow resolution"); + if (!resolveControlFlow()) + return false; + IonSpew(IonSpew_RegAlloc, "Control flow resolution complete"); + + if (mir->shouldCancel("LSRA Control Flow")) + return false; + + IonSpew(IonSpew_RegAlloc, "Beginning register allocation reification"); + if (!reifyAllocations()) + return false; + IonSpew(IonSpew_RegAlloc, "Register allocation reification complete"); + + if (mir->shouldCancel("LSRA Reification")) + return false; + + IonSpew(IonSpew_RegAlloc, "Beginning safepoint population."); + if (!populateSafepoints()) + return false; + IonSpew(IonSpew_RegAlloc, "Safepoint population complete."); + + if (mir->shouldCancel("LSRA Safepoints")) + return false; + + IonSpew(IonSpew_RegAlloc, "Register allocation complete"); + + return true; +} + +void +LinearScanAllocator::setIntervalRequirement(LiveInterval *interval) +{ + JS_ASSERT(interval->requirement()->kind() == Requirement::NONE); + JS_ASSERT(interval->hint()->kind() == Requirement::NONE); + + // This function computes requirement by virtual register, other types of + // interval should have requirements set manually + LinearScanVirtualRegister *reg = &vregs[interval->vreg()]; + + if (interval->index() == 0) { + // The first interval is the definition, so deal with any definition + // constraints/hints + + if (reg->def()->policy() == LDefinition::PRESET) { + // Preset policies get a FIXED requirement or hint. + if (reg->def()->output()->isRegister()) + interval->setHint(Requirement(*reg->def()->output())); + else + interval->setRequirement(Requirement(*reg->def()->output())); + } else if (reg->def()->policy() == LDefinition::MUST_REUSE_INPUT) { + // Reuse policies get either a FIXED requirement or a SAME_AS hint. + LUse *use = reg->ins()->getOperand(reg->def()->getReusedInput())->toUse(); + interval->setRequirement(Requirement(Requirement::REGISTER)); + interval->setHint(Requirement(use->virtualRegister(), interval->start().previous())); + } else if (reg->ins()->isPhi()) { + // Phis don't have any requirements, but they should prefer + // their input allocations, so they get a SAME_AS hint of the + // first input + LUse *use = reg->ins()->getOperand(0)->toUse(); + LBlock *predecessor = reg->block()->mir()->getPredecessor(0)->lir(); + CodePosition predEnd = outputOf(predecessor->lastId()); + interval->setHint(Requirement(use->virtualRegister(), predEnd)); + } else { + // Non-phis get a REGISTER requirement + interval->setRequirement(Requirement(Requirement::REGISTER)); + } + } + + UsePosition *fixedOp = nullptr; + UsePosition *registerOp = nullptr; + + // Search uses at the start of the interval for requirements. + UsePositionIterator usePos(interval->usesBegin()); + for (; usePos != interval->usesEnd(); usePos++) { + if (interval->start().next() < usePos->pos) + break; + + LUse::Policy policy = usePos->use->policy(); + if (policy == LUse::FIXED) { + fixedOp = *usePos; + interval->setRequirement(Requirement(Requirement::REGISTER)); + break; + } else if (policy == LUse::REGISTER) { + // Register uses get a REGISTER requirement + interval->setRequirement(Requirement(Requirement::REGISTER)); + } + } + + // Search other uses for hints. If the virtual register already has a + // canonical spill location, we will eagerly spill this interval, so we + // don't have to search for hints. + if (!fixedOp && !vregs[interval->vreg()].canonicalSpill()) { + for (; usePos != interval->usesEnd(); usePos++) { + LUse::Policy policy = usePos->use->policy(); + if (policy == LUse::FIXED) { + fixedOp = *usePos; + break; + } else if (policy == LUse::REGISTER) { + if (!registerOp) + registerOp = *usePos; + } + } + } + + if (fixedOp) { + // Intervals with a fixed use now get a FIXED hint. + AnyRegister required = GetFixedRegister(reg->def(), fixedOp->use); + interval->setHint(Requirement(LAllocation(required), fixedOp->pos)); + } else if (registerOp) { + // Intervals with register uses get a REGISTER hint. We may have already + // assigned a SAME_AS hint, make sure we don't overwrite it with a weaker + // hint. + if (interval->hint()->kind() == Requirement::NONE) + interval->setHint(Requirement(Requirement::REGISTER, registerOp->pos)); + } +} + +/* + * Enqueue by iteration starting from the node with the lowest start position. + * + * If we assign registers to intervals in order of their start positions + * without regard to their requirements, we can end up in situations where + * intervals that do not require registers block intervals that must have + * registers from getting one. To avoid this, we ensure that intervals are + * ordered by position and priority so intervals with more stringent + * requirements are handled first. + */ +void +LinearScanAllocator::UnhandledQueue::enqueueBackward(LiveInterval *interval) +{ + IntervalReverseIterator i(rbegin()); + + for (; i != rend(); i++) { + if (i->start() > interval->start()) + break; + if (i->start() == interval->start() && + i->requirement()->priority() >= interval->requirement()->priority()) + { + break; + } + } + insertAfter(*i, interval); +} + +/* + * Enqueue by iteration from high start position to low start position, + * after a provided node. + */ +void +LinearScanAllocator::UnhandledQueue::enqueueForward(LiveInterval *after, LiveInterval *interval) +{ + IntervalIterator i(begin(after)); + i++; // Skip the initial node. + + for (; i != end(); i++) { + if (i->start() < interval->start()) + break; + if (i->start() == interval->start() && + i->requirement()->priority() < interval->requirement()->priority()) + { + break; + } + } + insertBefore(*i, interval); +} + +void +LinearScanAllocator::UnhandledQueue::assertSorted() +{ +#ifdef DEBUG + LiveInterval *prev = nullptr; + for (IntervalIterator i(begin()); i != end(); i++) { + if (prev) { + JS_ASSERT(prev->start() >= i->start()); + JS_ASSERT_IF(prev->start() == i->start(), + prev->requirement()->priority() >= i->requirement()->priority()); + } + prev = *i; + } +#endif +} + +LiveInterval * +LinearScanAllocator::UnhandledQueue::dequeue() +{ + if (rbegin() == rend()) + return nullptr; + + LiveInterval *result = *rbegin(); + remove(result); + return result; +}