Home | History | Annotate | Download | only in compiler 
      1 // Copyright 2014 the V8 project authors. All rights reserved.
      2 // Use of this source code is governed by a BSD-style license that can be
      3 // found in the LICENSE file.
      4 
      5 #include "src/compiler/gap-resolver.h"
      6 
      7 #include <algorithm>
      8 #include <functional>
      9 #include <set>
     10 
     11 namespace v8 {
     12 namespace internal {
     13 namespace compiler {
     14 
     15 namespace {
     16 
     17 inline bool Blocks(MoveOperands* move, InstructionOperand destination) {
     18   return move->Blocks(destination);
     19 }
     20 
     21 
     22 inline bool IsRedundant(MoveOperands* move) { return move->IsRedundant(); }
     23 
     24 }  // namespace
     25 
     26 
     27 void GapResolver::Resolve(ParallelMove* moves) const {
     28   // Clear redundant moves.
     29   auto it =
     30       std::remove_if(moves->begin(), moves->end(), std::ptr_fun(IsRedundant));
     31   moves->erase(it, moves->end());
     32   for (auto move : *moves) {
     33     if (!move->IsEliminated()) PerformMove(moves, move);
     34   }
     35 }
     36 
     37 
     38 void GapResolver::PerformMove(ParallelMove* moves, MoveOperands* move) const {
     39   // Each call to this function performs a move and deletes it from the move
     40   // graph.  We first recursively perform any move blocking this one.  We mark a
     41   // move as "pending" on entry to PerformMove in order to detect cycles in the
     42   // move graph.  We use operand swaps to resolve cycles, which means that a
     43   // call to PerformMove could change any source operand in the move graph.
     44   DCHECK(!move->IsPending());
     45   DCHECK(!move->IsRedundant());
     46 
     47   // Clear this move's destination to indicate a pending move.  The actual
     48   // destination is saved on the side.
     49   DCHECK(!move->source().IsInvalid());  // Or else it will look eliminated.
     50   InstructionOperand destination = move->destination();
     51   move->SetPending();
     52 
     53   // Perform a depth-first traversal of the move graph to resolve dependencies.
     54   // Any unperformed, unpending move with a source the same as this one's
     55   // destination blocks this one so recursively perform all such moves.
     56   for (auto other : *moves) {
     57     if (other->Blocks(destination) && !other->IsPending()) {
     58       // Though PerformMove can change any source operand in the move graph,
     59       // this call cannot create a blocking move via a swap (this loop does not
     60       // miss any).  Assume there is a non-blocking move with source A and this
     61       // move is blocked on source B and there is a swap of A and B.  Then A and
     62       // B must be involved in the same cycle (or they would not be swapped).
     63       // Since this move's destination is B and there is only a single incoming
     64       // edge to an operand, this move must also be involved in the same cycle.
     65       // In that case, the blocking move will be created but will be "pending"
     66       // when we return from PerformMove.
     67       PerformMove(moves, other);
     68     }
     69   }
     70 
     71   // We are about to resolve this move and don't need it marked as pending, so
     72   // restore its destination.
     73   move->set_destination(destination);
     74 
     75   // This move's source may have changed due to swaps to resolve cycles and so
     76   // 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     move->Eliminate();
     80     return;
     81   }
     82 
     83   // The move may be blocked on a (at most one) pending move, in which case we
     84   // have a cycle.  Search for such a blocking move and perform a swap to
     85   // resolve it.
     86   auto blocker = std::find_if(moves->begin(), moves->end(),
     87                               std::bind2nd(std::ptr_fun(&Blocks), destination));
     88   if (blocker == moves->end()) {
     89     // The easy case: This move is not blocked.
     90     assembler_->AssembleMove(&source, &destination);
     91     move->Eliminate();
     92     return;
     93   }
     94 
     95   DCHECK((*blocker)->IsPending());
     96   // Ensure source is a register or both are stack slots, to limit swap cases.
     97   if (source.IsStackSlot() || source.IsDoubleStackSlot()) {
     98     std::swap(source, destination);
     99   }
    100   assembler_->AssembleSwap(&source, &destination);
    101   move->Eliminate();
    102 
    103   // Any unperformed (including pending) move with a source of either this
    104   // move's source or destination needs to have their source changed to
    105   // reflect the state of affairs after the swap.
    106   for (auto other : *moves) {
    107     if (other->Blocks(source)) {
    108       other->set_source(destination);
    109     } else if (other->Blocks(destination)) {
    110       other->set_source(source);
    111     }
    112   }
    113 }
    114 }  // namespace compiler
    115 }  // namespace internal
    116 }  // namespace v8
    117