/*

 * Copyright (c) 2009, 2018, Oracle and/or its affiliates. All rights reserved.

 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

 *

 * This code is free software; you can redistribute it and/or modify it

 * under the terms of the GNU General Public License version 2 only, as

 * published by the Free Software Foundation.

 *

 * This code is distributed in the hope that it will be useful, but WITHOUT

 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

 * version 2 for more details (a copy is included in the LICENSE file that

 * accompanied this code).

 *

 * You should have received a copy of the GNU General Public License version

 * 2 along with this work; if not, write to the Free Software Foundation,

 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

 *

 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

 * or visit www.oracle.com if you need additional information or have any

 * questions.

 */

package org.graalvm.compiler.java;

import static org.graalvm.compiler.bytecode.Bytecodes.AALOAD;

import static org.graalvm.compiler.bytecode.Bytecodes.AASTORE;

import static org.graalvm.compiler.bytecode.Bytecodes.ANEWARRAY;

import static org.graalvm.compiler.bytecode.Bytecodes.ARETURN;

import static org.graalvm.compiler.bytecode.Bytecodes.ARRAYLENGTH;

import static org.graalvm.compiler.bytecode.Bytecodes.ATHROW;

import static org.graalvm.compiler.bytecode.Bytecodes.BALOAD;

import static org.graalvm.compiler.bytecode.Bytecodes.BASTORE;

import static org.graalvm.compiler.bytecode.Bytecodes.CALOAD;

import static org.graalvm.compiler.bytecode.Bytecodes.CASTORE;

import static org.graalvm.compiler.bytecode.Bytecodes.CHECKCAST;

import static org.graalvm.compiler.bytecode.Bytecodes.DALOAD;

import static org.graalvm.compiler.bytecode.Bytecodes.DASTORE;

import static org.graalvm.compiler.bytecode.Bytecodes.DRETURN;

import static org.graalvm.compiler.bytecode.Bytecodes.FALOAD;

import static org.graalvm.compiler.bytecode.Bytecodes.FASTORE;

import static org.graalvm.compiler.bytecode.Bytecodes.FRETURN;

import static org.graalvm.compiler.bytecode.Bytecodes.GETFIELD;

import static org.graalvm.compiler.bytecode.Bytecodes.GETSTATIC;

import static org.graalvm.compiler.bytecode.Bytecodes.GOTO;

import static org.graalvm.compiler.bytecode.Bytecodes.GOTO_W;

import static org.graalvm.compiler.bytecode.Bytecodes.IALOAD;

import static org.graalvm.compiler.bytecode.Bytecodes.IASTORE;

import static org.graalvm.compiler.bytecode.Bytecodes.IDIV;

import static org.graalvm.compiler.bytecode.Bytecodes.IFEQ;

import static org.graalvm.compiler.bytecode.Bytecodes.IFGE;

import static org.graalvm.compiler.bytecode.Bytecodes.IFGT;

import static org.graalvm.compiler.bytecode.Bytecodes.IFLE;

import static org.graalvm.compiler.bytecode.Bytecodes.IFLT;

import static org.graalvm.compiler.bytecode.Bytecodes.IFNE;

import static org.graalvm.compiler.bytecode.Bytecodes.IFNONNULL;

import static org.graalvm.compiler.bytecode.Bytecodes.IFNULL;

import static org.graalvm.compiler.bytecode.Bytecodes.IF_ACMPEQ;

import static org.graalvm.compiler.bytecode.Bytecodes.IF_ACMPNE;

import static org.graalvm.compiler.bytecode.Bytecodes.IF_ICMPEQ;

import static org.graalvm.compiler.bytecode.Bytecodes.IF_ICMPGE;

import static org.graalvm.compiler.bytecode.Bytecodes.IF_ICMPGT;

import static org.graalvm.compiler.bytecode.Bytecodes.IF_ICMPLE;

import static org.graalvm.compiler.bytecode.Bytecodes.IF_ICMPLT;

import static org.graalvm.compiler.bytecode.Bytecodes.IF_ICMPNE;

import static org.graalvm.compiler.bytecode.Bytecodes.INVOKEDYNAMIC;

import static org.graalvm.compiler.bytecode.Bytecodes.INVOKEINTERFACE;

import static org.graalvm.compiler.bytecode.Bytecodes.INVOKESPECIAL;

import static org.graalvm.compiler.bytecode.Bytecodes.INVOKESTATIC;

import static org.graalvm.compiler.bytecode.Bytecodes.INVOKEVIRTUAL;

