diff -r 000000000000 -r 6474c204b198 js/src/jit/BacktrackingAllocator.cpp --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/js/src/jit/BacktrackingAllocator.cpp Wed Dec 31 06:09:35 2014 +0100 @@ -0,0 +1,1816 @@ +/* -*- 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 ® = 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 ® = 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 ® = 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 ® = 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 ® = 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 ® = 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 ® = 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 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(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(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(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 ® = 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); +}