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 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.BitSet;
34
35 import org.graalvm.compiler.core.common.alloc.RegisterAllocationConfig.AllocatableRegisters;
36 import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
37 import org.graalvm.compiler.core.common.util.Util;
38 import org.graalvm.compiler.debug.Debug;
39 import org.graalvm.compiler.debug.GraalError;
40 import org.graalvm.compiler.debug.Indent;
41 import org.graalvm.compiler.lir.LIRInstruction;
42 import org.graalvm.compiler.lir.LIRValueUtil;
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.TraceInterval.State;
50 import org.graalvm.compiler.lir.alloc.trace.lsra.TraceLinearScanPhase.TraceLinearScan;
51 import org.graalvm.compiler.lir.ssa.SSAUtil;
52
53 import jdk.vm.ci.code.Register;
54 import jdk.vm.ci.meta.Value;
55
56 /**
57 */
58 final class TraceLinearScanWalker {
158 prev.next = cur.next;
159 }
160 return newHead;
161 }
162
163 private Register[] availableRegs;
164
165 private final int[] usePos;
166 private final int[] blockPos;
167 private final BitSet isInMemory;
168
169 private final ArrayList<TraceInterval>[] spillIntervals;
170
171 private TraceLocalMoveResolver moveResolver; // for ordering spill moves
172
173 private int minReg;
174
175 private int maxReg;
176
177 private final TraceLinearScan allocator;
178
179 /**
180 * Sorted list of intervals, not live before the current position.
181 */
182 private TraceInterval unhandledAnyList;
183
184 /**
185 * Sorted list of intervals, live at the current position.
186 */
187 private TraceInterval activeAnyList;
188
189 private FixedInterval activeFixedList;
190
191 /**
192 * Sorted list of intervals in a life time hole at the current position.
193 */
194 private FixedInterval inactiveFixedList;
195
196 /**
197 * The current position (intercept point through the intervals).
205 * value, and allocate a "real" list only on demand in {@link #setUsePos}.
206 */
207 private static final ArrayList<TraceInterval> EMPTY_LIST = new ArrayList<>(0);
208
209 // accessors mapped to same functions in class LinearScan
210 private int blockCount() {
211 return allocator.blockCount();
212 }
213
214 private AbstractBlockBase<?> blockAt(int idx) {
215 return allocator.blockAt(idx);
216 }
217
218 @SuppressWarnings("unused")
219 private AbstractBlockBase<?> blockOfOpWithId(int opId) {
220 return allocator.blockForId(opId);
221 }
222
223 TraceLinearScanWalker(TraceLinearScan allocator, FixedInterval unhandledFixedFirst, TraceInterval unhandledAnyFirst) {
224 this.allocator = allocator;
225
226 unhandledAnyList = unhandledAnyFirst;
227 activeAnyList = TraceInterval.EndMarker;
228 activeFixedList = FixedInterval.EndMarker;
229 // we don't need a separate unhandled list for fixed.
230 inactiveFixedList = unhandledFixedFirst;
231 currentPosition = -1;
232
233 moveResolver = allocator.createMoveResolver();
234 int numRegs = allocator.getRegisters().size();
235 spillIntervals = Util.uncheckedCast(new ArrayList<?>[numRegs]);
236 for (int i = 0; i < numRegs; i++) {
237 spillIntervals[i] = EMPTY_LIST;
238 }
239 usePos = new int[numRegs];
240 blockPos = new int[numRegs];
241 isInMemory = new BitSet(numRegs);
242 }
243
244 private void initUseLists(boolean onlyProcessUsePos) {
449
450 // minimal block probability
451 double minProbability = maxBlock.probability();
452 for (int i = toBlockNr - 1; i >= fromBlockNr; i--) {
453 AbstractBlockBase<?> cur = blockAt(i);
454
455 if (cur.probability() < minProbability) {
456 // Block with lower probability found. Split at the end of this block.
457 minProbability = cur.probability();
458 optimalSplitPos = allocator.getLastLirInstructionId(cur) + 2;
459 }
460 }
461 assert optimalSplitPos > allocator.maxOpId() || allocator.isBlockBegin(optimalSplitPos) : "algorithm must move split pos to block boundary";
462
463 return optimalSplitPos;
464 }
465
466 @SuppressWarnings({"unused"})
467 private int findOptimalSplitPos(TraceInterval interval, int minSplitPos, int maxSplitPos, boolean doLoopOptimization) {
468 int optimalSplitPos = findOptimalSplitPos0(minSplitPos, maxSplitPos);
469 if (Debug.isLogEnabled()) {
470 Debug.log("optimal split position: %d", optimalSplitPos);
471 }
472 return optimalSplitPos;
473 }
474
475 private int findOptimalSplitPos0(int minSplitPos, int maxSplitPos) {
476 if (minSplitPos == maxSplitPos) {
477 // trivial case, no optimization of split position possible
478 if (Debug.isLogEnabled()) {
479 Debug.log("min-pos and max-pos are equal, no optimization possible");
480 }
481 return minSplitPos;
482
483 }
484 assert minSplitPos < maxSplitPos : "must be true then";
485 assert minSplitPos > 0 : "cannot access minSplitPos - 1 otherwise";
486
487 // reason for using minSplitPos - 1: when the minimal split pos is exactly at the
488 // beginning of a block, then minSplitPos is also a possible split position.
489 // Use the block before as minBlock, because then minBlock.lastLirInstructionId() + 2 ==
490 // minSplitPos
491 AbstractBlockBase<?> minBlock = allocator.blockForId(minSplitPos - 1);
492
493 // reason for using maxSplitPos - 1: otherwise there would be an assert on failure
494 // when an interval ends at the end of the last block of the method
495 // (in this case, maxSplitPos == allocator().maxLirOpId() + 2, and there is no
496 // block at this opId)
497 AbstractBlockBase<?> maxBlock = allocator.blockForId(maxSplitPos - 1);
498
499 assert minBlock.getLinearScanNumber() <= maxBlock.getLinearScanNumber() : "invalid order";
500 if (minBlock == maxBlock) {
501 // split position cannot be moved to block boundary : so split as late as possible
502 if (Debug.isLogEnabled()) {
503 Debug.log("cannot move split pos to block boundary because minPos and maxPos are in same block");
504 }
505 return maxSplitPos;
506
507 }
508 // seach optimal block boundary between minSplitPos and maxSplitPos
509 if (Debug.isLogEnabled()) {
510 Debug.log("moving split pos to optimal block boundary between block B%d and B%d", minBlock.getId(), maxBlock.getId());
511 }
512
513 return findOptimalSplitPos(minBlock, maxBlock, maxSplitPos);
514 }
515
516 // split an interval at the optimal position between minSplitPos and
517 // maxSplitPos in two parts:
518 // 1) the left part has already a location assigned
519 // 2) the right part is sorted into to the unhandled-list
520 @SuppressWarnings("try")
521 private void splitBeforeUsage(TraceInterval interval, int minSplitPos, int maxSplitPos) {
522
523 try (Indent indent = Debug.logAndIndent("splitting interval %s between %d and %d", interval, minSplitPos, maxSplitPos)) {
524
525 assert interval.from() < minSplitPos : "cannot split at start of interval";
526 assert currentPosition < minSplitPos : "cannot split before current position";
527 assert minSplitPos <= maxSplitPos : "invalid order";
528 assert maxSplitPos <= interval.to() : "cannot split after end of interval";
529
530 final int optimalSplitPos = findOptimalSplitPos(interval, minSplitPos, maxSplitPos, true);
531
532 if (optimalSplitPos == interval.to() && interval.nextUsage(RegisterPriority.MustHaveRegister, minSplitPos) == Integer.MAX_VALUE) {
533 // the split position would be just before the end of the interval
534 // . no split at all necessary
535 if (Debug.isLogEnabled()) {
536 Debug.log("no split necessary because optimal split position is at end of interval");
537 }
538 return;
539 }
540 // must calculate this before the actual split is performed and before split position is
541 // moved to odd opId
542 final int optimalSplitPosFinal;
543 boolean blockBegin = allocator.isBlockBegin(optimalSplitPos);
544 assert blockBegin || !allocator.isBlockBegin(optimalSplitPos - 1);
545 boolean moveNecessary = !blockBegin;
546 if (blockBegin) {
547 optimalSplitPosFinal = optimalSplitPos;
548 } else {
549 // move position before actual instruction (odd opId)
550 optimalSplitPosFinal = (optimalSplitPos - 1) | 1;
551 }
552
553 // TODO( je) better define what min split pos max split pos mean.
554 assert minSplitPos <= optimalSplitPosFinal && optimalSplitPosFinal <= maxSplitPos || minSplitPos == maxSplitPos && optimalSplitPosFinal == minSplitPos - 1 : "out of range";
555 assert optimalSplitPosFinal <= interval.to() : "cannot split after end of interval";
556 assert optimalSplitPosFinal > interval.from() : "cannot split at start of interval";
557
558 if (Debug.isLogEnabled()) {
559 Debug.log("splitting at position %d", optimalSplitPosFinal);
560 }
561 assert optimalSplitPosFinal > currentPosition : "Can not split interval " + interval + " at current position: " + currentPosition;
562
563 assert blockBegin || ((optimalSplitPosFinal & 1) == 1) : "split pos must be odd when not on block boundary";
564 assert !blockBegin || ((optimalSplitPosFinal & 1) == 0) : "split pos must be even on block boundary";
565
566 // TODO (je) duplicate code. try to fold
567 if (optimalSplitPosFinal == interval.to() && interval.nextUsage(RegisterPriority.MustHaveRegister, minSplitPos) == Integer.MAX_VALUE) {
568 // the split position would be just before the end of the interval
569 // . no split at all necessary
570 if (Debug.isLogEnabled()) {
571 Debug.log("no split necessary because optimal split position is at end of interval");
572 }
573 return;
574 }
575 TraceInterval splitPart = interval.split(optimalSplitPosFinal, allocator);
576
577 splitPart.setInsertMoveWhenActivated(moveNecessary);
578
579 assert splitPart.from() >= currentPosition : "cannot append new interval before current walk position";
580 unhandledAnyList = TraceLinearScanWalker.addToListSortedByStartAndUsePositions(unhandledAnyList, splitPart);
581
582 if (Debug.isLogEnabled()) {
583 Debug.log("left interval %s: %s", moveNecessary ? " " : "", interval.logString());
584 Debug.log("right interval %s: %s", moveNecessary ? "(move)" : "", splitPart.logString());
585 }
586 }
587 }
588
589 // split an interval at the optimal position between minSplitPos and
590 // maxSplitPos in two parts:
591 // 1) the left part has already a location assigned
592 // 2) the right part is always on the stack and therefore ignored in further processing
593 @SuppressWarnings("try")
594 private void splitForSpilling(TraceInterval interval) {
595 // calculate allowed range of splitting position
596 int maxSplitPos = currentPosition;
597 int previousUsage = interval.previousUsage(RegisterPriority.ShouldHaveRegister, maxSplitPos);
598 if (previousUsage == currentPosition) {
599 /*
600 * If there is a usage with ShouldHaveRegister priority at the current position fall
601 * back to MustHaveRegister priority. This only happens if register priority was
602 * downgraded to MustHaveRegister in #allocLockedRegister.
603 */
604 previousUsage = interval.previousUsage(RegisterPriority.MustHaveRegister, maxSplitPos);
605 }
606 int minSplitPos = Math.max(previousUsage + 1, interval.from());
607
608 try (Indent indent = Debug.logAndIndent("splitting and spilling interval %s between %d and %d", interval, minSplitPos, maxSplitPos)) {
609
610 assert interval.from() <= minSplitPos : "cannot split before start of interval";
611 assert minSplitPos <= maxSplitPos : "invalid order";
612 assert maxSplitPos < interval.to() : "cannot split at end end of interval";
613 assert currentPosition < interval.to() : "interval must not end before current position";
614
615 if (minSplitPos == interval.from()) {
616 // the whole interval is never used, so spill it entirely to memory
617
618 try (Indent indent2 = Debug.logAndIndent("spilling entire interval because split pos is at beginning of interval (use positions: %d)", interval.numUsePos())) {
619
620 assert interval.firstUsage(RegisterPriority.MustHaveRegister) > currentPosition : String.format("interval %s must not have use position before currentPosition %d", interval,
621 currentPosition);
622
623 allocator.assignSpillSlot(interval);
624 handleSpillSlot(interval);
625 changeSpillState(interval, minSplitPos);
626
627 // Also kick parent intervals out of register to memory when they have no use
628 // position. This avoids short interval in register surrounded by intervals in
629 // memory . avoid useless moves from memory to register and back
630 TraceInterval parent = interval;
631 while (parent != null && parent.isSplitChild()) {
632 parent = parent.getSplitChildBeforeOpId(parent.from());
633
634 if (isRegister(parent.location())) {
635 if (parent.firstUsage(RegisterPriority.ShouldHaveRegister) == Integer.MAX_VALUE) {
636 // parent is never used, so kick it out of its assigned register
637 if (Debug.isLogEnabled()) {
638 Debug.log("kicking out interval %d out of its register because it is never used", parent.operandNumber);
639 }
640 allocator.assignSpillSlot(parent);
641 handleSpillSlot(parent);
642 } else {
643 // do not go further back because the register is actually used by
644 // the interval
645 parent = null;
646 }
647 }
648 }
649 }
650
651 } else {
652 // search optimal split pos, split interval and spill only the right hand part
653 int optimalSplitPos = findOptimalSplitPos(interval, minSplitPos, maxSplitPos, false);
654
655 assert minSplitPos <= optimalSplitPos && optimalSplitPos <= maxSplitPos : "out of range";
656 assert optimalSplitPos < interval.to() : "cannot split at end of interval";
657 assert optimalSplitPos >= interval.from() : "cannot split before start of interval";
658
659 if (!allocator.isBlockBegin(optimalSplitPos)) {
660 // move position before actual instruction (odd opId)
661 optimalSplitPos = (optimalSplitPos - 1) | 1;
662 }
663
664 try (Indent indent2 = Debug.logAndIndent("splitting at position %d", optimalSplitPos)) {
665 assert allocator.isBlockBegin(optimalSplitPos) || ((optimalSplitPos & 1) == 1) : "split pos must be odd when not on block boundary";
666 assert !allocator.isBlockBegin(optimalSplitPos) || ((optimalSplitPos & 1) == 0) : "split pos must be even on block boundary";
667
668 TraceInterval spilledPart = interval.split(optimalSplitPos, allocator);
669 allocator.assignSpillSlot(spilledPart);
670 handleSpillSlot(spilledPart);
671 changeSpillState(spilledPart, optimalSplitPos);
672
673 if (!allocator.isBlockBegin(optimalSplitPos)) {
674 if (Debug.isLogEnabled()) {
675 Debug.log("inserting move from interval %s to %s", interval, spilledPart);
676 }
677 insertMove(optimalSplitPos, interval, spilledPart);
678 } else {
679 if (Debug.isLogEnabled()) {
680 Debug.log("no need to insert move. done by data-flow resolution");
681 }
682 }
683
684 // the currentSplitChild is needed later when moves are inserted for reloading
685 assert spilledPart.currentSplitChild() == interval : "overwriting wrong currentSplitChild";
686 spilledPart.makeCurrentSplitChild();
687
688 if (Debug.isLogEnabled()) {
689 Debug.log("left interval: %s", interval.logString());
690 Debug.log("spilled interval : %s", spilledPart.logString());
691 }
692 }
693 }
694 }
695 }
696
697 /**
698 * Change spill state of an interval.
699 *
700 * Note: called during register allocation.
701 *
702 * @param spillPos position of the spill
703 */
704 private void changeSpillState(TraceInterval interval, int spillPos) {
705 if (TraceLinearScanPhase.Options.LIROptTraceRAEliminateSpillMoves.getValue(allocator.getOptions())) {
706 switch (interval.spillState()) {
707 case NoSpillStore:
708 final int minSpillPos = calculateMinSpillPos(interval.spillDefinitionPos(), spillPos);
709 final int maxSpillPos = calculateMaxSpillPos(minSpillPos, spillPos);
710
778 /* Skip block begins. */
779 while (allocator.isBlockBegin(maxSpillPos) && maxSpillPos > minSpillPos) {
780 // -2 is block end, -4 is the instruction before
781 maxSpillPos -= 4;
782 }
783 assert minSpillPos <= maxSpillPos;
784 return maxSpillPos;
785 }
786
787 private boolean isNotBlockBeginOrMerge(int spillPos) {
788 int spillPosEven = spillPos & ~1;
789 return spillPosEven == 0 || !allocator.isBlockBegin(spillPosEven) || SSAUtil.isMerge(allocator.blockForId(spillPosEven));
790 }
791
792 /**
793 * @param minSpillPos minimal spill position
794 * @param maxSpillPos maximal spill position
795 */
796 private int findOptimalSpillPos(int minSpillPos, int maxSpillPos) {
797 int optimalSpillPos = findOptimalSpillPos0(minSpillPos, maxSpillPos) & (~1);
798 if (Debug.isLogEnabled()) {
799 Debug.log("optimal spill position: %d", optimalSpillPos);
800 }
801 return optimalSpillPos;
802 }
803
804 private int findOptimalSpillPos0(int minSpillPos, int maxSpillPos) {
805 if (minSpillPos == maxSpillPos) {
806 // trivial case, no optimization of split position possible
807 if (Debug.isLogEnabled()) {
808 Debug.log("min-pos and max-pos are equal, no optimization possible");
809 }
810 return minSpillPos;
811
812 }
813 assert minSpillPos < maxSpillPos : "must be true then";
814 assert minSpillPos >= 0 : "cannot access minSplitPos - 1 otherwise";
815
816 AbstractBlockBase<?> minBlock = allocator.blockForId(minSpillPos);
817 AbstractBlockBase<?> maxBlock = allocator.blockForId(maxSpillPos);
818
819 assert minBlock.getLinearScanNumber() <= maxBlock.getLinearScanNumber() : "invalid order";
820 if (minBlock == maxBlock) {
821 // split position cannot be moved to block boundary : so split as late as possible
822 if (Debug.isLogEnabled()) {
823 Debug.log("cannot move split pos to block boundary because minPos and maxPos are in same block");
824 }
825 return maxSpillPos;
826
827 }
828 // search optimal block boundary between minSplitPos and maxSplitPos
829 if (Debug.isLogEnabled()) {
830 Debug.log("moving split pos to optimal block boundary between block B%d and B%d", minBlock.getId(), maxBlock.getId());
831 }
832
833 // currently using the same heuristic as for splitting
834 return findOptimalSpillPos(minBlock, maxBlock, maxSpillPos);
835 }
836
837 private int findOptimalSpillPos(AbstractBlockBase<?> minBlock, AbstractBlockBase<?> maxBlock, int maxSplitPos) {
838 int fromBlockNr = minBlock.getLinearScanNumber();
839 int toBlockNr = maxBlock.getLinearScanNumber();
840
841 assert 0 <= fromBlockNr && fromBlockNr < blockCount() : "out of range";
842 assert 0 <= toBlockNr && toBlockNr < blockCount() : "out of range";
843 assert fromBlockNr < toBlockNr : "must cross block boundary";
844
845 /*
846 * Try to split at end of maxBlock. We use last instruction -2 because we want to insert the
847 * move before the block end op. If this would be after maxSplitPos, then use the
848 * maxSplitPos.
849 */
850 int optimalSplitPos = allocator.getLastLirInstructionId(maxBlock) - 2;
893 }
894
895 private void splitWhenPartialRegisterAvailable(TraceInterval interval, int registerAvailableUntil) {
896 int minSplitPos = Math.max(interval.previousUsage(RegisterPriority.ShouldHaveRegister, registerAvailableUntil), interval.from() + 1);
897 splitBeforeUsage(interval, minSplitPos, registerAvailableUntil);
898 }
899
900 private void splitAndSpillInterval(TraceInterval interval) {
901 int currentPos = currentPosition;
902 /*
903 * Search the position where the interval must have a register and split at the optimal
904 * position before. The new created part is added to the unhandled list and will get a
905 * register when it is activated.
906 */
907 int minSplitPos = currentPos + 1;
908 int maxSplitPos = interval.nextUsage(RegisterPriority.MustHaveRegister, minSplitPos);
909
910 if (maxSplitPos <= interval.to()) {
911 splitBeforeUsage(interval, minSplitPos, maxSplitPos);
912 } else {
913 Debug.log("No more usage, no need to split: %s", interval);
914 }
915
916 assert interval.nextUsage(RegisterPriority.MustHaveRegister, currentPos) == Integer.MAX_VALUE : "the remaining part is spilled to stack and therefore has no register";
917 splitForSpilling(interval);
918 }
919
920 @SuppressWarnings("try")
921 private boolean allocFreeRegister(TraceInterval interval) {
922 try (Indent indent = Debug.logAndIndent("trying to find free register for %s", interval)) {
923
924 initUseLists(true);
925 freeExcludeActiveFixed();
926 freeCollectInactiveFixed(interval);
927 freeExcludeActiveAny();
928 // freeCollectUnhandled(fixedKind, cur);
929
930 // usePos contains the start of the next interval that has this register assigned
931 // (either as a fixed register or a normal allocated register in the past)
932 // only intervals overlapping with cur are processed, non-overlapping invervals can be
933 // ignored safely
934 if (Debug.isLogEnabled()) {
935 // Enable this logging to see all register states
936 try (Indent indent2 = Debug.logAndIndent("state of registers:")) {
937 for (Register register : availableRegs) {
938 int i = register.number;
939 Debug.log("reg %d (%s): usePos: %d", register.number, register, usePos[i]);
940 }
941 }
942 }
943
944 Register hint = null;
945 IntervalHint locationHint = interval.locationHint(true);
946 if (locationHint != null && locationHint.location() != null && isRegister(locationHint.location())) {
947 hint = asRegister(locationHint.location());
948 if (Debug.isLogEnabled()) {
949 Debug.log("hint register %3d (%4s) from interval %s", hint.number, hint, locationHint);
950 }
951 }
952 assert interval.location() == null : "register already assigned to interval";
953
954 // the register must be free at least until this position
955 int regNeededUntil = interval.from() + 1;
956 int intervalTo = interval.to();
957
958 boolean needSplit = false;
959 int splitPos = -1;
960
961 Register reg = null;
962 Register minFullReg = null;
963 Register maxPartialReg = null;
964
965 for (Register availableReg : availableRegs) {
966 int number = availableReg.number;
967 if (usePos[number] >= intervalTo) {
968 // this register is free for the full interval
969 if (minFullReg == null || availableReg.equals(hint) || (usePos[number] < usePos[minFullReg.number] && !minFullReg.equals(hint))) {
971 }
972 } else if (usePos[number] > regNeededUntil) {
973 // this register is at least free until regNeededUntil
974 if (maxPartialReg == null || availableReg.equals(hint) || (usePos[number] > usePos[maxPartialReg.number] && !maxPartialReg.equals(hint))) {
975 maxPartialReg = availableReg;
976 }
977 }
978 }
979
980 if (minFullReg != null) {
981 reg = minFullReg;
982 } else if (maxPartialReg != null) {
983 needSplit = true;
984 reg = maxPartialReg;
985 } else {
986 return false;
987 }
988
989 splitPos = usePos[reg.number];
990 interval.assignLocation(reg.asValue(allocator.getKind(interval)));
991 if (Debug.isLogEnabled()) {
992 Debug.log("selected register %d (%s)", reg.number, reg);
993 }
994
995 assert splitPos > 0 : "invalid splitPos";
996 if (needSplit) {
997 // register not available for full interval, so split it
998 splitWhenPartialRegisterAvailable(interval, splitPos);
999 }
1000 // only return true if interval is completely assigned
1001 return true;
1002 }
1003 }
1004
1005 private void splitAndSpillIntersectingIntervals(Register reg) {
1006 assert reg != null : "no register assigned";
1007
1008 for (int i = 0; i < spillIntervals[reg.number].size(); i++) {
1009 TraceInterval interval = spillIntervals[reg.number].get(i);
1010 removeFromList(interval);
1011 splitAndSpillInterval(interval);
1012 }
1013 }
1014
1015 // Split an Interval and spill it to memory so that cur can be placed in a register
1016 @SuppressWarnings("try")
1017 private void allocLockedRegister(TraceInterval interval) {
1018 try (Indent indent = Debug.logAndIndent("alloc locked register: need to split and spill to get register for %s", interval)) {
1019
1020 // the register must be free at least until this position
1021 int firstUsage = interval.firstUsage(RegisterPriority.MustHaveRegister);
1022 int firstShouldHaveUsage = interval.firstUsage(RegisterPriority.ShouldHaveRegister);
1023 int regNeededUntil = Math.min(firstUsage, interval.from() + 1);
1024 int intervalTo = interval.to();
1025 assert regNeededUntil >= 0 && regNeededUntil < Integer.MAX_VALUE : "interval has no use";
1026
1027 Register reg;
1028 Register ignore;
1029 /*
1030 * In the common case we don't spill registers that have _any_ use position that is
1031 * closer than the next use of the current interval, but if we can't spill the current
1032 * interval we weaken this strategy and also allow spilling of intervals that have a
1033 * non-mandatory requirements (no MustHaveRegister use position).
1034 */
1035 for (RegisterPriority registerPriority = RegisterPriority.LiveAtLoopEnd; true; registerPriority = RegisterPriority.MustHaveRegister) {
1036 // collect current usage of registers
1037 initUseLists(false);
1038 spillExcludeActiveFixed();
1039 // spillBlockUnhandledFixed(cur);
1040 spillBlockInactiveFixed(interval);
1041 spillCollectActiveAny(registerPriority);
1042 if (Debug.isLogEnabled()) {
1043 printRegisterState();
1044 }
1045
1046 reg = null;
1047 ignore = interval.location() != null && isRegister(interval.location()) ? asRegister(interval.location()) : null;
1048
1049 for (Register availableReg : availableRegs) {
1050 int number = availableReg.number;
1051 if (availableReg.equals(ignore)) {
1052 // this register must be ignored
1053 } else if (usePos[number] > regNeededUntil) {
1054 /*
1055 * If the use position is the same, prefer registers (active intervals)
1056 * where the value is already on the stack.
1057 */
1058 if (reg == null || (usePos[number] > usePos[reg.number]) || (usePos[number] == usePos[reg.number] && (!isInMemory.get(reg.number) && isInMemory.get(number)))) {
1059 reg = availableReg;
1060 }
1061 }
1062 }
1063
1064 if (Debug.isLogEnabled()) {
1065 Debug.log("Register Selected: %s", reg);
1066 }
1067
1068 int regUsePos = (reg == null ? 0 : usePos[reg.number]);
1069 if (regUsePos <= firstShouldHaveUsage) {
1070 /* Check if there is another interval that is already in memory. */
1071 if (reg == null || interval.inMemoryAt(currentPosition) || !isInMemory.get(reg.number)) {
1072 if (Debug.isLogEnabled()) {
1073 Debug.log("able to spill current interval. firstUsage(register): %d, usePos: %d", firstUsage, regUsePos);
1074 }
1075
1076 if (firstUsage <= interval.from() + 1) {
1077 if (registerPriority.equals(RegisterPriority.LiveAtLoopEnd)) {
1078 /*
1079 * Tool of last resort: we can not spill the current interval so we
1080 * try to spill an active interval that has a usage but do not
1081 * require a register.
1082 */
1083 Debug.log("retry with register priority must have register");
1084 continue;
1085 }
1086 String description = "cannot spill interval (" + interval + ") that is used in first instruction (possible reason: no register found) firstUsage=" + firstUsage +
1087 ", interval.from()=" + interval.from() + "; already used candidates: " + Arrays.toString(availableRegs);
1088 /*
1089 * assign a reasonable register and do a bailout in product mode to
1090 * avoid errors
1091 */
1092 allocator.assignSpillSlot(interval);
1093 if (Debug.isDumpEnabled(Debug.INFO_LEVEL)) {
1094 dumpLIRAndIntervals(description);
1095 }
1096 throw new OutOfRegistersException("LinearScan: no register found", description);
1097 }
1098
1099 splitAndSpillInterval(interval);
1100 return;
1101 }
1102 }
1103 // common case: break out of the loop
1104 break;
1105 }
1106
1107 boolean needSplit = blockPos[reg.number] <= intervalTo;
1108
1109 int splitPos = blockPos[reg.number];
1110
1111 if (Debug.isLogEnabled()) {
1112 Debug.log("decided to use register %d", reg.number);
1113 }
1114 assert splitPos > 0 : "invalid splitPos";
1115 assert needSplit || splitPos > interval.from() : "splitting interval at from";
1116
1117 interval.assignLocation(reg.asValue(allocator.getKind(interval)));
1118 if (needSplit) {
1119 // register not available for full interval : so split it
1120 splitWhenPartialRegisterAvailable(interval, splitPos);
1121 }
1122
1123 // perform splitting and spilling for all affected intervals
1124 splitAndSpillIntersectingIntervals(reg);
1125 return;
1126 }
1127 }
1128
1129 private void dumpLIRAndIntervals(String description) {
1130 Debug.dump(Debug.INFO_LEVEL, allocator.getLIR(), description);
1131 allocator.printIntervals(description);
1132 }
1133
1134 @SuppressWarnings("try")
1135 private void printRegisterState() {
1136 try (Indent indent2 = Debug.logAndIndent("state of registers:")) {
1137 for (Register reg : availableRegs) {
1138 int i = reg.number;
1139 try (Indent indent3 = Debug.logAndIndent("reg %d: usePos: %d, blockPos: %d, inMemory: %b, intervals: ", i, usePos[i], blockPos[i], isInMemory.get(i))) {
1140 for (int j = 0; j < spillIntervals[i].size(); j++) {
1141 Debug.log("%s", spillIntervals[i].get(j));
1142 }
1143 }
1144 }
1145 }
1146 }
1147
1148 private boolean noAllocationPossible(TraceInterval interval) {
1149 if (allocator.callKillsRegisters()) {
1150 // fast calculation of intervals that can never get a register because the
1151 // the next instruction is a call that blocks all registers
1152 // Note: this only works if a call kills all registers
1153
1154 // check if this interval is the result of a split operation
1155 // (an interval got a register until this position)
1156 int pos = interval.from();
1157 if (isOdd(pos)) {
1158 // the current instruction is a call that blocks all registers
1159 if (pos < allocator.maxOpId() && allocator.hasCall(pos + 1) && interval.to() > pos + 1) {
1160 if (Debug.isLogEnabled()) {
1161 Debug.log("free register cannot be available because all registers blocked by following call");
1162 }
1163
1164 // safety check that there is really no register available
1165 assert !allocFreeRegister(interval) : "found a register for this interval";
1166 return true;
1167 }
1168 }
1169 }
1170 return false;
1171 }
1172
1173 private void initVarsForAlloc(TraceInterval interval) {
1174 AllocatableRegisters allocatableRegisters = allocator.getRegisterAllocationConfig().getAllocatableRegisters(allocator.getKind(interval).getPlatformKind());
1175 availableRegs = allocatableRegisters.allocatableRegisters;
1176 minReg = allocatableRegisters.minRegisterNumber;
1177 maxReg = allocatableRegisters.maxRegisterNumber;
1178 }
1179
1180 private static boolean isMove(LIRInstruction op, TraceInterval from, TraceInterval to) {
1181 if (ValueMoveOp.isValueMoveOp(op)) {
1233 assert interval.firstUsage(RegisterPriority.MustHaveRegister) == beginPos : "must have use position at begin of interval because of move";
1234 assert endHint.firstUsage(RegisterPriority.MustHaveRegister) == endPos : "must have use position at begin of interval because of move";
1235
1236 if (isRegister(beginHint.location())) {
1237 // registerHint is not spilled at beginPos : so it would not be benefitial to
1238 // immediately spill cur
1239 return;
1240 }
1241 assert registerHint.spillSlot() != null : "must be set when part of interval was spilled";
1242
1243 // modify intervals such that cur gets the same stack slot as registerHint
1244 // delete use positions to prevent the intervals to get a register at beginning
1245 interval.setSpillSlot(registerHint.spillSlot());
1246 interval.removeFirstUsePos();
1247 endHint.removeFirstUsePos();
1248 }
1249
1250 // allocate a physical register or memory location to an interval
1251 @SuppressWarnings("try")
1252 private boolean activateCurrent(TraceInterval interval) {
1253 if (Debug.isLogEnabled()) {
1254 logCurrentStatus();
1255 }
1256 boolean result = true;
1257
1258 try (Indent indent = Debug.logAndIndent("activating interval %s, splitParent: %d", interval, interval.splitParent().operandNumber)) {
1259
1260 if (interval.location() != null && isStackSlotValue(interval.location())) {
1261 // activating an interval that has a stack slot assigned . split it at first use
1262 // position
1263 // used for method parameters
1264 if (Debug.isLogEnabled()) {
1265 Debug.log("interval has spill slot assigned (method parameter) . split it before first use");
1266 }
1267 splitStackInterval(interval);
1268 result = false;
1269
1270 } else {
1271 if (interval.location() == null) {
1272 // interval has not assigned register . normal allocation
1273 // (this is the normal case for most intervals)
1274 if (Debug.isLogEnabled()) {
1275 Debug.log("normal allocation of register");
1276 }
1277
1278 // assign same spill slot to non-intersecting intervals
1279 combineSpilledIntervals(interval);
1280
1281 initVarsForAlloc(interval);
1282 if (noAllocationPossible(interval) || !allocFreeRegister(interval)) {
1283 // no empty register available.
1284 // split and spill another interval so that this interval gets a register
1285 allocLockedRegister(interval);
1286 }
1287
1288 // spilled intervals need not be move to active-list
1289 if (!isRegister(interval.location())) {
1290 result = false;
1291 }
1292 }
1293 }
1294
1295 // load spilled values that become active from stack slot to register
1296 if (interval.insertMoveWhenActivated()) {
1297 assert interval.isSplitChild();
1298 assert interval.currentSplitChild() != null;
1299 assert interval.currentSplitChild().operandNumber != interval.operandNumber : "cannot insert move between same interval";
1300 if (Debug.isLogEnabled()) {
1301 Debug.log("Inserting move from interval %d to %d because insertMoveWhenActivated is set", interval.currentSplitChild().operandNumber, interval.operandNumber);
1302 }
1303
1304 insertMove(interval.from(), interval.currentSplitChild(), interval);
1305 }
1306 interval.makeCurrentSplitChild();
1307
1308 }
1309
1310 return result; // true = interval is moved to active list
1311 }
1312
1313 void finishAllocation() {
1314 // must be called when all intervals are allocated
1315 moveResolver.resolveAndAppendMoves();
1316 }
1317
1318 @SuppressWarnings("try")
1319 private void logCurrentStatus() {
1320 try (Indent i = Debug.logAndIndent("active:")) {
1321 logList(activeFixedList);
1322 logList(activeAnyList);
1323 }
1324 try (Indent i = Debug.logAndIndent("inactive(fixed):")) {
1325 logList(inactiveFixedList);
1326 }
1327 }
1328
1329 void walk() {
1330 walkTo(Integer.MAX_VALUE);
1331 }
1332
1333 private void removeFromList(TraceInterval interval) {
1334 activeAnyList = TraceLinearScanWalker.removeAny(activeAnyList, interval);
1335 }
1336
1337 /**
1338 * Walks up to {@code from} and updates the state of {@link FixedInterval fixed intervals}.
1339 *
1340 * Fixed intervals can switch back and forth between the states {@link State#Active} and
1341 * {@link State#Inactive} (and eventually to {@link State#Handled} but handled intervals are not
1342 * managed).
1343 */
1344 @SuppressWarnings("try")
1345 private void walkToFixed(State state, int from) {
1346 assert state == State.Active || state == State.Inactive : "wrong state";
1347 FixedInterval prevprev = null;
1348 FixedInterval prev = (state == State.Active) ? activeFixedList : inactiveFixedList;
1349 FixedInterval next = prev;
1350 if (Debug.isLogEnabled()) {
1351 try (Indent i = Debug.logAndIndent("walkToFixed(%s, %d):", state, from)) {
1352 logList(next);
1353 }
1354 }
1355 while (next.currentFrom() <= from) {
1356 FixedInterval cur = next;
1357 next = cur.next;
1358
1359 boolean rangeHasChanged = false;
1360 while (cur.currentTo() <= from) {
1361 cur.nextRange();
1362 rangeHasChanged = true;
1363 }
1364
1365 // also handle move from inactive list to active list
1366 rangeHasChanged = rangeHasChanged || (state == State.Inactive && cur.currentFrom() <= from);
1367
1368 if (rangeHasChanged) {
1369 // remove cur from list
1370 if (prevprev == null) {
1371 if (state == State.Active) {
1372 activeFixedList = next;
1380 TraceInterval.State newState;
1381 if (cur.currentAtEnd()) {
1382 // move to handled state (not maintained as a list)
1383 newState = State.Handled;
1384 } else {
1385 if (cur.currentFrom() <= from) {
1386 // sort into active list
1387 activeFixedList = TraceLinearScanWalker.addToListSortedByCurrentFromPositions(activeFixedList, cur);
1388 newState = State.Active;
1389 } else {
1390 // sort into inactive list
1391 inactiveFixedList = TraceLinearScanWalker.addToListSortedByCurrentFromPositions(inactiveFixedList, cur);
1392 newState = State.Inactive;
1393 }
1394 if (prev == cur) {
1395 assert state == newState;
1396 prevprev = prev;
1397 prev = cur.next;
1398 }
1399 }
1400 intervalMoved(cur, state, newState);
1401 } else {
1402 prevprev = prev;
1403 prev = cur.next;
1404 }
1405 }
1406 }
1407
1408 /**
1409 * Walks up to {@code from} and updates the state of {@link TraceInterval intervals}.
1410 *
1411 * Trace intervals can switch once from {@link State#Unhandled} to {@link State#Active} and then
1412 * to {@link State#Handled} but handled intervals are not managed.
1413 */
1414 @SuppressWarnings("try")
1415 private void walkToAny(int from) {
1416 TraceInterval prevprev = null;
1417 TraceInterval prev = activeAnyList;
1418 TraceInterval next = prev;
1419 if (Debug.isLogEnabled()) {
1420 try (Indent i = Debug.logAndIndent("walkToAny(%d):", from)) {
1421 logList(next);
1422 }
1423 }
1424 while (next.from() <= from) {
1425 TraceInterval cur = next;
1426 next = cur.next;
1427
1428 if (cur.to() <= from) {
1429 // remove cur from list
1430 if (prevprev == null) {
1431 activeAnyList = next;
1432 } else {
1433 prevprev.next = next;
1434 }
1435 intervalMoved(cur, State.Active, State.Handled);
1436 } else {
1437 prevprev = prev;
1438 }
1439 prev = next;
1440 }
1441 }
1442
1443 /**
1444 * Get the next interval from {@linkplain #unhandledAnyList} which starts before or at
1445 * {@code toOpId}. The returned interval is removed.
1446 *
1447 * @postcondition all intervals in {@linkplain #unhandledAnyList} start after {@code toOpId}.
1448 *
1449 * @return The next interval or null if there is no {@linkplain #unhandledAnyList unhandled}
1450 * interval at position {@code toOpId}.
1451 */
1452 private TraceInterval nextInterval(int toOpId) {
1453 TraceInterval any = unhandledAnyList;
1454
1455 if (any != TraceInterval.EndMarker) {
1472 * @postcondition {@link #currentPosition} is set to {@code toOpId}, {@link #activeFixedList}
1473 * and {@link #inactiveFixedList} are populated.
1474 */
1475 @SuppressWarnings("try")
1476 private void walkTo(int toOpId) {
1477 assert currentPosition <= toOpId : "can not walk backwards";
1478 for (TraceInterval currentInterval = nextInterval(toOpId); currentInterval != null; currentInterval = nextInterval(toOpId)) {
1479 int opId = currentInterval.from();
1480
1481 // set currentPosition prior to call of walkTo
1482 currentPosition = opId;
1483
1484 // update unhandled stack intervals
1485 // updateUnhandledStackIntervals(opId);
1486
1487 // call walkTo even if currentPosition == id
1488 walkToFixed(State.Active, opId);
1489 walkToFixed(State.Inactive, opId);
1490 walkToAny(opId);
1491
1492 try (Indent indent = Debug.logAndIndent("walk to op %d", opId)) {
1493 if (activateCurrent(currentInterval)) {
1494 activeAnyList = TraceLinearScanWalker.addToListSortedByFromPositions(activeAnyList, currentInterval);
1495 intervalMoved(currentInterval, State.Unhandled, State.Active);
1496 }
1497 }
1498 }
1499 // set currentPosition prior to call of walkTo
1500 currentPosition = toOpId;
1501
1502 if (currentPosition <= allocator.maxOpId()) {
1503 // update unhandled stack intervals
1504 // updateUnhandledStackIntervals(toOpId);
1505
1506 // call walkTo if still in range
1507 walkToFixed(State.Active, toOpId);
1508 walkToFixed(State.Inactive, toOpId);
1509 walkToAny(toOpId);
1510 }
1511 }
1512
1513 private static void logList(FixedInterval i) {
1514 for (FixedInterval interval = i; interval != FixedInterval.EndMarker; interval = interval.next) {
1515 Debug.log("%s", interval.logString());
1516 }
1517 }
1518
1519 private static void logList(TraceInterval i) {
1520 for (TraceInterval interval = i; interval != TraceInterval.EndMarker; interval = interval.next) {
1521 Debug.log("%s", interval.logString());
1522 }
1523 }
1524
1525 private static void intervalMoved(IntervalHint interval, State from, State to) {
1526 // intervalMoved() is called whenever an interval moves from one interval list to another.
1527 // In the implementation of this method it is prohibited to move the interval to any list.
1528 if (Debug.isLogEnabled()) {
1529 Debug.log("interval moved from %s to %s: %s", from, to, interval.logString());
1530 }
1531 }
1532 }
|
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 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.BitSet;
34
35 import org.graalvm.compiler.core.common.alloc.RegisterAllocationConfig.AllocatableRegisters;
36 import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
37 import org.graalvm.compiler.core.common.util.Util;
38 import org.graalvm.compiler.debug.DebugContext;
39 import org.graalvm.compiler.debug.GraalError;
40 import org.graalvm.compiler.debug.Indent;
41 import org.graalvm.compiler.lir.LIRInstruction;
42 import org.graalvm.compiler.lir.LIRValueUtil;
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.TraceInterval.State;
50 import org.graalvm.compiler.lir.alloc.trace.lsra.TraceLinearScanPhase.TraceLinearScan;
51 import org.graalvm.compiler.lir.ssa.SSAUtil;
52
53 import jdk.vm.ci.code.Register;
54 import jdk.vm.ci.meta.Value;
55
56 /**
57 */
58 final class TraceLinearScanWalker {
158 prev.next = cur.next;
159 }
160 return newHead;
161 }
162
163 private Register[] availableRegs;
164
165 private final int[] usePos;
166 private final int[] blockPos;
167 private final BitSet isInMemory;
168
169 private final ArrayList<TraceInterval>[] spillIntervals;
170
171 private TraceLocalMoveResolver moveResolver; // for ordering spill moves
172
173 private int minReg;
174
175 private int maxReg;
176
177 private final TraceLinearScan allocator;
178 private final DebugContext debug;
179
180 /**
181 * Sorted list of intervals, not live before the current position.
182 */
183 private TraceInterval unhandledAnyList;
184
185 /**
186 * Sorted list of intervals, live at the current position.
187 */
188 private TraceInterval activeAnyList;
189
190 private FixedInterval activeFixedList;
191
192 /**
193 * Sorted list of intervals in a life time hole at the current position.
194 */
195 private FixedInterval inactiveFixedList;
196
197 /**
198 * The current position (intercept point through the intervals).
206 * value, and allocate a "real" list only on demand in {@link #setUsePos}.
207 */
208 private static final ArrayList<TraceInterval> EMPTY_LIST = new ArrayList<>(0);
209
210 // accessors mapped to same functions in class LinearScan
211 private int blockCount() {
212 return allocator.blockCount();
213 }
214
215 private AbstractBlockBase<?> blockAt(int idx) {
216 return allocator.blockAt(idx);
217 }
218
219 @SuppressWarnings("unused")
220 private AbstractBlockBase<?> blockOfOpWithId(int opId) {
221 return allocator.blockForId(opId);
222 }
223
224 TraceLinearScanWalker(TraceLinearScan allocator, FixedInterval unhandledFixedFirst, TraceInterval unhandledAnyFirst) {
225 this.allocator = allocator;
226 this.debug = allocator.getDebug();
227
228 unhandledAnyList = unhandledAnyFirst;
229 activeAnyList = TraceInterval.EndMarker;
230 activeFixedList = FixedInterval.EndMarker;
231 // we don't need a separate unhandled list for fixed.
232 inactiveFixedList = unhandledFixedFirst;
233 currentPosition = -1;
234
235 moveResolver = allocator.createMoveResolver();
236 int numRegs = allocator.getRegisters().size();
237 spillIntervals = Util.uncheckedCast(new ArrayList<?>[numRegs]);
238 for (int i = 0; i < numRegs; i++) {
239 spillIntervals[i] = EMPTY_LIST;
240 }
241 usePos = new int[numRegs];
242 blockPos = new int[numRegs];
243 isInMemory = new BitSet(numRegs);
244 }
245
246 private void initUseLists(boolean onlyProcessUsePos) {
451
452 // minimal block probability
453 double minProbability = maxBlock.probability();
454 for (int i = toBlockNr - 1; i >= fromBlockNr; i--) {
455 AbstractBlockBase<?> cur = blockAt(i);
456
457 if (cur.probability() < minProbability) {
458 // Block with lower probability found. Split at the end of this block.
459 minProbability = cur.probability();
460 optimalSplitPos = allocator.getLastLirInstructionId(cur) + 2;
461 }
462 }
463 assert optimalSplitPos > allocator.maxOpId() || allocator.isBlockBegin(optimalSplitPos) : "algorithm must move split pos to block boundary";
464
465 return optimalSplitPos;
466 }
467
468 @SuppressWarnings({"unused"})
469 private int findOptimalSplitPos(TraceInterval interval, int minSplitPos, int maxSplitPos, boolean doLoopOptimization) {
470 int optimalSplitPos = findOptimalSplitPos0(minSplitPos, maxSplitPos);
471 if (debug.isLogEnabled()) {
472 debug.log("optimal split position: %d", optimalSplitPos);
473 }
474 return optimalSplitPos;
475 }
476
477 private int findOptimalSplitPos0(int minSplitPos, int maxSplitPos) {
478 if (minSplitPos == maxSplitPos) {
479 // trivial case, no optimization of split position possible
480 if (debug.isLogEnabled()) {
481 debug.log("min-pos and max-pos are equal, no optimization possible");
482 }
483 return minSplitPos;
484
485 }
486 assert minSplitPos < maxSplitPos : "must be true then";
487 assert minSplitPos > 0 : "cannot access minSplitPos - 1 otherwise";
488
489 // reason for using minSplitPos - 1: when the minimal split pos is exactly at the
490 // beginning of a block, then minSplitPos is also a possible split position.
491 // Use the block before as minBlock, because then minBlock.lastLirInstructionId() + 2 ==
492 // minSplitPos
493 AbstractBlockBase<?> minBlock = allocator.blockForId(minSplitPos - 1);
494
495 // reason for using maxSplitPos - 1: otherwise there would be an assert on failure
496 // when an interval ends at the end of the last block of the method
497 // (in this case, maxSplitPos == allocator().maxLirOpId() + 2, and there is no
498 // block at this opId)
499 AbstractBlockBase<?> maxBlock = allocator.blockForId(maxSplitPos - 1);
500
501 assert minBlock.getLinearScanNumber() <= maxBlock.getLinearScanNumber() : "invalid order";
502 if (minBlock == maxBlock) {
503 // split position cannot be moved to block boundary : so split as late as possible
504 if (debug.isLogEnabled()) {
505 debug.log("cannot move split pos to block boundary because minPos and maxPos are in same block");
506 }
507 return maxSplitPos;
508
509 }
510 // seach optimal block boundary between minSplitPos and maxSplitPos
511 if (debug.isLogEnabled()) {
512 debug.log("moving split pos to optimal block boundary between block B%d and B%d", minBlock.getId(), maxBlock.getId());
513 }
514
515 return findOptimalSplitPos(minBlock, maxBlock, maxSplitPos);
516 }
517
518 // split an interval at the optimal position between minSplitPos and
519 // maxSplitPos in two parts:
520 // 1) the left part has already a location assigned
521 // 2) the right part is sorted into to the unhandled-list
522 @SuppressWarnings("try")
523 private void splitBeforeUsage(TraceInterval interval, int minSplitPos, int maxSplitPos) {
524
525 try (Indent indent = debug.logAndIndent("splitting interval %s between %d and %d", interval, minSplitPos, maxSplitPos)) {
526
527 assert interval.from() < minSplitPos : "cannot split at start of interval";
528 assert currentPosition < minSplitPos : "cannot split before current position";
529 assert minSplitPos <= maxSplitPos : "invalid order";
530 assert maxSplitPos <= interval.to() : "cannot split after end of interval";
531
532 final int optimalSplitPos = findOptimalSplitPos(interval, minSplitPos, maxSplitPos, true);
533
534 if (optimalSplitPos == interval.to() && interval.nextUsage(RegisterPriority.MustHaveRegister, minSplitPos) == Integer.MAX_VALUE) {
535 // the split position would be just before the end of the interval
536 // . no split at all necessary
537 if (debug.isLogEnabled()) {
538 debug.log("no split necessary because optimal split position is at end of interval");
539 }
540 return;
541 }
542 // must calculate this before the actual split is performed and before split position is
543 // moved to odd opId
544 final int optimalSplitPosFinal;
545 boolean blockBegin = allocator.isBlockBegin(optimalSplitPos);
546 assert blockBegin || !allocator.isBlockBegin(optimalSplitPos - 1);
547 boolean moveNecessary = !blockBegin;
548 if (blockBegin) {
549 optimalSplitPosFinal = optimalSplitPos;
550 } else {
551 // move position before actual instruction (odd opId)
552 optimalSplitPosFinal = (optimalSplitPos - 1) | 1;
553 }
554
555 // TODO( je) better define what min split pos max split pos mean.
556 assert minSplitPos <= optimalSplitPosFinal && optimalSplitPosFinal <= maxSplitPos || minSplitPos == maxSplitPos && optimalSplitPosFinal == minSplitPos - 1 : "out of range";
557 assert optimalSplitPosFinal <= interval.to() : "cannot split after end of interval";
558 assert optimalSplitPosFinal > interval.from() : "cannot split at start of interval";
559
560 if (debug.isLogEnabled()) {
561 debug.log("splitting at position %d", optimalSplitPosFinal);
562 }
563 assert optimalSplitPosFinal > currentPosition : "Can not split interval " + interval + " at current position: " + currentPosition;
564
565 assert blockBegin || ((optimalSplitPosFinal & 1) == 1) : "split pos must be odd when not on block boundary";
566 assert !blockBegin || ((optimalSplitPosFinal & 1) == 0) : "split pos must be even on block boundary";
567
568 // TODO (je) duplicate code. try to fold
569 if (optimalSplitPosFinal == interval.to() && interval.nextUsage(RegisterPriority.MustHaveRegister, minSplitPos) == Integer.MAX_VALUE) {
570 // the split position would be just before the end of the interval
571 // . no split at all necessary
572 if (debug.isLogEnabled()) {
573 debug.log("no split necessary because optimal split position is at end of interval");
574 }
575 return;
576 }
577 TraceInterval splitPart = interval.split(optimalSplitPosFinal, allocator);
578
579 splitPart.setInsertMoveWhenActivated(moveNecessary);
580
581 assert splitPart.from() >= currentPosition : "cannot append new interval before current walk position";
582 unhandledAnyList = TraceLinearScanWalker.addToListSortedByStartAndUsePositions(unhandledAnyList, splitPart);
583
584 if (debug.isLogEnabled()) {
585 debug.log("left interval %s: %s", moveNecessary ? " " : "", interval.logString());
586 debug.log("right interval %s: %s", moveNecessary ? "(move)" : "", splitPart.logString());
587 }
588 }
589 }
590
591 // split an interval at the optimal position between minSplitPos and
592 // maxSplitPos in two parts:
593 // 1) the left part has already a location assigned
594 // 2) the right part is always on the stack and therefore ignored in further processing
595 @SuppressWarnings("try")
596 private void splitForSpilling(TraceInterval interval) {
597 // calculate allowed range of splitting position
598 int maxSplitPos = currentPosition;
599 int previousUsage = interval.previousUsage(RegisterPriority.ShouldHaveRegister, maxSplitPos);
600 if (previousUsage == currentPosition) {
601 /*
602 * If there is a usage with ShouldHaveRegister priority at the current position fall
603 * back to MustHaveRegister priority. This only happens if register priority was
604 * downgraded to MustHaveRegister in #allocLockedRegister.
605 */
606 previousUsage = interval.previousUsage(RegisterPriority.MustHaveRegister, maxSplitPos);
607 }
608 int minSplitPos = Math.max(previousUsage + 1, interval.from());
609
610 try (Indent indent = debug.logAndIndent("splitting and spilling interval %s between %d and %d", interval, minSplitPos, maxSplitPos)) {
611
612 assert interval.from() <= minSplitPos : "cannot split before start of interval";
613 assert minSplitPos <= maxSplitPos : "invalid order";
614 assert maxSplitPos < interval.to() : "cannot split at end end of interval";
615 assert currentPosition < interval.to() : "interval must not end before current position";
616
617 if (minSplitPos == interval.from()) {
618 // the whole interval is never used, so spill it entirely to memory
619
620 try (Indent indent2 = debug.logAndIndent("spilling entire interval because split pos is at beginning of interval (use positions: %d)", interval.numUsePos())) {
621
622 assert interval.firstUsage(RegisterPriority.MustHaveRegister) > currentPosition : String.format("interval %s must not have use position before currentPosition %d", interval,
623 currentPosition);
624
625 allocator.assignSpillSlot(interval);
626 handleSpillSlot(interval);
627 changeSpillState(interval, minSplitPos);
628
629 // Also kick parent intervals out of register to memory when they have no use
630 // position. This avoids short interval in register surrounded by intervals in
631 // memory . avoid useless moves from memory to register and back
632 TraceInterval parent = interval;
633 while (parent != null && parent.isSplitChild()) {
634 parent = parent.getSplitChildBeforeOpId(parent.from());
635
636 if (isRegister(parent.location())) {
637 if (parent.firstUsage(RegisterPriority.ShouldHaveRegister) == Integer.MAX_VALUE) {
638 // parent is never used, so kick it out of its assigned register
639 if (debug.isLogEnabled()) {
640 debug.log("kicking out interval %d out of its register because it is never used", parent.operandNumber);
641 }
642 allocator.assignSpillSlot(parent);
643 handleSpillSlot(parent);
644 } else {
645 // do not go further back because the register is actually used by
646 // the interval
647 parent = null;
648 }
649 }
650 }
651 }
652
653 } else {
654 // search optimal split pos, split interval and spill only the right hand part
655 int optimalSplitPos = findOptimalSplitPos(interval, minSplitPos, maxSplitPos, false);
656
657 assert minSplitPos <= optimalSplitPos && optimalSplitPos <= maxSplitPos : "out of range";
658 assert optimalSplitPos < interval.to() : "cannot split at end of interval";
659 assert optimalSplitPos >= interval.from() : "cannot split before start of interval";
660
661 if (!allocator.isBlockBegin(optimalSplitPos)) {
662 // move position before actual instruction (odd opId)
663 optimalSplitPos = (optimalSplitPos - 1) | 1;
664 }
665
666 try (Indent indent2 = debug.logAndIndent("splitting at position %d", optimalSplitPos)) {
667 assert allocator.isBlockBegin(optimalSplitPos) || ((optimalSplitPos & 1) == 1) : "split pos must be odd when not on block boundary";
668 assert !allocator.isBlockBegin(optimalSplitPos) || ((optimalSplitPos & 1) == 0) : "split pos must be even on block boundary";
669
670 TraceInterval spilledPart = interval.split(optimalSplitPos, allocator);
671 allocator.assignSpillSlot(spilledPart);
672 handleSpillSlot(spilledPart);
673 changeSpillState(spilledPart, optimalSplitPos);
674
675 if (!allocator.isBlockBegin(optimalSplitPos)) {
676 if (debug.isLogEnabled()) {
677 debug.log("inserting move from interval %s to %s", interval, spilledPart);
678 }
679 insertMove(optimalSplitPos, interval, spilledPart);
680 } else {
681 if (debug.isLogEnabled()) {
682 debug.log("no need to insert move. done by data-flow resolution");
683 }
684 }
685
686 // the currentSplitChild is needed later when moves are inserted for reloading
687 assert spilledPart.currentSplitChild() == interval : "overwriting wrong currentSplitChild";
688 spilledPart.makeCurrentSplitChild();
689
690 if (debug.isLogEnabled()) {
691 debug.log("left interval: %s", interval.logString());
692 debug.log("spilled interval : %s", spilledPart.logString());
693 }
694 }
695 }
696 }
697 }
698
699 /**
700 * Change spill state of an interval.
701 *
702 * Note: called during register allocation.
703 *
704 * @param spillPos position of the spill
705 */
706 private void changeSpillState(TraceInterval interval, int spillPos) {
707 if (TraceLinearScanPhase.Options.LIROptTraceRAEliminateSpillMoves.getValue(allocator.getOptions())) {
708 switch (interval.spillState()) {
709 case NoSpillStore:
710 final int minSpillPos = calculateMinSpillPos(interval.spillDefinitionPos(), spillPos);
711 final int maxSpillPos = calculateMaxSpillPos(minSpillPos, spillPos);
712
780 /* Skip block begins. */
781 while (allocator.isBlockBegin(maxSpillPos) && maxSpillPos > minSpillPos) {
782 // -2 is block end, -4 is the instruction before
783 maxSpillPos -= 4;
784 }
785 assert minSpillPos <= maxSpillPos;
786 return maxSpillPos;
787 }
788
789 private boolean isNotBlockBeginOrMerge(int spillPos) {
790 int spillPosEven = spillPos & ~1;
791 return spillPosEven == 0 || !allocator.isBlockBegin(spillPosEven) || SSAUtil.isMerge(allocator.blockForId(spillPosEven));
792 }
793
794 /**
795 * @param minSpillPos minimal spill position
796 * @param maxSpillPos maximal spill position
797 */
798 private int findOptimalSpillPos(int minSpillPos, int maxSpillPos) {
799 int optimalSpillPos = findOptimalSpillPos0(minSpillPos, maxSpillPos) & (~1);
800 if (debug.isLogEnabled()) {
801 debug.log("optimal spill position: %d", optimalSpillPos);
802 }
803 return optimalSpillPos;
804 }
805
806 private int findOptimalSpillPos0(int minSpillPos, int maxSpillPos) {
807 if (minSpillPos == maxSpillPos) {
808 // trivial case, no optimization of split position possible
809 if (debug.isLogEnabled()) {
810 debug.log("min-pos and max-pos are equal, no optimization possible");
811 }
812 return minSpillPos;
813
814 }
815 assert minSpillPos < maxSpillPos : "must be true then";
816 assert minSpillPos >= 0 : "cannot access minSplitPos - 1 otherwise";
817
818 AbstractBlockBase<?> minBlock = allocator.blockForId(minSpillPos);
819 AbstractBlockBase<?> maxBlock = allocator.blockForId(maxSpillPos);
820
821 assert minBlock.getLinearScanNumber() <= maxBlock.getLinearScanNumber() : "invalid order";
822 if (minBlock == maxBlock) {
823 // split position cannot be moved to block boundary : so split as late as possible
824 if (debug.isLogEnabled()) {
825 debug.log("cannot move split pos to block boundary because minPos and maxPos are in same block");
826 }
827 return maxSpillPos;
828
829 }
830 // search optimal block boundary between minSplitPos and maxSplitPos
831 if (debug.isLogEnabled()) {
832 debug.log("moving split pos to optimal block boundary between block B%d and B%d", minBlock.getId(), maxBlock.getId());
833 }
834
835 // currently using the same heuristic as for splitting
836 return findOptimalSpillPos(minBlock, maxBlock, maxSpillPos);
837 }
838
839 private int findOptimalSpillPos(AbstractBlockBase<?> minBlock, AbstractBlockBase<?> maxBlock, int maxSplitPos) {
840 int fromBlockNr = minBlock.getLinearScanNumber();
841 int toBlockNr = maxBlock.getLinearScanNumber();
842
843 assert 0 <= fromBlockNr && fromBlockNr < blockCount() : "out of range";
844 assert 0 <= toBlockNr && toBlockNr < blockCount() : "out of range";
845 assert fromBlockNr < toBlockNr : "must cross block boundary";
846
847 /*
848 * Try to split at end of maxBlock. We use last instruction -2 because we want to insert the
849 * move before the block end op. If this would be after maxSplitPos, then use the
850 * maxSplitPos.
851 */
852 int optimalSplitPos = allocator.getLastLirInstructionId(maxBlock) - 2;
895 }
896
897 private void splitWhenPartialRegisterAvailable(TraceInterval interval, int registerAvailableUntil) {
898 int minSplitPos = Math.max(interval.previousUsage(RegisterPriority.ShouldHaveRegister, registerAvailableUntil), interval.from() + 1);
899 splitBeforeUsage(interval, minSplitPos, registerAvailableUntil);
900 }
901
902 private void splitAndSpillInterval(TraceInterval interval) {
903 int currentPos = currentPosition;
904 /*
905 * Search the position where the interval must have a register and split at the optimal
906 * position before. The new created part is added to the unhandled list and will get a
907 * register when it is activated.
908 */
909 int minSplitPos = currentPos + 1;
910 int maxSplitPos = interval.nextUsage(RegisterPriority.MustHaveRegister, minSplitPos);
911
912 if (maxSplitPos <= interval.to()) {
913 splitBeforeUsage(interval, minSplitPos, maxSplitPos);
914 } else {
915 debug.log("No more usage, no need to split: %s", interval);
916 }
917
918 assert interval.nextUsage(RegisterPriority.MustHaveRegister, currentPos) == Integer.MAX_VALUE : "the remaining part is spilled to stack and therefore has no register";
919 splitForSpilling(interval);
920 }
921
922 @SuppressWarnings("try")
923 private boolean allocFreeRegister(TraceInterval interval) {
924 try (Indent indent = debug.logAndIndent("trying to find free register for %s", interval)) {
925
926 initUseLists(true);
927 freeExcludeActiveFixed();
928 freeCollectInactiveFixed(interval);
929 freeExcludeActiveAny();
930 // freeCollectUnhandled(fixedKind, cur);
931
932 // usePos contains the start of the next interval that has this register assigned
933 // (either as a fixed register or a normal allocated register in the past)
934 // only intervals overlapping with cur are processed, non-overlapping invervals can be
935 // ignored safely
936 if (debug.isLogEnabled()) {
937 // Enable this logging to see all register states
938 try (Indent indent2 = debug.logAndIndent("state of registers:")) {
939 for (Register register : availableRegs) {
940 int i = register.number;
941 debug.log("reg %d (%s): usePos: %d", register.number, register, usePos[i]);
942 }
943 }
944 }
945
946 Register hint = null;
947 IntervalHint locationHint = interval.locationHint(true);
948 if (locationHint != null && locationHint.location() != null && isRegister(locationHint.location())) {
949 hint = asRegister(locationHint.location());
950 if (debug.isLogEnabled()) {
951 debug.log("hint register %3d (%4s) from interval %s", hint.number, hint, locationHint);
952 }
953 }
954 assert interval.location() == null : "register already assigned to interval";
955
956 // the register must be free at least until this position
957 int regNeededUntil = interval.from() + 1;
958 int intervalTo = interval.to();
959
960 boolean needSplit = false;
961 int splitPos = -1;
962
963 Register reg = null;
964 Register minFullReg = null;
965 Register maxPartialReg = null;
966
967 for (Register availableReg : availableRegs) {
968 int number = availableReg.number;
969 if (usePos[number] >= intervalTo) {
970 // this register is free for the full interval
971 if (minFullReg == null || availableReg.equals(hint) || (usePos[number] < usePos[minFullReg.number] && !minFullReg.equals(hint))) {
973 }
974 } else if (usePos[number] > regNeededUntil) {
975 // this register is at least free until regNeededUntil
976 if (maxPartialReg == null || availableReg.equals(hint) || (usePos[number] > usePos[maxPartialReg.number] && !maxPartialReg.equals(hint))) {
977 maxPartialReg = availableReg;
978 }
979 }
980 }
981
982 if (minFullReg != null) {
983 reg = minFullReg;
984 } else if (maxPartialReg != null) {
985 needSplit = true;
986 reg = maxPartialReg;
987 } else {
988 return false;
989 }
990
991 splitPos = usePos[reg.number];
992 interval.assignLocation(reg.asValue(allocator.getKind(interval)));
993 if (debug.isLogEnabled()) {
994 debug.log("selected register %d (%s)", reg.number, reg);
995 }
996
997 assert splitPos > 0 : "invalid splitPos";
998 if (needSplit) {
999 // register not available for full interval, so split it
1000 splitWhenPartialRegisterAvailable(interval, splitPos);
1001 }
1002 // only return true if interval is completely assigned
1003 return true;
1004 }
1005 }
1006
1007 private void splitAndSpillIntersectingIntervals(Register reg) {
1008 assert reg != null : "no register assigned";
1009
1010 for (int i = 0; i < spillIntervals[reg.number].size(); i++) {
1011 TraceInterval interval = spillIntervals[reg.number].get(i);
1012 removeFromList(interval);
1013 splitAndSpillInterval(interval);
1014 }
1015 }
1016
1017 // Split an Interval and spill it to memory so that cur can be placed in a register
1018 @SuppressWarnings("try")
1019 private void allocLockedRegister(TraceInterval interval) {
1020 try (Indent indent = debug.logAndIndent("alloc locked register: need to split and spill to get register for %s", interval)) {
1021
1022 // the register must be free at least until this position
1023 int firstUsage = interval.firstUsage(RegisterPriority.MustHaveRegister);
1024 int firstShouldHaveUsage = interval.firstUsage(RegisterPriority.ShouldHaveRegister);
1025 int regNeededUntil = Math.min(firstUsage, interval.from() + 1);
1026 int intervalTo = interval.to();
1027 assert regNeededUntil >= 0 && regNeededUntil < Integer.MAX_VALUE : "interval has no use";
1028
1029 Register reg;
1030 Register ignore;
1031 /*
1032 * In the common case we don't spill registers that have _any_ use position that is
1033 * closer than the next use of the current interval, but if we can't spill the current
1034 * interval we weaken this strategy and also allow spilling of intervals that have a
1035 * non-mandatory requirements (no MustHaveRegister use position).
1036 */
1037 for (RegisterPriority registerPriority = RegisterPriority.LiveAtLoopEnd; true; registerPriority = RegisterPriority.MustHaveRegister) {
1038 // collect current usage of registers
1039 initUseLists(false);
1040 spillExcludeActiveFixed();
1041 // spillBlockUnhandledFixed(cur);
1042 spillBlockInactiveFixed(interval);
1043 spillCollectActiveAny(registerPriority);
1044 if (debug.isLogEnabled()) {
1045 printRegisterState();
1046 }
1047
1048 reg = null;
1049 ignore = interval.location() != null && isRegister(interval.location()) ? asRegister(interval.location()) : null;
1050
1051 for (Register availableReg : availableRegs) {
1052 int number = availableReg.number;
1053 if (availableReg.equals(ignore)) {
1054 // this register must be ignored
1055 } else if (usePos[number] > regNeededUntil) {
1056 /*
1057 * If the use position is the same, prefer registers (active intervals)
1058 * where the value is already on the stack.
1059 */
1060 if (reg == null || (usePos[number] > usePos[reg.number]) || (usePos[number] == usePos[reg.number] && (!isInMemory.get(reg.number) && isInMemory.get(number)))) {
1061 reg = availableReg;
1062 }
1063 }
1064 }
1065
1066 if (debug.isLogEnabled()) {
1067 debug.log("Register Selected: %s", reg);
1068 }
1069
1070 int regUsePos = (reg == null ? 0 : usePos[reg.number]);
1071 if (regUsePos <= firstShouldHaveUsage) {
1072 /* Check if there is another interval that is already in memory. */
1073 if (reg == null || interval.inMemoryAt(currentPosition) || !isInMemory.get(reg.number)) {
1074 if (debug.isLogEnabled()) {
1075 debug.log("able to spill current interval. firstUsage(register): %d, usePos: %d", firstUsage, regUsePos);
1076 }
1077
1078 if (firstUsage <= interval.from() + 1) {
1079 if (registerPriority.equals(RegisterPriority.LiveAtLoopEnd)) {
1080 /*
1081 * Tool of last resort: we can not spill the current interval so we
1082 * try to spill an active interval that has a usage but do not
1083 * require a register.
1084 */
1085 debug.log("retry with register priority must have register");
1086 continue;
1087 }
1088 String description = "cannot spill interval (" + interval + ") that is used in first instruction (possible reason: no register found) firstUsage=" + firstUsage +
1089 ", interval.from()=" + interval.from() + "; already used candidates: " + Arrays.toString(availableRegs);
1090 /*
1091 * assign a reasonable register and do a bailout in product mode to
1092 * avoid errors
1093 */
1094 allocator.assignSpillSlot(interval);
1095 if (debug.isDumpEnabled(DebugContext.INFO_LEVEL)) {
1096 dumpLIRAndIntervals(description);
1097 }
1098 throw new OutOfRegistersException("LinearScan: no register found", description);
1099 }
1100
1101 splitAndSpillInterval(interval);
1102 return;
1103 }
1104 }
1105 // common case: break out of the loop
1106 break;
1107 }
1108
1109 boolean needSplit = blockPos[reg.number] <= intervalTo;
1110
1111 int splitPos = blockPos[reg.number];
1112
1113 if (debug.isLogEnabled()) {
1114 debug.log("decided to use register %d", reg.number);
1115 }
1116 assert splitPos > 0 : "invalid splitPos";
1117 assert needSplit || splitPos > interval.from() : "splitting interval at from";
1118
1119 interval.assignLocation(reg.asValue(allocator.getKind(interval)));
1120 if (needSplit) {
1121 // register not available for full interval : so split it
1122 splitWhenPartialRegisterAvailable(interval, splitPos);
1123 }
1124
1125 // perform splitting and spilling for all affected intervals
1126 splitAndSpillIntersectingIntervals(reg);
1127 return;
1128 }
1129 }
1130
1131 private void dumpLIRAndIntervals(String description) {
1132 debug.dump(DebugContext.INFO_LEVEL, allocator.getLIR(), description);
1133 allocator.printIntervals(description);
1134 }
1135
1136 @SuppressWarnings("try")
1137 private void printRegisterState() {
1138 try (Indent indent2 = debug.logAndIndent("state of registers:")) {
1139 for (Register reg : availableRegs) {
1140 int i = reg.number;
1141 try (Indent indent3 = debug.logAndIndent("reg %d: usePos: %d, blockPos: %d, inMemory: %b, intervals: ", i, usePos[i], blockPos[i], isInMemory.get(i))) {
1142 for (int j = 0; j < spillIntervals[i].size(); j++) {
1143 debug.log("%s", spillIntervals[i].get(j));
1144 }
1145 }
1146 }
1147 }
1148 }
1149
1150 private boolean noAllocationPossible(TraceInterval interval) {
1151 if (allocator.callKillsRegisters()) {
1152 // fast calculation of intervals that can never get a register because the
1153 // the next instruction is a call that blocks all registers
1154 // Note: this only works if a call kills all registers
1155
1156 // check if this interval is the result of a split operation
1157 // (an interval got a register until this position)
1158 int pos = interval.from();
1159 if (isOdd(pos)) {
1160 // the current instruction is a call that blocks all registers
1161 if (pos < allocator.maxOpId() && allocator.hasCall(pos + 1) && interval.to() > pos + 1) {
1162 if (debug.isLogEnabled()) {
1163 debug.log("free register cannot be available because all registers blocked by following call");
1164 }
1165
1166 // safety check that there is really no register available
1167 assert !allocFreeRegister(interval) : "found a register for this interval";
1168 return true;
1169 }
1170 }
1171 }
1172 return false;
1173 }
1174
1175 private void initVarsForAlloc(TraceInterval interval) {
1176 AllocatableRegisters allocatableRegisters = allocator.getRegisterAllocationConfig().getAllocatableRegisters(allocator.getKind(interval).getPlatformKind());
1177 availableRegs = allocatableRegisters.allocatableRegisters;
1178 minReg = allocatableRegisters.minRegisterNumber;
1179 maxReg = allocatableRegisters.maxRegisterNumber;
1180 }
1181
1182 private static boolean isMove(LIRInstruction op, TraceInterval from, TraceInterval to) {
1183 if (ValueMoveOp.isValueMoveOp(op)) {
1235 assert interval.firstUsage(RegisterPriority.MustHaveRegister) == beginPos : "must have use position at begin of interval because of move";
1236 assert endHint.firstUsage(RegisterPriority.MustHaveRegister) == endPos : "must have use position at begin of interval because of move";
1237
1238 if (isRegister(beginHint.location())) {
1239 // registerHint is not spilled at beginPos : so it would not be benefitial to
1240 // immediately spill cur
1241 return;
1242 }
1243 assert registerHint.spillSlot() != null : "must be set when part of interval was spilled";
1244
1245 // modify intervals such that cur gets the same stack slot as registerHint
1246 // delete use positions to prevent the intervals to get a register at beginning
1247 interval.setSpillSlot(registerHint.spillSlot());
1248 interval.removeFirstUsePos();
1249 endHint.removeFirstUsePos();
1250 }
1251
1252 // allocate a physical register or memory location to an interval
1253 @SuppressWarnings("try")
1254 private boolean activateCurrent(TraceInterval interval) {
1255 if (debug.isLogEnabled()) {
1256 logCurrentStatus();
1257 }
1258 boolean result = true;
1259
1260 try (Indent indent = debug.logAndIndent("activating interval %s, splitParent: %d", interval, interval.splitParent().operandNumber)) {
1261
1262 if (interval.location() != null && isStackSlotValue(interval.location())) {
1263 // activating an interval that has a stack slot assigned . split it at first use
1264 // position
1265 // used for method parameters
1266 if (debug.isLogEnabled()) {
1267 debug.log("interval has spill slot assigned (method parameter) . split it before first use");
1268 }
1269 splitStackInterval(interval);
1270 result = false;
1271
1272 } else {
1273 if (interval.location() == null) {
1274 // interval has not assigned register . normal allocation
1275 // (this is the normal case for most intervals)
1276 if (debug.isLogEnabled()) {
1277 debug.log("normal allocation of register");
1278 }
1279
1280 // assign same spill slot to non-intersecting intervals
1281 combineSpilledIntervals(interval);
1282
1283 initVarsForAlloc(interval);
1284 if (noAllocationPossible(interval) || !allocFreeRegister(interval)) {
1285 // no empty register available.
1286 // split and spill another interval so that this interval gets a register
1287 allocLockedRegister(interval);
1288 }
1289
1290 // spilled intervals need not be move to active-list
1291 if (!isRegister(interval.location())) {
1292 result = false;
1293 }
1294 }
1295 }
1296
1297 // load spilled values that become active from stack slot to register
1298 if (interval.insertMoveWhenActivated()) {
1299 assert interval.isSplitChild();
1300 assert interval.currentSplitChild() != null;
1301 assert interval.currentSplitChild().operandNumber != interval.operandNumber : "cannot insert move between same interval";
1302 if (debug.isLogEnabled()) {
1303 debug.log("Inserting move from interval %d to %d because insertMoveWhenActivated is set", interval.currentSplitChild().operandNumber, interval.operandNumber);
1304 }
1305
1306 insertMove(interval.from(), interval.currentSplitChild(), interval);
1307 }
1308 interval.makeCurrentSplitChild();
1309
1310 }
1311
1312 return result; // true = interval is moved to active list
1313 }
1314
1315 void finishAllocation() {
1316 // must be called when all intervals are allocated
1317 moveResolver.resolveAndAppendMoves();
1318 }
1319
1320 @SuppressWarnings("try")
1321 private void logCurrentStatus() {
1322 try (Indent i = debug.logAndIndent("active:")) {
1323 logList(debug, activeFixedList);
1324 logList(debug, activeAnyList);
1325 }
1326 try (Indent i = debug.logAndIndent("inactive(fixed):")) {
1327 logList(debug, inactiveFixedList);
1328 }
1329 }
1330
1331 void walk() {
1332 walkTo(Integer.MAX_VALUE);
1333 }
1334
1335 private void removeFromList(TraceInterval interval) {
1336 activeAnyList = TraceLinearScanWalker.removeAny(activeAnyList, interval);
1337 }
1338
1339 /**
1340 * Walks up to {@code from} and updates the state of {@link FixedInterval fixed intervals}.
1341 *
1342 * Fixed intervals can switch back and forth between the states {@link State#Active} and
1343 * {@link State#Inactive} (and eventually to {@link State#Handled} but handled intervals are not
1344 * managed).
1345 */
1346 @SuppressWarnings("try")
1347 private void walkToFixed(State state, int from) {
1348 assert state == State.Active || state == State.Inactive : "wrong state";
1349 FixedInterval prevprev = null;
1350 FixedInterval prev = (state == State.Active) ? activeFixedList : inactiveFixedList;
1351 FixedInterval next = prev;
1352 if (debug.isLogEnabled()) {
1353 try (Indent i = debug.logAndIndent("walkToFixed(%s, %d):", state, from)) {
1354 logList(debug, next);
1355 }
1356 }
1357 while (next.currentFrom() <= from) {
1358 FixedInterval cur = next;
1359 next = cur.next;
1360
1361 boolean rangeHasChanged = false;
1362 while (cur.currentTo() <= from) {
1363 cur.nextRange();
1364 rangeHasChanged = true;
1365 }
1366
1367 // also handle move from inactive list to active list
1368 rangeHasChanged = rangeHasChanged || (state == State.Inactive && cur.currentFrom() <= from);
1369
1370 if (rangeHasChanged) {
1371 // remove cur from list
1372 if (prevprev == null) {
1373 if (state == State.Active) {
1374 activeFixedList = next;
1382 TraceInterval.State newState;
1383 if (cur.currentAtEnd()) {
1384 // move to handled state (not maintained as a list)
1385 newState = State.Handled;
1386 } else {
1387 if (cur.currentFrom() <= from) {
1388 // sort into active list
1389 activeFixedList = TraceLinearScanWalker.addToListSortedByCurrentFromPositions(activeFixedList, cur);
1390 newState = State.Active;
1391 } else {
1392 // sort into inactive list
1393 inactiveFixedList = TraceLinearScanWalker.addToListSortedByCurrentFromPositions(inactiveFixedList, cur);
1394 newState = State.Inactive;
1395 }
1396 if (prev == cur) {
1397 assert state == newState;
1398 prevprev = prev;
1399 prev = cur.next;
1400 }
1401 }
1402 intervalMoved(debug, cur, state, newState);
1403 } else {
1404 prevprev = prev;
1405 prev = cur.next;
1406 }
1407 }
1408 }
1409
1410 /**
1411 * Walks up to {@code from} and updates the state of {@link TraceInterval intervals}.
1412 *
1413 * Trace intervals can switch once from {@link State#Unhandled} to {@link State#Active} and then
1414 * to {@link State#Handled} but handled intervals are not managed.
1415 */
1416 @SuppressWarnings("try")
1417 private void walkToAny(int from) {
1418 TraceInterval prevprev = null;
1419 TraceInterval prev = activeAnyList;
1420 TraceInterval next = prev;
1421 if (debug.isLogEnabled()) {
1422 try (Indent i = debug.logAndIndent("walkToAny(%d):", from)) {
1423 logList(debug, next);
1424 }
1425 }
1426 while (next.from() <= from) {
1427 TraceInterval cur = next;
1428 next = cur.next;
1429
1430 if (cur.to() <= from) {
1431 // remove cur from list
1432 if (prevprev == null) {
1433 activeAnyList = next;
1434 } else {
1435 prevprev.next = next;
1436 }
1437 intervalMoved(debug, cur, State.Active, State.Handled);
1438 } else {
1439 prevprev = prev;
1440 }
1441 prev = next;
1442 }
1443 }
1444
1445 /**
1446 * Get the next interval from {@linkplain #unhandledAnyList} which starts before or at
1447 * {@code toOpId}. The returned interval is removed.
1448 *
1449 * @postcondition all intervals in {@linkplain #unhandledAnyList} start after {@code toOpId}.
1450 *
1451 * @return The next interval or null if there is no {@linkplain #unhandledAnyList unhandled}
1452 * interval at position {@code toOpId}.
1453 */
1454 private TraceInterval nextInterval(int toOpId) {
1455 TraceInterval any = unhandledAnyList;
1456
1457 if (any != TraceInterval.EndMarker) {
1474 * @postcondition {@link #currentPosition} is set to {@code toOpId}, {@link #activeFixedList}
1475 * and {@link #inactiveFixedList} are populated.
1476 */
1477 @SuppressWarnings("try")
1478 private void walkTo(int toOpId) {
1479 assert currentPosition <= toOpId : "can not walk backwards";
1480 for (TraceInterval currentInterval = nextInterval(toOpId); currentInterval != null; currentInterval = nextInterval(toOpId)) {
1481 int opId = currentInterval.from();
1482
1483 // set currentPosition prior to call of walkTo
1484 currentPosition = opId;
1485
1486 // update unhandled stack intervals
1487 // updateUnhandledStackIntervals(opId);
1488
1489 // call walkTo even if currentPosition == id
1490 walkToFixed(State.Active, opId);
1491 walkToFixed(State.Inactive, opId);
1492 walkToAny(opId);
1493
1494 try (Indent indent = debug.logAndIndent("walk to op %d", opId)) {
1495 if (activateCurrent(currentInterval)) {
1496 activeAnyList = TraceLinearScanWalker.addToListSortedByFromPositions(activeAnyList, currentInterval);
1497 intervalMoved(debug, currentInterval, State.Unhandled, State.Active);
1498 }
1499 }
1500 }
1501 // set currentPosition prior to call of walkTo
1502 currentPosition = toOpId;
1503
1504 if (currentPosition <= allocator.maxOpId()) {
1505 // update unhandled stack intervals
1506 // updateUnhandledStackIntervals(toOpId);
1507
1508 // call walkTo if still in range
1509 walkToFixed(State.Active, toOpId);
1510 walkToFixed(State.Inactive, toOpId);
1511 walkToAny(toOpId);
1512 }
1513 }
1514
1515 private static void logList(DebugContext debug, FixedInterval i) {
1516 for (FixedInterval interval = i; interval != FixedInterval.EndMarker; interval = interval.next) {
1517 debug.log("%s", interval.logString());
1518 }
1519 }
1520
1521 private static void logList(DebugContext debug, TraceInterval i) {
1522 for (TraceInterval interval = i; interval != TraceInterval.EndMarker; interval = interval.next) {
1523 debug.log("%s", interval.logString());
1524 }
1525 }
1526
1527 private static void intervalMoved(DebugContext debug, IntervalHint interval, State from, State to) {
1528 // intervalMoved() is called whenever an interval moves from one interval list to another.
1529 // In the implementation of this method it is prohibited to move the interval to any list.
1530 if (debug.isLogEnabled()) {
1531 debug.log("interval moved from %s to %s: %s", from, to, interval.logString());
1532 }
1533 }
1534 }
|