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;
22
23import proguard.classfile.*;
24import proguard.classfile.attribute.*;
25import proguard.classfile.attribute.visitor.*;
26import proguard.classfile.constant.*;
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    private final MyRecursionChecker    recursionChecker      = new MyRecursionChecker();
58
59    private Method  targetMethod;
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.ACC_PRIVATE |
95                            ClassConstants.ACC_STATIC  |
96                            ClassConstants.ACC_FINAL)) != 0 &&
97
98            // Only check the method if it is not synchronized, etc.
99            (accessFlags & (ClassConstants.ACC_SYNCHRONIZED |
100                            ClassConstants.ACC_NATIVE       |
101                            ClassConstants.ACC_ABSTRACT)) == 0)
102        {
103//            codeAttributeComposer.DEBUG = DEBUG =
104//                clazz.getName().equals("abc/Def") &&
105//                method.getName(clazz).equals("abc");
106
107            targetMethod = method;
108            inlinedAny   = false;
109            codeAttributeComposer.reset();
110
111            // The code may expand, due to expanding constant and variable
112            // instructions.
113            codeAttributeComposer.beginCodeFragment(codeAttribute.u4codeLength);
114
115            // Copy the instructions.
116            codeAttribute.instructionsAccept(clazz, method, this);
117
118            // Update the code attribute if any code has been inlined.
119            if (inlinedAny)
120            {
121                // Copy the exceptions.
122                codeAttribute.exceptionsAccept(clazz, method, this);
123
124                // Append a label just after the code.
125                codeAttributeComposer.appendLabel(codeAttribute.u4codeLength);
126
127                codeAttributeComposer.endCodeFragment();
128
129                codeAttributeComposer.visitCodeAttribute(clazz, method, codeAttribute);
130            }
131        }
132    }
133
134
135    // Implementations for InstructionVisitor.
136
137    public void visitAnyInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, Instruction instruction)
138    {
139        // Copy the instruction.
140        codeAttributeComposer.appendInstruction(offset, instruction);
141    }
142
143
144    public void visitConstantInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, ConstantInstruction constantInstruction)
145    {
146        // Is it a method invocation?
147        switch (constantInstruction.opcode)
148        {
149            case InstructionConstants.OP_INVOKEVIRTUAL:
150            case InstructionConstants.OP_INVOKESPECIAL:
151            case InstructionConstants.OP_INVOKESTATIC:
152            {
153                // Is it a recursive call?
154                clazz.constantPoolEntryAccept(constantInstruction.constantIndex, recursionChecker);
155
156                if (recursionChecker.isRecursive())
157                {
158                    // Is the next instruction a return?
159                    int nextOffset =
160                        offset + constantInstruction.length(offset);
161
162                    Instruction nextInstruction =
163                        InstructionFactory.create(codeAttribute.code, nextOffset);
164
165                    switch (nextInstruction.opcode)
166                    {
167                        case InstructionConstants.OP_IRETURN:
168                        case InstructionConstants.OP_LRETURN:
169                        case InstructionConstants.OP_FRETURN:
170                        case InstructionConstants.OP_DRETURN:
171                        case InstructionConstants.OP_ARETURN:
172                        case InstructionConstants.OP_RETURN:
173                        {
174                            // Isn't the recursive call inside a try/catch block?
175                            codeAttribute.exceptionsAccept(clazz, method, offset, recursionChecker);
176
177                            if (recursionChecker.isRecursive())
178                            {
179                                if (DEBUG)
180                                {
181                                    System.out.println("TailRecursionSimplifier: ["+
182                                                       clazz.getName()+"."+method.getName(clazz)+method.getDescriptor(clazz)+"], inlining "+constantInstruction.toString(offset));
183                                }
184
185                                // Append a label.
186                                codeAttributeComposer.appendLabel(offset);
187
188                                storeParameters(clazz, method);
189
190                                // Branch back to the start of the method.
191                                int gotoOffset = offset + 1;
192                                codeAttributeComposer.appendInstruction(gotoOffset,
193                                                                        new BranchInstruction(InstructionConstants.OP_GOTO, -gotoOffset));
194
195                                // The original return instruction will be
196                                // removed elsewhere, if possible.
197
198                                // Remember that the code has changed.
199                                inlinedAny = true;
200
201                                if (extraTailRecursionVisitor != null)
202                                {
203                                    extraTailRecursionVisitor.visitConstantInstruction(clazz, method, codeAttribute, offset, constantInstruction);
204                                }
205
206                                // The invocation itself is no longer necessary.
207                                return;
208                            }
209                        }
210                    }
211                }
212
213                break;
214            }
215        }
216
217        // Copy the instruction.
218        codeAttributeComposer.appendInstruction(offset, constantInstruction);
219    }
220
221
222    // Implementations for ExceptionInfoVisitor.
223
224    public void visitExceptionInfo(Clazz clazz, Method method, CodeAttribute codeAttribute, ExceptionInfo exceptionInfo)
225    {
226        codeAttributeComposer.appendException(new ExceptionInfo(exceptionInfo.u2startPC,
227                                                                exceptionInfo.u2endPC,
228                                                                exceptionInfo.u2handlerPC,
229                                                                exceptionInfo.u2catchType));
230    }
231
232
233    /**
234     * This ConstantVisitor and ExceptionInfoVisitor returns whether a method
235     * invocation can be treated as tail-recursive.
236     */
237    private class MyRecursionChecker
238    extends       SimplifiedVisitor
239    implements    ConstantVisitor,
240                  ExceptionInfoVisitor
241    {
242        private boolean recursive;
243
244
245        /**
246         * Returns whether the method invocation can be treated as
247         * tail-recursive.
248         */
249        public boolean isRecursive()
250        {
251            return recursive;
252        }
253
254        // Implementations for ConstantVisitor.
255
256        public void visitAnyMethodrefConstant(Clazz clazz, RefConstant methodrefConstant)
257        {
258            recursive = targetMethod.equals(methodrefConstant.referencedMember);
259        }
260
261
262        // Implementations for ExceptionInfoVisitor.
263
264        public void visitExceptionInfo(Clazz clazz, Method method, CodeAttribute codeAttribute, ExceptionInfo exceptionInfo)
265        {
266            recursive = false;
267        }
268    }
269
270
271    // Small utility methods.
272
273    /**
274     * Appends instructions to pop the parameters for the given method, storing
275     * them in new local variables.
276     */
277    private void storeParameters(Clazz clazz, Method method)
278    {
279        String descriptor = method.getDescriptor(clazz);
280
281        boolean isStatic =
282            (method.getAccessFlags() & ClassConstants.ACC_STATIC) != 0;
283
284        // Count the number of parameters, taking into account their categories.
285        int parameterSize   = ClassUtil.internalMethodParameterSize(descriptor);
286        int parameterOffset = isStatic ? 0 : 1;
287
288        // Store the parameter types.
289        String[] parameterTypes = new String[parameterSize];
290
291        InternalTypeEnumeration internalTypeEnumeration =
292            new InternalTypeEnumeration(descriptor);
293
294        for (int parameterIndex = 0; parameterIndex < parameterSize; parameterIndex++)
295        {
296            String parameterType = internalTypeEnumeration.nextType();
297            parameterTypes[parameterIndex] = parameterType;
298            if (ClassUtil.internalTypeSize(parameterType) == 2)
299            {
300                parameterIndex++;
301            }
302        }
303
304        codeAttributeComposer.beginCodeFragment(parameterSize + 1);
305
306        // Go over the parameter types backward, storing the stack entries
307        // in their corresponding variables.
308        for (int parameterIndex = parameterSize-1; parameterIndex >= 0; parameterIndex--)
309        {
310            String parameterType = parameterTypes[parameterIndex];
311            if (parameterType != null)
312            {
313                byte opcode;
314                switch (parameterType.charAt(0))
315                {
316                    case ClassConstants.TYPE_BOOLEAN:
317                    case ClassConstants.TYPE_BYTE:
318                    case ClassConstants.TYPE_CHAR:
319                    case ClassConstants.TYPE_SHORT:
320                    case ClassConstants.TYPE_INT:
321                        opcode = InstructionConstants.OP_ISTORE;
322                        break;
323
324                    case ClassConstants.TYPE_LONG:
325                        opcode = InstructionConstants.OP_LSTORE;
326                        break;
327
328                    case ClassConstants.TYPE_FLOAT:
329                        opcode = InstructionConstants.OP_FSTORE;
330                        break;
331
332                    case ClassConstants.TYPE_DOUBLE:
333                        opcode = InstructionConstants.OP_DSTORE;
334                        break;
335
336                    default:
337                        opcode = InstructionConstants.OP_ASTORE;
338                        break;
339                }
340
341                codeAttributeComposer.appendInstruction(parameterSize-parameterIndex-1,
342                                                        new VariableInstruction(opcode, parameterOffset + parameterIndex));
343            }
344        }
345
346        // Put the 'this' reference in variable 0.
347        if (!isStatic)
348        {
349            codeAttributeComposer.appendInstruction(parameterSize,
350                                                    new VariableInstruction(InstructionConstants.OP_ASTORE, 0));
351        }
352
353        codeAttributeComposer.endCodeFragment();
354    }
355}