Do not split live intervals for registers used for locking.
When we can avoid splitting live intervals for registers used for
locking we should always do so. Using spilling for registers used
for locking confuses the Art lock verification code and leads
to warnings (and those warnings are treated as errors by
certain builds).
With this change, the register allocator only splits live ranges
holding objects used in locking operations as a last resort. If you
have deeply nested synchronized blocks we might have to spill the
value in any case and we will. But for most code this should never
happen.
R=mikaelpeltier@google.com, sgjesse@google.com
Bug: b/64765186
Change-Id: Ic8d4519cff28f8720830a8a884d98a72c3f108e6
diff --git a/src/main/java/com/android/tools/r8/ir/code/Value.java b/src/main/java/com/android/tools/r8/ir/code/Value.java
index b6c593c..618c879 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Value.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Value.java
@@ -231,6 +231,15 @@
|| ((debugData != null) && !debugData.debugUsers.isEmpty());
}
+ public boolean usedInMonitorOperation() {
+ for (Instruction instruction : uniqueUsers()) {
+ if (instruction.isMonitor()) {
+ return true;
+ }
+ }
+ return false;
+ }
+
public void addUser(Instruction user) {
users.add(user);
uniqueUsers = null;
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 7b7e5e7..460fe92 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
@@ -22,6 +22,7 @@
import com.android.tools.r8.ir.code.Sub;
import com.android.tools.r8.ir.code.Value;
import com.android.tools.r8.ir.code.Xor;
+import com.android.tools.r8.ir.regalloc.RegisterPositions.Type;
import com.android.tools.r8.logging.Log;
import com.android.tools.r8.utils.CfgPrinter;
import com.android.tools.r8.utils.InternalOptions;
@@ -1095,24 +1096,24 @@
if (mode == ArgumentReuseMode.ALLOW_ARGUMENT_REUSE) {
// The sentinel registers cannot be used and we block them.
- freePositions.set(0, 0, false);
+ freePositions.set(0, 0);
if (options.debug && !code.method.accessFlags.isStatic()) {
// If we are generating debug information, we pin the this value register since the
// debugger expects to always be able to find it in the input register.
assert numberOfArgumentRegisters > 0;
assert preArgumentSentinelValue.getNextConsecutive().requiredRegisters() == 1;
- freePositions.set(1, 0, false);
+ freePositions.set(1, 0);
}
int lastSentinelRegister = numberOfArgumentRegisters + NUMBER_OF_SENTINEL_REGISTERS - 1;
if (lastSentinelRegister <= registerConstraint) {
- freePositions.set(lastSentinelRegister, 0, false);
+ freePositions.set(lastSentinelRegister, 0);
}
} else {
// Argument reuse is not allowed and we block all the argument registers so that
// arguments are never free.
for (int i = 0; i < numberOfArgumentRegisters + NUMBER_OF_SENTINEL_REGISTERS; i++) {
if (i <= registerConstraint) {
- freePositions.set(i, 0, false);
+ freePositions.set(i, 0);
}
}
}
@@ -1124,7 +1125,7 @@
if (hasDedicatedMoveExceptionRegister) {
int moveExceptionRegister = numberOfArgumentRegisters + NUMBER_OF_SENTINEL_REGISTERS;
if (moveExceptionRegister <= registerConstraint) {
- freePositions.set(moveExceptionRegister, 0, false);
+ freePositions.set(moveExceptionRegister, 0);
}
}
@@ -1134,7 +1135,7 @@
if (activeRegister <= registerConstraint) {
for (int i = 0; i < intervals.requiredRegisters(); i++) {
if (activeRegister + i <= registerConstraint) {
- freePositions.set(activeRegister + i, 0, intervals.isConstantNumberInterval());
+ freePositions.set(activeRegister + i, 0);
}
}
}
@@ -1154,10 +1155,10 @@
// Don't use the register for an inactive interval that is only free until the next
// instruction. We can get into this situation when unhandledInterval starts at a
// gap position.
- freePositions.set(register, 0, freePositions.holdsConstant(register));
+ freePositions.set(register, 0);
} else {
if (nextOverlap < freePositions.get(register)) {
- freePositions.set(register, nextOverlap, intervals.isConstantNumberInterval());
+ freePositions.set(register, nextOverlap, intervals);
}
}
}
@@ -1173,7 +1174,7 @@
// Get the register (pair) that is free the longest. That is the register with the largest
// free position.
int candidate = getLargestValidCandidate(
- unhandledInterval, registerConstraint, needsRegisterPair, freePositions, false);
+ unhandledInterval, registerConstraint, needsRegisterPair, freePositions, Type.ANY);
assert candidate != REGISTER_CANDIDATE_NOT_FOUND;
int largestFreePosition = freePositions.get(candidate);
if (needsRegisterPair) {
@@ -1343,12 +1344,12 @@
}
private int getLargestCandidate(int registerConstraint, RegisterPositions freePositions,
- boolean needsRegisterPair, boolean restrictToConstant) {
+ boolean needsRegisterPair, RegisterPositions.Type type) {
int candidate = REGISTER_CANDIDATE_NOT_FOUND;
int largest = -1;
for (int i = 0; i <= registerConstraint; i++) {
- if (restrictToConstant && !freePositions.holdsConstant(i)) {
+ if (!freePositions.hasType(i, type)) {
continue;
}
int freePosition = freePositions.get(i);
@@ -1366,23 +1367,20 @@
}
}
}
-
return candidate;
}
private int getLargestValidCandidate(LiveIntervals unhandledInterval, int registerConstraint,
- boolean needsRegisterPair, RegisterPositions freePositions, boolean restrictToConstant) {
- int candidate = getLargestCandidate(registerConstraint, freePositions, needsRegisterPair,
- restrictToConstant);
+ boolean needsRegisterPair, RegisterPositions freePositions, RegisterPositions.Type type) {
+ int candidate = getLargestCandidate(registerConstraint, freePositions, needsRegisterPair, type);
if (candidate == REGISTER_CANDIDATE_NOT_FOUND) {
return candidate;
}
if (needsOverlappingLongRegisterWorkaround(unhandledInterval)) {
while (hasOverlappingLongRegisters(unhandledInterval, candidate)) {
// Make the overlapping register unavailable for allocation and try again.
- freePositions.set(candidate, 0, freePositions.holdsConstant(candidate));
- candidate = getLargestCandidate(registerConstraint, freePositions, needsRegisterPair,
- restrictToConstant);
+ freePositions.set(candidate, 0);
+ candidate = getLargestCandidate(registerConstraint, freePositions, needsRegisterPair, type);
}
}
return candidate;
@@ -1409,8 +1407,8 @@
for (int i = 0; i < intervals.requiredRegisters(); i++) {
if (activeRegister + i <= registerConstraint) {
int unhandledStart = unhandledInterval.getStart();
- usePositions.set(activeRegister + i, intervals.firstUseAfter(unhandledStart),
- intervals.isConstantNumberInterval());
+ usePositions.set(
+ activeRegister + i, intervals.firstUseAfter(unhandledStart), intervals);
}
}
}
@@ -1424,8 +1422,7 @@
if (inactiveRegister + i <= registerConstraint) {
int firstUse = intervals.firstUseAfter(unhandledInterval.getStart());
if (firstUse < usePositions.get(inactiveRegister + i)) {
- usePositions.set(inactiveRegister + i, firstUse,
- intervals.isConstantNumberInterval());
+ usePositions.set(inactiveRegister + i, firstUse, intervals);
}
}
}
@@ -1435,12 +1432,12 @@
// Disallow the reuse of argument registers by always treating them as being used
// at instruction number 0.
for (int i = 0; i < numberOfArgumentRegisters + NUMBER_OF_SENTINEL_REGISTERS; i++) {
- usePositions.set(i, 0, false);
+ usePositions.set(i, 0);
}
// Disallow reuse of the move exception register if we have reserved one.
if (hasDedicatedMoveExceptionRegister) {
- usePositions.set(numberOfArgumentRegisters + NUMBER_OF_SENTINEL_REGISTERS, 0, false);
+ usePositions.set(numberOfArgumentRegisters + NUMBER_OF_SENTINEL_REGISTERS, 0);
}
// Treat active linked argument intervals as pinned. They cannot be given another register
@@ -1456,21 +1453,32 @@
// Get the register (pair) that has the highest use position.
boolean needsRegisterPair = unhandledInterval.requiredRegisters() == 2;
+ // First look for a candidate that can be rematerialized.
int candidate = getLargestValidCandidate(unhandledInterval, registerConstraint,
- needsRegisterPair, usePositions, true);
+ needsRegisterPair, usePositions, Type.CONST_NUMBER);
if (candidate != Integer.MAX_VALUE) {
- int nonConstCandidate = getLargestValidCandidate(unhandledInterval, registerConstraint,
- needsRegisterPair, usePositions, false);
- if (nonConstCandidate == Integer.MAX_VALUE || candidate == REGISTER_CANDIDATE_NOT_FOUND) {
- candidate = nonConstCandidate;
+ // Look for a non-const, non-monitor candidate.
+ int otherCandidate = getLargestValidCandidate(
+ unhandledInterval, registerConstraint, needsRegisterPair, usePositions, Type.OTHER);
+ if (otherCandidate == Integer.MAX_VALUE || candidate == REGISTER_CANDIDATE_NOT_FOUND) {
+ candidate = otherCandidate;
} else {
- int largestConstUsePosition = getLargestPosition(usePositions, candidate, needsRegisterPair);
- if (largestConstUsePosition - MIN_CONSTANT_FREE_FOR_POSITIONS < unhandledInterval
- .getStart()) {
+ int largestConstUsePosition =
+ getLargestPosition(usePositions, candidate, needsRegisterPair);
+ if (largestConstUsePosition - MIN_CONSTANT_FREE_FOR_POSITIONS <
+ unhandledInterval.getStart()) {
// The candidate that can be rematerialized has a live range too short to use it.
- candidate = nonConstCandidate;
+ 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
+ // to Art lock verification issues.
+ if (candidate == REGISTER_CANDIDATE_NOT_FOUND) {
+ candidate = getLargestValidCandidate(
+ unhandledInterval, registerConstraint, needsRegisterPair, usePositions, Type.MONITOR);
+ }
}
int largestUsePosition = getLargestPosition(usePositions, candidate, needsRegisterPair);
@@ -1711,7 +1719,7 @@
if (register + i <= registerConstraint) {
int firstUse = other.firstUseAfter(interval.getStart());
if (firstUse < blockedPositions.get(register + i)) {
- blockedPositions.set(register + i, firstUse, other.isConstantNumberInterval());
+ blockedPositions.set(register + i, firstUse, other);
// If we start blocking registers other than linked arguments, we might need to
// explicitly update the use positions as well as blocked positions.
assert usePositions.get(register + i) <= blockedPositions.get(register + i);
diff --git a/src/main/java/com/android/tools/r8/ir/regalloc/LiveIntervals.java b/src/main/java/com/android/tools/r8/ir/regalloc/LiveIntervals.java
index 9a810d9..65628c3 100644
--- a/src/main/java/com/android/tools/r8/ir/regalloc/LiveIntervals.java
+++ b/src/main/java/com/android/tools/r8/ir/regalloc/LiveIntervals.java
@@ -28,6 +28,7 @@
private int register = NO_REGISTER;
private LiveIntervals hint;
private boolean spilled = false;
+ private boolean usedInMonitorOperations = false;
// Only registers up to and including the registerLimit are allowed for this interval.
private int registerLimit = U16BIT_MAX;
@@ -39,6 +40,7 @@
LiveIntervals(Value value) {
this.value = value;
+ usedInMonitorOperations = value.usedInMonitorOperation();
splitParent = this;
value.setLiveIntervals(this);
}
@@ -46,6 +48,7 @@
LiveIntervals(LiveIntervals splitParent) {
this.splitParent = splitParent;
value = splitParent.value;
+ usedInMonitorOperations = splitParent.usedInMonitorOperations;
}
private int toInstructionPosition(int position) {
@@ -436,6 +439,10 @@
return value.definition != null && value.isConstNumber();
}
+ public boolean usedInMonitorOperation() {
+ return usedInMonitorOperations;
+ }
+
public int numberOfUsesWithConstraint() {
int count = 0;
for (LiveIntervalsUse use : getUses()) {
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 35b87fc..d061db7 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,6 +3,7 @@
// 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;
@@ -14,10 +15,14 @@
*/
public class RegisterPositions {
+
+ enum Type { MONITOR, CONST_NUMBER, OTHER, ANY }
+
private static final int INITIAL_SIZE = 16;
private int limit;
private int[] backing;
private BitSet registerHoldsConstant;
+ private BitSet registerHoldsMonitor;
public RegisterPositions(int limit) {
this.limit = limit;
@@ -26,18 +31,41 @@
backing[i] = Integer.MAX_VALUE;
}
registerHoldsConstant = new BitSet(limit);
+ registerHoldsMonitor = new BitSet(limit);
}
- public boolean holdsConstant(int index) {
+ public boolean hasType(int index, Type type) {
+ switch (type) {
+ case MONITOR:
+ return holdsMonitor(index);
+ case CONST_NUMBER:
+ return holdsConstant(index);
+ case OTHER:
+ return !holdsMonitor(index) && !holdsConstant(index);
+ case ANY:
+ return true;
+ default:
+ throw new Unreachable("Unexpected register position type: " + type);
+ }
+ }
+
+ private boolean holdsConstant(int index) {
return registerHoldsConstant.get(index);
}
- public void set(int index, int value, boolean holdsConstant) {
+ private boolean holdsMonitor(int index) { return registerHoldsMonitor.get(index); }
+
+ public void set(int index, int value) {
if (index >= backing.length) {
grow(index + 1);
}
backing[index] = value;
- registerHoldsConstant.set(index, holdsConstant);
+ }
+
+ public void set(int index, int value, LiveIntervals intervals) {
+ set(index, value);
+ registerHoldsConstant.set(index, intervals.isConstantNumberInterval());
+ registerHoldsMonitor.set(index, intervals.usedInMonitorOperation());
}
public int get(int index) {
