Google Git
Sign in
cobalt / cobalt / c73ce7d5dfce7ae20bcc30efc5f220e0fbac12b1 / . / src / third_party / mozjs-45 / js / src / jit / BacktrackingAllocator.cpp
blob: 85ddab2484599a5ac24438de100b2583ba141ed7 [file] [log] [blame]
/* -*- 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 "jsprf.h"
#include "jit/BitSet.h"
using namespace js;
using namespace js::jit;
using mozilla::DebugOnly;
/////////////////////////////////////////////////////////////////////
// Utility
/////////////////////////////////////////////////////////////////////
static inline bool
SortBefore(UsePosition* a, UsePosition* b)
{
return a->pos <= b->pos;
}
static inline bool
SortBefore(LiveRange::BundleLink* a, LiveRange::BundleLink* b)
{
LiveRange* rangea = LiveRange::get(a);
LiveRange* rangeb = LiveRange::get(b);
MOZ_ASSERT(!rangea->intersects(rangeb));
return rangea->from() < rangeb->from();
}
static inline bool
SortBefore(LiveRange::RegisterLink* a, LiveRange::RegisterLink* b)
{
return LiveRange::get(a)->from() <= LiveRange::get(b)->from();
}
template <typename T>
static inline void
InsertSortedList(InlineForwardList<T> &list, T* value)
{
if (list.empty()) {
list.pushFront(value);
return;
}
if (SortBefore(list.back(), value)) {
list.pushBack(value);
return;
}
T* prev = nullptr;
for (InlineForwardListIterator<T> iter = list.begin(); iter; iter++) {
if (SortBefore(value, *iter))
break;
prev = *iter;
}
if (prev)
list.insertAfter(prev, value);
else
list.pushFront(value);
}
/////////////////////////////////////////////////////////////////////
// LiveRange
/////////////////////////////////////////////////////////////////////
void
LiveRange::addUse(UsePosition* use)
{
MOZ_ASSERT(covers(use->pos));
InsertSortedList(uses_, use);
}
void
LiveRange::distributeUses(LiveRange* other)
{
MOZ_ASSERT(other->vreg() == vreg());
MOZ_ASSERT(this != other);
// Move over all uses which fit in |other|'s boundaries.
for (UsePositionIterator iter = usesBegin(); iter; ) {
UsePosition* use = *iter;
if (other->covers(use->pos)) {
uses_.removeAndIncrement(iter);
other->addUse(use);
} else {
iter++;
}
}
// Distribute the definition to |other| as well, if possible.
if (hasDefinition() && from() == other->from())
other->setHasDefinition();
}
bool
LiveRange::contains(LiveRange* other) const
{
return from() <= other->from() && to() >= other->to();
}
void
LiveRange::intersect(LiveRange* other, Range* pre, Range* inside, Range* post) const
{
MOZ_ASSERT(pre->empty() && inside->empty() && post->empty());
CodePosition innerFrom = from();
if (from() < other->from()) {
if (to() < other->from()) {
*pre = range_;
return;
}
*pre = Range(from(), other->from());
innerFrom = other->from();
}
CodePosition innerTo = to();
if (to() > other->to()) {
if (from() >= other->to()) {
*post = range_;
return;
}
*post = Range(other->to(), to());
innerTo = other->to();
}
if (innerFrom != innerTo)
*inside = Range(innerFrom, innerTo);
}
bool
LiveRange::intersects(LiveRange* other) const
{
Range pre, inside, post;
intersect(other, &pre, &inside, &post);
return !inside.empty();
}
/////////////////////////////////////////////////////////////////////
// SpillSet
/////////////////////////////////////////////////////////////////////
void
SpillSet::setAllocation(LAllocation alloc)
{
for (size_t i = 0; i < numSpilledBundles(); i++)
spilledBundle(i)->setAllocation(alloc);
}
/////////////////////////////////////////////////////////////////////
// LiveBundle
/////////////////////////////////////////////////////////////////////
#ifdef DEBUG
size_t
LiveBundle::numRanges() const
{
size_t count = 0;
for (LiveRange::BundleLinkIterator iter = rangesBegin(); iter; iter++)
count++;
return count;
}
#endif // DEBUG
LiveRange*
LiveBundle::rangeFor(CodePosition pos) const
{
for (LiveRange::BundleLinkIterator iter = rangesBegin(); iter; iter++) {
LiveRange* range = LiveRange::get(*iter);
if (range->covers(pos))
return range;
}
return nullptr;
}
void
LiveBundle::addRange(LiveRange* range)
{
MOZ_ASSERT(!range->bundle());
range->setBundle(this);
InsertSortedList(ranges_, &range->bundleLink);
}
bool
LiveBundle::addRange(TempAllocator& alloc, uint32_t vreg, CodePosition from, CodePosition to)
{
LiveRange* range = LiveRange::New(alloc, vreg, from, to);
if (!range)
return false;
addRange(range);
return true;
}
bool
LiveBundle::addRangeAndDistributeUses(TempAllocator& alloc, LiveRange* oldRange,
CodePosition from, CodePosition to)
{
LiveRange* range = LiveRange::New(alloc, oldRange->vreg(), from, to);
if (!range)
return false;
addRange(range);
oldRange->distributeUses(range);
return true;
}
LiveRange*
LiveBundle::popFirstRange()
{
LiveRange::BundleLinkIterator iter = rangesBegin();
if (!iter)
return nullptr;
LiveRange* range = LiveRange::get(*iter);
ranges_.removeAt(iter);
range->setBundle(nullptr);
return range;
}
void
LiveBundle::removeRange(LiveRange* range)
{
for (LiveRange::BundleLinkIterator iter = rangesBegin(); iter; iter++) {
LiveRange* existing = LiveRange::get(*iter);
if (existing == range) {
ranges_.removeAt(iter);
return;
}
}
MOZ_CRASH();
}
/////////////////////////////////////////////////////////////////////
// VirtualRegister
/////////////////////////////////////////////////////////////////////
bool
VirtualRegister::addInitialRange(TempAllocator& alloc, CodePosition from, CodePosition to)
{
MOZ_ASSERT(from < to);
// Mark [from,to) as a live range for this register during the initial
// liveness analysis, coalescing with any existing overlapping ranges.
LiveRange* prev = nullptr;
LiveRange* merged = nullptr;
for (LiveRange::RegisterLinkIterator iter(rangesBegin()); iter; ) {
LiveRange* existing = LiveRange::get(*iter);
if (from > existing->to()) {
// The new range should go after this one.
prev = existing;
iter++;
continue;
}
if (to.next() < existing->from()) {
// The new range should go before this one.
break;
}
if (!merged) {
// This is the first old range we've found that overlaps the new
// range. Extend this one to cover its union with the new range.
merged = existing;
if (from < existing->from())
existing->setFrom(from);
if (to > existing->to())
existing->setTo(to);
// Continue searching to see if any other old ranges can be
// coalesced with the new merged range.
iter++;
continue;
}
// Coalesce this range into the previous range we merged into.
MOZ_ASSERT(existing->from() >= merged->from());
if (existing->to() > merged->to())
merged->setTo(existing->to());
MOZ_ASSERT(!existing->hasDefinition());
existing->distributeUses(merged);
MOZ_ASSERT(!existing->hasUses());
ranges_.removeAndIncrement(iter);
}
if (!merged) {
// The new range does not overlap any existing range for the vreg.
LiveRange* range = LiveRange::New(alloc, vreg(), from, to);
if (!range)
return false;
if (prev)
ranges_.insertAfter(&prev->registerLink, &range->registerLink);
else
ranges_.pushFront(&range->registerLink);
}
return true;
}
void
VirtualRegister::addInitialUse(UsePosition* use)
{
LiveRange::get(*rangesBegin())->addUse(use);
}
void
VirtualRegister::setInitialDefinition(CodePosition from)
{
LiveRange* first = LiveRange::get(*rangesBegin());
MOZ_ASSERT(from >= first->from());
first->setFrom(from);
first->setHasDefinition();
}
LiveRange*
VirtualRegister::rangeFor(CodePosition pos, bool preferRegister /* = false */) const
{
LiveRange* found = nullptr;
for (LiveRange::RegisterLinkIterator iter = rangesBegin(); iter; iter++) {
LiveRange* range = LiveRange::get(*iter);
if (range->covers(pos)) {
if (!preferRegister || range->bundle()->allocation().isRegister())
return range;
if (!found)
found = range;
}
}
return found;
}
void
VirtualRegister::addRange(LiveRange* range)
{
InsertSortedList(ranges_, &range->registerLink);
}
void
VirtualRegister::removeRange(LiveRange* range)
{
for (LiveRange::RegisterLinkIterator iter = rangesBegin(); iter; iter++) {
LiveRange* existing = LiveRange::get(*iter);
if (existing == range) {
ranges_.removeAt(iter);
return;
}
}
MOZ_CRASH();
}
/////////////////////////////////////////////////////////////////////
// BacktrackingAllocator
/////////////////////////////////////////////////////////////////////
// This function pre-allocates and initializes as much global state as possible
// to avoid littering the algorithms with memory management cruft.
bool
BacktrackingAllocator::init()
{
if (!RegisterAllocator::init())
return false;
liveIn = mir->allocate<BitSet>(graph.numBlockIds());
if (!liveIn)
return false;
callRanges = LiveBundle::New(alloc(), nullptr, nullptr);
size_t numVregs = graph.numVirtualRegisters();
if (!vregs.init(mir->alloc(), numVregs))
return false;
memset(&vregs[0], 0, sizeof(VirtualRegister) * numVregs);
for (uint32_t i = 0; i < numVregs; i++)
new(&vregs[i]) VirtualRegister();
// Build virtual register objects.
for (size_t i = 0; i < graph.numBlocks(); i++) {
if (mir->shouldCancel("Create data structures (main loop)"))
return false;
LBlock* block = graph.getBlock(i);
for (LInstructionIterator ins = block->begin(); ins != block->end(); ins++) {
for (size_t j = 0; j < ins->numDefs(); j++) {
LDefinition* def = ins->getDef(j);
if (def->isBogusTemp())
continue;
vreg(def).init(*ins, def, /* isTemp = */ false);
}
for (size_t j = 0; j < ins->numTemps(); j++) {
LDefinition* def = ins->getTemp(j);
if (def->isBogusTemp())
continue;
vreg(def).init(*ins, def, /* isTemp = */ true);
}
}
for (size_t j = 0; j < block->numPhis(); j++) {
LPhi* phi = block->getPhi(j);
LDefinition* def = phi->getDef(0);
vreg(def).init(phi, def, /* isTemp = */ false);
}
}
LiveRegisterSet remainingRegisters(allRegisters_.asLiveSet());
while (!remainingRegisters.emptyGeneral()) {
AnyRegister reg = AnyRegister(remainingRegisters.takeAnyGeneral());
registers[reg.code()].allocatable = true;
}
while (!remainingRegisters.emptyFloat()) {
AnyRegister reg = AnyRegister(remainingRegisters.takeAnyFloat());
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);
}
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.
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();
LiveRange* range = LiveRange::New(alloc(), 0, entryOf(header), exitOf(block).next());
if (!range || !hotcode.insert(range))
return false;
}
}
return true;
}
bool
BacktrackingAllocator::addInitialFixedRange(AnyRegister reg, CodePosition from, CodePosition to)
{
LiveRange* range = LiveRange::New(alloc(), 0, from, to);
return range && registers[reg.code()].allocations.insert(range);
}
#ifdef DEBUG
// Returns true iff ins has a def/temp reusing the input allocation.
static bool
IsInputReused(LInstruction* ins, LUse* use)
{
for (size_t i = 0; i < ins->numDefs(); i++) {
if (ins->getDef(i)->policy() == LDefinition::MUST_REUSE_INPUT &&
ins->getOperand(ins->getDef(i)->getReusedInput())->toUse() == use)
{
return true;
}
}
for (size_t i = 0; i < ins->numTemps(); i++) {
if (ins->getTemp(i)->policy() == LDefinition::MUST_REUSE_INPUT &&
ins->getOperand(ins->getTemp(i)->getReusedInput())->toUse() == use)
{
return true;
}
}
return false;
}
#endif
/*
* This function builds up liveness ranges for all virtual registers
* defined in the function. Additionally, it populates the liveIn array with
* information about which registers are live at the beginning of a block, to
* aid resolution and reification in a later phase.
*
* The algorithm is based on the one published in:
*
* Wimmer, Christian, and Michael Franz. "Linear Scan Register Allocation on
* SSA Form." Proceedings of the International Symposium on Code Generation
* and Optimization. Toronto, Ontario, Canada, ACM. 2010. 170-79. PDF.
*
* The algorithm operates on blocks ordered such that dominators of a block
* are before the block itself, and such that all blocks of a loop are
* contiguous. It proceeds backwards over the instructions in this order,
* marking registers live at their uses, ending their live ranges at
* definitions, and recording which registers are live at the top of every
* block. To deal with loop backedges, registers live at the beginning of
* a loop gain a range covering the entire loop.
*/
bool
BacktrackingAllocator::buildLivenessInfo()
{
JitSpew(JitSpew_RegAlloc, "Beginning liveness analysis");
Vector<MBasicBlock*, 1, SystemAllocPolicy> loopWorkList;
BitSet loopDone(graph.numBlockIds());
if (!loopDone.init(alloc()))
return false;
for (size_t i = graph.numBlocks(); i > 0; i--) {
if (mir->shouldCancel("Build Liveness Info (main loop)"))
return false;
LBlock* block = graph.getBlock(i - 1);
MBasicBlock* mblock = block->mir();
BitSet& live = liveIn[mblock->id()];
new (&live) BitSet(graph.numVirtualRegisters());
if (!live.init(alloc()))
return false;
// Propagate liveIn from our successors to us.
for (size_t i = 0; i < mblock->lastIns()->numSuccessors(); i++) {
MBasicBlock* successor = mblock->lastIns()->getSuccessor(i);
// Skip backedges, as we fix them up at the loop header.
if (mblock->id() < successor->id())
live.insertAll(liveIn[successor->id()]);
}
// Add successor phis.
if (mblock->successorWithPhis()) {
LBlock* phiSuccessor = mblock->successorWithPhis()->lir();
for (unsigned int j = 0; j < phiSuccessor->numPhis(); j++) {
LPhi* phi = phiSuccessor->getPhi(j);
LAllocation* use = phi->getOperand(mblock->positionInPhiSuccessor());
uint32_t reg = use->toUse()->virtualRegister();
live.insert(reg);
vreg(use).setUsedByPhi();
}
}
// Registers are assumed alive for the entire block, a define shortens
// the range to the point of definition.
for (BitSet::Iterator liveRegId(live); liveRegId; ++liveRegId) {
if (!vregs[*liveRegId].addInitialRange(alloc(), entryOf(block), exitOf(block).next()))
return false;
}
// Shorten the front end of ranges for live variables to their point of
// definition, if found.
for (LInstructionReverseIterator ins = block->rbegin(); ins != block->rend(); ins++) {
// Calls may clobber registers, so force a spill and reload around the callsite.
if (ins->isCall()) {
for (AnyRegisterIterator iter(allRegisters_.asLiveSet()); iter.more(); iter++) {
bool found = false;
for (size_t i = 0; i < ins->numDefs(); i++) {
if (ins->getDef(i)->isFixed() &&
ins->getDef(i)->output()->aliases(LAllocation(*iter))) {
found = true;
break;
}
}
if (!found) {
if (!addInitialFixedRange(*iter, outputOf(*ins), outputOf(*ins).next()))
return false;
}
}
if (!callRanges->addRange(alloc(), 0, outputOf(*ins), outputOf(*ins).next()))
return false;
}
DebugOnly<bool> hasDoubleDef = false;
DebugOnly<bool> hasFloat32Def = false;
for (size_t i = 0; i < ins->numDefs(); i++) {
LDefinition* def = ins->getDef(i);
if (def->isBogusTemp())
continue;
#ifdef DEBUG
if (def->type() == LDefinition::DOUBLE)
hasDoubleDef = true;
if (def->type() == LDefinition::FLOAT32)
hasFloat32Def = true;
#endif
CodePosition from = outputOf(*ins);
if (def->policy() == LDefinition::MUST_REUSE_INPUT) {
// MUST_REUSE_INPUT is implemented by allocating an output
// register and moving the input to it. Register hints are
// used to avoid unnecessary moves. We give the input an
// LUse::ANY policy to avoid allocating a register for the
// input.
LUse* inputUse = ins->getOperand(def->getReusedInput())->toUse();
MOZ_ASSERT(inputUse->policy() == LUse::REGISTER);
MOZ_ASSERT(inputUse->usedAtStart());
*inputUse = LUse(inputUse->virtualRegister(), LUse::ANY, /* usedAtStart = */ true);
}
if (!vreg(def).addInitialRange(alloc(), from, from.next()))
return false;
vreg(def).setInitialDefinition(from);
live.remove(def->virtualRegister());
}
for (size_t i = 0; i < ins->numTemps(); i++) {
LDefinition* temp = ins->getTemp(i);
if (temp->isBogusTemp())
continue;
// Normally temps are considered to cover both the input
// and output of the associated instruction. In some cases
// though we want to use a fixed register as both an input
// and clobbered register in the instruction, so watch for
// this and shorten the temp to cover only the output.
CodePosition from = inputOf(*ins);
if (temp->policy() == LDefinition::FIXED) {
AnyRegister reg = temp->output()->toRegister();
for (LInstruction::InputIterator alloc(**ins); alloc.more(); alloc.next()) {
if (alloc->isUse()) {
LUse* use = alloc->toUse();
if (use->isFixedRegister()) {
if (GetFixedRegister(vreg(use).def(), use) == reg)
from = outputOf(*ins);
}
}
}
}
CodePosition to =
ins->isCall() ? outputOf(*ins) : outputOf(*ins).next();
if (!vreg(temp).addInitialRange(alloc(), from, to))
return false;
vreg(temp).setInitialDefinition(from);
}
DebugOnly<bool> hasUseRegister = false;
DebugOnly<bool> hasUseRegisterAtStart = false;
for (LInstruction::InputIterator inputAlloc(**ins); inputAlloc.more(); inputAlloc.next()) {
if (inputAlloc->isUse()) {
LUse* use = inputAlloc->toUse();
// Call uses should always be at-start or fixed, since
// calls use all registers.
MOZ_ASSERT_IF(ins->isCall() && !inputAlloc.isSnapshotInput(),
use->isFixedRegister() || use->usedAtStart());
#ifdef DEBUG
// Don't allow at-start call uses if there are temps of the same kind,
// so that we don't assign the same register.
if (ins->isCall() && use->usedAtStart()) {
for (size_t i = 0; i < ins->numTemps(); i++)
MOZ_ASSERT(vreg(ins->getTemp(i)).type() != vreg(use).type());
}
// If there are both useRegisterAtStart(x) and useRegister(y)
// uses, we may assign the same register to both operands
// (bug 772830). Don't allow this for now.
if (use->policy() == LUse::REGISTER) {
if (use->usedAtStart()) {
if (!IsInputReused(*ins, use))
hasUseRegisterAtStart = true;
} else {
hasUseRegister = true;
}
}
MOZ_ASSERT(!(hasUseRegister && hasUseRegisterAtStart));
#endif
// Don't treat RECOVERED_INPUT uses as keeping the vreg alive.
if (use->policy() == LUse::RECOVERED_INPUT)
continue;
// Fixed uses on calls are specially overridden to happen
// at the input position.
CodePosition to =
(use->usedAtStart() || (ins->isCall() && use->isFixedRegister()))
? inputOf(*ins)
: outputOf(*ins);
if (use->isFixedRegister()) {
LAllocation reg(AnyRegister::FromCode(use->registerCode()));
for (size_t i = 0; i < ins->numDefs(); i++) {
LDefinition* def = ins->getDef(i);
if (def->policy() == LDefinition::FIXED && *def->output() == reg)
to = inputOf(*ins);
}
}
if (!vreg(use).addInitialRange(alloc(), entryOf(block), to.next()))
return false;
UsePosition* usePosition = new(alloc()) UsePosition(use, to);
if (!usePosition)
return false;
vreg(use).addInitialUse(usePosition);
live.insert(use->virtualRegister());
}
}
}
// Phis have simultaneous assignment semantics at block begin, so at
// the beginning of the block we can be sure that liveIn does not
// contain any phi outputs.
for (unsigned int i = 0; i < block->numPhis(); i++) {
LDefinition* def = block->getPhi(i)->getDef(0);
if (live.contains(def->virtualRegister())) {
live.remove(def->virtualRegister());
} else {
// This is a dead phi, so add a dummy range over all phis. This
// can go away if we have an earlier dead code elimination pass.
CodePosition entryPos = entryOf(block);
if (!vreg(def).addInitialRange(alloc(), entryPos, entryPos.next()))
return false;
}
}
if (mblock->isLoopHeader()) {
// A divergence from the published algorithm is required here, as
// our block order does not guarantee that blocks of a loop are
// contiguous. As a result, a single live range spanning the
// loop is not possible. Additionally, we require liveIn in a later
// pass for resolution, so that must also be fixed up here.
MBasicBlock* loopBlock = mblock->backedge();
while (true) {
// Blocks must already have been visited to have a liveIn set.
MOZ_ASSERT(loopBlock->id() >= mblock->id());
// Add a range for this entire loop block
CodePosition from = entryOf(loopBlock->lir());
CodePosition to = exitOf(loopBlock->lir()).next();
for (BitSet::Iterator liveRegId(live); liveRegId; ++liveRegId) {
if (!vregs[*liveRegId].addInitialRange(alloc(), from, to))
return false;
}
// Fix up the liveIn set.
liveIn[loopBlock->id()].insertAll(live);
// Make sure we don't visit this node again
loopDone.insert(loopBlock->id());
// If this is the loop header, any predecessors are either the
// backedge or out of the loop, so skip any predecessors of
// this block
if (loopBlock != mblock) {
for (size_t i = 0; i < loopBlock->numPredecessors(); i++) {
MBasicBlock* pred = loopBlock->getPredecessor(i);
if (loopDone.contains(pred->id()))
continue;
if (!loopWorkList.append(pred))
return false;
}
}
// Terminate loop if out of work.
if (loopWorkList.empty())
break;
// Grab the next block off the work list, skipping any OSR block.
MBasicBlock* osrBlock = graph.mir().osrBlock();
while (!loopWorkList.empty()) {
loopBlock = loopWorkList.popCopy();
if (loopBlock != osrBlock)
break;
}
// If end is reached without finding a non-OSR block, then no more work items were found.
if (loopBlock == osrBlock) {
MOZ_ASSERT(loopWorkList.empty());
break;
}
}
// Clear the done set for other loops
loopDone.clear();
}
MOZ_ASSERT_IF(!mblock->numPredecessors(), live.empty());
}
JitSpew(JitSpew_RegAlloc, "Liveness analysis complete");
if (JitSpewEnabled(JitSpew_RegAlloc))
dumpInstructions();
return true;
}
bool
BacktrackingAllocator::go()
{
JitSpew(JitSpew_RegAlloc, "Beginning register allocation");
if (!init())
return false;
if (!buildLivenessInfo())
return false;
if (JitSpewEnabled(JitSpew_RegAlloc))
dumpFixedRanges();
if (!allocationQueue.reserve(graph.numVirtualRegisters() * 3 / 2))
return false;
JitSpew(JitSpew_RegAlloc, "Beginning grouping and queueing registers");
if (!mergeAndQueueRegisters())
return false;
if (JitSpewEnabled(JitSpew_RegAlloc))
dumpVregs();
JitSpew(JitSpew_RegAlloc, "Beginning main allocation loop");
// Allocate, spill and split bundles until finished.
while (!allocationQueue.empty()) {
if (mir->shouldCancel("Backtracking Allocation"))
return false;
QueueItem item = allocationQueue.removeHighest();
if (!processBundle(item.bundle))
return false;
}
JitSpew(JitSpew_RegAlloc, "Main allocation loop complete");
if (!pickStackSlots())
return false;
if (JitSpewEnabled(JitSpew_RegAlloc))
dumpAllocations();
if (!resolveControlFlow())
return false;
if (!reifyAllocations())
return false;
if (!populateSafepoints())
return false;
if (!annotateMoveGroups())
return false;
return true;
}
static bool
IsArgumentSlotDefinition(LDefinition* def)
{
return def->policy() == LDefinition::FIXED && def->output()->isArgument();
}
static bool
IsThisSlotDefinition(LDefinition* def)
{
return IsArgumentSlotDefinition(def) &&
def->output()->toArgument()->index() < THIS_FRAME_ARGSLOT + sizeof(Value);
}
bool
BacktrackingAllocator::tryMergeBundles(LiveBundle* bundle0, LiveBundle* bundle1)
{
// See if bundle0 and bundle1 can be merged together.
if (bundle0 == bundle1)
return true;
// Get a representative virtual register from each bundle.
VirtualRegister& reg0 = vregs[bundle0->firstRange()->vreg()];
VirtualRegister& reg1 = vregs[bundle1->firstRange()->vreg()];
if (!reg0.isCompatible(reg1))
return true;
// Registers which might spill to the frame's |this| slot can only be
// grouped with other such registers. The frame's |this| slot must always
// hold the |this| value, as required by JitFrame tracing and by the Ion
// constructor calling convention.
if (IsThisSlotDefinition(reg0.def()) || IsThisSlotDefinition(reg1.def())) {
if (*reg0.def()->output() != *reg1.def()->output())
return true;
}
// Registers which might spill to the frame's argument slots can only be
// grouped with other such registers if the frame might access those
// arguments through a lazy arguments object or rest parameter.
if (IsArgumentSlotDefinition(reg0.def()) || IsArgumentSlotDefinition(reg1.def())) {
if (graph.mir().entryBlock()->info().mayReadFrameArgsDirectly()) {
if (*reg0.def()->output() != *reg1.def()->output())
return true;
}
}
// Limit the number of times we compare ranges if there are many ranges in
// one of the bundles, to avoid quadratic behavior.
static const size_t MAX_RANGES = 200;
// Make sure that ranges in the bundles do not overlap.
LiveRange::BundleLinkIterator iter0 = bundle0->rangesBegin(), iter1 = bundle1->rangesBegin();
size_t count = 0;
while (iter0 && iter1) {
if (++count >= MAX_RANGES)
return true;
LiveRange* range0 = LiveRange::get(*iter0);
LiveRange* range1 = LiveRange::get(*iter1);
if (range0->from() >= range1->to())
iter1++;
else if (range1->from() >= range0->to())
iter0++;
else
return true;
}
// Move all ranges from bundle1 into bundle0.
while (LiveRange* range = bundle1->popFirstRange())
bundle0->addRange(range);
return true;
}
static inline LDefinition*
FindReusingDefinition(LNode* ins, LAllocation* alloc)
{
for (size_t i = 0; i < ins->numDefs(); i++) {
LDefinition* def = ins->getDef(i);
if (def->policy() == LDefinition::MUST_REUSE_INPUT &&
ins->getOperand(def->getReusedInput()) == alloc)
return def;
}
for (size_t i = 0; i < ins->numTemps(); i++) {
LDefinition* def = ins->getTemp(i);
if (def->policy() == LDefinition::MUST_REUSE_INPUT &&
ins->getOperand(def->getReusedInput()) == alloc)
return def;
}
return nullptr;
}
bool
BacktrackingAllocator::tryMergeReusedRegister(VirtualRegister& def, VirtualRegister& input)
{
// def is a vreg which reuses input for its output physical register. Try
// to merge ranges for def with those of input if possible, as avoiding
// copies before def's instruction is crucial for generated code quality
// (MUST_REUSE_INPUT is used for all arithmetic on x86/x64).
if (def.rangeFor(inputOf(def.ins()))) {
MOZ_ASSERT(def.isTemp());
def.setMustCopyInput();
return true;
}
LiveRange* inputRange = input.rangeFor(outputOf(def.ins()));
if (!inputRange) {
// 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 tryMergeBundles(def.firstBundle(), input.firstBundle());
}
// 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 input into two bundles at the
// point of the definition, which may permit merging. 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.
LBlock* block = def.ins()->block();
// The input's lifetime must end within the same block as the definition,
// otherwise it could live on in phis elsewhere.
if (inputRange != input.lastRange() || inputRange->to() > exitOf(block)) {
def.setMustCopyInput();
return true;
}
// If we already split the input for some other register, don't make a
// third bundle.
if (inputRange->bundle() != input.firstRange()->bundle()) {
def.setMustCopyInput();
return true;
}
// If the input will start out in memory then adding a separate bundle for
// memory uses after the def won't help.
if (input.def()->isFixed() && !input.def()->output()->isRegister()) {
def.setMustCopyInput();
return true;
}
// The input cannot have register or reused uses after the definition.
for (UsePositionIterator iter = inputRange->usesBegin(); iter; iter++) {
if (iter->pos <= inputOf(def.ins()))
continue;
LUse* use = iter->use;
if (FindReusingDefinition(insData[iter->pos], use)) {
def.setMustCopyInput();
return true;
}
if (use->policy() != LUse::ANY && use->policy() != LUse::KEEPALIVE) {
def.setMustCopyInput();
return true;
}
}
LiveRange* preRange = LiveRange::New(alloc(), input.vreg(),
inputRange->from(), outputOf(def.ins()));
if (!preRange)
return false;
// The new range starts at reg's input position, which means it overlaps
// with the old range at one position. This is what we want, because we
// need to copy the input before the instruction.
LiveRange* postRange = LiveRange::New(alloc(), input.vreg(),
inputOf(def.ins()), inputRange->to());
if (!postRange)
return false;
inputRange->distributeUses(preRange);
inputRange->distributeUses(postRange);
MOZ_ASSERT(!inputRange->hasUses());
JitSpew(JitSpew_RegAlloc, " splitting reused input at %u to try to help grouping",
inputOf(def.ins()));
LiveBundle* firstBundle = inputRange->bundle();
input.removeRange(inputRange);
input.addRange(preRange);
input.addRange(postRange);
firstBundle->removeRange(inputRange);
firstBundle->addRange(preRange);
// The new range goes in a separate bundle, where it will be spilled during
// allocation.
LiveBundle* secondBundle = LiveBundle::New(alloc(), nullptr, nullptr);
if (!secondBundle)
return false;
secondBundle->addRange(postRange);
return tryMergeBundles(def.firstBundle(), input.firstBundle());
}
bool
BacktrackingAllocator::mergeAndQueueRegisters()
{
MOZ_ASSERT(!vregs[0u].hasRanges());
// Create a bundle for each register containing all its ranges.
for (size_t i = 1; i < graph.numVirtualRegisters(); i++) {
VirtualRegister& reg = vregs[i];
if (!reg.hasRanges())
continue;
LiveBundle* bundle = LiveBundle::New(alloc(), nullptr, nullptr);
if (!bundle)
return false;
for (LiveRange::RegisterLinkIterator iter = reg.rangesBegin(); iter; iter++) {
LiveRange* range = LiveRange::get(*iter);
bundle->addRange(range);
}
}
// If there is an OSR block, merge parameters in that block with the
// corresponding parameters in the initial block.
if (MBasicBlock* osr = graph.mir().osrBlock()) {
size_t original = 1;
for (LInstructionIterator iter = osr->lir()->begin(); iter != osr->lir()->end(); iter++) {
if (iter->isParameter()) {
for (size_t i = 0; i < iter->numDefs(); i++) {
DebugOnly<bool> found = false;
VirtualRegister &paramVreg = vreg(iter->getDef(i));
for (; original < paramVreg.vreg(); original++) {
VirtualRegister &originalVreg = vregs[original];
if (*originalVreg.def()->output() == *iter->getDef(i)->output()) {
MOZ_ASSERT(originalVreg.ins()->isParameter());
if (!tryMergeBundles(originalVreg.firstBundle(), paramVreg.firstBundle()))
return false;
found = true;
break;
}
}
MOZ_ASSERT(found);
}
}
}
}
// Try to merge registers with their reused inputs.
for (size_t i = 1; i < graph.numVirtualRegisters(); i++) {
VirtualRegister& reg = vregs[i];
if (!reg.hasRanges())
continue;
if (reg.def()->policy() == LDefinition::MUST_REUSE_INPUT) {
LUse* use = reg.ins()->getOperand(reg.def()->getReusedInput())->toUse();
if (!tryMergeReusedRegister(reg, vreg(use)))
return false;
}
}
// Try to merge 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);
VirtualRegister &outputVreg = vreg(phi->getDef(0));
for (size_t k = 0, kend = phi->numOperands(); k < kend; k++) {
VirtualRegister& inputVreg = vreg(phi->getOperand(k)->toUse());
if (!tryMergeBundles(inputVreg.firstBundle(), outputVreg.firstBundle()))
return false;
}
}
}
// Add all bundles to the allocation queue, and create spill sets for them.
for (size_t i = 1; i < graph.numVirtualRegisters(); i++) {
VirtualRegister& reg = vregs[i];
for (LiveRange::RegisterLinkIterator iter = reg.rangesBegin(); iter; iter++) {
LiveRange* range = LiveRange::get(*iter);
LiveBundle* bundle = range->bundle();
if (range == bundle->firstRange()) {
SpillSet* spill = SpillSet::New(alloc());
if (!spill)
return false;
bundle->setSpillSet(spill);
size_t priority = computePriority(bundle);
if (!allocationQueue.insert(QueueItem(bundle, priority)))
return false;
}
}
}
return true;
}
static const size_t MAX_ATTEMPTS = 2;
bool
BacktrackingAllocator::tryAllocateFixed(LiveBundle* bundle, Requirement requirement,
bool* success, bool* pfixed,
LiveBundleVector& conflicting)
{
// Spill bundles which are required to be in a certain stack slot.
if (!requirement.allocation().isRegister()) {
JitSpew(JitSpew_RegAlloc, " stack allocation requirement");
bundle->setAllocation(requirement.allocation());
*success = true;
return true;
}
AnyRegister reg = requirement.allocation().toRegister();
return tryAllocateRegister(registers[reg.code()], bundle, success, pfixed, conflicting);
}
bool
BacktrackingAllocator::tryAllocateNonFixed(LiveBundle* bundle,
Requirement requirement, Requirement hint,
bool* success, bool* pfixed,
LiveBundleVector& conflicting)
{
// If we want, but do not require a bundle 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 (hint.kind() == Requirement::FIXED) {
AnyRegister reg = hint.allocation().toRegister();
if (!tryAllocateRegister(registers[reg.code()], bundle, success, pfixed, conflicting))
return false;
if (*success)
return true;
}
// Spill bundles which have no hint or register requirement.
if (requirement.kind() == Requirement::NONE && hint.kind() != Requirement::REGISTER) {
if (!spill(bundle))
return false;
*success = true;
return true;
}
if (conflicting.empty() || minimalBundle(bundle)) {
// Search for any available register which the bundle can be
// allocated to.
for (size_t i = 0; i < AnyRegister::Total; i++) {
if (!tryAllocateRegister(registers[i], bundle, success, pfixed, conflicting))
return false;
if (*success)
return true;
}
}
// Spill bundles which have no register requirement if they didn't get
// allocated.
if (requirement.kind() == Requirement::NONE) {
if (!spill(bundle))
return false;
*success = true;
return true;
}
// We failed to allocate this bundle.
MOZ_ASSERT(!*success);
return true;
}
bool
BacktrackingAllocator::processBundle(LiveBundle* bundle)
{
if (JitSpewEnabled(JitSpew_RegAlloc)) {
JitSpew(JitSpew_RegAlloc, "Allocating %s [priority %lu] [weight %lu]",
bundle->toString(), computePriority(bundle), computeSpillWeight(bundle));
}
// A bundle can be processed by doing any of the following:
//
// - Assigning the bundle a register. The bundle cannot overlap any other
// bundle allocated for that physical register.
//
// - Spilling the bundle, provided it has no register uses.
//
// - Splitting the bundle into two or more bundles which cover the original
// one. The new bundles are placed back onto the priority queue for later
// processing.
//
// - Evicting one or more existing allocated bundles, and then doing one
// of the above operations. Evicted bundles are placed back on the
// priority queue. Any evicted bundles must have a lower spill weight
// than the bundle being processed.
//
// As long as this structure is followed, termination is guaranteed.
// In general, we want to minimize the amount of bundle splitting (which
// generally necessitates spills), so allocate longer lived, lower weight
// bundles first and evict and split them later if they prevent allocation
// for higher weight bundles.
Requirement requirement, hint;
bool canAllocate = computeRequirement(bundle, &requirement, &hint);
bool fixed;
LiveBundleVector conflicting;
for (size_t attempt = 0;; attempt++) {
if (canAllocate) {
bool success = false;
fixed = false;
conflicting.clear();
// Ok, let's try allocating for this bundle.
if (requirement.kind() == Requirement::FIXED) {
if (!tryAllocateFixed(bundle, requirement, &success, &fixed, conflicting))
return false;
} else {
if (!tryAllocateNonFixed(bundle, requirement, hint, &success, &fixed, conflicting))
return false;
}
// If that worked, we're done!
if (success)
return true;
// If that didn't work, but we have one or more non-fixed bundles
// known to be conflicting, maybe we can evict them and try again.
if (attempt < MAX_ATTEMPTS &&
!fixed &&
!conflicting.empty() &&
maximumSpillWeight(conflicting) < computeSpillWeight(bundle))
{
for (size_t i = 0; i < conflicting.length(); i++) {
if (!evictBundle(conflicting[i]))
return false;
}
continue;
}
}
// A minimal bundle cannot be split any further. If we try to split it
// it at this point we will just end up with the same bundle and will
// enter an infinite loop. Weights and the initial live ranges must
// be constructed so that any minimal bundle is allocatable.
MOZ_ASSERT(!minimalBundle(bundle));
LiveBundle* conflict = conflicting.empty() ? nullptr : conflicting[0];
return chooseBundleSplit(bundle, canAllocate && fixed, conflict);
}
}
bool
BacktrackingAllocator::computeRequirement(LiveBundle* bundle,
Requirement *requirement, Requirement *hint)
{
// Set any requirement or hint on bundle according to its definition and
// uses. Return false if there are conflicting requirements which will
// require the bundle to be split.
for (LiveRange::BundleLinkIterator iter = bundle->rangesBegin(); iter; iter++) {
LiveRange* range = LiveRange::get(*iter);
VirtualRegister &reg = vregs[range->vreg()];
if (range->hasDefinition()) {
// Deal with any definition constraints/hints.
LDefinition::Policy policy = reg.def()->policy();
if (policy == LDefinition::FIXED) {
// Fixed policies get a FIXED requirement.
JitSpew(JitSpew_RegAlloc, " Requirement %s, fixed by definition",
reg.def()->output()->toString());
if (!requirement->merge(Requirement(*reg.def()->output())))
return false;
} 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.
if (!requirement->merge(Requirement(Requirement::REGISTER)))
return false;
}
}
// Search uses for requirements.
for (UsePositionIterator iter = range->usesBegin(); iter; iter++) {
LUse::Policy policy = iter->use->policy();
if (policy == LUse::FIXED) {
AnyRegister required = GetFixedRegister(reg.def(), iter->use);
JitSpew(JitSpew_RegAlloc, " Requirement %s, due to use at %u",
required.name(), iter->pos.bits());
// If there are multiple fixed registers which the bundle is
// required to use, fail. The bundle will need to be split before
// it can be allocated.
if (!requirement->merge(Requirement(LAllocation(required))))
return false;
} else if (policy == LUse::REGISTER) {
if (!requirement->merge(Requirement(Requirement::REGISTER)))
return false;
} else if (policy == LUse::ANY) {
// ANY differs from KEEPALIVE by actively preferring a register.
hint->merge(Requirement(Requirement::REGISTER));
}
}
}
return true;
}
bool
BacktrackingAllocator::tryAllocateRegister(PhysicalRegister& r, LiveBundle* bundle,
bool* success, bool* pfixed, LiveBundleVector& conflicting)
{
*success = false;
if (!r.allocatable)
return true;
LiveBundleVector aliasedConflicting;
for (LiveRange::BundleLinkIterator iter = bundle->rangesBegin(); iter; iter++) {
LiveRange* range = LiveRange::get(*iter);
VirtualRegister &reg = vregs[range->vreg()];
if (!reg.isCompatible(r.reg))
return true;
for (size_t a = 0; a < r.reg.numAliased(); a++) {
PhysicalRegister& rAlias = registers[r.reg.aliased(a).code()];
LiveRange* existing;
if (!rAlias.allocations.contains(range, &existing))
continue;
if (existing->hasVreg()) {
MOZ_ASSERT(existing->bundle()->allocation().toRegister() == rAlias.reg);
bool duplicate = false;
for (size_t i = 0; i < aliasedConflicting.length(); i++) {
if (aliasedConflicting[i] == existing->bundle()) {
duplicate = true;
break;
}
}
if (!duplicate && !aliasedConflicting.append(existing->bundle()))
return false;
} else {
JitSpew(JitSpew_RegAlloc, " %s collides with fixed use %s",
rAlias.reg.name(), existing->toString());
*pfixed = true;
return true;
}
}
}
if (!aliasedConflicting.empty()) {
// One or more aliased registers is allocated to another bundle
// overlapping this one. Keep track of the conflicting set, and in the
// case of multiple conflicting sets keep track of the set with the
// lowest maximum spill weight.
// The #ifdef guards against "unused variable 'existing'" bustage.
#ifdef JS_JITSPEW
if (JitSpewEnabled(JitSpew_RegAlloc)) {
if (aliasedConflicting.length() == 1) {
LiveBundle* existing = aliasedConflicting[0];
JitSpew(JitSpew_RegAlloc, " %s collides with %s [weight %lu]",
r.reg.name(), existing->toString(), computeSpillWeight(existing));
} else {
JitSpew(JitSpew_RegAlloc, " %s collides with the following", r.reg.name());
for (size_t i = 0; i < aliasedConflicting.length(); i++) {
LiveBundle* existing = aliasedConflicting[i];
JitSpew(JitSpew_RegAlloc, " %s [weight %lu]",
existing->toString(), computeSpillWeight(existing));
}
}
}
#endif
if (conflicting.empty()) {
if (!conflicting.appendAll(aliasedConflicting))
return false;
} else {
if (maximumSpillWeight(aliasedConflicting) < maximumSpillWeight(conflicting)) {
conflicting.clear();
if (!conflicting.appendAll(aliasedConflicting))
return false;
}
}
return true;
}
JitSpew(JitSpew_RegAlloc, " allocated to %s", r.reg.name());
for (LiveRange::BundleLinkIterator iter = bundle->rangesBegin(); iter; iter++) {
LiveRange* range = LiveRange::get(*iter);
if (!r.allocations.insert(range))
return false;
}
bundle->setAllocation(LAllocation(r.reg));
*success = true;
return true;
}
bool
BacktrackingAllocator::evictBundle(LiveBundle* bundle)
{
if (JitSpewEnabled(JitSpew_RegAlloc)) {
JitSpew(JitSpew_RegAlloc, " Evicting %s [priority %lu] [weight %lu]",
bundle->toString(), computePriority(bundle), computeSpillWeight(bundle));
}
AnyRegister reg(bundle->allocation().toRegister());
PhysicalRegister& physical = registers[reg.code()];
MOZ_ASSERT(physical.reg == reg && physical.allocatable);
for (LiveRange::BundleLinkIterator iter = bundle->rangesBegin(); iter; iter++) {
LiveRange* range = LiveRange::get(*iter);
physical.allocations.remove(range);
}
bundle->setAllocation(LAllocation());
size_t priority = computePriority(bundle);
return allocationQueue.insert(QueueItem(bundle, priority));
}
bool
BacktrackingAllocator::splitAndRequeueBundles(LiveBundle* bundle,
const LiveBundleVector& newBundles)
{
if (JitSpewEnabled(JitSpew_RegAlloc)) {
JitSpew(JitSpew_RegAlloc, " splitting bundle %s into:", bundle->toString());
for (size_t i = 0; i < newBundles.length(); i++)
JitSpew(JitSpew_RegAlloc, " %s", newBundles[i]->toString());
}
// Remove all ranges in the old bundle from their register's list.
for (LiveRange::BundleLinkIterator iter = bundle->rangesBegin(); iter; iter++) {
LiveRange* range = LiveRange::get(*iter);
vregs[range->vreg()].removeRange(range);
}
// Add all ranges in the new bundles to their register's list.
for (size_t i = 0; i < newBundles.length(); i++) {
LiveBundle* newBundle = newBundles[i];
for (LiveRange::BundleLinkIterator iter = newBundle->rangesBegin(); iter; iter++) {
LiveRange* range = LiveRange::get(*iter);
vregs[range->vreg()].addRange(range);
}
}
// Queue the new bundles for register assignment.
for (size_t i = 0; i < newBundles.length(); i++) {
LiveBundle* newBundle = newBundles[i];
size_t priority = computePriority(newBundle);
if (!allocationQueue.insert(QueueItem(newBundle, priority)))
return false;
}
return true;
}
bool
BacktrackingAllocator::spill(LiveBundle* bundle)
{
JitSpew(JitSpew_RegAlloc, " Spilling bundle");
MOZ_ASSERT(bundle->allocation().isBogus());
if (LiveBundle* spillParent = bundle->spillParent()) {
JitSpew(JitSpew_RegAlloc, " Using existing spill bundle");
for (LiveRange::BundleLinkIterator iter = bundle->rangesBegin(); iter; iter++) {
LiveRange* range = LiveRange::get(*iter);
LiveRange* parentRange = spillParent->rangeFor(range->from());
MOZ_ASSERT(parentRange->contains(range));
MOZ_ASSERT(range->vreg() == parentRange->vreg());
range->distributeUses(parentRange);
MOZ_ASSERT(!range->hasUses());
vregs[range->vreg()].removeRange(range);
}
return true;
}
return bundle->spillSet()->addSpilledBundle(bundle);
}
bool
BacktrackingAllocator::pickStackSlots()
{
for (size_t i = 1; i < graph.numVirtualRegisters(); i++) {
VirtualRegister& reg = vregs[i];
if (mir->shouldCancel("Backtracking Pick Stack Slots"))
return false;
for (LiveRange::RegisterLinkIterator iter = reg.rangesBegin(); iter; iter++) {
LiveRange* range = LiveRange::get(*iter);
LiveBundle* bundle = range->bundle();
if (bundle->allocation().isBogus()) {
if (!pickStackSlot(bundle->spillSet()))
return false;
MOZ_ASSERT(!bundle->allocation().isBogus());
}
}
}
return true;
}
bool
BacktrackingAllocator::pickStackSlot(SpillSet* spillSet)
{
// Look through all ranges that have been spilled in this set for a
// register definition which is fixed to a stack or argument slot. If we
// find one, use it for all bundles that have been spilled. tryMergeBundles
// makes sure this reuse is possible when an initial bundle contains ranges
// from multiple virtual registers.
for (size_t i = 0; i < spillSet->numSpilledBundles(); i++) {
LiveBundle* bundle = spillSet->spilledBundle(i);
for (LiveRange::BundleLinkIterator iter = bundle->rangesBegin(); iter; iter++) {
LiveRange* range = LiveRange::get(*iter);
if (range->hasDefinition()) {
LDefinition* def = vregs[range->vreg()].def();
if (def->policy() == LDefinition::FIXED) {
MOZ_ASSERT(!def->output()->isRegister());
MOZ_ASSERT(!def->output()->isStackSlot());
spillSet->setAllocation(*def->output());
return true;
}
}
}
}
LDefinition::Type type = vregs[spillSet->spilledBundle(0)->firstRange()->vreg()].type();
SpillSlotList* slotList;
switch (StackSlotAllocator::width(type)) {
case 4: slotList = &normalSlots; break;
case 8: slotList = &doubleSlots; break;
case 16: slotList = &quadSlots; break;
default:
MOZ_CRASH("Bad width");
}
// Maximum number of existing spill slots we will look at before giving up
// and allocating a new slot.
static const size_t MAX_SEARCH_COUNT = 10;
size_t searches = 0;
SpillSlot* stop = nullptr;
while (!slotList->empty()) {
SpillSlot* spillSlot = *slotList->begin();
if (!stop) {
stop = spillSlot;
} else if (stop == spillSlot) {
// We looked through every slot in the list.
break;
}
bool success = true;
for (size_t i = 0; i < spillSet->numSpilledBundles(); i++) {
LiveBundle* bundle = spillSet->spilledBundle(i);
for (LiveRange::BundleLinkIterator iter = bundle->rangesBegin(); iter; iter++) {
LiveRange* range = LiveRange::get(*iter);
LiveRange* existing;
if (spillSlot->allocated.contains(range, &existing)) {
success = false;
break;
}
}
if (!success)
break;
}
if (success) {
// We can reuse this physical stack slot for the new bundles.
// Update the allocated ranges for the slot.
for (size_t i = 0; i < spillSet->numSpilledBundles(); i++) {
LiveBundle* bundle = spillSet->spilledBundle(i);
if (!insertAllRanges(spillSlot->allocated, bundle))
return false;
}
spillSet->setAllocation(spillSlot->alloc);
return true;
}
// On a miss, move the spill to the end of the list. This will cause us
// to make fewer attempts to allocate from slots with a large and
// highly contended range.
slotList->popFront();
slotList->pushBack(spillSlot);
if (++searches == MAX_SEARCH_COUNT)
break;
}
// We need a new physical stack slot.
uint32_t stackSlot = stackSlotAllocator.allocateSlot(type);
SpillSlot* spillSlot = new(alloc()) SpillSlot(stackSlot, alloc().lifoAlloc());
if (!spillSlot)
return false;
for (size_t i = 0; i < spillSet->numSpilledBundles(); i++) {
LiveBundle* bundle = spillSet->spilledBundle(i);
if (!insertAllRanges(spillSlot->allocated, bundle))
return false;
}
spillSet->setAllocation(spillSlot->alloc);
slotList->pushFront(spillSlot);
return true;
}
bool
BacktrackingAllocator::insertAllRanges(LiveRangeSet& set, LiveBundle* bundle)
{
for (LiveRange::BundleLinkIterator iter = bundle->rangesBegin(); iter; iter++) {
LiveRange* range = LiveRange::get(*iter);
if (!set.insert(range))
return false;
}
return true;
}
bool
BacktrackingAllocator::deadRange(LiveRange* range)
{
// Check for direct uses of this range.
if (range->hasUses() || range->hasDefinition())
return false;
CodePosition start = range->from();
LNode* ins = insData[start];
if (start == entryOf(ins->block()))
return false;
VirtualRegister& reg = vregs[range->vreg()];
// Check if there are later ranges for this vreg.
LiveRange::RegisterLinkIterator iter = reg.rangesBegin(range);
for (iter++; iter; iter++) {
LiveRange* laterRange = LiveRange::get(*iter);
if (laterRange->from() > range->from())
return false;
}
// Check if this range ends at a loop backedge.
LNode* last = insData[range->to().previous()];
if (last->isGoto() && last->toGoto()->target()->id() < last->block()->mir()->id())
return false;
// Check if there are phis which this vreg flows to.
if (reg.usedByPhi())
return false;
return true;
}
bool
BacktrackingAllocator::resolveControlFlow()
{
// Add moves to handle changing assignments for vregs over their lifetime.
JitSpew(JitSpew_RegAlloc, "Resolving control flow (vreg loop)");
// Look for places where a register's assignment changes in the middle of a
// basic block.
MOZ_ASSERT(!vregs[0u].hasRanges());
for (size_t i = 1; i < graph.numVirtualRegisters(); i++) {
VirtualRegister& reg = vregs[i];
if (mir->shouldCancel("Backtracking Resolve Control Flow (vreg loop)"))
return false;
if (!alloc().ensureBallast())
return false;
for (LiveRange::RegisterLinkIterator iter = reg.rangesBegin(); iter; ) {
LiveRange* range = LiveRange::get(*iter);
// Remove ranges which will never be used.
if (deadRange(range)) {
reg.removeRangeAndIncrement(iter);
continue;
}
// The range which defines the register does not have a predecessor
// to add moves from.
if (range->hasDefinition()) {
iter++;
continue;
}
// Ignore ranges that start at block boundaries. We will handle
// these in the next phase.
CodePosition start = range->from();
LNode* ins = insData[start];
if (start == entryOf(ins->block())) {
iter++;
continue;
}
// If we already saw a range which covers the start of this range
// and has the same allocation, we don't need an explicit move at
// the start of this range.
bool skip = false;
for (LiveRange::RegisterLinkIterator prevIter = reg.rangesBegin();
prevIter != iter;
prevIter++)
{
LiveRange* prevRange = LiveRange::get(*prevIter);
if (prevRange->covers(start) &&
prevRange->bundle()->allocation() == range->bundle()->allocation())
{
skip = true;
break;
}
}
if (skip) {
iter++;
continue;
}
LiveRange* predecessorRange = reg.rangeFor(start.previous(), /* preferRegister = */ true);
if (start.subpos() == CodePosition::INPUT) {
if (!moveInput(ins->toInstruction(), predecessorRange, range, reg.type()))
return false;
} else {
if (!moveAfter(ins->toInstruction(), predecessorRange, range, reg.type()))
return false;
}
iter++;
}
}
JitSpew(JitSpew_RegAlloc, "Resolving control flow (block loop)");
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);
MOZ_ASSERT(phi->numDefs() == 1);
LDefinition* def = phi->getDef(0);
VirtualRegister& reg = vreg(def);
LiveRange* to = reg.rangeFor(entryOf(successor));
MOZ_ASSERT(to);
for (size_t k = 0; k < mSuccessor->numPredecessors(); k++) {
LBlock* predecessor = mSuccessor->getPredecessor(k)->lir();
MOZ_ASSERT(predecessor->mir()->numSuccessors() == 1);
LAllocation* input = phi->getOperand(k);
LiveRange* from = vreg(input).rangeFor(exitOf(predecessor), /* preferRegister = */ true);
MOZ_ASSERT(from);
if (!moveAtExit(predecessor, from, to, def->type()))
return false;
}
}
// Add moves to resolve graph edges with different allocations at their
// source and target.
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 (LiveRange::RegisterLinkIterator iter = reg.rangesBegin(); iter; iter++) {
LiveRange* to = LiveRange::get(*iter);
if (!to->covers(entryOf(successor)))
continue;
if (to->covers(exitOf(predecessor)))
continue;
LiveRange* from = reg.rangeFor(exitOf(predecessor), /* preferRegister = */ true);
if (mSuccessor->numPredecessors() > 1) {
MOZ_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, LNode* ins, bool considerCopy)
{
if (LDefinition* def = FindReusingDefinition(ins, use))
return considerCopy || !vregs[def->virtualRegister()].mustCopyInput();
return false;
}
bool
BacktrackingAllocator::isRegisterUse(LUse* use, LNode* 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(LiveRange* range)
{
if (!range->hasDefinition())
return false;
VirtualRegister& reg = vregs[range->vreg()];
if (reg.ins()->isPhi())
return false;
if (reg.def()->policy() == LDefinition::FIXED && !reg.def()->output()->isRegister())
return false;
return true;
}
bool
BacktrackingAllocator::reifyAllocations()
{
JitSpew(JitSpew_RegAlloc, "Reifying Allocations");
MOZ_ASSERT(!vregs[0u].hasRanges());
for (size_t i = 1; i < graph.numVirtualRegisters(); i++) {
VirtualRegister& reg = vregs[i];
if (mir->shouldCancel("Backtracking Reify Allocations (main loop)"))
return false;
for (LiveRange::RegisterLinkIterator iter = reg.rangesBegin(); iter; iter++) {
LiveRange* range = LiveRange::get(*iter);
if (range->hasDefinition()) {
reg.def()->setOutput(range->bundle()->allocation());
if (reg.ins()->recoversInput()) {
LSnapshot* snapshot = reg.ins()->toInstruction()->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(range->usesBegin()); iter; iter++) {
LAllocation* alloc = iter->use;
*alloc = range->bundle()->allocation();
// For any uses which feed into MUST_REUSE_INPUT definitions,
// add copies if the use and def have different allocations.
LNode* ins = insData[iter->pos];
if (LDefinition* def = FindReusingDefinition(ins, alloc)) {
LiveRange* outputRange = vreg(def).rangeFor(outputOf(ins));
LAllocation res = outputRange->bundle()->allocation();
LAllocation sourceAlloc = range->bundle()->allocation();
if (res != *alloc) {
LMoveGroup* group = getInputMoveGroup(ins->toInstruction());
if (!group->addAfter(sourceAlloc, res, reg.type()))
return false;
*alloc = res;
}
}
}
addLiveRegistersForRange(reg, range);
}
}
graph.setLocalSlotCount(stackSlotAllocator.stackHeight());
return true;
}
size_t
BacktrackingAllocator::findFirstNonCallSafepoint(CodePosition from)
{
size_t i = 0;
for (; i < graph.numNonCallSafepoints(); i++) {
const LInstruction* ins = graph.getNonCallSafepoint(i);
if (from <= inputOf(ins))
break;
}
return i;
}
void
BacktrackingAllocator::addLiveRegistersForRange(VirtualRegister& reg, LiveRange* range)
{
// Fill in the live register sets for all non-call safepoints.
LAllocation a = range->bundle()->allocation();
if (!a.isRegister())
return;
// Don't add output registers to the safepoint.
CodePosition start = range->from();
if (range->hasDefinition() && !reg.isTemp()) {
#ifdef CHECK_OSIPOINT_REGISTERS
// We don't add the output register to the safepoint,
// but it still might get added as one of the inputs.
// So eagerly add this reg to the safepoint clobbered registers.
if (reg.ins()->isInstruction()) {
if (LSafepoint* safepoint = reg.ins()->toInstruction()->safepoint())
safepoint->addClobberedRegister(a.toRegister());
}
#endif
start = start.next();
}
size_t i = findFirstNonCallSafepoint(start);
for (; i < graph.numNonCallSafepoints(); i++) {
LInstruction* ins = graph.getNonCallSafepoint(i);
CodePosition pos = inputOf(ins);
// Safepoints are sorted, so we can shortcut out of this loop
// if we go out of range.
if (range->to() <= pos)
break;
MOZ_ASSERT(range->covers(pos));
LSafepoint* safepoint = ins->safepoint();
safepoint->addLiveRegister(a.toRegister());
#ifdef CHECK_OSIPOINT_REGISTERS
if (reg.isTemp())
safepoint->addClobberedRegister(a.toRegister());
#endif
}
}
static inline bool
IsNunbox(VirtualRegister& reg)
{
#ifdef JS_NUNBOX32
return reg.type() == LDefinition::TYPE ||
reg.type() == LDefinition::PAYLOAD;
#else
return false;
#endif
}
static inline bool
IsSlotsOrElements(VirtualRegister& reg)
{
return reg.type() == LDefinition::SLOTS;
}
static inline bool
IsTraceable(VirtualRegister& reg)
{
if (reg.type() == LDefinition::OBJECT)
return true;
#ifdef JS_PUNBOX64
if (reg.type() == LDefinition::BOX)
return true;
#endif
return false;
}
size_t
BacktrackingAllocator::findFirstSafepoint(CodePosition pos, size_t startFrom)
{
size_t i = startFrom;
for (; i < graph.numSafepoints(); i++) {
LInstruction* ins = graph.getSafepoint(i);
if (pos <= inputOf(ins))
break;
}
return i;
}
bool
BacktrackingAllocator::populateSafepoints()
{
JitSpew(JitSpew_RegAlloc, "Populating Safepoints");
size_t firstSafepoint = 0;
MOZ_ASSERT(!vregs[0u].def());
for (uint32_t i = 1; i < graph.numVirtualRegisters(); i++) {
VirtualRegister& reg = vregs[i];
if (!reg.def() || (!IsTraceable(reg) && !IsSlotsOrElements(reg) && !IsNunbox(reg)))
continue;
firstSafepoint = findFirstSafepoint(inputOf(reg.ins()), firstSafepoint);
if (firstSafepoint >= graph.numSafepoints())
break;
for (LiveRange::RegisterLinkIterator iter = reg.rangesBegin(); iter; iter++) {
LiveRange* range = LiveRange::get(*iter);
for (size_t j = firstSafepoint; j < graph.numSafepoints(); j++) {
LInstruction* ins = graph.getSafepoint(j);
if (!range->covers(inputOf(ins))) {
if (inputOf(ins) >= range->to())
break;
continue;
}
// 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();
MOZ_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();
LAllocation a = range->bundle()->allocation();
if (a.isGeneralReg() && ins->isCall())
continue;
switch (reg.type()) {
case LDefinition::OBJECT:
if (!safepoint->addGcPointer(a))
return false;
break;
case LDefinition::SLOTS:
if (!safepoint->addSlotsOrElementsPointer(a))
return false;
break;
#ifdef JS_NUNBOX32
case LDefinition::TYPE:
if (!safepoint->addNunboxType(i, a))
return false;
break;
case LDefinition::PAYLOAD:
if (!safepoint->addNunboxPayload(i, a))
return false;
break;
#else
case LDefinition::BOX:
if (!safepoint->addBoxedValue(a))
return false;
break;
#endif
default:
MOZ_CRASH("Bad register type");
}
}
}
}
return true;
}
bool
BacktrackingAllocator::annotateMoveGroups()
{
// Annotate move groups in the LIR graph with any register that is not
// allocated at that point and can be used as a scratch register. This is
// only required for x86, as other platforms always have scratch registers
// available for use.
#ifdef JS_CODEGEN_X86
LiveRange* range = LiveRange::New(alloc(), 0, CodePosition(), CodePosition().next());
if (!range)
return false;
for (size_t i = 0; i < graph.numBlocks(); i++) {
if (mir->shouldCancel("Backtracking Annotate Move Groups"))
return false;
LBlock* block = graph.getBlock(i);
LInstruction* last = nullptr;
for (LInstructionIterator iter = block->begin(); iter != block->end(); ++iter) {
if (iter->isMoveGroup()) {
CodePosition from = last ? outputOf(last) : entryOf(block);
range->setTo(from.next());
range->setFrom(from);
for (size_t i = 0; i < AnyRegister::Total; i++) {
PhysicalRegister& reg = registers[i];
if (reg.reg.isFloat() || !reg.allocatable)
continue;
// This register is unavailable for use if (a) it is in use
// by some live range immediately before the move group,
// or (b) it is an operand in one of the group's moves. The
// latter case handles live ranges which end immediately
// before the move group or start immediately after.
// For (b) we need to consider move groups immediately
// preceding or following this one.
if (iter->toMoveGroup()->uses(reg.reg.gpr()))
continue;
bool found = false;
LInstructionIterator niter(iter);
for (niter++; niter != block->end(); niter++) {
if (niter->isMoveGroup()) {
if (niter->toMoveGroup()->uses(reg.reg.gpr())) {
found = true;
break;
}
} else {
break;
}
}
if (iter != block->begin()) {
LInstructionIterator riter(iter);
do {
riter--;
if (riter->isMoveGroup()) {
if (riter->toMoveGroup()->uses(reg.reg.gpr())) {
found = true;
break;
}
} else {
break;
}
} while (riter != block->begin());
}
LiveRange* existing;
if (found || reg.allocations.contains(range, &existing))
continue;
iter->toMoveGroup()->setScratchRegister(reg.reg.gpr());
break;
}
} else {
last = *iter;
}
}
}
#endif
return true;
}
/////////////////////////////////////////////////////////////////////
// Debugging methods
/////////////////////////////////////////////////////////////////////
#ifdef DEBUG
const char*
LiveRange::toString() const
{
// Not reentrant!
static char buf[2000];
char* cursor = buf;
char* end = cursor + sizeof(buf);
int n = JS_snprintf(cursor, end - cursor, "v%u [%u,%u)",
hasVreg() ? vreg() : 0, from().bits(), to().bits());
if (n < 0) MOZ_CRASH();
cursor += n;
if (bundle() && !bundle()->allocation().isBogus()) {
n = JS_snprintf(cursor, end - cursor, " %s", bundle()->allocation().toString());
if (n < 0) MOZ_CRASH();
cursor += n;
}
if (hasDefinition()) {
n = JS_snprintf(cursor, end - cursor, " (def)");
if (n < 0) MOZ_CRASH();
cursor += n;
}
for (UsePositionIterator iter = usesBegin(); iter; iter++) {
n = JS_snprintf(cursor, end - cursor, " %s@%u", iter->use->toString(), iter->pos.bits());
if (n < 0) MOZ_CRASH();
cursor += n;
}
return buf;
}
const char*
LiveBundle::toString() const
{
// Not reentrant!
static char buf[2000];
char* cursor = buf;
char* end = cursor + sizeof(buf);
for (LiveRange::BundleLinkIterator iter = rangesBegin(); iter; iter++) {
int n = JS_snprintf(cursor, end - cursor, "%s %s",
(iter == rangesBegin()) ? "" : " ##",
LiveRange::get(*iter)->toString());
if (n < 0) MOZ_CRASH();
cursor += n;
}
return buf;
}
#endif // DEBUG
void
BacktrackingAllocator::dumpVregs()
{
#ifdef DEBUG
MOZ_ASSERT(!vregs[0u].hasRanges());
fprintf(stderr, "Live ranges by virtual register:\n");
for (uint32_t i = 1; i < graph.numVirtualRegisters(); i++) {
fprintf(stderr, " ");
VirtualRegister& reg = vregs[i];
for (LiveRange::RegisterLinkIterator iter = reg.rangesBegin(); iter; iter++) {
if (iter != reg.rangesBegin())
fprintf(stderr, " ## ");
fprintf(stderr, "%s", LiveRange::get(*iter)->toString());
}
fprintf(stderr, "\n");
}
fprintf(stderr, "\nLive ranges by bundle:\n");
for (uint32_t i = 1; i < graph.numVirtualRegisters(); i++) {
VirtualRegister& reg = vregs[i];
for (LiveRange::RegisterLinkIterator baseIter = reg.rangesBegin(); baseIter; baseIter++) {
LiveRange* range = LiveRange::get(*baseIter);
LiveBundle* bundle = range->bundle();
if (range == bundle->firstRange()) {
fprintf(stderr, " ");
for (LiveRange::BundleLinkIterator iter = bundle->rangesBegin(); iter; iter++) {
if (iter != bundle->rangesBegin())
fprintf(stderr, " ## ");
fprintf(stderr, "%s", LiveRange::get(*iter)->toString());
}
fprintf(stderr, "\n");
}
}
}
#endif
}
void
BacktrackingAllocator::dumpFixedRanges()
{
#ifdef DEBUG
fprintf(stderr, "Live ranges by physical register: %s\n", callRanges->toString());
#endif // DEBUG
}
#ifdef DEBUG
struct BacktrackingAllocator::PrintLiveRange
{
bool& first_;
explicit PrintLiveRange(bool& first) : first_(first) {}
void operator()(const LiveRange* range)
{
if (first_)
first_ = false;
else
fprintf(stderr, " /");
fprintf(stderr, " %s", range->toString());
}
};
#endif
void
BacktrackingAllocator::dumpAllocations()
{
#ifdef DEBUG
fprintf(stderr, "Allocations:\n");
dumpVregs();
fprintf(stderr, "Allocations by physical register:\n");
for (size_t i = 0; i < AnyRegister::Total; i++) {
if (registers[i].allocatable && !registers[i].allocations.empty()) {
fprintf(stderr, " %s:", AnyRegister::FromCode(i).name());
bool first = true;
registers[i].allocations.forEach(PrintLiveRange(first));
fprintf(stderr, "\n");
}
}
fprintf(stderr, "\n");
#endif // DEBUG
}
///////////////////////////////////////////////////////////////////////////////
// Heuristic Methods
///////////////////////////////////////////////////////////////////////////////
size_t
BacktrackingAllocator::computePriority(LiveBundle* bundle)
{
// The priority of a bundle is its total length, so that longer lived
// bundles will be processed before shorter ones (even if the longer ones
// have a low spill weight). See processBundle().
size_t lifetimeTotal = 0;
for (LiveRange::BundleLinkIterator iter = bundle->rangesBegin(); iter; iter++) {
LiveRange* range = LiveRange::get(*iter);
lifetimeTotal += range->to() - range->from();
}
return lifetimeTotal;
}
bool
BacktrackingAllocator::minimalDef(LiveRange* range, LNode* ins)
{
// Whether this is a minimal range capturing a definition at ins.
return (range->to() <= minimalDefEnd(ins).next()) &&
((!ins->isPhi() && range->from() == inputOf(ins)) || range->from() == outputOf(ins));
}
bool
BacktrackingAllocator::minimalUse(LiveRange* range, UsePosition* use)
{
// Whether this is a minimal range capturing |use|.
LNode* ins = insData[use->pos];
return (range->from() == inputOf(ins)) &&
(range->to() == (use->use->usedAtStart() ? outputOf(ins) : outputOf(ins).next()));
}
bool
BacktrackingAllocator::minimalBundle(LiveBundle* bundle, bool* pfixed)
{
LiveRange::BundleLinkIterator iter = bundle->rangesBegin();
LiveRange* range = LiveRange::get(*iter);
if (!range->hasVreg()) {
*pfixed = true;
return true;
}
// If a bundle contains multiple ranges, splitAtAllRegisterUses will split
// each range into a separate bundle.
if (++iter)
return false;
if (range->hasDefinition()) {
VirtualRegister& reg = vregs[range->vreg()];
if (pfixed)
*pfixed = reg.def()->policy() == LDefinition::FIXED && reg.def()->output()->isRegister();
return minimalDef(range, reg.ins());
}
bool fixed = false, minimal = false, multiple = false;
for (UsePositionIterator iter = range->usesBegin(); iter; iter++) {
if (iter != range->usesBegin())
multiple = true;
LUse* use = iter->use;
switch (use->policy()) {
case LUse::FIXED:
if (fixed)
return false;
fixed = true;
if (minimalUse(range, *iter))
minimal = true;
break;
case LUse::REGISTER:
if (minimalUse(range, *iter))
minimal = true;
break;
default:
break;
}
}
// If a range contains a fixed use and at least one other use,
// splitAtAllRegisterUses will split each use into a different bundle.
if (multiple && fixed)
minimal = false;
if (pfixed)
*pfixed = fixed;
return minimal;
}
size_t
BacktrackingAllocator::computeSpillWeight(LiveBundle* bundle)
{
// Minimal bundles have an extremely high spill weight, to ensure they
// can evict any other bundles and be allocated to a register.
bool fixed;
if (minimalBundle(bundle, &fixed))
return fixed ? 2000000 : 1000000;
size_t usesTotal = 0;
fixed = false;
for (LiveRange::BundleLinkIterator iter = bundle->rangesBegin(); iter; iter++) {
LiveRange* range = LiveRange::get(*iter);
if (range->hasDefinition()) {
VirtualRegister& reg = vregs[range->vreg()];
if (reg.def()->policy() == LDefinition::FIXED && reg.def()->output()->isRegister()) {
usesTotal += 2000;
fixed = true;
} else if (!reg.ins()->isPhi()) {
usesTotal += 2000;
}
}
for (UsePositionIterator iter = range->usesBegin(); iter; iter++) {
LUse* use = iter->use;
switch (use->policy()) {
case LUse::ANY:
usesTotal += 1000;
break;
case LUse::FIXED:
fixed = true;
case LUse::REGISTER:
usesTotal += 2000;
break;
case LUse::KEEPALIVE:
break;
default:
// Note: RECOVERED_INPUT will not appear in UsePositionIterator.
MOZ_CRASH("Bad use");
}
}
}
// Bundles with fixed uses are given a higher spill weight, since they must
// be allocated to a specific register.
if (testbed && fixed)
usesTotal *= 2;
// Compute spill weight as a use density, lowering the weight for long
// lived bundles with relatively few uses.
size_t lifetimeTotal = computePriority(bundle);
return lifetimeTotal ? usesTotal / lifetimeTotal : 0;
}
size_t
BacktrackingAllocator::maximumSpillWeight(const LiveBundleVector& bundles)
{
size_t maxWeight = 0;
for (size_t i = 0; i < bundles.length(); i++)
maxWeight = Max(maxWeight, computeSpillWeight(bundles[i]));
return maxWeight;
}
bool
BacktrackingAllocator::trySplitAcrossHotcode(LiveBundle* bundle, bool* success)
{
// If this bundle has portions that are hot and portions that are cold,
// split it at the boundaries between hot and cold code.
LiveRange* hotRange = nullptr;
for (LiveRange::BundleLinkIterator iter = bundle->rangesBegin(); iter; iter++) {
LiveRange* range = LiveRange::get(*iter);
if (hotcode.contains(range, &hotRange))
break;
}
// Don't split if there is no hot code in the bundle.
if (!hotRange) {
JitSpew(JitSpew_RegAlloc, " bundle does not contain hot code");
return true;
}
// Don't split if there is no cold code in the bundle.
bool coldCode = false;
for (LiveRange::BundleLinkIterator iter = bundle->rangesBegin(); iter; iter++) {
LiveRange* range = LiveRange::get(*iter);
if (!hotRange->contains(range)) {
coldCode = true;
break;
}
}
if (!coldCode) {
JitSpew(JitSpew_RegAlloc, " bundle does not contain cold code");
return true;
}
JitSpew(JitSpew_RegAlloc, " split across hot range %s", hotRange->toString());
// Tweak the splitting method when compiling asm.js code to look at actual
// uses within the hot/cold code. This heuristic is in place as the below
// mechanism regresses several asm.js tests. Hopefully this will be fixed
// soon and this special case removed. See bug 948838.
if (compilingAsmJS()) {
SplitPositionVector splitPositions;
if (!splitPositions.append(hotRange->from()) || !splitPositions.append(hotRange->to()))
return false;
*success = true;
return splitAt(bundle, splitPositions);
}
LiveBundle* hotBundle = LiveBundle::New(alloc(), bundle->spillSet(), bundle->spillParent());
if (!hotBundle)
return false;
LiveBundle* preBundle = nullptr;
LiveBundle* postBundle = nullptr;
LiveBundle* coldBundle = nullptr;
if (testbed) {
coldBundle = LiveBundle::New(alloc(), bundle->spillSet(), bundle->spillParent());
if (!coldBundle)
return false;
}
// Accumulate the ranges of hot and cold code in the bundle. Note that
// we are only comparing with the single hot range found, so the cold code
// may contain separate hot ranges.
for (LiveRange::BundleLinkIterator iter = bundle->rangesBegin(); iter; iter++) {
LiveRange* range = LiveRange::get(*iter);
LiveRange::Range hot, coldPre, coldPost;
range->intersect(hotRange, &coldPre, &hot, &coldPost);
if (!hot.empty()) {
if (!hotBundle->addRangeAndDistributeUses(alloc(), range, hot.from, hot.to))
return false;
}
if (!coldPre.empty()) {
if (testbed) {
if (!coldBundle->addRangeAndDistributeUses(alloc(), range, coldPre.from, coldPre.to))
return false;
} else {
if (!preBundle) {
preBundle = LiveBundle::New(alloc(), bundle->spillSet(), bundle->spillParent());
if (!preBundle)
return false;
}
if (!preBundle->addRangeAndDistributeUses(alloc(), range, coldPre.from, coldPre.to))
return false;
}
}
if (!coldPost.empty()) {
if (testbed) {
if (!coldBundle->addRangeAndDistributeUses(alloc(), range, coldPost.from, coldPost.to))
return false;
} else {
if (!postBundle) {
postBundle = LiveBundle::New(alloc(), bundle->spillSet(), bundle->spillParent());
if (!postBundle)
return false;
}
if (!postBundle->addRangeAndDistributeUses(alloc(), range, coldPost.from, coldPost.to))
return false;
}
}
}
MOZ_ASSERT(hotBundle->numRanges() != 0);
LiveBundleVector newBundles;
if (!newBundles.append(hotBundle))
return false;
if (testbed) {
MOZ_ASSERT(coldBundle->numRanges() != 0);
if (!newBundles.append(coldBundle))
return false;
} else {
MOZ_ASSERT(preBundle || postBundle);
if (preBundle && !newBundles.append(preBundle))
return false;
if (postBundle && !newBundles.append(postBundle))
return false;
}
*success = true;
return splitAndRequeueBundles(bundle, newBundles);
}
bool
BacktrackingAllocator::trySplitAfterLastRegisterUse(LiveBundle* bundle, LiveBundle* conflict,
bool* success)
{
// If this bundle'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 (LiveRange::BundleLinkIterator iter = bundle->rangesBegin(); iter; iter++) {
LiveRange* range = LiveRange::get(*iter);
// If the range defines a register, consider that a register use for
// our purposes here.
if (isRegisterDefinition(range)) {
CodePosition spillStart = minimalDefEnd(insData[range->from()]).next();
if (!conflict || spillStart < conflict->firstRange()->from()) {
lastUse = lastRegisterFrom = range->from();
lastRegisterTo = spillStart;
}
}
for (UsePositionIterator iter(range->usesBegin()); iter; iter++) {
LUse* use = iter->use;
LNode* ins = insData[iter->pos];
// Uses in the bundle should be sorted.
MOZ_ASSERT(iter->pos >= lastUse);
lastUse = inputOf(ins);
if (!conflict || outputOf(ins) < conflict->firstRange()->from()) {
if (isRegisterUse(use, ins, /* considerCopy = */ true)) {
lastRegisterFrom = inputOf(ins);
lastRegisterTo = iter->pos.next();
}
}
}
}
// Can't trim non-register uses off the end by splitting.
if (!lastRegisterFrom.bits()) {
JitSpew(JitSpew_RegAlloc, " bundle has no register uses");
return true;
}
if (lastUse < lastRegisterTo) {
JitSpew(JitSpew_RegAlloc, " bundle's last use is a register use");
return true;
}
JitSpew(JitSpew_RegAlloc, " split after last register use at %u",
lastRegisterTo.bits());
SplitPositionVector splitPositions;
if (!splitPositions.append(lastRegisterTo))
return false;
*success = true;
return splitAt(bundle, splitPositions);
}
bool
BacktrackingAllocator::trySplitBeforeFirstRegisterUse(LiveBundle* bundle, LiveBundle* conflict, bool* success)
{
// If this bundle's earlier uses do not require it to be in a register,
// split it before the first use which does require a register. If conflict
// is specified, only consider register uses after the conflict ends.
if (isRegisterDefinition(bundle->firstRange())) {
JitSpew(JitSpew_RegAlloc, " bundle is defined by a register");
return true;
}
if (!bundle->firstRange()->hasDefinition()) {
JitSpew(JitSpew_RegAlloc, " bundle does not have definition");
return true;
}
CodePosition firstRegisterFrom;
CodePosition conflictEnd;
if (conflict) {
for (LiveRange::BundleLinkIterator iter = conflict->rangesBegin(); iter; iter++) {
LiveRange* range = LiveRange::get(*iter);
if (range->to() > conflictEnd)
conflictEnd = range->to();
}
}
for (LiveRange::BundleLinkIterator iter = bundle->rangesBegin(); iter; iter++) {
LiveRange* range = LiveRange::get(*iter);
for (UsePositionIterator iter(range->usesBegin()); iter; iter++) {
LUse* use = iter->use;
LNode* ins = insData[iter->pos];
if (!conflict || outputOf(ins) >= conflictEnd) {
if (isRegisterUse(use, ins, /* considerCopy = */ true)) {
firstRegisterFrom = inputOf(ins);
break;
}
}
}
}
if (!firstRegisterFrom.bits()) {
// Can't trim non-register uses off the beginning by splitting.
JitSpew(JitSpew_RegAlloc, " bundle has no register uses");
return true;
}
JitSpew(JitSpew_RegAlloc, " split before first register use at %u",
firstRegisterFrom.bits());
SplitPositionVector splitPositions;
if (!splitPositions.append(firstRegisterFrom))
return false;
*success = true;
return splitAt(bundle, splitPositions);
}
// When splitting a bundle according to a list of split positions, return
// whether a use or range at |pos| should use a different bundle than the last
// position this was called for.
static bool
UseNewBundle(const SplitPositionVector& splitPositions, CodePosition pos,
size_t* activeSplitPosition)
{
if (splitPositions.empty()) {
// When the split positions are empty we are splitting at all uses.
return true;
}
if (*activeSplitPosition == splitPositions.length()) {
// We've advanced past all split positions.
return false;
}
if (splitPositions[*activeSplitPosition] > pos) {
// We haven't gotten to the next split position yet.
return false;
}
// We've advanced past the next split position, find the next one which we
// should split at.
while (*activeSplitPosition < splitPositions.length() &&
splitPositions[*activeSplitPosition] <= pos)
{
(*activeSplitPosition)++;
}
return true;
}
static bool
HasPrecedingRangeSharingVreg(LiveBundle* bundle, LiveRange* range)
{
MOZ_ASSERT(range->bundle() == bundle);
for (LiveRange::BundleLinkIterator iter = bundle->rangesBegin(); iter; iter++) {
LiveRange* prevRange = LiveRange::get(*iter);
if (prevRange == range)
return false;
if (prevRange->vreg() == range->vreg())
return true;
}
MOZ_CRASH();
}
static bool
HasFollowingRangeSharingVreg(LiveBundle* bundle, LiveRange* range)
{
MOZ_ASSERT(range->bundle() == bundle);
bool foundRange = false;
for (LiveRange::BundleLinkIterator iter = bundle->rangesBegin(); iter; iter++) {
LiveRange* prevRange = LiveRange::get(*iter);
if (foundRange && prevRange->vreg() == range->vreg())
return true;
if (prevRange == range)
foundRange = true;
}
MOZ_ASSERT(foundRange);
return false;
}
bool
BacktrackingAllocator::splitAt(LiveBundle* bundle, const SplitPositionVector& splitPositions)
{
// Split the bundle at the given split points. Register uses which have no
// intervening split points are consolidated into the same bundle. If the
// list of split points is empty, then all register uses are placed in
// minimal bundles.
// splitPositions should be sorted.
for (size_t i = 1; i < splitPositions.length(); ++i)
MOZ_ASSERT(splitPositions[i-1] < splitPositions[i]);
// We don't need to create a new spill bundle if there already is one.
bool spillBundleIsNew = false;
LiveBundle* spillBundle = bundle->spillParent();
if (!spillBundle) {
spillBundle = LiveBundle::New(alloc(), bundle->spillSet(), nullptr);
if (!spillBundle)
return false;
spillBundleIsNew = true;
for (LiveRange::BundleLinkIterator iter = bundle->rangesBegin(); iter; iter++) {
LiveRange* range = LiveRange::get(*iter);
CodePosition from = range->from();
if (isRegisterDefinition(range))
from = minimalDefEnd(insData[from]).next();
if (from < range->to()) {
if (!spillBundle->addRange(alloc(), range->vreg(), from, range->to()))
return false;
if (range->hasDefinition() && !isRegisterDefinition(range))
spillBundle->lastRange()->setHasDefinition();
}
}
}
LiveBundleVector newBundles;
// The bundle which ranges are currently being added to.
LiveBundle* activeBundle = LiveBundle::New(alloc(), bundle->spillSet(), spillBundle);
if (!newBundles.append(activeBundle))
return false;
// State for use by UseNewBundle.
size_t activeSplitPosition = 0;
// Make new bundles according to the split positions, and distribute ranges
// and uses to them.
for (LiveRange::BundleLinkIterator iter = bundle->rangesBegin(); iter; iter++) {
LiveRange* range = LiveRange::get(*iter);
if (UseNewBundle(splitPositions, range->from(), &activeSplitPosition)) {
activeBundle = LiveBundle::New(alloc(), bundle->spillSet(), spillBundle);
if (!newBundles.append(activeBundle))
return false;
}
LiveRange* activeRange = LiveRange::New(alloc(), range->vreg(), range->from(), range->to());
if (!activeRange)
return false;
activeBundle->addRange(activeRange);
if (isRegisterDefinition(range))
activeRange->setHasDefinition();
while (range->hasUses()) {
UsePosition* use = range->popUse();
LNode* ins = insData[use->pos];
// Any uses of a register that appear before its definition has
// finished must be associated with the range for that definition.
if (isRegisterDefinition(range) && use->pos <= minimalDefEnd(insData[range->from()])) {
activeRange->addUse(use);
} else if (isRegisterUse(use->use, ins)) {
// Place this register use into a different bundle from the
// last one if there are any split points between the two uses.
// UseNewBundle always returns true if we are splitting at all
// register uses, but we can still reuse the last range and
// bundle if they have uses at the same position, except when
// either use is fixed (the two uses might require incompatible
// registers.)
if (UseNewBundle(splitPositions, use->pos, &activeSplitPosition) &&
(!activeRange->hasUses() ||
activeRange->usesBegin()->pos != use->pos ||
activeRange->usesBegin()->use->policy() == LUse::FIXED ||
use->use->policy() == LUse::FIXED))
{
activeBundle = LiveBundle::New(alloc(), bundle->spillSet(), spillBundle);
if (!newBundles.append(activeBundle))
return false;
activeRange = LiveRange::New(alloc(), range->vreg(), range->from(), range->to());
if (!activeRange)
return false;
activeBundle->addRange(activeRange);
}
activeRange->addUse(use);
} else {
MOZ_ASSERT(spillBundleIsNew);
spillBundle->rangeFor(use->pos)->addUse(use);
}
}
}
LiveBundleVector filteredBundles;
// Trim the ends of ranges in each new bundle when there are no other
// earlier or later ranges in the same bundle with the same vreg.
for (size_t i = 0; i < newBundles.length(); i++) {
LiveBundle* bundle = newBundles[i];
for (LiveRange::BundleLinkIterator iter = bundle->rangesBegin(); iter; ) {
LiveRange* range = LiveRange::get(*iter);
if (!range->hasDefinition()) {
if (!HasPrecedingRangeSharingVreg(bundle, range)) {
if (range->hasUses()) {
UsePosition* use = *range->usesBegin();
range->setFrom(inputOf(insData[use->pos]));
} else {
bundle->removeRangeAndIncrementIterator(iter);
continue;
}
}
}
if (!HasFollowingRangeSharingVreg(bundle, range)) {
if (range->hasUses()) {
UsePosition* use = range->lastUse();
range->setTo(use->pos.next());
} else if (range->hasDefinition()) {
range->setTo(minimalDefEnd(insData[range->from()]).next());
} else {
bundle->removeRangeAndIncrementIterator(iter);
continue;
}
}
iter++;
}
if (bundle->hasRanges() && !filteredBundles.append(bundle))
return false;
}
if (spillBundleIsNew && !filteredBundles.append(spillBundle))
return false;
return splitAndRequeueBundles(bundle, filteredBundles);
}
bool
BacktrackingAllocator::splitAcrossCalls(LiveBundle* bundle)
{
// Split the bundle 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 bundle's range.
SplitPositionVector callPositions;
for (LiveRange::BundleLinkIterator iter = callRanges->rangesBegin(); iter; iter++) {
LiveRange* callRange = LiveRange::get(*iter);
if (bundle->rangeFor(callRange->from()) && bundle->rangeFor(callRange->from().previous())) {
if (!callPositions.append(callRange->from()))
return false;
}
}
MOZ_ASSERT(callPositions.length());
#ifdef JS_JITSPEW
JitSpewStart(JitSpew_RegAlloc, " split across calls at ");
for (size_t i = 0; i < callPositions.length(); ++i)
JitSpewCont(JitSpew_RegAlloc, "%s%u", i != 0 ? ", " : "", callPositions[i].bits());
JitSpewFin(JitSpew_RegAlloc);
#endif
return splitAt(bundle, callPositions);
}
bool
BacktrackingAllocator::chooseBundleSplit(LiveBundle* bundle, bool fixed, LiveBundle* conflict)
{
bool success = false;
if (!trySplitAcrossHotcode(bundle, &success))
return false;
if (success)
return true;
if (fixed)
return splitAcrossCalls(bundle);
if (!trySplitBeforeFirstRegisterUse(bundle, conflict, &success))
return false;
if (success)
return true;
if (!trySplitAfterLastRegisterUse(bundle, conflict, &success))
return false;
if (success)
return true;
// Split at all register uses.
SplitPositionVector emptyPositions;
return splitAt(bundle, emptyPositions);
}