The Tor Browser: js/src/jit/MoveResolver.cpp@6474c204b198 (annotated)

js/src/jit/MoveResolver.cpp@6474c204b198 (annotated)

js/src/jit/MoveResolver.cpp

Wed, 31 Dec 2014 06:09:35 +0100

author: Michael Schloh von Bennewitz <michael@schloh.com>
date: Wed, 31 Dec 2014 06:09:35 +0100
changeset 0: 6474c204b198
permissions: -rw-r--r--

Cloned upstream origin tor-browser at tor-browser-31.3.0esr-4.5-1-build1
revision ID fc1c9ff7c1b2defdbc039f12214767608f46423f for hacking purpose.

 /* -*- 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 / annotate

js/src/jit/MoveResolver.cpp@6474c204b198 (annotated)

js/src/jit/MoveResolver.cpp