# HG changeset patch
# User Doug Simon <doug.simon@oracle.com>
# Date 1386937931 -3600
# Node ID 755645fa92d60bd15e4acc14baf000c13684f9fb
# Parent  26472d911fcdfb280fcfc447b93414820ff2b232
the load of a constant is commoned to the nearest block dominating all usages (GRAAL-508)

diff -r 26472d911fcd -r 755645fa92d6 graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/gen/LIRGenerator.java
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/gen/LIRGenerator.java	Fri Dec 13 13:25:36 2013 +0100
+++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/gen/LIRGenerator.java	Fri Dec 13 13:32:11 2013 +0100
@@ -42,6 +42,7 @@
 import com.oracle.graal.lir.StandardOp.BlockEndOp;
 import com.oracle.graal.lir.StandardOp.JumpOp;
 import com.oracle.graal.lir.StandardOp.LabelOp;
+import com.oracle.graal.lir.StandardOp.NoOp;
 import com.oracle.graal.nodes.*;
 import com.oracle.graal.nodes.PhiNode.PhiType;
 import com.oracle.graal.nodes.calc.*;
@@ -82,11 +83,69 @@
     private final boolean printIRWithLIR;
 
     /**
-     * Maps constants the variables within the scope of a single block to avoid loading a constant
+     * Maps constants to variables within the scope of a single block to avoid loading a constant
      * more than once per block.
      */
     private Map<Constant, Variable> constantsLoadedInCurrentBlock;
 
+    /**
+     * Handle for an operation that loads a constant into a variable. The operation starts in the
+     * first block where the constant is used but will eventually be
+     * {@linkplain LIRGenerator#insertConstantLoads() moved} to a block dominating all usages of the
+     * constant.
+     */
+    public static class LoadConstant implements Comparable<LoadConstant> {
+        /**
+         * The index of {@link #op} within {@link #block}'s instruction list or -1 if {@code op} is
+         * to be moved to a dominator block.
+         */
+        int index;
+
+        /**
+         * The operation that loads the constant.
+         */
+        private final LIRInstruction op;
+
+        /**
+         * The block that does or will contain {@link #op}. This is initially the block where the
+         * first usage of the constant is seen during LIR generation.
+         */
+        private Block block;
+
+        /**
+         * The variable into which the constant is loaded.
+         */
+        private final Variable variable;
+
+        public LoadConstant(Variable variable, Block block, int index, LIRInstruction op) {
+            this.variable = variable;
+            this.block = block;
+            this.index = index;
+            this.op = op;
+        }
+
+        /**
+         * Sorts {@link LoadConstant} objects according to their enclosing blocks. This is used to
+         * group loads per block in {@link LIRGenerator#insertConstantLoads()}.
+         */
+        public int compareTo(LoadConstant o) {
+            if (block.getId() < o.block.getId()) {
+                return -1;
+            }
+            if (block.getId() > o.block.getId()) {
+                return 1;
+            }
+            return 0;
+        }
+
+        @Override
+        public String toString() {
+            return block + "#" + op;
+        }
+    }
+
+    private Map<Constant, LoadConstant> constantLoads;
+
     private ValueNode currentInstruction;
     private ValueNode lastInstructionPrinted; // Debugging only
 
@@ -181,6 +240,12 @@
         return operand;
     }
 
