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.ssa.*;
028: import EDU.purdue.cs.bloat.tree.*;
029: import EDU.purdue.cs.bloat.util.*;
030:
031: /**
032: * Performs value numbering analysis on the nodes in a control flow graph. Nodes
033: * with identical value numbers are folded into one another so that common
034: * (redundent) expressions are eliminated. Note that ValueNumbering works on the
035: * SSAGraph for the CFG and not the CFG itself.
036: *
037: * @see SSAGraph
038: */
039: // L.T. Simpson 1996. Value-driven redundancy elimination. PhD
040: // Thesis. Rice University. Look it up. Chapter 4 contains the
041: // stuff on SCC-based value numbering.
042: public class ValueNumbering {
043: public static boolean DEBUG = false;
044:
045: SSAGraph ssaGraph;
046:
047: HashMap tuples; // Maps a Node to its Tuple
048:
049: ValueFolder folder;
050:
051: int next; // The next value number to assign
052:
053: public String debugDirName = "debug";
054:
055: public File debugDir;
056:
057: public boolean DUMP = false;
058:
059: private PrintWriter dump = new PrintWriter(System.out);
060:
061: /**
062: * Performs value numbering on a control flow graph.
063: *
064: * @see ComponentVisitor
065: * @see SSAGraph
066: * @see ValueFolder
067: */
068: public void transform(final FlowGraph cfg) {
069: // Specify directory into which all debugging files should be
070: // placed
071:
072: if (DUMP || ValueFolding.DUMP) {
073: final String className = cfg.method().declaringClass()
074: .type().className();
075: final String methodName = cfg.method().name();
076:
077: final String dirName = debugDirName + File.separator
078: + className + File.separator + methodName;
079:
080: debugDir = new File(dirName);
081: for (int nextDir = 1; debugDir.exists(); nextDir++) {
082: // Multiple directories
083: debugDir = new File(dirName + "_" + nextDir);
084: }
085:
086: if (!debugDir.exists()) {
087: debugDir.mkdirs();
088: }
089:
090: // General dumping file
091: try {
092: final File dumpFile = new File(debugDir, "vn_dump");
093: dump = new PrintWriter(new FileWriter(dumpFile), true);
094: } catch (final IOException ex) {
095: System.err.println(ex.toString());
096: }
097: }
098:
099: ssaGraph = new SSAGraph(cfg);
100: tuples = new HashMap();
101: folder = new ValueFolder(false, cfg.method().declaringClass()
102: .context());
103: next = 0;
104:
105: final HashMap valid = new HashMap();
106: final HashMap optimistic = new HashMap();
107:
108: ssaGraph.visitComponents(new ComponentVisitor() {
109: public void visitComponent(final List scc) {
110: if (ValueNumbering.DEBUG || DUMP) {
111: dump.println("\nNumbering SCC = " + scc);
112: }
113:
114: final Iterator e = scc.iterator();
115:
116: while (e.hasNext()) {
117: final Node node = (Node) e.next();
118: node.setValueNumber(-1);
119: }
120:
121: if (scc.size() > 1) {
122: if (ValueNumbering.DEBUG || DUMP) {
123: dump
124: .println("Optimistic-----------------------");
125: }
126:
127: boolean changed = true;
128:
129: while (changed) {
130: changed = false;
131:
132: final Iterator iter = scc.iterator();
133:
134: while (iter.hasNext()) {
135: final Node node = (Node) iter.next();
136:
137: if (valnum(node, optimistic)) {
138: changed = true;
139: }
140: }
141: }
142: }
143:
144: if (ValueNumbering.DEBUG || DUMP) {
145: dump
146: .println("Valid--------------------------------");
147: }
148:
149: // The valid table contains the correct value numbers. Run
150: // through the each node in the SCC and call valnum.
151: // Presumably, the nodes are in reverse postorder.
152: final Iterator iter = scc.iterator();
153:
154: while (iter.hasNext()) {
155: final Node node = (Node) iter.next();
156: valnum(node, valid);
157: }
158: }
159: });
160:
161: if (ValueNumbering.DEBUG || DUMP) {
162: dump
163: .println("Final value numbers--------------------------");
164: printValueNumbers(cfg, new PrintWriter(dump));
165: }
166:
167: if (DUMP) {
168: System.out.println(" Dumping to: " + debugDir);
169:
170: try {
171: final File valueNumbers = new File(debugDir, "scc.txt");
172: ssaGraph.printSCCs(new PrintWriter(new FileWriter(
173: valueNumbers)));
174: } catch (final IOException ex) {
175: System.err.println("IOException: " + ex);
176: }
177: }
178:
179: ssaGraph = null;
180: tuples = null;
181:
182: folder.cleanup();
183: folder = null;
184:
185: // Make sure each node has a value number
186: cfg.visit(new TreeVisitor() {
187: public void visitTree(final Tree tree) {
188: tree.visitChildren(this );
189: }
190:
191: public void visitNode(final Node node) {
192: node.visitChildren(this );
193: Assert.isTrue(node.valueNumber() != -1,
194: "No value number for " + node);
195: }
196: });
197: }
198:
199: private void printValueNumbers(final FlowGraph cfg,
200: final PrintWriter pw) {
201: cfg.visit(new TreeVisitor() {
202: public void visitTree(final Tree tree) {
203: tree.visitChildren(this );
204: }
205:
206: public void visitNode(final Node node) {
207: node.visitChildren(this );
208:
209: pw.println("VN[" + node + " "
210: + System.identityHashCode(node) +
211: // " == " + ssaGraph.equivalent(node) + " " +
212: // System.identityHashCode(ssaGraph.equivalent(node)) +
213: "] = " + node.valueNumber());
214: }
215: });
216: }
217:
218: /**
219: * Simplifies a node by examining its type. A ValueFolder may be used to
220: * perform simplification.
221: *
222: * @return The folded (simplified) value of the node (which may be the same
223: * as the node itself)
224: */
225: private Node simplify(final Node node) {
226: if (ValueNumbering.DEBUG || DUMP) {
227: dump.println("folding " + node + " in " + node.parent());
228: }
229:
230: final int v = node.valueNumber();
231:
232: // A value number of -1 (i.e. value number has not yet been
233: // assigned) cannot be simplified.
234: if (v == -1) {
235: return node;
236: }
237:
238: // A constant expression can't be simplified, set the value of
239: // value number v to be node
240: if (node instanceof ConstantExpr) {
241: folder.values.ensureSize(v + 1);
242: folder.values.set(v, node);
243: return node;
244: }
245:
246: // Check for the value number in the folder.
247: if (v < folder.values.size()) {
248: final ConstantExpr value = (ConstantExpr) folder.values
249: .get(v);
250:
251: if (value != null) {
252: return value;
253: }
254: }
255:
256: // Else, use a ValueFolder to fold the node
257: folder.node = null;
258: node.visit(folder);
259:
260: if (ValueNumbering.DEBUG || DUMP) {
261: dump.println("folded " + node + " to " + folder.node);
262: }
263:
264: if (folder.node == null) {
265: // Nothing changed
266: return node;
267: }
268:
269: // If we folded the node into a constant expression, add it to
270: // the values list
271: if (folder.node instanceof ConstantExpr) {
272: folder.values.ensureSize(v + 1);
273: folder.values.set(v, folder.node);
274: }
275:
276: return folder.node;
277: }
278:
279: /**
280: * Processes a Node in an SCC.
281: */
282: private boolean valnum(final Node node, final HashMap table) {
283: boolean changed = false; // Did the table change?
284:
285: Tuple tuple = (Tuple) tuples.get(node);
286:
287: if (tuple == null) {
288: // Make a new Tuple for the node being processed
289: final Node s = simplify(node);
290:
291: tuple = new Tuple(s);
292: tuples.put(node, tuple);
293:
294: if (ValueNumbering.DEBUG || DUMP) {
295: dump.println(" New tuple " + tuple);
296: }
297:
298: } else if (DUMP) {
299: dump.println(" " + node + " mapped to tuple " + tuple);
300: }
301:
302: final Node w = (Node) table.get(tuple);
303:
304: if (ValueNumbering.DEBUG || DUMP) {
305: dump.println(" Looking up " + tuple);
306: dump.println(" "
307: + tuple
308: + " mapped to node "
309: + w
310: + (w != null ? " (VN = " + w.valueNumber() + ")"
311: : ""));
312: }
313:
314: int value = -1;
315:
316: if ((w != null) && (w.valueNumber() != -1)) {
317: value = w.valueNumber();
318:
319: } else {
320: if (ValueNumbering.DEBUG || DUMP) {
321: dump.println(" New value number " + next);
322: }
323:
324: value = next++;
325: }
326:
327: Assert.isTrue(value != -1);
328:
329: // Now make sure all equivalent nodes have the same value number.
330: final Iterator iter = ssaGraph.equivalent(node).iterator();
331:
332: while (iter.hasNext()) {
333: final Node v = (Node) iter.next();
334:
335: final Tuple t = (Tuple) tuples.get(v);
336:
337: if (t == null) {
338: // Will get done later.
339: continue;
340: }
341:
342: if (v.valueNumber() != value) {
343: v.setValueNumber(value);
344: table.put(t, v);
345:
346: if (ValueNumbering.DEBUG || DUMP) {
347: dump.println(" Assigning value number "
348: + v.valueNumber() + " to " + v);
349: dump.println(" Mapping tuple " + t + " to node "
350: + v);
351: }
352:
353: changed = true;
354: }
355: }
356:
357: return changed;
358: }
359:
360: /**
361: * Tuple contains a Node and an associated hash value. The Node is the
362: * simplified version of another node. The main purpose of the Tuple class
363: * is to compare two Nodes to determine if they are the same with respect to
364: * their value numbers.
365: */
366: class Tuple {
367: Node node;
368:
369: int hash;
370:
371: public Tuple(final Node node) {
372: this .node = node;
373: final List children = ssaGraph.children(node);
374: this .hash = NodeComparator.hashCode(node) + children.size();
375: }
376:
377: public String toString() {
378: final List children = ssaGraph.children(node);
379:
380: String s = "<" + node + ", hash=" + hash;
381:
382: final Iterator iter = children.iterator();
383:
384: while (iter.hasNext()) {
385: final Node child = (Node) iter.next();
386: s += ", " + child + "{" + child.valueNumber() + "}";
387: }
388:
389: s += ">";
390:
391: return s;
392: }
393:
394: public int hashCode() {
395: return hash;
396: }
397:
398: public boolean equals(final Object obj) {
399: if (this == obj) {
400: return true;
401: }
402:
403: if (obj instanceof Tuple) {
404: final Tuple t = (Tuple) obj;
405:
406: if (node == t.node) {
407: return true;
408: }
409:
410: // All mem refs are unequal.
411: if ((node instanceof MemRefExpr)
412: || (t.node instanceof MemRefExpr)) {
413: return false;
414: }
415:
416: if (!NodeComparator.equals(node, t.node)) {
417: return false;
418: }
419:
420: final List children1 = ssaGraph.children(node);
421: final List children2 = ssaGraph.children(t.node);
422:
423: if (children1.size() != children2.size()) {
424: return false;
425: }
426:
427: if (node instanceof PhiStmt) {
428: // The order of the children does not matter
429: final int[] used = new int[next];
430: int free = 0; // The number of un-numbered children
431:
432: Iterator iter = children1.iterator();
433:
434: while (iter.hasNext()) {
435: final Node child = (Node) iter.next();
436: final int v = child.valueNumber();
437:
438: if (v != -1) {
439: used[v]++;
440:
441: } else {
442: free++;
443: }
444: }
445:
446: iter = children2.iterator();
447:
448: while (iter.hasNext()) {
449: final Node child = (Node) iter.next();
450: final int v = child.valueNumber();
451:
452: if (v != -1) {
453: if (used[v] != 0) {
454: used[v]--;
455:
456: } else {
457: free--;
458: }
459:
460: } else {
461: free--;
462: }
463: }
464:
465: if (free < 0) {
466: return false;
467: }
468:
469: return true;
470:
471: } else {
472: // The children of the nodes in the SSAGraph must have the
473: // same value numbers and be in the same order.
474: final Iterator iter1 = children1.iterator();
475: final Iterator iter2 = children2.iterator();
476:
477: while (iter1.hasNext() && iter2.hasNext()) {
478: final Node child1 = (Node) iter1.next();
479: final Node child2 = (Node) iter2.next();
480:
481: final int v1 = child1.valueNumber();
482: final int v2 = child2.valueNumber();
483:
484: if ((v1 != -1) && (v2 != -1) && (v1 != v2)) {
485: return false;
486: }
487: }
488:
489: if (iter1.hasNext() || iter2.hasNext()) {
490: // Size mismatch.
491: return false;
492: }
493:
494: return true;
495: }
496: }
497:
498: return false;
499: }
500: }
501: }
|