# HG changeset patch
# User Thomas Wuerthinger <thomas@wuerthinger.net>
# Date 1305819406 -7200
# Node ID 2ef23785ca93e3dae0797e559535ff287492e305
# Parent  beea26b73b3fd36abc2f2808f9e90f85aa48710c# Parent  027adfafd47e2551e1a9c76bceb8f7aefd6b5f2a
Merge.

diff -r beea26b73b3f -r 2ef23785ca93 graal/GraalCompiler/src/com/sun/c1x/graph/BlockMap.java
--- a/graal/GraalCompiler/src/com/sun/c1x/graph/BlockMap.java	Thu May 19 17:31:01 2011 +0200
+++ b/graal/GraalCompiler/src/com/sun/c1x/graph/BlockMap.java	Thu May 19 17:36:46 2011 +0200
@@ -27,6 +27,7 @@
 import java.util.*;
 
 import com.sun.c1x.debug.*;
+import com.sun.c1x.ir.*;
 import com.sun.cri.bytecode.*;
 import com.sun.cri.ci.*;
 import com.sun.cri.ri.*;
@@ -112,11 +113,14 @@
  * mark all local variables that are stored in the blocks in the list.
  */
 public final class BlockMap {
-    public class Block {
+    public static class Block {
         public int startBci;
         public int endBci;
         public boolean isExceptionEntry;
         public boolean isLoopHeader;
+        public int blockID;
+
+        public Instruction firstInstruction;
 
         private Block[] successors;
         private boolean visited;
@@ -165,6 +169,18 @@
         iterateOverBytecodes();
         addExceptionEdges();
         computeBlockOrder();
+
+        initializeBlockIds();
+
+        // Discard big arrays so that they can be GCed
+        blockMap = null;
+        canTrap = null;
+    }
+
+    private void initializeBlockIds() {
+        for (int i = 0; i < blocks.size(); i++) {
+            blocks.get(i).blockID = i;
+        }
     }
 
     private void makeExceptionEntries() {
diff -r beea26b73b3f -r 2ef23785ca93 graal/GraalCompiler/src/com/sun/c1x/graph/GraphBuilder.java
--- a/graal/GraalCompiler/src/com/sun/c1x/graph/GraphBuilder.java	Thu May 19 17:31:01 2011 +0200
+++ b/graal/GraalCompiler/src/com/sun/c1x/graph/GraphBuilder.java	Thu May 19 17:36:46 2011 +0200
@@ -31,6 +31,7 @@
 import com.oracle.graal.graph.*;
 import com.sun.c1x.*;
 import com.sun.c1x.debug.*;
+import com.sun.c1x.graph.BlockMap.Block;
 import com.sun.c1x.ir.*;
 import com.sun.c1x.util.*;
 import com.sun.c1x.value.*;
@@ -83,16 +84,17 @@
 
     private final BytecodeStream stream;           // the bytecode stream
     // bci-to-block mapping
-    private BlockBegin[] blockList;
+    private Block[] blockList;
 
     // the constant pool
     private final RiConstantPool constantPool;
 
-    // the worklist of blocks, managed like a sorted list
-    private BlockBegin[] workList;
-
-    // the current position in the worklist
-    private int workListIndex;
+    // the worklist of blocks, sorted by depth first number
+    private final PriorityQueue<Block> workList = new PriorityQueue<Block>(10, new Comparator<Block>() {
+        public int compare(Block o1, Block o2) {
+            return o1.blockID - o2.blockID;
+        }
+    });
 
     /**
      * Mask of {@link Flag} values.
@@ -102,9 +104,12 @@
     // Exception handler list
     private List<ExceptionHandler> exceptionHandlers;
 
-    private BlockBegin curBlock;                   // the current block
-    private FrameStateBuilder frameState;          // the current execution state
+    private Block curBlock;                   // the current block
+    private final FrameStateBuilder frameState;          // the current execution state
     private Instruction lastInstr;                 // the last instruction added
+    private Instruction placeholder;
+
+
     private final LogStream log;
 
     private Value rootMethodSynchronizedObject;
@@ -113,6 +118,8 @@
 
     private BlockBegin unwindBlock;
 
+    private final Set<Instruction> loopHeaders = new HashSet<Instruction>();
+
     /**
      * Creates a new, initialized, {@code GraphBuilder} instance for a given compilation.
      *
@@ -150,28 +157,39 @@
         // 2. compute the block map, setup exception handlers and get the entrypoint(s)
         BlockMap blockMap = compilation.getBlockMap(rootMethod);
 
-        blockList = new BlockBegin[rootMethod.code().length];
+        blockList = new Block[rootMethod.code().length];
         for (int i = 0; i < blockMap.blocks.size(); i++) {
-            BlockMap.Block block = blockMap.blocks.get(i);
-            BlockBegin blockBegin = new BlockBegin(block.startBci, ir.nextBlockNumber(), graph);
-            if (block.isLoopHeader) {
-                blockBegin.setParserLoopHeader(true);
-            }
-            blockBegin.setDepthFirstNumber(blockBegin.blockID);
-            blockList[block.startBci] = blockBegin;
+            Block block = blockMap.blocks.get(i);
+
+//            if (block.isLoopHeader) {
+                BlockBegin blockBegin = new BlockBegin(block.startBci, ir.nextBlockNumber(), graph);
+                blockBegin.setDepthFirstNumber(blockBegin.blockID);
+
+                block.firstInstruction = blockBegin;
+                blockList[block.startBci] = block;
+
+                if (block.isLoopHeader) {
+                    loopHeaders.add(blockBegin);
+                }
+//            } else {
+//                blockList[block.startBci] = new Placeholder(graph);
+//            }
         }
 
 
         // 1. create the start block
-        BlockBegin startBlock = new BlockBegin(0, ir.nextBlockNumber(), graph);
-        graph.root().setStart(startBlock);
+        Block startBlock = nextBlock(Instruction.SYNCHRONIZATION_ENTRY_BCI);
+        BlockBegin startBlockBegin = new BlockBegin(0, startBlock.blockID, graph);
+        startBlock.firstInstruction = startBlockBegin;
+
+        graph.root().setStart(startBlockBegin);
         curBlock = startBlock;
 
         RiExceptionHandler[] handlers = rootMethod.exceptionHandlers();
         if (handlers != null && handlers.length > 0) {
             exceptionHandlers = new ArrayList<ExceptionHandler>(handlers.length);
             for (RiExceptionHandler ch : handlers) {
-                BlockBegin entry = blockAtOrNull(ch.handlerBCI());
+                Block entry = blockList[ch.handlerBCI()];
                 // entry == null means that the exception handler is unreachable according to the BlockMap conservative analysis
                 if (entry != null) {
                     ExceptionHandler h = new ExceptionHandler(ch);
@@ -182,74 +200,96 @@
             flags |= Flag.HasHandler.mask;
         }
 
-        startBlock.mergeOrClone(frameState, rootMethod);
-        BlockBegin syncHandler = null;
+        assert !loopHeaders.contains(startBlock);
+        startBlockBegin.mergeOrClone(frameState, rootMethod, false);
 
         // 3. setup internal state for appending instructions
         curBlock = startBlock;
-        lastInstr = startBlock;
+        lastInstr = startBlockBegin;
         lastInstr.appendNext(null);
 
-        BlockBegin entryBlock = blockList[0];
+        Instruction entryBlock = blockAt(0);
+        BlockBegin syncHandler = null;
+        Block syncBlock = null;
         if (isSynchronized(rootMethod.accessFlags())) {
             // 4A.1 add a monitor enter to the start block
             rootMethodSynchronizedObject = synchronizedObject(frameState, compilation.method);
             genMonitorEnter(rootMethodSynchronizedObject, Instruction.SYNCHRONIZATION_ENTRY_BCI);
             // 4A.2 finish the start block
-            finishStartBlock(startBlock, entryBlock);
+            finishStartBlock(startBlockBegin, entryBlock);
 
             // 4A.3 setup an exception handler to unlock the root method synchronized object
-            syncHandler = new BlockBegin(Instruction.SYNCHRONIZATION_ENTRY_BCI, ir.nextBlockNumber(), graph);
-            markOnWorkList(syncHandler);
+            syncBlock = nextBlock(Instruction.SYNCHRONIZATION_ENTRY_BCI);
+            syncHandler = new BlockBegin(Instruction.SYNCHRONIZATION_ENTRY_BCI, syncBlock.blockID, graph);
+            syncBlock.firstInstruction = syncHandler;
+            markOnWorkList(syncBlock);
 
             ExceptionHandler h = new ExceptionHandler(new CiExceptionHandler(0, rootMethod.code().length, -1, 0, null));
-            h.setEntryBlock(syncHandler);
+            h.setEntryBlock(syncBlock);
             addExceptionHandler(h);
         } else {
             // 4B.1 simply finish the start block
-            finishStartBlock(startBlock, entryBlock);
+            finishStartBlock(startBlockBegin, entryBlock);
         }
 
         // 5. SKIPPED: look for intrinsics
 
         // 6B.1 do the normal parsing
-        addToWorkList(entryBlock);
+        addToWorkList(blockList[0]);
         iterateAllBlocks();
 
-        if (syncHandler != null && syncHandler.stateBefore() != null) {
+        if (syncBlock != null && syncHandler.stateBefore() != null) {
             // generate unlocking code if the exception handler is reachable
-            fillSyncHandler(rootMethodSynchronizedObject, syncHandler);
+            fillSyncHandler(rootMethodSynchronizedObject, syncBlock);
         }
     }
 
-    private Set<BlockBegin> blocksOnWorklist = new HashSet<BlockBegin>();
+    private Block nextBlock(int bci) {
+        Block block = new Block();
+        block.startBci = bci;
+        block.endBci = bci;
+        block.blockID = ir.nextBlockNumber();
+        return block;
+    }
 
-    private void markOnWorkList(BlockBegin block) {
+    private Set<Block> blocksOnWorklist = new HashSet<Block>();
+
+    private void markOnWorkList(Block block) {
         blocksOnWorklist.add(block);
     }
 
-    private boolean isOnWorkList(BlockBegin block) {
+    private boolean isOnWorkList(Block block) {
         return blocksOnWorklist.contains(block);
     }
 
-    private Set<BlockBegin> blocksVisited = new HashSet<BlockBegin>();
+    private Set<Block> blocksVisited = new HashSet<Block>();
 
-    private void markVisited(BlockBegin block) {
+    private void markVisited(Block block) {
         blocksVisited.add(block);
     }
 
-    private boolean isVisited(BlockBegin block) {
+    private boolean isVisited(Block block) {
         return blocksVisited.contains(block);
     }
 
-    private void finishStartBlock(BlockBegin startBlock, BlockBegin stdEntry) {
-        assert curBlock == startBlock;
+    private void finishStartBlock(BlockBegin startBlock, Instruction stdEntry) {
+        assert bci() == 0;
+        assert curBlock.firstInstruction == startBlock;
         FrameState stateAfter = frameState.create(bci());
-        Goto base = new Goto(stdEntry, stateAfter, graph);
+        Goto base = new Goto((BlockBegin) stdEntry, stateAfter, graph);
         appendWithBCI(base);
         startBlock.setEnd(base);
-        assert stdEntry.stateBefore() == null;
-        stdEntry.mergeOrClone(stateAfter, method());
+//        assert stdEntry instanceof Placeholder;
+        assert ((BlockBegin) stdEntry).stateBefore() == null;
+        prepareTarget(0);
+        mergeOrClone(stdEntry, stateAfter, method(), loopHeaders.contains(stdEntry));
+    }
+
+    private void prepareTarget(int bci) {
+    }
+
+    private void mergeOrClone(Instruction block, FrameState stateAfter, RiMethod method, boolean loopHeader) {
+        ((BlockBegin) block).mergeOrClone(stateAfter, method, loopHeader);
     }
 
     public RiMethod method() {
@@ -302,13 +342,13 @@
         }
 
         if (!exceptionHandlers.isEmpty()) {
-            BlockBegin successor;
+            Instruction successor;
 
             ArrayList<BlockBegin> newBlocks = new ArrayList<BlockBegin>();
 
             int current = exceptionHandlers.size() - 1;
             if (exceptionHandlers.get(current).isCatchAll()) {
-                successor = exceptionHandlers.get(current).entryBlock();
+                successor = exceptionHandlers.get(current).entryBlock().firstInstruction;
                 current--;
             } else {
                 if (unwindBlock == null) {
@@ -324,7 +364,7 @@
                 ExceptionHandler handler = exceptionHandlers.get(current);
 
                 BlockBegin newSucc = null;
-                for (Instruction pred : successor.blockPredecessors()) {
+                for (Node pred : successor.predecessors()) {
                     if (pred instanceof ExceptionDispatch) {
                         ExceptionDispatch dispatch = (ExceptionDispatch) pred;
                         if (dispatch.handler().handler == handler.handler) {
@@ -337,18 +377,20 @@
                     successor = newSucc;
                 } else {
                     BlockBegin dispatchEntry = new BlockBegin(handler.handlerBCI(), ir.nextBlockNumber(), graph);
+
                     if (handler.handler.catchType().isResolved()) {
-                        ExceptionDispatch end = new ExceptionDispatch(null, handler.entryBlock(), null, handler, null, graph);
-                        end.setBlockSuccessor(0, successor);
+                        ExceptionDispatch end = new ExceptionDispatch(null, (BlockBegin) handler.entryBlock().firstInstruction, null, handler, null, graph);
+                        end.setBlockSuccessor(0, (BlockBegin) successor);
                         dispatchEntry.appendNext(end);
                         dispatchEntry.setEnd(end);
                     } else {
                         Deoptimize deopt = new Deoptimize(graph);
                         dispatchEntry.appendNext(deopt);
-                        Goto end = new Goto(successor, null, graph);
+                        Goto end = new Goto((BlockBegin) successor, null, graph);
                         deopt.appendNext(end);
                         dispatchEntry.setEnd(end);
                     }
+
                     newBlocks.add(dispatchEntry);
                     successor = dispatchEntry;
                 }
@@ -361,7 +403,7 @@
             ExceptionObject exception = new ExceptionObject(graph);
             entry.appendNext(exception);
             FrameState stateWithException = entryState.duplicateModified(bci, CiKind.Void, exception);
-            BlockEnd end = new Goto(successor, stateWithException, graph);
+            BlockEnd end = new Goto((BlockBegin) successor, stateWithException, graph);
             exception.appendNext(end);
             entry.setEnd(end);
 
@@ -379,9 +421,8 @@
         FrameState oldState = dispatchEntry.stateBefore();
         if (oldState != null && dispatchEntry.predecessors().size() == 1) {
             dispatchEntry.setStateBefore(null);
-            oldState.delete();
         }
-        dispatchEntry.mergeOrClone(state, null);
+        dispatchEntry.mergeOrClone(state, null, false);
         FrameState mergedState = dispatchEntry.stateBefore();
 
         if (dispatchEntry.next() instanceof ExceptionDispatch) {
@@ -412,14 +453,16 @@
     private ExceptionHandler addExceptionHandler(ExceptionHandler handler, FrameStateAccess curState) {
         compilation.setHasExceptionHandlers();
 
-        BlockBegin entry = handler.entryBlock();
+        BlockMap.Block entry = handler.entryBlock();
 
         // clone exception handler
         ExceptionHandler newHandler = new ExceptionHandler(handler);
 
         // fill in exception handler subgraph lazily
         if (!isVisited(entry)) {
-            addToWorkList(entry);
+            if (handler.handlerBCI() != Instruction.SYNCHRONIZATION_ENTRY_BCI) {
+                addToWorkList(blockList[handler.handlerBCI()]);
+            }
         } else {
             // This will occur for exception handlers that cover themselves. This code
             // pattern is generated by javac for synchronized blocks. See the following
@@ -602,13 +645,13 @@
     }
 
     private void genGoto(int fromBCI, int toBCI) {
-        append(new Goto(blockAt(toBCI), null, graph));
+        append(new Goto((BlockBegin) blockAt(toBCI), null, graph));
     }
 
     private void ifNode(Value x, Condition cond, Value y, FrameState stateBefore) {
-        BlockBegin tsucc = blockAt(stream().readBranchDest());
-        BlockBegin fsucc = blockAt(stream().nextBCI());
-        append(new If(x, cond, y, tsucc, fsucc, null, graph));
+        Instruction tsucc = blockAt(stream().readBranchDest());
+        Instruction fsucc = blockAt(stream().nextBCI());
+        append(new If(x, cond, y, (BlockBegin) tsucc, (BlockBegin) fsucc, null, graph));
         stateBefore.delete();
     }
 
@@ -978,7 +1021,7 @@
         int bci = bci();
         BytecodeTableSwitch ts = new BytecodeTableSwitch(stream(), bci);
         int max = ts.numberOfCases();
-        List<BlockBegin> list = new ArrayList<BlockBegin>(max + 1);
+        List<Instruction> list = new ArrayList<Instruction>(max + 1);
         boolean isBackwards = false;
         for (int i = 0; i < max; i++) {
             // add all successors to the successor list
@@ -991,14 +1034,14 @@
         list.add(blockAt(bci + offset));
         boolean isSafepoint = isBackwards && !noSafepoints();
         FrameState stateBefore = isSafepoint ? frameState.create(bci()) : null;
-        append(new TableSwitch(frameState.ipop(), list, ts.lowKey(), stateBefore, graph));
+        append(new TableSwitch(frameState.ipop(), (List) list, ts.lowKey(), stateBefore, graph));
     }
 
     private void genLookupswitch() {
         int bci = bci();
         BytecodeLookupSwitch ls = new BytecodeLookupSwitch(stream(), bci);
         int max = ls.numberOfCases();
-        List<BlockBegin> list = new ArrayList<BlockBegin>(max + 1);
+        List<Instruction> list = new ArrayList<Instruction>(max + 1);
         int[] keys = new int[max];
         boolean isBackwards = false;
         for (int i = 0; i < max; i++) {
@@ -1013,7 +1056,7 @@
         list.add(blockAt(bci + offset));
         boolean isSafepoint = isBackwards && !noSafepoints();
         FrameState stateBefore = isSafepoint ? frameState.create(bci()) : null;
-        append(new LookupSwitch(frameState.ipop(), list, keys, stateBefore, graph));
+        append(new LookupSwitch(frameState.ipop(), (List) list, keys, stateBefore, graph));
     }
 
     private Value appendConstant(CiConstant constant) {
@@ -1033,6 +1076,10 @@
         assert x.next() == null : "instruction should not have been appended yet";
         assert lastInstr.next() == null : "cannot append instruction to instruction which isn't end (" + lastInstr + "->" + lastInstr.next() + ")";
 
+        if (placeholder != null) {
+            placeholder = null;
+        }
+
         lastInstr = lastInstr.appendNext(x);
         if (++stats.nodeCount >= C1XOptions.MaximumInstructionCount) {
             // bailout if we've exceeded the maximum inlining size
@@ -1042,12 +1089,12 @@
         return x;
     }
 
-    private BlockBegin blockAtOrNull(int bci) {
-        return blockList[bci];
+    private Instruction blockAtOrNull(int bci) {
+        return blockList[bci] != null ? blockList[bci].firstInstruction : null;
     }
 
-    private BlockBegin blockAt(int bci) {
-        BlockBegin result = blockAtOrNull(bci);
+    private Instruction blockAt(int bci) {
+        Instruction result = blockAtOrNull(bci);
         assert result != null : "Expected a block to begin at " + bci;
         return result;
     }
@@ -1061,17 +1108,18 @@
         }
     }
 
-    private void fillSyncHandler(Value lock, BlockBegin syncHandler) {
-        BlockBegin origBlock = curBlock;
+    private void fillSyncHandler(Value lock, Block syncHandler) {
+        Block origBlock = curBlock;
         FrameState origState = frameState.create(-1);
         Instruction origLast = lastInstr;
 
-        lastInstr = curBlock = syncHandler;
+        lastInstr = syncHandler.firstInstruction;
+        curBlock = syncHandler;
         while (lastInstr.next() != null) {
             // go forward to the end of the block
             lastInstr = lastInstr.next();
         }
-        frameState.initializeFrom(syncHandler.stateBefore());
+        frameState.initializeFrom(((BlockBegin) syncHandler.firstInstruction).stateBefore());
 
         int bci = Instruction.SYNCHRONIZATION_ENTRY_BCI;
 
@@ -1088,7 +1136,7 @@
 
         genThrow(bci);
         BlockEnd end = (BlockEnd) lastInstr;
-        curBlock.setEnd(end);
+        ((BlockBegin) curBlock.firstInstruction).setEnd(end);
         end.setStateAfter(frameState.create(bci()));
 
         curBlock = origBlock;
@@ -1098,24 +1146,33 @@
     }
 
     private void iterateAllBlocks() {
-        BlockBegin b;
-        while ((b = removeFromWorkList()) != null) {
+        Block block;
+        while ((block = removeFromWorkList()) != null) {
 
             // remove blocks that have no predecessors by the time it their bytecodes are parsed
-            if (b.blockPredecessors().size() == 0) {
-                markVisited(b);
+            if (block.firstInstruction.predecessors().size() == 0) {
+                markVisited(block);
                 continue;
             }
 
-            if (!isVisited(b)) {
-                markVisited(b);
+            if (!isVisited(block)) {
+                markVisited(block);
                 // now parse the block
-                curBlock = b;
-                frameState.initializeFrom(b.stateBefore());
-                lastInstr = b;
-                b.appendNext(null);
+                curBlock = block;
+                if (block.firstInstruction instanceof Placeholder) {
+                    assert false;
+                    placeholder = block.firstInstruction;
+                    frameState.initializeFrom(((Placeholder) placeholder).stateBefore());
+                    lastInstr = null;
+                } else {
+                    assert block.firstInstruction instanceof BlockBegin;
+                    placeholder = null;
+                    frameState.initializeFrom(((BlockBegin) block.firstInstruction).stateBefore());
+                    lastInstr = block.firstInstruction;
+                }
+                assert block.firstInstruction.next() == null;
 
-                iterateBytecodesForBlock(b.bci());
+                iterateBytecodesForBlock(block.startBci);
             }
         }
     }
@@ -1124,16 +1181,16 @@
         assert frameState != null;
         stream.setBCI(bci);
 
-        BlockBegin block = curBlock;
+        BlockBegin block = (BlockBegin) curBlock.firstInstruction;
         BlockEnd end = null;
         int endBCI = stream.endBCI();
         boolean blockStart = true;
 
         while (bci < endBCI) {
-            BlockBegin nextBlock = blockAtOrNull(bci);
+            Instruction nextBlock = blockAtOrNull(bci);
             if (nextBlock != null && nextBlock != block) {
                 // we fell through to the next block, add a goto and break
-                end = new Goto(nextBlock, null, graph);
+                end = new Goto((BlockBegin) nextBlock, null, graph);
                 lastInstr = lastInstr.appendNext(end);
                 break;
             }
@@ -1169,13 +1226,13 @@
         assert end != null : "end should exist after iterating over bytecodes";
         FrameState stateAtEnd = frameState.create(bci());
         end.setStateAfter(stateAtEnd);
-        curBlock.setEnd(end);
+        block.setEnd(end);
 
         // propagate the state
         for (BlockBegin succ : end.blockSuccessors()) {
-            assert succ.blockPredecessors().contains(curBlock.end());
-            succ.mergeOrClone(stateAtEnd, method());
-            addToWorkList(succ);
+            assert succ.blockPredecessors().contains(block.end());
+            succ.mergeOrClone(stateAtEnd, method(), loopHeaders.contains(succ));
+            addToWorkList(blockList[succ.bci()]);
         }
         return end;
     }
@@ -1454,39 +1511,15 @@
      * DFNs are earlier in the list).
      * @param block the block to add to the work list
      */
-    private void addToWorkList(BlockBegin block) {
+    private void addToWorkList(Block block) {
         if (!isOnWorkList(block)) {
             markOnWorkList(block);
             sortIntoWorkList(block);
         }
     }
 
-    private void sortIntoWorkList(BlockBegin top) {
-        // XXX: this is O(n), since the whole list is sorted; a heap could achieve O(nlogn), but
-        //      would only pay off for large worklists
-        if (workList == null) {
-            // need to allocate the worklist
-            workList = new BlockBegin[5];
-        } else if (workListIndex == workList.length) {
-            // need to grow the worklist
-            BlockBegin[] nworkList = new BlockBegin[workList.length * 3];
-            System.arraycopy(workList, 0, nworkList, 0, workList.length);
-            workList = nworkList;
-        }
-        // put the block at the end of the array
-        workList[workListIndex++] = top;
-        int dfn = top.depthFirstNumber();
-        assert dfn >= 0 : top + " does not have a depth first number";
-        int i = workListIndex - 2;
-        // push top towards the beginning of the array
-        for (; i >= 0; i--) {
-            BlockBegin b = workList[i];
-            if (b.depthFirstNumber() >= dfn) {
-                break; // already in the right position
-            }
-            workList[i + 1] = b; // bubble b down by one
-            workList[i] = top;   // and overwrite it with top
-        }
+    private void sortIntoWorkList(Block top) {
+        workList.offer(top);
     }
 
     /**
@@ -1495,12 +1528,8 @@
      * @return the next block from the worklist; {@code null} if there are no blocks
      * in the worklist
      */
-    private BlockBegin removeFromWorkList() {
-        if (workListIndex == 0) {
-            return null;
-        }
-        // pop the last item off the end
-        return workList[--workListIndex];
+    private Block removeFromWorkList() {
+        return workList.poll();
     }
 
     /**
diff -r beea26b73b3f -r 2ef23785ca93 graal/GraalCompiler/src/com/sun/c1x/ir/BlockBegin.java
--- a/graal/GraalCompiler/src/com/sun/c1x/ir/BlockBegin.java	Thu May 19 17:31:01 2011 +0200
+++ b/graal/GraalCompiler/src/com/sun/c1x/ir/BlockBegin.java	Thu May 19 17:36:46 2011 +0200
@@ -82,7 +82,7 @@
     private int linearScanNumber;
 
     // LIR block
-    private LIRBlock lirBlock;
+    public LIRBlock lirBlock;
 
     public void setLIRBlock(LIRBlock block) {
         this.lirBlock = block;
@@ -265,7 +265,7 @@
         v.visitBlockBegin(this);
     }
 
-    public void mergeOrClone(FrameStateAccess newState, RiMethod method) {
+    public void mergeOrClone(FrameStateAccess newState, RiMethod method, boolean loopHeader) {
         FrameState existingState = stateBefore();
 
         if (existingState == null) {
@@ -273,7 +273,7 @@
             FrameState duplicate = newState.duplicate(bci());
 
             // if the block is a loop header, insert all necessary phis
-            if (isParserLoopHeader()) {
+            if (loopHeader) {
                 insertLoopPhis(duplicate);
             }
 
@@ -306,16 +306,6 @@
         }
     }
 
-    boolean parserLoopHeader;
-
-    public boolean isParserLoopHeader() {
-        return parserLoopHeader;
-    }
-
-    public void setParserLoopHeader(boolean value) {
-        parserLoopHeader = value;
-    }
-
     @Override
     public String toString() {
         StringBuilder builder = new StringBuilder();
@@ -382,9 +372,6 @@
 
         // print flags
         StringBuilder sb = new StringBuilder(8);
-        if (isParserLoopHeader()) {
-            sb.append("LH");
-        }
         if (sb.length() != 0) {
             out.print('(').print(sb.toString()).print(')');
         }
diff -r beea26b73b3f -r 2ef23785ca93 graal/GraalCompiler/src/com/sun/c1x/ir/BlockEnd.java
--- a/graal/GraalCompiler/src/com/sun/c1x/ir/BlockEnd.java	Thu May 19 17:31:01 2011 +0200
+++ b/graal/GraalCompiler/src/com/sun/c1x/ir/BlockEnd.java	Thu May 19 17:36:46 2011 +0200
@@ -59,7 +59,14 @@
     }
 
     public FrameState setStateAfter(FrameState n) {
-        return (FrameState) successors().set(super.successorCount() + SUCCESSOR_STATE_AFTER, n);
+        FrameState oldState = stateAfter();
+        try {
+            return (FrameState) successors().set(super.successorCount() + SUCCESSOR_STATE_AFTER, n);
+        } finally {
+            if (oldState != n && oldState != null) {
+                oldState.delete();
+            }
+        }
     }
 
     /**
diff -r beea26b73b3f -r 2ef23785ca93 graal/GraalCompiler/src/com/sun/c1x/ir/ExceptionHandler.java
--- a/graal/GraalCompiler/src/com/sun/c1x/ir/ExceptionHandler.java	Thu May 19 17:31:01 2011 +0200
+++ b/graal/GraalCompiler/src/com/sun/c1x/ir/ExceptionHandler.java	Thu May 19 17:36:46 2011 +0200
@@ -24,6 +24,7 @@
 
 import java.util.*;
 
+import com.sun.c1x.graph.*;
 import com.sun.c1x.lir.*;
 import com.sun.cri.ri.*;
 
@@ -41,7 +42,7 @@
     public static final List<ExceptionHandler> ZERO_HANDLERS = Collections.emptyList();
 
     public final RiExceptionHandler handler;
-    private BlockBegin entryBlock;
+    private BlockMap.Block entryBlock;
     private LIRList entryCode;
     private int entryCodeOffset;
     private int phiOperand;
@@ -98,7 +99,7 @@
      * Gets the entry block for this exception handler.
      * @return the entry block
      */
-    public BlockBegin entryBlock() {
+    public BlockMap.Block entryBlock() {
         return entryBlock;
     }
 
@@ -115,7 +116,7 @@
         return phiOperand;
     }
 
-    public void setEntryBlock(BlockBegin entry) {
+    public void setEntryBlock(BlockMap.Block entry) {
         entryBlock = entry;
     }
 
diff -r beea26b73b3f -r 2ef23785ca93 graal/GraalCompiler/src/com/sun/c1x/ir/Placeholder.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/GraalCompiler/src/com/sun/c1x/ir/Placeholder.java	Thu May 19 17:36:46 2011 +0200
@@ -0,0 +1,84 @@
+/*
+ * Copyright (c) 2011, 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.sun.c1x.ir;
+
+import com.oracle.graal.graph.*;
+import com.sun.c1x.debug.*;
+import com.sun.c1x.value.*;
+import com.sun.cri.ci.*;
+
+
+public class Placeholder extends Instruction {
+
+    private static final int INPUT_COUNT = 1;
+    private static final int INPUT_STATE_BEFORE = 0;
+
+    private static final int SUCCESSOR_COUNT = 0;
+
+    @Override
+    protected int inputCount() {
+        return super.inputCount() + INPUT_COUNT;
+    }
+
+    @Override
+    protected int successorCount() {
+        return super.successorCount() + SUCCESSOR_COUNT;
+    }
+
+    /**
+     * The state for this instruction.
+     */
+    public FrameState stateBefore() {
+        return (FrameState) inputs().get(super.inputCount() + INPUT_STATE_BEFORE);
+    }
+
+    public FrameState setStateBefore(FrameState n) {
+        FrameState oldState = stateBefore();
+        try {
+            return (FrameState) inputs().set(super.inputCount() + INPUT_STATE_BEFORE, n);
+        } finally {
+            if (oldState != n && oldState != null) {
+                oldState.delete();
+            }
+        }
+    }
+
+    public Placeholder(Graph graph) {
+        super(CiKind.Void, INPUT_COUNT, SUCCESSOR_COUNT, graph);
+    }
+
+    @Override
+    public void accept(ValueVisitor v) {
+        assert false;
+    }
+
+    @Override
+    public void print(LogStream out) {
+        assert false;
+    }
+
+    @Override
+    public String shortName() {
+        return "Placeholder" + id();
+    }
+}
diff -r beea26b73b3f -r 2ef23785ca93 graal/GraalCompiler/src/com/sun/c1x/ir/StateSplit.java
--- a/graal/GraalCompiler/src/com/sun/c1x/ir/StateSplit.java	Thu May 19 17:31:01 2011 +0200
+++ b/graal/GraalCompiler/src/com/sun/c1x/ir/StateSplit.java	Thu May 19 17:36:46 2011 +0200
@@ -56,7 +56,14 @@
     }
 
     public FrameState setStateBefore(FrameState n) {
-        return (FrameState) inputs().set(super.inputCount() + INPUT_STATE_BEFORE, n);
+        FrameState oldState = stateBefore();
+        try {
+            return (FrameState) inputs().set(super.inputCount() + INPUT_STATE_BEFORE, n);
+        } finally {
+            if (oldState != n && oldState != null) {
+                oldState.delete();
+            }
+        }
     }
 
     /**
diff -r beea26b73b3f -r 2ef23785ca93 src/share/vm/c1x/c1x_VMEntries.cpp
--- a/src/share/vm/c1x/c1x_VMEntries.cpp	Thu May 19 17:31:01 2011 +0200
+++ b/src/share/vm/c1x/c1x_VMEntries.cpp	Thu May 19 17:36:46 2011 +0200
@@ -68,7 +68,6 @@
   TRACE_C1X_3("VMEntries::RiMethod_signature");
   VM_ENTRY_MARK
   methodOop method = VmIds::get<methodOop>(vmId);
-  method->constMethod()->exception_table();
   return VmIds::toString<jstring>(method->signature(), THREAD);
 }