The Tor Browser: js/src/jit/LinearScan.cpp@129ffea94266 (annotated)

js/src/jit/LinearScan.cpp@129ffea94266 (annotated)

js/src/jit/LinearScan.cpp

Sat, 03 Jan 2015 20:18:00 +0100

author: Michael Schloh von Bennewitz <michael@schloh.com>
date: Sat, 03 Jan 2015 20:18:00 +0100
branch: TOR_BUG_3246
changeset 7: 129ffea94266
permissions: -rw-r--r--

Conditionally enable double key logic according to:
private browsing mode or privacy.thirdparty.isolate preference and
implement in GetCookieStringCommon and FindCookie where it counts...
With some reservations of how to convince FindCookie users to test
condition and pass a nullptr when disabling double key logic.

 /* -*- 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<LAllocation *>(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<LAllocation *>(usePos->use) = *to->getAllocation();
                 if (!moveInput(usePos->pos, interval, to, reg->type()))
                     return false;
             } else {
                 JS_ASSERT(UseCompatibleWith(usePos->use, *interval->getAllocation()));
                 *static_cast<LAllocation *>(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<LDefinition*> 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;
 }

The Tor Browser / annotate

js/src/jit/LinearScan.cpp@129ffea94266 (annotated)

js/src/jit/LinearScan.cpp