src/v8/src/compiler/gap-resolver.cc

   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 typedef ZoneList<MoveOperands>::iterator op_iterator;
  16
  17 #ifdef ENABLE_SLOW_DCHECKS
  18 // TODO(svenpanne) Brush up InstructionOperand with comparison?
  19 struct InstructionOperandComparator {
  20   bool operator()(const InstructionOperand* x,
  21                   const InstructionOperand* y) const {
  22     return (x->kind() < y->kind()) ||
  23            (x->kind() == y->kind() && x->index() < y->index());
  24   }
  25 };
  26 #endif
  27
  28 // No operand should be the destination for more than one move.
  29 static void VerifyMovesAreInjective(ZoneList<MoveOperands>* moves) {
  30 #ifdef ENABLE_SLOW_DCHECKS
  31   std::set<InstructionOperand*, InstructionOperandComparator> seen;
  32   for (op_iterator i = moves->begin(); i != moves->end(); ++i) {
  33     SLOW_DCHECK(seen.find(i->destination()) == seen.end());
  34     seen.insert(i->destination());
  35   }
  36 #endif
  37 }
  38
  39
  40 void GapResolver::Resolve(ParallelMove* parallel_move) const {
  41   ZoneList<MoveOperands>* moves = parallel_move->move_operands();
  42   // TODO(svenpanne) Use the member version of remove_if when we use real lists.
  43   op_iterator end =
  44       std::remove_if(moves->begin(), moves->end(),
  45                      std::mem_fun_ref(&MoveOperands::IsRedundant));
  46   moves->Rewind(static_cast<int>(end - moves->begin()));
  47
  48   VerifyMovesAreInjective(moves);
  49
  50   for (op_iterator move = moves->begin(); move != moves->end(); ++move) {
  51     if (!move->IsEliminated()) PerformMove(moves, &*move);
  52   }
  53 }
  54
  55
  56 void GapResolver::PerformMove(ZoneList<MoveOperands>* moves,
  57                               MoveOperands* move) const {
  58   // Each call to this function performs a move and deletes it from the move
  59   // graph.  We first recursively perform any move blocking this one.  We mark a
  60   // move as "pending" on entry to PerformMove in order to detect cycles in the
  61   // move graph.  We use operand swaps to resolve cycles, which means that a
  62   // call to PerformMove could change any source operand in the move graph.
  63   DCHECK(!move->IsPending());
  64   DCHECK(!move->IsRedundant());
  65
  66   // Clear this move's destination to indicate a pending move.  The actual
  67   // destination is saved on the side.
  68   DCHECK_NOT_NULL(move->source());  // Or else it will look eliminated.
  69   InstructionOperand* destination = move->destination();
  70   move->set_destination(NULL);
  71
  72   // Perform a depth-first traversal of the move graph to resolve dependencies.
  73   // Any unperformed, unpending move with a source the same as this one's
  74   // destination blocks this one so recursively perform all such moves.
  75   for (op_iterator other = moves->begin(); other != moves->end(); ++other) {
  76     if (other->Blocks(destination) && !other->IsPending()) {
  77       // Though PerformMove can change any source operand in the move graph,
  78       // this call cannot create a blocking move via a swap (this loop does not
  79       // miss any).  Assume there is a non-blocking move with source A and this
  80       // move is blocked on source B and there is a swap of A and B.  Then A and
  81       // B must be involved in the same cycle (or they would not be swapped).
  82       // Since this move's destination is B and there is only a single incoming
  83       // edge to an operand, this move must also be involved in the same cycle.
  84       // In that case, the blocking move will be created but will be "pending"
  85       // when we return from PerformMove.
  86       PerformMove(moves, other);
  87     }
  88   }
  89
  90   // We are about to resolve this move and don't need it marked as pending, so
  91   // restore its destination.
  92   move->set_destination(destination);
  93
  94   // This move's source may have changed due to swaps to resolve cycles and so
  95   // it may now be the last move in the cycle.  If so remove it.
  96   InstructionOperand* source = move->source();
  97   if (source->Equals(destination)) {
  98     move->Eliminate();
  99     return;
 100   }
 101
 102   // The move may be blocked on a (at most one) pending move, in which case we
 103   // have a cycle.  Search for such a blocking move and perform a swap to
 104   // resolve it.
 105   op_iterator blocker = std::find_if(
 106       moves->begin(), moves->end(),
 107       std::bind2nd(std::mem_fun_ref(&MoveOperands::Blocks), destination));
 108   if (blocker == moves->end()) {
 109     // The easy case: This move is not blocked.
 110     assembler_->AssembleMove(source, destination);
 111     move->Eliminate();
 112     return;
 113   }
 114
 115   DCHECK(blocker->IsPending());
 116   // Ensure source is a register or both are stack slots, to limit swap cases.
 117   if (source->IsStackSlot() || source->IsDoubleStackSlot()) {
 118     std::swap(source, destination);
 119   }
 120   assembler_->AssembleSwap(source, destination);
 121   move->Eliminate();
 122
 123   // Any unperformed (including pending) move with a source of either this
 124   // move's source or destination needs to have their source changed to
 125   // reflect the state of affairs after the swap.
 126   for (op_iterator other = moves->begin(); other != moves->end(); ++other) {
 127     if (other->Blocks(source)) {
 128       other->set_source(destination);
 129     } else if (other->Blocks(destination)) {
 130       other->set_source(source);
 131     }
 132   }
 133 }
 134 }
 135 }
 136 }  // namespace v8::internal::compiler