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.trans;
0022:
0023: import java.io.*;
0024: import java.util.*;
0025:
0026: import EDU.purdue.cs.bloat.cfg.*;
0027: import EDU.purdue.cs.bloat.editor.*;
0028: import EDU.purdue.cs.bloat.tree.*;
0029: import EDU.purdue.cs.bloat.util.*;
0030:
0031: /**
0032: * <tt>ValueFolder</tt> uses a <tt>TreeVisitor</tt> to examine a
0033: * <tt>Node</tt> to determine whether or not it can be simplified. For
0034: * instance, redundent checks are removed and algebraic identities are
0035: * exploited.
0036: *
0037: * @see SideEffectChecker
0038: */
0039: class ValueFolder extends TreeVisitor {
0040: Node node; // (New) value of the folded node
0041:
0042: // If a value number has been reduced down to a constant number
0043: // (ConstantExpr), this array maintains that mapping.
0044: ResizeableArrayList values;
0045:
0046: // Keeps track of which value numbers correspond to expressions that
0047: // allocate new objects (NewExpr, NewArrayExpr, and NewMultiArrayExpr).
0048: BitSet news;
0049:
0050: // Local variable representing the this pointer
0051: LocalExpr this Ptr;
0052:
0053: // Used to determine whether or not a Node in the expression tree
0054: // has side effects
0055: SideEffectChecker sideEffects;
0056:
0057: // Do we actually replace expressions with common value #'s? Or do
0058: // we just calculate the value numbers.
0059: boolean replace;
0060:
0061: //
0062: ArrayList clean;
0063:
0064: /**
0065: * Constructor.
0066: *
0067: * @param replace
0068: * Do we replace values with their folded values?
0069: * @param context
0070: * Needed to create a <Tt>SideEffectChecker</tt>
0071: */
0072: public ValueFolder(final boolean replace,
0073: final EditorContext context) {
0074: this .node = null;
0075: this .replace = replace;
0076: this .clean = new ArrayList();
0077: this .sideEffects = new SideEffectChecker(context);
0078:
0079: this .values = new ResizeableArrayList();
0080: this .news = new BitSet();
0081: this .this Ptr = null;
0082: }
0083:
0084: /**
0085: * Cleans up nodes that
0086: */
0087: public void cleanup() {
0088: final Iterator iter = clean.iterator();
0089:
0090: while (iter.hasNext()) {
0091: final Node node = (Node) iter.next();
0092: node.cleanup();
0093: }
0094: }
0095:
0096: /**
0097: * Returns the simplified version of the most recently simplified
0098: * <tt>Node</tt>. Returns null if no simplification occurred.
0099: */
0100: public Node replacement() {
0101: return node;
0102: }
0103:
0104: public void visitNode(final Node node) {
0105: }
0106:
0107: public void visitLocalExpr(final LocalExpr expr) {
0108: // Determines whether or not the LocalExpr in question is the this
0109: // pointer. If the LocalExpr resides within an InitStmt, and the
0110: // LocalExpr is the first variable defined by the InitStmt, it is
0111: // the this pointer.
0112:
0113: if (this Ptr != null) {
0114: return;
0115: }
0116:
0117: if (expr.parent() instanceof InitStmt) {
0118: final InitStmt stmt = (InitStmt) expr.parent();
0119:
0120: final MethodEditor method = stmt.block().graph().method();
0121:
0122: if (!method.isStatic()) {
0123: Assert.isTrue(stmt.targets().length > 0);
0124:
0125: if (expr == stmt.targets()[0]) {
0126: this Ptr = expr;
0127:
0128: if (ValueFolding.DEBUG) {
0129: System.out.println("this = " + this Ptr);
0130: }
0131: }
0132: }
0133: }
0134: }
0135:
0136: public void visitPhiJoinStmt(final PhiJoinStmt stmt) {
0137: if (!(stmt.target() instanceof LocalExpr)) {
0138: return;
0139: }
0140:
0141: // A PhiJoinStmt may be eliminated if it is meaningless (all of
0142: // its operands have the same value number) or it is redundent
0143: // (its value is already computed by another PhiJoinStmt).
0144:
0145: final int v = stmt.valueNumber();
0146: int ov = -1; // Operand's value number
0147:
0148: final Iterator iter = stmt.operands().iterator();
0149:
0150: // Examine each operand of the PhiJoinStmt.
0151: while (iter.hasNext()) {
0152: final Expr expr = (Expr) iter.next();
0153:
0154: if (replace) {
0155: sideEffects.reset();
0156: expr.visit(sideEffects);
0157:
0158: if (sideEffects.hasSideEffects()) {
0159: return;
0160: }
0161: }
0162:
0163: if (expr.valueNumber() == -1) {
0164: continue;
0165: }
0166:
0167: if ((ov != -1) && (expr.valueNumber() != ov)) {
0168: // At least two operands have different value numbers. The
0169: // PhiJoinStmt cannot be simplified.
0170: return;
0171: }
0172:
0173: ov = expr.valueNumber();
0174: }
0175:
0176: if (ov == -1) {
0177: // We cannot replace an PhiJoinStmt with no operands
0178: Assert.isFalse(replace && (stmt.operands().size() == 0));
0179: ov = v;
0180: }
0181:
0182: // All operands have same value number or -1.
0183: values.ensureSize(Math.max(v, ov) + 1);
0184: final ConstantExpr value = (ConstantExpr) values.get(ov);
0185:
0186: if (value != null) {
0187: node = value;
0188: values.set(v, value);
0189:
0190: if (replace) {
0191: stmt.block().tree().removeStmt(stmt);
0192: }
0193: }
0194: }
0195:
0196: public void visitStoreExpr(final StoreExpr expr) {
0197: if (expr.expr() instanceof CheckExpr) {
0198: // This makes copy propagation more effective after PRE.
0199: // x := rc(y) --> rc(x := y)
0200: final CheckExpr rc = (CheckExpr) expr.expr();
0201:
0202: if (replace) {
0203: final Node parent = expr.parent();
0204:
0205: // x := rc(y) --> x := y
0206: expr.visit(new ReplaceVisitor(rc, rc.expr()));
0207:
0208: // rc(y) --> rc(x := y)
0209: rc.visit(new ReplaceVisitor(rc.expr(), expr));
0210:
0211: // x := rc(y) --> rc(x := y)
0212: parent.visit(new ReplaceVisitor(expr, rc));
0213:
0214: node = rc;
0215:
0216: } else {
0217: // Don't bother.
0218: node = null;
0219: }
0220:
0221: return;
0222: }
0223:
0224: if (expr.target() instanceof LocalExpr) {
0225: // If we're assigning into a local variable,
0226:
0227: final int v = expr.valueNumber();
0228: final int lv = expr.target().valueNumber();
0229: final int rv = expr.expr().valueNumber();
0230:
0231: int max = v;
0232: max = Math.max(max, lv);
0233: max = Math.max(max, rv);
0234: values.ensureSize(max + 1);
0235:
0236: boolean reffects = false;
0237:
0238: if (replace) {
0239: sideEffects.reset();
0240: expr.expr().visit(sideEffects);
0241: reffects = sideEffects.hasSideEffects();
0242: }
0243:
0244: final ConstantExpr rexpr = (ConstantExpr) values.get(rv);
0245:
0246: if (rexpr != null) {
0247: // The entire StoreExpr has a constant value
0248: if (!replace) {
0249: node = rexpr;
0250: values.set(v, node);
0251:
0252: } else if (!reffects
0253: && (expr.target().uses().size() == 0)) {
0254: // Replace the rhs with constant mapped to its value number
0255: node = new ConstantExpr(rexpr.value(), expr.type());
0256: node.setValueNumber(v);
0257: values.set(v, node);
0258: expr.replaceWith(node);
0259: }
0260: }
0261: }
0262: }
0263:
0264: public void visitNewMultiArrayExpr(final NewMultiArrayExpr expr) {
0265: // Keep track of the value numbers of expressions that create new
0266: // objects.
0267:
0268: if (expr.valueNumber() != -1) {
0269: if (ValueFolding.DEBUG) {
0270: System.out.println("New " + expr);
0271: }
0272:
0273: news.set(expr.valueNumber());
0274: }
0275: }
0276:
0277: public void visitNewArrayExpr(final NewArrayExpr expr) {
0278: // Keep track of the value numbers of expressions that create new
0279: // objects.
0280:
0281: if (expr.valueNumber() != -1) {
0282: if (ValueFolding.DEBUG) {
0283: System.out.println("New " + expr);
0284: }
0285:
0286: news.set(expr.valueNumber());
0287: }
0288: }
0289:
0290: public void visitNewExpr(final NewExpr expr) {
0291: // Keep track of the value number of expression that create new
0292: // objects.
0293:
0294: if (expr.valueNumber() != -1) {
0295: if (ValueFolding.DEBUG) {
0296: System.out.println("New " + expr);
0297: }
0298:
0299: news.set(expr.valueNumber());
0300: }
0301: }
0302:
0303: public void visitRCExpr(final RCExpr expr) {
0304: boolean move = false; // Can we remove the RCExpr
0305:
0306: final int v = expr.expr().valueNumber();
0307:
0308: if (expr.expr() instanceof RCExpr) {
0309: // If the expression being checked for residency is itself an
0310: // RCExpr, then the outer one is redundent.
0311: move = true;
0312:
0313: if (ValueFolding.DEBUG) {
0314: System.out.println("folding redundant rc in " + expr);
0315: }
0316:
0317: } else if (v != -1) {
0318: if ((this Ptr != null) && (this Ptr.valueNumber() == v)) {
0319: // We know that the this pointer is always resident, so we
0320: // don't need to perform an rc on it.
0321: move = true;
0322:
0323: if (ValueFolding.DEBUG) {
0324: System.out.println("folding rc(this) = " + expr);
0325: }
0326:
0327: } else if (news.get(v)) {
0328: // We know that the result of a new expression is always
0329: // resident, so we don't need to perform an rc on it.
0330: move = true;
0331:
0332: if (ValueFolding.DEBUG) {
0333: System.out.println("folding rc(new) = " + expr);
0334: }
0335: }
0336: }
0337:
0338: if (move) {
0339: node = expr.expr();
0340:
0341: if (replace) {
0342: // rc(this) --> this
0343: // rc(rc(x)) --> rc(x)
0344: node.setParent(null);
0345: expr.replaceWith(node, false);
0346: expr.cleanupOnly();
0347: }
0348: }
0349: }
0350:
0351: public void visitZeroCheckExpr(final ZeroCheckExpr expr) {
0352: boolean move = false;
0353:
0354: final int v = expr.expr().valueNumber();
0355:
0356: if (expr.expr() instanceof ZeroCheckExpr) {
0357: move = true;
0358:
0359: if (ValueFolding.DEBUG) {
0360: System.out.println("folding redundant ZeroCheck in "
0361: + expr);
0362: }
0363:
0364: } else if (v != -1) {
0365: if ((this Ptr != null) && (this Ptr.valueNumber() == v)) {
0366: // The this pointer can't be null.
0367:
0368: move = true;
0369:
0370: if (ValueFolding.DEBUG) {
0371: System.out.println("folding ZeroCheck(this) = "
0372: + expr);
0373: }
0374:
0375: } else if (news.get(v)) {
0376: // Newly created objects can't be null.
0377: move = true;
0378:
0379: if (ValueFolding.DEBUG) {
0380: System.out.println("folding ZeroCheck(new) = "
0381: + expr);
0382: }
0383:
0384: } else {
0385: // Check to see if the value number associated with the
0386: // expression being checked for zero-ness has a constant value
0387: // of zero.
0388: ConstantExpr eexpr = null;
0389:
0390: if (v < values.size()) {
0391: eexpr = (ConstantExpr) values.get(v);
0392: }
0393:
0394: if (eexpr != null) {
0395: final Object value = eexpr.value();
0396:
0397: if (value instanceof Long) {
0398: if (((Long) value).longValue() != 0L) {
0399: move = true;
0400: }
0401:
0402: } else if ((value instanceof Byte)
0403: || (value instanceof Short)
0404: || (value instanceof Integer)) {
0405: if (((Number) value).intValue() != 0) {
0406: move = true;
0407: }
0408:
0409: } else if (value instanceof Character) {
0410: if (((Character) value).charValue() != 0) {
0411: move = true;
0412: }
0413: }
0414: }
0415: }
0416: }
0417:
0418: if (move) {
0419: node = expr.expr();
0420:
0421: if (replace) {
0422: // ZeroCheck(1) --> 1
0423: // ZeroCheck(this) --> this
0424: // ZeroCheck(ZeroCheck(x)) --> ZeroCheck(x)
0425: node.setParent(null);
0426: expr.replaceWith(node, false);
0427: expr.cleanupOnly();
0428: }
0429: }
0430: }
0431:
0432: public void visitUCExpr(final UCExpr expr) {
0433: if (expr.expr() instanceof UCExpr) {
0434: // Remove redundent update checks
0435:
0436: final UCExpr uc = (UCExpr) expr.expr();
0437:
0438: if (uc.kind() == expr.kind()) {
0439: node = uc;
0440:
0441: if (replace) {
0442: // uc(uc(x)) --> uc(x)
0443: expr.visit(new ReplaceVisitor(uc, uc.expr()));
0444: uc.cleanupOnly();
0445: }
0446: }
0447: }
0448: }
0449:
0450: public void visitArithExpr(final ArithExpr expr) {
0451: if (expr.left().type().isIntegral()) {
0452: foldArithInteger(expr);
0453: } else if (expr.left().type().equals(Type.LONG)) {
0454: foldArithLong(expr);
0455: } else if (expr.left().type().equals(Type.FLOAT)) {
0456: foldArithFloat(expr);
0457: } else if (expr.left().type().equals(Type.DOUBLE)) {
0458: foldArithDouble(expr);
0459: }
0460: }
0461:
0462: /**
0463: * Look for integer arithmetic identities...
0464: */
0465: private void foldArithInteger(final ArithExpr expr) {
0466: final int v = expr.valueNumber();
0467: final int lv = expr.left().valueNumber();
0468: final int rv = expr.right().valueNumber();
0469:
0470: int max = v;
0471: max = Math.max(max, lv);
0472: max = Math.max(max, rv);
0473: values.ensureSize(max + 1);
0474:
0475: ConstantExpr lexpr = null;
0476: ConstantExpr rexpr = null;
0477:
0478: if ((0 <= lv) && (0 <= lv) && (lv < values.size())) {
0479: lexpr = (ConstantExpr) values.get(lv);
0480: }
0481:
0482: if ((0 <= rv) && (0 <= rv) && (rv < values.size())) {
0483: rexpr = (ConstantExpr) values.get(rv);
0484: }
0485:
0486: boolean leffects = false;
0487: boolean reffects = false;
0488:
0489: if (replace) {
0490: sideEffects.reset();
0491: expr.left().visit(sideEffects);
0492: leffects = sideEffects.hasSideEffects();
0493:
0494: sideEffects.reset();
0495: expr.right().visit(sideEffects);
0496: reffects = sideEffects.hasSideEffects();
0497: }
0498:
0499: if ((lexpr != null) && (rexpr != null) && !leffects
0500: && !reffects) {
0501: // Okay, both of the ArithExpr's operands evaluate to constants
0502: // and there are no side effects. We may be able to exploit
0503: // various algebraic identites.
0504: Integer value = null;
0505:
0506: final int lval = ((Number) lexpr.value()).intValue();
0507: final int rval = ((Number) rexpr.value()).intValue();
0508:
0509: switch (expr.operation()) {
0510: case ArithExpr.ADD:
0511: value = new Integer(lval + rval);
0512: break;
0513: case ArithExpr.AND:
0514: value = new Integer(lval & rval);
0515: break;
0516: case ArithExpr.DIV:
0517: if (rval != 0) {
0518: value = new Integer(lval / rval);
0519: }
0520: break;
0521: case ArithExpr.MUL:
0522: value = new Integer(lval * rval);
0523: break;
0524: case ArithExpr.IOR:
0525: value = new Integer(lval | rval);
0526: break;
0527: case ArithExpr.REM:
0528: if (rval != 0) {
0529: value = new Integer(lval % rval);
0530: }
0531: break;
0532: case ArithExpr.SUB:
0533: value = new Integer(lval - rval);
0534: break;
0535: case ArithExpr.XOR:
0536: value = new Integer(lval ^ rval);
0537: break;
0538: default:
0539: break;
0540: }
0541:
0542: if (value != null) {
0543: node = new ConstantExpr(value, expr.type());
0544: node.setValueNumber(v);
0545:
0546: values.set(v, node);
0547:
0548: if (replace) {
0549: expr.replaceWith(node);
0550: }
0551: }
0552:
0553: } else if ((lexpr == null) && (rexpr != null) && !reffects) {
0554: // Only the right operand evaluates to a constant...
0555: final int rval = ((Number) rexpr.value()).intValue();
0556:
0557: switch (rval) {
0558: case 0:
0559: // x + 0 = x
0560: // x - 0 = x
0561: // x | 0 = x
0562: // x * 0 = 0
0563: // x & 0 = 0
0564: switch (expr.operation()) {
0565: case ArithExpr.ADD:
0566: case ArithExpr.SUB:
0567: case ArithExpr.IOR:
0568: node = expr.left();
0569:
0570: if (replace) {
0571: node.setParent(null);
0572: expr.replaceWith(node, false);
0573: expr.right().cleanup();
0574: expr.cleanupOnly();
0575: }
0576: break;
0577: case ArithExpr.MUL:
0578: case ArithExpr.AND:
0579: node = new ConstantExpr(new Integer(0), expr.type());
0580: node.setValueNumber(v);
0581:
0582: values.set(v, node);
0583:
0584: if (replace) {
0585: expr.replaceWith(node);
0586: }
0587: break;
0588: }
0589: break;
0590: case 1:
0591: // x * 1 = x
0592: // x / 1 = x
0593: // x % 1 = 0
0594: switch (expr.operation()) {
0595: case ArithExpr.MUL:
0596: case ArithExpr.DIV:
0597: node = expr.left();
0598:
0599: if (replace) {
0600: node.setParent(null);
0601: expr.replaceWith(node, false);
0602: expr.right().cleanup();
0603: expr.cleanupOnly();
0604: }
0605: break;
0606: case ArithExpr.REM:
0607: node = new ConstantExpr(new Integer(0), expr.type());
0608: node.setValueNumber(v);
0609:
0610: values.set(v, node);
0611:
0612: if (replace) {
0613: expr.replaceWith(node);
0614: }
0615: break;
0616: }
0617: break;
0618: case -1:
0619: // x * -1 = -x
0620: // x / -1 = -x
0621: switch (expr.operation()) {
0622: case ArithExpr.MUL:
0623: case ArithExpr.DIV:
0624: if (replace) {
0625: expr.left().setParent(null);
0626: node = new NegExpr(expr.left(), expr.type());
0627: node.setValueNumber(v);
0628: expr.replaceWith(node, false);
0629: expr.right().cleanup();
0630: expr.cleanupOnly();
0631:
0632: } else {
0633: node = new NegExpr((Expr) expr.left().clone(),
0634: expr.type());
0635: node.setValueNumber(v);
0636: clean.add(node);
0637: }
0638: break;
0639: }
0640: break;
0641: }
0642:
0643: } else if ((lexpr != null) && (rexpr == null) && !leffects) {
0644: // Only left operand resolves to a constant value...
0645: final int lval = ((Number) lexpr.value()).intValue();
0646:
0647: switch (lval) {
0648: case 0:
0649: // 0 + x = x
0650: // 0 - x = -x
0651: // 0 | x = x
0652: // 0 * x = 0
0653: // 0 & x = 0
0654: switch (expr.operation()) {
0655: case ArithExpr.ADD:
0656: case ArithExpr.IOR:
0657: node = expr.right();
0658:
0659: if (replace) {
0660: node.setParent(null);
0661: expr.replaceWith(node, false);
0662: expr.left().cleanup();
0663: expr.cleanupOnly();
0664: }
0665: break;
0666: case ArithExpr.SUB:
0667: if (replace) {
0668: expr.right().setParent(null);
0669: node = new NegExpr(expr.right(), expr.type());
0670: node.setValueNumber(v);
0671: expr.replaceWith(node, false);
0672: expr.left().cleanup();
0673: expr.cleanupOnly();
0674: } else {
0675: node = new NegExpr((Expr) expr.right().clone(),
0676: expr.type());
0677: node.setValueNumber(v);
0678: clean.add(node);
0679: }
0680: break;
0681: case ArithExpr.MUL:
0682: case ArithExpr.AND:
0683: node = new ConstantExpr(new Integer(0), expr.type());
0684: node.setValueNumber(v);
0685:
0686: values.set(v, node);
0687:
0688: if (replace) {
0689: expr.replaceWith(node);
0690: }
0691: break;
0692: }
0693: break;
0694: case 1:
0695: // 1 * x = x
0696: switch (expr.operation()) {
0697: case ArithExpr.MUL:
0698: node = expr.right();
0699:
0700: if (replace) {
0701: node.setParent(null);
0702: expr.replaceWith(node, false);
0703: expr.left().cleanup();
0704: expr.cleanupOnly();
0705: }
0706: break;
0707: }
0708: break;
0709: case -1:
0710: // -1 * x = -x
0711: switch (expr.operation()) {
0712: case ArithExpr.MUL:
0713: if (replace) {
0714: expr.right().setParent(null);
0715: node = new NegExpr(expr.right(), expr.type());
0716: node.setValueNumber(v);
0717: expr.replaceWith(node, false);
0718: expr.left().cleanup();
0719: expr.cleanupOnly();
0720: } else {
0721: node = new NegExpr((Expr) expr.right().clone(),
0722: expr.type());
0723: node.setValueNumber(v);
0724: clean.add(node);
0725: }
0726: break;
0727: }
0728: break;
0729: }
0730: }
0731: }
0732:
0733: /**
0734: * Look for long arithmetic indentities...
0735: */
0736: private void foldArithLong(final ArithExpr expr) {
0737: final int v = expr.valueNumber();
0738: final int lv = expr.left().valueNumber();
0739: final int rv = expr.right().valueNumber();
0740:
0741: int max = v;
0742: max = Math.max(max, lv);
0743: max = Math.max(max, rv);
0744: values.ensureSize(max + 1);
0745:
0746: ConstantExpr lexpr = null;
0747: ConstantExpr rexpr = null;
0748:
0749: if ((0 <= lv) && (lv < values.size())) {
0750: lexpr = (ConstantExpr) values.get(lv);
0751: }
0752:
0753: if ((0 <= rv) && (rv < values.size())) {
0754: rexpr = (ConstantExpr) values.get(rv);
0755: }
0756:
0757: boolean leffects = false;
0758: boolean reffects = false;
0759:
0760: if (replace) {
0761: sideEffects.reset();
0762: expr.left().visit(sideEffects);
0763: leffects = sideEffects.hasSideEffects();
0764:
0765: sideEffects.reset();
0766: expr.right().visit(sideEffects);
0767: reffects = sideEffects.hasSideEffects();
0768: }
0769:
0770: if ((lexpr != null) && (rexpr != null) && !leffects
0771: && !reffects) {
0772: Number value = null;
0773:
0774: final long lval = ((Long) lexpr.value()).longValue();
0775: final long rval = ((Long) rexpr.value()).longValue();
0776:
0777: switch (expr.operation()) {
0778: case ArithExpr.ADD:
0779: value = new Long(lval + rval);
0780: break;
0781: case ArithExpr.AND:
0782: value = new Long(lval & rval);
0783: break;
0784: case ArithExpr.DIV:
0785: if (rval != 0) {
0786: value = new Long(lval / rval);
0787: }
0788: break;
0789: case ArithExpr.MUL:
0790: value = new Long(lval * rval);
0791: break;
0792: case ArithExpr.IOR:
0793: value = new Long(lval | rval);
0794: break;
0795: case ArithExpr.REM:
0796: if (rval != 0L) {
0797: value = new Long(lval % rval);
0798: }
0799: break;
0800: case ArithExpr.SUB:
0801: value = new Long(lval - rval);
0802: break;
0803: case ArithExpr.XOR:
0804: value = new Long(lval ^ rval);
0805: break;
0806: case ArithExpr.CMP:
0807: if (lval > rval) {
0808: value = new Integer(1);
0809: } else if (lval < rval) {
0810: value = new Integer(-1);
0811: } else {
0812: value = new Integer(0);
0813: }
0814: break;
0815: default:
0816: break;
0817: }
0818:
0819: if (value != null) {
0820: node = new ConstantExpr(value, expr.type());
0821: node.setValueNumber(v);
0822:
0823: values.set(v, node);
0824:
0825: if (replace) {
0826: expr.replaceWith(node);
0827: }
0828: }
0829: } else if ((lexpr == null) && (rexpr != null)) {
0830: final long rval = ((Long) rexpr.value()).longValue();
0831:
0832: if (reffects) {
0833: return;
0834: }
0835:
0836: if (rval == 0L) {
0837: // x + 0 = x
0838: // x - 0 = x
0839: // x | 0 = x
0840: // x * 0 = 0
0841: // x & 0 = 0
0842: switch (expr.operation()) {
0843: case ArithExpr.ADD:
0844: case ArithExpr.SUB:
0845: case ArithExpr.IOR:
0846: node = expr.left();
0847:
0848: if (replace) {
0849: node.setParent(null);
0850: expr.replaceWith(node, false);
0851: expr.right().cleanup();
0852: expr.cleanupOnly();
0853: }
0854: break;
0855: case ArithExpr.MUL:
0856: case ArithExpr.AND:
0857: node = new ConstantExpr(new Long(0L), expr.type());
0858: node.setValueNumber(v);
0859:
0860: values.set(v, node);
0861:
0862: if (replace) {
0863: expr.replaceWith(node);
0864: }
0865: break;
0866: }
0867: } else if (rval == 1L) {
0868: // x * 1 = x
0869: // x / 1 = x
0870: // x % 1 = 0
0871: switch (expr.operation()) {
0872: case ArithExpr.MUL:
0873: case ArithExpr.DIV:
0874: node = expr.left();
0875:
0876: if (replace) {
0877: node.setParent(null);
0878: expr.replaceWith(node, false);
0879: expr.right().cleanup();
0880: expr.cleanupOnly();
0881: }
0882: break;
0883: case ArithExpr.REM:
0884: node = new ConstantExpr(new Long(0L), expr.type());
0885: node.setValueNumber(v);
0886:
0887: values.set(v, node);
0888:
0889: if (replace) {
0890: expr.replaceWith(node);
0891: }
0892: break;
0893: }
0894: } else if (rval == -1L) {
0895: // x * -1 = -x
0896: // x / -1 = -x
0897: switch (expr.operation()) {
0898: case ArithExpr.MUL:
0899: case ArithExpr.DIV:
0900: if (replace) {
0901: expr.left().setParent(null);
0902: node = new NegExpr(expr.left(), Type.LONG);
0903: node.setValueNumber(v);
0904: expr.replaceWith(node, false);
0905: expr.right().cleanup();
0906: expr.cleanupOnly();
0907: } else {
0908: node = new NegExpr((Expr) expr.left().clone(),
0909: Type.LONG);
0910: node.setValueNumber(v);
0911: clean.add(node);
0912: }
0913: break;
0914: }
0915: }
0916: } else if ((lexpr != null) && (rexpr == null)) {
0917: final long lval = ((Long) lexpr.value()).longValue();
0918: if (lval == 0L) {
0919: // 0 + x = x
0920: // 0 - x = -x
0921: // 0 | x = x
0922: // 0 * x = 0
0923: // 0 & x = 0
0924: switch (expr.operation()) {
0925: case ArithExpr.ADD:
0926: case ArithExpr.IOR:
0927: node = expr.right();
0928:
0929: if (replace) {
0930: node.setParent(null);
0931: expr.replaceWith(node, false);
0932: expr.left().cleanup();
0933: expr.cleanupOnly();
0934: }
0935: break;
0936: case ArithExpr.SUB:
0937: if (replace) {
0938: expr.right().setParent(null);
0939: node = new NegExpr(expr.right(), Type.LONG);
0940: node.setValueNumber(v);
0941: expr.replaceWith(node, false);
0942: expr.left().cleanup();
0943: expr.cleanupOnly();
0944: } else {
0945: node = new NegExpr((Expr) expr.right().clone(),
0946: Type.LONG);
0947: node.setValueNumber(v);
0948: clean.add(node);
0949: }
0950: break;
0951: case ArithExpr.MUL:
0952: case ArithExpr.AND:
0953: node = new ConstantExpr(new Long(0L), expr.type());
0954: node.setValueNumber(v);
0955:
0956: values.set(v, node);
0957:
0958: if (replace) {
0959: expr.replaceWith(node);
0960: }
0961: break;
0962: }
0963: } else if (lval == 1L) {
0964: // 1 * x = x
0965: switch (expr.operation()) {
0966: case ArithExpr.MUL:
0967: node = expr.right();
0968:
0969: if (replace) {
0970: node.setParent(null);
0971: expr.replaceWith(node, false);
0972: expr.left().cleanup();
0973: expr.cleanupOnly();
0974: }
0975: break;
0976: }
0977: } else if (lval == -1L) {
0978: // -1 * x = -x
0979: switch (expr.operation()) {
0980: case ArithExpr.MUL:
0981: if (replace) {
0982: expr.right().setParent(null);
0983: node = new NegExpr(expr.right(), Type.LONG);
0984: node.setValueNumber(v);
0985: expr.replaceWith(node, false);
0986: expr.left().cleanup();
0987: expr.cleanupOnly();
0988: } else {
0989: node = new NegExpr((Expr) expr.right().clone(),
0990: Type.LONG);
0991: node.setValueNumber(v);
0992: clean.add(node);
0993: }
0994: break;
0995: }
0996: }
0997: }
0998: }
0999:
1000: /**
1001: * Look for float arithmetic identities...
1002: */
1003: private void foldArithFloat(final ArithExpr expr) {
1004: final int v = expr.valueNumber();
1005: final int lv = expr.left().valueNumber();
1006: final int rv = expr.right().valueNumber();
1007:
1008: int max = v;
1009: max = Math.max(max, lv);
1010: max = Math.max(max, rv);
1011: values.ensureSize(max + 1);
1012:
1013: ConstantExpr lexpr = null;
1014: ConstantExpr rexpr = null;
1015:
1016: if ((0 <= lv) && (lv < values.size())) {
1017: lexpr = (ConstantExpr) values.get(lv);
1018: }
1019:
1020: if ((0 <= rv) && (rv < values.size())) {
1021: rexpr = (ConstantExpr) values.get(rv);
1022: }
1023:
1024: if ((lexpr == null) || (rexpr == null)) {
1025: return;
1026: }
1027:
1028: final Float rvalue = (Float) rexpr.value();
1029: final Float lvalue = (Float) lexpr.value();
1030:
1031: if (lvalue.isNaN() || lvalue.isInfinite()) {
1032: return;
1033: }
1034:
1035: if (rvalue.isNaN() || rvalue.isInfinite()) {
1036: return;
1037: }
1038:
1039: boolean leffects = false;
1040: boolean reffects = false;
1041:
1042: if (replace) {
1043: sideEffects.reset();
1044: expr.left().visit(sideEffects);
1045: leffects = sideEffects.hasSideEffects();
1046:
1047: sideEffects.reset();
1048: expr.right().visit(sideEffects);
1049: reffects = sideEffects.hasSideEffects();
1050:
1051: if (leffects || reffects) {
1052: return;
1053: }
1054: }
1055:
1056: // Can't fold (x op C) = y since x may be NaN or infinite
1057: // or +/-0.0.
1058:
1059: Number value = null;
1060:
1061: final float lval = lvalue.floatValue();
1062: final float rval = rvalue.floatValue();
1063:
1064: switch (expr.operation()) {
1065: case ArithExpr.ADD:
1066: value = new Float(lval + rval);
1067: break;
1068: case ArithExpr.DIV:
1069: value = new Float(lval / rval);
1070: break;
1071: case ArithExpr.MUL:
1072: value = new Float(lval * rval);
1073: break;
1074: case ArithExpr.REM:
1075: value = new Float(lval % rval);
1076: break;
1077: case ArithExpr.SUB:
1078: value = new Float(lval - rval);
1079: break;
1080: case ArithExpr.CMP:
1081: if (lval > rval) {
1082: value = new Integer(1);
1083: } else if (lval < rval) {
1084: value = new Integer(-1);
1085: } else {
1086: value = new Integer(0);
1087: }
1088: break;
1089: default:
1090: break;
1091: }
1092:
1093: if (value != null) {
1094: node = new ConstantExpr(value, expr.type());
1095: node.setValueNumber(v);
1096:
1097: values.set(v, node);
1098:
1099: if (replace) {
1100: expr.replaceWith(node);
1101: }
1102: }
1103: }
1104:
1105: /**
1106: * Look for double arithmetic identities...
1107: */
1108: private void foldArithDouble(final ArithExpr expr) {
1109: final int v = expr.valueNumber();
1110: final int lv = expr.left().valueNumber();
1111: final int rv = expr.right().valueNumber();
1112:
1113: int max = v;
1114: max = Math.max(max, lv);
1115: max = Math.max(max, rv);
1116: values.ensureSize(max + 1);
1117:
1118: ConstantExpr lexpr = null;
1119: ConstantExpr rexpr = null;
1120:
1121: if ((0 <= lv) && (lv < values.size())) {
1122: lexpr = (ConstantExpr) values.get(lv);
1123: }
1124:
1125: if ((0 <= rv) && (rv < values.size())) {
1126: rexpr = (ConstantExpr) values.get(rv);
1127: }
1128:
1129: if ((lexpr == null) || (rexpr == null)) {
1130: return;
1131: }
1132:
1133: final Double rvalue = (Double) rexpr.value();
1134: final Double lvalue = (Double) lexpr.value();
1135:
1136: if (lvalue.isNaN() || lvalue.isInfinite()) {
1137: return;
1138: }
1139:
1140: if (rvalue.isNaN() || rvalue.isInfinite()) {
1141: return;
1142: }
1143:
1144: boolean leffects = false;
1145: boolean reffects = false;
1146:
1147: if (replace) {
1148: sideEffects.reset();
1149: expr.left().visit(sideEffects);
1150: leffects = sideEffects.hasSideEffects();
1151:
1152: sideEffects.reset();
1153: expr.right().visit(sideEffects);
1154: reffects = sideEffects.hasSideEffects();
1155:
1156: if (leffects || reffects) {
1157: return;
1158: }
1159: }
1160:
1161: // Can't fold (x op C) = y since x may be NaN or infinite
1162: // or +/-0.0.
1163:
1164: Number value = null;
1165:
1166: final double lval = lvalue.doubleValue();
1167: final double rval = rvalue.doubleValue();
1168:
1169: switch (expr.operation()) {
1170: case ArithExpr.ADD:
1171: value = new Double(lval + rval);
1172: break;
1173: case ArithExpr.DIV:
1174: value = new Double(lval / rval);
1175: break;
1176: case ArithExpr.MUL:
1177: value = new Double(lval * rval);
1178: break;
1179: case ArithExpr.REM:
1180: value = new Double(lval % rval);
1181: break;
1182: case ArithExpr.SUB:
1183: value = new Double(lval - rval);
1184: break;
1185: case ArithExpr.CMP:
1186: if (lval > rval) {
1187: value = new Integer(1);
1188: } else if (lval < rval) {
1189: value = new Integer(-1);
1190: } else {
1191: value = new Integer(0);
1192: }
1193: break;
1194: default:
1195: break;
1196: }
1197:
1198: if (value != null) {
1199: node = new ConstantExpr(value, expr.type());
1200: node.setValueNumber(v);
1201:
1202: values.set(v, node);
1203:
1204: if (replace) {
1205: expr.replaceWith(node);
1206: }
1207: }
1208: }
1209:
1210: public void visitCastExpr(final CastExpr expr) {
1211: // Note: we can't fold i2b, i2c, i2s, i2l, i2f, f2i, ...
1212: // We only fold (String) "" and (C) null.
1213:
1214: final int v = expr.valueNumber();
1215: final int ev = expr.expr().valueNumber();
1216: values.ensureSize(Math.max(v, ev) + 1);
1217:
1218: ConstantExpr eexpr = null;
1219:
1220: if ((0 <= ev) && (ev < values.size())) {
1221: eexpr = (ConstantExpr) values.get(ev);
1222: }
1223:
1224: if (eexpr == null) {
1225: return;
1226: }
1227:
1228: if (replace) {
1229: sideEffects.reset();
1230: expr.expr().visit(sideEffects);
1231: final boolean effects = sideEffects.hasSideEffects();
1232:
1233: if (effects) {
1234: return;
1235: }
1236: }
1237:
1238: final Object evalue = eexpr.value();
1239:
1240: if ((evalue instanceof String)
1241: && expr.castType().equals(Type.STRING)) {
1242: // The ConstantExpr must be ""
1243: node = new ConstantExpr(evalue, expr.castType());
1244: node.setValueNumber(v);
1245:
1246: values.set(v, node);
1247:
1248: if (replace) {
1249: expr.replaceWith(node);
1250: }
1251:
1252: return;
1253: }
1254:
1255: if (expr.castType().isReference()) {
1256: if ((evalue == null) && expr.castType().isReference()) {
1257: // The ConstantExpr is null
1258: node = new ConstantExpr(null, expr.castType());
1259: node.setValueNumber(v);
1260:
1261: values.set(v, node);
1262:
1263: if (replace) {
1264: expr.replaceWith(node);
1265: }
1266: }
1267:
1268: return;
1269: }
1270: }
1271:
1272: public void visitNegExpr(final NegExpr expr) {
1273: final int v = expr.valueNumber();
1274: final int ev = expr.expr().valueNumber();
1275: values.ensureSize(Math.max(v, ev) + 1);
1276:
1277: ConstantExpr eexpr = null;
1278:
1279: if ((0 <= ev) && (ev < values.size())) {
1280: eexpr = (ConstantExpr) values.get(ev);
1281: }
1282:
1283: if (eexpr != null) {
1284: // If the operand of the NegExpr is a constant value, simply
1285: // replace the constant with its negation and remove the NegExpr.
1286:
1287: final Number evalue = (Number) eexpr.value();
1288:
1289: boolean eeffects = false;
1290:
1291: if (replace) {
1292: sideEffects.reset();
1293: expr.expr().visit(sideEffects);
1294: eeffects = sideEffects.hasSideEffects();
1295: }
1296:
1297: if (!eeffects) {
1298: Number value = null;
1299:
1300: if (evalue instanceof Integer) {
1301: value = new Integer(-evalue.intValue());
1302: } else if (value instanceof Long) {
1303: value = new Long(-evalue.longValue());
1304: } else if (value instanceof Float) {
1305: value = new Float(-evalue.floatValue());
1306: } else if (value instanceof Double) {
1307: value = new Double(-evalue.doubleValue());
1308: }
1309:
1310: if (value != null) {
1311: node = new ConstantExpr(value, expr.type());
1312: node.setValueNumber(v);
1313:
1314: values.set(v, node);
1315:
1316: if (replace) {
1317: expr.replaceWith(node);
1318: }
1319:
1320: return;
1321: }
1322: }
1323: }
1324:
1325: if (expr.expr() instanceof NegExpr) {
1326: // -(-x) --> x
1327:
1328: final NegExpr neg = (NegExpr) expr.expr();
1329: node = neg.expr();
1330:
1331: if (replace) {
1332: expr.parent().visit(new ReplaceVisitor(expr, node));
1333: expr.cleanupOnly();
1334: neg.cleanupOnly();
1335: }
1336: }
1337: }
1338:
1339: public void visitShiftExpr(final ShiftExpr expr) {
1340: // Exploit shifting zero bits or shifting zero
1341:
1342: final int v = expr.valueNumber();
1343: final int ev = expr.expr().valueNumber();
1344: final int bv = expr.bits().valueNumber();
1345:
1346: int max = v;
1347: max = Math.max(max, ev);
1348: max = Math.max(max, bv);
1349: values.ensureSize(max + 1);
1350:
1351: ConstantExpr eexpr = null;
1352: ConstantExpr bexpr = null;
1353:
1354: if ((0 <= ev) && (ev < values.size())) {
1355: eexpr = (ConstantExpr) values.get(ev);
1356: }
1357:
1358: if ((0 <= bv) && (bv < values.size())) {
1359: bexpr = (ConstantExpr) values.get(bv);
1360: }
1361:
1362: Object evalue = null;
1363: Object bvalue = null;
1364: boolean eeffects = false;
1365: boolean beffects = false;
1366:
1367: if (eexpr != null) {
1368: evalue = eexpr.value();
1369: }
1370:
1371: if (bexpr != null) {
1372: bvalue = bexpr.value();
1373: }
1374:
1375: if (replace) {
1376: sideEffects.reset();
1377: expr.expr().visit(sideEffects);
1378: eeffects = sideEffects.hasSideEffects();
1379:
1380: sideEffects.reset();
1381: expr.bits().visit(sideEffects);
1382: beffects = sideEffects.hasSideEffects();
1383: }
1384:
1385: if ((eexpr == null) && (bexpr != null)) {
1386: if (bvalue.equals(new Integer(0))
1387: || bvalue.equals(new Long(0))) {
1388: // x << 0 = x
1389: // x >> 0 = x
1390: // x >>> 0 = x
1391: if (!beffects) {
1392: node = expr.expr();
1393:
1394: if (replace) {
1395: node.setParent(null);
1396: expr.replaceWith(node, false);
1397: expr.bits().cleanup();
1398: expr.cleanupOnly();
1399: }
1400: }
1401: }
1402:
1403: return;
1404: }
1405:
1406: if (beffects) {
1407: return;
1408: }
1409:
1410: Object value = null;
1411:
1412: if (evalue instanceof Integer) {
1413: final int eval = ((Integer) evalue).intValue();
1414:
1415: if (eval == 0) {
1416: // 0 << x = 0
1417: // 0 >> x = 0
1418: // 0 >>> x = 0
1419: value = evalue;
1420:
1421: } else if (bvalue instanceof Integer) {
1422: if (replace && eeffects) {
1423: return;
1424: }
1425:
1426: final int bval = ((Integer) bvalue).intValue();
1427:
1428: switch (expr.dir()) {
1429: case ShiftExpr.LEFT:
1430: value = new Integer(eval << bval);
1431: break;
1432: case ShiftExpr.RIGHT:
1433: value = new Integer(eval >> bval);
1434: break;
1435: case ShiftExpr.UNSIGNED_RIGHT:
1436: value = new Integer(eval >>> bval);
1437: break;
1438: }
1439: }
1440:
1441: } else if (evalue instanceof Long) {
1442: final long eval = ((Long) evalue).longValue();
1443:
1444: if (eval == 0) {
1445: // 0 << x = 0
1446: // 0 >> x = 0
1447: // 0 >>> x = 0
1448: value = evalue;
1449:
1450: } else if (bvalue instanceof Integer) {
1451: if (replace && eeffects) {
1452: return;
1453: }
1454:
1455: final int bval = ((Integer) bvalue).intValue();
1456:
1457: switch (expr.dir()) {
1458: case ShiftExpr.LEFT:
1459: value = new Long(eval << bval);
1460: break;
1461: case ShiftExpr.RIGHT:
1462: value = new Long(eval >> bval);
1463: break;
1464: case ShiftExpr.UNSIGNED_RIGHT:
1465: value = new Long(eval >>> bval);
1466: break;
1467: }
1468: }
1469: }
1470:
1471: if (value != null) {
1472: node = new ConstantExpr(value, expr.type());
1473: node.setValueNumber(v);
1474:
1475: values.set(v, node);
1476:
1477: if (replace) {
1478: expr.replaceWith(node);
1479: }
1480: }
1481: }
1482:
1483: public void visitIfZeroStmt(final IfZeroStmt stmt) {
1484: // If the expression being compared to zero evaluates to a
1485: // constant, then try to exploit this fact.
1486:
1487: final Block block = stmt.block();
1488: final FlowGraph cfg = block.graph();
1489:
1490: final int v = stmt.valueNumber();
1491: final int ev = stmt.expr().valueNumber();
1492: values.ensureSize(Math.max(ev, v) + 1);
1493:
1494: ConstantExpr eexpr = null;
1495:
1496: if ((0 <= ev) && (ev < values.size())) {
1497: eexpr = (ConstantExpr) values.get(ev);
1498: }
1499:
1500: if (eexpr == null) {
1501: return;
1502: }
1503:
1504: final Object evalue = eexpr.value();
1505:
1506: boolean eeffects = false;
1507:
1508: if (replace) {
1509: sideEffects.reset();
1510: stmt.expr().visit(sideEffects);
1511: eeffects = sideEffects.hasSideEffects();
1512:
1513: if (eeffects) {
1514: return;
1515: }
1516: }
1517:
1518: JumpStmt jump;
1519:
1520: if (evalue instanceof Integer) {
1521: final int eval = ((Integer) evalue).intValue();
1522:
1523: boolean result;
1524:
1525: switch (stmt.comparison()) {
1526: case IfStmt.EQ:
1527: result = eval == 0;
1528: break;
1529: case IfStmt.NE:
1530: result = eval != 0;
1531: break;
1532: case IfStmt.GT:
1533: result = eval > 0;
1534: break;
1535: case IfStmt.GE:
1536: result = eval >= 0;
1537: break;
1538: case IfStmt.LT:
1539: result = eval < 0;
1540: break;
1541: case IfStmt.LE:
1542: result = eval <= 0;
1543: break;
1544: default:
1545: throw new RuntimeException();
1546: }
1547:
1548: if (result) {
1549: // Result is always true, replace IfZeroStmt with an
1550: // unconditional jump to the true target.
1551: jump = new GotoStmt(stmt.trueTarget());
1552: jump.catchTargets().addAll(stmt.catchTargets());
1553: node = jump;
1554: node.setValueNumber(v);
1555:
1556: if (replace) {
1557: stmt.replaceWith(node);
1558: cfg.removeEdge(block, stmt.falseTarget());
1559: }
1560:
1561: } else {
1562: // Result is always false, replace IfZeroStmt with an
1563: // unconditional jump to the false target.
1564: jump = new GotoStmt(stmt.falseTarget());
1565: jump.catchTargets().addAll(stmt.catchTargets());
1566: node = jump;
1567: node.setValueNumber(v);
1568:
1569: if (replace) {
1570: stmt.replaceWith(node);
1571: cfg.removeEdge(block, stmt.trueTarget());
1572: }
1573: }
1574:
1575: } else if (evalue == null) {
1576: // The expression always evaluates to null
1577:
1578: switch (stmt.comparison()) {
1579: case IfStmt.EQ:
1580: // Always jump to true target
1581: jump = new GotoStmt(stmt.trueTarget());
1582: jump.catchTargets().addAll(stmt.catchTargets());
1583: node = jump;
1584: node.setValueNumber(v);
1585:
1586: if (replace) {
1587: stmt.replaceWith(node);
1588: cfg.removeEdge(block, stmt.falseTarget());
1589: }
1590: break;
1591:
1592: case IfStmt.NE:
1593: // Always jump to false target
1594: jump = new GotoStmt(stmt.falseTarget());
1595: jump.catchTargets().addAll(stmt.catchTargets());
1596: node = jump;
1597: node.setValueNumber(v);
1598:
1599: if (replace) {
1600: stmt.replaceWith(node);
1601: cfg.removeEdge(block, stmt.trueTarget());
1602: }
1603: break;
1604: default:
1605: throw new RuntimeException();
1606: }
1607: }
1608: }
1609:
1610: public void visitIfCmpStmt(final IfCmpStmt stmt) {
1611: final Block block = stmt.block();
1612: final FlowGraph cfg = block.graph();
1613:
1614: final int v = stmt.valueNumber();
1615: final int lv = stmt.left().valueNumber();
1616: final int rv = stmt.right().valueNumber();
1617:
1618: int max = v;
1619: max = Math.max(max, lv);
1620: max = Math.max(max, rv);
1621: values.ensureSize(max + 1);
1622:
1623: ConstantExpr lexpr = null;
1624: ConstantExpr rexpr = null;
1625:
1626: if ((0 <= lv) && (lv < values.size())) {
1627: lexpr = (ConstantExpr) values.get(lv);
1628: }
1629:
1630: if ((0 <= rv) && (rv < values.size())) {
1631: rexpr = (ConstantExpr) values.get(rv);
1632: }
1633:
1634: Object lvalue = null;
1635: Object rvalue = null;
1636:
1637: if (lexpr != null) {
1638: lvalue = lexpr.value();
1639: }
1640:
1641: if (rexpr != null) {
1642: rvalue = rexpr.value();
1643: }
1644:
1645: boolean leffects = false;
1646: boolean reffects = false;
1647:
1648: if (replace) {
1649: sideEffects.reset();
1650: stmt.left().visit(sideEffects);
1651: leffects = sideEffects.hasSideEffects();
1652:
1653: sideEffects.reset();
1654: stmt.right().visit(sideEffects);
1655: reffects = sideEffects.hasSideEffects();
1656: }
1657:
1658: if ((lvalue instanceof Integer) && !leffects) {
1659: final int lval = ((Integer) lvalue).intValue();
1660:
1661: if ((lval == 0)
1662: && !((rvalue instanceof Integer) || reffects)) {
1663: // If two integers are being compared and the left operand is
1664: // zero, then we can replace the IfCmpStmt with a IfZeroStmt.
1665:
1666: int cmp;
1667:
1668: switch (stmt.comparison()) {
1669: case IfStmt.EQ:
1670: cmp = IfStmt.EQ;
1671: break;
1672: case IfStmt.NE:
1673: cmp = IfStmt.NE;
1674: break;
1675: case IfStmt.LT:
1676: cmp = IfStmt.GT;
1677: break;
1678: case IfStmt.LE:
1679: cmp = IfStmt.GE;
1680: break;
1681: case IfStmt.GT:
1682: cmp = IfStmt.LT;
1683: break;
1684: case IfStmt.GE:
1685: cmp = IfStmt.LE;
1686: break;
1687: default:
1688: throw new RuntimeException();
1689: }
1690:
1691: if (replace) {
1692: final JumpStmt jump = new IfZeroStmt(cmp,
1693: (Expr) stmt.right().clone(), stmt
1694: .trueTarget(), stmt.falseTarget());
1695: jump.catchTargets().addAll(stmt.catchTargets());
1696: node = jump;
1697: node.setValueNumber(v);
1698: stmt.replaceWith(node);
1699:
1700: } else {
1701: // Why bother! -- Nate
1702: // Why ask why! -- Dave
1703: node = null;
1704: }
1705:
1706: return;
1707: }
1708: }
1709:
1710: if ((rvalue instanceof Integer) && !reffects) {
1711: final int rval = ((Integer) rvalue).intValue();
1712:
1713: if ((rval == 0)
1714: && !((lvalue instanceof Integer) || leffects)) {
1715: // If IfCmpStmt compares two integers and the right operand is
1716: // zero, then replace the IfCmpStmt with an IfZeroStmt.
1717: final int cmp = stmt.comparison();
1718:
1719: if (replace) {
1720: final JumpStmt jump = new IfZeroStmt(cmp,
1721: (Expr) stmt.left().clone(), stmt
1722: .trueTarget(), stmt.falseTarget());
1723: jump.catchTargets().addAll(stmt.catchTargets());
1724: node = jump;
1725: node.setValueNumber(v);
1726: stmt.replaceWith(node);
1727:
1728: } else {
1729: // Why bother! -- Cut and paste! Way to go Nate!
1730: node = null;
1731: }
1732:
1733: return;
1734: }
1735: }
1736:
1737: if ((lexpr != null) && (lvalue == null) && !leffects) {
1738: if ((rexpr == null) || (rvalue != null) || reffects) {
1739: // Left operand evaluates to null. Replace IfCmpStmt with an
1740: // IfZeroStmt.
1741: final int cmp = stmt.comparison();
1742:
1743: if (replace) {
1744: final JumpStmt jump = new IfZeroStmt(cmp,
1745: (Expr) stmt.right().clone(), stmt
1746: .trueTarget(), stmt.falseTarget());
1747: jump.catchTargets().addAll(stmt.catchTargets());
1748: node = jump;
1749: node.setValueNumber(v);
1750: stmt.replaceWith(node);
1751:
1752: } else {
1753: // Why bother!
1754: node = null;
1755: }
1756:
1757: return;
1758: }
1759: }
1760:
1761: if ((rexpr != null) && (rvalue == null) && !reffects) {
1762: if ((lexpr == null) || (lvalue != null) || leffects) {
1763: // The right operand evaluates to null. Replace IfCmpStmt
1764: // with an IfZeroStmt. Note that we do not need to mess with
1765: // operators because if the lhs is being compared against
1766: // null, it must be a reference type and the only operators
1767: // are EQ and NE.
1768:
1769: final int cmp = stmt.comparison();
1770:
1771: if (replace) {
1772: final JumpStmt jump = new IfZeroStmt(cmp,
1773: (Expr) stmt.left().clone(), stmt
1774: .trueTarget(), stmt.falseTarget());
1775: jump.catchTargets().addAll(stmt.catchTargets());
1776: node = jump;
1777: node.setValueNumber(v);
1778: stmt.replaceWith(node);
1779:
1780: } else {
1781: // Why bother!
1782: node = null;
1783: }
1784:
1785: return;
1786: }
1787: }
1788:
1789: if (leffects || reffects) {
1790: return;
1791: }
1792:
1793: if ((lexpr == null) || (rexpr == null)) {
1794: return;
1795: }
1796:
1797: JumpStmt jump;
1798:
1799: if ((lvalue instanceof Integer) && (rvalue instanceof Integer)) {
1800: // Both operands evaluate to non-zero integers, evaluate the
1801: // comparison and go from there.
1802:
1803: final int lval = ((Integer) lvalue).intValue();
1804: final int rval = ((Integer) rvalue).intValue();
1805:
1806: boolean result;
1807:
1808: switch (stmt.comparison()) {
1809: case IfStmt.EQ:
1810: result = lval == rval;
1811: break;
1812: case IfStmt.NE:
1813: result = lval != rval;
1814: break;
1815: case IfStmt.GT:
1816: result = lval > rval;
1817: break;
1818: case IfStmt.GE:
1819: result = lval >= rval;
1820: break;
1821: case IfStmt.LT:
1822: result = lval < rval;
1823: break;
1824: case IfStmt.LE:
1825: result = lval <= rval;
1826: break;
1827: default:
1828: throw new RuntimeException();
1829: }
1830:
1831: if (result) {
1832: jump = new GotoStmt(stmt.trueTarget());
1833: jump.catchTargets().addAll(stmt.catchTargets());
1834: node = jump;
1835: node.setValueNumber(v);
1836:
1837: if (replace) {
1838: stmt.replaceWith(node);
1839: cfg.removeEdge(block, stmt.falseTarget());
1840: }
1841:
1842: } else {
1843: jump = new GotoStmt(stmt.falseTarget());
1844: jump.catchTargets().addAll(stmt.catchTargets());
1845: node = jump;
1846: node.setValueNumber(v);
1847:
1848: if (replace) {
1849: stmt.replaceWith(node);
1850: cfg.removeEdge(block, stmt.trueTarget());
1851: }
1852: }
1853:
1854: } else if ((lvalue == null) && (rvalue == null)) {
1855: switch (stmt.comparison()) {
1856: case IfStmt.EQ:
1857: jump = new GotoStmt(stmt.trueTarget());
1858: jump.catchTargets().addAll(stmt.catchTargets());
1859: node = jump;
1860: node.setValueNumber(v);
1861:
1862: if (replace) {
1863: stmt.replaceWith(node);
1864: cfg.removeEdge(block, stmt.falseTarget());
1865: }
1866: break;
1867: case IfStmt.NE:
1868: jump = new GotoStmt(stmt.falseTarget());
1869: jump.catchTargets().addAll(stmt.catchTargets());
1870: node = jump;
1871: node.setValueNumber(v);
1872:
1873: if (replace) {
1874: stmt.replaceWith(node);
1875: cfg.removeEdge(block, stmt.trueTarget());
1876: }
1877: break;
1878: default:
1879: throw new RuntimeException();
1880: }
1881: }
1882: }
1883:
1884: public void visitSwitchStmt(final SwitchStmt stmt) {
1885: // If the index of the SwitchStmt evaluates to a constant value,
1886: // then always take that target (may be the default target).
1887: // Replace the SwitchStmt with a GotoStmt.
1888: final Block block = stmt.block();
1889: final FlowGraph cfg = block.graph();
1890:
1891: final int v = stmt.valueNumber();
1892: final int iv = stmt.index().valueNumber();
1893: values.ensureSize(Math.max(v, iv) + 1);
1894:
1895: ConstantExpr iexpr = null;
1896:
1897: if ((0 <= iv) && (iv < values.size())) {
1898: iexpr = (ConstantExpr) values.get(iv);
1899: }
1900:
1901: boolean ieffects = false;
1902:
1903: if (replace) {
1904: sideEffects.reset();
1905: stmt.index().visit(sideEffects);
1906: ieffects = sideEffects.hasSideEffects();
1907:
1908: if (ieffects) {
1909: return;
1910: }
1911: }
1912:
1913: if (iexpr == null) {
1914: return;
1915: }
1916:
1917: if (!(iexpr.value() instanceof Integer)) {
1918: return;
1919: }
1920:
1921: JumpStmt jump;
1922:
1923: final Integer ivalue = (Integer) iexpr.value();
1924:
1925: final int ival = ivalue.intValue();
1926:
1927: boolean useDefault = true;
1928:
1929: for (int i = 0; i < stmt.values().length; i++) {
1930: if (stmt.values()[i] == ival) {
1931: jump = new GotoStmt(stmt.targets()[i]);
1932: jump.catchTargets().addAll(stmt.catchTargets());
1933: node = jump;
1934: node.setValueNumber(v);
1935:
1936: if (replace) {
1937: stmt.replaceWith(node);
1938: }
1939: useDefault = false;
1940:
1941: } else {
1942: // Definitely not to this target.
1943: if (replace) {
1944: cfg.removeEdge(block, stmt.targets()[i]);
1945: }
1946: }
1947: }
1948:
1949: if (useDefault) {
1950: jump = new GotoStmt(stmt.defaultTarget());
1951: jump.catchTargets().addAll(stmt.catchTargets());
1952: node = jump;
1953: node.setValueNumber(v);
1954:
1955: if (replace) {
1956: stmt.replaceWith(node);
1957: }
1958: } else {
1959: // Definitely not to the default target.
1960: if (replace) {
1961: cfg.removeEdge(block, stmt.defaultTarget());
1962: }
1963: }
1964: }
1965:
1966: void printValueNumbers(final PrintWriter pw) {
1967: if (pw == null) {
1968: return;
1969: }
1970:
1971: final Iterator iter = values.iterator();
1972:
1973: pw.println("Value Numbers mapped to constants\n");
1974:
1975: for (int i = 0; iter.hasNext(); i++) {
1976: final Object o = iter.next();
1977: if (o != null) {
1978: pw.println(i + " -> " + o);
1979: }
1980: }
1981: }
1982: }
|