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