Frame

package mockit.asm.controlFlow;

import static mockit.asm.controlFlow.FrameTypeMask.ARRAY_OF;
import static mockit.asm.controlFlow.FrameTypeMask.BASE;
import static mockit.asm.controlFlow.FrameTypeMask.BASE_KIND;
import static mockit.asm.controlFlow.FrameTypeMask.BASE_VALUE;
import static mockit.asm.controlFlow.FrameTypeMask.BOOLEAN;
import static mockit.asm.controlFlow.FrameTypeMask.BYTE;
import static mockit.asm.controlFlow.FrameTypeMask.CHAR;
import static mockit.asm.controlFlow.FrameTypeMask.DIM;
import static mockit.asm.controlFlow.FrameTypeMask.DOUBLE;
import static mockit.asm.controlFlow.FrameTypeMask.ELEMENT_OF;
import static mockit.asm.controlFlow.FrameTypeMask.FLOAT;
import static mockit.asm.controlFlow.FrameTypeMask.INTEGER;
import static mockit.asm.controlFlow.FrameTypeMask.KIND;
import static mockit.asm.controlFlow.FrameTypeMask.LOCAL;
import static mockit.asm.controlFlow.FrameTypeMask.LONG;
import static mockit.asm.controlFlow.FrameTypeMask.NULL;
import static mockit.asm.controlFlow.FrameTypeMask.OBJECT;
import static mockit.asm.controlFlow.FrameTypeMask.SHORT;
import static mockit.asm.controlFlow.FrameTypeMask.STACK;
import static mockit.asm.controlFlow.FrameTypeMask.TOP;
import static mockit.asm.controlFlow.FrameTypeMask.TOP_IF_LONG_OR_DOUBLE;
import static mockit.asm.controlFlow.FrameTypeMask.UNINITIALIZED;
import static mockit.asm.controlFlow.FrameTypeMask.UNINITIALIZED_THIS;
import static mockit.asm.controlFlow.FrameTypeMask.VALUE;
import static mockit.asm.jvmConstants.Opcodes.*;

import edu.umd.cs.findbugs.annotations.NonNull;
import edu.umd.cs.findbugs.annotations.Nullable;

import mockit.asm.constantPool.ConstantPoolGeneration;
import mockit.asm.constantPool.DynamicItem;
import mockit.asm.constantPool.Item;
import mockit.asm.constantPool.StringItem;
import mockit.asm.constantPool.TypeOrMemberItem;
import mockit.asm.jvmConstants.Access;
import mockit.asm.jvmConstants.ArrayElementType;
import mockit.asm.jvmConstants.ConstantPoolTypes;
import mockit.asm.types.ArrayType;
import mockit.asm.types.JavaType;
import mockit.asm.types.PrimitiveType;

import org.checkerframework.checker.index.qual.NonNegative;

/**
 * Information about the input and output stack map frames of a basic block.
 * <p>
 * Frames are computed in a two steps process: during the visit of each instruction, the state of the frame at the end
 * of current basic block is updated by simulating the action of the instruction on the previous state of this so called
 * "output frame". In visitMaxStack, a fix point algorithm is used to compute the "input frame" of each basic block,
 * i.e. the stack map frame at the beginning of the basic block, starting from the input frame of the first basic block
 * (which is computed from the method descriptor), and by using the previously computed output frames to compute the
 * input state of the other blocks.
 * <p>
 * All output and input frames are stored as arrays of integers. Reference and array types are represented by an index
 * into a type table (which is not the same as the constant pool of the class, in order to avoid adding unnecessary
 * constants in the pool - not all computed frames will end up being stored in the stack map table). This allows very
 * fast type comparisons.
 * <p>
 * Output stack map frames are computed relatively to the input frame of the basic block, which is not yet known when
 * output frames are computed. It is therefore necessary to be able to represent abstract types such as "the type at
 * position x in the input frame locals" or "the type at position x from the top of the input frame stack" or even "the
 * type at position x in the input frame, with y more (or less) array dimensions". This explains the rather complicated
 * type format used in output frames.
 * <p>
 * This format is the following: DIM KIND VALUE (4, 4 and 24 bits). DIM is a signed number of array dimensions (from -8
 * to 7). KIND is either BASE, LOCAL or STACK. BASE is used for types that are not relative to the input frame. LOCAL is
 * used for types that are relative to the input local variable types. STACK is used for types that are relative to the
 * input stack types. VALUE depends on KIND. For LOCAL types, it is an index in the input local variable types. For
 * STACK types, it is a position relatively to the top of input frame stack. For BASE types, it is either one of the
 * constants defined below, or for OBJECT and UNINITIALIZED types, a tag and an index in the type table.
 * <p>
 * Output frames can contain types of any kind and with a positive or negative dimension (and even unassigned types,
 * represented by 0 - which does not correspond to any valid type value). Input frames can only contain BASE types of
 * positive or null dimension. In all cases the type table contains only internal type names (array type descriptors are
 * forbidden - dimensions must be represented through the DIM field).
 * <p>
 * The LONG and DOUBLE types are always represented by using two slots (LONG + TOP or DOUBLE + TOP), for local variable
 * types as well as in the operand stack. This is necessary to be able to simulate DUPx_y instructions, whose effect
 * would be dependent on the actual type values if types were always represented by a single slot in the stack (and this
 * is not possible, since actual type values are not always known - cf LOCAL and STACK type kinds).
 */
