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 namespace { | 15 namespace { |
16 | 16 |
| 17 #define REP_BIT(rep) (1 << static_cast<int>(rep)) |
| 18 |
| 19 const int kFloat32Bit = REP_BIT(MachineRepresentation::kFloat32); |
| 20 const int kFloat64Bit = REP_BIT(MachineRepresentation::kFloat64); |
| 21 |
17 inline bool Blocks(MoveOperands* move, InstructionOperand destination) { | 22 inline bool Blocks(MoveOperands* move, InstructionOperand destination) { |
18 return move->Blocks(destination); | 23 return !move->IsEliminated() && move->source().InterferesWith(destination); |
19 } | 24 } |
20 | 25 |
| 26 // Splits a FP move between two location operands into the equivalent series of |
| 27 // moves between smaller sub-operands, e.g. a double move to two single moves. |
| 28 // This helps reduce the number of cycles that would normally occur under FP |
| 29 // aliasing, and makes swaps much easier to implement. |
| 30 MoveOperands* Split(MoveOperands* move, MachineRepresentation smaller_rep, |
| 31 ParallelMove* moves) { |
| 32 DCHECK(!kSimpleFPAliasing); |
| 33 // Splitting is only possible when the slot size is the same as float size. |
| 34 DCHECK_EQ(kPointerSize, kFloatSize); |
| 35 const LocationOperand& src_loc = LocationOperand::cast(move->source()); |
| 36 const LocationOperand& dst_loc = LocationOperand::cast(move->destination()); |
| 37 MachineRepresentation dst_rep = dst_loc.representation(); |
| 38 DCHECK_NE(smaller_rep, dst_rep); |
| 39 auto src_kind = src_loc.location_kind(); |
| 40 auto dst_kind = dst_loc.location_kind(); |
21 | 41 |
22 inline bool IsRedundant(MoveOperands* move) { return move->IsRedundant(); } | 42 int aliases = |
| 43 1 << (ElementSizeLog2Of(dst_rep) - ElementSizeLog2Of(smaller_rep)); |
| 44 int base = -1; |
| 45 USE(base); |
| 46 DCHECK_EQ(aliases, RegisterConfiguration::Turbofan()->GetAliases( |
| 47 dst_rep, 0, smaller_rep, &base)); |
| 48 |
| 49 int src_index = -1; |
| 50 int slot_size = (1 << ElementSizeLog2Of(smaller_rep)) / kPointerSize; |
| 51 int src_step = 1; |
| 52 if (src_kind == LocationOperand::REGISTER) { |
| 53 src_index = src_loc.register_code() * aliases; |
| 54 } else { |
| 55 src_index = src_loc.index(); |
| 56 // For operands that occuply multiple slots, the index refers to the last |
| 57 // slot. On little-endian architectures, we start at the high slot and use a |
| 58 // negative step so that register-to-slot moves are in the correct order. |
| 59 src_step = -slot_size; |
| 60 } |
| 61 int dst_index = -1; |
| 62 int dst_step = 1; |
| 63 if (dst_kind == LocationOperand::REGISTER) { |
| 64 dst_index = dst_loc.register_code() * aliases; |
| 65 } else { |
| 66 dst_index = dst_loc.index(); |
| 67 dst_step = -slot_size; |
| 68 } |
| 69 |
| 70 // Reuse 'move' for the first fragment. It is not pending. |
| 71 move->set_source(AllocatedOperand(src_kind, smaller_rep, src_index)); |
| 72 move->set_destination(AllocatedOperand(dst_kind, smaller_rep, dst_index)); |
| 73 // Add the remaining fragment moves. |
| 74 for (int i = 1; i < aliases; ++i) { |
| 75 src_index += src_step; |
| 76 dst_index += dst_step; |
| 77 moves->AddMove(AllocatedOperand(src_kind, smaller_rep, src_index), |
| 78 AllocatedOperand(dst_kind, smaller_rep, dst_index)); |
| 79 } |
| 80 // Return the first fragment. |
| 81 return move; |
| 82 } |
23 | 83 |
24 } // namespace | 84 } // namespace |
25 | 85 |
| 86 void GapResolver::Resolve(ParallelMove* moves) { |
| 87 // Clear redundant moves, and collect FP move representations if aliasing |
| 88 // is non-simple. |
| 89 int reps = 0; |
| 90 for (size_t i = 0; i < moves->size();) { |
| 91 MoveOperands* move = (*moves)[i]; |
| 92 if (move->IsRedundant()) { |
| 93 (*moves)[i] = moves->back(); |
| 94 moves->pop_back(); |
| 95 continue; |
| 96 } |
| 97 i++; |
| 98 if (!kSimpleFPAliasing && move->destination().IsFPRegister()) { |
| 99 reps |= |
| 100 REP_BIT(LocationOperand::cast(move->destination()).representation()); |
| 101 } |
| 102 } |
26 | 103 |
27 void GapResolver::Resolve(ParallelMove* moves) const { | 104 if (!kSimpleFPAliasing) { |
28 // Clear redundant moves. | 105 if (reps && !base::bits::IsPowerOfTwo32(reps)) { |
29 auto it = | 106 // Start with the smallest FP moves, so we never encounter smaller moves |
30 std::remove_if(moves->begin(), moves->end(), std::ptr_fun(IsRedundant)); | 107 // in the middle of a cycle of larger moves. |
31 moves->erase(it, moves->end()); | 108 if ((reps & kFloat32Bit) != 0) { |
32 for (MoveOperands* move : *moves) { | 109 split_rep_ = MachineRepresentation::kFloat32; |
| 110 for (size_t i = 0; i < moves->size(); ++i) { |
| 111 auto move = (*moves)[i]; |
| 112 if (!move->IsEliminated() && move->destination().IsFloatRegister()) |
| 113 PerformMove(moves, move); |
| 114 } |
| 115 } |
| 116 if ((reps & kFloat64Bit) != 0) { |
| 117 split_rep_ = MachineRepresentation::kFloat64; |
| 118 for (size_t i = 0; i < moves->size(); ++i) { |
| 119 auto move = (*moves)[i]; |
| 120 if (!move->IsEliminated() && move->destination().IsDoubleRegister()) |
| 121 PerformMove(moves, move); |
| 122 } |
| 123 } |
| 124 } |
| 125 split_rep_ = MachineRepresentation::kSimd128; |
| 126 } |
| 127 |
| 128 for (size_t i = 0; i < moves->size(); ++i) { |
| 129 auto move = (*moves)[i]; |
33 if (!move->IsEliminated()) PerformMove(moves, move); | 130 if (!move->IsEliminated()) PerformMove(moves, move); |
34 } | 131 } |
35 } | 132 } |
36 | 133 |
37 void GapResolver::PerformMove(ParallelMove* moves, MoveOperands* move) const { | 134 void GapResolver::PerformMove(ParallelMove* moves, MoveOperands* move) { |
38 // Each call to this function performs a move and deletes it from the move | 135 // Each call to this function performs a move and deletes it from the move |
39 // graph. We first recursively perform any move blocking this one. We mark a | 136 // graph. We first recursively perform any move blocking this one. We mark a |
40 // move as "pending" on entry to PerformMove in order to detect cycles in the | 137 // move as "pending" on entry to PerformMove in order to detect cycles in the |
41 // move graph. We use operand swaps to resolve cycles, which means that a | 138 // move graph. We use operand swaps to resolve cycles, which means that a |
42 // call to PerformMove could change any source operand in the move graph. | 139 // call to PerformMove could change any source operand in the move graph. |
43 DCHECK(!move->IsPending()); | 140 DCHECK(!move->IsPending()); |
44 DCHECK(!move->IsRedundant()); | 141 DCHECK(!move->IsRedundant()); |
45 | 142 |
46 // Clear this move's destination to indicate a pending move. The actual | 143 // Clear this move's destination to indicate a pending move. The actual |
47 // destination is saved on the side. | 144 // destination is saved on the side. |
48 DCHECK(!move->source().IsInvalid()); // Or else it will look eliminated. | 145 InstructionOperand source = move->source(); |
| 146 DCHECK(!source.IsInvalid()); // Or else it will look eliminated. |
49 InstructionOperand destination = move->destination(); | 147 InstructionOperand destination = move->destination(); |
50 move->SetPending(); | 148 move->SetPending(); |
51 | 149 |
| 150 // We may need to split moves between FP locations differently. |
| 151 bool is_fp_loc_move = !kSimpleFPAliasing && destination.IsFPLocationOperand(); |
| 152 |
52 // Perform a depth-first traversal of the move graph to resolve dependencies. | 153 // Perform a depth-first traversal of the move graph to resolve dependencies. |
53 // Any unperformed, unpending move with a source the same as this one's | 154 // Any unperformed, unpending move with a source the same as this one's |
54 // destination blocks this one so recursively perform all such moves. | 155 // destination blocks this one so recursively perform all such moves. |
55 for (MoveOperands* other : *moves) { | 156 for (size_t i = 0; i < moves->size(); ++i) { |
56 if (other->Blocks(destination) && !other->IsPending()) { | 157 auto other = (*moves)[i]; |
| 158 if (other->IsEliminated()) continue; |
| 159 if (other->IsPending()) continue; |
| 160 if (other->source().InterferesWith(destination)) { |
| 161 if (!kSimpleFPAliasing && is_fp_loc_move && |
| 162 LocationOperand::cast(other->source()).representation() > |
| 163 split_rep_) { |
| 164 // 'other' must also be an FP location move. Break it into fragments |
| 165 // of the same size as 'move'. 'other' is set to one of the fragments, |
| 166 // and the rest are appended to 'moves'. |
| 167 other = Split(other, split_rep_, moves); |
| 168 // 'other' may not block destination now. |
| 169 if (!other->source().InterferesWith(destination)) continue; |
| 170 } |
57 // Though PerformMove can change any source operand in the move graph, | 171 // Though PerformMove can change any source operand in the move graph, |
58 // this call cannot create a blocking move via a swap (this loop does not | 172 // this call cannot create a blocking move via a swap (this loop does not |
59 // miss any). Assume there is a non-blocking move with source A and this | 173 // miss any). Assume there is a non-blocking move with source A and this |
60 // move is blocked on source B and there is a swap of A and B. Then A and | 174 // move is blocked on source B and there is a swap of A and B. Then A and |
61 // B must be involved in the same cycle (or they would not be swapped). | 175 // B must be involved in the same cycle (or they would not be swapped). |
62 // Since this move's destination is B and there is only a single incoming | 176 // Since this move's destination is B and there is only a single incoming |
63 // edge to an operand, this move must also be involved in the same cycle. | 177 // edge to an operand, this move must also be involved in the same cycle. |
64 // In that case, the blocking move will be created but will be "pending" | 178 // In that case, the blocking move will be created but will be "pending" |
65 // when we return from PerformMove. | 179 // when we return from PerformMove. |
66 PerformMove(moves, other); | 180 PerformMove(moves, other); |
67 } | 181 } |
68 } | 182 } |
69 | 183 |
| 184 // This move's source may have changed due to swaps to resolve cycles and so |
| 185 // it may now be the last move in the cycle. If so remove it. |
| 186 source = move->source(); |
| 187 if (source.EqualsCanonicalized(destination)) { |
| 188 move->Eliminate(); |
| 189 return; |
| 190 } |
| 191 |
70 // We are about to resolve this move and don't need it marked as pending, so | 192 // We are about to resolve this move and don't need it marked as pending, so |
71 // restore its destination. | 193 // restore its destination. |
72 move->set_destination(destination); | 194 move->set_destination(destination); |
73 | 195 |
74 // This move's source may have changed due to swaps to resolve cycles and so | |
75 // it may now be the last move in the cycle. If so remove it. | |
76 InstructionOperand source = move->source(); | |
77 if (source.InterferesWith(destination)) { | |
78 move->Eliminate(); | |
79 return; | |
80 } | |
81 | |
82 // The move may be blocked on a (at most one) pending move, in which case we | 196 // The move may be blocked on a (at most one) pending move, in which case we |
83 // have a cycle. Search for such a blocking move and perform a swap to | 197 // have a cycle. Search for such a blocking move and perform a swap to |
84 // resolve it. | 198 // resolve it. |
85 auto blocker = std::find_if(moves->begin(), moves->end(), | 199 auto blocker = std::find_if(moves->begin(), moves->end(), |
86 std::bind2nd(std::ptr_fun(&Blocks), destination)); | 200 std::bind2nd(std::ptr_fun(&Blocks), destination)); |
87 if (blocker == moves->end()) { | 201 if (blocker == moves->end()) { |
88 // The easy case: This move is not blocked. | 202 // The easy case: This move is not blocked. |
89 assembler_->AssembleMove(&source, &destination); | 203 assembler_->AssembleMove(&source, &destination); |
90 move->Eliminate(); | 204 move->Eliminate(); |
91 return; | 205 return; |
92 } | 206 } |
93 | 207 |
94 DCHECK((*blocker)->IsPending()); | |
95 // Ensure source is a register or both are stack slots, to limit swap cases. | 208 // Ensure source is a register or both are stack slots, to limit swap cases. |
96 if (source.IsStackSlot() || source.IsFPStackSlot()) { | 209 if (source.IsStackSlot() || source.IsFPStackSlot()) { |
97 std::swap(source, destination); | 210 std::swap(source, destination); |
98 } | 211 } |
99 assembler_->AssembleSwap(&source, &destination); | 212 assembler_->AssembleSwap(&source, &destination); |
100 move->Eliminate(); | 213 move->Eliminate(); |
101 | 214 |
102 // Any unperformed (including pending) move with a source of either this | 215 // Update outstanding moves whose source may now have been moved. |
103 // move's source or destination needs to have their source changed to | 216 if (!kSimpleFPAliasing && is_fp_loc_move) { |
104 // reflect the state of affairs after the swap. | 217 // We may have to split larger moves. |
105 for (MoveOperands* other : *moves) { | 218 for (size_t i = 0; i < moves->size(); ++i) { |
106 if (other->Blocks(source)) { | 219 auto other = (*moves)[i]; |
107 other->set_source(destination); | 220 if (other->IsEliminated()) continue; |
108 } else if (other->Blocks(destination)) { | 221 if (source.InterferesWith(other->source())) { |
109 other->set_source(source); | 222 if (LocationOperand::cast(other->source()).representation() > |
| 223 split_rep_) { |
| 224 other = Split(other, split_rep_, moves); |
| 225 if (!source.InterferesWith(other->source())) continue; |
| 226 } |
| 227 other->set_source(destination); |
| 228 } else if (destination.InterferesWith(other->source())) { |
| 229 if (LocationOperand::cast(other->source()).representation() > |
| 230 split_rep_) { |
| 231 other = Split(other, split_rep_, moves); |
| 232 if (!destination.InterferesWith(other->source())) continue; |
| 233 } |
| 234 other->set_source(source); |
| 235 } |
| 236 } |
| 237 } else { |
| 238 for (auto other : *moves) { |
| 239 if (other->IsEliminated()) continue; |
| 240 if (source.EqualsCanonicalized(other->source())) { |
| 241 other->set_source(destination); |
| 242 } else if (destination.EqualsCanonicalized(other->source())) { |
| 243 other->set_source(source); |
| 244 } |
110 } | 245 } |
111 } | 246 } |
112 } | 247 } |
113 } // namespace compiler | 248 } // namespace compiler |
114 } // namespace internal | 249 } // namespace internal |
115 } // namespace v8 | 250 } // namespace v8 |
OLD | NEW |