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.optimize.peephole;
22
23import proguard.classfile.*;
24import proguard.classfile.attribute.*;
25import proguard.classfile.attribute.visitor.*;
26import proguard.classfile.instruction.*;
27import proguard.classfile.instruction.visitor.InstructionVisitor;
28import proguard.classfile.util.SimplifiedVisitor;
29
30/**
31 * This AttributeVisitor finds all instruction offsets, branch targets, and
32 * exception targets in the CodeAttribute objects that it visits.
33 *
34 * @author Eric Lafortune
35 */
36public class ReachableCodeMarker
37extends      SimplifiedVisitor
38implements   AttributeVisitor,
39             InstructionVisitor,
40             ExceptionInfoVisitor
41{
42    private boolean[] isReachable = new boolean[ClassConstants.TYPICAL_CODE_LENGTH];
43
44    private boolean next;
45    private boolean evaluateExceptions;
46
47
48    /**
49     * Returns whether the instruction at the given offset is reachable in
50     * the CodeAttribute that was visited most recently.
51     */
52    public boolean isReachable(int offset)
53    {
54        return isReachable[offset];
55    }
56
57
58    /**
59     * Returns whether any of the instructions at the given offsets are
60     * reachable in the CodeAttribute that was visited most recently.
61     */
62    public boolean isReachable(int startOffset, int endOffset)
63    {
64        // Check if any of the instructions is reachable.
65        for (int offset = startOffset; offset < endOffset; offset++)
66        {
67            if (isReachable[offset])
68            {
69                return true;
70            }
71        }
72
73        return false;
74    }
75
76
77    // Implementations for AttributeVisitor.
78
79    public void visitAnyAttribute(Clazz clazz, Attribute attribute) {}
80
81
82    public void visitCodeAttribute(Clazz clazz, Method method, CodeAttribute codeAttribute)
83    {
84        // Make sure there is a sufficiently large array.
85        int codeLength = codeAttribute.u4codeLength;
86        if (isReachable.length < codeLength)
87        {
88            // Create a new array.
89            isReachable = new boolean[codeLength];
90        }
91        else
92        {
93            // Reset the array.
94            for (int index = 0; index < codeLength; index++)
95            {
96                isReachable[index] = false;
97            }
98        }
99
100        // Mark the code, starting at the entry point.
101        markCode(clazz, method, codeAttribute, 0);
102
103        // Mark the exception handlers, iterating as long as necessary.
104        do
105        {
106            evaluateExceptions = false;
107
108            codeAttribute.exceptionsAccept(clazz, method, this);
109        }
110        while (evaluateExceptions);
111    }
112
113
114    // Implementations for InstructionVisitor.
115
116    public void visitSimpleInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, SimpleInstruction simpleInstruction)
117    {
118        byte opcode = simpleInstruction.opcode;
119        if (opcode == InstructionConstants.OP_IRETURN ||
120            opcode == InstructionConstants.OP_LRETURN ||
121            opcode == InstructionConstants.OP_FRETURN ||
122            opcode == InstructionConstants.OP_DRETURN ||
123            opcode == InstructionConstants.OP_ARETURN ||
124            opcode == InstructionConstants.OP_RETURN  ||
125            opcode == InstructionConstants.OP_ATHROW)
126        {
127            next = false;
128        }
129    }
130
131
132    public void visitConstantInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, ConstantInstruction constantInstruction)
133    {
134    }
135
136
137    public void visitVariableInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, VariableInstruction variableInstruction)
138    {
139        if (variableInstruction.opcode == InstructionConstants.OP_RET)
140        {
141            next = false;
142        }
143    }
144
145
146    public void visitBranchInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, BranchInstruction branchInstruction)
147    {
148        // Mark the branch target.
149        markBranchTarget(clazz,
150                         method,
151                         codeAttribute,
152                         offset + branchInstruction.branchOffset);
153
154        byte opcode = branchInstruction.opcode;
155        if (opcode == InstructionConstants.OP_GOTO ||
156            opcode == InstructionConstants.OP_GOTO_W)
157        {
158            next = false;
159        }
160    }
161
162
163    public void visitAnySwitchInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, SwitchInstruction switchInstruction)
164    {
165        // Mark the branch targets of the default jump offset.
166        markBranchTarget(clazz,
167                         method,
168                         codeAttribute,
169                         offset + switchInstruction.defaultOffset);
170
171        // Mark the branch targets of the jump offsets.
172        markBranchTargets(clazz,
173                          method,
174                          codeAttribute,
175                          offset,
176                          switchInstruction.jumpOffsets);
177
178        next = false;
179    }
180
181
182    // Implementations for ExceptionInfoVisitor.
183
184    public void visitExceptionInfo(Clazz clazz, Method method, CodeAttribute codeAttribute, ExceptionInfo exceptionInfo)
185    {
186        // Mark the exception handler if it's relevant.
187        if (!isReachable(exceptionInfo.u2handlerPC) &&
188            isReachable(exceptionInfo.u2startPC, exceptionInfo.u2endPC))
189        {
190            markCode(clazz, method, codeAttribute, exceptionInfo.u2handlerPC);
191
192            evaluateExceptions = true;
193        }
194    }
195
196
197    // Small utility methods.
198
199    /**
200     * Marks the branch targets of the given jump offsets for the instruction
201     * at the given offset.
202     */
203    private void markBranchTargets(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, int[] jumpOffsets)
204    {
205        for (int index = 0; index < jumpOffsets.length; index++)
206        {
207            markCode(clazz, method, codeAttribute, offset + jumpOffsets[index]);
208        }
209    }
210
211
212    /**
213     * Marks the branch target at the given offset.
214     */
215    private void markBranchTarget(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset)
216    {
217        boolean oldNext = next;
218
219        markCode(clazz, method, codeAttribute, offset);
220
221        next = oldNext;
222    }
223
224
225    /**
226     * Marks the code starting at the given offset.
227     */
228    private void markCode(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset)
229    {
230        boolean oldNext = next;
231
232        byte[] code = codeAttribute.code;
233
234        // Continue with the current instruction as long as we haven't marked it
235        // yet.
236        while (!isReachable[offset])
237        {
238            // Get the current instruction.
239            Instruction instruction = InstructionFactory.create(code, offset);
240
241            // Mark it as reachable.
242            isReachable[offset] = true;
243
244            // By default, we'll assume we can continue with the next
245            // instruction in a moment.
246            next = true;
247
248            // Mark the branch targets, if any.
249            instruction.accept(clazz, method, codeAttribute, offset, this);
250
251            // Can we really continue with the next instruction?
252            if (!next)
253            {
254                break;
255            }
256
257            // Go to the next instruction.
258            offset += instruction.length(offset);
259        }
260
261        next = oldNext;
262    }
263}
264