diff options
Diffstat (limited to 'src/proguard/optimize/evaluation/LivenessAnalyzer.java')
| -rw-r--r-- | src/proguard/optimize/evaluation/LivenessAnalyzer.java | 516 |
1 files changed, 516 insertions, 0 deletions
diff --git a/src/proguard/optimize/evaluation/LivenessAnalyzer.java b/src/proguard/optimize/evaluation/LivenessAnalyzer.java new file mode 100644 index 0000000..9915027 --- /dev/null +++ b/src/proguard/optimize/evaluation/LivenessAnalyzer.java @@ -0,0 +1,516 @@ +/* + * ProGuard -- shrinking, optimization, obfuscation, and preverification + * of Java bytecode. + * + * Copyright (c) 2002-2009 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.evaluation; + +import proguard.classfile.*; +import proguard.classfile.attribute.*; +import proguard.classfile.attribute.visitor.*; +import proguard.classfile.instruction.*; +import proguard.classfile.instruction.visitor.InstructionVisitor; +import proguard.classfile.util.SimplifiedVisitor; +import proguard.evaluation.value.*; + +/** + * This AttributeVisitor analyzes the liveness of the variables in the code + * attributes that it visits, based on partial evaluation. + * + * @author Eric Lafortune + */ +public class LivenessAnalyzer +extends SimplifiedVisitor +implements AttributeVisitor, + InstructionVisitor, + ExceptionInfoVisitor +{ + //* + private static final boolean DEBUG = false; + /*/ + private static boolean DEBUG = true; + //*/ + + private static final int MAX_VARIABLES_SIZE = 64; + + private final PartialEvaluator partialEvaluator; + + private long[] isAliveBefore = new long[ClassConstants.TYPICAL_CODE_LENGTH]; + private long[] isAliveAfter = new long[ClassConstants.TYPICAL_CODE_LENGTH]; + private long[] isCategory2 = new long[ClassConstants.TYPICAL_CODE_LENGTH]; + + // Fields acting as global temporary variables. + private boolean checkAgain; + private long alive; + + + /** + * Creates a new LivenessAnalyzer. + */ + public LivenessAnalyzer() + { + this(new PartialEvaluator()); + } + + + /** + * Creates a new LivenessAnalyzer that will use the given partial evaluator. + * It will run this evaluator on every code attribute that it visits. + */ + public LivenessAnalyzer(PartialEvaluator partialEvaluator) + { + this.partialEvaluator = partialEvaluator; + } + + + /** + * Returns whether the specified variable is alive before the instruction + * at the given offset. + */ + public boolean isAliveBefore(int instructionOffset, int variableIndex) + { + return variableIndex >= MAX_VARIABLES_SIZE || + (isAliveBefore[instructionOffset] & (1L << variableIndex)) != 0; + } + + + /** + * Sets whether the specified variable is alive before the instruction + * at the given offset. + */ + public void setAliveBefore(int instructionOffset, int variableIndex, boolean alive) + { + if (variableIndex < MAX_VARIABLES_SIZE) + { + if (alive) + { + isAliveBefore[instructionOffset] |= 1L << variableIndex; + } + else + { + isAliveBefore[instructionOffset] &= ~(1L << variableIndex); + } + } + } + + + /** + * Returns whether the specified variable is alive after the instruction + * at the given offset. + */ + public boolean isAliveAfter(int instructionOffset, int variableIndex) + { + return variableIndex >= MAX_VARIABLES_SIZE || + (isAliveAfter[instructionOffset] & (1L << variableIndex)) != 0; + } + + + /** + * Sets whether the specified variable is alive after the instruction + * at the given offset. + */ + public void setAliveAfter(int instructionOffset, int variableIndex, boolean alive) + { + if (variableIndex < MAX_VARIABLES_SIZE) + { + if (alive) + { + isAliveAfter[instructionOffset] |= 1L << variableIndex; + } + else + { + isAliveAfter[instructionOffset] &= ~(1L << variableIndex); + } + } + } + + + /** + * Returns whether the specified variable takes up two entries after the + * instruction at the given offset. + */ + public boolean isCategory2(int instructionOffset, int variableIndex) + { + return variableIndex < MAX_VARIABLES_SIZE && + (isCategory2[instructionOffset] & (1L << variableIndex)) != 0; + } + + + /** + * Sets whether the specified variable takes up two entries after the + * instruction at the given offset. + */ + public void setCategory2(int instructionOffset, int variableIndex, boolean category2) + { + if (variableIndex < MAX_VARIABLES_SIZE) + { + if (category2) + { + isCategory2[instructionOffset] |= 1L << variableIndex; + } + else + { + isCategory2[instructionOffset] &= ~(1L << variableIndex); + } + } + } + + + // 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"); + + if (DEBUG) + { + System.out.println(); + System.out.println("Liveness analysis: "+clazz.getName()+"."+method.getName(clazz)+method.getDescriptor(clazz)); + } + + // Initialize the global arrays. + initializeArrays(codeAttribute); + + // Evaluate the method. + partialEvaluator.visitCodeAttribute(clazz, method, codeAttribute); + + int codeLength = codeAttribute.u4codeLength; + int variablesSize = codeAttribute.u2maxLocals; + + // We'll only really analyze the first 64 variables. + if (variablesSize > MAX_VARIABLES_SIZE) + { + variablesSize = MAX_VARIABLES_SIZE; + } + + // Mark liveness blocks, as many times as necessary. + do + { + checkAgain = false; + alive = 0L; + + // Loop over all traced instructions, backward. + for (int offset = codeLength - 1; offset >= 0; offset--) + { + if (partialEvaluator.isTraced(offset)) + { + // Update the liveness based on the branch targets. + InstructionOffsetValue branchTargets = partialEvaluator.branchTargets(offset); + if (branchTargets != null) + { + // Update the liveness right after the branch instruction. + alive = combinedLiveness(branchTargets); + } + + // Merge the current liveness. + alive |= isAliveAfter[offset]; + + // Update the liveness after the instruction. + isAliveAfter[offset] = alive; + + // Update the current liveness based on the instruction. + codeAttribute.instructionAccept(clazz, method, offset, this); + + // Merge the current liveness. + alive |= isAliveBefore[offset]; + + // Update the liveness before the instruction. + if ((~isAliveBefore[offset] & alive) != 0L) + { + isAliveBefore[offset] = alive; + + // Do we have to check again after this loop? + checkAgain |= offset < maxOffset(partialEvaluator.branchOrigins(offset)); + } + } + } + + // Account for the liveness at the start of the exception handlers. + codeAttribute.exceptionsAccept(clazz, method, this); + } + while (checkAgain); + + // Loop over all instructions, to mark variables that take up two entries. + for (int offset = 0; offset < codeLength; offset++) + { + if (partialEvaluator.isTraced(offset)) + { + // Loop over all variables. + for (int variableIndex = 0; variableIndex < variablesSize; variableIndex++) + { + // Is the variable alive and a category 2 type? + if (isAliveBefore(offset, variableIndex)) + { + Value value = partialEvaluator.getVariablesBefore(offset).getValue(variableIndex); + if (value != null && value.isCategory2()) + { + // Mark it as such. + setCategory2(offset, variableIndex, true); + + // Mark the next variable as well. + setAliveBefore(offset, variableIndex + 1, true); + setCategory2( offset, variableIndex + 1, true); + } + } + + // Is the variable alive and a category 2 type? + if (isAliveAfter(offset, variableIndex)) + { + Value value = partialEvaluator.getVariablesAfter(offset).getValue(variableIndex); + if (value != null && value.isCategory2()) + { + // Mark it as such. + setCategory2(offset, variableIndex, true); + + // Mark the next variable as well. + setAliveAfter(offset, variableIndex + 1, true); + setCategory2( offset, variableIndex + 1, true); + } + } + } + } + } + + if (DEBUG) + { + // Loop over all instructions. + for (int offset = 0; offset < codeLength; offset++) + { + if (partialEvaluator.isTraced(offset)) + { + long aliveBefore = isAliveBefore[offset]; + long aliveAfter = isAliveAfter[offset]; + long category2 = isCategory2[offset]; + + // Print out the liveness of all variables before the instruction. + for (int variableIndex = 0; variableIndex < variablesSize; variableIndex++) + { + long variableMask = (1L << variableIndex); + System.out.print((aliveBefore & variableMask) == 0L ? '.' : + (category2 & variableMask) == 0L ? 'x' : + '*'); + } + + // Print out the instruction itself. + System.out.println(" "+ InstructionFactory.create(codeAttribute.code, offset).toString(offset)); + + // Print out the liveness of all variables after the instruction. + for (int variableIndex = 0; variableIndex < variablesSize; variableIndex++) + { + long variableMask = (1L << variableIndex); + System.out.print((aliveAfter & variableMask) == 0L ? '.' : + (category2 & variableMask) == 0L ? 'x' : + '='); + } + + System.out.println(); + } + } + } + } + + + // Implementations for InstructionVisitor. + + public void visitAnyInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, Instruction instruction) {} + + + public void visitVariableInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, VariableInstruction variableInstruction) + { + int variableIndex = variableInstruction.variableIndex; + if (variableIndex < MAX_VARIABLES_SIZE) + { + long livenessMask = 1L << variableIndex; + + // Is it a load instruction or a store instruction? + if (variableInstruction.isLoad()) + { + // Start marking the variable before the load instruction. + alive |= livenessMask; + } + else + { + // Stop marking the variable before the store instruction. + alive &= ~livenessMask; + + // But do mark the variable right after the store instruction. + isAliveAfter[offset] |= livenessMask; + } + } + } + + + public void visitConstantInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, ConstantInstruction constantInstruction) + { + // Special case: variable 0 ('this') in an initializer has to be alive + // as long as it hasn't been initialized. + if (offset == partialEvaluator.superInitializationOffset()) + { + alive |= 1L; + } + } + + + // Implementations for ExceptionInfoVisitor. + + public void visitExceptionInfo(Clazz clazz, Method method, CodeAttribute codeAttribute, ExceptionInfo exceptionInfo) + { + // Are any variables alive at the start of the handler? + long alive = isAliveBefore[exceptionInfo.u2handlerPC]; + if (alive != 0L) + { + // Set the same liveness flags for the entire try block. + int startOffset = exceptionInfo.u2startPC; + int endOffset = exceptionInfo.u2endPC; + + for (int offset = startOffset; offset < endOffset; offset++) + { + if (partialEvaluator.isTraced(offset)) + { + if ((~(isAliveBefore[offset] & isAliveAfter[offset]) & alive) != 0L) + { + isAliveBefore[offset] |= alive; + isAliveAfter[offset] |= alive; + + // Check again after having marked this try block. + checkAgain = true; + } + } + } + } + } + + + // Small utility methods. + + /** + * Initializes the global arrays. + */ + private void initializeArrays(CodeAttribute codeAttribute) + { + int codeLength = codeAttribute.u4codeLength; + + // Create new arrays for storing information at each instruction offset. + if (isAliveBefore.length < codeLength) + { + isAliveBefore = new long[codeLength]; + isAliveAfter = new long[codeLength]; + isCategory2 = new long[codeLength]; + } + else + { + for (int index = 0; index < codeLength; index++) + { + isAliveBefore[index] = 0L; + isAliveAfter[index] = 0L; + isCategory2[index] = 0L; + } + } + } + + + /** + * Returns the combined liveness mask of the variables right before the + * specified instruction offsets. + */ + private long combinedLiveness(InstructionOffsetValue instructionOffsetValue) + { + long alive = 0L; + + int count = instructionOffsetValue.instructionOffsetCount(); + for (int index = 0; index < count; index++) + { + alive |= isAliveBefore[instructionOffsetValue.instructionOffset(index)]; + } + + return alive; + } + + + /** + * Returns the minimum offset from the given instruction offsets. + */ + private int minOffset(Value instructionOffsets) + { + return minOffset(instructionOffsets, Integer.MAX_VALUE); + } + + + /** + * Returns the minimum offset from the given instruction offsets. + */ + private int minOffset(Value instructionOffsets, int minOffset) + { + if (instructionOffsets != null) + { + InstructionOffsetValue instructionOffsetValue = + instructionOffsets.instructionOffsetValue(); + + int count = instructionOffsetValue.instructionOffsetCount(); + for (int index = 0; index < count; index++) + { + int offset = instructionOffsetValue.instructionOffset(index); + if (minOffset > offset) + { + minOffset = offset; + } + } + } + + return minOffset; + } + + + /** + * Returns the maximum offset from the given instruction offsets. + */ + private int maxOffset(Value instructionOffsets) + { + return maxOffset(instructionOffsets, Integer.MIN_VALUE); + } + + + /** + * Returns the maximum offset from the given instruction offsets. + */ + private int maxOffset(Value instructionOffsets, int maxOffset) + { + if (instructionOffsets != null) + { + InstructionOffsetValue instructionOffsetValue = + instructionOffsets.instructionOffsetValue(); + + int count = instructionOffsetValue.instructionOffsetCount(); + for (int index = 0; index < count; index++) + { + int offset = instructionOffsetValue.instructionOffset(index); + if (maxOffset < offset) + { + maxOffset = offset; + } + } + } + + return maxOffset; + } +} |