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); } }