1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/js/src/jit/MoveResolver.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,140 @@
1.4 +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
1.5 + * vim: set ts=8 sts=4 et sw=4 tw=99:
1.6 + * This Source Code Form is subject to the terms of the Mozilla Public
1.7 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.8 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.9 +
1.10 +#include "jit/MoveResolver.h"
1.11 +
1.12 +using namespace js;
1.13 +using namespace js::jit;
1.14 +
1.15 +MoveResolver::MoveResolver()
1.16 + : hasCycles_(false)
1.17 +{
1.18 +}
1.19 +
1.20 +void
1.21 +MoveResolver::resetState()
1.22 +{
1.23 + hasCycles_ = false;
1.24 +}
1.25 +
1.26 +bool
1.27 +MoveResolver::addMove(const MoveOperand &from, const MoveOperand &to, MoveOp::Type type)
1.28 +{
1.29 + // Assert that we're not doing no-op moves.
1.30 + JS_ASSERT(!(from == to));
1.31 + PendingMove *pm = movePool_.allocate();
1.32 + if (!pm)
1.33 + return false;
1.34 + new (pm) PendingMove(from, to, type);
1.35 + pending_.pushBack(pm);
1.36 + return true;
1.37 +}
1.38 +
1.39 +// Given move (A -> B), this function attempts to find any move (B -> *) in the
1.40 +// pending move list, and returns the first one.
1.41 +MoveResolver::PendingMove *
1.42 +MoveResolver::findBlockingMove(const PendingMove *last)
1.43 +{
1.44 + for (PendingMoveIterator iter = pending_.begin(); iter != pending_.end(); iter++) {
1.45 + PendingMove *other = *iter;
1.46 +
1.47 + if (other->from() == last->to()) {
1.48 + // We now have pairs in the form (A -> X) (X -> y). The second pair
1.49 + // blocks the move in the first pair, so return it.
1.50 + return other;
1.51 + }
1.52 + }
1.53 +
1.54 + // No blocking moves found.
1.55 + return nullptr;
1.56 +}
1.57 +
1.58 +bool
1.59 +MoveResolver::resolve()
1.60 +{
1.61 + resetState();
1.62 + orderedMoves_.clear();
1.63 +
1.64 + InlineList<PendingMove> stack;
1.65 +
1.66 + // This is a depth-first-search without recursion, which tries to find
1.67 + // cycles in a list of moves. The output is not entirely optimal for cases
1.68 + // where a source has multiple destinations, i.e.:
1.69 + // [stack0] -> A
1.70 + // [stack0] -> B
1.71 + //
1.72 + // These moves may not occur next to each other in the list, making it
1.73 + // harder for the emitter to optimize memory to memory traffic. However, we
1.74 + // expect duplicate sources to be rare in greedy allocation, and indicative
1.75 + // of an error in LSRA.
1.76 + //
1.77 + // Algorithm.
1.78 + //
1.79 + // S = Traversal stack.
1.80 + // P = Pending move list.
1.81 + // O = Ordered list of moves.
1.82 + //
1.83 + // As long as there are pending moves in P:
1.84 + // Let |root| be any pending move removed from P
1.85 + // Add |root| to the traversal stack.
1.86 + // As long as S is not empty:
1.87 + // Let |L| be the most recent move added to S.
1.88 + //
1.89 + // Find any pending move M whose source is L's destination, thus
1.90 + // preventing L's move until M has completed.
1.91 + //
1.92 + // If a move M was found,
1.93 + // Remove M from the pending list.
1.94 + // If M's destination is |root|,
1.95 + // Annotate M and |root| as cycles.
1.96 + // Add M to S.
1.97 + // do not Add M to O, since M may have other conflictors in P that have not yet been processed.
1.98 + // Otherwise,
1.99 + // Add M to S.
1.100 + // Otherwise,
1.101 + // Remove L from S.
1.102 + // Add L to O.
1.103 + //
1.104 + while (!pending_.empty()) {
1.105 + PendingMove *pm = pending_.popBack();
1.106 +
1.107 + // Add this pending move to the cycle detection stack.
1.108 + stack.pushBack(pm);
1.109 +
1.110 + while (!stack.empty()) {
1.111 + PendingMove *blocking = findBlockingMove(stack.peekBack());
1.112 +
1.113 + if (blocking) {
1.114 + if (blocking->to() == pm->from()) {
1.115 + // We annotate cycles at each move in the cycle, and
1.116 + // assert that we do not find two cycles in one move chain
1.117 + // traversal (which would indicate two moves to the same
1.118 + // destination).
1.119 + pm->setCycleEnd();
1.120 + blocking->setCycleBegin(pm->type());
1.121 + hasCycles_ = true;
1.122 + pending_.remove(blocking);
1.123 + stack.pushBack(blocking);
1.124 + } else {
1.125 + // This is a new link in the move chain, so keep
1.126 + // searching for a cycle.
1.127 + pending_.remove(blocking);
1.128 + stack.pushBack(blocking);
1.129 + }
1.130 + } else {
1.131 + // Otherwise, pop the last move on the search stack because it's
1.132 + // complete and not participating in a cycle. The resulting
1.133 + // move can safely be added to the ordered move list.
1.134 + PendingMove *done = stack.popBack();
1.135 + if (!orderedMoves_.append(*done))
1.136 + return false;
1.137 + movePool_.free(done);
1.138 + }
1.139 + }
1.140 + }
1.141 +
1.142 + return true;
1.143 +}
