Update how register candidate is chosen
- Firstly try to find a register candidate that is a constant that
can be rematerialized. If it does not exist or if hos live range is
too short, fallback to select a register that can not be rematerialized.
It allows to save 14608 bytes on GMSCore V10(deploy jar), 15080 bytes
on GMSCore v9 (deploy jar) and for dex file related to the bug, it
allows to have 49880 bytes instead of 56380 bytes in debug mode and it
allows to have 48424 bytes instead of 55324 in release mode.
BUG: 62475297
Change-Id: I497c13a4c3dd8bdd6acafc6e2a3197648604035f
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 41759aa..33dc79a 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
@@ -62,6 +62,8 @@
*/
public class LinearScanRegisterAllocator implements RegisterAllocator {
public static final int NO_REGISTER = Integer.MIN_VALUE;
+ public static final int REGISTER_CANDIDATE_NOT_FOUND = -1;
+ public static final int MIN_CONSTANT_FREE_FOR_POSITIONS = 5;
private enum ArgumentReuseMode {
ALLOW_ARGUMENT_REUSE,
@@ -916,17 +918,17 @@
if (mode == ArgumentReuseMode.ALLOW_ARGUMENT_REUSE) {
// The sentinel registers cannot be used and we block them.
- freePositions.set(0, 0);
+ freePositions.set(0, 0, false);
int lastSentinelRegister = numberOfArgumentRegisters + NUMBER_OF_SENTINEL_REGISTERS - 1;
if (lastSentinelRegister <= registerConstraint) {
- freePositions.set(lastSentinelRegister, 0);
+ freePositions.set(lastSentinelRegister, 0, false);
}
} 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);
+ freePositions.set(i, 0, false);
}
}
}
@@ -938,7 +940,7 @@
if (hasDedicatedMoveExceptionRegister) {
int moveExceptionRegister = numberOfArgumentRegisters + NUMBER_OF_SENTINEL_REGISTERS;
if (moveExceptionRegister <= registerConstraint) {
- freePositions.set(moveExceptionRegister, 0);
+ freePositions.set(moveExceptionRegister, 0, false);
}
}
@@ -948,7 +950,7 @@
if (activeRegister <= registerConstraint) {
for (int i = 0; i < intervals.requiredRegisters(); i++) {
if (activeRegister + i <= registerConstraint) {
- freePositions.set(activeRegister + i, 0);
+ freePositions.set(activeRegister + i, 0, intervals.isConstantNumberInterval());
}
}
}
@@ -961,17 +963,18 @@
if (inactiveRegister <= registerConstraint && unhandledInterval.overlaps(intervals)) {
int nextOverlap = unhandledInterval.nextOverlap(intervals);
for (int i = 0; i < intervals.requiredRegisters(); i++) {
- if (inactiveRegister + i <= registerConstraint) {
+ int register = inactiveRegister + i;
+ if (register <= registerConstraint) {
int unhandledStart = toInstructionPosition(unhandledInterval.getStart());
if (nextOverlap == unhandledStart) {
// 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(inactiveRegister + i, 0);
+ freePositions.set(register, 0, freePositions.holdsConstant(register));
} else {
- freePositions.set(
- inactiveRegister + i,
- Math.min(freePositions.get(inactiveRegister + i), nextOverlap));
+ if (nextOverlap < freePositions.get(register)) {
+ freePositions.set(register, nextOverlap, intervals.isConstantNumberInterval());
+ }
}
}
}
@@ -986,7 +989,8 @@
// 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);
+ unhandledInterval, registerConstraint, needsRegisterPair, freePositions, false);
+ assert candidate != REGISTER_CANDIDATE_NOT_FOUND;
int largestFreePosition = freePositions.get(candidate);
if (needsRegisterPair) {
largestFreePosition = Math.min(largestFreePosition, freePositions.get(candidate + 1));
@@ -1138,14 +1142,15 @@
active.add(unhandledInterval);
}
- private int getLargestCandidate(
- int registerConstraint, RegisterPositions freePositions, boolean needsRegisterPair) {
- int candidate = 0;
- int largest = freePositions.get(0);
- if (needsRegisterPair) {
- largest = Math.min(largest, freePositions.get(1));
- }
- for (int i = 1; i <= registerConstraint; i++) {
+ private int getLargestCandidate(int registerConstraint, RegisterPositions freePositions,
+ boolean needsRegisterPair, boolean restrictToConstant) {
+ int candidate = REGISTER_CANDIDATE_NOT_FOUND;
+ int largest = -1;
+
+ for (int i = 0; i <= registerConstraint; i++) {
+ if (restrictToConstant && !freePositions.holdsConstant(i)) {
+ continue;
+ }
int freePosition = freePositions.get(i);
if (needsRegisterPair) {
if (i >= registerConstraint) {
@@ -1161,17 +1166,23 @@
}
}
}
+
return candidate;
}
private int getLargestValidCandidate(LiveIntervals unhandledInterval, int registerConstraint,
- boolean needsRegisterPair, RegisterPositions freePositions) {
- int candidate = getLargestCandidate(registerConstraint, freePositions, needsRegisterPair);
+ boolean needsRegisterPair, RegisterPositions freePositions, boolean restrictToConstant) {
+ int candidate = getLargestCandidate(registerConstraint, freePositions, needsRegisterPair,
+ restrictToConstant);
+ 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);
- candidate = getLargestCandidate(registerConstraint, freePositions, needsRegisterPair);
+ freePositions.set(candidate, 0, freePositions.holdsConstant(candidate));
+ candidate = getLargestCandidate(registerConstraint, freePositions, needsRegisterPair,
+ restrictToConstant);
}
}
return candidate;
@@ -1198,7 +1209,8 @@
for (int i = 0; i < intervals.requiredRegisters(); i++) {
if (activeRegister + i <= registerConstraint) {
int unhandledStart = unhandledInterval.getStart();
- usePositions.set(activeRegister + i, intervals.firstUseAfter(unhandledStart));
+ usePositions.set(activeRegister + i, intervals.firstUseAfter(unhandledStart),
+ intervals.isConstantNumberInterval());
}
}
}
@@ -1210,9 +1222,11 @@
if (inactiveRegister <= registerConstraint && intervals.overlaps(unhandledInterval)) {
for (int i = 0; i < intervals.requiredRegisters(); i++) {
if (inactiveRegister + i <= registerConstraint) {
- int unhandledStart = unhandledInterval.getStart();
- usePositions.set(inactiveRegister + i, Math.min(
- usePositions.get(inactiveRegister + i), intervals.firstUseAfter(unhandledStart)));
+ int firstUse = intervals.firstUseAfter(unhandledInterval.getStart());
+ if (firstUse < usePositions.get(inactiveRegister + i)) {
+ usePositions.set(inactiveRegister + i, firstUse,
+ intervals.isConstantNumberInterval());
+ }
}
}
}
@@ -1221,12 +1235,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);
+ usePositions.set(i, 0, false);
}
// Disallow reuse of the move exception register if we have reserved one.
if (hasDedicatedMoveExceptionRegister) {
- usePositions.set(numberOfArgumentRegisters + NUMBER_OF_SENTINEL_REGISTERS, 0);
+ usePositions.set(numberOfArgumentRegisters + NUMBER_OF_SENTINEL_REGISTERS, 0, false);
}
// Treat active linked argument intervals as pinned. They cannot be given another register
@@ -1241,18 +1255,26 @@
// Get the register (pair) that has the highest use position.
boolean needsRegisterPair = unhandledInterval.requiredRegisters() == 2;
- int candidate = getLargestValidCandidate(
- unhandledInterval, registerConstraint, needsRegisterPair, usePositions);
- int largestUsePosition = usePositions.get(candidate);
- int blockedPosition = blockedPositions.get(candidate);
- if (needsRegisterPair) {
- blockedPosition = Math.min(blockedPosition, blockedPositions.get(candidate + 1));
- largestUsePosition = Math.min(largestUsePosition, usePositions.get(candidate + 1));
+
+ int candidate = getLargestValidCandidate(unhandledInterval, registerConstraint,
+ needsRegisterPair, usePositions, true);
+ 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;
+ } else {
+ 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;
+ }
+ }
}
- // TODO(ager): When selecting a spill candidate also take rematerialization into account.
- // Prefer spilling a constant that can be rematerialized instead of spilling something that
- // cannot be rematerialized.
+ int largestUsePosition = getLargestPosition(usePositions, candidate, needsRegisterPair);
+ int blockedPosition = getBlockedPosition(blockedPositions, candidate, needsRegisterPair);
if (largestUsePosition < unhandledInterval.getFirstUse()) {
// All active and inactive intervals are used before current. Therefore, it is best to spill
@@ -1279,6 +1301,28 @@
}
}
+ private int getLargestPosition(RegisterPositions usePositions, int register,
+ boolean needsRegisterPair) {
+ int largestUsePosition = usePositions.get(register);
+
+ if (needsRegisterPair) {
+ largestUsePosition = Math.min(largestUsePosition, usePositions.get(register + 1));
+ }
+
+ return largestUsePosition;
+ }
+
+ private int getBlockedPosition(RegisterPositions blockedPositions, int register,
+ boolean needsRegisterPair) {
+ int blockedPosition = blockedPositions.get(register);
+
+ if (needsRegisterPair) {
+ blockedPosition = Math.min(blockedPosition, blockedPositions.get(register + 1));
+ }
+
+ return blockedPosition;
+ }
+
private void assignRegisterAndSpill(
LiveIntervals unhandledInterval, boolean needsRegisterPair, int candidate) {
assignRegister(unhandledInterval, candidate);
@@ -1456,12 +1500,13 @@
if (register <= registerConstraint && other.overlaps(interval)) {
for (int i = 0; i < other.requiredRegisters(); i++) {
if (register + i <= registerConstraint) {
- blockedPositions.set(register + i,
- Math.min(blockedPositions.get(register + i),
- other.firstUseAfter(interval.getStart())));
- // 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);
+ int firstUse = other.firstUseAfter(interval.getStart());
+ if (firstUse < blockedPositions.get(register + i)) {
+ blockedPositions.set(register + i, firstUse, other.isConstantNumberInterval());
+ // 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 c966813..cf44137 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
@@ -468,4 +468,8 @@
splitChild.print(printer, number + delta, number);
}
}
+
+ public boolean isConstantNumberInterval() {
+ return value.definition != null && value.definition.isConstNumber();
+ }
}
\ No newline at end of file
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 87eedca..35b87fc 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
@@ -4,6 +4,7 @@
package com.android.tools.r8.ir.regalloc;
import java.util.Arrays;
+import java.util.BitSet;
/**
* Simple mapping from a register to an int value.
@@ -16,6 +17,7 @@
private static final int INITIAL_SIZE = 16;
private int limit;
private int[] backing;
+ private BitSet registerHoldsConstant;
public RegisterPositions(int limit) {
this.limit = limit;
@@ -23,13 +25,19 @@
for (int i = 0; i < INITIAL_SIZE; i++) {
backing[i] = Integer.MAX_VALUE;
}
+ registerHoldsConstant = new BitSet(limit);
}
- public void set(int index, int value) {
+ public boolean holdsConstant(int index) {
+ return registerHoldsConstant.get(index);
+ }
+
+ public void set(int index, int value, boolean holdsConstant) {
if (index >= backing.length) {
grow(index + 1);
}
backing[index] = value;
+ registerHoldsConstant.set(index, holdsConstant);
}
public int get(int index) {
