Mercurial > hg > truffle

changeset 21322:73942ac6e650

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
LinearScan: outsource OptimizeSpillPosition.
author Josef Eisl <josef.eisl@jku.at>
date Tue, 12 May 2015 10:57:59 +0200
parents 1d5955a59d47
children 3570b7d1a6f9
files 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/OptimizeSpillPosition.java
diffstat 2 files changed, 217 insertions(+), 174 deletions(-) [+]
line wrap: on
line diff
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScan.java	Tue May 12 10:49:17 2015 +0200
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScan.java	Tue May 12 10:57:59 2015 +0200
@@ -25,7 +25,6 @@
 import static com.oracle.graal.api.code.CodeUtil.*;
 import static com.oracle.graal.api.code.ValueUtil.*;
 import static com.oracle.graal.compiler.common.GraalOptions.*;
-import static com.oracle.graal.compiler.common.cfg.AbstractControlFlowGraph.*;
 import static com.oracle.graal.lir.LIRValueUtil.*;
 
 import java.util.*;
@@ -1134,7 +1133,7 @@
                  * instruction 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 = ir.getLIRforBlock(block).get(ir.getLIRforBlock(block).size() - 1);
@@ -1242,7 +1241,7 @@
             new RegisterAllocation().apply(target, lirGenRes, codeEmittingOrder, linearScanOrder, context, false);
 
             if (LinearScan.Options.LSRAOptimizeSpillPosition.getValue()) {
-                new OptimizeSpillPosition().apply(target, lirGenRes, codeEmittingOrder, linearScanOrder, context, false);
+                new OptimizeSpillPosition(this).apply(target, lirGenRes, codeEmittingOrder, linearScanOrder, context, false);
             }
             new ResolveDataFlow().apply(target, lirGenRes, codeEmittingOrder, linearScanOrder, context);
 
@@ -1298,177 +1297,6 @@
     protected void beforeSpillMoveElimination() {
     }
 
