Delete dead code in register allocator
This also removes the previous/next consecutive pointers from Value.
Change-Id: Ie0e3a77e21c83250058e0914731ad742e3dc203d
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 631034e..25c51c9 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
@@ -1156,7 +1156,7 @@
}
public Iterator<Argument> argumentIterator() {
- return new Iterator<Argument>() {
+ return new Iterator<>() {
private final InstructionIterator instructionIterator = entryBlock().iterator();
private Argument next = instructionIterator.next().asArgument();
@@ -1178,6 +1178,10 @@
};
}
+ public Iterable<Argument> arguments() {
+ return () -> argumentIterator();
+ }
+
public List<Value> collectArguments() {
return collectArguments(false);
}
diff --git a/src/main/java/com/android/tools/r8/ir/code/Invoke.java b/src/main/java/com/android/tools/r8/ir/code/Invoke.java
index b4dc0ec..b284aa5 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Invoke.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Invoke.java
@@ -241,13 +241,13 @@
if (arguments().isEmpty()) {
return false;
}
- Value current = getFirstArgument();
- if (!current.isArgument()) {
+ Argument current = getFirstArgument().getDefinitionOrNull(Instruction::isArgument);
+ if (current == null) {
return false;
}
for (int i = 1; i < arguments().size(); i++) {
- Value next = getArgument(i);
- if (current.getNextConsecutive() != next) {
+ Argument next = getArgument(i).getDefinitionOrNull(Instruction::isArgument);
+ if (current.getNext() != next) {
return false;
}
current = next;
diff --git a/src/main/java/com/android/tools/r8/ir/code/Value.java b/src/main/java/com/android/tools/r8/ir/code/Value.java
index b140e11..d782e2b 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Value.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Value.java
@@ -12,7 +12,6 @@
import static com.android.tools.r8.ir.code.Opcodes.DEX_ITEM_BASED_CONST_STRING;
import static com.android.tools.r8.ir.code.Opcodes.INSTANCE_OF;
-import com.android.tools.r8.dex.Constants;
import com.android.tools.r8.errors.Unreachable;
import com.android.tools.r8.graph.AppInfoWithClassHierarchy;
import com.android.tools.r8.graph.AppView;
@@ -33,7 +32,6 @@
import com.android.tools.r8.ir.regalloc.LiveIntervals;
import com.android.tools.r8.position.MethodPosition;
import com.android.tools.r8.shaking.AppInfoWithLiveness;
-import com.android.tools.r8.utils.BooleanUtils;
import com.android.tools.r8.utils.IterableUtils;
import com.android.tools.r8.utils.LongInterval;
import com.android.tools.r8.utils.ObjectUtils;
@@ -180,8 +178,6 @@
private LinkedList<Phi> phiUsers = new LinkedList<>();
private Set<Phi> uniquePhiUsers = null;
- private Value nextConsecutive = null;
- private Value previousConsecutive = null;
private LiveIntervals liveIntervals;
private int needsRegister = -1;
private boolean isThis = false;
@@ -213,6 +209,14 @@
return definition;
}
+ @SuppressWarnings({"TypeParameterUnusedInFormals", "unchecked"})
+ public <T extends Instruction> T getDefinitionOrNull(Predicate<Instruction> predicate) {
+ if (definition != null && predicate.test(definition)) {
+ return (T) definition;
+ }
+ return null;
+ }
+
public boolean hasAliasedValue() {
return getAliasedValue() != this;
}
@@ -306,47 +310,6 @@
end.addDebugValue(this);
}
- public void linkTo(Value other) {
- assert nextConsecutive == null || nextConsecutive == other;
- assert other.previousConsecutive == null || other.previousConsecutive == this;
- other.previousConsecutive = this;
- nextConsecutive = other;
- }
-
- public void replaceLink(Value newArgument) {
- assert isLinked();
- if (previousConsecutive != null) {
- previousConsecutive.nextConsecutive = newArgument;
- newArgument.previousConsecutive = previousConsecutive;
- previousConsecutive = null;
- }
- if (nextConsecutive != null) {
- nextConsecutive.previousConsecutive = newArgument;
- newArgument.nextConsecutive = nextConsecutive;
- nextConsecutive = null;
- }
- }
-
- public boolean isLinked() {
- return nextConsecutive != null || previousConsecutive != null;
- }
-
- public Value getStartOfConsecutive() {
- Value current = this;
- while (current.getPreviousConsecutive() != null) {
- current = current.getPreviousConsecutive();
- }
- return current;
- }
-
- public Value getNextConsecutive() {
- return nextConsecutive;
- }
-
- public Value getPreviousConsecutive() {
- return previousConsecutive;
- }
-
public boolean onlyUsedInBlock(BasicBlock block) {
if (hasPhiUsers() || hasDebugUsers()) {
return false;
@@ -783,15 +746,6 @@
return false;
}
- public boolean hasRegisterConstraint() {
- for (Instruction instruction : uniqueUsers()) {
- if (instruction.maxInValueRegister() != Constants.U16BIT_MAX) {
- return true;
- }
- }
- return false;
- }
-
public boolean isValueOnStack() {
return false;
}
@@ -897,11 +851,6 @@
&& getConstInstruction().asConstNumber().getRawValue() == rawValue;
}
- public boolean isConstBoolean(boolean value) {
- return isConstNumber()
- && definition.asConstNumber().getRawValue() == BooleanUtils.longValue(value);
- }
-
public boolean isConstZero() {
return isConstNumber() && definition.asConstNumber().isZero();
}
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 c66b0eb..185cce6 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
@@ -256,6 +256,11 @@
private final Timing timing;
+ Iterable<LiveIntervals> getArgumentLiveIntervals() {
+ return Iterables.transform(
+ code.arguments(), argument -> argument.outValue().getLiveIntervals());
+ }
+
// Whether or not the code has a move exception instruction. Used to pin the move exception
// register.
private boolean hasDedicatedMoveExceptionRegister() {
@@ -352,7 +357,6 @@
@Override
public void allocateRegisters() {
// There are no linked values prior to register allocation.
- assert noLinkedValues();
assert code.isConsistentSSA(appView);
if (this.code.method().accessFlags.isBridge() && implementationIsBridge(this.code)) {
transformBridgeMethod();
@@ -1011,10 +1015,7 @@
}
Reference2IntMap<LiveIntervals> originalRegisterAssignment = new Reference2IntOpenHashMap<>();
originalRegisterAssignment.defaultReturnValue(NO_REGISTER);
- for (Value current = firstArgumentValue;
- current != null;
- current = current.getNextConsecutive()) {
- LiveIntervals intervals = current.getLiveIntervals();
+ for (LiveIntervals intervals : getArgumentLiveIntervals()) {
int conservativeRealRegisterEnd = realRegisterNumberFromAllocated(intervals.getRegisterEnd());
assert !mode.hasRegisterConstraint(intervals)
|| (mode.is8BitRefinement()
@@ -1145,10 +1146,8 @@
timing.end();
timing.begin("Argument linked");
- for (Value argumentValue = firstArgumentValue;
- argumentValue != null;
- argumentValue = argumentValue.getNextConsecutive()) {
- allocateRegistersForInvokeRangeSplits(argumentValue.getLiveIntervals());
+ for (LiveIntervals argumentLiveIntervals : getArgumentLiveIntervals()) {
+ allocateRegistersForInvokeRangeSplits(argumentLiveIntervals);
}
timing.end();
@@ -1199,18 +1198,14 @@
}
private void processArgumentLiveIntervals() {
- for (Value argumentValue = firstArgumentValue;
- argumentValue != null;
- argumentValue = argumentValue.getNextConsecutive()) {
- LiveIntervals argumentInterval = argumentValue.getLiveIntervals();
+ for (LiveIntervals argumentInterval : getArgumentLiveIntervals()) {
assert argumentInterval.hasRegister();
argumentInterval.setHandled();
if (!mode.hasRegisterConstraint(argumentInterval)) {
// All the argument intervals are active in the beginning and have preallocated registers.
active.add(argumentInterval);
} else if (mode.is8BitRefinement()
- && argumentInterval.getRegister() + argumentValue.requiredRegisters()
- <= numberOf4BitArgumentRegisters) {
+ && argumentInterval.getRegisterEnd() < numberOf4BitArgumentRegisters) {
active.add(argumentInterval);
} else {
// Treat the argument interval as spilled which will require a load to a different
@@ -1419,10 +1414,7 @@
private boolean verifyRegisterAssignmentNotConflictingWithArgument(LiveIntervals interval) {
assert interval.hasRegister();
- for (Value argumentValue = firstArgumentValue;
- argumentValue != null;
- argumentValue = argumentValue.getNextConsecutive()) {
- LiveIntervals argumentIntervals = argumentValue.getLiveIntervals();
+ for (LiveIntervals argumentIntervals : getArgumentLiveIntervals()) {
assert interval.getSplitParent() == argumentIntervals
|| !isPinnedArgumentRegister(argumentIntervals)
|| !interval.hasConflictingRegisters(argumentIntervals)
@@ -1623,10 +1615,7 @@
// Exclude the pinned argument registers for which there exists a split that overlaps with
// one of the inputs to the invoke-range instruction.
timing.begin("Exclude pinned args");
- for (Value argument = firstArgumentValue;
- argument != null;
- argument = argument.getNextConsecutive()) {
- LiveIntervals argumentLiveIntervals = argument.getLiveIntervals();
+ for (LiveIntervals argumentLiveIntervals : getArgumentLiveIntervals()) {
if (isPinnedArgumentRegister(argumentLiveIntervals)
&& liveIntervalsOverlappingAnyOf(argumentLiveIntervals, intervalsList)) {
excludeRegistersForInterval(argumentLiveIntervals);
@@ -2186,10 +2175,9 @@
firstArgumentValue.getLiveIntervals().forEachRegister(freePositions::setBlocked);
}
// But not any of the other argument registers.
- for (Value argument = firstArgumentValue;
- argument != null;
- argument = argument.getNextConsecutive()) {
- assert !isPinnedArgumentRegister(argument.getLiveIntervals()) || argument.isThis();
+ for (LiveIntervals argumentIntervals : getArgumentLiveIntervals()) {
+ assert !isPinnedArgumentRegister(argumentIntervals)
+ || argumentIntervals.getValue().isThis();
}
} else {
// Generally argument reuse is not allowed and we block all the argument registers so that
@@ -2202,10 +2190,8 @@
if (mode.is8BitRefinement()) {
assert numberOf4BitArgumentRegisters > 0;
int remainingNumberOf4BitArgumentRegisters = numberOf4BitArgumentRegisters;
- for (Value argumentValue = firstArgumentValue;
- argumentValue != null;
- argumentValue = argumentValue.getNextConsecutive()) {
- int requiredRegisters = argumentValue.requiredRegisters();
+ for (LiveIntervals argumentLiveIntervals : getArgumentLiveIntervals()) {
+ int requiredRegisters = argumentLiveIntervals.requiredRegisters();
remainingNumberOf4BitArgumentRegisters -= requiredRegisters;
if (remainingNumberOf4BitArgumentRegisters < 0) {
// Block all subsequent argument registers.
@@ -2214,7 +2200,7 @@
// Block this argument register if there is any overlap between the two live intervals.
// TODO(b/374266460): Allow using the argument register even when there are overlapping
// live intervals.
- if (argumentValue.getLiveIntervals().anySplitOverlaps(unhandledInterval)) {
+ if (argumentLiveIntervals.anySplitOverlaps(unhandledInterval)) {
for (int j = 0; j < requiredRegisters; j++) {
freePositions.setBlocked(i + j);
}
@@ -2413,10 +2399,8 @@
return false;
}
if (isArgumentRegister(candidate)) {
- for (Value argument = firstArgumentValue;
- argument != null;
- argument = argument.getNextConsecutive()) {
- if (isPinnedArgument(argument)) {
+ for (LiveIntervals argumentLiveIntervals : getArgumentLiveIntervals()) {
+ if (isPinnedArgumentRegister(argumentLiveIntervals)) {
return false;
}
}
@@ -2860,24 +2844,11 @@
protected void splitOverlappingInactiveIntervals(
LiveIntervals unhandledInterval, int candidate, boolean candidateIsWide) {
- List<LiveIntervals> newInactive = new ArrayList<>();
Iterator<LiveIntervals> inactiveIterator = inactive.iterator();
while (inactiveIterator.hasNext()) {
LiveIntervals intervals = inactiveIterator.next();
if (intervals.usesRegister(candidate, candidateIsWide)
&& 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());
- if (nextUsePosition != Integer.MAX_VALUE) {
- LiveIntervals split = intervals.splitBefore(nextUsePosition, mode);
- split.setRegister(intervals.getRegister());
- newInactive.add(split);
- }
- }
if (intervals.getStart() > unhandledInterval.getStart()) {
// The inactive live intervals hasn't started yet. Clear the temporary register
// assignment and move back to unhandled for register reassignment.
@@ -2892,7 +2863,6 @@
}
}
}
- inactive.addAll(newInactive);
}
private void spillOverlappingActiveIntervals(
@@ -2939,19 +2909,14 @@
intervals.setSpilled(true);
}
if (splitChild.hasUses()) {
- if (splitChild.isLinked() && !splitChild.isArgumentInterval()) {
- // Spilling a value with a pinned register. We need to move back at the next use.
- LiveIntervals splitOfSplit = splitChild.splitBefore(splitChild.getFirstUse(), mode);
- splitOfSplit.setRegister(intervals.getRegister());
- inactive.add(splitOfSplit);
- } else if (intervals.getValue().isConstNumber()) {
+ if (intervals.getValue().isConstNumber()) {
// TODO(ager): Do this for all constants. Currently we only rematerialize const
// number and therefore we only do it for numbers at this point.
splitRangesForSpilledConstant(splitChild, registerNumber);
} else if (intervals.isArgumentInterval()) {
splitRangesForSpilledArgument(splitChild);
} else {
- splitRangesForSpilledInterval(splitChild, registerNumber);
+ splitRangesForSpilledInterval(splitChild);
}
}
}
@@ -2976,21 +2941,11 @@
}
}
- private void splitRangesForSpilledInterval(LiveIntervals spilled, int registerNumber) {
+ private void splitRangesForSpilledInterval(LiveIntervals spilled) {
// Spilling a non-pinned, non-rematerializable value. We use the value in the spill
// register for as long as possible to avoid further moves.
assert spilled.isSpilled();
assert !spilled.getValue().isConstNumber();
- assert !spilled.isLinked() || spilled.isArgumentInterval();
- boolean isSpillingToArgumentRegister =
- spilled.isArgumentInterval() || isArgumentRegister(registerNumber);
- if (isSpillingToArgumentRegister) {
- if (mode.is8Bit()) {
- registerNumber = Constants.U8BIT_MAX;
- } else {
- registerNumber = Constants.U16BIT_MAX;
- }
- }
LiveIntervalsUse firstUseWithConstraint = spilled.firstUseWithConstraint(mode);
if (firstUseWithConstraint != null) {
int register = spilled.getRegister();
@@ -3015,7 +2970,6 @@
// as much as possible.
assert spilled.isSpilled();
assert spilled.getValue().isConstNumber();
- assert !spilled.isLinked() || spilled.isArgumentInterval();
// Do not split range if constant is reused by one of the eleven following instruction.
int maxGapSize = 11 * INSTRUCTION_NUMBER_DELTA;
LiveIntervalsUse firstUseWithConstraint = spilled.firstUseWithConstraint(mode);
@@ -3253,19 +3207,7 @@
instructionNumber = instruction.getNumber();
}
if (value.getLiveIntervals() == null) {
- Value current = value.getStartOfConsecutive();
- LiveIntervals intervals = new LiveIntervals(current);
- while (true) {
- liveIntervals.add(intervals);
- Value next = current.getNextConsecutive();
- if (next == null) {
- break;
- }
- LiveIntervals nextIntervals = new LiveIntervals(next);
- intervals.link(nextIntervals);
- current = next;
- intervals = nextIntervals;
- }
+ liveIntervals.add(new LiveIntervals(value));
}
LiveIntervals intervals = value.getLiveIntervals();
if (firstInstructionInBlock <= instructionNumber &&
@@ -3585,10 +3527,13 @@
private static boolean argumentsAreAlreadyLinked(Invoke invoke) {
Iterator<Value> it = invoke.arguments().iterator();
- Value current = it.next();
+ Argument current = it.next().getDefinitionOrNull(Instruction::isArgument);
+ if (current == null) {
+ return false;
+ }
while (it.hasNext()) {
- Value next = it.next();
- if (!current.isLinked() || current.getNextConsecutive() != next) {
+ Argument next = it.next().getDefinitionOrNull(Instruction::isArgument);
+ if (current.getNext() != next) {
return false;
}
current = next;
@@ -3614,7 +3559,6 @@
Value last = firstArgumentValue = arguments.get(0);
for (int i = 1; i < arguments.size(); ++i) {
Value next = arguments.get(i);
- last.linkTo(next);
last.getLiveIntervals().link(next.getLiveIntervals());
last = next;
}
@@ -3660,12 +3604,9 @@
if (firstArgumentValue != null) {
increaseCapacity(numberOfArgumentRegisters - 1, true);
int register = 0;
- for (Value current = firstArgumentValue;
- current != null;
- current = current.getNextConsecutive()) {
- LiveIntervals argumentLiveInterval = current.getLiveIntervals();
- assignRegister(argumentLiveInterval, register);
- register += current.requiredRegisters();
+ for (LiveIntervals argumentLiveIntervals : getArgumentLiveIntervals()) {
+ assignRegister(argumentLiveIntervals, register);
+ register += argumentLiveIntervals.requiredRegisters();
}
}
}
@@ -3847,22 +3788,6 @@
return !freeRegisters.contains(register) || (isWide && !freeRegisters.contains(register + 1));
}
- private boolean noLinkedValues() {
- for (BasicBlock block : code.blocks) {
- for (Phi phi : block.getPhis()) {
- assert phi.getNextConsecutive() == null;
- }
- for (Instruction instruction : block.getInstructions()) {
- for (Value value : instruction.inValues()) {
- assert value.getNextConsecutive() == null;
- }
- assert instruction.outValue() == null ||
- instruction.outValue().getNextConsecutive() == null;
- }
- }
- return true;
- }
-
@Override
public String toString() {
StringBuilder builder = new StringBuilder("Live ranges:\n");
diff --git a/src/main/java/com/android/tools/r8/ir/regalloc/LiveIntervals.java b/src/main/java/com/android/tools/r8/ir/regalloc/LiveIntervals.java
index f423296..75fd057 100644
--- a/src/main/java/com/android/tools/r8/ir/regalloc/LiveIntervals.java
+++ b/src/main/java/com/android/tools/r8/ir/regalloc/LiveIntervals.java
@@ -154,10 +154,6 @@
next.previousConsecutive = this;
}
- public boolean isLinked() {
- return splitParent.previousConsecutive != null || splitParent.nextConsecutive != null;
- }
-
public boolean isArgumentInterval() {
Instruction definition = this.splitParent.value.definition;
return definition != null && definition.isArgument();
diff --git a/src/main/java/com/android/tools/r8/ir/regalloc/SpillMoveSet.java b/src/main/java/com/android/tools/r8/ir/regalloc/SpillMoveSet.java
index 2575d3b..736ed62 100644
--- a/src/main/java/com/android/tools/r8/ir/regalloc/SpillMoveSet.java
+++ b/src/main/java/com/android/tools/r8/ir/regalloc/SpillMoveSet.java
@@ -7,12 +7,12 @@
import com.android.tools.r8.graph.AppView;
import com.android.tools.r8.ir.analysis.type.Nullability;
import com.android.tools.r8.ir.analysis.type.TypeElement;
+import com.android.tools.r8.ir.code.Argument;
import com.android.tools.r8.ir.code.BasicBlock;
import com.android.tools.r8.ir.code.IRCode;
import com.android.tools.r8.ir.code.Instruction;
import com.android.tools.r8.ir.code.InstructionListIterator;
import com.android.tools.r8.ir.code.Position;
-import com.android.tools.r8.ir.code.Value;
import com.android.tools.r8.utils.MapUtils;
import java.util.Collection;
import java.util.Collections;
@@ -135,12 +135,9 @@
insertAt.next();
}
// Generate moves for each argument.
- for (Value argumentValue = allocator.firstArgumentValue;
- argumentValue != null;
- argumentValue = argumentValue.getNextConsecutive()) {
- Instruction instruction = argumentValue.definition;
- if (needsMovesBeforeInstruction(instruction)) {
- scheduleMovesBeforeInstruction(tempRegister, instruction, insertAt);
+ for (Argument argument : code.arguments()) {
+ if (needsMovesBeforeInstruction(argument)) {
+ scheduleMovesBeforeInstruction(tempRegister, argument, insertAt);
}
}
}
diff --git a/src/main/java/com/android/tools/r8/ir/regalloc/UnsplitArgumentsResult.java b/src/main/java/com/android/tools/r8/ir/regalloc/UnsplitArgumentsResult.java
index 5b0810d..cf78fe1 100644
--- a/src/main/java/com/android/tools/r8/ir/regalloc/UnsplitArgumentsResult.java
+++ b/src/main/java/com/android/tools/r8/ir/regalloc/UnsplitArgumentsResult.java
@@ -5,7 +5,6 @@
import static com.android.tools.r8.ir.regalloc.LiveIntervals.NO_REGISTER;
-import com.android.tools.r8.ir.code.Value;
import it.unimi.dsi.fastutil.objects.Reference2IntMap;
public class UnsplitArgumentsResult {
@@ -28,10 +27,8 @@
// Returns true if any changes were made.
public boolean revertPartial() {
boolean changed = false;
- for (Value argument = allocator.firstArgumentValue;
- argument != null;
- argument = argument.getNextConsecutive()) {
- for (LiveIntervals child : argument.getLiveIntervals().getSplitChildren()) {
+ for (LiveIntervals argumentLiveIntervals : allocator.getArgumentLiveIntervals()) {
+ for (LiveIntervals child : argumentLiveIntervals.getSplitChildren()) {
changed |= revertPartial(child);
}
}
