0001: /* Copyright (C) 2004 - 2007 db4objects Inc. http://www.db4o.com
0002:
0003: This file is part of the db4o open source object database.
0004:
0005: db4o is free software; you can redistribute it and/or modify it under
0006: the terms of version 2 of the GNU General Public License as published
0007: by the Free Software Foundation and as clarified by db4objects' GPL
0008: interpretation policy, available at
0009: http://www.db4o.com/about/company/legalpolicies/gplinterpretation/
0010: Alternatively you can write to db4objects, Inc., 1900 S Norfolk Street,
0011: Suite 350, San Mateo, CA 94403, USA.
0012:
0013: db4o is distributed in the hope that it will be useful, but WITHOUT ANY
0014: WARRANTY; without even the implied warranty of MERCHANTABILITY or
0015: FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
0016: for more details.
0017:
0018: You should have received a copy of the GNU General Public License along
0019: with this program; if not, write to the Free Software Foundation, Inc.,
0020: 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
0021: package EDU.purdue.cs.bloat.inline;
0022:
0023: import java.util.*;
0024:
0025: import EDU.purdue.cs.bloat.editor.*;
0026: import EDU.purdue.cs.bloat.util.*;
0027:
0028: /**
0029: * The of <tt>InstructionStack</tt> keeps track of which instructions pushed a
0030: * certain element of the stack. It is a stack of sets of instructions. You can
0031: * think of it like this: (1, {4,6}, 8) means that instruction 1 pushed the item
0032: * on the bottom of the stack, instructions 4 and 6 both push the second element
0033: * on the stack (depending on control flow), and instruction 8 pushed the
0034: * element on top of the stack. We use this information at a call site to
0035: * determine what instruction(s) pushed the receiver object onto the stack.
0036: * Special thanks to Jan Vitek for helping me come up with this algorithm.
0037: *
0038: * <p>
0039: *
0040: * This class is an <tt>InstructionVisitor</tt> that updates the instruction
0041: * stack representation appropriately. When there is a merge in control flow,
0042: * two <tt>InstructionStack</tt>s are merged using the <tt>merge</tt>
0043: * method.
0044: *
0045: * <p>
0046: *
0047: * This class is also used to determine whether the object at a given stack
0048: * depth is "preexistent". An object preexists if we can guarantee that it was
0049: * created outside of the method in which it is used. While it is possible to
0050: * determine which fields are preexistent (see "Inlining of Virtual Methods" by
0051: * Detlefs and Ageson in ECOOP99), we only keep track of local variables that
0052: * preexist.
0053: *
0054: * <p>
0055: *
0056: * We determine which local variables preexist as follows. Initially, only the
0057: * local variables for method parameters preexist. When a store is encoutered,
0058: * we determine if the set of instructions on top of the stack consist of loads
0059: * preexistent variables. If so, then the variable being stored into is
0060: * preexistent. However, objects that are the result of an allocation
0061: * (constructor call) in the method are preexist. Thus, we maintain the preexist
0062: * information as a set. If the set is null, then the object does not preexist.
0063: * If the set is empty, then it preexists and came from at least one argument.
0064: * If the set is non-empty, then it contains the type(s) of the constructor(s)
0065: * from which it originated. Pretty neat, huh?
0066: */
0067: public class InstructionStack extends InstructionAdapter {
0068:
0069: MethodEditor method; // Method we're dealing with
0070:
0071: HashMap stacks; // Maps Labels to their stacks
0072:
0073: LinkedList currStack; // The current stack
0074:
0075: HashMap preexists; // Maps Labels to their preexists
0076:
0077: HashMap currPreexists; // The current preexist (var -> Set)
0078:
0079: private static void pre(final String s) {
0080: // Debug preexistence
0081: if (false) {
0082: System.out.println(s);
0083: }
0084: }
0085:
0086: /**
0087: * Constructor. Creates an empty <tt>InstructionStack</tt>.
0088: */
0089: public InstructionStack(final MethodEditor method) {
0090: this .method = method;
0091: this .stacks = new HashMap();
0092: this .preexists = new HashMap();
0093:
0094: // Initially only the parameters to the method prexist
0095: final Type[] paramTypes = method.paramTypes();
0096: this .currPreexists = new HashMap();
0097: for (int i = 0; i < paramTypes.length; i++) {
0098: // We only care about the preexistence of objects (not arrays)
0099: if ((paramTypes[i] != null) && paramTypes[i].isObject()) {
0100: this .currPreexists
0101: .put(method.paramAt(i), new HashSet());
0102: }
0103: }
0104: }
0105:
0106: /**
0107: * Deals with a Label.
0108: */
0109: public void handle(final Label label) {
0110: final LinkedList stack = (LinkedList) stacks.get(label);
0111:
0112: if (stack == null) {
0113: // If this label starts an exception handler, account for the
0114: // exception being pushed on the stack
0115: final Iterator tryCatches = method.tryCatches().iterator();
0116: while (tryCatches.hasNext()) {
0117: final TryCatch tc = (TryCatch) tryCatches.next();
0118:
0119: if (tc.handler().equals(label)) {
0120: // Kluge to push the exception object on the stack. I don't
0121: // think it matters much.
0122: final Instruction aload = new Instruction(
0123: Opcode.opcx_ldc, "Exception");
0124: currStack = new LinkedList();
0125: aload.visit(this );
0126: stacks.put(label, stack);
0127: label.setStartsBlock(true);
0128:
0129: // We have no idea from where the exception will be thrown,
0130: // so we can't make any assumptions about the preexistence
0131: // of any variables.
0132: currPreexists = new HashMap();
0133: return;
0134: }
0135: }
0136:
0137: if (currStack == null) {
0138: // Make a new stack
0139: currStack = new LinkedList();
0140: stacks.put(label, currStack);
0141:
0142: // I don't think we need to worry about the currPreexists. It
0143: // was taken care of in the constructor.
0144:
0145: } else {
0146: // Otherwise, keep the current stack
0147: currStack = (LinkedList) currStack.clone();
0148: stacks.put(label, currStack);
0149:
0150: // And the current preexists
0151: currPreexists = InstructionStack
0152: .clonePreexists(currPreexists);
0153: this .preexists.put(label, currPreexists);
0154: }
0155:
0156: } else {
0157: // Merge the old stack with the current one
0158: currStack = InstructionStack.merge(currStack, stack);
0159: stacks.put(label, currStack);
0160:
0161: final HashMap oldPreexists = (HashMap) this .preexists
0162: .get(label);
0163: currPreexists = InstructionStack.merge(oldPreexists,
0164: currPreexists);
0165: this .preexists.put(label, currPreexists);
0166: }
0167: }
0168:
0169: /**
0170: * Deals with an <tt>Instruction</tt> handles branches, jsrs, and the
0171: * like.
0172: */
0173: public void handle(final Instruction inst) {
0174: // Visit first
0175: inst.visit(this );
0176:
0177: if (inst.isJump()) {
0178: final Label target = (Label) inst.operand();
0179: target.setStartsBlock(true);
0180:
0181: // Merge the target's stack with any other stacks at that
0182: // label
0183: final LinkedList targetStack = (LinkedList) stacks
0184: .get(target);
0185: if (targetStack != null) {
0186: // Don't change currStack, but do the merge
0187: stacks.put(target, InstructionStack.merge(currStack,
0188: targetStack));
0189:
0190: final HashMap oldPreexists = (HashMap) this .preexists
0191: .get(target);
0192: this .preexists.put(target, InstructionStack.merge(
0193: currPreexists, oldPreexists));
0194:
0195: } else {
0196: // Put a new stack at the target
0197: stacks.put(target, currStack.clone());
0198: this .preexists.put(target, InstructionStack
0199: .clonePreexists(currPreexists));
0200: }
0201:
0202: if (!inst.isConditionalJump()) {
0203: // The next instruction should be a Label. But since it is
0204: // not the next instruction executed, we don't want to merge
0205: // the contents of the label's stack and the current stack.
0206: // So, null out the current stack.
0207: currStack = new LinkedList();
0208: }
0209:
0210: } else if (inst.isSwitch()) {
0211: // Propagate the current stack to all targets
0212: final Switch sw = (Switch) inst.operand();
0213: final Label defaultTarget = sw.defaultTarget();
0214: defaultTarget.setStartsBlock(true);
0215:
0216: final LinkedList defaultStack = (LinkedList) stacks
0217: .get(defaultTarget);
0218: if (defaultStack != null) {
0219: Assert.isTrue(defaultStack.size() == currStack.size(),
0220: "Stack height mismatch (" + defaultStack.size()
0221: + " != " + currStack.size() + ") at "
0222: + inst);
0223: // Merge stacks for good measure
0224: stacks.put(defaultTarget, InstructionStack.merge(
0225: currStack, defaultStack));
0226:
0227: final HashMap defaultPreexists = (HashMap) this .preexists
0228: .get(defaultTarget);
0229: this .preexists.put(defaultTarget, InstructionStack
0230: .merge(currPreexists, defaultPreexists));
0231:
0232: } else {
0233: // Put copy of stack at target
0234: stacks.put(defaultTarget, currStack.clone());
0235: this .preexists.put(defaultTarget, InstructionStack
0236: .clonePreexists(currPreexists));
0237: }
0238:
0239: final Label[] targets = sw.targets();
0240: for (int t = 0; t < targets.length; t++) {
0241: final Label target = targets[t];
0242: target.setStartsBlock(true);
0243: final LinkedList targetStack = (LinkedList) stacks
0244: .get(target);
0245: if (targetStack != null) {
0246: Assert.isTrue(targetStack.size() == currStack
0247: .size(), "Stack height mismatch ("
0248: + targetStack.size() + " != "
0249: + currStack.size() + ") at " + inst);
0250: // Merge stacks for good measure
0251: stacks.put(target, InstructionStack.merge(
0252: currStack, targetStack));
0253:
0254: final HashMap oldPreexists = (HashMap) this .preexists
0255: .get(target);
0256: this .preexists.put(target, InstructionStack.merge(
0257: oldPreexists, currPreexists));
0258:
0259: } else {
0260: stacks.put(target, currStack.clone());
0261: this .preexists.put(target, InstructionStack
0262: .clonePreexists(currPreexists));
0263: }
0264: }
0265:
0266: } else if (inst.isJsr()) {
0267: // Someday we might have to deal with subroutines that push
0268: // stuff on the stack. That complicates things. I'm going to
0269: // pretend it doesn't exist. It was good enough for Nate.
0270:
0271: // In the meantime, we have to propagate the fact that the jsr
0272: // pushes the return address to the subroutine. We use an empty
0273: // stack because it is possible that a subroutine could be
0274: // called with different stack heights. Here is another thing
0275: // that needs to be fixed someday.
0276: final LinkedList subStack = new LinkedList();
0277: final LinkedList oldStack = currStack;
0278:
0279: // Push the return address on stack
0280: currStack = subStack;
0281: inst.visit(this );
0282:
0283: currStack = oldStack; // Should be okay unless sub effects stack
0284:
0285: // Propagate subStack to subroutine
0286: final Label subroutine = (Label) inst.operand();
0287: subroutine.setStartsBlock(true);
0288: stacks.put(subroutine, subStack);
0289: this .preexists.put(subroutine, new HashMap());
0290:
0291: } else if (inst.isReturn() || inst.isThrow()) {
0292: // We don't what comes next, but we don't want to merge with the
0293: // current stack.
0294: currStack = new LinkedList();
0295: }
0296: }
0297:
0298: /**
0299: * Pushes an instruction onto the stack
0300: */
0301: private void push(final Instruction inst) {
0302: // Create a new set for the top element of the stack
0303: final Set set = new HashSet();
0304: set.add(inst);
0305: currStack.add(set);
0306: }
0307:
0308: /**
0309: * Pops the top of the stack.
0310: */
0311: private void pop() {
0312: currStack.removeLast();
0313: }
0314:
0315: /**
0316: * Pops a given number of elements off the stack.
0317: */
0318: private void pop(final int n) {
0319: for (int i = 0; i < n; i++) {
0320: currStack.removeLast();
0321: }
0322: }
0323:
0324: /**
0325: * Returns the number of elements in this instruction stack.
0326: */
0327: public int height() {
0328: return (currStack.size());
0329: }
0330:
0331: /**
0332: * Returns the set of <tt>Instruction</tt>s at depth <tt>n</tt> of the
0333: * instruction stack. Depth 0 is the top of the stack. The bottom of the
0334: * stack is at depth stackSize - 1.
0335: */
0336: public Set atDepth(final int n) {
0337: final Set set = (Set) currStack.get(currStack.size() - 1 - n);
0338: return (set);
0339: }
0340:
0341: /**
0342: * Returns a <tt>Set</tt> representing whether or not the instructions at
0343: * a given depth push a preexistent object onto the stack. If the list is
0344: * <tt>null</tt>, then the push is not preexistent. If the list is empty,
0345: * then the push is preexistent. If the list is non-empty, it contains the
0346: * <tt>Type</tt>(s) of objects that are known to be on the stack. These
0347: * types are the results of calls to constructors.
0348: */
0349: public HashSet preexistsAtDepth(final int n) {
0350: // How do we determine whether a set of instructions pushes a
0351: // preexist object? All of the instructions must be loads of
0352: // objects from preexistent variable or the result of an
0353: // object creation. Note that we can deal with arrays because
0354: // we'd have to keep track of indices.
0355:
0356: InstructionStack.pre(" Preexisting variables: "
0357: + InstructionStack.db(currPreexists));
0358:
0359: HashSet atDepth = null;
0360: final Iterator insts = this .atDepth(n).iterator();
0361: Assert.isTrue(insts.hasNext(), "No instructions at depth " + n);
0362: while (insts.hasNext()) {
0363: final Instruction inst = (Instruction) insts.next();
0364: InstructionStack.pre(" Instruction at " + n + ": "
0365: + inst);
0366: if (inst.opcodeClass() == Opcode.opcx_aload) {
0367: final LocalVariable var = (LocalVariable) inst
0368: .operand();
0369: final Set set = (Set) this .currPreexists.get(var);
0370: if (set != null) {
0371: if (set.isEmpty()) {
0372: // If the set is empty, then this local variable came
0373: // from
0374: // a method argument.
0375: atDepth = new HashSet();
0376:
0377: } else {
0378: // The list contains types that are the result of a
0379: // constructor call. Add them to the preexists list.
0380: if (atDepth == null) {
0381: atDepth = new HashSet();
0382: }
0383: atDepth.addAll(set);
0384: }
0385: continue;
0386: }
0387:
0388: // Instruction loads a non-preexistent variable, fall through
0389:
0390: } else if (inst.opcodeClass() == Opcode.opcx_new) {
0391: // We look for the new instruction instead of the constructor
0392: // call because of the way we represent the stack.
0393:
0394: if ((atDepth != null) && atDepth.isEmpty()) {
0395: // We already know that the object pushed at this depth are
0396: // one of the arguments. We don't the exact type of the
0397: // argument, so we can't safely add the type being
0398: // instantiated to the preexist list.
0399: continue;
0400: }
0401:
0402: // Figure out the type being created and add it to the
0403: // preexists list.
0404: final Type type = (Type) inst.operand();
0405: InstructionStack.pre(" Constructing "
0406: + Type.truncatedName(type));
0407: if (atDepth == null) {
0408: atDepth = new HashSet();
0409: }
0410: atDepth.add(type);
0411: continue;
0412:
0413: // A non-constructor invokespecial was called, fall through
0414:
0415: } else if (inst.opcodeClass() == Opcode.opcx_dup) {
0416: final Set set = this .preexistsAtDepth(n - 1);
0417: if (set != null) {
0418: if (set.isEmpty()) {
0419: // If list is empty, then this preexist must also be
0420: // empty
0421: atDepth = new HashSet();
0422:
0423: } else {
0424: // Add the classes instantiated to the list
0425: atDepth.addAll(set);
0426: }
0427: continue;
0428: }
0429: }
0430:
0431: InstructionStack.pre(" Doesn't preexist");
0432: return (null);
0433: }
0434:
0435: // If we got down here every instruction was preexistent
0436: InstructionStack.pre(" Preexists");
0437: return (atDepth);
0438:
0439: }
0440:
0441: /**
0442: * Merges two stacks together and returns their union. Note that stacks of
0443: * unequal height cannot be merged.
0444: */
0445: private static LinkedList merge(final LinkedList stack1,
0446: final LinkedList stack2) {
0447:
0448: Assert.isFalse((stack1 == null) && (stack2 == null),
0449: "Cannot merge two null stacks");
0450:
0451: final LinkedList merge = new LinkedList();
0452:
0453: // If either stack is null or empty, just use the other one
0454: if ((stack1 == null) || (stack1.size() == 0)) {
0455: merge.addAll(stack2);
0456: return (merge);
0457: }
0458:
0459: if ((stack2 == null) || (stack2.size() == 0)) {
0460: merge.addAll(stack1);
0461: return (merge);
0462: }
0463:
0464: Assert.isTrue(stack1.size() == stack2.size(),
0465: "Stacks of unequal height cannot be merged ("
0466: + stack1.size() + " != " + stack2.size() + ")");
0467:
0468: for (int i = 0; i < stack1.size(); i++) {
0469: final Set mergeSet = new HashSet();
0470: mergeSet.addAll((Set) stack1.get(i));
0471: mergeSet.addAll((Set) stack2.get(i));
0472: merge.add(i, mergeSet);
0473: }
0474:
0475: return (merge);
0476: }
0477:
0478: /**
0479: * Merges two preexists lists. For a given variable, if either of the two
0480: * input indices is <tt>null</tt>, then the result is <tt>null</tt>.
0481: * If either of the two input indices is empty, then the result is empty.
0482: * Otherwise, the result is the union of the two input sets.
0483: */
0484: private static HashMap merge(final HashMap one, final HashMap two) {
0485: Assert.isFalse((one == null) && (two == null),
0486: "Can't merge null preexists");
0487:
0488: if (one == null) {
0489: return (InstructionStack.clonePreexists(two));
0490:
0491: } else if (two == null) {
0492: return (InstructionStack.clonePreexists(one));
0493: }
0494:
0495: // Go through all of the variables in both sets. If one is not
0496: // contained in the other, then the set (or null) from the other
0497: // is used. If one is mapped to null, then the result is null.
0498: // If one has an empty set, then the result has an empty set.
0499: // Otherwise, the two non-empty sets are merge.
0500: final HashMap result = new HashMap();
0501: final Set allVars = new HashSet();
0502: allVars.addAll(one.keySet());
0503: allVars.addAll(two.keySet());
0504: final Iterator iter = allVars.iterator();
0505: while (iter.hasNext()) {
0506: final LocalVariable var = (LocalVariable) iter.next();
0507: if (!one.containsKey(var)) {
0508: HashSet set = (HashSet) two.get(var);
0509: if (set != null) {
0510: set = (HashSet) set.clone();
0511: }
0512:
0513: result.put(var, set);
0514:
0515: } else if (!two.containsKey(var)) {
0516: HashSet set = (HashSet) one.get(var);
0517: if (set != null) {
0518: set = (HashSet) set.clone();
0519: }
0520:
0521: result.put(var, set);
0522:
0523: } else {
0524: final HashSet oneSet = (HashSet) one.get(var);
0525: final HashSet twoSet = (HashSet) two.get(var);
0526: if ((oneSet == null) || (twoSet == null)) {
0527: result.put(var, null);
0528:
0529: } else if (oneSet.isEmpty() || twoSet.isEmpty()) {
0530: result.put(var, new HashSet());
0531:
0532: } else {
0533: final Set set = new HashSet();
0534: set.addAll(oneSet);
0535: set.addAll(twoSet);
0536: result.put(var, set);
0537: }
0538: }
0539: }
0540:
0541: InstructionStack.pre("Merge of " + InstructionStack.db(one)
0542: + " and " + InstructionStack.db(two) + " is "
0543: + InstructionStack.db(result));
0544:
0545: return (result);
0546: }
0547:
0548: /**
0549: * Returns a textual representation of a preexists mapping.
0550: */
0551: static String db(final HashMap preexists) {
0552: if (preexists == null) {
0553: return ("\n null?\n");
0554: }
0555:
0556: final StringBuffer sb = new StringBuffer("\n");
0557: final Iterator vars = preexists.keySet().iterator();
0558: while (vars.hasNext()) {
0559: final LocalVariable var = (LocalVariable) vars.next();
0560: final Set set = (Set) preexists.get(var);
0561: if (set == null) {
0562: sb.append(" " + var + ": null\n");
0563:
0564: } else {
0565: sb.append(" " + var + ": ");
0566: final Iterator iter = set.iterator();
0567: while (iter.hasNext()) {
0568: final Type type = (Type) iter.next();
0569: sb.append(Type.truncatedName(type));
0570: if (iter.hasNext()) {
0571: sb.append(", ");
0572: }
0573: }
0574: sb.append("\n");
0575: }
0576: }
0577:
0578: return (sb.toString());
0579: }
0580:
0581: /**
0582: * Makes a deep copy of a List containing preexists information.
0583: */
0584: private static HashMap clonePreexists(final HashMap old) {
0585: final HashMap clone = new HashMap();
0586: final Iterator vars = old.keySet().iterator();
0587: while (vars.hasNext()) {
0588: final LocalVariable var = (LocalVariable) vars.next();
0589: final HashSet set = (HashSet) old.get(var);
0590: if (set == null) {
0591: clone.put(var, null);
0592: } else {
0593: clone.put(var, set.clone());
0594: }
0595: }
0596: return (clone);
0597: }
0598:
0599: public void visit_nop(final Instruction inst) {
0600: }
0601:
0602: public void visit_ldc(final Instruction inst) {
0603: push(inst);
0604: }
0605:
0606: public void visit_iload(final Instruction inst) {
0607: push(inst);
0608: }
0609:
0610: public void visit_lload(final Instruction inst) {
0611: push(inst);
0612: }
0613:
0614: public void visit_fload(final Instruction inst) {
0615: push(inst);
0616: }
0617:
0618: public void visit_dload(final Instruction inst) {
0619: push(inst);
0620: }
0621:
0622: public void visit_aload(final Instruction inst) {
0623: push(inst);
0624: }
0625:
0626: public void visit_iaload(final Instruction inst) {
0627: pop(2);
0628: push(inst);
0629: }
0630:
0631: public void visit_laload(final Instruction inst) {
0632: pop(2);
0633: push(inst);
0634: }
0635:
0636: public void visit_faload(final Instruction inst) {
0637: pop(2);
0638: push(inst);
0639: }
0640:
0641: public void visit_daload(final Instruction inst) {
0642: pop(2);
0643: push(inst);
0644: }
0645:
0646: public void visit_aaload(final Instruction inst) {
0647: pop(2);
0648: push(inst);
0649: }
0650:
0651: public void visit_baload(final Instruction inst) {
0652: pop(2);
0653: push(inst);
0654: }
0655:
0656: public void visit_caload(final Instruction inst) {
0657: pop(2);
0658: push(inst);
0659: }
0660:
0661: public void visit_saload(final Instruction inst) {
0662: pop(2);
0663: push(inst);
0664: }
0665:
0666: public void visit_istore(final Instruction inst) {
0667: pop();
0668: }
0669:
0670: public void visit_lstore(final Instruction inst) {
0671: pop();
0672: }
0673:
0674: public void visit_fstore(final Instruction inst) {
0675: pop();
0676: }
0677:
0678: public void visit_dstore(final Instruction inst) {
0679: pop();
0680: }
0681:
0682: public void visit_astore(final Instruction inst) {
0683: // When we store an object to a local variable, we need to keep
0684: // track of whether or not the object being stored (and hence the
0685: // variable into which it is stored) is preexistent.
0686: final LocalVariable var = (LocalVariable) inst.operand();
0687: final HashSet set = preexistsAtDepth(0);
0688:
0689: if (set == null) {
0690: InstructionStack.pre(" " + var + " does not preexist");
0691: this .currPreexists.put(var, null);
0692:
0693: } else if (set.isEmpty()) {
0694: InstructionStack.pre(" " + var + " preexists");
0695: this .currPreexists.put(var, new HashSet());
0696:
0697: } else {
0698: // This store superceeds anything else that was already in this
0699: // local, so don't merge the sets.
0700: InstructionStack.pre(" " + var
0701: + " preexists with types");
0702: this .currPreexists.put(var, set.clone());
0703: }
0704:
0705: pop();
0706: }
0707:
0708: public void visit_iastore(final Instruction inst) {
0709: pop(3);
0710: }
0711:
0712: public void visit_lastore(final Instruction inst) {
0713: pop(3);
0714: }
0715:
0716: public void visit_fastore(final Instruction inst) {
0717: pop(3);
0718: }
0719:
0720: public void visit_dastore(final Instruction inst) {
0721: pop(3);
0722: }
0723:
0724: public void visit_aastore(final Instruction inst) {
0725: pop(3);
0726: }
0727:
0728: public void visit_bastore(final Instruction inst) {
0729: pop(3);
0730: }
0731:
0732: public void visit_castore(final Instruction inst) {
0733: pop(3);
0734: }
0735:
0736: public void visit_sastore(final Instruction inst) {
0737: pop(3);
0738: }
0739:
0740: /**
0741: * Helper method for asserting that all of the instructions are of a certain
0742: * category.
0743: */
0744: private void checkCategory(final Set insts, final int category) {
0745: final Iterator iter = insts.iterator();
0746: while (iter.hasNext()) {
0747: final Instruction inst = (Instruction) iter.next();
0748: Assert.isTrue(inst.category() == category,
0749: "Category mismatch: " + inst.category() + " != "
0750: + category);
0751: }
0752: }
0753:
0754: /**
0755: * Helper method for asserting that all of the instructions have the same
0756: * category. The category is returned.
0757: */
0758: private int checkCategory(final Set insts) {
0759: int category = 0;
0760: final Iterator iter = insts.iterator();
0761: while (iter.hasNext()) {
0762: final Instruction inst = (Instruction) iter.next();
0763: if (category == 0) {
0764: category = inst.category();
0765:
0766: } else {
0767: Assert.isTrue(inst.category() == category,
0768: "Category mismatch in instruction set");
0769: }
0770: }
0771:
0772: Assert.isTrue(category != 0, "No instructions in set");
0773: return (category);
0774: }
0775:
0776: public void visit_pop(final Instruction inst) {
0777: final Set insts = atDepth(0);
0778:
0779: checkCategory(insts, 1);
0780:
0781: pop();
0782: }
0783:
0784: public void visit_pop2(final Instruction inst) {
0785: // Form 1 pops two category 1 values off the stack. Form 2 pops
0786: // one category 2 value off the stack.
0787:
0788: final Set top1 = (Set) currStack.removeLast();
0789:
0790: final int category = checkCategory(top1);
0791:
0792: if (category == 1) {
0793: // Pop another category 1 off
0794: final Set top2 = (Set) currStack.removeLast();
0795: checkCategory(top2, 1);
0796: }
0797: }
0798:
0799: public void visit_dup(final Instruction inst) {
0800: // Duplicate the category 1 value on the top of the stack
0801: final Set dup = atDepth(0);
0802:
0803: checkCategory(dup, 1);
0804:
0805: currStack.add(new HashSet(dup));
0806: }
0807:
0808: public void visit_dup_x1(final Instruction inst) {
0809: final Set dup = atDepth(0);
0810:
0811: checkCategory(dup, 1);
0812:
0813: currStack.add(currStack.size() - 2, new HashSet(dup));
0814: }
0815:
0816: public void visit_dup_x2(final Instruction inst) {
0817: // Top value on stack must be category 1.
0818: final Set top1 = atDepth(0);
0819:
0820: checkCategory(top1, 1);
0821:
0822: final Set top2 = atDepth(1);
0823:
0824: final int category = checkCategory(top2);
0825:
0826: if (category == 1) {
0827: final Set top3 = atDepth(2);
0828: checkCategory(top3, 1);
0829:
0830: // Form 1: Dup top value and put three down
0831:
0832: currStack.add(currStack.size() - 3, new HashSet(top1));
0833:
0834: } else {
0835: // Form 2: Dup top value and put two down
0836:
0837: currStack.add(currStack.size() - 2, new HashSet(top1));
0838: }
0839: }
0840:
0841: public void visit_dup2(final Instruction inst) {
0842: // If top two values are both category 1, dup them both.
0843: // Otherwise, dup the one category 2 value.
0844: final Set top = atDepth(0);
0845:
0846: final int category = checkCategory(top);
0847:
0848: if (category == 1) {
0849: final Set top1 = atDepth(1);
0850: checkCategory(top1, 1);
0851:
0852: // Form 1: Dup top two values
0853:
0854: currStack.add(new HashSet(top1));
0855: currStack.add(new HashSet(top));
0856:
0857: } else {
0858: // Form 2: Dup top value
0859:
0860: currStack.add(new HashSet(top));
0861: }
0862: }
0863:
0864: public void visit_dup2_x1(final Instruction inst) {
0865: // If the top two values are of category 1, then dup them and put
0866: // them three down. Otherwise, the top two values are of category
0867: // 2 and the top value is put two down.
0868: final Set top = atDepth(0);
0869:
0870: final int category = checkCategory(top);
0871:
0872: if (category == 1) {
0873: final Set top1 = atDepth(1);
0874: checkCategory(top1, 1);
0875:
0876: // Form 1: Dup top two values and put three down
0877:
0878: final int n = currStack.size() - 3;
0879: currStack.add(n, top1);
0880: currStack.add(n, top);
0881:
0882: } else {
0883: final Set top1 = atDepth(1);
0884: checkCategory(top1, 1);
0885:
0886: // Form 2: Dup top value and put two down
0887:
0888: currStack.add(currStack.size() - 2, new HashSet(top));
0889: }
0890: }
0891:
0892: public void visit_dup2_x2(final Instruction inst) {
0893: // If the two four values are all category 1, then duplicate the
0894: // top two values and put them four down. If the top value is of
0895: // category 2 and the next two are of type 1, then dup the top
0896: // value and put it three down. If the top two values are both
0897: // category 1 and the third value is type 2, then dup the top two
0898: // values and put them three down. If the top two values are both
0899: // category 2, then dup the top one and put it two down.
0900:
0901: final Set top = atDepth(0);
0902: final int category = checkCategory(top);
0903:
0904: if (category == 1) {
0905: final Set top1 = atDepth(1);
0906: final int category1 = checkCategory(top1);
0907: if (category1 == 1) {
0908: final Set top2 = atDepth(2);
0909: final int category2 = checkCategory(top2);
0910: if (category2 == 1) {
0911: checkCategory(atDepth(3), 1);
0912:
0913: // Form 1: Dup top two values and put four down
0914: final int n = currStack.size() - 4;
0915: currStack.add(n, new HashSet(top1));
0916: currStack.add(n, new HashSet(top));
0917:
0918: } else {
0919: // Form 3: Dup top two values and put three down
0920: final int n = currStack.size() - 3;
0921: currStack.add(n, new HashSet(top1));
0922: currStack.add(n, new HashSet(top));
0923:
0924: }
0925:
0926: } else {
0927: Assert.isTrue(false,
0928: "Impossible stack combination for "
0929: + "dup2_x1: ... 2 1");
0930: }
0931:
0932: } else {
0933: final Set top1 = atDepth(1);
0934: final int category1 = checkCategory(top1);
0935: if (category1 == 1) {
0936: final int category2 = checkCategory(atDepth(2));
0937: if (category2 == 1) {
0938: // Form 2: Dup top value and put three down
0939: currStack.add(currStack.size() - 3,
0940: new HashSet(top));
0941:
0942: } else {
0943: Assert.isTrue(false,
0944: "Impossible stack combination for "
0945: + "dup2_x1: ... 2 1 2");
0946: }
0947:
0948: } else {
0949: // Form 4: Dup top and put two down
0950: currStack.add(currStack.size() - 2, new HashSet(top));
0951: }
0952: }
0953: }
0954:
0955: public void visit_swap(final Instruction inst) {
0956: final Set top = (Set) currStack.removeLast();
0957: final Set next = (Set) currStack.removeLast();
0958:
0959: checkCategory(top, 1);
0960: checkCategory(next, 1);
0961:
0962: currStack.add(top);
0963: currStack.add(next);
0964: }
0965:
0966: public void visit_iadd(final Instruction inst) {
0967: pop(2);
0968: push(inst);
0969: }
0970:
0971: public void visit_ladd(final Instruction inst) {
0972: pop(2);
0973: push(inst);
0974: }
0975:
0976: public void visit_fadd(final Instruction inst) {
0977: pop(2);
0978: push(inst);
0979: }
0980:
0981: public void visit_dadd(final Instruction inst) {
0982: pop(2);
0983: push(inst);
0984: }
0985:
0986: public void visit_isub(final Instruction inst) {
0987: pop(2);
0988: push(inst);
0989: }
0990:
0991: public void visit_lsub(final Instruction inst) {
0992: pop(2);
0993: push(inst);
0994: }
0995:
0996: public void visit_fsub(final Instruction inst) {
0997: pop(2);
0998: push(inst);
0999: }
1000:
1001: public void visit_dsub(final Instruction inst) {
1002: pop(2);
1003: push(inst);
1004: }
1005:
1006: public void visit_imul(final Instruction inst) {
1007: pop(2);
1008: push(inst);
1009: }
1010:
1011: public void visit_lmul(final Instruction inst) {
1012: pop(2);
1013: push(inst);
1014: }
1015:
1016: public void visit_fmul(final Instruction inst) {
1017: pop(2);
1018: push(inst);
1019: }
1020:
1021: public void visit_dmul(final Instruction inst) {
1022: pop(2);
1023: push(inst);
1024: }
1025:
1026: public void visit_idiv(final Instruction inst) {
1027: pop(2);
1028: push(inst);
1029: }
1030:
1031: public void visit_ldiv(final Instruction inst) {
1032: pop(2);
1033: push(inst);
1034: }
1035:
1036: public void visit_fdiv(final Instruction inst) {
1037: pop(2);
1038: push(inst);
1039: }
1040:
1041: public void visit_ddiv(final Instruction inst) {
1042: pop(2);
1043: push(inst);
1044: }
1045:
1046: public void visit_irem(final Instruction inst) {
1047: pop(2);
1048: push(inst);
1049: }
1050:
1051: public void visit_lrem(final Instruction inst) {
1052: pop(2);
1053: push(inst);
1054: }
1055:
1056: public void visit_frem(final Instruction inst) {
1057: pop(2);
1058: push(inst);
1059: }
1060:
1061: public void visit_drem(final Instruction inst) {
1062: pop(2);
1063: push(inst);
1064: }
1065:
1066: public void visit_ineg(final Instruction inst) {
1067: pop();
1068: push(inst);
1069: }
1070:
1071: public void visit_lneg(final Instruction inst) {
1072: pop();
1073: push(inst);
1074: }
1075:
1076: public void visit_fneg(final Instruction inst) {
1077: pop();
1078: push(inst);
1079: }
1080:
1081: public void visit_dneg(final Instruction inst) {
1082: pop();
1083: push(inst);
1084: }
1085:
1086: public void visit_ishl(final Instruction inst) {
1087: pop(2);
1088: push(inst);
1089: }
1090:
1091: public void visit_lshl(final Instruction inst) {
1092: pop(2);
1093: push(inst);
1094: }
1095:
1096: public void visit_ishr(final Instruction inst) {
1097: pop(2);
1098: push(inst);
1099: }
1100:
1101: public void visit_lshr(final Instruction inst) {
1102: pop(2);
1103: push(inst);
1104: }
1105:
1106: public void visit_iushr(final Instruction inst) {
1107: pop(2);
1108: push(inst);
1109: }
1110:
1111: public void visit_lushr(final Instruction inst) {
1112: pop(2);
1113: push(inst);
1114: }
1115:
1116: public void visit_iand(final Instruction inst) {
1117: pop(2);
1118: push(inst);
1119: }
1120:
1121: public void visit_land(final Instruction inst) {
1122: pop(2);
1123: push(inst);
1124: }
1125:
1126: public void visit_ior(final Instruction inst) {
1127: pop(2);
1128: push(inst);
1129: }
1130:
1131: public void visit_lor(final Instruction inst) {
1132: pop(2);
1133: push(inst);
1134: }
1135:
1136: public void visit_ixor(final Instruction inst) {
1137: pop(2);
1138: push(inst);
1139: }
1140:
1141: public void visit_lxor(final Instruction inst) {
1142: pop(2);
1143: push(inst);
1144: }
1145:
1146: public void visit_iinc(final Instruction inst) {
1147: // Kind of a fine point here. The instruction doesn't change the
1148: // stack, iinc increments a local variable.
1149: }
1150:
1151: public void visit_i2l(final Instruction inst) {
1152: pop();
1153: push(inst);
1154: }
1155:
1156: public void visit_i2f(final Instruction inst) {
1157: pop();
1158: push(inst);
1159: }
1160:
1161: public void visit_i2d(final Instruction inst) {
1162: pop();
1163: push(inst);
1164: }
1165:
1166: public void visit_l2i(final Instruction inst) {
1167: pop();
1168: push(inst);
1169: }
1170:
1171: public void visit_l2f(final Instruction inst) {
1172: pop();
1173: push(inst);
1174: }
1175:
1176: public void visit_l2d(final Instruction inst) {
1177: pop();
1178: push(inst);
1179: }
1180:
1181: public void visit_f2i(final Instruction inst) {
1182: pop();
1183: push(inst);
1184: }
1185:
1186: public void visit_f2l(final Instruction inst) {
1187: pop();
1188: push(inst);
1189: }
1190:
1191: public void visit_f2d(final Instruction inst) {
1192: pop();
1193: push(inst);
1194: }
1195:
1196: public void visit_d2i(final Instruction inst) {
1197: pop();
1198: push(inst);
1199: }
1200:
1201: public void visit_d2l(final Instruction inst) {
1202: pop();
1203: push(inst);
1204: }
1205:
1206: public void visit_d2f(final Instruction inst) {
1207: pop();
1208: push(inst);
1209: }
1210:
1211: public void visit_i2b(final Instruction inst) {
1212: pop();
1213: push(inst);
1214: }
1215:
1216: public void visit_i2c(final Instruction inst) {
1217: pop();
1218: push(inst);
1219: }
1220:
1221: public void visit_i2s(final Instruction inst) {
1222: pop();
1223: push(inst);
1224: }
1225:
1226: public void visit_lcmp(final Instruction inst) {
1227: pop(2);
1228: push(inst);
1229: }
1230:
1231: public void visit_fcmpl(final Instruction inst) {
1232: pop(2);
1233: push(inst);
1234: }
1235:
1236: public void visit_fcmpg(final Instruction inst) {
1237: pop(2);
1238: push(inst);
1239: }
1240:
1241: public void visit_dcmpl(final Instruction inst) {
1242: pop(2);
1243: push(inst);
1244: }
1245:
1246: public void visit_dcmpg(final Instruction inst) {
1247: pop(2);
1248: push(inst);
1249: }
1250:
1251: public void visit_ifeq(final Instruction inst) {
1252: pop();
1253: }
1254:
1255: public void visit_ifne(final Instruction inst) {
1256: pop();
1257: }
1258:
1259: public void visit_iflt(final Instruction inst) {
1260: pop();
1261: }
1262:
1263: public void visit_ifge(final Instruction inst) {
1264: pop();
1265: }
1266:
1267: public void visit_ifgt(final Instruction inst) {
1268: pop();
1269: }
1270:
1271: public void visit_ifle(final Instruction inst) {
1272: pop();
1273: }
1274:
1275: public void visit_if_icmpeq(final Instruction inst) {
1276: pop(2);
1277: }
1278:
1279: public void visit_if_icmpne(final Instruction inst) {
1280: pop(2);
1281: }
1282:
1283: public void visit_if_icmplt(final Instruction inst) {
1284: pop(2);
1285: }
1286:
1287: public void visit_if_icmpge(final Instruction inst) {
1288: pop(2);
1289: }
1290:
1291: public void visit_if_icmpgt(final Instruction inst) {
1292: pop(2);
1293: }
1294:
1295: public void visit_if_icmple(final Instruction inst) {
1296: pop(2);
1297: }
1298:
1299: public void visit_if_acmpeq(final Instruction inst) {
1300: pop(2);
1301: }
1302:
1303: public void visit_if_acmpne(final Instruction inst) {
1304: pop(2);
1305: }
1306:
1307: public void visit_goto(final Instruction inst) {
1308: // Nothing to do
1309: }
1310:
1311: public void visit_jsr(final Instruction inst) {
1312: push(inst);
1313: }
1314:
1315: public void visit_ret(final Instruction inst) {
1316: // Nothing to do
1317: }
1318:
1319: public void visit_switch(final Instruction inst) {
1320: pop();
1321: }
1322:
1323: // Return stuff performed by handle(Instruction)
1324: public void visit_ireturn(final Instruction inst) {
1325:
1326: }
1327:
1328: public void visit_lreturn(final Instruction inst) {
1329:
1330: }
1331:
1332: public void visit_freturn(final Instruction inst) {
1333:
1334: }
1335:
1336: public void visit_dreturn(final Instruction inst) {
1337:
1338: }
1339:
1340: public void visit_areturn(final Instruction inst) {
1341:
1342: }
1343:
1344: public void visit_return(final Instruction inst) {
1345:
1346: }
1347:
1348: public void visit_getstatic(final Instruction inst) {
1349: push(inst);
1350: }
1351:
1352: public void visit_putstatic(final Instruction inst) {
1353: pop();
1354: }
1355:
1356: public void visit_putstatic_nowb(final Instruction inst) {
1357: pop();
1358: }
1359:
1360: public void visit_getfield(final Instruction inst) {
1361: pop();
1362: push(inst);
1363: }
1364:
1365: public void visit_putfield(final Instruction inst) {
1366: pop(2);
1367: }
1368:
1369: public void visit_putfield_nowb(final Instruction inst) {
1370: pop(2);
1371: }
1372:
1373: public void visit_invokevirtual(final Instruction inst) {
1374: final MemberRef method = (MemberRef) inst.operand();
1375: final Type type = method.nameAndType().type();
1376:
1377: pop(type.paramTypes().length);
1378: pop(); // Pop receiver
1379:
1380: if (type.returnType() != Type.VOID) {
1381: push(inst);
1382: }
1383: }
1384:
1385: public void visit_invokespecial(final Instruction inst) {
1386: final MemberRef method = (MemberRef) inst.operand();
1387: final Type type = method.nameAndType().type();
1388:
1389: pop(type.paramTypes().length);
1390: pop(); // Pop receiver
1391:
1392: if (type.returnType() != Type.VOID) {
1393: push(inst);
1394: }
1395: }
1396:
1397: public void visit_invokestatic(final Instruction inst) {
1398: final MemberRef method = (MemberRef) inst.operand();
1399: final Type type = method.nameAndType().type();
1400:
1401: pop(type.paramTypes().length);
1402:
1403: if (type.returnType() != Type.VOID) {
1404: push(inst);
1405: }
1406: }
1407:
1408: public void visit_invokeinterface(final Instruction inst) {
1409: final MemberRef method = (MemberRef) inst.operand();
1410: final Type type = method.nameAndType().type();
1411:
1412: pop(type.paramTypes().length);
1413: pop(); // Pop receiver
1414:
1415: if (type.returnType() != Type.VOID) {
1416: push(inst);
1417: }
1418: }
1419:
1420: public void visit_new(final Instruction inst) {
1421: push(inst);
1422: }
1423:
1424: public void visit_newarray(final Instruction inst) {
1425: pop();
1426: push(inst);
1427: }
1428:
1429: public void visit_arraylength(final Instruction inst) {
1430: pop();
1431: push(inst);
1432: }
1433:
1434: public void visit_athrow(final Instruction inst) {
1435: // I guess...
1436: pop();
1437: push(inst);
1438: }
1439:
1440: public void visit_checkcast(final Instruction inst) {
1441: pop();
1442: push(inst);
1443: }
1444:
1445: public void visit_instanceof (final Instruction inst) {
1446: pop();
1447: push(inst);
1448: }
1449:
1450: public void visit_monitorenter(final Instruction inst) {
1451: pop();
1452: }
1453:
1454: public void visit_monitorexit(final Instruction inst) {
1455: pop();
1456: }
1457:
1458: public void visit_multianewarray(final Instruction inst) {
1459: final MultiArrayOperand operand = (MultiArrayOperand) inst
1460: .operand();
1461: final int dim = operand.dimensions();
1462:
1463: pop(dim);
1464:
1465: push(inst);
1466: }
1467:
1468: public void visit_ifnull(final Instruction inst) {
1469: pop();
1470: }
1471:
1472: public void visit_ifnonnull(final Instruction inst) {
1473: pop();
1474: }
1475:
1476: public void visit_rc(final Instruction inst) {
1477: }
1478:
1479: public void visit_aupdate(final Instruction inst) {
1480: }
1481:
1482: public void visit_supdate(final Instruction inst) {
1483: }
1484:
1485: public void visit_aswizzle(final Instruction inst) {
1486: }
1487:
1488: public void visit_aswrange(final Instruction inst) {
1489: }
1490:
1491: }
|