1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/js/src/jit/LiveRangeAllocator.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,901 @@
1.4 +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
1.5 + * vim: set ts=8 sts=4 et sw=4 tw=99:
1.6 + * This Source Code Form is subject to the terms of the Mozilla Public
1.7 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.8 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.9 +
1.10 +#include "jit/LiveRangeAllocator.h"
1.11 +
1.12 +#include "mozilla/DebugOnly.h"
1.13 +
1.14 +#include "jsprf.h"
1.15 +
1.16 +#include "jit/BacktrackingAllocator.h"
1.17 +#include "jit/BitSet.h"
1.18 +#include "jit/LinearScan.h"
1.19 +
1.20 +using namespace js;
1.21 +using namespace js::jit;
1.22 +
1.23 +using mozilla::DebugOnly;
1.24 +
1.25 +int
1.26 +Requirement::priority() const
1.27 +{
1.28 + switch (kind_) {
1.29 + case Requirement::FIXED:
1.30 + return 0;
1.31 +
1.32 + case Requirement::REGISTER:
1.33 + return 1;
1.34 +
1.35 + case Requirement::NONE:
1.36 + return 2;
1.37 +
1.38 + default:
1.39 + MOZ_ASSUME_UNREACHABLE("Unknown requirement kind.");
1.40 + }
1.41 +}
1.42 +
1.43 +bool
1.44 +LiveInterval::Range::contains(const Range *other) const
1.45 +{
1.46 + return from <= other->from && to >= other->to;
1.47 +}
1.48 +
1.49 +void
1.50 +LiveInterval::Range::intersect(const Range *other, Range *pre, Range *inside, Range *post) const
1.51 +{
1.52 + JS_ASSERT(pre->empty() && inside->empty() && post->empty());
1.53 +
1.54 + CodePosition innerFrom = from;
1.55 + if (from < other->from) {
1.56 + if (to < other->from) {
1.57 + *pre = Range(from, to);
1.58 + return;
1.59 + }
1.60 + *pre = Range(from, other->from);
1.61 + innerFrom = other->from;
1.62 + }
1.63 +
1.64 + CodePosition innerTo = to;
1.65 + if (to > other->to) {
1.66 + if (from >= other->to) {
1.67 + *post = Range(from, to);
1.68 + return;
1.69 + }
1.70 + *post = Range(other->to, to);
1.71 + innerTo = other->to;
1.72 + }
1.73 +
1.74 + if (innerFrom != innerTo)
1.75 + *inside = Range(innerFrom, innerTo);
1.76 +}
1.77 +
1.78 +bool
1.79 +LiveInterval::addRangeAtHead(CodePosition from, CodePosition to)
1.80 +{
1.81 + JS_ASSERT(from < to);
1.82 +
1.83 + Range newRange(from, to);
1.84 +
1.85 + if (ranges_.empty())
1.86 + return ranges_.append(newRange);
1.87 +
1.88 + Range &first = ranges_.back();
1.89 + if (to < first.from)
1.90 + return ranges_.append(newRange);
1.91 +
1.92 + if (to == first.from) {
1.93 + first.from = from;
1.94 + return true;
1.95 + }
1.96 +
1.97 + JS_ASSERT(from < first.to);
1.98 + JS_ASSERT(to > first.from);
1.99 + if (from < first.from)
1.100 + first.from = from;
1.101 + if (to > first.to)
1.102 + first.to = to;
1.103 +
1.104 + return true;
1.105 +}
1.106 +
1.107 +bool
1.108 +LiveInterval::addRange(CodePosition from, CodePosition to)
1.109 +{
1.110 + JS_ASSERT(from < to);
1.111 +
1.112 + Range newRange(from, to);
1.113 +
1.114 + Range *i;
1.115 + // Find the location to insert the new range
1.116 + for (i = ranges_.end() - 1; i >= ranges_.begin(); i--) {
1.117 + if (newRange.from <= i->to) {
1.118 + if (i->from < newRange.from)
1.119 + newRange.from = i->from;
1.120 + break;
1.121 + }
1.122 + }
1.123 + // Perform coalescing on overlapping ranges
1.124 + for (; i >= ranges_.begin(); i--) {
1.125 + if (newRange.to < i->from)
1.126 + break;
1.127 + if (newRange.to < i->to)
1.128 + newRange.to = i->to;
1.129 + ranges_.erase(i);
1.130 + }
1.131 +
1.132 + return ranges_.insert(i + 1, newRange);
1.133 +}
1.134 +
1.135 +void
1.136 +LiveInterval::setFrom(CodePosition from)
1.137 +{
1.138 + while (!ranges_.empty()) {
1.139 + if (ranges_.back().to < from) {
1.140 + ranges_.erase(&ranges_.back());
1.141 + } else {
1.142 + if (from == ranges_.back().to)
1.143 + ranges_.erase(&ranges_.back());
1.144 + else
1.145 + ranges_.back().from = from;
1.146 + break;
1.147 + }
1.148 + }
1.149 +}
1.150 +
1.151 +bool
1.152 +LiveInterval::covers(CodePosition pos)
1.153 +{
1.154 + if (pos < start() || pos >= end())
1.155 + return false;
1.156 +
1.157 + // Loop over the ranges in ascending order.
1.158 + size_t i = lastProcessedRangeIfValid(pos);
1.159 + for (; i < ranges_.length(); i--) {
1.160 + if (pos < ranges_[i].from)
1.161 + return false;
1.162 + setLastProcessedRange(i, pos);
1.163 + if (pos < ranges_[i].to)
1.164 + return true;
1.165 + }
1.166 + return false;
1.167 +}
1.168 +
1.169 +CodePosition
1.170 +LiveInterval::nextCoveredAfter(CodePosition pos)
1.171 +{
1.172 + for (size_t i = 0; i < ranges_.length(); i++) {
1.173 + if (ranges_[i].to <= pos) {
1.174 + if (i)
1.175 + return ranges_[i-1].from;
1.176 + break;
1.177 + }
1.178 + if (ranges_[i].from <= pos)
1.179 + return pos;
1.180 + }
1.181 + return CodePosition::MIN;
1.182 +}
1.183 +
1.184 +CodePosition
1.185 +LiveInterval::intersect(LiveInterval *other)
1.186 +{
1.187 + if (start() > other->start())
1.188 + return other->intersect(this);
1.189 +
1.190 + // Loop over the ranges in ascending order. As an optimization,
1.191 + // try to start at the last processed range.
1.192 + size_t i = lastProcessedRangeIfValid(other->start());
1.193 + size_t j = other->ranges_.length() - 1;
1.194 + if (i >= ranges_.length() || j >= other->ranges_.length())
1.195 + return CodePosition::MIN;
1.196 +
1.197 + while (true) {
1.198 + const Range &r1 = ranges_[i];
1.199 + const Range &r2 = other->ranges_[j];
1.200 +
1.201 + if (r1.from <= r2.from) {
1.202 + if (r1.from <= other->start())
1.203 + setLastProcessedRange(i, other->start());
1.204 + if (r2.from < r1.to)
1.205 + return r2.from;
1.206 + if (i == 0 || ranges_[i-1].from > other->end())
1.207 + break;
1.208 + i--;
1.209 + } else {
1.210 + if (r1.from < r2.to)
1.211 + return r1.from;
1.212 + if (j == 0 || other->ranges_[j-1].from > end())
1.213 + break;
1.214 + j--;
1.215 + }
1.216 + }
1.217 +
1.218 + return CodePosition::MIN;
1.219 +}
1.220 +
1.221 +/*
1.222 + * This function takes the callee interval and moves all ranges following or
1.223 + * including provided position to the target interval. Additionally, if a
1.224 + * range in the callee interval spans the given position, it is split and the
1.225 + * latter half is placed in the target interval.
1.226 + *
1.227 + * This function should only be called if it is known that the interval should
1.228 + * actually be split (and, presumably, a move inserted). As such, it is an
1.229 + * error for the caller to request a split that moves all intervals into the
1.230 + * target. Doing so will trip the assertion at the bottom of the function.
1.231 + */
1.232 +bool
1.233 +LiveInterval::splitFrom(CodePosition pos, LiveInterval *after)
1.234 +{
1.235 + JS_ASSERT(pos >= start() && pos < end());
1.236 + JS_ASSERT(after->ranges_.empty());
1.237 +
1.238 + // Move all intervals over to the target
1.239 + size_t bufferLength = ranges_.length();
1.240 + Range *buffer = ranges_.extractRawBuffer();
1.241 + if (!buffer)
1.242 + return false;
1.243 + after->ranges_.replaceRawBuffer(buffer, bufferLength);
1.244 +
1.245 + // Move intervals back as required
1.246 + for (Range *i = &after->ranges_.back(); i >= after->ranges_.begin(); i--) {
1.247 + if (pos >= i->to)
1.248 + continue;
1.249 +
1.250 + if (pos > i->from) {
1.251 + // Split the range
1.252 + Range split(i->from, pos);
1.253 + i->from = pos;
1.254 + if (!ranges_.append(split))
1.255 + return false;
1.256 + }
1.257 + if (!ranges_.append(i + 1, after->ranges_.end()))
1.258 + return false;
1.259 + after->ranges_.shrinkBy(after->ranges_.end() - i - 1);
1.260 + break;
1.261 + }
1.262 +
1.263 + // Split the linked list of use positions
1.264 + UsePosition *prev = nullptr;
1.265 + for (UsePositionIterator usePos(usesBegin()); usePos != usesEnd(); usePos++) {
1.266 + if (usePos->pos > pos)
1.267 + break;
1.268 + prev = *usePos;
1.269 + }
1.270 +
1.271 + uses_.splitAfter(prev, &after->uses_);
1.272 + return true;
1.273 +}
1.274 +
1.275 +void
1.276 +LiveInterval::addUse(UsePosition *use)
1.277 +{
1.278 + // Insert use positions in ascending order. Note that instructions
1.279 + // are visited in reverse order, so in most cases the loop terminates
1.280 + // at the first iteration and the use position will be added to the
1.281 + // front of the list.
1.282 + UsePosition *prev = nullptr;
1.283 + for (UsePositionIterator current(usesBegin()); current != usesEnd(); current++) {
1.284 + if (current->pos >= use->pos)
1.285 + break;
1.286 + prev = *current;
1.287 + }
1.288 +
1.289 + if (prev)
1.290 + uses_.insertAfter(prev, use);
1.291 + else
1.292 + uses_.pushFront(use);
1.293 +}
1.294 +
1.295 +void
1.296 +LiveInterval::addUseAtEnd(UsePosition *use)
1.297 +{
1.298 + JS_ASSERT(uses_.empty() || use->pos >= uses_.back()->pos);
1.299 + uses_.pushBack(use);
1.300 +}
1.301 +
1.302 +UsePosition *
1.303 +LiveInterval::nextUseAfter(CodePosition after)
1.304 +{
1.305 + for (UsePositionIterator usePos(usesBegin()); usePos != usesEnd(); usePos++) {
1.306 + if (usePos->pos >= after) {
1.307 + LUse::Policy policy = usePos->use->policy();
1.308 + JS_ASSERT(policy != LUse::RECOVERED_INPUT);
1.309 + if (policy != LUse::KEEPALIVE)
1.310 + return *usePos;
1.311 + }
1.312 + }
1.313 + return nullptr;
1.314 +}
1.315 +
1.316 +/*
1.317 + * This function locates the first "real" use of this interval that follows
1.318 + * the given code position. Non-"real" uses are currently just snapshots,
1.319 + * which keep virtual registers alive but do not result in the
1.320 + * generation of code that use them.
1.321 + */
1.322 +CodePosition
1.323 +LiveInterval::nextUsePosAfter(CodePosition after)
1.324 +{
1.325 + UsePosition *min = nextUseAfter(after);
1.326 + return min ? min->pos : CodePosition::MAX;
1.327 +}
1.328 +
1.329 +/*
1.330 + * This function finds the position of the first use of this interval
1.331 + * that is incompatible with the provideded allocation. For example,
1.332 + * a use with a REGISTER policy would be incompatible with a stack slot
1.333 + * allocation.
1.334 + */
1.335 +CodePosition
1.336 +LiveInterval::firstIncompatibleUse(LAllocation alloc)
1.337 +{
1.338 + for (UsePositionIterator usePos(usesBegin()); usePos != usesEnd(); usePos++) {
1.339 + if (!UseCompatibleWith(usePos->use, alloc))
1.340 + return usePos->pos;
1.341 + }
1.342 + return CodePosition::MAX;
1.343 +}
1.344 +
1.345 +LiveInterval *
1.346 +VirtualRegister::intervalFor(CodePosition pos)
1.347 +{
1.348 + for (LiveInterval **i = intervals_.begin(); i != intervals_.end(); i++) {
1.349 + if ((*i)->covers(pos))
1.350 + return *i;
1.351 + if (pos < (*i)->end())
1.352 + break;
1.353 + }
1.354 + return nullptr;
1.355 +}
1.356 +
1.357 +LiveInterval *
1.358 +VirtualRegister::getFirstInterval()
1.359 +{
1.360 + JS_ASSERT(!intervals_.empty());
1.361 + return intervals_[0];
1.362 +}
1.363 +
1.364 +// Instantiate LiveRangeAllocator for each template instance.
1.365 +template bool LiveRangeAllocator<LinearScanVirtualRegister, true>::buildLivenessInfo();
1.366 +template bool LiveRangeAllocator<BacktrackingVirtualRegister, false>::buildLivenessInfo();
1.367 +
1.368 +#ifdef DEBUG
1.369 +static inline bool
1.370 +NextInstructionHasFixedUses(LBlock *block, LInstruction *ins)
1.371 +{
1.372 + LInstructionIterator iter(block->begin(ins));
1.373 + iter++;
1.374 + for (LInstruction::InputIterator alloc(**iter); alloc.more(); alloc.next()) {
1.375 + if (alloc->isUse() && alloc->toUse()->isFixedRegister())
1.376 + return true;
1.377 + }
1.378 + return false;
1.379 +}
1.380 +
1.381 +// Returns true iff ins has a def/temp reusing the input allocation.
1.382 +static bool
1.383 +IsInputReused(LInstruction *ins, LUse *use)
1.384 +{
1.385 + for (size_t i = 0; i < ins->numDefs(); i++) {
1.386 + if (ins->getDef(i)->policy() == LDefinition::MUST_REUSE_INPUT &&
1.387 + ins->getOperand(ins->getDef(i)->getReusedInput())->toUse() == use)
1.388 + {
1.389 + return true;
1.390 + }
1.391 + }
1.392 +
1.393 + for (size_t i = 0; i < ins->numTemps(); i++) {
1.394 + if (ins->getTemp(i)->policy() == LDefinition::MUST_REUSE_INPUT &&
1.395 + ins->getOperand(ins->getTemp(i)->getReusedInput())->toUse() == use)
1.396 + {
1.397 + return true;
1.398 + }
1.399 + }
1.400 +
1.401 + return false;
1.402 +}
1.403 +#endif
1.404 +
1.405 +/*
1.406 + * This function pre-allocates and initializes as much global state as possible
1.407 + * to avoid littering the algorithms with memory management cruft.
1.408 + */
1.409 +template <typename VREG, bool forLSRA>
1.410 +bool
1.411 +LiveRangeAllocator<VREG, forLSRA>::init()
1.412 +{
1.413 + if (!RegisterAllocator::init())
1.414 + return false;
1.415 +
1.416 + liveIn = mir->allocate<BitSet*>(graph.numBlockIds());
1.417 + if (!liveIn)
1.418 + return false;
1.419 +
1.420 + // Initialize fixed intervals.
1.421 + for (size_t i = 0; i < AnyRegister::Total; i++) {
1.422 + AnyRegister reg = AnyRegister::FromCode(i);
1.423 + LiveInterval *interval = LiveInterval::New(alloc(), 0);
1.424 + interval->setAllocation(LAllocation(reg));
1.425 + fixedIntervals[i] = interval;
1.426 + }
1.427 +
1.428 + fixedIntervalsUnion = LiveInterval::New(alloc(), 0);
1.429 +
1.430 + if (!vregs.init(mir, graph.numVirtualRegisters()))
1.431 + return false;
1.432 +
1.433 + // Build virtual register objects
1.434 + for (size_t i = 0; i < graph.numBlocks(); i++) {
1.435 + if (mir->shouldCancel("Create data structures (main loop)"))
1.436 + return false;
1.437 +
1.438 + LBlock *block = graph.getBlock(i);
1.439 + for (LInstructionIterator ins = block->begin(); ins != block->end(); ins++) {
1.440 + for (size_t j = 0; j < ins->numDefs(); j++) {
1.441 + LDefinition *def = ins->getDef(j);
1.442 + if (def->policy() != LDefinition::PASSTHROUGH) {
1.443 + if (!vregs[def].init(alloc(), block, *ins, def, /* isTemp */ false))
1.444 + return false;
1.445 + }
1.446 + }
1.447 +
1.448 + for (size_t j = 0; j < ins->numTemps(); j++) {
1.449 + LDefinition *def = ins->getTemp(j);
1.450 + if (def->isBogusTemp())
1.451 + continue;
1.452 + if (!vregs[def].init(alloc(), block, *ins, def, /* isTemp */ true))
1.453 + return false;
1.454 + }
1.455 + }
1.456 + for (size_t j = 0; j < block->numPhis(); j++) {
1.457 + LPhi *phi = block->getPhi(j);
1.458 + LDefinition *def = phi->getDef(0);
1.459 + if (!vregs[def].init(alloc(), block, phi, def, /* isTemp */ false))
1.460 + return false;
1.461 + }
1.462 + }
1.463 +
1.464 + return true;
1.465 +}
1.466 +
1.467 +static void
1.468 +AddRegisterToSafepoint(LSafepoint *safepoint, AnyRegister reg, const LDefinition &def)
1.469 +{
1.470 + safepoint->addLiveRegister(reg);
1.471 +
1.472 + JS_ASSERT(def.type() == LDefinition::GENERAL ||
1.473 + def.type() == LDefinition::INT32 ||
1.474 + def.type() == LDefinition::DOUBLE ||
1.475 + def.type() == LDefinition::FLOAT32 ||
1.476 + def.type() == LDefinition::OBJECT);
1.477 +
1.478 + if (def.type() == LDefinition::OBJECT)
1.479 + safepoint->addGcRegister(reg.gpr());
1.480 +}
1.481 +
1.482 +/*
1.483 + * This function builds up liveness intervals for all virtual registers
1.484 + * defined in the function. Additionally, it populates the liveIn array with
1.485 + * information about which registers are live at the beginning of a block, to
1.486 + * aid resolution and reification in a later phase.
1.487 + *
1.488 + * The algorithm is based on the one published in:
1.489 + *
1.490 + * Wimmer, Christian, and Michael Franz. "Linear Scan Register Allocation on
1.491 + * SSA Form." Proceedings of the International Symposium on Code Generation
1.492 + * and Optimization. Toronto, Ontario, Canada, ACM. 2010. 170-79. PDF.
1.493 + *
1.494 + * The algorithm operates on blocks ordered such that dominators of a block
1.495 + * are before the block itself, and such that all blocks of a loop are
1.496 + * contiguous. It proceeds backwards over the instructions in this order,
1.497 + * marking registers live at their uses, ending their live intervals at
1.498 + * definitions, and recording which registers are live at the top of every
1.499 + * block. To deal with loop backedges, variables live at the beginning of
1.500 + * a loop gain an interval covering the entire loop.
1.501 + */
1.502 +template <typename VREG, bool forLSRA>
1.503 +bool
1.504 +LiveRangeAllocator<VREG, forLSRA>::buildLivenessInfo()
1.505 +{
1.506 + if (!init())
1.507 + return false;
1.508 +
1.509 + Vector<MBasicBlock *, 1, SystemAllocPolicy> loopWorkList;
1.510 + BitSet *loopDone = BitSet::New(alloc(), graph.numBlockIds());
1.511 + if (!loopDone)
1.512 + return false;
1.513 +
1.514 + for (size_t i = graph.numBlocks(); i > 0; i--) {
1.515 + if (mir->shouldCancel("Build Liveness Info (main loop)"))
1.516 + return false;
1.517 +
1.518 + LBlock *block = graph.getBlock(i - 1);
1.519 + MBasicBlock *mblock = block->mir();
1.520 +
1.521 + BitSet *live = BitSet::New(alloc(), graph.numVirtualRegisters());
1.522 + if (!live)
1.523 + return false;
1.524 + liveIn[mblock->id()] = live;
1.525 +
1.526 + // Propagate liveIn from our successors to us
1.527 + for (size_t i = 0; i < mblock->lastIns()->numSuccessors(); i++) {
1.528 + MBasicBlock *successor = mblock->lastIns()->getSuccessor(i);
1.529 + // Skip backedges, as we fix them up at the loop header.
1.530 + if (mblock->id() < successor->id())
1.531 + live->insertAll(liveIn[successor->id()]);
1.532 + }
1.533 +
1.534 + // Add successor phis
1.535 + if (mblock->successorWithPhis()) {
1.536 + LBlock *phiSuccessor = mblock->successorWithPhis()->lir();
1.537 + for (unsigned int j = 0; j < phiSuccessor->numPhis(); j++) {
1.538 + LPhi *phi = phiSuccessor->getPhi(j);
1.539 + LAllocation *use = phi->getOperand(mblock->positionInPhiSuccessor());
1.540 + uint32_t reg = use->toUse()->virtualRegister();
1.541 + live->insert(reg);
1.542 + }
1.543 + }
1.544 +
1.545 + // Variables are assumed alive for the entire block, a define shortens
1.546 + // the interval to the point of definition.
1.547 + for (BitSet::Iterator liveRegId(*live); liveRegId; liveRegId++) {
1.548 + if (!vregs[*liveRegId].getInterval(0)->addRangeAtHead(inputOf(block->firstId()),
1.549 + outputOf(block->lastId()).next()))
1.550 + {
1.551 + return false;
1.552 + }
1.553 + }
1.554 +
1.555 + // Shorten the front end of live intervals for live variables to their
1.556 + // point of definition, if found.
1.557 + for (LInstructionReverseIterator ins = block->rbegin(); ins != block->rend(); ins++) {
1.558 + // Calls may clobber registers, so force a spill and reload around the callsite.
1.559 + if (ins->isCall()) {
1.560 + for (AnyRegisterIterator iter(allRegisters_); iter.more(); iter++) {
1.561 + if (forLSRA) {
1.562 + if (!addFixedRangeAtHead(*iter, inputOf(*ins), outputOf(*ins)))
1.563 + return false;
1.564 + } else {
1.565 + bool found = false;
1.566 + for (size_t i = 0; i < ins->numDefs(); i++) {
1.567 + if (ins->getDef(i)->isPreset() &&
1.568 + *ins->getDef(i)->output() == LAllocation(*iter)) {
1.569 + found = true;
1.570 + break;
1.571 + }
1.572 + }
1.573 + if (!found && !addFixedRangeAtHead(*iter, outputOf(*ins), outputOf(*ins).next()))
1.574 + return false;
1.575 + }
1.576 + }
1.577 + }
1.578 +
1.579 + for (size_t i = 0; i < ins->numDefs(); i++) {
1.580 + if (ins->getDef(i)->policy() != LDefinition::PASSTHROUGH) {
1.581 + LDefinition *def = ins->getDef(i);
1.582 +
1.583 + CodePosition from;
1.584 + if (def->policy() == LDefinition::PRESET && def->output()->isRegister() && forLSRA) {
1.585 + // The fixed range covers the current instruction so the
1.586 + // interval for the virtual register starts at the next
1.587 + // instruction. If the next instruction has a fixed use,
1.588 + // this can lead to unnecessary register moves. To avoid
1.589 + // special handling for this, assert the next instruction
1.590 + // has no fixed uses. defineFixed guarantees this by inserting
1.591 + // an LNop.
1.592 + JS_ASSERT(!NextInstructionHasFixedUses(block, *ins));
1.593 + AnyRegister reg = def->output()->toRegister();
1.594 + if (!addFixedRangeAtHead(reg, inputOf(*ins), outputOf(*ins).next()))
1.595 + return false;
1.596 + from = outputOf(*ins).next();
1.597 + } else {
1.598 + from = forLSRA ? inputOf(*ins) : outputOf(*ins);
1.599 + }
1.600 +
1.601 + if (def->policy() == LDefinition::MUST_REUSE_INPUT) {
1.602 + // MUST_REUSE_INPUT is implemented by allocating an output
1.603 + // register and moving the input to it. Register hints are
1.604 + // used to avoid unnecessary moves. We give the input an
1.605 + // LUse::ANY policy to avoid allocating a register for the
1.606 + // input.
1.607 + LUse *inputUse = ins->getOperand(def->getReusedInput())->toUse();
1.608 + JS_ASSERT(inputUse->policy() == LUse::REGISTER);
1.609 + JS_ASSERT(inputUse->usedAtStart());
1.610 + *inputUse = LUse(inputUse->virtualRegister(), LUse::ANY, /* usedAtStart = */ true);
1.611 + }
1.612 +
1.613 + LiveInterval *interval = vregs[def].getInterval(0);
1.614 + interval->setFrom(from);
1.615 +
1.616 + // Ensure that if there aren't any uses, there's at least
1.617 + // some interval for the output to go into.
1.618 + if (interval->numRanges() == 0) {
1.619 + if (!interval->addRangeAtHead(from, from.next()))
1.620 + return false;
1.621 + }
1.622 + live->remove(def->virtualRegister());
1.623 + }
1.624 + }
1.625 +
1.626 + for (size_t i = 0; i < ins->numTemps(); i++) {
1.627 + LDefinition *temp = ins->getTemp(i);
1.628 + if (temp->isBogusTemp())
1.629 + continue;
1.630 +
1.631 + if (forLSRA) {
1.632 + if (temp->policy() == LDefinition::PRESET) {
1.633 + if (ins->isCall())
1.634 + continue;
1.635 + AnyRegister reg = temp->output()->toRegister();
1.636 + if (!addFixedRangeAtHead(reg, inputOf(*ins), outputOf(*ins)))
1.637 + return false;
1.638 +
1.639 + // Fixed intervals are not added to safepoints, so do it
1.640 + // here.
1.641 + if (LSafepoint *safepoint = ins->safepoint())
1.642 + AddRegisterToSafepoint(safepoint, reg, *temp);
1.643 + } else {
1.644 + JS_ASSERT(!ins->isCall());
1.645 + if (!vregs[temp].getInterval(0)->addRangeAtHead(inputOf(*ins), outputOf(*ins)))
1.646 + return false;
1.647 + }
1.648 + } else {
1.649 + // Normally temps are considered to cover both the input
1.650 + // and output of the associated instruction. In some cases
1.651 + // though we want to use a fixed register as both an input
1.652 + // and clobbered register in the instruction, so watch for
1.653 + // this and shorten the temp to cover only the output.
1.654 + CodePosition from = inputOf(*ins);
1.655 + if (temp->policy() == LDefinition::PRESET) {
1.656 + AnyRegister reg = temp->output()->toRegister();
1.657 + for (LInstruction::InputIterator alloc(**ins); alloc.more(); alloc.next()) {
1.658 + if (alloc->isUse()) {
1.659 + LUse *use = alloc->toUse();
1.660 + if (use->isFixedRegister()) {
1.661 + if (GetFixedRegister(vregs[use].def(), use) == reg)
1.662 + from = outputOf(*ins);
1.663 + }
1.664 + }
1.665 + }
1.666 + }
1.667 +
1.668 + CodePosition to =
1.669 + ins->isCall() ? outputOf(*ins) : outputOf(*ins).next();
1.670 + if (!vregs[temp].getInterval(0)->addRangeAtHead(from, to))
1.671 + return false;
1.672 + }
1.673 + }
1.674 +
1.675 + DebugOnly<bool> hasUseRegister = false;
1.676 + DebugOnly<bool> hasUseRegisterAtStart = false;
1.677 +
1.678 + for (LInstruction::InputIterator inputAlloc(**ins); inputAlloc.more(); inputAlloc.next()) {
1.679 + if (inputAlloc->isUse()) {
1.680 + LUse *use = inputAlloc->toUse();
1.681 +
1.682 + // The first instruction, LLabel, has no uses.
1.683 + JS_ASSERT_IF(forLSRA, inputOf(*ins) > outputOf(block->firstId()));
1.684 +
1.685 + // Call uses should always be at-start or fixed, since the fixed intervals
1.686 + // use all registers.
1.687 + JS_ASSERT_IF(ins->isCall() && !inputAlloc.isSnapshotInput(),
1.688 + use->isFixedRegister() || use->usedAtStart());
1.689 +
1.690 +#ifdef DEBUG
1.691 + // Don't allow at-start call uses if there are temps of the same kind,
1.692 + // so that we don't assign the same register.
1.693 + if (ins->isCall() && use->usedAtStart()) {
1.694 + for (size_t i = 0; i < ins->numTemps(); i++)
1.695 + JS_ASSERT(vregs[ins->getTemp(i)].isFloatReg() != vregs[use].isFloatReg());
1.696 + }
1.697 +
1.698 + // If there are both useRegisterAtStart(x) and useRegister(y)
1.699 + // uses, we may assign the same register to both operands due to
1.700 + // interval splitting (bug 772830). Don't allow this for now.
1.701 + if (use->policy() == LUse::REGISTER) {
1.702 + if (use->usedAtStart()) {
1.703 + if (!IsInputReused(*ins, use))
1.704 + hasUseRegisterAtStart = true;
1.705 + } else {
1.706 + hasUseRegister = true;
1.707 + }
1.708 + }
1.709 +
1.710 + JS_ASSERT(!(hasUseRegister && hasUseRegisterAtStart));
1.711 +#endif
1.712 +
1.713 + // Don't treat RECOVERED_INPUT uses as keeping the vreg alive.
1.714 + if (use->policy() == LUse::RECOVERED_INPUT)
1.715 + continue;
1.716 +
1.717 + CodePosition to;
1.718 + if (forLSRA) {
1.719 + if (use->isFixedRegister()) {
1.720 + AnyRegister reg = GetFixedRegister(vregs[use].def(), use);
1.721 + if (!addFixedRangeAtHead(reg, inputOf(*ins), outputOf(*ins)))
1.722 + return false;
1.723 + to = inputOf(*ins);
1.724 +
1.725 + // Fixed intervals are not added to safepoints, so do it
1.726 + // here.
1.727 + LSafepoint *safepoint = ins->safepoint();
1.728 + if (!ins->isCall() && safepoint)
1.729 + AddRegisterToSafepoint(safepoint, reg, *vregs[use].def());
1.730 + } else {
1.731 + to = use->usedAtStart() ? inputOf(*ins) : outputOf(*ins);
1.732 + }
1.733 + } else {
1.734 + to = (use->usedAtStart() || ins->isCall())
1.735 + ? inputOf(*ins) : outputOf(*ins);
1.736 + if (use->isFixedRegister()) {
1.737 + LAllocation reg(AnyRegister::FromCode(use->registerCode()));
1.738 + for (size_t i = 0; i < ins->numDefs(); i++) {
1.739 + LDefinition *def = ins->getDef(i);
1.740 + if (def->policy() == LDefinition::PRESET && *def->output() == reg)
1.741 + to = inputOf(*ins);
1.742 + }
1.743 + }
1.744 + }
1.745 +
1.746 + LiveInterval *interval = vregs[use].getInterval(0);
1.747 + if (!interval->addRangeAtHead(inputOf(block->firstId()), forLSRA ? to : to.next()))
1.748 + return false;
1.749 + interval->addUse(new(alloc()) UsePosition(use, to));
1.750 +
1.751 + live->insert(use->virtualRegister());
1.752 + }
1.753 + }
1.754 + }
1.755 +
1.756 + // Phis have simultaneous assignment semantics at block begin, so at
1.757 + // the beginning of the block we can be sure that liveIn does not
1.758 + // contain any phi outputs.
1.759 + for (unsigned int i = 0; i < block->numPhis(); i++) {
1.760 + LDefinition *def = block->getPhi(i)->getDef(0);
1.761 + if (live->contains(def->virtualRegister())) {
1.762 + live->remove(def->virtualRegister());
1.763 + } else {
1.764 + // This is a dead phi, so add a dummy range over all phis. This
1.765 + // can go away if we have an earlier dead code elimination pass.
1.766 + if (!vregs[def].getInterval(0)->addRangeAtHead(inputOf(block->firstId()),
1.767 + outputOf(block->firstId())))
1.768 + {
1.769 + return false;
1.770 + }
1.771 + }
1.772 + }
1.773 +
1.774 + if (mblock->isLoopHeader()) {
1.775 + // A divergence from the published algorithm is required here, as
1.776 + // our block order does not guarantee that blocks of a loop are
1.777 + // contiguous. As a result, a single live interval spanning the
1.778 + // loop is not possible. Additionally, we require liveIn in a later
1.779 + // pass for resolution, so that must also be fixed up here.
1.780 + MBasicBlock *loopBlock = mblock->backedge();
1.781 + while (true) {
1.782 + // Blocks must already have been visited to have a liveIn set.
1.783 + JS_ASSERT(loopBlock->id() >= mblock->id());
1.784 +
1.785 + // Add an interval for this entire loop block
1.786 + CodePosition from = inputOf(loopBlock->lir()->firstId());
1.787 + CodePosition to = outputOf(loopBlock->lir()->lastId()).next();
1.788 +
1.789 + for (BitSet::Iterator liveRegId(*live); liveRegId; liveRegId++) {
1.790 + if (!vregs[*liveRegId].getInterval(0)->addRange(from, to))
1.791 + return false;
1.792 + }
1.793 +
1.794 + // Fix up the liveIn set to account for the new interval
1.795 + liveIn[loopBlock->id()]->insertAll(live);
1.796 +
1.797 + // Make sure we don't visit this node again
1.798 + loopDone->insert(loopBlock->id());
1.799 +
1.800 + // If this is the loop header, any predecessors are either the
1.801 + // backedge or out of the loop, so skip any predecessors of
1.802 + // this block
1.803 + if (loopBlock != mblock) {
1.804 + for (size_t i = 0; i < loopBlock->numPredecessors(); i++) {
1.805 + MBasicBlock *pred = loopBlock->getPredecessor(i);
1.806 + if (loopDone->contains(pred->id()))
1.807 + continue;
1.808 + if (!loopWorkList.append(pred))
1.809 + return false;
1.810 + }
1.811 + }
1.812 +
1.813 + // Terminate loop if out of work.
1.814 + if (loopWorkList.empty())
1.815 + break;
1.816 +
1.817 + // Grab the next block off the work list, skipping any OSR block.
1.818 + while (!loopWorkList.empty()) {
1.819 + loopBlock = loopWorkList.popCopy();
1.820 + if (loopBlock->lir() != graph.osrBlock())
1.821 + break;
1.822 + }
1.823 +
1.824 + // If end is reached without finding a non-OSR block, then no more work items were found.
1.825 + if (loopBlock->lir() == graph.osrBlock()) {
1.826 + JS_ASSERT(loopWorkList.empty());
1.827 + break;
1.828 + }
1.829 + }
1.830 +
1.831 + // Clear the done set for other loops
1.832 + loopDone->clear();
1.833 + }
1.834 +
1.835 + JS_ASSERT_IF(!mblock->numPredecessors(), live->empty());
1.836 + }
1.837 +
1.838 + validateVirtualRegisters();
1.839 +
1.840 + // If the script has an infinite loop, there may be no MReturn and therefore
1.841 + // no fixed intervals. Add a small range to fixedIntervalsUnion so that the
1.842 + // rest of the allocator can assume it has at least one range.
1.843 + if (fixedIntervalsUnion->numRanges() == 0) {
1.844 + if (!fixedIntervalsUnion->addRangeAtHead(CodePosition(0, CodePosition::INPUT),
1.845 + CodePosition(0, CodePosition::OUTPUT)))
1.846 + {
1.847 + return false;
1.848 + }
1.849 + }
1.850 +
1.851 + return true;
1.852 +}
1.853 +
1.854 +#ifdef DEBUG
1.855 +
1.856 +void
1.857 +LiveInterval::validateRanges()
1.858 +{
1.859 + Range *prev = nullptr;
1.860 +
1.861 + for (size_t i = ranges_.length() - 1; i < ranges_.length(); i--) {
1.862 + Range *range = &ranges_[i];
1.863 +
1.864 + JS_ASSERT(range->from < range->to);
1.865 + JS_ASSERT_IF(prev, prev->to <= range->from);
1.866 + prev = range;
1.867 + }
1.868 +}
1.869 +
1.870 +#endif // DEBUG
1.871 +
1.872 +const char *
1.873 +LiveInterval::rangesToString() const
1.874 +{
1.875 +#ifdef DEBUG
1.876 + if (!numRanges())
1.877 + return " empty";
1.878 +
1.879 + // Not reentrant!
1.880 + static char buf[1000];
1.881 +
1.882 + char *cursor = buf;
1.883 + char *end = cursor + sizeof(buf);
1.884 +
1.885 + for (size_t i = 0; i < numRanges(); i++) {
1.886 + const LiveInterval::Range *range = getRange(i);
1.887 + int n = JS_snprintf(cursor, end - cursor, " [%u,%u>", range->from.pos(), range->to.pos());
1.888 + if (n < 0)
1.889 + return " ???";
1.890 + cursor += n;
1.891 + }
1.892 +
1.893 + return buf;
1.894 +#else
1.895 + return " ???";
1.896 +#endif
1.897 +}
1.898 +
1.899 +void
1.900 +LiveInterval::dump()
1.901 +{
1.902 + fprintf(stderr, "v%u: index=%u allocation=%s %s\n",
1.903 + vreg(), index(), getAllocation()->toString(), rangesToString());
1.904 +}
