| OLD | NEW |
| 1 // Copyright 2014 the V8 project authors. All rights reserved. | 1 // Copyright 2014 the V8 project authors. All rights reserved. |
| 2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
| 3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
| 4 | 4 |
| 5 #include "src/compiler/gap-resolver.h" | 5 #include "src/compiler/gap-resolver.h" |
| 6 | 6 |
| 7 #include <algorithm> | 7 #include <algorithm> |
| 8 #include <functional> | 8 #include <functional> |
| 9 #include <set> | 9 #include <set> |
| 10 | 10 |
| (...skipping 11 matching lines...) Expand all Loading... |
| 22 inline bool IsRedundant(MoveOperands* move) { return move->IsRedundant(); } | 22 inline bool IsRedundant(MoveOperands* move) { return move->IsRedundant(); } |
| 23 | 23 |
| 24 } // namespace | 24 } // namespace |
| 25 | 25 |
| 26 | 26 |
| 27 void GapResolver::Resolve(ParallelMove* moves) const { | 27 void GapResolver::Resolve(ParallelMove* moves) const { |
| 28 // Clear redundant moves. | 28 // Clear redundant moves. |
| 29 auto it = | 29 auto it = |
| 30 std::remove_if(moves->begin(), moves->end(), std::ptr_fun(IsRedundant)); | 30 std::remove_if(moves->begin(), moves->end(), std::ptr_fun(IsRedundant)); |
| 31 moves->erase(it, moves->end()); | 31 moves->erase(it, moves->end()); |
| 32 for (auto move : *moves) { | 32 for (MoveOperands* move : *moves) { |
| 33 if (!move->IsEliminated()) PerformMove(moves, move); | 33 if (!move->IsEliminated()) PerformMove(moves, move); |
| 34 } | 34 } |
| 35 } | 35 } |
| 36 | 36 |
| 37 | 37 |
| 38 void GapResolver::PerformMove(ParallelMove* moves, MoveOperands* move) const { | 38 void GapResolver::PerformMove(ParallelMove* moves, MoveOperands* move) const { |
| 39 // Each call to this function performs a move and deletes it from the move | 39 // Each call to this function performs a move and deletes it from the move |
| 40 // graph. We first recursively perform any move blocking this one. We mark a | 40 // graph. We first recursively perform any move blocking this one. We mark a |
| 41 // move as "pending" on entry to PerformMove in order to detect cycles in the | 41 // move as "pending" on entry to PerformMove in order to detect cycles in the |
| 42 // move graph. We use operand swaps to resolve cycles, which means that a | 42 // move graph. We use operand swaps to resolve cycles, which means that a |
| 43 // call to PerformMove could change any source operand in the move graph. | 43 // call to PerformMove could change any source operand in the move graph. |
| 44 DCHECK(!move->IsPending()); | 44 DCHECK(!move->IsPending()); |
| 45 DCHECK(!move->IsRedundant()); | 45 DCHECK(!move->IsRedundant()); |
| 46 | 46 |
| 47 // Clear this move's destination to indicate a pending move. The actual | 47 // Clear this move's destination to indicate a pending move. The actual |
| 48 // destination is saved on the side. | 48 // destination is saved on the side. |
| 49 DCHECK(!move->source().IsInvalid()); // Or else it will look eliminated. | 49 DCHECK(!move->source().IsInvalid()); // Or else it will look eliminated. |
| 50 InstructionOperand destination = move->destination(); | 50 InstructionOperand destination = move->destination(); |
| 51 move->SetPending(); | 51 move->SetPending(); |
| 52 | 52 |
| 53 // Perform a depth-first traversal of the move graph to resolve dependencies. | 53 // Perform a depth-first traversal of the move graph to resolve dependencies. |
| 54 // Any unperformed, unpending move with a source the same as this one's | 54 // Any unperformed, unpending move with a source the same as this one's |
| 55 // destination blocks this one so recursively perform all such moves. | 55 // destination blocks this one so recursively perform all such moves. |
| 56 for (auto other : *moves) { | 56 for (MoveOperands* other : *moves) { |
| 57 if (other->Blocks(destination) && !other->IsPending()) { | 57 if (other->Blocks(destination) && !other->IsPending()) { |
| 58 // Though PerformMove can change any source operand in the move graph, | 58 // Though PerformMove can change any source operand in the move graph, |
| 59 // this call cannot create a blocking move via a swap (this loop does not | 59 // this call cannot create a blocking move via a swap (this loop does not |
| 60 // miss any). Assume there is a non-blocking move with source A and this | 60 // miss any). Assume there is a non-blocking move with source A and this |
| 61 // move is blocked on source B and there is a swap of A and B. Then A and | 61 // move is blocked on source B and there is a swap of A and B. Then A and |
| 62 // B must be involved in the same cycle (or they would not be swapped). | 62 // B must be involved in the same cycle (or they would not be swapped). |
| 63 // Since this move's destination is B and there is only a single incoming | 63 // Since this move's destination is B and there is only a single incoming |
| 64 // edge to an operand, this move must also be involved in the same cycle. | 64 // edge to an operand, this move must also be involved in the same cycle. |
| 65 // In that case, the blocking move will be created but will be "pending" | 65 // In that case, the blocking move will be created but will be "pending" |
| 66 // when we return from PerformMove. | 66 // when we return from PerformMove. |
| (...skipping 29 matching lines...) Expand all Loading... |
| 96 // Ensure source is a register or both are stack slots, to limit swap cases. | 96 // Ensure source is a register or both are stack slots, to limit swap cases. |
| 97 if (source.IsStackSlot() || source.IsDoubleStackSlot()) { | 97 if (source.IsStackSlot() || source.IsDoubleStackSlot()) { |
| 98 std::swap(source, destination); | 98 std::swap(source, destination); |
| 99 } | 99 } |
| 100 assembler_->AssembleSwap(&source, &destination); | 100 assembler_->AssembleSwap(&source, &destination); |
| 101 move->Eliminate(); | 101 move->Eliminate(); |
| 102 | 102 |
| 103 // Any unperformed (including pending) move with a source of either this | 103 // Any unperformed (including pending) move with a source of either this |
| 104 // move's source or destination needs to have their source changed to | 104 // move's source or destination needs to have their source changed to |
| 105 // reflect the state of affairs after the swap. | 105 // reflect the state of affairs after the swap. |
| 106 for (auto other : *moves) { | 106 for (MoveOperands* other : *moves) { |
| 107 if (other->Blocks(source)) { | 107 if (other->Blocks(source)) { |
| 108 other->set_source(destination); | 108 other->set_source(destination); |
| 109 } else if (other->Blocks(destination)) { | 109 } else if (other->Blocks(destination)) { |
| 110 other->set_source(source); | 110 other->set_source(source); |
| 111 } | 111 } |
| 112 } | 112 } |
| 113 } | 113 } |
| 114 } // namespace compiler | 114 } // namespace compiler |
| 115 } // namespace internal | 115 } // namespace internal |
| 116 } // namespace v8 | 116 } // namespace v8 |
| OLD | NEW |