Line data Source code
1 : // Copyright 2011 the V8 project authors. All rights reserved.
2 : // Use of this source code is governed by a BSD-style license that can be
3 : // found in the LICENSE file.
4 :
5 : #if V8_TARGET_ARCH_X64
6 :
7 : #include "src/crankshaft/x64/lithium-gap-resolver-x64.h"
8 :
9 : #include "src/crankshaft/x64/lithium-codegen-x64.h"
10 : #include "src/objects-inl.h"
11 :
12 : namespace v8 {
13 : namespace internal {
14 :
15 279085 : LGapResolver::LGapResolver(LCodeGen* owner)
16 279085 : : cgen_(owner), moves_(32, owner->zone()) {}
17 :
18 :
19 24564097 : void LGapResolver::Resolve(LParallelMove* parallel_move) {
20 : DCHECK(moves_.is_empty());
21 : // Build up a worklist of moves.
22 24564097 : BuildInitialMoveList(parallel_move);
23 :
24 58619306 : for (int i = 0; i < moves_.length(); ++i) {
25 72855871 : LMoveOperands move = moves_[i];
26 : // Skip constants to perform them last. They don't block other moves
27 : // and skipping such moves with register destinations keeps those
28 : // registers free for the whole algorithm.
29 9311405 : if (!move.IsEliminated() && !move.source()->IsConstantOperand()) {
30 4414756 : PerformMove(i);
31 : }
32 : }
33 :
34 : // Perform the moves with constant sources.
35 34055180 : for (int i = 0; i < moves_.length(); ++i) {
36 4745523 : if (!moves_[i].IsEliminated()) {
37 : DCHECK(moves_[i].source()->IsConstantOperand());
38 151130 : EmitMove(i);
39 : }
40 : }
41 :
42 : moves_.Rewind(0);
43 24564134 : }
44 :
45 :
46 24564127 : void LGapResolver::BuildInitialMoveList(LParallelMove* parallel_move) {
47 : // Perform a linear sweep of the moves to add them to the initial list of
48 : // moves to perform, ignoring any move that is redundant (the source is
49 : // the same as the destination, the destination is ignored and
50 : // unallocated, or the move was already eliminated).
51 : const ZoneList<LMoveOperands>* moves = parallel_move->move_operands();
52 81664734 : for (int i = 0; i < moves->length(); ++i) {
53 57100595 : LMoveOperands move = moves->at(i);
54 16268228 : if (!move.IsRedundant()) moves_.Add(move, cgen_->zone());
55 : }
56 : Verify();
57 24564139 : }
58 :
59 :
60 4594391 : void LGapResolver::PerformMove(int index) {
61 : // Each call to this function performs a move and deletes it from the move
62 : // graph. We first recursively perform any move blocking this one. We
63 : // mark a move as "pending" on entry to PerformMove in order to detect
64 : // cycles in the move graph. We use operand swaps to resolve cycles,
65 : // which means that a call to PerformMove could change any source operand
66 : // in the move graph.
67 :
68 : DCHECK(!moves_[index].IsPending());
69 : DCHECK(!moves_[index].IsRedundant());
70 :
71 : // Clear this move's destination to indicate a pending move. The actual
72 : // destination is saved in a stack-allocated local. Recursion may allow
73 : // multiple moves to be pending.
74 : DCHECK(moves_[index].source() != NULL); // Or else it will look eliminated.
75 52659990 : LOperand* destination = moves_[index].destination();
76 : moves_[index].set_destination(NULL);
77 :
78 : // Perform a depth-first traversal of the move graph to resolve
79 : // dependencies. Any unperformed, unpending move with a source the same
80 : // as this one's destination blocks this one so recursively perform all
81 : // such moves.
82 26447270 : for (int i = 0; i < moves_.length(); ++i) {
83 8629244 : LMoveOperands other_move = moves_[i];
84 8900803 : if (other_move.Blocks(destination) && !other_move.IsPending()) {
85 : // Though PerformMove can change any source operand in the move graph,
86 : // this call cannot create a blocking move via a swap (this loop does
87 : // not miss any). Assume there is a non-blocking move with source A
88 : // and this move is blocked on source B and there is a swap of A and
89 : // B. Then A and B must be involved in the same cycle (or they would
90 : // not be swapped). Since this move's destination is B and there is
91 : // only a single incoming edge to an operand, this move must also be
92 : // involved in the same cycle. In that case, the blocking move will
93 : // be created but will be "pending" when we return from PerformMove.
94 179634 : PerformMove(i);
95 : }
96 : }
97 :
98 : // We are about to resolve this move and don't need it marked as
99 : // pending, so restore its destination.
100 : moves_[index].set_destination(destination);
101 :
102 : // This move's source may have changed due to swaps to resolve cycles and
103 : // so it may now be the last move in the cycle. If so remove it.
104 9188782 : if (moves_[index].source()->Equals(destination)) {
105 : moves_[index].Eliminate();
106 : return;
107 : }
108 :
109 : // The move may be blocked on a (at most one) pending move, in which case
110 : // we have a cycle. Search for such a blocking move and perform a swap to
111 : // resolve it.
112 20356628 : for (int i = 0; i < moves_.length(); ++i) {
113 8059198 : LMoveOperands other_move = moves_[i];
114 8059198 : if (other_move.Blocks(destination)) {
115 : DCHECK(other_move.IsPending());
116 132117 : EmitSwap(index);
117 : return;
118 : }
119 : }
120 :
121 : // This move is not blocked.
122 4370349 : EmitMove(index);
123 : }
124 :
125 :
126 0 : void LGapResolver::Verify() {
127 : #ifdef ENABLE_SLOW_DCHECKS
128 : // No operand should be the destination for more than one move.
129 : for (int i = 0; i < moves_.length(); ++i) {
130 : LOperand* destination = moves_[i].destination();
131 : for (int j = i + 1; j < moves_.length(); ++j) {
132 : SLOW_DCHECK(!destination->Equals(moves_[j].destination()));
133 : }
134 : }
135 : #endif
136 0 : }
137 :
138 :
139 : #define __ ACCESS_MASM(cgen_->masm())
140 :
141 :
142 4521480 : void LGapResolver::EmitMove(int index) {
143 13564444 : LOperand* source = moves_[index].source();
144 4521480 : LOperand* destination = moves_[index].destination();
145 :
146 : // Dispatch on the source and destination operand kinds. Not all
147 : // combinations are possible.
148 4521480 : if (source->IsRegister()) {
149 2187793 : Register src = cgen_->ToRegister(source);
150 2187795 : if (destination->IsRegister()) {
151 1399703 : Register dst = cgen_->ToRegister(destination);
152 4527638 : __ movp(dst, src);
153 : } else {
154 : DCHECK(destination->IsStackSlot());
155 788092 : Operand dst = cgen_->ToOperand(destination);
156 1576184 : __ movp(dst, src);
157 : }
158 :
159 2333687 : } else if (source->IsStackSlot()) {
160 2061077 : Operand src = cgen_->ToOperand(source);
161 2061079 : if (destination->IsRegister()) {
162 2056433 : Register dst = cgen_->ToRegister(destination);
163 4112866 : __ movp(dst, src);
164 : } else {
165 : DCHECK(destination->IsStackSlot());
166 4646 : Operand dst = cgen_->ToOperand(destination);
167 9292 : __ movp(kScratchRegister, src);
168 9292 : __ movp(dst, kScratchRegister);
169 : }
170 :
171 272610 : } else if (source->IsConstantOperand()) {
172 : LConstantOperand* constant_source = LConstantOperand::cast(source);
173 151130 : if (destination->IsRegister()) {
174 147531 : Register dst = cgen_->ToRegister(destination);
175 147531 : if (cgen_->IsSmiConstant(constant_source)) {
176 5 : __ Move(dst, cgen_->ToSmi(constant_source));
177 147526 : } else if (cgen_->IsInteger32Constant(constant_source)) {
178 29333 : int32_t constant = cgen_->ToInteger32(constant_source);
179 : // Do sign extension only for constant used as de-hoisted array key.
180 : // Others only need zero extension, which saves 2 bytes.
181 29333 : if (cgen_->IsDehoistedKeyConstant(constant_source)) {
182 1196 : __ Set(dst, constant);
183 : } else {
184 57470 : __ Set(dst, static_cast<uint32_t>(constant));
185 : }
186 : } else {
187 236386 : __ Move(dst, cgen_->ToHandle(constant_source));
188 : }
189 3599 : } else if (destination->IsDoubleRegister()) {
190 0 : double v = cgen_->ToDouble(constant_source);
191 : uint64_t int_val = bit_cast<uint64_t, double>(v);
192 0 : XMMRegister dst = cgen_->ToDoubleRegister(destination);
193 0 : if (int_val == 0) {
194 0 : __ Xorpd(dst, dst);
195 : } else {
196 0 : __ Set(kScratchRegister, int_val);
197 0 : __ Movq(dst, kScratchRegister);
198 : }
199 : } else {
200 : DCHECK(destination->IsStackSlot());
201 3599 : Operand dst = cgen_->ToOperand(destination);
202 3599 : if (cgen_->IsSmiConstant(constant_source)) {
203 0 : __ Move(dst, cgen_->ToSmi(constant_source));
204 3599 : } else if (cgen_->IsInteger32Constant(constant_source)) {
205 : // Do sign extension to 64 bits when stored into stack slot.
206 4182 : __ movp(dst, Immediate(cgen_->ToInteger32(constant_source)));
207 : } else {
208 3016 : __ Move(kScratchRegister, cgen_->ToHandle(constant_source));
209 3016 : __ movp(dst, kScratchRegister);
210 : }
211 : }
212 :
213 121480 : } else if (source->IsDoubleRegister()) {
214 53186 : XMMRegister src = cgen_->ToDoubleRegister(source);
215 53186 : if (destination->IsDoubleRegister()) {
216 72614 : __ Movapd(cgen_->ToDoubleRegister(destination), src);
217 : } else {
218 : DCHECK(destination->IsDoubleStackSlot());
219 33758 : __ Movsd(cgen_->ToOperand(destination), src);
220 : }
221 68294 : } else if (source->IsDoubleStackSlot()) {
222 68294 : Operand src = cgen_->ToOperand(source);
223 68294 : if (destination->IsDoubleRegister()) {
224 136588 : __ Movsd(cgen_->ToDoubleRegister(destination), src);
225 : } else {
226 : DCHECK(destination->IsDoubleStackSlot());
227 0 : __ Movsd(kScratchDoubleReg, src);
228 0 : __ Movsd(cgen_->ToOperand(destination), kScratchDoubleReg);
229 : }
230 : } else {
231 0 : UNREACHABLE();
232 : }
233 :
234 : moves_[index].Eliminate();
235 4521484 : }
236 :
237 :
238 132117 : void LGapResolver::EmitSwap(int index) {
239 1691695 : LOperand* source = moves_[index].source();
240 132117 : LOperand* destination = moves_[index].destination();
241 :
242 : // Dispatch on the source and destination operand kinds. Not all
243 : // combinations are possible.
244 264162 : if (source->IsRegister() && destination->IsRegister()) {
245 : // Swap two general-purpose registers.
246 132045 : Register src = cgen_->ToRegister(source);
247 132045 : Register dst = cgen_->ToRegister(destination);
248 396351 : __ movp(kScratchRegister, src);
249 264090 : __ movp(src, dst);
250 264090 : __ movp(dst, kScratchRegister);
251 :
252 144 : } else if ((source->IsRegister() && destination->IsStackSlot()) ||
253 4 : (source->IsStackSlot() && destination->IsRegister())) {
254 : // Swap a general-purpose register and a stack slot.
255 : Register reg =
256 4 : cgen_->ToRegister(source->IsRegister() ? source : destination);
257 : Operand mem =
258 4 : cgen_->ToOperand(source->IsRegister() ? destination : source);
259 8 : __ movp(kScratchRegister, mem);
260 8 : __ movp(mem, reg);
261 8 : __ movp(reg, kScratchRegister);
262 :
263 136 : } else if ((source->IsStackSlot() && destination->IsStackSlot()) ||
264 0 : (source->IsDoubleStackSlot() && destination->IsDoubleStackSlot())) {
265 : // Swap two stack slots or two double stack slots.
266 0 : Operand src = cgen_->ToOperand(source);
267 0 : Operand dst = cgen_->ToOperand(destination);
268 0 : __ Movsd(kScratchDoubleReg, src);
269 0 : __ movp(kScratchRegister, dst);
270 0 : __ Movsd(dst, kScratchDoubleReg);
271 0 : __ movp(src, kScratchRegister);
272 :
273 136 : } else if (source->IsDoubleRegister() && destination->IsDoubleRegister()) {
274 : // Swap two double registers.
275 68 : XMMRegister source_reg = cgen_->ToDoubleRegister(source);
276 68 : XMMRegister destination_reg = cgen_->ToDoubleRegister(destination);
277 136 : __ Movapd(kScratchDoubleReg, source_reg);
278 136 : __ Movapd(source_reg, destination_reg);
279 136 : __ Movapd(destination_reg, kScratchDoubleReg);
280 :
281 0 : } else if (source->IsDoubleRegister() || destination->IsDoubleRegister()) {
282 : // Swap a double register and a double stack slot.
283 : DCHECK((source->IsDoubleRegister() && destination->IsDoubleStackSlot()) ||
284 : (source->IsDoubleStackSlot() && destination->IsDoubleRegister()));
285 : XMMRegister reg = cgen_->ToDoubleRegister(source->IsDoubleRegister()
286 : ? source
287 0 : : destination);
288 0 : LOperand* other = source->IsDoubleRegister() ? destination : source;
289 : DCHECK(other->IsDoubleStackSlot());
290 0 : Operand other_operand = cgen_->ToOperand(other);
291 0 : __ Movapd(kScratchDoubleReg, reg);
292 0 : __ Movsd(reg, other_operand);
293 0 : __ Movsd(other_operand, kScratchDoubleReg);
294 :
295 : } else {
296 : // No other combinations are possible.
297 0 : UNREACHABLE();
298 : }
299 :
300 : // The swap of source and destination has executed a move from source to
301 : // destination.
302 : moves_[index].Eliminate();
303 :
304 : // Any unperformed (including pending) move with a source of either
305 : // this move's source or destination needs to have their source
306 : // changed to reflect the state of affairs after the swap.
307 1295344 : for (int i = 0; i < moves_.length(); ++i) {
308 515555 : LMoveOperands other_move = moves_[i];
309 515555 : if (other_move.Blocks(source)) {
310 : moves_[i].set_source(destination);
311 515544 : } else if (other_move.Blocks(destination)) {
312 : moves_[i].set_source(source);
313 : }
314 : }
315 132117 : }
316 :
317 : #undef __
318 :
319 : } // namespace internal
320 : } // namespace v8
321 :
322 : #endif // V8_TARGET_ARCH_X64
|