001 /*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements. See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License. You may obtain a copy of the License at
008 *
009 * http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017 package org.apache.commons.nabla.forward.analysis;
018
019 import java.util.ArrayList;
020 import java.util.HashSet;
021 import java.util.IdentityHashMap;
022 import java.util.Iterator;
023 import java.util.List;
024 import java.util.ListIterator;
025 import java.util.Map;
026 import java.util.Set;
027
028 import org.apache.commons.math3.analysis.differentiation.DerivativeStructure;
029 import org.apache.commons.nabla.DifferentiationException;
030 import org.apache.commons.nabla.NablaMessages;
031 import org.apache.commons.nabla.forward.arithmetic.DAddTransformer;
032 import org.apache.commons.nabla.forward.arithmetic.DDivTransformer;
033 import org.apache.commons.nabla.forward.arithmetic.DMulTransformer;
034 import org.apache.commons.nabla.forward.arithmetic.DNegTransformer;
035 import org.apache.commons.nabla.forward.arithmetic.DRemTransformer;
036 import org.apache.commons.nabla.forward.arithmetic.DSubTransformer;
037 import org.apache.commons.nabla.forward.instructions.DLoadTransformer;
038 import org.apache.commons.nabla.forward.instructions.DReturnTransformer;
039 import org.apache.commons.nabla.forward.instructions.DStoreTransformer;
040 import org.apache.commons.nabla.forward.instructions.DcmpTransformer;
041 import org.apache.commons.nabla.forward.instructions.Dup2Transformer;
042 import org.apache.commons.nabla.forward.instructions.Dup2X1Transformer;
043 import org.apache.commons.nabla.forward.instructions.Dup2X2Transformer;
044 import org.apache.commons.nabla.forward.instructions.InvokeStaticTransformer;
045 import org.apache.commons.nabla.forward.instructions.NarrowingTransformer;
046 import org.apache.commons.nabla.forward.instructions.Pop2Transformer;
047 import org.apache.commons.nabla.forward.instructions.WideningTransformer;
048 import org.apache.commons.nabla.forward.trimming.DLoadPop2Trimmer;
049 import org.apache.commons.nabla.forward.trimming.SwappedDloadTrimmer;
050 import org.apache.commons.nabla.forward.trimming.SwappedDstoreTrimmer;
051 import org.objectweb.asm.Opcodes;
052 import org.objectweb.asm.Type;
053 import org.objectweb.asm.tree.AbstractInsnNode;
054 import org.objectweb.asm.tree.FieldInsnNode;
055 import org.objectweb.asm.tree.IincInsnNode;
056 import org.objectweb.asm.tree.InsnList;
057 import org.objectweb.asm.tree.InsnNode;
058 import org.objectweb.asm.tree.LdcInsnNode;
059 import org.objectweb.asm.tree.MethodInsnNode;
060 import org.objectweb.asm.tree.MethodNode;
061 import org.objectweb.asm.tree.TypeInsnNode;
062 import org.objectweb.asm.tree.VarInsnNode;
063 import org.objectweb.asm.tree.analysis.Analyzer;
064 import org.objectweb.asm.tree.analysis.AnalyzerException;
065 import org.objectweb.asm.tree.analysis.Frame;
066 import org.objectweb.asm.tree.analysis.Interpreter;
067
068 /** Class transforming a method computing a value to a method
069 * computing both a value and its differential.
070 * @version $Id$
071 */
072 public class MethodDifferentiator {
073
074 /** Maximal number of temporary size 2 variables. */
075 private static final int MAX_TEMP = 5;
076
077 /** Math implementation classes. */
078 private final Set<String> mathClasses;
079
080 /** Name of the derived class. */
081 private final String derivedName;
082
083 /** Used locals variables array. */
084 private boolean[] usedLocals;
085
086 /** Set of converted values. */
087 private final Set<TrackingValue> converted;
088
089 /** Frames for the original method. */
090 private final Map<AbstractInsnNode, Frame<TrackingValue>> frames;
091
092 /** Instructions successors array. */
093 private final Map<AbstractInsnNode, Set<AbstractInsnNode>> successors;
094
095 /** Build a differentiator for a method.
096 * @param mathClasses math implementation classes
097 * @param derivedName name of the derived class
098 */
099 public MethodDifferentiator(final Set<String> mathClasses, final String derivedName) {
100 this.usedLocals = null;
101 this.mathClasses = mathClasses;
102 this.derivedName = derivedName;
103 this.converted = new HashSet<TrackingValue>();
104 this.frames = new IdentityHashMap<AbstractInsnNode, Frame<TrackingValue>>();
105 this.successors = new IdentityHashMap<AbstractInsnNode, Set<AbstractInsnNode>>();
106 }
107
108 /** Get the index of the input {@link DerivativeStructure derivative structure} variable.
109 * @return index of the input {@link DerivativeStructure derivative structure} variable
110 */
111 public int getInputDSIndex() {
112 // TODO: this should be improved in the general case,
113 // as we are not sure the variable will always remain at index 1
114 return 1;
115 }
116
117 /**
118 * Differentiate a method.
119 * @param primitiveName primitive class name
120 * @param method method to differentiate (<em>will</em> be modified)
121 * @exception DifferentiationException if method cannot be differentiated
122 */
123 public void differentiate(final String primitiveName, final MethodNode method)
124 throws DifferentiationException {
125 try {
126
127 // at start, "this" and one DerivativeStructure are already used
128 method.maxLocals = 2 * (method.maxLocals + MAX_TEMP) - 1;
129 usedLocals = new boolean[method.maxLocals];
130 useLocal(0, 1);
131 useLocal(1, 4);
132
133 final Type dsType = Type.getType(DerivativeStructure.class);
134
135 // add spare cells to hold new variables if needed
136 addSpareLocalVariables(method.instructions);
137
138 // analyze the original code, tracing values production/consumption
139 final FlowAnalyzer analyzer =
140 new FlowAnalyzer(new TrackingInterpreter(), method.instructions);
141 final Frame<TrackingValue>[] array = analyzer.analyze(primitiveName, method);
142
143 // convert the array into a map, since code changes will shift all indices
144 for (int i = 0; i < array.length; ++i) {
145 frames.put(method.instructions.get(i), array[i]);
146 }
147
148 // identify the needed changes
149 final Set<AbstractInsnNode> changes = identifyChanges(method.instructions);
150
151 if (changes.isEmpty()) {
152
153 // TODO: merge this case with the general case: DRETURN must always be
154 // changed when the function signature changes, and the change is either
155 // converting DRETURN to ARETURN, possibly with a prepended call to
156 // convertDoubleToDerivativeStructure before the ARETURN when stack0converted
157 // is false
158
159 // the method does not depend on the parameter at all!
160 // we replace all "return d;" by "return new DerivativeStructure(parameters, order, d);"
161 for (final Iterator<AbstractInsnNode> i = method.instructions.iterator(); i.hasNext();) {
162 final AbstractInsnNode insn = i.next();
163 if (insn.getOpcode() == Opcodes.DRETURN) {
164 final InsnList list = new DReturnTransformer(false).getReplacement(insn, this);
165 method.instructions.insert(insn, list);
166 method.instructions.remove(insn);
167 }
168 }
169
170 } else {
171
172 // perform the code changes
173 for (final AbstractInsnNode insn : changes) {
174 method.instructions.insert(insn, getReplacement(insn));
175 method.instructions.remove(insn);
176 }
177
178 // trim generated instructions list
179 new SwappedDloadTrimmer().trim(method.instructions);
180 new SwappedDstoreTrimmer().trim(method.instructions);
181 new DLoadPop2Trimmer().trim(method.instructions);
182
183 }
184
185 // remove the local variables added at the beginning and not used
186 removeUnusedSpareLocalVariables(method.instructions);
187
188 // set the method properties
189 method.desc = Type.getMethodDescriptor(dsType, dsType);
190 method.access |= Opcodes.ACC_SYNTHETIC;
191 method.maxLocals = maxVariables();
192
193 } catch (AnalyzerException ae) {
194 ae.printStackTrace(System.err);
195 if ((ae.getCause() != null) && ae.getCause() instanceof DifferentiationException) {
196 throw (DifferentiationException) ae.getCause();
197 } else {
198 throw new DifferentiationException(NablaMessages.UNABLE_TO_ANALYZE_METHOD,
199 primitiveName, method.name, ae.getMessage());
200 }
201 }
202 }
203
204 /** Add spare cells for new local variables.
205 * <p>In order to ease conversion from double values to derivative structures,
206 * we start by reserving one spare cell between each original local variables.
207 * So we have to modify the indices in all instructions referencing local
208 * variables in the original code, to take into account the renumbering
209 * introduced by these spare cells. The spare cells by themselves will
210 * be referenced by the converted instructions in the following passes.</p>
211 * <p>The spare cells that will not be used will be reclaimed after
212 * conversion, to avoid wasting memory.</p>
213 * @param instructions instructions of the method
214 * @exception DifferentiationException if local variables array has not been
215 * expanded appropriately beforehand
216 * @see #removeUnusedSpareLocalVariables()
217 */
218 private void addSpareLocalVariables(final InsnList instructions)
219 throws DifferentiationException {
220 for (final Iterator<AbstractInsnNode> i = instructions.iterator(); i.hasNext();) {
221 final AbstractInsnNode insn = i.next();
222 if (insn.getType() == AbstractInsnNode.VAR_INSN) {
223 final VarInsnNode varInsn = (VarInsnNode) insn;
224 if (varInsn.var > 2) {
225 varInsn.var = 2 * varInsn.var - 1;
226 final int opcode = varInsn.getOpcode();
227 if ((opcode == Opcodes.ILOAD) || (opcode == Opcodes.FLOAD) ||
228 (opcode == Opcodes.ALOAD) || (opcode == Opcodes.ISTORE) ||
229 (opcode == Opcodes.FSTORE) || (opcode == Opcodes.ASTORE)) {
230 useLocal(varInsn.var, 1);
231 } else {
232 useLocal(varInsn.var, 2);
233 }
234 }
235 } else if (insn.getOpcode() == Opcodes.IINC) {
236 final IincInsnNode iincInsn = (IincInsnNode) insn;
237 if (iincInsn.var > 2) {
238 iincInsn.var = 2 * iincInsn.var - 1;
239 useLocal(iincInsn.var, 1);
240 }
241 }
242 }
243 }
244
245 /** Remove the unused spare cells introduced at conversion start.
246 * @param instructions instructions of the method
247 * @see #addSpareLocalVariables()
248 */
249 private void removeUnusedSpareLocalVariables(final InsnList instructions) {
250 for (final Iterator<AbstractInsnNode> i = instructions.iterator(); i.hasNext();) {
251 final AbstractInsnNode insn = i.next();
252 if (insn.getType() == AbstractInsnNode.VAR_INSN) {
253 shiftVariable((VarInsnNode) insn);
254 }
255 }
256 }
257
258 /** Identify the instructions that must be changed.
259 * <p>Identification is based on data flow analysis. We start by changing
260 * the local variables in the initial frame to match the parameters of
261 * the derivative method, and propagate these variables following the
262 * instructions path, updating stack cells and local variables as needed.
263 * Instructions that must be changed are the ones that consume changed
264 * variables or stack cells.</p>
265 * @param instructions instructions of the method
266 * @return set containing all the instructions that must be changed
267 */
268 private Set<AbstractInsnNode> identifyChanges(final InsnList instructions) {
269
270 // the pending set contains the values (local variables or stack cells)
271 // that have been changed, they will trigger changes on the instructions
272 // that consume them
273 final Set<TrackingValue> pending = new HashSet<TrackingValue>();
274
275 // the changes set contains the instructions that must be changed
276 final Set<AbstractInsnNode> changes = new HashSet<AbstractInsnNode>();
277
278 // start by converting the parameter of the method,
279 // which is kept in local variable 1 of the initial frame
280 final TrackingValue dpParameter = frames.get(instructions.get(0)).getLocal(1);
281 pending.add(dpParameter);
282
283 // propagate the values conversions throughout the method
284 while (!pending.isEmpty()) {
285
286 // pop one element from the set of changed values
287 final Iterator<TrackingValue> iterator = pending.iterator();
288 final TrackingValue value = iterator.next();
289 iterator.remove();
290
291 // this value is converted
292 converted.add(value);
293
294 // check the consumers instructions for this value
295 for (final AbstractInsnNode consumer : value.getConsumers()) {
296
297 // an instruction consuming a converted value and producing
298 // a double must be changed to produce a derivative structure,
299 // get the double values produced and add them to the changed set
300 pending.addAll(getProducedAndNotConvertedDoubleValues(consumer));
301
302 // as a consumer of a converted value, the instruction must be changed
303 changes.add(consumer);
304
305 }
306
307 // check the producers instructions for this value
308 for (final AbstractInsnNode producer : value.getProducers()) {
309
310 // an instruction producing a converted value must be changed
311 changes.add(producer);
312
313 }
314 }
315
316 // the various GETFIELD/PUTFIELD instructions must also be changed
317 // to retrieve the field from the outer class
318 final ListIterator<AbstractInsnNode> iterator = instructions.iterator();
319 while (iterator.hasNext()) {
320 final AbstractInsnNode ins = iterator.next();
321 if ((ins.getOpcode() == Opcodes.GETFIELD) || (ins.getOpcode() == Opcodes.PUTFIELD)) {
322 changes.add(ins);
323 }
324 }
325
326 return changes;
327
328 }
329
330 /** Get the list of double values produced by an instruction and not yet converted.
331 * @param instruction instruction producing the values
332 * @return list of double values produced
333 */
334 private List<TrackingValue> getProducedAndNotConvertedDoubleValues(final AbstractInsnNode instruction) {
335
336 final List<TrackingValue> values = new ArrayList<TrackingValue>();
337
338 // get the frame before instruction execution
339 final Frame<TrackingValue> before = frames.get(instruction);
340 final int beforeStackSize = before.getStackSize();
341 final int locals = before.getLocals();
342
343 // check the frames produced by this instruction
344 // (they correspond to the input frames of its successors)
345 final Set<AbstractInsnNode> set = successors.get(instruction);
346 if (set != null) {
347
348 // loop over the successors of this instruction
349 for (final AbstractInsnNode successor : set) {
350 final Frame<TrackingValue> produced = frames.get(successor);
351
352 // check the stack cells
353 for (int i = 0; i < produced.getStackSize(); ++i) {
354 final TrackingValue value = produced.getStack(i);
355 if (((i >= beforeStackSize) || (value != before.getStack(i))) &&
356 value.getType().equals(Type.DOUBLE_TYPE) &&
357 !converted.contains(value)) {
358 values.add(value);
359 }
360 }
361
362 // check the local variables
363 for (int i = 0; i < locals; ++i) {
364 final TrackingValue value = (TrackingValue) produced.getLocal(i);
365 if ((value != before.getLocal(i)) &&
366 value.getType().equals(Type.DOUBLE_TYPE) &&
367 !converted.contains(value)) {
368 values.add(value);
369 }
370 }
371 }
372 }
373
374 return values;
375
376 }
377
378 /** Get the replacement list for an instruction.
379 * @param insn instruction to replace
380 * @return replacement instructions list
381 * @exception DifferentiationException if some instruction cannot be handled
382 * or if no temporary variable can be reserved
383 */
384 private InsnList getReplacement(final AbstractInsnNode insn)
385 throws DifferentiationException {
386
387 // get the frame at the start of the instruction
388 final Frame<TrackingValue> frame = frames.get(insn);
389 final int size = frame.getStackSize();
390 final boolean stack1Converted = (size > 0) && converted.contains(frame.getStack(size - 2));
391 final boolean stack0Converted = (size > 1) && converted.contains(frame.getStack(size - 1));
392
393 switch(insn.getOpcode()) {
394 case Opcodes.DLOAD :
395 useLocal(((VarInsnNode) insn).var, 4);
396 return new DLoadTransformer().getReplacement(insn, this);
397 case Opcodes.DALOAD :
398 // TODO: add support for DALOAD differentiation
399 throw new RuntimeException("DALOAD not handled yet");
400 case Opcodes.DSTORE :
401 useLocal(((VarInsnNode) insn).var, 4);
402 return new DStoreTransformer().getReplacement(insn, this);
403 case Opcodes.DASTORE :
404 // TODO: add support for DASTORE differentiation
405 throw new RuntimeException("DASTORE not handled yet");
406 case Opcodes.DUP2 :
407 return new Dup2Transformer().getReplacement(insn, this);
408 case Opcodes.POP2 :
409 return new Pop2Transformer().getReplacement(insn, this);
410 case Opcodes.DUP2_X1 :
411 return new Dup2X1Transformer().getReplacement(insn, this);
412 case Opcodes.DUP2_X2 :
413 return new Dup2X2Transformer(stack0Converted, stack1Converted).getReplacement(insn, this);
414 case Opcodes.DADD :
415 return new DAddTransformer(stack0Converted, stack1Converted).getReplacement(insn, this);
416 case Opcodes.DSUB :
417 return new DSubTransformer(stack0Converted, stack1Converted).getReplacement(insn, this);
418 case Opcodes.DMUL :
419 return new DMulTransformer(stack0Converted, stack1Converted).getReplacement(insn, this);
420 case Opcodes.DDIV :
421 return new DDivTransformer(stack0Converted, stack1Converted).getReplacement(insn, this);
422 case Opcodes.DREM :
423 return new DRemTransformer(stack0Converted, stack1Converted).getReplacement(insn, this);
424 case Opcodes.DNEG :
425 return new DNegTransformer().getReplacement(insn, this);
426 case Opcodes.DCONST_0 :
427 case Opcodes.DCONST_1 :
428 case Opcodes.LDC :
429 case Opcodes.I2D :
430 case Opcodes.L2D :
431 case Opcodes.F2D :
432 return new WideningTransformer().getReplacement(insn, this);
433 case Opcodes.D2I :
434 case Opcodes.D2L :
435 case Opcodes.D2F :
436 return new NarrowingTransformer().getReplacement(insn, this);
437 case Opcodes.DCMPL :
438 case Opcodes.DCMPG :
439 return new DcmpTransformer(stack0Converted, stack1Converted).getReplacement(insn, this);
440 case Opcodes.DRETURN :
441 // TODO: the constructor parameter forced to true seems strange...
442 return new DReturnTransformer(true).getReplacement(insn, this);
443 case Opcodes.GETSTATIC :
444 // TODO: add support for GETSTATIC differentiation
445 throw new RuntimeException("GETSTATIC not handled yet");
446 case Opcodes.PUTSTATIC :
447 // TODO: add support for PUTSTATIC differentiation
448 throw new RuntimeException("PUTSTATIC not handled yet");
449 case Opcodes.GETFIELD :
450 return replaceGetField((FieldInsnNode) insn);
451 case Opcodes.PUTFIELD :
452 // TODO: add support for PUTFIELD differentiation
453 throw new RuntimeException("PUTFIELD not handled yet");
454 case Opcodes.INVOKEVIRTUAL :
455 // TODO: add support for INVOKEVIRTUAL differentiation
456 throw new RuntimeException("INVOKEVIRTUAL not handled yet");
457 case Opcodes.INVOKESPECIAL :
458 // TODO: add support for INVOKESPECIAL differentiation
459 throw new RuntimeException("INVOKESPECIAL not handled yet");
460 case Opcodes.INVOKESTATIC :
461 return new InvokeStaticTransformer(stack0Converted, stack1Converted).getReplacement(insn, this);
462 case Opcodes.INVOKEINTERFACE :
463 // TODO: add support for INVOKEINTERFACE differentiation
464 throw new RuntimeException("INVOKEINTERFACE not handled yet");
465 case Opcodes.INVOKEDYNAMIC :
466 // TODO: add support for INVOKEDYNAMIC differentiation
467 throw new RuntimeException("INVOKEDYNAMIC not handled yet");
468 case Opcodes.NEWARRAY :
469 // TODO: add support for NEWARRAY differentiation
470 throw new RuntimeException("NEWARRAY not handled yet");
471 case Opcodes.ANEWARRAY :
472 // TODO: add support for ANEWARRAY differentiation
473 throw new RuntimeException("ANEWARRAY not handled yet");
474 case Opcodes.MULTIANEWARRAY :
475 // TODO: add support for MULTIANEWARRAY differentiation
476 throw new RuntimeException("MULTIANEWARRAY not handled yet");
477 default:
478 throw new DifferentiationException(NablaMessages.UNABLE_TO_HANDLE_INSTRUCTION, insn.getOpcode());
479 }
480
481 }
482
483 /** Replace a GETFIELD instruction.
484 * @param fieldInsn field instruction
485 * @return replacement instructions list
486 * @exception DifferentiationException if instruction cannot be replaced
487 */
488 private InsnList replaceGetField(final FieldInsnNode fieldInsn) throws DifferentiationException {
489
490 final InsnList list = new InsnList();
491
492 // get the field as an object
493 list.add(new LdcInsnNode(fieldInsn.name));
494 list.add(new MethodInsnNode(Opcodes.INVOKESPECIAL, derivedName, "getPrimitiveField",
495 Type.getMethodDescriptor(Type.getType(Object.class),
496 Type.getType(String.class))));
497
498 // convert it to the expected type
499 final Type type = Type.getType(fieldInsn.desc);
500 final Type boxedType;
501 final String valueMethodName;
502 switch (type.getSort()) {
503 case Type.VOID:
504 throw new DifferentiationException(NablaMessages.CANNOT_GET_VOID_FIELD, fieldInsn.name);
505 case Type.BOOLEAN:
506 valueMethodName = "booleanValue";
507 boxedType = Type.getType(Boolean.class);
508 break;
509 case Type.CHAR:
510 valueMethodName = "charValue";
511 boxedType = Type.getType(Character.class);
512 break;
513 case Type.BYTE:
514 valueMethodName = "byteValue";
515 boxedType = Type.getType(Byte.class);
516 break;
517 case Type.SHORT:
518 valueMethodName = "shortValue";
519 boxedType = Type.getType(Short.class);
520 break;
521 case Type.INT:
522 valueMethodName = "intValue";
523 boxedType = Type.getType(Integer.class);
524 break;
525 case Type.FLOAT:
526 valueMethodName = "floatValue";
527 boxedType = Type.getType(Float.class);
528 break;
529 case Type.LONG:
530 valueMethodName = "longValue";
531 boxedType = Type.getType(Long.class);
532 break;
533 case Type.DOUBLE:
534 valueMethodName = "doubleValue";
535 boxedType = Type.getType(Double.class);
536 break;
537 default :
538 // do nothing for Type.ARRAY and Type.OBJECT
539 valueMethodName = null;
540 boxedType = null;
541
542 }
543 if (boxedType != null) {
544 list.add(new TypeInsnNode(Opcodes.CHECKCAST, boxedType.getInternalName()));
545 }
546 if (valueMethodName != null) {
547 list.add(new MethodInsnNode(Opcodes.INVOKEVIRTUAL, boxedType.getInternalName(),
548 valueMethodName,
549 Type.getMethodDescriptor(type, new Type[0])));
550 }
551
552 return list;
553
554 }
555
556 /** Test if a class is a math implementation class.
557 * @param name name of the class to test
558 * @return true if the named class is a math implementation class
559 */
560 public boolean isMathImplementationClass(final String name) {
561 return mathClasses.contains(name);
562 }
563
564 /** Create instructions to convert a double on top of stack to a {@link DerivativeStructure}.
565 * @return list of conversion instructions
566 */
567 public InsnList doubleToDerivativeStructureConversion() {
568
569 final InsnList list = new InsnList();
570
571 // operand stack initial state: d
572 list.add(new TypeInsnNode(Opcodes.NEW,
573 Type.getInternalName(DerivativeStructure.class))); // => d y_ds
574 list.add(new InsnNode(Opcodes.DUP_X2)); // => y_ds d y_ds
575 list.add(new InsnNode(Opcodes.DUP_X2)); // => y_ds y_ds d y_ds
576 list.add(new InsnNode(Opcodes.POP)); // => y_ds y_ds d
577 list.add(new VarInsnNode(Opcodes.ALOAD, getInputDSIndex())); // => y_ds y_ds d x_ds
578 list.add(new MethodInsnNode(Opcodes.INVOKEVIRTUAL,
579 Type.getInternalName(DerivativeStructure.class),
580 "getFreeParameters",
581 Type.getMethodDescriptor(Type.INT_TYPE))); // => y_ds y_ds d params
582 list.add(new VarInsnNode(Opcodes.ALOAD, 1)); // => y_ds y_ds d params x_ds
583 list.add(new MethodInsnNode(Opcodes.INVOKEVIRTUAL,
584 Type.getInternalName(DerivativeStructure.class),
585 "getOrder",
586 Type.getMethodDescriptor(Type.INT_TYPE))); // => y_ds y_ds d params order
587 list.add(new InsnNode(Opcodes.DUP2_X2)); // => y_ds y_ds params order d params order
588 list.add(new InsnNode(Opcodes.POP2)); // => y_ds y_ds params order d
589 list.add(new MethodInsnNode(Opcodes.INVOKESPECIAL,
590 Type.getInternalName(DerivativeStructure.class),
591 "<init>",
592 Type.getMethodDescriptor(Type.VOID_TYPE,
593 Type.INT_TYPE,
594 Type.INT_TYPE,
595 Type.DOUBLE_TYPE))); // => y_ds
596
597 return list;
598
599 }
600
601 /** Set a local variable as used by the modified code.
602 * @param index index of the variable
603 * @param size size of the variable (1 or 2 for standard variables,
604 * 4 for special expanded derivative structures)
605 * @exception DifferentiationException if the number of the
606 * temporary variable lies outside of the allowed range
607 */
608 public void useLocal(final int index, final int size)
609 throws DifferentiationException {
610 if ((index < 0) || ((index + size) > usedLocals.length)) {
611 throw new DifferentiationException(NablaMessages.INDEX_OF_LOCAL_VARIABLE_OUT_OF_RANGE,
612 size, index, 1, MAX_TEMP);
613 }
614 for (int i = index; i < index + size; ++i) {
615 usedLocals[i] = true;
616 }
617 }
618
619 /** Get index of a size 2 temporary variable.
620 * <p>Temporary variables can be used for very short duration
621 * storage of size 2 values (i.e one double, or one long or two
622 * integers). These variables are reused in many replacement
623 * instructions sequences, so their content may be overridden
624 * at any time: they should be considered to have a scope
625 * limited to one replacement sequence only. This means that
626 * one should <em>not</em> store a value in a variable in one
627 * replacement sequence and retrieve it later in another
628 * replacement sequence as it may have been overridden in
629 * between.</p>
630 * <p>At most 5 temporary variables may be used.</p>
631 * @param number number of the temporary variable (must be
632 * between 1 and the maximal number of available temporary
633 * variables)
634 * @return index of the variable within the local variables
635 * array
636 * @exception DifferentiationException if the number of the
637 * temporary variable lies outside of the allowed range
638 */
639 public int getTmp(final int number) throws DifferentiationException {
640 if ((number < 0) || (number > MAX_TEMP)) {
641 throw new DifferentiationException(NablaMessages.NUMBER_OF_TEMPORARY_VARIABLES_OUT_OF_RANGE,
642 number, 1, MAX_TEMP);
643 }
644 final int index = usedLocals.length - 2 * number;
645 useLocal(index, 2);
646 return index;
647 }
648
649 /** Shifted the index of a variable instruction.
650 * @param insn variable instruction
651 */
652 private void shiftVariable(final VarInsnNode insn) {
653 int shifted = 0;
654 for (int i = 0; i < insn.var; ++i) {
655 if (usedLocals[i]) {
656 ++shifted;
657 }
658 }
659 insn.var = shifted;
660 }
661
662 /** Compute the maximal number of used local variables.
663 * @return maximal number of used local variables
664 */
665 private int maxVariables() {
666 int max = 0;
667 for (final boolean isUsed : usedLocals) {
668 if (isUsed) {
669 ++max;
670 }
671 }
672 return max;
673 }
674
675 /** Analyzer preserving instructions successors information. */
676 private class FlowAnalyzer extends Analyzer<TrackingValue> {
677
678 /** Instructions of the method. */
679 private final InsnList instructions;
680
681 /** Simple constructor.
682 * @param interpreter associated interpreter
683 * @param instructions instructions of the method
684 */
685 public FlowAnalyzer(final Interpreter<TrackingValue> interpreter,
686 final InsnList instructions) {
687 super(interpreter);
688 this.instructions = instructions;
689 }
690
691 /** Store a new edge.
692 * @param insn current instruction
693 * @param successor successor instruction
694 */
695 protected void newControlFlowEdge(final int insn, final int successor) {
696 // store the successor information
697 final AbstractInsnNode node = instructions.get(insn);
698 Set<AbstractInsnNode> set = successors.get(node);
699 if (set == null) {
700 set = new HashSet<AbstractInsnNode>();
701 successors.put(node, set);
702 }
703 set.add(instructions.get(successor));
704 }
705
706 }
707
708 }