--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/alloc/LIRInsertionBuffer.java	Fri Dec 23 12:10:28 2011 -0800
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/alloc/LIRInsertionBuffer.java	Fri Dec 23 12:21:46 2011 -0800
@@ -26,9 +26,17 @@
 
 import com.oracle.max.graal.compiler.lir.*;
 import com.oracle.max.graal.compiler.util.*;
-import com.sun.cri.ci.*;
 
 /**
+ * A buffer to enqueue updates to a list. This avoids frequent re-sizing of the list and copying of list elements
+ * when insertions are done at multiple positions of the list. Additionally, it ensures that the list is not modified
+ * while it is, e.g., iterated, and instead only modified once after the iteration is done.
+ * <br>
+ * The buffer uses internal data structures to store the enqueued updates. To avoid allocations, a buffer can be re-used.
+ * Call the methods in the following order:
+ * {@link #init()}, {@link #append()}, {@link #append()}, ..., {@link #finish()}, {@link #init()}, ...
+ * <br>
+ * Note: This class does not depend on LIRInstruction, so we could make it a generic utility class.
  */
 public final class LIRInsertionBuffer {
 
@@ -55,7 +63,9 @@
         ops = new ArrayList<>(8);
     }
 
-    // must be called before using the insertion buffer
+    /**
+     * Initialize this buffer. This method must be called before using {@link #append()}.
+     */
     public void init(List<LIRInstruction> newLir) {
         assert !initialized() : "already initialized";
         assert indexAndCount.size() == 0 && ops.size() == 0;
@@ -66,10 +76,29 @@
         return lir != null;
     }
 
-    public void move(int index, CiValue src, CiValue dst) {
-        append(index, StandardOpcode.MOVE.create(dst, src));
+    /**
+     * Enqueue a new instruction that will be appended to the instruction list when {@link #finish()} is called.
+     * The new instruction is added <b>before</b> the existing instruction with the given index. This method can only be called
+     * with increasing values of index, e.g., once an instruction was appended with index 4, subsequent instructions can
+     * only be appended with index 4 or higher.
+     */
+    public void append(int index, LIRInstruction op) {
+        int i = numberOfInsertionPoints() - 1;
+        if (i < 0 || indexAt(i) < index) {
+            appendNew(index, 1);
+        } else {
+            assert indexAt(i) == index : "can append LIROps in ascending order only";
+            assert countAt(i) > 0 : "check";
+            setCountAt(i, countAt(i) + 1);
+        }
+        ops.add(op);
+
+        assert verify();
     }
 
+    /**
+     * Append all enqueued instructions to the instruction list. After that, {@link init()} can be called again to re-use this buffer.
+     */
     public void finish() {
         if (ops.size() > 0) {
             int n = lir.size();
@@ -85,7 +114,7 @@
             while (ipIndex >= 0) {
                 int index = indexAt(ipIndex);
                 // make room after insertion point
-                while (index < fromIndex) {
+                while (fromIndex >= index) {
                     lir.set(toIndex--, lir.get(fromIndex--));
                 }
                 // insert ops from buffer
@@ -94,15 +123,10 @@
                 }
                 ipIndex--;
             }
+            indexAndCount.clear();
+            ops.clear();
         }
-
         lir = null;
-        indexAndCount.clear();
-        ops.clear();
-    }
-
-    public List<LIRInstruction> lirList() {
-        return lir;
     }
 
     private void appendNew(int index, int count) {
@@ -115,6 +139,7 @@
     }
 
     private int numberOfInsertionPoints() {
+        assert indexAndCount.size() % 2 == 0 : "must have a count for each index";
         return indexAndCount.size() >> 1;
     }
 
@@ -126,22 +151,6 @@
         return indexAndCount.get((i << 1) + 1);
     }
 
