src/jdk.internal.vm.compiler/share/classes/org.graalvm.compiler.lir/src/org/graalvm/compiler/lir/alloc/trace/lsra/TraceLinearScanWalker.java
Index
Unified diffs
Context diffs
Sdiffs
Patch
New
Old
Previous File
Next File
hotspot Cdiff src/jdk.internal.vm.compiler/share/classes/org.graalvm.compiler.lir/src/org/graalvm/compiler/lir/alloc/trace/lsra/TraceLinearScanWalker.java
src/jdk.internal.vm.compiler/share/classes/org.graalvm.compiler.lir/src/org/graalvm/compiler/lir/alloc/trace/lsra/TraceLinearScanWalker.java
Print this page
*** 33,43 ****
import java.util.BitSet;
import org.graalvm.compiler.core.common.alloc.RegisterAllocationConfig.AllocatableRegisters;
import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
import org.graalvm.compiler.core.common.util.Util;
! import org.graalvm.compiler.debug.Debug;
import org.graalvm.compiler.debug.GraalError;
import org.graalvm.compiler.debug.Indent;
import org.graalvm.compiler.lir.LIRInstruction;
import org.graalvm.compiler.lir.LIRValueUtil;
import org.graalvm.compiler.lir.StandardOp.BlockEndOp;
--- 33,43 ----
import java.util.BitSet;
import org.graalvm.compiler.core.common.alloc.RegisterAllocationConfig.AllocatableRegisters;
import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
import org.graalvm.compiler.core.common.util.Util;
! import org.graalvm.compiler.debug.DebugContext;
import org.graalvm.compiler.debug.GraalError;
import org.graalvm.compiler.debug.Indent;
import org.graalvm.compiler.lir.LIRInstruction;
import org.graalvm.compiler.lir.LIRValueUtil;
import org.graalvm.compiler.lir.StandardOp.BlockEndOp;
*** 173,182 ****
--- 173,183 ----
private int minReg;
private int maxReg;
private final TraceLinearScan allocator;
+ private final DebugContext debug;
/**
* Sorted list of intervals, not live before the current position.
*/
private TraceInterval unhandledAnyList;
*** 220,229 ****
--- 221,231 ----
return allocator.blockForId(opId);
}
TraceLinearScanWalker(TraceLinearScan allocator, FixedInterval unhandledFixedFirst, TraceInterval unhandledAnyFirst) {
this.allocator = allocator;
+ this.debug = allocator.getDebug();
unhandledAnyList = unhandledAnyFirst;
activeAnyList = TraceInterval.EndMarker;
activeFixedList = FixedInterval.EndMarker;
// we don't need a separate unhandled list for fixed.
*** 464,484 ****
}
@SuppressWarnings({"unused"})
private int findOptimalSplitPos(TraceInterval interval, int minSplitPos, int maxSplitPos, boolean doLoopOptimization) {
int optimalSplitPos = findOptimalSplitPos0(minSplitPos, maxSplitPos);
! if (Debug.isLogEnabled()) {
! Debug.log("optimal split position: %d", optimalSplitPos);
}
return optimalSplitPos;
}
private int findOptimalSplitPos0(int minSplitPos, int maxSplitPos) {
if (minSplitPos == maxSplitPos) {
// trivial case, no optimization of split position possible
! if (Debug.isLogEnabled()) {
! Debug.log("min-pos and max-pos are equal, no optimization possible");
}
return minSplitPos;
}
assert minSplitPos < maxSplitPos : "must be true then";
--- 466,486 ----
}
@SuppressWarnings({"unused"})
private int findOptimalSplitPos(TraceInterval interval, int minSplitPos, int maxSplitPos, boolean doLoopOptimization) {
int optimalSplitPos = findOptimalSplitPos0(minSplitPos, maxSplitPos);
! if (debug.isLogEnabled()) {
! debug.log("optimal split position: %d", optimalSplitPos);
}
return optimalSplitPos;
}
private int findOptimalSplitPos0(int minSplitPos, int maxSplitPos) {
if (minSplitPos == maxSplitPos) {
// trivial case, no optimization of split position possible
! if (debug.isLogEnabled()) {
! debug.log("min-pos and max-pos are equal, no optimization possible");
}
return minSplitPos;
}
assert minSplitPos < maxSplitPos : "must be true then";
*** 497,515 ****
AbstractBlockBase<?> maxBlock = allocator.blockForId(maxSplitPos - 1);
assert minBlock.getLinearScanNumber() <= maxBlock.getLinearScanNumber() : "invalid order";
if (minBlock == maxBlock) {
// split position cannot be moved to block boundary : so split as late as possible
! if (Debug.isLogEnabled()) {
! Debug.log("cannot move split pos to block boundary because minPos and maxPos are in same block");
}
return maxSplitPos;
}
// seach optimal block boundary between minSplitPos and maxSplitPos
! if (Debug.isLogEnabled()) {
! Debug.log("moving split pos to optimal block boundary between block B%d and B%d", minBlock.getId(), maxBlock.getId());
}
return findOptimalSplitPos(minBlock, maxBlock, maxSplitPos);
}
--- 499,517 ----
AbstractBlockBase<?> maxBlock = allocator.blockForId(maxSplitPos - 1);
assert minBlock.getLinearScanNumber() <= maxBlock.getLinearScanNumber() : "invalid order";
if (minBlock == maxBlock) {
// split position cannot be moved to block boundary : so split as late as possible
! if (debug.isLogEnabled()) {
! debug.log("cannot move split pos to block boundary because minPos and maxPos are in same block");
}
return maxSplitPos;
}
// seach optimal block boundary between minSplitPos and maxSplitPos
! if (debug.isLogEnabled()) {
! debug.log("moving split pos to optimal block boundary between block B%d and B%d", minBlock.getId(), maxBlock.getId());
}
return findOptimalSplitPos(minBlock, maxBlock, maxSplitPos);
}
*** 518,528 ****
// 1) the left part has already a location assigned
// 2) the right part is sorted into to the unhandled-list
@SuppressWarnings("try")
private void splitBeforeUsage(TraceInterval interval, int minSplitPos, int maxSplitPos) {
! try (Indent indent = Debug.logAndIndent("splitting interval %s between %d and %d", interval, minSplitPos, maxSplitPos)) {
assert interval.from() < minSplitPos : "cannot split at start of interval";
assert currentPosition < minSplitPos : "cannot split before current position";
assert minSplitPos <= maxSplitPos : "invalid order";
assert maxSplitPos <= interval.to() : "cannot split after end of interval";
--- 520,530 ----
// 1) the left part has already a location assigned
// 2) the right part is sorted into to the unhandled-list
@SuppressWarnings("try")
private void splitBeforeUsage(TraceInterval interval, int minSplitPos, int maxSplitPos) {
! try (Indent indent = debug.logAndIndent("splitting interval %s between %d and %d", interval, minSplitPos, maxSplitPos)) {
assert interval.from() < minSplitPos : "cannot split at start of interval";
assert currentPosition < minSplitPos : "cannot split before current position";
assert minSplitPos <= maxSplitPos : "invalid order";
assert maxSplitPos <= interval.to() : "cannot split after end of interval";
*** 530,541 ****
final int optimalSplitPos = findOptimalSplitPos(interval, minSplitPos, maxSplitPos, true);
if (optimalSplitPos == interval.to() && interval.nextUsage(RegisterPriority.MustHaveRegister, minSplitPos) == Integer.MAX_VALUE) {
// the split position would be just before the end of the interval
// . no split at all necessary
! if (Debug.isLogEnabled()) {
! Debug.log("no split necessary because optimal split position is at end of interval");
}
return;
}
// must calculate this before the actual split is performed and before split position is
// moved to odd opId
--- 532,543 ----
final int optimalSplitPos = findOptimalSplitPos(interval, minSplitPos, maxSplitPos, true);
if (optimalSplitPos == interval.to() && interval.nextUsage(RegisterPriority.MustHaveRegister, minSplitPos) == Integer.MAX_VALUE) {
// the split position would be just before the end of the interval
// . no split at all necessary
! if (debug.isLogEnabled()) {
! debug.log("no split necessary because optimal split position is at end of interval");
}
return;
}
// must calculate this before the actual split is performed and before split position is
// moved to odd opId
*** 553,589 ****
// TODO( je) better define what min split pos max split pos mean.
assert minSplitPos <= optimalSplitPosFinal && optimalSplitPosFinal <= maxSplitPos || minSplitPos == maxSplitPos && optimalSplitPosFinal == minSplitPos - 1 : "out of range";
assert optimalSplitPosFinal <= interval.to() : "cannot split after end of interval";
assert optimalSplitPosFinal > interval.from() : "cannot split at start of interval";
! if (Debug.isLogEnabled()) {
! Debug.log("splitting at position %d", optimalSplitPosFinal);
}
assert optimalSplitPosFinal > currentPosition : "Can not split interval " + interval + " at current position: " + currentPosition;
assert blockBegin || ((optimalSplitPosFinal & 1) == 1) : "split pos must be odd when not on block boundary";
assert !blockBegin || ((optimalSplitPosFinal & 1) == 0) : "split pos must be even on block boundary";
// TODO (je) duplicate code. try to fold
if (optimalSplitPosFinal == interval.to() && interval.nextUsage(RegisterPriority.MustHaveRegister, minSplitPos) == Integer.MAX_VALUE) {
// the split position would be just before the end of the interval
// . no split at all necessary
! if (Debug.isLogEnabled()) {
! Debug.log("no split necessary because optimal split position is at end of interval");
}
return;
}
TraceInterval splitPart = interval.split(optimalSplitPosFinal, allocator);
splitPart.setInsertMoveWhenActivated(moveNecessary);
assert splitPart.from() >= currentPosition : "cannot append new interval before current walk position";
unhandledAnyList = TraceLinearScanWalker.addToListSortedByStartAndUsePositions(unhandledAnyList, splitPart);
! if (Debug.isLogEnabled()) {
! Debug.log("left interval %s: %s", moveNecessary ? " " : "", interval.logString());
! Debug.log("right interval %s: %s", moveNecessary ? "(move)" : "", splitPart.logString());
}
}
}
// split an interval at the optimal position between minSplitPos and
--- 555,591 ----
// TODO( je) better define what min split pos max split pos mean.
assert minSplitPos <= optimalSplitPosFinal && optimalSplitPosFinal <= maxSplitPos || minSplitPos == maxSplitPos && optimalSplitPosFinal == minSplitPos - 1 : "out of range";
assert optimalSplitPosFinal <= interval.to() : "cannot split after end of interval";
assert optimalSplitPosFinal > interval.from() : "cannot split at start of interval";
! if (debug.isLogEnabled()) {
! debug.log("splitting at position %d", optimalSplitPosFinal);
}
assert optimalSplitPosFinal > currentPosition : "Can not split interval " + interval + " at current position: " + currentPosition;
assert blockBegin || ((optimalSplitPosFinal & 1) == 1) : "split pos must be odd when not on block boundary";
assert !blockBegin || ((optimalSplitPosFinal & 1) == 0) : "split pos must be even on block boundary";
// TODO (je) duplicate code. try to fold
if (optimalSplitPosFinal == interval.to() && interval.nextUsage(RegisterPriority.MustHaveRegister, minSplitPos) == Integer.MAX_VALUE) {
// the split position would be just before the end of the interval
// . no split at all necessary
! if (debug.isLogEnabled()) {
! debug.log("no split necessary because optimal split position is at end of interval");
}
return;
}
TraceInterval splitPart = interval.split(optimalSplitPosFinal, allocator);
splitPart.setInsertMoveWhenActivated(moveNecessary);
assert splitPart.from() >= currentPosition : "cannot append new interval before current walk position";
unhandledAnyList = TraceLinearScanWalker.addToListSortedByStartAndUsePositions(unhandledAnyList, splitPart);
! if (debug.isLogEnabled()) {
! debug.log("left interval %s: %s", moveNecessary ? " " : "", interval.logString());
! debug.log("right interval %s: %s", moveNecessary ? "(move)" : "", splitPart.logString());
}
}
}
// split an interval at the optimal position between minSplitPos and
*** 603,623 ****
*/
previousUsage = interval.previousUsage(RegisterPriority.MustHaveRegister, maxSplitPos);
}
int minSplitPos = Math.max(previousUsage + 1, interval.from());
! try (Indent indent = Debug.logAndIndent("splitting and spilling interval %s between %d and %d", interval, minSplitPos, maxSplitPos)) {
assert interval.from() <= minSplitPos : "cannot split before start of interval";
assert minSplitPos <= maxSplitPos : "invalid order";
assert maxSplitPos < interval.to() : "cannot split at end end of interval";
assert currentPosition < interval.to() : "interval must not end before current position";
if (minSplitPos == interval.from()) {
// the whole interval is never used, so spill it entirely to memory
! try (Indent indent2 = Debug.logAndIndent("spilling entire interval because split pos is at beginning of interval (use positions: %d)", interval.numUsePos())) {
assert interval.firstUsage(RegisterPriority.MustHaveRegister) > currentPosition : String.format("interval %s must not have use position before currentPosition %d", interval,
currentPosition);
allocator.assignSpillSlot(interval);
--- 605,625 ----
*/
previousUsage = interval.previousUsage(RegisterPriority.MustHaveRegister, maxSplitPos);
}
int minSplitPos = Math.max(previousUsage + 1, interval.from());
! try (Indent indent = debug.logAndIndent("splitting and spilling interval %s between %d and %d", interval, minSplitPos, maxSplitPos)) {
assert interval.from() <= minSplitPos : "cannot split before start of interval";
assert minSplitPos <= maxSplitPos : "invalid order";
assert maxSplitPos < interval.to() : "cannot split at end end of interval";
assert currentPosition < interval.to() : "interval must not end before current position";
if (minSplitPos == interval.from()) {
// the whole interval is never used, so spill it entirely to memory
! try (Indent indent2 = debug.logAndIndent("spilling entire interval because split pos is at beginning of interval (use positions: %d)", interval.numUsePos())) {
assert interval.firstUsage(RegisterPriority.MustHaveRegister) > currentPosition : String.format("interval %s must not have use position before currentPosition %d", interval,
currentPosition);
allocator.assignSpillSlot(interval);
*** 632,643 ****
parent = parent.getSplitChildBeforeOpId(parent.from());
if (isRegister(parent.location())) {
if (parent.firstUsage(RegisterPriority.ShouldHaveRegister) == Integer.MAX_VALUE) {
// parent is never used, so kick it out of its assigned register
! if (Debug.isLogEnabled()) {
! Debug.log("kicking out interval %d out of its register because it is never used", parent.operandNumber);
}
allocator.assignSpillSlot(parent);
handleSpillSlot(parent);
} else {
// do not go further back because the register is actually used by
--- 634,645 ----
parent = parent.getSplitChildBeforeOpId(parent.from());
if (isRegister(parent.location())) {
if (parent.firstUsage(RegisterPriority.ShouldHaveRegister) == Integer.MAX_VALUE) {
// parent is never used, so kick it out of its assigned register
! if (debug.isLogEnabled()) {
! debug.log("kicking out interval %d out of its register because it is never used", parent.operandNumber);
}
allocator.assignSpillSlot(parent);
handleSpillSlot(parent);
} else {
// do not go further back because the register is actually used by
*** 659,695 ****
if (!allocator.isBlockBegin(optimalSplitPos)) {
// move position before actual instruction (odd opId)
optimalSplitPos = (optimalSplitPos - 1) | 1;
}
! try (Indent indent2 = Debug.logAndIndent("splitting at position %d", optimalSplitPos)) {
assert allocator.isBlockBegin(optimalSplitPos) || ((optimalSplitPos & 1) == 1) : "split pos must be odd when not on block boundary";
assert !allocator.isBlockBegin(optimalSplitPos) || ((optimalSplitPos & 1) == 0) : "split pos must be even on block boundary";
TraceInterval spilledPart = interval.split(optimalSplitPos, allocator);
allocator.assignSpillSlot(spilledPart);
handleSpillSlot(spilledPart);
changeSpillState(spilledPart, optimalSplitPos);
if (!allocator.isBlockBegin(optimalSplitPos)) {
! if (Debug.isLogEnabled()) {
! Debug.log("inserting move from interval %s to %s", interval, spilledPart);
}
insertMove(optimalSplitPos, interval, spilledPart);
} else {
! if (Debug.isLogEnabled()) {
! Debug.log("no need to insert move. done by data-flow resolution");
}
}
// the currentSplitChild is needed later when moves are inserted for reloading
assert spilledPart.currentSplitChild() == interval : "overwriting wrong currentSplitChild";
spilledPart.makeCurrentSplitChild();
! if (Debug.isLogEnabled()) {
! Debug.log("left interval: %s", interval.logString());
! Debug.log("spilled interval : %s", spilledPart.logString());
}
}
}
}
}
--- 661,697 ----
if (!allocator.isBlockBegin(optimalSplitPos)) {
// move position before actual instruction (odd opId)
optimalSplitPos = (optimalSplitPos - 1) | 1;
}
! try (Indent indent2 = debug.logAndIndent("splitting at position %d", optimalSplitPos)) {
assert allocator.isBlockBegin(optimalSplitPos) || ((optimalSplitPos & 1) == 1) : "split pos must be odd when not on block boundary";
assert !allocator.isBlockBegin(optimalSplitPos) || ((optimalSplitPos & 1) == 0) : "split pos must be even on block boundary";
TraceInterval spilledPart = interval.split(optimalSplitPos, allocator);
allocator.assignSpillSlot(spilledPart);
handleSpillSlot(spilledPart);
changeSpillState(spilledPart, optimalSplitPos);
if (!allocator.isBlockBegin(optimalSplitPos)) {
! if (debug.isLogEnabled()) {
! debug.log("inserting move from interval %s to %s", interval, spilledPart);
}
insertMove(optimalSplitPos, interval, spilledPart);
} else {
! if (debug.isLogEnabled()) {
! debug.log("no need to insert move. done by data-flow resolution");
}
}
// the currentSplitChild is needed later when moves are inserted for reloading
assert spilledPart.currentSplitChild() == interval : "overwriting wrong currentSplitChild";
spilledPart.makeCurrentSplitChild();
! if (debug.isLogEnabled()) {
! debug.log("left interval: %s", interval.logString());
! debug.log("spilled interval : %s", spilledPart.logString());
}
}
}
}
}
*** 793,813 ****
* @param minSpillPos minimal spill position
* @param maxSpillPos maximal spill position
*/
private int findOptimalSpillPos(int minSpillPos, int maxSpillPos) {
int optimalSpillPos = findOptimalSpillPos0(minSpillPos, maxSpillPos) & (~1);
! if (Debug.isLogEnabled()) {
! Debug.log("optimal spill position: %d", optimalSpillPos);
}
return optimalSpillPos;
}
private int findOptimalSpillPos0(int minSpillPos, int maxSpillPos) {
if (minSpillPos == maxSpillPos) {
// trivial case, no optimization of split position possible
! if (Debug.isLogEnabled()) {
! Debug.log("min-pos and max-pos are equal, no optimization possible");
}
return minSpillPos;
}
assert minSpillPos < maxSpillPos : "must be true then";
--- 795,815 ----
* @param minSpillPos minimal spill position
* @param maxSpillPos maximal spill position
*/
private int findOptimalSpillPos(int minSpillPos, int maxSpillPos) {
int optimalSpillPos = findOptimalSpillPos0(minSpillPos, maxSpillPos) & (~1);
! if (debug.isLogEnabled()) {
! debug.log("optimal spill position: %d", optimalSpillPos);
}
return optimalSpillPos;
}
private int findOptimalSpillPos0(int minSpillPos, int maxSpillPos) {
if (minSpillPos == maxSpillPos) {
// trivial case, no optimization of split position possible
! if (debug.isLogEnabled()) {
! debug.log("min-pos and max-pos are equal, no optimization possible");
}
return minSpillPos;
}
assert minSpillPos < maxSpillPos : "must be true then";
*** 817,835 ****
AbstractBlockBase<?> maxBlock = allocator.blockForId(maxSpillPos);
assert minBlock.getLinearScanNumber() <= maxBlock.getLinearScanNumber() : "invalid order";
if (minBlock == maxBlock) {
// split position cannot be moved to block boundary : so split as late as possible
! if (Debug.isLogEnabled()) {
! Debug.log("cannot move split pos to block boundary because minPos and maxPos are in same block");
}
return maxSpillPos;
}
// search optimal block boundary between minSplitPos and maxSplitPos
! if (Debug.isLogEnabled()) {
! Debug.log("moving split pos to optimal block boundary between block B%d and B%d", minBlock.getId(), maxBlock.getId());
}
// currently using the same heuristic as for splitting
return findOptimalSpillPos(minBlock, maxBlock, maxSpillPos);
}
--- 819,837 ----
AbstractBlockBase<?> maxBlock = allocator.blockForId(maxSpillPos);
assert minBlock.getLinearScanNumber() <= maxBlock.getLinearScanNumber() : "invalid order";
if (minBlock == maxBlock) {
// split position cannot be moved to block boundary : so split as late as possible
! if (debug.isLogEnabled()) {
! debug.log("cannot move split pos to block boundary because minPos and maxPos are in same block");
}
return maxSpillPos;
}
// search optimal block boundary between minSplitPos and maxSplitPos
! if (debug.isLogEnabled()) {
! debug.log("moving split pos to optimal block boundary between block B%d and B%d", minBlock.getId(), maxBlock.getId());
}
// currently using the same heuristic as for splitting
return findOptimalSpillPos(minBlock, maxBlock, maxSpillPos);
}
*** 908,927 ****
int maxSplitPos = interval.nextUsage(RegisterPriority.MustHaveRegister, minSplitPos);
if (maxSplitPos <= interval.to()) {
splitBeforeUsage(interval, minSplitPos, maxSplitPos);
} else {
! Debug.log("No more usage, no need to split: %s", interval);
}
assert interval.nextUsage(RegisterPriority.MustHaveRegister, currentPos) == Integer.MAX_VALUE : "the remaining part is spilled to stack and therefore has no register";
splitForSpilling(interval);
}
@SuppressWarnings("try")
private boolean allocFreeRegister(TraceInterval interval) {
! try (Indent indent = Debug.logAndIndent("trying to find free register for %s", interval)) {
initUseLists(true);
freeExcludeActiveFixed();
freeCollectInactiveFixed(interval);
freeExcludeActiveAny();
--- 910,929 ----
int maxSplitPos = interval.nextUsage(RegisterPriority.MustHaveRegister, minSplitPos);
if (maxSplitPos <= interval.to()) {
splitBeforeUsage(interval, minSplitPos, maxSplitPos);
} else {
! debug.log("No more usage, no need to split: %s", interval);
}
assert interval.nextUsage(RegisterPriority.MustHaveRegister, currentPos) == Integer.MAX_VALUE : "the remaining part is spilled to stack and therefore has no register";
splitForSpilling(interval);
}
@SuppressWarnings("try")
private boolean allocFreeRegister(TraceInterval interval) {
! try (Indent indent = debug.logAndIndent("trying to find free register for %s", interval)) {
initUseLists(true);
freeExcludeActiveFixed();
freeCollectInactiveFixed(interval);
freeExcludeActiveAny();
*** 929,954 ****
// usePos contains the start of the next interval that has this register assigned
// (either as a fixed register or a normal allocated register in the past)
// only intervals overlapping with cur are processed, non-overlapping invervals can be
// ignored safely
! if (Debug.isLogEnabled()) {
// Enable this logging to see all register states
! try (Indent indent2 = Debug.logAndIndent("state of registers:")) {
for (Register register : availableRegs) {
int i = register.number;
! Debug.log("reg %d (%s): usePos: %d", register.number, register, usePos[i]);
}
}
}
Register hint = null;
IntervalHint locationHint = interval.locationHint(true);
if (locationHint != null && locationHint.location() != null && isRegister(locationHint.location())) {
hint = asRegister(locationHint.location());
! if (Debug.isLogEnabled()) {
! Debug.log("hint register %3d (%4s) from interval %s", hint.number, hint, locationHint);
}
}
assert interval.location() == null : "register already assigned to interval";
// the register must be free at least until this position
--- 931,956 ----
// usePos contains the start of the next interval that has this register assigned
// (either as a fixed register or a normal allocated register in the past)
// only intervals overlapping with cur are processed, non-overlapping invervals can be
// ignored safely
! if (debug.isLogEnabled()) {
// Enable this logging to see all register states
! try (Indent indent2 = debug.logAndIndent("state of registers:")) {
for (Register register : availableRegs) {
int i = register.number;
! debug.log("reg %d (%s): usePos: %d", register.number, register, usePos[i]);
}
}
}
Register hint = null;
IntervalHint locationHint = interval.locationHint(true);
if (locationHint != null && locationHint.location() != null && isRegister(locationHint.location())) {
hint = asRegister(locationHint.location());
! if (debug.isLogEnabled()) {
! debug.log("hint register %3d (%4s) from interval %s", hint.number, hint, locationHint);
}
}
assert interval.location() == null : "register already assigned to interval";
// the register must be free at least until this position
*** 986,997 ****
return false;
}
splitPos = usePos[reg.number];
interval.assignLocation(reg.asValue(allocator.getKind(interval)));
! if (Debug.isLogEnabled()) {
! Debug.log("selected register %d (%s)", reg.number, reg);
}
assert splitPos > 0 : "invalid splitPos";
if (needSplit) {
// register not available for full interval, so split it
--- 988,999 ----
return false;
}
splitPos = usePos[reg.number];
interval.assignLocation(reg.asValue(allocator.getKind(interval)));
! if (debug.isLogEnabled()) {
! debug.log("selected register %d (%s)", reg.number, reg);
}
assert splitPos > 0 : "invalid splitPos";
if (needSplit) {
// register not available for full interval, so split it
*** 1013,1023 ****
}
// Split an Interval and spill it to memory so that cur can be placed in a register
@SuppressWarnings("try")
private void allocLockedRegister(TraceInterval interval) {
! try (Indent indent = Debug.logAndIndent("alloc locked register: need to split and spill to get register for %s", interval)) {
// the register must be free at least until this position
int firstUsage = interval.firstUsage(RegisterPriority.MustHaveRegister);
int firstShouldHaveUsage = interval.firstUsage(RegisterPriority.ShouldHaveRegister);
int regNeededUntil = Math.min(firstUsage, interval.from() + 1);
--- 1015,1025 ----
}
// Split an Interval and spill it to memory so that cur can be placed in a register
@SuppressWarnings("try")
private void allocLockedRegister(TraceInterval interval) {
! try (Indent indent = debug.logAndIndent("alloc locked register: need to split and spill to get register for %s", interval)) {
// the register must be free at least until this position
int firstUsage = interval.firstUsage(RegisterPriority.MustHaveRegister);
int firstShouldHaveUsage = interval.firstUsage(RegisterPriority.ShouldHaveRegister);
int regNeededUntil = Math.min(firstUsage, interval.from() + 1);
*** 1037,1047 ****
initUseLists(false);
spillExcludeActiveFixed();
// spillBlockUnhandledFixed(cur);
spillBlockInactiveFixed(interval);
spillCollectActiveAny(registerPriority);
! if (Debug.isLogEnabled()) {
printRegisterState();
}
reg = null;
ignore = interval.location() != null && isRegister(interval.location()) ? asRegister(interval.location()) : null;
--- 1039,1049 ----
initUseLists(false);
spillExcludeActiveFixed();
// spillBlockUnhandledFixed(cur);
spillBlockInactiveFixed(interval);
spillCollectActiveAny(registerPriority);
! if (debug.isLogEnabled()) {
printRegisterState();
}
reg = null;
ignore = interval.location() != null && isRegister(interval.location()) ? asRegister(interval.location()) : null;
*** 1059,1098 ****
reg = availableReg;
}
}
}
! if (Debug.isLogEnabled()) {
! Debug.log("Register Selected: %s", reg);
}
int regUsePos = (reg == null ? 0 : usePos[reg.number]);
if (regUsePos <= firstShouldHaveUsage) {
/* Check if there is another interval that is already in memory. */
if (reg == null || interval.inMemoryAt(currentPosition) || !isInMemory.get(reg.number)) {
! if (Debug.isLogEnabled()) {
! Debug.log("able to spill current interval. firstUsage(register): %d, usePos: %d", firstUsage, regUsePos);
}
if (firstUsage <= interval.from() + 1) {
if (registerPriority.equals(RegisterPriority.LiveAtLoopEnd)) {
/*
* Tool of last resort: we can not spill the current interval so we
* try to spill an active interval that has a usage but do not
* require a register.
*/
! Debug.log("retry with register priority must have register");
continue;
}
String description = "cannot spill interval (" + interval + ") that is used in first instruction (possible reason: no register found) firstUsage=" + firstUsage +
", interval.from()=" + interval.from() + "; already used candidates: " + Arrays.toString(availableRegs);
/*
* assign a reasonable register and do a bailout in product mode to
* avoid errors
*/
allocator.assignSpillSlot(interval);
! if (Debug.isDumpEnabled(Debug.INFO_LEVEL)) {
dumpLIRAndIntervals(description);
}
throw new OutOfRegistersException("LinearScan: no register found", description);
}
--- 1061,1100 ----
reg = availableReg;
}
}
}
! if (debug.isLogEnabled()) {
! debug.log("Register Selected: %s", reg);
}
int regUsePos = (reg == null ? 0 : usePos[reg.number]);
if (regUsePos <= firstShouldHaveUsage) {
/* Check if there is another interval that is already in memory. */
if (reg == null || interval.inMemoryAt(currentPosition) || !isInMemory.get(reg.number)) {
! if (debug.isLogEnabled()) {
! debug.log("able to spill current interval. firstUsage(register): %d, usePos: %d", firstUsage, regUsePos);
}
if (firstUsage <= interval.from() + 1) {
if (registerPriority.equals(RegisterPriority.LiveAtLoopEnd)) {
/*
* Tool of last resort: we can not spill the current interval so we
* try to spill an active interval that has a usage but do not
* require a register.
*/
! debug.log("retry with register priority must have register");
continue;
}
String description = "cannot spill interval (" + interval + ") that is used in first instruction (possible reason: no register found) firstUsage=" + firstUsage +
", interval.from()=" + interval.from() + "; already used candidates: " + Arrays.toString(availableRegs);
/*
* assign a reasonable register and do a bailout in product mode to
* avoid errors
*/
allocator.assignSpillSlot(interval);
! if (debug.isDumpEnabled(DebugContext.INFO_LEVEL)) {
dumpLIRAndIntervals(description);
}
throw new OutOfRegistersException("LinearScan: no register found", description);
}
*** 1106,1117 ****
boolean needSplit = blockPos[reg.number] <= intervalTo;
int splitPos = blockPos[reg.number];
! if (Debug.isLogEnabled()) {
! Debug.log("decided to use register %d", reg.number);
}
assert splitPos > 0 : "invalid splitPos";
assert needSplit || splitPos > interval.from() : "splitting interval at from";
interval.assignLocation(reg.asValue(allocator.getKind(interval)));
--- 1108,1119 ----
boolean needSplit = blockPos[reg.number] <= intervalTo;
int splitPos = blockPos[reg.number];
! if (debug.isLogEnabled()) {
! debug.log("decided to use register %d", reg.number);
}
assert splitPos > 0 : "invalid splitPos";
assert needSplit || splitPos > interval.from() : "splitting interval at from";
interval.assignLocation(reg.asValue(allocator.getKind(interval)));
*** 1125,1146 ****
return;
}
}
private void dumpLIRAndIntervals(String description) {
! Debug.dump(Debug.INFO_LEVEL, allocator.getLIR(), description);
allocator.printIntervals(description);
}
@SuppressWarnings("try")
private void printRegisterState() {
! try (Indent indent2 = Debug.logAndIndent("state of registers:")) {
for (Register reg : availableRegs) {
int i = reg.number;
! try (Indent indent3 = Debug.logAndIndent("reg %d: usePos: %d, blockPos: %d, inMemory: %b, intervals: ", i, usePos[i], blockPos[i], isInMemory.get(i))) {
for (int j = 0; j < spillIntervals[i].size(); j++) {
! Debug.log("%s", spillIntervals[i].get(j));
}
}
}
}
}
--- 1127,1148 ----
return;
}
}
private void dumpLIRAndIntervals(String description) {
! debug.dump(DebugContext.INFO_LEVEL, allocator.getLIR(), description);
allocator.printIntervals(description);
}
@SuppressWarnings("try")
private void printRegisterState() {
! try (Indent indent2 = debug.logAndIndent("state of registers:")) {
for (Register reg : availableRegs) {
int i = reg.number;
! try (Indent indent3 = debug.logAndIndent("reg %d: usePos: %d, blockPos: %d, inMemory: %b, intervals: ", i, usePos[i], blockPos[i], isInMemory.get(i))) {
for (int j = 0; j < spillIntervals[i].size(); j++) {
! debug.log("%s", spillIntervals[i].get(j));
}
}
}
}
}
*** 1155,1166 ****
// (an interval got a register until this position)
int pos = interval.from();
if (isOdd(pos)) {
// the current instruction is a call that blocks all registers
if (pos < allocator.maxOpId() && allocator.hasCall(pos + 1) && interval.to() > pos + 1) {
! if (Debug.isLogEnabled()) {
! Debug.log("free register cannot be available because all registers blocked by following call");
}
// safety check that there is really no register available
assert !allocFreeRegister(interval) : "found a register for this interval";
return true;
--- 1157,1168 ----
// (an interval got a register until this position)
int pos = interval.from();
if (isOdd(pos)) {
// the current instruction is a call that blocks all registers
if (pos < allocator.maxOpId() && allocator.hasCall(pos + 1) && interval.to() > pos + 1) {
! if (debug.isLogEnabled()) {
! debug.log("free register cannot be available because all registers blocked by following call");
}
// safety check that there is really no register available
assert !allocFreeRegister(interval) : "found a register for this interval";
return true;
*** 1248,1280 ****
}
// allocate a physical register or memory location to an interval
@SuppressWarnings("try")
private boolean activateCurrent(TraceInterval interval) {
! if (Debug.isLogEnabled()) {
logCurrentStatus();
}
boolean result = true;
! try (Indent indent = Debug.logAndIndent("activating interval %s, splitParent: %d", interval, interval.splitParent().operandNumber)) {
if (interval.location() != null && isStackSlotValue(interval.location())) {
// activating an interval that has a stack slot assigned . split it at first use
// position
// used for method parameters
! if (Debug.isLogEnabled()) {
! Debug.log("interval has spill slot assigned (method parameter) . split it before first use");
}
splitStackInterval(interval);
result = false;
} else {
if (interval.location() == null) {
// interval has not assigned register . normal allocation
// (this is the normal case for most intervals)
! if (Debug.isLogEnabled()) {
! Debug.log("normal allocation of register");
}
// assign same spill slot to non-intersecting intervals
combineSpilledIntervals(interval);
--- 1250,1282 ----
}
// allocate a physical register or memory location to an interval
@SuppressWarnings("try")
private boolean activateCurrent(TraceInterval interval) {
! if (debug.isLogEnabled()) {
logCurrentStatus();
}
boolean result = true;
! try (Indent indent = debug.logAndIndent("activating interval %s, splitParent: %d", interval, interval.splitParent().operandNumber)) {
if (interval.location() != null && isStackSlotValue(interval.location())) {
// activating an interval that has a stack slot assigned . split it at first use
// position
// used for method parameters
! if (debug.isLogEnabled()) {
! debug.log("interval has spill slot assigned (method parameter) . split it before first use");
}
splitStackInterval(interval);
result = false;
} else {
if (interval.location() == null) {
// interval has not assigned register . normal allocation
// (this is the normal case for most intervals)
! if (debug.isLogEnabled()) {
! debug.log("normal allocation of register");
}
// assign same spill slot to non-intersecting intervals
combineSpilledIntervals(interval);
*** 1295,1306 ****
// load spilled values that become active from stack slot to register
if (interval.insertMoveWhenActivated()) {
assert interval.isSplitChild();
assert interval.currentSplitChild() != null;
assert interval.currentSplitChild().operandNumber != interval.operandNumber : "cannot insert move between same interval";
! if (Debug.isLogEnabled()) {
! Debug.log("Inserting move from interval %d to %d because insertMoveWhenActivated is set", interval.currentSplitChild().operandNumber, interval.operandNumber);
}
insertMove(interval.from(), interval.currentSplitChild(), interval);
}
interval.makeCurrentSplitChild();
--- 1297,1308 ----
// load spilled values that become active from stack slot to register
if (interval.insertMoveWhenActivated()) {
assert interval.isSplitChild();
assert interval.currentSplitChild() != null;
assert interval.currentSplitChild().operandNumber != interval.operandNumber : "cannot insert move between same interval";
! if (debug.isLogEnabled()) {
! debug.log("Inserting move from interval %d to %d because insertMoveWhenActivated is set", interval.currentSplitChild().operandNumber, interval.operandNumber);
}
insertMove(interval.from(), interval.currentSplitChild(), interval);
}
interval.makeCurrentSplitChild();
*** 1315,1330 ****
moveResolver.resolveAndAppendMoves();
}
@SuppressWarnings("try")
private void logCurrentStatus() {
! try (Indent i = Debug.logAndIndent("active:")) {
! logList(activeFixedList);
! logList(activeAnyList);
}
! try (Indent i = Debug.logAndIndent("inactive(fixed):")) {
! logList(inactiveFixedList);
}
}
void walk() {
walkTo(Integer.MAX_VALUE);
--- 1317,1332 ----
moveResolver.resolveAndAppendMoves();
}
@SuppressWarnings("try")
private void logCurrentStatus() {
! try (Indent i = debug.logAndIndent("active:")) {
! logList(debug, activeFixedList);
! logList(debug, activeAnyList);
}
! try (Indent i = debug.logAndIndent("inactive(fixed):")) {
! logList(debug, inactiveFixedList);
}
}
void walk() {
walkTo(Integer.MAX_VALUE);
*** 1345,1357 ****
private void walkToFixed(State state, int from) {
assert state == State.Active || state == State.Inactive : "wrong state";
FixedInterval prevprev = null;
FixedInterval prev = (state == State.Active) ? activeFixedList : inactiveFixedList;
FixedInterval next = prev;
! if (Debug.isLogEnabled()) {
! try (Indent i = Debug.logAndIndent("walkToFixed(%s, %d):", state, from)) {
! logList(next);
}
}
while (next.currentFrom() <= from) {
FixedInterval cur = next;
next = cur.next;
--- 1347,1359 ----
private void walkToFixed(State state, int from) {
assert state == State.Active || state == State.Inactive : "wrong state";
FixedInterval prevprev = null;
FixedInterval prev = (state == State.Active) ? activeFixedList : inactiveFixedList;
FixedInterval next = prev;
! if (debug.isLogEnabled()) {
! try (Indent i = debug.logAndIndent("walkToFixed(%s, %d):", state, from)) {
! logList(debug, next);
}
}
while (next.currentFrom() <= from) {
FixedInterval cur = next;
next = cur.next;
*** 1395,1405 ****
assert state == newState;
prevprev = prev;
prev = cur.next;
}
}
! intervalMoved(cur, state, newState);
} else {
prevprev = prev;
prev = cur.next;
}
}
--- 1397,1407 ----
assert state == newState;
prevprev = prev;
prev = cur.next;
}
}
! intervalMoved(debug, cur, state, newState);
} else {
prevprev = prev;
prev = cur.next;
}
}
*** 1414,1426 ****
@SuppressWarnings("try")
private void walkToAny(int from) {
TraceInterval prevprev = null;
TraceInterval prev = activeAnyList;
TraceInterval next = prev;
! if (Debug.isLogEnabled()) {
! try (Indent i = Debug.logAndIndent("walkToAny(%d):", from)) {
! logList(next);
}
}
while (next.from() <= from) {
TraceInterval cur = next;
next = cur.next;
--- 1416,1428 ----
@SuppressWarnings("try")
private void walkToAny(int from) {
TraceInterval prevprev = null;
TraceInterval prev = activeAnyList;
TraceInterval next = prev;
! if (debug.isLogEnabled()) {
! try (Indent i = debug.logAndIndent("walkToAny(%d):", from)) {
! logList(debug, next);
}
}
while (next.from() <= from) {
TraceInterval cur = next;
next = cur.next;
*** 1430,1440 ****
if (prevprev == null) {
activeAnyList = next;
} else {
prevprev.next = next;
}
! intervalMoved(cur, State.Active, State.Handled);
} else {
prevprev = prev;
}
prev = next;
}
--- 1432,1442 ----
if (prevprev == null) {
activeAnyList = next;
} else {
prevprev.next = next;
}
! intervalMoved(debug, cur, State.Active, State.Handled);
} else {
prevprev = prev;
}
prev = next;
}
*** 1487,1500 ****
// call walkTo even if currentPosition == id
walkToFixed(State.Active, opId);
walkToFixed(State.Inactive, opId);
walkToAny(opId);
! try (Indent indent = Debug.logAndIndent("walk to op %d", opId)) {
if (activateCurrent(currentInterval)) {
activeAnyList = TraceLinearScanWalker.addToListSortedByFromPositions(activeAnyList, currentInterval);
! intervalMoved(currentInterval, State.Unhandled, State.Active);
}
}
}
// set currentPosition prior to call of walkTo
currentPosition = toOpId;
--- 1489,1502 ----
// call walkTo even if currentPosition == id
walkToFixed(State.Active, opId);
walkToFixed(State.Inactive, opId);
walkToAny(opId);
! try (Indent indent = debug.logAndIndent("walk to op %d", opId)) {
if (activateCurrent(currentInterval)) {
activeAnyList = TraceLinearScanWalker.addToListSortedByFromPositions(activeAnyList, currentInterval);
! intervalMoved(debug, currentInterval, State.Unhandled, State.Active);
}
}
}
// set currentPosition prior to call of walkTo
currentPosition = toOpId;
*** 1508,1532 ****
walkToFixed(State.Inactive, toOpId);
walkToAny(toOpId);
}
}
! private static void logList(FixedInterval i) {
for (FixedInterval interval = i; interval != FixedInterval.EndMarker; interval = interval.next) {
! Debug.log("%s", interval.logString());
}
}
! private static void logList(TraceInterval i) {
for (TraceInterval interval = i; interval != TraceInterval.EndMarker; interval = interval.next) {
! Debug.log("%s", interval.logString());
}
}
! private static void intervalMoved(IntervalHint interval, State from, State to) {
// intervalMoved() is called whenever an interval moves from one interval list to another.
// In the implementation of this method it is prohibited to move the interval to any list.
! if (Debug.isLogEnabled()) {
! Debug.log("interval moved from %s to %s: %s", from, to, interval.logString());
}
}
}
--- 1510,1534 ----
walkToFixed(State.Inactive, toOpId);
walkToAny(toOpId);
}
}
! private static void logList(DebugContext debug, FixedInterval i) {
for (FixedInterval interval = i; interval != FixedInterval.EndMarker; interval = interval.next) {
! debug.log("%s", interval.logString());
}
}
! private static void logList(DebugContext debug, TraceInterval i) {
for (TraceInterval interval = i; interval != TraceInterval.EndMarker; interval = interval.next) {
! debug.log("%s", interval.logString());
}
}
! private static void intervalMoved(DebugContext debug, IntervalHint interval, State from, State to) {
// intervalMoved() is called whenever an interval moves from one interval list to another.
// In the implementation of this method it is prohibited to move the interval to any list.
! if (debug.isLogEnabled()) {
! debug.log("interval moved from %s to %s: %s", from, to, interval.logString());
}
}
}
src/jdk.internal.vm.compiler/share/classes/org.graalvm.compiler.lir/src/org/graalvm/compiler/lir/alloc/trace/lsra/TraceLinearScanWalker.java
Index
Unified diffs
Context diffs
Sdiffs
Patch
New
Old
Previous File
Next File