| OLD | NEW |
| 1 // Copyright 2014 the V8 project authors. All rights reserved. | 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 | 2 // Use of this source code is governed by a BSD-style license that can be |
| 3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
| 4 | 4 |
| 5 #include "src/compiler/gap-resolver.h" | 5 #include "src/compiler/gap-resolver.h" |
| 6 | 6 |
| 7 #include <algorithm> | 7 #include <algorithm> |
| 8 #include <functional> | 8 #include <functional> |
| 9 #include <set> | 9 #include <set> |
| 10 | 10 |
| 11 namespace v8 { | 11 namespace v8 { |
| 12 namespace internal { | 12 namespace internal { |
| 13 namespace compiler { | 13 namespace compiler { |
| 14 | 14 |
| 15 typedef ZoneList<MoveOperands>::iterator op_iterator; | 15 typedef ZoneList<MoveOperands>::iterator op_iterator; |
| 16 | 16 |
| 17 #ifdef ENABLE_SLOW_ASSERTS | 17 #ifdef ENABLE_SLOW_DCHECKS |
| 18 // TODO(svenpanne) Brush up InstructionOperand with comparison? | 18 // TODO(svenpanne) Brush up InstructionOperand with comparison? |
| 19 struct InstructionOperandComparator { | 19 struct InstructionOperandComparator { |
| 20 bool operator()(const InstructionOperand* x, | 20 bool operator()(const InstructionOperand* x, |
| 21 const InstructionOperand* y) const { | 21 const InstructionOperand* y) const { |
| 22 return (x->kind() < y->kind()) || | 22 return (x->kind() < y->kind()) || |
| 23 (x->kind() == y->kind() && x->index() < y->index()); | 23 (x->kind() == y->kind() && x->index() < y->index()); |
| 24 } | 24 } |
| 25 }; | 25 }; |
| 26 #endif | 26 #endif |
| 27 | 27 |
| 28 // No operand should be the destination for more than one move. | 28 // No operand should be the destination for more than one move. |
| 29 static void VerifyMovesAreInjective(ZoneList<MoveOperands>* moves) { | 29 static void VerifyMovesAreInjective(ZoneList<MoveOperands>* moves) { |
| 30 #ifdef ENABLE_SLOW_ASSERTS | 30 #ifdef ENABLE_SLOW_DCHECKS |
| 31 std::set<InstructionOperand*, InstructionOperandComparator> seen; | 31 std::set<InstructionOperand*, InstructionOperandComparator> seen; |
| 32 for (op_iterator i = moves->begin(); i != moves->end(); ++i) { | 32 for (op_iterator i = moves->begin(); i != moves->end(); ++i) { |
| 33 SLOW_ASSERT(seen.find(i->destination()) == seen.end()); | 33 SLOW_DCHECK(seen.find(i->destination()) == seen.end()); |
| 34 seen.insert(i->destination()); | 34 seen.insert(i->destination()); |
| 35 } | 35 } |
| 36 #endif | 36 #endif |
| 37 } | 37 } |
| 38 | 38 |
| 39 | 39 |
| 40 void GapResolver::Resolve(ParallelMove* parallel_move) const { | 40 void GapResolver::Resolve(ParallelMove* parallel_move) const { |
| 41 ZoneList<MoveOperands>* moves = parallel_move->move_operands(); | 41 ZoneList<MoveOperands>* moves = parallel_move->move_operands(); |
| 42 // TODO(svenpanne) Use the member version of remove_if when we use real lists. | 42 // TODO(svenpanne) Use the member version of remove_if when we use real lists. |
| 43 op_iterator end = | 43 op_iterator end = |
| 44 std::remove_if(moves->begin(), moves->end(), | 44 std::remove_if(moves->begin(), moves->end(), |
| 45 std::mem_fun_ref(&MoveOperands::IsRedundant)); | 45 std::mem_fun_ref(&MoveOperands::IsRedundant)); |
| 46 moves->Rewind(static_cast<int>(end - moves->begin())); | 46 moves->Rewind(static_cast<int>(end - moves->begin())); |
| 47 | 47 |
| 48 VerifyMovesAreInjective(moves); | 48 VerifyMovesAreInjective(moves); |
| 49 | 49 |
| 50 for (op_iterator move = moves->begin(); move != moves->end(); ++move) { | 50 for (op_iterator move = moves->begin(); move != moves->end(); ++move) { |
| 51 if (!move->IsEliminated()) PerformMove(moves, &*move); | 51 if (!move->IsEliminated()) PerformMove(moves, &*move); |
| 52 } | 52 } |
| 53 } | 53 } |
| 54 | 54 |
| 55 | 55 |
| 56 void GapResolver::PerformMove(ZoneList<MoveOperands>* moves, | 56 void GapResolver::PerformMove(ZoneList<MoveOperands>* moves, |
| 57 MoveOperands* move) const { | 57 MoveOperands* move) const { |
| 58 // Each call to this function performs a move and deletes it from the move | 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 | 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 | 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 | 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. | 62 // call to PerformMove could change any source operand in the move graph. |
| 63 ASSERT(!move->IsPending()); | 63 DCHECK(!move->IsPending()); |
| 64 ASSERT(!move->IsRedundant()); | 64 DCHECK(!move->IsRedundant()); |
| 65 | 65 |
| 66 // Clear this move's destination to indicate a pending move. The actual | 66 // Clear this move's destination to indicate a pending move. The actual |
| 67 // destination is saved on the side. | 67 // destination is saved on the side. |
| 68 ASSERT_NOT_NULL(move->source()); // Or else it will look eliminated. | 68 DCHECK_NOT_NULL(move->source()); // Or else it will look eliminated. |
| 69 InstructionOperand* destination = move->destination(); | 69 InstructionOperand* destination = move->destination(); |
| 70 move->set_destination(NULL); | 70 move->set_destination(NULL); |
| 71 | 71 |
| 72 // Perform a depth-first traversal of the move graph to resolve dependencies. | 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 | 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. | 74 // destination blocks this one so recursively perform all such moves. |
| 75 for (op_iterator other = moves->begin(); other != moves->end(); ++other) { | 75 for (op_iterator other = moves->begin(); other != moves->end(); ++other) { |
| 76 if (other->Blocks(destination) && !other->IsPending()) { | 76 if (other->Blocks(destination) && !other->IsPending()) { |
| 77 // Though PerformMove can change any source operand in the move graph, | 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 | 78 // this call cannot create a blocking move via a swap (this loop does not |
| (...skipping 26 matching lines...) Expand all Loading... |
| 105 op_iterator blocker = std::find_if( | 105 op_iterator blocker = std::find_if( |
| 106 moves->begin(), moves->end(), | 106 moves->begin(), moves->end(), |
| 107 std::bind2nd(std::mem_fun_ref(&MoveOperands::Blocks), destination)); | 107 std::bind2nd(std::mem_fun_ref(&MoveOperands::Blocks), destination)); |
| 108 if (blocker == moves->end()) { | 108 if (blocker == moves->end()) { |
| 109 // The easy case: This move is not blocked. | 109 // The easy case: This move is not blocked. |
| 110 assembler_->AssembleMove(source, destination); | 110 assembler_->AssembleMove(source, destination); |
| 111 move->Eliminate(); | 111 move->Eliminate(); |
| 112 return; | 112 return; |
| 113 } | 113 } |
| 114 | 114 |
| 115 ASSERT(blocker->IsPending()); | 115 DCHECK(blocker->IsPending()); |
| 116 // Ensure source is a register or both are stack slots, to limit swap cases. | 116 // Ensure source is a register or both are stack slots, to limit swap cases. |
| 117 if (source->IsStackSlot() || source->IsDoubleStackSlot()) { | 117 if (source->IsStackSlot() || source->IsDoubleStackSlot()) { |
| 118 std::swap(source, destination); | 118 std::swap(source, destination); |
| 119 } | 119 } |
| 120 assembler_->AssembleSwap(source, destination); | 120 assembler_->AssembleSwap(source, destination); |
| 121 move->Eliminate(); | 121 move->Eliminate(); |
| 122 | 122 |
| 123 // Any unperformed (including pending) move with a source of either this | 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 | 124 // move's source or destination needs to have their source changed to |
| 125 // reflect the state of affairs after the swap. | 125 // reflect the state of affairs after the swap. |
| 126 for (op_iterator other = moves->begin(); other != moves->end(); ++other) { | 126 for (op_iterator other = moves->begin(); other != moves->end(); ++other) { |
| 127 if (other->Blocks(source)) { | 127 if (other->Blocks(source)) { |
| 128 other->set_source(destination); | 128 other->set_source(destination); |
| 129 } else if (other->Blocks(destination)) { | 129 } else if (other->Blocks(destination)) { |
| 130 other->set_source(source); | 130 other->set_source(source); |
| 131 } | 131 } |
| 132 } | 132 } |
| 133 } | 133 } |
| 134 } | 134 } |
| 135 } | 135 } |
| 136 } // namespace v8::internal::compiler | 136 } // namespace v8::internal::compiler |
| OLD | NEW |