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

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

js/src/jit/LiveRangeAllocator.cpp

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

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

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

 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
  * vim: set ts=8 sts=4 et sw=4 tw=99:
  * This Source Code Form is subject to the terms of the Mozilla Public
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 #include "jit/LiveRangeAllocator.h"
 #include "mozilla/DebugOnly.h"
 #include "jsprf.h"
 #include "jit/BacktrackingAllocator.h"
 #include "jit/BitSet.h"
 #include "jit/LinearScan.h"
 using namespace js;
 using namespace js::jit;
 using mozilla::DebugOnly;
 int
 Requirement::priority() const
 {
     switch (kind_) {
       case Requirement::FIXED:
         return 0;
       case Requirement::REGISTER:
         return 1;
       case Requirement::NONE:
         return 2;
       default:
         MOZ_ASSUME_UNREACHABLE("Unknown requirement kind.");
     }
 }
 bool
 LiveInterval::Range::contains(const Range *other) const
 {
     return from <= other->from && to >= other->to;
 }
 void
 LiveInterval::Range::intersect(const Range *other, Range *pre, Range *inside, Range *post) const
 {
     JS_ASSERT(pre->empty() && inside->empty() && post->empty());
     CodePosition innerFrom = from;
     if (from < other->from) {
         if (to < other->from) {
             *pre = Range(from, to);
             return;
         }
         *pre = Range(from, other->from);
         innerFrom = other->from;
     }
     CodePosition innerTo = to;
     if (to > other->to) {
         if (from >= other->to) {
             *post = Range(from, to);
             return;
         }
         *post = Range(other->to, to);
         innerTo = other->to;
     }
     if (innerFrom != innerTo)
         *inside = Range(innerFrom, innerTo);
 }
 bool
 LiveInterval::addRangeAtHead(CodePosition from, CodePosition to)
 {
     JS_ASSERT(from < to);
     Range newRange(from, to);
     if (ranges_.empty())
         return ranges_.append(newRange);
     Range &first = ranges_.back();
     if (to < first.from)
         return ranges_.append(newRange);
     if (to == first.from) {
         first.from = from;
         return true;
     }
     JS_ASSERT(from < first.to);
     JS_ASSERT(to > first.from);
     if (from < first.from)
         first.from = from;
     if (to > first.to)
         first.to = to;
     return true;
 }
 bool
 LiveInterval::addRange(CodePosition from, CodePosition to)
 {
     JS_ASSERT(from < to);
     Range newRange(from, to);
     Range *i;
     // Find the location to insert the new range
     for (i = ranges_.end() - 1; i >= ranges_.begin(); i--) {
         if (newRange.from <= i->to) {
             if (i->from < newRange.from)
                 newRange.from = i->from;
             break;
         }
     }
     // Perform coalescing on overlapping ranges
     for (; i >= ranges_.begin(); i--) {
         if (newRange.to < i->from)
             break;
         if (newRange.to < i->to)
             newRange.to = i->to;
         ranges_.erase(i);
     }
     return ranges_.insert(i + 1, newRange);
 }
 void
 LiveInterval::setFrom(CodePosition from)
 {
     while (!ranges_.empty()) {
         if (ranges_.back().to < from) {
             ranges_.erase(&ranges_.back());
         } else {
             if (from == ranges_.back().to)
                 ranges_.erase(&ranges_.back());
             else
                 ranges_.back().from = from;
             break;
         }
     }
 }
 bool
 LiveInterval::covers(CodePosition pos)
 {
     if (pos < start() || pos >= end())
         return false;
     // Loop over the ranges in ascending order.
     size_t i = lastProcessedRangeIfValid(pos);
     for (; i < ranges_.length(); i--) {
         if (pos < ranges_[i].from)
             return false;
         setLastProcessedRange(i, pos);
         if (pos < ranges_[i].to)
             return true;
     }
     return false;
 }
 CodePosition
 LiveInterval::nextCoveredAfter(CodePosition pos)
 {
     for (size_t i = 0; i < ranges_.length(); i++) {
         if (ranges_[i].to <= pos) {
             if (i)
                 return ranges_[i-1].from;
             break;
         }
         if (ranges_[i].from <= pos)
             return pos;
     }
     return CodePosition::MIN;
 }
 CodePosition
 LiveInterval::intersect(LiveInterval *other)
 {
     if (start() > other->start())
         return other->intersect(this);
     // Loop over the ranges in ascending order. As an optimization,
     // try to start at the last processed range.
     size_t i = lastProcessedRangeIfValid(other->start());
     size_t j = other->ranges_.length() - 1;
     if (i >= ranges_.length() || j >= other->ranges_.length())
         return CodePosition::MIN;
     while (true) {
         const Range &r1 = ranges_[i];
         const Range &r2 = other->ranges_[j];
         if (r1.from <= r2.from) {
             if (r1.from <= other->start())
                 setLastProcessedRange(i, other->start());
             if (r2.from < r1.to)
                 return r2.from;
             if (i == 0 || ranges_[i-1].from > other->end())
                 break;
             i--;
         } else {
             if (r1.from < r2.to)
                 return r1.from;
             if (j == 0 || other->ranges_[j-1].from > end())
                 break;
             j--;
         }
     }
     return CodePosition::MIN;
 }
 /*
  * This function takes the callee interval and moves all ranges following or
  * including provided position to the target interval. Additionally, if a
  * range in the callee interval spans the given position, it is split and the
  * latter half is placed in the target interval.
  *
  * This function should only be called if it is known that the interval should
  * actually be split (and, presumably, a move inserted). As such, it is an
  * error for the caller to request a split that moves all intervals into the
  * target. Doing so will trip the assertion at the bottom of the function.
  */
 bool
 LiveInterval::splitFrom(CodePosition pos, LiveInterval *after)
 {
     JS_ASSERT(pos >= start() && pos < end());
     JS_ASSERT(after->ranges_.empty());
     // Move all intervals over to the target
     size_t bufferLength = ranges_.length();
     Range *buffer = ranges_.extractRawBuffer();
     if (!buffer)
         return false;
     after->ranges_.replaceRawBuffer(buffer, bufferLength);
     // Move intervals back as required
     for (Range *i = &after->ranges_.back(); i >= after->ranges_.begin(); i--) {
         if (pos >= i->to)
             continue;
         if (pos > i->from) {
             // Split the range
             Range split(i->from, pos);
             i->from = pos;
             if (!ranges_.append(split))
                 return false;
         }
         if (!ranges_.append(i + 1, after->ranges_.end()))
             return false;
         after->ranges_.shrinkBy(after->ranges_.end() - i - 1);
         break;
     }
     // Split the linked list of use positions
     UsePosition *prev = nullptr;
     for (UsePositionIterator usePos(usesBegin()); usePos != usesEnd(); usePos++) {
         if (usePos->pos > pos)
             break;
         prev = *usePos;
     }
     uses_.splitAfter(prev, &after->uses_);
     return true;
 }
 void
 LiveInterval::addUse(UsePosition *use)
 {
     // Insert use positions in ascending order. Note that instructions
     // are visited in reverse order, so in most cases the loop terminates
     // at the first iteration and the use position will be added to the
     // front of the list.
     UsePosition *prev = nullptr;
     for (UsePositionIterator current(usesBegin()); current != usesEnd(); current++) {
         if (current->pos >= use->pos)
             break;
         prev = *current;
     }
     if (prev)
         uses_.insertAfter(prev, use);
     else
         uses_.pushFront(use);
 }
 void
 LiveInterval::addUseAtEnd(UsePosition *use)
 {
     JS_ASSERT(uses_.empty() || use->pos >= uses_.back()->pos);
     uses_.pushBack(use);
 }
 UsePosition *
 LiveInterval::nextUseAfter(CodePosition after)
 {
     for (UsePositionIterator usePos(usesBegin()); usePos != usesEnd(); usePos++) {
         if (usePos->pos >= after) {
             LUse::Policy policy = usePos->use->policy();
             JS_ASSERT(policy != LUse::RECOVERED_INPUT);
             if (policy != LUse::KEEPALIVE)
                 return *usePos;
         }
     }
     return nullptr;
 }
 /*
  * This function locates the first "real" use of this interval that follows
  * the given code position. Non-"real" uses are currently just snapshots,
  * which keep virtual registers alive but do not result in the
  * generation of code that use them.
  */
 CodePosition
 LiveInterval::nextUsePosAfter(CodePosition after)
 {
     UsePosition *min = nextUseAfter(after);
     return min ? min->pos : CodePosition::MAX;
 }
 /*
  * This function finds the position of the first use of this interval
  * that is incompatible with the provideded allocation. For example,
  * a use with a REGISTER policy would be incompatible with a stack slot
  * allocation.
  */
 CodePosition
 LiveInterval::firstIncompatibleUse(LAllocation alloc)
 {
     for (UsePositionIterator usePos(usesBegin()); usePos != usesEnd(); usePos++) {
         if (!UseCompatibleWith(usePos->use, alloc))
             return usePos->pos;
     }
     return CodePosition::MAX;
 }
 LiveInterval *
 VirtualRegister::intervalFor(CodePosition pos)
 {
     for (LiveInterval **i = intervals_.begin(); i != intervals_.end(); i++) {
         if ((*i)->covers(pos))
             return *i;
         if (pos < (*i)->end())
             break;
     }
     return nullptr;
 }
 LiveInterval *
 VirtualRegister::getFirstInterval()
 {
     JS_ASSERT(!intervals_.empty());
     return intervals_[0];
 }
 // Instantiate LiveRangeAllocator for each template instance.
 template bool LiveRangeAllocator<LinearScanVirtualRegister, true>::buildLivenessInfo();
 template bool LiveRangeAllocator<BacktrackingVirtualRegister, false>::buildLivenessInfo();
 #ifdef DEBUG
 static inline bool
 NextInstructionHasFixedUses(LBlock *block, LInstruction *ins)
 {
     LInstructionIterator iter(block->begin(ins));
     iter++;
     for (LInstruction::InputIterator alloc(**iter); alloc.more(); alloc.next()) {
         if (alloc->isUse() && alloc->toUse()->isFixedRegister())
             return true;
     }
     return false;
 }
 // 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 pre-allocates and initializes as much global state as possible
  * to avoid littering the algorithms with memory management cruft.
  */
 template <typename VREG, bool forLSRA>
 bool
 LiveRangeAllocator<VREG, forLSRA>::init()
 {
     if (!RegisterAllocator::init())
         return false;
     liveIn = mir->allocate<BitSet*>(graph.numBlockIds());
     if (!liveIn)
         return false;
     // Initialize fixed intervals.
     for (size_t i = 0; i < AnyRegister::Total; i++) {
         AnyRegister reg = AnyRegister::FromCode(i);
         LiveInterval *interval = LiveInterval::New(alloc(), 0);
         interval->setAllocation(LAllocation(reg));
         fixedIntervals[i] = interval;
     }
     fixedIntervalsUnion = LiveInterval::New(alloc(), 0);
     if (!vregs.init(mir, graph.numVirtualRegisters()))
         return false;
     // 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->policy() != LDefinition::PASSTHROUGH) {
                     if (!vregs[def].init(alloc(), block, *ins, def, /* isTemp */ false))
                         return false;
                 }
             }
             for (size_t j = 0; j < ins->numTemps(); j++) {
                 LDefinition *def = ins->getTemp(j);
                 if (def->isBogusTemp())
                     continue;
                 if (!vregs[def].init(alloc(), block, *ins, def, /* isTemp */ true))
                     return false;
             }
         }
         for (size_t j = 0; j < block->numPhis(); j++) {
             LPhi *phi = block->getPhi(j);
             LDefinition *def = phi->getDef(0);
             if (!vregs[def].init(alloc(), block, phi, def, /* isTemp */ false))
                 return false;
         }
     }
     return true;
 }
 static void
 AddRegisterToSafepoint(LSafepoint *safepoint, AnyRegister reg, const LDefinition &def)
 {
     safepoint->addLiveRegister(reg);
     JS_ASSERT(def.type() == LDefinition::GENERAL ||
               def.type() == LDefinition::INT32 ||
               def.type() == LDefinition::DOUBLE ||
               def.type() == LDefinition::FLOAT32 ||
               def.type() == LDefinition::OBJECT);
     if (def.type() == LDefinition::OBJECT)
         safepoint->addGcRegister(reg.gpr());
 }
 /*
  * This function builds up liveness intervals 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 intervals at
  * definitions, and recording which registers are live at the top of every
  * block. To deal with loop backedges, variables live at the beginning of
  * a loop gain an interval covering the entire loop.
  */
 template <typename VREG, bool forLSRA>
 bool
 LiveRangeAllocator<VREG, forLSRA>::buildLivenessInfo()
 {
     if (!init())
         return false;
     Vector<MBasicBlock *, 1, SystemAllocPolicy> loopWorkList;
     BitSet *loopDone = BitSet::New(alloc(), graph.numBlockIds());
     if (!loopDone)
         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 = BitSet::New(alloc(), graph.numVirtualRegisters());
         if (!live)
             return false;
         liveIn[mblock->id()] = live;
         // 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);
             }
         }
         // Variables are assumed alive for the entire block, a define shortens
         // the interval to the point of definition.
         for (BitSet::Iterator liveRegId(*live); liveRegId; liveRegId++) {
             if (!vregs[*liveRegId].getInterval(0)->addRangeAtHead(inputOf(block->firstId()),
                                                                   outputOf(block->lastId()).next()))
             {
                 return false;
             }
         }
         // Shorten the front end of live intervals 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_); iter.more(); iter++) {
                     if (forLSRA) {
                         if (!addFixedRangeAtHead(*iter, inputOf(*ins), outputOf(*ins)))
                             return false;
                     } else {
                         bool found = false;
                         for (size_t i = 0; i < ins->numDefs(); i++) {
                             if (ins->getDef(i)->isPreset() &&
                                 *ins->getDef(i)->output() == LAllocation(*iter)) {
                                 found = true;
                                 break;
                             }
                         }
                         if (!found && !addFixedRangeAtHead(*iter, outputOf(*ins), outputOf(*ins).next()))
                             return false;
                     }
                 }
             }
             for (size_t i = 0; i < ins->numDefs(); i++) {
                 if (ins->getDef(i)->policy() != LDefinition::PASSTHROUGH) {
                     LDefinition *def = ins->getDef(i);
                     CodePosition from;
                     if (def->policy() == LDefinition::PRESET && def->output()->isRegister() && forLSRA) {
                         // The fixed range covers the current instruction so the
                         // interval for the virtual register starts at the next
                         // instruction. If the next instruction has a fixed use,
                         // this can lead to unnecessary register moves. To avoid
                         // special handling for this, assert the next instruction
                         // has no fixed uses. defineFixed guarantees this by inserting
                         // an LNop.
                         JS_ASSERT(!NextInstructionHasFixedUses(block, *ins));
                         AnyRegister reg = def->output()->toRegister();
                         if (!addFixedRangeAtHead(reg, inputOf(*ins), outputOf(*ins).next()))
                             return false;
                         from = outputOf(*ins).next();
                     } else {
                         from = forLSRA ? inputOf(*ins) : 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();
                         JS_ASSERT(inputUse->policy() == LUse::REGISTER);
                         JS_ASSERT(inputUse->usedAtStart());
                         *inputUse = LUse(inputUse->virtualRegister(), LUse::ANY, /* usedAtStart = */ true);
                     }
                     LiveInterval *interval = vregs[def].getInterval(0);
                     interval->setFrom(from);
                     // Ensure that if there aren't any uses, there's at least
                     // some interval for the output to go into.
                     if (interval->numRanges() == 0) {
                         if (!interval->addRangeAtHead(from, from.next()))
                             return false;
                     }
                     live->remove(def->virtualRegister());
                 }
             }
             for (size_t i = 0; i < ins->numTemps(); i++) {
                 LDefinition *temp = ins->getTemp(i);
                 if (temp->isBogusTemp())
                     continue;
                 if (forLSRA) {
                     if (temp->policy() == LDefinition::PRESET) {
                         if (ins->isCall())
                             continue;
                         AnyRegister reg = temp->output()->toRegister();
                         if (!addFixedRangeAtHead(reg, inputOf(*ins), outputOf(*ins)))
                             return false;
                         // Fixed intervals are not added to safepoints, so do it
                         // here.
                         if (LSafepoint *safepoint = ins->safepoint())
                             AddRegisterToSafepoint(safepoint, reg, *temp);
                     } else {
                         JS_ASSERT(!ins->isCall());
                         if (!vregs[temp].getInterval(0)->addRangeAtHead(inputOf(*ins), outputOf(*ins)))
                             return false;
                     }
                 } else {
                     // 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::PRESET) {
                         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(vregs[use].def(), use) == reg)
                                         from = outputOf(*ins);
                                 }
                             }
                         }
                     }
                     CodePosition to =
                         ins->isCall() ? outputOf(*ins) : outputOf(*ins).next();
                     if (!vregs[temp].getInterval(0)->addRangeAtHead(from, to))
                         return false;
                 }
             }
             DebugOnly<bool> hasUseRegister = false;
             DebugOnly<bool> hasUseRegisterAtStart = false;
             for (LInstruction::InputIterator inputAlloc(**ins); inputAlloc.more(); inputAlloc.next()) {
                 if (inputAlloc->isUse()) {
                     LUse *use = inputAlloc->toUse();
                     // The first instruction, LLabel, has no uses.
                     JS_ASSERT_IF(forLSRA, inputOf(*ins) > outputOf(block->firstId()));
                     // Call uses should always be at-start or fixed, since the fixed intervals
                     // use all registers.
                     JS_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++)
                             JS_ASSERT(vregs[ins->getTemp(i)].isFloatReg() != vregs[use].isFloatReg());
                     }
                     // If there are both useRegisterAtStart(x) and useRegister(y)
                     // uses, we may assign the same register to both operands due to
                     // interval splitting (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;
                         }
                     }
                     JS_ASSERT(!(hasUseRegister && hasUseRegisterAtStart));
 #endif
                     // Don't treat RECOVERED_INPUT uses as keeping the vreg alive.
                     if (use->policy() == LUse::RECOVERED_INPUT)
                         continue;
                     CodePosition to;
                     if (forLSRA) {
                         if (use->isFixedRegister()) {
                             AnyRegister reg = GetFixedRegister(vregs[use].def(), use);
                             if (!addFixedRangeAtHead(reg, inputOf(*ins), outputOf(*ins)))
                                 return false;
                             to = inputOf(*ins);
                             // Fixed intervals are not added to safepoints, so do it
                             // here.
                             LSafepoint *safepoint = ins->safepoint();
                             if (!ins->isCall() && safepoint)
                                 AddRegisterToSafepoint(safepoint, reg, *vregs[use].def());
                         } else {
                             to = use->usedAtStart() ? inputOf(*ins) : outputOf(*ins);
                         }
                     } else {
                         to = (use->usedAtStart() || ins->isCall())
                            ? 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::PRESET && *def->output() == reg)
                                     to = inputOf(*ins);
                             }
                         }
                     }
                     LiveInterval *interval = vregs[use].getInterval(0);
                     if (!interval->addRangeAtHead(inputOf(block->firstId()), forLSRA ? to : to.next()))
                         return false;
                     interval->addUse(new(alloc()) UsePosition(use, to));
                     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.
                 if (!vregs[def].getInterval(0)->addRangeAtHead(inputOf(block->firstId()),
                                                                outputOf(block->firstId())))
                 {
                     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 interval 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.
                 JS_ASSERT(loopBlock->id() >= mblock->id());
                 // Add an interval for this entire loop block
                 CodePosition from = inputOf(loopBlock->lir()->firstId());
                 CodePosition to = outputOf(loopBlock->lir()->lastId()).next();
                 for (BitSet::Iterator liveRegId(*live); liveRegId; liveRegId++) {
                     if (!vregs[*liveRegId].getInterval(0)->addRange(from, to))
                         return false;
                 }
                 // Fix up the liveIn set to account for the new interval
                 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.
                 while (!loopWorkList.empty()) {
                     loopBlock = loopWorkList.popCopy();
                     if (loopBlock->lir() != graph.osrBlock())
                         break;
                 }
                 // If end is reached without finding a non-OSR block, then no more work items were found.
                 if (loopBlock->lir() == graph.osrBlock()) {
                     JS_ASSERT(loopWorkList.empty());
                     break;
                 }
             }
             // Clear the done set for other loops
             loopDone->clear();
         }
         JS_ASSERT_IF(!mblock->numPredecessors(), live->empty());
     }
     validateVirtualRegisters();
     // If the script has an infinite loop, there may be no MReturn and therefore
     // no fixed intervals. Add a small range to fixedIntervalsUnion so that the
     // rest of the allocator can assume it has at least one range.
     if (fixedIntervalsUnion->numRanges() == 0) {
         if (!fixedIntervalsUnion->addRangeAtHead(CodePosition(0, CodePosition::INPUT),
                                                  CodePosition(0, CodePosition::OUTPUT)))
         {
             return false;
         }
     }
     return true;
 }
 #ifdef DEBUG
 void
 LiveInterval::validateRanges()
 {
     Range *prev = nullptr;
     for (size_t i = ranges_.length() - 1; i < ranges_.length(); i--) {
         Range *range = &ranges_[i];
         JS_ASSERT(range->from < range->to);
         JS_ASSERT_IF(prev, prev->to <= range->from);
         prev = range;
     }
 }
 #endif // DEBUG
 const char *
 LiveInterval::rangesToString() const
 {
 #ifdef DEBUG
     if (!numRanges())
         return " empty";
     // Not reentrant!
     static char buf[1000];
     char *cursor = buf;
     char *end = cursor + sizeof(buf);
     for (size_t i = 0; i < numRanges(); i++) {
         const LiveInterval::Range *range = getRange(i);
         int n = JS_snprintf(cursor, end - cursor, " [%u,%u>", range->from.pos(), range->to.pos());
         if (n < 0)
             return " ???";
         cursor += n;
     }
     return buf;
 #else
     return " ???";
 #endif
 }
 void
 LiveInterval::dump()
 {
     fprintf(stderr, "v%u: index=%u allocation=%s %s\n",
             vreg(), index(), getAllocation()->toString(), rangesToString());
 }

The Tor Browser / annotate

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

js/src/jit/LiveRangeAllocator.cpp