Mercurial > hg > graal-compiler

comparison graal/GraalCompiler/src/com/sun/c1x/graph/BlockMap.java @ 2675:bcd20d26d52d

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Refactoring of BlockMap so that it doesn't create BlockBegin objects, but maintains its own Block data structure
author Christian.Wimmer@Oracle.com
date Fri, 13 May 2011 13:59:32 -0700
parents ce054e34fbaf
children bcbda467e1ae
comparison
equal deleted inserted replaced
2672:35453d725a2a 2675:bcd20d26d52d
24 24
25 import static com.sun.cri.bytecode.Bytecodes.*; 25 import static com.sun.cri.bytecode.Bytecodes.*;
26 26
27 import java.util.*; 27 import java.util.*;
28 28
29 import com.oracle.graal.graph.*; 29 import com.sun.c1x.debug.*;
30 import com.sun.c1x.ir.*;
31 import com.sun.c1x.util.*;
32 import com.sun.cri.bytecode.*; 30 import com.sun.cri.bytecode.*;
33 import com.sun.cri.ci.*; 31 import com.sun.cri.ci.*;
34 import com.sun.cri.ri.*; 32 import com.sun.cri.ri.*;
35 33
36 /** 34 /**
112 * 110 *
113 * If the {@code computeStoresInLoops} argument to {@code build} is true, the {@code loopBlocks} list is processed to 111 * If the {@code computeStoresInLoops} argument to {@code build} is true, the {@code loopBlocks} list is processed to
114 * mark all local variables that are stored in the blocks in the list. 112 * mark all local variables that are stored in the blocks in the list.
115 */ 113 */
116 public final class BlockMap { 114 public final class BlockMap {
117 115 public class Block {
118 private static final BlockBegin[] NONE = {}; 116 public int startBci;
119 private static final List<BlockBegin> NONE_LIST = Collections.emptyList(); 117 public int endBci;
120 118 public boolean isExceptionEntry;
121 /** 119 public boolean isLoopHeader;
122 * The {@code ExceptionMap} class is used internally to track exception handlers 120
123 * while iterating over the bytecode and the control flow graph. Since methods with 121 private Block[] successors;
124 * exception handlers are much less frequent than those without, the common case 122 private boolean visited;
125 * does not need to construct an exception map. 123 private boolean active;
126 */ 124 private int loops;
127 private class ExceptionMap { 125 }
128 private final CiBitMap canTrap; 126
129 private final boolean isObjectInit; 127 private static final Block[] NO_SUCCESSORS = new Block[0];
130 private final RiExceptionHandler[] allHandlers; 128
131 private final ArrayMap<HashSet<BlockBegin>> handlerMap; 129 /**
132 130 * The blocks found in this method, in reverse postorder.
133 ExceptionMap(RiMethod method, byte[] code) { 131 */
134 canTrap = new CiBitMap(code.length); 132 public final List<Block> blocks;
135 isObjectInit = (method.isConstructor() && method.holder().superType() == null); 133
136 allHandlers = method.exceptionHandlers(); 134 /**
137 handlerMap = new ArrayMap<HashSet<BlockBegin>>(firstBlock, firstBlock + code.length / 5); 135 * A bit map covering the locals with a bit set for each local that might be stored to within a
138 } 136 * loop. If the bit is cleared, it is guaranteed that the local is never stored in a loop.
139 137 */
140 void setCanTrap(int bci) { 138 public final BitSet storesInLoops;
141 canTrap.set(bci); 139
142 } 140 private final RiMethod method;
143 141
144 void addHandlers(BlockBegin block, int bci) { 142 private Block[] blockMap;
145 if (canTrap.get(bci)) { 143
146 // XXX: replace with faster algorithm (sort exception handlers by start and end) 144 private BitSet canTrap;
147 for (RiExceptionHandler h : allHandlers) {
148 if (h.startBCI() <= bci && bci < h.endBCI()) {
149 addHandler(block, get(h.handlerBCI()));
150 if (h.isCatchAll()) {
151 break;
152 }
153 }
154 }
155 }
156 }
157
158 Collection<BlockBegin> getHandlers(BlockBegin block) {
159 // lookup handlers for the basic block
160 HashSet<BlockBegin> set = handlerMap.get(block.blockID);
161 return set == null ? NONE_LIST : set;
162 }
163
164 void setHandlerEntrypoints() {
165 // start basic blocks at all exception handler blocks and mark them as exception entries
166 for (RiExceptionHandler h : allHandlers) {
167 addEntrypoint(h.handlerBCI(), BlockBegin.BlockFlag.ExceptionEntry);
168 }
169 }
170
171 void addHandler(BlockBegin block, BlockBegin handler) {
172 // add a handler to a basic block, creating the set if necessary
173 HashSet<BlockBegin> set = handlerMap.get(block.blockID);
174 if (set == null) {
175 set = new HashSet<BlockBegin>();
176 handlerMap.put(block.blockID, set);
177 }
178 set.add(handler);
179 }
180 }
181
182 /** The bytecodes for the associated method. */
183 private final byte[] code;
184
185 /**
186 * Every {@link BlockBegin} node created by {@link BlockMap#build} has an entry in this
187 * array at the corresponding bytecode index. Length is same as {@link BlockMap#code}.
188 */
189 private final BlockBegin[] blockMap;
190
191 /**
192 * A bit map covering the locals with a bit set for each local that is
193 * stored to within a loop. This may be conservative depending on the value
194 * of the {@code computeStoresInLoops} parameters of {@link #build(boolean)}.
195 */
196 private final CiBitMap storesInLoops;
197
198 /**
199 * Every bytecode instruction that has zero, one or more successor nodes (e.g. {@link Bytecodes#GOTO} has one) has
200 * an entry in this array at the corresponding bytecode index. The value is another array of {@code BlockBegin} nodes,
201 * with length equal to the number of successors, whose entries are the {@code BlockBegin} nodes for the successor
202 * blocks. Length is same as {@link BlockMap#code}.
203 */
204 private BlockBegin[][] successorMap;
205
206 /** List of {@code BlockBegin} nodes that are inside loops. */
207 private ArrayList<BlockBegin> loopBlocks;
208 private ExceptionMap exceptionMap;
209
210 /**
211 * The first block number allocated for the blocks within this block map.
212 */
213 private final int firstBlock;
214
215 /**
216 * Used for initial block ID (count up) and post-order number (count down).
217 */
218 private int blockNum;
219
220 private final Graph graph;
221 145
222 /** 146 /**
223 * Creates a new BlockMap instance from bytecode of the given method . 147 * Creates a new BlockMap instance from bytecode of the given method .
224 * @param method the compiler interface method containing the code 148 * @param method the compiler interface method containing the code
225 * @param firstBlockNum the first block number to use when creating {@link BlockBegin} nodes 149 */
226 * @param graph 150 public BlockMap(RiMethod method) {
227 */ 151 this.method = method;
228 public BlockMap(RiMethod method, int firstBlockNum, Graph graph) { 152 this.blockMap = new Block[method.code().length];
229 this.graph = graph;
230 byte[] code = method.code();
231 this.code = code;
232 firstBlock = firstBlockNum;
233 blockNum = firstBlockNum;
234 blockMap = new BlockBegin[code.length];
235 successorMap = new BlockBegin[code.length][];
236 storesInLoops = new CiBitMap(method.maxLocals());
237 if (method.exceptionHandlers().length != 0) { 153 if (method.exceptionHandlers().length != 0) {
238 exceptionMap = new ExceptionMap(method, code); 154 this.canTrap = new BitSet(blockMap.length);
239 } 155 }
240 } 156 this.blocks = new ArrayList<Block>();
241 157 this.storesInLoops = new BitSet(method.maxLocals());
242 /**
243 * Add an entrypoint to this BlockMap. The resulting block will be marked
244 * with the specified block flags.
245 * @param bci the bytecode index of the start of the block
246 * @param entryFlag the entry flag to mark the block with
247 */
248 public void addEntrypoint(int bci, BlockBegin.BlockFlag entryFlag) {
249 make(bci).setBlockFlag(entryFlag);
250 }
251
252 /**
253 * Gets the block that begins at the specified bytecode index.
254 * @param bci the bytecode index of the start of the block
255 * @return the block starting at the specified index, if it exists; {@code null} otherwise
256 */
257 public BlockBegin get(int bci) {
258 if (bci < blockMap.length) {
259 return blockMap[bci];
260 }
261 return null;
262 }
263
264 private BlockBegin make(int bci) {
265 BlockBegin block = blockMap[bci];
266 if (block == null) {
267 block = new BlockBegin(bci, blockNum++, graph);
268 blockMap[bci] = block;
269 }
270 return block;
271 }
272
273 /**
274 * Gets a conservative approximation of the successors of a given block.
275 * @param block the block for which to get the successors
276 * @return an array of the successors of the specified block
277 */
278 public BlockBegin[] getSuccessors(BlockBegin block) {
279 BlockBegin[] succ = successorMap[block.bci()];
280 return succ == null ? NONE : succ;
281 }
282
283 /**
284 * Gets the exception handlers for a specified block. Note that this
285 * set of exception handlers takes into account whether the block contains
286 * bytecodes that can cause traps or not.
287 * @param block the block for which to get the exception handlers
288 * @return an array of the blocks which represent exception handlers; a zero-length
289 * array of blocks if there are no handlers that cover any potentially trapping
290 * instruction in the specified block
291 */
292 public Collection<BlockBegin> getHandlers(BlockBegin block) {
293 if (exceptionMap == null) {
294 return NONE_LIST;
295 }
296 return exceptionMap.getHandlers(block);
297 } 158 }
298 159
299 /** 160 /**
300 * Builds the block map and conservative CFG and numbers blocks. 161 * Builds the block map and conservative CFG and numbers blocks.
301 * @param computeStoresInLoops {@code true} if the block map builder should 162 */
302 * make a second pass over the bytecodes for blocks in loops 163 public void build() {
303 * @return {@code true} if the block map was built successfully; {@code false} otherwise 164 makeExceptionEntries();
304 */
305 public boolean build(boolean computeStoresInLoops) {
306 if (exceptionMap != null) {
307 exceptionMap.setHandlerEntrypoints();
308 }
309 iterateOverBytecodes(); 165 iterateOverBytecodes();
310 moveSuccessorLists(); 166 addExceptionEdges();
311 computeBlockNumbers(); 167 computeBlockOrder();
312 if (computeStoresInLoops) { 168
313 // process any blocks in loops to compute their stores 169 // Discard big arrays so that they can be GCed
314 // (requires another pass, but produces fewer phi's and ultimately better code) 170 blockMap = null;
315 processLoopBlocks(); 171 canTrap = null;
316 } else { 172 }
317 // be conservative and assume all locals are potentially stored in loops 173
318 // (does not require another pass, but produces more phi's and worse code) 174 private void makeExceptionEntries() {
319 storesInLoops.setAll(); 175 // start basic blocks at all exception handler blocks and mark them as exception entries
320 } 176 for (RiExceptionHandler h : method.exceptionHandlers()) {
321 return true; // XXX: what bailout conditions should the BlockMap check? 177 Block xhandler = makeBlock(h.handlerBCI());
322 } 178 xhandler.isExceptionEntry = true;
323 179 }
324 /** 180 }
325 * Cleans up any internal state not necessary after the initial pass. Note that 181
326 * this method discards the conservative CFG edges and only retains the block mapping 182 private void iterateOverBytecodes() {
327 * and stores in loops.
328 */
329 public void cleanup() {
330 // discard internal state no longer needed
331 successorMap = null;
332 loopBlocks = null;
333 exceptionMap = null;
334 }
335
336 /**
337 * Gets the number of blocks in this block map.
338 * @return the number of blocks
339 */
340 public int numberOfBlocks() {
341 return blockNum - firstBlock;
342 }
343
344 public int numberOfBytes() {
345 return code.length;
346 }
347
348 /**
349 * Gets the bitmap that indicates which local variables are assigned in loops.
350 * @return a bitmap which indicates the locals stored in loops
351 */
352 public CiBitMap getStoresInLoops() {
353 return storesInLoops;
354 }
355
356 void iterateOverBytecodes() {
357 // iterate over the bytecodes top to bottom. 183 // iterate over the bytecodes top to bottom.
358 // mark the entrypoints of basic blocks and build lists of successors for 184 // mark the entrypoints of basic blocks and build lists of successors for
359 // all bytecodes that end basic blocks (i.e. goto, ifs, switches, throw, jsr, returns, ret) 185 // all bytecodes that end basic blocks (i.e. goto, ifs, switches, throw, jsr, returns, ret)
186 byte[] code = method.code();
187 Block current = null;
360 int bci = 0; 188 int bci = 0;
361 ExceptionMap exceptionMap = this.exceptionMap;
362 byte[] code = this.code;
363 make(0);
364 while (bci < code.length) { 189 while (bci < code.length) {
190 if (current == null || blockMap[bci] != null) {
191 Block b = makeBlock(bci);
192 if (current != null) {
193 setSuccessors(current.endBci, b);
194 }
195 current = b;
196 }
197 blockMap[bci] = current;
198 current.endBci = bci;
199
365 int opcode = Bytes.beU1(code, bci); 200 int opcode = Bytes.beU1(code, bci);
366 switch (opcode) { 201 switch (opcode) {
367 case ATHROW:
368 if (exceptionMap != null) {
369 exceptionMap.setCanTrap(bci);
370 }
371 // fall through
372 case IRETURN: // fall through 202 case IRETURN: // fall through
373 case LRETURN: // fall through 203 case LRETURN: // fall through
374 case FRETURN: // fall through 204 case FRETURN: // fall through
375 case DRETURN: // fall through 205 case DRETURN: // fall through
376 case ARETURN: // fall through 206 case ARETURN: // fall through
377 case WRETURN: // fall through 207 case WRETURN: // fall through
378 case RETURN: 208 case RETURN: {
379 if (exceptionMap != null && exceptionMap.isObjectInit) { 209 current = null;
380 exceptionMap.setCanTrap(bci); 210
211 assert lengthOf(code, bci) == 1;
212 bci += 1;
213 break;
214 }
215
216 case ATHROW: {
217 current = null;
218 if (canTrap != null) {
219 canTrap.set(bci);
381 } 220 }
382 successorMap[bci] = NONE; // end of control flow 221
383 bci += 1; // these are all 1 byte opcodes 222 assert lengthOf(code, bci) == 1;
384 break; 223 bci += 1;
385 224 break;
386 case RET: 225 }
387 successorMap[bci] = NONE; // end of control flow
388 bci += 2; // ret is 2 bytes
389 break;
390 226
391 case IFEQ: // fall through 227 case IFEQ: // fall through
392 case IFNE: // fall through 228 case IFNE: // fall through
393 case IFLT: // fall through 229 case IFLT: // fall through
394 case IFGE: // fall through 230 case IFGE: // fall through
402 case IF_ICMPLE: // fall through 238 case IF_ICMPLE: // fall through
403 case IF_ACMPEQ: // fall through 239 case IF_ACMPEQ: // fall through
404 case IF_ACMPNE: // fall through 240 case IF_ACMPNE: // fall through
405 case IFNULL: // fall through 241 case IFNULL: // fall through
406 case IFNONNULL: { 242 case IFNONNULL: {
407 succ2(bci, bci + 3, bci + Bytes.beS2(code, bci + 1)); 243 current = null;
408 bci += 3; // these are all 3 byte opcodes 244 Block b1 = makeBlock(bci + 3);
245 Block b2 = makeBlock(bci + Bytes.beS2(code, bci + 1));
246 setSuccessors(bci, b1, b2);
247
248 assert lengthOf(code, bci) == 3;
249 bci += 3;
409 break; 250 break;
410 } 251 }
411 252
412 case GOTO: { 253 case GOTO: {
413 succ1(bci, bci + Bytes.beS2(code, bci + 1)); 254 current = null;
414 bci += 3; // goto is 3 bytes 255 Block b1 = makeBlock(bci + Bytes.beS2(code, bci + 1));
256 setSuccessors(bci, b1);
257
258 assert lengthOf(code, bci) == 3;
259 bci += 3;
415 break; 260 break;
416 } 261 }
417 262
418 case GOTO_W: { 263 case GOTO_W: {
419 succ1(bci, bci + Bytes.beS4(code, bci + 1)); 264 current = null;
420 bci += 5; // goto_w is 5 bytes 265 Block b1 = makeBlock(bci + Bytes.beS4(code, bci + 1));
266 setSuccessors(bci, b1);
267
268 assert lengthOf(code, bci) == 5;
269 bci += 5;
270 break;
271 }
272
273 case TABLESWITCH: {
274 BytecodeTableSwitch sw = new BytecodeTableSwitch(code, bci);
275 setSuccessors(bci, makeSwitchSuccessors(sw));
276 current = null;
277
278 assert lengthOf(code, bci) == sw.size();
279 bci += sw.size();
280 break;
281 }
282
283 case LOOKUPSWITCH: {
284 current = null;
285 BytecodeLookupSwitch sw = new BytecodeLookupSwitch(code, bci);
286 setSuccessors(bci, makeSwitchSuccessors(sw));
287
288 assert lengthOf(code, bci) == sw.size();
289 bci += sw.size();
421 break; 290 break;
422 } 291 }
423 292
424 case JSR: { 293 case JSR: {
425 int target = bci + Bytes.beS2(code, bci + 1); 294 throw new JSRNotSupportedBailout();
426 succ2(bci, bci + 3, target); // make JSR's a successor or not? 295 }
427 addEntrypoint(target, BlockBegin.BlockFlag.SubroutineEntry);
428 bci += 3; // jsr is 3 bytes
429 break;
430 }
431
432 case JSR_W: { 296 case JSR_W: {
433 int target = bci + Bytes.beS4(code, bci + 1); 297 throw new JSRNotSupportedBailout();
434 succ2(bci, bci + 5, target); 298 }
435 addEntrypoint(target, BlockBegin.BlockFlag.SubroutineEntry); 299 case RET: {
436 bci += 5; // jsr_w is 5 bytes 300 throw new JSRNotSupportedBailout();
437 break; 301 }
438 } 302
439
440 case TABLESWITCH: {
441 BytecodeSwitch sw = new BytecodeTableSwitch(code, bci);
442 makeSwitchSuccessors(bci, sw);
443 bci += sw.size();
444 break;
445 }
446
447 case LOOKUPSWITCH: {
448 BytecodeSwitch sw = new BytecodeLookupSwitch(code, bci);
449 makeSwitchSuccessors(bci, sw);
450 bci += sw.size();
451 break;
452 }
453 case WIDE: { 303 case WIDE: {
304 if (canTrap != null && ProfileInformationStub.trappedFrequently(method, bci)) {
305 canTrap.set(bci);
306 }
307
454 bci += lengthOf(code, bci); 308 bci += lengthOf(code, bci);
455 break; 309 break;
456 } 310 }
457 311
458 default: { 312 default: {
459 if (exceptionMap != null && canTrap(opcode)) { 313 if (canTrap != null && ProfileInformationStub.trappedFrequently(method, bci)) {
460 exceptionMap.setCanTrap(bci); 314 canTrap.set(bci);
461 } 315 }
462 bci += lengthOf(opcode); // all variable length instructions are handled above 316
463 } 317 assert lengthOf(code, bci) == lengthOf(opcode);
464 } 318 bci += lengthOf(opcode);
465 } 319 }
466 } 320 }
467 321 }
468 private void makeSwitchSuccessors(int bci, BytecodeSwitch tswitch) { 322 }
469 // make a list of all the successors of a switch 323
324 private Block makeBlock(int startBci) {
325 Block oldBlock = blockMap[startBci];
326 if (oldBlock == null) {
327 Block newBlock = new Block();
328 newBlock.startBci = startBci;
329 newBlock.successors = NO_SUCCESSORS;
330 blockMap[startBci] = newBlock;
331 return newBlock;
332
333 } else if (oldBlock.startBci != startBci) {
334 // Backward branch into the middle of an already processed block.
335 // Add the correct fall-through successor.
336 Block newBlock = new Block();
337 newBlock.startBci = startBci;
338 newBlock.endBci = oldBlock.endBci;
339 newBlock.successors = oldBlock.successors;
340
341 oldBlock.endBci = startBci - 1;
342 oldBlock.successors = new Block[] {newBlock };
343
344 for (int i = startBci; i <= newBlock.endBci; i++) {
345 blockMap[i] = newBlock;
346 }
347 return newBlock;
348
349 } else {
350 return oldBlock;
351 }
352 }
353
354 private Block[] makeSwitchSuccessors(BytecodeSwitch tswitch) {
470 int max = tswitch.numberOfCases(); 355 int max = tswitch.numberOfCases();
471 ArrayList<BlockBegin> list = new ArrayList<BlockBegin>(max + 1); 356 Block[] successors = new Block[max + 1];
472 for (int i = 0; i < max; i++) { 357 for (int i = 0; i < max; i++) {
473 list.add(make(tswitch.targetAt(i))); 358 successors[i] = makeBlock(tswitch.targetAt(i));
474 } 359 }
475 list.add(make(tswitch.defaultTarget())); 360 successors[max] = makeBlock(tswitch.defaultTarget());
476 successorMap[bci] = list.toArray(new BlockBegin[list.size()]); 361 return successors;
477 } 362 }
478 363
479 private void moveSuccessorLists() { 364 private void setSuccessors(int predBci, Block... successors) {
480 // move successor lists from the block-ending bytecodes that created them 365 for (Block sux : successors) {
481 // to the basic blocks which they end. 366 if (sux.isExceptionEntry) {
482 // also handle fall-through cases from backwards branches into the middle of a block 367 throw new CiBailout("Exception handler can be reached by both normal and exceptional control flow");
483 // add exception handlers to basic blocks 368 }
484 BlockBegin current = get(0); 369 }
485 ExceptionMap exceptionMap = this.exceptionMap; 370 Block predecessor = blockMap[predBci];
486 for (int bci = 0; bci < blockMap.length; bci++) { 371 assert predecessor.successors.length == 0;
487 BlockBegin next = blockMap[bci]; 372 predecessor.successors = successors;
488 if (next != null && next != current) { 373 }
489 if (current != null) { 374
490 // add fall through successor to current block 375 private void addExceptionEdges() {
491 successorMap[current.bci()] = new BlockBegin[] {next}; 376 if (canTrap == null) {
492 }
493 current = next;
494 }
495 if (exceptionMap != null) {
496 exceptionMap.addHandlers(current, bci);
497 }
498 BlockBegin[] succ = successorMap[bci];
499 if (succ != null && current != null) {
500 // move this successor list to current block
501 successorMap[bci] = null;
502 successorMap[current.bci()] = succ;
503 current = null;
504 }
505 }
506 assert current == null : "fell off end of code, should end with successor list";
507 }
508
509 private void computeBlockNumbers() {
510 // compute the block number for all blocks
511 int blockNum = this.blockNum;
512 int numBlocks = blockNum - firstBlock;
513 numberBlock(get(0), new CiBitMap(numBlocks), new CiBitMap(numBlocks));
514 this.blockNum = blockNum; // _blockNum is used to compute the number of blocks later
515 }
516
517 private boolean numberBlock(BlockBegin block, CiBitMap visited, CiBitMap active) {
518 // number a block with its reverse post-order traversal number
519 int blockIndex = block.blockID - firstBlock;
520
521 if (visited.get(blockIndex)) {
522 if (active.get(blockIndex)) {
523 // reached block via backward branch
524 block.setParserLoopHeader(true);
525 addLoopBlock(block);
526 return true;
527 }
528 // return whether the block is already a loop header
529 return block.isParserLoopHeader();
530 }
531
532 visited.set(blockIndex);
533 active.set(blockIndex);
534
535 boolean inLoop = false;
536 for (BlockBegin succ : getSuccessors(block)) {
537 // recursively process successors
538 inLoop |= numberBlock(succ, visited, active);
539 }
540 if (exceptionMap != null) {
541 for (BlockBegin succ : exceptionMap.getHandlers(block)) {
542 // process exception handler blocks
543 inLoop |= numberBlock(succ, visited, active);
544 }
545 }
546 // clear active bit after successors are processed
547 active.clear(blockIndex);
548 block.setDepthFirstNumber(blockNum--);
549 if (inLoop) {
550 addLoopBlock(block);
551 }
552
553 return inLoop;
554 }
555
556 private void addLoopBlock(BlockBegin block) {
557 if (loopBlocks == null) {
558 loopBlocks = new ArrayList<BlockBegin>();
559 }
560 loopBlocks.add(block);
561 }
562
563 private void processLoopBlocks() {
564 if (loopBlocks == null) {
565 return; 377 return;
566 } 378 }
567 for (BlockBegin block : loopBlocks) { 379
568 // process all the stores in this block 380 Block block = null;
569 int bci = block.bci(); 381 HashSet<Block> newSuccessorsOfBlock = new HashSet<Block>();
570 byte[] code = this.code; 382
571 while (true) { 383 for (int bci = canTrap.nextSetBit(0); bci >= 0; bci = canTrap.nextSetBit(bci + 1)) {
572 // iterate over the bytecodes in this block 384 Block newBlock = blockMap[bci];
573 int opcode = code[bci] & 0xff; 385 if (newBlock != block) {
574 if (opcode == WIDE) { 386 if (block != null) {
575 bci += processWideStore(code[bci + 1] & 0xff, code, bci); 387 block.successors = newSuccessorsOfBlock.toArray(new Block[newSuccessorsOfBlock.size()]);
576 } else if (isStore(opcode)) { 388 newSuccessorsOfBlock.clear();
577 bci += processStore(opcode, code, bci); 389 }
578 } else { 390 Collections.addAll(newSuccessorsOfBlock, newBlock.successors);
579 bci += lengthOf(code, bci); 391 }
580 } 392 block = newBlock;
581 if (bci >= code.length || blockMap[bci] != null) { 393
582 // stop when we reach the next block 394 for (RiExceptionHandler h : method.exceptionHandlers()) {
583 break; 395 if (h.startBCI() <= bci && bci < h.endBCI()) {
584 } 396 newSuccessorsOfBlock.add(blockMap[h.handlerBCI()]);
585 } 397 if (h.isCatchAll()) {
586 } 398 break;
587 } 399 }
588 400 }
589 private int processWideStore(int opcode, byte[] code, int bci) { 401 }
402 }
403 if (block != null) {
404 block.successors = newSuccessorsOfBlock.toArray(new Block[newSuccessorsOfBlock.size()]);
405 }
406 }
407
408 private void computeBlockOrder() {
409 int loop = computeBlockOrder(blockMap[0]);
410
411 if (loop != 0) {
412 // There is a path from a loop end to the method entry that does not pass the loop header.
413 // Therefore, the loop is non reducible (has more than one entry).
414 // We don't want to compile such methods because the IR only supports structured loops.
415 throw new CiBailout("Non-reducible loop");
416 }
417
418 // Convert postorder to the desired reverse postorder.
419 Collections.reverse(blocks);
420 }
421
422 /**
423 * The next available loop number.
424 */
425 private int nextLoop = 0;
426
427 /**
428 * Mark the block as a loop header, using the next available loop number.
429 * Also checks for corner cases that we don't want to compile.
430 */
431 private void makeLoopHeader(Block block) {
432 if (!block.isLoopHeader) {
433 block.isLoopHeader = true;
434
435 if (block.isExceptionEntry) {
436 // Loops that are implicitly formed by an exception handler lead to all sorts of corner cases.
437 // Don't compile such methods for now, until we see a concrete case that allows checking for correctness.
438 throw new CiBailout("Loop formed by an exception handler");
439 }
440 if (nextLoop >= Integer.SIZE) {
441 // This restriction can be removed by using a fall-back to a BitSet in case we have more than 32 loops
442 // Don't compile such methods for now, until we see a concrete case that allows checking for correctness.
443 throw new CiBailout("Too many loops in method");
444 }
445
446 assert block.loops == 0;
447 block.loops = 1 << nextLoop;
448 nextLoop++;
449 }
450 assert Integer.bitCount(block.loops) == 1;
451 }
452
453 /**
454 * Depth-first traversal of the control flow graph. The flag {@linkplain Block#visited} is used to
455 * visit every block only once. The flag {@linkplain Block#active} is used to detect cycles (backward
456 * edges).
457 */
458 private int computeBlockOrder(Block block) {
459 if (block.visited) {
460 if (block.active) {
461 // Reached block via backward branch.
462 makeLoopHeader(block);
463 }
464 // Return cached loop information for this block.
465 return block.loops;
466 }
467
468 block.visited = true;
469 block.active = true;
470
471 int loops = 0;
472 for (Block successor : block.successors) {
473 // Recursively process successors.
474 loops |= computeBlockOrder(successor);
475 }
476
477 if (loops != 0) {
478 processLoopBlock(block);
479 }
480 if (block.isLoopHeader) {
481 assert Integer.bitCount(block.loops) == 1;
482 loops &= ~block.loops;
483 }
484
485 block.loops = loops;
486 block.active = false;
487 blocks.add(block);
488
489 return loops;
490 }
491
492 private void processLoopBlock(Block block) {
493 // process all the stores in this block
494 byte[] code = method.code();
495 int bci = block.startBci;
496 while (bci <= block.endBci) {
497 int opcode = Bytes.beU1(code, bci);
498 if (isStore(opcode)) {
499 processStore(opcode, Bytes.beU1(code, bci + 1));
500
501 } else if (opcode == WIDE) {
502 opcode = Bytes.beU1(code, bci + 1);
503 if (isStore(opcode)) {
504 processStore(opcode, Bytes.beU2(code, bci + 2));
505 }
506 }
507 bci += lengthOf(code, bci);
508 }
509 }
510
511 private void processStore(int opcode, int local) {
590 switch (opcode) { 512 switch (opcode) {
591 case IINC: storeOne(Bytes.beU2(code, bci + 2)); return 6; 513 case IINC:
592 case ISTORE: storeOne(Bytes.beU2(code, bci + 2)); return 3; 514 case ISTORE:
593 case LSTORE: storeTwo(Bytes.beU2(code, bci + 2)); return 3; 515 case FSTORE:
594 case FSTORE: storeOne(Bytes.beU2(code, bci + 2)); return 3;
595 case DSTORE: storeTwo(Bytes.beU2(code, bci + 2)); return 3;
596 case ASTORE: storeOne(Bytes.beU2(code, bci + 2)); return 3;
597 }
598 return lengthOf(code, bci);
599 }
600
601 private int processStore(int opcode, byte[] code, int bci) {
602 switch (opcode) {
603 case IINC: storeOne(code[bci + 1] & 0xff); return 3;
604 case ISTORE: storeOne(code[bci + 1] & 0xff); return 2;
605 case LSTORE: storeTwo(code[bci + 1] & 0xff); return 2;
606 case FSTORE: storeOne(code[bci + 1] & 0xff); return 2;
607 case DSTORE: storeTwo(code[bci + 1] & 0xff); return 2;
608 case WSTORE: 516 case WSTORE:
609 case ASTORE: storeOne(code[bci + 1] & 0xff); return 2; 517 case ASTORE:
610 case ISTORE_0: // fall through 518 storesInLoops.set(local);
611 case ISTORE_1: // fall through 519 break;
612 case ISTORE_2: // fall through 520
613 case ISTORE_3: storeOne(opcode - ISTORE_0); return 1; 521 case LSTORE:
614 case LSTORE_0: // fall through 522 case DSTORE:
615 case LSTORE_1: // fall through 523 storesInLoops.set(local);
616 case LSTORE_2: // fall through 524 storesInLoops.set(local + 1);
617 case LSTORE_3: storeTwo(opcode - LSTORE_0); return 1; 525 break;
618 case FSTORE_0: // fall through 526
619 case FSTORE_1: // fall through 527 case ISTORE_0:
620 case FSTORE_2: // fall through 528 case FSTORE_0:
621 case FSTORE_3: storeOne(opcode - FSTORE_0); return 1; 529 case ASTORE_0:
622 case DSTORE_0: // fall through 530 case WSTORE_0:
623 case DSTORE_1: // fall through 531 storesInLoops.set(0);
624 case DSTORE_2: // fall through 532 break;
625 case DSTORE_3: storeTwo(opcode - DSTORE_0); return 1; 533 case ISTORE_1:
626 case ASTORE_0: // fall through 534 case FSTORE_1:
627 case ASTORE_1: // fall through 535 case ASTORE_1:
628 case ASTORE_2: // fall through 536 case WSTORE_1:
629 case ASTORE_3: storeOne(opcode - ASTORE_0); return 1; 537 storesInLoops.set(1);
630 case WSTORE_0: // fall through 538 break;
631 case WSTORE_1: // fall through 539 case ISTORE_2:
632 case WSTORE_2: // fall through 540 case FSTORE_2:
633 case WSTORE_3: storeOne(opcode - WSTORE_0); return 1; 541 case ASTORE_2:
634 } 542 case WSTORE_2:
635 throw Util.shouldNotReachHere(); 543 storesInLoops.set(2);
636 } 544 break;
637 545 case ISTORE_3:
638 private void storeOne(int local) { 546 case FSTORE_3:
639 storesInLoops.set(local); 547 case ASTORE_3:
640 } 548 case WSTORE_3:
641 549 storesInLoops.set(3);
642 private void storeTwo(int local) { 550 break;
643 storesInLoops.set(local); 551
644 storesInLoops.set(local + 1); 552 case LSTORE_0:
645 } 553 case DSTORE_0:
646 554 storesInLoops.set(0);
647 private void succ2(int bci, int s1, int s2) { 555 storesInLoops.set(1);
648 successorMap[bci] = new BlockBegin[] {make(s1), make(s2)}; 556 break;
649 } 557 case LSTORE_1:
650 558 case DSTORE_1:
651 private void succ1(int bci, int s1) { 559 storesInLoops.set(1);
652 successorMap[bci] = new BlockBegin[] {make(s1)}; 560 storesInLoops.set(2);
653 } 561 break;
654 562 case LSTORE_2:
655 private static StringBuilder append(StringBuilder sb, BlockBegin block) { 563 case DSTORE_2:
656 return sb.append('B').append(block.blockID).append('@').append(block.bci()); 564 storesInLoops.set(2);
657 } 565 storesInLoops.set(3);
658 566 break;
659 @Override 567 case LSTORE_3:
660 public String toString() { 568 case DSTORE_3:
661 StringBuilder sb = new StringBuilder(); 569 storesInLoops.set(3);
662 for (int bci = 0; bci < blockMap.length; ++bci) { 570 storesInLoops.set(4);
663 BlockBegin block = blockMap[bci]; 571 break;
664 if (block != null) { 572
665 append(sb, block); 573 default:
666 if (loopBlocks != null && loopBlocks.contains(block)) { 574 throw new InternalError("undefined store bytecode");
667 sb.append("{loop-header}"); 575 }
668 } 576 }
669 if (successorMap != null) { 577
670 BlockBegin[] succs = successorMap[bci]; 578
671 if (succs != null && succs.length > 0) { 579
672 sb.append(" ->"); 580 /**
673 for (BlockBegin succ : succs) { 581 * Print block information in the format required by {@linkplain CFGPrinter}. The method must
674 append(sb.append(' '), succ); 582 * be here because it accesses private state of a block.
675 } 583 */
676 } 584 public void printBlock(Block block, LogStream out) {
677 } 585 out.print("name \"B").print(block.startBci).println('"');
678 Collection<BlockBegin> handlers = getHandlers(block); 586 out.print("from_bci ").println(block.startBci);
679 if (!handlers.isEmpty()) { 587 out.print("to_bci ").println(block.endBci);
680 sb.append(" xhandlers{"); 588
681 for (BlockBegin h : handlers) { 589 out.println("predecessors ");
682 append(sb, h).append(' '); 590
683 } 591 out.print("successors ");
684 sb.append('}'); 592 for (Block succ : block.successors) {
685 } 593 if (!succ.isExceptionEntry) {
686 sb.append(String.format("%n")); 594 out.print("\"B").print(succ.startBci).print("\" ");
687 } 595 }
688 } 596 }
689 return sb.toString(); 597 out.println();
690 } 598
599 out.print("xhandlers");
600 for (Block succ : block.successors) {
601 if (succ.isExceptionEntry) {
602 out.print("\"B").print(succ.startBci).print("\" ");
603 }
604 }
605 out.println();
606
607 out.print("flags ");
608 if (block.isExceptionEntry) {
609 out.print("\"ex\" ");
610 }
611 if (block.isLoopHeader) {
612 out.print("\"plh\" ");
613 }
614 out.println();
615
616 out.print("loop_depth ").println(Integer.bitCount(block.loops));
617 }
618
619 //
620 // private static StringBuilder append(StringBuilder sb, BlockBegin block) {
621 // return sb.append('B').append(block.blockID).append('@').append(block.bci());
622 // }
623 //
624 // @Override
625 // public String toString() {
626 // StringBuilder sb = new StringBuilder();
627 // for (int bci = 0; bci < blockMap.length; ++bci) {
628 // BlockBegin block = blockMap[bci];
629 // if (block != null) {
630 // append(sb, block);
631 // if (loopBlocks != null && loopBlocks.contains(block)) {
632 // sb.append("{loop-header}");
633 // }
634 // if (successorMap != null) {
635 // BlockBegin[] succs = successorMap[bci];
636 // if (succs != null && succs.length > 0) {
637 // sb.append(" ->");
638 // for (BlockBegin succ : succs) {
639 // append(sb.append(' '), succ);
640 // }
641 // }
642 // }
643 // Collection<BlockBegin> handlers = getHandlers(block);
644 // if (!handlers.isEmpty()) {
645 // sb.append(" xhandlers{");
646 // for (BlockBegin h : handlers) {
647 // append(sb, h).append(' ');
648 // }
649 // sb.append('}');
650 // }
651 // sb.append(String.format("%n"));
652 // }
653 // }
654 // return sb.toString();
655 // }
691 } 656 }