Fix move scheduler issue and minimize reproduction
This fixes an issue where the dst registers of a move is used as a temporary register for the src registers of the same move.
Change-Id: I5fa0d9635bbc5fcf30bd9b0277ef7e791dbec7b4
diff --git a/src/main/java/com/android/tools/r8/ir/regalloc/RegisterMove.java b/src/main/java/com/android/tools/r8/ir/regalloc/RegisterMove.java
index 70d2ab8..7cf3dfb 100644
--- a/src/main/java/com/android/tools/r8/ir/regalloc/RegisterMove.java
+++ b/src/main/java/com/android/tools/r8/ir/regalloc/RegisterMove.java
@@ -87,6 +87,48 @@
|| (isWide() && scheduler.activeTempRegisters.contains(dst + 1));
}
+ // In order to unblock another move, the src register of a move can be moved to a temporary
+ // register. When the move is wide, the src register may be moved to one of its own destination
+ // registers.
+ //
+ // Example: Consider `move-wide r1, r2 <- r4, r5`. If one of the src registers r4, r5 are blocking
+ // another move, we need to move r4, r5 to a temp. Since the current move-wide has not already
+ // been scheduled, it must be the case that it is itself blocked, i.e., some other move is reading
+ // either r1, r2, or both.
+ //
+ // If both r1, r2 are read by other moves, then r1, r2 cannot be used as temporary registers, and
+ // there is no issue.
+ //
+ // If r1 is read by another move, but r2 is not, then we can use r2 as a temporary register. Thus
+ // to unblock another move, we might create the temporary move `move-wide r2, r3 <- r4, r5`. A
+ // prerequisite for this is that there exists a move `r3 <- _` and that `r3` is not read by any
+ // moves in the move set, so that r3 can also be used as a temporary register.
+ //
+ // (Similarly, we could create the temporary move `move-wide r0, r1 <- r4, r5`.)
+ //
+ // This leads to a situation where a move is blocking itself, because it is using one of its own
+ // registers as a temporary register to unblock another move.
+ public boolean isDestUsedAsTemporaryForSelf(RegisterMoveScheduler scheduler) {
+ assert isDestUsedAsTemporary(scheduler);
+ if (!isWide()) {
+ return false;
+ }
+ // We don't move constants to temporary registers.
+ if (definition != null) {
+ assert src == NO_REGISTER;
+ return false;
+ }
+ int mappedSrc = scheduler.valueMap.get(src);
+ assert mappedSrc != dst;
+ if (mappedSrc == dst - 1 && scheduler.activeTempRegisters.contains(dst)) {
+ return true;
+ }
+ if (mappedSrc == dst + 1 && scheduler.activeTempRegisters.contains(dst + 1)) {
+ return true;
+ }
+ return false;
+ }
+
public boolean isIdentical(RegisterMove move) {
return ObjectUtils.identical(this, move);
}
diff --git a/src/main/java/com/android/tools/r8/ir/regalloc/RegisterMoveScheduler.java b/src/main/java/com/android/tools/r8/ir/regalloc/RegisterMoveScheduler.java
index ea004c3..b71ea38 100644
--- a/src/main/java/com/android/tools/r8/ir/regalloc/RegisterMoveScheduler.java
+++ b/src/main/java/com/android/tools/r8/ir/regalloc/RegisterMoveScheduler.java
@@ -39,7 +39,7 @@
private final TreeSet<RegisterMove> moveSet = new TreeSet<>();
// Mapping to keep track of which values currently corresponds to each other.
// This is initially an identity map but changes as we insert moves.
- private final Int2IntMap valueMap = new Int2IntOpenHashMap();
+ final Int2IntMap valueMap = new Int2IntOpenHashMap();
// Location at which to insert the scheduled moves.
private final InstructionListIterator insertAt;
// Debug position associated with insertion point.
@@ -56,7 +56,7 @@
// Registers that are the destination register of some move in the move set, but which are
// currently being used as a temporary register for another value. Moves in the move set that
// write a register in this set are blocked until the temporary registers are released.
- public final IntSet activeTempRegisters = new IntOpenHashSet();
+ final IntSet activeTempRegisters = new IntOpenHashSet();
public RegisterMoveScheduler(
InstructionListIterator insertAt,
@@ -141,7 +141,8 @@
while (!worklist.isEmpty()) {
while (!worklist.isEmpty()) {
RegisterMove move = worklist.removeFirst();
- assert !move.isBlocked(this, moveSet, valueMap);
+ assert !move.isBlocked(this, moveSet, valueMap)
+ || move.isDestUsedAsTemporaryForSelf(this);
createMove(move);
}
enqueueUnblockedMoves(worklist, movesToSchedule);
@@ -253,7 +254,10 @@
// In order to unblock this move we might have to move more than one value to temporary
// registers if we are unlucky with the overlap for values that use two registers.
List<RegisterMove> movesWithSrc = findMovesWithSrc(move.dst, move.type);
- assert movesWithSrc.size() > 0;
+ if (movesWithSrc.isEmpty()) {
+ assert move.isDestUsedAsTemporaryForSelf(this);
+ return;
+ }
assert verifyMovesHaveDifferentSources(movesWithSrc);
for (RegisterMove moveWithSrc : movesWithSrc) {
// TODO(b/375147902): Maybe seed the move scheduler with a set of registers known to be free
@@ -385,7 +389,9 @@
private RegisterMove pickMoveToUnblock(TreeSet<RegisterMove> moves) {
// Pick a non-wide move to unblock if possible.
Iterable<RegisterMove> eligible =
- Iterables.filter(moves, move -> !move.isDestUsedAsTemporary(this));
+ Iterables.filter(
+ moves,
+ move -> !move.isDestUsedAsTemporary(this) || move.isDestUsedAsTemporaryForSelf(this));
RegisterMove move =
Iterables.find(eligible, not(RegisterMove::isWide), eligible.iterator().next());
moves.remove(move);
diff --git a/src/test/java/com/android/tools/r8/ir/regalloc/RegisterMoveSchedulerTest.java b/src/test/java/com/android/tools/r8/ir/regalloc/RegisterMoveSchedulerTest.java
index 5d57ddb..de6c3c6 100644
--- a/src/test/java/com/android/tools/r8/ir/regalloc/RegisterMoveSchedulerTest.java
+++ b/src/test/java/com/android/tools/r8/ir/regalloc/RegisterMoveSchedulerTest.java
@@ -4,7 +4,6 @@
package com.android.tools.r8.ir.regalloc;
import static org.junit.Assert.assertEquals;
-import static org.junit.Assert.fail;
import com.android.tools.r8.TestBase;
import com.android.tools.r8.TestParameters;
@@ -40,7 +39,6 @@
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
-import java.util.NoSuchElementException;
import java.util.Set;
import java.util.function.Consumer;
import java.util.function.UnaryOperator;
@@ -61,6 +59,10 @@
return list.get(i).asMove();
}
+ public ConstNumber getConst(int i) {
+ return list.get(i).asConstNumber();
+ }
+
public int size() {
return list.size();
}
@@ -589,37 +591,29 @@
@Test
public void reproNoSuchElementException() {
CollectMovesIterator moves = new CollectMovesIterator();
- int temp = 53;
- int args = 1;
- RegisterMoveScheduler scheduler = new RegisterMoveScheduler(moves, temp, args);
- scheduler.addMove(new RegisterMove(23, 15, TypeElement.getInt()));
- scheduler.addMove(new RegisterMove(26, 14, TypeElement.getInt()));
- scheduler.addMove(new RegisterMove(15, 20, TypeElement.getLong()));
- scheduler.addMove(new RegisterMove(17, 27, TypeElement.getLong()));
- scheduler.addMove(new RegisterMove(19, 4, TypeElement.getLong()));
- scheduler.addMove(new RegisterMove(21, 16, TypeElement.getLong()));
- scheduler.addMove(new RegisterMove(24, 6, TypeElement.getInt()));
- scheduler.addMove(new RegisterMove(25, 7, TypeElement.getInt()));
- scheduler.addMove(new RegisterMove(14, 8, TypeElement.getInt()));
- scheduler.addMove(new RegisterMove(30, 9, TypeElement.getInt()));
- scheduler.addMove(new RegisterMove(31, 13, TypeElement.getInt()));
- scheduler.addMove(new RegisterMove(34, 1, TypeElement.getInt()));
+ int temp = 42;
+ RegisterMoveScheduler scheduler = new RegisterMoveScheduler(moves, temp);
+ scheduler.addMove(new RegisterMove(10, 2, TypeElement.getInt()));
+ scheduler.addMove(new RegisterMove(2, 7, TypeElement.getLong()));
+ scheduler.addMove(new RegisterMove(4, 11, TypeElement.getLong()));
+ scheduler.addMove(new RegisterMove(6, 0, TypeElement.getLong()));
+ scheduler.addMove(new RegisterMove(8, 3, TypeElement.getLong()));
scheduler.addMove(
new RegisterMove(
- 27,
+ 11,
TypeElement.getInt(),
- new ConstNumber(new Value(0, TypeElement.getInt(), null), 3)));
- scheduler.addMove(
- new RegisterMove(
- 28,
- TypeElement.getInt(),
- new ConstNumber(new Value(1, TypeElement.getInt(), null), 18)));
- try {
- scheduler.schedule();
- fail();
- } catch (NoSuchElementException e) {
- // Expected.
- }
+ new ConstNumber(new Value(0, TypeElement.getInt(), null), 0)));
+ scheduler.schedule();
+ assertEquals(8, moves.size());
+ assertEquals("10 <- 2", toString(moves.get(0)));
+ assertEquals("5 <- 11", toString(moves.get(1)));
+ assertEquals("11 <- const 0", toString(moves.getConst(2)));
+ assertEquals("42 <- 7", toString(moves.get(3)));
+ assertEquals("8 <- 3", toString(moves.get(4)));
+ assertEquals("2 <- 42", toString(moves.get(5)));
+ assertEquals("4 <- 5", toString(moves.get(6)));
+ assertEquals("6 <- 0", toString(moves.get(7)));
+ assertEquals(2, scheduler.getUsedTempRegisters());
}
// Debugging aid.
@@ -633,7 +627,13 @@
System.out.println("----------------");
}
- private String toString(Instruction move) {
+ private String toString(ConstNumber move) {
+ return move.outValue().asFixedRegisterValue().getRegister()
+ + " <- const "
+ + move.asConstNumber().getRawValue();
+ }
+
+ private String toString(Move move) {
return move.outValue().asFixedRegisterValue().getRegister()
+ " <- "
+ move.getFirstOperand().asFixedRegisterValue().getRegister();
