Line data Source code
1 : /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
2 : * vim: set ts=8 sts=4 et sw=4 tw=99:
3 : * This Source Code Form is subject to the terms of the Mozilla Public
4 : * License, v. 2.0. If a copy of the MPL was not distributed with this
5 : * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
6 :
7 : #include "jit/MoveResolver.h"
8 :
9 : #include "mozilla/Attributes.h"
10 :
11 : #include "jit/MacroAssembler.h"
12 : #include "jit/RegisterSets.h"
13 :
14 : using namespace js;
15 : using namespace js::jit;
16 :
17 19673 : MoveOperand::MoveOperand(MacroAssembler& masm, const ABIArg& arg)
18 : {
19 19673 : switch (arg.kind()) {
20 : case ABIArg::GPR:
21 19652 : kind_ = REG;
22 19652 : code_ = arg.gpr().code();
23 19652 : break;
24 : #ifdef JS_CODEGEN_REGISTER_PAIR
25 : case ABIArg::GPR_PAIR:
26 : kind_ = REG_PAIR;
27 : code_ = arg.evenGpr().code();
28 : MOZ_ASSERT(code_ % 2 == 0);
29 : MOZ_ASSERT(code_ + 1 == arg.oddGpr().code());
30 : break;
31 : #endif
32 : case ABIArg::FPU:
33 5 : kind_ = FLOAT_REG;
34 5 : code_ = arg.fpu().code();
35 5 : break;
36 : case ABIArg::Stack:
37 16 : kind_ = MEMORY;
38 16 : code_ = masm.getStackPointer().code();
39 16 : disp_ = arg.offsetFromArgBase();
40 16 : break;
41 : }
42 19673 : }
43 :
44 4503 : MoveResolver::MoveResolver()
45 4503 : : numCycles_(0), curCycles_(0)
46 : {
47 4503 : }
48 :
49 : void
50 13452 : MoveResolver::resetState()
51 : {
52 13452 : numCycles_ = 0;
53 13452 : curCycles_ = 0;
54 13452 : }
55 :
56 : bool
57 19133 : MoveResolver::addMove(const MoveOperand& from, const MoveOperand& to, MoveOp::Type type)
58 : {
59 : // Assert that we're not doing no-op moves.
60 19133 : MOZ_ASSERT(!(from == to));
61 19133 : PendingMove* pm = movePool_.allocate();
62 19133 : if (!pm)
63 0 : return false;
64 19133 : new (pm) PendingMove(from, to, type);
65 19133 : pending_.pushBack(pm);
66 19133 : return true;
67 : }
68 :
69 : // Given move (A -> B), this function attempts to find any move (B -> *) in the
70 : // pending move list, and returns the first one.
71 : MoveResolver::PendingMove*
72 19231 : MoveResolver::findBlockingMove(const PendingMove* last)
73 : {
74 26589 : for (PendingMoveIterator iter = pending_.begin(); iter != pending_.end(); iter++) {
75 7455 : PendingMove* other = *iter;
76 :
77 7455 : if (other->from().aliases(last->to())) {
78 : // We now have pairs in the form (A -> X) (X -> y). The second pair
79 : // blocks the move in the first pair, so return it.
80 97 : return other;
81 : }
82 : }
83 :
84 : // No blocking moves found.
85 19134 : return nullptr;
86 : }
87 :
88 : // Given move (A -> B), this function attempts to find any move (B -> *) in the
89 : // move list iterator, and returns the first one.
90 : // N.B. It is unclear if a single move can complete more than one cycle, so to be
91 : // conservative, this function operates on iterators, so the caller can process all
92 : // instructions that start a cycle.
93 : MoveResolver::PendingMove*
94 194 : MoveResolver::findCycledMove(PendingMoveIterator* iter, PendingMoveIterator end, const PendingMove* last)
95 : {
96 286 : for (; *iter != end; (*iter)++) {
97 97 : PendingMove* other = **iter;
98 97 : if (other->from().aliases(last->to())) {
99 : // We now have pairs in the form (A -> X) (X -> y). The second pair
100 : // blocks the move in the first pair, so return it.
101 5 : (*iter)++;
102 5 : return other;
103 : }
104 : }
105 : // No blocking moves found.
106 97 : return nullptr;
107 : }
108 :
109 : #ifdef JS_CODEGEN_ARM
110 : static inline bool
111 : MoveIsDouble(const MoveOperand& move)
112 : {
113 : if (!move.isFloatReg())
114 : return false;
115 : return move.floatReg().isDouble();
116 : }
117 : #endif
118 :
119 : #ifdef JS_CODEGEN_ARM
120 : static inline bool
121 : MoveIsSingle(const MoveOperand& move)
122 : {
123 : if (!move.isFloatReg())
124 : return false;
125 : return move.floatReg().isSingle();
126 : }
127 : #endif
128 :
129 : #ifdef JS_CODEGEN_ARM
130 : bool
131 : MoveResolver::isDoubleAliasedAsSingle(const MoveOperand& move)
132 : {
133 : if (!MoveIsDouble(move))
134 : return false;
135 :
136 : for (auto iter = pending_.begin(); iter != pending_.end(); ++iter) {
137 : PendingMove* other = *iter;
138 : if (other->from().aliases(move) && MoveIsSingle(other->from()))
139 : return true;
140 : if (other->to().aliases(move) && MoveIsSingle(other->to()))
141 : return true;
142 : }
143 : return false;
144 : }
145 : #endif
146 :
147 : #ifdef JS_CODEGEN_ARM
148 : static MoveOperand
149 : SplitIntoLowerHalf(const MoveOperand& move)
150 : {
151 : if (MoveIsDouble(move)) {
152 : FloatRegister lowerSingle = move.floatReg().asSingle();
153 : return MoveOperand(lowerSingle);
154 : }
155 :
156 : MOZ_ASSERT(move.isMemoryOrEffectiveAddress());
157 : return move;
158 : }
159 : #endif
160 :
161 : #ifdef JS_CODEGEN_ARM
162 : static MoveOperand
163 : SplitIntoUpperHalf(const MoveOperand& move)
164 : {
165 : if (MoveIsDouble(move)) {
166 : FloatRegister lowerSingle = move.floatReg().asSingle();
167 : FloatRegister upperSingle = VFPRegister(lowerSingle.code() + 1, VFPRegister::Single);
168 : return MoveOperand(upperSingle);
169 : }
170 :
171 : MOZ_ASSERT(move.isMemoryOrEffectiveAddress());
172 : return MoveOperand(move.base(), move.disp() + sizeof(float));
173 : }
174 : #endif
175 :
176 : bool
177 13452 : MoveResolver::resolve()
178 : {
179 13452 : resetState();
180 13452 : orderedMoves_.clear();
181 :
182 : #ifdef JS_CODEGEN_ARM
183 : // Some of ARM's double registers alias two of its single registers,
184 : // but the algorithm below assumes that every register can participate
185 : // in at most one cycle. To satisfy the algorithm, any double registers
186 : // that may conflict are split into their single-register halves.
187 : //
188 : // This logic is only applicable because ARM only uses registers d0-d15,
189 : // all of which alias s0-s31. Double registers d16-d31 are unused.
190 : // Therefore there is never a double move that cannot be split.
191 : // If this changes in the future, the algorithm will have to be fixed.
192 : for (auto iter = pending_.begin(); iter != pending_.end(); ++iter) {
193 : PendingMove* pm = *iter;
194 :
195 : if (isDoubleAliasedAsSingle(pm->from()) || isDoubleAliasedAsSingle(pm->to())) {
196 : PendingMove* lower = movePool_.allocate();
197 : if (!lower)
198 : return false;
199 :
200 : // Insert the new node before the current position to not affect iteration.
201 : MoveOperand fromLower = SplitIntoLowerHalf(pm->from());
202 : MoveOperand toLower = SplitIntoLowerHalf(pm->to());
203 : new (lower) PendingMove(fromLower, toLower, MoveOp::FLOAT32);
204 : pending_.insertBefore(pm, lower);
205 :
206 : // Overwrite pm in place for the upper move. Iteration proceeds as normal.
207 : MoveOperand fromUpper = SplitIntoUpperHalf(pm->from());
208 : MoveOperand toUpper = SplitIntoUpperHalf(pm->to());
209 : pm->overwrite(fromUpper, toUpper, MoveOp::FLOAT32);
210 : }
211 : }
212 : #endif
213 :
214 13452 : InlineList<PendingMove> stack;
215 :
216 : // This is a depth-first-search without recursion, which tries to find
217 : // cycles in a list of moves.
218 : //
219 : // Algorithm.
220 : //
221 : // S = Traversal stack.
222 : // P = Pending move list.
223 : // O = Ordered list of moves.
224 : //
225 : // As long as there are pending moves in P:
226 : // Let |root| be any pending move removed from P
227 : // Add |root| to the traversal stack.
228 : // As long as S is not empty:
229 : // Let |L| be the most recent move added to S.
230 : //
231 : // Find any pending move M whose source is L's destination, thus
232 : // preventing L's move until M has completed.
233 : //
234 : // If a move M was found,
235 : // Remove M from the pending list.
236 : // If M's destination is |root|,
237 : // Annotate M and |root| as cycles.
238 : // Add M to S.
239 : // do not Add M to O, since M may have other conflictors in P that have not yet been processed.
240 : // Otherwise,
241 : // Add M to S.
242 : // Otherwise,
243 : // Remove L from S.
244 : // Add L to O.
245 : //
246 51526 : while (!pending_.empty()) {
247 19037 : PendingMove* pm = pending_.popBack();
248 :
249 : // Add this pending move to the cycle detection stack.
250 19037 : stack.pushBack(pm);
251 :
252 57499 : while (!stack.empty()) {
253 19231 : PendingMove* blocking = findBlockingMove(stack.peekBack());
254 :
255 19231 : if (blocking) {
256 97 : PendingMoveIterator stackiter = stack.begin();
257 97 : PendingMove* cycled = findCycledMove(&stackiter, stack.end(), blocking);
258 97 : if (cycled) {
259 : // Find the cycle's start.
260 : // We annotate cycles at each move in the cycle, and
261 : // assert that we do not find two cycles in one move chain
262 : // traversal (which would indicate two moves to the same
263 : // destination).
264 : // Since there can be more than one cycle, find them all.
265 0 : do {
266 5 : cycled->setCycleEnd(curCycles_);
267 5 : cycled = findCycledMove(&stackiter, stack.end(), blocking);
268 5 : } while (cycled);
269 :
270 5 : blocking->setCycleBegin(pm->type(), curCycles_);
271 5 : curCycles_++;
272 5 : pending_.remove(blocking);
273 5 : stack.pushBack(blocking);
274 : } else {
275 : // This is a new link in the move chain, so keep
276 : // searching for a cycle.
277 92 : pending_.remove(blocking);
278 92 : stack.pushBack(blocking);
279 : }
280 : } else {
281 : // Otherwise, pop the last move on the search stack because it's
282 : // complete and not participating in a cycle. The resulting
283 : // move can safely be added to the ordered move list.
284 19134 : PendingMove* done = stack.popBack();
285 19134 : if (!addOrderedMove(*done))
286 0 : return false;
287 19134 : movePool_.free(done);
288 : }
289 : }
290 : // If the current queue is empty, it is certain that there are
291 : // all previous cycles cannot conflict with future cycles,
292 : // so re-set the counter of pending cycles, while keeping a high-water mark.
293 19037 : if (numCycles_ < curCycles_)
294 5 : numCycles_ = curCycles_;
295 19037 : curCycles_ = 0;
296 : }
297 :
298 13452 : return true;
299 : }
300 :
301 : bool
302 19134 : MoveResolver::addOrderedMove(const MoveOp& move)
303 : {
304 : // Sometimes the register allocator generates move groups where multiple
305 : // moves have the same source. Try to optimize these cases when the source
306 : // is in memory and the target of one of the moves is in a register.
307 19134 : MOZ_ASSERT(!move.from().aliases(move.to()));
308 :
309 19134 : if (!move.from().isMemory() || move.isCycleBegin() || move.isCycleEnd())
310 18050 : return orderedMoves_.append(move);
311 :
312 : // Look for an earlier move with the same source, where no intervening move
313 : // touches either the source or destination of the new move.
314 2424 : for (int i = orderedMoves_.length() - 1; i >= 0; i--) {
315 1353 : const MoveOp& existing = orderedMoves_[i];
316 :
317 5412 : if (existing.from() == move.from() &&
318 1353 : !existing.to().aliases(move.to()) &&
319 0 : existing.type() == move.type() &&
320 2706 : !existing.isCycleBegin() &&
321 0 : !existing.isCycleEnd())
322 : {
323 0 : MoveOp* after = orderedMoves_.begin() + i + 1;
324 0 : if (existing.to().isGeneralReg() || existing.to().isFloatReg()) {
325 0 : MoveOp nmove(existing.to(), move.to(), move.type());
326 0 : return orderedMoves_.insert(after, nmove);
327 0 : } else if (move.to().isGeneralReg() || move.to().isFloatReg()) {
328 0 : MoveOp nmove(move.to(), existing.to(), move.type());
329 0 : orderedMoves_[i] = move;
330 0 : return orderedMoves_.insert(after, nmove);
331 : }
332 : }
333 :
334 1353 : if (existing.aliases(move))
335 13 : break;
336 : }
337 :
338 1084 : return orderedMoves_.append(move);
339 : }
340 :
341 : void
342 0 : MoveResolver::reorderMove(size_t from, size_t to)
343 : {
344 0 : MOZ_ASSERT(from != to);
345 :
346 0 : MoveOp op = orderedMoves_[from];
347 0 : if (from < to) {
348 0 : for (size_t i = from; i < to; i++)
349 0 : orderedMoves_[i] = orderedMoves_[i + 1];
350 : } else {
351 0 : for (size_t i = from; i > to; i--)
352 0 : orderedMoves_[i] = orderedMoves_[i - 1];
353 : }
354 0 : orderedMoves_[to] = op;
355 0 : }
356 :
357 : void
358 0 : MoveResolver::sortMemoryToMemoryMoves()
359 : {
360 : // Try to reorder memory->memory moves so that they are executed right
361 : // before a move that clobbers some register. This will allow the move
362 : // emitter to use that clobbered register as a scratch register for the
363 : // memory->memory move, if necessary.
364 0 : for (size_t i = 0; i < orderedMoves_.length(); i++) {
365 0 : const MoveOp& base = orderedMoves_[i];
366 0 : if (!base.from().isMemory() || !base.to().isMemory())
367 0 : continue;
368 0 : if (base.type() != MoveOp::GENERAL && base.type() != MoveOp::INT32)
369 0 : continue;
370 :
371 : // Look for an earlier move clobbering a register.
372 0 : bool found = false;
373 0 : for (int j = i - 1; j >= 0; j--) {
374 0 : const MoveOp& previous = orderedMoves_[j];
375 0 : if (previous.aliases(base) || previous.isCycleBegin() || previous.isCycleEnd())
376 0 : break;
377 :
378 0 : if (previous.to().isGeneralReg()) {
379 0 : reorderMove(i, j);
380 0 : found = true;
381 0 : break;
382 : }
383 : }
384 0 : if (found)
385 0 : continue;
386 :
387 : // Look for a later move clobbering a register.
388 0 : if (i + 1 < orderedMoves_.length()) {
389 0 : bool found = false, skippedRegisterUse = false;
390 0 : for (size_t j = i + 1; j < orderedMoves_.length(); j++) {
391 0 : const MoveOp& later = orderedMoves_[j];
392 0 : if (later.aliases(base) || later.isCycleBegin() || later.isCycleEnd())
393 0 : break;
394 :
395 0 : if (later.to().isGeneralReg()) {
396 0 : if (skippedRegisterUse) {
397 0 : reorderMove(i, j);
398 0 : found = true;
399 : } else {
400 : // There is no move that uses a register between the
401 : // original memory->memory move and this move that
402 : // clobbers a register. The move should already be able
403 : // to use a scratch register, so don't shift anything
404 : // around.
405 : }
406 0 : break;
407 : }
408 :
409 0 : if (later.from().isGeneralReg())
410 0 : skippedRegisterUse = true;
411 : }
412 :
413 0 : if (found) {
414 : // Redo the search for memory->memory moves at the current
415 : // index, so we don't skip the move just shifted back.
416 0 : i--;
417 : }
418 : }
419 : }
420 0 : }
|
