1// Copyright 2011 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#if V8_TARGET_ARCH_IA32
31
32#include "ia32/lithium-gap-resolver-ia32.h"
33#include "ia32/lithium-codegen-ia32.h"
34
35namespace v8 {
36namespace internal {
37
38LGapResolver::LGapResolver(LCodeGen* owner)
39    : cgen_(owner),
40      moves_(32, owner->zone()),
41      source_uses_(),
42      destination_uses_(),
43      spilled_register_(-1) {}
44
45
46void LGapResolver::Resolve(LParallelMove* parallel_move) {
47  ASSERT(HasBeenReset());
48  // Build up a worklist of moves.
49  BuildInitialMoveList(parallel_move);
50
51  for (int i = 0; i < moves_.length(); ++i) {
52    LMoveOperands move = moves_[i];
53    // Skip constants to perform them last.  They don't block other moves
54    // and skipping such moves with register destinations keeps those
55    // registers free for the whole algorithm.
56    if (!move.IsEliminated() && !move.source()->IsConstantOperand()) {
57      PerformMove(i);
58    }
59  }
60
61  // Perform the moves with constant sources.
62  for (int i = 0; i < moves_.length(); ++i) {
63    if (!moves_[i].IsEliminated()) {
64      ASSERT(moves_[i].source()->IsConstantOperand());
65      EmitMove(i);
66    }
67  }
68
69  Finish();
70  ASSERT(HasBeenReset());
71}
72
73
74void LGapResolver::BuildInitialMoveList(LParallelMove* parallel_move) {
75  // Perform a linear sweep of the moves to add them to the initial list of
76  // moves to perform, ignoring any move that is redundant (the source is
77  // the same as the destination, the destination is ignored and
78  // unallocated, or the move was already eliminated).
79  const ZoneList<LMoveOperands>* moves = parallel_move->move_operands();
80  for (int i = 0; i < moves->length(); ++i) {
81    LMoveOperands move = moves->at(i);
82    if (!move.IsRedundant()) AddMove(move);
83  }
84  Verify();
85}
86
87
88void LGapResolver::PerformMove(int index) {
89  // Each call to this function performs a move and deletes it from the move
90  // graph.  We first recursively perform any move blocking this one.  We
91  // mark a move as "pending" on entry to PerformMove in order to detect
92  // cycles in the move graph.  We use operand swaps to resolve cycles,
93  // which means that a call to PerformMove could change any source operand
94  // in the move graph.
95
96  ASSERT(!moves_[index].IsPending());
97  ASSERT(!moves_[index].IsRedundant());
98
99  // Clear this move's destination to indicate a pending move.  The actual
100  // destination is saved on the side.
101  ASSERT(moves_[index].source() != NULL);  // Or else it will look eliminated.
102  LOperand* destination = moves_[index].destination();
103  moves_[index].set_destination(NULL);
104
105  // Perform a depth-first traversal of the move graph to resolve
106  // dependencies.  Any unperformed, unpending move with a source the same
107  // as this one's destination blocks this one so recursively perform all
108  // such moves.
109  for (int i = 0; i < moves_.length(); ++i) {
110    LMoveOperands other_move = moves_[i];
111    if (other_move.Blocks(destination) && !other_move.IsPending()) {
112      // Though PerformMove can change any source operand in the move graph,
113      // this call cannot create a blocking move via a swap (this loop does
114      // not miss any).  Assume there is a non-blocking move with source A
115      // and this move is blocked on source B and there is a swap of A and
116      // B.  Then A and B must be involved in the same cycle (or they would
117      // not be swapped).  Since this move's destination is B and there is
118      // only a single incoming edge to an operand, this move must also be
119      // involved in the same cycle.  In that case, the blocking move will
120      // be created but will be "pending" when we return from PerformMove.
121      PerformMove(i);
122    }
123  }
124
125  // We are about to resolve this move and don't need it marked as
126  // pending, so restore its destination.
127  moves_[index].set_destination(destination);
128
129  // This move's source may have changed due to swaps to resolve cycles and
130  // so it may now be the last move in the cycle.  If so remove it.
131  if (moves_[index].source()->Equals(destination)) {
132    RemoveMove(index);
133    return;
134  }
135
136  // The move may be blocked on a (at most one) pending move, in which case
137  // we have a cycle.  Search for such a blocking move and perform a swap to
138  // resolve it.
139  for (int i = 0; i < moves_.length(); ++i) {
140    LMoveOperands other_move = moves_[i];
141    if (other_move.Blocks(destination)) {
142      ASSERT(other_move.IsPending());
143      EmitSwap(index);
144      return;
145    }
146  }
147
148  // This move is not blocked.
149  EmitMove(index);
150}
151
152
153void LGapResolver::AddMove(LMoveOperands move) {
154  LOperand* source = move.source();
155  if (source->IsRegister()) ++source_uses_[source->index()];
156
157  LOperand* destination = move.destination();
158  if (destination->IsRegister()) ++destination_uses_[destination->index()];
159
160  moves_.Add(move, cgen_->zone());
161}
162
163
164void LGapResolver::RemoveMove(int index) {
165  LOperand* source = moves_[index].source();
166  if (source->IsRegister()) {
167    --source_uses_[source->index()];
168    ASSERT(source_uses_[source->index()] >= 0);
169  }
170
171  LOperand* destination = moves_[index].destination();
172  if (destination->IsRegister()) {
173    --destination_uses_[destination->index()];
174    ASSERT(destination_uses_[destination->index()] >= 0);
175  }
176
177  moves_[index].Eliminate();
178}
179
180
181int LGapResolver::CountSourceUses(LOperand* operand) {
182  int count = 0;
183  for (int i = 0; i < moves_.length(); ++i) {
184    if (!moves_[i].IsEliminated() && moves_[i].source()->Equals(operand)) {
185      ++count;
186    }
187  }
188  return count;
189}
190
191
192Register LGapResolver::GetFreeRegisterNot(Register reg) {
193  int skip_index = reg.is(no_reg) ? -1 : Register::ToAllocationIndex(reg);
194  for (int i = 0; i < Register::NumAllocatableRegisters(); ++i) {
195    if (source_uses_[i] == 0 && destination_uses_[i] > 0 && i != skip_index) {
196      return Register::FromAllocationIndex(i);
197    }
198  }
199  return no_reg;
200}
201
202
203bool LGapResolver::HasBeenReset() {
204  if (!moves_.is_empty()) return false;
205  if (spilled_register_ >= 0) return false;
206
207  for (int i = 0; i < Register::NumAllocatableRegisters(); ++i) {
208    if (source_uses_[i] != 0) return false;
209    if (destination_uses_[i] != 0) return false;
210  }
211  return true;
212}
213
214
215void LGapResolver::Verify() {
216#ifdef ENABLE_SLOW_ASSERTS
217  // No operand should be the destination for more than one move.
218  for (int i = 0; i < moves_.length(); ++i) {
219    LOperand* destination = moves_[i].destination();
220    for (int j = i + 1; j < moves_.length(); ++j) {
221      SLOW_ASSERT(!destination->Equals(moves_[j].destination()));
222    }
223  }
224#endif
225}
226
227
228#define __ ACCESS_MASM(cgen_->masm())
229
230void LGapResolver::Finish() {
231  if (spilled_register_ >= 0) {
232    __ pop(Register::FromAllocationIndex(spilled_register_));
233    spilled_register_ = -1;
234  }
235  moves_.Rewind(0);
236}
237
238
239void LGapResolver::EnsureRestored(LOperand* operand) {
240  if (operand->IsRegister() && operand->index() == spilled_register_) {
241    __ pop(Register::FromAllocationIndex(spilled_register_));
242    spilled_register_ = -1;
243  }
244}
245
246
247Register LGapResolver::EnsureTempRegister() {
248  // 1. We may have already spilled to create a temp register.
249  if (spilled_register_ >= 0) {
250    return Register::FromAllocationIndex(spilled_register_);
251  }
252
253  // 2. We may have a free register that we can use without spilling.
254  Register free = GetFreeRegisterNot(no_reg);
255  if (!free.is(no_reg)) return free;
256
257  // 3. Prefer to spill a register that is not used in any remaining move
258  // because it will not need to be restored until the end.
259  for (int i = 0; i < Register::NumAllocatableRegisters(); ++i) {
260    if (source_uses_[i] == 0 && destination_uses_[i] == 0) {
261      Register scratch = Register::FromAllocationIndex(i);
262      __ push(scratch);
263      spilled_register_ = i;
264      return scratch;
265    }
266  }
267
268  // 4. Use an arbitrary register.  Register 0 is as arbitrary as any other.
269  Register scratch = Register::FromAllocationIndex(0);
270  __ push(scratch);
271  spilled_register_ = 0;
272  return scratch;
273}
274
275
276void LGapResolver::EmitMove(int index) {
277  LOperand* source = moves_[index].source();
278  LOperand* destination = moves_[index].destination();
279  EnsureRestored(source);
280  EnsureRestored(destination);
281
282  // Dispatch on the source and destination operand kinds.  Not all
283  // combinations are possible.
284  if (source->IsRegister()) {
285    ASSERT(destination->IsRegister() || destination->IsStackSlot());
286    Register src = cgen_->ToRegister(source);
287    Operand dst = cgen_->ToOperand(destination);
288    __ mov(dst, src);
289
290  } else if (source->IsStackSlot()) {
291    ASSERT(destination->IsRegister() || destination->IsStackSlot());
292    Operand src = cgen_->ToOperand(source);
293    if (destination->IsRegister()) {
294      Register dst = cgen_->ToRegister(destination);
295      __ mov(dst, src);
296    } else {
297      // Spill on demand to use a temporary register for memory-to-memory
298      // moves.
299      Register tmp = EnsureTempRegister();
300      Operand dst = cgen_->ToOperand(destination);
301      __ mov(tmp, src);
302      __ mov(dst, tmp);
303    }
304
305  } else if (source->IsConstantOperand()) {
306    LConstantOperand* constant_source = LConstantOperand::cast(source);
307    if (destination->IsRegister()) {
308      Register dst = cgen_->ToRegister(destination);
309      Representation r = cgen_->IsSmi(constant_source)
310          ? Representation::Smi() : Representation::Integer32();
311      if (cgen_->IsInteger32(constant_source)) {
312        __ Set(dst, cgen_->ToImmediate(constant_source, r));
313      } else {
314        __ LoadObject(dst, cgen_->ToHandle(constant_source));
315      }
316    } else if (destination->IsDoubleRegister()) {
317      double v = cgen_->ToDouble(constant_source);
318      uint64_t int_val = BitCast<uint64_t, double>(v);
319      int32_t lower = static_cast<int32_t>(int_val);
320      int32_t upper = static_cast<int32_t>(int_val >> kBitsPerInt);
321      if (CpuFeatures::IsSupported(SSE2)) {
322        CpuFeatureScope scope(cgen_->masm(), SSE2);
323        XMMRegister dst = cgen_->ToDoubleRegister(destination);
324        if (int_val == 0) {
325          __ xorps(dst, dst);
326        } else {
327          __ push(Immediate(upper));
328          __ push(Immediate(lower));
329          __ movdbl(dst, Operand(esp, 0));
330          __ add(esp, Immediate(kDoubleSize));
331        }
332      } else {
333        __ push(Immediate(upper));
334        __ push(Immediate(lower));
335        X87Register dst = cgen_->ToX87Register(destination);
336        cgen_->X87Mov(dst, MemOperand(esp, 0));
337        __ add(esp, Immediate(kDoubleSize));
338      }
339    } else {
340      ASSERT(destination->IsStackSlot());
341      Operand dst = cgen_->ToOperand(destination);
342      Representation r = cgen_->IsSmi(constant_source)
343          ? Representation::Smi() : Representation::Integer32();
344      if (cgen_->IsInteger32(constant_source)) {
345        __ Set(dst, cgen_->ToImmediate(constant_source, r));
346      } else {
347        Register tmp = EnsureTempRegister();
348        __ LoadObject(tmp, cgen_->ToHandle(constant_source));
349        __ mov(dst, tmp);
350      }
351    }
352
353  } else if (source->IsDoubleRegister()) {
354    if (CpuFeatures::IsSupported(SSE2)) {
355      CpuFeatureScope scope(cgen_->masm(), SSE2);
356      XMMRegister src = cgen_->ToDoubleRegister(source);
357      if (destination->IsDoubleRegister()) {
358        XMMRegister dst = cgen_->ToDoubleRegister(destination);
359        __ movaps(dst, src);
360      } else {
361        ASSERT(destination->IsDoubleStackSlot());
362        Operand dst = cgen_->ToOperand(destination);
363        __ movdbl(dst, src);
364      }
365    } else {
366      // load from the register onto the stack, store in destination, which must
367      // be a double stack slot in the non-SSE2 case.
368      ASSERT(destination->IsDoubleStackSlot());
369      Operand dst = cgen_->ToOperand(destination);
370      X87Register src = cgen_->ToX87Register(source);
371      cgen_->X87Mov(dst, src);
372    }
373  } else if (source->IsDoubleStackSlot()) {
374    if (CpuFeatures::IsSupported(SSE2)) {
375      CpuFeatureScope scope(cgen_->masm(), SSE2);
376      ASSERT(destination->IsDoubleRegister() ||
377             destination->IsDoubleStackSlot());
378      Operand src = cgen_->ToOperand(source);
379      if (destination->IsDoubleRegister()) {
380        XMMRegister dst = cgen_->ToDoubleRegister(destination);
381        __ movdbl(dst, src);
382      } else {
383        // We rely on having xmm0 available as a fixed scratch register.
384        Operand dst = cgen_->ToOperand(destination);
385        __ movdbl(xmm0, src);
386        __ movdbl(dst, xmm0);
387      }
388    } else {
389      // load from the stack slot on top of the floating point stack, and then
390      // store in destination. If destination is a double register, then it
391      // represents the top of the stack and nothing needs to be done.
392      if (destination->IsDoubleStackSlot()) {
393        Register tmp = EnsureTempRegister();
394        Operand src0 = cgen_->ToOperand(source);
395        Operand src1 = cgen_->HighOperand(source);
396        Operand dst0 = cgen_->ToOperand(destination);
397        Operand dst1 = cgen_->HighOperand(destination);
398        __ mov(tmp, src0);  // Then use tmp to copy source to destination.
399        __ mov(dst0, tmp);
400        __ mov(tmp, src1);
401        __ mov(dst1, tmp);
402      } else {
403        Operand src = cgen_->ToOperand(source);
404        X87Register dst = cgen_->ToX87Register(destination);
405        cgen_->X87Mov(dst, src);
406      }
407    }
408  } else {
409    UNREACHABLE();
410  }
411
412  RemoveMove(index);
413}
414
415
416void LGapResolver::EmitSwap(int index) {
417  LOperand* source = moves_[index].source();
418  LOperand* destination = moves_[index].destination();
419  EnsureRestored(source);
420  EnsureRestored(destination);
421
422  // Dispatch on the source and destination operand kinds.  Not all
423  // combinations are possible.
424  if (source->IsRegister() && destination->IsRegister()) {
425    // Register-register.
426    Register src = cgen_->ToRegister(source);
427    Register dst = cgen_->ToRegister(destination);
428    __ xchg(dst, src);
429
430  } else if ((source->IsRegister() && destination->IsStackSlot()) ||
431             (source->IsStackSlot() && destination->IsRegister())) {
432    // Register-memory.  Use a free register as a temp if possible.  Do not
433    // spill on demand because the simple spill implementation cannot avoid
434    // spilling src at this point.
435    Register tmp = GetFreeRegisterNot(no_reg);
436    Register reg =
437        cgen_->ToRegister(source->IsRegister() ? source : destination);
438    Operand mem =
439        cgen_->ToOperand(source->IsRegister() ? destination : source);
440    if (tmp.is(no_reg)) {
441      __ xor_(reg, mem);
442      __ xor_(mem, reg);
443      __ xor_(reg, mem);
444    } else {
445      __ mov(tmp, mem);
446      __ mov(mem, reg);
447      __ mov(reg, tmp);
448    }
449
450  } else if (source->IsStackSlot() && destination->IsStackSlot()) {
451    // Memory-memory.  Spill on demand to use a temporary.  If there is a
452    // free register after that, use it as a second temporary.
453    Register tmp0 = EnsureTempRegister();
454    Register tmp1 = GetFreeRegisterNot(tmp0);
455    Operand src = cgen_->ToOperand(source);
456    Operand dst = cgen_->ToOperand(destination);
457    if (tmp1.is(no_reg)) {
458      // Only one temp register available to us.
459      __ mov(tmp0, dst);
460      __ xor_(tmp0, src);
461      __ xor_(src, tmp0);
462      __ xor_(tmp0, src);
463      __ mov(dst, tmp0);
464    } else {
465      __ mov(tmp0, dst);
466      __ mov(tmp1, src);
467      __ mov(dst, tmp1);
468      __ mov(src, tmp0);
469    }
470  } else if (source->IsDoubleRegister() && destination->IsDoubleRegister()) {
471    CpuFeatureScope scope(cgen_->masm(), SSE2);
472    // XMM register-register swap. We rely on having xmm0
473    // available as a fixed scratch register.
474    XMMRegister src = cgen_->ToDoubleRegister(source);
475    XMMRegister dst = cgen_->ToDoubleRegister(destination);
476    __ movaps(xmm0, src);
477    __ movaps(src, dst);
478    __ movaps(dst, xmm0);
479  } else if (source->IsDoubleRegister() || destination->IsDoubleRegister()) {
480    CpuFeatureScope scope(cgen_->masm(), SSE2);
481    // XMM register-memory swap.  We rely on having xmm0
482    // available as a fixed scratch register.
483    ASSERT(source->IsDoubleStackSlot() || destination->IsDoubleStackSlot());
484    XMMRegister reg = cgen_->ToDoubleRegister(source->IsDoubleRegister()
485                                              ? source
486                                              : destination);
487    Operand other =
488        cgen_->ToOperand(source->IsDoubleRegister() ? destination : source);
489    __ movdbl(xmm0, other);
490    __ movdbl(other, reg);
491    __ movdbl(reg, Operand(xmm0));
492  } else if (source->IsDoubleStackSlot() && destination->IsDoubleStackSlot()) {
493    CpuFeatureScope scope(cgen_->masm(), SSE2);
494    // Double-width memory-to-memory.  Spill on demand to use a general
495    // purpose temporary register and also rely on having xmm0 available as
496    // a fixed scratch register.
497    Register tmp = EnsureTempRegister();
498    Operand src0 = cgen_->ToOperand(source);
499    Operand src1 = cgen_->HighOperand(source);
500    Operand dst0 = cgen_->ToOperand(destination);
501    Operand dst1 = cgen_->HighOperand(destination);
502    __ movdbl(xmm0, dst0);  // Save destination in xmm0.
503    __ mov(tmp, src0);  // Then use tmp to copy source to destination.
504    __ mov(dst0, tmp);
505    __ mov(tmp, src1);
506    __ mov(dst1, tmp);
507    __ movdbl(src0, xmm0);
508
509  } else {
510    // No other combinations are possible.
511    UNREACHABLE();
512  }
513
514  // The swap of source and destination has executed a move from source to
515  // destination.
516  RemoveMove(index);
517
518  // Any unperformed (including pending) move with a source of either
519  // this move's source or destination needs to have their source
520  // changed to reflect the state of affairs after the swap.
521  for (int i = 0; i < moves_.length(); ++i) {
522    LMoveOperands other_move = moves_[i];
523    if (other_move.Blocks(source)) {
524      moves_[i].set_source(destination);
525    } else if (other_move.Blocks(destination)) {
526      moves_[i].set_source(source);
527    }
528  }
529
530  // In addition to swapping the actual uses as sources, we need to update
531  // the use counts.
532  if (source->IsRegister() && destination->IsRegister()) {
533    int temp = source_uses_[source->index()];
534    source_uses_[source->index()] = source_uses_[destination->index()];
535    source_uses_[destination->index()] = temp;
536  } else if (source->IsRegister()) {
537    // We don't have use counts for non-register operands like destination.
538    // Compute those counts now.
539    source_uses_[source->index()] = CountSourceUses(source);
540  } else if (destination->IsRegister()) {
541    source_uses_[destination->index()] = CountSourceUses(destination);
542  }
543}
544
545#undef __
546
547} }  // namespace v8::internal
548
549#endif  // V8_TARGET_ARCH_IA32
550