commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From l..@apache.org
Subject svn commit: r648239 [1/4] - in /commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic: ./ analysis/ arithmetic/ functions/ instructions/ trimming/
Date Tue, 15 Apr 2008 13:20:54 GMT
Author: luc
Date: Tue Apr 15 06:20:36 2008
New Revision: 648239

URL: http://svn.apache.org/viewvc?rev=648239&view=rev
Log:
created bytecode-based automatic differentiation
this implementation uses the ASM bytecode engineering library
it is NOT complete yet!

Added:
    commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/
    commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/analysis/
    commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/analysis/AutomaticDifferentiator.java   (with props)
    commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/analysis/ClassDifferentiator.java   (with props)
    commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/analysis/ErrorReporter.java   (with props)
    commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/analysis/InstructionsTransformer.java   (with props)
    commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/analysis/MethodDifferentiator.java   (with props)
    commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/analysis/TrackingInterpreter.java   (with props)
    commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/analysis/TrackingValue.java   (with props)
    commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/arithmetic/
    commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/arithmetic/DAddTransformer1.java   (with props)
    commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/arithmetic/DAddTransformer12.java   (with props)
    commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/arithmetic/DAddTransformer2.java   (with props)
    commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/arithmetic/DDivTransformer1.java   (with props)
    commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/arithmetic/DDivTransformer12.java   (with props)
    commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/arithmetic/DDivTransformer2.java   (with props)
    commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/arithmetic/DMulTransformer1.java   (with props)
    commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/arithmetic/DMulTransformer12.java   (with props)
    commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/arithmetic/DMulTransformer2.java   (with props)
    commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/arithmetic/DNegTransformer.java   (with props)
    commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/arithmetic/DRemTransformer1.java   (with props)
    commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/arithmetic/DRemTransformer12.java   (with props)
    commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/arithmetic/DRemTransformer2.java   (with props)
    commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/arithmetic/DSubTransformer1.java   (with props)
    commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/arithmetic/DSubTransformer12.java   (with props)
    commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/arithmetic/DSubTransformer2.java   (with props)
    commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/functions/
    commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/functions/AcosTransformer.java   (with props)
    commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/functions/AcoshTransformer.java   (with props)
    commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/functions/AsinTransformer.java   (with props)
    commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/functions/AsinhTransformer.java   (with props)
    commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/functions/Atan2Transformer1.java   (with props)
    commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/functions/Atan2Transformer12.java   (with props)
    commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/functions/Atan2Transformer2.java   (with props)
    commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/functions/AtanTransformer.java   (with props)
    commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/functions/AtanhTransformer.java   (with props)
    commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/functions/CbrtTransformer.java   (with props)
    commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/functions/CosTransformer.java   (with props)
    commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/functions/CoshTransformer.java   (with props)
    commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/functions/ExpTransformer.java   (with props)
    commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/functions/Expm1Transformer.java   (with props)
    commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/functions/HypotTransformer1.java   (with props)
    commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/functions/HypotTransformer12.java   (with props)
    commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/functions/HypotTransformer2.java   (with props)
    commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/functions/Log10Transformer.java   (with props)
    commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/functions/Log1pTransformer.java   (with props)
    commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/functions/LogTransformer.java   (with props)
    commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/functions/MathInvocationTransformer.java   (with props)
    commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/functions/PowTransformer1.java   (with props)
    commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/functions/PowTransformer12.java   (with props)
    commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/functions/PowTransformer2.java   (with props)
    commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/functions/SinTransformer.java   (with props)
    commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/functions/SinhTransformer.java   (with props)
    commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/functions/SqrtTransformer.java   (with props)
    commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/functions/TanTransformer.java   (with props)
    commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/functions/TanhTransformer.java   (with props)
    commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/instructions/
    commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/instructions/DLoadTransformer.java   (with props)
    commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/instructions/DReturnTransformer.java   (with props)
    commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/instructions/DStoreTransformer.java   (with props)
    commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/instructions/DcmpTransformer1.java   (with props)
    commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/instructions/DcmpTransformer12.java   (with props)
    commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/instructions/DcmpTransformer2.java   (with props)
    commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/instructions/Dup2Transformer.java   (with props)
    commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/instructions/Dup2X1Transformer.java   (with props)
    commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/instructions/Dup2X2Transformer1.java   (with props)
    commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/instructions/Dup2X2Transformer12.java   (with props)
    commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/instructions/Dup2X2Transformer2.java   (with props)
    commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/instructions/NarrowingTransformer.java   (with props)
    commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/instructions/WideningTransformer.java   (with props)
    commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/trimming/
    commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/trimming/BytecodeTrimmer.java   (with props)
    commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/trimming/DLoadPop2Trimmer.java   (with props)
    commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/trimming/SwappedDloadTrimmer.java   (with props)
    commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/trimming/SwappedDstoreTrimmer.java   (with props)

