1 /*
2 * Copyright (c) 2009, 2015, 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 org.graalvm.compiler.java;
24
25 import static org.graalvm.compiler.bytecode.Bytecodes.AALOAD;
26 import static org.graalvm.compiler.bytecode.Bytecodes.AASTORE;
27 import static org.graalvm.compiler.bytecode.Bytecodes.ARETURN;
28 import static org.graalvm.compiler.bytecode.Bytecodes.ARRAYLENGTH;
29 import static org.graalvm.compiler.bytecode.Bytecodes.ATHROW;
30 import static org.graalvm.compiler.bytecode.Bytecodes.BALOAD;
31 import static org.graalvm.compiler.bytecode.Bytecodes.BASTORE;
32 import static org.graalvm.compiler.bytecode.Bytecodes.CALOAD;
33 import static org.graalvm.compiler.bytecode.Bytecodes.CASTORE;
34 import static org.graalvm.compiler.bytecode.Bytecodes.DALOAD;
35 import static org.graalvm.compiler.bytecode.Bytecodes.DASTORE;
36 import static org.graalvm.compiler.bytecode.Bytecodes.DRETURN;
37 import static org.graalvm.compiler.bytecode.Bytecodes.FALOAD;
38 import static org.graalvm.compiler.bytecode.Bytecodes.FASTORE;
39 import static org.graalvm.compiler.bytecode.Bytecodes.FRETURN;
40 import static org.graalvm.compiler.bytecode.Bytecodes.GETFIELD;
41 import static org.graalvm.compiler.bytecode.Bytecodes.GOTO;
42 import static org.graalvm.compiler.bytecode.Bytecodes.GOTO_W;
43 import static org.graalvm.compiler.bytecode.Bytecodes.IALOAD;
44 import static org.graalvm.compiler.bytecode.Bytecodes.IASTORE;
45 import static org.graalvm.compiler.bytecode.Bytecodes.IFEQ;
46 import static org.graalvm.compiler.bytecode.Bytecodes.IFGE;
47 import static org.graalvm.compiler.bytecode.Bytecodes.IFGT;
48 import static org.graalvm.compiler.bytecode.Bytecodes.IFLE;
49 import static org.graalvm.compiler.bytecode.Bytecodes.IFLT;
50 import static org.graalvm.compiler.bytecode.Bytecodes.IFNE;
51 import static org.graalvm.compiler.bytecode.Bytecodes.IFNONNULL;
52 import static org.graalvm.compiler.bytecode.Bytecodes.IFNULL;
53 import static org.graalvm.compiler.bytecode.Bytecodes.IF_ACMPEQ;
54 import static org.graalvm.compiler.bytecode.Bytecodes.IF_ACMPNE;
55 import static org.graalvm.compiler.bytecode.Bytecodes.IF_ICMPEQ;
56 import static org.graalvm.compiler.bytecode.Bytecodes.IF_ICMPGE;
57 import static org.graalvm.compiler.bytecode.Bytecodes.IF_ICMPGT;
58 import static org.graalvm.compiler.bytecode.Bytecodes.IF_ICMPLE;
59 import static org.graalvm.compiler.bytecode.Bytecodes.IF_ICMPLT;
60 import static org.graalvm.compiler.bytecode.Bytecodes.IF_ICMPNE;
61 import static org.graalvm.compiler.bytecode.Bytecodes.INVOKEDYNAMIC;
62 import static org.graalvm.compiler.bytecode.Bytecodes.INVOKEINTERFACE;
63 import static org.graalvm.compiler.bytecode.Bytecodes.INVOKESPECIAL;
64 import static org.graalvm.compiler.bytecode.Bytecodes.INVOKESTATIC;
65 import static org.graalvm.compiler.bytecode.Bytecodes.INVOKEVIRTUAL;
66 import static org.graalvm.compiler.bytecode.Bytecodes.IRETURN;
67 import static org.graalvm.compiler.bytecode.Bytecodes.JSR;
68 import static org.graalvm.compiler.bytecode.Bytecodes.JSR_W;
69 import static org.graalvm.compiler.bytecode.Bytecodes.LALOAD;
70 import static org.graalvm.compiler.bytecode.Bytecodes.LASTORE;
71 import static org.graalvm.compiler.bytecode.Bytecodes.LOOKUPSWITCH;
72 import static org.graalvm.compiler.bytecode.Bytecodes.LRETURN;
73 import static org.graalvm.compiler.bytecode.Bytecodes.PUTFIELD;
74 import static org.graalvm.compiler.bytecode.Bytecodes.RET;
75 import static org.graalvm.compiler.bytecode.Bytecodes.RETURN;
76 import static org.graalvm.compiler.bytecode.Bytecodes.SALOAD;
77 import static org.graalvm.compiler.bytecode.Bytecodes.SASTORE;
78 import static org.graalvm.compiler.bytecode.Bytecodes.TABLESWITCH;
79 import static org.graalvm.compiler.core.common.GraalOptions.SupportJsrBytecodes;
80
81 import java.util.ArrayList;
82 import java.util.Arrays;
83 import java.util.Collection;
84 import java.util.HashMap;
85 import java.util.HashSet;
86 import java.util.Iterator;
87 import java.util.List;
88 import java.util.TreeSet;
89
90 import org.graalvm.compiler.bytecode.Bytecode;
91 import org.graalvm.compiler.bytecode.BytecodeLookupSwitch;
92 import org.graalvm.compiler.bytecode.BytecodeStream;
93 import org.graalvm.compiler.bytecode.BytecodeSwitch;
94 import org.graalvm.compiler.bytecode.BytecodeTableSwitch;
95 import org.graalvm.compiler.bytecode.Bytecodes;
96 import org.graalvm.compiler.common.PermanentBailoutException;
97 import org.graalvm.compiler.core.common.CollectionsFactory;
98 import org.graalvm.compiler.debug.Debug;
99
100 import jdk.vm.ci.code.BytecodeFrame;
101 import jdk.vm.ci.meta.ExceptionHandler;
102
103 /**
104 * Builds a mapping between bytecodes and basic blocks and builds a conservative control flow graph
105 * (CFG). It makes one linear passes over the bytecodes to build the CFG where it detects block
106 * headers and connects them.
107 * <p>
108 * It also creates exception dispatch blocks for exception handling. These blocks are between a
109 * bytecode that might throw an exception, and the actual exception handler entries, and are later
110 * used to create the type checks with the exception handler catch types. If a bytecode is covered
111 * by an exception handler, this bytecode ends the basic block. This guarantees that a) control flow
112 * cannot be transferred to an exception dispatch block in the middle of a block, and b) that every
113 * block has at most one exception dispatch block (which is always the last entry in the successor
114 * list).
115 * <p>
116 * If a bytecode is covered by multiple exception handlers, a chain of exception dispatch blocks is
117 * created so that multiple exception handler types can be checked. The chains are re-used if
118 * multiple bytecodes are covered by the same exception handlers.
119 * <p>
120 * Note that exception unwinds, i.e., bytecodes that can throw an exception but the exception is not
121 * handled in this method, do not end a basic block. Not modeling the exception unwind block reduces
122 * the complexity of the CFG, and there is no algorithm yet where the exception unwind block would
123 * matter.
124 * <p>
125 * The class also handles subroutines (jsr and ret bytecodes): subroutines are inlined by
126 * duplicating the subroutine blocks. This is limited to simple, structured subroutines with a
127 * maximum subroutine nesting of 4. Otherwise, a bailout is thrown.
128 * <p>
129 * Loops in the methods are detected. If a method contains an irreducible loop (a loop with more
130 * than one entry), a bailout is thrown. This simplifies the compiler later on since only structured
131 * loops need to be supported.
132 * <p>
133 * A data flow analysis computes the live local variables from the point of view of the interpreter.
134 * The result is used later to prune frame states, i.e., remove local variable entries that are
135 * guaranteed to be never used again (even in the case of deoptimization).
136 * <p>
137 * The algorithms and analysis in this class are conservative and do not use any assumptions or
138 * profiling information.
139 */
140 public final class BciBlockMapping {
141
142 public static class BciBlock implements Cloneable {
143
144 protected int id;
145 public int startBci;
146 public int endBci;
147 public boolean isExceptionEntry;
148 public boolean isLoopHeader;
149 public int loopId;
150 public int loopEnd;
151 protected List<BciBlock> successors;
152 private int predecessorCount;
153
154 private boolean visited;
155 private boolean active;
156 public long loops;
157 public JSRData jsrData;
158
159 public static class JSRData implements Cloneable {
160 public HashMap<JsrScope, BciBlock> jsrAlternatives;
161 public JsrScope jsrScope = JsrScope.EMPTY_SCOPE;
162 public BciBlock jsrSuccessor;
163 public int jsrReturnBci;
164 public BciBlock retSuccessor;
165 public boolean endsWithRet = false;
166
167 public JSRData copy() {
168 try {
169 return (JSRData) this.clone();
170 } catch (CloneNotSupportedException e) {
171 return null;
172 }
173 }
174 }
175
176 public BciBlock() {
177 this.successors = new ArrayList<>(4);
178 }
179
180 public BciBlock exceptionDispatchBlock() {
181 if (successors.size() > 0 && successors.get(successors.size() - 1) instanceof ExceptionDispatchBlock) {
182 return successors.get(successors.size() - 1);
183 }
184 return null;
185 }
186
187 public int getId() {
188 return id;
189 }
190
191 public int getPredecessorCount() {
192 return this.predecessorCount;
193 }
194
195 public int numNormalSuccessors() {
196 if (exceptionDispatchBlock() != null) {
197 return successors.size() - 1;
198 }
199 return successors.size();
200 }
201
202 public BciBlock copy() {
203 try {
204 BciBlock block = (BciBlock) super.clone();
205 if (block.jsrData != null) {
206 block.jsrData = block.jsrData.copy();
207 }
208 block.successors = new ArrayList<>(successors);
209 return block;
210 } catch (CloneNotSupportedException e) {
211 throw new RuntimeException(e);
212 }
213 }
214
215 @Override
216 public String toString() {
217 StringBuilder sb = new StringBuilder("B").append(getId());
218 sb.append('[').append(startBci).append("->").append(endBci);
219 if (isLoopHeader || isExceptionEntry) {
220 sb.append(' ');
221 if (isLoopHeader) {
222 sb.append('L');
223 }
224 if (isExceptionEntry) {
225 sb.append('!');
226 }
227 }
228 sb.append(']');
229 return sb.toString();
230 }
231
232 public int getLoopDepth() {
233 return Long.bitCount(loops);
234 }
235
236 public boolean isLoopHeader() {
237 return isLoopHeader;
238 }
239
240 public boolean isExceptionEntry() {
241 return isExceptionEntry;
242 }
243
244 public BciBlock getSuccessor(int index) {
245 return successors.get(index);
246 }
247
248 /**
249 * Get the loop id of the inner most loop.
250 *
251 * @return the loop id of the most inner loop or -1 if not part of any loop
252 */
253 public int getLoopId() {
254 long l = loops;
255 if (l == 0) {
256 return -1;
257 }
258 int pos = 0;
259 for (int lMask = 1; (l & lMask) == 0; lMask = lMask << 1) {
260 pos++;
261 }
262 return pos;
263 }
264
265 /**
266 * Iterate over loop ids.
267 */
268 public Iterable<Integer> loopIdIterable() {
269 return new Iterable<Integer>() {
270 @Override
271 public Iterator<Integer> iterator() {
272 return idIterator(loops);
273 }
274 };
275 }
276
277 private static Iterator<Integer> idIterator(long field) {
278 return new Iterator<Integer>() {
279
280 long l = field;
281 int pos = 0;
282 int lMask = 1;
283
284 @Override
285 public Integer next() {
286 for (; (l & lMask) == 0; lMask = lMask << 1) {
287 pos++;
288 }
289 l &= ~lMask;
290 return pos;
291 }
292
293 @Override
294 public boolean hasNext() {
295 return l != 0;
296 }
297 };
298
299 }
300
301 public double probability() {
302 return 1D;
303 }
304
305 public BciBlock getPostdominator() {
306 return null;
307 }
308
309 private JSRData getOrCreateJSRData() {
310 if (jsrData == null) {
311 jsrData = new JSRData();
312 }
313 return jsrData;
314 }
315
316 void setEndsWithRet() {
317 getOrCreateJSRData().endsWithRet = true;
318 }
319
320 public JsrScope getJsrScope() {
321 if (this.jsrData == null) {
322 return JsrScope.EMPTY_SCOPE;
323 } else {
324 return jsrData.jsrScope;
325 }
326 }
327
328 public boolean endsWithRet() {
329 if (this.jsrData == null) {
330 return false;
331 } else {
332 return jsrData.endsWithRet;
333 }
334 }
335
336 void setRetSuccessor(BciBlock bciBlock) {
337 this.getOrCreateJSRData().retSuccessor = bciBlock;
338 }
339
340 public BciBlock getRetSuccessor() {
341 if (this.jsrData == null) {
342 return null;
343 } else {
344 return jsrData.retSuccessor;
345 }
346 }
347
348 public BciBlock getJsrSuccessor() {
349 if (this.jsrData == null) {
350 return null;
351 } else {
352 return jsrData.jsrSuccessor;
353 }
354 }
355
356 public int getJsrReturnBci() {
357 if (this.jsrData == null) {
358 return -1;
359 } else {
360 return jsrData.jsrReturnBci;
361 }
362 }
363
364 public HashMap<JsrScope, BciBlock> getJsrAlternatives() {
365 if (this.jsrData == null) {
366 return null;
367 } else {
368 return jsrData.jsrAlternatives;
369 }
370 }
371
372 public void initJsrAlternatives() {
373 JSRData data = this.getOrCreateJSRData();
374 if (data.jsrAlternatives == null) {
375 data.jsrAlternatives = new HashMap<>();
376 }
377 }
378
379 void setJsrScope(JsrScope nextScope) {
380 this.getOrCreateJSRData().jsrScope = nextScope;
381 }
382
383 void setJsrSuccessor(BciBlock clone) {
384 this.getOrCreateJSRData().jsrSuccessor = clone;
385 }
386
387 void setJsrReturnBci(int bci) {
388 this.getOrCreateJSRData().jsrReturnBci = bci;
389 }
390
391 public int getSuccessorCount() {
392 return successors.size();
393 }
394
395 public List<BciBlock> getSuccessors() {
396 return successors;
397 }
398
399 void setId(int i) {
400 this.id = i;
401 }
402
403 public void addSuccessor(BciBlock sux) {
404 successors.add(sux);
405 sux.predecessorCount++;
406 }
407
408 public void clearSucccessors() {
409 for (BciBlock sux : successors) {
410 sux.predecessorCount--;
411 }
412 successors.clear();
413 }
414 }
415
416 public static class ExceptionDispatchBlock extends BciBlock {
417
418 private HashMap<ExceptionHandler, ExceptionDispatchBlock> exceptionDispatch = new HashMap<>();
419
420 public ExceptionHandler handler;
421 public int deoptBci;
422 }
423
424 /**
425 * The blocks found in this method, in reverse postorder.
426 */
427 private BciBlock[] blocks;
428 public final Bytecode code;
429 public boolean hasJsrBytecodes;
430
431 private final ExceptionHandler[] exceptionHandlers;
432 private BciBlock startBlock;
433 private BciBlock[] loopHeaders;
434
435 private static final int LOOP_HEADER_MAX_CAPACITY = Long.SIZE;
436 private static final int LOOP_HEADER_INITIAL_CAPACITY = 4;
437
438 private int blocksNotYetAssignedId;
439 public int returnCount;
440 private int returnBci;
441
442 /**
443 * Creates a new BlockMap instance from {@code code}.
444 */
445 private BciBlockMapping(Bytecode code) {
446 this.code = code;
447 this.exceptionHandlers = code.getExceptionHandlers();
448 }
449
450 public BciBlock[] getBlocks() {
451 return this.blocks;
452 }
453
454 public int getReturnCount() {
455 return this.returnCount;
456 }
457
458 /**
459 * Builds the block map and conservative CFG and numbers blocks.
460 */
461 public void build(BytecodeStream stream) {
462 int codeSize = code.getCodeSize();
463 BciBlock[] blockMap = new BciBlock[codeSize];
464 makeExceptionEntries(blockMap);
465 iterateOverBytecodes(blockMap, stream);
466 if (hasJsrBytecodes) {
467 if (!SupportJsrBytecodes.getValue()) {
468 throw new JsrNotSupportedBailout("jsr/ret parsing disabled");
469 }
470 createJsrAlternatives(blockMap, blockMap[0]);
471 }
472 if (Debug.isLogEnabled()) {
473 this.log(blockMap, "Before BlockOrder");
474 }
475 computeBlockOrder(blockMap);
476 fixLoopBits(blockMap);
477
478 assert verify();
479
480 startBlock = blockMap[0];
481 if (Debug.isLogEnabled()) {
482 this.log(blockMap, "Before LivenessAnalysis");
483 }
484 }
485
486 private boolean verify() {
487 for (BciBlock block : blocks) {
488 assert blocks[block.getId()] == block;
489
490 for (int i = 0; i < block.getSuccessorCount(); i++) {
491 BciBlock sux = block.getSuccessor(i);
492 if (sux instanceof ExceptionDispatchBlock) {
493 assert i == block.getSuccessorCount() - 1 : "Only one exception handler allowed, and it must be last in successors list";
494 }
495 }
496 }
497
498 return true;
499 }
500
501 private void makeExceptionEntries(BciBlock[] blockMap) {
502 // start basic blocks at all exception handler blocks and mark them as exception entries
503 for (ExceptionHandler h : this.exceptionHandlers) {
504 BciBlock xhandler = makeBlock(blockMap, h.getHandlerBCI());
505 xhandler.isExceptionEntry = true;
506 }
507 }
508
509 private void iterateOverBytecodes(BciBlock[] blockMap, BytecodeStream stream) {
510 // iterate over the bytecodes top to bottom.
511 // mark the entrypoints of basic blocks and build lists of successors for
512 // all bytecodes that end basic blocks (i.e. goto, ifs, switches, throw, jsr, returns, ret)
513 BciBlock current = null;
514 stream.setBCI(0);
515 while (stream.currentBC() != Bytecodes.END) {
516 int bci = stream.currentBCI();
517
518 if (current == null || blockMap[bci] != null) {
519 BciBlock b = makeBlock(blockMap, bci);
520 if (current != null) {
521 addSuccessor(blockMap, current.endBci, b);
522 }
523 current = b;
524 }
525 blockMap[bci] = current;
526 current.endBci = bci;
527
528 switch (stream.currentBC()) {
529 case IRETURN: // fall through
530 case LRETURN: // fall through
531 case FRETURN: // fall through
532 case DRETURN: // fall through
533 case ARETURN: // fall through
534 case RETURN: {
535 returnCount++;
536 current = null;
537 returnBci = bci;
538 break;
539 }
540 case ATHROW: {
541 current = null;
542 ExceptionDispatchBlock handler = handleExceptions(blockMap, bci);
543 if (handler != null) {
544 addSuccessor(blockMap, bci, handler);
545 }
546 break;
547 }
548 case IFEQ: // fall through
549 case IFNE: // fall through
550 case IFLT: // fall through
551 case IFGE: // fall through
552 case IFGT: // fall through
553 case IFLE: // fall through
554 case IF_ICMPEQ: // fall through
555 case IF_ICMPNE: // fall through
556 case IF_ICMPLT: // fall through
557 case IF_ICMPGE: // fall through
558 case IF_ICMPGT: // fall through
559 case IF_ICMPLE: // fall through
560 case IF_ACMPEQ: // fall through
561 case IF_ACMPNE: // fall through
562 case IFNULL: // fall through
563 case IFNONNULL: {
564 current = null;
565 addSuccessor(blockMap, bci, makeBlock(blockMap, stream.readBranchDest()));
566 addSuccessor(blockMap, bci, makeBlock(blockMap, stream.nextBCI()));
567 break;
568 }
569 case GOTO:
570 case GOTO_W: {
571 current = null;
572 addSuccessor(blockMap, bci, makeBlock(blockMap, stream.readBranchDest()));
573 break;
574 }
575 case TABLESWITCH: {
576 current = null;
577 addSwitchSuccessors(blockMap, bci, new BytecodeTableSwitch(stream, bci));
578 break;
579 }
580 case LOOKUPSWITCH: {
581 current = null;
582 addSwitchSuccessors(blockMap, bci, new BytecodeLookupSwitch(stream, bci));
583 break;
584 }
585 case JSR:
586 case JSR_W: {
587 hasJsrBytecodes = true;
588 int target = stream.readBranchDest();
589 if (target == 0) {
590 throw new JsrNotSupportedBailout("jsr target bci 0 not allowed");
591 }
592 BciBlock b1 = makeBlock(blockMap, target);
593 current.setJsrSuccessor(b1);
594 current.setJsrReturnBci(stream.nextBCI());
595 current = null;
596 addSuccessor(blockMap, bci, b1);
597 break;
598 }
599 case RET: {
600 current.setEndsWithRet();
601 current = null;
602 break;
603 }
604 case INVOKEINTERFACE:
605 case INVOKESPECIAL:
606 case INVOKESTATIC:
607 case INVOKEVIRTUAL:
608 case INVOKEDYNAMIC: {
609 current = null;
610 addSuccessor(blockMap, bci, makeBlock(blockMap, stream.nextBCI()));
611 ExceptionDispatchBlock handler = handleExceptions(blockMap, bci);
612 if (handler != null) {
613 addSuccessor(blockMap, bci, handler);
614 }
615 break;
616 }
617 case IASTORE:
618 case LASTORE:
619 case FASTORE:
620 case DASTORE:
621 case AASTORE:
622 case BASTORE:
623 case CASTORE:
624 case SASTORE:
625 case IALOAD:
626 case LALOAD:
627 case FALOAD:
628 case DALOAD:
629 case AALOAD:
630 case BALOAD:
631 case CALOAD:
632 case SALOAD:
633 case ARRAYLENGTH:
634 case PUTFIELD:
635 case GETFIELD: {
636 ExceptionDispatchBlock handler = handleExceptions(blockMap, bci);
637 if (handler != null) {
638 current = null;
639 addSuccessor(blockMap, bci, makeBlock(blockMap, stream.nextBCI()));
640 addSuccessor(blockMap, bci, handler);
641 }
642 }
643 }
644 stream.next();
645 }
646 }
647
648 private BciBlock makeBlock(BciBlock[] blockMap, int startBci) {
649 BciBlock oldBlock = blockMap[startBci];
650 if (oldBlock == null) {
651 BciBlock newBlock = new BciBlock();
652 blocksNotYetAssignedId++;
653 newBlock.startBci = startBci;
654 blockMap[startBci] = newBlock;
655 return newBlock;
656
657 } else if (oldBlock.startBci != startBci) {
658 // Backward branch into the middle of an already processed block.
659 // Add the correct fall-through successor.
660 BciBlock newBlock = new BciBlock();
661 blocksNotYetAssignedId++;
662 newBlock.startBci = startBci;
663 newBlock.endBci = oldBlock.endBci;
664 for (BciBlock oldSuccessor : oldBlock.getSuccessors()) {
665 newBlock.addSuccessor(oldSuccessor);
666 }
667
668 oldBlock.endBci = startBci - 1;
669 oldBlock.clearSucccessors();
670 oldBlock.addSuccessor(newBlock);
671
672 for (int i = startBci; i <= newBlock.endBci; i++) {
673 blockMap[i] = newBlock;
674 }
675 return newBlock;
676
677 } else {
678 return oldBlock;
679 }
680 }
681
682 private void addSwitchSuccessors(BciBlock[] blockMap, int predBci, BytecodeSwitch bswitch) {
683 // adds distinct targets to the successor list
684 Collection<Integer> targets = new TreeSet<>();
685 for (int i = 0; i < bswitch.numberOfCases(); i++) {
686 targets.add(bswitch.targetAt(i));
687 }
688 targets.add(bswitch.defaultTarget());
689 for (int targetBci : targets) {
690 addSuccessor(blockMap, predBci, makeBlock(blockMap, targetBci));
691 }
692 }
693
694 private static void addSuccessor(BciBlock[] blockMap, int predBci, BciBlock sux) {
695 BciBlock predecessor = blockMap[predBci];
696 if (sux.isExceptionEntry) {
697 throw new PermanentBailoutException("Exception handler can be reached by both normal and exceptional control flow");
698 }
699 predecessor.addSuccessor(sux);
700 }
701
702 private final ArrayList<BciBlock> jsrVisited = new ArrayList<>();
703
704 private void createJsrAlternatives(BciBlock[] blockMap, BciBlock block) {
705 jsrVisited.add(block);
706 JsrScope scope = block.getJsrScope();
707
708 if (block.endsWithRet()) {
709 block.setRetSuccessor(blockMap[scope.nextReturnAddress()]);
710 block.addSuccessor(block.getRetSuccessor());
711 assert block.getRetSuccessor() != block.getJsrSuccessor();
712 }
713 Debug.log("JSR alternatives block %s sux %s jsrSux %s retSux %s jsrScope %s", block, block.getSuccessors(), block.getJsrSuccessor(), block.getRetSuccessor(), block.getJsrScope());
714
715 if (block.getJsrSuccessor() != null || !scope.isEmpty()) {
716 for (int i = 0; i < block.getSuccessorCount(); i++) {
717 BciBlock successor = block.getSuccessor(i);
718 JsrScope nextScope = scope;
719 if (successor == block.getJsrSuccessor()) {
720 nextScope = scope.push(block.getJsrReturnBci());
721 }
722 if (successor == block.getRetSuccessor()) {
723 nextScope = scope.pop();
724 }
725 if (!successor.getJsrScope().isPrefixOf(nextScope)) {
726 throw new JsrNotSupportedBailout("unstructured control flow (" + successor.getJsrScope() + " " + nextScope + ")");
727 }
728 if (!nextScope.isEmpty()) {
729 BciBlock clone;
730 if (successor.getJsrAlternatives() != null && successor.getJsrAlternatives().containsKey(nextScope)) {
731 clone = successor.getJsrAlternatives().get(nextScope);
732 } else {
733 successor.initJsrAlternatives();
734 clone = successor.copy();
735 blocksNotYetAssignedId++;
736 clone.setJsrScope(nextScope);
737 successor.getJsrAlternatives().put(nextScope, clone);
738 }
739 block.getSuccessors().set(i, clone);
740 if (successor == block.getJsrSuccessor()) {
741 block.setJsrSuccessor(clone);
742 }
743 if (successor == block.getRetSuccessor()) {
744 block.setRetSuccessor(clone);
745 }
746 }
747 }
748 }
749 for (BciBlock successor : block.getSuccessors()) {
750 if (!jsrVisited.contains(successor)) {
751 createJsrAlternatives(blockMap, successor);
752 }
753 }
754 }
755
756 private HashMap<ExceptionHandler, ExceptionDispatchBlock> initialExceptionDispatch = CollectionsFactory.newMap();
757
758 private ExceptionDispatchBlock handleExceptions(BciBlock[] blockMap, int bci) {
759 ExceptionDispatchBlock lastHandler = null;
760
761 for (int i = exceptionHandlers.length - 1; i >= 0; i--) {
762 ExceptionHandler h = exceptionHandlers[i];
763 if (h.getStartBCI() <= bci && bci < h.getEndBCI()) {
764 if (h.isCatchAll()) {
765 // Discard all information about succeeding exception handlers, since they can
766 // never be reached.
767 lastHandler = null;
768 }
769
770 HashMap<ExceptionHandler, ExceptionDispatchBlock> exceptionDispatch = lastHandler != null ? lastHandler.exceptionDispatch : initialExceptionDispatch;
771 ExceptionDispatchBlock curHandler = exceptionDispatch.get(h);
772 if (curHandler == null) {
773 curHandler = new ExceptionDispatchBlock();
774 blocksNotYetAssignedId++;
775 curHandler.startBci = -1;
776 curHandler.endBci = -1;
777 curHandler.deoptBci = bci;
778 curHandler.handler = h;
779 curHandler.addSuccessor(blockMap[h.getHandlerBCI()]);
780 if (lastHandler != null) {
781 curHandler.addSuccessor(lastHandler);
782 }
783 exceptionDispatch.put(h, curHandler);
784 }
785 lastHandler = curHandler;
786 }
787 }
788 return lastHandler;
789 }
790
791 private boolean loopChanges;
792
793 private void fixLoopBits(BciBlock[] blockMap) {
794 do {
795 loopChanges = false;
796 for (BciBlock b : blocks) {
797 b.visited = false;
798 }
799
800 long loop = fixLoopBits(blockMap, blockMap[0]);
801
802 if (loop != 0) {
803 // There is a path from a loop end to the method entry that does not pass the loop
804 // header.
805 // Therefore, the loop is non reducible (has more than one entry).
806 // We don't want to compile such methods because the IR only supports structured
807 // loops.
808 throw new PermanentBailoutException("Non-reducible loop: %016x", loop);
809 }
810 } while (loopChanges);
811 }
812
813 private void computeBlockOrder(BciBlock[] blockMap) {
814 int maxBlocks = blocksNotYetAssignedId;
815 this.blocks = new BciBlock[blocksNotYetAssignedId];
816 long loop = computeBlockOrder(blockMap[0]);
817
818 if (loop != 0) {
819 // There is a path from a loop end to the method entry that does not pass the loop
820 // header. Therefore, the loop is non reducible (has more than one entry).
821 // We don't want to compile such methods because the IR only supports structured loops.
822 throw new PermanentBailoutException("Non-reducible loop");
823 }
824
825 // Purge null entries for unreached blocks and sort blocks such that loop bodies are always
826 // consecutively in the array.
827 int blockCount = maxBlocks - blocksNotYetAssignedId + 2;
828 BciBlock[] newBlocks = new BciBlock[blockCount];
829 int next = 0;
830 for (int i = 0; i < blocks.length; ++i) {
831 BciBlock b = blocks[i];
832 if (b != null) {
833 b.setId(next);
834 newBlocks[next++] = b;
835 if (b.isLoopHeader) {
836 next = handleLoopHeader(newBlocks, next, i, b);
837 }
838 }
839 }
840
841 // Add return block.
842 BciBlock returnBlock = new BciBlock();
843 returnBlock.startBci = returnBci;
844 returnBlock.endBci = returnBci;
845 returnBlock.setId(newBlocks.length - 2);
846 newBlocks[newBlocks.length - 2] = returnBlock;
847
848 // Add unwind block.
849 ExceptionDispatchBlock unwindBlock = new ExceptionDispatchBlock();
850 unwindBlock.startBci = -1;
851 unwindBlock.endBci = -1;
852 unwindBlock.deoptBci = code.getMethod().isSynchronized() ? BytecodeFrame.UNWIND_BCI : BytecodeFrame.AFTER_EXCEPTION_BCI;
853 unwindBlock.setId(newBlocks.length - 1);
854 newBlocks[newBlocks.length - 1] = unwindBlock;
855
856 blocks = newBlocks;
857 }
858
859 private int handleLoopHeader(BciBlock[] newBlocks, int nextStart, int i, BciBlock loopHeader) {
860 int next = nextStart;
861 int endOfLoop = nextStart - 1;
862 for (int j = i + 1; j < blocks.length; ++j) {
863 BciBlock other = blocks[j];
864 if (other != null && (other.loops & (1L << loopHeader.loopId)) != 0) {
865 other.setId(next);
866 endOfLoop = next;
867 newBlocks[next++] = other;
868 blocks[j] = null;
869 if (other.isLoopHeader) {
870 next = handleLoopHeader(newBlocks, next, j, other);
871 }
872 }
873 }
874 loopHeader.loopEnd = endOfLoop;
875 return next;
876 }
877
878 public void log(BciBlock[] blockMap, String name) {
879 if (Debug.isLogEnabled()) {
880 String n = System.lineSeparator();
881 StringBuilder sb = new StringBuilder(Debug.currentScope()).append("BlockMap ").append(name).append(" :");
882 sb.append(n);
883 Iterable<BciBlock> it;
884 if (blocks == null) {
885 it = new HashSet<>(Arrays.asList(blockMap));
886 } else {
887 it = Arrays.asList(blocks);
888 }
889 for (BciBlock b : it) {
890 if (b == null) {
891 continue;
892 }
893 sb.append("B").append(b.getId()).append(" (").append(b.startBci).append(" -> ").append(b.endBci).append(")");
894 if (b.isLoopHeader) {
895 sb.append(" LoopHeader");
896 }
897 if (b.isExceptionEntry) {
898 sb.append(" ExceptionEntry");
899 }
900 sb.append(n).append(" Sux : ");
901 for (BciBlock s : b.getSuccessors()) {
902 sb.append("B").append(s.getId()).append(" (").append(s.startBci).append(" -> ").append(s.endBci).append(")");
903 if (s.isExceptionEntry) {
904 sb.append("!");
905 }
906 sb.append(" ");
907 }
908 sb.append(n).append(" Loop : ");
909 for (int pos : b.loopIdIterable()) {
910 sb.append("B").append(loopHeaders[pos].getId()).append(" ");
911 }
912 sb.append(n);
913 }
914 Debug.log("%s", sb);
915 }
916 }
917
918 /**
919 * Get the header block for a loop index.
920 */
921 public BciBlock getLoopHeader(int index) {
922 return loopHeaders[index];
923 }
924
925 /**
926 * The next available loop number.
927 */
928 private int nextLoop;
929
930 /**
931 * Mark the block as a loop header, using the next available loop number. Also checks for corner
932 * cases that we don't want to compile.
933 */
934 private void makeLoopHeader(BciBlock block) {
935 if (!block.isLoopHeader) {
936 block.isLoopHeader = true;
937
938 if (block.isExceptionEntry) {
939 // Loops that are implicitly formed by an exception handler lead to all sorts of
940 // corner cases.
941 // Don't compile such methods for now, until we see a concrete case that allows
942 // checking for correctness.
943 throw new PermanentBailoutException("Loop formed by an exception handler");
944 }
945 if (nextLoop >= LOOP_HEADER_MAX_CAPACITY) {
946 // This restriction can be removed by using a fall-back to a BitSet in case we have
947 // more than 64 loops
948 // Don't compile such methods for now, until we see a concrete case that allows
949 // checking for correctness.
950 throw new PermanentBailoutException("Too many loops in method");
951 }
952
953 assert block.loops == 0;
954 block.loops = 1L << nextLoop;
955 Debug.log("makeLoopHeader(%s) -> %x", block, block.loops);
956 if (loopHeaders == null) {
957 loopHeaders = new BciBlock[LOOP_HEADER_INITIAL_CAPACITY];
958 } else if (nextLoop >= loopHeaders.length) {
959 loopHeaders = Arrays.copyOf(loopHeaders, LOOP_HEADER_MAX_CAPACITY);
960 }
961 loopHeaders[nextLoop] = block;
962 block.loopId = nextLoop;
963 nextLoop++;
964 }
965 assert Long.bitCount(block.loops) == 1;
966 }
967
968 /**
969 * Depth-first traversal of the control flow graph. The flag {@linkplain BciBlock#visited} is
970 * used to visit every block only once. The flag {@linkplain BciBlock#active} is used to detect
971 * cycles (backward edges).
972 */
973 private long computeBlockOrder(BciBlock block) {
974 if (block.visited) {
975 if (block.active) {
976 // Reached block via backward branch.
977 makeLoopHeader(block);
978 // Return cached loop information for this block.
979 return block.loops;
980 } else if (block.isLoopHeader) {
981 return block.loops & ~(1L << block.loopId);
982 } else {
983 return block.loops;
984 }
985 }
986
987 block.visited = true;
988 block.active = true;
989
990 long loops = 0;
991 for (BciBlock successor : block.getSuccessors()) {
992 // Recursively process successors.
993 loops |= computeBlockOrder(successor);
994 if (successor.active) {
995 // Reached block via backward branch.
996 loops |= (1L << successor.loopId);
997 }
998 }
999
1000 block.loops = loops;
1001 Debug.log("computeBlockOrder(%s) -> %x", block, block.loops);
1002
1003 if (block.isLoopHeader) {
1004 loops &= ~(1L << block.loopId);
1005 }
1006
1007 block.active = false;
1008 blocksNotYetAssignedId--;
1009 blocks[blocksNotYetAssignedId] = block;
1010
1011 return loops;
1012 }
1013
1014 private long fixLoopBits(BciBlock[] blockMap, BciBlock block) {
1015 if (block.visited) {
1016 // Return cached loop information for this block.
1017 if (block.isLoopHeader) {
1018 return block.loops & ~(1L << block.loopId);
1019 } else {
1020 return block.loops;
1021 }
1022 }
1023
1024 block.visited = true;
1025 long loops = block.loops;
1026 for (BciBlock successor : block.getSuccessors()) {
1027 // Recursively process successors.
1028 loops |= fixLoopBits(blockMap, successor);
1029 }
1030 if (block.loops != loops) {
1031 loopChanges = true;
1032 block.loops = loops;
1033 Debug.log("fixLoopBits0(%s) -> %x", block, block.loops);
1034 }
1035
1036 if (block.isLoopHeader) {
1037 loops &= ~(1L << block.loopId);
1038 }
1039
1040 return loops;
1041 }
1042
1043 public static BciBlockMapping create(BytecodeStream stream, Bytecode code) {
1044 BciBlockMapping map = new BciBlockMapping(code);
1045 map.build(stream);
1046 if (Debug.isDumpEnabled(Debug.INFO_LOG_LEVEL)) {
1047 Debug.dump(Debug.INFO_LOG_LEVEL, map, code.getMethod().format("After block building %f %R %H.%n(%P)"));
1048 }
1049
1050 return map;
1051 }
1052
1053 public BciBlock[] getLoopHeaders() {
1054 return loopHeaders;
1055 }
1056
1057 public BciBlock getStartBlock() {
1058 return startBlock;
1059 }
1060
1061 public BciBlock getReturnBlock() {
1062 return blocks[blocks.length - 2];
1063 }
1064
1065 public ExceptionDispatchBlock getUnwindBlock() {
1066 return (ExceptionDispatchBlock) blocks[blocks.length - 1];
1067 }
1068
1069 public int getLoopCount() {
1070 return nextLoop;
1071 }
1072
1073 public int getBlockCount() {
1074 return blocks.length;
1075 }
1076 }