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.io.*;
024: import java.util.*;
025:
026: import EDU.purdue.cs.bloat.cfg.*;
027: import EDU.purdue.cs.bloat.editor.*;
028: import EDU.purdue.cs.bloat.ssa.*;
029: import EDU.purdue.cs.bloat.tree.*;
030:
031: /**
032: * <tt>ValueFolding</tt> uses a <tt>ValueFolder</tt> to determine which
033: * nodes in an expression tree can be removed or replaced by common expression
034: * elimination and constant propagation.
035: *
036: * @see ValueFolder
037: */
038: public class ValueFolding {
039: public static boolean DEBUG = false;
040:
041: SideEffectChecker sideEffects;
042:
043: ValueFolder folder;
044:
045: boolean changed;
046:
047: public static boolean DUMP = false;
048:
049: public static boolean SAVEDUMP = false;
050:
051: PrintWriter vn;
052:
053: PrintWriter dump;
054:
055: /**
056: * Performs value folding (common expression elimination and constant
057: * folding) on a control flow graph.
058: */
059: int next = 1;
060:
061: public void transform(final FlowGraph cfg) {
062:
063: final File dir = new File("ValueFoldingOutdir");
064: if (ValueFolding.DUMP) {
065: // System.out.println(" Dumping Value Folding in directory: " +
066: // dir);
067:
068: // try {
069: // cfgFile = new File(dir, "cfg.txt");
070:
071: // cfg.print(new PrintWriter(new FileWriter(cfgFile), true));
072:
073: // dotFile = new File(dir, "cfg.dot");
074: // cfg.printGraph(new PrintWriter(new FileWriter(dotFile),
075: // true));
076:
077: // vnFile = new File(dir, "value.numbers");
078: // vn = new PrintWriter(new FileWriter(vnFile), true);
079:
080: // dumpFile = new File(dir, "vn.dump");
081: // dump = new PrintWriter(new FileWriter(dumpFile), true);
082:
083: // } catch (IOException ex) {
084:
085: // }
086:
087: vn = new PrintWriter(System.out, true);
088: dump = new PrintWriter(System.out, true);
089: }
090:
091: final EditorContext context = cfg.method().declaringClass()
092: .context();
093:
094: sideEffects = new SideEffectChecker(context);
095:
096: folder = new ValueFolder(true, context);
097:
098: final SSAGraph ssaGraph = new SSAGraph(cfg);
099:
100: ssaGraph.visitComponents(new ComponentVisitor() {
101: public void visitComponent(final List scc) {
102: // Maps Nodes in the SCC to their folded value
103: final HashMap map = new HashMap(scc.size() * 2 + 1);
104:
105: boolean changed = true;
106:
107: while (changed) {
108: changed = false;
109:
110: final Iterator iter = scc.iterator();
111:
112: int x = 0;
113: while (iter.hasNext()) {
114: final Node node = (Node) iter.next();
115:
116: if (ValueFolding.DUMP) {
117: x++;
118: dump.println("Folding SCC Node " + node
119: + " (" + x + " of " + scc.size()
120: + ")");
121: }
122:
123: if (fold(map, node)) {
124: changed = true;
125: }
126: }
127:
128: if (ValueFolding.DUMP) {
129: dump.println("");
130: }
131:
132: if (scc.size() == 1) {
133: break;
134: }
135: }
136: }
137: });
138:
139: cfg.removeUnreachable();
140:
141: folder = null;
142: sideEffects = null;
143:
144: // Okay, we've successfully value folded, remove debugging files
145: if (ValueFolding.DUMP && !ValueFolding.SAVEDUMP) {
146: // cfgFile.delete();
147: // dotFile.delete();
148: // dumpFile.delete();
149: // vnFile.delete();
150: // dir.delete();
151: }
152: }
153:
154: /**
155: * Builds a mapping between the nodes in a CFG's SCCs and the expressions
156: * they are equivalent to.
157: *
158: * @param map
159: * A mapping between the SCCs of the CFG's SSA Graph
160: * (definitions) and the expressions they are folded to
161: * @param sccNode
162: * A Node in the SCC of the SSA Graph
163: *
164: * @return True, if the value in the mapping was changed.
165: */
166: boolean fold(final Map map, final Node sccNode) {
167: Node node = (Node) map.get(sccNode);
168:
169: if (ValueFolding.DUMP) {
170: dump.println(" SCC Node " + sccNode
171: + " is mapped to node " + node);
172: }
173:
174: // The SCC node has not been folded yet, fold it to itself
175: if (node == null) {
176: node = sccNode;
177: }
178:
179: if (!node.hasParent()) {
180: return false;
181: }
182:
183: if (ValueFolding.DEBUG) {
184: System.out.println("folding --- " + node + " in "
185: + node.parent());
186: }
187:
188: if (ValueFolding.DUMP) {
189: dump.println(" Folding " + node + " (" + "VN="
190: + node.valueNumber() + ") in " + node.parent());
191: }
192:
193: final int v = node.valueNumber();
194:
195: if (v == -1) {
196: // Node has not been assigned a value number, can't do anything
197: return false;
198: }
199:
200: folder.values.ensureSize(v + 1);
201: final ConstantExpr oldValue = (ConstantExpr) folder.values
202: .get(v);
203: ConstantExpr value = null;
204:
205: if (ValueFolding.DUMP) {
206: dump.println(" Node " + node + " is mapped to constant "
207: + oldValue);
208: }
209:
210: if (node instanceof ConstantExpr) {
211: // If the node that we're dealing with is already a
212: // ConstantExpr, change it to the mapped value if it is
213: // different.
214: value = (ConstantExpr) node;
215:
216: if ((oldValue == null) || !oldValue.equalsExpr(value)) {
217: // The node was not previously mapped to a constant, or it was
218: // mapped to a different constant. Update the mapping to
219: // relfect the new constant.
220: if (ValueFolding.DEBUG) {
221: System.out.println("changed " + oldValue + " to "
222: + value);
223: }
224:
225: if (ValueFolding.DUMP) {
226: dump.println(" Changed " + oldValue + " to "
227: + value);
228: }
229:
230: folder.values.set(v, value);
231: return true;
232: }
233:
234: // Mapping was already correct, don't do anything.
235: return false;
236: }
237:
238: if ((node instanceof Expr) && (oldValue != null)) {
239: // The node is a non-constant Expr that was mapped to a constant
240:
241: if (node.parent() instanceof PhiCatchStmt) {
242: // Don't fold values inside PhiCatchStmts
243: return false;
244: }
245:
246: sideEffects.reset();
247: node.visit(sideEffects);
248:
249: if (!sideEffects.hasSideEffects()) {
250: // If the expression does not have side effects, then make a
251: // clone of the value to which it was mapped and map the clone
252: // to the original sccNode (which may or may not be node).
253: // Technically, the mapping did not change.
254:
255: value = (ConstantExpr) oldValue.clone();
256: node.replaceWith(value);
257: map.put(sccNode, value);
258: return false;
259: }
260: }
261:
262: if (value == null) {
263: // The node is mapped to nothing, Use the ValueFolder to
264: // determine a expression that node can be folded to.
265:
266: folder.node = null;
267: node.visit(folder);
268:
269: if (ValueFolding.DEBUG) {
270: System.out.println("folded " + node + " to "
271: + folder.node);
272: }
273:
274: if (ValueFolding.DUMP) {
275: dump
276: .println(" Using ValueFolder to determine new value");
277: dump.println(" Folded " + node + " to "
278: + folder.node);
279: }
280:
281: if (folder.node != null) {
282: // Assert.isTrue(folder.node.hasParent(),
283: // "No parent for " + folder.node);
284: map.put(sccNode, folder.node);
285: }
286:
287: if (folder.node instanceof ConstantExpr) {
288: // If the node was folded into a ConstantExpr, then fold it in
289: // the ValueFolder.
290: value = (ConstantExpr) folder.node;
291: folder.values.set(v, value);
292: return true;
293: }
294: }
295:
296: return false;
297: }
298: }
|