Version 1.6.52
Cherry-pick: Improve handling of register allocation for intervals
same start.
CL: https://r8-review.googlesource.com/c/r8/+/45627
Bug: 142682636
Change-Id: Ib854a49cc1f849d660b3186d88c081f485616438
diff --git a/src/main/java/com/android/tools/r8/Version.java b/src/main/java/com/android/tools/r8/Version.java
index e9ad7d9..004eb44 100644
--- a/src/main/java/com/android/tools/r8/Version.java
+++ b/src/main/java/com/android/tools/r8/Version.java
@@ -11,7 +11,7 @@
// This field is accessed from release scripts using simple pattern matching.
// Therefore, changing this field could break our release scripts.
- public static final String LABEL = "1.6.51";
+ public static final String LABEL = "1.6.52";
private Version() {
}
diff --git a/src/main/java/com/android/tools/r8/cf/CfRegisterAllocator.java b/src/main/java/com/android/tools/r8/cf/CfRegisterAllocator.java
index ec6710b..93fc650 100644
--- a/src/main/java/com/android/tools/r8/cf/CfRegisterAllocator.java
+++ b/src/main/java/com/android/tools/r8/cf/CfRegisterAllocator.java
@@ -229,8 +229,7 @@
// Find a free register that is not used by an inactive interval that overlaps with
// unhandledInterval.
if (tryHint(unhandledInterval)) {
- assignRegisterToUnhandledInterval(
- unhandledInterval, unhandledInterval.getHint().getRegister());
+ assignRegisterToUnhandledInterval(unhandledInterval, unhandledInterval.getHint());
} else {
boolean wide = unhandledInterval.getType().isWide();
int register;
@@ -304,9 +303,9 @@
private void updateHints(LiveIntervals intervals) {
for (Phi phi : intervals.getValue().uniquePhiUsers()) {
if (!phi.isValueOnStack()) {
- phi.getLiveIntervals().setHint(intervals);
+ phi.getLiveIntervals().setHint(intervals, unhandled);
for (Value value : phi.getOperands()) {
- value.getLiveIntervals().setHint(intervals);
+ value.getLiveIntervals().setHint(intervals, unhandled);
}
}
}
@@ -317,7 +316,7 @@
return false;
}
boolean isWide = unhandled.getType().isWide();
- int hintRegister = unhandled.getHint().getRegister();
+ int hintRegister = unhandled.getHint();
if (freeRegisters.contains(hintRegister)
&& (!isWide || freeRegisters.contains(hintRegister + 1))) {
for (LiveIntervals inactive : inactive) {
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 8456912..c30e9d1 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
@@ -1056,7 +1056,7 @@
if (checkcastInput.getLiveIntervals() != null &&
!checkcastInput.getLiveIntervals().overlaps(unhandledInterval) &&
checkcastInput.getLocalInfo() == unhandledInterval.getValue().definition.getLocalInfo()) {
- unhandledInterval.setHint(checkcastInput.getLiveIntervals());
+ unhandledInterval.setHint(checkcastInput.getLiveIntervals(), unhandled);
}
}
}
@@ -1074,13 +1074,13 @@
assert left != null;
if (left.getLiveIntervals() != null &&
!left.getLiveIntervals().overlaps(unhandledInterval)) {
- unhandledInterval.setHint(left.getLiveIntervals());
+ unhandledInterval.setHint(left.getLiveIntervals(), unhandled);
} else {
Value right = binOp.rightValue();
assert right != null;
if (binOp.isCommutative() && right.getLiveIntervals() != null &&
!right.getLiveIntervals().overlaps(unhandledInterval)) {
- unhandledInterval.setHint(right.getLiveIntervals());
+ unhandledInterval.setHint(right.getLiveIntervals(), unhandled);
}
}
}
@@ -1209,7 +1209,7 @@
if (!value.isPhi() && value.definition.isMove()) {
Move move = value.definition.asMove();
LiveIntervals intervals = move.src().getLiveIntervals();
- intervals.setHint(current);
+ intervals.setHint(current, unhandled);
}
if (current != unhandledInterval) {
// Only the start of unhandledInterval has been reached at this point. All other live
@@ -1777,11 +1777,9 @@
// spilling. For phis we also use the hint before looking at the operand registers. The
// phi could have a hint from an argument moves which it seems more important to honor in
// practice.
- LiveIntervals hint = unhandledInterval.getHint();
+ Integer hint = unhandledInterval.getHint();
if (hint != null) {
- int register = hint.getRegister();
- if (tryHint(unhandledInterval, registerConstraint, freePositions, needsRegisterPair,
- register)) {
+ if (tryHint(unhandledInterval, registerConstraint, freePositions, needsRegisterPair, hint)) {
return true;
}
}
@@ -1862,13 +1860,14 @@
for (Phi phi : value.uniquePhiUsers()) {
LiveIntervals phiIntervals = phi.getLiveIntervals();
if (phiIntervals.getHint() == null) {
+ phiIntervals.setHint(intervals, unhandled);
for (int i = 0; i < phi.getOperands().size(); i++) {
Value operand = phi.getOperand(i);
LiveIntervals operandIntervals = operand.getLiveIntervals();
BasicBlock pred = phi.getBlock().getPredecessors().get(i);
operandIntervals = operandIntervals.getSplitCovering(pred.exit().getNumber());
if (operandIntervals.getHint() == null) {
- operandIntervals.setHint(intervals);
+ operandIntervals.setHint(intervals, unhandled);
}
}
}
@@ -1885,7 +1884,7 @@
BasicBlock pred = block.getPredecessors().get(i);
LiveIntervals operandIntervals =
operand.getLiveIntervals().getSplitCovering(pred.exit().getNumber());
- operandIntervals.setHint(intervals);
+ operandIntervals.setHint(intervals, unhandled);
}
}
}
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 0251687..9cb4c09 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
@@ -17,6 +17,7 @@
import java.util.Comparator;
import java.util.Iterator;
import java.util.List;
+import java.util.PriorityQueue;
import java.util.TreeSet;
import java.util.function.IntConsumer;
@@ -36,7 +37,7 @@
private final TreeSet<LiveIntervalsUse> uses = new TreeSet<>();
private int numberOfConsecutiveRegisters = -1;
private int register = NO_REGISTER;
- private LiveIntervals hint;
+ private Integer hint;
private boolean spilled = false;
private boolean usedInMonitorOperations = false;
@@ -82,11 +83,20 @@
return getType().requiredRegisters();
}
- public void setHint(LiveIntervals intervals) {
- hint = intervals;
+ public void setHint(LiveIntervals intervals, PriorityQueue<LiveIntervals> unhandled) {
+ // Do not set hints if they cannot be used anyway.
+ if (!overlaps(intervals)) {
+ // The hint is used in sorting the unhandled intervals. Therefore, if the hint changes
+ // we have to remove and reinsert the interval to get the sorting updated.
+ boolean removed = unhandled.remove(this);
+ hint = intervals.getRegister();
+ if (removed) {
+ unhandled.add(this);
+ }
+ }
}
- public LiveIntervals getHint() {
+ public Integer getHint() {
return hint;
}
@@ -537,8 +547,23 @@
@Override
public int compareTo(LiveIntervals other) {
+ // Sort by interval start instruction number.
int startDiff = getStart() - other.getStart();
- return startDiff != 0 ? startDiff : (value.getNumber() - other.value.getNumber());
+ if (startDiff != 0) return startDiff;
+ // Then sort by register number of hints to make sure that a phi
+ // does not take a low register that is the hint for another phi.
+ if (hint != null && other.hint != null) {
+ int registerDiff = hint - other.hint;
+ if (registerDiff != 0) return registerDiff;
+ }
+ // Intervals with hints go first so intervals without hints
+ // do not take registers from intervals with hints.
+ if (hint != null && other.hint == null) return -1;
+ if (hint == null && other.hint != null) return 1;
+ // Tie-breaker: no values have equal numbers.
+ int result = value.getNumber() - other.value.getNumber();
+ assert result != 0;
+ return result;
}
@Override
diff --git a/src/test/java/com/android/tools/r8/regress/b142682636/Regress142682636.java b/src/test/java/com/android/tools/r8/regress/b142682636/Regress142682636.java
new file mode 100644
index 0000000..2bef90c
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/regress/b142682636/Regress142682636.java
@@ -0,0 +1,20 @@
+// Copyright (c) 2019, 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.regress.b142682636;
+
+class Regress142682636 {
+ static void foo(long v, byte[] a, int s, int b) {
+ for (int i = s; i < s + b; i++) {
+ a[i] = (byte) v;
+ v = v >> 8;
+ }
+ }
+
+ static void bar(int s, long v, byte[] a, int b) {
+ for (int i = s; i < s + b; i++) {
+ a[i] = (byte) v;
+ v = v >> 8;
+ }
+ }
+}
diff --git a/src/test/java/com/android/tools/r8/regress/b142682636/Regress142682636Runner.java b/src/test/java/com/android/tools/r8/regress/b142682636/Regress142682636Runner.java
new file mode 100644
index 0000000..c1a3d6c
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/regress/b142682636/Regress142682636Runner.java
@@ -0,0 +1,40 @@
+package com.android.tools.r8.regress.b142682636;
+
+import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
+import static org.hamcrest.MatcherAssert.assertThat;
+import static org.junit.Assert.assertTrue;
+
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.code.MoveWide;
+import com.android.tools.r8.utils.codeinspector.ClassSubject;
+import com.android.tools.r8.utils.codeinspector.CodeInspector;
+import com.android.tools.r8.utils.codeinspector.MethodSubject;
+import java.util.Arrays;
+import org.junit.Test;
+
+public class Regress142682636Runner extends TestBase {
+ private final Class<?> testClass = Regress142682636.class;
+
+ @Test
+ public void test() throws Exception {
+ CodeInspector inspector = testForD8()
+ .addProgramClasses(testClass)
+ .release()
+ .compile()
+ .inspector();
+ ClassSubject clazz = inspector.clazz(testClass);
+ assertThat(clazz, isPresent());
+ MethodSubject foo = clazz.uniqueMethodWithName("foo");
+ assertThat(foo, isPresent());
+ checkNoMoveWide(foo);
+ MethodSubject bar = clazz.uniqueMethodWithName("bar");
+ assertThat(bar, isPresent());
+ checkNoMoveWide(bar);
+ }
+
+ private void checkNoMoveWide(MethodSubject m) {
+ assertTrue(Arrays.stream(m.getMethod().getCode().asDexCode().instructions)
+ .noneMatch(i -> i instanceof MoveWide));
+ }
+
+}