# HG changeset patch # User Christian Wimmer # Date 1324671706 28800 # Node ID a47535c91bf1bfc0989b31e71b9ed49ca07ee16a # Parent d6d589ed9b84266201ad04c0f36d595b2b64ed4f Change LIRInsertionBuffer to add instructions _before_ the specified index, instead of _after_. Cleanup the interface and document it. diff -r d6d589ed9b84 -r a47535c91bf1 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/alloc/LIRInsertionBuffer.java --- 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. + *
+ * 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()}, ... + *
+ * 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 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 before 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 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; diff -r d6d589ed9b84 -r a47535c91bf1 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/alloc/LinearScan.java --- 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(); } } diff -r d6d589ed9b84 -r a47535c91bf1 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/alloc/LinearScanWalker.java --- 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); } diff -r d6d589ed9b84 -r a47535c91bf1 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/alloc/MoveResolver.java --- 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());