public final class Frame {
    private static final int[] EMPTY_INPUT_STACK = {};

    @NonNull
    private final ConstantPoolGeneration cp;

    /**
     * The label (i.e. basic block) to which these input and output stack map frames correspond.
     */
    @NonNull
    final Label owner;

    /**
     * The input stack map frame locals.
     */
    int[] inputLocals;

    /**
     * The input stack map frame stack.
     */
    int[] inputStack;

    /**
     * The output stack map frame locals.
     */
    @Nullable
    private int[] outputLocals;

    /**
     * The output stack map frame stack.
     */
    private int[] outputStack;

    /**
     * Relative size of the output stack. The exact semantics of this field depends on the algorithm that is used.
     * <p>
     * When only the maximum stack size is computed, this field is the size of the output stack relatively to the top of
     * the input stack.
     * <p>
     * When the stack map frames are completely computed, this field is the actual number of types in
     * {@link #outputStack}.
     */
    @NonNegative
    private int outputStackTop;

    /**
     * Number of types that are initialized in the basic block.
     *
     * @see #initializations
     */
    private int initializationCount;

    /**
     * The types that are initialized in the basic block. A constructor invocation on an UNINITIALIZED or
     * UNINITIALIZED_THIS type must replace <em>every occurrence</em> of this type in the local variables and in the
     * operand stack. This cannot be done during the first phase of the algorithm since, during this phase, the local
     * variables and the operand stack are not completely computed. It is therefore necessary to store the types on
     * which constructors are invoked in the basic block, in order to do this replacement during the second phase of the
     * algorithm, where the frames are fully computed. Note that this array can contain types that are relative to input
     * locals or to the input stack.
     */
    private int[] initializations;

    Frame(@NonNull ConstantPoolGeneration cp, @NonNull Label owner) {
        this.cp = cp;
        this.owner = owner;
    }

    /**
     * Initializes the input frame of the first basic block from the method descriptor.
     *
     * @param access
     *            the access flags of the method to which this label belongs.
     * @param args
     *            the formal parameter types of this method.
     * @param maxLocals
     *            the maximum number of local variables of this method.
     */
    void initInputFrame(@NonNull String classDesc, int access, @NonNull JavaType[] args, @NonNegative int maxLocals) {
        inputLocals = new int[maxLocals];
        inputStack = EMPTY_INPUT_STACK;

        int localIndex = initializeThisParameterIfApplicable(classDesc, access);
        localIndex = initializeFormalParameterTypes(localIndex, args);

        while (localIndex < maxLocals) {
            inputLocals[localIndex] = TOP;
            localIndex++;
        }
    }

    @NonNegative
    private int initializeThisParameterIfApplicable(@NonNull String classDesc, int access) {
        if ((access & Access.STATIC) == 0) {
            inputLocals[0] = Access.isConstructor(access) ? UNINITIALIZED_THIS : OBJECT | cp.addNormalType(classDesc);
            return 1;
        }

        return 0;
    }

    @NonNegative
    private int initializeFormalParameterTypes(@NonNegative int localIndex, @NonNull JavaType[] args) {
        for (JavaType arg : args) {
            int typeEncoding = getTypeEncoding(arg.getDescriptor());
            inputLocals[localIndex] = typeEncoding;
            localIndex++;

            if (typeEncoding == LONG || typeEncoding == DOUBLE) {
                inputLocals[localIndex] = TOP;
                localIndex++;
            }
        }

        return localIndex;
    }

    /**
     * Returns the {@linkplain FrameTypeMask int encoding} of the given type.
     *
     * @param typeDesc
     *            a type descriptor
     *
     * @return the int encoding of the given type
     */
    @NonNegative
    private int getTypeEncoding(@NonNull String typeDesc) {
        int index = typeDesc.charAt(0) == '(' ? typeDesc.indexOf(')') + 1 : 0;

        switch (typeDesc.charAt(index)) {
            case 'V':
                return 0;
            case 'Z':
            case 'C':
            case 'B':
            case 'S':
            case 'I':
                return INTEGER;
            case 'F':
                return FLOAT;
            case 'J':
                return LONG;
            case 'D':
                return DOUBLE;
            case 'L':
                return getObjectTypeEncoding(typeDesc, index);
            case '[':
                return getArrayTypeEncoding(typeDesc, index);
            default:
                throw new IllegalArgumentException("Invalid type descriptor: " + typeDesc);
        }
    }

