Author: kohsuke Date: Wed Dec 28 14:53:35 2005 New Revision: 359657 URL: http://svn.apache.org/viewcvs?rev=359657&view=rev Log: improved the readability by introducing a class that represents an execution sequence. previously it was represented as an ArrayList, and therefore it was harder to understand what it was doing, and slower, because it involved a lot of cloning.
Added: jakarta/commons/sandbox/javaflow/trunk/src/java/org/apache/commons/javaflow/bytecode/transformation/bcel/analyser/ExecutionPath.java (with props) Modified: jakarta/commons/sandbox/javaflow/trunk/src/java/org/apache/commons/javaflow/bytecode/transformation/bcel/BcelClassTransformer.java jakarta/commons/sandbox/javaflow/trunk/src/java/org/apache/commons/javaflow/bytecode/transformation/bcel/analyser/ControlFlowGraph.java jakarta/commons/sandbox/javaflow/trunk/src/java/org/apache/commons/javaflow/bytecode/transformation/bcel/analyser/InstructionContext.java Modified: jakarta/commons/sandbox/javaflow/trunk/src/java/org/apache/commons/javaflow/bytecode/transformation/bcel/BcelClassTransformer.java URL: http://svn.apache.org/viewcvs/jakarta/commons/sandbox/javaflow/trunk/src/java/org/apache/commons/javaflow/bytecode/transformation/bcel/BcelClassTransformer.java?rev=359657&r1=359656&r2=359657&view=diff ============================================================================== --- jakarta/commons/sandbox/javaflow/trunk/src/java/org/apache/commons/javaflow/bytecode/transformation/bcel/BcelClassTransformer.java (original) +++ jakarta/commons/sandbox/javaflow/trunk/src/java/org/apache/commons/javaflow/bytecode/transformation/bcel/BcelClassTransformer.java Wed Dec 28 14:53:35 2005 @@ -57,6 +57,7 @@ import org.apache.commons.javaflow.bytecode.transformation.ResourceTransformer; import org.apache.commons.javaflow.bytecode.transformation.bcel.analyser.ControlFlowGraph; import org.apache.commons.javaflow.bytecode.transformation.bcel.analyser.ExceptionHandler; +import org.apache.commons.javaflow.bytecode.transformation.bcel.analyser.ExecutionPath; import org.apache.commons.javaflow.bytecode.transformation.bcel.analyser.ExecutionVisitor; import org.apache.commons.javaflow.bytecode.transformation.bcel.analyser.Frame; import org.apache.commons.javaflow.bytecode.transformation.bcel.analyser.InstructionContext; @@ -70,7 +71,6 @@ import java.io.FileOutputStream; import java.io.IOException; import java.io.InputStream; -import java.util.ArrayList; import java.util.Vector; @@ -198,7 +198,6 @@ // information about every instruction final ControlFlowGraph cfg = new ControlFlowGraph(method); - //analyse(clazz, method, cfg, icv, ev); analyse(clazzGen, method, cfg, ev); try { @@ -286,55 +285,26 @@ } } - //private void analyse(ClassGen clazz, MethodGen method, ControlFlowGraph cfg, InstConstraintVisitor icv, ExecutionVisitor ev) { private void analyse(ClassGen clazz, MethodGen method, ControlFlowGraph cfg, ExecutionVisitor ev) { log.debug("analyse " + method.getName()); - // build the initial frame situation for this method. - final Frame vanillaFrame = new Frame(method.getMaxLocals(), method.getMaxStack()); - if (!method.isStatic()) { - if (method.getName().equals(Constants.CONSTRUCTOR_NAME)) { - Frame._this = new UninitializedObjectType(new ObjectType(clazz.getClassName())); - vanillaFrame.getLocals().set(0, new UninitializedObjectType(new ObjectType(clazz.getClassName()))); - } else { - Frame._this = null; - vanillaFrame.getLocals().set(0, new ObjectType(clazz.getClassName())); - } - } - // fill local variables with parameter types - final Type[] argtypes = method.getArgumentTypes(); - int twoslotoffset = 0; - for (int j = 0; j < argtypes.length; j++) { - if ((argtypes[j] == Type.SHORT) || (argtypes[j] == Type.BYTE) || (argtypes[j] == Type.CHAR) || (argtypes[j] == Type.BOOLEAN)) { - argtypes[j] = Type.INT; - } - vanillaFrame.getLocals().set(twoslotoffset + j + (method.isStatic() ? 0 : 1), argtypes[j]); - if (argtypes[j].getSize() == 2) { - twoslotoffset++; - vanillaFrame.getLocals().set(twoslotoffset + j + (method.isStatic() ? 0 : 1), Type.UNKNOWN); - } - } - //icv.setMethodGen(method); + final Frame vanillaFrame = craeteInitialFrame(method, clazz); final Vector ics = new Vector(); // Type: InstructionContext - final Vector ecs = new Vector(); // Type: ArrayList (of InstructionContext) + final Vector ecs = new Vector(); // Type: ExecutionPath final InstructionContext start = cfg.contextOf(method.getInstructionList().getStart()); - //start.execute(vanillaFrame, new ArrayList(), icv, ev); - start.execute(vanillaFrame, new ArrayList(), ev); + start.execute(vanillaFrame, ExecutionPath.EMPTY, ev); // new ArrayList() <=> no Instruction was executed before // => Top-Level routine (no jsr call before) ics.add(start); - ecs.add(new ArrayList()); + ecs.add(ExecutionPath.EMPTY); while (!ics.isEmpty()) { final InstructionContext u = (InstructionContext) ics.remove(0); - final ArrayList ec = (ArrayList) ecs.remove(0); - - final ArrayList oldchain = (ArrayList) (ec.clone()); - final ArrayList newchain = (ArrayList) (ec.clone()); - newchain.add(u); + final ExecutionPath oldchain = (ExecutionPath) ecs.remove(0); + final ExecutionPath newchain = oldchain.append(u); if ((u.getInstruction().getInstruction()) instanceof RET) { // We can only follow _one_ successor, the one after the @@ -346,7 +316,7 @@ //if (theSuccessor.execute(u.getOutFrame(oldchain), newchain, icv, ev)) { if (theSuccessor.execute(u.getOutFrame(oldchain), newchain, ev)) { ics.add(theSuccessor); - ecs.add(newchain.clone()); + ecs.add(newchain); } } else { // "not a ret" // Normal successors. Add them to the queue of successors. @@ -356,7 +326,7 @@ //if (v.execute(u.getOutFrame(oldchain), newchain, icv, ev)) { if (v.execute(u.getOutFrame(oldchain), newchain, ev)) { ics.add(v); - ecs.add(newchain.clone()); + ecs.add(newchain); } } } @@ -379,15 +349,46 @@ .getExceptionType())); final Frame newFrame = new Frame(newLocals, newStack); - //if (v.execute(newFrame, new ArrayList(), icv, ev)) { - if (v.execute(newFrame, new ArrayList(), ev)) { + if (v.execute(newFrame, ExecutionPath.EMPTY, ev)) { ics.add(v); - ecs.add(new ArrayList()); + ecs.add(ExecutionPath.EMPTY); } } } } + /** + * Creates a [EMAIL PROTECTED] Frame} object that represents the state of the stack frame + * at the beginning of a method. + */ + private Frame craeteInitialFrame(MethodGen method, ClassGen clazz) { + final Frame vanillaFrame = new Frame(method.getMaxLocals(), method.getMaxStack()); + if (!method.isStatic()) { + if (method.getName().equals(Constants.CONSTRUCTOR_NAME)) { + Frame._this = new UninitializedObjectType(new ObjectType(clazz.getClassName())); + vanillaFrame.getLocals().set(0, new UninitializedObjectType(new ObjectType(clazz.getClassName()))); + } else { + Frame._this = null; + vanillaFrame.getLocals().set(0, new ObjectType(clazz.getClassName())); + } + } + // fill local variables with parameter types + final Type[] argtypes = method.getArgumentTypes(); + int twoslotoffset = 0; + for (int j = 0; j < argtypes.length; j++) { + if ((argtypes[j] == Type.SHORT) || (argtypes[j] == Type.BYTE) || (argtypes[j] == Type.CHAR) || (argtypes[j] == Type.BOOLEAN)) { + argtypes[j] = Type.INT; + } + vanillaFrame.getLocals().set(twoslotoffset + j + (method.isStatic() ? 0 : 1), argtypes[j]); + if (argtypes[j].getSize() == 2) { + twoslotoffset++; + vanillaFrame.getLocals().set(twoslotoffset + j + (method.isStatic() ? 0 : 1), Type.UNKNOWN); + } + } + + return vanillaFrame; + } + private void rewrite(MethodGen method, ControlFlowGraph cfg) throws ClassNotFoundException { final InstructionFactory insFactory = new InstructionFactory(method.getConstantPool()); final Vector invokeIns = new Vector(); @@ -409,7 +410,7 @@ Frame frame = null; try { context = cfg.contextOf(ins); - frame = context.getOutFrame(new ArrayList()); + frame = context.getOutFrame(ExecutionPath.EMPTY); } catch (AssertionViolatedException ave) { // empty } @@ -435,7 +436,7 @@ // remove additional dup's while (next != null && next.getInstruction().getOpcode() == Constants.DUP) { context = cfg.contextOf(next); - context.getOutFrame(new ArrayList()); + context.getOutFrame(ExecutionPath.EMPTY); final InstructionHandle newnext = next.getNext(); insList.delete(next); next = newnext; Modified: jakarta/commons/sandbox/javaflow/trunk/src/java/org/apache/commons/javaflow/bytecode/transformation/bcel/analyser/ControlFlowGraph.java URL: http://svn.apache.org/viewcvs/jakarta/commons/sandbox/javaflow/trunk/src/java/org/apache/commons/javaflow/bytecode/transformation/bcel/analyser/ControlFlowGraph.java?rev=359657&r1=359656&r2=359657&view=diff ============================================================================== --- jakarta/commons/sandbox/javaflow/trunk/src/java/org/apache/commons/javaflow/bytecode/transformation/bcel/analyser/ControlFlowGraph.java (original) +++ jakarta/commons/sandbox/javaflow/trunk/src/java/org/apache/commons/javaflow/bytecode/transformation/bcel/analyser/ControlFlowGraph.java Wed Dec 28 14:53:35 2005 @@ -65,10 +65,10 @@ private HashMap outFrames; // key: the last-executed JSR /** - * The 'execution predecessors' - a list of type InstructionContext + * The 'execution predecessors' - a list of [EMAIL PROTECTED] InstructionContext} * of those instances that have been execute()d before in that order. */ - private ArrayList executionPredecessors = null; // Type: InstructionContext + private ExecutionPath executionPredecessors = null; // Type: InstructionContext /** * Creates an InstructionHandleImpl object from an InstructionHandle. @@ -92,7 +92,7 @@ /** * Returns a clone of the "outgoing" frame situation with respect to the given ExecutionChain. */ - public Frame getOutFrame(ArrayList execChain){ + public Frame getOutFrame(ExecutionPath execChain){ executionPredecessors = execChain; Frame org; @@ -126,7 +126,7 @@ * and therefore calculates the "outgoing" frame situation. * Returns: True iff the "incoming" frame situation changed after * merging with "inFrame". - * The execPreds ArrayList must contain the InstructionContext + * The execPreds contain the InstructionContext * objects executed so far in the correct order. This is just * one execution path [out of many]. This is needed to correctly * "merge" in the special case of a RET's successor. @@ -135,9 +135,12 @@ * @return true - if and only if the "outgoing" frame situation * changed from the one before execute()ing. */ - public boolean execute(Frame inFrame, ArrayList execPreds, ExecutionVisitor ev){ + public boolean execute(Frame inFrame, ExecutionPath execPreds, ExecutionVisitor ev){ - executionPredecessors = (ArrayList) execPreds.clone(); + // When merge failed, this is useful to see what are two passes + ExecutionPath oldExecPreds = executionPredecessors; + + executionPredecessors = execPreds; //sanity check if ( (lastExecutionJSR() == null) && (subroutines.subroutineOf(getInstruction()) != subroutines.getTopLevel() ) ){ @@ -219,15 +222,11 @@ /** * Returns the control flow execution chain. This is built - * while execute(Frame, ArrayList)-ing the code represented + * while [EMAIL PROTECTED] #execute(Frame, ExecutionPath, ExecutionVisitor) executing} the code represented * by the surrounding ControlFlowGraph. */ private String getExecutionChain(){ - String s = this.toString(); - for (int i=executionPredecessors.size()-1; i>=0; i--){ - s = executionPredecessors.get(i)+"\n" + s; - } - return s; + return executionPredecessors.toString()+"\n"+this.toString(); } @@ -248,28 +247,8 @@ return instruction; } - /** - * Returns the InstructionContextImpl with an JSR/JSR_W - * that was last in the ExecutionChain, without - * a corresponding RET, i.e. - * we were called by this one. - * Returns null if we were called from the top level. - */ - private InstructionContextImpl lastExecutionJSR(){ - - int size = executionPredecessors.size(); - int retcount = 0; - - for (int i=size-1; i>=0; i--){ - InstructionContextImpl current = (InstructionContextImpl) (executionPredecessors.get(i)); - Instruction currentlast = current.getInstruction().getInstruction(); - if (currentlast instanceof RET) retcount++; - if (currentlast instanceof JsrInstruction){ - retcount--; - if (retcount == -1) return current; - } - } - return null; + private InstructionContext lastExecutionJSR(){ + return executionPredecessors.lastExecutionJSR(); } /* Satisfies InstructionContext.getSuccessors(). */ Added: jakarta/commons/sandbox/javaflow/trunk/src/java/org/apache/commons/javaflow/bytecode/transformation/bcel/analyser/ExecutionPath.java URL: http://svn.apache.org/viewcvs/jakarta/commons/sandbox/javaflow/trunk/src/java/org/apache/commons/javaflow/bytecode/transformation/bcel/analyser/ExecutionPath.java?rev=359657&view=auto ============================================================================== --- jakarta/commons/sandbox/javaflow/trunk/src/java/org/apache/commons/javaflow/bytecode/transformation/bcel/analyser/ExecutionPath.java (added) +++ jakarta/commons/sandbox/javaflow/trunk/src/java/org/apache/commons/javaflow/bytecode/transformation/bcel/analyser/ExecutionPath.java Wed Dec 28 14:53:35 2005 @@ -0,0 +1,72 @@ +package org.apache.commons.javaflow.bytecode.transformation.bcel.analyser; + +import org.apache.bcel.generic.Instruction; +import org.apache.bcel.generic.RET; +import org.apache.bcel.generic.JsrInstruction; + +/** + * List of [EMAIL PROTECTED] InstructionContext} that represents a sequence of an execution. + * + * <p> + * This object is immutable. + * The sequence is represented in left-associative style; that is, + * a sequence of [a,b,c,d] is represented as prev=[a,b,c] and last=d. + * + * @author Kohsuke Kawaguchi + */ +public final class ExecutionPath { + /** + * Singleton [EMAIL PROTECTED] ExecutionPath} that represents an empty sequence []. + */ + public static final ExecutionPath EMPTY = new ExecutionPath(null,null); + + private final ExecutionPath prev; + private final InstructionContext last; + + private ExecutionPath(ExecutionPath prev, InstructionContext last) { + this.prev = prev; + this.last = last; + } + + /** + * Creates a new [EMAIL PROTECTED] ExecutionPath} that has + * <tt>[... list in this ExecutionPath ..., ins]</tt>. + */ + public ExecutionPath append(InstructionContext ins) { + return new ExecutionPath(this,ins); + } + + /** + * Returns the InstructionContextImpl with an JSR/JSR_W + * that was last in the ExecutionChain, without + * a corresponding RET, i.e. + * we were called by this one. + * Returns null if we were called from the top level. + */ + public InstructionContext lastExecutionJSR(){ + int retcount = 0; + + for( ExecutionPath ptr = this; ptr!=EMPTY; ptr=ptr.prev) { + Instruction i = ptr.last.getInstruction().getInstruction(); + if (i instanceof RET) retcount++; + if (i instanceof JsrInstruction){ + retcount--; + if (retcount == -1) + return ptr.last; + } + } + + return null; + } + + /** + * Returns a human readable representation. + */ + public String toString() { + if(this==EMPTY) + return ""; + else { + return prev.toString()+"\n"+last.toString(); + } + } +} Propchange: jakarta/commons/sandbox/javaflow/trunk/src/java/org/apache/commons/javaflow/bytecode/transformation/bcel/analyser/ExecutionPath.java ------------------------------------------------------------------------------ svn:eol-style = native Modified: jakarta/commons/sandbox/javaflow/trunk/src/java/org/apache/commons/javaflow/bytecode/transformation/bcel/analyser/InstructionContext.java URL: http://svn.apache.org/viewcvs/jakarta/commons/sandbox/javaflow/trunk/src/java/org/apache/commons/javaflow/bytecode/transformation/bcel/analyser/InstructionContext.java?rev=359657&r1=359656&r2=359657&view=diff ============================================================================== --- jakarta/commons/sandbox/javaflow/trunk/src/java/org/apache/commons/javaflow/bytecode/transformation/bcel/analyser/InstructionContext.java (original) +++ jakarta/commons/sandbox/javaflow/trunk/src/java/org/apache/commons/javaflow/bytecode/transformation/bcel/analyser/InstructionContext.java Wed Dec 28 14:53:35 2005 @@ -51,7 +51,7 @@ * @return true - if and only if the "outgoing" frame situation * changed from the one before execute()ing. */ - boolean execute(Frame inFrame, ArrayList executionPredecessors, ExecutionVisitor ev); + boolean execute(Frame inFrame, ExecutionPath executionPredecessors, ExecutionVisitor ev); Frame getInFrame(); @@ -60,9 +60,9 @@ * therefore <B>it has to be calculated by execute(Frame, ArrayList) * first.</B> * - * @see #execute(Frame, ArrayList, ExecutionVisitor) + * @see #execute(Frame, ExecutionPath, ExecutionVisitor) */ - Frame getOutFrame(ArrayList executionPredecessors); + Frame getOutFrame(ExecutionPath executionPredecessors); /** * Returns the InstructionHandle this InstructionContext is wrapped around. --------------------------------------------------------------------- To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]