TailRecursionSimplifier.java revision 8a6199f0c36a778f22394364347a301b0b28e94b
1/* 2 * ProGuard -- shrinking, optimization, obfuscation, and preverification 3 * of Java bytecode. 4 * 5 * Copyright (c) 2002-2013 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; 22 23import proguard.classfile.*; 24import proguard.classfile.attribute.*; 25import proguard.classfile.attribute.visitor.*; 26import proguard.classfile.constant.MethodrefConstant; 27import proguard.classfile.constant.visitor.ConstantVisitor; 28import proguard.classfile.editor.CodeAttributeComposer; 29import proguard.classfile.instruction.*; 30import proguard.classfile.instruction.visitor.InstructionVisitor; 31import proguard.classfile.util.*; 32 33/** 34 * This MemberVisitor simplifies tail recursion calls in all methods that it 35 * visits. 36 * 37 * @author Eric Lafortune 38 */ 39public class TailRecursionSimplifier 40extends SimplifiedVisitor 41implements AttributeVisitor, 42 InstructionVisitor, 43 ConstantVisitor, 44 ExceptionInfoVisitor 45{ 46 //* 47 private static final boolean DEBUG = false; 48 /*/ 49 private static boolean DEBUG = true; 50 //*/ 51 52 53 private final InstructionVisitor extraTailRecursionVisitor; 54 55 56 private final CodeAttributeComposer codeAttributeComposer = new CodeAttributeComposer(); 57 private final MyRecursionChecker recursionChecker = new MyRecursionChecker(); 58 59 private Method targetMethod; 60 private boolean inlinedAny; 61 62 63 64 /** 65 * Creates a new TailRecursionSimplifier. 66 */ 67 public TailRecursionSimplifier() 68 { 69 this(null); 70 } 71 72 73 /** 74 * Creates a new TailRecursionSimplifier with an extra visitor. 75 * @param extraTailRecursionVisitor an optional extra visitor for all 76 * simplified tail recursions. 77 */ 78 public TailRecursionSimplifier(InstructionVisitor extraTailRecursionVisitor) 79 { 80 this.extraTailRecursionVisitor = extraTailRecursionVisitor; 81 } 82 83 84 // Implementations for AttributeVisitor. 85 86 public void visitAnyAttribute(Clazz clazz, Attribute attribute) {} 87 88 89 public void visitCodeAttribute(Clazz clazz, Method method, CodeAttribute codeAttribute) 90 { 91 int accessFlags = method.getAccessFlags(); 92 93 if (// Only check the method if it is private, static, or final. 94 (accessFlags & (ClassConstants.INTERNAL_ACC_PRIVATE | 95 ClassConstants.INTERNAL_ACC_STATIC | 96 ClassConstants.INTERNAL_ACC_FINAL)) != 0 && 97 98 // Only check the method if it is not synchronized, etc. 99 (accessFlags & (ClassConstants.INTERNAL_ACC_SYNCHRONIZED | 100 ClassConstants.INTERNAL_ACC_NATIVE | 101 ClassConstants.INTERNAL_ACC_INTERFACE | 102 ClassConstants.INTERNAL_ACC_ABSTRACT)) == 0) 103 { 104// codeAttributeComposer.DEBUG = DEBUG = 105// clazz.getName().equals("abc/Def") && 106// method.getName(clazz).equals("abc"); 107 108 targetMethod = method; 109 inlinedAny = false; 110 codeAttributeComposer.reset(); 111 112 // The code may expand, due to expanding constant and variable 113 // instructions. 114 codeAttributeComposer.beginCodeFragment(codeAttribute.u4codeLength); 115 116 // Copy the instructions. 117 codeAttribute.instructionsAccept(clazz, method, this); 118 119 // Update the code attribute if any code has been inlined. 120 if (inlinedAny) 121 { 122 // Copy the exceptions. 123 codeAttribute.exceptionsAccept(clazz, method, this); 124 125 // Append a label just after the code. 126 codeAttributeComposer.appendLabel(codeAttribute.u4codeLength); 127 128 codeAttributeComposer.endCodeFragment(); 129 130 codeAttributeComposer.visitCodeAttribute(clazz, method, codeAttribute); 131 } 132 } 133 } 134 135 136 // Implementations for InstructionVisitor. 137 138 public void visitAnyInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, Instruction instruction) 139 { 140 // Copy the instruction. 141 codeAttributeComposer.appendInstruction(offset, instruction); 142 } 143 144 145 public void visitConstantInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, ConstantInstruction constantInstruction) 146 { 147 // Is it a method invocation? 148 switch (constantInstruction.opcode) 149 { 150 case InstructionConstants.OP_INVOKEVIRTUAL: 151 case InstructionConstants.OP_INVOKESPECIAL: 152 case InstructionConstants.OP_INVOKESTATIC: 153 { 154 // Is it a recursive call? 155 clazz.constantPoolEntryAccept(constantInstruction.constantIndex, recursionChecker); 156 157 if (recursionChecker.isRecursive()) 158 { 159 // Is the next instruction a return? 160 int nextOffset = 161 offset + constantInstruction.length(offset); 162 163 Instruction nextInstruction = 164 InstructionFactory.create(codeAttribute.code, nextOffset); 165 166 switch (nextInstruction.opcode) 167 { 168 case InstructionConstants.OP_IRETURN: 169 case InstructionConstants.OP_LRETURN: 170 case InstructionConstants.OP_FRETURN: 171 case InstructionConstants.OP_DRETURN: 172 case InstructionConstants.OP_ARETURN: 173 case InstructionConstants.OP_RETURN: 174 { 175 // Isn't the recursive call inside a try/catch block? 176 codeAttribute.exceptionsAccept(clazz, method, offset, recursionChecker); 177 178 if (recursionChecker.isRecursive()) 179 { 180 if (DEBUG) 181 { 182 System.out.println("TailRecursionSimplifier: ["+ 183 clazz.getName()+"."+method.getName(clazz)+method.getDescriptor(clazz)+"], inlining "+constantInstruction.toString(offset)); 184 } 185 186 // Append a label. 187 codeAttributeComposer.appendLabel(offset); 188 189 storeParameters(clazz, method); 190 191 // Branch back to the start of the method. 192 int gotoOffset = offset + 1; 193 codeAttributeComposer.appendInstruction(gotoOffset, 194 new BranchInstruction(InstructionConstants.OP_GOTO, -gotoOffset)); 195 196 // The original return instruction will be 197 // removed elsewhere, if possible. 198 199 // Remember that the code has changed. 200 inlinedAny = true; 201 202 if (extraTailRecursionVisitor != null) 203 { 204 extraTailRecursionVisitor.visitConstantInstruction(clazz, method, codeAttribute, offset, constantInstruction); 205 } 206 207 // The invocation itself is no longer necessary. 208 return; 209 } 210 } 211 } 212 } 213 214 break; 215 } 216 } 217 218 // Copy the instruction. 219 codeAttributeComposer.appendInstruction(offset, constantInstruction); 220 } 221 222 223 // Implementations for ExceptionInfoVisitor. 224 225 public void visitExceptionInfo(Clazz clazz, Method method, CodeAttribute codeAttribute, ExceptionInfo exceptionInfo) 226 { 227 codeAttributeComposer.appendException(new ExceptionInfo(exceptionInfo.u2startPC, 228 exceptionInfo.u2endPC, 229 exceptionInfo.u2handlerPC, 230 exceptionInfo.u2catchType)); 231 } 232 233 234 /** 235 * This ConstantVisitor and ExceptionInfoVisitor returns whether a method 236 * invocation can be treated as tail-recursive. 237 */ 238 private class MyRecursionChecker 239 extends SimplifiedVisitor 240 implements ConstantVisitor, 241 ExceptionInfoVisitor 242 { 243 private boolean recursive; 244 245 246 /** 247 * Returns whether the method invocation can be treated as 248 * tail-recursive. 249 */ 250 public boolean isRecursive() 251 { 252 return recursive; 253 } 254 255 // Implementations for ConstantVisitor. 256 257 public void visitMethodrefConstant(Clazz clazz, MethodrefConstant methodrefConstant) 258 { 259 recursive = targetMethod.equals(methodrefConstant.referencedMember); 260 } 261 262 263 // Implementations for ExceptionInfoVisitor. 264 265 public void visitExceptionInfo(Clazz clazz, Method method, CodeAttribute codeAttribute, ExceptionInfo exceptionInfo) 266 { 267 recursive = false; 268 } 269 } 270 271 272 // Small utility methods. 273 274 /** 275 * Appends instructions to pop the parameters for the given method, storing 276 * them in new local variables. 277 */ 278 private void storeParameters(Clazz clazz, Method method) 279 { 280 String descriptor = method.getDescriptor(clazz); 281 282 boolean isStatic = 283 (method.getAccessFlags() & ClassConstants.INTERNAL_ACC_STATIC) != 0; 284 285 // Count the number of parameters, taking into account their categories. 286 int parameterSize = ClassUtil.internalMethodParameterSize(descriptor); 287 int parameterOffset = isStatic ? 0 : 1; 288 289 // Store the parameter types. 290 String[] parameterTypes = new String[parameterSize]; 291 292 InternalTypeEnumeration internalTypeEnumeration = 293 new InternalTypeEnumeration(descriptor); 294 295 for (int parameterIndex = 0; parameterIndex < parameterSize; parameterIndex++) 296 { 297 String parameterType = internalTypeEnumeration.nextType(); 298 parameterTypes[parameterIndex] = parameterType; 299 if (ClassUtil.internalTypeSize(parameterType) == 2) 300 { 301 parameterIndex++; 302 } 303 } 304 305 codeAttributeComposer.beginCodeFragment(parameterSize + 1); 306 307 // Go over the parameter types backward, storing the stack entries 308 // in their corresponding variables. 309 for (int parameterIndex = parameterSize-1; parameterIndex >= 0; parameterIndex--) 310 { 311 String parameterType = parameterTypes[parameterIndex]; 312 if (parameterType != null) 313 { 314 byte opcode; 315 switch (parameterType.charAt(0)) 316 { 317 case ClassConstants.INTERNAL_TYPE_BOOLEAN: 318 case ClassConstants.INTERNAL_TYPE_BYTE: 319 case ClassConstants.INTERNAL_TYPE_CHAR: 320 case ClassConstants.INTERNAL_TYPE_SHORT: 321 case ClassConstants.INTERNAL_TYPE_INT: 322 opcode = InstructionConstants.OP_ISTORE; 323 break; 324 325 case ClassConstants.INTERNAL_TYPE_LONG: 326 opcode = InstructionConstants.OP_LSTORE; 327 break; 328 329 case ClassConstants.INTERNAL_TYPE_FLOAT: 330 opcode = InstructionConstants.OP_FSTORE; 331 break; 332 333 case ClassConstants.INTERNAL_TYPE_DOUBLE: 334 opcode = InstructionConstants.OP_DSTORE; 335 break; 336 337 default: 338 opcode = InstructionConstants.OP_ASTORE; 339 break; 340 } 341 342 codeAttributeComposer.appendInstruction(parameterSize-parameterIndex-1, 343 new VariableInstruction(opcode, parameterOffset + parameterIndex)); 344 } 345 } 346 347 // Put the 'this' reference in variable 0. 348 if (!isStatic) 349 { 350 codeAttributeComposer.appendInstruction(parameterSize, 351 new VariableInstruction(InstructionConstants.OP_ASTORE, 0)); 352 } 353 354 codeAttributeComposer.endCodeFragment(); 355 } 356}