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.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(true, false);
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.clearModifications(deleteOffset);
127                        codeAttributeEditor.deleteInstruction(deleteOffset);
128                    }
129                }
130
131                // Redirect the goto instruction, if it is still necessary.
132                int newBranchOffset = branchOffset - commonCount;
133                if (newBranchOffset != branchInstruction.length(offset))
134                {
135                    Instruction newGotoInstruction =
136                         new BranchInstruction(opcode, newBranchOffset).shrink();
137                    codeAttributeEditor.replaceInstruction(offset,
138                                                           newGotoInstruction);
139                }
140
141                // Visit the instruction, if required.
142                if (extraInstructionVisitor != null)
143                {
144                    extraInstructionVisitor.visitBranchInstruction(clazz, method, codeAttribute, offset, branchInstruction);
145                }
146            }
147        }
148    }
149
150
151    // Small utility methods.
152
153    /**
154     * Returns the number of common bytes preceding the given offsets,
155     * avoiding branches and exception blocks.
156     */
157    private int commonByteCodeCount(CodeAttribute codeAttribute, int offset1, int offset2)
158    {
159        // Find the block of common instructions preceding it.
160        byte[] code = codeAttribute.code;
161
162        int successfulDelta = 0;
163
164        for (int delta = 1;
165             delta <= offset1 &&
166             delta <= offset2 &&
167             offset2 - delta != offset1;
168             delta++)
169        {
170            int newOffset1 = offset1 - delta;
171            int newOffset2 = offset2 - delta;
172
173            // Is the code identical at both offsets?
174            if (code[newOffset1] != code[newOffset2])
175            {
176                break;
177            }
178
179            // Are there instructions at either offset but not both?
180            if (branchTargetFinder.isInstruction(newOffset1) ^
181                branchTargetFinder.isInstruction(newOffset2))
182            {
183                break;
184            }
185
186            // Are there instructions at both offsets?
187            if (branchTargetFinder.isInstruction(newOffset1) &&
188                branchTargetFinder.isInstruction(newOffset2))
189            {
190                // Are the offsets involved in some branches?
191                // Note that the preverifier doesn't like initializer
192                // invocations to be moved around.
193                // Also note that the preverifier doesn't like pop instructions
194                // that work on different operands.
195                if (branchTargetFinder.isBranchOrigin(newOffset1)   ||
196                    branchTargetFinder.isBranchTarget(newOffset1)   ||
197                    branchTargetFinder.isExceptionStart(newOffset1) ||
198                    branchTargetFinder.isExceptionEnd(newOffset1)   ||
199                    branchTargetFinder.isInitializer(newOffset1)    ||
200                    branchTargetFinder.isExceptionStart(newOffset2) ||
201                    branchTargetFinder.isExceptionEnd(newOffset2)   ||
202                    isPop(code[newOffset1]))
203                {
204                    break;
205                }
206
207                // Make sure the new branch target was a branch target before,
208                // in order not to introduce new entries in the stack map table.
209                if (branchTargetFinder.isBranchTarget(newOffset2))
210                {
211                    successfulDelta = delta;
212                }
213
214                if (branchTargetFinder.isBranchTarget(newOffset1))
215                {
216                    break;
217                }
218            }
219        }
220
221        return successfulDelta;
222    }
223
224
225    /**
226     * Returns whether the given opcode represents a pop instruction that must
227     * get a consistent type (pop, pop2, arraylength).
228     */
229    private boolean isPop(byte opcode)
230    {
231        return opcode == InstructionConstants.OP_POP  ||
232               opcode == InstructionConstants.OP_POP2 ||
233               opcode == InstructionConstants.OP_ARRAYLENGTH;
234    }
235
236
237    /**
238     * Returns the whether there is a boundary of an exception block between
239     * the given offsets (including both).
240     */
241    private boolean exceptionBoundary(CodeAttribute codeAttribute, int offset1, int offset2)
242    {
243        // Swap the offsets if the second one is smaller than the first one.
244        if (offset2 < offset1)
245        {
246            int offset = offset1;
247            offset1 = offset2;
248            offset2 = offset;
249        }
250
251        // Check if there is a boundary of an exception block.
252        for (int offset = offset1; offset <= offset2; offset++)
253        {
254            if (branchTargetFinder.isExceptionStart(offset) ||
255                branchTargetFinder.isExceptionEnd(offset))
256            {
257                return true;
258            }
259        }
260
261        return false;
262    }
263}
264