Mercurial > hg > truffle

comparison graal/GraalCompiler/src/com/sun/c1x/graph/ScopeData.java @ 2509:16b9a8b5ad39

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Renamings Runtime=>GraalRuntime and Compiler=>GraalCompiler
author Thomas Wuerthinger <thomas@wuerthinger.net>
date Wed, 27 Apr 2011 11:50:44 +0200
parents graal/Compiler/src/com/sun/c1x/graph/ScopeData.java@9ec15d6914ca
children 274360f98f97
comparison
equal deleted inserted replaced
2508:fea94949e0a2 2509:16b9a8b5ad39
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 }