graal-jvmci-8: graal/GraalCompiler/src/com/sun/c1x/graph/GraphBuilder.java comparison

comparison graal/GraalCompiler/src/com/sun/c1x/graph/GraphBuilder.java @ 2733:2ef23785ca93

Merge.

author	Thomas Wuerthinger <thomas@wuerthinger.net>
date	Thu, 19 May 2011 17:36:46 +0200
parents	a2f62de90c76 027adfafd47e
children	d913f3049cee

comparison

equal deleted inserted replaced

-:beea26b73b3f
+:2ef23785ca93
 import java.util.*;
 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.*;
 import com.sun.cri.bytecode.*;
 import com.sun.cri.ci.*;
 private final C1XCompilation compilation;
 private final CiStatistics stats;
 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
+// the worklist of blocks, sorted by depth first number
-private BlockBegin[] workList;
+private final PriorityQueue<Block> workList = new PriorityQueue<Block>(10, new Comparator<Block>() {
+public int compare(Block o1, Block o2) {
-// the current position in the worklist
+return o1.blockID - o2.blockID;
-private int workListIndex;
+}
+});
 /**
 * Mask of {@link Flag} values.
 */
 private int flags;
 // Exception handler list
 private List<ExceptionHandler> exceptionHandlers;
-private BlockBegin curBlock;                   // the current block
+private Block curBlock;                   // the current block
-private FrameStateBuilder frameState;          // the current execution state
+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;
 private final Graph graph;
 private BlockBegin unwindBlock;
+private final Set<Instruction> loopHeaders = new HashSet<Instruction>();
 /**
 * Creates a new, initialized, {@code GraphBuilder} instance for a given compilation.
 *
 * @param compilation the compilation
 }
 // 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);
+Block block = blockMap.blocks.get(i);
-BlockBegin blockBegin = new BlockBegin(block.startBci, ir.nextBlockNumber(), graph);
-if (block.isLoopHeader) {
+//            if (block.isLoopHeader) {
-blockBegin.setParserLoopHeader(true);
+BlockBegin blockBegin = new BlockBegin(block.startBci, ir.nextBlockNumber(), graph);
-}
+blockBegin.setDepthFirstNumber(blockBegin.blockID);
-blockBegin.setDepthFirstNumber(blockBegin.blockID);
-blockList[block.startBci] = blockBegin;
+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);
+Block startBlock = nextBlock(Instruction.SYNCHRONIZATION_ENTRY_BCI);
-graph.root().setStart(startBlock);
+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);
 h.setEntryBlock(entry);
 exceptionHandlers.add(h);
 }
 }
 flags |= Flag.HasHandler.mask;
 }
-startBlock.mergeOrClone(frameState, rootMethod);
+assert !loopHeaders.contains(startBlock);
-BlockBegin syncHandler = null;
+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);
+syncBlock = nextBlock(Instruction.SYNCHRONIZATION_ENTRY_BCI);
-markOnWorkList(syncHandler);
+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();
-private void markOnWorkList(BlockBegin block) {
+block.startBci = bci;
+block.endBci = bci;
+block.blockID = ir.nextBlockNumber();
+return 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) {
+private void finishStartBlock(BlockBegin startBlock, Instruction stdEntry) {
-assert curBlock == startBlock;
+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;
+//        assert stdEntry instanceof Placeholder;
-stdEntry.mergeOrClone(stateAfter, method());
+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() {
 return compilation.method;
 }
 }
 }
 }
 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) {
 unwindBlock = new BlockBegin(bci, ir.nextBlockNumber(), graph);
 Unwind unwind = new Unwind(null, graph);
 for (; current >= 0; current--) {
 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) {
 newSucc = dispatch.begin();
 break;
 }
 if (newSucc != null) {
 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);
+ExceptionDispatch end = new ExceptionDispatch(null, (BlockBegin) handler.entryBlock().firstInstruction, null, handler, null, graph);
-end.setBlockSuccessor(0, successor);
+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;
 }
 }
 BlockBegin entry = new BlockBegin(bci, ir.nextBlockNumber(), graph);
 entry.setStateBefore(entryState);
 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);
 if (x instanceof Invoke) {
 ((Invoke) x).setExceptionEdge(entry);
 private void updateDispatchChain(BlockBegin dispatchEntry, FrameStateAccess state, int bci) {
 FrameState oldState = dispatchEntry.stateBefore();
 if (oldState != null && dispatchEntry.predecessors().size() == 1) {
 dispatchEntry.setStateBefore(null);
-oldState.delete();
+}
-}
+dispatchEntry.mergeOrClone(state, null, false);
-dispatchEntry.mergeOrClone(state, null);
 FrameState mergedState = dispatchEntry.stateBefore();
 if (dispatchEntry.next() instanceof ExceptionDispatch) {
 // ordinary dispatch handler
 ExceptionDispatch dispatch = (ExceptionDispatch) dispatchEntry.next();
 * of exception handlers for the {@link #curBlock current block}.
 */
 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
 // for why this change to javac was made:
 //
 Value y = append(Constant.forInt(delta, graph));
 frameState.storeLocal(index, append(new ArithmeticOp(IADD, CiKind.Int, x, y, isStrict(method().accessFlags()), false, graph)));
 }
 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());
