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.util.*;
0024:
0025: import EDU.purdue.cs.bloat.cfg.*;
0026: import EDU.purdue.cs.bloat.editor.*;
0027: import EDU.purdue.cs.bloat.ssa.*;
0028: import EDU.purdue.cs.bloat.tree.*;
0029: import EDU.purdue.cs.bloat.util.*;
0030:
0031: /**
0032: * Eliminate partially redundant local variable loads and stores by replacing
0033: * them with stack variables and dups.
0034: *
0035: * The algorithm is similar to SSAPRE, except:
0036: *
0037: * We need to place phis for locals at the IDF of the blocks containing defs and
0038: * uses (not just defs).
0039: */
0040: public class StackPRE {
0041: public static boolean DEBUG = false;
0042:
0043: protected FlowGraph cfg;
0044:
0045: protected List[] varphis;
0046:
0047: protected List[] stackvars;
0048:
0049: protected Worklist worklist;
0050:
0051: int next = 0;
0052:
0053: public StackPRE(final FlowGraph cfg) {
0054: this .cfg = cfg;
0055: }
0056:
0057: public void transform() {
0058: stackvars = new ArrayList[cfg.size()];
0059:
0060: for (int i = 0; i < stackvars.length; i++) {
0061: stackvars[i] = new ArrayList();
0062: }
0063:
0064: varphis = new ArrayList[cfg.size()];
0065:
0066: for (int i = 0; i < varphis.length; i++) {
0067: varphis[i] = new ArrayList();
0068: }
0069:
0070: // Collect local and stack variables into a worklist.
0071: // Mark the variables that are pushed before any are popped.
0072: worklist = new Worklist();
0073:
0074: cfg.visit(new TreeVisitor() {
0075: public void visitPhiJoinStmt(final PhiJoinStmt stmt) {
0076: worklist.addVarPhi(stmt);
0077: }
0078:
0079: public void visitPhiCatchStmt(final PhiCatchStmt stmt) {
0080: worklist.addLocalVar((LocalExpr) stmt.target());
0081: }
0082:
0083: public void visitLocalExpr(final LocalExpr expr) {
0084: worklist.addLocalVar(expr);
0085: }
0086:
0087: public void visitStackExpr(final StackExpr expr) {
0088: worklist.addStackVar(expr);
0089: }
0090: });
0091:
0092: while (!worklist.isEmpty()) {
0093: final ExprInfo exprInfo = worklist.removeFirst();
0094:
0095: if (StackPRE.DEBUG) {
0096: System.out.println("PRE for " + exprInfo.def()
0097: + " -------------------------");
0098: System.out.println("Placing Phis for " + exprInfo.def()
0099: + " -------------------------");
0100: }
0101:
0102: placePhiFunctions(exprInfo);
0103:
0104: if (StackPRE.DEBUG) {
0105: exprInfo.print();
0106: System.out.println("Renaming for " + exprInfo.def()
0107: + " -------------------------");
0108: }
0109:
0110: rename(exprInfo);
0111:
0112: if (StackPRE.DEBUG) {
0113: exprInfo.print();
0114: System.out.println("Down safety for " + exprInfo.def()
0115: + " -------------------------");
0116: }
0117:
0118: downSafety(exprInfo);
0119:
0120: if (StackPRE.DEBUG) {
0121: System.out
0122: .println("Will be available for "
0123: + exprInfo.def()
0124: + " -------------------------");
0125: }
0126:
0127: willBeAvail(exprInfo);
0128:
0129: if (StackPRE.DEBUG) {
0130: System.out.println("Finalize for " + exprInfo.def()
0131: + " -------------------------");
0132: }
0133:
0134: finalize(exprInfo);
0135:
0136: if (StackPRE.DEBUG) {
0137: System.out.println("Code motion for " + exprInfo.def()
0138: + " -------------------------");
0139: }
0140:
0141: final Type type = exprInfo.def().type();
0142: final StackExpr tmp = new StackExpr(0, type);
0143: final SSAConstructionInfo consInfo = new SSAConstructionInfo(
0144: cfg, tmp);
0145:
0146: codeMotion(exprInfo, tmp, consInfo);
0147:
0148: if (StackPRE.DEBUG) {
0149: System.out
0150: .println("Performing incremental SSA for "
0151: + exprInfo.def()
0152: + " -------------------------");
0153: }
0154:
0155: SSA.transform(cfg, consInfo);
0156:
0157: // Get the stack variable phis.
0158: final Collection defBlocks = consInfo.defBlocks();
0159: final Iterator e = cfg.iteratedDomFrontier(defBlocks)
0160: .iterator();
0161:
0162: while (e.hasNext()) {
0163: final Block block = (Block) e.next();
0164:
0165: final Iterator stmts = block.tree().stmts().iterator();
0166:
0167: while (stmts.hasNext()) {
0168: final Stmt stmt = (Stmt) stmts.next();
0169: if (stmt instanceof PhiJoinStmt) {
0170: worklist.prependVarPhi((PhiJoinStmt) stmt);
0171: } else if (!(stmt instanceof LabelStmt)) {
0172: // Only labels occur before phis. If we hit
0173: // something else, there are no more phis.
0174: break;
0175: }
0176: }
0177: }
0178:
0179: if (StackPRE.DEBUG) {
0180: exprInfo.print();
0181: System.out
0182: .println("Done with PRE for " + exprInfo.def()
0183: + " -------------------------");
0184: }
0185:
0186: exprInfo.cleanup();
0187: }
0188:
0189: varphis = null;
0190: worklist = null;
0191: }
0192:
0193: /**
0194: * For an local variable, v, insert a Phi at the iterated dominance frontier
0195: * of the blocks containing defs and uses of v. This differs from SSA phi
0196: * placement in that uses, not just defs are considered in computing the
0197: * IDF.
0198: */
0199: private void placePhiFunctions(final ExprInfo exprInfo) {
0200: final ArrayList w = new ArrayList(cfg.size());
0201:
0202: final Iterator uses = exprInfo.def().uses().iterator();
0203:
0204: w.add(exprInfo.def().block());
0205:
0206: while (uses.hasNext()) {
0207: final LocalExpr use = (LocalExpr) uses.next();
0208:
0209: if (use.parent() instanceof PhiJoinStmt) {
0210: final PhiJoinStmt phi = (PhiJoinStmt) use.parent();
0211:
0212: final Iterator preds = cfg.preds(use.block())
0213: .iterator();
0214:
0215: while (preds.hasNext()) {
0216: final Block pred = (Block) preds.next();
0217:
0218: if (phi.operandAt(pred) == use) {
0219: w.add(pred);
0220: break;
0221: }
0222: }
0223: } else if (!(use.parent() instanceof PhiCatchStmt)) {
0224: w.add(use.block());
0225: }
0226: }
0227:
0228: final Iterator df = cfg.iteratedDomFrontier(w).iterator();
0229:
0230: while (df.hasNext()) {
0231: final Block block = (Block) df.next();
0232: exprInfo.addPhi(block);
0233: }
0234:
0235: // Don't bother with placing phis for catch blocks, since the
0236: // operand stack is zeroed at catch blocks.
0237: }
0238:
0239: /**
0240: * Set the definition for the variable occurences. After this step all
0241: * occurences of the variable which are at different heights will have
0242: * different definitions.
0243: */
0244: private void rename(final ExprInfo exprInfo) {
0245: search(cfg.source(), exprInfo, null, 0, false);
0246: }
0247:
0248: private void search(final Block block, final ExprInfo exprInfo,
0249: Def top, int totalBalance, boolean seenDef) {
0250: if (StackPRE.DEBUG) {
0251: System.out.println(" renaming in " + block);
0252: }
0253:
0254: if (cfg.catchBlocks().contains(block)) {
0255: if (top != null) {
0256: top.setDownSafe(false);
0257: }
0258:
0259: top = null;
0260: }
0261:
0262: final Phi phi = exprInfo.exprPhiAtBlock(block);
0263:
0264: if (phi != null) {
0265: if (top != null) {
0266: top.setDownSafe(false);
0267: }
0268:
0269: top = phi;
0270:
0271: if (!seenDef) {
0272: top.setDownSafe(false);
0273: }
0274: }
0275:
0276: Node parent = null;
0277: int balance = 0;
0278:
0279: final Iterator iter = exprInfo.varsAtBlock(block).iterator();
0280:
0281: while (iter.hasNext()) {
0282: final VarExpr node = (VarExpr) iter.next();
0283:
0284: // Get the parent of the node. If the parent is a putfield
0285: // or array store, then the node is popped when the grandparent
0286: // is evaluated, not when the parent is evaluated.
0287: // We keep track of the parent so that when it changes, we
0288: // know to update the operand stack balance.
0289:
0290: Node p = node.parent();
0291:
0292: if ((p instanceof MemRefExpr) && ((MemRefExpr) p).isDef()) {
0293: p = p.parent();
0294: }
0295:
0296: if (parent != p) {
0297: parent = p;
0298: totalBalance += balance;
0299: balance = 0;
0300:
0301: if ((top != null) && (totalBalance < 0)) {
0302: top.setDownSafe(false);
0303: }
0304: }
0305:
0306: if (node instanceof StackExpr) {
0307: if (parent instanceof StackManipStmt) {
0308: switch (((StackManipStmt) parent).kind()) {
0309: case StackManipStmt.DUP:
0310: case StackManipStmt.DUP_X1:
0311: case StackManipStmt.DUP_X2:
0312: balance += 1;
0313: break;
0314: case StackManipStmt.DUP2:
0315: case StackManipStmt.DUP2_X1:
0316: case StackManipStmt.DUP2_X2:
0317: balance += 2;
0318: break;
0319: default:
0320: break;
0321: }
0322: } else if (node.isDef()) {
0323: balance += node.type().stackHeight();
0324: } else {
0325: balance -= node.type().stackHeight();
0326: }
0327: } else {
0328: final LocalExpr var = (LocalExpr) node;
0329:
0330: if (var.isDef()) {
0331: seenDef = true;
0332: }
0333:
0334: if (StackPRE.DEBUG) {
0335: System.out.println("node = " + var + " in "
0336: + parent);
0337: }
0338:
0339: if ((totalBalance == 0) && onBottom(var, false)) {
0340: // Copy the def from the top of the stack and
0341: // create a new def.
0342: exprInfo.setDef(var, top);
0343: top = new RealDef(var);
0344:
0345: if ((balance != 0) || !onBottom(var, true)) {
0346: top.setDownSafe(false);
0347: }
0348:
0349: if (StackPRE.DEBUG) {
0350: System.out.println("New def " + top
0351: + " with balance " + totalBalance
0352: + " + " + balance);
0353: }
0354: } else {
0355: // The occurence is not on the bottom, so it
0356: // must be reloaded from a local.
0357: exprInfo.setDef(var, null);
0358: }
0359: }
0360:
0361: if (StackPRE.DEBUG) {
0362: System.out.println("after " + parent + " top = " + top);
0363: }
0364: }
0365:
0366: totalBalance += balance;
0367:
0368: if ((top != null) && (totalBalance < 0)) {
0369: top.setDownSafe(false);
0370: }
0371:
0372: // If we hit the sink node, a def at the top of the stack is not
0373: // down safe.
0374: if ((block == cfg.sink())
0375: || cfg.succs(block).contains(cfg.sink())) {
0376: if (top != null) {
0377: top.setDownSafe(false);
0378: }
0379: }
0380:
0381: // First, fill in the operands for the StackPRE phis. Then,
0382: // handle local variable occurences in successor block variable
0383: // phis. We do this after the StackPRE phis since they will
0384: // hoist code above the variable phis.
0385:
0386: Iterator succs = cfg.succs(block).iterator();
0387:
0388: while (succs.hasNext()) {
0389: final Block succ = (Block) succs.next();
0390:
0391: final Phi succPhi = exprInfo.exprPhiAtBlock(succ);
0392:
0393: if (succPhi != null) {
0394: succPhi.setOperandAt(block, top);
0395: }
0396: }
0397:
0398: succs = cfg.succs(block).iterator();
0399:
0400: while (succs.hasNext()) {
0401: final Block succ = (Block) succs.next();
0402:
0403: final Iterator phis = varPhisAtBlock(succ).iterator();
0404:
0405: while (phis.hasNext()) {
0406: final PhiJoinStmt stmt = (PhiJoinStmt) phis.next();
0407:
0408: final Expr operand = stmt.operandAt(block);
0409:
0410: if (operand instanceof StackExpr) {
0411: balance += operand.type().stackHeight();
0412: }
0413:
0414: if (stmt.target() instanceof StackExpr) {
0415: balance -= stmt.target().type().stackHeight();
0416:
0417: if (top != null) {
0418: top.setDownSafe(false);
0419: top = null;
0420: }
0421: }
0422:
0423: if ((operand != null)
0424: && (operand.def() == exprInfo.def())) {
0425: // Phi operands aren't allowed to define any of the
0426: // locals. This should never happen since none of the
0427: // locals should be dominated by the phi operand,
0428: // but we'll play it safe and set top to null.
0429: exprInfo.setDef((LocalExpr) operand, top);
0430: top = null;
0431: }
0432:
0433: if (stmt.target() == exprInfo.def()) {
0434: exprInfo.setDef((LocalExpr) stmt.target(), top);
0435: top = new RealDef((LocalExpr) stmt.target());
0436: }
0437:
0438: totalBalance += balance;
0439:
0440: if ((top != null) && (totalBalance < 0)) {
0441: top.setDownSafe(false);
0442: }
0443: }
0444: }
0445:
0446: final Iterator children = cfg.domChildren(block).iterator();
0447:
0448: while (children.hasNext()) {
0449: final Block child = (Block) children.next();
0450: search(child, exprInfo, top, totalBalance, seenDef);
0451: }
0452: }
0453:
0454: private boolean onBottom(final LocalExpr var, final boolean really) {
0455: // InitStmts and PhiStmts are always on the bottom.
0456: if ((var.stmt() instanceof InitStmt)
0457: || (var.stmt() instanceof PhiStmt)) {
0458: return true;
0459: }
0460:
0461: class Bool {
0462: boolean value = true;
0463: }
0464: ;
0465:
0466: final Bool bottom = new Bool();
0467:
0468: var.stmt().visitChildren(new TreeVisitor() {
0469: boolean seen = false;
0470:
0471: public void visitExpr(final Expr expr) {
0472: if (StackPRE.DEBUG) {
0473: System.out.println("Checking " + expr + " seen="
0474: + seen + " bottom=" + bottom.value);
0475: }
0476:
0477: if (!seen) {
0478: expr.visitChildren(this );
0479: }
0480:
0481: if (!seen) {
0482: bottom.value = false;
0483: seen = true;
0484: }
0485:
0486: if (StackPRE.DEBUG) {
0487: System.out.println("Done with " + expr + " seen="
0488: + seen + " bottom=" + bottom.value);
0489: }
0490: }
0491:
0492: public void visitLocalExpr(final LocalExpr expr) {
0493: if (StackPRE.DEBUG) {
0494: System.out.println("Checking " + expr + " seen="
0495: + seen + " bottom=" + bottom.value);
0496: }
0497:
0498: if (!seen) {
0499: if (expr == var) {
0500: seen = true;
0501: } else if (expr.def() != var.def()) {
0502: bottom.value = false;
0503: seen = true;
0504: }
0505: }
0506:
0507: if (StackPRE.DEBUG) {
0508: System.out.println("Done with " + expr + " seen="
0509: + seen + " bottom=" + bottom.value);
0510: }
0511: }
0512:
0513: public void visitStackExpr(final StackExpr expr) {
0514: if (StackPRE.DEBUG) {
0515: System.out.println("Checking " + expr + " seen="
0516: + seen + " bottom=" + bottom.value);
0517: }
0518:
0519: if (really && !seen) {
0520: bottom.value = false;
0521: seen = true;
0522: }
0523:
0524: if (StackPRE.DEBUG) {
0525: System.out.println("Done with " + expr + " seen="
0526: + seen + " bottom=" + bottom.value);
0527: }
0528: }
0529: });
0530:
0531: return bottom.value;
0532: }
0533:
0534: /**
0535: * Mark each def as not down safe if there is a control flow path from that
0536: * Phi along which the expression is not evaluated before exit or being
0537: * altered by refinition of one of the variables of the expression. This can
0538: * happen if:
0539: *
0540: * 1) There is a path to exit along which the Phi target is not used. 2)
0541: * There is a path to exit along which the Phi target is used only as the
0542: * operand of a non-down-safe Phi.
0543: */
0544: private void downSafety(final ExprInfo exprInfo) {
0545: final Iterator blocks = cfg.nodes().iterator();
0546:
0547: while (blocks.hasNext()) {
0548: final Block block = (Block) blocks.next();
0549:
0550: final Phi phi = exprInfo.exprPhiAtBlock(block);
0551:
0552: if (phi == null) {
0553: continue;
0554: }
0555:
0556: if (StackPRE.DEBUG) {
0557: System.out.println(" down safety for " + phi
0558: + " in " + block);
0559: }
0560:
0561: if (phi.downSafe()) {
0562: if (StackPRE.DEBUG) {
0563: System.out.println(" already down safe");
0564: }
0565:
0566: continue;
0567: }
0568:
0569: // The phi is not down safe. Make all its operands not
0570: // down safe.
0571:
0572: final Iterator e = phi.operands().iterator();
0573:
0574: while (e.hasNext()) {
0575: final Def def = (Def) e.next();
0576:
0577: if (def != null) {
0578: resetDownSafe(def);
0579: }
0580: }
0581: }
0582: }
0583:
0584: private void resetDownSafe(final Def def) {
0585: if (StackPRE.DEBUG) {
0586: System.out.println(" reset down safe for " + def);
0587: }
0588:
0589: if (def instanceof Phi) {
0590: final Phi phi = (Phi) def;
0591:
0592: if (phi.downSafe()) {
0593: phi.setDownSafe(false);
0594:
0595: final Iterator e = phi.operands().iterator();
0596:
0597: while (e.hasNext()) {
0598: final Def operand = (Def) e.next();
0599:
0600: if (operand != null) {
0601: resetDownSafe(operand);
0602: }
0603: }
0604: }
0605: } else {
0606: def.setDownSafe(false);
0607: }
0608: }
0609:
0610: /**
0611: * Predict whether the expression will be available at each Phi result
0612: * following insertions for PRE.
0613: */
0614: private void willBeAvail(final ExprInfo exprInfo) {
0615: computeCanBeAvail(exprInfo);
0616: computeLater(exprInfo);
0617: }
0618:
0619: private void computeCanBeAvail(final ExprInfo exprInfo) {
0620: final Iterator blocks = cfg.nodes().iterator();
0621:
0622: while (blocks.hasNext()) {
0623: final Block block = (Block) blocks.next();
0624:
0625: final Phi phi = exprInfo.exprPhiAtBlock(block);
0626:
0627: if (phi == null) {
0628: continue;
0629: }
0630:
0631: if (!phi.downSafe() && phi.canBeAvail()) {
0632: resetCanBeAvail(exprInfo, phi);
0633: }
0634: }
0635: }
0636:
0637: private void resetCanBeAvail(final ExprInfo exprInfo, final Phi phi) {
0638: phi.setCanBeAvail(false);
0639:
0640: final Iterator blocks = cfg.nodes().iterator();
0641:
0642: // For each phi whose operand is at
0643: while (blocks.hasNext()) {
0644: final Block block = (Block) blocks.next();
0645:
0646: final Phi other = exprInfo.exprPhiAtBlock(block);
0647:
0648: if (other == null) {
0649: continue;
0650: }
0651:
0652: final Iterator e = cfg.preds(other.block()).iterator();
0653:
0654: while (e.hasNext()) {
0655: final Block pred = (Block) e.next();
0656:
0657: final Def def = other.operandAt(pred);
0658:
0659: if (def == phi) {
0660: other.setOperandAt(pred, null);
0661:
0662: if (!other.downSafe() && other.canBeAvail()) {
0663: resetCanBeAvail(exprInfo, other);
0664: }
0665: }
0666: }
0667: }
0668: }
0669:
0670: private void computeLater(final ExprInfo exprInfo) {
0671: Iterator blocks = cfg.nodes().iterator();
0672:
0673: while (blocks.hasNext()) {
0674: final Block block = (Block) blocks.next();
0675:
0676: final Phi phi = exprInfo.exprPhiAtBlock(block);
0677:
0678: if (phi != null) {
0679: phi.setLater(phi.canBeAvail());
0680: }
0681: }
0682:
0683: blocks = cfg.nodes().iterator();
0684:
0685: while (blocks.hasNext()) {
0686: final Block block = (Block) blocks.next();
0687:
0688: final Phi phi = exprInfo.exprPhiAtBlock(block);
0689:
0690: if ((phi != null) && phi.later()) {
0691: final Iterator e = phi.operands().iterator();
0692:
0693: while (e.hasNext()) {
0694: final Def def = (Def) e.next();
0695:
0696: if (def instanceof RealDef) {
0697: resetLater(exprInfo, phi);
0698: break;
0699: }
0700: }
0701: }
0702: }
0703: }
0704:
0705: private void resetLater(final ExprInfo exprInfo, final Phi phi) {
0706: phi.setLater(false);
0707:
0708: final Iterator blocks = cfg.nodes().iterator();
0709:
0710: while (blocks.hasNext()) {
0711: final Block block = (Block) blocks.next();
0712:
0713: final Phi other = exprInfo.exprPhiAtBlock(block);
0714:
0715: if (other == null) {
0716: continue;
0717: }
0718:
0719: final Iterator e = other.operands().iterator();
0720:
0721: while (e.hasNext()) {
0722: final Def def = (Def) e.next();
0723:
0724: if ((def == phi) && other.later()) {
0725: resetLater(exprInfo, other);
0726: break;
0727: }
0728: }
0729: }
0730: }
0731:
0732: private void finalize(final ExprInfo exprInfo) {
0733: final Iterator uses = exprInfo.def().uses().iterator();
0734:
0735: while (uses.hasNext()) {
0736: final LocalExpr use = (LocalExpr) uses.next();
0737:
0738: if (use.parent() instanceof PhiCatchStmt) {
0739: exprInfo.setSave(true);
0740: break;
0741: }
0742: }
0743:
0744: finalizeVisit(exprInfo, cfg.source());
0745: }
0746:
0747: private void finalizeVisit(final ExprInfo exprInfo,
0748: final Block block) {
0749: if (StackPRE.DEBUG) {
0750: System.out.println(" finalizing " + block);
0751: }
0752:
0753: // First finalize normal occurences of the local.
0754: final Iterator reals = exprInfo.varsAtBlock(block).iterator();
0755:
0756: while (reals.hasNext()) {
0757: final VarExpr node = (VarExpr) reals.next();
0758:
0759: if (node instanceof LocalExpr) {
0760: final LocalExpr real = (LocalExpr) node;
0761:
0762: if (StackPRE.DEBUG) {
0763: System.out.println(" -----------");
0764: }
0765:
0766: final Def def = exprInfo.def(real);
0767:
0768: if ((def != null) && def.downSafe()) {
0769: // We can reload from a stack variable, unless the we
0770: // can't safely push the phi operands.
0771: if (def instanceof Phi) {
0772: if (((Phi) def).willBeAvail()) {
0773: exprInfo.setPop(real, true);
0774: } else {
0775: exprInfo.setSave(true);
0776: }
0777: } else {
0778: exprInfo.setPush(((RealDef) def).var, true);
0779: exprInfo.setPop(real, true);
0780: }
0781: } else {
0782: // The real is not on the bottom. We must reload from a
0783: // local variable.
0784: if (real != exprInfo.def()) {
0785: exprInfo.setSave(true);
0786: }
0787: }
0788: }
0789: }
0790:
0791: // Next, handle code motion.
0792: Iterator succs = cfg.succs(block).iterator();
0793:
0794: while (succs.hasNext()) {
0795: final Block succ = (Block) succs.next();
0796:
0797: final Phi succPhi = exprInfo.exprPhiAtBlock(succ);
0798:
0799: if ((succPhi != null) && succPhi.willBeAvail()) {
0800: if (succPhi.insert(block)) {
0801: succPhi.setPushOperand(block, true);
0802: } else {
0803: final Def def = succPhi.operandAt(block);
0804:
0805: if (def instanceof RealDef) {
0806: Assert.isTrue(def.downSafe(), succPhi
0807: + " operand for " + block
0808: + " is not DS: " + def);
0809: exprInfo.setPush(((RealDef) def).var, true);
0810: } else {
0811: Assert.isTrue(def instanceof Phi, succPhi
0812: + " operand for " + block
0813: + " is not a phi: " + def);
0814: Assert.isTrue(((Phi) def).willBeAvail(),
0815: succPhi + " operand for " + block
0816: + " is not WBA: " + def);
0817: }
0818: }
0819: }
0820: }
0821:
0822: // Lastly, finalize occurences in variable phis. We do this
0823: // after the StackPRE hoisting since the hoisted code will
0824: // occur before the phis.
0825: succs = cfg.succs(block).iterator();
0826:
0827: while (succs.hasNext()) {
0828: final Block succ = (Block) succs.next();
0829:
0830: final Iterator phis = varPhisAtBlock(succ).iterator();
0831:
0832: while (phis.hasNext()) {
0833: final PhiJoinStmt stmt = (PhiJoinStmt) phis.next();
0834:
0835: final Expr operand = stmt.operandAt(block);
0836:
0837: if ((operand != null)
0838: && (operand.def() == exprInfo.def())) {
0839: final LocalExpr var = (LocalExpr) operand;
0840: final Def def = exprInfo.def(var);
0841:
0842: if ((def != null) && def.downSafe()) {
0843: // We can reload from a stack variable, unless the we
0844: // can't safely push the phi operands.
0845: if (def instanceof Phi) {
0846: if (((Phi) def).willBeAvail()) {
0847: exprInfo.setPop(var, true);
0848: } else {
0849: exprInfo.setSave(true);
0850: }
0851: } else {
0852: exprInfo.setPush(((RealDef) def).var, true);
0853: exprInfo.setPop(var, true);
0854: }
0855: }
0856: }
0857: }
0858: }
0859:
0860: final Iterator children = cfg.domChildren(block).iterator();
0861:
0862: while (children.hasNext()) {
0863: final Block child = (Block) children.next();
0864: finalizeVisit(exprInfo, child);
0865: }
0866: }
0867:
0868: private void codeMotion(final ExprInfo exprInfo,
0869: final StackExpr tmp, final SSAConstructionInfo consInfo) {
0870: // Be sure to visit pre-order so at least one predecessor is visited
0871: // before each block.
0872: final Iterator blocks = cfg.preOrder().iterator();
0873:
0874: while (blocks.hasNext()) {
0875: final Block block = (Block) blocks.next();
0876:
0877: if ((block == cfg.source()) || (block == cfg.sink())) {
0878: continue;
0879: }
0880:
0881: boolean added = false;
0882:
0883: final Iterator reals = exprInfo.varsAtBlock(block)
0884: .iterator();
0885:
0886: while (reals.hasNext()) {
0887: final VarExpr node = (VarExpr) reals.next();
0888:
0889: if (node instanceof LocalExpr) {
0890: final LocalExpr var = (LocalExpr) node;
0891:
0892: // If marked push, save it to a stack variable.
0893: // If marked pop, reload from a stack variable.
0894:
0895: final boolean push = exprInfo.push(var);
0896: boolean pop = exprInfo.pop(var);
0897:
0898: if (var.isDef() && exprInfo.save()) {
0899: pop = false;
0900: }
0901:
0902: if (push && pop) {
0903: Assert.isTrue(var != exprInfo.def());
0904:
0905: final StackExpr t1 = (StackExpr) tmp.clone();
0906: final StackExpr t2 = (StackExpr) tmp.clone();
0907:
0908: final StoreExpr store = new StoreExpr(t1, t2,
0909: t2.type());
0910: var.replaceWith(store);
0911:
0912: consInfo.addReal(t2);
0913: consInfo.addReal(t1);
0914: added = true;
0915: } else if (push) {
0916: final StackExpr t1 = (StackExpr) tmp.clone();
0917:
0918: final LocalExpr t2 = (LocalExpr) var.clone();
0919: t2.setDef(exprInfo.def());
0920:
0921: final StoreExpr store = new StoreExpr(t1, t2,
0922: t2.type());
0923:
0924: if (var != exprInfo.def()) {
0925: var.replaceWith(store);
0926: } else {
0927: final Node parent = var.parent();
0928:
0929: if (parent instanceof Stmt) {
0930: // InitStmt or PhiStmt.
0931: final Stmt stmt = new ExprStmt(store);
0932: block.tree().addStmtAfter(stmt,
0933: (Stmt) parent);
0934: } else {
0935: // a := E -> a := (S := E)
0936: Assert
0937: .isTrue(parent instanceof StoreExpr);
0938: final Expr rhs = ((StoreExpr) parent)
0939: .expr();
0940: parent.visit(new ReplaceVisitor(rhs,
0941: store));
0942: store
0943: .visit(new ReplaceVisitor(t2,
0944: rhs));
0945: t2.cleanup();
0946: }
0947: }
0948:
0949: consInfo.addReal(t1);
0950: added = true;
0951: } else if (pop) {
0952: final StackExpr t1 = (StackExpr) tmp.clone();
0953: var.replaceWith(t1);
0954:
0955: consInfo.addReal(t1);
0956: added = true;
0957: }
0958: }
0959: }
0960:
0961: final List s = stackvars[cfg.preOrderIndex(block)];
0962:
0963: if (added) {
0964: s.clear();
0965:
0966: block.tree().visitChildren(new TreeVisitor() {
0967: public void visitStackExpr(final StackExpr expr) {
0968: s.add(expr);
0969: }
0970: });
0971: }
0972:
0973: Iterator succs = cfg.succs(block).iterator();
0974:
0975: while (succs.hasNext()) {
0976: final Block succ = (Block) succs.next();
0977:
0978: final Phi succPhi = exprInfo.exprPhiAtBlock(succ);
0979:
0980: if ((succPhi != null) && succPhi.pushOperand(block)) {
0981: final StackExpr t1 = (StackExpr) tmp.clone();
0982: final LocalExpr t2 = (LocalExpr) exprInfo.def()
0983: .clone();
0984: t2.setDef(exprInfo.def());
0985:
0986: final StoreExpr store = new StoreExpr(t1, t2, t1
0987: .type());
0988:
0989: block.tree().addStmtBeforeJump(new ExprStmt(store));
0990:
0991: s.add(t1);
0992:
0993: consInfo.addReal(t1);
0994:
0995: if (StackPRE.DEBUG) {
0996: System.out.println("insert at end of " + block
0997: + ": " + store);
0998: }
0999: }
1000: }
1001:
1002: succs = cfg.succs(block).iterator();
1003:
1004: while (succs.hasNext()) {
1005: final Block succ = (Block) succs.next();
1006:
1007: final Iterator phis = varPhisAtBlock(succ).iterator();
1008:
1009: while (phis.hasNext()) {
1010: final PhiJoinStmt stmt = (PhiJoinStmt) phis.next();
1011:
1012: final Expr operand = stmt.operandAt(block);
1013:
1014: if ((operand != null)
1015: && (operand.def() == exprInfo.def())) {
1016: final LocalExpr var = (LocalExpr) operand;
1017:
1018: Assert.isFalse(exprInfo.push(var));
1019:
1020: if (exprInfo.pop(var)) {
1021: final StackExpr t1 = (StackExpr) tmp
1022: .clone();
1023: var.replaceWith(t1);
1024: consInfo.addReal(t1);
1025: }
1026: }
1027: }
1028: }
1029: }
1030: }
1031:
1032: abstract class Def {
1033: int version;
1034:
1035: boolean downSafe;
1036:
1037: public Def() {
1038: this .version = next++;
1039: this .downSafe = true;
1040: }
1041:
1042: public void setDownSafe(final boolean flag) {
1043: if (StackPRE.DEBUG) {
1044: System.out.println(this + " DS = " + flag);
1045: }
1046:
1047: downSafe = flag;
1048: }
1049:
1050: public boolean downSafe() {
1051: return downSafe;
1052: }
1053: }
1054:
1055: class RealDef extends Def {
1056: LocalExpr var;
1057:
1058: public RealDef(final LocalExpr var) {
1059: this .var = var;
1060:
1061: if (StackPRE.DEBUG) {
1062: System.out.println("new def for " + var + " in "
1063: + var.parent());
1064: }
1065: }
1066:
1067: public LocalExpr var() {
1068: return var;
1069: }
1070:
1071: public String toString() {
1072: return var.toString() + "{" + version + ","
1073: + (downSafe() ? "" : "!") + "DS}";
1074: }
1075: }
1076:
1077: class Phi extends Def {
1078: Block block;
1079:
1080: HashMap operands;
1081:
1082: HashMap saveOperand;
1083:
1084: boolean live;
1085:
1086: boolean downSafe;
1087:
1088: boolean canBeAvail;
1089:
1090: boolean later;
1091:
1092: public Phi(final Block block) {
1093: this .block = block;
1094:
1095: operands = new HashMap(cfg.preds(block).size() * 2);
1096: saveOperand = new HashMap(cfg.preds(block).size() * 2);
1097:
1098: downSafe = true;
1099: canBeAvail = true;
1100: later = true;
1101: }
1102:
1103: public Block block() {
1104: return block;
1105: }
1106:
1107: public Collection operands() {
1108: return new AbstractCollection() {
1109: public int size() {
1110: return cfg.preds(block).size();
1111: }
1112:
1113: public boolean contains(final Object obj) {
1114: if (obj == null) {
1115: return operands.size() != cfg.preds(block)
1116: .size();
1117: }
1118:
1119: return operands.containsValue(obj);
1120: }
1121:
1122: public Iterator iterator() {
1123: final Iterator iter = cfg.preds(block).iterator();
1124:
1125: return new Iterator() {
1126: public boolean hasNext() {
1127: return iter.hasNext();
1128: }
1129:
1130: public Object next() {
1131: final Block block = (Block) iter.next();
1132: return operandAt(block);
1133: }
1134:
1135: public void remove() {
1136: throw new UnsupportedOperationException();
1137: }
1138: };
1139: }
1140: };
1141: }
1142:
1143: public Def operandAt(final Block block) {
1144: return (Def) operands.get(block);
1145: }
1146:
1147: public void setOperandAt(final Block block, final Def def) {
1148: if (def != null) {
1149: operands.put(block, def);
1150: } else {
1151: operands.remove(block);
1152: }
1153: }
1154:
1155: public void setPushOperand(final Block block, final boolean flag) {
1156: if (StackPRE.DEBUG) {
1157: System.out.println(" operand " + block + " save="
1158: + flag);
1159: }
1160:
1161: saveOperand.put(block, new Boolean(flag));
1162: }
1163:
1164: public boolean pushOperand(final Block block) {
1165: final Boolean flag = (Boolean) saveOperand.get(block);
1166: return (flag != null) && flag.booleanValue();
1167: }
1168:
1169: public boolean insert(final Block block) {
1170: final Def def = operandAt(block);
1171:
1172: if (def == null) {
1173: return true;
1174: }
1175:
1176: if (!def.downSafe()) {
1177: return true;
1178: }
1179:
1180: if ((def instanceof Phi) && !((Phi) def).willBeAvail()) {
1181: return true;
1182: }
1183:
1184: return false;
1185: }
1186:
1187: public boolean willBeAvail() {
1188: return canBeAvail && !later;
1189: }
1190:
1191: public void setCanBeAvail(final boolean flag) {
1192: if (StackPRE.DEBUG) {
1193: System.out.println(this + " CBA = " + flag);
1194: }
1195:
1196: canBeAvail = flag;
1197: }
1198:
1199: public boolean canBeAvail() {
1200: return canBeAvail;
1201: }
1202:
1203: public void setLater(final boolean flag) {
1204: if (StackPRE.DEBUG) {
1205: System.out.println(this + " Later = " + flag);
1206: }
1207:
1208: later = flag;
1209: }
1210:
1211: public boolean later() {
1212: return later;
1213: }
1214:
1215: public String toString() {
1216: String s = "";
1217:
1218: final Iterator iter = cfg.preds(block).iterator();
1219:
1220: while (iter.hasNext()) {
1221: final Block pred = (Block) iter.next();
1222: final Def def = operandAt(pred);
1223:
1224: s += pred.label() + "=";
1225:
1226: if (def == null) {
1227: s += "null";
1228: } else {
1229: s += def.version;
1230: }
1231:
1232: if (iter.hasNext()) {
1233: s += ", ";
1234: }
1235: }
1236:
1237: return "phi" + "{" + version + ","
1238: + (downSafe() ? "" : "!") + "DS,"
1239: + (canBeAvail() ? "" : "!") + "CBA,"
1240: + (later() ? "" : "!") + "Later}(" + s + ")";
1241: }
1242: }
1243:
1244: public List varPhisAtBlock(final Block block) {
1245: return varphis[cfg.preOrderIndex(block)];
1246: }
1247:
1248: /**
1249: * Maintain the occurences so that they are visited in a preorder traversal
1250: * of the dominator tree.
1251: */
1252: private final class ExprInfo {
1253: ArrayList[] vars;
1254:
1255: Phi[] phis;
1256:
1257: boolean save;
1258:
1259: Map pushes;
1260:
1261: Map pops;
1262:
1263: Map defs;
1264:
1265: LocalExpr def;
1266:
1267: ArrayList cleanup;
1268:
1269: public ExprInfo(final LocalExpr def) {
1270: this .def = def;
1271:
1272: vars = new ArrayList[cfg.size()];
1273:
1274: for (int i = 0; i < vars.length; i++) {
1275: vars[i] = new ArrayList();
1276: }
1277:
1278: phis = new Phi[cfg.size()];
1279:
1280: save = false;
1281:
1282: pushes = new HashMap();
1283: pops = new HashMap();
1284:
1285: defs = new HashMap();
1286:
1287: cleanup = new ArrayList();
1288: }
1289:
1290: public void cleanup() {
1291: final Iterator iter = cleanup.iterator();
1292:
1293: while (iter.hasNext()) {
1294: final Node node = (Node) iter.next();
1295: node.cleanup();
1296: }
1297:
1298: vars = null;
1299: phis = null;
1300: pushes = null;
1301: pops = null;
1302: defs = null;
1303: def = null;
1304: cleanup = null;
1305: }
1306:
1307: public void registerForCleanup(final Node node) {
1308: cleanup.add(node);
1309: }
1310:
1311: public void setSave(final boolean flag) {
1312: save = flag;
1313: }
1314:
1315: public boolean save() {
1316: return save;
1317: }
1318:
1319: public void setPush(final LocalExpr expr, final boolean flag) {
1320: pushes.put(expr, new Boolean(flag));
1321: }
1322:
1323: public boolean push(final LocalExpr expr) {
1324: final Boolean b = (Boolean) pushes.get(expr);
1325: return (b != null) && b.booleanValue();
1326: }
1327:
1328: public void setPop(final LocalExpr expr, final boolean flag) {
1329: pops.put(expr, new Boolean(flag));
1330: }
1331:
1332: public boolean pop(final LocalExpr expr) {
1333: final Boolean b = (Boolean) pops.get(expr);
1334: return (b != null) && b.booleanValue();
1335: }
1336:
1337: public void setDef(final LocalExpr expr, final Def def) {
1338: if (StackPRE.DEBUG) {
1339: System.out.println(" setting def for " + expr
1340: + " to " + def);
1341: }
1342:
1343: if (def != null) {
1344: defs.put(expr, def);
1345: } else {
1346: defs.remove(expr);
1347: }
1348: }
1349:
1350: public Def def(final LocalExpr expr) {
1351: final Def def = (Def) defs.get(expr);
1352:
1353: if (StackPRE.DEBUG) {
1354: System.out.println(" def for " + expr + " is "
1355: + def);
1356: }
1357:
1358: return def;
1359: }
1360:
1361: public LocalExpr def() {
1362: return def;
1363: }
1364:
1365: public void addPhi(final Block block) {
1366: Phi phi = phis[cfg.preOrderIndex(block)];
1367:
1368: if (phi == null) {
1369: if (StackPRE.DEBUG) {
1370: System.out.println(" add phi for " + def
1371: + " at " + block);
1372: }
1373:
1374: phi = new Phi(block);
1375: phis[cfg.preOrderIndex(block)] = phi;
1376: }
1377: }
1378:
1379: public List varsAtBlock(final Block block) {
1380: final int blockIndex = cfg.preOrderIndex(block);
1381:
1382: final List list = new ArrayList(vars[blockIndex].size()
1383: + stackvars[blockIndex].size());
1384:
1385: final Iterator viter = vars[blockIndex].iterator();
1386: final Iterator siter = stackvars[blockIndex].iterator();
1387:
1388: if (!viter.hasNext() && !siter.hasNext()) {
1389: return new ArrayList(0);
1390: }
1391:
1392: block.tree().visitChildren(new TreeVisitor() {
1393: VarExpr vnext = null;
1394:
1395: VarExpr snext = null;
1396:
1397: {
1398: if (viter.hasNext()) {
1399: vnext = (VarExpr) viter.next();
1400: }
1401:
1402: if (siter.hasNext()) {
1403: snext = (VarExpr) siter.next();
1404: }
1405: }
1406:
1407: public void visitStmt(final Stmt stmt) {
1408: if (((vnext != null) && (vnext.stmt() == stmt))
1409: || ((snext != null) && (snext.stmt() == stmt))) {
1410: super .visitStmt(stmt);
1411: }
1412: }
1413:
1414: public void visitVarExpr(final VarExpr expr) {
1415: super .visitExpr(expr);
1416:
1417: if (expr == vnext) {
1418: if (viter.hasNext()) {
1419: vnext = (VarExpr) viter.next();
1420: } else {
1421: vnext = null;
1422: }
1423:
1424: if (expr == snext) {
1425: if (siter.hasNext()) {
1426: snext = (VarExpr) siter.next();
1427: } else {
1428: snext = null;
1429: }
1430: }
1431:
1432: list.add(expr);
1433: } else if (expr == snext) {
1434: if (siter.hasNext()) {
1435: snext = (VarExpr) siter.next();
1436: } else {
1437: snext = null;
1438: }
1439:
1440: list.add(expr);
1441: }
1442: }
1443: });
1444:
1445: return list;
1446: }
1447:
1448: public Phi exprPhiAtBlock(final Block block) {
1449: return phis[cfg.preOrderIndex(block)];
1450: }
1451:
1452: protected void print() {
1453: System.out.println("Print for " + def
1454: + "------------------");
1455:
1456: cfg.visit(new PrintVisitor() {
1457: Phi phi = null;
1458:
1459: public void visitBlock(final Block block) {
1460: phi = exprPhiAtBlock(block);
1461: super .visitBlock(block);
1462: }
1463:
1464: public void visitLabelStmt(final LabelStmt stmt) {
1465: super .visitLabelStmt(stmt);
1466:
1467: if (stmt.label().startsBlock()) {
1468: if (phi != null) {
1469: println(phi);
1470: }
1471: }
1472: }
1473:
1474: public void visitLocalExpr(final LocalExpr expr) {
1475: super .visitLocalExpr(expr);
1476:
1477: if (expr.def() == def) {
1478: super .print("{" + defs.get(expr) + "}");
1479: }
1480: }
1481: });
1482:
1483: System.out
1484: .println("End Print ----------------------------");
1485: }
1486: }
1487:
1488: class Worklist {
1489: Map exprInfos;
1490:
1491: LinkedList exprs;
1492:
1493: public Worklist() {
1494: exprInfos = new HashMap();
1495: exprs = new LinkedList();
1496: }
1497:
1498: public boolean isEmpty() {
1499: return exprs.isEmpty();
1500: }
1501:
1502: public ExprInfo removeFirst() {
1503: final ExprInfo exprInfo = (ExprInfo) exprs.removeFirst();
1504: exprInfos.remove(exprInfo.def());
1505: return exprInfo;
1506: }
1507:
1508: public void addLocalVar(final LocalExpr var) {
1509: final int blockIndex = cfg.preOrderIndex(var.block());
1510:
1511: if (StackPRE.DEBUG) {
1512: System.out.println("add var " + var);
1513: }
1514:
1515: ExprInfo exprInfo = (ExprInfo) exprInfos.get(var.def());
1516:
1517: if (exprInfo == null) {
1518: exprInfo = new ExprInfo((LocalExpr) var.def());
1519: exprs.add(exprInfo);
1520: exprInfos.put(var.def(), exprInfo);
1521:
1522: if (StackPRE.DEBUG) {
1523: System.out.println(" add info for " + var);
1524: }
1525: }
1526:
1527: exprInfo.vars[blockIndex].add(var);
1528: }
1529:
1530: public void addStackVar(final StackExpr var) {
1531: final int blockIndex = cfg.preOrderIndex(var.block());
1532:
1533: if (StackPRE.DEBUG) {
1534: System.out.println("add var " + var);
1535: }
1536:
1537: stackvars[blockIndex].add(var);
1538: }
1539:
1540: public void addVarPhi(final PhiJoinStmt stmt) {
1541: varphis[cfg.preOrderIndex(stmt.block())].add(stmt);
1542: }
1543:
1544: public void prependVarPhi(final PhiJoinStmt stmt) {
1545: final List v = varphis[cfg.preOrderIndex(stmt.block())];
1546:
1547: if (!v.contains(stmt)) {
1548: v.add(0, stmt);
1549: }
1550: }
1551: }
1552: }
|