GotoCommonCodeReplacer.java revision cfead78069f3dc32998dc118ee08cab3867acea2 
1/*
2 * ProGuard -- shrinking, optimization, obfuscation, and preverification
3 *             of Java bytecode.
4 *
5 * Copyright (c) 2002-2011 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.peephole;
22
23import proguard.classfile.*;
24import proguard.classfile.attribute.*;
25import proguard.classfile.attribute.visitor.AttributeVisitor;
26import proguard.classfile.editor.CodeAttributeEditor;
27import proguard.classfile.instruction.*;
28import proguard.classfile.instruction.visitor.InstructionVisitor;
29import proguard.classfile.util.SimplifiedVisitor;
30
31/**
32 * This AttributeVisitor redirects unconditional branches so any common code
33 * is shared, and the code preceding the branch can be removed, in the code
34 * attributes that it visits.
35 *
36 * @author Eric Lafortune
37 */
38public class GotoCommonCodeReplacer
39extends      SimplifiedVisitor
40implements   AttributeVisitor,
41             InstructionVisitor
42{
43    //*
44    private static final boolean DEBUG = false;
45    /*/
46    private static       boolean DEBUG = true;
47    //*/
48
49
50    private final InstructionVisitor  extraInstructionVisitor;
51
52    private final BranchTargetFinder  branchTargetFinder  = new BranchTargetFinder();
53    private final CodeAttributeEditor codeAttributeEditor = new CodeAttributeEditor();
54
55
56    /**
57     * Creates a new GotoCommonCodeReplacer.
58     * @param extraInstructionVisitor an optional extra visitor for all replaced
59     *                                goto instructions.
60     */
61    public GotoCommonCodeReplacer(InstructionVisitor  extraInstructionVisitor)
62    {
63        this.extraInstructionVisitor = extraInstructionVisitor;
64    }
65
66
67    // Implementations for AttributeVisitor.
68
69    public void visitAnyAttribute(Clazz clazz, Attribute attribute) {}
70
71
72    public void visitCodeAttribute(Clazz clazz, Method method, CodeAttribute codeAttribute)
73    {
74//        DEBUG =
75//            clazz.getName().equals("abc/Def") &&
76//            method.getName(clazz).equals("abc");
77
78        // Mark all branch targets.
79        branchTargetFinder.visitCodeAttribute(clazz, method, codeAttribute);
80
81        // Reset the code attribute editor.
82        codeAttributeEditor.reset(codeAttribute.u4codeLength);
83
84        // Remap the variables of the instructions.
85        codeAttribute.instructionsAccept(clazz, method, this);
86
87        // Apply the code atribute editor.
88        codeAttributeEditor.visitCodeAttribute(clazz, method, codeAttribute);
89    }
90
91
92    // Implementations for InstructionVisitor.
93
94    public void visitAnyInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, Instruction instruction) {}
95
96
97    public void visitBranchInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, BranchInstruction branchInstruction)
98    {
99        // Check if the instruction is an unconditional goto instruction that
100        // isn't the target of a branch itself.
101        byte opcode = branchInstruction.opcode;
102        if ((opcode == InstructionConstants.OP_GOTO ||
103             opcode == InstructionConstants.OP_GOTO_W) &&
104            !branchTargetFinder.isBranchTarget(offset))
105        {
106            int branchOffset = branchInstruction.branchOffset;
107            int targetOffset = offset + branchOffset;
108
109            // Get the number of common bytes.
110            int commonCount = commonByteCodeCount(codeAttribute, offset, targetOffset);
111
112            if (commonCount > 0 &&
113                !exceptionBoundary(codeAttribute, offset, targetOffset))
114            {
115                if (DEBUG)
116                {
117                    System.out.println("GotoCommonCodeReplacer: "+clazz.getName()+"."+method.getName(clazz)+" (["+(offset-commonCount)+"] - "+branchInstruction.toString(offset)+" -> "+targetOffset+")");
118                }
119
120                // Delete the common instructions.
121                for (int delta = 0; delta <= commonCount; delta++)
122                {
123                    int deleteOffset = offset - delta;
124                    if (branchTargetFinder.isInstruction(deleteOffset))
125                    {
126                        codeAttributeEditor.replaceInstruction(     deleteOffset, (Instruction)null);
127                        codeAttributeEditor.insertBeforeInstruction(deleteOffset, (Instruction)null);
128                        codeAttributeEditor.insertAfterInstruction( deleteOffset, (Instruction)null);
129
130                        codeAttributeEditor.deleteInstruction(deleteOffset);
131                    }
132                }
133
134                // Redirect the goto instruction, if it is still necessary.
135                int newBranchOffset = branchOffset - commonCount;
136                if (newBranchOffset != branchInstruction.length(offset))
137                {
138                    Instruction newGotoInstruction =
139                         new BranchInstruction(opcode, newBranchOffset);
140                    codeAttributeEditor.replaceInstruction(offset,
141                                                           newGotoInstruction);
142                }
143
144                // Visit the instruction, if required.
145                if (extraInstructionVisitor != null)
146                {
147                    extraInstructionVisitor.visitBranchInstruction(clazz, method, codeAttribute, offset, branchInstruction);
148                }
149            }
150        }
151    }
152
153
154    // Small utility methods.
155
156    /**
157     * Returns the number of common bytes preceding the given offsets,
158     * avoiding branches and exception blocks.
159     */
160    private int commonByteCodeCount(CodeAttribute codeAttribute, int offset1, int offset2)
161    {
162        // Find the block of common instructions preceding it.
163        byte[] code = codeAttribute.code;
164
165        int successfulDelta = 0;
166
167        for (int delta = 1;
168             delta <= offset1 &&
169             delta <= offset2 &&
170             offset2 - delta != offset1;
171             delta++)
172        {
173            int newOffset1 = offset1 - delta;
174            int newOffset2 = offset2 - delta;
175
176            // Is the code identical at both offsets?
177            if (code[newOffset1] != code[newOffset2])
178            {
179                break;
180            }
181
182            // Are there instructions at either offset but not both?
183            if (branchTargetFinder.isInstruction(newOffset1) ^
184                branchTargetFinder.isInstruction(newOffset2))
185            {
186                break;
187            }
188
189            // Are there instructions at both offsets?
190            if (branchTargetFinder.isInstruction(newOffset1) &&
191                branchTargetFinder.isInstruction(newOffset2))
192            {
193                // Are the offsets involved in some branches?
194                // Note that the preverifier doesn't like initializer
195                // invocations to be moved around.
196                // Also note that the preverifier doesn't like pop instructions
197                // that work on different operands.
198                if (branchTargetFinder.isBranchOrigin(newOffset1)   ||
199                    branchTargetFinder.isBranchTarget(newOffset1)   ||
200                    branchTargetFinder.isExceptionStart(newOffset1) ||
201                    branchTargetFinder.isExceptionEnd(newOffset1)   ||
202                    branchTargetFinder.isInitializer(newOffset1)    ||
203                    branchTargetFinder.isExceptionStart(newOffset2) ||
204                    branchTargetFinder.isExceptionEnd(newOffset2)   ||
205                    isPop(code[newOffset1]))
206                {
207                    break;
208                }
209
210                // Make sure the new branch target was a branch target before,
211                // in order not to introduce new entries in the stack map table.
212                if (branchTargetFinder.isBranchTarget(newOffset2))
213                {
214                    successfulDelta = delta;
215                }
216
217                if (branchTargetFinder.isBranchTarget(newOffset1))
218                {
219                    break;
220                }
221            }
222        }
223
224        return successfulDelta;
225    }
226
227
228    /**
229     * Returns whether the given opcode represents a pop instruction that must
230     * get a consistent type (pop, pop2, arraylength).
231     */
232    private boolean isPop(byte opcode)
233    {
234        return opcode == InstructionConstants.OP_POP  ||
235               opcode == InstructionConstants.OP_POP2 ||
236               opcode == InstructionConstants.OP_ARRAYLENGTH;
237    }
238
239
240    /**
241     * Returns the whether there is a boundary of an exception block between
242     * the given offsets (including both).
243     */
244    private boolean exceptionBoundary(CodeAttribute codeAttribute, int offset1, int offset2)
245    {
246        // Swap the offsets if the second one is smaller than the first one.
247        if (offset2 < offset1)
248        {
249            int offset = offset1;
250            offset1 = offset2;
251            offset2 = offset;
252        }
253
254        // Check if there is a boundary of an exception block.
255        for (int offset = offset1; offset <= offset2; offset++)
256        {
257            if (branchTargetFinder.isExceptionStart(offset) ||
258                branchTargetFinder.isExceptionEnd(offset))
259            {
260                return true;
261            }
262        }
263
264        return false;
265    }
266}
267