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