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