// Copyright 2014 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "src/compiler/gap-resolver.h"

#include <algorithm>
#include <set>

namespace v8 {
namespace internal {
namespace compiler {

namespace {

#define REP_BIT(rep) (1 << static_cast<int>(rep))

const int kFloat32Bit = REP_BIT(MachineRepresentation::kFloat32);
const int kFloat64Bit = REP_BIT(MachineRepresentation::kFloat64);

// Splits a FP move between two location operands into the equivalent series of
// moves between smaller sub-operands, e.g. a double move to two single moves.
// This helps reduce the number of cycles that would normally occur under FP
// aliasing, and makes swaps much easier to implement.
MoveOperands* Split(MoveOperands* move, MachineRepresentation smaller_rep,
                    ParallelMove* moves) {
  DCHECK(!kSimpleFPAliasing);
  // Splitting is only possible when the slot size is the same as float size.
  DCHECK_EQ(kPointerSize, kFloatSize);
  const LocationOperand& src_loc = LocationOperand::cast(move->source());
  const LocationOperand& dst_loc = LocationOperand::cast(move->destination());
  MachineRepresentation dst_rep = dst_loc.representation();
  DCHECK_NE(smaller_rep, dst_rep);
  auto src_kind = src_loc.location_kind();
  auto dst_kind = dst_loc.location_kind();

  int aliases =
      1 << (ElementSizeLog2Of(dst_rep) - ElementSizeLog2Of(smaller_rep));
  int base = -1;
  USE(base);
  DCHECK_EQ(aliases, RegisterConfiguration::Default()->GetAliases(
                         dst_rep, 0, smaller_rep, &base));

  int src_index = -1;
  int slot_size = (1 << ElementSizeLog2Of(smaller_rep)) / kPointerSize;
  int src_step = 1;
  if (src_kind == LocationOperand::REGISTER) {
    src_index = src_loc.register_code() * aliases;
  } else {
    src_index = src_loc.index();
    // For operands that occupy multiple slots, the index refers to the last
    // slot. On little-endian architectures, we start at the high slot and use a
    // negative step so that register-to-slot moves are in the correct order.
    src_step = -slot_size;
  }
  int dst_index = -1;
  int dst_step = 1;
  if (dst_kind == LocationOperand::REGISTER) {
    dst_index = dst_loc.register_code() * aliases;
  } else {
    dst_index = dst_loc.index();
    dst_step = -slot_size;
  }

  // Reuse 'move' for the first fragment. It is not pending.
  move->set_source(AllocatedOperand(src_kind, smaller_rep, src_index));
  move->set_destination(AllocatedOperand(dst_kind, smaller_rep, dst_index));
  // Add the remaining fragment moves.
  for (int i = 1; i < aliases; ++i) {
    src_index += src_step;
    dst_index += dst_step;
    moves->AddMove(AllocatedOperand(src_kind, smaller_rep, src_index),
                   AllocatedOperand(dst_kind, smaller_rep, dst_index));
  }
  // Return the first fragment.
  return move;
}

}  // namespace

void GapResolver::Resolve(ParallelMove* moves) {
  // Clear redundant moves, and collect FP move representations if aliasing
  // is non-simple.
  int reps = 0;
  for (size_t i = 0; i < moves->size();) {
    MoveOperands* move = (*moves)[i];
    if (move->IsRedundant()) {
      (*moves)[i] = moves->back();
      moves->pop_back();
      continue;
    }
    i++;
    if (!kSimpleFPAliasing && move->destination().IsFPRegister()) {
      reps |=
          REP_BIT(LocationOperand::cast(move->destination()).representation());
    }
  }

  if (!kSimpleFPAliasing) {
    if (reps && !base::bits::IsPowerOfTwo(reps)) {
      // Start with the smallest FP moves, so we never encounter smaller moves
      // in the middle of a cycle of larger moves.
      if ((reps & kFloat32Bit) != 0) {
        split_rep_ = MachineRepresentation::kFloat32;
        for (size_t i = 0; i < moves->size(); ++i) {
          auto move = (*moves)[i];
          if (!move->IsEliminated() && move->destination().IsFloatRegister())
            PerformMove(moves, move);
        }
      }
      if ((reps & kFloat64Bit) != 0) {
        split_rep_ = MachineRepresentation::kFloat64;
        for (size_t i = 0; i < moves->size(); ++i) {
          auto move = (*moves)[i];
          if (!move->IsEliminated() && move->destination().IsDoubleRegister())
            PerformMove(moves, move);
        }
      }
    }
    split_rep_ = MachineRepresentation::kSimd128;
  }

  for (size_t i = 0; i < moves->size(); ++i) {
    auto move = (*moves)[i];
    if (!move->IsEliminated()) PerformMove(moves, move);
  }
}

void GapResolver::PerformMove(ParallelMove* moves, MoveOperands* move) {
  // 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.
  DCHECK(!move->IsPending());
  DCHECK(!move->IsRedundant());

  // Clear this move's destination to indicate a pending move.  The actual
  // destination is saved on the side.
  InstructionOperand source = move->source();
  DCHECK(!source.IsInvalid());  // Or else it will look eliminated.
  InstructionOperand destination = move->destination();
  move->SetPending();

  // We may need to split moves between FP locations differently.
  const bool is_fp_loc_move =
      !kSimpleFPAliasing && destination.IsFPLocationOperand();

  // 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 (size_t i = 0; i < moves->size(); ++i) {
    auto other = (*moves)[i];
    if (other->IsEliminated()) continue;
    if (other->IsPending()) continue;
    if (other->source().InterferesWith(destination)) {
      if (is_fp_loc_move &&
          LocationOperand::cast(other->source()).representation() >
              split_rep_) {
        // 'other' must also be an FP location move. Break it into fragments
        // of the same size as 'move'. 'other' is set to one of the fragments,
        // and the rest are appended to 'moves'.
        other = Split(other, split_rep_, moves);
        // 'other' may not block destination now.
        if (!other->source().InterferesWith(destination)) continue;
      }
      // 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(moves, other);
    }
  }

