OLD | NEW |
| (Empty) |
1 // Copyright 2013 the V8 project authors. All rights reserved. | |
2 // Redistribution and use in source and binary forms, with or without | |
3 // modification, are permitted provided that the following conditions are | |
4 // met: | |
5 // | |
6 // * Redistributions of source code must retain the above copyright | |
7 // notice, this list of conditions and the following disclaimer. | |
8 // * Redistributions in binary form must reproduce the above | |
9 // copyright notice, this list of conditions and the following | |
10 // disclaimer in the documentation and/or other materials provided | |
11 // with the distribution. | |
12 // * Neither the name of Google Inc. nor the names of its | |
13 // contributors may be used to endorse or promote products derived | |
14 // from this software without specific prior written permission. | |
15 // | |
16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS | |
17 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT | |
18 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR | |
19 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT | |
20 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, | |
21 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT | |
22 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, | |
23 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY | |
24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT | |
25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE | |
26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | |
27 | |
28 #include "v8.h" | |
29 | |
30 #include "a64/lithium-gap-resolver-a64.h" | |
31 #include "a64/lithium-codegen-a64.h" | |
32 | |
33 namespace v8 { | |
34 namespace internal { | |
35 | |
36 // We use the root register to spill a value while breaking a cycle in parallel | |
37 // moves. We don't need access to roots while resolving the move list and using | |
38 // the root register has two advantages: | |
39 // - It is not in crankshaft allocatable registers list, so it can't interfere | |
40 // with any of the moves we are resolving. | |
41 // - We don't need to push it on the stack, as we can reload it with its value | |
42 // once we have resolved a cycle. | |
43 #define kSavedValue root | |
44 | |
45 LGapResolver::LGapResolver(LCodeGen* owner) | |
46 : cgen_(owner), moves_(32, owner->zone()), root_index_(0), in_cycle_(false), | |
47 saved_destination_(NULL), need_to_restore_root_(false) { } | |
48 | |
49 | |
50 #define __ ACCESS_MASM(cgen_->masm()) | |
51 | |
52 void LGapResolver::Resolve(LParallelMove* parallel_move) { | |
53 ASSERT(moves_.is_empty()); | |
54 | |
55 // Build up a worklist of moves. | |
56 BuildInitialMoveList(parallel_move); | |
57 | |
58 for (int i = 0; i < moves_.length(); ++i) { | |
59 LMoveOperands move = moves_[i]; | |
60 | |
61 // Skip constants to perform them last. They don't block other moves | |
62 // and skipping such moves with register destinations keeps those | |
63 // registers free for the whole algorithm. | |
64 if (!move.IsEliminated() && !move.source()->IsConstantOperand()) { | |
65 root_index_ = i; // Any cycle is found when we reach this move again. | |
66 PerformMove(i); | |
67 if (in_cycle_) RestoreValue(); | |
68 } | |
69 } | |
70 | |
71 // Perform the moves with constant sources. | |
72 for (int i = 0; i < moves_.length(); ++i) { | |
73 LMoveOperands move = moves_[i]; | |
74 | |
75 if (!move.IsEliminated()) { | |
76 ASSERT(move.source()->IsConstantOperand()); | |
77 EmitMove(i); | |
78 } | |
79 } | |
80 | |
81 if (need_to_restore_root_) { | |
82 ASSERT(kSavedValue.Is(root)); | |
83 __ InitializeRootRegister(); | |
84 need_to_restore_root_ = false; | |
85 } | |
86 | |
87 moves_.Rewind(0); | |
88 } | |
89 | |
90 | |
91 void LGapResolver::BuildInitialMoveList(LParallelMove* parallel_move) { | |
92 // Perform a linear sweep of the moves to add them to the initial list of | |
93 // moves to perform, ignoring any move that is redundant (the source is | |
94 // the same as the destination, the destination is ignored and | |
95 // unallocated, or the move was already eliminated). | |
96 const ZoneList<LMoveOperands>* moves = parallel_move->move_operands(); | |
97 for (int i = 0; i < moves->length(); ++i) { | |
98 LMoveOperands move = moves->at(i); | |
99 if (!move.IsRedundant()) moves_.Add(move, cgen_->zone()); | |
100 } | |
101 Verify(); | |
102 } | |
103 | |
104 | |
105 void LGapResolver::PerformMove(int index) { | |
106 // Each call to this function performs a move and deletes it from the move | |
107 // graph. We first recursively perform any move blocking this one. We | |
108 // mark a move as "pending" on entry to PerformMove in order to detect | |
109 // cycles in the move graph. | |
110 LMoveOperands& current_move = moves_[index]; | |
111 | |
112 ASSERT(!current_move.IsPending()); | |
113 ASSERT(!current_move.IsRedundant()); | |
114 | |
115 // Clear this move's destination to indicate a pending move. The actual | |
116 // destination is saved in a stack allocated local. Multiple moves can | |
117 // be pending because this function is recursive. | |
118 ASSERT(current_move.source() != NULL); // Otherwise it will look eliminated. | |
119 LOperand* destination = current_move.destination(); | |
120 current_move.set_destination(NULL); | |
121 | |
122 // Perform a depth-first traversal of the move graph to resolve | |
123 // dependencies. Any unperformed, unpending move with a source the same | |
124 // as this one's destination blocks this one so recursively perform all | |
125 // such moves. | |
126 for (int i = 0; i < moves_.length(); ++i) { | |
127 LMoveOperands other_move = moves_[i]; | |
128 if (other_move.Blocks(destination) && !other_move.IsPending()) { | |
129 PerformMove(i); | |
130 // If there is a blocking, pending move it must be moves_[root_index_] | |
131 // and all other moves with the same source as moves_[root_index_] are | |
132 // sucessfully executed (because they are cycle-free) by this loop. | |
133 } | |
134 } | |
135 | |
136 // We are about to resolve this move and don't need it marked as | |
137 // pending, so restore its destination. | |
138 current_move.set_destination(destination); | |
139 | |
140 // The move may be blocked on a pending move, which must be the starting move. | |
141 // In this case, we have a cycle, and we save the source of this move to | |
142 // a scratch register to break it. | |
143 LMoveOperands other_move = moves_[root_index_]; | |
144 if (other_move.Blocks(destination)) { | |
145 ASSERT(other_move.IsPending()); | |
146 BreakCycle(index); | |
147 return; | |
148 } | |
149 | |
150 // This move is no longer blocked. | |
151 EmitMove(index); | |
152 } | |
153 | |
154 | |
155 void LGapResolver::Verify() { | |
156 #ifdef ENABLE_SLOW_ASSERTS | |
157 // No operand should be the destination for more than one move. | |
158 for (int i = 0; i < moves_.length(); ++i) { | |
159 LOperand* destination = moves_[i].destination(); | |
160 for (int j = i + 1; j < moves_.length(); ++j) { | |
161 SLOW_ASSERT(!destination->Equals(moves_[j].destination())); | |
162 } | |
163 } | |
164 #endif | |
165 } | |
166 | |
167 | |
168 void LGapResolver::BreakCycle(int index) { | |
169 ASSERT(moves_[index].destination()->Equals(moves_[root_index_].source())); | |
170 ASSERT(!in_cycle_); | |
171 | |
172 // We use a register which is not allocatable by crankshaft to break the cycle | |
173 // to be sure it doesn't interfere with the moves we are resolving. | |
174 ASSERT(!kSavedValue.IsAllocatable()); | |
175 need_to_restore_root_ = true; | |
176 | |
177 // We save in a register the source of that move and we remember its | |
178 // destination. Then we mark this move as resolved so the cycle is | |
179 // broken and we can perform the other moves. | |
180 in_cycle_ = true; | |
181 LOperand* source = moves_[index].source(); | |
182 saved_destination_ = moves_[index].destination(); | |
183 | |
184 if (source->IsRegister()) { | |
185 __ Mov(kSavedValue, cgen_->ToRegister(source)); | |
186 } else if (source->IsStackSlot()) { | |
187 __ Ldr(kSavedValue, cgen_->ToMemOperand(source)); | |
188 } else if (source->IsDoubleRegister()) { | |
189 // TODO(all): We should use a double register to store the value to avoid | |
190 // the penalty of the mov across register banks. We are going to reserve | |
191 // d31 to hold 0.0 value. We could clobber this register while breaking the | |
192 // cycle and restore it after like we do with the root register. | |
193 // LGapResolver::RestoreValue() will need to be updated as well when we'll | |
194 // do that. | |
195 __ Fmov(kSavedValue, cgen_->ToDoubleRegister(source)); | |
196 } else if (source->IsDoubleStackSlot()) { | |
197 __ Ldr(kSavedValue, cgen_->ToMemOperand(source)); | |
198 } else { | |
199 UNREACHABLE(); | |
200 } | |
201 | |
202 // Mark this move as resolved. | |
203 // This move will be actually performed by moving the saved value to this | |
204 // move's destination in LGapResolver::RestoreValue(). | |
205 moves_[index].Eliminate(); | |
206 } | |
207 | |
208 | |
209 void LGapResolver::RestoreValue() { | |
210 ASSERT(in_cycle_); | |
211 ASSERT(saved_destination_ != NULL); | |
212 | |
213 if (saved_destination_->IsRegister()) { | |
214 __ Mov(cgen_->ToRegister(saved_destination_), kSavedValue); | |
215 } else if (saved_destination_->IsStackSlot()) { | |
216 __ Str(kSavedValue, cgen_->ToMemOperand(saved_destination_)); | |
217 } else if (saved_destination_->IsDoubleRegister()) { | |
218 __ Fmov(cgen_->ToDoubleRegister(saved_destination_), kSavedValue); | |
219 } else if (saved_destination_->IsDoubleStackSlot()) { | |
220 __ Str(kSavedValue, cgen_->ToMemOperand(saved_destination_)); | |
221 } else { | |
222 UNREACHABLE(); | |
223 } | |
224 | |
225 in_cycle_ = false; | |
226 saved_destination_ = NULL; | |
227 } | |
228 | |
229 | |
230 void LGapResolver::EmitMove(int index) { | |
231 LOperand* source = moves_[index].source(); | |
232 LOperand* destination = moves_[index].destination(); | |
233 | |
234 // Dispatch on the source and destination operand kinds. Not all | |
235 // combinations are possible. | |
236 | |
237 if (source->IsRegister()) { | |
238 Register source_register = cgen_->ToRegister(source); | |
239 if (destination->IsRegister()) { | |
240 __ Mov(cgen_->ToRegister(destination), source_register); | |
241 } else { | |
242 ASSERT(destination->IsStackSlot()); | |
243 __ Str(source_register, cgen_->ToMemOperand(destination)); | |
244 } | |
245 | |
246 } else if (source->IsStackSlot()) { | |
247 MemOperand source_operand = cgen_->ToMemOperand(source); | |
248 if (destination->IsRegister()) { | |
249 __ Ldr(cgen_->ToRegister(destination), source_operand); | |
250 } else { | |
251 ASSERT(destination->IsStackSlot()); | |
252 EmitStackSlotMove(index); | |
253 } | |
254 | |
255 } else if (source->IsConstantOperand()) { | |
256 LConstantOperand* constant_source = LConstantOperand::cast(source); | |
257 if (destination->IsRegister()) { | |
258 Register dst = cgen_->ToRegister(destination); | |
259 if (cgen_->IsSmi(constant_source)) { | |
260 __ Mov(dst, cgen_->ToSmi(constant_source)); | |
261 } else if (cgen_->IsInteger32Constant(constant_source)) { | |
262 __ Mov(dst, cgen_->ToInteger32(constant_source)); | |
263 } else { | |
264 __ LoadObject(dst, cgen_->ToHandle(constant_source)); | |
265 } | |
266 } else if (destination->IsDoubleRegister()) { | |
267 DoubleRegister result = cgen_->ToDoubleRegister(destination); | |
268 __ Fmov(result, cgen_->ToDouble(constant_source)); | |
269 } else { | |
270 ASSERT(destination->IsStackSlot()); | |
271 ASSERT(!in_cycle_); // Constant moves happen after all cycles are gone. | |
272 need_to_restore_root_ = true; | |
273 if (cgen_->IsSmi(constant_source)) { | |
274 __ Mov(kSavedValue, cgen_->ToSmi(constant_source)); | |
275 } else if (cgen_->IsInteger32Constant(constant_source)) { | |
276 __ Mov(kSavedValue, cgen_->ToInteger32(constant_source)); | |
277 } else { | |
278 __ LoadObject(kSavedValue, cgen_->ToHandle(constant_source)); | |
279 } | |
280 __ Str(kSavedValue, cgen_->ToMemOperand(destination)); | |
281 } | |
282 | |
283 } else if (source->IsDoubleRegister()) { | |
284 DoubleRegister src = cgen_->ToDoubleRegister(source); | |
285 if (destination->IsDoubleRegister()) { | |
286 __ Fmov(cgen_->ToDoubleRegister(destination), src); | |
287 } else { | |
288 ASSERT(destination->IsDoubleStackSlot()); | |
289 __ Str(src, cgen_->ToMemOperand(destination)); | |
290 } | |
291 | |
292 } else if (source->IsDoubleStackSlot()) { | |
293 MemOperand src = cgen_->ToMemOperand(source); | |
294 if (destination->IsDoubleRegister()) { | |
295 __ Ldr(cgen_->ToDoubleRegister(destination), src); | |
296 } else { | |
297 ASSERT(destination->IsDoubleStackSlot()); | |
298 EmitStackSlotMove(index); | |
299 } | |
300 | |
301 } else { | |
302 UNREACHABLE(); | |
303 } | |
304 | |
305 // The move has been emitted, we can eliminate it. | |
306 moves_[index].Eliminate(); | |
307 } | |
308 | |
309 | |
310 void LGapResolver::EmitStackSlotMove(int index) { | |
311 // We need a temp register to perform a stack slot to stack slot move, and | |
312 // the register must not be involved in breaking cycles. | |
313 | |
314 // Use the Crankshaft double scratch register as the temporary. | |
315 DoubleRegister temp = crankshaft_fp_scratch; | |
316 | |
317 LOperand* src = moves_[index].source(); | |
318 LOperand* dst = moves_[index].destination(); | |
319 | |
320 ASSERT(src->IsStackSlot()); | |
321 ASSERT(dst->IsStackSlot()); | |
322 __ Ldr(temp, cgen_->ToMemOperand(src)); | |
323 __ Str(temp, cgen_->ToMemOperand(dst)); | |
324 } | |
325 | |
326 } } // namespace v8::internal | |
OLD | NEW |