# HG changeset patch
# User Josef Eisl <josef.eisl@jku.at>
# Date 1445005922 -7200
# Node ID 16c3ddbe2ebc9fbe6d8d25a9e27902db3be6fa49
# Parent  1d8238228f815e658582eef9d8551bceb74ae845
TraceRA: eliminate spill moves.

diff -r 1d8238228f81 -r 16c3ddbe2ebc graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/alloc/TraceBuilder.java
--- a/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/alloc/TraceBuilder.java	Fri Oct 16 16:23:17 2015 +0200
+++ b/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/alloc/TraceBuilder.java	Fri Oct 16 16:32:02 2015 +0200
@@ -50,6 +50,12 @@
         public List<List<T>> getTraces() {
             return traces;
         }
+
+        public boolean incomingEdges(int traceNr) {
+            /* TODO (je): not efficient. find better solution. */
+            return getTraces().get(traceNr).stream().flatMap(b -> b.getPredecessors().stream()).anyMatch(s -> getTraceForBlock(s) != traceNr);
+        }
+
     }
 
     /**
@@ -71,6 +77,8 @@
     private TraceBuilder(List<T> blocks) {
         processed = new BitSet(blocks.size());
         worklist = new PriorityQueue<T>(TraceBuilder::compare);
+        assert (worklist != null);
+
         blocked = new int[blocks.size()];
         blockToTrace = new int[blocks.size()];
         for (T block : blocks) {
diff -r 1d8238228f81 -r 16c3ddbe2ebc graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScan.java
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScan.java	Fri Oct 16 16:23:17 2015 +0200
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScan.java	Fri Oct 16 16:32:02 2015 +0200
@@ -75,8 +75,7 @@
 
     private static final TraceLinearScanRegisterAllocationPhase TRACE_LINEAR_SCAN_REGISTER_ALLOCATION_PHASE = new TraceLinearScanRegisterAllocationPhase();
     private static final TraceLinearScanAssignLocationsPhase TRACE_LINEAR_SCAN_ASSIGN_LOCATIONS_PHASE = new TraceLinearScanAssignLocationsPhase();
-    // TODO (je) use!
-    @SuppressWarnings("unused") private static final TraceLinearScanEliminateSpillMovePhase TRACE_LINEAR_SCAN_ELIMINATE_SPILL_MOVE_PHASE = new TraceLinearScanEliminateSpillMovePhase();
+    private static final TraceLinearScanEliminateSpillMovePhase TRACE_LINEAR_SCAN_ELIMINATE_SPILL_MOVE_PHASE = new TraceLinearScanEliminateSpillMovePhase();
     private static final TraceLinearScanResolveDataFlowPhase TRACE_LINEAR_SCAN_RESOLVE_DATA_FLOW_PHASE = new TraceLinearScanResolveDataFlowPhase();
     private static final TraceLinearScanLifetimeAnalysisPhase TRACE_LINEAR_SCAN_LIFETIME_ANALYSIS_PHASE = new TraceLinearScanLifetimeAnalysisPhase();
 
@@ -736,6 +735,10 @@
                 TRACE_LINEAR_SCAN_RESOLVE_DATA_FLOW_PHASE.apply(target, lirGenRes, codeEmittingOrder, linearScanOrder, context, false);
                 Debug.dump(TraceRegisterAllocationPhase.TRACE_DUMP_LEVEL, sortedBlocks(), "%s", TRACE_LINEAR_SCAN_RESOLVE_DATA_FLOW_PHASE.getName());
 
+                // eliminate spill moves
+                TRACE_LINEAR_SCAN_ELIMINATE_SPILL_MOVE_PHASE.apply(target, lirGenRes, codeEmittingOrder, linearScanOrder, context, false);
+                Debug.dump(TraceRegisterAllocationPhase.TRACE_DUMP_LEVEL, sortedBlocks(), "%s", TRACE_LINEAR_SCAN_ELIMINATE_SPILL_MOVE_PHASE.getName());
+
                 TRACE_LINEAR_SCAN_ASSIGN_LOCATIONS_PHASE.apply(target, lirGenRes, codeEmittingOrder, linearScanOrder, context, false);
 
                 if (DetailedAsserts.getValue()) {
diff -r 1d8238228f81 -r 16c3ddbe2ebc graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanEliminateSpillMovePhase.java
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanEliminateSpillMovePhase.java	Fri Oct 16 16:23:17 2015 +0200
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanEliminateSpillMovePhase.java	Fri Oct 16 16:32:02 2015 +0200
@@ -24,6 +24,7 @@
 
 import static com.oracle.graal.compiler.common.GraalOptions.DetailedAsserts;
 import static com.oracle.graal.lir.LIRValueUtil.isStackSlotValue;
+import static com.oracle.graal.lir.LIRValueUtil.isVariable;
 import static jdk.vm.ci.code.ValueUtil.isRegister;
 
 import java.util.List;
@@ -59,7 +60,10 @@
     @Override
     protected <B extends AbstractBlockBase<B>> void run(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder, MoveFactory spillMoveFactory,
                     RegisterAllocationConfig registerAllocationConfig, TraceBuilderResult<?> traceBuilderResult, TraceLinearScan allocator) {
-        eliminateSpillMoves(allocator);
+        int traceNr = traceBuilderResult.getTraceForBlock(allocator.sortedBlocks().get(0));
+        if (!traceBuilderResult.incomingEdges(traceNr)) {
+            eliminateSpillMoves(allocator);
+        }
     }
 
     // called once before assignment of register numbers
@@ -94,7 +98,7 @@
                              * be correct. Only moves that have been inserted by LinearScan can be
                              * removed.
                              */
-                            if (canEliminateSpillMove(block, move)) {
+                            if (canEliminateSpillMove(allocator, block, move)) {
                                 /*
                                  * Move target is a stack slot that is always correct, so eliminate
                                  * instruction.
@@ -164,14 +168,27 @@
     }
 
     /**
+     * @param allocator
      * @param block The block {@code move} is located in.
      * @param move Spill move.
      */
-    private static boolean canEliminateSpillMove(AbstractBlockBase<?> block, MoveOp move) {
-        // TODO (je) do not eliminate spill moves yet!
+    private static boolean canEliminateSpillMove(TraceLinearScan allocator, AbstractBlockBase<?> block, MoveOp move) {
+        assert isVariable(move.getResult()) : "LinearScan inserts only moves to variables: " + move;
+
+        TraceInterval curInterval = allocator.intervalFor(move.getResult());
+
+        if (!isRegister(curInterval.location()) && curInterval.alwaysInMemory() && isPhiResolutionMove(allocator, move)) {
+            assert isStackSlotValue(curInterval.location()) : "Not a stack slot: " + curInterval.location();
+            return true;
+        }
         return false;
     }
 
+    private static boolean isPhiResolutionMove(TraceLinearScan allocator, MoveOp move) {
+        TraceInterval curInterval = allocator.intervalFor(move.getResult());
+        return !curInterval.isSplitParent();
+    }
+
     private static void checkIntervals(TraceInterval interval) {
         TraceInterval prev = null;
         TraceInterval temp = interval;