Minor cleanup of move scheduler
Bug: b/374702812
Change-Id: Id84958fe0b4c14030f4a6a42b14d5acbf75dab7e
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 be68587..963bc1f 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
@@ -3,9 +3,13 @@
// BSD-style license that can be found in the LICENSE file.
package com.android.tools.r8.ir.regalloc;
+import static com.android.tools.r8.ir.regalloc.LiveIntervals.NO_REGISTER;
+
import com.android.tools.r8.ir.analysis.type.TypeElement;
import com.android.tools.r8.ir.code.Instruction;
-import java.util.Map;
+import com.android.tools.r8.utils.ObjectUtils;
+import it.unimi.dsi.fastutil.ints.Int2IntMap;
+import java.util.Objects;
import java.util.Set;
// Register moves used by the spilling register allocator. These are used both for spill and
@@ -27,51 +31,56 @@
public RegisterMove(int dst, TypeElement type, Instruction definition) {
assert definition.isOutConstant();
this.dst = dst;
- this.src = LiveIntervals.NO_REGISTER;
+ this.src = NO_REGISTER;
this.definition = definition;
this.type = type;
}
- private boolean writes(int register) {
- if (type.isWidePrimitive() && (dst + 1) == register) {
+ public boolean writes(int register, boolean otherIsWide) {
+ if (dst == register) {
return true;
}
- return dst == register;
+ if (isWide() && dst + 1 == register) {
+ return true;
+ }
+ if (otherIsWide && dst == register + 1) {
+ return true;
+ }
+ return false;
}
- @SuppressWarnings("ReferenceEquality")
- public boolean isBlocked(Set<RegisterMove> moveSet, Map<Integer, Integer> valueMap) {
+ public boolean isBlocked(Set<RegisterMove> moveSet, Int2IntMap valueMap) {
for (RegisterMove move : moveSet) {
- if (move.src == LiveIntervals.NO_REGISTER) {
+ if (isIdentical(move) || move.src == NO_REGISTER) {
continue;
}
- if (move != this) {
- if (writes(valueMap.get(move.src))) {
- return true;
- }
- if (move.type.isWidePrimitive()) {
- if (writes(valueMap.get(move.src) + 1)) {
- return true;
- }
- }
+ if (writes(valueMap.get(move.src), move.isWide())) {
+ return true;
}
}
return false;
}
- @Override
- public int hashCode() {
- return src + dst * 3 + type.hashCode() * 5 + (definition == null ? 0 : definition.hashCode());
+ public boolean isIdentical(RegisterMove move) {
+ return ObjectUtils.identical(this, move);
+ }
+
+ public boolean isWide() {
+ return type.isWidePrimitive();
}
@Override
- @SuppressWarnings("ReferenceEquality")
+ public int hashCode() {
+ return src + dst * 3 + type.hashCode() * 5 + Objects.hashCode(definition);
+ }
+
+ @Override
public boolean equals(Object other) {
if (!(other instanceof RegisterMove)) {
return false;
}
RegisterMove o = (RegisterMove) other;
- return o.src == src && o.dst == dst && o.type == type && o.definition == definition;
+ return o.src == src && o.dst == dst && type.equals(o.type) && o.definition == definition;
}
@Override
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 5251d17..4c60ed6 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
@@ -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.ir.regalloc.LiveIntervals.NO_REGISTER;
+
import com.android.tools.r8.errors.Unreachable;
import com.android.tools.r8.ir.analysis.type.TypeElement;
import com.android.tools.r8.ir.code.Argument;
@@ -14,15 +16,15 @@
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 it.unimi.dsi.fastutil.ints.Int2IntMap;
+import it.unimi.dsi.fastutil.ints.Int2IntOpenHashMap;
import it.unimi.dsi.fastutil.ints.IntArraySet;
import it.unimi.dsi.fastutil.ints.IntSet;
+import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
-import java.util.HashMap;
import java.util.Iterator;
-import java.util.LinkedList;
import java.util.List;
-import java.util.Map;
import java.util.Set;
import java.util.TreeSet;
@@ -31,7 +33,7 @@
private final Set<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 Map<Integer, Integer> valueMap = new HashMap<>();
+ private final Int2IntMap valueMap = new Int2IntOpenHashMap();
// Number of temp registers used to schedule the moves.
private int usedTempRegisters = 0;
// Location at which to insert the scheduled moves.
@@ -46,6 +48,7 @@
this.insertAt = insertAt;
this.tempRegister = tempRegister;
this.position = position;
+ this.valueMap.defaultReturnValue(NO_REGISTER);
}
public RegisterMoveScheduler(InstructionListIterator insertAt, int tempRegister) {
@@ -54,19 +57,17 @@
public void addMove(RegisterMove move) {
moveSet.add(move);
- if (move.src != LiveIntervals.NO_REGISTER) {
+ if (move.src != NO_REGISTER) {
valueMap.put(move.src, move.src);
}
valueMap.put(move.dst, move.dst);
}
- // TODO(b/270398965): Replace LinkedList.
- @SuppressWarnings("JdkObsolete")
public void schedule() {
assert everyDestinationOnlyWrittenOnce();
// Worklist of moves that are ready to be inserted.
- Deque<RegisterMove> worklist = new LinkedList<>();
+ Deque<RegisterMove> worklist = new ArrayDeque<>();
// Initialize worklist with the moves that do not interfere with other moves.
Iterator<RegisterMove> iterator = moveSet.iterator();
@@ -85,10 +86,10 @@
RegisterMove move = worklist.removeFirst();
assert !move.isBlocked(moveSet, valueMap);
// Insert the move.
- Integer generatedDest = createMove(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 != LiveIntervals.NO_REGISTER) {
+ if (move.src != NO_REGISTER) {
valueMap.put(move.src, generatedDest);
}
// Iterate and find the moves that were blocked because they need to write to
@@ -107,6 +108,9 @@
// temporary registers for its destination value(s).
RegisterMove move = pickMoveToUnblock();
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);
}
}
@@ -118,9 +122,9 @@
private List<RegisterMove> findMovesWithSrc(int src, TypeElement type) {
List<RegisterMove> result = new ArrayList<>();
- assert src != LiveIntervals.NO_REGISTER;
+ assert src != NO_REGISTER;
for (RegisterMove move : moveSet) {
- if (move.src == LiveIntervals.NO_REGISTER) {
+ if (move.src == NO_REGISTER) {
continue;
}
int moveSrc = valueMap.get(move.src);
@@ -135,7 +139,7 @@
return result;
}
- private Integer createMove(RegisterMove move) {
+ private int createMove(RegisterMove move) {
Instruction instruction;
if (move.definition != null) {
if (move.definition.isArgument()) {
@@ -171,18 +175,19 @@
List<RegisterMove> movesWithSrc = findMovesWithSrc(move.dst, move.type);
assert movesWithSrc.size() > 0;
for (RegisterMove moveWithSrc : movesWithSrc) {
- // TODO(ager): For now we always use a new temporary register whenever we have to unblock
- // a move. The move scheduler can have multiple unblocking temps live at the same time
- // and therefore we cannot have just one tempRegister (pair). However, we could check here
- // if the previously used tempRegisters is still needed by any of the moves in the move set
- // (taking the value map into account). If not, we can reuse the temp register instead
- // of generating a new one.
- Value to = new FixedRegisterValue(moveWithSrc.type, tempRegister + usedTempRegisters);
+ // TODO(b/375147902): For now we always use a new temporary register whenever we have to
+ // unblock a move. The move scheduler can have multiple unblocking temps live at the same
+ // time and therefore we cannot have just one tempRegister (pair). However, we could check
+ // here if the previously used tempRegisters is still needed by any of the moves in the move
+ // set (taking the value map into account). If not, we can reuse the temp register instead
+ // of generating a new one.
+ int register = tempRegister + usedTempRegisters;
+ Value to = new FixedRegisterValue(moveWithSrc.type, register);
Value from = new FixedRegisterValue(moveWithSrc.type, valueMap.get(moveWithSrc.src));
Move instruction = new Move(to, from);
instruction.setPosition(position);
insertAt.add(instruction);
- valueMap.put(moveWithSrc.src, tempRegister + usedTempRegisters);
+ valueMap.put(moveWithSrc.src, register);
usedTempRegisters += moveWithSrc.type.requiredRegisters();
}
}
