The Tor Browser: js/src/jit/BacktrackingAllocator.cpp@6474c204b198 (annotated)

js/src/jit/BacktrackingAllocator.cpp@6474c204b198 (annotated)

js/src/jit/BacktrackingAllocator.cpp

Wed, 31 Dec 2014 06:09:35 +0100

author: Michael Schloh von Bennewitz <michael@schloh.com>
date: Wed, 31 Dec 2014 06:09:35 +0100
changeset 0: 6474c204b198
permissions: -rw-r--r--

Cloned upstream origin tor-browser at tor-browser-31.3.0esr-4.5-1-build1
revision ID fc1c9ff7c1b2defdbc039f12214767608f46423f for hacking purpose.

 /* -*- 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/BacktrackingAllocator.h"
 #include "jit/BitSet.h"
 using namespace js;
 using namespace js::jit;
 using mozilla::DebugOnly;
 bool
 BacktrackingAllocator::init()
 {
     RegisterSet remainingRegisters(allRegisters_);
     while (!remainingRegisters.empty(/* float = */ false)) {
         AnyRegister reg = AnyRegister(remainingRegisters.takeGeneral());
         registers[reg.code()].allocatable = true;
     }
     while (!remainingRegisters.empty(/* float = */ true)) {
         AnyRegister reg = AnyRegister(remainingRegisters.takeFloat());
         registers[reg.code()].allocatable = true;
     }
     LifoAlloc *lifoAlloc = mir->alloc().lifoAlloc();
     for (size_t i = 0; i < AnyRegister::Total; i++) {
         registers[i].reg = AnyRegister::FromCode(i);
         registers[i].allocations.setAllocator(lifoAlloc);
         LiveInterval *fixed = fixedIntervals[i];
         for (size_t j = 0; j < fixed->numRanges(); j++) {
             AllocatedRange range(fixed, fixed->getRange(j));
             if (!registers[i].allocations.insert(range))
                 return false;
         }
     }
     hotcode.setAllocator(lifoAlloc);
     // Partition the graph into hot and cold sections, for helping to make
     // splitting decisions. Since we don't have any profiling data this is a
     // crapshoot, so just mark the bodies of inner loops as hot and everything
     // else as cold.
     LiveInterval *hotcodeInterval = LiveInterval::New(alloc(), 0);
     LBlock *backedge = nullptr;
     for (size_t i = 0; i < graph.numBlocks(); i++) {
         LBlock *block = graph.getBlock(i);
         // If we see a loop header, mark the backedge so we know when we have
         // hit the end of the loop. Don't process the loop immediately, so that
         // if there is an inner loop we will ignore the outer backedge.
         if (block->mir()->isLoopHeader())
             backedge = block->mir()->backedge()->lir();
         if (block == backedge) {
             LBlock *header = block->mir()->loopHeaderOfBackedge()->lir();
             CodePosition from = inputOf(header->firstId());
             CodePosition to = outputOf(block->lastId()).next();
             if (!hotcodeInterval->addRange(from, to))
                 return false;
         }
     }
     for (size_t i = 0; i < hotcodeInterval->numRanges(); i++) {
         AllocatedRange range(hotcodeInterval, hotcodeInterval->getRange(i));
         if (!hotcode.insert(range))
             return false;
     }
     return true;
 }
 bool
 BacktrackingAllocator::go()
 {
     IonSpew(IonSpew_RegAlloc, "Beginning register allocation");
     IonSpew(IonSpew_RegAlloc, "Beginning liveness analysis");
     if (!buildLivenessInfo())
         return false;
     IonSpew(IonSpew_RegAlloc, "Liveness analysis complete");
     if (!init())
         return false;
     if (IonSpewEnabled(IonSpew_RegAlloc))
         dumpLiveness();
     if (!allocationQueue.reserve(graph.numVirtualRegisters() * 3 / 2))
         return false;
     if (!groupAndQueueRegisters())
         return false;
     if (IonSpewEnabled(IonSpew_RegAlloc))
         dumpRegisterGroups();
     // Allocate, spill and split register intervals until finished.
     while (!allocationQueue.empty()) {
         if (mir->shouldCancel("Backtracking Allocation"))
             return false;
         QueueItem item = allocationQueue.removeHighest();
         if (item.interval ? !processInterval(item.interval) : !processGroup(item.group))
             return false;
     }
     if (IonSpewEnabled(IonSpew_RegAlloc))
         dumpAllocations();
     return resolveControlFlow() && reifyAllocations() && populateSafepoints();
 }
 static bool
 LifetimesOverlap(BacktrackingVirtualRegister *reg0, BacktrackingVirtualRegister *reg1)
 {
     // Registers may have been eagerly split in two, see tryGroupReusedRegister.
     // In such cases, only consider the first interval.
     JS_ASSERT(reg0->numIntervals() <= 2 && reg1->numIntervals() <= 2);
     LiveInterval *interval0 = reg0->getInterval(0), *interval1 = reg1->getInterval(0);
     // Interval ranges are sorted in reverse order. The lifetimes overlap if
     // any of their ranges overlap.
     size_t index0 = 0, index1 = 0;
     while (index0 < interval0->numRanges() && index1 < interval1->numRanges()) {
         const LiveInterval::Range
             *range0 = interval0->getRange(index0),
             *range1 = interval1->getRange(index1);
         if (range0->from >= range1->to)
             index0++;
         else if (range1->from >= range0->to)
             index1++;
         else
             return true;
     }
     return false;
 }
 bool
 BacktrackingAllocator::canAddToGroup(VirtualRegisterGroup *group, BacktrackingVirtualRegister *reg)
 {
     for (size_t i = 0; i < group->registers.length(); i++) {
         if (LifetimesOverlap(reg, &vregs[group->registers[i]]))
             return false;
     }
     return true;
 }
 bool
 BacktrackingAllocator::tryGroupRegisters(uint32_t vreg0, uint32_t vreg1)
 {
     // See if reg0 and reg1 can be placed in the same group, following the
     // restrictions imposed by VirtualRegisterGroup and any other registers
     // already grouped with reg0 or reg1.
     BacktrackingVirtualRegister *reg0 = &vregs[vreg0], *reg1 = &vregs[vreg1];
     if (reg0->isFloatReg() != reg1->isFloatReg())
         return true;
     VirtualRegisterGroup *group0 = reg0->group(), *group1 = reg1->group();
     if (!group0 && group1)
         return tryGroupRegisters(vreg1, vreg0);
     if (group0) {
         if (group1) {
             if (group0 == group1) {
                 // The registers are already grouped together.
                 return true;
             }
             // Try to unify the two distinct groups.
             for (size_t i = 0; i < group1->registers.length(); i++) {
                 if (!canAddToGroup(group0, &vregs[group1->registers[i]]))
                     return true;
             }
             for (size_t i = 0; i < group1->registers.length(); i++) {
                 uint32_t vreg = group1->registers[i];
                 if (!group0->registers.append(vreg))
                     return false;
                 vregs[vreg].setGroup(group0);
             }
             return true;
         }
         if (!canAddToGroup(group0, reg1))
             return true;
         if (!group0->registers.append(vreg1))
             return false;
         reg1->setGroup(group0);
         return true;
     }
     if (LifetimesOverlap(reg0, reg1))
         return true;
     VirtualRegisterGroup *group = new(alloc()) VirtualRegisterGroup(alloc());
     if (!group->registers.append(vreg0) || !group->registers.append(vreg1))
         return false;
     reg0->setGroup(group);
     reg1->setGroup(group);
     return true;
 }
 bool
 BacktrackingAllocator::tryGroupReusedRegister(uint32_t def, uint32_t use)
 {
     BacktrackingVirtualRegister &reg = vregs[def], &usedReg = vregs[use];
     // reg is a vreg which reuses its input usedReg for its output physical
     // register. Try to group reg with usedReg if at all possible, as avoiding
     // copies before reg's instruction is crucial for the quality of the
     // generated code (MUST_REUSE_INPUT is used by all arithmetic instructions
     // on x86/x64).
     if (reg.intervalFor(inputOf(reg.ins()))) {
         JS_ASSERT(reg.isTemp());
         reg.setMustCopyInput();
         return true;
     }
     if (!usedReg.intervalFor(outputOf(reg.ins()))) {
         // The input is not live after the instruction, either in a safepoint
         // for the instruction or in subsequent code. The input and output
         // can thus be in the same group.
         return tryGroupRegisters(use, def);
     }
     // The input is live afterwards, either in future instructions or in a
     // safepoint for the reusing instruction. This is impossible to satisfy
     // without copying the input.
     //
     // It may or may not be better to split the interval at the point of the
     // definition, which may permit grouping. One case where it is definitely
     // better to split is if the input never has any register uses after the
     // instruction. Handle this splitting eagerly.
     if (usedReg.numIntervals() != 1 ||
         (usedReg.def()->isPreset() && !usedReg.def()->output()->isRegister())) {
         reg.setMustCopyInput();
         return true;
     }
     LiveInterval *interval = usedReg.getInterval(0);
     LBlock *block = insData[reg.ins()].block();
     // The input's lifetime must end within the same block as the definition,
     // otherwise it could live on in phis elsewhere.
     if (interval->end() > outputOf(block->lastId())) {
         reg.setMustCopyInput();
         return true;
     }
     for (UsePositionIterator iter = interval->usesBegin(); iter != interval->usesEnd(); iter++) {
         if (iter->pos <= inputOf(reg.ins()))
             continue;
         LUse *use = iter->use;
         if (FindReusingDefinition(insData[iter->pos].ins(), use)) {
             reg.setMustCopyInput();
             return true;
         }
         if (use->policy() != LUse::ANY && use->policy() != LUse::KEEPALIVE) {
             reg.setMustCopyInput();
             return true;
         }
     }
     LiveInterval *preInterval = LiveInterval::New(alloc(), interval->vreg(), 0);
     for (size_t i = 0; i < interval->numRanges(); i++) {
         const LiveInterval::Range *range = interval->getRange(i);
         JS_ASSERT(range->from <= inputOf(reg.ins()));
         CodePosition to = (range->to <= outputOf(reg.ins())) ? range->to : outputOf(reg.ins());
         if (!preInterval->addRange(range->from, to))
             return false;
     }
     LiveInterval *postInterval = LiveInterval::New(alloc(), interval->vreg(), 0);
     if (!postInterval->addRange(inputOf(reg.ins()), interval->end()))
         return false;
     LiveIntervalVector newIntervals;
     if (!newIntervals.append(preInterval) || !newIntervals.append(postInterval))
         return false;
     distributeUses(interval, newIntervals);
     if (!split(interval, newIntervals))
         return false;
     JS_ASSERT(usedReg.numIntervals() == 2);
     usedReg.setCanonicalSpillExclude(inputOf(reg.ins()));
     return tryGroupRegisters(use, def);
 }
 bool
 BacktrackingAllocator::groupAndQueueRegisters()
 {
     // Try to group registers with their reused inputs.
     // Virtual register number 0 is unused.
     JS_ASSERT(vregs[0u].numIntervals() == 0);
     for (size_t i = 1; i < graph.numVirtualRegisters(); i++) {
         BacktrackingVirtualRegister &reg = vregs[i];
         if (!reg.numIntervals())
             continue;
         if (reg.def()->policy() == LDefinition::MUST_REUSE_INPUT) {
             LUse *use = reg.ins()->getOperand(reg.def()->getReusedInput())->toUse();
             if (!tryGroupReusedRegister(i, use->virtualRegister()))
                 return false;
         }
     }
     // Try to group phis with their inputs.
     for (size_t i = 0; i < graph.numBlocks(); i++) {
         LBlock *block = graph.getBlock(i);
         for (size_t j = 0; j < block->numPhis(); j++) {
             LPhi *phi = block->getPhi(j);
             uint32_t output = phi->getDef(0)->virtualRegister();
             for (size_t k = 0, kend = phi->numOperands(); k < kend; k++) {
                 uint32_t input = phi->getOperand(k)->toUse()->virtualRegister();
                 if (!tryGroupRegisters(input, output))
                     return false;
             }
         }
     }
     // Virtual register number 0 is unused.
     JS_ASSERT(vregs[0u].numIntervals() == 0);
     for (size_t i = 1; i < graph.numVirtualRegisters(); i++) {
         if (mir->shouldCancel("Backtracking Enqueue Registers"))
             return false;
         BacktrackingVirtualRegister &reg = vregs[i];
         JS_ASSERT(reg.numIntervals() <= 2);
         JS_ASSERT(!reg.canonicalSpill());
         if (!reg.numIntervals())
             continue;
         // Disable this for now; see bugs 906858, 931487, and 932465.
 #if 0
         // Eagerly set the canonical spill slot for registers which are preset
         // for that slot, and reuse it for other registers in the group.
         LDefinition *def = reg.def();
         if (def->policy() == LDefinition::PRESET && !def->output()->isRegister()) {
             reg.setCanonicalSpill(*def->output());
             if (reg.group() && reg.group()->spill.isUse())
                 reg.group()->spill = *def->output();
         }
 #endif
         // Place all intervals for this register on the allocation queue.
         // During initial queueing use single queue items for groups of
         // registers, so that they will be allocated together and reduce the
         // risk of unnecessary conflicts. This is in keeping with the idea that
         // register groups are effectively single registers whose value changes
         // during execution. If any intervals in the group are evicted later
         // then they will be reallocated individually.
         size_t start = 0;
         if (VirtualRegisterGroup *group = reg.group()) {
             if (i == group->canonicalReg()) {
                 size_t priority = computePriority(group);
                 if (!allocationQueue.insert(QueueItem(group, priority)))
                     return false;
             }
             start++;
         }
         for (; start < reg.numIntervals(); start++) {
             LiveInterval *interval = reg.getInterval(start);
             if (interval->numRanges() > 0) {
                 size_t priority = computePriority(interval);
                 if (!allocationQueue.insert(QueueItem(interval, priority)))
                     return false;
             }
         }
     }
     return true;
 }
 static const size_t MAX_ATTEMPTS = 2;
 bool
 BacktrackingAllocator::tryAllocateFixed(LiveInterval *interval, bool *success,
                                         bool *pfixed, LiveInterval **pconflicting)
 {
     // Spill intervals which are required to be in a certain stack slot.
     if (!interval->requirement()->allocation().isRegister()) {
         IonSpew(IonSpew_RegAlloc, "stack allocation requirement");
         interval->setAllocation(interval->requirement()->allocation());
         *success = true;
         return true;
     }
     AnyRegister reg = interval->requirement()->allocation().toRegister();
     return tryAllocateRegister(registers[reg.code()], interval, success, pfixed, pconflicting);
 }
 bool
 BacktrackingAllocator::tryAllocateNonFixed(LiveInterval *interval, bool *success,
                                            bool *pfixed, LiveInterval **pconflicting)
 {
     // If we want, but do not require an interval to be in a specific
     // register, only look at that register for allocating and evict
     // or spill if it is not available. Picking a separate register may
     // be even worse than spilling, as it will still necessitate moves
     // and will tie up more registers than if we spilled.
     if (interval->hint()->kind() == Requirement::FIXED) {
         AnyRegister reg = interval->hint()->allocation().toRegister();
         if (!tryAllocateRegister(registers[reg.code()], interval, success, pfixed, pconflicting))
             return false;
         if (*success)
             return true;
     }
     // Spill intervals which have no hint or register requirement.
     if (interval->requirement()->kind() == Requirement::NONE) {
         spill(interval);
         *success = true;
         return true;
     }
     if (!*pconflicting || minimalInterval(interval)) {
         // Search for any available register which the interval can be
         // allocated to.
         for (size_t i = 0; i < AnyRegister::Total; i++) {
             if (!tryAllocateRegister(registers[i], interval, success, pfixed, pconflicting))
                 return false;
             if (*success)
                 return true;
         }
     }
     // We failed to allocate this interval.
     JS_ASSERT(!*success);
     return true;
 }
 bool
 BacktrackingAllocator::processInterval(LiveInterval *interval)
 {
     if (IonSpewEnabled(IonSpew_RegAlloc)) {
         IonSpew(IonSpew_RegAlloc, "Allocating v%u [priority %lu] [weight %lu]: %s",
                 interval->vreg(), computePriority(interval), computeSpillWeight(interval),
                 interval->rangesToString());
     }
     // An interval can be processed by doing any of the following:
     //
     // - Assigning the interval a register. The interval cannot overlap any
     //   other interval allocated for that physical register.
     //
     // - Spilling the interval, provided it has no register uses.
     //
     // - Splitting the interval into two or more intervals which cover the
     //   original one. The new intervals are placed back onto the priority
     //   queue for later processing.
     //
     // - Evicting one or more existing allocated intervals, and then doing one
     //   of the above operations. Evicted intervals are placed back on the
     //   priority queue. Any evicted intervals must have a lower spill weight
     //   than the interval being processed.
     //
     // As long as this structure is followed, termination is guaranteed.
     // In general, we want to minimize the amount of interval splitting
     // (which generally necessitates spills), so allocate longer lived, lower
     // weight intervals first and evict and split them later if they prevent
     // allocation for higher weight intervals.
     bool canAllocate = setIntervalRequirement(interval);
     bool fixed;
     LiveInterval *conflict = nullptr;
     for (size_t attempt = 0;; attempt++) {
         if (canAllocate) {
             bool success = false;
             fixed = false;
             conflict = nullptr;
             // Ok, let's try allocating for this interval.
             if (interval->requirement()->kind() == Requirement::FIXED) {
                 if (!tryAllocateFixed(interval, &success, &fixed, &conflict))
                     return false;
             } else {
                 if (!tryAllocateNonFixed(interval, &success, &fixed, &conflict))
                     return false;
             }
             // If that worked, we're done!
             if (success)
                 return true;
             // If that didn't work, but we have a non-fixed LiveInterval known
             // to be conflicting, maybe we can evict it and try again.
             if (attempt < MAX_ATTEMPTS &&
                 !fixed &&
                 conflict &&
                 computeSpillWeight(conflict) < computeSpillWeight(interval))
             {
                 if (!evictInterval(conflict))
                     return false;
                 continue;
             }
         }
         // A minimal interval cannot be split any further. If we try to split
         // it at this point we will just end up with the same interval and will
         // enter an infinite loop. Weights and the initial live intervals must
         // be constructed so that any minimal interval is allocatable.
         JS_ASSERT(!minimalInterval(interval));
         if (canAllocate && fixed)
             return splitAcrossCalls(interval);
         return chooseIntervalSplit(interval, conflict);
     }
 }
 bool
 BacktrackingAllocator::processGroup(VirtualRegisterGroup *group)
 {
     if (IonSpewEnabled(IonSpew_RegAlloc)) {
         IonSpew(IonSpew_RegAlloc, "Allocating group v%u [priority %lu] [weight %lu]",
                 group->registers[0], computePriority(group), computeSpillWeight(group));
     }
     bool fixed;
     LiveInterval *conflict;
     for (size_t attempt = 0;; attempt++) {
         // Search for any available register which the group can be allocated to.
         fixed = false;
         conflict = nullptr;
         for (size_t i = 0; i < AnyRegister::Total; i++) {
             bool success;
             if (!tryAllocateGroupRegister(registers[i], group, &success, &fixed, &conflict))
                 return false;
             if (success) {
                 conflict = nullptr;
                 break;
             }
         }
         if (attempt < MAX_ATTEMPTS &&
             !fixed &&
             conflict &&
             conflict->hasVreg() &&
             computeSpillWeight(conflict) < computeSpillWeight(group))
         {
             if (!evictInterval(conflict))
                 return false;
             continue;
         }
         for (size_t i = 0; i < group->registers.length(); i++) {
             VirtualRegister &reg = vregs[group->registers[i]];
             JS_ASSERT(reg.numIntervals() <= 2);
             if (!processInterval(reg.getInterval(0)))
                 return false;
         }
         return true;
     }
 }
 bool
 BacktrackingAllocator::setIntervalRequirement(LiveInterval *interval)
 {
     // Set any requirement or hint on interval according to its definition and
     // uses. Return false if there are conflicting requirements which will
     // require the interval to be split.
     interval->setHint(Requirement());
     interval->setRequirement(Requirement());
     BacktrackingVirtualRegister *reg = &vregs[interval->vreg()];
     // Set a hint if another interval in the same group is in a register.
     if (VirtualRegisterGroup *group = reg->group()) {
         if (group->allocation.isRegister()) {
             if (IonSpewEnabled(IonSpew_RegAlloc)) {
                 IonSpew(IonSpew_RegAlloc, "Hint %s, used by group allocation",
                         group->allocation.toString());
             }
             interval->setHint(Requirement(group->allocation));
         }
     }
     if (interval->index() == 0) {
         // The first interval is the definition, so deal with any definition
         // constraints/hints.
         LDefinition::Policy policy = reg->def()->policy();
         if (policy == LDefinition::PRESET) {
             // Preset policies get a FIXED requirement.
             if (IonSpewEnabled(IonSpew_RegAlloc)) {
                 IonSpew(IonSpew_RegAlloc, "Requirement %s, preset by definition",
                         reg->def()->output()->toString());
             }
             interval->setRequirement(Requirement(*reg->def()->output()));
         } else if (reg->ins()->isPhi()) {
             // Phis don't have any requirements, but they should prefer their
             // input allocations. This is captured by the group hints above.
         } else {
             // Non-phis get a REGISTER requirement.
             interval->setRequirement(Requirement(Requirement::REGISTER));
         }
     }
     // Search uses for requirements.
     for (UsePositionIterator iter = interval->usesBegin();
          iter != interval->usesEnd();
          iter++)
     {
         LUse::Policy policy = iter->use->policy();
         if (policy == LUse::FIXED) {
             AnyRegister required = GetFixedRegister(reg->def(), iter->use);
             if (IonSpewEnabled(IonSpew_RegAlloc)) {
                 IonSpew(IonSpew_RegAlloc, "Requirement %s, due to use at %u",
                         required.name(), iter->pos.pos());
             }
             // If there are multiple fixed registers which the interval is
             // required to use, fail. The interval will need to be split before
             // it can be allocated.
             if (!interval->addRequirement(Requirement(LAllocation(required))))
                 return false;
         } else if (policy == LUse::REGISTER) {
             if (!interval->addRequirement(Requirement(Requirement::REGISTER)))
                 return false;
         }
     }
     return true;
 }
 bool
 BacktrackingAllocator::tryAllocateGroupRegister(PhysicalRegister &r, VirtualRegisterGroup *group,
                                                 bool *psuccess, bool *pfixed, LiveInterval **pconflicting)
 {
     *psuccess = false;
     if (!r.allocatable)
         return true;
     if (r.reg.isFloat() != vregs[group->registers[0]].isFloatReg())
         return true;
     bool allocatable = true;
     LiveInterval *conflicting = nullptr;
     for (size_t i = 0; i < group->registers.length(); i++) {
         VirtualRegister &reg = vregs[group->registers[i]];
         JS_ASSERT(reg.numIntervals() <= 2);
         LiveInterval *interval = reg.getInterval(0);
         for (size_t j = 0; j < interval->numRanges(); j++) {
             AllocatedRange range(interval, interval->getRange(j)), existing;
             if (r.allocations.contains(range, &existing)) {
                 if (conflicting) {
                     if (conflicting != existing.interval)
                         return true;
                 } else {
                     conflicting = existing.interval;
                 }
                 allocatable = false;
             }
         }
     }
     if (!allocatable) {
         JS_ASSERT(conflicting);
         if (!*pconflicting || computeSpillWeight(conflicting) < computeSpillWeight(*pconflicting))
             *pconflicting = conflicting;
         if (!conflicting->hasVreg())
             *pfixed = true;
         return true;
     }
     *psuccess = true;
     group->allocation = LAllocation(r.reg);
     return true;
 }
 bool
 BacktrackingAllocator::tryAllocateRegister(PhysicalRegister &r, LiveInterval *interval,
                                            bool *success, bool *pfixed, LiveInterval **pconflicting)
 {
     *success = false;
     if (!r.allocatable)
         return true;
     BacktrackingVirtualRegister *reg = &vregs[interval->vreg()];
     if (reg->isFloatReg() != r.reg.isFloat())
         return true;
     JS_ASSERT_IF(interval->requirement()->kind() == Requirement::FIXED,
                  interval->requirement()->allocation() == LAllocation(r.reg));
     for (size_t i = 0; i < interval->numRanges(); i++) {
         AllocatedRange range(interval, interval->getRange(i)), existing;
         if (r.allocations.contains(range, &existing)) {
             if (existing.interval->hasVreg()) {
                 if (IonSpewEnabled(IonSpew_RegAlloc)) {
                     IonSpew(IonSpew_RegAlloc, "%s collides with v%u [%u,%u> [weight %lu]",
                             r.reg.name(), existing.interval->vreg(),
                             existing.range->from.pos(), existing.range->to.pos(),
                             computeSpillWeight(existing.interval));
                 }
                 if (!*pconflicting || computeSpillWeight(existing.interval) < computeSpillWeight(*pconflicting))
                     *pconflicting = existing.interval;
             } else {
                 if (IonSpewEnabled(IonSpew_RegAlloc)) {
                     IonSpew(IonSpew_RegAlloc, "%s collides with fixed use [%u,%u>",
                             r.reg.name(), existing.range->from.pos(), existing.range->to.pos());
                 }
                 *pfixed = true;
             }
             return true;
         }
     }
     IonSpew(IonSpew_RegAlloc, "allocated to %s", r.reg.name());
     for (size_t i = 0; i < interval->numRanges(); i++) {
         AllocatedRange range(interval, interval->getRange(i));
         if (!r.allocations.insert(range))
             return false;
     }
     // Set any register hint for allocating other intervals in the same group.
     if (VirtualRegisterGroup *group = reg->group()) {
         if (!group->allocation.isRegister())
             group->allocation = LAllocation(r.reg);
     }
     interval->setAllocation(LAllocation(r.reg));
     *success = true;
     return true;
 }
 bool
 BacktrackingAllocator::evictInterval(LiveInterval *interval)
 {
     if (IonSpewEnabled(IonSpew_RegAlloc)) {
         IonSpew(IonSpew_RegAlloc, "Evicting interval v%u: %s",
                 interval->vreg(), interval->rangesToString());
     }
     JS_ASSERT(interval->getAllocation()->isRegister());
     AnyRegister reg(interval->getAllocation()->toRegister());
     PhysicalRegister &physical = registers[reg.code()];
     JS_ASSERT(physical.reg == reg && physical.allocatable);
     for (size_t i = 0; i < interval->numRanges(); i++) {
         AllocatedRange range(interval, interval->getRange(i));
         physical.allocations.remove(range);
     }
     interval->setAllocation(LAllocation());
     size_t priority = computePriority(interval);
     return allocationQueue.insert(QueueItem(interval, priority));
 }
 void
 BacktrackingAllocator::distributeUses(LiveInterval *interval,
                                       const LiveIntervalVector &newIntervals)
 {
     JS_ASSERT(newIntervals.length() >= 2);
     // Simple redistribution of uses from an old interval to a set of new
     // intervals. Intervals are permitted to overlap, in which case this will
     // assign uses in the overlapping section to the interval with the latest
     // start position.
     for (UsePositionIterator iter(interval->usesBegin());
          iter != interval->usesEnd();
          iter++)
     {
         CodePosition pos = iter->pos;
         LiveInterval *addInterval = nullptr;
         for (size_t i = 0; i < newIntervals.length(); i++) {
             LiveInterval *newInterval = newIntervals[i];
             if (newInterval->covers(pos)) {
                 if (!addInterval || newInterval->start() < addInterval->start())
                     addInterval = newInterval;
             }
         }
         addInterval->addUseAtEnd(new(alloc()) UsePosition(iter->use, iter->pos));
     }
 }
 bool
 BacktrackingAllocator::split(LiveInterval *interval,
                              const LiveIntervalVector &newIntervals)
 {
     if (IonSpewEnabled(IonSpew_RegAlloc)) {
         IonSpew(IonSpew_RegAlloc, "splitting interval v%u %s into:",
                 interval->vreg(), interval->rangesToString());
         for (size_t i = 0; i < newIntervals.length(); i++)
             IonSpew(IonSpew_RegAlloc, "    %s", newIntervals[i]->rangesToString());
     }
     JS_ASSERT(newIntervals.length() >= 2);
     // Find the earliest interval in the new list.
     LiveInterval *first = newIntervals[0];
     for (size_t i = 1; i < newIntervals.length(); i++) {
         if (newIntervals[i]->start() < first->start())
             first = newIntervals[i];
     }
     // Replace the old interval in the virtual register's state with the new intervals.
     VirtualRegister *reg = &vregs[interval->vreg()];
     reg->replaceInterval(interval, first);
     for (size_t i = 0; i < newIntervals.length(); i++) {
         if (newIntervals[i] != first && !reg->addInterval(newIntervals[i]))
             return false;
     }
     return true;
 }
 bool BacktrackingAllocator::requeueIntervals(const LiveIntervalVector &newIntervals)
 {
     // Queue the new intervals for register assignment.
     for (size_t i = 0; i < newIntervals.length(); i++) {
         LiveInterval *newInterval = newIntervals[i];
         size_t priority = computePriority(newInterval);
         if (!allocationQueue.insert(QueueItem(newInterval, priority)))
             return false;
     }
     return true;
 }
 void
 BacktrackingAllocator::spill(LiveInterval *interval)
 {
     IonSpew(IonSpew_RegAlloc, "Spilling interval");
     JS_ASSERT(interval->requirement()->kind() == Requirement::NONE);
     JS_ASSERT(!interval->getAllocation()->isStackSlot());
     // We can't spill bogus intervals.
     JS_ASSERT(interval->hasVreg());
     BacktrackingVirtualRegister *reg = &vregs[interval->vreg()];
     bool useCanonical = !reg->hasCanonicalSpillExclude()
         || interval->start() < reg->canonicalSpillExclude();
     if (useCanonical) {
         if (reg->canonicalSpill()) {
             IonSpew(IonSpew_RegAlloc, "  Picked canonical spill location %s",
                     reg->canonicalSpill()->toString());
             interval->setAllocation(*reg->canonicalSpill());
             return;
         }
         if (reg->group() && !reg->group()->spill.isUse()) {
             IonSpew(IonSpew_RegAlloc, "  Reusing group spill location %s",
                     reg->group()->spill.toString());
             interval->setAllocation(reg->group()->spill);
             reg->setCanonicalSpill(reg->group()->spill);
             return;
         }
     }
     uint32_t stackSlot = stackSlotAllocator.allocateSlot(reg->type());
     JS_ASSERT(stackSlot <= stackSlotAllocator.stackHeight());
     LStackSlot alloc(stackSlot);
     interval->setAllocation(alloc);
     IonSpew(IonSpew_RegAlloc, "  Allocating spill location %s", alloc.toString());
     if (useCanonical) {
         reg->setCanonicalSpill(alloc);
         if (reg->group())
             reg->group()->spill = alloc;
     }
 }
 // Add moves to resolve conflicting assignments between a block and its
 // predecessors. XXX try to common this with LinearScanAllocator.
 bool
 BacktrackingAllocator::resolveControlFlow()
 {
     // Virtual register number 0 is unused.
     JS_ASSERT(vregs[0u].numIntervals() == 0);
     for (size_t i = 1; i < graph.numVirtualRegisters(); i++) {
         BacktrackingVirtualRegister *reg = &vregs[i];
         if (mir->shouldCancel("Backtracking Resolve Control Flow (vreg loop)"))
             return false;
         for (size_t j = 1; j < reg->numIntervals(); j++) {
             LiveInterval *interval = reg->getInterval(j);
             JS_ASSERT(interval->index() == j);
             bool skip = false;
             for (int k = j - 1; k >= 0; k--) {
                 LiveInterval *prevInterval = reg->getInterval(k);
                 if (prevInterval->start() != interval->start())
                     break;
                 if (*prevInterval->getAllocation() == *interval->getAllocation()) {
                     skip = true;
                     break;
                 }
             }
             if (skip)
                 continue;
             CodePosition start = interval->start();
             InstructionData *data = &insData[start];
             if (interval->start() > inputOf(data->block()->firstId())) {
                 JS_ASSERT(start == inputOf(data->ins()) || start == outputOf(data->ins()));
                 LiveInterval *prevInterval = reg->intervalFor(start.previous());
                 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;
                 }
             }
         }
     }
     for (size_t i = 0; i < graph.numBlocks(); i++) {
         if (mir->shouldCancel("Backtracking Resolve Control Flow (block 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);
             VirtualRegister *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;
             }
         }
         // Resolve split intervals with moves
         BitSet *live = liveIn[mSuccessor->id()];
         for (BitSet::Iterator liveRegId(*live); liveRegId; liveRegId++) {
             VirtualRegister &reg = vregs[*liveRegId];
             for (size_t j = 0; j < mSuccessor->numPredecessors(); j++) {
                 LBlock *predecessor = mSuccessor->getPredecessor(j)->lir();
                 for (size_t k = 0; k < reg.numIntervals(); k++) {
                     LiveInterval *to = reg.getInterval(k);
                     if (!to->covers(inputOf(successor->firstId())))
                         continue;
                     if (to->covers(outputOf(predecessor->lastId())))
                         continue;
                     LiveInterval *from = reg.intervalFor(outputOf(predecessor->lastId()));
                     if (mSuccessor->numPredecessors() > 1) {
                         JS_ASSERT(predecessor->mir()->numSuccessors() == 1);
                         if (!moveAtExit(predecessor, from, to, reg.type()))
                             return false;
                     } else {
                         if (!moveAtEntry(successor, from, to, reg.type()))
                             return false;
                     }
                 }
             }
         }
     }
     return true;
 }
 bool
 BacktrackingAllocator::isReusedInput(LUse *use, LInstruction *ins, bool considerCopy)
 {
     if (LDefinition *def = FindReusingDefinition(ins, use))
         return considerCopy || !vregs[def->virtualRegister()].mustCopyInput();
     return false;
 }
 bool
 BacktrackingAllocator::isRegisterUse(LUse *use, LInstruction *ins, bool considerCopy)
 {
     switch (use->policy()) {
       case LUse::ANY:
         return isReusedInput(use, ins, considerCopy);
       case LUse::REGISTER:
       case LUse::FIXED:
         return true;
       default:
         return false;
     }
 }
 bool
 BacktrackingAllocator::isRegisterDefinition(LiveInterval *interval)
 {
     if (interval->index() != 0)
         return false;
     VirtualRegister &reg = vregs[interval->vreg()];
     if (reg.ins()->isPhi())
         return false;
     if (reg.def()->policy() == LDefinition::PRESET && !reg.def()->output()->isRegister())
         return false;
     return true;
 }
 bool
 BacktrackingAllocator::reifyAllocations()
 {
     // Virtual register number 0 is unused.
     JS_ASSERT(vregs[0u].numIntervals() == 0);
     for (size_t i = 1; i < graph.numVirtualRegisters(); i++) {
         VirtualRegister *reg = &vregs[i];
         if (mir->shouldCancel("Backtracking Reify Allocations (main loop)"))
             return false;
         for (size_t j = 0; j < reg->numIntervals(); j++) {
             LiveInterval *interval = reg->getInterval(j);
             JS_ASSERT(interval->index() == j);
             if (interval->index() == 0) {
                 reg->def()->setOutput(*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 = *reg->def()->output();
                     }
                 }
             }
             for (UsePositionIterator iter(interval->usesBegin());
                  iter != interval->usesEnd();
                  iter++)
             {
                 LAllocation *alloc = iter->use;
                 *alloc = *interval->getAllocation();
                 // For any uses which feed into MUST_REUSE_INPUT definitions,
                 // add copies if the use and def have different allocations.
                 LInstruction *ins = insData[iter->pos].ins();
                 if (LDefinition *def = FindReusingDefinition(ins, alloc)) {
                     LiveInterval *outputInterval =
                         vregs[def->virtualRegister()].intervalFor(outputOf(ins));
                     LAllocation *res = outputInterval->getAllocation();
                     LAllocation *sourceAlloc = interval->getAllocation();
                     if (*res != *alloc) {
                         LMoveGroup *group = getInputMoveGroup(inputOf(ins));
                         if (!group->addAfter(sourceAlloc, res, def->type()))
                             return false;
                         *alloc = *res;
                     }
                 }
             }
             addLiveRegistersForInterval(reg, interval);
         }
     }
     graph.setLocalSlotCount(stackSlotAllocator.stackHeight());
     return true;
 }
 bool
 BacktrackingAllocator::populateSafepoints()
 {
     size_t firstSafepoint = 0;
     // Virtual register number 0 is unused.
     JS_ASSERT(!vregs[0u].def());
     for (uint32_t i = 1; i < vregs.numVirtualRegisters(); i++) {
         BacktrackingVirtualRegister *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.
         CodePosition end = reg->getInterval(0)->end();
         for (size_t j = 1; j < reg->numIntervals(); j++)
             end = Max(end, reg->getInterval(j)->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 < outputOf(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();
             for (size_t k = 0; k < reg->numIntervals(); k++) {
                 LiveInterval *interval = reg->getInterval(k);
                 if (!interval->covers(inputOf(ins)))
                     continue;
                 LAllocation *a = interval->getAllocation();
                 if (a->isGeneralReg() && ins->isCall())
                     continue;
                 switch (reg->type()) {
                   case LDefinition::OBJECT:
                     safepoint->addGcPointer(*a);
                     break;
                   case LDefinition::SLOTS:
                     safepoint->addSlotsOrElementsPointer(*a);
                     break;
 #ifdef JS_NUNBOX32
                   case LDefinition::TYPE:
                     safepoint->addNunboxType(i, *a);
                     break;
                   case LDefinition::PAYLOAD:
                     safepoint->addNunboxPayload(i, *a);
                     break;
 #else
                   case LDefinition::BOX:
                     safepoint->addBoxedValue(*a);
                     break;
 #endif
                   default:
                     MOZ_ASSUME_UNREACHABLE("Bad register type");
                 }
             }
         }
     }
     return true;
 }
 void
 BacktrackingAllocator::dumpRegisterGroups()
 {
     fprintf(stderr, "Register groups:\n");
     // Virtual register number 0 is unused.
     JS_ASSERT(!vregs[0u].group());
     for (size_t i = 1; i < graph.numVirtualRegisters(); i++) {
         VirtualRegisterGroup *group = vregs[i].group();
         if (group && i == group->canonicalReg()) {
             for (size_t j = 0; j < group->registers.length(); j++)
                 fprintf(stderr, " v%u", group->registers[j]);
             fprintf(stderr, "\n");
         }
     }
 }
 void
 BacktrackingAllocator::dumpLiveness()
 {
 #ifdef DEBUG
     fprintf(stderr, "Virtual Registers:\n");
     for (size_t blockIndex = 0; blockIndex < graph.numBlocks(); blockIndex++) {
         LBlock *block = graph.getBlock(blockIndex);
         MBasicBlock *mir = block->mir();
         fprintf(stderr, "\nBlock %lu", static_cast<unsigned long>(blockIndex));
         for (size_t i = 0; i < mir->numSuccessors(); i++)
             fprintf(stderr, " [successor %u]", mir->getSuccessor(i)->id());
         fprintf(stderr, "\n");
         for (size_t i = 0; i < block->numPhis(); i++) {
             LPhi *phi = block->getPhi(i);
             // Don't print the inputOf for phi nodes, since it's never used.
             fprintf(stderr, "[,%u Phi [def v%u] <-",
                     outputOf(phi).pos(),
                     phi->getDef(0)->virtualRegister());
             for (size_t j = 0; j < phi->numOperands(); j++)
                 fprintf(stderr, " %s", phi->getOperand(j)->toString());
             fprintf(stderr, "]\n");
         }
         for (LInstructionIterator iter = block->begin(); iter != block->end(); iter++) {
             LInstruction *ins = *iter;
             fprintf(stderr, "[%u,%u %s]", inputOf(ins).pos(), outputOf(ins).pos(), ins->opName());
             for (size_t i = 0; i < ins->numTemps(); i++) {
                 LDefinition *temp = ins->getTemp(i);
                 if (!temp->isBogusTemp())
                     fprintf(stderr, " [temp v%u]", temp->virtualRegister());
             }
             for (size_t i = 0; i < ins->numDefs(); i++) {
                 LDefinition *def = ins->getDef(i);
                 fprintf(stderr, " [def v%u]", def->virtualRegister());
             }
             for (LInstruction::InputIterator alloc(*ins); alloc.more(); alloc.next())
                 fprintf(stderr, " [use %s]", alloc->toString());
             fprintf(stderr, "\n");
         }
     }
     fprintf(stderr, "\nLive Ranges:\n\n");
     for (size_t i = 0; i < AnyRegister::Total; i++)
         if (registers[i].allocatable)
             fprintf(stderr, "reg %s: %s\n", AnyRegister::FromCode(i).name(), fixedIntervals[i]->rangesToString());
     // Virtual register number 0 is unused.
     JS_ASSERT(vregs[0u].numIntervals() == 0);
     for (size_t i = 1; i < graph.numVirtualRegisters(); i++) {
         fprintf(stderr, "v%lu:", static_cast<unsigned long>(i));
         VirtualRegister &vreg = vregs[i];
         for (size_t j = 0; j < vreg.numIntervals(); j++) {
             if (j)
                 fprintf(stderr, " *");
             fprintf(stderr, "%s", vreg.getInterval(j)->rangesToString());
         }
         fprintf(stderr, "\n");
     }
     fprintf(stderr, "\n");
 #endif // DEBUG
 }
 #ifdef DEBUG
 struct BacktrackingAllocator::PrintLiveIntervalRange
 {
     void operator()(const AllocatedRange &item)
     {
         if (item.range == item.interval->getRange(0)) {
             if (item.interval->hasVreg())
                 fprintf(stderr, "  v%u: %s\n",
                        item.interval->vreg(),
                        item.interval->rangesToString());
             else
                 fprintf(stderr, "  fixed: %s\n",
                        item.interval->rangesToString());
         }
     }
 };
 #endif
 void
 BacktrackingAllocator::dumpAllocations()
 {
 #ifdef DEBUG
     fprintf(stderr, "Allocations:\n");
     // Virtual register number 0 is unused.
     JS_ASSERT(vregs[0u].numIntervals() == 0);
     for (size_t i = 1; i < graph.numVirtualRegisters(); i++) {
         fprintf(stderr, "v%lu:", static_cast<unsigned long>(i));
         VirtualRegister &vreg = vregs[i];
         for (size_t j = 0; j < vreg.numIntervals(); j++) {
             if (j)
                 fprintf(stderr, " *");
             LiveInterval *interval = vreg.getInterval(j);
             fprintf(stderr, "%s :: %s", interval->rangesToString(), interval->getAllocation()->toString());
         }
         fprintf(stderr, "\n");
     }
     fprintf(stderr, "\n");
     for (size_t i = 0; i < AnyRegister::Total; i++) {
         if (registers[i].allocatable) {
             fprintf(stderr, "reg %s:\n", AnyRegister::FromCode(i).name());
             registers[i].allocations.forEach(PrintLiveIntervalRange());
         }
     }
     fprintf(stderr, "\n");
 #endif // DEBUG
 }
 bool
 BacktrackingAllocator::addLiveInterval(LiveIntervalVector &intervals, uint32_t vreg,
                                        LiveInterval *spillInterval,
                                        CodePosition from, CodePosition to)
 {
     LiveInterval *interval = LiveInterval::New(alloc(), vreg, 0);
     interval->setSpillInterval(spillInterval);
     return interval->addRange(from, to) && intervals.append(interval);
 }
 ///////////////////////////////////////////////////////////////////////////////
 // Heuristic Methods
 ///////////////////////////////////////////////////////////////////////////////
 size_t
 BacktrackingAllocator::computePriority(const LiveInterval *interval)
 {
     // The priority of an interval is its total length, so that longer lived
     // intervals will be processed before shorter ones (even if the longer ones
     // have a low spill weight). See processInterval().
     size_t lifetimeTotal = 0;
     for (size_t i = 0; i < interval->numRanges(); i++) {
         const LiveInterval::Range *range = interval->getRange(i);
         lifetimeTotal += range->to.pos() - range->from.pos();
     }
     return lifetimeTotal;
 }
 size_t
 BacktrackingAllocator::computePriority(const VirtualRegisterGroup *group)
 {
     size_t priority = 0;
     for (size_t j = 0; j < group->registers.length(); j++) {
         uint32_t vreg = group->registers[j];
         priority += computePriority(vregs[vreg].getInterval(0));
     }
     return priority;
 }
 bool
 BacktrackingAllocator::minimalDef(const LiveInterval *interval, LInstruction *ins)
 {
     // Whether interval is a minimal interval capturing a definition at ins.
     return (interval->end() <= minimalDefEnd(ins).next()) &&
         ((!ins->isPhi() && interval->start() == inputOf(ins)) || interval->start() == outputOf(ins));
 }
 bool
 BacktrackingAllocator::minimalUse(const LiveInterval *interval, LInstruction *ins)
 {
     // Whether interval is a minimal interval capturing a use at ins.
     return (interval->start() == inputOf(ins)) &&
         (interval->end() == outputOf(ins) || interval->end() == outputOf(ins).next());
 }
 bool
 BacktrackingAllocator::minimalInterval(const LiveInterval *interval, bool *pfixed)
 {
     if (!interval->hasVreg()) {
         *pfixed = true;
         return true;
     }
     if (interval->index() == 0) {
         VirtualRegister &reg = vregs[interval->vreg()];
         if (pfixed)
             *pfixed = reg.def()->policy() == LDefinition::PRESET && reg.def()->output()->isRegister();
         return minimalDef(interval, reg.ins());
     }
     bool fixed = false, minimal = false;
     for (UsePositionIterator iter = interval->usesBegin(); iter != interval->usesEnd(); iter++) {
         LUse *use = iter->use;
         switch (use->policy()) {
           case LUse::FIXED:
             if (fixed)
                 return false;
             fixed = true;
             if (minimalUse(interval, insData[iter->pos].ins()))
                 minimal = true;
             break;
           case LUse::REGISTER:
             if (minimalUse(interval, insData[iter->pos].ins()))
                 minimal = true;
             break;
           default:
             break;
         }
     }
     if (pfixed)
         *pfixed = fixed;
     return minimal;
 }
 size_t
 BacktrackingAllocator::computeSpillWeight(const LiveInterval *interval)
 {
     // Minimal intervals have an extremely high spill weight, to ensure they
     // can evict any other intervals and be allocated to a register.
     bool fixed;
     if (minimalInterval(interval, &fixed))
         return fixed ? 2000000 : 1000000;
     size_t usesTotal = 0;
     if (interval->index() == 0) {
         VirtualRegister *reg = &vregs[interval->vreg()];
         if (reg->def()->policy() == LDefinition::PRESET && reg->def()->output()->isRegister())
             usesTotal += 2000;
         else if (!reg->ins()->isPhi())
             usesTotal += 2000;
     }
     for (UsePositionIterator iter = interval->usesBegin(); iter != interval->usesEnd(); iter++) {
         LUse *use = iter->use;
         switch (use->policy()) {
           case LUse::ANY:
             usesTotal += 1000;
             break;
           case LUse::REGISTER:
           case LUse::FIXED:
             usesTotal += 2000;
             break;
           case LUse::KEEPALIVE:
             break;
           default:
             // Note: RECOVERED_INPUT will not appear in UsePositionIterator.
             MOZ_ASSUME_UNREACHABLE("Bad use");
         }
     }
     // Intervals for registers in groups get higher weights.
     if (interval->hint()->kind() != Requirement::NONE)
         usesTotal += 2000;
     // Compute spill weight as a use density, lowering the weight for long
     // lived intervals with relatively few uses.
     size_t lifetimeTotal = computePriority(interval);
     return lifetimeTotal ? usesTotal / lifetimeTotal : 0;
 }
 size_t
 BacktrackingAllocator::computeSpillWeight(const VirtualRegisterGroup *group)
 {
     size_t maxWeight = 0;
     for (size_t j = 0; j < group->registers.length(); j++) {
         uint32_t vreg = group->registers[j];
         maxWeight = Max(maxWeight, computeSpillWeight(vregs[vreg].getInterval(0)));
     }
     return maxWeight;
 }
 bool
 BacktrackingAllocator::trySplitAcrossHotcode(LiveInterval *interval, bool *success)
 {
     // If this interval has portions that are hot and portions that are cold,
     // split it at the boundaries between hot and cold code.
     const LiveInterval::Range *hotRange = nullptr;
     for (size_t i = 0; i < interval->numRanges(); i++) {
         AllocatedRange range(interval, interval->getRange(i)), existing;
         if (hotcode.contains(range, &existing)) {
             hotRange = existing.range;
             break;
         }
     }
     // Don't split if there is no hot code in the interval.
     if (!hotRange)
         return true;
     // Don't split if there is no cold code in the interval.
     bool coldCode = false;
     for (size_t i = 0; i < interval->numRanges(); i++) {
         if (!hotRange->contains(interval->getRange(i))) {
             coldCode = true;
             break;
         }
     }
     if (!coldCode)
         return true;
     SplitPositionVector splitPositions;
     if (!splitPositions.append(hotRange->from) || !splitPositions.append(hotRange->to))
         return false;
     *success = true;
     return splitAt(interval, splitPositions);
 }
 bool
 BacktrackingAllocator::trySplitAfterLastRegisterUse(LiveInterval *interval, LiveInterval *conflict, bool *success)
 {
     // If this interval's later uses do not require it to be in a register,
     // split it after the last use which does require a register. If conflict
     // is specified, only consider register uses before the conflict starts.
     CodePosition lastRegisterFrom, lastRegisterTo, lastUse;
     for (UsePositionIterator iter(interval->usesBegin());
          iter != interval->usesEnd();
          iter++)
     {
         LUse *use = iter->use;
         LInstruction *ins = insData[iter->pos].ins();
         // Uses in the interval should be sorted.
         JS_ASSERT(iter->pos >= lastUse);
         lastUse = inputOf(ins);
         if (!conflict || outputOf(ins) < conflict->start()) {
             if (isRegisterUse(use, ins, /* considerCopy = */ true)) {
                 lastRegisterFrom = inputOf(ins);
                 lastRegisterTo = iter->pos.next();
             }
         }
     }
     if (!lastRegisterFrom.pos() || lastRegisterFrom == lastUse) {
         // Can't trim non-register uses off the end by splitting.
         return true;
     }
     SplitPositionVector splitPositions;
     if (!splitPositions.append(lastRegisterTo))
         return false;
     *success = true;
     return splitAt(interval, splitPositions);
 }
 bool
 BacktrackingAllocator::splitAtAllRegisterUses(LiveInterval *interval)
 {
     // Split this interval so that all its register uses become minimal
     // intervals and allow the vreg to be spilled throughout its range.
     LiveIntervalVector newIntervals;
     uint32_t vreg = interval->vreg();
     // If this LiveInterval is the result of an earlier split which created a
     // spill interval, that spill interval covers the whole range, so we don't
     // need to create a new one.
     bool spillIntervalIsNew = false;
     LiveInterval *spillInterval = interval->spillInterval();
     if (!spillInterval) {
         spillInterval = LiveInterval::New(alloc(), vreg, 0);
         spillIntervalIsNew = true;
     }
     CodePosition spillStart = interval->start();
     if (isRegisterDefinition(interval)) {
         // Treat the definition of the interval as a register use so that it
         // can be split and spilled ASAP.
         CodePosition from = interval->start();
         CodePosition to = minimalDefEnd(insData[from].ins()).next();
         if (!addLiveInterval(newIntervals, vreg, spillInterval, from, to))
             return false;
         spillStart = to;
     }
     if (spillIntervalIsNew) {
         for (size_t i = 0; i < interval->numRanges(); i++) {
             const LiveInterval::Range *range = interval->getRange(i);
             CodePosition from = range->from < spillStart ? spillStart : range->from;
             if (!spillInterval->addRange(from, range->to))
                 return false;
         }
     }
     for (UsePositionIterator iter(interval->usesBegin());
          iter != interval->usesEnd();
          iter++)
     {
         LInstruction *ins = insData[iter->pos].ins();
         if (iter->pos < spillStart) {
             newIntervals.back()->addUseAtEnd(new(alloc()) UsePosition(iter->use, iter->pos));
         } else if (isRegisterUse(iter->use, ins)) {
             // For register uses which are not useRegisterAtStart, pick an
             // interval that covers both the instruction's input and output, so
             // that the register is not reused for an output.
             CodePosition from = inputOf(ins);
             CodePosition to = iter->pos.next();
             // Use the same interval for duplicate use positions, except when
             // the uses are fixed (they may require incompatible registers).
             if (newIntervals.empty() || newIntervals.back()->end() != to || iter->use->policy() == LUse::FIXED) {
                 if (!addLiveInterval(newIntervals, vreg, spillInterval, from, to))
                     return false;
             }
             newIntervals.back()->addUseAtEnd(new(alloc()) UsePosition(iter->use, iter->pos));
         } else {
             JS_ASSERT(spillIntervalIsNew);
             spillInterval->addUseAtEnd(new(alloc()) UsePosition(iter->use, iter->pos));
         }
     }
     if (spillIntervalIsNew && !newIntervals.append(spillInterval))
         return false;
     return split(interval, newIntervals) && requeueIntervals(newIntervals);
 }
 // Find the next split position after the current position.
 static size_t NextSplitPosition(size_t activeSplitPosition,
                                 const SplitPositionVector &splitPositions,
                                 CodePosition currentPos)
 {
     while (activeSplitPosition < splitPositions.length() &&
            splitPositions[activeSplitPosition] <= currentPos)
     {
         ++activeSplitPosition;
     }
     return activeSplitPosition;
 }
 // Test whether the current position has just crossed a split point.
 static bool SplitHere(size_t activeSplitPosition,
                       const SplitPositionVector &splitPositions,
                       CodePosition currentPos)
 {
     return activeSplitPosition < splitPositions.length() &&
            currentPos >= splitPositions[activeSplitPosition];
 }
 bool
 BacktrackingAllocator::splitAt(LiveInterval *interval,
                                const SplitPositionVector &splitPositions)
 {
     // Split the interval at the given split points. Unlike splitAtAllRegisterUses,
     // consolidate any register uses which have no intervening split points into the
     // same resulting interval.
     // splitPositions should be non-empty and sorted.
     JS_ASSERT(!splitPositions.empty());
     for (size_t i = 1; i < splitPositions.length(); ++i)
         JS_ASSERT(splitPositions[i-1] < splitPositions[i]);
     // Don't spill the interval until after the end of its definition.
     CodePosition spillStart = interval->start();
     if (isRegisterDefinition(interval))
         spillStart = minimalDefEnd(insData[interval->start()].ins()).next();
     uint32_t vreg = interval->vreg();
     // If this LiveInterval is the result of an earlier split which created a
     // spill interval, that spill interval covers the whole range, so we don't
     // need to create a new one.
     bool spillIntervalIsNew = false;
     LiveInterval *spillInterval = interval->spillInterval();
     if (!spillInterval) {
         spillInterval = LiveInterval::New(alloc(), vreg, 0);
         spillIntervalIsNew = true;
         for (size_t i = 0; i < interval->numRanges(); i++) {
             const LiveInterval::Range *range = interval->getRange(i);
             CodePosition from = range->from < spillStart ? spillStart : range->from;
             if (!spillInterval->addRange(from, range->to))
                 return false;
         }
     }
     LiveIntervalVector newIntervals;
     CodePosition lastRegisterUse;
     if (spillStart != interval->start()) {
         LiveInterval *newInterval = LiveInterval::New(alloc(), vreg, 0);
         newInterval->setSpillInterval(spillInterval);
         if (!newIntervals.append(newInterval))
             return false;
         lastRegisterUse = interval->start();
     }
     size_t activeSplitPosition = NextSplitPosition(0, splitPositions, interval->start());
     for (UsePositionIterator iter(interval->usesBegin()); iter != interval->usesEnd(); iter++) {
         LInstruction *ins = insData[iter->pos].ins();
         if (iter->pos < spillStart) {
             newIntervals.back()->addUseAtEnd(new(alloc()) UsePosition(iter->use, iter->pos));
             activeSplitPosition = NextSplitPosition(activeSplitPosition, splitPositions, iter->pos);
         } else if (isRegisterUse(iter->use, ins)) {
             if (lastRegisterUse.pos() == 0 ||
                 SplitHere(activeSplitPosition, splitPositions, iter->pos))
             {
                 // Place this register use into a different interval from the
                 // last one if there are any split points between the two uses.
                 LiveInterval *newInterval = LiveInterval::New(alloc(), vreg, 0);
                 newInterval->setSpillInterval(spillInterval);
                 if (!newIntervals.append(newInterval))
                     return false;
                 activeSplitPosition = NextSplitPosition(activeSplitPosition,
                                                         splitPositions,
                                                         iter->pos);
             }
             newIntervals.back()->addUseAtEnd(new(alloc()) UsePosition(iter->use, iter->pos));
             lastRegisterUse = iter->pos;
         } else {
             JS_ASSERT(spillIntervalIsNew);
             spillInterval->addUseAtEnd(new(alloc()) UsePosition(iter->use, iter->pos));
         }
     }
     // Compute ranges for each new interval that cover all its uses.
     size_t activeRange = interval->numRanges();
     for (size_t i = 0; i < newIntervals.length(); i++) {
         LiveInterval *newInterval = newIntervals[i];
         CodePosition start, end;
         if (i == 0 && spillStart != interval->start()) {
             start = interval->start();
             if (newInterval->usesEmpty())
                 end = spillStart;
             else
                 end = newInterval->usesBack()->pos.next();
         } else {
             start = inputOf(insData[newInterval->usesBegin()->pos].ins());
             end = newInterval->usesBack()->pos.next();
         }
         for (; activeRange > 0; --activeRange) {
             const LiveInterval::Range *range = interval->getRange(activeRange - 1);
             if (range->to <= start)
                 continue;
             if (range->from >= end)
                 break;
             if (!newInterval->addRange(Max(range->from, start),
                                        Min(range->to, end)))
                 return false;
             if (range->to >= end)
                 break;
         }
     }
     if (spillIntervalIsNew && !newIntervals.append(spillInterval))
         return false;
     return split(interval, newIntervals) && requeueIntervals(newIntervals);
 }
 bool
 BacktrackingAllocator::splitAcrossCalls(LiveInterval *interval)
 {
     // Split the interval to separate register uses and non-register uses and
     // allow the vreg to be spilled across its range.
     // Find the locations of all calls in the interval's range. Fixed intervals
     // are introduced by buildLivenessInfo only for calls when allocating for
     // the backtracking allocator. fixedIntervalsUnion is sorted backwards, so
     // iterate through it backwards.
     SplitPositionVector callPositions;
     for (size_t i = fixedIntervalsUnion->numRanges(); i > 0; i--) {
         const LiveInterval::Range *range = fixedIntervalsUnion->getRange(i - 1);
         if (interval->covers(range->from) && interval->covers(range->from.previous())) {
             if (!callPositions.append(range->from))
                 return false;
         }
     }
     JS_ASSERT(callPositions.length());
     return splitAt(interval, callPositions);
 }
 bool
 BacktrackingAllocator::chooseIntervalSplit(LiveInterval *interval, LiveInterval *conflict)
 {
     bool success = false;
     if (!trySplitAcrossHotcode(interval, &success))
         return false;
     if (success)
         return true;
     if (!trySplitAfterLastRegisterUse(interval, conflict, &success))
         return false;
     if (success)
         return true;
     return splitAtAllRegisterUses(interval);
 }

The Tor Browser / annotate

js/src/jit/BacktrackingAllocator.cpp@6474c204b198 (annotated)

js/src/jit/BacktrackingAllocator.cpp