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