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