/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
* vim: set ts=8 sts=2 et sw=2 tw=80:
* 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/MoveResolver.h"
#include "mozilla/ScopeExit.h"
#include "jit/MacroAssembler.h"
#include "jit/RegisterSets.h"
using namespace js;
using namespace js::jit;
MoveOperand::MoveOperand(MacroAssembler& masm,
const ABIArg& arg) : disp_(0) {
switch (arg.kind()) {
case ABIArg::GPR:
kind_ = Kind::Reg;
code_ = arg.gpr().code();
break;
#ifdef JS_CODEGEN_REGISTER_PAIR
case ABIArg::GPR_PAIR:
kind_ = Kind::RegPair;
code_ = arg.evenGpr().code();
MOZ_ASSERT(code_ % 2 == 0);
MOZ_ASSERT(code_ + 1 == arg.oddGpr().code());
break;
#endif
case ABIArg::FPU:
kind_ = Kind::FloatReg;
code_ = arg.fpu().code();
break;
case ABIArg::Stack:
kind_ = Kind::Memory;
if (IsHiddenSP(masm.getStackPointer())) {
MOZ_CRASH(
"Hidden SP cannot be represented as register code on this "
"platform");
}
else {
code_ = AsRegister(masm.getStackPointer()).code();
}
disp_ = arg.offsetFromArgBase();
break;
case ABIArg::Uninitialized:
MOZ_CRASH(
"Uninitialized ABIArg kind");
}
}
MoveResolver::MoveResolver() : numCycles_(0), curCycles_(0) {}
void MoveResolver::resetState() {
numCycles_ = 0;
curCycles_ = 0;
}
bool MoveResolver::addMove(
const MoveOperand& from,
const MoveOperand& to,
MoveOp::Type type) {
// Assert that we're not doing no-op moves.
MOZ_ASSERT(!(from == to));
PendingMove* pm = movePool_.allocate(from, to, type);
if (!pm) {
return false;
}
pending_.pushBack(pm);
return true;
}
// Given move (A -> B), this function attempts to find any move (B -> *) in the
// pending move list, and returns the first one.
MoveResolver::PendingMove* MoveResolver::findBlockingMove(
const PendingMove* last) {
for (PendingMoveIterator iter = pending_.begin(); iter != pending_.end();
iter++) {
PendingMove* other = *iter;
if (other->from().aliases(last->to())) {
// We now have pairs in the form (A -> X) (X -> y). The second pair
// blocks the move in the first pair, so return it.
return other;
}
}
// No blocking moves found.
return nullptr;
}
// Given move (A -> B), this function attempts to find any move (B -> *) in the
// move list iterator, and returns the first one.
// N.B. It is unclear if a single move can complete more than one cycle, so to
// be conservative, this function operates on iterators, so the caller can
// process all instructions that start a cycle.
MoveResolver::PendingMove* MoveResolver::findCycledMove(
PendingMoveIterator* iter, PendingMoveIterator end,
const PendingMove* last) {
for (; *iter != end; (*iter)++) {
PendingMove* other = **iter;
if (other->from().aliases(last->to())) {
// We now have pairs in the form (A -> X) (X -> y). The second pair
// blocks the move in the first pair, so return it.
(*iter)++;
return other;
}
}
// No blocking moves found.
return nullptr;
}
#ifdef JS_CODEGEN_ARM
static inline bool MoveIsDouble(
const MoveOperand& move) {
if (!move.isFloatReg()) {
return false;
}
return move.floatReg().isDouble();
}
#endif
#ifdef JS_CODEGEN_ARM
static inline bool MoveIsSingle(
const MoveOperand& move) {
if (!move.isFloatReg()) {
return false;
}
return move.floatReg().isSingle();
}
#endif
#ifdef JS_CODEGEN_ARM
bool MoveResolver::isDoubleAliasedAsSingle(
const MoveOperand& move) {
if (!MoveIsDouble(move)) {
return false;
}
for (
auto iter = pending_.begin(); iter != pending_.end(); ++iter) {
PendingMove* other = *iter;
if (other->from().aliases(move) && MoveIsSingle(other->from())) {
return true;
}
if (other->to().aliases(move) && MoveIsSingle(other->to())) {
return true;
}
}
return false;
}
#endif
#ifdef JS_CODEGEN_ARM
static MoveOperand SplitIntoLowerHalf(
const MoveOperand& move) {
if (MoveIsDouble(move)) {
FloatRegister lowerSingle = move.floatReg().asSingle();
return MoveOperand(lowerSingle);
}
MOZ_ASSERT(move.isMemoryOrEffectiveAddress());
return move;
}
#endif
#ifdef JS_CODEGEN_ARM
static MoveOperand SplitIntoUpperHalf(
const MoveOperand& move) {
if (MoveIsDouble(move)) {
FloatRegister lowerSingle = move.floatReg().asSingle();
FloatRegister upperSingle =
VFPRegister(lowerSingle.code() + 1, VFPRegister::Single);
return MoveOperand(upperSingle);
}
MOZ_ASSERT(move.isMemoryOrEffectiveAddress());
return MoveOperand(move.base(), move.disp() +
sizeof(
float));
}
#endif
// Resolves the pending_ list to a list in orderedMoves_.
bool MoveResolver::resolve() {
resetState();
orderedMoves_.clear();
// Upon return from this function, the pending_ list must be cleared.
auto clearPending = mozilla::MakeScopeExit([
this]() { pending_.clear(); });
#ifdef JS_CODEGEN_ARM
// Some of ARM's double registers alias two of its single registers,
// but the algorithm below assumes that every register can participate
// in at most one cycle. To satisfy the algorithm, any double registers
// that may conflict are split into their single-register halves.
//
// This logic is only applicable because ARM only uses registers d0-d15,
// all of which alias s0-s31. Double registers d16-d31 are unused.
// Therefore there is never a double move that cannot be split.
// If this changes in the future, the algorithm will have to be fixed.
bool splitDoubles =
false;
for (
auto iter = pending_.begin(); iter != pending_.end(); ++iter) {
PendingMove* pm = *iter;
if (isDoubleAliasedAsSingle(pm->from()) ||
isDoubleAliasedAsSingle(pm->to())) {
splitDoubles =
true;
break;
}
}
if (splitDoubles) {
for (
auto iter = pending_.begin(); iter != pending_.end(); ++iter) {
PendingMove* pm = *iter;
if (!MoveIsDouble(pm->from()) && !MoveIsDouble(pm->to())) {
continue;
}
MoveOperand fromLower = SplitIntoLowerHalf(pm->from());
MoveOperand toLower = SplitIntoLowerHalf(pm->to());
PendingMove* lower =
movePool_.allocate(fromLower, toLower, MoveOp::FLOAT32);
if (!lower) {
return false;
}
// Insert the new node before the current position to not affect
// iteration.
pending_.insertBefore(pm, lower);
// Overwrite pm in place for the upper move. Iteration proceeds as normal.
MoveOperand fromUpper = SplitIntoUpperHalf(pm->from());
MoveOperand toUpper = SplitIntoUpperHalf(pm->to());
pm->overwrite(fromUpper, toUpper, MoveOp::FLOAT32);
}
}
#endif
InlineList<PendingMove> stack;
// This is a depth-first-search without recursion, which tries to find
// cycles in a list of moves.
//
// Algorithm.
//
// S = Traversal stack.
// P = Pending move list.
// O = Ordered list of moves.
//
// As long as there are pending moves in P:
// Let |root| be any pending move removed from P
// Add |root| to the traversal stack.
// As long as S is not empty:
// Let |L| be the most recent move added to S.
//
// Find any pending move M whose source is L's destination, thus
// preventing L's move until M has completed.
//
// If a move M was found,
// Remove M from the pending list.
// If M's destination is |root|,
// Annotate M and |root| as cycles.
// Add M to S.
// do not Add M to O, since M may have other conflictors in P
// that have not yet been processed.
// Otherwise,
// Add M to S.
// Otherwise,
// Remove L from S.
// Add L to O.
//
while (!pending_.empty()) {
PendingMove* pm = pending_.popBack();
// Add this pending move to the cycle detection stack.
stack.pushBack(pm);
while (!stack.empty()) {
PendingMove* blocking = findBlockingMove(stack.peekBack());
if (blocking) {
PendingMoveIterator stackiter = stack.begin();
PendingMove* cycled = findCycledMove(&stackiter, stack.end(), blocking);
if (cycled) {
// Find the cycle's start.
// We annotate cycles at each move in the cycle, and
// assert that we do not find two cycles in one move chain
// traversal (which would indicate two moves to the same
// destination).
// Since there can be more than one cycle, find them all.
do {
cycled->setCycleEnd(curCycles_);
cycled = findCycledMove(&stackiter, stack.end(), blocking);
}
while (cycled);
blocking->setCycleBegin(pm->type(), curCycles_);
curCycles_++;
pending_.remove(blocking);
stack.pushBack(blocking);
}
else {
// This is a new link in the move chain, so keep
// searching for a cycle.
pending_.remove(blocking);
stack.pushBack(blocking);
}
}
else {
// Otherwise, pop the last move on the search stack because it's
// complete and not participating in a cycle. The resulting
// move can safely be added to the ordered move list.
PendingMove* done = stack.popBack();
if (!addOrderedMove(*done)) {
return false;
}
movePool_.free(done);
}
}
// If the current queue is empty, it is certain that there are
// all previous cycles cannot conflict with future cycles,
// so re-set the counter of pending cycles, while keeping a high-water mark.
if (numCycles_ < curCycles_) {
numCycles_ = curCycles_;
}
curCycles_ = 0;
}
return true;
}
bool MoveResolver::addOrderedMove(
const MoveOp& move) {
// Sometimes the register allocator generates move groups where multiple
// moves have the same source. Try to optimize these cases when the source
// is in memory and the target of one of the moves is in a register.
MOZ_ASSERT(!move.from().aliases(move.to()));
if (!move.from().isMemory() || move.isCycleBegin() || move.isCycleEnd()) {
return orderedMoves_.append(move);
}
// Look for an earlier move with the same source, where no intervening move
// touches either the source or destination of the new move.
for (
int i = orderedMoves_.length() - 1; i >= 0; i--) {
const MoveOp& existing = orderedMoves_[i];
if (existing.from() == move.from() && !existing.to().aliases(move.to()) &&
existing.type() == move.type() && !existing.isCycleBegin() &&
!existing.isCycleEnd()) {
MoveOp* after = orderedMoves_.begin() + i + 1;
if (existing.to().isGeneralReg() || existing.to().isFloatReg()) {
MoveOp nmove(existing.to(), move.to(), move.type());
return orderedMoves_.insert(after, nmove);
}
else if (move.to().isGeneralReg() || move.to().isFloatReg()) {
MoveOp nmove(move.to(), existing.to(), move.type());
orderedMoves_[i] = move;
return orderedMoves_.insert(after, nmove);
}
}
if (existing.aliases(move)) {
break;
}
}
return orderedMoves_.append(move);
}
void MoveResolver::reorderMove(size_t from, size_t to) {
MOZ_ASSERT(from != to);
MoveOp op = orderedMoves_[from];
if (from < to) {
for (size_t i = from; i < to; i++) {
orderedMoves_[i] = orderedMoves_[i + 1];
}
}
else {
for (size_t i = from; i > to; i--) {
orderedMoves_[i] = orderedMoves_[i - 1];
}
}
orderedMoves_[to] = op;
}
void MoveResolver::sortMemoryToMemoryMoves() {
// Try to reorder memory->memory moves so that they are executed right
// before a move that clobbers some register. This will allow the move
// emitter to use that clobbered register as a scratch register for the
// memory->memory move, if necessary.
for (size_t i = 0; i < orderedMoves_.length(); i++) {
const MoveOp& base = orderedMoves_[i];
if (!base.from().isMemory() || !base.to().isMemory()) {
continue;
}
if (base.type() != MoveOp::GENERAL && base.type() != MoveOp::INT32) {
continue;
}
// Look for an earlier move clobbering a register.
bool found =
false;
for (
int j = i - 1; j >= 0; j--) {
const MoveOp& previous = orderedMoves_[j];
if (previous.aliases(base) || previous.isCycleBegin() ||
previous.isCycleEnd()) {
break;
}
if (previous.to().isGeneralReg()) {
reorderMove(i, j);
found =
true;
break;
}
}
if (found) {
continue;
}
// Look for a later move clobbering a register.
if (i + 1 < orderedMoves_.length()) {
bool found =
false, skippedRegisterUse =
false;
for (size_t j = i + 1; j < orderedMoves_.length(); j++) {
const MoveOp& later = orderedMoves_[j];
if (later.aliases(base) || later.isCycleBegin() || later.isCycleEnd()) {
break;
}
if (later.to().isGeneralReg()) {
if (skippedRegisterUse) {
reorderMove(i, j);
found =
true;
}
else {
// There is no move that uses a register between the
// original memory->memory move and this move that
// clobbers a register. The move should already be able
// to use a scratch register, so don't shift anything
// around.
}
break;
}
if (later.from().isGeneralReg()) {
skippedRegisterUse =
true;
}
}
if (found) {
// Redo the search for memory->memory moves at the current
// index, so we don't skip the move just shifted back.
i--;
}
}
}
}
