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 |
11 namespace v8 { | 11 namespace v8 { |
12 namespace internal { | 12 namespace internal { |
13 namespace compiler { | 13 namespace compiler { |
14 | 14 |
15 typedef ZoneList<MoveOperands>::iterator op_iterator; | 15 typedef ZoneList<MoveOperands>::iterator op_iterator; |
16 | 16 |
17 #ifdef ENABLE_SLOW_ASSERTS | 17 #ifdef ENABLE_SLOW_DCHECKS |
18 // TODO(svenpanne) Brush up InstructionOperand with comparison? | 18 // TODO(svenpanne) Brush up InstructionOperand with comparison? |
19 struct InstructionOperandComparator { | 19 struct InstructionOperandComparator { |
20 bool operator()(const InstructionOperand* x, | 20 bool operator()(const InstructionOperand* x, |
21 const InstructionOperand* y) const { | 21 const InstructionOperand* y) const { |
22 return (x->kind() < y->kind()) || | 22 return (x->kind() < y->kind()) || |
23 (x->kind() == y->kind() && x->index() < y->index()); | 23 (x->kind() == y->kind() && x->index() < y->index()); |
24 } | 24 } |
25 }; | 25 }; |
26 #endif | 26 #endif |
27 | 27 |
28 // No operand should be the destination for more than one move. | 28 // No operand should be the destination for more than one move. |
29 static void VerifyMovesAreInjective(ZoneList<MoveOperands>* moves) { | 29 static void VerifyMovesAreInjective(ZoneList<MoveOperands>* moves) { |
30 #ifdef ENABLE_SLOW_ASSERTS | 30 #ifdef ENABLE_SLOW_DCHECKS |
31 std::set<InstructionOperand*, InstructionOperandComparator> seen; | 31 std::set<InstructionOperand*, InstructionOperandComparator> seen; |
32 for (op_iterator i = moves->begin(); i != moves->end(); ++i) { | 32 for (op_iterator i = moves->begin(); i != moves->end(); ++i) { |
33 SLOW_ASSERT(seen.find(i->destination()) == seen.end()); | 33 SLOW_DCHECK(seen.find(i->destination()) == seen.end()); |
34 seen.insert(i->destination()); | 34 seen.insert(i->destination()); |
35 } | 35 } |
36 #endif | 36 #endif |
37 } | 37 } |
38 | 38 |
39 | 39 |
40 void GapResolver::Resolve(ParallelMove* parallel_move) const { | 40 void GapResolver::Resolve(ParallelMove* parallel_move) const { |
41 ZoneList<MoveOperands>* moves = parallel_move->move_operands(); | 41 ZoneList<MoveOperands>* moves = parallel_move->move_operands(); |
42 // TODO(svenpanne) Use the member version of remove_if when we use real lists. | 42 // TODO(svenpanne) Use the member version of remove_if when we use real lists. |
43 op_iterator end = | 43 op_iterator end = |
44 std::remove_if(moves->begin(), moves->end(), | 44 std::remove_if(moves->begin(), moves->end(), |
45 std::mem_fun_ref(&MoveOperands::IsRedundant)); | 45 std::mem_fun_ref(&MoveOperands::IsRedundant)); |
46 moves->Rewind(static_cast<int>(end - moves->begin())); | 46 moves->Rewind(static_cast<int>(end - moves->begin())); |
47 | 47 |
48 VerifyMovesAreInjective(moves); | 48 VerifyMovesAreInjective(moves); |
49 | 49 |
50 for (op_iterator move = moves->begin(); move != moves->end(); ++move) { | 50 for (op_iterator move = moves->begin(); move != moves->end(); ++move) { |
51 if (!move->IsEliminated()) PerformMove(moves, &*move); | 51 if (!move->IsEliminated()) PerformMove(moves, &*move); |
52 } | 52 } |
53 } | 53 } |
54 | 54 |
55 | 55 |
56 void GapResolver::PerformMove(ZoneList<MoveOperands>* moves, | 56 void GapResolver::PerformMove(ZoneList<MoveOperands>* moves, |
57 MoveOperands* move) const { | 57 MoveOperands* move) const { |
58 // Each call to this function performs a move and deletes it from the move | 58 // Each call to this function performs a move and deletes it from the move |
59 // graph. We first recursively perform any move blocking this one. We mark a | 59 // graph. We first recursively perform any move blocking this one. We mark a |
60 // move as "pending" on entry to PerformMove in order to detect cycles in the | 60 // move as "pending" on entry to PerformMove in order to detect cycles in the |
61 // move graph. We use operand swaps to resolve cycles, which means that a | 61 // move graph. We use operand swaps to resolve cycles, which means that a |
62 // call to PerformMove could change any source operand in the move graph. | 62 // call to PerformMove could change any source operand in the move graph. |
63 ASSERT(!move->IsPending()); | 63 DCHECK(!move->IsPending()); |
64 ASSERT(!move->IsRedundant()); | 64 DCHECK(!move->IsRedundant()); |
65 | 65 |
66 // Clear this move's destination to indicate a pending move. The actual | 66 // Clear this move's destination to indicate a pending move. The actual |
67 // destination is saved on the side. | 67 // destination is saved on the side. |
68 ASSERT_NOT_NULL(move->source()); // Or else it will look eliminated. | 68 DCHECK_NOT_NULL(move->source()); // Or else it will look eliminated. |
69 InstructionOperand* destination = move->destination(); | 69 InstructionOperand* destination = move->destination(); |
70 move->set_destination(NULL); | 70 move->set_destination(NULL); |
71 | 71 |
72 // Perform a depth-first traversal of the move graph to resolve dependencies. | 72 // Perform a depth-first traversal of the move graph to resolve dependencies. |
73 // Any unperformed, unpending move with a source the same as this one's | 73 // Any unperformed, unpending move with a source the same as this one's |
74 // destination blocks this one so recursively perform all such moves. | 74 // destination blocks this one so recursively perform all such moves. |
75 for (op_iterator other = moves->begin(); other != moves->end(); ++other) { | 75 for (op_iterator other = moves->begin(); other != moves->end(); ++other) { |
76 if (other->Blocks(destination) && !other->IsPending()) { | 76 if (other->Blocks(destination) && !other->IsPending()) { |
77 // Though PerformMove can change any source operand in the move graph, | 77 // Though PerformMove can change any source operand in the move graph, |
78 // this call cannot create a blocking move via a swap (this loop does not | 78 // this call cannot create a blocking move via a swap (this loop does not |
(...skipping 26 matching lines...) Expand all Loading... |
105 op_iterator blocker = std::find_if( | 105 op_iterator blocker = std::find_if( |
106 moves->begin(), moves->end(), | 106 moves->begin(), moves->end(), |
107 std::bind2nd(std::mem_fun_ref(&MoveOperands::Blocks), destination)); | 107 std::bind2nd(std::mem_fun_ref(&MoveOperands::Blocks), destination)); |
108 if (blocker == moves->end()) { | 108 if (blocker == moves->end()) { |
109 // The easy case: This move is not blocked. | 109 // The easy case: This move is not blocked. |
110 assembler_->AssembleMove(source, destination); | 110 assembler_->AssembleMove(source, destination); |
111 move->Eliminate(); | 111 move->Eliminate(); |
112 return; | 112 return; |
113 } | 113 } |
114 | 114 |
115 ASSERT(blocker->IsPending()); | 115 DCHECK(blocker->IsPending()); |
116 // Ensure source is a register or both are stack slots, to limit swap cases. | 116 // Ensure source is a register or both are stack slots, to limit swap cases. |
117 if (source->IsStackSlot() || source->IsDoubleStackSlot()) { | 117 if (source->IsStackSlot() || source->IsDoubleStackSlot()) { |
118 std::swap(source, destination); | 118 std::swap(source, destination); |
119 } | 119 } |
120 assembler_->AssembleSwap(source, destination); | 120 assembler_->AssembleSwap(source, destination); |
121 move->Eliminate(); | 121 move->Eliminate(); |
122 | 122 |
123 // Any unperformed (including pending) move with a source of either this | 123 // Any unperformed (including pending) move with a source of either this |
124 // move's source or destination needs to have their source changed to | 124 // move's source or destination needs to have their source changed to |
125 // reflect the state of affairs after the swap. | 125 // reflect the state of affairs after the swap. |
126 for (op_iterator other = moves->begin(); other != moves->end(); ++other) { | 126 for (op_iterator other = moves->begin(); other != moves->end(); ++other) { |
127 if (other->Blocks(source)) { | 127 if (other->Blocks(source)) { |
128 other->set_source(destination); | 128 other->set_source(destination); |
129 } else if (other->Blocks(destination)) { | 129 } else if (other->Blocks(destination)) { |
130 other->set_source(source); | 130 other->set_source(source); |
131 } | 131 } |
132 } | 132 } |
133 } | 133 } |
134 } | 134 } |
135 } | 135 } |
136 } // namespace v8::internal::compiler | 136 } // namespace v8::internal::compiler |
OLD | NEW |