# HG changeset patch
# User Josef Eisl <josef.eisl@jku.at>
# Date 1401886392 -7200
# Node ID a07492ccaf525ce6cdd3c1ba128e6d2ba6d87758
# Parent  830fd9cd109914fb9cf08b9684214ba999be234d
LSRA spill optimization: calculate optimized spill position.

diff -r 830fd9cd1099 -r a07492ccaf52 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 12:19:24 2014 +0200
+++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/alloc/LinearScan.java	Wed Jun 04 14:53:12 2014 +0200
@@ -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.*;
@@ -1844,6 +1845,12 @@
                 throw Debug.handle(e);
             }
 
+            try (Scope s = Debug.scope("SpillPosition")) {
+                findSpillPosition();
+            } catch (Throwable e) {
+                throw Debug.handle(e);
+            }
+
             try (Scope s = Debug.scope("ResolveDataFlow")) {
                 resolveDataFlow();
             } catch (Throwable e) {
@@ -1876,6 +1883,68 @@
         }
     }
 
+    private DebugMetric betterSpillPos = Debug.metric("BetterSpillPosition");
+
+    private void findSpillPosition() {
+        for (Interval interval : intervals) {
+            if (interval != null && interval.isSplitParent() && interval.spillState() == SpillState.StoreAtDefinition) {
+                AbstractBlock<?> defBlock = blockForId(interval.spillDefinitionPos());
+                AbstractBlock<?> spillBlock = null;
+                try (Indent indent = Debug.logAndIndent("interval %s (%s)", interval, defBlock)) {
+                    for (Interval splitChild : interval.getSplitChildren()) {
+                        if (isStackSlot(splitChild.location())) {
+                            AbstractBlock<?> splitBlock = blockForId(splitChild.from());
+                            assert dominates(defBlock, splitBlock) : "Definition does not dominate the spill interval";
+                            Debug.log("Split interval %s", splitChild, splitBlock);
+                            if (spillBlock == null) {
+                                spillBlock = splitBlock;
+                            } else {
+                                spillBlock = nearestCommonDominator(spillBlock, splitBlock);
+                                assert spillBlock != null;
+                            }
+                        }
+                    }
+                    assert spillBlock != null;
+                    assert dominates(defBlock, spillBlock);
+                    if (!defBlock.equals(spillBlock)) {
+                        betterSpillPos.increment();
+                        int pos = getFirstLirInstructionId(spillBlock);
+                        Debug.log("Better spill position found (Block %s, %d)", spillBlock, pos);
+                    }
+                }
+            }
+        }
+    }
+
+    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)) {