plugins/org.eclipse.persistence.asm/src/org/eclipse/persistence/internal/libraries/asm/tree/analysis/Analyzer.java - eclipselink/eclipselink.runtime - Git at Google

 /***
  * ASM: a very small and fast Java bytecode manipulation framework
  * Copyright (c) 2000-2011 INRIA, France Telecom
  * All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
  * are met:
  * 1. Redistributions of source code must retain the above copyright
  *    notice, this list of conditions and the following disclaimer.
  * 2. Redistributions in binary form must reproduce the above copyright
  *    notice, this list of conditions and the following disclaimer in the
  *    documentation and/or other materials provided with the distribution.
  * 3. Neither the name of the copyright holders nor the names of its
  *    contributors may be used to endorse or promote products derived from
  *    this software without specific prior written permission.
  *
  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
  * THE POSSIBILITY OF SUCH DAMAGE.
  */
 package org.eclipse.persistence.internal.libraries.asm.tree.analysis;

 import java.util.ArrayList;
 import java.util.HashMap;
 import java.util.List;
 import java.util.Map;

 import org.eclipse.persistence.internal.libraries.asm.Opcodes;
 import org.eclipse.persistence.internal.libraries.asm.Type;
 import org.eclipse.persistence.internal.libraries.asm.tree.AbstractInsnNode;
 import org.eclipse.persistence.internal.libraries.asm.tree.IincInsnNode;
 import org.eclipse.persistence.internal.libraries.asm.tree.InsnList;
 import org.eclipse.persistence.internal.libraries.asm.tree.JumpInsnNode;
 import org.eclipse.persistence.internal.libraries.asm.tree.LabelNode;
 import org.eclipse.persistence.internal.libraries.asm.tree.LookupSwitchInsnNode;
 import org.eclipse.persistence.internal.libraries.asm.tree.MethodNode;
 import org.eclipse.persistence.internal.libraries.asm.tree.TableSwitchInsnNode;
 import org.eclipse.persistence.internal.libraries.asm.tree.TryCatchBlockNode;
 import org.eclipse.persistence.internal.libraries.asm.tree.VarInsnNode;

 /**
  * A semantic bytecode analyzer. <i>This class does not fully check that JSR and
  * RET instructions are valid.</i>
  *
  * @param <V>
  *            type of the Value used for the analysis.
  *
  * @author Eric Bruneton
  */
 public class Analyzer<V extends Value> implements Opcodes {

     private final Interpreter<V> interpreter;

     private int n;

     private InsnList insns;

     private List<TryCatchBlockNode>[] handlers;

     private Frame<V>[] frames;

     private Subroutine[] subroutines;

     private boolean[] queued;

     private int[] queue;

     private int top;

     /**
      * Constructs a new {@link Analyzer}.
      *
      * @param interpreter
      *            the interpreter to be used to symbolically interpret the
      *            bytecode instructions.
      */
     public Analyzer(final Interpreter<V> interpreter) {
         this.interpreter = interpreter;
     }

     /**
      * Analyzes the given method.
      *
      * @param owner
      *            the internal name of the class to which the method belongs.
      * @param m
      *            the method to be analyzed.
      * @return the symbolic state of the execution stack frame at each bytecode
      *         instruction of the method. The size of the returned array is
      *         equal to the number of instructions (and labels) of the method. A
      *         given frame is <tt>null</tt> if and only if the corresponding
      *         instruction cannot be reached (dead code).
      * @throws AnalyzerException
      *             if a problem occurs during the analysis.
      */
     @SuppressWarnings("unchecked")
     public Frame<V>[] analyze(final String owner, final MethodNode m)
             throws AnalyzerException {
         if ((m.access & (ACC_ABSTRACT | ACC_NATIVE)) != 0) {
             frames = (Frame<V>[]) new Frame<?>[0];
             return frames;
         }
         n = m.instructions.size();
         insns = m.instructions;
         handlers = (List<TryCatchBlockNode>[]) new List<?>[n];
         frames = (Frame<V>[]) new Frame<?>[n];
         subroutines = new Subroutine[n];
         queued = new boolean[n];
         queue = new int[n];
         top = 0;

         // computes exception handlers for each instruction
         for (int i = 0; i < m.tryCatchBlocks.size(); ++i) {
             TryCatchBlockNode tcb = m.tryCatchBlocks.get(i);
             int begin = insns.indexOf(tcb.start);
             int end = insns.indexOf(tcb.end);
             for (int j = begin; j < end; ++j) {
                 List<TryCatchBlockNode> insnHandlers = handlers[j];
                 if (insnHandlers == null) {
                     insnHandlers = new ArrayList<TryCatchBlockNode>();
                     handlers[j] = insnHandlers;
                 }
                 insnHandlers.add(tcb);
             }
         }

         // computes the subroutine for each instruction:
         Subroutine main = new Subroutine(null, m.maxLocals, null);
         List<AbstractInsnNode> subroutineCalls = new ArrayList<AbstractInsnNode>();
         Map<LabelNode, Subroutine> subroutineHeads = new HashMap<LabelNode, Subroutine>();
         findSubroutine(0, main, subroutineCalls);
         while (!subroutineCalls.isEmpty()) {
             JumpInsnNode jsr = (JumpInsnNode) subroutineCalls.remove(0);
             Subroutine sub = subroutineHeads.get(jsr.label);
             if (sub == null) {
                 sub = new Subroutine(jsr.label, m.maxLocals, jsr);
                 subroutineHeads.put(jsr.label, sub);
                 findSubroutine(insns.indexOf(jsr.label), sub, subroutineCalls);
             } else {
                 sub.callers.add(jsr);
             }
         }
         for (int i = 0; i < n; ++i) {
             if (subroutines[i] != null && subroutines[i].start == null) {
                 subroutines[i] = null;
             }
         }

         // initializes the data structures for the control flow analysis
         Frame<V> current = newFrame(m.maxLocals, m.maxStack);
         Frame<V> handler = newFrame(m.maxLocals, m.maxStack);
         current.setReturn(interpreter.newValue(Type.getReturnType(m.desc)));
         Type[] args = Type.getArgumentTypes(m.desc);
         int local = 0;
         if ((m.access & ACC_STATIC) == 0) {
             Type ctype = Type.getObjectType(owner);
             current.setLocal(local++, interpreter.newValue(ctype));
         }
         for (int i = 0; i < args.length; ++i) {
             current.setLocal(local++, interpreter.newValue(args[i]));
             if (args[i].getSize() == 2) {
                 current.setLocal(local++, interpreter.newValue(null));
             }
         }
         while (local < m.maxLocals) {
             current.setLocal(local++, interpreter.newValue(null));
         }
         merge(0, current, null);

         init(owner, m);

         // control flow analysis
         while (top > 0) {
             int insn = queue[--top];
             Frame<V> f = frames[insn];
             Subroutine subroutine = subroutines[insn];
             queued[insn] = false;

             AbstractInsnNode insnNode = null;
             try {
                 insnNode = m.instructions.get(insn);
                 int insnOpcode = insnNode.getOpcode();
                 int insnType = insnNode.getType();

                 if (insnType == AbstractInsnNode.LABEL
                         || insnType == AbstractInsnNode.LINE
                         || insnType == AbstractInsnNode.FRAME) {
                     merge(insn + 1, f, subroutine);
                     newControlFlowEdge(insn, insn + 1);
                 } else {
                     current.init(f).execute(insnNode, interpreter);
                     subroutine = subroutine == null ? null : subroutine.copy();

                     if (insnNode instanceof JumpInsnNode) {
                         JumpInsnNode j = (JumpInsnNode) insnNode;
                         if (insnOpcode != GOTO && insnOpcode != JSR) {
                             merge(insn + 1, current, subroutine);
                             newControlFlowEdge(insn, insn + 1);
                         }
                         int jump = insns.indexOf(j.label);
                         if (insnOpcode == JSR) {
                             merge(jump, current, new Subroutine(j.label,
                                     m.maxLocals, j));
                         } else {
                             merge(jump, current, subroutine);
                         }
                         newControlFlowEdge(insn, jump);
                     } else if (insnNode instanceof LookupSwitchInsnNode) {
                         LookupSwitchInsnNode lsi = (LookupSwitchInsnNode) insnNode;
                         int jump = insns.indexOf(lsi.dflt);
                         merge(jump, current, subroutine);
                         newControlFlowEdge(insn, jump);
                         for (int j = 0; j < lsi.labels.size(); ++j) {
                             LabelNode label = lsi.labels.get(j);
                             jump = insns.indexOf(label);
                             merge(jump, current, subroutine);
                             newControlFlowEdge(insn, jump);
                         }
                     } else if (insnNode instanceof TableSwitchInsnNode) {
                         TableSwitchInsnNode tsi = (TableSwitchInsnNode) insnNode;
                         int jump = insns.indexOf(tsi.dflt);
                         merge(jump, current, subroutine);
                         newControlFlowEdge(insn, jump);
                         for (int j = 0; j < tsi.labels.size(); ++j) {
                             LabelNode label = tsi.labels.get(j);
                             jump = insns.indexOf(label);
                             merge(jump, current, subroutine);
                             newControlFlowEdge(insn, jump);
                         }
                     } else if (insnOpcode == RET) {
                         if (subroutine == null) {
                             throw new AnalyzerException(insnNode,
                                     "RET instruction outside of a sub routine");
                         }
                         for (int i = 0; i < subroutine.callers.size(); ++i) {
                             JumpInsnNode caller = subroutine.callers.get(i);
                             int call = insns.indexOf(caller);
                             if (frames[call] != null) {
                                 merge(call + 1, frames[call], current,
                                         subroutines[call], subroutine.access);
                                 newControlFlowEdge(insn, call + 1);
                             }
                         }
                     } else if (insnOpcode != ATHROW
                             && (insnOpcode < IRETURN || insnOpcode > RETURN)) {
                         if (subroutine != null) {
                             if (insnNode instanceof VarInsnNode) {
                                 int var = ((VarInsnNode) insnNode).var;
                                 subroutine.access[var] = true;
                                 if (insnOpcode == LLOAD || insnOpcode == DLOAD
                                         || insnOpcode == LSTORE
                                         || insnOpcode == DSTORE) {
                                     subroutine.access[var + 1] = true;
                                 }
                             } else if (insnNode instanceof IincInsnNode) {
                                 int var = ((IincInsnNode) insnNode).var;
                                 subroutine.access[var] = true;
                             }
                         }
                         merge(insn + 1, current, subroutine);
                         newControlFlowEdge(insn, insn + 1);
                     }
                 }

                 List<TryCatchBlockNode> insnHandlers = handlers[insn];
                 if (insnHandlers != null) {
                     for (int i = 0; i < insnHandlers.size(); ++i) {
                         TryCatchBlockNode tcb = insnHandlers.get(i);
                         Type type;
                         if (tcb.type == null) {
                             type = Type.getObjectType("java/lang/Throwable");
                         } else {
                             type = Type.getObjectType(tcb.type);
                         }
                         int jump = insns.indexOf(tcb.handler);
                         if (newControlFlowExceptionEdge(insn, tcb)) {
                             handler.init(f);
                             handler.clearStack();
                             handler.push(interpreter.newValue(type));
                             merge(jump, handler, subroutine);
                         }
                     }
                 }
             } catch (AnalyzerException e) {
                 throw new AnalyzerException(e.node, "Error at instruction "
                         + insn + ": " + e.getMessage(), e);
             } catch (Exception e) {
                 throw new AnalyzerException(insnNode, "Error at instruction "
                         + insn + ": " + e.getMessage(), e);
             }
         }

         return frames;
     }

     private void findSubroutine(int insn, final Subroutine sub,
             final List<AbstractInsnNode> calls) throws AnalyzerException {
         while (true) {
             if (insn < 0 || insn >= n) {
                 throw new AnalyzerException(null,
                         "Execution can fall off end of the code");
             }
             if (subroutines[insn] != null) {
                 return;
             }
             subroutines[insn] = sub.copy();
             AbstractInsnNode node = insns.get(insn);

             // calls findSubroutine recursively on normal successors
             if (node instanceof JumpInsnNode) {
                 if (node.getOpcode() == JSR) {
                     // do not follow a JSR, it leads to another subroutine!
                     calls.add(node);
                 } else {
                     JumpInsnNode jnode = (JumpInsnNode) node;
                     findSubroutine(insns.indexOf(jnode.label), sub, calls);
                 }
             } else if (node instanceof TableSwitchInsnNode) {
                 TableSwitchInsnNode tsnode = (TableSwitchInsnNode) node;
                 findSubroutine(insns.indexOf(tsnode.dflt), sub, calls);
                 for (int i = tsnode.labels.size() - 1; i >= 0; --i) {
                     LabelNode l = tsnode.labels.get(i);
                     findSubroutine(insns.indexOf(l), sub, calls);
                 }
             } else if (node instanceof LookupSwitchInsnNode) {
                 LookupSwitchInsnNode lsnode = (LookupSwitchInsnNode) node;
                 findSubroutine(insns.indexOf(lsnode.dflt), sub, calls);
                 for (int i = lsnode.labels.size() - 1; i >= 0; --i) {
                     LabelNode l = lsnode.labels.get(i);
                     findSubroutine(insns.indexOf(l), sub, calls);
                 }
             }

             // calls findSubroutine recursively on exception handler successors
             List<TryCatchBlockNode> insnHandlers = handlers[insn];
             if (insnHandlers != null) {
                 for (int i = 0; i < insnHandlers.size(); ++i) {
                     TryCatchBlockNode tcb = insnHandlers.get(i);
                     findSubroutine(insns.indexOf(tcb.handler), sub, calls);
                 }
             }

             // if insn does not falls through to the next instruction, return.
             switch (node.getOpcode()) {
             case GOTO:
             case RET:
             case TABLESWITCH:
             case LOOKUPSWITCH:
             case IRETURN:
             case LRETURN:
             case FRETURN:
             case DRETURN:
             case ARETURN:
             case RETURN:
             case ATHROW:
                 return;
             }
             insn++;
         }
     }

     /**
      * Returns the symbolic stack frame for each instruction of the last
      * recently analyzed method.
      *
      * @return the symbolic state of the execution stack frame at each bytecode
      *         instruction of the method. The size of the returned array is
      *         equal to the number of instructions (and labels) of the method. A
      *         given frame is <tt>null</tt> if the corresponding instruction
      *         cannot be reached, or if an error occured during the analysis of
      *         the method.
      */
     public Frame<V>[] getFrames() {
         return frames;
     }

     /**
      * Returns the exception handlers for the given instruction.
      *
      * @param insn
      *            the index of an instruction of the last recently analyzed
      *            method.
      * @return a list of {@link TryCatchBlockNode} objects.
      */
     public List<TryCatchBlockNode> getHandlers(final int insn) {
         return handlers[insn];
     }

     /**
      * Initializes this analyzer. This method is called just before the
      * execution of control flow analysis loop in #analyze. The default
      * implementation of this method does nothing.
      *
      * @param owner
      *            the internal name of the class to which the method belongs.
      * @param m
      *            the method to be analyzed.
      * @throws AnalyzerException
      *             if a problem occurs.
      */
     protected void init(String owner, MethodNode m) throws AnalyzerException {
     }

     /**
      * Constructs a new frame with the given size.
      *
      * @param nLocals
      *            the maximum number of local variables of the frame.
      * @param nStack
      *            the maximum stack size of the frame.
      * @return the created frame.
      */
     protected Frame<V> newFrame(final int nLocals, final int nStack) {
         return new Frame<V>(nLocals, nStack);
     }

     /**
      * Constructs a new frame that is identical to the given frame.
      *
      * @param src
      *            a frame.
      * @return the created frame.
      */
     protected Frame<V> newFrame(final Frame<? extends V> src) {
         return new Frame<V>(src);
     }

     /**
      * Creates a control flow graph edge. The default implementation of this
      * method does nothing. It can be overriden in order to construct the
      * control flow graph of a method (this method is called by the
      * {@link #analyze analyze} method during its visit of the method's code).
      *
      * @param insn
      *            an instruction index.
      * @param successor
      *            index of a successor instruction.
      */
     protected void newControlFlowEdge(final int insn, final int successor) {
     }

     /**
      * Creates a control flow graph edge corresponding to an exception handler.
      * The default implementation of this method does nothing. It can be
      * overridden in order to construct the control flow graph of a method (this
      * method is called by the {@link #analyze analyze} method during its visit
      * of the method's code).
      *
      * @param insn
      *            an instruction index.
      * @param successor
      *            index of a successor instruction.
      * @return true if this edge must be considered in the data flow analysis
      *         performed by this analyzer, or false otherwise. The default
      *         implementation of this method always returns true.
      */
     protected boolean newControlFlowExceptionEdge(final int insn,
             final int successor) {
         return true;
     }

     /**
      * Creates a control flow graph edge corresponding to an exception handler.
      * The default implementation of this method delegates to
      * {@link #newControlFlowExceptionEdge(int, int)
      * newControlFlowExceptionEdge(int, int)}. It can be overridden in order to
      * construct the control flow graph of a method (this method is called by
      * the {@link #analyze analyze} method during its visit of the method's
      * code).
      *
      * @param insn
      *            an instruction index.
      * @param tcb
      *            TryCatchBlockNode corresponding to this edge.
      * @return true if this edge must be considered in the data flow analysis
      *         performed by this analyzer, or false otherwise. The default
      *         implementation of this method delegates to
      *         {@link #newControlFlowExceptionEdge(int, int)
      *         newControlFlowExceptionEdge(int, int)}.
      */
     protected boolean newControlFlowExceptionEdge(final int insn,
             final TryCatchBlockNode tcb) {
         return newControlFlowExceptionEdge(insn, insns.indexOf(tcb.handler));
     }

     // -------------------------------------------------------------------------

     private void merge(final int insn, final Frame<V> frame,
             final Subroutine subroutine) throws AnalyzerException {
         Frame<V> oldFrame = frames[insn];
         Subroutine oldSubroutine = subroutines[insn];
         boolean changes;

         if (oldFrame == null) {
             frames[insn] = newFrame(frame);
             changes = true;
         } else {
             changes = oldFrame.merge(frame, interpreter);
         }

         if (oldSubroutine == null) {
             if (subroutine != null) {
                 subroutines[insn] = subroutine.copy();
                 changes = true;
             }
         } else {
             if (subroutine != null) {
                 changes |= oldSubroutine.merge(subroutine);
             }
         }
         if (changes && !queued[insn]) {
             queued[insn] = true;
             queue[top++] = insn;
         }
     }

     private void merge(final int insn, final Frame<V> beforeJSR,
             final Frame<V> afterRET, final Subroutine subroutineBeforeJSR,
             final boolean[] access) throws AnalyzerException {
         Frame<V> oldFrame = frames[insn];
         Subroutine oldSubroutine = subroutines[insn];
         boolean changes;

         afterRET.merge(beforeJSR, access);

         if (oldFrame == null) {
             frames[insn] = newFrame(afterRET);
             changes = true;
         } else {
             changes = oldFrame.merge(afterRET, interpreter);
         }

         if (oldSubroutine != null && subroutineBeforeJSR != null) {
             changes |= oldSubroutine.merge(subroutineBeforeJSR);
         }
         if (changes && !queued[insn]) {
             queued[insn] = true;
             queue[top++] = insn;
         }
     }
 }
	/***
	* ASM: a very small and fast Java bytecode manipulation framework
	* Copyright (c) 2000-2011 INRIA, France Telecom
	* All rights reserved.
	*
	* Redistribution and use in source and binary forms, with or without
	* modification, are permitted provided that the following conditions
	* are met:
	* 1. Redistributions of source code must retain the above copyright
	* notice, this list of conditions and the following disclaimer.
	* 2. Redistributions in binary form must reproduce the above copyright
	* notice, this list of conditions and the following disclaimer in the
	* documentation and/or other materials provided with the distribution.
	* 3. Neither the name of the copyright holders nor the names of its
	* contributors may be used to endorse or promote products derived from
	* this software without specific prior written permission.
	*
	* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
	* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
	* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
	* ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
	* LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
	* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
	* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
	* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
	* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
	* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
	* THE POSSIBILITY OF SUCH DAMAGE.
	*/
	package org.eclipse.persistence.internal.libraries.asm.tree.analysis;

	import java.util.ArrayList;
	import java.util.HashMap;
	import java.util.List;
	import java.util.Map;

	import org.eclipse.persistence.internal.libraries.asm.Opcodes;
	import org.eclipse.persistence.internal.libraries.asm.Type;
	import org.eclipse.persistence.internal.libraries.asm.tree.AbstractInsnNode;
	import org.eclipse.persistence.internal.libraries.asm.tree.IincInsnNode;
	import org.eclipse.persistence.internal.libraries.asm.tree.InsnList;
	import org.eclipse.persistence.internal.libraries.asm.tree.JumpInsnNode;
	import org.eclipse.persistence.internal.libraries.asm.tree.LabelNode;
	import org.eclipse.persistence.internal.libraries.asm.tree.LookupSwitchInsnNode;
	import org.eclipse.persistence.internal.libraries.asm.tree.MethodNode;
	import org.eclipse.persistence.internal.libraries.asm.tree.TableSwitchInsnNode;
	import org.eclipse.persistence.internal.libraries.asm.tree.TryCatchBlockNode;
	import org.eclipse.persistence.internal.libraries.asm.tree.VarInsnNode;

	/**
	* A semantic bytecode analyzer. <i>This class does not fully check that JSR and
	* RET instructions are valid.</i>
	*
	* @param <V>
	* type of the Value used for the analysis.
	*
	* @author Eric Bruneton
	*/
	public class Analyzer<V extends Value> implements Opcodes {

	private final Interpreter<V> interpreter;

	private int n;

	private InsnList insns;

	private List<TryCatchBlockNode>[] handlers;

	private Frame<V>[] frames;

	private Subroutine[] subroutines;

	private boolean[] queued;

	private int[] queue;

	private int top;

	/**
	* Constructs a new {@link Analyzer}.
	*
	* @param interpreter
	* the interpreter to be used to symbolically interpret the
	* bytecode instructions.
	*/
	public Analyzer(final Interpreter<V> interpreter) {
	this.interpreter = interpreter;
	}

	/**
	* Analyzes the given method.
	*
	* @param owner
	* the internal name of the class to which the method belongs.
	* @param m
	* the method to be analyzed.
	* @return the symbolic state of the execution stack frame at each bytecode
	* instruction of the method. The size of the returned array is
	* equal to the number of instructions (and labels) of the method. A
	* given frame is <tt>null</tt> if and only if the corresponding
	* instruction cannot be reached (dead code).
	* @throws AnalyzerException
	* if a problem occurs during the analysis.
	*/
	@SuppressWarnings("unchecked")
	public Frame<V>[] analyze(final String owner, final MethodNode m)
	throws AnalyzerException {
	if ((m.access & (ACC_ABSTRACT \| ACC_NATIVE)) != 0) {
	frames = (Frame<V>[]) new Frame<?>[0];
	return frames;
	}
	n = m.instructions.size();
	insns = m.instructions;
	handlers = (List<TryCatchBlockNode>[]) new List<?>[n];
	frames = (Frame<V>[]) new Frame<?>[n];
	subroutines = new Subroutine[n];
	queued = new boolean[n];
	queue = new int[n];
	top = 0;

	// computes exception handlers for each instruction
	for (int i = 0; i < m.tryCatchBlocks.size(); ++i) {
	TryCatchBlockNode tcb = m.tryCatchBlocks.get(i);
	int begin = insns.indexOf(tcb.start);
	int end = insns.indexOf(tcb.end);
	for (int j = begin; j < end; ++j) {
	List<TryCatchBlockNode> insnHandlers = handlers[j];
	if (insnHandlers == null) {
	insnHandlers = new ArrayList<TryCatchBlockNode>();
	handlers[j] = insnHandlers;
	}
	insnHandlers.add(tcb);
	}
	}

	// computes the subroutine for each instruction:
	Subroutine main = new Subroutine(null, m.maxLocals, null);
	List<AbstractInsnNode> subroutineCalls = new ArrayList<AbstractInsnNode>();
	Map<LabelNode, Subroutine> subroutineHeads = new HashMap<LabelNode, Subroutine>();
	findSubroutine(0, main, subroutineCalls);
	while (!subroutineCalls.isEmpty()) {
	JumpInsnNode jsr = (JumpInsnNode) subroutineCalls.remove(0);
	Subroutine sub = subroutineHeads.get(jsr.label);
	if (sub == null) {
	sub = new Subroutine(jsr.label, m.maxLocals, jsr);
	subroutineHeads.put(jsr.label, sub);
	findSubroutine(insns.indexOf(jsr.label), sub, subroutineCalls);
	} else {
	sub.callers.add(jsr);
	}
	}
	for (int i = 0; i < n; ++i) {
	if (subroutines[i] != null && subroutines[i].start == null) {
	subroutines[i] = null;
	}
	}

	// initializes the data structures for the control flow analysis
	Frame<V> current = newFrame(m.maxLocals, m.maxStack);
	Frame<V> handler = newFrame(m.maxLocals, m.maxStack);
	current.setReturn(interpreter.newValue(Type.getReturnType(m.desc)));
	Type[] args = Type.getArgumentTypes(m.desc);
	int local = 0;
	if ((m.access & ACC_STATIC) == 0) {
	Type ctype = Type.getObjectType(owner);
	current.setLocal(local++, interpreter.newValue(ctype));
	}
	for (int i = 0; i < args.length; ++i) {
	current.setLocal(local++, interpreter.newValue(args[i]));
	if (args[i].getSize() == 2) {
	current.setLocal(local++, interpreter.newValue(null));
	}
	}
	while (local < m.maxLocals) {
	current.setLocal(local++, interpreter.newValue(null));
	}
	merge(0, current, null);

	init(owner, m);

	// control flow analysis
	while (top > 0) {
	int insn = queue[--top];
	Frame<V> f = frames[insn];
	Subroutine subroutine = subroutines[insn];
	queued[insn] = false;

	AbstractInsnNode insnNode = null;
	try {
	insnNode = m.instructions.get(insn);
	int insnOpcode = insnNode.getOpcode();
	int insnType = insnNode.getType();

	if (insnType == AbstractInsnNode.LABEL
	\|\| insnType == AbstractInsnNode.LINE
	\|\| insnType == AbstractInsnNode.FRAME) {
	merge(insn + 1, f, subroutine);
	newControlFlowEdge(insn, insn + 1);
	} else {
	current.init(f).execute(insnNode, interpreter);
	subroutine = subroutine == null ? null : subroutine.copy();

	if (insnNode instanceof JumpInsnNode) {
	JumpInsnNode j = (JumpInsnNode) insnNode;
	if (insnOpcode != GOTO && insnOpcode != JSR) {
	merge(insn + 1, current, subroutine);
	newControlFlowEdge(insn, insn + 1);
	}
	int jump = insns.indexOf(j.label);
	if (insnOpcode == JSR) {
	merge(jump, current, new Subroutine(j.label,
	m.maxLocals, j));
	} else {
	merge(jump, current, subroutine);
	}
	newControlFlowEdge(insn, jump);
	} else if (insnNode instanceof LookupSwitchInsnNode) {
	LookupSwitchInsnNode lsi = (LookupSwitchInsnNode) insnNode;
	int jump = insns.indexOf(lsi.dflt);
	merge(jump, current, subroutine);
	newControlFlowEdge(insn, jump);
	for (int j = 0; j < lsi.labels.size(); ++j) {
	LabelNode label = lsi.labels.get(j);
	jump = insns.indexOf(label);
	merge(jump, current, subroutine);
	newControlFlowEdge(insn, jump);
	}
	} else if (insnNode instanceof TableSwitchInsnNode) {
	TableSwitchInsnNode tsi = (TableSwitchInsnNode) insnNode;
	int jump = insns.indexOf(tsi.dflt);
	merge(jump, current, subroutine);
	newControlFlowEdge(insn, jump);
	for (int j = 0; j < tsi.labels.size(); ++j) {
	LabelNode label = tsi.labels.get(j);
	jump = insns.indexOf(label);
	merge(jump, current, subroutine);
	newControlFlowEdge(insn, jump);
	}
	} else if (insnOpcode == RET) {
	if (subroutine == null) {
	throw new AnalyzerException(insnNode,
	"RET instruction outside of a sub routine");
	}
	for (int i = 0; i < subroutine.callers.size(); ++i) {
	JumpInsnNode caller = subroutine.callers.get(i);
	int call = insns.indexOf(caller);
	if (frames[call] != null) {
	merge(call + 1, frames[call], current,
	subroutines[call], subroutine.access);
	newControlFlowEdge(insn, call + 1);
	}
	}
	} else if (insnOpcode != ATHROW
	&& (insnOpcode < IRETURN \|\| insnOpcode > RETURN)) {
	if (subroutine != null) {
	if (insnNode instanceof VarInsnNode) {
	int var = ((VarInsnNode) insnNode).var;
	subroutine.access[var] = true;
	if (insnOpcode == LLOAD \|\| insnOpcode == DLOAD
	\|\| insnOpcode == LSTORE
	\|\| insnOpcode == DSTORE) {
	subroutine.access[var + 1] = true;
	}
	} else if (insnNode instanceof IincInsnNode) {
	int var = ((IincInsnNode) insnNode).var;
	subroutine.access[var] = true;
	}
	}
	merge(insn + 1, current, subroutine);
	newControlFlowEdge(insn, insn + 1);
	}
	}

	List<TryCatchBlockNode> insnHandlers = handlers[insn];
	if (insnHandlers != null) {
	for (int i = 0; i < insnHandlers.size(); ++i) {
	TryCatchBlockNode tcb = insnHandlers.get(i);
	Type type;
	if (tcb.type == null) {
	type = Type.getObjectType("java/lang/Throwable");
	} else {
	type = Type.getObjectType(tcb.type);
	}
	int jump = insns.indexOf(tcb.handler);
	if (newControlFlowExceptionEdge(insn, tcb)) {
	handler.init(f);
	handler.clearStack();
	handler.push(interpreter.newValue(type));
	merge(jump, handler, subroutine);
	}
	}
	}
	} catch (AnalyzerException e) {
	throw new AnalyzerException(e.node, "Error at instruction "
	+ insn + ": " + e.getMessage(), e);
	} catch (Exception e) {
	throw new AnalyzerException(insnNode, "Error at instruction "
	+ insn + ": " + e.getMessage(), e);
	}
	}

	return frames;
	}

	private void findSubroutine(int insn, final Subroutine sub,
	final List<AbstractInsnNode> calls) throws AnalyzerException {
	while (true) {
	if (insn < 0 \|\| insn >= n) {
	throw new AnalyzerException(null,
	"Execution can fall off end of the code");
	}
	if (subroutines[insn] != null) {
	return;
	}
	subroutines[insn] = sub.copy();
	AbstractInsnNode node = insns.get(insn);

	// calls findSubroutine recursively on normal successors
	if (node instanceof JumpInsnNode) {
	if (node.getOpcode() == JSR) {
	// do not follow a JSR, it leads to another subroutine!
	calls.add(node);
	} else {
	JumpInsnNode jnode = (JumpInsnNode) node;
	findSubroutine(insns.indexOf(jnode.label), sub, calls);
	}
	} else if (node instanceof TableSwitchInsnNode) {
	TableSwitchInsnNode tsnode = (TableSwitchInsnNode) node;
	findSubroutine(insns.indexOf(tsnode.dflt), sub, calls);
	for (int i = tsnode.labels.size() - 1; i >= 0; --i) {
	LabelNode l = tsnode.labels.get(i);
	findSubroutine(insns.indexOf(l), sub, calls);
	}
	} else if (node instanceof LookupSwitchInsnNode) {
	LookupSwitchInsnNode lsnode = (LookupSwitchInsnNode) node;
	findSubroutine(insns.indexOf(lsnode.dflt), sub, calls);
	for (int i = lsnode.labels.size() - 1; i >= 0; --i) {
	LabelNode l = lsnode.labels.get(i);
	findSubroutine(insns.indexOf(l), sub, calls);
	}
	}

	// calls findSubroutine recursively on exception handler successors
	List<TryCatchBlockNode> insnHandlers = handlers[insn];
	if (insnHandlers != null) {
	for (int i = 0; i < insnHandlers.size(); ++i) {
	TryCatchBlockNode tcb = insnHandlers.get(i);
	findSubroutine(insns.indexOf(tcb.handler), sub, calls);
	}
	}

	// if insn does not falls through to the next instruction, return.
	switch (node.getOpcode()) {
	case GOTO:
	case RET:
	case TABLESWITCH:
	case LOOKUPSWITCH:
	case IRETURN:
	case LRETURN:
	case FRETURN:
	case DRETURN:
	case ARETURN:
	case RETURN:
	case ATHROW:
	return;
	}
	insn++;
	}
	}

	/**
	* Returns the symbolic stack frame for each instruction of the last
	* recently analyzed method.
	*
	* @return the symbolic state of the execution stack frame at each bytecode
	* instruction of the method. The size of the returned array is
	* equal to the number of instructions (and labels) of the method. A
	* given frame is <tt>null</tt> if the corresponding instruction
	* cannot be reached, or if an error occured during the analysis of
	* the method.
	*/
	public Frame<V>[] getFrames() {
	return frames;
	}

	/**
	* Returns the exception handlers for the given instruction.
	*
	* @param insn
	* the index of an instruction of the last recently analyzed
	* method.
	* @return a list of {@link TryCatchBlockNode} objects.
	*/
	public List<TryCatchBlockNode> getHandlers(final int insn) {
	return handlers[insn];
	}

	/**
	* Initializes this analyzer. This method is called just before the
	* execution of control flow analysis loop in #analyze. The default
	* implementation of this method does nothing.
	*
	* @param owner
	* the internal name of the class to which the method belongs.
	* @param m
	* the method to be analyzed.
	* @throws AnalyzerException
	* if a problem occurs.
	*/
	protected void init(String owner, MethodNode m) throws AnalyzerException {
	}

	/**
	* Constructs a new frame with the given size.
	*
	* @param nLocals
	* the maximum number of local variables of the frame.
	* @param nStack
	* the maximum stack size of the frame.
	* @return the created frame.
	*/
	protected Frame<V> newFrame(final int nLocals, final int nStack) {
	return new Frame<V>(nLocals, nStack);
	}

	/**
	* Constructs a new frame that is identical to the given frame.
	*
	* @param src
	* a frame.
	* @return the created frame.
	*/
	protected Frame<V> newFrame(final Frame<? extends V> src) {
	return new Frame<V>(src);
	}

	/**
	* Creates a control flow graph edge. The default implementation of this
	* method does nothing. It can be overriden in order to construct the
	* control flow graph of a method (this method is called by the
	* {@link #analyze analyze} method during its visit of the method's code).
	*
	* @param insn
	* an instruction index.
	* @param successor
	* index of a successor instruction.
	*/
	protected void newControlFlowEdge(final int insn, final int successor) {
	}

	/**
	* Creates a control flow graph edge corresponding to an exception handler.
	* The default implementation of this method does nothing. It can be
	* overridden in order to construct the control flow graph of a method (this
	* method is called by the {@link #analyze analyze} method during its visit
	* of the method's code).
	*
	* @param insn
	* an instruction index.
	* @param successor
	* index of a successor instruction.
	* @return true if this edge must be considered in the data flow analysis
	* performed by this analyzer, or false otherwise. The default
	* implementation of this method always returns true.
	*/
	protected boolean newControlFlowExceptionEdge(final int insn,
	final int successor) {
	return true;
	}

	/**
	* Creates a control flow graph edge corresponding to an exception handler.
	* The default implementation of this method delegates to
	* {@link #newControlFlowExceptionEdge(int, int)
	* newControlFlowExceptionEdge(int, int)}. It can be overridden in order to
	* construct the control flow graph of a method (this method is called by
	* the {@link #analyze analyze} method during its visit of the method's
	* code).
	*
	* @param insn
	* an instruction index.
	* @param tcb
	* TryCatchBlockNode corresponding to this edge.
	* @return true if this edge must be considered in the data flow analysis
	* performed by this analyzer, or false otherwise. The default
	* implementation of this method delegates to
	* {@link #newControlFlowExceptionEdge(int, int)
	* newControlFlowExceptionEdge(int, int)}.
	*/
	protected boolean newControlFlowExceptionEdge(final int insn,
	final TryCatchBlockNode tcb) {
	return newControlFlowExceptionEdge(insn, insns.indexOf(tcb.handler));
	}

	// -------------------------------------------------------------------------

	private void merge(final int insn, final Frame<V> frame,
	final Subroutine subroutine) throws AnalyzerException {
	Frame<V> oldFrame = frames[insn];
	Subroutine oldSubroutine = subroutines[insn];
	boolean changes;

	if (oldFrame == null) {
	frames[insn] = newFrame(frame);
	changes = true;
	} else {
	changes = oldFrame.merge(frame, interpreter);
	}

	if (oldSubroutine == null) {
	if (subroutine != null) {
	subroutines[insn] = subroutine.copy();
	changes = true;
	}
	} else {
	if (subroutine != null) {
	changes \|= oldSubroutine.merge(subroutine);
	}
	}
	if (changes && !queued[insn]) {
	queued[insn] = true;
	queue[top++] = insn;
	}
	}

	private void merge(final int insn, final Frame<V> beforeJSR,
	final Frame<V> afterRET, final Subroutine subroutineBeforeJSR,
	final boolean[] access) throws AnalyzerException {
	Frame<V> oldFrame = frames[insn];
	Subroutine oldSubroutine = subroutines[insn];
	boolean changes;

	afterRET.merge(beforeJSR, access);

	if (oldFrame == null) {
	frames[insn] = newFrame(afterRET);
	changes = true;
	} else {
	changes = oldFrame.merge(afterRET, interpreter);
	}

	if (oldSubroutine != null && subroutineBeforeJSR != null) {
	changes \|= oldSubroutine.merge(subroutineBeforeJSR);
	}
	if (changes && !queued[insn]) {
	queued[insn] = true;
	queue[top++] = insn;
	}
	}
	}