Adding upstream version 110.0.1.upstream/110.0.1upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 443 insertions, 0 deletions

diff --git a/js/src/jit/MoveResolver.cpp b/js/src/jit/MoveResolver.cpp
new file mode 100644
index 0000000000..2d47b32c35
--- /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_ = 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;
+      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--;
+      }
+    }
+  }
+}