src/jdk.internal.vm.compiler/share/classes/org.graalvm.compiler.lir/src/org/graalvm/compiler/lir/alloc/trace/lsra/TraceLinearScanLifetimeAnalysisPhase.java
Index
Unified diffs
Context diffs
Sdiffs
Patch
New
Old
Previous File
Next File
*** old/src/jdk.internal.vm.compiler/share/classes/org.graalvm.compiler.lir/src/org/graalvm/compiler/lir/alloc/trace/lsra/TraceLinearScanLifetimeAnalysisPhase.java Mon Mar 20 17:39:59 2017
--- new/src/jdk.internal.vm.compiler/share/classes/org.graalvm.compiler.lir/src/org/graalvm/compiler/lir/alloc/trace/lsra/TraceLinearScanLifetimeAnalysisPhase.java Mon Mar 20 17:39:59 2017
*** 20,45 ****
--- 20,44 ----
* or visit www.oracle.com if you need additional information or have any
* questions.
*/
package org.graalvm.compiler.lir.alloc.trace.lsra;
+ import static jdk.vm.ci.code.ValueUtil.asRegisterValue;
+ import static jdk.vm.ci.code.ValueUtil.asStackSlot;
+ import static jdk.vm.ci.code.ValueUtil.isRegister;
+ import static jdk.vm.ci.code.ValueUtil.isStackSlot;
import static org.graalvm.compiler.lir.LIRValueUtil.asVariable;
import static org.graalvm.compiler.lir.LIRValueUtil.isStackSlotValue;
import static org.graalvm.compiler.lir.LIRValueUtil.isVariable;
import static org.graalvm.compiler.lir.alloc.trace.TraceRegisterAllocationPhase.Options.TraceRAshareSpillInformation;
import static org.graalvm.compiler.lir.alloc.trace.TraceRegisterAllocationPhase.Options.TraceRAuseInterTraceHints;
import static org.graalvm.compiler.lir.alloc.trace.TraceUtil.asShadowedRegisterValue;
import static org.graalvm.compiler.lir.alloc.trace.TraceUtil.isShadowedRegisterValue;
import static org.graalvm.compiler.lir.alloc.trace.lsra.TraceLinearScanPhase.isVariableOrRegister;
import static jdk.vm.ci.code.ValueUtil.asRegisterValue;
import static jdk.vm.ci.code.ValueUtil.asStackSlot;
import static jdk.vm.ci.code.ValueUtil.isRegister;
import static jdk.vm.ci.code.ValueUtil.isStackSlot;
+ import java.util.ArrayList;
import java.util.EnumSet;
import java.util.List;
import java.util.ListIterator;
import org.graalvm.compiler.core.common.LIRKind;
import org.graalvm.compiler.core.common.alloc.Trace;
import org.graalvm.compiler.core.common.alloc.TraceBuilderResult;
import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
*** 51,73 ****
--- 50,73 ----
import org.graalvm.compiler.lir.LIR;
import org.graalvm.compiler.lir.LIRInstruction;
import org.graalvm.compiler.lir.LIRInstruction.OperandFlag;
import org.graalvm.compiler.lir.LIRInstruction.OperandMode;
import org.graalvm.compiler.lir.LIRValueUtil;
! import org.graalvm.compiler.lir.StandardOp.BlockEndOp;
! import org.graalvm.compiler.lir.StandardOp.JumpOp;
import org.graalvm.compiler.lir.StandardOp.LabelOp;
import org.graalvm.compiler.lir.StandardOp.LoadConstantOp;
import org.graalvm.compiler.lir.StandardOp.ValueMoveOp;
import org.graalvm.compiler.lir.ValueProcedure;
import org.graalvm.compiler.lir.Variable;
+ import org.graalvm.compiler.lir.alloc.trace.GlobalLivenessInfo;
import org.graalvm.compiler.lir.alloc.trace.ShadowedRegisterValue;
import org.graalvm.compiler.lir.alloc.trace.lsra.TraceInterval.RegisterPriority;
import org.graalvm.compiler.lir.alloc.trace.lsra.TraceInterval.SpillState;
import org.graalvm.compiler.lir.alloc.trace.lsra.TraceLinearScanPhase.TraceLinearScan;
import org.graalvm.compiler.lir.gen.LIRGenerationResult;
import org.graalvm.compiler.lir.gen.LIRGeneratorTool.MoveFactory;
! import org.graalvm.compiler.lir.ssi.SSIUtil;
! import org.graalvm.compiler.lir.ssa.SSAUtil;
import jdk.vm.ci.code.Register;
import jdk.vm.ci.code.RegisterArray;
import jdk.vm.ci.code.RegisterValue;
import jdk.vm.ci.code.TargetDescription;
*** 110,125 ****
--- 110,121 ----
public void analyze() {
countInstructions();
buildIntervals();
}
! private boolean sameTrace(AbstractBlockBase<?> a, AbstractBlockBase<?> b) {
! return traceBuilderResult.getTraceForBlock(b) == traceBuilderResult.getTraceForBlock(a);
}
private boolean isAllocatedOrCurrent(AbstractBlockBase<?> currentBlock, AbstractBlockBase<?> other) {
return traceBuilderResult.getTraceForBlock(other).getId() <= traceBuilderResult.getTraceForBlock(currentBlock).getId();
! private boolean isAllocated(AbstractBlockBase<?> currentBlock, AbstractBlockBase<?> other) {
! return traceBuilderResult.getTraceForBlock(other).getId() < traceBuilderResult.getTraceForBlock(currentBlock).getId();
}
/**
* Count instructions in all blocks. The numbering follows the
* {@linkplain TraceLinearScan#sortedBlocks() register allocation order}.
*** 261,271 ****
--- 257,267 ----
if (Debug.isLogEnabled()) {
Debug.log("add fixed def: %s, at %d", interval, defPos);
}
}
! private void addVariableDef(Variable operand, LIRInstruction op, RegisterPriority registerPriority) {
! private TraceInterval addVariableDef(Variable operand, LIRInstruction op, RegisterPriority registerPriority) {
int defPos = op.id();
TraceInterval interval = allocator.getOrCreateInterval(operand);
if (interval.isEmpty()) {
*** 296,305 ****
--- 292,302 ----
interval.addMaterializationValue(getMaterializedValue(op, operand, interval, allocator.neverSpillConstants(), allocator.getSpillMoveFactory()));
if (Debug.isLogEnabled()) {
Debug.log("add def: %s defPos %d (%s)", interval, defPos, registerPriority.name());
}
+ return interval;
}
private void addTemp(AllocatableValue operand, int tempPos, RegisterPriority registerPriority) {
if (!allocator.isProcessed(operand)) {
return;
*** 479,505 ****
--- 476,502 ----
RegisterArray callerSaveRegs = getCallerSavedRegisters();
int instructionIndex = numInstructions;
// iterate all blocks in reverse order
AbstractBlockBase<?>[] blocks = sortedBlocks();
! for (int i = blocks.length - 1; i >= 0; i--) {
! final AbstractBlockBase<?> block = blocks[i];
! for (int blockId = blocks.length - 1; blockId >= 0; blockId--) {
! final AbstractBlockBase<?> block = blocks[blockId];
try (Indent indent2 = Debug.logAndIndent("handle block %d", block.getId())) {
+ handleBlockEnd(block, (instructionIndex - 1) << 1);
/*
* Iterate all instructions of the block in reverse order. definitions of
* intervals are processed before uses.
*/
! ArrayList<LIRInstruction> instructions = getLIR().getLIRforBlock(block);
ListIterator<LIRInstruction> instIt = instructions.listIterator(instructions.size());
while (instIt.hasPrevious()) {
final LIRInstruction op = instIt.previous();
+ for (int instIdx = instructions.size() - 1; instIdx >= 1; instIdx--) {
+ final LIRInstruction op = instructions.get(instIdx);
// number instruction
instructionIndex--;
final int opId = instructionIndex << 1;
numberInstruction(block, op, instructionIndex);
+ final int opId = op.id();
try (Indent indent3 = Debug.logAndIndent("handle inst %d: %s", opId, op)) {
/*
* Add a temp range for each register if operation destroys
*** 529,553 ****
--- 526,556 ----
*/
op.visitEachState(stateProc);
}
} // end of instruction iteration
+ // number label instruction
+ instructionIndex--;
+ numberInstruction(block, instructions.get(0), instructionIndex);
+ AbstractBlockBase<?> pred = blockId == 0 ? null : blocks[blockId - 1];
+ handleBlockBegin(block, pred);
}
if (Debug.isDumpEnabled(DUMP_DURING_ANALYSIS_LEVEL)) {
allocator.printIntervals("After Block " + block);
}
} // end of block iteration
assert instructionIndex == 0 : "not at start?" + instructionIndex;
+ handleTraceBegin(blocks[0]);
! // fix spill state for phi/sigma intervals
! // fix spill state for phi/incoming intervals
for (TraceInterval interval : allocator.intervals()) {
if (interval != null && interval.spillState().equals(SpillState.NoDefinitionFound) && interval.spillDefinitionPos() != -1) {
! // there was a definition in a phi/sigma
! // there was a definition in a phi/incoming
interval.setSpillState(SpillState.NoSpillStore);
}
}
! if (TraceRAuseInterTraceHints.getValue(allocator.getLIR().getOptions())) {
addInterTraceHints();
}
for (FixedInterval interval1 : allocator.fixedIntervals()) {
if (interval1 != null) {
/* We use [-1, 0] to avoid intersection with incoming values. */
*** 555,564 ****
--- 558,613 ----
}
}
}
}
+ private void handleTraceBegin(AbstractBlockBase<?> block) {
+ LIRInstruction op = getLIR().getLIRforBlock(block).get(0);
+ GlobalLivenessInfo livenessInfo = allocator.getGlobalLivenessInfo();
+ for (int varNum : livenessInfo.getBlockIn(block)) {
+ if (isAliveAtBlockBegin(varNum)) {
+ addVariableDef(livenessInfo.getVariable(varNum), op, RegisterPriority.None);
+ }
+ }
+ }
+
+ private boolean isAliveAtBlockBegin(int varNum) {
+ return allocator.intervalFor(varNum) != null;
+ }
+
+ private void handleBlockBegin(AbstractBlockBase<?> block, AbstractBlockBase<?> pred) {
+ if (SSAUtil.isMerge(block)) {
+ // handle phis
+ // method parameters are fixed later on (see end of #buildIntervals)
+ LabelOp label = SSAUtil.phiIn(getLIR(), block);
+ JumpOp jump = pred == null ? null : SSAUtil.phiOut(getLIR(), pred);
+ for (int i = 0; i < label.getPhiSize(); i++) {
+ Variable var = asVariable(label.getIncomingValue(i));
+ TraceInterval toInterval = addVariableDef(var, label, RegisterPriority.ShouldHaveRegister);
+ // set hint for phis
+ if (jump != null) {
+ Value out = jump.getOutgoingValue(i);
+ if (isVariable(out)) {
+ TraceInterval fromInterval = allocator.getOrCreateInterval(asVariable(out));
+ toInterval.setLocationHint(fromInterval);
+ }
+ }
+ }
+ }
+ }
+
+ private void handleBlockEnd(AbstractBlockBase<?> block, int opId) {
+ // always alive until the end of the block
+ int aliveOpId = opId + 1;
+ GlobalLivenessInfo livenessInfo = allocator.getGlobalLivenessInfo();
+ for (int varNum : livenessInfo.getBlockOut(block)) {
+ if (allocator.intervalFor(varNum) == null) {
+ addVariableUse(livenessInfo.getVariable(varNum), 0, aliveOpId, RegisterPriority.None);
+ }
+ }
+ }
+
private void numberInstruction(AbstractBlockBase<?> block, LIRInstruction op, int index) {
int opId = index << 1;
assert op.id() == -1 || op.id() == opId : "must match";
op.setId(opId);
allocator.putOpIdMaps(index, op, block);
*** 566,611 ****
--- 615,668 ----
}
@SuppressWarnings("try")
private void addInterTraceHints() {
try (Scope s = Debug.scope("InterTraceHints", allocator)) {
// set hints for phi/sigma intervals
+ GlobalLivenessInfo livenessInfo = allocator.getGlobalLivenessInfo();
+ // set hints for phi/incoming intervals
for (AbstractBlockBase<?> block : sortedBlocks()) {
! LabelOp label = SSIUtil.incoming(getLIR(), block);
! LabelOp label = (LabelOp) getLIR().getLIRforBlock(block).get(0);
for (AbstractBlockBase<?> pred : block.getPredecessors()) {
if (isAllocatedOrCurrent(block, pred)) {
BlockEndOp outgoing = SSIUtil.outgoing(getLIR(), pred);
// do not look at phi variables as they are not same value!
for (int i = outgoing.getPhiSize(); i < outgoing.getOutgoingSize(); i++) {
Value toValue = label.getIncomingValue(i);
assert !isShadowedRegisterValue(toValue) : "Shadowed Registers are not allowed here: " + toValue;
if (isVariable(toValue)) {
Value fromValue = outgoing.getOutgoingValue(i);
assert sameTrace(block, pred) || !isVariable(fromValue) : "Unallocated variable: " + fromValue;
if (!LIRValueUtil.isConstantValue(fromValue)) {
addInterTraceHint(label, (AllocatableValue) toValue, fromValue);
+ addInterTraceHints(livenessInfo, pred, block, label);
}
}
+ } catch (Throwable e) {
+ throw Debug.handle(e);
}
}
+
+ private void addInterTraceHints(GlobalLivenessInfo livenessInfo, AbstractBlockBase<?> from, AbstractBlockBase<?> to, LabelOp label) {
+ if (isAllocated(to, from)) {
+ int[] liveVars = livenessInfo.getBlockIn(to);
+ Value[] outLocation = livenessInfo.getOutLocation(from);
+
+ for (int i = 0; i < liveVars.length; i++) {
+ int varNum = liveVars[i];
+ TraceInterval toInterval = allocator.intervalFor(varNum);
+ if (toInterval != null && !toInterval.hasHint()) {
+ Value fromValue = outLocation[i];
+ if (!LIRValueUtil.isConstantValue(fromValue)) {
+ addInterTraceHint(label, varNum, fromValue);
+ }
}
}
} catch (Throwable e) {
throw Debug.handle(e);
}
}
! private void addInterTraceHint(LabelOp label, AllocatableValue toValue, Value fromValue) {
assert isVariable(toValue) : "Wrong toValue: " + toValue;
! private void addInterTraceHint(LabelOp label, int varNum, Value fromValue) {
assert isRegister(fromValue) || isVariable(fromValue) || isStackSlotValue(fromValue) || isShadowedRegisterValue(fromValue) : "Wrong fromValue: " + fromValue;
! TraceInterval to = allocator.getOrCreateInterval(toValue);
! TraceInterval to = allocator.intervalFor(varNum);
+ if (to == null) {
+ // variable not live -> do nothing
+ return;
+ }
if (isVariableOrRegister(fromValue)) {
IntervalHint from = getIntervalHint((AllocatableValue) fromValue);
setHint(label, to, from);
} else if (isStackSlotValue(fromValue)) {
setSpillSlot(label, to, (AllocatableValue) fromValue);
! } else if (TraceRAshareSpillInformation.getValue(allocator.getLIR().getOptions()) && isShadowedRegisterValue(fromValue)) {
ShadowedRegisterValue shadowedRegisterValue = asShadowedRegisterValue(fromValue);
IntervalHint from = getIntervalHint(shadowedRegisterValue.getRegister());
setHint(label, to, from);
setSpillSlot(label, to, shadowedRegisterValue.getStackSlot());
} else {
src/jdk.internal.vm.compiler/share/classes/org.graalvm.compiler.lir/src/org/graalvm/compiler/lir/alloc/trace/lsra/TraceLinearScanLifetimeAnalysisPhase.java
Index
Unified diffs
Context diffs
Sdiffs
Patch
New
Old
Previous File
Next File