xref: /art/compiler/optimizing/parallel_move_resolver.cc

/*
 * Copyright (C) 2014 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#include "parallel_move_resolver.h"

#include "base/stl_util.h"
#include "nodes.h"

namespace art {

void ParallelMoveResolver::BuildInitialMoveList(HParallelMove* 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).
  for (size_t i = 0; i < parallel_move->NumMoves(); ++i) {
    MoveOperands* move = parallel_move->MoveOperandsAt(i);
    if (!move->IsRedundant()) {
      moves_.push_back(move);
    }
  }
}

void ParallelMoveResolverWithSwap::EmitNativeCode(HParallelMove* parallel_move) {
  DCHECK(moves_.empty());
  // Build up a worklist of moves.
  BuildInitialMoveList(parallel_move);

  // Move stack/stack slot to take advantage of a free register on constrained machines.
  for (size_t i = 0; i < moves_.size(); ++i) {
    const MoveOperands& move = *moves_[i];
    // Ignore constants and moves already eliminated.
    if (move.IsEliminated() || move.GetSource().IsConstant()) {
      continue;
    }

    if ((move.GetSource().IsStackSlot() || move.GetSource().IsDoubleStackSlot()) &&
        (move.GetDestination().IsStackSlot() || move.GetDestination().IsDoubleStackSlot())) {
      PerformMove(i);
    }
  }

  for (size_t i = 0; i < moves_.size(); ++i) {
    const MoveOperands& 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.GetSource().IsConstant()) {
      PerformMove(i);
    }
  }

  // Perform the moves with constant sources.
  for (size_t i = 0; i < moves_.size(); ++i) {
    MoveOperands* move = moves_[i];
    if (!move->IsEliminated()) {
      DCHECK(move->GetSource().IsConstant());
      EmitMove(i);
      // Eliminate the move, in case following moves need a scratch register.
      move->Eliminate();
    }
  }

  moves_.clear();
}

Location LowOf(Location location) {
  if (location.IsRegisterPair()) {
    return Location::RegisterLocation(location.low());
  } else if (location.IsFpuRegisterPair()) {
    return Location::FpuRegisterLocation(location.low());
  } else if (location.IsDoubleStackSlot()) {
    return Location::StackSlot(location.GetStackIndex());
  } else {
    return Location::NoLocation();
  }
}

Location HighOf(Location location) {
  if (location.IsRegisterPair()) {
    return Location::RegisterLocation(location.high());
  } else if (location.IsFpuRegisterPair()) {
    return Location::FpuRegisterLocation(location.high());
  } else if (location.IsDoubleStackSlot()) {
    return Location::StackSlot(location.GetHighStackIndex(4));
  } else {
    return Location::NoLocation();
  }
}

// Update the source of `move`, knowing that `updated_location` has been swapped
// with `new_source`. Note that `updated_location` can be a pair, therefore if
// `move` is non-pair, we need to extract which register to use.
static void UpdateSourceOf(MoveOperands* move, Location updated_location, Location new_source) {
  Location source = move->GetSource();
  if (LowOf(updated_location).Equals(source)) {
    move->SetSource(LowOf(new_source));
  } else if (HighOf(updated_location).Equals(source)) {
    move->SetSource(HighOf(new_source));
  } else {
    DCHECK(updated_location.Equals(source)) << updated_location << " " << source;
    move->SetSource(new_source);
  }
}

MoveOperands* ParallelMoveResolverWithSwap::PerformMove(size_t 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.

  MoveOperands* move = moves_[index];
  DCHECK(!move->IsPending());
  if (move->IsRedundant()) {
    // Because we swap register pairs first, following, un-pending
    // moves may become redundant.
    move->Eliminate();
    return nullptr;
  }

  // Clear this move's destination to indicate a pending move.  The actual
  // destination is saved in a stack-allocated local.  Recursion may allow
  // multiple moves to be pending.
  DCHECK(!move->GetSource().IsInvalid());
  Location destination = move->MarkPending();

  // 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.
  MoveOperands* required_swap = nullptr;
  for (size_t i = 0; i < moves_.size(); ++i) {
    const MoveOperands& other_move = *moves_[i];
    if (other_move.Blocks(destination) && !other_move.IsPending()) {
      // Though PerformMove can change any source operand in the move graph,
      // calling `PerformMove` cannot create a blocking move via a swap
      // (this loop does not miss any).
      // For example, 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.
      required_swap = PerformMove(i);

      if (required_swap == move) {
        // If this move is required to swap, we do so without looking
        // at the next moves. Swapping is not blocked by anything, it just
        // updates other moves's source.
        break;
      } else if (required_swap == moves_[i]) {
        // If `other_move` was swapped, we iterate again to find a new
        // potential cycle.
        required_swap = nullptr;
        i = -1;
      } else if (required_swap != nullptr) {
        // A move is required to swap. We walk back the cycle to find the
        // move by just returning from this `PerformMove`.
        moves_[index]->ClearPending(destination);
        return required_swap;
      }
    }
  }

  // We are about to resolve this move and don't need it marked as
  // pending, so restore its destination.
  move->ClearPending(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 (move->GetSource().Equals(destination)) {
    move->Eliminate();
    DCHECK(required_swap == nullptr);
    return nullptr;
  }

  // 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.
  bool do_swap = false;
  if (required_swap != nullptr) {
    DCHECK_EQ(required_swap, move);
    do_swap = true;
  } else {
    for (MoveOperands* other_move : moves_) {
      if (other_move->Blocks(destination)) {
        DCHECK(other_move->IsPending()) << "move=" << *move << " other_move=" << *other_move;
        if (!move->Is64BitMove() && other_move->Is64BitMove()) {
          // We swap 64bits moves before swapping 32bits moves. Go back from the
          // cycle by returning the move that must be swapped.
          return other_move;
        }
        do_swap = true;
        break;
      }
    }
  }

  if (do_swap) {
    EmitSwap(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.
    Location source = move->GetSource();
    Location swap_destination = move->GetDestination();
    move->Eliminate();
    for (MoveOperands* other_move : moves_) {
      if (other_move->Blocks(source)) {
        UpdateSourceOf(other_move, source, swap_destination);
      } else if (other_move->Blocks(swap_destination)) {
        UpdateSourceOf(other_move, swap_destination, source);
      }
    }
    // If the swap was required because of a 64bits move in the middle of a cycle,
    // we return the swapped move, so that the caller knows it needs to re-iterate
    // its dependency loop.
    return required_swap;
  } else {
    // This move is not blocked.
    EmitMove(index);
    move->Eliminate();
    DCHECK(required_swap == nullptr);
    return nullptr;
  }
}

bool ParallelMoveResolverWithSwap::IsScratchLocation(Location loc) {
  for (MoveOperands* move : moves_) {
    if (move->Blocks(loc)) {
      return false;
    }
  }

  for (MoveOperands* move : moves_) {
    if (move->GetDestination().Equals(loc)) {
      return true;
    }
  }

  return false;
}

int ParallelMoveResolverWithSwap::AllocateScratchRegister(int blocked,
                                                          int register_count,
                                                          int if_scratch,
                                                          bool* spilled) {
  DCHECK_NE(blocked, if_scratch);
  int scratch = -1;
  for (int reg = 0; reg < register_count; ++reg) {
    if ((blocked != reg) && IsScratchLocation(Location::RegisterLocation(reg))) {
      scratch = reg;
      break;
    }
  }

  if (scratch == -1) {
    *spilled = true;
    scratch = if_scratch;
  } else {
    *spilled = false;
  }

  return scratch;
}


ParallelMoveResolverWithSwap::ScratchRegisterScope::ScratchRegisterScope(
    ParallelMoveResolverWithSwap* resolver, int blocked, int if_scratch, int number_of_registers)
    : resolver_(resolver),
      reg_(kNoRegister),
      spilled_(false) {
  reg_ = resolver_->AllocateScratchRegister(blocked, number_of_registers, if_scratch, &spilled_);

  if (spilled_) {
    resolver->SpillScratch(reg_);
  }
}


ParallelMoveResolverWithSwap::ScratchRegisterScope::~ScratchRegisterScope() {
  if (spilled_) {
    resolver_->RestoreScratch(reg_);
  }
}

void ParallelMoveResolverNoSwap::EmitNativeCode(HParallelMove* parallel_move) {
  DCHECK_EQ(GetNumberOfPendingMoves(), 0u);
  DCHECK(moves_.empty());
  DCHECK(scratches_.empty());

  // Backend dependent initialization.
  PrepareForEmitNativeCode();

  // Build up a worklist of moves.
  BuildInitialMoveList(parallel_move);

  for (size_t i = 0; i < moves_.size(); ++i) {
    const MoveOperands& 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.GetSource().IsConstant()) {
      PerformMove(i);
    }
  }

  // Perform the moves with constant sources and register destinations with UpdateMoveSource()
  // to reduce the number of literal loads. Stack destinations are skipped since we won't be benefit
  // from changing the constant sources to stack locations.
  for (size_t i = 0; i < moves_.size(); ++i) {
    MoveOperands* move = moves_[i];
    Location destination = move->GetDestination();
    if (!move->IsEliminated() && !destination.IsStackSlot() && !destination.IsDoubleStackSlot()) {
      Location source = move->GetSource();
      EmitMove(i);
      move->Eliminate();
      // This may introduce additional instruction dependency, but reduce number
      // of moves and possible literal loads. For example,
      // Original moves:
      //   1234.5678 -> D0
      //   1234.5678 -> D1
      // Updated moves:
      //   1234.5678 -> D0
      //   D0 -> D1
      UpdateMoveSource(source, destination);
    }
  }

  // Perform the rest of the moves.
  for (size_t i = 0; i < moves_.size(); ++i) {
    MoveOperands* move = moves_[i];
    if (!move->IsEliminated()) {
      EmitMove(i);
      move->Eliminate();
    }
  }

  // All pending moves that we have added for resolve cycles should be performed.
  DCHECK_EQ(GetNumberOfPendingMoves(), 0u);

  // Backend dependent cleanup.
  FinishEmitNativeCode();

  moves_.clear();
  scratches_.clear();
}

Location ParallelMoveResolverNoSwap::GetScratchLocation(Location::Kind kind) {
  for (Location loc : scratches_) {
    if (loc.GetKind() == kind && !IsBlockedByMoves(loc)) {
      return loc;
    }
  }
  for (MoveOperands* move : moves_) {
    Location loc = move->GetDestination();
    if (loc.GetKind() == kind && !IsBlockedByMoves(loc)) {
      return loc;
    }
  }
  return Location::NoLocation();
}

void ParallelMoveResolverNoSwap::AddScratchLocation(Location loc) {
  if (kIsDebugBuild) {
    for (Location scratch : scratches_) {
      CHECK(!loc.Equals(scratch));
    }
  }
  scratches_.push_back(loc);
}

void ParallelMoveResolverNoSwap::RemoveScratchLocation(Location loc) {
  DCHECK(!IsBlockedByMoves(loc));
  for (auto it = scratches_.begin(), end = scratches_.end(); it != end; ++it) {
    if (loc.Equals(*it)) {
      scratches_.erase(it);
      break;
    }
  }
}

void ParallelMoveResolverNoSwap::PerformMove(size_t 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 scratch location to resolve cycles, also
  // additional pending moves might be added. After move has been performed,
  // we will update source operand in the move graph to reduce dependencies in
  // the graph.

  MoveOperands* move = moves_[index];
  DCHECK(!move->IsPending());
  DCHECK(!move->IsEliminated());
  if (move->IsRedundant()) {
    // Previous operations on the list of moves have caused this particular move
    // to become a no-op, so we can safely eliminate it. Consider for example
    // (0 -> 1) (1 -> 0) (1 -> 2). There is a cycle (0 -> 1) (1 -> 0), that we will
    // resolve as (1 -> scratch) (0 -> 1) (scratch -> 0). If, by chance, '2' is
    // used as the scratch location, the move (1 -> 2) will occur while resolving
    // the cycle. When that move is emitted, the code will update moves with a '1'
    // as their source to use '2' instead (see `UpdateMoveSource()`. In our example
    // the initial move (1 -> 2) would then become the no-op (2 -> 2) that can be
    // eliminated here.
    move->Eliminate();
    return;
  }

  // Clear this move's destination to indicate a pending move. The actual
  // destination is saved in a stack-allocated local. Recursion may allow
  // multiple moves to be pending.
  DCHECK(!move->GetSource().IsInvalid());
  Location destination = move->MarkPending();

  // 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) {
    const MoveOperands& other_move = *moves_[i];
    if (other_move.Blocks(destination) && !other_move.IsPending()) {
      PerformMove(i);
    }
  }

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

  // No one else should write to the move destination when the it is pending.
  DCHECK(!move->IsRedundant());

  Location source = move->GetSource();
  // The move may be blocked on several pending moves, in case we have a cycle.
  if (IsBlockedByMoves(destination)) {
    // For a cycle like: (A -> B) (B -> C) (C -> A), we change it to following
    // sequence:
    // (C -> scratch)     # Emit right now.
    // (A -> B) (B -> C)  # Unblocked.
    // (scratch -> A)     # Add to pending_moves_, blocked by (A -> B).
    Location::Kind kind = source.GetKind();
    DCHECK_NE(kind, Location::kConstant);
    Location scratch = AllocateScratchLocationFor(kind);
    // We only care about the move size.
    DataType::Type type = move->Is64BitMove() ? DataType::Type::kInt64 : DataType::Type::kInt32;
    // Perform (C -> scratch)
    move->SetDestination(scratch);
    EmitMove(index);
    move->Eliminate();
    UpdateMoveSource(source, scratch);
    // Add (scratch -> A).
    AddPendingMove(scratch, destination, type);
  } else {
    // This move is not blocked.
    EmitMove(index);
    move->Eliminate();
    UpdateMoveSource(source, destination);
  }

  // Moves in the pending list should not block any other moves. But performing
  // unblocked moves in the pending list can free scratch registers, so we do this
  // as early as possible.
  MoveOperands* pending_move;
  while ((pending_move = GetUnblockedPendingMove(source)) != nullptr) {
    Location pending_source = pending_move->GetSource();
    Location pending_destination = pending_move->GetDestination();
    // We do not depend on the pending move index. So just delete the move instead
    // of eliminating it to make the pending list cleaner.
    DeletePendingMove(pending_move);
    move->SetSource(pending_source);
    move->SetDestination(pending_destination);
    EmitMove(index);
    move->Eliminate();
    UpdateMoveSource(pending_source, pending_destination);
    // Free any unblocked locations in the scratch location list.
    // Note: Fetch size() on each iteration because scratches_ can be modified inside the loop.
    // FIXME: If FreeScratchLocation() removes the location from scratches_,
    // we skip the next location. This happens for arm64.
    for (size_t i = 0; i < scratches_.size(); ++i) {
      Location scratch = scratches_[i];
      // Only scratch overlapping with performed move source can be unblocked.
      if (scratch.OverlapsWith(pending_source) && !IsBlockedByMoves(scratch)) {
        FreeScratchLocation(pending_source);
      }
    }
  }
}

void ParallelMoveResolverNoSwap::UpdateMoveSource(Location from, Location to) {
  // This function is used to reduce the dependencies in the graph after
  // (from -> to) has been performed. Since we ensure there is no move with the same
  // destination, (to -> X) cannot be blocked while (from -> X) might still be
  // blocked. Consider for example the moves (0 -> 1) (1 -> 2) (1 -> 3). After
  // (1 -> 2) has been performed, the moves left are (0 -> 1) and (1 -> 3). There is
  // a dependency between the two. If we update the source location from 1 to 2, we
  // will get (0 -> 1) and (2 -> 3). There is no dependency between the two.
  //
  // This is not something we must do, but we can use fewer scratch locations with
  // this trick. For example, we can avoid using additional scratch locations for
  // moves (0 -> 1), (1 -> 2), (1 -> 0).
  for (MoveOperands* move : moves_) {
    if (move->GetSource().Equals(from)) {
      move->SetSource(to);
    }
  }
}

void ParallelMoveResolverNoSwap::AddPendingMove(Location source,
                                                Location destination,
                                                DataType::Type type) {
  pending_moves_.push_back(new (allocator_) MoveOperands(source, destination, type, nullptr));
}

void ParallelMoveResolverNoSwap::DeletePendingMove(MoveOperands* move) {
  RemoveElement(pending_moves_, move);
}

MoveOperands* ParallelMoveResolverNoSwap::GetUnblockedPendingMove(Location loc) {
  for (MoveOperands* move : pending_moves_) {
    Location destination = move->GetDestination();
    // Only moves with destination overlapping with input loc can be unblocked.
    if (destination.OverlapsWith(loc) && !IsBlockedByMoves(destination)) {
      return move;
    }
  }
  return nullptr;
}

bool ParallelMoveResolverNoSwap::IsBlockedByMoves(Location loc) {
  for (MoveOperands* move : pending_moves_) {
    if (move->Blocks(loc)) {
      return true;
    }
  }
  for (MoveOperands* move : moves_) {
    if (move->Blocks(loc)) {
      return true;
    }
  }
  return false;
}

// So far it is only used for debugging purposes to make sure all pending moves
// have been performed.
size_t ParallelMoveResolverNoSwap::GetNumberOfPendingMoves() {
  return pending_moves_.size();
}

}  // namespace art