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.preverify;
22
23import proguard.classfile.*;
24import proguard.classfile.attribute.*;
25import proguard.classfile.attribute.visitor.*;
26import proguard.classfile.editor.CodeAttributeComposer;
27import proguard.classfile.instruction.*;
28import proguard.classfile.instruction.visitor.InstructionVisitor;
29import proguard.classfile.util.SimplifiedVisitor;
30import proguard.classfile.visitor.*;
31import proguard.optimize.peephole.BranchTargetFinder;
32
33/**
34 * This AttributeVisitor inlines local subroutines (jsr/ret) in the code
35 * attributes that it visits.
36 *
37 * @author Eric Lafortune
38 */
39public class CodeSubroutineInliner
40extends      SimplifiedVisitor
41implements   AttributeVisitor,
42             InstructionVisitor,
43             ExceptionInfoVisitor
44{
45    //*
46    private static final boolean DEBUG = false;
47    /*/
48    private static       boolean DEBUG = true;
49    //*/
50
51
52    private final BranchTargetFinder    branchTargetFinder    = new BranchTargetFinder();
53    private final CodeAttributeComposer codeAttributeComposer = new CodeAttributeComposer(true);
54
55    private ExceptionInfoVisitor subroutineExceptionInliner = this;
56    private int                  clipStart                  = 0;
57    private int                  clipEnd                    = Integer.MAX_VALUE;
58
59
60    // Implementations for AttributeVisitor.
61
62    public void visitAnyAttribute(Clazz clazz, Attribute attribute) {}
63
64
65    public void visitCodeAttribute(Clazz clazz, Method method, CodeAttribute codeAttribute)
66    {
67//        DEBUG =
68//            clazz.getName().equals("abc/Def") &&
69//            method.getName(clazz).equals("abc");
70
71        // TODO: Remove this when the subroutine inliner has stabilized.
72        // Catch any unexpected exceptions from the actual visiting method.
73        try
74        {
75            // Process the code.
76            visitCodeAttribute0(clazz, method, codeAttribute);
77        }
78        catch (RuntimeException ex)
79        {
80            System.err.println("Unexpected error while inlining subroutines:");
81            System.err.println("  Class       = ["+clazz.getName()+"]");
82            System.err.println("  Method      = ["+method.getName(clazz)+method.getDescriptor(clazz)+"]");
83            System.err.println("  Exception   = ["+ex.getClass().getName()+"] ("+ex.getMessage()+")");
84
85            if (DEBUG)
86            {
87                method.accept(clazz, new ClassPrinter());
88            }
89
90            throw ex;
91        }
92    }
93
94
95    public void visitCodeAttribute0(Clazz clazz, Method method, CodeAttribute codeAttribute)
96    {
97        branchTargetFinder.visitCodeAttribute(clazz, method, codeAttribute);
98
99        // Don't bother if there aren't any subroutines anyway.
100        if (!containsSubroutines(codeAttribute))
101        {
102            return;
103        }
104
105        if (DEBUG)
106        {
107            System.out.println("SubroutineInliner: processing ["+clazz.getName()+"."+method.getName(clazz)+method.getDescriptor(clazz)+"]");
108        }
109
110        // Append the body of the code.
111        codeAttributeComposer.reset();
112        codeAttributeComposer.beginCodeFragment(codeAttribute.u4codeLength);
113
114        // Copy the non-subroutine instructions.
115        int offset  = 0;
116        while (offset < codeAttribute.u4codeLength)
117        {
118            Instruction instruction = InstructionFactory.create(codeAttribute.code, offset);
119            int instructionLength = instruction.length(offset);
120
121            // Is this returning subroutine?
122            if (branchTargetFinder.isSubroutine(offset) &&
123                branchTargetFinder.isSubroutineReturning(offset))
124            {
125                // Skip the subroutine.
126                if (DEBUG)
127                {
128                    System.out.println("  Skipping original subroutine instruction "+instruction.toString(offset));
129                }
130
131                // Append a label at this offset instead.
132                codeAttributeComposer.appendLabel(offset);
133            }
134            else
135            {
136                // Copy the instruction, inlining any subroutine call recursively.
137                instruction.accept(clazz, method, codeAttribute, offset, this);
138            }
139
140            offset += instructionLength;
141        }
142
143        // Copy the exceptions. Note that exceptions with empty try blocks
144        // are automatically removed.
145        codeAttribute.exceptionsAccept(clazz,
146                                       method,
147                                       subroutineExceptionInliner);
148
149        if (DEBUG)
150        {
151            System.out.println("  Appending label after code at ["+offset+"]");
152        }
153
154        // Append a label just after the code.
155        codeAttributeComposer.appendLabel(codeAttribute.u4codeLength);
156
157        // End and update the code attribute.
158        codeAttributeComposer.endCodeFragment();
159        codeAttributeComposer.visitCodeAttribute(clazz, method, codeAttribute);
160    }
161
162
163    /**
164     * Returns whether the given code attribute contains any subroutines.
165     */
166    private boolean containsSubroutines(CodeAttribute codeAttribute)
167    {
168        for (int offset = 0; offset < codeAttribute.u4codeLength; offset++)
169        {
170            if (branchTargetFinder.isSubroutineInvocation(offset))
171            {
172                return true;
173            }
174        }
175
176        return false;
177    }
178
179
180    /**
181     * Appends the specified subroutine.
182     */
183    private void inlineSubroutine(Clazz         clazz,
184                                  Method        method,
185                                  CodeAttribute codeAttribute,
186                                  int           subroutineInvocationOffset,
187                                  int           subroutineStart)
188    {
189        int subroutineEnd = branchTargetFinder.subroutineEnd(subroutineStart);
190
191        if (DEBUG)
192        {
193            System.out.println("  Inlining subroutine ["+subroutineStart+" -> "+subroutineEnd+"] at ["+subroutineInvocationOffset+"]");
194        }
195
196        // Don't go inlining exceptions that are already applicable to this
197        // subroutine invocation.
198        ExceptionInfoVisitor oldSubroutineExceptionInliner = subroutineExceptionInliner;
199        int                  oldClipStart                  = clipStart;
200        int                  oldClipEnd                    = clipEnd;
201
202        subroutineExceptionInliner =
203            new ExceptionExcludedOffsetFilter(subroutineInvocationOffset,
204                                              subroutineExceptionInliner);
205        clipStart = subroutineStart;
206        clipEnd   = subroutineEnd;
207
208        codeAttributeComposer.beginCodeFragment(codeAttribute.u4codeLength);
209
210        // Copy the subroutine instructions, inlining any subroutine calls
211        // recursively.
212        codeAttribute.instructionsAccept(clazz,
213                                         method,
214                                         subroutineStart,
215                                         subroutineEnd,
216                                         this);
217
218        if (DEBUG)
219        {
220            System.out.println("    Appending label after inlined subroutine at ["+subroutineEnd+"]");
221        }
222
223        // Append a label just after the code.
224        codeAttributeComposer.appendLabel(subroutineEnd);
225
226        // Inline the subroutine exceptions.
227        codeAttribute.exceptionsAccept(clazz,
228                                       method,
229                                       subroutineStart,
230                                       subroutineEnd,
231                                       subroutineExceptionInliner);
232
233        // We can again inline exceptions that are applicable to this
234        // subroutine invocation.
235        subroutineExceptionInliner = oldSubroutineExceptionInliner;
236        clipStart                  = oldClipStart;
237        clipEnd                    = oldClipEnd;
238
239        codeAttributeComposer.endCodeFragment();
240    }
241
242
243    // Implementations for InstructionVisitor.
244
245    public void visitAnyInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, Instruction instruction)
246    {
247        // Append the instruction.
248        codeAttributeComposer.appendInstruction(offset, instruction.shrink());
249    }
250
251
252    public void visitVariableInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, VariableInstruction variableInstruction)
253    {
254        byte opcode = variableInstruction.opcode;
255        if (opcode == InstructionConstants.OP_RET)
256        {
257            // Is the return instruction the last instruction of the subroutine?
258            if (branchTargetFinder.subroutineEnd(offset) == offset + variableInstruction.length(offset))
259            {
260                if (DEBUG)
261                {
262                    System.out.println("    Replacing subroutine return at ["+offset+"] by a label");
263                }
264
265                // Append a label at this offset instead of the subroutine return.
266                codeAttributeComposer.appendLabel(offset);
267            }
268            else
269            {
270                if (DEBUG)
271                {
272                    System.out.println("    Replacing subroutine return at ["+offset+"] by a simple branch");
273                }
274
275                // Replace the instruction by a branch.
276                Instruction replacementInstruction =
277                    new BranchInstruction(InstructionConstants.OP_GOTO,
278                                          branchTargetFinder.subroutineEnd(offset) - offset).shrink();
279
280                codeAttributeComposer.appendInstruction(offset, replacementInstruction);
281            }
282        }
283        else if (branchTargetFinder.isSubroutineStart(offset))
284        {
285            if (DEBUG)
286            {
287                System.out.println("    Replacing first subroutine instruction at ["+offset+"] by a label");
288            }
289
290            // Append a label at this offset instead of saving the subroutine
291            // return address.
292            codeAttributeComposer.appendLabel(offset);
293        }
294        else
295        {
296            // Append the instruction.
297            codeAttributeComposer.appendInstruction(offset, variableInstruction);
298        }
299    }
300
301
302    public void visitBranchInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, BranchInstruction branchInstruction)
303    {
304        byte opcode = branchInstruction.opcode;
305        if (opcode == InstructionConstants.OP_JSR ||
306            opcode == InstructionConstants.OP_JSR_W)
307        {
308            int branchOffset = branchInstruction.branchOffset;
309            int branchTarget = offset + branchOffset;
310
311            // Is the subroutine ever returning?
312            if (branchTargetFinder.isSubroutineReturning(branchTarget))
313            {
314                // Append a label at this offset instead of the subroutine invocation.
315                codeAttributeComposer.appendLabel(offset);
316
317                // Inline the invoked subroutine.
318                inlineSubroutine(clazz,
319                                 method,
320                                 codeAttribute,
321                                 offset,
322                                 branchTarget);
323            }
324            else
325            {
326                if (DEBUG)
327                {
328                    System.out.println("Replacing subroutine invocation at ["+offset+"] by a simple branch");
329                }
330
331                // Replace the subroutine invocation by a simple branch.
332                Instruction replacementInstruction =
333                    new BranchInstruction(InstructionConstants.OP_GOTO,
334                                          branchOffset).shrink();
335
336                codeAttributeComposer.appendInstruction(offset, replacementInstruction);
337            }
338        }
339        else
340        {
341            // Append the instruction.
342            codeAttributeComposer.appendInstruction(offset, branchInstruction);
343        }
344    }
345
346
347    // Implementations for ExceptionInfoVisitor.
348
349    public void visitExceptionInfo(Clazz clazz, Method method, CodeAttribute codeAttribute, ExceptionInfo exceptionInfo)
350    {
351        int startPC   = Math.max(exceptionInfo.u2startPC, clipStart);
352        int endPC     = Math.min(exceptionInfo.u2endPC,   clipEnd);
353        int handlerPC = exceptionInfo.u2handlerPC;
354        int catchType = exceptionInfo.u2catchType;
355
356        // Exclude any subroutine invocations that jump out of the try block,
357        // by adding a try block before (and later on, after) each invocation.
358        for (int offset = startPC; offset < endPC; offset++)
359        {
360            if (branchTargetFinder.isSubroutineInvocation(offset))
361            {
362                Instruction instruction = InstructionFactory.create(codeAttribute.code, offset);
363                int instructionLength = instruction.length(offset);
364
365                // Is it a subroutine invocation?
366                if (!exceptionInfo.isApplicable(offset + ((BranchInstruction)instruction).branchOffset))
367                {
368                    if (DEBUG)
369                    {
370                        System.out.println("  Appending extra exception ["+startPC+" -> "+offset+"] -> "+handlerPC);
371                    }
372
373                    // Append a try block that ends before the subroutine invocation.
374                    codeAttributeComposer.appendException(new ExceptionInfo(startPC,
375                                                                            offset,
376                                                                            handlerPC,
377                                                                            catchType));
378
379                    // The next try block will start after the subroutine invocation.
380                    startPC = offset + instructionLength;
381                }
382            }
383        }
384
385        if (DEBUG)
386        {
387            if (startPC == exceptionInfo.u2startPC &&
388                endPC   == exceptionInfo.u2endPC)
389            {
390                System.out.println("  Appending exception ["+startPC+" -> "+endPC+"] -> "+handlerPC);
391            }
392            else
393            {
394                System.out.println("  Appending clipped exception ["+exceptionInfo.u2startPC+" -> "+exceptionInfo.u2endPC+"] ~> ["+startPC+" -> "+endPC+"] -> "+handlerPC);
395            }
396        }
397
398        // Append the exception. Note that exceptions with empty try blocks
399        // are automatically ignored.
400        codeAttributeComposer.appendException(new ExceptionInfo(startPC,
401                                                                endPC,
402                                                                handlerPC,
403                                                                catchType));
404    }
405}
406