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.Debug;
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>
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
441 /**
442 * Creates a new BlockMap instance from {@code code}.
443 */
444 private BciBlockMapping(Bytecode code) {
445 this.code = code;
446 this.exceptionHandlers = code.getExceptionHandlers();
447 }
448
449 public BciBlock[] getBlocks() {
450 return this.blocks;
451 }
452
453 /**
454 * Builds the block map and conservative CFG and numbers blocks.
455 */
456 public void build(BytecodeStream stream, OptionValues options) {
457 int codeSize = code.getCodeSize();
458 BciBlock[] blockMap = new BciBlock[codeSize];
459 makeExceptionEntries(blockMap);
460 iterateOverBytecodes(blockMap, stream);
461 if (hasJsrBytecodes) {
462 if (!SupportJsrBytecodes.getValue(options)) {
463 throw new JsrNotSupportedBailout("jsr/ret parsing disabled");
464 }
465 createJsrAlternatives(blockMap, blockMap[0]);
466 }
467 if (Debug.isLogEnabled()) {
468 this.log(blockMap, "Before BlockOrder");
469 }
470 computeBlockOrder(blockMap);
471 fixLoopBits(blockMap);
472
473 assert verify();
474
475 startBlock = blockMap[0];
476 if (Debug.isLogEnabled()) {
477 this.log(blockMap, "Before LivenessAnalysis");
478 }
479 }
480
481 private boolean verify() {
482 for (BciBlock block : blocks) {
483 assert blocks[block.getId()] == block;
484
485 for (int i = 0; i < block.getSuccessorCount(); i++) {
486 BciBlock sux = block.getSuccessor(i);
487 if (sux instanceof ExceptionDispatchBlock) {
488 assert i == block.getSuccessorCount() - 1 : "Only one exception handler allowed, and it must be last in successors list";
489 }
490 }
491 }
492
493 return true;
494 }
495
496 private void makeExceptionEntries(BciBlock[] blockMap) {
686
687 private static void addSuccessor(BciBlock[] blockMap, int predBci, BciBlock sux) {
688 BciBlock predecessor = blockMap[predBci];
689 if (sux.isExceptionEntry) {
690 throw new PermanentBailoutException("Exception handler can be reached by both normal and exceptional control flow");
691 }
692 predecessor.addSuccessor(sux);
693 }
694
695 private final ArrayList<BciBlock> jsrVisited = new ArrayList<>();
696
697 private void createJsrAlternatives(BciBlock[] blockMap, BciBlock block) {
698 jsrVisited.add(block);
699 JsrScope scope = block.getJsrScope();
700
701 if (block.endsWithRet()) {
702 block.setRetSuccessor(blockMap[scope.nextReturnAddress()]);
703 block.addSuccessor(block.getRetSuccessor());
704 assert block.getRetSuccessor() != block.getJsrSuccessor();
705 }
706 Debug.log("JSR alternatives block %s sux %s jsrSux %s retSux %s jsrScope %s", block, block.getSuccessors(), block.getJsrSuccessor(), block.getRetSuccessor(), block.getJsrScope());
707
708 if (block.getJsrSuccessor() != null || !scope.isEmpty()) {
709 for (int i = 0; i < block.getSuccessorCount(); i++) {
710 BciBlock successor = block.getSuccessor(i);
711 JsrScope nextScope = scope;
712 if (successor == block.getJsrSuccessor()) {
713 nextScope = scope.push(block.getJsrReturnBci());
714 }
715 if (successor == block.getRetSuccessor()) {
716 nextScope = scope.pop();
717 }
718 if (!successor.getJsrScope().isPrefixOf(nextScope)) {
719 throw new JsrNotSupportedBailout("unstructured control flow (" + successor.getJsrScope() + " " + nextScope + ")");
720 }
721 if (!nextScope.isEmpty()) {
722 BciBlock clone;
723 if (successor.getJsrAlternatives() != null && successor.getJsrAlternatives().containsKey(nextScope)) {
724 clone = successor.getJsrAlternatives().get(nextScope);
725 } else {
726 successor.initJsrAlternatives();
853 private int handleLoopHeader(BciBlock[] newBlocks, int nextStart, int i, BciBlock loopHeader) {
854 int next = nextStart;
855 int endOfLoop = nextStart - 1;
856 for (int j = i + 1; j < blocks.length; ++j) {
857 BciBlock other = blocks[j];
858 if (other != null && (other.loops & (1L << loopHeader.loopId)) != 0) {
859 other.setId(next);
860 endOfLoop = next;
861 newBlocks[next++] = other;
862 blocks[j] = null;
863 if (other.isLoopHeader) {
864 next = handleLoopHeader(newBlocks, next, j, other);
865 }
866 }
867 }
868 loopHeader.loopEnd = endOfLoop;
869 return next;
870 }
871
872 public void log(BciBlock[] blockMap, String name) {
873 if (Debug.isLogEnabled()) {
874 String n = System.lineSeparator();
875 StringBuilder sb = new StringBuilder(Debug.currentScope()).append("BlockMap ").append(name).append(" :");
876 sb.append(n);
877 Iterable<BciBlock> it;
878 if (blocks == null) {
879 it = new HashSet<>(Arrays.asList(blockMap));
880 } else {
881 it = Arrays.asList(blocks);
882 }
883 for (BciBlock b : it) {
884 if (b == null) {
885 continue;
886 }
887 sb.append("B").append(b.getId()).append(" (").append(b.startBci).append(" -> ").append(b.endBci).append(")");
888 if (b.isLoopHeader) {
889 sb.append(" LoopHeader");
890 }
891 if (b.isExceptionEntry) {
892 sb.append(" ExceptionEntry");
893 }
894 sb.append(n).append(" Sux : ");
895 for (BciBlock s : b.getSuccessors()) {
896 sb.append("B").append(s.getId()).append(" (").append(s.startBci).append(" -> ").append(s.endBci).append(")");
897 if (s.isExceptionEntry) {
898 sb.append("!");
899 }
900 sb.append(" ");
901 }
902 sb.append(n).append(" Loop : ");
903 for (int pos : b.loopIdIterable()) {
904 sb.append("B").append(loopHeaders[pos].getId()).append(" ");
905 }
906 sb.append(n);
907 }
908 Debug.log("%s", sb);
909 }
910 }
911
912 /**
913 * Get the header block for a loop index.
914 */
915 public BciBlock getLoopHeader(int index) {
916 return loopHeaders[index];
917 }
918
919 /**
920 * The next available loop number.
921 */
922 private int nextLoop;
923
924 /**
925 * Mark the block as a loop header, using the next available loop number. Also checks for corner
926 * cases that we don't want to compile.
927 */
928 private void makeLoopHeader(BciBlock block) {
929 if (!block.isLoopHeader) {
930 block.isLoopHeader = true;
931
932 if (block.isExceptionEntry) {
933 // Loops that are implicitly formed by an exception handler lead to all sorts of
934 // corner cases.
935 // Don't compile such methods for now, until we see a concrete case that allows
936 // checking for correctness.
937 throw new PermanentBailoutException("Loop formed by an exception handler");
938 }
939 if (nextLoop >= LOOP_HEADER_MAX_CAPACITY) {
940 // This restriction can be removed by using a fall-back to a BitSet in case we have
941 // more than 64 loops
942 // Don't compile such methods for now, until we see a concrete case that allows
943 // checking for correctness.
944 throw new PermanentBailoutException("Too many loops in method");
945 }
946
947 assert block.loops == 0;
948 block.loops = 1L << nextLoop;
949 Debug.log("makeLoopHeader(%s) -> %x", block, block.loops);
950 if (loopHeaders == null) {
951 loopHeaders = new BciBlock[LOOP_HEADER_INITIAL_CAPACITY];
952 } else if (nextLoop >= loopHeaders.length) {
953 loopHeaders = Arrays.copyOf(loopHeaders, LOOP_HEADER_MAX_CAPACITY);
954 }
955 loopHeaders[nextLoop] = block;
956 block.loopId = nextLoop;
957 nextLoop++;
958 }
959 assert Long.bitCount(block.loops) == 1;
960 }
961
962 /**
963 * Depth-first traversal of the control flow graph. The flag {@linkplain BciBlock#visited} is
964 * used to visit every block only once. The flag {@linkplain BciBlock#active} is used to detect
965 * cycles (backward edges).
966 */
967 private long computeBlockOrder(BciBlock block) {
968 if (block.visited) {
969 if (block.active) {
975 return block.loops & ~(1L << block.loopId);
976 } else {
977 return block.loops;
978 }
979 }
980
981 block.visited = true;
982 block.active = true;
983
984 long loops = 0;
985 for (BciBlock successor : block.getSuccessors()) {
986 // Recursively process successors.
987 loops |= computeBlockOrder(successor);
988 if (successor.active) {
989 // Reached block via backward branch.
990 loops |= (1L << successor.loopId);
991 }
992 }
993
994 block.loops = loops;
995 Debug.log("computeBlockOrder(%s) -> %x", block, block.loops);
996
997 if (block.isLoopHeader) {
998 loops &= ~(1L << block.loopId);
999 }
1000
1001 block.active = false;
1002 blocksNotYetAssignedId--;
1003 blocks[blocksNotYetAssignedId] = block;
1004
1005 return loops;
1006 }
1007
1008 private long fixLoopBits(BciBlock[] blockMap, BciBlock block) {
1009 if (block.visited) {
1010 // Return cached loop information for this block.
1011 if (block.isLoopHeader) {
1012 return block.loops & ~(1L << block.loopId);
1013 } else {
1014 return block.loops;
1015 }
1016 }
1017
1018 block.visited = true;
1019 long loops = block.loops;
1020 for (BciBlock successor : block.getSuccessors()) {
1021 // Recursively process successors.
1022 loops |= fixLoopBits(blockMap, successor);
1023 }
1024 if (block.loops != loops) {
1025 loopChanges = true;
1026 block.loops = loops;
1027 Debug.log("fixLoopBits0(%s) -> %x", block, block.loops);
1028 }
1029
1030 if (block.isLoopHeader) {
1031 loops &= ~(1L << block.loopId);
1032 }
1033
1034 return loops;
1035 }
1036
1037 public static BciBlockMapping create(BytecodeStream stream, Bytecode code, OptionValues options) {
1038 BciBlockMapping map = new BciBlockMapping(code);
1039 map.build(stream, options);
1040 if (Debug.isDumpEnabled(Debug.INFO_LEVEL)) {
1041 Debug.dump(Debug.INFO_LEVEL, map, code.getMethod().format("After block building %f %R %H.%n(%P)"));
1042 }
1043
1044 return map;
1045 }
1046
1047 public BciBlock[] getLoopHeaders() {
1048 return loopHeaders;
1049 }
1050
1051 public BciBlock getStartBlock() {
1052 return startBlock;
1053 }
1054
1055 public ExceptionDispatchBlock getUnwindBlock() {
1056 return (ExceptionDispatchBlock) blocks[blocks.length - 1];
1057 }
1058
1059 public int getLoopCount() {
1060 return nextLoop;
1061 }
|
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>
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) {
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();
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) {
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 }
|