Fix bug in inactive linked interval splitting.
Linked intervals have fixed registers for all uses to make sure
that values are in consecutive registers at ranged invokes.
Therefore, when splitting an inactive linked interval, we need
to split before the next use and make sure that the same
register is used again at that use. However, if there are
no uses after the split point, there is no need to split and
attempting to do so will lead to an index out of bounds
exception.
R=sgjesse@google.com
Bug: 68656641
Change-Id: Iacd878895532f80c24adb52e9ce4c9abed57bf98
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 523d6db..5783ad4 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
@@ -136,9 +136,9 @@
// List of active intervals.
private List<LiveIntervals> active = new LinkedList<>();
// List of intervals where the current instruction falls into one of their live range holes.
- private List<LiveIntervals> inactive = new LinkedList<>();
+ protected List<LiveIntervals> inactive = new LinkedList<>();
// List of intervals that no register has been allocated to sorted by first live range.
- private PriorityQueue<LiveIntervals> unhandled = new PriorityQueue<>();
+ protected PriorityQueue<LiveIntervals> unhandled = new PriorityQueue<>();
// The first register used for parallel moves. After register allocation the parallel move
// temporary registers are [firstParallelMoveTemporary, maxRegisterNumber].
@@ -1517,7 +1517,7 @@
splitOverlappingInactiveIntervals(unhandledInterval, needsRegisterPair, candidate);
}
- private void splitOverlappingInactiveIntervals(
+ protected void splitOverlappingInactiveIntervals(
LiveIntervals unhandledInterval,
boolean needsRegisterPair,
int candidate) {
@@ -1529,10 +1529,16 @@
(needsRegisterPair && intervals.usesRegister(candidate + 1))) &&
intervals.overlaps(unhandledInterval)) {
if (intervals.isLinked() && !intervals.isArgumentInterval()) {
+ // If the inactive register is linked but not an argument, it needs to get the
+ // same register again at the next use after the start of the unhandled interval.
+ // If there are no such uses, we can use a different register for the remainder
+ // of the inactive interval and therefore do not have to split here.
int nextUsePosition = intervals.firstUseAfter(unhandledInterval.getStart());
- LiveIntervals split = intervals.splitBefore(nextUsePosition);
- split.setRegister(intervals.getRegister());
- newInactive.add(split);
+ if (nextUsePosition != Integer.MAX_VALUE) {
+ LiveIntervals split = intervals.splitBefore(nextUsePosition);
+ split.setRegister(intervals.getRegister());
+ newInactive.add(split);
+ }
}
if (intervals.getStart() > unhandledInterval.getStart()) {
// The inactive live intervals hasn't started yet. Clear the temporary register
diff --git a/src/test/java/com/android/tools/r8/ir/regalloc/Regress68656641.java b/src/test/java/com/android/tools/r8/ir/regalloc/Regress68656641.java
new file mode 100644
index 0000000..1d17e31
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/ir/regalloc/Regress68656641.java
@@ -0,0 +1,83 @@
+// Copyright (c) 2017, 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.ir.regalloc;
+
+import com.android.tools.r8.graph.DexApplication;
+import com.android.tools.r8.graph.DexEncodedMethod;
+import com.android.tools.r8.ir.code.IRCode;
+import com.android.tools.r8.ir.code.Value;
+import com.android.tools.r8.ir.code.ValueNumberGenerator;
+import com.android.tools.r8.ir.code.ValueType;
+import com.android.tools.r8.smali.SmaliTestBase;
+import com.android.tools.r8.utils.InternalOptions;
+import com.google.common.collect.ImmutableList;
+import java.util.PriorityQueue;
+import org.junit.Test;
+
+public class Regress68656641 extends SmaliTestBase {
+
+ private static class MyRegisterAllocator extends LinearScanRegisterAllocator {
+ public MyRegisterAllocator(IRCode code, InternalOptions options) {
+ super(code, options);
+ }
+
+ public void addInactiveIntervals(LiveIntervals intervals) {
+ inactive.add(intervals);
+ }
+
+ public void splitOverlappingInactiveIntervals(LiveIntervals intervals, int register) {
+ splitOverlappingInactiveIntervals(intervals, false, register);
+ }
+
+ public PriorityQueue<LiveIntervals> getUnhandled() {
+ return unhandled;
+ }
+ }
+
+ IRCode simpleCode(InternalOptions options) throws Exception {
+ SmaliBuilder builder = new SmaliBuilder(DEFAULT_CLASS_NAME);
+ MethodSignature signature = builder.addStaticMethod(
+ "void",
+ DEFAULT_METHOD_NAME,
+ ImmutableList.of(),
+ 1,
+ " return-void");
+ DexApplication application = buildApplication(builder, options);
+ // Build the code, and split the code into three blocks.
+ ValueNumberGenerator valueNumberGenerator = new ValueNumberGenerator();
+ DexEncodedMethod method = getMethod(application, signature);
+ IRCode code = method.buildIR(new InternalOptions(), valueNumberGenerator);
+ return code;
+ }
+
+
+ @Test
+ public void splitOverlappingInactiveIntervalWithNoNextUse() throws Exception {
+ InternalOptions options = new InternalOptions();
+ IRCode code = simpleCode(options);
+ MyRegisterAllocator allocator = new MyRegisterAllocator(code, options);
+ // Setup live an inactive live interval with ranges [0, 10[ and [20, 30[ with only
+ // uses in the first interval and which is linked to another interval.
+ LiveIntervals inactiveIntervals = new LiveIntervals(new Value(0, ValueType.INT, null));
+ inactiveIntervals.addRange(new LiveRange(0, 10));
+ inactiveIntervals.addUse(new LiveIntervalsUse(0, 10));
+ inactiveIntervals.addUse(new LiveIntervalsUse(4, 10));
+ inactiveIntervals.addRange(new LiveRange(20, 30));
+ inactiveIntervals.setRegister(0);
+ LiveIntervals linked = new LiveIntervals(new Value(1, ValueType.INT, null));
+ linked.setRegister(1);
+ inactiveIntervals.link(linked);
+ allocator.addInactiveIntervals(inactiveIntervals);
+ // Setup an unhandled interval that overlaps the inactive interval.
+ LiveIntervals unhandledIntervals = new LiveIntervals(new Value(2, ValueType.INT, null));
+ unhandledIntervals.addRange(new LiveRange(12, 24));
+ // Split the overlapping inactive intervals and check that after the split, the second
+ // part of the inactive interval is unhandled and will therefore get a new register
+ // assigned later during allocation.
+ allocator.splitOverlappingInactiveIntervals(unhandledIntervals, 0);
+ assert allocator.getUnhandled().size() == 1;
+ assert allocator.getUnhandled().peek().getStart() == 20;
+ assert allocator.getUnhandled().peek().getEnd() == 30;
+ }
+}
