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