gap-resolver.cc 4.26 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14
// 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 <functional>
#include <set>

namespace v8 {
namespace internal {
namespace compiler {

15
namespace {
16

17 18
inline bool Blocks(MoveOperands* move, InstructionOperand destination) {
  return move->Blocks(destination);
19 20 21
}


22 23 24
inline bool IsRedundant(MoveOperands* move) { return move->IsRedundant(); }

}  // namespace
25 26


27 28 29 30 31
void GapResolver::Resolve(ParallelMove* moves) const {
  // Clear redundant moves.
  auto it =
      std::remove_if(moves->begin(), moves->end(), std::ptr_fun(IsRedundant));
  moves->erase(it, moves->end());
32
  for (MoveOperands* move : *moves) {
33
    if (!move->IsEliminated()) PerformMove(moves, move);
34 35 36 37
  }
}


38
void GapResolver::PerformMove(ParallelMove* moves, MoveOperands* move) const {
39 40 41 42 43
  // 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.
44 45
  DCHECK(!move->IsPending());
  DCHECK(!move->IsRedundant());
46 47 48

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

  // 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.
56
  for (MoveOperands* other : *moves) {
57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76
    if (other->Blocks(destination) && !other->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(moves, other);
    }
  }

  // We are about to resolve this move and don't need it marked as pending, so
  // restore its destination.
  move->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.
77
  InstructionOperand source = move->source();
78
  if (source.EqualsCanonicalized(destination)) {
79 80 81 82 83 84 85
    move->Eliminate();
    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.
86 87
  auto blocker = std::find_if(moves->begin(), moves->end(),
                              std::bind2nd(std::ptr_fun(&Blocks), destination));
88 89
  if (blocker == moves->end()) {
    // The easy case: This move is not blocked.
90
    assembler_->AssembleMove(&source, &destination);
91 92 93 94
    move->Eliminate();
    return;
  }

95
  DCHECK((*blocker)->IsPending());
96
  // Ensure source is a register or both are stack slots, to limit swap cases.
97
  if (source.IsStackSlot() || source.IsFPStackSlot()) {
98 99
    std::swap(source, destination);
  }
100
  assembler_->AssembleSwap(&source, &destination);
101 102 103 104 105
  move->Eliminate();

  // 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.
106
  for (MoveOperands* other : *moves) {
107 108 109 110 111 112 113
    if (other->Blocks(source)) {
      other->set_source(destination);
    } else if (other->Blocks(destination)) {
      other->set_source(source);
    }
  }
}
114 115 116
}  // namespace compiler
}  // namespace internal
}  // namespace v8