Added: commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/analysis/AutomaticDifferentiator.java
URL: http://svn.apache.org/viewvc/commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/analysis/AutomaticDifferentiator.java?rev=648239&view=auto
==============================================================================
--- commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/analysis/AutomaticDifferentiator.java (added)
+++ commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/analysis/AutomaticDifferentiator.java Tue Apr 15 06:20:36 2008
@@ -0,0 +1,218 @@
+/*
+ * 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.io.IOException;
+import java.io.InputStream;
+import java.io.OutputStream;
+import java.lang.reflect.Constructor;
+import java.lang.reflect.InvocationTargetException;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Set;
+
+import org.apache.commons.nabla.core.DifferentialPair;
+import org.apache.commons.nabla.core.DifferentiationException;
+import org.apache.commons.nabla.core.UnivariateDerivative;
+import org.apache.commons.nabla.core.UnivariateDifferentiable;
+import org.apache.commons.nabla.core.UnivariateDifferentiator;
+import org.objectweb.asm.ClassReader;
+import org.objectweb.asm.ClassWriter;
+
+/** Automatic differentiator class based on bytecode analysis.
+ * <p>This class is an implementation of the {@link UnivariateDifferentiator}
+ * interface that computes <em>exact</em> differentials completely automatically
+ * and generate java classes and instances that compute the differential
+ * of the function as if they were hand-coded and compiled.</p>
+ * <p>The derivative bytecode created the first time an instance of a given class
+ * is differentiated is cached and will be reused if other instances of the same class
+ * are to be created later. The cache can also be dumped in a jar file for
+ * use in an application without bringing the full nabla library and its
+ * dependencies.</p>
+ * <p>This differentiator can handle only pure bytecode methods and known methods
+ * from math implementation classes like {@link java.lang.Math Math} or
+ * {@link java.lang.StrictMath StrictMath}. Pure bytecode methods are analyzed
+ * and converted. Methods from math implementation classes are only recognized
+ * by class and name and replaced by predefined derivative code.</p>
+ * @see org.apache.commons.nabla.Fetchdifferentiator
+ */
+public class AutomaticDifferentiator implements UnivariateDifferentiator {
+
+    /** 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;
+
+    /** UnivariateDifferentiable/UnivariateDerivative map. */
+    private final HashMap<Class<? extends UnivariateDifferentiable>,
+    Class<? extends UnivariateDerivative>> map;
+
+    /** Math implementation classes. */
+    private final Set<String> mathClasses;
+
+    /** Simple constructor.
+     * <p>Build a AutomaticDifferentiator instance with an empty cache.</p>
+     */
+    public AutomaticDifferentiator() {
+        map = new HashMap<Class<? extends UnivariateDifferentiable>,
+        Class<? extends UnivariateDerivative>>();
+        mathClasses = new HashSet<String>();
+        addMathImplementation(Math.class);
+        addMathImplementation(StrictMath.class);
+    }
+
+    /** Add an implementation class for mathematical functions.
+     * <p>At construction, the differentiator considers only the {@link
+     * java.lang.Math Math} and {@link java.lang.StrictMath StrictMath}
+     * classes are math implementation classes. It may be useful to add
+     * other class for example to add some missing functions like
+     * inverse hyperbolic cosine that are not provided by the standard
+     * java classes as of Java 1.6.</p>
+     * @param mathClass implementation class for mathematical functions
+     */
+    public void addMathImplementation(final Class<?> mathClass) {
+        mathClasses.add(mathClass.getName().replace('.', '/'));
+    }
+
+    /** Dump the cache into a stream.
+     * @param out output stream where to dump the cache
+     */
+    public void dumpCache(final OutputStream out) {
+        // TODO
+        throw new RuntimeException("not implemented yet");
+    }
+
+    /** {@inheritDoc} */
+    public UnivariateDerivative differentiate(final UnivariateDifferentiable d)
+        throws DifferentiationException {
+
+        // get the derivative class
+        final Class<? extends UnivariateDerivative> derivativeClass =
+            getDerivativeClass(d.getClass());
+
+        try {
+
+            // create the instance
+            final Constructor<? extends UnivariateDerivative> constructor =
+                derivativeClass.getConstructor(d.getClass());
+            return constructor.newInstance(d);
+
+        } catch (InstantiationException ie) {
+            throw new DifferentiationException("abstract class {0} cannot be instantiated ({1})",
+                                               derivativeClass.getName(), ie.getMessage());
+        } catch (IllegalAccessException iae) {
+            throw new DifferentiationException("illegal access to class {0} constructor ({1})",
+                                               derivativeClass.getName(), iae.getMessage());
+        } catch (NoSuchMethodException nsme) {
+            throw new DifferentiationException("class {0} cannot be built from an instance of class {1} ({2})",
+                                               derivativeClass.getName(), d.getClass().getName(), nsme.getMessage());
+        } catch (InvocationTargetException ite) {
+            throw new DifferentiationException("class {0} instantiation from an instance of class {1} failed ({2})",
+                                               derivativeClass.getName(), d.getClass().getName(), ite.getMessage());
+        }
+
+    }
+
+    /** Get the derivative class of a differentiable class.
+     * <p>The derivative class is either built on the fly
+     * or retrieved from the cache if it has been built previously.</p>
+     * @param differentiableClass class to differentiate
+     * @return derivative class
+     * @throws DifferentiationException if the class cannot be differentiated
+     */
+    private Class<? extends UnivariateDerivative>
+    getDerivativeClass(final Class<? extends UnivariateDifferentiable> differentiableClass)
+        throws DifferentiationException {
+
+        // lookup in the map if the class has already been differentiated
+        Class<? extends UnivariateDerivative> derivativeClass =
+            map.get(differentiableClass);
+
+        // build the derivative class if it does not exist yet
+        if (derivativeClass == null) {
+            // perform analytical differentiation
+            derivativeClass = createDerivativeClass(differentiableClass);
+
+            // put the newly created class in the map
+            map.put(differentiableClass, derivativeClass);
+
+        }
+
+        // return the derivative class
+        return derivativeClass;
+
+    }
+
+    /** Build a derivative class of a differentiable class.
+     * @param differentiableClass class to differentiate
+     * @return derivative class
+     * @throws DifferentiationException if the class cannot be differentiated
+     */
+    private Class<? extends UnivariateDerivative>
+    createDerivativeClass(final Class<? extends UnivariateDifferentiable> differentiableClass)
+        throws DifferentiationException {
+        try {
+
+            // set up both ends of the class transform chain
+            final String classResourceName = "/" + differentiableClass.getName().replace('.', '/') + ".class";
+            final InputStream stream = differentiableClass.getResourceAsStream(classResourceName);
+            final ClassReader reader = new ClassReader(stream);
+            final ClassWriter writer = new ClassWriter(reader, ClassWriter.COMPUTE_FRAMES);
+
+            // differentiate the function embedded in the differentiable class
+            final ClassDifferentiator differentiator = new ClassDifferentiator(mathClasses, writer);
+            reader.accept(differentiator, ClassReader.SKIP_DEBUG | ClassReader.SKIP_FRAMES);
+            differentiator.reportErrors();
+
+            // create the derivative class
+            return new DerivativeLoader(differentiableClass).defineClass(differentiator, writer);
+
+        } catch (IOException ioe) {
+            throw new DifferentiationException("class {0} cannot be read ({1})",
+                                          differentiableClass.getName(), ioe.getMessage());
+        }
+    }
+
+    /** Class loader generating derivative classes. */
+    private static class DerivativeLoader extends ClassLoader {
+
+        /** Simple constructor.
+         * @param differentiableClass differentiable class
+         */
+        public DerivativeLoader(final Class<? extends UnivariateDifferentiable> differentiableClass) {
+            super(differentiableClass.getClassLoader());
+        }
+
+        /** Define a derivative class.
+         * @param differentiator class differentiator
+         * @param writer class writer
+         * @return a generated derivative class
+         */
+        @SuppressWarnings("unchecked")
+        public Class<? extends UnivariateDerivative>
+        defineClass(final ClassDifferentiator differentiator, final ClassWriter writer) {
+            final String name = differentiator.getDerivativeClassName().replace('/', '.');
+            final byte[] bytecode = writer.toByteArray();
+            return (Class<? extends UnivariateDerivative>) defineClass(name, bytecode, 0, bytecode.length);
+        }
+    }
+
+}

