/*

  * Licensed to the Apache Software Foundation (ASF) under one or more

  * contributor license agreements.  See the NOTICE file distributed with

  * this work for additional information regarding copyright ownership.

  * The ASF licenses this file to You under the Apache License, Version 2.0

  * (the "License"); you may not use this file except in compliance with

  * the License.  You may obtain a copy of the License at

  *

  *      http://www.apache.org/licenses/LICENSE-2.0

  *

  * Unless required by applicable law or agreed to in writing, software

  * distributed under the License is distributed on an "AS IS" BASIS,

  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.

  * See the License for the specific language governing permissions and

  * limitations under the License.

  */

 package org.apache.commons.nabla.automatic.analysis;

 import java.util.ArrayList;

 import java.util.HashMap;

 import java.util.HashSet;

 import java.util.IdentityHashMap;

 import java.util.Iterator;

 import java.util.List;

 import java.util.Map;

 import java.util.Set;

 import org.apache.commons.nabla.automatic.arithmetic.DAddTransformer1;

 import org.apache.commons.nabla.automatic.arithmetic.DAddTransformer12;

 import org.apache.commons.nabla.automatic.arithmetic.DAddTransformer2;

 import org.apache.commons.nabla.automatic.arithmetic.DDivTransformer1;

 import org.apache.commons.nabla.automatic.arithmetic.DDivTransformer12;

 import org.apache.commons.nabla.automatic.arithmetic.DDivTransformer2;

 import org.apache.commons.nabla.automatic.arithmetic.DMulTransformer1;

 import org.apache.commons.nabla.automatic.arithmetic.DMulTransformer12;

 import org.apache.commons.nabla.automatic.arithmetic.DMulTransformer2;

 import org.apache.commons.nabla.automatic.arithmetic.DNegTransformer;

 import org.apache.commons.nabla.automatic.arithmetic.DRemTransformer1;

 import org.apache.commons.nabla.automatic.arithmetic.DRemTransformer12;

 import org.apache.commons.nabla.automatic.arithmetic.DRemTransformer2;

 import org.apache.commons.nabla.automatic.arithmetic.DSubTransformer1;

 import org.apache.commons.nabla.automatic.arithmetic.DSubTransformer12;

 import org.apache.commons.nabla.automatic.arithmetic.DSubTransformer2;

 import org.apache.commons.nabla.automatic.functions.AcosTransformer;

 import org.apache.commons.nabla.automatic.functions.AcoshTransformer;

 import org.apache.commons.nabla.automatic.functions.AsinTransformer;

 import org.apache.commons.nabla.automatic.functions.AsinhTransformer;

 import org.apache.commons.nabla.automatic.functions.Atan2Transformer1;

 import org.apache.commons.nabla.automatic.functions.Atan2Transformer12;

 import org.apache.commons.nabla.automatic.functions.Atan2Transformer2;

 import org.apache.commons.nabla.automatic.functions.AtanTransformer;

 import org.apache.commons.nabla.automatic.functions.AtanhTransformer;

 import org.apache.commons.nabla.automatic.functions.CbrtTransformer;

 import org.apache.commons.nabla.automatic.functions.CosTransformer;

 import org.apache.commons.nabla.automatic.functions.CoshTransformer;

 import org.apache.commons.nabla.automatic.functions.ExpTransformer;

 import org.apache.commons.nabla.automatic.functions.Expm1Transformer;

 import org.apache.commons.nabla.automatic.functions.HypotTransformer1;

 import org.apache.commons.nabla.automatic.functions.HypotTransformer12;

 import org.apache.commons.nabla.automatic.functions.HypotTransformer2;

 import org.apache.commons.nabla.automatic.functions.Log10Transformer;

 import org.apache.commons.nabla.automatic.functions.Log1pTransformer;

 import org.apache.commons.nabla.automatic.functions.LogTransformer;

 import org.apache.commons.nabla.automatic.functions.MathInvocationTransformer;

 import org.apache.commons.nabla.automatic.functions.PowTransformer1;

 import org.apache.commons.nabla.automatic.functions.PowTransformer12;

 import org.apache.commons.nabla.automatic.functions.PowTransformer2;

 import org.apache.commons.nabla.automatic.functions.SinTransformer;

 import org.apache.commons.nabla.automatic.functions.SinhTransformer;

 import org.apache.commons.nabla.automatic.functions.SqrtTransformer;

 import org.apache.commons.nabla.automatic.functions.TanTransformer;

 import org.apache.commons.nabla.automatic.functions.TanhTransformer;

 import org.apache.commons.nabla.automatic.instructions.DLoadTransformer;

 import org.apache.commons.nabla.automatic.instructions.DReturnTransformer;

 import org.apache.commons.nabla.automatic.instructions.DStoreTransformer;

 import org.apache.commons.nabla.automatic.instructions.DcmpTransformer1;

 import org.apache.commons.nabla.automatic.instructions.DcmpTransformer12;

 import org.apache.commons.nabla.automatic.instructions.DcmpTransformer2;

 import org.apache.commons.nabla.automatic.instructions.Dup2Transformer;

 import org.apache.commons.nabla.automatic.instructions.Dup2X1Transformer;

 import org.apache.commons.nabla.automatic.instructions.Dup2X2Transformer1;

 import org.apache.commons.nabla.automatic.instructions.Dup2X2Transformer12;

 import org.apache.commons.nabla.automatic.instructions.Dup2X2Transformer2;

 import org.apache.commons.nabla.automatic.instructions.NarrowingTransformer;

 import org.apache.commons.nabla.automatic.instructions.WideningTransformer;

 import org.apache.commons.nabla.automatic.trimming.DLoadPop2Trimmer;

 import org.apache.commons.nabla.automatic.trimming.SwappedDloadTrimmer;

 import org.apache.commons.nabla.automatic.trimming.SwappedDstoreTrimmer;

 import org.apache.commons.nabla.core.DifferentialPair;

 import org.apache.commons.nabla.core.DifferentiationException;

 import org.objectweb.asm.MethodVisitor;

 import org.objectweb.asm.Opcodes;

 import org.objectweb.asm.tree.AbstractInsnNode;

 import org.objectweb.asm.tree.FieldInsnNode;

 import org.objectweb.asm.tree.IincInsnNode;

 import org.objectweb.asm.tree.InsnList;

 import org.objectweb.asm.tree.InsnNode;

 import org.objectweb.asm.tree.LabelNode;

 import org.objectweb.asm.tree.MethodInsnNode;

 import org.objectweb.asm.tree.MethodNode;

 import org.objectweb.asm.tree.VarInsnNode;

 import org.objectweb.asm.tree.analysis.Analyzer;

 import org.objectweb.asm.tree.analysis.AnalyzerException;

 import org.objectweb.asm.tree.analysis.BasicValue;

 import org.objectweb.asm.tree.analysis.Frame;

 import org.objectweb.asm.tree.analysis.Interpreter;

 /** Class transforming a method computing a value to a method

  * computing both a value and its differential.

  */

 public class MethodDifferentiator extends MethodNode {

     /** Name for the DifferentialPair class. */

     public static final String DP_NAME = DifferentialPair.class.getName().replace('.', '/');

     /** Descriptor for the DifferentialPair class. */

     public static final String DP_DESCRIPTOR = "L" + DP_NAME + ";";

     /** Descriptor for the derivative class f method. */

     public static final String DP_RETURN_DP_DESCRIPTOR = "(" + DP_DESCRIPTOR + ")" + DP_DESCRIPTOR;

     /** Descriptor for <code>double f()</code> methods. */

     private static final String VOID_RETURN_D_DESCRIPTOR = "()D";

     /** Math functions transformer. */

     private static final Map<String, MathInvocationTransformer> MATH_TRANSFORMERS =

         new HashMap<String, MathInvocationTransformer>();

     static {

         MATH_TRANSFORMERS.put("acos",     new AcosTransformer());

         MATH_TRANSFORMERS.put("acosh",    new AcoshTransformer());

         MATH_TRANSFORMERS.put("asin",     new AsinTransformer());

         MATH_TRANSFORMERS.put("asinh",    new AsinhTransformer());

         MATH_TRANSFORMERS.put("atan2_12", new Atan2Transformer12());

         MATH_TRANSFORMERS.put("atan2_1",  new Atan2Transformer1());

         MATH_TRANSFORMERS.put("atan2_2",  new Atan2Transformer2());

         MATH_TRANSFORMERS.put("atan",     new AtanTransformer());

         MATH_TRANSFORMERS.put("atanh",    new AtanhTransformer());

         MATH_TRANSFORMERS.put("cbrt",     new CbrtTransformer());

         MATH_TRANSFORMERS.put("cos",      new CosTransformer());

         MATH_TRANSFORMERS.put("cosh",     new CoshTransformer());

         MATH_TRANSFORMERS.put("exp",      new ExpTransformer());

         MATH_TRANSFORMERS.put("expm1",    new Expm1Transformer());

         MATH_TRANSFORMERS.put("hypot_12", new HypotTransformer12());

         MATH_TRANSFORMERS.put("hypot_1",  new HypotTransformer1());

         MATH_TRANSFORMERS.put("hypot_2",  new HypotTransformer2());

         MATH_TRANSFORMERS.put("log10",    new Log10Transformer());

         MATH_TRANSFORMERS.put("log1p",    new Log1pTransformer());

         MATH_TRANSFORMERS.put("log",      new LogTransformer());

         MATH_TRANSFORMERS.put("pow_12",   new PowTransformer12());

         MATH_TRANSFORMERS.put("pow_1",    new PowTransformer1());

         MATH_TRANSFORMERS.put("pow_2",    new PowTransformer2());

         MATH_TRANSFORMERS.put("sin",      new SinTransformer());

         MATH_TRANSFORMERS.put("sinh",     new SinhTransformer());

         MATH_TRANSFORMERS.put("sqrt",     new SqrtTransformer());

         MATH_TRANSFORMERS.put("tan",      new TanTransformer());

         MATH_TRANSFORMERS.put("tanh",     new TanhTransformer());

     }

     /** Message format for unknown method. */

     private static final String UNKNOWN_METHOD_FMT = "unknown method {0}.{1}";

     /** Maximal number of temporary size 2 variables. */

     private static final int MAX_TEMP = 5;

     /** Math implementation classes. */

     private final Set<String> mathClasses;

     /** Generator to use. */

     private final MethodVisitor generator;

     /** Used locals variables array. */

     private boolean[] usedLocals;

     /** Primitive class name. */

     private final String primitiveName;

     /** Error reporter to use. */

     private final ErrorReporter errorReporter;

     /** Set of converted values. */

     private final Set<TrackingValue> converted;

     /** Frames for the original method. */

     private final Map<AbstractInsnNode, Frame> frames;

     /** Instructions successors array. */

     private final Map<AbstractInsnNode, Set<AbstractInsnNode>> successors;

     /** Cloned labels map. */

     private final Map<LabelNode, LabelNode> clonedLabels;

     /** Build a differentiator for a method.

      * @param access access flags of the method

      * @param name name of the method

      * @param desc descriptor of the method

      * @param signature signature of the method

      * @param exceptions exceptions thrown by the method

      * @param generator bytecode generator to use for the transformed method

      * @param primitiveName primitive class name

      * @param mathClasses math implementation classes

      * @param errorReporter reporter used for delaying exceptions

      */

     public MethodDifferentiator(final int access, final String name, final String desc,

                                 final String signature, final String[] exceptions,

                                 final MethodVisitor generator,final  String primitiveName,

                                 final Set<String> mathClasses,

                                 final ErrorReporter errorReporter) {

         super(access, name, desc, signature, exceptions);

         this.generator     = generator;

         this.usedLocals    = null;

         this.primitiveName = primitiveName;

         this.mathClasses   = mathClasses;

         this.errorReporter = errorReporter;

         this.converted     = new HashSet<TrackingValue>();

         this.frames        = new IdentityHashMap<AbstractInsnNode, Frame>();

         this.successors    = new IdentityHashMap<AbstractInsnNode, Set<AbstractInsnNode>>();

         this.clonedLabels  = new HashMap<LabelNode, LabelNode>();

     }

     /** {@inheritDoc} */

     @Override

     public void visitEnd() {

         try {

             // at start, "this" and one differential pair are used

             maxLocals  = 2 * (maxLocals + MAX_TEMP) - 1;

             usedLocals = new boolean[maxLocals];

             useLocal(0, 1);

             useLocal(1, 4);

             // add spare cells to hold new variables if needed

             addSpareLocalVariables();

             // analyze the original code, tracing values production/consumption

             final Frame[] array =

                 new FlowAnalyzer(new TrackingInterpreter()).analyze(primitiveName, this);

             // convert the array into a map, since code changes will shift all indices

             for (int i = 0; i < array.length; ++i) {

                 frames.put(instructions.get(i), array[i]);

             }

             // identify the needed changes

             final Set<AbstractInsnNode> changes = identifyChanges();

             if (changes.isEmpty()) {

                 // the method does not depend on the parameter at all!

                 // we replace all code by a simple "return DifferentialPair.ZERO;"

                 instructions.clear();

                 instructions.add(new FieldInsnNode(Opcodes.GETSTATIC, DP_NAME, "ZERO", DP_DESCRIPTOR));

                 instructions.add(new InsnNode(Opcodes.ARETURN));

             } else {

                 // perform the code changes

                 changeCode(changes);

                 // remove the local variables added at the beginning and not used

                 removeUnusedSpareLocalVariables();

                 // trim generated instructions list

                 SwappedDloadTrimmer.getInstance().trim(instructions);

                 SwappedDstoreTrimmer.getInstance().trim(instructions);

                 DLoadPop2Trimmer.getInstance().trim(instructions);

             }

             // change the descriptor to its true final value

             desc = DP_RETURN_DP_DESCRIPTOR;

             // generate the method

             accept(generator);

         } catch (AnalyzerException ae) {

             if ((ae.getCause() != null) && ae.getCause() instanceof DifferentiationException) {

                 errorReporter.register((DifferentiationException) ae.getCause());

             } else {

                 final DifferentiationException de =

                     new DifferentiationException("unable to analyze the {0}.{1} method ({2})",

                                             new Object[] {

                                                 primitiveName, name, ae.getMessage()

                                             });

                 errorReporter.register(de);

             }

         } catch (DifferentiationException de) {

             errorReporter.register(de);

         }

     }

     /** Add spare cells for new local variables.

      * <p>In order to ease conversion from double values to differential pairs,

      * we start by reserving one spare cell between each original local variables.

      * So we have to modify the indices in all instructions referencing local

      * variables in the original code, to take into account the renumbering

      * introduced by these spare cells. The spare cells by themselves will

      * be referenced by the converted instructions in the following passes.</p>

      * <p>The spare cells that will not be used will be reclaimed after

      * conversion, to avoid wasting memory.</p>

      * @exception DifferentiationException if local variables array has not been

      * expanded appropriately beforehand

      * @see #removeUnusedSpareLocalVariables()

      */

     private void addSpareLocalVariables() throws DifferentiationException {

         for (final Iterator<?> i = instructions.iterator(); i.hasNext();) {

             final AbstractInsnNode insn = (AbstractInsnNode) i.next();

             if (insn.getType() == AbstractInsnNode.VAR_INSN) {

                 final VarInsnNode varInsn = (VarInsnNode) insn;

                 if (varInsn.var > 2) {

                     varInsn.var = 2 * varInsn.var - 1;

                     final int opcode = varInsn.getOpcode();

                     if ((opcode == Opcodes.ILOAD)  || (opcode == Opcodes.FLOAD)  ||

                         (opcode == Opcodes.ALOAD)  || (opcode == Opcodes.ISTORE) ||

                         (opcode == Opcodes.FSTORE) || (opcode == Opcodes.ASTORE)) {

                         useLocal(varInsn.var, 1);

                     } else {

                         useLocal(varInsn.var, 2);

                     }

                 }

             } else if (insn.getOpcode() == Opcodes.IINC) {

                 final IincInsnNode iincInsn = (IincInsnNode) insn;

                 if (iincInsn.var > 2) {

                     iincInsn.var = 2 * iincInsn.var - 1;

                     useLocal(iincInsn.var, 1);

                 }

             }

         }

     }

     /** Remove the unused spare cells introduced at conversion start.

      * @see #addSpareLocalVariables()

      */

     private void removeUnusedSpareLocalVariables() {

         for (final Iterator<?> i = instructions.iterator(); i.hasNext();) {

             final AbstractInsnNode insn = (AbstractInsnNode) i.next();

             if (insn.getType() == AbstractInsnNode.VAR_INSN) {

                 shiftVariable((VarInsnNode) insn);

             }

         }

     }

     /** Identify the instructions that must be changed.

      * <p>Identification is based on data flow analysis. We start by changing

      * the local variables in the initial frame to match the parameters of

      * the derivative method, and propagate these variables following the

      * instructions path, updating stack cells and local variables as needed.

      * Instructions that must be changed are the ones that consume changed

      * variables or stack cells.</p>

      * @return set containing all the instructions that must be changed

      */

     private Set<AbstractInsnNode> identifyChanges() {

         // the pending set contains the values (local variables or stack cells)

         // that have been changed, they will trigger changes on the instructions

         // that consume them

         final Set<TrackingValue> pending = new HashSet<TrackingValue>();

         // the changes set contains the instructions that must be changed

         final Set<AbstractInsnNode> changes = new HashSet<AbstractInsnNode>();

         // start by converting the parameter of the method,

         // which is kept in local variable 1 of the initial frame

         final TrackingValue dpParameter = (TrackingValue) frames.get(instructions.get(0)).getLocal(1);

         pending.add(dpParameter);

         // propagate the values conversions throughout the method

         while (!pending.isEmpty()) {

             // pop one element from the set of changed values

             final Iterator<TrackingValue> iterator = pending.iterator();

             final TrackingValue value = iterator.next();

             iterator.remove();

             // this value is converted

             converted.add(value);

             // check the consumers instructions for this value

             for (final AbstractInsnNode consumer : value.getConsumers()) {

                 // an instruction consuming a converted value and producing

                 // a double must be changed to produce a differential pair,

                 // get the double values produced and add them to the changed set

                 for (TrackingValue produced : getProducedDoubleValues(consumer)) {

                     // add it to the pending set if it has not already been processed

                     if (!converted.contains(produced)) {

                         pending.add(produced);

                     }

                 }

                 // as a consumer of a converted value, the instruction must be changed

                 changes.add(consumer);

             }

             // check the producers instructions for this value

             for (final AbstractInsnNode producer : value.getProducers()) {

                 // an instruction producing a converted value must be changed

                 changes.add(producer);

             }

         }

         return changes;

     }

     /** Get the list of double values produced by an instruction.

      * @param instruction instruction producing the values

      * @return list of double values produced

      */

     private List<TrackingValue> getProducedDoubleValues(final AbstractInsnNode instruction) {

         final List<TrackingValue> values = new ArrayList<TrackingValue>();

         // get the frame before instruction execution

         final Frame before = frames.get(instruction);

         final int beforeStackSize = before.getStackSize();

         final int locals = before.getLocals();

         // check the frames produced by this instruction

         // (they correspond to the input frames of its successors)

         final Set<AbstractInsnNode> set = successors.get(instruction);

         if (set != null) {

             // loop over the successors of this instruction

             for (final AbstractInsnNode successor : set) {

                 final Frame produced = frames.get(successor);

                 // check the stack cells

                 for (int i = 0; i < produced.getStackSize(); ++i) {

                     final TrackingValue value = (TrackingValue) produced.getStack(i);

                     if (((i >= beforeStackSize) || (value != before.getStack(i))) &&

                         value.getValue().equals(BasicValue.DOUBLE_VALUE)) {

                         values.add(value);

                     }

                 }

                 // check the local variables

                 for (int i = 0; i < locals; ++i) {

                     final TrackingValue value = (TrackingValue) produced.getLocal(i);

                     if ((value != before.getLocal(i)) &&

                         value.getValue().equals(BasicValue.DOUBLE_VALUE)) {

                         values.add(value);

                     }

                 }

             }

         }

         return values;

     }

     /** Perform the code changes.

      * @param changes instructions that must be changed

      * @exception DifferentiationException if some instruction cannot be handled

      */

     private void changeCode(final Set<AbstractInsnNode> changes)

         throws DifferentiationException {

         // insert the parameter conversion code at method start

         final InsnList list = new InsnList();

         list.add(new VarInsnNode(Opcodes.ALOAD, 1));

         list.add(new InsnNode(Opcodes.DUP));

         list.add(new MethodInsnNode(Opcodes.INVOKEVIRTUAL, DP_NAME,

                                     "getValue", VOID_RETURN_D_DESCRIPTOR));

         list.add(new VarInsnNode(Opcodes.DSTORE, 1));

         list.add(new MethodInsnNode(Opcodes.INVOKEVIRTUAL, DP_NAME,

                                     "getFirstDerivative", VOID_RETURN_D_DESCRIPTOR));

         list.add(new VarInsnNode(Opcodes.DSTORE, 3));

         instructions.insertBefore(instructions.get(0), list);

         // transform the existing instructions

         for (final AbstractInsnNode insn : changes) {

             instructions.insert(insn, getReplacement(insn));

             instructions.remove(insn);

         }

     }

     /** Get the replacement list for an instruction.

      * @param insn instruction to replace

      * @return replacement instructions list

      * @exception DifferentiationException if some instruction cannot be handled

      * or if no temporary variable can be reserved

      */

     private InsnList getReplacement(final AbstractInsnNode insn)

         throws DifferentiationException {

         // get the frame at the start of the instruction

         final Frame frame = frames.get(insn);

         final int size = frame.getStackSize();

         final boolean stack1Converted = (size > 0) && converted.contains(frame.getStack(size - 2));

         final boolean stack0Converted = (size > 1) && converted.contains(frame.getStack(size - 1));

         switch(insn.getOpcode()) {

         case Opcodes.DLOAD :

             useLocal(((VarInsnNode) insn).var, 4);

             return  DLoadTransformer.getInstance().getReplacement(insn, this);

         case Opcodes.DALOAD :

             // TODO add support for DALOAD differentiation

             throw new RuntimeException("DALOAD not handled yet");

         case Opcodes.DSTORE :

             useLocal(((VarInsnNode) insn).var, 4);

             return  DStoreTransformer.getInstance().getReplacement(insn, this);

         case Opcodes.DASTORE :

             // TODO add support for DASTORE differentiation

             throw new RuntimeException("DASTORE not handled yet");

         case Opcodes.DUP2 :

             return Dup2Transformer.getInstance().getReplacement(insn, this);

         case Opcodes.DUP2_X1 :

             return Dup2X1Transformer.getInstance().getReplacement(insn, this);

         case Opcodes.DUP2_X2 :

             if (stack1Converted) {

                 if (stack0Converted) {

                     return Dup2X2Transformer12.getInstance().getReplacement(insn, this);

                 }

                 return Dup2X2Transformer1.getInstance().getReplacement(insn, this);

             }

             return Dup2X2Transformer2.getInstance().getReplacement(insn, this);

         case Opcodes.DADD :

             if (stack1Converted) {

                 if (stack0Converted) {

                     return DAddTransformer12.getInstance().getReplacement(insn, this);

                 }

                 return DAddTransformer1.getInstance().getReplacement(insn, this);

             }

             return  DAddTransformer2.getInstance().getReplacement(insn, this);

         case Opcodes.DSUB :

             if (stack1Converted) {

                 if (stack0Converted) {

                     return DSubTransformer12.getInstance().getReplacement(insn, this);

                 }

                 return DSubTransformer1.getInstance().getReplacement(insn, this);

             }

             return  DSubTransformer2.getInstance().getReplacement(insn, this);

         case Opcodes.DMUL :

             if (stack1Converted) {

                 if (stack0Converted) {

                     return  DMulTransformer12.getInstance().getReplacement(insn, this);

                 }

                 return  DMulTransformer1.getInstance().getReplacement(insn, this);

             }

             return  DMulTransformer2.getInstance().getReplacement(insn, this);

         case Opcodes.DDIV :

             if (stack1Converted) {

                 if (stack0Converted) {

                     return  DDivTransformer12.getInstance().getReplacement(insn, this);

                 }

                 return  DDivTransformer1.getInstance().getReplacement(insn, this);

             }

             return  DDivTransformer2.getInstance().getReplacement(insn, this);

         case Opcodes.DREM :

             if (stack1Converted) {

                 if (stack0Converted) {

                     return  DRemTransformer12.getInstance().getReplacement(insn, this);

                 }

                 return  DRemTransformer1.getInstance().getReplacement(insn, this);

             }

             return  DRemTransformer2.getInstance().getReplacement(insn, this);

         case Opcodes.DNEG :

             return  DNegTransformer.getInstance().getReplacement(insn, this);

         case Opcodes.DCONST_0 :

         case Opcodes.DCONST_1 :

         case Opcodes.LDC :

         case Opcodes.I2D :

         case Opcodes.L2D :

         case Opcodes.F2D :

             return WideningTransformer.getInstance().getReplacement(insn, this);

         case Opcodes.POP2 :

         case Opcodes.D2I :

         case Opcodes.D2L :

         case Opcodes.D2F :

             return NarrowingTransformer.getInstance().getReplacement(insn, this);

         case Opcodes.DCMPL :

         case Opcodes.DCMPG :

             if (stack1Converted) {

                 if (stack0Converted) {

                     return  DcmpTransformer12.getInstance().getReplacement(insn, this);

                 }

                 return  DcmpTransformer1.getInstance().getReplacement(insn, this);

             }

             return  DcmpTransformer2.getInstance().getReplacement(insn, this);

         case Opcodes.DRETURN :

             return  DReturnTransformer.getInstance().getReplacement(insn, this);

         case Opcodes.GETSTATIC :

             // TODO add support for GETSTATIC differentiation

             throw new RuntimeException("GETSTATIC not handled yet");

         case Opcodes.PUTSTATIC :

             // TODO add support for PUTSTATIC differentiation

             throw new RuntimeException("PUTSTATIC not handled yet");

         case Opcodes.GETFIELD :

             // TODO add support for GETFIELD differentiation

             throw new RuntimeException("GETFIELD not handled yet");

         case Opcodes.PUTFIELD :

             // TODO add support for PUTFIELD differentiation

             throw new RuntimeException("PUTFIELD not handled yet");

         case Opcodes.INVOKEVIRTUAL :

             // TODO add support for INVOKEVIRTUAL differentiation

             throw new RuntimeException("INVOKEVIRTUAL not handled yet");

         case Opcodes.INVOKESPECIAL :

             // TODO add support for INVOKESPECIAL differentiation

             throw new RuntimeException("INVOKESPECIAL not handled yet");

         case Opcodes.INVOKESTATIC :

             return replaceInvocation((MethodInsnNode) insn,

                                      stack1Converted, stack0Converted);

         case Opcodes.INVOKEINTERFACE :

             // TODO add support for INVOKEINTERFACE differentiation

             throw new RuntimeException("INVOKEINTERFACE not handled yet");

         case Opcodes.NEWARRAY :

             // TODO add support for NEWARRAY differentiation

             throw new RuntimeException("NEWARRAY not handled yet");

         case Opcodes.ANEWARRAY :

             // TODO add support for ANEWARRAY differentiation

             throw new RuntimeException("ANEWARRAY not handled yet");

         case Opcodes.MULTIANEWARRAY :

             // TODO add support for MULTIANEWARRAY differentiation

             throw new RuntimeException("MULTIANEWARRAY not handled yet");

         default:

             throw new DifferentiationException("unable to handle instruction with opcode {0}",

                                           new Object[] {

                                               Integer.valueOf(insn.getOpcode())

                                           });

         }

     }

     /** Replace an INVOKESTATIC instruction.

      * @param methodInsn invocation instruction

      * @param stack1Converted if true, the stack sub-head has been

      * converted to differential pair

      * @param stack0Converted if true, the stack head has been

      * converted to differential pair

      * @return replacement instructions list

      * @exception DifferentiationException if the instruction cannot be replaced

      */

     private InsnList replaceInvocation(final MethodInsnNode methodInsn,

                                        final boolean stack1Converted,

                                        final boolean stack0Converted)

         throws DifferentiationException {

         if (isMathImplementationClass(methodInsn.owner)) {

             if ("(D)D".equals(methodInsn.desc)) {

                 // this is a univariate method like sin, cos, exp ...

                 final MathInvocationTransformer transformer = MATH_TRANSFORMERS.get(methodInsn.name);

                 if (transformer == null) {

                     throw new DifferentiationException(UNKNOWN_METHOD_FMT,

                                                   methodInsn.owner, methodInsn.name);

                 }

                 return transformer.getReplacementList(methodInsn.owner, this);

             } else if ("(DD)D".equals(methodInsn.desc)) {

                 // this is a bivariate method like atan2, pow ...

                 // we may want to differentiate against first, second or both parameters

                 String name = null;

                 if (stack1Converted) {

                     if (stack0Converted) {

                         name = methodInsn.name + "_12";

                     } else {

                         name = methodInsn.name + "_1";

                     }

                 } else if (stack0Converted) {

                     name = methodInsn.name + "_2";

                 }

                 if (name != null) {

                     final MathInvocationTransformer transformer = MATH_TRANSFORMERS.get(name);

                     if (transformer == null) {

                         throw new DifferentiationException(UNKNOWN_METHOD_FMT,

                                                       methodInsn.owner, methodInsn.name);

                     }

                     return transformer.getReplacementList(methodInsn.owner, this);

                 }

             }

         }

         throw new DifferentiationException("unexpected instruction {0}",

                                            Integer.valueOf(methodInsn.getOpcode()));

     }

     /** Test if a class is a math implementation class.

      * @param name name of the class to test

      * @return true if the named class is a math implementation class

      */

     public boolean isMathImplementationClass(final String name) {

         return mathClasses.contains(name);

     }

     /** Set a local variable as used by the modified code.

      * @param index index of the variable

      * @param size size of the variable (1 or 2 for standard variables,

      * 4 for special expanded differential pairs)

      * @exception DifferentiationException if the number of the

      * temporary variable lies outside of the allowed range

      */

     public void useLocal(final int index, final int size)

         throws DifferentiationException {

         if ((index < 0) || ((index + size - 1) >= usedLocals.length)) {

             throw new DifferentiationException("index of size {0} local variable ({1}) " +

                                           "outside of [{2}, {3}] range",

                                           Integer.valueOf(size), Integer.valueOf(index),

                                           Integer.valueOf(1), Integer.valueOf(MAX_TEMP));

         }

         for (int i = index; i < index + size; ++i) {

             usedLocals[i] = true;

         }

     }

     /** Get index of a size 2 temporary variable.

      * <p>Temporary variables can be used for very short duration

      * storage of size 2 values (i.e one double, or one long or two

      * integers). These variables are reused in many replacement

      * instructions sequences, so their content may be overridden

      * at any time: they should be considered to have a scope

      * limited to one replacement sequence only. This means that

      * one should <em>not</em> store a value in a variable in one

      * replacement sequence and retrieve it later in another

      * replacement sequence as it may have been overridden in

      * between.</p>

      * <p>At most 5 temporary variables may be used.</p>

      * @param number number of the temporary variable (must be

      * between 1 and the maximal number of available temporary

      * variables)

      * @return index of the variable within the local variables

      * array

      * @exception DifferentiationException if the number of the

      * temporary variable lies outside of the allowed range

      */

     public int getTmp(final int number) throws DifferentiationException {

         if ((number < 0) || (number > MAX_TEMP)) {

             throw new DifferentiationException("number of temporary variable ({0}) outside of [{1}, {2}] range",

                                                Integer.valueOf(number),

                                                Integer.valueOf(1),

                                                Integer.valueOf(MAX_TEMP));

         }

         final int index = usedLocals.length - 2 * number;

         useLocal(index, 2);

         return index;

     }

     /** Shifted the index of a variable instruction.

      * @param insn variable instruction

      */

     public void shiftVariable(final VarInsnNode insn) {

         int shifted = 0;

         for (int i = 0; i < insn.var; ++i) {

             if (usedLocals[i]) {

                 ++shifted;

             }

         }

         insn.var = shifted;

     }

     /** Clone an instruction.

      * @param insn instruction to clone

      * @return cloned instruction

      */

     public AbstractInsnNode clone(final AbstractInsnNode insn) {

         return insn.clone(clonedLabels);

     }

     /** Analyzer preserving instructions successors information. */

     private class FlowAnalyzer extends Analyzer {

         /** Simple constructor.

          * @param interpreter associated interpreter

          */

         public FlowAnalyzer(final Interpreter interpreter) {

             super(interpreter);

         }

         /** Store a new edge.

          * @param insn current instruction

          * @param successor successor instruction

          */

         protected void newControlFlowEdge(final int insn, final int successor) {

             // store the successor information

             final AbstractInsnNode node = instructions.get(insn);

             Set<AbstractInsnNode> set = successors.get(node);

             if (set == null) {

                 set = new HashSet<AbstractInsnNode>();

                 successors.put(node, set);

             }

             set.add(instructions.get(successor));

         }

     }

 }