Use destination registers as temporary registers in move scheduler
Bug: b/375147902
Change-Id: I1ba66bb9ef4fdfb821163614a54630ccd975f5cf
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 963bc1f..70d2ab8 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
@@ -11,6 +11,7 @@
import it.unimi.dsi.fastutil.ints.Int2IntMap;
import java.util.Objects;
import java.util.Set;
+import java.util.function.IntConsumer;
// Register moves used by the spilling register allocator. These are used both for spill and
// for phi moves and they are moves between actual registers represented by their register number.
@@ -36,6 +37,22 @@
this.type = type;
}
+ public void forEachDestinationRegister(IntConsumer consumer) {
+ consumer.accept(dst);
+ if (isWide()) {
+ consumer.accept(dst + 1);
+ }
+ }
+
+ public void forEachSourceRegister(IntConsumer consumer) {
+ if (src != NO_REGISTER) {
+ consumer.accept(src);
+ if (isWide()) {
+ consumer.accept(src + 1);
+ }
+ }
+ }
+
public boolean writes(int register, boolean otherIsWide) {
if (dst == register) {
return true;
@@ -49,7 +66,11 @@
return false;
}
- public boolean isBlocked(Set<RegisterMove> moveSet, Int2IntMap valueMap) {
+ public boolean isBlocked(
+ RegisterMoveScheduler scheduler, Set<RegisterMove> moveSet, Int2IntMap valueMap) {
+ if (isDestUsedAsTemporary(scheduler)) {
+ return true;
+ }
for (RegisterMove move : moveSet) {
if (isIdentical(move) || move.src == NO_REGISTER) {
continue;
@@ -61,10 +82,19 @@
return false;
}
+ public boolean isDestUsedAsTemporary(RegisterMoveScheduler scheduler) {
+ return scheduler.activeTempRegisters.contains(dst)
+ || (isWide() && scheduler.activeTempRegisters.contains(dst + 1));
+ }
+
public boolean isIdentical(RegisterMove move) {
return ObjectUtils.identical(this, move);
}
+ public boolean isNotIdentical(RegisterMove move) {
+ return !isIdentical(move);
+ }
+
public boolean isWide() {
return type.isWidePrimitive();
}
@@ -113,4 +143,16 @@
}
return definition.getNumber() - o.definition.getNumber();
}
+
+ @Override
+ public String toString() {
+ if (type.isSinglePrimitive()) {
+ return "move " + dst + ", " + src;
+ } else if (type.isWidePrimitive()) {
+ return "move-wide " + dst + ", " + src;
+ } else {
+ assert type.isReferenceType();
+ return "move-object " + dst + ", " + src;
+ }
+ }
}
diff --git a/src/main/java/com/android/tools/r8/ir/regalloc/RegisterMoveCycle.java b/src/main/java/com/android/tools/r8/ir/regalloc/RegisterMoveCycle.java
new file mode 100644
index 0000000..a1e986d
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/regalloc/RegisterMoveCycle.java
@@ -0,0 +1,28 @@
+// Copyright (c) 2024, 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 java.util.TreeSet;
+
+class RegisterMoveCycle {
+
+ private final TreeSet<RegisterMove> moves;
+
+ // Whether the cycle is closed, i.e., the moves in the cycle are only blocked by moves also
+ // present in this cycle.
+ private final boolean closed;
+
+ RegisterMoveCycle(TreeSet<RegisterMove> cycle, boolean closed) {
+ this.moves = cycle;
+ this.closed = closed;
+ }
+
+ public TreeSet<RegisterMove> getMoves() {
+ return moves;
+ }
+
+ public boolean isClosed() {
+ return closed;
+ }
+}
diff --git a/src/main/java/com/android/tools/r8/ir/regalloc/RegisterMoveCycleDetector.java b/src/main/java/com/android/tools/r8/ir/regalloc/RegisterMoveCycleDetector.java
new file mode 100644
index 0000000..cdb321d
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/regalloc/RegisterMoveCycleDetector.java
@@ -0,0 +1,141 @@
+// Copyright (c) 2024, 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.utils.SetUtils;
+import it.unimi.dsi.fastutil.ints.Int2ObjectMap;
+import it.unimi.dsi.fastutil.ints.Int2ObjectOpenHashMap;
+import java.util.ArrayDeque;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.Deque;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Set;
+import java.util.TreeSet;
+
+public class RegisterMoveCycleDetector {
+
+ @SuppressWarnings("MixedMutabilityReturnType")
+ static List<RegisterMoveCycle> getMoveCycles(TreeSet<RegisterMove> moveSet) {
+ // Although there can be a cycle when there are two moves, we return no cycles, since the
+ // default move scheduling has the same behavior as the cycle-based move scheduling in this
+ // case.
+ if (moveSet.size() <= 2) {
+ return Collections.emptyList();
+ }
+ List<RegisterMoveCycle> moveCycles = new ArrayList<>();
+ Int2ObjectMap<TreeSet<RegisterMove>> readBy = createReadByGraph(moveSet);
+ Set<RegisterMove> finished = new HashSet<>();
+ Deque<RegisterMove> stack = new ArrayDeque<>();
+ TreeSet<RegisterMove> stackSet = new TreeSet<>();
+ for (RegisterMove move : moveSet) {
+ if (finished.contains(move)) {
+ continue;
+ }
+ dfs(move, finished, readBy, stack, stackSet, moveCycles);
+ assert finished.contains(move);
+ assert stack.isEmpty();
+ assert stackSet.isEmpty();
+ }
+ return moveCycles;
+ }
+
+ private static void dfs(
+ RegisterMove move,
+ Set<RegisterMove> finished,
+ Int2ObjectMap<TreeSet<RegisterMove>> readBy,
+ Deque<RegisterMove> stack,
+ TreeSet<RegisterMove> stackSet,
+ List<RegisterMoveCycle> moveCycles) {
+ stack.addLast(move);
+ boolean addedToStack = stackSet.add(move);
+ assert addedToStack;
+ // Explore all outgoing edges. The successors of this move are the moves that read the
+ // destination registers of the current move.
+ for (RegisterMove successor : getSuccessors(move, readBy)) {
+ if (finished.contains(successor)) {
+ // Already fully explored.
+ continue;
+ }
+ if (successor.isIdentical(move)) {
+ // This move is reading/writing overlapping registers (e.g., move-wide 0, 1).
+ continue;
+ }
+ if (stackSet.contains(successor)) {
+ moveCycles.add(extractCycle(stack, successor, readBy));
+ } else {
+ dfs(successor, finished, readBy, stack, stackSet, moveCycles);
+ }
+ }
+ RegisterMove removedFromStack = stack.removeLast();
+ assert removedFromStack.isIdentical(move);
+ boolean removedFromStackSet = stackSet.remove(move);
+ assert removedFromStackSet;
+ boolean markedFinished = finished.add(move);
+ assert markedFinished;
+ }
+
+ // Returns a one-to-many map from registers to the set of moves that read that register.
+ private static Int2ObjectMap<TreeSet<RegisterMove>> createReadByGraph(
+ TreeSet<RegisterMove> moveSet) {
+ Int2ObjectMap<TreeSet<RegisterMove>> readBy = new Int2ObjectOpenHashMap<>();
+ for (RegisterMove move : moveSet) {
+ move.forEachSourceRegister(
+ register -> {
+ if (readBy.containsKey(register)) {
+ readBy.get(register).add(move);
+ } else {
+ readBy.put(register, SetUtils.newTreeSet(move));
+ }
+ });
+ }
+ return readBy;
+ }
+
+ private static Set<RegisterMove> getSuccessors(
+ RegisterMove move, Int2ObjectMap<TreeSet<RegisterMove>> readBy) {
+ TreeSet<RegisterMove> successors = readBy.get(move.dst);
+ if (move.isWide()) {
+ TreeSet<RegisterMove> additionalSuccessors = readBy.get(move.dst + 1);
+ if (successors == null) {
+ successors = additionalSuccessors;
+ } else if (additionalSuccessors != null) {
+ successors = new TreeSet<>(successors);
+ successors.addAll(additionalSuccessors);
+ }
+ }
+ return successors != null ? successors : Collections.emptySet();
+ }
+
+ private static RegisterMoveCycle extractCycle(
+ Deque<RegisterMove> stack,
+ RegisterMove cycleEntry,
+ Int2ObjectMap<TreeSet<RegisterMove>> readBy) {
+ Deque<RegisterMove> cycle = new ArrayDeque<>();
+ while (!cycleEntry.isIdentical(cycle.peekFirst())) {
+ cycle.addFirst(stack.removeLast());
+ }
+ stack.addAll(cycle);
+ TreeSet<RegisterMove> cycleSet = new TreeSet<>(cycle);
+ return new RegisterMoveCycle(cycleSet, isClosedCycle(cycleSet, readBy));
+ }
+
+ private static boolean isClosedCycle(
+ TreeSet<RegisterMove> cycle, Int2ObjectMap<TreeSet<RegisterMove>> readBy) {
+ for (RegisterMove move : cycle) {
+ for (int i = 0; i < move.type.requiredRegisters(); i++) {
+ TreeSet<RegisterMove> successors = readBy.get(move.dst + i);
+ if (successors != null) {
+ for (RegisterMove successor : successors) {
+ if (!cycle.contains(successor)) {
+ return false;
+ }
+ }
+ }
+ }
+ }
+ return true;
+ }
+}
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 242f2dc..43c2ed3 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
@@ -4,6 +4,8 @@
package com.android.tools.r8.ir.regalloc;
import static com.android.tools.r8.ir.regalloc.LiveIntervals.NO_REGISTER;
+import static com.android.tools.r8.utils.IntConsumerUtils.emptyIntConsumer;
+import static com.google.common.base.Predicates.not;
import com.android.tools.r8.errors.Unreachable;
import com.android.tools.r8.ir.analysis.type.TypeElement;
@@ -16,6 +18,8 @@
import com.android.tools.r8.ir.code.Move;
import com.android.tools.r8.ir.code.Position;
import com.android.tools.r8.ir.code.Value;
+import com.android.tools.r8.utils.ObjectUtils;
+import com.google.common.collect.Iterables;
import it.unimi.dsi.fastutil.ints.Int2IntMap;
import it.unimi.dsi.fastutil.ints.Int2IntOpenHashMap;
import it.unimi.dsi.fastutil.ints.IntArraySet;
@@ -26,14 +30,13 @@
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
-import java.util.Iterator;
import java.util.List;
-import java.util.Set;
import java.util.TreeSet;
+import java.util.function.IntConsumer;
public class RegisterMoveScheduler {
// The set of moves to schedule.
- private final Set<RegisterMove> moveSet = new TreeSet<>();
+ 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();
@@ -44,8 +47,15 @@
// The first available temporary register.
private final int firstTempRegister;
private int nextTempRegister;
- // Free registers.
+ // Free temporary registers that have been allocated by move scheduling.
private final IntSortedSet freeRegisters = new IntRBTreeSet();
+ // Registers that can be used as temporary registers until they are assigned by a move in the
+ // move set.
+ private final IntSortedSet freeRegistersUntilAssigned = new IntRBTreeSet();
+ // 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();
public RegisterMoveScheduler(
InstructionListIterator insertAt, int firstTempRegister, Position position) {
@@ -60,6 +70,19 @@
this(insertAt, firstTempRegister, Position.none());
}
+ private void initializeFreeRegistersUntilAssigned() {
+ // All registers that are assigned by the move set but not read can be used as temporary
+ // registers until they are assigned.
+ assert activeTempRegisters.isEmpty();
+ assert freeRegistersUntilAssigned.isEmpty();
+ for (RegisterMove move : moveSet) {
+ move.forEachDestinationRegister(freeRegistersUntilAssigned::add);
+ }
+ for (RegisterMove move : moveSet) {
+ move.forEachSourceRegister(freeRegistersUntilAssigned::remove);
+ }
+ }
+
public void addMove(RegisterMove move) {
moveSet.add(move);
if (move.src != NO_REGISTER) {
@@ -70,53 +93,58 @@
public void schedule() {
assert everyDestinationOnlyWrittenOnce();
+ initializeFreeRegistersUntilAssigned();
// Worklist of moves that are ready to be inserted.
Deque<RegisterMove> worklist = new ArrayDeque<>();
- // Initialize worklist with the moves that do not interfere with other moves.
- Iterator<RegisterMove> iterator = moveSet.iterator();
- while (iterator.hasNext()) {
- RegisterMove move = iterator.next();
- if (!move.isBlocked(moveSet, valueMap)) {
- worklist.addLast(move);
- iterator.remove();
+ // If there are destination registers we can use until they are assigned, then instead of
+ // emitting these unblocked moves, we use them as temporary registers to unblock move cycles.
+ List<RegisterMoveCycle> moveCycles = RegisterMoveCycleDetector.getMoveCycles(moveSet);
+ for (RegisterMoveCycle moveCycle : moveCycles) {
+ for (RegisterMove move : moveCycle.getMoves()) {
+ assert move.isBlocked(this, moveSet, valueMap) || !moveSet.contains(move);
+ removeFromFreeRegistersUntilAssigned(move.dst, move.isWide(), emptyIntConsumer());
}
+ // If the cycle is not closed then some moves in the cycle are blocked by other moves.
+ // TODO(b/375147902): Try to schedule these other moves before scheduling the cycle to
+ // unblock the cycle. In JetNews 15% of move cycles are open.
+ if (moveCycle.isClosed()) {
+ assert moveSet.containsAll(moveCycle.getMoves());
+ assert worklist.isEmpty();
+ schedulePartial(moveCycle.getMoves(), worklist);
+ }
+ assert activeTempRegisters.isEmpty();
}
+ // Initialize worklist with the moves that do not interfere with other moves.
+ enqueueUnblockedMoves(worklist);
+ schedulePartial(moveSet, worklist);
+ assert freeRegistersUntilAssigned.isEmpty();
+ }
+
+ private void schedulePartial(
+ TreeSet<RegisterMove> movesToSchedule, Deque<RegisterMove> worklist) {
// Process the worklist generating moves. If the worklist becomes empty while the move set
// still contains elements we need to use a temporary to break cycles.
- while (!worklist.isEmpty() || !moveSet.isEmpty()) {
+ while (!worklist.isEmpty() || !movesToSchedule.isEmpty()) {
while (!worklist.isEmpty()) {
- RegisterMove move = worklist.removeFirst();
- assert !move.isBlocked(moveSet, valueMap);
- // Insert the move.
- int generatedDest = createMove(move);
- // Update the value map with the information that dest can be used instead of
- // src starting now.
- if (move.src != NO_REGISTER) {
- valueMap.put(move.src, generatedDest);
+ while (!worklist.isEmpty()) {
+ RegisterMove move = worklist.removeFirst();
+ assert !move.isBlocked(this, moveSet, valueMap);
+ createMove(move);
}
- // Iterate and find the moves that were blocked because they need to write to
- // one of the move src. That is now valid because the move src is preserved in dest.
- iterator = moveSet.iterator();
- while (iterator.hasNext()) {
- RegisterMove other = iterator.next();
- if (!other.isBlocked(moveSet, valueMap)) {
- worklist.addLast(other);
- iterator.remove();
- }
- }
+ enqueueUnblockedMoves(worklist, movesToSchedule);
}
- if (!moveSet.isEmpty()) {
+ if (!movesToSchedule.isEmpty()) {
// The remaining moves are conflicting. Chose a move and unblock it by generating moves to
// temporary registers for its destination value(s).
- RegisterMove move = pickMoveToUnblock();
+ RegisterMove move = pickMoveToUnblock(movesToSchedule);
createMoveDestToTemp(move);
// TODO(b/375147902): After emitting the newly unblocked move, try to prioritize the moves
// that blocked it, so that we free up the temp register, rather than getting overlapping
// temporary registers.
- worklist.addLast(move);
+ worklist.add(move);
}
}
}
@@ -135,7 +163,7 @@
int moveSrc = valueMap.get(move.src);
if (moveSrc == src) {
result.add(move);
- } else if (move.type.isWidePrimitive() && (moveSrc + 1) == src) {
+ } else if (move.isWide() && (moveSrc + 1) == src) {
result.add(move);
} else if (type.isWidePrimitive() && (moveSrc - 1) == src) {
result.add(move);
@@ -144,7 +172,7 @@
return result;
}
- private int createMove(RegisterMove move) {
+ private void createMove(RegisterMove move) {
Instruction instruction;
if (move.definition != null) {
if (move.definition.isArgument()) {
@@ -172,7 +200,43 @@
}
instruction.setPosition(position);
insertAt.add(instruction);
- return move.dst;
+
+ // Update the value map with the information that dest can be used instead of
+ // src starting now.
+ if (move.src != NO_REGISTER) {
+ valueMap.put(move.src, move.dst);
+ }
+ removeFromFreeRegistersUntilAssigned(move.dst, move.isWide(), emptyIntConsumer());
+ }
+
+ private void enqueueUnblockedMoves(Deque<RegisterMove> worklist) {
+ // Iterate and find the moves that were blocked because they need to write to one of the move
+ // src. That is now valid because the move src is preserved in dest.
+ moveSet.removeIf(
+ move -> {
+ if (move.isBlocked(this, moveSet, valueMap)) {
+ return false;
+ }
+ worklist.addLast(move);
+ return true;
+ });
+ }
+
+ private void enqueueUnblockedMoves(
+ Deque<RegisterMove> worklist, TreeSet<RegisterMove> movesToSchedule) {
+ // Iterate and find the moves that were blocked because they need to write to one of the move
+ // src. That is now valid because the move src is preserved in dest.
+ movesToSchedule.removeIf(
+ move -> {
+ if (move.isBlocked(this, moveSet, valueMap)) {
+ return false;
+ }
+ if (ObjectUtils.notIdentical(moveSet, movesToSchedule)) {
+ moveSet.remove(move);
+ }
+ worklist.addLast(move);
+ return true;
+ });
}
private void createMoveDestToTemp(RegisterMove move) {
@@ -195,15 +259,17 @@
}
private int takeFreeRegister(boolean wide) {
- for (int freeRegister : freeRegisters) {
- if (wide && !freeRegisters.remove(freeRegister + 1)) {
- continue;
- }
- freeRegisters.remove(freeRegister);
- return freeRegister;
+ int register = takeFreeRegisterFrom(freeRegistersUntilAssigned, wide);
+ if (register != NO_REGISTER) {
+ addActiveTempRegisters(register, wide);
+ return register;
+ }
+ register = takeFreeRegisterFrom(freeRegisters, wide);
+ if (register != NO_REGISTER) {
+ return register;
}
// We don't have a free register.
- int register = allocateExtraRegister();
+ register = allocateExtraRegister();
if (!wide) {
return register;
}
@@ -214,21 +280,78 @@
return register;
}
- private void returnTemporaryRegister(int register, boolean wide) {
- // TODO(b/375147902): If we seed the move scheduler with a set of free registers, then this
- // should also return non-temporary registers that are below firstTempRegister.
- if (isTemporaryRegister(register)) {
- freeRegisters.add(register);
- if (wide) {
- assert isTemporaryRegister(register + 1);
- freeRegisters.add(register + 1);
+ private static int takeFreeRegisterFrom(IntSortedSet freeRegisters, boolean wide) {
+ for (int freeRegister : freeRegisters) {
+ if (wide && !freeRegisters.remove(freeRegister + 1)) {
+ continue;
}
- } else if (wide && isTemporaryRegister(register + 1)) {
+ freeRegisters.remove(freeRegister);
+ return freeRegister;
+ }
+ return NO_REGISTER;
+ }
+
+ private void addActiveTempRegisters(int register, boolean wide) {
+ boolean addedRegister = activeTempRegisters.add(register);
+ assert addedRegister;
+ if (wide) {
+ boolean addedHighRegister = activeTempRegisters.add(register + 1);
+ assert addedHighRegister;
+ }
+ }
+
+ private void returnTemporaryRegister(int register, boolean wide) {
+ if (returnActiveTempRegister(register, wide)) {
+ addFreeRegistersUntilAssigned(register, wide);
+ } else if (isExtraTemporaryRegister(register)) {
+ returnExtraTemporaryRegister(register, wide);
+ }
+ }
+
+ private boolean returnActiveTempRegister(int register, boolean wide) {
+ boolean removedRegister = activeTempRegisters.remove(register);
+ if (wide) {
+ if (removedRegister) {
+ boolean removedHighRegister = activeTempRegisters.remove(register + 1);
+ assert removedHighRegister;
+ } else {
+ assert !activeTempRegisters.contains(register + 1);
+ }
+ }
+ return removedRegister;
+ }
+
+ private void addFreeRegistersUntilAssigned(int register, boolean wide) {
+ boolean addedRegister = freeRegistersUntilAssigned.add(register);
+ assert addedRegister;
+ if (wide) {
+ boolean addedHighRegister = freeRegistersUntilAssigned.add(register + 1);
+ assert addedHighRegister;
+ }
+ }
+
+ private void returnExtraTemporaryRegister(int register, boolean wide) {
+ assert isExtraTemporaryRegister(register);
+ freeRegisters.add(register);
+ if (wide) {
+ assert isExtraTemporaryRegister(register + 1);
freeRegisters.add(register + 1);
}
}
- private boolean isTemporaryRegister(int register) {
+ private void removeFromFreeRegistersUntilAssigned(
+ int register, boolean wide, IntConsumer changedConsumer) {
+ if (freeRegistersUntilAssigned.remove(register)) {
+ changedConsumer.accept(register);
+ }
+ if (wide) {
+ if (freeRegistersUntilAssigned.remove(register + 1)) {
+ changedConsumer.accept(register + 1);
+ }
+ }
+ }
+
+ private boolean isExtraTemporaryRegister(int register) {
return register >= firstTempRegister;
}
@@ -244,17 +367,16 @@
return true;
}
- private RegisterMove pickMoveToUnblock() {
- Iterator<RegisterMove> iterator = moveSet.iterator();
- RegisterMove move = null;
+ private RegisterMove pickMoveToUnblock(TreeSet<RegisterMove> moves) {
// Pick a non-wide move to unblock if possible.
- while (iterator.hasNext()) {
- move = iterator.next();
- if (!move.type.isWidePrimitive()) {
- break;
- }
+ Iterable<RegisterMove> eligible =
+ Iterables.filter(moves, move -> !move.isDestUsedAsTemporary(this));
+ RegisterMove move =
+ Iterables.find(eligible, not(RegisterMove::isWide), eligible.iterator().next());
+ moves.remove(move);
+ if (ObjectUtils.notIdentical(moves, moveSet)) {
+ moveSet.remove(move);
}
- iterator.remove();
return move;
}
diff --git a/src/main/java/com/android/tools/r8/utils/SetUtils.java b/src/main/java/com/android/tools/r8/utils/SetUtils.java
index ea46d64..7ec47cb 100644
--- a/src/main/java/com/android/tools/r8/utils/SetUtils.java
+++ b/src/main/java/com/android/tools/r8/utils/SetUtils.java
@@ -13,6 +13,7 @@
import java.util.IdentityHashMap;
import java.util.LinkedHashSet;
import java.util.Set;
+import java.util.TreeSet;
import java.util.concurrent.ConcurrentHashMap;
import java.util.function.Function;
@@ -118,6 +119,12 @@
return builder.build();
}
+ public static <T extends Comparable<T>> TreeSet<T> newTreeSet(T element) {
+ TreeSet<T> result = new TreeSet<>();
+ result.add(element);
+ return result;
+ }
+
public static <T, S> Set<T> mapIdentityHashSet(Collection<S> set, Function<S, T> fn) {
Set<T> out = newIdentityHashSet(set.size());
for (S element : set) {
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 ae83eee..804b482 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
@@ -388,18 +388,10 @@
scheduler.addMove(new RegisterMove(0, 3, TypeElement.getLong()));
scheduler.schedule();
assertEquals(3, moves.size());
- Move firstMove = moves.get(0).asMove();
- Move secondMove = moves.get(1).asMove();
- Move thirdMove = moves.get(2).asMove();
- assertEquals(ValueType.LONG, firstMove.outType());
- assertEquals(ValueType.LONG, secondMove.outType());
- assertEquals(ValueType.LONG, thirdMove.outType());
- assertEquals(42, firstMove.dest().asFixedRegisterValue().getRegister());
- assertEquals(1, firstMove.src().asFixedRegisterValue().getRegister());
- assertEquals(0, secondMove.dest().asFixedRegisterValue().getRegister());
- assertEquals(3, secondMove.src().asFixedRegisterValue().getRegister());
- assertEquals(2, thirdMove.dest().asFixedRegisterValue().getRegister());
- assertEquals(42, thirdMove.src().asFixedRegisterValue().getRegister());
+ assertEquals("42 <- 3", toString(moves.get(0)));
+ assertEquals("2 <- 1", toString(moves.get(1)));
+ assertEquals("0 <- 42", toString(moves.get(2)));
+ assertEquals(2, scheduler.getUsedTempRegisters());
}
@Test
@@ -460,12 +452,13 @@
scheduler.addMove(new RegisterMove(12, 19, TypeElement.getLong()));
scheduler.schedule();
// In order to resolve these moves, we need to use two temporary register pairs.
- assertEquals(6, moves.size());
- assertEquals(42, moves.get(0).asMove().dest().asFixedRegisterValue().getRegister());
- assertEquals(11, moves.get(0).asMove().src().asFixedRegisterValue().getRegister());
- assertEquals(44, moves.get(1).asMove().dest().asFixedRegisterValue().getRegister());
- assertEquals(13, moves.get(1).asMove().src().asFixedRegisterValue().getRegister());
- assertEquals(12, moves.get(2).asMove().dest().asFixedRegisterValue().getRegister());
+ assertEquals(5, moves.size());
+ assertEquals("42 <- 13", toString(moves.get(0)));
+ assertEquals("14 <- 11", toString(moves.get(1)));
+ assertEquals("10 <- 17", toString(moves.get(2)));
+ assertEquals("16 <- 42", toString(moves.get(3)));
+ assertEquals("12 <- 19", toString(moves.get(4)));
+ assertEquals(2, scheduler.getUsedTempRegisters());
}
@Test
@@ -487,19 +480,13 @@
scheduler.addMove(new RegisterMove(23, 28, TypeElement.getLong()));
scheduler.schedule();
// For this example we need recursive unblocking.
- assertEquals(6, moves.size());
- assertEquals(42, moves.get(0).asMove().dest().asFixedRegisterValue().getRegister());
- assertEquals(26, moves.get(0).asMove().src().asFixedRegisterValue().getRegister());
- assertEquals(26, moves.get(1).asMove().dest().asFixedRegisterValue().getRegister());
- assertEquals(22, moves.get(1).asMove().src().asFixedRegisterValue().getRegister());
- assertEquals(43, moves.get(2).asMove().dest().asFixedRegisterValue().getRegister());
- assertEquals(28, moves.get(2).asMove().src().asFixedRegisterValue().getRegister());
- assertEquals(28, moves.get(3).asMove().dest().asFixedRegisterValue().getRegister());
- assertEquals(42, moves.get(3).asMove().src().asFixedRegisterValue().getRegister());
- assertEquals(29, moves.get(4).asMove().dest().asFixedRegisterValue().getRegister());
- assertEquals(24, moves.get(4).asMove().src().asFixedRegisterValue().getRegister());
- assertEquals(23, moves.get(5).asMove().dest().asFixedRegisterValue().getRegister());
- assertEquals(43, moves.get(5).asMove().src().asFixedRegisterValue().getRegister());
+ assertEquals(5, moves.size());
+ assertEquals("42 <- 28", toString(moves.get(0)));
+ assertEquals("29 <- 24", toString(moves.get(1)));
+ assertEquals("23 <- 42", toString(moves.get(2)));
+ assertEquals("28 <- 26", toString(moves.get(3)));
+ assertEquals("26 <- 22", toString(moves.get(4)));
+ assertEquals(2, scheduler.getUsedTempRegisters());
}
@Test
@@ -522,6 +509,41 @@
assertEquals(1, scheduler.getUsedTempRegisters());
}
+ @Test
+ public void useDestinationRegisterAsTemporary() {
+ CollectMovesIterator moves = new CollectMovesIterator();
+ int temp = 42;
+ RegisterMoveScheduler scheduler = new RegisterMoveScheduler(moves, temp);
+ scheduler.addMove(new RegisterMove(0, 1, TypeElement.getInt()));
+ scheduler.addMove(new RegisterMove(1, 0, TypeElement.getInt()));
+ scheduler.addMove(new RegisterMove(2, 3, TypeElement.getInt()));
+ scheduler.schedule();
+ // Verify that the temp register has been reused.
+ assertEquals("2 <- 1", toString(moves.get(0)));
+ assertEquals("1 <- 0", toString(moves.get(1)));
+ assertEquals("0 <- 2", toString(moves.get(2)));
+ assertEquals("2 <- 3", toString(moves.get(3)));
+ assertEquals(0, scheduler.getUsedTempRegisters());
+ }
+
+ @Test
+ public void openMoveCycle() {
+ CollectMovesIterator moves = new CollectMovesIterator();
+ int temp = 42;
+ RegisterMoveScheduler scheduler = new RegisterMoveScheduler(moves, temp);
+ scheduler.addMove(new RegisterMove(2, 0, TypeElement.getInt()));
+ scheduler.addMove(new RegisterMove(0, 2, TypeElement.getLong()));
+ scheduler.addMove(new RegisterMove(4, 1, TypeElement.getInt()));
+ scheduler.schedule();
+ // The cycle is blocked by the move 4 <- 1, so we should emit this move first.
+ assertEquals(4, moves.size());
+ assertEquals("4 <- 1", toString(moves.get(0)));
+ assertEquals("42 <- 2", toString(moves.get(1)));
+ assertEquals("2 <- 0", toString(moves.get(2)));
+ assertEquals("0 <- 42", toString(moves.get(3)));
+ assertEquals(2, scheduler.getUsedTempRegisters());
+ }
+
// Debugging aid.
private void printMoves(List<Instruction> moves) {
System.out.println("Generated moves:");
