aboutsummaryrefslogtreecommitdiffstats
path: root/src/main/javassist/bytecode/analysis/Analyzer.java
diff options
context:
space:
mode:
authorjgreene <jgreene@30ef5769-5b8d-40dd-aea6-55b5d6557bb3>2008-05-24 05:13:20 +0000
committerjgreene <jgreene@30ef5769-5b8d-40dd-aea6-55b5d6557bb3>2008-05-24 05:13:20 +0000
commit2bae8b13291b8ef8fc3df24af627424f344581df (patch)
tree7d68840873257ab78ae69cc9ed9570adc18bc2d8 /src/main/javassist/bytecode/analysis/Analyzer.java
parente48604525140c746404a637282cb7b1dd97c18c4 (diff)
downloadjavassist-2bae8b13291b8ef8fc3df24af627424f344581df.tar.gz
javassist-2bae8b13291b8ef8fc3df24af627424f344581df.zip
Fix subtypeOf in CtArray
Introduce full data-flow analysis API Fix AALOAD by using data-flow analysis to determine the type Introduce a testsuite to the project Add a framedump toolp git-svn-id: http://anonsvn.jboss.org/repos/javassist/trunk@437 30ef5769-5b8d-40dd-aea6-55b5d6557bb3
Diffstat (limited to 'src/main/javassist/bytecode/analysis/Analyzer.java')
-rw-r--r--src/main/javassist/bytecode/analysis/Analyzer.java422
1 files changed, 422 insertions, 0 deletions
diff --git a/src/main/javassist/bytecode/analysis/Analyzer.java b/src/main/javassist/bytecode/analysis/Analyzer.java
new file mode 100644
index 00000000..7ef0b00b
--- /dev/null
+++ b/src/main/javassist/bytecode/analysis/Analyzer.java
@@ -0,0 +1,422 @@
+/*
+ * Javassist, a Java-bytecode translator toolkit.
+ * Copyright (C) 1999-2007 Shigeru Chiba, and others. All Rights Reserved.
+ *
+ * The contents of this file are subject to the Mozilla Public License Version
+ * 1.1 (the "License"); you may not use this file except in compliance with
+ * the License. Alternatively, the contents of this file may be used under
+ * the terms of the GNU Lesser General Public License Version 2.1 or later.
+ *
+ * Software distributed under the License is distributed on an "AS IS" basis,
+ * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
+ * for the specific language governing rights and limitations under the
+ * License.
+ */
+package javassist.bytecode.analysis;
+
+import java.util.Iterator;
+
+import javassist.ClassPool;
+import javassist.CtClass;
+import javassist.CtMethod;
+import javassist.NotFoundException;
+import javassist.bytecode.AccessFlag;
+import javassist.bytecode.BadBytecode;
+import javassist.bytecode.CodeAttribute;
+import javassist.bytecode.CodeIterator;
+import javassist.bytecode.ConstPool;
+import javassist.bytecode.Descriptor;
+import javassist.bytecode.ExceptionTable;
+import javassist.bytecode.MethodInfo;
+import javassist.bytecode.Opcode;
+
+/**
+ * A data-flow analyzer that determines the type state of the stack and local
+ * variable table at every reachable instruction in a method. During analysis,
+ * bytecode verification is performed in a similar manner to that described
+ * in the JVM specification.
+ *
+ * <p>Example:</p>
+ *
+ * <pre>
+ * // Method to analyze
+ * public Object doSomething(int x) {
+ * Number n;
+ * if (x < 5) {
+ * n = new Double(0);
+ * } else {
+ * n = new Long(0);
+ * }
+ *
+ * return n;
+ * }
+ *
+ * // Which compiles to:
+ * // 0: iload_1
+ * // 1: iconst_5
+ * // 2: if_icmpge 17
+ * // 5: new #18; //class java/lang/Double
+ * // 8: dup
+ * // 9: dconst_0
+ * // 10: invokespecial #44; //Method java/lang/Double."<init>":(D)V
+ * // 13: astore_2
+ * // 14: goto 26
+ * // 17: new #16; //class java/lang/Long
+ * // 20: dup
+ * // 21: lconst_1
+ * // 22: invokespecial #47; //Method java/lang/Long."<init>":(J)V
+ * // 25: astore_2
+ * // 26: aload_2
+ * // 27: areturn
+ *
+ * public void analyzeIt(CtClass clazz, MethodInfo method) {
+ * Analyzer analyzer = new Analyzer();
+ * Frame[] frames = analyzer.analyze(clazz, method);
+ * frames[0].getLocal(0).getCtClass(); // returns clazz;
+ * frames[0].getLocal(1).getCtClass(); // returns java.lang.String
+ * frames[1].peek(); // returns Type.INTEGER
+ * frames[27].peek().getCtClass(); // returns java.lang.Number
+ * }
+ * </pre>
+ *
+ * @see FramePrinter
+ * @author Jason T. Greene
+ */
+public class Analyzer implements Opcode {
+ private final SubroutineScanner scanner = new SubroutineScanner();
+ private CtClass clazz;
+ private ExceptionInfo[] exceptions;
+ private Frame[] frames;
+ private Subroutine[] subroutines;
+
+ private static class ExceptionInfo {
+ private int end;
+ private int handler;
+ private int start;
+ private Type type;
+
+ private ExceptionInfo(int start, int end, int handler, Type type) {
+ this.start = start;
+ this.end = end;
+ this.handler = handler;
+ this.type = type;
+ }
+ }
+
+ /**
+ * Performs data-flow analysis on a method and returns an array, indexed by
+ * instruction position, containing the starting frame state of all reachable
+ * instructions. Non-reachable code, and illegal code offsets are represented
+ * as a null in the frame state array. This can be used to detect dead code.
+ *
+ * If the method does not contain code (it is either native or abstract), null
+ * is returned.
+ *
+ * @param clazz the declaring class of the method
+ * @param method the method to analyze
+ * @return an array, indexed by instruction position, of the starting frame state,
+ * or null if this method doesn't have code
+ * @throws BadBytecode if the bytecode does not comply with the JVM specification
+ */
+ public Frame[] analyze(CtClass clazz, MethodInfo method) throws BadBytecode {
+ this.clazz = clazz;
+ CodeAttribute codeAttribute = method.getCodeAttribute();
+ // Native or Abstract
+ if (codeAttribute == null)
+ return null;
+
+ int maxLocals = codeAttribute.getMaxLocals();
+ int maxStack = codeAttribute.getMaxStack();
+ int codeLength = codeAttribute.getCodeLength();
+
+ CodeIterator iter = codeAttribute.iterator();
+ IntQueue queue = new IntQueue();
+
+ exceptions = buildExceptionInfo(method);
+ subroutines = scanner.scan(method);
+
+ Executor executor = new Executor(clazz.getClassPool(), method.getConstPool());
+ frames = new Frame[codeLength];
+ frames[iter.lookAhead()] = firstFrame(method, maxLocals, maxStack);
+ queue.add(iter.next());
+ while (!queue.isEmpty()) {
+ analyzeNextEntry(method, iter, queue, executor);
+ }
+
+ return frames;
+ }
+
+ /**
+ * Performs data-flow analysis on a method and returns an array, indexed by
+ * instruction position, containing the starting frame state of all reachable
+ * instructions. Non-reachable code, and illegal code offsets are represented
+ * as a null in the frame state array. This can be used to detect dead code.
+ *
+ * If the method does not contain code (it is either native or abstract), null
+ * is returned.
+ *
+ * @param method the method to analyze
+ * @return an array, indexed by instruction position, of the starting frame state,
+ * or null if this method doesn't have code
+ * @throws BadBytecode if the bytecode does not comply with the JVM specification
+ */
+ public Frame[] analyze(CtMethod method) throws BadBytecode {
+ return analyze(method.getDeclaringClass(), method.getMethodInfo2());
+ }
+
+ private void analyzeNextEntry(MethodInfo method, CodeIterator iter,
+ IntQueue queue, Executor executor) throws BadBytecode {
+ int pos = queue.take();
+ iter.move(pos);
+ iter.next();
+
+ Frame frame = frames[pos].copy();
+ Subroutine subroutine = subroutines[pos];
+
+ try {
+ executor.execute(method, pos, iter, frame, subroutine);
+ } catch (RuntimeException e) {
+ throw new BadBytecode(e.getMessage() + "[pos = " + pos + "]", e);
+ }
+
+ int opcode = iter.byteAt(pos);
+
+ if (opcode == TABLESWITCH) {
+ mergeTableSwitch(queue, pos, iter, frame);
+ } else if (opcode == LOOKUPSWITCH) {
+ mergeLookupSwitch(queue, pos, iter, frame);
+ } else if (opcode == RET) {
+ mergeRet(queue, iter, pos, frame, subroutine);
+ } else if (Util.isJumpInstruction(opcode)) {
+ int target = Util.getJumpTarget(pos, iter);
+
+ if (Util.isJsr(opcode)) {
+ // Merge the state before the jsr into the next instruction
+ mergeJsr(queue, frames[pos], subroutines[target], pos, lookAhead(iter, pos));
+ } else if (! Util.isGoto(opcode)) {
+ merge(queue, frame, lookAhead(iter, pos));
+ }
+
+ merge(queue, frame, target);
+ } else if (opcode != ATHROW && ! Util.isReturn(opcode)) {
+ // Can advance to next instruction
+ merge(queue, frame, lookAhead(iter, pos));
+ }
+
+ // Merge all exceptions that are reachable from this instruction.
+ // The redundancy is intentional, since the state must be based
+ // on the current instruction frame.
+ mergeExceptionHandlers(queue, method, pos, frame);
+ }
+
+ private ExceptionInfo[] buildExceptionInfo(MethodInfo method) {
+ ConstPool constPool = method.getConstPool();
+ ClassPool classes = clazz.getClassPool();
+
+ ExceptionTable table = method.getCodeAttribute().getExceptionTable();
+ ExceptionInfo[] exceptions = new ExceptionInfo[table.size()];
+ for (int i = 0; i < table.size(); i++) {
+ int index = table.catchType(i);
+ Type type;
+ try {
+ type = index == 0 ? Type.THROWABLE : Type.get(classes.get(constPool.getClassInfo(index)));
+ } catch (NotFoundException e) {
+ throw new IllegalStateException(e);
+ }
+
+ exceptions[i] = new ExceptionInfo(table.startPc(i), table.endPc(i), table.handlerPc(i), type);
+ }
+
+ return exceptions;
+ }
+
+ private Frame firstFrame(MethodInfo method, int maxLocals, int maxStack) {
+ int pos = 0;
+
+ Frame first = new Frame(maxLocals, maxStack);
+ if ((method.getAccessFlags() & AccessFlag.STATIC) == 0) {
+ first.setLocal(pos++, Type.get(clazz));
+ }
+
+ CtClass[] parameters;
+ try {
+ parameters = Descriptor.getParameterTypes(method.getDescriptor(), clazz.getClassPool());
+ } catch (NotFoundException e) {
+ throw new RuntimeException(e);
+ }
+
+ for (int i = 0; i < parameters.length; i++) {
+ Type type = zeroExtend(Type.get(parameters[i]));
+ first.setLocal(pos++, type);
+ if (type.getSize() == 2)
+ first.setLocal(pos++, Type.TOP);
+ }
+
+ return first;
+ }
+
+ private int getNext(CodeIterator iter, int of, int restore) throws BadBytecode {
+ iter.move(of);
+ iter.next();
+ int next = iter.lookAhead();
+ iter.move(restore);
+ iter.next();
+
+ return next;
+ }
+
+ private int lookAhead(CodeIterator iter, int pos) throws BadBytecode {
+ if (! iter.hasNext())
+ throw new BadBytecode("Execution falls off end! [pos = " + pos + "]");
+
+ return iter.lookAhead();
+ }
+
+
+ private void merge(IntQueue queue, Frame frame, int target) {
+ Frame old = frames[target];
+ boolean changed;
+
+ if (old == null) {
+ frames[target] = frame.copy();
+ changed = true;
+ } else {
+ changed = old.merge(frame);
+ }
+
+ if (changed) {
+ queue.add(target);
+ }
+ }
+
+ private void mergeExceptionHandlers(IntQueue queue, MethodInfo method, int pos, Frame frame) {
+ for (int i = 0; i < exceptions.length; i++) {
+ ExceptionInfo exception = exceptions[i];
+
+ // Start is inclusive, while end is exclusive!
+ if (pos >= exception.start && pos < exception.end) {
+ Frame newFrame = frame.copy();
+ newFrame.clearStack();
+ newFrame.push(exception.type);
+ merge(queue, newFrame, exception.handler);
+ }
+ }
+ }
+
+ private void mergeJsr(IntQueue queue, Frame frame, Subroutine sub, int pos, int next) throws BadBytecode {
+ if (sub == null)
+ throw new BadBytecode("No subroutine at jsr target! [pos = " + pos + "]");
+
+ Frame old = frames[next];
+ boolean changed = false;
+
+ if (old == null) {
+ old = frames[next] = frame.copy();
+ changed = true;
+ } else {
+ for (int i = 0; i < frame.localsLength(); i++) {
+ // Skip everything accessed by a subroutine, mergeRet must handle this
+ if (!sub.isAccessed(i)) {
+ Type oldType = old.getLocal(i);
+ Type newType = frame.getLocal(i);
+ if (oldType == null) {
+ old.setLocal(i, newType);
+ changed = true;
+ continue;
+ }
+
+ newType = oldType.merge(newType);
+ // Always set the type, in case a multi-type switched to a standard type.
+ old.setLocal(i, newType);
+ if (!newType.equals(oldType) || newType.popChanged())
+ changed = true;
+ }
+ }
+ }
+
+ if (! old.isJsrMerged()) {
+ old.setJsrMerged(true);
+ changed = true;
+ }
+
+ if (changed && old.isRetMerged())
+ queue.add(next);
+
+ }
+
+ private void mergeLookupSwitch(IntQueue queue, int pos, CodeIterator iter, Frame frame) throws BadBytecode {
+ int index = (pos & ~3) + 4;
+ // default
+ merge(queue, frame, pos + iter.s32bitAt(index));
+ int npairs = iter.s32bitAt(index += 4);
+ int end = npairs * 8 + (index += 4);
+
+ // skip "match"
+ for (index += 4; index < end; index += 8) {
+ int target = iter.s32bitAt(index) + pos;
+ merge(queue, frame, target);
+ }
+ }
+
+ private void mergeRet(IntQueue queue, CodeIterator iter, int pos, Frame frame, Subroutine subroutine) throws BadBytecode {
+ if (subroutine == null)
+ throw new BadBytecode("Ret on no subroutine! [pos = " + pos + "]");
+
+ Iterator callerIter = subroutine.callers().iterator();
+ while (callerIter.hasNext()) {
+ int caller = ((Integer) callerIter.next()).intValue();
+ int returnLoc = getNext(iter, caller, pos);
+ boolean changed = false;
+
+ Frame old = frames[returnLoc];
+ if (old == null) {
+ old = frames[returnLoc] = frame.copyStack();
+ changed = true;
+ } else {
+ changed = old.mergeStack(frame);
+ }
+
+ for (Iterator i = subroutine.accessed().iterator(); i.hasNext(); ) {
+ int index = ((Integer)i.next()).intValue();
+ Type oldType = old.getLocal(index);
+ Type newType = frame.getLocal(index);
+ if (oldType != newType) {
+ old.setLocal(index, newType);
+ changed = true;
+ }
+ }
+
+ if (! old.isRetMerged()) {
+ old.setRetMerged(true);
+ changed = true;
+ }
+
+ if (changed && old.isJsrMerged())
+ queue.add(returnLoc);
+ }
+ }
+
+
+ private void mergeTableSwitch(IntQueue queue, int pos, CodeIterator iter, Frame frame) throws BadBytecode {
+ // Skip 4 byte alignment padding
+ int index = (pos & ~3) + 4;
+ // default
+ merge(queue, frame, pos + iter.s32bitAt(index));
+ int low = iter.s32bitAt(index += 4);
+ int high = iter.s32bitAt(index += 4);
+ int end = (high - low + 1) * 4 + (index += 4);
+
+ // Offset table
+ for (; index < end; index += 4) {
+ int target = iter.s32bitAt(index) + pos;
+ merge(queue, frame, target);
+ }
+ }
+
+ private Type zeroExtend(Type type) {
+ if (type == Type.SHORT || type == Type.BYTE || type == Type.CHAR || type == Type.BOOLEAN)
+ return Type.INTEGER;
+
+ return type;
+ }
+}