1 /* 2 * ProGuard -- shrinking, optimization, obfuscation, and preverification 3 * of Java bytecode. 4 * 5 * Copyright (c) 2002-2009 Eric Lafortune (eric (at) 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.peephole; 22 23 import proguard.classfile.*; 24 import proguard.classfile.attribute.*; 25 import proguard.classfile.attribute.visitor.AttributeVisitor; 26 import proguard.classfile.editor.CodeAttributeEditor; 27 import proguard.classfile.instruction.*; 28 import proguard.classfile.instruction.visitor.InstructionVisitor; 29 import proguard.classfile.util.SimplifiedVisitor; 30 31 /** 32 * This AttributeVisitor redirects unconditional branches so any common code 33 * is shared, and the code preceding the branch can be removed, in the code 34 * attributes that it visits. 35 * 36 * @author Eric Lafortune 37 */ 38 public class GotoCommonCodeReplacer 39 extends SimplifiedVisitor 40 implements AttributeVisitor, 41 InstructionVisitor 42 { 43 //* 44 private static final boolean DEBUG = false; 45 /*/ 46 private static boolean DEBUG = true; 47 //*/ 48 49 50 private final InstructionVisitor extraInstructionVisitor; 51 52 private final BranchTargetFinder branchTargetFinder = new BranchTargetFinder(); 53 private final CodeAttributeEditor codeAttributeEditor = new CodeAttributeEditor(); 54 55 56 /** 57 * Creates a new GotoCommonCodeReplacer. 58 * @param extraInstructionVisitor an optional extra visitor for all replaced 59 * goto instructions. 60 */ 61 public GotoCommonCodeReplacer(InstructionVisitor extraInstructionVisitor) 62 { 63 this.extraInstructionVisitor = extraInstructionVisitor; 64 } 65 66 67 // Implementations for AttributeVisitor. 68 69 public void visitAnyAttribute(Clazz clazz, Attribute attribute) {} 70 71 72 public void visitCodeAttribute(Clazz clazz, Method method, CodeAttribute codeAttribute) 73 { 74 // DEBUG = 75 // clazz.getName().equals("abc/Def") && 76 // method.getName(clazz).equals("abc"); 77 78 // Mark all branch targets. 79 branchTargetFinder.visitCodeAttribute(clazz, method, codeAttribute); 80 81 // Reset the code attribute editor. 82 codeAttributeEditor.reset(codeAttribute.u4codeLength); 83 84 // Remap the variables of the instructions. 85 codeAttribute.instructionsAccept(clazz, method, this); 86 87 // Apply the code atribute editor. 88 codeAttributeEditor.visitCodeAttribute(clazz, method, codeAttribute); 89 } 90 91 92 // Implementations for InstructionVisitor. 93 94 public void visitAnyInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, Instruction instruction) {} 95 96 97 public void visitBranchInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, BranchInstruction branchInstruction) 98 { 99 // Check if the instruction is an unconditional goto instruction that 100 // isn't the target of a branch itself. 101 byte opcode = branchInstruction.opcode; 102 if ((opcode == InstructionConstants.OP_GOTO || 103 opcode == InstructionConstants.OP_GOTO_W) && 104 !branchTargetFinder.isBranchTarget(offset)) 105 { 106 int branchOffset = branchInstruction.branchOffset; 107 int targetOffset = offset + branchOffset; 108 109 // Get the number of common bytes. 110 int commonCount = commonByteCodeCount(codeAttribute, offset, targetOffset); 111 112 if (commonCount > 0 && 113 !exceptionBoundary(codeAttribute, offset, targetOffset)) 114 { 115 if (DEBUG) 116 { 117 System.out.println("GotoCommonCodeReplacer: "+clazz.getName()+"."+method.getName(clazz)+" (["+(offset-commonCount)+"] - "+branchInstruction.toString(offset)+" -> "+targetOffset+")"); 118 } 119 120 // Delete the common instructions. 121 for (int delta = 0; delta <= commonCount; delta++) 122 { 123 int deleteOffset = offset - delta; 124 if (branchTargetFinder.isInstruction(deleteOffset)) 125 { 126 codeAttributeEditor.replaceInstruction( deleteOffset, (Instruction)null); 127 codeAttributeEditor.insertBeforeInstruction(deleteOffset, (Instruction)null); 128 codeAttributeEditor.insertAfterInstruction( deleteOffset, (Instruction)null); 129 130 codeAttributeEditor.deleteInstruction(deleteOffset); 131 } 132 } 133 134 // Redirect the goto instruction, if it is still necessary. 135 int newBranchOffset = branchOffset - commonCount; 136 if (newBranchOffset != branchInstruction.length(offset)) 137 { 138 Instruction newGotoInstruction = 139 new BranchInstruction(opcode, newBranchOffset); 140 codeAttributeEditor.replaceInstruction(offset, 141 newGotoInstruction); 142 } 143 144 // Visit the instruction, if required. 145 if (extraInstructionVisitor != null) 146 { 147 extraInstructionVisitor.visitBranchInstruction(clazz, method, codeAttribute, offset, branchInstruction); 148 } 149 } 150 } 151 } 152 153 154 // Small utility methods. 155 156 /** 157 * Returns the number of common bytes preceding the given offsets, 158 * avoiding branches and exception blocks. 159 */ 160 private int commonByteCodeCount(CodeAttribute codeAttribute, int offset1, int offset2) 161 { 162 // Find the block of common instructions preceding it. 163 byte[] code = codeAttribute.code; 164 165 int successfulDelta = 0; 166 167 for (int delta = 1; 168 delta <= offset1 && 169 delta <= offset2 && 170 offset2 - delta != offset1; 171 delta++) 172 { 173 int newOffset1 = offset1 - delta; 174 int newOffset2 = offset2 - delta; 175 176 // Is the code identical at both offsets? 177 if (code[newOffset1] != code[newOffset2]) 178 { 179 break; 180 } 181 182 // Are there instructions at either offset but not both? 183 if (branchTargetFinder.isInstruction(newOffset1) ^ 184 branchTargetFinder.isInstruction(newOffset2)) 185 { 186 break; 187 } 188 189 // Are there instructions at both offsets? 190 if (branchTargetFinder.isInstruction(newOffset1) && 191 branchTargetFinder.isInstruction(newOffset2)) 192 { 193 // Are the offsets involved in some branches? 194 // Note that the preverifier doesn't like initializer 195 // invocations to be moved around. 196 // Also note that the preverifier doesn't like pop instructions 197 // that work on different operands. 198 if (branchTargetFinder.isBranchOrigin(newOffset1) || 199 branchTargetFinder.isBranchTarget(newOffset1) || 200 branchTargetFinder.isExceptionStart(newOffset1) || 201 branchTargetFinder.isExceptionEnd(newOffset1) || 202 branchTargetFinder.isInitializer(newOffset1) || 203 branchTargetFinder.isExceptionStart(newOffset2) || 204 branchTargetFinder.isExceptionEnd(newOffset2) || 205 isPop(code[newOffset1])) 206 { 207 break; 208 } 209 210 // Make sure the new branch target was a branch target before, 211 // in order not to introduce new entries in the stack map table. 212 if (branchTargetFinder.isBranchTarget(newOffset2)) 213 { 214 successfulDelta = delta; 215 } 216 217 if (branchTargetFinder.isBranchTarget(newOffset1)) 218 { 219 break; 220 } 221 } 222 } 223 224 return successfulDelta; 225 } 226 227 228 /** 229 * Returns whether the given opcode represents a pop instruction that must 230 * get a consistent type (pop, pop2, arraylength). 231 */ 232 private boolean isPop(byte opcode) 233 { 234 return opcode == InstructionConstants.OP_POP || 235 opcode == InstructionConstants.OP_POP2 || 236 opcode == InstructionConstants.OP_ARRAYLENGTH; 237 } 238 239 240 /** 241 * Returns the whether there is a boundary of an exception block between 242 * the given offsets (including both). 243 */ 244 private boolean exceptionBoundary(CodeAttribute codeAttribute, int offset1, int offset2) 245 { 246 // Swap the offsets if the second one is smaller than the first one. 247 if (offset2 < offset1) 248 { 249 int offset = offset1; 250 offset1 = offset2; 251 offset2 = offset; 252 } 253 254 // Check if there is a boundary of an exception block. 255 for (int offset = offset1; offset <= offset2; offset++) 256 { 257 if (branchTargetFinder.isExceptionStart(offset) || 258 branchTargetFinder.isExceptionEnd(offset)) 259 { 260 return true; 261 } 262 } 263 264 return false; 265 } 266 } 267