import static org.graalvm.compiler.bytecode.Bytecodes.IREM;

import static org.graalvm.compiler.bytecode.Bytecodes.IRETURN;

import static org.graalvm.compiler.bytecode.Bytecodes.JSR;

import static org.graalvm.compiler.bytecode.Bytecodes.JSR_W;

import static org.graalvm.compiler.bytecode.Bytecodes.LALOAD;

import static org.graalvm.compiler.bytecode.Bytecodes.LASTORE;

import static org.graalvm.compiler.bytecode.Bytecodes.LDC;

import static org.graalvm.compiler.bytecode.Bytecodes.LDC2_W;

import static org.graalvm.compiler.bytecode.Bytecodes.LDC_W;

import static org.graalvm.compiler.bytecode.Bytecodes.LDIV;

import static org.graalvm.compiler.bytecode.Bytecodes.LOOKUPSWITCH;

import static org.graalvm.compiler.bytecode.Bytecodes.LREM;

import static org.graalvm.compiler.bytecode.Bytecodes.LRETURN;

import static org.graalvm.compiler.bytecode.Bytecodes.MULTIANEWARRAY;

import static org.graalvm.compiler.bytecode.Bytecodes.NEW;

import static org.graalvm.compiler.bytecode.Bytecodes.PUTFIELD;

import static org.graalvm.compiler.bytecode.Bytecodes.PUTSTATIC;

import static org.graalvm.compiler.bytecode.Bytecodes.RET;

import static org.graalvm.compiler.bytecode.Bytecodes.RETURN;

import static org.graalvm.compiler.bytecode.Bytecodes.SALOAD;

import static org.graalvm.compiler.bytecode.Bytecodes.SASTORE;

import static org.graalvm.compiler.bytecode.Bytecodes.TABLESWITCH;

import static org.graalvm.compiler.core.common.GraalOptions.SupportJsrBytecodes;

import java.util.ArrayList;

import java.util.Arrays;

import java.util.Collection;

import java.util.Iterator;

import java.util.List;

import java.util.TreeSet;

import jdk.internal.vm.compiler.collections.EconomicMap;

import jdk.internal.vm.compiler.collections.Equivalence;

import org.graalvm.compiler.bytecode.Bytecode;

import org.graalvm.compiler.bytecode.BytecodeLookupSwitch;

import org.graalvm.compiler.bytecode.BytecodeStream;

import org.graalvm.compiler.bytecode.BytecodeSwitch;

import org.graalvm.compiler.bytecode.BytecodeTableSwitch;

import org.graalvm.compiler.bytecode.Bytecodes;

import org.graalvm.compiler.core.common.PermanentBailoutException;

import org.graalvm.compiler.debug.DebugContext;

import org.graalvm.compiler.options.OptionValues;

import jdk.vm.ci.code.BytecodeFrame;

import jdk.vm.ci.meta.ExceptionHandler;

/**

 * Builds a mapping between bytecodes and basic blocks and builds a conservative control flow graph

 * (CFG). It makes one linear passes over the bytecodes to build the CFG where it detects block

 * headers and connects them.

 * <p>

 * It also creates exception dispatch blocks for exception handling. These blocks are between a

 * bytecode that might throw an exception, and the actual exception handler entries, and are later

 * used to create the type checks with the exception handler catch types. If a bytecode is covered

 * by an exception handler, this bytecode ends the basic block. This guarantees that a) control flow

 * cannot be transferred to an exception dispatch block in the middle of a block, and b) that every

 * block has at most one exception dispatch block (which is always the last entry in the successor

 * list).

 * <p>

 * If a bytecode is covered by multiple exception handlers, a chain of exception dispatch blocks is

 * created so that multiple exception handler types can be checked. The chains are re-used if

 * multiple bytecodes are covered by the same exception handlers.

 * <p>

 * Note that exception unwinds, i.e., bytecodes that can throw an exception but the exception is not

 * handled in this method, do not end a basic block. Not modeling the exception unwind block reduces

 * the complexity of the CFG, and there is no algorithm yet where the exception unwind block would

 * matter.

 * <p>

 * The class also handles subroutines (jsr and ret bytecodes): subroutines are inlined by

 * duplicating the subroutine blocks. This is limited to simple, structured subroutines with a

 * maximum subroutine nesting of 4. Otherwise, a bailout is thrown.

 * <p>

 * Loops in the methods are detected. If a method contains an irreducible loop (a loop with more

 * than one entry), a bailout is thrown. This simplifies the compiler later on since only structured

 * loops need to be supported.

 * <p>

 * A data flow analysis computes the live local variables from the point of view of the interpreter.

 * The result is used later to prune frame states, i.e., remove local variable entries that are

 * guaranteed to be never used again (even in the case of deoptimization).

 * <p>

 * The algorithms and analysis in this class are conservative and do not use any assumptions or

 * profiling information.

 */