Propchange: commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/analysis/AutomaticDifferentiator.java
------------------------------------------------------------------------------
    svn:eol-style = native

Added: commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/analysis/ClassDifferentiator.java
URL: http://svn.apache.org/viewvc/commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/analysis/ClassDifferentiator.java?rev=648239&view=auto
==============================================================================
--- commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/analysis/ClassDifferentiator.java (added)
+++ commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/analysis/ClassDifferentiator.java Tue Apr 15 06:20:36 2008
@@ -0,0 +1,264 @@
+/*
+ * 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.Set;
+
+import org.apache.commons.nabla.core.DifferentiationException;
+import org.apache.commons.nabla.core.UnivariateDerivative;
+import org.apache.commons.nabla.core.UnivariateDifferentiable;
+import org.objectweb.asm.AnnotationVisitor;
+import org.objectweb.asm.Attribute;
+import org.objectweb.asm.ClassVisitor;
+import org.objectweb.asm.FieldVisitor;
+import org.objectweb.asm.MethodVisitor;
+import org.objectweb.asm.Opcodes;
+
+/**
+ * Visitor (in asm sense) for differentiating classes.
+ * <p>
+ * This visitor visits classes implementing the
+ * {@link UnivariateDifferentiable UnivariateDifferentiable} interface and convert
+ * them to classes implementing the {@link UnivariateDerivative
+ * UnivariateDerivative} interface.
+ * </p>
+ * <p>
+ * The visitor creates a new class as an inner class of the visited class.
+ * Instances of the generated class are therefore automatically bound to their
+ * primitive instance which is their directly enclosing instance. As such they
+ * have access to the current value of all fields.
+ * </p>
+ * <p>
+ * The visited class bytecode is not changed at all.
+ * </p>
+ */
+class ClassDifferentiator implements ClassVisitor {
+
+    /** Name for the primitive instance field. */
+    private static final String PRIMITIVE_FIELD = "primitive";
+
+    /** Math implementation classes. */
+    private final Set<String> mathClasses;
+
+    /** Class generating visitor. */
+    private final ClassVisitor generator;
+
+    /** Error reporter. */
+    private final ErrorReporter errorReporter;
+
+    /** Primitive class name. */
+    private String primitiveName;
+
+    /** Descriptor for the primitive class. */
+    private String primitiveDesc;
+
+    /** Derivative class name. */
+    private String derivativeName;
+
+    /** Indicator for specific fields and method addition. */
+    private boolean specificMembersAdded;
+
+    /**
+     * Simple constructor.
+     * @param mathClasses math implementation classes
+     * @param generator visitor to which class generation calls will be delegated
+     */
+    public ClassDifferentiator(final Set<String> mathClasses,
+                          final ClassVisitor generator) {
+        this.mathClasses = mathClasses;
+        this.generator   = generator;
+        errorReporter    = new ErrorReporter();
+    }
+
+    /**
+     * Get the name of the derivative class.
+     * @return name of the (generated) derivative class
+     */
+    public String getDerivativeClassName() {
+        return derivativeName;
+    }
+
+    /** {@inheritDoc} */
+    public void visit(final int version, final int access,
+                      final String name, final String signature,
+                      final String superName, final String[] interfaces) {
+        // set up the various names
+        primitiveName = name;
+        derivativeName   = primitiveName + "$NablaUnivariateDerivative";
+        primitiveDesc = "L" + primitiveName + ";";
+
+        // check the UnivariateDifferentiable interface is implemented
+        final Class<UnivariateDifferentiable> uDerClass = UnivariateDifferentiable.class;
+        boolean isDifferentiable = false;
+        for (String interf : interfaces) {
+            try {
+                isDifferentiable =
+                    isDifferentiable || uDerClass.isAssignableFrom(Class.forName(interf.replace('/', '.')));
+            } catch (ClassNotFoundException cnfe) {
+                // simply ignore this inaccessible interface
+            }
+        }
+
+        if (isDifferentiable) {
+            // generate the new class implementing the UnivariateDerivative interface
+            generator.visit(version, Opcodes.ACC_PUBLIC | Opcodes.ACC_SYNTHETIC,
+                            derivativeName, signature, superName,
+                            new String[] {
+                                UnivariateDerivative.class.getName().replace('.', '/')
+                            });
+        } else {
+            errorReporter.register(new DifferentiationException("the {0} class does not implement the {1} interface",
+                                                           name, uDerClass.getName()));
+        }
+
+        specificMembersAdded = false;
+
+    }
+
+    /** {@inheritDoc} */
+    public MethodVisitor visitMethod(final int access, final String name,
+                                     final String desc, final String signature,
+                                     final String[] exceptions) {
+
+        // don't do anything if an error has already been encountered
+        if (errorReporter.hasError()) {
+            return null;
+        }
+
+        if (!specificMembersAdded) {
+            // add the specific members we need
+            addPrimitiveField();
+            addConstructor();
+            addGetPrimitive();
+            specificMembersAdded = true;
+        }
+
+        // is it the "public double f(double)" method we want to differentiate ?
+        if (((access & Opcodes.ACC_PUBLIC) == Opcodes.ACC_PUBLIC) &&
+                "f".equals(name) && "(D)D".equals(desc) &&
+                ((exceptions == null) || (exceptions.length == 0))) {
+
+            // get a generator for the method we are going to create
+            final MethodVisitor visitor =
+                generator.visitMethod(access | Opcodes.ACC_SYNTHETIC, name,
+                                      AutomaticDifferentiator.DP_RETURN_DP_DESCRIPTOR, null, null);
+
+            // make sure our own differentiator will be used to transform the code
+            return new MethodDifferentiator(access, name, desc, signature, exceptions,
+                                       visitor, primitiveName, mathClasses, errorReporter);
+
+        }
+
+        // we are not interested in this method
+        return null;
+
+    }
+
+    /** {@inheritDoc} */
+    public FieldVisitor visitField(final int access, final String name,
+                                   final String desc, final  String signature,
+                                   final Object value) {
+        // we are not interested in any fields
+        return null;
+    }
+
+    /** {@inheritDoc} */
+    public void visitSource(final String source, final String debug) {
+    }
+
+    /** {@inheritDoc} */
+    public void visitOuterClass(final String owner, final String name,
+                                final String desc) {
+    }
+
+    /** {@inheritDoc} */
+    public AnnotationVisitor visitAnnotation(final String desc,
+                                             final boolean visible) {
+        return null;
+    }
+
+    /** {@inheritDoc} */
+    public void visitAttribute(final Attribute attr) {
+    }
+
+    /** {@inheritDoc} */
+    public void visitInnerClass(final String name, final String outerName,
+                                final String innerName, final int access) {
+    }
+
+    /** {@inheritDoc} */
+    public void visitEnd() {
+
+        // don't do anything if an error has already been encountered
+        if (errorReporter.hasError()) {
+            return;
+        }
+
+        generator.visitEnd();
+
+    }
+
+    /** Add the primitive field.
+     */
+    private void addPrimitiveField() {
+        final FieldVisitor visitor =
+            generator.visitField(Opcodes.ACC_PRIVATE | Opcodes.ACC_FINAL | Opcodes.ACC_SYNTHETIC,
+                                 PRIMITIVE_FIELD, primitiveDesc, null, null);
+        visitor.visitEnd();
+    }
+
+    /** Add the class constructor.
+     */
+    private void addConstructor() {
+        final String init = "<init>";
+        final MethodVisitor visitor =
+            generator.visitMethod(Opcodes.ACC_PUBLIC | Opcodes.ACC_SYNTHETIC, init,
+                                  "(" + primitiveDesc + ")V", null, null);
+        visitor.visitCode();
+        visitor.visitVarInsn(Opcodes.ALOAD, 0);
+        visitor.visitMethodInsn(Opcodes.INVOKESPECIAL, "java/lang/Object", init, "()V");
+        visitor.visitVarInsn(Opcodes.ALOAD, 0);
+        visitor.visitVarInsn(Opcodes.ALOAD, 1);
+        visitor.visitFieldInsn(Opcodes.PUTFIELD, derivativeName, PRIMITIVE_FIELD, primitiveDesc);
+        visitor.visitInsn(Opcodes.RETURN);
+        visitor.visitMaxs(0, 0);
+        visitor.visitEnd();
+    }
+
+    /** Add the {@link UnivariateDerivative#getPrimitive() getPrimitive()} method.
+     */
+    private void addGetPrimitive() {
+        final MethodVisitor visitor =
+            generator.visitMethod(Opcodes.ACC_PUBLIC | Opcodes.ACC_SYNTHETIC, "getPrimitive",
+                                  "()" + primitiveDesc, null, null);
+        visitor.visitCode();
+        visitor.visitVarInsn(Opcodes.ALOAD, 0);
+        visitor.visitFieldInsn(Opcodes.GETFIELD, derivativeName, PRIMITIVE_FIELD, primitiveDesc);
+        visitor.visitInsn(Opcodes.ARETURN);
+        visitor.visitMaxs(0, 0);
+        visitor.visitEnd();
+    }
+
+    /** Report the errors that may have occurred during analysis.
+     * @exception DifferentiationException if the derivative class
+     * could not be generated
+     */
+    public void reportErrors() throws DifferentiationException {
+        errorReporter.reportErrors();
+    }
+
+}

