src/jdk.internal.vm.compiler/share/classes/org.graalvm.compiler.lir/src/org/graalvm/compiler/lir/alloc/lsra/LinearScan.java
Index
Unified diffs
Context diffs
Sdiffs
Patch
New
Old
Previous File
Next File
hotspot Cdiff src/jdk.internal.vm.compiler/share/classes/org.graalvm.compiler.lir/src/org/graalvm/compiler/lir/alloc/lsra/LinearScan.java
src/jdk.internal.vm.compiler/share/classes/org.graalvm.compiler.lir/src/org/graalvm/compiler/lir/alloc/lsra/LinearScan.java
Print this page
*** 20,42 ****
* or visit www.oracle.com if you need additional information or have any
* questions.
*/
package org.graalvm.compiler.lir.alloc.lsra;
- import static org.graalvm.compiler.core.common.GraalOptions.DetailedAsserts;
- import static org.graalvm.compiler.lir.LIRValueUtil.isVariable;
- import static org.graalvm.compiler.lir.phases.LIRPhase.Options.LIROptimization;
import static jdk.vm.ci.code.CodeUtil.isEven;
import static jdk.vm.ci.code.ValueUtil.asRegister;
import static jdk.vm.ci.code.ValueUtil.isIllegal;
import static jdk.vm.ci.code.ValueUtil.isLegal;
import static jdk.vm.ci.code.ValueUtil.isRegister;
import java.util.Arrays;
import java.util.BitSet;
import java.util.EnumSet;
- import java.util.List;
import org.graalvm.compiler.core.common.LIRKind;
import org.graalvm.compiler.core.common.alloc.RegisterAllocationConfig;
import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
import org.graalvm.compiler.core.common.cfg.BlockMap;
--- 20,42 ----
* or visit www.oracle.com if you need additional information or have any
* questions.
*/
package org.graalvm.compiler.lir.alloc.lsra;
import static jdk.vm.ci.code.CodeUtil.isEven;
import static jdk.vm.ci.code.ValueUtil.asRegister;
import static jdk.vm.ci.code.ValueUtil.isIllegal;
import static jdk.vm.ci.code.ValueUtil.isLegal;
import static jdk.vm.ci.code.ValueUtil.isRegister;
+ import static org.graalvm.compiler.core.common.GraalOptions.DetailedAsserts;
+ import static org.graalvm.compiler.lir.LIRValueUtil.isVariable;
+ import static org.graalvm.compiler.lir.phases.LIRPhase.Options.LIROptimization;
+ import java.util.ArrayList;
import java.util.Arrays;
import java.util.BitSet;
import java.util.EnumSet;
import org.graalvm.compiler.core.common.LIRKind;
import org.graalvm.compiler.core.common.alloc.RegisterAllocationConfig;
import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
import org.graalvm.compiler.core.common.cfg.BlockMap;
*** 54,67 ****
import org.graalvm.compiler.lir.alloc.lsra.Interval.RegisterBinding;
import org.graalvm.compiler.lir.framemap.FrameMapBuilder;
import org.graalvm.compiler.lir.gen.LIRGenerationResult;
import org.graalvm.compiler.lir.gen.LIRGeneratorTool.MoveFactory;
import org.graalvm.compiler.lir.phases.AllocationPhase.AllocationContext;
! import org.graalvm.compiler.options.NestedBooleanOptionValue;
import org.graalvm.compiler.options.Option;
import org.graalvm.compiler.options.OptionType;
! import org.graalvm.compiler.options.OptionValue;
import jdk.vm.ci.code.Register;
import jdk.vm.ci.code.RegisterArray;
import jdk.vm.ci.code.RegisterAttributes;
import jdk.vm.ci.code.RegisterValue;
--- 54,69 ----
import org.graalvm.compiler.lir.alloc.lsra.Interval.RegisterBinding;
import org.graalvm.compiler.lir.framemap.FrameMapBuilder;
import org.graalvm.compiler.lir.gen.LIRGenerationResult;
import org.graalvm.compiler.lir.gen.LIRGeneratorTool.MoveFactory;
import org.graalvm.compiler.lir.phases.AllocationPhase.AllocationContext;
! import org.graalvm.compiler.options.NestedBooleanOptionKey;
import org.graalvm.compiler.options.Option;
+ import org.graalvm.compiler.options.OptionKey;
import org.graalvm.compiler.options.OptionType;
! import org.graalvm.compiler.options.OptionValues;
! import org.graalvm.util.Pair;
import jdk.vm.ci.code.Register;
import jdk.vm.ci.code.RegisterArray;
import jdk.vm.ci.code.RegisterAttributes;
import jdk.vm.ci.code.RegisterValue;
*** 77,87 ****
public class LinearScan {
public static class Options {
// @formatter:off
@Option(help = "Enable spill position optimization", type = OptionType.Debug)
! public static final OptionValue<Boolean> LIROptLSRAOptimizeSpillPosition = new NestedBooleanOptionValue(LIROptimization, true);
// @formatter:on
}
public static class BlockData {
--- 79,89 ----
public class LinearScan {
public static class Options {
// @formatter:off
@Option(help = "Enable spill position optimization", type = OptionType.Debug)
! public static final OptionKey<Boolean> LIROptLSRAOptimizeSpillPosition = new NestedBooleanOptionKey(LIROptimization, true);
// @formatter:on
}
public static class BlockData {
*** 175,184 ****
--- 177,193 ----
* Number of variables.
*/
private int numVariables;
private final boolean neverSpillConstants;
+ /**
+ * Sentinel interval to denote the end of an interval list.
+ */
+ protected final Interval intervalEndMarker;
+ public final Range rangeEndMarker;
+ public final boolean detailedAsserts;
+
protected LinearScan(TargetDescription target, LIRGenerationResult res, MoveFactory spillMoveFactory, RegisterAllocationConfig regAllocConfig, AbstractBlockBase<?>[] sortedBlocks,
boolean neverSpillConstants) {
this.ir = res.getLIR();
this.moveFactory = spillMoveFactory;
this.frameMapBuilder = res.getFrameMapBuilder();
*** 189,208 ****
this.registers = target.arch.getRegisters();
this.firstVariableNumber = getRegisters().size();
this.numVariables = ir.numVariables();
this.blockData = new BlockMap<>(ir.getControlFlowGraph());
this.neverSpillConstants = neverSpillConstants;
}
public int getFirstLirInstructionId(AbstractBlockBase<?> block) {
int result = ir.getLIRforBlock(block).get(0).id();
assert result >= 0;
return result;
}
public int getLastLirInstructionId(AbstractBlockBase<?> block) {
! List<LIRInstruction> instructions = ir.getLIRforBlock(block);
int result = instructions.get(instructions.size() - 1).id();
assert result >= 0;
return result;
}
--- 198,229 ----
this.registers = target.arch.getRegisters();
this.firstVariableNumber = getRegisters().size();
this.numVariables = ir.numVariables();
this.blockData = new BlockMap<>(ir.getControlFlowGraph());
this.neverSpillConstants = neverSpillConstants;
+ this.rangeEndMarker = new Range(Integer.MAX_VALUE, Integer.MAX_VALUE, null);
+ this.intervalEndMarker = new Interval(Value.ILLEGAL, Interval.END_MARKER_OPERAND_NUMBER, null, rangeEndMarker);
+ this.intervalEndMarker.next = intervalEndMarker;
+ this.detailedAsserts = DetailedAsserts.getValue(ir.getOptions());
+ }
+
+ public Interval intervalEndMarker() {
+ return intervalEndMarker;
+ }
+
+ public OptionValues getOptions() {
+ return ir.getOptions();
}
public int getFirstLirInstructionId(AbstractBlockBase<?> block) {
int result = ir.getLIRforBlock(block).get(0).id();
assert result >= 0;
return result;
}
public int getLastLirInstructionId(AbstractBlockBase<?> block) {
! ArrayList<LIRInstruction> instructions = ir.getLIRforBlock(block);
int result = instructions.get(instructions.size() - 1).id();
assert result >= 0;
return result;
}
*** 324,334 ****
* @return the created interval
*/
Interval createInterval(AllocatableValue operand) {
assert isLegal(operand);
int operandNumber = operandNumber(operand);
! Interval interval = new Interval(operand, operandNumber);
assert operandNumber < intervalsSize;
assert intervals[operandNumber] == null;
intervals[operandNumber] = interval;
return interval;
}
--- 345,355 ----
* @return the created interval
*/
Interval createInterval(AllocatableValue operand) {
assert isLegal(operand);
int operandNumber = operandNumber(operand);
! Interval interval = new Interval(operand, operandNumber, intervalEndMarker, rangeEndMarker);
assert operandNumber < intervalsSize;
assert intervals[operandNumber] == null;
intervals[operandNumber] = interval;
return interval;
}
*** 500,514 ****
newFirst = interval;
}
return newFirst;
}
! Interval.Pair createUnhandledLists(IntervalPredicate isList1, IntervalPredicate isList2) {
assert isSorted(sortedIntervals) : "interval list is not sorted";
! Interval list1 = Interval.EndMarker;
! Interval list2 = Interval.EndMarker;
Interval list1Prev = null;
Interval list2Prev = null;
Interval v;
--- 521,535 ----
newFirst = interval;
}
return newFirst;
}
! Pair<Interval, Interval> createUnhandledLists(IntervalPredicate isList1, IntervalPredicate isList2) {
assert isSorted(sortedIntervals) : "interval list is not sorted";
! Interval list1 = intervalEndMarker;
! Interval list2 = intervalEndMarker;
Interval list1Prev = null;
Interval list2Prev = null;
Interval v;
*** 527,546 ****
list2Prev = v;
}
}
if (list1Prev != null) {
! list1Prev.next = Interval.EndMarker;
}
if (list2Prev != null) {
! list2Prev.next = Interval.EndMarker;
}
! assert list1Prev == null || list1Prev.next == Interval.EndMarker : "linear list ends not with sentinel";
! assert list2Prev == null || list2Prev.next == Interval.EndMarker : "linear list ends not with sentinel";
! return new Interval.Pair(list1, list2);
}
protected void sortIntervalsBeforeAllocation() {
int sortedLen = 0;
for (Interval interval : intervals) {
--- 548,567 ----
list2Prev = v;
}
}
if (list1Prev != null) {
! list1Prev.next = intervalEndMarker;
}
if (list2Prev != null) {
! list2Prev.next = intervalEndMarker;
}
! assert list1Prev == null || list1Prev.next.isEndMarker() : "linear list ends not with sentinel";
! assert list2Prev == null || list2Prev.next.isEndMarker() : "linear list ends not with sentinel";
! return Pair.create(list1, list2);
}
protected void sortIntervalsBeforeAllocation() {
int sortedLen = 0;
for (Interval interval : intervals) {
*** 646,685 ****
boolean isCallerSave(Value operand) {
return attributes(asRegister(operand)).isCallerSave();
}
@SuppressWarnings("try")
! protected void allocate(TargetDescription target, LIRGenerationResult lirGenRes, MoveFactory spillMoveFactory, RegisterAllocationConfig registerAllocationConfig) {
!
/*
* This is the point to enable debug logging for the whole register allocation.
*/
try (Indent indent = Debug.logAndIndent("LinearScan allocate")) {
- AllocationContext context = new AllocationContext(spillMoveFactory, registerAllocationConfig);
createLifetimeAnalysisPhase().apply(target, lirGenRes, context);
try (Scope s = Debug.scope("AfterLifetimeAnalysis", (Object) intervals)) {
sortIntervalsBeforeAllocation();
createRegisterAllocationPhase().apply(target, lirGenRes, context);
! if (LinearScan.Options.LIROptLSRAOptimizeSpillPosition.getValue()) {
createOptimizeSpillPositionPhase().apply(target, lirGenRes, context);
}
createResolveDataFlowPhase().apply(target, lirGenRes, context);
sortIntervalsAfterAllocation();
! if (DetailedAsserts.getValue()) {
verify();
}
beforeSpillMoveElimination();
createSpillMoveEliminationPhase().apply(target, lirGenRes, context);
createAssignLocationsPhase().apply(target, lirGenRes, context);
! if (DetailedAsserts.getValue()) {
verifyIntervals();
}
} catch (Throwable e) {
throw Debug.handle(e);
}
--- 667,704 ----
boolean isCallerSave(Value operand) {
return attributes(asRegister(operand)).isCallerSave();
}
@SuppressWarnings("try")
! protected void allocate(TargetDescription target, LIRGenerationResult lirGenRes, AllocationContext context) {
/*
* This is the point to enable debug logging for the whole register allocation.
*/
try (Indent indent = Debug.logAndIndent("LinearScan allocate")) {
createLifetimeAnalysisPhase().apply(target, lirGenRes, context);
try (Scope s = Debug.scope("AfterLifetimeAnalysis", (Object) intervals)) {
sortIntervalsBeforeAllocation();
createRegisterAllocationPhase().apply(target, lirGenRes, context);
! if (LinearScan.Options.LIROptLSRAOptimizeSpillPosition.getValue(getOptions())) {
createOptimizeSpillPositionPhase().apply(target, lirGenRes, context);
}
createResolveDataFlowPhase().apply(target, lirGenRes, context);
sortIntervalsAfterAllocation();
! if (detailedAsserts) {
verify();
}
beforeSpillMoveElimination();
createSpillMoveEliminationPhase().apply(target, lirGenRes, context);
createAssignLocationsPhase().apply(target, lirGenRes, context);
! if (detailedAsserts) {
verifyIntervals();
}
} catch (Throwable e) {
throw Debug.handle(e);
}
*** 787,803 ****
Debug.log("Interval %d has no register assigned", i1.operandNumber);
Debug.log(i1.logString(this));
throw new GraalError("");
}
! if (i1.first() == Range.EndMarker) {
Debug.log("Interval %d has no Range", i1.operandNumber);
Debug.log(i1.logString(this));
throw new GraalError("");
}
! for (Range r = i1.first(); r != Range.EndMarker; r = r.next) {
if (r.from >= r.to) {
Debug.log("Interval %d has zero length range", i1.operandNumber);
Debug.log(i1.logString(this));
throw new GraalError("");
}
--- 806,822 ----
Debug.log("Interval %d has no register assigned", i1.operandNumber);
Debug.log(i1.logString(this));
throw new GraalError("");
}
! if (i1.first().isEndMarker()) {
Debug.log("Interval %d has no Range", i1.operandNumber);
Debug.log(i1.logString(this));
throw new GraalError("");
}
! for (Range r = i1.first(); !r.isEndMarker(); r = r.next) {
if (r.from >= r.to) {
Debug.log("Interval %d has zero length range", i1.operandNumber);
Debug.log(i1.logString(this));
throw new GraalError("");
}
*** 848,866 ****
try (Indent indent = Debug.logAndIndent("verifying that no oops are in fixed intervals *")) {
CheckConsumer checkConsumer = new CheckConsumer();
Interval fixedIntervals;
Interval otherIntervals;
! fixedIntervals = createUnhandledLists(IS_PRECOLORED_INTERVAL, null).first;
// to ensure a walking until the last instruction id, add a dummy interval
// with a high operation id
! otherIntervals = new Interval(Value.ILLEGAL, -1);
otherIntervals.addRange(Integer.MAX_VALUE - 2, Integer.MAX_VALUE - 1);
IntervalWalker iw = new IntervalWalker(this, fixedIntervals, otherIntervals);
for (AbstractBlockBase<?> block : sortedBlocks) {
! List<LIRInstruction> instructions = ir.getLIRforBlock(block);
for (int j = 0; j < instructions.size(); j++) {
LIRInstruction op = instructions.get(j);
if (op.hasState()) {
--- 867,885 ----
try (Indent indent = Debug.logAndIndent("verifying that no oops are in fixed intervals *")) {
CheckConsumer checkConsumer = new CheckConsumer();
Interval fixedIntervals;
Interval otherIntervals;
! fixedIntervals = createUnhandledLists(IS_PRECOLORED_INTERVAL, null).getLeft();
// to ensure a walking until the last instruction id, add a dummy interval
// with a high operation id
! otherIntervals = new Interval(Value.ILLEGAL, -1, intervalEndMarker, rangeEndMarker);
otherIntervals.addRange(Integer.MAX_VALUE - 2, Integer.MAX_VALUE - 1);
IntervalWalker iw = new IntervalWalker(this, fixedIntervals, otherIntervals);
for (AbstractBlockBase<?> block : sortedBlocks) {
! ArrayList<LIRInstruction> instructions = ir.getLIRforBlock(block);
for (int j = 0; j < instructions.size(); j++) {
LIRInstruction op = instructions.get(j);
if (op.hasState()) {
*** 870,880 ****
/*
* Make sure none of the fixed registers is live across an oopmap since we
* can't handle that correctly.
*/
if (checkLive) {
! for (Interval interval = iw.activeLists.get(RegisterBinding.Fixed); interval != Interval.EndMarker; interval = interval.next) {
if (interval.currentTo() > op.id() + 1) {
/*
* This interval is live out of this op so make sure that this
* interval represents some value that's referenced by this op
* either as an input or output.
--- 889,899 ----
/*
* Make sure none of the fixed registers is live across an oopmap since we
* can't handle that correctly.
*/
if (checkLive) {
! for (Interval interval = iw.activeLists.get(RegisterBinding.Fixed); !interval.isEndMarker(); interval = interval.next) {
if (interval.currentTo() > op.id() + 1) {
/*
* This interval is live out of this op so make sure that this
* interval represents some value that's referenced by this op
* either as an input or output.
src/jdk.internal.vm.compiler/share/classes/org.graalvm.compiler.lir/src/org/graalvm/compiler/lir/alloc/lsra/LinearScan.java
Index
Unified diffs
Context diffs
Sdiffs
Patch
New
Old
Previous File
Next File