# HG changeset patch
# User Tom Rodriguez <tom.rodriguez@oracle.com>
# Date 1404333610 25200
# Node ID c68c5fafef92a558cde2f3773df43375be928d50
# Parent  31e242cad4d106c6eb5dc654fe68299092641757# Parent  8057279ec60e0e1dfb5fc0ebf0e7bbeae5d5f2e1
Merge

diff -r 31e242cad4d1 -r c68c5fafef92 graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/alloc/Interval.java
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/alloc/Interval.java	Wed Jul 02 13:05:02 2014 -0700
+++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/alloc/Interval.java	Wed Jul 02 13:40:10 2014 -0700
@@ -309,6 +309,12 @@
         OneSpillStore,
 
         /**
+         * The interval is spilled multiple times or is spilled in a loop. Place the store somewhere
+         * on the dominator path between the definition and the usages.
+         */
+        SpillInDominator,
+
+        /**
          * The interval should be stored immediately after its definition to prevent multiple
          * redundant stores.
          */
@@ -649,13 +655,14 @@
     }
 
     void setSpillDefinitionPos(int pos) {
-        assert spillDefinitionPos() == -1 : "cannot set the position twice";
+        assert spillState() == SpillState.SpillInDominator || 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() {
-        return (splitParent().spillState == SpillState.StoreAtDefinition || splitParent().spillState == SpillState.StartInMemory) && !canMaterialize();
+        return (splitParent().spillState == SpillState.SpillInDominator || splitParent().spillState == SpillState.StoreAtDefinition || splitParent().spillState == SpillState.StartInMemory) &&
+                        !canMaterialize();
     }
 
     void removeFirstUsePos() {
@@ -1289,4 +1296,8 @@
         }
         return buf.toString();
     }
+
+    List<Interval> getSplitChildren() {
+        return Collections.unmodifiableList(splitChildren);
+    }
 }
diff -r 31e242cad4d1 -r c68c5fafef92 graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/alloc/LinearScan.java
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/alloc/LinearScan.java	Wed Jul 02 13:05:02 2014 -0700
+++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/alloc/LinearScan.java	Wed Jul 02 13:40:10 2014 -0700
@@ -25,6 +25,7 @@
 import static com.oracle.graal.api.code.CodeUtil.*;
 import static com.oracle.graal.api.code.ValueUtil.*;
 import static com.oracle.graal.compiler.GraalDebugConfig.*;
+import static com.oracle.graal.compiler.common.cfg.AbstractBlock.*;
 import static com.oracle.graal.lir.LIRValueUtil.*;
 
 import java.util.*;
@@ -41,13 +42,14 @@
 import com.oracle.graal.debug.*;
 import com.oracle.graal.debug.Debug.Scope;
 import com.oracle.graal.lir.*;
+import com.oracle.graal.lir.LIRInstruction.InstructionStateProcedure;
 import com.oracle.graal.lir.LIRInstruction.InstructionValueProcedure;
 import com.oracle.graal.lir.LIRInstruction.OperandFlag;
 import com.oracle.graal.lir.LIRInstruction.OperandMode;
-import com.oracle.graal.lir.LIRInstruction.StateProcedure;
 import com.oracle.graal.lir.LIRInstruction.ValueProcedure;
 import com.oracle.graal.lir.StandardOp.MoveOp;
 import com.oracle.graal.nodes.*;