Propchange: commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/analysis/ClassDifferentiator.java
------------------------------------------------------------------------------
    svn:eol-style = native

Added: commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/analysis/ErrorReporter.java
URL: http://svn.apache.org/viewvc/commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/analysis/ErrorReporter.java?rev=648239&view=auto
==============================================================================
--- commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/analysis/ErrorReporter.java (added)
+++ commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/analysis/ErrorReporter.java Tue Apr 15 06:20:36 2008
@@ -0,0 +1,55 @@
+/*
+ * 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 org.apache.commons.nabla.core.DifferentiationException;
+
+/** Class used for delayed error reporting.
+ */
+public class ErrorReporter {
+
+    /** Error report. */
+    private DifferentiationException reportedError;
+
+    /** Register an exception to be reported later.
+     * @param exception exception to be reported
+     */
+    public void register(final DifferentiationException exception) {
+        reportedError = exception;
+    }
+
+    /** Check if an error has already been registered.
+     * @return true if an error has already been registered
+     */
+    public boolean hasError() {
+        return reportedError != null;
+    }
+
+    /** Report the error if any.
+     * <p>If not error has been reported (i.e. if {@link #hasError()} returns
+     * <code>false</code>), this method does nothing. Otherwise, it rethrows
+     * the original exception.</p>
+     * @exception DifferentiationException if some error occurred
+     * during differentiation
+     */
+    public void reportErrors() throws DifferentiationException {
+        if (reportedError != null) {
+            throw reportedError;
+        }
+    }
+
+}