    @NonNegative
    private int getObjectTypeEncoding(@NonNull String typeDesc, @NonNegative int index) {
        // Stores the internal name, not the descriptor!
        String t = typeDesc.substring(index + 1, typeDesc.length() - 1);
        return OBJECT | cp.addNormalType(t);
    }

    @NonNegative
    private int getArrayTypeEncoding(@NonNull String typeDesc, @NonNegative int index) {
        int dims = getNumberOfDimensions(typeDesc, index);
        int data = getArrayElementTypeEncoding(typeDesc, index + dims);
        return dims << 28 | data;
    }

    @NonNegative
    private static int getNumberOfDimensions(@NonNull String typeDesc, @NonNegative int index) {
        int dims = 1;

        while (typeDesc.charAt(index + dims) == '[') {
            dims++;
        }

        return dims;
    }

    @NonNegative
    @SuppressWarnings("OverlyComplexMethod")
    private int getArrayElementTypeEncoding(@NonNull String typeDesc, @NonNegative int index) {
        switch (typeDesc.charAt(index)) {
            case 'Z':
                return BOOLEAN;
            case 'C':
                return CHAR;
            case 'B':
                return BYTE;
            case 'S':
                return SHORT;
            case 'I':
                return INTEGER;
            case 'F':
                return FLOAT;
            case 'J':
                return LONG;
            case 'D':
                return DOUBLE;
            case 'L':
                return getObjectTypeEncoding(typeDesc, index);
            default:
                throw new IllegalArgumentException("Invalid type descriptor: " + typeDesc);
        }
    }

    /**
     * Simulates the action of a IINC instruction on the output stack frame.
     */
    void executeIINC(@NonNegative int varIndex) {
        set(varIndex, INTEGER);
    }

    /**
     * Sets the output frame local variable type at the given index.
     *
     * @param local
     *            the index of the local that must be set
     * @param type
     *            the value of the local that must be set
     */
    private void set(@NonNegative int local, int type) {
        // Creates and/or resizes the output local variables array if necessary.
        if (outputLocals == null) {
            outputLocals = new int[10];
        }

        int n = outputLocals.length;

        if (local >= n) {
            int[] t = new int[Math.max(local + 1, 2 * n)];
            System.arraycopy(outputLocals, 0, t, 0, n);
            outputLocals = t;
        }

        // Sets the local variable.
        outputLocals[local] = type;
    }

    /**
     * Simulates the action of a BIPUSH, SIPUSH, or NEWARRAY instruction on the output stack frame.
     *
     * @param opcode
     *            the opcode of the instruction
     * @param operand
     *            the operand of the instruction, if any
     */
    void executeINT(@NonNegative int opcode, int operand) {
        if (opcode == NEWARRAY) {
            executeNewArray(operand);
        } else {
            push(INTEGER);
        }
    }

    private void executeNewArray(@NonNegative int arrayElementType) {
        pop();

        // noinspection SwitchStatementWithoutDefaultBranch
        switch (arrayElementType) {
            case ArrayElementType.BOOLEAN:
                push(ARRAY_OF | BOOLEAN);
                break;
            case ArrayElementType.CHAR:
                push(ARRAY_OF | CHAR);
                break;
            case ArrayElementType.BYTE:
                push(ARRAY_OF | BYTE);
                break;
            case ArrayElementType.SHORT:
                push(ARRAY_OF | SHORT);
                break;
            case ArrayElementType.INT:
                push(ARRAY_OF | INTEGER);
                break;
            case ArrayElementType.FLOAT:
                push(ARRAY_OF | FLOAT);
                break;
            case ArrayElementType.DOUBLE:
                push(ARRAY_OF | DOUBLE);
                break;
            case ArrayElementType.LONG:
                push(ARRAY_OF | LONG);
        }
    }

    /**
     * Pushes a new type onto the output frame stack.
     */
    private void push(int type) {
        // Creates and/or resizes the output stack array if necessary.
        if (outputStack == null) {
            outputStack = new int[10];
        }

        int n = outputStack.length;

        if (outputStackTop >= n) {
            int[] t = new int[Math.max(outputStackTop + 1, 2 * n)];
            System.arraycopy(outputStack, 0, t, 0, n);
            outputStack = t;
        }

        // Pushes the type on the output stack.
        outputStack[outputStackTop++] = type;

        owner.updateOutputStackMaxHeight(outputStackTop);
    }

    /**
     * Pops a type from the output frame stack and returns its value.
     */
    private int pop() {
        if (outputStackTop > 0) {
            return outputStack[--outputStackTop];
        }

        // If the output frame stack is empty, pops from the input stack.
        return STACK | -owner.decrementInputStackTop();
    }

    /**
     * Simulates the action of a LOOKUPSWITCH or TABLESWITCH instruction on the output stack frame.
     */
    void executeSWITCH() {
        pop(1);
    }

