# HG changeset patch
# User Josef Eisl <josef.eisl@jku.at>
# Date 1401979104 -7200
# Node ID a54a64af1e82c62353db1cb15992f7e802bd948a
# Parent  a7d11e1c738792a7b1a3c9f77bdc9bd15d40de19
LSRA spill optimization: take all blocks (with usepos) of a spill interval into account.

diff -r a7d11e1c7387 -r a54a64af1e82 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	Thu Jun 05 13:25:51 2014 +0200
+++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/alloc/LinearScan.java	Thu Jun 05 16:38:24 2014 +0200
@@ -1915,14 +1915,15 @@
                 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;
+                            for (AbstractBlock<?> splitBlock : blocksForSplitChild(splitChild)) {
+                                assert dominates(defBlock, splitBlock) : String.format("Definition does not dominate the spill block %s !dom %s (interval %s)", defBlock, splitBlock, interval);
+                                Debug.log("Split interval %s, block %s", splitChild, splitBlock);
+                                if (spillBlock == null) {
+                                    spillBlock = splitBlock;
+                                } else {
+                                    spillBlock = nearestCommonDominator(spillBlock, splitBlock);
+                                    assert spillBlock != null;
+                                }
                             }
                         }
                     }
@@ -1958,6 +1959,49 @@
         }
     }
 
+    /**
+     * Iterate over all {@link AbstractBlock blocks} of an interval with an use position.
+     */
+    private class UseBlockIterator implements Iterator<AbstractBlock<?>> {
+
+        int nextOpId;
+        Interval interval;
+
+        public UseBlockIterator(Interval interval) {
+            nextOpId = interval.nextUsage(RegisterPriority.None, 0);
+            this.interval = interval;
+        }
+
+        public AbstractBlock<?> next() {
+            AbstractBlock<?> block = blockForId(nextOpId);
+
+            int nextBlockIndex = block.getLinearScanNumber() + 1;
+            if (nextBlockIndex < sortedBlocks.size()) {
+                int from = getFirstLirInstructionId(sortedBlocks.get(nextBlockIndex));
+                assert from > nextOpId : "cannot go backwards";
+                assert from > maxOpId() || isBlockBegin(from) : "nextOpId is not a block begin";
+                assert from > maxOpId() || blockForId(from).getLinearScanNumber() == block.getLinearScanNumber() + 1 : "nextOpId is not the beginning of the next block";
+                nextOpId = interval.nextUsage(RegisterPriority.None, from);
+            } else {
+                // already at last the last block
+                nextOpId = Integer.MAX_VALUE;
+            }
+            return block;
+        }
+
+        public boolean hasNext() {
+            return nextOpId < interval.to();
+        }
+    }
+
+    private Iterable<AbstractBlock<?>> blocksForSplitChild(Interval interval) {
+        return new Iterable<AbstractBlock<?>>() {
+            public Iterator<AbstractBlock<?>> iterator() {
+                return new UseBlockIterator(interval);
+            }
+        };
+    }
+
     private static AbstractBlock<?> moveSpillOutOfLoop(AbstractBlock<?> defBlock, AbstractBlock<?> spillBlock) {
         int defLoopDepth = defBlock.getLoopDepth();
         for (AbstractBlock<?> block = spillBlock.getDominator(); !defBlock.equals(block); block = block.getDominator()) {