Update insertion of argument moves
This CL changes the way we insert moves for invoke-range instructions with at least 17 argument registers. With this change, the move for an argument of an invoke-range instruction will be inserted immediately after its definition (if the argument is defined in the same block as the invoke), rather than right before the invoke-range instruction.
With the current implementation, there is a high risk that we will need to spill the arguments before they get moved to the correct register right before the invoke.
Change-Id: I1db77d50b3d2bff909ea2a31283a047e74d21ec5
diff --git a/src/main/java/com/android/tools/r8/ir/code/BasicBlock.java b/src/main/java/com/android/tools/r8/ir/code/BasicBlock.java
index 241e9ef..24e6eb5 100644
--- a/src/main/java/com/android/tools/r8/ir/code/BasicBlock.java
+++ b/src/main/java/com/android/tools/r8/ir/code/BasicBlock.java
@@ -3,6 +3,8 @@
// BSD-style license that can be found in the LICENSE file.
package com.android.tools.r8.ir.code;
+import static com.android.tools.r8.ir.code.IRCode.INSTRUCTION_NUMBER_DELTA;
+
import com.android.tools.r8.errors.CompilationError;
import com.android.tools.r8.errors.Unreachable;
import com.android.tools.r8.graph.DebugLocalInfo;
@@ -409,6 +411,14 @@
this.number = number;
}
+ public int numberInstructions(int nextInstructionNumber) {
+ for (Instruction instruction : instructions) {
+ instruction.setNumber(nextInstructionNumber);
+ nextInstructionNumber += INSTRUCTION_NUMBER_DELTA;
+ }
+ return nextInstructionNumber;
+ }
+
public LinkedList<Instruction> getInstructions() {
return instructions;
}
diff --git a/src/main/java/com/android/tools/r8/ir/code/IRCode.java b/src/main/java/com/android/tools/r8/ir/code/IRCode.java
index d437da3..beaa62b 100644
--- a/src/main/java/com/android/tools/r8/ir/code/IRCode.java
+++ b/src/main/java/com/android/tools/r8/ir/code/IRCode.java
@@ -556,10 +556,7 @@
public ImmutableList<BasicBlock> numberInstructions() {
ImmutableList<BasicBlock> blocks = topologicallySortedBlocks();
for (BasicBlock block : blocks) {
- for (Instruction instruction : block.getInstructions()) {
- instruction.setNumber(nextInstructionNumber);
- nextInstructionNumber += INSTRUCTION_NUMBER_DELTA;
- }
+ nextInstructionNumber = block.numberInstructions(nextInstructionNumber);
}
return blocks;
}
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 aca1f85..f0f5b36 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
@@ -2351,6 +2351,23 @@
if (invoke.requiredArgumentRegisters() > 5 && !argumentsAreAlreadyLinked(invoke)) {
List<Value> arguments = invoke.arguments();
Value previous = null;
+
+ PriorityQueue<Move> insertAtDefinition = null;
+ if (invoke.requiredArgumentRegisters() > 16) {
+ insertAtDefinition =
+ new PriorityQueue<>(
+ (x, y) -> x.src().definition.getNumber() - y.src().definition.getNumber());
+
+ // Number the instructions in this basic block such that we can order the moves according
+ // to the positions of the instructions that define the srcs of the moves. Note that this
+ // is a local numbering of the instructions. These instruction numbers will be recomputed
+ // just before the liveness analysis.
+ BasicBlock block = invoke.getBlock();
+ if (block.entry().getNumber() == -1) {
+ block.numberInstructions(0);
+ }
+ }
+
for (int i = 0; i < arguments.size(); i++) {
Value argument = arguments.get(i);
Value newArgument = argument;
@@ -2371,15 +2388,65 @@
newArgument = createValue(argument.outType());
Move move = new Move(newArgument, argument);
move.setBlock(invoke.getBlock());
- move.setPosition(invoke.getPosition());
replaceArgument(invoke, i, newArgument);
- insertAt.add(move);
+
+ boolean argumentIsDefinedInSameBlock =
+ argument.definition != null && argument.definition.getBlock() == invoke.getBlock();
+ if (invoke.requiredArgumentRegisters() > 16 && argumentIsDefinedInSameBlock) {
+ // Heuristic: Insert the move immediately after the argument. This increases the
+ // likelyhood that we will be able to move the argument directly into the register it
+ // needs to be in for the ranged invoke.
+ //
+ // If we instead were to insert the moves immediately before the ranged invoke when
+ // there are many arguments, then there is a high risk that we will need to spill the
+ // arguments before they get moved to the correct register right before the invoke.
+ assert move.src().definition.getNumber() >= 0;
+ insertAtDefinition.add(move);
+ move.setPosition(argument.definition.getPosition());
+ } else {
+ insertAt.add(move);
+ move.setPosition(invoke.getPosition());
+ }
}
if (previous != null) {
previous.linkTo(newArgument);
}
previous = newArgument;
}
+
+ if (insertAtDefinition != null && !insertAtDefinition.isEmpty()) {
+ generateArgumentMovesAtDefinitions(invoke, insertAtDefinition, insertAt);
+ }
+ }
+ }
+
+ private void generateArgumentMovesAtDefinitions(
+ Invoke invoke, PriorityQueue<Move> insertAtDefinition, InstructionListIterator insertAt) {
+ Move move = insertAtDefinition.poll();
+ // Rewind instruction iterator to the position where the first move needs to be inserted.
+ Instruction previousDefinition = move.src().definition;
+ while (insertAt.peekPrevious() != previousDefinition) {
+ insertAt.previous();
+ }
+ // Insert the instructions one by one after their definition.
+ insertAt.add(move);
+ while (!insertAtDefinition.isEmpty()) {
+ move = insertAtDefinition.poll();
+ Instruction currentDefinition = move.src().definition;
+ assert currentDefinition.getNumber() >= previousDefinition.getNumber();
+ if (currentDefinition.getNumber() > previousDefinition.getNumber()) {
+ // Move the instruction iterator forward to where this move needs to be inserted.
+ while (insertAt.peekPrevious() != currentDefinition) {
+ insertAt.next();
+ }
+ }
+ insertAt.add(move);
+ // Update state.
+ previousDefinition = currentDefinition;
+ }
+ // Move the instruction iterator forward to its old position.
+ while (insertAt.peekNext() != invoke) {
+ insertAt.next();
}
}
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 8724d43..d52b84a 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
@@ -26,7 +26,7 @@
this.dst = dst;
this.src = LiveIntervals.NO_REGISTER;
this.type = type;
- assert definition.isConstInstruction() || definition.isArgument();
+ assert definition.isOutConstant() || definition.isArgument();
this.definition = definition;
}
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 afec916..b1e5e4f 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
@@ -6,6 +6,7 @@
import com.android.tools.r8.code.MoveType;
import com.android.tools.r8.errors.Unreachable;
import com.android.tools.r8.ir.code.Argument;
+import com.android.tools.r8.ir.code.ConstInstruction;
import com.android.tools.r8.ir.code.ConstNumber;
import com.android.tools.r8.ir.code.ConstString;
import com.android.tools.r8.ir.code.FixedRegisterValue;
@@ -132,15 +133,16 @@
private Integer createMove(RegisterMove move) {
Instruction instruction;
if (move.definition != null) {
- Instruction definition = move.definition;
- if (definition.isArgument()) {
- Argument argument = definition.asArgument();
+ if (move.definition.isArgument()) {
+ Argument argument = move.definition.asArgument();
int argumentRegister = argument.outValue().getLiveIntervals().getRegister();
Value to = new FixedRegisterValue(argument.outType(), move.dst);
Value from = new FixedRegisterValue(argument.outType(), argumentRegister);
instruction = new Move(to, from);
} else {
- Value to = new FixedRegisterValue(definition.outType(), move.dst);
+ assert move.definition.isOutConstant();
+ Value to = new FixedRegisterValue(move.definition.outType(), move.dst);
+ ConstInstruction definition = move.definition.getOutConstantConstInstruction();
if (definition.isConstNumber()) {
instruction = new ConstNumber(to, definition.asConstNumber().getRawValue());
} else if (definition.isConstString()) {
