From 42e1dbed4e870e5c452fa5173ac10921c46d06d0 Mon Sep 17 00:00:00 2001 From: chiba Date: Sun, 6 May 2007 15:41:43 +0000 Subject: [PATCH] implemented javassist.bytecode.stackmap package. git-svn-id: http://anonsvn.jboss.org/repos/javassist/trunk@369 30ef5769-5b8d-40dd-aea6-55b5d6557bb3 --- .../javassist/bytecode/StackMapTable.java | 17 +- .../bytecode/stackmap/BasicBlock.java | 673 ++++++++---------- .../javassist/bytecode/stackmap/Liveness.java | 364 ++++++++++ .../javassist/bytecode/stackmap/MapMaker.java | 400 ++++------- .../javassist/bytecode/stackmap/Tracer.java | 60 +- .../javassist/bytecode/stackmap/TypeData.java | 17 +- .../bytecode/stackmap/TypedBlock.java | 231 ++++++ 7 files changed, 1092 insertions(+), 670 deletions(-) create mode 100644 src/main/javassist/bytecode/stackmap/Liveness.java create mode 100644 src/main/javassist/bytecode/stackmap/TypedBlock.java diff --git a/src/main/javassist/bytecode/StackMapTable.java b/src/main/javassist/bytecode/StackMapTable.java index 56b1e716..159c6973 100644 --- a/src/main/javassist/bytecode/StackMapTable.java +++ b/src/main/javassist/bytecode/StackMapTable.java @@ -595,6 +595,7 @@ public class StackMapTable extends AttributeInfo { static class Printer extends Walker { private PrintWriter writer; + private int offset; /** * Prints the stack table map. @@ -611,30 +612,36 @@ public class StackMapTable extends AttributeInfo { Printer(byte[] data, PrintWriter pw) { super(data); writer = pw; + offset = -1; } public void sameFrame(int pos, int offsetDelta) { - writer.println("same frame: " + offsetDelta); + offset += offsetDelta + 1; + writer.println(offset + " same frame: " + offsetDelta); } public void sameLocals(int pos, int offsetDelta, int stackTag, int stackData) { - writer.println("same locals: " + offsetDelta); + offset += offsetDelta + 1; + writer.println(offset + " same locals: " + offsetDelta); printTypeInfo(stackTag, stackData); } public void chopFrame(int pos, int offsetDelta, int k) { - writer.println("chop frame: " + offsetDelta + ", " + k + " last locals"); + offset += offsetDelta + 1; + writer.println(offset + " chop frame: " + offsetDelta + ", " + k + " last locals"); } public void appendFrame(int pos, int offsetDelta, int[] tags, int[] data) { - writer.println("append frame: " + offsetDelta); + offset += offsetDelta + 1; + writer.println(offset + " append frame: " + offsetDelta); for (int i = 0; i < tags.length; i++) printTypeInfo(tags[i], data[i]); } public void fullFrame(int pos, int offsetDelta, int[] localTags, int[] localData, int[] stackTags, int[] stackData) { - writer.println("full frame: " + offsetDelta); + offset += offsetDelta + 1; + writer.println(offset + " full frame: " + offsetDelta); writer.println("[locals]"); for (int i = 0; i < localTags.length; i++) printTypeInfo(localTags[i], localData[i]); diff --git a/src/main/javassist/bytecode/stackmap/BasicBlock.java b/src/main/javassist/bytecode/stackmap/BasicBlock.java index 440b6ea5..af40a262 100644 --- a/src/main/javassist/bytecode/stackmap/BasicBlock.java +++ b/src/main/javassist/bytecode/stackmap/BasicBlock.java @@ -16,421 +16,370 @@ package javassist.bytecode.stackmap; import javassist.bytecode.*; +import java.util.HashMap; import java.util.ArrayList; -public class BasicBlock implements TypeTag, Comparable { - +public class BasicBlock { public int position, length; - public int stackTop, numLocals; - public TypeData[] stackTypes, localsTypes; - - /* The version number of the values of numLocals and localsTypes. - * These values are repeatedly updated while MapMaker#make() - * is running. This field represents when the values are recorded. - */ - public int version; - - /* a flag used by MapMaker#recordUsage() - */ - public int[] localsUsage; - - /* The number of the basic blocks from which a thread of control - * may reach this basic block. The number excludes the preceding - * block. Thus, if it is zero, a thread of control reaches - * only from the preceding block. Such a basic block represents - * the boundary of a try block. - */ - public int inbound; - - public static class Branch { - public Branch next; - public int target; - public int typeIndex; // exception type - public Branch(Branch next, int target, int type) { - this.next = next; - this.target = target; - this.typeIndex = type; - } - } + public int incoming; // the number of incoming branches. + public BasicBlock[] exit; // null if the block is a leaf. + public boolean stop; // true if the block ends with an unconditional jump. + public Catch toCatch; - /* A list of catch clauses that a thread may jump - * from this block to. - */ - public Branch catchBlocks; - - /* public static void main(String[] args) throws Exception { - BasicBlock b = new BasicBlock(0); - b.initFirstBlock(8, 1, args[0], args[1], args[2].equals("static"), args[2].equals("const")); - System.out.println(b); - }*/ - - private BasicBlock(int pos) { + protected BasicBlock(int pos) { position = pos; length = 0; - stackTop = numLocals = 0; - stackTypes = localsTypes = null; - inbound = 1; - localsUsage = null; - catchBlocks = null; - } - - public boolean alreadySet(int ver) { - return stackTypes != null && ver == version; - } - - /* - * Computes the correct value of numLocals. - * It assumes that: - * correct numLocals <= current numLocals - */ - public void resetNumLocals() { - if (localsTypes != null) { - int nl = numLocals; - while (nl > 0 && localsTypes[nl - 1] == TypeTag.TOP) { - if (nl > 1) { - TypeData td = localsTypes[nl - 2]; - if (td == TypeTag.LONG || td == TypeTag.DOUBLE) - break; - } - - --nl; - } - - numLocals = nl; - } + incoming = 0; } - public void setStackMap(int st, TypeData[] stack, - int nl, TypeData[] locals) + public static BasicBlock find(BasicBlock[] blocks, int pos) throws BadBytecode { - stackTop = st; - stackTypes = stack; - numLocals = nl; - localsTypes = locals; + for (int i = 0; i < blocks.length; i++) { + int iPos = blocks[i].position; + if (iPos <= pos && pos < iPos + blocks[i].length) + return blocks[i]; + } + + throw new BadBytecode("no basic block at " + pos); } - private void updateLength(int nextPos) { - length = nextPos - position; + public static class Catch { + Catch next; + BasicBlock body; + int typeIndex; + Catch(BasicBlock b, int i, Catch c) { + body = b; + typeIndex = i; + next = c; + } } public String toString() { StringBuffer sbuf = new StringBuffer(); - sbuf.append("Block at "); - sbuf.append(position); - sbuf.append(" stack={"); - printTypes(sbuf, stackTop, stackTypes); - sbuf.append("} locals={"); - printTypes(sbuf, numLocals, localsTypes); - sbuf.append('}'); + String cname = this.getClass().getName(); + int i = cname.lastIndexOf('.'); + sbuf.append(i < 0 ? cname : cname.substring(i + 1)); + sbuf.append("["); + toString2(sbuf); + sbuf.append("]"); return sbuf.toString(); } - private static void printTypes(StringBuffer sbuf, int size, - TypeData[] types) { - if (types == null) - return; - - for (int i = 0; i < size; i++) { - if (i > 0) - sbuf.append(", "); - - TypeData td = types[i]; - sbuf.append(td == null ? "<>" : td.toString()); + protected void toString2(StringBuffer sbuf) { + sbuf.append("pos=").append(position).append(", len=") + .append(length).append(", in=").append(incoming) + .append(", exit{"); + if (exit != null) { + for (int i = 0; i < exit.length; i++) + sbuf.append(exit[i].position).append(", "); } - } - - /** - * Finds the basic block including the given position. - * - * @param pos the position. - */ - public static BasicBlock find(BasicBlock[] blocks, int pos) throws BadBytecode { - int n = blocks.length; - for (int i = 0; i < n; i++) - if (blocks[i].position == pos) - return blocks[i]; - throw new BadBytecode("no basic block: " + pos); - } + sbuf.append("}, {"); + Catch th = toCatch; + while (th != null) { + sbuf.append("(").append(th.body.position).append(", ") + .append(th.typeIndex).append("), "); + th = th.next; + } - /** - * Divides the given code fragment into basic blocks. - * It returns null if the given MethodInfo does not include - * a CodeAttribute. - */ - public static BasicBlock[] makeBlocks(MethodInfo minfo) throws BadBytecode { - CodeAttribute ca = minfo.getCodeAttribute(); - if (ca == null) - return null; - - CodeIterator ci = ca.iterator(); - ConstPool pool = minfo.getConstPool(); - BasicBlock[] blocks = makeBlocks(ci, 0, ci.getCodeLength(), ca.getExceptionTable(), 0, pool); - boolean isStatic = (minfo.getAccessFlags() & AccessFlag.STATIC) != 0; - blocks[0].initFirstBlock(ca.getMaxStack(), ca.getMaxLocals(), - pool.getClassName(), minfo.getDescriptor(), - isStatic, minfo.isConstructor()); - return blocks; + sbuf.append("}"); } - /** - * Divides the given code fragment into basic blocks. - * - * @param begin the position where the basic block analysis starts. - * @param end exclusive. - * @param et the appended exception table entries. - * @param etOffset the offset added to the handlerPc entries in the exception table. - * @param pool the constant pool. - */ - public static BasicBlock[] makeBlocks(CodeIterator ci, int begin, int end, - ExceptionTable et, int etOffset, ConstPool pool) - throws BadBytecode - { - ci.begin(); - ci.move(begin); - ArrayList targets = new ArrayList(); - BasicBlock bb0 = new BasicBlock(begin); - bb0.inbound = 0; // the first block is not a branch target. - targets.add(bb0); - while (ci.hasNext()) { - int index = ci.next(); - if (index >= end) - break; - - int op = ci.byteAt(index); - if ((Opcode.IFEQ <= op && op <= Opcode.IF_ACMPNE) - || op == Opcode.IFNULL || op == Opcode.IFNONNULL) - targets.add(new BasicBlock(index + ci.s16bitAt(index + 1))); - else if (Opcode.GOTO <= op && op <= Opcode.LOOKUPSWITCH) - switch (op) { - case Opcode.GOTO : - case Opcode.JSR : - targets.add(new BasicBlock(index + ci.s16bitAt(index + 1))); - break; - // case Opcode.RET : - // throw new BadBytecode("ret at " + index); - case Opcode.TABLESWITCH : { - int pos = (index & ~3) + 4; - targets.add(new BasicBlock(index + ci.s32bitAt(pos))); // default branch target - int low = ci.s32bitAt(pos + 4); - int high = ci.s32bitAt(pos + 8); - int p = pos + 12; - int n = p + (high - low + 1) * 4; - while (p < n) { - targets.add(new BasicBlock(index + ci.s32bitAt(p))); - p += 4; - } - break; } - case Opcode.LOOKUPSWITCH : { - int pos = (index & ~3) + 4; - targets.add(new BasicBlock(index + ci.s32bitAt(pos))); // default branch target - int p = pos + 8 + 4; - int n = p + ci.s32bitAt(pos + 4) * 8; - while (p < n) { - targets.add(new BasicBlock(index + ci.s32bitAt(p))); - p += 8; - } - break; } - } - else if (op == Opcode.GOTO_W || op == Opcode.JSR_W) - targets.add(new BasicBlock(index + ci.s32bitAt(index + 1))); + static class Mark implements Comparable { + int position; + BasicBlock block; + BasicBlock[] jump; + boolean alwaysJmp; // true if a unconditional branch. + int size; // 0 unless the mark indicates RETURN etc. + Catch catcher; + + Mark(int p) { + position = p; + block = null; + jump = null; + alwaysJmp = false; + size = 0; + catcher = null; } - if (et != null) { - int i = et.size(); - while (--i >= 0) { - BasicBlock bb = new BasicBlock(et.startPc(i) + etOffset); - bb.inbound = 0; - targets.add(bb); - targets.add(new BasicBlock(et.handlerPc(i) + etOffset)); + public int compareTo(Object obj) { + if (obj instanceof Mark) { + int pos = ((Mark)obj).position; + return position - pos; } + + return -1; } - BasicBlock[] blocks = trimArray(targets, end); - markCatch(et, etOffset, blocks); - return blocks; + void setJump(BasicBlock[] bb, int s, boolean always) { + jump = bb; + size = s; + alwaysJmp = always; + } } - public int compareTo(Object obj) { - if (obj instanceof BasicBlock) { - int pos = ((BasicBlock)obj).position; - return position - pos; + public static class Maker { + /* Override these two methods if a subclass of BasicBlock must be + * instantiated. + */ + protected BasicBlock makeBlock(int pos) { + return new BasicBlock(pos); } - return -1; - } + protected BasicBlock[] makeArray(int size) { + return new BasicBlock[size]; + } - /** - * @param endPos exclusive - */ - private static BasicBlock[] trimArray(ArrayList targets, int endPos) { - Object[] targetArray = targets.toArray(); - int size = targetArray.length; - java.util.Arrays.sort(targetArray); - int s = 0; - int t0 = -1; - for (int i = 0; i < size; i++) { - int t = ((BasicBlock)targetArray[i]).position; - if (t != t0) { - s++; - t0 = t; - } + private BasicBlock[] makeArray(BasicBlock b) { + BasicBlock[] array = makeArray(1); + array[0] = b; + return array; } - BasicBlock[] results = new BasicBlock[s]; - BasicBlock bb0 = (BasicBlock)targetArray[0]; - results[0] = bb0; - t0 = bb0.position; - int j = 1; - for (int i = 1; i < size; i++) { - BasicBlock bb = (BasicBlock)targetArray[i]; - int t = bb.position; - if (t == t0) - results[j - 1].inbound += bb.inbound; - else { - results[j - 1].updateLength(t); - results[j++] = bb; - t0 = t; - } + private BasicBlock[] makeArray(BasicBlock b1, BasicBlock b2) { + BasicBlock[] array = makeArray(2); + array[0] = b1; + array[1] = b2; + return array; } - results[j - 1].updateLength(endPos); - return results; - } + public BasicBlock[] make(MethodInfo minfo) throws BadBytecode { + CodeAttribute ca = minfo.getCodeAttribute(); + if (ca == null) + return null; - private static void markCatch(ExceptionTable et, int etOffset, - BasicBlock[] blocks) - { - if (et == null) - return; - - int nblocks = blocks.length; - int n = et.size(); - for (int i = 0; i < n; i++) { - int start = et.startPc(i) + etOffset; - int end = et.endPc(i) + etOffset; - int handler = et.handlerPc(i) + etOffset; - int type = et.catchType(i); - for (int k = 0; k < nblocks; k++) { - BasicBlock bb = blocks[k]; - int p = bb.position; - if (start <= p && p < end) - bb.catchBlocks = new Branch(bb.catchBlocks, handler, type); - } + CodeIterator ci = ca.iterator(); + return make(ci, 0, ci.getCodeLength(), ca.getExceptionTable()); } - } - /** - * Initializes the first block by the given method descriptor. - * - * @param block the first basic block that this method initializes. - * @param className a dot-separated fully qualified class name. - * For example, javassist.bytecode.stackmap.BasicBlock. - * @param methodDesc method descriptor. - * @param isStatic true if the method is a static method. - * @param isConstructor true if the method is a constructor. - */ - void initFirstBlock(int maxStack, int maxLocals, String className, - String methodDesc, boolean isStatic, boolean isConstructor) - throws BadBytecode - { - if (methodDesc.charAt(0) != '(') - throw new BadBytecode("no method descriptor: " + methodDesc); - - stackTop = 0; - stackTypes = new TypeData[maxStack]; - TypeData[] locals = new TypeData[maxLocals]; - if (isConstructor) - locals[0] = new TypeData.UninitThis(className); - else if (!isStatic) - locals[0] = new TypeData.ClassName(className); - - int n = isStatic ? -1 : 0; - int i = 1; - try { - while ((i = descToTag(methodDesc, i, ++n, locals)) > 0) - if (locals[n].is2WordType()) - locals[++n] = TOP; + public BasicBlock[] make(CodeIterator ci, int begin, int end, + ExceptionTable et) + throws BadBytecode + { + HashMap marks = makeMarks(ci, begin, end, et); + BasicBlock[] bb = makeBlocks(marks); + addCatchers(bb, et); + return bb; } - catch (StringIndexOutOfBoundsException e) { - throw new BadBytecode("bad method descriptor: " - + methodDesc); + + /* Branch target + */ + private Mark makeMark(HashMap table, int pos) { + return makeMark0(table, pos, true, true); } - numLocals = n; - localsTypes = locals; - } + /* Branch instruction. + * size > 0 + */ + private Mark makeMark(HashMap table, int pos, BasicBlock[] jump, + int size, boolean always) { + Mark m = makeMark0(table, pos, false, false); + m.setJump(jump, size, always); + return m; + } - private static int descToTag(String desc, int i, - int n, TypeData[] types) - throws BadBytecode - { - int i0 = i; - int arrayDim = 0; - char c = desc.charAt(i); - if (c == ')') - return 0; - - while (c == '[') { - ++arrayDim; - c = desc.charAt(++i); + private Mark makeMark0(HashMap table, int pos, + boolean isBlockBegin, boolean isTarget) { + Integer p = new Integer(pos); + Mark m = (Mark)table.get(p); + if (m == null) { + m = new Mark(pos); + table.put(p, m); + } + + if (isBlockBegin) { + if (m.block == null) + m.block = makeBlock(pos); + + if (isTarget) + m.block.incoming++; + } + + return m; } - if (c == 'L') { - int i2 = desc.indexOf(';', ++i); - if (arrayDim > 0) - types[n] = new TypeData.ClassName(desc.substring(i0, ++i2)); - else - types[n] = new TypeData.ClassName(desc.substring(i0 + 1, ++i2 - 1) - .replace('/', '.')); - return i2; + private HashMap makeMarks(CodeIterator ci, int begin, int end, + ExceptionTable et) + throws BadBytecode + { + ci.begin(); + ci.move(begin); + HashMap marks = new HashMap(); + while (ci.hasNext()) { + int index = ci.next(); + if (index >= end) + break; + + int op = ci.byteAt(index); + if ((Opcode.IFEQ <= op && op <= Opcode.IF_ACMPNE) + || op == Opcode.IFNULL || op == Opcode.IFNONNULL) { + Mark to = makeMark(marks, index + ci.s16bitAt(index + 1)); + Mark next = makeMark(marks, index + 3); + makeMark(marks, index, makeArray(to.block, next.block), 3, false); + } + else if (Opcode.GOTO <= op && op <= Opcode.LOOKUPSWITCH) + switch (op) { + case Opcode.GOTO : + case Opcode.JSR : + makeGotoJsr(marks, index, index + ci.s16bitAt(index + 1), + op == Opcode.GOTO, 3); + break; + case Opcode.RET : + makeMark(marks, index, null, 1, true); + break; + case Opcode.TABLESWITCH : { + int pos = (index & ~3) + 4; + int low = ci.s32bitAt(pos + 4); + int high = ci.s32bitAt(pos + 8); + int ncases = high - low + 1; + BasicBlock[] to = makeArray(ncases + 1); + to[0] = makeMark(marks, index + ci.s32bitAt(pos)).block; // default branch target + int p = pos + 12; + int n = p + ncases * 4; + int k = 1; + while (p < n) { + to[k++] = makeMark(marks, index + ci.s32bitAt(p)).block; + p += 4; + } + makeMark(marks, index, to, n - index, true); + break; } + case Opcode.LOOKUPSWITCH : { + int pos = (index & ~3) + 4; + int ncases = ci.s32bitAt(pos + 4); + BasicBlock[] to = makeArray(ncases + 1); + to[0] = makeMark(marks, index + ci.s32bitAt(pos)).block; // default branch target + int p = pos + 8 + 4; + int n = p + ncases * 8 - 4; + int k = 1; + while (p < n) { + to[k++] = makeMark(marks, index + ci.s32bitAt(p)).block; + p += 8; + } + makeMark(marks, index, to, n - index, true); + break; } + } + else if ((Opcode.IRETURN <= op && op <= Opcode.RETURN) || op == Opcode.ATHROW) + makeMark(marks, index, null, 1, true); + else if (op == Opcode.GOTO_W || op == Opcode.JSR_W) + makeGotoJsr(marks, index, index + ci.s32bitAt(index + 1), + op == Opcode.GOTO_W, 5); + else if (op == Opcode.WIDE && ci.byteAt(index + 1) == Opcode.RET) + makeMark(marks, index, null, 1, true); + } + + if (et != null) { + int i = et.size(); + while (--i >= 0) { + makeMark0(marks, et.startPc(i), true, false); + makeMark(marks, et.handlerPc(i)); + } + } + + return marks; } - else if (arrayDim > 0) { - types[n] = new TypeData.ClassName(desc.substring(i0, ++i)); - return i; + + private void makeGotoJsr(HashMap marks, int pos, int target, boolean isGoto, int size) { + Mark to = makeMark(marks, target); + BasicBlock[] jumps; + if (isGoto) + jumps = makeArray(to.block); + else { + Mark next = makeMark(marks, pos + size); + jumps = makeArray(to.block, next.block); + } + + makeMark(marks, pos, jumps, size, isGoto); } - else { - TypeData t = toPrimitiveTag(c); - if (t == null) - throw new BadBytecode("bad method descriptor: " + desc); - types[n] = t; - return i + 1; + private BasicBlock[] makeBlocks(HashMap markTable) { + Mark[] marks = (Mark[])markTable.values() + .toArray(new Mark[markTable.size()]); + java.util.Arrays.sort(marks); + ArrayList blocks = new ArrayList(); + int i = 0; + BasicBlock prev; + if (marks.length > 0 && marks[0].position == 0 && marks[0].block != null) + prev = getBBlock(marks[i++]); + else + prev = makeBlock(0); + + blocks.add(prev); + while (i < marks.length) { + Mark m = marks[i++]; + BasicBlock bb = getBBlock(m); + if (bb == null) { + // the mark indicates a branch instruction + if (prev.length > 0) { + // the previous mark already has exits. + prev = makeBlock(prev.position + prev.length); + blocks.add(prev); + } + + prev.length = m.position + m.size - prev.position; + prev.exit = m.jump; + prev.stop = m.alwaysJmp; + } + else { + // the mark indicates a branch target + if (prev.length == 0) { + prev.length = m.position - prev.position; + bb.incoming++; + prev.exit = makeArray(bb); + } + else { + // the previous mark already has exits. + int prevPos = prev.position; + if (prevPos + prev.length < m.position) { + prev = makeBlock(prevPos + prev.length); + prev.length = m.position - prevPos; + // the incoming flow from dead code is not counted + // bb.incoming++; + prev.exit = makeArray(bb); + } + } + + blocks.add(bb); + prev = bb; + } + } + + return (BasicBlock[])blocks.toArray(makeArray(blocks.size())); } - } - private static TypeData toPrimitiveTag(char c) { - switch (c) { - case 'Z' : - case 'C' : - case 'B' : - case 'S' : - case 'I' : - return INTEGER; - case 'J' : - return LONG; - case 'F' : - return FLOAT; - case 'D' : - return DOUBLE; - case 'V' : - default : - return null; + private static BasicBlock getBBlock(Mark m) { + BasicBlock b = m.block; + if (b != null && m.size > 0) { + b.exit = m.jump; + b.length = m.size; + b.stop = m.alwaysJmp; + } + + return b; } - } - public static String getRetType(String desc) { - int i = desc.indexOf(')'); - if (i < 0) - return "java.lang.Object"; - - char c = desc.charAt(i + 1); - if (c == '[') - return desc.substring(i + 1); - else if (c == 'L') - return desc.substring(i + 2, desc.length() - 1).replace('/', '.'); - else - return "java.lang.Object"; + private void addCatchers(BasicBlock[] blocks, ExceptionTable et) + throws BadBytecode + { + if (et == null) + return; + + int i = et.size(); + while (--i >= 0) { + BasicBlock handler = find(blocks, et.handlerPc(i)); + int start = et.startPc(i); + int end = et.endPc(i); + int type = et.catchType(i); + handler.incoming--; + for (int k = 0; k < blocks.length; k++) { + BasicBlock bb = blocks[k]; + int iPos = bb.position; + if (start <= iPos && iPos < end) { + bb.toCatch = new Catch(handler, type, bb.toCatch); + handler.incoming++; + } + } + } + } } } diff --git a/src/main/javassist/bytecode/stackmap/Liveness.java b/src/main/javassist/bytecode/stackmap/Liveness.java new file mode 100644 index 00000000..8676b969 --- /dev/null +++ b/src/main/javassist/bytecode/stackmap/Liveness.java @@ -0,0 +1,364 @@ +/* + * Javassist, a Java-bytecode translator toolkit. + * Copyright (C) 1999-2006 Shigeru Chiba. 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.stackmap; + +import javassist.bytecode.*; + +public class Liveness { + protected static final byte UNKNOWN = 0; + protected static final byte READ = 1; + protected static final byte UPDATED = 2; + protected byte[] localsUsage; + + /** + * If true, all the arguments become alive within the whole method body. + * + * To correctly compute a stack map table, all the arguments must + * be alive (localsUsage[?] must be READ) at least in the first block. + */ + public static boolean useArgs = true; + + public void compute(CodeIterator ci, TypedBlock[] blocks, int maxLocals, + TypeData[] args) + throws BadBytecode + { + computeUsage(ci, blocks, maxLocals); + if (useArgs) + useAllArgs(blocks, args); + + computeLiveness1(blocks[0]); + while (hasChanged(blocks)) + computeLiveness2(blocks[0]); + } + + private void useAllArgs(TypedBlock[] blocks, TypeData[] args) { + for (int k = 0; k < blocks.length; k++) { + byte[] usage = blocks[k].localsUsage; + for (int i = 0; i < args.length; i++) + if (args[i] != TypeTag.TOP) + usage[i] = READ; + } + } + + static final int NOT_YET = 0; + static final int CHANGED_LAST = 1; + static final int DONE = 2; + static final int CHANGED_NOW = 3; + + private void computeLiveness1(TypedBlock tb) { + if (tb.updating) { + computeLiveness1u(tb); + return; + } + + if (tb.inputs != null) + return; + + tb.updating = true; + byte[] usage = tb.localsUsage; + int n = usage.length; + boolean[] in = new boolean[n]; + for (int i = 0; i < n; i++) + in[i] = usage[i] == READ; + + BasicBlock.Catch handlers = tb.toCatch; + while (handlers != null) { + TypedBlock h = (TypedBlock)handlers.body; + computeLiveness1(h); + for (int k = 0; k < n; k++) + if (h.inputs[k]) + in[k] = true; + + handlers = handlers.next; + } + + if (tb.exit != null) { + for (int i = 0; i < tb.exit.length; i++) { + TypedBlock e = (TypedBlock)tb.exit[i]; + computeLiveness1(e); + for (int k = 0; k < n; k++) + if (!in[k]) + in[k] = usage[k] == UNKNOWN && e.inputs[k]; + } + } + + tb.updating = false; + if (tb.inputs == null) { + tb.inputs = in; + tb.status = DONE; + } + else { + for (int i = 0; i < n; i++) + if (in[i] && !tb.inputs[i]) { + tb.inputs[i] = true; + tb.status = CHANGED_NOW; + } + } + } + + private void computeLiveness1u(TypedBlock tb) { + if (tb.inputs == null) { + byte[] usage = tb.localsUsage; + int n = usage.length; + boolean[] in = new boolean[n]; + for (int i = 0; i < n; i++) + in[i] = usage[i] == READ; + + tb.inputs = in; + tb.status = DONE; + } + } + + private void computeLiveness2(TypedBlock tb) { + if (tb.updating || tb.status >= DONE) + return; + + tb.updating = true; + if (tb.exit == null) + tb.status = DONE; + else { + boolean changed = false; + for (int i = 0; i < tb.exit.length; i++) { + TypedBlock e = (TypedBlock)tb.exit[i]; + computeLiveness2(e); + if (e.status != DONE) + changed = true; + } + + if (changed) { + changed = false; + byte[] usage = tb.localsUsage; + int n = usage.length; + for (int i = 0; i < tb.exit.length; i++) { + TypedBlock e = (TypedBlock)tb.exit[i]; + if (e.status != DONE) + for (int k = 0; k < n; k++) + if (!tb.inputs[k]) { + if (usage[k] == UNKNOWN && e.inputs[k]) { + tb.inputs[k] = true; + changed = true; + } + } + } + + tb.status = changed ? CHANGED_NOW : DONE; + } + else + tb.status = DONE; + } + + if (computeLiveness2except(tb)) + tb.status = CHANGED_NOW; + + tb.updating = false; + } + + private boolean computeLiveness2except(TypedBlock tb) { + BasicBlock.Catch handlers = tb.toCatch; + boolean changed = false; + while (handlers != null) { + TypedBlock h = (TypedBlock)handlers.body; + computeLiveness2(h); + if (h.status != DONE) { + boolean[] in = tb.inputs; + int n = in.length; + for (int k = 0; k < n; k++) + if (!in[k] && h.inputs[k]) { + in[k] = true; + changed = true; + } + } + + handlers = handlers.next; + } + + return changed; + } + + private boolean hasChanged(TypedBlock[] blocks) { + int n = blocks.length; + boolean changed = false; + for (int i = 0; i < n; i++) { + TypedBlock tb = blocks[i]; + if (tb.status == DONE) + tb.status = NOT_YET; + else { + tb.status = CHANGED_LAST; + changed = true; + } + } + + return changed; + } + + private void computeUsage(CodeIterator ci, TypedBlock[] blocks, int maxLocals) + throws BadBytecode + { + int n = blocks.length; + for (int i = 0; i < n; i++) { + TypedBlock tb = blocks[i]; + localsUsage = tb.localsUsage = new byte[maxLocals]; + int pos = tb.position; + analyze(ci, pos, pos + tb.length); + localsUsage = null; + } + } + + protected final void readLocal(int reg) { + if (localsUsage[reg] == UNKNOWN) + localsUsage[reg] = READ; + } + + protected final void writeLocal(int reg) { + if (localsUsage[reg] == UNKNOWN) + localsUsage[reg] = UPDATED; + } + + protected void analyze(CodeIterator ci, int begin, int end) + throws BadBytecode + { + ci.begin(); + ci.move(begin); + while (ci.hasNext()) { + int index = ci.next(); + if (index >= end) + break; + + int op = ci.byteAt(index); + if (op < 96) + if (op < 54) + doOpcode0_53(ci, index, op); + else + doOpcode54_95(ci, index, op); + else + if (op == Opcode.IINC) { + // this does not call writeLocal(). + readLocal(ci.byteAt(index + 1)); + } + else if (op == Opcode.WIDE) + doWIDE(ci, index); + } + } + + private void doOpcode0_53(CodeIterator ci, int pos, int op) { + switch (op) { + case Opcode.ILOAD : + case Opcode.LLOAD : + case Opcode.FLOAD : + case Opcode.DLOAD : + case Opcode.ALOAD : + readLocal(ci.byteAt(pos + 1)); + break; + case Opcode.ILOAD_0 : + case Opcode.ILOAD_1 : + case Opcode.ILOAD_2 : + case Opcode.ILOAD_3 : + readLocal(op - Opcode.ILOAD_0); + break; + case Opcode.LLOAD_0 : + case Opcode.LLOAD_1 : + case Opcode.LLOAD_2 : + case Opcode.LLOAD_3 : + readLocal(op - Opcode.LLOAD_0); + break; + case Opcode.FLOAD_0 : + case Opcode.FLOAD_1 : + case Opcode.FLOAD_2 : + case Opcode.FLOAD_3 : + readLocal(op - Opcode.FLOAD_0); + break; + case Opcode.DLOAD_0 : + case Opcode.DLOAD_1 : + case Opcode.DLOAD_2 : + case Opcode.DLOAD_3 : + readLocal(op - Opcode.DLOAD_0); + break; + case Opcode.ALOAD_0 : + case Opcode.ALOAD_1 : + case Opcode.ALOAD_2 : + case Opcode.ALOAD_3 : + readLocal(op - Opcode.ALOAD_0); + break; + } + } + + private void doOpcode54_95(CodeIterator ci, int pos, int op) { + switch (op) { + case Opcode.ISTORE : + case Opcode.LSTORE : + case Opcode.FSTORE : + case Opcode.DSTORE : + case Opcode.ASTORE : + writeLocal(ci.byteAt(pos + 1)); + break; + case Opcode.ISTORE_0 : + case Opcode.ISTORE_1 : + case Opcode.ISTORE_2 : + case Opcode.ISTORE_3 : + writeLocal(op - Opcode.ISTORE_0); + break; + case Opcode.LSTORE_0 : + case Opcode.LSTORE_1 : + case Opcode.LSTORE_2 : + case Opcode.LSTORE_3 : + writeLocal(op - Opcode.LSTORE_0); + break; + case Opcode.FSTORE_0 : + case Opcode.FSTORE_1 : + case Opcode.FSTORE_2 : + case Opcode.FSTORE_3 : + writeLocal(op - Opcode.FSTORE_0); + break; + case Opcode.DSTORE_0 : + case Opcode.DSTORE_1 : + case Opcode.DSTORE_2 : + case Opcode.DSTORE_3 : + writeLocal(op - Opcode.DSTORE_0); + break; + case Opcode.ASTORE_0 : + case Opcode.ASTORE_1 : + case Opcode.ASTORE_2 : + case Opcode.ASTORE_3 : + writeLocal(op - Opcode.ASTORE_0); + break; + } + } + + private void doWIDE(CodeIterator ci, int pos) throws BadBytecode { + int op = ci.byteAt(pos + 1); + int var = ci.u16bitAt(pos + 2); + switch (op) { + case Opcode.ILOAD : + case Opcode.LLOAD : + case Opcode.FLOAD : + case Opcode.DLOAD : + case Opcode.ALOAD : + readLocal(var); + break; + case Opcode.ISTORE : + case Opcode.LSTORE : + case Opcode.FSTORE : + case Opcode.DSTORE : + case Opcode.ASTORE : + writeLocal(var); + break; + case Opcode.IINC : + readLocal(var); + // this does not call writeLocal(). + break; + } + } +} diff --git a/src/main/javassist/bytecode/stackmap/MapMaker.java b/src/main/javassist/bytecode/stackmap/MapMaker.java index cbb238c9..17725903 100644 --- a/src/main/javassist/bytecode/stackmap/MapMaker.java +++ b/src/main/javassist/bytecode/stackmap/MapMaker.java @@ -22,11 +22,7 @@ import javassist.bytecode.*; * Stack map maker. */ public class MapMaker extends Tracer { - private boolean moveon; // used for returning another value from doOpcode(). - private boolean loopDetected; - private int iteration; - private BasicBlock[] blocks; - + /* public static void main(String[] args) throws Exception { boolean useMain2 = args[0].equals("0"); if (useMain2 && args.length > 1) { @@ -49,7 +45,7 @@ public class MapMaker extends Tracer { MethodInfo minfo = (MethodInfo)minfos.get(i); CodeAttribute ca = minfo.getCodeAttribute(); if (ca != null) - ca.setAttribute(MapMaker.getMap(cp, minfo)); + ca.setAttribute(make(cp, minfo)); } cc.writeFile("tmp"); @@ -60,253 +56,162 @@ public class MapMaker extends Tracer { //javassist.CtClass cc = cp.get(args[1]); javassist.CtClass cc = cp.makeClass(new java.io.FileInputStream(args[1])); MethodInfo minfo; - MapMaker mm; if (args[2].equals("_init_")) - // minfo = cc.getDeclaredConstructors()[0].getMethodInfo(); - minfo = cc.getClassInitializer().getMethodInfo(); + minfo = cc.getDeclaredConstructors()[0].getMethodInfo(); + // minfo = cc.getClassInitializer().getMethodInfo(); else minfo = cc.getDeclaredMethod(args[2]).getMethodInfo(); - mm = makeMapMaker(cp, minfo); - if (mm == null) - System.out.println("single basic block"); - else { - BasicBlock[] blocks = mm.getBlocks(); - for (int i = 0; i < blocks.length; i++) - System.out.println(blocks[i]); - - StackMapTable smt = mm.toStackMap(); + CodeAttribute ca = minfo.getCodeAttribute(); + if (ca == null) { + System.out.println("abstarct method"); + return; } + + TypedBlock[] blocks = TypedBlock.makeBlocks(minfo, ca, false); + MapMaker mm = new MapMaker(cp, minfo, ca); + mm.make(blocks, ca.getCode()); + for (int i = 0; i < blocks.length; i++) + System.out.println(blocks[i]); } + */ /** * Computes the stack map table of the given method and returns it. * It returns null if the given method does not have to have a * stack map table. */ - public static StackMapTable getMap(ClassPool classes, MethodInfo minfo) - throws BadBytecode - { - MapMaker mm = makeMapMaker(classes, minfo); - if (mm == null) - return null; - else - return mm.toStackMap(); - } - - /** - * Makes basic blocks with stack maps. If the number of the basic blocks - * is one, this method returns null. If the given method info does not - * include a code attribute, this method also returns null. - */ - public static MapMaker makeMapMaker(ClassPool classes, MethodInfo minfo) + public static StackMapTable make(ClassPool classes, MethodInfo minfo) throws BadBytecode { CodeAttribute ca = minfo.getCodeAttribute(); if (ca == null) return null; - CodeIterator ci = ca.iterator(); - ConstPool pool = minfo.getConstPool(); - ExceptionTable et = ca.getExceptionTable(); - BasicBlock[] blocks = BasicBlock.makeBlocks(ci, 0, ci.getCodeLength(), - et, 0, pool); - if (blocks.length < 2) - if (blocks.length == 0 || blocks[0].inbound < 1) - return null; - - boolean isStatic = (minfo.getAccessFlags() & AccessFlag.STATIC) != 0; - int maxStack = ca.getMaxStack(); - int maxLocals = ca.getMaxLocals(); - BasicBlock top = blocks[0]; - String desc = minfo.getDescriptor(); - top.initFirstBlock(maxStack, maxLocals, pool.getClassName(), desc, - isStatic, minfo.isConstructor()); - String retType = BasicBlock.getRetType(desc); - MapMaker mm = new MapMaker(classes, pool, maxStack, maxLocals, - blocks, retType, blocks[0], 0); - mm.make(ca.getCode(), et); - return mm; - } + TypedBlock[] blocks = TypedBlock.makeBlocks(minfo, ca, true); + if (blocks == null) + return null; - /** - * Constructs a tracer. - */ - MapMaker(ClassPool classes, ConstPool cp, - int maxStack, int maxLocals, BasicBlock[] bb, - String retType, BasicBlock init, int iterate) - { - this(classes, cp, maxStack, maxLocals, bb, retType, iterate); - TypeData[] srcTypes = init.localsTypes; - copyFrom(srcTypes.length, srcTypes, this.localsTypes); + MapMaker mm = new MapMaker(classes, minfo, ca); + mm.make(blocks, ca.getCode()); + return mm.toStackMap(blocks); } - private MapMaker(ClassPool classes, ConstPool cp, - int maxStack, int maxLocals, BasicBlock[] bb, - String retType, int iterateNo) - { - super(classes, cp, maxStack, maxLocals, retType); - blocks = bb; - loopDetected = false; - iteration = iterateNo; + public MapMaker(ClassPool classes, MethodInfo minfo, CodeAttribute ca) { + super(classes, minfo.getConstPool(), + ca.getMaxStack(), ca.getMaxLocals(), + TypedBlock.getRetType(minfo.getDescriptor())); } - public BasicBlock[] getBlocks() { return blocks; } + protected MapMaker(MapMaker old, boolean copyStack) { + super(old, copyStack); + } /** - * Runs an analyzer. + * Runs an analyzer (Phase 1 and 2). */ - void make(byte[] code, ExceptionTable et) throws BadBytecode { - blocks[0].version = iteration; - make(code, blocks[0]); - if (loopDetected) { - blocks[0].version = ++iteration; - make(code, blocks[0]); - } + void make(TypedBlock[] blocks, byte[] code) + throws BadBytecode + { + TypedBlock first = blocks[0]; + TypeData[] srcTypes = first.localsTypes; + copyFrom(srcTypes.length, srcTypes, this.localsTypes); + make(code, first); int n = blocks.length; for (int i = 0; i < n; i++) evalExpected(blocks[i]); } - // Phase 1: Code Tracing + // Phase 1 - private void make(byte[] code, BasicBlock bb) + private void make(byte[] code, TypedBlock tb) throws BadBytecode { - int pos = bb.position; - int end = pos + bb.length; - traceExceptions(code, bb.catchBlocks); - moveon = true; - while (moveon && pos < end) - pos += doOpcode(pos, code); - - if (moveon && pos < code.length) { - this.copyFrom(this); - nextBlock(pos, code, 0); + BasicBlock.Catch handlers = tb.toCatch; + while (handlers != null) { + traceException(code, handlers); + handlers = handlers.next; } - } - private void nextBlock(int pos, byte[] code, int offset) throws BadBytecode { - BasicBlock bb = BasicBlock.find(blocks, pos + offset); - if (bb.alreadySet(iteration)) { - mergeMap(stackTypes, bb.stackTypes); - mergeMap(localsTypes, bb.localsTypes); - mergeUsage(bb); - } - else { - recordStackMap(bb); - bb.version = iteration; - MapMaker maker = new MapMaker(classPool, cpool, stackTypes.length, - localsTypes.length, blocks, returnType, iteration); - maker.copyFrom(this); - maker.make(code, bb); - recordUsage(bb, maker); - if (maker.loopDetected) - this.loopDetected = true; + int pos = tb.position; + int end = pos + tb.length; + while (pos < end) + pos += doOpcode(pos, code); + + if (tb.exit != null) { + for (int i = 0; i < tb.exit.length; i++) { + TypedBlock e = (TypedBlock)tb.exit[i]; + if (e.alreadySet()) + mergeMap(e, true); + else { + recordStackMap(e); + MapMaker maker = new MapMaker(this, true); + maker.make(code, e); + } + } } } - private void traceExceptions(byte[] code, BasicBlock.Branch branches) + private void traceException(byte[] code, TypedBlock.Catch handler) throws BadBytecode { - while (branches != null) { - int pos = branches.target; - BasicBlock bb = BasicBlock.find(blocks, pos); - if (bb.alreadySet(iteration)) { - mergeMap(localsTypes, bb.localsTypes); - mergeUsage(bb); - } - else { - recordStackMap(bb, branches.typeIndex); - bb.version = iteration; - MapMaker maker = new MapMaker(classPool, cpool, stackTypes.length, - localsTypes.length, blocks, returnType, iteration); - - /* the following code is equivalent to maker.copyFrom(this) - * except stackTypes are not copied. - */ - maker.stackTypes[0] = bb.stackTypes[0].getSelf(); - maker.stackTop = 1; - TypeData[] srcTypes = this.localsTypes; - copyFrom(srcTypes.length, srcTypes, maker.localsTypes); - - maker.make(code, bb); - recordUsage(bb, maker); - if (maker.loopDetected) - this.loopDetected = true; - } - - branches = branches.next; + TypedBlock tb = (TypedBlock)handler.body; + if (tb.alreadySet()) + mergeMap(tb, false); + else { + recordStackMap(tb, handler.typeIndex); + MapMaker maker = new MapMaker(this, false); + + /* the following code is equivalent to maker.copyFrom(this) + * except stackTypes are not copied. + */ + maker.stackTypes[0] = tb.stackTypes[0].getSelf(); + maker.stackTop = 1; + maker.make(code, tb); } } - private static void mergeMap(TypeData[] srcTypes, TypeData[] destTypes) { - int n = srcTypes.length; - for (int i = 0; i < n; i++) { - TypeData s = srcTypes[i]; - TypeData d = destTypes[i]; - boolean sIsObj = false; - boolean dIsObj = false; - // s or b is null if it is TOP. - if (s != TOP && s.isObjectType()) - sIsObj = true; - - if (d != TOP && d.isObjectType()) - dIsObj = true; - - if (sIsObj && dIsObj) - d.merge(s); - else if (s != d) - destTypes[i] = TOP; + private void mergeMap(TypedBlock dest, boolean mergeStack) { + boolean[] inputs = dest.inputs; + int n = inputs.length; + for (int i = 0; i < n; i++) + if (inputs[i]) + merge(localsTypes[i], dest.localsTypes[i]); + + if (mergeStack) { + n = stackTop; + for (int i = 0; i < n; i++) + merge(stackTypes[i], dest.stackTypes[i]); } } - private void copyFrom(MapMaker src) { - int sp = src.stackTop; - this.stackTop = sp; - copyFrom(sp, src.stackTypes, this.stackTypes); - TypeData[] srcTypes = src.localsTypes; - copyFrom(srcTypes.length, srcTypes, this.localsTypes); - } + private void merge(TypeData td, TypeData target) { + boolean tdIsObj = false; + boolean targetIsObj = false; + // td or target is null if it is TOP. + if (td != TOP && td.isObjectType()) + tdIsObj = true; - private static int copyFrom(int n, TypeData[] srcTypes, TypeData[] destTypes) { - int k = -1; - for (int i = 0; i < n; i++) { - TypeData t = srcTypes[i]; - destTypes[i] = t == null ? null : t.getSelf(); - if (t != TOP) - if (t.is2WordType()) - k = i + 1; - else - k = i; - } + if (target != TOP && target.isObjectType()) + targetIsObj = true; - return k + 1; + if (tdIsObj && targetIsObj) + target.merge(td); } - private void recordStackMap(BasicBlock target) + private void recordStackMap(TypedBlock target) throws BadBytecode { - int n = localsTypes.length; - TypeData[] tLocalsTypes = new TypeData[n]; - int k = copyFrom(n, localsTypes, tLocalsTypes); - - n = stackTypes.length; - TypeData[] tStackTypes = new TypeData[n]; + TypeData[] tStackTypes = new TypeData[stackTypes.length]; int st = stackTop; copyFrom(st, stackTypes, tStackTypes); - - target.setStackMap(st, tStackTypes, k, tLocalsTypes); + recordStackMap0(target, st, tStackTypes); } - private void recordStackMap(BasicBlock target, int exceptionType) + private void recordStackMap(TypedBlock target, int exceptionType) throws BadBytecode { - int n = localsTypes.length; - TypeData[] tLocalsTypes = new TypeData[n]; - int k = copyFrom(n, localsTypes, tLocalsTypes); - String type; if (exceptionType == 0) type = "java.lang.Throwable"; @@ -316,44 +221,27 @@ public class MapMaker extends Tracer { TypeData[] tStackTypes = new TypeData[stackTypes.length]; tStackTypes[0] = new TypeData.ClassName(type); - target.setStackMap(1, tStackTypes, k, tLocalsTypes); + recordStackMap0(target, 1, tStackTypes); } - private void recordUsage(BasicBlock target, MapMaker next) { - int[] nextUsage = next.localsUsage; - TypeData[] tData = target.localsTypes; - int n = tData.length; - for (int i = blocks[0].numLocals; i < n; i++) - if (nextUsage[i] == READ) - readLocal(i); - else - tData[i] = TOP; + private void recordStackMap0(TypedBlock target, int st, TypeData[] tStackTypes) + throws BadBytecode + { + int n = localsTypes.length; + TypeData[] tLocalsTypes = new TypeData[n]; + int k = copyFrom(n, localsTypes, tLocalsTypes); - int[] usage = new int[nextUsage.length]; - n = usage.length; + boolean[] inputs = target.inputs; for (int i = 0; i < n; i++) - usage[i] = nextUsage[i]; - - target.localsUsage = usage; - } + if (!inputs[i]) + tLocalsTypes[i] = TOP; - private void mergeUsage(BasicBlock target) { - int[] usage = target.localsUsage; - if (usage == null) { - // detected a loop. - loopDetected = true; - } - else { - int n = usage.length; - for (int i = 0; i < n; i++) - if (usage[i] == READ) - readLocal(i); - } + target.setStackMap(st, tStackTypes, k, tLocalsTypes); } // Phase 2 - void evalExpected(BasicBlock target) throws BadBytecode { + void evalExpected(TypedBlock target) throws BadBytecode { ClassPool cp = classPool; evalExpected(cp, target.stackTop, target.stackTypes); TypeData[] types = target.localsTypes; @@ -373,20 +261,19 @@ public class MapMaker extends Tracer { // Phase 3 - public StackMapTable toStackMap() { - BasicBlock[] blocks = this.blocks; + public StackMapTable toStackMap(TypedBlock[] blocks) { StackMapTable.Writer writer = new StackMapTable.Writer(32); int n = blocks.length; - BasicBlock prev = blocks[0]; + TypedBlock prev = blocks[0]; int offsetDelta = prev.length; - if (prev.inbound > 0) { // the first instruction is a branch target. + if (prev.incoming > 0) { // the first instruction is a branch target. writer.sameFrame(0); offsetDelta--; } for (int i = 1; i < n; i++) { - BasicBlock bb = blocks[i]; - if (bb.inbound > 0) { + TypedBlock bb = blocks[i]; + if (isTarget(bb, blocks[i - 1])) { bb.resetNumLocals(); int diffL = stackMapDiff(prev.numLocals, prev.localsTypes, bb.numLocals, bb.localsTypes); @@ -402,8 +289,21 @@ public class MapMaker extends Tracer { return writer.toStackMapTable(cpool); } - private void toStackMapBody(StackMapTable.Writer writer, BasicBlock bb, - int diffL, int offsetDelta, BasicBlock prev) { + /** + * Returns true if cur is a branch target. + */ + private boolean isTarget(TypedBlock cur, TypedBlock prev) { + int in = cur.incoming; + if (in > 1) + return true; + else if (in < 1) + return false; + + return prev.stop; + } + + private void toStackMapBody(StackMapTable.Writer writer, TypedBlock bb, + int diffL, int offsetDelta, TypedBlock prev) { // if diffL is -100, two TypeData arrays do not share // any elements. @@ -521,44 +421,4 @@ public class MapMaker extends Tracer { return num; } - - // Branch actions - - protected void visitBranch(int pos, byte[] code, int offset) throws BadBytecode { - nextBlock(pos, code, offset); - } - - protected void visitGoto(int pos, byte[] code, int offset) throws BadBytecode { - nextBlock(pos, code, offset); - moveon = false; - } - - protected void visitTableSwitch(int pos, byte[] code, int n, int offsetPos, int defaultOffset) - throws BadBytecode - { - nextBlock(pos, code, defaultOffset); - for (int i = 0; i < n; i++) { - nextBlock(pos, code, ByteArray.read32bit(code, offsetPos)); - offsetPos += 4; - } - - moveon = false; - } - - protected void visitLookupSwitch(int pos, byte[] code, int n, int pairsPos, int defaultOffset) - throws BadBytecode - { - nextBlock(pos, code, defaultOffset); - pairsPos += 4; - for (int i = 0; i < n; i++) { - nextBlock(pos, code, ByteArray.read32bit(code, pairsPos)); - pairsPos += 8; - } - - moveon = false; - } - - protected void visitReturn(int pos, byte[] code) { moveon = false; } - - protected void visitThrow(int pos, byte[] code) { moveon = false; } } diff --git a/src/main/javassist/bytecode/stackmap/Tracer.java b/src/main/javassist/bytecode/stackmap/Tracer.java index 0107b8e9..bae3ae16 100644 --- a/src/main/javassist/bytecode/stackmap/Tracer.java +++ b/src/main/javassist/bytecode/stackmap/Tracer.java @@ -36,11 +36,6 @@ public abstract class Tracer implements TypeTag { protected TypeData[] stackTypes; protected TypeData[] localsTypes; - static final int UNKNOWN = 0; - static final int READ = 1; - static final int UPDATED = 2; - protected int[] localsUsage; - public Tracer(ClassPool classes, ConstPool cp, int maxStack, int maxLocals, String retType) { classPool = classes; @@ -49,21 +44,37 @@ public abstract class Tracer implements TypeTag { stackTop = 0; stackTypes = new TypeData[maxStack]; localsTypes = new TypeData[maxLocals]; - localsUsage = new int[maxLocals]; } - /* If the type is LONG or DOUBLE, - * the next local variable is also read. - * IINC (or WIDE IINC) calls only readLocal() but it does not call writeLocal(). - */ - protected final void readLocal(int reg) { - if (localsUsage[reg] == UNKNOWN) - localsUsage[reg] = READ; - } + public Tracer(Tracer t, boolean copyStack) { + classPool = t.classPool; + cpool = t.cpool; + returnType = t.returnType; + + stackTop = t.stackTop; + int size = t.stackTypes.length; + stackTypes = new TypeData[size]; + if (copyStack) + copyFrom(t.stackTop, t.stackTypes, stackTypes); + + int size2 = t.localsTypes.length; + localsTypes = new TypeData[size2]; + copyFrom(size2, t.localsTypes, localsTypes); + } + + protected static int copyFrom(int n, TypeData[] srcTypes, TypeData[] destTypes) { + int k = -1; + for (int i = 0; i < n; i++) { + TypeData t = srcTypes[i]; + destTypes[i] = t == TOP ? TOP : t.getSelf(); + if (t != TOP) + if (t.is2WordType()) + k = i + 1; + else + k = i; + } - protected final void writeLocal(int reg) { - if (localsUsage[reg] == UNKNOWN) - localsUsage[reg] = UPDATED; + return k + 1; } /** @@ -192,7 +203,6 @@ public abstract class Tracer implements TypeTag { case Opcode.ILOAD_2 : case Opcode.ILOAD_3 : stackTypes[stackTop++] = INTEGER; - readLocal(op - Opcode.ILOAD_0); break; case Opcode.LLOAD_0 : case Opcode.LLOAD_1 : @@ -200,14 +210,12 @@ public abstract class Tracer implements TypeTag { case Opcode.LLOAD_3 : stackTypes[stackTop++] = LONG; stackTypes[stackTop++] = TOP; - readLocal(op - Opcode.LLOAD_0); break; case Opcode.FLOAD_0 : case Opcode.FLOAD_1 : case Opcode.FLOAD_2 : case Opcode.FLOAD_3 : stackTypes[stackTop++] = FLOAT; - readLocal(op - Opcode.FLOAD_0); break; case Opcode.DLOAD_0 : case Opcode.DLOAD_1 : @@ -215,7 +223,6 @@ public abstract class Tracer implements TypeTag { case Opcode.DLOAD_3 : stackTypes[stackTop++] = DOUBLE; stackTypes[stackTop++] = TOP; - readLocal(op - Opcode.DLOAD_0); break; case Opcode.ALOAD_0 : case Opcode.ALOAD_1 : @@ -223,7 +230,6 @@ public abstract class Tracer implements TypeTag { case Opcode.ALOAD_3 : reg = op - Opcode.ALOAD_0; stackTypes[stackTop++] = localsTypes[reg]; - readLocal(reg); break; case Opcode.IALOAD : stackTypes[--stackTop - 1] = INTEGER; @@ -293,13 +299,11 @@ public abstract class Tracer implements TypeTag { if (type.is2WordType()) stackTypes[stackTop++] = TOP; - readLocal(localVar); return 2; } private int doALOAD(int localVar) { // int localVar, TypeData type) { stackTypes[stackTop++] = localsTypes[localVar]; - readLocal(localVar); return 2; } @@ -323,7 +327,6 @@ public abstract class Tracer implements TypeTag { case Opcode.ISTORE_3 : { int var = op - Opcode.ISTORE_0; localsTypes[var] = INTEGER; - writeLocal(var); stackTop--; } break; case Opcode.LSTORE_0 : @@ -333,7 +336,6 @@ public abstract class Tracer implements TypeTag { { int var = op - Opcode.LSTORE_0; localsTypes[var] = LONG; localsTypes[var + 1] = TOP; - writeLocal(var); stackTop -= 2; } break; case Opcode.FSTORE_0 : @@ -342,7 +344,6 @@ public abstract class Tracer implements TypeTag { case Opcode.FSTORE_3 : { int var = op - Opcode.FSTORE_0; localsTypes[var] = FLOAT; - writeLocal(var); stackTop--; } break; case Opcode.DSTORE_0 : @@ -352,7 +353,6 @@ public abstract class Tracer implements TypeTag { { int var = op - Opcode.DSTORE_0; localsTypes[var] = DOUBLE; localsTypes[var + 1] = TOP; - writeLocal(var); stackTop -= 2; } break; case Opcode.ASTORE_0 : @@ -424,7 +424,6 @@ public abstract class Tracer implements TypeTag { private int doXSTORE(int index, TypeData type) { stackTop--; - writeLocal(index); localsTypes[index] = type; if (type.is2WordType()) { stackTop--; @@ -436,7 +435,6 @@ public abstract class Tracer implements TypeTag { private int doASTORE(int index) { stackTop--; - writeLocal(index); // implicit upcast might be done. localsTypes[index] = stackTypes[stackTop].copy(); @@ -461,7 +459,6 @@ public abstract class Tracer implements TypeTag { switch (op) { case Opcode.IINC : - readLocal(code[pos + 1] & 0xff); // this does not call writeLocal(). return 3; case Opcode.I2L : @@ -705,7 +702,6 @@ public abstract class Tracer implements TypeTag { int index = ByteArray.readU16bit(code, pos + 2); return doASTORE(index); } case Opcode.IINC : - readLocal(ByteArray.readU16bit(code, pos + 2)); // this does not call writeLocal(). return 6; case Opcode.RET : diff --git a/src/main/javassist/bytecode/stackmap/TypeData.java b/src/main/javassist/bytecode/stackmap/TypeData.java index 2f9c780b..0069f0fa 100644 --- a/src/main/javassist/bytecode/stackmap/TypeData.java +++ b/src/main/javassist/bytecode/stackmap/TypeData.java @@ -122,7 +122,7 @@ public abstract class TypeData { protected static abstract class TypeName extends TypeData { protected ArrayList equivalences; - private String expectedName; + protected String expectedName; private CtClass cache; private boolean evalDone; @@ -275,6 +275,8 @@ public abstract class TypeData { } } + /* See also NullType.getExpected(). + */ public String getExpected() throws BadBytecode { ArrayList equiv = equivalences; if (equiv.size() == 1) @@ -359,6 +361,19 @@ public abstract class TypeData { else return super.getTypeData2(cp, type); } + + public String getExpected() throws BadBytecode { + String en = expectedName; + if (en == null) { + ArrayList equiv = equivalences; + if (equiv.size() == 1) + return getName(); + else + return "java.lang.Object"; + } + else + return en; + } } /** diff --git a/src/main/javassist/bytecode/stackmap/TypedBlock.java b/src/main/javassist/bytecode/stackmap/TypedBlock.java new file mode 100644 index 00000000..9d908755 --- /dev/null +++ b/src/main/javassist/bytecode/stackmap/TypedBlock.java @@ -0,0 +1,231 @@ +package javassist.bytecode.stackmap; + +import javassist.bytecode.*; + +public class TypedBlock extends BasicBlock { + public int stackTop, numLocals; + public TypeData[] stackTypes, localsTypes; + + // set by a Liveness object. + public boolean[] inputs; + public boolean updating; + public int status; + public byte[] localsUsage; + + /** + * Divides the method body into basic blocks. + * The type information of the first block is initialized. + * + * @param optmize if it is true and the method does not include + * branches, this method returns null. + */ + public static TypedBlock[] makeBlocks(MethodInfo minfo, CodeAttribute ca, + boolean optimize) + throws BadBytecode + { + TypedBlock[] blocks = (TypedBlock[])new Maker().make(minfo); + if (optimize && blocks.length < 2) + if (blocks.length == 0 || blocks[0].incoming == 0) + return null; + + ConstPool pool = minfo.getConstPool(); + boolean isStatic = (minfo.getAccessFlags() & AccessFlag.STATIC) != 0; + blocks[0].initFirstBlock(ca.getMaxStack(), ca.getMaxLocals(), + pool.getClassName(), minfo.getDescriptor(), + isStatic, minfo.isConstructor()); + new Liveness().compute(ca.iterator(), blocks, ca.getMaxLocals(), + blocks[0].localsTypes); + return blocks; + } + + protected TypedBlock(int pos) { + super(pos); + localsTypes = null; + inputs = null; + updating = false; + } + + protected void toString2(StringBuffer sbuf) { + super.toString2(sbuf); + sbuf.append(",\n stack={"); + printTypes(sbuf, stackTop, stackTypes); + sbuf.append("}, locals={"); + printTypes(sbuf, numLocals, localsTypes); + sbuf.append("}, inputs={"); + if (inputs != null) + for (int i = 0; i < inputs.length; i++) + sbuf.append(inputs[i] ? "1, " : "0, "); + + sbuf.append('}'); + } + + private void printTypes(StringBuffer sbuf, int size, + TypeData[] types) { + if (types == null) + return; + + for (int i = 0; i < size; i++) { + if (i > 0) + sbuf.append(", "); + + TypeData td = types[i]; + sbuf.append(td == null ? "<>" : td.toString()); + } + } + + public boolean alreadySet() { + return localsTypes != null; + } + + public void setStackMap(int st, TypeData[] stack, int nl, TypeData[] locals) + throws BadBytecode + { + stackTop = st; + stackTypes = stack; + numLocals = nl; + localsTypes = locals; + } + + /* + * Computes the correct value of numLocals. + */ + public void resetNumLocals() { + if (localsTypes != null) { + int nl = localsTypes.length; + while (nl > 0 && localsTypes[nl - 1] == TypeTag.TOP) { + if (nl > 1) { + TypeData td = localsTypes[nl - 2]; + if (td == TypeTag.LONG || td == TypeTag.DOUBLE) + break; + } + + --nl; + } + + numLocals = nl; + } + } + + public static class Maker extends BasicBlock.Maker { + protected BasicBlock makeBlock(int pos) { + return new TypedBlock(pos); + } + + protected BasicBlock[] makeArray(int size) { + return new TypedBlock[size]; + } + } + + /** + * Initializes the first block by the given method descriptor. + * + * @param block the first basic block that this method initializes. + * @param className a dot-separated fully qualified class name. + * For example, javassist.bytecode.stackmap.BasicBlock. + * @param methodDesc method descriptor. + * @param isStatic true if the method is a static method. + * @param isConstructor true if the method is a constructor. + */ + void initFirstBlock(int maxStack, int maxLocals, String className, + String methodDesc, boolean isStatic, boolean isConstructor) + throws BadBytecode + { + if (methodDesc.charAt(0) != '(') + throw new BadBytecode("no method descriptor: " + methodDesc); + + stackTop = 0; + stackTypes = new TypeData[maxStack]; + TypeData[] locals = new TypeData[maxLocals]; + if (isConstructor) + locals[0] = new TypeData.UninitThis(className); + else if (!isStatic) + locals[0] = new TypeData.ClassName(className); + + int n = isStatic ? -1 : 0; + int i = 1; + try { + while ((i = descToTag(methodDesc, i, ++n, locals)) > 0) + if (locals[n].is2WordType()) + locals[++n] = TypeTag.TOP; + } + catch (StringIndexOutOfBoundsException e) { + throw new BadBytecode("bad method descriptor: " + + methodDesc); + } + + numLocals = n; + localsTypes = locals; + } + + private static int descToTag(String desc, int i, + int n, TypeData[] types) + throws BadBytecode + { + int i0 = i; + int arrayDim = 0; + char c = desc.charAt(i); + if (c == ')') + return 0; + + while (c == '[') { + ++arrayDim; + c = desc.charAt(++i); + } + + if (c == 'L') { + int i2 = desc.indexOf(';', ++i); + if (arrayDim > 0) + types[n] = new TypeData.ClassName(desc.substring(i0, ++i2)); + else + types[n] = new TypeData.ClassName(desc.substring(i0 + 1, ++i2 - 1) + .replace('/', '.')); + return i2; + } + else if (arrayDim > 0) { + types[n] = new TypeData.ClassName(desc.substring(i0, ++i)); + return i; + } + else { + TypeData t = toPrimitiveTag(c); + if (t == null) + throw new BadBytecode("bad method descriptor: " + desc); + + types[n] = t; + return i + 1; + } + } + + private static TypeData toPrimitiveTag(char c) { + switch (c) { + case 'Z' : + case 'C' : + case 'B' : + case 'S' : + case 'I' : + return TypeTag.INTEGER; + case 'J' : + return TypeTag.LONG; + case 'F' : + return TypeTag.FLOAT; + case 'D' : + return TypeTag.DOUBLE; + case 'V' : + default : + return null; + } + } + + public static String getRetType(String desc) { + int i = desc.indexOf(')'); + if (i < 0) + return "java.lang.Object"; + + char c = desc.charAt(i + 1); + if (c == '[') + return desc.substring(i + 1); + else if (c == 'L') + return desc.substring(i + 2, desc.length() - 1).replace('/', '.'); + else + return "java.lang.Object"; + } +} -- 2.39.5