Change register allocator to deal better with unconstrained uses.
When low on registers, if the interval we are currently attempting
to allocate a register for has an unconstrained first use, split
the current interval instead of finding another interval to split.
In addition, make the determination of when to split argument
values right after their definition more precise.
These changes shouldn't matter much at this point. However,
zerny@ is working on changes to debug information handling
that will make this occur a lot more for arguments. For such
cases this is needed and generates better code than we currently
do.
R=zerny@google.com
Change-Id: I6d83b91a15486d294c2c66f68b17cb871c0cbae1
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 33dc79a..a30f574 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
@@ -567,18 +567,18 @@
active.add(argumentInterval);
} else {
// Treat the argument interval as spilled which will require a load to a different
- // register for all usages.
+ // register for all register-constrained usages.
if (argumentInterval.getUses().size() > 1) {
LiveIntervalsUse use = argumentInterval.firstUseWithConstraint();
if (use != null) {
LiveIntervals split;
- if (argumentInterval.getUses().size() == 2) {
- // If there is only one real use (definition plus one real use), split before
+ if (argumentInterval.numberOfUsesWithConstraint() == 1) {
+ // If there is only one register-constrained use, split before
// that one use.
split = argumentInterval.splitBefore(use.getPosition());
} else {
- // If there are multiple real users, split right after the definition to make it
- // more likely that arguments get in usable registers from the start.
+ // If there are multiple register-constrained users, split right after the definition
+ // to make it more likely that arguments get in usable registers from the start.
split = argumentInterval
.splitBefore(argumentInterval.getValue().definition.getNumber() + 1);
}
@@ -1004,7 +1004,24 @@
// argument reuse disallowed.
return false;
}
- allocateBlockedRegister(unhandledInterval);
+ // If the first use for these intervals is unconstrained, just spill this interval instead
+ // of finding another candidate to spill via allocateBlockedRegister.
+ if (!unhandledInterval.getUses().first().hasConstraint()) {
+ int nextConstrainedPosition = unhandledInterval.firstUseWithConstraint().getPosition();
+ int register;
+ // Arguments are always in the argument registers, so for arguments just use that register
+ // for the unconstrained prefix. For everything else, get a spill register.
+ if (unhandledInterval.isArgumentInterval()) {
+ register = unhandledInterval.getSplitParent().getRegister();
+ } else {
+ register = getSpillRegister(unhandledInterval);
+ }
+ LiveIntervals split = unhandledInterval.splitBefore(nextConstrainedPosition);
+ assignRegisterToUnhandledInterval(unhandledInterval, needsRegisterPair, register);
+ unhandled.add(split);
+ } else {
+ allocateBlockedRegister(unhandledInterval);
+ }
} else if (largestFreePosition >= unhandledInterval.getEnd()) {
// Free for the entire interval. Allocate the register.
assignRegisterToUnhandledInterval(unhandledInterval, needsRegisterPair, candidate);
@@ -1016,8 +1033,7 @@
}
// The candidate is free for the beginning of an interval. We split the interval
// and use the register for as long as we can.
- int splitPosition = largestFreePosition;
- LiveIntervals split = unhandledInterval.splitBefore(splitPosition);
+ LiveIntervals split = unhandledInterval.splitBefore(largestFreePosition);
assert split != unhandledInterval;
assignRegisterToUnhandledInterval(unhandledInterval, needsRegisterPair, candidate);
unhandled.add(split);
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 cf44137..f01ed3a 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
@@ -3,6 +3,7 @@
// BSD-style license that can be found in the LICENSE file.
package com.android.tools.r8.ir.regalloc;
+import static com.android.tools.r8.dex.Constants.U16BIT_MAX;
import static com.android.tools.r8.ir.regalloc.LinearScanRegisterAllocator.NO_REGISTER;
import com.android.tools.r8.dex.Constants;
@@ -29,7 +30,7 @@
private boolean spilled = false;
// Only registers up to and including the registerLimit are allowed for this interval.
- private int registerLimit = Constants.U16BIT_MAX;
+ private int registerLimit = U16BIT_MAX;
// Max register used for any of the non-spilled splits for these live intervals or for any of the
// live intervals that this live interval is connected to by phi moves. This is used to
@@ -331,7 +332,7 @@
public LiveIntervalsUse firstUseWithConstraint() {
for (LiveIntervalsUse use : uses) {
- if (use.getLimit() < Constants.U16BIT_MAX) {
+ if (use.hasConstraint()) {
return use;
}
}
@@ -386,13 +387,14 @@
}
private void recomputeLimit() {
- registerLimit = Constants.U16BIT_MAX;
+ registerLimit = U16BIT_MAX;
for (LiveIntervalsUse use : uses) {
updateRegisterConstraint(use.getLimit());
}
}
public LiveIntervals getSplitCovering(int instructionNumber) {
+ assert getSplitParent() == this;
// Check if this interval itself is covering the instruction.
if (getStart() <= instructionNumber && getEnd() > instructionNumber) {
return this;
@@ -417,6 +419,20 @@
return null;
}
+ public boolean isConstantNumberInterval() {
+ return value.definition != null && value.definition.isConstNumber();
+ }
+
+ public int numberOfUsesWithConstraint() {
+ int count = 0;
+ for (LiveIntervalsUse use : getUses()) {
+ if (use.hasConstraint()) {
+ count++;
+ }
+ }
+ return count;
+ }
+
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
@@ -468,8 +484,4 @@
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/LiveIntervalsUse.java b/src/main/java/com/android/tools/r8/ir/regalloc/LiveIntervalsUse.java
index fd37af8..a602134 100644
--- a/src/main/java/com/android/tools/r8/ir/regalloc/LiveIntervalsUse.java
+++ b/src/main/java/com/android/tools/r8/ir/regalloc/LiveIntervalsUse.java
@@ -3,6 +3,8 @@
// BSD-style license that can be found in the LICENSE file.
package com.android.tools.r8.ir.regalloc;
+import static com.android.tools.r8.dex.Constants.U16BIT_MAX;
+
public class LiveIntervalsUse implements Comparable<LiveIntervalsUse> {
private int position;
private int limit;
@@ -41,4 +43,8 @@
}
return limit - o.limit;
}
+
+ public boolean hasConstraint() {
+ return limit < U16BIT_MAX;
+ }
}
