001: /* Copyright (C) 2004 - 2007 db4objects Inc. http://www.db4o.com
002:
003: This file is part of the db4o open source object database.
004:
005: db4o is free software; you can redistribute it and/or modify it under
006: the terms of version 2 of the GNU General Public License as published
007: by the Free Software Foundation and as clarified by db4objects' GPL
008: interpretation policy, available at
009: http://www.db4o.com/about/company/legalpolicies/gplinterpretation/
010: Alternatively you can write to db4objects, Inc., 1900 S Norfolk Street,
011: Suite 350, San Mateo, CA 94403, USA.
012:
013: db4o is distributed in the hope that it will be useful, but WITHOUT ANY
014: WARRANTY; without even the implied warranty of MERCHANTABILITY or
015: FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
016: for more details.
017:
018: You should have received a copy of the GNU General Public License along
019: with this program; if not, write to the Free Software Foundation, Inc.,
020: 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
021: package EDU.purdue.cs.bloat.trans;
022:
023: import java.util.*;
024:
025: import EDU.purdue.cs.bloat.cfg.*;
026: import EDU.purdue.cs.bloat.tree.*;
027:
028: /**
029: * Performs copy and constant propagation on the blocks in a control flow graph.
030: */
031: public class ExprPropagation {
032: public static boolean DEBUG = false;
033:
034: FlowGraph cfg;
035:
036: boolean changed; // Did the cfg change?
037:
038: /**
039: * Constructor.
040: *
041: * @param cfg
042: * The control flow graph on which expression propagation is
043: * being performed.
044: */
045: public ExprPropagation(final FlowGraph cfg) {
046: this .cfg = cfg;
047: }
048:
049: /**
050: * Performs the propagation.
051: */
052: public void transform() {
053: changed = true;
054:
055: while (changed) {
056: changed = false;
057: propagate();
058: }
059: }
060:
061: /**
062: * Propagate expressions through the control flow graph in hopes of reducing
063: * the number of local variables.
064: */
065: private void propagate() {
066: cfg.visit(new TreeVisitor() {
067: Iterator iter;
068:
069: public void visitTree(final Tree tree) {
070: iter = tree.stmts().iterator();
071:
072: while (iter.hasNext()) {
073: final Stmt stmt = (Stmt) iter.next();
074: stmt.visit(this );
075: }
076: }
077:
078: public void visitStoreExpr(final StoreExpr expr) {
079: expr.visitChildren(this );
080:
081: if (!(expr.target() instanceof LocalExpr)) {
082: // If we're not assigning to a local variable, fergit it
083: return;
084: }
085:
086: final LocalExpr lhs = (LocalExpr) expr.target();
087: final Expr rhs = expr.expr();
088:
089: // L := (M := E)
090: // use L
091: // use M
092: //
093: // -->
094: //
095: // L := E
096: // use L
097: // use L
098: //
099: // Since we've already visited (M := E), M could not be
100: // eliminated. So, after propagating M to L, we won't be
101: // able to eliminate L either, so don't even try.
102: //
103: if (rhs instanceof StoreExpr) {
104: final StoreExpr store = (StoreExpr) rhs;
105:
106: final MemExpr rhsLHS = store.target();
107: final Expr rhsRHS = store.expr();
108:
109: if (rhsLHS instanceof LocalExpr) {
110: // Replace uses of M with L.
111:
112: // We need to make a copy of the lhs since it is a
113: // def an consequently does not contain a pointer to
114: // a def.
115: final LocalExpr copy = (LocalExpr) lhs.clone();
116: copy.setDef(lhs);
117:
118: if (propExpr(expr.block(), (LocalExpr) rhsLHS,
119: copy)) {
120: // If all uses of the rhsRHS local variable were
121: // replaced, replace all occurrences of the rhs with
122: // the
123: // local variable of rhsRHS.
124: changed = true;
125:
126: expr.visit(new ReplaceVisitor(rhs, rhsRHS));
127: rhsLHS.cleanup();
128: rhs.cleanupOnly();
129: }
130:
131: // Be sure to cleanup the copy.
132: copy.cleanup();
133: }
134:
135: }
136: // This next part is awful and comented out. Propagating
137: // local variables like this fails to take into account
138: // the live ranges. When we have L := M, it replaces L with
139: // M after M has been overwritten. Arg.
140: /*
141: * else if (rhs instanceof LeafExpr) { if
142: * (propExpr(expr.block(), lhs, rhs)) { // If all uses of the
143: * local variable in the lhs were // replaced with the LeafExpr
144: * in the rhs, then the store // (L := X) is useless. Replace it
145: * with (eval X) so it // can be removed later. changed = true;
146: * // Replace eval (L := X) with eval X // Dead code
147: * elimination will remove it. if (expr.parent() instanceof
148: * ExprStmt) iter.remove(); else expr.replaceWith((Expr)
149: * rhs.clone()); } }
150: */
151: }
152:
153: public void visitPhiStmt(final PhiStmt stmt) {
154: final Expr lhs = stmt.target();
155:
156: if (!(lhs instanceof LocalExpr)) {
157: // If we're not assigning into a local variable, fergit it
158: return;
159: }
160:
161: // Look at all of the operands of the PhiStmt. If all of the
162: // operands are either the same local variable or the same
163: // constant, then propagate an operand (doesn't matter which
164: // one because they're all the same value) to all uses of the
165: // target of the PhiStmt.
166: final Iterator e = stmt.operands().iterator();
167:
168: if (!e.hasNext()) {
169: return;
170: }
171:
172: final Expr rhs = (Expr) e.next();
173:
174: if (!(rhs instanceof LeafExpr)) {
175: return;
176: }
177:
178: while (e.hasNext()) {
179: final Expr operand = (Expr) e.next();
180:
181: if (rhs instanceof LocalExpr) {
182: if (operand instanceof LocalExpr) {
183: if (rhs.def() != operand.def()) {
184: return;
185: }
186: } else {
187: return;
188: }
189:
190: } else if (rhs instanceof ConstantExpr) {
191: if (!rhs.equalsExpr(operand)) {
192: return;
193: }
194:
195: } else {
196: return;
197: }
198: }
199:
200: if (propExpr(stmt.block(), (LocalExpr) lhs, rhs)) {
201: // If all uses of the PhiStmt's target were replaced, remove
202: // it from the expression tree.
203: changed = true;
204: iter.remove();
205: }
206: }
207: });
208: }
209:
210: /**
211: * Propagates the expression in rhs to all uses of the lhs. Returns true, if
212: * all of the uses of the lhs were replaced.
213: */
214: boolean propExpr(final Block block, final LocalExpr lhs,
215: final Expr rhs) {
216: if (ExprPropagation.DEBUG) {
217: System.out.println("prop " + rhs + " to uses of " + lhs);
218: System.out.println(" uses of lhs = " + lhs.uses());
219: }
220:
221: if (rhs instanceof LocalExpr) {
222: // We can't prop a local to a PhiStmt operand, so don't bother
223: // doing the propagation at all.
224: Iterator e = lhs.uses().iterator();
225:
226: while (e.hasNext()) {
227: final LocalExpr use = (LocalExpr) e.next();
228:
229: if (use.parent() instanceof PhiStmt) {
230: return false;
231: }
232: }
233:
234: // Replaces all uses of the lhs with the rhs. Both are local
235: // variables.
236: e = lhs.uses().iterator();
237:
238: while (e.hasNext()) {
239: final LocalExpr use = (LocalExpr) e.next();
240: use.replaceWith((Expr) rhs.clone());
241: }
242:
243: return true;
244:
245: } else {
246: boolean replacedAll = true;
247:
248: final Iterator e = lhs.uses().iterator();
249:
250: while (e.hasNext()) {
251: final LocalExpr use = (LocalExpr) e.next();
252:
253: if (use.parent() instanceof PhiCatchStmt) {
254: replacedAll = false;
255: } else {
256: use.replaceWith((Expr) rhs.clone());
257: }
258: }
259:
260: return replacedAll;
261: }
262: }
263: }
|