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.ssa;
022:
023: import java.io.*;
024: import java.util.*;
025:
026: import EDU.purdue.cs.bloat.cfg.*;
027: import EDU.purdue.cs.bloat.tree.*;
028: import EDU.purdue.cs.bloat.util.*;
029:
030: /**
031: * The SSA graph (also called the value graph) represents the nesting of
032: * expression in a control flow graph. Each node in the SSA graph represents an
033: * expression. If the expression is a definition, the it is labeled with the
034: * variable it defines. Each node has directed edges to the nodes representing
035: * its operands.
036: *
037: * <p>
038: *
039: * <tt>SSAGraph</tt> is a representation of the definitions found in a CFG in
040: * the following form: Each node in the graph is an expression that defines a
041: * variable (a <tt>VarExpr</tt>, <tt>PhiStmt</tt>, or a
042: * <tt>StackManipStmt</tt>). Edges in the graph point to the nodes whose
043: * expressions define the operands of the expression in the source node.
044: *
045: * <p>
046: *
047: * This class is used primarily get the strongly connected components of the SSA
048: * graph in support of value numbering and induction variable analysis.
049: *
050: * <p>
051: *
052: * Nate warns: Do not modify the CFG while using the SSA graph! The effects of
053: * such modification are undefined and will probably lead to nasty things
054: * occuring.
055: *
056: * @see EDU.purdue.cs.bloat.trans.ValueNumbering ValueNumbering
057: */
058: public class SSAGraph {
059: public static boolean DEBUG = false;
060:
061: FlowGraph cfg;
062:
063: HashMap equiv; // A mapping between a Node and all its equivalent Nodes
064:
065: /**
066: * Grumble.
067: */
068: public SSAGraph(final FlowGraph cfg, final boolean useless) {
069: this (cfg);
070: }
071:
072: /**
073: * Constructor. Traverse the control flow graph and determines which Nodes
074: * are of an equivalent Type.
075: *
076: * @param cfg
077: * The control flow graph to examine
078: */
079: public SSAGraph(final FlowGraph cfg) {
080: this .cfg = cfg;
081: this .equiv = new HashMap();
082:
083: cfg.visit(new TreeVisitor() {
084: // The CheckExpr and the Expr is checks are equivalent.
085: public void visitCheckExpr(final CheckExpr expr) {
086: expr.visitChildren(this );
087: makeEquiv(expr, expr.expr());
088: }
089:
090: // The target of the PhiStmt and the PhiStmt are equivalent
091: public void visitPhiStmt(final PhiStmt stmt) {
092: stmt.visitChildren(this );
093: makeEquiv(stmt.target(), stmt);
094: }
095:
096: // The use of a variable and its defining variable are equivalent
097: public void visitVarExpr(final VarExpr expr) {
098: if (!expr.isDef()) {
099: final VarExpr def = (VarExpr) expr.def();
100:
101: if (def != null) {
102: makeEquiv(expr, def);
103: }
104: }
105: }
106:
107: // With StackManipStmts the stack slot (StackExpr) after the
108: // StackManipStmt is equivalent to its corresponding slot before
109: // the StackManipStmt.
110: public void visitStackManipStmt(final StackManipStmt stmt) {
111: final StackExpr[] target = stmt.target();
112: final StackExpr[] source = stmt.source();
113:
114: switch (stmt.kind()) {
115: case StackManipStmt.SWAP:
116: // 0 1 -> 1 0
117: Assert.isTrue((source.length == 2)
118: && (target.length == 2),
119: "Illegal statement: " + stmt);
120: manip(source, target, new int[] { 1, 0 });
121: break;
122: case StackManipStmt.DUP:
123: // 0 -> 0 0
124: Assert.isTrue((source.length == 1)
125: && (target.length == 2),
126: "Illegal statement: " + stmt);
127: manip(source, target, new int[] { 0, 0 });
128: break;
129: case StackManipStmt.DUP_X1:
130: // 0 1 -> 1 0 1
131: Assert.isTrue((source.length == 2)
132: && (target.length == 3),
133: "Illegal statement: " + stmt);
134: manip(source, target, new int[] { 1, 0, 1 });
135: break;
136: case StackManipStmt.DUP_X2:
137: if (source.length == 3) {
138: // 0 1 2 -> 2 0 1 2
139: Assert.isTrue((source.length == 3)
140: && (target.length == 4),
141: "Illegal statement: " + stmt);
142: manip(source, target, new int[] { 2, 0, 1, 2 });
143: } else {
144: // 0-1 2 -> 2 0-1 2
145: Assert.isTrue((source.length == 2)
146: && (target.length == 3),
147: "Illegal statement: " + stmt);
148: manip(source, target, new int[] { 1, 0, 1 });
149: }
150: break;
151: case StackManipStmt.DUP2:
152: if (source.length == 2) {
153: // 0 1 -> 0 1 0 1
154: Assert.isTrue(target.length == 4,
155: "Illegal statement: " + stmt);
156: manip(source, target, new int[] { 0, 1, 0, 1 });
157: } else {
158: // 0-1 -> 0-1 0-1
159: Assert.isTrue((source.length == 1)
160: && (target.length == 2),
161: "Illegal statement: " + stmt);
162: manip(source, target, new int[] { 0, 0 });
163: }
164: break;
165: case StackManipStmt.DUP2_X1:
166: if (source.length == 3) {
167: // 0 1 2 -> 1 2 0 1 2
168: Assert.isTrue(target.length == 5,
169: "Illegal statement: " + stmt);
170: manip(source, target,
171: new int[] { 1, 2, 0, 1, 2 });
172: } else {
173: // 0 1-2 -> 1-2 0 1-2
174: Assert.isTrue((source.length == 2)
175: && (target.length == 3),
176: "Illegal statement: " + stmt);
177: manip(source, target, new int[] { 1, 0, 1 });
178: }
179: break;
180: case StackManipStmt.DUP2_X2:
181: if (source.length == 4) {
182: // 0 1 2 3 -> 2 3 0 1 2 3
183: Assert.isTrue(target.length == 6,
184: "Illegal statement: " + stmt);
185: manip(source, target, new int[] { 2, 3, 0, 1,
186: 2, 3 });
187: } else if (source.length == 3) {
188: if (target.length == 5) {
189: // 0-1 2 3 -> 2 3 0-1 2 3
190: manip(source, target, new int[] { 1, 2, 0,
191: 1, 2 });
192: } else {
193: // 0 1 2-3 -> 2-3 0 1 2-3
194: Assert.isTrue(target.length == 4,
195: "Illegal statement: " + stmt);
196: manip(source, target, new int[] { 2, 0, 1,
197: 2 });
198: }
199: } else {
200: // 0-1 2-3 -> 2-3 0-1 2-3
201: Assert.isTrue((source.length == 2)
202: && (target.length == 3),
203: "Illegal statement: " + stmt);
204: manip(source, target, new int[] { 1, 0, 1 });
205: }
206: break;
207: }
208:
209: stmt.visitChildren(this );
210: }
211:
212: // Determines equivalence of the StackExprs invovled in a
213: // StackManipStmt. Recall that StackManipStmt are things like
214: // the dup and swap instructions. So, elements (StackExprs) of
215: // the "new" stack will be equivalent to elements of the "old"
216: // stack. The s array defines the transformation.
217: private void manip(final StackExpr[] source,
218: final StackExpr[] target, final int[] s) {
219: for (int i = 0; i < s.length; i++) {
220: makeEquiv(target[i], source[s[i]]);
221: }
222: }
223:
224: // The StoreExpr is equivalent to the expression being stored.
225: public void visitStoreExpr(final StoreExpr expr) {
226: expr.visitChildren(this );
227: makeEquiv(expr, expr.expr());
228:
229: if (expr.target() instanceof VarExpr) {
230: makeEquiv(expr.target(), expr.expr());
231: }
232: }
233: });
234: }
235:
236: /**
237: * Returns the <tt>FlowGraph</tt> that this <tt>SSAGraph</tt> is built
238: * around.
239: */
240: public FlowGraph cfg() {
241: return (this .cfg);
242: }
243:
244: /**
245: * Returns a set of nodes whose value is equivalent to a given node. For
246: * example, the LHS and RHS of an assignment are equivalent. As are all
247: * local variables with the same definition.
248: */
249: public Set equivalent(final Node node) {
250: Set s = (Set) equiv.get(node);
251:
252: if (s == null) {
253: s = new HashSet(1);
254: s.add(node); // A node is equivalent to itself
255: equiv.put(node, s);
256: }
257:
258: return s;
259: }
260:
261: /**
262: * Makes node1 equivalent to node2 by adding the equivlance Set of node2 to
263: * the equivalance Set of node1, and vice versa.
264: */
265: void makeEquiv(final Node node1, final Node node2) {
266: final Set s1 = equivalent(node1);
267: final Set s2 = equivalent(node2);
268:
269: if (s1 != s2) {
270: s1.addAll(s2);
271:
272: final Iterator iter = s2.iterator();
273:
274: while (iter.hasNext()) {
275: final Node n = (Node) iter.next();
276: equiv.put(n, s1);
277: }
278: }
279: }
280:
281: /**
282: * Returns the children (that is, the operands) of a given Node in the SSA
283: * Graph.
284: */
285: public List children(final Node node) {
286: final ArrayList c = new ArrayList();
287:
288: if (node instanceof StoreExpr) {
289: final StoreExpr store = (StoreExpr) node;
290:
291: // Add the grand children of RHS. The RHS is equivalent to
292: // this node.
293: store.expr().visitChildren(new TreeVisitor() {
294: public void visitNode(final Node node) {
295: c.add(node);
296: }
297: });
298:
299: // The LHS is equivalent to this node if it is a VarExpr and not
300: // a child.
301: if (!(store.target() instanceof VarExpr)) {
302: c.add(store.target());
303: }
304:
305: } else if (node instanceof PhiStmt) {
306: final PhiStmt phi = (PhiStmt) node;
307: c.addAll(phi.operands());
308:
309: } else {
310: node.visitChildren(new TreeVisitor() {
311: public void visitNode(final Node node) {
312: c.add(node);
313: }
314: });
315: }
316:
317: return c;
318: }
319:
320: /**
321: * Returns the Sets of Nodes whose values are equivalent.
322: */
323: public Collection equivalences() {
324: return equiv.values();
325: }
326:
327: class Count {
328: int value = 0;
329: }
330:
331: /**
332: * Calculates the strongly connected components (SCC) of the SSA graph. SSCs
333: * are represented by a List of <tt>Node</tt>s. The SCCs are then visited
334: * by the ComponentVistor.
335: */
336: public void visitComponents(final ComponentVisitor visitor) {
337: // Number the nodes reverse post order (i.e. topological order).
338:
339: final Count count = new Count();
340:
341: final List postOrder = cfg.postOrder();
342: final ListIterator iter = postOrder.listIterator(postOrder
343: .size());
344:
345: // Perform a depth-first ordering of the nodes in the CFG to give
346: // each node a unique identifier. This is accomplished by
347: // visiting the blocks in the CFG in post-order and numbering the
348: // Nodes in the block's expression Tree in depth-first order.
349: while (iter.hasPrevious()) {
350: final Block block = (Block) iter.previous();
351:
352: block.visit(new TreeVisitor() {
353: public void visitTree(final Tree tree) {
354: tree.visitChildren(this );
355: }
356:
357: public void visitNode(final Node node) {
358: node.visitChildren(this );
359: node.setKey(count.value++);
360: }
361: });
362: }
363:
364: // Build the (strongly connected) components and call
365: // visitor.visitComponent for each.
366: cfg.visit(new TreeVisitor() {
367: ArrayList stack = new ArrayList();
368:
369: BitSet onStack = new BitSet(count.value + 1);
370:
371: int[] low = new int[count.value + 1];
372:
373: int[] dfs = new int[count.value + 1];
374:
375: int dfsNumber = 1;
376:
377: Node parent; // Parent in the SSA graph
378:
379: // Visit the blocks in the CFG in reverse postorder
380: public void visitFlowGraph(final FlowGraph cfg) {
381: final ListIterator e = postOrder.listIterator(postOrder
382: .size());
383:
384: while (e.hasPrevious()) {
385: final Block block = (Block) e.previous();
386: block.visit(this );
387: }
388: }
389:
390: public void visitTree(final Tree tree) {
391: parent = null;
392: tree.visitChildren(this );
393: }
394:
395: // This method is essentially Figure 4.6 in Taylor Simpson's PhD
396: // Thesis: www.cs.rice.edu/~lts. The implementation is a little
397: // funky, though, because someone wanted to use visitors.
398: // Grumble.
399: public void visitNode(final Node node) {
400: int dfn = dfs[node.key()];
401: // System.out.println("visit " + node + " key=" + node.key() +
402: // " dfn=" + dfn);
403:
404: if (dfn == 0) {
405: // The node in question has not yet been visited. Assign it
406: // the next dfNumber and add it to the stack. Mark all
407: // nodes that are equivalent to the node in question as
408: // being visited.
409:
410: dfn = dfsNumber++;
411: low[dfn] = dfn;
412:
413: stack.add(node);
414: onStack.set(dfn);
415:
416: Iterator equiv = equivalent(node).iterator();
417:
418: while (equiv.hasNext()) {
419: final Node e = (Node) equiv.next();
420: dfs[e.key()] = dfn;
421: }
422:
423: // Again examine each node, e, equivalent to the node in
424: // question. Then recursively visit the children of e in
425: // the SSA Graph.
426: final Node grandParent = parent;
427: parent = node;
428:
429: equiv = equivalent(node).iterator();
430:
431: while (equiv.hasNext()) {
432: final Node e = (Node) equiv.next();
433:
434: final Iterator children = children(e)
435: .iterator();
436:
437: while (children.hasNext()) {
438: final Node child = (Node) children.next();
439: child.visit(this );
440: }
441: }
442:
443: parent = grandParent; // Restore true parent
444:
445: // Now we finally get to the point where we can construct a
446: // strongly connected component. Pop all of the nodes off
447: // the stack until the node in question is reached.
448: if (low[dfn] == dfn) {
449: final ArrayList scc = new ArrayList();
450:
451: while (!stack.isEmpty()) {
452: final Node v = (Node) stack.remove(stack
453: .size() - 1);
454: onStack.clear(dfs[v.key()]);
455: scc.addAll(equivalent(v));
456:
457: if (v == node) {
458: break;
459: }
460: }
461:
462: // Sort the nodes in the SCC by their reverse
463: // post order numbers.
464: Collections.sort(scc, new Comparator() {
465: public int compare(final Object a,
466: final Object b) {
467: final int ka = ((Node) a).key();
468: final int kb = ((Node) b).key();
469: return ka - kb;
470: }
471: });
472:
473: if (SSAGraph.DEBUG) {
474: System.out.print("SCC =");
475:
476: final Iterator e = scc.iterator();
477:
478: while (e.hasNext()) {
479: final Node v = (Node) e.next();
480: System.out.print(" " + v + "{"
481: + v.key() + "}");
482: }
483:
484: System.out.println();
485: }
486:
487: // Visit the SCC with the visitor that was passed in.
488: visitor.visitComponent(scc);
489: }
490:
491: if (parent != null) {
492: final int parentDfn = dfs[parent.key()];
493: low[parentDfn] = Math.min(low[parentDfn],
494: low[dfn]);
495: }
496:
497: } else {
498: // We've already visited the node in question
499: if (parent != null) {
500: final int parentDfn = dfs[parent.key()];
501:
502: // (parent, node) is either a cross edge or a back edge.
503: if ((dfn < parentDfn) && onStack.get(dfn)) {
504: low[parentDfn] = Math.min(low[parentDfn],
505: dfn);
506: }
507: }
508: }
509: }
510: });
511: }
512:
513: /**
514: * Visits the strongly connected component that contains a given
515: * <tt>Node</tt>.
516: */
517: public void visitComponent(final Node startNode,
518: final ComponentVisitor visitor) {
519: // Number the nodes reverse post order (i.e. topological order).
520:
521: final Count count = new Count();
522:
523: final List postOrder = cfg.postOrder();
524: final ListIterator iter = postOrder.listIterator(postOrder
525: .size());
526:
527: // Perform a depth-first ordering of the nodes in the CFG to give
528: // each node a unique identifier. This is accomplished by
529: // visiting the blocks in the CFG in post-order and numbering the
530: // Nodes in the block's expression Tree in depth-first order.
531: while (iter.hasPrevious()) {
532: final Block block = (Block) iter.previous();
533:
534: block.visit(new TreeVisitor() {
535: public void visitTree(final Tree tree) {
536: tree.visitChildren(this );
537: }
538:
539: public void visitNode(final Node node) {
540: node.visitChildren(this );
541: node.setKey(count.value++);
542: }
543: });
544: }
545:
546: // Build the (strongly connected) components and call
547: // visitor.visitComponent for each.
548: cfg.visit(new TreeVisitor() {
549: ArrayList stack = new ArrayList();
550:
551: BitSet onStack = new BitSet(count.value + 1);
552:
553: int[] low = new int[count.value + 1];
554:
555: int[] dfs = new int[count.value + 1];
556:
557: int dfsNumber = 1;
558:
559: Node parent; // Parent in the SSA graph
560:
561: // Visit the blocks in the CFG in reverse postorder
562: public void visitFlowGraph(final FlowGraph cfg) {
563: final ListIterator e = postOrder.listIterator(postOrder
564: .size());
565:
566: while (e.hasPrevious()) {
567: final Block block = (Block) e.previous();
568: block.visit(this );
569: }
570: }
571:
572: public void visitTree(final Tree tree) {
573: parent = null;
574: tree.visitChildren(this );
575: }
576:
577: // This method is essentially Figure 4.6 in Taylor Simpson's PhD
578: // Thesis: www.cs.rice.edu/~lts. The implementation is a little
579: // funky, though, because someone wanted to use visitors.
580: // Grumble.
581: public void visitNode(final Node node) {
582: int dfn = dfs[node.key()];
583: // System.out.println("visit " + node + " key=" + node.key() +
584: // " dfn=" + dfn);
585:
586: if (dfn == 0) {
587: // If this node isn't equivalent to the node the care about,
588: // fergit it!
589: if (!equivalent(node).contains(startNode)) {
590: return;
591: }
592:
593: // The node in question has not yet been visited. Assign it
594: // the next dfNumber and add it to the stack. Mark all
595: // nodes that are equivalent to the node in question as
596: // being visited.
597:
598: dfn = dfsNumber++;
599: low[dfn] = dfn;
600:
601: stack.add(node);
602: onStack.set(dfn);
603:
604: Iterator equiv = equivalent(node).iterator();
605:
606: while (equiv.hasNext()) {
607: final Node e = (Node) equiv.next();
608: dfs[e.key()] = dfn;
609: }
610:
611: // Again examine each node, e, equivalent to the node in
612: // question. Then recursively visit the children of e in
613: // the SSA Graph.
614: final Node grandParent = parent;
615: parent = node;
616:
617: equiv = equivalent(node).iterator();
618:
619: while (equiv.hasNext()) {
620: final Node e = (Node) equiv.next();
621:
622: final Iterator children = children(e)
623: .iterator();
624:
625: while (children.hasNext()) {
626: final Node child = (Node) children.next();
627: child.visit(this );
628: }
629: }
630:
631: parent = grandParent; // Restore true parent
632:
633: // Now we finally get to the point where we can construct a
634: // strongly connected component. Pop all of the nodes off
635: // the stack until the node in question is reached.
636: if (low[dfn] == dfn) {
637: final ArrayList scc = new ArrayList();
638:
639: while (!stack.isEmpty()) {
640: final Node v = (Node) stack.remove(stack
641: .size() - 1);
642: onStack.clear(dfs[v.key()]);
643: scc.addAll(equivalent(v));
644:
645: if (v == node) {
646: break;
647: }
648: }
649:
650: // Sort the nodes in the SCC by their reverse
651: // post order numbers.
652: Collections.sort(scc, new Comparator() {
653: public int compare(final Object a,
654: final Object b) {
655: final int ka = ((Node) a).key();
656: final int kb = ((Node) b).key();
657: return ka - kb;
658: }
659: });
660:
661: if (SSAGraph.DEBUG) {
662: System.out.print("SCC =");
663:
664: final Iterator e = scc.iterator();
665:
666: while (e.hasNext()) {
667: final Node v = (Node) e.next();
668: System.out.print(" " + v + "{"
669: + v.key() + "}");
670: }
671:
672: System.out.println();
673: }
674:
675: // Visit the SCC with the visitor that was passed in.
676: visitor.visitComponent(scc);
677: }
678:
679: if (parent != null) {
680: final int parentDfn = dfs[parent.key()];
681: low[parentDfn] = Math.min(low[parentDfn],
682: low[dfn]);
683: }
684:
685: } else {
686: // We've already visited the node in question
687: if (parent != null) {
688: final int parentDfn = dfs[parent.key()];
689:
690: // (parent, node) is either a cross edge or a back edge.
691: if ((dfn < parentDfn) && onStack.get(dfn)) {
692: low[parentDfn] = Math.min(low[parentDfn],
693: dfn);
694: }
695: }
696: }
697: }
698: });
699: }
700:
701: /**
702: * Prints a textual representation of the strongly connected components of
703: * the SSAGraph to a PrintWriter.
704: */
705: public void printSCCs(final PrintWriter pw) {
706: final Collection equivs = this .equivalences(); // A Collection of Sets
707: final Iterator iter = equivs.iterator();
708:
709: pw.println("Strongly Connected Components of the SSAGraph");
710:
711: for (int i = 1; iter.hasNext(); i++) {
712: final Set scc = (Set) iter.next();
713: final Iterator sccIter = scc.iterator();
714:
715: pw.println(" Component " + i);
716:
717: while (sccIter.hasNext()) {
718: final Node node = (Node) sccIter.next();
719: pw.println(" " + node + " [VN = "
720: + node.valueNumber() + ", ID = "
721: + System.identityHashCode(node) + "]");
722: }
723: }
724: }
725: }
|