michael@0: /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
michael@0:  * vim: set ts=8 sts=4 et sw=4 tw=99:
michael@0:  * This Source Code Form is subject to the terms of the Mozilla Public
michael@0:  * License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0:  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
michael@0: 
michael@0: #include "jit/LiveRangeAllocator.h"
michael@0: 
michael@0: #include "mozilla/DebugOnly.h"
michael@0: 
michael@0: #include "jsprf.h"
michael@0: 
michael@0: #include "jit/BacktrackingAllocator.h"
michael@0: #include "jit/BitSet.h"
michael@0: #include "jit/LinearScan.h"
michael@0: 
michael@0: using namespace js;
michael@0: using namespace js::jit;
michael@0: 
michael@0: using mozilla::DebugOnly;
michael@0: 
michael@0: int
michael@0: Requirement::priority() const
michael@0: {
michael@0:     switch (kind_) {
michael@0:       case Requirement::FIXED:
michael@0:         return 0;
michael@0: 
michael@0:       case Requirement::REGISTER:
michael@0:         return 1;
michael@0: 
michael@0:       case Requirement::NONE:
michael@0:         return 2;
michael@0: 
michael@0:       default:
michael@0:         MOZ_ASSUME_UNREACHABLE("Unknown requirement kind.");
michael@0:     }
michael@0: }
michael@0: 
michael@0: bool
michael@0: LiveInterval::Range::contains(const Range *other) const
michael@0: {
michael@0:     return from <= other->from && to >= other->to;
michael@0: }
michael@0: 
michael@0: void
michael@0: LiveInterval::Range::intersect(const Range *other, Range *pre, Range *inside, Range *post) const
michael@0: {
michael@0:     JS_ASSERT(pre->empty() && inside->empty() && post->empty());
michael@0: 
michael@0:     CodePosition innerFrom = from;
michael@0:     if (from < other->from) {
michael@0:         if (to < other->from) {
michael@0:             *pre = Range(from, to);
michael@0:             return;
michael@0:         }
michael@0:         *pre = Range(from, other->from);
michael@0:         innerFrom = other->from;
michael@0:     }
michael@0: 
michael@0:     CodePosition innerTo = to;
michael@0:     if (to > other->to) {
michael@0:         if (from >= other->to) {
michael@0:             *post = Range(from, to);
michael@0:             return;
michael@0:         }
michael@0:         *post = Range(other->to, to);
michael@0:         innerTo = other->to;
michael@0:     }
michael@0: 
michael@0:     if (innerFrom != innerTo)
michael@0:         *inside = Range(innerFrom, innerTo);
michael@0: }
michael@0: 
michael@0: bool
michael@0: LiveInterval::addRangeAtHead(CodePosition from, CodePosition to)
michael@0: {
michael@0:     JS_ASSERT(from < to);
michael@0: 
michael@0:     Range newRange(from, to);
michael@0: 
michael@0:     if (ranges_.empty())
michael@0:         return ranges_.append(newRange);
michael@0: 
michael@0:     Range &first = ranges_.back();
michael@0:     if (to < first.from)
michael@0:         return ranges_.append(newRange);
michael@0: 
michael@0:     if (to == first.from) {
michael@0:         first.from = from;
michael@0:         return true;
michael@0:     }
michael@0: 
michael@0:     JS_ASSERT(from < first.to);
michael@0:     JS_ASSERT(to > first.from);
michael@0:     if (from < first.from)
michael@0:         first.from = from;
michael@0:     if (to > first.to)
michael@0:         first.to = to;
michael@0: 
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: bool
michael@0: LiveInterval::addRange(CodePosition from, CodePosition to)
michael@0: {
michael@0:     JS_ASSERT(from < to);
michael@0: 
michael@0:     Range newRange(from, to);
michael@0: 
michael@0:     Range *i;
michael@0:     // Find the location to insert the new range
michael@0:     for (i = ranges_.end() - 1; i >= ranges_.begin(); i--) {
michael@0:         if (newRange.from <= i->to) {
michael@0:             if (i->from < newRange.from)
michael@0:                 newRange.from = i->from;
michael@0:             break;
michael@0:         }
michael@0:     }
michael@0:     // Perform coalescing on overlapping ranges
michael@0:     for (; i >= ranges_.begin(); i--) {
michael@0:         if (newRange.to < i->from)
michael@0:             break;
michael@0:         if (newRange.to < i->to)
michael@0:             newRange.to = i->to;
michael@0:         ranges_.erase(i);
michael@0:     }
michael@0: 
michael@0:     return ranges_.insert(i + 1, newRange);
michael@0: }
michael@0: 
michael@0: void
michael@0: LiveInterval::setFrom(CodePosition from)
michael@0: {
michael@0:     while (!ranges_.empty()) {
michael@0:         if (ranges_.back().to < from) {
michael@0:             ranges_.erase(&ranges_.back());
michael@0:         } else {
michael@0:             if (from == ranges_.back().to)
michael@0:                 ranges_.erase(&ranges_.back());
michael@0:             else
michael@0:                 ranges_.back().from = from;
michael@0:             break;
michael@0:         }
michael@0:     }
michael@0: }
michael@0: 
michael@0: bool
michael@0: LiveInterval::covers(CodePosition pos)
michael@0: {
michael@0:     if (pos < start() || pos >= end())
michael@0:         return false;
michael@0: 
michael@0:     // Loop over the ranges in ascending order.
michael@0:     size_t i = lastProcessedRangeIfValid(pos);
michael@0:     for (; i < ranges_.length(); i--) {
michael@0:         if (pos < ranges_[i].from)
michael@0:             return false;
michael@0:         setLastProcessedRange(i, pos);
michael@0:         if (pos < ranges_[i].to)
michael@0:             return true;
michael@0:     }
michael@0:     return false;
michael@0: }
michael@0: 
michael@0: CodePosition
michael@0: LiveInterval::nextCoveredAfter(CodePosition pos)
michael@0: {
michael@0:     for (size_t i = 0; i < ranges_.length(); i++) {
michael@0:         if (ranges_[i].to <= pos) {
michael@0:             if (i)
michael@0:                 return ranges_[i-1].from;
michael@0:             break;
michael@0:         }
michael@0:         if (ranges_[i].from <= pos)
michael@0:             return pos;
michael@0:     }
michael@0:     return CodePosition::MIN;
michael@0: }
michael@0: 
michael@0: CodePosition
michael@0: LiveInterval::intersect(LiveInterval *other)
michael@0: {
michael@0:     if (start() > other->start())
michael@0:         return other->intersect(this);
michael@0: 
michael@0:     // Loop over the ranges in ascending order. As an optimization,
michael@0:     // try to start at the last processed range.
michael@0:     size_t i = lastProcessedRangeIfValid(other->start());
michael@0:     size_t j = other->ranges_.length() - 1;
michael@0:     if (i >= ranges_.length() || j >= other->ranges_.length())
michael@0:         return CodePosition::MIN;
michael@0: 
michael@0:     while (true) {
michael@0:         const Range &r1 = ranges_[i];
michael@0:         const Range &r2 = other->ranges_[j];
michael@0: 
michael@0:         if (r1.from <= r2.from) {
michael@0:             if (r1.from <= other->start())
michael@0:                 setLastProcessedRange(i, other->start());
michael@0:             if (r2.from < r1.to)
michael@0:                 return r2.from;
michael@0:             if (i == 0 || ranges_[i-1].from > other->end())
michael@0:                 break;
michael@0:             i--;
michael@0:         } else {
michael@0:             if (r1.from < r2.to)
michael@0:                 return r1.from;
michael@0:             if (j == 0 || other->ranges_[j-1].from > end())
michael@0:                 break;
michael@0:             j--;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     return CodePosition::MIN;
michael@0: }
michael@0: 
michael@0: /*
michael@0:  * This function takes the callee interval and moves all ranges following or
michael@0:  * including provided position to the target interval. Additionally, if a
michael@0:  * range in the callee interval spans the given position, it is split and the
michael@0:  * latter half is placed in the target interval.
michael@0:  *
michael@0:  * This function should only be called if it is known that the interval should
michael@0:  * actually be split (and, presumably, a move inserted). As such, it is an
michael@0:  * error for the caller to request a split that moves all intervals into the
michael@0:  * target. Doing so will trip the assertion at the bottom of the function.
michael@0:  */
michael@0: bool
michael@0: LiveInterval::splitFrom(CodePosition pos, LiveInterval *after)
michael@0: {
michael@0:     JS_ASSERT(pos >= start() && pos < end());
michael@0:     JS_ASSERT(after->ranges_.empty());
michael@0: 
michael@0:     // Move all intervals over to the target
michael@0:     size_t bufferLength = ranges_.length();
michael@0:     Range *buffer = ranges_.extractRawBuffer();
michael@0:     if (!buffer)
michael@0:         return false;
michael@0:     after->ranges_.replaceRawBuffer(buffer, bufferLength);
michael@0: 
michael@0:     // Move intervals back as required
michael@0:     for (Range *i = &after->ranges_.back(); i >= after->ranges_.begin(); i--) {
michael@0:         if (pos >= i->to)
michael@0:             continue;
michael@0: 
michael@0:         if (pos > i->from) {
michael@0:             // Split the range
michael@0:             Range split(i->from, pos);
michael@0:             i->from = pos;
michael@0:             if (!ranges_.append(split))
michael@0:                 return false;
michael@0:         }
michael@0:         if (!ranges_.append(i + 1, after->ranges_.end()))
michael@0:             return false;
michael@0:         after->ranges_.shrinkBy(after->ranges_.end() - i - 1);
michael@0:         break;
michael@0:     }
michael@0: 
michael@0:     // Split the linked list of use positions
michael@0:     UsePosition *prev = nullptr;
michael@0:     for (UsePositionIterator usePos(usesBegin()); usePos != usesEnd(); usePos++) {
michael@0:         if (usePos->pos > pos)
michael@0:             break;
michael@0:         prev = *usePos;
michael@0:     }
michael@0: 
michael@0:     uses_.splitAfter(prev, &after->uses_);
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: void
michael@0: LiveInterval::addUse(UsePosition *use)
michael@0: {
michael@0:     // Insert use positions in ascending order. Note that instructions
michael@0:     // are visited in reverse order, so in most cases the loop terminates
michael@0:     // at the first iteration and the use position will be added to the
michael@0:     // front of the list.
michael@0:     UsePosition *prev = nullptr;
michael@0:     for (UsePositionIterator current(usesBegin()); current != usesEnd(); current++) {
michael@0:         if (current->pos >= use->pos)
michael@0:             break;
michael@0:         prev = *current;
michael@0:     }
michael@0: 
michael@0:     if (prev)
michael@0:         uses_.insertAfter(prev, use);
michael@0:     else
michael@0:         uses_.pushFront(use);
michael@0: }
michael@0: 
michael@0: void
michael@0: LiveInterval::addUseAtEnd(UsePosition *use)
michael@0: {
michael@0:     JS_ASSERT(uses_.empty() || use->pos >= uses_.back()->pos);
michael@0:     uses_.pushBack(use);
michael@0: }
michael@0: 
michael@0: UsePosition *
michael@0: LiveInterval::nextUseAfter(CodePosition after)
michael@0: {
michael@0:     for (UsePositionIterator usePos(usesBegin()); usePos != usesEnd(); usePos++) {
michael@0:         if (usePos->pos >= after) {
michael@0:             LUse::Policy policy = usePos->use->policy();
michael@0:             JS_ASSERT(policy != LUse::RECOVERED_INPUT);
michael@0:             if (policy != LUse::KEEPALIVE)
michael@0:                 return *usePos;
michael@0:         }
michael@0:     }
michael@0:     return nullptr;
michael@0: }
michael@0: 
michael@0: /*
michael@0:  * This function locates the first "real" use of this interval that follows
michael@0:  * the given code position. Non-"real" uses are currently just snapshots,
michael@0:  * which keep virtual registers alive but do not result in the
michael@0:  * generation of code that use them.
michael@0:  */
michael@0: CodePosition
michael@0: LiveInterval::nextUsePosAfter(CodePosition after)
michael@0: {
michael@0:     UsePosition *min = nextUseAfter(after);
michael@0:     return min ? min->pos : CodePosition::MAX;
michael@0: }
michael@0: 
michael@0: /*
michael@0:  * This function finds the position of the first use of this interval
michael@0:  * that is incompatible with the provideded allocation. For example,
michael@0:  * a use with a REGISTER policy would be incompatible with a stack slot
michael@0:  * allocation.
michael@0:  */
michael@0: CodePosition
michael@0: LiveInterval::firstIncompatibleUse(LAllocation alloc)
michael@0: {
michael@0:     for (UsePositionIterator usePos(usesBegin()); usePos != usesEnd(); usePos++) {
michael@0:         if (!UseCompatibleWith(usePos->use, alloc))
michael@0:             return usePos->pos;
michael@0:     }
michael@0:     return CodePosition::MAX;
michael@0: }
michael@0: 
michael@0: LiveInterval *
michael@0: VirtualRegister::intervalFor(CodePosition pos)
michael@0: {
michael@0:     for (LiveInterval **i = intervals_.begin(); i != intervals_.end(); i++) {
michael@0:         if ((*i)->covers(pos))
michael@0:             return *i;
michael@0:         if (pos < (*i)->end())
michael@0:             break;
michael@0:     }
michael@0:     return nullptr;
michael@0: }
michael@0: 
michael@0: LiveInterval *
michael@0: VirtualRegister::getFirstInterval()
michael@0: {
michael@0:     JS_ASSERT(!intervals_.empty());
michael@0:     return intervals_[0];
michael@0: }
michael@0: 
michael@0: // Instantiate LiveRangeAllocator for each template instance.
michael@0: template bool LiveRangeAllocator<LinearScanVirtualRegister, true>::buildLivenessInfo();
michael@0: template bool LiveRangeAllocator<BacktrackingVirtualRegister, false>::buildLivenessInfo();
michael@0: 
michael@0: #ifdef DEBUG
michael@0: static inline bool
michael@0: NextInstructionHasFixedUses(LBlock *block, LInstruction *ins)
michael@0: {
michael@0:     LInstructionIterator iter(block->begin(ins));
michael@0:     iter++;
michael@0:     for (LInstruction::InputIterator alloc(**iter); alloc.more(); alloc.next()) {
michael@0:         if (alloc->isUse() && alloc->toUse()->isFixedRegister())
michael@0:             return true;
michael@0:     }
michael@0:     return false;
michael@0: }
michael@0: 
michael@0: // Returns true iff ins has a def/temp reusing the input allocation.
michael@0: static bool
michael@0: IsInputReused(LInstruction *ins, LUse *use)
michael@0: {
michael@0:     for (size_t i = 0; i < ins->numDefs(); i++) {
michael@0:         if (ins->getDef(i)->policy() == LDefinition::MUST_REUSE_INPUT &&
michael@0:             ins->getOperand(ins->getDef(i)->getReusedInput())->toUse() == use)
michael@0:         {
michael@0:             return true;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     for (size_t i = 0; i < ins->numTemps(); i++) {
michael@0:         if (ins->getTemp(i)->policy() == LDefinition::MUST_REUSE_INPUT &&
michael@0:             ins->getOperand(ins->getTemp(i)->getReusedInput())->toUse() == use)
michael@0:         {
michael@0:             return true;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     return false;
michael@0: }
michael@0: #endif
michael@0: 
michael@0: /*
michael@0:  * This function pre-allocates and initializes as much global state as possible
michael@0:  * to avoid littering the algorithms with memory management cruft.
michael@0:  */
michael@0: template <typename VREG, bool forLSRA>
michael@0: bool
michael@0: LiveRangeAllocator<VREG, forLSRA>::init()
michael@0: {
michael@0:     if (!RegisterAllocator::init())
michael@0:         return false;
michael@0: 
michael@0:     liveIn = mir->allocate<BitSet*>(graph.numBlockIds());
michael@0:     if (!liveIn)
michael@0:         return false;
michael@0: 
michael@0:     // Initialize fixed intervals.
michael@0:     for (size_t i = 0; i < AnyRegister::Total; i++) {
michael@0:         AnyRegister reg = AnyRegister::FromCode(i);
michael@0:         LiveInterval *interval = LiveInterval::New(alloc(), 0);
michael@0:         interval->setAllocation(LAllocation(reg));
michael@0:         fixedIntervals[i] = interval;
michael@0:     }
michael@0: 
michael@0:     fixedIntervalsUnion = LiveInterval::New(alloc(), 0);
michael@0: 
michael@0:     if (!vregs.init(mir, graph.numVirtualRegisters()))
michael@0:         return false;
michael@0: 
michael@0:     // Build virtual register objects
michael@0:     for (size_t i = 0; i < graph.numBlocks(); i++) {
michael@0:         if (mir->shouldCancel("Create data structures (main loop)"))
michael@0:             return false;
michael@0: 
michael@0:         LBlock *block = graph.getBlock(i);
michael@0:         for (LInstructionIterator ins = block->begin(); ins != block->end(); ins++) {
michael@0:             for (size_t j = 0; j < ins->numDefs(); j++) {
michael@0:                 LDefinition *def = ins->getDef(j);
michael@0:                 if (def->policy() != LDefinition::PASSTHROUGH) {
michael@0:                     if (!vregs[def].init(alloc(), block, *ins, def, /* isTemp */ false))
michael@0:                         return false;
michael@0:                 }
michael@0:             }
michael@0: 
michael@0:             for (size_t j = 0; j < ins->numTemps(); j++) {
michael@0:                 LDefinition *def = ins->getTemp(j);
michael@0:                 if (def->isBogusTemp())
michael@0:                     continue;
michael@0:                 if (!vregs[def].init(alloc(), block, *ins, def, /* isTemp */ true))
michael@0:                     return false;
michael@0:             }
michael@0:         }
michael@0:         for (size_t j = 0; j < block->numPhis(); j++) {
michael@0:             LPhi *phi = block->getPhi(j);
michael@0:             LDefinition *def = phi->getDef(0);
michael@0:             if (!vregs[def].init(alloc(), block, phi, def, /* isTemp */ false))
michael@0:                 return false;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: static void
michael@0: AddRegisterToSafepoint(LSafepoint *safepoint, AnyRegister reg, const LDefinition &def)
michael@0: {
michael@0:     safepoint->addLiveRegister(reg);
michael@0: 
michael@0:     JS_ASSERT(def.type() == LDefinition::GENERAL ||
michael@0:               def.type() == LDefinition::INT32 ||
michael@0:               def.type() == LDefinition::DOUBLE ||
michael@0:               def.type() == LDefinition::FLOAT32 ||
michael@0:               def.type() == LDefinition::OBJECT);
michael@0: 
michael@0:     if (def.type() == LDefinition::OBJECT)
michael@0:         safepoint->addGcRegister(reg.gpr());
michael@0: }
michael@0: 
michael@0: /*
michael@0:  * This function builds up liveness intervals for all virtual registers
michael@0:  * defined in the function. Additionally, it populates the liveIn array with
michael@0:  * information about which registers are live at the beginning of a block, to
michael@0:  * aid resolution and reification in a later phase.
michael@0:  *
michael@0:  * The algorithm is based on the one published in:
michael@0:  *
michael@0:  * Wimmer, Christian, and Michael Franz. "Linear Scan Register Allocation on
michael@0:  *     SSA Form." Proceedings of the International Symposium on Code Generation
michael@0:  *     and Optimization. Toronto, Ontario, Canada, ACM. 2010. 170-79. PDF.
michael@0:  *
michael@0:  * The algorithm operates on blocks ordered such that dominators of a block
michael@0:  * are before the block itself, and such that all blocks of a loop are
michael@0:  * contiguous. It proceeds backwards over the instructions in this order,
michael@0:  * marking registers live at their uses, ending their live intervals at
michael@0:  * definitions, and recording which registers are live at the top of every
michael@0:  * block. To deal with loop backedges, variables live at the beginning of
michael@0:  * a loop gain an interval covering the entire loop.
michael@0:  */
michael@0: template <typename VREG, bool forLSRA>
michael@0: bool
michael@0: LiveRangeAllocator<VREG, forLSRA>::buildLivenessInfo()
michael@0: {
michael@0:     if (!init())
michael@0:         return false;
michael@0: 
michael@0:     Vector<MBasicBlock *, 1, SystemAllocPolicy> loopWorkList;
michael@0:     BitSet *loopDone = BitSet::New(alloc(), graph.numBlockIds());
michael@0:     if (!loopDone)
michael@0:         return false;
michael@0: 
michael@0:     for (size_t i = graph.numBlocks(); i > 0; i--) {
michael@0:         if (mir->shouldCancel("Build Liveness Info (main loop)"))
michael@0:             return false;
michael@0: 
michael@0:         LBlock *block = graph.getBlock(i - 1);
michael@0:         MBasicBlock *mblock = block->mir();
michael@0: 
michael@0:         BitSet *live = BitSet::New(alloc(), graph.numVirtualRegisters());
michael@0:         if (!live)
michael@0:             return false;
michael@0:         liveIn[mblock->id()] = live;
michael@0: 
michael@0:         // Propagate liveIn from our successors to us
michael@0:         for (size_t i = 0; i < mblock->lastIns()->numSuccessors(); i++) {
michael@0:             MBasicBlock *successor = mblock->lastIns()->getSuccessor(i);
michael@0:             // Skip backedges, as we fix them up at the loop header.
michael@0:             if (mblock->id() < successor->id())
michael@0:                 live->insertAll(liveIn[successor->id()]);
michael@0:         }
michael@0: 
michael@0:         // Add successor phis
michael@0:         if (mblock->successorWithPhis()) {
michael@0:             LBlock *phiSuccessor = mblock->successorWithPhis()->lir();
michael@0:             for (unsigned int j = 0; j < phiSuccessor->numPhis(); j++) {
michael@0:                 LPhi *phi = phiSuccessor->getPhi(j);
michael@0:                 LAllocation *use = phi->getOperand(mblock->positionInPhiSuccessor());
michael@0:                 uint32_t reg = use->toUse()->virtualRegister();
michael@0:                 live->insert(reg);
michael@0:             }
michael@0:         }
michael@0: 
michael@0:         // Variables are assumed alive for the entire block, a define shortens
michael@0:         // the interval to the point of definition.
michael@0:         for (BitSet::Iterator liveRegId(*live); liveRegId; liveRegId++) {
michael@0:             if (!vregs[*liveRegId].getInterval(0)->addRangeAtHead(inputOf(block->firstId()),
michael@0:                                                                   outputOf(block->lastId()).next()))
michael@0:             {
michael@0:                 return false;
michael@0:             }
michael@0:         }
michael@0: 
michael@0:         // Shorten the front end of live intervals for live variables to their
michael@0:         // point of definition, if found.
michael@0:         for (LInstructionReverseIterator ins = block->rbegin(); ins != block->rend(); ins++) {
michael@0:             // Calls may clobber registers, so force a spill and reload around the callsite.
michael@0:             if (ins->isCall()) {
michael@0:                 for (AnyRegisterIterator iter(allRegisters_); iter.more(); iter++) {
michael@0:                     if (forLSRA) {
michael@0:                         if (!addFixedRangeAtHead(*iter, inputOf(*ins), outputOf(*ins)))
michael@0:                             return false;
michael@0:                     } else {
michael@0:                         bool found = false;
michael@0:                         for (size_t i = 0; i < ins->numDefs(); i++) {
michael@0:                             if (ins->getDef(i)->isPreset() &&
michael@0:                                 *ins->getDef(i)->output() == LAllocation(*iter)) {
michael@0:                                 found = true;
michael@0:                                 break;
michael@0:                             }
michael@0:                         }
michael@0:                         if (!found && !addFixedRangeAtHead(*iter, outputOf(*ins), outputOf(*ins).next()))
michael@0:                             return false;
michael@0:                     }
michael@0:                 }
michael@0:             }
michael@0: 
michael@0:             for (size_t i = 0; i < ins->numDefs(); i++) {
michael@0:                 if (ins->getDef(i)->policy() != LDefinition::PASSTHROUGH) {
michael@0:                     LDefinition *def = ins->getDef(i);
michael@0: 
michael@0:                     CodePosition from;
michael@0:                     if (def->policy() == LDefinition::PRESET && def->output()->isRegister() && forLSRA) {
michael@0:                         // The fixed range covers the current instruction so the
michael@0:                         // interval for the virtual register starts at the next
michael@0:                         // instruction. If the next instruction has a fixed use,
michael@0:                         // this can lead to unnecessary register moves. To avoid
michael@0:                         // special handling for this, assert the next instruction
michael@0:                         // has no fixed uses. defineFixed guarantees this by inserting
michael@0:                         // an LNop.
michael@0:                         JS_ASSERT(!NextInstructionHasFixedUses(block, *ins));
michael@0:                         AnyRegister reg = def->output()->toRegister();
michael@0:                         if (!addFixedRangeAtHead(reg, inputOf(*ins), outputOf(*ins).next()))
michael@0:                             return false;
michael@0:                         from = outputOf(*ins).next();
michael@0:                     } else {
michael@0:                         from = forLSRA ? inputOf(*ins) : outputOf(*ins);
michael@0:                     }
michael@0: 
michael@0:                     if (def->policy() == LDefinition::MUST_REUSE_INPUT) {
michael@0:                         // MUST_REUSE_INPUT is implemented by allocating an output
michael@0:                         // register and moving the input to it. Register hints are
michael@0:                         // used to avoid unnecessary moves. We give the input an
michael@0:                         // LUse::ANY policy to avoid allocating a register for the
michael@0:                         // input.
michael@0:                         LUse *inputUse = ins->getOperand(def->getReusedInput())->toUse();
michael@0:                         JS_ASSERT(inputUse->policy() == LUse::REGISTER);
michael@0:                         JS_ASSERT(inputUse->usedAtStart());
michael@0:                         *inputUse = LUse(inputUse->virtualRegister(), LUse::ANY, /* usedAtStart = */ true);
michael@0:                     }
michael@0: 
michael@0:                     LiveInterval *interval = vregs[def].getInterval(0);
michael@0:                     interval->setFrom(from);
michael@0: 
michael@0:                     // Ensure that if there aren't any uses, there's at least
michael@0:                     // some interval for the output to go into.
michael@0:                     if (interval->numRanges() == 0) {
michael@0:                         if (!interval->addRangeAtHead(from, from.next()))
michael@0:                             return false;
michael@0:                     }
michael@0:                     live->remove(def->virtualRegister());
michael@0:                 }
michael@0:             }
michael@0: 
michael@0:             for (size_t i = 0; i < ins->numTemps(); i++) {
michael@0:                 LDefinition *temp = ins->getTemp(i);
michael@0:                 if (temp->isBogusTemp())
michael@0:                     continue;
michael@0: 
michael@0:                 if (forLSRA) {
michael@0:                     if (temp->policy() == LDefinition::PRESET) {
michael@0:                         if (ins->isCall())
michael@0:                             continue;
michael@0:                         AnyRegister reg = temp->output()->toRegister();
michael@0:                         if (!addFixedRangeAtHead(reg, inputOf(*ins), outputOf(*ins)))
michael@0:                             return false;
michael@0: 
michael@0:                         // Fixed intervals are not added to safepoints, so do it
michael@0:                         // here.
michael@0:                         if (LSafepoint *safepoint = ins->safepoint())
michael@0:                             AddRegisterToSafepoint(safepoint, reg, *temp);
michael@0:                     } else {
michael@0:                         JS_ASSERT(!ins->isCall());
michael@0:                         if (!vregs[temp].getInterval(0)->addRangeAtHead(inputOf(*ins), outputOf(*ins)))
michael@0:                             return false;
michael@0:                     }
michael@0:                 } else {
michael@0:                     // Normally temps are considered to cover both the input
michael@0:                     // and output of the associated instruction. In some cases
michael@0:                     // though we want to use a fixed register as both an input
michael@0:                     // and clobbered register in the instruction, so watch for
michael@0:                     // this and shorten the temp to cover only the output.
michael@0:                     CodePosition from = inputOf(*ins);
michael@0:                     if (temp->policy() == LDefinition::PRESET) {
michael@0:                         AnyRegister reg = temp->output()->toRegister();
michael@0:                         for (LInstruction::InputIterator alloc(**ins); alloc.more(); alloc.next()) {
michael@0:                             if (alloc->isUse()) {
michael@0:                                 LUse *use = alloc->toUse();
michael@0:                                 if (use->isFixedRegister()) {
michael@0:                                     if (GetFixedRegister(vregs[use].def(), use) == reg)
michael@0:                                         from = outputOf(*ins);
michael@0:                                 }
michael@0:                             }
michael@0:                         }
michael@0:                     }
michael@0: 
michael@0:                     CodePosition to =
michael@0:                         ins->isCall() ? outputOf(*ins) : outputOf(*ins).next();
michael@0:                     if (!vregs[temp].getInterval(0)->addRangeAtHead(from, to))
michael@0:                         return false;
michael@0:                 }
michael@0:             }
michael@0: 
michael@0:             DebugOnly<bool> hasUseRegister = false;
michael@0:             DebugOnly<bool> hasUseRegisterAtStart = false;
michael@0: 
michael@0:             for (LInstruction::InputIterator inputAlloc(**ins); inputAlloc.more(); inputAlloc.next()) {
michael@0:                 if (inputAlloc->isUse()) {
michael@0:                     LUse *use = inputAlloc->toUse();
michael@0: 
michael@0:                     // The first instruction, LLabel, has no uses.
michael@0:                     JS_ASSERT_IF(forLSRA, inputOf(*ins) > outputOf(block->firstId()));
michael@0: 
michael@0:                     // Call uses should always be at-start or fixed, since the fixed intervals
michael@0:                     // use all registers.
michael@0:                     JS_ASSERT_IF(ins->isCall() && !inputAlloc.isSnapshotInput(),
michael@0:                                  use->isFixedRegister() || use->usedAtStart());
michael@0: 
michael@0: #ifdef DEBUG
michael@0:                     // Don't allow at-start call uses if there are temps of the same kind,
michael@0:                     // so that we don't assign the same register.
michael@0:                     if (ins->isCall() && use->usedAtStart()) {
michael@0:                         for (size_t i = 0; i < ins->numTemps(); i++)
michael@0:                             JS_ASSERT(vregs[ins->getTemp(i)].isFloatReg() != vregs[use].isFloatReg());
michael@0:                     }
michael@0: 
michael@0:                     // If there are both useRegisterAtStart(x) and useRegister(y)
michael@0:                     // uses, we may assign the same register to both operands due to
michael@0:                     // interval splitting (bug 772830). Don't allow this for now.
michael@0:                     if (use->policy() == LUse::REGISTER) {
michael@0:                         if (use->usedAtStart()) {
michael@0:                             if (!IsInputReused(*ins, use))
michael@0:                                 hasUseRegisterAtStart = true;
michael@0:                         } else {
michael@0:                             hasUseRegister = true;
michael@0:                         }
michael@0:                     }
michael@0: 
michael@0:                     JS_ASSERT(!(hasUseRegister && hasUseRegisterAtStart));
michael@0: #endif
michael@0: 
michael@0:                     // Don't treat RECOVERED_INPUT uses as keeping the vreg alive.
michael@0:                     if (use->policy() == LUse::RECOVERED_INPUT)
michael@0:                         continue;
michael@0: 
michael@0:                     CodePosition to;
michael@0:                     if (forLSRA) {
michael@0:                         if (use->isFixedRegister()) {
michael@0:                             AnyRegister reg = GetFixedRegister(vregs[use].def(), use);
michael@0:                             if (!addFixedRangeAtHead(reg, inputOf(*ins), outputOf(*ins)))
michael@0:                                 return false;
michael@0:                             to = inputOf(*ins);
michael@0: 
michael@0:                             // Fixed intervals are not added to safepoints, so do it
michael@0:                             // here.
michael@0:                             LSafepoint *safepoint = ins->safepoint();
michael@0:                             if (!ins->isCall() && safepoint)
michael@0:                                 AddRegisterToSafepoint(safepoint, reg, *vregs[use].def());
michael@0:                         } else {
michael@0:                             to = use->usedAtStart() ? inputOf(*ins) : outputOf(*ins);
michael@0:                         }
michael@0:                     } else {
michael@0:                         to = (use->usedAtStart() || ins->isCall())
michael@0:                            ? inputOf(*ins) : outputOf(*ins);
michael@0:                         if (use->isFixedRegister()) {
michael@0:                             LAllocation reg(AnyRegister::FromCode(use->registerCode()));
michael@0:                             for (size_t i = 0; i < ins->numDefs(); i++) {
michael@0:                                 LDefinition *def = ins->getDef(i);
michael@0:                                 if (def->policy() == LDefinition::PRESET && *def->output() == reg)
michael@0:                                     to = inputOf(*ins);
michael@0:                             }
michael@0:                         }
michael@0:                     }
michael@0: 
michael@0:                     LiveInterval *interval = vregs[use].getInterval(0);
michael@0:                     if (!interval->addRangeAtHead(inputOf(block->firstId()), forLSRA ? to : to.next()))
michael@0:                         return false;
michael@0:                     interval->addUse(new(alloc()) UsePosition(use, to));
michael@0: 
michael@0:                     live->insert(use->virtualRegister());
michael@0:                 }
michael@0:             }
michael@0:         }
michael@0: 
michael@0:         // Phis have simultaneous assignment semantics at block begin, so at
michael@0:         // the beginning of the block we can be sure that liveIn does not
michael@0:         // contain any phi outputs.
michael@0:         for (unsigned int i = 0; i < block->numPhis(); i++) {
michael@0:             LDefinition *def = block->getPhi(i)->getDef(0);
michael@0:             if (live->contains(def->virtualRegister())) {
michael@0:                 live->remove(def->virtualRegister());
michael@0:             } else {
michael@0:                 // This is a dead phi, so add a dummy range over all phis. This
michael@0:                 // can go away if we have an earlier dead code elimination pass.
michael@0:                 if (!vregs[def].getInterval(0)->addRangeAtHead(inputOf(block->firstId()),
michael@0:                                                                outputOf(block->firstId())))
michael@0:                 {
michael@0:                     return false;
michael@0:                 }
michael@0:             }
michael@0:         }
michael@0: 
michael@0:         if (mblock->isLoopHeader()) {
michael@0:             // A divergence from the published algorithm is required here, as
michael@0:             // our block order does not guarantee that blocks of a loop are
michael@0:             // contiguous. As a result, a single live interval spanning the
michael@0:             // loop is not possible. Additionally, we require liveIn in a later
michael@0:             // pass for resolution, so that must also be fixed up here.
michael@0:             MBasicBlock *loopBlock = mblock->backedge();
michael@0:             while (true) {
michael@0:                 // Blocks must already have been visited to have a liveIn set.
michael@0:                 JS_ASSERT(loopBlock->id() >= mblock->id());
michael@0: 
michael@0:                 // Add an interval for this entire loop block
michael@0:                 CodePosition from = inputOf(loopBlock->lir()->firstId());
michael@0:                 CodePosition to = outputOf(loopBlock->lir()->lastId()).next();
michael@0: 
michael@0:                 for (BitSet::Iterator liveRegId(*live); liveRegId; liveRegId++) {
michael@0:                     if (!vregs[*liveRegId].getInterval(0)->addRange(from, to))
michael@0:                         return false;
michael@0:                 }
michael@0: 
michael@0:                 // Fix up the liveIn set to account for the new interval
michael@0:                 liveIn[loopBlock->id()]->insertAll(live);
michael@0: 
michael@0:                 // Make sure we don't visit this node again
michael@0:                 loopDone->insert(loopBlock->id());
michael@0: 
michael@0:                 // If this is the loop header, any predecessors are either the
michael@0:                 // backedge or out of the loop, so skip any predecessors of
michael@0:                 // this block
michael@0:                 if (loopBlock != mblock) {
michael@0:                     for (size_t i = 0; i < loopBlock->numPredecessors(); i++) {
michael@0:                         MBasicBlock *pred = loopBlock->getPredecessor(i);
michael@0:                         if (loopDone->contains(pred->id()))
michael@0:                             continue;
michael@0:                         if (!loopWorkList.append(pred))
michael@0:                             return false;
michael@0:                     }
michael@0:                 }
michael@0: 
michael@0:                 // Terminate loop if out of work.
michael@0:                 if (loopWorkList.empty())
michael@0:                     break;
michael@0: 
michael@0:                 // Grab the next block off the work list, skipping any OSR block.
michael@0:                 while (!loopWorkList.empty()) {
michael@0:                     loopBlock = loopWorkList.popCopy();
michael@0:                     if (loopBlock->lir() != graph.osrBlock())
michael@0:                         break;
michael@0:                 }
michael@0: 
michael@0:                 // If end is reached without finding a non-OSR block, then no more work items were found.
michael@0:                 if (loopBlock->lir() == graph.osrBlock()) {
michael@0:                     JS_ASSERT(loopWorkList.empty());
michael@0:                     break;
michael@0:                 }
michael@0:             }
michael@0: 
michael@0:             // Clear the done set for other loops
michael@0:             loopDone->clear();
michael@0:         }
michael@0: 
michael@0:         JS_ASSERT_IF(!mblock->numPredecessors(), live->empty());
michael@0:     }
michael@0: 
michael@0:     validateVirtualRegisters();
michael@0: 
michael@0:     // If the script has an infinite loop, there may be no MReturn and therefore
michael@0:     // no fixed intervals. Add a small range to fixedIntervalsUnion so that the
michael@0:     // rest of the allocator can assume it has at least one range.
michael@0:     if (fixedIntervalsUnion->numRanges() == 0) {
michael@0:         if (!fixedIntervalsUnion->addRangeAtHead(CodePosition(0, CodePosition::INPUT),
michael@0:                                                  CodePosition(0, CodePosition::OUTPUT)))
michael@0:         {
michael@0:             return false;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: #ifdef DEBUG
michael@0: 
michael@0: void
michael@0: LiveInterval::validateRanges()
michael@0: {
michael@0:     Range *prev = nullptr;
michael@0: 
michael@0:     for (size_t i = ranges_.length() - 1; i < ranges_.length(); i--) {
michael@0:         Range *range = &ranges_[i];
michael@0: 
michael@0:         JS_ASSERT(range->from < range->to);
michael@0:         JS_ASSERT_IF(prev, prev->to <= range->from);
michael@0:         prev = range;
michael@0:     }
michael@0: }
michael@0: 
michael@0: #endif // DEBUG
michael@0: 
michael@0: const char *
michael@0: LiveInterval::rangesToString() const
michael@0: {
michael@0: #ifdef DEBUG
michael@0:     if (!numRanges())
michael@0:         return " empty";
michael@0: 
michael@0:     // Not reentrant!
michael@0:     static char buf[1000];
michael@0: 
michael@0:     char *cursor = buf;
michael@0:     char *end = cursor + sizeof(buf);
michael@0: 
michael@0:     for (size_t i = 0; i < numRanges(); i++) {
michael@0:         const LiveInterval::Range *range = getRange(i);
michael@0:         int n = JS_snprintf(cursor, end - cursor, " [%u,%u>", range->from.pos(), range->to.pos());
michael@0:         if (n < 0)
michael@0:             return " ???";
michael@0:         cursor += n;
michael@0:     }
michael@0: 
michael@0:     return buf;
michael@0: #else
michael@0:     return " ???";
michael@0: #endif
michael@0: }
michael@0: 
michael@0: void
michael@0: LiveInterval::dump()
michael@0: {
michael@0:     fprintf(stderr, "v%u: index=%u allocation=%s %s\n",
michael@0:             vreg(), index(), getAllocation()->toString(), rangesToString());
michael@0: }