# HG changeset patch # User Josef Eisl # Date 1430819770 -7200 # Node ID 1e9242c9735e285c86c0cdb7cc6b6d7a364a1815 # Parent ad3a3c192be6414fcf737ca5f72ad789f7b86460 Introduce SSALinearScan and SSAMoveResolver. diff -r ad3a3c192be6 -r 1e9242c9735e CHANGELOG.md --- a/CHANGELOG.md Thu Apr 30 15:32:34 2015 +0200 +++ b/CHANGELOG.md Tue May 05 11:56:10 2015 +0200 @@ -6,6 +6,7 @@ ## `tip` ### Graal * Add experimental support constructing low-level IR in SSA form. +* Add experimental support for SSA linear scan register allocation. ... ### Truffle diff -r ad3a3c192be6 -r 1e9242c9735e graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScan.java --- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScan.java Thu Apr 30 15:32:34 2015 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScan.java Tue May 05 11:56:10 2015 +0200 @@ -58,7 +58,7 @@ * >"Optimized Interval Splitting in a Linear Scan Register Allocator" by Christian Wimmer and * Hanspeter Moessenboeck. */ -final class LinearScan { +class LinearScan { final TargetDescription target; final LIRGenerationResult res; diff -r ad3a3c192be6 -r 1e9242c9735e graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScanPhase.java --- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScanPhase.java Thu Apr 30 15:32:34 2015 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScanPhase.java Tue May 05 11:56:10 2015 +0200 @@ -22,6 +22,8 @@ */ package com.oracle.graal.lir.alloc.lsra; +import static com.oracle.graal.compiler.common.GraalOptions.*; + import java.util.*; import com.oracle.graal.api.code.*; @@ -30,12 +32,28 @@ 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.*; +import com.oracle.graal.options.*; +import com.oracle.graal.options.DerivedOptionValue.OptionSupplier; public final class LinearScanPhase extends AllocationPhase { + public static final DerivedOptionValue SSA_LSRA = new DerivedOptionValue<>(new OptionSupplier() { + + private static final long serialVersionUID = 9115795480259228194L; + + public Boolean get() { + return SSA_LIR.getValue() && !SSADestructionPhase.Options.LIREagerSSADestruction.getValue(); + } + }); + @Override protected > void run(TargetDescription target, LIRGenerationResult lirGenRes, List codeEmittingOrder, List linearScanOrder, SpillMoveFactory spillMoveFactory) { - new LinearScan(target, lirGenRes, spillMoveFactory, new RegisterAllocationConfig(lirGenRes.getFrameMapBuilder().getRegisterConfig())).allocate(); + if (LinearScanPhase.SSA_LSRA.getValue()) { + new SSALinearScan(target, lirGenRes, spillMoveFactory, new RegisterAllocationConfig(lirGenRes.getFrameMapBuilder().getRegisterConfig())).allocate(); + } else { + new LinearScan(target, lirGenRes, spillMoveFactory, new RegisterAllocationConfig(lirGenRes.getFrameMapBuilder().getRegisterConfig())).allocate(); + } } } diff -r ad3a3c192be6 -r 1e9242c9735e graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/MoveResolver.java --- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/MoveResolver.java Thu Apr 30 15:32:34 2015 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/MoveResolver.java Tue May 05 11:56:10 2015 +0200 @@ -35,7 +35,7 @@ /** */ -final class MoveResolver { +class MoveResolver { private final LinearScan allocator; @@ -48,7 +48,7 @@ private boolean multipleReadsAllowed; private final int[] registerBlocked; - private void setValueBlocked(Value location, int direction) { + protected void setValueBlocked(Value location, int direction) { assert direction == 1 || direction == -1 : "out of bounds"; if (isRegister(location)) { registerBlocked[asRegister(location).number] += direction; @@ -57,7 +57,7 @@ } } - private int valueBlocked(Value location) { + protected int valueBlocked(Value location) { if (isRegister(location)) { return registerBlocked[asRegister(location).number]; } diff -r ad3a3c192be6 -r 1e9242c9735e graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/SSALinearScan.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/SSALinearScan.java Tue May 05 11:56:10 2015 +0200 @@ -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.alloc.lsra; + +import static com.oracle.graal.api.code.ValueUtil.*; +import static com.oracle.graal.lir.LIRValueUtil.*; + +import java.util.*; + +import com.oracle.graal.api.code.*; +import com.oracle.graal.api.meta.*; +import com.oracle.graal.compiler.common.alloc.*; +import com.oracle.graal.compiler.common.cfg.*; +import com.oracle.graal.debug.*; +import com.oracle.graal.debug.Debug.*; +import com.oracle.graal.lir.*; +import com.oracle.graal.lir.StandardOp.*; +import com.oracle.graal.lir.gen.*; +import com.oracle.graal.lir.gen.LIRGeneratorTool.SpillMoveFactory; +import com.oracle.graal.lir.ssa.*; +import com.oracle.graal.lir.ssa.SSAUtils.PhiValueVisitor; + +final class SSALinearScan extends LinearScan { + + private static final DebugMetric numStackToStackMoves = Debug.metric("SSA LSRA[numStackToStackMoves]"); + + SSALinearScan(TargetDescription target, LIRGenerationResult res, SpillMoveFactory spillMoveFactory, RegisterAllocationConfig regAllocConfig) { + super(target, res, spillMoveFactory, regAllocConfig); + } + + @Override + protected MoveResolver createMoveResolver() { + return new SSAMoveResolver(this); + } + + @Override + protected int firstInstructionOfInterest() { + // also look at Labels as they define PHI values + return 0; + } + + @Override + void resolveCollectMappings(AbstractBlockBase fromBlock, AbstractBlockBase toBlock, AbstractBlockBase midBlock, MoveResolver moveResolver) { + super.resolveCollectMappings(fromBlock, toBlock, midBlock, moveResolver); + + if (toBlock.getPredecessorCount() > 1) { + int toBlockFirstInstructionId = getFirstLirInstructionId(toBlock); + int fromBlockLastInstructionId = getLastLirInstructionId(fromBlock) + 1; + + AbstractBlockBase phiOutBlock = midBlock != null ? midBlock : fromBlock; + List instructions = ir.getLIRforBlock(phiOutBlock); + int phiOutIdx = SSAUtils.phiOutIndex(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) { + Interval toInterval = splitChildAtOpId(intervalFor(phiIn), toBlockFirstInstructionId, LIRInstruction.OperandMode.DEF); + if (isConstant(phiOut)) { + moveResolver.addMapping(phiOut, toInterval); + } else { + Interval fromInterval = splitChildAtOpId(intervalFor(phiOut), phiOutId, LIRInstruction.OperandMode.DEF); + if (fromInterval != toInterval && !fromInterval.location().equals(toInterval.location())) { + if (!(isStackSlotValue(toInterval.location()) && isStackSlotValue(fromInterval.location()))) { + moveResolver.addMapping(fromInterval, toInterval); + } else { + numStackToStackMoves.increment(); + moveResolver.addMapping(fromInterval, toInterval); + } + } + } + } + }; + + SSAUtils.forEachPhiValuePair(ir, toBlock, phiOutBlock, visitor); + SSAUtils.removePhiOut(ir, phiOutBlock); + } + } + + @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); + } + } + } + } + + @Override + protected boolean canEliminateSpillMove(AbstractBlockBase block, MoveOp move) { + // SSA Linear Scan might introduce moves to stack slots + assert isVariable(move.getResult()) || LinearScanPhase.SSA_LSRA.getValue() : "Move should not be produced in a non-SSA compilation: " + move; + + Interval curInterval = intervalFor(move.getResult()); + + if (!isRegister(curInterval.location()) && curInterval.alwaysInMemory() && !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) { + if (!LinearScanPhase.SSA_LSRA.getValue()) { + return false; + } + 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 = instructionForId(toInterval.from()); + if (!(op instanceof LabelOp)) { + return false; + } + AbstractBlockBase intStartBlock = blockForId(toInterval.from()); + assert 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; + } +} diff -r ad3a3c192be6 -r 1e9242c9735e graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/SSAMoveResolver.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/SSAMoveResolver.java Tue May 05 11:56:10 2015 +0200 @@ -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; + +import static com.oracle.graal.api.code.ValueUtil.*; + +import java.util.*; + +import com.oracle.graal.api.meta.*; +import com.oracle.graal.lir.*; +import com.oracle.graal.lir.framemap.*; + +final class SSAMoveResolver extends MoveResolver { + + private int[] stackBlocked = null; + + SSAMoveResolver(LinearScan allocator) { + super(allocator); + this.stackBlocked = new int[((FrameMapBuilderTool) allocator.frameMapBuilder).getNumberOfStackSlots()]; + } + + @Override + boolean checkEmpty() { + if (stackBlocked != null) { + 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; + } + + @Override + protected void setValueBlocked(Value location, int direction) { + assert direction == 1 || direction == -1 : "out of bounds"; + if (isVirtualStackSlot(location)) { + assert LinearScanPhase.SSA_LSRA.getValue() : "should only happen if SSA LSRA is used!"; + int stack = asVirtualStackSlot(location).getId(); + if (stack >= stackBlocked.length) { + stackBlocked = Arrays.copyOf(stackBlocked, stack + 1); + } + stackBlocked[stack] += direction; + } else if (isStackSlot(location)) { + assert LinearScanPhase.SSA_LSRA.getValue() : "should only happen if SSA LSRA is used!"; + assert asStackSlot(location).isInCallerFrame() : "Unexpected stack slot: " + location; + // incoming stack arguments can be ignored + } else { + super.setValueBlocked(location, direction); + } + } + + @Override + protected int valueBlocked(Value location) { + if (isVirtualStackSlot(location)) { + assert LinearScanPhase.SSA_LSRA.getValue() : "should only happen if SSA LSRA is used!"; + int stack = asVirtualStackSlot(location).getId(); + if (stack >= stackBlocked.length) { + return 0; + } + return stackBlocked[stack]; + } + if (isStackSlot(location)) { + assert LinearScanPhase.SSA_LSRA.getValue() : "should only happen if SSA LSRA is used!"; + assert asStackSlot(location).isInCallerFrame() : "Unexpected stack slot: " + location; + // incoming stack arguments are always blocked (aka they can not be written) + return 1; + } + 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); + } +}