    /**
     * Pops the given number of types from the output frame stack.
     *
     * @param elements
     *            the number of types that must be popped.
     */
    private void pop(@NonNegative int elements) {
        if (outputStackTop >= elements) {
            outputStackTop -= elements;
        } else {
            // If the number of elements to be popped is greater than the number of elements in the output stack, clear
            // it,
            // and pops the remaining elements from the input stack.
            owner.decrementInputStackTop(elements - outputStackTop);
            outputStackTop = 0;
        }
    }

    /**
     * Pops a type from the output frame stack.
     *
     * @param desc
     *            the descriptor of the type to be popped. Can also be a method descriptor (in this case this method
     *            pops the types corresponding to the method arguments).
     */
    private void pop(@NonNull String desc) {
        char c = desc.charAt(0);

        if (c == '(') {
            int elements = (JavaType.getArgumentsAndReturnSizes(desc) >> 2) - 1;
            pop(elements);
        } else if (c == 'J' || c == 'D') {
            pop(2);
        } else {
            pop(1);
        }
    }

    /**
     * Adds a new type to the list of types on which a constructor is invoked in the basic block.
     *
     * @param var
     *            a type on a which a constructor is invoked
     */
    private void init(int var) {
        // Creates and/or resizes the initializations array if necessary.
        if (initializations == null) {
            initializations = new int[2];
        }

        int n = initializations.length;

        if (initializationCount >= n) {
            int[] t = new int[Math.max(initializationCount + 1, 2 * n)];
            System.arraycopy(initializations, 0, t, 0, n);
            initializations = t;
        }

        // Stores the type to be initialized.
        initializations[initializationCount++] = var;
    }

    /**
     * Replaces the given type with the appropriate type if it is one of the types on which a constructor is invoked in
     * the basic block.
     *
     * @return the given type or, if <code>type</code> is one of the types on which a constructor is invoked in the
     *         basic block, the type corresponding to this constructor
     */
    @NonNegative
    private int init(@NonNull String classDesc, @NonNegative int type) {
        int s;

        if (type == UNINITIALIZED_THIS) {
            s = OBJECT | cp.addNormalType(classDesc);
        } else if ((type & (DIM | BASE_KIND)) == UNINITIALIZED) {
            String typeDesc = cp.getInternalName(type & BASE_VALUE);
            s = OBJECT | cp.addNormalType(typeDesc);
        } else {
            return type;
        }

        for (int j = 0; j < initializationCount; j++) {
            int u = initializations[j];
            int dim = u & DIM;
            int kind = u & KIND;

            if (kind == LOCAL) {
                u = dim + inputLocals[u & VALUE];
            } else if (kind == STACK) {
                u = dim + inputStack[inputStack.length - (u & VALUE)];
            }

            if (type == u) {
                return s;
            }
        }

        return type;
    }

    /**
     * Simulates the action of an xLOAD or xSTORE instruction on the output stack frame.
     *
     * @param opcode
     *            the opcode of the instruction
     * @param varIndex
     *            the local variable index
     */
    void executeVAR(int opcode, @NonNegative int varIndex) {
        // noinspection SwitchStatementWithoutDefaultBranch
        switch (opcode) {
            case ILOAD:
                push(INTEGER);
                break;
            case LLOAD:
                push(LONG);
                push(TOP);
                break;
            case FLOAD:
                push(FLOAT);
                break;
            case DLOAD:
                push(DOUBLE);
                push(TOP);
                break;
            case ALOAD:
                push(get(varIndex));
                break;
            case ISTORE:
            case FSTORE:
            case ASTORE:
                executeSingleWordStore(varIndex);
                break;
            case LSTORE:
            case DSTORE:
                executeDoubleWordStore(varIndex);
        }
    }

    /**
     * Returns the output frame local variable type at the given index.
     */
    @NonNegative
    private int get(@NonNegative int localIndex) {
        if (outputLocals == null || localIndex >= outputLocals.length) {
            // This local has never been assigned in this basic block, so it's still equal to its value in the input
            // frame.
            return LOCAL | localIndex;
        }

        int type = outputLocals[localIndex];

        if (type == 0) {
            // This local has never been assigned in this basic block, so it's still equal to its value in the input
            // frame.
            type = outputLocals[localIndex] = LOCAL | localIndex;
        }

        return type;
    }

    private void executeSingleWordStore(@NonNegative int arg) {
        int type1 = pop();
        set(arg, type1);
        executeStore(arg);
    }

    private void executeDoubleWordStore(@NonNegative int arg) {
        pop(1);

        int type1 = pop();
        set(arg, type1);
        set(arg + 1, TOP);

        executeStore(arg);
    }

    private void executeStore(@NonNegative int arg) {
        if (arg > 0) {
            int type2 = get(arg - 1);

            // If type2 is of kind STACK or LOCAL we cannot know its size!
            if (type2 == LONG || type2 == DOUBLE) {
                set(arg - 1, TOP);
            } else if ((type2 & KIND) != BASE) {
                set(arg - 1, type2 | TOP_IF_LONG_OR_DOUBLE);
            }
        }
    }

