# HG changeset patch
# User Josef Eisl <josef.eisl@jku.at>
# Date 1401893696 -7200
# Node ID ec54fc47ba5dcbed8b977f9e036ca57834ecf12f
# Parent  f686fae773838edd0f40ac6e8e2c53c75976de21
LSRA spill optimization: move spill out of loops.

diff -r f686fae77383 -r ec54fc47ba5d 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 Jun 04 16:05:14 2014 +0200
+++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/alloc/LinearScan.java	Wed Jun 04 16:54:56 2014 +0200
@@ -442,9 +442,8 @@
 
                 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.
+                    interval.setSpillState(SpillState.SpillInDominator);
                 } else {
                     // the interval is currently spilled only once, so for now there is no
                     // reason to store the interval at the definition
@@ -1904,20 +1903,42 @@
                             }
                         }
                     }
-                    if (spillBlock == null || defBlock.equals(spillBlock)) {
+                    if (spillBlock == null) {
                         // no spill interval
                         interval.setSpillState(SpillState.StoreAtDefinition);
                     } else {
-                        assert dominates(defBlock, spillBlock);
-                        betterSpillPos.increment();
-                        Debug.log("Better spill position found (Block %s)", spillBlock);
-                        interval.setSpillDefinitionPos(getFirstLirInstructionId(spillBlock));
+                        // move out of loops
+                        if (defBlock.getLoopDepth() < spillBlock.getLoopDepth()) {
+                            spillBlock = moveSpillOutOfLoop(defBlock, spillBlock);
+                        }
+
+                        if (!defBlock.equals(spillBlock)) {
+                            assert dominates(defBlock, spillBlock);
+                            betterSpillPos.increment();
+                            Debug.log("Better spill position found (Block %s)", spillBlock);
+                            interval.setSpillDefinitionPos(getFirstLirInstructionId(spillBlock));
+                        } else {
+                            // definition is the best choice
+                            interval.setSpillState(SpillState.StoreAtDefinition);
+                        }
                     }
                 }
             }
         }
     }
 
+    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;