+import com.oracle.graal.options.*;
 import com.oracle.graal.phases.util.*;
 
 /**
@@ -66,8 +68,16 @@
 
     boolean callKillsRegisters;
 
+    public static final int DOMINATOR_SPILL_MOVE_ID = -2;
     private static final int SPLIT_INTERVALS_CAPACITY_RIGHT_SHIFT = 1;
 
+    public static class Options {
+        // @formatter:off
+        @Option(help = "Enable spill position optimization")
+        public static final OptionValue<Boolean> LSRAOptimizeSpillPosition = new OptionValue<>(true);
+        // @formatter:on
+    }
+
     public static class BlockData {
 
         /**
@@ -441,9 +451,14 @@
 
                 if (defLoopDepth < spillLoopDepth) {
                     // the loop depth of the spilling position is higher then the loop depth
-                    // at the definition of the interval . move write to memory out of loop
-                    // by storing at definitin of the interval
-                    interval.setSpillState(SpillState.StoreAtDefinition);
+                    // at the definition of the interval . move write to memory out of loop.
+                    if (Options.LSRAOptimizeSpillPosition.getValue()) {
+                        // find best spill position in dominator the tree
+                        interval.setSpillState(SpillState.SpillInDominator);
+                    } else {
+                        // store at definition of the interval
+                        interval.setSpillState(SpillState.StoreAtDefinition);
+                    }
                 } else {
                     // the interval is currently spilled only once, so for now there is no
                     // reason to store the interval at the definition
@@ -453,12 +468,18 @@
             }
 
             case OneSpillStore: {
-                // the interval is spilled more then once, so it is better to store it to
-                // memory at the definition
-                interval.setSpillState(SpillState.StoreAtDefinition);
+                if (Options.LSRAOptimizeSpillPosition.getValue()) {
+                    // the interval is spilled more then once
+                    interval.setSpillState(SpillState.SpillInDominator);
+                } else {
+                    // it is better to store it to
+                    // memory at the definition
+                    interval.setSpillState(SpillState.StoreAtDefinition);
+                }
                 break;
             }
 
+            case SpillInDominator:
             case StoreAtDefinition:
             case StartInMemory:
             case NoOptimization:
@@ -1662,6 +1683,9 @@
         // included in the oop map
         iw.walkBefore(op.id());
 
+        // TODO(je) we could pass this as parameter
+        AbstractBlock<?> block = blockForId(op.id());
+
         // Iterate through active intervals
         for (Interval interval = iw.activeLists.get(RegisterBinding.Fixed); interval != Interval.EndMarker; interval = interval.next) {
             Value operand = interval.operand;
@@ -1684,11 +1708,25 @@
                 // Spill optimization: when the stack value is guaranteed to be always correct,
                 // then it must be added to the oop map even if the interval is currently in a
                 // register
-                if (interval.alwaysInMemory() && op.id() > interval.spillDefinitionPos() && !interval.location().equals(interval.spillSlot())) {
-                    assert interval.spillDefinitionPos() > 0 : "position not set correctly";
-                    assert interval.spillSlot() != null : "no spill slot assigned";
-                    assert !isRegister(interval.operand) : "interval is on stack :  so stack slot is registered twice";
-                    info.markLocation(interval.spillSlot(), frameMap);
+                int spillPos = interval.spillDefinitionPos();
+                if (interval.spillState() != SpillState.SpillInDominator) {
+                    if (interval.alwaysInMemory() && op.id() > interval.spillDefinitionPos() && !interval.location().equals(interval.spillSlot())) {
+                        assert interval.spillDefinitionPos() > 0 : "position not set correctly";
+                        assert spillPos > 0 : "position not set correctly";
+                        assert interval.spillSlot() != null : "no spill slot assigned";
+                        assert !isRegister(interval.operand) : "interval is on stack :  so stack slot is registered twice";
+                        info.markLocation(interval.spillSlot(), frameMap);
+                    }
+                } else {
+                    AbstractBlock<?> spillBlock = blockForId(spillPos);
+                    if (interval.alwaysInMemory() && !interval.location().equals(interval.spillSlot())) {
+                        if ((spillBlock.equals(block) && op.id() > spillPos) || AbstractBlock.dominates(spillBlock, block)) {
+                            assert spillPos > 0 : "position not set correctly";
+                            assert interval.spillSlot() != null : "no spill slot assigned";
+                            assert !isRegister(interval.operand) : "interval is on stack :  so stack slot is registered twice";
+                            info.markLocation(interval.spillSlot(), frameMap);
+                        }
+                    }
                 }
             }
         }
@@ -1753,6 +1791,13 @@
                 return operand;
             }
         };
+        InstructionStateProcedure stateProc = new InstructionStateProcedure() {
+
+            @Override
+            protected void doState(LIRInstruction op, LIRFrameState state) {
+                computeDebugInfo(iw, op, state);
+            }
+        };
 
         for (int j = 0; j < numInst; j++) {
             final LIRInstruction op = instructions.get(j);
@@ -1784,13 +1829,7 @@
             op.forEachOutput(assignProc);
 
             // compute reference map and debug information
-            op.forEachState(new StateProcedure() {
-
-                @Override
-                protected void doState(LIRFrameState state) {
-                    computeDebugInfo(iw, op, state);
-                }
-            });
+            op.forEachState(stateProc);
 
             // remove useless moves
             if (move != null) {
@@ -1843,6 +1882,14 @@
                 throw Debug.handle(e);
             }
 
+            if (Options.LSRAOptimizeSpillPosition.getValue()) {
+                try (Scope s = Debug.scope("OptimizeSpillPosition")) {
+                    optimizeSpillPosition();
+                } catch (Throwable e) {
+                    throw Debug.handle(e);
+                }
+            }
+
             try (Scope s = Debug.scope("ResolveDataFlow")) {
                 resolveDataFlow();
             } catch (Throwable e) {
@@ -1861,8 +1908,17 @@
                     verify();
                 }
 
-                eliminateSpillMoves();
-                assignLocations();
+                try (Scope s1 = Debug.scope("EliminateSpillMove")) {
+                    eliminateSpillMoves();
+                } catch (Throwable e) {
+                    throw Debug.handle(e);
+                }
+
+                try (Scope s1 = Debug.scope("AssignLocations")) {
+                    assignLocations();
+                } catch (Throwable e) {
+                    throw Debug.handle(e);
+                }
 
                 if (DetailedAsserts.getValue()) {
                     verifyIntervals();
@@ -1875,6 +1931,190 @@
         }
     }
 
+    private DebugMetric betterSpillPos = Debug.metric("BetterSpillPosition");
+    private DebugMetric betterSpillPosWithLowerProbability = Debug.metric("BetterSpillPositionWithLowerProbability");
+
+    private void optimizeSpillPosition() {
+        LIRInsertionBuffer[] insertionBuffers = new LIRInsertionBuffer[ir.linearScanOrder().size()];
+        for (Interval interval : intervals) {
+            if (interval != null && interval.isSplitParent() && interval.spillState() == SpillState.SpillInDominator) {
+                AbstractBlock<?> defBlock = blockForId(interval.spillDefinitionPos());
+                AbstractBlock<?> spillBlock = null;
+                Interval firstSpillChild = null;
+                try (Indent indent = Debug.logAndIndent("interval %s (%s)", interval, defBlock)) {
+                    for (Interval splitChild : interval.getSplitChildren()) {
+                        if (isStackSlot(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 (AbstractBlock<?> splitBlock : blocksForInterval(splitChild)) {
+                                if (dominates(defBlock, splitBlock)) {
+                                    Debug.log("Split interval %s, block %s", splitChild, splitBlock);
+                                    if (spillBlock == null) {
+                                        spillBlock = splitBlock;
+                                    } else {
+                                        spillBlock = nearestCommonDominator(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()))) {
+                            AbstractBlock<?> dom = spillBlock.getDominator();
+                            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();
+                            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, this).location();
+                                AllocatableValue toLocation = canonicalSpillOpr(interval);
+                                LIRInstruction move = ir.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 AbstractBlock blocks} of an interval.
+     */
+    private class IntervalBlockIterator implements Iterator<AbstractBlock<?>> {
+
+        Range range;
+        AbstractBlock<?> block;
+
+        public IntervalBlockIterator(Interval interval) {
+            range = interval.first();
+            block = blockForId(range.from);
+        }
+
+        public AbstractBlock<?> next() {
+            AbstractBlock<?> 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<AbstractBlock<?>> blocksForInterval(Interval interval) {
+        return new Iterable<AbstractBlock<?>>() {
+            public Iterator<AbstractBlock<?>> iterator() {
+                return new IntervalBlockIterator(interval);
+            }
+        };
+    }
+
+    private static AbstractBlock<?> moveSpillOutOfLoop(AbstractBlock<?> defBlock, AbstractBlock<?> spillBlock) {
+        int defLoopDepth = defBlock.getLoopDepth();
+        for (AbstractBlock<?> 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;
+    }
+
+    private AbstractBlock<?> nearestCommonDominator(AbstractBlock<?> a, AbstractBlock<?> b) {
+        assert a != null;
+        assert b != null;
+        try (Indent indent = Debug.logAndIndent("nearest common dominator of %s and %s", a, b)) {
+
+            if (a.equals(b)) {
+                return a;
+            }
+
+            // collect a's dominators
+            BitSet aDom = new BitSet(sortedBlocks.size());
+
+            // a != b
+            for (AbstractBlock<?> x = a; x != null; x = x.getDominator()) {
+                aDom.set(x.getId());
+            }
+
+            // walk b's dominator
+            for (AbstractBlock<?> x = b; x != null; x = x.getDominator()) {
+                if (aDom.get(x.getId())) {
+                    Debug.log("found %s", x);
+                    return x;
+                }
+            }
+        }
+        Debug.log("no common dominator found");
+        return null;
+    }
+
     void printIntervals(String label) {
         if (Debug.isLogEnabled()) {
             try (Indent indent = Debug.logAndIndent("intervals %s", label)) {
diff -r 31e242cad4d1 -r c68c5fafef92 graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/alloc/RegisterVerifier.java
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/alloc/RegisterVerifier.java	Wed Jul 02 13:05:02 2014 -0700
+++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/alloc/RegisterVerifier.java	Wed Jul 02 13:40:10 2014 -0700
@@ -191,7 +191,8 @@
 
             @Override
             public Value doValue(LIRInstruction op, Value operand, OperandMode mode, EnumSet<OperandFlag> flags) {
-                if (LinearScan.isVariableOrRegister(operand) && allocator.isProcessed(operand)) {
+                // we skip spill moves inserted by the spill position optimization
+                if (LinearScan.isVariableOrRegister(operand) && allocator.isProcessed(operand) && op.id() != LinearScan.DOMINATOR_SPILL_MOVE_ID) {
                     Interval interval = intervalAt(operand);
                     if (op.id() != -1) {
                         interval = interval.getSplitChildAtOpId(op.id(), mode, allocator);
diff -r 31e242cad4d1 -r c68c5fafef92 graal/com.oracle.graal.hotspot.amd64/src/com/oracle/graal/hotspot/amd64/AMD64HotSpotCompare.java
--- a/graal/com.oracle.graal.hotspot.amd64/src/com/oracle/graal/hotspot/amd64/AMD64HotSpotCompare.java	Wed Jul 02 13:05:02 2014 -0700
+++ b/graal/com.oracle.graal.hotspot.amd64/src/com/oracle/graal/hotspot/amd64/AMD64HotSpotCompare.java	Wed Jul 02 13:40:10 2014 -0700
@@ -26,6 +26,7 @@
 import static com.oracle.graal.lir.LIRInstruction.OperandFlag.*;
 
 import com.oracle.graal.api.meta.*;
+import com.oracle.graal.asm.*;
 import com.oracle.graal.asm.amd64.*;
 import com.oracle.graal.compiler.common.*;
 import com.oracle.graal.hotspot.data.*;
@@ -109,8 +110,11 @@
                     // compressed metaspace pointer
                     crb.recordInlineDataInCode(new MetaspaceData(0, y.asInt(), HotSpotMetaspaceConstant.getMetaspaceObject(y), true));
                     masm.cmpl(address.toAddress(), y.asInt());
+                } else if (y.getKind() == Kind.Long && NumUtil.is32bit(y.asLong())) {
+                    // uncompressed metaspace pointer
+                    crb.recordInlineDataInCode(new MetaspaceData(0, y.asLong(), HotSpotMetaspaceConstant.getMetaspaceObject(y), false));
+                    masm.cmpq(address.toAddress(), (int) y.asLong());
                 } else {
-                    // uncompressed metaspace pointer
                     throw GraalInternalError.shouldNotReachHere();
                 }
             } else {
diff -r 31e242cad4d1 -r c68c5fafef92 graal/com.oracle.graal.lir/src/com/oracle/graal/lir/LIRInstruction.java
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/LIRInstruction.java	Wed Jul 02 13:05:02 2014 -0700
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/LIRInstruction.java	Wed Jul 02 13:40:10 2014 -0700
@@ -121,19 +121,29 @@
         }
 
         @Override
-        final protected Value doValue(LIRInstruction instruction, Value value) {
+        protected final Value doValue(LIRInstruction instruction, Value value) {
             throw GraalInternalError.shouldNotReachHere("This doValue() methods should never be called");
         }
 
         @Override
-        final public Value doValue(LIRInstruction instruction, Value value, OperandMode mode, EnumSet<OperandFlag> flags) {
+        public final Value doValue(LIRInstruction instruction, Value value, OperandMode mode, EnumSet<OperandFlag> flags) {
             return doValue(value, mode, flags);
         }
     }
 
-    public abstract static class StateProcedure {
+    public abstract static class InstructionStateProcedure {
+
+        protected abstract void doState(LIRInstruction instruction, LIRFrameState state);
+    }
+
+    public abstract static class StateProcedure extends InstructionStateProcedure {
 
         protected abstract void doState(LIRFrameState state);
+
+        @Override
+        protected final void doState(LIRInstruction instruction, LIRFrameState state) {
+            doState(state);
+        }
     }
 
     /**
@@ -349,7 +359,7 @@
         instructionClass.forEachState(this, proc);
     }
 
-    public final void forEachState(StateProcedure proc) {
+    public final void forEachState(InstructionStateProcedure proc) {
         instructionClass.forEachState(this, proc);
     }
 
diff -r 31e242cad4d1 -r c68c5fafef92 graal/com.oracle.graal.lir/src/com/oracle/graal/lir/LIRInstructionClass.java
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/LIRInstructionClass.java	Wed Jul 02 13:05:02 2014 -0700
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/LIRInstructionClass.java	Wed Jul 02 13:40:10 2014 -0700
@@ -28,10 +28,10 @@
 import com.oracle.graal.api.code.*;
 import com.oracle.graal.api.meta.*;
 import com.oracle.graal.compiler.common.*;
+import com.oracle.graal.lir.LIRInstruction.InstructionStateProcedure;
 import com.oracle.graal.lir.LIRInstruction.InstructionValueProcedure;
 import com.oracle.graal.lir.LIRInstruction.OperandFlag;
 import com.oracle.graal.lir.LIRInstruction.OperandMode;
-import com.oracle.graal.lir.LIRInstruction.StateProcedure;
 import com.oracle.graal.lir.LIRInstruction.ValuePositionProcedure;
 
 public class LIRInstructionClass extends LIRIntrospection {
@@ -371,11 +371,11 @@
         }
     }
 
-    public final void forEachState(LIRInstruction obj, StateProcedure proc) {
+    public final void forEachState(LIRInstruction obj, InstructionStateProcedure proc) {
         for (int i = 0; i < stateOffsets.length; i++) {
             LIRFrameState state = getState(obj, stateOffsets[i]);
             if (state != null) {
-                proc.doState(state);
+                proc.doState(obj, state);
             }
         }
     }