    /**
     * Simulates the action of a conditional/unconditional jump instruction on the output stack frame.
     */
    void executeJUMP(@NonNegative int opcode) {
        // noinspection SwitchStatementWithoutDefaultBranch
        switch (opcode) {
            case IFEQ:
            case IFNE:
            case IFLT:
            case IFGE:
            case IFGT:
            case IFLE:
            case IFNULL:
            case IFNONNULL:
                pop(1);
                break;
            case IF_ICMPEQ:
            case IF_ICMPNE:
            case IF_ICMPLT:
            case IF_ICMPGE:
            case IF_ICMPGT:
            case IF_ICMPLE:
            case IF_ACMPEQ:
            case IF_ACMPNE:
                pop(2);
        }
    }

    /**
     * Simulates the action of the given zero-operand instruction on the output stack frame.
     */
    @SuppressWarnings({ "OverlyComplexMethod", "OverlyLongMethod" })
    public void execute(@NonNegative int opcode) {
        // noinspection SwitchStatementWithoutDefaultBranch
        switch (opcode) {
            case NOP:
            case INEG:
            case LNEG:
            case FNEG:
            case DNEG:
            case I2B:
            case I2C:
            case I2S:
            case GOTO:
            case RETURN:
                break;
            case ACONST_NULL:
                push(NULL);
                break;
            case ICONST_M1:
            case ICONST_0:
            case ICONST_1:
            case ICONST_2:
            case ICONST_3:
            case ICONST_4:
            case ICONST_5:
                push(INTEGER);
                break;
            case LCONST_0:
            case LCONST_1:
                push(LONG);
                push(TOP);
                break;
            case FCONST_0:
            case FCONST_1:
            case FCONST_2:
                push(FLOAT);
                break;
            case DCONST_0:
            case DCONST_1:
                push(DOUBLE);
                push(TOP);
                break;
            case IALOAD:
            case BALOAD:
            case CALOAD:
            case SALOAD:
                pop(2);
                push(INTEGER);
                break;
            case LALOAD:
            case D2L:
                pop(2);
                push(LONG);
                push(TOP);
                break;
            case FALOAD:
                pop(2);
                push(FLOAT);
                break;
            case DALOAD:
            case L2D:
                pop(2);
                push(DOUBLE);
                push(TOP);
                break;
            case AALOAD:
                executeAALOAD();
                break;
            case IASTORE:
            case BASTORE:
            case CASTORE:
            case SASTORE:
            case FASTORE:
            case AASTORE:
                pop(3);
                break;
            case LASTORE:
            case DASTORE:
                pop(4);
                break;
            case POP:
            case IRETURN:
            case FRETURN:
            case ARETURN:
            case ATHROW:
            case MONITORENTER:
            case MONITOREXIT:
                pop(1);
                break;
            case POP2:
            case LRETURN:
            case DRETURN:
                pop(2);
                break;
            case DUP:
                executeDUP();
                break;
            case DUP_X1:
                executeDUP_X1();
                break;
            case DUP_X2:
                executeDUP_X2();
                break;
            case DUP2:
                executeDUP2();
                break;
            case DUP2_X1:
                executeDUP2_X1();
                break;
            case DUP2_X2:
                executeDUP2_X2();
                break;
            case SWAP:
                executeSWAP();
                break;
            case IADD:
            case ISUB:
            case IMUL:
            case IDIV:
            case IREM:
            case IAND:
            case IOR:
            case IXOR:
            case ISHL:
            case ISHR:
            case IUSHR:
            case L2I:
            case D2I:
            case FCMPL:
            case FCMPG:
                pop(2);
                push(INTEGER);
                break;
            case LADD:
            case LSUB:
            case LMUL:
            case LDIV:
            case LREM:
            case LAND:
            case LOR:
            case LXOR:
                pop(4);
                push(LONG);
                push(TOP);
                break;
            case FADD:
            case FSUB:
            case FMUL:
            case FDIV:
            case FREM:
            case L2F:
            case D2F:
                pop(2);
                push(FLOAT);
                break;
            case DADD:
            case DSUB:
            case DMUL:
            case DDIV:
            case DREM:
                pop(4);
                push(DOUBLE);
                push(TOP);
                break;
            case LSHL:
            case LSHR:
            case LUSHR:
                pop(3);
                push(LONG);
                push(TOP);
                break;
            case I2L:
            case F2L:
                pop(1);
                push(LONG);
                push(TOP);
                break;
            case I2F:
                pop(1);
                push(FLOAT);
                break;
            case I2D:
            case F2D:
                pop(1);
                push(DOUBLE);
                push(TOP);
                break;
            case F2I:
            case ARRAYLENGTH:
                pop(1);
                push(INTEGER);
                break;
            case LCMP:
            case DCMPL:
            case DCMPG:
                pop(4);
                push(INTEGER);
        }
    }