+Instruction tsucc = blockAt(stream().readBranchDest());
-BlockBegin fsucc = blockAt(stream().nextBCI());
+Instruction fsucc = blockAt(stream().nextBCI());
-append(new If(x, cond, y, tsucc, fsucc, null, graph));
+append(new If(x, cond, y, (BlockBegin) tsucc, (BlockBegin) fsucc, null, graph));
 stateBefore.delete();
 }
 private void genIfZero(Condition cond) {
 Value y = appendConstant(CiConstant.INT_0);
 private void genTableswitch() {
 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
 int offset = ts.offsetAt(i);
 list.add(blockAt(bci + offset));
 int offset = ts.defaultOffset();
 isBackwards |= offset < 0; // if the default successor is backwards
 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++) {
 // add all successors to the successor list
 int offset = ls.offsetAt(i);
 int offset = ls.defaultOffset();
 isBackwards |= offset < 0; // if the default successor is backwards
 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) {
 return appendWithBCI(new Constant(constant, graph));
 }
 }
 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
 throw new CiBailout("Method and/or inlining is too large");
 }
 return x;
 }
-private BlockBegin blockAtOrNull(int bci) {
+private Instruction blockAtOrNull(int bci) {
-return blockList[bci];
+return blockList[bci] != null ? blockList[bci].firstInstruction : null;
 }
-private BlockBegin blockAt(int bci) {
+private Instruction blockAt(int bci) {
-BlockBegin result = blockAtOrNull(bci);
+Instruction result = blockAtOrNull(bci);
 assert result != null : "Expected a block to begin at " + bci;
 return result;
 }
 private Value synchronizedObject(FrameStateAccess state, RiMethod target) {
 } else {
 return state.localAt(0);
 }
 }
-private void fillSyncHandler(Value lock, BlockBegin syncHandler) {
+private void fillSyncHandler(Value lock, Block syncHandler) {
-BlockBegin origBlock = curBlock;
+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;
 assert lock != null;
 assert frameState.locksSize() > 0 && frameState.lockAt(frameState.locksSize() - 1) == lock;
 // exit the monitor
 genMonitorExit(lock, Instruction.SYNCHRONIZATION_ENTRY_BCI);
 genThrow(bci);
 BlockEnd end = (BlockEnd) lastInstr;
-curBlock.setEnd(end);
+((BlockBegin) curBlock.firstInstruction).setEnd(end);
 end.setStateAfter(frameState.create(bci()));
 curBlock = origBlock;
 frameState.initializeFrom(origState);
 origState.delete();
 lastInstr = origLast;
 }
 private void iterateAllBlocks() {
-BlockBegin b;
+Block block;
-while ((b = removeFromWorkList()) != null) {
+while ((block = removeFromWorkList()) != null) {
 // remove blocks that have no predecessors by the time it their bytecodes are parsed
-if (b.blockPredecessors().size() == 0) {
+if (block.firstInstruction.predecessors().size() == 0) {
-markVisited(b);
+markVisited(block);
 continue;
 }
-if (!isVisited(b)) {
+if (!isVisited(block)) {
-markVisited(b);
+markVisited(block);
 // now parse the block
-curBlock = b;
+curBlock = block;
-frameState.initializeFrom(b.stateBefore());
+if (block.firstInstruction instanceof Placeholder) {
-lastInstr = b;
+assert false;
-b.appendNext(null);
+placeholder = block.firstInstruction;
+frameState.initializeFrom(((Placeholder) placeholder).stateBefore());
-iterateBytecodesForBlock(b.bci());
+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(block.startBci);
 }
 }
 }
 private BlockEnd iterateBytecodesForBlock(int bci) {
 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;
 }
 // read the opcode
 int opcode = stream.currentBC();
 // connect to begin and set state
 // NOTE that inlining may have changed the block we are parsing
 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());
+assert succ.blockPredecessors().contains(block.end());
-succ.mergeOrClone(stateAtEnd, method());
+succ.mergeOrClone(stateAtEnd, method(), loopHeaders.contains(succ));
-addToWorkList(succ);
+addToWorkList(blockList[succ.bci()]);
 }
 return end;
 }
 private void traceState() {
 * Adds a block to the worklist, if it is not already in the worklist.
 * This method will keep the worklist topologically stored (i.e. the lower
 * 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) {
+private void sortIntoWorkList(Block top) {
-// XXX: this is O(n), since the whole list is sorted; a heap could achieve O(nlogn), but
+workList.offer(top);
-//      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
-}
 }
 /**
 * Removes the next block from the worklist. The list is sorted topologically, so the
 * block with the lowest depth first number in the list will be removed and returned.
 * @return the next block from the worklist; {@code null} if there are no blocks
 * in the worklist
 */
-private BlockBegin removeFromWorkList() {
+private Block removeFromWorkList() {
-if (workListIndex == 0) {
+return workList.poll();
-return null;
-}
-// pop the last item off the end
-return workList[--workListIndex];
 }
 /**
 * Checks whether this graph has any handlers.
 * @return {@code true} if there are any exception handlers

Mercurial > hg > graal-jvmci-8

comparison graal/GraalCompiler/src/com/sun/c1x/graph/GraphBuilder.java @ 2733:2ef23785ca93