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