    private void executeAALOAD() {
        pop(1);
        int type = pop();
        push(ELEMENT_OF + type);
    }

    private void executeDUP() {
        int type = pop();
        push(type);
        push(type);
    }

    private void executeDUP_X1() {
        int type1 = pop();
        int type2 = pop();
        push(type1);
        push(type2);
        push(type1);
    }

    private void executeDUP_X2() {
        int t1 = pop();
        int t2 = pop();
        int t3 = pop();
        push(t1);
        push(t3);
        push(t2);
        push(t1);
    }

    private void executeDUP2() {
        int t1 = pop();
        int t2 = pop();
        push(t2);
        push(t1);
        push(t2);
        push(t1);
    }

    private void executeDUP2_X1() {
        int t1 = pop();
        int t2 = pop();
        int t3 = pop();
        push(t2);
        push(t1);
        push(t3);
        push(t2);
        push(t1);
    }

    private void executeDUP2_X2() {
        int t1 = pop();
        int t2 = pop();
        int t3 = pop();
        int t4 = pop();
        push(t2);
        push(t1);
        push(t4);
        push(t3);
        push(t2);
        push(t1);
    }

    private void executeSWAP() {
        int t1 = pop();
        int t2 = pop();
        push(t1);
        push(t2);
    }

    /**
     * Simulates the action of an LCD instruction on the output stack frame.
     *
     * @param item
     *            the operand of the instructions
     */
    void executeLDC(@NonNull Item item) {
        switch (item.getType()) {
            case ConstantPoolTypes.INTEGER:
                push(INTEGER);
                break;
            case ConstantPoolTypes.LONG:
                push(LONG);
                push(TOP);
                break;
            case ConstantPoolTypes.FLOAT:
                push(FLOAT);
                break;
            case ConstantPoolTypes.DOUBLE:
                push(DOUBLE);
                push(TOP);
                break;
            case ConstantPoolTypes.CLASS:
                push(OBJECT | cp.addNormalType("java/lang/Class"));
                break;
            case ConstantPoolTypes.STRING:
                push(OBJECT | cp.addNormalType("java/lang/String"));
                break;
            case ConstantPoolTypes.METHOD_TYPE:
                push(OBJECT | cp.addNormalType("java/lang/invoke/MethodType"));
                break;
            case ConstantPoolTypes.METHOD_HANDLE:
                push(OBJECT | cp.addNormalType("java/lang/invoke/MethodHandle"));
                break;
            case ConstantPoolTypes.DYNAMIC:
                DynamicItem dynamicItem = (DynamicItem) item;
                String desc = dynamicItem.getDesc();
                if (desc.length() == 1) {
                    // primitive
                    char descChar = desc.charAt(0);
                    switch (descChar) {
                        case 'Z':
                        case 'B':
                        case 'S':
                        case 'I':
                            push(INTEGER);
                            break;
                        case 'F':
                            push(FLOAT);
                            break;
                        case 'D':
                            push(DOUBLE);
                            break;
                        case 'J':
                            push(LONG);
                            break;
                        default:
                            throw new IllegalArgumentException("Unsupported dynamic local 'primitive' type: " + desc);
                    }
                } else if (desc.charAt(0) == '[') {
                    // array
                    ArrayType arrayType = ArrayType.create(desc);
                    JavaType elementType = arrayType.getElementType();
                    int mask;
                    if (elementType instanceof PrimitiveType) {
                        PrimitiveType primitiveElementType = (PrimitiveType) elementType;
                        char descChar = primitiveElementType.getTypeCode();
                        switch (descChar) {
                            case 'Z':
                            case 'B':
                            case 'C':
                            case 'S':
                            case 'I':
                                mask = INTEGER;
                                break;
                            case 'F':
                                mask = FLOAT;
                                break;
                            case 'D':
                                mask = DOUBLE;
                                break;
                            case 'J':
                                mask = LONG;
                                break;
                            default:
                                throw new IllegalArgumentException(
                                        "Unsupported array element 'primitive' type: " + desc);
                        }
                    } else {
                        mask = OBJECT;
                    }
                    push(ARRAY_OF | mask);
                } else {
                    // object, substring 'L' and ';'
                    push(OBJECT | cp.addNormalType(desc.substring(1, desc.length() - 1)));
                }
                break;
             default:
                 throw new IllegalArgumentException("Unknown item type, cannot execute frame: " + item.getType());
         }
     }

