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
Blocks(MoveOperands * move,InstructionOperand destination)17 inline bool Blocks(MoveOperands* move, InstructionOperand destination) {
18 return move->Blocks(destination);
19 }
20
21
IsRedundant(MoveOperands * move)22 inline bool IsRedundant(MoveOperands* move) { return move->IsRedundant(); }
23
24 } // namespace
25
26
Resolve(ParallelMove * moves) const27 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 (MoveOperands* move : *moves) {
33 if (!move->IsEliminated()) PerformMove(moves, move);
34 }
35 }
36
37
PerformMove(ParallelMove * moves,MoveOperands * move) const38 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 (MoveOperands* 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.InterferesWith(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.IsFPStackSlot()) {
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 (MoveOperands* 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