-    private void append(int index, LIRInstruction op) {
-        assert indexAndCount.size() % 2 == 0 : "must have a count for each index";
-
-        int i = numberOfInsertionPoints() - 1;
-        if (i < 0 || indexAt(i) < index) {
-            appendNew(index, 1);
-        } else {
-            assert indexAt(i) == index : "can append LIROps in ascending order only";
-            assert countAt(i) > 0 : "check";
-            setCountAt(i, countAt(i) + 1);
-        }
-        ops.add(op);
-
-        assert verify();
-    }
-
     private boolean verify() {
         int sum = 0;
         int prevIdx = -1;

--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/alloc/LinearScan.java	Fri Dec 23 12:10:28 2011 -0800
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/alloc/LinearScan.java	Fri Dec 23 12:21:46 2011 -0800
@@ -457,7 +457,7 @@
                         assert fromLocation.isRegister() : "from operand must be a register but is: " + fromLocation + " toLocation=" + toLocation + " spillState=" + interval.spillState();
                         assert toLocation.isStackSlot() : "to operand must be a stack slot";
 
-                        insertionBuffer.move(j, fromLocation, toLocation);
+                        insertionBuffer.append(j + 1, StandardOpcode.MOVE.create(toLocation, fromLocation));
 
                         if (GraalOptions.TraceLinearScanLevel >= 4) {
                             CiStackSlot slot = interval.spillSlot();
@@ -1436,9 +1436,9 @@
             if (instr instanceof LIRBranch) {
                 // insert moves before branch
                 assert instr.code == StandardOpcode.JUMP : "block does not end with an unconditional jump";
-                moveResolver.setInsertPosition(fromBlock.lir(), instructions.size() - 2);
+                moveResolver.setInsertPosition(fromBlock.lir(), instructions.size() - 1);
             } else {
-                moveResolver.setInsertPosition(fromBlock.lir(), instructions.size() - 1);
+                moveResolver.setInsertPosition(fromBlock.lir(), instructions.size());
             }
 
         } else {
@@ -1458,7 +1458,7 @@
                 }
             }
 
-            moveResolver.setInsertPosition(toBlock.lir(), 0);
+            moveResolver.setInsertPosition(toBlock.lir(), 1);
         }
     }
 
@@ -1497,7 +1497,7 @@
                         // directly resolve between pred and sux (without looking at the empty block between)
                         resolveCollectMappings(pred, sux, moveResolver);
                         if (moveResolver.hasMappings()) {
-                            moveResolver.setInsertPosition(block.lir(), 0);
+                            moveResolver.setInsertPosition(block.lir(), 1);
                             moveResolver.resolveAndAppendMoves();
                         }
                     }

--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/alloc/LinearScanWalker.java	Fri Dec 23 12:10:28 2011 -0800
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/alloc/LinearScanWalker.java	Fri Dec 23 12:21:46 2011 -0800
@@ -245,7 +245,7 @@
         assert list.get(index).id() == opId : "error in calculation";
 
         // insert new instruction before instruction at position index
-        moveResolver.moveInsertPosition(opBlock.lir(), index - 1);
+        moveResolver.moveInsertPosition(opBlock.lir(), index);
         moveResolver.addMapping(srcIt, dstIt);
     }
 

--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/alloc/MoveResolver.java	Fri Dec 23 12:10:28 2011 -0800
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/alloc/MoveResolver.java	Fri Dec 23 12:21:46 2011 -0800
@@ -195,12 +195,11 @@
         assert fromInterval.operand != toInterval.operand : "from and to interval equal: " + fromInterval;
         assert Util.archKindsEqual(fromInterval.kind(), toInterval.kind()) : "move between different types";
         assert insertList != null && insertIdx != -1 : "must setup insert position first";
-        assert insertionBuffer.lirList() == insertList : "wrong insertion buffer";
 
         CiValue fromOpr = fromInterval.operand;
         CiValue toOpr = toInterval.operand;
 
-        insertionBuffer.move(insertIdx, fromOpr, toOpr);
+        insertionBuffer.append(insertIdx, StandardOpcode.MOVE.create(toOpr, fromOpr));
 
         if (GraalOptions.TraceLinearScanLevel >= 4) {
             TTY.println("MoveResolver: inserted move from %d (%s) to %d (%s)", fromInterval.operandNumber, fromInterval.location(), toInterval.operandNumber, toInterval.location());
@@ -210,10 +209,9 @@
     private void insertMove(CiValue fromOpr, Interval toInterval) {
         assert Util.archKindsEqual(fromOpr.kind, toInterval.kind()) : "move between different types";
         assert insertList != null && insertIdx != -1 : "must setup insert position first";
-        assert insertionBuffer.lirList() == insertList : "wrong insertion buffer";
 
         CiValue toOpr = toInterval.operand;
-        insertionBuffer.move(insertIdx, fromOpr, toOpr);
+        insertionBuffer.append(insertIdx, StandardOpcode.MOVE.create(toOpr, fromOpr));
 
         if (GraalOptions.TraceLinearScanLevel >= 4) {
             TTY.print("MoveResolver: inserted move from constant %s to %d (%s)", fromOpr, toInterval.operandNumber, toInterval.location());