     /**
      * Simulates the action of a NEW, ANEWARRAY, CHECKCAST or INSTANCEOF instruction on the output stack frame.
      *
      * @param opcode
      *            the opcode of the instruction
      * @param codeLength
      *            the operand of the instruction, if any
      * @param item
      *            the operand of the instruction
      */
     void executeTYPE(@NonNegative int opcode, @NonNegative int codeLength, @NonNull StringItem item) {
         // noinspection SwitchStatementWithoutDefaultBranch
         switch (opcode) {
             case NEW:
                 push(UNINITIALIZED | cp.addUninitializedType(item.getValue(), codeLength));
                 break;
             case ANEWARRAY:
                 executeANewArray(item);
                 break;
             case CHECKCAST:
                 executeCheckCast(item);
                 break;
             case INSTANCEOF:
                 pop(1);
                 push(INTEGER);
         }
     }

     private void executeANewArray(@NonNull StringItem item) {
         String s = item.getValue();
         pop();

         if (s.charAt(0) == '[') {
             push('[' + s);
         } else {
             push(ARRAY_OF | OBJECT | cp.addNormalType(s));
         }
     }

     /**
      * Pushes a new type onto the output frame stack.
      *
      * @param desc
      *            the descriptor of the type to be pushed; can also be a method descriptor (in this case this method
      *            pushes its return type onto the output frame stack)
      */
     private void push(@NonNull String desc) {
         int type = getTypeEncoding(desc);

         if (type != 0) {
             push(type);

             if (type == LONG || type == DOUBLE) {
                 push(TOP);
             }
         }
     }

     private void executeCheckCast(@NonNull StringItem item) {
         String s = item.getValue();
         pop();

         if (s.charAt(0) == '[') {
             push(s);
         } else {
             push(OBJECT | cp.addNormalType(s));
         }
     }

     /**
      * Simulates the action of a MULTIANEWARRAY instruction on the output stack frame.
      *
      * @param dims
      *            the number of dimensions of the array
      * @param arrayType
      *            the type of the array elements
      */
     void executeMULTIANEWARRAY(@NonNegative int dims, @NonNull StringItem arrayType) {
         pop(dims);
         push(arrayType.getValue());
     }

     /**
      * Simulates the action of the given instruction on the output stack frame.
      *
      * @param opcode
      *            the opcode of the instruction
      * @param item
      *            the operand of the instruction
      */
     public void execute(@NonNegative int opcode, @NonNull TypeOrMemberItem item) {
         if (opcode == INVOKEDYNAMIC) {
             executeInvokeDynamic(item);
         } else {
             // noinspection SwitchStatementWithoutDefaultBranch
             switch (opcode) {
                 case GETSTATIC:
                     push(item.getDesc());
                     break;
                 case PUTSTATIC:
                     pop(item.getDesc());
                     break;
                 case GETFIELD:
                     pop(1);
                     push(item.getDesc());
                     break;
                 case PUTFIELD:
                     pop(item.getDesc());
                     pop();
                     break;
                 case INVOKEVIRTUAL:
                 case INVOKESPECIAL:
                 case INVOKESTATIC:
                 case INVOKEINTERFACE:
                     executeInvoke(opcode, item);
             }
         }
     }

     private void executeInvoke(@NonNegative int opcode, @NonNull TypeOrMemberItem item) {
         String methodDesc = item.getDesc();
         pop(methodDesc);

         if (opcode != INVOKESTATIC) {
             int var = pop();

             if (opcode == INVOKESPECIAL && item.getName().charAt(0) == '<') {
                 init(var);
             }
         }

         push(methodDesc);
     }

     private void executeInvokeDynamic(@NonNull TypeOrMemberItem item) {
         String desc = item.getDesc();
         pop(desc);
         push(desc);
     }

     /**
      * Merges the input frame of the given basic block with the input and output frames of this basic block.
      *
      * @param frame
      *            the basic block whose input frame must be updated
      * @param edge
      *            the kind of the {@link Edge} between this label and 'label'; see {@link Edge#info}
      *
      * @return <code>true</code> if the input frame of the given label has been changed by this operation
      */
     boolean merge(@NonNull String classDesc, @NonNull Frame frame, @NonNegative int edge) {
         int nLocal = inputLocals.length;
         int nStack = inputStack.length;
         boolean changed = false;

         if (frame.inputLocals == null) {
             frame.inputLocals = new int[nLocal];
             changed = true;
         }

         int i;
         int s;
         int dim;
         int type;

         for (i = 0; i < nLocal; i++) {
             if (outputLocals != null && i < outputLocals.length) {
                 s = outputLocals[i];

                 if (s == 0) {
                     type = inputLocals[i];
                 } else {
                     dim = s & DIM;
                     int kind = s & KIND;

                     if (kind == BASE) {
                         type = s;
                     } else {
                         if (kind == LOCAL) {
                             type = dim + inputLocals[s & VALUE];
                         } else {
                             type = dim + inputStack[nStack - (s & VALUE)];
                         }

                         if ((s & TOP_IF_LONG_OR_DOUBLE) != 0 && (type == LONG || type == DOUBLE)) {
                             type = TOP;
                         }
                     }
                 }
             } else {
                 type = inputLocals[i];
             }

             if (initializations != null) {
                 type = init(classDesc, type);
             }

             changed |= merge(type, frame.inputLocals, i);
         }

         if (edge > 0) {
             for (i = 0; i < nLocal; ++i) {
                 type = inputLocals[i];
                 changed |= merge(type, frame.inputLocals, i);
             }

             if (frame.inputStack == null) {
                 frame.inputStack = new int[1];
                 changed = true;
             }

             changed |= merge(edge, frame.inputStack, 0);
             return changed;
         }

         int nInputStack = inputStack.length + owner.inputStackTop;

         if (frame.inputStack == null) {
             frame.inputStack = new int[nInputStack + outputStackTop];
             changed = true;
         }

         for (i = 0; i < nInputStack; i++) {
             type = inputStack[i];

             if (initializations != null) {
                 type = init(classDesc, type);
             }

             changed |= merge(type, frame.inputStack, i);
         }

         for (i = 0; i < outputStackTop; i++) {
             s = outputStack[i];
             dim = s & DIM;
             int kind = s & KIND;

             if (kind == BASE) {
                 type = s;
             } else {
                 if (kind == LOCAL) {
                     type = dim + inputLocals[s & VALUE];
                 } else {
                     type = dim + inputStack[nStack - (s & VALUE)];
                 }

                 if ((s & TOP_IF_LONG_OR_DOUBLE) != 0 && (type == LONG || type == DOUBLE)) {
                     type = TOP;
                 }
             }

             if (initializations != null) {
                 type = init(classDesc, type);
             }

             changed |= merge(type, frame.inputStack, nInputStack + i);
         }

         return changed;
     }

