--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/alloc/LinearScan.java	Thu Dec 12 14:56:52 2013 -0800
+++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/alloc/LinearScan.java	Fri Dec 13 07:56:25 2013 +0100
@@ -1869,6 +1869,7 @@
             printLir("After register number assignment", true);
             EdgeMoveOptimizer.optimize(ir);
             ControlFlowOptimizer.optimize(ir);
+            RedundantMoveElimination.optimize(ir, frameMap, gen.getGraph().method());
             NullCheckOptimizer.optimize(ir, target.implicitNullCheckLimit);
             printLir("After control flow optimization", false);
         } catch (Throwable e) {

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/RedundantMoveElimination.java	Fri Dec 13 07:56:25 2013 +0100
@@ -0,0 +1,462 @@
+/*
+ * Copyright (c) 2013, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+package com.oracle.graal.lir;
+
+import static com.oracle.graal.api.code.ValueUtil.*;
+
+import java.util.*;
+
+import com.oracle.graal.api.code.*;
+import com.oracle.graal.api.meta.*;
+import com.oracle.graal.debug.*;
+import com.oracle.graal.lir.StandardOp.MoveOp;
+import com.oracle.graal.lir.LIRInstruction.*;
+import com.oracle.graal.nodes.cfg.*;
+
+/**
+ * Removes move instructions, where the destination value is already in place.
+ */
+public final class RedundantMoveElimination {
+
+    public static void optimize(LIR lir, FrameMap frameMap, ResolvedJavaMethod method) {
+        RedundantMoveElimination redundantMoveElimination = new RedundantMoveElimination();
+        redundantMoveElimination.doOptimize(lir, frameMap, method);
+    }
+
+    /**
+     * Holds the entry and exit states for each block for dataflow analysis. The state is an array
+     * with an element for each relevant location (register or stack slot). Each element holds the
+     * global number of the location's definition. A location definition is simply an output of an
+     * instruction. Note that because instructions can have multiple outputs it is not possible to
+     * use the instruction id for value numbering. In addition, the result of merging at block
+     * entries (= phi values) get unique value numbers.
+     * 
+     * The value numbers also contain information if it is an object kind value or not: if the
+     * number is negative it is an object kind value.
+     */
+    private static class BlockData {
+
+        BlockData(int stateSize) {
+            entryState = new int[stateSize];
+            exitState = new int[stateSize];
+        }
+
+        /*
+         * The state at block entry for global dataflow analysis. It contains a global value number
+         * for each location to optimize.
+         */
+        int[] entryState;
+
+        /*
+         * The state at block exit for global dataflow analysis. It contains a global value number
+         * for each location to optimize.
+         */
+        int[] exitState;
+
+        /*
+         * The starting number for global value numbering in this block.
+         */
+        int entryValueNum;
+    }
+
+    Map<Block, BlockData> blockData = new HashMap<>();
+
+    Register[] callerSaveRegs;
+
+    Map<StackSlot, Integer> stackIndices = new HashMap<>();
+
+    int numRegs;
+
+    /*
+     * Pseudo value for a not yet assigned location.
+     */
+    static final int INIT_VALUE = 0;
+
+    /**
+     * The main method doing the elimination of redundant moves.
+     */
+    private void doOptimize(LIR lir, FrameMap frameMap, ResolvedJavaMethod method) {
+
+        try (Indent indent = Debug.logAndIndent(false, "eliminate redundant moves in %s", method)) {
+
+            callerSaveRegs = frameMap.registerConfig.getCallerSaveRegisters();
+
+            initBlockData(lir);
+
+            solveDataFlow(lir);
+
+            eliminateMoves(lir);
+        }
+    }
+
+    private void initBlockData(LIR lir) {
+
+        List<Block> blocks = lir.linearScanOrder();
+        numRegs = 0;
+
+        /*
+         * Search for relevant locations which can be optimized. These are register or stack slots
+         * which occur as destinations of move instructions.
+         */
+        for (Block block : blocks) {
+            List<LIRInstruction> instructions = lir.lir(block);
+            for (LIRInstruction op : instructions) {
+                if (isEligibleMove(op)) {
+                    Value dest = ((MoveOp) op).getResult();
+                    if (isRegister(dest)) {
+                        int regNum = ((RegisterValue) dest).getRegister().number;
+                        if (regNum >= numRegs) {
+                            numRegs = regNum + 1;
+                        }
+                    } else if (isStackSlot(dest)) {
+                        StackSlot stackSlot = (StackSlot) dest;
+                        if (!stackIndices.containsKey(stackSlot)) {
+                            stackIndices.put(stackSlot, stackIndices.size());
+                        }
+                    }
+                }
+            }
+        }
+
+        /*
+         * Now we know the number of locations to optimize, so we can allocate the block states.
+         */
+        int numLocations = numRegs + stackIndices.size();
+        Debug.log("num locations = %d (regs = %d, stack = %d)", numLocations, numRegs, stackIndices.size());
+        for (Block block : blocks) {
+            BlockData data = new BlockData(numLocations);
+            blockData.put(block, data);
+        }
+    }
+
+    /**
+     * Calculates the entry and exit states for all basic blocks.
+     */
+    private void solveDataFlow(LIR lir) {
+
+        Indent indent = Debug.logAndIndent("solve data flow");
+
+        List<Block> blocks = lir.linearScanOrder();
+
+        /*
+         * Iterate until there are no more changes.
+         */
+        int currentValueNum = 1;
+        boolean firstRound = true;
+        boolean changed;
+        do {
+            changed = false;
+            Indent indent2 = indent.logAndIndent("new iteration");
+
+            for (Block block : blocks) {
+
+                BlockData data = blockData.get(block);
+                /*
+                 * Initialize the number for global value numbering for this block. It is essential
+                 * that the starting number for a block is consistent at all iterations and also in
+                 * eliminateMoves().
+                 */
+                if (firstRound) {
+                    data.entryValueNum = currentValueNum;
+                }
+                int valueNum = data.entryValueNum;
+                assert valueNum > 0;
+                boolean newState = false;
+
+                if (block == blocks.get(0) || block.isExceptionEntry()) {
+                    /*
+                     * The entry block has undefined values. And also exception handler blocks: the
+                     * LinearScan can insert moves at the end of an exception handler predecessor
+                     * block (after the invoke, which throws the exception), and in reality such
+                     * moves are not in the control flow in case of an exception. So we assume a
+                     * save default for exception handler blocks.
+                     */
+                    indent2.log("kill all values at entry of block %d", block.getId());
+                    clearValues(data.entryState, valueNum);
+                } else {
+                    /*
+                     * Merge the states of predecessor blocks
+                     */
+                    for (Block predecessor : block.getPredecessors()) {
+                        BlockData predData = blockData.get(predecessor);
+                        newState |= mergeState(data.entryState, predData.exitState, valueNum);
+                    }
+                }
+                // Advance by the value numbers which are "consumed" by clearValues and mergeState
+                valueNum += data.entryState.length;
+
+                if (newState || firstRound) {
+
+                    Indent indent3 = indent2.logAndIndent("update block %d", block.getId());
+
+                    /*
+                     * Derive the exit state from the entry state by iterating through all
+                     * instructions of the block.
+                     */
+                    int[] iterState = data.exitState;
+                    copyState(iterState, data.entryState);
+                    List<LIRInstruction> instructions = lir.lir(block);
+
+                    for (LIRInstruction op : instructions) {
+                        valueNum = updateState(iterState, op, valueNum);
+                    }
+                    changed = true;
+                    indent3.outdent();
+                }
+                if (firstRound) {
+                    currentValueNum = valueNum;
+                }
+            }
+            firstRound = false;
+            indent2.outdent();
+
+        } while (changed);
+
+        indent.outdent();
+    }
+
+    /**
+     * Deletes all move instructions where the target location already contains the source value.
+     */
+    private void eliminateMoves(LIR lir) {
+
+        Indent indent = Debug.logAndIndent("eliminate moves");
+
+        List<Block> blocks = lir.linearScanOrder();
+
+        for (Block block : blocks) {
+
+            Indent indent2 = indent.logAndIndent("eliminate moves in block %d", block.getId());
+
+            List<LIRInstruction> instructions = lir.lir(block);
+            BlockData data = blockData.get(block);
+            boolean hasDead = false;
+
+            // Reuse the entry state for iteration, we don't need it later.
+            int[] iterState = data.entryState;
+
+            // Add the values which are "consumed" by clearValues and mergeState in solveDataFlow
+            int valueNum = data.entryValueNum + data.entryState.length;
+
+            int numInsts = instructions.size();
+            for (int idx = 0; idx < numInsts; idx++) {
+                LIRInstruction op = instructions.get(idx);
+                if (isEligibleMove(op)) {
+                    MoveOp moveOp = (MoveOp) op;
+                    int sourceIdx = getStateIdx(moveOp.getInput());
+                    int destIdx = getStateIdx(moveOp.getResult());
+                    if (sourceIdx >= 0 && destIdx >= 0 && iterState[sourceIdx] == iterState[destIdx]) {
+                        assert iterState[sourceIdx] != INIT_VALUE;
+                        indent2.log("delete move %s", op);
+                        instructions.set(idx, null);
+                        hasDead = true;
+                    }
+                }
+                // It doesn't harm if updateState is also called for a deleted move
+                valueNum = updateState(iterState, op, valueNum);
+            }
+            if (hasDead) {
+                instructions.removeAll(Collections.singleton(null));
+            }
+            indent2.outdent();
+        }
+        indent.outdent();
+    }
+
+    /**
+     * Updates the state for one instruction.
+     */
+    private int updateState(final int[] state, LIRInstruction op, int initValueNum) {
+
+        try (final Indent indent = Debug.logAndIndent("update state for op %s, initial value num = %d", op, initValueNum)) {
+            if (isEligibleMove(op)) {
+                /*
+                 * Handle the special case of a move instruction
+                 */
+                MoveOp moveOp = (MoveOp) op;
+                int sourceIdx = getStateIdx(moveOp.getInput());
+                int destIdx = getStateIdx(moveOp.getResult());
+                if (sourceIdx >= 0 && destIdx >= 0) {
+                    state[destIdx] = state[sourceIdx];
+                    indent.log("move value %d from %d to %d", state[sourceIdx], sourceIdx, destIdx);
+                    return initValueNum;
+                }
+            }
+
+            int valueNum = initValueNum;
+
+            if (op.destroysCallerSavedRegisters()) {
+                indent.log("kill all caller save regs");
+
+                for (Register reg : callerSaveRegs) {
+                    if (reg.number < numRegs) {
+                        // Kind.Object is the save default
+                        state[reg.number] = encodeValueNum(valueNum++, true);
+                    }
+                }
+            }
+
+            /*
+             * Value procedure for the instruction's output and temp values
+             */
+            class OutputValueProc extends ValueProcedure {
+
+                int opValueNum;
+
+                OutputValueProc(int opValueNum) {
+                    this.opValueNum = opValueNum;
+                }
+
+                @Override
+                public Value doValue(Value operand, OperandMode mode, EnumSet<OperandFlag> flags) {
+                    int stateIdx = getStateIdx(operand);
+                    if (stateIdx >= 0) {
+                        /*
+                         * Assign a unique number to the output or temp location.
+                         */
+                        state[stateIdx] = encodeValueNum(opValueNum++, operand.getKind() == Kind.Object);
+                        indent.log("set def %d for register %s(%d): %d", opValueNum, operand, stateIdx, state[stateIdx]);
+                    }
+                    return operand;
+                }
+            }
+
+            OutputValueProc outputValueProc = new OutputValueProc(valueNum);
+            op.forEachOutput(outputValueProc);
+            op.forEachTemp(outputValueProc);
+            valueNum = outputValueProc.opValueNum;
+
+            if (op.hasState()) {
+                /*
+                 * All instructions with framestates (mostly method calls), may do garbage
+                 * collection. GC will rewrite all object references which are live at this point.
+                 * So we can't rely on their values.
+                 */
+                indent.log("kill all object values");
+                clearValuesOfKindObject(state, valueNum);
+                valueNum += state.length;
+            }
+
+            return valueNum;
+        }
+    }
+
+    /**
+     * The state merge function for dataflow joins.
+     */
+    private static boolean mergeState(int[] dest, int[] source, int defNum) {
+        assert dest.length == source.length;
+        boolean changed = false;
+        for (int idx = 0; idx < source.length; idx++) {
+            int phiNum = defNum + idx;
+            if (dest[idx] != source[idx] && source[idx] != INIT_VALUE && dest[idx] != encodeValueNum(phiNum, isObjectValue(dest[idx]))) {
+                if (dest[idx] != INIT_VALUE) {
+                    dest[idx] = encodeValueNum(phiNum, isObjectValue(dest[idx]) || isObjectValue(source[idx]));
+                } else {
+                    dest[idx] = source[idx];
+                }
+                changed = true;
+            }
+        }
+        return changed;
+    }
+
+    private static void copyState(int[] dest, int[] source) {
+        assert dest.length == source.length;
+        for (int idx = 0; idx < source.length; idx++) {
+            dest[idx] = source[idx];
+        }
+    }
+
+    private static void clearValues(int[] state, int defNum) {
+        for (int idx = 0; idx < state.length; idx++) {
+            int phiNum = defNum + idx;
+            // Let the killed values assume to be object references: it's the save default.
+            state[idx] = encodeValueNum(phiNum, true);
+        }
+    }
+
+    private static void clearValuesOfKindObject(int[] state, int defNum) {
+        for (int idx = 0; idx < state.length; idx++) {
+            int phiNum = defNum + idx;
+            if (isObjectValue(state[idx])) {
+                state[idx] = encodeValueNum(phiNum, true);
+            }
+        }
+    }
+
+    /**
+     * Returns the index to the state arrays in BlockData for a specific location.
+     */
+    private int getStateIdx(Value location) {
+        if (isRegister(location)) {
+            int regNum = ((RegisterValue) location).getRegister().number;
+            if (regNum < numRegs) {
+                return regNum;
+            }
+        }
+        if (isStackSlot(location)) {
+            StackSlot slot = (StackSlot) location;
+            Integer index = stackIndices.get(slot);
+            if (index != null) {
+                return index.intValue() + numRegs;
+            }
+        }
+        return -1;
+    }
+
+    /**
+     * Encodes a value number + the is-object information to a number to be stored in a state.
+     */
+    private static int encodeValueNum(int valueNum, boolean isObjectKind) {
+        assert valueNum > 0;
+        if (isObjectKind) {
+            return -valueNum;
+        }
+        return valueNum;
+    }
+
+    /**
+     * Returns true if an encoded value number (which is stored in a state) refers to an object
+     * reference.
+     */
+    private static boolean isObjectValue(int encodedValueNum) {
+        return encodedValueNum < 0;
+    }
+
+    /**
+     * Returns true for a move instruction which is a candidate for elimination.
+     */
+    private static boolean isEligibleMove(LIRInstruction op) {
+        if (op instanceof MoveOp) {
+            MoveOp moveOp = (MoveOp) op;
+            Value source = moveOp.getInput();
+            Value dest = moveOp.getResult();
+            /*
+             * Moves with mismatching kinds are not moves, but memory loads/stores!
+             */
+            return source.getKind() == dest.getKind() && source.getPlatformKind() == dest.getPlatformKind() && source.getKind() != Kind.Illegal;
+        }
+        return false;
+    }
+}