Mercurial > hg > graal-compiler

changeset 22163:097111e323ff

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
LinearScanOptimizeSpillPositionPhase: outsource optimizeInterval.
author Josef Eisl <josef.eisl@jku.at>
date Tue, 07 Jul 2015 14:18:40 +0200
parents 0d31a8c4fc2e
children 62827991cf80
files graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScanOptimizeSpillPositionPhase.java
diffstat 1 files changed, 101 insertions(+), 94 deletions(-) [+]
line wrap: on
line diff
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScanOptimizeSpillPositionPhase.java	Tue Jul 07 10:53:03 2015 +0200
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScanOptimizeSpillPositionPhase.java	Tue Jul 07 14:18:40 2015 +0200
@@ -62,100 +62,7 @@
         try (Indent indent0 = Debug.logAndIndent("OptimizeSpillPositions")) {
             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) {
-                            Debug.log("not spill interval found");
-                            // no spill interval
-                            interval.setSpillState(SpillState.StoreAtDefinition);
-                        } else {
-                            Debug.log(3, "Spill block candidate (initial): %s", spillBlock);
-                            // move out of loops
-                            if (defBlock.getLoopDepth() < spillBlock.getLoopDepth()) {
-                                spillBlock = moveSpillOutOfLoop(defBlock, spillBlock);
-                            }
-                            Debug.log(3, "Spill block candidate (after loop optimizaton): %s", 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()) {
-                                    Debug.log(3, "Definition has lower probability %s (%f) is lower than spill block %s (%f)", defBlock, defBlock.probability(), spillBlock, 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);
-                                    Debug.log(3, "Insert spill move %s", move);
-                                    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 {
-                                Debug.log(3, "Definition is the best choice: %s", defBlock);
-                                // definition is the best choice
-                                interval.setSpillState(SpillState.StoreAtDefinition);
-                            }
-                        }
-                    }
-                }
+                optimizeInterval(insertionBuffers, interval);
             }
             for (LIRInsertionBuffer insertionBuffer : insertionBuffers) {
                 if (insertionBuffer != null) {
@@ -166,6 +73,106 @@
         }
     }
 
+    private void optimizeInterval(LIRInsertionBuffer[] insertionBuffers, Interval interval) {
+        if (interval == null || !interval.isSplitParent() || interval.spillState() != SpillState.SpillInDominator) {
+            return;
+        }
+        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)) {
+                            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) {
+                Debug.log("not spill interval found");
+                // no spill interval
+                interval.setSpillState(SpillState.StoreAtDefinition);
+                return;
+            }
+            Debug.log(3, "Spill block candidate (initial): %s", spillBlock);
+            // move out of loops
+            if (defBlock.getLoopDepth() < spillBlock.getLoopDepth()) {
+                spillBlock = moveSpillOutOfLoop(defBlock, spillBlock);
+            }
+            Debug.log(3, "Spill block candidate (after loop optimizaton): %s", spillBlock);
+
+            /*
+             * 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.
+             */
+            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()) {
+                    Debug.log(3, "Definition has lower probability %s (%f) is lower than spill block %s (%f)", defBlock, defBlock.probability(), spillBlock, 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);
+                    Debug.log(3, "Insert spill move %s", move);
+                    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 {
+                Debug.log(3, "Definition is the best choice: %s", defBlock);
+                // definition is the best choice
+                interval.setSpillState(SpillState.StoreAtDefinition);
+            }
+        }
+    }
+
     /**
      * Iterate over all {@link AbstractBlockBase blocks} of an interval.
      */