     /**
      * Merges the type at the given index in the given type array with the given type.
      *
      * @param type1
      *            the type with which the type array element must be merged
      * @param types
      *            an array of types
      * @param index
      *            the index of the type that must be merged in 'types'
      *
      * @return <code>true</code> if the type array has been modified by this operation
      */
     private boolean merge(@NonNegative int type1, @NonNull int[] types, @NonNegative int index) {
         int type2 = types[index];

         if (type2 == type1) {
             // If the types are equal, there is no change.
             return false;
         }

         if ((type1 & ~DIM) == NULL) {
             if (type2 == NULL) {
                 return false;
             }

             // noinspection AssignmentToMethodParameter
             type1 = NULL;
         }

         if (type2 == 0) {
             // If types[index] has never been assigned, merge(type2, type1) = type1.
             types[index] = type1;
             return true;
         }

         int v;

         if ((type2 & BASE_KIND) == OBJECT || (type2 & DIM) != 0) {
             // If type2 is a reference type of any dimension.
             if (type1 == NULL) {
                 // If type1 is the NULL type, merge(type2, type1) = type2, so there is no change.
                 return false;
             }
             if ((type1 & (DIM | BASE_KIND)) == (type2 & (DIM | BASE_KIND))) {
                 // If type1 and type2 have the same dimension and same base kind.
                 if ((type2 & BASE_KIND) == OBJECT) {
                     // If type1 is also a reference type, and if type2 and type1 have the same dimension
                     // merge(type2, type1) = dim(type1) | common parent of the element types of type2 and type1.
                     v = type1 & DIM | OBJECT | cp.getMergedType(type1 & BASE_VALUE, type2 & BASE_VALUE);
                 } else {
                     // If type2 and type1 are array types, but not with the same element type,
                     // merge(type2, type1) = dim(type2) - 1 | java/lang/Object.
                     int dim = ELEMENT_OF + (type2 & DIM);
                     v = dim | OBJECT | cp.addNormalType("java/lang/Object");
                 }
             } else if ((type1 & BASE_KIND) == OBJECT || (type1 & DIM) != 0) {
                 // If type1 is any other reference or array type, the merged type is min(uDim, tDim) | java/lang/Object,
                 // where uDim is the array dimension of type2, minus 1 if type2 is an array type with a primitive
                 // element
                 // type (and similarly for tDim).
                 int tDim = ((type1 & DIM) == 0 || (type1 & BASE_KIND) == OBJECT ? 0 : ELEMENT_OF) + (type1 & DIM);
                 int uDim = ((type2 & DIM) == 0 || (type2 & BASE_KIND) == OBJECT ? 0 : ELEMENT_OF) + (type2 & DIM);
                 v = Math.min(tDim, uDim) | OBJECT | cp.addNormalType("java/lang/Object");
             } else {
                 // If type1 is any other type, merge(type2, type1) = TOP.
                 v = TOP;
             }
         } else if (type2 == NULL) {
             // If type2 is the NULL type, merge(type2, type1) = type1, or TOP if type1 is not a reference type.
             v = (type1 & BASE_KIND) == OBJECT || (type1 & DIM) != 0 ? type1 : TOP;
         } else {
             // If type2 is any other type, merge(type2, type1) = TOP whatever type1.
             v = TOP;
         }

         if (type2 != v) {
             types[index] = v;
             return true;
         }

         return false;
     }
 }