Mercurial > hg > graal-compiler
changeset 22368:8c6bc650d7fa
Merge
| author | Tom Rodriguez <tom.rodriguez@oracle.com> |
|---|---|
| date | Mon, 27 Jul 2015 16:57:30 -0700 |
| parents | 7d48038267b4 (current diff) 1b0304bcf701 (diff) |
| children | 1884fa0c912e |
| files | graal/com.oracle.graal.lir/src/com/oracle/graal/lir/LIRVerifier.java graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/Interval.java graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/SSALinarScanResolveDataFlowPhase.java graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/SSALinearScan.java graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/SSALinearScanEliminateSpillMovePhase.java graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/SSALinearScanLifetimeAnalysisPhase.java graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/SSAMoveResolver.java graal/com.oracle.graal.lir/src/com/oracle/graal/lir/ssa/SSAUtils.java graal/com.oracle.graal.lir/src/com/oracle/graal/lir/util/IntValueMap.java graal/com.oracle.graal.printer/src/com/oracle/graal/printer/CompilationPrinter.java mx.graal/suite.py |
| diffstat | 55 files changed, 3572 insertions(+), 1002 deletions(-) [+] |
line wrap: on
line diff
--- a/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/BackendOptions.java Mon Jul 27 16:26:41 2015 -0700 +++ b/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/BackendOptions.java Mon Jul 27 16:57:30 2015 -0700 @@ -25,7 +25,7 @@ import static com.oracle.graal.compiler.common.BackendOptions.UserOptions.*; import static com.oracle.graal.compiler.common.GraalOptions.*; import jdk.internal.jvmci.options.*; -import jdk.internal.jvmci.options.DerivedOptionValue.*; +import jdk.internal.jvmci.options.DerivedOptionValue.OptionSupplier; /** * Options to control the backend configuration. @@ -36,27 +36,44 @@ // @formatter:off @Option(help = "Destruct SSA LIR eagerly (before other LIR phases).", type = OptionType.Debug) public static final OptionValue<Boolean> LIREagerSSADestruction = new OptionValue<>(false); + @Option(help = "Enable Linear Scan on SSI form.", type = OptionType.Debug) + public static final OptionValue<Boolean> LIROptSSILinearScan = new OptionValue<>(false); + @Option(help = "Enable experimental Trace Register Allocation.", type = OptionType.Debug) + public static final OptionValue<Boolean> TraceRA = new OptionValue<>(false); // @formatter:on } + /* Enable SSI Construction. */ + public static final DerivedOptionValue<Boolean> EnableSSIConstruction = new DerivedOptionValue<>(new OptionSupplier<Boolean>() { + private static final long serialVersionUID = -7375589337502162545L; + + public Boolean get() { + return LIROptSSILinearScan.getValue() || TraceRA.getValue(); + } + }); + /* Create SSA LIR during LIR generation. */ public static final DerivedOptionValue<Boolean> ConstructionSSAlirDuringLirBuilding = new DerivedOptionValue<>(new OptionSupplier<Boolean>() { private static final long serialVersionUID = 7657622005438210681L; public Boolean get() { - return SSA_LIR.getValue(); + return SSA_LIR.getValue() || EnableSSIConstruction.getValue(); } }); public enum LSRAVariant { NONSSA_LSAR, - SSA_LSRA + SSA_LSRA, + SSI_LSRA } public static final DerivedOptionValue<LSRAVariant> LinearScanVariant = new DerivedOptionValue<>(new OptionSupplier<LSRAVariant>() { private static final long serialVersionUID = 364925071685235153L; public LSRAVariant get() { + if (LIROptSSILinearScan.getValue()) { + return LSRAVariant.SSI_LSRA; + } if (SSA_LIR.getValue() && !LIREagerSSADestruction.getValue()) { return LSRAVariant.SSA_LSRA; } @@ -71,9 +88,14 @@ public Boolean get() { switch (LinearScanVariant.getValue()) { case SSA_LSRA: + case SSI_LSRA: return true; } + if (TraceRA.getValue()) { + return true; + } return false; } }); + }
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/alloc/TraceBuilder.java Mon Jul 27 16:57:30 2015 -0700 @@ -0,0 +1,168 @@ +/* + * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.compiler.common.alloc; + +import java.util.*; + +import com.oracle.graal.compiler.common.cfg.*; +import com.oracle.graal.debug.*; +import com.oracle.graal.debug.Debug.Scope; + +public final class TraceBuilder<T extends AbstractBlockBase<T>> { + + public static final class TraceBuilderResult<T extends AbstractBlockBase<T>> { + private final List<List<T>> traces; + private final int[] blockToTrace; + + private TraceBuilderResult(List<List<T>> traces, int[] blockToTrace) { + this.traces = traces; + this.blockToTrace = blockToTrace; + } + + public int getTraceForBlock(AbstractBlockBase<?> block) { + return blockToTrace[block.getId()]; + } + + public List<List<T>> getTraces() { + return traces; + } + } + + /** + * Build traces of sequentially executed blocks. + */ + public static <T extends AbstractBlockBase<T>> TraceBuilderResult<T> computeTraces(T startBlock, List<T> blocks) { + return new TraceBuilder<>(blocks).build(startBlock); + } + + private final PriorityQueue<T> worklist; + private final BitSet processed; + /** + * Contains the number of unprocessed predecessors for every {@link AbstractBlockBase#getId() + * block}. + */ + private final int[] blocked; + private final int[] blockToTrace; + + private TraceBuilder(List<T> blocks) { + processed = new BitSet(blocks.size()); + worklist = new PriorityQueue<T>(TraceBuilder::compare); + blocked = new int[blocks.size()]; + blockToTrace = new int[blocks.size()]; + for (T block : blocks) { + blocked[block.getId()] = block.getPredecessorCount(); + } + } + + private static <T extends AbstractBlockBase<T>> int compare(T a, T b) { + return Double.compare(b.probability(), a.probability()); + } + + private boolean processed(T b) { + return processed.get(b.getId()); + } + + private TraceBuilderResult<T> build(T startBlock) { + try (Scope s = Debug.scope("TraceBuilder"); Indent i = Debug.logAndIndent("start trace building: " + startBlock)) { + ArrayList<List<T>> traces = buildTraces(startBlock); + + assert verify(traces); + return new TraceBuilderResult<>(traces, blockToTrace); + } + } + + private boolean verify(ArrayList<List<T>> traces) { + assert traces.stream().flatMap(l -> l.stream()).distinct().count() == blocked.length : "Not all blocks assigned to traces!"; + for (List<T> trace : traces) { + T last = null; + for (T current : trace) { + assert last == null || current.getPredecessors().contains(last); + last = current; + } + } + return true; + } + + protected ArrayList<List<T>> buildTraces(T startBlock) { + ArrayList<List<T>> traces = new ArrayList<>(); + // add start block + worklist.add(startBlock); + // process worklist + while (!worklist.isEmpty()) { + T block = worklist.poll(); + assert block != null; + traces.add(startTrace(block, traces.size())); + } + return traces; + } + + /** + * Build a new trace starting at {@code block}. + */ + private List<T> startTrace(T block, int traceNumber) { + assert block.getPredecessors().stream().allMatch(this::processed) : "Predecessor unscheduled: " + block.getPredecessors().stream().filter(this::processed).findFirst().get(); + ArrayList<T> trace = new ArrayList<>(); + int blockNumber = 0; + try (Indent i = Debug.logAndIndent("StartTrace: " + block)) { + for (T currentBlock = block; currentBlock != null; currentBlock = selectNext(currentBlock)) { + Debug.log("add %s (prob: %f)", currentBlock, currentBlock.probability()); + processed.set(currentBlock.getId()); + worklist.remove(currentBlock); + trace.add(currentBlock); + unblock(currentBlock); + currentBlock.setLinearScanNumber(blockNumber++); + blockToTrace[currentBlock.getId()] = traceNumber; + } + } + return trace; + } + + /** + * Decrease the {@link #blocked} count for all predecessors and add them to the worklist once + * the count reaches 0. + */ + private void unblock(T currentBlock) { + for (T successor : currentBlock.getSuccessors()) { + if (!processed(successor)) { + int blockCount = --blocked[successor.getId()]; + assert blockCount >= 0; + if (blockCount == 0) { + worklist.add(successor); + } + } + } + } + + /** + * @return The unprocessed predecessor with the highest probability, or {@code null}. + */ + private T selectNext(T currentBlock) { + T next = null; + for (T succ : currentBlock.getSuccessors()) { + if (!processed(succ) && (next == null || succ.probability() > next.probability())) { + next = succ; + } + } + return next; + } +}
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/LIRGenerationPhase.java Mon Jul 27 16:26:41 2015 -0700 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/LIRGenerationPhase.java Mon Jul 27 16:57:30 2015 -0700 @@ -64,7 +64,7 @@ emitBlock(nodeLirBuilder, lirGenRes, (Block) b, graph, schedule.getBlockToNodesMap()); } context.lirGen.beforeRegisterAllocation(); - assert !ConstructionSSAlirDuringLirBuilding.getValue() || SSAUtils.verifySSAForm(lirGenRes.getLIR()); + assert !ConstructionSSAlirDuringLirBuilding.getValue() || SSAUtil.verifySSAForm(lirGenRes.getLIR()); } private static void emitBlock(NodeLIRBuilderTool nodeLirGen, LIRGenerationResult lirGenRes, Block b, StructuredGraph graph, BlockMap<List<Node>> blockMap) {
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/LIRFrameState.java Mon Jul 27 16:26:41 2015 -0700 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/LIRFrameState.java Mon Jul 27 16:57:30 2015 -0700 @@ -45,7 +45,7 @@ public final LabelRef exceptionEdge; protected DebugInfo debugInfo; - private IntValueMap liveBasePointers; + private IndexedValueMap liveBasePointers; public LIRFrameState(BytecodeFrame topFrame, VirtualObject[] virtualObjects, LabelRef exceptionEdge) { this.topFrame = topFrame; @@ -181,11 +181,11 @@ debugInfo = new DebugInfo(topFrame, virtualObjects); } - public IntValueMap getLiveBasePointers() { + public IndexedValueMap getLiveBasePointers() { return liveBasePointers; } - public void setLiveBasePointers(IntValueMap liveBasePointers) { + public void setLiveBasePointers(IndexedValueMap liveBasePointers) { this.liveBasePointers = liveBasePointers; }
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/LIRVerifier.java Mon Jul 27 16:26:41 2015 -0700 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/LIRVerifier.java Mon Jul 27 16:57:30 2015 -0700 @@ -131,7 +131,7 @@ assert last instanceof StandardOp.JumpOp : "block with successor must end with unconditional jump"; } if (block.getPredecessorCount() > 1) { - SSAUtils.verifyPhi(lir, block); + SSAUtil.verifyPhi(lir, block); } for (LIRInstruction op : lir.getLIRforBlock(block)) {
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/Interval.java Mon Jul 27 16:26:41 2015 -0700 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/Interval.java Mon Jul 27 16:57:30 2015 -0700 @@ -291,7 +291,7 @@ /** * Constants used in optimization of spilling of an interval. */ - enum SpillState { + public enum SpillState { /** * Starting state of calculation: no definition found yet. */ @@ -577,7 +577,7 @@ return first; } - int from() { + public int from() { return first.from; } @@ -593,11 +593,11 @@ return usePosList.size(); } - void setLocationHint(Interval interval) { + public void setLocationHint(Interval interval) { locationHint = interval; } - boolean isSplitParent() { + public boolean isSplitParent() { return splitParent == this; } @@ -646,22 +646,22 @@ return splitParent().spillState; } - int spillDefinitionPos() { + public int spillDefinitionPos() { return splitParent().spillDefinitionPos; } - void setSpillState(SpillState state) { + public void setSpillState(SpillState state) { assert state.ordinal() >= spillState().ordinal() : "state cannot decrease"; splitParent().spillState = state; } - void setSpillDefinitionPos(int pos) { + public void setSpillDefinitionPos(int pos) { assert spillState() == SpillState.SpillInDominator || spillState() == SpillState.NoDefinitionFound || spillDefinitionPos() == -1 : "cannot set the position twice"; splitParent().spillDefinitionPos = pos; } // returns true if this interval has a shadow copy on the stack that is always correct - boolean alwaysInMemory() { + public boolean alwaysInMemory() { return (splitParent().spillState == SpillState.SpillInDominator || splitParent().spillState == SpillState.StoreAtDefinition || splitParent().spillState == SpillState.StartInMemory) && !canMaterialize(); } @@ -1051,7 +1051,7 @@ } } - void addRange(int from, int to) { + public void addRange(int from, int to) { assert from < to : "invalid range"; assert first() == Range.EndMarker || to < first().next.from : "not inserting at begin of interval"; assert from <= first().to : "not inserting at begin of interval";
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScan.java Mon Jul 27 16:26:41 2015 -0700 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScan.java Mon Jul 27 16:57:30 2015 -0700 @@ -53,20 +53,7 @@ * >"Optimized Interval Splitting in a Linear Scan Register Allocator"</a> by Christian Wimmer and * Hanspeter Moessenboeck. */ -class LinearScan { - - final LIRGenerationResult res; - final LIR ir; - final FrameMapBuilder frameMapBuilder; - final RegisterAttributes[] registerAttributes; - final Register[] registers; - final RegisterAllocationConfig regAllocConfig; - private final SpillMoveFactory moveFactory; - - final boolean callKillsRegisters; - - public static final int DOMINATOR_SPILL_MOVE_ID = -2; - static final int SPLIT_INTERVALS_CAPACITY_RIGHT_SHIFT = 1; +public class LinearScan { public static class Options { // @formatter:off @@ -107,15 +94,25 @@ public BitSet liveKill; } + public static final int DOMINATOR_SPILL_MOVE_ID = -2; + private static final int SPLIT_INTERVALS_CAPACITY_RIGHT_SHIFT = 1; + + private final LIR ir; + private final FrameMapBuilder frameMapBuilder; + private final RegisterAttributes[] registerAttributes; + private final Register[] registers; + private final RegisterAllocationConfig regAllocConfig; + private final SpillMoveFactory moveFactory; + private final BlockMap<BlockData> blockData; /** * List of blocks in linear-scan order. This is only correct as long as the CFG does not change. */ - final List<? extends AbstractBlockBase<?>> sortedBlocks; + private final List<? extends AbstractBlockBase<?>> sortedBlocks; /** @see #intervals() */ - protected Interval[] intervals; + private Interval[] intervals; /** * The number of valid entries in {@link #intervals}. @@ -152,8 +149,8 @@ */ private final int firstVariableNumber; - LinearScan(TargetDescription target, LIRGenerationResult res, SpillMoveFactory spillMoveFactory, RegisterAllocationConfig regAllocConfig, List<? extends AbstractBlockBase<?>> sortedBlocks) { - this.res = res; + protected LinearScan(TargetDescription target, LIRGenerationResult res, SpillMoveFactory spillMoveFactory, RegisterAllocationConfig regAllocConfig, + List<? extends AbstractBlockBase<?>> sortedBlocks) { this.ir = res.getLIR(); this.moveFactory = spillMoveFactory; this.frameMapBuilder = res.getFrameMapBuilder(); @@ -162,30 +159,24 @@ this.regAllocConfig = regAllocConfig; this.registers = target.arch.getRegisters(); - this.firstVariableNumber = registers.length; + this.firstVariableNumber = getRegisters().length; this.blockData = new BlockMap<>(ir.getControlFlowGraph()); - - /* - * If all allocatable registers are caller saved, then no registers are live across a call - * site. The register allocator can save time not trying to find a register at a call site. - */ - this.callKillsRegisters = regAllocConfig.getRegisterConfig().areAllAllocatableRegistersCallerSaved(); } - int getFirstLirInstructionId(AbstractBlockBase<?> block) { + public int getFirstLirInstructionId(AbstractBlockBase<?> block) { int result = ir.getLIRforBlock(block).get(0).id(); assert result >= 0; return result; } - int getLastLirInstructionId(AbstractBlockBase<?> block) { + public int getLastLirInstructionId(AbstractBlockBase<?> block) { List<LIRInstruction> instructions = ir.getLIRforBlock(block); int result = instructions.get(instructions.size() - 1).id(); assert result >= 0; return result; } - SpillMoveFactory getSpillMoveFactory() { + public SpillMoveFactory getSpillMoveFactory() { return moveFactory; } @@ -228,7 +219,7 @@ return firstVariableNumber - 1; } - BlockData getBlockData(AbstractBlockBase<?> block) { + public BlockData getBlockData(AbstractBlockBase<?> block) { return blockData.get(block); } @@ -287,7 +278,7 @@ /** * Map from {@linkplain #operandNumber(Value) operand numbers} to intervals. */ - Interval[] intervals() { + public Interval[] intervals() { return intervals; } @@ -334,11 +325,11 @@ } // access to block list (sorted in linear scan order) - int blockCount() { + public int blockCount() { return sortedBlocks.size(); } - AbstractBlockBase<?> blockAt(int index) { + public AbstractBlockBase<?> blockAt(int index) { return sortedBlocks.get(index); } @@ -347,7 +338,7 @@ * block. These sets do not include any operands allocated as a result of creating * {@linkplain #createDerivedInterval(Interval) derived intervals}. */ - int liveSetSize() { + public int liveSetSize() { return firstDerivedIntervalIndex == -1 ? operandSize() : firstDerivedIntervalIndex; } @@ -359,13 +350,13 @@ return intervals[operandNumber]; } - Interval intervalFor(Value operand) { + public Interval intervalFor(Value operand) { int operandNumber = operandNumber(operand); assert operandNumber < intervalsSize; return intervals[operandNumber]; } - Interval getOrCreateInterval(AllocatableValue operand) { + public Interval getOrCreateInterval(AllocatableValue operand) { Interval ret = intervalFor(operand); if (ret == null) { return createInterval(operand); @@ -407,7 +398,7 @@ * @param opId an instruction {@linkplain LIRInstruction#id id} * @return the instruction whose {@linkplain LIRInstruction#id} {@code == id} */ - LIRInstruction instructionForId(int opId) { + public LIRInstruction instructionForId(int opId) { assert isEven(opId) : "opId not even"; LIRInstruction instr = opIdToInstructionMap[opIdToIndex(opId)]; assert instr.id() == opId; @@ -420,7 +411,7 @@ * @param opId an instruction {@linkplain LIRInstruction#id id} * @return the block containing the instruction denoted by {@code opId} */ - AbstractBlockBase<?> blockForId(int opId) { + public AbstractBlockBase<?> blockForId(int opId) { assert opIdToBlockMap.length > 0 && opId >= 0 && opId <= maxOpId() + 1 : "opId out of range"; return opIdToBlockMap[opIdToIndex(opId)]; } @@ -515,7 +506,7 @@ return new Interval.Pair(list1, list2); } - void sortIntervalsBeforeAllocation() { + protected void sortIntervalsBeforeAllocation() { int sortedLen = 0; for (Interval interval : intervals) { if (interval != null) { @@ -585,7 +576,7 @@ // wrapper for Interval.splitChildAtOpId that performs a bailout in product mode // instead of returning null - Interval splitChildAtOpId(Interval interval, int opId, LIRInstruction.OperandMode mode) { + public Interval splitChildAtOpId(Interval interval, int opId, LIRInstruction.OperandMode mode) { Interval result = interval.getSplitChildAtOpId(opId, mode, this); if (result != null) { @@ -622,8 +613,8 @@ return attributes(asRegister(operand)).isCallerSave(); } - <B extends AbstractBlockBase<B>> void allocate(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder, SpillMoveFactory spillMoveFactory, - RegisterAllocationConfig registerAllocationConfig) { + protected <B extends AbstractBlockBase<B>> void allocate(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder, + SpillMoveFactory spillMoveFactory, RegisterAllocationConfig registerAllocationConfig) { /* * This is the point to enable debug logging for the whole register allocation. @@ -688,7 +679,7 @@ return new LinearScanAssignLocationsPhase(this); } - void printIntervals(String label) { + protected void printIntervals(String label) { if (Debug.isLogEnabled()) { try (Indent indent = Debug.logAndIndent("intervals %s", label)) { for (Interval interval : intervals) { @@ -708,7 +699,7 @@ Debug.dump(Arrays.copyOf(intervals, intervalsSize), label); } - void printLir(String label, @SuppressWarnings("unused") boolean hirValid) { + protected void printLir(String label, @SuppressWarnings("unused") boolean hirValid) { Debug.dump(ir, label); } @@ -731,7 +722,7 @@ } } - void verifyIntervals() { + protected void verifyIntervals() { try (Indent indent = Debug.logAndIndent("verifying intervals")) { int len = intervalsSize; @@ -872,4 +863,28 @@ } } + public LIR getLIR() { + return ir; + } + + public FrameMapBuilder getFrameMapBuilder() { + return frameMapBuilder; + } + + public List<? extends AbstractBlockBase<?>> sortedBlocks() { + return sortedBlocks; + } + + public Register[] getRegisters() { + return registers; + } + + public RegisterAllocationConfig getRegisterAllocationConfig() { + return regAllocConfig; + } + + public boolean callKillsRegisters() { + return regAllocConfig.getRegisterConfig().areAllAllocatableRegistersCallerSaved(); + } + }
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScanAssignLocationsPhase.java Mon Jul 27 16:26:41 2015 -0700 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScanAssignLocationsPhase.java Mon Jul 27 16:57:30 2015 -0700 @@ -45,7 +45,7 @@ /** * Phase 7: Assign register numbers back to LIR. */ -final class LinearScanAssignLocationsPhase extends AllocationPhase { +public final class LinearScanAssignLocationsPhase extends AllocationPhase { private final LinearScan allocator; @@ -80,7 +80,7 @@ * before the branch instruction. So the split child information for this branch * would be incorrect. */ - LIRInstruction instr = allocator.ir.getLIRforBlock(block).get(allocator.ir.getLIRforBlock(block).size() - 1); + LIRInstruction instr = allocator.getLIR().getLIRforBlock(block).get(allocator.getLIR().getLIRforBlock(block).size() - 1); if (instr instanceof StandardOp.JumpOp) { if (allocator.getBlockData(block).liveOut.get(allocator.operandNumber(operand))) { assert false : String.format( @@ -125,10 +125,10 @@ * is a branch, spill moves are inserted before this branch and so the wrong operand * would be returned (spill moves at block boundaries are not considered in the live * ranges of intervals). - * + * * Solution: use the first opId of the branch target block instead. */ - final LIRInstruction instr = allocator.ir.getLIRforBlock(block).get(allocator.ir.getLIRforBlock(block).size() - 1); + final LIRInstruction instr = allocator.getLIR().getLIRforBlock(block).get(allocator.getLIR().getLIRforBlock(block).size() - 1); if (instr instanceof StandardOp.JumpOp) { if (allocator.getBlockData(block).liveOut.get(allocator.operandNumber(operand))) { tempOpId = allocator.getFirstLirInstructionId(block.getSuccessors().iterator().next()); @@ -208,9 +208,9 @@ private void assignLocations() { try (Indent indent = Debug.logAndIndent("assign locations")) { - for (AbstractBlockBase<?> block : allocator.sortedBlocks) { + for (AbstractBlockBase<?> block : allocator.sortedBlocks()) { try (Indent indent2 = Debug.logAndIndent("assign locations in block B%d", block.getId())) { - assignLocations(allocator.ir.getLIRforBlock(block)); + assignLocations(allocator.getLIR().getLIRforBlock(block)); } } }
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScanEliminateSpillMovePhase.java Mon Jul 27 16:26:41 2015 -0700 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScanEliminateSpillMovePhase.java Mon Jul 27 16:57:30 2015 -0700 @@ -42,7 +42,7 @@ import com.oracle.graal.lir.gen.LIRGeneratorTool.SpillMoveFactory; import com.oracle.graal.lir.phases.*; -class LinearScanEliminateSpillMovePhase extends AllocationPhase { +public class LinearScanEliminateSpillMovePhase extends AllocationPhase { private static final IntervalPredicate mustStoreAtDefinition = new LinearScan.IntervalPredicate() { @@ -54,7 +54,7 @@ protected final LinearScan allocator; - LinearScanEliminateSpillMovePhase(LinearScan allocator) { + protected LinearScanEliminateSpillMovePhase(LinearScan allocator) { this.allocator = allocator; } @@ -88,9 +88,9 @@ } LIRInsertionBuffer insertionBuffer = new LIRInsertionBuffer(); - for (AbstractBlockBase<?> block : allocator.sortedBlocks) { + for (AbstractBlockBase<?> block : allocator.sortedBlocks()) { try (Indent indent1 = Debug.logAndIndent("Handle %s", block)) { - List<LIRInstruction> instructions = allocator.ir.getLIRforBlock(block); + List<LIRInstruction> instructions = allocator.getLIR().getLIRforBlock(block); int numInst = instructions.size(); // iterate all instructions of the block.
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScanLifetimeAnalysisPhase.java Mon Jul 27 16:26:41 2015 -0700 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScanLifetimeAnalysisPhase.java Mon Jul 27 16:57:30 2015 -0700 @@ -50,14 +50,14 @@ import com.oracle.graal.lir.gen.LIRGeneratorTool.SpillMoveFactory; import com.oracle.graal.lir.phases.*; -class LinearScanLifetimeAnalysisPhase extends AllocationPhase { +public class LinearScanLifetimeAnalysisPhase extends AllocationPhase { protected final LinearScan allocator; /** * @param linearScan */ - LinearScanLifetimeAnalysisPhase(LinearScan linearScan) { + protected LinearScanLifetimeAnalysisPhase(LinearScan linearScan) { allocator = linearScan; } @@ -74,7 +74,7 @@ /** * Bit set for each variable that is contained in each loop. */ - BitMap2D intervalInLoop; + private BitMap2D intervalInLoop; boolean isIntervalInLoop(int interval, int loop) { return intervalInLoop.at(interval, loop); @@ -96,8 +96,8 @@ // Assign IDs to LIR nodes and build a mapping, lirOps, from ID to LIRInstruction node. int numInstructions = 0; - for (AbstractBlockBase<?> block : allocator.sortedBlocks) { - numInstructions += allocator.ir.getLIRforBlock(block).size(); + for (AbstractBlockBase<?> block : allocator.sortedBlocks()) { + numInstructions += allocator.getLIR().getLIRforBlock(block).size(); } // initialize with correct length @@ -105,10 +105,10 @@ int opId = 0; int index = 0; - for (AbstractBlockBase<?> block : allocator.sortedBlocks) { + for (AbstractBlockBase<?> block : allocator.sortedBlocks()) { allocator.initBlockData(block); - List<LIRInstruction> instructions = allocator.ir.getLIRforBlock(block); + List<LIRInstruction> instructions = allocator.getLIR().getLIRforBlock(block); int numInst = instructions.size(); for (int j = 0; j < numInst; j++) { @@ -139,13 +139,13 @@ intervalInLoop = new BitMap2D(allocator.operandSize(), allocator.numLoops()); // iterate all blocks - for (final AbstractBlockBase<?> block : allocator.sortedBlocks) { + for (final AbstractBlockBase<?> block : allocator.sortedBlocks()) { try (Indent indent = Debug.logAndIndent("compute local live sets for block %s", block)) { final BitSet liveGen = new BitSet(liveSize); final BitSet liveKill = new BitSet(liveSize); - List<LIRInstruction> instructions = allocator.ir.getLIRforBlock(block); + List<LIRInstruction> instructions = allocator.getLIR().getLIRforBlock(block); int numInst = instructions.size(); ValueConsumer useConsumer = (operand, mode, flags) -> { @@ -249,7 +249,7 @@ * sets. This is checked by these assertions to be sure about it. The entry block may have * incoming values in registers, which is ok. */ - if (isRegister(operand) && block != allocator.ir.getControlFlowGraph().getStartBlock()) { + if (isRegister(operand) && block != allocator.getLIR().getControlFlowGraph().getStartBlock()) { if (allocator.isProcessed(operand)) { assert liveKill.get(allocator.operandNumber(operand)) : "using fixed register that is not defined in this block"; } @@ -260,7 +260,7 @@ * Performs a backward dataflow analysis to compute global live sets (i.e. * {@link BlockData#liveIn} and {@link BlockData#liveOut}) for each block. */ - void computeGlobalLiveSets() { + protected void computeGlobalLiveSets() { try (Indent indent = Debug.logAndIndent("compute global live sets")) { int numBlocks = allocator.blockCount(); boolean changeOccurred; @@ -313,7 +313,7 @@ /* * liveIn(block) is the union of liveGen(block) with (liveOut(block) & * !liveKill(block)). - * + * * Note: liveIn has to be computed only in first iteration or if liveOut * has changed! */ @@ -341,7 +341,7 @@ } // check that the liveIn set of the first block is empty - AbstractBlockBase<?> startBlock = allocator.ir.getControlFlowGraph().getStartBlock(); + AbstractBlockBase<?> startBlock = allocator.getLIR().getControlFlowGraph().getStartBlock(); if (allocator.getBlockData(startBlock).liveIn.cardinality() != 0) { if (DetailedAsserts.getValue()) { reportFailure(numBlocks); @@ -356,7 +356,7 @@ try (Scope s = Debug.forceLog()) { try (Indent indent = Debug.logAndIndent("report failure")) { - BitSet startBlockLiveIn = allocator.getBlockData(allocator.ir.getControlFlowGraph().getStartBlock()).liveIn; + BitSet startBlockLiveIn = allocator.getBlockData(allocator.getLIR().getControlFlowGraph().getStartBlock()).liveIn; try (Indent indent2 = Debug.logAndIndent("Error: liveIn set of first block must be empty (when this fails, variables are used before they are defined):")) { for (int operandNum = startBlockLiveIn.nextSetBit(0); operandNum >= 0; operandNum = startBlockLiveIn.nextSetBit(operandNum + 1)) { Interval interval = allocator.intervalFor(operandNum); @@ -382,11 +382,11 @@ Deque<AbstractBlockBase<?>> definedIn = new ArrayDeque<>(); HashSet<AbstractBlockBase<?>> usedIn = new HashSet<>(); - for (AbstractBlockBase<?> block : allocator.sortedBlocks) { + for (AbstractBlockBase<?> block : allocator.sortedBlocks()) { if (allocator.getBlockData(block).liveGen.get(operandNum)) { usedIn.add(block); try (Indent indent3 = Debug.logAndIndent("used in block B%d", block.getId())) { - for (LIRInstruction ins : allocator.ir.getLIRforBlock(block)) { + for (LIRInstruction ins : allocator.getLIR().getLIRforBlock(block)) { try (Indent indent4 = Debug.logAndIndent("%d: %s", ins.id(), ins)) { ins.forEachState((liveStateOperand, mode, flags) -> { Debug.log("operand=%s", liveStateOperand); @@ -399,7 +399,7 @@ if (allocator.getBlockData(block).liveKill.get(operandNum)) { definedIn.add(block); try (Indent indent3 = Debug.logAndIndent("defined in block B%d", block.getId())) { - for (LIRInstruction ins : allocator.ir.getLIRforBlock(block)) { + for (LIRInstruction ins : allocator.getLIR().getLIRforBlock(block)) { Debug.log("%d: %s", ins.id(), ins); } } @@ -441,7 +441,7 @@ * Check that fixed intervals are not live at block boundaries (live set must be empty at * fixed intervals). */ - for (AbstractBlockBase<?> block : allocator.sortedBlocks) { + for (AbstractBlockBase<?> block : allocator.sortedBlocks()) { for (int j = 0; j <= allocator.maxRegisterNumber(); j++) { assert !allocator.getBlockData(block).liveIn.get(j) : "liveIn set of fixed register must be empty"; assert !allocator.getBlockData(block).liveOut.get(j) : "liveOut set of fixed register must be empty"; @@ -536,7 +536,7 @@ * Optimizes moves related to incoming stack based arguments. The interval for the destination * of such moves is assigned the stack slot (which is in the caller's frame) as its spill slot. */ - void handleMethodArguments(LIRInstruction op) { + protected void handleMethodArguments(LIRInstruction op) { if (op instanceof MoveOp) { MoveOp move = (MoveOp) op; if (optimizeMethodArgument(move.getInput())) { @@ -564,7 +564,7 @@ } } - void addRegisterHint(final LIRInstruction op, final Value targetValue, OperandMode mode, EnumSet<OperandFlag> flags, final boolean hintAtDef) { + protected void addRegisterHint(final LIRInstruction op, final Value targetValue, OperandMode mode, EnumSet<OperandFlag> flags, final boolean hintAtDef) { if (flags.contains(OperandFlag.HINT) && LinearScan.isVariableOrRegister(targetValue)) { op.forEachRegisterHint(targetValue, mode, (registerHint, valueMode, valueFlags) -> { @@ -662,7 +662,7 @@ return RegisterPriority.MustHaveRegister; } - void buildIntervals() { + protected void buildIntervals() { try (Indent indent = Debug.logAndIndent("build intervals")) { InstructionValueConsumer outputConsumer = (op, operand, mode, flags) -> { @@ -708,7 +708,7 @@ }; // create a list with all caller-save registers (cpu, fpu, xmm) - Register[] callerSaveRegs = allocator.regAllocConfig.getRegisterConfig().getCallerSaveRegisters(); + Register[] callerSaveRegs = allocator.getRegisterAllocationConfig().getRegisterConfig().getCallerSaveRegisters(); // iterate all blocks in reverse order for (int i = allocator.blockCount() - 1; i >= 0; i--) { @@ -716,7 +716,7 @@ AbstractBlockBase<?> block = allocator.blockAt(i); try (Indent indent2 = Debug.logAndIndent("handle block %d", block.getId())) { - List<LIRInstruction> instructions = allocator.ir.getLIRforBlock(block); + List<LIRInstruction> instructions = allocator.getLIR().getLIRforBlock(block); final int blockFrom = allocator.getFirstLirInstructionId(block); int blockTo = allocator.getLastLirInstructionId(block);
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScanOptimizeSpillPositionPhase.java Mon Jul 27 16:26:41 2015 -0700 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScanOptimizeSpillPositionPhase.java Mon Jul 27 16:57:30 2015 -0700 @@ -40,7 +40,7 @@ import com.oracle.graal.lir.gen.LIRGeneratorTool.SpillMoveFactory; import com.oracle.graal.lir.phases.*; -final class LinearScanOptimizeSpillPositionPhase extends AllocationPhase { +public final class LinearScanOptimizeSpillPositionPhase extends AllocationPhase { private static final DebugMetric betterSpillPos = Debug.metric("BetterSpillPosition"); private static final DebugMetric betterSpillPosWithLowerProbability = Debug.metric("BetterSpillPositionWithLowerProbability"); @@ -60,7 +60,7 @@ private void optimizeSpillPosition() { try (Indent indent0 = Debug.logAndIndent("OptimizeSpillPositions")) { - LIRInsertionBuffer[] insertionBuffers = new LIRInsertionBuffer[allocator.ir.linearScanOrder().size()]; + LIRInsertionBuffer[] insertionBuffers = new LIRInsertionBuffer[allocator.getLIR().linearScanOrder().size()]; for (Interval interval : allocator.intervals()) { optimizeInterval(insertionBuffers, interval); } @@ -118,7 +118,7 @@ /* * The spill block is the begin of the first split child (aka the value is on the * stack). - * + * * The problem is that if spill block has more than one predecessor, the values at the * end of the predecessors might differ. Therefore, we would need a spill move in all * predecessors. To avoid this we spill in the dominator. @@ -154,7 +154,7 @@ if (insertionBuffer == null) { insertionBuffer = new LIRInsertionBuffer(); insertionBuffers[spillBlock.getId()] = insertionBuffer; - insertionBuffer.init(allocator.ir.getLIRforBlock(spillBlock)); + insertionBuffer.init(allocator.getLIR().getLIRforBlock(spillBlock)); } int spillOpId = allocator.getFirstLirInstructionId(spillBlock); // insert spill move @@ -189,8 +189,8 @@ public AbstractBlockBase<?> next() { AbstractBlockBase<?> currentBlock = block; int nextBlockIndex = block.getLinearScanNumber() + 1; - if (nextBlockIndex < allocator.sortedBlocks.size()) { - block = allocator.sortedBlocks.get(nextBlockIndex); + if (nextBlockIndex < allocator.sortedBlocks().size()) { + block = allocator.sortedBlocks().get(nextBlockIndex); if (range.to <= allocator.getFirstLirInstructionId(block)) { range = range.next; if (range == Range.EndMarker) {
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScanPhase.java Mon Jul 27 16:26:41 2015 -0700 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScanPhase.java Mon Jul 27 16:57:30 2015 -0700 @@ -31,6 +31,8 @@ import com.oracle.graal.compiler.common.alloc.*; import com.oracle.graal.compiler.common.cfg.*; +import com.oracle.graal.lir.alloc.lsra.ssa.*; +import com.oracle.graal.lir.alloc.lsra.ssi.*; import com.oracle.graal.lir.gen.*; import com.oracle.graal.lir.gen.LIRGeneratorTool.SpillMoveFactory; import com.oracle.graal.lir.phases.*; @@ -42,6 +44,9 @@ RegisterAllocationConfig registerAllocationConfig) { final LinearScan allocator; switch (LinearScanVariant.getValue()) { + case SSI_LSRA: + allocator = new SSILinearScan(target, lirGenRes, spillMoveFactory, registerAllocationConfig, linearScanOrder); + break; case SSA_LSRA: allocator = new SSALinearScan(target, lirGenRes, spillMoveFactory, registerAllocationConfig, linearScanOrder); break;
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScanRegisterAllocationPhase.java Mon Jul 27 16:26:41 2015 -0700 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScanRegisterAllocationPhase.java Mon Jul 27 16:57:30 2015 -0700 @@ -33,7 +33,7 @@ import com.oracle.graal.lir.gen.LIRGeneratorTool.SpillMoveFactory; import com.oracle.graal.lir.phases.*; -final class LinearScanRegisterAllocationPhase extends AllocationPhase { +public final class LinearScanRegisterAllocationPhase extends AllocationPhase { private final LinearScan allocator;
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScanResolveDataFlowPhase.java Mon Jul 27 16:26:41 2015 -0700 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScanResolveDataFlowPhase.java Mon Jul 27 16:57:30 2015 -0700 @@ -41,11 +41,11 @@ * * Insert moves at edges between blocks if intervals have been split. */ -class LinearScanResolveDataFlowPhase extends AllocationPhase { +public class LinearScanResolveDataFlowPhase extends AllocationPhase { protected final LinearScan allocator; - LinearScanResolveDataFlowPhase(LinearScan allocator) { + protected LinearScanResolveDataFlowPhase(LinearScan allocator) { this.allocator = allocator; } @@ -55,7 +55,7 @@ resolveDataFlow(); } - void resolveCollectMappings(AbstractBlockBase<?> fromBlock, AbstractBlockBase<?> toBlock, AbstractBlockBase<?> midBlock, MoveResolver moveResolver) { + protected void resolveCollectMappings(AbstractBlockBase<?> fromBlock, AbstractBlockBase<?> toBlock, AbstractBlockBase<?> midBlock, MoveResolver moveResolver) { assert moveResolver.checkEmpty(); assert midBlock == null || (midBlock.getPredecessorCount() == 1 && midBlock.getSuccessorCount() == 1 && midBlock.getPredecessors().get(0).equals(fromBlock) && midBlock.getSuccessors().get(0).equals( @@ -87,7 +87,7 @@ Debug.log("inserting moves at end of fromBlock B%d", fromBlock.getId()); } - List<LIRInstruction> instructions = allocator.ir.getLIRforBlock(fromBlock); + List<LIRInstruction> instructions = allocator.getLIR().getLIRforBlock(fromBlock); LIRInstruction instr = instructions.get(instructions.size() - 1); if (instr instanceof StandardOp.JumpOp) { // insert moves before branch @@ -102,7 +102,7 @@ } if (DetailedAsserts.getValue()) { - assert allocator.ir.getLIRforBlock(fromBlock).get(0) instanceof StandardOp.LabelOp : "block does not start with a label"; + assert allocator.getLIR().getLIRforBlock(fromBlock).get(0) instanceof StandardOp.LabelOp : "block does not start with a label"; /* * Because the number of predecessor edges matches the number of successor edges, @@ -114,7 +114,7 @@ } } - moveResolver.setInsertPosition(allocator.ir.getLIRforBlock(toBlock), 1); + moveResolver.setInsertPosition(allocator.getLIR().getLIRforBlock(toBlock), 1); } } @@ -122,7 +122,7 @@ * Inserts necessary moves (spilling or reloading) at edges between blocks for intervals that * have been split. */ - void resolveDataFlow() { + protected void resolveDataFlow() { try (Indent indent = Debug.logAndIndent("resolve data flow")) { MoveResolver moveResolver = allocator.createMoveResolver(); @@ -136,11 +136,11 @@ } protected void optimizeEmptyBlocks(MoveResolver moveResolver, BitSet blockCompleted) { - for (AbstractBlockBase<?> block : allocator.sortedBlocks) { + for (AbstractBlockBase<?> block : allocator.sortedBlocks()) { // check if block has only one predecessor and only one successor if (block.getPredecessorCount() == 1 && block.getSuccessorCount() == 1) { - List<LIRInstruction> instructions = allocator.ir.getLIRforBlock(block); + List<LIRInstruction> instructions = allocator.getLIR().getLIRforBlock(block); assert instructions.get(0) instanceof StandardOp.LabelOp : "block must start with label"; assert instructions.get(instructions.size() - 1) instanceof StandardOp.JumpOp : "block with successor must end with unconditional jump"; @@ -174,7 +174,7 @@ protected void resolveDataFlow0(MoveResolver moveResolver, BitSet blockCompleted) { BitSet alreadyResolved = new BitSet(allocator.blockCount()); - for (AbstractBlockBase<?> fromBlock : allocator.sortedBlocks) { + for (AbstractBlockBase<?> fromBlock : allocator.sortedBlocks()) { if (!blockCompleted.get(fromBlock.getLinearScanNumber())) { alreadyResolved.clear(); alreadyResolved.or(blockCompleted);
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScanWalker.java Mon Jul 27 16:26:41 2015 -0700 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScanWalker.java Mon Jul 27 16:57:30 2015 -0700 @@ -84,12 +84,12 @@ super(allocator, unhandledFixedFirst, unhandledAnyFirst); moveResolver = allocator.createMoveResolver(); - spillIntervals = Util.uncheckedCast(new List[allocator.registers.length]); - for (int i = 0; i < allocator.registers.length; i++) { + spillIntervals = Util.uncheckedCast(new List[allocator.getRegisters().length]); + for (int i = 0; i < allocator.getRegisters().length; i++) { spillIntervals[i] = EMPTY_LIST; } - usePos = new int[allocator.registers.length]; - blockPos = new int[allocator.registers.length]; + usePos = new int[allocator.getRegisters().length]; + blockPos = new int[allocator.getRegisters().length]; } void initUseLists(boolean onlyProcessUsePos) { @@ -268,7 +268,7 @@ // numbering of instructions is known. // When the block already contains spill moves, the index must be increased until the // correct index is reached. - List<LIRInstruction> instructions = allocator.ir.getLIRforBlock(opBlock); + List<LIRInstruction> instructions = allocator.getLIR().getLIRforBlock(opBlock); int index = (opId - instructions.get(0).id()) >> 1; assert instructions.get(index).id() <= opId : "error in calculation"; @@ -845,7 +845,7 @@ * errors */ allocator.assignSpillSlot(interval); - Debug.dump(allocator.ir, description); + Debug.dump(allocator.getLIR(), description); allocator.printIntervals(description); throw new OutOfRegistersException("LinearScan: no register found", description); } @@ -892,7 +892,7 @@ } boolean noAllocationPossible(Interval interval) { - if (allocator.callKillsRegisters) { + if (allocator.callKillsRegisters()) { // fast calculation of intervals that can never get a register because the // the next instruction is a call that blocks all registers // Note: this only works if a call kills all registers @@ -917,7 +917,7 @@ } void initVarsForAlloc(Interval interval) { - AllocatableRegisters allocatableRegisters = allocator.regAllocConfig.getAllocatableRegisters(interval.kind().getPlatformKind()); + AllocatableRegisters allocatableRegisters = allocator.getRegisterAllocationConfig().getAllocatableRegisters(interval.kind().getPlatformKind()); availableRegs = allocatableRegisters.allocatableRegisters; minReg = allocatableRegisters.minRegisterNumber; maxReg = allocatableRegisters.maxRegisterNumber;
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/MoveResolver.java Mon Jul 27 16:26:41 2015 -0700 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/MoveResolver.java Mon Jul 27 16:57:30 2015 -0700 @@ -36,14 +36,14 @@ /** */ -class MoveResolver { +public class MoveResolver { private final LinearScan allocator; private int insertIdx; private LIRInsertionBuffer insertionBuffer; // buffer where moves are inserted - protected final List<Interval> mappingFrom; + private final List<Interval> mappingFrom; private final List<Value> mappingFromOpr; private final List<Interval> mappingTo; private boolean multipleReadsAllowed; @@ -58,6 +58,14 @@ } } + protected Interval getMappingFrom(int i) { + return mappingFrom.get(i); + } + + protected int mappingFromSize() { + return mappingFrom.size(); + } + protected int valueBlocked(Value location) { if (isRegister(location)) { return registerBlocked[asRegister(location).number]; @@ -81,7 +89,7 @@ return allocator; } - MoveResolver(LinearScan allocator) { + protected MoveResolver(LinearScan allocator) { this.allocator = allocator; this.multipleReadsAllowed = false; @@ -90,12 +98,12 @@ this.mappingTo = new ArrayList<>(8); this.insertIdx = -1; this.insertionBuffer = new LIRInsertionBuffer(); - this.registerBlocked = new int[allocator.registers.length]; + this.registerBlocked = new int[allocator.getRegisters().length]; } - boolean checkEmpty() { + protected boolean checkEmpty() { assert mappingFrom.size() == 0 && mappingFromOpr.size() == 0 && mappingTo.size() == 0 : "list must be empty before and after processing"; - for (int i = 0; i < getAllocator().registers.length; i++) { + for (int i = 0; i < getAllocator().getRegisters().length; i++) { assert registerBlocked[i] == 0 : "register map must be empty before and after processing"; } checkMultipleReads(); @@ -351,7 +359,7 @@ // one stack slot to another can happen (not allowed by LIRAssembler StackSlotValue spillSlot = fromInterval.spillSlot(); if (spillSlot == null) { - spillSlot = getAllocator().frameMapBuilder.allocateSpillSlot(fromInterval.kind()); + spillSlot = getAllocator().getFrameMapBuilder().allocateSpillSlot(fromInterval.kind()); fromInterval.setSpillSlot(spillSlot); } spillInterval(spillCandidate, fromInterval, spillSlot); @@ -420,7 +428,7 @@ this.insertIdx = newInsertIdx; } - void addMapping(Interval fromInterval, Interval toInterval) { + public void addMapping(Interval fromInterval, Interval toInterval) { if (isIllegal(toInterval.location()) && toInterval.canMaterialize()) { if (Debug.isLogEnabled()) { @@ -446,7 +454,7 @@ mappingTo.add(toInterval); } - void addMapping(Value fromOpr, Interval toInterval) { + public void addMapping(Value fromOpr, Interval toInterval) { if (Debug.isLogEnabled()) { Debug.log("add move mapping from %s to %s", fromOpr, toInterval); }
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/OptimizingLinearScanWalker.java Mon Jul 27 16:26:41 2015 -0700 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/OptimizingLinearScanWalker.java Mon Jul 27 16:57:30 2015 -0700 @@ -74,7 +74,7 @@ @Override void walk() { try (Scope s = Debug.scope("OptimizingLinearScanWalker")) { - for (AbstractBlockBase<?> block : allocator.sortedBlocks) { + for (AbstractBlockBase<?> block : allocator.sortedBlocks()) { optimizeBlock(block); } }
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/RegisterVerifier.java Mon Jul 27 16:26:41 2015 -0700 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/RegisterVerifier.java Mon Jul 27 16:57:30 2015 -0700 @@ -120,7 +120,7 @@ protected void printState(Interval[] inputState) { for (int i = 0; i < stateSize(); i++) { - Register reg = allocator.registers[i]; + Register reg = allocator.getRegisters()[i]; assert reg.number == i; if (inputState[i] != null) { Debug.log(" %6s %4d -- %s", reg, inputState[i].operandNumber, inputState[i]); @@ -202,7 +202,7 @@ } void processOperations(AbstractBlockBase<?> block, final Interval[] inputState) { - List<LIRInstruction> ops = allocator.ir.getLIRforBlock(block); + List<LIRInstruction> ops = allocator.getLIR().getLIRforBlock(block); InstructionValueConsumer useConsumer = new InstructionValueConsumer() { @Override @@ -242,7 +242,7 @@ op.visitEachInput(useConsumer); // invalidate all caller save registers at calls if (op.destroysCallerSavedRegisters()) { - for (Register r : allocator.regAllocConfig.getRegisterConfig().getCallerSaveRegisters()) { + for (Register r : allocator.getRegisterAllocationConfig().getRegisterConfig().getCallerSaveRegisters()) { statePut(inputState, r.asValue(), null); } }
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/SSALinarScanResolveDataFlowPhase.java Mon Jul 27 16:26:41 2015 -0700 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,89 +0,0 @@ -/* - * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved. - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. - * - * This code is free software; you can redistribute it and/or modify it - * under the terms of the GNU General Public License version 2 only, as - * published by the Free Software Foundation. - * - * This code is distributed in the hope that it will be useful, but WITHOUT - * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or - * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License - * version 2 for more details (a copy is included in the LICENSE file that - * accompanied this code). - * - * You should have received a copy of the GNU General Public License version - * 2 along with this work; if not, write to the Free Software Foundation, - * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. - * - * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA - * or visit www.oracle.com if you need additional information or have any - * questions. - */ -package com.oracle.graal.lir.alloc.lsra; - -import static jdk.internal.jvmci.code.ValueUtil.*; - -import java.util.*; - -import com.oracle.graal.debug.*; -import jdk.internal.jvmci.meta.*; - -import com.oracle.graal.compiler.common.cfg.*; -import com.oracle.graal.lir.*; -import com.oracle.graal.lir.ssa.*; -import com.oracle.graal.lir.ssa.SSAUtils.PhiValueVisitor; - -class SSALinarScanResolveDataFlowPhase extends LinearScanResolveDataFlowPhase { - - private static final DebugMetric numPhiResolutionMoves = Debug.metric("SSA LSRA[numPhiResolutionMoves]"); - private static final DebugMetric numStackToStackMoves = Debug.metric("SSA LSRA[numStackToStackMoves]"); - - SSALinarScanResolveDataFlowPhase(LinearScan allocator) { - super(allocator); - } - - @Override - void resolveCollectMappings(AbstractBlockBase<?> fromBlock, AbstractBlockBase<?> toBlock, AbstractBlockBase<?> midBlock, MoveResolver moveResolver) { - super.resolveCollectMappings(fromBlock, toBlock, midBlock, moveResolver); - - if (toBlock.getPredecessorCount() > 1) { - int toBlockFirstInstructionId = allocator.getFirstLirInstructionId(toBlock); - int fromBlockLastInstructionId = allocator.getLastLirInstructionId(fromBlock) + 1; - - AbstractBlockBase<?> phiOutBlock = midBlock != null ? midBlock : fromBlock; - List<LIRInstruction> instructions = allocator.ir.getLIRforBlock(phiOutBlock); - int phiOutIdx = SSAUtils.phiOutIndex(allocator.ir, phiOutBlock); - int phiOutId = midBlock != null ? fromBlockLastInstructionId : instructions.get(phiOutIdx).id(); - assert phiOutId >= 0; - - PhiValueVisitor visitor = new PhiValueVisitor() { - - public void visit(Value phiIn, Value phiOut) { - assert !isRegister(phiOut) : "phiOut is a register: " + phiOut; - assert !isRegister(phiIn) : "phiIn is a register: " + phiIn; - Interval toInterval = allocator.splitChildAtOpId(allocator.intervalFor(phiIn), toBlockFirstInstructionId, LIRInstruction.OperandMode.DEF); - if (isConstant(phiOut)) { - numPhiResolutionMoves.increment(); - moveResolver.addMapping(phiOut, toInterval); - } else { - Interval fromInterval = allocator.splitChildAtOpId(allocator.intervalFor(phiOut), phiOutId, LIRInstruction.OperandMode.DEF); - if (fromInterval != toInterval && !fromInterval.location().equals(toInterval.location())) { - numPhiResolutionMoves.increment(); - if (!(isStackSlotValue(toInterval.location()) && isStackSlotValue(fromInterval.location()))) { - moveResolver.addMapping(fromInterval, toInterval); - } else { - numStackToStackMoves.increment(); - moveResolver.addMapping(fromInterval, toInterval); - } - } - } - } - }; - - SSAUtils.forEachPhiValuePair(allocator.ir, toBlock, phiOutBlock, visitor); - SSAUtils.removePhiOut(allocator.ir, phiOutBlock); - } - } - -}
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/SSALinearScan.java Mon Jul 27 16:26:41 2015 -0700 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,80 +0,0 @@ -/* - * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved. - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. - * - * This code is free software; you can redistribute it and/or modify it - * under the terms of the GNU General Public License version 2 only, as - * published by the Free Software Foundation. - * - * This code is distributed in the hope that it will be useful, but WITHOUT - * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or - * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License - * version 2 for more details (a copy is included in the LICENSE file that - * accompanied this code). - * - * You should have received a copy of the GNU General Public License version - * 2 along with this work; if not, write to the Free Software Foundation, - * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. - * - * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA - * or visit www.oracle.com if you need additional information or have any - * questions. - */ -package com.oracle.graal.lir.alloc.lsra; - -import java.util.*; - -import jdk.internal.jvmci.code.*; -import com.oracle.graal.debug.*; -import com.oracle.graal.debug.Debug.*; - -import com.oracle.graal.compiler.common.alloc.*; -import com.oracle.graal.compiler.common.cfg.*; -import com.oracle.graal.lir.gen.*; -import com.oracle.graal.lir.gen.LIRGeneratorTool.SpillMoveFactory; -import com.oracle.graal.lir.ssa.*; - -final class SSALinearScan extends LinearScan { - - SSALinearScan(TargetDescription target, LIRGenerationResult res, SpillMoveFactory spillMoveFactory, RegisterAllocationConfig regAllocConfig, List<? extends AbstractBlockBase<?>> sortedBlocks) { - super(target, res, spillMoveFactory, regAllocConfig, sortedBlocks); - } - - @Override - protected MoveResolver createMoveResolver() { - SSAMoveResolver moveResolver = new SSAMoveResolver(this); - assert moveResolver.checkEmpty(); - return moveResolver; - } - - @Override - protected LinearScanLifetimeAnalysisPhase createLifetimeAnalysisPhase() { - return new SSALinearScanLifetimeAnalysisPhase(this); - } - - @Override - protected LinearScanResolveDataFlowPhase createResolveDataFlowPhase() { - return new SSALinarScanResolveDataFlowPhase(this); - } - - @Override - protected LinearScanEliminateSpillMovePhase createSpillMoveEliminationPhase() { - return new SSALinearScanEliminateSpillMovePhase(this); - } - - @Override - protected void beforeSpillMoveElimination() { - /* - * PHI Ins are needed for the RegisterVerifier, otherwise PHIs where the Out and In value - * matches (ie. there is no resolution move) are falsely detected as errors. - */ - try (Scope s1 = Debug.scope("Remove Phi In")) { - for (AbstractBlockBase<?> toBlock : sortedBlocks) { - if (toBlock.getPredecessorCount() > 1) { - SSAUtils.removePhiIn(ir, toBlock); - } - } - } - } - -}
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/SSALinearScanEliminateSpillMovePhase.java Mon Jul 27 16:26:41 2015 -0700 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,89 +0,0 @@ -/* - * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved. - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. - * - * This code is free software; you can redistribute it and/or modify it - * under the terms of the GNU General Public License version 2 only, as - * published by the Free Software Foundation. - * - * This code is distributed in the hope that it will be useful, but WITHOUT - * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or - * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License - * version 2 for more details (a copy is included in the LICENSE file that - * accompanied this code). - * - * You should have received a copy of the GNU General Public License version - * 2 along with this work; if not, write to the Free Software Foundation, - * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. - * - * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA - * or visit www.oracle.com if you need additional information or have any - * questions. - */ -package com.oracle.graal.lir.alloc.lsra; - -import static com.oracle.graal.compiler.common.BackendOptions.*; -import static com.oracle.graal.lir.LIRValueUtil.*; -import static jdk.internal.jvmci.code.ValueUtil.*; -import com.oracle.graal.debug.*; - -import com.oracle.graal.compiler.common.cfg.*; -import com.oracle.graal.lir.*; -import com.oracle.graal.lir.StandardOp.LabelOp; -import com.oracle.graal.lir.StandardOp.MoveOp; - -public class SSALinearScanEliminateSpillMovePhase extends LinearScanEliminateSpillMovePhase { - - SSALinearScanEliminateSpillMovePhase(LinearScan allocator) { - super(allocator); - } - - @Override - protected int firstInstructionOfInterest() { - // also look at Labels as they define PHI values - return 0; - } - - @Override - protected boolean canEliminateSpillMove(AbstractBlockBase<?> block, MoveOp move) { - assert isVariable(move.getResult()) || LinearScanVariant.getValue() == LSRAVariant.SSA_LSRA : "Move should not be produced in a non-SSA compilation: " + move; - - if (super.canEliminateSpillMove(block, move)) { - // SSA Linear Scan might introduce moves to stack slots - Interval curInterval = allocator.intervalFor(move.getResult()); - assert !isRegister(curInterval.location()) && curInterval.alwaysInMemory(); - if (!isPhiResolutionMove(block, move, curInterval)) { - assert isStackSlotValue(curInterval.location()) : "Not a stack slot: " + curInterval.location(); - return true; - } - } - return false; - } - - private boolean isPhiResolutionMove(AbstractBlockBase<?> block, MoveOp move, Interval toInterval) { - assert LinearScanVariant.getValue() == LSRAVariant.SSA_LSRA; - if (!toInterval.isSplitParent()) { - return false; - } - if ((toInterval.from() & 1) == 1) { - // phi intervals start at even positions. - return false; - } - if (block.getSuccessorCount() != 1) { - return false; - } - LIRInstruction op = allocator.instructionForId(toInterval.from()); - if (!(op instanceof LabelOp)) { - return false; - } - AbstractBlockBase<?> intStartBlock = allocator.blockForId(toInterval.from()); - assert allocator.ir.getLIRforBlock(intStartBlock).get(0).equals(op); - if (!block.getSuccessors().get(0).equals(intStartBlock)) { - return false; - } - try (Indent indet = Debug.indent()) { - Debug.log("Is a move (%s) to phi interval %s", move, toInterval); - } - return true; - } -}
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/SSALinearScanLifetimeAnalysisPhase.java Mon Jul 27 16:26:41 2015 -0700 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,87 +0,0 @@ -/* - * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved. - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. - * - * This code is free software; you can redistribute it and/or modify it - * under the terms of the GNU General Public License version 2 only, as - * published by the Free Software Foundation. - * - * This code is distributed in the hope that it will be useful, but WITHOUT - * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or - * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License - * version 2 for more details (a copy is included in the LICENSE file that - * accompanied this code). - * - * You should have received a copy of the GNU General Public License version - * 2 along with this work; if not, write to the Free Software Foundation, - * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. - * - * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA - * or visit www.oracle.com if you need additional information or have any - * questions. - */ -package com.oracle.graal.lir.alloc.lsra; - -import java.util.*; - -import com.oracle.graal.debug.*; -import jdk.internal.jvmci.meta.*; - -import com.oracle.graal.lir.*; -import com.oracle.graal.lir.LIRInstruction.OperandFlag; -import com.oracle.graal.lir.LIRInstruction.OperandMode; -import com.oracle.graal.lir.StandardOp.LabelOp; -import com.oracle.graal.lir.alloc.lsra.Interval.RegisterPriority; -import com.oracle.graal.lir.ssa.*; - -public class SSALinearScanLifetimeAnalysisPhase extends LinearScanLifetimeAnalysisPhase { - - SSALinearScanLifetimeAnalysisPhase(LinearScan linearScan) { - super(linearScan); - } - - @Override - void addRegisterHint(final LIRInstruction op, final Value targetValue, OperandMode mode, EnumSet<OperandFlag> flags, final boolean hintAtDef) { - super.addRegisterHint(op, targetValue, mode, flags, hintAtDef); - - if (hintAtDef && op instanceof LabelOp) { - LabelOp label = (LabelOp) op; - - Interval to = allocator.getOrCreateInterval((AllocatableValue) targetValue); - - SSAUtils.forEachPhiRegisterHint(allocator.ir, allocator.blockForId(label.id()), label, targetValue, mode, (ValueConsumer) (registerHint, valueMode, valueFlags) -> { - if (LinearScan.isVariableOrRegister(registerHint)) { - Interval from = allocator.getOrCreateInterval((AllocatableValue) registerHint); - - setHint(op, to, from); - setHint(op, from, to); - } - }); - } - } - - static void setHint(final LIRInstruction op, Interval target, Interval source) { - Interval currentHint = target.locationHint(false); - if (currentHint == null || currentHint.from() > target.from()) { - /* - * Update hint if there was none or if the hint interval starts after the hinted - * interval. - */ - target.setLocationHint(source); - if (Debug.isLogEnabled()) { - Debug.log("operation at opId %d: added hint from interval %d to %d", op.id(), source.operandNumber, target.operandNumber); - } - } - } - - @Override - protected RegisterPriority registerPriorityOfOutputOperand(LIRInstruction op) { - if (op instanceof LabelOp) { - LabelOp label = (LabelOp) op; - if (label.isPhiIn()) { - return RegisterPriority.None; - } - } - return super.registerPriorityOfOutputOperand(op); - } -}
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/SSAMoveResolver.java Mon Jul 27 16:26:41 2015 -0700 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,169 +0,0 @@ -/* - * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved. - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. - * - * This code is free software; you can redistribute it and/or modify it - * under the terms of the GNU General Public License version 2 only, as - * published by the Free Software Foundation. - * - * This code is distributed in the hope that it will be useful, but WITHOUT - * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or - * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License - * version 2 for more details (a copy is included in the LICENSE file that - * accompanied this code). - * - * You should have received a copy of the GNU General Public License version - * 2 along with this work; if not, write to the Free Software Foundation, - * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. - * - * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA - * or visit www.oracle.com if you need additional information or have any - * questions. - */ -package com.oracle.graal.lir.alloc.lsra; - -import static jdk.internal.jvmci.code.ValueUtil.*; - -import java.util.*; - -import jdk.internal.jvmci.code.*; -import jdk.internal.jvmci.common.*; -import jdk.internal.jvmci.meta.*; - -import com.oracle.graal.lir.*; -import com.oracle.graal.lir.framemap.*; - -final class SSAMoveResolver extends MoveResolver { - - private static final int STACK_SLOT_IN_CALLER_FRAME_IDX = -1; - private int[] stackBlocked; - private final int firstVirtualStackIndex; - - SSAMoveResolver(LinearScan allocator) { - super(allocator); - FrameMapBuilderTool frameMapBuilderTool = (FrameMapBuilderTool) allocator.frameMapBuilder; - FrameMap frameMap = frameMapBuilderTool.getFrameMap(); - this.stackBlocked = new int[frameMapBuilderTool.getNumberOfStackSlots()]; - this.firstVirtualStackIndex = !frameMap.frameNeedsAllocating() ? 0 : frameMap.currentFrameSize() + 1; - } - - @Override - boolean checkEmpty() { - for (int i = 0; i < stackBlocked.length; i++) { - assert stackBlocked[i] == 0 : "stack map must be empty before and after processing"; - } - return super.checkEmpty(); - } - - @Override - protected void checkMultipleReads() { - // multiple reads are allowed in SSA LSRA - } - - @Override - protected void verifyStackSlotMapping() { - // relax disjoint stack maps invariant - } - - @Override - protected boolean areMultipleReadsAllowed() { - return true; - } - - @Override - protected boolean mightBeBlocked(Value location) { - if (super.mightBeBlocked(location)) { - return true; - } - if (isStackSlotValue(location)) { - return true; - } - return false; - } - - private int getStackArrayIndex(StackSlotValue stackSlotValue) { - if (isStackSlot(stackSlotValue)) { - return getStackArrayIndex(asStackSlot(stackSlotValue)); - } - if (isVirtualStackSlot(stackSlotValue)) { - return getStackArrayIndex(asVirtualStackSlot(stackSlotValue)); - } - throw JVMCIError.shouldNotReachHere("Unhandled StackSlotValue: " + stackSlotValue); - } - - private int getStackArrayIndex(StackSlot stackSlot) { - int stackIdx; - if (stackSlot.isInCallerFrame()) { - // incoming stack arguments can be ignored - stackIdx = STACK_SLOT_IN_CALLER_FRAME_IDX; - } else { - assert stackSlot.getRawAddFrameSize() : "Unexpected stack slot: " + stackSlot; - int offset = -stackSlot.getRawOffset(); - assert 0 <= offset && offset < firstVirtualStackIndex : String.format("Wrong stack slot offset: %d (first virtual stack slot index: %d", offset, firstVirtualStackIndex); - stackIdx = offset; - } - return stackIdx; - } - - private int getStackArrayIndex(VirtualStackSlot virtualStackSlot) { - return firstVirtualStackIndex + virtualStackSlot.getId(); - } - - @Override - protected void setValueBlocked(Value location, int direction) { - assert direction == 1 || direction == -1 : "out of bounds"; - if (isStackSlotValue(location)) { - int stackIdx = getStackArrayIndex(asStackSlotValue(location)); - if (stackIdx == STACK_SLOT_IN_CALLER_FRAME_IDX) { - // incoming stack arguments can be ignored - return; - } - if (stackIdx >= stackBlocked.length) { - stackBlocked = Arrays.copyOf(stackBlocked, stackIdx + 1); - } - stackBlocked[stackIdx] += direction; - } else { - super.setValueBlocked(location, direction); - } - } - - @Override - protected int valueBlocked(Value location) { - if (isStackSlotValue(location)) { - int stackIdx = getStackArrayIndex(asStackSlotValue(location)); - if (stackIdx == STACK_SLOT_IN_CALLER_FRAME_IDX) { - // incoming stack arguments are always blocked (aka they can not be written) - return 1; - } - if (stackIdx >= stackBlocked.length) { - return 0; - } - return stackBlocked[stackIdx]; - } - return super.valueBlocked(location); - } - - @Override - protected LIRInstruction createMove(AllocatableValue fromOpr, AllocatableValue toOpr, AllocatableValue fromLocation, AllocatableValue toLocation) { - if (isStackSlotValue(toLocation) && isStackSlotValue(fromLocation)) { - return getAllocator().getSpillMoveFactory().createStackMove(toOpr, fromOpr); - } - return super.createMove(fromOpr, toOpr, fromLocation, toLocation); - } - - @Override - protected void breakCycle(int spillCandidate) { - if (spillCandidate != -1) { - super.breakCycle(spillCandidate); - return; - } - assert mappingFrom.size() > 1; - // Arbitrarily select the first entry for spilling. - int stackSpillCandidate = 0; - Interval fromInterval = mappingFrom.get(stackSpillCandidate); - assert isStackSlotValue(fromInterval.location()); - // allocate new stack slot - StackSlotValue spillSlot = getAllocator().frameMapBuilder.allocateSpillSlot(fromInterval.kind()); - spillInterval(stackSpillCandidate, fromInterval, spillSlot); - } -}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/ssa/SSALinarScanResolveDataFlowPhase.java Mon Jul 27 16:57:30 2015 -0700 @@ -0,0 +1,91 @@ +/* + * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.lir.alloc.lsra.ssa; + +import static jdk.internal.jvmci.code.ValueUtil.*; + +import java.util.*; + +import com.oracle.graal.debug.*; + +import jdk.internal.jvmci.meta.*; + +import com.oracle.graal.compiler.common.cfg.*; +import com.oracle.graal.lir.*; +import com.oracle.graal.lir.alloc.lsra.*; +import com.oracle.graal.lir.ssa.*; +import com.oracle.graal.lir.ssa.SSAUtil.PhiValueVisitor; + +class SSALinarScanResolveDataFlowPhase extends LinearScanResolveDataFlowPhase { + + private static final DebugMetric numPhiResolutionMoves = Debug.metric("SSA LSRA[numPhiResolutionMoves]"); + private static final DebugMetric numStackToStackMoves = Debug.metric("SSA LSRA[numStackToStackMoves]"); + + SSALinarScanResolveDataFlowPhase(LinearScan allocator) { + super(allocator); + } + + @Override + protected void resolveCollectMappings(AbstractBlockBase<?> fromBlock, AbstractBlockBase<?> toBlock, AbstractBlockBase<?> midBlock, MoveResolver moveResolver) { + super.resolveCollectMappings(fromBlock, toBlock, midBlock, moveResolver); + + if (toBlock.getPredecessorCount() > 1) { + int toBlockFirstInstructionId = allocator.getFirstLirInstructionId(toBlock); + int fromBlockLastInstructionId = allocator.getLastLirInstructionId(fromBlock) + 1; + + AbstractBlockBase<?> phiOutBlock = midBlock != null ? midBlock : fromBlock; + List<LIRInstruction> instructions = allocator.getLIR().getLIRforBlock(phiOutBlock); + int phiOutIdx = SSAUtil.phiOutIndex(allocator.getLIR(), phiOutBlock); + int phiOutId = midBlock != null ? fromBlockLastInstructionId : instructions.get(phiOutIdx).id(); + assert phiOutId >= 0; + + PhiValueVisitor visitor = new PhiValueVisitor() { + + public void visit(Value phiIn, Value phiOut) { + assert !isRegister(phiOut) : "phiOut is a register: " + phiOut; + assert !isRegister(phiIn) : "phiIn is a register: " + phiIn; + Interval toInterval = allocator.splitChildAtOpId(allocator.intervalFor(phiIn), toBlockFirstInstructionId, LIRInstruction.OperandMode.DEF); + if (isConstant(phiOut)) { + numPhiResolutionMoves.increment(); + moveResolver.addMapping(phiOut, toInterval); + } else { + Interval fromInterval = allocator.splitChildAtOpId(allocator.intervalFor(phiOut), phiOutId, LIRInstruction.OperandMode.DEF); + if (fromInterval != toInterval && !fromInterval.location().equals(toInterval.location())) { + numPhiResolutionMoves.increment(); + if (!(isStackSlotValue(toInterval.location()) && isStackSlotValue(fromInterval.location()))) { + moveResolver.addMapping(fromInterval, toInterval); + } else { + numStackToStackMoves.increment(); + moveResolver.addMapping(fromInterval, toInterval); + } + } + } + } + }; + + SSAUtil.forEachPhiValuePair(allocator.getLIR(), toBlock, phiOutBlock, visitor); + SSAUtil.removePhiOut(allocator.getLIR(), phiOutBlock); + } + } + +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/ssa/SSALinearScan.java Mon Jul 27 16:57:30 2015 -0700 @@ -0,0 +1,82 @@ +/* + * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.lir.alloc.lsra.ssa; + +import java.util.*; + +import jdk.internal.jvmci.code.*; + +import com.oracle.graal.debug.*; +import com.oracle.graal.debug.Debug.*; +import com.oracle.graal.compiler.common.alloc.*; +import com.oracle.graal.compiler.common.cfg.*; +import com.oracle.graal.lir.alloc.lsra.*; +import com.oracle.graal.lir.gen.*; +import com.oracle.graal.lir.gen.LIRGeneratorTool.SpillMoveFactory; +import com.oracle.graal.lir.ssa.*; + +public final class SSALinearScan extends LinearScan { + + public SSALinearScan(TargetDescription target, LIRGenerationResult res, SpillMoveFactory spillMoveFactory, RegisterAllocationConfig regAllocConfig, + List<? extends AbstractBlockBase<?>> sortedBlocks) { + super(target, res, spillMoveFactory, regAllocConfig, sortedBlocks); + } + + @Override + protected MoveResolver createMoveResolver() { + SSAMoveResolver moveResolver = new SSAMoveResolver(this); + assert moveResolver.checkEmpty(); + return moveResolver; + } + + @Override + protected LinearScanLifetimeAnalysisPhase createLifetimeAnalysisPhase() { + return new SSALinearScanLifetimeAnalysisPhase(this); + } + + @Override + protected LinearScanResolveDataFlowPhase createResolveDataFlowPhase() { + return new SSALinarScanResolveDataFlowPhase(this); + } + + @Override + protected LinearScanEliminateSpillMovePhase createSpillMoveEliminationPhase() { + return new SSALinearScanEliminateSpillMovePhase(this); + } + + @Override + protected void beforeSpillMoveElimination() { + /* + * PHI Ins are needed for the RegisterVerifier, otherwise PHIs where the Out and In value + * matches (ie. there is no resolution move) are falsely detected as errors. + */ + try (Scope s1 = Debug.scope("Remove Phi In")) { + for (AbstractBlockBase<?> toBlock : sortedBlocks()) { + if (toBlock.getPredecessorCount() > 1) { + SSAUtil.removePhiIn(getLIR(), toBlock); + } + } + } + } + +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/ssa/SSALinearScanEliminateSpillMovePhase.java Mon Jul 27 16:57:30 2015 -0700 @@ -0,0 +1,90 @@ +/* + * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.lir.alloc.lsra.ssa; + +import static com.oracle.graal.compiler.common.BackendOptions.*; +import static com.oracle.graal.lir.LIRValueUtil.*; +import static jdk.internal.jvmci.code.ValueUtil.*; + +import com.oracle.graal.debug.*; +import com.oracle.graal.compiler.common.cfg.*; +import com.oracle.graal.lir.*; +import com.oracle.graal.lir.StandardOp.LabelOp; +import com.oracle.graal.lir.StandardOp.MoveOp; +import com.oracle.graal.lir.alloc.lsra.*; + +public class SSALinearScanEliminateSpillMovePhase extends LinearScanEliminateSpillMovePhase { + + SSALinearScanEliminateSpillMovePhase(LinearScan allocator) { + super(allocator); + } + + @Override + protected int firstInstructionOfInterest() { + // also look at Labels as they define PHI values + return 0; + } + + @Override + protected boolean canEliminateSpillMove(AbstractBlockBase<?> block, MoveOp move) { + assert isVariable(move.getResult()) || LinearScanVariant.getValue() == LSRAVariant.SSA_LSRA : "Move should not be produced in a non-SSA compilation: " + move; + + if (super.canEliminateSpillMove(block, move)) { + // SSA Linear Scan might introduce moves to stack slots + Interval curInterval = allocator.intervalFor(move.getResult()); + assert !isRegister(curInterval.location()) && curInterval.alwaysInMemory(); + if (!isPhiResolutionMove(block, move, curInterval)) { + assert isStackSlotValue(curInterval.location()) : "Not a stack slot: " + curInterval.location(); + return true; + } + } + return false; + } + + private boolean isPhiResolutionMove(AbstractBlockBase<?> block, MoveOp move, Interval toInterval) { + assert LinearScanVariant.getValue() == LSRAVariant.SSA_LSRA; + if (!toInterval.isSplitParent()) { + return false; + } + if ((toInterval.from() & 1) == 1) { + // phi intervals start at even positions. + return false; + } + if (block.getSuccessorCount() != 1) { + return false; + } + LIRInstruction op = allocator.instructionForId(toInterval.from()); + if (!(op instanceof LabelOp)) { + return false; + } + AbstractBlockBase<?> intStartBlock = allocator.blockForId(toInterval.from()); + assert allocator.getLIR().getLIRforBlock(intStartBlock).get(0).equals(op); + if (!block.getSuccessors().get(0).equals(intStartBlock)) { + return false; + } + try (Indent indet = Debug.indent()) { + Debug.log("Is a move (%s) to phi interval %s", move, toInterval); + } + return true; + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/ssa/SSALinearScanLifetimeAnalysisPhase.java Mon Jul 27 16:57:30 2015 -0700 @@ -0,0 +1,89 @@ +/* + * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.lir.alloc.lsra.ssa; + +import java.util.*; + +import com.oracle.graal.debug.*; + +import jdk.internal.jvmci.meta.*; + +import com.oracle.graal.lir.*; +import com.oracle.graal.lir.LIRInstruction.OperandFlag; +import com.oracle.graal.lir.LIRInstruction.OperandMode; +import com.oracle.graal.lir.StandardOp.LabelOp; +import com.oracle.graal.lir.alloc.lsra.*; +import com.oracle.graal.lir.alloc.lsra.Interval.RegisterPriority; +import com.oracle.graal.lir.ssa.*; + +public class SSALinearScanLifetimeAnalysisPhase extends LinearScanLifetimeAnalysisPhase { + + SSALinearScanLifetimeAnalysisPhase(LinearScan linearScan) { + super(linearScan); + } + + @Override + protected void addRegisterHint(final LIRInstruction op, final Value targetValue, OperandMode mode, EnumSet<OperandFlag> flags, final boolean hintAtDef) { + super.addRegisterHint(op, targetValue, mode, flags, hintAtDef); + + if (hintAtDef && op instanceof LabelOp) { + LabelOp label = (LabelOp) op; + + Interval to = allocator.getOrCreateInterval((AllocatableValue) targetValue); + + SSAUtil.forEachPhiRegisterHint(allocator.getLIR(), allocator.blockForId(label.id()), label, targetValue, mode, (ValueConsumer) (registerHint, valueMode, valueFlags) -> { + if (LinearScan.isVariableOrRegister(registerHint)) { + Interval from = allocator.getOrCreateInterval((AllocatableValue) registerHint); + + setHint(op, to, from); + setHint(op, from, to); + } + }); + } + } + + public static void setHint(final LIRInstruction op, Interval target, Interval source) { + Interval currentHint = target.locationHint(false); + if (currentHint == null || currentHint.from() > target.from()) { + /* + * Update hint if there was none or if the hint interval starts after the hinted + * interval. + */ + target.setLocationHint(source); + if (Debug.isLogEnabled()) { + Debug.log("operation at opId %d: added hint from interval %d to %d", op.id(), source.operandNumber, target.operandNumber); + } + } + } + + @Override + protected RegisterPriority registerPriorityOfOutputOperand(LIRInstruction op) { + if (op instanceof LabelOp) { + LabelOp label = (LabelOp) op; + if (label.isPhiIn()) { + return RegisterPriority.None; + } + } + return super.registerPriorityOfOutputOperand(op); + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/ssa/SSAMoveResolver.java Mon Jul 27 16:57:30 2015 -0700 @@ -0,0 +1,170 @@ +/* + * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.lir.alloc.lsra.ssa; + +import static jdk.internal.jvmci.code.ValueUtil.*; + +import java.util.*; + +import jdk.internal.jvmci.code.*; +import jdk.internal.jvmci.common.*; +import jdk.internal.jvmci.meta.*; + +import com.oracle.graal.lir.*; +import com.oracle.graal.lir.alloc.lsra.*; +import com.oracle.graal.lir.framemap.*; + +public final class SSAMoveResolver extends MoveResolver { + + private static final int STACK_SLOT_IN_CALLER_FRAME_IDX = -1; + private int[] stackBlocked; + private final int firstVirtualStackIndex; + + public SSAMoveResolver(LinearScan allocator) { + super(allocator); + FrameMapBuilderTool frameMapBuilderTool = (FrameMapBuilderTool) allocator.getFrameMapBuilder(); + FrameMap frameMap = frameMapBuilderTool.getFrameMap(); + this.stackBlocked = new int[frameMapBuilderTool.getNumberOfStackSlots()]; + this.firstVirtualStackIndex = !frameMap.frameNeedsAllocating() ? 0 : frameMap.currentFrameSize() + 1; + } + + @Override + public boolean checkEmpty() { + for (int i = 0; i < stackBlocked.length; i++) { + assert stackBlocked[i] == 0 : "stack map must be empty before and after processing"; + } + return super.checkEmpty(); + } + + @Override + protected void checkMultipleReads() { + // multiple reads are allowed in SSA LSRA + } + + @Override + protected void verifyStackSlotMapping() { + // relax disjoint stack maps invariant + } + + @Override + protected boolean areMultipleReadsAllowed() { + return true; + } + + @Override + protected boolean mightBeBlocked(Value location) { + if (super.mightBeBlocked(location)) { + return true; + } + if (isStackSlotValue(location)) { + return true; + } + return false; + } + + private int getStackArrayIndex(StackSlotValue stackSlotValue) { + if (isStackSlot(stackSlotValue)) { + return getStackArrayIndex(asStackSlot(stackSlotValue)); + } + if (isVirtualStackSlot(stackSlotValue)) { + return getStackArrayIndex(asVirtualStackSlot(stackSlotValue)); + } + throw JVMCIError.shouldNotReachHere("Unhandled StackSlotValue: " + stackSlotValue); + } + + private int getStackArrayIndex(StackSlot stackSlot) { + int stackIdx; + if (stackSlot.isInCallerFrame()) { + // incoming stack arguments can be ignored + stackIdx = STACK_SLOT_IN_CALLER_FRAME_IDX; + } else { + assert stackSlot.getRawAddFrameSize() : "Unexpected stack slot: " + stackSlot; + int offset = -stackSlot.getRawOffset(); + assert 0 <= offset && offset < firstVirtualStackIndex : String.format("Wrong stack slot offset: %d (first virtual stack slot index: %d", offset, firstVirtualStackIndex); + stackIdx = offset; + } + return stackIdx; + } + + private int getStackArrayIndex(VirtualStackSlot virtualStackSlot) { + return firstVirtualStackIndex + virtualStackSlot.getId(); + } + + @Override + protected void setValueBlocked(Value location, int direction) { + assert direction == 1 || direction == -1 : "out of bounds"; + if (isStackSlotValue(location)) { + int stackIdx = getStackArrayIndex(asStackSlotValue(location)); + if (stackIdx == STACK_SLOT_IN_CALLER_FRAME_IDX) { + // incoming stack arguments can be ignored + return; + } + if (stackIdx >= stackBlocked.length) { + stackBlocked = Arrays.copyOf(stackBlocked, stackIdx + 1); + } + stackBlocked[stackIdx] += direction; + } else { + super.setValueBlocked(location, direction); + } + } + + @Override + protected int valueBlocked(Value location) { + if (isStackSlotValue(location)) { + int stackIdx = getStackArrayIndex(asStackSlotValue(location)); + if (stackIdx == STACK_SLOT_IN_CALLER_FRAME_IDX) { + // incoming stack arguments are always blocked (aka they can not be written) + return 1; + } + if (stackIdx >= stackBlocked.length) { + return 0; + } + return stackBlocked[stackIdx]; + } + return super.valueBlocked(location); + } + + @Override + protected LIRInstruction createMove(AllocatableValue fromOpr, AllocatableValue toOpr, AllocatableValue fromLocation, AllocatableValue toLocation) { + if (isStackSlotValue(toLocation) && isStackSlotValue(fromLocation)) { + return getAllocator().getSpillMoveFactory().createStackMove(toOpr, fromOpr); + } + return super.createMove(fromOpr, toOpr, fromLocation, toLocation); + } + + @Override + protected void breakCycle(int spillCandidate) { + if (spillCandidate != -1) { + super.breakCycle(spillCandidate); + return; + } + assert mappingFromSize() > 1; + // Arbitrarily select the first entry for spilling. + int stackSpillCandidate = 0; + Interval fromInterval = getMappingFrom(stackSpillCandidate); + assert isStackSlotValue(fromInterval.location()); + // allocate new stack slot + StackSlotValue spillSlot = getAllocator().getFrameMapBuilder().allocateSpillSlot(fromInterval.kind()); + spillInterval(stackSpillCandidate, fromInterval, spillSlot); + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/ssi/SSILinearScan.java Mon Jul 27 16:57:30 2015 -0700 @@ -0,0 +1,72 @@ +/* + * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.lir.alloc.lsra.ssi; + +import java.util.*; + +import jdk.internal.jvmci.code.*; + +import com.oracle.graal.compiler.common.alloc.*; +import com.oracle.graal.compiler.common.cfg.*; +import com.oracle.graal.lir.alloc.lsra.*; +import com.oracle.graal.lir.alloc.lsra.ssa.*; +import com.oracle.graal.lir.gen.*; +import com.oracle.graal.lir.gen.LIRGeneratorTool.SpillMoveFactory; +import com.oracle.graal.lir.ssi.*; + +public final class SSILinearScan extends LinearScan { + + public SSILinearScan(TargetDescription target, LIRGenerationResult res, SpillMoveFactory spillMoveFactory, RegisterAllocationConfig regAllocConfig, + List<? extends AbstractBlockBase<?>> sortedBlocks) { + super(target, res, spillMoveFactory, regAllocConfig, sortedBlocks); + } + + @Override + protected <B extends AbstractBlockBase<B>> void allocate(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder, + SpillMoveFactory spillMoveFactory, RegisterAllocationConfig registerAllocationConfig) { + assert SSIVerifier.verify(lirGenRes.getLIR()) : "LIR not in SSI form."; + super.allocate(target, lirGenRes, codeEmittingOrder, linearScanOrder, spillMoveFactory, registerAllocationConfig); + } + + @Override + protected MoveResolver createMoveResolver() { + SSAMoveResolver moveResolver = new SSAMoveResolver(this); + assert moveResolver.checkEmpty(); + return moveResolver; + } + + @Override + protected LinearScanLifetimeAnalysisPhase createLifetimeAnalysisPhase() { + return new SSILinearScanLifetimeAnalysisPhase(this); + } + + @Override + protected LinearScanResolveDataFlowPhase createResolveDataFlowPhase() { + return new SSILinearScanResolveDataFlowPhase(this); + } + + @Override + protected LinearScanEliminateSpillMovePhase createSpillMoveEliminationPhase() { + return new SSILinearScanEliminateSpillMovePhase(this); + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/ssi/SSILinearScanEliminateSpillMovePhase.java Mon Jul 27 16:57:30 2015 -0700 @@ -0,0 +1,46 @@ +/* + * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.lir.alloc.lsra.ssi; + +import com.oracle.graal.compiler.common.cfg.*; +import com.oracle.graal.lir.StandardOp.MoveOp; +import com.oracle.graal.lir.alloc.lsra.*; + +public class SSILinearScanEliminateSpillMovePhase extends LinearScanEliminateSpillMovePhase { + + public SSILinearScanEliminateSpillMovePhase(LinearScan allocator) { + super(allocator); + } + + @Override + protected int firstInstructionOfInterest() { + // also look at Labels as they define PHI values + return 0; + } + + @Override + protected boolean canEliminateSpillMove(AbstractBlockBase<?> block, MoveOp move) { + // TODO (je) do not eliminate spill moves yet! + return false; + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/ssi/SSILinearScanLifetimeAnalysisPhase.java Mon Jul 27 16:57:30 2015 -0700 @@ -0,0 +1,123 @@ +/* + * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.lir.alloc.lsra.ssi; + +import static com.oracle.graal.lir.alloc.lsra.ssa.SSALinearScanLifetimeAnalysisPhase.*; + +import java.util.*; + +import jdk.internal.jvmci.code.*; +import jdk.internal.jvmci.meta.*; + +import com.oracle.graal.lir.*; +import com.oracle.graal.lir.LIRInstruction.OperandFlag; +import com.oracle.graal.lir.LIRInstruction.OperandMode; +import com.oracle.graal.lir.StandardOp.LabelOp; +import com.oracle.graal.lir.alloc.lsra.*; +import com.oracle.graal.lir.alloc.lsra.Interval.RegisterPriority; +import com.oracle.graal.lir.alloc.lsra.Interval.SpillState; +import com.oracle.graal.lir.ssi.*; + +public class SSILinearScanLifetimeAnalysisPhase extends LinearScanLifetimeAnalysisPhase { + + public SSILinearScanLifetimeAnalysisPhase(LinearScan linearScan) { + super(linearScan); + } + + @Override + protected void addRegisterHint(final LIRInstruction op, final Value targetValue, OperandMode mode, EnumSet<OperandFlag> flags, final boolean hintAtDef) { + super.addRegisterHint(op, targetValue, mode, flags, hintAtDef); + + if (hintAtDef && op instanceof LabelOp) { + LabelOp label = (LabelOp) op; + + Interval to = allocator.getOrCreateInterval((AllocatableValue) targetValue); + + SSIUtil.forEachRegisterHint(allocator.getLIR(), allocator.blockForId(label.id()), label, targetValue, mode, (ValueConsumer) (registerHint, valueMode, valueFlags) -> { + if (LinearScan.isVariableOrRegister(registerHint)) { + Interval from = allocator.getOrCreateInterval((AllocatableValue) registerHint); + + setHint(op, to, from); + setHint(op, from, to); + } + }); + } + } + + @Override + protected void changeSpillDefinitionPos(LIRInstruction op, AllocatableValue operand, Interval interval, int defPos) { + assert interval.isSplitParent() : "can only be called for split parents"; + + switch (interval.spillState()) { + case NoDefinitionFound: + // assert interval.spillDefinitionPos() == -1 : "must no be set before"; + interval.setSpillDefinitionPos(defPos); + if (!(op instanceof LabelOp)) { + // Do not update state for labels. This will be done afterwards. + interval.setSpillState(SpillState.NoSpillStore); + } + break; + + case NoSpillStore: + assert defPos <= interval.spillDefinitionPos() : "positions are processed in reverse order when intervals are created"; + if (defPos < interval.spillDefinitionPos() - 2) { + // second definition found, so no spill optimization possible for this interval + interval.setSpillState(SpillState.NoOptimization); + } else { + // two consecutive definitions (because of two-operand LIR form) + assert allocator.blockForId(defPos) == allocator.blockForId(interval.spillDefinitionPos()) : "block must be equal"; + } + break; + + case NoOptimization: + // nothing to do + break; + + default: + throw new BailoutException("other states not allowed at this time"); + } + } + + @Override + protected void buildIntervals() { + super.buildIntervals(); + for (Interval interval : allocator.intervals()) { + if (interval != null && interval.spillState().equals(SpillState.NoDefinitionFound) && interval.spillDefinitionPos() != -1) { + // there was a definition in a phi/sigma + interval.setSpillState(SpillState.NoSpillStore); + } + } + } + + @Override + protected RegisterPriority registerPriorityOfOutputOperand(LIRInstruction op) { + if (op instanceof LabelOp) { + LabelOp label = (LabelOp) op; + if (label.id() != 0) { + // skip method header + return RegisterPriority.None; + } + } + return super.registerPriorityOfOutputOperand(op); + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/ssi/SSILinearScanResolveDataFlowPhase.java Mon Jul 27 16:57:30 2015 -0700 @@ -0,0 +1,128 @@ +/* + * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.lir.alloc.lsra.ssi; + +import static jdk.internal.jvmci.code.ValueUtil.*; + +import java.util.*; + +import jdk.internal.jvmci.meta.*; + +import com.oracle.graal.compiler.common.*; +import com.oracle.graal.compiler.common.cfg.*; +import com.oracle.graal.debug.*; +import com.oracle.graal.lir.*; +import com.oracle.graal.lir.alloc.lsra.*; +import com.oracle.graal.lir.ssa.SSAUtil.PhiValueVisitor; +import com.oracle.graal.lir.ssi.*; + +public class SSILinearScanResolveDataFlowPhase extends LinearScanResolveDataFlowPhase { + + private static final DebugMetric numSSIResolutionMoves = Debug.metric("SSI LSRA[numSSIResolutionMoves]"); + private static final DebugMetric numStackToStackMoves = Debug.metric("SSI LSRA[numStackToStackMoves]"); + + public SSILinearScanResolveDataFlowPhase(LinearScan allocator) { + super(allocator); + } + + @Override + protected void resolveDataFlow() { + super.resolveDataFlow(); + /* + * Incoming Values are needed for the RegisterVerifier, otherwise SIGMAs/PHIs where the Out + * and In value matches (ie. there is no resolution move) are falsely detected as errors. + */ + for (AbstractBlockBase<?> toBlock : allocator.sortedBlocks()) { + if (toBlock.getPredecessorCount() != 0) { + SSIUtil.removeIncoming(allocator.getLIR(), toBlock); + } else { + assert allocator.getLIR().getControlFlowGraph().getStartBlock().equals(toBlock); + } + SSIUtil.removeOutgoing(allocator.getLIR(), toBlock); + } + } + + @Override + protected void resolveCollectMappings(AbstractBlockBase<?> fromBlock, AbstractBlockBase<?> toBlock, AbstractBlockBase<?> midBlock, MoveResolver moveResolver) { + super.resolveCollectMappings(fromBlock, toBlock, midBlock, moveResolver); + + if (midBlock != null) { + HashMap<Value, Value> map = CollectionsFactory.newMap(); + SSIUtil.forEachValuePair(allocator.getLIR(), midBlock, fromBlock, (to, from) -> map.put(to, from)); + + MyPhiValueVisitor visitor = new MyPhiValueVisitor(moveResolver, toBlock, fromBlock); + SSIUtil.forEachValuePair(allocator.getLIR(), toBlock, midBlock, (to, from) -> { + Value phiOut = isConstant(from) ? from : map.get(from); + assert phiOut != null : "No entry for " + from; + visitor.visit(to, phiOut); + }); + } else { + // default case + SSIUtil.forEachValuePair(allocator.getLIR(), toBlock, fromBlock, new MyPhiValueVisitor(moveResolver, toBlock, fromBlock)); + } + + } + + private class MyPhiValueVisitor implements PhiValueVisitor { + final MoveResolver moveResolver; + final int toId; + final int fromId; + + public MyPhiValueVisitor(MoveResolver moveResolver, AbstractBlockBase<?> toBlock, AbstractBlockBase<?> fromBlock) { + this.moveResolver = moveResolver; + toId = allocator.getFirstLirInstructionId(toBlock); + fromId = allocator.getLastLirInstructionId(fromBlock); + assert fromId >= 0; + } + + public void visit(Value phiIn, Value phiOut) { + assert !isRegister(phiOut) : "Out is a register: " + phiOut; + assert !isRegister(phiIn) : "In is a register: " + phiIn; + if (Value.ILLEGAL.equals(phiIn)) { + // The value not needed in this branch. + return; + } + if (isVirtualStackSlot(phiIn) && isVirtualStackSlot(phiOut) && phiIn.equals(phiOut)) { + // no need to handle virtual stack slots + return; + } + Interval toInterval = allocator.splitChildAtOpId(allocator.intervalFor(phiIn), toId, LIRInstruction.OperandMode.DEF); + if (isConstant(phiOut)) { + numSSIResolutionMoves.increment(); + moveResolver.addMapping(phiOut, toInterval); + } else { + Interval fromInterval = allocator.splitChildAtOpId(allocator.intervalFor(phiOut), fromId, LIRInstruction.OperandMode.DEF); + if (fromInterval != toInterval) { + numSSIResolutionMoves.increment(); + if (!(isStackSlotValue(toInterval.location()) && isStackSlotValue(fromInterval.location()))) { + moveResolver.addMapping(fromInterval, toInterval); + } else { + numStackToStackMoves.increment(); + moveResolver.addMapping(fromInterval, toInterval); + } + } + } + } + } + +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceGlobalMoveResolver.java Mon Jul 27 16:57:30 2015 -0700 @@ -0,0 +1,408 @@ +/* + * Copyright (c) 2009, 2014, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.lir.alloc.trace; + +import static jdk.internal.jvmci.code.ValueUtil.*; + +import java.util.*; + +import jdk.internal.jvmci.code.*; +import jdk.internal.jvmci.common.*; +import jdk.internal.jvmci.meta.*; + +import com.oracle.graal.debug.*; +import com.oracle.graal.lir.*; +import com.oracle.graal.lir.alloc.lsra.*; +import com.oracle.graal.lir.framemap.*; +import com.oracle.graal.lir.gen.*; +import com.oracle.graal.lir.gen.LIRGeneratorTool.SpillMoveFactory; + +/** + */ +class TraceGlobalMoveResolver { + + private int insertIdx; + private LIRInsertionBuffer insertionBuffer; // buffer where moves are inserted + + private final List<Value> mappingFrom; + private final List<AllocatableValue> mappingTo; + private final int[] registerBlocked; + private static final int STACK_SLOT_IN_CALLER_FRAME_IDX = -1; + private int[] stackBlocked; + private final int firstVirtualStackIndex; + private final SpillMoveFactory spillMoveFactory; + private final FrameMapBuilder frameMapBuilder; + + private void setValueBlocked(Value location, int direction) { + assert direction == 1 || direction == -1 : "out of bounds"; + if (isStackSlotValue(location)) { + int stackIdx = getStackArrayIndex(asStackSlotValue(location)); + if (stackIdx == STACK_SLOT_IN_CALLER_FRAME_IDX) { + // incoming stack arguments can be ignored + return; + } + if (stackIdx >= stackBlocked.length) { + stackBlocked = Arrays.copyOf(stackBlocked, stackIdx + 1); + } + stackBlocked[stackIdx] += direction; + } else { + assert direction == 1 || direction == -1 : "out of bounds"; + if (isRegister(location)) { + registerBlocked[asRegister(location).number] += direction; + } else { + throw JVMCIError.shouldNotReachHere("unhandled value " + location); + } + } + } + + private int valueBlocked(Value location) { + if (isStackSlotValue(location)) { + int stackIdx = getStackArrayIndex(asStackSlotValue(location)); + if (stackIdx == STACK_SLOT_IN_CALLER_FRAME_IDX) { + // incoming stack arguments are always blocked (aka they can not be written) + return 1; + } + if (stackIdx >= stackBlocked.length) { + return 0; + } + return stackBlocked[stackIdx]; + } + if (isRegister(location)) { + return registerBlocked[asRegister(location).number]; + } + throw JVMCIError.shouldNotReachHere("unhandled value " + location); + } + + private static boolean areMultipleReadsAllowed() { + return true; + } + + private boolean hasMappings() { + return mappingFrom.size() > 0; + } + + private SpillMoveFactory getSpillMoveFactory() { + return spillMoveFactory; + } + + private Register[] getRegisters() { + return frameMapBuilder.getRegisterConfig().getAllocatableRegisters(); + } + + public TraceGlobalMoveResolver(LIRGenerationResult res, SpillMoveFactory spillMoveFactory, Architecture arch) { + + this.mappingFrom = new ArrayList<>(8); + this.mappingTo = new ArrayList<>(8); + this.insertIdx = -1; + this.insertionBuffer = new LIRInsertionBuffer(); + + this.frameMapBuilder = res.getFrameMapBuilder(); + this.spillMoveFactory = spillMoveFactory; + this.registerBlocked = new int[arch.getRegisters().length]; + + FrameMapBuilderTool frameMapBuilderTool = (FrameMapBuilderTool) frameMapBuilder; + this.stackBlocked = new int[frameMapBuilderTool.getNumberOfStackSlots()]; + + FrameMap frameMap = frameMapBuilderTool.getFrameMap(); + this.firstVirtualStackIndex = !frameMap.frameNeedsAllocating() ? 0 : frameMap.currentFrameSize() + 1; + } + + private boolean checkEmpty() { + for (int i = 0; i < stackBlocked.length; i++) { + assert stackBlocked[i] == 0 : "stack map must be empty before and after processing"; + } + assert mappingFrom.size() == 0 && mappingTo.size() == 0 : "list must be empty before and after processing"; + for (int i = 0; i < getRegisters().length; i++) { + assert registerBlocked[i] == 0 : "register map must be empty before and after processing"; + } + return true; + } + + private boolean verifyBeforeResolve() { + assert mappingFrom.size() == mappingTo.size() : "length must be equal"; + assert insertIdx != -1 : "insert position not set"; + + int i; + int j; + if (!areMultipleReadsAllowed()) { + for (i = 0; i < mappingFrom.size(); i++) { + for (j = i + 1; j < mappingFrom.size(); j++) { + assert mappingFrom.get(i) == null || mappingFrom.get(i) != mappingFrom.get(j) : "cannot read from same interval twice"; + } + } + } + + for (i = 0; i < mappingTo.size(); i++) { + for (j = i + 1; j < mappingTo.size(); j++) { + assert mappingTo.get(i) != mappingTo.get(j) : "cannot write to same interval twice"; + } + } + + for (i = 0; i < mappingTo.size(); i++) { + Value to = mappingTo.get(i); + assert !isStackSlotValue(to) || getStackArrayIndex(asStackSlotValue(to)) != STACK_SLOT_IN_CALLER_FRAME_IDX : "Cannot move to in argument: " + to; + } + + HashSet<Value> usedRegs = new HashSet<>(); + if (!areMultipleReadsAllowed()) { + for (i = 0; i < mappingFrom.size(); i++) { + Value from = mappingFrom.get(i); + if (from != null && !isIllegal(from)) { + boolean unique = usedRegs.add(from); + assert unique : "cannot read from same register twice"; + } + } + } + + usedRegs.clear(); + for (i = 0; i < mappingTo.size(); i++) { + Value to = mappingTo.get(i); + if (isIllegal(to)) { + // After insertion the location may become illegal, so don't check it since multiple + // intervals might be illegal. + continue; + } + boolean unique = usedRegs.add(to); + assert unique : "cannot write to same register twice"; + } + + return true; + } + + // mark assignedReg and assignedRegHi of the interval as blocked + private void block(Value location) { + if (mightBeBlocked(location)) { + assert areMultipleReadsAllowed() || valueBlocked(location) == 0 : "location already marked as used: " + location; + setValueBlocked(location, 1); + Debug.log("block %s", location); + } + } + + // mark assignedReg and assignedRegHi of the interval as unblocked + private void unblock(Value location) { + if (mightBeBlocked(location)) { + assert valueBlocked(location) > 0 : "location already marked as unused: " + location; + setValueBlocked(location, -1); + Debug.log("unblock %s", location); + } + } + + /** + * Checks if the {@linkplain Interval#location() location} of {@code to} is not blocked or is + * only blocked by {@code from}. + */ + private boolean safeToProcessMove(Value fromLocation, Value toLocation) { + if (mightBeBlocked(toLocation)) { + if ((valueBlocked(toLocation) > 1 || (valueBlocked(toLocation) == 1 && !isMoveToSelf(fromLocation, toLocation)))) { + return false; + } + } + + return true; + } + + public static boolean isMoveToSelf(Value from, Value to) { + assert to != null; + if (to.equals(from)) { + return true; + } + if (from != null && isRegister(from) && isRegister(to) && asRegister(from).equals(asRegister(to))) { + assert LIRKind.verifyMoveKinds(to.getLIRKind(), from.getLIRKind()) : String.format("Same register but Kind mismatch %s <- %s", to, from); + return true; + } + return false; + } + + private static boolean mightBeBlocked(Value location) { + return isRegister(location) || isStackSlotValue(location); + } + + private void createInsertionBuffer(List<LIRInstruction> list) { + assert !insertionBuffer.initialized() : "overwriting existing buffer"; + insertionBuffer.init(list); + } + + private void appendInsertionBuffer() { + if (insertionBuffer.initialized()) { + insertionBuffer.finish(); + } + assert !insertionBuffer.initialized() : "must be uninitialized now"; + + insertIdx = -1; + } + + private void insertMove(Value fromOperand, AllocatableValue toOperand) { + assert !fromOperand.equals(toOperand) : "from and to are equal: " + fromOperand + " vs. " + toOperand; + assert LIRKind.verifyMoveKinds(fromOperand.getLIRKind(), fromOperand.getLIRKind()) : "move between different types"; + assert insertIdx != -1 : "must setup insert position first"; + + insertionBuffer.append(insertIdx, createMove(fromOperand, toOperand)); + + if (Debug.isLogEnabled()) { + Debug.log("insert move from %s to %s at %d", fromOperand, toOperand, insertIdx); + } + } + + /** + * @param fromOpr {@link Interval#operand operand} of the {@code from} interval + * @param toOpr {@link Interval#operand operand} of the {@code to} interval + */ + private LIRInstruction createMove(Value fromOpr, AllocatableValue toOpr) { + if (isStackSlotValue(toOpr) && isStackSlotValue(fromOpr)) { + return getSpillMoveFactory().createStackMove(toOpr, fromOpr); + } + return getSpillMoveFactory().createMove(toOpr, fromOpr); + } + + private void resolveMappings() { + try (Indent indent = Debug.logAndIndent("resolveMapping")) { + assert verifyBeforeResolve(); + if (Debug.isLogEnabled()) { + printMapping(); + } + + // Block all registers that are used as input operands of a move. + // When a register is blocked, no move to this register is emitted. + // This is necessary for detecting cycles in moves. + for (int i = mappingFrom.size() - 1; i >= 0; i--) { + Value from = mappingFrom.get(i); + block(from); + } + + int spillCandidate = -1; + while (mappingFrom.size() > 0) { + boolean processedInterval = false; + + for (int i = mappingFrom.size() - 1; i >= 0; i--) { + Value fromInterval = mappingFrom.get(i); + AllocatableValue toInterval = mappingTo.get(i); + + Value fromLocation = fromInterval; + AllocatableValue toLocation = toInterval; + if (safeToProcessMove(fromLocation, toLocation)) { + // this interval can be processed because target is free + insertMove(fromLocation, toLocation); + unblock(fromLocation); + mappingFrom.remove(i); + mappingTo.remove(i); + + processedInterval = true; + } else if (fromInterval != null && isRegister(fromLocation)) { + // this interval cannot be processed now because target is not free + // it starts in a register, so it is a possible candidate for spilling + spillCandidate = i; + } + } + + if (!processedInterval) { + breakCycle(spillCandidate); + } + } + } + + // check that all intervals have been processed + assert checkEmpty(); + } + + private void breakCycle(int spillCandidate) { + // no move could be processed because there is a cycle in the move list + // (e.g. r1 . r2, r2 . r1), so one interval must be spilled to memory + assert spillCandidate != -1 : "no interval in register for spilling found"; + + // create a new spill interval and assign a stack slot to it + Value from = mappingFrom.get(spillCandidate); + try (Indent indent = Debug.logAndIndent("BreakCycle: %s", from)) { + StackSlotValue spillSlot = frameMapBuilder.allocateSpillSlot(from.getLIRKind()); + if (Debug.isLogEnabled()) { + Debug.log("created new slot for spilling: %s", spillSlot); + } + // insert a move from register to stack and update the mapping + insertMove(from, spillSlot); + block(spillSlot); + mappingFrom.set(spillCandidate, spillSlot); + unblock(from); + } + } + + private void printMapping() { + try (Indent indent = Debug.logAndIndent("Mapping")) { + for (int i = mappingFrom.size() - 1; i >= 0; i--) { + Debug.log("move %s <- %s", mappingTo.get(i), mappingFrom.get(i)); + } + } + } + + public void setInsertPosition(List<LIRInstruction> insertList, int insertIdx) { + assert this.insertIdx == -1 : "use moveInsertPosition instead of setInsertPosition when data already set"; + + createInsertionBuffer(insertList); + this.insertIdx = insertIdx; + } + + public void addMapping(Value from, AllocatableValue to) { + if (Debug.isLogEnabled()) { + Debug.log("add move mapping from %s to %s", from, to); + } + + assert !from.equals(to) : "from and to interval equal: " + from; + assert LIRKind.verifyMoveKinds(to.getLIRKind(), from.getLIRKind()) : String.format("Kind mismatch: %s vs. %s, from=%s, to=%s", from.getLIRKind(), to.getLIRKind(), from, to); + mappingFrom.add(from); + mappingTo.add(to); + } + + public void resolveAndAppendMoves() { + if (hasMappings()) { + resolveMappings(); + } + appendInsertionBuffer(); + } + + private int getStackArrayIndex(StackSlotValue stackSlotValue) { + if (isStackSlot(stackSlotValue)) { + return getStackArrayIndex(asStackSlot(stackSlotValue)); + } + if (isVirtualStackSlot(stackSlotValue)) { + return getStackArrayIndex(asVirtualStackSlot(stackSlotValue)); + } + throw JVMCIError.shouldNotReachHere("Unhandled StackSlotValue: " + stackSlotValue); + } + + private int getStackArrayIndex(StackSlot stackSlot) { + int stackIdx; + if (stackSlot.isInCallerFrame()) { + // incoming stack arguments can be ignored + stackIdx = STACK_SLOT_IN_CALLER_FRAME_IDX; + } else { + assert stackSlot.getRawAddFrameSize() : "Unexpected stack slot: " + stackSlot; + int offset = -stackSlot.getRawOffset(); + assert 0 <= offset && offset < firstVirtualStackIndex : String.format("Wrong stack slot offset: %d (first virtual stack slot index: %d", offset, firstVirtualStackIndex); + stackIdx = offset; + } + return stackIdx; + } + + private int getStackArrayIndex(VirtualStackSlot virtualStackSlot) { + return firstVirtualStackIndex + virtualStackSlot.getId(); + } + +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScan.java Mon Jul 27 16:57:30 2015 -0700 @@ -0,0 +1,126 @@ +/* + * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.lir.alloc.trace; + +import static com.oracle.graal.compiler.common.GraalOptions.*; + +import java.util.*; + +import jdk.internal.jvmci.code.*; + +import com.oracle.graal.compiler.common.alloc.*; +import com.oracle.graal.compiler.common.alloc.TraceBuilder.TraceBuilderResult; +import com.oracle.graal.compiler.common.cfg.*; +import com.oracle.graal.debug.*; +import com.oracle.graal.debug.Debug.Scope; +import com.oracle.graal.lir.alloc.lsra.*; +import com.oracle.graal.lir.alloc.lsra.ssa.*; +import com.oracle.graal.lir.alloc.lsra.ssi.*; +import com.oracle.graal.lir.gen.*; +import com.oracle.graal.lir.gen.LIRGeneratorTool.SpillMoveFactory; +import com.oracle.graal.lir.phases.AllocationPhase.AllocationContext; + +public final class TraceLinearScan extends LinearScan { + + private final TraceBuilderResult<?> traceBuilderResult; + + public TraceLinearScan(TargetDescription target, LIRGenerationResult res, SpillMoveFactory spillMoveFactory, RegisterAllocationConfig regAllocConfig, + List<? extends AbstractBlockBase<?>> sortedBlocks, TraceBuilderResult<?> traceBuilderResult) { + super(target, res, spillMoveFactory, regAllocConfig, sortedBlocks); + this.traceBuilderResult = traceBuilderResult; + } + + @Override + protected <B extends AbstractBlockBase<B>> void allocate(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder, + SpillMoveFactory 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, codeEmittingOrder, linearScanOrder, context, false); + + try (Scope s = Debug.scope("AfterLifetimeAnalysis", (Object) intervals())) { + sortIntervalsBeforeAllocation(); + + createRegisterAllocationPhase().apply(target, lirGenRes, codeEmittingOrder, linearScanOrder, context, false); + + if (LinearScan.Options.LSRAOptimizeSpillPosition.getValue()) { + createOptimizeSpillPositionPhase().apply(target, lirGenRes, codeEmittingOrder, linearScanOrder, context, false); + } + // resolve intra-trace data-flow + LinearScanResolveDataFlowPhase dataFlowPhase = createResolveDataFlowPhase(); + dataFlowPhase.apply(target, lirGenRes, codeEmittingOrder, linearScanOrder, context, false); + Debug.dump(TraceRegisterAllocationPhase.TRACE_DUMP_LEVEL, sortedBlocks(), "%s", dataFlowPhase.getName()); + + LinearScanAssignLocationsPhase assignPhase = createAssignLocationsPhase(); + assignPhase.apply(target, lirGenRes, codeEmittingOrder, linearScanOrder, context, false); + + if (DetailedAsserts.getValue()) { + verifyIntervals(); + } + } catch (Throwable e) { + throw Debug.handle(e); + } + } + } + + @Override + protected MoveResolver createMoveResolver() { + SSAMoveResolver moveResolver = new SSAMoveResolver(this); + assert moveResolver.checkEmpty(); + return moveResolver; + } + + @Override + protected LinearScanLifetimeAnalysisPhase createLifetimeAnalysisPhase() { + return new TraceLinearScanLifetimeAnalysisPhase(this, traceBuilderResult); + } + + @Override + protected LinearScanResolveDataFlowPhase createResolveDataFlowPhase() { + return new TraceLinearScanResolveDataFlowPhase(this); + } + + @Override + protected LinearScanEliminateSpillMovePhase createSpillMoveEliminationPhase() { + return new SSILinearScanEliminateSpillMovePhase(this); + } + + @Override + protected void printIntervals(String label) { + if (Debug.isDumpEnabled(TraceRegisterAllocationPhase.TRACE_DUMP_LEVEL)) { + super.printIntervals(label); + } + } + + @Override + protected void printLir(String label, boolean hirValid) { + if (Debug.isDumpEnabled(TraceRegisterAllocationPhase.TRACE_DUMP_LEVEL)) { + Debug.dump(TraceRegisterAllocationPhase.TRACE_DUMP_LEVEL, sortedBlocks(), label); + } + } + +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanLifetimeAnalysisPhase.java Mon Jul 27 16:57:30 2015 -0700 @@ -0,0 +1,286 @@ +/* + * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.lir.alloc.trace; + +import static com.oracle.graal.compiler.common.GraalOptions.*; +import static com.oracle.graal.lir.LIRValueUtil.*; +import static com.oracle.graal.lir.alloc.trace.TraceRegisterAllocationPhase.Options.*; +import static jdk.internal.jvmci.code.ValueUtil.*; + +import java.util.*; + +import jdk.internal.jvmci.code.*; +import jdk.internal.jvmci.common.*; +import jdk.internal.jvmci.meta.*; + +import com.oracle.graal.compiler.common.alloc.TraceBuilder.TraceBuilderResult; +import com.oracle.graal.compiler.common.cfg.*; +import com.oracle.graal.debug.*; +import com.oracle.graal.lir.*; +import com.oracle.graal.lir.StandardOp.BlockEndOp; +import com.oracle.graal.lir.StandardOp.LabelOp; +import com.oracle.graal.lir.StandardOp.MoveOp; +import com.oracle.graal.lir.alloc.lsra.*; +import com.oracle.graal.lir.alloc.lsra.Interval.RegisterPriority; +import com.oracle.graal.lir.alloc.lsra.Interval.SpillState; +import com.oracle.graal.lir.alloc.lsra.LinearScan.BlockData; +import com.oracle.graal.lir.ssi.*; + +public class TraceLinearScanLifetimeAnalysisPhase extends LinearScanLifetimeAnalysisPhase { + + private final TraceBuilderResult<?> traceBuilderResult; + + public TraceLinearScanLifetimeAnalysisPhase(LinearScan linearScan, TraceBuilderResult<?> traceBuilderResult) { + super(linearScan); + this.traceBuilderResult = traceBuilderResult; + } + + 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) <= traceBuilderResult.getTraceForBlock(currentBlock); + } + + static void setHint(final LIRInstruction op, Interval target, Interval source) { + Interval currentHint = target.locationHint(false); + if (currentHint == null || currentHint.from() > target.from()) { + /* + * Update hint if there was none or if the hint interval starts after the hinted + * interval. + */ + target.setLocationHint(source); + if (Debug.isLogEnabled()) { + Debug.log("operation at opId %d: added hint from interval %d (%s) to %d (%s)", op.id(), source.operandNumber, source, target.operandNumber, target); + } + } + } + + @Override + protected void changeSpillDefinitionPos(LIRInstruction op, AllocatableValue operand, Interval interval, int defPos) { + assert interval.isSplitParent() : "can only be called for split parents"; + + switch (interval.spillState()) { + case NoDefinitionFound: + // assert interval.spillDefinitionPos() == -1 : "must no be set before"; + interval.setSpillDefinitionPos(defPos); + if (!(op instanceof LabelOp)) { + // Do not update state for labels. This will be done afterwards. + interval.setSpillState(SpillState.NoSpillStore); + } + break; + + case NoSpillStore: + assert defPos <= interval.spillDefinitionPos() : "positions are processed in reverse order when intervals are created"; + if (defPos < interval.spillDefinitionPos() - 2) { + // second definition found, so no spill optimization possible for this interval + interval.setSpillState(SpillState.NoOptimization); + } else { + // two consecutive definitions (because of two-operand LIR form) + assert allocator.blockForId(defPos) == allocator.blockForId(interval.spillDefinitionPos()) : "block must be equal"; + } + break; + + case NoOptimization: + // nothing to do + break; + + default: + throw new BailoutException("other states not allowed at this time"); + } + } + + @Override + protected void buildIntervals() { + super.buildIntervals(); + // fix spill state for phi/sigma intervals + for (Interval interval : allocator.intervals()) { + if (interval != null && interval.spillState().equals(SpillState.NoDefinitionFound) && interval.spillDefinitionPos() != -1) { + // there was a definition in a phi/sigma + interval.setSpillState(SpillState.NoSpillStore); + } + } + if (TraceRAuseInterTraceHints.getValue()) { + addInterTraceHints(); + } + } + + private void addInterTraceHints() { + // set hints for phi/sigma intervals + LIR lir = allocator.getLIR(); + for (AbstractBlockBase<?> block : allocator.sortedBlocks()) { + LabelOp label = SSIUtil.incoming(lir, block); + for (AbstractBlockBase<?> pred : block.getPredecessors()) { + if (isAllocatedOrCurrent(block, pred)) { + BlockEndOp outgoing = SSIUtil.outgoing(lir, pred); + for (int i = 0; i < outgoing.getOutgoingSize(); i++) { + Value toValue = label.getIncomingValue(i); + if (!isIllegal(toValue)) { + Value fromValue = outgoing.getOutgoingValue(i); + assert sameTrace(block, pred) || !isVariable(fromValue) : "Unallocated variable: " + fromValue; + + if (!isStackSlotValue(fromValue) && !isConstant(fromValue)) { + Interval from = allocator.getOrCreateInterval((AllocatableValue) fromValue); + Interval to = allocator.getOrCreateInterval((AllocatableValue) toValue); + setHint(label, to, from); + } + } + } + } + } + } + /* + * Set the first range for fixed intervals to [-1, 0] to avoid intersection with incoming + * values. + */ + for (Interval interval : allocator.intervals()) { + if (interval != null && isRegister(interval.operand)) { + Range range = interval.first(); + if (range == Range.EndMarker) { + interval.addRange(-1, 0); + } else if (range.from == 0 && range.to == 1) { + range.from = -1; + range.to = 0; + } + } + } + } + + @Override + protected RegisterPriority registerPriorityOfOutputOperand(LIRInstruction op) { + if (op instanceof LabelOp) { + // skip method header + return RegisterPriority.None; + } + return super.registerPriorityOfOutputOperand(op); + } + + @Override + protected void handleMethodArguments(LIRInstruction op) { + if (op instanceof MoveOp) { + // do not optimize method arguments + return; + } + super.handleMethodArguments(op); + } + + /** + * Performs a backward dataflow analysis to compute global live sets (i.e. + * {@link BlockData#liveIn} and {@link BlockData#liveOut}) for each block. + */ + @Override + protected void computeGlobalLiveSets() { + try (Indent indent = Debug.logAndIndent("compute global live sets")) { + int numBlocks = allocator.blockCount(); + boolean changeOccurred; + boolean changeOccurredInBlock; + int iterationCount = 0; + BitSet liveOut = new BitSet(allocator.liveSetSize()); // scratch set for calculations + + /* + * Perform a backward dataflow analysis to compute liveOut and liveIn for each block. + * The loop is executed until a fixpoint is reached (no changes in an iteration). + */ + do { + changeOccurred = false; + + try (Indent indent2 = Debug.logAndIndent("new iteration %d", iterationCount)) { + + // iterate all blocks in reverse order + for (int i = numBlocks - 1; i >= 0; i--) { + AbstractBlockBase<?> block = allocator.blockAt(i); + BlockData blockSets = allocator.getBlockData(block); + + changeOccurredInBlock = false; + + /* liveOut(block) is the union of liveIn(sux), for successors sux of block. */ + int n = block.getSuccessorCount(); + if (n > 0) { + liveOut.clear(); + // block has successors + if (n > 0) { + for (AbstractBlockBase<?> successor : block.getSuccessors()) { + if (allocator.sortedBlocks().contains(successor)) { + liveOut.or(allocator.getBlockData(successor).liveIn); + } + } + } + + if (!blockSets.liveOut.equals(liveOut)) { + /* + * A change occurred. Swap the old and new live out sets to avoid + * copying. + */ + BitSet temp = blockSets.liveOut; + blockSets.liveOut = liveOut; + liveOut = temp; + + changeOccurred = true; + changeOccurredInBlock = true; + } + } + + if (iterationCount == 0 || changeOccurredInBlock) { + /* + * liveIn(block) is the union of liveGen(block) with (liveOut(block) & + * !liveKill(block)). + * + * Note: liveIn has to be computed only in first iteration or if liveOut + * has changed! + */ + BitSet liveIn = blockSets.liveIn; + liveIn.clear(); + liveIn.or(blockSets.liveOut); + liveIn.andNot(blockSets.liveKill); + liveIn.or(blockSets.liveGen); + + if (Debug.isLogEnabled()) { + Debug.log("block %d: livein = %s, liveout = %s", block.getId(), liveIn, blockSets.liveOut); + } + } + } + iterationCount++; + + if (changeOccurred && iterationCount > 50) { + throw new BailoutException("too many iterations in computeGlobalLiveSets"); + } + } + } while (changeOccurred); + + if (DetailedAsserts.getValue()) { + verifyLiveness(); + } + + // check that the liveIn set of the first block is empty + AbstractBlockBase<?> startBlock = allocator.blockAt(0); + if (allocator.getBlockData(startBlock).liveIn.cardinality() != 0) { + if (DetailedAsserts.getValue()) { + reportFailure(numBlocks); + } + // bailout if this occurs in product mode. + throw new JVMCIError("liveIn set of first block must be empty: " + allocator.getBlockData(startBlock).liveIn); + } + } + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanResolveDataFlowPhase.java Mon Jul 27 16:57:30 2015 -0700 @@ -0,0 +1,108 @@ +/* + * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.lir.alloc.trace; + +import static jdk.internal.jvmci.code.ValueUtil.*; + +import java.util.*; + +import jdk.internal.jvmci.meta.*; + +import com.oracle.graal.compiler.common.cfg.*; +import com.oracle.graal.debug.*; +import com.oracle.graal.lir.*; +import com.oracle.graal.lir.alloc.lsra.*; +import com.oracle.graal.lir.ssa.SSAUtil.PhiValueVisitor; +import com.oracle.graal.lir.ssi.*; + +public class TraceLinearScanResolveDataFlowPhase extends LinearScanResolveDataFlowPhase { + + private static final DebugMetric numSSIResolutionMoves = Debug.metric("SSI LSRA[numSSIResolutionMoves]"); + private static final DebugMetric numStackToStackMoves = Debug.metric("SSI LSRA[numStackToStackMoves]"); + + public TraceLinearScanResolveDataFlowPhase(LinearScan allocator) { + super(allocator); + } + + @Override + protected void optimizeEmptyBlocks(MoveResolver moveResolver, BitSet blockCompleted) { + // do not optimize + } + + @Override + protected void resolveCollectMappings(AbstractBlockBase<?> fromBlock, AbstractBlockBase<?> toBlock, AbstractBlockBase<?> midBlock, MoveResolver moveResolver) { + assert midBlock == null; + if (containedInTrace(fromBlock) && containedInTrace(toBlock)) { + super.resolveCollectMappings(fromBlock, toBlock, midBlock, moveResolver); + SSIUtil.forEachValuePair(allocator.getLIR(), toBlock, fromBlock, new MyPhiValueVisitor(moveResolver, toBlock, fromBlock)); + } + + } + + private boolean containedInTrace(AbstractBlockBase<?> block) { + return allocator.sortedBlocks().contains(block); + } + + private class MyPhiValueVisitor implements PhiValueVisitor { + final MoveResolver moveResolver; + final int toId; + final int fromId; + + public MyPhiValueVisitor(MoveResolver moveResolver, AbstractBlockBase<?> toBlock, AbstractBlockBase<?> fromBlock) { + this.moveResolver = moveResolver; + toId = allocator.getFirstLirInstructionId(toBlock); + fromId = allocator.getLastLirInstructionId(fromBlock); + assert fromId >= 0; + } + + public void visit(Value phiIn, Value phiOut) { + assert !isRegister(phiOut) : "Out is a register: " + phiOut; + assert !isRegister(phiIn) : "In is a register: " + phiIn; + if (Value.ILLEGAL.equals(phiIn)) { + // The value not needed in this branch. + return; + } + if (isVirtualStackSlot(phiIn) && isVirtualStackSlot(phiOut) && phiIn.equals(phiOut)) { + // no need to handle virtual stack slots + return; + } + Interval toInterval = allocator.splitChildAtOpId(allocator.intervalFor(phiIn), toId, LIRInstruction.OperandMode.DEF); + if (isConstant(phiOut)) { + numSSIResolutionMoves.increment(); + moveResolver.addMapping(phiOut, toInterval); + } else { + Interval fromInterval = allocator.splitChildAtOpId(allocator.intervalFor(phiOut), fromId, LIRInstruction.OperandMode.DEF); + if (fromInterval != toInterval) { + numSSIResolutionMoves.increment(); + if (!(isStackSlotValue(toInterval.location()) && isStackSlotValue(fromInterval.location()))) { + moveResolver.addMapping(fromInterval, toInterval); + } else { + numStackToStackMoves.increment(); + moveResolver.addMapping(fromInterval, toInterval); + } + } + } + } + } + +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceRegisterAllocationPhase.java Mon Jul 27 16:57:30 2015 -0700 @@ -0,0 +1,168 @@ +/* + * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.lir.alloc.trace; + +import static jdk.internal.jvmci.code.ValueUtil.*; + +import java.util.*; + +import jdk.internal.jvmci.code.*; +import jdk.internal.jvmci.meta.*; +import jdk.internal.jvmci.options.*; + +import com.oracle.graal.compiler.common.alloc.*; +import com.oracle.graal.compiler.common.alloc.TraceBuilder.TraceBuilderResult; +import com.oracle.graal.compiler.common.cfg.*; +import com.oracle.graal.debug.*; +import com.oracle.graal.debug.Debug.Scope; +import com.oracle.graal.lir.*; +import com.oracle.graal.lir.StandardOp.MoveOp; +import com.oracle.graal.lir.gen.*; +import com.oracle.graal.lir.gen.LIRGeneratorTool.SpillMoveFactory; +import com.oracle.graal.lir.phases.*; +import com.oracle.graal.lir.ssa.SSAUtil.PhiValueVisitor; +import com.oracle.graal.lir.ssi.*; + +public class TraceRegisterAllocationPhase extends AllocationPhase { + public static class Options { + // @formatter:off + @Option(help = "Use inter-trace register hints.", type = OptionType.Debug) + public static final OptionValue<Boolean> TraceRAuseInterTraceHints = new OptionValue<>(true); + // @formatter:on + } + + static final int TRACE_DUMP_LEVEL = 3; + + @Override + protected <B extends AbstractBlockBase<B>> void run(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder, SpillMoveFactory spillMoveFactory, + RegisterAllocationConfig registerAllocationConfig) { + LIR lir = lirGenRes.getLIR(); + assert SSIVerifier.verify(lir) : "LIR not in SSI form."; + B startBlock = linearScanOrder.get(0); + assert startBlock.equals(lir.getControlFlowGraph().getStartBlock()); + TraceBuilderResult<B> resultTraces = TraceBuilder.computeTraces(startBlock, linearScanOrder); + + Debug.dump(lir, "Before TraceRegisterAllocation"); + int traceNumber = 0; + for (List<B> trace : resultTraces.getTraces()) { + try (Indent i = Debug.logAndIndent("Allocating Trace%d: %s", traceNumber, trace); Scope s = Debug.scope("AllocateTrace", trace)) { + Debug.dump(TRACE_DUMP_LEVEL, trace, "Trace" + traceNumber + ": " + trace); + TraceLinearScan allocator = new TraceLinearScan(target, lirGenRes, spillMoveFactory, registerAllocationConfig, trace, resultTraces); + allocator.allocate(target, lirGenRes, codeEmittingOrder, linearScanOrder, spillMoveFactory, registerAllocationConfig); + Debug.dump(TRACE_DUMP_LEVEL, trace, "After Trace" + traceNumber + ": " + trace); + traceNumber++; + } catch (Throwable e) { + throw Debug.handle(e); + } + unnumberInstructions(trace, lir); + } + Debug.dump(lir, "After trace allocation"); + + resolveGlobalDataFlow(resultTraces, lirGenRes, spillMoveFactory, target.arch); + Debug.dump(lir, "After global dataflow resolution"); + + if (replaceStackToStackMoves(lir, spillMoveFactory)) { + Debug.dump(lir, "After fixing stack to stack moves"); + } + /* + * Incoming Values are needed for the RegisterVerifier, otherwise SIGMAs/PHIs where the Out + * and In value matches (ie. there is no resolution move) are falsely detected as errors. + */ + for (AbstractBlockBase<?> toBlock : lir.getControlFlowGraph().getBlocks()) { + if (toBlock.getPredecessorCount() != 0) { + SSIUtil.removeIncoming(lir, toBlock); + } else { + assert lir.getControlFlowGraph().getStartBlock().equals(toBlock); + } + SSIUtil.removeOutgoing(lir, toBlock); + } + } + + /** + * Fixup stack to stack moves introduced by stack arguments. + * + * TODO (je) find a better solution. + */ + private static boolean replaceStackToStackMoves(LIR lir, SpillMoveFactory spillMoveFactory) { + boolean changed = false; + for (AbstractBlockBase<?> block : lir.getControlFlowGraph().getBlocks()) { + List<LIRInstruction> instructions = lir.getLIRforBlock(block); + for (int i = 0; i < instructions.size(); i++) { + LIRInstruction inst = instructions.get(i); + + if (inst instanceof MoveOp) { + MoveOp move = (MoveOp) inst; + if (isStackSlotValue(move.getInput()) && isStackSlotValue(move.getResult())) { + instructions.set(i, spillMoveFactory.createStackMove(move.getResult(), move.getInput())); + changed = true; + } + } + } + } + return changed; + } + + private static <B extends AbstractBlockBase<B>> void resolveGlobalDataFlow(TraceBuilderResult<B> resultTraces, LIRGenerationResult lirGenRes, SpillMoveFactory spillMoveFactory, Architecture arch) { + LIR lir = lirGenRes.getLIR(); + /* Resolve trace global data-flow mismatch. */ + TraceGlobalMoveResolver moveResolver = new TraceGlobalMoveResolver(lirGenRes, spillMoveFactory, arch); + PhiValueVisitor visitor = (Value phiIn, Value phiOut) -> { + if (!isIllegal(phiIn) && !TraceGlobalMoveResolver.isMoveToSelf(phiOut, phiIn)) { + moveResolver.addMapping(phiOut, (AllocatableValue) phiIn); + } + }; + + try (Indent indent = Debug.logAndIndent("Trace global move resolution")) { + for (List<B> trace : resultTraces.getTraces()) { + for (AbstractBlockBase<?> fromBlock : trace) { + for (AbstractBlockBase<?> toBlock : fromBlock.getSuccessors()) { + if (resultTraces.getTraceForBlock(fromBlock) != resultTraces.getTraceForBlock(toBlock)) { + try (Indent indent0 = Debug.logAndIndent("Handle trace edge from %s (Trace%d) to %s (Trace%d)", fromBlock, resultTraces.getTraceForBlock(fromBlock), toBlock, + resultTraces.getTraceForBlock(toBlock))) { + + final List<LIRInstruction> instructions; + final int insertIdx; + if (fromBlock.getSuccessorCount() == 1) { + instructions = lir.getLIRforBlock(fromBlock); + insertIdx = instructions.size() - 1; + } else { + assert toBlock.getPredecessorCount() == 1; + instructions = lir.getLIRforBlock(toBlock); + insertIdx = 1; + } + + moveResolver.setInsertPosition(instructions, insertIdx); + SSIUtil.forEachValuePair(lir, toBlock, fromBlock, visitor); + moveResolver.resolveAndAppendMoves(); + } + } + } + } + } + } + } + + private static void unnumberInstructions(List<? extends AbstractBlockBase<?>> trace, LIR lir) { + trace.stream().flatMap(b -> lir.getLIRforBlock(b).stream()).forEach(op -> op.setId(-1)); + } +}
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/dfa/MarkBasePointersPhase.java Mon Jul 27 16:26:41 2015 -0700 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/dfa/MarkBasePointersPhase.java Mon Jul 27 16:57:30 2015 -0700 @@ -51,14 +51,14 @@ private final class BasePointersSet extends ValueSet<Marker<T>.BasePointersSet> { - private final IntValueMap variables; + private final IndexedValueMap variables; public BasePointersSet() { - variables = new IntValueMap(); + variables = new IndexedValueMap(); } private BasePointersSet(BasePointersSet s) { - variables = new IntValueMap(s.variables); + variables = new IndexedValueMap(s.variables); } @Override @@ -118,7 +118,7 @@ @Override protected void processState(LIRInstruction op, LIRFrameState info, BasePointersSet values) { - info.setLiveBasePointers(new IntValueMap(values.variables)); + info.setLiveBasePointers(new IndexedValueMap(values.variables)); } } }
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/dfa/RegStackValueSet.java Mon Jul 27 16:26:41 2015 -0700 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/dfa/RegStackValueSet.java Mon Jul 27 16:57:30 2015 -0700 @@ -36,20 +36,20 @@ final class RegStackValueSet extends ValueSet<RegStackValueSet> { private final FrameMap frameMap; - private final IntValueMap registers; - private final IntValueMap stack; + private final IndexedValueMap registers; + private final IndexedValueMap stack; private Set<Value> extraStack; public RegStackValueSet(FrameMap frameMap) { this.frameMap = frameMap; - registers = new IntValueMap(); - stack = new IntValueMap(); + registers = new IndexedValueMap(); + stack = new IndexedValueMap(); } private RegStackValueSet(FrameMap frameMap, RegStackValueSet s) { this.frameMap = frameMap; - registers = new IntValueMap(s.registers); - stack = new IntValueMap(s.stack); + registers = new IndexedValueMap(s.registers); + stack = new IndexedValueMap(s.stack); if (s.extraStack != null) { extraStack = new HashSet<>(s.extraStack); }
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/gen/BlockValueMap.java Mon Jul 27 16:57:30 2015 -0700 @@ -0,0 +1,35 @@ +/* + * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.lir.gen; + +import jdk.internal.jvmci.meta.*; + +import com.oracle.graal.compiler.common.cfg.*; + +public interface BlockValueMap { + + void accessOperand(Value operand, AbstractBlockBase<?> block); + + void defineOperand(Value operand, AbstractBlockBase<?> block); + +}
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/phases/AllocationStage.java Mon Jul 27 16:26:41 2015 -0700 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/phases/AllocationStage.java Mon Jul 27 16:57:30 2015 -0700 @@ -22,7 +22,10 @@ */ package com.oracle.graal.lir.phases; +import static com.oracle.graal.compiler.common.BackendOptions.UserOptions.*; + import com.oracle.graal.lir.alloc.lsra.*; +import com.oracle.graal.lir.alloc.trace.*; import com.oracle.graal.lir.dfa.*; import com.oracle.graal.lir.phases.AllocationPhase.AllocationContext; import com.oracle.graal.lir.stackslotalloc.*; @@ -30,7 +33,11 @@ public class AllocationStage extends LIRPhaseSuite<AllocationContext> { public AllocationStage() { appendPhase(new MarkBasePointersPhase()); - appendPhase(new LinearScanPhase()); + if (TraceRA.getValue()) { + appendPhase(new TraceRegisterAllocationPhase()); + } else { + appendPhase(new LinearScanPhase()); + } // build frame map if (LSStackSlotAllocator.Options.LIROptLSStackSlotAllocator.getValue()) {
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/phases/PreAllocationOptimizationStage.java Mon Jul 27 16:26:41 2015 -0700 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/phases/PreAllocationOptimizationStage.java Mon Jul 27 16:57:30 2015 -0700 @@ -23,11 +23,13 @@ package com.oracle.graal.lir.phases; import static com.oracle.graal.compiler.common.GraalOptions.*; +import static com.oracle.graal.compiler.common.BackendOptions.*; import com.oracle.graal.compiler.common.*; import com.oracle.graal.lir.constopt.*; import com.oracle.graal.lir.phases.PreAllocationOptimizationPhase.PreAllocationOptimizationContext; import com.oracle.graal.lir.ssa.*; +import com.oracle.graal.lir.ssi.*; public class PreAllocationOptimizationStage extends LIRPhaseSuite<PreAllocationOptimizationContext> { public PreAllocationOptimizationStage() { @@ -37,5 +39,8 @@ if (ConstantLoadOptimization.Options.LIROptConstantLoadOptimization.getValue()) { appendPhase(new ConstantLoadOptimization()); } + if (EnableSSIConstruction.getValue()) { + appendPhase(new SSIConstructionPhase()); + } } }
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/profiling/MoveProfiling.java Mon Jul 27 16:26:41 2015 -0700 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/profiling/MoveProfiling.java Mon Jul 27 16:57:30 2015 -0700 @@ -51,7 +51,8 @@ STACK2REG("Reg", "Stack"), CONST2REG("Reg", "Const"), REG2STACK("Stack", "Reg"), - CONST2STACK("Stack", "Const"); + CONST2STACK("Stack", "Const"), + STACK2STACK("Stack", "Stack"); private final String name; @@ -84,6 +85,9 @@ if (isConstant(src)) { return CONST2STACK; } + if (isStackSlot(src)) { + return STACK2STACK; + } } throw JVMCIError.shouldNotReachHere(String.format("Unrecognized Move: %s dst=%s, src=%s", move, dst, src)); }
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/ssa/SSADestructionPhase.java Mon Jul 27 16:26:41 2015 -0700 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/ssa/SSADestructionPhase.java Mon Jul 27 16:57:30 2015 -0700 @@ -48,15 +48,15 @@ List<LIRInstruction> instructions = lir.getLIRforBlock(pred); - int insertBefore = SSAUtils.phiOutIndex(lir, pred); + int insertBefore = SSAUtil.phiOutIndex(lir, pred); PhiResolver resolver = PhiResolver.create(lirGen, new LIRInsertionBuffer(), instructions, insertBefore); - SSAUtils.forEachPhiValuePair(lir, block, pred, resolver::move); + SSAUtil.forEachPhiValuePair(lir, block, pred, resolver::move); resolver.dispose(); - SSAUtils.removePhiOut(lir, pred); + SSAUtil.removePhiOut(lir, pred); } - SSAUtils.removePhiIn(lir, block); + SSAUtil.removePhiIn(lir, block); } }
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/ssa/SSAUtil.java Mon Jul 27 16:57:30 2015 -0700 @@ -0,0 +1,176 @@ +/* + * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.lir.ssa; + +import java.util.*; + +import jdk.internal.jvmci.meta.*; + +import com.oracle.graal.compiler.common.cfg.*; +import com.oracle.graal.lir.*; +import com.oracle.graal.lir.LIRInstruction.OperandMode; +import com.oracle.graal.lir.StandardOp.BlockEndOp; +import com.oracle.graal.lir.StandardOp.JumpOp; +import com.oracle.graal.lir.StandardOp.LabelOp; + +/** + * Utilities for working with Static-Single-Assignment LIR form. + * + * <h2>Representation of <code>PHI</code>s</h2> + * + * There is no explicit <code>PHI</code> {@linkplain LIRInstruction}. Instead, they are implemented + * as parallel copy that span across a control-flow edge. + * + * The variables introduced by <code>PHI</code>s of a specific {@linkplain AbstractBlockBase merge + * block} are {@linkplain LabelOp#setIncomingValues attached} to the {@linkplain LabelOp} of the + * block. The outgoing values from the predecessor are {@link JumpOp#setOutgoingValues input} to the + * {@linkplain BlockEndOp} of the predecessor. Because there are no critical edges we know that the + * {@link BlockEndOp} of the predecessor has to be a {@link JumpOp}. + * + * <h3>Example:</h3> + * + * <pre> + * B0 -> B1 + * ... + * v0|i = ... + * JUMP ~[v0|i, int[0|0x0]] destination: B0 -> B1 + * ________________________________________________ + * + * B2 -> B1 + * ... + * v1|i = ... + * v2|i = ... + * JUMP ~[v1|i, v2|i] destination: B2 -> B1 + * ________________________________________________ + * + * B1 <- B0,B2 + * [v3|i, v4|i] = LABEL + * ... + * </pre> + */ +public final class SSAUtil { + + public interface PhiValueVisitor { + /** + * @param phiIn the incoming value at the merge block + * @param phiOut the outgoing value from the predecessor block + */ + void visit(Value phiIn, Value phiOut); + } + + /** + * Visits each phi value pair of an edge, i.e. the outgoing value from the predecessor and the + * incoming value to the merge block. + */ + public static void forEachPhiValuePair(LIR lir, AbstractBlockBase<?> merge, AbstractBlockBase<?> pred, PhiValueVisitor visitor) { + if (merge.getPredecessorCount() < 2) { + return; + } + assert merge.getPredecessors().contains(pred) : String.format("%s not in predecessor list: %s", pred, merge.getPredecessors()); + assert pred.getSuccessorCount() == 1 : String.format("Merge predecessor block %s has more than one successor? %s", pred, pred.getSuccessors()); + assert pred.getSuccessors().get(0) == merge : String.format("Predecessor block %s has wrong successor: %s, should be: %s", pred, pred.getSuccessors().get(0), merge); + + JumpOp jump = phiOut(lir, pred); + LabelOp label = phiIn(lir, merge); + + assert label.getIncomingSize() == jump.getOutgoingSize() : String.format("Phi In/Out size mismatch: in=%d vs. out=%d", label.getIncomingSize(), jump.getOutgoingSize()); + + for (int i = 0; i < label.getIncomingSize(); i++) { + visitor.visit(label.getIncomingValue(i), jump.getOutgoingValue(i)); + } + } + + private static JumpOp phiOut(LIR lir, AbstractBlockBase<?> block) { + assert block.getSuccessorCount() == 1; + List<LIRInstruction> instructions = lir.getLIRforBlock(block); + int index = instructions.size() - 1; + LIRInstruction op = instructions.get(index); + return (JumpOp) op; + } + + public static int phiOutIndex(LIR lir, AbstractBlockBase<?> block) { + assert block.getSuccessorCount() == 1; + List<LIRInstruction> instructions = lir.getLIRforBlock(block); + int index = instructions.size() - 1; + assert instructions.get(index) instanceof JumpOp; + return index; + } + + private static LabelOp phiIn(LIR lir, AbstractBlockBase<?> block) { + assert block.getPredecessorCount() > 1; + LabelOp label = (LabelOp) lir.getLIRforBlock(block).get(0); + return label; + } + + public static void removePhiOut(LIR lir, AbstractBlockBase<?> block) { + JumpOp jump = phiOut(lir, block); + jump.clearOutgoingValues(); + } + + public static void removePhiIn(LIR lir, AbstractBlockBase<?> block) { + LabelOp label = phiIn(lir, block); + label.clearIncomingValues(); + } + + public static boolean verifySSAForm(LIR lir) { + return new SSAVerifier(lir).verify(); + } + + public static void verifyPhi(LIR lir, AbstractBlockBase<?> merge) { + assert merge.getPredecessorCount() > 1; + for (AbstractBlockBase<?> pred : merge.getPredecessors()) { + forEachPhiValuePair(lir, merge, pred, (phiIn, phiOut) -> { + assert phiIn.getLIRKind().equals(phiOut.getLIRKind()) || + (phiIn.getPlatformKind().equals(phiOut.getPlatformKind()) && phiIn.getLIRKind().isUnknownReference() && phiOut.getLIRKind().isValue()); + }); + } + } + + public static void forEachPhiRegisterHint(LIR lir, AbstractBlockBase<?> block, LabelOp label, Value targetValue, OperandMode mode, ValueConsumer valueConsumer) { + assert mode == OperandMode.DEF : "Wrong operand mode: " + mode; + assert lir.getLIRforBlock(block).get(0).equals(label) : String.format("Block %s and Label %s do not match!", block, label); + + if (!label.isPhiIn()) { + return; + } + int idx = indexOfValue(label, targetValue); + assert idx >= 0 : String.format("Value %s not in label %s", targetValue, label); + + for (AbstractBlockBase<?> pred : block.getPredecessors()) { + JumpOp jump = phiOut(lir, pred); + Value sourceValue = jump.getOutgoingValue(idx); + valueConsumer.visitValue(jump, sourceValue, null, null); + } + + } + + private static int indexOfValue(LabelOp label, Value value) { + for (int i = 0; i < label.getIncomingSize(); i++) { + if (label.getIncomingValue(i).equals(value)) { + return i; + } + } + return -1; + } + +}
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/ssa/SSAUtils.java Mon Jul 27 16:26:41 2015 -0700 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,176 +0,0 @@ -/* - * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved. - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. - * - * This code is free software; you can redistribute it and/or modify it - * under the terms of the GNU General Public License version 2 only, as - * published by the Free Software Foundation. - * - * This code is distributed in the hope that it will be useful, but WITHOUT - * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or - * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License - * version 2 for more details (a copy is included in the LICENSE file that - * accompanied this code). - * - * You should have received a copy of the GNU General Public License version - * 2 along with this work; if not, write to the Free Software Foundation, - * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. - * - * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA - * or visit www.oracle.com if you need additional information or have any - * questions. - */ -package com.oracle.graal.lir.ssa; - -import java.util.*; - -import jdk.internal.jvmci.meta.*; - -import com.oracle.graal.compiler.common.cfg.*; -import com.oracle.graal.lir.*; -import com.oracle.graal.lir.LIRInstruction.OperandMode; -import com.oracle.graal.lir.StandardOp.BlockEndOp; -import com.oracle.graal.lir.StandardOp.JumpOp; -import com.oracle.graal.lir.StandardOp.LabelOp; - -/** - * Utilities for working with Static-Single-Assignment LIR form. - * - * <h2>Representation of <code>PHI</code>s</h2> - * - * There is no explicit <code>PHI</code> {@linkplain LIRInstruction}. Instead, they are implemented - * as parallel copy that span across a control-flow edge. - * - * The variables introduced by <code>PHI</code>s of a specific {@linkplain AbstractBlockBase merge - * block} are {@linkplain LabelOp#setIncomingValues attached} to the {@linkplain LabelOp} of the - * block. The outgoing values from the predecessor are {@link JumpOp#setOutgoingValues input} to the - * {@linkplain BlockEndOp} of the predecessor. Because there are no critical edges we know that the - * {@link BlockEndOp} of the predecessor has to be a {@link JumpOp}. - * - * <h3>Example:</h3> - * - * <pre> - * B0 -> B1 - * ... - * v0|i = ... - * JUMP ~[v0|i, int[0|0x0]] destination: B0 -> B1 - * ________________________________________________ - * - * B2 -> B1 - * ... - * v1|i = ... - * v2|i = ... - * JUMP ~[v1|i, v2|i] destination: B2 -> B1 - * ________________________________________________ - * - * B1 <- B0,B2 - * [v3|i, v4|i] = LABEL - * ... - * </pre> - */ -public final class SSAUtils { - - public interface PhiValueVisitor { - /** - * @param phiIn the incoming value at the merge block - * @param phiOut the outgoing value from the predecessor block - */ - void visit(Value phiIn, Value phiOut); - } - - /** - * Visits each phi value pair of an edge, i.e. the outgoing value from the predecessor and the - * incoming value to the merge block. - */ - public static void forEachPhiValuePair(LIR lir, AbstractBlockBase<?> merge, AbstractBlockBase<?> pred, PhiValueVisitor visitor) { - if (merge.getPredecessorCount() < 2) { - return; - } - assert merge.getPredecessors().contains(pred) : String.format("%s not in predecessor list: %s", pred, merge.getPredecessors()); - assert pred.getSuccessorCount() == 1 : String.format("Merge predecessor block %s has more than one successor? %s", pred, pred.getSuccessors()); - assert pred.getSuccessors().get(0) == merge : String.format("Predecessor block %s has wrong successor: %s, should be: %s", pred, pred.getSuccessors().get(0), merge); - - JumpOp jump = phiOut(lir, pred); - LabelOp label = phiIn(lir, merge); - - assert label.getIncomingSize() == jump.getOutgoingSize() : String.format("Phi In/Out size mismatch: in=%d vs. out=%d", label.getIncomingSize(), jump.getOutgoingSize()); - - for (int i = 0; i < label.getIncomingSize(); i++) { - visitor.visit(label.getIncomingValue(i), jump.getOutgoingValue(i)); - } - } - - private static JumpOp phiOut(LIR lir, AbstractBlockBase<?> block) { - assert block.getSuccessorCount() == 1; - List<LIRInstruction> instructions = lir.getLIRforBlock(block); - int index = instructions.size() - 1; - LIRInstruction op = instructions.get(index); - return (JumpOp) op; - } - - public static int phiOutIndex(LIR lir, AbstractBlockBase<?> block) { - assert block.getSuccessorCount() == 1; - List<LIRInstruction> instructions = lir.getLIRforBlock(block); - int index = instructions.size() - 1; - assert instructions.get(index) instanceof JumpOp; - return index; - } - - private static LabelOp phiIn(LIR lir, AbstractBlockBase<?> block) { - assert block.getPredecessorCount() > 1; - LabelOp label = (LabelOp) lir.getLIRforBlock(block).get(0); - return label; - } - - public static void removePhiOut(LIR lir, AbstractBlockBase<?> block) { - JumpOp jump = phiOut(lir, block); - jump.clearOutgoingValues(); - } - - public static void removePhiIn(LIR lir, AbstractBlockBase<?> block) { - LabelOp label = phiIn(lir, block); - label.clearIncomingValues(); - } - - public static boolean verifySSAForm(LIR lir) { - return new SSAVerifier(lir).verify(); - } - - public static void verifyPhi(LIR lir, AbstractBlockBase<?> merge) { - assert merge.getPredecessorCount() > 1; - for (AbstractBlockBase<?> pred : merge.getPredecessors()) { - forEachPhiValuePair(lir, merge, pred, (phiIn, phiOut) -> { - assert phiIn.getLIRKind().equals(phiOut.getLIRKind()) || - (phiIn.getPlatformKind().equals(phiOut.getPlatformKind()) && phiIn.getLIRKind().isUnknownReference() && phiOut.getLIRKind().isValue()); - }); - } - } - - public static void forEachPhiRegisterHint(LIR lir, AbstractBlockBase<?> block, LabelOp label, Value targetValue, OperandMode mode, ValueConsumer valueConsumer) { - assert mode == OperandMode.DEF : "Wrong operand mode: " + mode; - assert lir.getLIRforBlock(block).get(0).equals(label) : String.format("Block %s and Label %s do not match!", block, label); - - if (!label.isPhiIn()) { - return; - } - int idx = indexOfValue(label, targetValue); - assert idx >= 0 : String.format("Value %s not in label %s", targetValue, label); - - for (AbstractBlockBase<?> pred : block.getPredecessors()) { - JumpOp jump = phiOut(lir, pred); - Value sourceValue = jump.getOutgoingValue(idx); - valueConsumer.visitValue(jump, sourceValue, null, null); - } - - } - - private static int indexOfValue(LabelOp label, Value value) { - for (int i = 0; i < label.getIncomingSize(); i++) { - if (label.getIncomingValue(i).equals(value)) { - return i; - } - } - return -1; - } - -}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/ssi/SSIBlockValueMapImpl.java Mon Jul 27 16:57:30 2015 -0700 @@ -0,0 +1,252 @@ +/* + * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.lir.ssi; + +import static com.oracle.graal.lir.LIRValueUtil.*; +import static jdk.internal.jvmci.code.ValueUtil.*; + +import java.util.*; + +import jdk.internal.jvmci.meta.*; + +import com.oracle.graal.compiler.common.cfg.*; +import com.oracle.graal.debug.*; +import com.oracle.graal.lir.*; +import com.oracle.graal.lir.LIRInstruction.OperandMode; +import com.oracle.graal.lir.StandardOp.BlockEndOp; +import com.oracle.graal.lir.StandardOp.LabelOp; +import com.oracle.graal.lir.gen.*; +import com.oracle.graal.lir.util.*; + +public final class SSIBlockValueMapImpl implements BlockValueMap { + + private static final class BlockData { + + /** Mapping from value to index into {@link #incoming}. */ + private final ValueMap<Value, Integer> valueIndexMap; + private final ArrayList<Value> incoming; + private final ArrayList<Value> outgoing; + + private BlockData(int initialVariableCapacity, int initialStackSlotCapacity) { + valueIndexMap = new VariableVirtualStackValueMap<>(initialVariableCapacity, initialStackSlotCapacity); + incoming = new ArrayList<>(); + outgoing = new ArrayList<>(); + } + + public Integer getIndex(Value operand) { + return valueIndexMap.get(operand); + } + + public Value getIncoming(int index) { + return incoming.get(index); + } + + public void setIncoming(int index, Value value) { + incoming.set(index, value); + } + + public int addIncoming(Value operand) { + assert isVariable(operand) || isVirtualStackSlot(operand) : "Not a variable or vstack: " + operand; + int index = incoming.size(); + incoming.add(Value.ILLEGAL); + valueIndexMap.put(operand, index); + return index; + } + + public boolean contains(Value operand) { + return getIndex(operand) != null; + } + + public int addOutgoing(Value operand) { + int index = outgoing.size(); + outgoing.add(operand); + return index; + } + + } + + /** Mapping from value to definition block. */ + private final ValueMap<Value, AbstractBlockBase<?>> valueToDefBlock; + private final BlockMap<BlockData> blockData; + private final int initialVariableCapacity; + private final int initialStackSlotCapacity; + + public SSIBlockValueMapImpl(AbstractControlFlowGraph<?> cfg, int initialVariableCapacity, int initialStackSlotCapacity) { + this.initialVariableCapacity = initialVariableCapacity; + this.initialStackSlotCapacity = initialStackSlotCapacity; + valueToDefBlock = new VariableVirtualStackValueMap<>(initialVariableCapacity, initialStackSlotCapacity); + blockData = new BlockMap<>(cfg); + } + + @Override + public void accessOperand(Value operand, AbstractBlockBase<?> block) { + assert block != null : "block is null"; + if (operand instanceof CompositeValue) { + ((CompositeValue) operand).forEachComponent(null, OperandMode.USE, (op, value, mode, flag) -> { + accessOperand(value, block); + return value; + }); + } else if (processValue(operand)) { + AbstractBlockBase<?> defBlock = getDefinitionBlock(operand); + assert defBlock != null : "Value is not defined: " + operand; + assert AbstractControlFlowGraph.dominates(defBlock, block) : "Block " + defBlock + " does not dominate " + block; + accessRecursive(operand, defBlock, block); + } + } + + @Override + public void defineOperand(Value operand, AbstractBlockBase<?> block) { + assert block != null : "block is null"; + if (processValue(operand)) { + AbstractBlockBase<?> defBlock = getDefinitionBlock(operand); + if (defBlock == null) { + setDefinitionBlock(operand, block); + } else { + /* + * Redefinition: this can happen for nodes that do not produce a new value but proxy + * another one (PiNode, reinterpret). + */ + assert AbstractControlFlowGraph.dominates(defBlock, block) : String.format("Definition of %s in %s does not dominate the redefinition %s", operand, defBlock, block); + } + } + } + + private static boolean processValue(Value operand) { + return isVariable(operand) || isVirtualStackSlot(operand); + } + + // setter getter for internal data structures + + private AbstractBlockBase<?> getDefinitionBlock(Value operand) { + return valueToDefBlock.get(operand); + } + + private void setDefinitionBlock(Value operand, AbstractBlockBase<?> block) { + valueToDefBlock.put(operand, block); + } + + private BlockData getOrInit(AbstractBlockBase<?> block) { + BlockData data = blockData.get(block); + if (data == null) { + data = new BlockData(initialVariableCapacity, initialStackSlotCapacity); + blockData.put(block, data); + } + return data; + } + + // implementation + + private void accessRecursive(Value operand, AbstractBlockBase<?> defBlock, AbstractBlockBase<?> block) { + try (Indent indent = Debug.logAndIndent("get operand %s in block %s", operand, block)) { + if (block.equals(defBlock)) { + Debug.log("found definition!"); + return; + } + BlockData data = getOrInit(block); + Integer index = data.getIndex(operand); + if (index != null) { + // value is live at block begin but might not be initialized + Value in = data.getIncoming(index); + if (Value.ILLEGAL.equals(in)) { + data.setIncoming(index, operand); + Debug.log("uninitialized incoming value -> initialize!"); + } else { + Debug.log("incoming value already initialized!"); + } + return; + } + + // the value is not yet live a current block + int idx = addLiveValueToBlock(operand, block); + data.setIncoming(idx, operand); + + for (AbstractBlockBase<?> pred : block.getPredecessors()) { + accessRecursive(operand, defBlock, pred); + } + } + } + + private int addLiveValueToBlock(Value operand, AbstractBlockBase<?> block) { + try (Indent indent = Debug.logAndIndent("add incoming value!")) { + int index = -1; + for (AbstractBlockBase<?> pred : block.getPredecessors()) { + try (Indent indent1 = Debug.logAndIndent("Add outgoing operand to %s", pred)) { + BlockData predData = getOrInit(pred); + int predIndex = predData.addOutgoing(operand); + + if (index == -1) { + index = predIndex; + } else { + assert predIndex == index; + } + + for (AbstractBlockBase<?> succ : pred.getSuccessors()) { + Debug.log("Add incoming operand to %s", succ); + BlockData succData = getOrInit(succ); + if (!succData.contains(operand)) { + int succIndex = succData.addIncoming(operand); + assert succIndex == predIndex; + } + } + } + } + Debug.log("new index: %d", index); + return index; + } + } + + // finish + + public void finish(LIRGeneratorTool gen) { + Debug.dump(gen.getResult().getLIR(), "Before SSI operands"); + AbstractControlFlowGraph<?> cfg = gen.getResult().getLIR().getControlFlowGraph(); + for (AbstractBlockBase<?> block : cfg.getBlocks()) { + // set label + BlockData data = blockData.get(block); + if (data != null) { + if (data.incoming != null && data.incoming.size() > 0) { + LabelOp label = getLabel(gen, block); + label.addIncomingValues(data.incoming.toArray(new Value[data.incoming.size()])); + } + // set block end + if (data.outgoing != null && data.outgoing.size() > 0) { + BlockEndOp blockEndOp = getBlockEnd(gen, block); + blockEndOp.addOutgoingValues(data.outgoing.toArray(new Value[data.outgoing.size()])); + } + } + } + } + + private static List<LIRInstruction> getLIRforBlock(LIRGeneratorTool gen, AbstractBlockBase<?> block) { + return gen.getResult().getLIR().getLIRforBlock(block); + } + + private static LabelOp getLabel(LIRGeneratorTool gen, AbstractBlockBase<?> block) { + return (LabelOp) getLIRforBlock(gen, block).get(0); + } + + private static BlockEndOp getBlockEnd(LIRGeneratorTool gen, AbstractBlockBase<?> block) { + List<LIRInstruction> instructions = getLIRforBlock(gen, block); + return (BlockEndOp) instructions.get(instructions.size() - 1); + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/ssi/SSIConstructionPhase.java Mon Jul 27 16:57:30 2015 -0700 @@ -0,0 +1,120 @@ +/* + * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.lir.ssi; + +import java.util.*; + +import jdk.internal.jvmci.code.*; + +import com.oracle.graal.compiler.common.cfg.*; +import com.oracle.graal.debug.*; +import com.oracle.graal.lir.*; +import com.oracle.graal.lir.LIRInstruction.OperandFlag; +import com.oracle.graal.lir.framemap.*; +import com.oracle.graal.lir.gen.*; +import com.oracle.graal.lir.phases.*; +import com.oracle.graal.lir.ssa.*; + +public final class SSIConstructionPhase extends PreAllocationOptimizationPhase { + + @Override + protected <B extends AbstractBlockBase<B>> void run(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder, LIRGeneratorTool lirGen) { + assert SSAUtil.verifySSAForm(lirGenRes.getLIR()); + LIR lir = lirGenRes.getLIR(); + new SSIBuilder(lir, lirGenRes.getFrameMapBuilder()).build(lirGen); + } + + private static final class SSIBuilder { + private final SSIBlockValueMapImpl valueMap; + private final LIR lir; + private final BitSet processed; + + private SSIBuilder(LIR lir, FrameMapBuilder frameMapBuilder) { + this.lir = lir; + valueMap = new SSIBlockValueMapImpl(lir.getControlFlowGraph(), lir.nextVariable(), ((FrameMapBuilderTool) frameMapBuilder).getNumberOfStackSlots()); + processed = new BitSet(lir.getControlFlowGraph().getBlocks().size()); + } + + private void build(LIRGeneratorTool lirGen) { + Deque<AbstractBlockBase<?>> worklist = new ArrayDeque<>(lir.getControlFlowGraph().getBlocks()); + while (!worklist.isEmpty()) { + AbstractBlockBase<?> block = worklist.poll(); + if (!processed.get(block.getId())) { + try (Indent indent = Debug.logAndIndent("Try processing Block %s", block)) { + // check predecessors + boolean reschedule = false; + for (AbstractBlockBase<?> pred : block.getPredecessors()) { + if (!processed.get(pred.getId()) && !isLoopBackEdge(pred, block)) { + Debug.log("Schedule predecessor: %s", pred); + worklist.addLast(pred); + reschedule = true; + } + } + if (reschedule) { + Debug.log("Reschedule block %s", block); + worklist.addLast(block); + } else { + processBlock(block); + } + } + } + } + valueMap.finish(lirGen); + } + + public void processBlock(AbstractBlockBase<?> block) { + assert !processed.get(block.getId()) : "Block already processed " + block; + try (Indent indent = Debug.logAndIndent("Process Block %s", block)) { + // track values + ValueConsumer useConsumer = (value, mode, flags) -> { + if (flags.contains(OperandFlag.UNINITIALIZED)) { + AbstractBlockBase<?> startBlock = lir.getControlFlowGraph().getStartBlock(); + Debug.log("Set definition of %s in block %s", value, startBlock); + valueMap.defineOperand(value, startBlock); + } else { + Debug.log("Access %s in block %s", value, block); + valueMap.accessOperand(value, block); + } + }; + ValueConsumer defConsumer = (value, mode, flags) -> { + Debug.log("Set definition of %s in block %s", value, block); + valueMap.defineOperand(value, block); + }; + for (LIRInstruction op : lir.getLIRforBlock(block)) { + // use + op.visitEachInput(useConsumer); + op.visitEachAlive(useConsumer); + op.visitEachState(useConsumer); + // def + op.visitEachTemp(defConsumer); + op.visitEachOutput(defConsumer); + } + processed.set(block.getId()); + } + } + + private static boolean isLoopBackEdge(AbstractBlockBase<?> from, AbstractBlockBase<?> to) { + return from.isLoopEnd() && to.isLoopHeader() && from.getLoop().equals(to.getLoop()); + } + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/ssi/SSIUtil.java Mon Jul 27 16:57:30 2015 -0700 @@ -0,0 +1,191 @@ +/* + * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.lir.ssi; + +import java.util.*; + +import jdk.internal.jvmci.meta.*; + +import com.oracle.graal.compiler.common.cfg.*; +import com.oracle.graal.lir.*; +import com.oracle.graal.lir.StandardOp.BlockEndOp; +import com.oracle.graal.lir.LIRInstruction.*; +import com.oracle.graal.lir.StandardOp.*; +import com.oracle.graal.lir.ssa.SSAUtil.*; + +/** + * Utilities for working with Static-Single-Information LIR form. + * + * <h2>Representation of φ and σ</h2> + * + * There are no explicit φ/σ {@link LIRInstruction}s. Instead, they are implemented as + * parallel copy that spans across a control-flow edge. + * + * The variables introduced by φ/σ of a specific {@linkplain AbstractBlockBase block} are + * {@linkplain LabelOp#setIncomingValues attached} to the {@link LabelOp} of the block. The outgoing + * values from the predecessor are {@linkplain BlockEndOp#setOutgoingValues input} to the + * {@link BlockEndOp} of the predecessor. + * + * When it does not matter whether we are talking about a φ or a σ we call the values that + * are defined by a label {@linkplain LabelOp#setIncomingValues incoming} and the values that are + * input to the {@link BlockEndOp} of the predecessor {@linkplain BlockEndOp#setOutgoingValues + * outgoing}. + * + * <h2>Implementation Details</h2> + * + * For our purposes we want a <em>maximal</em> SSI form, which means that all values that are alive + * across basic block boundaries are gated with a φ/σ. In other words the outgoing and + * incoming values of the {@link BlockEndOp} and {@link LabelOp} are equivalent to the live-out and + * live-in set of the corresponding block. + * + * As a side effect variables are local to a block. We reuse the name of the predecessor if they + * represent the same value (i.e. not a real φ definition). + * + * <h2>Examples</h2> + * + * <h3>Merge (φ)</h3> + * + * <pre> + * B0 -> B1 + * ... + * v0|i = ... + * JUMP ~[v0|i, int[0|0x0]] destination: B0 -> B1 + * ________________________________________________ + * + * B2 -> B1 + * ... + * v1|i = ... + * v2|i = ... + * JUMP ~[v1|i, v2|i] destination: B2 -> B1 + * ________________________________________________ + * + * B1 <- B0,B2 + * [v3|i, v4|i] = LABEL + * ... + * </pre> + * + * Note: the outgoing values of a block can contain constants (see <code>B0</code>). + * + * <h3>Split (σ)</h3> + * + * <pre> + * B0 -> B1,B2 + * ... + * v0|i = ... + * v1|i = ... + * v2|i = ... + * TEST (x: v1|i, y: v1|i) + * BRANCH ~[v2|i, v0|j] condition: <, true: B1 false: B2 + * ________________________________________________ + * + * B1 <- B0 + * [-, v0|j] = LABEL + * ... + * ________________________________________________ + * + * B2 <- B0 + * [v2|i, v0|j] = LABEL + * ... + * </pre> + * + * Note: If a incoming value is not needed in a branch it is {@link Value#ILLEGAL ignored} (see + * <code>B1<code>). + */ +public final class SSIUtil { + + public static BlockEndOp outgoing(LIR lir, AbstractBlockBase<?> block) { + return (BlockEndOp) outgoingInst(lir, block); + } + + public static LIRInstruction outgoingInst(LIR lir, AbstractBlockBase<?> block) { + List<LIRInstruction> instructions = lir.getLIRforBlock(block); + int index = instructions.size() - 1; + LIRInstruction op = instructions.get(index); + return op; + } + + public static LabelOp incoming(LIR lir, AbstractBlockBase<?> block) { + return (LabelOp) incomingInst(lir, block); + } + + private static LIRInstruction incomingInst(LIR lir, AbstractBlockBase<?> block) { + return lir.getLIRforBlock(block).get(0); + } + + public static void removeIncoming(LIR lir, AbstractBlockBase<?> block) { + incoming(lir, block).clearIncomingValues(); + } + + public static void removeOutgoing(LIR lir, AbstractBlockBase<?> block) { + outgoing(lir, block).clearOutgoingValues(); + } + + /** + * Visits each SIGMA/PHI value pair of an edge, i.e. the outgoing value from the predecessor and + * the incoming value to the merge block. + */ + public static void forEachValuePair(LIR lir, AbstractBlockBase<?> toBlock, AbstractBlockBase<?> fromBlock, PhiValueVisitor visitor) { + assert toBlock.getPredecessors().contains(fromBlock) : String.format("%s not in predecessor list: %s", fromBlock, toBlock.getPredecessors()); + assert fromBlock.getSuccessorCount() == 1 || toBlock.getPredecessorCount() == 1 : String.format("Critical Edge? %s has %d successors and %s has %d predecessors", fromBlock, + fromBlock.getSuccessorCount(), toBlock, toBlock.getPredecessorCount()); + assert fromBlock.getSuccessors().contains(toBlock) : String.format("Predecessor block %s has wrong successor: %s, should contain: %s", fromBlock, fromBlock.getSuccessors(), toBlock); + + BlockEndOp blockEnd = outgoing(lir, fromBlock); + LabelOp label = incoming(lir, toBlock); + + assert label.getIncomingSize() == blockEnd.getOutgoingSize() : String.format("In/Out size mismatch: in=%d vs. out=%d, blocks %s vs. %s", label.getIncomingSize(), blockEnd.getOutgoingSize(), + toBlock, fromBlock); + + for (int i = 0; i < label.getIncomingSize(); i++) { + visitor.visit(label.getIncomingValue(i), blockEnd.getOutgoingValue(i)); + } + } + + public static void forEachRegisterHint(LIR lir, AbstractBlockBase<?> block, LabelOp label, Value targetValue, OperandMode mode, ValueConsumer valueConsumer) { + assert mode == OperandMode.DEF : "Wrong operand mode: " + mode; + assert lir.getLIRforBlock(block).get(0).equals(label) : String.format("Block %s and Label %s do not match!", block, label); + + if (!label.isPhiIn()) { + return; + } + int idx = indexOfValue(label, targetValue); + assert idx >= 0 : String.format("Value %s not in label %s", targetValue, label); + + for (AbstractBlockBase<?> pred : block.getPredecessors()) { + BlockEndOp blockEnd = outgoing(lir, pred); + Value sourceValue = blockEnd.getOutgoingValue(idx); + valueConsumer.visitValue((LIRInstruction) blockEnd, sourceValue, null, null); + } + + } + + private static int indexOfValue(LabelOp label, Value value) { + for (int i = 0; i < label.getIncomingSize(); i++) { + if (label.getIncomingValue(i).equals(value)) { + return i; + } + } + return -1; + } + +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/ssi/SSIVerifier.java Mon Jul 27 16:57:30 2015 -0700 @@ -0,0 +1,158 @@ +/* + * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.lir.ssi; + +import static jdk.internal.jvmci.code.ValueUtil.*; + +import java.util.*; + +import jdk.internal.jvmci.meta.*; + +import com.oracle.graal.compiler.common.cfg.*; +import com.oracle.graal.debug.*; +import com.oracle.graal.debug.Debug.Scope; +import com.oracle.graal.lir.*; +import com.oracle.graal.lir.LIRInstruction.OperandFlag; +import com.oracle.graal.lir.LIRInstruction.OperandMode; +import com.oracle.graal.lir.StandardOp.BlockEndOp; +import com.oracle.graal.lir.StandardOp.LabelOp; + +public final class SSIVerifier { + + public static boolean verify(LIR lir) { + return new SSIVerifier(lir).verify(); + } + + private final LIR lir; + + private SSIVerifier(LIR lir) { + this.lir = lir; + } + + private boolean verify() { + try (Scope s = Debug.scope("SSIVerifier", lir)) { + for (AbstractBlockBase<?> block : lir.getControlFlowGraph().getBlocks()) { + doBlock(block); + } + } catch (Throwable e) { + throw Debug.handle(e); + } + return true; + } + + private void doBlock(AbstractBlockBase<?> block) { + for (AbstractBlockBase<?> succ : block.getSuccessors()) { + verifyEdge(block, succ); + } + verifyInstructions(block); + } + + private void verifyEdge(AbstractBlockBase<?> from, AbstractBlockBase<?> to) { + BlockEndOp out = SSIUtil.outgoing(lir, from); + LabelOp in = SSIUtil.incoming(lir, to); + int outgoingSize = out.getOutgoingSize(); + int incomingSize = in.getIncomingSize(); + assert outgoingSize == incomingSize : String.format("Outgoing size %d and incoming size %d do not match", outgoingSize, incomingSize); + + for (int i = 0; i < outgoingSize; i++) { + Value incomingValue = in.getIncomingValue(i); + Value outgoingValue = out.getOutgoingValue(i); + LIRKind inLIRKind = incomingValue.getLIRKind(); + LIRKind outLIRKind = outgoingValue.getLIRKind(); + assert LIRKind.verifyMoveKinds(inLIRKind, outLIRKind) || incomingValue.equals(Value.ILLEGAL) : String.format("Outgoing LIRKind %s (%s) an and incoming LIRKind %s (%s) do not match", + outgoingValue, outLIRKind, incomingValue, inLIRKind); + } + } + + private void verifyInstructions(AbstractBlockBase<?> block) { + List<LIRInstruction> instructions = lir.getLIRforBlock(block); + HashMap<Value, LIRInstruction> defined = new HashMap<>(); + + InstructionValueConsumer useConsumer = new InstructionValueConsumer() { + public void visitValue(LIRInstruction instruction, Value value, OperandMode mode, EnumSet<OperandFlag> flags) { + if (checkUsage(value)) { + assert defined.containsKey(value) || flags.contains(OperandFlag.UNINITIALIZED) : String.format("Value %s is used by instruction %s in block %s but not defined.", value, + instruction, block); + } + } + }; + InstructionValueConsumer stateConsumer = new InstructionValueConsumer() { + public void visitValue(LIRInstruction instruction, Value value, OperandMode mode, EnumSet<OperandFlag> flags) { + if (checkUsage(value)) { + /* + * TODO (je): There are undefined stack values used for locks. Ignore them for + * the time being. + */ + assert defined.containsKey(value) || isVirtualStackSlot(value) : String.format("Value %s is used in state of instruction %s in block %s but not defined.", value, instruction, + block); + } + } + }; + + InstructionValueConsumer defConsumer = new InstructionValueConsumer() { + public void visitValue(LIRInstruction instruction, Value value, OperandMode mode, EnumSet<OperandFlag> flags) { + if (trackDefinition(value)) { + assert !defined.containsKey(value) : String.format("Value %s is redefined by instruction %s in block %s but already defined by %s.", value, instruction, block, defined.get(value)); + defined.put(value, instruction); + } + } + }; + + for (LIRInstruction op : instructions) { + op.visitEachAlive(useConsumer); + op.visitEachInput(useConsumer); + op.visitEachState(stateConsumer); + + op.visitEachTemp(defConsumer); + op.visitEachOutput(defConsumer); + } + } + + private static boolean trackDefinition(Value value) { + if (isRegister(value)) { + // registers can be redefined + return false; + } + if (value.equals(Value.ILLEGAL)) { + // Don't care about illegal values + return false; + } + return true; + } + + private static boolean checkUsage(Value value) { + if (value instanceof Constant) { + // Constants do not need to be defined + return false; + } + if (isRegister(value)) { + // Assume fixed registers are correct + return false; + } + if (value.equals(Value.ILLEGAL)) { + // Don't care about illegal values + return false; + } + return true; + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/util/IndexedValueMap.java Mon Jul 27 16:57:30 2015 -0700 @@ -0,0 +1,163 @@ +/* + * Copyright (c) 2014, 2015, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.lir.util; + +import java.util.*; + +import jdk.internal.jvmci.meta.*; + +import com.oracle.graal.lir.*; +import com.oracle.graal.lir.LIRInstruction.OperandFlag; +import com.oracle.graal.lir.LIRInstruction.OperandMode; + +public final class IndexedValueMap { + private Value[] values; + + public IndexedValueMap() { + values = Value.NO_VALUES; + } + + public IndexedValueMap(IndexedValueMap other) { + int limit = other.values.length; + while (limit > 0) { + if (other.values[limit - 1] == null) { + limit--; + continue; + } + break; + } + values = new Value[limit]; + System.arraycopy(other.values, 0, values, 0, values.length); + } + + public Value get(int index) { + return values[index]; + } + + public void put(int index, Value value) { + if (values.length <= index) { + if (value == null) { + return; + } + Value[] newValues = new Value[index + 1]; + System.arraycopy(values, 0, newValues, 0, values.length); + values = newValues; + values[index] = value; + } else { + values[index] = value; + } + } + + public void putAll(IndexedValueMap stack) { + Value[] otherValues = stack.values; + int limit = otherValues.length; + if (limit > values.length) { + while (limit > 0) { + if (otherValues[limit - 1] == null) { + limit--; + continue; + } + break; + } + if (limit > values.length) { + Value[] newValues = new Value[limit]; + System.arraycopy(values, 0, newValues, 0, values.length); + values = newValues; + } + } + for (int i = 0; i < limit; i++) { + Value value = otherValues[i]; + if (value != null) { + values[i] = value; + } + } + } + + @Override + public boolean equals(Object other) { + if (other instanceof IndexedValueMap) { + IndexedValueMap that = (IndexedValueMap) other; + int limit = Math.min(values.length, that.values.length); + for (int i = 0; i < limit; i++) { + if (!Objects.equals(values[i], that.values[i])) { + return false; + } + } + for (int i = limit; i < values.length; i++) { + if (values[i] != null) { + return false; + } + } + for (int i = limit; i < that.values.length; i++) { + if (that.values[i] != null) { + return false; + } + } + return true; + } + return false; + } + + public void forEach(LIRInstruction inst, OperandMode mode, EnumSet<OperandFlag> flags, InstructionValueProcedure proc) { + for (int i = 0; i < values.length; i++) { + if (values[i] != null) { + values[i] = proc.doValue(inst, values[i], mode, flags); + } + } + } + + public void forEach(LIRInstruction inst, OperandMode mode, EnumSet<OperandFlag> flags, InstructionValueConsumer consumer) { + for (Value v : values) { + if (v != null) { + consumer.visitValue(inst, v, mode, flags); + } + } + } + + @Override + public int hashCode() { + throw new UnsupportedOperationException(); + } + + @Override + public String toString() { + StringBuilder sb = new StringBuilder("["); + boolean comma = false; + + for (int i = 0; i < values.length; i++) { + if (values[i] != null) { + if (comma) { + sb.append(", "); + } else { + comma = true; + } + + sb.append(i); + sb.append(": "); + sb.append(values[i]); + } + } + sb.append(']'); + return sb.toString(); + } +}
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/util/IntValueMap.java Mon Jul 27 16:26:41 2015 -0700 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,163 +0,0 @@ -/* - * Copyright (c) 2014, 2015, Oracle and/or its affiliates. All rights reserved. - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. - * - * This code is free software; you can redistribute it and/or modify it - * under the terms of the GNU General Public License version 2 only, as - * published by the Free Software Foundation. - * - * This code is distributed in the hope that it will be useful, but WITHOUT - * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or - * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License - * version 2 for more details (a copy is included in the LICENSE file that - * accompanied this code). - * - * You should have received a copy of the GNU General Public License version - * 2 along with this work; if not, write to the Free Software Foundation, - * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. - * - * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA - * or visit www.oracle.com if you need additional information or have any - * questions. - */ -package com.oracle.graal.lir.util; - -import java.util.*; - -import jdk.internal.jvmci.meta.*; - -import com.oracle.graal.lir.*; -import com.oracle.graal.lir.LIRInstruction.OperandFlag; -import com.oracle.graal.lir.LIRInstruction.OperandMode; - -public final class IntValueMap { - private Value[] values; - - public IntValueMap() { - values = Value.NO_VALUES; - } - - public IntValueMap(IntValueMap other) { - int limit = other.values.length; - while (limit > 0) { - if (other.values[limit - 1] == null) { - limit--; - continue; - } - break; - } - values = new Value[limit]; - System.arraycopy(other.values, 0, values, 0, values.length); - } - - public Value get(int index) { - return values[index]; - } - - public void put(int index, Value value) { - if (values.length <= index) { - if (value == null) { - return; - } - Value[] newValues = new Value[index + 1]; - System.arraycopy(values, 0, newValues, 0, values.length); - values = newValues; - values[index] = value; - } else { - values[index] = value; - } - } - - public void putAll(IntValueMap stack) { - Value[] otherValues = stack.values; - int limit = otherValues.length; - if (limit > values.length) { - while (limit > 0) { - if (otherValues[limit - 1] == null) { - limit--; - continue; - } - break; - } - if (limit > values.length) { - Value[] newValues = new Value[limit]; - System.arraycopy(values, 0, newValues, 0, values.length); - values = newValues; - } - } - for (int i = 0; i < limit; i++) { - Value value = otherValues[i]; - if (value != null) { - values[i] = value; - } - } - } - - @Override - public boolean equals(Object other) { - if (other instanceof IntValueMap) { - IntValueMap that = (IntValueMap) other; - int limit = Math.min(values.length, that.values.length); - for (int i = 0; i < limit; i++) { - if (!Objects.equals(values[i], that.values[i])) { - return false; - } - } - for (int i = limit; i < values.length; i++) { - if (values[i] != null) { - return false; - } - } - for (int i = limit; i < that.values.length; i++) { - if (that.values[i] != null) { - return false; - } - } - return true; - } - return false; - } - - public void forEach(LIRInstruction inst, OperandMode mode, EnumSet<OperandFlag> flags, InstructionValueProcedure proc) { - for (int i = 0; i < values.length; i++) { - if (values[i] != null) { - values[i] = proc.doValue(inst, values[i], mode, flags); - } - } - } - - public void forEach(LIRInstruction inst, OperandMode mode, EnumSet<OperandFlag> flags, InstructionValueConsumer consumer) { - for (Value v : values) { - if (v != null) { - consumer.visitValue(inst, v, mode, flags); - } - } - } - - @Override - public int hashCode() { - throw new UnsupportedOperationException(); - } - - @Override - public String toString() { - StringBuilder sb = new StringBuilder("["); - boolean comma = false; - - for (int i = 0; i < values.length; i++) { - if (values[i] != null) { - if (comma) { - sb.append(", "); - } else { - comma = true; - } - - sb.append(i); - sb.append(": "); - sb.append(values[i]); - } - } - sb.append(']'); - return sb.toString(); - } -}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/util/VariableVirtualStackValueMap.java Mon Jul 27 16:57:30 2015 -0700 @@ -0,0 +1,98 @@ +/* + * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.lir.util; + +import static com.oracle.graal.lir.LIRValueUtil.*; +import static jdk.internal.jvmci.code.ValueUtil.*; +import jdk.internal.jvmci.common.*; +import jdk.internal.jvmci.meta.*; + +public class VariableVirtualStackValueMap<K extends Value, T> extends ValueMap<K, T> { + + private final Object[] variables; + private final Object[] slots; + + public VariableVirtualStackValueMap(int initialVariableCapacity, int initialStackSlotCapacity) { + variables = new Object[initialVariableCapacity]; + slots = new Object[initialStackSlotCapacity]; + } + + @Override + public T get(K value) { + if (isVariable(value)) { + return get(variables, asVariable(value).index); + } + if (isVirtualStackSlot(value)) { + return get(slots, asVirtualStackSlot(value).getId()); + } + throw JVMCIError.shouldNotReachHere("Unsupported Value: " + value); + } + + @Override + public void remove(K value) { + if (isVariable(value)) { + remove(variables, asVariable(value).index); + } else if (isVirtualStackSlot(value)) { + remove(slots, asVirtualStackSlot(value).getId()); + } else { + throw JVMCIError.shouldNotReachHere("Unsupported Value: " + value); + } + } + + @Override + public void put(K value, T object) { + if (isVariable(value)) { + put(variables, asVariable(value).index, object); + } else if (isVirtualStackSlot(value)) { + put(slots, asVirtualStackSlot(value).getId(), object); + } else { + throw JVMCIError.shouldNotReachHere("Unsupported Value: " + value); + } + } + + @SuppressWarnings("unchecked") + private static <T> T get(Object[] array, int index) { + if (index >= array.length) { + return null; + } + return (T) array[index]; + } + + private static void remove(Object[] array, int index) { + if (index >= array.length) { + return; + } + array[index] = null; + } + + private static <T> Object[] put(Object[] array, int index, T object) { + if (index >= array.length) { + Object[] newArray = new Object[index + 1]; + System.arraycopy(array, 0, newArray, 0, array.length); + newArray[index] = object; + return newArray; + } + array[index] = object; + return null; + } +}
--- a/graal/com.oracle.graal.printer/src/com/oracle/graal/printer/CompilationPrinter.java Mon Jul 27 16:26:41 2015 -0700 +++ b/graal/com.oracle.graal.printer/src/com/oracle/graal/printer/CompilationPrinter.java Mon Jul 27 16:57:30 2015 -0700 @@ -114,7 +114,7 @@ /** * Formats given debug info as a multi line string. */ - protected String debugInfoToString(BytecodePosition codePos, ReferenceMap refMap, IntValueMap liveBasePointers, RegisterSaveLayout calleeSaveInfo) { + protected String debugInfoToString(BytecodePosition codePos, ReferenceMap refMap, IndexedValueMap liveBasePointers, RegisterSaveLayout calleeSaveInfo) { StringBuilder sb = new StringBuilder(); if (refMap != null) { sb.append("reference-map: ");
--- a/mx.graal/mx_graal.py Mon Jul 27 16:26:41 2015 -0700 +++ b/mx.graal/mx_graal.py Mon Jul 27 16:57:30 2015 -0700 @@ -1339,6 +1339,10 @@ with VM('server', 'product'): with Task('UnitTestsNonSSA:hosted-product', tasks) as t: if t: unittest(['--enable-timing', '--verbose', '--fail-fast', '-G:-SSA_LIR']) + # Run unit tests on server-hosted-jvmci with TraceRA + with VM('server', 'product'): + with Task('UnitTestsTraceRA:hosted-product', tasks) as t: + if t: unittest(['--enable-timing', '--verbose', '--fail-fast', '-G:+TraceRA']) # Run ctw against rt.jar on server-hosted-jvmci with VM('server', 'product'): with Task('CTW:hosted-product', tasks) as t: @@ -1388,6 +1392,11 @@ vm(['-XX:-TieredCompilation', '-G:-SSA_LIR', '-G:RegisterPressure=' + registers, '-esa', '-version']) with VM('jvmci', 'product'): + with Task('BootstrapTraceRAWithRegisterPressure:product', tasks) as t: + if t: + vm(['-XX:-TieredCompilation', '-G:+TraceRA', '-G:RegisterPressure=' + registers, '-esa', '-version']) + + with VM('jvmci', 'product'): with Task('BootstrapWithImmutableCode:product', tasks) as t: if t: vm(['-XX:-TieredCompilation', '-G:+ImmutableCode', '-G:+VerifyPhases', '-esa', '-version'])