Change the algorithm and generated code for parallel moves on IA32.

src/ia32/lithium-gap-resolver-ia32.cc

+// Copyright 2011 the V8 project authors. All rights reserved.
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are
+// met:
+//
+//     * Redistributions of source code must retain the above copyright
+//       notice, this list of conditions and the following disclaimer.
+//     * Redistributions in binary form must reproduce the above
+//       copyright notice, this list of conditions and the following
+//       disclaimer in the documentation and/or other materials provided
+//       with the distribution.
+//     * Neither the name of Google Inc. nor the names of its
+//       contributors may be used to endorse or promote products derived
+//       from this software without specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+#include "ia32/lithium-gap-resolver-ia32.h"
+#include "ia32/lithium-codegen-ia32.h"
+
+namespace v8 {
+namespace internal {
+
+LGapResolver::LGapResolver(LCodeGen* owner)
+    : cgen_(owner), moves_(32), spilled_register_(-1) {
+  for (int i = 0; i < Register::kNumAllocatableRegisters; ++i) {
+    general_source_uses_[i] = 0;
+    general_destination_uses_[i] = 0;
+  }
+  for (int i = 0; i < DoubleRegister::kNumAllocatableRegisters; ++i) {
+    double_source_uses_[i] = 0;
+    double_destination_uses_[i] = 0;
+  }
+}
+
+
+void LGapResolver::Resolve(LParallelMove* parallel_move) {
+  ASSERT(HasBeenReset());
+  // Build up a worklist of moves.
+  BuildInitialMoveList(parallel_move);
+
+  for (int i = moves_.length() - 1; i >= 0; --i) {
+    LMoveOperands move = moves_[i];
+    // Skip constants to perform them last.  They don't block other moves
+    // and skipping such moves with register destinations keeps those
+    // registers free for the whole algorithm.
+    if (!move.IsEliminated() && !move.source()->IsConstantOperand()) {
+      PerformMove(i);
+    }
+  }
+
+  // Perform the moves with constant sources.
+  for (int i = moves_.length() - 1; i >= 0; --i) {
+    if (!moves_[i].IsEliminated()) {

[fschneider, 2011/01/17 09:44:16]

Not sure: can a move with a constant source operand be eliminated by PerformMove
at all?

[Kevin Millikin (Chromium), 2011/01/17 10:13:08]

Only if it's the move passed to PerformMove.

+      ASSERT(moves_[i].source()->IsConstantOperand());
+      EmitMove(i);
+    }
+  }
+
+  Finish();
+  ASSERT(HasBeenReset());
+}
+
+
+void LGapResolver::BuildInitialMoveList(LParallelMove* parallel_move) {
+  // Perform a linear sweep of the moves to add them to the initial list of
+  // moves to perform, ignoring any move that is redundant (the source is
+  // the same as the destination, the destination is ignored and
+  // unallocated, or the move was already eliminated).
+  //
+  // Inform the move assembler of each move that will eventually be
+  // performed so it can track the registers used.
+  const ZoneList<LMoveOperands>* moves = parallel_move->move_operands();
+  for (int i = moves->length() - 1; i >= 0; --i) {
+    LMoveOperands move = moves->at(i);
+    if (!move.IsRedundant()) AddMove(move);
+  }

[fschneider, 2011/01/17 09:44:16]

How about a slot assert that verifies the move-graph property that no operand is
used as a destination more than once?

[Kevin Millikin (Chromium), 2011/01/17 10:13:08]

Good idea.  I will add it.

+}
+
+
+void LGapResolver::PerformMove(int index) {
+  // Each call to this function performs a move and deletes it from the move
+  // graph.  We first recursively perform any move blocking this one.  We
+  // mark a move as "pending" on entry to PerformMove in order to detect
+  // cycles in the move graph.  We use operand swaps to resolve cycles,
+  // which means that a call to PerformMove could change any source operand
+  // in the move graph.
+
+  ASSERT(!moves_[index].IsRedundant());
+
+  // Clear this move's destination to indicate a pending move.  The actual
+  // destination is saved on the side.
+  ASSERT(moves_[index].source() != NULL);  // Or else it will look eliminated.
+  LOperand* destination = moves_[index].destination();
+  moves_[index].set_destination(NULL);
+
+  // Perform a depth-first traversal of the move graph to resolve
+  // dependencies.  Any unperformed, unpending move with a source the same
+  // as this one's destination blocks this one so recursively perform all
+  // such moves.
+  for (int i = moves_.length() - 1; i >= 0; --i) {
+    LMoveOperands other_move = moves_[i];
+    if (other_move.Blocks(destination) && !other_move.IsPending()) {
+      // Though PerformMove can change any source operand in the move graph,
+      // this call cannot create a blocking move via a swap (this loop does
+      // not miss any).  Assume there is a non-blocking move with source A
+      // and this move is blocked on source B and there is a swap of A and
+      // B.  Then A and B must be involved in the same cycle (or they would
+      // not be swapped).  Since this move's destination is B and there is
+      // only a single incoming edge to an operand, this move must also be
+      // involved in the same cycle.  In that case, the blocking move will
+      // be created but will be "pending" when we return from PerformMove.
+      PerformMove(i);
+    }
+  }
+
+  // We are about to resolve this move and don't need it marked as
+  // pending, so restore its destination.
+  moves_[index].set_destination(destination);
+
+  // This move's source may have changed due to swaps to resolve cycles and
+  // so it may now be the last move in the cycle.  If so remove it.
+  if (moves_[index].source()->Equals(destination)) {
+    RemoveMove(index);
+    return;
+  }
+
+  // The move may be blocked on a (at most one) pending move, in which case
+  // we have a cycle.  Search for such a blocking move and perform a swap to
+  // resolve it.
+  for (int i = moves_.length() - 1; i >= 0; --i) {
+    LMoveOperands other_move = moves_[i];
+    if (other_move.Blocks(destination)) {
+      ASSERT(other_move.IsPending());
+      EmitSwap(index);
+      return;
+    }
+  }
+
+  // This move is not blocked.
+  EmitMove(index);
+}
+
+
+void LGapResolver::AddMove(LMoveOperands move) {
+  LOperand* source = move.source();
+  if (source->IsRegister()) {
+    ++general_source_uses_[source->index()];
+  } else if (source->IsDoubleRegister()) {
+    ++double_source_uses_[source->index()];
+  }
+
+  LOperand* destination = move.destination();
+  if (destination->IsRegister()) {
+    ++general_destination_uses_[destination->index()];
+  } else if (destination->IsDoubleRegister()) {
+    ++double_destination_uses_[destination->index()];
+  }
+
+  moves_.Add(move);
+}
+
+
+void LGapResolver::RemoveMove(int index) {
+  LOperand* source = moves_[index].source();
+  if (source->IsRegister()) {
+    --general_source_uses_[source->index()];
+    ASSERT(general_source_uses_[source->index()] >= 0);
+  } else if (source->IsDoubleRegister()) {
+    --double_source_uses_[source->index()];
+    ASSERT(double_source_uses_[source->index()] >= 0);
+  }
+
+  LOperand* destination = moves_[index].destination();
+  if (destination->IsRegister()) {
+    --general_destination_uses_[destination->index()];
+    ASSERT(general_destination_uses_[destination->index()] >= 0);
+  } else if (destination->IsDoubleRegister()) {
+    --double_destination_uses_[destination->index()];
+    ASSERT(double_destination_uses_[destination->index()] >= 0);
+  }
+
+  moves_[index].Eliminate();
+}
+
+
+int LGapResolver::CountSourceUses(LOperand* operand) {
+  int count = 0;
+  for (int i = moves_.length() - 1; i >= 0; --i) {
+    if (!moves_[i].IsEliminated() && moves_[i].source()->Equals(operand)) {
+      ++count;
+    }
+  }
+  return count;
+}
+
+
+Register LGapResolver::GetFreeRegisterNot(Register reg) {
+  int skip_index = reg.is(no_reg) ? -1 : Register::ToAllocationIndex(reg);
+  for (int i = 0; i < Register::kNumAllocatableRegisters; ++i) {
+    if (general_source_uses_[i] == 0 &&
+        general_destination_uses_[i] > 0 &&
+        i != skip_index) {
+      return Register::FromAllocationIndex(i);
+    }
+  }
+  return no_reg;
+}
+
+
+bool LGapResolver::HasBeenReset() {
+  if (!moves_.is_empty()) return false;
+  if (spilled_register_ >= 0) return false;
+
+  for (int i = 0; i < Register::kNumAllocatableRegisters; ++i) {
+    if (general_source_uses_[i] != 0) return false;
+    if (general_destination_uses_[i] != 0) return false;
+  }
+  for (int i = 0; i < DoubleRegister::kNumAllocatableRegisters; ++i) {
+    if (double_source_uses_[i] != 0) return false;
+    if (double_destination_uses_[i] != 0) return false;
+  }
+  return true;
+}
+
+
+#define __ ACCESS_MASM(cgen_->masm())
+
+void LGapResolver::Finish() {
+  if (spilled_register_ >= 0) {
+    __ pop(Register::FromAllocationIndex(spilled_register_));
+    spilled_register_ = -1;
+  }
+  moves_.Rewind(0);
+}
+
+
+void LGapResolver::EnsureRestored(LOperand* operand) {
+  if (operand->IsRegister() && operand->index() == spilled_register_) {
+    __ pop(Register::FromAllocationIndex(spilled_register_));
+    spilled_register_ = -1;
+  }
+}
+
+
+Register LGapResolver::EnsureTempRegister() {
+  // 1. We may have already spilled to create a temp register.
+  if (spilled_register_ >= 0) {
+    return Register::FromAllocationIndex(spilled_register_);
+  }
+
+  // 2. We may have a free register that we can use without spilling.
+  Register free = GetFreeRegisterNot(no_reg);
+  if (!free.is(no_reg)) return free;
+
+  // 3. Prefer to spill a register that is not used in any remaining move
+  // because it will not need to be restored until the end.
+  for (int i = 0; i < Register::kNumAllocatableRegisters; ++i) {
+    if (general_source_uses_[i] == 0 && general_destination_uses_[i] == 0) {
+      Register scratch = Register::FromAllocationIndex(i);
+      __ push(scratch);
+      spilled_register_ = i;
+      return scratch;
+    }
+  }
+
+  // 4. Use an arbitrary register.  Register 0 is as arbitrary as any other.
+  Register scratch = Register::FromAllocationIndex(0);
+  __ push(scratch);
+  spilled_register_ = 0;
+  return scratch;
+}
+
+
+void LGapResolver::EmitMove(int index) {
+  LOperand* source = moves_[index].source();
+  LOperand* destination = moves_[index].destination();
+  EnsureRestored(source);
+  EnsureRestored(destination);
+
+  // Dispatch on the source and destination operand kinds.  Not all
+  // combinations are possible.
+  if (source->IsRegister()) {
+    ASSERT(destination->IsRegister() || destination->IsStackSlot());
+    Register src = cgen_->ToRegister(source);
+    Operand dst = cgen_->ToOperand(destination);
+    __ mov(dst, src);
+
+  } else if (source->IsStackSlot()) {
+    ASSERT(destination->IsRegister() || destination->IsStackSlot());
+    Operand src = cgen_->ToOperand(source);
+    if (destination->IsRegister()) {
+      Register dst = cgen_->ToRegister(destination);
+      __ mov(dst, src);
+    } else {
+      // Spill on demand to use a temporary register for memory-to-memory
+      // moves.
+      Register tmp = EnsureTempRegister();
+      Operand dst = cgen_->ToOperand(destination);
+      __ mov(tmp, src);
+      __ mov(dst, tmp);
+    }
+
+  } else if (source->IsConstantOperand()) {
+    ASSERT(destination->IsRegister() || destination->IsStackSlot());
+    Immediate src = cgen_->ToImmediate(source);
+    Operand dst = cgen_->ToOperand(destination);
+    __ mov(dst, src);
+
+  } else if (source->IsDoubleRegister()) {
+    ASSERT(destination->IsDoubleRegister() ||
+           destination->IsDoubleStackSlot());
+    XMMRegister src = cgen_->ToDoubleRegister(source);
+    Operand dst = cgen_->ToOperand(destination);
+    __ movdbl(dst, src);
+
+  } else if (source->IsDoubleStackSlot()) {
+    ASSERT(destination->IsDoubleRegister() ||
+           destination->IsDoubleStackSlot());
+    Operand src = cgen_->ToOperand(source);
+    if (destination->IsDoubleRegister()) {
+      XMMRegister dst = cgen_->ToDoubleRegister(destination);
+      __ movdbl(dst, src);
+    } else {
+      // We rely on having xmm0 available as a fixed scratch register.
+      Operand dst = cgen_->ToOperand(destination);
+      __ movdbl(xmm0, src);
+      __ movdbl(dst, xmm0);
+    }
+
+  } else {
+    UNREACHABLE();
+  }
+
+  RemoveMove(index);
+}
+
+
+void LGapResolver::EmitSwap(int index) {
+  LOperand* source = moves_[index].source();
+  LOperand* destination = moves_[index].destination();
+  EnsureRestored(source);
+  EnsureRestored(destination);
+
+  // Dispatch on the source and destination operand kinds.  Not all
+  // combinations are possible.
+  if (source->IsRegister() && destination->IsRegister()) {
+    // Register-register.
+    Register src = cgen_->ToRegister(source);
+    Register dst = cgen_->ToRegister(destination);
+    __ xchg(dst, src);
+
+  } else if ((source->IsRegister() && destination->IsStackSlot()) ||
+             (source->IsStackSlot() && destination->IsRegister())) {
+    // Register-memory.  Use a free register as a temp if possible.  Do not
+    // spill on demand because the simple spill implementation cannot avoid
+    // spilling src at this point.  Memory-to-memory swaps are a rare case.

[fschneider, 2011/01/17 09:44:16]

The comment mentions mem-to-mem swaps which are not handled here, but further
below.

[Kevin Millikin (Chromium), 2011/01/17 10:13:08]

I will fix it.

+    Register tmp = GetFreeRegisterNot(no_reg);
+    Register reg =
+        cgen_->ToRegister(source->IsRegister() ? source : destination);
+    Operand mem =
+        cgen_->ToOperand(source->IsRegister() ? destination : source);
+    if (tmp.is(no_reg)) {
+      __ xor_(reg, mem);
+      __ xor_(mem, reg);
+      __ xor_(reg, mem);
+    } else {
+      __ mov(tmp, mem);
+      __ mov(mem, reg);
+      __ mov(reg, tmp);
+    }
+
+  } else if (source->IsStackSlot() && destination->IsStackSlot()) {
+    // Memory-memory.  Spill on demand to use a temporary.  If there is a
+    // free register after that, use it as a second temporary.
+    Register tmp0 = EnsureTempRegister();
+    Register tmp1 = GetFreeRegisterNot(tmp0);
+    Operand src = cgen_->ToOperand(source);
+    Operand dst = cgen_->ToOperand(destination);
+    if (tmp1.is(no_reg)) {
+      // Only one temp register available to us.
+      __ mov(tmp0, dst);
+      __ xor_(tmp0, src);
+      __ xor_(src, tmp0);
+      __ xor_(tmp0, src);
+      __ mov(dst, tmp0);
+    } else {
+      __ mov(tmp0, dst);
+      __ mov(tmp1, src);
+      __ mov(dst, tmp1);
+      __ mov(src, tmp0);
+    }
+
+  } else if (source->IsDoubleRegister() || destination->IsDoubleRegister()) {
+    // XMM register-register or register-memory.  We rely on having xmm0
+    // available as a fixed scratch register.
+    ASSERT(source->IsDoubleRegister() || source->IsDoubleStackSlot());
+    ASSERT(destination->IsDoubleRegister() ||
+           destination->IsDoubleStackSlot());
+    XMMRegister reg = cgen_->ToDoubleRegister(source->IsDoubleRegister()
+                                                  ? source
+                                                  : destination);
+    Operand other =
+        cgen_->ToOperand(source->IsDoubleRegister() ? destination : source);
+    __ movdbl(xmm0, other);
+    __ movdbl(other, reg);
+    __ movdbl(reg, Operand(xmm0));
+
+  } else if (source->IsDoubleStackSlot() && destination->IsDoubleStackSlot()) {
+    UNIMPLEMENTED();
+
+  } else {
+    // No other combinations are possible.
+    UNREACHABLE();
+  }
+
+  // The swap of source and destination has executed a move from source to
+  // destination.
+  RemoveMove(index);
+
+  // Any unperformed (including pending) move with a source of either
+  // this move's source or destination needs to have their source
+  // changed to reflect the state of affairs after the swap.
+  for (int j = moves_.length() - 1; j >= 0; --j) {
+    LMoveOperands other_move = moves_[j];
+    if (other_move.Blocks(source)) {
+      moves_[j].set_source(destination);
+    } else if (other_move.Blocks(destination)) {
+      moves_[j].set_source(source);
+    }
+  }
+
+  // In addition to swapping the actual uses as sources, we need to update
+  // the use counts.
+  if (source->IsRegister() && destination->IsRegister()) {
+    int temp = general_source_uses_[source->index()];
+    general_source_uses_[source->index()] =
+        general_source_uses_[destination->index()];
+    general_source_uses_[destination->index()] = temp;
+
+  } else if (source->IsRegister()) {
+    // We don't have use counts for non-register operands like destination.
+    // Compute those counts now.
+    general_source_uses_[source->index()] = CountSourceUses(source);
+
+  } else if (destination->IsRegister()) {
+    general_source_uses_[destination->index()] = CountSourceUses(destination);
+
+  } else if (source->IsDoubleRegister() &&
+             destination->IsDoubleRegister()) {
+    int temp = double_source_uses_[source->index()];
+    double_source_uses_[source->index()] =
+        double_source_uses_[destination->index()];
+    double_source_uses_[destination->index()] = temp;
+
+  } else if (source->IsDoubleRegister()) {
+    double_source_uses_[source->index()] = CountSourceUses(source);
+
+  } else if (destination->IsDoubleRegister()) {
+    double_source_uses_[destination->index()] = CountSourceUses(destination);
+  }
+}
+
+#undef __
+
+} }  // namespace v8::internal