1 /*
2 * Copyright (c) 2009, 2015, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23 package org.graalvm.compiler.lir.alloc.lsra;
24
25 import static jdk.vm.ci.code.CodeUtil.isOdd;
26 import static jdk.vm.ci.code.ValueUtil.asRegister;
27 import static jdk.vm.ci.code.ValueUtil.isRegister;
28 import static org.graalvm.compiler.lir.LIRValueUtil.isStackSlotValue;
29 import static org.graalvm.compiler.lir.LIRValueUtil.isVariable;
30
31 import java.util.ArrayList;
32 import java.util.Arrays;
33 import java.util.Collections;
34 import java.util.List;
35
36 import org.graalvm.compiler.core.common.alloc.RegisterAllocationConfig.AllocatableRegisters;
37 import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
38 import org.graalvm.compiler.core.common.util.Util;
39 import org.graalvm.compiler.debug.Debug;
40 import org.graalvm.compiler.debug.GraalError;
41 import org.graalvm.compiler.debug.Indent;
42 import org.graalvm.compiler.lir.LIRInstruction;
43 import org.graalvm.compiler.lir.StandardOp.ValueMoveOp;
44 import org.graalvm.compiler.lir.alloc.OutOfRegistersException;
45 import org.graalvm.compiler.lir.alloc.lsra.Interval.RegisterBinding;
46 import org.graalvm.compiler.lir.alloc.lsra.Interval.RegisterPriority;
47 import org.graalvm.compiler.lir.alloc.lsra.Interval.SpillState;
48 import org.graalvm.compiler.lir.alloc.lsra.Interval.State;
49
50 import jdk.vm.ci.code.Register;
51 import jdk.vm.ci.meta.Value;
52
53 /**
54 */
55 class LinearScanWalker extends IntervalWalker {
56
57 protected Register[] availableRegs;
58
59 protected final int[] usePos;
60 protected final int[] blockPos;
61
62 protected List<Interval>[] spillIntervals;
63
64 private MoveResolver moveResolver; // for ordering spill moves
65
66 private int minReg;
67
68 private int maxReg;
69
70 /**
71 * Only 10% of the lists in {@link #spillIntervals} are actually used. But when they are used,
72 * they can grow quite long. The maximum length observed was 45 (all numbers taken from a
73 * bootstrap run of Graal). Therefore, we initialize {@link #spillIntervals} with this marker
74 * value, and allocate a "real" list only on demand in {@link #setUsePos}.
75 */
76 private static final List<Interval> EMPTY_LIST = Collections.emptyList();
77
78 // accessors mapped to same functions in class LinearScan
79 int blockCount() {
80 return allocator.blockCount();
81 }
82
83 AbstractBlockBase<?> blockAt(int idx) {
84 return allocator.blockAt(idx);
85 }
86
87 AbstractBlockBase<?> blockOfOpWithId(int opId) {
88 return allocator.blockForId(opId);
89 }
90
91 LinearScanWalker(LinearScan allocator, Interval unhandledFixedFirst, Interval unhandledAnyFirst) {
92 super(allocator, unhandledFixedFirst, unhandledAnyFirst);
93
94 moveResolver = allocator.createMoveResolver();
95 spillIntervals = Util.uncheckedCast(new List<?>[allocator.getRegisters().size()]);
96 for (int i = 0; i < allocator.getRegisters().size(); i++) {
97 spillIntervals[i] = EMPTY_LIST;
98 }
99 usePos = new int[allocator.getRegisters().size()];
100 blockPos = new int[allocator.getRegisters().size()];
101 }
102
103 void initUseLists(boolean onlyProcessUsePos) {
104 for (Register register : availableRegs) {
105 int i = register.number;
106 usePos[i] = Integer.MAX_VALUE;
107
108 if (!onlyProcessUsePos) {
109 blockPos[i] = Integer.MAX_VALUE;
110 spillIntervals[i].clear();
111 }
112 }
113 }
114
115 int maxRegisterNumber() {
116 return maxReg;
117 }
118
119 int minRegisterNumber() {
120 return minReg;
121 }
122
123 boolean isRegisterInRange(int reg) {
124 return reg >= minRegisterNumber() && reg <= maxRegisterNumber();
125 }
126
127 void excludeFromUse(Interval i) {
128 Value location = i.location();
129 int i1 = asRegister(location).number;
130 if (isRegisterInRange(i1)) {
131 usePos[i1] = 0;
132 }
133 }
134
135 void setUsePos(Interval interval, int usePos, boolean onlyProcessUsePos) {
136 if (usePos != -1) {
137 assert usePos != 0 : "must use excludeFromUse to set usePos to 0";
138 int i = asRegister(interval.location()).number;
139 if (isRegisterInRange(i)) {
140 if (this.usePos[i] > usePos) {
141 this.usePos[i] = usePos;
142 }
143 if (!onlyProcessUsePos) {
144 List<Interval> list = spillIntervals[i];
145 if (list == EMPTY_LIST) {
146 list = new ArrayList<>(2);
147 spillIntervals[i] = list;
148 }
149 list.add(interval);
150 }
151 }
152 }
153 }
154
155 void setBlockPos(Interval i, int blockPos) {
156 if (blockPos != -1) {
157 int reg = asRegister(i.location()).number;
158 if (isRegisterInRange(reg)) {
159 if (this.blockPos[reg] > blockPos) {
160 this.blockPos[reg] = blockPos;
161 }
162 if (usePos[reg] > blockPos) {
163 usePos[reg] = blockPos;
164 }
165 }
166 }
167 }
168
169 void freeExcludeActiveFixed() {
170 Interval interval = activeLists.get(RegisterBinding.Fixed);
171 while (!interval.isEndMarker()) {
172 assert isRegister(interval.location()) : "active interval must have a register assigned";
173 excludeFromUse(interval);
174 interval = interval.next;
175 }
176 }
177
178 void freeExcludeActiveAny() {
179 Interval interval = activeLists.get(RegisterBinding.Any);
180 while (!interval.isEndMarker()) {
181 assert isRegister(interval.location()) : "active interval must have a register assigned";
182 excludeFromUse(interval);
183 interval = interval.next;
184 }
185 }
186
187 void freeCollectInactiveFixed(Interval current) {
188 Interval interval = inactiveLists.get(RegisterBinding.Fixed);
189 while (!interval.isEndMarker()) {
190 if (current.to() <= interval.currentFrom()) {
191 assert interval.currentIntersectsAt(current) == -1 : "must not intersect";
192 setUsePos(interval, interval.currentFrom(), true);
193 } else {
194 setUsePos(interval, interval.currentIntersectsAt(current), true);
195 }
196 interval = interval.next;
197 }
198 }
199
200 void freeCollectInactiveAny(Interval current) {
201 Interval interval = inactiveLists.get(RegisterBinding.Any);
202 while (!interval.isEndMarker()) {
203 setUsePos(interval, interval.currentIntersectsAt(current), true);
204 interval = interval.next;
205 }
206 }
207
208 void freeCollectUnhandled(RegisterBinding kind, Interval current) {
209 Interval interval = unhandledLists.get(kind);
210 while (!interval.isEndMarker()) {
211 setUsePos(interval, interval.intersectsAt(current), true);
212 if (kind == RegisterBinding.Fixed && current.to() <= interval.from()) {
213 setUsePos(interval, interval.from(), true);
214 }
215 interval = interval.next;
216 }
217 }
218
219 void spillExcludeActiveFixed() {
220 Interval interval = activeLists.get(RegisterBinding.Fixed);
221 while (!interval.isEndMarker()) {
222 excludeFromUse(interval);
223 interval = interval.next;
224 }
225 }
226
227 void spillBlockUnhandledFixed(Interval current) {
228 Interval interval = unhandledLists.get(RegisterBinding.Fixed);
229 while (!interval.isEndMarker()) {
230 setBlockPos(interval, interval.intersectsAt(current));
231 interval = interval.next;
232 }
233 }
234
235 void spillBlockInactiveFixed(Interval current) {
236 Interval interval = inactiveLists.get(RegisterBinding.Fixed);
237 while (!interval.isEndMarker()) {
238 if (current.to() > interval.currentFrom()) {
239 setBlockPos(interval, interval.currentIntersectsAt(current));
240 } else {
241 assert interval.currentIntersectsAt(current) == -1 : "invalid optimization: intervals intersect";
242 }
243
244 interval = interval.next;
245 }
246 }
247
248 void spillCollectActiveAny(RegisterPriority registerPriority) {
249 Interval interval = activeLists.get(RegisterBinding.Any);
250 while (!interval.isEndMarker()) {
251 setUsePos(interval, Math.min(interval.nextUsage(registerPriority, currentPosition), interval.to()), false);
252 interval = interval.next;
253 }
254 }
255
256 void spillCollectInactiveAny(Interval current) {
257 Interval interval = inactiveLists.get(RegisterBinding.Any);
258 while (!interval.isEndMarker()) {
259 if (interval.currentIntersects(current)) {
260 setUsePos(interval, Math.min(interval.nextUsage(RegisterPriority.LiveAtLoopEnd, currentPosition), interval.to()), false);
261 }
262 interval = interval.next;
263 }
264 }
265
266 void insertMove(int operandId, Interval srcIt, Interval dstIt) {
267 // output all moves here. When source and target are equal, the move is
268 // optimized away later in assignRegNums
269
270 int opId = (operandId + 1) & ~1;
271 AbstractBlockBase<?> opBlock = allocator.blockForId(opId);
272 assert opId > 0 && allocator.blockForId(opId - 2) == opBlock : "cannot insert move at block boundary";
273
274 // calculate index of instruction inside instruction list of current block
275 // the minimal index (for a block with no spill moves) can be calculated because the
276 // numbering of instructions is known.
277 // When the block already contains spill moves, the index must be increased until the
278 // correct index is reached.
279 ArrayList<LIRInstruction> instructions = allocator.getLIR().getLIRforBlock(opBlock);
280 int index = (opId - instructions.get(0).id()) >> 1;
281 assert instructions.get(index).id() <= opId : "error in calculation";
282
283 while (instructions.get(index).id() != opId) {
284 index++;
285 assert 0 <= index && index < instructions.size() : "index out of bounds";
286 }
287 assert 1 <= index && index < instructions.size() : "index out of bounds";
288 assert instructions.get(index).id() == opId : "error in calculation";
289
290 // insert new instruction before instruction at position index
291 moveResolver.moveInsertPosition(instructions, index);
292 moveResolver.addMapping(srcIt, dstIt);
293 }
294
295 int findOptimalSplitPos(AbstractBlockBase<?> minBlock, AbstractBlockBase<?> maxBlock, int maxSplitPos) {
296 int fromBlockNr = minBlock.getLinearScanNumber();
297 int toBlockNr = maxBlock.getLinearScanNumber();
298
299 assert 0 <= fromBlockNr && fromBlockNr < blockCount() : "out of range";
300 assert 0 <= toBlockNr && toBlockNr < blockCount() : "out of range";
301 assert fromBlockNr < toBlockNr : "must cross block boundary";
302
303 // Try to split at end of maxBlock. If this would be after
304 // maxSplitPos, then use the begin of maxBlock
305 int optimalSplitPos = allocator.getLastLirInstructionId(maxBlock) + 2;
306 if (optimalSplitPos > maxSplitPos) {
307 optimalSplitPos = allocator.getFirstLirInstructionId(maxBlock);
308 }
309
310 int minLoopDepth = maxBlock.getLoopDepth();
311 for (int i = toBlockNr - 1; minLoopDepth > 0 && i >= fromBlockNr; i--) {
312 AbstractBlockBase<?> cur = blockAt(i);
313
314 if (cur.getLoopDepth() < minLoopDepth) {
315 // block with lower loop-depth found . split at the end of this block
316 minLoopDepth = cur.getLoopDepth();
317 optimalSplitPos = allocator.getLastLirInstructionId(cur) + 2;
318 }
319 }
320 assert optimalSplitPos > allocator.maxOpId() || allocator.isBlockBegin(optimalSplitPos) : "algorithm must move split pos to block boundary";
321
322 return optimalSplitPos;
323 }
324
325 int findOptimalSplitPos(Interval interval, int minSplitPos, int maxSplitPos, boolean doLoopOptimization) {
326 int optimalSplitPos = -1;
327 if (minSplitPos == maxSplitPos) {
328 // trivial case, no optimization of split position possible
329 if (Debug.isLogEnabled()) {
330 Debug.log("min-pos and max-pos are equal, no optimization possible");
331 }
332 optimalSplitPos = minSplitPos;
333
334 } else {
335 assert minSplitPos < maxSplitPos : "must be true then";
336 assert minSplitPos > 0 : "cannot access minSplitPos - 1 otherwise";
337
338 // reason for using minSplitPos - 1: when the minimal split pos is exactly at the
339 // beginning of a block, then minSplitPos is also a possible split position.
340 // Use the block before as minBlock, because then minBlock.lastLirInstructionId() + 2 ==
341 // minSplitPos
342 AbstractBlockBase<?> minBlock = allocator.blockForId(minSplitPos - 1);
343
344 // reason for using maxSplitPos - 1: otherwise there would be an assert on failure
345 // when an interval ends at the end of the last block of the method
346 // (in this case, maxSplitPos == allocator().maxLirOpId() + 2, and there is no
347 // block at this opId)
348 AbstractBlockBase<?> maxBlock = allocator.blockForId(maxSplitPos - 1);
349
350 assert minBlock.getLinearScanNumber() <= maxBlock.getLinearScanNumber() : "invalid order";
351 if (minBlock == maxBlock) {
352 // split position cannot be moved to block boundary : so split as late as possible
353 if (Debug.isLogEnabled()) {
354 Debug.log("cannot move split pos to block boundary because minPos and maxPos are in same block");
355 }
356 optimalSplitPos = maxSplitPos;
357
358 } else {
359 if (interval.hasHoleBetween(maxSplitPos - 1, maxSplitPos) && !allocator.isBlockBegin(maxSplitPos)) {
360 // Do not move split position if the interval has a hole before maxSplitPos.
361 // Intervals resulting from Phi-Functions have more than one definition (marked
362 // as mustHaveRegister) with a hole before each definition. When the register is
363 // needed
364 // for the second definition : an earlier reloading is unnecessary.
365 if (Debug.isLogEnabled()) {
366 Debug.log("interval has hole just before maxSplitPos, so splitting at maxSplitPos");
367 }
368 optimalSplitPos = maxSplitPos;
369
370 } else {
371 // seach optimal block boundary between minSplitPos and maxSplitPos
372 if (Debug.isLogEnabled()) {
373 Debug.log("moving split pos to optimal block boundary between block B%d and B%d", minBlock.getId(), maxBlock.getId());
374 }
375
376 if (doLoopOptimization) {
377 // Loop optimization: if a loop-end marker is found between min- and
378 // max-position :
379 // then split before this loop
380 int loopEndPos = interval.nextUsageExact(RegisterPriority.LiveAtLoopEnd, allocator.getLastLirInstructionId(minBlock) + 2);
381 if (Debug.isLogEnabled()) {
382 Debug.log("loop optimization: loop end found at pos %d", loopEndPos);
383 }
384
385 assert loopEndPos > minSplitPos : "invalid order";
386 if (loopEndPos < maxSplitPos) {
387 // loop-end marker found between min- and max-position
388 // if it is not the end marker for the same loop as the min-position :
389 // then move
390 // the max-position to this loop block.
391 // Desired result: uses tagged as shouldHaveRegister inside a loop cause
392 // a reloading
393 // of the interval (normally, only mustHaveRegister causes a reloading)
394 AbstractBlockBase<?> loopBlock = allocator.blockForId(loopEndPos);
395
396 if (Debug.isLogEnabled()) {
397 Debug.log("interval is used in loop that ends in block B%d, so trying to move maxBlock back from B%d to B%d", loopBlock.getId(), maxBlock.getId(), loopBlock.getId());
398 }
399 assert loopBlock != minBlock : "loopBlock and minBlock must be different because block boundary is needed between";
400
401 int maxSpillPos = allocator.getLastLirInstructionId(loopBlock) + 2;
402 optimalSplitPos = findOptimalSplitPos(minBlock, loopBlock, maxSpillPos);
403 if (optimalSplitPos == maxSpillPos) {
404 optimalSplitPos = -1;
405 if (Debug.isLogEnabled()) {
406 Debug.log("loop optimization not necessary");
407 }
408 } else {
409 if (Debug.isLogEnabled()) {
410 Debug.log("loop optimization successful");
411 }
412 }
413 }
414 }
415
416 if (optimalSplitPos == -1) {
417 // not calculated by loop optimization
418 optimalSplitPos = findOptimalSplitPos(minBlock, maxBlock, maxSplitPos);
419 }
420 }
421 }
422 }
423 if (Debug.isLogEnabled()) {
424 Debug.log("optimal split position: %d", optimalSplitPos);
425 }
426
427 return optimalSplitPos;
428 }
429
430 // split an interval at the optimal position between minSplitPos and
431 // maxSplitPos in two parts:
432 // 1) the left part has already a location assigned
433 // 2) the right part is sorted into to the unhandled-list
434 @SuppressWarnings("try")
435 void splitBeforeUsage(Interval interval, int minSplitPos, int maxSplitPos) {
436
437 try (Indent indent = Debug.logAndIndent("splitting interval %s between %d and %d", interval, minSplitPos, maxSplitPos)) {
438
439 assert interval.from() < minSplitPos : "cannot split at start of interval";
440 assert currentPosition < minSplitPos : "cannot split before current position";
441 assert minSplitPos <= maxSplitPos : "invalid order";
442 assert maxSplitPos <= interval.to() : "cannot split after end of interval";
443
444 int optimalSplitPos = findOptimalSplitPos(interval, minSplitPos, maxSplitPos, true);
445
446 assert minSplitPos <= optimalSplitPos && optimalSplitPos <= maxSplitPos : "out of range";
447 assert optimalSplitPos <= interval.to() : "cannot split after end of interval";
448 assert optimalSplitPos > interval.from() : "cannot split at start of interval";
449
450 if (optimalSplitPos == interval.to() && interval.nextUsage(RegisterPriority.MustHaveRegister, minSplitPos) == Integer.MAX_VALUE) {
451 // the split position would be just before the end of the interval
452 // . no split at all necessary
453 if (Debug.isLogEnabled()) {
454 Debug.log("no split necessary because optimal split position is at end of interval");
455 }
456 return;
457 }
458
459 // must calculate this before the actual split is performed and before split position is
460 // moved to odd opId
461 boolean moveNecessary = !allocator.isBlockBegin(optimalSplitPos) && !interval.hasHoleBetween(optimalSplitPos - 1, optimalSplitPos);
462
463 if (!allocator.isBlockBegin(optimalSplitPos)) {
464 // move position before actual instruction (odd opId)
465 optimalSplitPos = (optimalSplitPos - 1) | 1;
466 }
467
468 if (Debug.isLogEnabled()) {
469 Debug.log("splitting at position %d", optimalSplitPos);
470 }
471
472 assert allocator.isBlockBegin(optimalSplitPos) || ((optimalSplitPos & 1) == 1) : "split pos must be odd when not on block boundary";
473 assert !allocator.isBlockBegin(optimalSplitPos) || ((optimalSplitPos & 1) == 0) : "split pos must be even on block boundary";
474
475 Interval splitPart = interval.split(optimalSplitPos, allocator);
476
477 splitPart.setInsertMoveWhenActivated(moveNecessary);
478
479 assert splitPart.from() >= currentPosition : "cannot append new interval before current walk position";
480 unhandledLists.addToListSortedByStartAndUsePositions(RegisterBinding.Any, splitPart);
481
482 if (Debug.isLogEnabled()) {
483 Debug.log("left interval %s: %s", moveNecessary ? " " : "", interval.logString(allocator));
484 Debug.log("right interval %s: %s", moveNecessary ? "(move)" : "", splitPart.logString(allocator));
485 }
486 }
487 }
488
489 // split an interval at the optimal position between minSplitPos and
490 // maxSplitPos in two parts:
491 // 1) the left part has already a location assigned
492 // 2) the right part is always on the stack and therefore ignored in further processing
493 @SuppressWarnings("try")
494 void splitForSpilling(Interval interval) {
495 // calculate allowed range of splitting position
496 int maxSplitPos = currentPosition;
497 int previousUsage = interval.previousUsage(RegisterPriority.ShouldHaveRegister, maxSplitPos);
498 if (previousUsage == currentPosition) {
499 /*
500 * If there is a usage with ShouldHaveRegister priority at the current position fall
501 * back to MustHaveRegister priority. This only happens if register priority was
502 * downgraded to MustHaveRegister in #allocLockedRegister.
503 */
504 previousUsage = interval.previousUsage(RegisterPriority.MustHaveRegister, maxSplitPos);
505 }
506 int minSplitPos = Math.max(previousUsage + 1, interval.from());
507
508 try (Indent indent = Debug.logAndIndent("splitting and spilling interval %s between %d and %d", interval, minSplitPos, maxSplitPos)) {
509
510 assert interval.state == State.Active : "why spill interval that is not active?";
511 assert interval.from() <= minSplitPos : "cannot split before start of interval";
512 assert minSplitPos <= maxSplitPos : "invalid order";
513 assert maxSplitPos < interval.to() : "cannot split at end end of interval";
514 assert currentPosition < interval.to() : "interval must not end before current position";
515
516 if (minSplitPos == interval.from()) {
517 // the whole interval is never used, so spill it entirely to memory
518
519 try (Indent indent2 = Debug.logAndIndent("spilling entire interval because split pos is at beginning of interval (use positions: %d)", interval.usePosList().size())) {
520
521 assert interval.firstUsage(RegisterPriority.MustHaveRegister) > currentPosition : String.format("interval %s must not have use position before currentPosition %d", interval,
522 currentPosition);
523
524 allocator.assignSpillSlot(interval);
525 handleSpillSlot(interval);
526 changeSpillState(interval, minSplitPos);
527
528 // Also kick parent intervals out of register to memory when they have no use
529 // position. This avoids short interval in register surrounded by intervals in
530 // memory . avoid useless moves from memory to register and back
531 Interval parent = interval;
532 while (parent != null && parent.isSplitChild()) {
533 parent = parent.getSplitChildBeforeOpId(parent.from());
534
535 if (isRegister(parent.location())) {
536 if (parent.firstUsage(RegisterPriority.ShouldHaveRegister) == Integer.MAX_VALUE) {
537 // parent is never used, so kick it out of its assigned register
538 if (Debug.isLogEnabled()) {
539 Debug.log("kicking out interval %d out of its register because it is never used", parent.operandNumber);
540 }
541 allocator.assignSpillSlot(parent);
542 handleSpillSlot(parent);
543 } else {
544 // do not go further back because the register is actually used by
545 // the interval
546 parent = null;
547 }
548 }
549 }
550 }
551
552 } else {
553 // search optimal split pos, split interval and spill only the right hand part
554 int optimalSplitPos = findOptimalSplitPos(interval, minSplitPos, maxSplitPos, false);
555
556 assert minSplitPos <= optimalSplitPos && optimalSplitPos <= maxSplitPos : "out of range";
557 assert optimalSplitPos < interval.to() : "cannot split at end of interval";
558 assert optimalSplitPos >= interval.from() : "cannot split before start of interval";
559
560 if (!allocator.isBlockBegin(optimalSplitPos)) {
561 // move position before actual instruction (odd opId)
562 optimalSplitPos = (optimalSplitPos - 1) | 1;
563 }
564
565 try (Indent indent2 = Debug.logAndIndent("splitting at position %d", optimalSplitPos)) {
566 assert allocator.isBlockBegin(optimalSplitPos) || ((optimalSplitPos & 1) == 1) : "split pos must be odd when not on block boundary";
567 assert !allocator.isBlockBegin(optimalSplitPos) || ((optimalSplitPos & 1) == 0) : "split pos must be even on block boundary";
568
569 Interval spilledPart = interval.split(optimalSplitPos, allocator);
570 allocator.assignSpillSlot(spilledPart);
571 handleSpillSlot(spilledPart);
572 changeSpillState(spilledPart, optimalSplitPos);
573
574 if (!allocator.isBlockBegin(optimalSplitPos)) {
575 if (Debug.isLogEnabled()) {
576 Debug.log("inserting move from interval %d to %d", interval.operandNumber, spilledPart.operandNumber);
577 }
578 insertMove(optimalSplitPos, interval, spilledPart);
579 }
580
581 // the currentSplitChild is needed later when moves are inserted for reloading
582 assert spilledPart.currentSplitChild() == interval : "overwriting wrong currentSplitChild";
583 spilledPart.makeCurrentSplitChild();
584
585 if (Debug.isLogEnabled()) {
586 Debug.log("left interval: %s", interval.logString(allocator));
587 Debug.log("spilled interval : %s", spilledPart.logString(allocator));
588 }
589 }
590 }
591 }
592 }
593
594 // called during register allocation
595 private void changeSpillState(Interval interval, int spillPos) {
596 switch (interval.spillState()) {
597 case NoSpillStore: {
598 int defLoopDepth = allocator.blockForId(interval.spillDefinitionPos()).getLoopDepth();
599 int spillLoopDepth = allocator.blockForId(spillPos).getLoopDepth();
600
601 if (defLoopDepth < spillLoopDepth) {
602 /*
603 * The loop depth of the spilling position is higher then the loop depth at the
604 * definition of the interval. Move write to memory out of loop.
605 */
606 if (LinearScan.Options.LIROptLSRAOptimizeSpillPosition.getValue(allocator.getOptions())) {
607 // find best spill position in dominator the tree
608 interval.setSpillState(SpillState.SpillInDominator);
609 } else {
610 // store at definition of the interval
611 interval.setSpillState(SpillState.StoreAtDefinition);
612 }
613 } else {
614 /*
615 * The interval is currently spilled only once, so for now there is no reason to
616 * store the interval at the definition.
617 */
618 interval.setSpillState(SpillState.OneSpillStore);
619 }
620 break;
621 }
622
623 case OneSpillStore: {
624 int defLoopDepth = allocator.blockForId(interval.spillDefinitionPos()).getLoopDepth();
625 int spillLoopDepth = allocator.blockForId(spillPos).getLoopDepth();
626
627 if (defLoopDepth <= spillLoopDepth) {
628 if (LinearScan.Options.LIROptLSRAOptimizeSpillPosition.getValue(allocator.getOptions())) {
629 // the interval is spilled more then once
630 interval.setSpillState(SpillState.SpillInDominator);
631 } else {
632 // It is better to store it to memory at the definition.
633 interval.setSpillState(SpillState.StoreAtDefinition);
634 }
635 }
636 break;
637 }
638
639 case SpillInDominator:
640 case StoreAtDefinition:
641 case StartInMemory:
642 case NoOptimization:
643 case NoDefinitionFound:
644 // nothing to do
645 break;
646
647 default:
648 throw GraalError.shouldNotReachHere("other states not allowed at this time");
649 }
650 }
651
652 /**
653 * This is called for every interval that is assigned to a stack slot.
654 */
655 protected void handleSpillSlot(Interval interval) {
656 assert interval.location() != null && (interval.canMaterialize() || isStackSlotValue(interval.location())) : "interval not assigned to a stack slot " + interval;
657 // Do nothing. Stack slots are not processed in this implementation.
658 }
659
660 void splitStackInterval(Interval interval) {
661 int minSplitPos = currentPosition + 1;
662 int maxSplitPos = Math.min(interval.firstUsage(RegisterPriority.ShouldHaveRegister), interval.to());
663
664 splitBeforeUsage(interval, minSplitPos, maxSplitPos);
665 }
666
667 void splitWhenPartialRegisterAvailable(Interval interval, int registerAvailableUntil) {
668 int minSplitPos = Math.max(interval.previousUsage(RegisterPriority.ShouldHaveRegister, registerAvailableUntil), interval.from() + 1);
669 splitBeforeUsage(interval, minSplitPos, registerAvailableUntil);
670 }
671
672 void splitAndSpillInterval(Interval interval) {
673 assert interval.state == State.Active || interval.state == State.Inactive : "other states not allowed";
674
675 int currentPos = currentPosition;
676 if (interval.state == State.Inactive) {
677 // the interval is currently inactive, so no spill slot is needed for now.
678 // when the split part is activated, the interval has a new chance to get a register,
679 // so in the best case no stack slot is necessary
680 assert interval.hasHoleBetween(currentPos - 1, currentPos + 1) : "interval can not be inactive otherwise";
681 splitBeforeUsage(interval, currentPos + 1, currentPos + 1);
682
683 } else {
684 // search the position where the interval must have a register and split
685 // at the optimal position before.
686 // The new created part is added to the unhandled list and will get a register
687 // when it is activated
688 int minSplitPos = currentPos + 1;
689 int maxSplitPos = Math.min(interval.nextUsage(RegisterPriority.MustHaveRegister, minSplitPos), interval.to());
690
691 splitBeforeUsage(interval, minSplitPos, maxSplitPos);
692
693 assert interval.nextUsage(RegisterPriority.MustHaveRegister, currentPos) == Integer.MAX_VALUE : "the remaining part is spilled to stack and therefore has no register";
694 splitForSpilling(interval);
695 }
696 }
697
698 @SuppressWarnings("try")
699 boolean allocFreeRegister(Interval interval) {
700 try (Indent indent = Debug.logAndIndent("trying to find free register for %s", interval)) {
701
702 initUseLists(true);
703 freeExcludeActiveFixed();
704 freeExcludeActiveAny();
705 freeCollectInactiveFixed(interval);
706 freeCollectInactiveAny(interval);
707 // freeCollectUnhandled(fixedKind, cur);
708 assert unhandledLists.get(RegisterBinding.Fixed).isEndMarker() : "must not have unhandled fixed intervals because all fixed intervals have a use at position 0";
709
710 // usePos contains the start of the next interval that has this register assigned
711 // (either as a fixed register or a normal allocated register in the past)
712 // only intervals overlapping with cur are processed, non-overlapping invervals can be
713 // ignored safely
714 if (Debug.isLogEnabled()) {
715 // Enable this logging to see all register states
716 try (Indent indent2 = Debug.logAndIndent("state of registers:")) {
717 for (Register register : availableRegs) {
718 int i = register.number;
719 Debug.log("reg %d: usePos: %d", register.number, usePos[i]);
720 }
721 }
722 }
723
724 Register hint = null;
725 Interval locationHint = interval.locationHint(true);
726 if (locationHint != null && locationHint.location() != null && isRegister(locationHint.location())) {
727 hint = asRegister(locationHint.location());
728 if (Debug.isLogEnabled()) {
729 Debug.log("hint register %d from interval %s", hint.number, locationHint);
730 }
731 }
732 assert interval.location() == null : "register already assigned to interval";
733
734 // the register must be free at least until this position
735 int regNeededUntil = interval.from() + 1;
736 int intervalTo = interval.to();
737
738 boolean needSplit = false;
739 int splitPos = -1;
740
741 Register reg = null;
742 Register minFullReg = null;
743 Register maxPartialReg = null;
744
745 for (Register availableReg : availableRegs) {
746 int number = availableReg.number;
747 if (usePos[number] >= intervalTo) {
748 // this register is free for the full interval
749 if (minFullReg == null || availableReg.equals(hint) || (usePos[number] < usePos[minFullReg.number] && !minFullReg.equals(hint))) {
750 minFullReg = availableReg;
751 }
752 } else if (usePos[number] > regNeededUntil) {
753 // this register is at least free until regNeededUntil
754 if (maxPartialReg == null || availableReg.equals(hint) || (usePos[number] > usePos[maxPartialReg.number] && !maxPartialReg.equals(hint))) {
755 maxPartialReg = availableReg;
756 }
757 }
758 }
759
760 if (minFullReg != null) {
761 reg = minFullReg;
762 } else if (maxPartialReg != null) {
763 needSplit = true;
764 reg = maxPartialReg;
765 } else {
766 return false;
767 }
768
769 splitPos = usePos[reg.number];
770 interval.assignLocation(reg.asValue(interval.kind()));
771 if (Debug.isLogEnabled()) {
772 Debug.log("selected register %d", reg.number);
773 }
774
775 assert splitPos > 0 : "invalid splitPos";
776 if (needSplit) {
777 // register not available for full interval, so split it
778 splitWhenPartialRegisterAvailable(interval, splitPos);
779 }
780 // only return true if interval is completely assigned
781 return true;
782 }
783 }
784
785 void splitAndSpillIntersectingIntervals(Register reg) {
786 assert reg != null : "no register assigned";
787
788 for (int i = 0; i < spillIntervals[reg.number].size(); i++) {
789 Interval interval = spillIntervals[reg.number].get(i);
790 removeFromList(interval);
791 splitAndSpillInterval(interval);
792 }
793 }
794
795 // Split an Interval and spill it to memory so that cur can be placed in a register
796 @SuppressWarnings("try")
797 void allocLockedRegister(Interval interval) {
798 try (Indent indent = Debug.logAndIndent("alloc locked register: need to split and spill to get register for %s", interval)) {
799
800 // the register must be free at least until this position
801 int firstUsage = interval.firstUsage(RegisterPriority.MustHaveRegister);
802 int firstShouldHaveUsage = interval.firstUsage(RegisterPriority.ShouldHaveRegister);
803 int regNeededUntil = Math.min(firstUsage, interval.from() + 1);
804 int intervalTo = interval.to();
805 assert regNeededUntil >= 0 && regNeededUntil < Integer.MAX_VALUE : "interval has no use";
806
807 Register reg;
808 Register ignore;
809 /*
810 * In the common case we don't spill registers that have _any_ use position that is
811 * closer than the next use of the current interval, but if we can't spill the current
812 * interval we weaken this strategy and also allow spilling of intervals that have a
813 * non-mandatory requirements (no MustHaveRegister use position).
814 */
815 for (RegisterPriority registerPriority = RegisterPriority.LiveAtLoopEnd; true; registerPriority = RegisterPriority.MustHaveRegister) {
816 // collect current usage of registers
817 initUseLists(false);
818 spillExcludeActiveFixed();
819 // spillBlockUnhandledFixed(cur);
820 assert unhandledLists.get(RegisterBinding.Fixed).isEndMarker() : "must not have unhandled fixed intervals because all fixed intervals have a use at position 0";
821 spillBlockInactiveFixed(interval);
822 spillCollectActiveAny(registerPriority);
823 spillCollectInactiveAny(interval);
824 if (Debug.isLogEnabled()) {
825 printRegisterState();
826 }
827
828 reg = null;
829 ignore = interval.location() != null && isRegister(interval.location()) ? asRegister(interval.location()) : null;
830
831 for (Register availableReg : availableRegs) {
832 int number = availableReg.number;
833 if (availableReg.equals(ignore)) {
834 // this register must be ignored
835 } else if (usePos[number] > regNeededUntil) {
836 if (reg == null || (usePos[number] > usePos[reg.number])) {
837 reg = availableReg;
838 }
839 }
840 }
841
842 int regUsePos = (reg == null ? 0 : usePos[reg.number]);
843 if (regUsePos <= firstShouldHaveUsage) {
844 if (Debug.isLogEnabled()) {
845 Debug.log("able to spill current interval. firstUsage(register): %d, usePos: %d", firstUsage, regUsePos);
846 }
847
848 if (firstUsage <= interval.from() + 1) {
849 if (registerPriority.equals(RegisterPriority.LiveAtLoopEnd)) {
850 /*
851 * Tool of last resort: we can not spill the current interval so we try
852 * to spill an active interval that has a usage but do not require a
853 * register.
854 */
855 Debug.log("retry with register priority must have register");
856 continue;
857 }
858 String description = generateOutOfRegErrorMsg(interval, firstUsage, availableRegs);
859 /*
860 * assign a reasonable register and do a bailout in product mode to avoid
861 * errors
862 */
863 allocator.assignSpillSlot(interval);
864 Debug.dump(Debug.INFO_LEVEL, allocator.getLIR(), description);
865 allocator.printIntervals(description);
866 throw new OutOfRegistersException("LinearScan: no register found", description);
867 }
868
869 splitAndSpillInterval(interval);
870 return;
871 }
872 break;
873 }
874
875 boolean needSplit = blockPos[reg.number] <= intervalTo;
876
877 int splitPos = blockPos[reg.number];
878
879 if (Debug.isLogEnabled()) {
880 Debug.log("decided to use register %d", reg.number);
881 }
882 assert splitPos > 0 : "invalid splitPos";
883 assert needSplit || splitPos > interval.from() : "splitting interval at from";
884
885 interval.assignLocation(reg.asValue(interval.kind()));
886 if (needSplit) {
887 // register not available for full interval : so split it
888 splitWhenPartialRegisterAvailable(interval, splitPos);
889 }
890
891 // perform splitting and spilling for all affected intervals
892 splitAndSpillIntersectingIntervals(reg);
893 return;
894 }
895 }
896
897 private static String generateOutOfRegErrorMsg(Interval interval, int firstUsage, Register[] availableRegs) {
898 return "Cannot spill interval (" + interval + ") that is used in first instruction (possible reason: no register found) firstUsage=" + firstUsage +
899 ", interval.from()=" + interval.from() + "; already used candidates: " + Arrays.toString(availableRegs);
900 }
901
902 @SuppressWarnings("try")
903 void printRegisterState() {
904 try (Indent indent2 = Debug.logAndIndent("state of registers:")) {
905 for (Register reg : availableRegs) {
906 int i = reg.number;
907 try (Indent indent3 = Debug.logAndIndent("reg %d: usePos: %d, blockPos: %d, intervals: ", i, usePos[i], blockPos[i])) {
908 for (int j = 0; j < spillIntervals[i].size(); j++) {
909 Debug.log("%s ", spillIntervals[i].get(j));
910 }
911 }
912 }
913 }
914 }
915
916 boolean noAllocationPossible(Interval interval) {
917 if (allocator.callKillsRegisters()) {
918 // fast calculation of intervals that can never get a register because the
919 // the next instruction is a call that blocks all registers
920 // Note: this only works if a call kills all registers
921
922 // check if this interval is the result of a split operation
923 // (an interval got a register until this position)
924 int pos = interval.from();
925 if (isOdd(pos)) {
926 // the current instruction is a call that blocks all registers
927 if (pos < allocator.maxOpId() && allocator.hasCall(pos + 1) && interval.to() > pos + 1) {
928 if (Debug.isLogEnabled()) {
929 Debug.log("free register cannot be available because all registers blocked by following call");
930 }
931
932 // safety check that there is really no register available
933 assert !allocFreeRegister(interval) : "found a register for this interval";
934 return true;
935 }
936 }
937 }
938 return false;
939 }
940
941 void initVarsForAlloc(Interval interval) {
942 AllocatableRegisters allocatableRegisters = allocator.getRegisterAllocationConfig().getAllocatableRegisters(interval.kind().getPlatformKind());
943 availableRegs = allocatableRegisters.allocatableRegisters;
944 minReg = allocatableRegisters.minRegisterNumber;
945 maxReg = allocatableRegisters.maxRegisterNumber;
946 }
947
948 static boolean isMove(LIRInstruction op, Interval from, Interval to) {
949 if (ValueMoveOp.isValueMoveOp(op)) {
950 ValueMoveOp move = ValueMoveOp.asValueMoveOp(op);
951 if (isVariable(move.getInput()) && isVariable(move.getResult())) {
952 return move.getInput() != null && move.getInput().equals(from.operand) && move.getResult() != null && move.getResult().equals(to.operand);
953 }
954 }
955 return false;
956 }
957
958 // optimization (especially for phi functions of nested loops):
959 // assign same spill slot to non-intersecting intervals
960 void combineSpilledIntervals(Interval interval) {
961 if (interval.isSplitChild()) {
962 // optimization is only suitable for split parents
963 return;
964 }
965
966 Interval registerHint = interval.locationHint(false);
967 if (registerHint == null) {
968 // cur is not the target of a move : otherwise registerHint would be set
969 return;
970 }
971 assert registerHint.isSplitParent() : "register hint must be split parent";
972
973 if (interval.spillState() != SpillState.NoOptimization || registerHint.spillState() != SpillState.NoOptimization) {
974 // combining the stack slots for intervals where spill move optimization is applied
975 // is not benefitial and would cause problems
976 return;
977 }
978
979 int beginPos = interval.from();
980 int endPos = interval.to();
981 if (endPos > allocator.maxOpId() || isOdd(beginPos) || isOdd(endPos)) {
982 // safety check that lirOpWithId is allowed
983 return;
984 }
985
986 if (!isMove(allocator.instructionForId(beginPos), registerHint, interval) || !isMove(allocator.instructionForId(endPos), interval, registerHint)) {
987 // cur and registerHint are not connected with two moves
988 return;
989 }
990
991 Interval beginHint = registerHint.getSplitChildAtOpId(beginPos, LIRInstruction.OperandMode.USE, allocator);
992 Interval endHint = registerHint.getSplitChildAtOpId(endPos, LIRInstruction.OperandMode.DEF, allocator);
993 if (beginHint == endHint || beginHint.to() != beginPos || endHint.from() != endPos) {
994 // registerHint must be split : otherwise the re-writing of use positions does not work
995 return;
996 }
997
998 assert beginHint.location() != null : "must have register assigned";
999 assert endHint.location() == null : "must not have register assigned";
1000 assert interval.firstUsage(RegisterPriority.MustHaveRegister) == beginPos : "must have use position at begin of interval because of move";
1001 assert endHint.firstUsage(RegisterPriority.MustHaveRegister) == endPos : "must have use position at begin of interval because of move";
1002
1003 if (isRegister(beginHint.location())) {
1004 // registerHint is not spilled at beginPos : so it would not be benefitial to
1005 // immediately spill cur
1006 return;
1007 }
1008 assert registerHint.spillSlot() != null : "must be set when part of interval was spilled";
1009
1010 // modify intervals such that cur gets the same stack slot as registerHint
1011 // delete use positions to prevent the intervals to get a register at beginning
1012 interval.setSpillSlot(registerHint.spillSlot());
1013 interval.removeFirstUsePos();
1014 endHint.removeFirstUsePos();
1015 }
1016
1017 // allocate a physical register or memory location to an interval
1018 @Override
1019 @SuppressWarnings("try")
1020 protected boolean activateCurrent(Interval interval) {
1021 boolean result = true;
1022
1023 try (Indent indent = Debug.logAndIndent("activating interval %s, splitParent: %d", interval, interval.splitParent().operandNumber)) {
1024
1025 final Value operand = interval.operand;
1026 if (interval.location() != null && isStackSlotValue(interval.location())) {
1027 // activating an interval that has a stack slot assigned . split it at first use
1028 // position
1029 // used for method parameters
1030 if (Debug.isLogEnabled()) {
1031 Debug.log("interval has spill slot assigned (method parameter) . split it before first use");
1032 }
1033 splitStackInterval(interval);
1034 result = false;
1035
1036 } else {
1037 if (interval.location() == null) {
1038 // interval has not assigned register . normal allocation
1039 // (this is the normal case for most intervals)
1040 if (Debug.isLogEnabled()) {
1041 Debug.log("normal allocation of register");
1042 }
1043
1044 // assign same spill slot to non-intersecting intervals
1045 combineSpilledIntervals(interval);
1046
1047 initVarsForAlloc(interval);
1048 if (noAllocationPossible(interval) || !allocFreeRegister(interval)) {
1049 // no empty register available.
1050 // split and spill another interval so that this interval gets a register
1051 allocLockedRegister(interval);
1052 }
1053
1054 // spilled intervals need not be move to active-list
1055 if (!isRegister(interval.location())) {
1056 result = false;
1057 }
1058 }
1059 }
1060
1061 // load spilled values that become active from stack slot to register
1062 if (interval.insertMoveWhenActivated()) {
1063 assert interval.isSplitChild();
1064 assert interval.currentSplitChild() != null;
1065 assert !interval.currentSplitChild().operand.equals(operand) : "cannot insert move between same interval";
1066 if (Debug.isLogEnabled()) {
1067 Debug.log("Inserting move from interval %d to %d because insertMoveWhenActivated is set", interval.currentSplitChild().operandNumber, interval.operandNumber);
1068 }
1069
1070 insertMove(interval.from(), interval.currentSplitChild(), interval);
1071 }
1072 interval.makeCurrentSplitChild();
1073
1074 }
1075
1076 return result; // true = interval is moved to active list
1077 }
1078
1079 public void finishAllocation() {
1080 // must be called when all intervals are allocated
1081 moveResolver.resolveAndAppendMoves();
1082 }
1083 }