comparison graal/GraalCompiler/src/com/sun/c1x/graph/GraphBuilder.java @ 2566:d524ad648049

Finish remove inlining (removed ScopeData), remove JSR support
author Gilles Duboscq <gilles.duboscq@oracle.com>
date Mon, 02 May 2011 10:24:16 +0200
parents cc1f1d396288
children 46586c77b129
comparison
equal deleted inserted replaced
2565:cc1f1d396288 2566:d524ad648049
59 * The minimum value to which {@link C1XOptions#TraceBytecodeParserLevel} must be set to trace 59 * The minimum value to which {@link C1XOptions#TraceBytecodeParserLevel} must be set to trace
60 * the frame state before each bytecode instruction as it is parsed. 60 * the frame state before each bytecode instruction as it is parsed.
61 */ 61 */
62 public static final int TRACELEVEL_STATE = 2; 62 public static final int TRACELEVEL_STATE = 2;
63 63
64 /**
65 * An enumeration of flags describing scope attributes.
66 */
67 public enum Flag {
68 /**
69 * Scope is protected by an exception handler.
70 * This attribute is inherited by nested scopes.
71 */
72 HasHandler,
73
74 /**
75 * Code in scope cannot contain safepoints.
76 * This attribute is inherited by nested scopes.
77 */
78 NoSafepoints;
79
80 public final int mask = 1 << ordinal();
81 }
82
64 final IR ir; 83 final IR ir;
65 final C1XCompilation compilation; 84 final C1XCompilation compilation;
66 final CiStatistics stats; 85 final CiStatistics stats;
67 86
68 /** 87 /**
73 /** 92 /**
74 * Map used for local load elimination (i.e. within the current block). 93 * Map used for local load elimination (i.e. within the current block).
75 */ 94 */
76 final MemoryMap memoryMap; 95 final MemoryMap memoryMap;
77 96
78 ScopeData scopeData; // Per-scope data; used for inlining 97 final BytecodeStream stream; // the bytecode stream
98 // bci-to-block mapping
99 BlockMap blockMap;
100
101 // the constant pool
102 final RiConstantPool constantPool;
103
104 // the worklist of blocks, managed like a sorted list
105 BlockBegin[] workList;
106
107 // the current position in the worklist
108 int workListIndex;
109
110 /**
111 * Mask of {@link Flag} values.
112 */
113 int flags;
114
115 // Exception handler list
116 List<ExceptionHandler> exceptionHandlers;
117
79 BlockBegin curBlock; // the current block 118 BlockBegin curBlock; // the current block
80 MutableFrameState curState; // the current execution state 119 MutableFrameState curState; // the current execution state
81 Instruction lastInstr; // the last instruction added 120 Instruction lastInstr; // the last instruction added
82 final LogStream log; 121 final LogStream log;
83 122
84 boolean skipBlock; // skip processing of the rest of this block 123 boolean skipBlock; // skip processing of the rest of this block
85 private Value rootMethodSynchronizedObject; 124 private Value rootMethodSynchronizedObject;
86
87 /** 125 /**
88 * Creates a new, initialized, {@code GraphBuilder} instance for a given compilation. 126 * Creates a new, initialized, {@code GraphBuilder} instance for a given compilation.
89 * 127 *
90 * @param compilation the compilation 128 * @param compilation the compilation
91 * @param ir the IR to build the graph into 129 * @param ir the IR to build the graph into
95 this.ir = ir; 133 this.ir = ir;
96 this.stats = compilation.stats; 134 this.stats = compilation.stats;
97 this.memoryMap = C1XOptions.OptLocalLoadElimination ? new MemoryMap() : null; 135 this.memoryMap = C1XOptions.OptLocalLoadElimination ? new MemoryMap() : null;
98 this.localValueMap = C1XOptions.OptLocalValueNumbering ? new ValueMap() : null; 136 this.localValueMap = C1XOptions.OptLocalValueNumbering ? new ValueMap() : null;
99 log = C1XOptions.TraceBytecodeParserLevel > 0 ? new LogStream(TTY.out()) : null; 137 log = C1XOptions.TraceBytecodeParserLevel > 0 ? new LogStream(TTY.out()) : null;
138 stream = new BytecodeStream(compilation.method.code());
139 constantPool = compilation.runtime.getConstantPool(compilation.method);
100 } 140 }
101 141
102 /** 142 /**
103 * Builds the graph for a the specified {@code IRScope}. 143 * Builds the graph for a the specified {@code IRScope}.
104 * @param scope the top IRScope 144 * @param scope the top IRScope
109 if (log != null) { 149 if (log != null) {
110 log.println(); 150 log.println();
111 log.println("Compiling " + compilation.method); 151 log.println("Compiling " + compilation.method);
112 } 152 }
113 153
154 if (rootMethod.noSafepoints()) {
155 flags |= Flag.NoSafepoints.mask;
156 }
157
114 // 1. create the start block 158 // 1. create the start block
115 ir.startBlock = new BlockBegin(0, ir.nextBlockNumber()); 159 ir.startBlock = new BlockBegin(0, ir.nextBlockNumber());
116 BlockBegin startBlock = ir.startBlock; 160 BlockBegin startBlock = ir.startBlock;
117 161
118 // 2. compute the block map and get the entrypoint(s) 162 // 2. compute the block map, setup exception handlers and get the entrypoint(s)
119 BlockMap blockMap = compilation.getBlockMap(rootMethod); 163 blockMap = compilation.getBlockMap(rootMethod);
120 BlockBegin stdEntry = blockMap.get(0); 164 BlockBegin stdEntry = blockMap.get(0);
121 pushRootScope(rootMethod, blockMap, startBlock); 165 curBlock = startBlock;
166
167 RiExceptionHandler[] handlers = rootMethod.exceptionHandlers();
168 if (handlers != null && handlers.length > 0) {
169 exceptionHandlers = new ArrayList<ExceptionHandler>(handlers.length);
170 for (RiExceptionHandler ch : handlers) {
171 ExceptionHandler h = new ExceptionHandler(ch);
172 h.setEntryBlock(blockAt(h.handler.handlerBCI()));
173 exceptionHandlers.add(h);
174 }
175 flags |= Flag.HasHandler.mask;
176 }
177
122 MutableFrameState initialState = stateAtEntry(rootMethod); 178 MutableFrameState initialState = stateAtEntry(rootMethod);
123 startBlock.mergeOrClone(initialState, rootMethod); 179 startBlock.mergeOrClone(initialState, rootMethod);
124 BlockBegin syncHandler = null; 180 BlockBegin syncHandler = null;
125 181
126 // 3. setup internal state for appending instructions 182 // 3. setup internal state for appending instructions
142 syncHandler.setBlockFlag(BlockBegin.BlockFlag.IsOnWorkList); 198 syncHandler.setBlockFlag(BlockBegin.BlockFlag.IsOnWorkList);
143 syncHandler.setBlockFlag(BlockBegin.BlockFlag.DefaultExceptionHandler); 199 syncHandler.setBlockFlag(BlockBegin.BlockFlag.DefaultExceptionHandler);
144 200
145 ExceptionHandler h = new ExceptionHandler(new CiExceptionHandler(0, rootMethod.code().length, -1, 0, null)); 201 ExceptionHandler h = new ExceptionHandler(new CiExceptionHandler(0, rootMethod.code().length, -1, 0, null));
146 h.setEntryBlock(syncHandler); 202 h.setEntryBlock(syncHandler);
147 scopeData.addExceptionHandler(h); 203 addExceptionHandler(h);
148 } else { 204 } else {
149 // 4B.1 simply finish the start block 205 // 4B.1 simply finish the start block
150 finishStartBlock(startBlock, stdEntry); 206 finishStartBlock(startBlock, stdEntry);
151 } 207 }
152 208
153 // 5. SKIPPED: look for intrinsics 209 // 5. SKIPPED: look for intrinsics
154 210
155 // 6B.1 do the normal parsing 211 // 6B.1 do the normal parsing
156 scopeData.addToWorkList(stdEntry); 212 addToWorkList(stdEntry);
157 iterateAllBlocks(); 213 iterateAllBlocks();
158 214
159 if (syncHandler != null && syncHandler.stateBefore() != null) { 215 if (syncHandler != null && syncHandler.stateBefore() != null) {
160 // generate unlocking code if the exception handler is reachable 216 // generate unlocking code if the exception handler is reachable
161 fillSyncHandler(rootMethodSynchronizedObject, syncHandler, false); 217 fillSyncHandler(rootMethodSynchronizedObject, syncHandler, false);
171 startBlock.setEnd(base); 227 startBlock.setEnd(base);
172 assert stdEntry.stateBefore() == null; 228 assert stdEntry.stateBefore() == null;
173 stdEntry.mergeOrClone(stateAfter, method()); 229 stdEntry.mergeOrClone(stateAfter, method());
174 } 230 }
175 231
176 void pushRootScope(RiMethod method, BlockMap blockMap, BlockBegin start) {
177 BytecodeStream stream = new BytecodeStream(method.code());
178 RiConstantPool constantPool = compilation.runtime.getConstantPool(method);
179 scopeData = new ScopeData(null, method, blockMap, stream, constantPool);
180 curBlock = start;
181 }
182
183 public boolean hasHandler() {
184 return scopeData.hasHandler();
185 }
186
187 public RiMethod method() { 232 public RiMethod method() {
188 return compilation.method; 233 return compilation.method;
189 } 234 }
190 235
191 public BytecodeStream stream() { 236 public BytecodeStream stream() {
192 return scopeData.stream; 237 return stream;
193 } 238 }
194 239
195 public int bci() { 240 public int bci() {
196 return scopeData.stream.currentBCI(); 241 return stream.currentBCI();
197 } 242 }
198 243
199 public int nextBCI() { 244 public int nextBCI() {
200 return scopeData.stream.nextBCI(); 245 return stream.nextBCI();
201 } 246 }
202 247
203 private void ipush(Value x) { 248 private void ipush(Value x) {
204 curState.ipush(x); 249 curState.ipush(x);
205 } 250 }
275 private void loadLocal(int index, CiKind kind) { 320 private void loadLocal(int index, CiKind kind) {
276 push(kind, curState.loadLocal(index)); 321 push(kind, curState.loadLocal(index));
277 } 322 }
278 323
279 private void storeLocal(CiKind kind, int index) { 324 private void storeLocal(CiKind kind, int index) {
280 if (scopeData.parsingJsr()) {
281 // We need to do additional tracking of the location of the return
282 // address for jsrs since we don't handle arbitrary jsr/ret
283 // constructs. Here we are figuring out in which circumstances we
284 // need to bail out.
285 if (kind == CiKind.Object) {
286 // might be storing the JSR return address
287 Value x = curState.xpop();
288 if (x.kind.isJsr()) {
289 setJsrReturnAddressLocal(index);
290 curState.storeLocal(index, x);
291 } else {
292 // nope, not storing the JSR return address
293 assert x.kind.isObject();
294 curState.storeLocal(index, x);
295 overwriteJsrReturnAddressLocal(index);
296 }
297 return;
298 } else {
299 // not storing the JSR return address local, but might overwrite it
300 overwriteJsrReturnAddressLocal(index);
301 }
302 }
303
304 curState.storeLocal(index, pop(kind)); 325 curState.storeLocal(index, pop(kind));
305 }
306
307 private void overwriteJsrReturnAddressLocal(int index) {
308 if (index == scopeData.jsrEntryReturnAddressLocal()) {
309 scopeData.setJsrEntryReturnAddressLocal(-1);
310 }
311 }
312
313 private void setJsrReturnAddressLocal(int index) {
314 scopeData.setJsrEntryReturnAddressLocal(index);
315
316 // Also check parent jsrs (if any) at this time to see whether
317 // they are using this local. We don't handle skipping over a
318 // ret.
319 for (ScopeData cur = scopeData.parent; cur != null && cur.parsingJsr(); cur = cur.parent) {
320 if (cur.jsrEntryReturnAddressLocal() == index) {
321 throw new CiBailout("subroutine overwrites return address from previous subroutine");
322 }
323 }
324 } 326 }
325 327
326 List<ExceptionHandler> handleException(Instruction x, int bci) { 328 List<ExceptionHandler> handleException(Instruction x, int bci) {
327 if (!hasHandler()) { 329 if (!hasHandler()) {
328 return Util.uncheckedCast(Collections.EMPTY_LIST); 330 return Util.uncheckedCast(Collections.EMPTY_LIST);
329 } 331 }
330 332
331 ArrayList<ExceptionHandler> exceptionHandlers = new ArrayList<ExceptionHandler>(); 333 ArrayList<ExceptionHandler> exceptionHandlers = new ArrayList<ExceptionHandler>();
332 ScopeData curScopeData = scopeData;
333 FrameState stateBefore = x.stateBefore(); 334 FrameState stateBefore = x.stateBefore();
334 int scopeCount = 0; 335 int scopeCount = 0;
335 336
336 assert stateBefore != null : "exception handler state must be available for " + x; 337 assert stateBefore != null : "exception handler state must be available for " + x;
337 FrameState state = stateBefore; 338 FrameState state = stateBefore;
338 assert bci == Instruction.SYNCHRONIZATION_ENTRY_BCI || bci == curScopeData.stream.currentBCI() : "invalid bci"; 339 assert bci == Instruction.SYNCHRONIZATION_ENTRY_BCI || bci == bci() : "invalid bci";
339 340
340 // join with all potential exception handlers 341 // join with all potential exception handlers
341 List<ExceptionHandler> handlers = curScopeData.exceptionHandlers(); 342 if (this.exceptionHandlers != null) {
342 if (handlers != null) { 343 for (ExceptionHandler handler : this.exceptionHandlers) {
343 for (ExceptionHandler handler : handlers) {
344 if (handler.covers(bci)) { 344 if (handler.covers(bci)) {
345 // if the handler covers this bytecode index, add it to the list 345 // if the handler covers this bytecode index, add it to the list
346 if (addExceptionHandler(exceptionHandlers, handler, curScopeData, state, scopeCount)) { 346 if (addExceptionHandler(exceptionHandlers, handler, state, scopeCount)) {
347 // if the handler was a default handler, we are done 347 // if the handler was a default handler, we are done
348 return exceptionHandlers; 348 return exceptionHandlers;
349 } 349 }
350 } 350 }
351 } 351 }
363 * @param curScopeData 363 * @param curScopeData
364 * @param curState the current state with empty stack 364 * @param curState the current state with empty stack
365 * @param scopeCount 365 * @param scopeCount
366 * @return {@code true} if handler catches all exceptions (i.e. {@code handler.isCatchAll() == true}) 366 * @return {@code true} if handler catches all exceptions (i.e. {@code handler.isCatchAll() == true})
367 */ 367 */
368 private boolean addExceptionHandler(ArrayList<ExceptionHandler> exceptionHandlers, ExceptionHandler handler, ScopeData curScopeData, FrameState curState, int scopeCount) { 368 private boolean addExceptionHandler(ArrayList<ExceptionHandler> exceptionHandlers, ExceptionHandler handler, FrameState curState, int scopeCount) {
369 compilation.setHasExceptionHandlers(); 369 compilation.setHasExceptionHandlers();
370 370
371 BlockBegin entry = handler.entryBlock(); 371 BlockBegin entry = handler.entryBlock();
372 FrameState entryState = entry.stateBefore(); 372 FrameState entryState = entry.stateBefore();
373 373
374 assert entry.bci() == handler.handler.handlerBCI(); 374 assert entry.bci() == handler.handler.handlerBCI();
375 assert entry.bci() == -1 || entry == curScopeData.blockAt(entry.bci()) : "blocks must correspond"; 375 assert entryState == null || curState.locksSize() == entryState.locksSize() : "locks do not match : cur:"+curState.locksSize()+" entry:"+entryState.locksSize();
376 assert entryState == null || curState.locksSize() == entryState.locksSize() : "locks do not match";
377 376
378 // exception handler starts with an empty expression stack 377 // exception handler starts with an empty expression stack
379 curState = curState.immutableCopyWithEmptyStack(); 378 curState = curState.immutableCopyWithEmptyStack();
380 379
381 entry.mergeOrClone(curState, method()); 380 entry.mergeOrClone(curState, method());
397 newHandler.setScopeCount(scopeCount); 396 newHandler.setScopeCount(scopeCount);
398 exceptionHandlers.add(newHandler); 397 exceptionHandlers.add(newHandler);
399 398
400 // fill in exception handler subgraph lazily 399 // fill in exception handler subgraph lazily
401 if (!entry.wasVisited()) { 400 if (!entry.wasVisited()) {
402 curScopeData.addToWorkList(entry); 401 addToWorkList(entry);
403 } else { 402 } else {
404 // This will occur for exception handlers that cover themselves. This code 403 // This will occur for exception handlers that cover themselves. This code
405 // pattern is generated by javac for synchronized blocks. See the following 404 // pattern is generated by javac for synchronized blocks. See the following
406 // for why this change to javac was made: 405 // for why this change to javac was made:
407 // 406 //
593 Value y = append(Constant.forInt(delta)); 592 Value y = append(Constant.forInt(delta));
594 curState.storeLocal(index, append(new ArithmeticOp(IADD, CiKind.Int, x, y, isStrict(method().accessFlags()), null))); 593 curState.storeLocal(index, append(new ArithmeticOp(IADD, CiKind.Int, x, y, isStrict(method().accessFlags()), null)));
595 } 594 }
596 595
597 void genGoto(int fromBCI, int toBCI) { 596 void genGoto(int fromBCI, int toBCI) {
598 boolean isSafepoint = !scopeData.noSafepoints() && toBCI <= fromBCI; 597 boolean isSafepoint = !noSafepoints() && toBCI <= fromBCI;
599 append(new Goto(blockAt(toBCI), null, isSafepoint)); 598 append(new Goto(blockAt(toBCI), null, isSafepoint));
600 } 599 }
601 600
602 void ifNode(Value x, Condition cond, Value y, FrameState stateBefore) { 601 void ifNode(Value x, Condition cond, Value y, FrameState stateBefore) {
603 BlockBegin tsucc = blockAt(stream().readBranchDest()); 602 BlockBegin tsucc = blockAt(stream().readBranchDest());
604 BlockBegin fsucc = blockAt(stream().nextBCI()); 603 BlockBegin fsucc = blockAt(stream().nextBCI());
605 int bci = stream().currentBCI(); 604 int bci = stream().currentBCI();
606 boolean isSafepoint = !scopeData.noSafepoints() && tsucc.bci() <= bci || fsucc.bci() <= bci; 605 boolean isSafepoint = !noSafepoints() && tsucc.bci() <= bci || fsucc.bci() <= bci;
607 append(new If(x, cond, y, tsucc, fsucc, isSafepoint ? stateBefore : null, isSafepoint)); 606 append(new If(x, cond, y, tsucc, fsucc, isSafepoint ? stateBefore : null, isSafepoint));
608 } 607 }
609 608
610 void genIfZero(Condition cond) { 609 void genIfZero(Condition cond) {
611 Value y = appendConstant(CiConstant.INT_0); 610 Value y = appendConstant(CiConstant.INT_0);
628 ifNode(x, cond, y, stateBefore); 627 ifNode(x, cond, y, stateBefore);
629 } 628 }
630 629
631 void genThrow(int bci) { 630 void genThrow(int bci) {
632 FrameState stateBefore = curState.immutableCopy(bci()); 631 FrameState stateBefore = curState.immutableCopy(bci());
633 Throw t = new Throw(apop(), stateBefore, !scopeData.noSafepoints()); 632 Throw t = new Throw(apop(), stateBefore, !noSafepoints());
634 appendWithoutOptimization(t, bci); 633 appendWithoutOptimization(t, bci);
635 } 634 }
636 635
637 void genCheckCast() { 636 void genCheckCast() {
638 int cpi = stream().readCPI(); 637 int cpi = stream().readCPI();
1005 void genReturn(Value x) { 1004 void genReturn(Value x) {
1006 if (method().isConstructor() && method().holder().superType() == null) { 1005 if (method().isConstructor() && method().holder().superType() == null) {
1007 callRegisterFinalizer(); 1006 callRegisterFinalizer();
1008 } 1007 }
1009 1008
1010 // If inlining, then returns become gotos to the continuation point.
1011 if (scopeData.continuation() != null) {
1012 if (isSynchronized(method().accessFlags())) {
1013 // if the inlined method is synchronized, then the monitor
1014 // must be released before jumping to the continuation point
1015 Value object = curState.lockAt(0);
1016 if (object instanceof Instruction) {
1017 Instruction obj = (Instruction) object;
1018 if (!obj.isAppended()) {
1019 appendWithoutOptimization(obj, Instruction.SYNCHRONIZATION_ENTRY_BCI);
1020 }
1021 }
1022 genMonitorExit(object, Instruction.SYNCHRONIZATION_ENTRY_BCI);
1023 }
1024
1025 // empty stack for return value
1026 curState.truncateStack(0);
1027 if (x != null) {
1028 curState.push(x.kind, x);
1029 }
1030 Goto gotoCallee = new Goto(scopeData.continuation(), null, false);
1031
1032 // ATTN: assumption: curState is not used further down, else add .immutableCopy()
1033 scopeData.updateSimpleInlineInfo(curBlock, lastInstr, curState);
1034
1035 // State at end of inlined method is the state of the caller
1036 // without the method parameters on stack, including the
1037 // return value, if any, of the inlined method on operand stack.
1038 curState = scopeData.continuationState().copy();
1039 if (x != null) {
1040 curState.push(x.kind, x);
1041 }
1042
1043 // The current bci is in the wrong scope, so use the bci of the continuation point.
1044 appendWithoutOptimization(gotoCallee, scopeData.continuation().bci());
1045 return;
1046 }
1047
1048 curState.truncateStack(0); 1009 curState.truncateStack(0);
1049 if (Modifier.isSynchronized(method().accessFlags())) { 1010 if (Modifier.isSynchronized(method().accessFlags())) {
1050 FrameState stateBefore = curState.immutableCopy(bci()); 1011 FrameState stateBefore = curState.immutableCopy(bci());
1051 // unlock before exiting the method 1012 // unlock before exiting the method
1052 int lockNumber = curState.locksSize() - 1; 1013 int lockNumber = curState.locksSize() - 1;
1056 append(lockAddress); 1017 append(lockAddress);
1057 } 1018 }
1058 append(new MonitorExit(rootMethodSynchronizedObject, lockAddress, lockNumber, stateBefore)); 1019 append(new MonitorExit(rootMethodSynchronizedObject, lockAddress, lockNumber, stateBefore));
1059 curState.unlock(); 1020 curState.unlock();
1060 } 1021 }
1061 append(new Return(x, !scopeData.noSafepoints())); 1022 append(new Return(x, !noSafepoints()));
1062 } 1023 }
1063 1024
1064 /** 1025 /**
1065 * Gets the number of locks held. 1026 * Gets the number of locks held.
1066 */ 1027 */
1096 curState.unlock(); 1057 curState.unlock();
1097 killMemoryMap(); // prevent any optimizations across synchronization 1058 killMemoryMap(); // prevent any optimizations across synchronization
1098 } 1059 }
1099 1060
1100 void genJsr(int dest) { 1061 void genJsr(int dest) {
1101 for (ScopeData cur = scopeData; cur != null && cur.parsingJsr(); cur = cur.parent) { 1062 throw new CiBailout("jsr/ret not supported");
1102 if (cur.jsrEntryBCI() == dest) {
1103 // the jsr/ret pattern includes a recursive invocation
1104 throw new CiBailout("recursive jsr/ret structure");
1105 }
1106 }
1107 System.err.println("> JSR!");
1108 push(CiKind.Jsr, append(Constant.forJsr(nextBCI())));
1109 tryInlineJsr(dest);
1110 } 1063 }
1111 1064
1112 void genRet(int localIndex) { 1065 void genRet(int localIndex) {
1113 if (!scopeData.parsingJsr()) { 1066 throw new CiBailout("jsr/ret not supported");
1114 throw new CiBailout("ret encountered when not parsing subroutine");
1115 }
1116
1117 if (localIndex != scopeData.jsrEntryReturnAddressLocal()) {
1118 throw new CiBailout("jsr/ret structure is too complicated");
1119 }
1120 // rets become non-safepoint gotos
1121 append(new Goto(scopeData.jsrContinuation(), null, false));
1122 } 1067 }
1123 1068
1124 void genTableswitch() { 1069 void genTableswitch() {
1125 int bci = bci(); 1070 int bci = bci();
1126 BytecodeTableSwitch ts = new BytecodeTableSwitch(stream(), bci); 1071 BytecodeTableSwitch ts = new BytecodeTableSwitch(stream(), bci);
1134 isBackwards |= offset < 0; // track if any of the successors are backwards 1079 isBackwards |= offset < 0; // track if any of the successors are backwards
1135 } 1080 }
1136 int offset = ts.defaultOffset(); 1081 int offset = ts.defaultOffset();
1137 isBackwards |= offset < 0; // if the default successor is backwards 1082 isBackwards |= offset < 0; // if the default successor is backwards
1138 list.add(blockAt(bci + offset)); 1083 list.add(blockAt(bci + offset));
1139 boolean isSafepoint = isBackwards && !scopeData.noSafepoints(); 1084 boolean isSafepoint = isBackwards && !noSafepoints();
1140 FrameState stateBefore = isSafepoint ? curState.immutableCopy(bci()) : null; 1085 FrameState stateBefore = isSafepoint ? curState.immutableCopy(bci()) : null;
1141 append(new TableSwitch(ipop(), list, ts.lowKey(), stateBefore, isSafepoint)); 1086 append(new TableSwitch(ipop(), list, ts.lowKey(), stateBefore, isSafepoint));
1142 } 1087 }
1143 1088
1144 void genLookupswitch() { 1089 void genLookupswitch() {
1156 isBackwards |= offset < 0; // track if any of the successors are backwards 1101 isBackwards |= offset < 0; // track if any of the successors are backwards
1157 } 1102 }
1158 int offset = ls.defaultOffset(); 1103 int offset = ls.defaultOffset();
1159 isBackwards |= offset < 0; // if the default successor is backwards 1104 isBackwards |= offset < 0; // if the default successor is backwards
1160 list.add(blockAt(bci + offset)); 1105 list.add(blockAt(bci + offset));
1161 boolean isSafepoint = isBackwards && !scopeData.noSafepoints(); 1106 boolean isSafepoint = isBackwards && !noSafepoints();
1162 FrameState stateBefore = isSafepoint ? curState.immutableCopy(bci()) : null; 1107 FrameState stateBefore = isSafepoint ? curState.immutableCopy(bci()) : null;
1163 append(new LookupSwitch(ipop(), list, keys, stateBefore, isSafepoint)); 1108 append(new LookupSwitch(ipop(), list, keys, stateBefore, isSafepoint));
1164 } 1109 }
1165 1110
1166 /** 1111 /**
1252 private boolean hasUncontrollableSideEffects(Value x) { 1197 private boolean hasUncontrollableSideEffects(Value x) {
1253 return x instanceof Invoke || x instanceof ResolveClass; 1198 return x instanceof Invoke || x instanceof ResolveClass;
1254 } 1199 }
1255 1200
1256 private BlockBegin blockAtOrNull(int bci) { 1201 private BlockBegin blockAtOrNull(int bci) {
1257 return scopeData.blockAt(bci); 1202 return blockMap.get(bci);
1258 } 1203 }
1259 1204
1260 private BlockBegin blockAt(int bci) { 1205 private BlockBegin blockAt(int bci) {
1261 BlockBegin result = blockAtOrNull(bci); 1206 BlockBegin result = blockAtOrNull(bci);
1262 assert result != null : "Expected a block to begin at " + bci; 1207 assert result != null : "Expected a block to begin at " + bci;
1263 return result; 1208 return result;
1264 }
1265
1266 boolean tryInlineJsr(int jsrStart) {
1267 // start a new continuation point.
1268 // all ret instructions will be replaced with gotos to this point
1269 BlockBegin cont = blockAt(nextBCI());
1270
1271 // push callee scope
1272 pushScopeForJsr(cont, jsrStart);
1273
1274 BlockBegin jsrStartBlock = blockAt(jsrStart);
1275 assert !jsrStartBlock.wasVisited();
1276 Goto gotoSub = new Goto(jsrStartBlock, null, false);
1277 gotoSub.setStateAfter(curState.immutableCopy(bci()));
1278 assert jsrStartBlock.stateBefore() == null;
1279 jsrStartBlock.setStateBefore(curState.immutableCopy(bci()));
1280 append(gotoSub);
1281 curBlock.setEnd(gotoSub);
1282 lastInstr = curBlock = jsrStartBlock;
1283
1284 scopeData.addToWorkList(jsrStartBlock);
1285
1286 iterateAllBlocks();
1287
1288 if (cont.stateBefore() != null) {
1289 if (!cont.wasVisited()) {
1290 scopeData.parent.addToWorkList(cont);
1291 }
1292 }
1293
1294 BlockBegin jsrCont = scopeData.jsrContinuation();
1295 assert jsrCont == cont && (!jsrCont.wasVisited() || jsrCont.isParserLoopHeader());
1296 assert lastInstr != null && lastInstr instanceof BlockEnd;
1297
1298 // continuation is in work list, so end iteration of current block
1299 skipBlock = true;
1300 popScopeForJsr();
1301 C1XMetrics.InlinedJsrs++;
1302 return true;
1303 }
1304
1305 void pushScopeForJsr(BlockBegin jsrCont, int jsrStart) {
1306 BytecodeStream stream = new BytecodeStream(compilation.method.code());
1307 RiConstantPool constantPool = scopeData.constantPool;
1308 ScopeData data = new ScopeData(scopeData, compilation.method, scopeData.blockMap, stream, constantPool, jsrStart);
1309 BlockBegin continuation = scopeData.continuation();
1310 data.setContinuation(continuation);
1311 if (continuation != null) {
1312 assert scopeData.continuationState() != null;
1313 data.setContinuationState(scopeData.continuationState().copy());
1314 }
1315 data.setJsrContinuation(jsrCont);
1316 scopeData = data;
1317 } 1209 }
1318 1210
1319 MutableFrameState stateAtEntry(RiMethod method) { 1211 MutableFrameState stateAtEntry(RiMethod method) {
1320 MutableFrameState state = new MutableFrameState(-1, method.maxLocals(), method.maxStackSize()); 1212 MutableFrameState state = new MutableFrameState(-1, method.maxLocals(), method.maxStackSize());
1321 int index = 0; 1213 int index = 0;
1389 lastInstr = origLast; 1281 lastInstr = origLast;
1390 } 1282 }
1391 1283
1392 private void iterateAllBlocks() { 1284 private void iterateAllBlocks() {
1393 BlockBegin b; 1285 BlockBegin b;
1394 while ((b = scopeData.removeFromWorkList()) != null) { 1286 while ((b = removeFromWorkList()) != null) {
1395 if (!b.wasVisited()) { 1287 if (!b.wasVisited()) {
1396 b.setWasVisited(true); 1288 b.setWasVisited(true);
1397 // now parse the block 1289 // now parse the block
1398 killMemoryMap(); 1290 killMemoryMap();
1399 curBlock = b; 1291 curBlock = b;
1404 iterateBytecodesForBlock(b.bci(), false); 1296 iterateBytecodesForBlock(b.bci(), false);
1405 } 1297 }
1406 } 1298 }
1407 } 1299 }
1408 1300
1409 private void popScopeForJsr() {
1410 scopeData = scopeData.parent;
1411 }
1412
1413 private BlockEnd iterateBytecodesForBlock(int bci, boolean inliningIntoCurrentBlock) { 1301 private BlockEnd iterateBytecodesForBlock(int bci, boolean inliningIntoCurrentBlock) {
1414 skipBlock = false; 1302 skipBlock = false;
1415 assert curState != null; 1303 assert curState != null;
1416 BytecodeStream s = scopeData.stream; 1304 stream.setBCI(bci);
1417 s.setBCI(bci);
1418 1305
1419 BlockBegin block = curBlock; 1306 BlockBegin block = curBlock;
1420 BlockEnd end = null; 1307 BlockEnd end = null;
1421 boolean pushException = block.isExceptionEntry() && block.next() == null; 1308 boolean pushException = block.isExceptionEntry() && block.next() == null;
1422 int prevBCI = bci; 1309 int prevBCI = bci;
1423 int endBCI = s.endBCI(); 1310 int endBCI = stream.endBCI();
1424 boolean blockStart = true; 1311 boolean blockStart = true;
1425 1312
1426 while (bci < endBCI) { 1313 while (bci < endBCI) {
1427 BlockBegin nextBlock = blockAtOrNull(bci); 1314 BlockBegin nextBlock = blockAtOrNull(bci);
1428 if (bci == 0 && inliningIntoCurrentBlock) { 1315 if (bci == 0 && inliningIntoCurrentBlock) {
1438 end = new Goto(nextBlock, null, false); 1325 end = new Goto(nextBlock, null, false);
1439 lastInstr = lastInstr.setNext(end, prevBCI); 1326 lastInstr = lastInstr.setNext(end, prevBCI);
1440 break; 1327 break;
1441 } 1328 }
1442 // read the opcode 1329 // read the opcode
1443 int opcode = s.currentBC(); 1330 int opcode = stream.currentBC();
1444 1331
1445 // push an exception object onto the stack if we are parsing an exception handler 1332 // push an exception object onto the stack if we are parsing an exception handler
1446 if (pushException) { 1333 if (pushException) {
1447 FrameState stateBefore = curState.immutableCopy(bci()); 1334 FrameState stateBefore = curState.immutableCopy(bci());
1448 apush(append(new ExceptionObject(stateBefore))); 1335 apush(append(new ExceptionObject(stateBefore)));
1449 pushException = false; 1336 pushException = false;
1450 } 1337 }
1451 1338
1452 traceState(); 1339 traceState();
1453 traceInstruction(bci, s, opcode, blockStart); 1340 traceInstruction(bci, stream, opcode, blockStart);
1454 processBytecode(bci, s, opcode); 1341 processBytecode(bci, stream, opcode);
1455 1342
1456 prevBCI = bci; 1343 prevBCI = bci;
1457 1344
1458 if (lastInstr instanceof BlockEnd) { 1345 if (lastInstr instanceof BlockEnd) {
1459 end = (BlockEnd) lastInstr; 1346 end = (BlockEnd) lastInstr;
1460 break; 1347 break;
1461 } 1348 }
1462 s.next(); 1349 stream.next();
1463 bci = s.currentBCI(); 1350 bci = stream.currentBCI();
1464 blockStart = false; 1351 blockStart = false;
1465 } 1352 }
1466 1353
1467 // stop processing of this block 1354 // stop processing of this block
1468 if (skipBlock) { 1355 if (skipBlock) {
1482 curBlock.setEnd(end); 1369 curBlock.setEnd(end);
1483 // propagate the state 1370 // propagate the state
1484 for (BlockBegin succ : end.successors()) { 1371 for (BlockBegin succ : end.successors()) {
1485 assert succ.predecessors().contains(curBlock); 1372 assert succ.predecessors().contains(curBlock);
1486 succ.mergeOrClone(end.stateAfter(), method()); 1373 succ.mergeOrClone(end.stateAfter(), method());
1487 scopeData.addToWorkList(succ); 1374 addToWorkList(succ);
1488 } 1375 }
1489 return end; 1376 return end;
1490 } 1377 }
1491 1378
1492 private void traceState() { 1379 private void traceState() {
1794 } 1681 }
1795 return null; 1682 return null;
1796 } 1683 }
1797 1684
1798 private RiConstantPool constantPool() { 1685 private RiConstantPool constantPool() {
1799 return scopeData.constantPool; 1686 return constantPool;
1687 }
1688
1689 /**
1690 * Adds an exception handler
1691 * @param handler the handler to add
1692 */
1693 private void addExceptionHandler(ExceptionHandler handler) {
1694 if (exceptionHandlers == null) {
1695 exceptionHandlers = new ArrayList<ExceptionHandler>();
1696 }
1697 exceptionHandlers.add(handler);
1698 flags |= Flag.HasHandler.mask;
1699 }
1700
1701 /**
1702 * Adds a block to the worklist, if it is not already in the worklist.
1703 * This method will keep the worklist topologically stored (i.e. the lower
1704 * DFNs are earlier in the list).
1705 * @param block the block to add to the work list
1706 */
1707 private void addToWorkList(BlockBegin block) {
1708 if (!block.isOnWorkList()) {
1709 block.setOnWorkList(true);
1710 sortIntoWorkList(block);
1711 }
1712 }
1713
1714 private void sortIntoWorkList(BlockBegin top) {
1715 // XXX: this is O(n), since the whole list is sorted; a heap could achieve O(nlogn), but
1716 // would only pay off for large worklists
1717 if (workList == null) {
1718 // need to allocate the worklist
1719 workList = new BlockBegin[5];
1720 } else if (workListIndex == workList.length) {
1721 // need to grow the worklist
1722 BlockBegin[] nworkList = new BlockBegin[workList.length * 3];
1723 System.arraycopy(workList, 0, nworkList, 0, workList.length);
1724 workList = nworkList;
1725 }
1726 // put the block at the end of the array
1727 workList[workListIndex++] = top;
1728 int dfn = top.depthFirstNumber();
1729 assert dfn >= 0 : top + " does not have a depth first number";
1730 int i = workListIndex - 2;
1731 // push top towards the beginning of the array
1732 for (; i >= 0; i--) {
1733 BlockBegin b = workList[i];
1734 if (b.depthFirstNumber() >= dfn) {
1735 break; // already in the right position
1736 }
1737 workList[i + 1] = b; // bubble b down by one
1738 workList[i] = top; // and overwrite it with top
1739 }
1740 }
1741
1742 /**
1743 * Removes the next block from the worklist. The list is sorted topologically, so the
1744 * block with the lowest depth first number in the list will be removed and returned.
1745 * @return the next block from the worklist; {@code null} if there are no blocks
1746 * in the worklist
1747 */
1748 private BlockBegin removeFromWorkList() {
1749 if (workListIndex == 0) {
1750 return null;
1751 }
1752 // pop the last item off the end
1753 return workList[--workListIndex];
1754 }
1755
1756 /**
1757 * Checks whether this graph has any handlers.
1758 * @return {@code true} if there are any exception handlers
1759 */
1760 private boolean hasHandler() {
1761 return (flags & Flag.HasHandler.mask) != 0;
1762 }
1763
1764 /**
1765 * Checks whether this graph can contain safepoints.
1766 */
1767 private boolean noSafepoints() {
1768 return (flags & Flag.NoSafepoints.mask) != 0;
1800 } 1769 }
1801 } 1770 }