michael@0: /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
michael@0:  * vim: set ts=8 sts=4 et sw=4 tw=99:
michael@0:  * This Source Code Form is subject to the terms of the Mozilla Public
michael@0:  * License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0:  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
michael@0: 
michael@0: #include "jit/MoveResolver.h"
michael@0: 
michael@0: using namespace js;
michael@0: using namespace js::jit;
michael@0: 
michael@0: MoveResolver::MoveResolver()
michael@0:   : hasCycles_(false)
michael@0: {
michael@0: }
michael@0: 
michael@0: void
michael@0: MoveResolver::resetState()
michael@0: {
michael@0:     hasCycles_ = false;
michael@0: }
michael@0: 
michael@0: bool
michael@0: MoveResolver::addMove(const MoveOperand &from, const MoveOperand &to, MoveOp::Type type)
michael@0: {
michael@0:     // Assert that we're not doing no-op moves.
michael@0:     JS_ASSERT(!(from == to));
michael@0:     PendingMove *pm = movePool_.allocate();
michael@0:     if (!pm)
michael@0:         return false;
michael@0:     new (pm) PendingMove(from, to, type);
michael@0:     pending_.pushBack(pm);
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: // Given move (A -> B), this function attempts to find any move (B -> *) in the
michael@0: // pending move list, and returns the first one.
michael@0: MoveResolver::PendingMove *
michael@0: MoveResolver::findBlockingMove(const PendingMove *last)
michael@0: {
michael@0:     for (PendingMoveIterator iter = pending_.begin(); iter != pending_.end(); iter++) {
michael@0:         PendingMove *other = *iter;
michael@0: 
michael@0:         if (other->from() == last->to()) {
michael@0:             // We now have pairs in the form (A -> X) (X -> y). The second pair
michael@0:             // blocks the move in the first pair, so return it.
michael@0:             return other;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     // No blocking moves found.
michael@0:     return nullptr;
michael@0: }
michael@0: 
michael@0: bool
michael@0: MoveResolver::resolve()
michael@0: {
michael@0:     resetState();
michael@0:     orderedMoves_.clear();
michael@0: 
michael@0:     InlineList<PendingMove> stack;
michael@0: 
michael@0:     // This is a depth-first-search without recursion, which tries to find
michael@0:     // cycles in a list of moves. The output is not entirely optimal for cases
michael@0:     // where a source has multiple destinations, i.e.:
michael@0:     //      [stack0] -> A
michael@0:     //      [stack0] -> B
michael@0:     //
michael@0:     // These moves may not occur next to each other in the list, making it
michael@0:     // harder for the emitter to optimize memory to memory traffic. However, we
michael@0:     // expect duplicate sources to be rare in greedy allocation, and indicative
michael@0:     // of an error in LSRA.
michael@0:     //
michael@0:     // Algorithm.
michael@0:     //
michael@0:     // S = Traversal stack.
michael@0:     // P = Pending move list.
michael@0:     // O = Ordered list of moves.
michael@0:     //
michael@0:     // As long as there are pending moves in P:
michael@0:     //      Let |root| be any pending move removed from P
michael@0:     //      Add |root| to the traversal stack.
michael@0:     //      As long as S is not empty:
michael@0:     //          Let |L| be the most recent move added to S.
michael@0:     //
michael@0:     //          Find any pending move M whose source is L's destination, thus
michael@0:     //          preventing L's move until M has completed.
michael@0:     //
michael@0:     //          If a move M was found,
michael@0:     //              Remove M from the pending list.
michael@0:     //              If M's destination is |root|,
michael@0:     //                  Annotate M and |root| as cycles.
michael@0:     //                  Add M to S.
michael@0:     //                  do not Add M to O, since M may have other conflictors in P that have not yet been processed.
michael@0:     //              Otherwise,
michael@0:     //                  Add M to S.
michael@0:     //         Otherwise,
michael@0:     //              Remove L from S.
michael@0:     //              Add L to O.
michael@0:     //
michael@0:     while (!pending_.empty()) {
michael@0:         PendingMove *pm = pending_.popBack();
michael@0: 
michael@0:         // Add this pending move to the cycle detection stack.
michael@0:         stack.pushBack(pm);
michael@0: 
michael@0:         while (!stack.empty()) {
michael@0:             PendingMove *blocking = findBlockingMove(stack.peekBack());
michael@0: 
michael@0:             if (blocking) {
michael@0:                 if (blocking->to() == pm->from()) {
michael@0:                     // We annotate cycles at each move in the cycle, and
michael@0:                     // assert that we do not find two cycles in one move chain
michael@0:                     // traversal (which would indicate two moves to the same
michael@0:                     // destination).
michael@0:                     pm->setCycleEnd();
michael@0:                     blocking->setCycleBegin(pm->type());
michael@0:                     hasCycles_ = true;
michael@0:                     pending_.remove(blocking);
michael@0:                     stack.pushBack(blocking);
michael@0:                 } else {
michael@0:                     // This is a new link in the move chain, so keep
michael@0:                     // searching for a cycle.
michael@0:                     pending_.remove(blocking);
michael@0:                     stack.pushBack(blocking);
michael@0:                 }
michael@0:             } else {
michael@0:                 // Otherwise, pop the last move on the search stack because it's
michael@0:                 // complete and not participating in a cycle. The resulting
michael@0:                 // move can safely be added to the ordered move list.
michael@0:                 PendingMove *done = stack.popBack();
michael@0:                 if (!orderedMoves_.append(*done))
michael@0:                     return false;
michael@0:                 movePool_.free(done);
michael@0:             }
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     return true;
michael@0: }