package org.graalvm.compiler.lir.alloc.lsra;
import static org.graalvm.compiler.lir.LIRValueUtil.isStackSlotValue;
import static org.graalvm.compiler.lir.LIRValueUtil.isVariable;
import static org.graalvm.compiler.lir.LIRValueUtil.isVirtualStackSlot;
import static jdk.vm.ci.code.ValueUtil.asRegister;
import static jdk.vm.ci.code.ValueUtil.isIllegal;
import static jdk.vm.ci.code.ValueUtil.isRegister;
import static jdk.vm.ci.code.ValueUtil.isStackSlot;
import java.util.ArrayList;
import java.util.Collections;
import java.util.EnumSet;
import java.util.List;
import org.graalvm.compiler.core.common.LIRKind;
import org.graalvm.compiler.core.common.util.IntList;
import org.graalvm.compiler.core.common.util.Util;
import org.graalvm.compiler.debug.Assertions;
import org.graalvm.compiler.debug.GraalError;
import org.graalvm.compiler.lir.LIRInstruction;
import org.graalvm.compiler.lir.Variable;
import jdk.vm.ci.code.RegisterValue;
import jdk.vm.ci.code.StackSlot;
import jdk.vm.ci.meta.AllocatableValue;
import jdk.vm.ci.meta.Constant;
import jdk.vm.ci.meta.Value;
import jdk.vm.ci.meta.ValueKind;
public final class Interval {
static final class RegisterBindingLists {
public Interval fixed;
public Interval any;
public Interval stack;
RegisterBindingLists(Interval fixed, Interval any, Interval stack) {
this.fixed = fixed;
this.any = any;
this.stack = stack;
}
public Interval get(RegisterBinding binding) {
switch (binding) {
case Any:
return any;
case Fixed:
return fixed;
case Stack:
return stack;
}
throw GraalError.shouldNotReachHere();
}
public void set(RegisterBinding binding, Interval list) {
assert list != null;
switch (binding) {
case Any:
any = list;
break;
case Fixed:
fixed = list;
break;
case Stack:
stack = list;
break;
}
}
public void addToListSortedByCurrentFromPositions(RegisterBinding binding, Interval interval) {
Interval list = get(binding);
Interval prev = null;
Interval cur = list;
while (cur.currentFrom() < interval.currentFrom()) {
prev = cur;
cur = cur.next;
}
Interval result = list;
if (prev == null) {
result = interval;
} else {
prev.next = interval;
}
interval.next = cur;
set(binding, result);
}
public void addToListSortedByStartAndUsePositions(RegisterBinding binding, Interval interval) {
Interval list = get(binding);
Interval prev = null;
Interval cur = list;
while (cur.from() < interval.from() || (cur.from() == interval.from() && cur.firstUsage(RegisterPriority.None) < interval.firstUsage(RegisterPriority.None))) {
prev = cur;
cur = cur.next;
}
if (prev == null) {
list = interval;
} else {
prev.next = interval;
}
interval.next = cur;
set(binding, list);
}
public void remove(RegisterBinding binding, Interval i) {
Interval list = get(binding);
Interval prev = null;
Interval cur = list;
while (cur != i) {
assert cur != null && !cur.isEndMarker() : "interval has not been found in list: " + i;
prev = cur;
cur = cur.next;
}
if (prev == null) {
set(binding, cur.next);
} else {
prev.next = cur.next;
}
}
}
public enum RegisterPriority {
None,
LiveAtLoopEnd,
ShouldHaveRegister,
MustHaveRegister;
public static final RegisterPriority[] VALUES = values();
public boolean greaterEqual(RegisterPriority other) {
return ordinal() >= other.ordinal();
}
public boolean lessThan(RegisterPriority other) {
return ordinal() < other.ordinal();
}
}
enum RegisterBinding {
Fixed,
Any,
Stack;
public static final RegisterBinding[] VALUES = values();
}
enum State {
Unhandled,
Active,
Inactive,
Handled;
}
public enum SpillState {
NoDefinitionFound,
NoSpillStore,
OneSpillStore,
SpillInDominator,
StoreAtDefinition,
StartInMemory,
NoOptimization;
public static final EnumSet<SpillState> ALWAYS_IN_MEMORY = EnumSet.of(SpillInDominator, StoreAtDefinition, StartInMemory);
}
public static final class UsePosList {
private IntList list;
public UsePosList(int initialCapacity) {
list = new IntList(initialCapacity * 2);
}
private UsePosList(IntList list) {
this.list = list;
}
public UsePosList splitAt(int splitPos) {
int i = size() - 1;
int len = 0;
while (i >= 0 && usePos(i) < splitPos) {
--i;
len += 2;
}
int listSplitIndex = (i + 1) * 2;
IntList childList = list;
list = IntList.copy(this.list, listSplitIndex, len);
childList.setSize(listSplitIndex);
UsePosList child = new UsePosList(childList);
return child;
}
public int usePos(int index) {
return list.get(index << 1);
}
public RegisterPriority registerPriority(int index) {
return RegisterPriority.VALUES[list.get((index << 1) + 1)];
}
public void add(int usePos, RegisterPriority registerPriority) {
assert list.size() == 0 || usePos(size() - 1) > usePos;
list.add(usePos);
list.add(registerPriority.ordinal());
}
public int size() {
return list.size() >> 1;
}
public void removeLowestUsePos() {
list.setSize(list.size() - 2);
}
public void setRegisterPriority(int index, RegisterPriority registerPriority) {
list.set((index << 1) + 1, registerPriority.ordinal());
}
@Override
public String toString() {
StringBuilder buf = new StringBuilder("[");
for (int i = size() - 1; i >= 0; --i) {
if (buf.length() != 1) {
buf.append(", ");
}
RegisterPriority prio = registerPriority(i);
buf.append(usePos(i)).append(" -> ").append(prio.ordinal()).append(':').append(prio);
}
return buf.append("]").toString();
}
}
protected static final int END_MARKER_OPERAND_NUMBER = Integer.MIN_VALUE;
public final AllocatableValue operand;
public final int operandNumber;
private AllocatableValue location;
private AllocatableValue spillSlot;
private ValueKind<?> kind;
private Range first;
private UsePosList usePosList;
private Range current;
Interval next;
State state;
private int cachedTo;
private Interval splitParent;
private List<Interval> splitChildren = Collections.emptyList();
private Interval currentSplitChild;
private boolean insertMoveWhenActivated;
private SpillState spillState;
private int spillDefinitionPos;
private Interval locationHint;
private Constant materializedValue;
private int numMaterializationValuesAdded;
void assignLocation(AllocatableValue newLocation) {
if (isRegister(newLocation)) {
assert this.location == null : "cannot re-assign location for " + this;
if (newLocation.getValueKind().equals(LIRKind.Illegal) && !kind.equals(LIRKind.Illegal)) {
this.location = asRegister(newLocation).asValue(kind);
return;
}
} else if (isIllegal(newLocation)) {
assert canMaterialize();
} else {
assert this.location == null || isRegister(this.location) || (isVirtualStackSlot(this.location) && isStackSlot(newLocation)) : "cannot re-assign location for " + this;
assert isStackSlotValue(newLocation);
assert !newLocation.getValueKind().equals(LIRKind.Illegal);
assert newLocation.getValueKind().equals(this.kind);
}
this.location = newLocation;
}
public boolean isEndMarker() {
return operandNumber == END_MARKER_OPERAND_NUMBER;
}
public AllocatableValue location() {
return location;
}
public ValueKind<?> kind() {
assert !isRegister(operand) : "cannot access type for fixed interval";
return kind;
}
public void setKind(ValueKind<?> kind) {
assert isRegister(operand) || this.kind().equals(LIRKind.Illegal) || this.kind().equals(kind) : "overwriting existing type";
this.kind = kind;
}
public Range first() {
return first;
}
public int from() {
return first.from;
}
int to() {
if (cachedTo == -1) {
cachedTo = calcTo();
}
assert cachedTo == calcTo() : "invalid cached value";
return cachedTo;
}
int numUsePositions() {
return usePosList.size();
}
public void setLocationHint(Interval interval) {
locationHint = interval;
}
public boolean isSplitParent() {
return splitParent == this;
}
boolean isSplitChild() {
return splitParent != this;
}
public Interval splitParent() {
assert splitParent.isSplitParent() : "not a split parent: " + this;
return splitParent;
}
public AllocatableValue spillSlot() {
return splitParent().spillSlot;
}
public void setSpillSlot(AllocatableValue slot) {
assert isStackSlotValue(slot);
assert splitParent().spillSlot == null || (isVirtualStackSlot(splitParent().spillSlot) && isStackSlot(slot)) : "connot overwrite existing spill slot";
splitParent().spillSlot = slot;
}
Interval currentSplitChild() {
return splitParent().currentSplitChild;
}
void makeCurrentSplitChild() {
splitParent().currentSplitChild = this;
}
boolean insertMoveWhenActivated() {
return insertMoveWhenActivated;
}
void setInsertMoveWhenActivated(boolean b) {
insertMoveWhenActivated = b;
}
public SpillState spillState() {
return splitParent().spillState;
}
public int spillDefinitionPos() {
return splitParent().spillDefinitionPos;
}
public void setSpillState(SpillState state) {
assert state.ordinal() >= spillState().ordinal() : "state cannot decrease";
splitParent().spillState = state;
}
public void setSpillDefinitionPos(int pos) {
assert spillState() == SpillState.SpillInDominator || spillState() == SpillState.NoDefinitionFound || spillDefinitionPos() == -1 : "cannot set the position twice";
splitParent().spillDefinitionPos = pos;
}
public boolean alwaysInMemory() {
return SpillState.ALWAYS_IN_MEMORY.contains(spillState()) && !canMaterialize();
}
void removeFirstUsePos() {
usePosList.removeLowestUsePos();
}
boolean intersects(Interval i) {
return first.intersects(i.first);
}
int intersectsAt(Interval i) {
return first.intersectsAt(i.first);
}
void rewindRange() {
current = first;
}
void nextRange() {
assert !this.isEndMarker() : "not allowed on sentinel";
current = current.next;
}
int currentFrom() {
return current.from;
}
int currentTo() {
return current.to;
}
boolean currentAtEnd() {
return current.isEndMarker();
}
boolean currentIntersects(Interval it) {
return current.intersects(it.current);
}
int currentIntersectsAt(Interval it) {
return current.intersectsAt(it.current);
}
Interval(AllocatableValue operand, int operandNumber, Interval intervalEndMarker, Range rangeEndMarker) {
assert operand != null;
this.operand = operand;
this.operandNumber = operandNumber;
if (isRegister(operand)) {
location = operand;
} else {
assert isIllegal(operand) || isVariable(operand);
}
this.kind = LIRKind.Illegal;
this.first = rangeEndMarker;
this.usePosList = new UsePosList(4);
this.current = rangeEndMarker;
this.next = intervalEndMarker;
this.cachedTo = -1;
this.spillState = SpillState.NoDefinitionFound;
this.spillDefinitionPos = -1;
splitParent = this;
currentSplitChild = this;
}
public void addMaterializationValue(Constant value) {
if (numMaterializationValuesAdded == 0) {
materializedValue = value;
} else {
materializedValue = null;
}
numMaterializationValuesAdded++;
}
public boolean canMaterialize() {
return getMaterializedValue() != null;
}
public Constant getMaterializedValue() {
return splitParent().materializedValue;
}
int calcTo() {
assert !first.isEndMarker() : "interval has no range";
Range r = first;
while (!r.next.isEndMarker()) {
r = r.next;
}
return r.to;
}
boolean checkSplitChildren() {
if (!splitChildren.isEmpty()) {
assert isSplitParent() : "only split parents can have children";
for (int i = 0; i < splitChildren.size(); i++) {
Interval i1 = splitChildren.get(i);
assert i1.splitParent() == this : "not a split child of this interval";
assert i1.kind().equals(kind()) : "must be equal for all split children";
assert (i1.spillSlot() == null && spillSlot == null) || i1.spillSlot().equals(spillSlot()) : "must be equal for all split children";
for (int j = i + 1; j < splitChildren.size(); j++) {
Interval i2 = splitChildren.get(j);
assert !i1.operand.equals(i2.operand) : "same register number";
if (i1.from() < i2.from()) {
assert i1.to() <= i2.from() && i1.to() < i2.to() : "intervals overlapping";
} else {
assert i2.from() < i1.from() : "intervals start at same opId";
assert i2.to() <= i1.from() && i2.to() < i1.to() : "intervals overlapping";
}
}
}
}
return true;
}
public Interval locationHint(boolean searchSplitChild) {
if (!searchSplitChild) {
return locationHint;
}
if (locationHint != null) {
assert locationHint.isSplitParent() : "ony split parents are valid hint registers";
if (locationHint.location != null && isRegister(locationHint.location)) {
return locationHint;
} else if (!locationHint.splitChildren.isEmpty()) {
int len = locationHint.splitChildren.size();
for (int i = 0; i < len; i++) {
Interval interval = locationHint.splitChildren.get(i);
if (interval.location != null && isRegister(interval.location)) {
return interval;
}
}
}
}
return null;
}
Interval getSplitChildAtOpId(int opId, LIRInstruction.OperandMode mode, LinearScan allocator) {
assert isSplitParent() : "can only be called for split parents";
assert opId >= 0 : "invalid opId (method cannot be called for spill moves)";
if (splitChildren.isEmpty()) {
assert this.covers(opId, mode) : this + " does not cover " + opId;
return this;
} else {
Interval result = null;
int len = splitChildren.size();
int toOffset = (mode == LIRInstruction.OperandMode.DEF ? 0 : 1);
int i;
for (i = 0; i < len; i++) {
Interval cur = splitChildren.get(i);
if (cur.from() <= opId && opId < cur.to() + toOffset) {
if (i > 0) {
Util.atPutGrow(splitChildren, i, splitChildren.get(0), null);
Util.atPutGrow(splitChildren, 0, cur, null);
}
result = cur;
break;
}
}
assert checkSplitChild(result, opId, allocator, toOffset, mode);
return result;
}
}
private boolean checkSplitChild(Interval result, int opId, LinearScan allocator, int toOffset, LIRInstruction.OperandMode mode) {
if (result == null) {
StringBuilder msg = new StringBuilder(this.toString()).append(" has no child at ").append(opId);
if (!splitChildren.isEmpty()) {
Interval firstChild = splitChildren.get(0);
Interval lastChild = splitChildren.get(splitChildren.size() - 1);
msg.append(" (first = ").append(firstChild).append(", last = ").append(lastChild).append(")");
}
throw new GraalError("Linear Scan Error: %s", msg);
}
if (!splitChildren.isEmpty()) {
for (Interval interval : splitChildren) {
if (interval != result && interval.from() <= opId && opId < interval.to() + toOffset) {
throw new GraalError("two valid result intervals found for opId %d: %d and %d\n%s\n", opId, result.operandNumber, interval.operandNumber,
result.logString(allocator), interval.logString(allocator));
}
}
}
assert result.covers(opId, mode) : "opId not covered by interval";
return true;
}
Interval getIntervalCoveringOpId(int opId) {
assert opId >= 0 : "invalid opId";
assert opId < to() : "can only look into the past";
if (opId >= from()) {
return this;
}
Interval parent = splitParent();
Interval result = null;
assert !parent.splitChildren.isEmpty() : "no split children available";
int len = parent.splitChildren.size();
for (int i = len - 1; i >= 0; i--) {
Interval cur = parent.splitChildren.get(i);
if (cur.from() <= opId && opId < cur.to()) {
assert result == null : "covered by multiple split children " + result + " and " + cur;
result = cur;
}
}
return result;
}
Interval getSplitChildBeforeOpId(int opId) {
assert opId >= 0 : "invalid opId";
Interval parent = splitParent();
Interval result = null;
assert !parent.splitChildren.isEmpty() : "no split children available";
int len = parent.splitChildren.size();
for (int i = len - 1; i >= 0; i--) {
Interval cur = parent.splitChildren.get(i);
if (cur.to() <= opId && (result == null || result.to() < cur.to())) {
result = cur;
}
}
assert result != null : "no split child found";
return result;
}
boolean splitChildCovers(int opId, LIRInstruction.OperandMode mode) {
assert isSplitParent() : "can only be called for split parents";
assert opId >= 0 : "invalid opId (method can not be called for spill moves)";
if (splitChildren.isEmpty()) {
return covers(opId, mode);
} else {
int len = splitChildren.size();
for (int i = 0; i < len; i++) {
Interval cur = splitChildren.get(i);
if (cur.covers(opId, mode)) {
return true;
}
}
return false;
}
}
private RegisterPriority adaptPriority(RegisterPriority priority) {
if (priority == RegisterPriority.ShouldHaveRegister && canMaterialize()) {
return RegisterPriority.MustHaveRegister;
}
return priority;
}
int firstUsage(RegisterPriority minRegisterPriority) {
assert isVariable(operand) : "cannot access use positions for fixed intervals";
for (int i = usePosList.size() - 1; i >= 0; --i) {
RegisterPriority registerPriority = adaptPriority(usePosList.registerPriority(i));
if (registerPriority.greaterEqual(minRegisterPriority)) {
return usePosList.usePos(i);
}
}
return Integer.MAX_VALUE;
}
int nextUsage(RegisterPriority minRegisterPriority, int from) {
assert isVariable(operand) : "cannot access use positions for fixed intervals";
for (int i = usePosList.size() - 1; i >= 0; --i) {
int usePos = usePosList.usePos(i);
if (usePos >= from && adaptPriority(usePosList.registerPriority(i)).greaterEqual(minRegisterPriority)) {
return usePos;
}
}
return Integer.MAX_VALUE;
}
int nextUsageExact(RegisterPriority exactRegisterPriority, int from) {
assert isVariable(operand) : "cannot access use positions for fixed intervals";
for (int i = usePosList.size() - 1; i >= 0; --i) {
int usePos = usePosList.usePos(i);
if (usePos >= from && adaptPriority(usePosList.registerPriority(i)) == exactRegisterPriority) {
return usePos;
}
}
return Integer.MAX_VALUE;
}
int previousUsage(RegisterPriority minRegisterPriority, int from) {
assert isVariable(operand) : "cannot access use positions for fixed intervals";
int prev = -1;
for (int i = usePosList.size() - 1; i >= 0; --i) {
int usePos = usePosList.usePos(i);
if (usePos > from) {
return prev;
}
if (adaptPriority(usePosList.registerPriority(i)).greaterEqual(minRegisterPriority)) {
prev = usePos;
}
}
return prev;
}
public void addUsePos(int pos, RegisterPriority registerPriority, boolean detailedAsserts) {
assert covers(pos, LIRInstruction.OperandMode.USE) : String.format("use position %d not covered by live range of interval %s", pos, this);
if (registerPriority != RegisterPriority.None && isVariable(operand)) {
if (detailedAsserts) {
for (int i = 0; i < usePosList.size(); i++) {
assert pos <= usePosList.usePos(i) : "already added a use-position with lower position";
if (i > 0) {
assert usePosList.usePos(i) < usePosList.usePos(i - 1) : "not sorted descending";
}
}
}
int len = usePosList.size();
if (len == 0 || usePosList.usePos(len - 1) > pos) {
usePosList.add(pos, registerPriority);
} else if (usePosList.registerPriority(len - 1).lessThan(registerPriority)) {
assert usePosList.usePos(len - 1) == pos : "list not sorted correctly";
usePosList.setRegisterPriority(len - 1, registerPriority);
}
}
}
public void addRange(int from, int to) {
assert from < to : "invalid range";
assert first().isEndMarker() || to < first().next.from : "not inserting at begin of interval";
assert from <= first().to : "not inserting at begin of interval";
if (first.from <= to) {
assert !first.isEndMarker();
first.from = Math.min(from, first().from);
first.to = Math.max(to, first().to);
} else {
first = new Range(from, to, first());
}
}
Interval newSplitChild(LinearScan allocator) {
Interval parent = splitParent();
Interval result = allocator.createDerivedInterval(parent);
result.setKind(kind());
result.splitParent = parent;
result.setLocationHint(parent);
if (parent.splitChildren.isEmpty()) {
assert isSplitParent() : "list must be initialized at first split";
parent.splitChildren = new ArrayList<>(4);
parent.splitChildren.add(this);
}
parent.splitChildren.add(result);
return result;
}
Interval split(int splitPos, LinearScan allocator) {
assert isVariable(operand) : "cannot split fixed intervals";
Interval result = newSplitChild(allocator);
Range prev = null;
Range cur = first;
while (!cur.isEndMarker() && cur.to <= splitPos) {
prev = cur;
cur = cur.next;
}
assert !cur.isEndMarker() : "split interval after end of last range";
if (cur.from < splitPos) {
result.first = new Range(splitPos, cur.to, cur.next);
cur.to = splitPos;
cur.next = allocator.rangeEndMarker;
} else {
assert prev != null : "split before start of first range";
result.first = cur;
prev.next = allocator.rangeEndMarker;
}
result.current = result.first;
cachedTo = -1;
result.usePosList = usePosList.splitAt(splitPos);
if (Assertions.detailedAssertionsEnabled(allocator.getOptions())) {
for (int i = 0; i < usePosList.size(); i++) {
assert usePosList.usePos(i) < splitPos;
}
for (int i = 0; i < result.usePosList.size(); i++) {
assert result.usePosList.usePos(i) >= splitPos;
}
}
return result;
}
Interval splitFromStart(int splitPos, LinearScan allocator) {
assert isVariable(operand) : "cannot split fixed intervals";
assert splitPos > from() && splitPos < to() : "can only split inside interval";
assert splitPos > first.from && splitPos <= first.to : "can only split inside first range";
assert firstUsage(RegisterPriority.None) > splitPos : "can not split when use positions are present";
Interval result = newSplitChild(allocator);
result.addRange(first.from, splitPos);