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.classfile.attribute.visitor;
22
23import proguard.classfile.*;
24import proguard.classfile.attribute.*;
25import proguard.classfile.instruction.*;
26import proguard.classfile.instruction.visitor.InstructionVisitor;
27import proguard.classfile.util.SimplifiedVisitor;
28import proguard.classfile.visitor.ClassPrinter;
29
30import java.util.Arrays;
31
32/**
33 * This AttributeVisitor computes the stack sizes at all instruction offsets
34 * of the code attributes that it visits.
35 *
36 * @author Eric Lafortune
37 */
38public class StackSizeComputer
39extends      SimplifiedVisitor
40implements   AttributeVisitor,
41             InstructionVisitor,
42             ExceptionInfoVisitor
43{
44    //*
45    private static final boolean DEBUG = false;
46    /*/
47    private static       boolean DEBUG = true;
48    //*/
49
50
51    private boolean[] evaluated  = new boolean[ClassConstants.TYPICAL_CODE_LENGTH];
52    private int[]     stackSizes = new int[ClassConstants.TYPICAL_CODE_LENGTH];
53
54    private boolean exitInstructionBlock;
55
56    private int stackSize;
57    private int maxStackSize;
58
59
60    /**
61     * Returns whether the instruction at the given offset is reachable in the
62     * most recently visited code attribute.
63     */
64    public boolean isReachable(int instructionOffset)
65    {
66        return evaluated[instructionOffset];
67    }
68
69
70    /**
71     * Returns the stack size at the given instruction offset of the most
72     * recently visited code attribute.
73     */
74    public int getStackSize(int instructionOffset)
75    {
76        if (!evaluated[instructionOffset])
77        {
78            throw new IllegalArgumentException("Unknown stack size at unreachable instruction offset ["+instructionOffset+"]");
79        }
80
81        return stackSizes[instructionOffset];
82    }
83
84
85    /**
86     * Returns the maximum stack size of the most recently visited code attribute.
87     */
88    public int getMaxStackSize()
89    {
90        return maxStackSize;
91    }
92
93
94    // Implementations for AttributeVisitor.
95
96    public void visitAnyAttribute(Clazz clazz, Attribute attribute) {}
97
98
99    public void visitCodeAttribute(Clazz clazz, Method method, CodeAttribute codeAttribute)
100    {
101//        DEBUG =
102//            clazz.getName().equals("abc/Def") &&
103//            method.getName(clazz).equals("abc");
104
105        // TODO: Remove this when the code has stabilized.
106        // Catch any unexpected exceptions from the actual visiting method.
107        try
108        {
109            // Process the code.
110            visitCodeAttribute0(clazz, method, codeAttribute);
111        }
112        catch (RuntimeException ex)
113        {
114            System.err.println("Unexpected error while computing stack sizes:");
115            System.err.println("  Class       = ["+clazz.getName()+"]");
116            System.err.println("  Method      = ["+method.getName(clazz)+method.getDescriptor(clazz)+"]");
117            System.err.println("  Exception   = ["+ex.getClass().getName()+"] ("+ex.getMessage()+")");
118
119            if (DEBUG)
120            {
121                method.accept(clazz, new ClassPrinter());
122            }
123
124            throw ex;
125        }
126    }
127
128
129    public void visitCodeAttribute0(Clazz clazz, Method method, CodeAttribute codeAttribute)
130    {
131        if (DEBUG)
132        {
133            System.out.println("StackSizeComputer: "+clazz.getName()+"."+method.getName(clazz)+method.getDescriptor(clazz));
134        }
135
136        // Try to reuse the previous array.
137        int codeLength = codeAttribute.u4codeLength;
138        if (evaluated.length < codeLength)
139        {
140            evaluated  = new boolean[codeLength];
141            stackSizes = new int[codeLength];
142        }
143        else
144        {
145            Arrays.fill(evaluated, 0, codeLength, false);
146        }
147
148        // The initial stack is always empty.
149        stackSize    = 0;
150        maxStackSize = 0;
151
152        // Evaluate the instruction block starting at the entry point of the method.
153        evaluateInstructionBlock(clazz, method, codeAttribute, 0);
154
155        // Evaluate the exception handlers.
156        codeAttribute.exceptionsAccept(clazz, method, this);
157    }
158
159
160    // Implementations for InstructionVisitor.
161
162    public void visitSimpleInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, SimpleInstruction simpleInstruction)
163    {
164        byte opcode = simpleInstruction.opcode;
165
166        // Some simple instructions exit from the current instruction block.
167        exitInstructionBlock =
168            opcode == InstructionConstants.OP_IRETURN ||
169            opcode == InstructionConstants.OP_LRETURN ||
170            opcode == InstructionConstants.OP_FRETURN ||
171            opcode == InstructionConstants.OP_DRETURN ||
172            opcode == InstructionConstants.OP_ARETURN ||
173            opcode == InstructionConstants.OP_RETURN  ||
174            opcode == InstructionConstants.OP_ATHROW;
175    }
176
177    public void visitConstantInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, ConstantInstruction constantInstruction)
178    {
179        // Constant pool instructions never end the current instruction block.
180        exitInstructionBlock = false;
181    }
182
183    public void visitVariableInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, VariableInstruction variableInstruction)
184    {
185        byte opcode = variableInstruction.opcode;
186
187        // The ret instruction end the current instruction block.
188        exitInstructionBlock =
189            opcode == InstructionConstants.OP_RET;
190    }
191
192    public void visitBranchInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, BranchInstruction branchInstruction)
193    {
194        byte opcode = branchInstruction.opcode;
195
196        // Evaluate the target instruction blocks.
197        evaluateInstructionBlock(clazz,
198                                 method,
199                                 codeAttribute,
200                                 offset +
201                                 branchInstruction.branchOffset);
202
203        // Evaluate the instructions after a subroutine branch.
204        if (opcode == InstructionConstants.OP_JSR ||
205            opcode == InstructionConstants.OP_JSR_W)
206        {
207            // We assume subroutine calls (jsr and jsr_w instructions) don't
208            // change the stack, other than popping the return value.
209            stackSize -= 1;
210
211            evaluateInstructionBlock(clazz,
212                                     method,
213                                     codeAttribute,
214                                     offset + branchInstruction.length(offset));
215        }
216
217        // Some branch instructions always end the current instruction block.
218        exitInstructionBlock =
219            opcode == InstructionConstants.OP_GOTO   ||
220            opcode == InstructionConstants.OP_GOTO_W ||
221            opcode == InstructionConstants.OP_JSR    ||
222            opcode == InstructionConstants.OP_JSR_W;
223    }
224
225
226    public void visitAnySwitchInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, SwitchInstruction switchInstruction)
227    {
228        // Evaluate the target instruction blocks.
229
230        // Loop over all jump offsets.
231        int[] jumpOffsets = switchInstruction.jumpOffsets;
232
233        for (int index = 0; index < jumpOffsets.length; index++)
234        {
235            // Evaluate the jump instruction block.
236            evaluateInstructionBlock(clazz,
237                                     method,
238                                     codeAttribute,
239                                     offset + jumpOffsets[index]);
240        }
241
242        // Also evaluate the default instruction block.
243        evaluateInstructionBlock(clazz,
244                                 method,
245                                 codeAttribute,
246                                 offset + switchInstruction.defaultOffset);
247
248        // The switch instruction always ends the current instruction block.
249        exitInstructionBlock = true;
250    }
251
252
253    // Implementations for ExceptionInfoVisitor.
254
255    public void visitExceptionInfo(Clazz clazz, Method method, CodeAttribute codeAttribute, ExceptionInfo exceptionInfo)
256    {
257        if (DEBUG)
258        {
259            System.out.println("Exception:");
260        }
261
262        // The stack size when entering the exception handler is always 1.
263        stackSize = 1;
264
265        // Evaluate the instruction block starting at the entry point of the
266        // exception handler.
267        evaluateInstructionBlock(clazz,
268                                 method,
269                                 codeAttribute,
270                                 exceptionInfo.u2handlerPC);
271    }
272
273
274    // Small utility methods.
275
276    /**
277     * Evaluates a block of instructions that hasn't been handled before,
278     * starting at the given offset and ending at a branch instruction, a return
279     * instruction, or a throw instruction. Branch instructions are handled
280     * recursively.
281     */
282    private void evaluateInstructionBlock(Clazz         clazz,
283                                          Method        method,
284                                          CodeAttribute codeAttribute,
285                                          int           instructionOffset)
286    {
287        if (DEBUG)
288        {
289            if (evaluated[instructionOffset])
290            {
291                System.out.println("-- (instruction block at "+instructionOffset+" already evaluated)");
292            }
293            else
294            {
295                System.out.println("-- instruction block:");
296            }
297        }
298
299        // Remember the initial stack size.
300        int initialStackSize = stackSize;
301
302        // Remember the maximum stack size.
303        if (maxStackSize < stackSize)
304        {
305            maxStackSize = stackSize;
306        }
307
308        // Evaluate any instructions that haven't been evaluated before.
309        while (!evaluated[instructionOffset])
310        {
311            // Mark the instruction as evaluated.
312            evaluated[instructionOffset] = true;
313
314            Instruction instruction = InstructionFactory.create(codeAttribute.code,
315                                                                instructionOffset);
316
317            if (DEBUG)
318            {
319                int stackPushCount = instruction.stackPushCount(clazz);
320                int stackPopCount  = instruction.stackPopCount(clazz);
321                System.out.println("["+instructionOffset+"]: "+
322                                   stackSize+" - "+
323                                   stackPopCount+" + "+
324                                   stackPushCount+" = "+
325                                   (stackSize+stackPushCount-stackPopCount)+": "+
326                                   instruction.toString(instructionOffset));
327            }
328
329            // Compute the instruction's effect on the stack size.
330            stackSize -= instruction.stackPopCount(clazz);
331
332            if (stackSize < 0)
333            {
334                throw new IllegalArgumentException("Stack size becomes negative after instruction "+
335                                                   instruction.toString(instructionOffset)+" in ["+
336                                                   clazz.getName()+"."+
337                                                   method.getName(clazz)+
338                                                   method.getDescriptor(clazz)+"]");
339            }
340
341            stackSizes[instructionOffset] =
342            stackSize += instruction.stackPushCount(clazz);
343
344            // Remember the maximum stack size.
345            if (maxStackSize < stackSize)
346            {
347                maxStackSize = stackSize;
348            }
349
350            // Remember the next instruction offset.
351            int nextInstructionOffset = instructionOffset +
352                                        instruction.length(instructionOffset);
353
354            // Visit the instruction, in order to handle branches.
355            instruction.accept(clazz, method, codeAttribute, instructionOffset, this);
356
357            // Stop evaluating after a branch.
358            if (exitInstructionBlock)
359            {
360                break;
361            }
362
363            // Continue with the next instruction.
364            instructionOffset = nextInstructionOffset;
365
366            if (DEBUG)
367            {
368                if (evaluated[instructionOffset])
369                {
370                    System.out.println("-- (instruction at "+instructionOffset+" already evaluated)");
371                }
372            }
373        }
374
375        // Restore the stack size for possible subsequent instruction blocks.
376        this.stackSize = initialStackSize;
377    }
378}
379