The Tor Browser: comparison js/src/jit/MoveResolver.cpp

--1:000000000000
+:b7070a32b70b
+/* -*- 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"
+using namespace js;
+using namespace js::jit;
+MoveResolver::MoveResolver()
+: hasCycles_(false)
+{
+}
+void
+MoveResolver::resetState()
+{
+hasCycles_ = false;
+}
+bool
+MoveResolver::addMove(const MoveOperand &from, const MoveOperand &to, MoveOp::Type type)
+{
+// Assert that we're not doing no-op moves.
+JS_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() == 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;
+}
+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. The output is not entirely optimal for cases
+// where a source has multiple destinations, i.e.:
+//      [stack0] -> A
+//      [stack0] -> B
+//
+// These moves may not occur next to each other in the list, making it
+// harder for the emitter to optimize memory to memory traffic. However, we
+// expect duplicate sources to be rare in greedy allocation, and indicative
+// of an error in LSRA.
+//
+// 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) {
+if (blocking->to() == pm->from()) {
+// 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).
+pm->setCycleEnd();
+blocking->setCycleBegin(pm->type());
+hasCycles_ = true;
+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 (!orderedMoves_.append(*done))
+return false;
+movePool_.free(done);
+}
+}
+}
+return true;
+}

The Tor Browser / file comparison

comparison: js/src/jit/MoveResolver.cpp

js/src/jit/MoveResolver.cpp