blob: 93fc6500420a87adce7bf66cf3da40fcc786bb4b [file] [log] [blame]
// Copyright (c) 2017, the R8 project authors. Please see the AUTHORS file
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.
package com.android.tools.r8.cf;
import static com.android.tools.r8.ir.regalloc.LiveIntervals.NO_REGISTER;
import com.android.tools.r8.cf.TypeVerificationHelper.TypeInfo;
import com.android.tools.r8.errors.Unreachable;
import com.android.tools.r8.graph.AppView;
import com.android.tools.r8.ir.code.BasicBlock;
import com.android.tools.r8.ir.code.DebugLocalWrite;
import com.android.tools.r8.ir.code.Dup;
import com.android.tools.r8.ir.code.Dup2;
import com.android.tools.r8.ir.code.IRCode;
import com.android.tools.r8.ir.code.IRCode.LiveAtEntrySets;
import com.android.tools.r8.ir.code.Instruction;
import com.android.tools.r8.ir.code.InstructionIterator;
import com.android.tools.r8.ir.code.Load;
import com.android.tools.r8.ir.code.Phi;
import com.android.tools.r8.ir.code.Pop;
import com.android.tools.r8.ir.code.StackValue;
import com.android.tools.r8.ir.code.StackValues;
import com.android.tools.r8.ir.code.Store;
import com.android.tools.r8.ir.code.Swap;
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.RegisterAllocator;
import com.android.tools.r8.utils.InternalOptions;
import com.google.common.collect.ImmutableList;
import it.unimi.dsi.fastutil.ints.Int2ReferenceMap;
import it.unimi.dsi.fastutil.ints.Int2ReferenceOpenHashMap;
import it.unimi.dsi.fastutil.ints.IntOpenHashSet;
import it.unimi.dsi.fastutil.ints.IntSet;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
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.NavigableSet;
import java.util.PriorityQueue;
import java.util.Set;
import java.util.TreeSet;
/**
* Allocator for assigning local-indexes to non-stack values.
*
* <p>This is mostly a very simple variant of {@link
* com.android.tools.r8.ir.regalloc.LinearScanRegisterAllocator} since for CF there are no register
* constraints and thus no need for spilling.
*/
public class CfRegisterAllocator implements RegisterAllocator {
private final AppView<?> appView;
private final IRCode code;
private final TypeVerificationHelper typeHelper;
// Mapping from basic blocks to the set of values live at entry to that basic block.
private Map<BasicBlock, LiveAtEntrySets> liveAtEntrySets;
public static class TypesAtBlockEntry {
public final Int2ReferenceMap<TypeInfo> registers;
public final List<TypeInfo> stack; // Last item is the top.
TypesAtBlockEntry(Int2ReferenceMap<TypeInfo> registers, List<TypeInfo> stack) {
this.registers = registers;
this.stack = stack;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("regs[");
for (Int2ReferenceMap.Entry<TypeInfo> kv : registers.int2ReferenceEntrySet()) {
sb.append(kv.getIntKey()).append(":").append(kv.getValue()).append(", ");
}
sb.append("], stack[");
for (TypeInfo t : stack) {
sb.append(t).append(", ");
}
sb.append("]");
return sb.toString();
}
};
private final Map<BasicBlock, TypesAtBlockEntry> lazyTypeInfoAtBlockEntry = new HashMap<>();
// List of all top-level live intervals for all SSA values.
private final List<LiveIntervals> liveIntervals = new ArrayList<>();
// List of active intervals.
private final List<LiveIntervals> active = new LinkedList<>();
// List of intervals where the current instruction falls into one of their live range holes.
private final List<LiveIntervals> inactive = new LinkedList<>();
// List of intervals that no register has been allocated to sorted by first live range.
private final PriorityQueue<LiveIntervals> unhandled = new PriorityQueue<>();
// The set of registers that are free for allocation.
private NavigableSet<Integer> freeRegisters = new TreeSet<>();
private int nextUnusedRegisterNumber = 0;
private int maxRegisterNumber = 0;
private int maxArgumentRegisterNumber = -1;
public CfRegisterAllocator(AppView<?> appView, IRCode code, TypeVerificationHelper typeHelper) {
this.appView = appView;
this.code = code;
this.typeHelper = typeHelper;
}
@Override
public int registersUsed() {
return maxRegisterNumber + 1;
}
@Override
public int getRegisterForValue(Value value, int instructionNumber) {
return getRegisterForValue(value);
}
public int getRegisterForValue(Value value) {
if (value instanceof FixedLocalValue) {
return ((FixedLocalValue) value).getRegister(this);
}
assert !value.getLiveIntervals().hasSplits();
return value.getLiveIntervals().getRegister();
}
@Override
public int getArgumentOrAllocateRegisterForValue(Value value, int instructionNumber) {
return getRegisterForValue(value);
}
@Override
public InternalOptions options() {
return appView.options();
}
@Override
public void allocateRegisters() {
computeNeedsRegister();
ImmutableList<BasicBlock> blocks = computeLivenessInformation();
performLinearScan();
// Even if the method is reachability sensitive, we do not compute debug information after
// register allocation. We just treat the method as being in debug mode in order to keep
// locals alive for their entire live range. In release mode the liveness is all that matters
// and we do not actually want locals information in the output.
if (appView.options().debug) {
LinearScanRegisterAllocator.computeDebugInfo(
code, blocks, liveIntervals, this, liveAtEntrySets);
}
}
private void computeNeedsRegister() {
for (Instruction instruction : code.instructions()) {
Value outValue = instruction.outValue();
if (outValue != null) {
boolean isStackValue =
(outValue instanceof StackValue) || (outValue instanceof StackValues);
outValue.setNeedsRegister(!isStackValue);
}
}
}
private ImmutableList<BasicBlock> computeLivenessInformation() {
ImmutableList<BasicBlock> blocks = code.numberInstructions();
liveAtEntrySets = code.computeLiveAtEntrySets();
LinearScanRegisterAllocator.computeLiveRanges(
appView.options(), code, liveAtEntrySets, liveIntervals);
return blocks;
}
private void performLinearScan() {
unhandled.addAll(liveIntervals);
while (!unhandled.isEmpty() && unhandled.peek().getValue().isArgument()) {
LiveIntervals argument = unhandled.poll();
assignRegisterToUnhandledInterval(argument, getNextFreeRegister(argument.getType().isWide()));
}
maxArgumentRegisterNumber = nextUnusedRegisterNumber - 1;
while (!unhandled.isEmpty()) {
LiveIntervals unhandledInterval = unhandled.poll();
assert !unhandledInterval.getValue().isArgument();
int start = unhandledInterval.getStart();
{
// Check for active intervals that expired or became inactive.
Iterator<LiveIntervals> it = active.iterator();
while (it.hasNext()) {
LiveIntervals activeIntervals = it.next();
if (start >= activeIntervals.getEnd()) {
it.remove();
freeRegistersForIntervals(activeIntervals);
} else if (!activeIntervals.overlapsPosition(start)) {
assert activeIntervals.getRegister() != NO_REGISTER;
it.remove();
inactive.add(activeIntervals);
freeRegistersForIntervals(activeIntervals);
}
}
}
{
// Check for inactive intervals that expired or become active.
Iterator<LiveIntervals> it = inactive.iterator();
while (it.hasNext()) {
LiveIntervals inactiveIntervals = it.next();
if (start >= inactiveIntervals.getEnd()) {
it.remove();
} else if (inactiveIntervals.overlapsPosition(start)) {
it.remove();
assert inactiveIntervals.getRegister() != NO_REGISTER;
active.add(inactiveIntervals);
takeRegistersForIntervals(inactiveIntervals);
}
}
}
// Find a free register that is not used by an inactive interval that overlaps with
// unhandledInterval.
if (tryHint(unhandledInterval)) {
assignRegisterToUnhandledInterval(unhandledInterval, unhandledInterval.getHint());
} else {
boolean wide = unhandledInterval.getType().isWide();
int register;
NavigableSet<Integer> previousFreeRegisters = new TreeSet<Integer>(freeRegisters);
while (true) {
register = getNextFreeRegister(wide);
boolean overlapsInactiveInterval = false;
for (LiveIntervals inactiveIntervals : inactive) {
if (inactiveIntervals.usesRegister(register, wide)
&& unhandledInterval.overlaps(inactiveIntervals)) {
overlapsInactiveInterval = true;
break;
}
}
if (!overlapsInactiveInterval) {
break;
}
// Remove so that next invocation of getNextFreeRegister does not consider this.
freeRegisters.remove(register);
// For wide types, register + 1 and 2 might be good even though register + 0 and 1
// weren't, so don't remove register+1 from freeRegisters.
}
freeRegisters = previousFreeRegisters;
assignRegisterToUnhandledInterval(unhandledInterval, register);
}
}
}
// Note that getNextFreeRegister will not take the register before it is committed to an interval.
private int getNextFreeRegister(boolean isWide) {
if (!freeRegisters.isEmpty()) {
if (isWide) {
// In case of a wide local we don't allow it to start at maxArgumentRegisterNumber, that is
// either at the last, non-wide argument or the second register of the last, wide argument.
// This is a workaround for a jacoco bug (see b/117593305) where the jacoco instrumentation
// algorithm assumes that we never reuse argument registers so it is safe to insert the
// instrumentation registers starting with the first register after the arguments.
//
// Without this workaround we may create a wide local whose first register overlaps the
// last argument and whose second register will overlap the first instrumentation register.
// The result is a Java verification error.
for (Integer register : freeRegisters) {
if ((freeRegisters.contains(register + 1) || nextUnusedRegisterNumber == register + 1)
&& register != maxArgumentRegisterNumber) {
return register;
}
}
return nextUnusedRegisterNumber;
}
return freeRegisters.first();
}
return nextUnusedRegisterNumber;
}
private void freeRegistersForIntervals(LiveIntervals intervals) {
int register = intervals.getRegister();
freeRegisters.add(register);
if (intervals.getType().isWide()) {
freeRegisters.add(register + 1);
}
}
private void takeRegistersForIntervals(LiveIntervals intervals) {
int register = intervals.getRegister();
freeRegisters.remove(register);
if (intervals.getType().isWide()) {
freeRegisters.remove(register + 1);
}
}
private void updateHints(LiveIntervals intervals) {
for (Phi phi : intervals.getValue().uniquePhiUsers()) {
if (!phi.isValueOnStack()) {
phi.getLiveIntervals().setHint(intervals, unhandled);
for (Value value : phi.getOperands()) {
value.getLiveIntervals().setHint(intervals, unhandled);
}
}
}
}
private boolean tryHint(LiveIntervals unhandled) {
if (unhandled.getHint() == null) {
return false;
}
boolean isWide = unhandled.getType().isWide();
int hintRegister = unhandled.getHint();
if (freeRegisters.contains(hintRegister)
&& (!isWide || freeRegisters.contains(hintRegister + 1))) {
for (LiveIntervals inactive : inactive) {
if (inactive.usesRegister(hintRegister, isWide) && inactive.overlaps(unhandled)) {
return false;
}
}
return true;
}
return false;
}
private void assignRegisterToUnhandledInterval(LiveIntervals unhandledInterval, int register) {
assignRegister(unhandledInterval, register);
takeRegistersForIntervals(unhandledInterval);
updateRegisterState(register, unhandledInterval.getType().isWide());
updateHints(unhandledInterval);
active.add(unhandledInterval);
}
private void updateRegisterState(int register, boolean needsRegisterPair) {
int maxRegister = register + (needsRegisterPair ? 1 : 0);
if (maxRegister >= nextUnusedRegisterNumber) {
nextUnusedRegisterNumber = maxRegister + 1;
}
maxRegisterNumber = Math.max(maxRegisterNumber, maxRegister);
}
private void assignRegister(LiveIntervals intervals, int register) {
intervals.setRegister(register);
}
public void addToLiveAtEntrySet(BasicBlock block, Collection<Phi> phis) {
for (Phi phi : phis) {
if (phi.isValueOnStack()) {
liveAtEntrySets.get(block).liveStackValues.addLast(phi);
} else {
liveAtEntrySets.get(block).liveValues.add(phi);
}
}
}
public TypesAtBlockEntry getTypesAtBlockEntry(BasicBlock block) {
return lazyTypeInfoAtBlockEntry.computeIfAbsent(
block,
k -> {
Set<Value> liveValues = liveAtEntrySets.get(k).liveValues;
Int2ReferenceMap<TypeInfo> registers = new Int2ReferenceOpenHashMap<>(liveValues.size());
for (Value liveValue : liveValues) {
registers.put(getRegisterForValue(liveValue), typeHelper.getTypeInfo(liveValue));
}
Deque<Value> liveStackValues = liveAtEntrySets.get(k).liveStackValues;
List<TypeInfo> stack = new ArrayList<>(liveStackValues.size());
for (Value value : liveStackValues) {
stack.add(typeHelper.getTypeInfo(value));
}
return new TypesAtBlockEntry(registers, stack);
});
}
@Override
public void mergeBlocks(BasicBlock kept, BasicBlock removed) {
TypesAtBlockEntry typesOfKept = getTypesAtBlockEntry(kept);
TypesAtBlockEntry typesOfRemoved = getTypesAtBlockEntry(removed);
// Join types of registers (= JVM local variables).
assert typesOfKept.registers.size() == typesOfRemoved.registers.size();
// Updating the reference into lazyTypeInfoAtBlockEntry directly.
updateFirstRegisterMapByJoiningTheSecond(typesOfKept.registers, typesOfRemoved.registers);
// Join types of stack elements.
assert typesOfKept.stack.size() == typesOfRemoved.stack.size();
// Updating the reference into lazyTypeInfoAtBlockEntry directly.
updateFirstStackByJoiningTheSecond(typesOfKept.stack, typesOfRemoved.stack);
}
@Override
public boolean hasEqualTypesAtEntry(BasicBlock first, BasicBlock second) {
if (!java.util.Objects.equals(first.getLocalsAtEntry(), second.getLocalsAtEntry())) {
return false;
}
// Check that stack at entry is same.
List<TypeInfo> firstStack = getTypesAtBlockEntry(first).stack;
List<TypeInfo> secondStack = getTypesAtBlockEntry(second).stack;
if (firstStack.size() != secondStack.size()) {
return false;
}
for (int i = 0; i < firstStack.size(); i++) {
if (firstStack.get(i).getDexType() != secondStack.get(i).getDexType()) {
return false;
}
}
// Check if the blocks are catch-handlers, which implies that the exception is transferred
// through the stack.
if (first.entry().isMoveException() != second.entry().isMoveException()) {
return false;
}
// If both blocks are catch handlers, we require that the exceptions are the same type.
if (first.entry().isMoveException()
&& typeHelper.getTypeInfo(first.entry().outValue()).getDexType()
!= typeHelper.getTypeInfo(second.entry().outValue()).getDexType()) {
return false;
}
return true;
}
// Return false if this is not an instruction with the type of outvalue dependent on types of
// invalues.
private boolean tryApplyInstructionWithDependentOutType(
Instruction instruction, Int2ReferenceMap<TypeInfo> registers, Deque<TypeInfo> stack) {
if (instruction.outValue() == null || instruction.inValues().isEmpty()) {
return false;
}
if (instruction instanceof Load) {
int register = getRegisterForValue(instruction.inValues().get(0));
assert registers.containsKey(register);
stack.addLast(registers.get(register));
} else if (instruction instanceof Store) {
int register = getRegisterForValue(instruction.outValue());
registers.put(register, stack.removeLast());
} else if (instruction instanceof Pop) {
stack.removeLast();
} else if (instruction instanceof Dup) {
stack.addLast(stack.getLast());
} else if (instruction instanceof Dup2) {
TypeInfo wasTop = stack.removeLast();
TypeInfo wasBelowTop = stack.getLast();
stack.addLast(wasTop);
stack.addLast(wasBelowTop);
stack.addLast(wasTop);
} else if (instruction instanceof Swap) {
TypeInfo wasTop = stack.removeLast();
TypeInfo wasBelowTop = stack.removeLast();
stack.addLast(wasTop);
stack.addLast(wasBelowTop);
} else if (instruction instanceof DebugLocalWrite) {
int dstRegister = getRegisterForValue(instruction.outValue());
registers.put(dstRegister, stack.removeLast());
} else {
return false;
}
return true;
}
private void applyInstructionsToTypes(
BasicBlock block,
Int2ReferenceMap<TypeInfo> registers,
Deque<TypeInfo> stack,
int prefixSize) {
InstructionIterator it = block.iterator();
int instructionsLeft = prefixSize;
while (--instructionsLeft >= 0 && it.hasNext()) {
Instruction current = it.next();
if (tryApplyInstructionWithDependentOutType(current, registers, stack)) {
continue;
}
for (int i = current.inValues().size() - 1; i >= 0; --i) {
Value inValue = current.inValues().get(i);
if (inValue.isValueOnStack()) {
stack.removeLast();
}
}
Value outValue = current.outValue();
if (outValue == null) {
continue;
}
TypeInfo outType = typeHelper.getTypeInfo(outValue);
assert outType != null;
if (outValue.needsRegister()) {
int register = getRegisterForValue(outValue);
registers.put(register, outType);
} else if (outValue.isValueOnStack()) {
stack.addLast(outType);
} else {
throw new Unreachable();
}
}
}
private void applyInstructionsBackwardsToRegisterLiveness(
BasicBlock block, IntSet liveRegisters, int suffixSize) {
InstructionIterator iterator = block.iterator(block.getInstructions().size());
int instructionsLeft = suffixSize;
while (--instructionsLeft >= 0 && iterator.hasPrevious()) {
Instruction current = iterator.previous();
Value outValue = current.outValue();
if (outValue != null && outValue.needsRegister()) {
int register = getRegisterForValue(outValue);
assert liveRegisters.contains(register);
liveRegisters.remove(register);
}
for (Value inValue : current.inValues()) {
if (inValue.needsRegister()) {
int register = getRegisterForValue(inValue);
liveRegisters.add(register);
}
}
}
}
@Override
public void addNewBlockToShareIdenticalSuffix(
BasicBlock block, int suffixSize, List<BasicBlock> predsBeforeSplit) {
Int2ReferenceMap<TypeInfo> joinedRegistersBeforeSuffix = new Int2ReferenceOpenHashMap<>();
List<TypeInfo> joinedStackBeforeSuffix = new ArrayList<>(); // Last item is the top.
assert !predsBeforeSplit.isEmpty();
for (BasicBlock pred : predsBeforeSplit) {
// Replay instructions of prefix on registers and stack at block entry.
TypesAtBlockEntry types = getTypesAtBlockEntry(pred);
Int2ReferenceMap<TypeInfo> registersFromPrefix =
new Int2ReferenceOpenHashMap<>(types.registers);
Deque<TypeInfo> stackFromPrefix = new ArrayDeque<>(types.stack);
applyInstructionsToTypes(
pred, registersFromPrefix, stackFromPrefix, pred.getInstructions().size() - suffixSize);
// Replay instructions of suffix on registers at block end to compute liveness between prefix
// and suffix.
Int2ReferenceMap<TypeInfo> registersAtExit;
if (pred.getSuccessors().isEmpty()) {
registersAtExit = new Int2ReferenceOpenHashMap<>();
} else {
assert pred.getSuccessors().size() == 1;
registersAtExit = getTypesAtBlockEntry(pred.getSuccessors().get(0)).registers;
}
IntSet registersLiveFromSuffix = new IntOpenHashSet(registersAtExit.size() * 2);
registersLiveFromSuffix.addAll(registersAtExit.keySet());
applyInstructionsBackwardsToRegisterLiveness(pred, registersLiveFromSuffix, suffixSize);
// We have two sets of registers between the prefix and suffix:
// - 'registersFromPrefix', which is computed from block entry forwards, and
// - 'registersLiveFromSuffix', which is computed from block exit backwards.
// Keep only the registers from the prefix which are live as computed from the suffix.
Int2ReferenceMap<TypeInfo> registersBeforeSuffix =
new Int2ReferenceOpenHashMap<>(registersFromPrefix.size());
for (int register : registersLiveFromSuffix) {
assert registersFromPrefix.containsKey(register);
registersBeforeSuffix.put(register, registersFromPrefix.get(register));
}
updateFirstRegisterMapByJoiningTheSecond(joinedRegistersBeforeSuffix, registersBeforeSuffix);
updateFirstStackByJoiningTheSecond(
joinedStackBeforeSuffix, Arrays.asList(stackFromPrefix.toArray(new TypeInfo[0])));
}
assert !lazyTypeInfoAtBlockEntry.containsKey(block);
lazyTypeInfoAtBlockEntry.put(
block, new TypesAtBlockEntry(joinedRegistersBeforeSuffix, joinedStackBeforeSuffix));
}
// First registermap can be empty, otherwise they must have identical keysets
private void updateFirstRegisterMapByJoiningTheSecond(
Int2ReferenceMap<TypeInfo> map1, Int2ReferenceMap<TypeInfo> map2) {
if (map1.isEmpty()) {
map1.putAll(map2);
return;
}
assert map1.size() == map2.size();
for (Int2ReferenceMap.Entry<TypeInfo> entry1 : map1.int2ReferenceEntrySet()) {
int register = entry1.getIntKey();
TypeInfo type1 = entry1.getValue();
assert map2.containsKey(register);
TypeInfo joinedType = typeHelper.join(type1, map2.get(register));
if (joinedType != type1) {
map1.put(register, joinedType);
}
}
}
// First stack can be empty, otherwise they must have the same size.
private void updateFirstStackByJoiningTheSecond(List<TypeInfo> stack1, List<TypeInfo> stack2) {
if (stack1.isEmpty()) {
stack1.addAll(stack2);
return;
}
assert stack1.size() == stack2.size();
for (int i = 0; i < stack1.size(); ++i) {
TypeInfo type1 = stack1.get(i);
TypeInfo joinedType = typeHelper.join(type1, stack2.get(i));
if (joinedType != type1) {
stack1.set(i, joinedType);
}
}
}
}