From 26a029d407be480d791972afb5975cf62c9360a6 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Fri, 19 Apr 2024 02:47:55 +0200 Subject: Adding upstream version 124.0.1. Signed-off-by: Daniel Baumann --- js/src/jit/MoveResolver.cpp | 443 ++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 443 insertions(+) create mode 100644 js/src/jit/MoveResolver.cpp (limited to 'js/src/jit/MoveResolver.cpp') diff --git a/js/src/jit/MoveResolver.cpp b/js/src/jit/MoveResolver.cpp new file mode 100644 index 0000000000..4a9edd8e74 --- /dev/null +++ b/js/src/jit/MoveResolver.cpp @@ -0,0 +1,443 @@ +/* -*- 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 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--; + } + } + } +} -- cgit v1.2.3