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