[CF] Share more code between the CF and DEX register allocators.
Change-Id: I69efec48b80e3d0013fcb5d4e1d947475165c4a1
diff --git a/src/main/java/com/android/tools/r8/cf/CfRegisterAllocator.java b/src/main/java/com/android/tools/r8/cf/CfRegisterAllocator.java
index adf82dd..1c7c6d9 100644
--- a/src/main/java/com/android/tools/r8/cf/CfRegisterAllocator.java
+++ b/src/main/java/com/android/tools/r8/cf/CfRegisterAllocator.java
@@ -3,8 +3,6 @@
// BSD-style license that can be found in the LICENSE file.
package com.android.tools.r8.cf;
-import static com.android.tools.r8.dex.Constants.U16BIT_MAX;
-import static com.android.tools.r8.ir.code.IRCode.INSTRUCTION_NUMBER_DELTA;
import static com.android.tools.r8.ir.regalloc.LiveIntervals.NO_REGISTER;
import com.android.tools.r8.errors.Unreachable;
@@ -12,12 +10,10 @@
import com.android.tools.r8.ir.code.IRCode;
import com.android.tools.r8.ir.code.Instruction;
import com.android.tools.r8.ir.code.InstructionIterator;
-import com.android.tools.r8.ir.code.InstructionListIterator;
-import com.android.tools.r8.ir.code.Phi;
import com.android.tools.r8.ir.code.StackValue;
import com.android.tools.r8.ir.code.Value;
+import com.android.tools.r8.ir.regalloc.LinearScanRegisterAllocator;
import com.android.tools.r8.ir.regalloc.LiveIntervals;
-import com.android.tools.r8.ir.regalloc.LiveIntervalsUse;
import com.android.tools.r8.ir.regalloc.LiveRange;
import com.android.tools.r8.ir.regalloc.RegisterAllocator;
import com.android.tools.r8.utils.InternalOptions;
@@ -25,7 +21,6 @@
import it.unimi.dsi.fastutil.ints.IntList;
import java.util.ArrayList;
import java.util.Collection;
-import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
@@ -128,117 +123,7 @@
private void computeLivenessInformation() {
code.numberInstructions();
liveAtEntrySets = code.computeLiveAtEntrySets();
- computeLiveRanges();
- }
-
- private void computeLiveRanges() {
- for (BasicBlock block : code.topologicallySortedBlocks()) {
- Set<Value> live = new HashSet<>();
- List<BasicBlock> successors = block.getSuccessors();
- Set<Value> phiOperands = new HashSet<>();
- for (BasicBlock successor : successors) {
- live.addAll(liveAtEntrySets.get(successor));
- int predIndex = successor.getPredecessors().indexOf(block);
- for (Phi phi : successor.getPhis()) {
- live.remove(phi);
- phiOperands.add(phi.getOperand(predIndex));
- assert phi.getDebugValues().stream().allMatch(Value::needsRegister);
- phiOperands.addAll(phi.getDebugValues());
- }
- }
- live.addAll(phiOperands);
- List<Instruction> instructions = block.getInstructions();
- for (Value value : live) {
- int end = block.entry().getNumber() + instructions.size() * INSTRUCTION_NUMBER_DELTA;
- // Make sure that phi operands do not overlap the phi live range. The phi operand is
- // not live until the next instruction, but only until the gap before the next instruction
- // where the phi value takes over.
- if (phiOperands.contains(value)) {
- end--;
- }
- addLiveRange(value, block, end);
- }
- InstructionListIterator it = block.listIterator(block.getInstructions().size());
- while (it.hasPrevious()) {
- Instruction instruction = it.previous();
- int number = instruction.getNumber();
- Value definition = instruction.outValue();
- if (definition != null) {
- // For instructions that define values which have no use create a live range covering
- // the instruction. This will typically be instructions that can have side effects even
- // if their output is not used.
- if (!definition.isUsed()) {
- addLiveRange(definition, block, number + INSTRUCTION_NUMBER_DELTA);
- assert instruction.isArgument()
- : "Arguments should be the only potentially unused local in CF";
- }
- live.remove(definition);
- }
- for (Value use : instruction.inValues()) {
- if (use.needsRegister()) {
- if (!live.contains(use)) {
- live.add(use);
- addLiveRange(use, block, number);
- }
- LiveIntervals useIntervals = use.getLiveIntervals();
- useIntervals.addUse(new LiveIntervalsUse(number, U16BIT_MAX /* unconstrained */));
- }
- }
- if (options.debug) {
- for (Value use : instruction.getDebugValues()) {
- assert use.needsRegister();
- if (!live.contains(use)) {
- live.add(use);
- addLiveRange(use, block, number);
- }
- }
- }
- }
- }
- }
-
- private void addLiveRange(Value value, BasicBlock block, int end) {
- int firstInstructionInBlock = block.entry().getNumber();
- int instructionsSize = block.getInstructions().size() * INSTRUCTION_NUMBER_DELTA;
- int lastInstructionInBlock =
- firstInstructionInBlock + instructionsSize - INSTRUCTION_NUMBER_DELTA;
- int instructionNumber;
- if (value.isPhi()) {
- instructionNumber = firstInstructionInBlock;
- } else {
- Instruction instruction = value.definition;
- 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 intervals = value.getLiveIntervals();
- if (firstInstructionInBlock <= instructionNumber
- && instructionNumber <= lastInstructionInBlock) {
- if (value.isPhi()) {
- // Phis need to interfere with spill restore moves inserted before the instruction because
- // the phi value is defined on the inflowing edge.
- instructionNumber--;
- }
- intervals.addRange(new LiveRange(instructionNumber, end));
- if (!value.isPhi()) {
- intervals.addUse(new LiveIntervalsUse(instructionNumber, U16BIT_MAX /* unconstrained */));
- }
- } else {
- intervals.addRange(new LiveRange(firstInstructionInBlock - 1, end));
- }
+ LinearScanRegisterAllocator.computeLiveRanges(options, code, liveAtEntrySets, liveIntervals);
}
private void performLinearScan() {
diff --git a/src/main/java/com/android/tools/r8/ir/code/Load.java b/src/main/java/com/android/tools/r8/ir/code/Load.java
index 74cf861..cc45086 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Load.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Load.java
@@ -6,6 +6,7 @@
import com.android.tools.r8.cf.LoadStoreHelper;
import com.android.tools.r8.cf.TypeVerificationHelper;
import com.android.tools.r8.cf.code.CfLoad;
+import com.android.tools.r8.dex.Constants;
import com.android.tools.r8.errors.Unreachable;
import com.android.tools.r8.graph.AppInfoWithSubtyping;
import com.android.tools.r8.graph.DexType;
@@ -40,7 +41,7 @@
@Override
public int maxInValueRegister() {
- throw new Unreachable();
+ return Constants.U16BIT_MAX;
}
@Override
diff --git a/src/main/java/com/android/tools/r8/ir/code/Store.java b/src/main/java/com/android/tools/r8/ir/code/Store.java
index 05c7c79..6600137 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Store.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Store.java
@@ -7,6 +7,7 @@
import com.android.tools.r8.cf.LoadStoreHelper;
import com.android.tools.r8.cf.TypeVerificationHelper;
import com.android.tools.r8.cf.code.CfStore;
+import com.android.tools.r8.dex.Constants;
import com.android.tools.r8.errors.Unreachable;
import com.android.tools.r8.graph.AppInfoWithSubtyping;
import com.android.tools.r8.graph.DexType;
@@ -47,7 +48,7 @@
@Override
public int maxOutValueRegister() {
- throw new Unreachable();
+ return Constants.U16BIT_MAX;
}
@Override
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 b982b52..5de9f00 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
@@ -1814,20 +1814,25 @@
}
}
- private void addLiveRange(Value v, BasicBlock b, int end) {
- int firstInstructionInBlock = b.entry().getNumber();
- int instructionsSize = b.getInstructions().size() * INSTRUCTION_NUMBER_DELTA;
+ private static void addLiveRange(
+ Value value,
+ BasicBlock block,
+ int end,
+ List<LiveIntervals> liveIntervals,
+ InternalOptions options) {
+ int firstInstructionInBlock = block.entry().getNumber();
+ int instructionsSize = block.getInstructions().size() * INSTRUCTION_NUMBER_DELTA;
int lastInstructionInBlock =
firstInstructionInBlock + instructionsSize - INSTRUCTION_NUMBER_DELTA;
int instructionNumber;
- if (v.isPhi()) {
+ if (value.isPhi()) {
instructionNumber = firstInstructionInBlock;
} else {
- Instruction instruction = v.definition;
+ Instruction instruction = value.definition;
instructionNumber = instruction.getNumber();
}
- if (v.getLiveIntervals() == null) {
- Value current = v.getStartOfConsecutive();
+ if (value.getLiveIntervals() == null) {
+ Value current = value.getStartOfConsecutive();
LiveIntervals intervals = new LiveIntervals(current);
while (true) {
liveIntervals.add(intervals);
@@ -1841,17 +1846,18 @@
intervals = nextIntervals;
}
}
- LiveIntervals intervals = v.getLiveIntervals();
+ LiveIntervals intervals = value.getLiveIntervals();
if (firstInstructionInBlock <= instructionNumber &&
instructionNumber <= lastInstructionInBlock) {
- if (v.isPhi()) {
+ if (value.isPhi()) {
// Phis need to interfere with spill restore moves inserted before the instruction because
// the phi value is defined on the inflowing edge.
instructionNumber--;
}
intervals.addRange(new LiveRange(instructionNumber, end));
- if (!v.isPhi()) {
- int constraint = v.definition.maxOutValueRegister();
+ assert unconstrainedForCf(intervals.getRegisterLimit(), options);
+ if (!options.outputClassFiles && !value.isPhi()) {
+ int constraint = value.definition.maxOutValueRegister();
intervals.addUse(new LiveIntervalsUse(instructionNumber, constraint));
}
} else {
@@ -1859,10 +1865,18 @@
}
}
+ private void computeLiveRanges() {
+ computeLiveRanges(options, code, liveAtEntrySets, liveIntervals);
+ }
+
/**
* Compute live ranges based on liveAtEntry sets for all basic blocks.
*/
- private void computeLiveRanges() {
+ public static void computeLiveRanges(
+ InternalOptions options,
+ IRCode code,
+ Map<BasicBlock, Set<Value>> liveAtEntrySets,
+ List<LiveIntervals> liveIntervals) {
for (BasicBlock block : code.topologicallySortedBlocks()) {
Set<Value> live = new HashSet<>();
List<BasicBlock> successors = block.getSuccessors();
@@ -1886,7 +1900,7 @@
if (phiOperands.contains(value)) {
end--;
}
- addLiveRange(value, block, end);
+ addLiveRange(value, block, end, liveIntervals, options);
}
ListIterator<Instruction> iterator =
block.getInstructions().listIterator(block.getInstructions().size());
@@ -1898,19 +1912,29 @@
// the instruction. This will typically be instructions that can have side effects even
// if their output is not used.
if (!definition.isUsed()) {
- addLiveRange(definition, block, instruction.getNumber() + INSTRUCTION_NUMBER_DELTA);
+ addLiveRange(
+ definition,
+ block,
+ instruction.getNumber() + INSTRUCTION_NUMBER_DELTA,
+ liveIntervals,
+ options);
+ assert !options.outputClassFiles || instruction.isArgument()
+ : "Arguments should be the only potentially unused local in CF";
}
live.remove(definition);
}
for (Value use : instruction.inValues()) {
- if (!live.contains(use) && use.needsRegister()) {
- live.add(use);
- addLiveRange(use, block, instruction.getNumber());
- }
if (use.needsRegister()) {
- LiveIntervals useIntervals = use.getLiveIntervals();
- useIntervals.addUse(
- new LiveIntervalsUse(instruction.getNumber(), instruction.maxInValueRegister()));
+ assert unconstrainedForCf(instruction.maxInValueRegister(), options);
+ if (!live.contains(use)) {
+ live.add(use);
+ addLiveRange(use, block, instruction.getNumber(), liveIntervals, options);
+ }
+ if (!options.outputClassFiles) {
+ int inConstraint = instruction.maxInValueRegister();
+ LiveIntervals useIntervals = use.getLiveIntervals();
+ useIntervals.addUse(new LiveIntervalsUse(instruction.getNumber(), inConstraint));
+ }
}
}
if (options.debug) {
@@ -1919,7 +1943,7 @@
assert use.needsRegister();
if (!live.contains(use)) {
live.add(use);
- addLiveRange(use, block, number);
+ addLiveRange(use, block, number, liveIntervals, options);
}
}
}
@@ -1927,6 +1951,10 @@
}
}
+ private static boolean unconstrainedForCf(int constraint, InternalOptions options) {
+ return !options.outputClassFiles || constraint == Constants.U16BIT_MAX;
+ }
+
private void clearUserInfo() {
code.blocks.forEach(BasicBlock::clearUserInfo);
}