-    private static final DebugMetric betterSpillPos = Debug.metric("BetterSpillPosition");
-    private static final DebugMetric betterSpillPosWithLowerProbability = Debug.metric("BetterSpillPositionWithLowerProbability");
-
-    private final class OptimizeSpillPosition extends AllocationPhase {
-
-        @Override
-        protected <B extends AbstractBlockBase<B>> void run(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder,
-                        SpillMoveFactory spillMoveFactory) {
-            optimizeSpillPosition();
-            printIntervals("After optimize spill position");
-        }
-
-        private void optimizeSpillPosition() {
-            LIRInsertionBuffer[] insertionBuffers = new LIRInsertionBuffer[ir.linearScanOrder().size()];
-            for (Interval interval : intervals) {
-                if (interval != null && interval.isSplitParent() && interval.spillState() == SpillState.SpillInDominator) {
-                    AbstractBlockBase<?> defBlock = blockForId(interval.spillDefinitionPos());
-                    AbstractBlockBase<?> spillBlock = null;
-                    Interval firstSpillChild = null;
-                    try (Indent indent = Debug.logAndIndent("interval %s (%s)", interval, defBlock)) {
-                        for (Interval splitChild : interval.getSplitChildren()) {
-                            if (isStackSlotValue(splitChild.location())) {
-                                if (firstSpillChild == null || splitChild.from() < firstSpillChild.from()) {
-                                    firstSpillChild = splitChild;
-                                } else {
-                                    assert firstSpillChild.from() < splitChild.from();
-                                }
-                                // iterate all blocks where the interval has use positions
-                                for (AbstractBlockBase<?> splitBlock : blocksForInterval(splitChild)) {
-                                    if (dominates(defBlock, splitBlock)) {
-                                        if (Debug.isLogEnabled()) {
-                                            Debug.log("Split interval %s, block %s", splitChild, splitBlock);
-                                        }
-                                        if (spillBlock == null) {
-                                            spillBlock = splitBlock;
-                                        } else {
-                                            spillBlock = commonDominator(spillBlock, splitBlock);
-                                            assert spillBlock != null;
-                                        }
-                                    }
-                                }
-                            }
-                        }
-                        if (spillBlock == null) {
-                            // no spill interval
-                            interval.setSpillState(SpillState.StoreAtDefinition);
-                        } else {
-                            // move out of loops
-                            if (defBlock.getLoopDepth() < spillBlock.getLoopDepth()) {
-                                spillBlock = moveSpillOutOfLoop(defBlock, spillBlock);
-                            }
-
-                            /*
-                             * If the spill block is the begin of the first split child (aka the
-                             * value is on the stack) spill in the dominator.
-                             */
-                            assert firstSpillChild != null;
-                            if (!defBlock.equals(spillBlock) && spillBlock.equals(blockForId(firstSpillChild.from()))) {
-                                AbstractBlockBase<?> dom = spillBlock.getDominator();
-                                if (Debug.isLogEnabled()) {
-                                    Debug.log("Spill block (%s) is the beginning of a spill child -> use dominator (%s)", spillBlock, dom);
-                                }
-                                spillBlock = dom;
-                            }
-
-                            if (!defBlock.equals(spillBlock)) {
-                                assert dominates(defBlock, spillBlock);
-                                betterSpillPos.increment();
-                                if (Debug.isLogEnabled()) {
-                                    Debug.log("Better spill position found (Block %s)", spillBlock);
-                                }
-
-                                if (defBlock.probability() <= spillBlock.probability()) {
-                                    // better spill block has the same probability -> do nothing
-                                    interval.setSpillState(SpillState.StoreAtDefinition);
-                                } else {
-                                    LIRInsertionBuffer insertionBuffer = insertionBuffers[spillBlock.getId()];
-                                    if (insertionBuffer == null) {
-                                        insertionBuffer = new LIRInsertionBuffer();
-                                        insertionBuffers[spillBlock.getId()] = insertionBuffer;
-                                        insertionBuffer.init(ir.getLIRforBlock(spillBlock));
-                                    }
-                                    int spillOpId = getFirstLirInstructionId(spillBlock);
-                                    // insert spill move
-                                    AllocatableValue fromLocation = interval.getSplitChildAtOpId(spillOpId, OperandMode.DEF, LinearScan.this).location();
-                                    AllocatableValue toLocation = canonicalSpillOpr(interval);
-                                    LIRInstruction move = getSpillMoveFactory().createMove(toLocation, fromLocation);
-                                    move.setId(DOMINATOR_SPILL_MOVE_ID);
-                                    /*
-                                     * We can use the insertion buffer directly because we always
-                                     * insert at position 1.
-                                     */
-                                    insertionBuffer.append(1, move);
-
-                                    betterSpillPosWithLowerProbability.increment();
-                                    interval.setSpillDefinitionPos(spillOpId);
-                                }
-                            } else {
-                                // definition is the best choice
-                                interval.setSpillState(SpillState.StoreAtDefinition);
-                            }
-                        }
-                    }
-                }
-            }
-            for (LIRInsertionBuffer insertionBuffer : insertionBuffers) {
-                if (insertionBuffer != null) {
-                    assert insertionBuffer.initialized() : "Insertion buffer is nonnull but not initialized!";
-                    insertionBuffer.finish();
-                }
-            }
-        }
-
-        /**
-         * Iterate over all {@link AbstractBlockBase blocks} of an interval.
-         */
-        private class IntervalBlockIterator implements Iterator<AbstractBlockBase<?>> {
-
-            Range range;
-            AbstractBlockBase<?> block;
-
-            public IntervalBlockIterator(Interval interval) {
-                range = interval.first();
-                block = blockForId(range.from);
-            }
-
-            public AbstractBlockBase<?> next() {
-                AbstractBlockBase<?> currentBlock = block;
-                int nextBlockIndex = block.getLinearScanNumber() + 1;
-                if (nextBlockIndex < sortedBlocks.size()) {
-                    block = sortedBlocks.get(nextBlockIndex);
-                    if (range.to <= getFirstLirInstructionId(block)) {
-                        range = range.next;
-                        if (range == Range.EndMarker) {
-                            block = null;
-                        } else {
-                            block = blockForId(range.from);
-                        }
-                    }
-                } else {
-                    block = null;
-                }
-                return currentBlock;
-            }
-
-            public boolean hasNext() {
-                return block != null;
-            }
-        }
-
-        private Iterable<AbstractBlockBase<?>> blocksForInterval(Interval interval) {
-            return new Iterable<AbstractBlockBase<?>>() {
-                public Iterator<AbstractBlockBase<?>> iterator() {
-                    return new IntervalBlockIterator(interval);
-                }
-            };
-        }
-
-        private AbstractBlockBase<?> moveSpillOutOfLoop(AbstractBlockBase<?> defBlock, AbstractBlockBase<?> spillBlock) {
-            int defLoopDepth = defBlock.getLoopDepth();
-            for (AbstractBlockBase<?> block = spillBlock.getDominator(); !defBlock.equals(block); block = block.getDominator()) {
-                assert block != null : "spill block not dominated by definition block?";
-                if (block.getLoopDepth() <= defLoopDepth) {
-                    assert block.getLoopDepth() == defLoopDepth : "Cannot spill an interval outside of the loop where it is defined!";
-                    return block;
-                }
-            }
-            return defBlock;
-        }
-    }
-
     void printIntervals(String label) {
         if (Debug.isLogEnabled()) {
             try (Indent indent = Debug.logAndIndent("intervals %s", label)) {
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/OptimizeSpillPosition.java	Tue May 12 10:57:59 2015 +0200
@@ -0,0 +1,215 @@
+/*
+ * 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.compiler.common.cfg.AbstractControlFlowGraph.*;
+
+import java.util.*;
+
+import com.oracle.graal.api.code.*;
+import com.oracle.graal.api.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.alloc.lsra.Interval.SpillState;
+import com.oracle.graal.lir.gen.*;
+import com.oracle.graal.lir.gen.LIRGeneratorTool.SpillMoveFactory;
+import com.oracle.graal.lir.phases.*;
+
+final class OptimizeSpillPosition extends AllocationPhase {
+
+    private static final DebugMetric betterSpillPos = Debug.metric("BetterSpillPosition");
+    private static final DebugMetric betterSpillPosWithLowerProbability = Debug.metric("BetterSpillPositionWithLowerProbability");
+
+    private final LinearScan allocator;
+
+    OptimizeSpillPosition(LinearScan allocator) {
+        this.allocator = allocator;
+    }
+
+    @Override
+    protected <B extends AbstractBlockBase<B>> void run(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder, SpillMoveFactory spillMoveFactory) {
+        optimizeSpillPosition();
+        allocator.printIntervals("After optimize spill position");
+    }
+
+    private void optimizeSpillPosition() {
+        LIRInsertionBuffer[] insertionBuffers = new LIRInsertionBuffer[allocator.ir.linearScanOrder().size()];
+        for (Interval interval : allocator.intervals) {
+            if (interval != null && interval.isSplitParent() && interval.spillState() == SpillState.SpillInDominator) {
+                AbstractBlockBase<?> defBlock = allocator.blockForId(interval.spillDefinitionPos());
+                AbstractBlockBase<?> spillBlock = null;
+                Interval firstSpillChild = null;
+                try (Indent indent = Debug.logAndIndent("interval %s (%s)", interval, defBlock)) {
+                    for (Interval splitChild : interval.getSplitChildren()) {
+                        if (isStackSlotValue(splitChild.location())) {
+                            if (firstSpillChild == null || splitChild.from() < firstSpillChild.from()) {
+                                firstSpillChild = splitChild;
+                            } else {
+                                assert firstSpillChild.from() < splitChild.from();
+                            }
+                            // iterate all blocks where the interval has use positions
+                            for (AbstractBlockBase<?> splitBlock : blocksForInterval(splitChild)) {
+                                if (dominates(defBlock, splitBlock)) {
+                                    if (Debug.isLogEnabled()) {
+                                        Debug.log("Split interval %s, block %s", splitChild, splitBlock);
+                                    }
+                                    if (spillBlock == null) {
+                                        spillBlock = splitBlock;
+                                    } else {
+                                        spillBlock = commonDominator(spillBlock, splitBlock);
+                                        assert spillBlock != null;
+                                    }
+                                }
+                            }
+                        }
+                    }
+                    if (spillBlock == null) {
+                        // no spill interval
+                        interval.setSpillState(SpillState.StoreAtDefinition);
+                    } else {
+                        // move out of loops
+                        if (defBlock.getLoopDepth() < spillBlock.getLoopDepth()) {
+                            spillBlock = moveSpillOutOfLoop(defBlock, spillBlock);
+                        }
+
+                        /*
+                         * If the spill block is the begin of the first split child (aka the value
+                         * is on the stack) spill in the dominator.
+                         */
+                        assert firstSpillChild != null;
+                        if (!defBlock.equals(spillBlock) && spillBlock.equals(allocator.blockForId(firstSpillChild.from()))) {
+                            AbstractBlockBase<?> dom = spillBlock.getDominator();
+                            if (Debug.isLogEnabled()) {
+                                Debug.log("Spill block (%s) is the beginning of a spill child -> use dominator (%s)", spillBlock, dom);
+                            }
+                            spillBlock = dom;
+                        }
+
+                        if (!defBlock.equals(spillBlock)) {
+                            assert dominates(defBlock, spillBlock);
+                            betterSpillPos.increment();
+                            if (Debug.isLogEnabled()) {
+                                Debug.log("Better spill position found (Block %s)", spillBlock);
+                            }
+
+                            if (defBlock.probability() <= spillBlock.probability()) {
+                                // better spill block has the same probability -> do nothing
+                                interval.setSpillState(SpillState.StoreAtDefinition);
+                            } else {
+                                LIRInsertionBuffer insertionBuffer = insertionBuffers[spillBlock.getId()];
+                                if (insertionBuffer == null) {
+                                    insertionBuffer = new LIRInsertionBuffer();
+                                    insertionBuffers[spillBlock.getId()] = insertionBuffer;
+                                    insertionBuffer.init(allocator.ir.getLIRforBlock(spillBlock));
+                                }
+                                int spillOpId = allocator.getFirstLirInstructionId(spillBlock);
+                                // insert spill move
+                                AllocatableValue fromLocation = interval.getSplitChildAtOpId(spillOpId, OperandMode.DEF, allocator).location();
+                                AllocatableValue toLocation = LinearScan.canonicalSpillOpr(interval);
+                                LIRInstruction move = allocator.getSpillMoveFactory().createMove(toLocation, fromLocation);
+                                move.setId(LinearScan.DOMINATOR_SPILL_MOVE_ID);
+                                /*
+                                 * We can use the insertion buffer directly because we always insert
+                                 * at position 1.
+                                 */
+                                insertionBuffer.append(1, move);
+
+                                betterSpillPosWithLowerProbability.increment();
+                                interval.setSpillDefinitionPos(spillOpId);
+                            }
+                        } else {
+                            // definition is the best choice
+                            interval.setSpillState(SpillState.StoreAtDefinition);
+                        }
+                    }
+                }
+            }
+        }
+        for (LIRInsertionBuffer insertionBuffer : insertionBuffers) {
+            if (insertionBuffer != null) {
+                assert insertionBuffer.initialized() : "Insertion buffer is nonnull but not initialized!";
+                insertionBuffer.finish();
+            }
+        }
+    }
+
+    /**
+     * Iterate over all {@link AbstractBlockBase blocks} of an interval.
+     */
+    private class IntervalBlockIterator implements Iterator<AbstractBlockBase<?>> {
+
+        Range range;
+        AbstractBlockBase<?> block;
+
+        public IntervalBlockIterator(Interval interval) {
+            range = interval.first();
+            block = allocator.blockForId(range.from);
+        }
+
+        public AbstractBlockBase<?> next() {
+            AbstractBlockBase<?> currentBlock = block;
+            int nextBlockIndex = block.getLinearScanNumber() + 1;
+            if (nextBlockIndex < allocator.sortedBlocks.size()) {
+                block = allocator.sortedBlocks.get(nextBlockIndex);
+                if (range.to <= allocator.getFirstLirInstructionId(block)) {
+                    range = range.next;
+                    if (range == Range.EndMarker) {
+                        block = null;
+                    } else {
+                        block = allocator.blockForId(range.from);
+                    }
+                }
+            } else {
+                block = null;
+            }
+            return currentBlock;
+        }
+
+        public boolean hasNext() {
+            return block != null;
+        }
+    }
+
+    private Iterable<AbstractBlockBase<?>> blocksForInterval(Interval interval) {
+        return new Iterable<AbstractBlockBase<?>>() {
+            public Iterator<AbstractBlockBase<?>> iterator() {
+                return new IntervalBlockIterator(interval);
+            }
+        };
+    }
+
+    private static AbstractBlockBase<?> moveSpillOutOfLoop(AbstractBlockBase<?> defBlock, AbstractBlockBase<?> spillBlock) {
+        int defLoopDepth = defBlock.getLoopDepth();
+        for (AbstractBlockBase<?> block = spillBlock.getDominator(); !defBlock.equals(block); block = block.getDominator()) {
+            assert block != null : "spill block not dominated by definition block?";
+            if (block.getLoopDepth() <= defLoopDepth) {
+                assert block.getLoopDepth() == defLoopDepth : "Cannot spill an interval outside of the loop where it is defined!";
+                return block;
+            }
+        }
+        return defBlock;
+    }
+}