1/*
2 * ProGuard -- shrinking, optimization, obfuscation, and preverification
3 *             of Java bytecode.
4 *
5 * Copyright (c) 2002-2013 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.*;
31import proguard.evaluation.*;
32import proguard.evaluation.value.*;
33import proguard.optimize.info.*;
34
35/**
36 * This AttributeVisitor simplifies the code attributes that it visits, based
37 * on partial evaluation.
38 *
39 * @author Eric Lafortune
40 */
41public class EvaluationSimplifier
42extends      SimplifiedVisitor
43implements   AttributeVisitor,
44             InstructionVisitor
45{
46    private static final int  POS_ZERO_FLOAT_BITS  = Float.floatToIntBits(0.0f);
47    private static final long POS_ZERO_DOUBLE_BITS = Double.doubleToLongBits(0.0);
48
49    //*
50    private static final boolean DEBUG = false;
51    /*/
52    private static       boolean DEBUG = true;
53    //*/
54
55    private final InstructionVisitor extraInstructionVisitor;
56
57    private final PartialEvaluator             partialEvaluator;
58    private final SideEffectInstructionChecker sideEffectInstructionChecker = new SideEffectInstructionChecker(true, true);
59    private final CodeAttributeEditor          codeAttributeEditor          = new CodeAttributeEditor(false, true);
60
61
62    /**
63     * Creates a new EvaluationSimplifier.
64     */
65    public EvaluationSimplifier()
66    {
67        this(new PartialEvaluator(), null);
68    }
69
70
71    /**
72     * Creates a new EvaluationSimplifier.
73     * @param partialEvaluator        the partial evaluator that will
74     *                                execute the code and provide
75     *                                information about the results.
76     * @param extraInstructionVisitor an optional extra visitor for all
77     *                                simplified instructions.
78     */
79    public EvaluationSimplifier(PartialEvaluator   partialEvaluator,
80                                InstructionVisitor extraInstructionVisitor)
81    {
82        this.partialEvaluator        = partialEvaluator;
83        this.extraInstructionVisitor = extraInstructionVisitor;
84    }
85
86
87    // Implementations for AttributeVisitor.
88
89    public void visitAnyAttribute(Clazz clazz, Attribute attribute) {}
90
91
92    public void visitCodeAttribute(Clazz clazz, Method method, CodeAttribute codeAttribute)
93    {
94//        DEBUG =
95//            clazz.getName().equals("abc/Def") &&
96//            method.getName(clazz).equals("abc");
97
98        // TODO: Remove this when the evaluation simplifier has stabilized.
99        // Catch any unexpected exceptions from the actual visiting method.
100        try
101        {
102            // Process the code.
103            visitCodeAttribute0(clazz, method, codeAttribute);
104        }
105        catch (RuntimeException ex)
106        {
107            System.err.println("Unexpected error while simplifying instructions after partial evaluation:");
108            System.err.println("  Class       = ["+clazz.getName()+"]");
109            System.err.println("  Method      = ["+method.getName(clazz)+method.getDescriptor(clazz)+"]");
110            System.err.println("  Exception   = ["+ex.getClass().getName()+"] ("+ex.getMessage()+")");
111            System.err.println("Not optimizing this method");
112
113            if (DEBUG)
114            {
115                method.accept(clazz, new ClassPrinter());
116
117                throw ex;
118            }
119        }
120    }
121
122
123    public void visitCodeAttribute0(Clazz clazz, Method method, CodeAttribute codeAttribute)
124    {
125        if (DEBUG)
126        {
127            System.out.println();
128            System.out.println("Class "+ClassUtil.externalClassName(clazz.getName()));
129            System.out.println("Method "+ClassUtil.externalFullMethodDescription(clazz.getName(),
130                                                                                 0,
131                                                                                 method.getName(clazz),
132                                                                                 method.getDescriptor(clazz)));
133        }
134
135        // Evaluate the method.
136        partialEvaluator.visitCodeAttribute(clazz, method, codeAttribute);
137
138        int codeLength = codeAttribute.u4codeLength;
139
140        // Reset the code changes.
141        codeAttributeEditor.reset(codeLength);
142
143        // Replace any instructions that can be simplified.
144        for (int offset = 0; offset < codeLength; offset++)
145        {
146            if (partialEvaluator.isTraced(offset))
147            {
148                Instruction instruction = InstructionFactory.create(codeAttribute.code,
149                                                                    offset);
150
151                instruction.accept(clazz, method, codeAttribute, offset, this);
152            }
153        }
154
155        // Apply all accumulated changes to the code.
156        codeAttributeEditor.visitCodeAttribute(clazz, method, codeAttribute);
157    }
158
159
160    // Implementations for InstructionVisitor.
161
162    public void visitSimpleInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, SimpleInstruction simpleInstruction)
163    {
164        switch (simpleInstruction.opcode)
165        {
166            case InstructionConstants.OP_IALOAD:
167            case InstructionConstants.OP_BALOAD:
168            case InstructionConstants.OP_CALOAD:
169            case InstructionConstants.OP_SALOAD:
170            case InstructionConstants.OP_IADD:
171            case InstructionConstants.OP_ISUB:
172            case InstructionConstants.OP_IMUL:
173            case InstructionConstants.OP_IDIV:
174            case InstructionConstants.OP_IREM:
175            case InstructionConstants.OP_INEG:
176            case InstructionConstants.OP_ISHL:
177            case InstructionConstants.OP_ISHR:
178            case InstructionConstants.OP_IUSHR:
179            case InstructionConstants.OP_IAND:
180            case InstructionConstants.OP_IOR:
181            case InstructionConstants.OP_IXOR:
182            case InstructionConstants.OP_L2I:
183            case InstructionConstants.OP_F2I:
184            case InstructionConstants.OP_D2I:
185            case InstructionConstants.OP_I2B:
186            case InstructionConstants.OP_I2C:
187            case InstructionConstants.OP_I2S:
188                replaceIntegerPushInstruction(clazz, offset, simpleInstruction);
189                break;
190
191            case InstructionConstants.OP_LALOAD:
192            case InstructionConstants.OP_LADD:
193            case InstructionConstants.OP_LSUB:
194            case InstructionConstants.OP_LMUL:
195            case InstructionConstants.OP_LDIV:
196            case InstructionConstants.OP_LREM:
197            case InstructionConstants.OP_LNEG:
198            case InstructionConstants.OP_LSHL:
199            case InstructionConstants.OP_LSHR:
200            case InstructionConstants.OP_LUSHR:
201            case InstructionConstants.OP_LAND:
202            case InstructionConstants.OP_LOR:
203            case InstructionConstants.OP_LXOR:
204            case InstructionConstants.OP_I2L:
205            case InstructionConstants.OP_F2L:
206            case InstructionConstants.OP_D2L:
207                replaceLongPushInstruction(clazz, offset, simpleInstruction);
208                break;
209
210            case InstructionConstants.OP_FALOAD:
211            case InstructionConstants.OP_FADD:
212            case InstructionConstants.OP_FSUB:
213            case InstructionConstants.OP_FMUL:
214            case InstructionConstants.OP_FDIV:
215            case InstructionConstants.OP_FREM:
216            case InstructionConstants.OP_FNEG:
217            case InstructionConstants.OP_I2F:
218            case InstructionConstants.OP_L2F:
219            case InstructionConstants.OP_D2F:
220                replaceFloatPushInstruction(clazz, offset, simpleInstruction);
221                break;
222
223            case InstructionConstants.OP_DALOAD:
224            case InstructionConstants.OP_DADD:
225            case InstructionConstants.OP_DSUB:
226            case InstructionConstants.OP_DMUL:
227            case InstructionConstants.OP_DDIV:
228            case InstructionConstants.OP_DREM:
229            case InstructionConstants.OP_DNEG:
230            case InstructionConstants.OP_I2D:
231            case InstructionConstants.OP_L2D:
232            case InstructionConstants.OP_F2D:
233                replaceDoublePushInstruction(clazz, offset, simpleInstruction);
234                break;
235
236            case InstructionConstants.OP_AALOAD:
237                replaceReferencePushInstruction(clazz, offset, simpleInstruction);
238                break;
239        }
240    }
241
242
243    public void visitVariableInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, VariableInstruction variableInstruction)
244    {
245        int variableIndex = variableInstruction.variableIndex;
246
247        switch (variableInstruction.opcode)
248        {
249            case InstructionConstants.OP_ILOAD:
250            case InstructionConstants.OP_ILOAD_0:
251            case InstructionConstants.OP_ILOAD_1:
252            case InstructionConstants.OP_ILOAD_2:
253            case InstructionConstants.OP_ILOAD_3:
254                replaceIntegerPushInstruction(clazz, offset, variableInstruction, variableIndex);
255                break;
256
257            case InstructionConstants.OP_LLOAD:
258            case InstructionConstants.OP_LLOAD_0:
259            case InstructionConstants.OP_LLOAD_1:
260            case InstructionConstants.OP_LLOAD_2:
261            case InstructionConstants.OP_LLOAD_3:
262                replaceLongPushInstruction(clazz, offset, variableInstruction, variableIndex);
263                break;
264
265            case InstructionConstants.OP_FLOAD:
266            case InstructionConstants.OP_FLOAD_0:
267            case InstructionConstants.OP_FLOAD_1:
268            case InstructionConstants.OP_FLOAD_2:
269            case InstructionConstants.OP_FLOAD_3:
270                replaceFloatPushInstruction(clazz, offset, variableInstruction, variableIndex);
271                break;
272
273            case InstructionConstants.OP_DLOAD:
274            case InstructionConstants.OP_DLOAD_0:
275            case InstructionConstants.OP_DLOAD_1:
276            case InstructionConstants.OP_DLOAD_2:
277            case InstructionConstants.OP_DLOAD_3:
278                replaceDoublePushInstruction(clazz, offset, variableInstruction, variableIndex);
279                break;
280
281            case InstructionConstants.OP_ALOAD:
282            case InstructionConstants.OP_ALOAD_0:
283            case InstructionConstants.OP_ALOAD_1:
284            case InstructionConstants.OP_ALOAD_2:
285            case InstructionConstants.OP_ALOAD_3:
286                replaceReferencePushInstruction(clazz, offset, variableInstruction);
287                break;
288
289            case InstructionConstants.OP_ASTORE:
290            case InstructionConstants.OP_ASTORE_0:
291            case InstructionConstants.OP_ASTORE_1:
292            case InstructionConstants.OP_ASTORE_2:
293            case InstructionConstants.OP_ASTORE_3:
294                deleteReferencePopInstruction(clazz, offset, variableInstruction);
295                break;
296
297            case InstructionConstants.OP_RET:
298                replaceBranchInstruction(clazz, offset, variableInstruction);
299                break;
300        }
301    }
302
303
304    public void visitConstantInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, ConstantInstruction constantInstruction)
305    {
306        switch (constantInstruction.opcode)
307        {
308            case InstructionConstants.OP_GETSTATIC:
309            case InstructionConstants.OP_GETFIELD:
310                replaceAnyPushInstruction(clazz, offset, constantInstruction);
311                break;
312
313            case InstructionConstants.OP_INVOKEVIRTUAL:
314            case InstructionConstants.OP_INVOKESPECIAL:
315            case InstructionConstants.OP_INVOKESTATIC:
316            case InstructionConstants.OP_INVOKEINTERFACE:
317                if (constantInstruction.stackPushCount(clazz) > 0 &&
318                    !sideEffectInstructionChecker.hasSideEffects(clazz,
319                                                                 method,
320                                                                 codeAttribute,
321                                                                 offset,
322                                                                 constantInstruction))
323                {
324                    replaceAnyPushInstruction(clazz, offset, constantInstruction);
325                }
326
327                break;
328
329            case InstructionConstants.OP_CHECKCAST:
330                replaceReferencePushInstruction(clazz, offset, constantInstruction);
331                break;
332        }
333    }
334
335
336    public void visitBranchInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, BranchInstruction branchInstruction)
337    {
338        switch (branchInstruction.opcode)
339        {
340            case InstructionConstants.OP_GOTO:
341            case InstructionConstants.OP_GOTO_W:
342                // Don't replace unconditional branches.
343                break;
344
345            case InstructionConstants.OP_JSR:
346            case InstructionConstants.OP_JSR_W:
347                replaceJsrInstruction(clazz, offset, branchInstruction);
348                break;
349
350            default:
351                replaceBranchInstruction(clazz, offset, branchInstruction);
352                break;
353        }
354    }
355
356
357    public void visitAnySwitchInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, SwitchInstruction switchInstruction)
358    {
359        // First try to simplify it to a simple branch.
360        replaceBranchInstruction(clazz, offset, switchInstruction);
361
362        // Otherwise make sure all branch targets are valid.
363        if (!codeAttributeEditor.isModified(offset))
364        {
365            replaceSwitchInstruction(clazz, offset, switchInstruction);
366        }
367    }
368
369
370    // Small utility methods.
371
372    /**
373     * Replaces the push instruction at the given offset by a simpler push
374     * instruction, if possible.
375     */
376    private void replaceAnyPushInstruction(Clazz       clazz,
377                                           int         offset,
378                                           Instruction instruction)
379    {
380        Value pushedValue = partialEvaluator.getStackAfter(offset).getTop(0);
381        if (pushedValue.isParticular())
382        {
383            switch (pushedValue.computationalType())
384            {
385                case Value.TYPE_INTEGER:
386                    replaceIntegerPushInstruction(clazz, offset, instruction);
387                    break;
388                case Value.TYPE_LONG:
389                    replaceLongPushInstruction(clazz, offset, instruction);
390                    break;
391                case Value.TYPE_FLOAT:
392                    replaceFloatPushInstruction(clazz, offset, instruction);
393                    break;
394                case Value.TYPE_DOUBLE:
395                    replaceDoublePushInstruction(clazz, offset, instruction);
396                    break;
397                case Value.TYPE_REFERENCE:
398                    replaceReferencePushInstruction(clazz, offset, instruction);
399                    break;
400            }
401        }
402    }
403
404
405    /**
406     * Replaces the integer pushing instruction at the given offset by a simpler
407     * push instruction, if possible.
408     */
409    private void replaceIntegerPushInstruction(Clazz       clazz,
410                                               int         offset,
411                                               Instruction instruction)
412    {
413        replaceIntegerPushInstruction(clazz,
414                                      offset,
415                                      instruction,
416                                      partialEvaluator.getVariablesBefore(offset).size());
417    }
418
419
420    /**
421     * Replaces the integer pushing instruction at the given offset by a simpler
422     * push instruction, if possible.
423     */
424    private void replaceIntegerPushInstruction(Clazz       clazz,
425                                               int         offset,
426                                               Instruction instruction,
427                                               int         maxVariableIndex)
428    {
429        Value pushedValue = partialEvaluator.getStackAfter(offset).getTop(0);
430        if (pushedValue.isParticular())
431        {
432            // Push a constant instead.
433            int value = pushedValue.integerValue().value();
434            if ((short)value == value)
435            {
436                replaceConstantPushInstruction(clazz,
437                                               offset,
438                                               instruction,
439                                               InstructionConstants.OP_SIPUSH,
440                                               value);
441            }
442            else
443            {
444                ConstantPoolEditor constantPoolEditor =
445                    new ConstantPoolEditor((ProgramClass)clazz);
446
447                Instruction replacementInstruction =
448                    new ConstantInstruction(InstructionConstants.OP_LDC,
449                                            constantPoolEditor.addIntegerConstant(value));
450
451                replaceInstruction(clazz, offset, instruction, replacementInstruction);
452            }
453        }
454        else if (pushedValue.isSpecific())
455        {
456            // Load an equivalent lower-numbered variable instead, if any.
457            TracedVariables variables = partialEvaluator.getVariablesBefore(offset);
458            for (int variableIndex = 0; variableIndex < maxVariableIndex; variableIndex++)
459            {
460                if (pushedValue.equals(variables.load(variableIndex)))
461                {
462                    replaceVariablePushInstruction(clazz,
463                                                   offset,
464                                                   instruction,
465                                                   InstructionConstants.OP_ILOAD,
466                                                   variableIndex);
467                    break;
468                }
469            }
470        }
471    }
472
473
474    /**
475     * Replaces the long pushing instruction at the given offset by a simpler
476     * push instruction, if possible.
477     */
478    private void replaceLongPushInstruction(Clazz       clazz,
479                                            int         offset,
480                                            Instruction instruction)
481    {
482        replaceLongPushInstruction(clazz,
483                                   offset,
484                                   instruction,
485                                   partialEvaluator.getVariablesBefore(offset).size());
486    }
487
488
489    /**
490     * Replaces the long pushing instruction at the given offset by a simpler
491     * push instruction, if possible.
492     */
493    private void replaceLongPushInstruction(Clazz       clazz,
494                                            int         offset,
495                                            Instruction instruction,
496                                            int         maxVariableIndex)
497    {
498        Value pushedValue = partialEvaluator.getStackAfter(offset).getTop(0);
499        if (pushedValue.isParticular())
500        {
501            // Push a constant instead.
502            long value = pushedValue.longValue().value();
503            if (value == 0L ||
504                value == 1L)
505            {
506                replaceConstantPushInstruction(clazz,
507                                       offset,
508                                       instruction,
509                                       InstructionConstants.OP_LCONST_0,
510                                       (int)value);
511            }
512            else
513            {
514                ConstantPoolEditor constantPoolEditor =
515                    new ConstantPoolEditor((ProgramClass)clazz);
516
517                Instruction replacementInstruction =
518                    new ConstantInstruction(InstructionConstants.OP_LDC2_W,
519                                            constantPoolEditor.addLongConstant(value));
520
521                replaceInstruction(clazz, offset, instruction, replacementInstruction);
522            }
523        }
524        else if (pushedValue.isSpecific())
525        {
526            // Load an equivalent lower-numbered variable instead, if any.
527            TracedVariables variables = partialEvaluator.getVariablesBefore(offset);
528            for (int variableIndex = 0; variableIndex < maxVariableIndex; variableIndex++)
529            {
530                // Note that we have to check the second part as well.
531                if (pushedValue.equals(variables.load(variableIndex)) &&
532                    variables.load(variableIndex + 1) != null         &&
533                    variables.load(variableIndex + 1).computationalType() == Value.TYPE_TOP)
534                {
535                    replaceVariablePushInstruction(clazz,
536                                                   offset,
537                                                   instruction,
538                                                   InstructionConstants.OP_LLOAD,
539                                                   variableIndex);
540                }
541            }
542        }
543    }
544
545
546    /**
547     * Replaces the float pushing instruction at the given offset by a simpler
548     * push instruction, if possible.
549     */
550    private void replaceFloatPushInstruction(Clazz       clazz,
551                                             int         offset,
552                                             Instruction instruction)
553    {
554        replaceFloatPushInstruction(clazz,
555                                    offset,
556                                    instruction,
557                                    partialEvaluator.getVariablesBefore(offset).size());
558    }
559
560
561    /**
562     * Replaces the float pushing instruction at the given offset by a simpler
563     * push instruction, if possible.
564     */
565    private void replaceFloatPushInstruction(Clazz       clazz,
566                                             int         offset,
567                                             Instruction instruction,
568                                             int         maxVariableIndex)
569    {
570        Value pushedValue = partialEvaluator.getStackAfter(offset).getTop(0);
571        if (pushedValue.isParticular())
572        {
573            // Push a constant instead.
574            // Make sure to distinguish between +0.0 and -0.0.
575            float value = pushedValue.floatValue().value();
576            if (value == 0.0f && Float.floatToIntBits(value) == POS_ZERO_FLOAT_BITS ||
577                value == 1.0f ||
578                value == 2.0f)
579            {
580                replaceConstantPushInstruction(clazz,
581                                               offset,
582                                               instruction,
583                                               InstructionConstants.OP_FCONST_0,
584                                               (int)value);
585            }
586            else
587            {
588                ConstantPoolEditor constantPoolEditor =
589                    new ConstantPoolEditor((ProgramClass)clazz);
590
591                Instruction replacementInstruction =
592                    new ConstantInstruction(InstructionConstants.OP_LDC,
593                                            constantPoolEditor.addFloatConstant(value));
594
595                replaceInstruction(clazz, offset, instruction, replacementInstruction);
596            }
597        }
598        else if (pushedValue.isSpecific())
599        {
600            // Load an equivalent lower-numbered variable instead, if any.
601            TracedVariables variables = partialEvaluator.getVariablesBefore(offset);
602            for (int variableIndex = 0; variableIndex < maxVariableIndex; variableIndex++)
603            {
604                if (pushedValue.equals(variables.load(variableIndex)))
605                {
606                    replaceVariablePushInstruction(clazz,
607                                                   offset,
608                                                   instruction,
609                                                   InstructionConstants.OP_FLOAD,
610                                                   variableIndex);
611                }
612            }
613        }
614    }
615
616
617    /**
618     * Replaces the double pushing instruction at the given offset by a simpler
619     * push instruction, if possible.
620     */
621    private void replaceDoublePushInstruction(Clazz       clazz,
622                                              int         offset,
623                                              Instruction instruction)
624    {
625        replaceDoublePushInstruction(clazz,
626                                     offset,
627                                     instruction,
628                                     partialEvaluator.getVariablesBefore(offset).size());
629    }
630
631
632    /**
633     * Replaces the double pushing instruction at the given offset by a simpler
634     * push instruction, if possible.
635     */
636    private void replaceDoublePushInstruction(Clazz       clazz,
637                                              int         offset,
638                                              Instruction instruction,
639                                              int         maxVariableIndex)
640    {
641        Value pushedValue = partialEvaluator.getStackAfter(offset).getTop(0);
642        if (pushedValue.isParticular())
643        {
644            // Push a constant instead.
645            // Make sure to distinguish between +0.0 and -0.0.
646            double value = pushedValue.doubleValue().value();
647            if (value == 0.0 && Double.doubleToLongBits(value) == POS_ZERO_DOUBLE_BITS ||
648                value == 1.0)
649            {
650                replaceConstantPushInstruction(clazz,
651                                               offset,
652                                               instruction,
653                                               InstructionConstants.OP_DCONST_0,
654                                               (int)value);
655            }
656            else
657            {
658                ConstantPoolEditor constantPoolEditor =
659                    new ConstantPoolEditor((ProgramClass)clazz);
660
661                Instruction replacementInstruction =
662                    new ConstantInstruction(InstructionConstants.OP_LDC2_W,
663                                            constantPoolEditor.addDoubleConstant(value));
664
665                replaceInstruction(clazz, offset, instruction, replacementInstruction);
666            }
667        }
668        else if (pushedValue.isSpecific())
669        {
670            // Load an equivalent lower-numbered variable instead, if any.
671            TracedVariables variables = partialEvaluator.getVariablesBefore(offset);
672            for (int variableIndex = 0; variableIndex < maxVariableIndex; variableIndex++)
673            {
674                // Note that we have to check the second part as well.
675                if (pushedValue.equals(variables.load(variableIndex)) &&
676                    variables.load(variableIndex + 1) != null         &&
677                    variables.load(variableIndex + 1).computationalType() == Value.TYPE_TOP)
678                {
679                    replaceVariablePushInstruction(clazz,
680                                                   offset,
681                                                   instruction,
682                                                   InstructionConstants.OP_DLOAD,
683                                                   variableIndex);
684                }
685            }
686        }
687    }
688
689
690    /**
691     * Replaces the reference pushing instruction at the given offset by a
692     * simpler push instruction, if possible.
693     */
694    private void replaceReferencePushInstruction(Clazz       clazz,
695                                                 int         offset,
696                                                 Instruction instruction)
697    {
698        Value pushedValue = partialEvaluator.getStackAfter(offset).getTop(0);
699        if (pushedValue.isParticular())
700        {
701            // A reference value can only be specific if it is null.
702            replaceConstantPushInstruction(clazz,
703                                           offset,
704                                           instruction,
705                                           InstructionConstants.OP_ACONST_NULL,
706                                           0);
707        }
708    }
709
710
711    /**
712     * Replaces the instruction at a given offset by a given push instruction
713     * of a constant.
714     */
715    private void replaceConstantPushInstruction(Clazz       clazz,
716                                                int         offset,
717                                                Instruction instruction,
718                                                byte        replacementOpcode,
719                                                int         value)
720    {
721        Instruction replacementInstruction =
722            new SimpleInstruction(replacementOpcode, value);
723
724        replaceInstruction(clazz, offset, instruction, replacementInstruction);
725    }
726
727
728    /**
729     * Replaces the instruction at a given offset by a given push instruction
730     * of a variable.
731     */
732    private void replaceVariablePushInstruction(Clazz       clazz,
733                                                int         offset,
734                                                Instruction instruction,
735                                                byte        replacementOpcode,
736                                                int         variableIndex)
737    {
738        Instruction replacementInstruction =
739            new VariableInstruction(replacementOpcode, variableIndex);
740
741        replaceInstruction(clazz, offset, instruction, replacementInstruction);
742    }
743
744
745    /**
746     * Replaces the given 'jsr' instruction by a simpler branch instruction,
747     * if it jumps to a subroutine that doesn't return or a subroutine that
748     * is only called from one place.
749     */
750    private void replaceJsrInstruction(Clazz             clazz,
751                                       int               offset,
752                                       BranchInstruction branchInstruction)
753    {
754        // Is the subroutine ever returning?
755        int subroutineStart = offset + branchInstruction.branchOffset;
756        if (!partialEvaluator.isSubroutineReturning(subroutineStart) ||
757            partialEvaluator.branchOrigins(subroutineStart).instructionOffsetCount() == 1)
758        {
759            // All 'jsr' instructions to this subroutine can be replaced
760            // by unconditional branch instructions.
761            replaceBranchInstruction(clazz, offset, branchInstruction);
762        }
763        else if (!partialEvaluator.isTraced(offset + branchInstruction.length(offset)))
764        {
765            // We have to make sure the instruction after this 'jsr'
766            // instruction is valid, even if it is never reached.
767            replaceByInfiniteLoop(clazz, offset + branchInstruction.length(offset), branchInstruction);
768        }
769    }
770
771
772    /**
773     * Deletes the reference popping instruction at the given offset, if
774     * it is at the start of a subroutine that doesn't return or a subroutine
775     * that is only called from one place.
776     */
777    private void deleteReferencePopInstruction(Clazz       clazz,
778                                               int         offset,
779                                               Instruction instruction)
780    {
781        if (partialEvaluator.isSubroutineStart(offset) &&
782            (!partialEvaluator.isSubroutineReturning(offset) ||
783             partialEvaluator.branchOrigins(offset).instructionOffsetCount() == 1))
784        {
785            if (DEBUG) System.out.println("  Deleting store of subroutine return address "+instruction.toString(offset));
786
787            // A reference value can only be specific if it is null.
788            codeAttributeEditor.deleteInstruction(offset);
789        }
790    }
791
792
793    /**
794     * Deletes the given branch instruction, or replaces it by a simpler branch
795     * instruction, if possible.
796     */
797    private void replaceBranchInstruction(Clazz       clazz,
798                                          int         offset,
799                                          Instruction instruction)
800    {
801        InstructionOffsetValue branchTargets = partialEvaluator.branchTargets(offset);
802
803        // Is there exactly one branch target (not from a goto or jsr)?
804        if (branchTargets != null &&
805            branchTargets.instructionOffsetCount() == 1)
806        {
807            // Is it branching to the next instruction?
808            int branchOffset = branchTargets.instructionOffset(0) - offset;
809            if (branchOffset == instruction.length(offset))
810            {
811                if (DEBUG) System.out.println("  Ignoring zero branch instruction at ["+offset+"]");
812            }
813            else
814            {
815                // Replace the branch instruction by a simple branch instruction.
816                Instruction replacementInstruction =
817                    new BranchInstruction(InstructionConstants.OP_GOTO,
818                                          branchOffset);
819
820                replaceInstruction(clazz, offset, instruction, replacementInstruction);
821            }
822        }
823    }
824
825
826    /**
827     * Makes sure all branch targets of the given switch instruction are valid.
828     */
829    private void replaceSwitchInstruction(Clazz             clazz,
830                                          int               offset,
831                                          SwitchInstruction switchInstruction)
832    {
833        // Get the actual branch targets.
834        InstructionOffsetValue branchTargets = partialEvaluator.branchTargets(offset);
835
836        // Get an offset that can serve as a valid default offset.
837        int defaultOffset =
838            branchTargets.instructionOffset(branchTargets.instructionOffsetCount()-1) -
839            offset;
840
841        Instruction replacementInstruction = null;
842
843        // Check the jump offsets.
844        int[] jumpOffsets = switchInstruction.jumpOffsets;
845        for (int index = 0; index < jumpOffsets.length; index++)
846        {
847            if (!branchTargets.contains(offset + jumpOffsets[index]))
848            {
849                // Replace the unused offset.
850                jumpOffsets[index] = defaultOffset;
851
852                // Remember to replace the instruction.
853                replacementInstruction = switchInstruction;
854            }
855        }
856
857        // Check the default offset.
858        if (!branchTargets.contains(offset + switchInstruction.defaultOffset))
859        {
860            // Replace the unused offset.
861            switchInstruction.defaultOffset = defaultOffset;
862
863            // Remember to replace the instruction.
864            replacementInstruction = switchInstruction;
865        }
866
867        if (replacementInstruction != null)
868        {
869            replaceInstruction(clazz, offset, switchInstruction, replacementInstruction);
870        }
871    }
872
873
874    /**
875     * Replaces the given instruction by an infinite loop.
876     */
877    private void replaceByInfiniteLoop(Clazz       clazz,
878                                       int         offset,
879                                       Instruction instruction)
880    {
881        // Replace the instruction by an infinite loop.
882        Instruction replacementInstruction =
883            new BranchInstruction(InstructionConstants.OP_GOTO, 0);
884
885        if (DEBUG) System.out.println("  Replacing unreachable instruction by infinite loop "+replacementInstruction.toString(offset));
886
887        codeAttributeEditor.replaceInstruction(offset, replacementInstruction);
888
889        // Visit the instruction, if required.
890        if (extraInstructionVisitor != null)
891        {
892            // Note: we're not passing the right arguments for now, knowing that
893            // they aren't used anyway.
894            instruction.accept(clazz, null, null, offset, extraInstructionVisitor);
895        }
896    }
897
898
899    /**
900     * Replaces the instruction at a given offset by a given push instruction.
901     */
902    private void replaceInstruction(Clazz       clazz,
903                                    int         offset,
904                                    Instruction instruction,
905                                    Instruction replacementInstruction)
906    {
907        // Pop unneeded stack entries if necessary.
908        int popCount =
909            instruction.stackPopCount(clazz) -
910            replacementInstruction.stackPopCount(clazz);
911
912        insertPopInstructions(offset, popCount);
913
914        if (DEBUG) System.out.println("  Replacing instruction "+instruction.toString(offset)+" -> "+replacementInstruction.toString()+(popCount == 0 ? "" : " ("+popCount+" pops)"));
915
916        codeAttributeEditor.replaceInstruction(offset, replacementInstruction);
917
918        // Visit the instruction, if required.
919        if (extraInstructionVisitor != null)
920        {
921            // Note: we're not passing the right arguments for now, knowing that
922            // they aren't used anyway.
923            instruction.accept(clazz, null, null, offset, extraInstructionVisitor);
924        }
925    }
926
927
928    /**
929     * Pops the given number of stack entries before the instruction at the
930     * given offset.
931     */
932    private void insertPopInstructions(int offset, int popCount)
933    {
934        switch (popCount)
935        {
936            case 0:
937            {
938                break;
939            }
940            case 1:
941            {
942                // Insert a single pop instruction.
943                Instruction popInstruction =
944                    new SimpleInstruction(InstructionConstants.OP_POP);
945
946                codeAttributeEditor.insertBeforeInstruction(offset,
947                                                            popInstruction);
948                break;
949            }
950            case 2:
951            {
952                // Insert a single pop2 instruction.
953                Instruction popInstruction =
954                    new SimpleInstruction(InstructionConstants.OP_POP2);
955
956                codeAttributeEditor.insertBeforeInstruction(offset,
957                                                            popInstruction);
958                break;
959            }
960            default:
961            {
962                // Insert the specified number of pop instructions.
963                Instruction[] popInstructions =
964                    new Instruction[popCount / 2 + popCount % 2];
965
966                Instruction popInstruction =
967                    new SimpleInstruction(InstructionConstants.OP_POP2);
968
969                for (int index = 0; index < popCount / 2; index++)
970                {
971                      popInstructions[index] = popInstruction;
972                }
973
974                if (popCount % 2 == 1)
975                {
976                    popInstruction =
977                        new SimpleInstruction(InstructionConstants.OP_POP);
978
979                    popInstructions[popCount / 2] = popInstruction;
980                }
981
982                codeAttributeEditor.insertBeforeInstruction(offset,
983                                                            popInstructions);
984                break;
985            }
986        }
987    }
988}
989