Propchange: commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/analysis/ErrorReporter.java
------------------------------------------------------------------------------
    svn:eol-style = native

Added: commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/analysis/InstructionsTransformer.java
URL: http://svn.apache.org/viewvc/commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/analysis/InstructionsTransformer.java?rev=648239&view=auto
==============================================================================
--- commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/analysis/InstructionsTransformer.java (added)
+++ commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/analysis/InstructionsTransformer.java Tue Apr 15 06:20:36 2008
@@ -0,0 +1,40 @@
+/*
+ * 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 org.apache.commons.nabla.core.DifferentiationException;
+import org.objectweb.asm.tree.AbstractInsnNode;
+import org.objectweb.asm.tree.InsnList;
+
+/** Transformer for bytecode instructions.
+ * <p>Transformation is done by replacing a single instruction with
+ * a complete list.</p>
+ */
+public interface InstructionsTransformer {
+
+    /** Get the replacement instructions.
+     * @param original original instruction
+     * @param methodDifferentiator method differentiator driving this transformer
+     * @return replacement instructions
+     * @exception DifferentiationException if the method differentiator cannot provide
+     * a temporary variable
+     */
+    InsnList getReplacement(AbstractInsnNode original,
+                            MethodDifferentiator methodDifferentiator)
+        throws DifferentiationException;
+
+}

