# HG changeset patch
# User Josef Eisl <josef.eisl@jku.at>
# Date 1402411406 -7200
# Node ID 0abb7a42ef75323393d73249d707dd996cbd4bf9
# Parent  d2fc1c1536550729d677f6cfce5f0e4c2c06191a
LSRA spill optimization: insert the spill moves at the right position.

diff -r d2fc1c153655 -r 0abb7a42ef75 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	Tue Jun 10 13:29:41 2014 +0200
+++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/alloc/Interval.java	Tue Jun 10 16:43:26 2014 +0200
@@ -661,7 +661,8 @@
 
     // 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() {
diff -r d2fc1c153655 -r 0abb7a42ef75 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	Tue Jun 10 13:29:41 2014 +0200
+++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/alloc/LinearScan.java	Tue Jun 10 16:43:26 2014 +0200
@@ -496,11 +496,57 @@
         abstract boolean apply(Interval i);
     }
 
-    private static final IntervalPredicate mustStoreAtDefinition = new IntervalPredicate() {
+    private static Interval addToListSortedByDefinition(Interval first, Interval interval) {
+        assert first != null;
+        if (first == Interval.EndMarker) {
+            interval.next = Interval.EndMarker;
+            return interval;
+        }
+
+        int spillPos = interval.spillDefinitionPos();
+        if (first.spillDefinitionPos() > spillPos) {
+            interval.next = first;
+            return interval;
+        }
+        Interval current = first;
+        while (current.next != Interval.EndMarker && current.next.spillDefinitionPos() < spillPos) {
+            current = current.next;
+        }
+        interval.next = current.next;
+        current.next = interval;
+        return first;
+    }
+
+    private Interval.Pair createSortedByDefinitionLists(IntervalPredicate isList1, IntervalPredicate isList2) {
+        assert isSorted(sortedIntervals) : "interval list is not sorted";
+
+        Interval list1 = Interval.EndMarker;
+        Interval list2 = Interval.EndMarker;
+
+        Interval v;
+
+        int n = sortedIntervals.length;
+        for (int i = 0; i < n; i++) {
+            v = sortedIntervals[i];
+            if (v == null) {
+                continue;
+            }
+
+            if (isList1.apply(v)) {
+                list1 = addToListSortedByDefinition(list1, v);
+            } else if (isList2 == null || isList2.apply(v)) {
+                list2 = addToListSortedByDefinition(list2, v);
+            }
+        }
+
+        return new Interval.Pair(list1, list2);
+    }
+
+    private static final IntervalPredicate mustStoreAtDominatorORDefinition = new IntervalPredicate() {
 
         @Override
         public boolean apply(Interval i) {
-            return i.isSplitParent() && i.spillState() == SpillState.StoreAtDefinition;
+            return i.isSplitParent() && (i.spillState() == SpillState.StoreAtDefinition || i.spillState() == SpillState.SpillInDominator);
         }
     };
 
@@ -511,7 +557,7 @@
             // collect all intervals that must be stored after their definition.
             // the list is sorted by Interval.spillDefinitionPos
             Interval interval;
-            interval = createUnhandledLists(mustStoreAtDefinition, null).first;
+            interval = createSortedByDefinitionLists(mustStoreAtDominatorORDefinition, null).first;
             if (DetailedAsserts.getValue()) {
                 checkIntervals(interval);
             }
@@ -521,9 +567,8 @@
                 List<LIRInstruction> instructions = ir.getLIRforBlock(block);
                 int numInst = instructions.size();
 
-                // iterate all instructions of the block. skip the first
-                // because it is always a label
-                for (int j = 1; j < numInst; j++) {
+                // iterate all instructions of the block.
+                for (int j = 0; j < numInst; j++) {
                     LIRInstruction op = instructions.get(j);
                     int opId = op.id();
 
@@ -550,7 +595,8 @@
                         // insert move from register to stack just after
                         // the beginning of the interval
                         assert interval == Interval.EndMarker || interval.spillDefinitionPos() >= opId : "invalid order";
-                        assert interval == Interval.EndMarker || (interval.isSplitParent() && interval.spillState() == SpillState.StoreAtDefinition) : "invalid interval";
+                        assert interval == Interval.EndMarker ||
+                                        (interval.isSplitParent() && (interval.spillState() == SpillState.StoreAtDefinition || interval.spillState() == SpillState.SpillInDominator)) : "invalid interval";
 
                         while (interval != Interval.EndMarker && interval.spillDefinitionPos() == opId) {
                             if (!interval.canMaterialize()) {
@@ -590,13 +636,11 @@
         while (temp != Interval.EndMarker) {
             assert temp.spillDefinitionPos() > 0 : "invalid spill definition pos";
             if (prev != null) {
-                assert temp.from() >= prev.from() : "intervals not sorted";
                 assert temp.spillDefinitionPos() >= prev.spillDefinitionPos() : "when intervals are sorted by from :  then they must also be sorted by spillDefinitionPos";
             }
 
             assert temp.spillSlot() != null || temp.canMaterialize() : "interval has no spill slot assigned";
             assert temp.spillDefinitionPos() >= temp.from() : "invalid order";
-            assert temp.spillDefinitionPos() <= temp.from() + 2 : "only intervals defined once at their start-pos can be optimized";
 
             Debug.log("interval %d (from %d to %d) must be stored at %d", temp.operandNumber, temp.from(), temp.to(), temp.spillDefinitionPos());