+    /**
+     * Controls whether commoning is performed on {@linkplain #canInlineConstant(Constant)
+     * non-inlinable} constants.
+     */
+    private static final boolean CommonConstantLoads = Boolean.parseBoolean(System.getProperty("graal.commonConstantLoads", "true"));
+
     private Value getConstantOperand(ValueNode node) {
         if (!ConstantNodeRecordsUsages) {
             Constant value = node.asConstant();
@@ -189,15 +254,42 @@
                     return !node.isExternal() ? setResult(node, value) : value;
                 } else {
                     Variable loadedValue;
-                    if (constantsLoadedInCurrentBlock == null) {
-                        constantsLoadedInCurrentBlock = new HashMap<>();
-                        loadedValue = null;
+                    if (CommonConstantLoads) {
+                        if (constantLoads == null) {
+                            constantLoads = new HashMap<>();
+                        }
+                        LoadConstant load = constantLoads.get(value);
+                        if (load == null) {
+                            int index = lir.lir(currentBlock).size();
+                            // loadedValue = newVariable(value.getPlatformKind());
+                            loadedValue = emitMove(value);
+                            LIRInstruction op = lir.lir(currentBlock).get(index);
+                            constantLoads.put(value, new LoadConstant(loadedValue, currentBlock, index, op));
+                        } else {
+                            Block dominator = ControlFlowGraph.commonDominator(load.block, currentBlock);
+                            loadedValue = load.variable;
+                            if (dominator != load.block) {
+                                if (load.index >= 0) {
+                                    List<LIRInstruction> instructions = lir.lir(load.block);
+                                    instructions.set(load.index, new NoOp(null, -1));
+                                    load.index = -1;
+                                }
+                            } else {
+                                assert load.block != currentBlock || load.index < lir.lir(currentBlock).size();
+                            }
+                            load.block = dominator;
+                        }
                     } else {
-                        loadedValue = constantsLoadedInCurrentBlock.get(value);
-                    }
-                    if (loadedValue == null) {
-                        loadedValue = emitMove(value);
-                        constantsLoadedInCurrentBlock.put(value, loadedValue);
+                        if (constantsLoadedInCurrentBlock == null) {
+                            constantsLoadedInCurrentBlock = new HashMap<>();
+                            loadedValue = null;
+                        } else {
+                            loadedValue = constantsLoadedInCurrentBlock.get(value);
+                        }
+                        if (loadedValue == null) {
+                            loadedValue = emitMove(value);
+                            constantsLoadedInCurrentBlock.put(value, loadedValue);
+                        }
                     }
                     return loadedValue;
                 }
@@ -795,10 +887,74 @@
 
     @Override
     public void beforeRegisterAllocation() {
+        insertConstantLoads();
     }
 
     /**
-     * Gets an garbage vale for a given kind.
+     * Moves deferred {@linkplain LoadConstant loads} of constants into blocks dominating all usages
+     * of the constant. Any operations inserted into a block are guaranteed to be immediately prior
+     * to the first control flow instruction near the end of the block.
+     */
+    private void insertConstantLoads() {
+        if (constantLoads != null) {
+            // Remove loads where all usages are in the same block.
+            for (Iterator<Map.Entry<Constant, LoadConstant>> iter = constantLoads.entrySet().iterator(); iter.hasNext();) {
+                LoadConstant lc = iter.next().getValue();
+                if (lc.index != -1) {
+                    assert lir.lir(lc.block).get(lc.index) == lc.op;
+                    iter.remove();
+                }
+            }
+            if (constantLoads.isEmpty()) {
+                return;
+            }
+
+            // Sorting groups the loads per block.
+            LoadConstant[] groupedByBlock = constantLoads.values().toArray(new LoadConstant[constantLoads.size()]);
+            Arrays.sort(groupedByBlock);
+
+            int groupBegin = 0;
+            while (true) {
+                int groupEnd = groupBegin + 1;
+                Block block = groupedByBlock[groupBegin].block;
+                while (groupEnd < groupedByBlock.length && groupedByBlock[groupEnd].block == block) {
+                    groupEnd++;
+                }
+                int groupSize = groupEnd - groupBegin;
+
+                List<LIRInstruction> ops = lir.lir(block);
+                int lastIndex = ops.size() - 1;
+                assert ops.get(lastIndex) instanceof BlockEndOp;
+                int insertionIndex = lastIndex;
+                for (int i = Math.max(0, lastIndex - MAX_EXCEPTION_EDGE_OP_DISTANCE_FROM_END); i < lastIndex; i++) {
+                    if (getExceptionEdge(ops.get(i)) != null) {
+                        insertionIndex = i;
+                        break;
+                    }
+                }
+
+                if (groupSize == 1) {
+                    ops.add(insertionIndex, groupedByBlock[groupBegin].op);
+                } else {
+                    assert groupSize > 1;
+                    List<LIRInstruction> moves = new ArrayList<>(groupSize);
+                    for (int i = groupBegin; i < groupEnd; i++) {
+                        moves.add(groupedByBlock[i].op);
+                    }
+                    ops.addAll(insertionIndex, moves);
+                }
+
+                if (groupEnd == groupedByBlock.length) {
+                    break;
+                }
+                groupBegin = groupEnd;
+            }
+            constantLoads = null;
+        }
+    }
+
+    /**
+     * Gets a garbage value for a given kind.
      */
     protected Constant zapValueForKind(PlatformKind kind) {
         long dead = 0xDEADDEADDEADDEADL;
diff -r 26472d911fcd -r 755645fa92d6 graal/com.oracle.graal.lir/src/com/oracle/graal/lir/LIR.java
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/LIR.java	Fri Dec 13 13:25:36 2013 +0100
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/LIR.java	Fri Dec 13 13:32:11 2013 +0100
@@ -27,6 +27,7 @@
 import com.oracle.graal.api.meta.*;
 import com.oracle.graal.debug.*;
 import com.oracle.graal.graph.*;
+import com.oracle.graal.lir.LIRInstruction.StateProcedure;
 import com.oracle.graal.lir.StandardOp.BlockEndOp;
 import com.oracle.graal.lir.asm.*;
 import com.oracle.graal.nodes.*;
@@ -140,8 +141,6 @@
     public void emitCode(CompilationResultBuilder crb) {
         crb.frameContext.enter(crb);
 
-        // notifyBlocksOfSuccessors();
-
         int index = 0;
         for (Block b : codeEmittingOrder) {
             crb.setCurrentBlockIndex(index++);
@@ -189,15 +188,55 @@
         return hasArgInCallerFrame;
     }
 
+    /**
+     * Gets the exception edge (if any) originating at a given operation.
+     */
+    public static LabelRef getExceptionEdge(LIRInstruction op) {
+        final LabelRef[] exceptionEdge = {null};
+        op.forEachState(new StateProcedure() {
+            @Override
+            protected void doState(LIRFrameState state) {
+                if (state.exceptionEdge != null) {
+                    assert exceptionEdge[0] == null;
+                    exceptionEdge[0] = state.exceptionEdge;
+                }
+            }
+        });
+        return exceptionEdge[0];
+    }
+
+    /**
+     * The maximum distance an operation with an {@linkplain #getExceptionEdge(LIRInstruction)
+     * exception edge} can be from the last instruction of a LIR block. The value of 2 is based on a
+     * non-void call operation that has an exception edge. Such a call op will have a move op after
+     * it to put the return value into the result variable.
+     * <p>
+     * The rationale for such a constant is to limit the search for an insertion point when adding
+     * move operations at the end of a block. Such moves must be inserted before all control flow
+     * instructions.
+     */
+    public static final int MAX_EXCEPTION_EDGE_OP_DISTANCE_FROM_END = 2;
+
     public static boolean verifyBlock(LIR lir, Block block) {
         List<LIRInstruction> ops = lir.lir(block);
         if (ops.size() == 0) {
-            return true;
+            return false;
         }
-        for (LIRInstruction op : ops.subList(0, ops.size() - 1)) {
+        LIRInstruction opWithExceptionEdge = null;
+        int index = 0;
+        int lastIndex = ops.size() - 1;
+        for (LIRInstruction op : ops.subList(0, lastIndex)) {
             assert !(op instanceof BlockEndOp) : op.getClass();
+            LabelRef exceptionEdge = getExceptionEdge(op);
+            if (exceptionEdge != null) {
+                assert opWithExceptionEdge == null : "multiple ops with an exception edge not allowed";
+                opWithExceptionEdge = op;
+                int distanceFromEnd = lastIndex - index;
+                assert distanceFromEnd <= MAX_EXCEPTION_EDGE_OP_DISTANCE_FROM_END;
+            }
+            index++;
         }
-        LIRInstruction end = ops.get(ops.size() - 1);
+        LIRInstruction end = ops.get(lastIndex);
         assert end instanceof BlockEndOp : end.getClass();
         return true;
     }
@@ -210,7 +249,9 @@
             for (Block pred : block.getPredecessors()) {
                 assert blocks.contains(pred) : "missing predecessor from: " + block + "to: " + pred;
             }
-            verifyBlock(lir, block);
+            if (!verifyBlock(lir, block)) {
+                return false;
+            }
         }
         return true;
     }