Propchange: commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/analysis/InstructionsTransformer.java
------------------------------------------------------------------------------
    svn:eol-style = native

Added: commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/analysis/MethodDifferentiator.java
URL: http://svn.apache.org/viewvc/commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/analysis/MethodDifferentiator.java?rev=648239&view=auto
==============================================================================
--- commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/analysis/MethodDifferentiator.java (added)
+++ commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/analysis/MethodDifferentiator.java Tue Apr 15 06:20:36 2008
@@ -0,0 +1,786 @@
+/*
+ * 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.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 {
+
+    /** 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,
+                                                   AutomaticDifferentiator.DP_NAME,
+                                                   "ZERO",
+                                                   AutomaticDifferentiator.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 = AutomaticDifferentiator.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, AutomaticDifferentiator.DP_NAME, "getU0",
+                                    VOID_RETURN_D_DESCRIPTOR));
+        list.add(new VarInsnNode(Opcodes.DSTORE, 1));
+        list.add(new MethodInsnNode(Opcodes.INVOKEVIRTUAL, AutomaticDifferentiator.DP_NAME, "getU1",
+                                    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 DALOAD
+            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 DASTORE
+            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 GETSTATIC
+            throw new RuntimeException("GETSTATIC not handled yet");
+        case Opcodes.PUTSTATIC :
+            // TODO PUTSTATIC
+            throw new RuntimeException("PUTSTATIC not handled yet");
+        case Opcodes.GETFIELD :
+            // TODO GETFIELD
+            throw new RuntimeException("GETFIELD not handled yet");
+        case Opcodes.PUTFIELD :
+            // TODO PUTFIELD
+            throw new RuntimeException("PUTFIELD not handled yet");
+        case Opcodes.INVOKEVIRTUAL :
+            // TODO INVOKEVIRTUAL
+            throw new RuntimeException("INVOKEVIRTUAL not handled yet");
+        case Opcodes.INVOKESPECIAL :
+            // TODO INVOKESPECIAL
+            throw new RuntimeException("INVOKESPECIAL not handled yet");
+        case Opcodes.INVOKESTATIC :
+            return replaceInvocation((MethodInsnNode) insn,
+                                     stack1Converted, stack0Converted);
+        case Opcodes.INVOKEINTERFACE :
+            // TODO INVOKEINTERFACE
+            throw new RuntimeException("INVOKEINTERFACE not handled yet");
+        case Opcodes.NEWARRAY :
+            // TODO NEWARRAY
+            throw new RuntimeException("NEWARRAY not handled yet");
+        case Opcodes.ANEWARRAY :
+            // TODO ANEWARRAY
+            throw new RuntimeException("ANEWARRAY not handled yet");
+        case Opcodes.MULTIANEWARRAY :
+            // TODO MULTIANEWARRAY
+            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));
+        }
+
+    }
+
+}

Propchange: commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/analysis/MethodDifferentiator.java
------------------------------------------------------------------------------
    svn:eol-style = native

Added: commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/analysis/TrackingInterpreter.java
URL: http://svn.apache.org/viewvc/commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/analysis/TrackingInterpreter.java?rev=648239&view=auto
==============================================================================
--- commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/analysis/TrackingInterpreter.java (added)
+++ commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/analysis/TrackingInterpreter.java Tue Apr 15 06:20:36 2008
@@ -0,0 +1,148 @@
+/*
+ * 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.Iterator;
+import java.util.List;
+
+import org.objectweb.asm.Type;
+import org.objectweb.asm.tree.AbstractInsnNode;
+import org.objectweb.asm.tree.analysis.AnalyzerException;
+import org.objectweb.asm.tree.analysis.BasicInterpreter;
+import org.objectweb.asm.tree.analysis.BasicValue;
+import org.objectweb.asm.tree.analysis.Value;
+
+/** An interpreter tracking which instructions use which values.
+ * <p>This interpreter wraps {@link org.objectweb.asm.tree.analysis.BasicValue
+ * BasicValue} instances into {@link TrackingValue TrackingValue} instances.</p>
+ */
+public class TrackingInterpreter extends BasicInterpreter {
+
+    /** Build an interpreter.
+     */
+    public TrackingInterpreter() {
+    }
+
+    /** {@inheritDoc} */
+    @Override
+    public Value newValue(final Type type) {
+        return (type == null) ? TrackingValue.UNINITIALIZED_VALUE : wrap(super.newValue(type), null);
+    }
+
+    /** {@inheritDoc} */
+    @Override
+    public Value newOperation(final AbstractInsnNode insn) {
+        return wrap(super.newOperation(insn), insn);
+    }
+
+    /** {@inheritDoc} */
+    @Override
+    public Value unaryOperation(final AbstractInsnNode insn,
+                                final Value value)
+        throws AnalyzerException {
+        ((TrackingValue) value).addConsumer(insn);
+        return wrap(super.unaryOperation(insn, value), insn);
+    }
+
+    /** {@inheritDoc} */
+    @Override
+    public Value binaryOperation(final AbstractInsnNode insn,
+                                 final Value value1, final Value value2)
+        throws AnalyzerException {
+        ((TrackingValue) value1).addConsumer(insn);
+        ((TrackingValue) value2).addConsumer(insn);
+        return wrap(super.binaryOperation(insn, value1, value2), insn);
+    }
+
+    /** {@inheritDoc} */
+    @Override
+    public Value ternaryOperation(final AbstractInsnNode insn,
+                                  final Value value1, final Value value2,
+                                  final Value value3)
+        throws AnalyzerException {
+        ((TrackingValue) value1).addConsumer(insn);
+        ((TrackingValue) value2).addConsumer(insn);
+        ((TrackingValue) value3).addConsumer(insn);
+        return wrap(super.ternaryOperation(insn, value1, value2, value3), insn);
+    }
+
+    /** {@inheritDoc} */
+    @SuppressWarnings("unchecked")
+    @Override
+    public Value naryOperation(final AbstractInsnNode insn,
+                               final List values)
+        throws AnalyzerException {
+        for (final Iterator<?> iterator = values.iterator(); iterator.hasNext();) {
+            ((TrackingValue) iterator.next()).addConsumer(insn);
+        }
+        return wrap(super.naryOperation(insn, values), insn);
+    }
+
+    /** {@inheritDoc} */
+    @Override
+    public Value copyOperation(final AbstractInsnNode insn,
+                               final Value value)
+        throws AnalyzerException {
+        // we reuse the same instance instead of wrapping it again
+        // thus simplifying transitive dependencies propagation
+        final TrackingValue tv = (TrackingValue) value;
+        tv.addConsumer(insn);
+        tv.addProducer(insn);
+        return value;
+    }
+
+    /** {@inheritDoc} */
+    @Override
+    public Value merge(final Value v, final Value w) {
+
+        final TrackingValue tv = (TrackingValue) v;
+        final TrackingValue tw = (TrackingValue) w;
+        TrackingValue.merge(tv, tw);
+
+        final BasicValue superMerged = (BasicValue) super.merge(tv.getValue(), tw.getValue());
+        return (superMerged == tv.getValue()) ? tv : new TrackingValue(superMerged);
+
+    }
+
+    /** Wrap a value returned by the superclass.
+     * @param value underlying value (may be null)
+     * @param producer instruction producing the value (may be null)
+     * @return the wrapped value
+     */
+    private TrackingValue wrap(final Value value,
+                               final AbstractInsnNode producer) {
+
+        if (value == null) {
+            return null;
+        }
+
+        // values produced by the superclass are either BasicValue instances
+        // (like BasicValue.DOUBLE_VALUE) or already TrackingValue if the
+        // superclass called our local implementation of newValue or newOperation
+        final TrackingValue tv = (value instanceof TrackingValue) ?
+                                 (TrackingValue) value :
+                                 new TrackingValue((BasicValue) value);
+
+        if (producer != null) {
+            tv.addProducer(producer);
+        }
+
+        return tv;
+
+    }
+
+}

