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