public final class BciBlockMapping {

    public static class BciBlock implements Cloneable {

        int id;

        final int startBci;

        int endBci;

        private boolean isExceptionEntry;

        private boolean isLoopHeader;

        int loopId;

        int loopEnd;

        List<BciBlock> successors;

        private int predecessorCount;

        private boolean visited;

        private boolean active;

        long loops;

        JSRData jsrData;

        public static class JSRData implements Cloneable {

            public EconomicMap<JsrScope, BciBlock> jsrAlternatives;

            public JsrScope jsrScope = JsrScope.EMPTY_SCOPE;

            public BciBlock jsrSuccessor;

            public int jsrReturnBci;

            public BciBlock retSuccessor;

            public boolean endsWithRet = false;

            public JSRData copy() {

                try {

                    return (JSRData) this.clone();

                } catch (CloneNotSupportedException e) {

                    return null;

                }

            }

        }

        BciBlock(int startBci) {

            this.startBci = startBci;

            this.successors = new ArrayList<>();

        }

        public int getStartBci() {

            return startBci;

        }

        public int getEndBci() {

            return endBci;

        }

        public long getLoops() {

            return loops;

        }

        public BciBlock exceptionDispatchBlock() {

            if (successors.size() > 0 && successors.get(successors.size() - 1) instanceof ExceptionDispatchBlock) {

                return successors.get(successors.size() - 1);

            }

            return null;

        }

        public int getId() {

            return id;

        }

        public int getPredecessorCount() {

            return this.predecessorCount;

        }

        public int numNormalSuccessors() {

            if (exceptionDispatchBlock() != null) {

                return successors.size() - 1;

            }

            return successors.size();

        }

        public BciBlock copy() {

            try {

                BciBlock block = (BciBlock) super.clone();

                if (block.jsrData != null) {

                    block.jsrData = block.jsrData.copy();

                }

                block.successors = new ArrayList<>(successors);

                return block;

            } catch (CloneNotSupportedException e) {

                throw new RuntimeException(e);

            }

        }

        @Override

        public String toString() {

            StringBuilder sb = new StringBuilder("B").append(getId());

            sb.append('[').append(startBci).append("..").append(endBci);

            if (isLoopHeader || isExceptionEntry || this instanceof ExceptionDispatchBlock) {

                sb.append(' ');

                if (isLoopHeader) {

                    sb.append('L');

                }

                if (isExceptionEntry) {

                    sb.append('!');

                } else if (this instanceof ExceptionDispatchBlock) {

                    sb.append("<!>");

                }

            }

            sb.append(']');

            return sb.toString();

        }

        public int getLoopDepth() {

            return Long.bitCount(loops);

        }

        public boolean isLoopHeader() {

            return isLoopHeader;

        }

        public boolean isExceptionEntry() {

            return isExceptionEntry;

        }

        public BciBlock getSuccessor(int index) {

            return successors.get(index);

        }

        /**

         * Get the loop id of the inner most loop.

         *

         * @return the loop id of the most inner loop or -1 if not part of any loop

         */

        public int getLoopId() {

            long l = loops;

            if (l == 0) {

                return -1;

            }

            int pos = 0;

            for (int lMask = 1; (l & lMask) == 0; lMask = lMask << 1) {

                pos++;

            }

            return pos;

        }

        /**

         * Iterate over loop ids.

         */

        public Iterable<Integer> loopIdIterable() {

            return new Iterable<Integer>() {

                @Override

                public Iterator<Integer> iterator() {

                    return idIterator(loops);

                }

            };

        }

        private static Iterator<Integer> idIterator(long field) {

            return new Iterator<Integer>() {

                long l = field;

                int pos = 0;

                int lMask = 1;

                @Override

                public Integer next() {

                    for (; (l & lMask) == 0; lMask = lMask << 1) {

                        pos++;

                    }

                    l &= ~lMask;

                    return pos;

                }

                @Override

                public boolean hasNext() {

                    return l != 0;

                }

            };

        }

        public double probability() {

            return 1D;

        }

        public BciBlock getPostdominator() {

            return null;

        }

        private JSRData getOrCreateJSRData() {

            if (jsrData == null) {

                jsrData = new JSRData();

            }

            return jsrData;

        }

