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