Add m-esr52 at 52.6.0

1 files changed, 321 insertions, 0 deletions

diff --git a/js/src/jit/MoveResolver.cpp b/js/src/jit/MoveResolver.cpp
new file mode 100644
index 000000000..5fd6c7bd5
--- /dev/null
+++ b/js/src/jit/MoveResolver.cpp
@@ -0,0 +1,321 @@
+/* -*- 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/MoveResolver.h"
+
+#include "mozilla/Attributes.h"
+
+#include "jit/MacroAssembler.h"
+#include "jit/RegisterSets.h"
+
+using namespace js;
+using namespace js::jit;
+
+MoveOperand::MoveOperand(MacroAssembler& masm, const ABIArg& arg)
+{
+    switch (arg.kind()) {
+      case ABIArg::GPR:
+        kind_ = REG;
+        code_ = arg.gpr().code();
+        break;
+#ifdef JS_CODEGEN_REGISTER_PAIR
+      case ABIArg::GPR_PAIR:
+        kind_ = REG_PAIR;
+        code_ = arg.evenGpr().code();
+        MOZ_ASSERT(code_ % 2 == 0);
+        MOZ_ASSERT(code_ + 1 == arg.oddGpr().code());
+        break;
+#endif
+      case ABIArg::FPU:
+        kind_ = FLOAT_REG;
+        code_ = arg.fpu().code();
+        break;
+      case ABIArg::Stack:
+        kind_ = MEMORY;
+        code_ = masm.getStackPointer().code();
+        disp_ = arg.offsetFromArgBase();
+        break;
+    }
+}
+
+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();
+    if (!pm)
+        return false;
+    new (pm) PendingMove(from, to, type);
+    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;
+}
+
+bool
+MoveResolver::resolve()
+{
+    resetState();
+    orderedMoves_.clear();
+
+    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--;
+            }
+        }
+    }
+}