Fix incorrect comparison of virtual registers in rematerialization
This fixes a register allocation bug that only manifests when methods require more than 256 registers.
The const instructions in DEX have an 8 bit register constraint. When determining if a value can be rematerialized, the register allocator therefore finds the max non-spilled register for the live intervals of the value to check if it fits in 8 bits.
However, in the computation of the max non-spilled register, the register allocator failed to consider that the virtual registers 0...N where N=number of arguments are larger than registers N+1...M where M is the max virtual register.
Bug: b/408438353
Change-Id: I6c9d8c0d99bdb77a1678411995df5579f91b9ef3
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 1816c75..b091a88 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
@@ -948,6 +948,7 @@
}
}
} else {
+ assert !mode.is8BitRetry();
assert !mode.is16Bit();
}
@@ -963,7 +964,8 @@
break;
case ALLOW_ARGUMENT_REUSE_U8BIT:
- if (highestUsedRegister() > Constants.U8BIT_MAX
+ if (!succeeded
+ || highestUsedRegister() > Constants.U8BIT_MAX
|| options().getTestingOptions().alwaysUsePessimisticRegisterAllocation) {
// Redo allocation in mode ALLOW_ARGUMENT_REUSE_U16BIT. This always succeed.
unusedRegisters = null;
@@ -980,7 +982,8 @@
break;
case ALLOW_ARGUMENT_REUSE_U8BIT_REFINEMENT:
- if (highestUsedRegister() > Constants.U8BIT_MAX
+ if (!succeeded
+ || highestUsedRegister() > Constants.U8BIT_MAX
|| numberOf4BitArgumentRegisters > computeNumberOf4BitArgumentRegisters()) {
// Redo allocation in mode ALLOW_ARGUMENT_REUSE_U8BIT_RETRY. This always succeed.
numberOf4BitArgumentRegisters = 0;
@@ -3113,7 +3116,7 @@
private void computeRematerializableBits() {
for (LiveIntervals liveInterval : liveIntervals) {
- liveInterval.computeRematerializable(this);
+ liveInterval.computeRematerializable(this, mode);
}
}
@@ -3208,6 +3211,23 @@
return register < numberOfArgumentRegisters;
}
+ public int maxVirtualRegister(int register, int other) {
+ if (register == NO_REGISTER) {
+ return other;
+ }
+ if (other == NO_REGISTER) {
+ return register;
+ }
+ if (isArgumentRegister(register)) {
+ if (!isArgumentRegister(other)) {
+ return register;
+ }
+ } else if (isArgumentRegister(other)) {
+ return other;
+ }
+ return Math.max(register, other);
+ }
+
boolean canSkipArgumentMove(LiveIntervals intervals) {
if (!isPinnedArgumentRegister(intervals)) {
return false;
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 816d263..1703894 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
@@ -348,7 +348,7 @@
liveAtMoveExceptionEntry = true;
}
- private int computeMaxNonSpilledRegister() {
+ private int computeMaxNonSpilledRegister(LinearScanRegisterAllocator allocator) {
assert splitParent == this;
assert maxNonSpilledRegister == NO_REGISTER;
if (!isSpilled()) {
@@ -356,22 +356,23 @@
}
for (LiveIntervals child : splitChildren) {
if (!child.isSpilled()) {
- maxNonSpilledRegister = Math.max(maxNonSpilledRegister, child.getRegister());
+ maxNonSpilledRegister =
+ allocator.maxVirtualRegister(maxNonSpilledRegister, child.getRegister());
}
}
return maxNonSpilledRegister;
}
- public void setMaxNonSpilledRegister(int i) {
- assert i >= splitParent.maxNonSpilledRegister;
- splitParent.maxNonSpilledRegister = i;
+ public void setMaxNonSpilledRegister(int register, LinearScanRegisterAllocator allocator) {
+ assert allocator.maxVirtualRegister(register, splitParent.maxNonSpilledRegister) == register;
+ splitParent.maxNonSpilledRegister = register;
}
- public int getMaxNonSpilledRegister() {
+ public int getMaxNonSpilledRegister(LinearScanRegisterAllocator allocator) {
if (splitParent.maxNonSpilledRegister != NO_REGISTER) {
return splitParent.maxNonSpilledRegister;
}
- return splitParent.computeMaxNonSpilledRegister();
+ return splitParent.computeMaxNonSpilledRegister(allocator);
}
public boolean usesRegister(int n, boolean otherIsWide) {
@@ -716,7 +717,8 @@
return builder.toString();
}
- public void computeRematerializable(LinearScanRegisterAllocator allocator) {
+ public void computeRematerializable(
+ LinearScanRegisterAllocator allocator, ArgumentReuseMode mode) {
assert splitParent == this;
if (value.isArgument()) {
isRematerializable = true;
@@ -732,6 +734,11 @@
return;
}
+ if (!mode.is16Bit()) {
+ isRematerializable = true;
+ return;
+ }
+
// If the constant is spilled when flowing to a phi and the phi has a register higher than what
// can be const rematerialized then this value is not rematerializable and needs a register even
// when spilled.
@@ -757,12 +764,13 @@
// these computations. We use the unadjusted real register number to make sure that
// isRematerializable for the same intervals does not change from one phase of
// compilation to the next.
- if (getMaxNonSpilledRegister() == NO_REGISTER) {
+ int maxNonSpilledRegister = getMaxNonSpilledRegister(allocator);
+ if (maxNonSpilledRegister == NO_REGISTER) {
assert allSplitsAreSpilled();
isRematerializable = true;
- return;
+ } else {
+ int maxRealRegister = allocator.unadjustedRealRegisterFromAllocated(maxNonSpilledRegister);
+ isRematerializable = maxRealRegister < U8BIT_MAX;
}
- int max = allocator.unadjustedRealRegisterFromAllocated(getMaxNonSpilledRegister());
- isRematerializable = max < U8BIT_MAX;
}
}
diff --git a/src/main/java/com/android/tools/r8/ir/regalloc/SpillMove.java b/src/main/java/com/android/tools/r8/ir/regalloc/SpillMove.java
index 3edfd86..aed222b 100644
--- a/src/main/java/com/android/tools/r8/ir/regalloc/SpillMove.java
+++ b/src/main/java/com/android/tools/r8/ir/regalloc/SpillMove.java
@@ -29,13 +29,13 @@
return type.hashCode() + 3 * from.getRegister() + 5 * to.getRegister();
}
- public void updateMaxNonSpilled() {
- int maxFrom = from.getMaxNonSpilledRegister();
- int maxTo = to.getMaxNonSpilledRegister();
- if (maxFrom > maxTo) {
- to.setMaxNonSpilledRegister(maxFrom);
+ public void updateMaxNonSpilled(LinearScanRegisterAllocator allocator) {
+ int maxFrom = from.getMaxNonSpilledRegister(allocator);
+ int maxTo = to.getMaxNonSpilledRegister(allocator);
+ if (allocator.maxVirtualRegister(maxFrom, maxTo) == maxFrom) {
+ to.setMaxNonSpilledRegister(maxFrom, allocator);
} else {
- from.setMaxNonSpilledRegister(maxTo);
+ from.setMaxNonSpilledRegister(maxTo, allocator);
}
}
diff --git a/src/main/java/com/android/tools/r8/ir/regalloc/SpillMoveSet.java b/src/main/java/com/android/tools/r8/ir/regalloc/SpillMoveSet.java
index 736ed62..dfe4e74 100644
--- a/src/main/java/com/android/tools/r8/ir/regalloc/SpillMoveSet.java
+++ b/src/main/java/com/android/tools/r8/ir/regalloc/SpillMoveSet.java
@@ -100,7 +100,7 @@
public void addPhiMove(int i, LiveIntervals to, LiveIntervals from) {
assert i % 2 == 1;
SpillMove move = new SpillMove(moveTypeForIntervals(to, from), to, from);
- move.updateMaxNonSpilled();
+ move.updateMaxNonSpilled(allocator);
instructionToPhiMoves.computeIfAbsent(i, (k) -> new LinkedHashSet<>()).add(move);
}
