Mercurial > hg > truffle

changeset 21240:1e9242c9735e

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Introduce SSALinearScan and SSAMoveResolver.
author Josef Eisl <josef.eisl@jku.at>
date Tue, 05 May 2015 11:56:10 +0200
parents ad3a3c192be6
children 7b8843cc6610
files CHANGELOG.md graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScan.java graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScanPhase.java graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/MoveResolver.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/SSAMoveResolver.java
diffstat 6 files changed, 305 insertions(+), 5 deletions(-) [+]
line wrap: on
line diff
--- 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
--- 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"</a> by Christian Wimmer and
  * Hanspeter Moessenboeck.
  */
-final class LinearScan {
+class LinearScan {
 
     final TargetDescription target;
     final LIRGenerationResult res;
--- 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<Boolean> SSA_LSRA = new DerivedOptionValue<>(new OptionSupplier<Boolean>() {
+
+        private static final long serialVersionUID = 9115795480259228194L;
+
+        public Boolean get() {
+            return SSA_LIR.getValue() && !SSADestructionPhase.Options.LIREagerSSADestruction.getValue();
+        }
+    });
+
     @Override
     protected <B extends AbstractBlockBase<B>> void run(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> 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();
+        }
     }
 
 }
--- 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];
         }
--- /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<LIRInstruction> 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;
+    }
+}
--- /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);
+    }
+}