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 |