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
11namespace v8 {
12namespace internal {
13namespace compiler {
14
15namespace {
16
17#define REP_BIT(rep) (1 << static_cast<int>(rep))
18
19const int kFloat32Bit = REP_BIT(MachineRepresentation::kFloat32);
20const int kFloat64Bit = REP_BIT(MachineRepresentation::kFloat64);
21
22inline bool Blocks(MoveOperands* move, InstructionOperand destination) {
23  return !move->IsEliminated() && move->source().InterferesWith(destination);
24}
25
26// Splits a FP move between two location operands into the equivalent series of
27// moves between smaller sub-operands, e.g. a double move to two single moves.
28// This helps reduce the number of cycles that would normally occur under FP
29// aliasing, and makes swaps much easier to implement.
30MoveOperands* Split(MoveOperands* move, MachineRepresentation smaller_rep,
31                    ParallelMove* moves) {
32  DCHECK(!kSimpleFPAliasing);
33  // Splitting is only possible when the slot size is the same as float size.
34  DCHECK_EQ(kPointerSize, kFloatSize);
35  const LocationOperand& src_loc = LocationOperand::cast(move->source());
36  const LocationOperand& dst_loc = LocationOperand::cast(move->destination());
37  MachineRepresentation dst_rep = dst_loc.representation();
38  DCHECK_NE(smaller_rep, dst_rep);
39  auto src_kind = src_loc.location_kind();
40  auto dst_kind = dst_loc.location_kind();
41
42  int aliases =
43      1 << (ElementSizeLog2Of(dst_rep) - ElementSizeLog2Of(smaller_rep));
44  int base = -1;
45  USE(base);
46  DCHECK_EQ(aliases, RegisterConfiguration::Turbofan()->GetAliases(
47                         dst_rep, 0, smaller_rep, &base));
48
49  int src_index = -1;
50  int slot_size = (1 << ElementSizeLog2Of(smaller_rep)) / kPointerSize;
51  int src_step = 1;
52  if (src_kind == LocationOperand::REGISTER) {
53    src_index = src_loc.register_code() * aliases;
54  } else {
55    src_index = src_loc.index();
56    // For operands that occuply multiple slots, the index refers to the last
57    // slot. On little-endian architectures, we start at the high slot and use a
58    // negative step so that register-to-slot moves are in the correct order.
59    src_step = -slot_size;
60  }
61  int dst_index = -1;
62  int dst_step = 1;
63  if (dst_kind == LocationOperand::REGISTER) {
64    dst_index = dst_loc.register_code() * aliases;
65  } else {
66    dst_index = dst_loc.index();
67    dst_step = -slot_size;
68  }
69
70  // Reuse 'move' for the first fragment. It is not pending.
71  move->set_source(AllocatedOperand(src_kind, smaller_rep, src_index));
72  move->set_destination(AllocatedOperand(dst_kind, smaller_rep, dst_index));
73  // Add the remaining fragment moves.
74  for (int i = 1; i < aliases; ++i) {
75    src_index += src_step;
76    dst_index += dst_step;
77    moves->AddMove(AllocatedOperand(src_kind, smaller_rep, src_index),
78                   AllocatedOperand(dst_kind, smaller_rep, dst_index));
79  }
80  // Return the first fragment.
81  return move;
82}
83
84}  // namespace
85
86void GapResolver::Resolve(ParallelMove* moves) {
87  // Clear redundant moves, and collect FP move representations if aliasing
88  // is non-simple.
89  int reps = 0;
90  for (size_t i = 0; i < moves->size();) {
91    MoveOperands* move = (*moves)[i];
92    if (move->IsRedundant()) {
93      (*moves)[i] = moves->back();
94      moves->pop_back();
95      continue;
96    }
97    i++;
98    if (!kSimpleFPAliasing && move->destination().IsFPRegister()) {
99      reps |=
100          REP_BIT(LocationOperand::cast(move->destination()).representation());
101    }
102  }
103
104  if (!kSimpleFPAliasing) {
105    if (reps && !base::bits::IsPowerOfTwo32(reps)) {
106      // Start with the smallest FP moves, so we never encounter smaller moves
107      // in the middle of a cycle of larger moves.
108      if ((reps & kFloat32Bit) != 0) {
109        split_rep_ = MachineRepresentation::kFloat32;
110        for (size_t i = 0; i < moves->size(); ++i) {
111          auto move = (*moves)[i];
112          if (!move->IsEliminated() && move->destination().IsFloatRegister())
113            PerformMove(moves, move);
114        }
115      }
116      if ((reps & kFloat64Bit) != 0) {
117        split_rep_ = MachineRepresentation::kFloat64;
118        for (size_t i = 0; i < moves->size(); ++i) {
119          auto move = (*moves)[i];
120          if (!move->IsEliminated() && move->destination().IsDoubleRegister())
121            PerformMove(moves, move);
122        }
123      }
124    }
125    split_rep_ = MachineRepresentation::kSimd128;
126  }
127
128  for (size_t i = 0; i < moves->size(); ++i) {
129    auto move = (*moves)[i];
130    if (!move->IsEliminated()) PerformMove(moves, move);
131  }
132}
133
134void GapResolver::PerformMove(ParallelMove* moves, MoveOperands* move) {
135  // Each call to this function performs a move and deletes it from the move
136  // graph.  We first recursively perform any move blocking this one.  We mark a
137  // move as "pending" on entry to PerformMove in order to detect cycles in the
138  // move graph.  We use operand swaps to resolve cycles, which means that a
139  // call to PerformMove could change any source operand in the move graph.
140  DCHECK(!move->IsPending());
141  DCHECK(!move->IsRedundant());
142
143  // Clear this move's destination to indicate a pending move.  The actual
144  // destination is saved on the side.
145  InstructionOperand source = move->source();
146  DCHECK(!source.IsInvalid());  // Or else it will look eliminated.
147  InstructionOperand destination = move->destination();
148  move->SetPending();
149
150  // We may need to split moves between FP locations differently.
151  bool is_fp_loc_move = !kSimpleFPAliasing && destination.IsFPLocationOperand();
152
153  // Perform a depth-first traversal of the move graph to resolve dependencies.
154  // Any unperformed, unpending move with a source the same as this one's
155  // destination blocks this one so recursively perform all such moves.
156  for (size_t i = 0; i < moves->size(); ++i) {
157    auto other = (*moves)[i];
158    if (other->IsEliminated()) continue;
159    if (other->IsPending()) continue;
160    if (other->source().InterferesWith(destination)) {
161      if (!kSimpleFPAliasing && is_fp_loc_move &&
162          LocationOperand::cast(other->source()).representation() >
163              split_rep_) {
164        // 'other' must also be an FP location move. Break it into fragments
165        // of the same size as 'move'. 'other' is set to one of the fragments,
166        // and the rest are appended to 'moves'.
167        other = Split(other, split_rep_, moves);
168        // 'other' may not block destination now.
169        if (!other->source().InterferesWith(destination)) continue;
170      }
171      // Though PerformMove can change any source operand in the move graph,
172      // this call cannot create a blocking move via a swap (this loop does not
173      // miss any).  Assume there is a non-blocking move with source A and this
174      // move is blocked on source B and there is a swap of A and B.  Then A and
175      // B must be involved in the same cycle (or they would not be swapped).
176      // Since this move's destination is B and there is only a single incoming
177      // edge to an operand, this move must also be involved in the same cycle.
178      // In that case, the blocking move will be created but will be "pending"
179      // when we return from PerformMove.
180      PerformMove(moves, other);
181    }
182  }
183
184  // This move's source may have changed due to swaps to resolve cycles and so
185  // it may now be the last move in the cycle.  If so remove it.
186  source = move->source();
187  if (source.EqualsCanonicalized(destination)) {
188    move->Eliminate();
189    return;
190  }
191
192  // We are about to resolve this move and don't need it marked as pending, so
193  // restore its destination.
194  move->set_destination(destination);
195
196  // The move may be blocked on a (at most one) pending move, in which case we
197  // have a cycle.  Search for such a blocking move and perform a swap to
198  // resolve it.
199  auto blocker = std::find_if(moves->begin(), moves->end(),
200                              std::bind2nd(std::ptr_fun(&Blocks), destination));
201  if (blocker == moves->end()) {
202    // The easy case: This move is not blocked.
203    assembler_->AssembleMove(&source, &destination);
204    move->Eliminate();
205    return;
206  }
207
208  // Ensure source is a register or both are stack slots, to limit swap cases.
209  if (source.IsStackSlot() || source.IsFPStackSlot()) {
210    std::swap(source, destination);
211  }
212  assembler_->AssembleSwap(&source, &destination);
213  move->Eliminate();
214
215  // Update outstanding moves whose source may now have been moved.
216  if (!kSimpleFPAliasing && is_fp_loc_move) {
217    // We may have to split larger moves.
218    for (size_t i = 0; i < moves->size(); ++i) {
219      auto other = (*moves)[i];
220      if (other->IsEliminated()) continue;
221      if (source.InterferesWith(other->source())) {
222        if (LocationOperand::cast(other->source()).representation() >
223            split_rep_) {
224          other = Split(other, split_rep_, moves);
225          if (!source.InterferesWith(other->source())) continue;
226        }
227        other->set_source(destination);
228      } else if (destination.InterferesWith(other->source())) {
229        if (LocationOperand::cast(other->source()).representation() >
230            split_rep_) {
231          other = Split(other, split_rep_, moves);
232          if (!destination.InterferesWith(other->source())) continue;
233        }
234        other->set_source(source);
235      }
236    }
237  } else {
238    for (auto other : *moves) {
239      if (other->IsEliminated()) continue;
240      if (source.EqualsCanonicalized(other->source())) {
241        other->set_source(destination);
242      } else if (destination.EqualsCanonicalized(other->source())) {
243        other->set_source(source);
244      }
245    }
246  }
247}
248}  // namespace compiler
249}  // namespace internal
250}  // namespace v8
251