  // 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.
  source = move->source();
  if (source.EqualsCanonicalized(destination)) {
    move->Eliminate();
    return;
  }

  // We are about to resolve this move and don't need it marked as pending, so
  // restore its destination.
  move->set_destination(destination);

  // 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.
  auto blocker =
      std::find_if(moves->begin(), moves->end(), [&](MoveOperands* move) {
        return !move->IsEliminated() &&
               move->source().InterferesWith(destination);
      });
  if (blocker == moves->end()) {
    // The easy case: This move is not blocked.
    assembler_->AssembleMove(&source, &destination);
    move->Eliminate();
    return;
  }

  // Ensure source is a register or both are stack slots, to limit swap cases.
  if (source.IsStackSlot() || source.IsFPStackSlot()) {
    std::swap(source, destination);
  }
  assembler_->AssembleSwap(&source, &destination);
  move->Eliminate();

  // Update outstanding moves whose source may now have been moved.
  if (is_fp_loc_move) {
    // We may have to split larger moves.
    for (size_t i = 0; i < moves->size(); ++i) {
      auto other = (*moves)[i];
      if (other->IsEliminated()) continue;
      if (source.InterferesWith(other->source())) {
        if (LocationOperand::cast(other->source()).representation() >
            split_rep_) {
          other = Split(other, split_rep_, moves);
          if (!source.InterferesWith(other->source())) continue;
        }
        other->set_source(destination);
      } else if (destination.InterferesWith(other->source())) {
        if (LocationOperand::cast(other->source()).representation() >
            split_rep_) {
          other = Split(other, split_rep_, moves);
          if (!destination.InterferesWith(other->source())) continue;
        }
        other->set_source(source);
      }
    }
  } else {
    for (auto other : *moves) {
      if (other->IsEliminated()) continue;
      if (source.EqualsCanonicalized(other->source())) {
        other->set_source(destination);
      } else if (destination.EqualsCanonicalized(other->source())) {
        other->set_source(source);
      }
    }
  }
}
}  // namespace compiler
}  // namespace internal
}  // namespace v8