The Tor Browser / file comparison
comparison: js/src/jit/MoveResolver.cpp
js/src/jit/MoveResolver.cpp
- changeset 0
- 6474c204b198
equal
deleted
inserted
replaced
| -1:000000000000 | 0:b7070a32b70b |
|---|---|
| 1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- | |
| 2 * vim: set ts=8 sts=4 et sw=4 tw=99: | |
| 3 * This Source Code Form is subject to the terms of the Mozilla Public | |
| 4 * License, v. 2.0. If a copy of the MPL was not distributed with this | |
| 5 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ | |
| 6 | |
| 7 #include "jit/MoveResolver.h" | |
| 8 | |
| 9 using namespace js; | |
| 10 using namespace js::jit; | |
| 11 | |
| 12 MoveResolver::MoveResolver() | |
| 13 : hasCycles_(false) | |
| 14 { | |
| 15 } | |
| 16 | |
| 17 void | |
| 18 MoveResolver::resetState() | |
| 19 { | |
| 20 hasCycles_ = false; | |
| 21 } | |
| 22 | |
| 23 bool | |
| 24 MoveResolver::addMove(const MoveOperand &from, const MoveOperand &to, MoveOp::Type type) | |
| 25 { | |
| 26 // Assert that we're not doing no-op moves. | |
| 27 JS_ASSERT(!(from == to)); | |
| 28 PendingMove *pm = movePool_.allocate(); | |
| 29 if (!pm) | |
| 30 return false; | |
| 31 new (pm) PendingMove(from, to, type); | |
| 32 pending_.pushBack(pm); | |
| 33 return true; | |
| 34 } | |
| 35 | |
| 36 // Given move (A -> B), this function attempts to find any move (B -> *) in the | |
| 37 // pending move list, and returns the first one. | |
| 38 MoveResolver::PendingMove * | |
| 39 MoveResolver::findBlockingMove(const PendingMove *last) | |
| 40 { | |
| 41 for (PendingMoveIterator iter = pending_.begin(); iter != pending_.end(); iter++) { | |
| 42 PendingMove *other = *iter; | |
| 43 | |
| 44 if (other->from() == last->to()) { | |
| 45 // We now have pairs in the form (A -> X) (X -> y). The second pair | |
| 46 // blocks the move in the first pair, so return it. | |
| 47 return other; | |
| 48 } | |
| 49 } | |
| 50 | |
| 51 // No blocking moves found. | |
| 52 return nullptr; | |
| 53 } | |
| 54 | |
| 55 bool | |
| 56 MoveResolver::resolve() | |
| 57 { | |
| 58 resetState(); | |
| 59 orderedMoves_.clear(); | |
| 60 | |
| 61 InlineList<PendingMove> stack; | |
| 62 | |
| 63 // This is a depth-first-search without recursion, which tries to find | |
| 64 // cycles in a list of moves. The output is not entirely optimal for cases | |
| 65 // where a source has multiple destinations, i.e.: | |
| 66 // [stack0] -> A | |
| 67 // [stack0] -> B | |
| 68 // | |
| 69 // These moves may not occur next to each other in the list, making it | |
| 70 // harder for the emitter to optimize memory to memory traffic. However, we | |
| 71 // expect duplicate sources to be rare in greedy allocation, and indicative | |
| 72 // of an error in LSRA. | |
| 73 // | |
| 74 // Algorithm. | |
| 75 // | |
| 76 // S = Traversal stack. | |
| 77 // P = Pending move list. | |
| 78 // O = Ordered list of moves. | |
| 79 // | |
| 80 // As long as there are pending moves in P: | |
| 81 // Let |root| be any pending move removed from P | |
| 82 // Add |root| to the traversal stack. | |
| 83 // As long as S is not empty: | |
| 84 // Let |L| be the most recent move added to S. | |
| 85 // | |
| 86 // Find any pending move M whose source is L's destination, thus | |
| 87 // preventing L's move until M has completed. | |
| 88 // | |
| 89 // If a move M was found, | |
| 90 // Remove M from the pending list. | |
| 91 // If M's destination is |root|, | |
| 92 // Annotate M and |root| as cycles. | |
| 93 // Add M to S. | |
| 94 // do not Add M to O, since M may have other conflictors in P that have not yet been processed. | |
| 95 // Otherwise, | |
| 96 // Add M to S. | |
| 97 // Otherwise, | |
| 98 // Remove L from S. | |
| 99 // Add L to O. | |
| 100 // | |
| 101 while (!pending_.empty()) { | |
| 102 PendingMove *pm = pending_.popBack(); | |
| 103 | |
| 104 // Add this pending move to the cycle detection stack. | |
| 105 stack.pushBack(pm); | |
| 106 | |
| 107 while (!stack.empty()) { | |
| 108 PendingMove *blocking = findBlockingMove(stack.peekBack()); | |
| 109 | |
| 110 if (blocking) { | |
| 111 if (blocking->to() == pm->from()) { | |
| 112 // We annotate cycles at each move in the cycle, and | |
| 113 // assert that we do not find two cycles in one move chain | |
| 114 // traversal (which would indicate two moves to the same | |
| 115 // destination). | |
| 116 pm->setCycleEnd(); | |
| 117 blocking->setCycleBegin(pm->type()); | |
| 118 hasCycles_ = true; | |
| 119 pending_.remove(blocking); | |
| 120 stack.pushBack(blocking); | |
| 121 } else { | |
| 122 // This is a new link in the move chain, so keep | |
| 123 // searching for a cycle. | |
| 124 pending_.remove(blocking); | |
| 125 stack.pushBack(blocking); | |
| 126 } | |
| 127 } else { | |
| 128 // Otherwise, pop the last move on the search stack because it's | |
| 129 // complete and not participating in a cycle. The resulting | |
| 130 // move can safely be added to the ordered move list. | |
| 131 PendingMove *done = stack.popBack(); | |
| 132 if (!orderedMoves_.append(*done)) | |
| 133 return false; | |
| 134 movePool_.free(done); | |
| 135 } | |
| 136 } | |
| 137 } | |
| 138 | |
| 139 return true; | |
| 140 } |
