1/*
2 * ProGuard -- shrinking, optimization, obfuscation, and preverification
3 *             of Java bytecode.
4 *
5 * Copyright (c) 2002-2014 Eric Lafortune (eric@graphics.cornell.edu)
6 *
7 * This program is free software; you can redistribute it and/or modify it
8 * under the terms of the GNU General Public License as published by the Free
9 * Software Foundation; either version 2 of the License, or (at your option)
10 * any later version.
11 *
12 * This program is distributed in the hope that it will be useful, but WITHOUT
13 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
15 * more details.
16 *
17 * You should have received a copy of the GNU General Public License along
18 * with this program; if not, write to the Free Software Foundation, Inc.,
19 * 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
20 */
21package proguard.optimize.evaluation;
22
23import proguard.classfile.*;
24import proguard.classfile.attribute.*;
25import proguard.classfile.attribute.visitor.AttributeVisitor;
26import proguard.classfile.editor.*;
27import proguard.classfile.instruction.*;
28import proguard.classfile.instruction.visitor.InstructionVisitor;
29import proguard.classfile.util.*;
30import proguard.classfile.visitor.ClassPrinter;
31import proguard.evaluation.TracedVariables;
32import proguard.evaluation.value.*;
33import proguard.optimize.info.SideEffectInstructionChecker;
34
35import java.util.Arrays;
36
37/**
38 * This AttributeVisitor simplifies the code attributes that it visits, based
39 * on partial evaluation.
40 *
41 * @author Eric Lafortune
42 */
43public class EvaluationSimplifier
44extends      SimplifiedVisitor
45implements   AttributeVisitor,
46             InstructionVisitor
47{
48    private static final int  POS_ZERO_FLOAT_BITS  = Float.floatToIntBits(0.0f);
49    private static final long POS_ZERO_DOUBLE_BITS = Double.doubleToLongBits(0.0);
50
51    //*
52    private static final boolean DEBUG = false;
53    /*/
54    private static       boolean DEBUG = System.getProperty("es") != null;
55    //*/
56
57    private final InstructionVisitor extraInstructionVisitor;
58
59    private final PartialEvaluator             partialEvaluator;
60    private final SideEffectInstructionChecker sideEffectInstructionChecker = new SideEffectInstructionChecker(true, true);
61    private final CodeAttributeEditor          codeAttributeEditor          = new CodeAttributeEditor(false, true);
62
63
64    /**
65     * Creates a new EvaluationSimplifier.
66     */
67    public EvaluationSimplifier()
68    {
69        this(new PartialEvaluator(), null);
70    }
71
72
73    /**
74     * Creates a new EvaluationSimplifier.
75     * @param partialEvaluator        the partial evaluator that will
76     *                                execute the code and provide
77     *                                information about the results.
78     * @param extraInstructionVisitor an optional extra visitor for all
79     *                                simplified instructions.
80     */
81    public EvaluationSimplifier(PartialEvaluator   partialEvaluator,
82                                InstructionVisitor extraInstructionVisitor)
83    {
84        this.partialEvaluator        = partialEvaluator;
85        this.extraInstructionVisitor = extraInstructionVisitor;
86    }
87
88
89    // Implementations for AttributeVisitor.
90
91    public void visitAnyAttribute(Clazz clazz, Attribute attribute) {}
92
93
94    public void visitCodeAttribute(Clazz clazz, Method method, CodeAttribute codeAttribute)
95    {
96//        DEBUG =
97//            clazz.getName().equals("abc/Def") &&
98//            method.getName(clazz).equals("abc");
99
100        // TODO: Remove this when the evaluation simplifier has stabilized.
101        // Catch any unexpected exceptions from the actual visiting method.
102        try
103        {
104            // Process the code.
105            visitCodeAttribute0(clazz, method, codeAttribute);
106        }
107        catch (RuntimeException ex)
108        {
109            System.err.println("Unexpected error while simplifying instructions after partial evaluation:");
110            System.err.println("  Class       = ["+clazz.getName()+"]");
111            System.err.println("  Method      = ["+method.getName(clazz)+method.getDescriptor(clazz)+"]");
112            System.err.println("  Exception   = ["+ex.getClass().getName()+"] ("+ex.getMessage()+")");
113            System.err.println("Not optimizing this method");
114
115            if (DEBUG)
116            {
117                method.accept(clazz, new ClassPrinter());
118
119                throw ex;
120            }
121        }
122    }
123
124
125    public void visitCodeAttribute0(Clazz clazz, Method method, CodeAttribute codeAttribute)
126    {
127        if (DEBUG)
128        {
129            System.out.println();
130            System.out.println("EvaluationSimplifier ["+clazz.getName()+"."+method.getName(clazz)+method.getDescriptor(clazz)+"]");
131        }
132
133        // Evaluate the method.
134        partialEvaluator.visitCodeAttribute(clazz, method, codeAttribute);
135
136        int codeLength = codeAttribute.u4codeLength;
137
138        // Reset the code changes.
139        codeAttributeEditor.reset(codeLength);
140
141        // Replace any instructions that can be simplified.
142        for (int offset = 0; offset < codeLength; offset++)
143        {
144            if (partialEvaluator.isTraced(offset))
145            {
146                Instruction instruction = InstructionFactory.create(codeAttribute.code,
147                                                                    offset);
148
149                instruction.accept(clazz, method, codeAttribute, offset, this);
150            }
151        }
152
153        // Apply all accumulated changes to the code.
154        codeAttributeEditor.visitCodeAttribute(clazz, method, codeAttribute);
155    }
156
157
158    // Implementations for InstructionVisitor.
159
160    public void visitSimpleInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, SimpleInstruction simpleInstruction)
161    {
162        switch (simpleInstruction.opcode)
163        {
164            case InstructionConstants.OP_IALOAD:
165            case InstructionConstants.OP_BALOAD:
166            case InstructionConstants.OP_CALOAD:
167            case InstructionConstants.OP_SALOAD:
168            case InstructionConstants.OP_IADD:
169            case InstructionConstants.OP_ISUB:
170            case InstructionConstants.OP_IMUL:
171            case InstructionConstants.OP_IDIV:
172            case InstructionConstants.OP_IREM:
173            case InstructionConstants.OP_INEG:
174            case InstructionConstants.OP_ISHL:
175            case InstructionConstants.OP_ISHR:
176            case InstructionConstants.OP_IUSHR:
177            case InstructionConstants.OP_IAND:
178            case InstructionConstants.OP_IOR:
179            case InstructionConstants.OP_IXOR:
180            case InstructionConstants.OP_L2I:
181            case InstructionConstants.OP_F2I:
182            case InstructionConstants.OP_D2I:
183            case InstructionConstants.OP_I2B:
184            case InstructionConstants.OP_I2C:
185            case InstructionConstants.OP_I2S:
186            case InstructionConstants.OP_ARRAYLENGTH:
187                replaceIntegerPushInstruction(clazz, offset, simpleInstruction);
188                break;
189
190            case InstructionConstants.OP_LALOAD:
191            case InstructionConstants.OP_LADD:
192            case InstructionConstants.OP_LSUB:
193            case InstructionConstants.OP_LMUL:
194            case InstructionConstants.OP_LDIV:
195            case InstructionConstants.OP_LREM:
196            case InstructionConstants.OP_LNEG:
197            case InstructionConstants.OP_LSHL:
198            case InstructionConstants.OP_LSHR:
199            case InstructionConstants.OP_LUSHR:
200            case InstructionConstants.OP_LAND:
201            case InstructionConstants.OP_LOR:
202            case InstructionConstants.OP_LXOR:
203            case InstructionConstants.OP_I2L:
204            case InstructionConstants.OP_F2L:
205            case InstructionConstants.OP_D2L:
206                replaceLongPushInstruction(clazz, offset, simpleInstruction);
207                break;
208
209            case InstructionConstants.OP_FALOAD:
210            case InstructionConstants.OP_FADD:
211            case InstructionConstants.OP_FSUB:
212            case InstructionConstants.OP_FMUL:
213            case InstructionConstants.OP_FDIV:
214            case InstructionConstants.OP_FREM:
215            case InstructionConstants.OP_FNEG:
216            case InstructionConstants.OP_I2F:
217            case InstructionConstants.OP_L2F:
218            case InstructionConstants.OP_D2F:
219                replaceFloatPushInstruction(clazz, offset, simpleInstruction);
220                break;
221
222            case InstructionConstants.OP_DALOAD:
223            case InstructionConstants.OP_DADD:
224            case InstructionConstants.OP_DSUB:
225            case InstructionConstants.OP_DMUL:
226            case InstructionConstants.OP_DDIV:
227            case InstructionConstants.OP_DREM:
228            case InstructionConstants.OP_DNEG:
229            case InstructionConstants.OP_I2D:
230            case InstructionConstants.OP_L2D:
231            case InstructionConstants.OP_F2D:
232                replaceDoublePushInstruction(clazz, offset, simpleInstruction);
233                break;
234
235            case InstructionConstants.OP_AALOAD:
236                replaceReferencePushInstruction(clazz, offset, simpleInstruction);
237                break;
238        }
239    }
240
241
242    public void visitVariableInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, VariableInstruction variableInstruction)
243    {
244        int variableIndex = variableInstruction.variableIndex;
245
246        switch (variableInstruction.opcode)
247        {
248            case InstructionConstants.OP_ILOAD:
249            case InstructionConstants.OP_ILOAD_0:
250            case InstructionConstants.OP_ILOAD_1:
251            case InstructionConstants.OP_ILOAD_2:
252            case InstructionConstants.OP_ILOAD_3:
253                replaceIntegerPushInstruction(clazz, offset, variableInstruction, variableIndex);
254                break;
255
256            case InstructionConstants.OP_LLOAD:
257            case InstructionConstants.OP_LLOAD_0:
258            case InstructionConstants.OP_LLOAD_1:
259            case InstructionConstants.OP_LLOAD_2:
260            case InstructionConstants.OP_LLOAD_3:
261                replaceLongPushInstruction(clazz, offset, variableInstruction, variableIndex);
262                break;
263
264            case InstructionConstants.OP_FLOAD:
265            case InstructionConstants.OP_FLOAD_0:
266            case InstructionConstants.OP_FLOAD_1:
267            case InstructionConstants.OP_FLOAD_2:
268            case InstructionConstants.OP_FLOAD_3:
269                replaceFloatPushInstruction(clazz, offset, variableInstruction, variableIndex);
270                break;
271
272            case InstructionConstants.OP_DLOAD:
273            case InstructionConstants.OP_DLOAD_0:
274            case InstructionConstants.OP_DLOAD_1:
275            case InstructionConstants.OP_DLOAD_2:
276            case InstructionConstants.OP_DLOAD_3:
277                replaceDoublePushInstruction(clazz, offset, variableInstruction, variableIndex);
278                break;
279
280            case InstructionConstants.OP_ALOAD:
281            case InstructionConstants.OP_ALOAD_0:
282            case InstructionConstants.OP_ALOAD_1:
283            case InstructionConstants.OP_ALOAD_2:
284            case InstructionConstants.OP_ALOAD_3:
285                replaceReferencePushInstruction(clazz, offset, variableInstruction);
286                break;
287
288            case InstructionConstants.OP_ASTORE:
289            case InstructionConstants.OP_ASTORE_0:
290            case InstructionConstants.OP_ASTORE_1:
291            case InstructionConstants.OP_ASTORE_2:
292            case InstructionConstants.OP_ASTORE_3:
293                deleteReferencePopInstruction(clazz, offset, variableInstruction);
294                break;
295
296            case InstructionConstants.OP_RET:
297                replaceBranchInstruction(clazz, offset, variableInstruction);
298                break;
299        }
300    }
301
302
303    public void visitConstantInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, ConstantInstruction constantInstruction)
304    {
305        switch (constantInstruction.opcode)
306        {
307            case InstructionConstants.OP_GETSTATIC:
308            case InstructionConstants.OP_GETFIELD:
309                replaceAnyPushInstruction(clazz, offset, constantInstruction);
310                break;
311
312            case InstructionConstants.OP_INVOKEVIRTUAL:
313            case InstructionConstants.OP_INVOKESPECIAL:
314            case InstructionConstants.OP_INVOKESTATIC:
315            case InstructionConstants.OP_INVOKEINTERFACE:
316                if (constantInstruction.stackPushCount(clazz) > 0 &&
317                    !sideEffectInstructionChecker.hasSideEffects(clazz,
318                                                                 method,
319                                                                 codeAttribute,
320                                                                 offset,
321                                                                 constantInstruction))
322                {
323                    replaceAnyPushInstruction(clazz, offset, constantInstruction);
324                }
325
326                break;
327
328            case InstructionConstants.OP_CHECKCAST:
329                replaceReferencePushInstruction(clazz, offset, constantInstruction);
330                break;
331        }
332    }
333
334
335    public void visitBranchInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, BranchInstruction branchInstruction)
336    {
337        switch (branchInstruction.opcode)
338        {
339            case InstructionConstants.OP_GOTO:
340            case InstructionConstants.OP_GOTO_W:
341                // Don't replace unconditional branches.
342                break;
343
344            case InstructionConstants.OP_JSR:
345            case InstructionConstants.OP_JSR_W:
346                replaceJsrInstruction(clazz, offset, branchInstruction);
347                break;
348
349            default:
350                replaceBranchInstruction(clazz, offset, branchInstruction);
351                break;
352        }
353    }
354
355
356    public void visitTableSwitchInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, TableSwitchInstruction tableSwitchInstruction)
357    {
358        // First try to simplify it to a simple branch.
359        replaceBranchInstruction(clazz, offset, tableSwitchInstruction);
360
361        // Otherwise try to simplify simple enum switches.
362        if (!codeAttributeEditor.isModified(offset))
363        {
364            replaceSimpleEnumSwitchInstruction(clazz,
365                                               codeAttribute,
366                                               offset,
367                                               tableSwitchInstruction);
368
369            // Otherwise make sure all branch targets are valid.
370            if (!codeAttributeEditor.isModified(offset))
371            {
372                cleanUpSwitchInstruction(clazz, offset, tableSwitchInstruction);
373
374                trimSwitchInstruction(clazz, offset, tableSwitchInstruction);
375            }
376        }
377    }
378
379
380    public void visitLookUpSwitchInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, LookUpSwitchInstruction lookUpSwitchInstruction)
381    {
382        // First try to simplify it to a simple branch.
383        replaceBranchInstruction(clazz, offset, lookUpSwitchInstruction);
384
385        // Otherwise try to simplify simple enum switches.
386        if (!codeAttributeEditor.isModified(offset))
387        {
388            replaceSimpleEnumSwitchInstruction(clazz,
389                                               codeAttribute,
390                                               offset,
391                                               lookUpSwitchInstruction);
392
393            // Otherwise make sure all branch targets are valid.
394            if (!codeAttributeEditor.isModified(offset))
395            {
396                cleanUpSwitchInstruction(clazz, offset, lookUpSwitchInstruction);
397
398                trimSwitchInstruction(clazz, offset, lookUpSwitchInstruction);
399            }
400        }
401    }
402
403
404    // Small utility methods.
405
406    /**
407     * Replaces the push instruction at the given offset by a simpler push
408     * instruction, if possible.
409     */
410    private void replaceAnyPushInstruction(Clazz       clazz,
411                                           int         offset,
412                                           Instruction instruction)
413    {
414        Value pushedValue = partialEvaluator.getStackAfter(offset).getTop(0);
415        if (pushedValue.isParticular())
416        {
417            switch (pushedValue.computationalType())
418            {
419                case Value.TYPE_INTEGER:
420                    replaceIntegerPushInstruction(clazz, offset, instruction);
421                    break;
422                case Value.TYPE_LONG:
423                    replaceLongPushInstruction(clazz, offset, instruction);
424                    break;
425                case Value.TYPE_FLOAT:
426                    replaceFloatPushInstruction(clazz, offset, instruction);
427                    break;
428                case Value.TYPE_DOUBLE:
429                    replaceDoublePushInstruction(clazz, offset, instruction);
430                    break;
431                case Value.TYPE_REFERENCE:
432                    replaceReferencePushInstruction(clazz, offset, instruction);
433                    break;
434            }
435        }
436    }
437
438
439    /**
440     * Replaces the integer pushing instruction at the given offset by a simpler
441     * push instruction, if possible.
442     */
443    private void replaceIntegerPushInstruction(Clazz       clazz,
444                                               int         offset,
445                                               Instruction instruction)
446    {
447        replaceIntegerPushInstruction(clazz,
448                                      offset,
449                                      instruction,
450                                      partialEvaluator.getVariablesBefore(offset).size());
451    }
452
453
454    /**
455     * Replaces the integer pushing instruction at the given offset by a simpler
456     * push instruction, if possible.
457     */
458    private void replaceIntegerPushInstruction(Clazz       clazz,
459                                               int         offset,
460                                               Instruction instruction,
461                                               int         maxVariableIndex)
462    {
463        Value pushedValue = partialEvaluator.getStackAfter(offset).getTop(0);
464        if (pushedValue.isParticular())
465        {
466            // Push a constant instead.
467            int value = pushedValue.integerValue().value();
468            if ((short)value == value)
469            {
470                replaceConstantPushInstruction(clazz,
471                                               offset,
472                                               instruction,
473                                               InstructionConstants.OP_SIPUSH,
474                                               value);
475            }
476            else
477            {
478                ConstantPoolEditor constantPoolEditor =
479                    new ConstantPoolEditor((ProgramClass)clazz);
480
481                Instruction replacementInstruction =
482                    new ConstantInstruction(InstructionConstants.OP_LDC,
483                                            constantPoolEditor.addIntegerConstant(value));
484
485                replaceInstruction(clazz, offset, instruction, replacementInstruction);
486            }
487        }
488        else if (pushedValue.isSpecific())
489        {
490            // Load an equivalent lower-numbered variable instead, if any.
491            TracedVariables variables = partialEvaluator.getVariablesBefore(offset);
492            for (int variableIndex = 0; variableIndex < maxVariableIndex; variableIndex++)
493            {
494                if (pushedValue.equals(variables.load(variableIndex)))
495                {
496                    replaceVariablePushInstruction(clazz,
497                                                   offset,
498                                                   instruction,
499                                                   InstructionConstants.OP_ILOAD,
500                                                   variableIndex);
501                    break;
502                }
503            }
504        }
505    }
506
507
508    /**
509     * Replaces the long pushing instruction at the given offset by a simpler
510     * push instruction, if possible.
511     */
512    private void replaceLongPushInstruction(Clazz       clazz,
513                                            int         offset,
514                                            Instruction instruction)
515    {
516        replaceLongPushInstruction(clazz,
517                                   offset,
518                                   instruction,
519                                   partialEvaluator.getVariablesBefore(offset).size());
520    }
521
522
523    /**
524     * Replaces the long pushing instruction at the given offset by a simpler
525     * push instruction, if possible.
526     */
527    private void replaceLongPushInstruction(Clazz       clazz,
528                                            int         offset,
529                                            Instruction instruction,
530                                            int         maxVariableIndex)
531    {
532        Value pushedValue = partialEvaluator.getStackAfter(offset).getTop(0);
533        if (pushedValue.isParticular())
534        {
535            // Push a constant instead.
536            long value = pushedValue.longValue().value();
537            if (value == 0L ||
538                value == 1L)
539            {
540                replaceConstantPushInstruction(clazz,
541                                       offset,
542                                       instruction,
543                                       InstructionConstants.OP_LCONST_0,
544                                       (int)value);
545            }
546            else
547            {
548                ConstantPoolEditor constantPoolEditor =
549                    new ConstantPoolEditor((ProgramClass)clazz);
550
551                Instruction replacementInstruction =
552                    new ConstantInstruction(InstructionConstants.OP_LDC2_W,
553                                            constantPoolEditor.addLongConstant(value));
554
555                replaceInstruction(clazz, offset, instruction, replacementInstruction);
556            }
557        }
558        else if (pushedValue.isSpecific())
559        {
560            // Load an equivalent lower-numbered variable instead, if any.
561            TracedVariables variables = partialEvaluator.getVariablesBefore(offset);
562            for (int variableIndex = 0; variableIndex < maxVariableIndex; variableIndex++)
563            {
564                // Note that we have to check the second part as well.
565                if (pushedValue.equals(variables.load(variableIndex)) &&
566                    variables.load(variableIndex + 1) != null         &&
567                    variables.load(variableIndex + 1).computationalType() == Value.TYPE_TOP)
568                {
569                    replaceVariablePushInstruction(clazz,
570                                                   offset,
571                                                   instruction,
572                                                   InstructionConstants.OP_LLOAD,
573                                                   variableIndex);
574                }
575            }
576        }
577    }
578
579
580    /**
581     * Replaces the float pushing instruction at the given offset by a simpler
582     * push instruction, if possible.
583     */
584    private void replaceFloatPushInstruction(Clazz       clazz,
585                                             int         offset,
586                                             Instruction instruction)
587    {
588        replaceFloatPushInstruction(clazz,
589                                    offset,
590                                    instruction,
591                                    partialEvaluator.getVariablesBefore(offset).size());
592    }
593
594
595    /**
596     * Replaces the float pushing instruction at the given offset by a simpler
597     * push instruction, if possible.
598     */
599    private void replaceFloatPushInstruction(Clazz       clazz,
600                                             int         offset,
601                                             Instruction instruction,
602                                             int         maxVariableIndex)
603    {
604        Value pushedValue = partialEvaluator.getStackAfter(offset).getTop(0);
605        if (pushedValue.isParticular())
606        {
607            // Push a constant instead.
608            // Make sure to distinguish between +0.0 and -0.0.
609            float value = pushedValue.floatValue().value();
610            if (value == 0.0f && Float.floatToIntBits(value) == POS_ZERO_FLOAT_BITS ||
611                value == 1.0f ||
612                value == 2.0f)
613            {
614                replaceConstantPushInstruction(clazz,
615                                               offset,
616                                               instruction,
617                                               InstructionConstants.OP_FCONST_0,
618                                               (int)value);
619            }
620            else
621            {
622                ConstantPoolEditor constantPoolEditor =
623                    new ConstantPoolEditor((ProgramClass)clazz);
624
625                Instruction replacementInstruction =
626                    new ConstantInstruction(InstructionConstants.OP_LDC,
627                                            constantPoolEditor.addFloatConstant(value));
628
629                replaceInstruction(clazz, offset, instruction, replacementInstruction);
630            }
631        }
632        else if (pushedValue.isSpecific())
633        {
634            // Load an equivalent lower-numbered variable instead, if any.
635            TracedVariables variables = partialEvaluator.getVariablesBefore(offset);
636            for (int variableIndex = 0; variableIndex < maxVariableIndex; variableIndex++)
637            {
638                if (pushedValue.equals(variables.load(variableIndex)))
639                {
640                    replaceVariablePushInstruction(clazz,
641                                                   offset,
642                                                   instruction,
643                                                   InstructionConstants.OP_FLOAD,
644                                                   variableIndex);
645                }
646            }
647        }
648    }
649
650
651    /**
652     * Replaces the double pushing instruction at the given offset by a simpler
653     * push instruction, if possible.
654     */
655    private void replaceDoublePushInstruction(Clazz       clazz,
656                                              int         offset,
657                                              Instruction instruction)
658    {
659        replaceDoublePushInstruction(clazz,
660                                     offset,
661                                     instruction,
662                                     partialEvaluator.getVariablesBefore(offset).size());
663    }
664
665
666    /**
667     * Replaces the double pushing instruction at the given offset by a simpler
668     * push instruction, if possible.
669     */
670    private void replaceDoublePushInstruction(Clazz       clazz,
671                                              int         offset,
672                                              Instruction instruction,
673                                              int         maxVariableIndex)
674    {
675        Value pushedValue = partialEvaluator.getStackAfter(offset).getTop(0);
676        if (pushedValue.isParticular())
677        {
678            // Push a constant instead.
679            // Make sure to distinguish between +0.0 and -0.0.
680            double value = pushedValue.doubleValue().value();
681            if (value == 0.0 && Double.doubleToLongBits(value) == POS_ZERO_DOUBLE_BITS ||
682                value == 1.0)
683            {
684                replaceConstantPushInstruction(clazz,
685                                               offset,
686                                               instruction,
687                                               InstructionConstants.OP_DCONST_0,
688                                               (int)value);
689            }
690            else
691            {
692                ConstantPoolEditor constantPoolEditor =
693                    new ConstantPoolEditor((ProgramClass)clazz);
694
695                Instruction replacementInstruction =
696                    new ConstantInstruction(InstructionConstants.OP_LDC2_W,
697                                            constantPoolEditor.addDoubleConstant(value));
698
699                replaceInstruction(clazz, offset, instruction, replacementInstruction);
700            }
701        }
702        else if (pushedValue.isSpecific())
703        {
704            // Load an equivalent lower-numbered variable instead, if any.
705            TracedVariables variables = partialEvaluator.getVariablesBefore(offset);
706            for (int variableIndex = 0; variableIndex < maxVariableIndex; variableIndex++)
707            {
708                // Note that we have to check the second part as well.
709                if (pushedValue.equals(variables.load(variableIndex)) &&
710                    variables.load(variableIndex + 1) != null         &&
711                    variables.load(variableIndex + 1).computationalType() == Value.TYPE_TOP)
712                {
713                    replaceVariablePushInstruction(clazz,
714                                                   offset,
715                                                   instruction,
716                                                   InstructionConstants.OP_DLOAD,
717                                                   variableIndex);
718                }
719            }
720        }
721    }
722
723
724    /**
725     * Replaces the reference pushing instruction at the given offset by a
726     * simpler push instruction, if possible.
727     */
728    private void replaceReferencePushInstruction(Clazz       clazz,
729                                                 int         offset,
730                                                 Instruction instruction)
731    {
732        Value pushedValue = partialEvaluator.getStackAfter(offset).getTop(0);
733        if (pushedValue.isParticular())
734        {
735            // A reference value can only be specific if it is null.
736            replaceConstantPushInstruction(clazz,
737                                           offset,
738                                           instruction,
739                                           InstructionConstants.OP_ACONST_NULL,
740                                           0);
741        }
742    }
743
744
745    /**
746     * Replaces the instruction at a given offset by a given push instruction
747     * of a constant.
748     */
749    private void replaceConstantPushInstruction(Clazz       clazz,
750                                                int         offset,
751                                                Instruction instruction,
752                                                byte        replacementOpcode,
753                                                int         value)
754    {
755        Instruction replacementInstruction =
756            new SimpleInstruction(replacementOpcode, value);
757
758        replaceInstruction(clazz, offset, instruction, replacementInstruction);
759    }
760
761
762    /**
763     * Replaces the instruction at a given offset by a given push instruction
764     * of a variable.
765     */
766    private void replaceVariablePushInstruction(Clazz       clazz,
767                                                int         offset,
768                                                Instruction instruction,
769                                                byte        replacementOpcode,
770                                                int         variableIndex)
771    {
772        Instruction replacementInstruction =
773            new VariableInstruction(replacementOpcode, variableIndex);
774
775        replaceInstruction(clazz, offset, instruction, replacementInstruction);
776    }
777
778
779    /**
780     * Replaces the given 'jsr' instruction by a simpler branch instruction,
781     * if it jumps to a subroutine that doesn't return or a subroutine that
782     * is only called from one place.
783     */
784    private void replaceJsrInstruction(Clazz             clazz,
785                                       int               offset,
786                                       BranchInstruction branchInstruction)
787    {
788        // Is the subroutine ever returning?
789        int subroutineStart = offset + branchInstruction.branchOffset;
790        if (!partialEvaluator.isSubroutineReturning(subroutineStart) ||
791            partialEvaluator.branchOrigins(subroutineStart).instructionOffsetCount() == 1)
792        {
793            // All 'jsr' instructions to this subroutine can be replaced
794            // by unconditional branch instructions.
795            replaceBranchInstruction(clazz, offset, branchInstruction);
796        }
797        else if (!partialEvaluator.isTraced(offset + branchInstruction.length(offset)))
798        {
799            // We have to make sure the instruction after this 'jsr'
800            // instruction is valid, even if it is never reached.
801            replaceByInfiniteLoop(clazz, offset + branchInstruction.length(offset), branchInstruction);
802        }
803    }
804
805
806    /**
807     * Deletes the reference popping instruction at the given offset, if
808     * it is at the start of a subroutine that doesn't return or a subroutine
809     * that is only called from one place.
810     */
811    private void deleteReferencePopInstruction(Clazz       clazz,
812                                               int         offset,
813                                               Instruction instruction)
814    {
815        if (partialEvaluator.isSubroutineStart(offset) &&
816            (!partialEvaluator.isSubroutineReturning(offset) ||
817             partialEvaluator.branchOrigins(offset).instructionOffsetCount() == 1))
818        {
819            if (DEBUG) System.out.println("  Deleting store of subroutine return address "+instruction.toString(offset));
820
821            // A reference value can only be specific if it is null.
822            codeAttributeEditor.deleteInstruction(offset);
823        }
824    }
825
826
827    /**
828     * Deletes the given branch instruction, or replaces it by a simpler branch
829     * instruction, if possible.
830     */
831    private void replaceBranchInstruction(Clazz       clazz,
832                                          int         offset,
833                                          Instruction instruction)
834    {
835        InstructionOffsetValue branchTargets = partialEvaluator.branchTargets(offset);
836
837        // Is there exactly one branch target (not from a goto or jsr)?
838        if (branchTargets != null &&
839            branchTargets.instructionOffsetCount() == 1)
840        {
841            // Is it branching to the next instruction?
842            int branchOffset = branchTargets.instructionOffset(0) - offset;
843            if (branchOffset == instruction.length(offset))
844            {
845                if (DEBUG) System.out.println("  Ignoring zero branch instruction at ["+offset+"]");
846            }
847            else
848            {
849                // Replace the branch instruction by a simple branch instruction.
850                Instruction replacementInstruction =
851                    new BranchInstruction(InstructionConstants.OP_GOTO,
852                                          branchOffset);
853
854                replaceInstruction(clazz, offset, instruction, replacementInstruction);
855            }
856        }
857    }
858
859
860    /**
861     * Replaces the given table switch instruction, if it is based on the value
862     * of a fixed array. This is typical for switches on simple enums.
863     */
864    private void replaceSimpleEnumSwitchInstruction(Clazz                  clazz,
865                                                    CodeAttribute          codeAttribute,
866                                                    int                    offset,
867                                                    TableSwitchInstruction tableSwitchInstruction)
868    {
869        // Check if the switch instruction is consuming a single value loaded
870        // from a fully specified array.
871        InstructionOffsetValue producerOffsets =
872            partialEvaluator.getStackBefore(offset).getTopProducerValue(0).instructionOffsetValue();
873
874        if (producerOffsets.instructionOffsetCount() == 1)
875        {
876            int producerOffset = producerOffsets.instructionOffset(0);
877
878            if (codeAttribute.code[producerOffset] == InstructionConstants.OP_IALOAD &&
879                !codeAttributeEditor.isModified(producerOffset))
880            {
881                ReferenceValue referenceValue =
882                    partialEvaluator.getStackBefore(producerOffset).getTop(1).referenceValue();
883
884                if (referenceValue.isParticular())
885                {
886                    // Simplify the entire construct.
887                    replaceSimpleEnumSwitchInstruction(clazz,
888                                                       codeAttribute,
889                                                       producerOffset,
890                                                       offset,
891                                                       tableSwitchInstruction,
892                                                       referenceValue);
893                }
894            }
895        }
896    }
897
898
899    /**
900     * Replaces the given table switch instruction that is based on a value of
901     * the given fixed array.
902     */
903    private void replaceSimpleEnumSwitchInstruction(Clazz                  clazz,
904                                                    CodeAttribute          codeAttribute,
905                                                    int                    loadOffset,
906                                                    int                    switchOffset,
907                                                    TableSwitchInstruction tableSwitchInstruction,
908                                                    ReferenceValue         mappingValue)
909    {
910        ValueFactory valueFactory = new ParticularValueFactory();
911
912        // Transform the jump offsets.
913        int[] jumpOffsets    = tableSwitchInstruction.jumpOffsets;
914        int[] newJumpOffsets = new int[mappingValue.arrayLength(valueFactory).value()];
915
916        for (int index = 0; index < newJumpOffsets.length; index++)
917        {
918            int switchCase =
919                mappingValue.integerArrayLoad(valueFactory.createIntegerValue(
920                    index),
921                                              valueFactory).value();
922
923            newJumpOffsets[index] =
924                switchCase >= tableSwitchInstruction.lowCase &&
925                switchCase <= tableSwitchInstruction.highCase ?
926                    jumpOffsets[switchCase - tableSwitchInstruction.lowCase] :
927                    tableSwitchInstruction.defaultOffset;
928        }
929
930        // Update the instruction.
931        tableSwitchInstruction.lowCase     = 0;
932        tableSwitchInstruction.highCase    = newJumpOffsets.length - 1;
933        tableSwitchInstruction.jumpOffsets = newJumpOffsets;
934
935        // Replace the original one with the new version.
936        replaceSimpleEnumSwitchInstruction(clazz,
937                                           loadOffset,
938                                           switchOffset,
939                                           tableSwitchInstruction);
940
941        cleanUpSwitchInstruction(clazz, switchOffset, tableSwitchInstruction);
942
943        trimSwitchInstruction(clazz, switchOffset, tableSwitchInstruction);
944    }
945
946
947    /**
948     * Replaces the given look up switch instruction, if it is based on the
949     * value of a fixed array. This is typical for switches on simple enums.
950     */
951    private void replaceSimpleEnumSwitchInstruction(Clazz                   clazz,
952                                                    CodeAttribute           codeAttribute,
953                                                    int                     offset,
954                                                    LookUpSwitchInstruction lookupSwitchInstruction)
955    {
956        // Check if the switch instruction is consuming a single value loaded
957        // from a fully specified array.
958        InstructionOffsetValue producerOffsets =
959            partialEvaluator.getStackBefore(offset).getTopProducerValue(0).instructionOffsetValue();
960
961        if (producerOffsets.instructionOffsetCount() == 1)
962        {
963            int producerOffset = producerOffsets.instructionOffset(0);
964
965            if (codeAttribute.code[producerOffset] == InstructionConstants.OP_IALOAD &&
966                !codeAttributeEditor.isModified(producerOffset))
967            {
968                ReferenceValue referenceValue =
969                    partialEvaluator.getStackBefore(producerOffset).getTop(1).referenceValue();
970
971                if (referenceValue.isParticular())
972                {
973                    // Simplify the entire construct.
974                    replaceSimpleEnumSwitchInstruction(clazz,
975                                                       codeAttribute,
976                                                       producerOffset,
977                                                       offset,
978                                                       lookupSwitchInstruction,
979                                                       referenceValue);
980                }
981            }
982        }
983    }
984
985
986    /**
987     * Replaces the given look up switch instruction that is based on a value of
988     * the given fixed array. This is typical for switches on simple enums.
989     */
990    private void replaceSimpleEnumSwitchInstruction(Clazz                   clazz,
991                                                    CodeAttribute           codeAttribute,
992                                                    int                     loadOffset,
993                                                    int                     switchOffset,
994                                                    LookUpSwitchInstruction lookupSwitchInstruction,
995                                                    ReferenceValue          mappingValue)
996    {
997        ValueFactory valueFactory = new ParticularValueFactory();
998
999        // Transform the jump offsets.
1000        int[] cases          = lookupSwitchInstruction.cases;
1001        int[] jumpOffsets    = lookupSwitchInstruction.jumpOffsets;
1002        int[] newJumpOffsets = new int[mappingValue.arrayLength(valueFactory).value()];
1003
1004        for (int index = 0; index < newJumpOffsets.length; index++)
1005        {
1006            int switchCase =
1007                mappingValue.integerArrayLoad(valueFactory.createIntegerValue(index),
1008                                              valueFactory).value();
1009
1010            int caseIndex = Arrays.binarySearch(cases, switchCase);
1011
1012            newJumpOffsets[index] = caseIndex >= 0 ?
1013                jumpOffsets[caseIndex] :
1014                lookupSwitchInstruction.defaultOffset;
1015        }
1016
1017        // Replace the original lookup switch with a table switch.
1018        TableSwitchInstruction replacementSwitchInstruction =
1019            new TableSwitchInstruction(InstructionConstants.OP_TABLESWITCH,
1020                                       lookupSwitchInstruction.defaultOffset,
1021                                       0,
1022                                       newJumpOffsets.length - 1,
1023                                       newJumpOffsets);
1024
1025        replaceSimpleEnumSwitchInstruction(clazz,
1026                                           loadOffset,
1027                                           switchOffset,
1028                                           replacementSwitchInstruction);
1029
1030        cleanUpSwitchInstruction(clazz, switchOffset, replacementSwitchInstruction);
1031
1032        trimSwitchInstruction(clazz, switchOffset, replacementSwitchInstruction);
1033    }
1034
1035
1036    /**
1037     * Makes sure all branch targets of the given switch instruction are valid.
1038     */
1039    private void cleanUpSwitchInstruction(Clazz             clazz,
1040                                          int               offset,
1041                                          SwitchInstruction switchInstruction)
1042    {
1043        // Get the actual branch targets.
1044        InstructionOffsetValue branchTargets = partialEvaluator.branchTargets(offset);
1045
1046        // Get an offset that can serve as a valid default offset.
1047        int defaultOffset =
1048            branchTargets.instructionOffset(branchTargets.instructionOffsetCount()-1) -
1049            offset;
1050
1051        Instruction replacementInstruction = null;
1052
1053        // Check the jump offsets.
1054        int[] jumpOffsets = switchInstruction.jumpOffsets;
1055        for (int index = 0; index < jumpOffsets.length; index++)
1056        {
1057            if (!branchTargets.contains(offset + jumpOffsets[index]))
1058            {
1059                // Replace the unused offset.
1060                jumpOffsets[index] = defaultOffset;
1061
1062                // Remember to replace the instruction.
1063                replacementInstruction = switchInstruction;
1064            }
1065        }
1066
1067        // Check the default offset.
1068        if (!branchTargets.contains(offset + switchInstruction.defaultOffset))
1069        {
1070            // Replace the unused offset.
1071            switchInstruction.defaultOffset = defaultOffset;
1072
1073            // Remember to replace the instruction.
1074            replacementInstruction = switchInstruction;
1075        }
1076
1077        if (replacementInstruction != null)
1078        {
1079            replaceInstruction(clazz, offset, switchInstruction, replacementInstruction);
1080        }
1081    }
1082
1083
1084    /**
1085     * Trims redundant offsets from the given switch instruction.
1086     */
1087    private void trimSwitchInstruction(Clazz                  clazz,
1088                                       int                    offset,
1089                                       TableSwitchInstruction tableSwitchInstruction)
1090    {
1091        // Get an offset that can serve as a valid default offset.
1092        int   defaultOffset = tableSwitchInstruction.defaultOffset;
1093        int[] jumpOffsets   = tableSwitchInstruction.jumpOffsets;
1094        int   length        = jumpOffsets.length;
1095
1096        // Find the lowest index with a non-default jump offset.
1097        int lowIndex = 0;
1098        while (lowIndex < length &&
1099               jumpOffsets[lowIndex] == defaultOffset)
1100        {
1101            lowIndex++;
1102        }
1103
1104        // Find the highest index with a non-default jump offset.
1105        int highIndex = length - 1;
1106        while (highIndex >= 0 &&
1107               jumpOffsets[highIndex] == defaultOffset)
1108        {
1109            highIndex--;
1110        }
1111
1112        // Can we use a shorter array?
1113        int newLength = highIndex - lowIndex + 1;
1114        if (newLength < length)
1115        {
1116            if (newLength <= 0)
1117            {
1118                // Replace the switch instruction by a simple branch instruction.
1119                Instruction replacementInstruction =
1120                    new BranchInstruction(InstructionConstants.OP_GOTO,
1121                                          defaultOffset);
1122
1123                replaceInstruction(clazz, offset, tableSwitchInstruction,
1124                                   replacementInstruction);
1125            }
1126            else
1127            {
1128                // Trim the array.
1129                int[] newJumpOffsets = new int[newLength];
1130
1131                System.arraycopy(jumpOffsets, lowIndex, newJumpOffsets, 0, newLength);
1132
1133                tableSwitchInstruction.jumpOffsets = newJumpOffsets;
1134                tableSwitchInstruction.lowCase    += lowIndex;
1135                tableSwitchInstruction.highCase   -= length - newLength - lowIndex;
1136
1137                replaceInstruction(clazz, offset, tableSwitchInstruction,
1138                                   tableSwitchInstruction);
1139            }
1140        }
1141    }
1142
1143
1144    /**
1145     * Trims redundant offsets from the given switch instruction.
1146     */
1147    private void trimSwitchInstruction(Clazz                   clazz,
1148                                       int                     offset,
1149                                       LookUpSwitchInstruction lookUpSwitchInstruction)
1150    {
1151        // Get an offset that can serve as a valid default offset.
1152        int   defaultOffset = lookUpSwitchInstruction.defaultOffset;
1153        int[] jumpOffsets   = lookUpSwitchInstruction.jumpOffsets;
1154        int   length        = jumpOffsets.length;
1155        int   newLength     = length;
1156
1157        // Count the default jump offsets.
1158        for (int index = 0; index < length; index++)
1159        {
1160            if (jumpOffsets[index] == defaultOffset)
1161            {
1162                newLength--;
1163            }
1164        }
1165
1166        // Can we use shorter arrays?
1167        if (newLength < length)
1168        {
1169            if (newLength <= 0)
1170            {
1171                // Replace the switch instruction by a simple branch instruction.
1172                Instruction replacementInstruction =
1173                    new BranchInstruction(InstructionConstants.OP_GOTO,
1174                                          defaultOffset);
1175
1176                replaceInstruction(clazz, offset, lookUpSwitchInstruction,
1177                                   replacementInstruction);
1178            }
1179            else
1180            {
1181                // Remove redundant entries from the arrays.
1182                int[] cases          = lookUpSwitchInstruction.cases;
1183                int[] newJumpOffsets = new int[newLength];
1184                int[] newCases       = new int[newLength];
1185
1186                int newIndex = 0;
1187
1188                for (int index = 0; index < length; index++)
1189                {
1190                    if (jumpOffsets[index] != defaultOffset)
1191                    {
1192                        newJumpOffsets[newIndex] = jumpOffsets[index];
1193                        newCases[newIndex++]     = cases[index];
1194                    }
1195                }
1196
1197                lookUpSwitchInstruction.jumpOffsets = newJumpOffsets;
1198                lookUpSwitchInstruction.cases       = newCases;
1199
1200                replaceInstruction(clazz, offset, lookUpSwitchInstruction,
1201                                   lookUpSwitchInstruction);
1202            }
1203        }
1204    }
1205
1206
1207    /**
1208     * Replaces the given instruction by an infinite loop.
1209     */
1210    private void replaceByInfiniteLoop(Clazz       clazz,
1211                                       int         offset,
1212                                       Instruction instruction)
1213    {
1214        // Replace the instruction by an infinite loop.
1215        Instruction replacementInstruction =
1216            new BranchInstruction(InstructionConstants.OP_GOTO, 0);
1217
1218        if (DEBUG) System.out.println("  Replacing unreachable instruction by infinite loop "+replacementInstruction.toString(offset));
1219
1220        codeAttributeEditor.replaceInstruction(offset, replacementInstruction);
1221
1222        // Visit the instruction, if required.
1223        if (extraInstructionVisitor != null)
1224        {
1225            // Note: we're not passing the right arguments for now, knowing that
1226            // they aren't used anyway.
1227            instruction.accept(clazz,
1228                               null,
1229                               null,
1230                               offset,
1231                               extraInstructionVisitor);
1232        }
1233    }
1234
1235
1236    /**
1237     * Replaces the instruction at a given offset by a given push instruction.
1238     */
1239    private void replaceInstruction(Clazz       clazz,
1240                                    int         offset,
1241                                    Instruction instruction,
1242                                    Instruction replacementInstruction)
1243    {
1244        // Pop unneeded stack entries if necessary.
1245        int popCount =
1246            instruction.stackPopCount(clazz) -
1247            replacementInstruction.stackPopCount(clazz);
1248
1249        insertPopInstructions(offset, popCount);
1250
1251        if (DEBUG) System.out.println("  Replacing instruction "+instruction.toString(offset)+" -> "+replacementInstruction.toString()+(popCount == 0 ? "" : " ("+popCount+" pops)"));
1252
1253        codeAttributeEditor.replaceInstruction(offset, replacementInstruction);
1254
1255        // Visit the instruction, if required.
1256        if (extraInstructionVisitor != null)
1257        {
1258            // Note: we're not passing the right arguments for now, knowing that
1259            // they aren't used anyway.
1260            instruction.accept(clazz, null, null, offset, extraInstructionVisitor);
1261        }
1262    }
1263
1264
1265    /**
1266     * Pops the given number of stack entries before the instruction at the
1267     * given offset.
1268     */
1269    private void insertPopInstructions(int offset, int popCount)
1270    {
1271        switch (popCount)
1272        {
1273            case 0:
1274            {
1275                break;
1276            }
1277            case 1:
1278            {
1279                // Insert a single pop instruction.
1280                Instruction popInstruction =
1281                    new SimpleInstruction(InstructionConstants.OP_POP);
1282
1283                codeAttributeEditor.insertBeforeInstruction(offset,
1284                                                            popInstruction);
1285                break;
1286            }
1287            case 2:
1288            {
1289                // Insert a single pop2 instruction.
1290                Instruction popInstruction =
1291                    new SimpleInstruction(InstructionConstants.OP_POP2);
1292
1293                codeAttributeEditor.insertBeforeInstruction(offset,
1294                                                            popInstruction);
1295                break;
1296            }
1297            default:
1298            {
1299                // Insert the specified number of pop instructions.
1300                Instruction[] popInstructions =
1301                    new Instruction[popCount / 2 + popCount % 2];
1302
1303                Instruction popInstruction =
1304                    new SimpleInstruction(InstructionConstants.OP_POP2);
1305
1306                for (int index = 0; index < popCount / 2; index++)
1307                {
1308                      popInstructions[index] = popInstruction;
1309                }
1310
1311                if (popCount % 2 == 1)
1312                {
1313                    popInstruction =
1314                        new SimpleInstruction(InstructionConstants.OP_POP);
1315
1316                    popInstructions[popCount / 2] = popInstruction;
1317                }
1318
1319                codeAttributeEditor.insertBeforeInstruction(offset,
1320                                                            popInstructions);
1321                break;
1322            }
1323        }
1324    }
1325
1326
1327    /**
1328     * Replaces the simple enum switch instructions at a given offsets by a
1329     * given replacement instruction.
1330     */
1331    private void replaceSimpleEnumSwitchInstruction(Clazz             clazz,
1332                                                    int               loadOffset,
1333                                                    int               switchOffset,
1334                                                    SwitchInstruction replacementSwitchInstruction)
1335    {
1336        if (DEBUG) System.out.println("  Replacing switch instruction at ["+switchOffset+"] -> ["+loadOffset+"] swap + pop, "+replacementSwitchInstruction.toString(switchOffset)+")");
1337
1338        // Remove the array load instruction.
1339        codeAttributeEditor.replaceInstruction(loadOffset, new Instruction[]
1340            {
1341                new SimpleInstruction(InstructionConstants.OP_SWAP),
1342                new SimpleInstruction(InstructionConstants.OP_POP),
1343            });
1344
1345        // Replace the switch instruction.
1346        codeAttributeEditor.replaceInstruction(switchOffset, replacementSwitchInstruction);
1347
1348        // Visit the instruction, if required.
1349        if (extraInstructionVisitor != null)
1350        {
1351            // Note: we're not passing the right arguments for now, knowing that
1352            // they aren't used anyway.
1353            replacementSwitchInstruction.accept(clazz,
1354                                                null,
1355                                                null,
1356                                                switchOffset,
1357                                                extraInstructionVisitor);
1358        }
1359    }
1360}
1361