diff options
Diffstat (limited to 'src/proguard/optimize/peephole/BranchTargetFinder.java')
| -rw-r--r-- | src/proguard/optimize/peephole/BranchTargetFinder.java | 761 |
1 files changed, 0 insertions, 761 deletions
diff --git a/src/proguard/optimize/peephole/BranchTargetFinder.java b/src/proguard/optimize/peephole/BranchTargetFinder.java deleted file mode 100644 index 507c1f8..0000000 --- a/src/proguard/optimize/peephole/BranchTargetFinder.java +++ /dev/null @@ -1,761 +0,0 @@ -/* - * ProGuard -- shrinking, optimization, obfuscation, and preverification - * of Java bytecode. - * - * Copyright (c) 2002-2014 Eric Lafortune (eric@graphics.cornell.edu) - * - * This program is free software; you can redistribute it and/or modify it - * under the terms of the GNU General Public License as published by the Free - * Software Foundation; either version 2 of the License, or (at your option) - * any later version. - * - * This program is distributed in the hope that it will be useful, but WITHOUT - * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or - * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for - * more details. - * - * You should have received a copy of the GNU General Public License along - * with this program; if not, write to the Free Software Foundation, Inc., - * 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA - */ -package proguard.optimize.peephole; - -import proguard.classfile.*; -import proguard.classfile.attribute.*; -import proguard.classfile.attribute.visitor.*; -import proguard.classfile.constant.*; -import proguard.classfile.constant.visitor.ConstantVisitor; -import proguard.classfile.instruction.*; -import proguard.classfile.instruction.visitor.InstructionVisitor; -import proguard.classfile.util.SimplifiedVisitor; - -import java.util.Arrays; - -/** - * This AttributeVisitor finds all instruction offsets, branch targets, and - * exception targets in the CodeAttribute objects that it visits. - * - * @author Eric Lafortune - */ -public class BranchTargetFinder -extends SimplifiedVisitor -implements AttributeVisitor, - InstructionVisitor, - ExceptionInfoVisitor, - ConstantVisitor -{ - //* - private static final boolean DEBUG = false; - /*/ - private static boolean DEBUG = System.getProperty("btf") != null; - //*/ - - public static final int NONE = -1; - - // We'll explicitly mark instructions that are not part of a subroutine, - // with NO_SUBROUTINE. Subroutines may just branch back into normal code - // (e.g. due to a break instruction in Java code), and we want to avoid - // marking such normal code as subroutine. The first mark wins, so we're - // assuming that such code is marked as normal code before it is marked - // as subroutine. - public static final int UNKNOWN = -1; - public static final int NO_SUBROUTINE = -2; - - private static final short INSTRUCTION = 1 << 0; - private static final short BRANCH_ORIGIN = 1 << 1; - private static final short BRANCH_TARGET = 1 << 2; - private static final short AFTER_BRANCH = 1 << 3; - private static final short EXCEPTION_START = 1 << 4; - private static final short EXCEPTION_END = 1 << 5; - private static final short EXCEPTION_HANDLER = 1 << 6; - private static final short SUBROUTINE_INVOCATION = 1 << 7; - private static final short SUBROUTINE_RETURNING = 1 << 8; - - private static final int MAXIMUM_CREATION_OFFSETS = 32; - - - private short[] instructionMarks = new short[ClassConstants.TYPICAL_CODE_LENGTH + 1]; - private int[] subroutineStarts = new int[ClassConstants.TYPICAL_CODE_LENGTH]; - private int[] subroutineEnds = new int[ClassConstants.TYPICAL_CODE_LENGTH]; - private int[] creationOffsets = new int[ClassConstants.TYPICAL_CODE_LENGTH]; - private int[] initializationOffsets = new int[ClassConstants.TYPICAL_CODE_LENGTH]; - private int superInitializationOffset; - private boolean containsSubroutines; - - private boolean repeat; - private int currentSubroutineStart; - private int[] recentCreationOffsets = new int[MAXIMUM_CREATION_OFFSETS]; - private int recentCreationOffsetIndex; - private boolean isInitializer; - - - /** - * Returns whether there is an instruction at the given offset in the - * CodeAttribute that was visited most recently. - */ - public boolean isInstruction(int offset) - { - return (instructionMarks[offset] & INSTRUCTION) != 0; - } - - - /** - * Returns whether the instruction at the given offset is the target of - * any kind in the CodeAttribute that was visited most recently. - */ - public boolean isTarget(int offset) - { - return offset == 0 || - (instructionMarks[offset] & (BRANCH_TARGET | - EXCEPTION_START | - EXCEPTION_END | - EXCEPTION_HANDLER)) != 0; - } - - - /** - * Returns whether the instruction at the given offset is the origin of a - * branch instruction in the CodeAttribute that was visited most recently. - */ - public boolean isBranchOrigin(int offset) - { - return (instructionMarks[offset] & BRANCH_ORIGIN) != 0; - } - - - /** - * Returns whether the instruction at the given offset is the target of a - * branch instruction in the CodeAttribute that was visited most recently. - */ - public boolean isBranchTarget(int offset) - { - return (instructionMarks[offset] & BRANCH_TARGET) != 0; - } - - - /** - * Returns whether the instruction at the given offset comes right after a - * definite branch instruction in the CodeAttribute that was visited most - * recently. - */ - public boolean isAfterBranch(int offset) - { - return (instructionMarks[offset] & AFTER_BRANCH) != 0; - } - - - /** - * Returns whether the instruction at the given offset is the start of an - * exception try block in the CodeAttribute that was visited most recently. - */ - public boolean isExceptionStart(int offset) - { - return (instructionMarks[offset] & EXCEPTION_START) != 0; - } - - - /** - * Returns whether the instruction at the given offset is the end of an - * exception try block in the CodeAttribute that was visited most recently. - */ - public boolean isExceptionEnd(int offset) - { - return (instructionMarks[offset] & EXCEPTION_END) != 0; - } - - - /** - * Returns whether the instruction at the given offset is the start of an - * exception catch block in the CodeAttribute that was visited most recently. - */ - public boolean isExceptionHandler(int offset) - { - return (instructionMarks[offset] & EXCEPTION_HANDLER) != 0; - } - - - /** - * Returns whether the instruction at the given offset is a subroutine - * invocation in the CodeAttribute that was visited most recently. - */ - public boolean isSubroutineInvocation(int offset) - { - return (instructionMarks[offset] & SUBROUTINE_INVOCATION) != 0; - } - - - /** - * Returns whether the instruction at the given offset is the start of a - * subroutine in the CodeAttribute that was visited most recently. - */ - public boolean isSubroutineStart(int offset) - { - return subroutineStarts[offset] == offset; - } - - - /** - * Returns whether the instruction at the given offset is part of a - * subroutine in the CodeAttribute that was visited most recently. - */ - public boolean isSubroutine(int offset) - { - return subroutineStarts[offset] >= 0; - } - - - /** - * Returns whether the subroutine at the given offset is ever returning - * by means of a regular 'ret' instruction. - */ - public boolean isSubroutineReturning(int offset) - { - return (instructionMarks[offset] & SUBROUTINE_RETURNING) != 0; - } - - - /** - * Returns the start offset of the subroutine at the given offset, in the - * CodeAttribute that was visited most recently. - */ - public int subroutineStart(int offset) - { - return subroutineStarts[offset]; - } - - - /** - * Returns the offset after the subroutine at the given offset, in the - * CodeAttribute that was visited most recently. - */ - public int subroutineEnd(int offset) - { - return subroutineEnds[offset]; - } - - - /** - * Returns whether the instruction at the given offset is a 'new' - * instruction, in the CodeAttribute that was visited most recently. - */ - public boolean isNew(int offset) - { - return initializationOffsets[offset] != NONE; - } - - - /** - * Returns the instruction offset at which the object instance that is - * created at the given 'new' instruction offset is initialized, or - * <code>NONE</code> if it is not being created. - */ - public int initializationOffset(int offset) - { - return initializationOffsets[offset]; - } - - - /** - * Returns whether the method is an instance initializer, in the - * CodeAttribute that was visited most recently. - */ - public boolean isInitializer() - { - return superInitializationOffset != NONE; - } - - - /** - * Returns the instruction offset at which this initializer is calling - * the "super" or "this" initializer method, or <code>NONE</code> if it is - * not an initializer. - */ - public int superInitializationOffset() - { - return superInitializationOffset; - } - - - /** - * Returns whether the instruction at the given offset is the special - * invocation of an instance initializer, in the CodeAttribute that was - * visited most recently. - */ - public boolean isInitializer(int offset) - { - return creationOffsets[offset] != NONE; - } - - - /** - * Returns the offset of the 'new' instruction that corresponds to the - * invocation of the instance initializer at the given offset, or - * <code>AT_METHOD_ENTRY</code> if the invocation is calling the "super" or - * "this" initializer method, , or <code>NONE</code> if it is not a 'new' - * instruction. - */ - public int creationOffset(int offset) - { - return creationOffsets[offset]; - } - - - /** - * Returns whether the method contains subroutines, in the CodeAttribute - * that was visited most recently. - */ - public boolean containsSubroutines() - { - return containsSubroutines; - } - - - // Implementations for AttributeVisitor. - - public void visitAnyAttribute(Clazz clazz, Attribute attribute) {} - - - public void visitCodeAttribute(Clazz clazz, Method method, CodeAttribute codeAttribute) - { -// DEBUG = -// clazz.getName().equals("abc/Def") && -// method.getName(clazz).equals("abc"); - - // Make sure there are sufficiently large arrays. - int codeLength = codeAttribute.u4codeLength; - if (subroutineStarts.length < codeLength) - { - // Create new arrays. - instructionMarks = new short[codeLength + 1]; - subroutineStarts = new int[codeLength]; - subroutineEnds = new int[codeLength]; - creationOffsets = new int[codeLength]; - initializationOffsets = new int[codeLength]; - - // Reset the arrays. - Arrays.fill(subroutineStarts, 0, codeLength, UNKNOWN); - Arrays.fill(subroutineEnds, 0, codeLength, UNKNOWN); - Arrays.fill(creationOffsets, 0, codeLength, NONE); - Arrays.fill(initializationOffsets, 0, codeLength, NONE); - } - else - { - // Reset the arrays. - Arrays.fill(instructionMarks, 0, codeLength, (short)0); - Arrays.fill(subroutineStarts, 0, codeLength, UNKNOWN); - Arrays.fill(subroutineEnds, 0, codeLength, UNKNOWN); - Arrays.fill(creationOffsets, 0, codeLength, NONE); - Arrays.fill(initializationOffsets, 0, codeLength, NONE); - - instructionMarks[codeLength] = 0; - } - - superInitializationOffset = NONE; - containsSubroutines = false; - - // Iterate until all subroutines have been fully marked. - do - { - repeat = false; - currentSubroutineStart = NO_SUBROUTINE; - recentCreationOffsetIndex = 0; - - // Mark branch targets by going over all instructions. - codeAttribute.instructionsAccept(clazz, method, this); - - // Mark branch targets in the exception table. - codeAttribute.exceptionsAccept(clazz, method, this); - } - while (repeat); - - // The end of the code is a branch target sentinel. - instructionMarks[codeLength] = BRANCH_TARGET; - - if (containsSubroutines) - { - // Set the subroutine returning flag and the subroutine end at each - // subroutine start. - int previousSubroutineStart = NO_SUBROUTINE; - - for (int offset = 0; offset < codeLength; offset++) - { - if (isInstruction(offset)) - { - int subroutineStart = subroutineStarts[offset]; - - if (subroutineStart >= 0 && - isSubroutineReturning(offset)) - { - instructionMarks[subroutineStart] |= SUBROUTINE_RETURNING; - } - - if (previousSubroutineStart >= 0) - { - subroutineEnds[previousSubroutineStart] = offset; - } - - previousSubroutineStart = subroutineStart; - } - } - - if (previousSubroutineStart >= 0) - { - subroutineEnds[previousSubroutineStart] = codeLength; - } - - // Set the subroutine returning flag and the subroutine end at each - // subroutine instruction, based on the marks at the subroutine - // start. - for (int offset = 0; offset < codeLength; offset++) - { - if (isSubroutine(offset)) - { - int subroutineStart = subroutineStarts[offset]; - - if (isSubroutineReturning(subroutineStart)) - { - instructionMarks[offset] |= SUBROUTINE_RETURNING; - } - - subroutineEnds[offset] = subroutineEnds[subroutineStart]; - } - } - } - - if (DEBUG) - { - System.out.println(); - System.out.println("Branch targets: "+clazz.getName()+"."+method.getName(clazz)+method.getDescriptor(clazz)); - - for (int index = 0; index < codeLength; index++) - { - if (isInstruction(index)) - { - System.out.println("" + - (isBranchOrigin(index) ? 'B' : '-') + - (isAfterBranch(index) ? 'b' : '-') + - (isBranchTarget(index) ? 'T' : '-') + - (isExceptionStart(index) ? 'E' : '-') + - (isExceptionEnd(index) ? 'e' : '-') + - (isExceptionHandler(index) ? 'H' : '-') + - (isSubroutineInvocation(index) ? 'J' : '-') + - (isSubroutineStart(index) ? 'S' : '-') + - (isSubroutineReturning(index) ? 'r' : '-') + - (isSubroutine(index) ? " ["+subroutineStart(index)+" -> "+subroutineEnd(index)+"]" : "") + - (isNew(index) ? " ["+initializationOffset(index)+"] " : " ---- ") + - InstructionFactory.create(codeAttribute.code, index).toString(index)); - } - } - } - } - - - // Implementations for InstructionVisitor. - - public void visitSimpleInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, SimpleInstruction simpleInstruction) - { - // Mark the instruction. - instructionMarks[offset] |= INSTRUCTION; - - // Check if this is an instruction of a subroutine. - checkSubroutine(offset); - - byte opcode = simpleInstruction.opcode; - if (opcode == InstructionConstants.OP_IRETURN || - opcode == InstructionConstants.OP_LRETURN || - opcode == InstructionConstants.OP_FRETURN || - opcode == InstructionConstants.OP_DRETURN || - opcode == InstructionConstants.OP_ARETURN || - opcode == InstructionConstants.OP_ATHROW) - { - // Mark the branch origin. - markBranchOrigin(offset); - - // Mark the next instruction. - markAfterBranchOrigin(offset + simpleInstruction.length(offset)); - } - } - - - public void visitConstantInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, ConstantInstruction constantInstruction) - { - // Mark the instruction. - instructionMarks[offset] |= INSTRUCTION; - - // Check if this is an instruction of a subroutine. - checkSubroutine(offset); - - byte opcode = constantInstruction.opcode; - if (opcode == InstructionConstants.OP_NEW) - { - // Push the 'new' instruction offset on the stack. - recentCreationOffsets[recentCreationOffsetIndex++] = offset; - } - else if (opcode == InstructionConstants.OP_INVOKESPECIAL) - { - // Is it calling an instance initializer? - isInitializer = false; - clazz.constantPoolEntryAccept(constantInstruction.constantIndex, this); - if (isInitializer) - { - // Do we have any 'new' instruction offsets on the stack? - if (recentCreationOffsetIndex > 0) - { - // Pop the 'new' instruction offset from the stack. - int recentCreationOffset = recentCreationOffsets[--recentCreationOffsetIndex]; - - // Link the creation offset and the initialization offset. - // TODO: There could be multiple initialization offsets. - creationOffsets[offset] = recentCreationOffset; - - initializationOffsets[recentCreationOffset] = offset; - } - else - { - // Remember the super initialization offset. - // TODO: There could be multiple initialization offsets. - // For instance, in the constructor of the generated class - // groovy.inspect.swingui.GeneratedBytecodeAwareGroovyClassLoader - // in groovy-all-2.2.1.jar. - superInitializationOffset = offset; - } - } - } - } - - - public void visitVariableInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, VariableInstruction variableInstruction) - { - // Mark the instruction. - instructionMarks[offset] |= INSTRUCTION; - - // Check if this is an instruction of a subroutine. - checkSubroutine(offset); - - if (variableInstruction.opcode == InstructionConstants.OP_RET) - { - // Mark the method. - containsSubroutines = true; - - // Mark the branch origin. - markBranchOrigin(offset); - - // Mark the subroutine return at its return instruction. - instructionMarks[offset] |= SUBROUTINE_RETURNING; - - // Mark the next instruction. - markAfterBranchOrigin(offset + variableInstruction.length(offset)); - } - } - - - public void visitBranchInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, BranchInstruction branchInstruction) - { - int branchOffset = branchInstruction.branchOffset; - int targetOffset = offset + branchOffset; - - // Mark the branch origin. - markBranchOrigin(offset); - - // Check if this is an instruction of a subroutine. - checkSubroutine(offset); - - // Mark the branch target. - markBranchTarget(offset, branchOffset); - - byte opcode = branchInstruction.opcode; - if (opcode == InstructionConstants.OP_JSR || - opcode == InstructionConstants.OP_JSR_W) - { - // Mark the method. - containsSubroutines = true; - - // Mark the subroutine invocation. - instructionMarks[offset] |= SUBROUTINE_INVOCATION; - - // Mark the new subroutine start. - markBranchSubroutineStart(offset, branchOffset, targetOffset); - } - else if (currentSubroutineStart != UNKNOWN) - { - // Mark the continued subroutine start. - markBranchSubroutineStart(offset, branchOffset, currentSubroutineStart); - } - - if (opcode == InstructionConstants.OP_GOTO || - opcode == InstructionConstants.OP_GOTO_W) - { - // Mark the next instruction. - markAfterBranchOrigin(offset + branchInstruction.length(offset)); - } - } - - - public void visitAnySwitchInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, SwitchInstruction switchInstruction) - { - // Mark the branch origin. - markBranchOrigin(offset); - - // Check if this is an instruction of a subroutine. - checkSubroutine(offset); - - // Mark the branch targets of the default jump offset. - markBranch(offset, switchInstruction.defaultOffset); - - // Mark the branch targets of the jump offsets. - markBranches(offset, switchInstruction.jumpOffsets); - - // Mark the next instruction. - markAfterBranchOrigin(offset + switchInstruction.length(offset)); - } - - - // Implementations for ConstantVisitor. - - public void visitAnyConstant(Clazz clazz, Constant constant) {} - - - public void visitMethodrefConstant(Clazz clazz, MethodrefConstant methodrefConstant) - { - // Remember whether the method is an initializer. - isInitializer = methodrefConstant.getName(clazz).equals(ClassConstants.METHOD_NAME_INIT); - } - - - // Implementations for ExceptionInfoVisitor. - - public void visitExceptionInfo(Clazz clazz, Method method, CodeAttribute codeAttribute, ExceptionInfo exceptionInfo) - { - int startPC = exceptionInfo.u2startPC; - int endPC = exceptionInfo.u2endPC; - int handlerPC = exceptionInfo.u2handlerPC; - - // Mark the exception offsets. - instructionMarks[startPC] |= EXCEPTION_START; - instructionMarks[endPC] |= EXCEPTION_END; - instructionMarks[handlerPC] |= EXCEPTION_HANDLER; - - // Mark the handler as part of a subroutine if necessary. - if (subroutineStarts[handlerPC] == UNKNOWN && - subroutineStarts[startPC] != UNKNOWN) - { - subroutineStarts[handlerPC] = subroutineStarts[startPC]; - - // We'll have to go over all instructions again. - repeat = true; - } - } - - - // Small utility methods. - - /** - * Marks the branch targets and their subroutine starts at the given - * offsets. - */ - private void markBranches(int offset, int[] jumpOffsets) - { - for (int index = 0; index < jumpOffsets.length; index++) - { - markBranch(offset, jumpOffsets[index]); - } - } - - - /** - * Marks the branch target and its subroutine start at the given offset. - */ - private void markBranch(int offset, int jumpOffset) - { - markBranchTarget(offset, jumpOffset); - - if (currentSubroutineStart != UNKNOWN) - { - markBranchSubroutineStart(offset, jumpOffset, currentSubroutineStart); - } - } - - /** - * Marks the branch origin at the given offset. - */ - private void markBranchOrigin(int offset) - { - instructionMarks[offset] |= INSTRUCTION | BRANCH_ORIGIN; - } - - - /** - * Marks the branch target at the given offset. - */ - private void markBranchTarget(int offset, int jumpOffset) - { - int targetOffset = offset + jumpOffset; - - instructionMarks[targetOffset] |= BRANCH_TARGET; - } - - - /** - * Marks the subroutine start at the given offset, if applicable. - */ - private void markBranchSubroutineStart(int offset, - int jumpOffset, - int subroutineStart) - { - int targetOffset = offset + jumpOffset; - - // Are we marking a subroutine and branching to an offset that hasn't - // been marked yet? - if (subroutineStarts[targetOffset] == UNKNOWN) - { - // Is it a backward branch? - if (jumpOffset < 0) - { - // Remember the smallest subroutine start. - if (subroutineStart > targetOffset) - { - subroutineStart = targetOffset; - } - - // We'll have to go over all instructions again. - repeat = true; - } - - // Mark the subroutine start of the target. - subroutineStarts[targetOffset] = subroutineStart; - } - } - - - /** - * Marks the instruction at the given offset, after a branch. - */ - private void markAfterBranchOrigin(int nextOffset) - { - instructionMarks[nextOffset] |= AFTER_BRANCH; - - // Stop marking a subroutine. - currentSubroutineStart = UNKNOWN; - } - - - /** - * Checks if the specified instruction is inside a subroutine. - */ - private void checkSubroutine(int offset) - { - // Are we inside a previously marked subroutine? - if (subroutineStarts[offset] != UNKNOWN) - { - // Start marking a subroutine. - currentSubroutineStart = subroutineStarts[offset]; - } - - // Are we marking a subroutine? - else if (currentSubroutineStart != UNKNOWN) - { - // Mark the subroutine start. - subroutineStarts[offset] = currentSubroutineStart; - } - } -} |