Only block registers temporarily in register allocation workarounds
Change-Id: Ibbe53001176ee01c16b702cc6f0df1924e257e28
diff --git a/src/main/java/com/android/tools/r8/ir/regalloc/LinearScanRegisterAllocator.java b/src/main/java/com/android/tools/r8/ir/regalloc/LinearScanRegisterAllocator.java
index c280514..827f316 100644
--- a/src/main/java/com/android/tools/r8/ir/regalloc/LinearScanRegisterAllocator.java
+++ b/src/main/java/com/android/tools/r8/ir/regalloc/LinearScanRegisterAllocator.java
@@ -1640,7 +1640,7 @@
}
// Set all free positions for possible registers to max integer.
- RegisterPositions freePositions = new RegisterPositions(registerConstraint + 1);
+ RegisterPositions freePositions = new RegisterPositionsImpl(registerConstraint + 1);
if ((options().debug || code.method().getOptimizationInfo().isReachabilitySensitive())
&& !code.method().accessFlags.isStatic()) {
@@ -1958,13 +1958,13 @@
LiveIntervals unhandledInterval,
int registerConstraint,
boolean needsRegisterPair,
- RegisterPositions freePositions,
+ RegisterPositionsWithExtraBlockedRegisters freePositions,
RegisterPositions.Type type) {
if (workaroundNeeded.test(unhandledInterval)) {
int lastCandidate = candidate;
while (workaroundNeededForCandidate.test(unhandledInterval, candidate)) {
// Make the unusable register unavailable for allocation and try again.
- freePositions.setBlocked(candidate);
+ freePositions.setBlockedTemporarily(candidate);
candidate =
getLargestCandidate(
unhandledInterval, registerConstraint, freePositions, needsRegisterPair, type);
@@ -1972,8 +1972,17 @@
// candidate returned again once we have tried them all. In that case we didn't find a
// valid register candidate and we need to broaden the search to other types.
if (lastCandidate == candidate) {
+ assert false
+ : "Unexpected attempt to take blocked register "
+ + candidate
+ + " in "
+ + code.context().toSourceString();
return REGISTER_CANDIDATE_NOT_FOUND;
}
+ // If we did not find a valid register, then give up, and broaden the search to other types.
+ if (candidate == REGISTER_CANDIDATE_NOT_FOUND) {
+ return candidate;
+ }
lastCandidate = candidate;
}
}
@@ -1992,6 +2001,10 @@
if (candidate == REGISTER_CANDIDATE_NOT_FOUND) {
return candidate;
}
+ // Wrap the use positions such that registers blocked by the workarounds are only blocked until
+ // the end of this method.
+ RegisterPositionsWithExtraBlockedRegisters usePositionsWrapper =
+ new RegisterPositionsWithExtraBlockedRegisters(usePositions);
candidate =
handleWorkaround(
this::needsLongResultOverlappingLongOperandsWorkaround,
@@ -2000,7 +2013,7 @@
unhandledInterval,
registerConstraint,
needsRegisterPair,
- usePositions,
+ usePositionsWrapper,
type);
candidate =
handleWorkaround(
@@ -2010,7 +2023,7 @@
unhandledInterval,
registerConstraint,
needsRegisterPair,
- usePositions,
+ usePositionsWrapper,
type);
candidate =
handleWorkaround(
@@ -2020,7 +2033,7 @@
unhandledInterval,
registerConstraint,
needsRegisterPair,
- usePositions,
+ usePositionsWrapper,
type);
return candidate;
}
@@ -2033,8 +2046,8 @@
}
// Initialize all candidate registers to Integer.MAX_VALUE.
- RegisterPositions usePositions = new RegisterPositions(registerConstraint + 1);
- RegisterPositions blockedPositions = new RegisterPositions(registerConstraint + 1);
+ RegisterPositions usePositions = new RegisterPositionsImpl(registerConstraint + 1);
+ RegisterPositions blockedPositions = new RegisterPositionsImpl(registerConstraint + 1);
// Compute next use location for all currently active registers.
for (LiveIntervals intervals : active) {
@@ -2087,12 +2100,18 @@
boolean needsRegisterPair = unhandledInterval.getType().isWide();
// First look for a candidate that can be rematerialized.
- int candidate = getLargestValidCandidate(unhandledInterval, registerConstraint,
- needsRegisterPair, usePositions, Type.CONST_NUMBER);
+ int candidate =
+ getLargestValidCandidate(
+ unhandledInterval,
+ registerConstraint,
+ needsRegisterPair,
+ usePositions,
+ Type.CONST_NUMBER);
if (candidate != Integer.MAX_VALUE) {
// Look for a non-const, non-monitor candidate.
- int otherCandidate = getLargestValidCandidate(
- unhandledInterval, registerConstraint, needsRegisterPair, usePositions, Type.OTHER);
+ int otherCandidate =
+ getLargestValidCandidate(
+ unhandledInterval, registerConstraint, needsRegisterPair, usePositions, Type.OTHER);
if (otherCandidate == Integer.MAX_VALUE || candidate == REGISTER_CANDIDATE_NOT_FOUND) {
candidate = otherCandidate;
} else {
@@ -2104,6 +2123,7 @@
candidate = otherCandidate;
}
}
+
// If looking at constants and non-monitor registers did not find a valid spill candidate
// we allow ourselves to look at monitor spill candidates as well. Registers holding objects
// used as monitors should not be spilled if we can avoid it. Spilling them can lead
diff --git a/src/main/java/com/android/tools/r8/ir/regalloc/RegisterPositions.java b/src/main/java/com/android/tools/r8/ir/regalloc/RegisterPositions.java
index f58a140..caafb2e 100644
--- a/src/main/java/com/android/tools/r8/ir/regalloc/RegisterPositions.java
+++ b/src/main/java/com/android/tools/r8/ir/regalloc/RegisterPositions.java
@@ -3,18 +3,13 @@
// BSD-style license that can be found in the LICENSE file.
package com.android.tools.r8.ir.regalloc;
-import com.android.tools.r8.errors.Unreachable;
-import java.util.Arrays;
-import java.util.BitSet;
-
/**
* Simple mapping from a register to an int value.
- * <p>
- * The backing for the mapping grows as needed up to a given limit. If no mapping exists for
- * a register number the value is assumed to be Integer.MAX_VALUE.
+ *
+ * <p>The backing for the mapping grows as needed up to a given limit. If no mapping exists for a
+ * register number the value is assumed to be Integer.MAX_VALUE.
*/
-
-public class RegisterPositions {
+public abstract class RegisterPositions {
enum Type {
MONITOR,
@@ -23,103 +18,22 @@
ANY
}
- private static final int INITIAL_SIZE = 16;
- private final int limit;
- private int[] backing;
- private final BitSet registerHoldsConstant;
- private final BitSet registerHoldsMonitor;
- private final BitSet registerHoldsNewStringInstanceDisallowingSpilling;
- private final BitSet blockedRegisters;
+ public abstract boolean hasType(int index, Type type);
- public RegisterPositions(int limit) {
- this.limit = limit;
- backing = new int[INITIAL_SIZE];
- for (int i = 0; i < INITIAL_SIZE; i++) {
- backing[i] = Integer.MAX_VALUE;
- }
- registerHoldsConstant = new BitSet(limit);
- registerHoldsMonitor = new BitSet(limit);
- registerHoldsNewStringInstanceDisallowingSpilling = new BitSet(limit);
- blockedRegisters = new BitSet(limit);
- }
+ public abstract void set(int index, int value, LiveIntervals intervals);
- public boolean hasType(int index, Type type) {
- assert !isBlocked(index);
- switch (type) {
- case MONITOR:
- return holdsMonitor(index);
- case CONST_NUMBER:
- return holdsConstant(index);
- case OTHER:
- return !holdsMonitor(index)
- && !holdsConstant(index)
- && !holdsNewStringInstanceDisallowingSpilling(index);
- case ANY:
- return true;
- default:
- throw new Unreachable("Unexpected register position type: " + type);
- }
- }
+ public abstract int get(int index);
- private boolean holdsConstant(int index) {
- return registerHoldsConstant.get(index);
- }
+ public abstract int getLimit();
- private boolean holdsMonitor(int index) { return registerHoldsMonitor.get(index); }
+ public abstract void setBlocked(int index);
- private boolean holdsNewStringInstanceDisallowingSpilling(int index) {
- return registerHoldsNewStringInstanceDisallowingSpilling.get(index);
- }
+ public abstract boolean isBlocked(int index);
- public void set(int index, int value) {
- if (index >= backing.length) {
- grow(index + 1);
- }
- backing[index] = value;
- }
-
- public void set(int index, int value, LiveIntervals intervals) {
- set(index, value);
- registerHoldsConstant.set(index, intervals.isConstantNumberInterval());
- registerHoldsMonitor.set(index, intervals.usedInMonitorOperation());
- registerHoldsNewStringInstanceDisallowingSpilling.set(
- index, intervals.isNewStringInstanceDisallowingSpilling());
- }
-
- public int get(int index) {
- assert !isBlocked(index);
- if (index < backing.length) {
- return backing[index];
- }
- assert index < limit;
- return Integer.MAX_VALUE;
- }
-
- public void setBlocked(int index) {
- blockedRegisters.set(index);
- }
-
- public boolean isBlocked(int index) {
- return blockedRegisters.get(index);
- }
-
- public boolean isBlocked(int index, boolean isWide) {
+ public final boolean isBlocked(int index, boolean isWide) {
if (isBlocked(index)) {
return true;
}
return isWide && isBlocked(index + 1);
}
-
- public void grow(int minSize) {
- int size = backing.length;
- while (size < minSize) {
- size *= 2;
- }
- size = Math.min(size, limit);
- int oldSize = backing.length;
- backing = Arrays.copyOf(backing, size);
- for (int i = oldSize; i < size; i++) {
- backing[i] = Integer.MAX_VALUE;
- }
- }
}
diff --git a/src/main/java/com/android/tools/r8/ir/regalloc/RegisterPositionsImpl.java b/src/main/java/com/android/tools/r8/ir/regalloc/RegisterPositionsImpl.java
new file mode 100644
index 0000000..0f11ebf
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/regalloc/RegisterPositionsImpl.java
@@ -0,0 +1,117 @@
+// Copyright (c) 2021, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+package com.android.tools.r8.ir.regalloc;
+
+import com.android.tools.r8.errors.Unreachable;
+import java.util.Arrays;
+import java.util.BitSet;
+
+public class RegisterPositionsImpl extends RegisterPositions {
+
+ private static final int INITIAL_SIZE = 16;
+ private final int limit;
+ private int[] backing;
+ private final BitSet registerHoldsConstant;
+ private final BitSet registerHoldsMonitor;
+ private final BitSet registerHoldsNewStringInstanceDisallowingSpilling;
+ private final BitSet blockedRegisters;
+
+ public RegisterPositionsImpl(int limit) {
+ this.limit = limit;
+ backing = new int[INITIAL_SIZE];
+ for (int i = 0; i < INITIAL_SIZE; i++) {
+ backing[i] = Integer.MAX_VALUE;
+ }
+ registerHoldsConstant = new BitSet(limit);
+ registerHoldsMonitor = new BitSet(limit);
+ registerHoldsNewStringInstanceDisallowingSpilling = new BitSet(limit);
+ blockedRegisters = new BitSet(limit);
+ }
+
+ @Override
+ public boolean hasType(int index, Type type) {
+ assert !isBlocked(index);
+ switch (type) {
+ case MONITOR:
+ return holdsMonitor(index);
+ case CONST_NUMBER:
+ return holdsConstant(index);
+ case OTHER:
+ return !holdsMonitor(index)
+ && !holdsConstant(index)
+ && !holdsNewStringInstanceDisallowingSpilling(index);
+ case ANY:
+ return true;
+ default:
+ throw new Unreachable("Unexpected register position type: " + type);
+ }
+ }
+
+ private boolean holdsConstant(int index) {
+ return registerHoldsConstant.get(index);
+ }
+
+ private boolean holdsMonitor(int index) {
+ return registerHoldsMonitor.get(index);
+ }
+
+ private boolean holdsNewStringInstanceDisallowingSpilling(int index) {
+ return registerHoldsNewStringInstanceDisallowingSpilling.get(index);
+ }
+
+ private void set(int index, int value) {
+ if (index >= backing.length) {
+ grow(index + 1);
+ }
+ backing[index] = value;
+ }
+
+ @Override
+ public void set(int index, int value, LiveIntervals intervals) {
+ set(index, value);
+ registerHoldsConstant.set(index, intervals.isConstantNumberInterval());
+ registerHoldsMonitor.set(index, intervals.usedInMonitorOperation());
+ registerHoldsNewStringInstanceDisallowingSpilling.set(
+ index, intervals.isNewStringInstanceDisallowingSpilling());
+ }
+
+ @Override
+ public int get(int index) {
+ assert !isBlocked(index);
+ if (index < backing.length) {
+ return backing[index];
+ }
+ assert index < limit;
+ return Integer.MAX_VALUE;
+ }
+
+ @Override
+ public int getLimit() {
+ return limit;
+ }
+
+ @Override
+ public void setBlocked(int index) {
+ blockedRegisters.set(index);
+ }
+
+ @Override
+ public boolean isBlocked(int index) {
+ return blockedRegisters.get(index);
+ }
+
+ private void grow(int minSize) {
+ int size = backing.length;
+ while (size < minSize) {
+ size *= 2;
+ }
+ size = Math.min(size, limit);
+ int oldSize = backing.length;
+ backing = Arrays.copyOf(backing, size);
+ for (int i = oldSize; i < size; i++) {
+ backing[i] = Integer.MAX_VALUE;
+ }
+ }
+}
diff --git a/src/main/java/com/android/tools/r8/ir/regalloc/RegisterPositionsWithExtraBlockedRegisters.java b/src/main/java/com/android/tools/r8/ir/regalloc/RegisterPositionsWithExtraBlockedRegisters.java
new file mode 100644
index 0000000..16c7bb4
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/regalloc/RegisterPositionsWithExtraBlockedRegisters.java
@@ -0,0 +1,58 @@
+// Copyright (c) 2021, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+package com.android.tools.r8.ir.regalloc;
+
+import java.util.BitSet;
+
+public class RegisterPositionsWithExtraBlockedRegisters extends RegisterPositions {
+
+ private final RegisterPositions positions;
+ private final BitSet extraBlockedRegisters;
+
+ public RegisterPositionsWithExtraBlockedRegisters(RegisterPositions positions) {
+ this.positions = positions;
+ this.extraBlockedRegisters = new BitSet(positions.getLimit());
+ }
+
+ @Override
+ public boolean hasType(int index, Type type) {
+ assert !isBlockedTemporarily(index);
+ return positions.hasType(index, type);
+ }
+
+ @Override
+ public void set(int index, int value, LiveIntervals intervals) {
+ positions.set(index, value, intervals);
+ }
+
+ @Override
+ public int get(int index) {
+ assert !isBlockedTemporarily(index);
+ return positions.get(index);
+ }
+
+ @Override
+ public int getLimit() {
+ return positions.getLimit();
+ }
+
+ @Override
+ public void setBlocked(int index) {
+ positions.setBlocked(index);
+ }
+
+ public void setBlockedTemporarily(int index) {
+ extraBlockedRegisters.set(index);
+ }
+
+ @Override
+ public boolean isBlocked(int index) {
+ return positions.isBlocked(index) || isBlockedTemporarily(index);
+ }
+
+ public boolean isBlockedTemporarily(int index) {
+ return extraBlockedRegisters.get(index);
+ }
+}
