• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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  */
21 package proguard.classfile.attribute.visitor;
22 
23 import proguard.classfile.*;
24 import proguard.classfile.attribute.*;
25 import proguard.classfile.instruction.*;
26 import proguard.classfile.instruction.visitor.InstructionVisitor;
27 import proguard.classfile.util.SimplifiedVisitor;
28 import proguard.classfile.visitor.ClassPrinter;
29 
30 import 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  */
38 public class StackSizeComputer
39 extends      SimplifiedVisitor
40 implements   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      */
isReachable(int instructionOffset)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      */
getStackSize(int instructionOffset)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      */
getMaxStackSize()88     public int getMaxStackSize()
89     {
90         return maxStackSize;
91     }
92 
93 
94     // Implementations for AttributeVisitor.
95 
visitAnyAttribute(Clazz clazz, Attribute attribute)96     public void visitAnyAttribute(Clazz clazz, Attribute attribute) {}
97 
98 
visitCodeAttribute(Clazz clazz, Method method, CodeAttribute codeAttribute)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 
visitCodeAttribute0(Clazz clazz, Method method, CodeAttribute codeAttribute)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 
visitSimpleInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, SimpleInstruction simpleInstruction)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 
visitConstantInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, ConstantInstruction constantInstruction)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 
visitVariableInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, VariableInstruction variableInstruction)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 
visitBranchInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, BranchInstruction branchInstruction)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 
visitAnySwitchInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, SwitchInstruction switchInstruction)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 
visitExceptionInfo(Clazz clazz, Method method, CodeAttribute codeAttribute, ExceptionInfo exceptionInfo)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      */
evaluateInstructionBlock(Clazz clazz, Method method, CodeAttribute codeAttribute, int instructionOffset)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