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.tbaa.*;
0029: import EDU.purdue.cs.bloat.tree.*;
0030: import EDU.purdue.cs.bloat.util.*;
0031:
0032: /**
0033: * Perform partial redundancy elimination of a CFG in SSA form using the
0034: * SSA-based algorithm described in:
0035: *
0036: * <pre>
0037: * Fred Chow, Sun Chan, Robert Kennedy, Shin-Ming Liu, Raymond Lo,
0038: * and Peng Tu, "A New Algorithm for Partial Redundancy Elimination
0039: * based on SSA Form", Proc. PLDI '97: 273-286, 1997.
0040: * </pre>
0041: *
0042: * NOTE: The type for all occurrences of an inserted variable is the same as the
0043: * type of the first occurrence of the expression the variable replaces. This
0044: * type is guaranteed since we only group expression with equal types.
0045: */
0046:
0047: /*
0048: * Okay, you asked for it: SSAPRE. SSAPRE stands for Partial Redundency
0049: * Elimination in Static Single-Assignment form. Partial Redundency Elimination
0050: * invovles finding multiple occurreces of the same expressions (i.e.
0051: * expressions that are lexically equivalent) and moving those occurrences up
0052: * higher in the CFG so that the expression is evaluated fewer times.
0053: * Occurrences of the expression that has been moved are replaced with a
0054: * temporary variable that is assigned the value of the moved expression. PRE is
0055: * a superset of Common Subexpression Elimination.
0056: *
0057: * The Golden Rule of SSAPRE: Move expressions to eliminate redundent
0058: * evaluations, but do not make more work along a given path in the CFG by
0059: * introducing an expression along a path where it originally was not.
0060: *
0061: * PRE techniques have been around for quite sometime, but most algorithms used
0062: * a bit vector notation to represent occurrences of an expression. In order to
0063: * apply those PRE techniques, the CFG in SSA form would have to be transformed
0064: * into bit vector notation before PRE could be performed. The modified bit
0065: * vectors would then have to be transformed back into a CFG in SSA form before
0066: * any other optimizations (or code generation) could take place.
0067: *
0068: * That was the way life was until [Chow, et. al.] came along. At the 1997 PLDI
0069: * conference, they presented a paper that showed how PRE could be performed
0070: * directly on a CFG in SSA form. The paper itself is a rather difficult read.
0071: * So don't feel bad if you don't understand it on the first (or seventeenth)
0072: * read.
0073: *
0074: * BLOAT performs SSAPRE on the CFG for optimizable methods. Due to some of
0075: * Java's quirks (e.g. exceptions), this implementation does not follow Chow's
0076: * exactly. However, it is very close and understanding this implementation will
0077: * aid the understanding of Chow and vice versa.
0078: *
0079: * The first step in SSAPRE is to create a worklist of all expressions that are
0080: * candidates for SSAPRE. Only first-order expressions are entered into the
0081: * worklist. First-order expressions consist of a single operators and two
0082: * operands that are either a variable or have a constant value. For instance,
0083: * a+b is a first-order expression, while a+b-c is not. The first-order
0084: * expressions that are inserted into the worklist are "real occurrences" of the
0085: * expression (as opposed to PHI-statements or PHI-operands, as we shall shortly
0086: * see). In addition to real occurrences of the expression, the worklist also
0087: * contains kill statements. Certain constructs in Java, such as exceptions,
0088: * method calls, and synchronized blocks, limit the assumptions one can make
0089: * about the behavior of the code. Thus, at places in the code where such
0090: * constructs occur, kills are inserted to say "We cannot move code across this
0091: * point." The above is performed in collectOccurrences().
0092: *
0093: * SSAPRE is then performed on each expression in the worklist. The first step
0094: * in SSAPRE is to place PHI-functions. PHI-functions are similar to the
0095: * phi-functions that occur in converting a CFG to SSA form. Essentially, a
0096: * PHI-function is placed at a block (node in the CFG) at which a join occurs
0097: * (i.a. there are two paths that can enter the block), at which the expression
0098: * is available on at least one of the incoming paths, and at which the
0099: * expression will be used again (e.g. we don't bother putting a PHI-function at
0100: * the "exit" node). This leads us to place PHI-functions in two situations.
0101: * First, for each block that contains a real occurrence of the expression, a
0102: * PHI-function is placed at every block in its iterated dominance frontier
0103: * (DF+). Second, a PHI-function is placed in every block that contains a
0104: * phi-function for either of the operands to the expression. At this point, the
0105: * operands to the PHI-functions are unknown. They are of the form:
0106: *
0107: * h = PHI(h, h, ..., h)
0108: *
0109: * and are referred to as PHI-statements (also called "expression-PHIs" in
0110: * Chow's paper). The method placePhis() inserts these hypothetical
0111: * PHI-functions into the CFG.
0112: *
0113: * Once the expression-PHIs have been placed, version numbers are assigned to
0114: * each hypothetical h. Both real occurrences of the expression and
0115: * PHI-statements for the expression have a numbered h value associated with
0116: * them. Occurrences that have the same version number have identical values and
0117: * any control flow path that includes two difference h-versions must cross an
0118: * assignment to an operand of the expression or an PHI-statement for h. The
0119: * version numbers are assigned in two passes over the CFG. The first pass
0120: * compiles of a worklist containing all of the real occurrences that are
0121: * defined by an PHI-statement. It also maintains a stack of real occurrences of
0122: * the expression. The first pass optimistically assumes that versions of the
0123: * operands to a PHI-function are the same as the version of the expression that
0124: * is on top of the expression stack. The second pass corrects any false
0125: * assumptions that were made during the first pass. Since the first pass saw
0126: * all of the occurrences, the versions of the h-variables can be determined
0127: * from the existence of a phi-function (note lowercase phi) at that block. In
0128: * some cases, the occurrence may be placed back into the worklist for further
0129: * processing. The rename() method handles the assignment of version numbers
0130: * using this two-pass method.
0131: *
0132: * Now that the PHI-functions have been placed and version numbers have been
0133: * assigned, other information about the hypotheticals is extracted and will be
0134: * used to move redundent occurrences of the expression. The first piece of
0135: * information that is calculated is whether or not an PHI-statement is
0136: * "down-safe" (also referred to as being "anticipated"). When version numbers
0137: * were assigned to hypotheticals, a use-def relationship was created:
0138: * PHI-statements use operands that are hypotheticals defined by other
0139: * occurrences. One can conceptualize a directed graph consisting of
0140: * PHI-statements and the directed edges going from a use of a hypothetical to
0141: * its definition. This graph is referred to by Chow as the "SSA Graph". (This
0142: * is not to be confused with the class SSAGraph which models the SSA Graph for
0143: * variables, not expressions. This implementation does not directly model the
0144: * SSA Graph.) Using the SSA Graph the down-safety of an PHI-statement is
0145: * computed by backwards propagation along the use-def chains. An PHI-statement
0146: * is not down-safe if there is a control flow path from that PHI-statement
0147: * along which the expression is not evaluated (i.e. there is no real
0148: * occurrence) before the exit block is encountered or one of the expression's
0149: * variables is redefined. Why is down-safety important? If an PHI-statement is
0150: * not down-safe, it is not worthwhile to hoist it any higher in the code. If it
0151: * were to be hoisted, it might add a unnecessary evaluation of the expression
0152: * along some path. This would break the golden rule of SSAPRE. There are two
0153: * situations in which an PHI-statement is not down-safe. The first occurs when
0154: * there is no path to exit along which the result (left hand side) of the
0155: * PHI-statement is not used. The second occurs when there is a path to exit
0156: * along which the only use of the PHI-statement result is as an operand to an
0157: * PHI-statement which itself is not down-safe. The PHI-statement that fit the
0158: * first criterion can be marked as not down-safe during the renaming step. In
0159: * addition, each operand to an PHI-statement (called an PHI-operand) is marked
0160: * as "has real use" when the path to the PHI-operand crosses a real occurrence
0161: * of the same version of the expression. Simply put, an PHI-operand has a real
0162: * use, if it is associated with a real expression instead of an PHI-statement.
0163: * The down-safety of the PHI-statements in the CFG is computed using of the
0164: * downSafety() and resetDownSafe() methods.
0165: *
0166: * The above description was written by Dave and Steve Lennon in early September
0167: * of 1998. I'm surprised at how much we knew then. Consult the BLOAT Book for
0168: * the conclusion to our exciting SSAPRE saga.
0169: */
0170:
0171: public class SSAPRE {
0172: public static boolean DEBUG = false;
0173:
0174: public static boolean NO_THREAD = false; // Do we ignore threads?
0175:
0176: public static boolean NO_PRECISE = false; // Are exceptions not precise?
0177:
0178: public static boolean NO_ACCESS_PATHS = false;
0179:
0180: protected FlowGraph cfg; // CFG on which to perform SSAPRE
0181:
0182: protected int nextValueNumber; // Next value number to assign
0183:
0184: protected EditorContext context;
0185:
0186: protected ResizeableArrayList[] kills;
0187:
0188: protected boolean[] killsSorted;
0189:
0190: protected SideEffectChecker sideEffects;
0191:
0192: protected ExprWorklist worklist; // Worklist containing expr to analyze
0193:
0194: // Maps phi statements together as to allow for access path reduction?
0195: protected HashMap phiRelated;
0196:
0197: /**
0198: * Constructor.
0199: *
0200: * @param cfg
0201: * Control flow graph on which to perform SSA-based PRE.
0202: * @param context The EditorContext containing all the classes that BLOAT
0203: * knows about.
0204: */
0205: public SSAPRE(final FlowGraph cfg, final EditorContext context) {
0206: this .cfg = cfg;
0207: this .context = context;
0208: }
0209:
0210: /**
0211: * Performs SSA-based partial redundency elimination (PRE) on a control flow
0212: * graph.
0213: */
0214: public void transform() {
0215: sideEffects = new SideEffectChecker(context);
0216:
0217: kills = new ResizeableArrayList[cfg.size()];
0218: killsSorted = new boolean[cfg.size()];
0219:
0220: for (int i = 0; i < kills.length; i++) {
0221: kills[i] = new ResizeableArrayList();
0222: killsSorted[i] = false;
0223: }
0224:
0225: // In a single pass over the CFG:
0226: //
0227: // Number the expressions in each block in ascending order.
0228: // Insert all first-order expressions into the worklist.
0229: // Insert access path kills into the worklist.
0230: // Insert exception throw kills into the worklist.
0231: // Locate phi-related expressions.
0232: // Find the next value number.
0233:
0234: worklist = new ExprWorklist();
0235: phiRelated = new HashMap();
0236:
0237: // Compile the worklist of expressions on which to perform SSAPRE.
0238: collectOccurrences();
0239:
0240: // Do the transformation for each expression.
0241: while (!worklist.isEmpty()) {
0242: final ExprInfo exprInfo = worklist.removeFirst();
0243: transform(exprInfo);
0244: }
0245:
0246: // null these guys so that they'll be garbage collected sooner
0247: sideEffects = null;
0248: kills = null;
0249: worklist = null;
0250: }
0251:
0252: /**
0253: * Performs partial redundency elimination on a given expression. This
0254: * method is called on every lexically-distinct expression in a method.
0255: *
0256: * @see #collectOccurrences
0257: *
0258: * @see #placePhis
0259: * @see #rename
0260: * @see #downSafety
0261: * @see #willBeAvail
0262: * @see #finalize
0263: */
0264: private void transform(final ExprInfo exprInfo) {
0265: if (SSAPRE.DEBUG) {
0266: System.out.println("PRE for " + exprInfo.prototype()
0267: + " -------------------------");
0268: }
0269:
0270: if (exprInfo.numUses() == 0) {
0271: if (SSAPRE.DEBUG) {
0272: System.out.println("Skipping...all occurrences are "
0273: + "as targets. -------------------------");
0274: }
0275:
0276: exprInfo.cleanup();
0277: return;
0278: }
0279:
0280: if (SSAPRE.DEBUG) {
0281: System.out.println("Placing Phis for "
0282: + exprInfo.prototype()
0283: + " -------------------------");
0284: }
0285:
0286: // Place the PHI nodes for the expression. Note that these PHI nodes are
0287: // for expressions, not variables. However, the same Phi classes are
0288: // used.
0289: placePhis(exprInfo);
0290:
0291: if (SSAPRE.DEBUG) {
0292: exprInfo.print();
0293: System.out.println("Renaming for " + exprInfo.prototype()
0294: + " -------------------------");
0295: }
0296:
0297: // Calculate version numbers for each occurrence of the expression
0298: // in exprInfo. Rename occurrences that have the same version number.
0299: rename(exprInfo);
0300:
0301: if (SSAPRE.DEBUG) {
0302: exprInfo.print();
0303: System.out.println("Down safety for "
0304: + exprInfo.prototype()
0305: + " -------------------------");
0306: }
0307:
0308: // Determine which PHI-nodes are "down safe". "Down safe" nodes are used
0309: // at least once on all paths from the PHI-node to the exit node.
0310: downSafety(exprInfo);
0311:
0312: if (SSAPRE.DEBUG) {
0313: System.out.println("Will be available for "
0314: + exprInfo.prototype()
0315: + " -------------------------");
0316: }
0317:
0318: // Determine at which PHI-nodes the expression in exprInfo will be
0319: // available after code insertions are performed. Code can only be
0320: // inserted at the end of the predacessor blocks of these nodes.
0321: willBeAvail(exprInfo);
0322:
0323: if (SSAPRE.DEBUG) {
0324: System.out.println("Finalize for " + exprInfo.prototype()
0325: + " -------------------------");
0326: }
0327:
0328: finalize(exprInfo);
0329:
0330: if (SSAPRE.DEBUG) {
0331: System.out.println("Code motion for "
0332: + exprInfo.prototype()
0333: + " -------------------------");
0334: }
0335:
0336: final Type type = exprInfo.prototype().type();
0337: final LocalVariable v = cfg.method().newLocal(type);
0338: final VarExpr tmp = new LocalExpr(v.index(), type);
0339:
0340: final SSAConstructionInfo consInfo = new SSAConstructionInfo(
0341: cfg, tmp);
0342: codeMotion(exprInfo, tmp, consInfo);
0343:
0344: if (SSAPRE.DEBUG) {
0345: System.out.println("Performing incremental SSA for "
0346: + exprInfo.prototype()
0347: + " -------------------------");
0348: }
0349:
0350: // OK, this shouldn't be necessary. We should construct the SSA
0351: // form for t as we do code motion using the expr-phis. But that was
0352: // quite buggy in the early implementations (and probably still is),
0353: // so I just build SSA form in another pass. If you change it to
0354: // build SSA form for t during code motion, you must also remove
0355: // the phis not in the IDF of the defs of t and fix up the FUD chains
0356: // afterward.
0357:
0358: SSA.transform(cfg, consInfo);
0359:
0360: // Set the value numbers for all the new exprs.
0361: // This uses the occurrences of the var and the var-phi information
0362: // added to consInfo by SSA construction.
0363:
0364: setValueNumbers(consInfo);
0365:
0366: // Add parents of the real occurrences to the var.
0367:
0368: enqueueParents(consInfo);
0369:
0370: if (SSAPRE.DEBUG) {
0371: exprInfo.print();
0372: System.out.println("Done with PRE for "
0373: + exprInfo.prototype()
0374: + " -------------------------");
0375: }
0376:
0377: // Null out all the pointers in the exprInfo in case the exprInfo
0378: // is still reachable.
0379: exprInfo.cleanup();
0380: }
0381:
0382: /**
0383: * Visits the CFG and for each lexically-distinct first-order expression
0384: * whose subexpressions no have subexpressions nor side effects (that is,
0385: * expressions containing one operatand and comprised of only local
0386: * variables and/or constants), places all occurrences of that expression,
0387: * sorted by their pre-order positions in the CFG, into a worklist.
0388: *
0389: * Note that only real occurrences of expression are inserted into the
0390: * worklist. PHI and PHI-operand occurrences have not been placed yet.
0391: *
0392: * Additionally, Kill expressions are placed in the worklist to indicate
0393: * boundaries across which code cannot be hoisted.
0394: */
0395: private void collectOccurrences() {
0396: // count represents the preorder number for each expression. It is
0397: // assigned to each expression's key
0398: final Int count = new Int();
0399:
0400: // maxValue is the maximum value number encountered on a traversal
0401: // of the expression tree. It is used to determine this.nextValueNumber
0402: final Int maxValue = new Int();
0403:
0404: // A Set of Blocks that begin a protected region
0405: final Set beginTry = beginTry();
0406:
0407: // Visit each node in the CFG. At each Expr node make note of the
0408: // node's preorder number. Keep track of the largest value number
0409: // encountered. Add Kills to the worklist when necessary. Add
0410: // first-order real occurrences of an expression to the worklist at
0411: // MemRefExpr (access paths) and Expr (expression) nodes.
0412: cfg.visit(new TreeVisitor() {
0413: public void visitBlock(final Block block) {
0414: if (beginTry.contains(block)) {
0415: // If the block begins a protected region, then we must
0416: // insert
0417: // a Kill to prevent hoisting out of the region.
0418: worklist.addKill(block, new ExceptionKill(
0419: count.value++));
0420: }
0421:
0422: block.visitChildren(this );
0423: }
0424:
0425: public void visitPhiStmt(final PhiStmt stmt) {
0426: if (maxValue.value < stmt.valueNumber()) {
0427: maxValue.value = stmt.valueNumber();
0428: }
0429:
0430: stmt.visitChildren(this );
0431:
0432: final Iterator iter = stmt.operands().iterator();
0433:
0434: // Iterate over all of the operands to the phi node.
0435: // Make special note of local (or stack) variables.
0436: while (iter.hasNext()) {
0437: final Expr operand = (Expr) iter.next();
0438:
0439: if (operand instanceof VarExpr) {
0440: if (operand.def() != null) {
0441: phiRelatedUnion(operand.def(), stmt
0442: .target());
0443: }
0444: }
0445: }
0446: }
0447:
0448: public void visitConstantExpr(final ConstantExpr expr) {
0449: if (maxValue.value < expr.valueNumber()) {
0450: maxValue.value = expr.valueNumber();
0451: }
0452:
0453: expr.setKey(count.value++);
0454: }
0455:
0456: public void visitVarExpr(final VarExpr expr) {
0457: if (maxValue.value < expr.valueNumber()) {
0458: maxValue.value = expr.valueNumber();
0459: }
0460:
0461: expr.setKey(count.value++);
0462: }
0463:
0464: public void visitCatchExpr(final CatchExpr expr) {
0465: if (maxValue.value < expr.valueNumber()) {
0466: maxValue.value = expr.valueNumber();
0467: }
0468:
0469: expr.visitChildren(this );
0470: expr.setKey(count.value++);
0471: worklist.addKill(expr.block(), new ExceptionKill(expr
0472: .key()));
0473: }
0474:
0475: public void visitMonitorStmt(final MonitorStmt stmt) {
0476: if (maxValue.value < stmt.valueNumber()) {
0477: maxValue.value = stmt.valueNumber();
0478: }
0479:
0480: if (!SSAPRE.NO_THREAD) {
0481: stmt.visitChildren(this );
0482: stmt.setKey(count.value++);
0483: worklist.addKill(stmt.block(), new MemRefKill(stmt
0484: .key()));
0485: }
0486: }
0487:
0488: public void visitCallExpr(final CallExpr expr) {
0489: if (maxValue.value < expr.valueNumber()) {
0490: maxValue.value = expr.valueNumber();
0491: }
0492:
0493: expr.visitChildren(this );
0494: expr.setKey(count.value++);
0495: worklist.addKill(expr.block(), new MemRefKill(expr
0496: .key()));
0497: }
0498:
0499: public void visitMemRefExpr(final MemRefExpr expr) {
0500: if (maxValue.value < expr.valueNumber()) {
0501: maxValue.value = expr.valueNumber();
0502: }
0503:
0504: boolean firstOrder = isFirstOrder(expr);
0505:
0506: if (!firstOrder) {
0507: expr.visitChildren(this );
0508: }
0509:
0510: expr.setKey(count.value++);
0511:
0512: if (expr.isDef()) {
0513: worklist.addKill(expr.block(), new MemRefKill(expr,
0514: expr.key()));
0515: }
0516:
0517: if (firstOrder) {
0518: worklist.addReal(expr);
0519: }
0520: }
0521:
0522: public void visitStmt(final Stmt stmt) {
0523: if (maxValue.value < stmt.valueNumber()) {
0524: maxValue.value = stmt.valueNumber();
0525: }
0526:
0527: stmt.visitChildren(this );
0528: }
0529:
0530: public void visitExpr(final Expr expr) {
0531: if (maxValue.value < expr.valueNumber()) {
0532: maxValue.value = expr.valueNumber();
0533: }
0534:
0535: if (isFirstOrder(expr)) {
0536: worklist.addReal(expr);
0537: } else {
0538: expr.visitChildren(this );
0539: }
0540:
0541: expr.setKey(count.value++);
0542: }
0543: });
0544:
0545: nextValueNumber = maxValue.value + 1;
0546: }
0547:
0548: /**
0549: * Returns a Set of Blocks that begin the protected regions in the CFG.
0550: */
0551: private Set beginTry() {
0552: final Set beginTry = new HashSet();
0553:
0554: final Iterator blocks = cfg.catchBlocks().iterator();
0555:
0556: while (blocks.hasNext()) {
0557: final Block block = (Block) blocks.next();
0558:
0559: final Handler handler = (Handler) cfg.handlersMap().get(
0560: block);
0561:
0562: if (handler != null) {
0563: final HashSet p = new HashSet();
0564:
0565: final Iterator prots = handler.protectedBlocks()
0566: .iterator();
0567:
0568: while (prots.hasNext()) {
0569: final Block prot = (Block) prots.next();
0570: p.addAll(cfg.preds(prot));
0571: }
0572:
0573: p.removeAll(handler.protectedBlocks());
0574:
0575: // Add the protected region blocks which have preds outside the
0576: // region to the beginTry set.
0577: final Iterator preds = p.iterator();
0578:
0579: while (preds.hasNext()) {
0580: final Block pred = (Block) preds.next();
0581: beginTry.addAll(cfg.succs(pred));
0582: }
0583: }
0584: }
0585:
0586: return beginTry;
0587: }
0588:
0589: private void enqueueParents(final SSAConstructionInfo consInfo) {
0590: final Set seen = new HashSet();
0591:
0592: final Iterator iter = cfg.nodes().iterator();
0593:
0594: while (iter.hasNext()) {
0595: final Block block = (Block) iter.next();
0596:
0597: final Iterator e = consInfo.realsAtBlock(block).iterator();
0598:
0599: while (e.hasNext()) {
0600: final VarExpr real = (VarExpr) e.next();
0601:
0602: Node p = real.parent();
0603:
0604: if ((p instanceof StoreExpr) && real.isDef()) {
0605: p = p.parent();
0606: }
0607:
0608: if ((p instanceof Expr) && !seen.contains(p)) {
0609: final Expr expr = (Expr) p;
0610:
0611: seen.add(p);
0612:
0613: if (isFirstOrder(expr)) {
0614: worklist.addReal(expr);
0615: }
0616: }
0617: }
0618: }
0619: }
0620:
0621: private void setValueNumbers(final SSAConstructionInfo consInfo) {
0622: // Compute value numbers using the RPO algorithm \cite{Simpson96}.
0623: // For such a small set of numbers this should be faster than
0624: // recomputing the strongly connected components of the entire SSA
0625: // graph and using the SCC-based algorithm.
0626:
0627: boolean changed = true;
0628:
0629: while (changed) {
0630: changed = false;
0631:
0632: final List postOrder = cfg.postOrder();
0633: final ListIterator iter = postOrder.listIterator(postOrder
0634: .size());
0635:
0636: while (iter.hasPrevious()) {
0637: final Block block = (Block) iter.previous();
0638:
0639: final PhiStmt phi = consInfo.phiAtBlock(block);
0640:
0641: if (phi != null) {
0642: if (phi.target().valueNumber() == -1) {
0643: phi.target().setValueNumber(nextValueNumber++);
0644: changed = true;
0645: }
0646:
0647: final Iterator operands = phi.operands().iterator();
0648:
0649: while (operands.hasNext()) {
0650: final VarExpr operand = (VarExpr) operands
0651: .next();
0652:
0653: if (operand == null) {
0654: continue;
0655: }
0656:
0657: final VarExpr def = (VarExpr) operand.def();
0658:
0659: if (def == null) {
0660: if (operand.valueNumber() == -1) {
0661: operand
0662: .setValueNumber(nextValueNumber++);
0663: changed = true;
0664: }
0665: continue;
0666: }
0667:
0668: if (def.valueNumber() == -1) {
0669: def.setValueNumber(nextValueNumber++);
0670: changed = true;
0671: }
0672:
0673: if (def.valueNumber() != operand.valueNumber()) {
0674: operand.setValueNumber(def.valueNumber());
0675: changed = true;
0676: }
0677: }
0678: }
0679:
0680: final Iterator e = consInfo.realsAtBlock(block)
0681: .iterator();
0682:
0683: while (e.hasNext()) {
0684: final VarExpr real = (VarExpr) e.next();
0685:
0686: if (real.isDef()) {
0687: Assert
0688: .isTrue(real.parent() instanceof StoreExpr);
0689:
0690: final StoreExpr store = (StoreExpr) real
0691: .parent();
0692: final Expr rhs = store.expr();
0693:
0694: if (rhs.valueNumber() == -1) {
0695: // This should only happen with hoisted stores.
0696: rhs.setValueNumber(nextValueNumber++);
0697: changed = true;
0698: }
0699:
0700: if (store.valueNumber() != rhs.valueNumber()) {
0701: // This should only happen with hoisted stores.
0702: store.setValueNumber(rhs.valueNumber());
0703: changed = true;
0704: }
0705:
0706: if (real.valueNumber() != rhs.valueNumber()) {
0707: real.setValueNumber(rhs.valueNumber());
0708: changed = true;
0709: }
0710: } else {
0711: final VarExpr def = (VarExpr) real.def();
0712:
0713: if (def == null) {
0714: if (real.valueNumber() == -1) {
0715: real.setValueNumber(nextValueNumber++);
0716: changed = true;
0717: }
0718: continue;
0719: }
0720:
0721: if (def.valueNumber() == -1) {
0722: // This shouldn't happen.
0723: def.setValueNumber(nextValueNumber++);
0724: changed = true;
0725: }
0726:
0727: if (def.valueNumber() != real.valueNumber()) {
0728: real.setValueNumber(def.valueNumber());
0729: changed = true;
0730: }
0731: }
0732: }
0733: }
0734: }
0735:
0736: final Iterator iter = cfg.nodes().iterator();
0737:
0738: while (iter.hasNext()) {
0739: final Block block = (Block) iter.next();
0740:
0741: final PhiStmt phi = consInfo.phiAtBlock(block);
0742:
0743: if (phi != null) {
0744:
0745: final Iterator operands = phi.operands().iterator();
0746:
0747: while (operands.hasNext()) {
0748: final Expr operand = (Expr) operands.next();
0749:
0750: if (operand instanceof VarExpr) {
0751: if (operand.def() != null) {
0752: phiRelatedUnion(operand.def(), phi.target());
0753: }
0754: }
0755: }
0756: }
0757: }
0758: }
0759:
0760: /**
0761: * A PHI-function (different from a phi-function) is needed whenever
0762: * different values of the same expression reach a common point in the
0763: * program. A PHI is inserted in a block in two different situations:
0764: *
0765: * 1) Place PHI at the expression's iterated dominance frontier (DF+) 2)
0766: * When there is a phi for a variable contained in the expression (this
0767: * indicates an alteration in the expression)
0768: *
0769: * It is only necessary to insert a PHI at a merge point when the expression
0770: * will occur again after that block.
0771: */
0772: private void placePhis(final ExprInfo exprInfo) {
0773: // Place Phis for each expression at the iterated dominance
0774: // frontier of the blocks containing the expression.
0775:
0776: // w contains all of the blocks in which the expression occurs
0777: final ArrayList w = new ArrayList(cfg.size());
0778:
0779: Iterator blocks = cfg.nodes().iterator();
0780:
0781: while (blocks.hasNext()) {
0782: final Block block = (Block) blocks.next();
0783:
0784: if (exprInfo.occurrencesAtBlock(block).size() > 0) {
0785: w.add(block);
0786: }
0787: }
0788:
0789: // The iterated dominance frontier for all of the blocks containing
0790: // the expression. Will ultimately contain all of the places at which
0791: // PHI-function need to be inserted.
0792: final Set df = new HashSet(cfg.iteratedDomFrontier(w));
0793:
0794: // Set of phi functions for the variables in the expression
0795: final ArrayList worklist = new ArrayList();
0796:
0797: // Set of phi functions that have ever been added to the worklist.
0798: // When blocks in the worklist are processed, they are removed.
0799: // inWorklist ensures that a block is not processed more than once.
0800: final Set inWorklist = new HashSet();
0801:
0802: // For each variable occurrence in exprInfo, place a Phi where
0803: // there is a phi for the variable.
0804:
0805: blocks = cfg.nodes().iterator();
0806:
0807: // Iterate over every block in the method and make a worklist of all
0808: // phi functions that define one of the variables in this expression.
0809: while (blocks.hasNext()) {
0810: final Block block = (Block) blocks.next();
0811:
0812: final Iterator e = exprInfo.realsAtBlock(block).iterator();
0813:
0814: while (e.hasNext()) {
0815: final Expr real = (Expr) e.next();
0816:
0817: real.visit(new TreeVisitor() {
0818: public void visitVarExpr(final VarExpr var) {
0819: final Expr def = var.def();
0820:
0821: if (def == null) {
0822: return;
0823: }
0824:
0825: final Node p = def.parent();
0826:
0827: if ((p instanceof PhiStmt)
0828: && !inWorklist.contains(p)) {
0829: worklist.add(p);
0830: inWorklist.add(p);
0831: }
0832: }
0833: });
0834: }
0835: }
0836:
0837: // Go through the worklist and add the blocks containing the
0838: // phi-functions to list of blocks to which to add PHI-functions.
0839: // Also, examine each operand to the phi-function and add it to
0840: // the worklist if it itself is defined by a phi-function.
0841: while (!worklist.isEmpty()) {
0842: final PhiStmt phi = (PhiStmt) worklist.remove(worklist
0843: .size() - 1);
0844: df.add(phi.block());
0845:
0846: final Iterator iter = phi.operands().iterator();
0847:
0848: while (iter.hasNext()) {
0849: final Expr expr = (Expr) iter.next();
0850:
0851: if (expr instanceof VarExpr) {
0852: final VarExpr var = (VarExpr) expr;
0853:
0854: final Expr def = var.def();
0855:
0856: if (def == null) {
0857: continue;
0858: }
0859:
0860: final Node p = def.parent();
0861:
0862: if ((p instanceof PhiStmt)
0863: && !inWorklist.contains(p)) {
0864: worklist.add(p);
0865: inWorklist.add(p);
0866: }
0867: }
0868: }
0869: }
0870:
0871: // df contains all of the blocks in which an PHI-statement for the
0872: // expression should be added. Add them to the exprInfo.
0873: final Iterator iter = df.iterator();
0874:
0875: while (iter.hasNext()) {
0876: final Block block = (Block) iter.next();
0877: exprInfo.addPhi(block);
0878: }
0879: }
0880:
0881: /**
0882: * Rename all occurrences of the expression. placePhis went through the CFG
0883: * and placed PHI-functions at merge blocks in the code. Now, we have to go
0884: * through and assign version numbers to all of the "h" variables generated
0885: * by the PHI-functions.
0886: * <p>
0887: * There are two methods outlined in [Chow 1997]. The first is more
0888: * straightforward (ya right, it took us two days to figure it out) while
0889: * the second is more space efficient. The second method delays the renaming
0890: * of the "h" variables. It makes two passes over the CFG (actually, they
0891: * are preorder traversals of the dominator tree).
0892: * <p>
0893: * The first pass builds a worklist containing all of the real occurrences
0894: * that are defined by a PHI for a given expression. We optimisitically
0895: * assume that versions of PHI operands are the same as the version on top
0896: * of the expression stack. These assumptions are checked for correctness
0897: * during the second pass.
0898: * <p>
0899: * The second pass performs the correct renaming. It relies on seeing a
0900: * later occurrence of the expression. That is, it implies that at the
0901: * earlier PHI, the expression is partially anticipated. The second pass
0902: * operates on all of the real occurrences in the worklist built in the
0903: * first pass. From the versions of the variables at the merge block of a
0904: * PHI, the versions of the variables at each predacessor block are
0905: * determined based on the presence or absence of a phi-function for the at
0906: * that merge block. If the versions are different from the assumed versions
0907: * from the first pass, the operand is rest to null (bottom). Otherwise, the
0908: * operand is correct. If the PHI operand is also defined by a PHI, it is
0909: * added to the worklost and is handled later.
0910: */
0911: // Rename all occurrences of the expression. This is done in two passes.
0912: //
0913: // The first pass assigns version numbers (FUD chain pointers really) in a
0914: // pre-order traversal of the dominator tree and builds the worklist for
0915: // pass 2.
0916: //
0917: // We optimistically assume that a Phi can be used as a definition for a
0918: // real and clean up in pass 2 by adjusting all the FUD chains if the
0919: // assumption proves false.
0920: //
0921: // NOTE: Renaming is where almost all previous PRE bugs have come from, so
0922: // when looking for a bug, it might be good to start looking here first.
0923: private void rename(final ExprInfo exprInfo) {
0924: // Renaming pass 1. This assigns version numbers (FUD chain
0925: // pointers really) in a pre-order traversal of the dominator tree
0926: // and builds the worklist for pass 2.
0927:
0928: final ArrayList renameWorklist = new ArrayList();
0929:
0930: search(cfg.source(), exprInfo, null, null, renameWorklist);
0931:
0932: // Pass 2.
0933:
0934: // First, build another worklist which uses the leaves of the reals
0935: // on the old worklist. We extend this worklist later with the leaves
0936: // factored through var-phis.
0937:
0938: final HashSet seen = new HashSet();
0939:
0940: final LinkedList leavesWorklist = new LinkedList();
0941:
0942: final Iterator iter = renameWorklist.iterator();
0943:
0944: while (iter.hasNext()) {
0945: // Examine each real occurrence that may need more work.
0946: // Construct a list of the operands of the real occurrence. We
0947: // should have already determined that the occurrence is first
0948: // order. So, if we hit anything other than a constant, local
0949: // variable, or stack expression, we have a problem.
0950:
0951: final Expr real = (Expr) iter.next();
0952: final Phi phi = (Phi) exprInfo.def(real);
0953:
0954: // Keep track of operands of the real occurrence.
0955: final ArrayList leaves = new ArrayList();
0956:
0957: real.visitChildren(new TreeVisitor() {
0958: public void visitStoreExpr(final StoreExpr expr) {
0959: // This should have been checked before adding
0960: // the real to the worklist.
0961: throw new RuntimeException();
0962: }
0963:
0964: public void visitConstantExpr(final ConstantExpr expr) {
0965: leaves.add(expr);
0966: }
0967:
0968: public void visitVarExpr(final VarExpr expr) {
0969: leaves.add(expr.def());
0970: }
0971:
0972: public void visitExpr(final Expr expr) {
0973: throw new RuntimeException();
0974: }
0975: });
0976:
0977: // Save the leaves for later use when building phi operands.
0978: phi.setLeaves(leaves);
0979:
0980: leavesWorklist.add(phi);
0981: }
0982:
0983: // Now we actually go about assigning version numbers to the
0984: // operands of the PHI-statement. If the operand is defined by a
0985: // real occurrence (RealDef), examine the children of the real
0986: // occurrence.
0987:
0988: while (!leavesWorklist.isEmpty()) {
0989: final Phi phi = (Phi) leavesWorklist.removeFirst();
0990: phi.setLive(true);
0991:
0992: final List leaves = phi.leaves();
0993:
0994: // Compare the leaves against what we expect for the Phi operands.
0995: final Iterator preds = cfg.preds(phi.block()).iterator();
0996:
0997: PREDS: while (preds.hasNext()) {
0998: final Block pred = (Block) preds.next();
0999: final Def operand = phi.operandAt(pred);
1000:
1001: if (operand instanceof RealDef) {
1002: final Expr expr = ((RealDef) operand).expr;
1003:
1004: final Bool match = new Bool();
1005: match.value = true;
1006:
1007: final Iterator leafIter = leaves.iterator();
1008:
1009: expr.visitChildren(new TreeVisitor() {
1010: public void visitExpr(final Expr expr) {
1011: throw new RuntimeException();
1012: }
1013:
1014: public void visitStoreExpr(final StoreExpr expr) {
1015: expr.target().visit(this );
1016: }
1017:
1018: public void visitConstantExpr(
1019: final ConstantExpr expr) {
1020: visitLeaf(expr);
1021: }
1022:
1023: public void visitVarExpr(final VarExpr expr) {
1024: visitLeaf(expr);
1025: }
1026:
1027: public void visitLeaf(final Expr expr) {
1028: if (!leafIter.hasNext()) {
1029: // We've already examined all of the leaves,
1030: // they
1031: // don't match
1032: match.value = false;
1033: return;
1034: }
1035:
1036: Expr leaf = (Expr) leafIter.next();
1037:
1038: // Factor the leaf through any var-phis there. That
1039: // is,
1040: // If the leaf is defined by a phi-statement, use
1041: // the
1042: // corresponding phi-operand as the leaf. If the
1043: // leaves
1044: // don't match (i.e. are not constants, variables,
1045: // nor
1046: // have the same value number), say so.
1047: if (leaf instanceof VarExpr) {
1048: Assert.isTrue(((VarExpr) leaf).isDef());
1049:
1050: if (leaf.parent() instanceof PhiJoinStmt) {
1051: final PhiJoinStmt leafPhi = (PhiJoinStmt) leaf
1052: .parent();
1053:
1054: if (leafPhi.block() == phi.block()) {
1055: leaf = leafPhi.operandAt(pred);
1056: }
1057: }
1058: }
1059:
1060: if (!(leaf instanceof ConstantExpr)
1061: && !(leaf instanceof VarExpr)) {
1062:
1063: match.value = false;
1064: return;
1065: }
1066:
1067: if (expr.valueNumber() != leaf
1068: .valueNumber()) {
1069: match.value = false;
1070: return;
1071: }
1072: }
1073: });
1074:
1075: if (!match.value || leafIter.hasNext()) {
1076: // If the leaves do not match (or if we didn't get to
1077: // all
1078: // of the leaves), then we have a null PHI-operand
1079: // (bottom) and the operand does not have a real use.
1080: phi.setOperandAt(pred, null);
1081: phi.setHasRealUse(pred, false);
1082: }
1083:
1084: } else if (operand instanceof Phi) {
1085: final ArrayList newLeaves = new ArrayList(leaves
1086: .size());
1087: final Phi opPhi = (Phi) operand;
1088:
1089: final Iterator leafIter = leaves.iterator();
1090:
1091: // If the operand is defined by a PHI-statement,
1092:
1093: LEAVES: while (leafIter.hasNext()) {
1094: Expr leaf = (Expr) leafIter.next();
1095:
1096: // Factor the leaf through a phi.
1097: if (leaf instanceof VarExpr) {
1098: Assert.isTrue(((VarExpr) leaf).isDef());
1099:
1100: if (leaf.parent() instanceof PhiJoinStmt) {
1101: final PhiJoinStmt leafPhi = (PhiJoinStmt) leaf
1102: .parent();
1103:
1104: if (leafPhi.block() == phi.block()) {
1105: leaf = leafPhi.operandAt(pred);
1106: }
1107: }
1108: }
1109:
1110: if (leaf instanceof VarExpr) {
1111: leaf = leaf.def();
1112:
1113: if (leaf.block() == opPhi.block()) {
1114: if (leaf.parent() instanceof PhiJoinStmt) {
1115: newLeaves.add(leaf);
1116: continue LEAVES;
1117: }
1118: } else if (leaf.block().dominates(
1119: opPhi.block())) {
1120: newLeaves.add(leaf);
1121: continue LEAVES;
1122: }
1123: }
1124:
1125: // The leaf is defined after the operand.
1126: phi.setOperandAt(pred, null);
1127: phi.setHasRealUse(pred, false);
1128: continue PREDS;
1129: }
1130:
1131: Assert.isTrue(leaves.size() == newLeaves.size());
1132:
1133: // If we got here, the real only uses leaves defined above
1134: // the operand. Add the operand to the worklist.
1135: final Pair pair = new Pair(phi, opPhi);
1136:
1137: if (!seen.contains(pair)) {
1138: seen.add(pair);
1139: opPhi.setLeaves(newLeaves);
1140: leavesWorklist.add(opPhi);
1141: }
1142: }
1143: }
1144: }
1145:
1146: // Remove the dead phis.
1147: final Iterator blocks = cfg.nodes().iterator();
1148:
1149: while (blocks.hasNext()) {
1150: final Block block = (Block) blocks.next();
1151:
1152: final Phi phi = exprInfo.exprPhiAtBlock(block);
1153:
1154: if ((phi != null) && !phi.live()) {
1155: if (SSAPRE.DEBUG) {
1156: System.out.println(" dead Phi at " + block);
1157: }
1158:
1159: exprInfo.removePhi(block);
1160: }
1161: }
1162: }
1163:
1164: class Pair {
1165: Object a;
1166:
1167: Object b;
1168:
1169: Pair(final Object a, final Object b) {
1170: this .a = a;
1171: this .b = b;
1172: }
1173:
1174: public boolean equals(final Object o) {
1175: return (o instanceof Pair) && ((Pair) o).a.equals(a)
1176: && ((Pair) o).b.equals(b);
1177: }
1178:
1179: public int hashCode() {
1180: return a.hashCode() ^ b.hashCode();
1181: }
1182: }
1183:
1184: /**
1185: * This method performs the first pass of the delayed renaming algorithm.
1186: * Recall that the original renaming algorithm kept a stack for the
1187: * "current" version number of each variable used in the expression being
1188: * renamed. Well, when a real occurrence of the expression is encountered,
1189: * we don't need the stacks because the real occurrence contains the current
1190: * version numbers of the variables. So, we only need the version numbers
1191: * when renaming the "h" variables for PHI-operands.
1192: *
1193: * When this first pass encounters a PHI-operand, it optimistically assumes
1194: * that the version on top of the stack is the correct version. The "h"
1195: * values for real occurrences will be handled correctly.
1196: *
1197: * This implementation represents an occurrences "h" value by its Def (the
1198: * "setDef" method of ExprInfo). This method performs a pre-order traversal
1199: * of the CFG's dominator tree and assigns "names" (actually references to
1200: * Defs) to occurrences of an expression.
1201: *
1202: * The end result of this traversal is a worklist of real occurrences that
1203: * require further renaming. Along the way, we compute the down safety (or
1204: * lack there of) of some PHI-statements.
1205: *
1206: * @param block
1207: * The block in the CFG being traversed
1208: * @param exprInfo
1209: * The expression on which we are performing PRE.
1210: * @param top
1211: * The most recently encountered real occurrence of the
1212: * expression. It can be thought of as the "top" of a stack of
1213: * expressions.
1214: * @param topdef
1215: * top's Def. That is, its "h" value.
1216: */
1217: // This pass is pretty much as described in Chow97 in the Delayed
1218: // Renaming section, except we have to handle kills for access paths
1219: // and for exceptions.
1220: //
1221: // Instead of using an explicit stack of occurrences, top points to
1222: // the occurrence at the top of the stack and topdef points to top's
1223: // def. top is null if topdef is a Phi and a real occurrence hasn't
1224: // followed it. Thus a Phi is not down safe if it is killed and top
1225: // is null.
1226: private void search(final Block block, final ExprInfo exprInfo,
1227: Expr top, Def topdef, final List renameWorklist) {
1228: if (SSAPRE.DEBUG) {
1229: System.out.println(" renaming in " + block);
1230: }
1231:
1232: final Phi phi = exprInfo.exprPhiAtBlock(block);
1233:
1234: // If there's a PHI in the block, make this PHI the new topdef.
1235: //
1236: if (phi != null) {
1237:
1238: top = null;
1239: topdef = phi;
1240:
1241: // If the expression has a stack variable, don't allow any
1242: // hoisting.
1243: //
1244: // To prevent hoisting, it is sufficient to make the phi not
1245: // down safe. If any operand of the phi is null and the phi is
1246: // not down safe, no hoisting will be attempted (see
1247: // canBeAvail). If an operand is non-null, then the expression
1248: // is already evaluated on that path and no hoisting should be
1249: // attempted.
1250:
1251: if (exprInfo.hasStackVariable()) {
1252: phi.setDownSafe(false);
1253: }
1254:
1255: // If the expression can throw an exception, don't allow any
1256: // hoisting. This is stricter than it should be.
1257: //
1258: // We can fix this for fields, divisions, and remainders with
1259: // a trick like: NullCheck(p).f or x / ZeroCheck(y).
1260: //
1261: // Array refs are more complicated since you need both the
1262: // array and the index checked.
1263: //
1264: // Don't bother if exceptions are not precise.
1265:
1266: if (!SSAPRE.NO_PRECISE && exprInfo.hasSideEffects()) {
1267: phi.setDownSafe(false);
1268: }
1269: }
1270:
1271: // If we hit the sink node, a phi at the top of the stack is not
1272: // down safe.
1273: if (block == cfg.sink()) {
1274: if ((topdef instanceof Phi) && (top == null)) {
1275: ((Phi) topdef).setDownSafe(false);
1276: }
1277:
1278: // The sink node has no real occurrences and no children in
1279: // the dominator tree. So, go home.
1280: return;
1281: }
1282:
1283: // Kill (nullify) topdef in catch blocks. This prevents hoisting into
1284: // protected regions.
1285: if (cfg.catchBlocks().contains(block)) {
1286: if ((topdef instanceof Phi) && (top == null)) {
1287: ((Phi) topdef).setDownSafe(false);
1288: }
1289:
1290: if (SSAPRE.DEBUG) {
1291: System.out.println("Top killed at catch " + block);
1292: }
1293:
1294: top = null;
1295: topdef = null;
1296: }
1297:
1298: // Go through all of the real occurrences (and any kills) in the
1299: // block in the order that they appear.
1300: final Iterator e = exprInfo.occurrencesAtBlock(block)
1301: .iterator();
1302:
1303: while (e.hasNext()) {
1304: final Object obj = e.next();
1305:
1306: if (obj instanceof Kill) {
1307: if (topdef != null) {
1308: final Kill kill = (Kill) obj;
1309:
1310: if (SSAPRE.DEBUG) {
1311: System.out.println("Kill " + kill.expr);
1312: }
1313:
1314: boolean die = false;
1315:
1316: // If we have a memory reference (access path), we need to
1317: // check if the Kill could be an alias def for this
1318: // expression.
1319: if (exprInfo.prototype() instanceof MemRefExpr) {
1320: if (kill instanceof MemRefKill) {
1321: final MemRefExpr k = (MemRefExpr) kill.expr;
1322: final MemRefExpr p = (MemRefExpr) exprInfo
1323: .prototype();
1324:
1325: if (kill.expr == null) {
1326: // If kill.expr is null, kill everything.
1327: die = true;
1328:
1329: } else if (TBAA.canAlias(context, k, p)) {
1330: die = true;
1331: }
1332: }
1333: }
1334:
1335: // If we haven't been killed yet, see if the kill is there
1336: // to prevent us from hoisting out of protected regions.
1337: //
1338: // This is possibly not necessary since if the exception
1339: // can be thrown outside the protected region, we won't get
1340: // here in the first place. Removing this code could give
1341: // us better results.
1342: if (!die && exprInfo.hasSideEffects()) {
1343: if (kill instanceof ExceptionKill) {
1344: // Just a kill to keep us from hoisting out of
1345: // a protected region or out of a handler.
1346: die = true;
1347: }
1348: }
1349:
1350: if (die) {
1351: if (SSAPRE.DEBUG) {
1352: System.out.println("Killed");
1353: }
1354:
1355: if ((topdef instanceof Phi) && (top == null)) {
1356: ((Phi) topdef).setDownSafe(false); // Can't use it
1357: }
1358:
1359: top = null;
1360: topdef = null;
1361: }
1362: }
1363:
1364: continue;
1365: }
1366:
1367: // If we get here, we are dealing with a real occurrence of the
1368: // expression. Now we need to determine whether or not the real
1369: // occurrence matches the "h" value (definition) on top of the
1370: // "stack" (topdef).
1371: final Expr real = (Expr) obj;
1372:
1373: // If the real has a store in it, we can't reuse the def at
1374: // the top of stack, even if it is a Phi. Because something
1375: // got redefined inside the expression.
1376: final Bool hasStore = new Bool();
1377:
1378: if (real.isDef()) {
1379: hasStore.value = true;
1380:
1381: } else {
1382: real.visit(new TreeVisitor() {
1383: public void visitStoreExpr(final StoreExpr expr) {
1384: hasStore.value = true;
1385: }
1386:
1387: public void visitExpr(final Expr expr) {
1388: if (!hasStore.value) {
1389: expr.visitChildren(this );
1390: }
1391: }
1392: });
1393: }
1394:
1395: boolean matches = true;
1396:
1397: if (hasStore.value) {
1398: matches = false;
1399:
1400: if (SSAPRE.DEBUG) {
1401: System.out.println("real has store");
1402: }
1403: }
1404:
1405: if (matches && (topdef == null)) {
1406: matches = false;
1407:
1408: if (SSAPRE.DEBUG) {
1409: System.out.println("null topdef");
1410: }
1411: }
1412:
1413: if (matches && (topdef instanceof Phi)) {
1414: if (!matchesPhi(real, (Phi) topdef)) {
1415: // Some variable used in the real got redefined after the
1416: // PHI. So they'll have different values.
1417: matches = false;
1418:
1419: if (SSAPRE.DEBUG) {
1420: System.out
1421: .println("uses var defined after topdef");
1422: }
1423: }
1424: }
1425:
1426: if (matches && (top != null)) {
1427: if (!matches(top, real)) {
1428: matches = false;
1429:
1430: if (SSAPRE.DEBUG) {
1431: System.out.println("mismatch " + top + " != "
1432: + real);
1433: }
1434: }
1435: }
1436:
1437: // If topdef does not match the real occurrence, then make the real
1438: // occurrence the new topdef.
1439: if (!matches) {
1440: if ((top == null) && (topdef instanceof Phi)) {
1441: // No real occurrence after the Phi, so the Phi is not down
1442: // safe.
1443: ((Phi) topdef).setDownSafe(false);
1444: }
1445:
1446: // We know that the real occurrence defines the expression
1447: final RealDef def = new RealDef(real);
1448: exprInfo.setDef(real, def);
1449: topdef = def;
1450:
1451: } else {
1452: // The operands of the real occurrence and the PHI-statement
1453: // match. So, the definition on top of the "stack" defines
1454: // the expression.
1455:
1456: Assert.isTrue(topdef != null);
1457:
1458: if (SSAPRE.DEBUG) {
1459: System.out.println("copying top def");
1460: }
1461:
1462: if (topdef instanceof Phi) {
1463: // If the definition on top of the renaming stack is a
1464: // PHI-statement, the real occurrence may need more work.
1465: // Add it to the renameWorklist.
1466: renameWorklist.add(real);
1467: }
1468:
1469: // Copy the definition from the top of the stack.
1470: exprInfo.setDef(real, topdef);
1471: }
1472:
1473: top = real;
1474: }
1475:
1476: final Iterator succs = cfg.succs(block).iterator();
1477:
1478: // Examine each successor block of the block being traversed. If
1479: // the block contains a PHI-statement, set the PHI-statement's
1480: // operand corresponding to the block being traversed to the
1481: // definition on top of the renaming stack.
1482: while (succs.hasNext()) {
1483: final Block succ = (Block) succs.next();
1484:
1485: // If we hit the sink node, a Phi at the top of the stack is not
1486: // down safe.
1487: if (succ == cfg.sink()) {
1488: if ((top == null) && (topdef instanceof Phi)) {
1489: ((Phi) topdef).setDownSafe(false);
1490: }
1491: }
1492:
1493: final Phi succPhi = exprInfo.exprPhiAtBlock(succ);
1494:
1495: if (succPhi != null) {
1496: succPhi.setOperandAt(block, topdef);
1497:
1498: if (top != null) {
1499: succPhi.setHasRealUse(block, true);
1500: }
1501: }
1502: }
1503:
1504: final Iterator children = cfg.domChildren(block).iterator();
1505:
1506: // Visit each child in the dominator tree.
1507: while (children.hasNext()) {
1508: final Block child = (Block) children.next();
1509: search(child, exprInfo, top, topdef, renameWorklist);
1510: }
1511: }
1512:
1513: /**
1514: * This method determines whether or not a given (real occurrence of an)
1515: * expression has the same operands as the target of a PHI-statement. That
1516: * is, has one of the operands of the real occurrence changed since the the
1517: * PHI-statement?
1518: */
1519: private boolean matchesPhi(final Expr real, final Phi phi) {
1520: final Bool match = new Bool();
1521: match.value = true;
1522:
1523: real.visitChildren(new TreeVisitor() {
1524: public void visitExpr(final Expr expr) {
1525: if (match.value) {
1526: expr.visitChildren(this );
1527: }
1528: }
1529:
1530: public void visitStoreExpr(final StoreExpr expr) {
1531: // A store means a new SSA number, so they won't match
1532: match.value = false;
1533: }
1534:
1535: public void visitVarExpr(final VarExpr expr) {
1536: if (!match.value) {
1537: return;
1538: }
1539:
1540: // We're dealing with one of the operands of the real
1541: // occurrence. If the operand is defined by a phi-statement
1542: // that occurrs in the same block as the PHI-statement, then
1543: // the variable in the real occurrence is the same as that in
1544: // the PHI-statement. Similarly, is the block in which the
1545: // real occurrence's definition occurs dominate the block in
1546: // which the PHI-statement occurs, the two versions of the
1547: // variable are the same. Otherwise the variable has been
1548: // modified between the PHI-statement and the real occurrence.
1549:
1550: final VarExpr def = (VarExpr) expr.def();
1551:
1552: if (def == null) {
1553: match.value = false;
1554: return;
1555: }
1556:
1557: final Block block = phi.block();
1558:
1559: final Node p = def.parent();
1560:
1561: if (block == p.block()) {
1562: // Anything other than a var-phi means the real occurrence
1563: // uses a variable defined after the Phi.
1564: if (p instanceof PhiJoinStmt) {
1565: return;
1566: }
1567:
1568: } else if (p.block().dominates(block)) {
1569: // The real uses a var defined above the phi.
1570: // This, too, is okay.
1571: return;
1572: }
1573:
1574: // The real uses a variable defined after the Phi.
1575: match.value = false;
1576: }
1577: });
1578:
1579: return match.value;
1580: }
1581:
1582: /**
1583: * Compares two expressions and determines whether or not they match.
1584: */
1585: private boolean matches(final Expr expr1, final Expr expr2) {
1586: final LinkedList leaves = new LinkedList();
1587:
1588: expr1.visit(new TreeVisitor() {
1589: public void visitStoreExpr(final StoreExpr expr) {
1590: expr.target().visit(this );
1591: }
1592:
1593: public void visitConstantExpr(final ConstantExpr expr) {
1594: leaves.add(expr);
1595: }
1596:
1597: public void visitVarExpr(final VarExpr expr) {
1598: leaves.add(expr);
1599: }
1600: });
1601:
1602: final Bool match = new Bool();
1603: match.value = true;
1604:
1605: expr2.visit(new TreeVisitor() {
1606: public void visitExpr(final Expr expr) {
1607: if (match.value) {
1608: expr.visitChildren(this );
1609: }
1610: }
1611:
1612: public void visitStoreExpr(final StoreExpr expr) {
1613: if (match.value) {
1614: expr.target().visit(this );
1615: }
1616: }
1617:
1618: public void visitConstantExpr(final ConstantExpr expr) {
1619: visitLeaf(expr);
1620: }
1621:
1622: public void visitVarExpr(final VarExpr expr) {
1623: visitLeaf(expr);
1624: }
1625:
1626: public void visitLeaf(final Expr expr) {
1627: if (leaves.isEmpty()) {
1628: match.value = false;
1629: return;
1630: }
1631:
1632: final Expr leaf = (Expr) leaves.removeFirst();
1633:
1634: if ((leaf == null)
1635: || (expr.valueNumber() != leaf.valueNumber())) {
1636: match.value = false;
1637: }
1638: }
1639: });
1640:
1641: return match.value;
1642: }
1643:
1644: private Expr buildPhiOperand(final ExprInfo exprInfo,
1645: final Phi phi, final Block pred) {
1646: final Iterator leaves = phi.leaves().iterator();
1647:
1648: final Expr expr = (Expr) exprInfo.prototype().clone();
1649:
1650: expr.visit(new TreeVisitor() {
1651: public void visitExpr(final StoreExpr expr) {
1652: throw new RuntimeException();
1653: }
1654:
1655: public void visitConstantExpr(final ConstantExpr expr) {
1656: visitLeaf(expr);
1657: }
1658:
1659: public void visitVarExpr(final VarExpr expr) {
1660: visitLeaf(expr);
1661: }
1662:
1663: public void visitLeaf(final Expr expr) {
1664: if (leaves.hasNext()) {
1665: Expr leaf = (Expr) leaves.next();
1666:
1667: if (leaf instanceof VarExpr) {
1668: Assert.isTrue(((VarExpr) leaf).isDef());
1669:
1670: if (leaf.parent() instanceof PhiJoinStmt) {
1671: final PhiJoinStmt leafPhi = (PhiJoinStmt) leaf
1672: .parent();
1673:
1674: if (leafPhi.block() == phi.block()) {
1675: leaf = leafPhi.operandAt(pred);
1676:
1677: if (leaf instanceof VarExpr) {
1678: leaf = leaf.def();
1679: }
1680: }
1681: }
1682: }
1683:
1684: Assert.isTrue(leaf != null);
1685:
1686: final Expr copy = (Expr) leaf.clone();
1687:
1688: if (leaf.isDef()) {
1689: copy.setDef((VarExpr) leaf);
1690: }
1691:
1692: expr.replaceWith(copy);
1693: } else {
1694: throw new RuntimeException();
1695: }
1696: }
1697: });
1698:
1699: expr.setValueNumber(nextValueNumber++);
1700:
1701: return expr;
1702: }
1703:
1704: /**
1705: * A Phi is not down safe if there is a control flow path from that Phi
1706: * along which the expression is not evaluated before exit or being altered
1707: * by redefinition of one of the variables of the expression. This can
1708: * happen if:
1709: *
1710: * 1) There is a path to exit along which the Phi target is not used. 2)
1711: * There is a path to exit along which the Phi target is used only as the
1712: * operand of a non-down-safe Phi.
1713: */
1714: private void downSafety(final ExprInfo exprInfo) {
1715: final Iterator blocks = cfg.nodes().iterator();
1716:
1717: while (blocks.hasNext()) {
1718: final Block block = (Block) blocks.next();
1719:
1720: final Phi phi = exprInfo.exprPhiAtBlock(block);
1721:
1722: if ((phi == null) || phi.downSafe()) {
1723: continue;
1724: }
1725:
1726: final Iterator e = cfg.preds(block).iterator();
1727:
1728: while (e.hasNext()) {
1729: final Block pred = (Block) e.next();
1730: resetDownSafe(phi, pred);
1731: }
1732: }
1733: }
1734:
1735: private void resetDownSafe(final Phi phi, final Block block) {
1736: if (phi.hasRealUse(block)) {
1737: return;
1738: }
1739:
1740: final Def def = phi.operandAt(block);
1741:
1742: if (def instanceof Phi) {
1743: final Phi phidef = (Phi) def;
1744:
1745: if (phidef.downSafe()) {
1746: phidef.setDownSafe(false);
1747:
1748: if (SSAPRE.DEBUG) {
1749: System.out.println(" def = Phi in "
1750: + phidef.block());
1751: System.out
1752: .println(" def made not down safe");
1753: }
1754:
1755: final Iterator e = cfg.preds(block).iterator();
1756:
1757: while (e.hasNext()) {
1758: final Block pred = (Block) e.next();
1759: resetDownSafe(phidef, pred);
1760: }
1761: }
1762: }
1763: }
1764:
1765: /**
1766: * Determines whether or not a PHI expression is "will be available". Will
1767: * be available determines where we end up placing an evaluation of the
1768: * expression. Will be available = Can be available AND (not Later)
1769: */
1770: private void willBeAvail(final ExprInfo exprInfo) {
1771: computeCanBeAvail(exprInfo);
1772: computeLater(exprInfo);
1773: }
1774:
1775: /**
1776: * Can be available (cba) means "at this point, we can insert an evaluation
1777: * of the expression". If cba = 0, then the PHI-statement is "useless" and
1778: * uses of it are changed to tack (bottom). Can be available depends on the
1779: * down safety of the PHI-statement.
1780: */
1781: private void computeCanBeAvail(final ExprInfo exprInfo) {
1782: final Iterator blocks = cfg.nodes().iterator();
1783:
1784: // Go through every PHI-statement of the exprInfo.
1785: while (blocks.hasNext()) {
1786: final Block block = (Block) blocks.next();
1787:
1788: final Phi phi = exprInfo.exprPhiAtBlock(block);
1789:
1790: if (phi == null) {
1791: continue;
1792: }
1793:
1794: if (!phi.canBeAvail()) {
1795: continue;
1796: }
1797:
1798: if (phi.downSafe()) {
1799: continue;
1800: }
1801:
1802: final Iterator e = cfg.preds(block).iterator();
1803:
1804: // We determined above that:
1805: // 1. This PHI-statement is not down safe
1806: // 2. It is currently can be available
1807: // Now, if one of the PHI-statement's operands is tack (null),
1808: // reset "can be avail" for this PHI-statement.
1809:
1810: while (e.hasNext()) {
1811: final Block pred = (Block) e.next();
1812:
1813: final Def operand = phi.operandAt(pred);
1814:
1815: if (operand == null) {
1816: resetCanBeAvail(exprInfo, phi);
1817: break;
1818: }
1819: }
1820: }
1821: }
1822:
1823: /**
1824: * Resets the cba flag for a given PHI-expression and then iterates over the
1825: * PHI-statement's operands and resets them under certain conditions.
1826: */
1827: private void resetCanBeAvail(final ExprInfo exprInfo, final Phi phi) {
1828: phi.setCanBeAvail(false);
1829:
1830: final Iterator blocks = cfg.nodes().iterator();
1831:
1832: // Iterate over every PHI-statement, other, that uses the
1833: // the "h" defined by phi as an operand...
1834:
1835: while (blocks.hasNext()) {
1836: final Block block = (Block) blocks.next();
1837:
1838: final Phi other = exprInfo.exprPhiAtBlock(block);
1839:
1840: if (other == null) {
1841: continue;
1842: }
1843:
1844: final Iterator e = cfg.preds(block).iterator();
1845:
1846: while (e.hasNext()) {
1847: final Block pred = (Block) e.next();
1848:
1849: final Def operand = other.operandAt(pred);
1850:
1851: // For each use of the "h" defined by exprInfo...
1852: if (operand == phi) {
1853: if (other.hasRealUse(pred)) {
1854: continue;
1855: }
1856:
1857: // If the use does not have a real use, set the use to tack
1858: // (bottom).
1859: other.setOperandAt(pred, null);
1860:
1861: // Since we changed other (by setting one of its operands to
1862: // tack), if other is not down safe, propagate this
1863: // information
1864: // back up the CFG by resetting its cba.
1865: if (!other.downSafe() && other.canBeAvail()) {
1866: resetCanBeAvail(exprInfo, other);
1867: }
1868: }
1869: }
1870: }
1871: }
1872:
1873: /**
1874: * Later basically says, "We cannot place an evaluation of the expression
1875: * any later that this point without adding additional evaluation(s) along
1876: * some path". An expression is "interesting" when later is false.
1877: */
1878: private void computeLater(final ExprInfo exprInfo) {
1879: Iterator blocks = cfg.nodes().iterator();
1880:
1881: // Initialize later to can be available...
1882: while (blocks.hasNext()) {
1883: final Block block = (Block) blocks.next();
1884:
1885: final Phi phi = exprInfo.exprPhiAtBlock(block);
1886:
1887: if (phi == null) {
1888: continue;
1889: }
1890:
1891: phi.setLater(phi.canBeAvail());
1892: }
1893:
1894: blocks = cfg.nodes().iterator();
1895:
1896: // Iterate over each PHI-statement, phi...
1897:
1898: while (blocks.hasNext()) {
1899: final Block block = (Block) blocks.next();
1900:
1901: final Phi phi = exprInfo.exprPhiAtBlock(block);
1902:
1903: if (phi == null) {
1904: continue;
1905: }
1906:
1907: if (!phi.later()) {
1908: continue;
1909: }
1910:
1911: final Iterator e = cfg.preds(block).iterator();
1912:
1913: // If later == true and there is an operand of phi that:
1914: // 1. is not tack
1915: // 2. has a real use
1916: // set later to false and propagate this information back up the
1917: // CFG.
1918: // Basically, what we're saying is that if an operand of the
1919: // PHI-statement has a real use, we want to evaluate the expression
1920: // now.
1921:
1922: while (e.hasNext()) {
1923: final Block pred = (Block) e.next();
1924: final Def operand = phi.operandAt(pred);
1925:
1926: if ((operand != null) && phi.hasRealUse(pred)) {
1927: resetLater(exprInfo, phi);
1928: break;
1929: }
1930: }
1931: }
1932: }
1933:
1934: /**
1935: * Resets later and propagates this information back up the CFG.
1936: */
1937: private void resetLater(final ExprInfo exprInfo, final Phi phi) {
1938: phi.setLater(false);
1939:
1940: final Iterator blocks = cfg.nodes().iterator();
1941:
1942: while (blocks.hasNext()) {
1943: final Block block = (Block) blocks.next();
1944:
1945: final Phi other = exprInfo.exprPhiAtBlock(block);
1946:
1947: if (other == null) {
1948: continue;
1949: }
1950:
1951: final Iterator e = cfg.preds(block).iterator();
1952:
1953: // For PHI-statement that has the "h" defined by phi as an
1954: // operand...
1955:
1956: while (e.hasNext()) {
1957: final Block pred = (Block) e.next();
1958: final Def operand = other.operandAt(pred);
1959:
1960: if (operand == phi) {
1961: if (!other.later()) {
1962: continue;
1963: }
1964:
1965: // Propagate later = false up the CFG.
1966: resetLater(exprInfo, other);
1967: break;
1968: }
1969: }
1970: }
1971: }
1972:
1973: /**
1974: * Finalize is the final step in preparing for the placement of temporaries
1975: * and evaluations of the expression. It decides whether the results of real
1976: * occurrences should be computed on the spot (and saved to a temporary) or
1977: * reloaded from a temporary. Some PHI-statements are removed and some are
1978: * replaced by PHI-statements operating on the temporaries. Additional
1979: * evaluations of the expression may be added where the expression is not
1980: * available.
1981: */
1982: private void finalize(final ExprInfo exprInfo) {
1983: // We assume that all availDef for exprInfo are tack.
1984: // Perform a perorder traversal of the dominance tree. Remember that
1985: // the root of the dominance tree is also the root of the CFG.
1986: finalizeVisit(exprInfo, cfg.source(), null);
1987: }
1988:
1989: /**
1990: *
1991: *
1992: * @param exprInfo
1993: * The expression on which we're performing SSAPRE.
1994: * @param block
1995: * The block to search for occurrences of exprInfo.
1996: * @param top
1997: * Top is used to determine when an element of Avail_def
1998: * dominates a given occurrence.
1999: */
2000: private void finalizeVisit(final ExprInfo exprInfo,
2001: final Block block, Def top) {
2002: if (SSAPRE.DEBUG) {
2003: System.out.println(" finalizing " + block);
2004: }
2005:
2006: // Get the (only) PHI-statement at the current block. If wba = 1 for
2007: // the PHI-statement,
2008: final Phi phi = exprInfo.exprPhiAtBlock(block);
2009:
2010: if (phi != null) {
2011: if (phi.willBeAvail()) {
2012: exprInfo.setAvailDef(phi, phi);
2013: top = phi;
2014: } else {
2015: top = null;
2016: }
2017: }
2018:
2019: final Iterator reals = exprInfo.realsAtBlock(block).iterator();
2020:
2021: // Iterate over all of the real occurrences in the block.
2022:
2023: while (reals.hasNext()) {
2024: final Expr real = (Expr) reals.next();
2025:
2026: if (SSAPRE.DEBUG) {
2027: System.out.println(" -----------");
2028: }
2029:
2030: // Get defining "h" occurrence for the expression
2031: final Def def = exprInfo.def(real);
2032: Assert.isTrue(def != null, real + " is undefined");
2033:
2034: // Get Avail_def[i][x]
2035: final Def availDef = exprInfo.availDef(def);
2036:
2037: // If Avail_def[i][x] == bottom (tack)
2038: // or Avail_def[i][x] does not dominate this occurrence of E[i]
2039: // Avail_def[i][x] = this occurrence of E[i]
2040: //
2041: // The statement (availDef != top) is equivalent to saying "availDef
2042: // does not dominate real". Why is this so? Top essentially keeps
2043: // track of the last PHI-statement we've seen. Thus, top will only
2044: // be changed when we encounter a PHI-statement. We only encounter
2045: // PHI-statements at join blocks, which are obviously not dominated
2046: // by a block (containing availDef) along one of its paths.
2047: if ((availDef == null) || (availDef != top)) {
2048: top = new RealDef(real);
2049: exprInfo.setAvailDef(def, top);
2050: }
2051: // If the available definition is a real occurrence, set its
2052: // save and reload flags
2053: else if (availDef instanceof RealDef) {
2054: exprInfo.setReload(real, true);
2055: exprInfo.setSave(((RealDef) availDef).expr, true);
2056: } else {
2057: Assert.isTrue(availDef instanceof Phi);
2058: exprInfo.setReload(real, true);
2059: }
2060: }
2061:
2062: final Iterator succs = cfg.succs(block).iterator();
2063:
2064: // Iterate over each successor block in the CFG...
2065: while (succs.hasNext()) {
2066: final Block succ = (Block) succs.next();
2067:
2068: final Phi succPhi = exprInfo.exprPhiAtBlock(succ);
2069:
2070: // If the PHI-statement is will be available,
2071: if (succPhi != null) {
2072: if (succPhi.willBeAvail()) {
2073: if (succPhi.canInsert(block)) {
2074: succPhi.setSaveOperand(block, true);
2075: } else {
2076: final Def operand = succPhi.operandAt(block);
2077:
2078: Assert.isTrue(operand != null);
2079:
2080: final Def availDef = exprInfo.availDef(operand);
2081:
2082: if (availDef instanceof RealDef) {
2083: exprInfo.setSave(((RealDef) availDef).expr,
2084: true);
2085: }
2086: }
2087: }
2088: }
2089: }
2090:
2091: final Iterator children = cfg.domChildren(block).iterator();
2092:
2093: while (children.hasNext()) {
2094: final Block child = (Block) children.next();
2095: finalizeVisit(exprInfo, child, top);
2096: }
2097: }
2098:
2099: private void codeMotion(final ExprInfo exprInfo, final VarExpr tmp,
2100: final SSAConstructionInfo consInfo) {
2101: final List[] targets = new List[cfg.size()];
2102:
2103: Iterator blocks = cfg.nodes().iterator();
2104:
2105: while (blocks.hasNext()) {
2106: final Block block = (Block) blocks.next();
2107:
2108: final Phi phi = exprInfo.exprPhiAtBlock(block);
2109:
2110: if (phi != null) {
2111: final Iterator preds = cfg.preds(block).iterator();
2112:
2113: while (preds.hasNext()) {
2114: final Block pred = (Block) preds.next();
2115:
2116: if (!phi.saveOperand(pred)) {
2117: continue;
2118: }
2119:
2120: final Expr operand = buildPhiOperand(exprInfo, phi,
2121: pred);
2122: Assert.isTrue(operand != null);
2123:
2124: final VarExpr t = (VarExpr) tmp.clone();
2125: t.setValueNumber(operand.valueNumber());
2126:
2127: final StoreExpr store = new StoreExpr(t, operand, t
2128: .type());
2129: store.setValueNumber(operand.valueNumber());
2130: pred.tree().addStmtBeforeJump(new ExprStmt(store));
2131:
2132: if (SSAPRE.DEBUG) {
2133: System.out.println("Created new store: "
2134: + store);
2135: }
2136:
2137: // Save the target for later since we need to add
2138: // it to consInfo last.
2139: final int predIndex = cfg.preOrderIndex(pred);
2140:
2141: if (targets[predIndex] == null) {
2142: targets[predIndex] = new ArrayList();
2143: }
2144:
2145: targets[predIndex].add(t);
2146:
2147: if (SSAPRE.DEBUG) {
2148: System.out.println("insert at end of " + pred
2149: + ": " + store);
2150: }
2151: }
2152: }
2153:
2154: final Iterator e = exprInfo.realsAtBlock(block).iterator();
2155:
2156: while (e.hasNext()) {
2157: final Expr real = (Expr) e.next();
2158:
2159: if (exprInfo.save(real)) {
2160: if (!real.isDef()) {
2161: save(exprInfo, tmp, real, consInfo);
2162: } else {
2163: saveTarget(exprInfo, tmp, real, consInfo);
2164: }
2165:
2166: } else if (exprInfo.reload(real)) {
2167: Assert.isFalse(real.isDef(), "Can't reload a def: "
2168: + real + " in " + real.parent());
2169: reload(exprInfo, tmp, real, consInfo);
2170: }
2171: }
2172: }
2173:
2174: blocks = cfg.nodes().iterator();
2175:
2176: while (blocks.hasNext()) {
2177: final Block block = (Block) blocks.next();
2178: final int blockIndex = cfg.preOrderIndex(block);
2179:
2180: if (targets[blockIndex] != null) {
2181: final Iterator iter = targets[blockIndex].iterator();
2182:
2183: while (iter.hasNext()) {
2184: final VarExpr t = (VarExpr) iter.next();
2185: consInfo.addReal(t);
2186: }
2187: }
2188: }
2189: }
2190:
2191: private void save(final ExprInfo exprInfo, final VarExpr tmp,
2192: final Expr real, final SSAConstructionInfo consInfo) {
2193: if (SSAPRE.DEBUG) {
2194: System.out.println("SAVE: " + real + " to " + tmp
2195: + "--------------------------------");
2196: }
2197:
2198: if ((real instanceof CheckExpr) && exprInfo.hasStackVariable()) {
2199: // Check(x) leaves x on the stack. Do nothing.
2200: return;
2201: }
2202:
2203: // Replace expression
2204: // use x + e
2205: // with
2206: // use x + (t := e)
2207: // We must evaluate x before e.
2208:
2209: final Node parent = real.parent();
2210: final VarExpr t = (VarExpr) tmp.clone();
2211: t.setValueNumber(real.valueNumber());
2212:
2213: final StoreExpr store = new StoreExpr(t, real, real.type());
2214: store.setValueNumber(real.valueNumber());
2215: parent.visit(new ReplaceVisitor(real, store));
2216:
2217: consInfo.addReal(t);
2218:
2219: if (SSAPRE.DEBUG) {
2220: System.out
2221: .println("END SAVE--------------------------------");
2222: }
2223: }
2224:
2225: private void reload(final ExprInfo exprInfo, final VarExpr tmp,
2226: final Expr real, final SSAConstructionInfo consInfo) {
2227: if (SSAPRE.DEBUG) {
2228: System.out.println("RELOAD: " + real + " to " + tmp
2229: + "--------------------------------");
2230: }
2231:
2232: Expr t;
2233:
2234: if ((real instanceof CheckExpr) && exprInfo.hasStackVariable()) {
2235: // Check(x) leaves x on the stack. Replace with just x.
2236:
2237: t = ((CheckExpr) real).expr();
2238: real.parent().visit(new ReplaceVisitor(real, t));
2239: real.cleanupOnly();
2240:
2241: } else {
2242: // Replace
2243: // use e
2244: // with
2245: // use t
2246:
2247: t = (VarExpr) tmp.clone();
2248: t.setValueNumber(real.valueNumber());
2249: real.replaceWith(t);
2250:
2251: consInfo.addReal((VarExpr) t);
2252: }
2253:
2254: if (SSAPRE.DEBUG) {
2255: System.out.println("reload t " + t + " in " + t.parent());
2256: }
2257:
2258: if (SSAPRE.DEBUG) {
2259: System.out
2260: .println("END RELOAD--------------------------------");
2261: }
2262: }
2263:
2264: private void saveTarget(final ExprInfo exprInfo, final VarExpr tmp,
2265: final Expr real, final SSAConstructionInfo consInfo) {
2266: if (SSAPRE.DEBUG) {
2267: System.out.println("SAVE TARGET: " + real + " to " + tmp
2268: + "--------------------------------");
2269: }
2270:
2271: Assert.isTrue(real instanceof MemRefExpr);
2272:
2273: // Replace
2274: // a.b := c
2275: // with:
2276: // a.b := (t := c);
2277:
2278: final VarExpr t = (VarExpr) tmp.clone();
2279: t.setValueNumber(real.valueNumber());
2280:
2281: final StoreExpr store = (StoreExpr) real.parent();
2282: final Expr rhs = store.expr();
2283:
2284: final StoreExpr rhsStore = new StoreExpr(t, rhs, rhs.type());
2285: rhsStore.setValueNumber(real.valueNumber());
2286: store.visit(new ReplaceVisitor(rhs, rhsStore));
2287:
2288: consInfo.addReal(t);
2289:
2290: if (SSAPRE.DEBUG) {
2291: System.out.println("save target " + store);
2292: }
2293:
2294: if (SSAPRE.DEBUG) {
2295: System.out
2296: .println("END SAVE TARGET------------------------------");
2297: }
2298: }
2299:
2300: /**
2301: * Returns whether or not an expression is first-order. A first-order
2302: * expression has only one operator. For example, a+b is first-order.
2303: */
2304: boolean isFirstOrder(final Expr expr) {
2305: final FirstOrderChecker f = new FirstOrderChecker();
2306: expr.visit(f);
2307: return f.firstOrder;
2308: }
2309:
2310: /**
2311: * FirstOrderChecker is a TreeVistor that traverses an expression tree and
2312: * determines whether or not it is first order. A first order expression
2313: * Override all visitXXXExpr methods so that they do not visit children. We
2314: * only want to check the expr we first visit.
2315: */
2316: private final class FirstOrderChecker extends TreeVisitor {
2317: boolean firstOrder = false;
2318:
2319: public void visitExpr(final Expr expr) {
2320: }
2321:
2322: /**
2323: * A leaf in the expression tree consists of an expression that only
2324: * references local variables, or an expression that is a constant, or
2325: * an expressions that stores into a local variable.
2326: */
2327: private boolean isLeaf(final Expr expr) {
2328: if (expr instanceof StoreExpr) {
2329: return ((StoreExpr) expr).target() instanceof LocalExpr;
2330: }
2331:
2332: return (expr instanceof LocalExpr)
2333: || (expr instanceof ConstantExpr);
2334: }
2335:
2336: public void visitCheckExpr(final CheckExpr expr) {
2337: // UGLY: We special case RC and UC to allow stack variables since
2338: // they do not change the operand stack at all. However, since
2339: // they do contain stack variables, we cannot hoist these
2340: // expressions, but we can one eliminate them so long as they
2341: // are replaced with stack variables rather than locals.
2342:
2343: if (isLeaf(expr.expr())
2344: || (expr.expr() instanceof StackExpr)) {
2345: firstOrder = true;
2346: }
2347: }
2348:
2349: /**
2350: * An arithmetic expression is first-order if both its left and right
2351: * operands are leaves.
2352: */
2353: public void visitArithExpr(final ArithExpr expr) {
2354: if (isLeaf(expr.left()) && isLeaf(expr.right())) {
2355: firstOrder = true;
2356: }
2357: }
2358:
2359: /**
2360: * An ArrayLengthExpr is first-order when the array whose length is
2361: * being taken is expressed as a leaf.
2362: */
2363: public void visitArrayLengthExpr(final ArrayLengthExpr expr) {
2364: if (isLeaf(expr.array())) {
2365: firstOrder = true;
2366: }
2367: }
2368:
2369: /**
2370: * An ArrayRefExpr is first order when both the array it references and
2371: * the index used to reference it are expressed as leaves.
2372: */
2373: public void visitArrayRefExpr(final ArrayRefExpr expr) {
2374: if (SSAPRE.NO_ACCESS_PATHS) {
2375: return;
2376: }
2377:
2378: if (isLeaf(expr.array()) && isLeaf(expr.index())) {
2379: firstOrder = true;
2380: }
2381: }
2382:
2383: public void visitCastExpr(final CastExpr expr) {
2384: if (isLeaf(expr.expr())) {
2385: firstOrder = true;
2386: }
2387: }
2388:
2389: /**
2390: * If a field is volatile (meaning that a field may be changed by other
2391: * threads), a reference to it is not first order. I'm not too sure why
2392: * this makes any difference.
2393: */
2394: public void visitFieldExpr(final FieldExpr expr) {
2395: if (SSAPRE.NO_ACCESS_PATHS) {
2396: return;
2397: }
2398:
2399: if (isLeaf(expr.object())) {
2400: try {
2401: final FieldEditor e = context.editField(expr
2402: .field());
2403:
2404: if (!e.isVolatile()) {
2405: firstOrder = true;
2406: }
2407:
2408: context.release(e.fieldInfo());
2409:
2410: } catch (final NoSuchFieldException e) {
2411: // A field wasn't found. Silently assume it's volatile.
2412: firstOrder = false;
2413: }
2414: }
2415: }
2416:
2417: public void visitInstanceOfExpr(final InstanceOfExpr expr) {
2418: if (isLeaf(expr.expr())) {
2419: firstOrder = true;
2420: }
2421: }
2422:
2423: public void visitNegExpr(final NegExpr expr) {
2424: if (isLeaf(expr.expr())) {
2425: firstOrder = true;
2426: }
2427: }
2428:
2429: public void visitShiftExpr(final ShiftExpr expr) {
2430: if (isLeaf(expr.expr()) && isLeaf(expr.bits())) {
2431: firstOrder = true;
2432: }
2433: }
2434:
2435: /**
2436: * Once again, an expression that references a volatile static field is
2437: * not first-order.
2438: *
2439: * @see #visitFieldExpr
2440: */
2441: public void visitStaticFieldExpr(final StaticFieldExpr expr) {
2442: if (SSAPRE.NO_ACCESS_PATHS) {
2443: return;
2444: }
2445:
2446: try {
2447: final FieldEditor e = context.editField(expr.field());
2448:
2449: if (!e.isVolatile()) {
2450: firstOrder = true;
2451: }
2452:
2453: context.release(e.fieldInfo());
2454:
2455: } catch (final NoSuchFieldException e) {
2456: // A field wasn't found. Silently assume it's volatile.
2457: firstOrder = false;
2458: }
2459: }
2460: }
2461:
2462: /**
2463: * Wrapper classes that are used to simulate pass-by-reference. That is,
2464: * their values are changed inside methods. When used as parameters they
2465: * must be declared as being final.
2466: */
2467: class Int {
2468: int value = 0;
2469: }
2470:
2471: class Bool {
2472: boolean value = false;
2473: }
2474:
2475: int next = 0;
2476:
2477: /**
2478: * Def represents a point at which a variable is defined. Each definition
2479: * has a version number associated with it.
2480: */
2481: abstract class Def {
2482: int version = next++;
2483: }
2484:
2485: /**
2486: * RealDef represents a real occurrence of an expression.
2487: */
2488: class RealDef extends Def {
2489: Expr expr;
2490:
2491: public RealDef(final Expr expr) {
2492: this .expr = expr;
2493: }
2494:
2495: public String toString() {
2496: return "[" + expr + "]_" + version;
2497: }
2498: }
2499:
2500: /**
2501: * Phi represents a PHI-statement (PHI-function) for merging an expression
2502: * along two paths.
2503: * <p>
2504: * Information about the operands to PHI-statements is maintained in the PHI
2505: * class.
2506: * <p>
2507: * A PHI-statement has the form: h = PHI(h, h)
2508: *
2509: * @see #operands
2510: */
2511: class Phi extends Def {
2512: Block block; // Block in which the PHI-statement occurs
2513:
2514: // Note that arrays are indexed by a block's preorder number.
2515:
2516: Def[] operands; // Operand to the PHI-statement
2517:
2518: boolean[] hasRealUse; // Is the ith operand a real use?
2519:
2520: boolean[] saveOperand;
2521:
2522: boolean downSafe; // downsafe flag (ds)
2523:
2524: boolean canBeAvail; // can_be_available (cba)
2525:
2526: boolean later; // later flag (later)
2527:
2528: boolean live;
2529:
2530: List leaves;
2531:
2532: /**
2533: * Constructor.
2534: *
2535: * @param exprInfo
2536: * The expression that this PHI-statement is associated with.
2537: * @param block
2538: * The block in which this PHI-statement occurs. Note that an
2539: * PHI-statement can only occur in one block.
2540: */
2541: public Phi(final ExprInfo exprInfo, final Block block) {
2542: this .block = block;
2543:
2544: final int size = cfg.size();
2545:
2546: operands = new Def[size];
2547: hasRealUse = new boolean[size];
2548: saveOperand = new boolean[size];
2549:
2550: leaves = null;
2551:
2552: downSafe = true; // Initially, ds = 1
2553: canBeAvail = true; // Initially, cba = 1
2554: later = true; // Initially, later = cba
2555: live = false; // Initially, live = 0
2556: }
2557:
2558: /**
2559: * Returns the block in which this PHI-statement is occurs.
2560: */
2561: public Block block() {
2562: return block;
2563: }
2564:
2565: /**
2566: * Sets the operands to a real occurrence of the expression. Leaves only
2567: * apply to PHI-statements that are associated with a real occurrence of
2568: * the expression.
2569: */
2570: public void setLeaves(final List leaves) {
2571: if (SSAPRE.DEBUG) {
2572: System.out.println("setting leaves of " + this + " to "
2573: + leaves);
2574: }
2575:
2576: this .leaves = new ArrayList(leaves);
2577: }
2578:
2579: /**
2580: * Returns the operands to the real occurrence represented by this
2581: * PHI-statement. It is assumed that this PHI-statement represents a
2582: * real occurrence.
2583: */
2584: public List leaves() {
2585: Assert.isTrue(leaves != null);
2586:
2587: final Iterator iter = leaves.iterator();
2588:
2589: while (iter.hasNext()) {
2590: final Expr e = (Expr) iter.next();
2591: Assert.isTrue((e instanceof VarExpr)
2592: || (e instanceof ConstantExpr), "not a leaf: "
2593: + e);
2594: }
2595:
2596: return leaves;
2597: }
2598:
2599: /**
2600: * Returns the operands of the PHI-statement. This is just a list of all
2601: * of the block's predacessors.
2602: */
2603: public Collection operands() {
2604: final LinkedList v = new LinkedList();
2605:
2606: final Iterator preds = cfg.preds(block).iterator();
2607:
2608: while (preds.hasNext()) {
2609: final Block pred = (Block) preds.next();
2610: v.addFirst(operandAt(pred));
2611: }
2612:
2613: return v;
2614: }
2615:
2616: /**
2617: * Sets an operand of this PHI-statement. Recall that PHI-operands are
2618: * associated with a predacessor block of the block in which the
2619: * PHI-statement resides.
2620: *
2621: * @param block
2622: * The block associated with the operand.
2623: * @param def
2624: * The PHI-definition that is the operand.
2625: */
2626: public void setOperandAt(final Block block, final Def def) {
2627: final int blockIndex = cfg.preOrderIndex(block);
2628: operands[blockIndex] = def;
2629:
2630: if (SSAPRE.DEBUG) {
2631: System.out.println(this );
2632: }
2633: }
2634:
2635: /**
2636: * Returns the PHI-operand of this PHI-statement associated with a given
2637: * block. Recall that PHI-operands are associated with a predacessor
2638: * block of the block in which the PHI-statement resides.
2639: */
2640: public Def operandAt(final Block block) {
2641: final int blockIndex = cfg.preOrderIndex(block);
2642: return operands[blockIndex];
2643: }
2644:
2645: /**
2646: * Sets the "has real use" flag.
2647: */
2648: public void setHasRealUse(final Block block, final boolean flag) {
2649: final int blockIndex = cfg.preOrderIndex(block);
2650:
2651: hasRealUse[blockIndex] = flag;
2652:
2653: if (SSAPRE.DEBUG) {
2654: System.out.println(this );
2655: }
2656: }
2657:
2658: public boolean hasRealUse(final Block block) {
2659: final int blockIndex = cfg.preOrderIndex(block);
2660: return hasRealUse[blockIndex];
2661: }
2662:
2663: /**
2664: *
2665: */
2666: public void setSaveOperand(final Block block, final boolean flag) {
2667: final int blockIndex = cfg.preOrderIndex(block);
2668: saveOperand[blockIndex] = flag;
2669:
2670: if (SSAPRE.DEBUG) {
2671: System.out.println(this );
2672: }
2673: }
2674:
2675: public boolean saveOperand(final Block block) {
2676: final int blockIndex = cfg.preOrderIndex(block);
2677: return saveOperand[blockIndex];
2678: }
2679:
2680: /**
2681: * Determines whether or not a PHI-operand satisfies "insert". For
2682: * insert to hold, the following conditions must be met: 1. The
2683: * PHI-statement is "will be available" 2. The PHI-operand is tack
2684: * (null), or "has real use" is false and the operand is defined by an
2685: * PHI-statement that does not satisfy "will be available".
2686: *
2687: * @param block
2688: * The block with which a desired operand is associated with.
2689: * Recall that PHI-operands are associated with the block
2690: * that is a predacessor of the block in which they are
2691: * contained.
2692: */
2693: public boolean canInsert(final Block block) {
2694: final int blockIndex = cfg.preOrderIndex(block);
2695:
2696: final Def def = operands[blockIndex];
2697:
2698: if (def == null) {
2699: return true;
2700: }
2701:
2702: if (!hasRealUse[blockIndex]) {
2703: if (def instanceof Phi) {
2704: final Phi phi = (Phi) def;
2705:
2706: if (!phi.willBeAvail()) {
2707: return true;
2708: }
2709: }
2710: }
2711:
2712: return false;
2713: }
2714:
2715: /**
2716: * Returns whether or not an PHI-statement satisfies "will be
2717: * available". "Will be available" is used to determine the locations in
2718: * which to insert evaluations of the expression in the finalize() pass.
2719: * <p>
2720: * willBeAvail = canBeAvail && !later
2721: *
2722: * @see #finalize()
2723: */
2724: public boolean willBeAvail() {
2725: // WBA => CBA => DS
2726: return canBeAvail && !later;
2727: }
2728:
2729: /**
2730: * Sets the "can be available" flag.
2731: */
2732: public void setCanBeAvail(final boolean flag) {
2733: canBeAvail = flag;
2734:
2735: if (SSAPRE.DEBUG) {
2736: System.out.println(this );
2737: }
2738: }
2739:
2740: /**
2741: * Returns the "can be available" flag.
2742: */
2743: public boolean canBeAvail() {
2744: return canBeAvail;
2745: }
2746:
2747: /**
2748: * Sets the "later" flag. If the later flag is false, it means that an
2749: * evaluation of the expression may not be placed at any point below
2750: * this PHI-statement without introducing a useless computation along
2751: * some path.
2752: */
2753: public void setLater(final boolean flag) {
2754: later = flag;
2755:
2756: if (SSAPRE.DEBUG) {
2757: System.out.println(this );
2758: }
2759: }
2760:
2761: /**
2762: * Returns the "later" flag.
2763: *
2764: * @see #setLater
2765: */
2766: public boolean later() {
2767: return later;
2768: }
2769:
2770: public void setLive(final boolean flag) {
2771: live = flag;
2772: }
2773:
2774: public boolean live() {
2775: return live;
2776: }
2777:
2778: /**
2779: * Sets the "down-safe" flag. An PHI-statement is "down-safe" if there
2780: * is no path from the PHI-statement to the exit block that does not
2781: * recalculate the expression. If an PHI-statement is "down-safe" it is
2782: * worthwhile to attempt to hoist it up higher in the program.
2783: * <p>
2784: * An PHI-statement is not "down-safe" when a) There is a path to exit
2785: * along which the PHI-statement result is never used. b) There is a
2786: * path to exit along which the only used of the result of the
2787: * PHI-statement is an operand of an PHI-statement which itself is not
2788: * "down-safe".
2789: */
2790: public void setDownSafe(final boolean flag) {
2791: downSafe = flag;
2792:
2793: if (SSAPRE.DEBUG) {
2794: System.out.println(this );
2795: }
2796: }
2797:
2798: /**
2799: * Returns whether or not this PHI-statement is "down-safe".
2800: *
2801: * @see #setDownSafe
2802: */
2803: public boolean downSafe() {
2804: return downSafe;
2805: }
2806:
2807: /**
2808: * Returns a textual representation of this PHI-statement.
2809: */
2810: public String toString() {
2811: String s = "Phi_" + version + "[";
2812:
2813: if (!downSafe) {
2814: s += "!";
2815: }
2816:
2817: s += "DS,";
2818:
2819: if (!canBeAvail) {
2820: s += "!";
2821: }
2822:
2823: s += "CBA,";
2824:
2825: if (!later) {
2826: s += "!";
2827: }
2828:
2829: s += "later](";
2830:
2831: if (operands != null) {
2832: final Iterator e = cfg.preds(block).iterator();
2833:
2834: while (e.hasNext()) {
2835: final Block pred = (Block) e.next();
2836: final int predIndex = cfg.preOrderIndex(pred);
2837:
2838: s += pred.label() + "=";
2839:
2840: final Def operand = operands[predIndex];
2841:
2842: if (operand == null) {
2843: s += "undef[";
2844: } else {
2845: s += operand.version + "[";
2846: }
2847:
2848: if (!hasRealUse[predIndex]) {
2849: s += "!";
2850: }
2851:
2852: s += "HRU,";
2853:
2854: if (!saveOperand[predIndex]) {
2855: s += "!";
2856: }
2857:
2858: s += "save,";
2859:
2860: if (!canInsert(pred)) {
2861: s += "!";
2862: }
2863:
2864: s += "insert]";
2865:
2866: if (e.hasNext()) {
2867: s += ", ";
2868: }
2869: }
2870: }
2871:
2872: s += ")";
2873:
2874: return s;
2875: }
2876: }
2877:
2878: /**
2879: * ExprInfo represents an expression that we are performing SSA-based PRE
2880: * on. An occurrence of an expression can take one of three forms: 1) A real
2881: * occurrence of an expression (h = a+b) 2) A (target of a) PHI function (h =
2882: * PHI(...)) 3) An operand to a PHI function (PHI(h, ...))
2883: *
2884: * The occurrences of an expression are ordered according to a preorder
2885: * traversal of the CFG.
2886: *
2887: */
2888: private final class ExprInfo {
2889: ExprKey key; // A unique key for an Expr instance
2890:
2891: private int numUses; // Number of uses (not defs) of this expr
2892:
2893: private List[] reals; // The real occurrences of this expression
2894:
2895: private boolean[] realsSorted; // Are the reals at a given block
2896: // sorted?
2897:
2898: private Phi[] phis; // PHI expressions for this occurrences
2899:
2900: Map defs; // Maps an Expr to its defining occurrence
2901:
2902: // "h" in the CFG.
2903: Map availDefs; //
2904:
2905: Map saves;
2906:
2907: Map reloads;
2908:
2909: private Expr prototype; // The actual expression being represented
2910:
2911: private boolean isFinal; // Does the expression access a final field?
2912:
2913: private boolean hasSideEffects;
2914:
2915: private boolean hasStackVariable;
2916:
2917: /**
2918: * Constructor.
2919: *
2920: * @param expr
2921: * The expression (real occurrence) represented by this
2922: * ExprInfo.
2923: * @param key
2924: * A unique key by which this expression can be identified.
2925: */
2926: public ExprInfo(final Expr expr, final ExprKey key) {
2927: this .key = key;
2928:
2929: prototype = (Expr) expr.clone();
2930:
2931: // Clean up the expression's children (remember that expr's children
2932: // are also cloned, so we aren't changing the tree).
2933: prototype.visitChildren(new TreeVisitor() {
2934: public void visitStoreExpr(final StoreExpr expr) {
2935: expr.target().setDef(null);
2936: expr.target().setParent(null);
2937: expr.replaceWith(expr.target(), false);
2938: expr.cleanupOnly();
2939: expr.expr().cleanup();
2940: }
2941:
2942: public void visitVarExpr(final VarExpr expr) {
2943: expr.setDef(null);
2944: }
2945:
2946: public void visitConstantExpr(final ConstantExpr expr) {
2947: }
2948:
2949: // The prototype expression should only
2950: // contain StoreExpr, VarExpr, or
2951: // ConstantExpr...
2952: public void visitExpr(final Expr expr) {
2953: throw new RuntimeException();
2954: }
2955: });
2956:
2957: numUses = 0;
2958:
2959: reals = new ArrayList[cfg.size()];
2960: realsSorted = new boolean[cfg.size()];
2961:
2962: for (int i = 0; i < reals.length; i++) {
2963: reals[i] = new ArrayList();
2964: realsSorted[i] = false;
2965: }
2966:
2967: phis = new Phi[cfg.size()];
2968:
2969: defs = new HashMap();
2970: availDefs = new HashMap();
2971: saves = new HashMap();
2972: reloads = new HashMap();
2973:
2974: if (prototype instanceof MemRefExpr) {
2975: // Traverse the tree and determine whether expr accesses a final
2976: // field.
2977: final FinalChecker fch = new FinalChecker();
2978: prototype.visit(fch);
2979: isFinal = fch.isFinal;
2980:
2981: } else {
2982: isFinal = true;
2983: }
2984:
2985: // For PRE, RCs, UCs, stores, and possible reassignment
2986: // through aliases are not considered side effects.
2987: sideEffects.reset();
2988: prototype.visit(sideEffects);
2989:
2990: int flag = sideEffects.sideEffects();
2991: flag &= ~SideEffectChecker.STORE;
2992: flag &= ~SideEffectChecker.ALIAS;
2993: flag &= ~SideEffectChecker.RC;
2994: flag &= ~SideEffectChecker.UC;
2995: hasSideEffects = flag != 0;
2996:
2997: // Special case: allow RC(S) and UC(S).
2998: if ((flag & SideEffectChecker.STACK) != 0) {
2999: Assert.isTrue(prototype instanceof CheckExpr);
3000: hasStackVariable = true;
3001: }
3002: }
3003:
3004: public boolean hasStackVariable() {
3005: return hasStackVariable;
3006: }
3007:
3008: public boolean hasSideEffects() {
3009: return hasSideEffects;
3010: }
3011:
3012: public int numUses() {
3013: return numUses;
3014: }
3015:
3016: public void cleanup() {
3017: reals = null;
3018: phis = null;
3019: saves = null;
3020: reloads = null;
3021: defs = null;
3022: availDefs = null;
3023: prototype = null;
3024: }
3025:
3026: // Reload is used in finalize
3027: public void setReload(final Expr expr, final boolean flag) {
3028: if (SSAPRE.DEBUG) {
3029: System.out.println(" setting reload for " + expr
3030: + " to " + flag);
3031: }
3032:
3033: reloads.put(expr, new Boolean(flag));
3034: }
3035:
3036: public boolean reload(final Expr expr) {
3037: final Boolean flag = (Boolean) reloads.get(expr);
3038: return (flag != null) && flag.booleanValue();
3039: }
3040:
3041: // Save is used in finalize
3042: public void setSave(final Expr expr, final boolean flag) {
3043: if (SSAPRE.DEBUG) {
3044: System.out.println(" setting save for " + expr
3045: + " to " + flag);
3046: }
3047:
3048: saves.put(expr, new Boolean(flag));
3049: }
3050:
3051: public boolean save(final Expr expr) {
3052: final Boolean flag = (Boolean) saves.get(expr);
3053: return (flag != null) && flag.booleanValue();
3054: }
3055:
3056: // AvailDef is used in finalize
3057: public void setAvailDef(final Def def, final Def availDef) {
3058: if (SSAPRE.DEBUG) {
3059: System.out.println(" setting avail def for "
3060: + def + " to " + availDef);
3061: }
3062:
3063: availDefs.put(def, availDef);
3064: }
3065:
3066: public Def availDef(final Def def) {
3067: final Def availDef = (Def) availDefs.get(def);
3068:
3069: if (SSAPRE.DEBUG) {
3070: System.out.println(" avail def for " + def
3071: + " is " + availDef);
3072: }
3073:
3074: return availDef;
3075: }
3076:
3077: /**
3078: * Sets the defining occurrence (the "h") of a given real occurrence.
3079: */
3080: public void setDef(final Expr expr, final Def def) {
3081: if (SSAPRE.DEBUG) {
3082: System.out.println(" setting def for " + expr
3083: + " to " + def);
3084: }
3085:
3086: if (def != null) {
3087: defs.put(expr, def);
3088: } else {
3089: defs.remove(expr);
3090: }
3091: }
3092:
3093: /**
3094: * Returns the Def (either a ReafDef or Phi) defining a given occurrence
3095: * of the expression modeled by this ExprInfo.
3096: */
3097: public Def def(final Expr expr) {
3098: final Def def = (Def) defs.get(expr);
3099:
3100: if (SSAPRE.DEBUG) {
3101: System.out.println(" def for " + expr + " is "
3102: + def);
3103: }
3104:
3105: return def;
3106: }
3107:
3108: public Expr prototype() {
3109: return prototype;
3110: }
3111:
3112: /**
3113: * Notifies this ExprInfo of the existence of another real occurrence of
3114: * the expression.
3115: */
3116: public void addReal(final Expr real) {
3117: if (!real.isDef()) {
3118: numUses++;
3119: }
3120:
3121: final int blockIndex = cfg.preOrderIndex(real.block());
3122: reals[blockIndex].add(real);
3123: realsSorted[blockIndex] = false;
3124: }
3125:
3126: /**
3127: * Notifies this ExprInfo of the existence of an PHI-statement for this
3128: * expression. If the PHI is not already present, a new Phi instance is
3129: * created for it and placed in the phis array.
3130: *
3131: * @param block
3132: * The block at which the PHI occurs.
3133: */
3134: public void addPhi(final Block block) {
3135: final int blockIndex = cfg.preOrderIndex(block);
3136:
3137: if (phis[blockIndex] == null) {
3138: if (SSAPRE.DEBUG) {
3139: System.out.println(" add phi for " + prototype
3140: + " at " + block);
3141: }
3142:
3143: phis[blockIndex] = new Phi(this , block);
3144: }
3145: }
3146:
3147: /**
3148: * Removes a PHI occurrence from the phis array.
3149: */
3150: public void removePhi(final Block block) {
3151: final int blockIndex = cfg.preOrderIndex(block);
3152: phis[blockIndex] = null;
3153: }
3154:
3155: /**
3156: * Returns the PHI occurrence for this expression at a given Block in
3157: * the code.
3158: */
3159: public Phi exprPhiAtBlock(final Block block) {
3160: final int blockIndex = cfg.preOrderIndex(block);
3161: return phis[blockIndex];
3162: }
3163:
3164: /**
3165: * Returns the real occurrences of this expression at a given Block in
3166: * the code.
3167: */
3168: public List realsAtBlock(final Block block) {
3169: final int blockIndex = cfg.preOrderIndex(block);
3170:
3171: final List r = reals[blockIndex];
3172:
3173: if (!realsSorted[blockIndex]) {
3174: sortExprs(r);
3175: realsSorted[blockIndex] = true;
3176: }
3177:
3178: return r;
3179: }
3180:
3181: /**
3182: * Returns a List of the real occurrences of the expression and any Kill
3183: * expressions contained in a given Block in the code.
3184: */
3185: public List occurrencesAtBlock(final Block block) {
3186: if (isFinal && !hasSideEffects) {
3187: return realsAtBlock(block);
3188: }
3189:
3190: final int blockIndex = cfg.preOrderIndex(block);
3191:
3192: final List a = kills[blockIndex];
3193: final List r = reals[blockIndex];
3194:
3195: if (!killsSorted[blockIndex]) {
3196: sortKills(a);
3197: killsSorted[blockIndex] = true;
3198: }
3199:
3200: if (!realsSorted[blockIndex]) {
3201: sortExprs(r);
3202: realsSorted[blockIndex] = true;
3203: }
3204:
3205: // return a list that is essentially a combination of the
3206: // real occurrences and the kill expressions
3207: return new AbstractList() {
3208: public int size() {
3209: return r.size() + a.size();
3210: }
3211:
3212: public boolean contains(final Object obj) {
3213: if (obj instanceof Kill) {
3214: return a.contains(obj);
3215: } else if (obj instanceof Expr) {
3216: return r.contains(obj);
3217: }
3218:
3219: return false;
3220: }
3221:
3222: public Object get(final int index) {
3223: throw new UnsupportedOperationException();
3224: }
3225:
3226: public Iterator iterator() {
3227: return new Iterator() {
3228: Iterator aiter;
3229:
3230: Iterator riter;
3231:
3232: Kill anext;
3233:
3234: Expr rnext;
3235:
3236: {
3237: aiter = a.iterator();
3238: riter = r.iterator();
3239:
3240: if (aiter.hasNext()) {
3241: anext = (Kill) aiter.next();
3242: } else {
3243: anext = null;
3244: }
3245:
3246: if (riter.hasNext()) {
3247: rnext = (Expr) riter.next();
3248: } else {
3249: rnext = null;
3250: }
3251: }
3252:
3253: public boolean hasNext() {
3254: return (anext != null) || (rnext != null);
3255: }
3256:
3257: public Object next() {
3258: boolean real = false;
3259:
3260: if (anext == null) {
3261: if (rnext == null) {
3262: throw new NoSuchElementException();
3263: }
3264:
3265: real = true;
3266:
3267: } else if (rnext == null) {
3268: real = false;
3269:
3270: } else {
3271: // Kills go first if keys are equal.
3272: if (anext.key() <= rnext.key()) {
3273: real = false;
3274: } else {
3275: real = true;
3276: }
3277: }
3278:
3279: if (real) {
3280: final Object t = rnext;
3281:
3282: if (riter.hasNext()) {
3283: rnext = (Expr) riter.next();
3284: } else {
3285: rnext = null;
3286: }
3287:
3288: return t;
3289:
3290: } else {
3291: final Object t = anext;
3292:
3293: if (aiter.hasNext()) {
3294: anext = (Kill) aiter.next();
3295: } else {
3296: anext = null;
3297: }
3298:
3299: return t;
3300: }
3301: }
3302:
3303: public void remove() {
3304: throw new UnsupportedOperationException();
3305: }
3306: };
3307: }
3308:
3309: public ListIterator listIterator() {
3310: throw new UnsupportedOperationException();
3311: }
3312: };
3313: } // end occurrencesAtBlock()
3314:
3315: /**
3316: * Sort a list of expressions into preorder.
3317: *
3318: * Recall that the key of each occurrence node was set to its preorder
3319: * number in collectOccurrences.
3320: */
3321: private void sortExprs(final List list) {
3322: Collections.sort(list, new Comparator() {
3323: public int compare(final Object a, final Object b) {
3324: if (a == b) {
3325: return 0;
3326: }
3327:
3328: final int ka = ((Expr) a).key();
3329: final int kb = ((Expr) b).key();
3330:
3331: return ka - kb;
3332: }
3333: });
3334: }
3335:
3336: /**
3337: * Sorts a lists of Kills into preorder. That is, the Kills in a given
3338: * block are sorted by the pre-order number.
3339: */
3340: private void sortKills(final List list) {
3341: Collections.sort(list, new Comparator() {
3342: public int compare(final Object a, final Object b) {
3343: if (a == b) {
3344: return 0;
3345: }
3346:
3347: final int ka = ((Kill) a).key();
3348: final int kb = ((Kill) b).key();
3349:
3350: return ka - kb;
3351: }
3352: });
3353: }
3354:
3355: /**
3356: * Print a textual description of this ExprInfo.
3357: */
3358: protected void print() {
3359: System.out.println("Print for " + prototype
3360: + "------------------");
3361:
3362: cfg.visit(new PrintVisitor() {
3363: Phi phi = null;
3364:
3365: public void visitBlock(final Block block) {
3366: phi = exprPhiAtBlock(block);
3367: super .visitBlock(block);
3368: }
3369:
3370: public void visitLabelStmt(final LabelStmt stmt) {
3371: super .visitLabelStmt(stmt);
3372:
3373: if (stmt.label().startsBlock()) {
3374: if (phi != null) {
3375: println(phi);
3376: phi = null;
3377: }
3378: }
3379: }
3380: });
3381:
3382: System.out
3383: .println("End Print ----------------------------");
3384: }
3385: } // end class ExprInfo
3386:
3387: /**
3388: * Traverses a tree and determines if a final (class or instance) field is
3389: * accessed.
3390: */
3391: class FinalChecker extends TreeVisitor {
3392: public boolean isFinal = true;
3393:
3394: public void visitExpr(final Expr expr) {
3395: if (isFinal) {
3396: expr.visitChildren(this );
3397: }
3398: }
3399:
3400: public void visitArrayRefExpr(final ArrayRefExpr expr) {
3401: isFinal = false;
3402: }
3403:
3404: public void visitFieldExpr(final FieldExpr expr) {
3405: final MemberRef field = expr.field();
3406:
3407: try {
3408: final FieldEditor e = context.editField(field);
3409: if (!e.isFinal()) {
3410: isFinal = false;
3411: }
3412: context.release(e.fieldInfo());
3413:
3414: } catch (final NoSuchFieldException e) {
3415: // A field wasn't found. Silently assume it's not final.
3416: isFinal = false;
3417: }
3418:
3419: if (isFinal) {
3420: expr.visitChildren(this );
3421: }
3422: }
3423:
3424: public void visitStaticFieldExpr(final StaticFieldExpr expr) {
3425: final MemberRef field = expr.field();
3426:
3427: try {
3428: final FieldEditor e = context.editField(field);
3429: if (!e.isFinal()) {
3430: isFinal = false;
3431: }
3432: context.release(e.fieldInfo());
3433:
3434: } catch (final NoSuchFieldException e) {
3435: // A field wasn't found. Silently assume it's not final.
3436: isFinal = false;
3437: }
3438:
3439: if (isFinal) {
3440: expr.visitChildren(this );
3441: }
3442: }
3443: }
3444:
3445: /**
3446: * ExprWorklist is a worklist of expressions (represented by ExprInfo)
3447: * containing all of the first-order expressions in the CFG (method). The
3448: * worklist is assembled in collectOccurrences() and its expressions are
3449: * used throughout SSAPRE.
3450: */
3451: class ExprWorklist {
3452: Map exprInfos; // A mapping between ExprKey and ExprInfo
3453:
3454: LinkedList exprs; // All the ExprInfos we know about
3455:
3456: public ExprWorklist() {
3457: exprInfos = new HashMap();
3458: exprs = new LinkedList();
3459: }
3460:
3461: public boolean isEmpty() {
3462: return exprs.isEmpty();
3463: }
3464:
3465: public ExprInfo removeFirst() {
3466: final ExprInfo exprInfo = (ExprInfo) exprs.removeFirst();
3467: exprInfos.remove(exprInfo.key);
3468: return exprInfo;
3469: }
3470:
3471: /**
3472: * Add a real occurrence of an expression to the worklist. If necessary,
3473: * an ExprInfo is created to represent the expression.
3474: */
3475: public void addReal(final Expr real) {
3476: if (SSAPRE.DEBUG) {
3477: System.out.println(" add to worklist=" + real);
3478: }
3479:
3480: final ExprKey key = new ExprKey(real);
3481:
3482: ExprInfo exprInfo = (ExprInfo) exprInfos.get(key);
3483:
3484: if (exprInfo == null) {
3485: exprInfo = new ExprInfo(real, key);
3486: exprs.add(exprInfo);
3487: exprInfos.put(key, exprInfo);
3488:
3489: if (SSAPRE.DEBUG) {
3490: System.out.println(" add info");
3491: }
3492: }
3493:
3494: exprInfo.addReal(real);
3495: }
3496:
3497: /**
3498: * Adds a Kill expression to the worklist at a given block.
3499: */
3500: public void addKill(final Block block, final Kill kill) {
3501: if (SSAPRE.DEBUG) {
3502: System.out.println(" add alias to worklist="
3503: + kill.expr + " " + kill);
3504: }
3505:
3506: final int blockIndex = cfg.preOrderIndex(block);
3507: kills[blockIndex].add(kill);
3508: killsSorted[blockIndex] = false;
3509: }
3510: }
3511:
3512: /**
3513: * Kill represents a point at which code cannot be hoisted across.
3514: */
3515: abstract class Kill {
3516: int key;
3517:
3518: Expr expr;
3519:
3520: /**
3521: * Constructor.
3522: *
3523: * @param expr
3524: * The expression that causes this kill.
3525: */
3526: public Kill(final Expr expr, final int key) {
3527: this .expr = expr;
3528: this .key = key;
3529: }
3530:
3531: public Kill(final int key) {
3532: this (null, key);
3533: }
3534:
3535: public int key() {
3536: return key;
3537: }
3538: }
3539:
3540: /**
3541: * ExceptionKill is a Kill that occurrs because an exception may be
3542: * encountered. An ExceptionKill is used when a Block that begins a
3543: * protected region or an expression that catches an exception is
3544: * encountered.
3545: */
3546: class ExceptionKill extends Kill {
3547: public ExceptionKill(final Expr expr, final int key) {
3548: super (expr, key);
3549: }
3550:
3551: public ExceptionKill(final int key) {
3552: super (key);
3553: }
3554: }
3555:
3556: /**
3557: * MemRefKill is a Kill that occurrs because a reference to a memory
3558: * location may be made. A MemRefKill is used when a synchronized
3559: * (monitorenter and monitorexit) block of code, or an expression that
3560: * accesses a memory location (MemRefExpr) and defines a variable, or an
3561: * expression that invokes a method is encountered.
3562: */
3563: class MemRefKill extends Kill {
3564: public MemRefKill(final Expr expr, final int key) {
3565: super (expr, key);
3566: }
3567:
3568: public MemRefKill(final int key) {
3569: super (key);
3570: }
3571: }
3572:
3573: /**
3574: * Represents an expression and a hash code for that expression.
3575: */
3576: class ExprKey {
3577: Expr expr;
3578:
3579: int hash;
3580:
3581: public ExprKey(final Expr expr) {
3582: this .expr = expr;
3583: this .hash = NodeComparator.hashCode(expr)
3584: + expr.type().hashCode();
3585: }
3586:
3587: public int hashCode() {
3588: return hash;
3589: }
3590:
3591: private List listChildren(Expr expr) {
3592: final List children = new ArrayList();
3593:
3594: if (expr instanceof StoreExpr) {
3595: expr = ((StoreExpr) expr).target();
3596: }
3597:
3598: expr.visitChildren(new TreeVisitor() {
3599: public void visitStoreExpr(final StoreExpr expr) {
3600: // Ignore the RHS.
3601: children.add(expr.target());
3602: }
3603:
3604: public void visitExpr(final Expr expr) {
3605: children.add(expr);
3606: }
3607: });
3608:
3609: return children;
3610: }
3611:
3612: public boolean equals(final Object obj) {
3613: if (obj instanceof ExprKey) {
3614: final ExprKey other = (ExprKey) obj;
3615:
3616: if (!expr.type().equals(other.expr.type())) {
3617: return false;
3618: }
3619:
3620: if (!NodeComparator.equals(expr, other.expr)) {
3621: return false;
3622: }
3623:
3624: final List children = listChildren(expr);
3625: final List otherChildren = listChildren(other.expr);
3626:
3627: if (children.size() != otherChildren.size()) {
3628: return false;
3629: }
3630:
3631: final Iterator iter1 = children.iterator();
3632: final Iterator iter2 = otherChildren.iterator();
3633:
3634: while (iter1.hasNext() && iter2.hasNext()) {
3635: final Expr child1 = (Expr) iter1.next();
3636: final Expr child2 = (Expr) iter2.next();
3637:
3638: if ((child1 instanceof StackExpr) != (child2 instanceof StackExpr)) {
3639: return false;
3640: }
3641:
3642: if ((child1 instanceof VarExpr)
3643: && (child2 instanceof VarExpr)) {
3644:
3645: if (phiRelatedFind(child1.def()) != phiRelatedFind(child2
3646: .def())) {
3647:
3648: return false;
3649: }
3650:
3651: } else {
3652: Assert.isTrue((child1 instanceof ConstantExpr)
3653: || (child2 instanceof ConstantExpr),
3654: "neither " + child1 + " nor " + child2
3655: + " are constants");
3656:
3657: // If one is a constant the other must have the same
3658: // value as the constant.
3659: if (child1.valueNumber() != child2
3660: .valueNumber()) {
3661: return false;
3662: }
3663: }
3664: }
3665:
3666: if (iter1.hasNext() || iter2.hasNext()) {
3667: // Size mismatch.
3668: return false;
3669: }
3670:
3671: return true;
3672: }
3673:
3674: return false;
3675: }
3676: } // end class ExprKey
3677:
3678: /**
3679: *
3680: */
3681: Expr phiRelatedFind(Expr a) {
3682: final ArrayList stack = new ArrayList();
3683:
3684: while (a != null) {
3685: Object p = phiRelated.get(a);
3686:
3687: if ((p == a) || (p == null)) {
3688: // Path compression.
3689: final Iterator iter = stack.iterator();
3690:
3691: while (iter.hasNext()) {
3692: p = iter.next();
3693:
3694: if (p != a) {
3695: phiRelated.put(p, a);
3696: }
3697: }
3698:
3699: return a;
3700: }
3701:
3702: stack.add(a);
3703: a = (Expr) p;
3704: }
3705:
3706: return null;
3707: }
3708:
3709: /**
3710: * phiRelatedUnion associates a variable (local or stack)
3711: */
3712: void phiRelatedUnion(final Expr a, final Expr b) {
3713: final Expr p = phiRelatedFind(a);
3714: final Expr q = phiRelatedFind(b);
3715: if (p != q) {
3716: phiRelated.put(p, q);
3717: }
3718: }
3719: }
|