--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceInterval.java	Thu Nov 26 22:58:57 2015 -0800
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceInterval.java	Thu Nov 26 14:22:06 2015 +0100
@@ -525,7 +525,8 @@
      * {@code opId}.
      */
     public boolean inMemoryAt(int opId) {
-        return SpillState.IN_MEMORY.contains(spillState()) && !canMaterialize() && opId > spillDefinitionPos();
+        SpillState spillSt = spillState();
+        return spillSt == SpillState.StartInMemory || (spillSt == SpillState.SpillStore && opId > spillDefinitionPos() && !canMaterialize());
     }
 
     void removeFirstUsePos() {

--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanWalker.java	Thu Nov 26 22:58:57 2015 -0800
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanWalker.java	Thu Nov 26 14:22:06 2015 +0100
@@ -30,6 +30,7 @@
 
 import java.util.ArrayList;
 import java.util.Arrays;
+import java.util.BitSet;
 import java.util.List;
 
 import jdk.vm.ci.code.BailoutException;
@@ -59,6 +60,7 @@
 
     private final int[] usePos;
     private final int[] blockPos;
+    private final BitSet isInMemory;
 
     private List<TraceInterval>[] spillIntervals;
 
@@ -94,12 +96,14 @@
         super(allocator, unhandledFixedFirst, unhandledAnyFirst);
 
         moveResolver = allocator.createMoveResolver();
-        spillIntervals = Util.uncheckedCast(new List<?>[allocator.getRegisters().length]);
-        for (int i = 0; i < allocator.getRegisters().length; i++) {
+        int numRegs = allocator.getRegisters().length;
+        spillIntervals = Util.uncheckedCast(new List<?>[numRegs]);
+        for (int i = 0; i < numRegs; i++) {
             spillIntervals[i] = EMPTY_LIST;
         }
-        usePos = new int[allocator.getRegisters().length];
-        blockPos = new int[allocator.getRegisters().length];
+        usePos = new int[numRegs];
+        blockPos = new int[numRegs];
+        isInMemory = new BitSet(numRegs);
     }
 
     private void initUseLists(boolean onlyProcessUsePos) {
@@ -110,6 +114,7 @@
             if (!onlyProcessUsePos) {
                 blockPos[i] = Integer.MAX_VALUE;
                 spillIntervals[i].clear();
+                isInMemory.clear(i);
             }
         }
     }
@@ -149,6 +154,10 @@
                         spillIntervals[i] = list;
                     }
                     list.add(interval);
+                    // set is in memory flag
+                    if (interval.inMemoryAt(currentPosition)) {
+                        isInMemory.set(i);
+                    }
                 }
             }
         }
@@ -859,43 +868,55 @@
                     if (availableReg.equals(ignore)) {
                         // this register must be ignored
                     } else if (usePos[number] > regNeededUntil) {
-                        if (reg == null || (usePos[number] > usePos[reg.number])) {
+                        /*
+                         * If the use position is the same, prefer registers (active intervals)
+                         * where the value is already on the stack.
+                         */
+                        if (reg == null || (usePos[number] > usePos[reg.number]) || (usePos[number] == usePos[reg.number] && (!isInMemory.get(reg.number) && isInMemory.get(number)))) {
                             reg = availableReg;
                         }
                     }
                 }
 
+                if (Debug.isLogEnabled()) {
+                    Debug.log("Register Selected: %s", reg);
+                }
+
                 int regUsePos = (reg == null ? 0 : usePos[reg.number]);
                 if (regUsePos <= firstShouldHaveUsage) {
-                    if (Debug.isLogEnabled()) {
-                        Debug.log("able to spill current interval. firstUsage(register): %d, usePos: %d", firstUsage, regUsePos);
-                    }
-
-                    if (firstUsage <= interval.from() + 1) {
-                        if (registerPriority.equals(RegisterPriority.LiveAtLoopEnd)) {
-                            /*
-                             * Tool of last resort: we can not spill the current interval so we try
-                             * to spill an active interval that has a usage but do not require a
-                             * register.
-                             */
-                            Debug.log("retry with register priority must have register");
-                            continue;
+                    /* Check if there is another interval that is already in memory. */
+                    if (reg == null || interval.inMemoryAt(currentPosition) || !isInMemory.get(reg.number)) {
+                        if (Debug.isLogEnabled()) {
+                            Debug.log("able to spill current interval. firstUsage(register): %d, usePos: %d", firstUsage, regUsePos);
                         }
-                        String description = "cannot spill interval (" + interval + ") that is used in first instruction (possible reason: no register found) firstUsage=" + firstUsage +
-                                        ", interval.from()=" + interval.from() + "; already used candidates: " + Arrays.toString(availableRegs);
-                        /*
-                         * assign a reasonable register and do a bailout in product mode to avoid
-                         * errors
-                         */
-                        allocator.assignSpillSlot(interval);
-                        Debug.dump(allocator.getLIR(), description);
-                        allocator.printIntervals(description);
-                        throw new OutOfRegistersException("LinearScan: no register found", description);
+
+                        if (firstUsage <= interval.from() + 1) {
+                            if (registerPriority.equals(RegisterPriority.LiveAtLoopEnd)) {
+                                /*
+                                 * Tool of last resort: we can not spill the current interval so we
+                                 * try to spill an active interval that has a usage but do not
+                                 * require a register.
+                                 */
+                                Debug.log("retry with register priority must have register");
+                                continue;
+                            }
+                            String description = "cannot spill interval (" + interval + ") that is used in first instruction (possible reason: no register found) firstUsage=" + firstUsage +
+                                            ", interval.from()=" + interval.from() + "; already used candidates: " + Arrays.toString(availableRegs);
+                            /*
+                             * assign a reasonable register and do a bailout in product mode to
+                             * avoid errors
+                             */
+                            allocator.assignSpillSlot(interval);
+                            Debug.dump(allocator.getLIR(), description);
+                            allocator.printIntervals(description);
+                            throw new OutOfRegistersException("LinearScan: no register found", description);
+                        }
+
+                        splitAndSpillInterval(interval);
+                        return;
                     }
-
-                    splitAndSpillInterval(interval);
-                    return;
                 }
+                // common case: break out of the loop
                 break;
             }
 
@@ -926,9 +947,9 @@
         try (Indent indent2 = Debug.logAndIndent("state of registers:")) {
             for (Register reg : availableRegs) {
                 int i = reg.number;
-                try (Indent indent3 = Debug.logAndIndent("reg %d: usePos: %d, blockPos: %d, intervals: ", i, usePos[i], blockPos[i])) {
+                try (Indent indent3 = Debug.logAndIndent("reg %d: usePos: %d, blockPos: %d, inMemory: %b, intervals: ", i, usePos[i], blockPos[i], isInMemory.get(i))) {
                     for (int j = 0; j < spillIntervals[i].size(); j++) {
-                        Debug.log("%s ", spillIntervals[i].get(j));
+                        Debug.log("%s", spillIntervals[i].get(j));
                     }
                 }
             }