diff -r 000000000000 -r 6474c204b198 js/src/jit/MoveResolver.cpp
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/js/src/jit/MoveResolver.cpp	Wed Dec 31 06:09:35 2014 +0100
@@ -0,0 +1,140 @@
+/* -*- 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;
+}