TailRecursionSimplifier.java revision db267bc191f906f55eaef21a27110cce2ec57fdf 
1/*
2 * ProGuard -- shrinking, optimization, obfuscation, and preverification
3 *             of Java bytecode.
4 *
5 * Copyright (c) 2002-2009 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;
22
23import proguard.classfile.*;
24import proguard.classfile.attribute.*;
25import proguard.classfile.attribute.visitor.*;
26import proguard.classfile.constant.MethodrefConstant;
27import proguard.classfile.constant.visitor.ConstantVisitor;
28import proguard.classfile.editor.CodeAttributeComposer;
29import proguard.classfile.instruction.*;
30import proguard.classfile.instruction.visitor.InstructionVisitor;
31import proguard.classfile.util.*;
32
33/**
34 * This MemberVisitor simplifies tail recursion calls in  all methods that it
35 * visits.
36 *
37 * @author Eric Lafortune
38 */
39public class TailRecursionSimplifier
40extends      SimplifiedVisitor
41implements   AttributeVisitor,
42             InstructionVisitor,
43             ConstantVisitor,
44             ExceptionInfoVisitor
45{
46    //*
47    private static final boolean DEBUG = false;
48    /*/
49    private static       boolean DEBUG = true;
50    //*/
51
52
53    private final InstructionVisitor extraTailRecursionVisitor;
54
55
56    private final CodeAttributeComposer codeAttributeComposer = new CodeAttributeComposer();
57
58    private Method  targetMethod;
59    private boolean recursive;
60    private boolean inlinedAny;
61
62
63
64    /**
65     * Creates a new TailRecursionSimplifier.
66     */
67    public TailRecursionSimplifier()
68    {
69        this(null);
70    }
71
72
73    /**
74     * Creates a new TailRecursionSimplifier with an extra visitor.
75     * @param extraTailRecursionVisitor an optional extra visitor for all
76     *                                  simplified tail recursions.
77     */
78    public TailRecursionSimplifier(InstructionVisitor extraTailRecursionVisitor)
79    {
80        this.extraTailRecursionVisitor = extraTailRecursionVisitor;
81    }
82
83
84    // Implementations for AttributeVisitor.
85
86    public void visitAnyAttribute(Clazz clazz, Attribute attribute) {}
87
88
89    public void visitCodeAttribute(Clazz clazz, Method method, CodeAttribute codeAttribute)
90    {
91        int accessFlags = method.getAccessFlags();
92
93        if (// Only check the method if it is private, static, or final.
94            (accessFlags & (ClassConstants.INTERNAL_ACC_PRIVATE |
95                            ClassConstants.INTERNAL_ACC_STATIC  |
96                            ClassConstants.INTERNAL_ACC_FINAL)) != 0 &&
97
98            // Only check the method if it is not synchronized, etc.
99            (accessFlags & (ClassConstants.INTERNAL_ACC_SYNCHRONIZED |
100                            ClassConstants.INTERNAL_ACC_NATIVE       |
101                            ClassConstants.INTERNAL_ACC_INTERFACE    |
102                            ClassConstants.INTERNAL_ACC_ABSTRACT)) == 0)
103        {
104//            codeAttributeComposer.DEBUG = DEBUG =
105//                clazz.getName().equals("abc/Def") &&
106//                method.getName(clazz).equals("abc");
107
108            targetMethod    = method;
109            inlinedAny      = false;
110            codeAttributeComposer.reset();
111
112            // Append the body of the code.
113            copyCode(clazz, method, codeAttribute);
114
115            // Update the code attribute if any code has been inlined.
116            if (inlinedAny)
117            {
118                codeAttributeComposer.visitCodeAttribute(clazz, method, codeAttribute);
119            }
120        }
121    }
122
123
124    /**
125     * Appends the code of the given code attribute.
126     */
127    private void copyCode(Clazz clazz, Method method, CodeAttribute codeAttribute)
128    {
129        // The code may expand, due to expanding constant and variable
130        // instructions.
131        codeAttributeComposer.beginCodeFragment(codeAttribute.u4codeLength);
132
133        // Copy the instructions.
134        codeAttribute.instructionsAccept(clazz, method, this);
135
136        // Append a label just after the code.
137        codeAttributeComposer.appendLabel(codeAttribute.u4codeLength);
138
139        codeAttributeComposer.endCodeFragment();
140    }
141
142
143    // Implementations for InstructionVisitor.
144
145    public void visitAnyInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, Instruction instruction)
146    {
147        // Copy the instruction.
148        codeAttributeComposer.appendInstruction(offset, instruction.shrink());
149    }
150
151
152    public void visitConstantInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, ConstantInstruction constantInstruction)
153    {
154        // Is it a method invocation?
155        switch (constantInstruction.opcode)
156        {
157            case InstructionConstants.OP_INVOKEVIRTUAL:
158            case InstructionConstants.OP_INVOKESPECIAL:
159            case InstructionConstants.OP_INVOKESTATIC:
160            {
161                // Is it a recursive call?
162                clazz.constantPoolEntryAccept(constantInstruction.constantIndex, this);
163
164                if (recursive)
165                {
166                    // Is the next instruction a return?
167                    int nextOffset =
168                        offset + constantInstruction.length(offset);
169
170                    Instruction nextInstruction =
171                        InstructionFactory.create(codeAttribute.code, nextOffset);
172
173                    switch (nextInstruction.opcode)
174                    {
175                        case InstructionConstants.OP_IRETURN:
176                        case InstructionConstants.OP_LRETURN:
177                        case InstructionConstants.OP_FRETURN:
178                        case InstructionConstants.OP_DRETURN:
179                        case InstructionConstants.OP_ARETURN:
180                        case InstructionConstants.OP_RETURN:
181                        {
182                            // Isn't the recursive call inside a try/catch block?
183                            codeAttribute.exceptionsAccept(clazz, method, offset, this);
184
185                            if (recursive)
186                            {
187                                if (DEBUG)
188                                {
189                                    System.out.println("TailRecursionSimplifier.visitConstantInstruction: ["+
190                                                       clazz.getName()+"."+method.getName(clazz)+method.getDescriptor(clazz)+"], inlining "+constantInstruction.toString(offset));
191                                }
192
193                                // Append a label.
194                                codeAttributeComposer.appendLabel(offset);
195
196                                storeParameters(clazz, method);
197
198                                // Branch back to the start of the method.
199                                int gotoOffset = offset + 1;
200                                codeAttributeComposer.appendInstruction(gotoOffset,
201                                                                        new BranchInstruction(InstructionConstants.OP_GOTO, -gotoOffset));
202
203                                // The original return instruction will be
204                                // removed elsewhere, if possible.
205
206                                // Remember that the code has changed.
207                                inlinedAny = true;
208
209                                if (extraTailRecursionVisitor != null)
210                                {
211                                    extraTailRecursionVisitor.visitConstantInstruction(clazz, method, codeAttribute, offset, constantInstruction);
212                                }
213
214                                // The invocation itself is no longer necessary.
215                                return;
216                            }
217                        }
218                    }
219                }
220
221                break;
222            }
223        }
224
225        // Copy the instruction.
226        codeAttributeComposer.appendInstruction(offset, constantInstruction.shrink());
227    }
228
229
230    // Implementations for ConstantVisitor.
231
232    public void visitMethodrefConstant(Clazz clazz, MethodrefConstant methodrefConstant)
233    {
234        recursive = targetMethod.equals(methodrefConstant.referencedMember);
235    }
236
237
238    // Implementations for ExceptionInfoVisitor.
239
240    public void visitExceptionInfo(Clazz clazz, Method method, CodeAttribute codeAttribute, ExceptionInfo exceptionInfo)
241    {
242        recursive = false;
243    }
244
245
246    // Small utility methods.
247
248    /**
249     * Appends instructions to pop the parameters for the given method, storing
250     * them in new local variables.
251     */
252    private void storeParameters(Clazz clazz, Method method)
253    {
254        String descriptor = method.getDescriptor(clazz);
255
256        boolean isStatic =
257            (method.getAccessFlags() & ClassConstants.INTERNAL_ACC_STATIC) != 0;
258
259        // Count the number of parameters, taking into account their categories.
260        int parameterCount  = ClassUtil.internalMethodParameterCount(descriptor);
261        int parameterSize   = ClassUtil.internalMethodParameterSize(descriptor);
262        int parameterOffset = isStatic ? 0 : 1;
263
264        // Store the parameter types.
265        String[] parameterTypes = new String[parameterSize];
266
267        InternalTypeEnumeration internalTypeEnumeration =
268            new InternalTypeEnumeration(descriptor);
269
270        for (int parameterIndex = 0; parameterIndex < parameterSize; parameterIndex++)
271        {
272            String parameterType = internalTypeEnumeration.nextType();
273            parameterTypes[parameterIndex] = parameterType;
274            if (ClassUtil.internalTypeSize(parameterType) == 2)
275            {
276                parameterIndex++;
277            }
278        }
279
280        codeAttributeComposer.beginCodeFragment(parameterSize + 1);
281
282        // Go over the parameter types backward, storing the stack entries
283        // in their corresponding variables.
284        for (int parameterIndex = parameterSize-1; parameterIndex >= 0; parameterIndex--)
285        {
286            String parameterType = parameterTypes[parameterIndex];
287            if (parameterType != null)
288            {
289                byte opcode;
290                switch (parameterType.charAt(0))
291                {
292                    case ClassConstants.INTERNAL_TYPE_BOOLEAN:
293                    case ClassConstants.INTERNAL_TYPE_BYTE:
294                    case ClassConstants.INTERNAL_TYPE_CHAR:
295                    case ClassConstants.INTERNAL_TYPE_SHORT:
296                    case ClassConstants.INTERNAL_TYPE_INT:
297                        opcode = InstructionConstants.OP_ISTORE;
298                        break;
299
300                    case ClassConstants.INTERNAL_TYPE_LONG:
301                        opcode = InstructionConstants.OP_LSTORE;
302                        break;
303
304                    case ClassConstants.INTERNAL_TYPE_FLOAT:
305                        opcode = InstructionConstants.OP_FSTORE;
306                        break;
307
308                    case ClassConstants.INTERNAL_TYPE_DOUBLE:
309                        opcode = InstructionConstants.OP_DSTORE;
310                        break;
311
312                    default:
313                        opcode = InstructionConstants.OP_ASTORE;
314                        break;
315                }
316
317                codeAttributeComposer.appendInstruction(parameterSize-parameterIndex-1,
318                                                        new VariableInstruction(opcode, parameterOffset + parameterIndex).shrink());
319            }
320        }
321
322        // Put the 'this' reference in variable 0.
323        if (!isStatic)
324        {
325            codeAttributeComposer.appendInstruction(parameterSize,
326                                                    new VariableInstruction(InstructionConstants.OP_ASTORE, 0).shrink());
327        }
328
329        codeAttributeComposer.endCodeFragment();
330    }
331}