/* This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

#include "jit/x86-shared/MoveEmitter-x86-shared.h"

#include "jit/MacroAssembler-inl.h"

using namespace js;
using namespace js::jit;

using mozilla::Maybe;

MoveEmitterX86::MoveEmitterX86(MacroAssembler& masm)
    : inCycle_(false), masm(masm), pushedAtCycle_(-1) {
  pushedAtStart_ = masm.framePushed();
}

// Examine the cycle in moves starting at position i. Determine if it's a
// simple cycle consisting of all register-to-register moves in a single class,
// and whether it can be implemented entirely by swaps.
size_t MoveEmitterX86::characterizeCycle(const MoveResolver& moves, size_t i,
                                         bool* allGeneralRegs,
                                         bool* allFloatRegs) {
  size_t swapCount = 0;

  for (size_t j = i;; j++) {
    const MoveOp& move = moves.getMove(j);

    // If it isn't a cycle of registers of the same kind, we won't be able
    // to optimize it.
    if (!move.to().isGeneralReg()) {
      *allGeneralRegs = false;
    }
    if (!move.to().isFloatReg()) {
      *allFloatRegs = false;
    }
    if (!*allGeneralRegs && !*allFloatRegs) {
      return -1;
    }

    // Stop iterating when we see the last one.
    if (j != i && move.isCycleEnd()) {
      break;
    }

    // Check that this move is actually part of the cycle. This is
    // over-conservative when there are multiple reads from the same source,
    // but that's expected to be rare.
    if (move.from() != moves.getMove(j + 1).to()) {
      *allGeneralRegs = false;
      *allFloatRegs = false;
      return -1;
    }

    swapCount++;
  }

  // Check that the last move cycles back to the first move.
  const MoveOp& move = moves.getMove(i + swapCount);
  if (move.from() != moves.getMove(i).to()) {
    *allGeneralRegs = false;
    *allFloatRegs = false;
    return -1;
  }

  return swapCount;
}

// If we can emit optimized code for the cycle in moves starting at position i,
// do so, and return true.
bool MoveEmitterX86::maybeEmitOptimizedCycle(const MoveResolver& moves,
                                             size_t i, bool allGeneralRegs,
                                             bool allFloatRegs,
                                             size_t swapCount) {
  MOZ_ASSERT(swapCount > 0);

  if (allGeneralRegs && swapCount <= 2) {
    // Use x86's swap-integer-registers instruction if we only have a few
    // swaps. (x86 also has a swap between registers and memory but it's
    // slow.)
    for (size_t k = 0; k < swapCount; k++) {
      masm.xchg(moves.getMove(i + k).to().reg(),
                moves.getMove(i + k + 1).to().reg());
    }
    return true;
  }

  if (allFloatRegs) {
    // There's no xchg for xmm registers, but we can use the scratch register.
    // |characterizeCycle| ensures this is a simple cycle where each move's
    // source is the next move's target (wrapping around for the last move):
    //
    //   A => B
    //   C => A
    //   B => C
    //
    // We break the cycle by using the scratch register:
    //
    //   B => scratch
    //   A => B
    //   C => A
    //   scratch => C
    ScratchSimd128Scope scratch(masm);
    for (size_t k = 0; k <= swapCount; k++) {
      FloatRegister from = moves.getMove(i + k).from().floatReg();
      FloatRegister to = moves.getMove(i + k).to().floatReg();
      MOZ_ASSERT(from != scratch && to != scratch);
      if (k == 0) {
        MOZ_ASSERT(from == moves.getMove(i + 1).to().floatReg());
        masm.vmovapd(to, scratch);
        masm.vmovapd(from, to);
      } else if (k == swapCount) {
        MOZ_ASSERT(from == moves.getMove(i).to().floatReg());
        masm.vmovapd(scratch, to);
      } else {
        MOZ_ASSERT(from == moves.getMove(i + k + 1).to().floatReg());
        masm.vmovapd(from, to);
      }
    }
    return true;
  }

  return false;
}

void MoveEmitterX86::emit(const MoveResolver& moves) {
#if defined(JS_CODEGEN_X86) && defined(DEBUG)
  // Clobber any scratch register we have, to make regalloc bugs more visible.
  if (scratchRegister_.isSome()) {
    masm.mov(ImmWord(0xdeadbeef), scratchRegister_.value());
  }
#endif

  for (size_t i = 0; i < moves.numMoves(); i++) {
#if defined(JS_CODEGEN_X86) && defined(DEBUG)
    if (!scratchRegister_.isSome()) {
      Maybe<Register> reg = findScratchRegister(moves, i);
      if (reg.isSome()) {
        masm.mov(ImmWord(0xdeadbeef), reg.value());
      }
    }
#endif

    const MoveOp& move = moves.getMove(i);
    const MoveOperand& from = move.from();
    const MoveOperand& to = move.to();

    if (move.isCycleEnd()) {
      MOZ_ASSERT(inCycle_);
      completeCycle(to, move.type());
      inCycle_ = false;
      continue;
    }

    if (move.isCycleBegin()) {
      MOZ_ASSERT(!inCycle_);

      // Characterize the cycle.
      bool allGeneralRegs = true, allFloatRegs = true;
      size_t swapCount =
          characterizeCycle(moves, i, &allGeneralRegs, &allFloatRegs);

      // Attempt to optimize it to avoid using the stack.
      if (maybeEmitOptimizedCycle(moves, i, allGeneralRegs, allFloatRegs,
                                  swapCount)) {
        i += swapCount;
        continue;
      }

      // Otherwise use the stack.
      breakCycle(to, move.endCycleType());
      inCycle_ = true;
    }

    // A normal move which is not part of a cycle.
    switch (move.type()) {
      case MoveOp::FLOAT32:
        emitFloat32Move(from, to);
        break;
      case MoveOp::DOUBLE:
        emitDoubleMove(from, to);
        break;
      case MoveOp::INT32:
        emitInt32Move(from, to, moves, i);
        break;
      case MoveOp::GENERAL:
        emitGeneralMove(from, to, moves, i);
        break;
      case MoveOp::SIMD128:
        emitSimd128Move(from, to);
        break;
      default:
        MOZ_CRASH("Unexpected move type");
    }
  }
}

Address MoveEmitterX86::cycleSlot() {
  if (pushedAtCycle_ == -1) {
    // Reserve stack for cycle resolution
    static_assert(SpillSlotSize == 16);
    masm.reserveStack(SpillSlotSize);
    pushedAtCycle_ = masm.framePushed();
  }

  return Address(StackPointer, masm.framePushed() - pushedAtCycle_);
}

Address MoveEmitterX86::toAddress(const MoveOperand& operand) const {
  if (operand.base() != StackPointer) {
    return Address(operand.base(), operand.disp());
  }

  MOZ_ASSERT(operand.disp() >= 0);

  // Otherwise, the stack offset may need to be adjusted.
  return Address(StackPointer,
                 operand.disp() + (masm.framePushed() - pushedAtStart_));
}

// Warning, do not use the resulting operand with pop instructions, since they
// compute the effective destination address after altering the stack pointer.
// Use toPopOperand if an Operand is needed for a pop.
Operand MoveEmitterX86::toOperand(const MoveOperand& operand) const {
  if (operand.isMemoryOrEffectiveAddress()) {
    return Operand(toAddress(operand));
  }
  if (operand.isGeneralReg()) {
    return Operand(operand.reg());
  }

  MOZ_ASSERT(operand.isFloatReg());
  return Operand(operand.floatReg());
}

// This is the same as toOperand except that it computes an Operand suitable for
// use in a pop.
Operand MoveEmitterX86::toPopOperand(const MoveOperand& operand) const {
  if (operand.isMemory()) {
    if (operand.base() != StackPointer) {
      return Operand(operand.base(), operand.disp());
    }

    MOZ_ASSERT(operand.disp() >= 0);

    // Otherwise, the stack offset may need to be adjusted.
    // Note the adjustment by the stack slot here, to offset for the fact that
    // pop computes its effective address after incrementing the stack pointer.
    return Operand(
        StackPointer,
        operand.disp() + (masm.framePushed() - sizeof(void*) - pushedAtStart_));
  }
  if (operand.isGeneralReg()) {
    return Operand(operand.reg());
  }

  MOZ_ASSERT(operand.isFloatReg());
  return Operand(operand.floatReg());
}

void MoveEmitterX86::breakCycle(const MoveOperand& to, MoveOp::Type type) {
  // There is some pattern:
  //   (A -> B)
  //   (B -> A)
  //
  // This case handles (A -> B), which we reach first. We save B, then allow
  // the original move to continue.
  switch (type) {
    case MoveOp::SIMD128:
      if (to.isMemory()) {
        ScratchSimd128Scope scratch(masm);
        masm.loadUnalignedSimd128(toAddress(to), scratch);
        masm.storeUnalignedSimd128(scratch, cycleSlot());
      } else {
        masm.storeUnalignedSimd128(to.floatReg(), cycleSlot());
      }
      break;
    case MoveOp::FLOAT32:
      if (to.isMemory()) {
        ScratchFloat32Scope scratch(masm);
        masm.loadFloat32(toAddress(to), scratch);
        masm.storeFloat32(scratch, cycleSlot());
      } else {
        masm.storeFloat32(to.floatReg(), cycleSlot());
      }
      break;
    case MoveOp::DOUBLE:
      if (to.isMemory()) {
        ScratchDoubleScope scratch(masm);
        masm.loadDouble(toAddress(to), scratch);
        masm.storeDouble(scratch, cycleSlot());
      } else {
        masm.storeDouble(to.floatReg(), cycleSlot());
      }
      break;
    case MoveOp::INT32:
#ifdef JS_CODEGEN_X64
      // x64 can't pop to a 32-bit destination, so don't push.
      if (to.isMemory()) {
        masm.load32(toAddress(to), ScratchReg);
        masm.store32(ScratchReg, cycleSlot());
      } else {
        masm.store32(to.reg(), cycleSlot());
      }
      break;
#endif
    case MoveOp::GENERAL:
      masm.Push(toOperand(to));
      break;
    default:
      MOZ_CRASH("Unexpected move type");
  }
}

void MoveEmitterX86::completeCycle(const MoveOperand& to, MoveOp::Type type) {
  // There is some pattern:
  //   (A -> B)
  //   (B -> A)
  //
  // This case handles (B -> A), which we reach last. We emit a move from the
  // saved value of B, to A.
  switch (type) {
    case MoveOp::SIMD128:
      MOZ_ASSERT(pushedAtCycle_ != -1);
      MOZ_ASSERT(pushedAtCycle_ - pushedAtStart_ >= Simd128DataSize);
      if (to.isMemory()) {
        ScratchSimd128Scope scratch(masm);
        masm.loadUnalignedSimd128(cycleSlot(), scratch);
        masm.storeUnalignedSimd128(scratch, toAddress(to));
      } else {
        masm.loadUnalignedSimd128(cycleSlot(), to.floatReg());
      }
      break;
    case MoveOp::FLOAT32:
      MOZ_ASSERT(pushedAtCycle_ != -1);
      MOZ_ASSERT(pushedAtCycle_ - pushedAtStart_ >= sizeof(float));
      if (to.isMemory()) {
        ScratchFloat32Scope scratch(masm);
        masm.loadFloat32(cycleSlot(), scratch);
        masm.storeFloat32(scratch, toAddress(to));
      } else {
        masm.loadFloat32(cycleSlot(), to.floatReg());
      }
      break;
    case MoveOp::DOUBLE:
      MOZ_ASSERT(pushedAtCycle_ != -1);
      MOZ_ASSERT(pushedAtCycle_ - pushedAtStart_ >= sizeof(double));
      if (to.isMemory()) {
        ScratchDoubleScope scratch(masm);
        masm.loadDouble(cycleSlot(), scratch);
        masm.storeDouble(scratch, toAddress(to));
      } else {
        masm.loadDouble(cycleSlot(), to.floatReg());
      }
      break;
    case MoveOp::INT32:
#ifdef JS_CODEGEN_X64
      MOZ_ASSERT(pushedAtCycle_ != -1);
      MOZ_ASSERT(pushedAtCycle_ - pushedAtStart_ >= sizeof(int32_t));
      // x64 can't pop to a 32-bit destination.
      if (to.isMemory()) {
        masm.load32(cycleSlot(), ScratchReg);
        masm.store32(ScratchReg, toAddress(to));
      } else {
        masm.load32(cycleSlot(), to.reg());
      }
      break;
#endif
    case MoveOp::GENERAL:
      MOZ_ASSERT(masm.framePushed() - pushedAtStart_ >= sizeof(intptr_t));
      masm.Pop(toPopOperand(to));
      break;
    default:
      MOZ_CRASH("Unexpected move type");
  }
}

void MoveEmitterX86::emitInt32Move(const MoveOperand& from,
                                   const MoveOperand& to,
                                   const MoveResolver& moves, size_t i) {
  if (from.isGeneralReg()) {
    masm.move32(from.reg(), toOperand(to));
  } else if (to.isGeneralReg()) {
    MOZ_ASSERT(from.isMemory());
    masm.load32(toAddress(from), to.reg());
  } else {
    // Memory to memory gpr move.
    MOZ_ASSERT(from.isMemory());
    Maybe<Register> reg = findScratchRegister(moves, i);
    if (reg.isSome()) {
      masm.load32(toAddress(from), reg.value());
      masm.move32(reg.value(), toOperand(to));
    } else {
      // No scratch register available; bounce it off the stack.
      masm.Push(toOperand(from));
      masm.Pop(toPopOperand(to));
    }
  }
}

void MoveEmitterX86::emitGeneralMove(const MoveOperand& from,
                                     const MoveOperand& to,
                                     const MoveResolver& moves, size_t i) {
  if (from.isGeneralReg()) {
    masm.mov(from.reg(), toOperand(to));
  } else if (to.isGeneralReg()) {
    MOZ_ASSERT(from.isMemoryOrEffectiveAddress());
    if (from.isMemory()) {
      masm.loadPtr(toAddress(from), to.reg());
    } else {
      masm.lea(toOperand(from), to.reg());
    }
  } else if (from.isMemory()) {
    // Memory to memory gpr move.
    Maybe<Register> reg = findScratchRegister(moves, i);
    if (reg.isSome()) {
      masm.loadPtr(toAddress(from), reg.value());
      masm.mov(reg.value(), toOperand(to));
    } else {
      // No scratch register available; bounce it off the stack.
      masm.Push(toOperand(from));
      masm.Pop(toPopOperand(to));
    }
  } else {
    // Effective address to memory move.
    MOZ_ASSERT(from.isEffectiveAddress());
    Maybe<Register> reg = findScratchRegister(moves, i);
    if (reg.isSome()) {
      masm.lea(toOperand(from), reg.value());
      masm.mov(reg.value(), toOperand(to));
    } else {
      // This is tricky without a scratch reg. We can't do an lea. Bounce the
      // base register off the stack, then add the offset in place. Note that
      // this clobbers FLAGS!
      masm.Push(from.base());
      masm.Pop(toPopOperand(to));
      MOZ_ASSERT(to.isMemoryOrEffectiveAddress());
      masm.addPtr(Imm32(from.disp()), toAddress(to));
    }
  }
}

void MoveEmitterX86::emitFloat32Move(const MoveOperand& from,
                                     const MoveOperand& to) {
  MOZ_ASSERT_IF(from.isFloatReg(), from.floatReg().isSingle());
  MOZ_ASSERT_IF(to.isFloatReg(), to.floatReg().isSingle());

  if (from.isFloatReg()) {
    if (to.isFloatReg()) {
      masm.moveFloat32(from.floatReg(), to.floatReg());
    } else {
      masm.storeFloat32(from.floatReg(), toAddress(to));
    }
  } else if (to.isFloatReg()) {
    masm.loadFloat32(toAddress(from), to.floatReg());
  } else {
    // Memory to memory move.
    MOZ_ASSERT(from.isMemory());
    ScratchFloat32Scope scratch(masm);
    masm.loadFloat32(toAddress(from), scratch);
    masm.storeFloat32(scratch, toAddress(to));
  }
}

void MoveEmitterX86::emitDoubleMove(const MoveOperand& from,
                                    const MoveOperand& to) {
  MOZ_ASSERT_IF(from.isFloatReg(), from.floatReg().isDouble());
  MOZ_ASSERT_IF(to.isFloatReg(), to.floatReg().isDouble());

  if (from.isFloatReg()) {
    if (to.isFloatReg()) {
      masm.moveDouble(from.floatReg(), to.floatReg());
    } else {
      masm.storeDouble(from.floatReg(), toAddress(to));
    }
  } else if (to.isFloatReg()) {
    masm.loadDouble(toAddress(from), to.floatReg());
  } else {
    // Memory to memory move.
    MOZ_ASSERT(from.isMemory());
    ScratchDoubleScope scratch(masm);
    masm.loadDouble(toAddress(from), scratch);
    masm.storeDouble(scratch, toAddress(to));
  }
}

void MoveEmitterX86::emitSimd128Move(const MoveOperand& from,
                                     const MoveOperand& to) {
  MOZ_ASSERT_IF(from.isFloatReg(), from.floatReg().isSimd128());
  MOZ_ASSERT_IF(to.isFloatReg(), to.floatReg().isSimd128());

  if (from.isFloatReg()) {
    if (to.isFloatReg()) {
      masm.moveSimd128(from.floatReg(), to.floatReg());
    } else {
      masm.storeUnalignedSimd128(from.floatReg(), toAddress(to));
    }
  } else if (to.isFloatReg()) {
    masm.loadUnalignedSimd128(toAddress(from), to.floatReg());
  } else {
    // Memory to memory move.
    MOZ_ASSERT(from.isMemory());
    ScratchSimd128Scope scratch(masm);
    masm.loadUnalignedSimd128(toAddress(from), scratch);
    masm.storeUnalignedSimd128(scratch, toAddress(to));
  }
}

void MoveEmitterX86::finish() {
  assertDone();

  masm.freeStack(masm.framePushed() - pushedAtStart_);
}

Maybe<Register> MoveEmitterX86::findScratchRegister(const MoveResolver& moves,
                                                    size_t initial) {
#ifdef JS_CODEGEN_X86
  if (scratchRegister_.isSome()) {
    return scratchRegister_;
  }

  // All registers are either in use by this move group or are live
  // afterwards. Look through the remaining moves for a register which is
  // clobbered before it is used, and is thus dead at this point.
  AllocatableGeneralRegisterSet regs(GeneralRegisterSet::All());
  for (size_t i = initial; i < moves.numMoves(); i++) {
    const MoveOp& move = moves.getMove(i);
    if (move.from().isGeneralReg()) {
      regs.takeUnchecked(move.from().reg());
    } else if (move.from().isMemoryOrEffectiveAddress()) {
      regs.takeUnchecked(move.from().base());
    }
    if (move.to().isGeneralReg()) {
      if (i != initial && !move.isCycleBegin() && regs.has(move.to().reg())) {
        return mozilla::Some(move.to().reg());
      }
      regs.takeUnchecked(move.to().reg());
    } else if (move.to().isMemoryOrEffectiveAddress()) {
      regs.takeUnchecked(move.to().base());
    }
  }

  return mozilla::Nothing();
#else
  return mozilla::Some(ScratchReg);
#endif
}