Propchange: commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/analysis/TrackingInterpreter.java
------------------------------------------------------------------------------
    svn:eol-style = native

Added: commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/analysis/TrackingValue.java
URL: http://svn.apache.org/viewvc/commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/analysis/TrackingValue.java?rev=648239&view=auto
==============================================================================
--- commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/analysis/TrackingValue.java (added)
+++ commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/analysis/TrackingValue.java Tue Apr 15 06:20:36 2008
@@ -0,0 +1,123 @@
+/*
+ * 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.HashSet;
+import java.util.Set;
+
+import org.objectweb.asm.tree.AbstractInsnNode;
+import org.objectweb.asm.tree.analysis.BasicValue;
+import org.objectweb.asm.tree.analysis.Value;
+
+/** A value that keep track of both instructions producing and consuming it.
+ */
+public class TrackingValue implements Value {
+
+    /** Special value for uninitialized values. */
+    public static final TrackingValue UNINITIALIZED_VALUE =
+        new TrackingValue((BasicValue) BasicValue.UNINITIALIZED_VALUE);
+
+    /** Underlying value. */
+    private final BasicValue value;
+
+    /** Instructions that consume this value. */
+    private Set<AbstractInsnNode> consumers;
+
+    /** Instructions that produce this value. */
+    private Set<AbstractInsnNode> producers;
+
+    /** Values that are merged with this value. */
+    private Set<TrackingValue> merged;
+
+    /** Build a new value without any link to instructions.
+     * @param value wrapped {@link BasicValue} value
+     */
+    public TrackingValue(final BasicValue value) {
+        this.value = value;
+        consumers  = new HashSet<AbstractInsnNode>();
+        producers  = new HashSet<AbstractInsnNode>();
+        merged     = new HashSet<TrackingValue>();
+    }
+
+    /** Get the wrapped {@link BasicValue}.
+     * @return wrapped {@link BasicValue}
+     */
+    public BasicValue getValue() {
+        return value;
+    }
+
+    /** {@inheritDoc} */
+    public int getSize() {
+        return value.getSize();
+    }
+
+    /** Add a consumer for this value.
+     * @param consumer consumer for this value
+     */
+    public void addConsumer(final AbstractInsnNode consumer) {
+        consumers.add(consumer);
+    }
+
+    /** Get the consumers for this value and all values it is merged with.
+     * @return the instructions consuming either this value or the values
+     * it has been merged with
+     */
+    public Set<AbstractInsnNode> getConsumers() {
+        return consumers;
+    }
+
+    /** Add a producer for this value.
+     * @param producer producer for this value
+     */
+    public void addProducer(final AbstractInsnNode producer) {
+        producers.add(producer);
+    }
+
+    /** Get the producers for this value and all values it is merged with.
+     * @return the instructions producing either this value or the values
+     * it has been merged with
+     */
+    public Set<AbstractInsnNode> getProducers() {
+        return producers;
+    }
+
+    /** Merge two instances.
+     * <p>Once merged, values share the same producers and consumers sets.</p>
+     * @param value1 first value to merge
+     * @param value2 second value to merge
+     */
+    public static void merge(final TrackingValue value1,
+                             final TrackingValue value2) {
+
+        // merge the sets
+        value1.consumers.addAll(value2.consumers);
+        value1.producers.addAll(value2.producers);
+        value1.merged.addAll(value2.merged);
+
+        // share the merged sets
+        for (TrackingValue value : value2.merged) {
+            value.consumers = value1.consumers;
+            value.producers = value1.producers;
+            value.merged    = value1.merged;
+        }
+        value2.consumers = value1.consumers;
+        value2.producers = value1.producers;
+        value2.merged    = value1.merged;
+
+    }
+
+}

Propchange: commons/sandbox/nabla/trunk/src/main/java/org/apache/commons/nabla/automatic/analysis/TrackingValue.java
------------------------------------------------------------------------------
    svn:eol-style = native



Mime
View raw message