        void setEndsWithRet() {

            getOrCreateJSRData().endsWithRet = true;

        }

        public JsrScope getJsrScope() {

            if (this.jsrData == null) {

                return JsrScope.EMPTY_SCOPE;

            } else {

                return jsrData.jsrScope;

            }

        }

        public boolean endsWithRet() {

            if (this.jsrData == null) {

                return false;

            } else {

                return jsrData.endsWithRet;

            }

        }

        void setRetSuccessor(BciBlock bciBlock) {

            this.getOrCreateJSRData().retSuccessor = bciBlock;

        }

        public BciBlock getRetSuccessor() {

            if (this.jsrData == null) {

                return null;

            } else {

                return jsrData.retSuccessor;

            }

        }

        public BciBlock getJsrSuccessor() {

            if (this.jsrData == null) {

                return null;

            } else {

                return jsrData.jsrSuccessor;

            }

        }

        public int getJsrReturnBci() {

            if (this.jsrData == null) {

                return -1;

            } else {

                return jsrData.jsrReturnBci;

            }

        }

        public EconomicMap<JsrScope, BciBlock> getJsrAlternatives() {

            if (this.jsrData == null) {

                return null;

            } else {

                return jsrData.jsrAlternatives;

            }

        }

        public void initJsrAlternatives() {

            JSRData data = this.getOrCreateJSRData();

            if (data.jsrAlternatives == null) {

                data.jsrAlternatives = EconomicMap.create(Equivalence.DEFAULT);

            }

        }

        void setJsrScope(JsrScope nextScope) {

            this.getOrCreateJSRData().jsrScope = nextScope;

        }

        void setJsrSuccessor(BciBlock clone) {

            this.getOrCreateJSRData().jsrSuccessor = clone;

        }

        void setJsrReturnBci(int bci) {

            this.getOrCreateJSRData().jsrReturnBci = bci;

        }

        public int getSuccessorCount() {

            return successors.size();

        }

        public List<BciBlock> getSuccessors() {

            return successors;

        }

        void setId(int i) {

            this.id = i;

        }

        public void addSuccessor(BciBlock sux) {

            successors.add(sux);

            sux.predecessorCount++;

        }

        public void clearSucccessors() {

            for (BciBlock sux : successors) {

                sux.predecessorCount--;

            }

            successors.clear();

        }

        public boolean isExceptionDispatch() {

            return false;

        }

    }

    public static class ExceptionDispatchBlock extends BciBlock {

        public final ExceptionHandler handler;

        public final int deoptBci;

        /**

         * Constructor for a normal dispatcher.

         */

        ExceptionDispatchBlock(ExceptionHandler handler, int deoptBci) {

            super(handler.getHandlerBCI());

            this.endBci = startBci;

            this.deoptBci = deoptBci;

            this.handler = handler;

        }

        /**

         * Constructor for the method unwind dispatcher.

         */

        ExceptionDispatchBlock(int deoptBci) {

            super(deoptBci);

            this.endBci = deoptBci;

            this.deoptBci = deoptBci;

            this.handler = null;

        }

        @Override

        public boolean isExceptionDispatch() {

            return true;

        }

    }

    /**

     * The blocks found in this method, in reverse postorder.

     */

    private BciBlock[] blocks;

    public final Bytecode code;

    public boolean hasJsrBytecodes;

    private final ExceptionHandler[] exceptionHandlers;

    private BciBlock startBlock;

    private BciBlock[] loopHeaders;

    private static final int LOOP_HEADER_MAX_CAPACITY = Long.SIZE;

    private static final int LOOP_HEADER_INITIAL_CAPACITY = 4;

    private int blocksNotYetAssignedId;

    private final DebugContext debug;

    /**

     * Creates a new BlockMap instance from {@code code}.

     */

    private BciBlockMapping(Bytecode code, DebugContext debug) {

        this.code = code;

        this.debug = debug;

        this.exceptionHandlers = code.getExceptionHandlers();

    }

    public BciBlock[] getBlocks() {

        return this.blocks;

    }

    /**

     * Builds the block map and conservative CFG and numbers blocks.

     */

    public void build(BytecodeStream stream, OptionValues options) {

        int codeSize = code.getCodeSize();

        BciBlock[] blockMap = new BciBlock[codeSize];

        makeExceptionEntries(blockMap);

        iterateOverBytecodes(blockMap, stream);

        if (hasJsrBytecodes) {

            if (!SupportJsrBytecodes.getValue(options)) {