/*

 * Copyright (c) 2009, 2015, 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.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.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.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.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.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.LOOKUPSWITCH;

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

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

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.HashSet;

import java.util.Iterator;

import java.util.List;

import java.util.TreeSet;

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 {

        protected int id;

        public int startBci;

        public int endBci;

        public boolean isExceptionEntry;

        public boolean isLoopHeader;

        public int loopId;

        public int loopEnd;

        protected List<BciBlock> successors;

        private int predecessorCount;

        private boolean visited;

        private boolean active;

        public long loops;

        public 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;

                }

            }

        }

        public BciBlock() {

            this.successors = new ArrayList<>(4);

        }

        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) {

                sb.append(' ');

                if (isLoopHeader) {

                    sb.append('L');

                }

                if (isExceptionEntry) {

                    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 static class ExceptionDispatchBlock extends BciBlock {

        public ExceptionHandler handler;

        public int deoptBci;

    }

    /**

     * 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)) {

                throw new JsrNotSupportedBailout("jsr/ret parsing disabled");

            }

            createJsrAlternatives(blockMap, blockMap[0]);

        }

        if (debug.isLogEnabled()) {

            this.log(blockMap, "Before BlockOrder");

        }

        computeBlockOrder(blockMap);

        fixLoopBits(blockMap);

        assert verify();

        startBlock = blockMap[0];

        if (debug.isLogEnabled()) {

            this.log(blockMap, "Before LivenessAnalysis");

        }

    }

    private boolean verify() {

        for (BciBlock block : blocks) {

            assert blocks[block.getId()] == block;

            for (int i = 0; i < block.getSuccessorCount(); i++) {

                BciBlock sux = block.getSuccessor(i);

                if (sux instanceof ExceptionDispatchBlock) {

                    assert i == block.getSuccessorCount() - 1 : "Only one exception handler allowed, and it must be last in successors list";

                }

            }

        }

        return true;

    }

    private void makeExceptionEntries(BciBlock[] blockMap) {

        // start basic blocks at all exception handler blocks and mark them as exception entries

        for (ExceptionHandler h : this.exceptionHandlers) {

            BciBlock xhandler = makeBlock(blockMap, h.getHandlerBCI());

            xhandler.isExceptionEntry = true;

        }

    }

    private void iterateOverBytecodes(BciBlock[] blockMap, BytecodeStream stream) {

        // iterate over the bytecodes top to bottom.

        // mark the entrypoints of basic blocks and build lists of successors for

        // all bytecodes that end basic blocks (i.e. goto, ifs, switches, throw, jsr, returns, ret)

        BciBlock current = null;

        stream.setBCI(0);

        while (stream.currentBC() != Bytecodes.END) {

            int bci = stream.currentBCI();

            if (current == null || blockMap[bci] != null) {

                BciBlock b = makeBlock(blockMap, bci);

                if (current != null) {

                    addSuccessor(blockMap, current.endBci, b);

                }

                current = b;

            }

            blockMap[bci] = current;

            current.endBci = bci;

            switch (stream.currentBC()) {

                case IRETURN: // fall through

                case LRETURN: // fall through

                case FRETURN: // fall through

                case DRETURN: // fall through