Mercurial > hg > graal-jvmci-8
comparison graal/Compiler/src/com/sun/c1x/graph/BlockMap.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.cri.bytecode.Bytecodes.*; | |
26 | |
27 import java.util.*; | |
28 | |
29 import com.sun.c1x.*; | |
30 import com.sun.c1x.ir.*; | |
31 import com.sun.c1x.util.*; | |
32 import com.sun.cri.bytecode.*; | |
33 import com.sun.cri.ci.*; | |
34 import com.sun.cri.ri.*; | |
35 | |
36 /** | |
37 * Builds a mapping between bytecodes and basic blocks and builds a conservative control flow | |
38 * graph. Note that this class serves a similar role to C1's {@code BlockListBuilder}, but makes fewer assumptions about | |
39 * what the compiler interface provides. It builds all basic blocks for the control flow graph without requiring the | |
40 * compiler interface to provide a bitmap of the beginning of basic blocks. It makes two linear passes; one over the | |
41 * bytecodes to build block starts and successor lists, and one pass over the block map to build the CFG. | |
42 * | |
43 * Note that the CFG built by this class is <i>not</i> connected to the actual {@code BlockBegin} instances; this class | |
44 * does, however, compute and assign the reverse postorder number of the blocks. This comment needs refinement. (MJJ) | |
45 * | |
46 * <H2>More Details on {@link BlockMap#build}</H2> | |
47 * | |
48 * If the method has any exception handlers the {@linkplain #exceptionMap exception map} will be created (TBD). | |
49 * | |
50 * A {@link BlockBegin} node with the {@link BlockFlag#StandardEntry} flag is created with bytecode index 0. | |
51 * Note this is distinct from the similar {@link BlockBegin} node assigned to {@link IR#startBlock} by | |
52 * {@link GraphBuilder}. | |
53 * | |
54 * The bytecodes are then scanned linearly looking for bytecodes that contain control transfers, e.g., {@code GOTO}, | |
55 * {@code RETURN}, {@code IFGE}, and creating the corresponding entries in {@link #successorMap} and {@link #blockMap}. | |
56 * In addition, if {@link #exceptionMap} is not null, entries are made for any bytecode that can cause an exception. | |
57 * More TBD. | |
58 * | |
59 * Observe that this process finds bytecodes that terminate basic blocks, so the {@link #moveSuccessorLists} method is | |
60 * called to reassign the successors to the {@code BlockBegin} node that actually starts the block. | |
61 * | |
62 * <H3>Example</H3> | |
63 * | |
64 * Consider the following source code: | |
65 * | |
66 * <pre> | |
67 * <code> | |
68 * public static int test(int arg1, int arg2) { | |
69 * int x = 0; | |
70 * while (arg2 > 0) { | |
71 * if (arg1 > 0) { | |
72 * x += 1; | |
73 * } else if (arg1 < 0) { | |
74 * x -= 1; | |
75 * } | |
76 * } | |
77 * return x; | |
78 * } | |
79 * </code> | |
80 * </pre> | |
81 * | |
82 * This is translated by javac to the following bytecode: | |
83 * | |
84 * <pre> | |
85 * <code> | |
86 * 0: iconst_0 | |
87 * 1: istore_2 | |
88 * 2: goto 22 | |
89 * 5: iload_0 | |
90 * 6: ifle 15 | |
91 * 9: iinc 2, 1 | |
92 * 12: goto 22 | |
93 * 15: iload_0 | |
94 * 16: ifge 22 | |
95 * 19: iinc 2, -1 | |
96 * 22: iload_1 | |
97 * 23: ifgt 5 | |
98 * 26: iload_2 | |
99 * 27: ireturn | |
100 * </code> | |
101 * </pre> | |
102 * | |
103 * There are seven basic blocks in this method, 0..2, 5..6, 9..12, 15..16, 19..19, 22..23 and 26..27. Therefore, before | |
104 * the call to {@code moveSuccessorLists}, the {@code blockMap} array has {@code BlockBegin} nodes at indices 0, 5, 9, | |
105 * 15, 19, 22 and 26. The {@code successorMap} array has entries at 2, 6, 12, 16, 23, 27 corresponding to the control | |
106 * transfer bytecodes. The entry at index 6, for example, is a length two array of {@code BlockBegin} nodes for indices | |
107 * 9 and 15, which are the successors for the basic block 5..6. After the call to {@code moveSuccessors}, {@code | |
108 * successorMap} has entries at 0, 5, 9, 15, 19, 22 and 26, i.e, matching {@code blockMap}. | |
109 * <p> | |
110 * Next the blocks are numbered using <a href="http://en.wikipedia.org/wiki/Depth-first_search#Vertex_orderings">reverse | |
111 * post-order</a>. For the above example this results in the numbering 2, 4, 7, 5, 6, 3, 8. Also loop header blocks are | |
112 * detected during the traversal by detecting a repeat visit to a block that is still being processed. This causes the | |
113 * block to be flagged as a loop header and also added to the {@link #loopBlocks} list. The {@code loopBlocks} list | |
114 * contains the blocks at 0, 5, 9, 15, 19, 22, with 22 as the loop header. (N.B. the loop header block is added multiple | |
115 * (4) times to this list). (Should 0 be in? It's not inside the loop). | |
116 * | |
117 * If the {@code computeStoresInLoops} argument to {@code build} is true, the {@code loopBlocks} list is processed to | |
118 * mark all local variables that are stored in the blocks in the list. | |
119 * | |
120 * @author Ben L. Titzer | |
121 */ | |
122 public final class BlockMap { | |
123 | |
124 private static final BlockBegin[] NONE = {}; | |
125 private static final List<BlockBegin> NONE_LIST = Collections.emptyList(); | |
126 | |
127 /** | |
128 * The {@code ExceptionMap} class is used internally to track exception handlers | |
129 * while iterating over the bytecode and the control flow graph. Since methods with | |
130 * exception handlers are much less frequent than those without, the common case | |
131 * does not need to construct an exception map. | |
132 */ | |
133 private class ExceptionMap { | |
134 private final CiBitMap canTrap; | |
135 private final boolean isObjectInit; | |
136 private final RiExceptionHandler[] allHandlers; | |
137 private final ArrayMap<HashSet<BlockBegin>> handlerMap; | |
138 | |
139 ExceptionMap(RiMethod method, byte[] code) { | |
140 canTrap = new CiBitMap(code.length); | |
141 isObjectInit = C1XIntrinsic.getIntrinsic(method) == C1XIntrinsic.java_lang_Object$init; | |
142 allHandlers = method.exceptionHandlers(); | |
143 handlerMap = new ArrayMap<HashSet<BlockBegin>>(firstBlock, firstBlock + code.length / 5); | |
144 } | |
145 | |
146 void setCanTrap(int bci) { | |
147 canTrap.set(bci); | |
148 } | |
149 | |
150 void addHandlers(BlockBegin block, int bci) { | |
151 if (canTrap.get(bci)) { | |
152 // XXX: replace with faster algorithm (sort exception handlers by start and end) | |
153 for (RiExceptionHandler h : allHandlers) { | |
154 if (h.startBCI() <= bci && bci < h.endBCI()) { | |
155 addHandler(block, get(h.handlerBCI())); | |
156 if (h.isCatchAll()) { | |
157 break; | |
158 } | |
159 } | |
160 } | |
161 } | |
162 } | |
163 | |
164 Collection<BlockBegin> getHandlers(BlockBegin block) { | |
165 // lookup handlers for the basic block | |
166 HashSet<BlockBegin> set = handlerMap.get(block.blockID); | |
167 return set == null ? NONE_LIST : set; | |
168 } | |
169 | |
170 void setHandlerEntrypoints() { | |
171 // start basic blocks at all exception handler blocks and mark them as exception entries | |
172 for (RiExceptionHandler h : allHandlers) { | |
173 addEntrypoint(h.handlerBCI(), BlockBegin.BlockFlag.ExceptionEntry); | |
174 } | |
175 } | |
176 | |
177 void addHandler(BlockBegin block, BlockBegin handler) { | |
178 // add a handler to a basic block, creating the set if necessary | |
179 HashSet<BlockBegin> set = handlerMap.get(block.blockID); | |
180 if (set == null) { | |
181 set = new HashSet<BlockBegin>(); | |
182 handlerMap.put(block.blockID, set); | |
183 } | |
184 set.add(handler); | |
185 } | |
186 } | |
187 | |
188 /** The bytecodes for the associated method. */ | |
189 private final byte[] code; | |
190 | |
191 /** | |
192 * Every {@link BlockBegin} node created by {@link BlockMap#build} has an entry in this | |
193 * array at the corresponding bytecode index. Length is same as {@link BlockMap#code}. | |
194 */ | |
195 private final BlockBegin[] blockMap; | |
196 | |
197 /** | |
198 * A bit map covering the locals with a bit set for each local that is | |
199 * stored to within a loop. This may be conservative depending on the value | |
200 * of the {@code computeStoresInLoops} parameters of {@link #build(boolean)}. | |
201 */ | |
202 private final CiBitMap storesInLoops; | |
203 | |
204 /** | |
205 * Every bytecode instruction that has zero, one or more successor nodes (e.g. {@link Bytecodes#GOTO} has one) has | |
206 * an entry in this array at the corresponding bytecode index. The value is another array of {@code BlockBegin} nodes, | |
207 * with length equal to the number of successors, whose entries are the {@code BlockBegin} nodes for the successor | |
208 * blocks. Length is same as {@link BlockMap#code}. | |
209 */ | |
210 private BlockBegin[][] successorMap; | |
211 | |
212 /** List of {@code BlockBegin} nodes that are inside loops. */ | |
213 private ArrayList<BlockBegin> loopBlocks; | |
214 private ExceptionMap exceptionMap; | |
215 | |
216 /** | |
217 * The first block number allocated for the blocks within this block map. | |
218 */ | |
219 private final int firstBlock; | |
220 | |
221 /** | |
222 * Used for initial block ID (count up) and post-order number (count down). | |
223 */ | |
224 private int blockNum; | |
225 | |
226 /** | |
227 * Creates a new BlockMap instance from bytecode of the given method . | |
228 * @param method the compiler interface method containing the code | |
229 * @param firstBlockNum the first block number to use when creating {@link BlockBegin} nodes | |
230 */ | |
231 public BlockMap(RiMethod method, int firstBlockNum) { | |
232 byte[] code = method.code(); | |
233 this.code = code; | |
234 firstBlock = firstBlockNum; | |
235 blockNum = firstBlockNum; | |
236 blockMap = new BlockBegin[code.length]; | |
237 successorMap = new BlockBegin[code.length][]; | |
238 storesInLoops = new CiBitMap(method.maxLocals()); | |
239 if (method.exceptionHandlers().length != 0) { | |
240 exceptionMap = new ExceptionMap(method, code); | |
241 } | |
242 } | |
243 | |
244 /** | |
245 * Add an entrypoint to this BlockMap. The resulting block will be marked | |
246 * with the specified block flags. | |
247 * @param bci the bytecode index of the start of the block | |
248 * @param entryFlag the entry flag to mark the block with | |
249 */ | |
250 public void addEntrypoint(int bci, BlockBegin.BlockFlag entryFlag) { | |
251 make(bci).setBlockFlag(entryFlag); | |
252 } | |
253 | |
254 /** | |
255 * Gets the block that begins at the specified bytecode index. | |
256 * @param bci the bytecode index of the start of the block | |
257 * @return the block starting at the specified index, if it exists; {@code null} otherwise | |
258 */ | |
259 public BlockBegin get(int bci) { | |
260 if (bci < blockMap.length) { | |
261 return blockMap[bci]; | |
262 } | |
263 return null; | |
264 } | |
265 | |
266 BlockBegin make(int bci) { | |
267 BlockBegin block = blockMap[bci]; | |
268 if (block == null) { | |
269 block = new BlockBegin(bci, blockNum++); | |
270 blockMap[bci] = block; | |
271 } | |
272 return block; | |
273 } | |
274 | |
275 /** | |
276 * Gets a conservative approximation of the successors of a given block. | |
277 * @param block the block for which to get the successors | |
278 * @return an array of the successors of the specified block | |
279 */ | |
280 public BlockBegin[] getSuccessors(BlockBegin block) { | |
281 BlockBegin[] succ = successorMap[block.bci()]; | |
282 return succ == null ? NONE : succ; | |
283 } | |
284 | |
285 /** | |
286 * Gets the exception handlers for a specified block. Note that this | |
287 * set of exception handlers takes into account whether the block contains | |
288 * bytecodes that can cause traps or not. | |
289 * @param block the block for which to get the exception handlers | |
290 * @return an array of the blocks which represent exception handlers; a zero-length | |
291 * array of blocks if there are no handlers that cover any potentially trapping | |
292 * instruction in the specified block | |
293 */ | |
294 public Collection<BlockBegin> getHandlers(BlockBegin block) { | |
295 if (exceptionMap == null) { | |
296 return NONE_LIST; | |
297 } | |
298 return exceptionMap.getHandlers(block); | |
299 } | |
300 | |
301 /** | |
302 * Builds the block map and conservative CFG and numbers blocks. | |
303 * @param computeStoresInLoops {@code true} if the block map builder should | |
304 * make a second pass over the bytecodes for blocks in loops | |
305 * @return {@code true} if the block map was built successfully; {@code false} otherwise | |
306 */ | |
307 public boolean build(boolean computeStoresInLoops) { | |
308 if (exceptionMap != null) { | |
309 exceptionMap.setHandlerEntrypoints(); | |
310 } | |
311 iterateOverBytecodes(); | |
312 moveSuccessorLists(); | |
313 computeBlockNumbers(); | |
314 if (computeStoresInLoops) { | |
315 // process any blocks in loops to compute their stores | |
316 // (requires another pass, but produces fewer phi's and ultimately better code) | |
317 processLoopBlocks(); | |
318 } else { | |
319 // be conservative and assume all locals are potentially stored in loops | |
320 // (does not require another pass, but produces more phi's and worse code) | |
321 storesInLoops.setAll(); | |
322 } | |
323 return true; // XXX: what bailout conditions should the BlockMap check? | |
324 } | |
325 | |
326 /** | |
327 * Cleans up any internal state not necessary after the initial pass. Note that | |
328 * this method discards the conservative CFG edges and only retains the block mapping | |
329 * and stores in loops. | |
330 */ | |
331 public void cleanup() { | |
332 // discard internal state no longer needed | |
333 successorMap = null; | |
334 loopBlocks = null; | |
335 exceptionMap = null; | |
336 } | |
337 | |
338 /** | |
339 * Gets the number of blocks in this block map. | |
340 * @return the number of blocks | |
341 */ | |
342 public int numberOfBlocks() { | |
343 return blockNum - firstBlock; | |
344 } | |
345 | |
346 public int numberOfBytes() { | |
347 return code.length; | |
348 } | |
349 | |
350 /** | |
351 * Gets the bitmap that indicates which local variables are assigned in loops. | |
352 * @return a bitmap which indicates the locals stored in loops | |
353 */ | |
354 public CiBitMap getStoresInLoops() { | |
355 return storesInLoops; | |
356 } | |
357 | |
358 void iterateOverBytecodes() { | |
359 // iterate over the bytecodes top to bottom. | |
360 // mark the entrypoints of basic blocks and build lists of successors for | |
361 // all bytecodes that end basic blocks (i.e. goto, ifs, switches, throw, jsr, returns, ret) | |
362 int bci = 0; | |
363 ExceptionMap exceptionMap = this.exceptionMap; | |
364 byte[] code = this.code; | |
365 make(0).setStandardEntry(); | |
366 while (bci < code.length) { | |
367 int opcode = Bytes.beU1(code, bci); | |
368 switch (opcode) { | |
369 case ATHROW: | |
370 if (exceptionMap != null) { | |
371 exceptionMap.setCanTrap(bci); | |
372 } | |
373 // fall through | |
374 case IRETURN: // fall through | |
375 case LRETURN: // fall through | |
376 case FRETURN: // fall through | |
377 case DRETURN: // fall through | |
378 case ARETURN: // fall through | |
379 case WRETURN: // fall through | |
380 case RETURN: | |
381 if (exceptionMap != null && exceptionMap.isObjectInit) { | |
382 exceptionMap.setCanTrap(bci); | |
383 } | |
384 successorMap[bci] = NONE; // end of control flow | |
385 bci += 1; // these are all 1 byte opcodes | |
386 break; | |
387 | |
388 case RET: | |
389 successorMap[bci] = NONE; // end of control flow | |
390 bci += 2; // ret is 2 bytes | |
391 break; | |
392 | |
393 case IFEQ: // fall through | |
394 case IFNE: // fall through | |
395 case IFLT: // fall through | |
396 case IFGE: // fall through | |
397 case IFGT: // fall through | |
398 case IFLE: // fall through | |
399 case IF_ICMPEQ: // fall through | |
400 case IF_ICMPNE: // fall through | |
401 case IF_ICMPLT: // fall through | |
402 case IF_ICMPGE: // fall through | |
403 case IF_ICMPGT: // fall through | |
404 case IF_ICMPLE: // fall through | |
405 case IF_ACMPEQ: // fall through | |
406 case IF_ACMPNE: // fall through | |
407 case IFNULL: // fall through | |
408 case IFNONNULL: { | |
409 succ2(bci, bci + 3, bci + Bytes.beS2(code, bci + 1)); | |
410 bci += 3; // these are all 3 byte opcodes | |
411 break; | |
412 } | |
413 | |
414 case GOTO: { | |
415 succ1(bci, bci + Bytes.beS2(code, bci + 1)); | |
416 bci += 3; // goto is 3 bytes | |
417 break; | |
418 } | |
419 | |
420 case GOTO_W: { | |
421 succ1(bci, bci + Bytes.beS4(code, bci + 1)); | |
422 bci += 5; // goto_w is 5 bytes | |
423 break; | |
424 } | |
425 | |
426 case JSR: { | |
427 int target = bci + Bytes.beS2(code, bci + 1); | |
428 succ2(bci, bci + 3, target); // make JSR's a successor or not? | |
429 addEntrypoint(target, BlockBegin.BlockFlag.SubroutineEntry); | |
430 bci += 3; // jsr is 3 bytes | |
431 break; | |
432 } | |
433 | |
434 case JSR_W: { | |
435 int target = bci + Bytes.beS4(code, bci + 1); | |
436 succ2(bci, bci + 5, target); | |
437 addEntrypoint(target, BlockBegin.BlockFlag.SubroutineEntry); | |
438 bci += 5; // jsr_w is 5 bytes | |
439 break; | |
440 } | |
441 | |
442 case TABLESWITCH: { | |
443 BytecodeSwitch sw = new BytecodeTableSwitch(code, bci); | |
444 makeSwitchSuccessors(bci, sw); | |
445 bci += sw.size(); | |
446 break; | |
447 } | |
448 | |
449 case LOOKUPSWITCH: { | |
450 BytecodeSwitch sw = new BytecodeLookupSwitch(code, bci); | |
451 makeSwitchSuccessors(bci, sw); | |
452 bci += sw.size(); | |
453 break; | |
454 } | |
455 case WIDE: { | |
456 bci += lengthOf(code, bci); | |
457 break; | |
458 } | |
459 | |
460 default: { | |
461 if (exceptionMap != null && canTrap(opcode)) { | |
462 exceptionMap.setCanTrap(bci); | |
463 } | |
464 bci += lengthOf(opcode); // all variable length instructions are handled above | |
465 } | |
466 } | |
467 } | |
468 } | |
469 | |
470 private void makeSwitchSuccessors(int bci, BytecodeSwitch tswitch) { | |
471 // make a list of all the successors of a switch | |
472 int max = tswitch.numberOfCases(); | |
473 ArrayList<BlockBegin> list = new ArrayList<BlockBegin>(max + 1); | |
474 for (int i = 0; i < max; i++) { | |
475 list.add(make(tswitch.targetAt(i))); | |
476 } | |
477 list.add(make(tswitch.defaultTarget())); | |
478 successorMap[bci] = list.toArray(new BlockBegin[list.size()]); | |
479 } | |
480 | |
481 private void moveSuccessorLists() { | |
482 // move successor lists from the block-ending bytecodes that created them | |
483 // to the basic blocks which they end. | |
484 // also handle fall-through cases from backwards branches into the middle of a block | |
485 // add exception handlers to basic blocks | |
486 BlockBegin current = get(0); | |
487 ExceptionMap exceptionMap = this.exceptionMap; | |
488 for (int bci = 0; bci < blockMap.length; bci++) { | |
489 BlockBegin next = blockMap[bci]; | |
490 if (next != null && next != current) { | |
491 if (current != null) { | |
492 // add fall through successor to current block | |
493 successorMap[current.bci()] = new BlockBegin[] {next}; | |
494 } | |
495 current = next; | |
496 } | |
497 if (exceptionMap != null) { | |
498 exceptionMap.addHandlers(current, bci); | |
499 } | |
500 BlockBegin[] succ = successorMap[bci]; | |
501 if (succ != null && current != null) { | |
502 // move this successor list to current block | |
503 successorMap[bci] = null; | |
504 successorMap[current.bci()] = succ; | |
505 current = null; | |
506 } | |
507 } | |
508 assert current == null : "fell off end of code, should end with successor list"; | |
509 } | |
510 | |
511 private void computeBlockNumbers() { | |
512 // compute the block number for all blocks | |
513 int blockNum = this.blockNum; | |
514 int numBlocks = blockNum - firstBlock; | |
515 numberBlock(get(0), new CiBitMap(numBlocks), new CiBitMap(numBlocks)); | |
516 this.blockNum = blockNum; // _blockNum is used to compute the number of blocks later | |
517 } | |
518 | |
519 private boolean numberBlock(BlockBegin block, CiBitMap visited, CiBitMap active) { | |
520 // number a block with its reverse post-order traversal number | |
521 int blockIndex = block.blockID - firstBlock; | |
522 | |
523 if (visited.get(blockIndex)) { | |
524 if (active.get(blockIndex)) { | |
525 // reached block via backward branch | |
526 block.setParserLoopHeader(true); | |
527 addLoopBlock(block); | |
528 return true; | |
529 } | |
530 // return whether the block is already a loop header | |
531 return block.isParserLoopHeader(); | |
532 } | |
533 | |
534 visited.set(blockIndex); | |
535 active.set(blockIndex); | |
536 | |
537 boolean inLoop = false; | |
538 for (BlockBegin succ : getSuccessors(block)) { | |
539 // recursively process successors | |
540 inLoop |= numberBlock(succ, visited, active); | |
541 } | |
542 if (exceptionMap != null) { | |
543 for (BlockBegin succ : exceptionMap.getHandlers(block)) { | |
544 // process exception handler blocks | |
545 inLoop |= numberBlock(succ, visited, active); | |
546 } | |
547 } | |
548 // clear active bit after successors are processed | |
549 active.clear(blockIndex); | |
550 block.setDepthFirstNumber(blockNum--); | |
551 if (inLoop) { | |
552 addLoopBlock(block); | |
553 } | |
554 | |
555 return inLoop; | |
556 } | |
557 | |
558 private void addLoopBlock(BlockBegin block) { | |
559 if (loopBlocks == null) { | |
560 loopBlocks = new ArrayList<BlockBegin>(); | |
561 } | |
562 loopBlocks.add(block); | |
563 } | |
564 | |
565 private void processLoopBlocks() { | |
566 if (loopBlocks == null) { | |
567 return; | |
568 } | |
569 for (BlockBegin block : loopBlocks) { | |
570 // process all the stores in this block | |
571 int bci = block.bci(); | |
572 byte[] code = this.code; | |
573 while (true) { | |
574 // iterate over the bytecodes in this block | |
575 int opcode = code[bci] & 0xff; | |
576 if (opcode == WIDE) { | |
577 bci += processWideStore(code[bci + 1] & 0xff, code, bci); | |
578 } else if (isStore(opcode)) { | |
579 bci += processStore(opcode, code, bci); | |
580 } else { | |
581 bci += lengthOf(code, bci); | |
582 } | |
583 if (bci >= code.length || blockMap[bci] != null) { | |
584 // stop when we reach the next block | |
585 break; | |
586 } | |
587 } | |
588 } | |
589 } | |
590 | |
591 private int processWideStore(int opcode, byte[] code, int bci) { | |
592 switch (opcode) { | |
593 case IINC: storeOne(Bytes.beU2(code, bci + 2)); return 6; | |
594 case ISTORE: storeOne(Bytes.beU2(code, bci + 2)); return 3; | |
595 case LSTORE: storeTwo(Bytes.beU2(code, bci + 2)); return 3; | |
596 case FSTORE: storeOne(Bytes.beU2(code, bci + 2)); return 3; | |
597 case DSTORE: storeTwo(Bytes.beU2(code, bci + 2)); return 3; | |
598 case ASTORE: storeOne(Bytes.beU2(code, bci + 2)); return 3; | |
599 } | |
600 return lengthOf(code, bci); | |
601 } | |
602 | |
603 private int processStore(int opcode, byte[] code, int bci) { | |
604 switch (opcode) { | |
605 case IINC: storeOne(code[bci + 1] & 0xff); return 3; | |
606 case ISTORE: storeOne(code[bci + 1] & 0xff); return 2; | |
607 case LSTORE: storeTwo(code[bci + 1] & 0xff); return 2; | |
608 case FSTORE: storeOne(code[bci + 1] & 0xff); return 2; | |
609 case DSTORE: storeTwo(code[bci + 1] & 0xff); return 2; | |
610 case WSTORE: | |
611 case ASTORE: storeOne(code[bci + 1] & 0xff); return 2; | |
612 case ISTORE_0: // fall through | |
613 case ISTORE_1: // fall through | |
614 case ISTORE_2: // fall through | |
615 case ISTORE_3: storeOne(opcode - ISTORE_0); return 1; | |
616 case LSTORE_0: // fall through | |
617 case LSTORE_1: // fall through | |
618 case LSTORE_2: // fall through | |
619 case LSTORE_3: storeTwo(opcode - LSTORE_0); return 1; | |
620 case FSTORE_0: // fall through | |
621 case FSTORE_1: // fall through | |
622 case FSTORE_2: // fall through | |
623 case FSTORE_3: storeOne(opcode - FSTORE_0); return 1; | |
624 case DSTORE_0: // fall through | |
625 case DSTORE_1: // fall through | |
626 case DSTORE_2: // fall through | |
627 case DSTORE_3: storeTwo(opcode - DSTORE_0); return 1; | |
628 case ASTORE_0: // fall through | |
629 case ASTORE_1: // fall through | |
630 case ASTORE_2: // fall through | |
631 case ASTORE_3: storeOne(opcode - ASTORE_0); return 1; | |
632 case WSTORE_0: // fall through | |
633 case WSTORE_1: // fall through | |
634 case WSTORE_2: // fall through | |
635 case WSTORE_3: storeOne(opcode - WSTORE_0); return 1; | |
636 } | |
637 throw Util.shouldNotReachHere(); | |
638 } | |
639 | |
640 private void storeOne(int local) { | |
641 storesInLoops.set(local); | |
642 } | |
643 | |
644 private void storeTwo(int local) { | |
645 storesInLoops.set(local); | |
646 storesInLoops.set(local + 1); | |
647 } | |
648 | |
649 private void succ2(int bci, int s1, int s2) { | |
650 successorMap[bci] = new BlockBegin[] {make(s1), make(s2)}; | |
651 } | |
652 | |
653 private void succ1(int bci, int s1) { | |
654 successorMap[bci] = new BlockBegin[] {make(s1)}; | |
655 } | |
656 | |
657 private static StringBuilder append(StringBuilder sb, BlockBegin block) { | |
658 return sb.append('B').append(block.blockID).append('@').append(block.bci()); | |
659 } | |
660 | |
661 @Override | |
662 public String toString() { | |
663 StringBuilder sb = new StringBuilder(); | |
664 for (int bci = 0; bci < blockMap.length; ++bci) { | |
665 BlockBegin block = blockMap[bci]; | |
666 if (block != null) { | |
667 append(sb, block); | |
668 if (loopBlocks != null && loopBlocks.contains(block)) { | |
669 sb.append("{loop-header}"); | |
670 } | |
671 if (successorMap != null) { | |
672 BlockBegin[] succs = successorMap[bci]; | |
673 if (succs != null && succs.length > 0) { | |
674 sb.append(" ->"); | |
675 for (BlockBegin succ : succs) { | |
676 append(sb.append(' '), succ); | |
677 } | |
678 } | |
679 } | |
680 Collection<BlockBegin> handlers = getHandlers(block); | |
681 if (!handlers.isEmpty()) { | |
682 sb.append(" xhandlers{"); | |
683 for (BlockBegin h : handlers) { | |
684 append(sb, h).append(' '); | |
685 } | |
686 sb.append('}'); | |
687 } | |
688 sb.append(String.format("%n")); | |
689 } | |
690 } | |
691 return sb.toString(); | |
692 } | |
693 } |