Mercurial > hg > truffle
comparison graal/Compiler/src/com/sun/c1x/graph/ScopeData.java @ 2507:9ec15d6914ca
Pull over of compiler from maxine repository.
author | Thomas Wuerthinger <thomas@wuerthinger.net> |
---|---|
date | Wed, 27 Apr 2011 11:43:22 +0200 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
2506:4a3bf8a5bf41 | 2507:9ec15d6914ca |
---|---|
1 /* | |
2 * Copyright (c) 2009, 2011, Oracle and/or its affiliates. All rights reserved. | |
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. | |
4 * | |
5 * This code is free software; you can redistribute it and/or modify it | |
6 * under the terms of the GNU General Public License version 2 only, as | |
7 * published by the Free Software Foundation. | |
8 * | |
9 * This code is distributed in the hope that it will be useful, but WITHOUT | |
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
12 * version 2 for more details (a copy is included in the LICENSE file that | |
13 * accompanied this code). | |
14 * | |
15 * You should have received a copy of the GNU General Public License version | |
16 * 2 along with this work; if not, write to the Free Software Foundation, | |
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. | |
18 * | |
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA | |
20 * or visit www.oracle.com if you need additional information or have any | |
21 * questions. | |
22 */ | |
23 package com.sun.c1x.graph; | |
24 | |
25 import static com.sun.c1x.graph.ScopeData.Flag.*; | |
26 import static com.sun.c1x.graph.ScopeData.ReturnBlock.*; | |
27 | |
28 import java.util.*; | |
29 | |
30 import com.sun.c1x.*; | |
31 import com.sun.c1x.ir.*; | |
32 import com.sun.c1x.value.*; | |
33 import com.sun.cri.bytecode.*; | |
34 import com.sun.cri.ri.*; | |
35 | |
36 /** | |
37 * The {@code ScopeData} class represents inlining context when parsing the bytecodes | |
38 * of an inlined method. | |
39 * | |
40 * @author Ben L. Titzer | |
41 */ | |
42 public class ScopeData { | |
43 // XXX: refactor and split this class into ScopeData, JsrScopeData, and InlineScopeData | |
44 | |
45 /** | |
46 * An enumeration of flags describing scope attributes. | |
47 */ | |
48 public enum Flag { | |
49 /** | |
50 * Scope is protected by an exception handler. | |
51 * This attribute is inherited by nested scopes. | |
52 */ | |
53 HasHandler, | |
54 | |
55 /** | |
56 * Code in scope cannot contain safepoints. | |
57 * This attribute is inherited by nested scopes. | |
58 */ | |
59 NoSafepoints; | |
60 | |
61 public final int mask = 1 << ordinal(); | |
62 } | |
63 | |
64 | |
65 final ScopeData parent; | |
66 // the IR scope | |
67 final IRScope scope; | |
68 // bci-to-block mapping | |
69 final BlockMap blockMap; | |
70 // the bytecode stream | |
71 final BytecodeStream stream; | |
72 // the constant pool | |
73 final RiConstantPool constantPool; | |
74 // the worklist of blocks, managed like a sorted list | |
75 BlockBegin[] workList; | |
76 // the current position in the worklist | |
77 int workListIndex; | |
78 // maximum inline size for this scope | |
79 int maxInlineSize; | |
80 | |
81 /** | |
82 * Mask of {@link Flag} values. | |
83 */ | |
84 int flags; | |
85 | |
86 // Exception handler list | |
87 List<ExceptionHandler> exceptionHandlers; | |
88 | |
89 // The continuation point for the inline. Currently only used in | |
90 // multi-block inlines, but eventually would like to use this for | |
91 // all inlines for uniformity and simplicity; in this case would | |
92 // get the continuation point from the BlockList instead of | |
93 // fabricating it anew because Invokes would be considered to be | |
94 // BlockEnds. | |
95 BlockBegin continuation; | |
96 | |
97 // Without return value of inlined method on stack | |
98 FrameState continuationState; | |
99 | |
100 /** | |
101 * Field used to generate fewer blocks when inlining. If this value is {@code null}, | |
102 * then no {@code return}s have been encountered during inlining. If it is an instance | |
103 * of {@link ReturnBlock}, then it is the block info for the single {@code return} | |
104 * encountered. Otherwise, it will be {@link ReturnBlock#MULTIPLE_RETURNS}. | |
105 */ | |
106 ReturnBlock inlinedReturnBlock; | |
107 | |
108 /** | |
109 * Tracks the destination bci of the jsr. This is (currently) only used to determine | |
110 * bailout conditions, since only a subset of all of the possible jsr-ret control | |
111 * structures can (currently) be compiled. | |
112 * | |
113 * A value > 0 for this field indicates parsing of a jsr. | |
114 */ | |
115 final int jsrEntryBci; | |
116 | |
117 // We need to track the local variable in which the return address | |
118 // was stored to ensure we can handle inlining the jsr, because we | |
119 // don't handle arbitrary jsr/ret constructs. | |
120 int jsrRetAddrLocal; | |
121 | |
122 // If we are parsing a jsr, the continuation point for rets | |
123 BlockBegin jsrContinuation; | |
124 | |
125 final BlockBegin[] jsrDuplicatedBlocks; // blocks that have been duplicated for JSR inlining | |
126 | |
127 /** | |
128 * Constructs a new ScopeData instance with the specified parent ScopeData. | |
129 * @param parent the parent scope data | |
130 * @param scope the IR scope | |
131 * @param blockMap the block map for this scope | |
132 * @param stream the bytecode stream | |
133 * @param constantPool the constant pool | |
134 */ | |
135 public ScopeData(ScopeData parent, IRScope scope, BlockMap blockMap, BytecodeStream stream, RiConstantPool constantPool) { | |
136 this.parent = parent; | |
137 this.scope = scope; | |
138 this.blockMap = blockMap; | |
139 this.stream = stream; | |
140 this.constantPool = constantPool; | |
141 this.jsrEntryBci = -1; | |
142 this.jsrDuplicatedBlocks = null; | |
143 if (parent != null) { | |
144 maxInlineSize = (int) (C1XOptions.MaximumInlineRatio * parent.maxInlineSize()); | |
145 if (maxInlineSize < C1XOptions.MaximumTrivialSize) { | |
146 maxInlineSize = C1XOptions.MaximumTrivialSize; | |
147 } | |
148 if (parent.hasHandler()) { | |
149 flags |= HasHandler.mask; | |
150 } | |
151 if (parent.noSafepoints() || scope.method.noSafepoints()) { | |
152 flags |= NoSafepoints.mask; | |
153 } | |
154 } else { | |
155 maxInlineSize = C1XOptions.MaximumInlineSize; | |
156 if (scope.method.noSafepoints()) { | |
157 flags |= NoSafepoints.mask; | |
158 } | |
159 } | |
160 RiExceptionHandler[] handlers = scope.method.exceptionHandlers(); | |
161 if (handlers != null && handlers.length > 0) { | |
162 exceptionHandlers = new ArrayList<ExceptionHandler>(handlers.length); | |
163 for (RiExceptionHandler ch : handlers) { | |
164 ExceptionHandler h = new ExceptionHandler(ch); | |
165 h.setEntryBlock(blockAt(h.handler.handlerBCI())); | |
166 exceptionHandlers.add(h); | |
167 } | |
168 flags |= HasHandler.mask; | |
169 } | |
170 } | |
171 | |
172 /** | |
173 * Constructs a new ScopeData instance with the specified parent ScopeData. This constructor variant creates | |
174 * a scope data for parsing a JSR. | |
175 * @param parent the parent scope data | |
176 * @param scope the IR scope | |
177 * @param blockMap the block map for this scope | |
178 * @param stream the bytecode stream | |
179 * @param constantPool the constant pool | |
180 * @param jsrEntryBci the bytecode index of the entrypoint of the JSR | |
181 */ | |
182 public ScopeData(ScopeData parent, IRScope scope, BlockMap blockMap, BytecodeStream stream, RiConstantPool constantPool, int jsrEntryBci) { | |
183 this.parent = parent; | |
184 this.scope = scope; | |
185 this.blockMap = blockMap; | |
186 this.stream = stream; | |
187 this.constantPool = constantPool; | |
188 assert jsrEntryBci > 0 : "jsr cannot jump to BCI 0"; | |
189 assert parent != null : "jsr must have parent scope"; | |
190 this.jsrEntryBci = jsrEntryBci; | |
191 this.jsrDuplicatedBlocks = new BlockBegin[scope.method.code().length]; | |
192 this.jsrRetAddrLocal = -1; | |
193 | |
194 maxInlineSize = (int) (C1XOptions.MaximumInlineRatio * parent.maxInlineSize()); | |
195 if (maxInlineSize < C1XOptions.MaximumTrivialSize) { | |
196 maxInlineSize = C1XOptions.MaximumTrivialSize; | |
197 } | |
198 flags = parent.flags; | |
199 | |
200 // duplicate the parent scope's exception handlers, if any | |
201 List<ExceptionHandler> handlers = parent.exceptionHandlers(); | |
202 if (handlers != null && handlers.size() > 0) { | |
203 exceptionHandlers = new ArrayList<ExceptionHandler>(handlers.size()); | |
204 for (ExceptionHandler ph : handlers) { | |
205 ExceptionHandler h = new ExceptionHandler(ph); | |
206 int handlerBci = h.handler.handlerBCI(); | |
207 if (handlerBci >= 0) { | |
208 // need to duplicate the handler block because it is a "normal" handler | |
209 h.setEntryBlock(blockAt(handlerBci)); | |
210 } else { | |
211 // don't duplicate the handler block because it is a synchronization handler | |
212 // that was added by parsing/inlining a synchronized method | |
213 assert ph.entryBlock().checkBlockFlag(BlockBegin.BlockFlag.DefaultExceptionHandler); | |
214 h.setEntryBlock(ph.entryBlock()); | |
215 } | |
216 exceptionHandlers.add(h); | |
217 } | |
218 assert hasHandler(); | |
219 } | |
220 } | |
221 | |
222 /** | |
223 * Gets the block beginning at the specified bytecode index. Note that this method | |
224 * will clone the block if it the scope data is currently parsing a JSR. | |
225 * @param bci the bytecode index of the start of the block | |
226 * @return the block starting at the specified bytecode index | |
227 */ | |
228 public BlockBegin blockAt(int bci) { | |
229 if (jsrDuplicatedBlocks != null) { | |
230 // all blocks in a JSR are duplicated on demand using an internal array, | |
231 // including those for exception handlers in the scope of the method | |
232 // containing the jsr (because those exception handlers may contain ret | |
233 // instructions in some cases). | |
234 BlockBegin block = jsrDuplicatedBlocks[bci]; | |
235 if (block == null) { | |
236 BlockBegin p = this.parent.blockAt(bci); | |
237 if (p != null) { | |
238 BlockBegin newBlock = new BlockBegin(p.bci(), C1XCompilation.compilation().hir().nextBlockNumber()); | |
239 newBlock.setDepthFirstNumber(p.depthFirstNumber()); | |
240 newBlock.copyBlockFlags(p); | |
241 jsrDuplicatedBlocks[bci] = newBlock; | |
242 block = newBlock; | |
243 } | |
244 } | |
245 return block; | |
246 } | |
247 return blockMap.get(bci); | |
248 } | |
249 | |
250 /** | |
251 * Checks whether this scope has any handlers. | |
252 * @return {@code true} if there are any exception handlers | |
253 */ | |
254 public boolean hasHandler() { | |
255 return (flags & Flag.HasHandler.mask) != 0; | |
256 } | |
257 | |
258 /** | |
259 * Checks whether this scope can contain safepoints. | |
260 */ | |
261 public boolean noSafepoints() { | |
262 return (flags & Flag.NoSafepoints.mask) != 0; | |
263 } | |
264 | |
265 /** | |
266 * Gets the maximum inline size. | |
267 * @return the maximum inline size | |
268 */ | |
269 public int maxInlineSize() { | |
270 return maxInlineSize; | |
271 } | |
272 | |
273 /** | |
274 * Gets the size of the stack at the caller. | |
275 * @return the size of the stack | |
276 */ | |
277 public int callerStackSize() { | |
278 FrameState state = scope.callerState; | |
279 return state == null ? 0 : state.stackSize(); | |
280 } | |
281 | |
282 /** | |
283 * Gets the block continuation for this ScopeData. | |
284 * @return the continuation | |
285 */ | |
286 public BlockBegin continuation() { | |
287 return continuation; | |
288 } | |
289 | |
290 /** | |
291 * Sets the continuation for this ScopeData. | |
292 * @param continuation the continuation | |
293 */ | |
294 public void setContinuation(BlockBegin continuation) { | |
295 this.continuation = continuation; | |
296 } | |
297 | |
298 /** | |
299 * Gets the state at the continuation point. | |
300 * @return the state at the continuation point | |
301 */ | |
302 public FrameState continuationState() { | |
303 return continuationState; | |
304 } | |
305 | |
306 /** | |
307 * Sets the state at the continuation point. | |
308 * @param state the state at the continuation | |
309 */ | |
310 public void setContinuationState(FrameState state) { | |
311 continuationState = state; | |
312 } | |
313 | |
314 /** | |
315 * Checks whether this ScopeData is parsing a JSR. | |
316 * @return {@code true} if this scope data is parsing a JSR | |
317 */ | |
318 public boolean parsingJsr() { | |
319 return jsrEntryBci > 0; | |
320 } | |
321 | |
322 /** | |
323 * Gets the bytecode index for the JSR entry. | |
324 * @return the jsr entry bci | |
325 */ | |
326 public int jsrEntryBCI() { | |
327 return jsrEntryBci; | |
328 } | |
329 | |
330 /** | |
331 * Gets the index of the local variable containing the JSR return address. | |
332 * @return the index of the local with the JSR return address | |
333 */ | |
334 public int jsrEntryReturnAddressLocal() { | |
335 return jsrRetAddrLocal; | |
336 } | |
337 | |
338 /** | |
339 * Sets the index of the local variable containing the JSR return address. | |
340 * @param local the local | |
341 */ | |
342 public void setJsrEntryReturnAddressLocal(int local) { | |
343 jsrRetAddrLocal = local; | |
344 } | |
345 | |
346 /** | |
347 * Gets the continuation for parsing a JSR. | |
348 * @return the jsr continuation | |
349 */ | |
350 public BlockBegin jsrContinuation() { | |
351 return jsrContinuation; | |
352 } | |
353 | |
354 /** | |
355 * Sets the continuation for parsing a JSR. | |
356 * @param block the block that is the continuation | |
357 */ | |
358 public void setJsrContinuation(BlockBegin block) { | |
359 jsrContinuation = block; | |
360 } | |
361 | |
362 /** | |
363 * A block delimited by a return instruction in an inlined method. | |
364 */ | |
365 public static class ReturnBlock { | |
366 /** | |
367 * The inlined block. | |
368 */ | |
369 final BlockBegin block; | |
370 | |
371 /** | |
372 * The second last instruction in the block. That is, the one before the return instruction. | |
373 */ | |
374 final Instruction returnPredecessor; | |
375 | |
376 /** | |
377 * The frame state at the end of the block. | |
378 */ | |
379 final FrameState returnState; | |
380 | |
381 ReturnBlock(BlockBegin block, Instruction returnPredecessor, FrameState returnState) { | |
382 super(); | |
383 this.block = block; | |
384 this.returnPredecessor = returnPredecessor; | |
385 this.returnState = returnState; | |
386 } | |
387 | |
388 public static final ReturnBlock MULTIPLE_RETURNS = new ReturnBlock(null, null, null); | |
389 } | |
390 | |
391 /** | |
392 * Updates the info about blocks in this scope delimited by a return instruction. | |
393 * | |
394 * @param block a block delimited by a {@code return} instruction | |
395 * @param returnPredecessor the second last instruction in the block. That is, the one before the return instruction. | |
396 * @param returnState the frame state after the return instruction | |
397 */ | |
398 public void updateSimpleInlineInfo(BlockBegin block, Instruction returnPredecessor, FrameState returnState) { | |
399 if (inlinedReturnBlock == null) { | |
400 inlinedReturnBlock = new ReturnBlock(block, returnPredecessor, returnState); | |
401 } else { | |
402 inlinedReturnBlock = MULTIPLE_RETURNS; | |
403 } | |
404 } | |
405 | |
406 /** | |
407 * Gets the return block info for a simple inline scope. That is, a scope that contains only a | |
408 * single block delimited by a {@code return} instruction. | |
409 * | |
410 * @return the return block info for a simple inline scope or {@code null} if this is not a simple inline scope | |
411 */ | |
412 public ReturnBlock simpleInlineInfo() { | |
413 if (inlinedReturnBlock == MULTIPLE_RETURNS) { | |
414 return null; | |
415 } | |
416 return inlinedReturnBlock; | |
417 } | |
418 | |
419 /** | |
420 * Gets the list of exception handlers for this scope data. | |
421 * @return the list of exception handlers | |
422 */ | |
423 public List<ExceptionHandler> exceptionHandlers() { | |
424 return exceptionHandlers; | |
425 } | |
426 | |
427 /** | |
428 * Adds an exception handler to this scope data. | |
429 * @param handler the handler to add | |
430 */ | |
431 public void addExceptionHandler(ExceptionHandler handler) { | |
432 if (exceptionHandlers == null) { | |
433 exceptionHandlers = new ArrayList<ExceptionHandler>(); | |
434 } | |
435 assert !parsingJsr() : "jsr scope should already have all the handlers it needs"; | |
436 exceptionHandlers.add(handler); | |
437 flags |= HasHandler.mask; | |
438 } | |
439 | |
440 /** | |
441 * Adds a block to the worklist, if it is not already in the worklist. | |
442 * This method will keep the worklist topologically stored (i.e. the lower | |
443 * DFNs are earlier in the list). | |
444 * @param block the block to add to the work list | |
445 */ | |
446 public void addToWorkList(BlockBegin block) { | |
447 if (!block.isOnWorkList()) { | |
448 if (block == continuation || block == jsrContinuation) { | |
449 return; | |
450 } | |
451 block.setOnWorkList(true); | |
452 sortIntoWorkList(block); | |
453 } | |
454 } | |
455 | |
456 private void sortIntoWorkList(BlockBegin top) { | |
457 // XXX: this is O(n), since the whole list is sorted; a heap could achieve O(nlogn), but | |
458 // would only pay off for large worklists | |
459 if (workList == null) { | |
460 // need to allocate the worklist | |
461 workList = new BlockBegin[5]; | |
462 } else if (workListIndex == workList.length) { | |
463 // need to grow the worklist | |
464 BlockBegin[] nworkList = new BlockBegin[workList.length * 3]; | |
465 System.arraycopy(workList, 0, nworkList, 0, workList.length); | |
466 workList = nworkList; | |
467 } | |
468 // put the block at the end of the array | |
469 workList[workListIndex++] = top; | |
470 int dfn = top.depthFirstNumber(); | |
471 assert dfn >= 0 : top + " does not have a depth first number"; | |
472 int i = workListIndex - 2; | |
473 // push top towards the beginning of the array | |
474 for (; i >= 0; i--) { | |
475 BlockBegin b = workList[i]; | |
476 if (b.depthFirstNumber() >= dfn) { | |
477 break; // already in the right position | |
478 } | |
479 workList[i + 1] = b; // bubble b down by one | |
480 workList[i] = top; // and overwrite it with top | |
481 } | |
482 } | |
483 | |
484 /** | |
485 * Removes the next block from the worklist. The list is sorted topologically, so the | |
486 * block with the lowest depth first number in the list will be removed and returned. | |
487 * @return the next block from the worklist; {@code null} if there are no blocks | |
488 * in the worklist | |
489 */ | |
490 public BlockBegin removeFromWorkList() { | |
491 if (workListIndex == 0) { | |
492 return null; | |
493 } | |
494 // pop the last item off the end | |
495 return workList[--workListIndex]; | |
496 } | |
497 | |
498 /** | |
499 * Converts this scope data to a string for debugging purposes. | |
500 * @return a string representation of this scope data | |
501 */ | |
502 @Override | |
503 public String toString() { | |
504 if (parsingJsr()) { | |
505 return "jsr@" + jsrEntryBci + " data for " + scope.toString(); | |
506 } else { | |
507 return "data for " + scope.toString(); | |
508 } | |
509 | |
510 } | |
511 } |