Line data Source code
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/register-configuration.h"
12 :
13 : namespace v8 {
14 : namespace internal {
15 : namespace compiler {
16 :
17 : namespace {
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.
23 : MoveOperands* Split(MoveOperands* move, MachineRepresentation smaller_rep,
24 : ParallelMove* moves) {
25 : DCHECK(!kSimpleFPAliasing);
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 :
77 : enum MoveOperandKind : uint8_t { kConstant, kGpReg, kFpReg, kStack };
78 :
79 : MoveOperandKind GetKind(const InstructionOperand& move) {
80 70396128 : if (move.IsConstant()) return kConstant;
81 : LocationOperand loc_op = LocationOperand::cast(move);
82 51711051 : if (loc_op.location_kind() != LocationOperand::REGISTER) return kStack;
83 39322126 : return IsFloatingPoint(loc_op.representation()) ? kFpReg : kGpReg;
84 : }
85 :
86 : } // namespace
87 :
88 46047791 : void 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 168227327 : for (auto it = moves->begin(); it != moves->end();) {
97 55066032 : MoveOperands* move = *it;
98 55066032 : if (move->IsRedundant()) {
99 19868112 : *it = moves->back();
100 : moves->pop_back();
101 : continue;
102 : }
103 : source_kinds.Add(GetKind(move->source()));
104 : destination_kinds.Add(GetKind(move->destination()));
105 : if (!kSimpleFPAliasing && move->destination().IsFPRegister()) {
106 : fp_reps |= RepresentationBit(
107 : LocationOperand::cast(move->destination()).representation());
108 : }
109 : ++it;
110 : }
111 :
112 51533622 : if ((source_kinds & destination_kinds).empty() || moves->size() < 2) {
113 : // Fast path for non-conflicting parallel moves.
114 108233777 : for (MoveOperands* move : *moves) {
115 23098069 : assembler_->AssembleMove(&move->source(), &move->destination());
116 : }
117 46047715 : return;
118 : }
119 :
120 : if (!kSimpleFPAliasing) {
121 : if (fp_reps && !base::bits::IsPowerOfTwo(fp_reps)) {
122 : // Start with the smallest FP moves, so we never encounter smaller moves
123 : // in the middle of a cycle of larger moves.
124 : if ((fp_reps & RepresentationBit(MachineRepresentation::kFloat32)) != 0) {
125 : split_rep_ = MachineRepresentation::kFloat32;
126 : for (size_t i = 0; i < moves->size(); ++i) {
127 : auto move = (*moves)[i];
128 : if (!move->IsEliminated() && move->destination().IsFloatRegister())
129 : PerformMove(moves, move);
130 : }
131 : }
132 : if ((fp_reps & RepresentationBit(MachineRepresentation::kFloat64)) != 0) {
133 : split_rep_ = MachineRepresentation::kFloat64;
134 : for (size_t i = 0; i < moves->size(); ++i) {
135 : auto move = (*moves)[i];
136 : if (!move->IsEliminated() && move->destination().IsDoubleRegister())
137 : PerformMove(moves, move);
138 : }
139 : }
140 : }
141 : split_rep_ = MachineRepresentation::kSimd128;
142 : }
143 :
144 27679782 : for (size_t i = 0; i < moves->size(); ++i) {
145 12099922 : auto move = (*moves)[i];
146 12099922 : if (!move->IsEliminated()) PerformMove(moves, move);
147 : }
148 : }
149 :
150 12099999 : void GapResolver::PerformMove(ParallelMove* moves, MoveOperands* move) {
151 : // Each call to this function performs a move and deletes it from the move
152 : // graph. We first recursively perform any move blocking this one. We mark a
153 : // move as "pending" on entry to PerformMove in order to detect cycles in the
154 : // move graph. We use operand swaps to resolve cycles, which means that a
155 : // call to PerformMove could change any source operand in the move graph.
156 : DCHECK(!move->IsPending());
157 : DCHECK(!move->IsRedundant());
158 :
159 : // Clear this move's destination to indicate a pending move. The actual
160 : // destination is saved on the side.
161 12099999 : InstructionOperand source = move->source();
162 : DCHECK(!source.IsInvalid()); // Or else it will look eliminated.
163 12099999 : InstructionOperand destination = move->destination();
164 : move->SetPending();
165 :
166 : // We may need to split moves between FP locations differently.
167 : const bool is_fp_loc_move =
168 : !kSimpleFPAliasing && destination.IsFPLocationOperand();
169 :
170 : // Perform a depth-first traversal of the move graph to resolve dependencies.
171 : // Any unperformed, unpending move with a source the same as this one's
172 : // destination blocks this one so recursively perform all such moves.
173 130016936 : for (size_t i = 0; i < moves->size(); ++i) {
174 117916994 : auto other = (*moves)[i];
175 52908526 : if (other->IsEliminated()) continue;
176 33160592 : if (other->IsPending()) continue;
177 20359256 : if (other->source().InterferesWith(destination)) {
178 : if (is_fp_loc_move &&
179 : LocationOperand::cast(other->source()).representation() >
180 : split_rep_) {
181 : // 'other' must also be an FP location move. Break it into fragments
182 : // of the same size as 'move'. 'other' is set to one of the fragments,
183 : // and the rest are appended to 'moves'.
184 : other = Split(other, split_rep_, moves);
185 : // 'other' may not block destination now.
186 : if (!other->source().InterferesWith(destination)) continue;
187 : }
188 : // Though PerformMove can change any source operand in the move graph,
189 : // this call cannot create a blocking move via a swap (this loop does not
190 : // miss any). Assume there is a non-blocking move with source A and this
191 : // move is blocked on source B and there is a swap of A and B. Then A and
192 : // B must be involved in the same cycle (or they would not be swapped).
193 : // Since this move's destination is B and there is only a single incoming
194 : // edge to an operand, this move must also be involved in the same cycle.
195 : // In that case, the blocking move will be created but will be "pending"
196 : // when we return from PerformMove.
197 616642 : PerformMove(moves, other);
198 : }
199 : }
200 :
201 : // This move's source may have changed due to swaps to resolve cycles and so
202 : // it may now be the last move in the cycle. If so remove it.
203 12099942 : source = move->source();
204 12099928 : if (source.EqualsCanonicalized(destination)) {
205 : move->Eliminate();
206 12011364 : return;
207 : }
208 :
209 : // We are about to resolve this move and don't need it marked as pending, so
210 : // restore its destination.
211 : move->set_destination(destination);
212 :
213 : // The move may be blocked on a (at most one) pending move, in which case we
214 : // have a cycle. Search for such a blocking move and perform a swap to
215 : // resolve it.
216 : auto blocker =
217 52057631 : std::find_if(moves->begin(), moves->end(), [&](MoveOperands* move) {
218 84029501 : return !move->IsEliminated() &&
219 31971844 : move->source().InterferesWith(destination);
220 52057657 : });
221 12020969 : if (blocker == moves->end()) {
222 : // The easy case: This move is not blocked.
223 11932446 : assembler_->AssembleMove(&source, &destination);
224 : move->Eliminate();
225 : return;
226 : }
227 :
228 : // Ensure source is a register or both are stack slots, to limit swap cases.
229 171794 : if (source.IsStackSlot() || source.IsFPStackSlot()) {
230 : std::swap(source, destination);
231 : }
232 88523 : assembler_->AssembleSwap(&source, &destination);
233 : move->Eliminate();
234 :
235 : // Update outstanding moves whose source may now have been moved.
236 : if (is_fp_loc_move) {
237 : // We may have to split larger moves.
238 : for (size_t i = 0; i < moves->size(); ++i) {
239 : auto other = (*moves)[i];
240 : if (other->IsEliminated()) continue;
241 : if (source.InterferesWith(other->source())) {
242 : if (LocationOperand::cast(other->source()).representation() >
243 : split_rep_) {
244 : other = Split(other, split_rep_, moves);
245 : if (!source.InterferesWith(other->source())) continue;
246 : }
247 : other->set_source(destination);
248 : } else if (destination.InterferesWith(other->source())) {
249 : if (LocationOperand::cast(other->source()).representation() >
250 : split_rep_) {
251 : other = Split(other, split_rep_, moves);
252 : if (!destination.InterferesWith(other->source())) continue;
253 : }
254 : other->set_source(source);
255 : }
256 : }
257 : } else {
258 773444 : for (auto other : *moves) {
259 596400 : if (other->IsEliminated()) continue;
260 603625 : if (source.EqualsCanonicalized(other->source())) {
261 : other->set_source(destination);
262 289454 : } else if (destination.EqualsCanonicalized(other->source())) {
263 : other->set_source(source);
264 : }
265 : }
266 : }
267 : }
268 : } // namespace compiler
269 : } // namespace internal
270 183867 : } // namespace v8
|
